betaFeedback

WorksMathematics

Gaps in the Most Frequent Sizes of Integer Sumsets

Abstract

Nathanson observed that, for four-element sets AA of integers, the most frequent sizes of the iterated sumset hAhA are separated by triangular numbers. Senger proved this and suggested an analogue for larger sets. We establish this pattern for kk-element subsets of {1,…,q}\{1,\ldots,q\}, for every fixed k≥3k\geq3, where h≥2h\geq2 is either fixed or grows slower than q1/(2k−1)q^{1/(2k-1)}. As q→∞q\to\infty, almost every such set has the largest possible hh-fold sumset, and almost every exception has one of h−1h-1 explicit smaller sizes. The differences between consecutive sizes among these hh values are consecutive (k−2)(k-2)-dimensional simplex numbers.

Introduction

Let A⊂ZA \subset\mathbb{Z} be a finite subset. The sumset of AA is

A+A={a+a′:a,a′∈A}=2AA + A = \{a + a' : a,a' \in A\} = 2A

and its hh-fold sumset is

hA=(h−1)A+A={a+a′:a∈A, a′∈(h−1)A},hA = (h-1)A + A = \{a + a' : a \in A,\ a' \in(h-1)A\},

where 1A=A1A = A and repetition is allowed.

The size of hAhA has been studied in two complementary regimes. In the first, the set AA is fixed and h→∞h \to\infty. Nathanson [10] proved that if AA is a finite set of integers with min⁡A=0\min A = 0 and gcd⁡(A)=1\gcd(A) = 1, then for all sufficiently large hh, the integers in [0..hmax⁡A][0..h\max A] that are missing from hAhA form two finite sets, one near each endpoint of this interval, which do not depend on hh up to translation. In particular, ∣hA∣|hA| is eventually a linear function of hh. Khovanskii [Kho92] proved that for a finite subset AA of Zd\mathbb{Z}^d, ∣hA∣|hA| agrees with a polynomial in hh for all sufficiently large hh. Nathanson and Ruzsa [NR02] gave an elementary lattice-point proof of eventual polynomial growth for finite subsets of abelian semigroups. For finite subsets of Zd\mathbb{Z}^d, Granville, Shakan and Walker [5] gave effective bounds on how large hh must be. A finite set BB of integers is sum-dominant if ∣B+B∣>∣B−B∣|B+B| > |B-B|. In the study of such sets, Iyer, Lazarev, Miller and Zhang [7] determined the limiting behavior of hAhA for an arbitrary finite set AA as h→∞h \to\infty, together with a bound on how large hh must be for this behavior to appear. They also proved that no set AA has the property that A,2A,…,hAA, 2A, \ldots, hA are all sum-dominant for every hh.

In the second regime, which is the subject of this paper, hh is fixed or grows slowly with qq, and AA is a kk-element subset of {1,…,q}\{1,\ldots,q\} with q→∞q \to\infty. A kk-element set AA is a BhB_h-set when ∣hA∣|hA| attains the universal upper bound Mh,kM_{h,k} (see Definition 2.2). For h=2h=2 these are the Sidon sets, studied by Erdős and Turán [4], and Bose and Chowla [3] constructed large BhB_h-sets for every hh. We refer to O’Bryant’s survey [14] for the extensive literature on these sets. Nathanson [11] proved that almost all kk-element subsets of [q][q] are Sidon sets, even when kk grows with qq at a suitable rate. Random subsets of intervals are also central to the study of sum-dominant sets. Martin and O’Bryant [9] proved that a positive proportion of subsets of {0,…,n}\{0,\ldots,n\} are sum-dominant, and Hegarty and Miller [6] proved that when the elements of [q][q] are chosen independently with probability p(q)p(q) satisfying p(q)→0p(q) \to0 and qp(q)→∞qp(q) \to\infty, almost all sets have more differences than sums.

One particular approach has been to study the cardinalities of ∣hA∣|hA| for various values of hh. Nathanson [12 Problem 5] first studied the most frequent sizes of ∣hA∣|hA| for ∣A∣=4|A|=4 and observed triangular gaps between them. O’Bryant proved a formula for the initial sequence of sumset sizes in terms of the successive L1L^1-minima of a lattice and gave a heuristic explanation of the observed frequencies [15]. The fourth listed author studied this problem further, and proved this phenomenon to be true for k=4k=4 [16 Thm. 2]. He also suggested that for k>4k>4, analogous “champagnerpyramid” numbers would describe the sumset-size deficits [16 Sec. 4]. These are (k−1)(k-1)-dimensional simplex numbers, whose consecutive differences are (k−2)(k-2)-dimensional simplex numbers. We prove that this gap pattern holds for all fixed k≥3k \ge3 by generalizing the fourth author’s constructions, as we now explain.

