Skip to content

The cyclic subgroup \(\langle ab \rangle\) 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 2 minutes 5 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=\langle ab \rangle\), claimed to be cyclic of order \(23\). Then

\[ [\mathrm{M}_{24}:H] = 10,644,480. \]

We verify this index. The enumeration is over \(H\), so its result is an index rather than the order \(244,823,040\) of M24.

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)^23"), "")
presentation.add_rule(p, parse_relations("(ABab)^12"), "")
# [a, bab] = a^-1 (bab)^-1 a (bab).
presentation.add_rule(p, parse_relations("(ABABabab)^5"), "")
presentation.add_rule(p, parse_relations("(ababaB)^3(abaBaB)^3"), "")
# [a, b^-1 a b a b]^5 = 1, marked redundant in the ATLAS source.
presentation.add_rule(p, parse_relations("(ABABAbaBabab)^5"), "")
presentation.add_rule(p, parse_relations("(ab(abaB)^3)^4"), "")

presentation.replace_word_with_new_generator(p, presentation.longest_subword_reducing_length(p))
presentation.replace_word_with_new_generator(p, presentation.longest_subword_reducing_length(p))
presentation.sort_each_rule(p)
presentation.sort_rules(p)

# Run the Todd-Coxeter algorithm
tc = ToddCoxeter(congruence_kind.onesided, p)

tc.add_generating_pair("ab", "")
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.lower_bound(10644480)
# Cap the reporting interval at one second.
tc.report_every(timedelta(seconds=1))

tc.run_for(timedelta(minutes=10))

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

actual_index = tc.number_of_classes()
print(f"The index of the subgroup is {actual_index}")
if actual_index != 10644480:
    raise RuntimeError(f"expected index 10644480, got {actual_index}")

The output

The original log calls the final value “the size of the group defined by the presentation”. Since the script enumerates over \(\langle ab \rangle\), that value is the subgroup index. The code above uses the corrected label.

Truncated output from the Python script
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: running for approx. 10min0s
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: RUN 0 START (strategy() = felsch)
#0: ToddCoxeter: |A| = 6, |R| = 14, |u| + |v| ∈ [2, 45], ∑(|u| + |v|) = 178
++++++++++++++++++++++++++++++++
#0: ToddCoxeter: FELSCH 0.0 START
#0: ToddCoxeter: FELSCH 0.0.0     |        active |           killed |         defined
#0: ToddCoxeter: nodes            |           101 |               35 |             136
#0: ToddCoxeter:                  |        active |          missing |      % complete
#0: ToddCoxeter: edges            |           157 |              449 |           25.9%
#0: ToddCoxeter: time             | run 0 = 136µs | all runs = 136µs | elapsed = 205µs
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.0.1       |         active |            killed |          defined
#1: ToddCoxeter: nodes              |      1,946,556 |           253,428 |        2,199,994
#1: ToddCoxeter: diff 0.0.0         |     +1,946,455 |          +253,393 |       +2,199,858
[... lines omitted ...]
#0: ToddCoxeter: diff 0.1.124       |             +0 |                +0 |            +0.0%
#0: ToddCoxeter: diff 0.1.0         |    +63,866,723 |              -449 |           +74.1%
#0: ToddCoxeter: phase 0.1 = 2min4s | run 0 = 2min4s | all runs = 2min4s | elapsed = 2min4s
++++++++++++++++++++++++++++++++
#1: ToddCoxeter: FELSCH 0.1.126     |         active |            killed |          defined
#1: ToddCoxeter: nodes              |     10,644,480 |        52,857,227 |       63,501,707
#1: ToddCoxeter: diff 0.1.125       |             +0 |                +0 |               +0
#1: ToddCoxeter: diff 0.1.0         |    +10,644,379 |       +52,857,192 |      +63,501,571
#1: ToddCoxeter:                    |         active |           missing |       % complete
#1: ToddCoxeter: edges              |     63,866,880 |                 0 |           100.0%
#1: ToddCoxeter: diff 0.1.125       |             +0 |                +0 |            +0.0%
#1: ToddCoxeter: diff 0.1.0         |    +63,866,723 |              -449 |           +74.1%
#1: ToddCoxeter: phase 0.1 = 2min5s | run 0 = 2min5s | all runs = 2min5s | elapsed = 2min5s
++++++++++++++++++++++++++++++++
#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%) | 2min4s (99%)
#0: ToddCoxeter: phase 0.1 = 2min5s   | run 0 = 2min5s | all runs = 2min5s | elapsed = 2min5s
The size of the group defined by the presentation is 10644480

The computed index is the claimed index: \(10,644,480\).

Note

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