You are currently browsing the category archive for the ‘math.GR’ category.

Let , be additive groups (i.e., groups with an abelian addition group law). A map is a homomorphism if one has

for all . A map is an *affine* homomorphism if one has

for all *additive quadruples* in , by which we mean that and . The two notions are closely related; it is easy to verify that is an affine homomorphism if and only if is the sum of a homomorphism and a constant.

Now suppose that also has a translation-invariant metric . A map is said to be a quasimorphism if one has

for all , where denotes a quantity at a bounded distance from the origin. Similarly, is an *affine quasimorphism* if

for all additive quadruples in . Again, one can check that is an affine quasimorphism if and only if it is the sum of a quasimorphism and a constant (with the implied constant of the quasimorphism controlled by the implied constant of the affine quasimorphism). (Since every constant is itself a quasimorphism, it is in fact the case that affine quasimorphisms are quasimorphisms, but now the implied constant in the latter is not controlled by the implied constant of the former.)

“Trivial” examples of quasimorphisms include the sum of a homomorphism and a bounded function. Are there others? In some cases, the answer is no. For instance, suppose we have a quasimorphism . Iterating (2), we see that for any integer and natural number , which we can rewrite as for non-zero . Also, is Lipschitz. Sending , we can verify that is a Cauchy sequence as and thus tends to some limit ; we have for , hence for positive , and then one can use (2) one last time to obtain for all . Thus is the sum of the homomorphism and a bounded sequence.

In general, one can phrase this problem in the language of group cohomology (discussed in this previous post). Call a map a *-cocycle*. A *-cocycle* is a map obeying the identity

for all . Given a -cocycle , one can form its *derivative* by the formula

Such functions are called *-coboundaries*. It is easy to see that the abelian group of -coboundaries is a subgroup of the abelian group of -cocycles. The quotient of these two groups is the first group cohomology of with coefficients in , and is denoted .

If a -cocycle is bounded then its derivative is a bounded -coboundary. The quotient of the group of bounded -cocycles by the derivatives of bounded -cocycles is called the *bounded first group cohomology* of with coefficients in , and is denoted . There is an obvious homomorphism from to , formed by taking a coset of the space of derivatives of bounded -cocycles, and enlarging it to a coset of the space of -coboundaries. By chasing all the definitions, we see that all quasimorphism from to are the sum of a homomorphism and a bounded function if and only if this homomorphism is injective; in fact the quotient of the space of quasimorphisms by the sum of homomorphisms and bounded functions is isomorphic to the kernel of .

In additive combinatorics, one is often working with functions which only have additive structure a fraction of the time, thus for instance (1) or (3) might only hold “ of the time”. This makes it somewhat difficult to directly interpret the situation in terms of group cohomology. However, thanks to tools such as the Balog-Szemerédi-Gowers lemma, one can upgrade this sort of -structure to -structure – at the cost of restricting the domain to a smaller set. Here I record one such instance of this phenomenon, thus giving a tentative link between additive combinatorics and group cohomology. (I thank Yuval Wigderson for suggesting the problem of locating such a link.)

Theorem 1Let , be additive groups with , let be a subset of , let , and let be a function such thatfor additive quadruples in . Then there exists a subset of containing with , a subset of with , and a function such that

for all (thus, the derivative takes values in on ), and such that for each , one has

