betaFeedback

WorksMathematics

The BCC lattice is the optimal 3D lattice quantizer for all p≥1p\geq1

Abstract

For every finite p≥1p\ge1, the body-centered cubic lattice uniquely minimizes the ppth moment of the Voronoi cell among three-dimensional lattices of covolume one, up to orthogonal transformations. This proves the Graf–Luschgy conjecture for three-dimensional lattice quantizers (\cite{GL}).

Introduction

Following Bourne, Cagnetti and Roper [4 Eqs. (1.1)–(1.4)], let A=(t1∣t2∣t3)∈GL(3,R)A=(t_1\mid t_2\mid t_3)\in GL(3,\mathbb{R}) and write

Λ(A)=span⁡Z{t1,t2,t3}=AZ3,V(A)={x∈R3:∣x∣≤∣x−w∣ for every w∈Λ(A)}.\Lambda(A)=\operatorname{span}_{\mathbb{Z}}\{t_1,t_2,t_3\}=A\mathbb{Z}^3,\qquad V(A)=\{x\in\mathbb{R}^3:|x|\leq|x-w|\text{ for every }w\in\Lambda(A)\}.

The volume ∣V(A)∣=∣det⁡A∣|V(A)|=|\det A| is the covolume of Λ(A)\Lambda(A). For p≥1p\geq1 define the normalized Voronoi moment by

Ep(A)=∣V(A)∣−1−p/3∫V(A)∣x∣p dx.E_p(A)=|V(A)|^{-1-p/3}\int_{V(A)}|x|^p\,dx.

For c>0c>0, O∈O(3)O\in O(3) and U∈GL(3,Z)U\in GL(3,\mathbb{Z}), V(cOAU)=cOV(A)V(cOAU)=cOV(A), so

Ep(cOAU)=(c3∣V(A)∣)−1−p/3cp+3∫V(A)∣x∣p dx=Ep(A).(1)E_p(cOAU)=(c^3|V(A)|)^{-1-p/3}c^{p+3}\int_{V(A)}|x|^p\,dx=E_p(A). \tag*{(1)}

Taking c=∣V(A)∣−1/3c=|V(A)|^{-1/3} reduces the minimization to ∣V(A)∣=1|V(A)|=1.

Use the BCC basis of [4 Eq. (4.13)],

Abcc=(101/2011/2001/2),D3∗=Λ(Abcc).A_{\mathrm{bcc}}= \begin{pmatrix} 1 & 0 & 1/2\\ 0 & 1 & 1/2\\ 0 & 0 & 1/2 \end{pmatrix},\qquad D_3^*=\Lambda(A_{\mathrm{bcc}}).

Here ∣V(Abcc)∣=1/2|V(A_{\mathrm{bcc}})|=1/2. For a lattice L=Λ(A)L=\Lambda(A), write ∣L∣=∣V(A)∣|L|=|V(A)| and Ep(L)=Ep(A)E_p(L)=E_p(A). This value is independent of the choice of basis by (1). Set

LB=21/3D3∗=Λ(21/3Abcc),∣LB∣=1.L_{\mathrm{B}}=2^{1/3}D_3^*=\Lambda(2^{1/3}A_{\mathrm{bcc}}),\qquad|L_{\mathrm{B}}|=1.

Theorem 1.1. Let 1≤p<∞1\leq p<\infty. Among full-rank lattices L⊂R3L\subset\mathbb{R}^3 of covolume one,

min⁡∣L∣=1Ep(L)=Ep(LB)=Ep(Abcc),argmin⁡∣L∣=1Ep(L)={OLB:O∈O(3)}.(2)\min_{|L|=1}E_p(L)=E_p(L_{\mathrm{B}})=E_p(A_{\mathrm{bcc}}),\qquad\underset{|L|=1}{\operatorname{argmin}}E_p(L)=\{OL_{\mathrm{B}}:O\in O(3)\}. \tag*{(2)}

This resolves the Graf–Luschgy Conjecture [13 Conjecture 8.17]. The normalization of the sharp constant is

