Mathieu group M11 as a subgroup of Mathieu group M23 (Presentation 1)
The claims on this page come from https://brauer.maths.qmul.ac.uk/Atlas/v3/subgroup/M23G1-max1W1.
Claim
\[
\mathrm{M}_{23} = \langle a, b \mid a^2 = b^4 = (ab)^{23} = (ab^2)^6 = [a, b]^6 = (abab^{−1}ab^2)^4 = (ab)^3ab^{−1}ab^2(abab^{−1})^2(ab)^3(ab^{−1})^3 = (abab^2)^3(ab^2ab^{−1})^2abab^2abab^{−1}ab^2 = 1\rangle
\]
and
\[
\mathrm{M}_{11} = {\mathrm{M}_{23}} \mathbin{/} \langle a, b \mid b = bbabbababbbabbabab = 1 \rangle
\]
with
\[
[\mathrm{M}_{23} : \mathrm{M}_{11}] = 1,288.
\]
The code
In libsemigroups_pybind11, the following script constructs the presentation for M23, adds the generating pairs that define the subgroup M11, and runs the Todd-Coxeter algorithm.
Code
from libsemigroups_pybind11 import (
Presentation,
ToddCoxeter,
congruence_kind,
presentation,
)
from libsemigroups_pybind11.words import parse_relations
# Setup the presentation object with the empty word and inverses, so it can represent a group
p = Presentation("abAB")
p.contains_empty_word(True)
presentation.add_inverse_rules(p, "ABab")
# Add the defining relations
presentation.add_rule(p, parse_relations("a^2"), "")
presentation.add_rule(p, parse_relations("b^4"), "")
presentation.add_rule(p, parse_relations("(ab)^23"), "")
presentation.add_rule(p, parse_relations("(ab^2)^6"), "")
presentation.add_rule(p, parse_relations("(a,b)^6"), "")
presentation.add_rule(p, parse_relations("(abaBab^2)^4"), "")
presentation.add_rule(p, parse_relations("(ab)^3aBab^2(abaB)^2(ab)^3(aB)^3"), "")
presentation.add_rule(p, parse_relations("(abab^2)^3(ab^2aB)^2abab^2abaBab^2"), "")
# Add generating pairs for the maximal subgroup
tc = ToddCoxeter(congruence_kind.onesided, p)
tc.add_generating_pair("b", "")
tc.add_generating_pair("bbabbababbbabbabab", "")
# Run the Todd-Coxeter algorithm
tc.strategy(tc.options.strategy.felsch)
tc.def_version(tc.options.def_version.two)
tc.def_policy(tc.options.def_policy.discard_all_if_no_space)
tc.use_relations_in_extra(True)
tc.def_max(10000)
tc.run()
print(f"The index of the subgroup is {tc.number_of_classes()}")
The output
Output from the Python script
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 START (strategy() = felsch)
#0: ToddCoxeter: |A| = 4, |R| = 12, |u| + |v| ∈ [2, 46], ∑(|u| + |v|) = 198
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.0 START
#0: ToddCoxeter: FELSCH 0.0.0 | active | killed | defined
#0: ToddCoxeter: nodes | 119 | 56 | 175
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 181 | 295 | 38.0%
#0: ToddCoxeter: time | run 0 = 248µs | all runs = 248µs | elapsed = 323µs
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.1 | active | killed | defined
#1: ToddCoxeter: nodes | 1,258,648 | 24,628 | 1,283,314
#1: ToddCoxeter: diff 0.0.0 | +1,258,529 | +24,572 | +1,283,139
#1: ToddCoxeter: | active | missing | % complete
#1: ToddCoxeter: edges | 3,915,350 | 1,119,242 | 77.8%
#1: ToddCoxeter: diff 0.0.0 | +3,915,169 | +1,118,947 | +39.7%
#1: ToddCoxeter: phase 0.0 = 1.000s | run 0 = 1.000s | all runs = 1.000s | elapsed = 1.000s
#0: ToddCoxeter: large collapse, number of coincidences 100,000 >= 100,000 = large_collapse()!
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.2 | active | killed | defined
#1: ToddCoxeter: nodes | 273,941 | 2,129,053 | 2,402,478
#1: ToddCoxeter: diff 0.0.1 | -984,707 | +2,104,425 | +1,119,164
#1: ToddCoxeter: diff 0.0.0 | +273,822 | +2,128,997 | +2,402,303
#1: ToddCoxeter: | active | missing | % complete
#1: ToddCoxeter: edges | 0 | 1,095,764 | 0.0%
#1: ToddCoxeter: diff 0.0.1 | -3,915,350 | -23,478 | -77.8%
#1: ToddCoxeter: diff 0.0.0 | -181 | +1,095,469 | -38.0%
#1: ToddCoxeter: phase 0.0 = 2.000s | run 0 = 2.001s | all runs = 2.001s | elapsed = 2.001s
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.0 STOP
#0: ToddCoxeter: FELSCH 0.0.3 | active | killed | defined
#0: ToddCoxeter: nodes | 1,288 | 2,401,190 | 2,402,478
#0: ToddCoxeter: diff 0.0.2 | -272,653 | +272,137 | +0
#0: ToddCoxeter: diff 0.0.0 | +1,169 | +2,401,134 | +2,402,303
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 5,152 | 0 | 100.0%
#0: ToddCoxeter: diff 0.0.2 | +5,152 | -1,095,764 | +100.0%
#0: ToddCoxeter: diff 0.0.0 | +4,971 | -295 | +62.0%
#0: ToddCoxeter: phase 0.0 = 2.013s | run 0 = 2.013s | all runs = 2.013s | elapsed = 2.013s
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: LOOKAHEAD 0.1 START (lookahead_extent() = full, lookahead_style() = hlt)
#0: ToddCoxeter: LOOKAHEAD 0.1.0 | active | killed | defined
#0: ToddCoxeter: nodes | 1,288 | 2,401,190 | 2,402,478
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 5,152 | 0 | 100.0%
#0: ToddCoxeter: time | run 0 = 2.013s | all runs = 2.013s | elapsed = 2.013s
#0: ToddCoxeter: triggered because there are skipped definitions (1,288 active nodes)!
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: LOOKAHEAD 0.1 STOP
#0: ToddCoxeter: LOOKAHEAD 0.1.1 | active | killed | defined
#0: ToddCoxeter: nodes | 1,288 | 2,401,190 | 2,402,478
#0: ToddCoxeter: diff 0.1.0 | +0 | +0 | +0
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 5,152 | 0 | 100.0%
#0: ToddCoxeter: diff 0.1.0 | +0 | +0 | +0.0%
#0: ToddCoxeter: phase 0.1 = 391µs | run 0 = 2.014s | all runs = 2.014s | elapsed = 2.014s
#0: ToddCoxeter: lookahead_next() is now max(f x a = 2,576, m = 10,000) (-4,990,000)
#0: ToddCoxeter: because f x a < n
#0: ToddCoxeter: where: a = number_of_nodes_active() = 1,288
#0: ToddCoxeter: f = lookahead_growth_factor() = 2
#0: ToddCoxeter: m = lookahead_min() = 10,000
#0: ToddCoxeter: n = lookahead_next() = 5,000,000
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.2.2 | active | killed | defined
#0: ToddCoxeter: nodes | 1,288 | 2,401,190 | 2,402,478
#0: ToddCoxeter: diff 0.2.1 | +0 | +0 | +0
#0: ToddCoxeter: diff 0.2.0 | +0 | +0 | +0
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 5,152 | 0 | 100.0%
#0: ToddCoxeter: diff 0.2.1 | +0 | +0 | +0.0%
#0: ToddCoxeter: diff 0.2.0 | +0 | +0 | +0.0%
#0: ToddCoxeter: phase 0.2 = 418µs | run 0 = 2.014s | all runs = 2.014s | elapsed = 2.014s
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 STOP (finished)
#0: ToddCoxeter: run 0 | lookahead | lookbehind | hlt | felsch
#0: ToddCoxeter: num. phases | 1 | 0 | 0 | 1
#0: ToddCoxeter: time spent in phases | 414µs (0%) | - (0%) | - (0%) | 2.013s (100%)
#0: ToddCoxeter: phase 0.2 = 437µs | run 0 = 2.014s | all runs = 2.014s | elapsed = 2.014s
The index of the subgroup is 1288
The computed index is the same as the claimed index: \(1,288\).