Recursive Reduction of Multiplication Tables

Abstract

Motivated by the problem of enumerating finite transformation semigroups here we present a recursive algorithm for systematic reduction of multiplication tables. We can downsize the hopelessly huge search space even if we do not exploit properties of the underlying algebra. By considering the elements appearing in the diagonal of the table we can define a closure operator on the cuts. This technique can be used for any algebraic structure with one multiplication operation. When considering transformation semigroups in particular, the automorphism group can be used to find new complete cuts. For a computational implementation, permutation groups provide convenient test cases for the algorithm since for groups the number of subgroups and conjugacy classes are easy to calculate.