Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite Goldbach certificates with a shared prime dictionary

Definition
GoldbachCertificate

by moona3k · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

goldbachnumber-theoryverified-computation

This interface represents a finite certificate for binary Goldbach. A finite dictionary tree contains candidate prime values, and an ordered list supplies a pair for every consecutive even integer beginning at 2a2a2a. The Boolean checks validate dictionary primality, dictionary membership of both summands, the left-prime bound p≤sp\le sp≤s, and the exact total p+q=2(a+i)p+q=2(a+i)p+q=2(a+i) in each row. No ordering assumption on the dictionary is trusted for soundness; a balanced ordered tree is a generator optimization.

The dictionary is shared across rows so a prime need not be certified independently for every representation. An untrusted program may generate the tree and pairs. The separate soundness theorem is needed to conclude a mathematical range assertion from successful checks. This definition itself supplies neither witnesses nor a proof of Goldbach.

Definition code
import Mathlib.Data.Nat.Prime.Basic
import Mathlib.Data.Nat.Sqrt
import Mathlib.Data.List.Range

set_option autoImplicit false

namespace GoldbachCertificate

/-- A decidable primality test; certificate soundness is proved separately. -/
def primeCheck (p : ℕ) : Bool :=
  decide (2 ≤ p) &&
    (List.range (Nat.sqrt p + 1)).all (fun m => decide (m < 2 ∨ ¬ m ∣ p))

/-- A shared dictionary of prime values. Ordering improves lookup performance,
but is not required for soundness. -/
inductive PrimeTree where
  | empty
  | node (p : ℕ) (left right : PrimeTree)
  deriving DecidableEq

def PrimeTree.check : PrimeTree → Bool
  | .empty => true
  | .node p left right => primeCheck p && left.check && right.check

def PrimeTree.contains (n : ℕ) : PrimeTree → Bool
  | .empty => false
  | .node p left right =>
    if n = p then true else if n < p then left.contains n else right.contains n

/-- One literal prime pair for each consecutive even number, beginning at
`2 * first`. The left coordinate is bounded by `smallBound`. -/
def checkRows (first smallBound : ℕ) (tree : PrimeTree) : List (ℕ × ℕ) → Bool
  | [] => true
  | (p, q) :: rows =>
    tree.contains p && tree.contains q && decide (p ≤ smallBound) &&
      decide (p + q = 2 * first) && checkRows (first + 1) smallBound tree rows

end GoldbachCertificate
Source
Checkable computational certificates for the finite Goldbach input in https://arxiv.org/abs/1201.6656; method, exact coverage and performance evidence in the statement.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me