Skip to content
Preprint

Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields

Nov 2026 · 0 citations
Computer Science

Abstract

We study exact representations of explicit signed modular predicates on $\{-1,1\}^n$ as products of bounded-degree polynomials over prime fields, measured by total variable-occurrence cost. Our main result is an exponential lower bound for products of cubic polynomials. Over $\mathbb F_3$ the proof is self-contained: every cubic factor in a nonvanishing product is a unit on the sign cube, the unit identity forces bounded affine-observation complexity, and a simultaneous clustering argument converts this structural compression into an exponential occurrence lower bound. We also give an alternative reconstruction route that isolates the quadratic structure behind the cubic classification. We then extend the cubic theorem to every fixed prime field $\mathbb F_p$ of characteristic greater than three for odd target modulus $q$ coprime to $p$. The only non-elementary structural input in this extension is Karam's restricted-range rank theorem; the conversion from multiplication to parity and the $p$-tuple clustering argument are proved explicitly. Finally, we establish a coefficient-field-independent degree-lifting principle. If a lower bound is known at one fixed degree, restriction to a large independent set yields a quantitative lower bound at the next degree. In particular, the exponential cubic theorem implies $ L^{(p,q)}_4(n)=\Omega_{p,q}\!\left(\frac{n^4}{(\log(2+n))^3}\right). $ For the characteristic-three core this already gives a lower bound for a restricted mixed-modulus circuit class.

View source

Similar papers

Preprint Sep 2026

A Degree--Size Relation for Resolution over Polynomials

For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime field. Applications include exponential lower bounds for CNFs in $\operatorname{Res}(\operatorname{PC}_r/\mathbb{F}_p)$ and hence in $\operato...

Shuo Pang · 1 citation · ⚡1
Review Nov 2026

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

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, i...

Søren Riis · 0 citations
Preprint Nov 2026

The existence of small defining polynomials for number fields, II

We prove that every number field of odd degree $n\geq 3$ and absolute discriminant $D$ has an integral defining polynomial whose coefficients are $O_n(D^{(n-1)/(2n-1)})$ in size. This strengthens, in odd-degree cases, the recently established bound of $O_n(D^{1/2})$ for all degrees $n$, which was conjectured in 1998 by...

M. Bhargava, Sameera Vemulapalli · 0 citations
Preprint Oct 2026

A Quadratic Bound for Automorphism Groups of Curves of Positive $p$-Rank in Odd Characteristic

Let $X$ be a nonsingular projective curve of genus $g\ge2$ over an algebraically closed field of odd characteristic $p$. Giulietti and Korchm\'aros established a quadratic genus bound with constant $900$ forcing zero $p$-rank for curves of even genus. We extend this bound to odd genus: for every $g\ge2$, positive $p$-r...

Saeed Tafazolian · 0 citations
Preprint Oct 2026

A polynomial method over formal power series

We give new upper bounds on families of integer vectors with prescribed coordinate multiplicities and a forbidden scalar product. Our method uses coefficient functions over formal power series and recovers the Frankl--Wilson bound for binary vectors. For vectors in $\{-1,0,1\}^n$, we obtain an exponential improvement o...

A. Akhiiarov, Mikhail S. Koshelev, A. Kupavskii et al. · 0 citations
Preprint Nov 2026

Multivariate Pellarin $L$-values on algebraic curves

We establish a generating trace formula for multicharacter ideal-type $L$-values associated with rank-one Drinfeld modules. For a sign-normalized Hayes module with free period lattice, the formula realizes the $L$-values at weights $n\equiv s\pmod{q^{\deg_\infty}-1}$ as a trace over the ordinary Hilbert class field. We...

Chuang-Qiang Hu, S. Yau, Li-Shan Yu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.