Computer Science/Discrete Mathematics Seminar II

We will continue the proof of the following result: if A is a finite subset of a free group with at least two non-commuting elements then |AAA| is almost quadratic in |A|. Last week we reduced the problem to obtaining lower bounds on |ABC| when there are no cancellations, A is a prefix chain, C is a suffix chain and B has relatively small intersections with cosets of all cyclic subgroups. Today we will show the remaining (and crucial) part based on the theory of highly periodic words. The talk will be reasonably self-contained and independent of the first part.