🔢 mathematics

Inverse problems for sumset sizes of finite sets of integers

This paper investigates the sequence of sumset sizes for finite sets of integers, analyzing the relationships between these sequences for affinely inequivalent sets and comparing their growth rates and configurations.

Original authors: Melvyn B. Nathanson

Published 2026-07-23

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Melvyn B. Nathanson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where numbers aren't just tools for counting, but characters in a story about how they mix together. This story lives in a branch of mathematics called additive number theory, a field that studies what happens when you take a group of numbers and add them to each other. Think of it like a kitchen: if you have a bag of specific ingredients (a set of numbers), what happens when you mix them? If you take two ingredients and combine them, you get a new batch. If you take three, you get an even bigger batch. Mathematicians call these batches "sumsets."

The big question this paper tackles is a bit like a detective story. Usually, we know the ingredients and want to predict the size of the final dish. But here, the detective has the opposite problem: they see the size of the dish growing over time and want to figure out exactly what the original ingredients were. The paper asks: If two different groups of ingredients produce dishes of the exact same size at every stage of cooking, are the ingredients actually the same? Or can two completely different "recipes" (sets of numbers) produce identical growth patterns? It turns out that in the world of integers, the answer is surprisingly tricky, and the growth of these number-batches can wiggle and dance in ways we are only just beginning to understand.

The Mystery of the Growing Number Piles

In this paper, the author, Melvyn B. Nathanson, investigates the "sumset size" of finite sets of integers. Let's break this down with a simple metaphor. Imagine you have a small collection of unique stones, say a set $A$ . If you take two stones from this pile and add their values together, you get a new pile of numbers called the "2-fold sumset" ( $2A$ ). If you take three stones, you get the "3-fold sumset" ( $3A$ ), and so on. The paper tracks the size (the number of unique items) of these piles as you keep adding more stones to the mix.

For a long time, mathematicians knew that if you keep doing this enough times, the size of the pile grows in a very predictable, straight-line pattern. It's like a car that eventually settles into a steady cruise control speed. The paper confirms this "cruise control" behavior, showing that eventually, the size of the sumset increases by a fixed amount every time you add another layer.

The Great Identity Swap

The real magic happens when the author asks: Can two different sets of numbers look exactly the same as they grow?

Imagine two different boxes of LEGOs. Box A has a red brick and a blue brick. Box B has a green brick and a yellow brick. If you build towers by stacking them, maybe the number of unique tower heights you can make is identical for both boxes. The paper proves that this is not just a fluke; it's a common occurrence for sets of a certain size.

The author constructs specific examples of "affinely inequivalent" sets. In plain English, this means two sets that are not just simple copies of each other (like shifting all numbers up by 1 or stretching them by 2). They are genuinely different shapes. The paper shows that for sets of size $k \ge 3$ , you can find pairs of these different sets where the number of items in their sumsets is identical for every step starting from $h=2$ ( $h=2, 3, 4, \dots$ ).

For instance, the paper explicitly constructs two sets of size 3:

Set A: $\{0, 2, 7\}$
Set B: $\{0, 3, 7\}$

Even though these sets are different, the number of unique sums you get when you add them to themselves is exactly the same for every step from $h=2$ onwards. The paper provides explicit constructions for sets of size 3, size 4, and a general construction for any size $k \ge 5$ (by taking a base set of size 4 and adding a block of consecutive integers). This means that simply counting the size of the sumsets is not enough to tell you exactly what the original set of numbers was, because the "fingerprint" of the size sequence starting from the second step is not unique to the set.

The Oscillation Dance

But the story gets even more playful. The paper explores a phenomenon called "oscillation." Imagine two runners, Set A and Set B. Sometimes A is ahead (has a larger sumset), sometimes B is ahead. The paper asks: Can we make them switch leads back and forth as many times as we want?

The author provides a "yes" answer for specific patterns. By carefully choosing the numbers in the sets (specifically, sets that look like a solid block of numbers with one extra number far away), the paper demonstrates that you can engineer a scenario where:

For the first few steps, both sets produce the exact same number of sums.
Then, for a specific step, Set B suddenly produces more sums than Set A.
And this difference grows larger as you go further.

The paper proves that for any number of steps $h_1$ , you can find two sets of the same size that are identical up to step $h_1$ , but then Set B pulls ahead and stays ahead forever after. It's like two runners running a race where they are tied for the first mile, but then one suddenly speeds up and never looks back.

The Shape-Shifting Race

The paper also dives into a more complex game involving three or more sets. Instead of just comparing two runners, imagine a race with $n$ runners. The author introduces a concept called "normalization," which is like ranking the runners by who is currently in the lead, regardless of their actual speed. If Set A is the smallest, Set B is the middle, and Set C is the largest, their "ranked order" is (1, 2, 3).

The paper poses a fascinating question: Can we find a group of sets that changes their ranking order in a specific, pre-planned sequence? For example, could we find three sets where:

At step 1, the order is A < B < C.
At step 2, the order flips to C < A < B.
At step 3, it flips again to B < C < A.

The paper doesn't solve this completely but sets up the rules for the game. However, in a final update added in January 2025, the paper notes that another mathematician, Noah Kravitz, has recently proved that yes, you can indeed create sets that follow any specific sequence of rankings you want, for as long as you like, and then settle into a final, permanent order.

What Remains Unknown

While the paper solves several puzzles, it leaves the door wide open for others. It asks if we can make the runners switch leads in a complex, alternating pattern (like A wins, then B wins, then A wins again) for a long sequence of steps. It also wonders if we can do this while keeping the "maximum number" in both sets exactly the same. These are the open questions that invite the next generation of number detectives to step in.

In short, this paper reveals that the world of adding numbers is full of hidden twins and shape-shifters. Just because two groups of numbers grow at the same rate doesn't mean they are the same group, and with the right setup, you can make them dance in almost any pattern you can imagine.

Technical Summary: Inverse Problems for Sumset Sizes of Finite Sets of Integers

Problem Statement
This paper investigates inverse problems concerning the sequence of sumset sizes $(|hA|)_{h=1}^{\infty}$ for a finite set of integers $A$ . The central question is the extent to which this sequence determines the structural properties of $A$ , specifically its affine equivalence class. Two sets $A$ and $B$ are affinely equivalent if $B = \lambda A + \mu$ for rational $\lambda \neq 0$ and $\mu$ . Since affine transformations preserve sumset sizes ($|hA| = |hB|$ for all $h$ ), the sequence $(|hA|)$ is an affine invariant. The paper asks whether this invariant is sufficient to distinguish between affinely inequivalent sets of the same cardinality. Specifically, it explores:

Whether there exist affinely inequivalent sets $A$ and $B$ such that $|hA| = |hB|$ for all $h \geq 1$ .
The comparative growth rates of sumset sizes for inequivalent sets, including whether the inequality $|hA| < |hB|$ can reverse at specific thresholds.
The existence of "oscillating" behaviors where the relative order of sumset sizes changes multiple times as $h$ increases.

Methodology
The author employs a combination of structural analysis, explicit construction, and asymptotic estimation:

Direct Problem Foundations: The paper relies on established results (Theorems 1 and 2) stating that for sufficiently large $h$ , the sumset size $|hA|$ follows an arithmetic progression determined by the maximum element of $A$ and the genus of the associated numerical semigroup.
Explicit Constructions: To address inverse questions, the paper constructs specific families of sets. A primary class of examples involves sets of the form $A_{\ell, w} = [0, \ell] \cup \{w\}$ , where $[0, \ell]$ is an interval of integers and $w$ is an additional element.
Interval Overlap Analysis: The methodology for calculating $|hA_{\ell, w}|$ involves decomposing the $h$ -fold sumset into a union of intervals $I_j = jw + (h-j)[0, \ell]$ . The cardinality is determined by analyzing the overlap conditions between these intervals, which depend on the relationship between $h$ , $\ell$ , and $w$ .
Comparative Analysis: By varying the parameter $w$ (e.g., comparing $w$ and $w+1$ ), the paper derives exact formulas for $|hA|$ and $|hB|$ to demonstrate where and how their sizes diverge or coincide.

Key Contributions and Results

Non-Uniqueness of the Sumset Size Sequence:
The paper proves that the sequence $(|hA|)_{h=1}^{\infty}$ does not uniquely determine the affine equivalence class of $A$ .
- Theorem 4: For every integer $k \geq 3$ , there exist affinely inequivalent sets $A$ and $B$ with $|A| = |B| = k$ such that $|hA| = |hB|$ for all $h \geq 2$ .
- Construction: For $k=3$ , the sets $\{0, 2, 7\}$ and $\{0, 3, 7\}$ are shown to have identical sumset sizes for all $h$ . For $k \geq 4$ , sets of the form $\{0, 3, 5, 6\} \cup [8, k+3]$ and $\{0, 4, 5, 6\} \cup [8, k+3]$ serve as examples.
Exact Formulas for Specific Set Classes:
- Theorem 5: Provides exact formulas for the size of the sumset $|hA_{\ell, w}|$ where $A_{\ell, w} = [0, \ell] \cup \{w\}$ . The formula depends on whether $h$ is small (intervals are disjoint) or large (intervals overlap), defined by a threshold involving $w/\ell$ .
- Theorem 6: Specializes Theorem 5 for the case $\ell=1$ (sets of the form $\{0, 1, w\}$ ), relating the result to the genus of the numerical semigroup generated by $\{0, 1, w\}$ .
Controlled Divergence and Oscillations:
- Theorem 8: Demonstrates that for any $k \geq 3$ and any threshold $h_1 \geq 1$ , there exist sets $A$ and $B$ of size $k$ such that $|hA| = |hB|$ for all $h \leq h_1$ , but for all $h > h_1$ , $|hB| = |hA| + (h - h_1) > |hA|$ . This proves that one can construct sets that are indistinguishable by sumset size up to an arbitrary point, after which one strictly dominates the other.
- Oscillation Examples: The paper presents experimental data and theoretical constructions suggesting that sumset sizes can oscillate. It constructs pairs of sets where $|hA| > |hB|$ for small $h$ , $|hA| < |hB|$ for intermediate $h$ , and $|hA| > |hB|$ again for large $h$ (due to the asymptotic behavior dictated by the maximum element).
Generalized $\tau$ -Type Problems:
The paper introduces a framework for comparing $n$ -tuples of sets. It defines a normalization map $\tau$ that converts a tuple of integers into a tuple of ranks (e.g., $(3, 1, 2) \to (2, 1, 3)$ ).
- Problems 6–8: These open problems ask whether one can construct an $n$ -tuple of sets $(A_1, \dots, A_n)$ such that the relative ordering of their sumset sizes (encoded by $\tau(|hA|)$ ) follows a prescribed sequence of patterns as $h$ increases.

Significance and Open Problems
The paper establishes that the sequence of sumset sizes is a weak invariant; it cannot distinguish between all affinely inequivalent sets. While the asymptotic behavior is well-understood (eventually an arithmetic progression), the "small $h" behavior is complex and allows for significant flexibility in constructing sets with identical or oscillating growth profiles.

The author explicitly frames the work as the beginning of a "comparative additive number theory," noting that many problems remain open:

Problem 2 & 3: Can one construct sets where the inequality $|hA| > |hB|$ and $|hA| < |hB|$ alternates arbitrarily many times?
Problem 4: Can one construct sets where the inequality flips based on the parity of $h$ (odd vs. even) up to a certain bound?
Problem 6 & 7: Can one realize any prescribed sequence of relative orderings (normalizations) for an $n$ -tuple of sets?

The paper concludes by noting that Noah Kravitz recently proved a theorem (Theorem 9) answering some of these generalized oscillation questions affirmatively, confirming that for any finite sequence of desired orderings (and a final stable ordering), there exists a tuple of sets that realizes this sequence.