AFTD Auto-Formalizing Theoretical Domains

greedy_matching_fraction_ge_of_blocking_le

theoremverifiedformalization

Let P be a hereditary segment property. If β_P(ℓ) ≤ p (formalized by segment_blocking_bound_le P ℓ p), then on every duplicate-free list pts of points in ℝ² in general position on which Greedy creates ℓ segments, Greedy matches at least a 2ℓ / (2ℓ + p) fraction of the input points, meaning (2ℓ)/(2ℓ+p) ≤ 2ℓ / pts.length.

Statement

theorem greedy_matching_fraction_ge_of_blocking_le
    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ)
    (hβ : segment_blocking_bound_le P ℓ p) (pts : List (ℝ × ℝ))
    (h_nodup : pts.Nodup) (h_gen : points_in_general_position (pts.toFinset : Set (ℝ × ℝ)))
    (h_card : (greedyMatching P pts).1.card = ℓ) :
    (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ)
Formalizes
arXiv:2610.23130 Theorem 1.2 (1)
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • segment_blocking_bound_leFor a segment property P on Finset (Sym2 (ℝ × ℝ)) and natural numbers ℓ and p, segment_blocking_bound_le P ℓ p asserts that every finite…
  • IsHereditarySegmentPropertyA predicate P on finite sets of unordered pairs in Sym2 (ℝ × ℝ) is a hereditary segment property if P holds on the empty finset and for…
  • points_in_general_positionA set S of points in the real plane ℝ × ℝ is in general position if for all pairwise distinct points p₁, p₂, p₃ in S, the three-element…
  • greedyMatchingGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P…
  • segment_endpointsGiven a finite set L : Finset (Sym2 (ℝ × ℝ)) of unordered pairs of points in ℝ × ℝ, segment_endpoints L is the finset of type Finset (ℝ ×…
  • greedyStepGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop, a state (M, U) consisting of a finite set of matched unordered pairs M : Finset (Sym2…
  • segments_block_points_propFor a predicate P on finite sets of unordered pairs in Sym2 (ℝ × ℝ), a finite set L of unordered pairs in Sym2 (ℝ × ℝ), and a finite set S…
  • greedyMatching_nilFor every predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop on finite sets of unordered pairs of points in ℝ × ℝ, greedyMatching P [] equals the…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 1

Read back from the Lean

Let $P$ be a property of finite sets of segments (unordered pairs of points in $\mathbb{R}^2$), and suppose $P$ is hereditary (it holds on the empty set, and if it holds for a set $t$, it holds for every subset $s \subseteq t$). Let $\ell, p \in \mathbb{N}$ such that $p$ is a blocking bound for $\ell$ under $P$: namely, for any finite set of segments $L$ of cardinality $\ell$ with $P(L)$ and any finite set of points $S \subset \mathbb{R}^2$, if the union of the endpoints of $L$ and the points of $S$ is in general position (no three distinct points are collinear), and $S$ is blocked by $L$ under $P$ (for every pair of distinct points $u, v \in S$, $P(L \cup \{s(u,v)\})$ is false), then $|S| \le p$. Let $pts$ be a duplicate-free list of points in $\mathbb{R}^2$ whose underlying set of points is in general position. If running the greedy matching algorithm on $pts$ with respect to $P$ produces a matching of cardinality $\ell$, then: $$\frac{2\ell}{2\ell + p} \le \frac{2\ell}{|pts|}$$ where $|pts|$ is the length of $pts$, and the division and values are in $\mathbb{R}$.

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

The proof, explained

The proof establishes that if the blocking bound β_P(ℓ) ≤ p holds for a hereditary segment property P, Greedy matches at least a 2ℓ / (2ℓ + p) fraction of the input points on any duplicate-free point set in general position yielding ℓ segments. An inductive loop invariant proves that throughout Greedy, the matched segments satisfy P, the unmatched points are blocked by the segments, and their union forms the input points. The blocking bound bounds the unmatched points by p, and the ℓ segments contribute at most 2ℓ endpoints, bounding the total input size by 2ℓ + p. Dividing 2ℓ by this upper bound yields the desired fraction lower bound.

  1. The endpoints of insert s(u, v) M are {u, v} ∪ segment_endpoints M.

    Unfolding the definition of segment endpoints as a big union over segments and distributing the union over the inserted segment.

    lines 6–10

    uses Finset.biUnion_insert

    lemma greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair
        (u v : ℝ × ℝ) (M : Finset (Sym2 (ℝ × ℝ))) :
        segment_endpoints (insert s(u, v) M) = {u, v} ∪ segment_endpoints M := by
      simp [segment_endpoints, Finset.biUnion_insert]
    
  2. The empty set of segments has at most 2 * 0 endpoints.

    Base case of induction on the set of segments L: the empty set has no endpoints, and 0 ≤ 0 holds by simplification.

    lines 11–15

    uses Finset.induction_on

    lemma greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le
        (L : Finset (Sym2 (ℝ × ℝ))) : (segment_endpoints L).card ≤ 2 * L.card := by
      classical
      induction L using Finset.induction_on with
      | empty => simp [segment_endpoints]
  3. Any finite set of segments L has at most 2 * |L| endpoints.

    By induction, each inserted segment s(u, v) adds at most its two endpoints {u, v}; by subadditivity of cardinality, the number of endpoints grows by at most 2.

    lines 16–26

    uses Sym2.ind, greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair, Finset.card_union_le, Nat.add_le_add, Finset.card_le_two, Finset.card_insert_of_notMem

      | insert a L ha ih =>
        induction a using Sym2.ind with
        | _ u v =>
          rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair]
          calc (({u, v} : Finset (ℝ × ℝ)) ∪ segment_endpoints L).card
              ≤ ({u, v} : Finset (ℝ × ℝ)).card + (segment_endpoints L).card :=
                  Finset.card_union_le _ _
            _ ≤ 2 + 2 * L.card := Nat.add_le_add Finset.card_le_two ih
            _ = 2 * (insert s(u, v) L).card := by
                  rw [Finset.card_insert_of_notMem ha]; ring
    
  4. In the empty list, erasing a does not contain a.

    Base case of induction on list l: [].erase a is empty, which contains no elements.

    lines 27–30

    lemma greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self
        (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) : a ∉ l.erase a := by
      induction l with
      | nil => simp
  5. In any duplicate-free list l, erasing a yields a list not containing a.

    For a non-empty duplicate-free list b :: t, if b = a, erasing a leaves t (which does not contain a because the list has no duplicates); if b ≠ a, erasing a recurses on t, so a is neither b nor in t.erase a by induction.

    lines 31–43

    uses List.nodup_cons, List.erase_cons_head, List.erase_cons, if_neg

      | cons b t ih =>
        rw [List.nodup_cons] at h
        obtain ⟨hbt, ht⟩ := h
        by_cases hba : b = a
        · subst hba
          rw [List.erase_cons_head]
          exact hbt
        · rw [List.erase_cons]
          simp only [beq_iff_eq]
          rw [if_neg hba]
          simp only [List.mem_cons, not_or]
          exact ⟨fun hab => hba hab.symm, ih ht⟩
    
  6. For a duplicate-free list l, an element x is in (l.erase a).toFinset if and only if x ∈ l.toFinset and x ≠ a.

    Any element of l.erase a belongs to l and cannot be a by the previous lemma; conversely, any element of l other than a is preserved by erase.

    lines 44–55

    uses List.mem_toFinset, List.mem_of_mem_erase, greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self, List.mem_erase_of_ne

    lemma greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset
        (l : List (ℝ × ℝ)) (h : l.Nodup) (a x : ℝ × ℝ) :
        x ∈ (l.erase a).toFinset ↔ x ∈ l.toFinset ∧ x ≠ a := by
      simp only [List.mem_toFinset]
      constructor
      · intro hx
        refine ⟨List.mem_of_mem_erase (a := x) (b := a) (l := l) hx, ?_⟩
        rintro rfl
        exact greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self l h x hx
      · rintro ⟨hx, hne⟩
        exact (List.mem_erase_of_ne (a := x) (b := a) (l := l) hne).mpr hx
    
  7. For a duplicate-free list l with a ∈ l, insert a (l.erase a).toFinset = l.toFinset.

    By extensionality: inserting a back into the elements of l.erase a covers a (which is in l) and all other elements of l, recovering l.toFinset.

    lines 56–70

    uses greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset, Or.inl, Or.inr

    lemma greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset
        (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) (ha : a ∈ l) :
        insert a (l.erase a).toFinset = l.toFinset := by
      ext x
      simp only [Finset.mem_insert, List.mem_toFinset,
        greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset l h a x]
      constructor
      · rintro (rfl | ⟨hx, _⟩)
        · exact ha
        · exact hx
      · intro hx
        by_cases hxa : x = a
        · exact Or.inl hxa
        · exact Or.inr ⟨hx, hxa⟩
    
  8. If E ∪ insert u Ke = W, then {u, a} ∪ E ∪ Ke = W ∪ {a}. automation

    Substituting W with E ∪ {u} ∪ Ke, both sides describe the set E ∪ Ke ∪ {u, a}; the goal is closed by propositional logic.

    lines 71–78

    lemma greedy_matching_fraction_ge_of_blocking_le_some_union
        (E Ke W : Finset (ℝ × ℝ)) (u a : ℝ × ℝ) (hE : E ∪ insert u Ke = W) :
        ({u, a} : Finset (ℝ × ℝ)) ∪ E ∪ Ke = W ∪ {a} := by
      rw [← hE]
      ext x
      simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton]
      tauto
    
  9. Unpack the inductive invariant for the state (M, U) and expand greedyStep into a search for an eligible match for point a.

    Extract the four components of the invariant (P M, U blocked by M, U duplicate-free, endpoints ∪ U = w) and case-split on whether List.find? finds a point u ∈ U that can match with a while preserving P.

    lines 79–93

    lemma greedy_matching_fraction_ge_of_blocking_le_step
        (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P)
        (w : List (ℝ × ℝ)) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) (a : ℝ × ℝ)
        (hinv : greedy_matching_fraction_ge_of_blocking_le_inv P w M U)
        (ha : a ∉ w.toFinset) :
        greedy_matching_fraction_ge_of_blocking_le_inv P (w ++ [a])
          (greedyStep P (M, U) a).1 (greedyStep P (M, U) a).2 := by
      obtain ⟨hPM, hblk, hUnd, heq⟩ := hinv
      classical
      let g : ℝ × ℝ → Bool := fun u => decide (P (insert s(u, a) M))
      have hgd : greedyStep P (M, U) a = (match List.find? g U with
          | some u => (insert s(u, a) M, U.erase u)
          | none => (M, U ++ [a])) := rfl
      rw [hgd]
      cases hf : List.find? g U with
  10. When an eligible point u ∈ U is matched with a, P holds for the new matching, remaining points are blocked, and U.erase u has no duplicates.

    By construction, P holds on insert s(u, a) M. Any two points in U.erase u cannot form a valid segment with M by the inductive hypothesis, hence not with insert s(u, a) M because P is hereditary. Erasing u from a duplicate-free list preserves the duplicate-free property.

    lines 94–104

    uses of_decide_eq_true, List.find?_some, greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset, Finset.insert_subset_insert, Finset.subset_insert, List.Nodup.erase

      | some u =>
          refine ⟨?_, ?_, ?_, ?_⟩
          · exact of_decide_eq_true (by simpa [g] using List.find?_some hf)
          · intro x y hx hy hxy hbig
            obtain ⟨hxU, hxu⟩ :=
              (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u x).mp hx
            obtain ⟨hyU, hyu⟩ :=
              (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u y).mp hy
            exact hblk hxU hyU hxy
              (hP.2 (Finset.insert_subset_insert s(x, y) (Finset.subset_insert s(u, a) M)) hbig)
          · exact List.Nodup.erase u hUnd
  11. When u is matched with a, the union of segment endpoints and remaining unmatched points equals (w ++ [a]).toFinset.

    The new endpoints are {u, a} ∪ segment_endpoints M, and the remaining unmatched points are (U.erase u).toFinset. Since insert u (U.erase u).toFinset = U.toFinset, the union rearrangement lemma gives w.toFinset ∪ {a}, which equals (w ++ [a]).toFinset.

    lines 105–115

    uses greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair, List.mem_of_find?_eq_some, greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset, greedy_matching_fraction_ge_of_blocking_le_some_union, List.toFinset_append

          · rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair]
            have hu : u ∈ U := List.mem_of_find?_eq_some hf
            have hUins : insert u (U.erase u).toFinset = U.toFinset :=
              greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset U hUnd u hu
            have hE : segment_endpoints M ∪ insert u (U.erase u).toFinset = w.toFinset := by
              rw [hUins]; exact heq
            rw [greedy_matching_fraction_ge_of_blocking_le_some_union
              (segment_endpoints M) (U.erase u).toFinset w.toFinset u a hE]
            rw [List.toFinset_append]
            simp
      | none =>
  12. When no point in U can match with a, P M still holds and U ∪ {a} is blocked by M.

    The matching M is unchanged, so P M holds. For any distinct x, y ∈ U ∪ {a}, if both are in U they are blocked by the induction hypothesis; if one is a and the other z ∈ U, the fact that find? returned none implies insert s(z, a) M does not satisfy P.

    lines 116–140

    uses of_decide_eq_false, Sym2.eq_swap

          refine ⟨?_, ?_, ?_, ?_⟩
          · exact hPM
          · intro x y hx hy hxy
            have hxn : x ∈ U.toFinset ∨ x = a := by
              rcases (by simpa using hx : x = a ∨ x ∈ U.toFinset) with h | h
              · exact Or.inr h
              · exact Or.inl h
            have hyn : y ∈ U.toFinset ∨ y = a := by
              rcases (by simpa using hy : y = a ∨ y ∈ U.toFinset) with h | h
              · exact Or.inr h
              · exact Or.inl h
            have hg : ∀ z ∈ U.toFinset, ¬ P (insert s(z, a) M) := by
              intro z hz
              have hzf : g z = false := by
                have h1 : ¬ g z = true := (List.find?_eq_none.mp hf) z (List.mem_toFinset.mp hz)
                exact Bool.eq_false_iff.mpr h1
              exact of_decide_eq_false (by simpa [g] using hzf)
            rcases hxn with hxU | rfl
            · rcases hyn with hyU | rfl
              · exact hblk hxU hyU hxy
              · exact hg x hxU
            · rcases hyn with hyU | rfl
              · have h1 := hg y hyU
                rwa [Sym2.eq_swap] at h1
              · exact absurd rfl hxy
  13. When a remains unmatched, U ++ [a] has no duplicates and the union of endpoints and unmatched points equals (w ++ [a]).toFinset.

    Since a ∉ w and U ⊆ w, a ∉ U, so appending a preserves the duplicate-free property. The union of endpoints and U ++ [a] associates to (segment_endpoints M ∪ U) ∪ {a} = w ∪ {a}.

    lines 141–153

    uses Finset.subset_union_right, List.mem_toFinset, List.nodup_append, List.nodup_singleton, List.mem_singleton, List.toFinset_append, Finset.union_assoc

          · have hUsub : U.toFinset ⊆ w.toFinset := by
              rw [← heq]; exact Finset.subset_union_right
            have haUf : a ∉ U.toFinset := fun h => ha (hUsub h)
            have haU : a ∉ U := fun h => haUf (List.mem_toFinset.mpr h)
            rw [List.nodup_append]
            refine ⟨hUnd, List.nodup_singleton a, ?_⟩
            intro x hx y hy
            rw [List.mem_singleton] at hy
            subst hy
            exact fun hxa => haU (hxa ▸ hx)
          · rw [List.toFinset_append, ← Finset.union_assoc, heq]
            simp [List.toFinset_append]
    
  14. The loop invariant holds at the base case pts = [].

    Greedy matching on the empty list returns (∅, []), for which P holds by the hereditary property, blocking is vacuously true on the empty set, [] has no duplicates, and the endpoints union is empty.

    lines 154–167

    uses greedyMatching_nil

    lemma greedy_matching_fraction_ge_of_blocking_le_inv_nodup
        (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P)
        (pts : List (ℝ × ℝ)) (h : pts.Nodup) :
        greedy_matching_fraction_ge_of_blocking_le_inv P pts
          (greedyMatching P pts).1 (greedyMatching P pts).2 := by
      classical
      induction pts using List.reverseRecOn with
      | nil =>
        rw [greedyMatching_nil]
        refine ⟨hP.1, ?_, ?_, ?_⟩
        · intro u v hu hv huv
          simp at hu
        · simp
        · simp [segment_endpoints]
  15. The loop invariant holds after running Greedy on any duplicate-free list of points.

    By reverse induction on pts, adding the next point a using greedyStep preserves the invariant by greedy_matching_fraction_ge_of_blocking_le_step, since a ∉ w follows from pts having no duplicates.

    lines 168–180

    uses List.nodup_append, List.mem_toFinset, List.foldl_append, greedy_matching_fraction_ge_of_blocking_le_step, Prod.mk.eta

      | append_singleton w a ih =>
        obtain ⟨hw, _, hdisj⟩ := List.nodup_append.mp h
        have ha : a ∉ w.toFinset := by
          intro haw
          exact (hdisj a (List.mem_toFinset.mp haw) a (by simp)) rfl
        have hgm : greedyMatching P (w ++ [a]) = greedyStep P (greedyMatching P w) a := by
          simp [greedyMatching, List.foldl_append]
        rw [hgm]
        have hstep := greedy_matching_fraction_ge_of_blocking_le_step P hP w
          (greedyMatching P w).1 (greedyMatching P w).2 a (ih hw) ha
        rw [Prod.mk.eta] at hstep
        exact hstep
    
  16. The state after running Greedy on pts satisfies the loop invariant.

    Instantiate greedy_matching_fraction_ge_of_blocking_le_inv_nodup with the duplicate-free list pts.

    lines 181–190

    uses greedy_matching_fraction_ge_of_blocking_le_inv_nodup

    /-- Part (1) of Theorem 1.2: if β_P(ℓ) ≤ p, Greedy matches at least a 2ℓ/(2ℓ+p) fraction on every input producing ℓ segments. -/
    theorem greedy_matching_fraction_ge_of_blocking_le
        (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ)
        (hβ : segment_blocking_bound_le P ℓ p) (pts : List (ℝ × ℝ))
        (h_nodup : pts.Nodup) (h_gen : points_in_general_position (pts.toFinset : Set (ℝ × ℝ)))
        (h_card : (greedyMatching P pts).1.card = ℓ) :
        (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ) := by
      classical
      obtain ⟨hPM, hblk, hUnd, heq⟩ :=
        greedy_matching_fraction_ge_of_blocking_le_inv_nodup P hP pts h_nodup
  17. The union of the segment endpoints and the unmatched points is in general position.

    Because the union of the segment endpoints and the unmatched points equals the set of input points pts, it inherits general position from the hypothesis on pts.

    lines 191–195

    uses Finset.coe_union

      have hgen' : points_in_general_position
          ((↑(segment_endpoints (greedyMatching P pts).1) : Set (ℝ × ℝ)) ∪
            (↑(greedyMatching P pts).2.toFinset : Set (ℝ × ℝ))) := by
        rw [← Finset.coe_union, heq]
        exact h_gen
  18. There are at most p unmatched points.

    By definition of the blocking bound β_P(ℓ) ≤ p, any set of points in general position blocked by ℓ segments satisfying P has cardinality at most p.

    lines 196–197

      have hUcard : (greedyMatching P pts).2.toFinset.card ≤ p :=
        hβ (greedyMatching P pts).1 (greedyMatching P pts).2.toFinset h_card hPM hgen' hblk
  19. The ℓ matched segments have at most 2ℓ endpoints.

    Applying greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le to the matching of size ℓ shows that its endpoints number at most 2ℓ.

    lines 198–201

    uses greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le

      have hends : (segment_endpoints (greedyMatching P pts).1).card ≤ 2 * ℓ := by
        have h := greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le
          (greedyMatching P pts).1
        rwa [h_card] at h
  20. The total number of input points is at most 2ℓ + p.

    The set of input points is the union of the segment endpoints (at most 2ℓ) and the unmatched points (at most p); by subadditivity of cardinality, |pts| ≤ 2ℓ + p.

    lines 202–209

    uses List.toFinset_card_of_nodup, Finset.card_union_le, Nat.add_le_add

      have hlen : pts.length ≤ 2 * ℓ + p := by
        rw [← List.toFinset_card_of_nodup h_nodup]
        calc pts.toFinset.card
            = (segment_endpoints (greedyMatching P pts).1 ∪
                (greedyMatching P pts).2.toFinset).card := by rw [heq]
          _ ≤ (segment_endpoints (greedyMatching P pts).1).card +
                (greedyMatching P pts).2.toFinset.card := Finset.card_union_le _ _
          _ ≤ 2 * ℓ + p := Nat.add_le_add hends hUcard
  21. The desired inequality holds when ℓ = 0.

    When ℓ = 0, the numerator 2ℓ is 0, so both sides evaluate to 0 and the inequality holds trivially.

    lines 210–212

    uses Nat.eq_zero_or_pos

      rcases Nat.eq_zero_or_pos ℓ with hℓ0 | hℓpos
      · subst hℓ0
        simp
  22. When ℓ > 0, the input list pts is non-empty.

    If pts were empty, Greedy would produce 0 segments, contradicting ℓ > 0. Thus |pts| > 0.

    lines 213–221

    uses Nat.eq_zero_or_pos, List.length_eq_zero_iff, greedyMatching_nil

      · have hnpos : 0 < pts.length := by
          rcases Nat.eq_zero_or_pos pts.length with h0 | hpos
          · exfalso
            have hnil : pts = [] := List.length_eq_zero_iff.mp h0
            subst hnil
            rw [greedyMatching_nil] at h_card
            simp at h_card
            omega
          · exact hpos
  23. The inequality (2ℓ) / (2ℓ + p) ≤ 2ℓ / |pts| holds.

    Since 0 < |pts| ≤ 2ℓ + p and 2ℓ ≥ 0, dividing 2ℓ by the larger quantity 2ℓ + p yields a smaller or equal quotient than dividing by |pts|.

    lines 222–224

    uses div_le_div_of_nonneg_left

        have hden : (0 : ℝ) < (pts.length : ℝ) := by exact_mod_cast hnpos
        have hle : (pts.length : ℝ) ≤ 2 * (ℓ : ℝ) + (p : ℝ) := by exact_mod_cast hlen
        exact div_le_div_of_nonneg_left (by positivity) hden hle
