Summary
This paper shows that certain mathematical functions cannot be represented efficiently by multiplying simple cubic polynomials taken from prime number-based number systems. The authors prove that to exactly describe these functions, you need an exponentially large number of occurrences of variables in such polynomial products. Their results hold for fields related to prime numbers, including specific cases like three-element fields, and extend to more general prime fields. They also provide a method to extend these lower bounds to polynomials of higher degree. This helps explain the limitations of certain algebraic circuit designs.
What this means in practice
- •For circuit designers: Rule out certain low-degree polynomial multiplication circuits for exactly computing modular functions, guiding more efficient circuit design.
- •For cryptography engineers: Understand hardness of representing modular predicates, informing security assumptions based on polynomial computations over prime fields.
A theory result. No direct application yet.
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)=Ω_{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.