9
$\begingroup$

Given $a, b \in \mathbb Z$, set $[\![a,b]\!] := \{x \in \mathbb Z: a \le x \le b\}$. A basic result in additive number theory goes as follows:

If $A$ is a finite subset of $\mathbb N$ with $0 \in A$ and $\gcd A = 1$, then there exist $b, c \in \mathbb N$, $B \subseteq [\![0, b-2 ]\!]$, and $C \subseteq [\![ 0, c-2 ]\!]$ such that $$ kA = B \cup [\![ b, k \max A - c ]\!] \cup (k\max A - C)$$ for all but finitely many $k \in \mathbb N^+$, where $$ kA := \{a_1 + \cdots + a_k: a_1, \ldots, a_k \in A\}$$ is the $k$-fold sumset of the set $A$.

The result is sometimes referred to as the fundamental theorem of additive number theory; see, for instance, the 2nd paragraph on p. 3 of

M.B. Nathanson, 'Addictive Number Theory', pp. 1–8 in: D. Chudnovsky and G. Chudnovsky (eds.), Additive Number Theory, Springer, 2010.

I'd like to ask the following:

Question. What is the earliest appearance of the result in the literature?

Over the years, I've consistently attributed the theorem to Melvyn Nathanson, who proved an effective version of it in

Sums of finite sets of integers, Amer. Math. Monthly 79 (1972), No. 9, 1010–1012.

In fact, I believe that Nathanson's paper is the right answer to my question. However, I know some reputed scholars in the additive combinatorics community who maintain (in private communications) that the result is folklore. Moreover, my attribution of the theorem to Nathanson was recently questioned by an anonymous referee in their report on a joint paper with Weihao Yan. So, I've decided to ask here, in the hope of shedding further light on this matter.

For instance, there is no reference to any folklore result along the lines of Nathanson's theorem in

A. Granville, G. Shakan, and A. Walker, Effective Results on the Size and Structure of Sumsets, Combinatorica 43 (2023), 1139–1178.

And Nathanson attributes the theorem to himself in

Sums of Finite Sets of Integers, II, Amer. Math. Monthly 128 (2021), No. 10, 888–896,

where one can read,

A fundamental theorem of additive number theory, published 50 years ago in [7, 8], explicitly solves the asymptotic problem for finite sets of integers.

In this excerpt, [7] is Nathanson's 1972 paper cited above, while [8] is Nathanson's 1996 book Additive Number Theory: Inverse Problems and the Geometry of Sumsets (GTM 165).

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I don't know of any older reference where this result is explicitly proven. But from the theory of the Hilbert polynomial (from 1890) one can show that $|kA|$ is eventually polynomial in $k$, and using easy upper bounds one can show that this polynomial must be linear. Using Freiman's $3k-4$ theorem (1959) this already gives most of the desired description of $kA$, with the rest being straightforward elementary case analysis. But this does require some nontrivial effort. $\endgroup$
    – Terry Tao
    Commented Aug 7 at 15:28
  • 5
    $\begingroup$ Also, to my knowledge, this result has not been referred to as the fundamental theorem in additive combinatorics (note the use of the indefinite article in the quote from Nathanson). In fact I would argue that Freiman's inverse sumset theorem (and its generalizations) have been more fundamental to the subject. $\endgroup$
    – Terry Tao
    Commented Aug 7 at 15:31
  • 3
    $\begingroup$ See also the theory of the Frobenius coin problem (introduced by Sylvester in 1882) and Schur's theorem (1912): en.wikipedia.org/wiki/Coin_problem en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics, which addresses the related problem of describing $\bigcup_{k=1}^\infty kA$. $\endgroup$
    – Terry Tao
    Commented Aug 7 at 15:35
  • 2
    $\begingroup$ It's possible here that one needs to disambiguate between additive combinatorics, and the older subject of additive number theory (which, roughly speaking, corresponds to the additive combinatorics of the integers or natural numbers). $\endgroup$
    – Terry Tao
    Commented Aug 7 at 17:21
  • 1
    $\begingroup$ As far as I know, the result is due to Nathanson (1972). The mere existence of the structure for $k$ large should not be difficult to derive from the Sylvester-Frobenius observation on the coin problem. A much more difficult problem (mostly solved now) is to determine the smallest value of $k$ for which $kA$ is structured. $\endgroup$
    – Seva
    Commented Aug 8 at 6:47

1 Answer 1

Reset to default
12
$\begingroup$

I shared the link to this thread with several colleagues, inviting them to contribute to the discussion. Notably, I received a response from Melvyn Nathanson himself, most of which is reproduced below with his permission:

As far as I know, my result was never part of any folklore and I was the first person to consider and solve the problem of the structure of iterated sumsets of a finite set of integers and to obtain, as a corollary, the exact linear growth of the cardinality of the sumsets. [...] the result could be deduced from the (19th century) Hilbert polynomial, but the first person to apply the Hilbert polynomial to additive problems was Askold Khovanskii in a beautiful paper in 1992 (and, according to MathScinet, I was the first person to cite this paper in 2000). Indeed, like many simple but basic results in mathematics, the theorem about the growth of finite sumsets could easily have been proved by Euclid and certainly by Euler, if either had asked the question, but often in mathematics the most important thing is to think of the question.

I don't expect any better answer to the question, so I’m going to accept this one.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .