Arithmetic and Geometry, Bonn, April 2013

April 18, 2013

Today on the conference Florian Pop gave a wonderful, very inspirational and very enlightening talk on Rumely’s arithmetical capacity theory. I feel a strong desire to abandon all my current projects and start reading Rumely’s books. Last time I had such feeling when I learned the notion of o-minimality and read the book of van den Dries.

http://www.him.uni-bonn.de/programs/current-trimester-program/arithmetic-and-geometry/research-conference/schedule/#c4388

By the way, as Martin Widmer remarked during his recent talk in Bordeaux, o-minimality is a very clever way of formalizing the notion of “being non-pathological”.

Posted in Uncategorized | 5 Comments »

A mean value theorem

July 29, 2011

Christine Riedtmann asked me about the proof of the general mean value theorem mentioned in the very first entry of this blog. Let me recall the statement. In what follows {I} is an interval and {{x_0, \ldots, x_n}} are (pairwise distinct) points on {I}.

Theorem 1 Let {{f_0, \ldots, f_n}} be {n} times differentiable functions on {I}. Then

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

with some {{\tau_{ij}\in I}}.

Here {V(x_0, \ldots, x_n)} is the Vandermonde determinant.

The proof is based on the more special Schwarz mean value theorem, also mentioned in that entry. It is more convenient for us to state the Schwarz theorem as follows.

Theorem 2 (Schwarz) Let {f} be an {n} times differentiable function on {I}. Denote by {P(t)} the Lagrange interpolation polynomial for {f} at the points {{x_0, \ldots, x_n}} (the polynomial of degree at most~{n} taking value {f(x_j)} at {x_j} for {j=0,\ldots,n}.) Then for some {{\tau \in I}} we have {{f^{(n)}(\tau)=P^{(n)}(=P^{(n)}(\tau))}}.

In this form the Schwarz theorem is immediate: the “auxiliary function” {{f(t)-P(t)}} vanishes at {{x_0, \ldots, x_n}}, and by the Rolle theorem its {n}-th derivative vanishes somewhere on {I}.

To prove Theorem 1 we consider the interpolation polynomials {P_{ij}(t)} of {f_i} at {{x_0, \ldots, x_j}}. Let {{t_0, \ldots, t_n}} be independent indeterminates. Elementary transformations of determinants show that

\displaystyle \det\bigl[P_{ij}(t_j)\bigr] =\frac{\prod_{0\le k< \ell\le n}(t_\ell-x_k) }{V(x_0, \ldots, x_n)}\det\bigl[f_i(x_j)\bigr].

Applying to the both sides the differential operator

\displaystyle \frac{1}{0!1!\cdots n!}\,\frac{\partial^{0+1+\cdots+n}}{\partial t_0^0\partial t_1^1\cdots \partial t_n^n},

we obtain

\displaystyle \det \left[\frac{P_{ij}^{(j)}}{j!}\right]=\frac{1 }{V(x_0, \ldots, x_n)}\det\bigl[f_i(x_j)\bigr].

Now the Schwarz theorem implies that {{P_{ij}^{(j)}= f_i^{(j)}(\tau_{ij})}} with a suitably chosen {\tau_{ij}}.

Posted in Mathematics | Leave a Comment »

Equivalence of norms

June 17, 2011

It is well-known that all norms on a finite dimensional {{\mathbb R}}-vector space are equivalent: the proof is immediate, because the unit ball is compact. A similar argument works with {{\mathbb R}} replaced by any locally compact field. It is less known that the same is true over any complete field, without assuming local compactness. The compactness argument no longer works, but the proof is still not very difficult. However, the arguments I saw in the literature so far are somewhat bulky (see, for instance, Section 144 of van der Waerden’s “Algebra”).

Recently our master student Martin Djukanovic showed me a wonderful short proof of this statement. We argue by induction in the dimension. There is nothing to prove in dimension {1}. Now let {V} be an {m}-dimensional vector space over some complete field, {m>1}. We fix a basis {e_1,\ldots, e_m} of {V} and show that any norm {\|\cdot\|} on {V} is equivalent to the sup-norm {\|\cdot\|_\infty} with respect to this basis:

