On the Structure of Quintic Polynomials

DOI10.4230/LIPICS.APPROX-RANDOM.2016.33MaRDI QIDQ4636466zbMATH OpenOpenAlexFDO

Authors Pooya Hatami

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1510.05334

zbMATH Keywords

higher-order Fourier analysispolynomialsregularity lemmasstructure theorem

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Abstract: 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=mathbb{F}_q$ be a prime field. [1.] Suppose $f:mathbb{F}^{n}ightarrowmathbbF$ is a degree five polynomial with bias(f)=delta. Then f can be written in the form $f=su{m}_{i=1}^c{G}_i{H}_i+Q$, where $G_i$ and $H_i$s are nonconstant polynomials satisfying $deg(G_i)+deg(H_i)leq5$ and $Q$ is a degree $leq4$ polynomial. Moreover, $c=c(delta)$ does not depend on $n$ and $q$. [2.] Suppose $f:mathbb{F}^{n}ightarrowmathbbF$ is a degree five polynomial with $bias(f)=delta$. Then there exists an $Omeg{a}_{d}elta(n)$ dimensional affine subspace $V$ of $mathbb{F}^n$ 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 $Omega(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<|mathbbF|+4$. While the $d<|mathbbF|+4$ assumption seems very restrictive, we note that prior to our work such structure theorems were only known for $d<|mathbbF|$ by Green and Tao [Contrib. Discrete Math. 2009] and Bhowmick and Lovett [arXiv:1506.02047]. Using algorithmic regularity lemmas for polynomials developed by Bhattacharyya, et. al. [SODA 2015], we show that whenever such a strong structure exists, it can be found algorithmically in time polynomial in n.

Recommendations

• On Lecacheux's family of quintic polynomials
• On a sequence of nonsolvable quintic polynomials
• scientific article; zbMATH DE number 1492883
• On \(D_5\)-polynomials with integer coefficients
• Dihedral quintic polynomials and a theorem of Galois
• QUINTIC POLYNOMIALS OF HASHIMOTO–TSUNOGAI, BRUMER AND KUMMER
• On the reducible quintic complete base polynomials
• On quintic equations
• On the number of quintic fields
• scientific article; zbMATH DE number 1910411

Cited in

(12)

• On the Lagrange resolvents of a dihedral quintic polynomial
• Quincunx fundamental refinable functions in arbitrary dimensions
• The stratification by rank for homogeneous polynomials with border rank 5 which essentially depend on five variables
• On the bias of cubic polynomials
• A note on quintic polynomial approximation of generalized Cornu spiral segments
• Reducibility and the Galois group of a parametric family of quintic polynomials
• The fifth coefficient of adjoint polynomial and a new invariant.
• scientific article; zbMATH DE number 4045802 (Why is no real title available?)
• scientific article; zbMATH DE number 1492883 (Why is no real title available?)
• scientific article; zbMATH DE number 2204503 (Why is no real title available?)
• Two structural results for low degree polynomials and applications
• Highly Symmetric Quintic Quotients

This page was built for publication: On the Structure of Quintic Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636466)