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.

Definable subsets over (nonstandard) finite fields, and almost quantifier elimination

Much as group theory is the study of groups, or graph theory is the study of graphs, model theory is the study of models (also known as structures) of some language (which, in this post, will always be a single-sorted, first-order language). A structure is a set , equipped with one or more operations, constants, and relations. This is of course an extremely general type of mathematical object, but (quite remarkably) one can still say a substantial number of interesting things about very broad classes of structures.

We will observe the common abuse of notation of using the set as a metonym for the entire structure, much as we usually refer to a group simply as , a vector space simply as , and so forth. Following another common bending of the rules, we also allow some operations on structures (such as the multiplicative inverse operation on a group or field) to only be partially defined, and we allow use of the usual simplifying conventions for mathematical formulas (e.g. writing instead of or , in cases where associativity is known). We will also deviate slightly from the usual practice in logic by emphasising individual structures, rather than the theory of general classes of structures; for instance, we will talk about the theory of a single field such as or , rather than the theory of all fields of a certain type (e.g. real closed fields or algebraically closed fields).

Once one has a structure , one can introduce the notion of a definable subset of , or more generally of a Cartesian power of , defined as a set of the form

for some formula in the language with free variables and any number of constants from (that is, is a well-formed formula built up from a finite number of constants in , the relations and operations on , logical connectives such as , , , and the quantifiers ). Thus, for instance, in the theory of the arithmetic of the natural numbers , the set of primes is a definable set, since we have

In the theory of the field of reals , the unit circle is an example of a definable set,

but so is the the complement of the circle,

and the interval :

Due to the unlimited use of constants, any finite subset of a power of any structure is, by our conventions, definable in that structure. (One can of course also consider definability without parameters (also known as -definability), in which arbitrary constants are not permitted, but we will not do so here.)

We can isolate some special subclasses of definable sets:

• An atomic definable set is a set of the form (1) in which is an atomic formula (i.e. it does not contain any logical connectives or quantifiers).
• A quantifier-free definable set is a set of the form (1) in which is quantifier-free (i.e. it can contain logical connectives, but does not contain the quantifiers ).

Example 1 In the theory of a field such as , an atomic definable set is the same thing as an affine algebraic set (also known as an affine algebraic variety, with the understanding that varieties are not necessarily assumed to be irreducible), and a quantifier-free definable set is known as a constructible set; thus we see that algebraic geometry can be viewed in some sense as a special case of model theory. (Conversely, it can in fact be quite profitable to think of model theory as an abstraction of algebraic geometry; for instance, the concepts of Morley rank and Morley degree in model theory (discussed in this previous blog post) directly generalises the concepts of dimension and degree in algebraic geometry.) Over , the interval is a definable set, but not a quantifier-free definable set (and certainly not an atomic definable set); and similarly for the primes over .

A quantifier-free definable set in is nothing more than a finite boolean combination of atomic definable sets; in other words, the class of quantifier-free definable sets over is the smallest class that contains the atomic definable sets and is closed under boolean operations such as complementation and union (which generate all the other boolean operations). Similarly, the class of definable sets over is the smallest class that contains the quantifier-free definable sets, and is also closed under the operation of projection from to for every natural number , where is the map .

Some structures have the property of enjoying quantifier elimination, which means that every definable set is in fact a quantifier-free definable set, or equivalently that the projection of a quantifier-free definable set is again quantifier-free. For instance, an algebraically closed field (with the field operations) has quantifier elimination (i.e. the projection of a constructible set is again constructible); this fact can be proven by the classical tool of resultants, and among other things can be used to give a proof of Hilbert’s nullstellensatz. (Note though that projection does not necessary preserve the property of being atomic; for instance, the projection of the atomic set is the non-atomic, but still quantifier-free definable, set .) In the converse direction, it is not difficult to use the nullstellensatz to deduce quantifier elimination. For theory of the real field , which is not algebraically closed, one does not have quantifier elimination, as one can see from the example of the unit circle (which is a quantifier-free definable set) projecting down to the interval (which is definable, but not quantifer-free definable). However, if one adds the additional operation of order to the reals, giving it the language of an ordered field rather than just a field, then quantifier elimination is recovered (the class of quantifier-free definable sets now enlarges to match the class of definable sets, which in this case is also the class of semi-algebraic sets); this is the famous Tarski-Seidenberg theorem.

