A deterministically selected quadratic-size prime field
ProvedStableMSR.Recovery.Supplement.OrderStream.field_size_specalgorithmsclusteringderandomization
Bertrand’s postulate gives a prime between the threshold and twice the threshold. The least such prime is the unique nonzero summand in the field-size definition.
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.field_size_spec (m : ℕ) : (fieldSize m).Prime ∧ 8193≤fieldSize m ∧ 4*m^2≤fieldSize m ∧ fieldSize m≤2*lower m := 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.