Skip to content

Mathieu group M22 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}_{22} = {\mathrm{M}_{23}} \mathbin{/} \langle a, b \mid a = bababbab = 1 \rangle \]

with

\[ [\mathrm{M}_{23} : \mathrm{M}_{22}] = 23. \]

Warning

The word \(bababbab\) in plain text on the page

https://brauer.maths.qmul.ac.uk/Atlas/v3/subgroup/M23G1-max1W1

does not seem to generate a subgroup of the correct index. Expanding the GAP straightline programme at:

http://atlas.math.rwth-aachen.de/Atlas/v3/scripts/slp2.php%3Fformat=GAP&filename=M23G1-max1W1&filename_path=spor%252FM23&sub_dir=words

yields the word \(bababbbab\) which does generate a subgroup of the correct index.

The code

In libsemigroups_pybind11, the following script constructs the presentation for M23, adds the generating pairs that define the subgroup M22, and runs the Todd-Coxeter algorithm. This is based on the plain text implementation from the ATLAS.

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("a", "")
tc.add_generating_pair("bababbab", "")

# 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 group is {tc.number_of_classes()}")

In libsemigroups_pybind11, the following script constructs the presentation for M23, adds the generating pairs that define the subgroup M22, and runs the Todd-Coxeter algorithm. This is based on the GAP straightline program hosted on the ATLAS.

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("a", "")
tc.add_generating_pair("bababbbab", "")

# 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 group 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            |           112 |               52 |             164
#0: ToddCoxeter:                  |        active |          missing |      % complete
#0: ToddCoxeter: edges            |           184 |              264 |           41.1%
#0: ToddCoxeter: time             | run 0 = 239µs | all runs = 239µs | elapsed = 315µs
#0: ToddCoxeter: large collapse, number of coincidences 100,000 >= 100,000 = large_collapse()!
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.0 STOP
#0: ToddCoxeter: FELSCH 0.0.1      |        active |           killed |         defined
#0: ToddCoxeter: nodes             |         1,288 |        1,176,014 |       1,177,302
#0: ToddCoxeter: diff 0.0.0        |        +1,176 |       +1,175,962 |      +1,177,138
#0: ToddCoxeter:                   |        active |          missing |      % complete
#0: ToddCoxeter: edges             |         5,152 |                0 |          100.0%
#0: ToddCoxeter: diff 0.0.0        |        +4,968 |             -264 |          +58.9%
#0: ToddCoxeter: phase 0.0 = 980ms | run 0 = 980ms | all runs = 980ms | elapsed = 980ms
++++++++++++++++++++++++++++++++
#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 |        1,176,014 |       1,177,302
#0: ToddCoxeter:                  |        active |          missing |      % complete
#0: ToddCoxeter: edges            |         5,152 |                0 |          100.0%
#0: ToddCoxeter: time             | run 0 = 980ms | all runs = 980ms | elapsed = 980ms
#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 |        1,176,014 |       1,177,302
#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 = 436µs | run 0 = 980ms | all runs = 980ms | elapsed = 980ms
#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 |        1,176,014 |       1,177,302
#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 = 465µs | run 0 = 980ms | all runs = 980ms | elapsed = 980ms
++++++++++++++++++++++++++++++++
#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 |    460µs (0%) |           - (0%) |          - (0%) | 980ms (100%)
#0: ToddCoxeter: phase 0.2 = 498µs    | run 0 = 980ms | all runs = 980ms | elapsed = 980ms
The index of the subgroup is 1288

The computed index is \(1,288\) which is not the same as the claimed index: \(23\).

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            |           113 |               52 |             165
#0: ToddCoxeter:                  |        active |          missing |      % complete
#0: ToddCoxeter: edges            |           178 |              274 |           39.4%
#0: ToddCoxeter: time             | run 0 = 251µs | all runs = 251µs | elapsed = 428µs
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.0 STOP
#0: ToddCoxeter: FELSCH 0.0.1      |        active |           killed |         defined
#0: ToddCoxeter: nodes             |            23 |          880,964 |         880,987
#0: ToddCoxeter: diff 0.0.0        |           -90 |         +880,912 |        +880,822
#0: ToddCoxeter:                   |        active |          missing |      % complete
#0: ToddCoxeter: edges             |            92 |                0 |          100.0%
#0: ToddCoxeter: diff 0.0.0        |           -86 |             -274 |          +60.6%
#0: ToddCoxeter: phase 0.0 = 937ms | run 0 = 937ms | all runs = 937ms | elapsed = 937ms
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: LOOKAHEAD 0.1 START (lookahead_extent() = full, lookahead_style() = hlt)
#0: ToddCoxeter: LOOKAHEAD 0.1.0  |        active |           killed |         defined
#0: ToddCoxeter: nodes            |            23 |          880,964 |         880,987
#0: ToddCoxeter:                  |        active |          missing |      % complete
#0: ToddCoxeter: edges            |            92 |                0 |          100.0%
#0: ToddCoxeter: time             | run 0 = 937ms | all runs = 937ms | elapsed = 937ms
#0: ToddCoxeter: triggered because there are skipped definitions (23 active nodes)!
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: LOOKAHEAD 0.1 STOP
#0: ToddCoxeter: LOOKAHEAD 0.1.1  |        active |           killed |         defined
#0: ToddCoxeter: nodes            |            23 |          880,964 |         880,987
#0: ToddCoxeter: diff 0.1.0       |            +0 |               +0 |              +0
#0: ToddCoxeter:                  |        active |          missing |      % complete
#0: ToddCoxeter: edges            |            92 |                0 |          100.0%
#0: ToddCoxeter: diff 0.1.0       |            +0 |               +0 |           +0.0%
#0: ToddCoxeter: phase 0.1 = 44µs | run 0 = 937ms | all runs = 937ms | elapsed = 937ms
#0: ToddCoxeter: lookahead_next() is now max(f x a = 46, m = 10,000) (-4,990,000)
#0: ToddCoxeter: because f x a < n
#0: ToddCoxeter: where:  a = number_of_nodes_active()     = 23
#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            |            23 |          880,964 |         880,987
#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            |            92 |                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 = 94µs | run 0 = 937ms | all runs = 937ms | elapsed = 937ms
++++++++++++++++++++++++++++++++
#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 |     87µs (0%) |           - (0%) |          - (0%) | 937ms (100%)
#0: ToddCoxeter: phase 0.2 = 119µs    | run 0 = 937ms | all runs = 937ms | elapsed = 937ms
The index of the group is 23

The computed index is the same as the claimed index: \(23\).