Improved Bound for the k-Variate Elekes-Rónyai Theorem

Jahn, Yaara; Raz, Orit E.

doi:10.4230/LIPIcs.SoCG.2026.59

Improved Bound for the $𝒌$ -Variate Elekes–Rónyai Theorem

Yaara Jahn

Hebrew University of Jerusalem, Israel Orit E. Raz

Ben-Gurion University, Be’er-Sheva, Israel

Abstract

Let $f\in\mathbb{R}[x_{1},\ldots,x_{k}]$ , for $k\geq 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 the result of Raz, Sharir, and De Zeeuw [9], dealing with the case $k=3$ , it is proved in Raz and Shem Tov [10], that for every choice of finite $A_{1},\ldots,A_{k}\subset\mathbb{R}$ , each of size $n$ , one has

|f(A_{1},\ldots,A_{k})|=\Omega(n^{3/2}),

(1)

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 ${\rm rank}(f)$ . Letting $r={\rm rank}(f)$ , we prove that

|f(A_{1},\ldots,A_{k})|=\Omega\left(n^{\frac{5r-4}{2r}-\varepsilon}\right),

(2)

for every $\varepsilon>0$ , where the constant of proportionality depends on $\varepsilon$ and on $\deg(f)$ . This improves the lower bound (1), for polynomials $f$ for which ${\rm rank}(f)\geq 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}$ .

Keywords and phrases:

Polynomial Expansion, Elekes–Rónyai theorem

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Combinatoric problems

DOI:

10.4230/LIPIcs.SoCG.2026.59

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

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 [3] 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 [4] 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 [8] to be $\Omega(n^{4/3})$ , and further improved in [13] 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 [9], and the general $k$ -variate case was established by Raz and Shem Tov [10]. They obtain the following result.

Theorem 1 ([9, 10]).

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, 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 [10] 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$ ; here we consider the rank over the field of rational functions in $x_{2},\dots,x_{k}$ over $\mathbb{R}$ , which is equivalent to evaluating the rank at a generic point $(x_{2},\dots,x_{k})\in\mathbb{R}^{k-1}$ . 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 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 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.

Example 4.

Let $f(x_{1},\dots,x_{k})=p_{1}(x_{1})+p_{2}(x_{2})+\dots+p_{k}(x_{k})$ . The coefficient map $T_{f,x_{1}}$ maps $(x_{2},\dots,x_{k})$ to the coefficients of $p_{1}(x_{1})$ , which consist only of a single term depending on the other variables. The Jacobian matrix consists almost entirely of zeros, yielding $\text{rank}(f)=1$ . This aligns perfectly with the special degenerate forms described in Theorem 1.

We prove the following main result of the paper.

Theorem 5.

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 $\varepsilon$ .

Observe that for a generic $k$ -variate polynomial, the rank is maximal, meaning $r=k-1$ . In this case, Theorem 5 yields a lower bound of $\Omega(n^{\frac{5k-9}{2k-2}-\epsilon})$ . Notably, this relates to Conjecture 1.3 of de Zeeuw [2], which posits that a generic bivariate polynomial has at least $\Omega(n^{2-\epsilon})$ distinct values. Our theorem pushes towards this super-quadratic growth and currently provides the best known lower bound for the minimal number of distinct values taken by generic $k$ -variate polynomials for $k\geq 4$ .

We observe that ${\rm rank}(f)=1$ corresponds to the special forms from Theorem 1. Indeed, we have the following theorem.

Theorem 6.

Let $k\geq 3$ and let $f\in\mathbb{R}\left[x_{1}\ldots,x_{k}\right]$ . Assume that $f$ depends non-trivially on each of its variables and that

{\rm rank}(f)=1.

Then $f$ has one of the forms

	$\displaystyle f\left(x_{1},\ldots,x_{k}\right)$	$\displaystyle=h\left(p_{1}\left(x_{1}\right)+\cdots+p_{k}\left(x_{k}\right)% \right)\ \ \text{ or}$
	$\displaystyle f\left(x_{1},\ldots,x_{k}\right)$	$\displaystyle=h\left(p_{1}\left(x_{1}\right)\cdot\ldots\cdot p_{k}\left(x_{k}% \right)\right),$		(6)

for some univariate real polynomials $h(x),p_{1}(x),\ldots,p_{k}(x)$ .

Finally, we present an application of our results to the following Erdős-type combinatorial geometric problem. Let $\nu$ denote the moment curve in $\mathbb{R}^{d}$ , parameterized by

\nu(t)=(t,t^{2},\ldots,t^{d}),\quad t\in\mathbb{R}.

Let $P\subset\nu$ be a finite set of $n$ points. For any distinct $p_{1},\ldots,p_{d+1}\in\nu$ , let $\sigma=\sigma(p_{1},\ldots,p_{d+1})$ denote the $d$ -simplex which is the convex hull of $p_{1},\ldots,p_{d+1}$ in $\mathbb{R}^{d}$ , and let ${\rm vol}(\sigma)$ denote its $d$ -dimensional volume. Define

\Delta(P)=\left\{{\rm vol}(\sigma(p_{1},\ldots,p_{d+1}))\mid p_{1},\ldots,p_{d% +1}\in P\right\}.

We have the following theorem.

Theorem 7.

Let $\nu$ be the moment curve in $\mathbb{R}^{d}$ and let $P\subset\nu$ be any finite set of size $n$ . Then, for every $\varepsilon>0$ ,

|\Delta(P)|=\Omega\left(n^{\frac{5d-4}{2d}-\varepsilon}\right),

where the implicit constant depends only on $\varepsilon$ and on $d$ .

Theorem 7 is obtained by identifying a $(d+1)$ -variate polynomial $f$ whose expansion over a certain $n\times\cdots\times n$ grid in $\mathbb{R}^{d+1}$ corresponds to the number of distinct volumes of $d$ -simplices spanned by $P$ . We then show that $f$ has rank $d$ and apply our main Theorem 5.

Organization of the paper

The paper is organized as follows. In Section 2 we recall an incidence bound that will serve as a key tool in our arguments. In Section 3, we establish a special case of our main result, Theorem 5, and in Section 4, we complete its proof. The proof of Theorem 6 is provided in Section 5. Finally, Section 6 contains the proof of Theorem 7.

2 Incidences between points and algebraic curves

