2026-09-05T11:58:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25866 2026-06-23T12:59:53Z ddc:004 open_access

Improved Bound for the k-Variate Elekes-Rónyai Theorem Jahn, Yaara Raz, Orit E. Polynomial Expansion Elekes-Rónyai theorem Let f ∈ ℝ[x₁,…,x_k], for k ≥ 2. For any finite sets A₁,…,A_k ⊂ ℝ, consider the set f(A₁,…,A_k): = {f(a₁,…,a_k)∣ (a₁,⋯,a_k) ∈ A₁×⋯× A_k}, that is, the image of A₁×⋯×A_k under f. Extending a theorem of Elekes and Rónyai, which deals with the case k = 2, and the result of Raz, Sharir, and De Zeeuw [Raz et al., 2018], dealing with the case k = 3, it is proved in Raz and Shem Tov [Raz and Shem{-}Tov, 2020], that for every choice of finite A₁,…, A_k ⊂ ℝ, each of size n, one has (1) |f(A₁,…,A_k)| = Ω(n^{3/2}), unless f has some degenerate special form. In this paper, we introduce the notion of a rank of a k-variate polynomial f, denoted as rank(f). Letting r = rank(f), we prove that (2) |f(A₁,…,A_k)| = Ω(n^{(5r-4)/2r-ε}) , for every ε > 0, where the constant of proportionality depends on ε and on deg(f). This improves the lower bound (1), for polynomials f for which rank(f) ≥ 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 ℝ^d. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yaara Jahn and Orit E. Raz 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.59 urn:nbn:de:0030-drops-258663 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.59 eng https://creativecommons.org/licenses/by/4.0/legalcode