Ep(LB)=∫V(21/3Abcc)∣x∣p dx=21+p/3∫V(Abcc)∣x∣p dx.E_p(L_{\mathrm{B}})=\int_{V(2^{1/3}A_{\mathrm{bcc}})}|x|^p\,dx=2^{1+p/3}\int_{V(A_{\mathrm{bcc}})}|x|^p\,dx.

The fixed-square expression for this constant is given in (11).

Let XX be a nonempty finite set in a domain Ω\Omega of volume one. With the masses on XX free, the transport cost is

min⁡f:Ω→Xf measurable∫Ω∣x−f(x)∣p dx=∫Ωmin⁡w∈X∣x−w∣p dx=∫Ωdist⁡(x,X)p dx.\min_{\substack{f:\Omega\to X\\ f\ \mathrm{measurable}}}\int_{\Omega}|x-f(x)|^{p}\,dx=\int_{\Omega}\min_{w\in X}|x-w|^{p}\,dx=\int_{\Omega}\operatorname{dist}(x,X)^{p}\,dx.

A nearest-site map attains the minimum [4 Lemma 2.2]. On the unit cube in Rd\mathbb{R}^{d}, the asymptotic quantization theorem gives [22, 5]

lim⁡N→∞Np/dinf⁡X⊂[0,1]d#X=N∫[0,1]dmin⁡w∈X∣x−w∣p dx∈(0,∞).\lim_{N\to\infty}N^{p/d}\inf_{\substack{X\subset[0,1]^{d}\\ \#X=N}}\int_{[0,1]^{d}}\min_{w\in X}|x-w|^{p}\,dx\in(0,\infty).

Gruber extended this asymptotic theory to Riemannian manifolds and normed spaces [15]. For a bounded open Ω⊂R3\Omega\subset\mathbb{R}^{3} of volume one with ∂Ω=φ(K)\partial\Omega=\varphi(K), where K⊂R2K\subset\mathbb{R}^{2} is compact and φ:R2→R3\varphi:\mathbb{R}^{2}\to\mathbb{R}^{3} is Lipschitz, Bourne, Cagnetti and Roper [4 Theorem A.1] prove the pointwise limit

lim⁡ε↓0ε−p∣V(A)∣−p/3∫Ωdist⁡(x,Λ(εA)∩Ω)p dx=Ep(A).\lim_{\varepsilon\downarrow0}\varepsilon^{-p}|V(A)|^{-p/3}\int_{\Omega}\operatorname{dist}(x,\Lambda(\varepsilon A)\cap\Omega)^{p}\,dx=E_{p}(A).

The same theorem gives Γ\Gamma-convergence of the rescaled distortion on GL(3,R)GL(3,\mathbb{R}) with the Frobenius metric.

In dimension two the moment theorem of Fejes Tóth yields triangular-lattice optimality for every finite p≥1p\ge1. The regular hexagon also gives the unrestricted planar asymptotic constant [11, 14]. See [4, Sect. 2]. In dimension three the unrestricted problem is the setting of Gersho’s conjecture. It concerns the asymptotic cell geometry of unconstrained optimal point sets [12]. For a precise quadratic formulation see Choksi and Lu [7 Conjecture 1.1]. Du and Wang obtained numerical evidence for the BCC cell in the three-dimensional quadratic problem [10]. For the high-rate variable-rate problem on periodic tilings, Sloane and Vaishampayan computed the asymptotic constant in terms of the cell volumes and second moments. In their comparison, the BCC constant is smaller than that of the A15 quantizer [21]. For quadratic quantization, Aydın and Iacobelli establish asymptotic local optimality of BCC under small periodic perturbations [1], while Luo and Xie obtain nonlinear stability estimates uniform over finite-index periods [18].

Among three-dimensional lattices, Barnes and Sloane proved BCC optimality for p=2p=2 [3], and Bambah proved it for the covering radius at fixed covolume [2]. The latter is the limiting problem

lim⁡p→∞Ep(A)1/p=∣V(A)∣−1/3max⁡x∈V(A)∣x∣.\lim_{p\to\infty}E_{p}(A)^{1/p}=|V(A)|^{-1/3}\max_{x\in V(A)}|x|.

