Improved bound for the $k$-variate Elekes--Rónyai theorem

Abstract

Let $f\in \mathbb{R}[x_1,\dots ,x_k]$, for $k\ge 2$. For any finite sets $A_1,\dots ,A_k\subset \mathbb{R}$, consider the set $$f(A_1,\dots ,A_k):=\{f(a_1,\dots ,a_k)\mid (a_1,\cdots ,a_k)\in A_1\times \cdots \times A_k\},$$ that is, the image of $A_1\times \cdots \times A_k$ under $f$. Extending a theorem of Elekes and Rónyai, which deals with the case $k=2$, and a result of Raz, Sharir, and De Zeeuw, dealing with the case $k=3$, it was proved Raz and Shem Tov, that for every choice of finite $A_1,\dots ,A_k\subset \mathbb{R}$, each of size $n$, one has \begin{equation}\label{RSbound} |f(A_1,\ldots,A_k)|=Ω(n^{3/2}), \end{equation} unless $f$ has some degenerate special form. In this paper, we introduce the notion of a {\it rank} of a $k$-variate polynomial $f$, denoted as $\mathrm{rank}(f)$. Letting $r=\mathrm{rank}(f)$, we prove that \begin{equation} |f(A_1,\ldots,A_k)|=Ω\left(n^{\frac{5r-4}{2r}-\varepsilon}\right), \end{equation} for every $\epsilon >0$, where the constant of proportionality depends on $\epsilon$ and on $\mathrm{deg}(f)$. This improves the previous lower bound, for polynomials $f$ for which $\mathrm{rank}(f)\ge 3$. We present an application of our main result, to lower bound the number of distinct $d$-volumes spanned by $(d+1)$-tuples of points lying on the moment curve in ${\mathbb{R}}^d$.