pith. sign in

arxiv: 0806.0092 · v1 · pith:75EYMRD7new · submitted 2008-05-31 · 🧮 math.NT · math.CO

Asymptotically tight bounds on subset sums

classification 🧮 math.NT math.CO
keywords sigmaboundsubsetasymptoticallysqrtbeenbestgoddyn
0
0 comments X
read the original abstract

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}.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.