r"""We want to find a presentation of the Monster as a Hurwitz group.


Description of the task to be done
..................................

Wilson :cite:`Wil01`  has shown that the Monster group is a 
Hurwitz group, i.e. a group generated by two elements :math:`a, b`
satisfying the relations :math:`a^2 = b^3 = (ab)^7 = 1`. 

In a **MathOverflow** question is has been asked for the
smallest possible order of the commutator
:math:`[a,b] = a^{-1} b^{-1} a b` of :math:`a` and :math:`b` in 
such a presentation of the Monster, see

https://mathoverflow.net/q/363882 .


Using the implementation of the Monster group in the *mmgroup* 
project, it is now possible to find a non-trivial upper bound for 
that commutator. The purpose of this application is to find 
generators  :math:`a, b` of the Monster satisfying the relations 
given above, so that we can compute the order of the 
commutator :math:`[a,b]`.

In :cite:`Wil01`  Wilson has given explicit generators 
:math:`a` (in class 2B) and :math:`b` (in class 3B) of the 
Monster satifying the relations given above. It appears to be 
extremely difficult to translate these two generators from the
language used in :cite:`Wil01`  to the language used in our
*mmgroup* package. Since not all such pairs  :math:`a, b` must be 
isomorphic (via conjugation), we also want to find several such 
pairs. So we have to reimplement the search for such pairs here.

At the time of writing this document we have found  7 pairs of
such generators  :math:`a, b`; and in both cases the commmutator
:math:`[a,b]` has order 39. I thank Gabriel Goller in Augsburg, 
Germany for computing most of these pairs.



Python scripts referred in the following subsections can be found 
in subdirectory ``applications/Hurwitz`` of the repository.

Searching for pairs of generators
.................................

Let :math:`G_{x0}` be the subgroup of the Monster of structure
:math:`2^{1+24}.\mbox{Co}_1` as defined in the **API reference**
of this package, and let :math:`z_{-1}` be
the central involution in that subgroup. Then for generating a 
pair :math:`a, b` as above, we put :math:`a = z_{-1}` . Then we 
search for a random  :math:`g_3 \in G_{x0}` of order 3 with
:math:`\chi_1(g_3) = 53`, so that :math:`g_3` is in class 3B
of the Monster. Here :math:`\chi_1` is the character of degree 
196883 of the Monster. With the *mmgroup* package we can 
compute that character 
in much less than a second. For a fixed  :math:`g_3` we generate 
a large number of (sufficiently) random elements :math:`g_e` of 
the Monster and we put :math:`g = g_e^{-1} g_3 g_e`. If
:math:`z g` has order 7 then :math:`(a, b) = (z, g)` is a 
candidate for a pair of generators, and we store :math:`g_3` 
and :math:`g_e` in a file for further processing.

The python script ``find_generators.py`` searches for pairs
:math:`(a, b)` as above, and stores the corresponding elements  
:math:`g_3, g_e` in file ``Hurwitz_order7.txt``.
Here for checking the order of :math:`a b` we simply check
that :math:`v \cdot (a b)^7 = v` for a random vector :math:`v`
in the 196883-dimensional representation of the Monster
modulo 3.
This is by far the most time-consuming computation in the
whole application. Wilson :cite:`Wil01` reports a success rate of
one over 64 millions for finding a suitable pair. Using
all CPUs of the authors's computer, we can check about 
12 million candidates per day, so that our search has to run 
for about a week.


Verifying pairs of generators
.............................

Given a pair :math:`(a, b)` satisfying the relations
:math:`a^2 = b^3 = (ab)^7 = 1`, we also have to verify that 
:math:`a` and :math:`b` actually generate the Monster group
and not just a proper subgroup of the Monster. Here the 
strategy in :cite:`Wil01` is to compute random elements in the group 
:math:`\langle a, b \rangle` generated by :math:`a` and 
:math:`b`, until one finds an element :math:`h_1` of order 94
and an element :math:`h_2` or order 41, 59, or 71. According
to :cite:`Wil01`, every proper subgroup of the Monster containing an 
element of order 94 is contained in a maximal subgroup of 
structure :math:`2.B`, where :math:`B` is the Baby Monster.
But none of the primes  41, 59, or 71 divides the order of
:math:`B`; so :math:`h_1` and :math:`h_2` generate the Monster.

We compute a certificate for checking that :math:`a` 
and :math:`b` generate the Monster as follows.
Put :math:`H(a, b, n)  = \prod_{i=0}^{63} a b^{1+\nu_i}` for 
elements :math:`a, b` of the Monster, and an integer
:math:`0 \leq n < 2^{64}` with binary representation
:math:`n = \sum_{i=0}^{63} \nu_i \cdot 2^i, \nu_i \in \{0,1\}`. 
If  :math:`a` and :math:`b` 
generate the Monster then we can effectively find integers
:math:`n_1, n_2` such that :math:`H(a, b, n_1)` has order 94
and :math:`H(a, b, n_2)`  has order 41, 59, or 71.

The script ``parse_found.py`` reads the file ``Hurwitz_order7.txt`` 
discussed in the previous section and checks if pair of candidates 
in that file actually generates the Monster. If this is the case 
for a pair then it stores that pair plus a certificate for that
pair in a list in file ``hurwitz_monster_samples.py``. 
Computing such a certificate take a few minutes for a pair
:math:`(a, b)` on the author's computer, which is negligible
compared to the effort for finding such a pair.



Using pairs of generators
.........................

For using a pair of generators of the Monster, the user may
simply import the file ``hurwitz_monster_samples.py``. This file
essentially contains a list of pairs of elements of the Monster, 
so that each of these pairs generates the Monster as a Hurwitz 
group. That list also contains certificates for these pairs as
discussed in the last section.
A precomputed file ``hurwitz_monster_samples.py`` containing
(at least) two such pairs is stored in the ``git`` repository
of the project.

The script ``hurwitz_verify.py`` checks all pairs 
:math:`(a,b)` contained in file ``hurwitz_monster_samples.py``
and displays the order of the commutator :math:`[a,b]`. This
activity takes just a few seconds for each pair.



"""

