| Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/semigroups/libsemigroups/src/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 18.5.2025 mit Größe 72 kB |
|
Quelle fpsemi-examples.cpp Sprache: C |
|||||||||
|
//
// libsemigroups - C++ library for semigroups and monoids // Copyright (C) 2022 Murray T. Whyte // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // // This file contains some implementations of functions that produce fp // semigroups for testing purposes. #include "libsemigroups/fpsemi-examples.hpp" #include <algorithm> // for max, for_each #include <cstdint> // for int64_t #include <cstdlib> // for abs #include <numeric> // for iota #include "libsemigroups/exception.hpp" // for LIBSEMIGROUPS_EXCEPTION #include "libsemigroups/types.hpp" // for word_type, relation_type namespace libsemigroups { namespace { template <typename T> std::vector<T> concat(std::vector<T> lhs, const std::vector<T>& rhs) { lhs.insert(lhs.end(), rhs.begin(), rhs.end()); return lhs; } std::vector<size_t> max_elt_B(size_t i) { std::vector<size_t> t(0); for (int end = i; end >= 0; end--) { for (int k = 0; k <= end; k++) { t.push_back(k); } } return t; } std::vector<size_t> max_elt_D(size_t i, int g) { // g est 0 ou 1 : 0 pour f et 1 pour e std::vector<size_t> t(0); int parity = g; for (int end = i; end > 0; end--) { t.push_back(parity); for (int k = 2; k <= end; k++) { t.push_back(k); } parity = (parity + 1) % 2; } return t; } word_type operator^(word_type const& w, size_t exp) { word_type result; for (size_t i = 0; i < exp; ++i) { result.insert(result.end(), w.cbegin(), w.cend()); } return result; } word_type operator*(word_type const& lhs, word_type const& rhs) { word_type result(lhs); result.insert(result.end(), rhs.cbegin(), rhs.cend()); return result; } void add_monoid_relations(std::vector<word_type> const& alphabet, word_type id, std::vector<relation_type>& relations) { for (size_t i = 0; i < alphabet.size(); ++i) { if (alphabet[i] != id) { relations.emplace_back(alphabet[i] * id, alphabet[i]); relations.emplace_back(id * alphabet[i], alphabet[i]); } else { relations.emplace_back(id * id, id); } } } void add_full_transformation_monoid_relations(std::vector<relation_type>& result, size_t n, size_t pi_start, size_t e12_value) { // This function adds the full transformation monoid relations due to // Iwahori, from Section 9.3, p161-162, (Ganyushkin + Mazorchuk), // expressed in terms of the generating set {pi_2, ..., pi_n, // epsilon_{12}} using the notation of that chapter. // https://link.springer.com/book/10.1007/978-1-84800-281-4 // The argument n specifies the degree of the full transformation monoid. // The generators corresponding to the pi_i will always constitute n - 2 // consecutive integers, starting from the argument pi_start. The argument // m specifies the value which will represent the idempotent e12. // When adding these relations for the full transformation // monoid presentation (Iwahori) in this file, we want e12_value = n - 1. // For the partial transformation monoid presentation, we want e12_value = // n. if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be at least 4, found %llu", uint64_t(n)); } if (e12_value >= pi_start && e12_value <= pi_start + n - 2) { LIBSEMIGROUPS_EXCEPTION("e12 must not lie in the range [pi_start, " "pi_start + n - 2], found %llu", uint64_t(e12_value)); } word_type e12 = {e12_value}; std::vector<word_type> pi; for (size_t i = pi_start; i <= pi_start + n - 2; ++i) { pi.push_back({i}); } // The following expresses the epsilon idempotents in terms of the // generating set auto eps = [&e12, &pi](size_t i, size_t j) -> word_type { LIBSEMIGROUPS_ASSERT(i != j); if (i == 1 && j == 2) { return e12; } else if (i == 2 && j == 1) { return pi[0] * e12 * pi[0]; } else if (i == 1) { return pi[0] * pi[j - 2] * pi[0] * e12 * pi[0] * pi[j - 2] * pi[0]; } else if (j == 2) { return pi[i - 2] * e12 * pi[i - 2]; } else if (j == 1) { return pi[0] * pi[i - 2] * e12 * pi[i - 2] * pi[0]; } else if (i == 2) { return pi[j - 2] * pi[0] * e12 * pi[0] * pi[j - 2]; } return pi[i - 2] * pi[0] * pi[j - 2] * pi[0] * e12 * pi[0] * pi[j - 2] * pi[0] * pi[i - 2]; }; auto transp = [&pi](size_t i, size_t j) -> word_type { LIBSEMIGROUPS_ASSERT(i != j); if (i > j) { std::swap(i, j); } if (i == 1) { return pi[j - 2]; } return pi[i - 2] * pi[j - 2] * pi[i - 2]; }; // Relations a for (size_t i = 1; i <= n; ++i) { for (size_t j = 1; j <= n; ++j) { if (j == i) { continue; } // Relations (k) result.emplace_back(transp(i, j) * eps(i, j), eps(i, j)); // Relations (j) result.emplace_back(eps(j, i) * eps(i, j), eps(i, j)); // Relations (i) result.emplace_back(eps(i, j) * eps(i, j), eps(i, j)); // Relations (d) result.emplace_back(transp(i, j) * eps(i, j) * transp(i, j), eps(j, i)); for (size_t k = 1; k <= n; ++k) { if (k == i || k == j) { continue; } // Relations (h) result.emplace_back(eps(k, j) * eps(i, j), eps(k, j)); // Relations (g) result.emplace_back(eps(k, i) * eps(i, j), transp(i, j) * eps(k, j)); // Relations (f) result.emplace_back(eps(j, k) * eps(i, j), eps(i, j) * eps(i, k)); result.emplace_back(eps(j, k) * eps(i, j), eps(i, k) * eps(i, j)); // Relations (c) result.emplace_back(transp(k, i) * eps(i, j) * transp(k, i), eps(k, j)); // Relations (b) result.emplace_back(transp(j, k) * eps(i, j) * transp(j, k), eps(i, k)); for (size_t l = 1; l <= n; ++l) { if (l == i || l == j || l == k) { continue; } // Relations (e) result.emplace_back(eps(l, k) * eps(i, j), eps(i, j) * eps(l, k)); // Relations (a) result.emplace_back(transp(k, l) * eps(i, j) * transp(k, l), eps(i, j)); } } } } } } // namespace namespace fpsemigroup { std::vector<relation_type> stellar_monoid(size_t l) { if (l < 2) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 2, found %llu", uint64_t(l)); } std::vector<size_t> pi; for (size_t i = 0; i < l; ++i) { pi.push_back(i); // 0 est \pi_0 } std::vector<relation_type> rels{}; std::vector<size_t> t{pi[0]}; for (int i = 1; i < static_cast<int>(l); ++i) { t.insert(t.begin(), pi[i]); rels.push_back({concat(t, {pi[i]}), t}); } return rels; } std::vector<relation_type> fibonacci_semigroup(size_t r, size_t n) { if (n == 0) { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be strictly positive, found %llu", uint64_t(n)); } if (r == 0) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be strictly positive, found %llu", uint64_t(r)); } std::vector<relation_type> result; for (size_t i = 0; i < n; ++i) { word_type lhs(r, 0); std::iota(lhs.begin(), lhs.end(), i); std::for_each(lhs.begin(), lhs.end(), [&n](size_t& x) { x %= n; }); result.emplace_back(lhs, word_type({(i + r) % n})); } return result; } std::vector<relation_type> plactic_monoid(size_t n) { if (n < 2) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 2, found %llu", uint64_t(n)); } std::vector<relation_type> result; for (size_t c = 0; c < n; ++c) { for (size_t b = 0; b < c; ++b) { for (size_t a = 0; a < b; ++a) { result.emplace_back(word_type({b, a, c}), word_type({b, c, a})); result.emplace_back(word_type({a, c, b}), word_type({c, a, b})); } } } for (size_t b = 0; b < n; ++b) { for (size_t a = 0; a < b; ++a) { result.emplace_back(word_type({b, a, a}), word_type({a, b, a})); result.emplace_back(word_type({b, b, a}), word_type({b, a, b})); } } return result; } std::vector<relation_type> stylic_monoid(size_t n) { if (n < 2) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 2, found %llu", uint64_t(n)); } std::vector<relation_type> result = plactic_monoid(n); for (size_t a = 0; a < n; ++a) { result.emplace_back(word_type({a, a}), word_type({a})); } return result; } std::vector<relation_type> symmetric_group(size_t n, author val, size_t index) { if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be at least 4, found %llu", uint64_t(n)); } if (val == author::Carmichael) { if (index != 0) { LIBSEMIGROUPS_EXCEPTION("expected 3rd argument to be 0 when 2nd " "argument is author::Carmichael, found %llu", uint64_t(index)); } // Exercise 9.5.2, p172 of // https://link.springer.com/book/10.1007/978-1-84800-281-4 std::vector<word_type> pi; for (size_t i = 0; i <= n - 2; ++i) { pi.push_back({i}); } std::vector<relation_type> result; for (size_t i = 0; i <= n - 2; ++i) { result.emplace_back(pi[i] ^ 2, word_type({})); } for (size_t i = 0; i < n - 2; ++i) { result.emplace_back((pi[i] * pi[i + 1]) ^ 3, word_type({})); } result.emplace_back((pi[n - 2] * pi[0]) ^ 3, word_type({})); for (size_t i = 0; i < n - 2; ++i) { for (size_t j = 0; j < i; ++j) { result.emplace_back((pi[i] * pi[i + 1] * pi[i] * pi[j]) ^ 2, word_type({})); } for (size_t j = i + 2; j <= n - 2; ++j) { result.emplace_back((pi[i] * pi[i + 1] * pi[i] * pi[j]) ^ 2, word_type({})); } } for (size_t j = 1; j < n - 2; ++j) { result.emplace_back((pi[n - 2] * pi[0] * pi[n - 2] * pi[j]) ^ 2, word_type({})); } return result; } else if (val == author::Coxeter + author::Moser) { // From Chapter 3, Proposition 1.2 in https://bit.ly/3R5ZpKW (Ruskuc // thesis) if (index != 0) { LIBSEMIGROUPS_EXCEPTION( "expected 3rd argument to be 0 when 2nd argument is " "author::Coxeter + author::Moser, found %llu", uint64_t(index)); } std::vector<word_type> a; for (size_t i = 0; i < n - 1; ++i) { a.push_back({i}); } std::vector<relation_type> result; for (size_t i = 0; i < n - 1; i++) { result.emplace_back(a[i] ^ 2, word_type({})); } for (size_t j = 0; j < n - 2; ++j) { result.emplace_back((a[j] * a[j + 1]) ^ 3, word_type({})); } for (size_t l = 2; l < n - 1; ++l) { for (size_t k = 0; k <= l - 2; ++k) { result.emplace_back((a[k] * a[l]) ^ 2, word_type({})); } } return result; } else if (val == author::Moore) { if (index == 0) { // From Chapter 3, Proposition 1.1 in https://bit.ly/3R5ZpKW (Ruskuc // thesis) word_type const e = {}; word_type const a = {0}; word_type const b = {1}; std::vector<relation_type> result; result.emplace_back(a ^ 2, e); result.emplace_back(b ^ n, e); result.emplace_back((a * b) ^ (n - 1), e); result.emplace_back((a * (b ^ (n - 1)) * a * b) ^ 3, e); for (size_t j = 2; j <= n - 2; ++j) { result.emplace_back((a * ((b ^ (n - 1)) ^ j) * a * (b ^ j)) ^ 2, e); } return result; } else if (index == 1) { // From https://core.ac.uk/download/pdf/82378951.pdf // TODO: Get proper DOI of this paper std::vector<relation_type> result; std::vector<word_type> s; for (size_t i = 0; i <= n - 2; ++i) { s.push_back({i}); } for (size_t i = 0; i <= n - 2; ++i) { result.emplace_back(s[i] ^ 2, word_type({})); } for (size_t i = 0; i <= n - 4; ++i) { for (size_t j = i + 2; j <= n - 2; ++j) { result.emplace_back(s[i] * s[j], s[j] * s[i]); } } for (size_t i = 1; i <= n - 2; ++i) { result.emplace_back(s[i] * s[i - 1] * s[i], s[i - 1] * s[i] * s[i - 1]); } return result; } LIBSEMIGROUPS_EXCEPTION("expected 3rd argument to be 0 or 1 when 2nd " "argument is author::Moore, found %llu", uint64_t(index)); } else if (val == author::Burnside + author::Miller) { // See Eq 2.6 of 'Presentations of finite simple groups: A quantitative // approach' J. Amer. Math. Soc. 21 (2008), 711-774 if (index != 0) { LIBSEMIGROUPS_EXCEPTION( "expected 3rd argument to be 0 when 2nd argument is " "author::Burnside + author::Miller, found %llu", uint64_t(index)); } std::vector<word_type> a; for (size_t i = 0; i <= n - 2; ++i) { a.push_back({i}); } std::vector<relation_type> result; for (size_t i = 0; i <= n - 2; ++i) { result.emplace_back(a[i] ^ 2, word_type({})); } for (size_t i = 0; i <= n - 2; ++i) { for (size_t j = 0; j <= n - 2; ++j) { if (i == j) { continue; } result.emplace_back((a[i] * a[j]) ^ 3, word_type({})); } } for (size_t i = 0; i <= n - 2; ++i) { for (size_t j = 0; j <= n - 2; ++j) { if (i == j) { continue; } for (size_t k = 0; k <= n - 2; ++k) { if (k == i || k == j) { continue; } result.emplace_back((a[i] * a[j] * a[i] * a[k]) ^ 2, word_type({})); } } } return result; } else if (val == author::Guralnick + author::Kantor + author::Kassabov + author::Lubotzky) { // See Section 2.2 of 'Presentations of finite simple groups: A // quantitative approach' J. Amer. Math. Soc. 21 (2008), 711-774 std::vector<word_type> a; for (size_t i = 0; i <= n - 2; ++i) { a.push_back({i}); } std::vector<relation_type> result; for (size_t i = 0; i <= n - 2; ++i) { result.emplace_back(a[i] ^ 2, word_type({})); } for (size_t i = 0; i <= n - 2; ++i) { for (size_t j = 0; j <= n - 2; ++j) { if (i != j) { result.emplace_back((a[i] * a[j]) ^ 3, word_type({})); } } } for (size_t i = 0; i <= n - 2; ++i) { for (size_t j = 0; j <= n - 2; ++j) { if (i == j) { continue; } for (size_t k = 0; k <= n - 2; ++k) { if (k != i && k != j) { result.emplace_back((a[i] * a[j] * a[k]) ^ 4, word_type({})); } } } } return result; } else { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be one of: author::Burnside + " "author::Miller, " "author::Carmichael, author::Coxeter + author::Moser, or " "author::Moore, found %s", detail::to_string(val).c_str()); } } std::vector<relation_type> alternating_group(size_t n, author val) { if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be at least 4, found %llu", uint64_t(n)); } if (val == author::Moore) { std::vector<relation_type> result; std::vector<word_type> a; for (size_t i = 0; i <= n - 3; ++i) { a.push_back(word_type({i})); } result.emplace_back(a[0] ^ 3, word_type({})); for (size_t j = 1; j <= n - 3; ++j) { result.emplace_back(a[j] ^ 2, word_type({})); } for (size_t i = 1; i <= n - 3; ++i) { result.emplace_back((a[i - 1] * a[i]) ^ 3, word_type({})); } for (size_t k = 2; k <= n - 3; ++k) { for (size_t j = 0; j <= k - 2; ++j) { result.emplace_back((a[j] * a[k]) ^ 2, word_type({})); } } return result; } LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::Moore, found %s", detail::to_string(val).c_str()); } // From https://core.ac.uk/reader/33304940 std::vector<relation_type> dual_symmetric_inverse_monoid(size_t n, author val) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be at least 3, found %llu", uint64_t(n)); } if (val == author::Easdown + author::East + author::FitzGerald) { auto mij = [](size_t i, size_t j) { if (i == j) { return 1; } else if (std::abs(static_cast<int64_t>(i) - static_cast<int64_t>(j)) == 1) { return 3; } else { return 2; } }; std::vector<word_type> alphabet; for (size_t i = 0; i < n + 1; ++i) { alphabet.push_back({i}); } auto x = alphabet.back(); auto e = alphabet.front(); std::vector<relation_type> result; add_monoid_relations(alphabet, e, result); auto s = alphabet.cbegin(); // R1 for (size_t i = 1; i <= n - 1; ++i) { for (size_t j = 1; j <= n - 1; ++j) { result.emplace_back((s[i] * s[j]) ^ mij(i, j), e); } } // R2 result.emplace_back(x ^ 3, x); // R3 result.emplace_back(x * s[1], x); result.emplace_back(s[1] * x, x); // R4 result.emplace_back(x * s[2] * x, x * s[2] * x * s[2]); result.emplace_back(x * s[2] * x * s[2], s[2] * x * s[2] * x); result.emplace_back(s[2] * x * s[2] * x, x * s[2] * (x ^ 2)); result.emplace_back(x * s[2] * (x ^ 2), (x ^ 2) * s[2] * x); if (n == 3) { return result; } // R5 word_type const sigma = s[2] * s[3] * s[1] * s[2]; result.emplace_back((x ^ 2) * sigma * (x ^ 2) * sigma, sigma * (x ^ 2) * sigma * (x ^ 2)); result.emplace_back(sigma * (x ^ 2) * sigma * (x ^ 2), x * s[2] * s[3] * s[2] * x); // R6 std::vector<word_type> l = {{}, {}, x * s[2] * s[1]}; for (size_t i = 3; i <= n - 1; ++i) { l.push_back(s[i] * l[i - 1] * s[i] * s[i - 1]); } std::vector<word_type> y = {{}, {}, {}, x}; for (size_t i = 4; i <= n; ++i) { y.push_back(l[i - 1] * y[i - 1] * s[i - 1]); } for (size_t i = 3; i <= n - 1; ++i) { result.emplace_back(y[i] * s[i] * y[i], s[i] * y[i] * s[i]); } if (n == 4) { return result; } // R7 for (size_t i = 4; i <= n - 1; ++i) { result.emplace_back(x * s[i], s[i] * x); } return result; } else { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::Easdown + author::East + " "author::FitzGerald, found %s", detail::to_string(val).c_str()); } } std::vector<relation_type> uniform_block_bijection_monoid(size_t n, author val) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be at least 3, found %llu", uint64_t(n)); } if (val == author::FitzGerald) { auto mij = [](size_t i, size_t j) { if (i == j) { return 1; } else if (std::abs(static_cast<int64_t>(i) - static_cast<int64_t>(j)) == 1) { return 3; } else { return 2; } }; std::vector<word_type> alphabet; for (size_t i = 0; i < n + 1; ++i) { alphabet.push_back({i}); } auto t = alphabet.back(); auto e = alphabet.front(); std::vector<relation_type> result; add_monoid_relations(alphabet, e, result); auto s = alphabet.cbegin(); // S in Theorem 3 (same as dual_symmetric_inverse_monoid) for (size_t i = 1; i <= n - 1; ++i) { for (size_t j = 1; j <= n - 1; ++j) { result.emplace_back((s[i] * s[j]) ^ mij(i, j), e); } } // F2 result.emplace_back(t ^ 2, t); // F3 result.emplace_back(t * s[1], t); result.emplace_back(s[1] * t, t); // F4 for (size_t i = 3; i <= n - 1; ++i) { result.emplace_back(s[i] * t, t * s[i]); } // F5 result.emplace_back(s[2] * t * s[2] * t, t * s[2] * t * s[2]); // F6 result.emplace_back( s[2] * s[1] * s[3] * s[2] * t * s[2] * s[3] * s[1] * s[2] * t, t * s[2] * s[1] * s[3] * s[2] * t * s[2] * s[3] * s[1] * s[2]); return result; } else { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::FitzGerald, found %s", detail::to_string(val).c_str()); } } // From Theorem 41 in doi:10.1016/j.jalgebra.2011.04.008 std::vector<relation_type> partition_monoid(size_t n, author val) { std::vector<relation_type> result; if (val == author::Machine) { if (n != 3) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument (size_t) must be 3 when the " "2nd argument is Machine, found %llu", uint64_t(n)); } result.emplace_back<word_type, word_type>({0, 0}, {0}); result.emplace_back<word_type, word_type>({0, 1}, {1}); result.emplace_back<word_type, word_type>({0, 2}, {2}); result.emplace_back<word_type, word_type>({0, 3}, {3}); result.emplace_back<word_type, word_type>({0, 4}, {4}); result.emplace_back<word_type, word_type>({1, 0}, {1}); result.emplace_back<word_type, word_type>({2, 0}, {2}); result.emplace_back<word_type, word_type>({2, 2}, {0}); result.emplace_back<word_type, word_type>({2, 4}, {4}); result.emplace_back<word_type, word_type>({3, 0}, {3}); result.emplace_back<word_type, word_type>({3, 3}, {3}); result.emplace_back<word_type, word_type>({4, 0}, {4}); result.emplace_back<word_type, word_type>({4, 2}, {4}); result.emplace_back<word_type, word_type>({4, 4}, {4}); result.emplace_back<word_type, word_type>({1, 1, 1}, {0}); result.emplace_back<word_type, word_type>({1, 1, 2}, {2, 1}); result.emplace_back<word_type, word_type>({1, 2, 1}, {2}); result.emplace_back<word_type, word_type>({2, 1, 1}, {1, 2}); result.emplace_back<word_type, word_type>({2, 1, 2}, {1, 1}); result.emplace_back<word_type, word_type>({2, 1, 4}, {1, 1, 4}); result.emplace_back<word_type, word_type>({3, 1, 2}, {1, 2, 3}); result.emplace_back<word_type, word_type>({3, 4, 3}, {3}); result.emplace_back<word_type, word_type>({4, 1, 2}, {4, 1, 1}); result.emplace_back<word_type, word_type>({4, 3, 4}, {4}); result.emplace_back<word_type, word_type>({1, 1, 3, 1}, {2, 3, 2}); result.emplace_back<word_type, word_type>({1, 1, 3, 2}, {2, 3, 1}); result.emplace_back<word_type, word_type>({1, 2, 3, 1}, {3, 2}); result.emplace_back<word_type, word_type>({1, 2, 3, 2}, {3, 1}); result.emplace_back<word_type, word_type>({1, 2, 3, 4}, {3, 1, 4}); result.emplace_back<word_type, word_type>({1, 3, 2, 3}, {3, 1, 3}); result.emplace_back<word_type, word_type>({1, 4, 1, 4}, {4, 1, 4}); result.emplace_back<word_type, word_type>({2, 1, 3, 1}, {1, 3, 2}); result.emplace_back<word_type, word_type>({2, 1, 3, 2}, {1, 3, 1}); result.emplace_back<word_type, word_type>({2, 1, 3, 4}, {1, 3, 1, 4}); result.emplace_back<word_type, word_type>({2, 3, 1, 3}, {1, 3, 1, 3}); result.emplace_back<word_type, word_type>({2, 3, 1, 4}, {1, 1, 3, 4}); result.emplace_back<word_type, word_type>({2, 3, 2, 3}, {3, 2, 3}); result.emplace_back<word_type, word_type>({3, 1, 3, 2}, {3, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 4, 3}, {1, 2, 3}); result.emplace_back<word_type, word_type>({3, 2, 3, 2}, {3, 2, 3}); result.emplace_back<word_type, word_type>({4, 1, 1, 4}, {4, 1, 4}); result.emplace_back<word_type, word_type>({4, 1, 3, 2}, {4, 1, 3, 1}); result.emplace_back<word_type, word_type>({4, 1, 4, 1}, {4, 1, 4}); result.emplace_back<word_type, word_type>({1, 3, 1, 1, 3}, {3, 2, 1, 3}); result.emplace_back<word_type, word_type>({1, 3, 4, 1, 4}, {4, 1, 3, 4}); result.emplace_back<word_type, word_type>({2, 3, 1, 1, 3}, {3, 1, 1, 3}); result.emplace_back<word_type, word_type>({2, 3, 2, 1, 3}, {1, 3, 2, 1, 3}); result.emplace_back<word_type, word_type>({2, 3, 4, 1, 3}, {1, 3, 4, 1, 3}); result.emplace_back<word_type, word_type>({2, 3, 4, 1, 4}, {1, 4, 1, 3, 4}); result.emplace_back<word_type, word_type>({3, 1, 1, 4, 1}, {1, 1, 4, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 3, 1, 1}, {3, 2, 1, 3}); result.emplace_back<word_type, word_type>({3, 2, 3, 1, 1}, {3, 1, 1, 3}); result.emplace_back<word_type, word_type>({3, 4, 1, 1, 3}, {1, 2, 3}); result.emplace_back<word_type, word_type>({3, 4, 1, 4, 3}, {1, 1, 4, 1, 3}); result.emplace_back<word_type, word_type>({4, 1, 1, 3, 4}, {4, 3, 1, 4}); result.emplace_back<word_type, word_type>({4, 1, 3, 1, 1}, {1, 3, 1, 1, 4}); result.emplace_back<word_type, word_type>({4, 1, 3, 1, 3}, {4, 3, 1, 3}); result.emplace_back<word_type, word_type>({4, 1, 3, 1, 4}, {4, 1, 3, 4}); result.emplace_back<word_type, word_type>({4, 1, 3, 4, 1}, {4, 1, 3, 4}); result.emplace_back<word_type, word_type>({4, 1, 4, 3, 2}, {4, 1, 4, 3, 1}); result.emplace_back<word_type, word_type>({1, 1, 3, 4, 1, 3}, {3, 1, 4, 1, 3}); result.emplace_back<word_type, word_type>({1, 1, 4, 1, 3, 4}, {3, 4, 1, 4}); result.emplace_back<word_type, word_type>({1, 3, 1, 1, 4, 3}, {4, 3, 2, 1, 3}); result.emplace_back<word_type, word_type>({1, 3, 1, 3, 1, 3}, {3, 1, 3, 1, 3}); result.emplace_back<word_type, word_type>({1, 3, 1, 4, 1, 3}, {3, 4, 1, 3}); result.emplace_back<word_type, word_type>({1, 4, 3, 1, 1, 4}, {4, 3, 1, 1, 4}); result.emplace_back<word_type, word_type>({2, 3, 1, 1, 4, 3}, {1, 4, 3, 2, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 1, 3, 4, 1}, {3, 1, 4, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 1, 4, 3, 1}, {1, 1, 4, 3, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 3, 1, 3, 1}, {3, 1, 3, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 3, 1, 4, 1}, {3, 4, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 4, 1, 1, 3}, {3}); result.emplace_back<word_type, word_type>({4, 1, 4, 3, 1, 1}, {4, 3, 1, 1, 4}); result.emplace_back<word_type, word_type>({4, 1, 4, 3, 1, 4}, {4, 1, 4}); result.emplace_back<word_type, word_type>({4, 3, 1, 3, 1, 4}, {1, 3, 1, 1, 4}); result.emplace_back<word_type, word_type>({1, 1, 4, 3, 1, 3, 1}, {3, 1, 1, 4, 3, 2}); result.emplace_back<word_type, word_type>({1, 1, 4, 3, 2, 1, 3}, {3, 1, 1, 4, 3}); result.emplace_back<word_type, word_type>({1, 3, 1, 3, 4, 1, 3}, {3, 1, 3, 4, 1, 3}); result.emplace_back<word_type, word_type>({3, 1, 1, 4, 3, 2, 1}, {3, 1, 1, 4, 3}); result.emplace_back<word_type, word_type>({3, 1, 3, 1, 3, 4, 1}, {3, 1, 3, 4, 1, 3}); result.emplace_back<word_type, word_type>({4, 3, 1, 1, 4, 3, 2}, {4, 1, 4, 3, 1, 3, 1}); result.emplace_back<word_type, word_type>({3, 1, 1, 4, 3, 2, 3, 1}, {3, 1, 1, 4, 3, 2, 3}); result.emplace_back<word_type, word_type>({3, 1, 1, 4, 3, 2, 3, 4, 1}, {1, 1, 4, 3, 1, 3, 4, 1, 3}); return result; } else if (val == author::East) { if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument (size_t) must be at least 4 " "when the 2nd argument is author::East, found %llu", uint64_t(n)); } word_type s = {0}; word_type c = {1}; word_type e = {2}; word_type t = {3}; word_type id = {4}; std::vector<word_type> alphabet = {s, c, e, t, id}; add_monoid_relations(alphabet, id, result); // V1 result.emplace_back(c ^ n, id); result.emplace_back((s * c) ^ (n - 1), id); result.emplace_back(s * s, id); for (size_t i = 2; i <= n / 2; ++i) { result.emplace_back(((c ^ i) * s * (c ^ (n - i)) * s) ^ 2, id); } // V2 result.emplace_back(e * e, e); result.emplace_back(e * t * e, e); result.emplace_back(s * c * e * (c ^ (n - 1)) * s, e); result.emplace_back(c * s * (c ^ (n - 1)) * e * c * s * (c ^ (n - 1)), e); // V3 result.emplace_back(t * t, t); result.emplace_back(t * e * t, t); result.emplace_back(t * s, t); result.emplace_back(s * t, t); result.emplace_back( (c ^ 2) * s * (c ^ (n - 2)) * t * (c ^ 2) * s * (c ^ (n - 2)), t); result.emplace_back((c ^ (n - 1)) * s * c * s * (c ^ (n - 1)) * t * c * s * (c ^ (n - 1)) * s * c, t); // V4 result.emplace_back(s * e * s * e, e * s * e); result.emplace_back(e * s * e * s, e * s * e); // V5 result.emplace_back(t * c * t * (c ^ (n - 1)), c * t * (c ^ (n - 1)) * t); // V6 result.emplace_back(t * (c ^ 2) * t * (c ^ (n - 2)), (c ^ 2) * t * (c ^ (n - 2)) * t); // V7 result.emplace_back(t * (c ^ 2) * e * (c ^ (n - 2)), (c ^ 2) * e * (c ^ (n - 2)) * t); } else { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::East, found %s", detail::to_string(val).c_str()); } return result; } // From Theorem 5 in 10.21136/MB.2007.134125 // https://dml.cz/bitstream/handle/10338.dmlcz/134125/MathBohem_132-2007-3_6.pdf std::vector<relation_type> singular_brauer_monoid(size_t n) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 3, found %llu", uint64_t(n)); } std::vector<std::vector<word_type>> t; size_t val = 0; for (size_t i = 0; i < n; ++i) { t.push_back({}); for (size_t j = 0; j < n; ++j) { if (i != j) { t.back().push_back({val}); val++; } else { t.back().push_back({0}); } } } std::vector<relation_type> result; // (3) + (4) for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { if (i != j) { result.emplace_back(t[i][j], t[j][i]); result.emplace_back(t[i][j] ^ 2, t[i][j]); } } } // (6) + (7) for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { for (size_t k = 0; k < n; ++k) { if (i != j && j != k && i != k) { result.emplace_back(t[i][j] * t[i][k] * t[j][k], t[i][j] * t[j][k]); result.emplace_back(t[i][j] * t[j][k] * t[i][j], t[i][j]); } } } } // (5) + (8) + (9) for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { for (size_t k = 0; k < n; ++k) { for (size_t l = 0; l < n; ++l) { if (i != j && j != k && i != k && i != l && j != l && k != l) { result.emplace_back(t[i][j] * t[j][k] * t[k][l], t[i][j] * t[i][l] * t[k][l]); result.emplace_back(t[i][j] * t[k][l] * t[i][k], t[i][j] * t[j][l] * t[i][k]); result.emplace_back(t[i][j] * t[k][l], t[k][l] * t[i][j]); } } } } } return result; } // From https://doi.org/10.1007/s10012-000-0001-1 std::vector<relation_type> orientation_preserving_monoid(size_t n) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 3, found %llu", uint64_t(n)); } word_type b = {0}; word_type u = {1}; word_type e = {2}; std::vector<relation_type> result; add_monoid_relations({b, u, e}, e, result); result.emplace_back(b ^ n, e); result.emplace_back(u ^ 2, u); result.emplace_back((u * b) ^ n, u * b); result.emplace_back(b * ((u * (b ^ (n - 1))) ^ (n - 1)), (u * (b ^ (n - 1))) ^ (n - 1)); for (size_t i = 2; i <= n - 1; ++i) { result.emplace_back(u * (b ^ i) * ((u * b) ^ (n - 1)) * (b ^ (n - i)), (b ^ i) * ((u * b) ^ (n - 1)) * (b ^ (n - i)) * u); } return result; } // Also from https://doi.org/10.1007/s10012-000-0001-1 std::vector<relation_type> orientation_reversing_monoid(size_t n) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 3, found %llu", uint64_t(n)); } word_type e = {0}; word_type b = {1}; word_type u = {2}; word_type c = {3}; std::vector<relation_type> result; add_monoid_relations({e, b, u, c}, e, result); result.emplace_back(b ^ n, e); result.emplace_back(u ^ 2, u); result.emplace_back((u * b) ^ n, u * b); result.emplace_back(b * ((u * (b ^ (n - 1))) ^ (n - 1)), (u * (b ^ (n - 1))) ^ (n - 1)); for (size_t i = 2; i <= n - 1; ++i) { result.emplace_back(u * (b ^ i) * ((u * b) ^ (n - 1)) * (b ^ (n - i)), (b ^ i) * ((u * b) ^ (n - 1)) * (b ^ (n - i)) * u); } result.emplace_back(c ^ 2, e); result.emplace_back(b * c, c * (b ^ (n - 1))); result.emplace_back(u * c, c * ((b * u) ^ (n - 1))); result.emplace_back(c * (u * (b ^ (n - 1)) ^ (n - 2)), (b ^ (n - 2)) * ((u * (b ^ (n - 1))) ^ (n - 2))); return result; } // From Theorem 2.2 in https://doi.org/10.1093/qmath/haab001 std::vector<relation_type> temperley_lieb_monoid(size_t n) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 3, found %llu", uint64_t(n)); } std::vector<word_type> e(n, word_type()); for (size_t i = 0; i < n - 1; ++i) { e[i + 1] = {i}; } std::vector<relation_type> result; // E1 for (size_t i = 1; i <= n - 1; ++i) { result.emplace_back(e[i] ^ 2, e[i]); } // E2 + E3 for (size_t i = 1; i <= n - 1; ++i) { for (size_t j = 1; j <= n - 1; ++j) { auto d = std::abs(static_cast<int64_t>(i) - static_cast<int64_t>(j)); if (d > 1) { result.emplace_back(e[i] * e[j], e[j] * e[i]); } else if (d == 1) { result.emplace_back(e[i] * e[j] * e[i], e[i]); } } } return result; } // From Theorem 3.1 in // https://link.springer.com/content/pdf/10.2478/s11533-006-0017-6.pdf std::vector<relation_type> brauer_monoid(size_t n) { word_type const e = {0}; std::vector<word_type> sigma(n); std::vector<word_type> theta(n); std::vector<word_type> alphabet = {e}; for (size_t i = 1; i <= n - 1; ++i) { sigma[i] = {i}; alphabet.push_back(sigma[i]); } for (size_t i = 1; i <= n - 1; ++i) { theta[i] = {i + n - 1}; alphabet.push_back(theta[i]); } std::vector<relation_type> result; add_monoid_relations(alphabet, e, result); // E1 for (size_t i = 1; i <= n - 1; ++i) { result.emplace_back(sigma[i] ^ 2, e); result.emplace_back(theta[i] ^ 2, theta[i]); result.emplace_back(theta[i] * sigma[i], sigma[i] * theta[i]); result.emplace_back(sigma[i] * theta[i], theta[i]); } // E2 + E3 for (size_t i = 1; i <= n - 1; ++i) { for (size_t j = 1; j <= n - 1; ++j) { auto d = std::abs(static_cast<int64_t>(i) - static_cast<int64_t>(j)); if (d > 1) { result.emplace_back(sigma[i] * sigma[j], sigma[j] * sigma[i]); result.emplace_back(theta[i] * theta[j], theta[j] * theta[i]); result.emplace_back(theta[i] * sigma[j], sigma[j] * theta[i]); } else if (d == 1) { result.emplace_back(sigma[i] * sigma[j] * sigma[i], sigma[j] * sigma[i] * sigma[j]); result.emplace_back(theta[i] * theta[j] * theta[i], theta[i]); result.emplace_back(sigma[i] * theta[j] * theta[i], sigma[j] * theta[i]); result.emplace_back(theta[i] * theta[j] * sigma[i], theta[i] * sigma[j]); } } } return result; } // From Proposition 4.2 in // https://link.springer.com/content/pdf/10.1007/s002339910016.pdf std::vector<relation_type> rectangular_band(size_t m, size_t n) { if (m == 0) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be strictly positive, found %llu", uint64_t(m)); } if (n == 0) { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be strictly positive, found %llu", uint64_t(n)); } std::vector<word_type> a(m); std::vector<word_type> b(n); for (size_t i = 0; i < m; ++i) { a[i] = {i}; } for (size_t i = 0; i < n; ++i) { b[i] = {i + m}; } std::vector<relation_type> result; result.emplace_back(a[0], b[0]); // (7) for (size_t i = 1; i < m; ++i) { result.emplace_back(a[i - 1] * a[i], a[i - 1]); } result.emplace_back(a[m - 1] * a[0], a[m - 1]); // (8) for (size_t i = 1; i < n; ++i) { result.emplace_back(b[i - 1] * b[i], b[i]); } result.emplace_back(b[n - 1] * b[0], b[0]); for (size_t i = 1; i < m; ++i) { for (size_t j = 1; j < n; ++j) { result.emplace_back(b[j] * a[i], a[0]); } } return result; } std::vector<relation_type> full_transformation_monoid(size_t n, author val) { if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument (size_t) must be at least 4, found %llu", uint64_t(n)); } if (val == author::Aizenstat) { // From Proposition 1.7 in https://bit.ly/3R5ZpKW auto result = symmetric_group(n, author::Moore); word_type const a = {0}; word_type const b = {1}; word_type const t = {2}; result.emplace_back(a * t, t); result.emplace_back( (b ^ (n - 2)) * a * (b ^ 2) * t * (b ^ (n - 2)) * a * (b ^ 2), t); result.emplace_back(b * a * (b ^ (n - 1)) * a * b * t * (b ^ (n - 1)) * a * b * a * (b ^ (n - 1)), t); result.emplace_back((t * b * a * (b ^ (n - 1))) ^ 2, t); result.emplace_back(((b ^ (n - 1)) * a * b * t) ^ 2, t * (b ^ (n - 1)) * a * b * t); result.emplace_back((t * (b ^ (n - 1)) * a * b) ^ 2, t * (b ^ (n - 1)) * a * b * t); result.emplace_back((t * b * a * (b ^ (n - 2)) * a * b) ^ 2, (b * a * (b ^ (n - 2)) * a * b * t) ^ 2); return result; } else if (val == author::Iwahori) { // From Theorem 9.3.1, p161-162, (Ganyushkin + Mazorchuk) // using Theorem 9.1.4 to express presentation in terms // of the pi_i and e_12. // https://link.springer.com/book/10.1007/978-1-84800-281-4 auto result = symmetric_group(n, author::Carmichael); add_full_transformation_monoid_relations(result, n, 0, n - 1); return result; } LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::Aizenstat or " "author::Iwahori, found %s", detail::to_string(val).c_str()); } std::vector<relation_type> partial_transformation_monoid(size_t n, author val) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument (size_t) must be at least 3, found %llu", uint64_t(n)); } else if (val == author::Machine) { if (n != 3) { LIBSEMIGROUPS_EXCEPTION("the 1st argument must be 3 where the 2nd " "argument is author::Machine, found %llu", uint64_t(n)); } return {{{0, 0}, {}}, {{0, 3}, {3}}, {{2, 2}, {2}}, {{2, 3}, {2}}, {{3, 2}, {3}}, {{3, 3}, {3}}, {{0, 1, 0}, {1, 1}}, {{0, 1, 1}, {1, 0}}, {{1, 0, 1}, {0}}, {{1, 1, 0}, {0, 1}}, {{1, 1, 1}, {}}, {{1, 1, 3}, {0, 1, 3}}, {{2, 0, 1}, {0, 1, 2}}, {{3, 0, 2}, {2, 0, 2}}, {{3, 1, 2}, {2, 1, 2}}, {{0, 1, 2, 0}, {2, 1, 1}}, {{0, 1, 2, 1}, {2, 1, 0}}, {{0, 2, 0, 2}, {2, 0, 2}}, {{0, 2, 1, 0}, {1, 2, 1}}, {{0, 2, 1, 1}, {1, 2, 0}}, {{0, 2, 1, 2}, {2, 1, 2}}, {{1, 2, 1, 0}, {0, 2, 1}}, {{1, 2, 1, 1}, {0, 2, 0}}, {{1, 2, 1, 3}, {0, 2, 1, 3}}, {{1, 3, 1, 3}, {3, 1, 3}}, {{2, 0, 2, 0}, {2, 0, 2}}, {{2, 0, 2, 1}, {2, 1, 2}}, {{2, 1, 2, 1}, {2, 1, 2, 0}}, {{2, 1, 3, 1}, {2, 1, 3, 0}}, {{3, 0, 1, 2}, {3, 0, 1}}, {{3, 0, 1, 3}, {3, 0, 1}}, {{3, 1, 3, 1}, {3, 1, 3, 0}}, {{1, 0, 2, 1, 3}, {3, 1, 0, 2}}, {{1, 1, 2, 0, 2}, {2, 1, 1, 2}}, {{1, 1, 2, 1, 2}, {2, 1, 0, 2}}, {{1, 3, 1, 0, 2}, {2, 1, 3}}, {{2, 1, 0, 2, 1}, {2, 1, 0, 2, 0}}, {{2, 1, 1, 2, 0}, {2, 1, 1, 2}}, {{2, 1, 1, 2, 1}, {2, 1, 0, 2}}, {{2, 1, 3, 0, 1}, {1, 3, 1, 1, 2}}, {{3, 1, 0, 2, 1}, {3, 1, 0, 2, 0}}, {{3, 1, 1, 2, 0}, {3, 1, 1, 2}}, {{3, 1, 1, 2, 1}, {3, 1, 0, 2}}, {{1, 2, 1, 2, 0, 2}, {2, 1, 2, 0, 2}}}; } else if (val == author::Sutov) { // From Theorem 9.4.1, p169, (Ganyushkin + Mazorchuk) // https://link.springer.com/book/10.1007/978-1-84800-281-4 if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument must be at least 4 when the " "2nd argument is author::Sutov, found %llu", uint64_t(n)); } auto result = symmetric_inverse_monoid(n, author::Sutov); add_full_transformation_monoid_relations(result, n, 0, n); word_type e12 = {n}; std::vector<word_type> epsilon = {{n - 1}, {0, n - 1, 0}, {1, n - 1, 1}}; result.emplace_back(e12 * epsilon[1], e12); result.emplace_back(epsilon[1] * e12, epsilon[1]); result.emplace_back(e12 * epsilon[0], epsilon[1] * epsilon[0] * e12); result.emplace_back(e12 * epsilon[2], epsilon[2] * e12); return result; } LIBSEMIGROUPS_EXCEPTION("expected 2nd argument to be author::Machine or " "author::Sutov, found %s", detail::to_string(val).c_str()); } // From Theorem 9.2.2, p156 // https://link.springer.com/book/10.1007/978-1-84800-281-4 (Ganyushkin + // Mazorchuk) std::vector<relation_type> symmetric_inverse_monoid(size_t n, author val) { if (val == author::Sutov) { if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument must be at least 4 when the " "2nd argument is author::Sutov, found %llu", uint64_t(n)); } auto result = symmetric_group(n, author::Carmichael); std::vector<word_type> pi; for (size_t i = 0; i <= n - 2; ++i) { pi.push_back({i}); } std::vector<word_type> epsilon; epsilon.push_back({n - 1}); for (size_t i = 0; i <= n - 2; ++i) { epsilon.push_back(pi[i] * epsilon[0] * pi[i]); } result.emplace_back(epsilon[0] ^ 2, epsilon[0]); result.emplace_back(epsilon[0] * epsilon[1], epsilon[1] * epsilon[0]); for (size_t k = 1; k <= n - 2; ++k) { result.emplace_back(epsilon[1] * pi[k], pi[k] * epsilon[1]); result.emplace_back(epsilon[k + 1] * pi[0], pi[0] * epsilon[k + 1]); } result.emplace_back(epsilon[1] * epsilon[0] * pi[0], epsilon[1] * epsilon[0]); return result; } LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::Sutov, found %s", detail::to_string(val).c_str()); } // Chinese monoid // See: The Chinese Monoid - Cassaigne, Espie, Krob, Novelli and Hivert, // 2001 std::vector<relation_type> chinese_monoid(size_t n) { if (n < 2) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 2, found %llu", uint64_t(n)); } std::vector<relation_type> result; for (size_t a = 0; a < n; a++) { for (size_t b = a; b < n; b++) { for (size_t c = b; c < n; c++) { if (a != b) { result.emplace_back(word_type({c, b, a}), word_type({c, a, b})); } if (b != c) { result.emplace_back(word_type({c, b, a}), word_type({b, c, a})); } } } } return result; } std::vector<relation_type> monogenic_semigroup(size_t m, size_t r) { std::vector<relation_type> result; if (r == 0) { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be strictly positive, found %llu", uint64_t(r)); } result.emplace_back(word_type({0}) ^ (m + r), word_type({0}) ^ m); return result; } std::vector<relation_type> order_preserving_monoid(size_t n) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 3, found %llu", uint64_t(n)); } std::vector<word_type> u; std::vector<word_type> v; for (size_t i = 0; i <= n - 2; ++i) { u.push_back({i}); v.push_back({n - 1 + i}); } std::vector<relation_type> result; // relations 1 for (size_t i = 1; i <= n - 2; ++i) { result.emplace_back(v[n - 2 - i] * u[i], u[i] * v[n - 1 - i]); } // relations 2 for (size_t i = 1; i <= n - 2; ++i) { result.emplace_back(u[n - 2 - i] * v[i], v[i] * u[n - 1 - i]); } // relations 3 for (size_t i = 0; i <= n - 2; ++i) { result.emplace_back(v[n - 2 - i] * u[i], u[i]); } // relations 4 for (size_t i = 0; i <= n - 2; ++i) { result.emplace_back(u[n - 2 - i] * v[i], v[i]); } // relations 5 for (size_t i = 0; i <= n - 2; ++i) { for (size_t j = 0; j <= n - 2; ++j) { if (j != (n - 2) - i && j != n - i - 1) { result.emplace_back(u[i] * v[j], v[j] * u[i]); } } } // relation 6 result.emplace_back(u[0] * u[1] * u[0], u[0] * u[1]); // relation 7 result.emplace_back(v[0] * v[1] * v[0], v[0] * v[1]); return result; } std::vector<relation_type> cyclic_inverse_monoid(size_t n, author val, size_t index) { if (val == author::Fernandes) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument must be at least 3 where the 2nd argument is " "author::Fernandes, found %llu", uint64_t(n)); } // See Theorem 2.6 of https://arxiv.org/pdf/2211.02155.pdf if (index == 0) { word_type g = {0}; std::vector<word_type> e(n, {0}); size_t inc = 1; std::for_each(e.begin(), e.end(), [&inc](auto& w) { w[0] += inc++; std::vector<relation_type> result; // R1 result.emplace_back(g ^ n, word_type({})); // R2 for (size_t i = 0; i < n; ++i) { result.emplace_back(e[i] ^ 2, e[i]); } // R3 for (size_t i = 0; i < n - 1; ++i) { for (size_t j = i + 1; j < n; ++j) { result.emplace_back(e[i] * e[j], e[j] * e[i]); } } // R4 result.emplace_back(g * e[0], e[n - 1] * g); for (size_t i = 0; i < n - 1; ++i) { result.emplace_back(g * e[i + 1], e[i] * g); } // R5 word_type prod(n, 0); std::iota(prod.begin(), prod.end(), size_t(1)); result.emplace_back(g * prod, prod); return result; } // See Theorem 2.7 of https://arxiv.org/pdf/2211.02155.pdf if (index == 1) { word_type g = {0}; word_type e = {1}; std::vector<relation_type> result; result.emplace_back(g ^ n, word_type({})); // relation Q1 result.emplace_back(e ^ 2, e); // relation Q2 // relations Q3 for (size_t j = 2; j <= n; ++j) for (size_t i = 1; i < j; ++i) { result.emplace_back(e * (g ^ (n - j + i)) * e * (g ^ (n - i + j)), (g ^ (n - j + i)) * e * (g ^ (n - i + j)) * e); } result.emplace_back(g * (e * (g ^ (n - 1)) ^ n), (e * (g ^ (n - 1))) ^ n); // relation Q4 return result; } LIBSEMIGROUPS_EXCEPTION("3rd argument must be 0 or 1 where 2nd " "argument is author::Fernandes, found %llu", uint64_t(n)); } LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::Fernandes, found %s", detail::to_string(val).c_str()); } // See Theorem 2.17 of https://arxiv.org/pdf/2211.02155.pdf std::vector<relation_type> order_preserving_cyclic_inverse_monoid(size_t n) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 3, found %llu", uint64_t(n)); } word_type x = {0}; word_type y = {1}; std::vector<word_type> e; for (size_t i = 2; i <= n - 1; ++i) { e.push_back({i}); } std::vector<relation_type> result; // relations V1 for (size_t i = 0; i <= n - 3; ++i) { result.emplace_back(e[i] ^ 2, e[i]); } // relations V2 result.emplace_back(x * y * x, x); result.emplace_back(y * x * y, y); // relations V3 result.emplace_back(y * (x ^ 2) * y, x * (y ^ 2) * x); // relations V4 for (size_t j = 1; j <= n - 3; ++j) { for (size_t i = 0; i < j; ++i) { result.emplace_back(e[i] * e[j], e[j] * e[i]); } } // relations V5 for (size_t i = 0; i <= n - 3; ++i) { result.emplace_back(x * y * e[i], e[i] * x * y); result.emplace_back(y * x * e[i], e[i] * y * x); } // relations V6 for (size_t i = 0; i <= n - 4; ++i) { result.emplace_back(x * e[i + 1], e[i] * x); } // relations V7 result.emplace_back((x ^ 2) * y, e[n - 3] * x); result.emplace_back(y * (x ^ 2), x * e[0]); // relations V8 word_type lhs = y * x; word_type rhs = x; for (size_t i = 0; i <= n - 3; ++i) { lhs = lhs * e[i]; rhs = rhs * e[i]; } lhs = lhs * x * y; rhs = rhs * x * y; result.emplace_back(lhs, rhs); return result; } // See Theorem 2.8 of https://arxiv.org/pdf/2205.02196.pdf std::vector<relation_type> partial_isometries_cycle_graph_monoid(size_t n) { if (n < 3) { LIBSEMIGROUPS_EXCEPTION( "expected argument to be at least 3, found %llu", uint64_t(n)); } std::vector<relation_type> result; word_type g = {0}; word_type h = {1}; word_type e = {2}; // Q1 result.emplace_back(g ^ n, word_type({})); result.emplace_back(h ^ 2, word_type({})); result.emplace_back(h * g, (g ^ (n - 1)) * h); // Q2 result.emplace_back(e ^ 2, e); result.emplace_back(g * h * e * g * h, e); // Q3 for (size_t j = 2; j <= n; ++j) { for (size_t i = 1; i < j; ++i) { result.emplace_back(e * (g ^ (j - i)) * e * (g ^ (n - j + i)), (g ^ (j - i)) * e * (g ^ (n - j + i)) * e); } } if (n % 2 == 1) { // Q4 result.emplace_back(h * g * ((e * g) ^ (n - 2)) * e, ((e * g) ^ (n - 2)) * e); } else { // Q5 result.emplace_back( h * g * ((e * g) ^ (n / 2 - 1)) * g * ((e * g) ^ (n / 2 - 2)) * e, ((e * g) ^ (n / 2 - 1)) * g * ((e * g) ^ (n / 2 - 2)) * e); result.emplace_back(h * ((e * g) ^ (n - 1)) * e, ((e * g) ^ (n - 1)) * e); } return result; } std::vector<relation_type> not_symmetric_group(size_t n, author val) { if (n < 4) { LIBSEMIGROUPS_EXCEPTION( "expected 1st argument to be at least 4, found %llu", uint64_t(n)); } if (val == author::Guralnick + author::Kantor + author::Kassabov + author::Lubotzky) { // See Section 2.2 of 'Presentations of finite simple groups: A // quantitative approach' J. Amer. Math. Soc. 21 (2008), 711-774 std::vector<word_type> a; for (size_t i = 0; i <= n - 2; ++i) { a.push_back({i}); } std::vector<relation_type> result; for (size_t i = 0; i <= n - 2; ++i) { result.emplace_back(a[i] ^ 2, word_type({})); } for (size_t i = 0; i <= n - 2; ++i) { for (size_t j = 0; j <= n - 2; ++j) { if (i != j) { result.emplace_back((a[i] * a[j]) ^ 3, word_type({})); } } } for (size_t i = 0; i <= n - 2; ++i) { for (size_t j = 0; j <= n - 2; ++j) { if (i == j) { continue; } for (size_t k = 0; k <= n - 2; ++k) { if (k != i && k != j) { result.emplace_back((a[i] * a[j] * a[k]) ^ 4, word_type({})); } } } } return result; } else { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::Guralnick + author::Kantor", " + author::Kassabov + author::Lubotzky found %s", detail::to_string(val).c_str()); } } // The remaining presentation functions are currently undocumented, as we // are not completely sure what they are. std::vector<relation_type> rook_monoid(size_t l, int q) { if (l < 2) { LIBSEMIGROUPS_EXCEPTION( "the 1st argument (size_t) must at least 2, found %llu", uint64_t(l)); } else if (q != 0 && q != 1) { LIBSEMIGROUPS_EXCEPTION( "the 2nd argument (int) must be 0 or 1, found %llu", uint64_t(q)); } std::vector<size_t> s; for (size_t i = 0; i < l; ++i) { s.push_back(i); // 0 est \pi_0 } // identity relations size_t id = l; std::vector<relation_type> rels = {relation_type({id, id}, {id})}; for (size_t i = 0; i < l; ++i) { rels.push_back({{s[i], id}, {s[i]}}); rels.push_back({{id, s[i]}, {s[i]}}); } switch (q) { case 0: for (size_t i = 0; i < l; ++i) rels.push_back({{s[i], s[i]}, {s[i]}}); break; case 1: rels.push_back({{s[0], s[0]}, {s[0]}}); for (size_t i = 1; i < l; ++i) rels.push_back({{s[i], s[i]}, {id}}); break; default: { } } for (int i = 0; i < static_cast<int>(l); ++i) { for (int j = 0; j < static_cast<int>(l); ++j) { if (std::abs(i - j) >= 2) { rels.push_back({{s[i], s[j]}, {s[j], s[i]}}); } } } for (size_t i = 1; i < l - 1; ++i) { rels.push_back({{s[i], s[i + 1], s[i]}, {s[i + 1], s[i], s[i + 1]}}); } rels.push_back({{s[1], s[0], s[1], s[0]}, {s[0], s[1], s[0], s[1]}}); rels.push_back({{s[1], s[0], s[1], s[0]}, {s[0], s[1], s[0]}}); return rels; } std::vector<relation_type> renner_common_type_B_monoid(size_t l, int q) { // q is supposed to be 0 or 1 std::vector<size_t> s; std::vector<size_t> e; for (size_t i = 0; i < l; ++i) { s.push_back(i); } for (size_t i = l; i < 2 * l + 1; ++i) { e.push_back(i); } size_t id = 2 * l + 1; std::vector<relation_type> rels = {relation_type({id, id}, {id})}; // identity relations for (size_t i = 0; i < l; ++i) { rels.push_back({{s[i], id}, {s[i]}}); rels.push_back({{id, s[i]}, {s[i]}}); rels.push_back({{id, e[i]}, {e[i]}}); rels.push_back({{e[i], id}, {e[i]}}); } rels.push_back({{id, e[l]}, {e[l]}}); rels.push_back({{e[l], id}, {e[l]}}); switch (q) { case 0: for (size_t i = 0; i < l; ++i) rels.push_back({{s[i], s[i]}, {s[i]}}); break; case 1: for (size_t i = 0; i < l; ++i) rels.push_back({{s[i], s[i]}, {id}}); break; default: { } } for (int i = 0; i < static_cast<int>(l); ++i) { for (int j = 0; j < static_cast<int>(l); ++j) { if (std::abs(i - j) >= 2) { rels.push_back({{s[i], s[j]}, {s[j], s[i]}}); } } } for (size_t i = 1; i < l - 1; ++i) { rels.push_back({{s[i], s[i + 1], s[i]}, {s[i + 1], s[i], s[i + 1]}}); } rels.push_back({{s[1], s[0], s[1], s[0]}, {s[0], s[1], s[0], s[1]}}); for (size_t i = 1; i < l; ++i) { for (size_t j = 0; j < i; ++j) { rels.push_back({{s[i], e[j]}, {e[j], s[i]}}); } } for (size_t i = 0; i < l; ++i) { for (size_t j = i + 1; j < l + 1; ++j) { rels.push_back({{s[i], e[j]}, {e[j], s[i]}}); rels.push_back({{s[i], e[j]}, {e[j]}}); } } for (size_t i = 0; i < l + 1; ++i) { for (size_t j = 0; j < l + 1; ++j) { rels.push_back({{e[i], e[j]}, {e[j], e[i]}}); rels.push_back({{e[i], e[j]}, {e[std::max(i, j)]}}); } } for (size_t i = 0; i < l; ++i) { rels.push_back({{e[i], s[i], e[i]}, {e[i + 1]}}); } return rels; } std::vector<relation_type> renner_type_B_monoid(size_t l, int q, author val) { if (val == author::Godelle) { std::vector<size_t> s; std::vector<size_t> e; for (size_t i = 0; i < l; ++i) { s.push_back(i); } for (size_t i = l; i < 2 * l + 1; ++i) { e.push_back(i); } std::vector<relation_type> rels = renner_common_type_B_monoid(l, q); if (l >= 2) rels.push_back({{e[0], s[0], s[1], s[0], e[0]}, {e[2]}}); return rels; } else { LIBSEMIGROUPS_EXCEPTION( "expected 2nd argument to be author::Godelle, found %s", detail::to_string(val).c_str()); } } std::vector<relation_type> RennerTypeBMonoid(size_t l, int q) { std::vector<size_t> s; std::vector<size_t> e; for (size_t i = 0; i < l; ++i) { --> -------------------- --> maximum size reached --> -------------------- ¤ Dauer der Verarbeitung: 0.42 Sekunden (vorverarbeitet) ¤*© Formatika GbR, Deutschland |
|
2026-03-28