You are currently browsing the tag archive for the ‘amalgamated free product’ tag.

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.

 Anonymous on Polymath15, ninth thread: goin… Anonymous on Polymath15, ninth thread: goin… geepee on The blue-eyed islanders puzzle… Anonymous on Polymath15, ninth thread: goin… Jim H Adams on Expansion in finite simple gro… Anonymous on Heat flow and zeroes of polyno… timobock on 245B, Notes 11: The strong and… Don'tknow on Open thread for mathematicians… Don'tknow on Open thread for mathematicians… Alexander Davis on The Dantzig selector: Statisti… Covering and Plünnec… on An entropy Plünnecke-Ruzsa… michaelmross on The Collatz conjecture, Little… Vincent on The Collatz conjecture, Little… juststudent on The Collatz conjecture, Little… Terence Tao on Polymath15, ninth thread: goin…