Monthly Archive

You are currently browsing the monthly archive for August 2012.

The Lang-Weil bound

31 August, 2012 in expository, math.AG, math.NT | Tags: , , , , , | by | 19 comments

Let {F} be a finite field, with algebraic closure {\overline{F}}, and let {V} be an (affine) algebraic variety defined over {\overline{F}}, by which I mean a set of the form

\displaystyle V = \{ x \in \overline{F}^d: P_1(x) = \ldots = P_m(x) = 0 \}

for some ambient dimension {d \geq 0}, and some finite number of polynomials {P_1,\ldots,P_m: \overline{F}^d \rightarrow \overline{F}}. In order to reduce the number of subscripts later on, let us say that {V} has complexity at most {M} if {d}, {m}, and the degrees of the {P_1,\ldots,P_m} are all less than or equal to {M}. Note that we do not require at this stage that {V} be irreducible (i.e. not the union of two strictly smaller varieties), or defined over {F}, though we will often specialise to these cases later in this post. (Also, everything said here can also be applied with almost no changes to projective varieties, but we will stick with affine varieties for sake of concreteness.)

One can consider two crude measures of how “big” the variety {V} is. The first measure, which is algebraic geometric in nature, is the dimension {\hbox{dim}(V)} of the variety {V}, which is an integer between {0} and {d} (or, depending on convention, {-\infty}, {-1}, or undefined, if {V} is empty) that can be defined in a large number of ways (e.g. it is the largest {r} for which the generic linear projection from {V} to {\overline{F}^r} is dominant, or the smallest {r} for which the intersection with a generic codimension {r} subspace is non-empty). The second measure, which is number-theoretic in nature, is the number {|V(F)| = |V \cap F^d|} of {F}-points of {V}, i.e. points {x = (x_1,\ldots,x_d)} in {V} all of whose coefficients lie in the finite field, or equivalently the number of solutions to the system of equations {P_i(x_1,\ldots,x_d) = 0} for {i=1,\ldots,m} with variables {x_1,\ldots,x_d} in {F}.

These two measures are linked together in a number of ways. For instance, we have the basic Schwarz-Zippel type bound (which, in this qualitative form, goes back at least to Lemma 1 of the work of Lang and Weil in 1954).

Lemma 1 (Schwarz-Zippel type bound) Let {V} be a variety of complexity at most {M}. Then we have {|V(F)| \ll_M |F|^{\hbox{dim}(V)}}.

Proof: (Sketch) For the purposes of exposition, we will not carefully track the dependencies of implied constants on the complexity {M}, instead simply assuming that all of these quantities remain controlled throughout the argument. (If one wished, one could obtain ineffective bounds on these quantities by an ultralimit argument, as discussed in this previous post, or equivalently by moving everything over to a nonstandard analysis framework; one could also obtain such uniformity using the machinery of schemes.)

We argue by induction on the ambient dimension {d} of the variety {V}. The {d=0} case is trivial, so suppose {d \geq 1} and that the claim has already been proven for {d-1}. By breaking up {V} into irreducible components we may assume that {V} is irreducible (this requires some control on the number and complexity of these components, but this is available, as discussed in this previous post). For each {x_1,\ldots,x_{d-1} \in \overline{F}}, the fibre {\{ x_d \in \overline{F}: (x_1,\ldots,x_{d-1},x_d) \in V \}} is either one-dimensional (and thus all of {\overline{F}}) or zero-dimensional. In the latter case, one has {O_M(1)} points in the fibre from the fundamental theorem of algebra (indeed one has a bound of {D} in this case), and {(x_1,\ldots,x_{d-1})} lives in the projection of {V} to {\overline{F}^{d-1}}, which is a variety of dimension at most {\hbox{dim}(V)} and controlled complexity, so the contribution of this case is acceptable from the induction hypothesis. In the former case, the fibre contributes {|F|} {F}-points, but {(x_1,\ldots,x_{d-1})} lies in a variety in {\overline{F}^{d-1}} of dimension at most {\hbox{dim}(V)-1} (since otherwise {V} would contain a subvariety of dimension at least {\hbox{dim}(V)+1}, which is absurd) and controlled complexity, and so the contribution of this case is also acceptable from the induction hypothesis. \Box

One can improve the bound on the implied constant to be linear in the degree of {V} (see e.g. Claim 7.2 of this paper of Dvir, Kollar, and Lovett, or Lemma A.3 of this paper of Ellenberg, Oberlin, and myself), but we will not be concerned with these improvements here.

