Ruling out polynomial bijections over the rationals via Bombieri-Lang?

I recently came across this question on MathOverflow asking if there are any polynomials of two variables with rational coefficients, such that the map is a bijection. The answer to this question is almost surely “no”, but it is remarkable how hard this problem resists any attempt at rigorous proof. (MathOverflow users with enough privileges to see deleted answers will find that there are no fewer than seventeen deleted attempts at a proof in response to this question!)

On the other hand, the one surviving response to the question does point out this paper of Poonen which shows that assuming a powerful conjecture in Diophantine geometry known as the Bombieri-Lang conjecture (discussed in this previous post), it is at least possible to exhibit polynomials which are injective.

I believe that it should be possible to also rule out the existence of bijective polynomials if one assumes the Bombieri-Lang conjecture, and have sketched out a strategy to do so, but filling in the gaps requires a fair bit more algebraic geometry than I am capable of. So as a sort of experiment, I would like to see if a rigorous implication of this form (similarly to the rigorous implication of the Erdos-Ulam conjecture from the Bombieri-Lang conjecture in my previous post) can be crowdsourced, in the spirit of the polymath projects (though I feel that this particular problem should be significantly quicker to resolve than a typical such project).

Here is how I imagine a Bombieri-Lang-powered resolution of this question should proceed (modulo a large number of unjustified and somewhat vague steps that I believe to be true but have not established rigorously). Suppose for contradiction that we have a bijective polynomial . Then for any polynomial of one variable, the surface

has infinitely many rational points; indeed, every rational lifts to exactly one rational point in . I believe that for “typical” this surface should be irreducible. One can now split into two cases:

• (a) The rational points in are Zariski dense in .
• (b) The rational points in are not Zariski dense in .

Consider case (b) first. By definition, this case asserts that the rational points in are contained in a finite number of algebraic curves. By Faltings’ theorem (a special case of the Bombieri-Lang conjecture), any curve of genus two or higher only contains a finite number of rational points. So all but finitely many of the rational points in are contained in a finite union of genus zero and genus one curves. I think all genus zero curves are birational to a line, and all the genus one curves are birational to an elliptic curve (though I don’t have an immediate reference for this). These curves all can have an infinity of rational points, but very few of them should have “enough” rational points that their projection to the third coordinate is “large”. In particular, I believe

