Soficity, short cycles and the Higman group (after Helfgott-Juschenko)

Posted by: matheuscmss | October 11, 2015

Soficity, short cycles and the Higman group (after Helfgott-Juschenko)

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 ${Sym(n)}$ the group of all permutations of ${\{1,\dots, n\}}$ .

For ${g_1, g_2\in Sym(n)}$ , we define their distance ${d_n(g_1, g_2)}$ by

$\displaystyle d_n(g_1, g_2):=\frac{1}{n}\#\{1\leq i\leq n: g_1(i)\neq g_2(i)\}$

Definition 1 (Gromov; Weiss) Let ${G}$ be a group. Given ${\delta>0}$ and ${S\subset G}$ finite, we say that ${\phi:S\rightarrow Sym(n)}$ is a ${(S,n,\delta)}$ -sofic representation whenever

(a) ${\phi}$ is an “approximate homomorphism”: ${d_n(\phi(g)\phi(h),\phi(gh))<\delta}$ for all ${g,h\in S}$ with ${gh\in S}$ ;

(b) ${\phi(g)\in Sym(n)}$ has “few” fixed points for ${g\neq e}$ : ${d_n(\phi(g),id)>1-\delta}$ for all ${g\in S-\{e\}}$ .

We say that a group ${G}$ is sofic if it has ${(S,n,\delta)}$ -sofic representation for all ${S\subset G}$ finite, all ${\delta>0}$ (and some ${n\in\mathbb{N}}$ ).

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 ${m\geq 2}$ , let

$\displaystyle H_m := \langle a_1,\dots, a_m : a_i^{-1} a_{i+1} a_i = a_{i+1}^2 \textrm{ for all } i\in\mathbb{Z}/m\mathbb{Z} \rangle$

The groups ${H_2}$ and ${H_3}$ are trivial, and the group ${H_4}$ is the so-called Higman group.

Remark 1 Several statements in this post can be generalized for ${H_m}$ for all ${m\geq 4}$ , but for the sake of exposition we will stick to ${H_4}$ .

Theorem 2 (Helfgott-Juschenko) Assume that ${H_4}$ is sofic.Then, for every ${\varepsilon>0}$ , there exists ${n\in\mathbb{N}}$ and a bijection ${f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}}$ such that

(a) ${f}$ is an “almost exponential function”: ${f(x+1)=2f(x)}$ for all ${x\in S}$ where ${S\subset\mathbb{Z}/n\mathbb{Z}}$ is a subset of cardinality ${|S|\geq (1-\varepsilon)n}$ .

(b) ${f^4(x):=f\circ f\circ f\circ f(x)=x}$ for all ${x\in\mathbb{Z}/n\mathbb{Z}}$ .

Remark 2 The existence of functions ${f}$ as above is “unlikely” when ${\varepsilon>0}$ is small. More precisely, it is possible to show that there are no bijections ${f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}}$ satisfying item (a) with ${\varepsilon=0}$ and item (b) when ${n=p^5}$ is the fifth power of a prime ${p}$ (cf. Remark 4 below for a more precise statement).

In other words, if we could take ${\varepsilon=0}$ and ${n=p^5}$ in the statement of Theorem 2, the non-soficity of the Higman group ${H_4}$ would follow.

Unfortunately, the techniques of Helfgott and Juschenko do not allow us to take ${\varepsilon=0}$ in Theorem 2, but they permit to control the integer ${n}$ . More concretely, as we are going to see in Theorem 4 below, the integer ${n}$ can be chosen from any fixed sequence ${0<n_1<n_2<\dots}$ which is thick in the following sense:

Definition 3 A sequence ${0<n_1<n_2<\dots}$ of positive integers is thick if for every ${\varepsilon>0}$ there exists ${K>0}$ such that

$\displaystyle \frac{n_{k+1}}{n_k}\leq 1+\varepsilon$

for all ${k>K}$ .

Remark 3 It does not take much to be a thick sequence: for example, the sequences ${\{n^3\}_{n\in\mathbb{N}}}$ and ${\{p^5\}_{p \textrm{ prime}}}$ are thick.

