The monoids of orders eight, nine & ten. (English) Zbl 1204.20075
Summary: We describe the use of symbolic algebraic computation allied with AI search techniques, applied to the problem of the identification, enumeration and storage of all monoids of order ten or less. Our approach is novel, using computer algebra to break symmetry and constraint satisfaction search to find candidate solutions. We present new results in algebraic combinatorics: up to isomorphism and anti-isomorphism, there are 858,977 monoids of order eight; 1,844,075,697 monoids of order nine and 52,991,253,973,742 monoids of order ten.
MSC:
| 20M10 | General structure theory for semigroups |
| 68W30 | Symbolic computation and algebraic computation |
| 05E15 | Combinatorial aspects of groups and algebras (MSC2010) |
| 20-04 | Software, source code, etc. for problems pertaining to group theory |
Keywords:
classification of finite semigroups; nilpotent semigroups; multiplication tables of semigroups; computer algebra; constraint satisfaction; GAPOnline Encyclopedia of Integer Sequences:
Number of monoids (semigroups with identity) of order n, considered to be equivalent when they are isomorphic or anti-isomorphic (by reversal of the operator).Number of nonequivalent monoids of order n with more than one invertible element
Number of nonequivalent monoids of order n in which the action of the unit group on the maximal ideal is nontrivial.
References:
| [1] | Sloane, N.J.A.: The on-line encyclopedia of integer sequences. http://www.research.att.com/\(\sim\)njas/sequences/Seis.html (2008) · Zbl 1274.11001 |
| [2] | Distler, A., Kelsey, T.: The monoids of order eight and nine. In: Autexier, S., Campbell, J., Rubio, J., Sorge, V., Suzuki, M., Wiedijk, F. (eds.) Intelligent Computer Mathematics, 9th International Conference, AISC 2008, Proceedings. Lecture Notes in Artificial Intelligence, vol. 5144, pp. 61–76. Springer, New York (2008) |
| [3] | The GAP Group: GAP–Groups, Algorithms, and Programming, version 4.4.10 (2007) |
| [4] | Linton, S.: Finding the smallest image of a set. In: ISSAC ’04: Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, pp. 229–234. ACM, New York (2004) · Zbl 1134.05302 |
| [5] | Gent, I.P., Jefferson, C., Miguel, I.: Minion: a fast scalable constraint solver. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) ECAI, pp. 98–102. IOS, Amsterdam (2006) |
| [6] | Cohen, D.A., Jeavons, P., Jefferson, C., Petrie, K.E., Smith, B.M.: Symmetry definitions for constraint satisfaction problems. Constraints 11(2–3), 115–137 (2006) · Zbl 1103.68809 · doi:10.1007/s10601-006-8059-8 |
| [7] | Crawford, J.M., Ginsberg, M.L., Luks, E.M., Roy, A.: Symmetry-breaking predicates for search problems. In: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, pp. 148–159 (1996) |
| [8] | Grillet, P.: Semigroups: An Introduction to the Structure Theory. Marcel Dekker, New York (1995) · Zbl 0830.20079 |
| [9] | Plemmons, R.J.: There are 15973 semigroups of order 6. Math. Algorithms 2, 2–17 (1967) |
| [10] | Satoh, S., Yama, K., Tokizawa, M.: Semigroups of order 8. Semigroup Forum 49, 7–29 (1994) · Zbl 0917.20049 · doi:10.1007/BF02573467 |
| [11] | Harary, F., Palmer, E.M.: Graphical Enumeration. Academic, New York (1973) · Zbl 0266.05108 |
| [12] | Distler, A., Mitchell, J.D.: smallsemi – a GAP package. http://turnbull.mcs.st-and.ac.uk/\(\sim\)jamesm/smallsemi/ (2008) |
| [13] | Jefferson, C., Kelsey, T., Linton, S., Petrie, K.: Gaplex: generalised static symmetry breaking. In: Benhamou, F., Jussien, N., O’Sullivan, B. (eds.) Trends in Constraint Programming. ISTE, pp. 191–205 (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
