Incremental SAT-Based Enumeration of Solutions to the Yang-Baxter Equation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915272171978752 |
|---|---|
| author | Van Caudenberg, Daimy Bogaerts, Bart Vendramin, Leandro |
| author_facet | Van Caudenberg, Daimy Bogaerts, Bart Vendramin, Leandro |
| contents | We tackle the problem of enumerating set-theoretic solutions to the Yang-Baxter equation. This equation originates from statistical and quantum mechanics, but also has applications in knot theory, cryptography, quantum computation and group theory. Non-degenerate, involutive solutions have been enumerated for sets up to size 10 using constraint programming with partial static symmetry breaking; for general non-involutive solutions, a similar approach was used to enumerate solutions for sets up to size 8. In this paper, we use and extend the SAT Modulo Symmetries framework (SMS), to expand the boundaries for which solutions are known. The SMS framework relies on a minimality check; we present two solutions to this, one that stays close to the original one designed for enumerating graphs and a new incremental, SAT-based approach. With our new method, we can reproduce previously known results much faster and also report on results for sizes that have remained out of reach so far. This is an extended version of a paper to appear in the proceedings of the 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14363 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Incremental SAT-Based Enumeration of Solutions to the Yang-Baxter Equation Van Caudenberg, Daimy Bogaerts, Bart Vendramin, Leandro Logic in Computer Science Discrete Mathematics We tackle the problem of enumerating set-theoretic solutions to the Yang-Baxter equation. This equation originates from statistical and quantum mechanics, but also has applications in knot theory, cryptography, quantum computation and group theory. Non-degenerate, involutive solutions have been enumerated for sets up to size 10 using constraint programming with partial static symmetry breaking; for general non-involutive solutions, a similar approach was used to enumerate solutions for sets up to size 8. In this paper, we use and extend the SAT Modulo Symmetries framework (SMS), to expand the boundaries for which solutions are known. The SMS framework relies on a minimality check; we present two solutions to this, one that stays close to the original one designed for enumerating graphs and a new incremental, SAT-based approach. With our new method, we can reproduce previously known results much faster and also report on results for sizes that have remained out of reach so far. This is an extended version of a paper to appear in the proceedings of the 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems. |
| title | Incremental SAT-Based Enumeration of Solutions to the Yang-Baxter Equation |
| topic | Logic in Computer Science Discrete Mathematics |
| url | https://arxiv.org/abs/2501.14363 |