As we already announced, the main result of Helfgott-Juschenko is the following improvement of Theorem 2:

Theorem 4 (Helfgott-Juschenko) Assume that ${H_4}$ is sofic and let ${0<n_1<n_2<\dots}$ be a thick sequence.Then, for every ${\varepsilon>0}$ , there exists ${k}$ and a bijection ${f:\mathbb{Z}/n_k\mathbb{Z}\rightarrow\mathbb{Z}/n_k\mathbb{Z}}$ such that

(a) ${f(x+1)=2f(x)}$ for all ${x\in S}$ where ${S\subset\mathbb{Z}/n_k\mathbb{Z}}$ is a subset of cardinality ${|S|\geq (1-\varepsilon)n_k}$ .

(b) ${f^4(x):=f\circ f\circ f\circ f(x)=x}$ for all ${x\in\mathbb{Z}/n_k\mathbb{Z}}$ .

Remark 4 The non-soficity of Higman group ${H_4}$ would follow from this theorem if the bijection ${f:\mathbb{Z}/n_k\mathbb{Z}\rightarrow \mathbb{Z}/n_k\mathbb{Z}}$ , ${n_k\in\{p^5\}_{p\textrm{ prime}}}$ , provided by this statement could be taken so that

(a*) ${f(x+1)=2f(x)}$ for all ${x\in S}$ where ${S\subset\mathbb{Z}/n_k\mathbb{Z}}$ is a subset of cardinality ${|S|\geq n_k-n_k^{1/6}}$ .

(b) ${f^4(x):=f\circ f\circ f\circ f(x)=x}$ for all ${x\in\mathbb{Z}/n_k\mathbb{Z}}$ .

Indeed, this is so because Glebsky and Holden-Robinson proved that there is no ${f}$ verifying (a*) and (b).

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 ${H_3}$ is trivial to show that, for each ${\varepsilon>0}$ , there exists ${n_{\varepsilon}\in\mathbb{N}}$ such that for any ${n\geq n_{\varepsilon}}$ there is no bijection ${f:\mathbb{Z}/n\mathbb{Z}\rightarrow \mathbb{Z}/n\mathbb{Z}}$ such that

(a) ${f(x+1)=2f(x)}$ for all ${x\in S}$ for ${|S|\geq (1-\varepsilon)n}$ .

(b) ${f^3(x):=f\circ f\circ f(x)=x}$ for all ${x\in S}$ for ${|S|\geq (1-\varepsilon)n}$ .

This last remark can be generalized as follows.

Theorem 5 (Helfgott-Juschenko) Let ${n, g\geq 2}$ be coprime. Consider the function ${f:\{0,1,\dots, n-1\}\rightarrow\{0,1,\dots, n-1\}}$ given by

$\displaystyle f(x)=g^x (\textrm{mod } n)$

Then, the equation

$\displaystyle f^3(x):=f\circ f\circ f(x)=x$

has at most ${o(n)}$ solutions ${x\in\{0,1,\dots, n-1\}}$ .

Remark 6 This theorem improves on a result of Glebsky-Shparlinski.

1.2. Main ideas in the proofs of Theorems 4 and 5

As we are going to see in a moment, the key ingredient in the proof of Theorem 4 is the following result of Kerr-Li and Elek-Szabo

Theorem 6 Sofic representations of an amenable group ${G}$ are “conjugated”: if ${\phi_1}$ , ${\phi_2}$ are ${(S, n, \delta)}$ -sofic representations of ${G}$ with ${n}$ large enough and ${\delta}$ small enough in terms of a parameter ${\varepsilon>0}$ , then there exists a bijection ${\tau:\{1,\dots,n\}\rightarrow \{1,\dots, n\}}$ such that

$\displaystyle (\tau\circ\phi_1(s)\circ\tau^{-1})(x) = \phi_2(s)(x)$

for all ${s\in S}$ and for ${\varepsilon}$ -almost all ${x}$ (i.e., for at least ${(1-\varepsilon)n}$ values of ${x}$ ).

while the idea of the proof of Theorem 5 is to use a finitary version of Poincaré recurrence theorem.