For h≥0h \ge0, let

Xh,k={x=(x1,…,xk)∈Z≥0k:∑i=1kxi=h}.\mathcal{X}_{h,k}=\left\{\mathbf{x}=(x_1,\ldots,x_k)\in\mathbb{Z}_{\ge0}^k:\sum_{i=1}^{k}x_i=h\right\}.

We call elements of Xh,k\mathcal{X}_{h,k} sum vectors since by representing elements of A={a1<a2<⋯<ak}A=\{a_1<a_2<\cdots<a_k\} as A⃗=(a1,a2,…,ak)∈Z≥0k\vec{A}=(a_1,a_2,\ldots,a_k)\in\mathbb{Z}_{\ge0}^k we can produce any element of hAhA. We may redefine hAhA as

hA={x⋅A⃗:x∈Xh,k}.hA=\{\mathbf{x}\cdot\vec{A}:\mathbf{x}\in\mathcal{X}_{h,k}\}.

Let

Mh,k=∣Xh,k∣=(h+k−1k−1),M−1,k=0M_{h,k}=|\mathcal{X}_{h,k}|=\binom{h+k-1}{k-1},\qquad M_{-1,k}=0

be the maximum possible size of hAhA. We are ready to state our main result.

Theorem 1.1. Let k≥3k\ge3 be fixed, and let q→∞q\to\infty and h=h(q)≥2h=h(q)\ge2 with h=o(q1/k)h=o(q^{1/k}). For 0≤ℓ<h0\le\ell<h, let

Pℓ=Mh,k−Mℓ−1,k.P_\ell=M_{h,k}-M_{\ell-1,k}.

Then the following statements hold.

#{A∈([q]k):∣hA∣=Mh,k}=Θ(qk).(1)\#\left\{A\in\binom{[q]}{k}:|hA|=M_{h,k}\right\}=\Theta(q^k). \tag*{(1)}
#{A∈([q]k):∣hA∣∉{P0,…,Ph−1}}=O(h2k−2qk−2).(2)\#\left\{A\in\binom{[q]}{k}:|hA|\notin\{P_0,\ldots,P_{h-1}\}\right\}=O(h^{2k-2}q^{k-2}). \tag*{(2)}
#{A∈([q]k):∣hA∣=Pℓ}=Ω(qk−1h−ℓ+1).(3)\#\left\{A\in\binom{[q]}{k}:|hA|=P_\ell\right\}=\Omega\left(\frac{q^{k-1}}{h-\ell+1}\right). \tag*{(3)}

Accordingly, we show that the natural gaps between the most frequent sizes of ∣hA∣|hA| are of the form

(ℓ+k−2k−2),\binom{\ell+k-2}{k-2},

which specialize to the triangular numbers when k=4k=4.

Formalization

The results of this paper have been formalized in the Lean 4 proof assistant with the Mathlib library [2]. Part of the Lean code was written by Awan, and part was generated by Aristotle, the automated theorem prover developed by Harmonic [1]. Every proof, including the generated ones, is checked by the Lean kernel, with the one exception noted at the end of this paragraph. The formalization contains no sorry. It proves Lemmas 3.2, 3.4, 3.6, 5.3 and 5.6, Propositions 3.5, 5.4 and 5.7, Theorem 1.1 for fixed hh together with explicit versions of its three bounds, which hold once qq exceeds an explicit polynomial in hh and imply Theorem 1.1 as stated, Corollaries 4.1 and 5.1, Remark 5.2, and Examples 2.3, 3.3 and 3.7. In particular, it contains a proof of Lemma 5.3, for which we only cite Senger’s argument, and it proves Lemma 3.6 directly for every kk, without using O’Bryant’s theorem. For Remark 4.2, the formalization proves the conclusion of Corollary 4.1 for every q>70⋅2kk!h(2h+1)2k−2q>70\cdot2^k k!h(2h+1)^{2k-2}, which is 70 times the threshold stated there, and it checks the computation for (h,k)=(3,4)(h,k)=(3,4) and 16≤q≤5016\le q\le50 with native_decide, which relies on Lean’s compiler in addition to its kernel.

Acknowledgments

We thank the organizers of the Polymath Jr. research group whose efforts brought about this collaboration. This work was supported by the National Science Foundation under Grant DMS2341670.

Background

Throughout we assume familiarity with standard definitions and notation of additive and algebraic combinatorics; see, e.g., [TV06, Sta11].

For integers u≤vu \le v and q≥1q \ge1, we write

