Ranking distinct hash keys gives the advertised permutation and order
ProvedStableMSR.Recovery.Supplement.OrderStream.rank_order_is_permutationalgorithmsclusteringderandomization
Keys consist of a hash value followed by the original vertex index. Their strict ranks give a bijection with the first m naturals. The rank readback is its inverse, so list positions compare exactly as the keys do.
Preamble
import Definitions.Def_StableMSR_PolynomialOrderStream open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.Compiler.BoundedSum open Polynomial open StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.OrderStream
Formal statement
theorem StableMSR.Recovery.Supplement.OrderStream.rank_order_is_permutation (m c : ℕ) : (row m c).Perm ((List.range m).map (fun i=>(i:ℤ))) ∧
∀ x < m, ∀ y < m, (row m c).idxOf (x:ℤ) < (row m c).idxOf (y:ℤ) ↔ score m c x < score m c y := by
sorry
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix B, Theorem B.2. Charged deterministic RAM implementation.