Unimodular Equivalence of Integral Simplices

Feihu Liu, Sihao Tao, Guoce Xin, [2mm] School of Mathematical Sciences, [-0.8ex] Capital Normal University, Beijing, 100048, P.R. China, Email address: [email protected], Email address: [email protected], Email address: [email protected] · 2026

Read Unimodular Equivalence of Integral Simplices by Feihu Liu, Sihao Tao, Guoce Xin, [2mm] School of Mathematical Sciences, [-0.8ex] Capital Normal University, Beijing, 100048, P.R. China, Email address: [email protected], Email address: [email protected], Email address: [email protected] (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-2601-06819.txt.

Introduction

Feihu Liu and co-authors posted a 2026 arXiv preprint. The preprint deals with unimodular equivalence of integral simplices. It came out on arXiv in 2026 as a PAPERS preprint. China, Testing the unimodular equivalence of two full-dimensional integral simplices can be reduced to testing unimodular permutation (UP) equivalence of two nonsingular matrices. Readers in the field get a short, focused account of the problem and the steps the authors take.

Catalog record

CREATORFeihu Liu, Sihao Tao, Guoce Xin, [2mm] School of Mathematical Sciences, [-0.8ex] Capital Normal University, Beijing, 100048, P.R. China, Email address: [email protected], Email address: [email protected], Email address: [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-06819

Browse the full library · About the Tower of Babel

Full text

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

Unimodular Equivalence of Integral Simplices Feihu Liu, Sihao Tao, Guoce Xin, [2mm] School of Mathematical Sciences, [-0.8ex] Capital Normal University, Beijing, 100048, P.R. China, Email address: [email protected], Email address: [email protected], Email address: [email protected] 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 HEM , for deciding the unimodular equivalence of d d -dimensional integral simplices, as well as achieving a polynomial-time complexity with a failure probability less than 2.5 × 10 − 7 2.5\times 10^{-7} . A key ingredient is the introduction of the permuted Hermite normal form and its associated 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 n -dimensional pyramids are unimodularly equivalent. This resolves an open question posed by Abney-McPeek et al. 2020 Mathematics subject classification : Primary 52B11; Secondary 52B05; 52B20; 68R05. Keywords : Ehrhart theory; Integral simplex; Unimodularly equivalent; Hermite normal form; Smith normal form. Contents 1 Introduction This paper presents the first practical algorithm for testing the unimodular equivalence of full-dimensional integral simplices that run in quasi-polynomial time on average and in provable polynomial time with failure probability less than 2.5\times 10^{-7} . We first introduce some basic concepts, then present our two major contributions. 1.1 Basic concepts Let \mathcal{P} be a full-dimensional polytope in \mathbb{R}^{d} . Ehrhart theory [ 6 ] studies the function counting the number of integer lattice points in the n -th dilation of \mathcal{P} , defined as \mathrm{ehr}(\mathcal{P},n)=|n\mathcal{P}\cap\mathbb{Z}^{d}|,\ \ \ \ \ n=1,2,\ldots, where n\mathcal{P}:=\{n\alpha:\alpha\in\mathcal{P}\} . A polytope \mathcal{P} is called an integral polytope if its vertices have integer coordinates, and a rational polytope if its vertices lie in \mathbb{Q}^{d} . For a rational polytope \mathcal{P} , the denominator of \mathcal{P} is the smallest positive integer k such that k\mathcal{P} is an integral polytope. Ehrhart theory has attracted considerable attention, yielding many results concerning the function \mathrm{ehr}(\mathcal{P},n) ; we refer the reader to [ 3 ] and [ 19 , Chapter 4] . A fundamental result [ 6 ] states that for any rational polytope \mathcal{P} with denominator k , the function \mathrm{ehr}(\mathcal{P},n) is a quasi-polynomial in n of period k . This means \mathrm{ehr}(\mathcal{P},n)=c_{d}(n)n^{d}+\cdots+c_{1}(n)n+c_{0}(n), where each c_{i}(n) is a periodic function with period dividing k , and c_{d}(n) is not identically zero. This quasi-polynomial is the Ehrhart quasi-polynomial of \mathcal{P} . When \mathcal{P} is integral, \mathrm{ehr}(\mathcal{P},n) is a polynomial of degree d , called the Ehrhart polynomial of \mathcal{P} . We now recall key definitions, following [ 22 ] (see also [ 11 , 9 ] ). Definition 1.1 . Two rational polytopes \mathcal{P},\mathcal{Q}\subseteq\mathbb{R}^{d} are Ehrhart-equivalent if \mathrm{ehr}(\mathcal{P},n)=\mathrm{ehr}(\mathcal{Q},n) for all positive integers n ; equivalently, \mathcal{P} and \mathcal{Q} share the same Ehrhart quasi-polynomial. Definition 1.2 . An affine unimodular transformation U:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d} is a map of the form U(\mathbf{x})=A\mathbf{x}+\mathbf{b},\ \ \mathbf{x}\in\mathbb{R}^{d}, where A\in\mathrm{GL}_{d}(\mathbb{Z}) (the group of integer d\times d matrices with determinant \pm 1 ) and \mathbf{b}\in\mathbb{Z}^{d} . The set of such transformations is denoted \mathrm{GL}_{d}(\mathbb{Z})\ltimes\mathbb{Z}^{d} . Definition 1.3 . Two rational polytopes \mathcal{P},\mathcal{Q}\subseteq\mathbb{R}^{d} are unimodularly equivalent if there exists an affine unimodular transformation U\in\mathrm{GL}_{d}(\mathbb{Z})\ltimes\mathbb{Z}^{d} satisfying U(\mathcal{P})=\mathcal{Q} . A set S\in\mathbb{R}^{d} is called relatively open if it is open inside its affine span [ 8 ] . Definition 1.4 . Two rational polytopes \mathcal{P},\mathcal{Q}\subseteq\mathbb{R}^{d} are \mathrm{GL}_{d}(\mathbb{Z}) -equidecomposable if there exist relatively open simplices \mathcal{P}_{1},\ldots,\mathcal{P}_{r} and unimodular transformations U_{1},\ldots,U_{r}\in\mathrm{GL}_{d}(\mathbb{Z})\ltimes\mathbb{Z}^{d} such that \displaystyle\mathcal{P}=\bigsqcup_{i=1}^{r}\mathcal{P}_{i}\quad\text{and}\quad\mathcal{Q}=\bigsqcup_{i=1}^{r}U_{i}(\mathcal{P}_{i}), where \bigsqcup denotes disjoint union. Unimodular equivalence implies both Ehrhart equivalence and \mathrm{GL}_{d}(\mathbb{Z}) -equidecomposability, and it plays a central role in Ehrhart theory. Motivated by the work of Kaibel and Schwartz [ 12 ] and Abney-McPeek et al. [ 1 ] , we investigate algorithms for determining unimodular equivalence between full-dimensional integral simplices. The significance of developing such algorithms is highlighted in [ 10 , Problem 2] and [ 12 ] . Similarly, the algorithmic problem of testing affine equivalence for polytopes is considered a fundamental problem [ 13 , Section 4: Problems 19–23] . Problem 1.5 . ( [ 10 , Problem 2] : Unimodular Equivalence Checking) Given simplices \mathcal{P} and \mathcal{Q} , determine whether \mathcal{P} and \mathcal{Q} are unimodularly equivalent. To the best of our knowledge, three algorithms are currently known for unimodular equivalence checking: 1. Kaibel and Schwartz [ 12 , Proposition 4] provide an algorithm for full-dimensional simplicial polytopes with complexity \mathcal{O}(d!\cdot d^{2}\cdot m^{2}) , where m denotes the number of facets (which reduces to d+1 for simplices). 2. Gribanov [ 10 , Theorem 2] presents an algorithm for two integral \Delta -modular (not necessarily full-dimensional) simplices (defined in Section 3.1) with complexity d^{\log_{2}\Delta}\cdot\Delta!\cdot\mathrm{poly}(d,\Delta) . 3. Abney-Mcpeek et. al. [ 1 ] developed VPEC (Algorithm 3.3 ), which achieves complexity \mathcal{O}((d+1)!\cdot(d+1)^{3}) . For a full-dimensional integral d -simplex \mathcal{P}=\text{conv}(\{\mathbf{v}_{0},\mathbf{v}_{1},\dots,\mathbf{v}_{d}\}) with vertices \mathbf{v}_{i}\in\mathbb{Z}^{d} , the lattice volume (also called normalized volume ) is defined as \text{vol}_{\mathbb{Z}}(\mathcal{P})=\left|\det\left(\mathbf{v}_{1}-\mathbf{v}_{0}|\mathbf{v}_{2}-\mathbf{v}_{0}|\dots|\mathbf{v}_{d}-\mathbf{v}_{0}\right)\right|. Notably, the lattice volume is invariant under unimodular transformations, which is a basic property for characterizing the unimodular equivalence of integral simplices. 1.2 Two major contributions Contribution 1: The HEM algorithm for unimodular permutation (UP) equivalence. Existing algorithms for testing unimodular equivalence of integral simplices [ 12 , 10 , 1 ] exhibit a worst-case complexity factor of d! . Our HEM (Hermite Normal Form-Based Equivalence Method) algorithm overcomes this barrier by leveraging the Hermite normal form of integer matrices. Theorem 1.6 . Let \mathcal{P}=\mathrm{conv}(A) and \mathcal{Q}=\mathrm{conv}(B) be full-dimensional integral simplices in \mathbb{R}^{d} with identical lattice volume v , where A,B\in\mathbb{Z}^{d\times(d+1)} are integer matrices whose columns represent the vertices. Then HEM decides the unimodular equivalence of \mathcal{P} and \mathcal{Q} • deterministically in time \mathcal{O}((d+1)!\,(d+1)^{3}) , • probabilistically in time \mathcal{O}((d+1)^{6}\log^{2}v) with failure probability less than 2.5\times 10^{-7} , • and in average time \mathcal{O}((d+1)^{\log(d+1)}\log^{2}v) . The HEM algorithm introduces two key innovations: the permuted Hermite normal form and associated pattern groups within the symmetric group \mathfrak{S}_{n} . The core idea simplifies the UP-equivalence test by comparing canonical representatives derived from the coset decomposition induced by these pattern groups. Contribution 2: A dimension-free resolution to Abney-McPeek et al.’s open problem. For 2 -dimensional integral simplices \mathcal{P} and \mathcal{Q} , Abney-McPeek et al. established that \mathcal{P} and \mathcal{Q} are unimodularly equivalent if and only if their pyramids are unimodularly equivalent. They subsequently posed the following open problem [ 1 , Section 5] : Does this equivalence extend to 3 -dimensional and arbitrary d -dimensional simplices? We provide an affirmative answer to this question in Theorem 2.10 ; the proof is technical. The paper is organized as follows. Section 2 we introduce some equivalence relations on matrices and establish that two full-dimensional integral simplices are unimodularly equivalent if and only if their n -dimensional pyramids are unimodularly equivalent. This result provides an affirmative answer to the question posed by Abney-Mcpeek et al. Subsection 3.1 analyzes the computational complexity of the three known algorithms for detecting unimodular equivalence between simplices. Subsection 3.2 introduces our proposed algorithm HEM . Section 4 presents a

Read the complete text