Let $N=\{1,2,\ldots ,n\},n>1$. We wish to construct a set $A\subseteq N$ with the property:

The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$.

Question: What is the maximum value of $|A|$?

It is obvious that if $\quad$ $T_m=1+2+\ldots +m=\frac{m(m+1)}{2}$ and $T_m<n$, then $|A|\geq m$.
This gives immediately $\max|A|\geq c\cdot \sqrt{n}$.
Is it possible to obtain something more accurate?
Thanks in advance.

  • 6
    $\begingroup$ mathoverflow.net/questions/44309 indicates that this value is called the restricted Davenport number of the cyclic group $C_n$, and that it is (asymptotically?) bounded above by $\sqrt{2n}$, which matches your lower bound. $\endgroup$ – Emil Jeřábek Oct 30 '14 at 21:50
  • 3
    $\begingroup$ As @EmilJeřábek notes, $\sqrt{2n}$ is the precise asymptotic value of $\max{|A|}$. Your construction gives the lower bound, while the result of Y. O. Hamidoune and G. Zemor in the paper On zero-free subset sums (Acta Arithmetica, 1996) supplies an upper bound of $\sqrt{2n} + O(n^{1/3}\log{n})$ (with a much better error term if $n$ is prime). For $n$ prime, a bound of the form $\max{|A|} < C \sqrt{n}$ already goes back to the 1964 Acta Arithmetica paper On the addition of residue classes mod $p$ by Erdos and Heilbronn. $\endgroup$ – Vesselin Dimitrov Oct 30 '14 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.