Skip to content

Erdős problem 871

Let AA be an additive basis of order 22, and suppose 1A∗1A(n)→∞1_A\ast 1_A(n)\to \infty as n→∞n\to \infty. Can AA be partitioned into two disjoint additive bases of order 22?

Sources

The source's own material, retained exactly.

1 retained statement36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

871.lean

Retained formal statement1 of 1

Let AA be an additive basis of order 22, and suppose 1A∗1A(n)→∞1_A\ast 1_A(n)\to \infty as n→∞n\to \infty. Can AA be partitioned into two disjoint additive bases of order 22?

A question of Erdős and Nathanson [ErNa88], who proved this is true if 1A∗1A(n)>clog⁡n1_A\ast 1_A(n) > c\log n (for all large nn) for some constant c>(log⁡43)−1c>(\log\frac{4}{3})^{-1}. Erdős and Nathanson [ErNa89] also proved that for every tt there exists a basis AA of order 22 such that 1A∗1A(n)≥t1_A\ast 1_A(n)\geq t for all large nn and yet AA cannot be partitioned into two disjoint additive bases. This has been disproved by Larsen using Claude Opus 4.5 - in fact only a small modification of the argument of [ErNa89] is required.

FormalConjectures/ErdosProblems/871.leanErdos871.erdos_87111 linesExact file
False ↔  ∀ (A : Set ℕ),    ((∀ᶠ (n : ℕ) in Filter.atTop, ∃ a ∈ A, ∃ b ∈ A, a + b = n) ∧        ∀ (t : ℕ),          ∀ᶠ (n : ℕ) in Filter.atTop,            ∃ pairs, pairs.card ≥ t ∧ ∀ p ∈ pairs, p.1 ∈ A ∧ p.2 ∈ A ∧ p.1 + p.2 = n ∧ p.1 ≤ p.2) →      ∃ B C,        (∀ (x : ℕ), x ∈ A ↔ x ∈ B ∨ x ∈ C) ∧          Disjoint B C ∧            (∀ᶠ (n : ℕ) in Filter.atTop, ∃ a ∈ B, ∃ b ∈ B, a + b = n) ∧              ∀ᶠ (n : ℕ) in Filter.atTop, ∃ a ∈ C, ∃ b ∈ C, a + b = n
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.