Skip to content

The trivial subgroup of Mathieu group M24

The presentation comes from the ATLAS Magma file, with the additional relation \([a,b^{-1}abab]^5=1\) enabled as in the overview. The ATLAS source marks this relation as redundant. We do not verify that this relation is redundant here.

The computation

The recorded run took about 1 hour 45 minutes 42 seconds. The animation shows its progress, with the number of active nodes and the proportion of defined edges.

Progress of the Todd–Coxeter computation.

Claim

Let \(H\) be the trivial subgroup. We verify that the presentation of M24, including the additional relation described above, defines a group of order

\[ [\mathrm{M}_{24}:H] = |\mathrm{M}_{24}| = 244,823,040. \]

The code

The following script includes the full presentation and can be run on its own. It uses only the generators a and b; inverses are expressed using \(a^{-1}=a\) and \(b^{-1}=b^2\).

Code
from datetime import timedelta

from libsemigroups_pybind11 import (
    Presentation,
    ToddCoxeter,
    congruence_kind,
    presentation,
)
from libsemigroups_pybind11.words import parse_relations

# The empty word and a^2 = b^3 = 1 allow this presentation to define a group.
p = Presentation("ab")
p.contains_empty_word(True)

# Add the defining relations
presentation.add_rule(p, parse_relations("a^2"), "")
presentation.add_rule(p, parse_relations("b^3"), "")
presentation.add_rule(p, parse_relations("(ab)^23"), "")
presentation.add_rule(p, parse_relations("(abbab)^12"), "")
presentation.add_rule(p, parse_relations("(abbabbabab)^5"), "")
presentation.add_rule(p, parse_relations("(abababb)^3(ababbabb)^3"), "")
presentation.add_rule(
    p, parse_relations("(abbabbababbabab)^5"), ""
)  # redundant, but quite useful.
presentation.add_rule(p, parse_relations("(ab(ababb)^3)^4"), "")

if __name__ == "__main__":
    # Enumerate the whole group, without imposing any subgroup generators.
    tc = ToddCoxeter(congruence_kind.twosided, p)
    tc.strategy(tc.options.strategy.felsch)
    tc.def_version(tc.options.def_version.two)
    tc.use_relations_in_extra(True)
    tc.def_max(10000)
    tc.lower_bound(244823040)
    # Cap the reporting interval at one second.
    tc.report_every(timedelta(seconds=1))

    actual_order = tc.number_of_classes()
    print(f"The size of the group defined by the presentation is {actual_order}")
    if actual_order != 244823040:
        raise RuntimeError(f"expected order 244823040, got {actual_order}")

The output

Truncated output from the Python script
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 START (strategy() = felsch)
#0: ToddCoxeter: |A| = 2, |R| = 8, |u| + |v| ∈ [2, 75], ∑(|u| + |v|) = 349
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.0 START
#0: ToddCoxeter: FELSCH 0.0.0     |        active |           killed |         defined
#0: ToddCoxeter: nodes            |           286 |               21 |             307
#0: ToddCoxeter:                  |        active |          missing |      % complete
#0: ToddCoxeter: edges            |           298 |              274 |           52.1%
#0: ToddCoxeter: time             | run 0 = 291µs | all runs = 291µs | elapsed = 357µs
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.1       |         active |            killed |          defined
#1: ToddCoxeter: nodes              |      1,760,116 |            47,675 |        1,807,814
#1: ToddCoxeter: diff 0.0.0         |     +1,759,830 |           +47,654 |       +1,807,507
#1: ToddCoxeter:                    |         active |           missing |       % complete
#1: ToddCoxeter: edges              |      2,961,491 |           558,741 |            84.1%
[... lines omitted ...]
#1: ToddCoxeter: diff 0.1.6294          |                 +0 |                    +0 |                +0.0%
#1: ToddCoxeter: diff 0.1.0             |       +489,645,782 |                  -274 |               +47.9%
#1: ToddCoxeter: phase 0.1 = 1h45min41s | run 0 = 1h45min41s | all runs = 1h45min41s | elapsed = 1h45min41s
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.1.6296        |             active |                killed |              defined
#1: ToddCoxeter: nodes                  |        244,823,040 |           313,710,991 |          558,534,031
#1: ToddCoxeter: diff 0.1.6295          |                 +0 |                    +0 |                   +0
#1: ToddCoxeter: diff 0.1.0             |       +244,822,754 |          +313,710,970 |         +558,533,724
#1: ToddCoxeter:                        |             active |               missing |           % complete
#1: ToddCoxeter: edges                  |        489,646,080 |                     0 |               100.0%
#1: ToddCoxeter: diff 0.1.6295          |                 +0 |                    +0 |                +0.0%
#1: ToddCoxeter: diff 0.1.0             |       +489,645,782 |                  -274 |               +47.9%
#1: ToddCoxeter: phase 0.1 = 1h45min42s | run 0 = 1h45min42s | all runs = 1h45min42s | elapsed = 1h45min42s
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 STOP (finished)
#0: ToddCoxeter: run 0                  |          lookahead |            lookbehind |                  hlt |            felsch
#0: ToddCoxeter: num. phases            |                  0 |                     0 |                    0 |                 1
#0: ToddCoxeter: time spent in phases   |             - (0%) |                - (0%) |               - (0%) | 1h45min14s (100%)
#0: ToddCoxeter: phase 0.1 = 1h45min42s | run 0 = 1h45min42s | all runs = 1h45min42s | elapsed = 1h45min42s
The size of the group defined by the presentation is 244823040

The computed order is the claimed order: \(244,823,040\).

Note

The output and timings may vary between machines, but the final result should be the same.