1

I am looking for a reference (or a simple proof) of the fact that a free group is sofic. The preferred dynamical definition of a sofic group seems to be that there is a sequence of finite sets $V_n$ with $|V_n|\to\infty$ and a sequence of maps $\sigma_n\colon \Gamma\to \text{Sym}(V_n)$ such that for (1) fixed $g$ and $h$, $\sigma_n(gh)(v)=\sigma_n(g)\sigma_n(h)v$ for most $v\in V_n$ as $n\to\infty$; and (2) for fixed $g\ne e$, $\sigma_n(g)v\ne v$ for most $v\in V_n$ as $n\to\infty$.

Many references that I have seen establish this property for amenable groups (where $V_n$ is taken to be a Følner sequence in $\Gamma$, and $\sigma_n(g)$ is defined to be left multiplication by $g$ where this leaves elements of $V_n$ inside $V_n$; and defined arbitrarily to make $\sigma_n(g)$ a bijection for other elements of $V_n$) and for residually finite groups (where $V_n$ is taken to be a sequence of quotients of $\Gamma$ by increasing normal subgroups of finite index).

It is quite straightforward to see that $SL(d,\mathbb Z)$, for example, is residually finite. The case of the free group $F_n$ is described in the references that I have seen (a number of lectures online, Lewis Bowen's ICM address and the book of Kerr and Li) as an "interesting technical exercise", or is deduced by embedding $F_n$ in $SL(d,\mathbb Z)$.

Does anyone know a direct proof that $F_n$ is sofic, or have a reference to such a proof?
Anthony Quas
  • 22,470
  • $F_n$ embeds explicitly into $\mathrm{SL}_2(\mathbf{Z})$ (as you already seem to mention). So what is the "interesting" exercise? – YCor Jun 14 '21 at 23:12
  • What I believe is interesting (see e.g. http://www.birs.ca/events/2017/5-day-workshops/17w5068/videos/watch/201707240903-Bowen.html) is to see that the free group is sofic by explicitly constructing the maps $\sigma_n$ without going through $SL(d,\mathbb Z)$. [NB: In the video I linked to, Bowen gives two definitions of sofic: one by obtaining the Cayley graph as a Benjamini-Schramm limit of labelled graphs; and another through sofic approximations; the exercise was described in terms of the first of these.] (Maybe I could ask: what if I didn't know that $F_n$ embeds in $SL_2(\mathbb Z)$?) – Anthony Quas Jun 14 '21 at 23:26
  • 2
    Indeed the first proof, by O. Schreier, of residual finiteness of free groups is not through congruence quotient but uses a Schreier graph argument. Unfortunately it's quite far from giving maps as you want, since the proof provides one action for one element, so one first needs one such action for each element in the $n$-ball (thus giving an action that is faithful on the $n$-ball) and then consider the left action on the image of this action, to get a action that is free on the $n$-ball. This yields a huge target group (of size factorial of exponential of $n$). – YCor Jun 14 '21 at 23:32
  • 3
    You can take the ball of radius n in the Cayley graph of the free group and ask edges between these elements.Then you get for each generator x of the free group a partial permutation of the set of words of length at most n by taking the initial vertex of an edge labeled by x to the final vertex. Any partial permutation of a finite set can be extended to a permutation since the size of the complement of the domain is the size of the completent of the range. Extending all the partial permutations associated to the generators to permutations gives an action on the n-ball separating the n-ball. – Benjamin Steinberg Jun 15 '21 at 01:13
  • 2
    See also https://mathoverflow.net/questions/20471/why-are-free-groups-residually-finite – Benjamin Steinberg Jun 15 '21 at 01:14
  • @BenjaminSteinberg the problem is that you need more than separating the $n$-ball: you need, for every non-identity $h$ in the $n$-ball, to ensure that $h$ acts with a proportion $\le\varepsilon$ of fixed points on the given finite set. – YCor Jun 15 '21 at 07:18
  • @YCor, oh I see. Then you have to grow the set to are acting on – Benjamin Steinberg Jun 15 '21 at 10:32
  • @AnthonyQuas: if you just want to avoid SL_2, you should be happy with a direct proof that free groups are residually finite. @BenjaminSteinberg’s comment provides exactly that proof; it’s I think formally the same as Schreier’s original proof. – HJRW Jun 15 '21 at 22:11
  • By the way, if you’re interested in Bowen’s work, he gave a related construction of finite-index subgroups of free groups in this paper: https://arxiv.org/abs/0802.0185v5 , – HJRW Jun 15 '21 at 22:14

1 Answers1

1

There is a very simple probabilistic proof. Begin with a large finite set - its elements are called "parents", and let each parent have $2d$ offspring labelled with the generators of our free group. Now let the kids go to a nightclub, where each of them randomly finds a partner from the opposite sex (or shall I say gender?). Then the resulting labelled graph on the set of parents is a Schreier graph of the free group which converges to the Cayley tree as the number of parents goes to infinity.

R W
  • 16,643
  • Thank you! When you say "finds a couple", I guess you mean "finds a partner?" – Anthony Quas Jun 15 '21 at 01:57
  • So what is $V_n$ and what is the action? The children are parents themselves? The number of possible genders is what? $2d$? And what is the opposite gender for a gender $i$? – markvs Jun 15 '21 at 01:57
  • @Anthony Quas - Yes, of course – R W Jun 15 '21 at 03:05
  • @MarkSapir : my understanding is that each parent has a child of each “gender”, $S$. All of the children go out and hook up with a randomly chosen partner of the opposite gender ($s$ with $s^{-1}$). – Anthony Quas Jun 15 '21 at 03:08
  • @Mark Sapir - I use an equivalent definition of soficity in terms of the Benjamini-Schramm convergence mentioned by Anthony Quas in one of his comments. There are $n$ parents and $2dn$ children. Genders are labelled with the generators and their inverses. The opposite gender to $i$ is of course $-i$ (i.e., the inverse generator). After the coupling is completed we have a Schreier graph on the set of parents, which for large $n$ locally looks almost like the Cayley tree. – R W Jun 15 '21 at 03:16
  • @RW: The OP wants $V_n$ and an action. If children are not parents as well this tree has height 2 and does not approximate the Cayley graph. – markvs Jun 15 '21 at 03:19
  • @Mark Sapir - Well, $V_n$ is the constructed (random) Schreier graph endowed with a natural action (as any Schreier graph is). The claim is that this graph with probability close to 1 approximates the Cayley tree. – R W Jun 15 '21 at 03:24
  • It is still not clear. If it is a Schreier graph of a subgroup of finite index, there must be cycles. So some (all) parents from the set are descendants of themselves. That is not what is in the answer. You need to show that the minimal cycle length is arbitrary large a.s. in order to claim that the graphs tend to a tree. I think it is much harder than using the modular group and its finite quotients. – markvs Jun 15 '21 at 03:40
  • @ Mark Sapir Of course, there are cycles. I only claim that with probability close to one all cycles are long enough, which is the case because it is highly unlikely to form a cycle of a fixed length in a big crowd with the random mating mechanism I have described. One doesn't have to show that there are no cycles of a prescribed length at all - it is just enough to show that their frequency goes to 0. I find my argument much more transparent, but de gustibus non disputandum est :) – R W Jun 15 '21 at 04:05