On the other hand, many important structures do not have quantifier elimination; typically, the projection of a quantifier-free definable set is not, in general, quantifier-free definable. This failure of the projection property also shows up in many contexts outside of model theory; for instance, Lebesgue famously made the error of thinking that the projection of a Borel measurable set remained Borel measurable (it is merely an analytic set instead). Turing’s halting theorem can be viewed as an assertion that the projection of a decidable set (also known as a computable or recursive set) is not necessarily decidable (it is merely semi-decidable (or recursively enumerable) instead). The notorious P=NP problem can also be essentially viewed in this spirit; roughly speaking (and glossing over the placement of some quantifiers), it asks whether the projection of a polynomial-time decidable set is again polynomial-time decidable. And so forth. (See this blog post of Dick Lipton for further discussion of the subtleties of projections.)

Now we consider the status of quantifier elimination for the theory of a finite field . If interpreted naively, quantifier elimination is trivial for a finite field , since every subset of is finite and thus quantifier-free definable. However, we can recover an interesting question in one of two (essentially equivalent) ways. One is to work in the asymptotic regime in which the field is large, but the length of the formulae used to construct one’s definable sets stays bounded uniformly in the size of (where we view any constant in as contributing a unit amount to the length of a formula, no matter how large is). A simple counting argument then shows that only a small number of subsets of become definable in the asymptotic limit , since the number of definable sets clearly grows at most polynomially in for any fixed bound on the formula length, while the number of all subsets of grows exponentially in .

Another way to proceed is to work not with a single finite field , or even with a sequence of finite fields, but with the ultraproduct of a sequence of finite fields, and to study the properties of definable sets over this ultraproduct. (We will be using the notation of ultraproducts and nonstandard analysis from this previous blog post.) This approach is equivalent to the more finitary approach mentioned in the previous paragraph, at least if one does not care to track of the exact bounds on the length of the formulae involved. Indeed, thanks to Los’s theorem, a definable subset of is nothing more than the ultraproduct of definable subsets of for all sufficiently close to , with the length of the formulae used to define uniformly bounded in . In the language of nonstandard analysis, one can view as a nonstandard finite field.

The ultraproduct of finite fields is an important example of a pseudo-finite field – a field that obeys all the sentences in the languages of fields that finite fields do, but is not necessarily itself a finite field. The model theory of pseudo-finite fields was first studied systematically by Ax (in the same paper where the Ax-Grothendieck theorem, discussed previously on this blog, was established), with important further contributions by Kiefe, by Fried-Sacerdote, by two papers of Chatzidakis-van den Dries-Macintyre, and many other authors.

As mentioned before, quantifier elimination trivially holds for finite fields. But for infinite pseudo-finite fields, such as the ultraproduct of finite fields with going to infinity, quantifier elimination fails. For instance, in a finite field , the set of quadratic residues is a definable set, with a bounded formula length, and so in the ultraproduct , the set of nonstandard quadratic residues is also a definable set. However, in one dimension, we see from the factor theorem that the only atomic definable sets are either finite or the whole field , and so the only constructible sets (i.e. the only quantifier-free definable sets) are either finite or cofinite in . Since the quadratic residues have asymptotic density in a large finite field, they cannot form a quantifier-free definable set, despite being definable.

Nevertheless, there is a very nice almost quantifier elimination result for these fields, in characteristic zero at least, which we phrase here as follows:

