The optimal three-dimensional quadratic quantization constant
For $N \ge 1$ let $$q_N = \inf_{z_1, \dots, z_N \in [0,1]^3} \int_{[0,1]^3} \min_i |x - z_i|^2 \, dx.$$ Let $L_{\mathrm{BCC}} = 2^{1/3} \bigl( \mathbb{Z}^3 \cup (\mathbb{Z}^3 + (1/2, 1/2, 1/2)) \bigr)$, the body-centred cubic lattice with one point per unit volume, and let $V_{\mathrm{BCC}}$ be the Voronoi cell of its origin, a truncated octahedron. Gersho conjectured that the Voronoi cells of optimal quantizers are asymptotically congruent to a single space-tiling polytope (1979); in three dimensions the conjectured polytope is the truncated octahedron. Barnes and Sloane proved that the body-centred cubic lattice is the optimal lattice quantizer in three dimensions (1983). In the plane the corresponding statement, with the regular hexagon, is Fejes Tóth's theorem on sums of moments; Gruber gave the first complete proof (1999). Choksi and Lu proved a bound, independent of $N$, on the number of faces of the Voronoi cells of optimal configurations (2020). By Zador's theorem the limit $\lim_{N \to \infty} N^{2/3} q_N$ exists and is positive (1982).
Problem. Prove or disprove $$\lim_{N \to \infty} N^{2/3} q_N = \int_{V_{\mathrm{BCC}}} |x|^2 \, dx.$$ The left side optimizes over arbitrary point sets. This is the energy-constant version of the three-dimensional Gersho conjecture; congruence of the asymptotic cells is not required.
Source: Gersho (1979), as the asymptotic congruence of optimal quantizer cells; with the body-centred cubic lattice in three dimensions, Choksi and Lu (2020), Conjecture 1.1. Stated by AIM — Open Applied Problems as the energy-constant version.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, centroidal Voronoi tessellations, lattice quantizers, optimal quantization
References
@article{gersho1979,
author = {Gersho, Allen},
title = {Asymptotically optimal block quantization},
journal = {IEEE Trans. Inform. Theory},
volume = {25},
number = {4},
year = {1979},
pages = {373--380},
doi = {10.1109/TIT.1979.1056067},
}
@article{choksi2020,
author = {Choksi, Rustum and Lu, Xin Yang},
title = {Bounds on the geometric complexity of optimal centroidal {V}oronoi tesselations in {3D}},
journal = {Comm. Math. Phys.},
volume = {377},
number = {3},
year = {2020},
pages = {2429--2450},
doi = {10.1007/s00220-020-03789-y},
eprint = {1806.07591},
archivePrefix = {arXiv},
}
@article{gruber1999,
author = {Gruber, Peter M.},
title = {A short analytic proof of {F}ejes {T}{\'o}th's theorem on sums of moments},
journal = {Aequationes Math.},
volume = {58},
number = {3},
year = {1999},
pages = {291--295},
doi = {10.1007/s000100050116},
}
@article{barnes1983,
author = {Barnes, E. S. and Sloane, N. J. A.},
title = {The optimal lattice quantizer in three dimensions},
journal = {SIAM J. Algebraic Discrete Methods},
volume = {4},
number = {1},
year = {1983},
pages = {30--41},
doi = {10.1137/0604005},
}
@misc{aim-bcc-quantization,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The optimal three-dimensional quadratic quantization constant}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/085-bcc-quantization.md},
note = {Entry 085 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00576, "The optimal three-dimensional quadratic quantization constant", clopen.solutions.