arxiv: 2605.07784 · v1 · submitted 2026-05-08 · 💻 cs.DS · cs.CC· cs.SC· math.RA

Recognition: no theorem link

Computing bases in Hermite normal form of lattices of integer relations

George Labahn , Arne Storjohann

Authors on Pith no claims yet

Pith reviewed 2026-05-11 03:22 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.SCmath.RA

keywords Hermite normal forminteger latticeslattice of integer relationsrandomized Las Vegas algorithmsmatrix multiplication complexityDiophantine linear algebracomputational algebra

0 comments

The pith

A Las Vegas randomized algorithm computes the Hermite normal form basis for the lattice of all integer vectors p such that pF lies in the row lattice of M.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors present a randomized algorithm that returns an n by n matrix in Hermite normal form whose rows exactly span the set of all p in Z to the 1 by n satisfying the condition that p times F belongs to the integer lattice generated by the rows of a given full-column-rank matrix M. This lattice is the natural object of study whenever one seeks integer linear dependence relations constrained by an auxiliary matrix F. The same procedure specializes to the classical task of computing the Hermite normal form of M itself when M is square and F is the identity matrix. In that special case the bit complexity is asymptotically the same as the cost of multiplying two matrices of the same dimensions and entry sizes. Readers interested in exact linear algebra over the integers would therefore obtain a practical speed-up for a fundamental canonical-form computation.

Core claim

Given a full column rank matrix M in Z^{ℓ×m} and an integer matrix F in Z^{n×m}, the algorithm computes the n×n basis in Hermite form of the integer lattice comprised of all rows p in Z^{1×n} such that pF lies in the integer lattice generated by the rows of M. The procedure is randomized of the Las Vegas type: it either returns failure or produces the correct result, with failure probability at most 1/2. When M is square and F equals the identity, the returned basis is the Hermite normal form of M and the bit operation count matches the cost of multiplying two matrices of the same dimension and entry bit length.

What carries the argument

The Las Vegas randomized procedure that returns a Hermite normal form basis for the preimage lattice defined by the linear condition pF belonging to the row lattice of M.

If this is right

When M is square and F is the identity matrix the output is exactly the Hermite normal form of M.
The bit complexity in the square case equals the cost of two matrix multiplications of the input dimensions and entry sizes.
The algorithm returns a correct basis whenever it does not report failure.
The method applies directly to rectangular full-column-rank M and to arbitrary auxiliary matrices F.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same reduction could be used inside computer algebra systems to accelerate any routine that currently relies on slower Hermite normal form implementations for integer matrices.
Applications that repeatedly compute minimal integer relations, such as lattice-based cryptography or exact linear programming, would become feasible at larger scales.
Direct comparison of the new output against a classical slow algorithm on random small matrices would give immediate empirical confirmation of correctness.

Load-bearing premise

The random choices performed by the algorithm succeed with probability at least one half, and the input matrix M has full column rank.

What would settle it

Run the algorithm on a small square full-rank integer matrix M with F set to the identity, then verify that the output matrix is in Hermite normal form, has the same determinant as M, and that its rows span precisely the same lattice as the classical definition.

Figures

Figures reproduced from arXiv: 2605.07784 by Arne Storjohann, George Labahn.

read the original abstract

Given a full column rank $M \in \Z^{\ell \times m}$ and an $F \in \Z^{n \times m}$ we present an algorithm to compute the $n \times n$ basis in Hermite form of the integer lattice comprised of all rows $p \in \Z^{1 \times n}$ such that $pF \in \Z^{1 \times m}$ is in the integer lattice generated by the rows of $M$. The algorithm is randomized of the Las Vegas type, that is, it can fail with probability at most $1/2$, but if fail is not returned it guarantees to produce the correct result. When $M$ is square and $F=I_m$, then the computed basis is the Hermite normal form of $M$, and the algorithm uses about the same number of bit operations as required to multiply together two matrices of the same dimension and size of entries as $M$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

A new Las Vegas algorithm for Hermite bases of relation lattices that matches matrix multiplication cost in the square case.

read the letter

