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)?

  • 1
    $\begingroup$ What do you mean every polynomial is an interpolating code? Why are you denoting same symbol for interpolating sequence and interpolating code? $\endgroup$ – T.... Jul 7 '19 at 14:06
  • $\begingroup$ @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$). $\endgroup$ – Michal R. Przybylek Jul 8 '19 at 18:47
  • $\begingroup$ @Turbo, I have added examples of an interpolating sequence and an interpolating code. I hope it clarifies the terminology. $\endgroup$ – Michal R. Przybylek Jul 8 '19 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.