Back to Math Tools
Back to notes

# Polynomials

## Low degree extension

Let $\mathbb{F}$ be a field, $H,S\subseteq\mathbb{F}$ are subsets, and $f:H^m\rightarrow S$ for some $m\in\bbN$. Then there exists a $m$-variate polynomial $\tilde{f}:\mathbb{F}^m\rightarrow\mathbb{F}$ such that

• (low degree) the degree of $\tilde{f}$ in each variable is at most $h-1$ where $h=\card{H}$, and
• (extension) for any $x\in H^m$, $\tilde{f}(x)=f(x)$.

The idea is based on Lagrange’s interpolation. Denote the elements in $H$ as $H=\{a_1,\dots,a_h\}$, define $\tilde{f}$ as follows. $$\tilde{f}(x) := \sum_{i_1,\dots i_m\in[h]}\phi(a_{i_1},\dots,a_{i_m})\prod_{t\in[m]}\frac{\prod_{j\neq i_t}(x_t-a_j)}{\prod_{j\neq i_t}a_{i_t}-a_j}.$$

Clearly that the degree of $\tilde{f}$ in each variable is at most $h-1$. To check the second property, consider any $x\in H^m$, we have $x=(a_1,\dots,a_m)$ for some $a_i\in H$ for any $i\in[m]$. Then, by the definition of $\tilde{f}$, we have $\tilde{f}(x)=f(x)$.

## Schwartz-Zippel lemma

Let $\mathbb{F}$ be a field and $S\subseteq\mathbb{F}$. For any degree $d$ nonzero $m$-variate polynomial $f$ over $\mathbb{F}$ for some $m\in\bbN^+$, we have $$\mathbb{P}_{a_1,\dots,a_m\leftarrow S}[f(a_1,\dots,a_m)=0]\leq\frac{d}{\card{S}}.$$

Let’s prove by induction on the number of variables. When $m=1$, as the number of roots of a degree $d$ nonzero polynomial is at most $d$, the inequality holds.

Suppose the inequality holds for degree less than $m$, rewrite $f(x_1,\dots,x_m)$ as follows.

$$f(x_1,\dots,x_m) = \sum_{i=0}^{\ell}f_i(x_2,\dots,x_m)x_1^i,$$

where $f_i$ is a $(m-1)$-variate polynomial of degree at most $d-i$ and $\ell\leq d$. As a result, by the induction hypothesis, the probability that $f(x_1,a_2,\dots,a_m)$ is a zero polynomial can be upper bounded by $\frac{d-\ell}{\card{S}}$. Thus,

\begin{align} &\mathbb{P}_{a_1,\dots,a_m\leftarrow S}[f(a_1,\dots,a_m)=0]\\
&= \mathbb{P}_{a_1\leftarrow S}[f(a_1,\dots,a_m)|f(\cdot,a_2,\dots,a_m)\text{ is nonzero}]\\
&\cdot\mathbb{P}_{a_2,\dots,a_m\leftarrow S}[f(\cdot,a_2,\dots,a_m)\text{ is nonzero}]\\
&+ \mathbb{P}_{a_1\leftarrow S}[f(a_1,\dots,a_m)|f(\cdot,a_2,\dots,a_m)\text{ is zero}]\\
&\cdot\mathbb{P}_{a_2,\dots,a_m\leftarrow S}[f(\cdot,a_2,\dots,a_m)\text{ is zero}]\\
&\leq \frac{\ell}{\card{S}}\cdot1+ 1\cdot\frac{d-\ell}{\card{S}}\\
&=\frac{d}{\card{S}}. \end{align}

## Composition techniques

### Bundling polynomials into a single polynomial

Given polynomials $p_1,\dots,p_t:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ where $\mathbb{F}$ is a field and $\card{\mathbb{F}}\geq t$. Suppose each of the degree of the polynomials is at most $\alpha$, then there exists a polynomial $q:\mathbb{F}^{\ell+1}\rightarrow\mathbb{F}$ of degree at most $\alpha+t-1$ such that for any $i\in[t]$ and $z\in\mathbb{F}^{\ell}$, $q(i,z)=p_i(z)$.

Construct $q$ as follows. First, for each $i\in[t]$, define polynomial $$\delta_{i}(x) := \prod_{j\neq i\in[t]}\frac{x-j}{i-j}.$$ Namely, for any $i,j\in[t]$, $\delta_i(j)=\mathbf{1}_{i=j}$. Note that the degree of $\delta_i$ is at most $t-1$.