For a finite set of points ${\cal P}\subset\mathbb{R}^{2}$ and a finite set of planar curves ${\cal C}$ , we let $I({\cal P},{\cal C})$ denote the set of point-curve incidences; that is

I({\cal P},{\cal C})=\{(p,\gamma)\in{\cal P}\times{\cal C}\mid p\in\gamma\}.

The classical Szemerédi–Trotter theorem [14] asserts that, for the special case where ${\cal C}$ is a set of lines, and putting $m:=|{\cal P}|$ and $n:=|{\cal C}|$ , one has

\left|I({\cal P},{\cal C})\right|=O\left(m^{2/3}n^{2/3}+m+n\right).

Since the Szemerédi–Trotter result, many alternative proofs and analogue problems have been studied. Today incidence problems play a fundamental role in combinatorial geometry. For our result we will need an extension of the Szemerédi–Trotter theorem to point-curve incidence problems, where the curves are algebraic and come from an $s$ -dimensional family of curves. We now present the definition from Sharir–Zahl [12].

A bivariate polynomial $h\in\mathbb{R}[x,y]$ of degree at most $D$ is a linear combination of the form

h(x,y)=\sum_{0\leq i+j\leq D}c_{ij}x^{i}y^{j}.

Note that the number of monomials $x^{i}y^{j}$ such that $0\leq i+j\leq D$ is $\binom{D+2}{2}$ . In this sense, every point $\vec{c}\in\mathbb{R}^{\binom{D+2}{2}}$ (other than the all-zero vector) can be associated with a curve in $\mathbb{R}^{2}$ , given by the zeroset of the bivariate polynomial whose coefficients are the entries of $\vec{c}$ . If $\lambda\neq 0$ , then $f$ and $\lambda f$ have the same zero-set. Thus, the set of algebraic curves that can be defined by a polynomial of degree at most $D$ in $\mathbb{R}^{2}$ can be identified with the points in the projective space ${\bf P}\mathbb{R}^{\binom{D+2}{2}}$ .

In [12], Sharir and Zahl defined an $s$ -dimensional family of plane curves of degree at most $D$ to be an algebraic variety $F\subset{\bf P}\mathbf{\mathbb{}}{R}^{\binom{D+2}{2}}$ such that $\dim(F)=s$ . We will call the degree of the variety $F$ the complexity of the family.

They then proved the following incidence bound:

Theorem 8 (Sharir–Zahl [12]).

Let $\cal{F}$ be an $s$ -dimensional family of plane curves of degree at most $D$ and complexity at most $K$ . Let $\mathcal{P}$ be a set of $m$ points in the plane and let ${\cal C}\subset{\cal F}$ be a set of $n$ plane curves. Suppose that no two of the curves in ${\cal C}$ share a common irreducible component. Then for every $\varepsilon>0$ , we have

I\left(\mathcal{P},\mathcal{C}\right)=O_{\varepsilon}\left(m^{\frac{2s}{5s-4}}% n^{\frac{5s-6}{5s-4}+\varepsilon}\right)+O\left(m^{2/3}n^{2/3}+m+n\right),

where the constant of proportionality depends on $s, K, D$ and in the first term also on $\varepsilon$ .

3 A special case

In this section we prove the special case of Theorem 5 with $r=k-1$ . This will serve as a key ingredient for the proof of the general result.

Proposition 9.

Let $k\geq 3$ , $f\in\mathbb{R}\left[x_{1}\ldots,x_{k}\right]$ , and assume that ${\rm{rank}}(f)=k-1$ . 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{5(k-1)-4}{2(k-1)}-% \varepsilon}\right),

where the constant of proportionality depends on $\deg(f)$ , on $k$ , and on $\varepsilon$ .

Proof.

Let $f,A_{1},\ldots,A_{k}$ be as in the statement. Up to renaming of the variables, we may assume without loss of generality that ${\rm rank}_{x_{1}}(f)=k-1$ . Put

B=f(A_{1},\ldots,A_{k})

We aim to lower bound $|B|$ . For this, consider:

S=\left\{\left(x_{1},x_{2},\ldots,x_{k},y\right)\in A_{1}\times A_{2}\times% \cdots\times A_{k}\times B\mid y=f\left(x_{1},\ldots,x_{k}\right)\right\}.

Notice that, for every $(a_{1}\ldots,a_{k})\in A_{1}\times\ldots\times A_{k}$ , we have that $(a_{1}\ldots,a_{k},f(a_{1},\ldots,a_{k}))\in S$ , and so

\lvert S\rvert=n^{k}.

(7)

We claim that, for every $\varepsilon>0$ , one has

\lvert S\rvert=O\left(\lvert B\rvert^{\frac{2(k-1)}{5(k-1)-4}}n^{(k-1)(1+% \varepsilon)}\right),

(8)

where the constant of proportionality depends on $\varepsilon$ , $k$ , and $\deg(f)$ . Combining (7) and (8), we get

n^{k}=O\left(\lvert B\rvert^{\frac{2(k-1)}{5(k-1)-4}}n^{(k-1)(1+\varepsilon)}\right)

or

|B|=\Omega\left(n^{\frac{5(k-1)-4}{2(k-1)}-\varepsilon^{\prime}}\right),

where $\varepsilon^{\prime}=\tfrac{5(k-1)-4}{2}\varepsilon$ , which proves the proposition.

So in order to complete the proof of Proposition 9 we only need to prove (8). Let $T=T_{f,x_{1}}$ be the coefficient map defined in the introduction. By assumption, ${\rm rank}(J_{T})=k-1$ . Thus, there exist indices $\left(i_{1},\ldots,i_{k-1}\right)$ such that for

\hat{T}:(x_{2}\ldots,x_{k})\mapsto(\alpha_{i_{1}}(x_{2}\ldots,x_{k}),\ldots,% \alpha_{i_{k-1}}(x_{2}\ldots,x_{k})),

we have

\det J_{\hat{T}}\not\equiv 0.

Define

	$\displaystyle S_{0}$	$\displaystyle=\left\{\left(a_{1},\ldots,a_{k},b\right)\in S\mid\det J_{\hat{T}% }\left(a_{2},\ldots,a_{k}\right)=0\right\},$
	$\displaystyle S^{\prime}$	$\displaystyle=S\setminus S_{0}.$

Clearly $|S|=|S_{0}|+|S^{\prime}|$ .

Observe that,

