Triangular and tetrahedral number differences of sumset sizes in additive number theory

Melvyn B. Nathanson · 2025

Read Triangular and tetrahedral number differences of sumset sizes in additive number theory by Melvyn B. Nathanson (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-2506-15015.txt.

Introduction

Melvyn Nathanson studies sumset sizes in additive number theory in a 2025 paper on sums of finite integer sets. Past work focused on sets with very small sumsets or very large ones, leaving the middle range open.

Nathanson looks at the full spread of sumset sizes for finite sets. For sets of size four, an unexpected pattern appears in which sizes are popular. The pattern ties to triangular and tetrahedral numbers, classic figurate counts. The result shows hidden order in a range long treated as messy. Number theorists get a new structural clue about how set sums grow, with a link between plain counting shapes and sum popularity.

Catalog record

CREATORMelvyn B. Nathanson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-15015

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Triangular and tetrahedral number differences of sumset sizes in additive number theory Thanks: Supported in part by PSC-CUNY Research Award Program grant 66197-00 54. Melvyn B. Nathanson Abstract . The study of sums of finite sets of integers has mostly concentrated on sets with very small sumsets (Freiman’s theorem and related work) and on sets with very large sumsets (Sidon sets and B h B_{h} -sets). This paper considers the full range of sumset sizes of finite sets of integers and an unexpected pattern (related to the triangular and tetrahedral numbers) that appears in the distribution of popular sumset sizes of sets of size 4. 2000 Mathematics Subject Classification 11B05, 11B13, 11B30,11B34, 11B75 1. The sumset size problem The integer interval [u,v] is the set of all integers n such that u\leq n\leq v . The h -fold sum of a set A of integers is the set hA of all sums of h not necessarily distinct elements of A : hA=\left\{a_{1}+\cdots+a_{h}:a_{i}\in A\text{ for all }i\in[1,h]\right\}. It is a fundamental unsolved problem in additive number theory, and a problem that strangely seems not to have been previously investigated, to compute and understand the sumset sizes of finite sets of integers. 1 1 1 This problem was discussed at three recent number theory conferences (Integers 2025 in Athens, Georgia, CANT 2025 in New York, and BIRS-IMAG in Granada, Spain) and no one could cite earlier work. References to previous papers would be appreciated. For all positive integers h and k , we define the range of sumset sizes \mathcal{R}_{\mathbf{Z}}(h,k)=\left\{|hA|:A\subseteq\mathbf{Z}\text{ and }|A|=k\right\}. This set was introduced in Nathanson [ 7 ] and studied in [ 8 , 10 , 11 ] . The idea of “sumset” is central in additive number theory and suggests many simple but a priori difficult questions. For example, does there exist a set A of size |A|=11 whose 7 -fold sum has size |7A|=15551 ? The answer is “yes,” and the set A_{0}=\{0,897,2056,2441,2988,3259,5294,6506,8013,9391,9872\} has the desired sumset sum. However, the answer was obtained by cheating: I started with the set A_{0} and computed its 7 -fold sum. For this set A_{0} , Maple quickly calculated the sumsets hA_{0} and the sumset sizes |hA_{0}| for h\in[1,7] . The second line of the following table gives the sequence of sumset sizes |hA_{0}| . The maximum size of an h -fold sumset of a set of size k is \binom{h+k-1}{h} . The third line of the table gives the maximum size of an h -fold sumset of a set A of size 11 for h\in[1,7] . h 1 2 3 4 5 6 7 |hA_{0}| 11 66 285 986 2878 7226 15551 \max|hA| 11 66 286 1001 3003 8008 19448 A B_{h} -set is a set A of integers such that every integer in the h -fold sumset hA has a unique representation as a sum of h increasing elements of A . If A has size k , then A is a B_{h} -set if and only if |hA|=\binom{h+k-1}{h} . A B_{2} -set is also called a Sidon set. We see from the table above that A_{0} is a Sidon set. Every B_{3} -set of size 11 satisfies |3A|=286 , but the special set A_{0} has |3A_{0}|=285 , and so is not a B_{3} -set. Moreover, there must be exactly one integer n_{0} that has two representations as a sum of three elements of A_{0} and no integer that has more than two representations as a sum of three elements of A_{0} . We have n_{0}=18782=0+9391+9391=897+8013+9872\in 3A_{0}. There are many related questions. The maximum size of a 7-fold sumset of a set of 10 integers is \binom{16}{7}=11440 . It follows that if A is a set of integers with |7A|=15551 , then |A|\geq 11 . What is the cardinality of the largest set A such that |7A|=15551 ? Sets A and B are affinely equivalent if there are numbers \lambda\neq 0 and \mu such that B=\lambda\ast A+\mu=\{\lambda a+\mu:a\in A\}. Affinely equivalent sets have the same sumset sums. Sets A and B are affinely inequivalent if they are not affinely equivalent. How many affinely inequivalent sets A satisfy |A|=11 and |7A|=15551 ? How many affinely inequivalent finite sets A satisfy |7A|=15551 ? The computation complexity inequality ( 2 ) implies that all these questions can be answered in finite time. We have \max\mathcal{R}_{\mathbf{Z}}(h,k)=\binom{h+k-1}{k-1} and sets with this sumset size ( B_{h} -sets and Sidon sets) have been extensively studied ( [ 5 , 6 , 9 , 12 ] ). Similarly, \min\mathcal{R}_{\mathbf{Z}}(h,k)=h(k-1)+1 and sets with this sumset size (called arithmetic progressions) and sets with very small sumset size have also been extensively studied (Freiman’s theorem and related work [ 4 , 16 ] ). Thus, (1) \mathcal{R}_{\mathbf{Z}}(h,k)\subseteq\left[h(k-1)+1,\binom{h+k-1}{k-1}\right]. Because the set \mathcal{R}_{\mathbf{Z}}(h,k) is finite, we can define the integer N(h,k) as the smallest integer N such that \mathcal{R}_{\mathbf{Z}}(h,k)=\{|hA|:A\subseteq[0,N-1]\text{ and }|A|=k\}. The integer N(h,k) determines the computational complexity of the sumset size problem. It is proved in [ 11 ] that, for all h\geq 3 and k\geq 3 , (2) N(h,k)<4(8h)^{k-1}. Thus, for fixed k , the set \mathcal{R}_{\mathbf{Z}}(h,k) can be computed in polynomial time. Here are some simple results. For all h and k , \mathcal{R}_{\mathbf{Z}}(h,1)=\{1\},\quad\mathcal{R}_{\mathbf{Z}}(1,k)=\{k\},\qand\mathcal{R}_{\mathbf{Z}}(h,2)=\{h+1\}. For all k , the set \mathcal{R}_{\mathbf{Z}}(2,k) is the interval of integers: \mathcal{R}_{\mathbf{Z}}(2,k)=\left[2k-1,\binom{k+1}{2}\right]. However, the set \mathcal{R}_{\mathbf{Z}}(3,3) is not an interval of integers. We have \mathcal{R}_{\mathbf{Z}}(3,3)\subseteq\left[7,10\right] but \mathcal{R}_{\mathbf{Z}}(3,3)=\{7,9,10\}. The number 8 missing. For k=3 and all h\geq 1 , Nathanson [ 7 ] proved that \mathcal{R}_{\mathbf{Z}}(h,3)=\left\{\binom{h+2}{2}-\binom{t}{2}:t\in[1,h]\right\}. and so |\mathcal{R}_{\mathbf{Z}}(h,3)|=h . Problem 1 . For k=4 , we have \mathcal{R}_{\mathbf{Z}}(h,4)\subseteq\left[3h+1,\binom{h+3}{3}\right]. Compute \mathcal{R}_{\mathbf{Z}}(h,4) for all positive integers h . Problem 2 . For all positive integers h and k , compute the set of sumset sizes \mathcal{R}_{\mathbf{Z}}(h,k) . Explain the integers “missing” from the interval on the right side of ( 1 ). This is a core problem in additive number theory. Problem 3 . Let k\geq 4 . Prove that “most” numbers in the interval on the right side of ( 1 ) are not sumset sizes, that is, prove that \left|\mathcal{R}_{\mathbf{Z}}(h,k)\right|=o_{k}\left(h^{k-1}\right) or, better, that \left|\mathcal{R}_{\mathbf{Z}}(h,k)\right|=O_{k}\left(h^{k-2}\right). Problem 4 . Is there some kind of relation or reciprocity between the sets \mathcal{R}_{\mathbf{Z}}(h,k) and \mathcal{R}_{\mathbf{Z}}(k,h) ? For example, is there a function f:\mathbf{N}\rightarrow\mathbf{N} such that, if t\in\mathcal{R}_{\mathbf{Z}}(h,k) , then f(t)\in\mathcal{R}_{\mathbf{Z}}(k,h) ? Is there a function g:\mathbf{N}\rightarrow\mathbf{N} such that t\in\mathcal{R}_{\mathbf{Z}}(h,k) if and only if g(t)\in\mathcal{R}_{\mathbf{Z}}(k,h) ? Are there functions \alpha,\beta,\gamma such that, if t\in\mathcal{R}_{\mathbf{Z}}(h,k) , then \gamma(t)\in\mathcal{R}_{\mathbf{Z}}(\alpha(h),\beta(k)) ? For related work on “sumset size races,” see [ 2 , 3 , 13 ] . 2. 5-fold sums of sets of size 4 In this section we describe some computational experiments on 5-fold sumsets of sets of size 4. The calculations were programmed in Maple. Experiment 1. Let q=100 . There are \binom{100}{4}=3,921,225 subsets of size 4 contained in the integer interval [0,q-1] . Their 5-fold sumsets are contained in [16,56] . For all t\in[16,56] , let S(t) denote the number of sets A\subseteq[0,q-1]=[0,99] such that |A|=4 and |5A|=t . The following table records the distribution of sumset sizes. t S(t) t S(t) t S(t) 16 1617 30 4655 44 10574 17 0 31 3444 45 18862 18 0 32 5273 46 450320 19 0 33 1906 47 6706 20

Read the complete text