Abstract
In this paper we describe an algorithm for the computation of canonical forms of finite subsets of \(\mathbb {Z}^d\), up to affinities over \(\mathbb {Z}\). For fixed dimension d, this algorithm has worst-case asymptotic complexity \(O(n \log ^2 n \, s\,\mu (s))\), where n is the number of points in the given subset, s is an upper bound to the size of the binary representation of any of the n points, and \(\mu (s)\) is an upper bound to the number of operations required to multiply two s-bit numbers. In particular, the problem is fixed-parameter tractable with respect to the dimension d. This problem arises e.g. in the context of computation of invariants of finitely presented groups with abelianized group isomorphic to \(\mathbb {Z}^d\). In that context one needs to decide whether two Laurent polynomials in d indeterminates, considered as elements of the group ring over the abelianized group, are equivalent with respect to a change of basis.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alexander, J.W.: Topological invariants of knots and links. Trans. Am. Math. Soc. 30(2), 275–306 (1928)
Alt, H., Mehlhorn, K., Wagener, H., Welzl, E.: Congruence, similarity, and symmetries of geometric objects. Discrete Comput. Geom. 3(3), 237–256 (1988)
Bellettini, G., Beorchia, V., Paolini, M., Pasquarelli, F.: Shape Reconstruction from Apparent Contours: Theory and Algorithms. Computational Imaging and Vision, vol. 44. Springer, Heidelberg (2015)
Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10(4), 377–409 (1993)
Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138. Springer, Berlin (1993)
Downey, R.G., Fellows, M.R., Kapron, B.M., Hallett, M.T., Wareham, H.T.: The parameterized complexity of some problems in logic and linguistics. In: Nerode, A., Matiyasevich, Yu.V. (eds.) Logical Foundations of Computer Science (St. Petersburg, 1994). Lecture Notes in Computer Science, vol. 813, pp. 89–100. Springer, Berlin (1994)
Eick, B.: Computational group theory. Jahresber. Deutsch. Math.-Ver. 107(3), 155–170 (2015)
Fox, R.H.: Free differential calculus. I. Derivation in the free group ring. Ann. Math. 57, 547–560 (1953)
Fox, R.H.: Free differential calculus. II. The isomorphism problem of groups. Ann. Math. 59, 196–210 (1954)
Holt, D.F., Eick, B., O’Brien, E.A.: Handbook of Computational Group Theory. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton (2005)
Holt, D.F., Rees, S.: Testing for isomorphism between finitely presented groups. In: Liebeck, M.W., Saxl, J. (eds.) Groups, Combinatorics and Geometry. London Mathematical Society Lecture Note Series, vol. 165, pp. 459–475. Cambridge University Press, Cambridge (1992)
Minkowski, H.: Zur Theorie der positiven quadratischen Formen. J. Reine Angew. Math. 101, 196–202 (1887)
Newman, M.: Integral Matrices. Pure and Applied Mathematics, vol. 45. Academic Press, New York (1972)
Novikov, P.S.: On the Algorithmic Unsolvability of the Word Problem in Group Theory. Trudy Matematicheskogo Instituta imeni V.A. Steklova, vol. 44. Russian Academy of Sciences, Moscow (1955)
Rolfsen, D.: Knots and Links. AMS Chelsea Publishing Series, vol. 346. American Mathematical Society, Providence (1976)
Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7(3), 281–292 (1971)
Serre, J.-P.: Bounds for the orders of the finite subgroups of \(G(k)\). In: Geck, M., Testerman, D., Thévenaz, J. (eds.) Group Representation Theory, pp. 405–450. EPFL Press, Lausanne (2007)
Sims, C.C.: Computation with Finitely Presented Groups. Encyclopedia of Mathematics and Its Applications, vol. 48. Cambridge University Press, Cambridge (1994)
Storjohann, A.: Computing Hermite and Smith normal forms of triangular integer matrices. Linear Algebra Appl. 282(1–3), 25–45 (1998)
Storjohann, A., Labahn, G.: Asymptotically fast computation of Hermite normal forms of integer matrices. In: Lakshman, Y.N. (ed.) Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pp. 259–266. ACM, New York (1996)
Acknowledgements
I would like to thank my father Maurizio Paolini for having introduced me to the problem and for his valuable suggestions. I would also like to thank Luca Ghidelli for the useful discussions and for having carefully read this paper. Then I would like to thank professors Patrizia Gianni, Carlo Traverso and Giovanni Gaiffi for their advice. Finally I thank the referees, for the thorough revisions and for pointing out interesting references and connections.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors in Charge: Günter M. Ziegler, Kenneth Clarkson
Rights and permissions
About this article
Cite this article
Paolini, G. An Algorithm for Canonical Forms of Finite Subsets of \(\mathbb {Z}^d\) up to Affinities. Discrete Comput Geom 58, 293–312 (2017). https://doi.org/10.1007/s00454-017-9895-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-017-9895-6