Expanding polynomials: A generalization of the Elekes-Rónyai theorem to $d$ variables

Abstract

We prove the following statement. Let $f\in \mathbb{R}[x_1,\dots ,x_d]$, for some $d\ge 3$, and assume that $f$ depends non-trivially in each of $x_1,\dots ,x_d$. Then one of the following holds. (i) For every finite sets $A_1,\dots ,A_d\subset \mathbb{R}$, each of size $n$, we have $$|f(A_1\times \dots \times A_d)|=\Omega (n^{3/2}),$$ with constant of proportionality that depends on $\mathrm{deg}f$. (ii) $f$ is of one of the forms \begin{align*} f(x_1,\ldots, x_d)&=h(p_1(x_1)+\cdots+p_d(x_d))~~\text{or}\\ f(x_1,\ldots, x_d)&=h(p_1(x_1)\cdot\ldots\cdot p_d(x_d)), \end{align*} for some univariate real polynomials $h(x)$, $p_1(x),\dots ,p_d(x)$. This generalizes the results from [ER00,RSS, RSdZ], which treat the cases $d=2$ and $d=3$.

19 pages