🔢 mathematics

On the size of $h$ -fold sumsets

This paper derives an exact formula for the size of the $h$ -fold sumset of a finite set of integers and establishes necessary and sufficient conditions for a specific set structure to yield a closed-form expression involving truncated binomial coefficients, thereby generalizing a previous result by Nathanson.

Original authors: Shi-Qiang Chen, Quan-Hui Yang

Published 2026-08-03

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Shi-Qiang Chen, Quan-Hui Yang

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 you are a chef trying to figure out how many different flavors of soup you can make. You have a specific pantry of ingredients, say a bag of potatoes, a jar of spices, and a block of cheese. If you decide to make a "two-ingredient soup," you can mix any two items from your pantry (potato + potato, potato + spice, spice + cheese, etc.). If you make a "three-ingredient soup," you mix three items. In the world of mathematics, this is called an additive number theory problem. Instead of soup, mathematicians look at sets of numbers. They ask: if I take a set of numbers and add them together $h$ times (where $h$ is any positive integer), how many unique total sums can I create?

This isn't just a game of arithmetic; it's about understanding the hidden structure of numbers. Sometimes, adding numbers together creates a smooth, predictable pattern, like a perfectly straight line. Other times, the results are messy and full of gaps. For decades, mathematicians have been trying to write down a perfect "recipe" (a formula) that tells them exactly how many unique sums exist for any given set of numbers and any number of additions. While they knew the answers for very small sets (like sets with just two or three numbers), the moment they tried to add a fourth number to the mix, the math got incredibly complicated, and the simple recipes stopped working.

This paper, written by Shi-Qiang Chen and Quan-Hui Yang, steps into that messy kitchen to tidy up a specific corner. The authors focus on a special type of number set: one that starts with a nice, consecutive run of numbers (like 0, 1, 2, 3...), followed by two larger, specific numbers. They wanted to know: under what exact conditions can we write a simple, clean formula to predict the number of unique sums?

The team discovered that the answer depends entirely on the relationship between those two larger numbers. They proved that a simple, explicit formula works perfectly if and only if the larger numbers fit together in a very specific way—either the remainder when one is divided by the other is zero, or they are large enough relative to the starting run of numbers. If these conditions aren't met, the simple formula breaks down, and the number of sums becomes much harder to pin down.

To solve this, the authors used a clever mathematical tool called a generating function. You can think of this as a magical machine that takes a list of numbers and turns them into a polynomial (a fancy algebraic expression). By watching how this machine behaves, the authors could "see" the patterns of the sums without having to add them up one by one. They found that when their specific conditions were met, the machine produced a result that could be described using "truncated binomial coefficients"—a way of counting combinations that stops counting once you hit a certain limit.

The paper doesn't just guess; it provides a rigorous proof. The authors first established a general rule that works for any finite set of numbers, no matter how messy. Then, they applied this rule to their specific sets to show exactly when the math simplifies. They also demonstrated that if you try to use their simple formula in cases where the conditions aren't met, it fails. In other words, they didn't just find a shortcut; they proved exactly where the shortcut exists and where you have to take the long, winding road. This work builds on previous findings by mathematician Melvyn Nathanson, extending his results from smaller sets to this more complex four-number scenario, giving us a clearer map of how numbers behave when they are added together repeatedly.

Technical Summary: On the Size of h-Fold Sumsets

Problem Statement
The paper addresses the fundamental problem in additive number theory of determining the exact cardinality $|hA|$ of the $h$ -fold sumset of a finite set of integers $A$ . While classical extremal bounds exist (the lower bound attained by arithmetic progressions and the upper bound by sets with unique representations), the precise structure of $|hA|$ for intermediate cases remains complex. The authors specifically focus on sets of the form $A = \{0, 1, \dots, s, a, b\}$ with $1 \le s < a < b$ . This work is motivated by recent open problems posed by Nathanson (2025) regarding the structure of sumsets for four-element sets and the computation of the set of sumset sizes $R(h, 4)$ .

Methodology
The authors employ a combination of structural analysis of the shortest representation function and generating functions.

