Inverse problems for sumset sizes of finite sets of integers

Melvyn B. Nathanson · 2024

Read Inverse problems for sumset sizes of finite sets of integers by Melvyn B. Nathanson (2024) 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-2412-16154.txt.

Introduction

Melvyn Nathanson studies inverse problems for the sizes of sumsets of finite integer sets. For a set A, its h-fold sumset collects all sums of h elements drawn from A. The 2024 paper asks what the growth of those sizes reveals about the set itself.

The work examines the full sequence of sumset sizes as h grows without bound. It compares sequences for sets that cannot be matched by shifts and scalings. It also weighs growth rates and shapes across those sequences side by side. Such inverse questions matter because many distinct sets can share early sumset data. The paper maps how much of a set's form its sumset sizes can pin down.

Catalog record

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

Source: https://arxiv.org/abs/2412-16154

Browse the full library · About the Tower of Babel

Full text

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

Inverse problems for sumset sizes of finite sets of integers Thanks: Supported in part by PSC-CUNY Research Award Program grant 66197-00 54. Melvyn B. Nathanson Abstract . Let A A be a finite set of integers and let h ​ A hA be its h h -fold sumset. This paper investigates the sequence of sumset sizes ( | h ​ A | ) h = 1 ∞ (|hA|)_{h=1}^{\infty} , the relations between these sequences for affinely inequivalent sets A A and B B , and the comparative growth rates and configurations of the sumset size sequences ( | h ​ A | ) h = 1 ∞ (|hA|)_{h=1}^{\infty} and ( | h ​ B | ) h = 1 ∞ (|hB|)_{h=1}^{\infty} . 2000 Mathematics Subject Classification 11B05, 11B13, 11B34, 11B75, 11D04, 11D07, 11P70, 05A16 1. The sequence of sumset sizes Let A be a nonempty finite set of integers. The h -fold sumset of the set A , denoted hA , is the set of all sums of h not necessarily distinct elements of A . Let |hA| denote the size (or cardinality) of the set |hA| . A direct problem for sumset sizes in additive number theory is to compute the infinite sequence (|hA|)_{h=1}^{\infty} . For sufficiently large h , this sequence is completely determined by Theorem 2 and is eventually an arithmetic progression. For small h , Theorem 3 gives a lower bound for |hA| . Sets of integers A and B are affinely equivalent if there exist rational numbers \lambda and \mu with \lambda\neq 0 such that B=\lambda\ast A+\mu=\{\lambda x+\mu:x\in A\}. For example, the sets \{0,2\} and \{1,4\} are affinely equivalent because \{0,2\}=\frac{2}{3}\ast\{1,4\}-\frac{2}{3}. With \lambda=-1 and a\in\mathbf{Z} , the set A is affinely equivalent to its reflection a-A=(-1)\ast A+a . All 1-element sets of integers are affinely equivalent and all 2-element sets of integers are affinely equivalent. The sets [0,k-1] and [0,k-2]\cup\{k\} are affinely inequivalent sets of integers of size k for all k\geq 3 . If A and B are affinely equivalent sets with B=\lambda\ast A+\mu , then hB=h(\lambda\ast A+\mu)=\lambda\ast hA+h\mu and so |hA|=|hB| for all h\geq 1 . Thus, the size of a sumset is an affine invariant . It is natural to consider inverse problems for the sequence of sumset sizes \left(|hA|\right)_{h=1}^{\infty} of a nonempty finite set A of integers. To what extent does the sequence of positive integers \left(|hA|\right)_{h=1}^{\infty} determine A ? If A and B are affinely equivalent sets, then \left(|hA|\right)_{h=1}^{\infty}=\left(|hB|\right)_{h=1}^{\infty} . What are the relations between the sequences \left(|hA|\right)_{h=1}^{\infty} and \left(|hB|\right)_{h=1}^{\infty} for affinely inequivalent sets of the same size? Do there exist affinely inequivalent finite sets of integers A and B such that \left(|hA|\right)_{h=1}^{\infty}=\left(|hB|\right)_{h=1}^{\infty} ? For every positive integer h_{1} , do there exists finite sets of integers A and B such that |hA|=|hB| for all h\leq h_{1} but |hA|<|hB| for all h>h_{1} ? Do there exists finite sets of integers A and B such that |hA|>|hB| for all h\leq h_{1} but |hA|<|hB| for all h>h_{1} ? We answer some of these question, but many problems remain open. Notation. In this paper, all sets are finite sets of integers. The interval of integers [u,v] is the set of all integers n such that u\leq n\leq v . The integer part , also called the floor , of the real number x , denoted \lfloor x\rfloor , is the greatest integer n\leq x , and the ceiling of the real number x , denoted \lceil x\rceil , is the smallest integer n\geq x . 2. The direct problem for sumset sizes A finite set of integers is normalized if \min(A)=0 and \gcd(A)=1 . If the set A is normalized, then the set \max(A)-A is also normalized. Every finite set of at least two integers is affinely equivalent to an essentially unique normalized set. (If A and A^{\prime} are affinely equivalent normalized sets of integers, then A^{\prime}=\max(A)-A .) The following result is fundamental in additive number theory. Theorem 1 (Nathanson [ 6 , 7 ] ) . Let A be a finite set of k\geq 2 integers with \min(A)=0 , \max(A)=a , and \gcd(A)=1 . There exist integers C and D and subsets \mathcal{C}\subseteq[0,C-2] and \mathcal{D}\subseteq[0,D-2] such that hA=\mathcal{C}\cup[C,ha-D]\cup(ha-\mathcal{D}) for all h\geq h_{0}(A) . The numerical semigroup generated by a set A of relatively prime nonnegative integers is the set S(A)=\{0\}\cup\bigcup_{h=1}^{\infty}hA . This semigroup contains all sufficiently large integers. The Frobenius number of the set A , denoted g(A) , is the largest integer that is not in the semigroup. The genus of A , denoted N(A) , is the number of nonnegative integers not contained in the numerical semigroup S(A) . (For the Frobenius problem, see Ramírez-Alfonsín [ 8 ] .) In Theorem 1 , |\mathcal{C}|=C-N(A)\qqand|\mathcal{D}|=D-N(a-A) where a-A=\{a-x:x\in A\} is the reflection of A . Theorem 1 immediately implies the following. Theorem 2 . Let A be a finite set of k\geq 2 integers with \min(A)=0 , \max(A)=a , and \gcd(A)=1 . Then |hA|=ha+1-N(A)-N(a-A) for all h\geq h_{0}(A) and so the sequence of sumset sizes \left(|hA|\right)_{h=1}^{\infty} is eventually an arithmetic progression with difference a . The original result in [ 6 ] was h_{0}(A)=a^{2}(k-1) . Recently, Andrew Granville, George Shakan, and Aled Walker [ 1 , 2 ] obtained h_{0}(A)=a-k+2 . Vsevolod Lev [ 5 ] gives another proof of this result. The hard part of the direct problem is to understand |hA| for small h . For this, the following result is useful. Theorem 3 (Lev [ 4 ] ) . Let A be a finite set of k\geq 2 integers with \min(A)=0 , \max(A)=a , and \gcd(A)=1 . For all h\geq 2 , |hA|\geq|(h-1)A|+\min(a,h(k-2)+1). 3. Inverse problems for sumset size Problem 1 . Let A be a normalized finite set of integers. The inverse problem for sumset sizes is to deduce structural information about A from the sumset size sequence \left(|hA|\right)_{h=1}^{\infty} . For example, if A is a normalized finite set of integers, then the sequence \left(|hA|\right)_{h=1}^{\infty} is eventually an arithmetic progression with |hA|=ha+1-N(A)-N(a-A) and so \max(A)=a . The set A is an interval if and only if 2|hA|=|(h-1)A|+|(h+1)A| for all h\geq 2 . The set A is not an interval if |hA|\neq h|A|-h+1 for some h\geq 2 . The next result shows that the sumset size sequence \left(|hA|\right)_{h=1}^{\infty} does not determine the affine equivalence class of A . Theorem 4 . For all k\geq 3 , there exist affinely inequivalent sets A and B such that |A|=|B|=k and |hA|=|hB| for all h\geq 2 . Proof. The proof is by explicit construction. Let k=3 . The sets A=\{0,2,7\}\qqand B=\{0,3,7\} are affinely inequivalent with |A|=|B|=3 . We have \displaystyle 2A \displaystyle=\{0,2,4,7,9,14\} \displaystyle 2B \displaystyle=\{0,3,6,7,10,14\} \displaystyle 3A \displaystyle=\{0,2,4,6,7,9,11,14,16,21\} \displaystyle 3B \displaystyle=\{0,3,6,7,9,10,13,14,17,21\} \displaystyle 4A \displaystyle=\{0,2,4,6,7,8,9,11,13,14,16,18,21,23,28\} \displaystyle 4B \displaystyle=\{0,3,6,7,9,10,12,13,14,16,17,20,21,24,28\} and so |2A|=|2B|=6 |3A|=|3B|=10 |4A|=|4B|=15. Applying Theorems 1 and 2 , we obtain finite sets \mathcal{C}_{A}=\{0,2,4\}\qqand\mathcal{D}_{A}=\{0,5,7,10,12,14,15,17,19,20,21,22\} and \mathcal{C}_{B}=\{0,3,6,7,9,10\}\qqand\mathcal{D}_{B}=\{0,4,7,8,11,12,14,15,16\} such that |\mathcal{C}_{A}|+|\mathcal{D}_{A}|=|\mathcal{C}_{B}|+|\mathcal{D}_{B}|=15. For all h\geq 5 we have hA=\mathcal{C}_{A}\cup[6,7h-24]\cup(7h-\mathcal{D}_{A}) and hB=\mathcal{C}_{B}\cup[12,7h-18]\cup(7h-\mathcal{D}_{B}) and so |hA|=|hB|=7h-14. It follows that |hA|=|hB| for all h\geq 1 . Let k=4 . The sets A=\{0,3,5,6\}\qqand B=\{0,4,5,6\} are affinely inequivalent with |A|=|B|=4 . For all h\geq 2 we have hA=A\cup[8,6h] and hB=B\cup[8,6h] and so |hA|=|hB|=6h-3 for all h\geq 2 . For all k\geq 5 , the sets A=\{0,3,5,6\}\cup[8,k+3]\qqand B=\{0,4,5,6\}\cup[8,k+3] are affinely inequivalent with

Read the complete text