|S_{0}|=|A_{1}|\cdot\left|\left(A_{2}\times\cdots\times A_{k}\right)\cap\left% \{\det J_{\hat{T}}=0\right\}\right|\leq n\cdot\deg(\det J_{\hat{T}})n^{k-2},

where the inequality is due to the Schwartz–Zippel Lemma (see [11, 16]). Thus, we get

\left|S_{0}\right|=O(n^{k-1}),

(9)

where the constant of proportionality depends on $\deg(f)$ and on $k$ .

We now bound $\lvert S^{\prime}\rvert$ . For this, we reduce the problem into a point-curve incidence problem in the plane as follows. With each $(a_{2},\ldots,a_{k})\in A_{2}\times\cdots\times A_{k}$ for which $\det J_{\hat{T}}(a_{2},\ldots,a_{k})\neq 0$ , we associate a curve $\gamma_{a_{2},\ldots,a_{k}}$ in $\mathbb{R}^{2}$ given by the equation

y=f(x,a_{2},\ldots,a_{k}).

Note that $\gamma_{a_{2},\ldots,a_{k}}$ is irreducible for every $(a_{2},\ldots,a_{k})\in A_{2}\times\cdots\times A_{k}$ , because it is defined by an equation of the form $y=P(x)$ , making it the graph of a polynomial. Let

	$\displaystyle\mathcal{P}$	$\displaystyle=A_{1}\times B,$
	$\displaystyle\mathcal{C}$	$\displaystyle=\left\{\gamma_{a_{2},\ldots,a_{k}}\mid\det J_{\hat{T}}(a_{2},% \ldots,a_{k})\neq 0\right\};$

note that curves in ${\cal C}$ are taken without multiplicity. Let $I(\mathcal{P},\mathcal{C})$ denote the set of point-curve incidences between $\mathcal{P}$ and $\mathcal{C}$ .

$\vartriangleright$ Claim 10.

We have

\lvert S^{\prime}\rvert=\Theta\left(\lvert I(\mathcal{P},\mathcal{C})\rvert% \right),

(10)

where the constant of proportionality depends only on $\deg f$ and on $k$ .

Proof.

By definition, if $(a_{1},a_{2},\ldots,a_{k},b)\in S^{\prime}$ then $((a_{1},b),\gamma_{a_{2},\ldots,a_{k}})\in I(\mathcal{P},\mathcal{C})$ . So, to prove the claim, it suffices to show that every $(p,\gamma)\in I(\mathcal{P},\mathcal{C})$ corresponds to at most $O(1)$ elements of $S^{\prime}$ .

For $\gamma\in\mathcal{C}$ , write

m(\gamma)=\left\{(a_{2},\ldots,a_{k})\mid\text{$\gamma_{a_{2},\ldots,a_{k}}=% \gamma$ and $\det J_{\hat{T}}(a_{2},\ldots,a_{k})\neq 0$}\right\}.

We need to prove that

|m(\gamma)|=O(1),

(11)

with constant of proportionality that depends only on $\deg(f)$ and on $k$ .

By the definition of the set $\mathcal{C}$ , we have that $\gamma$ is given by an equation of the form

y=\sum_{i=0}^{d_{x_{1}}}c_{i}x^{i},

for some coefficients $c_{0},\ldots,c_{d_{x_{1}}}\in\mathbb{R}$ . Let $V$ denote the algebraic variety which is given by the system of equations

$\displaystyle\alpha_{i_{1}}(x_{2},\ldots,x_{k})$	$\displaystyle=c_{i_{1}}$
$\displaystyle\alpha_{i_{2}}(x_{2},\ldots,x_{k})$	$\displaystyle=c_{i_{2}}$	(12)
$\displaystyle\vdots$
$\displaystyle\alpha_{i_{k-1}}(x_{2},\ldots,x_{k})$	$\displaystyle=c_{i_{k-1}}.$

Then

m(\gamma)\subset V.

Write $V=V_{0}\cup V_{+}$ , where $V_{0}$ is the union of all $0$ -dimensional irreducible components of $V$ , and $V_{+}$ is the union of all other irreducible components of $V$ . Recall that, by properties of real algebraic varieties, we have that $V_{0}$ is finite, and

|V_{0}|=O(1),

with a constant that depends only of $\deg(f)$ and on $k$ (see e.g. [1, 6, 15] for a bound on the number of connected components of a real algebraic variety).

Thus, to prove (11), it suffices to show that $m(\gamma)\subset V_{0}$ . Assume, for contradiction, that this is not the case. That is, there exists $(a_{2},\ldots,a_{k})\in m(\gamma)\cap V_{+}$ . Then, by definition, we have

	$\displaystyle\hat{T}$	$\displaystyle(a_{2},\ldots,a_{k})=(c_{i_{1}},\ldots,c_{i_{k-1}})$
	$\displaystyle\det$	$\displaystyle J_{\hat{T}}(a_{2},\ldots,a_{k})\neq 0.$

By the inverse function theorem, there exists an open neighborhood, $N$ , of $(a_{2},\ldots,a_{k})$ such that $\hat{T}$ restricted to $N$ is invertible. In particular,

N\cap\hat{T}^{-1}\{(c_{i_{1}},\ldots,c_{i_{k-1}})\}=\{(a_{2},\ldots,a_{k})\}.

On the other hand,

N\cap\hat{T}^{-1}(c_{i_{1}},\ldots,c_{i_{k-1}})=N\cap V.

Since $N$ is a neighborhood of $(a_{1},\ldots,a_{k-1})$ and the latter lies on an irreducible component of $V$ of dimension at least 1, the intersection $N\cap V$ must be infinite. This leads to a contradiction, and thus $m(\gamma)\subset V_{0}$ . This completes the proof of Claim 10. $\hfill\vartriangleleft$

