Low degree check using barycentric formula

Barycentric formula

$$A(X) = \prod_{i=0}^{n-1} (X-x_i)$$

$$A'(X) = \sum_{j=0}^{n-1} \prod_{i \not= j}(X-x_i)$$

$$f(z) = A(z)\sum_{i=0}^{n-1} \frac{f_i}{A'(x_i)} \frac{1}{z-x_i}$$

Check that a polynomial is of low degree

Let $\omega$ be an $n$-th root of unity satisfying $A(X)= X^n-1=0$.

Let $f(X)$ be a polynomial defined by its evaluations $f_i=f(\omega^i)$ ($n$ values). We want to check that $f(X)$ is of degree at most $n/2-1$.

Let $g(X)$ be the polynomial function resulting from interpolating $f_0, f_2, f_4, \ldots$ and $h(X)$ the same by interpolating $f_1, f_3, f_5, \ldots$. If $g(X)==h(X)$, then the degree of $f(X)$ must be less than $n/2-1$.

We sample a random point $r$ and use the barycentric formular to evaluat $g(X)$ and $h(X)$ at $r$. If $g(r)=h(r)$ then with large probability $g(X)=h(X)$ (Schwartz-Zippel Lemma). In order to compute this we use the barycentric formula for $g(r)$ and $h(r)$:

$$B(X) = X^\frac{n}{2} - 1$$

$$B'(X) = \frac{n}{2} X^{\frac{n}{2} - 1}$$

$$g(r) = B(r)\sum_{\substack{i=0 \\ i \text{ even}} }^{n-1} \frac{f_i}{B'(\omega^i)} \frac{1}{r-\omega^i} = \frac{2}{n} \sum_{\substack{i=0 \\ i \text{ even}} }^{n-1} \frac{f_i}{\omega^{i(\frac{n}{2} - 1)}} \frac{r^\frac{n}{2} - 1}{r-\omega^i}$$

$$C(X) = X^\frac{n}{2} + 1$$

$$C'(X) = \frac{n}{2} X^{\frac{n}{2} - 1} = B'(X)$$

$$h(r) = C(r)\sum_{\substack{i=0 \\ i \text{ odd}} }^{n-1} \frac{f_i}{C'(\omega^i)} \frac{1}{r-\omega^i} = \frac{2}{n} \sum_{\substack{i=0 \\ i \text{ odd}} }^{n-1} \frac{f_i}{\omega^{i(\frac{n}{2} - 1)}} \frac{r^\frac{n}{2} + 1}{r-\omega^i}$$

So to check that $f(X)$ is of low degree verify that

$$g(r) - h(r) = \frac{2}{n} \sum_{\substack{i=0} }^{n-1} \frac{f_i}{\omega^{i(\frac{n}{2} - 1)}} \frac{(-1)^i r^\frac{n}{2} - 1}{r-\omega^i} = 0$$

Proof of correctness

By contradiction. Assume that there does not exist a polynomial of degree $n-1$ or less that interpolates all $f_i$.

$g(X)$ and $h(X)$ are both of degree at most $n-1$; if $g(X)=h(X)$ then they would both interpolate all the points, which thus cannot be true. Thus $g(X)\not=h(X)$.

This means that $p(X)=g(X)-h(X)$ is a polynomial of degree at most $n-1$ and not identical to $0$; accordingly it has at most $n-1$ zeros in $\mathbb F_p$. The probability that $p(r)=0$ for a random $r$ is thus $\leq \frac{n-1}{p}$ and thus negligible.

Generalisation to any degree

More generally, how can we check that $n$ points are on a polynomial of degree $d$, where $d$ is not necessarily \(\frac{n}{2} - 1\)?

We can still do this by applying the barycentric formular to (1) and $d+1$ points and (2) all $n$ points.

$$B(X) = \prod_{i=0}^{d} (X-\omega^i)$$

$$B'(X) = \sum_{j=0}^{d} \prod_{i \not= j}(X-\omega^i)$$

$$g(r) = B(r)\sum_{i=0}^d\frac{f_i}{B'(\omega^i)}\frac{1}{r-\omega^i}$$

$$C(X) = X^n - 1$$

$$C'(X) = n X^{n - 1}$$

$$h(r) = C(r)\sum_{i=0}^{n-1} \frac{f_i}{C'(\omega^i)} \frac{1}{r-\omega^i} = \frac{1}{n} \sum_{i=0}^{n-1} \frac{f_i}{\omega^{i(n - 1)}} \frac{r^n - 1}{r-\omega^i}$$

$$g(r) - h(r) =\sum_{i=0}^d \frac{f_i}{r-\omega^i}\left(\frac{B(r)}{B'(\omega^i)} - \frac{r^n - 1}{n\omega^{i(n - 1)}} \right) - \sum_{i=d}^{n-1} \frac{f_i}{r-\omega^i}\frac{r^n - 1}{n\omega^{i(n - 1)}}$$

The main downside of this formular is that computing the $B'(\omega^i)$ takes quadratic time and this is not a linear algorithm anymore. However when $d$ and $n$ are known beforehand this can be precomputed.