\displaystyle \|x_1e_1+\cdots+x_me_m\|_\infty = \max\{|x_1|, \ldots, |x_m|\}.

By induction, this holds in dimension {m-1}. In particular, in dimension {m-1} any normed space over a complete field is itself complete, because this is obviously true for the sup-norm.

For any {v\in V} we have {\|v\|\le C\|v\|_\infty} with {C=\|e_1\|+\cdots+\|e_m\|}. It remains to show that {\|v\|_\infty\le C\|v\|} with some other {C>0}. Assuming the contrary, we find an infinite sequence of non-zero vectors {v_n\in V} such that {\|v_n\|/\|v_n\|_\infty\rightarrow 0} as {n\rightarrow \infty}. Taking a subsequence, we may assume that the sup-norm of each {v_n} is attained at its {m}-th coordinate, and after re-scaling we may assume that the {m}-th coordinate (and thereby the sup-norm) of each {v_n} is {1}. Thus, each {v_n} can be written as {u_n+e}, where {u_n\in U=\langle e_1, \ldots, e_{m-1}\rangle} and {e=e_m}.

Since {\|v_n\|_\infty=1}, we have {\|v_n\|=\|u_n+e\|\rightarrow 0} as {n\rightarrow \infty}. Thus, the sequence {(u_n)} converges to {-e}. Hence it is a Cauchy sequence. But {U} is complete by the induction, which implies that {(u_n)} converges in {U}. We obtain {-e\in U}, a contradiction.

Posted in Mathematics | Leave a Comment »

radius-dimension symmetry for octahedra

June 20, 2010

Let {O(m,r)} be the number of integral points in the {m}-dimensional octahedron of radius {r}:

\displaystyle O(m,r)= \Bigl|\{(x_1,\ldots, x_m)\in {\mathbb Z}^m: |x_1|+\cdots+|x_m|\le r\}\Bigr|.

A standard combinatorial argument shows that for positive integers {m} and {n}

\displaystyle O(m,n)=\sum_{k=0}^{\min\{m,n\}} 2^k \binom mk \binom nk,

and, in particular,

\displaystyle O(m,n)=O(n,m). \ \ \ \ \ (1)

Is it possible to give a “geometric” interpretation (or any other “conceptual” interpretation) of identity (1)?

Update
A satisfactory answer was given by Allison and Mark Lewko, see the comments.

Posted in Mathematics | 2 Comments »

Liouville vs Cantor

June 14, 2010

I do not know who is the author of this bad joke, but it is appalling that even qualified mathematicians often say that Cantor’s proof of existence of transcendental numbers is non-constructive, as opposed to Liouville’s proof.

Let me recall that Liouville proved that the infinite sum {\sum 2^{-n!}} is transcendental, while Cantor proved that the set of algebraic numbers is countable, but the set of reals is uncountable.

Dear colleagues, Cantor’s proof is less “constructive” than Liuoville’s only on emotional or aesthetic level. Mathematically, both are equally constructive.

Indeed, the only way I can imagine of defining a real number “constructively” is providing an algorithm for computing rational approximations to it of any prescribed precision. More formally, call a real number {\alpha} constructible if there exists an algorithm (a Turing machine) which, having a natural number {n} at the input, produces at the output a rational approximation to {\alpha} with precision {1/n}. I do not know another reasonable (non-equivalent) definition of a constructible real number; if anybody knows, I would be happy if he shares it with me.

Of course, the Liouville number {\sum 2^{-n!}} is constructible, the good rational approximations being the partial sums of the infinite series.

Further, call a sequence {(\alpha_n)} constructible if there exists an algorithm, which, having natural {m} and {n} at the input, produces a rational approximation to {a_n} with precision {1/m} at the output.

Now two simple exercises.

  1. Show that there exists a constructible sequence containing all algebraic numbers.
  2. Show that for any constructible sequence, there exists a constructible number not contained in this sequence.

A careful examination of Cantor’s proof reveals that its first part solves the first exercise, and the second part solves the second exercise.

I would never waste time for recalling these trivialities in my precious blog if this misunderstanding were not so widespread even among professional mathematicians.

Posted in Mathematics | 6 Comments »

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

Posted in Mathematics | 2 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.)

Posted in Mathematics | 6 Comments »