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 1Note 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 theabstract line, which is the primitive object, and itsrealisationas 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 2One 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 3One can view as a type ofcompletionof , 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 ofarbitrarysequences 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 4One could collect the ultralimits of all the ordinary objects and spaces in the standard universe and form a new structure, thenonstandard universe, which one can view as acompletionof 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); - etc.

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);
- etc.

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 1The 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 1Show 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

evenif we have for some limit natural number , and a limit natural number to beprimeif it is greater than but cannot be written as the product of two limit natural numbers greater than .

Exercise 2Let 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

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

Lemma 4 (Qualitative Bezout-type theorem)Every dimension algebraic variety is finite.

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 5Note 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:

Lemma 6 (Qualitative Noetherian condition)There does not exist an infinite decreasing sequence of algebraic sets in a affine space , in which each set is a proper subset of the previous one.

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 6Specialising 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 3Let the notation and assumptions be as in Lemma 8. Show that if isnotan algebraic variety, then is a not algebraic variety for all sufficiently close to .

Exercise 4Let the notation and assumptions be as in Lemma 8. Call an algebraic set-irreducibleif it cannot be expressed as the union of two proper algebraic sets of complexity at most . Show that ifisan 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:

Theorem 9 (Degree controls complexity)Let be an algebraic variety of of degree . Then has complexity at most for some constants depending only on .

*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 7There is a stronger theorem that asserts that if the degree of aschemein 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 — **

As a further illustration, I’ll redo an application of the correspondence principle from a previous post of mine. The starting point is the following famous theorem of Gromov:

Theorem 12 (Qualitative Gromov theorem)Every finitely generated group of polynomial growth is virtually nilpotent.

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 8As 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:

Theorem 14 (Furstenberg recurrence theorem)Let be a measure-preserving system, and let have positive measure. Let . Then there exists such that is non-empty.

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 | |

Matrices | Linear transformations | |

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.

## 41 comments

Comments feed for this article

1 February, 2010 at 5:12 pm

solrizeThis sounds sort of like a method I’ve heard of called “proof mining” from mathematical logic, though I don’t actually know anything about it. There is a stub wikipedia article about it, if that’s of any interest: http://en.wikipedia.org/wiki/Proof_mining .

3 February, 2010 at 9:43 am

Terence TaoUltralimit analysis suggests that proof mining is possible, but does not perform any proof mining

per se. Indeed, ultralimit analysis can take an infinitary qualitative resultas a black box(without knowing anything about how such a result is proved), and uses this to obtain a finitary quantitative (but ineffective) analogue of this result. In contrast, proof mining analyses theproofof the infinitary result and uses this to establish aneffectivequantitative counterpart.1 February, 2010 at 9:41 pm

JSEAwesome post.

At the end of the proof of Lemma 5: “But then this forces {A_\alpha} to be finite for {\alpha} sufficiently close to {\alpha_\infty}.” Do you mean “bounded,” not “finite” here?

[Corrected, thanks – T.]1 February, 2010 at 9:48 pm

JSEAlso, in the proof of Theorem 9, it would be more accurate to thank me for copying that argument out of Lazarsfeld’s book….

4 February, 2010 at 8:10 am

Anonymousanon

Dear Terry,

Does the ultralimit depend on the choice of a particular fixed

nonprinciple ultrafilter?

4 February, 2010 at 12:27 pm

AnonymousYes.

4 February, 2010 at 1:10 pm

AnonymousDear Terry,

To clarify my earlier question: How does the ultralimit depend on the choice

of the nonprincipal ultrafilter? For example, is there a huge number of non isomorphic versions of the hyperreals, or nonstandard completions of a given standard universe?

11 February, 2010 at 9:22 am

Terence TaoThis is discussed in the comments of my previous blog post:

https://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-management/

The short answer is yes, there are a large number of non-isomorphic completions; in general, two different ultrafilters will not be isomorphic to each other. But for the type of ultralimit analysis performed above, it is rare that one needs to know anything more specific about the ultrafilter one is using – they all give elementary limits, and this is usually all one needs. (When doing additive combinatorics via ultrafilters, though, it is often very convenient to use special ultrafilters adapted to the additive structure, such as idempotent ultrafilters.)

4 February, 2010 at 1:11 pm

JSE“Again, this argument gives absolutely no clue as to how {C_F} is going to depend on {F}. (Indeed, I would be curious to know what this dependence is exactly.)”

I think it could be pretty horrible. Suppose for instance that F is monotone nondecreasing. A_1 could be F(1) hyperplanes in k^F(1), i.e. the vanishing of the product of F(1) linear polynomials. Then strip out one of these hyperplanes to get A_2, another to get A_3, and so on, until you get to A_{F(1)}, which is a single hyperplane. Now take A_{F(1)+1} to be the intersection of this hyperplane with the vanishing locus of F(F(1)) linear forms. This is a union of F(F(1)) codimension-2 subspaces; now strip them out one at a time until you get to something around A_{F(F(1))}. And the next variety will be a union of F(F(F(1))) codim-3 subspaces, and so on. So I guess I’m saying that C_F must at least be on order of F(F(F(….F(1)))) where the iteration is itself carried out F(1) times.

