Spectral radius of a finitely generated group

Question

Let $G$ be a finitely generated group and $\Gamma$ be its Cayley graph with the usual word metric. Let $\mu$ be a symmetric non-degenerate measure on $G$ (maybe with finite support or smooth), and define $p(x, y) = \mu(x^{-1} y)$. As is well-known, $p$ generates a random walk on $\Gamma$ with transition probability $p(x, y)$. Now, define the quantity $\displaystyle\rho := \limsup_{n} p_n(x, y)^{1/n}$, where $p_n(x, y)$ is the probability of hitting $y$ starting from $x$ at time $n$ (recall that $p_n$ can also be obtained from the $n$-fold convolution $\mu^{(n)}$).

It it a well-known result that $G$ is amenable if and only if $\rho = 1$. A priori, though the definition of $\rho$ seems to depend on the measure $\mu$, the above result seems to suggest that it is a purely metric concept (since amenability is a variant of nice isoperimetric behavior and is a purely metric construct), and does not depend on the specific non-degenerate measure under consideration.

My question is, is the last statement correct? And if yes, can it be seen directly, or does it follow after the fact?

Further comment: I originally asked on MSE, but there is no answer there, so I am cross-posting here.

Answer 1

There is not much difference between the characterizations of amenability in terms of the spectral radius (Kesten's condition) and in isoperimetric terms (Følner's condition). In both cases the group is endowed with an additional structure, and in both cases the criterion does not depend on the choice of this structure. There is nothing extraordinary in this situation at all: for instance no one should be surprised that a smooth manifold can be endowed with a Riemannian structure, and that certain properties formulated in terms of this additional structure do not depend on its choice.

Returning to amenability, in the first case this additional structure is provided by a symmetric probability measure $\mu$ whose support generates the group and by the associated Markov operator $P_\mu$ (the so-called ``smoothness'' of $\mu$ with its completely inappropriate name has nothing to do here), and in the second case an additional structure is provided by a generating set $K$ used to define the boundary $\partial_K$. The conditions themselves are also very similar as both amount to the existence of almost invariant objects relative to the respective structures. For Kesten's criterion this is (for arbitrarily small $\epsilon>0$) $$ \exists\, f \in \ell^2(G) : \| f - P_\mu f \|_2 < \epsilon \|f\|_2 \;, $$ and for Følner's criterion this is $$ \exists\, A\subset G: |\partial_K A | < \epsilon |A| \;. $$

This similarity is not just formal as there are pretty standard tricks which allow one to pass from sets to the corresponding indicator functions (as elements of $\ell^1(G)$), and to link the existence of almost $P_\mu$-invariant functions in $\ell^1$ and in $\ell^2$, which provides a conceptual reason for the equivalence of these two conditions.

Answer 2

The questions in the OP are

• "is this statement correct?" to which the answer is yes. But the tone is somewhat misleading: the isoperimetric conditon (sometimes called "Følner's criterion") is as arbitrary as the measure, because it depends on the graph structure, which depends on the generating set. There is a way to formulate Følner's condition without a generating set, but you would not call it isoperimetry (more on that at the end).

• "can it be seen directly, or does it follow after the fact?" The answer to that question depends a lot on what you consider to be easy tricks. Below I sketch a way to reframe both conditions so that they look close to each other. They are both statements about the closedness of the gradient operator; and the definition of that operator is dependent on the generating set, or the measure (which is a "generating set with weights").

