op_902_single_edge_max_discrepancy
On any single-edge carpooling instance with distinct endpoints, the maximum discrepancy under any orientation sign is at most 1.
Statement
theorem op_902_single_edge_max_discrepancy (n : ℕ) (e : Fin n × Fin n) (he : e.1 ≠ e.2)
(b : Bool) :
carpool_max_discrepancy n [e] [b] ≤ 1- Formalizes
- arXiv:2611.00388 Sec 1.1, Online carpooling against an oblivious adversary
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- Used by 1
- op_1106_forest_carpooling_single_edge_max_discrepancyFor any single edge on Fin n with distinct endpoints and any initial coin, randomized greedy carpooling produces a maximum discrepancy of…
Read back from the Lean
For every natural number $n$, every directed edge $e \in \mathrm{Fin}(n) \times \mathrm{Fin}(n)$ whose endpoints are distinct ($e.1 \neq e.2$), and every boolean sign $b$, the carpool maximum discrepancy (carpool_max_discrepancy) of the single-edge list $[e]$ with sign list $[b]$ on $n$ vertices 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
The maximum carpool discrepancy over an edge sequence is defined as the maximum discrepancy across all intermediate states, starting from 0. For a single edge, there are only two states: the initial zero state and the state after orienting the edge. At the initial state, every vertex has discrepancy 0, and after the single step, every vertex has discrepancy at most 1 in absolute value. Since both intermediate maximum discrepancies are bounded by 1, their overall maximum is at most 1.
The initial state where all vertex discrepancies are zero has maximum vertex discrepancy at most 1.
Line 5 notes the hypothesis $e.1 \neq e.2$. By definition, the maximum vertex discrepancy of the zero function is the supremum of $|0|$ over all vertices. By `Finset.sup_le`, this supremum is at most 1 provided that $|0| \le 1$ at every vertex $v$, which holds by basic arithmetic (`norm_num`).
uses
Finset.sup_lehave _ := he have hd0 : max_vertex_discrepancy n (fun _ => 0) ≤ 1 := by unfold max_vertex_discrepancy apply Finset.sup_le intro v _ norm_num
After updating along edge $e$ with orientation $b$, the maximum vertex discrepancy remains at most 1.
Unfolding the definition and applying `Finset.sup_le`, it suffices to verify that every vertex $v$ has discrepancy of absolute value at most 1 after the step. The step definition adds $\pm 1$ at $e.1$, $\mp 1$ at $e.2$ (depending on the boolean sign $b$), and 0 elsewhere. A case split on whether $v = e.1$, $v = e.2$, and whether $b$ is true (`split_ifs`) reduces each case to an arithmetic computation verified by `norm_num`.
uses
Finset.sup_lehave hd1 : max_vertex_discrepancy n (carpool_step n (fun _ => 0) e b) ≤ 1 := by unfold max_vertex_discrepancy apply Finset.sup_le intro v _ unfold carpool_step dsimp split_ifs <;> norm_num
The overall maximum carpool discrepancy definitionally reduces to $\max(\max(0, D_0), D_1) \le 1$.
For a single edge $[e]$ and single sign $[b]$, the sequence of intermediate states consists only of the initial zero state $D_0$ and the updated state $D_1$. The definition of `carpool_max_discrepancy` folds the binary maximum starting at 0 over this list, which definitionally simplifies to $\max(\max(0, D_0), D_1) \le 1$.
change max (max 0 (max_vertex_discrepancy n (fun _ => 0))) (max_vertex_discrepancy n (carpool_step n (fun _ => 0) e b)) ≤ 1
The maximum carpool discrepancy on the single edge is at most 1.
Rewriting with `max_le_iff` decomposes the condition $\max(\max(0, D_0), D_1) \le 1$ into three bounds: $0 \le 1$, $D_0 \le 1$, and $D_1 \le 1$. The first is immediate from arithmetic, while the latter two are precisely the previously proved bounds `hd0` and `hd1`.
uses
max_le_iffrw [max_le_iff, max_le_iff] exact ⟨⟨by norm_num, hd0⟩, hd1⟩
Finset.sup_le- The supremum of a function $f$ over a finite set $s$ is bounded above by $a$ if $f(b) \le a$ for all $b \in s$.
max_le_iff- The maximum $\max(a, b)$ is at most $c$ if and only if both $a \le c$ and $b \le c$.
- Line 5 (`have _ := he`) references the assumption that the endpoints are distinct solely to silence an unused-variable compiler warning. The proof does not mathematically require $e.1 \neq e.2$, because the case analysis in line 17 covers coincident endpoints as well (yielding a net update of 0).
- Lines 18–19 use `change` to rewrite the goal via definitional equality: on a list of length 1, the definitions of `carpool_discrepancies` and `carpool_max_discrepancy` evaluate directly to $\max(\max(0, D_0), D_1)$ without needing list lemmas.
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.
/-- Any orientation on a single edge has maximum discrepancy at most 1. -/theorem op_902_single_edge_max_discrepancy (n : ℕ) (e : Fin n × Fin n) (he : e.1 ≠ e.2) (b : Bool) : carpool_max_discrepancy n [e] [b] ≤ 1 := by have _ := he have hd0 : max_vertex_discrepancy n (fun _ => 0) ≤ 1 := by unfold max_vertex_discrepancy apply Finset.sup_le intro v _ norm_num have hd1 : max_vertex_discrepancy n (carpool_step n (fun _ => 0) e b) ≤ 1 := by unfold max_vertex_discrepancy apply Finset.sup_le intro v _ unfold carpool_step dsimp split_ifs <;> norm_num change max (max 0 (max_vertex_discrepancy n (fun _ => 0))) (max_vertex_discrepancy n (carpool_step n (fun _ => 0) e b)) ≤ 1 rw [max_le_iff, max_le_iff] exact ⟨⟨by norm_num, hd0⟩, hd1⟩