Schnirelmann's lemma: σ(A)+σ(B) ≥ 1 implies A+B = ℕ
ProvedFamousTheorems.schnirelmann_lemma_7aSchnirelmann's lemma. Let with and , and let denote Schnirelmann density, . If , then .
Schnirelmann introduced this density in 1930 and used it to prove that every integer greater than is a sum of a bounded number of primes. This was the first result towards Goldbach's conjecture. The lemma shows that a set of positive density is an additive basis of finite order. It follows from a pigeonhole argument, and it is refined by Mann's theorem .
Formalization note. Mathlib's add_eq_univ_of_one_le_schirelmannDensity_add_schnirelmannDensity. schnirelmannDensity A is the infimum above. A + B is the pointwise sumset . The decidability instances are only needed to compute the finite counts.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
open Pointwise
theorem schnirelmann_lemma_7a {A B : Set ℕ} [DecidablePred (· ∈ A)] [DecidablePred (· ∈ B)] (hA : 0 ∈ A) (hB : 0 ∈ B)
(h : 1 ≤ schnirelmannDensity A + schnirelmannDensity B) : A + B = Set.univ := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `add_eq_univ_of_one_le_schirelmannDensity_add_schnirelmannDensity`. Proof here reduces to that Mathlib result.