The key takeaway is that this paper gives a randomized Las Vegas algorithm to compute the n by n Hermite normal form basis of the integer lattice of rows p such that pF lies in the row lattice of M. When M is square and F is the identity, the output is the HNF of M and the bit complexity is about the same as multiplying two matrices of matching dimension and entry size. The algorithm can return fail with probability at most 1/2 but is guaranteed correct otherwise. The full paper supplies the procedure, a correctness proof under the full column rank assumption on M, and the complexity analysis tied to matrix multiplication. This is a concrete advance for the general relation lattice setting rather than just the standard HNF case. The work handles the extension to arbitrary F cleanly and avoids hidden parameters or circular steps in the argument. The main limitation is the probabilistic failure mode, which means a small number of restarts in practice, though the 1/2 bound is standard for this style of algorithm. The full rank requirement is stated explicitly and is necessary for the lattice to have the claimed dimension. No other gaps appear in the reasoning or the reduction to the matrix multiplication benchmark. This is for researchers who need efficient HNF computations in computer algebra, integer relation detection, or lattice-based cryptography. A reader working on implementations or complexity of algebraic algorithms would get direct value from the complexity result. The paper shows clear thinking and solid grounding in the existing literature on lattice bases. I would send it to peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript presents a Las Vegas randomized algorithm that, given a full-column-rank integer matrix M ∈ ℤ^{ℓ×m} and an arbitrary integer matrix F ∈ ℤ^{n×m}, computes an n×n basis in Hermite normal form for the lattice of all row vectors p ∈ ℤ^{1×n} such that pF lies in the integer row lattice generated by M. The algorithm returns 'fail' with probability at most 1/2 but is guaranteed correct on success. In the special case M square and F = I_m the output is the HNF of M and the bit complexity is asymptotically the same as that of multiplying two matrices of the same dimensions and entry size.

Significance. If the claimed algorithm, correctness proof, and complexity bound hold, the result is a useful generalization of HNF computation to lattices of integer relations. The reduction to matrix-multiplication complexity in the standard case is a notable strength, as it places the procedure on the same footing as the best current HNF algorithms and supplies a concrete, falsifiable complexity statement.

minor comments (3)

§2.1: the notation for the row lattice generated by M is introduced without an explicit definition of the ambient module; adding one sentence would remove ambiguity for readers unfamiliar with the integer-relation setting.
Algorithm 1, line 12: the random sampling step is described only at a high level; a brief remark on the bit length of the sampled entries and the precise failure-probability calculation would improve reproducibility.
Theorem 5.3: the complexity statement is given in terms of matrix multiplication; it would be helpful to state the precise exponent (e.g., the current best ω) used in the O-notation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work, recognition of its significance as a generalization of HNF computation, and recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The manuscript presents an explicit Las Vegas randomized algorithm for computing the n×n HNF basis of the integer lattice {p ∈ Z^{1×n} | pF lies in the row lattice of M}, together with a correctness proof under the stated full-column-rank assumption and a complexity analysis that reduces the special case (M square, F = I) to a constant number of matrix multiplications of matching dimension and entry size. All load-bearing steps are direct algorithmic constructions and standard lattice definitions; no equation or claim reduces by construction to a fitted parameter, self-citation, or renamed input. The complexity reference is an external benchmark (matrix multiplication), not an internal tautology. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard existence and uniqueness of Hermite normal forms for full-rank integer lattices and on the probabilistic correctness of the Las Vegas procedure; no free parameters or new entities are introduced.

axioms (2)

standard math Hermite normal form exists and is unique for any full column rank integer matrix
Invoked implicitly when the algorithm is said to return the basis in Hermite form.
domain assumption The lattice of integer relations p with pF in the row lattice of M is a full-rank Z-module of rank n
Required for the output to be an n by n basis.

pith-pipeline@v0.9.0 · 5469 in / 1465 out tokens · 49608 ms · 2026-05-11T03:22:36.900351+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

[1]

Alman and V

J. Alman and V. V. Williams. A refined laser method and faster matrix multiplication. InProc. of 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539, 2021

work page 2021
[2]

Beckermann and G

B. Beckermann and G. Labahn. A uniform approach for the fast computation of matrix–type Padé approximants.SIAM Journal on Matrix Analysis and Applications, 15(3):804–823, 1994

work page 1994
[3]

Beckermann and G

