The edge that is as big as the ball

How fast the ball fills counts the elements within $r$ steps of the identity and finds two behaviours: a polynomial in the lattice, a power of three in the free group. There is a second reading of the same counts, and it turns out to decide something the growth rate does not.

Ask not how large the ball is but what fraction of it lies on the outside.

The ratio, and what it is not #

For the integers the ball of radius $r$ has $2r+1$ elements and its outermost shell has two, so the share is $2/(2r+1)$ and goes to nothing. For the integers squared the ball has about $2r^2$ and the shell about $4r$, so the share is about $2/r$ and also goes to nothing. For the free group the ball has $2\cdot 3^r - 1$ and the shell has $4 \cdot 3^{r-1}$, so the share is very nearly $2/3$ — at every radius.

The ratio is not the growth rate and it is not determined by it. Both lattices have polynomial growth of different degrees and both ratios vanish; a group could in principle grow exponentially and still have sets with vanishing boundary ratio, and some do. What the ratio measures is whether the group has large sets that are almost all interior, and that is a separate question from how many elements are near the identity.

A group with such sets is called amenable, and the condition is usually stated for an arbitrary sequence of finite sets rather than for balls: there must be finite sets $F_k$ whose boundary — the elements of $F_k$ with a neighbour outside — is a vanishing fraction of $F_k$. Balls are the obvious candidate and they work for the lattices. For the free group nothing works, and that is a theorem rather than a failure of imagination.

The same measurement on the free group answers the other half, and the two panels together are the whole of the distinction — one set of balls whose edges become negligible, one whose edges do not.

Why a tree can be cut into two copies of itself #

Sort the elements of the free group on $a$ and $b$ by the first letter of their reduced word. Four classes, plus the identity.

Now take the class starting with $a^{-1}$ and multiply everything in it by $a$ on the left. A word $a^{-1}w$ becomes $w$, and $w$ can be anything that does not start with $a$ — including the empty word. So

$$\{\text{starts with } a\} \;\sqcup\; a \cdot \{\text{starts with } a^{-1}\} \;=\; \text{the whole group},$$

and the two pieces do not overlap, since the first consists of words starting with $a$ and the second of words that do not.

The same argument with $b$ gives a second such pair. So four of the pieces — $A$, $a^{-1}$-class, $B$, $b^{-1}$-class — reassemble, by two multiplications, into two copies of the whole group.

That is a paradoxical decomposition, and there is nothing suspect in it. No piece is measured, nothing is added, and the pieces are genuine subsets defined by a property anybody can check on a word. What makes it possible is that the group is infinite in a particular way: shifting by one letter moves a class onto a set much larger than itself, because in a tree there is always more room further out.

The ball of a tree, looked at #

The tree makes the arithmetic obvious in a way the ratio plot does not, and it is worth looking at once before the theorem.

Every element other than the identity has four neighbours: one closer to the identity and three further away. So each element of shell $k$ contributes three to shell $k+1$, the shells triple, and a geometric series with ratio three has its last term larger than the sum of all the earlier ones — $3^k > 1 + 3 + \cdots + 3^{k-1}$, with room to spare.

That inequality is the entire mechanism, and it is the one a lattice cannot supply. In the lattice each element has four neighbours too, and for most of them two are closer and two are further, so the shells grow linearly rather than geometrically and the last one is a vanishing share.

The word “branching” is the usual name for it and it is slightly misleading, because it suggests the tree matters. What matters is the ratio of successive shells: any group whose shells grow by a factor bounded away from one has a boundary that does not vanish, tree or not. The tree is where the factor is easiest to compute.

Where the two facts meet #

The connection between the ratio and the decomposition is a theorem and it is the reason both are on one page.

A group with a paradoxical decomposition has no sets with small boundary. Suppose the group splits into pieces $A_1, \ldots, A_m$ and $B_1, \ldots, B_n$ with $\bigsqcup g_i A_i = \bigsqcup h_j B_j = G$. Take a finite set $F$ with boundary a fraction $\varepsilon$ of it. Each $g_i F$ differs from $F$ by at most a bounded multiple of the boundary, so translating changes $F$ hardly at all — and the decomposition says the translates of the pieces cover the group twice over. Counting $F$’s elements two ways gives $|F| \approx 2|F|$ up to an error controlled by $\varepsilon$, which is impossible once $\varepsilon$ is small enough.

