Triangular gaps in the most frequent sizes of h A hA for | A | = 4 |A|=4
Steven Senger · 2025
Read Triangular gaps in the most frequent sizes of h A hA for | A | = 4 |A|=4 by Steven Senger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03008.txt.
Introduction
Steven Senger explains a pattern seen in experiments on sumsets, sets built by adding a fixed set to itself many times. Take a random four-element set of whole numbers and form all sums of h of its elements. Some sizes for the resulting sumset occur far more often than others, and the popular sizes show triangular gaps. His 2025 paper explains where those gaps come from.
The analysis covers the case where the pool of numbers is much larger than the number of summands. Sumset size is a basic measure in additive combinatorics, tied to how much internal structure a set has. Experimental patterns like these gaps can mislead if taken at face value, so a proof that explains them helps separate real structure from sampling quirks.
Catalog record
| CREATOR | Steven Senger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-03008
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Triangular gaps in the most frequent sizes of h A hA for | A | = 4 |A|=4 Steven Senger Abstract . We explain the triangular gaps observed experimentally in the most popular sizes of the h h -fold iterated sumset, h A , hA, when A A is a randomly chosen four-element subset of the first q q natural numbers, for q q much larger than h . h. 1. Introduction It is well-known that for sufficiently large q, “most” subsets of [1..q] are B_{h} -sets for parameters h taken to be much smaller than q. Mel Nathanson made this precise in [ 3 ] . At the 2025 meeting of the Combinatorial and Additive Number Theory (CANT) conference, he also observed computationally that for a fixed q, the most frequent sizes hA, where A is a four-element subset of [1..q], were separated by consecutive triangular numbers. See his work in [ 4 ] and see [ 2 ] by Kevin O’Bryant for significant insight into this problem and related problems. The primary goal of this note is to offer a relatively simple explanation for the triangular gap phenomenon, based on some combinatorial estimates. We also present a few related arguments which may be of independent interest. 1.1. Notation When u,v\in\mathbf{Z}, define the integer interval [u..v]=\{n\in\mathbf{Z}:u\leq n\leq v\}\text{ and }[v]:=[1..v]. Let A be a finite set of integers and let hA:=A+A+\dots+A with h copies of A to be the h -fold sumset of A . Notice that if A\subseteq[a,b] , then hA\subseteq[ha,hb] . Next, use \binom{[q]}{k} to denote the set of all k -element subsets of the integer interval [1..q] . Then \left|\binom{[q]}{k}\right|=\binom{q}{k}=\frac{q^{k}}{k!}+O\left(q^{k-1}\right). Let \mathcal{X}_{h,k} be the set of all k -tuples \mathbf{x}=(x_{1},\ldots,x_{k}) of nonnegative integers such that \sum_{i=1}^{k}x_{i}=h . We define the number M_{h,k} to be M_{h,k}:=|\mathcal{X}_{h,k}|=\binom{h+k-1}{k-1}=\frac{h^{k-1}}{(k-1)!}+O_{k}\left(h^{k-2}\right). The support of the vector \mathbf{x}=(x_{1},\ldots,x_{k})\in\mathcal{X}_{h,k} is the set \support(\mathbf{x})=\{i\in[1..k]:x_{i}\geq 1\}. For A=\{a_{1},\ldots,a_{k}\}\in\binom{[q]}{k} and n\in\mathbf{Z} , the representation function r_{A,h}(n) counts the number of representations of n as a sum of h elements of A . Equivalently, writing \vec{A}=(a_{1},\ldots,a_{k})\in\mathbf{N}_{0}^{k} , we have r_{A,h}(n)=\left|\left\{\mathbf{x}\in\mathcal{X}_{h,k}:\mathbf{x}\cdot\vec{A}=n\right\}\right|. The set A\in\binom{[q]}{k} is a B_{h} -set if r_{A,h}(n)=0 or 1 for all integers n . Let \mathcal{B}_{h,k}(q) be the set of all k -element B_{h} -sets in the interval [1..q] . For all positive integers k we have \binom{[q]}{k}=\mathcal{B}_{1,k}(q)\supseteq\cdots\supseteq\mathcal{B}_{h,k}(q)\supseteq\mathcal{B}_{h+1,k}(q)\supseteq\cdots. One central object of our study will be the set of B_{h} -sets that are not B_{h+1} -sets, which we denote by \mathcal{B}^{*}_{h,k}(q). That is, \mathcal{B}^{*}_{h,k}(q)=\mathcal{B}_{h,k}(q)\setminus\mathcal{B}_{h+1,k}(q). Given sets A,B\subseteq\mathbf{N}, if a,b,c,d\in A are (not necessarily distinct) elements chosen so that \{a,b\}\neq\{c,d\}, and a+b=c+d, then we notice that the sumset A+A will be strictly smaller than M_{2,|A|}. We call this a collision in A+A . We similarly define collisions in hA to be cases where some element of hA can be written as two sums of h elements of A that are not merely permutations of one another. For example, a+b+c=3d is a collision, but a+2b=b+a+b is not. The “triangular gaps” appear in the frequency of the sizes of hA because this phenomenon happens at different values of h for different sets A. To describe this, we introduce some terminology. If we fix h\geq 2, we will call a potential h -fold iterated sumset size h -frequent if it occurs \Omega(h^{-5}q^{3}) times, or h -rare if it occurs O(h^{13}q^{2}) times. 1.2. Main results Essentially, the argument is that for appropriate choices of q and h, we can show that the maximum possible sumset size M_{h,4} occurs most often, for \Theta(q^{4}) choices of A\in\binom{[q]}{4}, and that the smaller iterated sumset sizes occur frequently ( \Theta(q^{3}) times) when they are a triangular gap away from the previous frequent size, and rarely ( O(q^{2}) times) otherwise. We do this by giving upper and lower bounds on the sizes of B_{\ell,4}^{*}(q) for relevant choices of \ell, as well as giving upper and lower bounds on the iterated sumset sizes for subsets of B_{\ell,4}^{*}(q) that are frequent and rare. Specifically, we show that for most A\in B_{\ell,4}^{*}(q), we will have |(h+\ell)A|=M_{h,4}-\binom{\ell+2}{3}, which gives rise to the triangular gaps, and we will show that the exceptional choices are comparatively uncommon. The first result is a technical lemma that allows us to estimate the number of B_{h} -sets that fail to be B_{h+1} -sets, as well as the number of such sets that have more than one collision. Specifically, it tells us that for sets in \mathcal{B}_{h,4}^{*}(q), the iterated sumset size M_{h,4}-1 is h -frequent, while smaller sizes are h -rare. Most of the proof relies on highly geometric arguments. These are postponed until Section 3 . Lemma 1 . Given q sufficiently large with respect to h\geq 2, we have (i)~~|\mathcal{B}^{*}_{h,4}(q)|=O\left(h^{7}q^{3}\right), (ii)~~|\mathcal{B}^{*}_{h,4}(q)|=\Omega\left(h^{-5}q^{3}\right),\text{ and } (iii)~~\left|\{A\in\mathcal{B}^{*}_{h,4}(q):|(h+1)A|\leq M_{h+1,4}-2\}\right|=O\left(h^{13}q^{2}\right). Specifically, we will use this lemma to prove the following theorem. The first statement in it is a fairly direct corollary, and will be crucial to explaining the triangular gaps. The second statement is already known, as can be seen in far greater generality in [ 5 ] by Nathanson, but we include it as it is a direct consequence of the rest of the argument. Theorem 1 . Suppose q is sufficiently large with respect to h\geq 2. For A\in\binom{[q]}{4} iterated sumset size M_{h,4} occurs \Theta(q^{4}) times and the size M_{h,4}-1 occurs \Omega(h^{-5}q^{3}) and O(h^{13}q^{3}) times. Moreover, the proportion of B_{h} -sets in \binom{[q]}{4} is increasing in q. To see how these results relate to the observed triangular gaps between popular iterated sumset sizes, we prove the following. It shows that if a B_{h} -set fails to be a B_{h+1} -set, then we have a straightforward upper bound for the sizes of subsequent iterated sumsets. Lemma 2 . For A\in\mathcal{B}_{h,4}^{*}(q), we have |(h+\ell)A|\leq M_{h+\ell,4}-{\ell+2\choose 3}. We combine this lemma with some of the arguments in the proof of Theorem 1 to obtain the following quantitative characterization of the triangular gap phenomenon. Theorem 2 . Suppose q is sufficiently large with respect to h\geq 2, and \ell<h. The numbers of elements of \binom{[q]}{4} with sizes of the form M_{h,4}-{\ell+2\choose 3}, are \Omega(h^{-5}q^{3}) , and the numbers of elements with sizes between those are O(h^{13}q^{2}). This gives us that for appropriate choices of h,\ell and q, the iterated sumset sizes M_{h,4},M_{h,4}-1,M_{h,4}-4,M_{h,4}-10,M_{h,4}-20,\dots,M_{h,4}-{\ell+2\choose 3} must all be h -frequent while the sizes between them must be h -rare. As this sequence is just M_{h,4} with successive tetrahedral numbers subtracted, the adjacent terms will have differences equal to the gaps between adjacent tetrahedral numbers, which are consecutive triangular numbers. This shows that the gaps between the largest h sumset sizes that are h -frequent must be triangular. The basic idea will be to prove the main results in Section 2 . This section is largely additive combinatorics, and will assume Lemma 1 (i) and (iii) . In Section 3 , we give a fairly geometric proof of Lemma 1 (i) and (iii) , and related results. We conclude with a discussion on generalizations to larger set sizes in Section 4 . 1.3. Acknowledgments The author would like to thank Mel Nathanson for simplifying and generalizing numerous parts of this note, particularly for Lemma 5 , Kevin O’Bryant for pointing out a crucial error in an earlier draft, and both of them