Erdős Problem #361
Editorial depth: Reviewed explanatory article — evidence qualified.
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.
The question in plain language
Fix a real number \(c>0\) and a positive integer \(n\). Look inside the interval of integers from \(1\) through \(\lfloor cn\rfloor\). We want the largest possible set \(A\) with the property that no subset of \(A\) has sum exactly \(n\). In other words, even after choosing or discarding each member of \(A\), the target \(n\) must remain unreachable. Writing
the problem asks how large \(F_c(n)\) can be, and whether its value fluctuates in an irregular way as \(n\) changes. The question is extremal: it asks for the maximum size, not merely for one construction.
The historical wording is slightly different. Erdős and Graham ask how many integers strictly less than \(n/k\) can be chosen, with \(k\) fixed and \(n\) large, so that \(n\) is not a subset sum. The live formulation replaces \(1/k\) by an arbitrary fixed \(c>0\) and uses the closed interval through \(\lfloor cn\rfloor\). These are closely related normalizations, but strict versus non-strict endpoint conventions can differ for individual \(n\), so they should not be silently identified.
A small example
Take \(c=3/4\) and \(n=4\). Then \(\lfloor cn\rfloor=3\), so the universe is \(\{1,2,3\}\). The set \(\{1,2\}\) is valid: its subset sums are \(0,1,2,3\), and none is \(4\). Thus \(F_{3/4}(4)\geq2\).
There is only one candidate of size three, namely \(\{1,2,3\}\). It is invalid because the subset \(\{1,3\}\) sums to \(4\). Hence \(F_{3/4}(4)=2\). An exhaustive exact check gives the valid candidates
(), (1), (2), (1, 2), (3), (2, 3)
and maximum cardinality 2. One reproducible verifier is:
from itertools import combinations
U, n = (1, 2, 3), 4
def subset_sums(A):
s = {0}
for a in A:
s |= {x + a for x in s}
return s
good = [A for r in range(4) for A in combinations(U, r)
if n not in subset_sums(A)]
print(good, max(map(len, good)))
This is an exact finite calculation over integers, not a heuristic and not a proof of the asymptotic problem. It illustrates the key semantic point: checking only the sum of the whole candidate set would incorrectly accept \(\{1,2,3\}\), while the problem checks every subset.
What is known
The primary source inspected here is P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 59. It records the question; the page does not supply a solution or an asymptotic formula for this extremal function. The maintained Erdős Problems page labels the problem open and says that it cannot be resolved by a finite computation.
The live discussion contains useful but unverified exploration. One comment gives elementary constructions from multiples of the smallest prime not dividing \(n\) and from intervals whose repeated use would overshoot \(n\). Other comments propose residue-class constructions for particular divisibility patterns, including \(c=3/4\). These are reports by contributors, not checked theorems in the source packet.
There is also a proof claim posted in July 2026. Its summary asserts, among other things, an exact formula for \(c\geq1\) and non-convergence of \(F_c(n)/n\) for \(0<c<1\). A later comment says that the posted argument addresses only the irregular-dependence part and that a more general theorem may still be missing. A second contributor reports a note with subsequential limits. No primary paper or independently checked proof for those claims was available in this inquiry, so they remain unverified external reports rather than established coverage.
GCL's current state
The frozen catalogue evidence is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, blob 4e60263a80af6207aca494d2e1388e44fa372889. Its entry records informal status open, last updated 2025-08-31, formal status unformalized, and statement-formalized metadata yes.
The issue-pinned formal file is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, FormalConjectures/ErdosProblems/361.lean, blob 48fc69c8afea3f309265e3921c661b0f7af4cb16. All three declarations are proved by sorry and use placeholder answer(sorry). More importantly, its hypothesis hA : ∀ c n, ... shadows the fixed real parameter with fresh natural binders, forcing one function to represent all cutoffs at once. Its filter rejects only candidates whose entire sum is \(n\); it does not reject a candidate having some subset summing to \(n\).
Formal-conjectures issue #4440 documents both defects. Later fix commit eb5f135f5ae06f3764310a7146e19db1da91f917 introduces an explicit subset-avoidance predicate and an exact test for the \(n=4\) example. That repository change is evidence about formal-source history, not GCL mathematical certification, and it does not by itself settle the open asymptotic question.
What remains
A bounded successor task should audit the live numerical report for \(c=3/4\) at \(n=100,101,102,103,104\), where a discussion comment reports values 34,37,32,38,35. The input is exactly those five integers and the closed universe \(\{1,\ldots,\lfloor3n/4\rfloor\}\). The target is one exact value \(F_{3/4}(n)\) for each input, together with a maximizing set.
Use integer dynamic programming to enumerate every subset of the universe whose sum is \(n\), then solve the resulting finite hitting-set formulation: for every forbidden subset \(B\), the retained indicators must satisfy \(\sum_{x\in B}x_A\leq |B|-1\). Acceptance requires an independently readable certificate consisting of the proposed set, a complete forbidden-subset constraint digest, and a checked upper-bound certificate ruling out a larger set. Falsification is the first valid larger set, invalid proposed set, missing constraint, or mismatch with a reported value. Stop after all five certificates pass or at the first discrepancy; do not infer an asymptotic theorem from the finite table.
Sources and claim boundaries
The original assignment is MATH-PROGRAMME issue #1631. The live entry is Erdős Problem 361, accessed 2026-10-13. The primary scan is Erdős--Graham (1980), cited on printed p. 59; the inspected PDF has SHA-256 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. The catalogue and pinned formal hashes are recorded above. The later formal repair is not a proof of the original problem.
The original SOURCE RESULT/1 citation is authenticated original RESULT/1. This article does not claim a solved status, publication, award, Lean replay, or GCL certification. Accepted coverage is determined by the applicable V2 ledger, not by the catalogue label, live discussion, proof-claim page, or this editorial article.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1631 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.