Problem 540

Is it true that if $A\subseteq \mathbb{Z}/N\mathbb{Z}$ has size $\gg N^{1/2}$ then there exists some non-empty $S\subseteq A$ such that $\sum_{n\in S}n\equiv 0\pmod{N}$ ?

Source: erdosproblems.com/540

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site's label is PROVED (LEAN). Szemerédi's Theorem (Acta Arith. 1970, refereed) gives $c>0$ and $n_0$ such that for every $n>n_0$ , every abelian group of order $n$ and every subset $A$ with $|A|\ge c\sqrt n$ , $0$ is a sum of a nonempty subset of $A$ ; for $n\le n_0$ any $c\ge\sqrt{n_0}$ makes $c\sqrt n\ge n$ , so only $A=\mathbb Z/n\mathbb Z\ni0$ qualifies, and one constant serves every $N$ (a one-line remark on this page). The standing derives from the claim page Szemerédi's theorem, accepted on the refereed publication and the site's acceptance, so the problem is solved, proved. Refinements, each with its claim page: Olson (1968, Theorem

proved the prime case with the threshold $s>(4p-3)^{1/2}$ , hence with the constant $2$ (Olson (1968)); Hamidoune and Zémor (1996) proved $|S|\ge\sqrt{2p}+5\ln p$ for prime order and $|S|>\sqrt{2n}+O(n^{1/3}\ln n)$ for every finite abelian group of order $n$ , a second full proof (Hamidoune and Zémor (1996)); Balandraud (2012) proved Selfridge's exact value for primes, which makes the threshold $\sqrt{2p}+O(1)$ there (Balandraud (2012)). The constant $\sqrt2$ for composite $N$ (beyond the $o(1)$ term) remains open. For non-abelian groups, Erdős (1973) recorded the case as unsettled; Hamidoune and Zémor's introduction (p. 143) credits Olson's 1975 paper with the constant $3$ "in the case of an arbitrary finite group", while their Theorem 2.5 states his result for abelian groups. Olson's 1975 paper is not carded, so this page leaves open whether it settles the non-abelian question, and the paper has no claim page. The site's (LEAN) suffix is a catalog label explained under Formalization and the Lean label below.

Sz70: Szemerédi, E., On a conjecture of Erdős and Heilbronn. Acta Arith. 17 (1970), no. 3, 227--229, DOI 10.4064/aa-17-3-227-229; the Theorem, p. 227. Library home: Szemerédi 1970.
ErHe64: Erdős, P. and Heilbronn, H., On the addition of residue classes mod $p$ . Acta Arith. 9 (1964), no. 2, 149--159, DOI 10.4064/aa-9-2-149-159; Theorem I, p. 149; Conjectures 1--4, pp. 158--159. Library home: Erdős and Heilbronn 1964.
Ol68: Olson, J. E., An addition theorem modulo $p$ . J. Combinatorial Theory 5 (1968), no. 1, 45--52, DOI 10.1016/S0021-9800(68)80027-4; Theorem 1, p. 45, with its proof, pp. 46--47 (in the publisher's open archive). Library home: Olson 1968.
HaZe96: Hamidoune, Y. O. and Zémor, G., On zero-free subset sums. Acta Arith. 78 (1996), no. 2, 143--152, DOI 10.4064/aa-78-2-143-152; Theorem 3.3, p. 148; Theorem 4.5, p. 151. Library home: Hamidoune and Zémor 1996.
Ba12: Balandraud, É., An addition theorem and maximal zero-sum free sets in $\mathbb Z/p\mathbb Z$ . Israel J. Math. 188 (2012), no. 1, 405--429, DOI 10.1007/s11856-011-0171-9, with an erratum, ibid. 192 (2012), no. 2, 1009--1010 (not read); arXiv:0907.3492v1 (20 July 2009, read, not held; its labels used here); Theorem 9, p. 16. Library home: Balandraud 2012.
Er65b: Erdős, P., Some recent advances and current problems in number theory. Lectures on Modern Mathematics III, Wiley (1965), 196--244; printed pp. 230--231. Library home: Erdős 1965.
Er73: Erdős, P., Problems and results on combinatorial number theory (1973), 117--138; item 7 on printed p. 126. Library home: Erdos 1973.
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980); printed p. 103 and p. 95. Library home: Erdős and Graham 1980.
Gu04: Guy, R. K., Unsolved Problems in Number Theory, 3rd ed. Problem Books in Mathematics, Springer (2004), xviii+437 pp.; C15 "Maximal zero-sum-free sets", printed pp. 193--194: Erdős and Heilbronn's largest $k=k(m)$ of distinct residues modulo $m$ with no zero-sum subset, $k(20)=6$ , $k\ge\lfloor(-1+\sqrt{8m+9})/2\rfloor$ for $m>5$ with equality for $5<m\le24$ , Selfridge's construction and conjecture for even $m$ , his conjecture $k(p)=k$ for primes $\frac12k(k+1)<p<\frac12(k+1)(k+2)$ , and the Erdős--Heilbronn and Olson results modulo $p$ ; no proofs. Library home: Guy 2004.
OEIS: Sloane, N. J. A., Sequence A034463, The On-Line Encyclopedia of Integer Sequences (1999; entry last modified 10 September 2025, server time): the largest number of residue classes mod $n$ with no zero-sum subset.

Problem 540

Status

Proof claims

Discussion