You are currently browsing the category archive for the ‘math.GT’ category.
How many groups of order four are there? Technically, there are an enormous number, so much so, in fact, that the class of groups of order four is not even a set, but merely a proper class. This is because any four objects can be turned into a group by designating one of the four objects, say , to be the group identity, and imposing a suitable multiplication table (and inversion law) on the four elements in a manner that obeys the usual group axioms. Since all sets are themselves objects, the class of four-element groups is thus at least as large as the class of all sets, which by Russell’s paradox is known not to itself be a set (assuming the usual ZFC axioms of set theory).
A much better question is to ask how many groups of order four there are up to isomorphism, counting each isomorphism class of groups exactly once. Now, as one learns in undergraduate group theory classes, the answer is just “two”: the cyclic group and the Klein four-group .
More generally, given a class of objects and some equivalence relation on (which one should interpret as describing the property of two objects in being “isomorphic”), one can consider the number of objects in “up to isomorphism”, which is simply the cardinality of the collection of equivalence classes of . In the case where is finite, one can express this cardinality by the formula
thus one counts elements in , weighted by the reciprocal of the number of objects they are isomorphic to.
Example 1 Let be the five-element set of integers between and . Let us say that two elements of are isomorphic if they have the same magnitude: . Then the quotient space consists of just three equivalence classes: , , and . Thus there are three objects in up to isomorphism, and the identity (1) is then just
Thus, to count elements in up to equivalence, the elements are given a weight of because they are each isomorphic to two elements in , while the element is given a weight of because it is isomorphic to just one element in (namely, itself).
Given a finite probability set , there is also a natural probability distribution on , namely the uniform distribution, according to which a random variable is set equal to any given element of with probability :
Given a notion of isomorphism on , one can then define the random equivalence class that the random element belongs to. But if the isomorphism classes are unequal in size, we now encounter a biasing effect: even if was drawn uniformly from , the equivalence class need not be uniformly distributed in . For instance, in the above example, if was drawn uniformly from , then the equivalence class will not be uniformly distributed in the three-element space , because it has a probability of being equal to the class or to the class , and only a probability of being equal to the class .
However, it is possible to remove this bias by changing the weighting in (1), and thus changing the notion of what cardinality means. To do this, we generalise the previous situation. Instead of considering sets with an equivalence relation to capture the notion of isomorphism, we instead consider groupoids, which are sets in which there are allowed to be multiple isomorphisms between elements in (and in particular, there are allowed to be multiple automorphisms from an element to itself). More precisely:
Definition 2 A groupoid is a set (or proper class) , together with a (possibly empty) collection of “isomorphisms” between any pair of elements of , and a composition map from isomorphisms , to isomorphisms in for every , obeying the following group-like axioms:
- (Identity) For every , there is an identity isomorphism , such that for all and .
- (Associativity) If , , and for some , then .
- (Inverse) If for some , then there exists an inverse isomorphism such that and .
We say that two elements of a groupoid are isomorphic, and write , if there is at least one isomorphism from to .
Example 3 Any category gives a groupoid by taking to be the set (or class) of objects, and to be the collection of invertible morphisms from to . For instance, in the category of sets, would be the collection of bijections from to ; in the category of linear vector spaces over some given base field , would be the collection of invertible linear transformations from to ; and so forth.
Every set equipped with an equivalence relation can be turned into a groupoid by assigning precisely one isomorphism from to for any pair with , and no isomorphisms from to when , with the groupoid operations of identity, composition, and inverse defined in the only way possible consistent with the axioms. We will call this the simply connected groupoid associated with this equivalence relation. For instance, with as above, if we turn into a simply connected groupoid, there will be precisely one isomorphism from to , and also precisely one isomorphism from to , but no isomorphisms from to , , or .
However, one can also form multiply-connected groupoids in which there can be multiple isomorphisms from one element of to another. For instance, one can view as a space that is acted on by multiplication by the two-element group . This gives rise to two types of isomorphisms, an identity isomorphism from to for each , and a negation isomorphism from to for each ; in particular, there are two automorphisms of (i.e., isomorphisms from to itself), namely and , whereas the other four elements of only have a single automorphism (the identity isomorphism). One defines composition, identity, and inverse in this groupoid in the obvious fashion (using the group law of the two-element group ); for instance, we have .
For a finite multiply-connected groupoid, it turns out that the natural notion of “cardinality” (or as I prefer to call it, “cardinality up to isomorphism”) is given by the variant
of (1). That is to say, in the multiply connected case, the denominator is no longer the number of objects isomorphic to , but rather the number of isomorphisms from to other objects . Grouping together all summands coming from a single equivalence class in , we can also write this expression as
where is the automorphism group of , that is to say the group of isomorphisms from to itself. (Note that if belong to the same equivalence class , then the two groups and will be isomorphic and thus have the same cardinality, and so the above expression is well-defined.
For instance, if we take to be the simply connected groupoid on , then the number of elements of up to isomorphism is
exactly as before. If however we take the multiply connected groupoid on , in which has two automorphisms, the number of elements of up to isomorphism is now the smaller quantity
the equivalence class is now counted with weight rather than due to the two automorphisms on . Geometrically, one can think of this groupoid as being formed by taking the five-element set , and “folding it in half” around the fixed point , giving rise to two “full” quotient points and one “half” point . More generally, given a finite group acting on a finite set , and forming the associated multiply connected groupoid, the cardinality up to isomorphism of this groupoid will be , since each element of will have isomorphisms on it (whether they be to the same element , or to other elements of ).
The definition (2) can also make sense for some infinite groupoids; to my knowledge this was first explicitly done in this paper of Baez and Dolan. Consider for instance the category of finite sets, with isomorphisms given by bijections as in Example 3. Every finite set is isomorphic to for some natural number , so the equivalence classes of may be indexed by the natural numbers. The automorphism group of has order , so the cardinality of up to isomorphism is
(This fact is sometimes loosely stated as “the number of finite sets is “, but I view this statement as somewhat misleading if the qualifier “up to isomorphism” is not added.) Similarly, when one allows for multiple isomorphisms from a group to itself, the number of groups of order four up to isomorphism is now
because the cyclic group has two automorphisms, whereas the Klein four-group has six.
In the case that the cardinality of a groupoid up to isomorphism is finite and non-empty, one can now define the notion of a random isomorphism class in drawn “uniformly up to isomorphism”, by requiring the probability of attaining any given isomorphism class to be
thus the probability of being isomorphic to a given element will be inversely proportional to the number of automorphisms that has. For instance, if we take to be the set with the simply connected groupoid, will be drawn uniformly from the three available equivalence classes , with a probability of attaining each; but if instead one uses the multiply connected groupoid coming from the action of , and draws uniformly up to isomorphism, then and will now be selected with probability each, and will be selected with probability . Thus this distribution has accounted for the bias mentioned previously: if a finite group acts on a finite space , and is drawn uniformly from , then now still be drawn uniformly up to isomorphism from , if we use the multiply connected groupoid coming from the action, rather than the simply connected groupoid coming from just the -orbit structure on .
Using the groupoid of finite sets, we see that a finite set chosen uniformly up to isomorphism will have a cardinality that is distributed according to the Poisson distribution of parameter , that is to say it will be of cardinality with probability .
One important source of groupoids are the fundamental groupoids of a manifold (one can also consider more general topological spaces than manifolds, but for simplicity we will restrict this discussion to the manifold case), in which the underlying space is simply , and the isomorphisms from to are the equivalence classes of paths from to up to homotopy; in particular, the automorphism group of any given point is just the fundamental group of at that base point. The equivalence class of a point in is then the connected component of in . The cardinality up to isomorphism of the fundamental groupoid is then
where is the collection of connected components of , and is the order of the fundamental group of . Thus, simply connected components of count for a full unit of cardinality, whereas multiply connected components (which can be viewed as quotients of their simply connected cover by their fundamental group) will count for a fractional unit of cardinality, inversely to the order of their fundamental group.
This notion of cardinality up to isomorphism of a groupoid behaves well with respect to various basic notions. For instance, suppose one has an -fold covering map of one finite groupoid by another . This means that is a functor that is surjective, with all preimages of cardinality , with the property that given any pair in the base space and any in the preimage of , every isomorphism has a unique lift from the given initial point (and some in the preimage of ). Then one can check that the cardinality up to isomorphism of is times the cardinality up to isomorphism of , which fits well with the geometric picture of as the -fold cover of . (For instance, if one covers a manifold with finite fundamental group by its universal cover, this is a -fold cover, the base has cardinality up to isomorphism, and the universal cover has cardinality one up to isomorphism.) Related to this, if one draws an equivalence class of uniformly up to isomorphism, then will be an equivalence class of drawn uniformly up to isomorphism also.
Indeed, one can show that this notion of cardinality up to isomorphism for groupoids is uniquely determined by a small number of axioms such as these (similar to the axioms that determine Euler characteristic); see this blog post of Qiaochu Yuan for details.
The probability distributions on isomorphism classes described by the above recipe seem to arise naturally in many applications. For instance, if one draws a profinite abelian group up to isomorphism at random in this fashion (so that each isomorphism class of a profinite abelian group occurs with probability inversely proportional to the number of automorphisms of this group), then the resulting distribution is known as the Cohen-Lenstra distribution, and seems to emerge as the natural asymptotic distribution of many randomly generated profinite abelian groups in number theory and combinatorics, such as the class groups of random quadratic fields; see this previous blog post for more discussion. For a simple combinatorial example, the set of fixed points of a random permutation on elements will have a cardinality that converges in distribution to the Poisson distribution of rate (as discussed in this previous post), thus we see that the fixed points of a large random permutation asymptotically are distributed uniformly up to isomorphism. I’ve been told that this notion of cardinality up to isomorphism is also particularly compatible with stacks (which are a good framework to describe such objects as moduli spaces of algebraic varieties up to isomorphism), though I am not sufficiently acquainted with this theory to say much more than this.
I’ve just uploaded to the arXiv my paper “An integration approach to the Toeplitz square peg problem“, submitted to Forum of Mathematics, Sigma. This paper resulted from my attempts recently to solve the Toeplitz square peg problem (also known as the inscribed square problem):
See this recent survey of Matschke in the Notices of the AMS for the latest results on this problem.
The route I took to the results in this paper was somewhat convoluted. I was motivated to look at this problem after lecturing recently on the Jordan curve theorem in my class. The problem is superficially similar to the Jordan curve theorem in that the result is known (and rather easy to prove) if is sufficiently regular (e.g. if it is a polygonal path), but seems to be significantly more difficult when the curve is merely assumed to be continuous. Roughly speaking, all the known positive results on the problem have proceeded using (in some form or another) tools from homology: note for instance that one can view the conjecture as asking whether the four-dimensional subset of the eight-dimensional space necessarily intersects the four-dimensional space consisting of the quadruples traversing a square in (say) anti-clockwise order; this space is a four-dimensional linear subspace of , with a two-dimensional subspace of “degenerate” squares removed. If one ignores this degenerate subspace, one can use intersection theory to conclude (under reasonable “transversality” hypotheses) that intersects an odd number of times (up to the cyclic symmetries of the square), which is basically how Conjecture 1 is proven in the regular case. Unfortunately, if one then takes a limit and considers what happens when is just a continuous curve, the odd number of squares created by these homological arguments could conceivably all degenerate to points, thus blocking one from proving the conjecture in the general case.
Inspired by my previous work on finite time blowup for various PDEs, I first tried looking for a counterexample in the category of (locally) self-similar curves that are smooth (or piecewise linear) away from a single origin where it can oscillate infinitely often; this is basically the smoothest type of curve that was not already covered by previous results. By a rescaling and compactness argument, it is not difficult to see that such a counterexample would exist if there was a counterexample to the following periodic version of the conjecture:
Conjecture 2 (Periodic square peg problem) Let be two disjoint simple closed piecewise linear curves in the cylinder which have a winding number of one, that is to say they are homologous to the loop from to . Then the union of and contains the four vertices of a square.
In contrast to Conjecture 1, which is known for polygonal paths, Conjecture 2 is still open even under the hypothesis of polygonal paths; the homological arguments alluded to previously now show that the number of inscribed squares in the periodic setting is even rather than odd, which is not enough to conclude the conjecture. (This flipping of parity from odd to even due to an infinite amount of oscillation is reminiscent of the “Eilenberg-Mazur swindle“, discussed in this previous post.)
I therefore tried to construct counterexamples to Conjecture 2. I began perturbatively, looking at curves that were small perturbations of constant functions. After some initial Taylor expansion, I was blocked from forming such a counterexample because an inspection of the leading Taylor coefficients required one to construct a continuous periodic function of mean zero that never vanished, which of course was impossible by the intermediate value theorem. I kept expanding to higher and higher order to try to evade this obstruction (this, incidentally, was when I discovered this cute application of Lagrange reversion) but no matter how high an accuracy I went (I think I ended up expanding to sixth order in a perturbative parameter before figuring out what was going on!), this obstruction kept resurfacing again and again. I eventually figured out that this obstruction was being caused by a “conserved integral of motion” for both Conjecture 2 and Conjecture 1, which can in fact be used to largely rule out perturbative constructions. This yielded a new positive result for both conjectures:
We sketch the proof of Theorem 3(i) as follows (the proof of Theorem 3(ii) is very similar). Let be the curve , thus traverses one of the two graphs that comprise . For each time , there is a unique square with first vertex (and the other three vertices, traversed in anticlockwise order, denoted ) such that also lies in the graph of and also lies in the graph of (actually for technical reasons we have to extend by constants to all of in order for this claim to be true). To see this, we simply rotate the graph of clockwise by around , where (by the Lipschitz hypotheses) it must hit the graph of in a unique point, which is , and which then determines the other two vertices of the square. The curve has the same starting and ending point as the graph of or ; using the Lipschitz hypothesis one can show this graph is simple. If the curve ever hits the graph of other than at the endpoints, we have created an inscribed square, so we may assume for contradiction that avoids the graph of , and hence by the Jordan curve theorem the two curves enclose some non-empty bounded open region .
Now for the conserved integral of motion. If we integrate the -form on each of the four curves , we obtain the identity
This identity can be established by the following calculation: one can parameterise
for some Lipschitz functions ; thus for instance . Inserting these parameterisations and doing some canceling, one can write the above integral as
which vanishes because (which represent the sidelengths of the squares determined by vanish at the endpoints .
Using this conserved integral of motion, one can show that
which by Stokes’ theorem then implies that the bounded open region mentioned previously has zero area, which is absurd.
This argument hinged on the curve being simple, so that the Jordan curve theorem could apply. Once one left the perturbative regime of curves of small Lipschitz constant, it became possible for to be self-crossing, but nevertheless there still seemed to be some sort of integral obstruction. I eventually isolated the problem in the form of a strengthened version of Conjecture 2:
(note the -form is still well defined on the cylinder ; note also that the curves are allowed to cross each other.) Then there exists a (possibly degenerate) square with vertices (traversed in anticlockwise order) lying on respectively.
It is not difficult to see that Conjecture 4 implies Conjecture 2. Actually I believe that the converse implication is at least morally true, in that any counterexample to Conjecture 4 can be eventually transformed to a counterexample to Conjecture 2 and Conjecture 1. The conserved integral of motion argument can establish Conjecture 4 in many cases, for instance if are graphs of functions of Lipschitz constant less than one.
Conjecture 4 has a model special case, when one of the is assumed to just be a horizontal loop. In this case, the problem collapses to that of producing an intersection between two three-dimensional subsets of a six-dimensional space, rather than to four-dimensional subsets of an eight-dimensional space. More precisely, some elementary transformations reveal that this special case of Conjecture 4 can be formulated in the following fashion in which the geometric notion of a square is replaced by the additive notion of a triple of real numbers summing to zero:
Then there exist and with such that for .
This conjecture is easy to establish if one of the curves, say , is the graph of some piecewise linear function , since in that case the curve and the curve enclose the same area in the sense that , and hence must intersect by the Jordan curve theorem (otherwise they would enclose a non-zero amount of area between them), giving the claim. But when none of the are graphs, the situation becomes combinatorially more complicated.
Using some elementary homological arguments (e.g. breaking up closed -cycles into closed paths) and working with a generic horizontal slice of the curves, I was able to show that Conjecture 5 was equivalent to a one-dimensional problem that was largely combinatorial in nature, revolving around the sign patterns of various triple sums with drawn from various finite sets of reals.
- (i) For any , the sums are non-zero.
- (ii) (Non-crossing) For any and with the same parity, the pairs and are non-crossing in the sense that
- (iii) (Non-crossing sums) For any , , of the same parity, one has
Then one has
Roughly speaking, Conjecture 6 and Conjecture 5 are connected by constructing curves to connect to for by various paths, which either lie to the right of the axis (when is odd) or to the left of the axis (when is even). The axiom (ii) is asserting that the numbers are ordered according to the permutation of a meander (formed by gluing together two non-crossing perfect matchings).
Using various ad hoc arguments involving “winding numbers”, it is possible to prove this conjecture in many cases (e.g. if one of the is at most ), to the extent that I have now become confident that this conjecture is true (and have now come full circle from trying to disprove Conjecture 1 to now believing that this conjecture holds also). But it seems that there is some non-trivial combinatorial argument to be made if one is to prove this conjecture; purely homological arguments seem to partially resolve the problem, but are not sufficient by themselves.
While I was not able to resolve the square peg problem, I think these results do provide a roadmap to attacking it, first by focusing on the combinatorial conjecture in Conjecture 6 (or its equivalent form in Conjecture 5), then after that is resolved moving on to Conjecture 4, and then finally to Conjecture 1.
Having discussed differentiation of complex mappings in the preceding notes, we now turn to the integration of complex maps. We first briefly review the situation of integration of (suitably regular) real functions of one variable. Actually there are three closely related concepts of integration that arise in this setting:
- (i) The signed definite integral , which is usually interpreted as the Riemann integral (or equivalently, the Darboux integral), which can be defined as the limit (if it exists) of the Riemann sums
where is some partition of , is an element of the interval , and the limit is taken as the maximum mesh size goes to zero. It is convenient to adopt the convention that for ; alternatively one can interpret as the limit of the Riemann sums (1), where now the (reversed) partition goes leftwards from to , rather than rightwards from to .
- (ii) The unsigned definite integral , usually interpreted as the Lebesgue integral. The precise definition of this integral is a little complicated (see e.g. this previous post), but roughly speaking the idea is to approximate by simple functions for some coefficients and sets , and then approximate the integral by the quantities , where is the Lebesgue measure of . In contrast to the signed definite integral, no orientation is imposed or used on the underlying domain of integration, which is viewed as an “undirected” set .
- (iii) The indefinite integral or antiderivative , defined as any function whose derivative exists and is equal to on . Famously, the antiderivative is only defined up to the addition of an arbitrary constant , thus for instance .
There are some other variants of the above integrals (e.g. the Henstock-Kurzweil integral, discussed for instance in this previous post), which can handle slightly different classes of functions and have slightly different properties than the standard integrals listed here, but we will not need to discuss such alternative integrals in this course (with the exception of some improper and principal value integrals, which we will encounter in later notes).
The above three notions of integration are closely related to each other. For instance, if is a Riemann integrable function, then the signed definite integral and unsigned definite integral coincide (when the former is oriented correctly), thus
If is continuous, then by the fundamental theorem of calculus, it possesses an antiderivative , which is well defined up to an additive constant , and
for any , thus for instance and .
All three of the above integration concepts have analogues in complex analysis. By far the most important notion will be the complex analogue of the signed definite integral, namely the contour integral , in which the directed line segment from one real number to another is now replaced by a type of curve in the complex plane known as a contour. The contour integral can be viewed as the special case of the more general line integral , that is of particular relevance in complex analysis. There are also analogues of the Lebesgue integral, namely the arclength measure integrals and the area integrals , but these play only an auxiliary role in the subject. Finally, we still have the notion of an antiderivative (also known as a primitive) of a complex function .
As it turns out, the fundamental theorem of calculus continues to hold in the complex plane: under suitable regularity assumptions on a complex function and a primitive of that function, one has
whenever is a contour from to that lies in the domain of . In particular, functions that possess a primitive must be conservative in the sense that for any closed contour. This property of being conservative is not typical, in that “most” functions will not be conservative. However, there is a remarkable and far-reaching theorem, the Cauchy integral theorem (also known as the Cauchy-Goursat theorem), which asserts that any holomorphic function is conservative, so long as the domain is simply connected (or if one restricts attention to contractible closed contours). We will explore this theorem and several of its consequences the next set of notes.
Perhaps Thurston’s best known achievement is the proof of the hyperbolisation theorem for Haken manifolds, which showed that 3-manifolds which obeyed a certain number of topological conditions, could always be given a hyperbolic geometry (i.e. a Riemannian metric that made the manifold isometric to a quotient of the hyperbolic 3-space ). This difficult theorem connecting the topological and geometric structure of 3-manifolds led Thurston to give his influential geometrisation conjecture, which (in principle, at least) completely classifies the topology of an arbitrary compact 3-manifold as a combination of eight model geometries (now known as Thurston model geometries). This conjecture has many consequences, including Thurston’s hyperbolisation theorem and (most famously) the Poincaré conjecture. Indeed, by placing that conjecture in the context of a conceptually appealing general framework, of which many other cases could already be verified, Thurston provided one of the strongest pieces of evidence towards the truth of the Poincaré conjecture, until the work of Grisha Perelman in 2002-2003 proved both the Poincaré conjecture and the geometrisation conjecture by developing Hamilton’s Ricci flow methods. (There are now several variants of Perelman’s proof of both conjectures; in the proof of geometrisation by Bessieres, Besson, Boileau, Maillot, and Porti, Thurston’s hyperbolisation theorem is a crucial ingredient, allowing one to bypass the need for the theory of Alexandrov spaces in a key step in Perelman’s argument.)
One of my favourite results of Thurston’s is his elegant method for everting the sphere (smoothly turning a sphere in inside out without any folds or singularities). The fact that sphere eversion can be achieved at all is highly unintuitive, and is often referred to as Smale’s paradox, as Stephen Smale was the first to give a proof that such an eversion exists. However, prior to Thurston’s method, the known constructions for sphere eversion were quite complicated. Thurston’s method, relying on corrugating and then twisting the sphere, is sufficiently conceptual and geometric that it can in fact be explained quite effectively in non-technical terms, as was done in the following excellent video entitled “Outside In“, and produced by the Geometry Center:
In addition to his direct mathematical research contributions, Thurston was also an amazing mathematical expositor, having the rare knack of being able to describe the process of mathematical thinking in addition to the results of that process and the intuition underlying it. His wonderful essay “On proof and progress in mathematics“, which I highly recommend, is the quintessential instance of this; more recent examples include his many insightful questions and answers on MathOverflow.
I unfortunately never had the opportunity to meet Thurston in person (although we did correspond a few times online), but I know many mathematicians who have been profoundly influenced by him and his work. His death is a great loss for mathematics.
A topological space is said to be metrisable if one can find a metric on it whose open balls generate the topology.
There are some obvious necessary conditions on the space in order for it to be metrisable. For instance, it must be Hausdorff, since all metric spaces are Hausdorff. It must also be first countable, because every point in a metric space has a countable neighbourhood base of balls , .
In the converse direction, being Hausdorff and first countable is not always enough to guarantee metrisability, for a variety of reasons. For instance the long line is not metrisable despite being both Hausdorff and first countable, due to a failure of paracompactness, which prevents one from gluing together the local metric structures on this line into a global one. Even after adding in paracompactness, this is still not enough; the real line with the lower limit topology (also known as the Sorgenfrey line) is Hausdorff, first countable, and paracompact, but still not metrisable (because of a failure of second countability despite being separable).
However, there is one important setting in which the Hausdorff and first countability axioms do suffice to give metrisability, and that is the setting of topological groups:
Theorem 1 (Birkhoff-Kakutani theorem) Let be a topological group (i.e. a topological space that is also a group, such that the group operations and are continuous). Then is metrisable if and only if it is both Hausdorff and first countable.
Remark 1 It is not hard to show that a topological group is Hausdorff if and only if the singleton set is closed. More generally, in an arbitrary topological group, it is a good exercise to show that the closure of is always a closed normal subgroup of , whose quotient is then a Hausdorff topological group. Because of this, the study of topological groups can usually be reduced immediately to the study of Hausdorff topological groups. (Indeed, in many texts, topological groups are automatically understood to be an abbreviation for “Hausdorff topological group”.)
The standard proof of the Birkhoff-Kakutani theorem (which we have taken from this book of Montgomery and Zippin) relies on the following Urysohn-type lemma:
- (Unique maximum) , and for all .
- (Neighbourhood base) The sets for form a neighbourhood base at the identity.
- (Uniform continuity) For every , there exists an open neighbourhood of the identity such that for all and .
Note that if had a left-invariant metric, then the function would suffice for this lemma, which already gives some indication as to why this lemma is relevant to the Birkhoff-Kakutani theorem.
Let us assume Lemma 2 for now and finish the proof of the Birkhoff-Kakutani theorem. We only prove the difficult direction, namely that a Hausdorff first countable topological group is metrisable. We let be the function from Lemma 2, and define the function by the formula
where is the space of bounded continuous functions on (with the supremum norm) and is the left-translation operator .
Clearly obeys the the identity and symmetry axioms, and the triangle inequality is also immediate. This already makes a pseudometric. In order for to be a genuine metric, what is needed is that have no non-trivial translation invariances, i.e. one has for all . But this follows since attains its maximum at exactly one point, namely the group identity .
To put it another way: because has no non-trivial translation invariances, the left translation action gives an embedding , and then inherits a metric from the metric structure on .
Now we have to check whether the metric actually generates the topology. This amounts to verifying two things. Firstly, that every ball in this metric is open; and secondly, that every open neighbourhood of a point contains a ball .
To verify the former claim, it suffices to show that the map from to is continuous, follows from the uniform continuity hypothesis. The second claim follows easily from the neighbourhood base hypothesis, since if then .
Remark 2 The above argument in fact shows that if a group is metrisable, then it admits a left-invariant metric. The idea of using a suitable continuous function to generate a useful metric structure on a topological group is a powerful one, for instance underlying the Gleason lemmas which are fundamental to the solution of Hilbert’s fifth problem. I hope to return to this topic in a future post.
Now we prove Lemma 2. By first countability, we can find a countable neighbourhood base
of the identity. As is Hausdorff, we must have
For every dyadic rational in , we can now define the open sets by setting
for all and .
We now set
with the understanding that if the supremum is over the empty set. One easily verifies using (4) that is continuous, and furthermore obeys the uniform continuity property. The neighbourhood base property follows since the are a neighbourhood base of the identity, and the unique maximum property follows from (3). This proves Lemma 2.
Remark 3 A very similar argument to the one above also establishes that every topological group is completely regular.
Notice that the function constructed in the above argument was localised to the set . As such, it is not difficult to localise the Birkhoff-Kakutani theorem to local groups. A local group is a topological space equipped with an identity , a partially defined inversion operation , and a partially defined product operation , where , are open subsets of and , obeying the following restricted versions of the group axioms:
- (Continuity) and are continuous on their domains of definition.
- (Identity) For any , and are well-defined and equal to .
- (Inverse) For any , and are well-defined and equal to . is well-defined and equal to .
- (Local associativity) If are such that , , , and are all well-defined, then .
Informally, one can view a local group as a topological group in which the closure axiom has been almost completely dropped, but with all the other axioms retained. A basic way to generate a local group is to start with an ordinary topological group and restrict it to an open neighbourhood of the identity, with and . However, this is not quite the only way to generate local groups (ultimately because the local associativity axiom does not necessarily imply a (stronger) global associativity axiom in which one considers two different ways to multiply more than three group elements together).
Remark 4 Another important example of a local group is that of a group chunk, in which the sets and are somehow “generic”; for instance, could be an algebraic variety, Zariski-open, and the group operations birational on their domains of definition. This is somewhat analogous to the notion of a “ group” in additive combinatorics. There are a number of group chunk theorems, starting with a theorem of Weil in the algebraic setting, which roughly speaking assert that a generic portion of a group chunk can be identified with the generic portion of a genuine group.
We then have
Theorem 3 (Birkhoff-Kakutani theorem for local groups) Let be a local group which is Hausdorff and first countable. Then there exists an open neighbourhood of the identity which is metrisable.
Proof: (Sketch) It is not difficult to see that in a local group , one can find a symmetric neighbourhood of the identity such that the product of any (say) elements of (multiplied together in any order) are well-defined, which effectively allows us to treat elements of as if they belonged to a group for the purposes of simple algebraic manipulation, such as applying the cancellation laws for . Inside this , one can then repeat the previous arguments and eventually end up with a continuous function supported in obeying the conclusions of Lemma 2 (but in the uniform continuity conclusion, one has to restrict to, say, , to avoid issues of ill-definedness). The definition (1) then gives a metric on with the required properties, where we make the convention that vanishes for (say) and .
My motivation for studying local groups is that it turns out that there is a correspondence (first observed by Hrushovski) between the concept of an approximate group in additive combinatorics, and a locally compact local group in topological group theory; I hope to discuss this correspondence further in a subsequent post.
The ham sandwich theorem asserts that, given bounded open sets in , there exists a hyperplane that bisects each of these sets , in the sense that each of the two half-spaces on either side of the hyperplane captures exactly half of the volume of . The shortest proof of this result proceeds by invoking the Borsuk-Ulam theorem.
A useful generalisation of the ham sandwich theorem is the polynomial ham sandwich theorem, which asserts that given bounded open sets in , there exists a hypersurface of degree (thus is a polynomial of degree such that the two semi-algebraic sets and capture half the volume of each of the . (More precisely, the degree will be at most , where is the first positive integer for which exceeds .) This theorem can be deduced from the Borsuk-Ulam theorem in the same manner that the ordinary ham sandwich theorem is (and can also be deduced directly from the ordinary ham sandwich theorem via the Veronese embedding).
The polynomial ham sandwich theorem is a theorem about continuous bodies (bounded open sets), but a simple limiting argument leads one to the following discrete analogue: given finite sets in , there exists a hypersurface of degree , such that each of the two semi-algebraic sets and contain at most half of the points on (note that some of the points of can certainly lie on the boundary ). This can be iterated to give a useful cell decomposition:
Proposition 1 (Cell decomposition) Let be a finite set of points in , and let be a positive integer. Then there exists a polynomial of degree at most , and a decomposition
into the hypersurface and a collection of cells bounded by , such that , and such that each cell contains at most points.
A proof is sketched in this previous blog post. The cells in the argument are not necessarily connected (being instead formed by intersecting together a number of semi-algebraic sets such as and ), but it is a classical result (established independently by Oleinik-Petrovskii, Milnor, and Thom) that any degree hypersurface divides into connected components, so one can easily assume that the cells are connected if desired. (Incidentally, one does not need the full machinery of the results in the above cited papers – which control not just the number of components, but all the Betti numbers of the complement of – to get the bound on connected components; one can instead observe that every bounded connected component has a critical point where , and one can control the number of these points by Bezout’s theorem, after perturbing slightly to enforce genericity, and then count the unbounded components by an induction on dimension.)
Remark 1 By setting as large as , we obtain as a limiting case of the cell decomposition the fact that any finite set of points in can be captured by a hypersurface of degree . This fact is in fact true over arbitrary fields (not just over ), and can be proven by a simple linear algebra argument (see e.g. this previous blog post). However, the cell decomposition is more flexible than this algebraic fact due to the ability to arbitrarily select the degree parameter .
The cell decomposition can be viewed as a structural theorem for arbitrary large configurations of points in space, much as the Szemerédi regularity lemma can be viewed as a structural theorem for arbitrary large dense graphs. Indeed, just as many problems in the theory of large dense graphs can be profitably attacked by first applying the regularity lemma and then inspecting the outcome, it now seems that many problems in combinatorial incidence geometry can be attacked by applying the cell decomposition (or a similar such decomposition), with a parameter to be optimised later, to a relevant set of points, and seeing how the cells interact with each other and with the other objects in the configuration (lines, planes, circles, etc.). This strategy was spectacularly illustrated recently with Guth and Katz‘s use of the cell decomposition to resolve the Erdös distinct distance problem (up to logarithmic factors), as discussed in this blog post.
In this post, I wanted to record a simpler (but still illustrative) version of this method (that I learned from Nets Katz), namely to provide yet another proof of the Szemerédi-Trotter theorem in incidence geometry:
Theorem 2 (Szemerédi-Trotter theorem) Given a finite set of points and a finite set of lines in , the set of incidences has cardinality
This theorem has many short existing proofs, including one via crossing number inequalities (as discussed in this previous post) or via a slightly different type of cell decomposition (as discussed here). The proof given below is not that different, in particular, from the latter proof, but I believe it still serves as a good introduction to the polynomial method in combinatorial incidence geometry.
Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “Approximate subgroups of linear groups“, submitted to GAFA. This paper contains (the first part) of the results announced previously by us; the second part of these results, concerning expander groups, will appear subsequently. The release of this paper has been coordinated with the release of a parallel paper by Pyber and Szabo (previously announced within an hour(!) of our own announcement).
Our main result describes (with polynomial accuracy) the “sufficiently Zariski dense” approximate subgroups of simple algebraic groups , or more precisely absolutely almost simple algebraic groups over , such as . More precisely, define a -approximate subgroup of a genuine group to be a finite symmetric neighbourhood of the identity (thus and ) such that the product set can be covered by left-translates (and equivalently, right-translates) of .
Let be a field, and let be its algebraic closure. For us, an absolutely almost simple algebraic group over is a linear algebraic group defined over (i.e. an algebraic subvariety of for some with group operations given by regular maps) which is connected (i.e. irreducible), and such that the completion has no proper normal subgroups of positive dimension (i.e. the only normal subgroups are either finite, or are all of . To avoid degeneracies we also require to be non-abelian (i.e. not one-dimensional). These groups can be classified in terms of their associated finite-dimensional simple complex Lie algebra, which of course is determined by its Dynkin diagram, together with a choice of weight lattice (and there are only finitely many such choices once the Lie algebra is fixed). However, the exact classification of these groups is not directly used in our work.
Our first main theorem classifies the approximate subgroups of such a group in the model case when generates the entire group , and is finite; they are either very small or very large.
Theorem 1 (Approximate groups that generate) Let be an absolutely almost simple algebraic group over . If is finite and is a -approximate subgroup of that generates , then either or , where the implied constants depend only on .
The hypothesis that generates cannot be removed completely, since if was a proper subgroup of of size intermediate between that of the trivial group and of , then the conclusion would fail (with ). However, one can relax the hypothesis of generation to that of being sufficiently Zariski-dense in . More precisely, we have
Theorem 2 (Zariski-dense approximate groups) Let be an absolutely almost simple algebraic group over . If is a -approximate group) is not contained in any proper algebraic subgroup of of complexity at most (where is sufficiently large depending on ), then either or , where the implied constants depend only on and is the group generated by .
Here, we say that an algebraic variety has complexity at most if it can be cut out of an ambient affine or projective space of dimension at most by using at most polynomials, each of degree at most . (Note that this is not an intrinsic notion of complexity, but will depend on how one embeds the algebraic variety into an ambient space; but we are assuming that our algebraic group is a linear group and thus comes with such an embedding.)
In the case when , the second option of this theorem cannot occur since is infinite, leading to a satisfactory classification of the Zariski-dense approximate subgroups of almost simple connected algebraic groups over . On the other hand, every approximate subgroup of is Zariski-dense in some algebraic subgroup, which can be then split as an extension of a semisimple algebraic quotient group by a solvable algebraic group (the radical of the Zariski closure). Pursuing this idea (and glossing over some annoying technical issues relating to connectedness), together with the Freiman theory for solvable groups over due to Breuillard and Green, we obtain our third theorem:
Theorem 3 (Freiman’s theorem in ) Let be a -approximate subgroup of . Then there exists a nilpotent -approximate subgroup of size at most , such that is covered by translates of .
This can be compared with Gromov’s celebrated theorem that any finitely generated group of polynomial growth is virtually nilpotent. Indeed, the above theorem easily implies Gromov’s theorem in the case of finitely generated subgroups of .
By fairly standard arguments, the above classification theorems for approximate groups can be used to give bounds on the expansion and diameter of Cayley graphs, for instance one can establish a conjecture of Babai and Seress that connected Cayley graphs on absolutely almost simple groups over a finite field have polylogarithmic diameter at most. Applications to expanders include the result on Suzuki groups mentioned in a previous post; further applications will appear in a forthcoming paper.
Apart from the general structural theory of algebraic groups, and some quantitative 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 Konyagin and Bourgain-Glibichuk-Konyagin in the setting of sum-product estimates, and generalised to more non-commutative settings by Helfgott; this is discussed in this previous post. Secondly, we adapt an argument of Larsen and Pink (which we learned from a paper of Hrushovski) to obtain a sharp bound on the extent to which a sufficiently Zariski-dense approximate groups can concentrate in a (bounded complexity) subvariety; this is discussed at the end of this blog post.
This week I was in my home town of Adelaide, Australia, for the 2009 annual meeting of the Australian Mathematical Society. This was a fairly large meeting (almost 500 participants). One of the highlights of such a large meeting is the ability to listen to plenary lectures in fields adjacent to one’s own, in which speakers can give high-level overviews of a subject without getting too bogged down in the technical details. From the talks here I learned a number of basic things which were well known to experts in that field, but which I had not fully appreciated, and so I wanted to share them here.
The first instance of this was from a plenary lecture by Danny Calegari entitled “faces of the stable commutator length (scl) ball”. One thing I learned from this talk is that in homotopy theory, there is a very close relationship between topological spaces (such as manifolds) on one hand, and groups (and generalisations of groups) on the other, so that homotopy-theoretic questions about the former can often be converted to purely algebraic questions about the latter, and vice versa; indeed, it seems that homotopy theorists almost think of topological spaces and groups as being essentially the same concept, despite looking very different at first glance. To get from a space to a group, one looks at homotopy groups of that space, and in particular the fundamental group ; conversely, to get from a group back to a topological space one can use the Eilenberg-Maclane spaces associated to that group (and more generally, a Postnikov tower associated to a sequence of such groups, together with additional data). In Danny’s talk, he gave the following specific example: the problem of finding the least complicated embedded surface with prescribed (and homologically trivial) boundary in a space , where “least complicated” is measured by genus (or more precisely, the negative component of Euler characteristic), is essentially equivalent to computing the commutator length of the element in the fundamental group corresponding to that boundary (i.e. the least number of commutators one is required to multiply together to express the element); and the stable version of this problem (where one allows the surface to wrap around the boundary times for some large , and one computes the asymptotic ratio between the Euler characteristic and ) is similarly equivalent to computing the stable commutator length of that group element. (Incidentally, there is a simple combinatorial open problem regarding commutator length in the free group, which I have placed on the polymath wiki.)
This theme was reinforced by another plenary lecture by Ezra Getzler entitled “-groups”, in which he showed how sequences of groups (such as the first homotopy groups ) can be enhanced into a more powerful structure known as an -group, which is more complicated to define, requiring the machinery of simplicial complexes, sheaves, and nerves. Nevertheless, this gives a very topological and geometric interpretation of the concept of a group and its generalisations, which are of use in topological quantum field theory, among other things.
Mohammed Abuzaid gave a plenary lecture entitled “Functoriality in homological mirror symmetry”. One thing I learned from this talk was that the (partially conjectural) phenomenon of (homological) mirror symmetry is one of several types of duality, in which the behaviour of maps into one mathematical object (e.g. immersed or embedded curves, surfaces, etc.) are closely tied to the behaviour of maps out of a dual mathematical object (e.g. functionals, vector fields, forms, sections, bundles, etc.). A familiar example of this is in linear algebra: by taking adjoints, a linear map into a vector space can be related to an adjoint linear map mapping out of the dual space . Here, the behaviour of curves in a two-dimensional symplectic manifold (or more generally, Lagrangian submanifolds in a higher-dimensional symplectic manifold), is tied to the behaviour of holomorphic sections on bundles over a dual algebraic variety, where the precise definition of “behaviour” is category-theoretic, involving some rather complicated gadgets such as the Fukaya category of a symplectic manifold. As with many other applications of category theory, it is not just the individual pairings between an object and its dual which are of interest, but also the relationships between these pairings, as formalised by various functors between categories (and natural transformations between functors). (One approach to mirror symmetry was discussed by Shing-Tung Yau at a distinguished lecture at UCLA, as transcribed in this previous post.)
There was a related theme in a talk by Dennis Gaitsgory entitled “The geometric Langlands program”. From my (very superficial) understanding of the Langlands program, the behaviour of specific maps into a reductive Lie group , such as representations in of a fundamental group, étale fundamental group, class group, or Galois group of a global field, is conjecturally tied to specific maps out of a dual reductive Lie group , such as irreducible automorphic representations of , or of various structures (such as derived categories) attached to vector bundles on . There are apparently some tentatively conjectured links (due to Witten?) between Langlands duality and mirror symmetry, but they seem at present to be fairly distinct phenomena (one is topological and geometric, the other is more algebraic and arithmetic). For abelian groups, Langlands duality is closely connected to the much more classical Pontryagin duality in Fourier analysis. (There is an analogue of Fourier analysis for nonabelian groups, namely representation theory, but the link from this to the Langlands program is somewhat murky, at least to me.)
Related also to this was a plenary talk by Akshay Venkatesh, entitled “The Cohen-Lenstra heuristics over global fields”. Here, the question concerned the conjectural behaviour of class groups of quadratic fields, and in particular to explain the numerically observed phenomenon that about of all quadratic fields (with prime) enjoy unique factorisation (i.e. have trivial class group). (Class groups, as I learned in these two talks, are arithmetic analogues of the (abelianised) fundamental groups in topology, with Galois groups serving as the analogue of the full fundamental group.) One thing I learned here was that there was a canonical way to randomly generate a (profinite) abelian group, by taking the product of randomly generated finite abelian -groups for each prime . The way to canonically randomly generate a finite abelian -group is to take large integers , and look at the cokernel of a random homomorphism from to . In the limit (or by replacing with the -adics and just sending ), this stabilises and generates any given -group with probability
where ranges over all -groups; I do not know how to prove this identity other than via the above probability computation, the proof of which I give below the fold.
Based on the heuristic that the class group should behave “randomly” subject to some “obvious” constraints, it is expected that a randomly chosen real quadratic field has unique factorisation (i.e. the class group has trivial -group component for every ) with probability
whereas a randomly chosen imaginary quadratic field has unique factorisation with probability
The former claim is conjectural, whereas the latter claim follows from (for instance) Siegel’s theorem on the size of the class group, as discussed in this previous post. Ellenberg, Venkatesh, and Westerland have recently established some partial results towards the function field analogues of these heuristics.
One of the most important topological concepts in analysis is that of compactness (as discussed for instance in my Companion article on this topic). There are various flavours of this concept, but let us focus on sequential compactness: a subset E of a topological space X is sequentially compact if every sequence in E has a convergent subsequence whose limit is also in E. This property allows one to do many things with the set E. For instance, it allows one to maximise a functional on E:
Proposition 1. (Existence of extremisers) Let E be a non-empty sequentially compact subset of a topological space X, and let be a continuous function. Then the supremum is attained at at least one point , thus for all . (In particular, this supremum is finite.) Similarly for the infimum.
Proof. Let be the supremum . By the definition of supremum (and the axiom of (countable) choice), one can find a sequence in E such that . By compactness, we can refine this sequence to a subsequence (which, by abuse of notation, we shall continue to call ) such that converges to a limit x in E. Since we still have , and f is continuous at x, we conclude that f(x)=L, and the claim for the supremum follows. The claim for the infimum is similar.
Remark 1. An inspection of the argument shows that one can relax the continuity hypothesis on F somewhat: to attain the supremum, it suffices that F be upper semicontinuous, and to attain the infimum, it suffices that F be lower semicontinuous.
We thus see that sequential compactness is useful, among other things, for ensuring the existence of extremisers. In finite-dimensional spaces (such as vector spaces), compact sets are plentiful; indeed, the Heine-Borel theorem asserts that every closed and bounded set is compact. However, once one moves to infinite-dimensional spaces, such as function spaces, then the Heine-Borel theorem fails quite dramatically; most of the closed and bounded sets one encounters in a topological vector space are non-compact, if one insists on using a reasonably “strong” topology. This causes a difficulty in (among other things) calculus of variations, which is often concerned to finding extremisers to a functional on a subset E of an infinite-dimensional function space X.
In recent decades, mathematicians have found a number of ways to get around this difficulty. One of them is to weaken the topology to recover compactness, taking advantage of such results as the Banach-Alaoglu theorem (or its sequential counterpart). Of course, there is a tradeoff: weakening the topology makes compactness easier to attain, but makes the continuity of F harder to establish. Nevertheless, if F enjoys enough “smoothing” or “cancellation” properties, one can hope to obtain continuity in the weak topology, allowing one to do things such as locate extremisers. (The phenomenon that cancellation can lead to continuity in the weak topology is sometimes referred to as compensated compactness.)
Another option is to abandon trying to make all sequences have convergent subsequences, and settle just for extremising sequences to have convergent subsequences, as this would still be enough to retain Theorem 1. Pursuing this line of thought leads to the Palais-Smale condition, which is a substitute for compactness in some calculus of variations situations.
But in many situations, one cannot weaken the topology to the point where the domain E becomes compact, without destroying the continuity (or semi-continuity) of F, though one can often at least find an intermediate topology (or metric) in which F is continuous, but for which E is still not quite compact. Thus one can find sequences in E which do not have any subsequences that converge to a constant element , even in this intermediate metric. (As we shall see shortly, one major cause of this failure of compactness is the existence of a non-trivial action of a non-compact group G on E; such a group action can cause compensated compactness or the Palais-Smale condition to fail also.) Because of this, it is a priori conceivable that a continuous function F need not attain its supremum or infimum.
Nevertheless, even though a sequence does not have any subsequences that converge to a constant x, it may have a subsequence (which we also call ) which converges to some non-constant sequence (in the sense that the distance between the subsequence and the new sequence in a this intermediate metric), where the approximating sequence is of a very structured form (e.g. “concentrating” to a point, or “travelling” off to infinity, or a superposition of several concentrating or travelling profiles of this form). This weaker form of compactness, in which superpositions of a certain type of profile completely describe all the failures (or defects) of compactness, is known as concentration compactness, and the decomposition of the subsequence is known as the profile decomposition. In many applications, it is a sufficiently good substitute for compactness that one can still do things like locate extremisers for functionals F – though one often has to make some additional assumptions of F to compensate for the more complicated nature of the compactness. This phenomenon was systematically studied by P.L. Lions in the 80s, and found great application in calculus of variations and nonlinear elliptic PDE. More recently, concentration compactness has been a crucial and powerful tool in the non-perturbative analysis of nonlinear dispersive PDE, in particular being used to locate “minimal energy blowup solutions” or “minimal mass blowup solutions” for such a PDE (analogously to how one can use calculus of variations to find minimal energy solutions to a nonlinear elliptic equation); see for instance this recent survey by Killip and Visan.
In typical applications, the concentration compactness phenomenon is exploited in moderately sophisticated function spaces (such as Sobolev spaces or Strichartz spaces), with the failure of traditional compactness being connected to a moderately complicated group G of symmetries (e.g. the group generated by translations and dilations). Because of this, concentration compactness can appear to be a rather complicated and technical concept when it is first encountered. In this note, I would like to illustrate concentration compactness in a simple toy setting, namely in the space of absolutely summable sequences, with the uniform () metric playing the role of the intermediate metric, and the translation group playing the role of the symmetry group G. This toy setting is significantly simpler than any model that one would actually use in practice [for instance, in most applications X is a Hilbert space], but hopefully it serves to illuminate this useful concept in a less technical fashion.
This week I was in Columbus, Ohio, attending a conference on equidistribution on manifolds. I talked about my recent paper with Ben Green on the quantitative behaviour of polynomial sequences in nilmanifolds, which I have blogged about previously. During my talk (and inspired by the immediately preceding talk of Vitaly Bergelson), I stated explicitly for the first time a generalisation of the van der Corput trick which morally underlies our paper, though it is somewhat buried there as we specialised it to our application at hand (and also had to deal with various quantitative issues that made the presentation more complicated). After the talk, several people asked me for a more precise statement of this trick, so I am presenting it here, and as an application reproving an old theorem of Leon Green that gives a necessary and sufficient condition as to whether a linear sequence on a nilmanifold is equidistributed, which generalises the famous theorem of Weyl on equidistribution of polynomials.
UPDATE, Feb 2013: It has been pointed out to me by Pavel Zorin that this argument does not fully recover the theorem of Leon Green; to cover all cases, one needs the more complicated van der Corput argument in our paper.