2.3. The bound for periodic packings
Let P be a periodic packing (Definition 2.1.1) of separation 1 with lattice
\Lambda, a nonempty set of centers X, and a bounded region D whose \Lambda-translates
tile \mathbb{R}^d (each point lies in exactly one translate). Let f be a nonzero complex
Schwartz function on \mathbb{R}^d that is real valued with real valued Fourier transform
(Definition 1.1.2), such that f(x) \le 0 for |x| \ge 1 and
\widehat f \ge 0. Then the upper density of P is at most
\dfrac{f(0)}{\widehat f(0)}\operatorname{vol}(B(0,1/2)).
Lean code for Theorem2.3.1●1 theorem
Associated Lean declarations
-
LinearProgrammingBound'[complete]
-
LinearProgrammingBound'[complete]
-
theoremdefined in CohnElkies/SpherePacking/CohnElkiesBound.leancomplete
theorem LinearProgrammingBound' {d : ℕ} {f : SchwartzMap (EuclideanSpace ℝ (Fin d)) ℂ} {P : PeriodicSpherePacking d} {D : Set (EuclideanSpace ℝ (Fin d))} [Nonempty ↑P.centers] (hne_zero : f ≠ 0) (hReal : ∀ (x : EuclideanSpace ℝ (Fin d)), ↑(f x).re = f x) (hRealFourier : ∀ (x : EuclideanSpace ℝ (Fin d)), ↑((FourierTransform.fourier f) x).re = (FourierTransform.fourier f) x) (hCohnElkies₁ : ∀ (x : EuclideanSpace ℝ (Fin d)), ‖x‖ ≥ 1 → (f x).re ≤ 0) (hCohnElkies₂ : ∀ (x : EuclideanSpace ℝ (Fin d)), ((FourierTransform.fourier f) x).re ≥ 0) (hP : P.separation = 1) (hD_isBounded : Bornology.IsBounded D) (hD_unique_covers : ∀ (x : EuclideanSpace ℝ (Fin d)), ∃! g, g +ᵥ x ∈ D) (hd : 0 < d) : P.upperPackingDensity ≤ ↑(f 0).re.toNNReal / ↑((FourierTransform.fourier f) 0).re.toNNReal * MeasureTheory.volume (Metric.ball 0 (1 / 2))
theorem LinearProgrammingBound' {d : ℕ} {f : SchwartzMap (EuclideanSpace ℝ (Fin d)) ℂ} {P : PeriodicSpherePacking d} {D : Set (EuclideanSpace ℝ (Fin d))} [Nonempty ↑P.centers] (hne_zero : f ≠ 0) (hReal : ∀ (x : EuclideanSpace ℝ (Fin d)), ↑(f x).re = f x) (hRealFourier : ∀ (x : EuclideanSpace ℝ (Fin d)), ↑((FourierTransform.fourier f) x).re = (FourierTransform.fourier f) x) (hCohnElkies₁ : ∀ (x : EuclideanSpace ℝ (Fin d)), ‖x‖ ≥ 1 → (f x).re ≤ 0) (hCohnElkies₂ : ∀ (x : EuclideanSpace ℝ (Fin d)), ((FourierTransform.fourier f) x).re ≥ 0) (hP : P.separation = 1) (hD_isBounded : Bornology.IsBounded D) (hD_unique_covers : ∀ (x : EuclideanSpace ℝ (Fin d)), ∃! g, g +ᵥ x ∈ D) (hd : 0 < d) : P.upperPackingDensity ≤ ↑(f 0).re.toNNReal / ↑((FourierTransform.fourier f) 0).re.toNNReal * MeasureTheory.volume (Metric.ball 0 (1 / 2))
The linear programming bound for a single periodic packing of separation `1`.
Let X_D = X \cap D be the N centers in the fundamental region. Since every center is
uniquely y + \lambda with y \in X_D and \lambda \in \Lambda
(SpherePacking.CohnElkies.fundamentalCentersLatticeProductEquiv), the double sum of f over
X \times X_D can be written as
\sum_{x \in X_D}\sum_{y \in X_D}\sum_{\lambda\in\Lambda} f(x - y + \lambda)
(SpherePacking.CohnElkies.center_double_sum_eq_region_lattice_sum). For x \ne y, or for
x = y and \lambda \ne 0, the point x - y + \lambda is a difference of distinct centers,
so it has norm at least 1 and f is nonpositive there; hence each inner lattice sum is at most
f(0) if x = y and at most 0 otherwise
(SpherePacking.CohnElkies.real_lattice_sum_bounded_by_origin_term), and the double sum is at
most N f(0) (packing_bound_auxiliary_estimate).
On the other hand, Poisson summation Theorem 2.2.1 applied to each
inner sum with v = x - y, followed by an exchange of the finite sums over x, y with the
absolutely convergent spectral sum (SpherePacking.CohnElkies.packing_spectral_sum_exchange),
identifies the double sum with
\dfrac{1}{\operatorname{covol}(\Lambda)}\sum_{m\in\Lambda^*}\widehat f(m)\,|S(m)|^2,
S(m) = \sum_{x\in X_D}e^{2\pi i\langle x,m\rangle},
(packing_bound_geometric_estimate). Every term is nonnegative because \widehat f \ge 0
(SpherePacking.CohnElkies.nonnegative_weighted_nonzero_frequency_sum), and the term m = 0
equals N^2\widehat f(0)/\operatorname{covol}(\Lambda) (packing_bound_spectral_estimate).
Combining the two estimates gives N/\operatorname{covol}(\Lambda) \le f(0)/\widehat f(0), and
the density formula Lemma 2.1.8 turns this into the claim.