Skip to content

Latest commit

 

History

History
266 lines (154 loc) · 7.14 KB

demo_reduction.rst

File metadata and controls

266 lines (154 loc) · 7.14 KB
Raw

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 Seysen22. 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 Wilson13, we assume that computations in the subgroup Gx0 of the Monster (of structure 21 + 24.Co1) are easy enough, so that demonstration code is not needed for them. The relevant computations in Gx0 are described in detail in the appendices of Seysen22.

We also assume that functions for the operation of the Monster on its 196884-dimensional representation ρ15 (with coefficients taken modulo 15) are available. This operation is described in detail in Seysen20. 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 demonstration-subfunction-label describes the interface of functions implementing the tasks mentioned above.

Warning

Functions and classes presented in Chapter demonstration-label 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.

mmgroup.demo.Mm

mmgroup.demo.MmV15

mmgroup.demo.Leech2

The reduction algorithm for the Monster group

mmgroup.demo.reduce_monster

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.

../../src/mmgroup/demo/reduce_monster.py

Here is a simple test function for testing the main function reduce_monster_element.

../../src/mmgroup/demo/reduce_monster.py

The following function reduces an element of the subgroup Gx0 of the Monster. The implementation of this function is discussed in Seysen22, Section 6.

../../src/mmgroup/demo/reduce_monster.py

Reducing an axis in the Monster

mmgroup.demo.reduce_axis

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.

../../src/mmgroup/demo/reduce_axis.py

Dictionary TARGET_ORBITS encodes the graph shown in Figure 2 in Seysen22, 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 Seysen22, Section 8.4.

../../src/mmgroup/demo/reduce_axis.py

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 Seysen22, 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.

../../src/mmgroup/demo/reduce_axis.py

Reducing a feasible axis in the Baby Monster

mmgroup.demo.reduce_feasible

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.

../../src/mmgroup/demo/reduce_feasible.py

Subfunctions for the reduction algorithm

mmgroup.demo.reduce_sub

mmgroup.demo.reduce_sub.mat15_norm

mmgroup.demo.reduce_sub.mat15_apply

mmgroup.demo.reduce_sub.mat15_rank_3

mmgroup.demo.reduce_sub.vect15_S

mmgroup.demo.reduce_sub.leech2_span

mmgroup.demo.reduce_sub.leech2_rad

mmgroup.demo.reduce_sub.map_type4_to_Omega

mmgroup.demo.reduce_sub.map_type2_to_standard

mmgroup.demo.reduce_sub.map_feasible_type2_to_standard

mmgroup.demo.reduce_sub.find_triality_element_for_axis

mmgroup.demo.reduce_sub.find_in_Nx0