Let c≥1 be a real number. Let G be an abelian group and let A⊂G be a finite set satisfying ∣A+A∣≤c∣A∣, where X+Y:={x+y∣x∈X,y∈Y} and ∣Z∣ denotes the cardinality of Z. Prove that
∣k timesA+A+⋯+A∣≤ck∣A∣
for every positive integer k.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
(Proposed by Przemyslaw Mazur, Jagiellonian University)
Solution. Let B be a nonempty subset of A for which the value of the expression c1=∣B∣∣A+B∣ is the least possible. Note that c1≤c since A is one of the possible choices of B.
Lemma 1. For any finite set D⊂G we have ∣A+B+D∣≤c1∣B+D∣.
Proof. Apply induction on the cardinality of D. For ∣D∣=1 the Lemma is true by the definition of c1. Suppose it is true for some D and let x∈/D. Let B1={y∈B∣x+y∈B+D}. Then B+(D∪{x}) decomposes into the union of two disjoint sets:
B+(D∪{x})=(B+D)∪((B∖B1)+{x})
and therefore ∣B+(D∪{x})∣=∣B+D∣+∣B∣−∣B1∣. Now we need to deal with the cardinality of the set A+B+(D∪{x}). Writing A+B+(D∪{x})=(A+B+D)∪(A+B+{x}) we count some of the elements twice: for example if y∈B1, then A+{y}+{x}⊂(A+B+D)∩(A+B+{x}). Therefore all the elements of the set A+B1+{x} are counted twice and thus
where the last inequality follows from the inductive hypothesis and the observation that ∣B∣∣A+B∣=c1≤∣B1∣∣A+B1∣ (or B1 is the empty set). □
Lemma 2. For every k≥1 we have ∣k timesA+…+A+B∣≤c1k∣B∣.
Proof. Induction on k. For k=1 the statement is true by definition of c1. For greater k set D=k−1 timesA+…+A in the previous lemma: ∣k timesA+…+A+B∣≤c1∣k−1 timesA+…+A+B∣≤c1k∣B∣. □
Remark. The proof above due to Giorgios Petridis and can be found at http://gowers.wordpress.com/2011/02/10/a-new-way-of-proving-sumset-estimates/
Transcribed from the official solutions, page 4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.