On the number of defects in optimal quantizers on closed surfaces: the hexagonal torus

Jack Edward Tisdell †, Rustum Choksi †, Xin Yang Lu ‡ · 2025

Read On the number of defects in optimal quantizers on closed surfaces: the hexagonal torus by Jack Edward Tisdell †, Rustum Choksi †, Xin Yang Lu ‡ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22680.txt.

Introduction

Jack Edward Tisdell, Rustum Choksi, and Xin Yang Lu count flaws in optimal point patterns on a torus in a 2025 mathematics paper. Quantization scatters n points over a surface to represent it faithfully; the best local pattern is hexagonal, and every non-hexagonal cell is a defect. On closed surfaces defects cannot vanish entirely, so the question is how fast they must grow. The authors build a proof strategy from error bounds and special integers tied to hexagonal lattice constructions.

On the hexagonal torus they prove defects grow no faster than the fourth root of n, fewer than on surfaces with edges. They conjecture the true rate is merely logarithmic. Pattern flaws on curved worlds echo through materials and graphics alike.

Catalog record

CREATORJack Edward Tisdell †, Rustum Choksi †, Xin Yang Lu ‡
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-22680

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the number of defects in optimal quantizers on closed surfaces: the hexagonal torus Jack Edward Tisdell †, Rustum Choksi †, Xin Yang Lu ‡ Abstract . We present a strategy for proving an asymptotic upper bound on the number of defects (non-hexagonal Voronoi cells) in the n n generator optimal quantizer on a closed surface (i.e., compact 2-manifold without boundary). The program is based upon a general lower bound on the optimal quantization error and related upper bounds for the Löschian numbers n n (the norms of the Eisenstein integers) based upon the Goldberg-Coxeter construction. A gap lemma is used to reduce the asymptotics of the number of defects to precisely the asymptotics for the gaps between Löschian numbers. We apply this strategy on the hexagonal torus and prove that the number of defects is at most O ⁡ ( n 1 / 4 ) O(n^{1/4}) —strictly fewer than surfaces with boundary—and conjecture (based upon the number-theoretic Löschian gap conjecture) that it is in fact O ⁡ ( log ⁡ n ) O(\log n) . Incidentally, the method also yields a related upper bound on the variance of the areas of the Voronoi cells. We show further that the bound on the number of defects holds in a neighborhood of the optimizers. Finally, we remark on the remaining issues for implementation on the 2-sphere. 1. Introduction Finding the optimal way to quantize a continuous distribution over a domain or manifold into a fixed number of points falls under the broad class of problems referred to as Optimal Quantization . These types of problems tend to be highly non-local and are related to the crystallization conjecture in mathematical physics ( [ 3 , 4 ] ). Our interest here entails the minimization of energy functionals (quantization errors) which exhibit a type of semi-locality as they can be defined in terms of the “neighborhoods” of each point, for some suitable notion of “neighborhood”. A natural approach along these lines is to take as the total energy the sum of individual energies of the Voronoi cells of each point in the tessellation they generate. Indeed, this is precisely what one obtains whenever one defines an energy density (whose integral is the energy) that depends only on the nearest point—an obvious attempt toward semi-locality. To this end, we investigate for each n , the variational problem (1) \text{minimize }\mathcal{E}(Y)=\int_{\mathcal{M}}\min_{y\in Y}\varrho_{\mathcal{M}}(x,y)^{r}\,d\sigma_{\mathcal{M}}(x)\text{ over all $Y\subset\mathcal{M}$ with $\lvert Y\rvert\leq n$}, where \mathcal{M} is some compact surface (a Riemannian 2 -manifold, to be precise), \varrho_{\mathcal{M}} and \sigma_{\mathcal{M}} are its induced distance and surface measure, and r>0 . We refer to \mathcal{E}(Y) as the quantization error (with respect to exponent r ) in quantizing the measure d\sigma_{\mathcal{M}}(x) by the discrete set Y . As mentioned above, this defining integral splits into the sum over Voronoi cells: \mathcal{E}(Y)=\int_{\mathcal{M}}\min_{y}\varrho_{\mathcal{M}}(x,y)^{r}\,d\sigma_{\mathcal{M}}(x)=\sum_{y}\int_{D_{y}}\varrho_{\mathcal{M}}(x,y)^{r}\,d\sigma_{\mathcal{M}}(x) where D_{y} is the Voronoi cell containing y in the diagram generated by Y . Thus, the Voronoi diagrams of solutions and near solutions are of central interest for this class of problems. In this context, optimal quantization generalizes the problem of finding the optimal centroidal Voronoi tessellation when r=2 ( [ 8 ] ). These problems are also directly linked to semi-discrete optimal transport (see for example, [ 5 ] ). There has been significant work, particularly in two dimensions, on the asymptotic behaviour of solutions as the number of generating points n tends to infinity. First off, in Euclidean domains a well-known conjecture attributed to Gersho [ 10 ] addresses the periodic nature of the configuration with least quantization error (alternatively, the centroidal Voronoi tessellation with lowest energy). It asserts that there exists a polytope V (not depending on r ) which tiles Euclidean space such that all interior Voronoi cells in the optimal configuration are asymptotically congruent scaled copies of V . In two dimensions (where the conjecture is fully resolved), the optimal polytope V is a regular hexagon, corresponding to an optimal placement of points on a triangular lattice. In dimension three, the optimal polytope V is conjectured to be the truncated octahedron, corresponding to an optimal placement of points on a BCC (body centered cubic) lattice (see for example, [ 2 , 9 , 7 ] ). Voronoi cells which include the boundary are of course irregular, the number of which in two dimensions is O(\sqrt{n}) . Thanks to the seminal work of Gruber, the asymptotic emergence of the regular hexagonal tiling in two dimensions is totally generic. Indeed, for essentially any compact Riemannian 2-manifold and a broad class of functions f , the Voronoi cells tend toward nearly congruent regular hexagons (asymptotically Euclidean) except for a vanishingly small proportion —i.e., o(n) many—of possibly non-hexagonal cells. We refer the reader to Gruber [ 14 , 15 ] for the fully general results, but we will recall in Section 2.1 the special cases that apply to our problem. In this article, we consider domains which are compact 2-manifolds without boundary and address the asymptotics for the number of non-hexagons in the optimal configuration. Borrowing from crystallography (see for example, [ 6 , 17 , 16 , 21 , 18 , 19 ] ), let us make the following definition: Definition . A (topological) defect in a quantizer Y is a non-hexagonal Voronoi cell. We denote the number of such defects by \df(Y) . We remark that from a mathematical point of view, the issue of defects in the optimal quantizers (and in crystallography in general) is largely open. Clearly, the O(\sqrt{n}) many defects in the planar Euclidean case is a tighter bound than Gruber’s general o(n) . It’s also the optimal result in that case, the solutions are always well-distributed throughout the domain and so there must be, up to a constant factor, at least \sqrt{n} many defects due to boundary effects alone. This invites the main question: Question . On a closed surface, do energy minimizers have strictly fewer than O(\sqrt{n}) many defects and if so, how much fewer? Here we present a strategy to answer this question in the affirmative, and moreover produce quantitative upper bounds on the number of defects. The program is based upon a general lower bound on the optimal quantization error (the energy) and related upper bounds for Löschian numbers n (the norms of the Eisenstein integers) realized using the Goldberg-Coxeter construction. A gap lemma is used to reduce the asymptotics of the number of defects (for arbitrary n ) to precisely the asymptotics for the gaps between Löschian numbers. Whereas, our ultimate goal is the application on the 2-sphere, here we complete the program for the hexagonal torus ; the simplest closed surface for which both Gruber’s results and the Goldberg-Coxeter construction apply directly. It’s important to understand that, nonetheless, the problem is non-trivial on the hexagonal torus for this surface does not admit regular hexagonal tilings except for Löschian numbers n , while the asymptotically optimal quantization problem concerns arbitrary (large) n . We prove that the number of defects is at most O(n^{1/4}) —strictly fewer than surfaces with boundary—and conjecture (based upon the number-theoretic Löschian gap conjecture) that it is in fact O(\log n) . Our method also yields a related upper bound on the variance of the

Read the complete text