And a group without such sets has a paradoxical decomposition. That direction is Tarski’s theorem, from 1929, and it is much harder: the sets with small boundary are equivalent to the existence of an invariant finitely additive measure assigning the whole group measure one, and Tarski showed the failure of that is exactly the paradox. So the two conditions are not merely related; they are the same condition, and the ratio in the hero figure is the instrument.

There is a third form of the same equivalence, and it is the one that makes the theorem feel inevitable rather than clever. A paradoxical decomposition says the group can be doubled by rearranging; a thin-boundary sequence says the group has finite pieces that are almost translation-invariant. Those two cannot both hold, because an almost-invariant piece would be almost unchanged by the rearrangement and so would have to be both its own size and twice it.

The consequence is the one worth carrying. Whether a group can be cut up and reassembled into two copies of itself is decided by one ratio — the boundary of a large finite set against its size — and by nothing about the group’s size, its growth degree, or whether it is commutative. Commutativity implies the ratio vanishes, so no commutative group is paradoxical, and that is the whole reason the line’s pathology stops where it does.

Which is why three dimensions and not two #

A set that has no size at all records the fact and names the mechanism in one sentence: Banach and Tarski’s decomposition of a ball uses rotations of three-space, which contain a free subgroup on two generators, and “in one and two dimensions no such decomposition exists, precisely because the relevant groups are too commutative to contain a free subgroup.”

This essay is what makes that sentence a reason rather than a claim.

The rigid motions of the plane have a commutative subgroup of translations with the rotations acting on it, and such a group has balls with vanishing boundary ratio — so it is amenable, so no paradoxical decomposition of the plane exists by rigid motions, and the plane’s pathologies stop at the non-measurable set that a Vitali construction produces.

The rotations of three-space are different. Two rotations about different axes through irrational angles generate a free group on two generators — Hausdorff showed it in 1914 — and the free group is not amenable, by the count above. So the sphere inherits the decomposition: transfer the four pieces along the group’s orbits, patch the fixed points, and a ball becomes two balls.

So the dimension is not where the difficulty lies. It is where the free group first appears, and the free group first appears because three-dimensional rotations do not commute in a way two-dimensional ones do. A count of elements in a tree, and a ball comes apart.

What an invariant measure would have to do #

The equivalence in the section above was stated in terms of a finitely additive invariant measure, and it is worth saying what such a thing is, because the phrase carries the whole argument and is easy to read past.

An invariant finitely additive measure on a group $G$ assigns to every subset $A$ a number $\mu(A)$ between nought and one, with $\mu(G) = 1$, with $\mu(A \sqcup B) = \mu(A) + \mu(B)$ for disjoint sets, and with $\mu(gA) = \mu(A)$ for every group element $g$. It is finitely additive, so no limits are involved and no pathologies of the Vitali kind arise; and it is defined on every subset, which is what makes it strong.

Now a paradoxical decomposition is exactly what such a measure forbids. If $G = \bigsqcup g_i A_i = \bigsqcup h_j B_j$ with the $A_i$ and $B_j$ together partitioning $G$, then adding up gives

$$1 = \sum \mu(g_i A_i) = \sum \mu(A_i), \qquad 1 = \sum \mu(B_j),$$

so $\sum \mu(A_i) + \sum \mu(B_j) = 2$ — and that sum is $\mu(G) = 1$, since the pieces partition the group. One equals two, so no such measure exists.

The content of Tarski’s theorem is the converse, and it is the hard direction: if no paradoxical decomposition exists then the measure does. The construction of the measure from the boundary condition is a limit of averages over the sets whose edges are thin, taken in a space large enough to have a convergent subsequence — which is where the axiom of choice enters this side of the subject, quietly, exactly as it enters the other side loudly.

What the ratio does not decide #

It does not follow from the growth type. There are amenable groups of exponential growth — the group of symmetries of the integers generated by translation and doubling is one — so vanishing boundary ratio does not imply the ball grows slowly. The implication runs the other way: subexponential growth forces amenability, because a group whose balls grow subexponentially has infinitely many radii at which one ball is barely larger than the last, and those balls have small boundary.

