Proposition 2 (used in the proof of Theorem 10) — dense threshold estimates
ProvedLinearHashingPoissonesque.ExpectedLoads.Supplement.dense_threshold_estimateslinear-hashingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be real and be integers. Set and assume . Both dense-regime estimates hold:
The constants outside the first square root and inside the second square root are distinct and exact. These estimates support Theorem 10, and apply to arbitrary positive , without a power-of-two restriction.
Differences from the source:
- encoding: Definition 1 real Poisson thresholds → published upperThreshold and lowerThreshold, using their root sets and exact zero branch; reason: on positive real m and 1 ≤ r ≤ n the nonzero root sets are singletons; no rounding or extra hypothesis is imposed
- encoding: the two threshold inequalities with mu=m/n → a conjunction with mu substituted and n,r natural; reason: 1 ≤ r ≤ n implies n ≥ 1; m remains real and no power-of-two constraint is imposed
Preamble
import Definitions.Def_LinearHashingPoissonesque_ExpectedLoads_PoissonThresholds
Formal statement
namespace LinearHashingPoissonesque.ExpectedLoads.Supplement
/-- Proposition 2, p.19: arbitrary positive real m and arbitrary 1 ≤ r ≤ n. -/
theorem dense_threshold_estimates (m : ℝ) (n r : ℕ) (hm : 0 < m)
(hr : 1 ≤ r) (hrn : r ≤ n) (hdense : Real.log ((n : ℝ) / r) ≤ m / n) :
upperThreshold m n r ≤ m / n + 2 * Real.sqrt (m / n * Real.log ((n : ℝ) / r)) ∧
m / n - Real.sqrt (2 * (m / n) * Real.log ((n : ℝ) / r)) ≤
lowerThreshold m n r := by sorry
end LinearHashingPoissonesque.ExpectedLoads.Supplement
Source
Vinayak Kumar, STOC 2027 submission #1155 (October 2026), p.19, Proposition 2; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1155.pdf#page=19