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.

– No non-trivial finite models –

Let’s first show the second part of Theorem 1.  The key point is that in a finite group G’, all elements have finite order, thanks to Lagrange’s theorem.  From (1) we have

b^{-1}ab = a^2

and hence by induction

b^{-n}ab^n = a^{2^n} (2)

for any positive n.  One consequence of (2) is that if b^n=1, then a = a^{2^n}, and thus a^{2^n-1} = 1.  Applying this with n equal to the order \hbox{ord}(b) of b, we conclude that

\hbox{ord}(a) | 2^{\hbox{ord}(b)}-1.

As a consequence, if \hbox{ord}(a) is divisible by some prime p, then 2^{\hbox{ord}(b)}-1 is divisible by p, which forces p to be odd and \hbox{ord}(b) to be divisible by the multiplicative order of 2 modulo p.  This is at most p-1 (by Fermat’s little theorem), and so \hbox{ord}(b) is divisible by a prime strictly smaller than the prime dividing \hbox{ord}(a).  But we can cyclically permute this argument and conclude that \hbox{ord}(c) is divisible by an even smaller prime than the prime dividing \hbox{ord}(b), and so forth, creating an infinite descent, which is absurd.  Thus none of \hbox{ord}(a), \hbox{ord}(b), \hbox{ord}(c), \hbox{ord}(d) can be divisible by any prime, and so a,b,c,d are trivial as claimed.

Remark 1. There is nothing special here about using four generators; the above arguments work with any number of generators (adapting (1) appropriately).  But we will need four generators in order to establish the infinite model below. \diamond

Remark 2. The above argument also shows that the group G has no non-trivial finite-dimensional linear representation.  Indeed, let a, b, c, d be matrices obeying (1), then b is conjugate to b^2 = c^{-1} b c, which by the spectral theorem forces the eigenvalues of b to be roots of unity, which implies in particular that b^n grows at most polynomially in n; similarly for a^n.  Applying (2) we see that a^{2^n} grows at most polynomially in n, which by the Jordan normal form for a implies that a is diagonalisable; since its eigenvalues are roots of unity, it thus has finite order.  Similarly for b,c,d.  Now apply the previous argument to conclude that a,b,c,d are trivial. \diamond

– Existence of an infinite model –

To build the infinite group G that obeys the relations (1), we need the notion of an amalgamated free product of groups.

Recall that the free product G_1 * G_2 of two groups G_1 and G_2 can be defined (up to group isomorphism) in one of three equivalent ways:

  1. (Relations-based definition) G_1 * G_2 is the group generated by the disjoint union G_1 \uplus G_2 of G_1 and G_2, with no further relations between these elements beyond those already present in G_1 and G_2 separately.
  2. (Category-theoretic definition) G_1 * G_2 is a group with homomorphisms from G_1 and G_2 into G_1 * G_2, which is universal in the sense that any other group G’ with homomorphisms from G_1, G_2 will have these homomorphisms factor uniquely through G_1 * G_2.
  3. (Word-based definition) G_1 * G_2 is the collection of all words g_1 g_2 \ldots g_n, where each g_i lies in either G_1 or G_2, with no two adjacent g_i, g_{i+1} lying in the same G_j (let’s label G_1, G_2 here to be disjoint to avoid notational confusion), with the obvious group operations.

It is not hard to see that all three definitions are equivalent, and that the free product exists and is unique up to group isomorphism.

Example 1. The free product of the free cyclic group \langle a \rangle with one generator a, and the free cyclic group \langle b \rangle with one generator b, is the free (non-abelian) group \langle a, b \rangle on two generators. \diamond

We will need a “relative” generalisation of the free product concept, in which the groups G_1, G_2 are not totally disjoint, but instead share a common subgroup H (or if one wants to proceed more category-theoretically, with a group H that embeds into both G_1 and G_2).  In this situation, we define the amalgamated free product G_1 *_H G_2 by one of the following two equivalent definitions:

  1. (Relations-based definition) G_1 * _H G_2 is the group generated by the relative disjoint union G_1 \uplus_H G_2 of G_1 and G_2 (which is the same as the disjoint union but with the common subgroup H identified), with no further relations between these elements beyond those already present in G_1 and G_2 separately.
  2. (Category-theoretic definition) G_1 *_H G_2 is a group with homomorphisms from G_1 and G_2 into G_1 *_H G_2 that agree on H, which is universal in the sense that any other group G’ with homomorphisms from G_1, G_2 that agree on H will have these homomorphisms factor uniquely through G_1 *_H G_2.

Example 2. Let G_1 := \langle a, b | ab = ba^2 \rangle be the group generated by two elements a, b with one relation ab = ba^2.  It is not hard to see that all elements of G_1 can be expressed uniquely as b^n a^m for some integers n, m, and in particular that H := \langle b \rangle is a free cyclic group.  Let G_2 := \langle b, c | bc = cb^2 \rangle be the group generated by two elements b, c with one relation bc = cb^2, then again H := \langle b \rangle is a free cyclic group, and isomorphic to the previous copy of H.  The amalgamated free product G_1 *_H G_2 = \langle a, b, c | ab=ba^2, bc = cb^2 \rangle is then generated by three elements a, b, c with two relations ab = ba^2, bc = cb^2. \diamond

