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.