Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial…

Abstract

This paper proves asymptotically optimal linear degree lower bounds for Nullstellensatz and Polynomial Calculus, yielding a four-way polynomial-versus-exponential proof-size classification for uniform polynomial consequences over fields of positive characteristic. The size bounds use full, explicit coefficient lists, including zeros. Apart from a fixed finite initial range, exactly one of four cases occurs: T₁, bounded degree; T₂, degree at least linear in the universe size n; T₃, constant degree on some residue classes and at least linear degree on the others; or T₄, infinitely many recurring finite degrees, with bounded-degree subsequences and finite Ω(n) peaks at arbitrarily large sizes. Thus the size patterns are polynomial bounds, exponential lower bounds, a periodic mixture, or polynomial subsequences with finite exponential peaks, respectively. Underivable targets have degree ∞, and both proof systems assign the same type. The result strengthens my 2008--2009 refutation classification and extends it to uniform consequences. The proof uses degree-preserving lifting with onset and period bounds linear in the degree. A common p-adic hardness spectrum describes the four types topologically. Distinguishing any two types is undecidable already for refutations. The linear degree bounds, four-way classification and pairwise undecidability results have been formalised and verified in Lean. The Lean formalisation, verification records and an accompanying tutorial are available in the supporting materials (https://doi.org/10.5281/zenodo.23965838).

On the uniform flatness of polynomial graphs
Xieping Wang, Li Zhang
arXiv14 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Dice enterprises and polynomial approximation: uniform query tails
Jessica Taylor
arXiv28 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv
Polynomial-in-r bounds for forbidden traces of uniform hypergraphs
Pei Wu
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Polynomial Difference Schemes with Energy and Momentum Multipliers on Orthogonal Uniform Meshes: Stencil Restrictions and Monge--Ampère-Type Examples
E. I. Kaptsov
arXiv6 Oct 2026PreprintarXiv licenceFull textMathematical physics Numerical analysis & scientific computingarXiv
Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter
Denis Belomestny
arXiv29 Aug 2026PreprintCC BY 4.0Full textOptimisation & control StatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{riis2026degree,
  title = {{Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus}},
  author = {Søren Riis},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.07280},
  eprint = {2611.07280},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07280},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus
AU  - Søren Riis
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.07280
UR  - https://arxiv.org/abs/2611.07280
AB  - This paper proves asymptotically optimal linear degree lower bounds for Nullstellensatz and Polynomial Calculus, yielding a four-way polynomial-versus-exponential proof-size classification for uniform polynomial consequences over fields of positive characteristic. The size bounds use full, explicit coefficient lists, including zeros. Apart from a fixed finite initial range, exactly one of four cases occurs: T_1, bounded degree; T_2, degree at least linear in the universe size n; T_3, constant degree on some residue classes and at least linear degree on the others; or T_4, infinitely many recurring finite degrees, with bounded-degree subsequences and finite Ω(n) peaks at arbitrarily large sizes. Thus the size patterns are polynomial bounds, exponential lower bounds, a periodic mixture, or polynomial subsequences with finite exponential peaks, respectively. Underivable targets have degree ∞, and both proof systems assign the same type. The result strengthens my 2008--2009 refutation classification and extends it to uniform consequences. The proof uses degree-preserving lifting with onset and period bounds linear in the degree. A common p-adic hardness spectrum describes the four types topologically. Distinguishing any two types is undecidable already for refutations. The linear degree bounds, four-way classification and pairwise undecidability results have been formalised and verified in Lean. The Lean formalisation, verification records and an accompanying tutorial are available in the supporting materials (https://doi.org/10.5281/zenodo.23965838).
ER  -

Abstract

Related

Cite