[u..v]={n∈Z:u≤n≤v},[q]=[1..q].[u..v] = \{n \in\mathbb{Z} : u \le n \le v\}, \qquad[q] = [1..q].

Definition 2.1. Let q≥k≥1q \ge k \ge1. The set of kk-element subsets of [q][q] is

([q]k)={A⊆[q]:∣A∣=k}.\binom{[q]}{k} = \{A \subseteq[q] : |A| = k\}.

For A∈([q]k)A \in\binom{[q]}{k}, we always list the elements of AA in increasing order, a1<a2<⋯<aka_1 < a_2 < \cdots< a_k, and we call

A⃗=(a1,a2,…,ak)∈[q]k\vec{A} = (a_1,a_2,\ldots,a_k) \in[q]^k

the set vector of AA.

The map A↦A⃗A \mapsto\vec{A} is injective, so we may count subsets of [q][q] by counting their set vectors in [q]k[q]^k.

Definition 2.2. Let A∈([q]k)A \in\binom{[q]}{k} and h≥1h \ge1. The set AA is a BhB_h-set if ∣hA∣=Mh,k|hA| = M_{h,k}. Following [16], an element n∈hAn \in hA is a collision in hAhA if nn can be written in at least two different ways as a sum of hh elements of AA listed in nondecreasing order.

For instance, a1+a2a_1+a_2 and a2+a1a_2+a_1 are not two different ways of writing an element of 2A2A, since only a1+a2a_1+a_2 is listed in nondecreasing order. A sum of hh elements of AA listed in nondecreasing order is determined by the number of times each aia_i occurs in it, that is, by a sum vector in Xh,kX_{h,k}. Hence nn is a collision in hAhA exactly when n=x⋅A⃗=y⋅A⃗n = \mathbf{x} \cdot\vec{A} = \mathbf{y} \cdot\vec{A} for distinct x,y∈Xh,k\mathbf{x},\mathbf{y} \in X_{h,k}. Consequently, AA is a BhB_h-set if and only if hAhA has no collisions, that is, if and only if the map x↦x⋅A⃗\mathbf{x} \mapsto\mathbf{x} \cdot\vec{A} is injective on Xh,kX_{h,k}.

References

  1. [1][A+25] Tudor Achim et al., Aristotle: IMO-level automated theorem proving, 2025, arXiv:2510.01346.arxiv.org/abs/2510.01346
  2. [2][Awa26] Saad A. Awan, Lean 4 formalization of "Gaps in the most frequent sizes of integer sumsets", https://github.com/sawan201/PolyMathJr_MSTD, 2026, Commit b1c796e.
  3. [3][BC62] R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962), 141–147.DOI
  4. [4][ET41] Paul Erdős and Paul Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215.
  5. [5][GSW23] Andrew Granville, George Shakan, and Aled Walker, Effective results on the size and structure of sumsets, Combinatorica 43 (2023), no. 6, 1139–1178.arxiv.org/abs/2105.09181
  6. [6][HM09] Peter Hegarty and Steven J. Miller, When almost all sets are difference dominated, Random Structures Algorithms 35 (2009), no. 1, 118–136.arxiv.org/abs/0707.3417
  7. [7][ILMZ12] Geoffrey Iyer, Oleg Lazarev, Steven J. Miller, and Liyang Zhang, Generalized more sums than differences sets, J. Number Theory 132 (2012), no. 5, 1054–1073.arxiv.org/abs/1108.4500
  8. [9]Greg Martin and Kevin O’Bryant, Many sets have more sums than differences, Additive Combinatorics, CRM Proc. Lecture Notes, vol. 43, Amer. Math. Soc., Providence, RI, 2007, pp. 287–305.arxiv.org/abs/math/0608131
  9. [10]Melvyn B. Nathanson, Sums of finite sets of integers, Amer. Math. Monthly 79 (1972), 1010–1012.DOI
  10. [11]———, On the ubiquity of Sidon sets, Number Theory (New York, 2003), Springer, New York, 2004, pp. 263–272.arxiv.org/abs/math/0304496
  11. [12]———, Triangular and tetrahedral number differences of sumset sizes in additive number theory, Integers 26A (2026), Paper No. A18.
  12. [14]Kevin O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin. DS11 (2004), Dynamic Survey.DOI
  13. [15]———, On Nathanson’s triangular number phenomenon, Integers 26A (2026), Paper No. A19.
  14. [16]Steven Senger, Triangular gaps in the most frequent sizes of hA for |A| = 4, 2025, arXiv:2511.03008.

Paper details

vlnc:W_hxrg29y9
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 21

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents