Orbit Computation for Atomically Generated Subgroups of Isometries of Z

Partitions of a set play an important role in automatic knowledge discovery algorithms that learn human-like concepts from human-like innate priors. One such type of prior is isometries, the recognition of which is considered a part of innate human cognitive ability. In this paper, we consider isometries of Zⁿ and compute isometry-subgroup-induced partitions as orbit computations under various isometry-subgroup actions on Zⁿ. For both computational (to avoid infinity) and practical (to consider an application domain) reasons, we restrict the set of orbits, i.e., a partition of Zⁿ, to a finite subset, i.e., a partition of Z \subseteq Zⁿ. However, not only is the orbit relation still defined on the entire Zⁿ, but the algorithm has no control over Z which is specified a priori by an application or a data set. Our main contribution is an efficient algorithm solving this restricted orbit-computation problem exactly, in the special case of atomically generated subgroups-a new notion motivated from building human-like artificial intelligence. Technically, the atomic property is key to preserving the semidirect-product structure-the core structure we leverage to make our algorithm outperform generic approaches. Besides algorithmic merit, our approach enables parallel-computing implementations in many subroutines, which can further benefit from hardware boosts. Moreover, our algorithm works efficiently for any finite subset Z regardless of its shape or its location in Zⁿ. Therefore, this algorithmic efficiency is application-independent.