Semialgebraic methods and generalized sum-product phenomena

Semialgebraic methods and generalized sum-product phenomena, Discrete Analysis 2022:18, 23 pp.

The sum-product problem goes back to the following question of Erdős and Szemerédi from 1983. Suppose that $A$ is a finite set of integers. Let $A+A=\{a+a':\ a,a'\in A\}$ and $A\cdot A=\{aa':\ a,a'\in A\}$; these sets are referred to as the sumset and the product set of $A$. What can we say about the size of $A+A$ and $A\cdot A$ compared with the size of $A$? The sumset $A+A$ can have cardinality as small as $2|A|-1$ if $A$ is an arithmetic progression, and the same holds for the product set if $A$ is a geometric progression. However, arithmetic progressions and geometric progressions are very different, which led Erdős and Szemerédi to conjecture that it is not possible for both sets to be small simultaneously. More precisely, they conjectured that for every $\epsilon>0$ there exists a constant $c(\epsilon)>0$ such that for every finite set $A$ of integers, either $A+A$ or $A\cdot A$ has cardinality at least $c(\epsilon)|A|^{2-\epsilon}$.

This question remains open, but there are several partial results, due to various authors. There are also many extensions and generalizations to other settings; for example, a natural asymmetric variant concerns the size of $A+B$ and $A\cdot B$, where $A,B$ are two finite sets of integers.

The Elekes-Rónyai problem is the following related question. Let $f(x,y)$ be a polynomial in two variables. What can we say about the size of the set $f(A\times B)=\{f(a,b):\ a\in A,b\in B\}$? The expectation is that $f(A\times B)$ should be large as long as $f$ combines addition and multiplication in a nontrivial way. This can be quantified as follows: we will say that $f$ is expanding if there are constants $C, \epsilon>0$ such that for all sets $A,B\subset\mathbb R$ with $|A|=|B|=n$,

$$|f(A\times B)|\geq Cn^{1+\epsilon}.\qquad\qquad(1)$$
For example, the polynomials $f(x,y)=x+y$ and $f(x,y)=xy$ are not expanding, since the lower bound above fails for arithmetic and geometric progressions, respectively. However, more generic polynomials such as $x^2+xy+y^2$ or $x^2y+xy^2$ are expanding. This follows from results of Elekes-Rónyai and Raz-Sharir-Solymosi, who proved that a polynomial $f(x,y)$ must be expanding unless it has an explicit additive or multiplicative structure, in the sense that either $f(x,y)=g(\phi(x)+\psi(y))$ or $f(x,y)=g(\phi(x)\cdot \psi(y))$, where $g,\phi,\psi$ are single-variable polynomials.

The article by Jing, Roy, and Tran makes several contributions to this area of study. First, it was pointed out by de Zeeuw that a nonexpanding polynomial $f(x,y)$ (that is, one that has one of the above structures) might still satisfy (1) in the symmetric case $A=B$. The present paper provides a classification of all “symmetrically nonexpanding” polynomials, i.e., polynomials for which (1) fails when $A=B$. Second, the authors consider a variant concerning two polynomials $P$ and $Q$ are present. When do we have an estimate

$$\max\{|P(A\times B)|,|Q(A\times B)|\}\geq Cn^{1+\epsilon} \ (2)$$
for all sets $A,B$ with $|A|=|B|=n$? The original Erdős-Szemerédi problem provides the example $P(x,y)=x+y$ and $Q(x,y)=xy$, where (2) is expected to hold for any $\epsilon\in(0,1)$ (with $C$ depending on $\epsilon$). The authors classify all pairs of polynomials for which (2) fails with $\epsilon=1/4$, both in the symmetric case ($A=B$) and in the non-symmetric case ($A$, $B$ arbitrary subject to the cardinality condition). The proofs rely on methods from model theory and in particular the concept of definable sets, which have not been used previously in this context. It is likely that the approach here will find further applications.