Presumably the constants and can be improved further, but we have not attempted to optimise these constants. We chose as the domain on which one has a bounded derivative, as one can use the Bogulybov lemma (see e.g, Proposition 4.39 of my book with Van Vu) to find a large Bohr set inside . In applications, the set need not have bounded size, or even bounded doubling; for instance, in the inverse theory over a small finite fields , one would be interested in the situation where is the group of matrices with coefficients in (for some large , and being the subset consisting of those matrices of rank bounded by some bound .

*Proof:* By hypothesis, there are triples such that and

Thus, there is a set with such that for all , one has (6) for pairs with ; in particular, there exists such that (6) holds for values of . Setting , we conclude that for each , one has

Consider the bipartite graph whose vertex sets are two copies of , and and connected by a (directed) edge if and (7) holds. Then this graph has edges. Applying (a slight modification of) the Balog-Szemerédi-Gowers theorem (for instance by modifying the proof of Corollary 5.19 of my book with Van Vu), we can then find a subset of with with the property that for any , there exist triples such that the edges all lie in this bipartite graph. This implies that, for all , there exist septuples obeying the constraints

and for . These constraints imply in particular that

Also observe that

Thus, if and are such that , we see that

for octuples in the hyperplane

By the pigeonhole principle, this implies that for any fixed , there can be at most sets of the form with , that are pairwise disjoint. Using a greedy algorithm, we conclude that there is a set of cardinality , such that each set with , intersects for some , or in other words that

This implies that there exists a subset of with , and an element for each , such that

for all . Note we may assume without loss of generality that and .

By construction of , and permuting labels, we can find 16-tuples such that

and

for . We sum this to obtain

and hence by (8)

where . Since

we see that there are only possible values of . By the pigeonhole principle, we conclude that at most of the sets can be disjoint. Arguing as before, we conclude that there exists a set of cardinality such that

whenever (10) holds.

For any , write arbitrarily as for some (with if , and if ) and then set

Then from (11) we have (4). For we have , and (5) then follows from (9).

This is a sequel to this previous blog post, in which we discussed the effect of the heat flow evolution

on the zeroes of a time-dependent family of polynomials , with a particular focus on the case when the polynomials had real zeroes. Here (inspired by some discussions I had during a recent conference on the Riemann hypothesis in Bristol) we record the analogous theory in which the polynomials instead have zeroes on a circle , with the heat flow slightly adjusted to compensate for this. As we shall discuss shortly, a key example of this situation arises when is the numerator of the zeta function of a curve.

More precisely, let be a natural number. We will say that a polynomial

of degree (so that ) obeys the *functional equation* if the are all real and

for all , thus

and

for all non-zero . This means that the zeroes of (counting multiplicity) lie in and are symmetric with respect to complex conjugation and inversion across the circle . We say that this polynomial *obeys the Riemann hypothesis* if all of its zeroes actually lie on the circle . For instance, in the case, the polynomial obeys the Riemann hypothesis if and only if .

Such polynomials arise in number theory as follows: if is a projective curve of genus over a finite field , then, as famously proven by Weil, the associated local zeta function (as defined for instance in this previous blog post) is known to take the form

where is a degree polynomial obeying both the functional equation and the Riemann hypothesis. In the case that is an elliptic curve, then and takes the form , where is the number of -points of minus . The Riemann hypothesis in this case is a famous result of Hasse.

Another key example of such polynomials arise from rescaled characteristic polynomials

of matrices in the compact symplectic group . These polynomials obey both the functional equation and the Riemann hypothesis. The Sato-Tate conjecture (in higher genus) asserts, roughly speaking, that “typical” polyomials arising from the number theoretic situation above are distributed like the rescaled characteristic polynomials (1), where is drawn uniformly from with Haar measure.

Given a polynomial of degree with coefficients

we can evolve it in time by the formula

thus for . Informally, as one increases , this evolution accentuates the effect of the extreme monomials, particularly, and at the expense of the intermediate monomials such as , and conversely as one decreases . This family of polynomials obeys the heat-type equation

In view of the results of Marcus, Spielman, and Srivastava, it is also very likely that one can interpret this flow in terms of expected characteristic polynomials involving conjugation over the compact symplectic group , and should also be tied to some sort of “” version of Brownian motion on this group, but we have not attempted to work this connection out in detail.

It is clear that if obeys the functional equation, then so does for any other time . Now we investigate the evolution of the zeroes. Suppose at some time that the zeroes of are distinct, then

From the inverse function theorem we see that for times sufficiently close to , the zeroes of continue to be distinct (and vary smoothly in ), with

Differentiating this at any not equal to any of the , we obtain

and

and

Inserting these formulae into (2) (expanding as ) and canceling some terms, we conclude that

for sufficiently close to , and not equal to . Extracting the residue at , we conclude that

which we can rearrange as

If we make the change of variables (noting that one can make depend smoothly on for sufficiently close to ), this becomes

Intuitively, this equation asserts that the phases repel each other if they are real (and attract each other if their difference is imaginary). If obeys the Riemann hypothesis, then the are all real at time , then the Picard uniqueness theorem (applied to and its complex conjugate) then shows that the are also real for sufficiently close to . If we then define the entropy functional

then the above equation becomes a gradient flow

which implies in particular that is non-increasing in time. This shows that as one evolves time forward from , there is a uniform lower bound on the separation between the phases , and hence the equation can be solved indefinitely; in particular, obeys the Riemann hypothesis for all if it does so at time . Our argument here assumed that the zeroes of were simple, but this assumption can be removed by the usual limiting argument.

For any polynomial obeying the functional equation, the rescaled polynomials converge locally uniformly to as . By Rouche’s theorem, we conclude that the zeroes of converge to the equally spaced points on the circle . Together with the symmetry properties of the zeroes, this implies in particular that obeys the Riemann hypothesis for all sufficiently large positive . In the opposite direction, when , the polynomials converge locally uniformly to , so if , of the zeroes converge to the origin and the other converge to infinity. In particular, fails the Riemann hypothesis for sufficiently large negative . Thus (if ), there must exist a real number , which we call the *de Bruijn-Newman constant* of the original polynomial , such that obeys the Riemann hypothesis for and fails the Riemann hypothesis for . The situation is a bit more complicated if vanishes; if is the first natural number such that (or equivalently, ) does not vanish, then by the above arguments one finds in the limit that of the zeroes go to the origin, go to infinity, and the remaining zeroes converge to the equally spaced points . In this case the de Bruijn-Newman constant remains finite except in the degenerate case , in which case .

For instance, consider the case when and for some real with . Then the quadratic polynomial

has zeroes

and one easily checks that these zeroes lie on the circle when , and are on the real axis otherwise. Thus in this case we have (with if ). Note how as increases to , the zeroes repel each other and eventually converge to , while as decreases to , the zeroes collide and then separate on the real axis, with one zero going to the origin and the other to infinity.

The arguments in my paper with Brad Rodgers (discussed in this previous post) indicate that for a “typical” polynomial of degree that obeys the Riemann hypothesis, the expected time to relaxation to equilibrium (in which the zeroes are equally spaced) should be comparable to , basically because the average spacing is and hence by (3) the typical velocity of the zeroes should be comparable to , and the diameter of the unit circle is comparable to , thus requiring time comparable to to reach equilibrium. Taking contrapositives, this suggests that the de Bruijn-Newman constant should typically take on values comparable to (since typically one would not expect the initial configuration of zeroes to be close to evenly spaced). I have not attempted to formalise or prove this claim, but presumably one could do some numerics (perhaps using some of the examples of given previously) to explore this further.

The Polymath14 online collaboration has uploaded to the arXiv its paper “Homogeneous length functions on groups“, submitted to Algebra & Number Theory. The paper completely classifies *homogeneous length functions* on an arbitrary group , that is to say non-negative functions that obey the symmetry condition , the non-degeneracy condition , the triangle inequality , and the homogeneity condition . It turns out that these norms can only arise from pulling back the norm of a Banach space by an isometric embedding of the group. Among other things, this shows that can only support a homogeneous length function if and only if it is abelian and torsion free, thus giving a metric description of this property.

The proof is based on repeated use of the homogeneous length function axioms, combined with elementary identities of commutators, to obtain increasingly good bounds on quantities such as , until one can show that such norms have to vanish. See the previous post for a full proof. The result is robust in that it allows for some loss in the triangle inequality and homogeneity condition, allowing for some new results on “quasinorms” on groups that relate to quasihomomorphisms.

As there are now a large number of comments on the previous post on this project, this post will also serve as the new thread for any final discussion of this project as it winds down.

In the tradition of “Polymath projects“, the problem posed in the previous two blog posts has now been solved, thanks to the cumulative effect of many small contributions by many participants (including, but not limited to, Sean Eberhard, Tobias Fritz, Siddharta Gadgil, Tobias Hartnick, Chris Jerdonek, Apoorva Khare, Antonio Machiavelo, Pace Nielsen, Andy Putman, Will Sawin, Alexander Shamov, Lior Silberman, and David Speyer). In this post I’ll write down a streamlined resolution, eliding a number of important but ultimately removable partial steps and insights made by the above contributors en route to the solution.

Theorem 1Let be a group. Suppose one has a “seminorm” function which obeys the triangle inequalityfor all , with equality whenever . Then the seminorm factors through the abelianisation map .

*Proof:* By the triangle inequality, it suffices to show that for all , where is the commutator.

We first establish some basic facts. Firstly, by hypothesis we have , and hence whenever is a power of two. On the other hand, by the triangle inequality we have for all positive , and hence by the triangle inequality again we also have the matching lower bound, thus

for all . The claim is also true for (apply the preceding bound with and ). By replacing with if necessary we may now also assume without loss of generality that , thus

Next, for any , and any natural number , we have

so on taking limits as we have . Replacing by gives the matching lower bound, thus we have the conjugation invariance

Next, we observe that if are such that is conjugate to both and , then one has the inequality

Indeed, if we write for some , then for any natural number one has

where the and terms each appear times. From (2) we see that conjugation by does not affect the norm. Using this and the triangle inequality several times, we conclude that

and the claim (3) follows by sending .

The following special case of (3) will be of particular interest. Let , and for any integers , define the quantity

Observe that is conjugate to both and to , hence by (3) one has

which by (2) leads to the recursive inequality

We can write this in probabilistic notation as

where is a random vector that takes the values and with probability each. Iterating this, we conclude in particular that for any large natural number , one has

where and are iid copies of . We can write where are iid signs. By the triangle inequality, we thus have

noting that is an even integer. On the other hand, has mean zero and variance , hence by Cauchy-Schwarz

But by (1), the left-hand side is equal to . Dividing by and then sending , we obtain the claim.

The above theorem reduces such seminorms to abelian groups. It is easy to see from (1) that any torsion element of such groups has zero seminorm, so we can in fact restrict to torsion-free groups, which we now write using additive notation , thus for instance for . We think of as a -module. One can then extend the seminorm to the associated -vector space by the formula , and then to the associated -vector space by continuity, at which point it becomes a genuine seminorm (provided we have ensured the symmetry condition ). Conversely, any seminorm on induces a seminorm on . (These arguments also appear in this paper of Khare and Rajaratnam.)

This post is a continuation of the previous post, which has attracted a large number of comments. I’m recording here some calculations that arose from those comments (particularly those of Pace Nielsen, Lior Silberman, Tobias Fritz, and Apoorva Khare). Please feel free to either continue these calculations or to discuss other approaches to the problem, such as those mentioned in the remaining comments to the previous post.

Let be the free group on two generators , and let be a quantity obeying the triangle inequality

and the linear growth property

for all and integers ; this implies the conjugation invariance

or equivalently

We consider inequalities of the form

for various real numbers . For instance, since

we have (1) for . We also have the following further relations:

Proposition 1

*Proof:* For (i) we simply observe that

For (ii), we calculate

giving the claim.

For (iii), we calculate

giving the claim.

For (iv), we calculate

giving the claim.

Here is a typical application of the above estimates. If (1) holds for , then by part (i) it holds for , then by (ii) (2) holds for , then by (iv) (1) holds for . The map has fixed point , thus

For instance, if , then .

Here is a curious question posed to me by Apoorva Khare that I do not know the answer to. Let be the free group on two generators . Does there exist a metric on this group which is

- bi-invariant, thus for all ; and
- linear growth in the sense that for all and all natural numbers ?

By defining the “norm” of an element to be , an equivalent formulation of the problem asks if there exists a non-negative norm function that obeys the conjugation invariance

for all , the triangle inequality

for all , and the linear growth

for all and , and such that for all non-identity . Indeed, if such a norm exists then one can just take to give the desired metric.

One can normalise the norm of the generators to be at most , thus

This can then be used to upper bound the norm of other words in . For instance, from (1), (3) one has

A bit less trivially, from (3), (2), (1) one can bound commutators as

In a similar spirit one has

What is not clear to me is if one can keep arguing like this to continually improve the upper bounds on the norm of a given non-trivial group element to the point where this norm must in fact vanish, which would demonstrate that no metric with the above properties on would exist (and in fact would impose strong constraints on similar metrics existing on other groups as well). It is also tempting to use some ideas from geometric group theory (e.g. asymptotic cones) to try to understand these metrics further, though I wasn’t able to get very far with this approach. Anyway, this feels like a problem that might be somewhat receptive to a more crowdsourced attack, so I am posing it here in case any readers wish to try to make progress on it.

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 1Let 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 justThus, 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 2A 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 3Any 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.

Suppose that are two subgroups of some ambient group , with the index of in being finite. Then is the union of left cosets of , thus for some set of cardinality . The elements of are not entirely arbitrary with regards to . For instance, if is a *normal* subgroup of , then for each , the conjugation map preserves . In particular, if we write for the conjugate of by , then

Even if is not normal in , it turns out that the conjugation map *approximately* preserves , if is bounded. To quantify this, let us call two subgroups *-commensurate* for some if one has

Proposition 1Let be groups, with finite index . Then for every , the groups and are -commensurate, in fact

*Proof:* One can partition into left translates of , as well as left translates of . Combining the partitions, we see that can be partitioned into at most non-empty sets of the form . Each of these sets is easily seen to be a left translate of the subgroup , thus . Since

and , we obtain the claim.

One can replace the inclusion by commensurability, at the cost of some worsening of the constants:

Corollary 2Let be -commensurate subgroups of . Then for every , the groups and are -commensurate.

*Proof:* Applying the previous proposition with replaced by , we see that for every , and are -commensurate. Since and have index at most in and respectively, the claim follows.

It turns out that a similar phenomenon holds for the more general concept of an *approximate group*, and gives a “classification” of all the approximate groups containing a given approximate group as a “bounded index approximate subgroup”. Recall that a -approximate group in a group for some is a symmetric subset of containing the identity, such that the product set can be covered by at most left translates of (and thus also right translates, by the symmetry of ). For simplicity we will restrict attention to finite approximate groups so that we can use their cardinality as a measure of size. We call finite two approximate groups *-commensurate* if one has

note that this is consistent with the previous notion of commensurability for genuine groups.

Theorem 3Let be a group, and let be real numbers. Let be a finite -approximate group, and let be a symmetric subset of that contains .

- (i) If is a -approximate group with , then one has for some set of cardinality at most . Furthermore, for each , the approximate groups and are -commensurate.
- (ii) Conversely, if for some set of cardinality at most , and and are -commensurate for all , then , and is a -approximate group.

Informally, the assertion that is an approximate group containing as a “bounded index approximate subgroup” is equivalent to being covered by a bounded number of shifts of , where approximately normalises in the sense that and have large intersection. Thus, to classify all such , the problem essentially reduces to that of classifying those that approximately normalise .

To prove the theorem, we recall some standard lemmas from arithmetic combinatorics, which are the foundation stones of the “Ruzsa calculus” that we will use to establish our results:

Lemma 4 (Ruzsa covering lemma)If and are finite non-empty subsets of , then one has for some set with cardinality .

*Proof:* We take to be a subset of with the property that the translates are disjoint in , and such that is maximal with respect to set inclusion. The required properties of are then easily verified.

Lemma 5 (Ruzsa triangle inequality)If are finite non-empty subsets of , then

*Proof:* If is an element of with and , then from the identity we see that can be written as the product of an element of and an element of in at least distinct ways. The claim follows.

Now we can prove (i). By the Ruzsa covering lemma, can be covered by at most

left-translates of , and hence by at most left-translates of , thus for some . Since only intersects if , we may assume that

and hence for any

By the Ruzsa covering lemma again, this implies that can be covered by at most left-translates of , and hence by at most left-translates of . By the pigeonhole principle, there thus exists a group element with

Since

and

the claim follows.

Now we prove (ii). Clearly

Now we control the size of . We have

From the Ruzsa triangle inequality and symmetry we have

and thus

By the Ruzsa covering lemma, this implies that is covered by at most left-translates of , hence by at most left-translates of . Since , the claim follows.

We now establish some auxiliary propositions about commensurability of approximate groups. The first claim is that commensurability is approximately transitive:

Proposition 6Let be a -approximate group, be a -approximate group, and be a -approximate group. If and are -commensurate, and and are -commensurate, then and are -commensurate.

*Proof:* From two applications of the Ruzsa triangle inequality we have

By the Ruzsa covering lemma, we may thus cover by at most left-translates of , and hence by left-translates of . By the pigeonhole principle, there thus exists a group element such that

and so by arguing as in the proof of part (i) of the theorem we have

and similarly

and the claim follows.

The next proposition asserts that the union and (modified) intersection of two commensurate approximate groups is again an approximate group:

Proposition 7Let be a -approximate group, be a -approximate group, and suppose that and are -commensurate. Then is a -approximate subgroup, and is a -approximate subgroup.

Using this proposition, one may obtain a variant of the previous theorem where the containment is replaced by commensurability; we leave the details to the interested reader.

*Proof:* We begin with . Clearly is symmetric and contains the identity. We have . The set is already covered by left translates of , and hence of ; similarly is covered by left translates of . As for , we observe from the Ruzsa triangle inequality that

and hence by the Ruzsa covering lemma, is covered by at most left translates of , and hence by left translates of , and hence of . Similarly is covered by at most left translates of . The claim follows.

Now we consider . Again, this is clearly symmetric and contains the identity. Repeating the previous arguments, we see that is covered by at most left-translates of , and hence there exists a group element with

Now observe that

and so by the Ruzsa covering lemma, can be covered by at most left-translates of . But this latter set is (as observed previously) contained in , and the claim follows.

Because of Euler’s identity , the complex exponential is not injective: for any complex and integer . As such, the complex logarithm is not well-defined as a single-valued function from to . However, after making a branch cut, one can create a branch of the logarithm which is single-valued. For instance, after removing the negative real axis , one has the *standard branch* of the logarithm, with defined as the unique choice of the complex logarithm of whose imaginary part has magnitude strictly less than . This particular branch has a number of useful additional properties:

- The standard branch is holomorphic on its domain .
- One has for all in the domain . In particular, if is real, then is real.
- One has for all in the domain .

One can then also use the standard branch of the logarithm to create standard branches of other multi-valued functions, for instance creating a standard branch of the square root function. We caution however that the identity can fail for the standard branch (or indeed for any branch of the logarithm).

One can extend this standard branch of the logarithm to complex matrices, or (equivalently) to linear transformations on an -dimensional complex vector space , provided that the spectrum of that matrix or transformation avoids the branch cut . Indeed, from the spectral theorem one can decompose any such as the direct sum of operators on the non-trivial generalised eigenspaces of , where ranges in the spectrum of . For each component of , we define

where is the Taylor expansion of at ; as is nilpotent, only finitely many terms in this Taylor expansion are required. The logarithm is then defined as the direct sum of the .

The matrix standard branch of the logarithm has many pleasant and easily verified properties (often inherited from their scalar counterparts), whenever has no spectrum in :

- (i) We have .
- (ii) If and have no spectrum in , then .
- (iii) If has spectrum in a closed disk in , then , where is the Taylor series of around (which is absolutely convergent in ).
- (iv) depends holomorphically on . (Easily established from (ii), (iii), after covering the spectrum of by disjoint disks; alternatively, one can use the Cauchy integral representation for a contour in the domain enclosing the spectrum of .) In particular, the standard branch of the matrix logarithm is smooth.
- (v) If is any invertible linear or antilinear map, then . In particular, the standard branch of the logarithm commutes with matrix conjugations; and if is real with respect to a complex conjugation operation on (that is to say, an antilinear involution), then is real also.
- (vi) If denotes the transpose of (with the complex dual of ), then . Similarly, if denotes the adjoint of (with the complex conjugate of , i.e. with the conjugated multiplication map ), then .
- (vii) One has .
- (viii) If denotes the spectrum of , then .

As a quick application of the standard branch of the matrix logarithm, we have

Proposition 1Let be one of the following matrix groups: , , , , , or , where is a non-degenerate real quadratic form (so is isomorphic to a (possibly indefinite) orthogonal group for some . Then any element of whose spectrum avoids is exponential, that is to say for some in the Lie algebra of .

*Proof:* We just prove this for , as the other cases are similar (or a bit simpler). If , then (viewing as a complex-linear map on , and using the complex bilinear form associated to to identify with its complex dual , then is real and . By the properties (v), (vi), (vii) of the standard branch of the matrix logarithm, we conclude that is real and , and so lies in the Lie algebra , and the claim now follows from (i).

Exercise 2Show that is not exponential in if . Thus we see that the branch cut in the above proposition is largely necessary. See this paper of Djokovic for a more complete description of the image of the exponential map in classical groups, as well as this previous blog post for some more discussion of the surjectivity (or lack thereof) of the exponential map in Lie groups.

For a slightly less quick application of the standard branch, we have the following result (recently worked out in the answers to this MathOverflow question):

Proposition 3Let be an element of the split orthogonal group which lies in the connected component of the identity. Then .

The requirement that lie in the identity component is necessary, as the counterexample for shows.

*Proof:* We think of as a (real) linear transformation on , and write for the quadratic form associated to , so that . We can split , where is the sum of all the generalised eigenspaces corresponding to eigenvalues in , and is the sum of all the remaining eigenspaces. Since and are real, are real (i.e. complex-conjugation invariant) also. For , the restriction of to then lies in , where is the restriction of to , and

The spectrum of consists of positive reals, as well as complex pairs (with equal multiplicity), so . From the preceding proposition we have for some ; this will be important later.

It remains to show that . If has spectrum at then we are done, so we may assume that has spectrum only at (being invertible, has no spectrum at ). We split , where correspond to the portions of the spectrum in , ; these are real, -invariant spaces. We observe that if are generalised eigenspaces of with , then are orthogonal with respect to the (complex-bilinear) inner product associated with ; this is easiest to see first for the actual eigenspaces (since for all ), and the extension to generalised eigenvectors then follows from a routine induction. From this we see that is orthogonal to , and and are null spaces, which by the non-degeneracy of (and hence of the restriction of to ) forces to have the same dimension as , indeed now gives an identification of with . If we let be the restrictions of to , we thus identify with , since lies in ; in particular is invertible. Thus

and so it suffices to show that .

At this point we need to use the hypothesis that lies in the identity component of . This implies (by a continuity argument) that the restriction of to any maximal-dimensional positive subspace has positive determinant (since such a restriction cannot be singular, as this would mean that positive norm vector would map to a non-positive norm vector). Now, as have equal dimension, has a balanced signature, so does also. Since , already lies in the identity component of , and so has positive determinant on any maximal-dimensional positive subspace of . We conclude that has positive determinant on any maximal-dimensional positive subspace of .

We choose a complex basis of , to identify with , which has already been identified with . (In coordinates, are now both of the form , and for .) Then becomes a maximal positive subspace of , and the restriction of to this subspace is conjugate to , so that

But since and is positive definite, so as required.

In graph theory, the recently developed theory of *graph limits* has proven to be a useful tool for analysing large dense graphs, being a convenient reformulation of the Szemerédi regularity lemma. Roughly speaking, the theory asserts that given any sequence of finite graphs, one can extract a subsequence which converges (in a specific sense) to a continuous object known as a “graphon” – a symmetric measurable function . What “converges” means in this context is that subgraph densities converge to the associated integrals of the graphon . For instance, the edge density

converge to the integral

the triangle density

converges to the integral

the four-cycle density

converges to the integral

and so forth. One can use graph limits to prove many results in graph theory that were traditionally proven using the regularity lemma, such as the triangle removal lemma, and can also reduce many asymptotic graph theory problems to continuous problems involving multilinear integrals (although the latter problems are not necessarily easy to solve!). See this text of Lovasz for a detailed study of graph limits and their applications.

One can also express graph limits (and more generally hypergraph limits) in the language of nonstandard analysis (or of ultraproducts); see for instance this paper of Elek and Szegedy, Section 6 of this previous blog post, or this paper of Towsner. (In this post we assume some familiarity with nonstandard analysis, as reviewed for instance in the previous blog post.) Here, one starts as before with a sequence of finite graphs, and then takes an ultraproduct (with respect to some arbitrarily chosen non-principal ultrafilter ) to obtain a nonstandard graph , where is the ultraproduct of the , and similarly for the . The set can then be viewed as a symmetric subset of which is measurable with respect to the Loeb -algebra of the product (see this previous blog post for the construction of Loeb measure). A crucial point is that this -algebra is larger than the product of the Loeb -algebra of the individual vertex set . This leads to a decomposition

where the “graphon” is the orthogonal projection of onto , and the “regular error” is orthogonal to all product sets for . The graphon then captures the statistics of the nonstandard graph , in exact analogy with the more traditional graph limits: for instance, the edge density

(or equivalently, the limit of the along the ultrafilter ) is equal to the integral

where denotes Loeb measure on a nonstandard finite set ; the triangle density

(or equivalently, the limit along of the triangle densities of ) is equal to the integral

and so forth. Note that with this construction, the graphon is living on the Cartesian square of an abstract probability space , which is likely to be inseparable; but it is possible to cut down the Loeb -algebra on to minimal countable -algebra for which remains measurable (up to null sets), and then one can identify with , bringing this construction of a graphon in line with the traditional notion of a graphon. (See Remark 5 of this previous blog post for more discussion of this point.)

Additive combinatorics, which studies things like the additive structure of finite subsets of an abelian group , has many analogies and connections with asymptotic graph theory; in particular, there is the arithmetic regularity lemma of Green which is analogous to the graph regularity lemma of Szemerédi. (There is also a higher order arithmetic regularity lemma analogous to hypergraph regularity lemmas, but this is not the focus of the discussion here.) Given this, it is natural to suspect that there is a theory of “additive limits” for large additive sets of bounded doubling, analogous to the theory of graph limits for large dense graphs. The purpose of this post is to record a candidate for such an additive limit. This limit can be used as a substitute for the arithmetic regularity lemma in certain results in additive combinatorics, at least if one is willing to settle for qualitative results rather than quantitative ones; I give a few examples of this below the fold.

It seems that to allow for the most flexible and powerful manifestation of this theory, it is convenient to use the nonstandard formulation (among other things, it allows for full use of the transfer principle, whereas a more traditional limit formulation would only allow for a transfer of those quantities continuous with respect to the notion of convergence). Here, the analogue of a nonstandard graph is an *ultra approximate group* in a nonstandard group , defined as the ultraproduct of finite -approximate groups for some standard . (A -approximate group is a symmetric set containing the origin such that can be covered by or fewer translates of .) We then let be the external subgroup of generated by ; equivalently, is the union of over all standard . This space has a Loeb measure , defined by setting

whenever is an internal subset of for any standard , and extended to a countably additive measure; the arguments in Section 6 of this previous blog post can be easily modified to give a construction of this measure.

The Loeb measure is a translation invariant measure on , normalised so that has Loeb measure one. As such, one should think of as being analogous to a locally compact abelian group equipped with a Haar measure. It should be noted though that is not *actually* a locally compact group with Haar measure, for two reasons:

- There is not an obvious topology on that makes it simultaneously locally compact, Hausdorff, and -compact. (One can get one or two out of three without difficulty, though.)
- The addition operation is not measurable from the product Loeb algebra to . Instead, it is measurable from the coarser Loeb algebra to (compare with the analogous situation for nonstandard graphs).

Nevertheless, the analogy is a useful guide for the arguments that follow.

Let denote the space of bounded Loeb measurable functions (modulo almost everywhere equivalence) that are supported on for some standard ; this is a complex algebra with respect to pointwise multiplication. There is also a convolution operation , defined by setting

whenever , are bounded nonstandard functions (extended by zero to all of ), and then extending to arbitrary elements of by density. Equivalently, is the pushforward of the -measurable function under the map .

The basic structural theorem is then as follows.

Theorem 1 (Kronecker factor)Let be an ultra approximate group. Then there exists a (standard) locally compact abelian group of the formfor some standard and some compact abelian group , equipped with a Haar measure and a measurable homomorphism (using the Loeb -algebra on and the Baire -algebra on ), with the following properties:

- (i) has dense image, and is the pushforward of Loeb measure by .
- (ii) There exists sets with open and compact, such that
- (iii) Whenever with compact and open, there exists a nonstandard finite set such that
- (iv) If , then we have the convolution formula
where are the pushforwards of to , the convolution on the right-hand side is convolution using , and is the pullback map from to . In particular, if , then for all .

One can view the locally compact abelian group as a “model “or “Kronecker factor” for the ultra approximate group (in close analogy with the Kronecker factor from ergodic theory). In the case that is a genuine nonstandard finite group rather than an ultra approximate group, the non-compact components of the Kronecker group are trivial, and this theorem was implicitly established by Szegedy. The compact group is quite large, and in particular is likely to be inseparable; but as with the case of graphons, when one is only studying at most countably many functions , one can cut down the size of this group to be separable (or equivalently, second countable or metrisable) if desired, so one often works with a “reduced Kronecker factor” which is a quotient of the full Kronecker factor . Once one is in the separable case, the Baire sigma algebra is identical with the more familiar Borel sigma algebra.

Given any sequence of uniformly bounded functions for some fixed , we can view the function defined by

as an “additive limit” of the , in much the same way that graphons are limits of the indicator functions . The additive limits capture some of the statistics of the , for instance the normalised means

converge (along the ultrafilter ) to the mean

and for three sequences of functions, the normalised correlation

converges along to the correlation

the normalised Gowers norm

converges along to the Gowers norm

and so forth. We caution however that some correlations that involve evaluating more than one function at the same point will not necessarily be preserved in the additive limit; for instance the normalised norm

does not necessarily converge to the norm

but can converge instead to a larger quantity, due to the presence of the orthogonal projection in the definition (4) of .

An important special case of an additive limit occurs when the functions involved are indicator functions of some subsets of . The additive limit does not necessarily remain an indicator function, but instead takes values in (much as a graphon takes values in even though the original indicators take values in ). The convolution is then the ultralimit of the normalised convolutions ; in particular, the measure of the support of provides a lower bound on the limiting normalised cardinality of a sumset. In many situations this lower bound is an equality, but this is not necessarily the case, because the sumset could contain a large number of elements which have very few () representations as the sum of two elements of , and in the limit these portions of the sumset fall outside of the support of . (One can think of the support of as describing the “essential” sumset of , discarding those elements that have only very few representations.) Similarly for higher convolutions of . Thus one can use additive limits to partially control the growth of iterated sumsets of subsets of approximate groups , in the regime where stays bounded and goes to infinity.

Theorem 1 can be proven by Fourier-analytic means (combined with Freiman’s theorem from additive combinatorics), and we will do so below the fold. For now, we give some illustrative examples of additive limits.

Example 2 (Bohr sets)We take to be the intervals , where is a sequence going to infinity; these are -approximate groups for all . Let be an irrational real number, let be an interval in , and for each natural number let be the Bohr setIn this case, the (reduced) Kronecker factor can be taken to be the infinite cylinder with the usual Lebesgue measure . The additive limits of and end up being and , where is the finite cylinder

and is the rectangle

Geometrically, one should think of and as being wrapped around the cylinder via the homomorphism , and then one sees that is converging in some normalised weak sense to , and similarly for and . In particular, the additive limit predicts the growth rate of the iterated sumsets to be quadratic in until becomes comparable to , at which point the growth transitions to linear growth, in the regime where is bounded and is large.

If were rational instead of irrational, then one would need to replace by the finite subgroup here.

Example 3 (Structured subsets of progressions)We take be the rank two progressionwhere is a sequence going to infinity; these are -approximate groups for all . Let be the subset

Then the (reduced) Kronecker factor can be taken to be with Lebesgue measure , and the additive limits of the and are then and , where is the square

and is the circle

Geometrically, the picture is similar to the Bohr set one, except now one uses a Freiman homomorphism for to embed the original sets into the plane . In particular, one now expects the growth rate of the iterated sumsets and to be quadratic in , in the regime where is bounded and is large.

Example 4 (Dissociated sets)Let be a fixed natural number, and takewhere are randomly chosen elements of a large cyclic group , where is a sequence of primes going to infinity. These are -approximate groups. The (reduced) Kronecker factor can (almost surely) then be taken to be with counting measure, and the additive limit of is , where and is the standard basis of . In particular, the growth rates of should grow approximately like for bounded and large.

Example 5 (Random subsets of groups)Let be a sequence of finite additive groups whose order is going to infinity. Let be a random subset of of some fixed density . Then (almost surely) the Kronecker factor here can be reduced all the way to the trivial group , and the additive limit of the is the constant function . The convolutions then converge in the ultralimit (modulo almost everywhere equivalence) to the pullback of ; this reflects the fact that of the elements of can be represented as the sum of two elements of in ways. In particular, occupies a proportion of .

Example 6 (Trigonometric series)Take for a sequence of primes going to infinity, and for each let be an infinite sequence of frequencies chosen uniformly and independently from . Let denote the random trigonometric seriesThen (almost surely) we can take the reduced Kronecker factor to be the infinite torus (with the Haar probability measure ), and the additive limit of the then becomes the function defined by the formula

In fact, the pullback is the ultralimit of the . As such, for any standard exponent , the normalised norm

can be seen to converge to the limit

The reader is invited to consider combinations of the above examples, e.g. random subsets of Bohr sets, to get a sense of the general case of Theorem 1.

It is likely that this theorem can be extended to the noncommutative setting, using the noncommutative Freiman theorem of Emmanuel Breuillard, Ben Green, and myself, but I have not attempted to do so here (see though this recent preprint of Anush Tserunyan for some related explorations); in a separate direction, there should be extensions that can control higher Gowers norms, in the spirit of the work of Szegedy.

Note: the arguments below will presume some familiarity with additive combinatorics and with nonstandard analysis, and will be a little sketchy in places.

## Recent Comments