On the Unimodular Isomorphism Problem of Convex Lattice Polytopes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908428262178816 |
|---|---|
| author | Liu, Qiuyue Cai, Zhanyuan |
| author_facet | Liu, Qiuyue Cai, Zhanyuan |
| contents | This paper studies the \emph{unimodular isomorphism problem} (UIP) of convex lattice polytopes: given two convex lattice polytopes $P$ and $P'$, decide whether there exists a unimodular affine transformation mapping $P$ to $P'$. We show that UIP is graph isomorphism hard, while the polytope congruence problem and the combinatorial polytope isomorphism problem (Akutsu, 1998; Kaibel, Schwartz, 2003) were shown to be graph isomorphism complete, and both the lattice isomorphism problem ( $\mathrm{Sikiri\acute{c}}$, $\mathrm{Sch\ddot{u}rmann}$, Vallentin, 2009) and the projective/affine polytope isomorphism problem (Kaibel, Schwartz, 2003) were shown to be graph isomorphism hard. Furthermore, inspired by protocols for lattice (non-) isomorphism (Ducas, van Woerden, 2022; Haviv, Regev, 2014), we present a statistical zero-knowledge proof system for unimodular isomorphism of lattice polytopes. Finally, we propose an algorithm that given two lattice polytopes computes all unimodular affine transformations mapping one polytope to another and, in particular, decides UIP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23846 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Unimodular Isomorphism Problem of Convex Lattice Polytopes Liu, Qiuyue Cai, Zhanyuan Metric Geometry This paper studies the \emph{unimodular isomorphism problem} (UIP) of convex lattice polytopes: given two convex lattice polytopes $P$ and $P'$, decide whether there exists a unimodular affine transformation mapping $P$ to $P'$. We show that UIP is graph isomorphism hard, while the polytope congruence problem and the combinatorial polytope isomorphism problem (Akutsu, 1998; Kaibel, Schwartz, 2003) were shown to be graph isomorphism complete, and both the lattice isomorphism problem ( $\mathrm{Sikiri\acute{c}}$, $\mathrm{Sch\ddot{u}rmann}$, Vallentin, 2009) and the projective/affine polytope isomorphism problem (Kaibel, Schwartz, 2003) were shown to be graph isomorphism hard. Furthermore, inspired by protocols for lattice (non-) isomorphism (Ducas, van Woerden, 2022; Haviv, Regev, 2014), we present a statistical zero-knowledge proof system for unimodular isomorphism of lattice polytopes. Finally, we propose an algorithm that given two lattice polytopes computes all unimodular affine transformations mapping one polytope to another and, in particular, decides UIP. |
| title | On the Unimodular Isomorphism Problem of Convex Lattice Polytopes |
| topic | Metric Geometry |
| url | https://arxiv.org/abs/2506.23846 |