It is not hard to see that the above two definitions are equivalent, and that G_1 *_H G_2 exists and is unique up to group isomorphism.  But note that I did not give the word-based definition of the amalgamated free product yet.  We will need to do so now; I will use the arguments from this 1954 paper of Neumann (who I briefly overlapped with, actually, at ANU), though the basic result I need here (namely, Corollary 1) dates all the way back to the work of Schreier in 1927.

In order to analyse these groups, we will need to study how they act on various spaces.  If G is a group, we define a G-space to be a set X together with an action (g, x) \mapsto gx of G on X (or equivalently, a homomorphism from G to the permutation group \hbox{Sym}(X) of X).  Thus for instance G is itself a G-space. A G-space X is transitive if for every x,y \in X, there exists g \in G such that gx=y. A morphism from one G-space X to another G-space Y is a map \phi:X \to Y such that \phi(gx) = g\phi(x) for all g \in G and x \in X.  If a morphism has an inverse that is also a morphism, we say that it is an isomorphism.

The first observation is that a G-space with certain properties will necessarily be isomorphic to G itself.

Lemma 1. (Criterion for isomorphism with G) Let G be a group, and let X be a non-empty transitive G-space, and suppose there is a morphism \pi: X \to G from the G-space X to the G-space G.  Then \pi is in fact an isomorphism of G-spaces.

Proof. It suffices to show that \pi is both injective and surjective.  To show surjectivity, observe that the image \pi(X) is G-invariant and non-empty.  But the action of G on G is transitive, and so \pi(X)=G as desired.  To show injectivity, observe from transitivity that if x, x' are distinct elements of X then x' = gx for some non-identity g \in G, thus \pi(x') = g \pi(x), thus \pi(x') \neq \pi(x), establishing injectivity. \Box

Now we can give the word formulation of the amalgamated free product.

Lemma 2. (Word-based description of amalgamated free product) Let G_1, G_2 be two groups with common subgroup H, and let G := G_1 *_H G_2 be the amalgamated free product.  Let G_1 = \bigcup_{s_1 \in S_1} H \cdot s_1, G_2 = \bigcup_{s_2 \in S_2} H \cdot s_2 be some partitions of G_1, G_2 into right-cosets of H.  Let X be the space of all formal words of the form h s_1 s_2 \ldots s_n, where h \in H, each s_i lies in either S_1 or S_2, and no two adjacent s_i, s_{i+1} lie in the same S_j.  let \pi: X \to G be the obvious evaluation map.  Then there is an action of G on X for which \pi becomes an isomorphism of G-spaces.

Proof. It is easy to verify that G_1 and G_2 act separately on X in a manner consistent (via \pi) with their action on G, and these actions agree on H.  Hence the amalgamated free product G also acts on this space and turns \pi into a morphism of G-spaces. From construction of X we see that the G-action is transitive, and the claim now follows from Lemma 1. \Box

Corollary 1. Let G_1, G_2 be two groups with common subgroup H, and let G := G_1 *_H G_2 be the amalgamated free product. Let g_1 \in G_1 and g_2 \in G_2 be such that the cyclic groups \langle g_1 \rangle, \langle g_2 \rangle are infinite and have no intersection with H.  Then g_1, g_2 generate a free subgroup in G.

Proof. By hypothesis (and the axiom of choice), we can find a partition G_1 = \bigcup_{s_1 \in S_1} H \cdot s_1 where S_1 contains the infinite cyclic group \langle g_1 \rangle, and similarly we can find a partition G_2 = \bigcup_{s_2 \in S_2} H \cdot s_2. Let X be the space in Lemma 2.  Each reduced word formed by g_1, g_2 then generates a distinct element of X, and thus (by Lemma 2) a distinct element of G.  The claim follows. \Box

Remark 3. The above corollary can also be established by the ping-pong lemma (which is not surprising, since the proof of that lemma uses many of the same ideas, and in particular exploiting an action of G on a space X in order to distinguish various words in G from each other).  Indeed, observe that g_1, g_1^{-1} map those words h s_1 s_2 \ldots s_n in X with s_1 \not \in S_1 into words h s_0 s_1 \ldots s_n with s_0 \in S_1, and similarly for g_2, g_2^{-1}, which is the type of hypothesis needed to apply the ping-pong lemma. [Thanks to Ben Green for this observation.] \diamond

Now we can finish the proof of Theorem 1.  As discussed in Example 2, the group G_1 := \langle a, b, c | ab=ba^2, bc = cb^2 \rangle is the amalgamated free product of \langle a, b | ab=ba^2 \rangle and \langle b, c | bc=cb^2 \rangle relative to \langle b \rangle.  By Corollary 1, a and c generate the free group here, thus G_1 contains H = \langle a, c \rangle as a subgroup.  Similarly, the group G_2 := \langle c, d, a | cd=dc^2; da=ad^2 \rangle also contains H = \langle a, c \rangle as a subgroup.  We may then form the amalgamated free product

G := G_1 *_H G_2 = \langle a, b, c, d | ab = ba^2, bc = cb^2, cd = dc^2, da=ad^2 \rangle

and another application of Theorem 1 shows that b,d generate the free group (and are in particular distinct); similarly a, c are distinct.  Finally, the group \langle a,b | ab=ba^2 \rangle embeds into G_1, which embeds into G, and so a, b, are also distinct; cyclically permuting this we conclude that all of the a, b, c, d are distinct as claimed.