It does not decide whether a group contains a free subgroup. For a long time the two were thought equivalent — the von Neumann problem asked whether every non-amenable group contains a free group on two generators — and Ol’shanskii produced a counterexample in 1980. So non-amenability is a statement about boundaries and not a statement about containing a tree, even though the tree is where it was first seen.

And it does not decide the measure-theoretic question directly. Amenability gives an invariant finitely additive measure on all subsets. What Solovay’s model is about is countably additive measure, and the two are different properties: the line has an invariant finitely additive measure on every subset and does not have a countably additive one, which is why Vitali’s construction works on the line and Banach–Tarski’s does not.

What the pictures cannot show #

Every measurement here is at radius eight or less, and the condition is about a limit. A ratio falling from one to a fifth over eight radii is evidence that it goes to nothing; a ratio sitting at two thirds over eight radii is evidence that it does not. Neither is a proof, and both are what a count can supply.

The condition as stated quantifies over all finite sets, not over balls. The figures test balls, which suffices for one direction — if the balls work, the group is amenable — and not for the other, since a group whose balls have large boundary might have some other sequence that works. For the free group the impossibility is the theorem quoted above and not something the figures establish.

And the paradoxical decomposition is checked on words up to five letters. The accounting — every shorter word in exactly one of two pieces — is verified word by word over all 485 of them, and the claim is about infinitely many. The verification is the mechanism and the mechanism is what generalises, which is the standing shape of the argument in this collection.

Still open: which groups, and how thin the boundary can be #

Amenability is decidable for the groups anybody first meets and is hard in general. Whether a group given by a finite presentation is amenable is not algorithmically decidable, and there are groups whose amenability was open for decades — the Grigorchuk group is amenable, which was proved by a growth argument, and finding a non-amenable group with no free subgroup took until 1980.

The quantitative question is more open. For an amenable group one can ask how large a set has to be before its boundary is a small fraction — the Følner function — and its growth is a genuine invariant, computed for very few groups. For the lattice it is polynomial; for the group of symmetries generated by translation and doubling it is much larger; and a characterisation of which functions occur is not available.

There is a third direction with a clean statement. Every amenable group has an invariant finitely additive measure, and how many such measures it has is a question about the group: the integers have a great many, and the possible structures of that space are understood in few cases.

The averaging reading, which is where the name comes from #

The word amenable is von Neumann’s and it was chosen for a property that sounds unrelated to boundaries: a group is amenable when there is a consistent way to take the average of a bounded function on it.

Suppose a function assigns a number between nought and one to every element of the group, and an average is wanted — a single number, respecting the obvious properties: the average of a constant is that constant, averaging is linear, and shifting the function along the group leaves its average alone. For a finite group the average is the sum over the size. For an infinite one there is no such formula, and whether a substitute exists is the question.

For the integers there is one, and the Følner sets construct it: average over $\{-k, \ldots, k\}$ and take a limit along a suitable subsequence. Shifting the function by one changes the average over the window by two terms out of $2k+1$, which vanishes — and that vanishing is exactly the boundary ratio. So the averaging property and the thin-boundary property are two descriptions of one thing, and the Følner condition is the second written down.

For the free group no average exists, and the paradoxical decomposition is why: the indicator function of a piece would have to have an average that is both a third and a half of the whole, depending on which reassembly is used.

The averaging reading is the one that made the concept useful outside group theory, since a group acting on anything with an invariant average inherits strong properties — and it is also the reason the concept has a dozen equivalent definitions, each natural in a different subject and none obviously the same as the others.

What one ratio was worth #

The growth rate counts how much of a group is near the identity and the boundary ratio asks how much of a large piece is on its edge. The second is the coarser-looking question and it is the one that decides a theorem about balls in space.

The chain is short and every link is elementary. Most of a tree is its leaves; a set whose edge is a fixed share of it can be shifted onto something much larger; so the free group splits into four pieces making two copies; so any space the free group acts on freely splits the same way; and the rotations of three-space contain a free group — whose Cayley graph is the tree the growth count walked.

What the chain does not contain is anything about volume, and that is the point the set with no size makes from the other end. The decomposition is a fact about a group, established by counting words. The impossibility of measuring the pieces is a consequence rather than an ingredient — and the reason the same construction fails in the plane is that the plane’s group of motions has balls whose edges are thin.