AFTD Auto-Formalizing Theoretical Domains

forest_carpool_component_coin_locality

theoremverified

Two coin assignments that agree on every edge in the final connected component of a fixed vertex give the same final greedy discrepancy at that vertex.

Statement

theorem forest_carpool_component_coin_locality (n : ℕ)
    (edges : List (Fin n × Fin n)) (v : Fin n)
    (r s : Fin edges.length → Bool)
    (hcoins : ∀ i : Fin edges.length,
      (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}).Reachable v (edges.get i).1 →
      r i = s i) :
  forest_carpool_final_discrepancy n edges r v =
    forest_carpool_final_discrepancy n edges s v
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • forest_carpool_final_discrepancyThe final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.
  • carpool_stepIn online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d…
  • carpool_greedy_orientationsGiven a list of edges and a list of tie-breaking coins, randomized greedy carpooling orients each edge toward the endpoint with smaller…
  • carpool_discrepanciesThe sequence of discrepancy vectors (d₀, ..., d_T) starting from the zero vector, where each d_t is updated from d_{t-1} using the t-th…
  • Arena.Reachable.transReachability is transitive.
  • bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
Used by 3

The proof, explained

The proof reformulates the sequential discrepancy update into a recursive fold G and establishes locality: a single carpool step along an edge only modifies discrepancies at that edge's endpoints, so if neither endpoint is reachable from a vertex w, the discrepancy at w is untouched, and if an endpoint is reachable, both endpoints belong to w's connected component, meaning their discrepancies and coin bits match and yield the same greedy decision. By induction over the edge list, the final discrepancy on w's connected component depends solely on the coins of edges in that component. Applying this to the full graph of edges, two coin assignments agreeing on the component of v yield identical final discrepancies at v.

  1. The scan accumulator computing the sequence of carpool discrepancies matches the direct recursive fold G.

    We proceed by induction on the edge list es, generalizing over the coin list cs and discrepancy functions. When either the edge list or coin list is empty, both the scan and G leave the discrepancy unchanged. In the inductive step with edge e and coin c, the scan updates the discrepancy by carpool_step with orientation gbit d e c, which matches the recursive call of G by the induction hypothesis.

    lines 16–25

    uses List.zip_cons_cons, List.scanl_cons, List.getLastD_cons

      induction es generalizing cs d z with
      | nil => simp [carpool_greedy_orientations.aux, G]
      | cons e es ih =>
        cases cs with
        | nil => simp [carpool_greedy_orientations.aux, G]
        | cons c cs =>
          simp only [carpool_greedy_orientations.aux, List.zip_cons_cons, List.scanl_cons,
            List.getLastD_cons, G]
          rw [← ih cs _ d]
          rfl
  2. The final discrepancy forest_carpool_final_discrepancy equals G n edges (List.ofFn r) 0.

    Unfolding the definitions of forest_carpool_final_discrepancy, carpool_discrepancies, and carpool_greedy_orientations, the final discrepancy is the last element of the scan list starting from the all-zero discrepancy. Applying scan_eq expresses this directly as the recursive fold G.

    lines 29–30

    uses scan_eq

      unfold forest_carpool_final_discrepancy carpool_discrepancies carpool_greedy_orientations
      exact scan_eq n edges (List.ofFn r) _ _
  3. A single carpool step preserves agreement of discrepancies on the component of w when the edge's first endpoint is reachable from w.

    Let x be a vertex reachable from w, and suppose e.1 is reachable from w. Since e is an edge of Γ (or a self-loop), e.2 is also reachable from w. By the hypothesis that d and d' agree on all vertices reachable from w, we have d(e.1) = d'(e.1) and d(e.2) = d'(e.2). Because e.1 is reachable, the coins also agree (c = c'). Consequently, the greedy orientation bits match (gbit d e c = gbit d' e c'). Since both the orientation and the prior discrepancy d(x) = d'(x) match, the updated discrepancies at x are identical.

    lines 39–47

      intro x hx
      by_cases h1 : Γ.Reachable w e.1
      · have h2 : Γ.Reachable w e.2 := by
          rcases he with h | h
          · rwa [← h]
          · exact h1.trans h.reachable
        have hb : gbit d e c = gbit d' e c' := by
          unfold gbit; rw [hd _ h1, hd _ h2, hc h1]
        unfold carpool_step; rw [hb, hd x hx]
  4. A single carpool step preserves agreement of discrepancies on the component of w when the edge's first endpoint is not reachable from w.

    If e.1 is not reachable from w, then e.2 cannot be reachable from w either, since e is an edge of Γ. Thus, any vertex x reachable from w satisfies x ≠ e.1 and x ≠ e.2. A carpool step along e only modifies the discrepancies at e.1 and e.2, leaving the discrepancy at x unchanged. Since d(x) = d'(x) before the step, they remain equal after the step.

    lines 48–55

      · have h2 : ¬ Γ.Reachable w e.2 := by
          intro h2; apply h1
          rcases he with h | h
          · rwa [h]
          · exact h2.trans h.symm.reachable
        have hx1 : x ≠ e.1 := by rintro rfl; exact h1 hx
        have hx2 : x ≠ e.2 := by rintro rfl; exact h2 hx
        unfold carpool_step; simp [hx1, hx2, hd x hx]
  5. The recursive fold G preserves agreement on the component of w in the base case and when coin lists are exhausted.

    We induct on the edge list es. In the base case where es is empty, G returns the current discrepancy, which agrees on all vertices reachable from w by assumption. If es is non-empty but the coin list is empty, both coin lists must be empty by length equality, and G again returns the initial discrepancy unchanged.

    lines 64–77

      intro es
      induction es with
      | nil => intro cs cs' d d' _ _ _ hd x hx; simp [G, hd x hx]
      | cons e es ih =>
        intro cs cs' d d' hes hlen hcoin hd x hx
        cases cs with
        | nil =>
          cases cs' with
          | nil => simp [G, hd x hx]
          | cons _ _ => simp at hlen
        | cons c cs =>
          cases cs' with
          | nil => simp at hlen
          | cons c' cs' =>
  6. The recursive fold G preserves agreement on the component of w across all remaining edges.

    In the inductive step where both coin lists are non-empty with heads c, c' and tails cs, cs', we use local_step to show that the one-step updated discrepancies agree on all vertices reachable from w. The coin bits for the first edge agree by specializing the coin hypothesis at index 0. The coin agreement condition for the remaining edges follows by shifting indices by 1. We then apply the induction hypothesis on the tail of the edges.

    lines 78–87

    uses List.mem_cons_of_mem, local_step, List.mem_cons_self

            simp only [G]
            refine ih cs cs' _ _ (fun e he => hes e (List.mem_cons_of_mem _ he))
              (by simpa using hlen) ?_ ?_ x hx
            · intro j hj hr
              have := hcoin (j + 1) (by simpa using hj) (by simpa using hr)
              simpa using this
            · refine local_step n Γ w e (hes e (List.mem_cons_self ..)) d d' c c' hd ?_
              intro hr
              have := hcoin 0 (by simp) (by simpa using hr)
              simpa using this
  7. The final discrepancy at v reduces to evaluating G on the graph Γ formed by all edges in edges.

    Using final_eq, we rewrite the final discrepancies under coin assignments r and s as G applied to List.ofFn r and List.ofFn s starting from the all-zero discrepancy. We then apply ForestCarpoolLocal.G_local with Γ defined as the graph with edge set {s(e.1, e.2) | e ∈ edges} and base vertex v. Since the initial discrepancies are both identically zero, they agree everywhere, and v is reachable from itself by reflexivity.

    lines 99–101

    uses ForestCarpoolLocal.final_eq, ForestCarpoolLocal.G_local, SimpleGraph.Reachable.refl

      rw [ForestCarpoolLocal.final_eq, ForestCarpoolLocal.final_eq]
      refine ForestCarpoolLocal.G_local n (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}) v edges _ _ _ _ ?_
        (by simp) ?_ (fun _ _ => rfl) v (SimpleGraph.Reachable.refl v)
  8. Every edge in edges is either a self-loop or an adjacency in Γ.

    For any edge e ∈ edges, if e.1 = e.2, it is a self-loop. Otherwise e.1 ≠ e.2, and by definition of SimpleGraph.fromEdgeSet, the unordered pair s(e.1, e.2) forms an edge in Γ.

    lines 102–105

    uses Or.inl, Or.inr, SimpleGraph.fromEdgeSet_adj

      · intro e he
        by_cases h : e.1 = e.2
        · exact Or.inl h
        · exact Or.inr (SimpleGraph.fromEdgeSet_adj _ |>.mpr ⟨⟨e, he, rfl⟩, h⟩)
  9. The coin lists agree at every edge whose first endpoint is reachable from v.

    For any index j < edges.length, if (edges[j]).1 is reachable from v in Γ, the assumption hcoins at index ⟨j, hj⟩ implies r(j) = s(j). Thus the j-th elements of List.ofFn r and List.ofFn s are equal, completing the verification of all hypotheses for G_local.

    lines 106–108

      · intro j hj hr
        have := hcoins ⟨j, hj⟩ (by simpa using hr)
        simp [hj, this]
