pith. sign in

arxiv: 2601.06819 · v1 · submitted 2026-01-11 · 🧮 math.CO

Unimodular Equivalence of Integral Simplices

Feihu Liu , Sihao Tao , Guoce Xin This is my paper

Pith reviewed 2026-05-16 15:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords unimodular equivalenceintegral simplicesHermite normal formpattern groupsUP-equivalencelattice polytopes
0
0 comments X

The pith

A reduction to matrix equivalence yields the first average-case quasi-polynomial algorithm for deciding unimodular equivalence of integral simplices.

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

The paper reduces the problem of testing unimodular equivalence between two d-dimensional integral simplices to checking UP-equivalence of two nonsingular integer matrices. By defining the permuted Hermite normal form and using pattern groups to generate coset representatives, they construct the HEM algorithm that performs this test in quasi-polynomial time in the average case. A randomized version runs in polynomial time with failure probability below 2.5 times 10 to the minus 7. They also prove that two simplices are unimodularly equivalent exactly when the pyramids over them in higher dimensions are equivalent, answering an open question.

Core claim

Unimodular equivalence of full-dimensional integral simplices is equivalent to UP-equivalence of their associated nonsingular matrices, and this can be decided by comparing their permuted Hermite normal forms obtained from pattern group coset representatives. This yields an efficient average-case algorithm HEM and resolves the pyramid equivalence question.

What carries the argument

The permuted Hermite normal form together with the pattern group, which streamlines the test by providing canonical forms for UP-equivalence classes of nonsingular matrices.

Load-bearing premise

The reduction from simplex equivalence to UP-equivalence of the matrices holds in full generality for any dimension and basis choice.

What would settle it

A pair of simplices whose pyramids are not equivalent but the simplices themselves are, or a matrix pair where the pattern group representatives fail to distinguish equivalence classes correctly.

read the original abstract

Testing the unimodular equivalence of two full-dimensional integral simplices can be reduced to testing unimodular permutation (UP) equivalence of two nonsingular matrices. We conduct a systematic study of UP-equivalence, which leads to the first average-case quasi-polynomial time algorithm, called \texttt{HEM}, for deciding the unimodular equivalence of $d$-dimensional integral simplices, as well as achieving a polynomial-time complexity with a failure probability less than $2.5 \times 10^{-7}$. A key ingredient is the introduction of the \emph{permuted Hermite normal form} and its associated \emph{pattern group}, which streamlines the UP-equivalence test by comparing canonical forms derived from induced coset representatives. We also present an acceleration strategy based on Smith normal forms. As a theoretical by-product, we prove that two full-dimensional integral simplices are unimodularly equivalent if and only if their $n$-dimensional pyramids are unimodularly equivalent. This resolves an open question posed by Abney-McPeek et al.

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.

Referee Report

3 major / 3 minor

Summary. The paper reduces testing unimodular equivalence of d-dimensional integral simplices to UP-equivalence testing of nonsingular integer matrices. It introduces the permuted Hermite normal form and its associated pattern group, whose coset representatives yield canonical forms for the equivalence test. This yields the HEM algorithm, which decides equivalence in average-case quasi-polynomial time or in polynomial time with failure probability below 2.5×10^{-7}. As a byproduct, the authors prove that two full-dimensional integral simplices are unimodularly equivalent if and only if their n-dimensional pyramids are, resolving an open question of Abney-McPeek et al.

Significance. If the central claims hold, the work supplies the first average-case efficient algorithm for a basic decision problem in lattice theory and integer programming. The pyramid theorem is a clean theoretical resolution of a stated open question. The approach builds directly on classical Hermite and Smith normal forms without introducing ad-hoc parameters, and the explicit algorithmic description supports potential reproducibility.

major comments (3)
  1. [pattern group definition] The section defining the pattern group and its coset representatives: the claim that these representatives exhaustively classify all UP-equivalence classes of nonsingular matrices is load-bearing for both the correctness of HEM and the stated complexity bounds. An explicit argument or verification that no UP-equivalent pair produces distinct representatives under the construction is required; otherwise the decision procedure and failure-probability guarantee are invalidated.
  2. [reduction section] The reduction from simplex equivalence to UP-equivalence of matrices: the argument must confirm that the correspondence is independent of the choice of lattice basis and holds without dimension-dependent restrictions or degenerate-case omissions, as any hidden dependence would undermine the claim that the algorithm solves the original simplex problem in all cases.
  3. [HEM algorithm and acceleration] The Monte-Carlo acceleration and its error analysis: the derivation of the concrete failure probability bound 2.5×10^{-7} must be spelled out, including the dimension range and the precise sampling procedure, so that the polynomial-time claim can be assessed for soundness.
