Abstract:
We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over~$\F$. We prove that, with very high probability, a random degree~$d+1$ polynomial has only an exponentially small correlation with all polynomials of degree~$d$, for all degrees~$d$ up to $\Theta(n)$. That is, a random degree~$d+1$ polynomial does not admit a good approximation of lower degree. In order to prove this, we provide far tail estimates on the distribution of the bias of a random low degree polynomial. Recently, several results regarding the weight distribution of Reed--Muller codes were obtained. Our results can be interpreted as a new large deviation bound on the weight distribution of Reed--Muller codes.

Abstract:
We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$. We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to $\Theta(n)$. That is, a random degree $d$ polynomial does not admit good approximations of lesser degree. In order to prove this, we prove far tail estimates on the distribution of the bias of a random low degree polynomial. As part of the proof, we also prove tight lower bounds on the dimension of truncated Reed--Muller codes.