The Cohn–Elkies exponent and sign uncertainty

1.1. The sphere-packing problem and the Cohn–Elkies linear program🔗

Sphere packing asks how densely congruent balls can fill Euclidean space.

Definition1.1.1
uses 0
Used by 5
Reverse dependency previews
Preview
Theorem 1.1.8
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • defdefined in CohnElkies/Basic.lean
    complete
    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.

Definition1.1.2
uses 0
Used by 16
Reverse dependency previews
Preview
Definition 1.1.4
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • 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
Definition1.1.3
uses 0
Used by 5
Reverse dependency previews
Preview
Definition 1.1.6
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • defdefined in CohnElkies/Basic.lean
    complete
    def CohnElkies.unitBallVolume (d : ℕ) : ℝ
    def CohnElkies.unitBallVolume (d : ℕ) : ℝ
    The volume `v_d = π^{d/2}/Γ(d/2+1)` of the unit ball in `ℝ^d`. 
Definition1.1.4
uses 1
Used by 7
Reverse dependency previews
Preview
Lemma 1.1.5
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • structure(6 fields)defined in CohnElkies/Basic.lean
    complete
    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). 
    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. 
Lemma1.1.5
uses 1
Used by 2
Reverse dependency previews
Preview
Definition 1.1.6
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • theoremdefined in CohnElkies/Basic.lean
    complete
    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`. 
Proof for Lemma 1.1.5

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.

Definition1.1.6
Statement uses 4
Statement dependency previews
Preview
Definition 1.1.3
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 6
Reverse dependency previews
Preview
Theorem 1.1.9
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • defdefined in CohnElkies/Basic.lean
    complete
    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. 
Lemma1.1.7
uses 1
Used by 2
Reverse dependency previews
Preview
Definition 1.1.6
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • complete
    theorem CohnElkies.admissible_nonempty (d : ℕ) :
      Nonempty (CohnElkies.Admissible d)
    theorem CohnElkies.admissible_nonempty (d : ℕ) :
      Nonempty (CohnElkies.Admissible d)
Proof for Lemma 1.1.7

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.

Theorem1.1.8
uses 1used by 1✓L∃∀N

(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
  • theoremdefined in CohnElkies/PackingBound.lean
    complete
    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)`. 
Proof for Theorem 1.1.8
Proof uses 4
Proof dependency previews
Preview
Definition 1.1.3
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

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).

Theorem1.1.9
uses 1used by 1✓L∃∀N

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
  • theoremdefined in CohnElkies/PackingBound.lean
    complete
    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. 
Proof for Theorem 1.1.9
Proof uses 2
Proof dependency previews
Preview
Theorem 1.1.8
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

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.

Theorem1.1.10
uses 1
Used by 2
Reverse dependency previews
Preview
Theorem 1.1.11
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • complete
    theorem CohnElkies.sharpPackingRootAsymptotic :
      CohnElkies.SharpPackingRootAsymptotic
    theorem CohnElkies.sharpPackingRootAsymptotic :
      CohnElkies.SharpPackingRootAsymptotic
    `LP_d^{1/d} → √(e/(2π))`. 
  • theoremdefined in CohnElkies/PackingBound.lean
    complete
    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π))`. 
Theorem1.1.11
uses 1used by 1✓L∃∀N

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
  • complete
    theorem CohnElkies.sharpLogAsymptotic : CohnElkies.SharpLogAsymptotic
    theorem CohnElkies.sharpLogAsymptotic :
      CohnElkies.SharpLogAsymptotic
    `log (LP_d)/d → (1/2) log (e/(2π))`. 
  • complete
    theorem CohnElkies.sharpBinaryLogAsymptotic :
      CohnElkies.SharpBinaryLogAsymptotic
    theorem CohnElkies.sharpBinaryLogAsymptotic :
      CohnElkies.SharpBinaryLogAsymptotic
    `log₂ (LP_d)/d → -(1/2) log₂ (2π/e)`. 
  • complete
    theorem CohnElkies.sharpQuotientAsymptotic : CohnElkies.SharpQuotientAsymptotic
    theorem CohnElkies.sharpQuotientAsymptotic :
      CohnElkies.SharpQuotientAsymptotic
    `inf_{f ∈ 𝒜_d} (f(0)/𝓕f(0))^{1/d} / √d → 1/π`. 
  • complete
    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`. 
  • complete
    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`. 
Proof for Theorem 1.1.11

\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.

Proof for Theorem 1.1.10
Proof uses 5
Proof dependency previews
Preview
Definition 1.1.6
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

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.

Theorem1.1.12
uses 1used by 0✓L∃∀N

\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
  • theoremdefined in CohnElkies/PackingBound.lean
    complete
    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.lean
    complete
    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…`. 
Proof for Theorem 1.1.12
Proof uses 3
Proof dependency previews
Preview
Theorem 1.1.9
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

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}.