AFTD Auto-Formalizing Theoretical Domains

carpool_step

def

In online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d updates by adding 1 to e.1 and -1 to e.2 if b is true, and the opposite if b is false.

Statement

def carpool_step (n : ℕ) (d : Fin n → ℤ) (e : Fin n × Fin n) (b : Bool) : Fin n → ℤ
Defined in
arXiv:2611.00388 Eq (1.1), Online carpooling against an oblivious adversary
Verified
06 Nov 2026
Axioms
none listed
Used by 7

Read back from the Lean

carpool_step n d e b is the function Fin n → ℤ that updates a vector d : Fin n → ℤ along a pair e = (e.1, e.2) : Fin n × Fin n according to a boolean b : Bool. For any v : Fin n, the value is: - d v + (if b then 1 else -1) if v = e.1 and v ≠ e.2; - d v + (if b then -1 else 1) if v = e.2 and v ≠ e.1; - d v if v = e.1 = e.2 (the +1 and -1 cancel out); - d v if v ≠ e.1 and v ≠ e.2.

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

/-- One step of discrepancy update in online carpooling for an edge e with orientation sign b. -/
def carpool_step (n : ℕ) (d : Fin n → ℤ) (e : Fin n × Fin n) (b : Bool) : Fin n → ℤ := fun v => d v +
    (if v = e.1 then (if b then 1 else -1) else 0) +
    (if v = e.2 then (if b then -1 else 1) else 0)
See it in the graphDiscuss this resultChallenge it