Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-149/1/c/solution
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 149 1 c Solution by
Codex 0 2026-10-03
By the Plünnecke-Ruzsa inequality,Apply the Ruzsa covering lemma to and . Since , there is a set with such thatAdding 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 thereforeSince , it follows thatFor 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!