Erdős Problem #540

Erdős problem 540. Does $|A|\geq C\sqrt N$, for a suitable absolute constant $C$, force a nonempty zero-sum subset of $A\subseteq\mathbb Z/N\mathbb Z$?

Status and precise known input. Yes. We use Hamidoune and Zémor, On zero-free subset sums, Acta Arithmetica 78 $1996$, 143--152, Theorem 4.5: https://matwbn.icm.edu.pl/ksiazki/aa/aa78/aa7823.pdf. Their theorem, in its asymptotic consequence, says that every subset of any finite abelian group of order $N$ of size at least \[ \sqrt{2N}+O(N^{1/3}\log N) \] has a nonempty zero-sum subset, with an absolute implied constant in the sufficient threshold. This is an external theorem, not a bound derived from the pigeonhole principle alone. The problem source is https://www.erdosproblems.com/540; checked 24 September 2026.

The quantifiers and the cyclic lower bound. Since $N^{1/3}\log N=o(\sqrt N)$, for every fixed $\eta>0$ and all sufficiently large $N$, size at least $(\sqrt2+\eta)\sqrt N$ suffices. In particular an absolute $C$ works for all large $N$. Enlarging it covers the finitely many smaller $N$: a set equal to the whole group contains $0$, and for thresholds exceeding $N$ the implication is vacuous.

This leading constant cannot be decreased in general. Let $k$ be the largest integer satisfying $k(k+1)/2<N$, and take the distinct residues \[ A=\{1,2,\ldots,k\}\subseteq\mathbb Z/N\mathbb Z. \] Every nonempty subset has an ordinary integer sum between $1$ and $k(k+1)/2<N$, hence is not zero modulo $N$. Furthermore $k=\sqrt{2N}+O(1)$. Thus a universal threshold $(c+o(1))\sqrt N$ with $c<\sqrt2$ would fail for all sufficiently large $N$. Together with the theorem, this identifies the leading constant for cyclic groups.

Why distinctness is crucial. For a sequence, $N-1$ copies of the residue $1$ have no nonempty zero sum. Thus the square-root statement could not hold for sequences permitting repetitions. Conversely, every sequence of $N$ group elements has a nonempty zero-sum consecutive block: its $N+1$ partial sums, including the empty sum, repeat in a group of order $N$. This proves only a linear threshold and explains why it does not supply the theorem used above.

An elementary necessary condition for a counterexample. If $0\in A$, there is a singleton witness. If $a,-a\in A$ are distinct, there is a two-element witness. Thus a zero-sum-free set contains at most one element from each two-element orbit of negation. Elements of order two are fixed points of negation and may occur individually: the relation $a+a=0$ does not use a subset of a set unless there are two distinct available elements, so it does not exclude these fixed points. If $h$ is the number of nonzero elements of order two, this elementary argument gives only $|A|\leq(N-1-h)/2+h$, far larger than the square-root theorem in general. It identifies precisely the limitation of this shortcut.

Completion estimate. The desired universal bound and its sharp leading constant follow from the stated external theorem and the fully proved lower construction. COMPLETION: 100%