B. Beckermann and G. Labahn. Recursiveness in matrix rational interpolation problems.Journal of Computational and Applied Math, 77:5–34, 1997

work page 1997
[4]

Biasse, C

J.-F. Biasse, C. Fieker, and T. Hofmann. On the computation of the HNF of a module over the ring of integers of a number field.Journal of Symbolic Computation, 40(3):581–615, 2017

work page 2017
[5]

Birmpilis, G

S. Birmpilis, G. Labahn, and A. Storjohann. A Las Vegas algorithm for computing the Smith form of a nonsingular integer matrix. InProc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’20, page 38–45, New York, NY, USA, 2020. ACM

work page 2020
[6]

Birmpilis, G

S. Birmpilis, G. Labahn, and A. Storjohann. A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix.Journal of Symbolic Computation, 116:146–182, 2023

work page 2023
[7]

Birmpilis, G

S. Birmpilis, G. Labahn, and A. Storjohann. A cubic algorithm for computing the Hermite normal form of a nonsingular integer matrix.ACM Transactions of Algorithms, 19:1–36, 2023

work page 2023
[8]

Deterministic reduction of integer nonsin- gular linear system solving to matrix multiplication

Stavros Birmpilis, George Labahn, and Arne Storjohann. Deterministic reduction of integer nonsin- gular linear system solving to matrix multiplication. InProc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’19, page 58–65, New York, NY, USA, 2019. ACM. ISBN 9781450360845

work page 2019
[9]

T-W. J. Chou and G. E. Collins. Algorithms for the solutions of systems of linear diophantine equations. SIAM Journal of Computing, 11:687–708, 1982

work page 1982
[10]

P. D. Domich, R. Kannan, and L. E. Trotter, Jr. Hermite normal form computation using modulo determinant arithmetic.Mathematics of Operations Research, 12(1):50–59, 1987

work page 1987
[11]

Dumas, C

J.-G. Dumas, C. Pernet, and Z. Sultan. Fast computation of the rank profile matrix and the generalized Bruhat decomposition.Journal of Symbolic Computation, 83:187–210, 2017

work page 2017
[12]

von zur Gathen and J

J. von zur Gathen and J. Gerhard.Modern Computer Algebra. Cambridge University Press, 3rd edition, 2013

work page 2013
[13]

Gupta, S

S. Gupta, S. Sarkar, A. Storjohann, and J. Valeriote. Triangularx-basis decompositions and derandom- ization of linear algebra algorithms overK[x].Journal of Symbolic Computation, 47(4), 2012. Festschrift for the 60th Birthday of Joachim von zur Gathen

work page 2012
[14]

J. L. Hafner and K. S. McCurley. Asymptotically fast triangularization of matrices over rings.SIAM Journal of Computing, 20(6):1068–1083, December 1991

work page 1991
[15]

C. Hermite. Sur l’introduction des variables continues dans la théorie des nombres.J. Reine Angew. Math., 41:191–216, 1851

work page
[16]

J. A. Howell. Spans in the module(Zm)s.Linear and Multilinear Algebra, 19:67—77, 1986

work page 1986
[17]

Ibarra, S

O. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications.Journal of Algorithms, 3:45–56, 1982

work page 1982
[18]

C. S. Iliopoulos. Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix.SIAM Journal of Computing, 18(4):658–669, 1989. 37

work page 1989
[19]

Jeannerod, C

C.-P. Jeannerod, C. Pernet, and A. Storjohann. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition.Journal of Symbolic Computation, 56:56–58, 2013

work page 2013
[20]

Jeannerod, V

C.-P. Jeannerod, V. Neiger, É. Schost, and G. Villard. Computing minimal interpolation bases.Journal of Symbolic Computation, 83:272–314, 2017

work page 2017
[21]

Kannan and A

R. Kannan and A. Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of and integer matrix.SIAM Journal of Computing, 8(4):499–507, November 1979

work page 1979
[22]

O. Knill. A Multivariable Chinese Remainder Theorem, 2012. URLhttps://arxiv.org/abs/1206. 5114

work page 2012
[23]

Labahn, V

G. Labahn, V. Neiger, and W. Zhou. Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix.Journal of Complexity, 42:44–71, 2017

work page 2017
[24]

