CS Paper Radar

Optimality of the $D_4$ lattice quantizer

Tianle Liu

cs.IT math.MGmath.CO ·submitted 2026-10-26 13:19 UTC · v2
theory

Abstract

We prove that the root lattice $D_4$ uniquely minimizes the normalized second moment among four-dimensional lattices, up to similarity. The minimum is $13/(120\sqrt{2})$. The proof reduces the problem to polynomial inequalities on three secondary cones. We derive the second-moment formulas geometrically and give explicit polynomial certificates that can be checked by coefficient comparison. We also derive a lower bound for lattice quantizers in every dimension at least two from the number of Voronoi facets, using a comparison with circular cones and concavity in the solid angle. This bound strictly improves the sphere bound and recovers the hexagonal value in dimension two.

Comment
Simplified the proof of four-dimensional optimality, with explicit polynomial certificates now included in the paper. Main results unchanged

Closest papers

Nearest neighbours by meaning across the whole index.

A Nuclear-Norm Lower Bound for Dithered Scalar Quantization of Matrix Products

cs.IT cs.LGmath.NA ·2026-09-04 ·Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal
theorycode/data similarity 0.58
Abstract · 17 pages, 2 figures. Code: https://github.com/piyush314/gauge-floors

We consider the problem of minimizing error in quantized matrix multiplication $C=AB$. Scalar quantization of the factors introduces rounding errors whose scale depends on the maximum absolute entries -- the ranges -- of their rows and columns. These ranges determine the quantization grid steps. To reduce the error, we optimize over product-preserving transformations that alter the factor ranges and grid steps without changing $C$. Specifically, we seek the smallest leading expected squared error over invertible inner changes of basis and orthogonal outer rotations. Under independent, zero-mean subtractive dither noise on an unbounded lattice, we prove the output-only bound $E_{\rm lead} \ge (c_A+c_B)/K \Vert AB\Vert_*^2$, where $K$ is the inner dimension, $c_A$ and $c_B$ are normalized noise variances, and $\Vert AB\Vert_*$ is the nuclear norm. The bound is tight: an SVD-aligned Hadamard construction attains the infimum whenever a Hadamard matrix of order $K$ exists, including every power of two, while an SVD-aligned DCT construction is within a factor of two for every $K$. Without outer rotations, Gram-matrix balancing minimizes factorization energy, and finite-set flattening achieves the bound within $C\log(K(m+n))$. For power-of-two $K$, conditional expectations deterministically select the Hadamard signs in $O((m+n)K^2)$ exact-real operations. Synthetic experiments verify both constructions and illustrate the tradeoff between regularization and conditioning. These results characterize the full-gauge optimum and quantify the cost of preserving row and column indices.

0.61

Gaussian mass inequalities for lattices

cs.IT math.NT ·2026-11-15 ·Minjia Shi, Xinguang Dai, Patrick Solé
similarity 0.58
Abstract · 50 pages

The Gaussian mass of a lattice is the evaluation of its theta series at a real nome and is relevant to lattice coding for the wiretap Gaussian channel. The ratio of the Gaussian mass of stable lattices to the Gaussian mass of the integer lattice was conjectured to be $\le 1$ (Regev et al., 2024). Kominers proved this bound recently for lattices obtained by Construction~A from binary self-dual codes. Building on Kominers' bound, we establish corresponding inequalities on average for Construction~$A_4$ lattices obtained from free self-dual quaternary codes and for Construction~$A_6$ lattices obtained from self-dual senary codes. We also prove the strict Gaussian-mass inequality for extremal unimodular lattices of both Type~II and Type~I. The Type~I result uses the Rains--Sloane definition of extremality. Its proof combines a universal theta truncation with an exact inversion of the shadow coefficients, and a Gaussian inequality for translated lattices. In addition, we obtain an averaging bound over the genus of Type~II lattices, and extend the binary Construction~A inequality to Siegel theta series of arbitrary genus, with further quaternary results under conditions on the residue code.

0.39

