# Lower bound on growth for intersection of two subgroups of free group

Let $$\Gamma_1$$ and $$\Gamma_2$$ be two subgroups of the rank-$$2$$ free group $$F_2$$. Can then one find a nontrivial lower bound on the growth exponent of their intersection $$\Gamma_1 \cap \Gamma_2$$, in terms of the growth exponents of the two subgroups?

Here by the growth exponent of a subgroup $$\Gamma \subset F_2$$ I mean the real number

$$\lim_{n \to \infty} \frac{1}{n} \log \# \{w \in \Gamma \;\mid\; \ell(w) \leq n\},$$

where $$\ell$$ denotes the word length inside $$F_2$$; so that this exponent lies between $$0$$ and $$\log 3$$.

For semigroups, clearly there is no hope for such a lower bound. Indeed, in the rank-$$2$$ free monoid $$A^*$$ (on the alphabet $$A = \{a, b\}$$), the two subsemigroups $$S_1 := (aA^*)^+$$ and $$S_2 := (bA^*)^+$$ (generated by all the words starting with $$a$$, resp. with $$b$$) are disjoint, but have maximal growth exponent (namely $$\log 2$$).

However this construction does not work at all for groups. I have tried to find pairs of subgroups in $$F_2$$ that have large growth exponents but trivial (or at least small) intersection, but I am not even sure where to start. Any help would be appreciated!

• Do you know this limit to exist? or would you rather ask about liminf/limsup?
– YCor
Oct 28, 2020 at 10:42
• OK, first of all, I had made a typo: I meant to count words in balls, not spheres. With the original definition, indeed, it is easy to come up with examples where the limit does not exist. With the corrected definition, I am almost (but not quite completely) sure that it always exists. Do you think I am mistaken? In the meanwhile, I will double-check this. Oct 28, 2020 at 11:01
• You are right; I just changed it. Oct 28, 2020 at 11:52
• It would help if you can relate the growth exponent of a subgroup to the corresponding Stallings core graph. (I would guess someone has done this already.) Core graphs of intersections are easy to compute using fibre products (see Stallings' paper Topology of finite graphs).
– HJRW
Oct 28, 2020 at 12:16

OK, in fact I figured this out as soon as I properly understood how Stallings graphs work. Here is the analogous construction for groups.

Let $$\Gamma_0$$ be the subgroup of the free group $$F_2 = \langle a, b \rangle$$ generated by the set $$\{a^{k+1} b^{-1} a^{-k} \;\mid\; k \geq 0\}$$. I claim that elements of $$\Gamma_0$$ can be characterized as follows: a reduced word $$w(a,b,a^{-1},b^{-1})$$ lies in $$\Gamma_0$$ if and only if the word obtained from $$w$$ by substituting an opening parenthesis to each $$a$$ and $$b$$, and a closing parenthesis to each $$a^{-1}$$ and $$b^{-1}$$, is well-parenthesized.

This is probably easy to show by hand, but the right way to see things is probably to use Stallings graphs (see e.g. these slides for a very quick visual introduction: http://www.lix.polytechnique.fr/combi/archivesSeminaire/transparents/150513_Frederique_Bassino.pdf, or this paper for a more detailed one: https://arxiv.org/abs/math/0202285 ). Their key property is that a word $$w \in F_2$$ belongs to some subgroup $$\Gamma$$ if and only if there exists a loop in the Stallings graph of $$\Gamma$$, starting and ending at its basepoint, and labeled by $$w$$. Now the Stallings graph of $$\Gamma_0$$ has vertices indexed by $$\mathbb{Z}_{\geq 0}$$ (with basepoint $$0$$) and, for each vertex $$n$$, an edge labeled $$a$$ and an edge labeled $$b$$ both going from $$n$$ to $$n+1$$; and the characterization follows immediately.

It is then not very hard to see that $$\Gamma_0$$ has maximal possible growth exponent, namely $$\log 3$$. In fact, the number of words of length $$2n$$ in $$\Gamma$$ is twice the sequence https://oeis.org/A059231 , which grows like a polynomial times $$3^{2n}$$ (OEIS gives the asymptotic estimate "a(n) ~ sqrt(2)3^(2n+1)/(8*sqrt(Pi)*n^(3/2))").

Now we set $$\Gamma_1 := a \Gamma_0 a^{-1}$$ and $$\Gamma_2 := b \Gamma_0 b^{-1}$$. Of course these two groups still have growth exponent $$\log 3$$. However, their intersection is trivial: indeed, all nontrivial elements of $$\Gamma_1$$ (resp. of $$\Gamma_2$$) actually start with $$a$$ (resp. $$b$$) and end with $$a^{-1}$$ (resp. $$b^{-1}$$), even when written in reduced form.

This last statement is obvious from the characterization of $$\Gamma_0$$, but once again it is helpful to think in terms of Stallings graphs, in particular so as to bring into light the parallel with the semigroup construction. The Stallings graph of $$\Gamma_1$$ (resp. $$\Gamma_2$$) is obtained from the Stallings graph of $$\Gamma_0$$ by adding a new basepoint, with a single edge from that vertex to the old basepoint labeled by $$a$$ (resp. by $$b$$).

• Is there a finitely generated subgroup of infinite index with maximal growth exponent? I suppose at the very least one could `cut off' $\Gamma_0$ (so $0\leq k\leq n$, say) and obtain a sequence of subgroups with exponent tending towards $\log 3$.
– HJRW
Oct 28, 2020 at 16:04
• Your second sentence is certainly true. As for the first sentence, I would guess that the answer is "no". Here is the reasoning: there is a theorem that says that if a finitely generated subgroup of $F_2$ has infinite index, then at least one vertex of its Stallings graph has at least one transition missing. I think that this implies that the transition matrix of the Stallings graph (whose spectrum controls the growth of the group) must have spectral radius strictly less than 3. If you are not convinced, I can try to develop this argument. Oct 28, 2020 at 19:56
• Thanks! I’d be interested if you can show this, but it’s not super-important.
– HJRW
Oct 29, 2020 at 6:50