## Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 479-505 |

Number of pages | 27 |

Journal | SIAM Journal on Applied Algebra and Geometry |

Volume | 5 |

Issue number | 3 |

DOIs | |

State | Published - 2021 |

## Keywords

- Atomic
- Isometry
- Restricted orbit computation
- Semidirect product

## ASJC Scopus subject areas

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