6 February, 2010 at 3:08 pm

Terence TaoThanks Jordan! Actually that’s not too bad – polynomial type bounds on complexity lead to exponential type bounds on length of chain, exponential bounds on complexity lead to tower exponential type bounds on length, and so forth. At least the Ackermann hierarchy or worse (e.g. Goodstein sequences) are not involved…

6 February, 2010 at 2:53 pm

mishaIt seems in the “Definition 1 (Algebraic set) An (affine) algebraic set over an algebraically field” the word _algebraically_ is not correct. Unnecessary?

[Oops, the word “closed” was missing. Corrected, thanks. -T.]10 February, 2010 at 6:45 pm

OrrDear Terry,

Apropos “quantitative” algebraic geometry – did you ever think about the following problem:

Given an ideal , we know that there are polynomials such that every can be written as , where are polynomials. Now assume that there is some norm on the algebra of polynomials. Do there exist polynomials such that every can be written as , but now with the additional constraint that , where is some universal constant?

28 March, 2010 at 9:59 pm

254B, Notes 1: Equidistribution of polynomial sequences in torii « What’s new[…] cost of converting the finitary theory to an infinitary one. Ultralimit analysis was discussed in this previous blog post; we give a quick review […]

29 March, 2010 at 6:43 am

AnonymousIn Definition 1, it should be “algebraically closed field”.

[Corrected, thanks – T.]8 May, 2010 at 1:48 pm

254B, Lecture Notes 4: Equidistribution of polynomials over finite fields « What’s new[…] in a finitary setting rather than a nonstandard one, but the two approaches are equivalent; see this blog post for more […]

12 May, 2010 at 1:30 pm

Approximate subgroups of linear subgroups « What’s new[…] analogues of the basic theory of algebraic geometry (which we chose to obtain via ultrafilters, as discussed in this post), we rely on two basic tools. Firstly, we use a version of the pivot argument developed first by […]

13 June, 2010 at 2:42 am

Symposium “Abel Prize 2010” « Disquisitiones Mathematicae[…] to bound the number of elements of the finite set used to generate a given point , it is not effective because, for instance, there is no efficient method (to the best of my knowledge) to find explicit […]

18 September, 2010 at 11:29 am

AnonymousDear Terry,

just a stylistic remark on section 4: the argument is presented as a contradiction, but it’s actually a direct proof (“Let A have positive density, then we find E and conclude that A contains an arithmetic progression.”). I think it would be more pleasant to read in the direct style.

27 November, 2010 at 12:07 am

Nonstandard analysis as a completion of standard analysis « What’s new[…] are also discussed in more detail in this previous blog post. A fundamental theorem of Los asserts that the ultrapower is elementarily equivalent to : any […]

29 November, 2010 at 12:00 pm

Concentration compactness via nonstandard analysis « What’s new[…] basics of nonstandard analysis are reviewed in this previous blog post (and see also this later post on ultralimit analysis, as well as the most recent post on this topic). Very briefly, we will need to fix a non-principal […]

14 December, 2010 at 12:42 am

Ultrafilters in Ramsey theory « Annoying Precision[…] for automatically constructing infinitary results to nonconstructive but finitary ones. There is a post by Terence Tao discussing similar applications of ultraproducts as the one above; we will have more to say about […]

30 March, 2011 at 9:33 am

Higher order Fourier analysis « What’s new[…] on my graduate course in the topic, though it also contains material from some additional posts related to linear and higher order Fourier analysis on the blog. It is available online here. […]

5 July, 2011 at 2:49 pm

