The Cohn–Elkies exponent and sign uncertainty

2.4. From arbitrary to periodic packings🔗

Theorem2.4.1
Statement uses 2
Statement dependency previews
Preview
Definition 1.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 2
Reverse dependency previews
Preview
Theorem 1.1.8
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • 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
  • 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
Proof for Theorem 2.4.1
Proof uses 2
Proof dependency previews
Preview
Lemma 2.1.7
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

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

Theorem2.4.2
Statement uses 2
Statement dependency previews
Preview
Definition 1.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 1✓L∃∀N

(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
  • 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`. 
Proof for Theorem 2.4.2
Proof uses 3
Proof dependency previews
Preview
Lemma 2.1.7
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

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.