Quadratic Complexity of Voronoi Diagrams in $\mathbb{R}^3$ for Lines in a Single Ruling of a Regulus

cs.CG math.AG ·2026-08-27 ·Eunku Park, Kangjin Han
theory similarity 0.52
Abstract · Added a coauthor, more detailed explanations of algebraic geometry, and additional figures

We study nearest and farthest Voronoi diagrams of lines in three-dimensional Euclidean space, which partition space according to the closest and farthest input lines, respectively. For arbitrary lines, a gap remains between the known quadratic lower bound and near-cubic upper bounds for the complexity of the nearest diagram. We consider input lines chosen from one of two continuous families of straight lines on a smooth surface defined by a quadratic equation, with one line from each family passing through every point of the surface. Under the geometric assumptions stated in the paper, we prove quadratic upper bounds on the total number of vertices, edges, faces, and connected three-dimensional regions in both diagrams. We also construct quadratically many nearest vertices using lines from a single family on one fixed surface, establishing a tight quadratic worst-case bound. The farthest diagram has quadratic total complexity for every input satisfying our assumptions. Our proof uses a parametrization that arranges the input lines in a cyclic order and expresses tangency to a sphere by a polynomial equation of degree four. At a Voronoi vertex, the four tangent input lines give four distinct roots. The sign changes between these roots, together with the nearest or farthest condition, force two intervening parameter intervals to contain no other input parameters. Thus, only quadratically many choices of four lines can define a vertex, and each choice yields at most eight isolated candidate centers.

0.27

On the Kissing Number of Craig's Lattice and Spherical List Decoding

cs.IT ·2026-11-17 ·Léo Ducas, Julian Nowakowski, Ailsa Robertson
theory similarity 0.51
Abstract

Craig's lattices $A_{p-1}^k$ are a family of lattices with large kissing numbers, i.e., relative to their dimension $n = p-1$, they contain a large number of shortest nonzero vectors. Specifically, for small $k = o(\log p / \log \log p)$, a lower bound of Bacher (2015) shows that $A_{p-1}^k$ has a super-polynomial kissing number of $ω(n^k)$. Craig's lattices are therefore attractive candidates for the construction of spherical codes. In this work, we introduce a polynomial-time list decoder for spherical codes obtained from Craig's lattices for angular distance below $45^\circ$. Our second main result shows that Bacher's lower bound is asymptotically tight for $k = o(\log p / \log \log p)$. Finally, we introduce an efficient algorithm for computing the kissing number of $A_{p-1}^k$. Using this algorithm, we compute their kissing number in dimensions up to 521. Based on this data, we pose the open question whether the kissing number of $A_{p-1}^k$ with $k \approx \sqrt{p}$ grows like $e^{Θ(\sqrt{n})}$ in dimension $n=p-1$. Concurrent work by Laarhoven and Kominers as well as Bennett, Hhan, Li and Stephens-Davidowitz proves such a bound for very closely related lattices.

0.17

The Honeycomb Framework for Code Bounds

cs.IT cs.DM ·2026-08-20 ·William Gay, Fernando Granha Jeronimo, Lenny Liu
theoryhighly cited similarity 0.51
Abstract