ForestCarpoolLocal.final_eq
The final carpool discrepancy equals the recursive fold G evaluated on the edge list, the list of coin values, and the all-zero initial discrepancy.
ForestCarpoolLocal.G_local
The recursive fold G preserves discrepancy values on the connected component of vertex w, provided all edges belong to the graph, coin lists have equal length, coins agree on all reachable edges, and initial discrepancies agree on reachable vertices.
List.getLastD_cons
The last element of a non-empty list b :: l with fallback a equals the last element of l with fallback b.
List.mem_cons_of_mem
If an element belongs to a list l, it also belongs to y :: l.
List.mem_cons_self
The head element a belongs to the list a :: l.
List.scanl_cons
The left scan of a non-empty list a :: l with accumulator b starts with b followed by the scan of l starting from f b a.
List.zip_cons_cons
Zipping two non-empty lists pairs their heads and continues with the zip of their tails.
local_step
A single carpool step along an edge preserves discrepancy agreement on a graph component, provided initial discrepancies agree on the component and the coin bits agree when the edge touches the component.
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.
scan_eq
The last discrepancy in the scan sequence produced by carpool_greedy_orientations.aux equals the discrepancy computed by the recursive fold G.
SimpleGraph.fromEdgeSet_adj
Two vertices v and w are adjacent in the graph generated by edge set s if and only if the unordered pair s(v, w) is in s and v ≠ w.
SimpleGraph.Reachable.refl
Every vertex in a graph is reachable from itself.

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

