Sharp Effective Finite-Field Nullstellensatz

DOI10.1080/00029890.2023.2230810MaRDI QIDQ6058311zbMATH OpenOpenAlexFDO

Authors Guy Moshkovitz

Publication date 1 November 2023

Published in The American Mathematical Monthly (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Complexity of proofs (03F20) Polynomials over finite fields (11T06)

Abstract: The (weak) Nullstellensatz over finite fields says that if $P_1,ldots,P_m$ are $n$-variate degree-$d$ polynomials with no common zero over a finite field $mathbbF$ then there are polynomials $R_1,ldots,R_m$ such that $R_1{P}_1+cdots+R_m{P}_{m}equiv1$. Green and Tao [Contrib. Discrete Math. 2009, Proposition 9.1] used a regularity lemma to obtain an effective proof, showing that the degrees of the polynomials $R_i$ can be bounded independently of $n$, though with an Ackermann-type dependence on the other parameters $m$, $d$, and $|mathbbF|$. In this paper we use the polynomial method to give a proof with a degree bound of $md(|mathbbF|-1)$. We also show that the dependence on each of the parameters is the best possible up to an absolute constant. We further include a generalization, offered by Pete L. Clark, from finite fields to arbitrary subsets in arbitrary fields, provided the polynomials $P_i$ take finitely many values on said subset.

Recommendations

• Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
• A generic effective Nullstellensatz
• A short proof of combinatorial Nullstellensatz
• Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz
• Combinatorial Nullstellensatz approach to polynomial expansion
• scientific article; zbMATH DE number 4165041
• Two variants of Hilbert’s Nullstellensatz
• Punctured combinatorial Nullstellensätze
• Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry

Cites work

• Bounds for the degrees in the Nullstellensatz
• Démonstration d'une hypothèse de M. Artin
• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• Random CNF's are hard for the polynomial calculus
• Sharp Effective Nullstellensatz
• The Combinatorial Nullstellensätze revisited
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• Zeroes of Polynomials Over Finite Fields

Cited in

(3)

• An improvement to Chevalley's theorem with restricted variables
• A Refinement of a Mixed Sparse Effective Nullstellensatz
• Ramsey numbers through the lenses of polynomial ideals and Nullstellensätze

This page was built for publication: Sharp Effective Finite-Field Nullstellensatz

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