Erdős Problem #1136
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
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.
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
Can we choose more than one-third of the positive integers, in the sense of lower natural density, so that the sum of any two chosen numbers is never a power of two?
Erdős Problem #1136 asks for a set \(A\subseteq\mathbb N\) with
for every \(a,b\in A\) and \(k\ge0\). Self-sums \(a+a\) are included.
The answer is yes: a construction of Müller has density exactly \(1/2\), and the published theorem says this is optimal.
A small example
Let \(A\) consist of the positive integers whose odd part is congruent to \(3\) modulo \(4\). Equivalently, each has the form
If two such integers have different powers of two dividing them, their sum has an odd factor larger than one. If their powers agree, then their sum is \(2^{i+1}\) times an odd number congruent to \(3\bmod4\). In neither case is the sum a pure power of two.
The finite count is slightly subtler than saying exactly half: through \(2^{14}=16384\) there are 8,191 members. The limiting density is nevertheless \(1/2\).
What is known
Erdős posed the question at the 1987 Berlin DMV conference, as reported by Müller (2011). The simple set of multiples of three gives the threshold density \(1/3\).
Müller (2011) constructed the set above and established that no admissible set has lower density exceeding \(1/2\). Thus the maximum possible lower density is exactly one-half.
The maintained catalogue also labels the problem PROVED (LEAN), but its formalization metadata does not provide a directly verified theorem in the older GCL snapshot. An external formal-proof label is not an independent GCL kernel check.
GCL's current state
Authenticated source audit #2407 contains the explicit modular sum argument. Exact enumeration through 16,384 confirms the finite count and excludes all power-of-two pair sums at that bound.
This independently verifies the construction, not Müller's general upper-density optimality proof.
What remains
Inspect Müller's original density calculation and upper bound, reconcile the live Lean label with an immutable formal proof commit, and verify the exact inclusion of the diagonal \(a=b\).
Sources and claim boundaries
Erdős #1136; Müller (2011); GCL return. The construction is independently derived; optimality is externally proved. Unaccepted draft.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2407 — 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.