forest_carpool_component_coin_locality
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
- forest_carpool_disjoint_components_independentIf appending the edge u-v to the given prefix yields a forest, then under uniformly random prefix coins the two endpoint final…
- forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
- forest_carpool_maximum_fibonacci_tailFor a forest arrival sequence, the probability that any vertex at any prefix has absolute discrepancy at least D is at most four times the…
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.
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.
uses
List.zip_cons_cons,List.scanl_cons,List.getLastD_consinduction 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
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.
uses
scan_equnfold forest_carpool_final_discrepancy carpool_discrepancies carpool_greedy_orientations exact scan_eq n edges (List.ofFn r) _ _
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.
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]
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.
· 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]
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.
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' =>
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.
uses
List.mem_cons_of_mem,local_step,List.mem_cons_selfsimp 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
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.
uses
ForestCarpoolLocal.final_eq,ForestCarpoolLocal.G_local,SimpleGraph.Reachable.reflrw [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)
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 Γ.
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⟩)
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.
· 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.
- The proof introduces an auxiliary recursive function ForestCarpoolLocal.G and proves it equivalent to the scanl-based discrepancy definitions via scan_eq and final_eq, facilitating structural induction on edge lists.
- The graph Γ is defined as the simple graph whose edges are the unordered pairs of endpoints from the edge list, ignoring self-loops and edge direction, which exactly captures the reachability structure needed for component locality.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]