On the structure of cubic and quartic polynomials

DOI10.1145/1806689.1806736zbMATH Open1293.11104arXiv0908.2853OpenAlexW1989959918MaRDI QIDQ2875161FDOQ2875161

Authors: Elad Haramaty, Amir Shpilka 

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias (i.e. they are not equidistributed). This result generalizes the corresponding results from the theory of quadratic forms. It also significantly improves the results of Green and Tao and Kaufman and Lovett for such polynomials. 2. For the case of degree four polynomials with high Gowers norm we show that (a subspace of co-dimension O(1) of) F^n can be partitioned to subspaces of dimension Omega(n) such that on each of the subspaces the polynomial is equal to some degree three polynomial. It was shown by Green and Tao and by Lovett, Meshulam and Samorodnitsky that a quartic polynomial with a high Gowers norm is not necessarily correlated with any cubic polynomial. Our result shows that a slightly weaker statement does hold. The proof is based on finding a structure in the space of partial derivatives of the underlying polynomial.

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

Recommendations

• On some cubic or quartic algebraic units
• On the structure of polynomial roots
• Cubic polynomials and quadratic forms
• On binary cubic and quartic forms
• On Quadrapell numbers and Quadrapell polynomials
• On a quartic polynomials family of two parameters
• Cubic, quartic and sextic Pólya fields
• Characterization of quadratic and cubic \(\sigma\)-polynomials

zbMATH Keywords

Gowers normcubic polynomialsquartic polynomials

Mathematics Subject Classification ID

Polynomials over finite fields (11T06)

Cited In (10)

• On hitting-set generators for polynomials that vanish rarely
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• On the bias of cubic polynomials
• Properties of high rank subvarieties of affine spaces
• Title not available (Why is that?)
• On hitting-set generators for polynomials that vanish rarely
• Polynomial bound for the partition rank vs the analytic rank of tensors
• The analytic rank of tensors and its applications
• Partition and analytic rank are equivalent over large fields
• On the bias of Reed-Muller codes over odd prime fields

This page was built for publication: On the structure of cubic and quartic polynomials

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