<p>Let <span class="math-container">$\mathcal{P}^2_n$</span> be the set of rational polynomials of degree at most <span class="math-container">$2n$</span> that are <em>sqares</em> of polynomials, i.e. <span class="math-container">$\mathcal{P}^2_n$</span> consists of the set of polynomials of the following form:
<span class="math-container">$$(a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n)^2$$</span>
where <span class="math-container">$a_i \in \mathbb{Q}$</span>.</p>

<p>There is a natural (polynomial) algorithm to recover <span class="math-container">$p \in \mathcal{P}^2_n$</span> from <span class="math-container">$2n+1$</span> evaluation points. Nonetheless, one may do much better.</p>

<p>Let <span class="math-container">$\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$</span> be a sequence of <span class="math-container">$n+2$</span> pairs of rational numbers. We shall say that <span class="math-container">$\langle \bar{x}, \bar{y}\rangle$</span> is <em>interpolating</em> if there exists a polynomial <span class="math-container">$p \in \mathcal{P}^2_n$</span> (the witness) such that: <span class="math-container">$p(x_i) = y_i$</span> for <span class="math-container">$0 \leq i \leq n+1$</span>; and we say that it is a <em>code</em> if there is at most one such polynomial. By a simple counting argument one may show that every polynomial <span class="math-container">$p \in \mathcal{P}^2_n$</span> has an interpolating code.</p>

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

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

<p>There are two natural problems associated with the above setting.</p>

<p>Problem 1: For a given interpolating sequence <span class="math-container">$\langle \bar{x}, \bar{y}\rangle$</span> find its witness <span class="math-container">$p \in \mathcal{P}^2_n$</span></p>

<p>Problem 2: For a given interpolating code <span class="math-container">$\langle \bar{x}, \bar{y} \rangle$</span> find its unique witness <span class="math-container">$p \in \mathcal{P}^2_n$</span></p>

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

CC BY-SA 4.0
2019-07-07T14:06:14.207Z
What do you mean every polynomial is an interpolating code? Why are you denoting same symbol for interpolating sequence and interpolating code?
Turbo
CC BY-SA 4.0
2019-07-08T18:47:31.550Z
@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
CC BY-SA 4.0
2019-07-08T19:15:48.750Z
@Turbo, I have added examples of an interpolating sequence and an interpolating code. I hope it clarifies the terminology.
Michal R. Przybylek
<ds.algorithms>
Interpolation of the square of a polynomial
Michal R. Przybylek
# Interpolation of the square of a polynomial

(Asked by: username_0 on 2019-07-05)

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

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: What do you mean every polynomial is an interpolating code? Why are you denoting same symbol for interpolating sequence and interpolating code?  
> **username_0**: @username_1, 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$).  
> **username_0**: @username_1, I have added examples of an interpolating sequence and an interpolating code. I hope it clarifies the terminology.  

---

## 0 answers

