AFTD Auto-Formalizing Theoretical Domains

online_carpool_orientations

def

For an instance on vertex set Fin n and a random tape r of K boolean coins, given an orientation function orient that takes an edge history in List (Fin n × Fin n) and the coins in Fin K → Bool to an orientation bit in Bool, online_carpool_orientations n orient edges r is the list of boolean orientations for the edges in edges, where the i-th edge is oriented using orient applied to the prefix edges.take (i + 1) and r.

Statement

def online_carpool_orientations (n : ℕ) {K : ℕ}
    (orient : List (Fin n × Fin n) → (Fin K → Bool) → Bool)
    (edges : List (Fin n × Fin n)) (r : Fin K → Bool) : List Bool
Defined in
arXiv:2611.00388 Sec 1.1, Online carpooling against an oblivious adversary
Verified
06 Nov 2026
Axioms
none listed

Read back from the Lean

Given a natural number n, an implicit natural number K, an orientation rule orient : List (Fin n × Fin n) → (Fin K → Bool) → Bool, a list of edges edges : List (Fin n × Fin n), and a function r : Fin K → Bool, online_carpool_orientations n orient edges r is defined as the List Bool of length edges.length whose i-th element (for index i : Fin edges.length) is orient (edges.take (i.val + 1)) r (that is, the result of evaluating orient on the prefix of edges of length i + 1 together with r).

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 list of boolean orientations produced by an online carpooling algorithm given edge history on Fin n and random coins. -/
def online_carpool_orientations (n : ℕ) {K : ℕ}
    (orient : List (Fin n × Fin n) → (Fin K → Bool) → Bool)
    (edges : List (Fin n × Fin n)) (r : Fin K → Bool) : List Bool := List.ofFn (fun i : Fin edges.length => orient (edges.take (i.val + 1)) r)
See it in the graphDiscuss this resultChallenge it