You are currently browsing the tag archive for the ‘Freiman isomorphism’ tag.
Additive combinatorics is largely focused on the additive properties of finite subsets A of an additive group . 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 inside the integers . 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 without losing any combinatorial information. More precisely, there is a Freiman isomorphism of order 2 between the set in and the set in . One can view the latter version of as a model for the former version of . 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 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
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 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.