AFTD Auto-Formalizing Theoretical Domains

greedyStep

def

Given a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop, a state (M, U) consisting of a finite set of matched unordered pairs M : Finset (Sym2 (ℝ × ℝ)) and a list of unmatched points U : List (ℝ × ℝ), and an arriving point v : ℝ × ℝ, greedyStep searches U in order for the first point u such that P holds on the insertion of s(u, v) into M; if found, it returns (insert s(u, v) M, U.erase u), and if no such u exists, it returns (M, U ++ [v]).

Statement

noncomputable def greedyStep (P : Finset (Sym2 (ℝ × ℝ)) → Prop)
    (state : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)) (v : ℝ × ℝ) :
    Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)
Defined in
arXiv:2610.23130, Section 1
Verified
22 Oct 2026
Axioms
none listed
Used by 4
  • greedyMatchingGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P…
  • not_greedy_fraction_le_of_blocking_geThe statement greedy_fraction_le_of_blocking_ge is false: The statement is false as written; a machine-checked refutation is provided.…
  • greedy_matching_fraction_ge_of_blocking_leLet P be a hereditary segment property. If β_P(ℓ) ≤ p (formalized by segment_blocking_bound_le P ℓ p), then on every duplicate-free list…
  • greedy_matching_fraction_le_of_blocking_geLet P be a hereditary segment property. If β_P(ℓ) ≥ p (formalized by segment_blocking_bound_ge P ℓ p), then there exists a duplicate-free…

Read back from the Lean

greedyStep is a noncomputable definition that takes: 1. a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop on finite sets of unordered pairs of points in $\mathbb{R}^2$, 2. a state state = (M, U) where M is a finite set of unordered pairs of points in $\mathbb{R}^2$ (Finset (Sym2 (ℝ × ℝ))) and U is a list of points in $\mathbb{R}^2$ (List (ℝ × ℝ)), and 3. a point v : ℝ × ℝ, and returns an updated pair (M', U') : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ) defined as follows: - It searches the list U for the first element u such that P (insert s(u, v) M) holds (where s(u, v) is the unordered pair of u and v). - If such a u is found, it returns (insert s(u, v) M, U.erase u) (inserting the edge {u, v} into M and erasing the first occurrence of u from U). - If no such u exists in U, it returns (M, U ++ [v]) (leaving M unchanged and appending v to the end of U).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- One step of the greedy matching algorithm upon arrival of a new point v. -/
noncomputable def greedyStep (P : Finset (Sym2 (ℝ × ℝ)) → Prop)
    (state : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)) (v : ℝ × ℝ) :
    Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ) := open scoped Classical in
  let (M, U) := state
  match U.find? (fun u => P (insert s(u, v) M)) with
  | some u => (insert s(u, v) M, U.erase u)
  | none => (M, U ++ [v])
See it in the graphDiscuss this resultChallenge it