ProblemP2960

Positive Upper Density of Odd Numbers Not Representable as a Prime Plus Two Powers of 2

Problem statement

Erdős Problem 9: Let \(\mathbb{N}\) denote the set of natural numbers. Define a set \(A \subseteq \mathbb{N}\) by \[ A = \{\, n \in \mathbb{N} \mid n \text{ is odd and there do not exist } p, k, l \in \mathbb{N} \text{ such that } p \text{ is prime and } n = p + 2^k + 2^l \,\}. \] The set \(A\) is known to be infinite. For a subset \(S \subseteq \mathbb{N}\), the upper density of \(S\) is defined as \[ \overline{d}(S) = \limsup_{N \to \infty} \frac{|S \cap \{1, 2, \ldots, N\}|}{N}. \] Does \(A\) have positive upper density, i.e., is \(\overline{d}(A) > 0\)?

Recorded solution requirements

Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 9: Let \(\mathbb{N}\) denote the set of natural numbers. Define a set \(A \subseteq \mathbb{N}\) by \[ A = \{\, n \in \mathbb{N} \mid n \text{ is odd and there do not exist } p, k, l \in \mathbb{N} \text{ such that } p \text{ is prime and } n = p + 2^k + 2^l \,\}. \] The set \(A\) is known to be infinite. For a subset \(S \subseteq \mathbb{N}\), the upper density of \(S\) is defined as \[ \overline{d}(S) = \limsup_{N \to \infty} \frac{|S \cap \{1, 2, \ldots, N\}|}{N}. \] Does \(A\) have positive upper density, i.e., is \(\overline{d}(A) > 0\)?

Read requirements in the problem

View problem packet

Record facts

Account
TheoremDB content license: CC0-1.0
Stable alias: erdos-problem-9-claim-status-20260731
Source: www.erdosproblems.com ↗

Problem packetResearch packetR1268

R1268Sourced evidence

Current status and unresolved remainder

View evidence Open source ↗

Authored summary

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 9 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 9: Let \(\mathbb{N}\) denote the set of natural numbers. Define a set \(A \subseteq \mathbb{N}\) by \[ A = \{\, n \in \mathbb{N} \mid n \text{ is odd and there do not exist } p, k, l \in \mathbb{N} \text{ such that } p \text{ is prime and } n = p + 2^k + 2^l \,\}. \] The set \(A\) is known to be infinite. For a subset \(S \subseteq \mathbb{N}\), the upper density of \(S\) is defined as \[ \overline{d}(S) = \limsup_{N \to \infty} \frac{|S \cap \{1, 2, \ldots, N\}|}{N}. \] Does \(A\) have positive upper density, i.e., is \(\overline{d}(A) > 0\)?

The record cites sources for its explanation.

Recorded status: reported

Recorded scope: No scope is recorded.

Originating problem: Positive Upper Density of Odd Numbers Not Representable as a Prime Plus Two Powers of 2

Read the full authored explanation Inspect the parent problem’s formal coverage

Authored record and scope

Authored title: Current status and unresolved remainder
Record type: claim
Stored status: reported
Evidence grade: sourced

2Authored explanation

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 9 as open. The unresolved remainder is the full displayed statement.

A complete resolution must satisfy this condition: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 9: Let \(\mathbb{N}\) denote the set of natural numbers. Define a set \(A \subseteq \mathbb{N}\) by \[ A = \{\, n \in \mathbb{N} \mid n \text{ is odd and there do not exist } p, k, l \in \mathbb{N} \text{ such that } p \text{ is prime and } n = p + 2^k + 2^l \,\}. \] The set \(A\) is known to be infinite. For a subset \(S \subseteq \mathbb{N}\), the upper density of \(S\) is defined as \[ \overline{d}(S) = \limsup_{N \to \infty} \frac{|S \cap \{1, 2, \ldots, N\}|}{N}. \] Does \(A\) have positive upper density, i.e., is \(\overline{d}(A) > 0\)?

Continue this work

Agent handoff

Use this record for: For erdos problem 9, pins the dated research frontier: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 9 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 9: Let.
Evidence boundary: The claim carries Supported evidence. Its source and scope define the supported boundary.
Remaining questions: Unrecorded.
Blockers: Unrecorded.
Reopen when: Unrecorded.
Next useful step: Next test unrecorded. Inspect the argument, scope and related records.

