← Back to arXiv
arXivCombinatoricsarXiv:2608.26349

On polynomial expanders with many variables

The paper studies a question in combinatorial number theory: if you take a finite set of numbers and plug them into a polynomial with many variables, how many distinct output values can you get? This is the study of "polynomial expanders," so called because a good expander produces many more distinct outputs than inputs. If your set has, say, 100 numbers, a polynomial in several variables could in principle produce anywhere from 100 to 100-to-the-power-of-the-number-of-variables distinct outputs, and understanding which polynomials achieve near-maximum expansion is a central problem in the field.

The specific polynomial studied here takes n+2 variables and has a carefully designed structure involving products and powers of differences between variables. The main result shows that if you feed any finite set of complex numbers into all input slots, the number of distinct outputs grows like the size of the set raised to the nth power. Since the polynomial has n+2 inputs, this is nearly the best possible expansion rate, falling short of the theoretical maximum by only a factor of two powers of the set size. The result holds for any finite set of complex numbers and for any integer n of at least 2, making it a flexible and broadly applicable statement.

The significance of this result is that it provides an explicit, scalable family of polynomials that expand well in arbitrarily many variables. Much prior work on polynomial expanders focused on polynomials in just two or three variables, where clever algebraic and geometric tools are available. Handling many variables is considerably harder because the geometric intuition becomes murkier and combinatorial arguments become more intricate. Having an explicit construction that achieves near-optimal expansion in n+2 variables, with a single unified proof, is a meaningful advance in understanding how algebraic structure can force a large spread of outputs from a structured input set.

Read original →