Next, define polynomial $$q(x,z) := \sum_{i\in[t]}\delta_i(x)\cdot p_i(z).$$ Note that the degree of $q$ is at most $\alpha+t-1$ and for any $i\in[t]$ and $z\in\mathbb{F}^{\ell}$, $q(i,z)=p_i(z)$, which is the goal of the lemma.

### Low degree extension

Given a degree $d$ polynomial $p:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ and $H\subseteq\mathbb{F}$. Then there exists a polynomial $q$ of degree $\ell\cdot\card{H}$ such that $p$ is nonzero on $H^{\ell}$ iff $q$ is nonzero on $\mathbb{F}^{\ell}$.

Denote $H=\{h_1,\dots,h_{\card{H}}\}$. Define $p_1:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ as follows.

$$p_1(x_1,x_2,\dots,x_{\ell})=\sum_{t\in[\card{H}]}p(h_t,x_2,\dots,x_{\ell})\cdot x_1^t.$$

Observe that $p$ is nonzero on $H^{\ell}$ iff $p_1$ is nonzero on $\mathbb{F}\times H^{\ell-1}$. Similarly, for $i=2,\dots,\ell$, define $p_i:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ as follows.

$$p_{i}(x_1,x_2,\dots,x_{\ell})=\sum_{t\in[\card{H}]}p(x_1,\dots,x_{i-1},h_t,\dots,x_{\ell})\cdot x_i^t.$$ Thus, we have $p$ is nonzero on $H^{\ell}$ iff $p_i$ is nonzero on $\mathbb{F}^{i}\times H^{\ell- i}$. Take $q=p_{\ell}$

Also, by the construction, for each $i\in[\ell]$, the degree of $x_i$ in $q$ is at most $\card{H}$. Thus, the total degree of $q$ is at most $\ell\cdot\card{H}$.

## Local characterizations

Local characterizations of polynomials are useful tools for property testing in which one can test whether an oracle is close to a low degree polynomial. Intuitively, as a global property is equivalent to a set of local properties, by probabilistically checking whether the oracle satisfies an random local property, one can infer the closeness of the oracle having that property. See this note for details.

### Local characterizations of multivariate polynomial

Let $\mathbb{F}$ be a field and $f$ be a $m$-variate polynomial over $\mathbb{F}$ where $\card{\mathbb{F}}>2d$. $f$ is of degree at most $d$ iff for any line $L_{\bs,\bh}:=\{f(\bs+t\cdot \bh)\}_{t\in\mathbb{F}}$, where $\bs,\bh\in\mathbb{F}^m$, is a polynomial of degree at most $d$ in $i$.

In the following, denote $f_{\bs,\bh}(t)=f(\bs+t\cdot\bh)$ for any $\bs,\bh\in\mathbb{F}$ and $t\in\mathbb{F}$.

• ($\Rightarrow$) This direction is trivial. For any $\bs,\bh\in\mathbb{F}$ and $t\in\mathbb{F}$, we have $f(\bs+t\cdot \bh)=f(\bs_1+t\cdot\bh_1,\dots,\bs_m+t\cdot\bh_m)$. As the degree of the $i$th coordinate is the same as the degree of $(\bs_i+t\cdot\bh_i)$ for any $i\in[m]$, the total degree of $t$ in $f_{\bs,\bh}(t)$ is the same as the total degree of $f$, which is at most $d$.
• ($\Leftarrow$) This direction is proved by induction on the number of variables and Schwartz-Zippel lemma.

For the base case, clearly that the statement holds for univariate polynomial. Suppose the statement holds for $(m-1)$-variate polynomial, consider the following.

First, we can yield the following loose upper bound on the degree of $f$ by the induction hypothesis.

Suppose the local characterization lemma holds for polynomials with at most $m-1$ variables. For any $\bs,\bh\in\mathbb{F}^m$, $L_{\bs,\bh}$ is a polynomial of degree at most $d$, then the degree of $f$ is at most $2d$.

For any $\bx\in\mathbb{F}^{m-1}$, let $\bh=(\bx,0)$, we have $f_{\mathbf{0},\bh}$ is polynomial of degree at most $d$ by the assumption. Specifically, we can rewrite $f$ as follows. $$f(x_1,\dots,x_m) = \sum_{a=0}^{d}f(x_1,\dots,x_{m-1},a)\delta_a{x_m},$$ where $\delta_a$ is the degree $d$ polynomial such that $\delta_{a}(a’)=\mathbf{1}_{a=a’}$ for any $a,a’\in\{0,1,\dots,d\}$.

