Demonstration code for the reduction algorithm
This chapter has been written for a mathematically-inclined reader who wants to read an implementation demonstrating the reduction algorithm for the Monster group in [Sey22]. In this section we present a Python implementation of that reduction algorithm. This implementation has been optimized for readability, and not for speed; but it can still be executed and tested.
Our goal is present a satisfactory demonstration of the new reduction algorithm in this chapter of the project documentation. Executable Python code can be found in the mmgoup.demo package. Function reduce_monster_element in the mmgroup.demo.reduce_monster package actually reduces an element of the Monster.
Demonstrating every tiny detail of the reduction algorithm in Python leads to a bloated software package that is hardly readable or executable. So we have to make a compromise, which parts of the reduction algorithm we want to demonstrate.
Following the Pacific island model in [Wil13], we assume that computations in the subgroup \(G_{x0}\) of the Monster (of structure \(2^{1+24}.\mbox{Co}_1\)) are easy enough, so that demonstration code is not needed for them. The relevant computations in \(G_{x0}\) are described in detail in the appendices of [Sey22].
We also assume that functions for the operation of the Monster on its 196884-dimensional representation \(\rho_{15}\) (with coefficients taken modulo 15) are available. This operation is described in detail in [Sey20]. In the mmgroup package we use multiplication for that operation.
We also assume that functions performing linear algebra with matrices over the Leech lattice (modulo 2 and 3) are available.
Section Subfunctions for the reduction algorithm describes the interface of functions implementing the tasks mentioned above.
Warning
Functions and classes presented in Chapter Demonstration code for the reduction algorithm are for demonstration only. They should not be used in a life application!
This demonstration makes some random choices in the reduction process. This is appropriate for testing. The life implementation of the reduction algorithm is deterministic.
Data structures
This section contains the data structures required for the demonstration of the reduction algorithm. These data structures are classes that can be imported from module mmgroup.demo.
- class mmgroup.demo.Mm(tag=None, atom=None, *args, **kwds)
Models an element of the Monster group
Here it would be tempting to use the class
MMdefined in the API reference of the mmgroup package for computing in the Monster instead. Note that methods of classMMmay apply the reduction algorithm whenever appropriate. Hence it would be cheating to demonstrate the reduction algorithm with instances of that class.So we use this class Mm for demonstrating the reduction algorithm for the Monster.
The constructor of the class Mm performs the same action as the constructor of class
MM. The generators of the Monster used here are discussed in [Sey22], Section 3 - 5.But multiplication of instances of class Mm is simply a concatenation of words, without any attempt to reduce the result.
We use the following special cases of calling the constructor:
Calling Mm(‘r’, k) constructs a random word in the generators of the Monster containing k triality elements \(\tau^{\pm 1}\), for an integer k.
Calling the constructor with the string ‘negate_beta’ constructs an element of the normal subgroup \(Q_{x0}\) of the subgroup \(G_{x0}\) of the Monster that exchanges the axes \(v^+\) and \(v^-\) defined in [Sey22], Section 7.2.
- property count_triality_elements
Length of a word representing an element of the Monster
The function returns the number of the triality elements \(\tau^{\pm 1}\) contained in the word representing the group element. This will be used as an indication for the length of the word. This is similar to (although not equal to) the definition of the length of a word in [Wil13].
- class mmgroup.demo.MmV15(vector_name=0)
Models a vector in the representation of the Monster mod 15
The constructor constructs a vector in the representation of the Monster mod 15 depending on the parameter vector_name passed as an argument. If vector_name is the string ‘v+’ or ‘v-’ then we construct the vector \(v^+\) or \(v^-\) defined in [Sey22], Section 7.2, respectively.
If vector_name is the string ‘v1’ then the we construct a precomputed vector \(v_1\) satisfying the requirements in [Sey22], Section 6. The computation of such a vector \(v_1\) is discussed in [Sey22], Appendix B.
Two such vectors in this class may be checked for equality. A vector may be multiplied with an element of the Monster group. Other operations are not supported.
- class mmgroup.demo.Leech2(value)
Models an vector in the Leech lattice mod 2
Such vectors may be added. A vector may be multiplied with an element of the subgroup \(G_{x0}\) of the monster.
Calling the constructor with the string ‘Omega’ or ‘beta’ returns the vector \(\lambda_\Omega\) or \(\lambda_{\beta}\) defined in [Sey22], Section 4.1 or 7.1, respectively.
Calling the constructor with an integer argument returns the element of the Leech lattice mod 2 with that number. Here the numbering is as in class
XLeech2, setting the sign bit to zero.- property type
Return type of vector in Leech lattice mod 2.
The type of a vector is the halved norm of a shortest preimage of the vector in the Leech lattice. That type is equal to 0, 2, 3, or 4.
The reduction algorithm for the Monster group
This module demonstrates the reduction algorithm for the Monster
The main function reduce_monster_element in this module reduces an element of the Monster group. Given an word \(g\) of generators of the Monster of an arbitrary length, the function returns an word \(h\) of generators of the Monster of length at most 7, such that \(g \cdot h\) is the neutral element of the Monster. Here the length of a word is is the number of triality elements \(\tau^{\pm 1}\) contained in that word.
Module mmgroup.demo.reduce_monster requires the following external references.
from mmgroup.demo import Mm, Leech2, MmV15
from mmgroup.demo.reduce_sub import *
from mmgroup.demo.reduce_axis import reduce_axis
from mmgroup.demo.reduce_feasible import reduce_feasible_axis
Here comes the main function reduce_monster_element of the module that reduces an element of the Monster group.
def reduce_monster_element(g):
r"""Reduce an element g of the Monster
:param g: Element of the Monster of arbitrary length
:type g: class Mm
:return: Element h of length at most 7 with g * h == 1
:rtype: class Mm
"""
# Compute h such that g * h is in the subgroup H^+ of the Monster
v_plus = MmV15('v+') * g
h = reduce_axis(v_plus) # Now g * h is in H^+
# Compute h such that g * h is in the subgroup H of G_x0
v_minus = MmV15('v-') * g * h
h = h * reduce_feasible_axis(v_minus) # Now g * h is in H
# Reduce the element g * h in the group G_x0
v_1 = MmV15('v1') * g * h
h = h * reduce_G_x0(v_1) # Now g * h is 1
return h
Here is a simple test function for testing the main function reduce_monster_element.
def check_reduce_monster_element():
r"""Generate a random element g of the Monster and test reduction of g
"""
g = Mm('r', 14) # Random Monster element g
assert g.count_triality_elements == 14 # Check length of g
h = reduce_monster_element(g) # Reduce g; the result is h
assert MmV15('v1') * g * h == MmV15('v1') # Check that g * h is 1
assert h.count_triality_elements <= 7 # Length of h must be <= 7
The following function reduces an element of the subgroup \(G_{x0}\) of the Monster. The implementation of this function is discussed in [Sey22], Section 6.
def reduce_G_x0(v):
r"""Reduce an element g of the subgroup G_x0 of the Monster
:param v: Vector in representation of the Monster, see below
:type v: class MmV15
:return: Element g of G_x0 as defined below
:rtype: class Mm
Let v be a vector in the representation of the Monster
satisfying the conditition
v * g = MmV15('v1')
for an unknown element g of the group G_x0. The function computes
g if such an element g exists. Otherwise it raises an error.
"""
v2 = v.copy() # Local copy of v
# Compute kernel of the matrix corresponding to part 300_x of v;
# that kernel must contain a unique Leech lattice vector l2 of type 4
r3, l2 = mat15_rank_3(v2, 0)
assert r3 == 23 # Rank of 300_x must be 23
# Compute element g1 of G_x0 that transforms l2 to \lambda_\Omega
g1 = map_type4_to_Omega(l2)
v2 = v2 * g1 # Transform v2 with g1
# Now v2 * g2 = MmV15('v1') for a (uinque) element g2 of the group N_x0
g2 = find_in_Nx0(v2) # Finding g2 is easy
assert v * g1 * g2 == MmV15('v1') # This is what we expect
return g1 * g2
Reducing an axis in the Monster
Module mmgroup.demo.reduce_axis demonstrates the reduction of an axis
Here the axes are certain vectors in the representation \(\rho_{15}\) the Monster. The axes are in a one-to-one correspondence with the left cosets of the subgroup \(H^+\) of structure \(2.B\) of the Monster. Thus mapping an arbitrary axis v to the standard axis \(v^+\) corresponding to the subgroup \(H^+\) is equivalent to mapping an element of the Monster to an element of \(H^+\) by right multiplication. For background we refer to [Sey22], Section 7.
The process of finding an element \(g\) that maps axis v to \(v^+\) is called reduction of the axis v. Function reduce_axis in this module reduces an axis v.
We name an orbit of an axis under the action of the subgroup \(G_{x0}\) by a string as in [Sey22], Section 8.2. In the sequel an orbit of an axis means an orbit under the action of \(G_{x0}\). Function axis_orbit in this module computes the orbit of an axis.
For reducing an axis we first multiply an axis with a suitable element of \(G_{x0}\) in order to obtain a ‘nice’ axis in the same orbit. Roughly speaking, an axis is ‘nice’ if multiplication with a suitable power of the triality element \(\tau\) of the Monster maps that axis into a ‘simpler’ orbit.
This way we may repeatedly multiply an axis first with an element of \(G_{x0}\) and then with a power of \(\tau\), leading to a ‘simpler’ orbit in each step of the reduction process, as discussed in [Sey22], Section 8. Possible sequences of orbits obtained during such a reduction process are shown in Figure 2 in [Sey22], Section 8.3.
For each axis \({\bf v}\) there is a set \(U_4({\bf v})\) of vectors in the Leech lattice mod 2 such that for any \(g \in G_{x0}\) the axis \({\bf v} g\) is ‘nice’, if there is an \(l_2 \in U_4({\bf v})\) with \(l_2 g = \lambda_\Omega\). For background we refer to [Sey22], Section 8.3. Function compute_U in this module is used to compute the set \(U_4({\bf v})\). More precisely, calling compute_U(v) returns a set \(U({\bf v})\) of vectors in the Leech lattice mod 2; and \(U_4({\bf v})\) is the set of type-4 vectors contained in that set. Function map_type4_to_Omega in module mmgroup.demo.reduce_sub computes \(g\) from \(l_2\).
At the end of that process we obtain an axis in the orbit ‘2A’. That orbit also contains the axis \(v^+\). Mapping an arbitrary axis in orbit ‘2A’ to the standard axis \(v^+\) is easy.
Module mmgroup.demo.reduce_axis requires the following external references.
from random import choice # returns a random entry of a list
from mmgroup.demo import Mm, Leech2, MmV15 # data strucures used
from mmgroup.demo.reduce_sub import * # functions used
Here is the implementation of function reduce_axis.
def reduce_axis(v):
r"""Return element of Monster reducing an axis v to the standard axis v^+
:param v: The axis to be reduced
:type v: class MmV15
:return: Element g of the Monster with v * g = v^+
:rtype: class Mm
Here v^+ is the standard axis.
"""
v1 = v.copy() # Local copy of axis v
g = Mm(1) # Neutral element of the Monster
# In g we will accumulate the element of the Monster that transforms v
# Map axis to a 'simpler' orbit; see documentation of the module
while True:
orbit = axis_orbit(v1) # Orbit of current axis v
if orbit == '2A':
break # Done if we are in orbit '2A'
# Compute the set U_4(v) and select a random element l2 of that set
U = compute_U(v1)
U_4 = [l2 for l2 in U if l2.type == 4]
l2 = choice(U_4) # A random element of U_4(v)
# Find a Monster element g1 that maps v1 to a 'nice' axis
# and map v1 to that 'nice' axis
g1 = map_type4_to_Omega(l2)
v1 = v1 * g1 # Transform v1 with g1
g = g * g1
assert v * g == v1 # Correctness condition for loop
# Find a Monster element g_tau that maps v1 to a 'simpler' axis,
# and map v1 to that 'simpler' axis
target_orbits = TARGET_ORBITS[orbit] # possible 'simpler' orbits
g_tau = find_triality_element_for_axis(v1, target_orbits)
v1 = v1 * g_tau # Transform v1 with g_tau
g = g * g_tau
assert v * g == v1 # Correctness condition for loop
# Now axis v has been transformed to an axis v1 in orbit '2A'.
# Map the short Leech lattice vector l2 corresponding to axis v1
# to the standard short vector \lambda_\beta.
_, l2 = mat15_rank_3(v1, 2)
g1 = map_type2_to_standard(l2) # g1 transforms l2 to \lambda_\beta
v1 = v1 * g1 # Transform v1 with g1
g = g * g1
# Here Here v1 must be v^+ or v^-
assert v1 in [MmV15('v+'), MmV15('v-')]
if v1 != MmV15('v+'):
G_MINUS = Mm('negate_beta')
v1 = v1 * G_MINUS # Correct v1 if it is equal to v^-
g = g * G_MINUS
assert v * g == MmV15('v+') # This is what we expect
return g
Dictionary TARGET_ORBITS encodes the graph shown in Figure 2 in [Sey22], Section 8.3. The vertices of that graph are orbits of axes.
TARGET_ORBITS = {
'2B' : ['2A'],
'4A' : ['2A'],
'4B' : ['2B'],
'4C' : ['2B'],
'6A' : ['4A'],
'6C' : ['4A'],
'6F' : ['4C'],
'8B' : ['4A'],
'10A' : ['6A'],
'10B' : ['4B', '4C'],
'12C' : ['4B', '6A'],
}
Here is the implementation of function axis_orbit. This function has been implemented according to the discussion of the orbits of axes in [Sey22], Section 8.4.
def axis_orbit(v):
"""Compute the orbit of an axis
:param v: The axis to be checked
:type v: class MmV15
:return: Name of the orbit of axis v
:rtype: str
"""
ORBITS_KNOWN_FROM_NORM = {
2:'8B', 3:'4C', 5:'6C', 10:'12C', 13:'4B'
}
assert isinstance(v, MmV15) and v.p == 15
# Compute norm of the 24 times 24 matrix 300_x contained in vector v (mod 15)
norm = mat15_norm(v)
if norm in ORBITS_KNOWN_FROM_NORM:
# If there is only one orbit with that norm, return that orbit
return ORBITS_KNOWN_FROM_NORM[norm]
elif norm == 4:
# If 300_x has norm 4 then compute the rank r3 of matrix
# M = 300_x - 2 * M_1, where M_1 is the unit matrix
r3, l2 = mat15_rank_3(v, 2)
if r3 == 23:
# If M has rank 23 then we check that the kernel of M
# contains a vector l2 of type 2 in Leech lattice
if l2.type == 2:
# Compute y = transposed(l2) * M * l2 (mod 15)
y = mat15_apply(v, l2)
if y == 4:
return '2A' # Orbit is '2A' if y == 4
elif y == 7:
return '6A' # Orbit is '6A' if y == 7
else:
raise ValueError("Vector is not an axis")
else:
raise ValueError("Vector is not an axis")
elif r3 == 2:
return '10A' # Orbit is '10A' if M has rank 2
else:
raise ValueError("Vector is not an axis")
elif norm == 8:
# If 300_x has norm 8 then compute rank r3 of matrix 300_x
r3, _, = mat15_rank_3(v, 0)
if r3 == 8:
return '2B' # Orbit is '2A' if rank is 8
elif r3 == 24:
return '10B' # Orbit is '10B' if rank is 24
else:
raise ValueError("Vector is not an axis")
elif norm == 14:
# If 300_x has norm 14 then compute rank r3 of matrix 300_x
r3, _, = mat15_rank_3(v, 0)
if r3 == 8:
return '6F' # Orbit is '6F' if rank is 8
elif r3 == 23:
return '4A' # Orbit is '4A' if rank is 23
else:
raise ValueError("Vector is not an axis")
else:
raise ValueError("Vector is not an axis")
Here is the implementation of function compute_U. For an axis v the function computes the set U(v) of vectors in the Leech lattice (mod 2) defined in [Sey22], Section 8.4. The implementation of the function is essentially a rewrite of the discussion of the different cases of axis orbits in that section.
def compute_U(v):
"""Compute a set of Leech lattice vectors from an axis v
For a given axis v the function computes the set U(v) of
vectors in the Leech lattice mod 2, as defined above.
:param v: The axis v
:type v: class MmV15
:return: The set U(v) of vectors in the Leech lattice (mod 2)
:rtype: list[Leech2]
"""
assert isinstance(v, MmV15) and v.p == 15
orbit = axis_orbit(v) # Compute the orbit of axis v
if orbit == '2A':
return []
if orbit == '2B':
return leech2_span(vect15_S(v, 4))
if orbit == '4A':
_, l2 = mat15_rank_3(v, 0)
return [l2]
if orbit in ['4B','4C']:
return leech2_rad(vect15_S(v, 1))
if orbit == '6A':
_, l2 = mat15_rank_3(v, 2)
return [x + l2 for x in vect15_S(v, 5)]
if orbit == '6C':
return leech2_span(vect15_S(v, 3))
if orbit in ['6F', '12C']:
return leech2_rad(vect15_S(v, 7))
if orbit == '8B':
S1 = (vect15_S(v, 1))
l2 = choice(S1) # l2 is a random element of S1
return [l2 + x for x in S1]
if orbit == '10A':
S1 = (vect15_S(v, 1))
S3 = (vect15_S(v, 3))
l2 = S3[0] # S3 is a singleton here
return [l2 + x for x in S1]
if orbit == '10B':
return leech2_rad(vect15_S(v, 4))
raise ValueError('Unknown orbit')
Reducing a feasible axis in the Baby Monster
Module mmgroup.demo.reduce_feasible: reduction of a feasible axis
Here the feasible axes are certain axes in the representation \(\rho_{15}\) of the Monster, see [Sey22], Section 9.1 for details. They are in a one-to-one correspondence with the left cosets of the subgroup \(H = G_{x0} \cap H^+\) in the group \(H^+\) defined in [Sey22].
Thus mapping an arbitrary feasible axis v to the standard feasible axis \(v^-\) corresponding to the subgroup \(H\) is equivalent to mapping an element of \(H^+\) to an element of \(H\) by right multiplication.
The process of finding an element \(g\) in \(H^+\) that maps a feasible axis v to \(v^-\) is called reduction of the feasible axis v. Function reduce_feasible_axis in this module reduces a feasible axis v.
The algorithm in function reduce_feasible_axis for reducing a feasible axis is discussed in [Sey22], Section 9. This algorithm is quite similar to the algorithm in function reduce_axis for reducing a general axis. Analogies between these two algorithms are summarized in Table 2 in that section.
An orbit of \(H^+\) under the action of \(H\) will be called a \(H\)-orbit. As in function reduce_axis, we repeatedly multiply a feasible axis first with an element of \(H\) and then with a power of \(\tau\). This way we will map the axis into a ‘simpler’ \(H\)-orbit in each step of the reduction process.
Details of that reduction process are discussed in [Sey22], Section 9. Possible sequences of \(H\)-orbits obtained during such a reduction process are shown in Figure 3 in that section.
An orbit of the Monster under the action of \(G_{x0}\) will be called a \(G\)-orbit. Note that disjoint \(H\)-orbits lie in disjoint \(G\)-orbits, with the following exceptions. \(H\)-orbits ‘2A0’ and ‘2A1’ are in \(G\)-orbit ‘2A’; and \(H\)-orbits ‘2B0’ and ‘2B1’ are in \(G\)-orbit ‘2B’.
The reduction process mentioned above terminates if the feasible axis is in the \(H\)-orbit ‘2A0’ or ‘2A1’. Orbit ‘2A1’ is the singleton \(\{v^-\}\), so that we are done in that case. Transforming a feasible axis from orbit ‘2A0’ to orbit ‘2A1’ is easy.
Module mmgroup.demo.reduce_feasible requires the following external references.
from mmgroup.demo import Mm, Leech2, MmV15
from mmgroup.demo.reduce_axis import axis_orbit
from mmgroup.demo.reduce_axis import compute_U
from mmgroup.demo.reduce_axis import TARGET_ORBITS
from mmgroup.demo.reduce_sub import*
Here is the implementation of function reduce_feasible_axis.
def reduce_feasible_axis(v):
r"""Return element of Monster reducing a feasible axis v
Here reducing a feasible axis means reduction to the
standard feasible axis v^-.
:param v: The feasible axis to be reduced
:type v: class MmV15
:return: Element g of subgroup H^+ of the Monster with v * g = v^-
:rtype: class Mm
"""
BETA = Leech2('beta') # Vector \lambda_\beta in leech lattice mod 2
OMEGA = Leech2('Omega') # Vector \lambda_\Omega in leech lattice mod 2
v1 = v.copy() # Local copy of the feasible axis v
g = Mm(1) # Neutral element of the Monster
# In g we will accumulate the element of H^+ that transforms v
# Map axis to a 'simpler' orbit
while True:
orbit = axis_orbit(v1)
if orbit == '2A': # Done if we are in orbit '2A1' or '2A0'
break
# Compute the set U_f(v), as defined in [Sey22], Section 9.2;
# and select a random element l2 of that set
U = compute_U(v1)
U_f = [
l2 + BETA for l2 in U if
l2.type == 4 and (l2 + BETA).type == 2
]
l2 = choice(U_f) # A random element of U_f(v)
# Find a Monster element g1 that maps v1 to a 'nice' axis
# and map v1 to that 'nice' (feasible) axis
g1 = map_feasible_type2_to_standard(l2)
v1 = v1 * g1 # Transform v1 with g1
g = g * g1
assert v * g == v1 # Correctness condition for loop
# Find a Monster element g_tau that maps v1 to a 'simpler' axis,
# and map v1 to that 'simpler' (feasible) axis
target_orbits = TARGET_ORBITS[orbit]
g_tau = find_triality_element_for_axis(v1, target_orbits)
v1 = v1 * g_tau # Transform v1 with g_tau
g = g * g_tau
assert v * g == v1 # Correctness condition for loop
# Now v has been transformed to an axis v1 in orbit '2A0' or '2A1'.
# Compute the short Leech lattice vector l2 = \lambda(ax(v2)).
_, l2 = mat15_rank_3(v1, 2)
if l2 == BETA:
# If l2 is \lambda_beta then v1 is in orbit '2A1' and we are done
assert v * g == MmV15('v-') # This is what we expect
return g
# Map v1 to an axis with \lambda(ax(v1)) = \lambda\beta + \lambda\Omega
g1 = map_feasible_type2_to_standard(l2)
g = g * g1
v1 = v1 * g1 # Transform v1 with g1
# Now a power of the triality element maps v1 to the
# standard feasible axis v^-
for e in [1, -1]:
v2 = v1 * Mm('t', e)
if v2 == MmV15('v-'):
g = g * Mm('t', e)
assert v * g == MmV15('v-') # This is what we expect
return g
raise ValueError("Vector is not a feasible axis")
Subfunctions for the reduction algorithm
The Python module mmgroup.demo.reduce_sub contains auxiliary functions required for the reduction on an element of the Monster group.
Most functions in this module correspond to functions defined in [Sey22]. Cross references are given in the documentation of a function.
Implementations of the functions in this module are usually just Python wrappers for the corresponding C functions in the mmgroup package.
- mmgroup.demo.reduce_sub.mat15_norm(v)
Compute norm of a matrix related to a vector in \(\rho_{15}\)
- Parameters:
v (class MmV15) – vector in representation \(\rho_{15}\) of the Monster
Let \(A\) be the 24 times 24 matrix corresponding to part \(300_x\) of vector v. The function returns the norm of the matrix \(A\) (reduced mod 15).
- Returns:
Norm of matrix \(A\) (mod 15)
- Return type:
int
This corresponds to computing \(||M(v)|| \pmod{15}\) in [Sey22], Section 8.2.
- mmgroup.demo.reduce_sub.mat15_apply(v, l2)
Apply matrix related to a vector in \(\rho_{15}\) to Leech lattice vector
- Parameters:
v (class MmV15) – vector in representation \(\rho_{15}\) of the Monster
l2 (class Leech2) – vector in the Leech lattice mod 2 of type 2
Let \(A\) be the 24 times 24 matrix corresponding to part \(300_x\) of vector v.
The function returns \(l_2 A l_2^\top\) (reduced mod 15), where \(l_2\) is any preimage of l2 in the Leech lattice.
- Returns:
\(l_2 A l_2^\top \pmod{15}\)
- Return type:
int
This corresponds to computing \(M(v, l_2) \pmod{15}\) in [Sey22], Section 8.3.
- mmgroup.demo.reduce_sub.mat15_rank_3(v, k)
Compute rank of a matrix related to a vector in \(\rho_{15}\)
- Parameters:
v (class MmV15) – vector in representation \(\rho_{15}\) of the Monster
k (int) – scalar factor for the 24 times 24 unit matrix
Let \(A\) be the 24 times 24 matrix corresponding to part \(300_x\) of vector v. Let \(A_k\) be the matrix \(A\) minus k times the unit matrix, with coefficients taken modulo 3. Matrix \(A_k\) has a natural interpretation as a matrix acting on the Leech lattice (mod 3).
- Returns:
tuple(r, l2) with r the rank of the matrix \(A_k\)
- Return type:
tuple(int, class Leech2)
If the kernel of \(A_k\) is one-dimensional and its preimage in the Leech lattice contains a nonzero vector l3 of type at most 4 then we let l2 be the (unique) vector in the Leech lattice mod 2 with l2 = l3 (mod 2). Otherwise we put l2 = None.
This corresponds to computing the pair \((\mbox{rank}_3(v,k), l_2)\), as defined in [Sey22], Section 8.3, with \(l_2 \in \mbox{ker}_3(v,k)\) if the conditions mentioned above are satisfied.
- mmgroup.demo.reduce_sub.vect15_S(v, k)
Compute Leech lattice vectors related to a vector in \(\rho_{15}\)
- Parameters:
v (class MmV15) – vector in representation \(\rho_{15}\) of the Monster
k (int) – a number 0 < k < 8
The basis vectors of part \(98280_x\) of v are in one-to-one correspondence with the shortest nonzero vectors of the Leech lattice, up to sign. The function returns the list of short Leech lattice vectors such that the corresponding co-ordinate of (part \(98280_x\) of) v has absolute value k (modulo 15).
- Returns:
List of short Leech lattice vectors as described above
- Return type:
list[class Leech2]
This corresponds to computing \(S_k(v)\) in [Sey22], Section 8.3.
- mmgroup.demo.reduce_sub.leech2_span(l2_list)
List vectors in a subspace of the Leech lattice modulo 2
- Parameters:
l2_list (list[class Leech2]) – List of vectors in the Leech lattice mod 2
The function returns the list of all vectors in the Leech lattice mod 2 that are in the subspace spanned by the vectors in the list l2_list.
- Returns:
List of short Leech lattice vectors as described above
- Return type:
list[class Leech2]
This corresponds to computing the set \(\mbox{span}(S)\), as defined in [Sey22], Section 8.3, where \(S\) is the set of vectors given by the list l2_list.
- mmgroup.demo.reduce_sub.leech2_rad(l2_list)
List vectors in a subspace of the Leech lattice modulo 2
- Parameters:
l2_list (list[class Leech2]) – List of vectors in the Leech lattice mod 2
The function returns the list of all vectors in the Leech lattice mod 2 that are in the radical of the subspace spanned by the vectors in the list l2_list. The radical of a subspace is the intersection of that subspace with its orthogonal complement.
- Returns:
List of short Leech lattice vectors as described above
- Return type:
list[class Leech2]
This corresponds to computing the set \(\mbox{rad}(S)\), as defined in [Sey22], Section 8.3, where \(S\) is the set of vectors given by the list l2_list.
- mmgroup.demo.reduce_sub.map_type4_to_Omega(l2)
Map a type-4 vector in the Leech lattice mod 2 to \(\lambda_\Omega\)
- Parameters:
l2 (class Leech2) – Vector of type 4 in the Leech lattice mod 2
The function returns an element \(g\) of the group \(G_{x0}\) that maps the vector l2 of type 4 in the Leech lattice mod 2 to the standard type-4 vector \(\lambda_\Omega\).
- Returns:
group element \(g\) mapping l2 to \(\lambda_\Omega\)
- Return type:
class Mm
An implementation of this function is discussed in [Sey22], Appendix A.
- mmgroup.demo.reduce_sub.map_type2_to_standard(l2)
Map a type-2 vector in Leech lattice mod 2 to \(\lambda_\beta\)
- Parameters:
l2 (class Leech2) – Vector of type 2 in the Leech lattice mod 2
The function returns an element \(g\) of the group \(G_{x0}\) that maps the vector l2 of type 2 in the Leech lattice mod 2 to the standard type-2 vector \(\lambda_\beta\).
- Returns:
group element \(g\) mapping l2 to \(\lambda_\beta\)
- Return type:
class Mm
An implementation of this function is discussed in [Sey22], Appendix C.
- mmgroup.demo.reduce_sub.map_feasible_type2_to_standard(l2)
Map a feasible type-2 vector in the Leech lattice mod 2 to \(\lambda_\beta+\lambda_\Omega\)
- Parameters:
l2 (class Leech2) – Feasible vector of type 2 in the Leech lattice mod 2
The function returns an element \(g\) of the group \(G_{x0}\) that maps the feasible vector l2 of type 2 in the Leech lattice mod 2 to the standard feasible type-2 vector \(\lambda_\Omega + \lambda_\beta\). Here the term feasible is defined in [Sey22], Section 9.1.
- Returns:
group element \(g\) mapping l2 to \(\lambda_\beta+\lambda_\Omega\)
- Return type:
class Mm
An implementation of this function is discussed in [Sey22], Appendix D.
- mmgroup.demo.reduce_sub.find_triality_element_for_axis(v, axis_orbits)
Try to transform an axis in \(\rho_{15}\) into a given axis orbit
- Parameters:
v (class MmV15) – an axis in the representation \(\rho_{15}\) of the Monster
axis_orbits (list[str]) – List of expected types of the transformed axis
Let \(v\) be the axis given by v. The function computes the axes \(v \cdot \tau^e\) for \(e =\pm 1\), where \(\tau\) is the triality element in the Monster.
If possible, the function returns an element \(\tau^e, e = \pm 1\) such that the type of the axis \(v \cdot \tau^e\) is in the list axis_orbits of axis types. Names of axis types are as in [Sey22], Section 8.2.
The function raises ValueError if this is not possible. It does not change the axis stored in v.
- Returns:
An element \(\tau^e\) of the Monster as described above
- Return type:
class Mm
Using function axis_orbit in module mmgroup.demo.reduce_axis this function can be implemented as follows:
def find_triality_element_for_axis(v, axis_orbits) for e in [1, -1]: if axis_orbit(v * Mm('t', e)) in axis_orbits: return Mm('t', e) raise ValueError
The implementation used here is much faster, since it computes fewer co-ordinates of the transformed axes.
- mmgroup.demo.reduce_sub.find_in_Nx0(v)
Identify an element of the subgroup \(N_{x0}\) of the Monster
- Parameters:
v (class MmV15) – vector in representation \(\rho_{15}\) of the Monster
Let \(v_1\) be the precomputed vector in \(\rho_{15}\) defined in the constructor of class
MmV15. Vector v must be an image of \(v_1\) under an element of the subgroup \(N_{x0}\) of the Monster. Then the function returns an element \(g\) of \(N_{x0}\) with \({\bf v} g = v_1\), if such an element \(g\) exists. Otherwise it raises ValueError. Note that at most one element \(g\) of the Monster may satisfy that condition.- Returns:
An element \(g\) of the Monster as described above
- Return type:
class Mm
An implementation of this identification of an element of the group \(N_{x0}\) is described in [Sey22], Section 6. The precomputed vector \(v_1\) satisfies the conditions stated in the same section.