Split primes and the Elekes-R\'onyai problem — Plain-Language Explanation

The Big Question: Can You Hide the Chaos?

Imagine you have a giant machine (a mathematical formula) that takes two numbers, $x$ and $y$ , and spits out a new number. Let's call this machine $f$ .

Now, imagine you have a big bag of numbers, let's call it Set A. You take every possible pair of numbers from this bag, feed them into the machine, and collect all the results. This collection of results is called the Image Set.

The Puzzle:
Mathematicians have long wondered: If you pick a "complicated" machine (one that isn't just adding or multiplying numbers in a simple way), can you ever arrange your bag of numbers so that the machine produces very few unique results?

The "Easy" Machines: If your machine is just adding ( $x+y$ ) or multiplying ( $x \times y$ ), you can easily trick it. If you put in an arithmetic progression (like 1, 2, 3, 4), the sums stay small and predictable. If you put in a geometric progression (like 2, 4, 8, 16), the products stay small. In these cases, the number of unique results grows slowly (linearly) as you add more numbers to your bag.
The "Hard" Machines: The famous Elekes-Rónyai problem asked: What if the machine is not simple? What if it's a mix, like $x + y + (x-y)^2$ ? The prevailing belief (a conjecture by Elekes) was that for these "hard" machines, no matter how cleverly you pick your numbers, the number of unique results will explode. It should grow almost as fast as the square of your bag size (if you have $N$ numbers, you should get roughly $N^2$ unique results).

The Breakthrough: The "Magic Sieve"

In this paper, the author, Cosmin Pohoata, says: "Actually, you can trick the hard machine."

He proves that there exists a specific "hard" machine ( $f(x, y) = x + y + (x-y)^2$ ) and a way to pick numbers such that the number of unique results is much smaller than expected. It's not just a little smaller; it's significantly smaller, breaking the rule that everyone thought was unbreakable.

How Did He Do It? (The Analogy)

To understand the trick, imagine you are trying to hide a specific set of keys in a massive, multi-story building.

The Building (The Number System): Instead of looking at normal numbers, the author builds a special, high-dimensional "number world" (a mathematical structure called a number field). Think of this as a building with thousands of floors.
The Locks (The Primes): He chooses a special set of "locks" (prime numbers) that have a very specific property: they split perfectly into many independent rooms on every floor of the building.
The Trap (The Residue Classes): The author designs his machine so that no matter what numbers you put in, the output must land in a very specific, tiny corner of the building.
- Imagine that on every floor, the machine is forced to only land on "even-numbered rooms" or "rooms with red doors."
- Because the machine has to satisfy this rule on every single floor simultaneously, the number of possible places it can end up becomes incredibly small.
The Result: Even though the building is huge (representing a large set of numbers), the "allowed" rooms are so few that the machine produces very few unique outcomes.

The "Split Prime" Secret Sauce

The secret ingredient is something called Split Primes.

In normal math, a prime number might act like a single, solid wall.
In this author's special number world, these primes "split" like a tree branching out. One prime becomes many independent "residue fields" (like many small, separate rooms).
The author uses a tower of these number worlds, getting taller and taller (higher dimensions).
In each small room, the machine is forced to produce a "square" number (like 0, 1, 4, 9). Since squares are rare compared to all numbers, this restricts the output.
Because the primes split into many rooms, this restriction happens over and over again. The restrictions multiply, creating a "bottleneck" that squeezes the number of unique results down dramatically.

The "Small Doubling" Bonus

The paper also shows something even cooler. Not only does the machine produce few results, but the numbers in the bag also have a special property: if you add any two numbers from the bag together, you don't get too many new numbers.

Analogy: Imagine a group of people where if you pair them up to form new teams, the number of unique teams formed is still relatively small. This makes the "bag of numbers" very structured and efficient, which helps the trick work even better.

The Conclusion

The author successfully built a counterexample. He showed that for the specific formula $x + y + (x-y)^2$ , you can find huge sets of numbers where the number of unique outputs is roughly $N^{2-c}$ (where $c$ is a small positive number).

This means the output is sub-quadratic. It grows slower than the square of the input size. This disproves the long-standing conjecture that "hard" formulas must produce nearly $N^2$ unique results.

In short: The author found a mathematical "loophole" using a complex, high-dimensional number system and special prime numbers to force a complicated formula to behave like a simple one, keeping the number of unique results surprisingly low.

Technical Summary: Split Primes and the Elekes-Rónyai Problem

Problem Statement
The paper addresses the Elekes–Rónyai problem, a central question in arithmetic combinatorics and incidence geometry. The problem investigates the expansion properties of bivariate polynomials $f \in \mathbb{R}[x, y]$ over finite sets $A, B \subset \mathbb{R}$ . Specifically, it asks for the minimum possible size of the image set $f(A, B) = \{f(a, b) : a \in A, b \in B\}$ when $|A| = |B| = n$ .

It is established that if $f$ is "special"—meaning it is either additive ( $f(x, y) = g(u(x) + v(y))$ ) or multiplicative ( $f(x, y) = g(u(x)v(y))$ )—the image size can be linear in $n$ (e.g., by choosing $A$ and $B$ as arithmetic or geometric progressions). For "non-special" polynomials, Elekes and Rónyai (2000) proved qualitatively that the image size must be superlinear ( $|f(A, B)|/n \to \infty$ ). A prominent conjecture by Elekes posits a quantitative bound: for every non-special polynomial and every $\epsilon > 0$ , there exists a constant $C_{f, \epsilon}$ such that $|f(A, B)| \ge C_{f, \epsilon} n^{2-\epsilon}$ .

Methodology and Construction
The paper constructs a counterexample to Elekes' conjecture using a combination of algebraic number theory, lattice geometry, and a novel application of a "local-to-global" sieve principle.

The Polynomial: The author focuses on the specific non-special polynomial $f(x, y) = x + y + (x - y)^2$ .
Algebraic Number Theory Input: The construction relies on a tower of totally real number fields $K_i$ with degrees $d_i \to \infty$ and bounded root discriminants (based on results by Hajir, Maire, and Ramakrishna). Crucially, there exists an infinite set of rational primes $P$ that split completely in every field of this tower.
Local Residue Restriction: The author defines an auxiliary polynomial $f_Q(x, y) = Q(x + y) + (x - y)^2$ , where $Q$ is a product of distinct primes from $P$ . Modulo any prime ideal $\mathfrak{p}$ dividing $Q$ , the term $Q(x+y)$ vanishes, forcing $f_Q(x, y) \equiv (x-y)^2 \pmod{\mathfrak{p}}$ . Consequently, the image of $f_Q$ in the residue field $\mathbb{F}_p$ is restricted to the set of quadratic residues (squares), which has density roughly $1/2$ .
Global Construction via Lattices:
- The author selects a field $K$ of degree $d$ from the tower and considers a symmetric Minkowski box $B_K(X)$ in the ring of integers $\mathcal{O}_K$ .
- By the Chinese Remainder Theorem, the restriction to quadratic residues modulo each prime factor of $Q$ compounds across the $d$ independent residue fields generated by the splitting primes. This forces the image of $f_Q$ to lie in a set of residue classes with density $\rho^d$ , where $\rho < 1$ .
- Using geometry-of-numbers estimates (Blichfeldt's lemma and packing arguments), the author shows that the number of integer points in the Minkowski box grows exponentially with $d$ (specifically $\sim X^d$ ), while the number of allowed residue classes grows as $(\rho Q)^d$ .
- Because $\rho < 1$ , the "congruence saving" factor $\rho^d$ dominates the growth of the set size, resulting in a polynomial image size that is a fixed power less than 2.

Key Results
The paper establishes the following main theorem:

Theorem 1.1: There exist arbitrarily large finite sets $A \subset \mathbb{R}$ and an absolute constant $c > 0$ such that for $f(x, y) = x + y + (x - y)^2$ :
$|f(A, A)| \le |A|^{2-c}$
Furthermore, for any fixed $\epsilon > 0$ , the sets can be chosen such that the additive doubling is small ( $|A+A| \le |A|^{1+\epsilon}$ ) while maintaining the image bound $|f(A, A)| \le |A|^{2-c_\epsilon}$ .
Non-Special Verification: The paper rigorously proves that $f(x, y) = x + y + (x - y)^2$ is neither additive nor multiplicative over $\mathbb{C}$ , confirming it is a valid candidate for the Elekes–Rónyai problem.

Significance and Claims
The paper claims to disprove the Elekes conjecture regarding the near-quadratic lower bound for non-special polynomials. By demonstrating that a specific non-special polynomial can have an image size of $O(n^{2-c})$ (where $c > 0$ is a constant), the author shows that the conjectured bound of $n^{2-\epsilon}$ is false.

The construction is described as an inversion of a "combinatorial large sieve" method. While typical sieve methods use local branching to prove that sets with bounded multiplicity must be small, this work uses local branching (splitting primes) to force values into a small collection of local residue classes, thereby constructing a large set with a small image.

The paper notes that the construction was first announced in a blog post in June 2026 and relies on recent breakthroughs in the Erdős unit-distance problem and the sum-product conjecture, specifically utilizing high-dimensional symmetric Minkowski boxes and bounded root-discriminant towers. The work provides a formal proof and detailed context for these counterexamples.

Split primes and the Elekes-Rónyai problem