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 Zn and compute isometry-subgroup-induced partitions as orbit computations under various isometry-subgroup actions on Zn. 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 Zn, to a finite subset, i.e., a partition of Z \subseteq Zn. However, not only is the orbit relation still defined on the entire Zn, 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 Zn. Therefore, this algorithmic efficiency is application-independent.

Original languageEnglish (US)
Pages (from-to)479-505
Number of pages27
JournalSIAM Journal on Applied Algebra and Geometry
Issue number3
StatePublished - 2021


  • Atomic
  • Isometry
  • Restricted orbit computation
  • Semidirect product

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Applied Mathematics


Dive into the research topics of 'Orbit Computation for Atomically Generated Subgroups of Isometries of Z'. Together they form a unique fingerprint.

Cite this