Finset.biUnion_insert
The big union of a function over insert a s is the value at a united with the big union over s.
Finset.induction_on
Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved by inserting an element not already in the set.
Sym2.ind
Every element of the symmetric square Sym2 α is an unordered pair s(u, v).
greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair
Adding a segment s(u, v) to a set of segments M adds {u, v} to its set of endpoints.
Finset.card_union_le
The cardinality of a union of finite sets is at most the sum of their cardinalities.
Nat.add_le_add
Adding inequalities preserves ordering on natural numbers.
Finset.card_le_two
A pair set {a, b} has cardinality at most 2.
Finset.card_insert_of_notMem
Inserting an element not in a finite set increases its cardinality by 1.
List.nodup_cons
A list b :: t has no duplicates if and only if b ∉ t and t has no duplicates.
List.erase_cons_head
Erasing the head element a from a :: l leaves l.
List.erase_cons
Erasing from b :: l inspects whether b = a, returning l if equal, and b :: l.erase a otherwise.
if_neg
An if-then-else on a false condition simplifies to the else branch.
List.mem_toFinset
An element belongs to l.toFinset if and only if it belongs to l.
List.mem_of_mem_erase
Any element of l.erase b belongs to l.
greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self
For a duplicate-free list l, an element a does not belong to l.erase a.
List.mem_erase_of_ne
For a ≠ b, an element belongs to l.erase b if and only if it belongs to l.
greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset
For a duplicate-free list l, x ∈ (l.erase a).toFinset if and only if x ∈ l and x ≠ a.
Or.inl
Constructs a proof of a ∨ b from a proof of a.
Or.inr
Constructs a proof of a ∨ b from a proof of b.
of_decide_eq_true
If decide p evaluates to true, then p is true.
List.find?_some
If List.find? finds an element, that element satisfies the predicate.
Finset.insert_subset_insert
If s ⊆ t, then insert a s ⊆ insert a t.
Finset.subset_insert
A set s is a subset of insert a s.
List.Nodup.erase
Erasing an element from a duplicate-free list preserves the duplicate-free property.
List.mem_of_find?_eq_some
If List.find? finds an element in l, that element belongs to l.
greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset
For a duplicate-free list l and a ∈ l, inserting a into (l.erase a).toFinset recovers l.toFinset.
greedy_matching_fraction_ge_of_blocking_le_some_union
If E ∪ insert u Ke = W, then {u, a} ∪ E ∪ Ke = W ∪ {a}.
List.toFinset_append
The set of elements of an appended list is the union of their sets of elements.
of_decide_eq_false
If decide p evaluates to false, then ¬p is true.
Sym2.eq_swap
The unordered pair s(a, b) equals s(b, a).
Finset.subset_union_right
A set s₂ is a subset of s₁ ∪ s₂.
List.nodup_append
The concatenation of two lists has no duplicates if and only if each has no duplicates and they are disjoint.
List.nodup_singleton
A singleton list [a] has no duplicates.
List.mem_singleton
An element belongs to [b] if and only if it equals b.
Finset.union_assoc
Union of finite sets is associative.
greedyMatching_nil
Greedy matching on the empty list produces no segments and no unmatched points.
List.foldl_append
Folding over an appended list equals folding over the first list, then over the second.
greedy_matching_fraction_ge_of_blocking_le_step
The greedy matching invariant is preserved when a new point is processed by greedyStep.
Prod.mk.eta
Every pair p satisfies (p.1, p.2) = p.
greedy_matching_fraction_ge_of_blocking_le_inv_nodup
The greedy matching invariant holds after running on any duplicate-free list of points.
Finset.coe_union
The set coercion of a union of finite sets is the union of their set coercions.
greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le
A set of segments L has at most 2 * |L| endpoints.
List.toFinset_card_of_nodup
The cardinality of the set of elements of a duplicate-free list equals its length.
Nat.eq_zero_or_pos
Every natural number is either 0 or strictly positive.
List.length_eq_zero_iff
A list has length 0 if and only if it is empty.
div_le_div_of_nonneg_left
If c ≥ 0 and 0 < a ≤ b, then c / b ≤ c / a.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

