Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/iii/paper-16/2/ii/solution
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 16 2 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
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 , defineThe sets partition . If , then for some , and therefore . The newly contributed portion of consequently has size at mostSum 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 , givingThus . 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!