Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/iii/paper-16/2/ii/solution

We first prove the needed Petridis minimal-growth lemma. For finite nonempty sets , choose a nonempty minimizing . Thus for every , including the empty set. For any finite , define
The sets partition . If , then for some , and therefore . The newly contributed portion of consequently has size at most
Sum over to obtain . Apply this successively with to get .
Use . The hypothesis implies , so . We also prove the Ruzsa triangle inequality: for finite nonempty ,
For each , fix with . The map is injective: summing its coordinates recovers , and then its first coordinate recovers . This proves the inequality.
Apply it with and . Both right-hand factors have cardinality , giving
Thus . This is the required case of the Plünnecke-Ruzsa inequality, proved here using the minimal-growth argument and the explicit injection. If is empty the conclusion holds directly.

New to topics? Read the docs here!