Without further hypotheses on {V}, the above upper bound is sharp (except for improvements in the implied constants). For instance, the variety

\displaystyle V := \{ (x_1,\ldots,x_d) \in \overline{F}^d: \prod_{j=1}^D (x_d - a_j) = 0\},

where {a_1,\ldots,a_D \in F} are distict, is the union of {D} distinct hyperplanes of dimension {d-1}, with {|V(F)| = D |F|^{d-1}} and complexity {\max(D,d)}; similar examples can easily be concocted for other choices of {\hbox{dim}(V)}. In the other direction, there is also no non-trivial lower bound for {|V(F)|} without further hypotheses on {V}. For a trivial example, if {a} is an element of {\overline{F}} that does not lie in {F}, then the hyperplane

\displaystyle V := \{ (x_1,\ldots,x_d) \in \overline{F}^d: x_d - a = 0 \}

clearly has no {F}-points whatsoever, despite being a {d-1}-dimensional variety in {\overline{F}^d} of complexity {d}. For a slightly less non-trivial example, if {a} is an element of {F} that is not a quadratic residue, then the variety

\displaystyle V := \{ (x_1,\ldots,x_d) \in \overline{F}^d: x_d^2 - a = 0 \},

which is the union of two hyperplanes, still has no {F}-points, even though this time the variety is defined over {F} instead of {\overline{F}} (by which we mean that the defining polynomial(s) have all of their coefficients in {F}). There is however the important Lang-Weil bound that allows for a much better estimate as long as {V} is both defined over {F} and irreducible:

Theorem 2 (Lang-Weil bound) Let {V} be a variety of complexity at most {M}. Assume that {V} is defined over {F}, and that {V} is irreducible as a variety over {\overline{F}} (i.e. {V} is geometrically irreducible or absolutely irreducible). Then

\displaystyle |V(F)| = (1 + O_M(|F|^{-1/2})) |F|^{\hbox{dim}(V)}.

Again, more explicit bounds on the implied constant here are known, but will not be the focus of this post. As the previous examples show, the hypotheses of definability over {F} and geometric irreducibility are both necessary.

The Lang-Weil bound is already non-trivial in the model case {d=2, \hbox{dim}(V)=1} of plane curves:

Theorem 3 (Hasse-Weil bound) Let {P: \overline{F}^2 \rightarrow \overline{F}} be an irreducible polynomial of degree {D} with coefficients in {F}. Then

\displaystyle |\{ (x,y) \in F^2: P(x,y) = 0 \}| = |F| + O_D( |F|^{1/2} ).

Thus, for instance, if {a,b \in F}, then the elliptic curve {\{ (x,y) \in F^2: y^2 = x^3 + ax + b \}} has {|F| + O(|F|^{1/2})} {F}-points, a result first established by Hasse. The Hasse-Weil bound is already quite non-trivial, being the analogue of the Riemann hypothesis for plane curves. For hyper-elliptic curves, an elementary proof (due to Stepanov) is discussed in this previous post. For general plane curves, the first proof was by Weil (leading to his famous Weil conjectures); there is also a nice version of Stepanov’s argument due to Bombieri covering this case which is a little less elementary (relying crucially on the Riemann-Roch theorem for the upper bound, and a lifting trick to then get the lower bound), which I briefly summarise later in this post. The full Lang-Weil bound is deduced from the Hasse-Weil bound by an induction argument using generic hyperplane slicing, as I will also summarise later in this post.

The hypotheses of definability over {F} and geometric irreducibility in the Lang-Weil can be removed after inserting a geometric factor:

Corollary 4 (Lang-Weil bound, alternate form) Let {V} be a variety of complexity at most {M}. Then one has

\displaystyle |V(F)| = (c(V) + O_M(|F|^{-1/2})) |F|^{\hbox{dim}(V)}

where {c(V)} is the number of top-dimensional components of {V} (i.e. geometrically irreducible components of {V} of dimension {\hbox{dim}(V)}) that are definable over {F}, or equivalently are invariant with respect to the Frobenius endomorphism {x \mapsto x^{|F|}} that defines {F}.

