AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_costs

def

Given n facilities placed at integers 0, ..., n-1 on the circle ℝ/nℤ and an arrival sequence x in Fin n -> Real arriving in sequential order 0, ..., n-1, cycle_greedy_costs n x is the function mapping each i in Fin n to the shortest-arc distance from arrival x i to its assigned nearest free facility in Fin n, where shortest-arc distance is |(x i - j) - n * round((x i - j)/n)| and ties among equidistant free facilities are broken by choosing the facility with the smallest index j.

Statement

noncomputable def cycle_greedy_costs (n : ℕ) (x : Fin n → ℝ) : Fin n → ℝ
Defined in
arXiv:2610.15776
Verified
03 Nov 2026
Axioms
none listed
Used by 1
  • cycle_greedy_costs_measurableFor every n, the vector of sequential nearest-free greedy costs is a Borel measurable function of the arrival vector.

Read back from the Lean

cycle_greedy_costs n x defines a function of type Fin n → ℝ for a given natural number n and a sequence of positions x : Fin n → ℝ. It computes the sequence of costs obtained by greedily matching each point x i (for i in order from 0 to n - 1) to an available index j ∈ Fin n on a circle of circumference n: 1. **Circular distance**: For $a \in \mathbb{R}$ and $j \in \text{Fin } n$, if $n = 0$ the distance is $0$; otherwise, with $d = a - j$ and $k = \lfloor d/n + 1/2 \rfloor$, the circular distance is $|d - n \cdot k|$. 2. **Greedy selection**: Starting with all indices in $\text{Fin } n$ available (free = Finset.univ), for each index $i \in \text{Fin } n$ in increasing order ($0, 1, \dots, n-1$): - Find the minimum circular distance from $x(i)$ to any available index $j \in \text{free}$. - Choose the candidate $j \in \text{free}$ achieving this minimum distance, breaking ties by selecting the smallest index $j$ in $\text{Fin } n$. - Record the chosen minimum distance as the cost for step $i$, and remove $j$ from $\text{free}$. 3. **Output**: Returns the function mapping each $i \in \text{Fin } n$ to the cost recorded at step $i$ (retrieved as the $i$-th element of the resulting list of costs).

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

/-- Vector of shortest-arc distances paid by each of n successive continuous arrivals on a circle of circumference n under nearest-free greedy facility assignment. -/
noncomputable def cycle_greedy_costs (n : ℕ) (x : Fin n → ℝ) : Fin n → ℝ :=
  let circ_dist (a : ℝ) (j : Fin n) : ℝ :=
    if n = 0 then 0
    else
      let d := a - (j.val : ℝ)
      let k : ℝ := ((⌊d / (n : ℝ) + 1 / 2⌋ : ℤ) : ℝ)
      |d - (n : ℝ) * k|
  let choose (free : Finset (Fin n)) (h : free.Nonempty) (x : ℝ) : Fin n :=
    let min_d := (free.image (circ_dist x)).min' (Finset.Nonempty.image h _)
    let candidates := free.filter (fun j => circ_dist x j = min_d)
    candidates.min' (by
      have hmem := Finset.min'_mem (free.image (circ_dist x)) (Finset.Nonempty.image h _)
      rcases Finset.mem_image.mp hmem with ⟨j, hj, heq⟩
      exact ⟨j, Finset.mem_filter.mpr ⟨hj, heq⟩⟩)
  let step (free : Finset (Fin n)) (x : ℝ) : ℝ × Finset (Fin n) :=
    if h : free.Nonempty then
      let best := choose free h x
      (circ_dist x best, free.erase best)
    else
      (0, free)
  let cost_list := ((List.finRange n).foldl
    (fun (acc : List ℝ × Finset (Fin n)) (i : Fin n) =>
      let (c, free') := step acc.2 (x i)
      (acc.1 ++ [c], free'))
    ([], Finset.univ)).1
  fun i => cost_list.getD i.val 0
See it in the graphDiscuss this resultChallenge it