As $f(x_1,\dots,x_{m-1},a)$ also satisfies the assumption and only has $m-1$ variables for any $a\in\{0,1,\dots,d\}$, by the induction hypothesis, $f(x_1,\dots,x_{m-1},a)$ is of degree at most $d$. Thus, the degree of $f$ is at most $2d$.

With the above loose upper bound, we can use the Schwartz-Zippel lemma to show that the degree of $f$ is the same as the degree of $f_{\mathbf{0},\bh}$ for some $\bh\in\mathbb{F}^m$.

Suppose the degree of $f$ is at most $2d$ and $\card{\mathbb{F}}>2d$, then there exists $\bh\in\mathbb{F}^m$ such that $\text{deg}(f)=\text{deg}(f_{\mathbf{0},\bh})$.

Observe that $$f_{\mathbf{0},\bh}(t)=f(t\cdot\bh_1,\dots,t\cdot\bh_m)=\sum_{i=0}^{\text{deg}(f)}f_i(\bh)t^i,$$ where $f_i$ is a polynomial of degree at most $2d$ by the above loos upper bound. Note that the degree of $h_{\mathbf{0},\bh}$ is the largest $i$ such that $f_i(\bh)$ is nonzero. As a result, the probability of $\text{deg}(f_{\mathbf{0},\bh})=\text{deg}(f)$ can be lower bounded by the probability of $f_{\text{deg}(f)}(\bh)$ not being zero.

\begin{align} \mathbb{P}_{\bh}[\text{deg}(f_{\mathbf{0},\bh})=\text{deg}(f)]&=\mathbb{P}_{\bh}[f_{\text{deg}(f)}(\bh)\neq0]\\
&>1-\frac{2d}{\card{\mathbb{F}}}>0. \end{align}

Thus, by the probabilistic argument, we know that there exists $\bh\in\mathbb{F}^m$ such that $\text{deg}(f)=\text{deg}(f_{\mathbf{1},\bh})$.

Finally, by the assumption, for any $\bh\in\mathbb{F}^m$, $\text{deg}(f_{\mathbf{0},\bh})\leq d$. Thus, directly from the above claim, we have $\text{deg}(f)\leq d$.

### Local characterization of univariate polynomial

Let $\mathbb{F}$ be a field and $1\leq d<\card{\mathbb{F}}+1$. There exists $e_1,\dots,e_{d+1},\alpha_1,\dots,\alpha_{d+1}\in\mathbb{F}$ such that for any univariate polynomial $f:\mathbb{F}\rightarrow\mathbb{F}$ of degree at most $d$ and $x,h\in\mathbb{F}$ we have $$f(x) = \sum_{i\in[d+1]}\alpha_i\cdot f(x+e_i\cdot h).$$

Here we only prove the special case where $\mathbb{F}$ is a prime field. Basically, for general fields, the ideas are the same.

For prime field, we’ll take $e_i=i$ and $\alpha_i=(-1)^{i+1}\binom{d+1}{i}$ for any $i\in[d+1]$.

Let’s prove by induction on $d$. Clearly that when $f$ is a constant function, i.e., $d=0$, we have $f(x)=f(x+h)$ for any $x,h\in\mathbb{F}$. Now, suppose that the statement holds for polynomial of degree less than $d$.

Consider the derivative of $f$: $f’$, which is defined as $f’(x):=f(x+1)-f(x)$ for any $x\in\mathbb{F}$. For any $x\in\mathbb{F}$, we can rewrite $f(x)$ as $$f(x) = f(x+1)-f’(x).$$ By induction hypothesis, we have \begin{align} f’(x) &= \sum_{i=1}^d(-1)^{i+1}\binom{d}{i}f’(x+i)\\
&= \sum_{i=1}^d(-1)^{i+1}\binom{d}{i}\Big(f(x+i+1)-f(x+i)\Big)\\
&= -\sum_{i=1}^d(-1)^{i+1}\binom{d}{i}f(x+i) - \sum_{i=2}^{d+1}(-1)^{i+1}\binom{d}{i-1}f(x+i). \end{align} Combine the above two equations we have \begin{align} f(x) &= f(x+1)+\sum_{i=1}^d(-1)^{i+1}\binom{d}{i}f(x+i)+\sum_{i=2}^{d+1}(-1)^{i+1}\binom{d}{i-1}f(x+i)\\
&=\sum_{i=1}^d(-1)^{i+1}[\binom{d}{i}+\binom{d}{i-1}]f(x+i) + (-1)^{d+2}\binom{d}{d}f(x+d+1)\\
&=\sum_{i=1}^{d+1}(-1)^{i+1}\binom{d+1}{i}f(x+i). \end{align}