• one might also interpret your question as "can it be seen directly that $\rho=1$ does not depend on the measure?". To which the answer is again "it depends". Roughly, you need to notice that (a) a "lazy" variant of $\mu$ has $\rho=1$ exactly when $\mu$ does (b) $\mu^{(n)}$ also has $\rho = 1$ exactly when $\mu$ does (c) $\rho = 1$ has to do with there being almost constant functions (d) given $\mu$ and $\mu'$, there is a $n$ and a $t$ so that if a function is almost constant for $\mu^{(n)}$, then it is almost constant for $tI + (1-t) \mu'$ (the $t$-lazy version of $\mu'$).

Below is the reformulation of each condition ("isoperimetry" and "spectral radius").

The isoperimetric condition (sometime called Følner's criterion) can be stated as follows. Pick a finite symmetric generating set $S$ of the group $\Gamma$ and consider the Cayley graph associated to it. Then $\Gamma$ is amenable if and only if $$ (F) \qquad \text{there is a sequence } F_n \text{ of finite sets so that } \dfrac{|\partial F_n|}{|F_n|} \to 0 $$ (where $\partial F_n$ denotes the boundary of $F_n$). There are [at least] three definitions of "boundary", but it is not so important which one you pick; they give sets whose cardinalities are bounded above and below up to the constant $|S|$. For my purpose here, $\partial F_n$ is the number of edges between $F_n$ and its complement $F_n^{\mathsf{c}}$.

This is useful because $|\partial F_n|$ is then just the norm of the gradient of $1_{F_n}$: $\|\nabla 1_{F_n}\|_{\ell^1}$. To expand on the terminology: $\nabla$ is the operator which to a function $f$ on the vertices associates the function $\nabla f$ on the edges defined by $\nabla f (x,y) = f(y) - f(x)$. Følner's condition then becomes: $$ (F') \qquad \text{there is a sequence of functions } f_n \in \ell^1 \text{ so that } \dfrac{\| \nabla f_n \|_{\ell^1} }{\|f_n\|_{\ell^1}} \to 0. $$ It is easy to check that $(F) \implies (F')$ (just take a characteristic function of the $F_n$). The converse is a bit technical, but boils down to writing a function $f$ as a sum of characteristic functions and then argue by contradiction (if none of these characteristic function do the trick, then $f$ won't). This is often referred to as "slicing argument".

Now let me reframe the condition in terms of the spectral radius (Kesten's criterion). The random walk $\mu$ also acts on functions (namely by convolution): $R_\mu f (x)= \sum_{s \in \mathrm{Supp}\, \mu} f(xs) \mu(s)$. Now it turns out that $$ \rho = \| R_\mu^{n} \delta_x\|_{\ell^2}^{1/n} = \|R_\mu\|_{\ell^2 \to \ell^2} $$ It is technical to check that this is your $\rho$, but fairly standard if you dealt with self-adjoint operators before. This means that Kesten's criterion is $$ (K) \qquad \|R_\mu\|_{\ell^2 \to \ell^2} = 1 $$ But if this is the case, then there is a sequence $f_n$ with $\|f_n\|_{\ell^2} = 1$ and $\langle f_n \mid R_\mu f_n \rangle \to 1$. In particular, $$ \begin{array}{rl} &\|f_n\|_{\ell^2}^2 - \langle f_n \mid R_\mu f_n \rangle \to 0\\ \implies & \langle f_n \mid f_n \rangle - \langle f_n \mid R_\mu f_n \rangle \to 0\\ \implies & \langle f_n \mid (I-R_\mu) f_n \rangle \to 0\\ \end{array} $$ But $I-R_\mu$ is a Laplacian, and Laplacian can be written as $\nabla^* \nabla$ (where $\nabla$ is a gradient on the generating set $S = \mathrm{Supp} \, \mu$ and $\nabla^*$ is its adjoint; see this post for more details on this). So we have a $f_n$ with $\|f_n\|_{\ell^2} = 1$ and $ \langle f_n \mid \nabla^* \nabla f_n \rangle = \|\nabla f_n\|_{\ell^2}^2 \to 0$ and thus we get the reformulation: $$ (K') \qquad \text{there is a sequence of functions } f_n \in \ell^2 \text{ so that } \dfrac{\| \nabla f_n \|_{\ell^2} }{\|f_n\|_{\ell^2}} \to 0. $$ At this point $(K')$ and $(F')$ are just the same condition with a different $\ell^p$ space. Of course, it could have happened that these two conditions are not equivalent (and again, there are more technicalities in showing this equivalence).

So once you've gone so far the conditions boil down to: is $\nabla$ a closed operator from $\ell^p \to \ell^p$? And the answer is, it never depends on $p$ (as long as $p < \infty$).

As a side note, there is another condition which does not depend on any choice of generating set (and is also sometimes called Følner's criterion). This says that $$ (F_0) \qquad \text{there is a sequence } F_n \text{ of finite sets so that } \forall \gamma \in \Gamma, \dfrac{|\gamma F_n \setminus F_n|}{|F_n|} \to 0 $$ It's a standard exercise to check the equivalence of this and condition $(F)$ (when the group is finitely generated!).

Answer 3

I'm not sure it answers your questions but there are indeed metric interpretations of the spectral radius. Given an action of a group $G$ on a metric space $(X,d)$, you can define the Poincaré series $\mathcal{P}(s)$ as $$\mathcal{P}(s)=\sum_{g\in G}\mathrm{e}^{-sd(x_0,g\cdot x_0)},$$ where $x_0\in X$ is a fixed base point. The critical exponent is the number $\delta$ such that for $s<\delta$, $\mathcal{P}(s)$ is infinite and for $s>\delta$, it is finite.

The Green distance associated with a random walk on a group $G$ is given by $$d_G(g,h)-\log\bigg(\mathbb{P}\big(\exists n, gX_n=h\big)\bigg)=-\log\frac{G(g,h)}{G(e,e)},$$ where $G$ is the Green function associated with the random walk. It was introduced by Blachere and Brofferio in here. Define then the symmetrized $r$-Green distance as $$d_{r}(g,h)=-\log \frac{G(g,h|r)}{G(e,e|r)} - \log \frac{G(h,g|r)}{G(e,e|r)}.$$ Here, $G(g,h|r)$ is the $r$-Green function defined by $$G(g,h|r)=\sum_{n\geq 0}r^np_n(x,y).$$ Of course, when the random walk is symmetric, the symmetrized Green distance is twice the usual Green distance.

Define the Poincaré series associated with $d_r$ by $$\mathcal{P}_p(r)=\sum_{g\in G}G(g,h|r)G(h,g|r)=\sum_{g\in G}\mathrm{e}^{-d_r(g,h)}.$$ The only difference with usual Poincaré series is that the parameter $r$ is inside the definition of the distance. As explained in Section 3.3 of this paper, the logarithm of the spectral radius can be interpreted as the critical exponent of the Poicanré series associated with the $r$-symmetrized Green distance.

In various hyperbolic contexts (see 3, 4, 5) for instance), the critical exponent coincides with the growth rate of the distance. Hence, in some sense, the logarithm of the spectral radius can be thought as a growth rate-like quantity for the symmetrized Green distance.

Now, to answer your specific question, as pointed out in the comments, the exact value of the spectral radius is difficult to compute and depends very much on the measure driving the random walk. However, as you state, the fact that the value is 1 is independent of this measure : it only depends on whether the group is amenable or not.

But actually, the exact same thing happens for the usual growth rate of the word metric. Its exact value depends on the generating set you choose, but the fact that it is 1 does not depend on it.