Enumerating coefficient indices preserves the minwise fraction with multiplicity
ProvedStableMSR.Recovery.Supplement.OrderStream.polynomial_family_fractionalgorithmsclusteringderandomization
Base-q digits identify the coefficient indices bijectively with the coefficient vectors over the selected prime field. Each vector contributes one list entry. The proved polynomial minwise bound therefore applies directly to the actual fraction of output permutations.
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.polynomial_family_fraction (m : ℕ) : (family m).length=count m ∧ PermutationFamily m (family m) ∧
∀T : Finset ℕ,T⊆Finset.range m → T.Nonempty → ∀z∈T,
firstFraction (family m) T z ≤ 3/(2*(T.card:ℝ)) := 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.