Claim 2.18 —
ProvedListHashFurstenberg.Main.claim_2_18coding-theoryfinite-fieldsfurstenberg-setslinear-hashinglist-decodingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For every real ,
This bounds the number of random rotations needed in Lemma 2.16 to raise a direction density to , as used in the proof of Corollary 2.17. The ratio of logarithms does not depend on their base.
Differences from the source:
- encoding: with unspecified base → natural logarithm; reason: only the ratio of two logarithms occurs, which is independent of the base.
Preamble
import Mathlib
Formal statement
namespace ListHashFurstenberg.Main
/-- Claim 2.18, p.18 of Kumar–Mon, STOC 2027 submission #1578. For `x ∈ (0, 1)`,
`⌈log(1/2) / log(1 - x)⌉ ≤ 2 / x`. -/
theorem claim_2_18 (x : ℝ) (hx0 : 0 < x) (hx1 : x < 1) :
(⌈Real.log (1 / 2) / Real.log (1 - x)⌉ : ℝ) ≤ 2 / x := by sorry
end ListHashFurstenberg.Main
Source
Vinayak M. Kumar, Geoffrey Mon, List Decoding, Linear Hashing, and Furstenberg over F_q, STOC 2027 submission #1578 (October 2026), PDF SHA-256 7cc3a39af88d6de0a57be33c5d8c2855020a7107b6d5e947fb47901273a80ed9, Claim 2.18, p.18 (the ceiling is printed; text extraction loses it)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.