You are currently browsing the tag archive for the ‘ping-pong lemma’ tag.

Notational convention: In this post only, I will colour a statement red if it assumes the axiom of choice. (For the rest of the course, the axiom of choice will be implicitly assumed throughout.) $\diamond$

The famous Banach-Tarski paradox asserts that one can take the unit ball in three dimensions, divide it up into finitely many pieces, and then translate and rotate each piece so that their union is now two disjoint unit balls.  As a consequence of this paradox, it is not possible to create a finitely additive measure on ${\Bbb R}^3$ that is both translation and rotation invariant, which can measure every subset of ${\Bbb R}^3$, and which gives the unit ball a non-zero measure. This paradox helps explain why Lebesgue measure (which is countably additive and both translation and rotation invariant, and gives the unit ball a non-zero measure) cannot measure every set, instead being restricted to measuring sets that are Lebesgue measurable.

On the other hand, it is not possible to replicate the Banach-Tarski paradox in one or two dimensions; the unit interval in ${\Bbb R}$ or unit disk in ${\Bbb R}^2$ cannot be rearranged into two unit intervals or two unit disks using only finitely many pieces, translations, and rotations, and indeed there do exist non-trivial finitely additive measures on these spaces. However, it is possible to obtain a Banach-Tarski type paradox in one or two dimensions using countably many such pieces; this rules out the possibility of extending Lebesgue measure to a countably additive translation invariant measure on all subsets of ${\Bbb R}$ (or any higher-dimensional space).

In these notes I would like to establish all of the above results, and tie them in with some important concepts and tools in modern group theory, most notably amenability and the ping-pong lemma.  This material is not required for the rest of the course, but nevertheless has some independent interest.

Additive combinatorics is largely focused on the additive properties of finite subsets A of an additive group $G = (G,+)$.  This group can be finite or infinite, but there is a very convenient trick, the Ruzsa projection trick, which allows one to reduce the latter case to the former.  For instance, consider the set $A = \{1,\ldots,N\}$ inside the integers ${\Bbb Z}$.  The integers of course form an infinite group, but if we are only interested in sums of at most two elements of A at a time, we can embed A ininside the finite cyclic group ${\Bbb Z}/2N{\Bbb Z}$ without losing any combinatorial information.  More precisely, there is a Freiman isomorphism of order 2 between the set $\{1,\ldots,N\}$ in ${\Bbb Z}$ and the set $\{1,\ldots,N\}$ in ${\Bbb Z}/2N{\Bbb Z}$.  One can view the latter version of $\{1,\ldots,N\}$ as a model for the former version of $\{1,\ldots,N\}$. More generally, it turns out that any finite set A in an additive group can be modeled in the above set by an equivalent set in a finite group, and in fact one can ensure that this ambient modeling group is not much larger than A itself if A has some additive structure; see this paper of Ruzsa (or Lemma 5.26 of my book with Van Vu) for a precise statement.  This projection trick has a number of important uses in additive combinatorics, most notably in Ruzsa’s simplified proof of Freiman’s theorem.

Given the interest in non-commutative analogues of Freiman’s theorem, it is natural to ask whether one can similarly model finite sets A in multiplicative (and non-commutative) groups $G = (G,\times)$ using finite models.  Unfortunately (as I learned recently from Akshay Venkatesh, via Ben Green), this turns out to be impossible in general, due to an old example of Higman.  More precisely, Higman shows:

Theorem 1. There exists an infinite group G generated by four distinct elements a,b,c,d that obey the relations

$ab = ba^2; bc = cb^2; cd = dc^2; da = ad^2$; (1)

in fact, a and c generate the free group in G.  On the other hand, if G’ is a finite group containing four elements a,b,c,d obeying (1), then a,b,c,d are all trivial.

As a consequence, the finite set $A := \{ 1, a, b, c, d, ab, bc, cd, da \}$ in G has no model (in the sense of Freiman isomorphisms) in a finite group.

Theorem 1 is proven by a small amount of elementary group theory and number theory, and it was neat enough that I thought I would reproduce it here.