Proposition 1 (used in the proofs of Theorems 2 and 10) — divergence increment
ProvedLinearHashingPoissonesque.ExpectedLoads.Supplement.divergence_incrementlinear-hashingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let and be real numbers, and write . Then
Both the integral identity and its lower bound are asserted. This estimate controls increments of the Poisson divergence in the maximum-load comparison and dense-threshold estimates.
Differences from the source:
- encoding: the chained integral identity and inequality → a conjunction of the identity with the interval-integral lower bound; reason: both source clauses are retained; continuity of log(x/mu) on the positive interval implies integrability
Preamble
import Definitions.Def_LinearHashingPoissonesque_ExpectedLoads_PoissonDivergence
Formal statement
namespace LinearHashingPoissonesque.ExpectedLoads.Supplement
/-- Proposition 1, p.8: both the integral identity and its lower bound. -/
theorem divergence_increment (mu s t : ℝ) (hmu : 0 < mu) (hs : 0 < s) (hst : s < t) :
poissonDivergence t mu - poissonDivergence s mu =
(∫ x in s..t, Real.log (x / mu)) ∧
(t - s) * Real.log (s / mu) ≤ (∫ x in s..t, Real.log (x / mu)) := by sorry
end LinearHashingPoissonesque.ExpectedLoads.Supplement
Source
Vinayak Kumar, STOC 2027 submission #1155 (October 2026), p.8, Proposition 1; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1155.pdf#page=8