2015/10/19 by Pooya Hatami, Hatami, Pooya
Mathematics · #05-XX #11T06 #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals #Mathematics and Applications #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.1510.05334
openalex publication_date 2015/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the structure of bounded degree polynomials over finite fields. Haramaty and Shpilka [STOC 2010] showed that biased degree three or four polynomials admit a strong structural property. We confirm that this is the case for degree five polynomials also. Let \mathbbF=\mathbbFq be a prime field. [1.] Suppose f:\mathbbFn→ \mathbbF is a degree five polynomial with bias(f)=δ. Then f can be written in the form f= ∑i=1c Gi Hi + Q, where Gi and His are nonconstant polynomials satisfying deg(Gi)+deg(Hi)≤ 5 and Q is a degree ≤ 4 polynomial. Moreover, c=c(δ) does not depend on n and q. [2.] Suppose f:\mathbbFn→ \mathbbF is a degree five polynomial with bias(f)=δ. Then there exists an Ωδ(n) dimensional affine subspace V of \mathbbFn such that f restricted to V is a constant. Cohen and Tal [Random 2015] proved that biased polynomials of degree at most four are constant on a subspace of dimension Ω(n). Item [2.] extends this to degree five polynomials. A corollary to Item [2.] is that any degree five affine disperser for dimension k is also an affine extractor for dimension O(k). We note that Item [2.] cannot hold for degrees six or higher. We obtain our results for degree five polynomials as a special case of structure theorems that we prove for biased degree d polynomials when d