Erdős Problem #771
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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.
The question in plain language
For each n define f(n) to be the largest integer r such that for EVERY positive m one can choose a subset S⊆{1,...,n} of cardinality r whose subset sums do NOT include m. Erdős and Graham conjectured f(n)=(1/2+o(1))n/log n; the asymptotic is PROVED by combining their lower construction with Alon–Freiman [AlFr88] upper bound. The set S may depend on m; one single S avoiding ALL positive m is not the question.
A small example
For n=10 and m=9, choose S={2,4,6,8,10}, size five: all subset sums of S are even, hence none equals 9. More generally if prime p does NOT divide m, choosing all multiples of p up to n gives floor(n/p) elements with every subset sum divisible by p. This is an exact elementary lower-bound mechanism, but it does not show the sharp worst-case asymptotic by itself.
What is known
Erdős–Graham showed that when m can matter, it can be restricted to m<n(n+1)/2 and the least prime p not dividing m satisfies p<(2+o(1))log n, providing f(n)≥(1/2+o(1))n/log n. Alon and Freiman [AlFr88] built a hard target m (a suitable lcm of initial integers) proving the complementary upper f(n)≤(1/2+o(1))n/log n. The upper is not a theorem that every S avoids no sums: it says there exists a difficult m for which no larger S can avoid representing m. Full 1988 paper details not independently rederived.
GCL's current state
The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.
Critical source-scope distinction: For each m EXISTS S depending on m, upper bound from one difficult m versus lower for all m.
What remains
Prove the prime nondivisor lower construction and give an exact n=10,m=9 fixture. Source-lock Alon–Freiman's upper hard-target m and uniform (1/2+o(1)) leading constant, carefully tracking worst-case m quantifiers and positive subset-sum convention.
Sources and claim boundaries
Maintained Erdős #771; authenticated GCL source return. Full original primary proofs and deployed browser MathJax review pending. No V2 admission.
Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2042 — 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.