In view of Claim 10, in order to bound $|S^{\prime}|$ it suffices to bound $\left|I\left(\mathcal{P},\mathcal{C}\right)\right|.$ We have $\lvert\mathcal{P}\rvert=n\lvert B\rvert$ and $\lvert\mathcal{C}\rvert\leq n^{k-1}$ . Since the curves in $\mathcal{C}$ are irreducible, every two distinct curves $\gamma,\gamma^{\prime}$ in $\mathcal{C}$ intersect in at most $d_{x_{1}}^{2}$ points, by Bezout’s Theorem (see e.g. [5, Corollary 7.8]). We can therefore apply Theorem 8. In our context, the family of curves $\mathcal{F}$ is parameterized by the $k-1$ variables from $A_{2}\times\dots\times A_{k}$ , so the dimension is $s\leq k-1$ . The degree $D\leq\max(\deg(f),1)$ and the complexity $K=O(1)$ depend strictly on $k$ and $deg(f)$ , and crucially, are independent of $n$ . This gives
$\displaystyle\lvert I\left(\mathcal{P},\mathcal{C}\right)\rvert$ $\displaystyle=O\left(\left(\lvert B\rvert\cdot n\right)^{\frac{2(k-1)}{5(k-1)-% 4}}n^{(k-1)\left(\frac{5(k-1)-6}{5(k-1)-4}+\varepsilon\right)}+(\lvert B\rvert n% )^{2/3}(n^{k-1})^{2/3}+\lvert B\rvert n+n^{k-1}\right).$

or

\displaystyle\lvert I\left(\mathcal{P},\mathcal{C}\right)\rvert

\displaystyle=O\left(\lvert B\rvert^{\frac{2(k-1)}{5(k-1)-4}}n^{(k-1)\left(1+% \varepsilon\right)}+|B|^{\frac{2}{3}}n^{\frac{2k}{3}}+\lvert B\rvert n+n^{k-1}% \right).

Note that we may assume without loss of generality that the first summand is dominant. Indeed, the second summand is dominant if

|B|^{\frac{2(k-1)}{5(k-1)-4}}n^{(k-1)(1+\varepsilon)}\leq|B|^{\frac{2}{3}}n^{% \frac{2k}{3}}

or

|B|\geq n^{\frac{5(k-1)-4}{4}+O(\varepsilon)},

which is stronger than the lower bound we wish to prove on $|B|$ , for every $k\geq 3$ . Similarly, the third summand is dominant if

|B|^{\frac{2r}{5r-4}}n^{r(1+\varepsilon)}\leq|B|n

or

|B|\geq n^{\frac{(k-2)(5(k-1)-4)}{3(k-1)-4}+\varepsilon\frac{(k-1)(5(k-1)-4)}{% 3(k-1)-4}},

which is better than the lower we want to prove on $|B|$ for every $k$ , as is easy to verify. Finally, the fourth summand is always subsumed by the first one.

Hence, either the conclusion of Proposition 9 holds, or we obtain

\lvert I\left(\mathcal{P},\mathcal{C}\right)\rvert=O\left(\lvert B\rvert^{% \frac{2(k-1)}{5(k-1)-4}}n^{(k-1)\left(1+\varepsilon\right)}\right).

In view of Claim 10 and combined with (9), the inequality (8) follows. This completes the proof Proposition 9. $\hfill\blacktriangleleft$

4 Proof of Theorem 5

The following lemma shows that the main Theorem 5 can in fact be reduced to the statement of Proposition 9.

Lemma 11.

Let $f\in\mathbb{R}\left[x_{1}\ldots,x_{k}\right]$ and assume that ${\rm{rank}}_{x_{1}}(f)=r<k-1$ . Then, up to renaming of the variables $x_{2},\ldots,x_{k}$ , we have that

g(x_{1},\ldots,x_{r+1}):=f\left(x_{1},x_{2},\ldots,x_{r+1},y_{r+2},\ldots,y_{k% }\right)

is a $(r+1)$ -variate polynomial in $\mathbb{R}\left[x_{1},\ldots,x_{r+1}\right]$ with ${\rm rank}_{x_{1}}(g)=r$ , for all $\left(y_{r+2},\ldots,y_{k}\right)\in\mathbb{R}^{k-r-1}\setminus Z_{0}$ , where $Z_{0}$ is some subvariety of $\mathbb{R}^{k-r-1}$ of codimension at least 1 and degree depending only on $k$ and $\deg(f)$ .

Proof.

Let $f$ be as in the statement. Let $T=T_{f,x_{1}}$ be the corresponding coefficient map. By assumption

{\rm rank}\left(J_{T}\right)=r<k-1.

(13)

Up to renaming the variables, we may assume without the loss of generality, that the first $r$ columns of $J_{T}$ , corresponding to the variables $x_{2},\ldots,x_{r+1}$ , are independent. Observe that the matrix composed of the first $r$ columns of $J_{T}$ , is in fact the Jacobian matrix of the coefficient map $T_{g,x_{1}}$ , where $g$ is the $(r+1)$ -variate polynomial given by

g\left(x_{1},x_{2},\ldots,x_{r+1}\right):=f\left(x_{1},x_{2},\ldots,x_{r+1},y_% {r+2},\ldots,y_{k}\right);

here $x_{2},\dots,x_{r+1}$ are regarded as constant parameters.

Our goal is to show that for $J_{T_{g,x_{1}}}$ , treated as a matrix with entries in $\mathbb{R}(x_{1},\ldots,x_{r+1})$ , we have that $\text{rank}(J_{T_{g,x_{1}}})=r$ , for every generic choice of $(y_{r+2},\dots,y_{k})\in\mathbb{R}^{k-r-1}$ .

Let $\Delta$ denote the polynomial corresponding to the sum of squares of the determinants of all the $r\times r$ submatrices of $J_{T_{g,x_{1}}}$ . So $\Delta$ is a multivariate polynomial, and we can write

\Delta(x_{2},\ldots,x_{r+1},y_{r+2},\ldots,y_{k})=\sum\limits_{i}\beta_{i}(y_{% r+2},\ldots,y_{k})g_{i}(x_{2},\ldots,x_{r+1}),

with $g_{i}\in\mathbb{R}[x_{2},\ldots,x_{r+1}]$ and $\beta_{i}\in\mathbb{R}[y_{r+2},\ldots,y_{k}]$ . By the definition of $\Delta$ we have
${\rm rank}(J_{T_{g,x_{1}}}(x_{2},\ldots,x_{r+1},y_{r+2},\ldots,y_{k}))<r$ if and only if $\Delta(x_{2},\ldots,x_{r+1},y_{r+2},\ldots,y_{k})=0$ .

Thus, in view of (13), we have $\Delta\not\equiv 0$ . In particular, the polynomials $\beta_{i}$ are not all zero. Thus, letting

Z_{0}:=\left\{\left(y_{r+2},\ldots,y_{k}\right)\mid\forall i\nobreak\ \beta_{i% }(y_{r+2},\ldots,y_{k})=0\right\},