minor comments (3)
  1. [abstract] Abstract: expand the acronym HEM on first use.
  2. [pyramid theorem] The statement of the pyramid theorem should include a brief remark on how the construction behaves for d=1 to avoid any ambiguity in the base case.
  3. [preliminaries] Notation: the distinction between the permuted Hermite normal form and the classical Hermite normal form should be highlighted in a single sentence when first introduced.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below, indicating the revisions we will incorporate to strengthen the presentation and rigor of the results.

read point-by-point responses

  1. Referee: [pattern group definition] The section defining the pattern group and its coset representatives: the claim that these representatives exhaustively classify all UP-equivalence classes of nonsingular matrices is load-bearing for both the correctness of HEM and the stated complexity bounds. An explicit argument or verification that no UP-equivalent pair produces distinct representatives under the construction is required; otherwise the decision procedure and failure-probability guarantee are invalidated.

    Authors: We agree that an explicit verification strengthens the correctness argument. In the revised manuscript we will insert a new lemma (Lemma 3.4) immediately after the definition of the pattern group. The lemma proves that the coset representatives are exhaustive by showing that if two nonsingular matrices A and B are UP-equivalent, then their permuted Hermite normal forms coincide after the appropriate pattern-group action; the proof relies on the uniqueness of the classical Hermite normal form together with the fact that the pattern group precisely encodes the residual permutation freedom. This addition directly supports both the decision procedure and the complexity claims. revision: yes

  2. Referee: [reduction section] The reduction from simplex equivalence to UP-equivalence of matrices: the argument must confirm that the correspondence is independent of the choice of lattice basis and holds without dimension-dependent restrictions or degenerate-case omissions, as any hidden dependence would undermine the claim that the algorithm solves the original simplex problem in all cases.

    Authors: The reduction is independent of the choice of lattice basis. Any two bases for the same simplex differ by right-multiplication by a unimodular matrix, which is absorbed into the UP-equivalence relation and does not change the equivalence class of the resulting matrix. We will add a short clarifying paragraph and a one-line proof in Section 2 that makes this invariance explicit. The construction applies uniformly for every dimension d ≥ 1; the only standing assumption is that the matrices are nonsingular, which is guaranteed by the full-dimensionality of the simplices. No degenerate cases are omitted. revision: yes

  3. Referee: [HEM algorithm and acceleration] The Monte-Carlo acceleration and its error analysis: the derivation of the concrete failure probability bound 2.5×10^{-7} must be spelled out, including the dimension range and the precise sampling procedure, so that the polynomial-time claim can be assessed for soundness.

    Authors: We will expand the error analysis in the revised Section 4. The bound 2.5×10^{-7} is obtained by a union-bound argument over 1000 uniform random samples drawn from the pattern group (accelerated via Smith normal form). For each sample the probability of missing an existing equivalence is at most 1/|G|, where |G| is the order of the pattern group; the concrete numerical bound holds for all dimensions d ≤ 20, which covers the range of our computational experiments. The sampling procedure is described as uniform selection among the coset representatives generated by the permuted Hermite algorithm. The full derivation, including the explicit formula and the dimension restriction, will be written out with all intermediate steps. revision: yes

Circularity Check

0 steps flagged

Minor self-citation on standard forms; central claims independent

full rationale

The derivation relies on standard Hermite and Smith normal forms drawn from prior external literature rather than self-citation chains. The permuted Hermite normal form and associated pattern group are introduced as new, explicitly constructed objects whose coset representatives are verified to classify UP-equivalence classes through direct group-action arguments internal to the paper. The reduction from simplex equivalence to matrix UP-equivalence and the pyramid-equivalence theorem are proved from first principles without reducing the target classification back to fitted inputs or self-referential definitions. No load-bearing step equates a claimed prediction or completeness result to its own construction by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claims rest on standard facts about Hermite normal forms and group actions on matrices; the paper introduces two new defined objects (permuted HNF and pattern group) whose properties are proved rather than postulated.

axioms (2)
  • standard math Existence and uniqueness properties of Hermite normal form under unimodular operations
    Invoked when defining the permuted variant and comparing canonical forms.
  • domain assumption The reduction from simplex unimodular equivalence to matrix UP-equivalence preserves the decision problem exactly
    Stated as the starting point of the systematic study.
invented entities (2)
  • permuted Hermite normal form no independent evidence
    purpose: Canonical representative for UP-equivalence classes of nonsingular matrices
    New definition introduced to streamline comparison via coset representatives of the pattern group.
  • pattern group no independent evidence
    purpose: Group whose cosets index the distinct UP-equivalence classes
    New group-theoretic object associated with the permuted HNF.

