Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-149/1/c/solution

By the Plünnecke-Ruzsa inequality,
Apply the Ruzsa covering lemma to and . Since , there is a set with such that
Adding and reusing this inclusion inductively gives
A sum of members of the fixed set depends only on the multiplicity of each member. The number of possible multiplicity vectors is at most , and therefore
Since , it follows that
For fixed , this differs from the Plünnecke–Ruzsa bound only by a polynomial factor in , so both have the same leading exponential function factor .

New to topics? Read the docs here!