Graf and Luschgy asked whether the same lattice minimizes every finite pp-th moment [13 Conjecture 8.17]. Bourne, Cagnetti and Roper proved strict local optimality in lattice shape for every finite p≥1p\ge1 and global optimality near p=2p=2 [4 Theorems 1.2–1.3]. They also found a local branch of body-centered tetragonal critical points issuing from the face-centered cubic lattice at p=2p=2 [4 Theorem 1.5]. Theorem 1.1 gives the global minimizer in the Bravais-lattice class for the entire finite exponent range.

The regular truncated octahedron, the Voronoi cell of BCC, also minimizes surface area among three-dimensional parallelohedra of fixed volume [6, 16]. The proof by Hales and Song uses an exact Bernstein certificate for the final polynomial inequality [16 Appendix A]. Outline of the proof.

  1. Voronoi moments on a fixed square. Section 2 writes the Voronoi cell in Selling coordinates and subdivides one facet from each opposite pair. Radial integration over the fifteen tile pyramids and their opposites gives

Ep(A)=14(p+3)(det⁡Q)1+p/6∑T∈TWT∫[−1,1]2qTp/2 dx dy.E_{p}(A)=\frac{1}{4(p+3)(\det Q)^{1+p/6}}\sum_{T\in\mathcal{T}}W_{T}\int_{[-1,1]^{2}}q_{T}^{p/2}\,dx\,dy.

Here QQ is the Gram matrix of a Selling basis, qTq_T is the squared radius on tile TT, and WTW_T is its weight. At ρij=1\rho_{ij}=1 the fifteen quadratics take only two forms. The BCC equality case is determined by

0<det⁡Q≤16(∑0≤i<j≤3ρij6)30 < \det Q \le16\left(\frac{\sum_{0\le i<j\le3}\rho_{ij}}{6}\right)^3

equality ⟺\Longleftrightarrow ρ01=ρ02=ρ03=ρ12=ρ13=ρ23\rho_{01}=\rho_{02}=\rho_{03}=\rho_{12}=\rho_{13}=\rho_{23}.

(2) Polynomial comparison for 1≤p≤351\le p\le35. Section 3 bounds the p/2p/2 power of the scaled ratio of qTq_T to its BCC value. The lower polynomials are Taylor polynomials of degrees four and three for p∈[1,2]p\in[1,2] and p∈[2,4]p\in[2,4], and weighted tangents of degrees two and three for p∈[4,6]p\in[4,6] and p∈[6,35]p\in[6,35], respectively. Bounds on the determinant factors then give polynomials in the conorms. For each of the thirty edge orders up to relabelling, the substitution

ρσ(i)=Xi+⋯+X5,X0,…,X5≥0,0≤i≤5\rho_{\sigma(i)}=X_i+\cdots+X_5,\qquad X_0,\ldots,X_5\ge0,\qquad0\le i\le5

reduces the comparison to coefficientwise nonnegativity. Numerical Lemmas 5.1–5.4 give these inequalities by exact interval arithmetic.

(3) Linear comparison for p≥35p\ge35. Section 4 uses the tangent sp/2≥1+p2(s−1)s^{p/2}\ge1+\frac{p}{2}(s-1) and reduces each coefficient to a linear combination of six weighted reference integrals. Numerical Lemma 5.6 gives nonnegativity on [35,1028][35,1028]. For p≥1026p\ge1026, the signs follow from estimates at the maximizing corners of the two reference quadratics. In both comparisons, the determinant bounds give Ep(A)>Ep(Abcc)E_p(A)>E_p(A_{\mathrm{bcc}}) when the conorms are unequal. Equal conorms and ∣V(A)∣=1|V(A)|=1 give the orbit in (1.2).

(4) Exact numerical bounds. Section 5 gives the rational computations for both comparisons. For bounded exponents, Numerical Lemmas 5.1–5.4 give coefficient bounds and counts. Numerical Lemma 5.5 computes the degree-ten coefficient pairs by finite differences. Numerical Lemma 5.6 bounds the corresponding weighted integrals by Bernstein coefficients.

Selling coordinates and the Voronoi moment

We obtain the fifteen fixed-square integrals in (9) by subdividing the facets of the zonotope (4) and integrating along rays. The BCC quadratics are given by (10). The determinant bound (14) identifies the equality case, and (18) gives the nonnegative variables for the two comparisons.