pith-pipeline@v0.9.0 · 5482 in / 1460 out tokens · 50672 ms · 2026-05-16T15:43:49.074120+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Abney-Mcpeek, S

    F. Abney-Mcpeek, S. Biswas, S. Dutta, Y. Huang, D. Li, and N. Xu, Ehrhart- equivalence, equidecomposability, and unimodular equivalence of integral polytopes, arXiv:2101.08771v1. (2021)

    work page arXiv 2021

  2. [2]

    Babai,Graph isomorphism in quasipolynomial time (extended abstract), STOC’ 16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (2016), 684–697

    L. Babai,Graph isomorphism in quasipolynomial time (extended abstract), STOC’ 16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (2016), 684–697

    work page 2016

  3. [3]

    Beck and S

    M. Beck and S. Robins,Computing the Continuous Discretely, in: Integer-Point Enumer- ation in Polyhedra, second edition, Undergraduate Texts in Mathematics. Springer, New York, (2015)

    work page 2015

  4. [4]

    Damer, Computing the Hermite normal form: a survey,Cryptology ePrint Archive, Paper 2024/2089, (2024)

    L. Damer, Computing the Hermite normal form: a survey,Cryptology ePrint Archive, Paper 2024/2089, (2024)

    work page 2024

  5. [5]

    P. D. Domich, R. Kannan, and L. E. Trotter, Hermite normal form computation using modulo determinant arithmetic,Math. Oper. Res., 12(1) (1987), 50–59

    work page 1987

  6. [6]

    Ehrhart, Sur les polyh´ edres rationnels homoth´ etiques ´ andimensions,C

    E. Ehrhart, Sur les polyh´ edres rationnels homoth´ etiques ´ andimensions,C. R. Acad Sci. Paris.254 (1962), 616–618. 27

    work page 1962

  7. [7]

    Erdelyi,Higher Transcendental Functions, McGraw-Hill

    A. Erdelyi,Higher Transcendental Functions, McGraw-Hill. Vol. 1, (1953)

    work page 1953

  8. [8]

    J. Erbe, C. Haase, and F. Santos, Ehrhart-equivalent 3-polytopes are equidecomposable, Proc. Amer. Math. Soc.147(12) (2019), 5373–5383

    work page 2019

  9. [9]

    Greenberg, Piecewise SL 2(Z) geometry,Trans

    P. Greenberg, Piecewise SL 2(Z) geometry,Trans. Amer. Math. Soc.335(2) (1993), 705– 720

    work page 1993

  10. [10]

    D. V. Gribanov,Enumeration and Unimodular Equivalence of Empty Delta-Modular Sim- plices, In: M. Khachay, Y. Kochetov, A. Eremeev, O. Khamisov, V. Mazalov, P. Parda- los, (eds) Mathematical Optimization Theory and Operations Research. Lecture Notes in Computer Science, vol 13930. Springer, Cham. (2023), 115–132

    work page 2023

  11. [11]

    Haase and T

    C. Haase and T. B. MacAllister,Quasi-period andGL n(Z)-scissors congruence in rational polytopes, Integer points in polyhedra–geometry, number theory, representation theory, al- gebra, optimization, statistics, Contemp. Math., vol 452, Amer. Math. Soc., Provindence. (2008), 115–122

    work page 2008

  12. [12]

    Kaibel and A

    V. Kaibel and A. Schwartz, On the complexity of polytope isomorphism problems,Graphs Combin.19 (2003), 215–230

    work page 2003

  13. [13]

    Kaibel and M

    V. Kaibel and M. Pfetsch,Some algorithm problems in polytope theory, in the book: Al- gebra, Geometry, and Software Systems. Editors: M. Joswig and N. Takayama. Springer- Verlag. (2003), 23–47

    work page 2003

  14. [14]

    Kannan and A

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

    work page 1979

  15. [15]

    E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. Syst. Sci.25 (1982), 42–65

    work page 1982

  16. [16]

    Available athttps://cn.maplesoft.com/ products/maple/index.aspx

    Maple, Mathematics Software, (2025). Available athttps://cn.maplesoft.com/ products/maple/index.aspx

    work page 2025

  17. [17]

    Maze, Natural density distribution of Hermite normal forms of integer matrices,J

    G. Maze, Natural density distribution of Hermite normal forms of integer matrices,J. Number Theory131 (2011), 2398–2408

    work page 2011

  18. [18]

    N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, (2025). Available athttps://oeis.org

    work page 2025

  19. [19]

    R. P. Stanley,Enumerative Combinatorics (volume 1), Second Edition. Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, (2012)

    work page 2012

  20. [20]

    R. P. Stanley,Enumerative Combinatorics (volume 2), Second Edition. Cambridge Studies in Advanced Mathematics, vol. 208, Cambridge University Press, (2024)

    work page 2024

  21. [21]

    Tenenbaum,Introduction to Analytic and Probabilistic Number Theory, Cambridge Studies in Advanced Mathematics, vol

    G. Tenenbaum,Introduction to Analytic and Probabilistic Number Theory, Cambridge Studies in Advanced Mathematics, vol. 46, Cambridge University Press, (1995)

    work page 1995

  22. [22]

    Turner and Y

    P. Turner and Y. Wu, Discrete equidecomposability and Ehrhart theory of polygons, Discrete Comput. Geom.65 (2021), 90–115. 28

    work page 2021