Bias implies low rank for quartic polynomials

2019/02/27 by Amichai Lampert, Lampert, Amichai
Computer Science · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1902.10632

openalex publication_date 2019/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the structure of polynomials of degree four in many variables over a fixed prime field \mathbbF=\mathbbF_p. In 2007, Green and Tao proved that if a polynomial f:\mathbbFⁿ→\mathbbF is poorly distributed, then it is a function of a few polynomials of smaller degree. In 2009, Haramaty and Shpilka found an effective bound for f of degree four: If bias(f)≥δ, then the number of lower degree polynomials required is at most polynomial in 1/δ and f has a simple presentation as a sum of their products. We make a step towards showing that in fact the number of lower degree polynomials required is at most log-polynomial in 1/δ, with the same simple presentation of f. This result was a Master's thesis supervised by T. Ziegler at the Hebrew University of Jerusalem, submitted in October 2018. A log-polynomial bound for polynomials of arbitrary degree was recently proved independently by Milicevic and by Janzer.

Related

• Worst Case to Average Case Reductions for Polynomials
• On the Structure of Cubic and Quartic Polynomials
• Bias vs structure of polynomials in large fields, and applications in information theory
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• On the Structure of Quintic Polynomials