Polynomial bounds via nonstandard analysis « What’s new[…] we take ultralimits (see e.g. this previous blog post of a quick review of ultralimit analysis, which we will assume knowledge of in the argument that […]

15 October, 2011 at 10:58 am

254A, Notes 6: Ultraproducts as a bridge between hard analysis and soft analysis « What’s new[…] (Logical limit) If the are all distinct spaces (or elements or subsets of distinct spaces), with few morphisms connecting them together, then topological and categorical limits are often unavailable or unhelpful. In such cases, however, one can still tie together such objects using an ultraproduct construction (or similar device) to create a limiting object or limiting space that is a logical limit of the , in the sense that various properties of the (particularly those that can be phrased using the language of first-order logic) are preserved in the limit. As such, logical limits are often very well suited for the task of connecting finitary and infinitary mathematics together. Ultralimit type constructions are of course used extensively in logic (particularly in model theory), but are also popular in metric geometry. They can also be used in many of the previously mentioned areas of mathematics, such as algebraic geometry (as discussed in this previous post). […]

5 February, 2012 at 11:33 am

254B, Notes 5: Product theorems, pivot arguments, and the Larsen-Pink non-concentration inequality « What’s new[…] subvariety of (here we use the uniform complexity bound). One can also show that ; see Lemma 3 of this blog post. As such, we […]

2 April, 2012 at 4:55 pm

A cheap version of nonstandard analysis « What’s new[…] Below the fold, I would like to describe this cheap version of nonstandard analysis, which I think can serve as a pedagogical stepping stone towards fully nonstandard analysis, as it is formally similar to (though weaker than) fully nonstandard analysis, but on the other hand is closer in practice to standard analysis. As we shall see below, the relation between cheap nonstandard analysis and standard analysis is analogous in many ways to the relation between probabilistic reasoning and deterministic reasoning; it also resembles somewhat the preference in much of modern mathematics for viewing mathematical objects as belonging to families (or to categories) to be manipulated en masse, rather than treating each object individually. (For instance, nonstandard analysis can be used as a partial substitute for scheme theory in order to obtain uniformly quantitative results in algebraic geometry, as discussed for instance in this previous blog post.) […]

31 August, 2012 at 5:02 pm

The Lang-Weil bound « What’s new[…] one could obtain ineffective bounds on these quantities by an ultralimit argument, as discussed in this previous post, or equivalently by moving everything over to a nonstandard analysis framework; one could also […]

12 September, 2012 at 3:36 pm

Definable subsets over (nonstandard) finite fields, and almost quantifier elimination « What’s new[…] we have absolutely irreducible with dimension for close to (see Lemma 3 and Lemma 8 of this previous blog post), and so by the Lang-Weil bound (see this previous blog post) we […]

25 October, 2012 at 10:11 am

Walsh’s ergodic theorem, metastability, and external Cauchy convergence « What’s new[…] We will assume some familiarity with nonstandard analysis, as covered for instance in these previous blog posts. […]

14 November, 2012 at 9:42 am

Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets « What’s new[…] reduce to by an ultraproduct (or nonstandard analysis) construction, similar to that discussed in this previous post), the varieties are generically finite étale covers of , and the fibre product is then […]

14 March, 2013 at 1:17 pm

Rectification and the Lefschetz principle | What's new[…] be used as a bridge to connect quantitative and qualitative results (as discussed in these previous blog posts), we will deduce Theorem 3 from the following (well-known) qualitative […]

27 March, 2013 at 7:34 pm

An informal version of the Furstenberg correspondence principle | What's new[…] , and leads to the Furstenberg correspondence principle, discussed for instance in these previous blog posts. Such principles allow one to rigorously pass back and forth between the combinatorics of […]

8 June, 2013 at 2:19 am

Ramsey theorem and ultrafilters (II) | chorasimilarity[…] motivation is the fact that I don’t get why one has to reason by compactness and contradiction, so I am looking for a direct proof (which is of course still non […]

29 October, 2013 at 8:09 pm

A spectral theory proof of the algebraic regularity lemma | What's new[…] 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.) […]

7 December, 2013 at 4:05 pm

Ultraproducts as a Bridge Between Discrete and Continuous Analysis | What's new[…] notably “Ultraproducts as a bridge between hard analysis and soft analysis” and “Ultralimit analysis and quantitative algebraic geometry“‘. The text here has substantially more details than the talk; one may wish to skip all […]

20 July, 2015 at 8:23 pm

A nonstandard analysis proof of Szemeredi’s theorem | What's new[…] routine “compactness and contradiction” arguments (as discussed in this previous post), Theorem 1 can be deduced from the following nonstandard […]

17 April, 2016 at 5:48 am

simingtuDear Prof. Tao,

In Lemma, I can not see from the argument how one can derive that the quantity is independent of the field . Would you like to give any hint? Thank you very much.

17 April, 2016 at 10:10 am

Terence TaoI assume you are referring to Lemma 5. As stated in the blog post, the argument proceeds by contradiction. If, for a given , there does

notexist a quantity independent of for which the statement of Lemma 5 holds, then for each natural number one can find a field and dimension zero sets of complexity bounded by for which the cardinality of exceeds . Taking ultralimits one obtains a counterexample to Lemma 4. (This is a simple example of the basic “compactness and contradiction” argument that is used frequently when employing ultrafilter or nonstandard methods to establish a finitary result.)17 April, 2016 at 12:04 pm

easyProfessor Tao How do you remember what you wrote eons ago?

3 June, 2017 at 7:54 am

manhtuankhtnDear Prof. Tao, Could you please explain why every bounded limit real number x has a unique standard part? From the Bolzano-Weierstrass theorem we know that each bounded sequence in R has a convergent subsequence. But how can we guarantee that the index set is in the given ultrafilter? Thank you very much.

7 June, 2017 at 1:39 pm

Terence TaoHint: a bounded limit real number creates a Dedekind cut of the standard rationals, since every standard rational is either less than , or greater than or equal to . One can also repeat the _proof_ of the Bolzano-Weierstrass theorem (repeatedly dividing an interval into two subintervals), rather than using the standard Bolzano-Weierstrass theorem as a “black box”.