AFTD Auto-Formalizing Theoretical Domains

greedy_matching_fraction_le_of_blocking_ge

theoremverifiedformalization

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

Statement

theorem greedy_matching_fraction_le_of_blocking_ge
    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ)
    (hβ : segment_blocking_bound_ge P ℓ p) :
    ∃ pts : List (ℝ × ℝ), pts.Nodup ∧ points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) ∧
      (greedyMatching P pts).1.card = ℓ ∧
      (2 * (ℓ : ℝ)) / (pts.length : ℝ) ≤ (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ))
Formalizes
arXiv:2610.23130 Theorem 1.2 (2)
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • segment_blocking_bound_geFor a segment property P on Finset (Sym2 (ℝ × ℝ)) and natural numbers ℓ and p, segment_blocking_bound_ge P ℓ p asserts that there exists a…
  • 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…
Used by 1

Read back from the Lean

Let P be a property of finite sets of segments (unordered pairs of points in ℝ²), and let ℓ and p be natural numbers. Assume: 1. hP: P is hereditary, meaning P ∅ holds and for all finite sets of segments s ⊆ t, if P t holds then P s holds. 2. hβ: there exists a finite set of segments L and a finite set of points S in ℝ² such that: - L has cardinality ℓ, - P L holds, - the set of endpoints of segments in L has cardinality 2 * ℓ (i.e., the segments are pairwise vertex-disjoint and non-degenerate), - the endpoints of L are disjoint from S, - the union of the endpoints of L and S is in general position (no three distinct points are collinear), - L blocks S under P (for all distinct u, v ∈ S, P (insert s(u, v) L) is false), and - S has cardinality at least p. Then, there exists a list of points pts in ℝ² such that: 1. pts has no duplicate elements (pts.Nodup), 2. the points in pts are in general position (no three distinct points in pts.toFinset are collinear), 3. the greedy matching algorithm run on pts with respect to P produces a matching of cardinality ℓ, and 4. the ratio of matched vertices to total vertices satisfies: (2 * ℓ : ℝ) / (pts.length : ℝ) ≤ (2 * ℓ : ℝ) / (2 * ℓ + p : ℝ).

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 constructs an adversarial input sequence pts for the online Greedy matching algorithm by first presenting the endpoints of a target segment set L in adjacent pairs, followed by all points of a blocked set S. On the segment endpoints, Greedy buffers the first endpoint of each segment and immediately matches it with the second because the segment property P is hereditary, reconstructing the matching L and leaving the buffer empty. On the subsequent points from S, the blocking property ensures that no two points in S can form an admissible segment under P, forcing Greedy to append every point of S to the buffer without creating any new matches. The resulting sequence contains 2ℓ + |S| distinct points in general position, on which Greedy creates exactly ℓ segments and matches a fraction 2ℓ / (2ℓ + |S|) ≤ 2ℓ / (2ℓ + p) of the points.

  1. The endpoint set of the representative pair of an unordered pair s(u, v) is {u, v}.

    By greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec, the representative pair formed into an unordered pair equals s(u, v). By Sym2.eq_iff, two unordered pairs are equal if and only if their coordinates match directly or swapped. In the first case the endpoint set is {u, v}, and in the second it is {v, u}, which equals {u, v} by Finset.pair_comm.

    lines 17–21

    uses greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec, Sym2.eq_iff, Finset.pair_comm

      have h := greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec (s(u, v))
      rw [Sym2.eq_iff] at h
      rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩
      · rw [h1, h2]
      · rw [h1, h2, Finset.pair_comm]
  2. The endpoint set of a segment collection L is the union of endpointsOf e over all e ∈ L.

    Unfolding segment_endpoints, which is defined as a union over L, function extensionality reduces the claim to showing that the endpoints of each segment e equal endpointsOf e. Representing e as s(u, v) using its representative pair, this follows from greedy_matching_fraction_le_of_blocking_ge_rep_pair_eq.

    lines 33–41

    uses greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec, greedy_matching_fraction_le_of_blocking_ge_rep_pair_eq

      unfold segment_endpoints
      congr 1
      funext e
      obtain ⟨u, v, rfl⟩ :
          ∃ u v, e = s(u, v) :=
        ⟨_, _, (greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec e).symm⟩
      simp only [greedy_matching_fraction_le_of_blocking_ge_endpointsOf]
      rw [greedy_matching_fraction_le_of_blocking_ge_rep_pair_eq]
      rfl
  3. A point x belongs to segment_endpoints L if and only if x is the first or second coordinate of the representative pair of some e ∈ L.

    Rewriting segment_endpoints L as the union of endpointsOf e via greedy_matching_fraction_le_of_blocking_ge_segment_endpoints_eq_biUnion, membership in the union is equivalent by Finset.mem_biUnion to belonging to endpointsOf e for some e ∈ L. By definition of endpointsOf e as the two-element set containing the representative's coordinates, x belongs to it if and only if x equals one of those two coordinates.

    lines 49–61

    uses greedy_matching_fraction_le_of_blocking_ge_segment_endpoints_eq_biUnion, Finset.mem_biUnion

      rw [greedy_matching_fraction_le_of_blocking_ge_segment_endpoints_eq_biUnion]
      constructor
      · intro h
        rw [Finset.mem_biUnion] at h
        obtain ⟨e, he, hxe⟩ := h
        exact ⟨e, he, by
          simpa [greedy_matching_fraction_le_of_blocking_ge_endpointsOf, Finset.mem_insert,
            Finset.mem_singleton] using hxe⟩
      · rintro ⟨e, he, h | h⟩
        · rw [Finset.mem_biUnion]
          exact ⟨e, he, by simp [greedy_matching_fraction_le_of_blocking_ge_endpointsOf, h]⟩
        · rw [Finset.mem_biUnion]
          exact ⟨e, he, by simp [greedy_matching_fraction_le_of_blocking_ge_endpointsOf, h]⟩
  4. The finite set formed by flattening the list of representative pairs of L equals segment_endpoints L.

    By finset extensionality (Finset.ext), an element x belongs to the flattened list's finset if and only if it appears in the list (List.mem_toFinset), which means x is a coordinate of some representative pair of e ∈ L. By greedy_matching_fraction_le_of_blocking_ge_mem_segment_endpoints_iff, this is equivalent to x ∈ segment_endpoints L.

    lines 73–84

    uses Finset.ext, List.mem_toFinset, greedy_matching_fraction_le_of_blocking_ge_mem_segment_endpoints_iff

      apply Finset.ext
      intro x
      rw [List.mem_toFinset, greedy_matching_fraction_le_of_blocking_ge_mem_segment_endpoints_iff]
      simp only [greedy_matching_fraction_le_of_blocking_ge_pairList, List.mem_flatMap, List.mem_map,
        List.mem_cons, List.not_mem_nil, or_false, Finset.mem_toList]
      constructor
      · rintro ⟨p, ⟨e, he, rfl⟩, h | h⟩
        · exact ⟨e, he, Or.inl h⟩
        · exact ⟨e, he, Or.inr h⟩
      · rintro ⟨e, he, h | h⟩
        · exact ⟨_, ⟨e, he, rfl⟩, Or.inl h⟩
        · exact ⟨_, ⟨e, he, rfl⟩, Or.inr h⟩
  5. The length of the flattened list of representative pairs of L is 2 * |L|. automation

    Flattening replaces each segment's representative with a 2-element list. By List.length_flatMap, the total length is the sum of these lengths, which evaluates to 2 * |L| by linear arithmetic.

    lines 91–95

    uses List.length_flatMap

      simp only [greedy_matching_fraction_le_of_blocking_ge_pairList]
      rw [List.length_flatMap]
      simp only [List.length_cons, List.length_nil, List.map_map]
      simp
      omega
  6. Any list whose finset cardinality equals its length is duplicate-free.

    By induction on the list. The empty list is trivially duplicate-free. For a cons list a :: t, if a were in t, inserting a would not increase the cardinality (Finset.insert_eq_of_mem), forcing |t.toFinset| = t.length + 1, contradicting List.toFinset_card_le. Thus a ∉ t, so inserting a increments the cardinality by Finset.card_insert_of_notMem, leaving |t.toFinset| = t.length. The induction hypothesis then ensures t has no duplicates, so a :: t is duplicate-free by List.nodup_cons.mpr.

    lines 100–112

    uses List.toFinset_cons, List.length_cons, Finset.insert_eq_of_mem, List.toFinset_card_le, Finset.card_insert_of_notMem, List.nodup_cons.mpr

      induction l with
      | nil => simp
      | cons a t ih =>
        rw [List.toFinset_cons, List.length_cons] at h
        have ha : a ∉ t := by
          intro hat
          rw [Finset.insert_eq_of_mem (by simpa [List.mem_toFinset] using hat)] at h
          have hle : t.toFinset.card ≤ t.length := List.toFinset_card_le t
          omega
        have hains : a ∉ t.toFinset := by simpa [List.mem_toFinset] using ha
        rw [Finset.card_insert_of_notMem hains] at h
        have ht : t.toFinset.card = t.length := by omega
        exact List.nodup_cons.mpr ⟨ha, ih ht⟩
  7. When |segment_endpoints L| = 2 * |L|, the flattened list of representative pairs of L is duplicate-free.

    The finset of elements in the flattened list is segment_endpoints L (by greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset), so its cardinality is 2 * |L|, which equals the list's length by greedy_matching_fraction_le_of_blocking_ge_flatten_length. Therefore, greedy_matching_fraction_le_of_blocking_ge_nodup_of_card applies to conclude the list is duplicate-free.

    lines 119–121

    uses greedy_matching_fraction_le_of_blocking_ge_nodup_of_card, greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset, greedy_matching_fraction_le_of_blocking_ge_flatten_length

      apply greedy_matching_fraction_le_of_blocking_ge_nodup_of_card
      rw [greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset, h2,
        ← greedy_matching_fraction_le_of_blocking_ge_flatten_length]
  8. Re-pairing the representative pairs into unordered pairs recovers the original segment finset L.

    Mapping the unordered pair constructor over the representative pairs is the identity on segments by greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec, so the mapped list is L.toList by List.map_id. Converting L.toList back to a finset yields L by Finset.toList_toFinset.

    lines 128–136

    uses greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec, List.map_id, Finset.toList_toFinset

      have h : (greedy_matching_fraction_le_of_blocking_ge_pairList L).map
          (fun p => s(p.1, p.2)) = L.toList := by
        simp only [greedy_matching_fraction_le_of_blocking_ge_pairList, List.map_map]
        have hc : ((fun p : (ℝ × ℝ) × (ℝ × ℝ) => s(p.1, p.2)) ∘
            greedy_matching_fraction_le_of_blocking_ge_sym2rep) = id := by
          funext e
          exact greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec e
        rw [hc, List.map_id]
      rw [h, Finset.toList_toFinset]
  9. If no point in the buffer U forms an admissible segment with arriving point v, Greedy appends v to U.

    The step function searches U for a point u such that insert s(u, v) M satisfies P. Since no such point exists in U, List.find? returns none by List.find?_eq_none, which according to the definition of greedyStep appends v to U without modifying M.

    lines 143–147

    uses List.find?_eq_none

      have hfind : List.find? (fun u => decide (P (insert s(u, v) M))) U = none := by
        rw [List.find?_eq_none]
        intro u hu
        simpa using h u hu
      simp only [greedyStep, hfind]
  10. Sequentially feeding the endpoints of segments in pairs matches each pair, resulting in matching M ∪ pairs and an empty buffer.

    We argue by induction on the list of pairs. In the inductive step, for a pair p = (p.1, p.2), point p.1 arrives to an empty buffer and is stored. When p.2 arrives, because P is hereditary and insert s(p.1, p.2) M ⊆ L with P L holding, P(insert s(p.1, p.2) M) holds. Greedy immediately matches p.1 and p.2, adding the segment to M and clearing the buffer. The induction hypothesis then completes the matching on the remaining pairs.

    lines 159–185

    uses List.flatMap_cons, List.foldl_append, List.foldl_cons

      intro pairs
      induction pairs with
      | nil => intro hseg M hM; simp
      | cons p rest ih =>
        intro hseg M hM
        rw [List.flatMap_cons, List.foldl_append]
        have hsegp : s(p.1, p.2) ∈ L := hseg p (by simp)
        have hsub : insert s(p.1, p.2) M ⊆ L := by
          intro x hx
          rw [Finset.mem_insert] at hx
          rcases hx with rfl | hx
          · exact hsegp
          · exact hM hx
        have hPg : P (insert s(p.1, p.2) M) := hP.2 hsub hPL
        have hstep : greedyStep P (M, []) p.1 = (M, [p.1]) := by
          simp [greedyStep, List.find?_nil]
        have hstep2 : greedyStep P (M, [p.1]) p.2 = (insert s(p.1, p.2) M, []) := by
          have hfind : List.find? (fun u => decide (P (insert s(u, p.2) M))) [p.1] = some p.1 := by
            simp [hPg]
          simp only [greedyStep, hfind]
          simp
        have hone : List.foldl (greedyStep P) (M, []) [p.1, p.2] = (insert s(p.1, p.2) M, []) := by
          rw [List.foldl_cons, hstep, List.foldl_cons, hstep2]
          rfl
        rw [hone]
        rw [ih (fun q hq => hseg q (List.mem_cons_of_mem _ hq)) (insert s(p.1, p.2) M) hsub]
        rw [List.map_cons, List.toFinset_cons, Finset.union_insert, Finset.insert_union]
  11. Feeding points from a blocked set S to Greedy with matching L creates no new segments and buffers all points.

    We argue by induction on the point list ws. For each incoming point w, every point u currently in the buffer U belongs to S and is distinct from w. The blocking property segments_block_points_prop asserts that insert s(u, w) L does not satisfy P. By greedy_matching_fraction_le_of_blocking_ge_step_none, Greedy appends w to the buffer without creating any matching segment. Inductive bookkeeping ensures the updated buffer remains within S and disjoint from the remaining points.

    lines 193–225

    uses greedy_matching_fraction_le_of_blocking_ge_step_none, List.foldl_cons, List.append_assoc, List.singleton_append

          List.foldl (greedyStep P) (L, U) ws = (L, U ++ ws) := by
      intro ws
      induction ws with
      | nil => intro _ _ U _ _; simp
      | cons w rest ih =>
        intro hnod hmem U hU hdis
        have hwS : w ∈ S := hmem w (by simp)
        have hnod' : rest.Nodup := (List.nodup_cons.mp hnod).2
        have hwrest : w ∉ rest := (List.nodup_cons.mp hnod).1
        have hdis' : U.Disjoint rest := by
          intro a ha har
          exact hdis ha (List.mem_cons_of_mem _ har)
        have hstep : greedyStep P (L, U) w = (L, U ++ [w]) := by
          apply greedy_matching_fraction_le_of_blocking_ge_step_none
          intro u hu
          have huS : u ∈ S := hU u hu
          have hne : u ≠ w := by
            intro h
            exact hdis hu (h ▸ List.mem_cons_self)
          exact hblk huS hwS hne
        rw [List.foldl_cons, hstep,
          ih hnod' (fun q hq => hmem q (List.mem_cons_of_mem _ hq)) (U ++ [w]) ?_ ?_]
        · rw [List.append_assoc, List.singleton_append]
        · intro a ha
          rw [List.mem_append, List.mem_singleton] at ha
          rcases ha with h | rfl
          · exact hU a h
          · exact hwS
        · intro a ha
          rw [List.mem_append, List.mem_singleton] at ha
          rcases ha with h | rfl
          · exact hdis' h
          · exact hwrest
  12. Given witnesses L and S from the blocking bound, constructing pts = ends ++ S.toList results in Greedy producing matching L and buffer S.toList.

    The sequence ends contains the endpoints of L in pairs. Feeding ends to Greedy starting from an empty state matches all pairs, resulting in matching L and an empty buffer by greedy_matching_fraction_le_of_blocking_ge_foldl_pairs and greedy_matching_fraction_le_of_blocking_ge_pairList_matched. Then feeding S.toList adds no new segments and leaves matching L with buffer S.toList by greedy_matching_fraction_le_of_blocking_ge_foldl_S.

    lines 234–260

    uses greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset, greedy_matching_fraction_le_of_blocking_ge_flatten_nodup, greedy_matching_fraction_le_of_blocking_ge_flatten_length, greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec, List.foldl_append, greedy_matching_fraction_le_of_blocking_ge_foldl_pairs, greedy_matching_fraction_le_of_blocking_ge_pairList_matched, greedy_matching_fraction_le_of_blocking_ge_foldl_S, Finset.nodup_toList

      obtain ⟨L, S, hLcard, hPL, hends, hdisj, hgen, hblk, hpS⟩ := hβ
      classical
      have hends' : (segment_endpoints L).card = 2 * L.card := by rw [hLcard]; exact hends
      set pairs := greedy_matching_fraction_le_of_blocking_ge_pairList L with hpairs
      set ends : List (ℝ × ℝ) :=
        List.flatMap (fun q : (ℝ × ℝ) × (ℝ × ℝ) => [q.1, q.2]) pairs with hendsdef
      set pts : List (ℝ × ℝ) := ends ++ S.toList with hpts
      have hpairF : ends.toFinset = segment_endpoints L :=
        greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset L
      have hpairN : ends.Nodup := greedy_matching_fraction_le_of_blocking_ge_flatten_nodup L hends'
      have hpairLen : ends.length = 2 * L.card :=
        greedy_matching_fraction_le_of_blocking_ge_flatten_length L
      have hsegmem : ∀ q ∈ pairs, s(q.1, q.2) ∈ L := by
        intro q hq
        rw [hpairs] at hq
        simp only [greedy_matching_fraction_le_of_blocking_ge_pairList, List.mem_map,
          Finset.mem_toList] at hq
        obtain ⟨e, he, rfl⟩ := hq
        rw [greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec]
        exact he
      have hfold : List.foldl (greedyStep P) (∅, []) pts = (L, S.toList) := by
        rw [hpts, List.foldl_append]
        rw [greedy_matching_fraction_le_of_blocking_ge_foldl_pairs P L hP hPL pairs hsegmem ∅
          (Finset.empty_subset L)]
        rw [greedy_matching_fraction_le_of_blocking_ge_pairList_matched, Finset.empty_union]
        exact greedy_matching_fraction_le_of_blocking_ge_foldl_S P L S hblk S.toList
          (Finset.nodup_toList S) (fun w hw => Finset.mem_toList.mp hw) [] (by simp) (by simp)
  13. The constructed point sequence pts contains no duplicates.

    By List.nodup_append, pts = ends ++ S.toList is duplicate-free because ends is duplicate-free, S.toList is duplicate-free by Finset.nodup_toList, and their elements are disjoint by Finset.disjoint_left.mp since ends has elements segment_endpoints L which is disjoint from S.

    lines 261–269

    uses List.nodup_append, Finset.nodup_toList, Finset.disjoint_left.mp

      refine ⟨pts, ?_, ?_, ?_, ?_⟩
      · rw [hpts, List.nodup_append]
        refine ⟨hpairN, Finset.nodup_toList S, ?_⟩
        intro a ha b hb hab
        have ha' : a ∈ segment_endpoints L := by rw [← hpairF]; simpa using ha
        have hb' : b ∈ S := Finset.mem_toList.mp hb
        subst hab
        exact (Finset.disjoint_left.mp hdisj ha') hb'
      · have hset : pts.toFinset = segment_endpoints L ∪ S := by
  14. The point set pts.toFinset is in general position.

    The set of elements of pts is the union of ends.toFinset and S.toList.toFinset, which equals segment_endpoints L ∪ S by greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset and Finset.toList_toFinset. This union is given to be in general position by the blocking bound hypothesis.

    lines 270–273

    uses List.toFinset_append, greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset, Finset.toList_toFinset, Finset.coe_union

          rw [hpts, hendsdef, hpairs, List.toFinset_append,
            greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset, Finset.toList_toFinset]
        rw [hset, Finset.coe_union]
        exact hgen
  15. Greedy produces a matching of cardinality ℓ on pts.

    By definition of greedyMatching and the fold simulation, the matching produced by Greedy is L. By the blocking bound hypothesis, |L| = ℓ.

    lines 274–275

      · simp only [greedyMatching]
        rw [hfold, hLcard]
  16. The fraction of points matched by Greedy on pts is at most 2ℓ / (2ℓ + p).

    The total number of points is |pts| = 2|L| + |S| = 2ℓ + |S| by List.length_append and Finset.length_toList. If 2ℓ + p = 0, then ℓ = 0 and the inequality is trivial. If 2ℓ + p > 0, since |S| ≥ p, we have 2ℓ + p ≤ 2ℓ + |S| = |pts| by Nat.add_le_add_left. Since the numerator 2ℓ is non-negative and 2ℓ + p > 0, div_le_div_of_nonneg_left implies that dividing by the larger denominator |pts| yields an equal or smaller fraction.

    lines 276–292

    uses List.length_append, Finset.length_toList, Nat.eq_zero_or_pos, Nat.add_le_add_left, div_le_div_of_nonneg_left

      · have hlen : (pts.length : ℝ) = 2 * (L.card : ℝ) + (S.card : ℝ) := by
          rw [hpts, hendsdef, hpairs, List.length_append, hpairLen, Finset.length_toList]
          push_cast
          ring
        rcases Nat.eq_zero_or_pos (2 * ℓ + p) with hp0 | hppos
        · have hℓ0 : ℓ = 0 := by omega
          simp [hℓ0]
        · have hkey : 2 * (ℓ : ℝ) + (p : ℝ) ≤ 2 * (L.card : ℝ) + (S.card : ℝ) := by
            have h1 : 2 * ℓ + p ≤ 2 * L.card + S.card := by
              rw [hLcard]; exact Nat.add_le_add_left hpS _
            exact_mod_cast h1
          have hpos : (0 : ℝ) < 2 * (ℓ : ℝ) + (p : ℝ) := by
            have h2 : (0 : ℝ) < ((2 * ℓ + p : ℕ) : ℝ) := by exact_mod_cast hppos
            push_cast at h2 ⊢
            linarith
          rw [hlen]
          exact div_le_div_of_nonneg_left (by positivity) hpos hkey
greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec
The unordered pair formed from the representative pair of an unordered pair e is e itself.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z and y = w) or (x = w and y = z).
Finset.pair_comm
The unordered pair {a, b} in Finset equals {b, a}.
greedy_matching_fraction_le_of_blocking_ge_rep_pair_eq
The representative pair of an unordered pair s(u, v) has endpoint set {u, v}.
greedy_matching_fraction_le_of_blocking_ge_segment_endpoints_eq_biUnion
The endpoint set of a segment collection L is the union of endpointsOf e over all e in L.
Finset.mem_biUnion
An element belongs to a biUnion over a finset if and only if it belongs to the image of some element in the finset.
Finset.ext
Two finite sets are equal if and only if they have the same elements.
List.mem_toFinset
An element belongs to the finset of a list if and only if it is an element of the list.
greedy_matching_fraction_le_of_blocking_ge_mem_segment_endpoints_iff
A point belongs to segment_endpoints L if and only if it equals the first or second coordinate of the representative of some segment in L.
List.length_flatMap
The length of a flatMap on a list is the sum of the lengths of the mapped sublists.
List.toFinset_cons
Converting a cons list a :: l to a finset yields insert a l.toFinset.
List.length_cons
The length of a cons list a :: l is the length of l plus one.
Finset.insert_eq_of_mem
Inserting an element into a finset that already contains it leaves the finset unchanged.
List.toFinset_card_le
The cardinality of the finset of elements in a list is at most the length of the list.
Finset.card_insert_of_notMem
Inserting an element not in a finset increases its cardinality by one.
List.nodup_cons.mpr
If a is not in l and l is duplicate-free, then a :: l is duplicate-free.
greedy_matching_fraction_le_of_blocking_ge_nodup_of_card
Any list whose set of distinct elements has cardinality equal to its length has no duplicates.
greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset
The finset of elements in the flattened representative-pair list of L equals segment_endpoints L.
greedy_matching_fraction_le_of_blocking_ge_flatten_length
The flattened representative-pair list of L has length 2 * |L|.
List.map_id
Mapping the identity function over a list returns the list itself.
Finset.toList_toFinset
Converting a finset to a list and back to a finset recovers the original finset.
List.find?_eq_none
Searching a list with find? returns none if and only if the predicate fails on every element.
List.flatMap_cons
flatMap on a cons list x :: xs equals f x concatenated with flatMap on xs.
List.foldl_append
Folding over an appended list l ++ l' equals folding over l' starting from the result on l.
List.foldl_cons
Folding over a cons list a :: l applies the step function to the accumulator and a, then folds over l.
greedy_matching_fraction_le_of_blocking_ge_step_none
If an arriving point cannot form an admissible segment with any point in the buffer, Greedy appends it to the buffer and keeps the matching unchanged.
List.append_assoc
Associativity of list concatenation: (as ++ bs) ++ cs = as ++ (bs ++ cs).
List.singleton_append
A singleton list concatenated to a list: [a] ++ as = a :: as.
greedy_matching_fraction_le_of_blocking_ge_flatten_nodup
When the endpoint set of L has size 2 * |L|, the flattened representative-pair list is duplicate-free.
greedy_matching_fraction_le_of_blocking_ge_foldl_pairs
Sequential execution of Greedy on flattened pairs from L from an empty buffer matches each pair, producing matching M ∪ pairs and an empty buffer.
greedy_matching_fraction_le_of_blocking_ge_pairList_matched
Reconstructing unordered pairs from the representative-pair list recovers the original finset of segments L.
greedy_matching_fraction_le_of_blocking_ge_foldl_S
Feeding blocked points from S to Greedy when the matching is L creates no new segments and appends all of them to the buffer.
Finset.nodup_toList
Converting any finset to a list produces a duplicate-free list.
List.nodup_append
The concatenation of two lists is duplicate-free if both are duplicate-free and they share no common elements.
Finset.disjoint_left.mp
If two finsets are disjoint, an element in the first cannot belong to the second.
List.toFinset_append
The finset of elements of an appended list is the union of the finsets of each list.
Finset.coe_union
The coercion of a union of finsets to sets is the union of their coerced sets.
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
Finset.length_toList
The length of the list obtained from a finset equals the cardinality of the finset.
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
Nat.add_le_add_left
Adding a constant to both sides of an inequality preserves the inequality.
div_le_div_of_nonneg_left
For a ≥ 0 and 0 < c ≤ b, a / b ≤ a / c.

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

open scoped Classical/-- A representative pair of an unordered pair of points in the plane. -/noncomputable def greedy_matching_fraction_le_of_blocking_ge_sym2rep (e : Sym2 (ℝ × ℝ)) :    (ℝ × ℝ) × (ℝ × ℝ) := Quot.out e/-- The representative pair reproduces the unordered pair. -/lemma greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec (e : Sym2 (ℝ × ℝ)) :    s((greedy_matching_fraction_le_of_blocking_ge_sym2rep e).1,      (greedy_matching_fraction_le_of_blocking_ge_sym2rep e).2) = e := Quot.out_eq e/-- The endpoint set of the representative of `s(u,v)` is `{u, v}`. -/lemma greedy_matching_fraction_le_of_blocking_ge_rep_pair_eq (u v : ℝ × ℝ) :    ({(greedy_matching_fraction_le_of_blocking_ge_sym2rep (s(u, v))).1,      (greedy_matching_fraction_le_of_blocking_ge_sym2rep (s(u, v))).2} : Finset (ℝ × ℝ))      = {u, v} := by  have h := greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec (s(u, v))  rw [Sym2.eq_iff] at h  rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩  · rw [h1, h2]  · rw [h1, h2, Finset.pair_comm]/-- The two-element endpoint set of a segment, read off its representative. -/noncomputable def greedy_matching_fraction_le_of_blocking_ge_endpointsOf (e : Sym2 (ℝ × ℝ)) :    Finset (ℝ × ℝ) :=  {(greedy_matching_fraction_le_of_blocking_ge_sym2rep e).1,   (greedy_matching_fraction_le_of_blocking_ge_sym2rep e).2}/-- `segment_endpoints` is the biUnion of the two-element endpoint sets. -/lemma greedy_matching_fraction_le_of_blocking_ge_segment_endpoints_eq_biUnion    (L : Finset (Sym2 (ℝ × ℝ))) :    segment_endpoints L = L.biUnion greedy_matching_fraction_le_of_blocking_ge_endpointsOf := by  unfold segment_endpoints  congr 1  funext e  obtain ⟨u, v, rfl⟩ :      ∃ u v, e = s(u, v) :=    ⟨_, _, (greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec e).symm⟩  simp only [greedy_matching_fraction_le_of_blocking_ge_endpointsOf]  rw [greedy_matching_fraction_le_of_blocking_ge_rep_pair_eq]  rfl/-- Membership in `segment_endpoints`, expressed through representatives. -/lemma greedy_matching_fraction_le_of_blocking_ge_mem_segment_endpoints_iff    (L : Finset (Sym2 (ℝ × ℝ))) (x : ℝ × ℝ) :    x ∈ segment_endpoints L ↔ ∃ e ∈ L,      x = (greedy_matching_fraction_le_of_blocking_ge_sym2rep e).1 ∨      x = (greedy_matching_fraction_le_of_blocking_ge_sym2rep e).2 := by  rw [greedy_matching_fraction_le_of_blocking_ge_segment_endpoints_eq_biUnion]  constructor  · intro h    rw [Finset.mem_biUnion] at h    obtain ⟨e, he, hxe⟩ := h    exact ⟨e, he, by      simpa [greedy_matching_fraction_le_of_blocking_ge_endpointsOf, Finset.mem_insert,        Finset.mem_singleton] using hxe⟩  · rintro ⟨e, he, h | h⟩    · rw [Finset.mem_biUnion]      exact ⟨e, he, by simp [greedy_matching_fraction_le_of_blocking_ge_endpointsOf, h]⟩    · rw [Finset.mem_biUnion]      exact ⟨e, he, by simp [greedy_matching_fraction_le_of_blocking_ge_endpointsOf, h]⟩/-- The segments of `L`, each replaced by its representative pair. -/noncomputable def greedy_matching_fraction_le_of_blocking_ge_pairList    (L : Finset (Sym2 (ℝ × ℝ))) : List ((ℝ × ℝ) × (ℝ × ℝ)) :=  L.toList.map greedy_matching_fraction_le_of_blocking_ge_sym2rep/-- Flattening the representative pairs yields the endpoint set of `L`. -/lemma greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset    (L : Finset (Sym2 (ℝ × ℝ))) :    (List.flatMap (fun p : (ℝ × ℝ) × (ℝ × ℝ) => [p.1, p.2])      (greedy_matching_fraction_le_of_blocking_ge_pairList L)).toFinset = segment_endpoints L := by  apply Finset.ext  intro x  rw [List.mem_toFinset, greedy_matching_fraction_le_of_blocking_ge_mem_segment_endpoints_iff]  simp only [greedy_matching_fraction_le_of_blocking_ge_pairList, List.mem_flatMap, List.mem_map,    List.mem_cons, List.not_mem_nil, or_false, Finset.mem_toList]  constructor  · rintro ⟨p, ⟨e, he, rfl⟩, h | h⟩    · exact ⟨e, he, Or.inl h⟩    · exact ⟨e, he, Or.inr h⟩  · rintro ⟨e, he, h | h⟩    · exact ⟨_, ⟨e, he, rfl⟩, Or.inl h⟩    · exact ⟨_, ⟨e, he, rfl⟩, Or.inr h⟩/-- The flattened representative-pair list has `2 * |L|` entries. -/lemma greedy_matching_fraction_le_of_blocking_ge_flatten_length    (L : Finset (Sym2 (ℝ × ℝ))) :    (List.flatMap (fun p : (ℝ × ℝ) × (ℝ × ℝ) => [p.1, p.2])      (greedy_matching_fraction_le_of_blocking_ge_pairList L)).length = 2 * L.card := by  simp only [greedy_matching_fraction_le_of_blocking_ge_pairList]  rw [List.length_flatMap]  simp only [List.length_cons, List.length_nil, List.map_map]  simp  omega/-- A list whose finset of entries has the same cardinality as its length is duplicate-free. -/lemma greedy_matching_fraction_le_of_blocking_ge_nodup_of_card    {α : Type*} [DecidableEq α] {l : List α} (h : l.toFinset.card = l.length) : l.Nodup := by  induction l with  | nil => simp  | cons a t ih =>    rw [List.toFinset_cons, List.length_cons] at h    have ha : a ∉ t := by      intro hat      rw [Finset.insert_eq_of_mem (by simpa [List.mem_toFinset] using hat)] at h      have hle : t.toFinset.card ≤ t.length := List.toFinset_card_le t      omega    have hains : a ∉ t.toFinset := by simpa [List.mem_toFinset] using ha    rw [Finset.card_insert_of_notMem hains] at h    have ht : t.toFinset.card = t.length := by omega    exact List.nodup_cons.mpr ⟨ha, ih ht⟩/-- Distinct endpoints make the flattened representative list duplicate-free. -/lemma greedy_matching_fraction_le_of_blocking_ge_flatten_nodup    (L : Finset (Sym2 (ℝ × ℝ))) (h2 : (segment_endpoints L).card = 2 * L.card) :    (List.flatMap (fun p : (ℝ × ℝ) × (ℝ × ℝ) => [p.1, p.2])      (greedy_matching_fraction_le_of_blocking_ge_pairList L)).Nodup := by  apply greedy_matching_fraction_le_of_blocking_ge_nodup_of_card  rw [greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset, h2,    ← greedy_matching_fraction_le_of_blocking_ge_flatten_length]/-- Re-pairing the representatives recovers `L`. -/lemma greedy_matching_fraction_le_of_blocking_ge_pairList_matched    (L : Finset (Sym2 (ℝ × ℝ))) :    ((greedy_matching_fraction_le_of_blocking_ge_pairList L).map      (fun p => s(p.1, p.2))).toFinset = L := by  have h : (greedy_matching_fraction_le_of_blocking_ge_pairList L).map      (fun p => s(p.1, p.2)) = L.toList := by    simp only [greedy_matching_fraction_le_of_blocking_ge_pairList, List.map_map]    have hc : ((fun p : (ℝ × ℝ) × (ℝ × ℝ) => s(p.1, p.2)) ∘        greedy_matching_fraction_le_of_blocking_ge_sym2rep) = id := by      funext e      exact greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec e    rw [hc, List.map_id]  rw [h, Finset.toList_toFinset]/-- Greedy appends the arriving point when no buffered point is admissible. -/lemma greedy_matching_fraction_le_of_blocking_ge_step_none    {P : Finset (Sym2 (ℝ × ℝ)) → Prop} {M : Finset (Sym2 (ℝ × ℝ))}    {U : List (ℝ × ℝ)} {v : ℝ × ℝ} (h : ∀ u ∈ U, ¬ P (insert s(u, v) M)) :    greedyStep P (M, U) v = (M, U ++ [v]) := by  have hfind : List.find? (fun u => decide (P (insert s(u, v) M))) U = none := by    rw [List.find?_eq_none]    intro u hu    simpa using h u hu  simp only [greedyStep, hfind]/-- Feeding the flattened representative pairs (all inside `L`) to Greedy matches all of them. -/lemma greedy_matching_fraction_le_of_blocking_ge_foldl_pairs    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (L : Finset (Sym2 (ℝ × ℝ)))    (hP : IsHereditarySegmentProperty P) (hPL : P L) :    ∀ (pairs : List ((ℝ × ℝ) × (ℝ × ℝ))),    (∀ p ∈ pairs, s(p.1, p.2) ∈ L) →    ∀ M : Finset (Sym2 (ℝ × ℝ)), M ⊆ L →      List.foldl (greedyStep P) (M, [])        (List.flatMap (fun p : (ℝ × ℝ) × (ℝ × ℝ) => [p.1, p.2]) pairs)        = (M ∪ (pairs.map (fun p => s(p.1, p.2))).toFinset, []) := by  intro pairs  induction pairs with  | nil => intro hseg M hM; simp  | cons p rest ih =>    intro hseg M hM    rw [List.flatMap_cons, List.foldl_append]    have hsegp : s(p.1, p.2) ∈ L := hseg p (by simp)    have hsub : insert s(p.1, p.2) M ⊆ L := by      intro x hx      rw [Finset.mem_insert] at hx      rcases hx with rfl | hx      · exact hsegp      · exact hM hx    have hPg : P (insert s(p.1, p.2) M) := hP.2 hsub hPL    have hstep : greedyStep P (M, []) p.1 = (M, [p.1]) := by      simp [greedyStep, List.find?_nil]    have hstep2 : greedyStep P (M, [p.1]) p.2 = (insert s(p.1, p.2) M, []) := by      have hfind : List.find? (fun u => decide (P (insert s(u, p.2) M))) [p.1] = some p.1 := by        simp [hPg]      simp only [greedyStep, hfind]      simp    have hone : List.foldl (greedyStep P) (M, []) [p.1, p.2] = (insert s(p.1, p.2) M, []) := by      rw [List.foldl_cons, hstep, List.foldl_cons, hstep2]      rfl    rw [hone]    rw [ih (fun q hq => hseg q (List.mem_cons_of_mem _ hq)) (insert s(p.1, p.2) M) hsub]    rw [List.map_cons, List.toFinset_cons, Finset.union_insert, Finset.insert_union]/-- A blocking family matches none of the blocked points: Greedy appends them all. -/lemma greedy_matching_fraction_le_of_blocking_ge_foldl_S    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (L : Finset (Sym2 (ℝ × ℝ)))    (S : Finset (ℝ × ℝ)) (hblk : segments_block_points_prop P L S) :    ∀ ws : List (ℝ × ℝ), ws.Nodup → (∀ w ∈ ws, w ∈ S) →    ∀ U : List (ℝ × ℝ), (∀ u ∈ U, u ∈ S) → U.Disjoint ws →      List.foldl (greedyStep P) (L, U) ws = (L, U ++ ws) := by  intro ws  induction ws with  | nil => intro _ _ U _ _; simp  | cons w rest ih =>    intro hnod hmem U hU hdis    have hwS : w ∈ S := hmem w (by simp)    have hnod' : rest.Nodup := (List.nodup_cons.mp hnod).2    have hwrest : w ∉ rest := (List.nodup_cons.mp hnod).1    have hdis' : U.Disjoint rest := by      intro a ha har      exact hdis ha (List.mem_cons_of_mem _ har)    have hstep : greedyStep P (L, U) w = (L, U ++ [w]) := by      apply greedy_matching_fraction_le_of_blocking_ge_step_none      intro u hu      have huS : u ∈ S := hU u hu      have hne : u ≠ w := by        intro h        exact hdis hu (h ▸ List.mem_cons_self)      exact hblk huS hwS hne    rw [List.foldl_cons, hstep,      ih hnod' (fun q hq => hmem q (List.mem_cons_of_mem _ hq)) (U ++ [w]) ?_ ?_]    · rw [List.append_assoc, List.singleton_append]    · intro a ha      rw [List.mem_append, List.mem_singleton] at ha      rcases ha with h | rfl      · exact hU a h      · exact hwS    · intro a ha      rw [List.mem_append, List.mem_singleton] at ha      rcases ha with h | rfl      · exact hdis' h      · exact hwrest/-- Part (2) of Theorem 1.2: if β_P(ℓ) ≥ p, there exists an input on which Greedy creates ℓ segments and matches at most a 2ℓ/(2ℓ+p) fraction. -/theorem greedy_matching_fraction_le_of_blocking_ge    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ)    (hβ : segment_blocking_bound_ge P ℓ p) :    ∃ pts : List (ℝ × ℝ), pts.Nodup ∧ points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) ∧      (greedyMatching P pts).1.card = ℓ ∧      (2 * (ℓ : ℝ)) / (pts.length : ℝ) ≤ (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) := by  obtain ⟨L, S, hLcard, hPL, hends, hdisj, hgen, hblk, hpS⟩ := hβ  classical  have hends' : (segment_endpoints L).card = 2 * L.card := by rw [hLcard]; exact hends  set pairs := greedy_matching_fraction_le_of_blocking_ge_pairList L with hpairs  set ends : List (ℝ × ℝ) :=    List.flatMap (fun q : (ℝ × ℝ) × (ℝ × ℝ) => [q.1, q.2]) pairs with hendsdef  set pts : List (ℝ × ℝ) := ends ++ S.toList with hpts  have hpairF : ends.toFinset = segment_endpoints L :=    greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset L  have hpairN : ends.Nodup := greedy_matching_fraction_le_of_blocking_ge_flatten_nodup L hends'  have hpairLen : ends.length = 2 * L.card :=    greedy_matching_fraction_le_of_blocking_ge_flatten_length L  have hsegmem : ∀ q ∈ pairs, s(q.1, q.2) ∈ L := by    intro q hq    rw [hpairs] at hq    simp only [greedy_matching_fraction_le_of_blocking_ge_pairList, List.mem_map,      Finset.mem_toList] at hq    obtain ⟨e, he, rfl⟩ := hq    rw [greedy_matching_fraction_le_of_blocking_ge_sym2rep_spec]    exact he  have hfold : List.foldl (greedyStep P) (∅, []) pts = (L, S.toList) := by    rw [hpts, List.foldl_append]    rw [greedy_matching_fraction_le_of_blocking_ge_foldl_pairs P L hP hPL pairs hsegmem ∅      (Finset.empty_subset L)]    rw [greedy_matching_fraction_le_of_blocking_ge_pairList_matched, Finset.empty_union]    exact greedy_matching_fraction_le_of_blocking_ge_foldl_S P L S hblk S.toList      (Finset.nodup_toList S) (fun w hw => Finset.mem_toList.mp hw) [] (by simp) (by simp)  refine ⟨pts, ?_, ?_, ?_, ?_⟩  · rw [hpts, List.nodup_append]    refine ⟨hpairN, Finset.nodup_toList S, ?_⟩    intro a ha b hb hab    have ha' : a ∈ segment_endpoints L := by rw [← hpairF]; simpa using ha    have hb' : b ∈ S := Finset.mem_toList.mp hb    subst hab    exact (Finset.disjoint_left.mp hdisj ha') hb'  · have hset : pts.toFinset = segment_endpoints L ∪ S := by      rw [hpts, hendsdef, hpairs, List.toFinset_append,        greedy_matching_fraction_le_of_blocking_ge_flatten_toFinset, Finset.toList_toFinset]    rw [hset, Finset.coe_union]    exact hgen  · simp only [greedyMatching]    rw [hfold, hLcard]  · have hlen : (pts.length : ℝ) = 2 * (L.card : ℝ) + (S.card : ℝ) := by      rw [hpts, hendsdef, hpairs, List.length_append, hpairLen, Finset.length_toList]      push_cast      ring    rcases Nat.eq_zero_or_pos (2 * ℓ + p) with hp0 | hppos    · have hℓ0 : ℓ = 0 := by omega      simp [hℓ0]    · have hkey : 2 * (ℓ : ℝ) + (p : ℝ) ≤ 2 * (L.card : ℝ) + (S.card : ℝ) := by        have h1 : 2 * ℓ + p ≤ 2 * L.card + S.card := by          rw [hLcard]; exact Nat.add_le_add_left hpS _        exact_mod_cast h1      have hpos : (0 : ℝ) < 2 * (ℓ : ℝ) + (p : ℝ) := by        have h2 : (0 : ℝ) < ((2 * ℓ + p : ℕ) : ℝ) := by exact_mod_cast hppos        push_cast at h2 ⊢        linarith      rw [hlen]      exact div_le_div_of_nonneg_left (by positivity) hpos hkey
See it in the graphDiscuss this resultChallenge it