Lemma 2.15 — The complete finite-grid ball overlap inequality
OpenAMRangeAvoid.Characterization.Supplement.lemma_2_15complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
Let , let be an integer with , and put and . For with , let . Then
The bound retains the exact constant and exponent and applies to every admissible radius and integer translation, including the boundary .
Differences from the source:
- encoding: integer Euclidean balls in positive dimension → finite sets of vectors on Fin n defined by exact sums of squared coordinates; reason: this is the same closed Euclidean ball, with the positive-dimension convention inherited from Lemma 2.14
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Grid import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement
theorem lemma_2_15 (n : ℕ) (hn : 1 ≤ n) (R : ℕ)
(hR : Real.sqrt n / 2 < (R : ℝ)) (w : Fin n → ℤ)
(hw : ‖integerEuclidean w‖ ≤ 2 * ((R : ℝ) - Real.sqrt n / 2)) :
((gridLens R w).card : ℝ) / (gridBall n R).card ≥
(1 / Real.sqrt (2 * Real.pi * n)) *
(((R : ℝ) - Real.sqrt n / 2) / ((R : ℝ) + Real.sqrt n / 2)) ^ n *
Real.rpow (1 - ‖integerEuclidean w‖ ^ 2 /
(4 * ((R : ℝ) - Real.sqrt n / 2) ^ 2)) (((n : ℝ) + 1) / 2) := by sorry
end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Lemma 2.15, printed p.13 (PDF p.15); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf