The Cohn–Elkies exponent and sign uncertainty

2.3. The bound for periodic packings🔗

Theorem2.3.1
Statement uses 2
Statement dependency previews
Preview
Definition 1.1.2
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

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

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.