We use Selling’s reduction [20] in the obtuse-superbase form of Conway and Sloane [9 Theorem 8].

References

  1. [1]Aydın, A. D., Iacobelli, M.: Local crystallization in three-dimensional quantization. arXiv:2610.28547v1 (2026).arxiv.org/abs/2610.28547
  2. [2]Bambah, R. P.: On lattice coverings by spheres. Proc. Nat. Inst. Sci. India 20, 25–52 (1954).
  3. [3]Barnes, E. S., Sloane, N. J. A.: The optimal lattice quantizer in three dimensions. SIAM J. Algebraic Discrete Methods 4, 30–41 (1983).
  4. [4]Bourne, D. P., Cagnetti, F., Roper, S. M.: Optimality of the BCC lattice among 3D lattice quantizers. arXiv:2610.39705v1 (2026).arxiv.org/abs/2610.39705
  5. [5]Bucklew, J. A., Wise, G. L.: Multidimensional asymptotic quantization theory with rth power distortion measures. IEEE Trans. Inform. Theory 28, 239–247 (1982).
  6. [6]Cesaroni, A., Novaga, M.: The truncated octahedron minimizes surface area among parallelohedra of equal volume. arXiv:2609.02384v2 (2026).arxiv.org/abs/2609.02384
  7. [7]Choksi, R., Lu, X. Y.: Bounds on the geometric complexity of optimal centroidal Voronoi tessellations in 3D. Comm. Math. Phys. 377, 2429–2450 (2020).arxiv.org/abs/1806.07591
  8. [8]Conway, J. H., Sloane, N. J. A.: Voronoi regions of lattices, second moments of polytopes, and quantization. IEEE Trans. Inform. Theory 28, 211–226 (1982).
  9. [9]Conway, J. H., Sloane, N. J. A.: Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices. Proc. Roy. Soc. London Ser. A 436, 55–68 (1992).DOI
  10. [10]Du, Q., Wang, D. S.: The optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three-dimensional space. Comput. Math. Appl. 49, 1355–1373 (2005).DOI
  11. [11]Fejes Tóth, L.: Lagerungen in der Ebene, auf der Kugel und im Raum, 2nd edn. Grundlehren Math. Wiss., vol. 65. Springer (1972).
  12. [12]Gersho, A.: Asymptotically optimal block quantization. IEEE Trans. Inform. Theory 25, 373–380 (1979).DOI
  13. [13]Graf, S., Luschgy, H.: Foundations of quantization for probability distributions. Lecture Notes in Mathematics, vol. 1730. Springer (2000).DOI
  14. [14]Gruber, P. M.: A short analytic proof of Fejes Tóth’s theorem on sums of moments. Aequationes Math. 58, 291–295 (1999).DOI
  15. [15]Gruber, P. M.: Optimum quantization and its applications. Adv. Math. 186, 456–497 (2004).DOI
  16. [16]Hales, T., Song, L.: The truncated octahedral conjecture. arXiv:2609.00997v2 (2026).arxiv.org/abs/2609.00997
  17. [17]Lasserre, J. B.: Integration on a convex polytope. Proc. Amer. Math. Soc. 126, 2433–2441 (1998).DOI
  18. [18]Luo, S., Xie, B.: On sharp stability of the BCC quantizer. arXiv:2610.26553v1 (2026).arxiv.org/abs/2610.26553
  19. [19]Schymura, M., Seidel, I., Weltge, S.: Lifts for Voronoi cells of lattices. Discrete Comput. Geom. 70, 845–865 (2023).arxiv.org/abs/2106.04432
  20. [20]Selling, E.: Ueber die binären und ternären quadratischen Formen. J. Reine Angew. Math. 77, 143–229 (1874).DOI
  21. [21]Sloane, N. J. A., Vaishampayan, V. A.: A Zador-like formula for quantizers based on periodic tilings. IEEE Trans. Inform. Theory 48, 3138–3140 (2002).DOI
  22. [22]Zador, P. L.: Asymptotic quantization error of continuous signals and the quantization dimension. IEEE Trans. Inform. Theory 28, 139–149 (1982).DOI

Paper details

vlnc:W_ry8wby6z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI

View statement
Looking for related papers…
Contents