# Effective results on the size and structure of sumsets

For a set ${A \subset \mathbb{Z}^d}$ we define the ${N}$-fold sumset of ${A}$ via

$\displaystyle NA : = \{a_1 + \ldots + a_N : a_i \in A\}.$

We have the following result of Khovanskii from 1992.

Theorem 1 (Polynomial size of iterated sumsets): Let ${A \subset \mathbb{Z}^d}$ of size ${n}$. Then there exists a ${N_A \geq 1}$ and ${c_0 , \ldots , c_d \in \mathbb{Q}}$ such that for ${N \geq N_A}$

$\displaystyle |NA| = \sum_{j=0}^d c_j N^j. \ \ \ \spadesuit$

One part of a recent work, Andrew Granville, Aled Walker, and I were able to provide effective bounds for ${N_A}$. We let

$\displaystyle w(A) = \max_{a , b \in A} ||a-b||_{\infty}.$

Theorem 2 (Effective Khovanskii): Let ${A \subset \mathbb{Z}^d}$ of size ${n}$. Then there exists ${c_0 , \ldots , c_d \in \mathbb{Q}}$ such that for any

$\displaystyle N \geq 2^{2n} n^{n^3 + 1} w(A)^{n^3}.\ \ \ \ \ (1)$

one has

$\displaystyle |NA| = \sum_{j=0}^d c_j N^j. \ \ \ \spadesuit$

It is not clear that (1) is best possible. Certainly there has to be some dependence on how ${A}$ lies in space, as can be seen by taking the elements of ${A}$ to be increasingly spread out. Curran and Goldmakher showed that when ${|A| = d+2}$, one needs ${N_A}$ at least the order of ${ \omega(A)^d }$

We first recall an elegant proof of Theorem 1 due to Nathanson and Ruzsa, which is also the starting point for Theorem 2.

Proof of Theorem 1: We consider ${\mathbb{Z}_{\geq 0}^n}$, equipped with ${\leq}$, the lexicographical ordering. Let ${A = \{a_1 ,\ldots , a_n\}}$. We then have a map

$\displaystyle \phi : \mathbb{Z}_{\geq 0}^n \rightarrow \bigcup_{j=0}^{\infty} jA,$

via

$\displaystyle \phi(x_1 , \ldots , x_n) =x_1 a_1 + \ldots + x_n a_n.$

It is worth noting that if ${\phi}$ is injective, we immediately deduce Theorem 1 by the stars and bars. Typically ${\phi}$ is not injective, but it turns out to not be a significant problem. We let ${U}$ be the set of elements ${x}$ such that there exists a ${y}$ with ${||y||_1 = ||x||_1}$, ${y < x}$, and ${\phi(y) = \phi(x)}$. We call any element of ${U}$ useless. They are deemed useless as

$\displaystyle |NA| = \{x \in \mathbb{Z}_{\geq 0}^n : ||x||_1 = N\} \setminus U.$

There is nothing intrinsic that makes elements of ${U}$ useless, rather it is a consequence of our choice of lexicographical ordering. One can check that ${U}$ is closed under translations from elements of ${\mathbb{Z}_{\geq 0}^n}$.

We need a way to count the elements of ${U}$ and thus propose another definition. We let ${\leq_{{\rm unif}}}$ be the partial ordering where ${x \leq_{{\rm unif}} y}$ if ${x}$ is smaller than ${y}$ coordinate-wise. Let ${U_{\min}}$ be the elements ${x \in U}$ such that there is no ${y\in U}$ with ${y <_{{\rm unif}} x}$. Dickson’s lemma implies that ${U_{\min}}$ is finite. For a set ${U'}$, we let

$\displaystyle B(N, U') = \{x \in \mathbb{Z}_{\geq 0 }^n: ||x||_1 = N , x >_{{\rm unif}} u, \ \text{for all} \ u \in U'\}.$

Thus we have, by the inclusion-exclusion principle,

$\displaystyle | \{x \in \mathbb{Z}_{\geq 0}^n : ||x||_1 = N\} \setminus U| = \sum_{U' \subset U_{\min}} (-1)^{|U'|}| B(N , U')|.$

Thus it is enough to show for any finite ${U'}$, ${\#B(N,U')}$ is polynomial in ${N}$, for ${N}$ large enough. This follows from the same stars and bars argument mentioned above, as long as

$\displaystyle N \geq \max_{u \in U'} ||u||_{\infty}, \ \ \ \ \ (2)$

and Theorem 1 follows. ${\spadesuit}$

Note that this proof does not give any effective bound on ${N_A}$, as we do not have any control over the set ${U_{\min}}$. In particular, one would like to have a bound on the ${\ell^{\infty}}$ norm of the elements of ${U_{\min}}$, in light of (2). In general, one cannot make Dickson’s lemma quantitative, but in our case we can use the structure of ${U_{\min}}$ to do so. The point is that ${U}$ is defined by linear relations, so one can appeal to Siegel’s lemma.

Proof (sketch) of Theorem 2: We translate ${A}$ so that ${0 \in A}$, which does not effect the problem (in particular, ${w(A)}$ remains unchanged). We build upon the proof of Theorem 1. Suppose ${x \in U_{\min}}$. As ${x \in U}$, there is a ${y \in \mathbb{Z}_{\geq 0}^n}$ such that ${||x||_1 = ||y||_1}$, ${y < x}$, and ${\phi(x) = \phi(y)}$. Thus

$\displaystyle \sum_{i \in I} x_i a_i = \sum_{j \in J} y_i a_j.$

As ${x \in U_{\min}}$, one can check that ${I\cap J = \emptyset}$. We now construct a matrix ${M}$ as follows. The first row has ${\#I}$ 1’s followed by ${\#J}$ ${-1}$‘s. The remaining ${d}$ rows are give by ${(a_i)_{i \in I}}$ and ${(-a_j)_{j \in J}}$. Thus

$\displaystyle M (x,y)^T = 0 \ \ \ \ \ (3)$

One would hope to apply Siegel’s lemma, which asserts that (3) has a solution such that ${||(x,y)||_{\infty}}$ is small. The primary issue is that this small solution, ${x^*}$ may have nothing to do with ${(x,y)^T}$. However one can translate ${(x,y)^T}$ by a multiple of ${x^*}$ to create a solution that is small in a single coordinate. Then one “forgets” this coordinate and tries proceeds by induction. A secondary issue is that the ${x^* \in \mathbb{Z}^n}$, may have negative coordinates, but this turns out to not be a critical issue. All of this carried out in section 6 of the aforementioned paper with Granville and Walker. ${\spadesuit}$