Variational and Majorization Principles in Lattice Reduction
Javier Blanco-Romero, Florina Almenares Mendoza · 2026
Read Variational and Majorization Principles in Lattice Reduction by Javier Blanco-Romero, Florina Almenares Mendoza (2026) 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-2604-27801.txt.
Introduction
Blanco-Romero and Almenares Mendoza use majorization to describe the local swap engine behind Gram-Schmidt smoothing in lattice trimming. Each working Lovász swap works like a T-transform, reshaping the log-norm profile, cutting every Schur-convex spread measure. The worst-case GSA shell is the unique lowest-spread profile fitting Lovász gap shape, its slope set by LLL alone. The swap path meets an exact folding rule for variance loss. The viewpoint orders deep-insert rules and suggests Thermal-Adaptive and Geodesic Deep-LLL.
Catalog record
| CREATOR | Javier Blanco-Romero, Florina Almenares Mendoza |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66864 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.27801
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Variational and Majorization Principles in Lattice Reduction Javier Blanco-Romero, Florina Almenares Mendoza Abstract Lattice reduction smooths the Gram-Schmidt profile, and we use majorization to describe the local swap mechanism behind that smoothing. In this language, each non-degenerate Lovász swap acts as a T-transform on the log-norm profile. As a consequence, every strictly Schur-convex measure of profile spread decreases at such a swap. Two structural consequences follow. First, the worst-case GSA envelope admits a variational interpretation. It is the unique minimum-variance profile compatible with the Lovász gap geometry, so its slope is determined by the LLL parameter alone. Second, the realized swap trajectory satisfies an exact telescoping identity for variance dissipation. The same viewpoint also helps organize deep-insertion heuristics. It suggests a thermal family of Schur-convex scoring rules, motivates adaptive selection within that family, and leads to two concrete selectors: Thermal-Adaptive, which reduces operation counts relative to SS-GG on flat profiles in our benchmarks while recovering SS-GG on q q -ary inputs, and Geodesic Deep-LLL, which reduces equivalent-swap counts on structured lattices in our benchmarks at higher wall-clock cost. \DeclareSourcemap \maps [datatype=bibtex] \map \step [fieldsource=abstract,null] \step [fieldset=abstract,null] Keywords: Lattice reduction; LLL algorithm; majorization; T-transform; Schur-convexity; Gram-Schmidt orthogonalization; q -ary lattices Mathematics Subject Classification (2020): 11Y16; 11H06; 68W25 1 Introduction Lattice reduction smooths a basis. The Gram-Schmidt log-norm profile of a raw lattice basis is usually jagged, and after LLL [ 10 ] , BKZ [ 15 ] , or BKZ 2.0 [ 4 ] it is often close to linear. Two questions sit behind that familiar picture: why does the profile flatten, and how much can the next move steer that flattening? The standard answer to the first is usually phrased through the Geometric Series Assumption [ 14 ] and explored quantitatively with simulators [ 4 ] . Together they describe the profile shape reduction tends to produce, but not the local swap dynamics that drive the flattening. The second question has led to a family of deep-insertion selectors [ 5 , 17 , 3 ] . Each chooses an objective and descends in it, with the choice justified mainly by algorithmic behavior. We go one level lower, to the individual swap. A non-degenerate Lovász swap preserves the sum of two adjacent log-norms and pulls them strictly closer together. In the language of majorization theory [ 11 ] , it is a T-transform, so the post-swap profile is majorized by the pre-swap one. Every strictly Schur-convex function of the profile therefore decreases at every non-degenerate swap, independently of the dimension, the input distribution, and the LLL threshold \delta . That local law has two consequences. On the dynamics side, the log-determinant pins the profile to an affine hyperplane and the Lovász condition bounds adjacent log-norm gaps; under both constraints, the arithmetic progression whose slope depends only on \delta is the unique minimum-variance shape. Its slope is the steepest descent any \delta -LLL output can sustain in the worst case; the Gram-Schmidt log slopes that Gama and Nguyen [ 7 ] measure on real bases are shallower, in line with the variance-dissipation picture below. On the algorithmic side, the same structure organizes deep-insertion selectors into two families, a symmetric one that treats profile entries equally and contains SS-GG, and a position-weighted one that contains Pot-DeepLLL. Within the thermal subfamily, adaptive selection becomes natural as the profile drifts. Section 2 surveys prior work, Section 3 sets the background, Section 4 proves the per-swap structure, Section 5 develops the selector implications, Section 6 tests them, and Sections 7 – 8 close the loop. 2 Related Work Two strands of prior work bear on the per-swap picture: the evolution of the GSO profile during reduction, and the algorithmic exploitation of that evolution through objective-driven selectors. On the dynamics side, Schnorr’s Geometric Series Assumption [ 14 ] approximates BKZ output by a geometric sequence \lVert\mathbf{b}_{i}^{*}\rVert^{2}/\lVert\mathbf{b}_{1}^{*}\rVert^{2}=q^{i-1} , with quotient q depending on blocksize. Gama and Nguyen [ 7 ] measured Gram-Schmidt log slopes across LLL, DeepLLL, and BKZ and linked the slope to the root-Hermite factor. Chen and Nguyen [ 4 ] built the GSA into the BKZ 2.0 simulator; Hanrot, Pujol, and Stehlé [ 9 ] analyzed BKZ as a dynamical system on profile space and showed convergence to a quasi-GSA fixed point; Micciancio and Walter [ 12 ] pushed the predictive side further with closed-form quality estimates. At finer scale, Yu and Ducas [ 19 ] observed negative correlation between adjacent squared norms r_{i} and r_{i+1} and a self-stabilizing reduction of global profile variance; Bai, Stehlé, and Wen [ 2 ] documented the head concavity that makes BKZ output deviate from a straight line at small blocksize, a deviation that shrinks as the blocksize grows. These results characterize the shape reduction converges to and the rate of convergence at the tour level, but do not certify monotonicity of nonlinear profile functionals at the level of a single swap. On the algorithmic side, nonsequential local reduction begins with DeepLLL [ 15 ] , where a basis vector is inserted at an earlier position whenever a generalized Lovász condition is violated. The polynomial-time variants Pot-DeepLLL and SS-DeepLLL replaced that rule by descent in an explicit objective: the basis potential \mathrm{Pot}(B)=\prod_{i}\lVert\mathbf{b}_{i}^{*}\rVert^{2(d-i+1)} [ 5 ] and the squared-sum \mathrm{SS}(B)=\sum_{i}\lVert\mathbf{b}_{i}^{*}\rVert^{2} [ 17 ] . Efficient GSO update formulas [ 16 ] made these schemes practical, and the SS objective already appeared as a preprocessing criterion in SVP sampling [ 6 ] . Yasuda et al. [ 18 ] gave conditional decrease guarantees for SS under individual LLL swaps. The X-GG framework of Bhattacherjee, Hernandez-Castro, and Moyler [ 3 ] globalizes the descent idea, searching the whole basis for the insertion that most decreases an objective X and obtaining the SS-GG and Pot-GG instances. Across this line, each objective is motivated by its algorithmic behavior, and there is no common principle that selects or parameterizes them from the geometry of the swap itself. Majorization is standard in matrix analysis, quantum information, and resource theory [ 11 ] . We are not aware of prior work using it to organize the per-swap dynamics of lattice reduction or to derive deep-insertion objective families from the structure of the underlying move. 3 Background Three ingredients carry the rest of the paper: the GSO log-norm profile, the Lovász swap, and the majorization language that describes what a swap does. 3.1 The GSO log-norm profile Definition 1 (GSO log-norm profile) . Given a lattice basis \mathbf{B}=(\mathbf{b}_{1},\ldots,\mathbf{b}_{d}) , its GSO log-norm profile is \mathbf{p}=(p_{1},\ldots,p_{d}) with p_{i}=\ln\lVert\mathbf{b}_{i}^{*}\rVert and r_{i}=\lVert\mathbf{b}_{i}^{*}\rVert^{2}=e^{2p_{i}} , where \mathbf{b}_{i}^{*} are the Gram-Schmidt vectors and \ln denotes the natural logarithm (used throughout). Every basis change in lattice reduction multiplies \mathbf{B} on the left by a unimodular matrix, so |\det\mathbf{B}|=\prod_{i}r_{i}^{1/2} is preserved and so is its logarithm: \textstyle\sum_{i=1}^{d}p_{i}=\ln\lvert\det(\mathbf{B})\rvert. (1) The LLL potential \Phi=\sum_{i=1}^{d}(d-i+1)\,p_{i} is a position-weighted sum, with earlier positions contributing more heavily. It serves as a termination certificate: \Phi decreases strictly at each Lovász swap and is bounded below by a lattice-dependent constant, so the algorithm performs only finitely many swaps. Unlike the log-determinant, \Phi is strictly decreasing rather than conserved. 3.2 Lovász swaps A swap at position k is triggered when the Lovász condition is violated: r_{k}<(\delta-\mu_{k,k-1}^{2})\,r_{k-1}, (2) where \mu_{k,k-1} is the (k,k-1) Gram-Schmidt coefficient