Let be finite and nonempty. One of the first things we learn in additive combinatorics is

There are a host of results improving on (1) when has certain structure. For instance, all of the following have an short and elementary proof. Here .

- (1)
- (2) , for convex,
- (3) ,
- (4) .

Let’s see one way to prove (1). After translation and dilation, we may suppose that contains both even and odd numbers. Let be the even numbers in and be the odd numbers in . By (1),

We remark that there is another proof of this in which one picks elements of in increasing order.

Antal Balog and I considered the question of improving (1) when . We proved the following.

**Theorem 1:** Let be an integer and be finite. Then

This is best possible up to the constant as can be seen by taking to be an arithmetic progression. Below in the fold, we will a proof in the case where is a prime. This case is technically easier, and was first handled by Cilleruelo, Hamidoune, and Serra. Already the case is non–trivial, though a proof of had appeared several times in the literature. We adopt the proof from our paper, which can be modified to handle the general case.

We partition into residue classes modulo as follows:

We say is fully–distributed mod (FD) if or equivalently intersects every residue class modulo . The key fact is that not only the sets are disjoint, but so are the sets and we have

As long as , we may assume that since we may replace with . This is actually a key point: Theorem 1 is translation and dilation invariant. We first show that Theorem 1 is true for random sets.

**Lemma (FD):** Suppose is FD. Then

**Proof:** By (1) and (3), we have

Now we are in a position to prove Theorem 1.

by induction on . For , this follows from (1) with . We now assume (4) holds for some and show it for .

Suppose that there is some such that . Then by (1), (4) and , we have

Suppose now that , as defined in (2) is FD for all . By (3) and translation and dilation invariance of , we have

and there is some such that is not FD. We then apply the following lemma.

**Lemma (not FD):** Suppose is not FD. Then

Let’s use Lemma (not FD) to finish the proof. By Lemma (not FD), (4) twice and (5) we have

This completes the proof modulo Lemma (not FD).

**Proof of Lemma (not FD):** Suppose

Then for any , we have

It follows that for every there is a such that , and so there is an such that

We may repeat this argument with in place of and so on to get that for every and , there is such that

Since is prime, we get that is FD, as desired.

Since this work, I worked out the general case of sum of many dilates. After that, Antal Balog and I worked on the analogous problem in vector spaces. Both papers contain several open problems and one of them appears on my problems page with a cash reward. Also, feel free to see my short video I made on the topic, which highlights some of the problems.

One natural generalization that remains open is

where and not contained in any dimensional subspace. The cases and are known to hold.