# Interpolation of the square of a polynomial

Let $$\mathcal{P}^2_n$$ be the set of rational polynomials of degree at most $$2n$$ that are sqares of polynomials, i.e. $$\mathcal{P}^2_n$$ consists of the set of polynomials of the following form: $$(a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n)^2$$ where $$a_i \in \mathbb{Q}$$.

There is a natural (polynomial) algorithm to recover $$p \in \mathcal{P}^2_n$$ from $$2n+1$$ evaluation points. Nonetheless, one may do much better.

Let $$\langle \bar{x}, \bar{y}\rangle = \langle x_0, y_0 \rangle, \langle x_1, y_1 \rangle, \dotsc, \langle x_{n+1}, y_{n+1} \rangle$$ be a sequence of $$n+2$$ pairs of rational numbers. We shall say that $$\langle \bar{x}, \bar{y}\rangle$$ is interpolating if there exists a polynomial $$p \in \mathcal{P}^2_n$$ (the witness) such that: $$p(x_i) = y_i$$ for $$0 \leq i \leq n+1$$; and we say that it is a code if there is at most one such polynomial. By a simple counting argument one may show that every polynomial $$p \in \mathcal{P}^2_n$$ has an interpolating code.

For example, the sequence $$\langle -1, 1\rangle, \langle 0, 1\rangle, \langle 1, 1\rangle, \langle 2, 1\rangle$$ is interpolating in $$\mathcal{P}^2_2$$. Its witness is $$p(x) = 1$$. However, it is not a code, because it has another witness: $$q(x) = (x^2 - x + 1)^2$$.

On the other hand, the sequence $$\langle -1, 1\rangle, \langle 0, 1\rangle, \langle 1, 1\rangle, \langle 3, 1\rangle$$ is an interpolating code in $$\mathcal{P}^2_2$$ --- its unique witness is the constant polynomial $$p(x) = 1$$.

There are two natural problems associated with the above setting.

Problem 1: For a given interpolating sequence $$\langle \bar{x}, \bar{y}\rangle$$ find its witness $$p \in \mathcal{P}^2_n$$

Problem 2: For a given interpolating code $$\langle \bar{x}, \bar{y} \rangle$$ find its unique witness $$p \in \mathcal{P}^2_n$$

What is the computational complexity of the above problems? Are these problems polynomial (there are, of course, obvious exponential algorithms)?

• What do you mean every polynomial is an interpolating code? Why are you denoting same symbol for interpolating sequence and interpolating code? – T.... Jul 7 '19 at 14:06
• @Turbo, being an "interpolating sequence" is a property of a sequence (i.e.~there exists $p \in \mathcal{P}^2_n$ such that when we evaluate $p$ at $x_i$, we will get $y_i$) . Another property a sequence can have is being a "code" (i.e.~there exists at most one $p \in \mathcal{P}^2_n$ such that when we evaluate $p$ at $x_i$, we will get $y_i$). – Michal R. Przybylek Jul 8 '19 at 18:47
• @Turbo, I have added examples of an interpolating sequence and an interpolating code. I hope it clarifies the terminology. – Michal R. Przybylek Jul 8 '19 at 19:15