AFTD Auto-Formalizing Theoretical Domains

carpool_discrepancies

def

The 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 edge and its orientation sign.

Statement

def carpool_discrepancies (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) :
    List (Fin n → ℤ)
Defined in
arXiv:2611.00388 Eq (1.1), Online carpooling against an oblivious adversary
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • 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 4

Read back from the Lean

A definition of carpool_discrepancies n edges signs, which computes the list of cumulative discrepancy states (functions from Fin n to ℤ) across a sequence of steps. Given: - n : ℕ, the number of vertices, - edges : List (Fin n × Fin n), a list of directed edges, - signs : List Bool, a list of boolean signs, the function pairs edges and signs elementwise using List.zip (truncating to the length of the shorter list), and performs a left scan (List.scanl) starting from the all-zero discrepancy function fun _ => 0. At each step, for the current discrepancy d : Fin n → ℤ, an edge e = (e.1, e.2), and a boolean sign b, the discrepancy is updated via carpool_step n d e b: - vertex e.1 changes by +1 if b = true and -1 if b = false; - vertex e.2 changes by -1 if b = true and +1 if b = false (with effects summing to 0 if e.1 = e.2); - all other vertices remain unchanged. The resulting list has length min (edges.length) (signs.length) + 1, with the initial all-zero function as its first element.

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 trajectory of discrepancy vectors from time 0 to T for an edge sequence and signs. -/
def carpool_discrepancies (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) :
    List (Fin n → ℤ) := (edges.zip signs).scanl (fun d (e, b) => carpool_step n d e b) (fun _ => 0)
See it in the graphDiscuss this resultChallenge it