An Algorithm for Canonical Forms of Finite Subsets of Zd up to Affinities

In this paper we describe an algorithm for the computation of canonical forms of finite subsets of Zd, up to affinities over Z. For fixed dimension d, this algorithm has worst-case asymptotic complexity O(nlog2nsμ(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 μ(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 Zd. 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.