For a set we define the -fold sumset of via
We have the following result of Khovanskii from 1992.
Theorem 1 (Polynomial size of iterated sumsets): Let of size . Then there exists a and such that for
It is not clear that (1) is best possible. Certainly there has to be some dependence on how lies in space, as can be seen by taking the elements of to be increasingly spread out. Curran and Goldmakher showed that when , one needs at least the order of
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 , equipped with , the lexicographical ordering. Let . We then have a map
It is worth noting that if is injective, we immediately deduce Theorem 1 by the stars and bars. Typically is not injective, but it turns out to not be a significant problem. We let be the set of elements such that there exists a with , , and . We call any element of useless. They are deemed useless as
There is nothing intrinsic that makes elements of useless, rather it is a consequence of our choice of lexicographical ordering. One can check that is closed under translations from elements of .
We need a way to count the elements of and thus propose another definition. We let be the partial ordering where if is smaller than coordinate-wise. Let be the elements such that there is no with . Dickson’s lemma implies that is finite. For a set , we let
Thus we have, by the inclusion-exclusion principle,
Thus it is enough to show for any finite , is polynomial in , for large enough. This follows from the same stars and bars argument mentioned above, as long as
and Theorem 1 follows.
Note that this proof does not give any effective bound on , as we do not have any control over the set . In particular, one would like to have a bound on the norm of the elements of , in light of (2). In general, one cannot make Dickson’s lemma quantitative, but in our case we can use the structure of to do so. The point is that is defined by linear relations, so one can appeal to Siegel’s lemma.
Proof (sketch) of Theorem 2: We translate so that , which does not effect the problem (in particular, remains unchanged). We build upon the proof of Theorem 1. Suppose . As , there is a such that , , and . Thus
As , one can check that . We now construct a matrix as follows. The first row has 1’s followed by ‘s. The remaining rows are give by and . Thus
One would hope to apply Siegel’s lemma, which asserts that (3) has a solution such that is small. The primary issue is that this small solution, may have nothing to do with . However one can translate by a multiple of 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 , 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.