Theorem 1 (Almost quantifier elimination) Let be a nonstandard finite field of characteristic zero, and let be a definable set over . Then is the union of finitely many sets of the form

where is an atomic definable subset of (i.e. the -points of an algebraic variety defined over in ) and is a polynomial.

Results of this type were first obtained essentially due to Catarina Kiefe, although the formulation here is closer to that of Chatzidakis-van den Dries-Macintyre.

Informally, this theorem says that while we cannot quite eliminate all quantifiers from a definable set over a nonstandard finite field, we can eliminate all but one existential quantifier. Note that negation has also been eliminated in this theorem; for instance, the definable set uses a negation, but can also be described using a single existential quantifier as .) I believe that there are more complicated analogues of this result in positive characteristic, but I have not studied this case in detail (Kiefe’s result does not assume characteristic zero, but her conclusion is slightly different from the one given here). In the one-dimensional case , the only varieties are the affine line and finite sets, and we can simplify the above statement, namely that any definable subset of takes the form for some polynomial (i.e. definable sets in are nothing more than the projections of the -points of a plane curve).

There is an equivalent formulation of this theorem for standard finite fields, namely that if is a finite field and is definable using a formula of length at most , then can be expressed in the form (2) with the degree of bounded by some quantity depending on and , assuming that the characteristic of is sufficiently large depending on .

The theorem gives quite a satisfactory description of definable sets in either standard or nonstandard finite fields (at least if one does not care about effective bounds in some of the constants, and if one is willing to exclude the small characteristic case); for instance, in conjunction with the Lang-Weil bound discussed in this recent blog post, it shows that any non-empty definable subset of a nonstandard finite field has a nonstandard cardinality of for some positive standard rational and integer . Equivalently, any non-empty definable subset of for some standard finite field using a formula of length at most has a standard cardinality of for some positive rational of height and some natural number between and . (For instance, in the example of the quadratic residues given above, is equal to and equal to .) There is a more precise statement to this effect, namely that the Poincaré series of a definable set is rational; see Kiefe’s paper for details.

Below the fold I give a proof of Theorem 1, which relies primarily on the Lang-Weil bound mentioned above.

A geometric proof of the impossibility of angle trisection by straightedge and compass

One of the most well known problems from ancient Greek mathematics was that of trisecting an angle by straightedge and compass, which was eventually proven impossible in 1837 by Pierre Wantzel, using methods from Galois theory.

Formally, one can set up the problem as follows. Define a configuration to be a finite collection of points, lines, and circles in the Euclidean plane. Define a construction step to be one of the following operations to enlarge the collection :

• (Straightedge) Given two distinct points in , form the line that connects and , and add it to .
• (Compass) Given two distinct points in , and given a third point in (which may or may not equal or ), form the circle with centre and radius equal to the length of the line segment joining and , and add it to .
• (Intersection) Given two distinct curves in (thus is either a line or a circle in , and similarly for ), select a point that is common to both and (there are at most two such points), and add it to .

We say that a point, line, or circle is constructible by straightedge and compass from a configuration if it can be obtained from after applying a finite number of construction steps.

Problem 1 (Angle trisection) Let be distinct points in the plane. Is it always possible to construct by straightedge and compass from a line through that trisects the angle , in the sense that the angle between and is one third of the angle of ?

Thanks to Wantzel’s result, the answer to this problem is known to be “no” in general; a generic angle cannot be trisected by straightedge and compass. (On the other hand, some special angles can certainly be trisected by straightedge and compass, such as a right angle. Also, one can certainly trisect generic angles using other methods than straightedge and compass; see the Wikipedia page on angle trisection for some examples of this.)

The impossibility of angle trisection stands in sharp contrast to the easy construction of angle bisection via straightedge and compass, which we briefly review as follows:

1. Start with three points .
2. Form the circle with centre and radius , and intersect it with the line . Let be the point in this intersection that lies on the same side of as . ( may well be equal to ).
3. Form the circle with centre and radius , and the circle with centre and radius . Let be the point of intersection of and that is not .
4. The line will then bisect the angle .

