Improved bound for the k k -variate Elekes–Rónyai theorem
Yaara Jahn, Orit E. Raz · 2025
Read Improved bound for the k k -variate Elekes–Rónyai theorem by Yaara Jahn, Orit E. Raz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04233.txt.
Introduction
Yaara Jahn and Orit E Raz improve the Elekes-Ronyai bound for how large the image of finite grid sets under a multivariate polynomial must be. The bound holds unless the polynomial has a special degenerate form. Earlier results handled two and three variables, and a general bound gave growth with exponent three halves for set size.
A new notion, the rank of the polynomial, sharpens the estimate. When rank is at least three, the image grows with a higher exponent that depends on rank, improving the prior bound for those polynomials. An application lower-bounds the number of distinct volumes spanned by point configurations. Expansion phenomena of this kind sit beneath many incidence geometry arguments.
Catalog record
| CREATOR | Yaara Jahn, Orit E. Raz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-04233
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved bound for the k k -variate Elekes–Rónyai theorem Yaara Jahn, Orit E. Raz Abstract Let f ∈ ℝ [ x 1 , … , x k ] f\in\mathbb{R}[x_{1},\ldots,x_{k}] , for k ≥ 2 k\geq 2 . For any finite sets A 1 , … , A k ⊂ ℝ A_{1},\ldots,A_{k}\subset\mathbb{R} , consider the set f ( A 1 , … , A k ) := { f ( a 1 , … , a k ) ∣ ( a 1 , ⋯ , a k ) ∈ A 1 × ⋯ × A k } , 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 × ⋯ × A k A_{1}\times\cdots\times A_{k} under f f . Extending a theorem of Elekes and Rónyai, which deals with the case k = 2 k=2 , and the result of Raz, Sharir, and De Zeeuw [ 7 ] , dealing with the case k = 3 k=3 , it is proved in Raz and Shem Tov [ 8 ] , that for every choice of finite A 1 , … , A k ⊂ ℝ A_{1},\ldots,A_{k}\subset\mathbb{R} , each of size n n , one has | f ( A 1 , … , A k ) | = Ω ( n 3 / 2 ) , |f(A_{1},\ldots,A_{k})|=\Omega(n^{3/2}), (1) unless f f has some degenerate special form. In this paper, we introduce the notion of a rank of a k k -variate polynomial f f , denoted as rank ( f ) {\rm rank}(f) . Letting r = rank ( f ) r={\rm rank}(f) , we prove that | f ( A 1 , … , A k ) | = Ω ( n 5 r − 4 2 r − ε ) , |f(A_{1},\ldots,A_{k})|=\Omega\left(n^{\frac{5r-4}{2r}-\varepsilon}\right), (2) for every ε > 0 \varepsilon>0 , where the constant of proportionality depends on ε \varepsilon and on deg ( f ) \deg(f) . This improves the lower bound ( 1 ), for polynomials f f for which rank ( f ) ≥ 3 {\rm rank}(f)\geq 3 . We present an application of our main result, to lower bound the number of distinct d d -volumes spanned by ( d + 1 ) (d+1) -tuples of points lying on the moment curve in ℝ d \mathbb{R}^{d} . 1 Introduction In many cases in combinatorial geometry, counting questions involving distances, slopes, collinearity, etc., can be reformulated as analogous counting questions involving grid points lying on certain algebraic varieties. A unified study of such problems began with a question of Elekes [ 2 ] about expansion of bivariate real polynomials f(x,y) . Specifically, he asked: For a bivariate polynomial f\in\mathbb{R}[x,y] and given finite sets A,B\subset\mathbb{R} , how small can be the image set f(A,B)=\{f(a,b)\mid a\in A,b\in B\}. Elekes conjectured that the image of f on a n\times n Cartesian product must be of cardinality superlinear in n , unless f has a very concrete special form . This was confirmed in 2000 by Elekes and Rónyai [ 3 ] who proved the following dichotomy: Either f has one of the forms \displaystyle f(x,y) \displaystyle=h(p(x)+q(y))\quad\text{or} \displaystyle f(x,y) \displaystyle=h(p(x)q(y)), (3) for some univariate real polynomials p,q,h , or, otherwise, for every finite A,B\subset\mathbb{R} , each of size n , we have |f(A,B)|=\omega(n). (4) In case f is not one of the forms in ( 3 ), the lower bound on |f(A,B)| was improved in [ 6 ] to be \Omega(n^{4/3}) , and further improved in [ 11 ] to be \Omega(n^{3/2}) , which is currently the best known lower bound for bivariate polynomials that are not special. An analogue of the Elekes–Rónyai problem can be formulated for polynomials in more than two variables. The trivariate case was studied by Raz, Sharir, and De Zeeuw [ 7 ] , and the general k -variate case was established by Raz and Shem Tov [ 8 ] . They obtain the following result. Theorem 1.1 ( [ 7 , 8 ] ). Let k\geq 3 and let f\in\mathbb{R}[x_{1},\ldots,x_{k}] . Then one of the following holds: (i) For every A_{1},\ldots,A_{k}\in\mathbb{R} each of size n one has f(A_{1},\ldots,A_{k})|=\Omega\left(n^{3/2}\right) (ii) f is of one of the forms: \displaystyle f(x_{1},\ldots,x_{k}) \displaystyle=h(p_{1}(x_{1})+\cdots+p_{k}(x_{k})) (5) \displaystyle f(x_{1},\ldots,x_{k}) \displaystyle=h(p_{1}(x_{1})\cdot\ldots\cdot p_{k}(x_{k})) Note that the bound in Theorem 1.1 , for non-special polynomials f , is independent of k , and in particular coincides with the bound for k=3 . At first glance this may appear to be merely a consequence of the proof. Indeed, the argument in [ 8 ] reduces the k -variate case for k\geq 4 to the trivariate case by fixing values for k-3 of the variables. They then show that if fixing any such subset of k-3 variables yields a special trivariate polynomial, then f itself, as a k -variate polynomial, must be special in the sense of ( 5 ). It is natural to expect that increasing the number of variables should force the image of f to grow faster. However, certain polynomials in many variables can in effect behave like polynomials in fewer variables. For example, consider the (k+2) -variate polynomial f(x,y,z_{1}\ldots,z_{k})=xy+z_{1}+z_{2}+\cdots+z_{k}. Let A,B,C_{1},\ldots,C_{k}\subset\mathbb{R} , where A,B are arbitrary finite sets of size n and C_{1}=\cdots=C_{k}=[n] . Let C:=C_{1}+\cdots+C_{k}=\{k,k+1,\ldots,kn\}. Then |C|=\Theta(n) , and letting g(x,y,z):=xy+z , we have f(A,B,C_{1},\ldots,C_{k})=g(A,B,C). In this case, with the current techniques, it is unclear how to obtain a bound on the expansion of f that improves upon the trivariate result for g . Our results. In this paper, we recognize k -variate polynomials that are, in a precise sense, truly k -variate, and we improve the corresponding expansion bounds for them. More precisely, for a k -variate polynomial f , we introduce the notion of the rank of f . If f has rank r , then, in a rigorous sense, it is essentially (r+1) -variate, and the bound on the size of its image can be improved with an exponent that grows with r . We now define the rank of a polynomial and then state our main result. Let f\in\mathbb{R}\left[x_{1},\ldots,x_{k}\right] and let d_{x_{1}} stand for the degree of f with respect to the variable x_{1} . Write f\left(x_{1},\ldots,x_{k}\right)=\sum\limits_{i=0}^{d_{x_{1}}}\alpha_{i}\left(x_{2},\ldots,x_{k}\right)x_{1}^{i}. We consider the coefficient map T=T_{f,x_{1}}:\mathbb{R}^{k-1}\to\mathbb{R}^{d_{x_{1}}+1} given by \left(x_{2},\ldots,x_{k}\right)\mapsto\left(\alpha_{0}\left(x_{2},\ldots,x_{k}\right),\ldots,\alpha_{d_{x_{1}}}\left(x_{2},\ldots,x_{k}\right)\right). We define the rank of f with respect to the variable x_{1} to be {\rm rank}_{x_{1}}(f):={\rm rank}(J_{T}), where J_{T} stands for the Jacobian matrix of T . Note that 0\leq{\rm rank}_{x_{1}}(f)\leq k-1. Similarly, define {\rm rank}_{x_{i}}(f) , for every i=2,\ldots,k , where x_{i} plays the role of x_{1} . Finally, define the rank of the polynomial f to be {\rm rank}(f):=\max_{1\leq i\leq k}{\rm rank}_{x_{i}}(f). Example 1.2 . Let f\left(x_{1},x_{2},\ldots,x_{k}\right)=x_{1}x_{k}+x_{2}x_{k}^{2}\dots+x_{k-1}x_{k}^{k-1}. Then \text{rank}(f)=\text{rank}_{x_{k}}(f)=k-1 . Example 1.3 . Let f(x_{1},x_{2},\ldots,x_{k})=p_{1}(x_{1})x_{k}+p_{2}(x_{1},x_{2})x_{k}^{2}+\dots+p_{k-1}(x_{1},\ldots,x_{k-1})x_{k}^{k-1}, where p_{i} is an i -variate polynomial that depends non-trivially on x_{i} . Then \text{rank}(f)=\text{rank}_{x_{k}}(f)=k-1 . Indeed, in this case the matrix J_{T_{f,x_{k}}} is upper-triangular. We prove the following main result of the paper. Theorem 1.4 . Let k\geq 3 and let f\in\mathbb{R}[x_{1}\ldots,x_{k}] . Assume that {\rm rank}(f)=r\geq 2 . Then, for every \varepsilon>0 , the following holds: Let A_{1},\ldots,A_{k}\subseteq\mathbb{R} be finite, each of size n . Then \lvert f(A_{1},\ldots,A_{k})\rvert=\Omega\left(n^{\frac{5r-4}{2r}-\varepsilon}\right), where the constant of proportionality depends on \deg(f) , on r , and on