Possible Sizes of Sumsets

Isaac Rajagopal · 2025

Read Possible Sizes of Sumsets by Isaac Rajagopal (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-2510-23022.txt.

Introduction

Isaac Rajagopal studies which sizes a repeated sumset can take, a question in additive number theory. Start with a set of k whole numbers and add h picks from it in all ways. Nathanson asked what counts of distinct sums can occur for general h and k, building on work by Erdos and Szemeredi for the two-fold case.

Rajagopal proves that once k passes a bound that depends only on h, nearly every size in the full range occurs. Only a small named set of sizes is missing. For three-fold sums he shows the bound can be as low as two, settling the shape in that case.

Catalog record

CREATORIsaac Rajagopal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-23022

Browse the full library · About the Tower of Babel

Full text

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

Possible Sizes of Sumsets Isaac Rajagopal Abstract . Nathanson introduced the range of cardinalities of h h -fold sumsets ℛ ⁡ ( h , k ) ≔ { | h ​ A | : A ⊂ ℤ ​ and ​ | A | = k } . \mathcal{R}(h,k)\coloneq\{|hA|:A\subset\mathbb{Z}\text{ and }|A|=k\}. Following a remark of Erdős and Szemerédi that determined the form of ℛ ⁡ ( h , k ) \mathcal{R}(h,k) when h = 2 h=2 , Nathanson asked what the form of ℛ ⁡ ( h , k ) \mathcal{R}(h,k) is for arbitrary h , k ∈ ℕ h,k\in\mathbb{N} . For h ∈ ℕ h\in\mathbb{N} , we prove there is some constant k h ∈ ℕ k_{h}\in\mathbb{N} such that if k > k h k>k_{h} , then ℛ ⁡ ( h , k ) \mathcal{R}(h,k) is the entire interval [ h ​ k − h + 1 , ( h + k − 1 h ) ] \left[hk-h+1,\binom{h+k-1}{h}\right] except for a specified set of ( h − 1 2 ) \binom{h-1}{2} numbers. Moreover, we show that one can take k 3 = 2 k_{3}=2 . \dth@everypar = 1. Introduction Let A\subset\mathbb{Z} be a set of integers. For h\in\mathbb{N} , write hA\coloneq\{a_{1}+\cdots+a_{h}:a_{i}\in A\} to denote the h -fold sumset of A . Note that the a_{i} need not be distinct. Nathanson defined the set \mathcal{R}(h,k) of the possible sizes of these h -fold sumsets when |A|=k . Definition 1.1 ( [ Nat24 ] ) . Let h,k\in\mathbb{N} . Define the range of cardinalities of h -fold sumsets \mathcal{R}(h,k)\coloneq\{|hA|:A\subset\mathbb{Z}\text{ and }|A|=k\}. Nathanson [ Nat24 ] posed the problem of determining the exact values in \mathcal{R}(h,k) for arbitrary h,k\in\mathbb{N} . In this paper, we will determine the form of \mathcal{R}(h,k) for fixed h\in\mathbb{N} and large k , and for h=3 and all k\in\mathbb{N} , specifically answering Nathanson’s Problems 8 and 9 in [ Nat24 ] . The first work related to \mathcal{R}(h,k) was by Erdős and Szemerédi [ ES83 ] , who remarked that “it is easy to see that” \mathcal{R}(2,k)=\left[2k-1,\binom{k+1}{2}\right] for all k\in\mathbb{N} . Nathanson [ Nat24 ] determined the exact form of \mathcal{R}(h,3) for any h\in\mathbb{N} . Nathanson’s recent program has involved finding specific values in \mathcal{R}(h,k) and studying the frequency with which certain sumset sizes show up, with particular attention to k=4 [ Nat24 , Nat25a , Nat25b , Nat25c , Nat25d , O’B25 ] . With fixed h>2 and k increasing, the problem of determining \mathcal{R}(h,k) remained fully open. For real numbers a and b , let [a,b] denote the interval of integers from \mathopen{}\left\lceil a\right\rceil\mathclose{} to \lfloor b\rfloor , including endpoints. It is not hard to show [ Nat96 , Theorem 1.3] that (1.1) \mathcal{R}(h,k)\subseteq\left[hk-h+1,\binom{h+k-1}{h}\right], and that \mathcal{R}(h,k) includes the endpoints of this interval. Let m=hk-h+1 . Nathanson [ Nat24 , Theorem 7] found a gap in this interval, showing that m+1\not\in\mathcal{R}(h,k) for h>2 . Schinina [ Sch25 ] extended this to find that there are no elements of \mathcal{R}(h,k) in [m+1,m+h-2] . We extend this interval to a set of \min(h,k)-2 intervals, which we call \Delta_{h,k} because they geometrically form a triangle when h\leq k , as shown in Figure 1 . Definition 1.2 . Let m=hk-h+1 . Then define \Delta_{h,k}\coloneq\bigcup_{\ell=0}^{\min(h,k)-3}[m+\ell h+1,m+\ell h+(h-2-\ell)]. Theorem 1.3 . For all h,k\in\mathbb{N} , we have \mathcal{R}(h,k)\cap\Delta_{h,k}=\emptyset. 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 \vdots \vdots \vdots 920 921 922 923 924 Figure 1. We trivially have \mathcal{R}(6,7)\subseteq[37,924] . Schinina’s theorem shows that there are no elements of \mathcal{R}(6,7) on the red line. The gray triangle represents the numbers in \Delta_{6,7} , and Theorem 1.3 shows that there are no elements of \mathcal{R}(6,7) in \Delta_{6,7} . Conjecture 1.6 says that \mathcal{R}(6,7) is all of the listed numbers outside the gray triangle. Schinina’s theorem describes the interval in \Delta_{h,k} with \ell=0 . Figure 1 shows an illustrated example of the points ruled out by Schinina’s theorem and Theorem 1.3 . Our main theorem states that for general h and large k , all other numbers in the bounding interval outside \Delta_{h,k} are in \mathcal{R}(h,k) . Theorem 1.4 . Fix h\in\mathbb{N} . There exists a constant k_{h}\in\mathbb{N} such that if k>k_{h} , then \mathcal{R}(h,k)=\left[hk-h+1,\binom{h+k-1}{h}\right]\setminus\Delta_{h,k}. Remark 1.5 . Tracking constants in our proof shows that one can take k_{h}\leq 2^{20h^{2}} . We have not attempted to optimize this quantity further because it appears to be quite far from the truth. Numerical experiments for small h and k suggest that perhaps the conclusion of Theorem 1.4 holds for all k>h . This would be the best possible, since it sometimes fails for k\leq h ; for example, when k=3 and h>3 , there are fewer elements in \mathcal{R}(h,k) . See Section 5.2 for a discussion of what happens when k\leq h . Conjecture 1.6 . Let h\in\mathbb{N} , and let k>h . Then \mathcal{R}(h,k)=\left[hk-h+1,\binom{h+k-1}{h}\right]\setminus\Delta_{h,k}. For any fixed h , Theorem 1.4 reduces Conjecture 1.6 to a finite problem, albeit a computationally intensive one. We are able to prove that k_{3}=2 suffices, which implies Conjecture 1.6 when h=3 ; note that \Delta_{3,k}=\{3k-1\} . Theorem 1.7 . If k>2 , then \mathcal{R}(3,k)=\{3k-2\}\cup\left[3k,\binom{k+2}{3}\right]. In contrast with previous work, our proofs of Theorem 1.4 and Theorem 1.7 are nonconstructive; for a single desired sumset size, our proof does not give an explicit construction attaining it. Instead, we use continuity-type arguments to prove existence. We construct a sequence of sets A_{i} such that, even though the quantities |hA_{i}| vary non-monotonically, we can guarantee that the entire set \{|hA_{i}|\} is an interval. To study |hA| , we also study the distribution of the tuples (|A|,|2A|,|3A|,\ldots,|hA|) for various k -element sets A . Even though we do not characterize exactly which tuples are possible, we extract enough structural information to characterize the possible values of |hA| . This opens up fruitful directions for new research, to control these tuples more precisely. Another key part of our construction is combining dense sets, meaning sets with small doubling, and sparse sets, which look like Sidon sets or B_{h} sets, to get sets in the middle. 1.1. Roadmap In Section 2 , we prove Theorem 1.3 by employing an asymmetric form of Freiman’s 3k-3 theorem to control the sizes of sumsets from the diameter of sets. We then prove Theorem 1.7 before Theorem 1.4 because the proof of Theorem 1.7 contains simpler versions of some of the ideas in the proof of Theorem 1.4 . In Section 3 , we prove Theorem 1.7 using a nonconstructive inductive argument involving understanding the possible tuples (|2A|,|3A|) for all sets A\subset\mathbb{Z} with |A|=k . The bulk of the paper is in Section 4 , where we prove Theorem 1.4 . This is done using two separate constructions: In Section 4.2 , we construct sets A with smaller values of |hA| using a partially inductive construction; in Section 4.3 , we construct sets A with larger values of |hA| by combining dense sets that resemble arithmetic progressions with sparse sets that resemble geometric sequences. Section 5 discusses possible future directions of research and open problems. 2. Ruling out Numbers from \mathcal{R}(h,k) We begin with a

Read the complete text