Shortest Representation Function ( $\ell_A$ ): The core tool is the function $\ell_A(n)$ , defined as the minimum number of elements from $A$ required to sum to $n$ . An integer $n$ belongs to the sumset $hA$ if and only if $\ell_A(n) \le h$ .
Modular Decomposition: The set $A$ is normalized such that $A = \{0 = a_0 < a_1 < \dots < a_k = m\}$ with $\gcd(a_1, \dots, a_k) = 1$ . The authors analyze $\ell_A$ by decomposing integers $n$ into $n = tm + v$, where $0 \le v < m$ . They define auxiliary functions $M_t(v)$ based on the minimum of linear combinations modulo $m$ , which allows them to characterize the "records" of the representation length.
Generating Functions: For the specific case of $A = \{0, 1, \dots, s, a, b\}$ , the authors utilize generating functions to count the number of representable integers. They derive a polynomial $P_{s,N}(z)$ related to the ceiling function $\lceil x/s \rceil$ and use it to express the generating function for the size of the sumset.
Truncated Binomial Coefficients: The final formulas are expressed using truncated binomial coefficients $\binom{x}{j}$ , defined as $\binom{x}{j}$ if $x \ge j$ and $0$ otherwise.

Key Contributions and Results

General Exact Formula (Theorem 1): The paper establishes an exact formula for $|hA|$ for any finite normalized set $A$ . The formula is a summation over residues $v \in [0, m-1]$ involving the "record" values of the shortest representation function. Specifically, it expresses $|hA|$ as a sum of truncated binomial coefficients of degree 1, determined by the finite strict records of the function $M_t(v)$ .
Explicit Formula for $\{0, 1, \dots, s, a, b\}$ (Theorem 2): The authors derive a definitive explicit formula for $|hA|$ when $A = \{0, 1, \dots, s, a, b\}$ . Letting $b = qa + r$ with $0 \le r < a$ , the size is given by:
$|hA| = \sum_e p_{a,e} \left[ \binom{h-e+3}{3} - \binom{h-q-e+3}{3} \right] + \sum_e p_{r,e} \binom{h-q-e+2}{2}$
where $p_{N,e}$ are coefficients derived from the polynomial $P_{s,N}(z)$ .
Necessary and Sufficient Conditions: A critical contribution is the proof that the above explicit formula holds for all positive integers $h$ $h$ if and only if $r = 0$ or $qs + r \ge a$ .
- If these conditions are met, the structure of the sumset is regular enough to be captured by the polynomial formula for all $h$ .
- If the conditions fail (i.e., $r > 0$ and $qs + r < a$), the formula fails for specific values of $h$ (specifically $h = q+1$ ), as the set of representable integers includes elements that the formula does not account for.
Corollary for Four-Element Sets: By setting $s=1$ , the authors provide a six-term explicit formula for $|h\{0, 1, a, b\}|$ , valid if and only if $r=0$ or $q+r \ge a$ .

Significance and Claims
The paper claims to generalize a result by Nathanson. Specifically, Nathanson previously identified a family of four-element sets where the sumset size follows a specific pattern. This work extends that understanding by:

Providing a general framework (Theorem 1) applicable to any finite normalized set, thereby offering a theoretical solution to the structural questions raised in Nathanson's Problem 1 and Problem 2.
Precisely characterizing the boundary conditions under which a simple, closed-form expression (in terms of truncated binomial coefficients) exists for the sumset size of sets with a specific "almost arithmetic" structure.
Demonstrating that outside the "regular range" defined by the condition $r=0$ or $qs+r \ge a$ , the arithmetic structure of the sumset becomes irregular, and the simple formula fails, necessitating the use of the more complex general formula from Theorem 1.

The authors do not claim to solve the general problem of computing $R(h, 4)$ (the set of all possible sumset sizes for 4-element sets) completely, but rather provide the necessary tools and specific exact formulas for a significant subclass of these sets, clarifying when simple formulas are applicable and when they are not.

Technical Summary: On the Size of h-Fold Sumsets

More like this