The key difference between angle trisection and angle bisection ultimately boils down to the following trivial number-theoretic fact:

Lemma 2 There is no power of that is evenly divisible by .

Proof: Obvious by modular arithmetic, by induction, or by the fundamental theorem of arithmetic.

In contrast, there are of course plenty of powers of that are evenly divisible by , and this is ultimately why angle bisection is easy while angle trisection is hard.

The standard way in which Lemma 2 is used to demonstrate the impossibility of angle trisection is via Galois theory. The implication is quite short if one knows this theory, but quite opaque otherwise. We briefly sketch the proof of this implication here, though we will not need it in the rest of the discussion. Firstly, Lemma 2 implies the following fact about field extensions.

Corollary 3 Let be a field, and let be an extension of that can be constructed out of by a finite sequence of quadratic extensions. Then does not contain any cubic extensions of .

Proof: If contained a cubic extension of , then the dimension of over would be a multiple of three. On the other hand, if is obtained from by a tower of quadratic extensions, then the dimension of over is a power of two. The claim then follows from Lemma 2.

To conclude the proof, one then notes that any point, line, or circle that can be constructed from a configuration is definable in a field obtained from the coefficients of all the objects in after taking a finite number of quadratic extensions, whereas a trisection of an angle will generically only be definable in a cubic extension of the field generated by the coordinates of .

The Galois theory method also allows one to obtain many other impossibility results of this type, most famously the Abel-Ruffini theorem on the insolvability of the quintic equation by radicals. For this reason (and also because of the many applications of Galois theory to number theory and other branches of mathematics), the Galois theory argument is the “right” way to prove the impossibility of angle trisection within the broader framework of modern mathematics. However, this argument has the drawback that it requires one to first understand Galois theory (or at least field theory), which is usually not presented until an advanced undergraduate algebra or number theory course, whilst the angle trisection problem requires only high-school level mathematics to formulate. Even if one is allowed to “cheat” and sweep several technicalities under the rug, one still needs to possess a fair amount of solid intuition about advanced algebra in order to appreciate the proof. (This was undoubtedly one reason why, even after Wantzel’s impossibility result was published, a large amount of effort was still expended by amateur mathematicians to try to trisect a general angle.)

In this post I would therefore like to present a different proof (or perhaps more accurately, a disguised version of the standard proof) of the impossibility of angle trisection by straightedge and compass, that avoids explicit mention of Galois theory (though it is never far beneath the surface). With “cheats”, the proof is actually quite simple and geometric (except for Lemma 2, which is still used at a crucial juncture), based on the basic geometric concept of monodromy; unfortunately, some technical work is needed however to remove these cheats.

To describe the intuitive idea of the proof, let us return to the angle bisection construction, that takes a triple of points as input and returns a bisecting line as output. We iterate the construction to create a quadrisecting line , via the following sequence of steps that extend the original bisection construction:

1. Start with three points .
2. Form the circle with centre and radius , and intersect it with the line . Let be the point in this intersection that lies on the same side of as . ( may well be equal to ).
3. Form the circle with centre and radius , and the circle with centre and radius . Let be the point of intersection of and that is not .
4. Let be the point on the line which lies on , and is on the same side of as .
5. Form the circle with centre and radius . Let be the point of intersection of and that is not .
6. The line will then quadrisect the angle .

Let us fix the points and , but not , and view (as well as intermediate objects such as , , , , , , ) as a function of .

Let us now do the following: we begin rotating counterclockwise around , which drags around the other objects , , , , , , that were constructed by accordingly. For instance, here is an early stage of this rotation process, when the angle has become obtuse:

