Hash-order output entries have bounded-sum expressions
ProvedStableMSR.Recovery.Supplement.OrderStream.hash_order_stream_is_boundedalgorithmsclusteringderandomization
Use bounded divisor tests for primality, fixed powers for coefficient extraction and polynomial evaluation, and counts of smaller keys to compute ranks. Address arithmetic supplies the length fields and entries of the serialized output.
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.hash_order_stream_is_bounded : Form (fun ρ=>span (ρ 0)) ∧ Form (fun ρ=>word (ρ 0) (ρ 1)) := 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.