Let us now see how these ingredients are employed by Helfgott-Juschenko in their proofs of Theorems 4 and 5.

2. Proof of Theorem 4

2.1. Amenable groups and Baumslag-Solitar groups

Let ${G}$ be a finitely generated group, say ${G=\langle S\rangle}$ , ${S}$ finite. We say that ${G}$ is amenable if there exists a countable sequence ${e\in F_1\subset F_2\subset\dots\subset F_n\subset\dots\subset G}$ of finite sets exhausting ${G}$ (i.e., ${G=\bigcup\limits_{j\in\mathbb{N}} F_j}$ ) consisting of almost invariant subsets in the sense that:

$\displaystyle |sF_j\cup F_j|<\left(1+\frac{1}{j}\right)|F_j|$

for all ${s\in S}$ and ${j\in\mathbb{N}}$ .

The Baumslag-Solitar groups ${BS(1,m)}$ are

$\displaystyle BS(1,m):=\langle a_1, a_2: a_1^{-1} a_2 a_1 = a_2^m\rangle$

Example 1 ${BS(1,m)}$ is amenable.

It follows from its amenability that ${BS(1,m)}$ is a sofic group. As it turns out, one can give a direct proof of this last fact along the following lines. Given ${\varepsilon>0}$ , let ${n}$ be an integer such that

$\displaystyle \prod\limits_{p|n}(p-1)\geq (1-\varepsilon)n$

(e.g., let ${n}$ be a sufficiently large prime number), and ${n}$ is coprime with ${m}$ .

Define ${\psi_n: BS(1,m)\rightarrow Sym(\mathbb{Z}/n\mathbb{Z})}$ by

$\displaystyle \psi_n(a_1)(x):=\frac{1}{m} x, \quad \psi_n(a_2)(x):=x+1$

(so that ${\psi_n(a_1)^{-1}\psi_n(a_2)\psi_n(a_1) = \psi_n(a_2)^m}$ ). One can check that ${\psi_n}$ is a ${(S,n,O(\varepsilon))}$ -sofic representation.

2.2. End of proof of Theorem 4

Suppose ${H_4}$ is sofic. Then, the semi-direct product ${G_4}$ of ${\mathbb{Z}/4\mathbb{Z}}$ and ${H_4}$ is also sofic (because it is an amenable extension of a sofic group). Here, the semi-direct product is defined by letting a generator ${t\in\mathbb{Z}/4\mathbb{Z}}$ act on ${H_4}$ by conjugation as follows: ${a_{i+1} = t^{-1} a_i^{-1} t}$ , ${i\in\mathbb{Z}/4\mathbb{Z}}$ .

Denote by ${S}$ the set of words of length ${\leq 4}$ on ${\{a_1, a_2, a_3, a_4, t\}}$ , and let ${\phi: G_4\rightarrow Sym(n)}$ be a ${(S,n,\delta)}$ -sofic representation.

We think of the Baumslag-Solitar group ${BS(1,2)}$ as sitting inside ${H_4}$ and ${G_4}$ , and we consider the restriction ${\phi|_{BS(1,2)}}$ as an ${(S\cap BS(1,2),n,\delta)}$ -sofic representation.

By the theorem of Kerr-Li and Elek-Szabo (cf. Theorem 6 above), ${\phi|_{BS(1,2)}}$ is “conjugated” to the representation ${\psi_n}$ constructed above, i.e., there exists ${\tau:\mathbb{Z}/n\mathbb{Z}\rightarrow \mathbb{Z}/n\mathbb{Z}}$ such that, for all ${s\in S}$ ,

$\displaystyle \psi_n(s)(x) = \tau\circ\phi|_{BS(1,2)}\circ\tau^{-1}(s)(x)$

for at least ${(1-\varepsilon)n}$ values of ${x}$ .

Since ${\phi}$ is an almost homomorphism, ${t^{-1}a_1^{-1}t=a_2}$ and ${t^4=1}$ , we have that

$\displaystyle \phi(a_2)(x) = \phi(t^{-1})\phi(a_1^{-1})\phi(t)(x)$

