// // 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;
}
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});
}
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;
} elseif (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;
} elseif (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;
} elseif (index == 1) { // From https://core.ac.uk/download/pdf/82378951.pdf // TODO: Get proper DOI of this paper
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));
} elseif (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;
} elseif (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;
} elseif (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;
} elseif (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);
}
}
return result;
} elseif (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<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;
// 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]);
} elseif (d == 1) {
result.emplace_back(e[i] * e[j] * e[i], e[i]);
}
}
}
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]);
}
// 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};
}
// (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;
} elseif (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());
}
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]);
}
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]);
}
}
}
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);
}
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 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};
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));
} elseif (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]}});
}
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;
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);
}
