$\newcommand\cC{\mathcal C} \newcommand\F{\mathbb F}$
We show that low degree polynomials can be efficiently recovered when some of their values are corrupted (without knowing where they are corrupted). This is a result from error-correcting codes.
Let’s say we have a polynomial $P$ with degree less than $n$. If we know $n$ values of this polynomial, the polynomial is determined uniquely. This follows from a simple argument: if $P(\alpha_i) = Q(\alpha_i)$ for $n$ distinct values $\{\alpha_1, ..., \alpha_n\}$, then $P-Q$ has $n$ roots and is thus zero or degree $n$ (contradicting the degree restrictions $\deg P, \deg Q < n$).
A slightly harder question is how we might produce $P$ from the values. Luckily for us, there is a formula. If $f(\alpha_i) = y_i$ for $i=1,2,...,n$, then $$f(x) := y_i\sum_{i=1}^k \prod_{j\neq i, j\le k} \frac{x-\alpha_j}{\alpha_i-\alpha_j}.$$
Now, let’s make it harder. Suppose we know $n$ values of a polynomial with degree $d$, but $e$ of them are corrupted. And let’s say that the polynomial is still uniquely recoverable.
If the values of $P$ and $Q$ at $n$ points can be “corrupted” by $e$ errors so that they match, then $P$ and $Q$ match at $(n-2e)$ points. Hence, this works as long as $d < \frac{n-2e}{2}$.
The challenge then is to recover the polynomial. This is theoretically straightforward (for instance, we can try each of $\binom{n}{e}$ combinations of errors), but the difficulty is doing it efficiently.
Here is a surprising algorithm which works whenever an $f$ exists:
Find $Q$ of degree $\le d+e-1$ and $P$ of degree $k$ such that $$y_i\cdot P(\alpha_i) = Q(\alpha_i),\qquad i=1,2,...,n.$$
Return $Q/P$.
On first look, this doesn’t make any sense whatsoever. But let’s suppose we had the right answer $f=Q/P$. Then, the equations in step 1 become $$P(\alpha_i) \cdot (f(\alpha_i) - y_i) = 0$$ so one candidate for $P$ is the so called error locator polynomial: $$P(x) = \prod_{i: f(\alpha_i) - y_i \neq 0} (x-\alpha_i)$$ which means $\deg P \le e$, so $\deg Q \le e+d-1$.
Furthermore, $\deg P + \deg Q \le 2e+d-1 < n$, so we have that for two different pairs $(P_1, Q_1), (P_2, Q_2)$ that satisfy step 1,
$$ \begin{align*} & P_1(\alpha_i) Q_2(\alpha_i) - P_2(\alpha_i) Q_1(\alpha_1) \\ &= P_1 (\alpha_i) \cdot (y_i P_2(\alpha_i)) - P_2(\alpha_i) \cdot (y_i P_1(\alpha_i)) \\ &= 0, \qquad i = 1,2,...,n \end{align*} $$
so since $P_1Q_2-P_2Q_1$ has $n$ roots, it is the zero polynomial. Thus, we must have $$\frac{Q_1}{P_1} = \frac{Q_2}{P_2}$$ so it doesn’t matter which pair we find.
See also: Larry Guth’s lecture notes
How do we make sense of this? One way to interpret step 1 is that we are interpolating the point-value pairs with a bivariate polynomial. Here’s the new wording for comparison:
Loosely, this means that once the curves $\{Q(x,y) = 0\}$ and $\{y = P(x)\}$ intersect at enough points, they become the same curve and we have found $P$.
Here are the details.
Step 1. We have $(d_0+d_1+2)$ degrees of freedom, and $n$ constraints, so $d_1 + d_2 + 2 > n$, guarantees a non-trivial solution $Q$. In linear algebra language, we are counting the dimensions of linear map $$Q \mapsto (Q(\alpha_1,y_1), ..., Q(\alpha_n,y_n)).$$
Step 2. If $y$ agreed with $f$ at $n-e$ spots, then this forces the polynomial $Q(x, f(x))$ to have at least $n-e$ roots but degree $\le \max\{d_0, d_1 + d - 1\}$, so if $$d_0, d_1+d-1 < n-e,$$ then $Q(x,f(x))$ is the zero polynomial and $f=Q_0/Q_1$ is valid. This means that we’re good for all $$e \le \frac{n-d-1}{2}.$$
This is really close to optimal, and also gives us a hint about how we can construct the error locator polynomial.
Concretely, this means that if we have a polynomial of degree $n/100$, then we can correct for up to around $\frac{1}{2}\left(1- \frac{1}{100}\right)n$ errors - almost half of all the values can be wrong and we’ll still get it right at the end! Of course, if we allow half of all the values to be wrong, then any two set of values can clash, so this is really strong.
I was going to talk about the Guruswami-Sudan algorithm here: basically, even if the polynomial cannot be uniquely recovered, we can have an algorithm spit out a (small) list of all the possible polynomials. But maybe for a next article!
Let $p$ be an odd prime, and $d<\frac{p-1}{2}$. Prove that there are no more than $10p$ polynomials $f(x)\in\mathbb{F}_p$ with degree $d$ such that $f(x)=2^x$ on more than $\sqrt{pd}$ values.
We will pretty much do this combinatorially. Suppose there are polynomials $\{p_i\}$ and define the sets $$S_i = \{x: p_i(x) = 2^x\} \subset \mathbb F_p$$
Then we require the sets to satisfy (1) $S_i > \sqrt{pd}$, (2) $|S_i \cap S_j| < d$.
Denote $t=\min |S_i| > \sqrt{pd}$. Now we define the indicator vector $s_i$ whose $x$-th coordinate is 1 if $x\in S_i$ and $0$ otherwise. Note that $s_i \cdot s_j < d$.
Consider $$\tilde s_i := s_i - \frac{d}{t} \cdot \bf{1}$$ Then it is clear that $$\tilde s_i \cdot \tilde s_j = s_i\cdot s_j - \frac{d}{t}(|S_i|+|S_j|) +\frac{p d^2}{t^2} < 0$$ so the vectors $\{\tilde s_i\}$ are pairwise distinct and obtuse. However, in $\mathbb R^p$ there are at most $p+1$ pairwise obtuse vectors, so originally there are at most $p+1$ such polynomials.