A symmetric multivariate Elekes-Rónyai theorem

This paper establishes a symmetric multivariate Elekes-Rónyai theorem providing a lower bound on the size of the image of a polynomial over finite sets unless the polynomial exhibits specific additive or multiplicative degeneracies, while also proving a generalized Erdős-Szemerédi theorem for two polynomials in higher dimensions.

The Gist

Imagine you have a giant, magical blender. You put in a bunch of numbers from a specific list (let's call this list A). You mix them together using a complex recipe (a mathematical formula called a Polynomial).

The big question mathematicians have been asking for decades is: How many different smoothies can you make?

If you take 100 numbers and mix them in a simple way, you might only get 100 different results. But if you mix them in a "chaotic" or "complex" way, you might get thousands of unique results. The paper by Yewen Sun is about proving exactly how many unique results you are guaranteed to get, and figuring out the specific "recipes" that fail to create variety.

Here is the breakdown of the paper's discoveries using simple analogies:

1. The Basic Rule: Chaos vs. Order

In the world of math, there's a famous rule (the Elekes–Rónyai Theorem) that says:

"If your recipe is complicated enough, mixing a list of $n$ numbers will produce at least $n^{1.5}$ (roughly $n$ times the square root of $n$) unique results."

Think of it like shuffling a deck of cards. If you just stack them in order, you have 1 arrangement. If you shuffle them randomly, you have billions. The theorem says: "Unless your recipe is a boring, predictable trick, you will get a huge explosion of variety."

The Catch: The old rule had a loophole. It only worked if you mixed different lists of numbers (List A with List B). But what if you mix List A with itself? (Like taking the same deck of cards and shuffling it against itself). The old rule sometimes failed to predict the explosion of variety in this "symmetric" case.

2. The New Discovery: The Symmetric Explosion

Yewen Sun's paper fixes this. It proves that even when you mix a list with itself (Symmetric Case), you still get a massive explosion of variety—unless the recipe is a very specific type of "cheat."

The "Cheat" Recipes:
The paper identifies two types of boring recipes that don't create variety:

1. The Additive Cheat: The recipe is just a sum of parts, like $f(x + y + z)$. If the parts $x, y, z$ are all "proportional" to each other (like $x$, $2x$, and$3x$), the blender just spits out a predictable stream.
2. The Multiplicative Cheat: The recipe is a product, like $f(x \cdot y \cdot z)$. If the parts are powers of each other (like $x$, $x^2$, $x^3$), it's also predictable.

The Big Result:
Sun proves that if your recipe is NOT one of these two specific cheats, then mixing your list with itself will create a huge number of unique outcomes. The more variables you have (more ingredients in the blender), the more variety you get, up to a certain limit.

3. The "Tolerance" for Cheating

Here is where it gets really cool. Sun introduces a concept called $t$.

Imagine you have a recipe with 10 ingredients ($x_1$ to $x_{10}$).

• If the recipe is a "cheat" for all 10 ingredients, you get low variety.
• But what if the recipe is a cheat for only 8 of them, and the other 2 are wild and chaotic?

Sun's theorem says: As long as you have enough "wild" ingredients, the variety explodes.
He calculates a specific "safety zone." If you have a certain number of ingredients that are not proportional to each other, the number of unique results will be huge. The more "wild" ingredients you have, the bigger the explosion.

4. The "Two-Recipe" Test (The Erdős–Szemerédi Connection)

The paper also tackles a second problem: What if you have two different recipes (Recipe P and Recipe Q)?

• Maybe Recipe P is a "cheat" (low variety).
• Maybe Recipe Q is a "cheat" (low variety).

The paper proves that they cannot both be cheats at the same time unless they are "twins" (mathematically related in a very specific way).

• Analogy: Imagine you have two different ways to bake a cake. If both ways result in a boring, flat cake, they must be using the exact same ingredients in the exact same proportions. If they are different enough, at least one of them will produce a fluffy, unique cake.

5. How They Proved It: The "Curve" Detective

To prove this, the author used a tool from Geometry (specifically, counting how lines and curves intersect).

• The Metaphor: Imagine plotting your recipe on a graph. If the recipe is a "cheat," the points on the graph form a straight line or a simple curve. If it's a "wild" recipe, the points scatter everywhere.
• The author used a "magnifying glass" (a theorem by Elekes, Nathanson, and Ruzsa) to look at these curves. They proved that if the curve isn't a straight line, it can't overlap with a shifted version of itself very many times.
• The Result: Because the curves don't overlap much, the "blender" (the polynomial) must be creating new, unique numbers every time.

Summary in One Sentence

Yewen Sun proved that if you mix a list of numbers with itself using a complex formula, you will get a massive explosion of unique results, unless the formula is a very specific, predictable trick involving sums or products of proportional parts.

This is a major step forward in understanding how numbers interact, helping mathematicians predict when chaos (variety) is inevitable and when order (predictability) is possible.

Technical Summary

Here is a detailed technical summary of the paper "A Symmetric Multivariate Elekes–Rónyai Theorem" by Yewen Sun.

1. Problem Statement and Context

The Elekes–Rónyai Theorem:
The classical Elekes–Rónyai theorem (2000) addresses the expansion of the image of a polynomial $f(x, y)$ over finite sets $A, B \subset \mathbb{R}$. It states that if $f$ is not of a specific "degenerate" form (essentially $f(x,y) = h(g(x)+k(y))$ or $f(x,y) = h(g(x)k(y))$), then $|f(A, B)| \gg n^{1+\epsilon}$. Recent improvements have pushed the exponent $\epsilon$ up to $1/2$ (Solymosi–Zahl, 2024).

The Symmetric Case ($A=B$):
A significant open problem was the "symmetric" case where $A=B$. In this setting, standard degenerate forms like $f(x,y) = x + y^2$ (which fits the additive form $h(g(x)+k(y))$) do not necessarily yield superlinear expansion under the standard theorem, yet they often exhibit expansion in the symmetric case. Jing, Roy, and Tran (2022) resolved the 2D symmetric case, proving $|f(A, A)| \gg n^{5/4}$ unless $f$ has a specific structure where the univariate components are equivalent under scaling (additive) or power relations (multiplicative).

The Multivariate Challenge:
The paper aims to generalize the symmetric result to $d$ variables ($d \ge 2$) and to a "generalized Erdős–Szemerédi" setting involving two polynomials. The core question is: Given a polynomial $P(x_1, \dots, x_d)$ and a finite set $A \subset \mathbb{R}$, what is the lower bound for $|P(A, \dots, A)|$?

2. Methodology

The author employs a novel strategy combining incidence geometry, algebraic geometry, and combinatorial induction.

A. Key Technical Tool: Variations of the Elekes–Nathanson–Ruzsa Theorem

The proof relies heavily on a generalization of a result by Elekes, Nathanson, and Ruzsa (2000). The author proves Theorem 1.3, which establishes a lower bound for the size of the sumset $|S + T|$ where $S$ is a curve parametrized by polynomials (possibly involving logarithms).

• The Setup: Let $S = \{(f(p(a)), g(q(a))) : a \in A\}$ where $f, g$ are either the identity or $\log|\cdot|$.
• The Condition: If the curve $C = \{(f(p(t)), g(q(t)))\}$ is not contained in an affine line, then:
  $$|S + T| \gg \min\{|A||T|, |A|^{3/2}|T|^{1/2}\}$$
• Algebraic Geometry: To prove this, the author analyzes the intersection of the curve $C$ with its translates $C+a$. Using the resultant and Bézout's theorem, they show that if $C$ is not a line (or a specific logarithmic line), the intersection $|(C+a) \cap C|$ is bounded by $O(\delta^2)$. This allows the application of the Szemerédi–Trotter theorem for curves to bound incidences.

B. Inductive Structure

The main theorems are proved by induction on the dimension $d$ and the parameter $t$ (which measures the "mismatch" between polynomials).

• Base Case ($d=2$): The author provides a new proof of the Jing–Roy–Tran (2022) result using the new Theorem 1.3.
• Inductive Step: The proof reduces the $d$-dimensional problem to a $(d-1)$-dimensional problem by isolating one variable and applying the 2D result (Theorem 1.3) to the remaining structure.

C. Combinatorial Lemma on Permutations

A crucial combinatorial lemma (Lemma 5.2) is introduced to handle the symmetry. It states that if for every permutation $\sigma$ of $[d]$, there exists a large subset of indices where the polynomial components are equivalent under $\sigma$, then there must exist a large equivalence class of indices where the components are mutually equivalent. This allows the author to deduce the structural form of the polynomial from the failure of expansion.

3. Key Contributions and Results

Result 1: Symmetric Multivariate Elekes–Rónyai Theorem (Theorem 1.1)

Let $P \in \mathbb{R}[x_1, \dots, x_d]$ be a polynomial of degree $\delta$ depending non-trivially on all variables. For a finite set $A$ of size $n$:
$$|P(A, \dots, A)| \gg_{\delta} n^{\frac{3}{2} - \frac{1}{2t+1}}$$
Unless $P$ takes one of two specific forms:

1. Additive: $P = f(u_1(x_1) + \dots + u_d(x_d))$
2. Multiplicative: $P = f(u_1(x_1) \cdots u_d(x_d))$

In these exceptional cases, there must exist a large index subset $I \subseteq [d]$ with $|I| = d - \lfloor \frac{t-1}{2} \rfloor$ such that for all $i, j \in I$:

• Additive: $u_i \equiv_a u_j$ (i.e., $u_i = \lambda u_j$).
• Multiplicative: $u_i \equiv_m u_j$ (i.e., $|u_i| = |u_j|^\kappa$).

Significance: This generalizes the 2D result of Jing–Roy–Tran to arbitrary dimensions. The exponent improves as $t$ increases (requiring more "mismatched" components), approaching $n^{3/2}$ for large $t$.

Result 2: Generalized Erdős–Szemerédi Theorem (Theorem 1.2)

For two polynomials $P, Q \in \mathbb{R}[x_1, \dots, x_d]$:
$$\max\{|P(A, \dots, A)|, |Q(A, \dots, A)|\} \gg_{\delta} n^{\frac{3}{2} - \frac{1}{2t+1}}$$
Unless $P$ and $Q$ form a $t$-additive pair or a $t$-multiplicative pair.

• A $t$-additive pair means $P = f(\sum u_i)$ and $Q = g(\sum v_i)$, and the number of indices where $u_i \not\equiv_a v_i$ is less than $t$.
• This unifies the expansion of sums and products in higher dimensions, generalizing the classical Erdős–Szemerédi conjecture.

4. Significance and Impact

1. Resolution of Symmetric Multivariate Cases: The paper successfully extends the symmetric Elekes–Rónyai theorem from 2D to $d$-dimensions, a long-standing gap in the field.
2. New Proof Technique: By introducing a variation of the Elekes–Nathanson–Ruzsa theorem involving logarithmic curves, the author provides a flexible tool that handles both additive and multiplicative structures simultaneously. This approach is more robust than previous methods for the symmetric case.
3. Quantitative Improvements: The paper provides explicit exponents ($3/2 - 1/(2t+1)$) that depend on the structural complexity of the polynomials, offering a finer classification of when expansion occurs.
4. Foundational for Future Work: The combinatorial lemma regarding permutations and equivalence classes (Lemma 5.2) may have applications in other areas of additive combinatorics involving symmetric structures.

In summary, Yewen Sun's paper establishes a powerful framework for understanding the expansion of symmetric multivariate polynomials, bridging the gap between the classical Elekes–Rónyai theorem and the symmetric Erdős–Szemerédi problem in high dimensions.