1.1. The sphere-packing problem and the Cohn–Elkies linear program
Sphere packing asks how densely congruent balls can fill Euclidean space.
Let d \ge 1. A sphere packing in \mathbb{R}^d is a set of balls of radius 1/2 whose
centers are pairwise separated by at least 1. Its upper density is the limit superior, as
r \to \infty, of the proportion of the ball B(0,r) covered by the packing. The maximal
sphere-packing density \Delta_d is the supremum of the upper densities of all sphere packings
in \mathbb{R}^d.
Lean code for Definition1.1.1●1 definition
Associated Lean declarations
-
SpherePackingConstant[complete]
-
SpherePackingConstant[complete]
-
defdefined in CohnElkies/Basic.leancomplete
def SpherePackingConstant (d : ℕ) : ENNReal
def SpherePackingConstant (d : ℕ) : ENNReal
The sphere-packing constant `Δ_d`: the supremum of the upper densities of all packings.
Throughout we use the following Fourier convention.
For f \in L^1(\mathbb{R}^d) the Fourier transform is
\widehat f(\xi) = \int_{\mathbb{R}^d} f(x)\,e^{-2\pi i x\cdot\xi}\,dx (equation (1) of the
report). With this normalisation the Gaussian e^{-\pi|x|^2} is its own Fourier transform,
\widehat{f(a\,\cdot)}(\xi) = a^{-d}\widehat f(\xi/a) for a > 0, the transform of a real even
function is real and even, Fourier inversion \widehat{\widehat f}(x) = f(-x) holds for Schwartz
functions and, almost everywhere, for f \in L^1 with \widehat f \in L^1, and the Fourier
transform of an integrable function is continuous and bounded.
Lean code for Definition1.1.2●1 theorem
Associated Lean declarations
-
Real.fourier_eq[complete]
-
Real.fourier_eq[complete]
-
theoremdefined in Mathlib/Analysis/Fourier/FourierTransform.leancomplete
theorem Real.fourier_eq.{u_1, u_3} {V : Type u_1} {E : Type u_3} [NormedAddCommGroup E] [NormedSpace ℂ E] [NormedAddCommGroup V] [InnerProductSpace ℝ V] [MeasurableSpace V] [BorelSpace V] [FiniteDimensional ℝ V] (f : V → E) (w : V) : FourierTransform.fourier f w = ∫ (v : V), Real.fourierChar (-inner ℝ v w) • f v
theorem Real.fourier_eq.{u_1, u_3} {V : Type u_1} {E : Type u_3} [NormedAddCommGroup E] [NormedSpace ℂ E] [NormedAddCommGroup V] [InnerProductSpace ℝ V] [MeasurableSpace V] [BorelSpace V] [FiniteDimensional ℝ V] (f : V → E) (w : V) : FourierTransform.fourier f w = ∫ (v : V), Real.fourierChar (-inner ℝ v w) • f v
The volume of the unit ball in \mathbb{R}^d is v_d = \pi^{d/2}/\Gamma(d/2+1) (equation (1)).
A ball of radius 1/2 has volume v_d/2^d.
Lean code for Definition1.1.3●1 definition
Associated Lean declarations
-
CohnElkies.unitBallVolume[complete]
-
CohnElkies.unitBallVolume[complete]
-
defdefined in CohnElkies/Basic.leancomplete
def CohnElkies.unitBallVolume (d : ℕ) : ℝ
def CohnElkies.unitBallVolume (d : ℕ) : ℝ
The volume `v_d = π^{d/2}/Γ(d/2+1)` of the unit ball in `ℝ^d`.
Write \mathcal{S}(\mathbb{R}^d;\mathbb{R}) for the real Schwartz space. The admissible class
is (equation (2))
\mathcal{A}_d = \{ f \in \mathcal{S}(\mathbb{R}^d;\mathbb{R}) :
\widehat f(0) > 0,\ \widehat f \ge 0 \text{ on } \mathbb{R}^d,
f \le 0 \text{ on } \{|x| \ge 1\} \},
with the Fourier transform of Definition 1.1.2. No radial symmetry is assumed;
\mathcal{A}_d^{\mathrm{rad}} denotes the subclass of radial functions.
Lean code for Definition1.1.4●1 definition
Associated Lean declarations
-
PackingBounds.FullAdmissible[complete]
-
PackingBounds.FullAdmissible[complete]
-
structuredefined in CohnElkies/Basic.leancomplete
structure PackingBounds.FullAdmissible (d : ℕ) : Type
structure PackingBounds.FullAdmissible (d : ℕ) : Type
The admissible class `𝒜_d` of the report, equation (2): real Schwartz functions `f` with `𝓕 f ≥ 0`, `𝓕 f (0) > 0` and `f ≤ 0` outside the unit ball (no radiality assumed).
Fields
function : CohnElkies.TestFunction d
The Schwartz function `f : ℝ^d → ℂ`.
real : ∀ (x : CohnElkies.Euclidean d), (self.function x).im = 0
`f` is real-valued.
fourier_real : ∀ (x : CohnElkies.Euclidean d), ((FourierTransform.fourier self.function) x).im = 0
`𝓕 f` is real-valued.
fourier_nonneg : ∀ (x : CohnElkies.Euclidean d), 0 ≤ ((FourierTransform.fourier self.function) x).re
`𝓕 f ≥ 0` on `ℝ^d`.
fourier_zero_pos : 0 < ((FourierTransform.fourier self.function) 0).re
`𝓕 f (0) > 0`.
outside_nonpos : ∀ (x : CohnElkies.Euclidean d), 1 ≤ ‖x‖ → (self.function x).re ≤ 0
`f ≤ 0` outside the open unit ball.
Every f \in \mathcal{A}_d (see Definition 1.1.4) satisfies
f(0) = \int_{\mathbb{R}^d} \widehat f(\xi)\,d\xi > 0.
Lean code for Lemma1.1.5●1 theorem
Associated Lean declarations
-
CohnElkies.admissible_zero_pos[complete]
-
CohnElkies.admissible_zero_pos[complete]
-
theoremdefined in CohnElkies/Basic.leancomplete
theorem CohnElkies.admissible_zero_pos {d : ℕ} (f : CohnElkies.Admissible d) : 0 < (f.function 0).re
theorem CohnElkies.admissible_zero_pos {d : ℕ} (f : CohnElkies.Admissible d) : 0 < (f.function 0).re
`f(0) > 0` for admissible `f ∈ 𝒜_d`, by Fourier inversion: `f(0) = ∫ 𝓕 f > 0`.
Fourier inversion for Schwartz functions (Definition 1.1.2) gives
f(0) = \int \widehat f. The integrand is continuous, nonnegative and strictly positive at
\xi = 0, so the integral is strictly positive.
The Cohn–Elkies linear-programming bound is (equation (3))
\mathrm{LP}_d = \dfrac{v_d}{2^d}\ \inf_{f \in \mathcal{A}_d} \dfrac{f(0)}{\widehat f(0)},
with v_d from Definition 1.1.3 and \mathcal{A}_d from
Definition 1.1.4. By Lemma 1.1.5 every quotient is
positive, and by Lemma 1.1.7 the infimum is taken over a nonempty set,
so \mathrm{LP}_d \in [0,\infty).
Lean code for Definition1.1.6●1 definition
Associated Lean declarations
-
PackingBounds.fullLinearProgram[complete]
-
PackingBounds.fullLinearProgram[complete]
-
defdefined in CohnElkies/Basic.leancomplete
def PackingBounds.fullLinearProgram (d : ℕ) : ℝ
def PackingBounds.fullLinearProgram (d : ℕ) : ℝ
The Cohn–Elkies linear programming bound `LP_d = (v_d/2^d) inf_{f ∈ 𝒜_d} f(0)/𝓕f(0)`, equation (3) of the report.
For every d \ge 1 the radial admissible class \mathcal{A}_d^{\mathrm{rad}}, and hence
\mathcal{A}_d (Definition 1.1.4), is nonempty: the autocorrelation
\varphi * \varphi of the flat bump \varphi(x) = \exp(-1/(1 - 4|x|^2)) for |x| < 1/2,
\varphi(x) = 0 otherwise, is admissible.
Lean code for Lemma1.1.7●1 theorem
Associated Lean declarations
-
CohnElkies.admissible_nonempty[complete]
-
CohnElkies.admissible_nonempty[complete]
-
theoremdefined in CohnElkies/Admissible/Nonempty.leancomplete
theorem CohnElkies.admissible_nonempty (d : ℕ) : Nonempty (CohnElkies.Admissible d)
theorem CohnElkies.admissible_nonempty (d : ℕ) : Nonempty (CohnElkies.Admissible d)
The bump CohnElkies.bump is smooth, real, radial, nonnegative and supported in the closed ball
of radius 1/2, with positive integral (CohnElkies.integral_bumpReal_pos). Its autocorrelation
CohnElkies.autocorrelation is again real and radial, and it vanishes for |x| \ge 1 because
the supports of \varphi and of \varphi(x - \cdot) are then disjoint
(CohnElkies.autocorrelation_eq_zero). Its Fourier transform is the square (\widehat\varphi)^2
(Definition 1.1.2, CohnElkies.fourier_autocorrelation_apply), which is real and
nonnegative because \widehat\varphi is real for the real radial function \varphi, and its
value at the origin is (\int\varphi)^2 > 0.
(Gorbachev; Cohn–Elkies.) For every d \ge 1 and every f \in \mathcal{A}_d, the packing
density of Definition 1.1.1 satisfies
\Delta_d \le \dfrac{v_d}{2^d}\,\dfrac{f(0)}{\widehat f(0)}.
Lean code for Theorem1.1.8●1 theorem
Associated Lean declarations
-
theoremdefined in CohnElkies/PackingBound.leancomplete
theorem PackingBounds.PackingBridge.sphere_packing_le_admissible {d : ℕ} (hd : 0 < d) (f : CohnElkies.Admissible d) : SpherePackingConstant d ≤ ENNReal.ofReal (CohnElkies.unitBallVolume d / 2 ^ d * CohnElkies.quotient f)
theorem PackingBounds.PackingBridge.sphere_packing_le_admissible {d : ℕ} (hd : 0 < d) (f : CohnElkies.Admissible d) : SpherePackingConstant d ≤ ENNReal.ofReal (CohnElkies.unitBallVolume d / 2 ^ d * CohnElkies.quotient f)
The Cohn–Elkies bound: each admissible `f ∈ 𝒜_d` bounds the sphere packing constant by `2^{-d} v_d · f(0)/𝓕f(0)`.
The proof occupies the next chapter. For a periodic packing, Poisson summation over its lattice
turns the sum of f over differences of centers into a spectral sum whose terms are
nonnegative and whose term at the origin already gives the bound
(Theorem 2.3.1); arbitrary packings are approximated by periodic ones
(Theorem 2.4.1), giving Theorem 2.4.2 in the form
\Delta_d \le \operatorname{vol}(B(0,1/2))\,f(0)/\widehat f(0). The volume of the half ball is
v_d/2^d (Definition 1.1.3).
For every d \ge 1 (equation (4)), \Delta_d \le \mathrm{LP}_d, with \mathrm{LP}_d as in
Definition 1.1.6.
Lean code for Theorem1.1.9●1 theorem
Associated Lean declarations
-
theoremdefined in CohnElkies/PackingBound.leancomplete
theorem PackingBounds.PackingBridge.sphere_packing_le_linear_program (d : ℕ) (hd : 0 < d) : SpherePackingConstant d ≤ ENNReal.ofReal (PackingBounds.fullLinearProgram d)
theorem PackingBounds.PackingBridge.sphere_packing_le_linear_program (d : ℕ) (hd : 0 < d) : SpherePackingConstant d ≤ ENNReal.ofReal (PackingBounds.fullLinearProgram d)
The Cohn–Elkies bound `Δ_d ≤ LP_d`, equation (4) of the report.
Take the infimum over f \in \mathcal{A}_d in Theorem 1.1.8; the radial
reduction Lemma 3.2.9 identifies the radial and the full program.
The first main theorem determines the exponential rate of the linear program, as conjectured by Afkhami-Jeddi, Cohn, Hartman, de Laat and Tajdini.
-
CohnElkies.sharpPackingRootAsymptotic[complete] -
PackingBounds.FullMain.exact_limit[complete]
As d \to \infty, \mathrm{LP}_d^{1/d} \longrightarrow \sqrt{e/(2\pi)}, where
\mathrm{LP}_d is defined in Definition 1.1.6.
Lean code for Theorem1.1.10●2 theorems
Associated Lean declarations
-
CohnElkies.sharpPackingRootAsymptotic[complete]
-
PackingBounds.FullMain.exact_limit[complete]
-
CohnElkies.sharpPackingRootAsymptotic[complete] -
PackingBounds.FullMain.exact_limit[complete]
-
theoremdefined in CohnElkies/Asymptotics/Main.leancomplete
theorem CohnElkies.sharpPackingRootAsymptotic : CohnElkies.SharpPackingRootAsymptotic
theorem CohnElkies.sharpPackingRootAsymptotic : CohnElkies.SharpPackingRootAsymptotic
`LP_d^{1/d} → √(e/(2π))`. -
theoremdefined in CohnElkies/PackingBound.leancomplete
theorem PackingBounds.FullMain.exact_limit : Filter.Tendsto (fun d ↦ PackingBounds.fullLinearProgram d ^ (↑d)⁻¹) Filter.atTop (nhds √(Real.exp 1 / (2 * Real.pi)))
theorem PackingBounds.FullMain.exact_limit : Filter.Tendsto (fun d ↦ PackingBounds.fullLinearProgram d ^ (↑d)⁻¹) Filter.atTop (nhds √(Real.exp 1 / (2 * Real.pi)))
Theorem 1.1 of the report: `LP_d^{1/d} → √(e / (2π))`.
-
CohnElkies.sharpLogAsymptotic[complete] -
CohnElkies.sharpBinaryLogAsymptotic[complete] -
CohnElkies.sharpQuotientAsymptotic[complete] -
CohnElkies.exists_manuscriptPackingIsLittleO[complete] -
CohnElkies.exists_manuscriptQuotientRootIsLittleO[complete]
Equivalently to Theorem 1.1.10: \log \mathrm{LP}_d/d \to \tfrac12\log(e/(2\pi)),
\log_2\mathrm{LP}_d/d \to -\tfrac12\log_2(2\pi/e), \mathrm{LP}_d = (\sqrt{e/(2\pi)} + o(1))^d,
\inf_{f\in\mathcal{A}_d}(f(0)/\widehat f(0))^{1/d}/\sqrt d \to 1/\pi, and
\inf_{f\in\mathcal{A}_d}(f(0)/\widehat f(0))^{1/d} = (1/\pi + o(1))\sqrt d.
Lean code for Theorem1.1.11●5 theorems
Associated Lean declarations
-
CohnElkies.sharpLogAsymptotic[complete]
-
CohnElkies.sharpBinaryLogAsymptotic[complete]
-
CohnElkies.sharpQuotientAsymptotic[complete]
-
CohnElkies.exists_manuscriptPackingIsLittleO[complete]
-
CohnElkies.exists_manuscriptQuotientRootIsLittleO[complete]
-
CohnElkies.sharpLogAsymptotic[complete] -
CohnElkies.sharpBinaryLogAsymptotic[complete] -
CohnElkies.sharpQuotientAsymptotic[complete] -
CohnElkies.exists_manuscriptPackingIsLittleO[complete] -
CohnElkies.exists_manuscriptQuotientRootIsLittleO[complete]
-
theoremdefined in CohnElkies/Asymptotics/Main.leancomplete
theorem CohnElkies.sharpLogAsymptotic : CohnElkies.SharpLogAsymptotic
theorem CohnElkies.sharpLogAsymptotic : CohnElkies.SharpLogAsymptotic
`log (LP_d)/d → (1/2) log (e/(2π))`.
-
theoremdefined in CohnElkies/Asymptotics/Main.leancomplete
theorem CohnElkies.sharpBinaryLogAsymptotic : CohnElkies.SharpBinaryLogAsymptotic
theorem CohnElkies.sharpBinaryLogAsymptotic : CohnElkies.SharpBinaryLogAsymptotic
`log₂ (LP_d)/d → -(1/2) log₂ (2π/e)`.
-
theoremdefined in CohnElkies/Asymptotics/Main.leancomplete
theorem CohnElkies.sharpQuotientAsymptotic : CohnElkies.SharpQuotientAsymptotic
theorem CohnElkies.sharpQuotientAsymptotic : CohnElkies.SharpQuotientAsymptotic
`inf_{f ∈ 𝒜_d} (f(0)/𝓕f(0))^{1/d} / √d → 1/π`. -
theoremdefined in CohnElkies/Asymptotics/Manuscript.leancomplete
theorem CohnElkies.exists_manuscriptPackingIsLittleO : ∃ e, (e =o[Filter.atTop] fun x ↦ 1) ∧ ∀ (d : ℕ), 0 < d → CohnElkies.LP d = (CohnElkies.criticalPackingBase + e d) ^ d
theorem CohnElkies.exists_manuscriptPackingIsLittleO : ∃ e, (e =o[Filter.atTop] fun x ↦ 1) ∧ ∀ (d : ℕ), 0 < d → CohnElkies.LP d = (CohnElkies.criticalPackingBase + e d) ^ d
Manuscript form of Theorem 1.1: `LP_d = (√(e/(2π)) + o(1))^d`.
-
theoremdefined in CohnElkies/Asymptotics/Manuscript.leancomplete
theorem CohnElkies.exists_manuscriptQuotientRootIsLittleO : ∃ e, (e =o[Filter.atTop] fun x ↦ 1) ∧ ∀ (d : ℕ), 0 < d → sInf (CohnElkies.manuscriptQuotientRootSet d) = (Real.pi⁻¹ + e d) * √↑d
theorem CohnElkies.exists_manuscriptQuotientRootIsLittleO : ∃ e, (e =o[Filter.atTop] fun x ↦ 1) ∧ ∀ (d : ℕ), 0 < d → sInf (CohnElkies.manuscriptQuotientRootSet d) = (Real.pi⁻¹ + e d) * √↑d
Manuscript form of Theorem 1.1: `inf {(f(0)/𝓕f(0))^{1/d}} = (1/π + o(1)) √d`.
\mathrm{LP}_d = (v_d/2^d)\inf_f f(0)/\widehat f(0) with (v_d/2^d)^{1/d}\sqrt d \to \sqrt{2\pi e}/2
(Lemma 3.1.8) and \sqrt{2\pi e}/(2\pi) = \sqrt{e/(2\pi)}; the
logarithmic forms follow by continuity of \log and \log_2 at the positive limit, and the
o(1) forms by taking d-th roots.
Lower bound. By Theorem 4.2.2 there is a sequence \epsilon_d \to 0 such that every
F \in \mathcal{A}_d satisfies
F(0)/\widehat F(0) \ge (2^d/v_d)\,(\sqrt{e/(2\pi)} - \epsilon_d)^d for all sufficiently large
d. Inserting this into Definition 1.1.6 gives
\mathrm{LP}_d \ge (\sqrt{e/(2\pi)} - \epsilon_d)^d, hence
\liminf_{d\to\infty} \mathrm{LP}_d^{1/d} \ge \sqrt{e/(2\pi)}.
Upper bound. By Theorem 5.5.6, for every small \epsilon > 0 and every large d
there is an admissible function of normalized cost at most R_{\epsilon,d}/\sqrt d, where
R_{\epsilon,d}/\sqrt d \to \alpha_\epsilon as d \to \infty and \alpha_\epsilon \to 1/\pi
as \epsilon \downarrow 0; together with Lemma 3.1.8 this gives
\limsup_{d\to\infty}\mathrm{LP}_d^{1/d} \le \sqrt{e/(2\pi)}. In the formalization the two
halves are not taken separately: the sandwich argument Theorem 7.6.1 combines the
uniform lower bound with the \epsilon-family of upper constructions and yields the limit
\inf_{f\in\mathcal{A}_d}(f(0)/\widehat f(0))^{1/d}/\sqrt d \to 1/\pi directly, from which
Stirling's formula gives the claim.
\Delta_d \le \mathrm{LP}_d = 2^{-(\alpha_* + o(1))d} as d \to \infty, where
\alpha_* = \tfrac12 \log_2(2\pi/e) = 0.6044\ldots; equivalently
\Delta_d \le (\sqrt{e/(2\pi)} + o(1))^d. This improves the Kabatianskii–Levenshtein
exponent 0.59905576\ldots, and the matching lower bound in Theorem 1.1.10 shows that no
Cohn–Elkies auxiliary function can improve this exponent.
Lean code for Theorem1.1.12●2 theorems
Associated Lean declarations
-
theoremdefined in CohnElkies/PackingBound.leancomplete
theorem PackingBounds.PackingBridge.sphere_packing_sharp_asymptotic_upper : ∃ e, (e =o[Filter.atTop] fun x ↦ 1) ∧ ∀ (d : ℕ), 0 < d → SpherePackingConstant d ≤ ENNReal.ofReal ((√(Real.exp 1 / (2 * Real.pi)) + e d) ^ d)
theorem PackingBounds.PackingBridge.sphere_packing_sharp_asymptotic_upper : ∃ e, (e =o[Filter.atTop] fun x ↦ 1) ∧ ∀ (d : ℕ), 0 < d → SpherePackingConstant d ≤ ENNReal.ofReal ((√(Real.exp 1 / (2 * Real.pi)) + e d) ^ d)
Sharp asymptotic upper bound: `Δ_d ≤ (√(e/(2π)) + o(1))^d`.
-
theoremdefined in CohnElkies/PackingBound.leancomplete
theorem PackingBounds.FullMain.exact_binary_exponent : Filter.Tendsto (fun d ↦ Real.logb 2 (PackingBounds.fullLinearProgram d) / ↑d) Filter.atTop (nhds (-(1 / 2) * Real.logb 2 (2 * Real.pi / Real.exp 1)))
theorem PackingBounds.FullMain.exact_binary_exponent : Filter.Tendsto (fun d ↦ Real.logb 2 (PackingBounds.fullLinearProgram d) / ↑d) Filter.atTop (nhds (-(1 / 2) * Real.logb 2 (2 * Real.pi / Real.exp 1)))
Theorem 1.1 in base-2 form: `log₂ LP_d / d → -½ log₂(2π/e) = -0.6044…`.
Combine Theorem 1.1.9 with Theorem 1.1.10 and
Theorem 1.1.11:
\mathrm{LP}_d = (\sqrt{e/(2\pi)} + o(1))^d = 2^{-(\frac12\log_2(2\pi/e) + o(1))d}.