Improved bound for the $k$-variate Elekes--Rónyai theorem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912690502369280 |
|---|---|
| author | Jahn, Yaara Raz, Orit E. |
| author_facet | Jahn, Yaara Raz, Orit E. |
| contents | Let $f\in \mathbb{R}[x_1,\ldots, x_k]$, for $k\ge 2$. For any finite sets $A_1,\ldots, A_k\subset \mathbb{R}$, consider the set $$ f(A_1,\ldots, A_k):=\{f(a_1,\ldots, 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,\ldots, 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 ${\rm rank}(f)$. Letting $r={\rm 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 $\varepsilon>0$, where the constant of proportionality depends on $\varepsilon$ and on ${\rm deg}(f)$. This improves the previous lower bound, for polynomials $f$ for which ${\rm 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_04233 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved bound for the $k$-variate Elekes--Rónyai theorem Jahn, Yaara Raz, Orit E. Combinatorics Let $f\in \mathbb{R}[x_1,\ldots, x_k]$, for $k\ge 2$. For any finite sets $A_1,\ldots, A_k\subset \mathbb{R}$, consider the set $$ f(A_1,\ldots, A_k):=\{f(a_1,\ldots, 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,\ldots, 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 ${\rm rank}(f)$. Letting $r={\rm 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 $\varepsilon>0$, where the constant of proportionality depends on $\varepsilon$ and on ${\rm deg}(f)$. This improves the previous lower bound, for polynomials $f$ for which ${\rm 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$. |
| title | Improved bound for the $k$-variate Elekes--Rónyai theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.04233 |