AFTD Auto-Formalizing Theoretical Domains

ocacagSplit

def

Bisect the integer interval c = [c.1, c.2] at its midpoint m = floor((c.1+c.2)/2), returning the half that contains v: [c.1, m] if v ≤ m, else [m+1, c.2].

Statement

def ocacagSplit (c : ℤ × ℤ) (v : ℤ) : ℤ × ℤ
Source
step towards online_cycle_augmentation_adversary_cost_ge
Verified
09 Nov 2026
Axioms
none listed
Used by 2
  • ocacagChainAuxThe list of nested dyadic cuts obtained by starting at interval c and bisecting t times toward the vertex v: [c] for t = 0, and c ::…
  • ocacagChainThe dyadic chain to leaf v: start at the top cut [1, 2^(k-1)] and bisect k-1 times toward v, giving k nested cuts down to the singleton {v}.

Lean source view module on GitHub

/-- One step of the dyadic bisection, keeping the half that contains `v`. -/
def ocacagSplit (c : ℤ × ℤ) (v : ℤ) : ℤ × ℤ := if v ≤ (c.1 + c.2) / 2 then (c.1, (c.1 + c.2) / 2) else ((c.1 + c.2) / 2 + 1, c.2)
See it in the graphDiscuss this resultChallenge it