we see that $Z_{0}$ has codimension at least 1. This completes the proof of the lemma. $\hfill\blacktriangleleft$

We can now complete the proof of our main Theorem 5.

Proof of Theorem 5.

Let $f\in\mathbb{R}[x_{1},\ldots,x_{k}]$ and assume without loss of generality that $\deg_{x_{1}}(f)=r\leq k-2$ . Apply Lemma 11 to $f$ . Then, up to renaming of the variables, there exists an algebraic variety $Z_{0}\subset\mathbb{R}^{k-r-1}$ , of codimension at least one, and of degree $O(1)$ , such that for every $(y_{r+2},\ldots,y_{k})\in\mathbb{R}^{k-r-1}\setminus Z_{0}$ we have that the polynomial

(x_{1},\ldots,x_{r+1})\mapsto f(x_{1},\ldots,x_{r+1},y_{r+2},\ldots,y_{k})

is an $(r+1)$ -variate polynomial of rank $r$ .

Observe that, by the Schwartz–Zippel lemma, there exists $(a_{r+2},\ldots,a_{k})\in\left(A_{r+2}\times\ldots\times A_{k}\right)\setminus Z% _{0}$ . Thus

g(x_{1},\ldots,x_{r+1}):=f(x_{1},\ldots,x_{r+1},a_{r+2},\ldots,a_{k})

satisfies ${\rm rank}_{x_{1}}(g)=r$ . Thus, by Proposition 9, we have that

|g(A_{1},\ldots,A_{r+1})|=\Omega\left(n^{\frac{5r-4}{2r}-\varepsilon}\right).

Noting that

g(A_{1},\ldots,A_{r+1})=f(A_{1},\ldots,A_{r+1},\{a_{r+2}\},\ldots,\{a_{k}\})% \subset f(A_{1},\ldots,A_{k}),

this completes the proof of the theorem. $\hfill\blacktriangleleft$

5 Characterization of rank-1 polynomials

In this section we prove Theorem 6. For the proof we will use the following lemma from Raz and Shem Tov [10].

Lemma 12 (Raz–Shem Tov [10, Lemma 2.3]).

Let $f\in\mathbb{R}[x_{1},\ldots,x_{k}]$ . Assume that

\frac{\frac{\partial f}{\partial x_{1}}(x_{1},\ldots,x_{k})}{r_{1}(x_{1})}=% \cdots=\frac{\frac{\partial f}{\partial x_{k}}(x_{1},\ldots,x_{k})}{r_{k}(x_{k% })},

(14)

for some univariate real polynomials $r_{1},\ldots,r_{k}$ . Then, $f$ is one of the forms

	$\displaystyle f\left(x_{1},\ldots,x_{k}\right)$	$\displaystyle=h\left(p_{1}\left(x_{1}\right)+\cdots+p_{k}\left(x_{k}\right)% \right)\ \ \text{ or}$
	$\displaystyle f\left(x_{1},\ldots,x_{k}\right)$	$\displaystyle=h\left(p_{1}\left(x_{1}\right)\cdot\cdots\cdot p_{k}\left(x_{k}% \right)\right),$

for some univariate real polynomials $h(x),p_{1}(x),\ldots,p_{k}(x)$ .

Proof of Theorem 6.

Let $f$ be as in the statement. Since $f$ depends non-trivially on each of its variables, we have in particular that

{\rm rank}_{x_{i}}(f)=1,\quad\text{ for each $i=1,\ldots,k$.}

(15)

In view of Lemma 12, it suffices to show that $f$ satisfies the differential equation (14), for some univariate polynomials $r_{1},\ldots,r_{k}$ . By symmetry, it suffices to prove that

\frac{\frac{\partial f}{\partial x_{1}}(x_{1},\ldots,x_{k})}{r_{1}(x_{1})}=% \frac{\frac{\partial f}{\partial x_{2}}(x_{1},\ldots,x_{k})}{r_{2}(x_{2})}

(16)

We write

f\left(x_{1},\ldots,x_{k}\right)=\sum_{i=0}^{d_{x_{1}}}\alpha_{i}^{(1)}\left(x% _{2},\ldots,x_{k}\right)x_{1}^{i}=\cdots=\sum_{i=0}^{d_{x_{k}}}\alpha_{i}^{(k)% }\left(x_{1},\ldots,x_{k-1}\right)x_{k}^{i},

(17)

where $d_{x_{j}}$ stands for the degree of $f$ as a univariate polynomial in the variable $x_{j}$ . Then for every $j,\ell\in\left\{1,\ldots,k\right\}$ , such that $j\neq\ell$ , we have

\frac{\partial f}{\partial x_{j}}\left(x_{1},\ldots,x_{k}\right)=\sum_{i=0}^{d% _{x_{\ell}}}\frac{\partial\alpha_{i}^{(\ell)}\left(x_{1},\ldots,\widehat{x_{% \ell}},\ldots,x_{k}\right)}{\partial x_{j}}x_{\ell}^{i}.

(18)

We next show that

\frac{\frac{\partial f}{\partial x_{1}}}{{\frac{\partial f}{\partial x_{2}}}}=% u(x_{1},x_{2}),

(19)

where $u$ is some rational function over $\mathbb{R}$ .

In other words, we need to show that $\frac{\partial f}{\partial x_{1}}/{\frac{\partial f}{\partial x_{2}}}$ is independent of $x_{i}$ , for every $i\neq 1,2$ . By symmetry it suffices to show that this ratio is independent of the variable $x_{3}$ . Consider the first two columns of $J_{T_{f,x_{3}}}$ , corresponding to derivatives with respect to $x_{1}$ and to $x_{2}$ . Namely,

\left(\begin{array}[]{cc}\frac{\partial\alpha_{0}^{(3)}}{\partial x_{1}}&\frac% {\partial\alpha_{0}^{(3)}}{\partial x_{2}}\\ \frac{\partial\alpha_{1}^{(3)}}{\partial x_{1}}&\frac{\partial\alpha_{1}^{(3)}% }{\partial x_{2}}\\ \vdots&\vdots\\ \frac{\partial\alpha_{d_{x_{3}}}^{(3)}}{\partial x_{1}}&\frac{\partial\alpha_{% d_{x_{3}}}^{(3)}}{\partial x_{2}}\end{array}\right).

