Erdős Problem #395
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: analysis.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The V2 admissions ledger alone determines accepted compendium coverage. This article is a source-bounded explanation, not mathematical certification.
The question in plain language
Choose \(n\) complex numbers \(z_1,\ldots,z_n\) on the unit circle. Independently choose each sign \(\varepsilon_i\) to be \(+1\) or \(-1\), and add the signed vectors:
Problem 395 asks whether there is an absolute constant \(c>0\) such that, for every \(n>0\) and every unit choice of the \(z_i\), at least a fraction \(c/n\) of the \(2^n\) sign choices satisfy
The probability is uniform over all \(2^n\) sign patterns. Thus the claim is a lower bound that must work simultaneously for every configuration of unit complex numbers; it is not a statement about a typical configuration. In geometric language, signed walks made from arbitrary unit steps must return to the disk of radius \(\sqrt{2}\) often enough. This is called a reverse Littlewood–Offord problem because ordinary Littlewood–Offord results usually give upper bounds on concentration.
The historical version used radius \(1\). The present registered statement uses \(\sqrt{2}\), a material normalization rather than a cosmetic change.
A small example
Take four unit steps, two equal to \(1\) and two equal to \(i\). An exact enumeration can be done with integer coordinates: each sign pattern produces \((x,y)\), where \(x\) is the signed sum of the two real steps and \(y\) is the signed sum of the two imaginary steps. The condition \(|S|\leq\sqrt{2}\) is exactly \(x^2+y^2\leq2\).
The real coordinate is zero in exactly two of the four sign choices for the real steps, and the imaginary coordinate is zero in exactly two choices for the imaginary steps. Therefore exactly \(2\cdot2=4\) of the \(2^4=16\) patterns give \((x,y)=(0,0)\), so the probability is
This was independently checked by enumerating the sixteen sign tuples with integer arithmetic; the accepted squared norm among the hits was exactly \(0\). It illustrates the counting convention and avoids numerical approximations. It does not prove a uniform bound for arbitrary vectors or any asymptotic statement.
The radius-one form already fails in the smallest two-step example \(z_1=1\), \(z_2=i\). Every signed sum is one of \(\pm1\pm i\), whose squared norm is \(2\), so none lies in the unit disk. This is the counterexample attributed to Carnielli and Carolino on the live entry. Replacing \(1\) by \(\sqrt{2}\) is therefore essential.
What is known
Paul Erdős posed the original question in “On a lemma of Littlewood and Offord,” Bulletin of the American Mathematical Society 51 (1945), 898–902, DOI 10.1090/S0002-9904-1945-08454-7. Carnielli and Carolino, “Adjusting a conjecture of Erdős,” Contributions to Discrete Mathematics 6 (2011), 154–159, DOI 10.55016/ojs/cdm.v6i1.62011, give the planar radius-one counterexample and explain the adjusted radius.
The primary resolving source checked for this audit is Xiaoyu He, Tomas Juškevičius, Bhargav Narayanan, and Sam Spiro, “The Reverse Littlewood–Offord problem of Erdős,” arXiv:2408.11034, version 3 PDF, SHA-256 834e4098f8411787bf87e4e5c71f9333e1d391ddb7dd67693565125c6afa7cc1. Theorem 1.1 on p. 2 states that an absolute \(c>0\) exists for unit vectors in \(\mathbb{R}^2\) with threshold \(\sqrt{2}\) and probability at least \(c/n\); the proof is completed on p. 13. Complex unit numbers and unit vectors in the plane are the same data under the usual identification.
That paper also records a stronger earlier result by József Beck, “On a Geometric Problem of Erdős, Sárközy, and Szermerédi Concerning Vector Sums,” European Journal of Combinatorics 4 (1983), 1–10, DOI 10.1016/S0195-6698(83)80002-X. Beck’s result is cited by the later paper as covering the relevant higher-dimensional form. This article relies on the directly inspected HJNS theorem for the exact registered planar statement, without claiming an independent replay of either proof.
GCL's current state
The pinned catalogue packet is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, entry number: "395", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal status proved, formal status Lean, statement metadata yes, and last-update dates 2025-08-31 and 2026-08-24/2026-09-19. The local GCL registry binds the entry to issue #1665, whose original body SHA-256 is 06950756b6545affc71b5737990454381b5b27e36c546e9a673a1f9dcd36ad8f, and classifies it OUTSIDE_STRICT_OPEN_TRIAGE.
The live Erdős Problems #395 page, accessed 2026-10-13, displays the same \(\sqrt{2}\) statement, the radius-one counterexample, and the HJNS reference. Its live formalized-statement link points to upstream FormalConjectures. The pinned GCL FC-GDM-85F86371 snapshot has no #395 statement file, so that absence is preserved rather than silently backfilled.
An upstream FormalConjectures file now exists at commit 568ea401e53e67cdadb1e60064c6dfd520103177, blob 892433c0f17fc552f633ede6622df2a7a0dac977: 395.lean. Its signedSumCount definition and quantifiers match the adjusted theorem, but its theorem body is by sorry. The commit message reports a linked external Lean proof and build checks; those are external reports, not a GCL replay or certification.
What remains
At the mathematical-source level, the remaining task is not to discover whether the adjusted theorem has a cited proof: the inspected HJNS primary paper states and proves it. The useful bounded successor is instead a semantic and formal interface audit. Compare the complex-number statement, the \(\mathbb{R}^2\) vector statement, the normalization of uniform sign patterns, and the count-to-probability conversion in signedSumCount.
The audit should use the exact upstream commit and blob above, verify that \(n>0\), every input has norm one, the threshold is \(\sqrt{2}\), and the lower bound is \(c/n\) with one absolute positive constant. It should separately check the radius-one False variant and the sharpness construction, without treating either as a proof of the main theorem. Acceptance is a written semantic concordance identifying matching quantifiers and a reproducible finite count such as the sixteen-pattern check above. Falsification is any mismatch in domain, threshold, sign encoding, probability normalization, or quantifier scope. Stop at that first mismatch or after the concordance is complete; do not launch a full Lean build or claim certification.
Sources and claim boundaries
The original issue is #1665. Its comments were empty at audit time, and the original SOURCE RESULT/1 citation is authenticated original RESULT/1. No future comment URL is invented here. The frozen catalogue commit and blob, live page, HJNS PDF hash, upstream FormalConjectures commit and blob, Erdős’s 1945 paper, Carnielli–Carolino’s 2011 paper, and Beck’s 1983 paper are the source identities used above.
The external paper theorem is established mathematical source evidence; the upstream commit’s linked Lean proof and build report are unverified external reports for this audit; the by sorry theorem file is a formal statement, not a proof; the finite enumeration is an exact local check; and GCL mathematical certification is not supplied. Catalogue labels and formal metadata describe provenance and current snapshots. They do not replace primary-source reading, and the V2 admissions ledger alone decides accepted editorial coverage.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1665 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.