op_1106_forest_carpooling_length_two_bound
For any oblivious forest edge sequence of length 2 on Fin n and any assignment of 2 coins, the maximum prefix discrepancy under randomized greedy carpooling is at most 1.
Statement
theorem op_1106_forest_carpooling_length_two_bound
(n : ℕ) (edges : List (Fin n × Fin n))
(hT : edges.length = 2)
(hforest : CarpoolForestEdgeSequence n edges)
(coins : List Bool) (hcoins : coins.length = 2) :
carpool_max_discrepancy n edges (carpool_greedy_orientations n edges coins) ≤ 1- Source
- arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- CarpoolForestEdgeSequenceA list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected…
- 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_max_discrepancyThe maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
- max_vertex_discrepancyThe maximum absolute discrepancy among all vertices for an integer discrepancy vector d on n vertices.
- carpool_stepIn online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d…
- ValidCarpoolEdgeSequenceA list of edges on n vertices is valid for online carpooling if every arriving edge connects two distinct vertices.
- 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…
Read back from the Lean
For every natural number n, list edges of pairs of vertices in Fin n, and list coins of Booleans:
if edges has length 2,
and edges forms a carpool forest edge sequence (meaning every edge has distinct endpoints, the list of unordered edges has no duplicates, and the graph formed by these edges is acyclic),
and coins has length 2,
then the maximum vertex discrepancy across all intermediate and final discrepancy states resulting from the greedy orientation algorithm on edges with tie-breaking coins coins is at most 1.
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
To prove that randomized greedy carpooling on two forest edges achieves maximum discrepancy at most 1, the proof decomposes the prefix discrepancy into three stages: initial, after edge 1, and after edge 2. The initial and first-step discrepancies are bounded by 1 since each vertex changes by at most 1 from zero. For the second step, because the edge has distinct endpoints that cannot both have reached +1 or both -1 in the first step, the greedy decision rule guarantees that both endpoints remain in [-1, 1], while non-incident vertices retain their step-1 discrepancies.
For any vertex v not incident to an edge e, a carpool step leaves the discrepancy at v unchanged.
Unfolding carpool_step, both conditions v = e.1 and v = e.2 evaluate to false by hypothesis, so both conditional adjustments are zero.
uses
if_negdsimp [carpool_step] rw [if_neg h1, if_neg h2] ring
For an edge e with distinct endpoints, a carpool step adjusts the discrepancy at the first endpoint by +1 if b is true and -1 if b is false.
Unfolding carpool_step, the condition for the first endpoint holds while that for the second endpoint is false since e.1 ≠ e.2, leaving only the first endpoint's adjustment.
uses
if_pos,if_negdsimp [carpool_step] rw [if_pos rfl, if_neg he] ring
For an edge e with distinct endpoints, a carpool step adjusts the discrepancy at the second endpoint by -1 if b is true and +1 if b is false.
Unfolding carpool_step, the first condition is false by symmetry of distinctness and the second is true, applying the second endpoint's adjustment.
uses
if_pos,if_neg,Ne.symmdsimp [carpool_step] rw [if_neg (Ne.symm he), if_pos rfl] ring
For two edges, greedy orientation uses the first coin for the first edge and greedily balances the endpoints of the second edge.
Unfolding carpool_greedy_orientations, since the initial discrepancy is everywhere zero, 0 < 0 is false in both directions, so the greedy rule defaults to the coin c1 for edge 1. The remaining orientation b2 is defined by the greedy balance rule on the resulting state d1.
uses
carpool_greedy_orientations.aux.eq_def,if_negunfold carpool_greedy_orientations rw [carpool_greedy_orientations.aux.eq_def] dsimp only have h1 : ¬ ((0 : ℤ) < 0) := by decide change (if (0 : ℤ) < 0 then true else if (0 : ℤ) < 0 then false else c1) :: _ = _ rw [if_neg h1, if_neg h1] congr 1
The maximum discrepancy over a two-step sequence is the maximum of 0, the discrepancy of the zero state, and the discrepancies after steps 1 and 2.
By definition, carpool_discrepancies produces the list of states [0, d1, d2], and taking the maximum vertex discrepancy over these prefixes unfolds directly to nested pairwise maximums.
dsimp [carpool_max_discrepancy, carpool_discrepancies] rfl
Starting from zero, every vertex has discrepancy between -1 and 1 after one carpool step. automation
Case analysis on whether a vertex v is the first endpoint, the second endpoint, or neither shows that the resulting discrepancy is 1, -1, or 0, all of which lie in [-1, 1].
dsimp [carpool_step] split_ifs <;> omega
Starting from zero along a non-loop edge, two distinct vertices cannot both have discrepancy 1 after one step. automation
Assuming for contradiction that both distinct vertices reach discrepancy 1, case analysis on vertex equality with the edge endpoints shows that no orientation can increase both vertices simultaneously.
dsimp [carpool_step] intro ⟨h1, h2⟩ split_ifs at h1 h2 <;> (try subst_vars) <;> (try contradiction)
Starting from zero along a non-loop edge, two distinct vertices cannot both have discrepancy -1 after one step. automation
Similarly, assuming both distinct vertices reach discrepancy -1 contradicts the update rule, which decreases at most one vertex per step.
dsimp [carpool_step] intro ⟨h1, h2⟩ split_ifs at h1 h2 <;> (try subst_vars) <;> (try contradiction)
If edge endpoint discrepancies lie in [-1, 1] and are not both 1 or both -1, the greedy step keeps both discrepancies in [-1, 1]. automation
Exhaustive case analysis on the coin and the possible integer values in {-1, 0, 1} shows that the greedy choice ensures both updated values remain in [-1, 1].
rcases c with _ | _ <;> interval_cases x <;> interval_cases y <;> intro b <;> dsimp [b] <;> first | (exfalso; apply hnot_both_pos; decide) | (exfalso; apply hnot_both_neg; decide) | (revert b; decide)
The two-step maximum discrepancy bound reduces to bounding the vertex discrepancy at the initial state, after step 1, and after step 2.
Deconstructing the edge sequence and coins of length 2 as [e1, e2] and [c1, c2], the forest hypothesis guarantees that neither edge is a loop. Rewriting with op_1106_carpool_greedy_two and op_1106_carpool_max_discrepancy_two reduces the discrepancy bound to showing that 0 ≤ 1 (trivially) and that the vertex discrepancy at each of the three prefix states is at most 1.
uses
op_1106_carpool_greedy_two,op_1106_carpool_max_discrepancy_two,max_le_iffmatch edges, coins, hT, hcoins with | [e1, e2], [c1, c2], _, _ => have he1 : e1.1 ≠ e1.2 := hforest.1 e1 (by simp) have he2 : e2.1 ≠ e2.2 := hforest.1 e2 (by simp) rw [op_1106_carpool_greedy_two] dsimp only rw [op_1106_carpool_max_discrepancy_two] simp only [max_le_iff] refine ⟨⟨⟨by norm_num, ?_⟩, ?_⟩, ?_⟩
The vertex discrepancy of the initial zero state is at most 1.
At every vertex the initial discrepancy is 0, so its absolute value is 0 ≤ 1.
uses
Finset.sup_le· unfold max_vertex_discrepancy apply Finset.sup_le intro v _ norm_num
The vertex discrepancy after the first edge step is at most 1.
For every vertex v, op_1106_carpool_step_zero_bounds shows that the discrepancy lies in [-1, 1], so its absolute value is at most 1 by linear integer arithmetic.
uses
Finset.sup_le,op_1106_carpool_step_zero_bounds· unfold max_vertex_discrepancy apply Finset.sup_le intro v _ have hb := op_1106_carpool_step_zero_bounds n e1 c1 v omega
The vertex discrepancy after the second edge step is at most 1.
For any vertex v, the discrepancies of e2's endpoints after step 1 lie in [-1, 1] and cannot both be 1 or both -1 by op_1106_carpool_step_zero_not_both_one and op_1106_carpool_step_zero_not_both_neg_one. By op_1106_carpool_greedy_step_bounded, the greedy choice keeps both endpoint discrepancies within absolute value 1. Case analysis on v shows that if v is an endpoint, its discrepancy is bounded by op_1106_carpool_step_fst or op_1106_carpool_step_snd; if v is not in e2, its discrepancy is unchanged from step 1 by op_1106_carpool_step_not_mem and hence remains bounded in [-1, 1].
uses
Finset.sup_le,op_1106_carpool_step_zero_bounds,op_1106_carpool_step_zero_not_both_one,op_1106_carpool_step_zero_not_both_neg_one,op_1106_carpool_greedy_step_bounded,op_1106_carpool_step_fst,op_1106_carpool_step_snd,op_1106_carpool_step_not_mem· unfold max_vertex_discrepancy apply Finset.sup_le intro v _ set d1 := carpool_step n (fun _ => 0) e1 c1 set b2 := if d1 e2.1 < d1 e2.2 then true else if d1 e2.2 < d1 e2.1 then false else c2 have hx_bounds := op_1106_carpool_step_zero_bounds n e1 c1 e2.1 have hy_bounds := op_1106_carpool_step_zero_bounds n e1 c1 e2.2 have hnot_pos := op_1106_carpool_step_zero_not_both_one n e1 he1 c1 e2.1 e2.2 he2 have hnot_neg := op_1106_carpool_step_zero_not_both_neg_one n e1 he1 c1 e2.1 e2.2 he2 have hstep := op_1106_carpool_greedy_step_bounded (d1 e2.1) (d1 e2.2) c2 hx_bounds.1 hx_bounds.2 hy_bounds.1 hy_bounds.2 hnot_pos hnot_neg by_cases hv1 : v = e2.1 · subst hv1 rw [op_1106_carpool_step_fst n d1 e2 he2 b2] exact hstep.1 · by_cases hv2 : v = e2.2 · subst hv2 rw [op_1106_carpool_step_snd n d1 e2 he2 b2] exact hstep.2 · rw [op_1106_carpool_step_not_mem n d1 e2 b2 v hv1 hv2] dsimp [d1] have hb := op_1106_carpool_step_zero_bounds n e1 c1 v omega
if_neg- if a condition is false, an if-then-else expression reduces to the else branch
if_pos- if a condition is true, an if-then-else expression reduces to the then branch
Ne.symm- inequality is symmetric: if a ≠ b then b ≠ a
carpool_greedy_orientations.aux.eq_def- the definitional equation for the recursive helper of greedy orientations
max_le_iff- a maximum of two numbers is at most c if and only if both numbers are at most c
Finset.sup_le- the supremum of a finite set is at most a value if and only if every element is at most that value
op_1106_carpool_greedy_two- the greedy orientations for a two-edge sequence use the first coin on edge 1 and greedily balance edge 2
op_1106_carpool_max_discrepancy_two- the maximum discrepancy over two edges expands to the maximum over the three prefix states
op_1106_carpool_step_zero_bounds- starting from discrepancy zero, a single edge step leaves all vertex discrepancies in the interval [-1, 1]
op_1106_carpool_step_zero_not_both_one- after one step from zero along an edge with distinct endpoints, two distinct vertices cannot both have discrepancy 1
op_1106_carpool_step_zero_not_both_neg_one- after one step from zero along an edge with distinct endpoints, two distinct vertices cannot both have discrepancy -1
op_1106_carpool_greedy_step_bounded- if endpoint discrepancies lie in [-1, 1] and are not both 1 or both -1, greedy updating keeps both in [-1, 1]
op_1106_carpool_step_fst- updating a non-loop edge adjusts the first endpoint by +1 or -1 depending on the orientation
op_1106_carpool_step_snd- updating a non-loop edge adjusts the second endpoint by -1 or +1 depending on the orientation
op_1106_carpool_step_not_mem- vertices not incident to the edge are unaffected by a carpool step
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.
Lean’s trace was cut to the first 400 of 520 tactics.
lemma op_1106_carpool_step_not_mem (n : ℕ) (d : Fin n → ℤ) (e : Fin n × Fin n) (b : Bool) (v : Fin n) (h1 : v ≠ e.1) (h2 : v ≠ e.2) : carpool_step n d e b v = d v := by dsimp [carpool_step] rw [if_neg h1, if_neg h2] ringlemma op_1106_carpool_step_fst (n : ℕ) (d : Fin n → ℤ) (e : Fin n × Fin n) (he : e.1 ≠ e.2) (b : Bool) : carpool_step n d e b e.1 = d e.1 + if b then 1 else -1 := by dsimp [carpool_step] rw [if_pos rfl, if_neg he] ringlemma op_1106_carpool_step_snd (n : ℕ) (d : Fin n → ℤ) (e : Fin n × Fin n) (he : e.1 ≠ e.2) (b : Bool) : carpool_step n d e b e.2 = d e.2 + if b then -1 else 1 := by dsimp [carpool_step] rw [if_neg (Ne.symm he), if_pos rfl] ringlemma op_1106_carpool_greedy_two (n : ℕ) (e1 e2 : Fin n × Fin n) (c1 c2 : Bool) : carpool_greedy_orientations n [e1, e2] [c1, c2] = let b1 := c1 let d1 := carpool_step n (fun _ => 0) e1 b1 let b2 := if d1 e2.1 < d1 e2.2 then true else if d1 e2.2 < d1 e2.1 then false else c2 [b1, b2] := by unfold carpool_greedy_orientations rw [carpool_greedy_orientations.aux.eq_def] dsimp only have h1 : ¬ ((0 : ℤ) < 0) := by decide change (if (0 : ℤ) < 0 then true else if (0 : ℤ) < 0 then false else c1) :: _ = _ rw [if_neg h1, if_neg h1] congr 1lemma op_1106_carpool_max_discrepancy_two (n : ℕ) (e1 e2 : Fin n × Fin n) (b1 b2 : Bool) : carpool_max_discrepancy n [e1, e2] [b1, b2] = max (max (max 0 (max_vertex_discrepancy n (fun _ => 0))) (max_vertex_discrepancy n (carpool_step n (fun _ => 0) e1 b1))) (max_vertex_discrepancy n (carpool_step n (carpool_step n (fun _ => 0) e1 b1) e2 b2)) := by dsimp [carpool_max_discrepancy, carpool_discrepancies] rfllemma op_1106_carpool_step_zero_bounds (n : ℕ) (e : Fin n × Fin n) (b : Bool) (v : Fin n) : -1 ≤ carpool_step n (fun _ => 0) e b v ∧ carpool_step n (fun _ => 0) e b v ≤ 1 := by dsimp [carpool_step] split_ifs <;> omegalemma op_1106_carpool_step_zero_not_both_one (n : ℕ) (e : Fin n × Fin n) (he : e.1 ≠ e.2) (b : Bool) (u v : Fin n) (huv : u ≠ v) : ¬ (carpool_step n (fun _ => 0) e b u = 1 ∧ carpool_step n (fun _ => 0) e b v = 1) := by dsimp [carpool_step] intro ⟨h1, h2⟩ split_ifs at h1 h2 <;> (try subst_vars) <;> (try contradiction)lemma op_1106_carpool_step_zero_not_both_neg_one (n : ℕ) (e : Fin n × Fin n) (he : e.1 ≠ e.2) (b : Bool) (u v : Fin n) (huv : u ≠ v) : ¬ (carpool_step n (fun _ => 0) e b u = -1 ∧ carpool_step n (fun _ => 0) e b v = -1) := by dsimp [carpool_step] intro ⟨h1, h2⟩ split_ifs at h1 h2 <;> (try subst_vars) <;> (try contradiction)lemma op_1106_carpool_greedy_step_bounded (x y : ℤ) (c : Bool) (hx1 : -1 ≤ x) (hx2 : x ≤ 1) (hy1 : -1 ≤ y) (hy2 : y ≤ 1) (hnot_both_pos : ¬(x = 1 ∧ y = 1)) (hnot_both_neg : ¬(x = -1 ∧ y = -1)) : let b := if x < y then true else if y < x then false else c (x + (if b then 1 else -1)).natAbs ≤ 1 ∧ (y + (if b then -1 else 1)).natAbs ≤ 1 := by rcases c with _ | _ <;> interval_cases x <;> interval_cases y <;> intro b <;> dsimp [b] <;> first | (exfalso; apply hnot_both_pos; decide) | (exfalso; apply hnot_both_neg; decide) | (revert b; decide)/-- On any forest edge sequence of length 2, randomized greedy carpooling achieves maximum discrepancy at most 1 for any coin assignment. -/theorem op_1106_forest_carpooling_length_two_bound (n : ℕ) (edges : List (Fin n × Fin n)) (hT : edges.length = 2) (hforest : CarpoolForestEdgeSequence n edges) (coins : List Bool) (hcoins : coins.length = 2) : carpool_max_discrepancy n edges (carpool_greedy_orientations n edges coins) ≤ 1 := by match edges, coins, hT, hcoins with | [e1, e2], [c1, c2], _, _ => have he1 : e1.1 ≠ e1.2 := hforest.1 e1 (by simp) have he2 : e2.1 ≠ e2.2 := hforest.1 e2 (by simp) rw [op_1106_carpool_greedy_two] dsimp only rw [op_1106_carpool_max_discrepancy_two] simp only [max_le_iff] refine ⟨⟨⟨by norm_num, ?_⟩, ?_⟩, ?_⟩ · unfold max_vertex_discrepancy apply Finset.sup_le intro v _ norm_num · unfold max_vertex_discrepancy apply Finset.sup_le intro v _ have hb := op_1106_carpool_step_zero_bounds n e1 c1 v omega · unfold max_vertex_discrepancy apply Finset.sup_le intro v _ set d1 := carpool_step n (fun _ => 0) e1 c1 set b2 := if d1 e2.1 < d1 e2.2 then true else if d1 e2.2 < d1 e2.1 then false else c2 have hx_bounds := op_1106_carpool_step_zero_bounds n e1 c1 e2.1 have hy_bounds := op_1106_carpool_step_zero_bounds n e1 c1 e2.2 have hnot_pos := op_1106_carpool_step_zero_not_both_one n e1 he1 c1 e2.1 e2.2 he2 have hnot_neg := op_1106_carpool_step_zero_not_both_neg_one n e1 he1 c1 e2.1 e2.2 he2 have hstep := op_1106_carpool_greedy_step_bounded (d1 e2.1) (d1 e2.2) c2 hx_bounds.1 hx_bounds.2 hy_bounds.1 hy_bounds.2 hnot_pos hnot_neg by_cases hv1 : v = e2.1 · subst hv1 rw [op_1106_carpool_step_fst n d1 e2 he2 b2] exact hstep.1 · by_cases hv2 : v = e2.2 · subst hv2 rw [op_1106_carpool_step_snd n d1 e2 he2 b2] exact hstep.2 · rw [op_1106_carpool_step_not_mem n d1 e2 b2 v hv1 hv2] dsimp [d1] have hb := op_1106_carpool_step_zero_bounds n e1 c1 v omega