# Sum of a set and its dilate

Let ${A, B \subset \mathbb{Z}}$ be finite and nonempty. One of the first things we learn in additive combinatorics is

$\displaystyle |A+B| \geq |A| +|B| - 1. \ \ \ \ \ (1)$

There are a host of results improving on (1) when ${B}$ has certain structure. For instance, all of the following have an short and elementary proof. Here ${q \cdot A := \{qa : a \in A\}}$.

• (1) ${|A+2\cdot A| \geq 2 |A| - 3}$
• (2) ${|A+A -A| \gg |A|^2}$, for ${A}$ convex,
• (3) ${|A+AA| \geq |A|^2 + |A| - 1}$,
• (4) ${|A + A^{-1}| \geq |A|^2}$.

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

$\displaystyle |A+2 \cdot A| = |A_0 + 2 \cdot A| + |A_1 + 2 \cdot A| \geq |A_0| + |A| - 1 + |A_1| + |A| - 1 = 3 |A| - 2.$

We remark that there is another proof of this in which one picks ${2 |A| - 3}$ elements of ${A+2 \cdot A}$ in increasing order.

Antal Balog and I considered the question of improving (1) when ${B = q \cdot A }$. We proved the following.

Theorem 1: Let ${q\geq 1}$ be an integer and ${A \subset \mathbb{Z}}$ be finite. Then

$\displaystyle |A+q \cdot A| \geq (q + 1) |A| - O_q(1). \ \ \ \spadesuit$

This is best possible up to the constant as can be seen by taking ${A}$ to be an arithmetic progression. Below in the fold, we will a proof in the case where ${q}$ is a prime. This case is technically easier, and was first handled by Cilleruelo, Hamidoune, and Serra. Already the case ${q=3}$ is non–trivial, though a proof of ${|A+3 \cdot A| \geq 4 |A| - 4}$ 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 ${A}$ into residue classes modulo ${q}$ as follows:

$\displaystyle A = \displaystyle \bigcup_{j = 1}^s A_j , \ \ A_j = a_j + q \cdot A_j^{\prime}, \ \ A_j \neq \emptyset ,\ \ 0 \leq a_j < q.\ \ \ \ \ (2)$

We say ${A}$ is fully–distributed mod ${q}$ (FD) if ${s=q}$ or equivalently ${A}$ intersects every residue class modulo ${q}$. The key fact is that not only the sets ${A_i}$ are disjoint, but so are the sets ${A_i + q \cdot A}$ and we have

$\displaystyle A + q \cdot A= \coprod_{i =1}^s A_i + q \cdot A.\ \ \ \ \ (3)$

As long as ${|A| \geq 2}$, we may assume that ${s \geq 2}$ since we may replace ${A}$ with ${\frac{1}{q} \cdot (A - x)}$. 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 ${A}$ is FD. Then

$\displaystyle |A+q \cdot A| \geq (q+1)|A| - q. \ \ \ \spadesuit$

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

$\displaystyle |A+q \cdot A| = \sum_{j=1}^q |A_j + q \cdot A| \geq \sum_{j=1}^q \left(|A_j |+ |A| - 1 \right) = (q + 1)|A| - q. \ \ \ \spadesuit$

Now we are in a position to prove Theorem 1.

Proof of Theorem 1: We prove

$\displaystyle |A+q \cdot A| \geq \frac{m}{q} |A| - C_m,\ \ \ \ \ (4)$

by induction on ${m}$. For ${m = 2q}$, this follows from (1) with ${C_m = 1}$. We now assume (4) holds for some ${m < q(q+1)}$ and show it for ${m+1}$.

Suppose that there is some ${1 \leq i \leq s}$ such that ${|A_i| \leq q^{-1} |A|}$. Then by (1), (4) and ${m < q(q+1)}$, we have

$\displaystyle |A+q \cdot A| \geq |A_i + q \cdot A| + |(A \setminus A_i) + q \cdot (A \setminus A_i)|$

$\displaystyle \geq |A_i| + |A| - 1 + \frac{m}{q} (|A| - |A_i|) - C_m \geq \frac{m+1}{q} |A| - C_m - 1.$

Suppose now that ${A_i'}$, as defined in (2) is FD for all ${1 \leq i \leq s}$. By (3) and translation and dilation invariance of ${|X+ q \cdot X|}$, we have

$\displaystyle |A+q \cdot A| \geq \sum_{j=1}^s |A_j + q \cdot A_j| = \sum_{j=1}^s |A'_j + q \cdot A'_j| \geq (q+1) |A| - q^2.$

Thus we may suppose that

$\displaystyle |A_i| \geq \frac{|A|}{q} , \ \ 1 \leq i \leq s,\ \ \ \ \ (5)$

and there is some ${k}$ such that ${A'_k}$ is not FD. We then apply the following lemma.

Lemma (not FD): Suppose ${A_k'}$ is not FD. Then

$\displaystyle |A_j+ q \cdot A| \geq |A_j + q \cdot A_j| + \min_{1 \leq m \leq s} |A_m|. \ \ \ \spadesuit$

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

$\displaystyle |A+q \cdot A| \geq |A_k + q \cdot A| + |(A \setminus A_k) + q \cdot (A \setminus A_k)|$

$\displaystyle \geq |A_k + q \cdot A_k| + \min_{1 \leq m \leq s} |A_m| + \frac{m}{q} (|A| - |A_k|) - C_m$

$\displaystyle \geq \frac{m}{q} |A_k| - C_m + \frac{|A|}{q} + \frac{m}{q} (|A| - |A_k|) - C_m$

$\displaystyle = \frac{m+1}{q} |A| - 2 C_m.$

This completes the proof modulo Lemma (not FD).

Proof of Lemma (not FD): Suppose

$\displaystyle |A_k + q \cdot A| < |A_k + q \cdot A_k| + \displaystyle \min_{1 \leq m \leq s} |Q_m|.$

Then for any ${1\leq m \leq s}$, we have

$\displaystyle |A_m^{\prime}| = |A_m| > |(A_k+ q \cdot A_m )\setminus (A_k+ q \cdot A_k) | = |(a_m - a_k + A_k^{\prime} + q \cdot A_m^{\prime}) \setminus (A_k^{\prime} + q \cdot A_k^{\prime})|.$

It follows that for every ${x \in A_k^{\prime}}$ there is a ${y \in A_m^{\prime}}$ such that ${a_m-a_k+x+qy\in A'_k + q\cdot A'_k}$, and so there is an ${x'\in A'_k}$ such that

$\displaystyle a_m - a_k + x \equiv x' \pmod q.$

We may repeat this argument with ${x'}$ in place of ${x}$ and so on to get that for every ${x \in A'_k}$ and ${w \in \mathbb{Z}}$, there is ${z \in A'_k}$ such that

$\displaystyle w(a_m - a_k) + x = z \pmod q.$

Since ${q}$ is prime, we get that ${A'_k}$ is FD, as desired. ${\spadesuit}$

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

$\displaystyle |A+q \cdot A| \geq (|q| + 2d -1)|A| - O_{d , q}(1),$

where ${A \subset \mathbb{Z}^d}$ and not contained in any ${d-1}$ dimensional subspace. The cases ${d=2}$ and ${d=3}$ are known to hold.