A few months ago on his blog Terry Tao explained how one could, by analogy with the theory of graph limits, replace the explicit use of arithmetic regularity with a soft device which he calls an additive limit. Roughly speaking, the additive limit, or Kronecker factor, of a sequence of finite abelian groups is a compact quotient of the ultraproduct which controls the convolutions. The result is that many theorems from additive combinatorics, such as Roth’s theorem, which are usually proved using quantitative tools like Fourier analysis can instead be proved using soft tools more like the Lebesgue differentiation theorem.
The purpose of this post is to extend Tao’s construction to the nonabelian setting. Tao already stated in his post that this should be possible, so one could say that this is just an exercise in nonabelian Fourier analysis. On the other hand the proof in the nonabelian setting more or less forces a more categorical point of view, so certain points of this exercise are instructive.
1. Measurable Bohr compactification
Given any topological group there is a compact group , called the Bohr compactification of , such every continuous homomorphism from to a compact group factors uniquely through . One can think of as the ‘largest’ compact group in which has dense image. We need a variant of this definition for groups endowed only with a -algebra instead of a topology.
By a measurable group we mean a group together with a -algebra of subsets of . Note that we do not make any measurability assumptions about the group operation or even the left- or right-shifts, though certainly it would be sensible to do so in other contexts. For us the only role of is to distinguish among all homomorphisms the measurable homomorphisms. The analogue of Bohr compactification for measurable groups is given by the following theorem.
Theorem 1 (Existence of measurable Bohr compactification) For every measurable group there is a compact group together with a -measurable homomorphism such that every -measurable homomorphism from to a compact group factors uniquely as the composition of and a continuous homomorphism .
In category-theoretic terms is a left adjoint to the functor from compact groups to measurable groups which replaces a group’s topology with its Baire -algebra. By the adjoint functor theorem it suffices to check that the functor is continuous, which boils down to the following lemma. Incidentally the analogue of this lemma fails for the Borel -algebra, which is why we must consider the Baire -algebra instead.
Lemma 2 For compact Hausdorff spaces we have . In words, the Baire -algebra of the product is the product of the Baire -algebras.
Proof: The containment is immediate from the defintions. To prove the opposite containment it suffices to check that every continuous function is measurable with respect to . This is certainly true of functions which depend on only finitely many coordinates, and thus for all continuous functions by the Stone–Weierstrass theorem.
Those who, like me, are not used to thinking in terms of the adjoint functor theorem will appreciate a more pedestrian proof of Theorem 1. To this end, let be the set of all pairs , where is a compact group and is a -measurable homomorphism with dense in . Then
is the diagonal map then is the Bohr compactification of . Indeed, the measurability of follows from Lemma 2, and the universal property is essentially obvious: given a -measurable homomorphism with compact, the pair appears in , so we have continuous maps
whose composition satisfies ; moreover is unique because is dense in .
Alternatively, by the Peter–Weyl theorem, can be defined as the inverse limit of all measurable finite-dimensional unitary representations of .
It is natural to ask what relation the measurable Bohr compactification bears to the usual Bohr compactification . In particular, is just the composition ? Clearly if and only if every measurable homomorphism from to a compact group is continuous. This follows from Steinhaus’s theorem if is locally compact, but it certainly fails in general, for instance for with the topology inherited from .
2. The Bohr compactification of an ultrafinite group
Let be a sequence of finite groups and let be a nonprincipal ultrafilter. We form the ultraproduct and make it into a measurable group by giving it the Loeb -algebra , the -algebra generated by internal sets , where . We define the Loeb measure on internal sets by putting
and we define on by extension.
While the group operation is not generally measurable with respect to the product -algebra , it is measurable with respect to the larger -algebra . Moreover this latter -algebra is still ‘product-like’ in the sense that all -measurable obey Fubini’s theorem, so we have a sensibly defined convolution operation given
Now consider the Bohr compactification of . The first thing to notice is that is a -invariant Baire probability measure on . Since is dense in we conclude that is in fact -invariant, so by the uniqueness of Haar measure we must have
In the remainder of this section we relate the two convolution algebras and . Given we can form the pullback . Since
we see that is a well defined element of , and in fact defines an isometric embedding
In the other direction we have the pushforward
defined as the adjoint of . The identities
are readily verified. For instance, the last of these is verified by the following computation, valid for by -Fubini:
We can summarise the situation as an isometric Banach algebra isomorphism
The following theorem asserts that in fact alone determines convolutions in , and thus will more generally control all ‘first-order configurations’ in .
Theorem 3 We have . Thus all convolutions in can be computed in , in the sense that
for all .
The theorem follows from the following lemma.
Lemma 4 For all and we have
In particular by optimising we have
Proof: We borrow nonabelian harmonic analysis notation from Tao. Certainly we may assume that and are internal, say and . Then by nonabelian Plancherel,
where in the last line the supremum is taken over all . Fixing some such , by Plancherel again
so we may assume that for -most . But then the representations induce a measurable representation , which in turn by the universal property of factors through a continuous representation . Thus
This proves the lemma.
3. Quasirandomness
From an additive combinatorics point of view, nonabelian groups obey a structure versus randomness principle: the asymptotic behaviour with respect to linear configurations can usually be described as some combination of abelian and random-like behaviour. Following Gowers, we call a sequence of finite groups quasirandom if the least dimension of a nontrivial representation of tends to infinity with . For example for every nontrivial representation of the alternating group has dimension at least , so the sequence is quasirandom.
Theorem 5 The ultrafinite group has trivial Bohr compactification if and only if the least dimension of a nontrivial representation of tends to infinity as . In particular, is quasirandom if and only if is trivial for every .
First we need a simple lemma.
Lemma 6 Let and be groups with finite and a map which satisfies for of the pairs . Then there is a homomorphism such that for of the points .
Proof: For every and for of the pairs we have
so for each there is a unique such that
for of the points . Clearly for of the points , and for we have
for of the points , in particular for at least one , so is a homomorphism.
Proof: (of Theorem~5) Suppose we have a sequence of nontrivial homomorphisms for all on some neighbourhood of . Then induces a measurable homomorphism , and since has no small subgroups the induced homomorphism will also be nontrivial, so must be nontrivial.
Conversely suppose the least dimension of a nontrivial representation of tends to infinity as tends to , and let be a measurable homomorphism. By a countable saturation argument there is an internal function , say , such that almost everywhere. Then satisfies for of the pairs , so by the lemma there is a homomorphism such that for of the points . But by assumption any such homomorphism must be trivial for near enough to , so we must have almost everywhere, so almost everywhere. Moreover since we must in fact have identically. Since the Peter–Weyl theorem implies that is an inverse limit of matrix groups this implies that is trivial.
Equations are generally easy to solve in quasirandom groups. We illustrate this point with the following theorem.
Theorem 7 Let be quasirandom and let . Then there exists such that if and has density then we can find with .
Proof: Let , let , and let be the internal function . Then , so if is the Bohr compactification then . But by the previous theorem is trivial, so is a constant , so by Theorem 3 we have
In other words the number of pairs such that is at least as , but since was arbitrary this must hold as .
Here is another nice criterion for quasirandomness, which can be found in Gowers’s original paper: is not quasirandom if and only if the groups have nontrivial abelian quotients or nontrivial small quotients. In our setup we can write this the following way.
Theorem 8 Let be an ultrafinite group. Then one of the following three alternatives hold:
- is trivial.
- has a nontrivial abelian quotient.
- has a nontrivial finite quotient.
Proof: Suppose . By the previous theorem if is nontrivial then the groups have bounded-dimensional nontrivial representations as . By Jordan’s theorem, has a normal abelian subgroup of bounded index. If as then 2 holds, while if as then 3 holds.
Using this theorem one can prove a sort of converse to Theorem 7. If is not quasirandom then there are arbitrarily large and product-free subsets of density bounded away from . We leave the details to the reader.
4. Roth’s theorem
As an application of group limits we can prove the following version of Roth’s theorem.
Theorem 9 Let be a finite group on which the squaring map is -to-. Let be a subset of density . Then there are solutions to in . Equivalently, there are pairs such that .
Proof: If the theorem fails then we have finite groups , some , and subsets of density for which there are fewer than pairs such that . Let and . Then but
But note
and by Theorem 3 this is the same as
where . By Fubini’s theorem this is the same as , where
But a standard argument (approximating by a continuous function) shows that is a continuous nonnegative function, and
Hence on a neighbourhood of , so , in contradiction to (1).
We chose to count configurations of the form precisely because they are alternatively described by the rather simple equation . If instead we chose to count the more “obvious” nonabelian analgues of three-term arithmetic progressions, namely configurations of the form , then we would be counting solutions to the more complicated equation . The problem is that the count of these configurations is not obviously controlled by convolutions, so we can’t easily transport the problem to the Bohr compactification. In fact the situation is delicate and not completely understood: see for example this paper of Tao for the case of . [Later edit: This paper of Sarah Peluse solves this problem for simple groups.]