DIRECT AND INVERSE PROBLEMS FOR CERTAIN SUMSETS IN ADDITIVE NUMBER THEORY

Abstract

The present thesis deals with the study of direct and inverse problems for certain sumsets in additive number theory. Let A and B be two nonempty finite sets of integers. Let h and r be two positive integers. The first sumset considered is the sumset of the form A+r B, called the sum of dilates of the sets A and B. The second sumset considered is the h-fold generalized sumset h(g)A with g 1 an integer, which is a generalization of the h-fold sumset hA and the h-fold restricted sumset h^A. The third sumset considered is the h-fold signed sumset h A. The fourth sumset considered is the h-fold restricted signed sumset h^ A. The last sumset considered are the subset and subsequence sums, where the subset sums are actually the unions of restricted sumsets and the subsequence sums are the unions of generalized sumsets. The sumset A+r B := fa+rb : a 2 A;b 2 Bg is called the sum of dilates of A and B. For r = 1, the sum of dilates A+r B coincides with the Minkowski sumset A+B := fa+b : a 2 A;b 2 Bg. The direct problem for the sum of dilates A+r B is to find the minimum number of elements in A+r B in terms of number of elements in the sets A and B. The inverse problem for A+r B is to find the structure of the finite sets A and B for which jA+r Bj is minimal. In this thesis, we solve both direct and inverse problems for A+r B. Let A = fa0;a1; : : : ;ak􀀀1g be a nonempty finite set of integers. The h-fold sumset hA is the set of all sums of h elements of A, and the h-fold restricted sumset h^A is the set of all sums of h distinct elements of A. More precisely, hA := ( k􀀀1 å i=0 liai : li 2 N for i = 0;1; : : : ;k􀀀1 and k􀀀1 å i=0 li = h ) ; and h^A := ( k􀀀1 å i=0 liai : li 2 f0;1g for i = 0;1; : : : ;k􀀀1 and k􀀀1 å i=0 li = h ) ; where N denotes the set of nonnegative integers, and 1 h k in case of h^A. i ii We define the h-fold signed sumset of A, denoted by h A, by h A := ( k􀀀1 å i=0 liai : li 2 Z for i = 0;1; : : : ;k􀀀1 and k􀀀1 å i=0 jlij = h ) : We also define the h-fold restricted signed sumset of A, denoted by h^ A, by h^ A := ( k􀀀1 å i=0 liai : li 2 f􀀀1;0;1g for i = 0;1; : : : ;k􀀀1 and k􀀀1 å i=0 jlij = h ) ; where 1 h k. The direct problem for the sumset h A (similarly for h^ A) is to find the minimum number of elements in h A (respectively, h^ A) in terms of number of elements in A. The inverse problem for h A (similarly for h^ A) is to determine the structure of the finite set A for which jh Aj (respectively, jh^ Aj) is minimal. In this thesis, we study the direct and inverse problems for both the sumsets h A and h^ A. In the next part of the thesis, we consider the following generalized sumset. As the name suggests, this sumset generalizes both regular sumset hA and restricted sumset h^A. For a nonempty finite set A of k integers, and for positive integers h, g with 1 g h kg, the h-fold generalized sumset h(g)A is defined by h(g)A := ( k􀀀1 å i=0 liai : li 2 f0;1; : : : ; gg for i = 0;1; : : : ;k􀀀1 and k􀀀1 å i=0 li = h ) : Clearly, the h-fold sumset hA and the h-fold restricted sumset h^A are particular cases of the h-fold generalized sumset h(g)A for g = h and g = 1, respectively. Let A = f0;1; : : : ;k 􀀀2;k 􀀀1+bg, where b is a nonnegative integer. We investigate the behaviour of jh(g)Aj with respect to b, by finding the exact cardinality of h(g)A. Let A be a nonempty finite set of k integers. Given a subset B of A, the sum of all elements of B is called the subset sum of B. Let S(A) be the set of all subset sums of A. The subsequence sum of a given sequence A of integers is defined in a similar way. We consider the following subset and subsequence sums with some restriction on the number of elements of the set A (or sequence A ). For a nonnegative integer a ( k), we define Sa(A) to be the set of subset sums of all subsets of A that are of the size at least a. More precisely, Sa(A) := ( å b2B b : B A; jBj a ) : iii Similarly, for a nonempty sequence A = (|a0; :{:z: ;a}0 r copies ;|a1; :{:z: ;a}1 r copies ; : : : ;|ak􀀀1; :{:z: ;ak􀀀}1 r copies ) of k distinct integers each repeating exactly r ( 1) times, and for a nonnegative integer a ( rk), we define Sa(r;A ) to be the set of subsequence sums of all subsequences of A that are of the size at least a. More precisely, Sa(r;A ) := ( å b2B b :B is a subsequence of A with jBj a ) ; where jBj is the number of terms in the subsequence B. We find the minimum cardinality of the set of subset sums Sa(A) and the set of subsequence sums Sa(r;A ). We also find the structure of the finite set A (or sequence A ) of integers for which jSa(A)j (or jSa(r;A )j) is minimal.