Note that neither of the columns is zero, since $f$ depends non-trivially in each of its variables. Moreover, since ${\rm rank}(J_{T_{f,x_{3}}})=1$ , by (15), and using the fact that the entries of $J_{T_{f,x_{3}}}$ are independent of $x_{3}$ , we get that there exists a rational function $u(x_{1},x_{2},x_{4},\ldots,x_{k})$ such that

\frac{\partial\alpha_{i}^{(3)}}{\partial x_{1}}=u(x_{1},x_{2},x_{4},\ldots,x_{% k})\frac{\partial\alpha_{i}^{(3)}}{\partial x_{2}},\quad\text{for $i=0,\ldots,% d_{x_{3}}$.}

Using the identity (18), this implies that

\frac{\frac{\partial f}{\partial x_{1}}}{\frac{\partial f}{\partial x_{2}}}=u(% x_{1},x_{2},x_{4},\ldots,x_{k});

that is, this ratio is independent of $x_{3}$ . This proves (19).

Repeating the analysis symmetrically for the pair $x_{1},x_{3}$ and then to the pair $x_{2},x_{3}$ we conclude that there exist real rational functions $v(x_{1},x_{3})$ and $w(x_{2},x_{3})$ such that

	$\displaystyle\frac{\frac{\partial f}{\partial x_{1}}}{\frac{\partial f}{% \partial x_{3}}}$	$\displaystyle=v(x_{1},x_{3})$
	$\displaystyle\frac{\frac{\partial f}{\partial x_{2}}}{\frac{\partial f}{% \partial x_{3}}}$	$\displaystyle=w(x_{2},x_{3}).$

But then

\frac{\frac{\partial f}{\partial x_{1}}}{\frac{\partial f}{\partial x_{2}}}=% \frac{v(x_{1},x_{3})}{w(x_{2},x_{3})}=u(x_{1},x_{2}),

meaning in particular that the ratio of $v, w$ is independent of $x_{3}$ . Thus, setting an arbitrary value for $x_{3}$ , we get that

\frac{\frac{\partial f}{\partial x_{1}}}{\frac{\partial f}{\partial x_{2}}}=% \frac{v(x_{1},0)}{w(x_{2},0)}.

Thus, letting $r_{1}(x_{1}):=v(x_{1},0)$ and $r_{2}(x_{2}):=w(x_{2},0)$ , this proves (16), and hence completes the proof of the lemma. $\hfill\blacktriangleleft$

6 Distinct $𝒅$ -volumes on the moment curve in $\mathbb{R}^{d}$

In this section we prove Theorem 7.

Proof of Theorem 7.

The moment curve in $\mathbb{R}^{d}$ is defined by $\nu(x)=(x,x^{2},\ldots,x^{d})$ . Consider $d+1$ point on $\nu$ given by the parameters $x_{1},\ldots,x_{d+1}\in\mathbb{R}^{d}$ , and let $\sigma(x_{1},\ldots,x_{d+1})$ denote the simplex spanned by these points. Define

f(x_{1},\ldots,x_{d+1}):={\rm vol}\sigma(x_{1},\ldots,x_{d+1}).

It suffices to prove that

{\rm rank}_{x_{d+1}}(f)=d.

(20)

Indeed, assume that (20) is true and let $P\subset\nu$ be a set of size $n$ . Let $A$ denote the $x_{1}$ -coordinate of the points in $P$ . Then $\Delta(P)=f(A,\ldots,A)$ . By Theorem 5, for every $\varepsilon>0$ , we have

|\Delta(P)|=|f(A,\ldots,A)|=\Omega\left(n^{\frac{5d-4}{2d}-\varepsilon}\right),

as needed.

So we only need to prove (20). We have

\displaystyle f(x_{1},\ldots,x_{d+1})

\displaystyle=\frac{1}{d!}\det\begin{pmatrix}1&x_{1}&x_{1}^{2}&\ldots&x_{1}^{d% }\\ 1&x_{2}&x_{2}^{2}&\ldots&x_{2}^{d}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_{d+1}&x_{d+1}^{2}&\ldots&x_{d+1}^{d}\\ \end{pmatrix},

which is the determinant of the $(d+1)\times(d+1)$ -Vandermonde matrix. Thus

	$\displaystyle f(x_{1},\ldots,x_{d+1})$	$\displaystyle=\frac{1}{d!}\prod_{1\leq i<j\leq d+1}(x_{j}-x_{i})$
		$\displaystyle=\frac{1}{d!}\prod_{1\leq i<j\leq d}(x_{j}-x_{i})\prod_{k=1}^{d}(% x_{d+1}-x_{k})$
		$\displaystyle=g(x_{1},\ldots,x_{d})\hat{f}(x_{1},\ldots,x_{d+1}),$

where $g(x_{1},\ldots,x_{d}):=\frac{1}{d!}\prod_{1\leq i<j\leq d}(x_{j}-x_{i})$ is independent of $x_{d+1}$ and $\hat{f}(x_{1},\ldots,x_{d+1}):=\prod_{k=1}^{d}(x_{d+1}-x_{k}).$ Note that $\hat{f}$ can be written as

\hat{f}(x_{1},\ldots,x_{d+1})=\sum_{\ell=0}^{d}s_{\ell}(x_{1},\ldots,x_{d})x_{% d+1}^{\ell},

where

	$\displaystyle s_{0}(x_{1},\ldots,x_{d})$	$\displaystyle=(-1)^{d}x_{1}\cdots x_{d}$
	$\displaystyle s_{1}(x_{1},\ldots,x_{d})$	$\displaystyle=(-1)^{d-1}(x_{2}\cdots x_{d}+x_{1}x_{3}\cdots x_{d}+\cdots+x_{1}% \cdots x_{d-1})$
		$\displaystyle\ldots$
	$\displaystyle s_{d-1}(x_{1},\ldots,x_{d})$	$\displaystyle=-x_{1}-\cdots-x_{d}$
	$\displaystyle s_{d}(x_{1},\ldots,x_{d})$	$\displaystyle=1,$

are the symmetric polynomials.

$\vartriangleright$ Claim 13.

Let $M$ be the $d\times d$ matrix $M=(M_{i,j})_{0\leq i\leq d-1,\;1\leq j\leq d}$ given by

M_{i,j}=\frac{\partial s_{i}}{\partial x_{j}}\qquad(0\leq i\leq d-1,\;1\leq j% \leq d).

