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.