Structure and Randomness for Finite-field Polynomials are (almost) Equivalent

What can be said about a system of polynomial equations over a finite field if its number of solutions deviates from that of a random system? Answer: Roughly, one of the polynomials (or a linear combination thereof) can be written in terms of “few” polynomials of lower degree.

What can be said about a polynomial of degree k over a finite field whose derivatives of order k (rather than k+1) are already biased towards 0? Answer: Roughly, it has "large" correlation with some polynomial of lower degree.

The quantitative versions of these questions are important in number theory, additive combinatorics, coding theory, and more, and it is known that they are all related to yet another question: the so-called partition versus analytic rank conjecture for tensors. We will discuss a recent proof of the conjecture(s) up to a logarithmic factor.

The proof has little dependence on prior results (relying on not much more than the Schwartz-Zippel lemma), and at its core is “local rank”, a new, combinatorial notion of tensor rank which we believe could be a powerful tool for studying higher-degree polynomials.

Joint work with Daniel Zhu.

(No prior background will be assumed in the talk beyond linear algebra)