Then ${\rm rank}(M)=d$ .

The strategy for this proof is adapted from the proof of [ [7], section 4].

Proof.

We prove that $\det M$ is not the zero polynomial. Consider the function

P(x_{1},\ldots,x_{d},t)=\prod_{k=1}^{d}(t-x_{k})=\sum_{k=0}^{d}s_{k}\,t^{k},

which is a monic polynomial in $t$ .

For $1\leq j\leq d$ we have

\frac{\partial P}{\partial x_{j}}(t)=-\prod_{\begin{subarray}{c}k=1\\ k\neq j\end{subarray}}^{d}(t-x_{k})=\sum_{k=0}^{d-1}\frac{\partial s_{k}}{% \partial x_{j}}\,t^{k}

Evaluating at $t=x_{i}$ yields

\frac{\partial P}{\partial x_{j}}(x_{i})=\sum_{k=0}^{d-1}\frac{\partial s_{k}}% {\partial x_{j}}\,x_{i}^{k}=\begin{cases}0,&i\neq j,\\[4.0pt] -\displaystyle\prod_{k\neq j}(x_{j}-x_{k}),&i=j.\end{cases}

(21)

The identity (21) implies

\begin{pmatrix}1&x_{1}&x_{1}^{2}&\ldots&x_{1}^{d-1}\\ 1&x_{2}&x_{2}^{2}&\ldots&x_{2}^{d-1}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_{d}&x_{d}^{2}&\ldots&x_{d}^{d-1}\\ \end{pmatrix}M=\operatorname{diag}\left(\frac{\partial P}{\partial x_{1}}(x_{1% }),\ldots,\frac{\partial P}{\partial x_{d}}(x_{d})\right).

Thus

	$\displaystyle\det(M)$	$\displaystyle=\frac{(-1)^{d}\prod_{j=1}^{d}\prod_{i\neq j}(x_{j}-x_{i})}{\prod% _{1\leq i<j\leq d}(x_{j}-x_{i})}$
		$\displaystyle=\frac{(-1)^{d}\prod_{1\leq i\neq j\leq d}(x_{j}-x_{i})}{\prod_{1% \leq i<j\leq d}(x_{j}-x_{i})}$
		$\displaystyle=\prod_{1\leq i<j\leq d}(x_{j}-x_{i}).$

This completes the proof of Claim 13. $\hfill\vartriangleleft$

We are now ready to prove (20). Write

f(x_{1},\ldots,x_{d+1})=\sum_{i=0}^{d}\alpha_{i}(x_{1},\ldots,x_{d})x_{d+1}^{i}.

By the above we have

\alpha_{i}=g(x_{1},\ldots,x_{d})s_{i}(x_{1},\ldots,x_{d}),\text{ for $i=0,% \ldots,d$}

Let $T=T_{f,x_{d+1}}$ . Denoting partial derivatives with subscripts (e.g., $g_{x_{1}}=\frac{\partial g}{\partial x_{1}}$ ), we have

J_{T}=\begin{pmatrix}g_{x_{1}}s_{0}+g{s_{0}}_{x_{1}}&g_{x_{2}}s_{0}+g{s_{0}}_{% x_{2}}&\cdots&g_{x_{d}}s_{0}+g{s_{0}}_{x_{d}}\\ \vdots&\vdots&&\vdots\\ g_{x_{1}}s_{d-1}+g{s_{d-1}}_{x_{1}}&g_{x_{2}}s_{d-1}+g{s_{d-1}}_{x_{2}}&\cdots% &g_{x_{d}}s_{d-1}+g{s_{d-1}}_{x_{d-1}}\\ g_{x_{1}}&g_{x_{2}}&\cdots&g_{x_{d}}\end{pmatrix}.

Applying row operation to the first $d$ rows, namely, $R_{i}\leftarrow R_{i}-s_{i}R_{d}$ we get

	$\displaystyle{\rm rank}J_{T}$	$\displaystyle={\rm rank}\begin{pmatrix}g{s_{0}}_{x_{1}}&g{s_{0}}_{x_{2}}&% \cdots&g{s_{0}}_{x_{d}}\\ \vdots&\vdots&&\vdots\\ g{s_{d-1}}_{x_{1}}&g{s_{d-1}}_{x_{2}}&\cdots&g{s_{d-1}}_{x_{d-1}}\\ g_{x_{1}}&g_{x_{2}}&\cdots&g_{x_{d}}\end{pmatrix}$
		$\displaystyle={\rm rank}\begin{pmatrix}{s_{0}}_{x_{1}}&{s_{0}}_{x_{2}}&\cdots&% {s_{0}}_{x_{d}}\\ \vdots&\vdots&&\vdots\\ {s_{d-1}}_{x_{1}}&{s_{d-1}}_{x_{2}}&\cdots&{s_{d-1}}_{x_{d-1}}\\ g_{x_{1}}/g&g_{x_{2}}/g&\cdots&g_{x_{d}}/g\end{pmatrix}.$

Note that first $d$ rows of the above matrix are exactly the matrix $M$ from Claim 13. This completes the proof of Theorem 7 $\hfill\blacktriangleleft$

References