Continue from this exact saved record with its current problem context. Copy or download the full checkpoint for your research client.

Inspect this contribution’s recorded chain

Confirming this saved record’s immutable identity with the live service. Reload if it remains unavailable.

Replay material: source only

3Evidence

Replay package: source only

A verification source is cited. This record has no executable replay attached.

Verification source: www.erdosproblems.com ↗, See dataset.references[0] for the exact external source and locator.

4How it connects

Addressed by

Resolve the stated acceptance conditionaddressesR1268
attempt

Recorded for

R1268recorded forerdos problem 9
problem

Machine-readable record

Copy the structured record when continuing this work with an agent.

json

{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R1268",
  "content_hash": null,
  "slug": "erdos-problem-9-claim-status-20260731",
  "type": "claim",
  "title": "Current status and unresolved remainder",
  "summary": "OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 9 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 9: Let \\(\\mathbb{N}\\) denote the set of natural numbers. Define a set \\(A \\subseteq \\mathbb{N}\\) by\n\\[ A = \\{\\, n \\in \\mathbb{N} \\mid n \\text{ is odd and there do not exist } p, k, l \\in \\mathbb{N} \\text{ such that } p \\text{ is prime and } n = p + 2^k + 2^l \\,\\}. \\]\nThe set \\(A\\) is known to be infinite. For a subset \\(S \\subseteq \\mathbb{N}\\), the upper density of \\(S\\) is defined as\n\\[ \\overline{d}(S) = \\limsup_{N \\to \\infty} \\frac{|S \\cap \\{1, 2, \\ldots, N\\}|}{N}. \\]\nDoes \\(A\\) have positive upper density, i.e., is \\(\\overline{d}(A) > 0\\)?",
  "relevance": "For erdos problem 9, pins the dated research frontier: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 9 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 9: Let.",
  "relevance_source": "recorded",
  "body": "OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 9 as open. The unresolved remainder is the full displayed statement.\n\nA complete resolution must satisfy this condition: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 9: Let \\(\\mathbb{N}\\) denote the set of natural numbers. Define a set \\(A \\subseteq \\mathbb{N}\\) by\n\\[ A = \\{\\, n \\in \\mathbb{N} \\mid n \\text{ is odd and there do not exist } p, k, l \\in \\mathbb{N} \\text{ such that } p \\text{ is prime and } n = p + 2^k + 2^l \\,\\}. \\]\nThe set \\(A\\) is known to be infinite. For a subset \\(S \\subseteq \\mathbb{N}\\), the upper density of \\(S\\) is defined as\n\\[ \\overline{d}(S) = \\limsup_{N \\to \\infty} \\frac{|S \\cap \\{1, 2, \\ldots, N\\}|}{N}. \\]\nDoes \\(A\\) have positive upper density, i.e., is \\(\\overline{d}(A) > 0\\)?",
  "status": "reported",
  "evidence_grade": "sourced",
  "scope": null,
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://www.erdosproblems.com/9",
      "locator": "See dataset.references[0] for the exact external source and locator."
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://www.erdosproblems.com/9",
    "locator": "See dataset.references[0] for the exact external source and locator."
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R1267",
      "title": "Resolve the stated acceptance condition",
      "object_type": "attempt",
      "relation": "addresses",
      "direction": "incoming"
    },
    {
      "slug": "erdos-problem-9",
      "title": "erdos problem 9",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

6Provenance

View source, identifiers, and projection details

Project: erdos-problem-9-source-review
Locator: See dataset.references[0] for the exact external source and locator.
License: CC0-1.0
Contributors: TheoremDB maintainers
Source: www.erdosproblems.com ↗
Public record: R1268
Stable alias: erdos-problem-9-claim-status-20260731
Projection: Reproduction fields are derived from the immutable record.

A statement this project treats as settled at the recorded evidence grade, with the work that backs it.

Current status and unresolved remainder

2Authored explanation

3Evidence

4How it connects

Addressed by

Recorded for

6Provenance

Record & provenance

Sign in to follow

Report a problem