Bit length of a list of rational (atom, mass) pairs
DefinitionLawLocalComp_Supplement_bitLenlaw-compressionmonotone-normsp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitystochastic-loads
For a finite list of pairs of rational numbers, its bit length is
the total number of bits needed to write all atoms and masses , where for in lowest terms and is the number of binary digits of .
It is the size of the description of a finite rational law given as a list of atoms with their probabilities.
Formalization Note is the published WeightedCongestionBR.bitLen (one sign bit plus the binary lengths of the numerator and the denominator).
Definition code
import Mathlib
import Definitions.Def_WeightedCongestionBR_bitLen
namespace LawLocalComp
namespace Supplement
/-- **The bit length of a list of rational (atom, mass) pairs.**
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; Theorem 6.2, p.10.
`bitLen ℓ = ∑_{(x, m) ∈ ℓ} (ℓ(x) + ℓ(m))`: the total binary length of all atoms and masses written
in the list, where `ℓ(q) = 1 + size|a| + size b` for `q = a/b` in lowest terms is the published
`WeightedCongestionBR.bitLen` (sign bit, numerator and denominator in binary). -/
def bitLen (l : List (ℚ × ℚ)) : ℕ :=
(l.map fun z => WeightedCongestionBR.bitLen z.1 + WeightedCongestionBR.bitLen z.2).sum
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; Theorem 6.2, p.10