I have blogged a number of times in the past about the relationship between finitary (or “hard”, or “quantitative”) analysis, and infinitary (or “soft”, or “qualitative”) analysis. One way to connect the two types of analysis is via compactness arguments (and more specifically, contradiction and compactness arguments); such arguments can convert qualitative properties (such as continuity) to quantitative properties (such as bounded), basically because of the fundamental fact that continuous functions on a compact space are bounded (or the closely related fact that sequentially continuous functions on a sequentially compact space are bounded).
A key stage in any such compactness argument is the following: one has a sequence of “quantitative” or “finitary” objects or spaces, and one has to somehow end up with a “qualitative” or “infinitary” limit object or limit space. One common way to achieve this is to embed everything inside some universal space and then use some weak compactness property of that space, such as the Banach-Alaoglu theorem (or its sequential counterpart). This is for instance the idea behind the Furstenberg correspondence principle relating ergodic theory to combinatorics; see for instance this post of mine on this topic.
However, there is a slightly different approach, which I will call ultralimit analysis, which proceeds via the machinery of ultrafilters and ultraproducts; typically, the limit objects one constructs are now the ultraproducts (or ultralimits) of the original objects . There are two main facts that make ultralimit analysis powerful. The first is that one can take ultralimits of arbitrary sequences of objects, as opposed to more traditional tools such as metric completions, which only allow one to take limits of Cauchy sequences of objects. The second fact is Los’s theorem, which tells us that is an elementary limit of the (i.e. every sentence in first-order logic which is true for the for large enough, is true for ). This existence of elementary limits is a manifestation of the compactness theorem in logic; see this earlier blog post for more discussion. So we see that compactness methods and ultrafilter methods are closely intertwined. (See also my earlier class notes for a related connection between ultrafilters and compactness.)
Ultralimit analysis is very closely related to nonstandard analysis. I already discussed some aspects of this relationship in an earlier post, and will expand upon it at the bottom of this post. Roughly speaking, the relationship between ultralimit analysis and nonstandard analysis is analogous to the relationship between measure theory and probability theory.
To illustrate how ultralimit analysis is actually used in practice, I will show later in this post how to take a qualitative infinitary theory – in this case, basic algebraic geometry – and apply ultralimit analysis to then deduce a quantitative version of this theory, in which the complexity of the various algebraic sets and varieties that appear as outputs are controlled uniformly by the complexity of the inputs. The point of this exercise is to show how ultralimit analysis allows for a relatively painless conversion back and forth between the quantitative and qualitative worlds, though in some cases the quantitative translation of a qualitative result (or vice versa) may be somewhat unexpected. In an upcoming paper of myself, Ben Green, and Emmanuel Breuillard (announced in the previous blog post), we will rely on ultralimit analysis to reduce the messiness of various quantitative arguments by replacing them with a qualitative setting in which the theory becomes significantly cleaner.
For sake of completeness, I also redo some earlier instances of the correspondence principle via ultralimit analysis, namely the deduction of the quantitative Gromov theorem from the qualitative one, and of Szemerédi’s theorem from the Furstenberg recurrence theorem, to illustrate how close the two techniques are to each other.
— 1. Ultralimit analysis —
In order to perform ultralimit analysis, we need to prepare the scene by deciding on three things in advance:
- The standard universe of standard objects and spaces.
- A distinction between ordinary objects, and spaces.
- A choice of non-principal ultrafilter .
We now discuss each of these three preparatory ingredients in turn.
We assume that we have a standard universe or superstructure which contains all the “standard” sets, objects, and structures that we ordinarily care about, such as the natural numbers, the real numbers, the power set of real numbers, the power set of the power set of real numbers, and so forth. For technical reasons, we have to limit the size of this universe by requiring that it be a set, rather than a class; thus (by Russell’s paradox), not all sets will be standard (e.g. itself will not be a standard set). However, in many areas of mathematics (particularly those of a “finitary” or at most “countable” flavour, or those based on finite-dimensional spaces such as ), the type of objects considered in a field of mathematics can often be contained inside a single set . For instance, the class of all groups is too large to be a set. But in practice, one is only interested in, say, groups with an at most countable number of generators, and if one then enumerates these generators and considers their relations, one can identify each such group (up to isomorphism) to one in some fixed set of model groups. One can then take to be the collection of these groups, and the various objects one can form from these groups (e.g. power sets, maps from one group to another, etc.). Thus, in practice, the requirement that we limit the scope of objects to care about is not a significant limitation. (If one does not want to limit one’s scope in this fashion, one can proceed instead using the machinery of Grothendieck universes.)
It is important to note that while we primarily care about objects inside the standard universe , we allow ourselves to use objects outside the standard universe (but still inside the ambient set theory) whenever it is convenient to do so. The situation is analogous to that of using complex analysis to solve real analysis problems; one may only care about statements that have to do with real numbers, but sometimes it is convenient to introduce complex numbers within the proofs of such statements. (More generally, the trick of passing to some completion of one’s original structure in order to more easily perform certain mathematical arguments is a common theme throughout modern mathematics.)
We will also assume that there is a distinction between two types of objects in this universe: spaces, which are sets that can contain other objects, and ordinary objects, which are all the objects that are not spaces. Thus, for instance, a group element would typically be considered an ordinary object, whereas a group itself would be a space that group elements can live in. It is also convenient to view functions between two spaces as itself a type of ordinary object (namely, an element of a space of maps from to ). The precise concept of what constitutes a space, and what constitutes an ordinary object, is somewhat hard to formalise, but the basic rule of thumb to decide whether an object should be a space or not is to ask whether mathematical phrases such as , , or are likely to make useful sense. If so, then is a space; otherwise, is an ordinary object.
Examples of spaces include sets, groups, rings, fields, graphs, vector spaces, topological spaces, metric spaces, function spaces, measure spaces, dynamical systems, and operator algebras. Examples of ordinary objects include points, numbers, functions, matrices, strings, and equations.
Remark 1 Note that in some cases, a single object may seem to be both an ordinary object and a space, but one can often separate the two roles that this object is playing by making a sufficiently fine distinction. For instance, in Euclidean geometry, a line in is both an ordinary object (it is one of the primitive concepts in that geometry), but it can also be viewed as a space of points. In such cases, it becomes useful to distinguish between the abstract line , which is the primitive object, and its realisation as a space of points in the Euclidean plane. This type of distinction is quite common in algebraic geometry, thus, for instance, the imaginary circle has an empty realisation in the real plane , but has a non-trivial realisation in the complex plane (or over finite fields), and so we do not consider (as an abstract algebraic variety) to be empty. Similarly, given a function , we distinguish between the function itself (as an abstract object) and the graph of that function over some given domain .
We also fix a nonprincipal ultrafilter on the natural numbers. Recall that this is a collection of subsets of with the following properties:
- No finite set lies in .
- If is in , then any subset of containing is in .
- If lie in , then also lies in .
- If , then exactly one of and lies in .
Given a property which may be true or false for each natural number , we say that is true for sufficiently close to if the set lies in . The existence of a non-principal ultrafilter is guaranteed by the ultrafilter lemma, which can be proven using the axiom of choice.
Remark 2 One can view as a point in the Stone-Čech compactification, in which case “for sufficiently close to ” acquires the familiar topological meaning “for all in a neighbourhood of “.
We can use this ultrafilter to take limits of standard objects and spaces. Indeed, given any two sequences , of standard ordinary objects, we say that such sequences are equivalent if we have for all sufficiently close to . We then define the ultralimit of a sequence to be the equivalence class of (in the space of all sequences in the universe). In other words, we have
if and only if for all sufficiently close to .
The ultralimit lies outside the standard universe , but is still constructible as an object in the ambient set theory (because was assumed to be a set). Note that we do not need to be well-defined for all for the limit to make sense; it is enough that is well-defined for all sufficiently close to .
If , we refer to the sequence of ordinary objects as a model for the limit . Thus, any two models for the same limit object will agree in a sufficiently small neighbourhood of .
Similarly, given a sequence of standard spaces , one can form the ultralimit (or ultraproduct) , defined as the collection of all ultralimits of sequences , where for all (or for all sufficiently close to ). Again, this space will lie outside the standard universe, but is still a set. (This will not conflict with the notion of ultralimits for ordinary objects, so long as one always takes care to keep spaces and ordinary objects separate.) If , we refer to the sequence of spaces as a model for .
As a special case of an ultralimit, given a single space , its ultralimit is known as the ultrapower of and will be denoted .
Remark 3 One can view as a type of completion of , much as the reals are the metric completion of the rationals. Indeed, just as the reals encompass all limits of Cauchy sequences in the rationals, up to equivalence, the ultrapower encompass all limits of arbitrary sequences in , up to agreement sufficiently close to . The ability to take limits of arbitrary sequences, and not merely Cauchy sequences or convergent sequences, is the underlying source of power of ultralimit analysis. (This ability ultimately arises from the universal nature of the Stone-Čech compactification , as well as the discrete nature of , which makes all sequences continuous.)
Of course, we embed the rationals into the reals by identifying each rational with its limit . In a similar spirit, we identify every standard ordinary object with its ultralimit . In particular, a standard space is now identified with a subspace of . When is finite, it is easy to see that this embedding of to is surjective; but for infinite , the ultrapower is significantly larger than itself.
Remark 4 One could collect the ultralimits of all the ordinary objects and spaces in the standard universe and form a new structure, the nonstandard universe , which one can view as a completion of the standard universe, in much the same way that the reals are a completion of the rationals. However, we will not have to explicitly deal with this nonstandard universe and will not discuss it again in this post.
In nonstandard analysis, an ultralimit of standard ordinary object in a given class is referred to as (or more precisely, models) a nonstandard object in that class. To emphasise the slightly different philosophy of ultralimit analysis, however, I would like to call these objects limit objects in that class instead. Thus, for instance:
- An ultralimit of standard natural numbers is a limit natural number (or a nonstandard natural number, or an element of );
- An ultralimit of standard real numbers is a limit real number (or a nonstandard real number, or a hyperreal, or an element of );
- An ultralimit of standard functions between two sets is a limit function (also known as an internal function, or a nonstandard function);
- An ultralimit of standard continuous functions between two topological spaces is a limit continuous function (or internal continuous function, or nonstandard continuous function);
Clearly, all standard ordinary objects are limit objects of the same class, but not conversely.
Similarly, ultralimits of spaces in a given class will be referred to limit spaces in that class (in nonstandard analysis, they would be called nonstandard spaces or internal spaces instead). For instance:
- An ultralimit of standard sets is a limit set (or internal set, or nonstandard set);
- An ultralimit of standard groups is a limit group (or internal group, or nonstandard group);
- An ultralimit of standard measure spaces is a limit measure space (or internal measure space, or nonstandard measure space);
Note that finite standard spaces will also be limit spaces of the same class, but infinite standard spaces will not. For instance, is a standard group, but is not a limit group, basically because it does not contain limit integers such as . However, is contained in the limit group . The relationship between standard spaces and limit spaces is analogous to that between incomplete spaces and complete spaces in various fields of mathematics (e.g. in metric space theory or field theory).
Any operation or result involving finitely many standard objects, spaces, and first-order quantifiers carries over to their nonstandard or limit counterparts (the formal statement of this is Los’s theorem). For instance, the addition operation on standard natural numbers gives an addition operation on limit natural numbers, defined by the formula
It is easy to see that this is a well-defined operation on the limit natural numbers , and that the usual properties of addition (e.g. the associative and commutative laws) carry over to this limit (much as how the associativity and commutativity of addition on the rationals automatically implies the same laws of arithmetic for the reals). Similarly, we can define the other arithmetic and order relations on limit numbers: for instance we have
if and only if for all sufficiently close to , and similarly define , etc. Note from the definition of an ultrafilter that we still have the usual order trichotomy: given any two limit numbers , exactly one of , , and is true.
Example 1 The limit natural number is larger than all standard natural numbers, but is even larger still.
The following two exercises should give some intuition of how Los’s theorem is proved, and what it could be useful for:
Exercise 1 Show that the following two formulations of Goldbach’s conjecture are equivalent:
- Every even natural number greater than two is the sum of two primes.
- Every even limit natural number greater than two is the sum of two prime limit natural numbers.
Here, we define a limit natural number to be even if we have for some limit natural number , and a limit natural number to be prime if it is greater than but cannot be written as the product of two limit natural numbers greater than .
Exercise 2 Let be a sequence of algebraically closed fields. Show that the ultralimit is also an algebraically closed field. In other words, every limit algebraically closed field is an algebraically closed field.
Given an ultralimit of functions , we can view as a function from the limit space to the limit space by the formula
Again, it is easy to check that this is well-defined. Thus every limit function from a limit space to a limit space is a function from to , but the converse is not true in general.
One can easily show that limit sets behave well with respect to finitely many boolean operations; for instance, the intersection of two limit sets and is another limit set, namely . However, we caution that the same is not necessarily true for infinite boolean operations; the countable union or intersection of limit sets need not be a limit set. (For instance, each individual standard integer in is a limit set, but their union is not.) Indeed, there is an analogy between the limit subsets of a limit set, and the clopen subsets of a topological space (or the constructible sets in an algebraic variety).
By the same type of arguments used to show Exercise 2, one can check that every limit group is a group (albeit one that usually lies outside the standard universe ), every limit ring is a ring, every limit field is a field, etc.
The situation with vector spaces is a little more interesting. The ultraproduct of a collection of standard vector spaces over is a vector space over the larger field , because the various scalar multiplication operations over the standard reals become a scalar multiplication operation over the limit reals. Of course, as the standard reals are a subfield of the limit reals , is also a vector space over the standard reals ; but when viewed this way, the properties of the are not automatically inherited by . For instance, if each of the are -dimensional over for some fixed finite , then is -dimensional over the limit reals , but is infinite dimensional over the reals .
Now let be a limit finite set, i.e. a limit of finite sets . Every finite set is a limit finite set, but not conversely; for instance, is a limit finite set which has infinite cardinality. On the other hand, because every finite set has a cardinality which is a standard natural number, we can assign to every limit finite set a limit cardinality which is a limit natural number, by the formula
This limit cardinality inherits all of the first-order properties of ordinary cardinality. For instance, we have the inclusion-exclusion formula
for any two limit finite sets; this follows from the inclusion-exclusion formula for standard finite sets by an easy limiting argument.
It is not hard to show that is finite if and only if the are bounded for sufficiently close to . Thus, we see that one feature of passage to ultralimits is that it converts the term “bounded” to “finite”, while the term “finite” becomes “limit finite”. This makes ultralimit analysis useful for deducing facts about bounded quantities from facts about finite quantities. We give some examples of this in the next section.
In a similar vein, an ultralimit of standard metric spaces yields a limit metric space, thus for instance is now a metric taking values in the limit reals. Now, if the spaces were uniformly bounded, then the limit space would be bounded by some (standard) real diameter. From the Bolzano-Weierstrass theorem we see that every bounded limit real number has a unique standard part which differs from by an infinitesimal, i.e. a limit real number of the form where converges to zero in the classical sense. As a consequence, the standard part of the limit metric function is a genuine metric function . The resulting metric space is often referred to as an ultralimit of the original metric spaces , although strictly speaking this conflicts slightly with the notation here, because we consider to be the ultralimit instead.
— 2. Application: quantitative algebraic geometry —
As a sample application of the above machinery, we shall use ultrafilter analysis to quickly deduce some quantitative (but not explicitly effective) algebraic geometry results from their more well-known qualitative counterparts. Significantly stronger results than the ones given here can be provided by the field of effective algebraic geometry, but that theory is somewhat more complicated than the classical qualitative theory, and the point I want to stress here is that one can obtain a “cheap” version of this effective algebraic geometry from the qualitative theory by a straightforward ultrafilter argument. I do not know of a comparably easy way to get such ineffective quantitative results without the use of ultrafilters or closely related tools (e.g. nonstandard analysis or elementary limits).
We first recall a basic definition:
Definition 1 (Algebraic set) An (affine) algebraic set over an algebraically closed field is a subset of , where is a positive integer, of the form
where are a finite collection of polynomials.
Now we turn to the quantitative theory, in which we try to control the complexity of various objects. Let us say that an algebraic set in has complexity at most if , and one can express the set in the form (1) where , and each of the polynomials has degree at most . We can then ask the question of to what extent one can make the above qualitative algebraic statements quantitative. For instance, it is known that a dimension algebraic set is finite; but can we bound how finite it is in terms of the complexity of that set? We are particularly interested in obtaining bounds here which are uniform in the underlying field .
One way to do so is to open up an algebraic geometry textbook and carefully go through the proofs of all the relevant qualitative facts, and carefully track the dependence on the complexity. For instance, one could bound the cardinality of a dimension algebraic set using Bézout’s theorem. But here, we will use ultralimit analysis to obtain such quantitative analogues “for free” from their qualitative counterparts. The catch, though, is that the bounds we obtain are ineffective; they use the qualitative facts as a “black box”, and one would have to go through the proof of these facts in order to extract anything better.
To begin the application of ultrafilter analysis, we use the following simple lemma.
Lemma 2 (Ultralimits of bounded complexity algebraic sets are algebraic) Let be a dimension. Suppose we have a sequence of algebraic sets over algebraically closed fields , whose complexity is bounded by a quantity which is uniform in . Then if we set and , then is an algebraically closed field and is an algebraic set (also of complexity at most ).
Conversely, every algebraic set in is the ultralimit of algebraic sets in of bounded complexity.
Proof: The fact that is algebraically closed comes from Exercise 2. Now we look at the algebraic sets . By adding dummy polynomials if necessary, we can write
where the of degree at most .
We can then take ultralimits of the to create polynomials of degree at most . One easily verifies on taking ultralimits that
and the first claim follows. The converse claim is proven similarly.
Ultralimits preserve a number of key algebraic concepts (basically because such concepts are definable in first-order logic). We first illustrate this with the algebraic geometry concept of dimension. It is known that every non-empty algebraic set in has a dimension , which is an integer between and , with the convention that the empty set has dimension . There are many ways to define this dimension, but one way is to proceed by induction on the dimension as follows. A non-empty algebraic subset of has dimension . Now if , we say that an algebraic set has dimension for some if the following statements hold:
- For all but finitely many , the slice either all have dimension , or are all empty.
- For the remaining , the slice has dimension at most . If the generic slices were all empty, then one of the exceptional has to have dimension exactly .
Informally, has dimension iff a generic slice of has dimension .
It is a non-trivial fact to show that every algebraic set in does indeed have a well-defined dimension between and .
Now we see how dimension behaves under ultralimits.
Lemma 3 (Continuity of dimension) Suppose that are algebraic sets over various algebraically closed fields of uniformly bounded complexity, and let be the limiting algebraic set given by Lemma 2. Then . In other words, we have for all sufficiently close to .
Proof: One could obtain this directly from Los’s theorem, but it is instructive to do this from first principles.
We induct on dimension . The case is trivial, so suppose that and the claim has already been shown for . Write for the dimension of . If , then is empty and so must be empty for all sufficiently close to , so suppose that . By the construction of dimension, the slice all have dimension (or are all empty) for all but finitely many values of . Let us assume that these generic slices all have dimension ; the other case is treated similarly and is left to the reader. As is the ultralimit of the , we can write for each . We claim that for sufficiently close to , the slices have dimension whenever . Indeed, suppose that this were not the case. Carefully negating the quantifiers (and using the ultrafilter property), we see that for sufficiently close to , we can find such that has dimension different from . Taking ultralimits and writing , we see from the induction hypothesis that has dimension different from , contradiction.
We have shown that for sufficiently close to , all but finitely many slices of have dimension , and thus by the definition of dimension, has dimension , and the claim follows.
We can use this to deduce quantitative algebraic geometry results from qualitative analogues. For instance, from the definition of dimension we have
Using ultrafilter analysis, we immediately obtain the following quantitative analogue:
Lemma 5 (Quantitative Bezout-type theorem) Let be an algebraic set of dimension and complexity at most over a field . Then the cardinality is bounded by a quantity depending only on (in particular, it is independent of ).
Proof: By passing to the algebraic closure, we may assume that is algebraically closed.
Suppose this were not the case. Carefully negating the quantifiers (and using the axiom of choice), we may find a sequence of dimension algebraic sets and uniformly bounded complexity over algebraically closed fields , such that as . We pass to an ultralimit to obtain a limit algebraic set , which by Lemma 3 has dimension , and is thus finite by Lemma 4. But then this forces to be bounded for sufficiently close to (indeed we have in such a neighbourhood), contradiction.
Remark 5 Note that this proof gives absolutely no bound on in terms of ! One can get such a bound by using more effective tools, such as the actual Bezout theorem, but this requires more actual knowledge of how the qualitative algebraic results are proved. If one only knows the qualitative results as a black box, then the ineffective quantitative result is the best one can do.
Now we give another illustration of the method. The following fundamental result in algebraic geometry is known:
Using ultralimit analysis, one can convert this qualitative result into an ostensibly stronger quantitative version:
Lemma 7 (Quantitative Noetherian condition) Let be a function. Let be a sequence of properly nested algebraic sets in for some algebraically closed field , such that each has complexity at most . Then is bounded by for some depending only on (in particular, it is independent of ).
Remark 6 Specialising to the case when is a constant , we see that there is an upper bound on proper nested sequences of algebraic sets of bounded complexity; but the statement is more powerful than this because we allow to be non-constant. Note that one can easily use this strong form of the quantitative Noetherian condition to recover Lemma 6 (why?), but if one only knew Lemma 7 in the constant case then this does not obviously recover Lemma 6.
Proof: Note that is bounded by , so it will suffice to prove this claim for a fixed .
Fix . Suppose the claim failed. Carefully negating all the quantifiers (and using the axiom of choice), we see that there exists an , a sequence of algebraically closed fields, a sequence going to infinity, and sequences
of properly nested algebraic sets in , with each having complexity at most .
We take an ultralimit of everything that depends on , creating an algebraically closed field , and an infinite sequence
of properly nested algebraic sets in . (In fact, we could continue this sequence into a limit sequence up to the unbounded limit number , but we will not need this overspill here.) But this contradicts Lemma 6.
Again, this argument gives absolutely no clue as to how is going to depend on . (Indeed, I would be curious to know what this dependence is exactly.)
Let us give one last illustration of the ultralimit analysis method, which contains an additional subtlety. Define an algebraic variety to be an algebraic set which is irreducible, which means that it cannot be expressed as the union of two proper subalgebraic sets. This notation is stable under ultralimits:
Lemma 8 (Continuity of irreducibility) Suppose that are algebraic sets over various algebraically closed fields of uniformly bounded complexity, and let be the limiting algebraic set given by Lemma 2. Then is an algebraic variety if and only if is an algebraic variety for all sufficiently close to .
However, this lemma is somewhat harder to prove than previous ones, because the notion of irreducibility is not quite a first order statement. The following exercises show the limit of what one can do without using some serious algebraic geometry:
Exercise 3 Let the notation and assumptions be as in Lemma 8. Show that if is not an algebraic variety, then is a not algebraic variety for all sufficiently close to .
Exercise 4 Let the notation and assumptions be as in Lemma 8. Call an algebraic set -irreducible if it cannot be expressed as the union of two proper algebraic sets of complexity at most . Show that if is an algebraic variety, then for every , is -irreducible for all sufficiently close to .
These exercises are not quite strong enough to give Lemma 8, because -irreducibility is a weaker concept than irreducibility. However, one can do better by applying some further facts in algebraic geometry. Given an algebraic set of dimension in an affine space , one can assign a degree , which is a positive integer such that for generic -dimensional affine subspaces of , which means that belongs to the affine Grassmannian of -dimensional affine subspaces of , after removing an algebraic subset of of dimension strictly less than that of . It is a standard fact of algebraic geometry that every algebraic set can be assigned a degree. Somewhat less trivially, the degree controls the complexity:
Proof: (We thank Jordan Ellenberg and Ania Otwinowska for this argument.) It suffices to show that can be cut out by polynomials of degree , since the space of polynomials of degree that vanish on is a vector space of dimension bounded only by and .
Let have dimension . We pick a generic affine subspace of of dimension , and consider the cone formed by taking all the union of all the lines joining a point in to a point in . This is an algebraic image of and is thus generically an algebraic set of dimension , i.e. a hypersurface. Furthermore, as has degree , it is not hard to see that has degree as well. Since a hypersurface is necessarily cut out by a single polynomial, this polynomial must have degree .
To finish the claim, it suffices to show that the intersection of the as varies is exactly . Clearly, this intersection contains . Now let be any point not in . The cone of over can be viewed as an algebraic subset of the projective space of dimension ; meanwhile, the cone of a generic subspace of dimension is a generic subspace of of the same dimension. Thus, for generic , these two cones do not intersect, and thus lies outside , and the claim follows.
Remark 7 There is a stronger theorem that asserts that if the degree of a scheme in is bounded, then the complexity of that scheme is bounded as well. The main difference between a variety and a scheme here is that for a scheme, we not only specify the set of points cut out by the scheme, but also the ideal of functions that we want to think of as vanishing on that set. This theorem is significantly more difficult than the above result; it is Corollary 6.11 of Kleiman’s SGA6 article.
Given this theorem, we can now prove Lemma 8.
Proof: In view of Exercise 3, it suffices to show that if is irreducible, then the are irreducible for sufficiently close to .
The algebraic set has some dimension and degree , thus for generic affine -dimensional subspaces of . Undoing the limit using Lemma 2 and Lemma 3 (adapted to the Grassmannian rather than to affine space), we see that for sufficiently close to , for generic affine -dimensional subspaces of . In other words, has degree , and thus by Theorem 9, any algebraic variety of of the same dimension as will have complexity bounded by uniformly in . Let be a -dimensional algebraic subvariety of , and let be the ultralimit of the . Then by Lemma 2, Lemma 3 and the uniform complexity bound, is a -dimensional algebraic subset of , and thus must equal all of by irreducibility of . But this implies that for all sufficiently close to , and the claim follows.
We give a sample application of this result. From the Noetherian condition we easily obtain
Lemma 10 (Qualitative decomposition into varieties) Every algebraic set can be expressed as a union of finitely many algebraic varieties.
Using ultralimit analysis, we can make this quantitative:
Lemma 11 (Quantitative decomposition into varieties) Let be an algebraic set of complexity at most over an algebraically closed field . Then can be expressed as the union of at most algebraic varieties of complexity at most , where depends only on .
Proof: As is bounded by , it suffices to prove the claim for a fixed .
Fix and . Suppose the claim failed. Carefully negating all the quantifiers (and using the axiom of choice), we see that there exists a sequence of uniformly bounded complexity, such that cannot be expressed as the union of at most algebraic varieties of complexity at most . Now we pass to an ultralimit, obtaining a limit algebraic set . As discussed earlier, is an algebraic set over an algebraically closed field and is thus expressible as the union of a finite number of algebraic varieties . By Lemma 2 and Lemma 8, each is an ultralimit of algebraic varieties of bounded complexity. The claim follows.
— 3. Application: Quantitative Gromov theorem —
Let us now make the observation (already observed in Gromov’s original paper) that this theorem implies (and is in fact equivalent to) a quantitative version:
Theorem 13 (Quantitative Gromov theorem) For every there exists such that if is generated by a finite set with the growth condition for all , then is virtually nilpotent, and furthermore it has a nilpotent subgroup of step and index at most for some depending only on . Here is the ball of radius generated by the set .
Proof: We use ultralimit analysis. Suppose this theorem failed. Carefully negating the quantifiers, we find that there exists , as well as a sequence of groups generated by a finite set such that for all , and such that does not contain any nilpotent subgroup of step and index at most .
Now we take ultralimits, setting and . As the have cardinality uniformly bounded (by ), is finite. The set need not generate , but it certainly generates some subgroup of this group. Since for all and all , we see on taking ultralimits that for all . Thus is of polynomial growth, and is thus virtually nilpotent.
Now we need to undo the ultralimit, but this requires a certain amount of preparation. We know that contains a finite index nilpotent subgroup . As is finitely generated, the finite index subgroup is also. (Proof: for large enough, will intersect every coset of . As a consequence, one can describe the action of on the finite set using only knowledge of . In particular, generates a finite index subgroup. Increasing , the index of this subgroup is non-increasing, and thus must eventually stabilise. At that point, we generate all of .) Let be a set of generators for . Since is nilpotent of some step , all commutators of of length at least vanish.
Writing as an ultralimit of , we see that the are finite subsets of which generate some subgroup . Since all commutators of of length at least vanish, the same is true for for close enough to , and so is nilpotent for such with step bounded uniformly in .
Finally, if we let be large enough that intersects every coset of , then we can cover by a product of and some elements of (which are of course finite products of elements in and their inverses). Undoing the ultralimit, we see that for sufficiently close to , we can cover by the product of and some elements of . Iterating this we see that we can cover all of by times , and so has finite index bounded uniformly in . But this contradicts the construction of .
Remark 8 As usual, the argument gives no effective bound on . Obtaining such an effective bound is in fact rather non-trivial; see this paper of Yehuda Shalom and myself for further discussion.
— 4. Application: Furstenberg correspondence principle —
Let me now redo another application of the correspondence principle via ultralimit analysis. We will begin with the following famous result of Furstenberg:
We then use this theorem and ultralimit analysis to derive the following well-known result of Szemerédi:
Theorem 15 (Szemerédi’s theorem) Every set of integers of positive upper density contains arbitrarily long arithmetic progressions.
Proof: Suppose this were not the case. Then there exists and a set of positive upper density with no progressions of length . Unpacking the definition of positive upper density, this means that there exists and a sequence such that
for all . We pass to an ultralimit, introducing the limit natural number and using the ultrapower (note that is a space, not an ordinary object). Then we have
where the cardinalities are in the limit sense. Note also that has no progressins of length .
Consider the space of all boolean combinations of shifts of , where ranges over (standard) integers, thus for instance
would be such a set. We call such sets definable sets. We give each such definable set a limit measure
This measure takes values in the limit interval and is clearly a finitely additive probability measure. It is also nearly translation invariant in the sense that
for any standard integer , where is an infinitesimal (i.e. a limit real number which is smaller in magnitude than any positive standard real number). In particular, the standard part of is a finitely additive standard probability measure. Note from construction that .
Now we convert this finitely additive measure into a countably additive one. Let be the set of all subsets of the integers. This is a compact metrisable space, which we endow with the Borel -algebra and the standard shift . The Borel -algebra is generated by the clopen sets in this space, which are boolean combinations of , where is the basic cylinder set . Each clopen set can be assigned a definable set in by mapping to and then extending by boolean combinations. The finitely additive probability measure on definable sets then pulls back to a finitely additive probability measure on clopen sets in . Applying the Carathéodory extension theorem (taking advantage of the compactness of ), we can extend this finitely additive measure to a countably additive Borel probability measure.
By construction, . Applying Theorem 14, we can find such that is non-empty. This implies that is non-empty, and so contains an arithmetic progression of length , a contradiction.
Note that the above argument is nearly identical to the usual proof of the correspondence principle, which uses Prokhorov’s theorem instead of ultrafilters. The measure constructed above is essentially the Loeb measure for the ultraproduct.
— 5. Relationship with nonstandard analysis —
Ultralimit analysis is extremely close to, but subtly different from, nonstandard analysis, because of a shift of emphasis and philosophy. The relationship can be illustrated by the following table of analogies:
|Digits||Strings of digits||Numbers|
|Symbols||Strings of symbols||Sentences|
|Set theory||Finite von Neumann ordinals||Peano arithmetic|
|Rational numbers||Real numbers|
|Real analysis||Analysis on||Complex analysis|
|Euclidean plane geometry|
|Coordinate chart atlases||Manifolds|
|Algebra||Sheaves of rings||Schemes|
|Deterministic theory||Measure theory||Probability theory|
|Probability theory||Von Neumann algebras||Noncommutative probability theory|
|Classical mechanics||Hilbert space mechanics||Quantum mechanics|
|Finitary analysis||Asymptotic analysis||Infinitary analysis|
|Combinatorics||Correspondence principle||Ergodic theory|
|Quantitative analysis||Compactness arguments||Qualitative analysis|
|Standard analysis||Ultralimit analysis||Nonstandard analysis|
(Here is the algebraic completion of the reals, but is the metric completion of the rationals.)
In the first column one has a “base” theory or concept, which implicitly carries with it a certain ontology and way of thinking, regarding what objects one really cares to study, and what objects really “exist” in some mathematical sense. In the second column one has a fancier theory than the base theory (typically a “limiting case”, a “generalisation”, or a “completion” of the base theory), but one which still shares a close relationship with the base theory, in particular largely retaining the ontological and conceptual mindset of that theory. In the third column one has a new theory, which is modeled by the theories in the middle column, but which is not tied to that model, or to the implicit ontology and viewpoint carried by that model. For instance, one can think of a complex number as an element of the algebraic completion of the reals, but one does not have to, and indeed in many parts of complex analysis or complex geometry one wants to ignore the role of the reals as much as possible. Similarly for other rows of the above table. See for instance these lecture notes of mine for further discussion of the distinction between measure theory and probability theory.
[The relationship between the second and third columns of the above table is also known as the map-territory relation.]
Returning to ultralimit analysis, this is a type of analysis which still shares close ties with its base theory, standard analysis, in that all the objects one considers are either standard objects, or ultralimits of such objects (and similarly for all the spaces one considers). But more importantly, one continues to think of nonstandard objects as being ultralimits of standard objects, rather than having an existence which is largely independent of the concept of base theory of standard analysis. This perspective is reversed in nonstandard analysis: one views the nonstandard universe as existing in its own right, and the fact that the standard universe can be embedded inside it is a secondary feature (albeit one which is absolutely essential if one is to use nonstandard analysis in any nontrivial manner to say something new about standard analysis). In nonstandard analysis, ultrafilters are viewed as one tool in which one can construct the nonstandard universe from the standard one, but their role in the subject is otherwise minimised. In contrast, the ultrafilter plays a prominent role in ultralimit analysis.
In my opinion, none of the three columns here are inherently “better” than the other two; but they do work together quite well. In particular, the middle column serves as a very useful bridge to carry results back and forth between the worlds of the left and right columns.