AFTD Auto-Formalizing Theoretical Domains

carpool_max_discrepancy

def

The maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.

Statement

def carpool_max_discrepancy (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) : ℕ
Defined in
arXiv:2611.00388 Eq (1.2), Online carpooling against an oblivious adversary
Verified
06 Nov 2026
Axioms
none listed
Built on 2
  • 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…
  • max_vertex_discrepancyThe maximum absolute discrepancy among all vertices for an integer discrepancy vector d on n vertices.
Used by 5

Read back from the Lean

The definition carpool_max_discrepancy n edges signs computes the maximum discrepancy across all vertices and across all prefix steps during the carpool process, returning a natural number ℕ. Given: - n : ℕ: the number of vertices, with vertex set Fin n, - edges : List (Fin n × Fin n): a sequence of directed edges, - signs : List Bool: a sequence of boolean choices, the function computes: 1. The list of pairs obtained by zipping edges with signs (truncated to the length of the shorter list). 2. The sequence of discrepancy functions Fin n → ℤ produced by scanl, starting from the all-zero function fun _ => 0. At each step with edge e = (u, v) and sign b : Bool, the discrepancy vector d is updated at vertex x by adding (if b then 1 else -1) if x = u and (if b then -1 else 1) if x = v (adding both if u = v). 3. For each intermediate discrepancy state d : Fin n → ℤ (including the initial all-zero state), the maximum vertex discrepancy max_{v : Fin n} |d(v)| (computed via Finset.univ.sup (fun v => (d v).natAbs)). 4. The maximum over all intermediate states of these maximum vertex discrepancies, folded via max starting at 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The maximum prefix discrepancy M_T of an online carpooling trajectory. -/
def carpool_max_discrepancy (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) : ℕ := ((carpool_discrepancies n edges signs).map (max_vertex_discrepancy n)).foldl max 0
See it in the graphDiscuss this resultChallenge it