← 研踪 PaperTrailarXiv:2611.02385 · v1
Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields
首次提交 2026-11-02 09:54
版本更新 2026-11-02 09:54
雷达观测 2026-11-04 23:42
摘要
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)=Ω_{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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-02 09:54 · 最新观测版本
Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields
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)=Ω_{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.
查看此版本解读 →查看此版本原文 ↗