for almost all ( ${\geq (1-\varepsilon)n}$ ) values of ${x}$ . Thus,

$\displaystyle \begin{array}{rcl} \psi_n(a_2)(x) = (\tau\circ\phi\circ\tau^{-1}(t))^{-1}\circ \psi_n(a_1)^{-1} \circ (\tau\circ\phi\circ\tau^{-1}(t))(x) \end{array}$

and

$\displaystyle \phi(t)^4(x)=\phi(t^4)(x)=x$

for almost all values of ${x}$ . Furthermore, since ${\phi(t)}$ and ${\tau\circ\phi\circ\tau^{-1}(t)}$ are conjugated, the last equation is also true for ${\tau\circ\phi\circ\tau^{-1}(t)}$ .

Therefore, by adjusting the values of ${\tau\circ\phi\circ\tau^{-1}}$ on a subset of values of ${x}$ of cardinality ${\leq\varepsilon n}$ , we obtain ${f:\mathbb{Z}/n\mathbb{Z}\rightarrow \mathbb{Z}/n\mathbb{Z}}$ such that ${f(x) = (\tau\circ\phi\circ\tau^{-1}(t))(x)}$ and

$\displaystyle x+1=\psi_n(a_2)(x) = f^{-1}(2f(x)), \textrm{ i.e. } f(x+1) = 2 f(x)$

for ${\geq(1-\varepsilon)n}$ values of ${x}$ , and ${f^4(x)=x}$ for all values of ${x}$ . 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 ${x\mapsto g^x}$ are well-defined in ${\mathbb{Z}/n\mathbb{Z}}$ . Nevertheless, the discussion below can be adapted to produce an actual proof of Theorem 5.

Let ${g}$ be a generator of ${(\mathbb{Z}/p\mathbb{Z})^{\times}}$ , and suppose that

$\displaystyle g^{g^{g^x}}=x \ \ \ \ \ (1)$

for a positive proportion of values of ${x}$ .

Then, there exists ${0\neq k=O(1)}$ (bounded in terms of the proportion above) such that (1) holds for a both ${x}$ and ${x+k}$ for a positive proportion of values of ${x}$ : this is an incarnation of Poincaré recurrence theorem.

In other terms, for a positive proportion of values of ${x}$ , one has

$\displaystyle g^{g^{g^{x+k}}} = x + k = g^{g^{g^x}} + k$

By setting ${y:=g^{g^x}}$ , one deduces that the equation

$\displaystyle g^{y^{g^k}} = g^y + k \ \ \ \ \ (2)$

has a set of solutions ${y}$ with positive proportion.

Using Poincaré recurrence theorem once more, we can find ${0\neq \ell=O(1)}$ such that (2) holds for a both ${y}$ and ${\ell y}$ for a positive proportion of values of ${y}$ .

By writing ${z:=g^y}$ , we have a positive proportion of values of ${z}$ satisfying the equation

$\displaystyle (z+k)^{\ell^{g^k}} = z^{\ell}+k$

However, this is a contradiction because ${g}$ , ${k}$ and ${\ell}$ are fixed, so that the previous equation is a polynomial equation on ${z}$ with a bounded number of solutions (and, thus, it can’t be satisfied for a positive proportion of values of ${z}$ ).

Posted in expository, math.GR, math.NT, Mathematics | Tags: amenable group, Baumslag-Solitar group, Harald Helfg, Higman group, Kate Juschenko, Poincare recurrence theorem, sofic group

Responses

Thanks for the notes. I think there’s a small typo in Def 1: we should require that $d_n(\phi(g),id) > 1 - \delta$ rather than just $d_n(\phi(g),id) > \delta$ . [Corrected. Thanks, M.]
By: Sean Eberhard on January 22, 2016
at 9:52 am

Reply

M	T	W	T	F	S	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

	Adam on Breuillard-Sert’s joint…
	Adam on Breuillard-Sert’s joint…
	Writing a Hilbert C*… on ERT16: Compact extensions
	matheuscmss on Yoccoz book collection at…
	Jairo B. on Yoccoz book collection at…

Disquisitiones Mathematicae