Next semester I will be teaching an introductory course on geometric group theory and there is a basic question that I do not know the answer to. Let $G$ be a finitely generated group with finite symmetric generating set $S$ and let $\Gamma$ be the corresponding Cayley graph. For each $n \geq 1$, let $B_{n}$ be the closed ball of radius $n$ in $\Gamma$ about the unit element $e$ and let
$b_{n} = |B_{n}|$. Then it is known that $\lim b_{n}^{1/n}$ always exists. (For example, see de la Harpe's book.) My question is whether $\lim b_{n+1}/b_{n}$ always exists?
Cayley Graphs – Size of Balls Analysis
gr.group-theory
Related Solutions
I've managed to answer a few of the latter questions, and please look below for a solution in the finite-degree case.
Theorem. There is an uncountable graph $\Gamma$ that is not a Cayley graph in the set-theoretic universe $V$, but which is a Cayley graph in a larger set-theoretic universe, obtained by forcing.
Proof. Let $\Gamma$ be a directed graph that is a tree, such that all vertices have infinite in-out degree, but such that some of these degrees are countable and some uncountable. For example, perhaps all the in-degrees are countable and all out-degrees are uncountable. It is not difficult to construct such a graph. Clearly, $\Gamma$ cannot be a Cayley graph, since the degrees don't match. Denote the (current) set-theoretic universe by $V$, and perform forcing to a forcing extension $V[G]$ in which $\Gamma$ is countable. (It is a remarkable fact about forcing that any set at all can become countable in a forcing extension.) In the extension $V[G]$, the graph $\Gamma$ is the countable tree in which every vertex has countably infinite in-out degree. Thus, in the forcing extension, $\Gamma$ is the Cayley graph of the free group on countably many generators. $_\square$
Theorem. There is a graph $\Gamma$ which is not a Cayley graph, but every finite subgraph of $\Gamma$ is part of a Cayley graph. Indeed, every countable subgraph of $\Gamma$ is part of a Cayley graph. Every countable subgraph of $\Gamma$ can be extended to a larger countable subgraph of $\Gamma$ that is a Cayley graph.
Proof. The same graph $\Gamma$ as above works. Every countable subgraph of $\Gamma$ involves only countably many edges, and can be placed into a countable subgraph of $\Gamma$ that is the Cayley graph of the free group on countably many generators. $_\square$
The conclusion is that you cannot tell if an uncountable graph is a Cayley graph by looking only at the finite subgraphs, or indeed, by looking only at its countable subgraphs.
These observations show that in the uncountable case, one should just restrict the question at the outset to graphs satisfying the degree-matching condition.
Let me also give the fuller details for the finite-degree case, following the suggestion of François Dorais (and my tree-of-attempts argument).
Theorem. There is a finitistic condition on countable graphs $\Gamma$ that holds exactly of the finite-degree Cayley graphs. Specifically, the set of finite-degree countable Cayley graphs has complexity at most $\sum_4^0$ in the arithmetic hierarchy.
Proof. Let us suppose that the graph $\Gamma$ is given to us simply as a binary relation on $\omega$, that is, an element of $2^{\omega\times\omega}$. The assertion that the graph is connected has complexity $\prod_2^0$, since you must only say that every two vertices are connected by a finite path. The assertion that the graph has finite degree and all in-out degrees are the same has complexity $\sum_4^0$, since you can say "there is a natural number $k$ such that for all vertices $v$ there are $k$ vertices $w_1,\dotsc,w_k$ pointing at $v$, such that no other vertex points at $v$ (and similarly for pointing out).
Now, suppose that $\Gamma$ is a connected directed graph and all in-out degrees are $k$. Fix a node $e$ that will represent the group identity (if $\Gamma$ is a Cayley graph, any node will do since they all look the same, so take $e=0$). Let us refer to the $k$ nodes pointed at from $e$ as the set of generators (since if $\Gamma$ really is a Cayley graph, these will be the generators). Define that $p$ is a partial labeling of the edges of $\Gamma$ with generators, if $p$ is a function defined in a finite distance ball of $e$ in $\Gamma$, where $p$ labels each arrow in that ball with a generator. Such a labeling is coherent if first, for every node every generator is used once going out from that node and once going into that node, and second, if for every node $v$, if there is a loop starting and ending at $v$, then the word $w$ obtained from that loop works as a loop from every node to itself. We only enforce the requirements on coherence of $p$ as far as $p$ is defined (since it is merely a partial function). Thus, a coherent labeling is an attempt to make a labeling of the the graph into a Cayley graph, that has not run into trouble yet.
Let $T$ be the collection of finite coherent labelings, labeling all edges on the first $n$ nodes for some $n$. This is a finitely branching tree under inclusion.
I claim that $\Gamma$ is a Cayley graph if and only if there are arbitrarily such large coherent labelings. The forward direction is clear, since we may restrict a full coherent labeling to any finite subgraph. Conversely, if we can find a coherent labeling for any finite subgraph of $\Gamma$, then the tree $T$ is infinite and finitely branching. Thus, by Konig's lemma there is an infinite branch. Such a branch labels all the edges in $\Gamma$ and satisfies the coherence condition. Such a labeling exactly provides a group presentation with Cayley graph $\Gamma$.
The complexity of saying that every initial segment of the nodes admits a coherent labeling is $\prod_2^0$, since you must say for every $n$, there is a labeling $p$ of the first $n$ nodes such that $p$ is coherent. Being coherent is a $\Delta_0^0$ requirement on $p$. $_\square$
In particular, to recognize when a graph is a finitely generated Cayley graph does not require one to quantify over infinite objects, and so for finite degree graphs, this is an answer to the main question.
I was surprised that the part of the description driving the complexity is the assertion that the degrees must all match, rather than the assertion that there are coherent labelings on the finite subgraphs. Can this be simplified?
This still leaves the case of countably many generators wide open. Also, this still doesn't answer the question about having a computable graph $\Gamma$, which is a Cayley graph, but which has no computable presentation. Such an example would be very interesting. Even in the finite degree case, as I mentioned in the question, the best the argument above produces is a low branch.
I'm fairly sure [from personal communications] this question is (widely) open in general [and a negative answer would come as a surprise to many]. But the only groups I know of where it is known that $\lim \frac{b_{k+1}}{b_k}$ do not exist are the ones described here (as linked by Andreas Thom). Now, for these groups it is clear the answer is yes.
It turns out that, for the generating sets given there, these groups have "pinched" exponential growth. So as a consolation (or perhaps a tiny step of progress to answer the question) here is a partial answer for groups (and generating sets) that have pinched exponential growth.
Remark: for examples of such pairs and as well as groups where one generating set has pinched exponential growth while the other does not, see at the end of this answer.
Notation: Let $B(n)$ be the ball of radius $n$ and $b_n = |B(n)|$. Let $S(n) = B(n) \setminus B(n-1)$ (with $S(0) = \lbrace e_G \rbrace$) be the spheres and $s_n = |S(n)|$.
Definition: Say a pair $(G,S)$ (where $S$ is a finite generating set of the group $G$) has pinched exponential growth if there are constants $K<L \in\mathbb{R}$ and $M \in \mathbb{R}$ so that $K \mathrm{exp}(Mn) \leq b_n \leq L \mathrm{exp}(Mn)$.
Proposition: If $\mathrm{Cay}(G,S)$ has pinched exponential growth, then $\liminf \frac{b_{k+1}}{b_k} >1$.
Let $g = \lim_n b_n^{1/n} = \inf_n b_n^{1/n}$. Now, note there are infinitely many $n_i$ so that, for $n \leq n_i$, $s_{n_i} \geq s_n$ (otherwise $s_n$ is bounded and $b_n$ grows at most linearly). Clearly, $s_{n_i} \leq b_{n_i} \leq (n_i+1) s_{n_i}$, so $$ g = \liminf b_{n_i}^{1/n_i} \geq \liminf_i s_{n_i}^{1/n_i}. $$ But $b_n \leq \sum_{j=0}^n s_j$ so $$g = \liminf_i b_{n_i}^{1/n_i} \leq \liminf (n_i+1)^{1/n_i} s_{n_i}^{1/n_i} = \liminf |S(n_i)|^{1/n_i}. $$ Thus far we have $$g = \liminf |S(n_i)|^{1/n_i}.$$ However, $n \mapsto s_n$ is also sub-multiplicative, i.e. $s_{n+m} \leq s_n s_m$. Hence $$g = \lim_n s_n^{1/n} = \inf_n s_n^{1/n}.$$ The equality with the $\inf$ implies $s_n/g^n \geq 1$.
Next note that pinched exponential growth is equivalent to $\limsup b_n/g^n = L < \infty$ (for some $L$). Putting this together $$ \begin{array}{rll} \displaystyle \liminf \frac{s_{n+1}}{b_n} & \displaystyle = g \liminf \frac{s_{n+1}}{g^{n+1}} \cdot \frac{g^n}{b_n} \\ & \displaystyle \geq g \liminf \frac{s_{n+1}}{g^{n+1}} \bigg( \limsup \frac{b_n}{g^n} \bigg)^{-1} & \displaystyle \geq g /L \end{array} $$ This implies that $$ \frac{ |B(n+1)|}{|B(n)|} \geq 1 + \frac{g}{L} $$ as desired.
Three remarks on pinched exponential growth:
1- the property depends on the generating set. If $(G,S)$ has pinched exponential growth. Then $G \times \mathbb{Z}$ with "summed" generating set $\lbrace (s,0) \mid s \in S \rbrace \cup \lbrace (e_G,\pm 1) \rbrace$ has also pinched exponential growth. With the "product" generating set $\lbrace (s,\epsilon) \mid s \in S , \epsilon = \pm 1 \rbrace$ it does not have pinched growth. Also, $G \times G$ with the product generating set has pinched exponential growth, but with the summed generating set it does not.
2- with the "usual" generating sets, solvable Baumslag-Solitar and some lamplighters groups have pinched exponential growth (this can be seen on their growth series). For the growth series of $BS(1,n)$ see Collins, Edjvet and Gill, Growth series of the group $\langle x,y \mid x^{-1}y x=y^\ell \rangle$, Arch. Math. 62:1--11, 1994. For the growth series of lamplighters of the form $(\oplus_{i \in \mathbb{Z}} H) \rtimes \mathbb{Z}$) where the growth series of $H$ is known (i.e. $H$ is finite, or Abelian, or $BS(1,n)$, or a lamplighter or ...) see Johnson, Rational growth of wreath products, in "Groups St Andrews 1989" volume 2 309--315.
3- If the growth series is rational then having pinched exponential growth is the same as having exactly one root on the convergence radius. Groups with two roots on their convergence radius are known to exist, but I don't know if there is a group (with rational growth series and) 3 roots on the convergence radius.
Best Answer
In the article
R. Grigorchuk and P. De La Harpe, On problems related to growth, entropy, and spectrum in group theory, Journal of Dynamical and Control Systems, Volume 3, Number 1, 51-89
on the lower part of page 58 the authors mention the manuscript
A. Machi, Growth functions and growth matrices for finitely generated groups. Unpublished manuscript, Univ. di Roma La Sapienza, 1986.
and explain an example due to Machi. Machi showed that the convergence of $b_{n+1}/b_n$ can fail for one generating set of ${\mathbb Z}_2 \star {\mathbb Z}_3$ and hold for another. In particular, the limit does not always exist. The two generating sets are $\lbrace s,t\rbrace$ and $\lbrace s,st\rbrace$, where $s$ and $t$ are the natural generators with $s^2=t^3=e$.