• (i) If is birational to an elliptic curve, then the number of elements of of height at most should grow at most polylogarithmically in (i.e., be of order .
• (ii) If is birational to a line but not of the form for some rational , then then the number of elements of of height at most should grow slower than (in fact I think it can only grow like ).

I do not have proofs of these results (though I think something similar to (i) can be found in Knapp’s book, and (ii) should basically follow by using a rational parameterisation of with nonlinear). Assuming these assertions, this would mean that there is a curve of the form that captures a “positive fraction” of the rational points of , as measured by restricting the height of the third coordinate to lie below a large threshold , computing density, and sending to infinity (taking a limit superior). I believe this forces an identity of the form

for all . Such identities are certainly possible for some choices of (e.g. for arbitrary polynomials of one variable) but I believe that the only way that such identities hold for a “positive fraction” of (as measured using height as before) is if there is in fact a rational identity of the form

for some rational functions with rational coefficients (in which case we would have and ). But such an identity would contradict the hypothesis that is bijective, since one can take a rational point outside of the curve , and set , in which case we have violating the injective nature of . Thus, modulo a lot of steps that have not been fully justified, we have ruled out the scenario in which case (b) holds for a “positive fraction” of .

This leaves the scenario in which case (a) holds for a “positive fraction” of . Assuming the Bombieri-Lang conjecture, this implies that for such , any resolution of singularities of fails to be of general type. I would imagine that this places some very strong constraints on , since I would expect the equation to describe a surface of general type for “generic” choices of (after resolving singularities). However, I do not have a good set of techniques for detecting whether a given surface is of general type or not. Presumably one should proceed by viewing the surface as a fibre product of the simpler surface and the curve over the line . In any event, I believe the way to handle (a) is to show that the failure of general type of implies some strong algebraic constraint between and (something in the spirit of (1), perhaps), and then use this constraint to rule out the bijectivity of by some further ad hoc method.

Prismatic cohomology

Last week, we had Peter Scholze give an interesting distinguished lecture series here at UCLA on “Prismatic Cohomology”, which is a new type of cohomology theory worked out by Scholze and Bhargav Bhatt. (Video of the talks will be available shortly; for now we have some notes taken by two note–takers in the audience on that web page.) My understanding of this (speaking as someone that is rather far removed from this area) is that it is progress towards the “motivic” dream of being able to define cohomology for varieties (or similar objects) defined over arbitrary commutative rings , and with coefficients in another arbitrary commutative ring . Currently, we have various flavours of cohomology that only work for certain types of domain rings and coefficient rings :

• Singular cohomology, which roughly speaking works when the domain ring is a characteristic zero field such as or , but can allow for arbitrary coefficients ;
• de Rham cohomology, which roughly speaking works as long as the coefficient ring is the same as the domain ring (or a homomorphic image thereof), as one can only talk about -valued differential forms if the underlying space is also defined over ;
• -adic cohomology, which is a remarkably powerful application of étale cohomology, but only works well when the coefficient ring is localised around a prime that is different from the characteristic of the domain ring ; and
• Crystalline cohomology, in which the domain ring is a field of some finite characteristic , but the coefficient ring can be a slight deformation of , such as the ring of Witt vectors of .

There are various relationships between the cohomology theories, for instance de Rham cohomology coincides with singular cohomology for smooth varieties in the limiting case . The following picture Scholze drew in his first lecture captures these sorts of relationships nicely:

The new prismatic cohomology of Bhatt and Scholze unifies many of these cohomologies in the “neighbourhood” of the point in the above diagram, in which the domain ring and the coefficient ring are both thought of as being “close to characteristic ” in some sense, so that the dilates of these rings is either zero, or “small”. For instance, the -adic ring is technically of characteristic , but is a “small” ideal of (it consists of those elements of of -adic valuation at most ), so one can think of as being “close to characteristic ” in some sense. Scholze drew a “zoomed in” version of the previous diagram to informally describe the types of rings for which prismatic cohomology is effective:

To define prismatic cohomology rings one needs a “prism”: a ring homomorphism from to equipped with a “Frobenius-like” endomorphism on obeying some axioms. By tuning these homomorphisms one can recover existing cohomology theories like crystalline or de Rham cohomology as special cases of prismatic cohomology. These specialisations are analogous to how a prism splits white light into various individual colours, giving rise to the terminology “prismatic”, and depicted by this further diagram of Scholze:

(And yes, Peter confirmed that he and Bhargav were inspired by the Dark Side of the Moon album cover in selecting the terminology.)

There was an abstract definition of prismatic cohomology (as being the essentially unique cohomology arising from prisms that obeyed certain natural axioms), but there was also a more concrete way to view them in terms of coordinates, as a “-deformation” of de Rham cohomology. Whereas in de Rham cohomology one worked with derivative operators that for instance applied to monomials by the usual formula

prismatic cohomology in coordinates can be computed using a “-derivative” operator that for instance applies to monomials by the formula

where

is the “-analogue” of (a polynomial in that equals in the limit ). (The -analogues become more complicated for more general forms than these.) In this more concrete setting, the fact that prismatic cohomology is independent of the choice of coordinates apparently becomes quite a non-trivial theorem.

 

Trying to understand the Galois correspondence

Let be a field, and let be a finite extension of that field; in this post we will denote such a relationship by . We say that is a Galois extension of if the cardinality of the automorphism group of fixing is as large as it can be, namely the degree of the extension. In that case, we call the Galois group of over and denote it also by . The fundamental theorem of Galois theory then gives a one-to-one correspondence (also known as the Galois correspondence) between the intermediate extensions between and and the subgroups of :

Theorem 1 (Fundamental theorem of Galois theory) Let be a Galois extension of .

• (i) If is an intermediate field betwen and , then is a Galois extension of , and is a subgroup of .
• (ii) Conversely, if is a subgroup of , then there is a unique intermediate field such that ; namely is the set of elements of that are fixed by .
• (iii) If and , then if and only if is a subgroup of .
• (iv) If is an intermediate field between and , then is a Galois extension of if and only if is a normal subgroup of . In that case, is isomorphic to the quotient group .

Example 2 Let , and let be the degree Galois extension formed by adjoining a primitive root of unity (that is to say, is the cyclotomic field of order ). Then is isomorphic to the multiplicative cyclic group (the invertible elements of the ring ). Amongst the intermediate fields, one has the cyclotomic fields of the form where divides ; they are also Galois extensions, with isomorphic to and isomorphic to the elements of such that modulo . (There can also be other intermediate fields, corresponding to other subgroups of .)

Example 3 Let be the field of rational functions of one indeterminate with complex coefficients, and let be the field formed by adjoining an root to , thus . Then is a degree Galois extension of with Galois group isomorphic to (with an element corresponding to the field automorphism of that sends to ). The intermediate fields are of the form where divides ; they are also Galois extensions, with isomorphic to and isomorphic to the multiples of in .

There is an analogous Galois correspondence in the covering theory of manifolds. For simplicity we restrict attention to finite covers. If is a connected manifold and is a finite covering map of by another connected manifold , we denote this relationship by . (Later on we will change our function notations slightly and write in place of the more traditional , and similarly for the deck transformations below; more on this below the fold.) If , we can define to be the group of deck transformations: continuous maps which preserve the fibres of . We say that this covering map is a Galois cover if the cardinality of the group is as large as it can be. In that case we call the Galois group of over and denote it by .

Suppose is a finite cover of . An intermediate cover between and is a cover of by , such that , in such a way that the covering maps are compatible, in the sense that is the composition of and . This sort of compatibilty condition will be implicitly assumed whenever we chain together multiple instances of the notation. Two intermediate covers are equivalent if they cover each other, in a fashion compatible with all the other covering maps, thus and . We then have the analogous Galois correspondence:

Theorem 4 (Fundamental theorem of covering spaces) Let be a Galois covering.

• (i) If is an intermediate cover betwen and , then is a Galois extension of , and is a subgroup of .
• (ii) Conversely, if is a subgroup of , then there is a intermediate cover , unique up to equivalence, such that .
• (iii) If and , then if and only if is a subgroup of .
• (iv) If , then is a Galois cover of if and only if is a normal subgroup of . In that case, is isomorphic to the quotient group .

Example 5 Let , and let be the -fold cover of with covering map . Then is a Galois cover of , and is isomorphic to the cyclic group . The intermediate covers are (up to equivalence) of the form with covering map where divides ; they are also Galois covers, with isomorphic to and isomorphic to the multiples of in .

Given the strong similarity between the two theorems, it is natural to ask if there is some more concrete connection between Galois theory and the theory of finite covers.

In one direction, if the manifolds have an algebraic structure (or a complex structure), then one can relate covering spaces to field extensions by considering the field of rational functions (or meromorphic functions) on the space. For instance, if and is the coordinate on , one can consider the field of rational functions on ; the -fold cover with coordinate from Example 5 similarly has a field of rational functions. The covering relates the two coordinates by the relation , at which point one sees that the rational functions on are a degree extension of that of (formed by adjoining the root of unity to ). In this way we see that Example 5 is in fact closely related to Example 3.

Exercise 6 What happens if one uses meromorphic functions in place of rational functions in the above example? (To answer this question, I found it convenient to use a discrete Fourier transform associated to the multiplicative action of the roots of unity on to decompose the meromorphic functions on as a linear combination of functions invariant under this action, times a power of the coordinate for .)

I was curious however about the reverse direction. Starting with some field extensions , is it is possible to create manifold like spaces associated to these fields in such a fashion that (say) behaves like a “covering space” to with a group of deck transformations isomorphic to , so that the Galois correspondences agree? Also, given how the notion of a path (and associated concepts such as loops, monodromy and the fundamental group) play a prominent role in the theory of covering spaces, can spaces such as or also come with a notion of a path that is somehow compatible with the Galois correspondence?

The standard answer from modern algebraic geometry (as articulated for instance in this nice MathOverflow answer by Minhyong Kim) is to set equal to the spectrum of the field . As a set, the spectrum of a commutative ring is defined as the set of prime ideals of . Generally speaking, the map that maps a commutative ring to its spectrum tends to act like an inverse of the operation that maps a space to a ring of functions on that space. For instance, if one considers the commutative ring of regular functions on , then each point in gives rise to the prime ideal , and one can check that these are the only such prime ideals (other than the zero ideal ), giving an almost one-to-one correspondence between and . (The zero ideal corresponds instead to the generic point of .)

Of course, the spectrum of a field such as is just a point, as the zero ideal is the only prime ideal. Naively, it would then seem that there is not enough space inside such a point to support a rich enough structure of paths to recover the Galois theory of this field. In modern algebraic geometry, one addresses this issue by considering not just the set-theoretic elements of , but more general “base points” that map from some other (affine) scheme to (one could also consider non-affine base points of course). One has to rework many of the fundamentals of the subject to accommodate this “relative point of view“, for instance replacing the usual notion of topology with an étale topology, but once one does so one obtains a very satisfactory theory.

As an exercise, I set myself the task of trying to interpret Galois theory as an analogue of covering space theory in a more classical fashion, without explicit reference to more modern concepts such as schemes, spectra, or étale topology. After some experimentation, I found a reasonably satisfactory way to do so as follows. The space that one associates with in this classical perspective is not the single point , but instead the much larger space consisting of ring homomorphisms from to arbitrary integral domains ; informally, consists of all the “models” or “representations” of (in the spirit of this previous blog post). (There is a technical set-theoretic issue here because the class of integral domains is a proper class, so that will also be a proper class; I will completely ignore such technicalities in this post.) We view each such homomorphism as a single point in . The analogous notion of a path from one point to another is then a homomorphism of integral domains, such that is the composition of with . Note that every prime ideal in the spectrum of a commutative ring gives rise to a point in the space defined here, namely the quotient map to the ring , which is an integral domain because is prime. So one can think of as being a distinguished subset of ; alternatively, one can think of as a sort of “penumbra” surrounding . In particular, when is a field, defines a special point in , namely the identity homomorphism .

Below the fold I would like to record this interpretation of Galois theory, by first revisiting the theory of covering spaces using paths as the basic building block, and then adapting that theory to the theory of field extensions using the spaces indicated above. This is not too far from the usual scheme-theoretic way of phrasing the connection between the two topics (basically I have replaced étale-type points with more classical points ), but I had not seen it explicitly articulated before, so I am recording it here for my own benefit and for any other readers who may be interested.

246C notes 1: Meromorphic functions on Riemann surfaces, and the Riemann-Roch theorem

The fundamental object of study in real differential geometry are the real manifolds: Hausdorff topological spaces that locally look like open subsets of a Euclidean space , and which can be equipped with an atlas of coordinate charts from open subsets covering to open subsets in , which are homeomorphisms; in particular, the transition maps defined by are all continuous. (It is also common to impose the requirement that the manifold be second countable, though this will not be important for the current discussion.) A smooth real manifold is a real manifold in which the transition maps are all smooth.

In a similar fashion, the fundamental object of study in complex differential geometry are the complex manifolds, in which the model space is rather than , and the transition maps are required to be holomorphic (and not merely smooth or continuous). In the real case, the one-dimensional manifolds (curves) are quite simple to understand, particularly if one requires the manifold to be connected; for instance, all compact connected one-dimensional real manifolds are homeomorphic to the unit circle (why?). However, in the complex case, the connected one-dimensional manifolds – the ones that look locally like subsets of – are much richer, and are known as Riemann surfaces. For sake of completeness we give the (somewhat lengthy) formal definition:

Definition 1 (Riemann surface) If is a Hausdorff connected topological space, a (one-dimensional complex) atlas is a collection of homeomorphisms from open subsets of that cover to open subsets of the complex numbers , such that the transition maps defined by are all holomorphic. Here is an arbitrary index set. Two atlases , on are said to be equivalent if their union is also an atlas, thus the transition maps and their inverses are all holomorphic. A Riemann surface is a Hausdorff connected topological space equipped with an equivalence class of one-dimensional complex atlases.

A map from one Riemann surface to another is holomorphic if the maps are holomorphic for any charts , of an atlas of and respectively; it is not hard to see that this definition does not depend on the choice of atlas. It is also clear that the composition of two holomorphic maps is holomorphic (and in fact the class of Riemann surfaces with their holomorphic maps forms a category).

Here are some basic examples of Riemann surfaces.

Example 2 (Quotients of ) The complex numbers clearly form a Riemann surface (using the identity map as the single chart for an atlas). Of course, maps that are holomorphic in the usual sense will also be holomorphic in the sense of the above definition, and vice versa, so the notion of holomorphicity for Riemann surfaces is compatible with that of holomorphicity for complex maps. More generally, given any discrete additive subgroup of , the quotient is a Riemann surface. There are an infinite number of possible atlases to use here; one such is to pick a sufficiently small neighbourhood of the origin in and take the atlas where and for all . In particular, given any non-real complex number , the complex torus formed by quotienting by the lattice is a Riemann surface.

Example 3 Any open connected subset of is a Riemann surface. By the Riemann mapping theorem, all simply connected open , other than itself, are isomorphic (as Riemann surfaces) to the unit disk (or, equivalently, to the upper half-plane).

Example 4 (Riemann sphere) The Riemann sphere , as a topological manifold, is the one-point compactification of . Topologically, this is a sphere and is in particular connected. One can cover the Riemann sphere by the two open sets and , and give these two open sets the charts and defined by for , for , and . This is a complex atlas since the is holomorphic on .

An alternate way of viewing the Riemann sphere is as the projective line . Topologically, this is the punctured complex plane quotiented out by non-zero complex dilations, thus elements of this space are equivalence classes with the usual quotient topology. One can cover this space by two open sets and and give these two open sets the charts and defined by for , . This is a complex atlas, basically because for and is holomorphic on .

Exercise 5 Verify that the Riemann sphere is isomorphic (as a Riemann surface) to the projective line.

Example 6 (Smooth algebraic plane curves) Let be a complex polynomial in three variables which is homogeneous of some degree , thus

Define the complex projective plane to be the punctured space quotiented out by non-zero complex dilations, with the usual quotient topology. (There is another important topology to place here of fundamental importance in algebraic geometry, namely the Zariski topology, but we will ignore this topology here.) This is a compact space, whose elements are equivalence classes . Inside this plane we can define the (projective, degree ) algebraic curve

this is well defined thanks to (1). It is easy to verify that is a closed subset of and hence compact; it is non-empty thanks to the fundamental theorem of algebra.

Suppose that is irreducible, which means that it is not the product of polynomials of smaller degree. As we shall show in the appendix, this makes the algebraic curve connected. (Actually, algebraic curves remain connected even in the reducible case, thanks to Bezout’s theorem, but we will not prove that theorem here.) We will in fact make the stronger nonsingularity hypothesis: there is no triple such that the four numbers simultaneously vanish for . (This looks like four constraints, but is in fact essentially just three, due to the Euler identity

that arises from differentiating (1) in . The fact that nonsingularity implies irreducibility is another consequence of Bezout’s theorem, which is not proven here.) For instance, the polynomial is irreducible but singular (there is a “cusp” singularity at ). With this hypothesis, we call the curve smooth.

Now suppose is a point in ; without loss of generality we may take non-zero, and then we can normalise . Now one can think of as an inhomogeneous polynomial in just two variables , and by nondegeneracy we see that the gradient is non-zero whenever . By the (complexified) implicit function theorem, this ensures that the affine algebraic curve

is a Riemann surface in a neighbourhood of ; we leave this as an exercise. This can be used to give a coordinate chart for in a neighbourhood of when . Similarly when is non-zero. This can be shown to give an atlas on , which (assuming the connectedness claim that we will prove later) gives the structure of a Riemann surface.

Exercise 7 State and prove a complex version of the implicit function theorem that justifies the above claim that the charts in the above example form an atlas, and an algebraic curve associated to a non-singular polynomial is a Riemann surface.

Exercise 8

• (i) Show that all (irreducible plane projective) algebraic curves of degree are isomorphic to the Riemann sphere. (Hint: reduce to an explicit linear polynomial such as .)
• (ii) Show that all (irreducible plane projective) algebraic curves of degree are isomorphic to the Riemann sphere. (Hint: to reduce computation, first use some linear algebra to reduce the homogeneous quadratic polynomial to a standard form, such as or .)

Exercise 9 If are complex numbers, show that the projective cubic curve

is nonsingular if and only if the discriminant is non-zero. (When this occurs, the curve is called an elliptic curve (in Weierstrass form), which is a fundamentally important example of a Riemann surface in many areas of mathematics, and number theory in particular. One can also define the discriminant for polynomials of higher degree, but we will not do so here.)

A recurring theme in mathematics is that an object is often best studied by understanding spaces of “good” functions on . In complex analysis, there are two basic types of good functions:

Definition 10 Let be a Riemann surface. A holomorphic function on is a holomorphic map from to ; the space of all such functions will be denoted . A meromorphic function on is a holomorphic map from to the Riemann sphere , that is not identically equal to ; the space of all such functions will be denoted .

One can also define holomorphicity and meromorphicity in terms of charts: a function is holomorphic if and only if, for any chart , the map is holomorphic in the usual complex analysis sense; similarly, a function is meromorphic if and only if the preimage is discrete (otherwise, by analytic continuation and the connectedness of , will be identically equal to ) and for any chart , the map becomes a meromorphic function in the usual complex analysis sense, after removing the discrete set of complex numbers where this map is infinite. One consequence of this alternate definition is that the space of holomorphic functions is a commutative complex algebra (a complex vector space closed under pointwise multiplication), while the space of meromorphic functions is a complex field (a commutative complex algebra where every non-zero element has an inverse). Another consequence is that one can define the notion of a zero of given order , or a pole of order , for a holomorphic or meromorphic function, by composing with a chart map and using the usual complex analysis notions there, noting (from the holomorphicity of transition maps and their inverses) that this does not depend on the choice of chart. (However, one cannot similarly define the residue of a meromorphic function on this way, as the residue turns out to be chart-dependent thanks to the chain rule. Residues should instead be applied to meromorphic -forms, a concept we will introduce later.) A third consequence is analytic continuation: if two holomorphic or meromorphic functions on agree on a non-empty open set, then they agree everywhere.

On the complex numbers , there are of course many holomorphic functions and meromorphic functions; for instance any power series with an infinite radius of convergence will give a holomorphic function, and the quotient of any two such functions (with non-zero denominator) will give a meromorphic function. Furthermore, we have extremely wide latitude in how to specify the zeroes of the holomorphic function, or the zeroes and poles of the meromorphic function, thanks to tools such as the Weierstrass factorisation theorem or the Mittag-Leffler theorem (covered in previous quarters).

It turns out, however, that the situation changes dramatically when the Riemann surface is compact, with the holomorphic and meromorphic functions becoming much more rigid. First of all, compactness eliminates all holomorphic functions except for the constants:

Lemma 11 Let be a holomorphic function on a compact Riemann surface . Then is constant.

This result should be seen as a close sibling of Liouville’s theorem that all bounded entire functions are constant. (Indeed, in the case of a complex torus, this lemma is a corollary of Liouville’s theorem.)

Proof: As is continuous and is compact, must attain a maximum at some point . Working in a chart around and applying the maximum principle, we conclude that is constant in a neighbourhood of , and hence is constant everywhere by analytic continuation.

This dramatically cuts down the number of possible meromorphic functions – indeed, for an abstract Riemann surface, it is not immediately obvious that there are any non-constant meromorphic functions at all! As the poles are isolated and the surface is compact, a meromorphic function can only have finitely many poles, and if one prescribes the location of the poles and the maximum order at each pole, then we shall see that the space of meromorphic functions is now finite dimensional. The precise dimensions of these spaces are in fact rather interesting, and obey a basic duality law known as the Riemann-Roch theorem. We will give a mostly self-contained proof of the Riemann-Roch theorem in these notes, omitting only some facts about genus and Euler characteristic, as well as construction of certain meromorphic -forms (also known as Abelian differentials).

A more detailed study of Riemann surface (and more generally, complex manifolds) can be found for instance in Griffiths and Harris’s “Principles of Algebraic Geometry“.

The Erdos-Ulam problem, varieties of general type, and the Bombieri-Lang conjecture

In 1946, Ulam, in response to a theorem of Anning and Erdös, posed the following problem:

Problem 1 (Erdös-Ulam problem) Let be a set such that the distance between any two points in is rational. Is it true that cannot be (topologically) dense in ?

The paper of Anning and Erdös addressed the case that all the distances between two points in were integer rather than rational in the affirmative.

The Erdös-Ulam problem remains open; it was discussed recently over at Gödel’s lost letter. It is in fact likely (as we shall see below) that the set in the above problem is not only forbidden to be topologically dense, but also cannot be Zariski dense either. If so, then the structure of is quite restricted; it was shown by Solymosi and de Zeeuw that if fails to be Zariski dense, then all but finitely many of the points of must lie on a single line, or a single circle. (Conversely, it is easy to construct examples of dense subsets of a line or circle in which all distances are rational, though in the latter case the square of the radius of the circle must also be rational.)

The main tool of the Solymosi-de Zeeuw analysis was Faltings’ celebrated theorem that every algebraic curve of genus at least two contains only finitely many rational points. The purpose of this post is to observe that an affirmative answer to the full Erdös-Ulam problem similarly follows from the conjectured analogue of Falting’s theorem for surfaces, namely the following conjecture of Bombieri and Lang:

Conjecture 2 (Bombieri-Lang conjecture) Let be a smooth projective irreducible algebraic surface defined over the rationals which is of general type. Then the set of rational points of is not Zariski dense in .

In fact, the Bombieri-Lang conjecture has been made for varieties of arbitrary dimension, and for more general number fields than the rationals, but the above special case of the conjecture is the only one needed for this application. We will review what “general type” means (for smooth projective complex varieties, at least) below the fold.

The Bombieri-Lang conjecture is considered to be extremely difficult, in particular being substantially harder than Faltings’ theorem, which is itself a highly non-trivial result. So this implication should not be viewed as a practical route to resolving the Erdös-Ulam problem unconditionally; rather, it is a demonstration of the power of the Bombieri-Lang conjecture. Still, it was an instructive algebraic geometry exercise for me to carry out the details of this implication, which quickly boils down to verifying that a certain quite explicit algebraic surface is of general type (Theorem 4 below). As I am not an expert in the subject, my computations here will be rather tedious and pedestrian; it is likely that they could be made much slicker by exploiting more of the machinery of modern algebraic geometry, and I would welcome any such streamlining by actual experts in this area. (For similar reasons, there may be more typos and errors than usual in this post; corrections are welcome as always.) My calculations here are based on a similar calculation of van Luijk, who used analogous arguments to show (assuming Bombieri-Lang) that the set of perfect cuboids is not Zariski-dense in its projective parameter space.

We also remark that in a recent paper of Makhul and Shaffaf, the Bombieri-Lang conjecture (or more precisely, a weaker consequence of that conjecture) was used to show that if is a subset of with rational distances which intersects any line in only finitely many points, then there is a uniform bound on the cardinality of the intersection of with any line. I have also recently learned (private communication) that an unpublished work of Shaffaf has obtained a result similar to the one in this post, namely that the Erdös-Ulam conjecture follows from the Bombieri-Lang conjecture, plus an additional conjecture about the rational curves in a specific surface.

Let us now give the elementary reductions to the claim that a certain variety is of general type. For sake of contradiction, let be a dense set such that the distance between any two points is rational. Then certainly contains two points that are a rational distance apart. By applying a translation, rotation, and a (rational) dilation, we may assume that these two points are and . As is dense, there is a third point of not on the axis, which after a reflection we can place in the upper half-plane; we will write it as with .

Given any two points in , the quantities are rational, and so by the cosine rule the dot product is rational as well. Since , this implies that the -component of every point in is rational; this in turn implies that the product of the -coordinates of any two points in is rational as well (since this differs from by a rational number). In particular, and are rational, and all of the points in now lie in the lattice . (This fact appears to have first been observed in the 1988 habilitationschrift of Kemnitz.)

Now take four points , in in general position (so that the octuplet avoids any pre-specified hypersurface in ); this can be done if is dense. (If one wished, one could re-use the three previous points to be three of these four points, although this ultimately makes little difference to the analysis.) If is any point in , then the distances from to are rationals that obey the equations

for , and thus determine a rational point in the affine complex variety defined as

By inspecting the projection from to , we see that is a branched cover of , with the generic cover having points (coming from the different ways to form the square roots ); in particular, is a complex affine algebraic surface, defined over the rationals. By inspecting the monodromy around the four singular base points (which switch the sign of one of the roots , while keeping the other three roots unchanged), we see that the variety is connected away from its singular set, and thus irreducible. As is topologically dense in , it is Zariski-dense in , and so generates a Zariski-dense set of rational points in . To solve the Erdös-Ulam problem, it thus suffices to show that

Claim 3 For any non-zero rational and for rationals in general position, the rational points of the affine surface is not Zariski dense in .

This is already very close to a claim that can be directly resolved by the Bombieri-Lang conjecture, but is affine rather than projective, and also contains some singularities. The first issue is easy to deal with, by working with the projectivisation

 

of , where is the homogeneous quadratic polynomial

with

and the projective complex space is the space of all equivalence classes of tuples up to projective equivalence . By identifying the affine point with the projective point , we see that consists of the affine variety together with the set , which is the union of eight curves, each of which lies in the closure of . Thus is the projective closure of , and is thus a complex irreducible projective surface, defined over the rationals. As is cut out by four quadric equations in and has degree sixteen (as can be seen for instance by inspecting the intersection of with a generic perturbation of a fibre over the generically defined projection ), it is also a complete intersection. To show (3), it then suffices to show that the rational points in are not Zariski dense in .

Heuristically, the reason why we expect few rational points in is as follows. First observe from the projective nature of (1) that every rational point is equivalent to an integer point. But for a septuple of integers of size , the quantity is an integer point of of size , and so should only vanish about of the time. Hence the number of integer points of height comparable to should be about

this is a convergent sum if ranges over (say) powers of two, and so from standard probabilistic heuristics (see this previous post) we in fact expect only finitely many solutions, in the absence of any special algebraic structure (e.g. the structure of an abelian variety, or a birational reduction to a simpler variety) that could produce an unusually large number of solutions.

The Bombieri-Lang conjecture, Conjecture 2, can be viewed as a formalisation of the above heuristics (roughly speaking, it is one of the most optimistic natural conjectures one could make that is compatible with these heuristics while also being invariant under birational equivalence).

Unfortunately, contains some singular points. Being a complete intersection, this occurs when the Jacobian matrix of the map has less than full rank, or equivalently that the gradient vectors

 

for are linearly dependent, where the is in the coordinate position associated to . One way in which this can occur is if one of the gradient vectors vanish identically. This occurs at precisely points, when is equal to for some , and one has for all (so in particular ). Let us refer to these as the obvious singularities; they arise from the geometrically evident fact that the distance function is singular at .

The other way in which could occur is if a non-trivial linear combination of at least two of the gradient vectors vanishes. From (2), this can only occur if for some distinct , which from (1) implies that

 

and

 

for two choices of sign . If the signs are equal, then (as are in general position) this implies that , and then we have the singular point

 

If the non-trivial linear combination involved three or more gradient vectors, then by the pigeonhole principle at least two of the signs involved must be equal, and so the only singular points are (5). So the only remaining possibility is when we have two gradient vectors that are parallel but non-zero, with the signs in (3), (4) opposing. But then (as are in general position) the vectors are non-zero and non-parallel to each other, a contradiction. Thus, outside of the obvious singular points mentioned earlier, the only other singular points are the two points (5).

We will shortly show that the obvious singularities are ordinary double points; the surface near any of these points is analytically equivalent to an ordinary cone near the origin, which is a cone over a smooth conic curve . The two non-obvious singularities (5) are slightly more complicated than ordinary double points, they are elliptic singularities, which approximately resemble a cone over an elliptic curve. (As far as I can tell, this resemblance is exact in the category of real smooth manifolds, but not in the category of algebraic varieties.) If one blows up each of the point singularities of separately, no further singularities are created, and one obtains a smooth projective surface (using the Segre embedding as necessary to embed back into projective space, rather than in a product of projective spaces). Away from the singularities, the rational points of lift up to rational points of . Assuming the Bombieri-Lang conjecture, we thus are able to answer the Erdös-Ulam problem in the affirmative once we establish

Theorem 4 The blowup of is of general type.

This will be done below the fold, by the pedestrian device of explicitly constructing global differential forms on ; I will also be working from a complex analysis viewpoint rather than an algebraic geometry viewpoint as I am more comfortable with the former approach. (As mentioned above, though, there may well be a quicker way to establish this result by using more sophisticated machinery.)

I thank Mark Green and David Gieseker for helpful conversations (and a crash course in varieties of general type!).

Remark 5 The above argument shows in fact (assuming Bombieri-Lang) that sets with all distances rational cannot be Zariski-dense, and thus (by Solymosi-de Zeeuw) must lie on a single line or circle with only finitely many exceptions. Assuming a stronger version of Bombieri-Lang involving a general number field , we obtain a similar conclusion with “rational” replaced by “lying in ” (one has to extend the Solymosi-de Zeeuw analysis to more general number fields, but this should be routine, using the analogue of Faltings’ theorem for such number fields).

The Bombieri-Stepanov proof of the Hasse-Weil bound

Let be a finite field of order , and let be an absolutely irreducible smooth projective curve defined over (and hence over the algebraic closure of that field). For instance, could be the projective elliptic curve

in the projective plane , where are coefficients whose discriminant is non-vanishing, which is the projective version of the affine elliptic curve

To each such curve one can associate a genus , which we will define later; for instance, elliptic curves have genus . We can also count the cardinality of the set of -points of . The Hasse-Weil bound relates the two:

Theorem 1 (Hasse-Weil bound) .

The usual proofs of this bound proceed by first establishing a trace formula of the form

 

for some complex numbers independent of ; this is in fact a special case of the Lefschetz-Grothendieck trace formula, and can be interpreted as an assertion that the zeta function associated to the curve is rational. The task is then to establish a bound for all ; this (or more precisely, the slightly stronger assertion ) is the Riemann hypothesis for such curves. This can be done either by passing to the Jacobian variety of and using a certain duality available on the cohomology of such varieties, known as Rosati involution; alternatively, one can pass to the product surface and apply the Riemann-Roch theorem for that surface.

In 1969, Stepanov introduced an elementary method (a version of what is now known as the polynomial method) to count (or at least to upper bound) the quantity . The method was initially restricted to hyperelliptic curves, but was soon extended to general curves. In particular, Bombieri used this method to give a short proof of the following weaker version of the Hasse-Weil bound:

Theorem 2 (Weak Hasse-Weil bound) If is a perfect square, and , then .

In fact, the bound on can be sharpened a little bit further, as we will soon see.

Theorem 2 is only an upper bound on , but there is a Galois-theoretic trick to convert (a slight generalisation of) this upper bound to a matching lower bound, and if one then uses the trace formula (1) (and the “tensor power trick” of sending to infinity to control the weights ) one can then recover the full Hasse-Weil bound. We discuss these steps below the fold.

I’ve discussed Bombieri’s proof of Theorem 2 in this previous post (in the special case of hyperelliptic curves), but now wish to present the full proof, with some minor simplifications from Bombieri’s original presentation; it is mostly elementary, with the deepest fact from algebraic geometry needed being Riemann’s inequality (a weak form of the Riemann-Roch theorem).

The first step is to reinterpret as the number of points of intersection between two curves in the surface . Indeed, if we define the Frobenius endomorphism on any projective space by

then this map preserves the curve , and the fixed points of this map are precisely the points of :

Thus one can interpret as the number of points of intersection between the diagonal curve

and the Frobenius graph

which are copies of inside . But we can use the additional hypothesis that is a perfect square to write this more symmetrically, by taking advantage of the fact that the Frobenius map has a square root

with also preserving . One can then also interpret as the number of points of intersection between the curve

 

and its transpose

Let be the field of rational functions on (with coefficients in ), and define , , and analogously )(although is likely to be disconnected, so will just be a ring rather than a field. We then (morally) have the commuting square

if we ignore the issue that a rational function on, say, , might blow up on all of and thus not have a well-defined restriction to . We use and to denote the restriction maps. Furthermore, we have obvious isomorphisms , coming from composing with the graphing maps and .

The idea now is to find a rational function on the surface of controlled degree which vanishes when restricted to , but is non-vanishing (and not blowing up) when restricted to . On , we thus get a non-zero rational function of controlled degree which vanishes on – which then lets us bound the cardinality of in terms of the degree of . (In Bombieri’s original argument, one required vanishing to high order on the side, but in our presentation, we have factored out a term which removes this high order vanishing condition.)

To find this , we will use linear algebra. Namely, we will locate a finite-dimensional subspace of (consisting of certain “controlled degree” rational functions) which projects injectively to , but whose projection to has strictly smaller dimension than itself. The rank-nullity theorem then forces the existence of a non-zero element of whose projection to vanishes, but whose projection to is non-zero.

Now we build . Pick a point of , which we will think of as being a point at infinity. (For the purposes of proving Theorem 2, we may clearly assume that is non-empty.) Thus is fixed by . To simplify the exposition, we will also assume that is fixed by the square root of ; in the opposite case when has order two when acting on , the argument is essentially the same, but all references to in the second factor of need to be replaced by (we leave the details to the interested reader).

For any natural number , define to be the set of rational functions which are allowed to have a pole of order up to at , but have no other poles on ; note that as we are assuming to be smooth, it is unambiguous what a pole is (and what order it will have). (In the fancier language of divisors and Cech cohomology, we have .) The space is clearly a vector space over ; one can view intuitively as the space of “polynomials” on of “degree” at most . When , consists just of the constant functions. Indeed, if , then the image of avoids and so lies in the affine line ; but as is projective, the image needs to be compact (hence closed) in , and must therefore be a point, giving the claim.

For higher , we have the easy relations

 

The former inequality just comes from the trivial inclusion . For the latter, observe that if two functions lie in , so that they each have a pole of order at most at , then some linear combination of these functions must have a pole of order at most at ; thus has codimension at most one in , giving the claim.

From (3) and induction we see that each of the are finite dimensional, with the trivial upper bound

 

Riemann’s inequality complements this with the lower bound

 

thus one has for all but at most exceptions (in fact, exactly exceptions as it turns out). This is a consequence of the Riemann-Roch theorem; it can be proven from abstract nonsense (the snake lemma) if one defines the genus in a non-standard fashion (as the dimension of the first Cech cohomology of the structure sheaf of ), but to obtain this inequality with a standard definition of (e.g. as the dimension of the zeroth Cech cohomolgy of the line bundle of differentials) requires the more non-trivial tool of Serre duality.

At any rate, now that we have these vector spaces , we will define to be a tensor product space

for some natural numbers which we will optimise in later. That is to say, is spanned by functions of the form with and . This is clearly a linear subspace of of dimension , and hence by Rieman’s inequality we have

 

if

 

Observe that maps a tensor product to a function . If and , then we see that the function has a pole of order at most at . We conclude that

 

and in particular by (4)

 

and similarly

 

We will choose to be a bit bigger than , to make the image of smaller than that of . From (6), (10) we see that if we have the inequality

 

(together with (7)) then cannot be injective.

On the other hand, we have the following basic fact:

Lemma 3 (Injectivity) If

 

then is injective.

Proof: From (3), we can find a linear basis of such that each of the has a distinct order of pole at (somewhere between and inclusive). Similarly, we may find a linear basis of such that each of the has a distinct order of pole at (somewhere between and inclusive). The functions then span , and the order of pole at is . But since , these orders are all distinct, and so these functions must be linearly independent. The claim follows.

This gives us the following bound:

Proposition 4 Let be natural numbers such that (7), (11), (12) hold. Then .

Proof: As is not injective, we can find with vanishing. By the above lemma, the function is then non-zero, but it must also vanish on , which has cardinality . On the other hand, by (8), has a pole of order at most at and no other poles. Since the number of poles and zeroes of a rational function on a projective curve must add up to zero, the claim follows.

If , we may make the explicit choice

and a brief calculation then gives Theorem 2. In some cases one can optimise things a bit further. For instance, in the genus zero case (e.g. if is just the projective line ) one may take and conclude the absolutely sharp bound in this case; in the case of the projective line , the function is in fact the very concrete function .

Remark 1 When is not a perfect square, one can try to run the above argument using the factorisation instead of . This gives a weaker version of the above bound, of the shape . In the hyperelliptic case at least, one can erase this loss by working with a variant of the argument in which one requires to vanish to high order at , rather than just to first order; see this survey article of mine for details.

The Monge-Cayley-Salmon theorem via classical differential geometry

Let be an irreducible polynomial in three variables. As is not algebraically closed, the zero set can split into various components of dimension between and . For instance, if , the zero set is a line; more interestingly, if , then is the union of a line and a surface (or the product of an acnodal cubic curve with a line). We will assume that the -dimensional component is non-empty, thus defining a real surface in . In particular, this hypothesis implies that is not just irreducible over , but is in fact absolutely irreducible (i.e. irreducible over ), since otherwise one could use the complex factorisation of to contain inside the intersection of the complex zero locus of complex polynomial and its complex conjugate, with having no common factor, forcing to be at most one-dimensional. (For instance, in the case , one can take .) Among other things, this makes a Zariski-dense subset of , thus any polynomial identity which holds true at every point of , also holds true on all of . This allows us to easily use tools from algebraic geometry in this real setting, even though the reals are not quite algebraically closed.

The surface is said to be ruled if, for a Zariski open dense set of points , there exists a line through for some non-zero which is completely contained in , thus

for all . Also, a point is said to be a flecnode if there exists a line through for some non-zero which is tangent to to third order, in the sense that

as , or equivalently that

 

for . Clearly, if is a ruled surface, then a Zariski open dense set of points on are a flecnode. We then have the remarkable theorem (discovered first by Monge, and then later by Cayley and Salmon) asserting the converse:

Theorem 1 (Monge-Cayley-Salmon theorem) Let be an irreducible polynomial with non-empty. Suppose that a Zariski dense set of points in are flecnodes. Then is a ruled surface.

Among other things, this theorem was used in the celebrated result of Guth and Katz that almost solved the Erdos distance problem in two dimensions, as discussed in this previous blog post. Vanishing to third order is necessary: observe that in a surface of negative curvature, such as the saddle , every point on the surface is tangent to second order to a line (the line in the direction for which the second fundamental form vanishes). This surface happens to be ruled, but a generic perturbation of this surface (e.g. ) will no longer be ruled, although it is still negative curvature near the origin.

The original proof of the Monge-Cayley-Salmon theorem is not easily accessible and not written in modern language. A modern proof of this theorem (together with substantial generalisations, for instance to higher dimensions) is given by Landsberg; the proof uses the machinery of modern algebraic geometry. The purpose of this post is to record an alternate proof of the Monge-Cayley-Salmon theorem based on classical differential geometry (in particular, the notion of torsion of a curve) and basic ODE methods (in particular, Gronwall’s inequality and the Picard existence theorem). The idea is to “integrate” the lines indicated by the flecnode to produce smooth curves on the surface ; one then uses the vanishing (1) and some basic calculus to conclude that these curves have zero torsion and are thus planar curves. Some further manipulation using (1) (now just to second order instead of third) then shows that these curves are in fact straight lines, giving the ruling on the surface.

Update: Janos Kollar has informed me that the above theorem was essentially known to Monge in 1809; see his recent arXiv note for more details.

I thank Larry Guth and Micha Sharir for conversations leading to this post.

Qualitative probability theory, types, and the group chunk and group configuration theorems

The classical foundations of probability theory (discussed for instance in this previous blog post) is founded on the notion of a probability space – a space (the sample space) equipped with a -algebra (the event space), together with a countably additive probability measure that assigns a real number in the interval to each event.

One can generalise the concept of a probability space to a finitely additive probability space, in which the event space is now only a Boolean algebra rather than a -algebra, and the measure is now only finitely additive instead of countably additive, thus when are disjoint events. By giving up countable additivity, one loses a fair amount of measure and integration theory, and in particular the notion of the expectation of a random variable becomes problematic (unless the random variable takes only finitely many values). Nevertheless, one can still perform a fair amount of probability theory in this weaker setting.

In this post I would like to describe a further weakening of probability theory, which I will call qualitative probability theory, in which one does not assign a precise numerical probability value to each event, but instead merely records whether this probability is zero, one, or something in between. Thus is now a function from to the set , where is a new symbol that replaces all the elements of the open interval . In this setting, one can no longer compute quantitative expressions, such as the mean or variance of a random variable; but one can still talk about whether an event holds almost surely, with positive probability, or with zero probability, and there are still usable notions of independence. (I will refer to classical probability theory as quantitative probability theory, to distinguish it from its qualitative counterpart.)

The main reason I want to introduce this weak notion of probability theory is that it becomes suited to talk about random variables living inside algebraic varieties, even if these varieties are defined over fields other than or . In algebraic geometry one often talks about a “generic” element of a variety defined over a field , which does not lie in any specified variety of lower dimension defined over . Once has positive dimension, such generic elements do not exist as classical, deterministic -points in , since of course any such point lies in the -dimensional subvariety of . There are of course several established ways to deal with this problem. One way (which one might call the “Weil” approach to generic points) is to extend the field to a sufficiently transcendental extension , in order to locate a sufficient number of generic points in . Another approach (which one might dub the “Zariski” approach to generic points) is to work scheme-theoretically, and interpret a generic point in as being associated to the zero ideal in the function ring of . However I want to discuss a third perspective, in which one interprets a generic point not as a deterministic object, but rather as a random variable taking values in , but which lies in any given lower-dimensional subvariety of with probability zero. This interpretation is intuitive, but difficult to implement in classical probability theory (except perhaps when considering varieties over or ) due to the lack of a natural probability measure to place on algebraic varieties; however it works just fine in qualitative probability theory. In particular, the algebraic geometry notion of being “generically true” can now be interpreted probabilistically as an assertion that something is “almost surely true”.

It turns out that just as qualitative random variables may be used to interpret the concept of a generic point, they can also be used to interpret the concept of a type in model theory; the type of a random variable is the set of all predicates that are almost surely obeyed by . In contrast, model theorists often adopt a Weil-type approach to types, in which one works with deterministic representatives of a type, which often do not occur in the original structure of interest, but only in a sufficiently saturated extension of that structure (this is the analogue of working in a sufficiently transcendental extension of the base field). However, it seems that (in some cases at least) one can equivalently view types in terms of (qualitative) random variables on the original structure, avoiding the need to extend that structure. (Instead, one reserves the right to extend the sample space of one’s probability theory whenever necessary, as part of the “probabilistic way of thinking” discussed in this previous blog post.) We illustrate this below the fold with two related theorems that I will interpret through the probabilistic lens: the “group chunk theorem” of Weil (and later developed by Hrushovski), and the “group configuration theorem” of Zilber (and again later developed by Hrushovski). For sake of concreteness we will only consider these theorems in the theory of algebraically closed fields, although the results are quite general and can be applied to many other theories studied in model theory.

A spectral theory proof of the algebraic regularity lemma

Let be a field. A definable set over is a set of the form

where is a natural number, and is a predicate involving the ring operations of , the equality symbol , an arbitrary number of constants and free variables in , the quantifiers , boolean operators such as , and parentheses and colons, where the quantifiers are always understood to be over the field . Thus, for instance, the set of quadratic residues

is definable over , and any algebraic variety over is also a definable set over . Henceforth we will abbreviate “definable over ” simply as “definable”.

If is a finite field, then every subset of is definable, since finite sets are automatically definable. However, we can obtain a more interesting notion in this case by restricting the complexity of a definable set. We say that is a definable set of complexity at most if , and can be written in the form (1) for some predicate of length at most (where all operators, quantifiers, relations, variables, constants, and punctuation symbols are considered to have unit length). Thus, for instance, a hypersurface in dimensions of degree would be a definable set of complexity . We will then be interested in the regime where the complexity remains bounded, but the field size (or field characteristic) becomes large.

In a recent paper, I established (in the large characteristic case) the following regularity lemma for dense definable graphs, which significantly strengthens the Szemerédi regularity lemma in this context, by eliminating “bad” pairs, giving a polynomially strong regularity, and also giving definability of the cells:

Lemma 1 (Algebraic regularity lemma) Let be a finite field, let be definable non-empty sets of complexity at most , and let also be definable with complexity at most . Assume that the characteristic of is sufficiently large depending on . Then we may partition and with , with the following properties:

• (Definability) Each of the are definable of complexity .
• (Size) We have and for all and .
• (Regularity) We have

  

  for all , , , and , where is a rational number in with numerator and denominator .

My original proof of this lemma was quite complicated, based on an explicit calculation of the “square”

of using the Lang-Weil bound and some facts about the étale fundamental group. It was the reliance on the latter which was the main reason why the result was restricted to the large characteristic setting. (I then applied this lemma to classify expanding polynomials over finite fields of large characteristic, but I will not discuss these applications here; see this previous blog post for more discussion.)

Recently, Anand Pillay and Sergei Starchenko (and independently, Udi Hrushovski) have observed that the theory of the étale fundamental group is not necessary in the argument, and the lemma can in fact be deduced from quite general model theoretic techniques, in particular using (a local version of) the concept of stability. One of the consequences of this new proof of the lemma is that the hypothesis of large characteristic can be omitted; the lemma is now known to be valid for arbitrary finite fields (although its content is trivial if the field is not sufficiently large depending on the complexity at most ).

Inspired by this, I decided to see if I could find yet another proof of the algebraic regularity lemma, again avoiding the theory of the étale fundamental group. It turns out that the spectral proof of the Szemerédi regularity lemma (discussed in this previous blog post) adapts very nicely to this setting. The key fact needed about definable sets over finite fields is that their cardinality takes on an essentially discrete set of values. More precisely, we have the following fundamental result of Chatzidakis, van den Dries, and Macintyre:

Proposition 2 Let be a finite field, and let .

• (Discretised cardinality) If is a non-empty definable set of complexity at most , then one has

  

  where is a natural number, and is a positive rational number with numerator and denominator . In particular, we have .

• (Definable cardinality) Assume is sufficiently large depending on . If , and are definable sets of complexity at most , so that can be viewed as a definable subset of that is definably parameterised by , then for each natural number and each positive rational with numerator and denominator , the set

  

  is definable with complexity , where the implied constants in the asymptotic notation used to define (4) are the same as those that appearing in (3). (Informally: the “dimension” and “measure” of depends definably on .)

We will take this proposition as a black box; a proof can be obtained by combining the description of definable sets over pseudofinite fields (discussed in this previous post) with the Lang-Weil bound (discussed in this previous post). (The former fact is phrased using nonstandard analysis, but one can use standard compactness-and-contradiction arguments to convert such statements to statements in standard analysis, as discussed in this post.)

The above proposition places severe restrictions on the cardinality of definable sets; for instance, it shows that one cannot have a definable set of complexity at most and cardinality , if is sufficiently large depending on . If are definable sets of complexity at most , it shows that for some rational with numerator and denominator ; furthermore, if , we may improve this bound to . In particular, we obtain the following “self-improving” properties:

• If are definable of complexity at most and for some , then (if is sufficiently small depending on and is sufficiently large depending on ) this forces .
• If are definable of complexity at most and for some and positive rational , then (if is sufficiently small depending on and is sufficiently large depending on ) this forces .

It turns out that these self-improving properties can be applied to the coefficients of various matrices (basically powers of the adjacency matrix associated to ) that arise in the spectral proof of the regularity lemma to significantly improve the bounds in that lemma; we describe how this is done below the fold. We also make some connections to the stability-based proofs of Pillay-Starchenko and Hrushovski.

Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory

I’ve just uploaded to the arXiv my article “Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory“, submitted to the new journal “EMS surveys in the mathematical sciences“.  This is the first draft of a survey article on the polynomial method – a technique in combinatorics and number theory for controlling a relevant set of points by comparing it with the zero set of a suitably chosen polynomial, and then using tools from algebraic geometry (e.g. Bezout’s theorem) on that zero set. As such, the method combines algebraic geometry with combinatorial geometry, and could be viewed as the philosophy of a combined field which I dub “algebraic combinatorial geometry”.   There is also an important extension of this method when one is working overthe reals, in which methods from algebraic topology (e.g. the ham sandwich theorem and its generalisation to polynomials), and not just algebraic geometry, come into play also.

The polynomial method has been used independently many times in mathematics; for instance, it plays a key role in the proof of Baker’s theorem in transcendence theory, or Stepanov’s method in giving an elementary proof of the Riemann hypothesis for finite fields over curves; in combinatorics, the nullstellenatz of Alon is also another relatively early use of the polynomial method.  More recently, it underlies Dvir’s proof of the Kakeya conjecture over finite fields and Guth and Katz’s near-complete solution to the Erdos distance problem in the plane, and can be used to give a short proof of the Szemeredi-Trotter theorem.  One of the aims of this survey is to try to present all of these disparate applications of the polynomial method in a somewhat unified context; my hope is that there will eventually be a systematic foundation for algebraic combinatorial geometry which naturally contains all of these different instances the polynomial method (and also suggests new instances to explore); but the field is unfortunately not at that stage of maturity yet.

This is something of a first draft, so comments and suggestions are even more welcome than usual.  (For instance, I have already had my attention drawn to some additional uses of the polynomial method in the literature that I was not previously aware of.)