Last August 25th, Harald Helfgott gave the talk “Soficity, short cycles and the Higman group” (based on joint work with Kate Juschenko) during the Second Workshop on Combinatorics, Number Theory and Dynamical Systems coorganized by Christian Mauduit, Carlos Gustavo Moreira, Yuri Lima and myself at IMPA (Brazil).
This post is a transcription of my notes for Harald’s talk, and, evidently, all mistakes/errors are my responsibility.
1. Some notations
We denote by the group of all permutations of .
For , we define their distance by
Definition 1 (Gromov; Weiss) Let be a group. Given and finite, we say that is a -sofic representation whenever
- (a) is an “approximate homomorphism”: for all with ;
- (b) has “few” fixed points for : for all .
We say that a group is sofic if it has -sofic representation for all finite, all (and some ).
Basic examples of sofic groups are: finite groups, amenable groups, etc. In general, it is known that several families of groups are sofic, but it is an important open problem to construct (or show the existence of) non-sofic groups.
The goal of this post is to discuss a candidate for non-sofic group and its connections to Number Theory.
1.1. Higman groups
For , let
The groups and are trivial, and the group is the so-called Higman group.
Remark 1 Several statements in this post can be generalized for for all , but for the sake of exposition we will stick to .
- (a) is an “almost exponential function”: for all where is a subset of cardinality .
- (b) for all .
Remark 2 The existence of functions as above is “unlikely” when is small. More precisely, it is possible to show that there are no bijections satisfying item (a) with and item (b) when is the fifth power of a prime (cf. Remark 4 below for a more precise statement).
In other words, if we could take and in the statement of Theorem 2, the non-soficity of the Higman group would follow.
Unfortunately, the techniques of Helfgott and Juschenko do not allow us to take in Theorem 2, but they permit to control the integer . More concretely, as we are going to see in Theorem 4 below, the integer can be chosen from any fixed sequence which is thick in the following sense:
Definition 3 A sequence of positive integers is thick if for every there exists such that
for all .
Remark 3 It does not take much to be a thick sequence: for example, the sequences and are thick.
As we already announced, the main result of Helfgott-Juschenko is the following improvement of Theorem 2:
- (a) for all where is a subset of cardinality .
- (b) for all .
- (a*) for all where is a subset of cardinality .
- (b) for all .
Remark 5 A natural question related to Theorem 4 is: what happens with fewer iterations in item (b)? In this situation, it is possible to use the fact that the group is trivial to show that, for each , there exists such that for any there is no bijection such that
- (a) for all for .
- (b) for all for .
This last remark can be generalized as follows.
Then, the equation
has at most solutions .
Remark 6 This theorem improves on a result of Glebsky-Shparlinski.
1.2. Main ideas in the proofs of Theorems 4 and 5
Theorem 6 Sofic representations of an amenable group are “conjugated”: if , are -sofic representations of with large enough and small enough in terms of a parameter , then there exists a bijection such that
for all and for -almost all (i.e., for at least values of ).
while the idea of the proof of Theorem 5 is to use a finitary version of Poincaré recurrence theorem.
2. Proof of Theorem 4
2.1. Amenable groups and Baumslag-Solitar groups
Let be a finitely generated group, say , finite. We say that is amenable if there exists a countable sequence of finite sets exhausting (i.e., ) consisting of almost invariant subsets in the sense that:
for all and .
The Baumslag-Solitar groups are
Example 1 is amenable.
It follows from its amenability that is a sofic group. As it turns out, one can give a direct proof of this last fact along the following lines. Given , let be an integer such that
(e.g., let be a sufficiently large prime number), and is coprime with .
(so that ). One can check that is a -sofic representation.
2.2. End of proof of Theorem 4
Suppose is sofic. Then, the semi-direct product of and is also sofic (because it is an amenable extension of a sofic group). Here, the semi-direct product is defined by letting a generator act on by conjugation as follows: , .
Denote by the set of words of length on , and let be a -sofic representation.
We think of the Baumslag-Solitar group as sitting inside and , and we consider the restriction as an -sofic representation.
By the theorem of Kerr-Li and Elek-Szabo (cf. Theorem 6 above), is “conjugated” to the representation constructed above, i.e., there exists such that, for all ,
for at least values of .
Since is an almost homomorphism, and , we have that
for almost all () values of . Thus,
for almost all values of . Furthermore, since and are conjugated, the last equation is also true for .
Therefore, by adjusting the values of on a subset of values of of cardinality , we obtain such that and
for values of , and for all values of . This completes the proof of Theorem 4.
3. Idea of proof of Theorem 5
This short section contains an oversimplified argument because we will implicitly assume that the exponential maps are well-defined in . Nevertheless, the discussion below can be adapted to produce an actual proof of Theorem 5.
Then, there exists (bounded in terms of the proportion above) such that (1) holds for a both and for a positive proportion of values of : this is an incarnation of Poincaré recurrence theorem.
In other terms, for a positive proportion of values of , one has
Using Poincaré recurrence theorem once more, we can find such that (2) holds for a both and for a positive proportion of values of .
By writing , we have a positive proportion of values of satisfying the equation
However, this is a contradiction because , and are fixed, so that the previous equation is a polynomial equation on with a bounded number of solutions (and, thus, it can’t be satisfied for a positive proportion of values of ).