Asymptotically tight bounds on subset sums

Details Asymptotically tight bounds on subset sums Asymptotically tight bounds on subset sums

2008-05-31

arxiv.org/abs/0806.0092v1

Mathematics

Number Theory

24 pages

Scientific paper

For a subset A of a finite abelian group G we define Sigma(A)={sum_{a\in B}a:B\subset A}. In the case that Sigma(A) has trivial stabiliser, one may deduce that the size of Sigma(A) is at least quadratic in |A|; the bound |Sigma(A)|>= |A|^{2}/64 has recently been obtained by De Vos, Goddyn, Mohar and Samal. We improve this bound to the asymptotically best possible result |Sigma(A)|>= (1/4-o(1))|A|^{2}. We also study a related problem in which A is any subset of Z_{n} with all elements of A coprime to n; it has recently been shown, by Vu, that if such a set A has the property Sigma(A) is not Z_{n} then |A|=O(sqrt{n}). This bound was improved to |A|<= 8sqrt{n} by De Vos, Goddyn, Mohar and Samal, we further improve the bound to the asymptotically best possible result |A|<= (2+o(1))sqrt{n}.

Affiliated with

Also associated with

No associations

Rating

Asymptotically tight bounds on subset sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotically tight bounds on subset sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotically tight bounds on subset sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-517857