AFTD Auto-Formalizing Theoretical Domains

op_1106_forest_carpooling_length_two_bound

theoremverified

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.

  1. 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.

    lines 4–6

    uses if_neg

      dsimp [carpool_step]
      rw [if_neg h1, if_neg h2]
      ring
  2. 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.

    lines 10–12

    uses if_pos, if_neg

      dsimp [carpool_step]
      rw [if_pos rfl, if_neg he]
      ring
  3. 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.

    lines 16–18

    uses if_pos, if_neg, Ne.symm

      dsimp [carpool_step]
      rw [if_neg (Ne.symm he), if_pos rfl]
      ring
  4. 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.

    lines 26–32

    uses carpool_greedy_orientations.aux.eq_def, if_neg

      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 1
  5. 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.

    lines 39–40

      dsimp [carpool_max_discrepancy, carpool_discrepancies]
      rfl
  6. 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].

    lines 44–45

      dsimp [carpool_step]
      split_ifs <;> omega
  7. 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.

    lines 50–52

      dsimp [carpool_step]
      intro ⟨h1, h2⟩
      split_ifs at h1 h2 <;> (try subst_vars) <;> (try contradiction)
  8. 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.

    lines 57–59

      dsimp [carpool_step]
      intro ⟨h1, h2⟩
      split_ifs at h1 h2 <;> (try subst_vars) <;> (try contradiction)
  9. 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].

    lines 69–76

      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)
  10. 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.

    lines 85–93

    uses op_1106_carpool_greedy_two, op_1106_carpool_max_discrepancy_two, max_le_iff

      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, ?_⟩, ?_⟩, ?_⟩
  11. 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.

    lines 94–97

    uses Finset.sup_le

        · unfold max_vertex_discrepancy
          apply Finset.sup_le
          intro v _
          norm_num
  12. 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.

    lines 98–102

    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
  13. 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].

    lines 103–125

    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

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
See it in the graphDiscuss this resultChallenge it