AFTD Auto-Formalizing Theoretical Domains

op_902_single_edge_max_discrepancy

theoremverifiedformalization

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

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.

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

    lines 5–10

    uses Finset.sup_le

      have _ := he
      have hd0 : max_vertex_discrepancy n (fun _ => 0) ≤ 1 := by
        unfold max_vertex_discrepancy
        apply Finset.sup_le
        intro v _
        norm_num
  2. 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`.

    lines 11–17

    uses Finset.sup_le

      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
  3. 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$.

    lines 18–19

      change max (max 0 (max_vertex_discrepancy n (fun _ => 0)))
        (max_vertex_discrepancy n (carpool_step n (fun _ => 0) e b)) ≤ 1
  4. 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`.

    lines 20–21

    uses max_le_iff

      rw [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$.

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

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