Proof: By breaking up a general variety {V} into components (and using Lemma 1 to dispose of any lower-dimensional components), it suffices to establish this claim when {V} is itself geometrically irreducible. If {V} is definable over {F}, the claim follows from Theorem 2. If {V} is not definable over {F}, then it is not fixed by the Frobenius endomorphism {Frob} (since otherwise one could produce a set of defining polynomials that were fixed by Frobenius and thus defined over {F} by using some canonical basis (such as a reduced Grobner basis) for the associated ideal), and so {V \cap Frob(V)} has strictly smaller dimension than {V}. But {V \cap Frob(V)} captures all the {F}-points of {V}, so in this case the claim follows from Lemma 1. \Box

Note that if {V} is reducible but is itself defined over {F}, then the Frobenius endomorphism preserves {V} itself, but may permute the components of {V} around. In this case, {c(V)} is the number of fixed points of this permutation action of Frobenius on the components. In particular, {c(V)} is always a natural number between {0} and {O_M(1)}; thus we see that regardless of the geometry of {V}, the normalised count {|V(F)|/|F|^{\hbox{dim}(V)}} is asymptotically restricted to a bounded range of natural numbers (in the regime where the complexity stays bounded and {|F|} goes to infinity).

Example 1 Consider the variety

\displaystyle V := \{ (x,y) \in \overline{F}^2: x^2 - ay^2 = 0 \}

for some non-zero parameter {a \in F}. Geometrically (by which we basically mean “when viewed over the algebraically closed field {\overline{F}}“), this is the union of two lines, with slopes corresponding to the two square roots of {a}. If {a} is a quadratic residue, then both of these lines are defined over {F}, and are fixed by Frobenius, and {c(V) = 2} in this case. If {a} is not a quadratic residue, then the lines are not defined over {F}, and the Frobenius automorphism permutes the two lines while preserving {V} as a whole, giving {c(V)=0} in this case.

Corollary 4 effectively computes (at least to leading order) the number-theoretic size {|V(F)|} of a variety in terms of geometric information about {V}, namely its dimension {\hbox{dim}(V)} and the number {c(V)} of top-dimensional components fixed by Frobenius. It turns out that with a little bit more effort, one can extend this connection to cover not just a single variety {V}, but a family of varieties indexed by points in some base space {W}. More precisely, suppose we now have two affine varieties {V,W} of bounded complexity, together with a regular map {\phi: V \rightarrow W} of bounded complexity (the definition of complexity of a regular map is a bit technical, see e.g. this paper, but one can think for instance of a polynomial or rational map of bounded degree as a good example). It will be convenient to assume that the base space {W} is irreducible. If the map {\phi} is a dominant map (i.e. the image {\phi(V)} is Zariski dense in {W}), then standard algebraic geometry results tell us that the fibres {\phi^{-1}(\{w\})} are an unramified family of {\hbox{dim}(V)-\hbox{dim}(W)}-dimensional varieties outside of an exceptional subset {W'} of {W} of dimension strictly smaller than {\hbox{dim}(W)} (and with {\phi^{-1}(W')} having dimension strictly smaller than {\hbox{dim}(V)}); see e.g. Section I.6.3 of Shafarevich.

