Erdős Problem #1179
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: proved (not automatically the live result).
Subject areas: additive combinatorics, probability.
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.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Erdős Problem #1179 asks the following. The maintained status is PROVED.
Fix \(0<\epsilon<1\), an abelian group \(G\) of size \(N\) and a uniformly random exactly \(k\)‑element subset \(A\). Let \(F_A(g)\) count all subsets \(S\subseteq A\) (including empty) with \(\sum_{x\in S}x=g\). Seek minimal random threshold \(k=g_\epsilon(N)\) so that, with probability \(\to1\) as \(N\to\infty\), all residues simultaneously satisfy
The phrase “minimal \(k\) such that probability tends to 1 as \(N\to\infty\)” requires a source-normalized asymptotic function of \(N\), rather than pretending this probability is a fixed‑\(N\) property. Also verify uniformity across finite abelian group isomorphism types.
A small example
In \(\mathbb Z/7\mathbb Z\), \(A=\{1,2,4\}\) has eight subsets. Their sum counts across residues \(0,1,\dots,6\) are \((2,1,1,1,1,1,1)\). Ideal count is \(8/7\); residue-zero relative deviation is \((2-8/7)/(8/7)=3/4\). This deterministic \(A\) therefore fails the condition for \(\epsilon<3/4\); it is neither a counterexample to a random high-probability theorem nor a proof of a sharp threshold.
What is known
https://www.erdosproblems.com/1179 lists the target \(g_\epsilon(N)=(1+o_\epsilon(1))\log_2N\) as PROVED. Erdős–Rényi [ErRe65] first obtained an upper \((2+o(1))\log_2N+O_\epsilon(1)\); Erdős–Hall [ErHa76] sharpened to \((1+O_\epsilon(\log\log\log N/\log\log N))\log_2N\), matching the elementary lower bound \(\ge\log_2N\) in leading order. Published theorem proof not independently replayed.
GCL's current state
Authenticated original-issue RESULT/1 research return. GCL independently replayed only the exact bounded fixture in ci/erdos_compendium_007_phase21_checks.py. The general theorem statements above are attributed to their external sources rather than independently certified. This is a locally authored and unaccepted draft.
What remains
Source-read Erdős–Hall 1976 for \(k(N,\epsilon)\), the uniform-over‑\(G\) interpretation and simultaneous-in‑\(g\) concentration. Preserve empty-subset counting, correct \(\log_2\) base, and distinguish deterministic bad samples from random almost-sure asymptotics.
Protected V2 admission requires source fidelity, manuscript QA and any mandatory independent critic reviews; none is inferred from this finite example.
Sources and claim boundaries
https://www.erdosproblems.com/1179 ; [Er73,p.127],[ErRe65],[ErHa76], related #543.
Finite evidence receipt: governance/erdos_compendium/batches/EC-BULK-007_FINITE_CHECKS_PHASE21.json. Original GitHub source issue identities unchanged; source-fidelity adjudication, public deployment and V2 editorial acceptance PENDING.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2450 — 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.