def greedy_matching_fraction_ge_of_blocking_le_inv (P : Finset (Sym2 (ℝ × ℝ)) → Prop)    (w : List (ℝ × ℝ)) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) : Prop :=  P M ∧ segments_block_points_prop P M U.toFinset ∧ U.Nodup ∧    segment_endpoints M ∪ U.toFinset = w.toFinsetlemma greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair    (u v : ℝ × ℝ) (M : Finset (Sym2 (ℝ × ℝ))) :    segment_endpoints (insert s(u, v) M) = {u, v} ∪ segment_endpoints M := by  simp [segment_endpoints, Finset.biUnion_insert]lemma greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le    (L : Finset (Sym2 (ℝ × ℝ))) : (segment_endpoints L).card ≤ 2 * L.card := by  classical  induction L using Finset.induction_on with  | empty => simp [segment_endpoints]  | insert a L ha ih =>    induction a using Sym2.ind with    | _ u v =>      rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair]      calc (({u, v} : Finset (ℝ × ℝ)) ∪ segment_endpoints L).card          ≤ ({u, v} : Finset (ℝ × ℝ)).card + (segment_endpoints L).card :=              Finset.card_union_le _ _        _ ≤ 2 + 2 * L.card := Nat.add_le_add Finset.card_le_two ih        _ = 2 * (insert s(u, v) L).card := by              rw [Finset.card_insert_of_notMem ha]; ringlemma greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self    (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) : a ∉ l.erase a := by  induction l with  | nil => simp  | cons b t ih =>    rw [List.nodup_cons] at h    obtain ⟨hbt, ht⟩ := h    by_cases hba : b = a    · subst hba      rw [List.erase_cons_head]      exact hbt    · rw [List.erase_cons]      simp only [beq_iff_eq]      rw [if_neg hba]      simp only [List.mem_cons, not_or]      exact ⟨fun hab => hba hab.symm, ih ht⟩lemma greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset    (l : List (ℝ × ℝ)) (h : l.Nodup) (a x : ℝ × ℝ) :    x ∈ (l.erase a).toFinset ↔ x ∈ l.toFinset ∧ x ≠ a := by  simp only [List.mem_toFinset]  constructor  · intro hx    refine ⟨List.mem_of_mem_erase (a := x) (b := a) (l := l) hx, ?_⟩    rintro rfl    exact greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self l h x hx  · rintro ⟨hx, hne⟩    exact (List.mem_erase_of_ne (a := x) (b := a) (l := l) hne).mpr hxlemma greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset    (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) (ha : a ∈ l) :    insert a (l.erase a).toFinset = l.toFinset := by  ext x  simp only [Finset.mem_insert, List.mem_toFinset,    greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset l h a x]  constructor  · rintro (rfl | ⟨hx, _⟩)    · exact ha    · exact hx  · intro hx    by_cases hxa : x = a    · exact Or.inl hxa    · exact Or.inr ⟨hx, hxa⟩lemma greedy_matching_fraction_ge_of_blocking_le_some_union    (E Ke W : Finset (ℝ × ℝ)) (u a : ℝ × ℝ) (hE : E ∪ insert u Ke = W) :    ({u, a} : Finset (ℝ × ℝ)) ∪ E ∪ Ke = W ∪ {a} := by  rw [← hE]  ext x  simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton]  tautolemma greedy_matching_fraction_ge_of_blocking_le_step    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P)    (w : List (ℝ × ℝ)) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) (a : ℝ × ℝ)    (hinv : greedy_matching_fraction_ge_of_blocking_le_inv P w M U)    (ha : a ∉ w.toFinset) :    greedy_matching_fraction_ge_of_blocking_le_inv P (w ++ [a])      (greedyStep P (M, U) a).1 (greedyStep P (M, U) a).2 := by  obtain ⟨hPM, hblk, hUnd, heq⟩ := hinv  classical  let g : ℝ × ℝ → Bool := fun u => decide (P (insert s(u, a) M))  have hgd : greedyStep P (M, U) a = (match List.find? g U with      | some u => (insert s(u, a) M, U.erase u)      | none => (M, U ++ [a])) := rfl  rw [hgd]  cases hf : List.find? g U with  | some u =>      refine ⟨?_, ?_, ?_, ?_⟩      · exact of_decide_eq_true (by simpa [g] using List.find?_some hf)      · intro x y hx hy hxy hbig        obtain ⟨hxU, hxu⟩ :=          (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u x).mp hx        obtain ⟨hyU, hyu⟩ :=          (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u y).mp hy        exact hblk hxU hyU hxy          (hP.2 (Finset.insert_subset_insert s(x, y) (Finset.subset_insert s(u, a) M)) hbig)      · exact List.Nodup.erase u hUnd      · rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair]        have hu : u ∈ U := List.mem_of_find?_eq_some hf        have hUins : insert u (U.erase u).toFinset = U.toFinset :=          greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset U hUnd u hu        have hE : segment_endpoints M ∪ insert u (U.erase u).toFinset = w.toFinset := by          rw [hUins]; exact heq        rw [greedy_matching_fraction_ge_of_blocking_le_some_union          (segment_endpoints M) (U.erase u).toFinset w.toFinset u a hE]        rw [List.toFinset_append]        simp  | none =>      refine ⟨?_, ?_, ?_, ?_⟩      · exact hPM      · intro x y hx hy hxy        have hxn : x ∈ U.toFinset ∨ x = a := by          rcases (by simpa using hx : x = a ∨ x ∈ U.toFinset) with h | h          · exact Or.inr h          · exact Or.inl h        have hyn : y ∈ U.toFinset ∨ y = a := by          rcases (by simpa using hy : y = a ∨ y ∈ U.toFinset) with h | h          · exact Or.inr h          · exact Or.inl h        have hg : ∀ z ∈ U.toFinset, ¬ P (insert s(z, a) M) := by          intro z hz          have hzf : g z = false := by            have h1 : ¬ g z = true := (List.find?_eq_none.mp hf) z (List.mem_toFinset.mp hz)            exact Bool.eq_false_iff.mpr h1          exact of_decide_eq_false (by simpa [g] using hzf)        rcases hxn with hxU | rfl        · rcases hyn with hyU | rfl          · exact hblk hxU hyU hxy          · exact hg x hxU        · rcases hyn with hyU | rfl          · have h1 := hg y hyU            rwa [Sym2.eq_swap] at h1          · exact absurd rfl hxy      · have hUsub : U.toFinset ⊆ w.toFinset := by          rw [← heq]; exact Finset.subset_union_right        have haUf : a ∉ U.toFinset := fun h => ha (hUsub h)        have haU : a ∉ U := fun h => haUf (List.mem_toFinset.mpr h)        rw [List.nodup_append]        refine ⟨hUnd, List.nodup_singleton a, ?_⟩        intro x hx y hy        rw [List.mem_singleton] at hy        subst hy        exact fun hxa => haU (hxa ▸ hx)      · rw [List.toFinset_append, ← Finset.union_assoc, heq]        simp [List.toFinset_append]lemma greedy_matching_fraction_ge_of_blocking_le_inv_nodup    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P)    (pts : List (ℝ × ℝ)) (h : pts.Nodup) :    greedy_matching_fraction_ge_of_blocking_le_inv P pts      (greedyMatching P pts).1 (greedyMatching P pts).2 := by  classical  induction pts using List.reverseRecOn with  | nil =>    rw [greedyMatching_nil]    refine ⟨hP.1, ?_, ?_, ?_⟩    · intro u v hu hv huv      simp at hu    · simp    · simp [segment_endpoints]  | append_singleton w a ih =>    obtain ⟨hw, _, hdisj⟩ := List.nodup_append.mp h    have ha : a ∉ w.toFinset := by      intro haw      exact (hdisj a (List.mem_toFinset.mp haw) a (by simp)) rfl    have hgm : greedyMatching P (w ++ [a]) = greedyStep P (greedyMatching P w) a := by      simp [greedyMatching, List.foldl_append]    rw [hgm]    have hstep := greedy_matching_fraction_ge_of_blocking_le_step P hP w      (greedyMatching P w).1 (greedyMatching P w).2 a (ih hw) ha    rw [Prod.mk.eta] at hstep    exact hstep/-- Part (1) of Theorem 1.2: if β_P(ℓ) ≤ p, Greedy matches at least a 2ℓ/(2ℓ+p) fraction on every input producing ℓ segments. -/theorem greedy_matching_fraction_ge_of_blocking_le    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ)    (hβ : segment_blocking_bound_le P ℓ p) (pts : List (ℝ × ℝ))    (h_nodup : pts.Nodup) (h_gen : points_in_general_position (pts.toFinset : Set (ℝ × ℝ)))    (h_card : (greedyMatching P pts).1.card = ℓ) :    (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ) := by  classical  obtain ⟨hPM, hblk, hUnd, heq⟩ :=    greedy_matching_fraction_ge_of_blocking_le_inv_nodup P hP pts h_nodup  have hgen' : points_in_general_position      ((↑(segment_endpoints (greedyMatching P pts).1) : Set (ℝ × ℝ)) ∪        (↑(greedyMatching P pts).2.toFinset : Set (ℝ × ℝ))) := by    rw [← Finset.coe_union, heq]    exact h_gen  have hUcard : (greedyMatching P pts).2.toFinset.card ≤ p :=    hβ (greedyMatching P pts).1 (greedyMatching P pts).2.toFinset h_card hPM hgen' hblk  have hends : (segment_endpoints (greedyMatching P pts).1).card ≤ 2 * ℓ := by    have h := greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le      (greedyMatching P pts).1    rwa [h_card] at h  have hlen : pts.length ≤ 2 * ℓ + p := by    rw [← List.toFinset_card_of_nodup h_nodup]    calc pts.toFinset.card        = (segment_endpoints (greedyMatching P pts).1 ∪            (greedyMatching P pts).2.toFinset).card := by rw [heq]      _ ≤ (segment_endpoints (greedyMatching P pts).1).card +            (greedyMatching P pts).2.toFinset.card := Finset.card_union_le _ _      _ ≤ 2 * ℓ + p := Nat.add_le_add hends hUcard  rcases Nat.eq_zero_or_pos ℓ with hℓ0 | hℓpos  · subst hℓ0    simp  · have hnpos : 0 < pts.length := by      rcases Nat.eq_zero_or_pos pts.length with h0 | hpos      · exfalso        have hnil : pts = [] := List.length_eq_zero_iff.mp h0        subst hnil        rw [greedyMatching_nil] at h_card        simp at h_card        omega      · exact hpos    have hden : (0 : ℝ) < (pts.length : ℝ) := by exact_mod_cast hnpos    have hle : (pts.length : ℝ) ≤ 2 * (ℓ : ℝ) + (p : ℝ) := by exact_mod_cast hlen    exact div_le_div_of_nonneg_left (by positivity) hden hle
See it in the graphDiscuss this resultChallenge it