Now for the slightly tricky bit. We are going to keep rotating beyond a half-rotation of , so that now becomes a reflex angle. At this point, a singularity occurs; the point collides into , and so there is an instant in which the line is not well-defined. However, this turns out to be a removable singularity (and the easiest way to demonstrate this will be to tap the power of complex analysis, as complex numbers can easily route around such a singularity), and we can blast through it to the other side, giving a picture like this:

Note that we have now deviated from the original construction in that and are no longer on the same side of ; we are thus now working in a continuation of that construction rather than with the construction itself. Nevertheless, we can still work with this continuation (much as, say, one works with analytic continuations of infinite series such as beyond their original domain of definition).

We now keep rotating around . Here, is approaching a full rotation of :

When reaches a full rotation, a different singularity occurs: and coincide. Nevertheless, this is also a removable singularity, and we blast through to beyond a full rotation:

And now is back where it started, as are , , , and … but the point has moved, from one intersection point of to the other. As a consequence, , , and have also changed, with being at right angles to where it was before. (In the jargon of modern mathematics, the quadrisection construction has a non-trivial monodromy.)

But nothing stops us from rotating some more. If we continue this procedure, we see that after two full rotations of around , all points, lines, and circles constructed from have returned to their original positions. Because of this, we shall say that the quadrisection construction described above is periodic with period .

Similarly, if one performs an octisection of the angle by bisecting the quadrisection, one can verify that this octisection is periodic with period ; it takes four full rotations of around before the configuration returns to where it started. More generally, one can show

Proposition 4 Any construction of straightedge and compass from the points is periodic with period equal to a power of .

The reason for this, ultimately, is because any two circles or lines will intersect each other in at most two points, and so at each step of a straightedge-and-compass construction there is an ambiguity of at most . Each rotation of around can potentially flip one of these points to the other, but then if one rotates again, the point returns to its original position, and then one can analyse the next point in the construction in the same fashion until one obtains the proposition.

But now consider a putative trisection operation, that starts with an arbitrary angle and somehow uses some sequence of straightedge and compass constructions to end up with a trisecting line :

What is the period of this construction? If we continuously rotate around , we observe that a full rotations of only causes the trisecting line to rotate by a third of a full rotation (i.e. by ):

Because of this, we see that the period of any construction that contains must be a multiple of . But this contradicts Proposition 4 and Lemma 2.

Below the fold, I will make the above proof rigorous. Unfortunately, in doing so, I had to again leave the world of high-school mathematics, as one needs a little bit of algebraic geometry and complex analysis to resolve the issues with singularities that we saw in the above sketch. Still, I feel that at an intuitive level at least, this argument is more geometric and accessible than the Galois-theoretic argument (though anyone familiar with Galois theory will note that there is really not that much difference between the proofs, ultimately, as one has simply replaced the Galois group with a closely related monodromy group instead).

The Lucas-Lehmer test for Mersenne primes

In the last few weeks, the Great Internet Mersenne Prime Search (GIMPS) announced the discovery of two new Mersenne primes, both over ten million digits in length, including one discovered by the computing team right here at UCLA (see this page for more information).  [I was not involved in this computing effort.]  As for the question “Why do we want to find such big primes anyway?”, see this page, though this is not the focus of my post today.

The GIMPS approach to finding Mersenne primes relies of course on modern computing power, parallelisation, and efficient programming, but the number-theoretic heart of it – aside from some basic optimisation tricks such as fast multiplication and preliminary sieving to eliminate some obviously non-prime Mersenne number candidates – is the Lucas-Lehmer primality test for Mersenne numbers, which is much faster for this special type of number than any known general-purpose (deterministic) primality test (such as, say, the AKS test).  This test is easy enough to describe, and I will do so later in this post, and also has some short elementary proofs of correctness; but the proofs are sometimes presented in a way that involves pulling a lot of rabbits out of hats, giving the argument a magical feel rather than a natural one.  In this post, I will try to explain the basic ideas that make the primality test work, seeking a proof which is perhaps less elementary and a little longer than some of the proofs in the literature, but is perhaps a bit better motivated.