Erdős Problem #13
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
How large can a set \(A\) of integers between 1 and \(N\) be if no smaller member divides the sum of two larger members? More precisely, whenever \(a,b,c\in A\) and \(a<\min(b,c)\), we require \(a\) not to divide \(b+c\). The two larger summands may be equal.
Erdős Problem #13, posed by Erdős and Sárközy, conjectured an upper bound of \(N/3+O(1)\). The conjecture was proved by Benjamin Bedert in 2023. A separate problem allowing sums of \(r\) larger elements remains an open generalization.
A small example
Choose
This contains \(N-\lfloor2N/3\rfloor\) integers, about one third of the interval. If \(a,b,c\in A\) and \(a<b,c\), then
There is no integer multiple of \(a\) strictly between \(2a\) and \(3a\), so \(a\) cannot divide \(b+c\). For \(N=9\), the set \(\{7,8,9\}\) is one concrete example. This proves that one third is achievable, not that no other construction can be larger.
What is known
Bedert, On a problem of Erdős and Sárközy about sequences with no term dividing the sum of two larger terms, arXiv:2301.07065 (2023), proves the stronger estimate
for every sufficiently large \(N\). Together with the tail construction above, this determines the asymptotic leading constant. The detailed published argument was not independently reproduced for this article.
GCL's current state
Source audit #1282 reads the pinned formal statement, whose predicate quantifies over possibly equal \(b,c\) and whose main theorem states a uniform \(N/3+C\) upper bound. The frozen theorem body was unfilled; metadata calling the mathematical result solved is not a GCL kernel certification. The audit checks the elementary matching construction and flags the still-open multi-summand variant.
What remains
The original two-larger-summand question is resolved. Remaining tasks involve formal verification of the published upper theorem and separate study of the generalized sum-of-multiple-elements question. Neither is a reason to label the historical #13 statement open again.
Sources and claim boundaries
- Erdős Problems #13: solved statement and generalization.
- Bedert (2023), author preprint: published proof result, not independently kernel-replayed here.
- GCL source return #1282: exact finite construction and statement comparison, not new mathematical certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1282 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.