Contents

Notation & Background

Let \(\mathcal{P}\) be some property of groups, for example, abelian, nilpotent, or free. A group \(G\) is said to virtually \(\mathcal{P}\) if it has a finite-index subgroup \(H\) with has property \(\mathcal{P}\).

Suppose that \(G\) is a group with finite generating set \(X\). Then, we write \(X^*\) for the free monoid generated by \(X\), that is, \(X^*\) is the set of all words which can be spelled using the letter in \(X\). For each \(w \in X^*\), we write \(\overline{w}\) for the corresponding element in \(G\), that is, \(w \mapsto \overline{w}\) is a map from \(X^*\) to \(G\).

Now suppose that \(w = w_1 w_2 \cdots w_k \in X^*\) where each \(w_i \in X\), then we define the word length as \(|w|_X = k\). This can then be extended to a metric on \(G\) as \[ \ell_X(g) := \min\{ k \in \mathbb{N} \mid w \in X^* \ \ \text{with}\ \ |w|_X=k\ \ \text{and}\ \ \overline{w}=g \}. \] That is, \(\ell_X(g)\) is the minimal length of a word which represents the element \(g\in G\). Note: from this we can show that \(G\) is a metric space with respect to the metric \(d_X(g,h) = \ell_X(g^{-1}h)\).

If \(w\in X^*\) is a word with \(\overline{w}=g\in G\) and \(\ell_X(g) = |w|_X\), then we say that \(w\) is a geodesic.

A brief history of growth:

