Skip to content

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.

Back to catalogue · Compendium introduction