A finite law with a description of at most bits
DefinitionLawLocalComp_Supplement_HasBitslaw-compressionmonotone-normsp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitystochastic-loads
Let be a finite nonnegative law and a natural number. has a description of at most bits if there is a list of rational (atom, mass) pairs that represents (every entry is nonnegative and, for every , is the sum of the masses listed at atom ) and whose bit length is at most .
In particular such an is rational. This is the notion in which the witness laws of Theorems 6.1 and 6.2 have "polynomial description" and in which the probe laws of Theorem 6.2 have polynomial "scalar encodings".
Formalization Note The representation predicate is the base mission's published IsListRep; repeated atoms in the list are allowed.
Definition code
import Mathlib
import Definitions.Def_LawLocalComp_IsListRep
import Definitions.Def_LawLocalComp_Supplement_bitLen
namespace LawLocalComp
namespace Supplement
/-- **A law with a description of at most `B` bits.**
Mahboub–Rahgoshay, *Optimal Law-Local Compression for Stochastic Loads*, STOC 2027
submission manuscript of Oct. 29, 2026 (sha256 5f71501c…aa873), Theorem 6.1, p.9 ("witness description is polynomial in 1/ε, log N and accuracy bits");
Theorem 6.2, p.10 ("Law/probe bits are polynomial, not necessarily expanded copy lists", p.12).
`HasBits X B`: some list of rational (atom, mass) pairs represents `X` (in the sense of the
published `IsListRep`) and has total bit length at most `B`. In particular `X` is rational. -/
def HasBits (X : Law) (B : ℕ) : Prop := ∃ l : List (ℚ × ℚ), IsListRep l X ∧ bitLen l ≤ B
end Supplement
end LawLocalComp
Source
Mahboub–Rahgoshay, Optimal Law-Local Compression for Stochastic Loads, STOC 2027 submission (manuscript of Oct. 29, 2026, sha256 5f71501c…aa873), Theorem 6.1, p.9 ("witness description is polynomial in 1/ε, log N and accuracy bits"); Theorem 6.2, p.10; proof of Theorem 6.2, p.12 ("Law/probe bits are polynomial")