Mathieu group M23 (Presentation 1)
The claims on this page come from https://brauer.maths.qmul.ac.uk/Atlas/v3/pres/M23G1-P1.
The Python script includes the additional relation \((abab^2ab^2)^6 = 1\), which its source marks as redundant and useful. We do not verify that this relation is redundant here.
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
\]
with
\[
|\mathrm{M}_{23}| = 10,200,960.
\]
On this page, we verify that the presentation used by the script defines a group of order \(10,200,960\).
The code
In libsemigroups_pybind11, the following script constructs the presentation for M23 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 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^2ab^2)^6"), ""
) # Is redundant, but very useful.
presentation.add_rule(p, parse_relations("(abab^2)^3(ab^2aB)^2abab^2abaBab^2"), "")
presentation.replace_subword(p, "A", "a")
p.alphabet("Bab")
# Run the Todd-Coxeter algorithm
tc = ToddCoxeter(congruence_kind.twosided, p)
tc.strategy(ToddCoxeter.options.strategy.felsch)
# Takes approx. 2.5 minutes
print(f"The size of the group defined by the presentation is {tc.number_of_classes()}")
The output
The truncated output of the enumeration is below:
Truncated output from the Python script
Bab
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 START (strategy() = felsch)
#0: ToddCoxeter: |A| = 3, |R| = 13, |u| + |v| ∈ [2, 48], ∑(|u| + |v|) = 246
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.0 START
#0: ToddCoxeter: FELSCH 0.0.0 | active | killed | defined
#0: ToddCoxeter: nodes | 1 | 0 | 1
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 0 | 3 | 0.0%
#0: ToddCoxeter: time | run 0 = 22µs | all runs = 22µs | elapsed = 66µs
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.1 | active | killed | defined
#1: ToddCoxeter: nodes | 1,822,250 | 36,043 | 1,858,318
#1: ToddCoxeter: diff 0.0.0 | +1,822,249 | +36,043 | +1,858,317
#1: ToddCoxeter: | active | missing | % complete
#1: ToddCoxeter: edges | 4,253,812 | 1,212,938 | 77.8%
#1: ToddCoxeter: diff 0.0.0 | +4,253,812 | +1,212,935 | +77.8%
#1: ToddCoxeter: phase 0.0 = 1.000s | run 0 = 1.000s | all runs = 1.000s | elapsed = 1.000s
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.2 | active | killed | defined
#1: ToddCoxeter: nodes | 3,655,607 | 83,517 | 3,739,139
#1: ToddCoxeter: diff 0.0.1 | +1,833,357 | +47,474 | +1,880,821
#1: ToddCoxeter: diff 0.0.0 | +3,655,606 | +83,517 | +3,739,138
#1: ToddCoxeter: | active | missing | % complete
#1: ToddCoxeter: edges | 8,538,514 | 2,428,307 | 77.9%
#1: ToddCoxeter: diff 0.0.1 | +4,284,702 | +1,215,369 | +0.0%
#1: ToddCoxeter: diff 0.0.0 | +8,538,514 | +2,428,304 | +77.9%
#1: ToddCoxeter: phase 0.0 = 2.001s | run 0 = 2.001s | all runs = 2.001s | elapsed = 2.001s
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.3 | active | killed | defined
#1: ToddCoxeter: nodes | 5,466,932 | 137,547 | 5,604,495
#1: ToddCoxeter: diff 0.0.2 | +1,811,325 | +54,030 | +1,865,356
#1: ToddCoxeter: diff 0.0.0 | +5,466,931 | +137,547 | +5,604,494
#1: ToddCoxeter: | active | missing | % complete
#1: ToddCoxeter: edges | 12,774,618 | 3,626,178 | 77.9%
#1: ToddCoxeter: diff 0.0.2 | +4,236,104 | +1,197,871 | +0.0%
#1: ToddCoxeter: diff 0.0.0 | +12,774,618 | +3,626,175 | +77.9%
#1: ToddCoxeter: phase 0.0 = 3.006s | run 0 = 3.006s | all runs = 3.006s | elapsed = 3.006s
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.4 | active | killed | defined
#1: ToddCoxeter: nodes | 7,294,223 | 190,832 | 7,485,071
#1: ToddCoxeter: diff 0.0.3 | +1,827,291 | +53,285 | +1,880,576
#1: ToddCoxeter: diff 0.0.0 | +7,294,222 | +190,832 | +7,485,070
#1: ToddCoxeter: | active | missing | % complete
#1: ToddCoxeter: edges | 17,048,446 | 4,834,223 | 77.9%
#1: ToddCoxeter: diff 0.0.3 | +4,273,828 | +1,208,045 | +0.0%
#1: ToddCoxeter: diff 0.0.0 | +17,048,446 | +4,834,220 | +77.9%
#1: ToddCoxeter: phase 0.0 = 4.011s | run 0 = 4.011s | all runs = 4.011s | elapsed = 4.011s
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.5 | active | killed | defined
#1: ToddCoxeter: nodes | 9,065,055 | 235,680 | 9,300,749
#1: ToddCoxeter: diff 0.0.4 | +1,770,832 | +44,848 | +1,815,678
#1: ToddCoxeter: diff 0.0.0 | +9,065,054 | +235,680 | +9,300,748
#1: ToddCoxeter: | active | missing | % complete
[... lines omitted ...]
#0: ToddCoxeter: diff 0.1.51 | +0 | +0 | +0
#0: ToddCoxeter: diff 0.1.0 | +0 | +0 | +0
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 30,602,880 | 0 | 100.0%
#0: ToddCoxeter: diff 0.1.51 | +0 | +0 | +0.0%
#0: ToddCoxeter: diff 0.1.0 | +0 | +0 | +0.0%
#0: ToddCoxeter: phase 0.1 = 51.591s | run 0 = 2min29s | all runs = 2min29s | elapsed = 2min29s
#0: ToddCoxeter: lookahead_next() is now max(f x a = 20,401,920, m = 10,000) (+15,401,920)
#0: ToddCoxeter: because a > n
#0: ToddCoxeter: where: a = number_of_nodes_active() = 10,200,960
#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.53 | active | killed | defined
#0: ToddCoxeter: nodes | 10,200,960 | 33,207,284 | 43,408,244
#0: ToddCoxeter: diff 0.2.52 | +0 | +0 | +0
#0: ToddCoxeter: diff 0.2.0 | +0 | +0 | +0
#0: ToddCoxeter: | active | missing | % complete
#0: ToddCoxeter: edges | 30,602,880 | 0 | 100.0%
#0: ToddCoxeter: diff 0.2.52 | +0 | +0 | +0.0%
#0: ToddCoxeter: diff 0.2.0 | +0 | +0 | +0.0%
#0: ToddCoxeter: phase 0.2 = 51.591s | run 0 = 2min29s | all runs = 2min29s | elapsed = 2min29s
++++++++++++++++++++++++++++++++
#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 | 51.591s (35%) | - (0%) | - (0%) | 1min37s (65%)
#0: ToddCoxeter: phase 0.2 = 51.708s | run 0 = 2min29s | all runs = 2min29s | elapsed = 2min29s
The size of the group defined by the presentation is 10200960
The computed size of the group matches the claimed size: \(10,200,960\).