[1] S. Basu, R. Pollack, and M.F. Coste-Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer Berlin Heidelberg, 2007. URL: https://books.google.co.il/books?id=8Hyp1SLis4IC.
[2] Frank de Zeeuw. A survey of elekes-rónyai-type problems. arXiv: Combinatorics, pages 95–124, 2018. URL: https://api.semanticscholar.org/CorpusID:73602404.
[3] György Elekes. On linear combinatorics i. concurrency—an algebraic approach. Combinatorica, 17(4):447–458, 1997. doi:10.1007/BF01194999.
[4] György Elekes and Lajos Rónyai. A combinatorial problem on polynomials and rational functions. J. Comb. Theory A, 89(1):1–20, 2000. doi:10.1006/jcta.1999.2976.
[5] Robin Hartshorne. Algebraic Geometry, volume 52 of Graduate texts in mathematics. Springer, 1977. doi:10.1007/978-1-4757-3849-0.
[6] J. Milnor. On the betti numbers of real varieties. Proceedings of the American Mathematical Society, 15(2):275–280, 1964. URL: http://www.jstor.org/stable/2034050.
[7] João F. Queiró. An inverse problem for singular values and the jacobian of the elementary symmetric functions. Linear Algebra and its Applications, 197–198:277–282, 1994. doi:10.1016/0024-3795(94)90491-X.
[8] Orit E. Raz, Micha Sharir, and Frank De Zeeuw. Polynomials vanishing on cartesian products: the elekes–szabó theorem revisited. Duke Mathematical Journal, 165(18):3517–3566, 2016. doi:10.1215/00127094-3674103.
[9] Orit E. Raz, Micha Sharir, and Frank de Zeeuw. The elekes–szabó theorem in four dimensions. Israel J. Math., 227:663–690, 2018.
[10] Orit E. Raz and Zvika Shem-Tov. Expanding polynomials: A generalization of the elekes–rónyai theorem to $d$ variables. Combinatorica, 40(5):721–748, 2020. doi:10.1007/s00493-020-4041-0.
[11] Jacob Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27:701–717, 1980. doi:10.1145/322217.322225.
[12] Micha Sharir and Joshua Zahl. Cutting algebraic curves into pseudo-segments and applications. J. Combin. Theory Ser. A, 150:1–35, 2017. doi:10.1016/j.jcta.2017.02.006.
[13] József Solymosi and J. Zhal. Improved elekes–szabó type estimates using proximity. J. Combin. Theory Ser. A, 201:105813, 2024. doi:10.1016/j.jcta.2023.105813.
[14] Endre Szemerédi and William T. Trotter. A combinatorial distinction between the euclidean and projective planes. European J. Combin., 4:385–394, 1983. doi:10.1016/S0195-6698(83)80036-5.
[15] R. Thom. Sur l’homologie des variétés algébriques réelles. In Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pages 255–265. Princeton Univ. Press, Princeton, N.J., 1965.
[16] Richard Zippel. An explicit separation of relativised random polynomial time and relativised deterministic polynomial time. Inform. Process. Lett., 33:207–212, 1989. doi:10.1016/0020-0190(89)90143-9.

[bib.bib1] [1] S. Basu, R. Pollack, and M.F. Coste-Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer Berlin Heidelberg, 2007. URL: https://books.google.co.il/books?id=8Hyp1SLis4IC.

[bib.bib2] [2] Frank de Zeeuw. A survey of elekes-rónyai-type problems. arXiv: Combinatorics, pages 95–124, 2018. URL: https://api.semanticscholar.org/CorpusID:73602404.

[bib.bib3] [3] György Elekes. On linear combinatorics i. concurrency—an algebraic approach. Combinatorica, 17(4):447–458, 1997. doi:10.1007/BF01194999.

[bib.bib4] [4] György Elekes and Lajos Rónyai. A combinatorial problem on polynomials and rational functions. J. Comb. Theory A, 89(1):1–20, 2000. doi:10.1006/jcta.1999.2976.

[bib.bib5] [5] Robin Hartshorne. Algebraic Geometry, volume 52 of Graduate texts in mathematics. Springer, 1977. doi:10.1007/978-1-4757-3849-0.

[bib.bib6] [6] J. Milnor. On the betti numbers of real varieties. Proceedings of the American Mathematical Society, 15(2):275–280, 1964. URL: http://www.jstor.org/stable/2034050.

[bib.bib7] [7] João F. Queiró. An inverse problem for singular values and the jacobian of the elementary symmetric functions. Linear Algebra and its Applications, 197–198:277–282, 1994. doi:10.1016/0024-3795(94)90491-X.

[bib.bib8] [8] Orit E. Raz, Micha Sharir, and Frank De Zeeuw. Polynomials vanishing on cartesian products: the elekes–szabó theorem revisited. Duke Mathematical Journal, 165(18):3517–3566, 2016. doi:10.1215/00127094-3674103.

[bib.bib9] [9] Orit E. Raz, Micha Sharir, and Frank de Zeeuw. The elekes–szabó theorem in four dimensions. Israel J. Math., 227:663–690, 2018.

[bib.bib10] [10] Orit E. Raz and Zvika Shem-Tov. Expanding polynomials: A generalization of the elekes–rónyai theorem to $d$ variables. Combinatorica, 40(5):721–748, 2020. doi:10.1007/s00493-020-4041-0.

[bib.bib11] [11] Jacob Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27:701–717, 1980. doi:10.1145/322217.322225.

[bib.bib12] [12] Micha Sharir and Joshua Zahl. Cutting algebraic curves into pseudo-segments and applications. J. Combin. Theory Ser. A, 150:1–35, 2017. doi:10.1016/j.jcta.2017.02.006.

[bib.bib13] [13] József Solymosi and J. Zhal. Improved elekes–szabó type estimates using proximity. J. Combin. Theory Ser. A, 201:105813, 2024. doi:10.1016/j.jcta.2023.105813.

[bib.bib14] [14] Endre Szemerédi and William T. Trotter. A combinatorial distinction between the euclidean and projective planes. European J. Combin., 4:385–394, 1983. doi:10.1016/S0195-6698(83)80036-5.

[bib.bib15] [15] R. Thom. Sur l’homologie des variétés algébriques réelles. In Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pages 255–265. Princeton Univ. Press, Princeton, N.J., 1965.

[bib.bib16] [16] Richard Zippel. An explicit separation of relativised random polynomial time and relativised deterministic polynomial time. Inform. Process. Lett., 33:207–212, 1989. doi:10.1016/0020-0190(89)90143-9.

	$\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}))$

Improved Bound for the 𝒌-Variate Elekes–Rónyai Theorem

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 ([9, 10]).

Our results

Example 2.

Example 3.

Example 4.

Theorem 5.

Theorem 6.

Theorem 7.

Organization of the paper

2 Incidences between points and algebraic curves

Theorem 8 (Sharir–Zahl [12]).

3 A special case

Proposition 9.

Proof.

⊳ Claim 10.

Proof.

4 Proof of Theorem 5

Lemma 11.

Proof.

Proof of Theorem 5.

5 Characterization of rank-1 polynomials

Lemma 12 (Raz–Shem Tov [10, Lemma 2.3]).

Proof of Theorem 6.

6 Distinct 𝒅-volumes on the moment curve in ℝ𝒅

Proof of Theorem 7.

⊳ Claim 13.

Proof.

References

Improved Bound for the $𝒌$ -Variate Elekes–Rónyai Theorem

$\vartriangleright$ Claim 10.

6 Distinct $𝒅$ -volumes on the moment curve in $\mathbb{R}^{d}$

$\vartriangleright$ Claim 13.