Skip to content

The trivial subgroup of the Mathieu group M12

The presentation comes from the ATLAS of Group Representations. Enumerating over the trivial subgroup computes the order of the group.

The computation

The recorded run took about 581 milliseconds. 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 M12 defines a group of order

\[ [\mathrm{M}_{12}:H] = |\mathrm{M}_{12}| = 95,040. \]

The code

The following script includes the full presentation and can be run on its own.

Code
from datetime import timedelta

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

# Enable the empty word and inverses so the presentation defines 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^3"), "")
presentation.add_rule(p, parse_relations("(ab)^11"), "")
presentation.add_rule(p, parse_relations("(ABab)^6"), "")
presentation.add_rule(p, parse_relations("(ababaB)^6"), "")

tc = ToddCoxeter(congruence_kind.twosided, p)
tc.report_every(timedelta(milliseconds=5))
tc.run_for(timedelta(seconds=10))

if not tc.finished():
    raise RuntimeError("The enumeration did not finish within 10 seconds")

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

The output

Truncated output from the Python script
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: running for approx. 10.000s
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 START (strategy() = hlt)
#0: ToddCoxeter: |A| = 4, |R| = 9, |u| + |v| ∈ [2, 36], ∑(|u| + |v|) = 95
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: HLT 0.0 START
#0: ToddCoxeter: HLT 0.0.0        |       active |          killed |        defined
#0: ToddCoxeter: nodes            |            1 |               0 |              1
#0: ToddCoxeter:                  |       active |         missing |     % complete
#0: ToddCoxeter: edges            |            0 |               4 |           0.0%
#0: ToddCoxeter: time             | run 0 = 22µs | all runs = 22µs | elapsed = 77µs
[... lines omitted ...]
#1: ToddCoxeter:                  |        active |          missing |      % complete
#1: ToddCoxeter: edges            |       380,160 |                0 |          100.0%
#1: ToddCoxeter: diff 0.3.8       |            +0 |               +0 |           +0.0%
#1: ToddCoxeter: diff 0.3.0       |           -17 |               -7 |           +0.0%
#1: ToddCoxeter: phase 0.3 = 38ms | run 0 = 580ms | all runs = 580ms | elapsed = 580ms
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 STOP (finished)
#0: ToddCoxeter: run 0                |     lookahead |       lookbehind |             hlt |       felsch
#0: ToddCoxeter: num. phases          |             1 |                0 |               2 |            0
#0: ToddCoxeter: time spent in phases |   343ms (59%) |           - (0%) |     207ms (36%) |       - (0%)
#0: ToddCoxeter: phase 0.3 = 40ms     | run 0 = 581ms | all runs = 581ms | elapsed = 581ms
The size of the group defined by the presentation is 95040

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

Note

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