2.4. From arbitrary to periodic packings
For every d \ge 1 the periodic packing constant of Definition 2.1.2
equals \Delta_d (Definition 1.1.1). More precisely, for every sphere packing
S of separation 1 and every b below the upper density of S there is a periodic
packing of separation 1 with upper density above b.
Lean code for Theorem2.4.1●2 theorems
Associated Lean declarations
-
theoremdefined in CohnElkies/SpherePacking/PeriodicApproximation.leancomplete
theorem periodic_packing_supremum_eq_unrestricted {d : ℕ} (hd : 0 < d) : PeriodicSpherePackingConstant d = SpherePackingConstant d
theorem periodic_packing_supremum_eq_unrestricted {d : ℕ} (hd : 0 < d) : PeriodicSpherePackingConstant d = SpherePackingConstant d
-
theoremdefined in CohnElkies/SpherePacking/PeriodicApproximation.leancomplete
theorem SpherePacking.exists_periodic_unit_packing_above_density_threshold {d : ℕ} (hd : 0 < d) (S : SpherePacking d) (hSsep : S.separation = 1) {b : ENNReal} (hb : b < S.upperPackingDensity) : ∃ P, P.separation = 1 ∧ b < P.upperPackingDensity
theorem SpherePacking.exists_periodic_unit_packing_above_density_threshold {d : ℕ} (hd : 0 < d) (S : SpherePacking d) (hSsep : S.separation = 1) {b : ENNReal} (hb : b < S.upperPackingDensity) : ∃ P, P.separation = 1 ∧ b < P.upperPackingDensity
Periodic packings are packings, so the periodic constant is at most \Delta_d; by
Lemma 2.1.7 it suffices to prove the second statement. Let X be
the centers of S. For L > 0 consider the cube C_L = [0,L)^d (axisAlignedCell), the
cubic lattice \Lambda_L = L\mathbb{Z}^d (axisCellLattice), whose translates of C_L tile
space, and the inset cube [1/2, L-1/2]^d (insetAxisAlignedCell). For a translate
g + C_L, g \in \Lambda_L, keep the centers x \in X \cap (g + C_L) whose ball
B(x,1/2) lies inside g + C_L, and repeat them \Lambda_L-periodically
(latticeReplicatedCenters): since the balls of the kept centers lie in one tile and the tiles
are disjoint, distinct replicated centers are still at distance at least 1, so this is a
periodic packing of separation 1 (replicateToPeriodicPacking). By
Lemma 2.1.8 its density is
|X_{\mathrm{kept}}|\operatorname{vol}(B(0,1/2))/L^d, and the discarded centers lie in the
boundary shell [-1/2, L+1/2]^d \setminus [1, L-1]^d (boundaryShell), whose volume is
(L+1)^d - (L-2)^d = o(L^d) (volume_boundaryShell, tendsto_volume_boundaryShell_div_cell).
Averaging over the translates g + C_L meeting a large ball B(0,R)
(lattice_count_mul_volume_cell_le_volume_ball) and using that the covered proportion of
B(0,R) exceeds b for arbitrarily large R, one finds L and g for which the kept
centers alone give density above b (exists_replicated_packing_density_eq).
(Cohn–Elkies linear programming bound.) 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
\Delta_d \le \dfrac{f(0)}{\widehat f(0)}\operatorname{vol}(B(0,1/2)),
with \Delta_d from Definition 1.1.1. No radiality is assumed.
Lean code for Theorem2.4.2●1 theorem
Associated Lean declarations
-
LinearProgrammingBound[complete]
-
LinearProgrammingBound[complete]
-
theoremdefined in CohnElkies/SpherePacking/CohnElkiesBound.leancomplete
theorem LinearProgrammingBound {d : ℕ} {f : SchwartzMap (EuclideanSpace ℝ (Fin d)) ℂ} (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) (hd : 0 < d) : SpherePackingConstant d ≤ ↑(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)) ℂ} (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) (hd : 0 < d) : SpherePackingConstant d ≤ ↑(f 0).re.toNNReal / ↑(FourierTransform.fourier (⇑f) 0).re.toNNReal * MeasureTheory.volume (Metric.ball 0 (1 / 2))
**The Cohn–Elkies linear programming bound**: if `f` is a nonzero real valued Schwartz function with real valued Fourier transform such that `f ≤ 0` outside the unit ball and `𝓕 f ≥ 0`, then the sphere packing constant of `ℝ^d` is at most `f 0 / 𝓕 f 0` times the volume of a ball of radius `1 / 2`.
By Theorem 2.4.1 and Lemma 2.1.7,
\Delta_d is the supremum of the upper densities of the periodic packings of separation 1,
so it suffices to bound each of them. A periodic packing without centers has density 0. For a
periodic packing P with centers, choose a \mathbb{Z}-basis of its lattice
(PeriodicSpherePacking.canonicalPackingLatticeBasis); its fundamental domain is bounded
(PeriodicSpherePacking.fundamental_region_admits_norm_bound) and its lattice translates tile
space (PeriodicSpherePacking.basis_region_translates_cover_uniquely), so
Theorem 2.3.1 applies to P and gives the bound.
The bridge from this statement to equation (4) of the report is short: for f \in \mathcal{A}_d
the hypotheses hold, \operatorname{vol}(B(0,1/2)) = v_d/2^d
(PackingBounds.PackingBridge.volume_half_ball), and taking the infimum over f gives
\Delta_d \le \mathrm{LP}_d (Theorem 1.1.9). Note that the formal packing
constant lives in [0,\infty], so these inequalities are stated with the real right-hand sides
coerced by ENNReal.ofReal; that \Delta_d \le 1 is SpherePacking.upper_packing_density_le_one
for every packing.