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

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.)