We introduce the honeycomb hierarchy, a representation-theoretic framework that gives new asymptotic upper bounds on $R_2(δ)$. Its first level is the two-row hyperoctahedral representation graph associated with type $S^{(n-k,k)}$. Retaining every two-row irreducible and every coordinate box-transfer channel, together with a moving-projection theorem, yields an explicit four-parameter exponent $κ_{\mathrm{HC}}$. The earlier whole-cube exponent $κ_H$ is a boundary restriction of this optimization, whereas the fully optimized second MRRW exponent $M_2$ is an exact symmetric slice. The prior best curve is the combined $κ_{\mathrm{bin}}=\min\{κ_{\mathrm{CW}},κ_H\}$, which uses a constant-weight branch $κ_{\mathrm{CW}}$. Replacing only the whole-cube branch by the honeycomb bound gives $κ_{\mathrm{best}}=\min\{κ_{\mathrm{CW}}, κ_{\mathrm{HC}}\}$. We prove, on $0<δ<1/2$, \[ R_2(δ)\le κ_{\mathrm{best}}(δ) \le κ_{\mathrm{bin}}(δ) \le R_{\mathrm{2MQC}}(δ)<M_2(δ),\\[-1mm] κ_{\mathrm{best}}(δ) \le \min\{κ_{\mathrm{CW}}(δ), κ_{\mathrm{bal}}(δ)\} <R_{\mathrm{2MQC}}(δ), \qquad κ_H(δ)=R_{\mathrm{MQC}}(δ). \] The hierarchy has two further directions. Increasing the representation depth replaces scalar by matrix-valued transfers on the hive. Increasing the anchor depth localizes it in a stable-set hierarchy. The resulting bounds are monotone in both directions and eventually recover $A_2(n,d)$. A complementary Horn--channel hierarchy gives matrix optimizations whose $2\times2$ level is $κ_{\mathrm{HC}}$ and whose $3\times3$ level is a stronger bound. Already at low levels, they can be used to improve the strongest previous general bounds, while the honeycomb framework provides a route towards tighter bounds.

0.46

Fourth-Moment Geometry of Rademacher Sums

cs.LG math.PR ·2026-08-18 ·Peigan Gao, Jian Qian
similarity 0.51
Abstract

Let $\varepsilon_1,\ldots,\varepsilon_n$ be independent Rademacher signs and let $a=(a_1,\ldots,a_n)\in\R^n$ satisfy the normalization below. For the normalized Rademacher sum, we determine how its higher moments depend on the fourth-order mass. Combining a sharp fixed-q moment envelope with a separate argument below the convexity threshold gives the Gaussian stability inequality for the full range $p\geq4$ of this linear-in-q bound. The same fourth-order framework determines the sharp finite dimensional $L_p/L_4$ Khintchine constant for $p\geq5$, with the flat coefficient vector as the extremizer. These results settle the conjectures of Jakimiuk and of Barański, Murawski, Nayar, and Oleszkiewicz stated below. We also prove Jakimiuk's conjectured quadratic stability estimate at $p=3$. The resulting bounds retain information about sparsity and effective dimension, with applications to Rademacher random projections and randomly signed errors; those applications are not developed further here. Their Laplace-transform form also gives coefficient-sensitive tail bounds. The proofs are discovered with substantial assistance from ChatGPT 5.6 Sol.

0.50

Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation

cs.CG quant-phcs.DS ·2026-10-04 ·Ruizhe Zhang
theory similarity 0.51
Abstract

Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science. Given a quantum membership oracle for a convex body $K\subset\mathbb{R}^d$, we show that estimating $\mathrm{vol}(K)$ to relative error $\varepsilon$ takes $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ queries. This improves the previous quantum upper bound $\widetilde O(d^3+d^{9/4}/\varepsilon)$ of Chakrabarti et al. (ACM TQC 2023) and Cornelissen--Hamoudi (SODA 2023), and achieves a larger quantum speedup over the currently best classical upper bound $\widetilde O(d^{7/2}+d^3/\varepsilon^2)$ of Jia et al. (JACM 2026). Our quantum algorithm combines two new ingredients: an input-dependent effective spectral-gap analysis of quantum walks based on uniform classical warm-start mixing bounds, and a single quantum estimator for products of normalizer ratios in simulated annealing based on classical bridge sampling. We also prove an $Ω(d)$ quantum query lower bound for constant relative error, improving the previous $Ω(\sqrt d)$ lower bound.

0.23

Three Standard Deviations Suffice While One Does Not

cs.DM math.CO ·2026-09-28 ·Victor Reis, Zhao Song
theory similarity 0.51
Abstract · 15 pages

Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4 < 2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n \ge 2^{50}$, there exists a matrix $A \in \{-1,1\}^{n \times n}$ such that $\|Ax\|_\infty >1.0000002\sqrt{n}$ for every choice of signs $x \in \{-1,1\}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.

0.11