Introduction
In automated reasoning and finite model finding, the "symmetry explosion" problem presents a significant hurdle. When searching for mathematical structures of a fixed size $n$, such as groups or semigroups, solvers often encounter millions of isomorphic copies—structures that are identical except for the labeling of their elements. This redundancy drastically increases the search space and computational cost. This paper, presented at AAAI-25, introduces a novel SAT-based technique to achieve complete symmetry breaking, ensuring that only a single unique representative of each structure is considered.
The Symmetry Challenge
For a domain of size $n$, there are $n!$ possible permutations of elements. Traditional "partial" symmetry breaking methods reduce redundancy but do not eliminate it entirely. "Complete" symmetry breaking, while theoretically ideal, has historically been viewed as impractical due to the super-exponential growth of required constraints. The authors address this by developing a method to generate compact sets of constraints that still guarantee completeness.
Methodology: Canonizing Sets and SAT Encoding
The researchers employ a "constrain and generate" approach centered on lexicographical ordering (lex-leader constraints). A structure is defined as a lex-leader if its multiplication table is the smallest possible version across all permutations.
Canonizing Sets
Instead of utilizing all $n!$ permutations, the authors propose an incremental algorithm to identify a "canonizing set"—a minimal subset of permutations sufficient to break all symmetries for a given class of structures.
As shown in the figure above, the size of these canonizing sets remains remarkably small compared to the theoretical maximum of $n!-1$, particularly for structures with more inherent algebraic properties. For instance, groups of size 10 required only 18 permutations for a complete break.
Vectorization Strategies
The efficiency of the SAT encoding depends on how the 2D multiplication table is flattened into a 1D vector for comparison. The authors compared a standard "row-by-row" approach with a "diagonal-first" strategy.
Empirical results indicate that diagonal vectorization consistently yields smaller canonizing sets and faster solving times. This "diagonal advantage" likely stems from the fact that diagonal elements often provide more immediate information for symmetry breaking in many algebraic structures.
Empirical Results and New Mathematical Data
By integrating these compact symmetry breaks with the d4 model counter, the authors successfully enumerated non-isomorphic structures that were previously beyond reach. Key findings include:
- AG-groupoids: The study determined there are exactly 643,460,323,187 non-isomorphic AG-groupoids of size 7. Previous efforts had only reached size 6.
- Implication Zroupoids: For $n=7$, the count was found to be approximately 600 trillion, a result previously undocumented in mathematical literature.
- Efficiency in Groups: For groups of size 10, the system completed the count in just 149 seconds.
Conclusion
This research demonstrates that complete symmetry breaking is not only theoretically possible but practically feasible through compact canonizing sets and optimized SAT encodings. While computational limits are still encountered around $n=10$ for less-structured magmas, the method provides a powerful tool for mathematical discovery and the verification of sequences in the Online Encyclopedia of Integer Sequences (OEIS). Future work will explore extending the framework to multi-functional structures and further investigating the theoretical underpinnings of the diagonal vectorization advantage.
Summary updated