Liu and Y

R. Liu and Y. Pan. Computing Hermite normal form faster via solving system of linear equations. In Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’19, page 283–290, New York, NY, USA, 2019. ACM

work page 2019
[25]

Micciancio and B

D. Micciancio and B. Warinschi. A linear space algorithm for computing the Hermite normal form. In B. Mourrain, editor,Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’01, pages 231—236. ACM Press, New York, 2001

work page 2001
[26]

Neiger and T

V. Neiger and T. X. Vu. Computing canonical bases of modules of univariate relations. InProc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’17. ACM Press, New York, 2017

work page 2017
[27]

O. Ore. The General Chinese Remainder Theorem.The American Mathematical Monthly., 59:365–370, 1952

work page 1952
[28]

Pauderis and A

C. Pauderis and A. Storjohann. Computing the invariant structure of integer matrices: Fast algorithms into practice. InProc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’13, pages 307–314, New York, NY, USA, 2013. ACM

work page 2013
[29]

Pernet and W

C. Pernet and W. Stein. Fast computation of Hermite normal forms of integer matrices.Journal of Number Theory, 130(7):1675–1683, 2010

work page 2010
[30]

Saunders and Zhendong Wan

D. Saunders and Zhendong Wan. Smith normal form of dense integer matrices, fast algorithms into practice. In J. Gutierrez, editor,Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’04, pages 274–281. ACM Press, New York, 2004

work page 2004
[31]

Storjohann.Algorithms for Matrix Canonical Forms

A. Storjohann.Algorithms for Matrix Canonical Forms. PhD thesis, Swiss Federal Institute of Tech- nology, ETH–Zurich, 2000

work page 2000
[32]

High–orderlifting.ExtendedAbstract

A.Storjohann. High–orderlifting.ExtendedAbstract. InT.Mora, editor,Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’02, pages 246–254. ACM Press, New York, 2002

work page 2002
[33]

Storjohann

A. Storjohann. High–order lifting and integrality certification.Journal of Symbolic Computation, 36 (3–4):613–648, 2003. Extended abstract in [32]

work page 2003
[34]

Storjohann

A. Storjohann. Notes on computing minimal approximant bases. In W. Decker, M. Dewar, E. Kaltofen, and S. Watt, editors,Challenges in Symbolic Computation Software, number 06271 in Dagstuhl Semi- nar Proceedings. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006. URLhttp://drops.dagstuhl.de/opus/vollt...

work page 2006
[35]

Storjohann and G

A. Storjohann and G. Labahn. Asymptotically fast computation of Hermite normal forms of integer matrices. In Y. N. Lakshman, editor,Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’96, pages 259–266. ACM Press, New York, 1996. 38

work page 1996
[36]

Storjohann and T

A. Storjohann and T. Mulders. Fast algorithms for linear algebra moduloN. In G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci, editors,Algorithms — ESA ’98, LNCS 1461, pages 139–150. Springer Verlag, 1998

work page 1998
[37]

Multivariable Chinese Remainder Theorem.Resonance, 20:206–216, 2015

B Sury. Multivariable Chinese Remainder Theorem.Resonance, 20:206–216, 2015

work page 2015
[38]

Z. Wang, S. Birmpilis, G. Labahn, and A. Storjohann. A C implementation of the Smith massager algorithm, 2026. In progress

work page 2026
[39]

Zhou and G

W. Zhou and G. Labahn. Efficient computation of order basis. In J. P. May, editor,Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’09, pages 375–384. ACM Press, New York, 2009

work page 2009
[40]

Zhou and G

W. Zhou and G. Labahn. Computing column bases of polynomial matrices. InProc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’13, pages 379–388. ACM Press, Boston, USA, 2013

work page 2013
[41]

W. Zhou, G. Labahn, and A. Storjohann. Computing minimal nullspace basis. In J. van der Hoeven and M. van Hoeij, editors,Proc. Int’l. Symp. on Symbolic and Algebraic Computation: ISSAC’12, pages 366–373. ACM Press, New York, 2012

work page 2012
[42]

W. Zhou, G. Labahn, and A. Storjohann. A deterministic algorithm for inverting a polynomial matrix. Journal of Complexity, 31:162–173, 2015. 39

work page 2015