# Real versus Finite field polynomials

Let $f$ be a Boolean function.

Let $g$ be the minimum degree real polynomial that represents $f$ with degree $d$.

Let $g_{p}$ be the minimum degree $\Bbb F_p$ polynomial that represents $f$ with degree $d_p$.

Does $\exists p:d_p\leq d\leq d_p^c$ hold with some constant $c>0$?

$d_2\leq d\leq d_2^c$ does not hold with some constant $c>0$.

Counter example at $\Bbb F_2$.

$IP_n=\sum_{i=1}^nx_iy_i\bmod 2$ does have $d_2=2$, while $d=\Omega(n)$.

• Did you try generalizing your example to other $p$? Jan 31 '15 at 5:09
• I tried for $IP_{n,p}=(\sum_{i=1}^nx_iy_i\mod p)\mod 2$, Jan 31 '15 at 5:50
• Did you use the fact that mod 2 is a constant polynomial? E.g. $2x^2+2x$ when $p=3$. Jan 31 '15 at 21:15
• Interesting no I did not think of that. I just thought we have to interpolate at $p$ distinct terms instead of $n$ terms. Jan 31 '15 at 21:30