cycle_greedy_costs
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