Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


The claim. There are a real c>0c>0 and an integer n0n_0 such that for every n>n0n>n_0, every abelian group GG of order nn and every A⊆GA\subseteq G with ∣A∣≥cn\lvert A\rvert\ge c\sqrt n, 00 is the sum of a nonempty subset of AA. Applied to G=Z/NZG=\mathbb Z/N\mathbb Z this is the statement of Problem 540 for N>n0N>n_0, and one constant serves every NN: for N≤n0N\le n_0 any c≥n0c\ge\sqrt{n_0} makes cN≥Nc\sqrt N\ge N, so only A=Z/NZA=\mathbb Z/N\mathbb Z, which contains 00, qualifies (a one-line remark made on the problem page). The theorem thus settles the problem in the affirmative. E. Szemerédi, On a conjecture of Erdős and Heilbronn, Acta Arith. 17 (1970), no. 3, 227--229, received 15 May 1969 (the date this page is named by, the earliest dated record of the claim); the Theorem on p. 227, paged as the Theorem of Szemerédi (1970). The proof (pp. 228--229) is a two-page combinatorial argument by contradiction through a matrix of subset sums and a chain-counting alternative; this page records its structure, not a check of each step. The paper leaves the constant unspecified and records that the sharper conjecture with 2n2\sqrt n and the non-abelian question are undecided; the constant is now 2+o(1)\sqrt2+o(1) by Hamidoune and Zémor (1996) and exact for primes by Balandraud (2012), refinements with their own claim pages, Hamidoune and Zémor (1996) and Balandraud (2012).

Acceptance. Refereed: the journal publication cited above. Reviewed: the site's curator, Thomas Bloom, who is independent of the author, accepts the theorem as the proof of the conjecture of Erdős and Heilbronn, with the label PROVED (LEAN) and a commentary attributing the general case to this paper and the prime case to Olson (1968); Erdős acknowledged the proof in his 1973 survey and, with Graham, in the 1980 monograph. The formalization link is the external Lean file that the formal-conjectures statement names as its proof, at the repository head of 15 September 2026; it names Szemerédi as the informal author and the prover Aristotle (Harmonic) and Matteo Del Vecchio as the formal authors, proves the problem's statement with the constant 1000010000 with the axiom closure its closing comment records as propext, Classical.choice and Quot.sound; the corpus has not built or independently audited it, so it is not acceptance evidence.

Depends on. Nothing in this wiki: the theorem is proved within the paper, whose card is linked above.