Erdős Problem #1204
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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 #1204 has maintained status OPEN — SHARP ASYMPTOTICS UNKNOWN at this audit.
An increasing nonnegative integer \(k\)‑tuple \(0\le a_1<\cdots<a_k\) is admissible if, for every prime \(p\), its set of occupied residue classes mod \(p\) omits at least one residue. Define \(A(k)=\min a_k\) and independently \(B(k)=\min k^{-1}\sum_i a_i\), both over all admissible tuples. Translation invariance permits shifting a minimizing tuple to \(a_1=0\). For \(p>k\), admissibility is automatic, so checking all primes \(p\le k\) is enough for a fixed \(k\). The main question is whether \(A(k)\sim k\log k\); the corresponding \(B(k)\) is a separate optimization, not simply \(A(k)/2\) by definition.
A small example
Independently enumerate \(k=2,\dots,6\) increasing tuples beginning at zero with maximum element at most 23; check admissibility modulo every prime \(\le k\). The fixture obtains \(A(2)=2,A(3)=6,A(4)=8,A(5)=12,A(6)=16\) and stores exact minimizing tuples and rational sample averages for \(B(k)\). These are only bounded-search values unless it is separately shown that no valid smaller-witness tuple was missed; the reported \(A(k)\) values are exact in that range because a minimizer lies below 23 and all smaller tuples were enumerated.
What is known
The maintained catalogue https://www.erdosproblems.com/1204 attributes the problem to Elliott [El65], Erdős [Er80,p.108] and gives the currently known \((1/2+o(1))k\log k\le A(k)\le(1+o(1))k\log k\), with upper via primes just larger than \(k\) (Davenport); lower-order improvements Hensley–Richard [HeRi73]/Polymath [Po14c]. The relation \(B(k)\ge k^{-1}\sum_{j\le k}A(j)\) implies a lower of approximately \((1/4)k\log k\), versus upper \((1/2+o(1))k\log k\) from prime construction. The source has a likely typo in a greedy step written \(a_{i+1}>a_{i-1}\), which should not be silently adopted as a valid definition.
GCL's current state
Authenticated original issue-bound research return. The bounded mathematical fixture was independently replayed through ci/erdos_compendium_007_phase24_checks.py. All external advanced/general theorem statements remain attributed to sources, not independently certified. This is a local UNACCEPTED editorial manuscript.
What remains
Read Elliott 1965, Hensley–Richard and Polymath expositions to check admissibility conventions and the greedy-index typo. Audit the finite exhaustive enumeration with an independent algorithm, distinguish bounds for A and B, and retain the asymptotic constant-one conjecture as OPEN. Do not infer \(B\sim A/2\) from the two separately minimized sequences.
Independent source fidelity and critical mathematical review, protected publication, actual public deployment and V2 admission remain separate uncompleted obligations.
Sources and claim boundaries
https://www.erdosproblems.com/1204 ; [Er80,p.108],[El65],[HeRi73],[Po14c], related #855.
Exact finite receipt: governance/erdos_compendium/batches/EC-BULK-007_FINITE_CHECKS_PHASE24.json. Original source issue frozen SHA retained; no independent certificate claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2475 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- 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.