Products, quotients and remainders are bounded-sum computations
ProvedStableMSR.Recovery.Compiler.BoundedSum.bounded_natural_arithmeticalgorithmsclusteringderandomization
Multiplication is bounded repeated addition. Division by a positive natural counts its positive multiples up to the dividend. The zero divisor and remainder follow the natural-number conventions.
Preamble
import Definitions.Def_StableMSR_BoundedSumRAM open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.Compiler.BoundedSum open Polynomial
Formal statement
theorem StableMSR.Recovery.Compiler.BoundedSum.bounded_natural_arithmetic : (∀ f g : Env→ℕ,Form f → Form g → Form (fun ρ=>f ρ*g ρ)) ∧
(∀ f g : Env→ℕ,Form f → Form g → Form (fun ρ=>f ρ/g ρ)) ∧
(∀ f g : Env→ℕ,Form f → Form g → Form (fun ρ=>f ρ%g ρ)) := 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.