A Product Theorem in Free Groups

A. Razborov, IAS

In inverse problems in arithmetic combinatorics, one is interested in describing internal properties of those finite subsets $A$ of an algebraic structure that ``barely expand'' under its operations. One of the deepest results in the area is Freiman's theorem providing a complete characterization of the sets $A$ in abelian torsion-free groups for which $A+A$ is almost linear in $A$. Nothing non-trivial, however, is known already about sets of integers $A$ with $A+A+...+A\leq A^{1+\delta}$. Surprisingly, these questions have turned out to be easier for more complicated algebraic structures like commutative rings or, very recently, non-abelian groups. In particular, Chang (2006) proved that for some fixed $\delta$, any set $A$ in a free group with $|AAA|\leq A^{1+\delta}$ belongs to a cyclic subgroup. We give a purely combinatorial proof of this result based on the theory of periodic words and their occurrences. Our proof also shows that $\delta$ can be chosen arbitrarily close to 1, and this is optimal.