Effective results on the size and structure of sumsets

Additive Combinatorics

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}

Leave a Reply