Explicit sumset sizes in additive number theory

1. Problem Statement

The central problem addressed in this paper is the characterization of the set of possible sizes of $h$-fold sumsets for finite sets of integers.

• Definitions: Let $A$ be a finite subset of integers with cardinality $|A| = k$. The $h$-fold sumset $hA$ is defined as the set of all sums of $h$ (not necessarily distinct) elements from $A$:
  $$hA = \{a_1 + \dots + a_h : a_i \in A\}$$
• The Target Set: The paper investigates the set $R_{\mathbb{Z}}(h, k)$, which contains all possible cardinalities $|hA|$ for sets $A$ of size $k$:
  $$R_{\mathbb{Z}}(h, k) = \{|hA| : A \subseteq \mathbb{Z}, |A| = k\}$$
• Known Bounds:
  • Minimum: $|hA| \geq hk - h + 1$. Equality holds if and only if $A$ is an arithmetic progression.
  • Maximum: $|hA| \leq \binom{h+k-1}{h}$. Equality holds if and only if $A$ is a $B_h$-set (all $h$-fold sums are distinct).
• The Gap: While the minimum and maximum are well-understood, the full range of intermediate values in $R_{\mathbb{Z}}(h, k)$ for $h \geq 3$ and $k \geq 3$ was largely unknown. Previous work established that $R_{\mathbb{Z}}(h, k)$ is not a continuous integer interval (there are "missing numbers"), but the specific structure of these gaps and the existence of explicit constructions for values within the range remained an open problem.

2. Methodology

Nathanson employs a constructive approach, moving away from probabilistic or random set generation to derive explicit families of finite sets with calculable sumset sizes. The methodology relies on:

1. Affine Invariance: Utilizing the fact that sumset size is invariant under affine transformations ($B = \lambda A + \mu$), allowing the restriction of study to subsets of non-negative integers.
2. Vector Representation: Representing the sumset $hA$ via the set of vectors $X_{h,k} = \{(x_1, \dots, x_k) \in \mathbb{N}_0^k : \sum x_j = h\}$. The sumset is the image of the dot product $x \cdot a$.
3. Interval Union Analysis: Constructing sets $A$ as unions of arithmetic progressions or intervals. The core technique involves analyzing the union of translated intervals generated by the sumset operation.
   • The paper defines conditions under which these resulting intervals overlap or remain disjoint.
   • It utilizes a "gap" analysis to determine when the union of intervals forms a single continuous block versus a set of disjoint blocks.
4. Inductive Proofs: Using induction on the number of elements $k$ and the sumset order $h$ to prove properties of the resulting sumset sizes.

3. Key Contributions and Results

A. Clarification of the "Missing Number" Phenomenon

The paper reinforces and extends previous findings (Theorem 3 and 4) that $R_{\mathbb{Z}}(h, k)$ is not an interval. Specifically:

• The value $hk - h + 2$ is never in $R_{\mathbb{Z}}(h, k)$.
• A larger gap exists: The interval $[hk - h + 2, hk - 1]$ contains no elements of $R_{\mathbb{Z}}(h, k)$.
• However, the value $hk$ is always present in the set.

B. Explicit Constructions for $k=4$ (The $R_{\mathbb{Z}}(h, 4)$ Case)

A major contribution is the detailed characterization of sumset sizes for sets of size 4, which had previously been a "mystery."

• Theorem 6 (Arithmetic Progressions of Translates): The author constructs sets $A$ formed by the union of $\ell$ translates of an interval $[0, a-1]$ spaced by a difference $b$.
  • If $A = \bigcup_{j=1}^\ell ((j-1)b + [0, a-1])$ with $k = a\ell$, the paper derives explicit formulas for $|hA|$.
  • Result: This construction yields an arithmetic progression of sumset sizes within $R_{\mathbb{Z}}(h, k)$.
  • Corollary 2: Specifically for $k=4$, $R_{\mathbb{Z}}(h, 4)$ contains the $h$-term arithmetic progression $\{bh + 1 : b \in [3, h+2]\}$.

C. Sums of Intervals of Different Lengths

The paper analyzes sets $A$ composed of two disjoint intervals of different lengths: $A = [0, a] \cup [b, b+c]$.

• Theorem 7: Provides an exact formula for $|hA|$ based on the relationship between the gap $b$ and the interval lengths $a, c$.
  • Case 1 (Large Gap): If $b > ha$, the sumset consists of disjoint intervals, and the size is a quadratic function of $h$.
  • Case 2 (Overlapping): If $a < b \leq ha$, the intervals merge partially. The size is given by a complex formula involving the floor function $i_0 = \lfloor \frac{ha-b}{a-c} \rfloor$.
• Corollary 5: Using this theorem, the author proves that $(h+1)^2 \in R_{\mathbb{Z}}(h, 4)$ and identifies specific values generated by varying the gap $b$.

D. Existence of $hk$

Corollary 6 provides a constructive proof that $hk \in R_{\mathbb{Z}}(h, k)$ for all $h \geq 2, k \geq 3$, utilizing the set $A = [0, k-2] \cup \{k\}$.

E. Arithmetic Progressions in $R_{\mathbb{Z}}(h, k)$

Corollary 7 demonstrates that for any fixed $h$ and $k$, the set $R_{\mathbb{Z}}(h, k)$ contains substantial integer intervals (arithmetic progressions with difference 1). Specifically, it contains the interval:
$$\left[ \frac{h^2(k-2)}{2} + \frac{hk}{2} - k + 3, \quad \frac{h^2(k-2)}{2} + \frac{hk}{2} \right]$$

4. Significance

• Structural Insight: The paper moves beyond simple bounds to reveal the internal structure of $R_{\mathbb{Z}}(h, k)$. It proves that while the set is not a single interval, it contains large, contiguous blocks of integers (arithmetic progressions).
• Explicit Constructions: Prior to this work, finding a set $A$ with a specific sumset size often required exhaustive computer searches. Nathanson provides closed-form constructions (families of sets) that guarantee specific sumset sizes, making the generation of these values deterministic.
• Resolution of Specific Cases: It effectively solves the problem for $k=4$ by providing a rich family of values, significantly reducing the "unknown" territory in additive number theory for small set sizes.
• Foundation for Future Research: By establishing that $R_{\mathbb{Z}}(h, k)$ contains explicit arithmetic progressions, the paper suggests that the set is "dense" in certain regions, guiding future research into the distribution of the remaining "missing" numbers.

In summary, Nathanson's paper transforms the understanding of sumset sizes from a problem of bounding to a problem of explicit construction, demonstrating that the set of possible sizes is far more structured and populated than previously realized, containing large arithmetic progressions derived from unions of intervals.