Archive for April, 2010

Lattice points on algebraic curves: a uniform estimate (after Bombieri and Pila)

April 23, 2010

In the previous post we discussed the following result of Bombieri and Pila (1989): let ${{\Gamma\subset {\mathbb R}^2}}$ be a compact segment of a real analytic transcendental plane curve; then for any positive integer ${N}$

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right| \le c(\Gamma, \epsilon)N^\epsilon.$

Bombieri and Pila remark that a similar (and even stronger) statement holds if ${\Gamma}$ is algebraic but does not admit polynomial parametrization.

The obvious disadvantage of this result is dependence of the constant ${c}$ in ${\Gamma}$. It turns out that a slightly weaker inequality holds uniformly for all algebraic curves of given degree. Precisely:

Theorem 1 let ${\Gamma}$ be segment of an irreducible plane algebraic curve of degree ${\nu}$ contained in the unit square ${[0,1]^2}$. Then for ${{\epsilon>0}}$

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right| \le c(\nu,\epsilon)N^{1/\nu+\epsilon}.$

Equivalently, if ${\Gamma}$ is a segment of an irreducible algebraic curve of degree ${\nu}$ contained in the square ${[0,N]^2}$, then

$\displaystyle \left|\Gamma \cap {\mathbb Z}^2\right| \le c(\nu,\epsilon)N^{1/\nu+\epsilon}.$

One cannot do better than the exponent ${1/\nu}$, as the example ${y=x^\nu}$ shows.

Due to the uniformity, this result easily extends to arbitrary dimension by projection and slicing (Pila 1995): let ${V}$ be an irreducible affine variety of dimension ${\mu}$ and degree ${\nu}$, contained in the affine space ${{\mathbb R}^n}$; then

$\displaystyle \left|V\cap [0,N]^n \cap{\mathbb Z}^n\right|\le c(n,\nu,\epsilon) N^{\mu-1+1/\nu+\epsilon}.$

The proof of Theorem 1 goes along similar lines as that in the transcendence case, but is more involved, because now we have to keep track of the dependence of all parameters in the function ${f}$. For a function ${f\in C^n(I)}$ we define the ${n}$-norm by

$\displaystyle \|f\|_n= \max\left\{|f|_\infty, \frac{|f'|_\infty}{1!}, \ldots, \frac{|f^{(n)}|_\infty}{n!}\right\},$

where ${|\cdot|_\infty}$ is the sup-norm. With this definition we can make inequality (1) of the previous post totally explicit:

$\displaystyle \Bigl|\det \bigl[f_i(x_j)\bigr]\Bigr|\le n!\|f_1\|_n\cdots\|f_n\|_n \bigl(\max|x_i-x_j|\bigr)^{n(n-1)/2}.$

The Leibniz identity

$\displaystyle \frac{(f_1\cdots f_k)^{(n)}}{n!} = \sum_{a_1+\cdots+a_k=n} \frac{f_1^{(a_1)}}{a_1!}\cdots \frac{f_k^{(a_k)}}{a_k!}$

shows that

$\displaystyle \|f_1\cdots f_k\|_n \le \binom{n+k-1}{k-1} \|f_1\|\cdots \|f_k\|_n.$

In particular, if ${{I\subset[0,1]}}$ then

$\displaystyle \|x^if(x)^j\|_n\le \binom {n+i+j-1}{i+j-1}\|f\|_n^j.$

In the sequel by a ${(d,e)}$-curve we mean a plane algebraic curve ${{P(x,y)=0}}$ of degree less than ${d}$ in ${x}$ and less then ${e}$ in ${y}$. Arguing as in the previous post, we prove the following: let ${f}$ be a sufficiently smooth function, defined on a compact interval ${I}$. Let ${{(x_1, y_1), \ldots, (x_s, y_s)}}$ be points on the curve ${\Gamma}$ defined by ${y=f(x)}$, not lying on on a ${(d,e)}$-curve. Assume that the coordinates ${x_i}$ and ${y_i}$ are rational numbers with denominator ${N}$; then

$\displaystyle \max|x_i-x_j|\ge c \left(\|f\|_{de-1}^{e-1}N^{d+e-2}\right)^{-1/(de-1)} \ge c\|f\|_{de}^{-1/d}N^{-1/e-1/d} \ \ \ \ \ (1)$

with ${c=c(d,e)}$. (Here unnumbered constants ${c}$ may vary from equation to equation, while numbered constants ${c_0}$, ${c_1}$, etc. are individual.)

From now on we assume that ${{I\subset[0,1]}}$. If the set ${\Gamma\cap(N^{-1}{\mathbb Z})^2}$ does not lie on a single ${(d,e)}$-curve, then the right-hand side of (1) does not exceed the length of ${I}$. Splitting ${I}$ into subintervals shorter than this right-hand side, it follows immediately that the set ${\Gamma\cap(N^{-1}{\mathbb Z})^2}$ lies on at most

$\displaystyle \max\left\{1,c\|f\|_{de}^{1/d}N^{1/e+1/d}\right\}, \qquad c=c(d,e).$

${(d,e)}$-curves. (We have to write ${\max\{1,\cdot\}}$ to take into account the case when the set ${\Gamma\cap(N^{-1}{\mathbb Z})^2}$ lies on a single ${(d,e)}$-curve.)

Now assume that ${f(x)}$ is a ${(\mu, \nu)}$-algebraic function; that is, it satisfies a polynomial equation ${{P\bigl(x,f(x)\bigr)=0}}$, where ${P(x,y)}$ is an irreducible real polynomial of ${x}$-degree ${\mu}$ and ${y}$-degree ${\nu}$. In this case the curve ${\Gamma}$, defined by ${y=f(x)}$ has at most ${{(d+\nu)(\mu+\nu)}}$ intersections with any ${(d,\nu)}$-curve. Hence

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right|\le c_0\max\left\{1,\|f\|_{d\nu}^{1/d}\right\}N^{1/\nu+1/d}, \ \ \ \ \ (2)$
$\displaystyle c_0=c_0(\mu,\nu,d).$

Our next goal is get rid of the norm of ${f}$. To do this, Bombieri and Pila show that the norm is “large” only on short intervals. Precisely:

Proposition 2 Let ${f}$ be a ${(\mu, \nu)}$-algebraic function defined on an interval ${{I\subset[0,1]}}$. Let ${n}$ be a positive integer. Then for every ${A>0}$ there is at most ${c_1(\mu,\nu, n)}$ intervals of length at most ${c_2(\mu,\nu,n)A^{-1/n}}$ each such that ${{\|f\|_n\le A\|f\|_0}}$ outside these intervals.

We postpone the proof of this proposition until one of my subsequent posts, and show now how it allows one to replace ${\|f\|_{d\nu}}$ by ${\|f\|_0}$ in (2). Precisely:

Proposition 3 For ${f}$ as in Proposition 2 and any ${d}$ we have

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right|\le C\max\left\{1, \|f\|_0^{1/d}\right\}N^{1/\nu+2/d},\ \ \ \ \ (3)$
$\displaystyle C=C(\mu,\nu,d).$

In particular, if ${f}$ takes values in ${[0,1]}$ then

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right|\le CN^{1/\nu+2/d} \ \ \ \ \ (4)$

The proof is by induction in ${N}$. The definition of ${C}$ under which the induction works will appear in the course of the proof.

Applying Proposition 2 with ${A=N}$ and ${{n=d\nu}}$, we split our interval ${I}$ into ${\le c_1}$ intervals of length ${\le c_2N^{-1/d\nu}}$ (call them “short”) where ${\|f\|_{d\nu}}$ is “large”, and the remaining part where ${\|f\|_{d\nu}\le N\|f\|_0}$. This remaining part itself splits into at most ${{c_1+1}}$ intervals (call them “long”). Applying to every “long” interval estimate (2), we see that the curve ${\Gamma}$ has at most

$\displaystyle (c_1+1)c_0\max\left\{1, \|f\|_0^{1/d}\right\}N^{1/\nu+2/d} \ \ \ \ \ (5)$

points with denominator ${N}$ above these “long” intervals.

Now let ${J}$ be a “short” interval, and let ${{\ell=\ell(J)}}$ be its length. We may assume that ${{J=[a/N,b/N]}}$ with ${{a,b\in {\mathbb Z}}}$, so that ${\ell}$ is an integral multiple of ${1/N}$:

$\displaystyle \ell = \frac{N'}N, \qquad 0\le N'

If ${N'=0}$ then ${\Gamma}$ has only ${1}$ point over ${J}$. If ${{N'>0}}$ then the number of points with denominator ${N}$ on ${\Gamma}$ over ${J}$ is the same as the number of points with denominator ${N'}$ on the curve ${{y=\ell^{-1}f(\ell^{-1}x)}}$ over the interval ${[0,1]}$ . By induction, the latter quantity is bounded by

$\displaystyle C\max\left\{1, \|\ell^{-1}f\|_0^{1/d}\right\}(N')^{1/\nu+2/d} \le C\ell^{1/\nu} \max\left\{1, \|f\|_0^{1/d}\right\}N^{1/\nu+2/d}$

Since ${\ell\le c_2N^{-1/d\nu}}$, the latter quantity does not exceed

$\displaystyle C c_2N^{-1/\nu^2d}\max\left\{1, \|f\|_0^{1/d}\right\}N^{1/\nu+2/d}.$

Hence there is at most

$\displaystyle Cc_1c_2N^{-1/\nu^2d} \max\left\{1, \|f\|_0^{1/d}\right\} N^{1/\nu+2/d} \ \ \ \ \ (6)$

points over “short” intervals.

Thus, the total number of points with denominator ${N}$ on ${\Gamma}$ is bounded by the sum of (5) and (6). Now let ${{N_0=N_0(\mu,\nu,d)}}$ be a so large that for ${{N\ge N_0}}$ the quantity (6) does not exceed ${{\frac12 C \max\left\{1, \|f\|_0^{1/d}\right\} N^{1/\nu+2/d}}}$. Then

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right|\le \left((c_1+1)c_0+\frac12C\right)\max\left\{1, \|f\|_0^{1/d}\right\}N^{1/\nu+2/d}. \ \ \ \ \ (7)$

Now if ${{C\ge N_0}}$ then (3) holds trivially for ${{N\le N_0}}$, which gives the base of our induction. And if ${{C\ge 2(c_1+1)c_0}}$ then the right-hand side of (7) does not exceed that of (3), which gives the induction step. This proves Proposition 3.

Now we easily complete the proof of Theorem 1. Let ${F(x,y)=0}$ be the irreducible equation of our curve, so that ${\deg F=\nu}$. We may assume that ${\deg_xF=\deg_yF=\nu}$. Indeed, one may find a unimodular integral matrix ${\begin{bmatrix}a&b\\c&d\end{bmatrix}}$ with entries non-exceeding ${\nu}$ in absolute value such that the polynomial ${F(ax+by,cx+dy)}$ is of both ${x}$-degree and ${y}$-degree ${\nu}$. The image of the unit square under the linear transformation defined by the inverse of this matrix is contained in the square ${[-2\nu,2\nu]^2}$, and it remains to split the latter into ${16\nu^2}$ unit squares and translate the variables in each.

Further, a compact segment of an irreducible algebraic curve ${F(x,y)=0}$ of ${x}$-degree and ${y}$-degree ${\nu}$ splits into ${c(\nu)}$ compact segments of the type ${y=f(x)}$ or ${x=f(y)}$, where ${f}$ is a ${(\nu,\nu)}$-algebraic function. Applying to each of the latter estimate (4), we obtain the result.

(I thank all participants of the Groupe de travail “Géométrie diophantienne” in Bordeaux for their precious comments.)

Schwarz mean value theorem and lattice points on analytic curves (after Bombieri and Pila)

April 3, 2010

Let ${{\Gamma\subset {\mathbb R}^2}}$ be a compact segment of a plane real analytic transcendental curve. Bombieri and Pila (1989) proved that ${\Gamma}$ may not contain “many” rational points with a given denominator. Precisely: given ${{\epsilon>0}}$, there exists a constant ${{c=c(\Gamma, \epsilon)}}$ such that for any positive integer ${N}$

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right| \le cN^\epsilon.$

(As they remark, the same statement holds if ${\Gamma}$ is algebraic but does not admit polynomial parametrization: this is a rather easy consequence of the Mordell-Weil theorem.)

This theorem is instrumental in the recent novel proof, by Pila and Zannier (2008), of the Manin-Muford conjecture on torsion points on subvarieties of Abelian varieties.

The argument of Bombieri and Pila is based on the mean value theorem of H.A.Schwarz. It asserts that, given an interval ${I}$, a function ${{f\in C^n(I)}}$, and ${{n+1}}$ points ${{x_0, \ldots, x_n\in I}}$, there exists a point ${{\tau\in I}}$ such that

$\displaystyle \det \begin{bmatrix} 1&x_0&\ldots&x_0^{n-1}&f(x_0)\\ &&\ldots\\ 1&x_n&\ldots&x_n^{n-1}&f(x_n) \end{bmatrix}= \frac{f^{(n)}(\tau)}{n!}V(x_0, \ldots, x_n),$

where ${V(x_0, \ldots, x_n)}$ is the Vandermond determinant. The case ${{n=1}}$ is the Lagrange mean value theorem.

Dörge (1927) used this theorem to bound the number of integral points on finite segments of algebraic curves and deduce from this a very simple proof of Hilbert’s irreducibility theorem. The work of Dörge is reproduced in Lang’s Fundamentals of Diophantine Geometry (see Theorem 2.1 in Chapter 9), and I advice to read this piece (it is independent of the rest of the book). The argument of Bombieri and Pila is a very beautiful extension of Dörge’s idea.

The starting point of Bombieri and Pila’s argument is yet another “mean value theorem”. Let ${I}$ be an interval, ${{x_1, \ldots, x_n\in I}}$ and ${{f_1, \ldots, f_n\in C^{n-1}(I)}}$. Then

$\displaystyle \det \bigl[f_i(x_j)\bigr]= \det \left[\frac{f_i^{(j-1)}(\tau_{ij})}{j!}\right]V(x_1, \ldots, x_n)$

with some ${{\tau_{ij}\in I}}$. Let us prove this for ${{n=2}}$:

$\displaystyle \begin{vmatrix} f_1(x_1)&f_1(x_2)\\ f_2(x_1) & f_2(x_2) \end{vmatrix}= \begin{vmatrix} f_1(x_1)&f_1(x_2)-f_1(x_1)\\ f_2(x_1) & f_2(x_2)-f_2(x_1) \end{vmatrix} =\begin{vmatrix} f_1(\tau_{11})&f_1'(\tau_{12})\\ f_2(\tau_{21})&f_1'(\tau_{22}) \end{vmatrix} (x_2-x_1)$

by the Lagrange theorem. (We take ${{\tau_{11}=x_1}}$ and ${{\tau_{21}=x_2}}$.) The proof of the general case is pretty the same, but with Lagrange replaced by Schwarz.

If the interval ${I}$ is compact, we obtain the following consequence: there exists a constant ${C}$ (depending on the functions ${{f_1, \ldots, f_n}}$) such that for any ${{x_1, \ldots, x_n\in I}}$

$\displaystyle \Bigl|\det \bigl[f_i(x_j)\bigr]\Bigr|\le CV(x_1, \ldots, x_n)\le C \bigl(\max|x_i-x_j|\bigr)^{n(n-1)/2}. \ \ \ \ \ (1)$

Now fix a positive integer ${d}$. In the sequel by a ${d}$-curve we mean a plane algebraic curve ${{P(x,y)=0}}$ of degree less than ${d}$ in ${x}$ and in ${y}$. Then ${d^2}$ points ${{(x_1,y_1), \ldots, (x_{d^2}, y_{d^2})}}$ do not lie on a ${d}$-curve if and only if the determinant

$\displaystyle \Delta=\Delta \bigl((x_1,y_1), \ldots, (x_{d^2}, y_{d^2})\bigr)=\det \Bigl[x_k^iy_k^j\Bigr]_{\genfrac{}{}{0pt}{}{ 0\le i,j< d}{1\le k\le d^2}}$

is non-zero. (Here ${(i,j)}$ is the “vertical” index, and ${k}$ is the “horizontal” index.) If all the coordinates ${x_k}$ and ${y_k}$ are rational numbers with denominator ${N}$, then ${\Delta}$ is a non-zero rational number with denominator at most ${N^{d^2(d-1)}}$. We obtain the lower estimate

$\displaystyle |\Delta|\ge N^{-d^2(d-1)}.$

Now let ${f(x)}$ be a sufficiently smooth function on a compact interval ${I}$ and ${\Gamma}$ the plane curve ${{y=f(x)}}$. If all our points lie on ${\Gamma}$ then ${\Delta}$ can be expressed like ${\det \bigl[g_{ij}(x_k)\bigr]}$ with ${{g_{ij}(x)=x^if(x)^j}}$. Applying inequality (1) with the functions ${g_{ij}}$ instead of ${f_i}$, we obtain the following upper estimate:

$\displaystyle |\Delta|\le C \bigl(\max|x_i-x_j|\bigr)^{d^2(d^2-1)/2},$

where ${C}$ depends on ${f}$ and ${d}$. Thus, if our points

• have rational numbers with denominator ${N}$ as coordinates,
• lie on ${\Gamma}$, and
• do not lie on a ${d}$-curve,

then

$\displaystyle \max|x_i-x_j|\ge \kappa N^{-2/(d+1)}, \qquad \kappa=\kappa(f,d)>0.$

The same is true if we take more than ${d^2}$ points with these properties, because we can always select among them ${d^2}$ points not lying on a ${d}$-curve.

Splitting our interval into subintervals of length less than ${\kappa N^{-2/(d+1)}}$, we obtain the following statement (“the main lemma” of Bombieri and Pila):

the set ${\Gamma \cap (N^{-1}{\mathbb Z})^2}$ lies on ${O\bigl(N^{2/(d+1)}\bigr)}$   ${d}$-curves.

We are ready to prove the theorem of Bombieri and Pila. Let ${\Gamma}$ be a compact segment of a plane analytic transcendental curve. We may assume that ${\Gamma}$ is of the type ${y=f(x)}$. Also, a compactness argument shows that number of intersections of ${\Gamma}$ with any ${d}$-curve is bounded by a constant, depending on ${\Gamma}$ and ${d}$. It follows that for any ${d}$

$\displaystyle \left|\Gamma \cap (N^{-1}{\mathbb Z})^2\right| \le c(\Gamma, d) N^{2/(d+1)}.$

Selecting ${d}$ small enough, we complete the proof.

(I thank the participants of the Groupe de travail “Géométrie diophantienne” in Bordeaux for their precious comments.)