namespace ForestCarpoolLocal/-- greedy bit -/def gbit {n : ℕ} (d : Fin n → ℤ) (e : Fin n × Fin n) (c : Bool) : Bool :=  if d e.1 < d e.2 then true else if d e.2 < d e.1 then false else c/-- greedy fold -/def G (n : ℕ) : List (Fin n × Fin n) → List Bool → (Fin n → ℤ) → (Fin n → ℤ)  | [], _, d => d  | _, [], d => d  | e :: es, c :: cs, d => G n es cs (carpool_step n d e (gbit d e c))theorem scan_eq (n : ℕ) (es : List (Fin n × Fin n)) (cs : List Bool) (d z : Fin n → ℤ) :    ((es.zip (carpool_greedy_orientations.aux n es cs d)).scanl      (fun d (e, b) => carpool_step n d e b) d).getLastD z = G n es cs d := by  induction es generalizing cs d z with  | nil => simp [carpool_greedy_orientations.aux, G]  | cons e es ih =>    cases cs with    | nil => simp [carpool_greedy_orientations.aux, G]    | cons c cs =>      simp only [carpool_greedy_orientations.aux, List.zip_cons_cons, List.scanl_cons,        List.getLastD_cons, G]      rw [← ih cs _ d]      rfltheorem final_eq (n : ℕ) (edges : List (Fin n × Fin n)) (r : Fin edges.length → Bool) :    forest_carpool_final_discrepancy n edges r = G n edges (List.ofFn r) (fun _ => 0) := by  unfold forest_carpool_final_discrepancy carpool_discrepancies carpool_greedy_orientations  exact scan_eq n edges (List.ofFn r) _ _theorem local_step (n : ℕ) (Γ : SimpleGraph (Fin n)) (w : Fin n)    (e : Fin n × Fin n) (he : e.1 = e.2 ∨ Γ.Adj e.1 e.2)    (d d' : Fin n → ℤ) (c c' : Bool)    (hd : ∀ x, Γ.Reachable w x → d x = d' x)    (hc : Γ.Reachable w e.1 → c = c') :    ∀ x, Γ.Reachable w x →      carpool_step n d e (gbit d e c) x = carpool_step n d' e (gbit d' e c') x := by  intro x hx  by_cases h1 : Γ.Reachable w e.1  · have h2 : Γ.Reachable w e.2 := by      rcases he with h | h      · rwa [← h]      · exact h1.trans h.reachable    have hb : gbit d e c = gbit d' e c' := by      unfold gbit; rw [hd _ h1, hd _ h2, hc h1]    unfold carpool_step; rw [hb, hd x hx]  · have h2 : ¬ Γ.Reachable w e.2 := by      intro h2; apply h1      rcases he with h | h      · rwa [h]      · exact h2.trans h.symm.reachable    have hx1 : x ≠ e.1 := by rintro rfl; exact h1 hx    have hx2 : x ≠ e.2 := by rintro rfl; exact h2 hx    unfold carpool_step; simp [hx1, hx2, hd x hx]theorem G_local (n : ℕ) (Γ : SimpleGraph (Fin n)) (w : Fin n) :    ∀ (es : List (Fin n × Fin n)) (cs cs' : List Bool) (d d' : Fin n → ℤ),    (∀ e ∈ es, e.1 = e.2 ∨ Γ.Adj e.1 e.2) →    cs.length = cs'.length →    (∀ j (hj : j < es.length), Γ.Reachable w es[j].1 → cs[j]? = cs'[j]?) →    (∀ x, Γ.Reachable w x → d x = d' x) →    ∀ x, Γ.Reachable w x → G n es cs d x = G n es cs' d' x := by  intro es  induction es with  | nil => intro cs cs' d d' _ _ _ hd x hx; simp [G, hd x hx]  | cons e es ih =>    intro cs cs' d d' hes hlen hcoin hd x hx    cases cs with    | nil =>      cases cs' with      | nil => simp [G, hd x hx]      | cons _ _ => simp at hlen    | cons c cs =>      cases cs' with      | nil => simp at hlen      | cons c' cs' =>        simp only [G]        refine ih cs cs' _ _ (fun e he => hes e (List.mem_cons_of_mem _ he))          (by simpa using hlen) ?_ ?_ x hx        · intro j hj hr          have := hcoin (j + 1) (by simpa using hj) (by simpa using hr)          simpa using this        · refine local_step n Γ w e (hes e (List.mem_cons_self ..)) d d' c c' hd ?_          intro hr          have := hcoin 0 (by simp) (by simpa using hr)          simpa using thisend ForestCarpoolLocaltheorem forest_carpool_component_coin_locality (n : ℕ)    (edges : List (Fin n × Fin n)) (v : Fin n)    (r s : Fin edges.length → Bool)    (hcoins : ∀ i : Fin edges.length,      (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}).Reachable v (edges.get i).1 →      r i = s i) :  forest_carpool_final_discrepancy n edges r v =    forest_carpool_final_discrepancy n edges s v := by  rw [ForestCarpoolLocal.final_eq, ForestCarpoolLocal.final_eq]  refine ForestCarpoolLocal.G_local n (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}) v edges _ _ _ _ ?_    (by simp) ?_ (fun _ _ => rfl) v (SimpleGraph.Reachable.refl v)  · intro e he    by_cases h : e.1 = e.2    · exact Or.inl h    · exact Or.inr (SimpleGraph.fromEdgeSet_adj _ |>.mpr ⟨⟨e, he, rfl⟩, h⟩)  · intro j hj hr    have := hcoins ⟨j, hj⟩ (by simpa using hr)    simp [hj, this]
See it in the graphDiscuss this resultChallenge it