# Which groups are doubling?

A metric space $$(M,d)$$ is doubling if there exists $$n$$ such that every ball of radius $$r$$ can be covered by $$n$$ balls of radius $$r/2$$, for all $$r$$. For which f.g. groups $$G$$ and finite symmetric generating sets $$S$$, is $$\mathrm{Cay}(G, S)$$ doubling under the path metric? Groups like this have polynomial growth, so they are virtually nilpotent by Gromov's theorem.

So which virtually nilpotent groups are doubling, and for which generating sets? All, I suppose, but I got cold feet trying to do it, it seemed quite difficult straight from the definitions and I don't really know the Lie group stuff well enough.

If $$S$$ is a finite symmetric generating set for a group $$G$$, is $$\mathrm{Cay}(G, S)$$ doubling precisely when $$G$$ is virtually nilpotent?

I'll note that in general (undirected) graphs, doubling implies polynomial growth, but not the other way around, consider for example the comb graph with vertices $$\mathbb{Z} \times \mathbb{N}$$ and edges $$\{\{(m,n), (m,n+1)\}, \{(m,0), (m+1,0)\} \;|\; m \in \mathbb{Z}, n \in \mathbb{N}\}$$. But could be true for vertex-transitive graphs.

• To be doubling is a QI invariant, so this doesn't depend on a generating subset. F.g. virtually nilpotent groups are doubling. More generally, simply connected nilpotent Lie groups are doubling, this follows from Gromov and Pansu's work. I'll post an answer.
– YCor
Oct 28, 2020 at 13:21
• @YCor In the first sentence: do you mean "... if there exists $n$ such that ..., for all $r$" ? Oct 28, 2020 at 14:32
• Yes I did, thanks. Oct 28, 2020 at 14:36
• @MartinSeysen yes: $\exists n \forall r\forall x \exists F$: $|F|\le n$ and $B(x,r)\subset B(F,r/2)$. (You '@' this sentence to me but refer to OP's post)
– YCor
Oct 28, 2020 at 14:44

I think this follows from a standard ball-packing argument.

Suppose that $$G$$ with the metric $$\rho$$ induced from the Cayley graph has growth $$V(R)=|B_R(1)| \sim R^d$$, i.e. $$\exists\ 0 such that $$cR^d\leq V(R)\leq CR^d$$, where $$B_R(1)$$ is the open ball of radius $$R$$ about the identity (indeed, this argument works for any metric-measure space with polynomial growth of balls about every point in this sense). This holds for finitely generated nilpotent groups by a result of Bass.

Then take a maximal $$R/2$$-packing $$N_R$$ of $$B_R(1)$$, i.e. $$N_R\subset B_R(1)$$ where $$\rho(g_1,g_2)\geq R/2$$ for $$g_1,g_2\in N_R, g_1\neq g_2$$. Then $$B_{R/4}(g_1)\cap B_{R/4}(g_2) =\emptyset$$.

By maximality, $$B_R(1)\subseteq \cup_{g\in N_R} B_{R/2}(g)$$: if not, then we could find another point $$h\in B_R(1)$$ whose distance $$\rho(h,N_R)$$ is at least $$R/2$$, so $$N_R\cup \{h\}$$ is an $$R/2$$-packing, a contradiction to maximality of $$N_R$$. Thus $$N_R$$ is an $$R/2$$-net of $$B_R(1)$$.

Moreover, the union of the balls of radius $$R/4$$ about points of $$N_R$$ lies in $$B_{5R/4}(1)$$. Hence $$|N_R|V(R/4) \leq V(5 R/4)$$. So we have $$|N_R| \leq \frac{V(5R/4)}{V(R/4)} \leq \frac{C (5R/4)^d}{c(R/4)^d} =C/c5^d$$. Hence the space is doubling.

• So it seems this is true for all polynomial-growth graphs, as soon as the growth has a well-defined degree. My comb has degree 2 near the spine, and degree 1 in the teeth. Amazing (or possibly typical) that I missed that, I already proved some equivalent conditions using this same packing argument. Oct 29, 2020 at 6:55
• You use $d$ for two different things; and for posterity maybe it would be worth generalizing this to the statement that if growth is sufficiently regular in an arbitrary graph then polynomial growth = doubling? Oct 29, 2020 at 6:58
• @VilleSalo "has a well-defined degree" has several possible senses, one of which being: "$\log(|B(x_0,r)|)/\log(r)$ converges", a stronger one being that for some real $d$. $|B(x_0,r)|/r^d$ has liminf $>0$ and limsup $<0$, and an even stronger one being the same plus requiring that $d$ is an integer.
– YCor
Oct 29, 2020 at 8:13
• Sure, I was just summarizing how this fits in with my example. I think your second definition is what is needed for this proof; it's what's explictly used, and I'm guessing there's a counterexample if we use your first definition. Oct 29, 2020 at 8:17
• @IanAgol the exact growth is not classified, but a lot is known. It was proved around 70 that there's an explicit computable degree of polynomial growth $D$ (with liminf and limsup of $V(n)/n^D$ positive finite), then by Pansu around 1980 that $V_S(n)/n^D$ converges for every choice of finite generating subset, and a little is known about the second asymptotic term (e.g., work of Breuillard and Le Donne), also covering metrics with some asymptotic condition that's more general than word metrics (e.g., for $\mathbf{Z}^d$ it's natural to allow restrictions of Banach norms on $\mathbf{R}^d$).
– YCor
Oct 29, 2020 at 17:28

Yes: a f.g. discrete, and more generally compactly generated locally compact group is doubling iff it has polynomial growth.

For f.g. groups, you mentioned $$\Rightarrow$$, and asked $$\Leftarrow$$, which I justify below.

Define $$X$$ to be large-scale doubling if for some $$R_0,M_0$$, every ball of radius $$R\ge R_0$$ is finite union of $$M_0$$ balls of radius $$R/2$$.

To be large-scale doubling is a QI-invariant. For a metric space in which balls of given radius have bounded cardinal, it's obviously equivalent to doubling.

So for a f.g. group, being doubling doesn't depend on a choice of finite generating subset. Since every f.g. nilpotent group is QI to some simply connected nilpotent Lie group (Malcev), it is enough to check that every simply connected nilpotent Lie group $$G$$ is large-scale doubling. (More generally every compactly generated locally compact group of at most polynomial growth is QI to such a $$G$$.)

Indeed Pansu proved in 1983 that every asymptotic cone of such a Lie group $$G$$ is homeomorphic to $$G$$ and is a proper metric space. This implies that $$G$$ is large-scale doubling, by the following fact:

If a space $$X$$ is not large-scale doubling, then there exists a sequence of points $$(x_n)$$, and radii $$r_n\to\infty$$ and $$M_n\to\infty$$ such that the $$2r_n$$-ball around $$x_n$$ contains $$M_n$$ points at distance $$\ge r_n$$. It easily follows that the ultralimit of rescaled metric spaces $$(X,x_n,\frac{1}{r_n}d)$$, which has a natural basepoint $$o$$ has infinitely many points in the $$2$$-ball around $$o$$ at pairwise distance $$\ge 1$$, so is not a proper metric space.

• Prevents $G$ from not being large-scale doubling, I suppose. I think I saw this statement of Pansu in the literature (or some restatement of it), but I didn't connect the dots. I only know the theorem of Malcev from your MO posts, and haven't located it, i suppose I should do that. Oct 28, 2020 at 13:40
• Also, thanks a bunch. I did expect you'd give some answer involving the asymptotic cone, but I didn't expect to actually understand it. (To clarify: I think I did.) Oct 28, 2020 at 13:45
• For the purposes of OP's question it seems to be much easier to prove the doubling property of simply connected Lie group directly - by using the explicit polynomial form of multiplication in these groups
– R W
Oct 28, 2020 at 15:33
• @RW I'd be happy to understand and upvote an answer along these lines.
– YCor
Oct 28, 2020 at 15:44