Now suppose that {V}, {W}, and {\phi} are defined over {F}. Then, by Lang-Weil, {W(F)} has {(1 + O(|F|^{-1/2})) |F|^{\hbox{dim}(W)}} {F}-points, and by Schwarz-Zippel, for all but {O( |F|^{\hbox{dim}(W)-1})} of these {F}-points {w} (the ones that lie in the subvariety {W'}), the fibre {\phi^{-1}(\{w\})} is an algebraic variety defined over {F} of dimension {\hbox{dim}(V)-\hbox{dim}(W)}. By using ultraproduct arguments (see e.g. Lemma 3.7 of this paper of mine with Emmanuel Breuillard and Ben Green), this variety can be shown to have bounded complexity, and thus by Corollary 4, has {(c(\phi^{-1}(\{w\})) + O(|F|^{-1/2}) |F|^{\hbox{dim}(V)-\hbox{dim}(W)}} {F}-points. One can then ask how the quantity {c(\phi^{-1}(\{w\})} is distributed. A simple but illustrative example occurs when {V=W=F} and {\phi: F \rightarrow F} is the polynomial {\phi(x) := x^2}. Then {c(\phi^{-1}(\{w\})} equals {2} when {w} is a non-zero quadratic residue and {0} when {w} is a non-zero quadratic non-residue (and {1} when {w} is zero, but this is a negligible fraction of all {w}). In particular, in the asymptotic limit {|F| \rightarrow \infty}, {c(\phi^{-1}(\{w\})} is equal to {2} half of the time and {0} half of the time.

Now we describe the asymptotic distribution of the {c(\phi^{-1}(\{w\}))}. We need some additional notation. Let {w_0} be an {F}-point in {W \backslash W'}, and let {\pi_0( \phi^{-1}(\{w_0\}) )} be the connected components of the fibre {\phi^{-1}(\{w_0\})}. As {\phi^{-1}(\{w_0\})} is defined over {F}, this set of components is permuted by the Frobenius endomorphism {Frob}. But there is also an action by monodromy of the fundamental group {\pi_1(W \backslash W')} (this requires a certain amount of étale machinery to properly set up, as we are working over a positive characteristic field rather than over the complex numbers, but I am going to ignore this rather important detail here, as I still don’t fully understand it). This fundamental group may be infinite, but (by the étale construction) is always profinite, and in particular has a Haar probability measure, in which every finite index subgroup (and their cosets) are measurable. Thus we may meaningfully talk about elements drawn uniformly at random from this group, so long as we work only with the profinite {\sigma}-algebra on {\pi_1(W \backslash W')} that is generated by the cosets of the finite index subgroups of this group (which will be the only relevant sets we need to measure when considering the action of this group on finite sets, such as the components of a generic fibre).

Theorem 5 (Lang-Weil with parameters) Let {V, W} be varieties of complexity at most {M} with {W} irreducible, and let {\phi: V \rightarrow W} be a dominant map of complexity at most {M}. Let {w_0} be an {F}-point of {W \backslash W'}. Then, for any natural number {a}, one has {c(\phi^{-1}(\{w\})) = a} for {(\mathop{\bf P}( X = a ) + O_M(|F|^{-1/2})) |F|^{\hbox{dim}(W)}} values of {w \in W(F)}, where {X} is the random variable that counts the number of components of a generic fibre {\phi^{-1}(w_0)} that are invariant under {g \circ Frob}, where {g} is an element chosen uniformly at random from the étale fundamental group {\pi_1(W \backslash W')}. In particular, in the asymptotic limit {|F| \rightarrow \infty}, and with {w} chosen uniformly at random from {W(F)}, {c(\phi^{-1}(\{w\}))} (or, equivalently, {|\phi^{-1}(\{w\})(F)| / |F|^{\hbox{dim}(V)-\hbox{dim}(W)}}) and {X} have the same asymptotic distribution.

This theorem generalises Corollary 4 (which is the case when {W} is just a point, so that {\phi^{-1}(\{w\})} is just {V} and {g} is trivial). Informally, the effect of a non-trivial parameter space {W} on the Lang-Weil bound is to push around the Frobenius map by monodromy for the purposes of counting invariant components, and a randomly chosen set of parameters corresponds to a randomly chosen loop on which to perform monodromy.

Example 2 Let {V=W=F} and {\phi(x) = x^m} for some fixed {m \geq 1}; to avoid some technical issues let us suppose that {m} is coprime to {|F|}. Then {W'} can be taken to be {\{0\}}, and for a base point {w_0 \in W \backslash W'} we can take {w_0=1}. The fibre {\phi^{-1}(\{1\})} – the {m^{th}} roots of unity – can be identified with the cyclic group {{\bf Z}/m{\bf Z}} by using a primitive root of unity. The étale fundamental group {\pi(W \backslash W') = \pi(\overline{F} \backslash 0)} is (I think) isomorphic to the profinite closure {\hat {\bf Z}} of the integers {{\bf Z}} (excluding the part of that closure coming from the characteristic of {F}). Not coincidentally, the integers {{\bf Z}} are the fundamental group of the complex analogue {{\bf C} \backslash \{0\}} of {W \backslash W'}. (Brian Conrad points out to me though that for more complicated varieties, such as covers of {\overline{F} \backslash \{0\}} by a power of the characteristic, the etale fundamental group is more complicated than just a profinite closure of the ordinary fundamental group, due to the presence of Artin-Schreier covers that are only ramified at infinity.) The action of this fundamental group on the fibres {{\bf Z}/m{\bf Z}} can given by translation. Meanwhile, the Frobenius map {Frob} on {{\bf Z}/m{\bf Z}} is given by multiplication by {|F|}. A random element {g \circ Frob} then becomes a random affine map {x \mapsto |F|x+b} on {{\bf Z}/m{\bf Z}}, where {b} chosen uniformly at random from {{\bf Z}/m{\bf Z}}. The number of fixed points of this map is equal to the greatest common divisor {(|F|-1,m)} of {|F|-1} and {m} when {b} is divisible by {(|F|-1,m)}, and equal to {0} otherwise. This matches up with the elementary number fact that a randomly chosen non-zero element of {F} will be an {m^{th}} power with probability {1/(|F|-1,m)}, and when this occurs, the number of {m^{th}} roots in {F} will be {(|F|-1,m)}.

Example 3 (Thanks to Jordan Ellenberg for this example.) Consider a random elliptic curve {E = \{ y^2 = x^3 + ax + b \}}, where {a,b} are chosen uniformly at random, and let {m \geq 1}. Let {E[m]} be the {m}-torsion points of {E} (i.e. those elements {g \in E} with {mg = 0} using the elliptic curve addition law); as a group, this is isomorphic to {{\bf Z}/m{\bf Z} \times {\bf Z}/m{\bf Z}} (assuming that {F} has sufficiently large characteristic, for simplicity), and consider the number of {F} points of {E[m]}, which is a random variable taking values in the natural numbers between {0} and {m^2}. In this case, the base variety {W} is the modular curve {X(1)}, and the covering variety {V} is the modular curve {X_1(m)}. The generic fibre here can be identified with {{\bf Z}/m{\bf Z} \times {\bf Z}/m{\bf Z}}, the monodromy action projects down to the action of {SL_2({\bf Z}/m{\bf Z})}, and the action of Frobenius on this fibre can be shown to be given by a {2 \times 2} matrix with determinant {|F|} (with the exact choice of matrix depending on the choice of fibre and of the identification), so the distribution of the number of {F}-points of {E[m]} is asymptotic to the distribution of the number of fixed points {X} of a random linear map of determinant {|F|} on {{\bf Z}/m{\bf Z} \times {\bf Z}/m{\bf Z}}.

Theorem 5 seems to be well known “folklore” among arithmetic geometers, though I do not know of an explicit reference for it. I enjoyed deriving it for myself (though my derivation is somewhat incomplete due to my lack of understanding of étale cohomology) from the ordinary Lang-Weil theorem and the moment method. I’m recording this derivation later in this post, mostly for my own benefit (as I am still in the process of learning this material), though perhaps some other readers may also be interested in it.

Caveat: not all details are fully fleshed out in this writeup, particularly those involving the finer points of algebraic geometry and étale cohomology, as my understanding of these topics is not as complete as I would like it to be.

Many thanks to Brian Conrad and Jordan Ellenberg for helpful discussions on these topics.

Read the rest of this entry »

On sets defining few ordinary lines

24 August, 2012 in math.CO, paper | Tags: , , , | by | 17 comments

Ben Green and I have just uploaded to the arXiv our new paper “On sets defining few ordinary lines“, submitted to Discrete and Computational Geometry. This paper asymptotically solves two old questions concerning finite configurations of points {P} in the plane {{\mathbb R}^2}. Given a set {P} of {n} points in the plane, define an ordinary line to be a line containing exactly two points of {P}. The classical Sylvester-Gallai theorem, first posed as a problem by Sylvester in 1893, asserts that as long as the points of {P} are not all collinear, {P} defines at least one ordinary line:

It is then natural to pose the question of what is the minimal number of ordinary lines that a set of {n} non-collinear points can generate. In 1940, Melchior gave an elegant proof of the Sylvester-Gallai theorem based on projective duality and Euler’s formula {V-E+F=2}, showing that at least three ordinary lines must be created; in 1951, Motzkin showed that there must be {\gg n^{1/2}} ordinary lines. Previously to this paper, the best lower bound was by Csima and Sawyer, who in 1993 showed that there are at least {6n/13} ordinary lines. In the converse direction, if {n} is even, then by considering {n/2} equally spaced points on a circle, and {n/2} points on the line at infinity in equally spaced directions, one can find a configuration of {n} points that define just {n/2} ordinary lines.

As first observed by Böröczky, variants of this example also give few ordinary lines for odd {n}, though not quite as few as {n/2}; more precisely, when {n=1 \hbox{ mod } 4} one can find a configuration with {3(n-1)/4} ordinary lines, and when {n = 3 \hbox{ mod } 4} one can find a configuration with {3(n-3)/4} ordinary lines. Our first main result is that these configurations are best possible for sufficiently large {n}:

Theorem 1 (Dirac-Motzkin conjecture) If {n} is sufficiently large, then any set of {n} non-collinear points in the plane will define at least {\lfloor n/2\rfloor} ordinary lines. Furthermore, if {n} is odd, at least {3\lfloor n/4\rfloor} ordinary lines must be created.

The Dirac-Motzkin conjecture asserts that the first part of this theorem in fact holds for all {n}, not just for sufficiently large {n}; in principle, our theorem reduces that conjecture to a finite verification, although our bound for “sufficiently large” is far too poor to actually make this feasible (it is of double exponential type). (There are two known configurations for which one has {(n-1)/2} ordinary lines, one with {n=7} (discovered by Kelly and Moser), and one with {n=13} (discovered by Crowe and McKee).)

Our second main result concerns not the ordinary lines, but rather the {3}-rich lines of an {n}-point set – a line that meets exactly three points of that set. A simple double counting argument (counting pairs of distinct points in the set in two different ways) shows that there are at most

\displaystyle \binom{n}{2} / \binom{3}{2} = \frac{1}{6} n^2 - \frac{1}{6} n

{3}-rich lines. On the other hand, on an elliptic curve, three distinct points P,Q,R on that curve are collinear precisely when they sum to zero with respect to the group law on that curve. Thus (as observed first by Sylvester in 1868), any finite subgroup of an elliptic curve (of which one can produce numerous examples, as elliptic curves in {{\mathbb R}^2} have the group structure of either {{\mathbb R}/{\mathbb Z}} or {{\mathbb R}/{\mathbb Z} \times ({\mathbb Z}/2{\mathbb Z})}) can provide examples of {n}-point sets with a large number of {3}-rich lines ({\lfloor \frac{1}{6} n^2 - \frac{1}{2} n + 1\rfloor}, to be precise). One can also shift such a finite subgroup by a third root of unity and obtain a similar example with only one fewer {3}-rich line. Sylvester then formally posed the question of determining whether this was best possible.

This problem was known as the Orchard planting problem, and was given a more poetic formulation as such by Jackson in 1821 (nearly fifty years prior to Sylvester!):

Our second main result answers this problem affirmatively in the large {n} case:

Theorem 2 (Orchard planting problem) If {n} is sufficiently large, then any set of {n} points in the plane will determine at most {\lfloor \frac{1}{6} n^2 - \frac{1}{2} n + 1\rfloor} {3}-rich lines.

Again, our threshold for “sufficiently large” for this {n} is extremely large (though slightly less large than in the previous theorem), and so a full solution of the problem, while in principle reduced to a finitary computation, remains infeasible at present.

Our results also classify the extremisers (and near extremisers) for both of these problems; basically, the known examples mentioned previously are (up to projective transformation) the only extremisers when {n} is sufficiently large.

Our proof strategy follows the “inverse theorem method” from additive combinatorics. Namely, rather than try to prove direct theorems such as lower bounds on the number of ordinary lines, or upper bounds on the number of {3}-rich lines, we instead try to prove inverse theorems (also known as structure theorems), in which one attempts a structural classification of all configurations with very few ordinary lines (or very many {3}-rich lines). In principle, once one has a sufficiently explicit structural description of these sets, one simply has to compute the precise number of ordinary lines or {3}-rich lines in each configuration in the list provided by that structural description in order to obtain results such as the two theorems above.

Note from double counting that sets with many {3}-rich lines will necessarily have few ordinary lines. Indeed, if we let {N_k} denote the set of lines that meet exactly {k} points of an {n}-point configuration, so that {N_3} is the number of {3}-rich lines and {N_2} is the number of ordinary lines, then we have the double counting identity

\displaystyle \sum_{k=2}^n \binom{k}{2} N_k = \binom{n}{2}

which among other things implies that any counterexample to the orchard problem can have at most {n+O(1)} ordinary lines. In particular, any structural theorem that lets us understand configurations with {O(n)} ordinary lines will, in principle, allow us to obtain results such as the above two theorems.

As it turns out, we do eventually obtain a structure theorem that is strong enough to achieve these aims, but it is difficult to prove this theorem directly. Instead we proceed more iteratively, beginning with a “cheap” structure theorem that is relatively easy to prove but provides only a partial amount of control on the configurations with {O(n)} ordinary lines. One then builds upon that theorem with additional arguments to obtain an “intermediate” structure theorem that gives better control, then a “weak” structure theorem that gives even more control, a “strong” structure theorem that gives yet more control, and then finally a “very strong” structure theorem that gives an almost complete description of the configurations (but only in the asymptotic regime when {n} is very large). It turns out that the “weak” theorem is enough for the orchard planting problem, and the “strong” version is enough for the Dirac-Motzkin conjecture. (So the “very strong” structure theorem ends up being unnecessary for the two applications given, but may be of interest for other applications.) Note that the stronger theorems do not completely supercede the weaker ones, because the quantitative bounds in the theorems get progressively worse as the control gets stronger.

Before we state these structure theorems, note that all the examples mentioned previously of sets with few ordinary lines involved cubic curves: either irreducible examples such as elliptic curves, or reducible examples such as the union of a circle (or more generally, a conic section) and a line. (We also allow singular cubic curves, such as the union of a conic section and a tangent line, or a singular irreducible curve such as {\{ (x,y): y^2 = x^3 \}}.) This turns out to be no coincidence; cubic curves happen to be very good at providing many {3}-rich lines (and thus, few ordinary lines), and conversely it turns out that they are essentially the only way to produce such lines. This can already be evidenced by our cheap structure theorem:

Theorem 3 (Cheap structure theorem) Let {P} be a configuration of {n} points with at most {{}Kn} ordinary lines for some {K \geq 1}. Then {P} can be covered by at most {500K} cubic curves.

This theorem is already a non-trivial amount of control on sets with few ordinary lines, but because the result does not specify the nature of these curves, and how they interact with each other, it does not seem to be directly useful for applications. The intermediate structure theorem given below gives a more precise amount of control on these curves (essentially guaranteeing that all but at most one of the curve components are lines):

Theorem 4 (Intermediate structure theorem) Let {P} be a configuration of {n} points with at most {{}Kn} ordinary lines for some {K \geq 1}. Then one of the following is true:

  1. {P} lies on the union of an irreducible cubic curve and an additional {O(K^{O(1)})} points.
  2. {P} lies on the union of an irreducible conic section and an additional {O(K^{O(1)})} lines, with {n/2 + O(K^{O(1)})} of the points on {P} in either of the two components.
  3. {P} lies on the union of {O(K)} lines and an additional {O(K^{O(1)})} points.

By some additional arguments (including a very nice argument supplied to us by Luke Alexander Betts, an undergraduate at Cambridge, which replaces a much more complicated (and weaker) argument we originally had for this paper), one can cut down the number of lines in the above theorem to just one, giving a more useful structure theorem, at least when {n} is large:

Theorem 5 (Weak structure theorem) Let {P} be a configuration of {n} points with at most {{}Kn} ordinary lines for some {K \geq 1}. Assume that {n \geq \exp(\exp(CK^C))} for some sufficiently large absolute constant {C}. Then one of the following is true:

  1. {P} lies on the union of an irreducible cubic curve and an additional {O(K^{O(1)})} points.
  2. {P} lies on the union of an irreducible conic section, a line, and an additional {O(K^{O(1)})} points, with {n/2 + O(K^{O(1)})} of the points on {P} in either of the first two components.
  3. {P} lies on the union of a single line and an additional {O(K^{O(1)})} points.

As mentioned earlier, this theorem is already strong enough to resolve the orchard planting problem for large {n}. The presence of the double exponential here is extremely annoying, and is the main reason why the final thresholds for “sufficiently large” in our results are excessively large, but our methods seem to be unable to eliminate these exponentials from our bounds (though they can fortunately be confined to a lower bound for {n}, keeping the other bounds in the theorem polynomial in {K}).

For the Dirac-Motzkin conjecture one needs more precise control on the portion of {P} on the various low-degree curves indicated. This is given by the following result:

Theorem 6 (Strong structure theorem) Let {P} be a configuration of {n} points with at most {{}Kn} ordinary lines for some {K \geq 1}. Assume that {n \geq \exp(\exp(CK^C))} for some sufficiently large absolute constant {C}. Then, after adding or deleting {O(K^{O(1)})} points from {P} if necessary (modifying {n} appropriately), and then applying a projective transformation, one of the following is true:

  1. {P} is a finite subgroup of an elliptic curve (EDIT: as pointed out in comments, one also needs to allow for finite subgroups of acnodal singular cubic curves), possibly shifted by a third root of unity.
  2. {P} is the Borozcky example mentioned previously (the union of {n/2} equally spaced points on the circle, and {n/2} points on the line at infinity).
  3. {P} lies on a single line.

By applying a final “cleanup” we can replace the {O(K^{O(1)})} in the above theorem with the optimal {O(K)}, which is our “very strong” structure theorem. But the strong structure theorem is already sufficient to establish the Dirac-Motzkin conjecture for large {n}.

There are many tools that go into proving these theorems, some of which are extremely classical (with at least one going back to the ancient Greeks), and others being more recent. I will discuss some (not all) of these tools below the fold, and more specifically:

  1. Melchior’s argument, based on projective duality and Euler’s formula, initially used to prove the Sylvester-Gallai theorem;
  2. Chasles’ version of the Cayley-Bacharach theorem, which can convert dual triangular grids (produced by Melchior’s argument) into cubic curves that meet many points of the original configuration {P});
  3. Menelaus’s theorem, which is useful for producing ordinary lines when the point configuration lies on a few non-concurrent lines, particularly when combined with a sum-product estimate of Elekes, Nathanson, and Ruzsa;
  4. Betts’ argument, that produces ordinary lines when the point configuration lies on a few concurrent lines;
  5. A result of Poonen and Rubinstein that any point not on the origin or unit circle can lie on at most seven chords connecting roots of unity; this, together with a variant for elliptic curves, gives the very strong structure theorem, and is also (a strong version of) what is needed to finish off the Dirac-Motzkin and orchard planting problems from the structure theorems given above.

There are also a number of more standard tools from arithmetic combinatorics (e.g. a version of the Balog-Szemeredi-Gowers lemma) which are needed to tie things together at various junctures, but I won’t say more about these methods here as they are (by now) relatively routine.

Read the rest of this entry »

Bill Thurston

22 August, 2012 in math.GT, math.HO, obituary | Tags: , , , | by | 37 comments

Bill Thurston, who made fundamental contributions to our understanding of low-dimensional manifolds and related structures, died on Tuesday, aged 65.

Perhaps Thurston’s best known achievement is the proof of the hyperbolisation theorem for Haken manifolds, which showed that 3-manifolds which obeyed a certain number of topological conditions, could always be given a hyperbolic geometry (i.e. a Riemannian metric that made the manifold isometric to a quotient of the hyperbolic 3-space H^3).  This difficult theorem connecting the topological and geometric structure of 3-manifolds led Thurston to give his influential geometrisation conjecture, which (in principle, at least) completely classifies the topology of an arbitrary compact 3-manifold as a combination of eight model geometries (now known as Thurston model geometries).  This conjecture has many consequences, including Thurston’s hyperbolisation theorem and (most famously) the Poincaré conjecture.  Indeed, by placing that conjecture in the context of a conceptually appealing general framework, of which many other cases could already be verified, Thurston provided one of the strongest pieces of evidence towards the truth of the Poincaré conjecture, until the work of Grisha Perelman in 2002-2003 proved both the Poincaré conjecture and the geometrisation conjecture by developing Hamilton’s Ricci flow methods.  (There are now several variants of Perelman’s proof of both conjectures; in the proof of geometrisation by Bessieres, Besson, Boileau, Maillot, and Porti, Thurston’s hyperbolisation theorem is a crucial ingredient, allowing one to bypass the need for the theory of Alexandrov spaces in a key step in Perelman’s argument.)

One of my favourite results of Thurston’s is his elegant method for everting the sphere (smoothly turning a sphere S^2 in {\bf R}^3 inside out without any folds or singularities).  The fact that sphere eversion can be achieved at all is highly unintuitive, and is often referred to as Smale’s paradox, as Stephen Smale was the first to give a proof that such an eversion exists.  However, prior to Thurston’s method, the known constructions for sphere eversion were quite complicated.  Thurston’s method, relying on corrugating and then twisting the sphere, is sufficiently conceptual and geometric that it can in fact be explained quite effectively in non-technical terms, as was done in the following excellent video entitled “Outside In“, and produced by the Geometry Center:

In addition to his direct mathematical research contributions, Thurston was also an amazing mathematical expositor, having the rare knack of being able to describe the process of mathematical thinking in addition to the results of that process and the intuition underlying it.  His wonderful essay “On proof and progress in mathematics“, which I highly recommend, is the quintessential instance of this; more recent examples include his many insightful questions and answers on MathOverflow.

I unfortunately never had the opportunity to meet Thurston in person (although we did correspond a few times online), but I know many mathematicians who have been profoundly influenced by him and his work.  His death is a great loss for mathematics.

Archives