From the definitions above, we can define the volume growth function of a group as \[ \gamma_X(n) := \#\{ g \in G \mid \ell_X(g) \leqslant n \}. \] That is, \(\gamma_X(n)\) counts the number of elements which can be spelled out with words in \(X\) of length at most \(n\). We then say that two growth functions \(f(n)\) and \(g(n)\) are equivalent if there exists some constant \(C \geqslant 1\) such that \[ C\cdot f(C\cdot n) \geqslant g(n) \quad\text{and}\quad C\cdot g(C\cdot n) \geqslant f(n). \] It is a well-known result, proven independently by Švarc [10] and Milnor [8] , that the volume growth function \(\gamma_X(n)\) is invariant under change of generating set and quasi-isometry with respect to the above equivalence relation. From this, it was noticed that every group known in the 1960's had growth that was either equivalent to a polynomial, or equivalent to an exponential.

In 1968, Milnor [9] asked the following two questions:

  1. Is there a characterisation of groups with polynomial growth?
  2. Are there groups of intermediate growth (i.e. neither polynomial nor exponential)?

The first of Milnor's questions was answered in 1981 by Gromov [7] who showed that a group has polynomial growth if and only if it is virtually nilpotent. Milnor's second question was answered in 1984 by Grigorchuk [6] where it was shown that there exists a group of intermediate growth.

Topic: Geodesic Growth

Definition

Let \(G\) be a group with finite generating set \(X\), then the geodesic growth function \(a_X(n)\) counts the number of geodesics with length at most \(n\). That is, \[ a_X(n) := \#\{ w \in X^* \mid \ell_X(\overline{w}) = |w|_X \leqslant n \}. \] We then notice that each element of \(G\) has at least one geodesic.

To study the asymptotics of the function \(a_X(n)\), it is often helpful to find nice closed forms for the geodesic growth series \[ A_X(z) = \sum_{n=0}^\infty a_X(n) \, z^n. \] For example, if \(A_X(n)\) is a rational series (i.e. there are polynomials \(P(z)\) and \(Q(z)\) such that \(A_X(z)=P(z)/Q(z)\)), then there would exist finitely many polynomials \(f_1(n)\), \(f_2(n)\), …, \(f_k(n)\) and a constant \(N \geqslant 0\) such that \[ a_X(n) = f_1(n) \gamma_1^{-n} +f_2(n) \gamma_2^{-n} +\cdots +f_k(n) \gamma_k^{-n} \] for all \(n \geqslant N\), where \(\gamma_i\) are the singularities of the series \(A_X(n)\).

Observation & Examples

The geodesic growth \(a_X(n)\) is bound from below by the volume growth \(\gamma_X(n)\). Thus, if \( a_X(n) \) has a polynomial upper bound, then the group must be a virtually nilpotent group.

Unlike volume growth, geodesic growth function depends heavily on the chosen generating set. For example, take the virtually cyclic group \[ \mathbb{Z} \times C_2 = \left\langle z,t \mid t^2 = 1,\ zt=tz \right\rangle. \] A part of the Cayley graph of \(\mathbb{Z} \times C_2\), with respect to the generating set \(X = \{z,z^{-1}, t\}\) is given in Figure 1. For this generating set, the group has polynomial geodesic growth, in particular, \( a_X(n) = n^2+3n \) for each \(n \geqslant 2 \).

Figure 1: Cayley graph of \(\mathbb{Z}\times C_2\) with respect to generating set \(X = \{z,z^{-1}, t\}\).

Now consider the group \(\mathbb{Z} \times C_2\), with respect to the generating set \(X = \{zt, z^{-1} t, z, z^{-1}\}\) as in Figure 2. In this case, the geodesic growth is exponential, in particular, \( a_X(n) = 2^{n+1}-1 \).

············
Figure 2: Cayley graph of \(\mathbb{Z}\times C_2\) with respect to generating set \(X = \{zt, z^{-1} t, z, z^{-1}\}\).

Thus, when we speak of the geodesic growth of a group, we must always specify a generating set.

Literature

Two natural questions then arrise:

  1. Is there a characterisation of groups with polynomial geodesic growth?
  2. Are there groups of intermediate geodesic growth (i.e. neither polynomial nor exponential)?

The geodesic growth of the nilpotent and virtually abelian groups was studied by Bridson, Burillo, Elder and Šunić [4] . In this work, the authors showed that showed that every nilpotent group is either virtually abelian, or has exponential geodesic growth with respect to every generating sets; and they gave the first example of a group \[ \mathbb{Z}^2 \rtimes C_2 = \left\langle x,y,t \mid xy=yx, t^2=1, txt=y \right\rangle \] with polynomial geodesic growth (with respect to the generating set \(\{x,x^{-1},y,y^{-1}\}\)) and is not virtually cyclic.

The problem of whether there exists a group of intermediate geodesic growth was studied in the thesis of Brönnimann [5] . In particular, Brönnimann showed that in almost all groups of intermediate growth (which were known at the time), the geodesic growth is exponential for the usual generating set. The one example where Brönnimann's techniques did not work is referred to as the Fabrykowski-Gupta group.

Personal Contributions

  • Characterised the geodesic growth for virtually abelian groups [2] .
    Main results:
    • virtually abelian groups cannot have intermediate geodesic growth;
    • for virtually abelian groups, the geodesic growth is either exponential with D-finite generating function, or polynomial with rational generating function and
    • the set of all geodesics of a virtually abelian group forms a blind multicounter language.
    All of the above results hold for every finite (weighted monoid) generating set.
  • In a joint work with Murray Elder [3] , we showed that there exists a virtually 2-step nilpotent group with polynomial geodesic growth. Previously, it was conjectured that all groups of polynomial geodesic growth were virtually abelian.

Open Problems

  • Is the geodesic growth series for the group introduced in [3] rational?
  • Is there an intermediate growth group with intermediate geodesic growth?
  • Is there a characterisation of groups with polynomial geodesic growth?
  • Is there a virtually abelian group without rational geodesic growth?

Topic: Word Problems & Cogrowth

Let \(G\) be a group with generating set \(X\), then the word problem is the set of words \[ \mathrm{WP}_X := \{ w\in X^* \mid \overline{w} = 1 \}. \] That is, \(\mathrm{WP}_X\) is the set of all words which evaluate to the group identity.

The cogrowth series is then the generating function \[ \mathrm{C}_X(z) := \sum_{n=0}^\infty c_n z^n \] where each term \(c_n\) counts the words in \(\mathrm{WP}_X\) with length exactly \(n\).

The coword problem of a group is the complement of the word problem, that is, \[ \mathrm{coWP}_X := X^*\setminus \mathrm{WP}_X. \] That is, \(\mathrm{coWP}_X\) is the set of words which do not evaluate to the group identity.

Open Questions

  • Is the coword problem for Grigorchuk's (or a similarly defined) context-free language?
  • Is the word problem for Grigorchuk's (or a similarly defined) group an Indexed language, as defined by Aho [1] ?
  • If a group has a coword problem that is context-free, then is that group a subgroup of Thompson's group V?
  • If a group has an algebraic cogrowth series, then is it virtually free?

References

  1. Alfred Aho (1968). "Indexed grammars—an extension of context-free grammars." Journal of the ACM. 15 (4): 647–671. DOI: 10.1145/321479.321488
  2. Alex Bishop. "Geodesic growth in virtually abelian groups." J. Algebra 573 (2021), 760–786. DOI: 10.1016/j.jalgebra.2020.12.003 [Additional link: arXiv:1908.07294]
  3. Alex Bishop and Murray Elder. "A virtually 2-step nilpotent group with polynomial geodesic growth." Algebra Discrete Math. 33 (2022), no. 2, 21–28. DOI: 10.12958/adm1667 [Additional link: arXiv:2007.06834]
  4. Martin Bridson, José Burillo, Murray Elder and Zoran Šunić. "On groups whose geodesic growth is polynomial." Internat. J. Algebra Comput. 22 (2012), no. 5, 1250048. DOI: 10.1142/S0218196712500488 [Additional link: arXiv:1009.5051]
  5. Julie Marie Brönnimann. "Geodesic growth of groups." Diss. Université de Neuchâtel, 2016.
  6. R. I. Grigorchuk. "Degrees of growth of finitely generated groups and the theory of invariant means." Izv. Akad. Nauk SSSR Ser. Mat., 48(5):939–985, 1984
  7. Mikhael Gromov. "Groups of polynomial growth and expanding maps." Inst. Hautes Études Sci. Publ. Math., 53:53–73, 1981
  8. John Milnor. "A note on curvature and fundamental group." In: J. Differential Geometry 2 (1968), pp. 1-7. issn: 0022-040X. http://projecteuclid.org/euclid.jdg/1214501132
  9. John Milnor. "Advanced Problems: 5603." In: The American Mathematical Monthly 75.6 (1968), pp. 685–686. issn: 00029890, 19300972. http://www.jstor.org/stable/2313822
  10. A. S. Švarc, "A volume invariant of coverings" (in Russian), Doklady Akademii Nauk SSSR, vol. 105, 1955, pp. 32–34.