The mmgroup API reference

Introduction

In the area of mathematics known as group theory, the Monster group \(\mathbb{M}\) is the largest finite sporadic simple group. It has order

\(2^{46} \cdot 3^{20} \cdot 5^9 \cdot 7^6 \cdot 11^2 \cdot 13^3 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 41 \cdot 47 \cdot 59 \cdot 71\) = \(\small 808.017.424.794.512.875.886.459.904.961.710.757.005.754.368.000.000.000\) .

The Monster group has first been constructed by Griess [Gri82]. That construction has been simplified by Conway [Con85]. For more information about the Monster group we refer to [Wik23].

The mmgroup package is a Python implementation of Conway’s construction [Con85] of the Monster group \(\mathbb{M}\). Its is the first implementation of the Monster group where arbitrary operations in that group can effectively be performed. On the author’s PC (Intel i7-8750H at 4 GHz running on 64-bit Windows) the group multiplication in \(\mathbb{M}\) takes less than 30 ms. This is more than five orders of magnitude faster than estimated in 2013 in [Wil13].

The Monster group \(\mathbb{M}\) has a rational representation \(\rho\) of dimension \(196884\), see [Con85]. In that representation the denominators of the matrix coefficients are powers of two. So reducing these coefficients modulo a small odd prime \(p\) leads to a representation \(\rho_p\) of \(\mathbb{M}\) over the finite field \(\mathbb{F}_p\).

The mmgroup package uses highly optimized C programs for calculating in such representations \(\rho_p\) of the Monster \(\mathbb{M}\). The main ingredient for speeding up the computation in \(\mathbb{M}\) is the calculation and the analysis of the images of certain vectors in \(\rho_p\) that are called 2A axes in [Con85].

In the description of the mmgroup package we use the notation in [Sey20], where an explicit generating set of the Monster \(\mathbb{M}\) is given. For a mathematical description of the implementation we refer to [Sey22].

Installation and test

Installation on 64-bit Windows

For installing the mmgroup package on a 64-bit Windows system, python 3 must be installed. Then type:

pip install mmgroup
pip install pytest
python -m pytest --pyargs mmgroup -m "not slow"

The last command tests the installation.

Installation on Linux and macOS with a 64-bit x86 CPU

For installing the mmgroup package on a Linux or macOS system, python 3 must be installed. Then type:

pip3 install mmgroup
pip3 install pytest
python3 -m pytest --pyargs mmgroup -m "not slow"

The last command tests the installation.

Other platforms

For other platforms the package must be compiled from a source distribution. Therefore the cibuildwheel tool may be used, see Building the mmgroup package with cibuildwheel.

A general description of the build process is given in the Guide for developers of the project documentation.

Basic structures

Conway’s construction of the Monster group starts with the extended binary Golay code \(\mathcal{C}\), which is a 12-dimensional linear subspace of the 24-dimensional vector space \(\mathbb{F}_2^{24}\). The Golay code has Hamming distance 8. Its automorphism group is the Mathieu group \(M_{24}\), which is a simple group operating as a permutation group on 24 points. These points are identified with the basis vectors of \(\mathbb{F}_2^{24}\).

Module mmgroup contains fast C routines for computing with the Golay code \(\mathcal{C}\), its cocode \(\mathcal{C^*}\), and the Mathieu group \(M_{24}\). There are Python classes for a more convenient handling of these objects that wrap these C functions; these classes are described in this section.

In this section we also describe Python classes modelling more complicated mathematical structures. One of these structures is the Parker loop \(\mathcal{P}\), which is a non-associative loop that can be constructed as a double cover of the Golay code \(\mathcal{C}\). We also consider a group \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) of automorphisms of \(\mathcal{P}\), which has structure \(2^{12}.M_{24}\). Here the normal subgroup of \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) or order \(2^{12}\) is isomorphic to the Golay cocode \(\mathcal{C^*}\).

Another important ingredient of the construction of the Monster is the Leech lattice \(\Lambda\), which is the densest lattice in dimension 24. We also consider the Leech lattice modulo 2, which we denote by \(\Lambda / 2 \Lambda\), and the automorphism group \(\mbox{Co}_1\) of \(\Lambda / 2 \Lambda\), which is simple.

The Golay code and its cocode

We deal with the Golay code and its cocode.

Let \(\tilde{\Omega}\) be the set of integers \(\{ i \in \mathbb{Z} \mid 0 \leq i < 24\}\) of size \(24\) and construct the vector space \(\mathcal{V} = \mathbb{F}_2^{24}\) as \(\prod_{i\in \tilde{\Omega}} \mathbb{F}_2\). In this document elements of \(\mathcal{V}\) are called bit vectors. We represent bit vectors as instances of class GcVector.

We identify the power set of \(\tilde{\Omega}\) with the vector space \(\mathcal{V} = \mathbb{F}_2^{24}\) by mapping each subset of \(\tilde{\Omega}\) to its characteristic function, which is a bit vector in \(\mathcal{V}\). So we may talk about union and intersection of bit vectors in a natural way and use the python operators | and & for these operations as usual. We use the + operator for vector addition of bit vectors. Bit vectors are numbered from 0 to 0xffffff, with bit i of that number corresponding to the i-th unit vector.

The Golay code \(\mathcal{C}\) is a \(12\)-dimensional linear subspace of \(\mathcal{V}\) such that a nonzero vector in \(\mathcal{C}\) has weight at least \(8\). This characterizes the Golay code up to permutation. In this package we chose a specific basis of the Golay code that satisfies the requirements in [Sey20], see The basis of the Golay code and of its cocode for details. We represent Golay code words as instances of class GCode. Golay code words of weight \(8\) and \(12\) are called octads and dodecads, respectively.

We stress that class GCode is not a subclass of class GcVector. Instances of these two classes are numbered in a different way. Golay code words are numbered from 0 to 0xfff with bit i of that number corresponding to the i-th basis vector of the Golay code. See The basis of the Golay code and of its cocode for the chosen basis of the Golay code.

The Golay cocode \(\mathcal{C}^*\) is the 12-dimensional quotient space \(\mathbb{F}_2^{24} / \mathcal{C}\). For any \(\delta \in \mathcal{C}^*\) the weight of \(\delta\) is the weight of its lightest representative in \(\mathbb{F}_2^{24}\). That weight is at most 4. There is a unique lightest representative it the weight is less than 4, and there are six mutually disjoint lightest representatives of an element of weight 4. A partition of \(\mathbb{F}_2^{24}\) given by such a set of disjoint representatives is called a tetrad. We represent elements of the cocode of the Golay code as instances of class Cocode. Cocode elements are numbered from 0 to 0xfff with bit i of that number corresponding to the i-th basis vector of the cocode. Our basis of the cocode is the reciprocal basis of the basis of the Golay code, see The basis of the Golay code and of its cocode for details.

The scalar product of a Golay code word and a cocode element is the parity of the intersection of the Golay code word and any representative of the cocode element. If g is an instance of class GCode and d is an instance of class Cocode then g & d is an instance of class Parity. Here class Parity models an integer modulo 2, which is also considered as the parity of a bit vector. Standard operations, e.g. (-1)**p, work as expected for an instance p of class Parity.

The standard function len(x) returns the (minimal) weight |x| of an instance x of class GcVector, GCode or Cocode. For instances g1, g2, g3 of class GCode, the expression g1 & g2 is an instance of class Cocode and g1 & g2 & g3 an instance of class Parity; these values have a natural interpretations as bitwise intersections. g1/4 is a shorthand for Parity(len(g1)/4); and (g1 & g2)/2 is a shorthand for Parity(len(g1 & g2)/2). These two expressions are called the power map and the commutator, respectively, in [Asc86]; and g1 & g2 & g3 is called the associator in [Asc86].

The numbering of the Golay code words and of the cocode elements is important for indexing some generators of \(\mathbb{M}\) and also some basis vectors in the representations \(\rho_p\) of \(\mathbb{M}\).

class mmgroup.GCode(value)

This class models a code word of the Golay code.

The Golay code is a binary [24, 12, 8] code. So there are \(2^{12}\) code words, each word is \(24\) bit long, and the Hamming distance between two different code words is at least \(8\).

The \(2^{12}\) Golay code words are numbered from 0 to 0xfff. Bit i in that number refers to the coefficient of the i-th basis vector of the Golay code, which may be \(0\) or \(1\).

Parameters:

value (see table below for legal types) – This is the value of the Golay code word to be returned.

Returns:

A Golay code vector

Return type:

an instance of class GCode

Raise:

TypeError if type(value) is not in the table given below.
ValueError if value cannot be converted to an instance of class GCode.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class `GCode`
type	Evaluates to
`int`	Here the code word with number `value` is returned. `0 <= value < 0x1000` must hold.
`list` of `int`	A list of integers `0 <= i < 24` is interpreted as a list of bit positions to be set in a bit vector. The Golay code word corresponding to that bit vector is returned. Up to `3` erroneous bits are corrected.
class `GCode`	A deep copy of parameter `value` is returned.
class `PLoop`	The Parker loop element `value` is converted to a Golay code word (by dropping its sign) and returned.
class `GcVector`	The bit vector `value` of type `GcVector` is converted to a Golay code word and returned. Up to `3` erroneous bits in that vector are corrected.
class `XLeech2`	The Golay code part of the `XLeech2` object is converted to a Golay code word and returned.
`str`	Create random element depending on the string `'r'`: Create arbitrary Golay code word

Standard operations

Addition of Golay code words and scalar multiplication (with scalars of type int or Parity) are done as usual.

The bitwise and operator & means bitwise and of two code words of type GCode. The result of such an operation on two Golay code words is a Golay cocode word of type Cocode.

The bitwise & operator of a Golay code word and a Golay cocode word of type Cocode is not well defined as a bit vector, but it has a well-defined parity. So in this case the result of the & operator is a parity object of type Parity.

For the bitwise & operator bit vectors of type GcVector, see class GcVector.

The ~ operator means bitwise complement as usual; it returns the complemented code word, which is also of type GCode.

Standard functions

len(g) returns the bit weight of the Golay code word g, i.e. the number of bits set in the word g.

Special functions

Let g1, g2, and g3 be Golay code vectors of type GCode.

The expression g1/4 is a shorthand for Parity(len(g1)/4). It returns len(g1)/4 modulo 2 as a parity object of type Parity.

GcVector(g1 & g2) returns the bitwise intersection of g1 and g2 as a bit vector of type GcVector.

(g1 & g2)/2 is a shorthand for Parity(len(GcVector(g1 & g2))/2). It returns the halved bit weight of g1 & g2 modulo 2 as a parity object of type Parity. This value is also called the commutator of g1 and g2.

g1 & g2 & g3 returns the parity of the bitwise intersection of g1, g2, and g3 as a parity object of type Parity. This value is also called the associator of g1, g2, and g3.

abs(g1) is a shorthand for abs(PLoop(g1)), see class PLoop for details.

property bit_list: Return the ordered list of positions of bits being set

property bits

Return the Golay code word as a 24-bit vector.

The function returns a list with 24 entries equal to 0 or 1.

property gcode

Return the number of the Golay code word.

Same as property ord.

property octad

Return number of octad of the Golay code word as an octad.

Complements of octads are also accepted as octads. We have 0 <= o < 759 for the returned number o.

Raise:

ValueError if the Golay code word is not an octad.

property ord

Return the number of the Golay code word.

We have 0 <= i < 0x1000 for the returned number i.

split()

Split the Golay code word g.

Returns:: A triple (0, eo, v) with g = Omega * eo + v.

Here Omega is the Golay code word containing one bits only, eo is 0 or 1, and v is a Golay code word of type GCode with 0 <= v1.ord < 0x800.

This method is for compatibility with the corresponding method in class PLoop.

split_octad()

Split an octad from the Golay code word g.

Returns:: A triple (0, eo, o) with g = Omega * eo + o.

Here Omega is the Golay code word containing one bits only, eo is 0 or 1, and v is a Golay code word of type GCode which is either the zero code word or an octad, i.e. a code word of weight 8.

This method is for compatibility with the corresponding method in class PLoop.

Raise:

ValueError if this is not possible.

theta(g2=None)

Return cocycle of Golay code words.

The cocycle theta maps a pair of Golay code words to an integer modulo 2. It is linear in its second argument, so it may also be considered as a mapping from the Golay code to the cocode of the Golay code.

Parameters:

g2 – None (default) or another Golay code word of type GCode.

Returns:

If g2 is a code word of type GCode, we return the value g1.theta(g2) = theta(g1, g2) as a Parity object.
If g2 is None (default), we return the value g1.theta() = theta(g1) as a Cocode object. Note that g1.theta(g2) == g1.theta() & g2 .

The importance of the theta function comes from the fact that the multiplication of elements of the Parker loop is based on the cocycle. We embed the set of Golay code words into the set of positive Parker loop elements, which are instances of class PLoop.

Let g1 and g2 be Golay code words of type GCode. Then PLoop(g1) and PLoop(g2) are the corresponding positive Parker loop elements, and g1.theta(g2) is an integer modulo 2 of type Parity. We have:

PLoop(g1) * PLoop(g2) == (-1)**g1.theta(g2) * PLoop(g1 + g2) .

property vector

Return bit vector corresponding to the Golay code word as an int.

We have 0 <= v < 0x1000000 for the returned number v. Bit i of the number v is the i-th coordinate of the corresponding bit vector.

class mmgroup.GcVector(value)

Models a 24-bit vector in the underlying space of the Golay code.

The \(2^{24}\) bit vectors are numbered from 0 to 0xffffff. Bit i in that number refers to the coefficient of the i-th basis vector of the vector space, which may be \(0\) or \(1\).

Parameters:

value (see table below for legal types) – This is the value of the bit vector to be returned.

Returns:

A bit vector of 24 bit length.

Return type:

an instance of class GcVector

Raise:

TypeError if type(value) is not in the table given above.
ValueError if value cannot be converted to an instance of class GcVector.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class `GcVector`
type	Evaluates to
`int`	Here the bit vector with number `value` is returned. `0 <= value < 0x1000000` must hold.
`list` of `int`	A list of integers `0 <= i < 24` is interpreted as a list of bit positions to be set in a bit vector. That bit vector is returned.
class `GCode`	The bit vector corresponding to the Golay code word `value` is returned.
class `PLoop`	The Parker loop element `value` is converted to a Golay code word (by dropping its sign) and then to a bit vector. That bit vector is returned.
class `GcVector`	A deep copy of parameter `value` is returned.
`str`	Create random element depending on the string `'r'`: Create arbitrary bit vector

Standard operations

Addition of bit vectors and scalar multiplication (with scalars of type int or Parity) are done as usual. The sum of a bit vector and a Golay code word (of type GCode) is a bit vector. The sum of a bit vector and a cocode word (of type Cocode) is a cocode word of type Cocode.

The bitwise and operators &, |, and ~ operate on two bit vectors as expected. If the other operand is a Golay code vector (of type GCode) then it is converted to a bit vector.

Standard functions

len(v) returns the bit weight of the bit vector v, i.e. the number of bits set in the vector v.

property bit_list: Return the ordered list of positions of bits being set

property bits

Return the Golay code word as a 24-bit vector.

Returns a list with 24 entries equal to 0 or 1.

property cocode: Return number of the cocode word corresponding to the vector.

property gcode

Return number of Golay code word corresponding to the bit vector

Raise:

ValueError if the bit vector is not an Golay code word.

property octad

If the bit vector is an octad, return the number of that octad

Complements of octads are also accepted as octads.

Raise:

ValueError if the bit vector is not an octad.

property ord

Return the number of the bit vector.

We have 0 <= i < 0x1000000 for the returned number i.

syndrome(i=None)

Return syndrome of cocode element as a bit vector.

Parameters:

i – None (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns:

Syndrome of a Golay cocode element as a bit vector of type GcVector.

Raise:

ValueError if argument i is None and the syndrome is not unique.

v.syndrome(i) is equivalent to Cocode(v).syndrome(i).

syndrome_list(i=None)

Return syndrome of cocode element as list of bit positions.

Parameters:

i – None (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns:

Syndrome of a Golay cocode element as a list of at most four bit positions.

Raise:

ValueError if argument i is None and the syndrome is not unique.

The syndrome of the Golay cocode element is calculated in the same way as in method syndrome. But here the result is returned as an ordered list of bit positions corresponding to the bits which are set in the syndrome.

v.syndrome_list(i) is equivalent to Cocode(v).syndrome_list(i).

property vector

Return the number of the bit vector.

We have 0 <= i < 0x1000000 for the returned number i.

Same as property ord.

class mmgroup.Cocode(value)

This class models an element of the cocode of the Golay code.

The Golay code is a binary [24, 12, 8] code. So its cocode has \(2^{12}\) elements, each of it is a \(24\) bit long word (modulo the Golay code).

The \(2^{12}\) Golay cocode elements are numbered from 0 to 0xfff. Bit i in that number refers to the coefficient of the i-th basis vector of the Golay cocode, which may be \(0\) or \(1\). The chosen basis of the cocode is the reciprocal basis of the chosen basis of the Golay code.

Parameters:

value (see table below for legal types) – This is the value of the Golay cocode word to be returned.

Returns:

A Golay cocode element

Return type:

an instance of class Cocode

Raise:

TypeError if type(value) is not in the table given below.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class `Cocode`
type	Evaluates to
`int`	Here the cocode element with number `value` is returned. `0 <= value <= 0x1000` must hold.
`list` of `int`	A list of integers `0 <= i < 24` is interpreted as a list of bit positions to be set in a bit vector. The cocode word corresponding to that bit vector is returned.
class `Cocode`	A deep copy of parameter `value` is returned.
class `XLeech2`	The cocode part of the `XLeech2` object is converted to a cocode element and returned.
`str`	Create random element depending on the string `'r'`: Create arbitrary cocode element `'e'`: Create an even cocode element `'o'`: Create an odd cocode element

Standard operations

Addition of cocode elements and scalar multiplication (with scalars of type int or Parity) are done as usual.

g & c and c & g are legal operations for a Golay code element g of type GCode and a cocode element c of type Cocode. The result of this operation is not well defined as a bit vector, but it has a well-defined parity. Thus g & c returns a parity object of type Parity.

Standard functions

Let c be a cocode element of type Cocode. len(c) returns the bit weight of a shortest representative of the Golay code element c.

Special functions

The expression c % 2 is a shorthand for Parity(len(c)). It returns the parity of c as a parity object of type Parity.

property cocode

Return the number of the cocode element.

We have 0 <= i < 0x1000 for the returned number i.

Same as property ord.

property ord

Return the number of the cocode element.

We have 0 <= i < 0x1000 for the returned number i.

property parity: Return parity of the cocode element as a Parity object.

syndrome(i=None)

Return syndrome of cocode element as a bit vector.

Parameters:

i – None (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns:

Syndrome of a Golay cocode element as a bit vector of type GcVector.

Raise:

ValueError if argument i is None and the syndrome is not unique.

Any Golay cocode element has either a unique shortest representative of bit weight <= 3 or precisely six shortest representatives of bit weight 4 which form a partition of the underlying set of the code. Such a partition is called a tetrad.

In coding theory, a shortest representative of a cocode element is called a syndrome.

If the syndrome is unique, the function returns that syndrome. Otherwise it returns the syndrome containing bit at position i.

syndrome_list(i=None)

Return syndrome of cocode element as list of bit positions.

Parameters:

i – None (default) or an integer 0 <= i < 24 used to select a syndrome.

Returns:

Syndrome of a Golay cocode element as a list of at most four bit positions.

Raise:

ValueError if argument i is None and the syndrome is not unique.

The syndrome of the Golay cocode element is calculated in the same way as in method syndrome. But here the result is returned as an ordered list of bit positions corresponding to the bits which are set in the syndrome.

syndromes_llist()

Return shortest syndromes of cocode element as list of lists.

The function returns the list of all shortest representatives of the cocode element as a list ll of lists. Each entry of ll corresponds to a shortest representative. Such an entry is an ordered list of bit positions corresponding to the bits which are set in the representative. Output ll is sorted in natural order.

class mmgroup.Parity(value)

This class models the parity of a bit vector.

As one might expect, the parity of a bit vector may be odd or even, and it is an element of the field GF(2) of two elements.

This means that arithmetic operations +, -, and * work as expected on instances of class Parity, or on instances of this class combined with integers.

The values 1**p and (-1)**p are defined as usual for an object p of class Parity. Similarly, g**p is defined if g is an element of a group defined in this package and has order 1 or 2. More precisely, g must be an instance of class AbstractGroupWord here.

Bitwise operations &, |, and ^ are illegal on instances of class Parity.

Parity(x) is defined if x an integer, an instance of class Parity, or an instance of any class defined is this package which has a natural parity, e.g. an instance of class GcVector or Cocode.

int(p) evaluates to 0 or 1 for an instance of class Parity.

Implementation remarks

If an object x has an attribute or a property parity then Parity(x) means Parity(x.parity) and x + p means Parity(x) + p for any instance p of class Parity.

If an object x has an attribute or a property parity_class then x * p and p * x mean Parity(parity_class(x) * int(p)). If that attribute or a property has value True then x * p and p * x mean Parity(x * int(P)).

property ord: Return 1 if the parity is odd and 0 if it is even

The Parker loop

We deal with the Parker loop, which is a non-associative Moufang loop.

The Parker loop is written multiplicatively its elements can be represented as pairs in the set \(\mathcal{P} = \mathcal{C} \times \mathbb{F}_2\), see e.g. [Asc86], [Con85]. We also write 1 for the neutral element \((0,0) \in \mathcal{C} \times \mathbb{F}_2 = \mathcal{P}\) of the Parker loop and -1 for its negative \((0,1)\). Let \(\Omega\) = \((\tilde{\Omega}, 0)\), where \(\tilde{\Omega}\) is the Golay code word 1,...,1. Then the center \(Z(\mathcal{P})\) of \(\mathcal{P}\) is \(\{1, -1, \Omega, -\Omega\}\). An element \((g,s)\), \(g \in \mathcal{C}\) is called positive if \(s = 0\) and negative if \(s = 1\).

Multiplication of two Parker loop elements \((g_1,s_1), (g_2,s_2)\) is given by a cocycle \(\theta: \mathcal{C} \times \mathcal{C} \rightarrow \mathbb{F}_2\) as follows:

\((g_1,s_1) \cdot (g_2,s_2) = (g_1 + g_2, s_1 + s_2 + \theta(g_1, g_2))\).

There are several possibilities for the cocycle \(\theta\). We choose a cocycle \(\theta\) satisfying the requirements given by [Sey20], see The basis of the Golay code and of its cocode for details.

We represent elements of \(\mathcal{P}\) as instances of class PLoop. For Golay code word g given as an instance of class GCode, the value PLoop(g) is the positive element (g,0) of the Parker loop, and -PLoop(g) is the corresponding negative element (g,1). The constant PLoopOne is equal to the neutral element (0,0) and the constant PLoopOmega is equal to the central element ~PLoopOne. Here the ~ means bitwise complement of the corresponding Golay code element without changing the sign of a Parker loop element. Thus PLoopOmega is the positive Parker loop element corresponding to the Golay code word containing 24 one bits. So the center \(Z(\mathcal{P})\) of \(\mathcal{P}\) is:

[PLoopOne, -PLoopOne, PLoopOmega, -PLoopOmega] .

Let g1, g2 be instances of class GCode. For positive elements of the Parker loop the multiplication formula given above can be coded as follows:

PLoop(g1) * PLoop(g2) == (-1)**g1.theta(g2) * PLoop(g1 + g2) .

The elements of the Parker loop are numbered from 0 to 0x1fff. Here the numbers of the positive Parker loop elements correspond to the numbers of the Golay code words. The numbering system for the Parker loop is also used for indexing certain elements of the monster group \(\mathbb{M}\).

A transversal of \(Z(\mathcal{P})\) in \(\mathcal{P}\) is used for indexing certain basis vectors of the representation \(\rho\) of \(\mathbb{M}\). Property ord of an instance a of class PLoop returns the number of that element of the Parker loop. For indexing vectors in \(\rho\) it is important to know that (-a).ord = a.ord ^ 0x1000 and (~a).ord = a.ord ^ 0x800. Thus the Parker loop elements a with 0 <= a.ord < 0x800 are a transversal of \(Z(\mathcal{P})\) in \(\mathcal{P}\).

class mmgroup.PLoop(value=0)

This class models an element of the Parker Loop.

The Parker loop is a non-associative loop with \(2^{1+12}\) elements. Each element can be interpreted as a signed Golay code word, see class GCode. Accordingly, class PLoop is a subclass of class GCode.

The loop operation is written multiplicatively. The neutral element of the loop (corresponding to the positive zero word of the Golay code) is PLoopOne, and its negative is -PLoopOne. PLoopOmega is the (positive) element corresponding to the all-one vector of the Golay code.

The \(2^{1+12}\) Parker loop elements are numbered from 0 to 0x1fff. Elements 0 to 0xfff are are positive and corresponding to the Golay code words with the same number. The element with number 0x1000 ^ i is the negative of the element with number i.

Parameters:

value (see table below for legal types) – This is the value of the Parker loop element to be returned.

Returns:

A Parker loop element

Return type:

an instance of class PLoop

Raise:

TypeError if type(value) is not in the table given above.
ValueError if value cannot be converted to an instance of class PLoop.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class `PLoop`
type	Evaluates to
`int`	Here the code word with number `value` is returned. `0 <= value < 0x2000` must hold. We have `PLoop(0) == PLoopOne`, `PLoop(0x1000) == -PLoopOne`, and `PLoop(0x800) == ~PLoopOne == PLoopOmega`.
`list` of `int`	Such a list is converted to a Golay code word, see class `GCode`, and the corresponding (positive) Parker loop element is returned.
class `GCode`	The corresponding (positive) Parker loop element is returned.
class `PLoop`	A deep copy of parameter `value` is returned.
class `GcVector`	This is converted to a Golay code word, see class `GCode`, and the corresponding (positive) Parker loop element is returned.
class `XLeech2`	The Parker loop part of the `XLeech2` object is returned.
`str`	Create random element depending on the string `'r'`: Create arbitrary Parker loop element

Standard operations

Let a be a Parker loop element. The multiplication operator * implements the non-associative loop operation. Division by a Parker loop element means multiplication by its inverse, and exponentiation means repeated multiplication, with a**(-1) the loop inverse of a, as usual.

The ~ operator maps the Parker loop element a to a * PLoopOmega, leaving the sign of a unchanged.

Multiplication with the integer 1 or -1 means the multiplication with the neutral element PLoopOne or with its negative -PLoopOne, respectively.

If any of the operations +, - or & is applied to a Parker loop element, that element is converted to a Golay code word of type GCode, ignoring the sign. This conversion also takes place if a Parker loop element is multiplied or divided by an integer different from 1 or -1.

Standard functions

len(a) is a shorthand for len(GCode(a)). Here function GCode(a) converts a to a Golay code word of type GCode.

abs(a) returns the element in the set {a, -a} which is positive.

property ord

Return the number of the Parker loop element.

We have 0 <= i < 0x2000 for the returned number i.

parity_class: alias of GCode

property sign

Return the sign of the Parker loop element.

This is 1 for a positive and -1 for a negative element.

split()

Split sign and Omega from Parker loop element a.

Returns:: a triple (es, eo, v) with a = (-1)**e1 * PLoopOmega**eo * v .

Here v is the unique (positive) element of the Parker loop of type PLoop with 0 <= v.ord < 0x800 satisfying that equation. es and eo are 0 or 1.

split_octad()

Split Parker loop element a into central element and octad

Returns:: a triple (es, eo, o) with a = (-1)**e1 * PLoopOmega**eo * o.

Here o is either the neutral Parker loop element PLoopOne or Parker loop element corresponding to a positive octad. es and eo are 0 or 1. An octad is a Golay code word (of type GCode) of weight 8.

Raise:

Raise ValueError if this is not possible.

mmgroup.PLoopZ(e1=0, eo=0)

Return a specific central element of the Parker loop.

Parameters:

e1 (int) – Sign, the sign of the element will be (-1)**e1
eo (int) – Exponent for PLoopOmega, default is 0

Returns:

The central element (-1)**e1 * PLoopOmega**eo of the Parker loop.

Return type:

an instance of class PLoop.

Here PLoopOmega is the positive element of the Parker loop corresponding to the Golay code word 1,...,1.

e1 and eo may also be parity objects of type Parity.

Octads and suboctads

We deal with octads and certain subsets of octads called suboctads.

An octad is a Golay code word of weight 8. The Golay code has 759 octads. A signed octad is a Parker loop element corresponding to an octad or a complement of an octad. Signed octads are used for indexing some unit vectors of the representation \(\rho\) of the monster \(\mathbb{M}\).

Function Octad() returns a signed octad as an instance of class PLoop. Arguments of function Octad() are interpreted in the same way as arguments of the constructor for class PLoop, but the function raises ValueError if the result is not a (possibly complemented) signed octad.

We use some lexical order for numbering the 759 octads, which we do not describe in detail. Due to the well-known properties of the Golay code we can create a random octad and display its number as follows:

from random import sample
from mmgroup import Octad
# Select 5 random integers between 0 and 23
int_list = sample(range(24), 5)
# Complete these 5 integers to a (unique) octad o
o = Octad(int_list)
# Display octad o and its number
print("Octad", o.bit_list, "has number", o.octad)

A suboctad of an octad o is an element of the Golay cocode \(\mathcal{C}^*\) of even parity which can be represented as a subset of o. Each octad has 64 suboctads. A pair (octad, suboctad) is used for indexing some basis vectors in the representation \(\rho\). function SubOctad creates a suboctad as an instance of class XLeech2 from such a pair. Function SubOctad takes two arguments octad and suboctad. The first argument evaluates to a signed octad as in function Octad(). The second argument evaluates to a suboctad, see function SubOctad for details.

The raison d’etre of a suboctad is indexing a basis vector in the representation \(\rho\). For this purpose we need a pair of integers refering to the octad and the suboctad. For an instance so of class XLeech2 that pair is given as the pair of the last two integers in so.vector_tuple().

For an octad o and a suboctad s precisely one of the pairs (o,s) and (~o,s) is actually used as an index for \(\rho\). The pair (~o,s) is used if the cocode element corresponding to s has minimum weight 2; the pair (o,s) is used if that element has minimum weight 0 or 4. See [Con85] or [Sey20] for background. In this implementation both, (o,s) and (~o,s), refer to the same basis vector of \(\rho\).

mmgroup.Octad(octad)

Return a (signed) octad as an element of the Parker loop.

Parameters:

octad (see table below for legal types) – the value of the octad to be returned.

Returns:

a (signed) octad

Return type:

an instance of class PLoop

Raise:

TypeError if type(octad) is not in the table given above.
ValueError if octad cannot be converted to a (possibly negated and complemented) octad.

Depending on its type parameter octad is interpreted as follows:

Legal types for parameter `octad`
type	Evaluates to
`int`	Here the (positive) octad with number `octad` is returned. There are 759 octads in the Golay code. So `0 <= octad < 759` must hold.
`list` of `int`	Such a list is converted to a Golay code word, see class `GCode`, and the corresponding (positive) Parker loop element is returned.
class `GCode`	The corresponding (positive) Parker loop element is returned.
class `PLoop`	A deep copy of parameter `octad` is returned.
class `GcVector`	This is converted to a Golay code word, see class `GCode`, and the corresponding (positive) Parker loop element is returned.
class `XLeech2`	The octad part of the vector `octad` is returned.
`str`	Create random element depending on the string `'r'`: Create arbitrary octad

A complement of an octad is also accepted; then the corresponding Parker loop element is retured. The function raises ValueError if parameter octad does not evaluate to an octad or a complement of an octad.

mmgroup.octad_entries(octad)

Return list of entries of an octad

Here parameter octad describes an octad as in function Octad. That octad is a sum of eight basis vectors of \(\mbox{GF}_2^{24}\), with basis vectors numbered from 0 to 23. The function returns the list [b0,...,b7] of the indices of these eight basis vectors in a certain order that may differ from the natural order.

We use these indices for numbering the suboctads of that octad as described in the documentation of function SubOctad.

Caution

The order of the basis vectors returned by this function may be changed in future versions!

mmgroup.SubOctad(octad, suboctad=0)

Creates a suboctad as instance of class XLeech2

Parameters:

octad (same as in function Octad) – The first component of the pair (octad, suboctad) to be created.
suboctad (see table below for legal types) – The second component of the pair (octad, suboctad) to be created.

Returns:

The suboctad given by the pair (octad, suboctad)

Return type:

an instance of class XLeech2

Raise:

TypeError if one of the arguments octad or suboctad is not of correct type.
ValueError if argument octad or suboctad does not evaluate to an octad or to a correct suboctad, respectively.

A suboctad is an even cocode element that can be represented as a subset of the octad given by the argument octad.

The raison d’etre of function SubOctad is that pairs (octad, suboctad) are used for indexing vectors in the representation of the monster group. Here we want to number the octads from 0 to 758 and the suboctads form 0 to 63, depending on the octad. Note that every octad has 64 suboctads.

Depending on its type parameter suboctad is interpreted as follows:

Legal types for parameter `suboctad`
type	Evaluates to
`int`	Here the suboctad with the number given in the argument is taken. That numbering depends on the octad given in the argument `octad`. `0 <= suboctad < 64` must hold.
`list` of `int`	Such a list is converted to a bit vector as in class `GcVector`, and the cocode element corresponding to that bit vector is taken.
class `GCode`	The intersection of the octad given as the first argument and the Golay code word given as the second argument is taken.
class `GcVector`	This is converted to a cocode element, see class `Cocode`, and that cocode element is taken.
class `Cocode`	That cocode element is taken as the suboctad.
`str`	Create random element depending on the string `'r'`: Create arbitrary suboctad

The numbering of the suboctads

Suboctads are numbered for 0 to 63. Let [b0, b1,..., b7] be the bits set in the octad of the pair (octad, suboctad). Here we assume the indices of the basis vectors making up the octad are ordered as returned by function octad_entries, when applied to the octad.

The following table shows the suboctad numbers for some suboctads given as cocode elements. More suboctad numbers can be obtained by combining suboctads and their corresponding numbers with XOR.

Suboctad numbers of some cocode elements
`[b0,b1]`	`[b0,b2]`	`[b0,b3]`	`[b0,b4]`	`[b0,b5]`	`[b0,b6]`
`s = 1`	`s = 2`	`s = 4`	`s = 8`	`s = 16`	`s = 32`

E.g. [b0, b5, b6, b7] is equivalent to [b1, b2, b3, b4] modulo the Golay code and has number s = 1 ^ 2 ^ 4 ^ 8 = 15.

Automorphisms of the Parker loop

We deal with a certain group of automorphisms of the Parker loop.

A standard automorphism is an automorphism of the Parker loop \(\mathcal{P}\) which maps to an automorphism of the Golay code \(\mathcal{C}\) when factoring out the elements \(\{1,-1\}\) of \(\mathcal{P}\). Let \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) be the group of standard automorphisms of \(\mathcal{P}\). We embed \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) into \({\mathbb{M}}\) as in [Con85]. In ATLAS notation, see [CCN+85], that group has structure

\[{{\rm Aut}_{{\rm St}} \mathcal{P}} = 2^{12} . M_{24}\, .\]

This means that \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) has an elementary Abelian normal subgroup of order \(2^{12}\) with factor group \(M_{24}\). That group extension does not split. Here the group \(2^{12}\) is isomorphic to the Golay cocode \(\mathcal{C}^*\) and \(M_{24}\) is the Mathieu group acting on \(\mathbb{F}_2^{24}\) by permuting the basis vectors. \(M_{24}\) is the automorphism group of the Golay code \(\mathcal{C}\) .

The automorphisms in the subgroup \(\mathcal{C}^*\) of \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) are called diagonal automorphisms. A diagonal automorphism \(d \in \mathcal{C}^*\) maps an element \(a\) of \(\mathcal{P}\) to \((-1)^s \cdot a\) with \(s = |a \, \& \, d|\). Here \(\&\) means the bitwise and operation of bit vectors and \(|.|\) means the bit weight of a bit vector.

Since the extension \(2^{12} . M_{24}\) does not split, there is no canonical embedding of \(M_{24}\) into \({{\rm Aut}_{{\rm St}} \mathcal{P}}\). For practical purposes we need such an embedding. We choose a basis \(b_1,\ldots,b_{11}\) of the Golay code \(\mathcal{C}\), see section The basis of the Golay code and of its cocode. Let \(a_i\) be the positive element of the Parker loop \(\mathcal{P}\) corresponding to \(b_i\). For any \(\tilde{g} \in M_{24}\) we let \(g\) be the unique element of \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) with \(g \mathcal{C}^* = \tilde{g}\) that maps all elements \(a_1,\ldots,a_{11}\) of \(\mathcal{P}\) to positive elements of \(\mathcal{P}\). We call \(g\) the standard representative of \(\tilde{g}\) in \({{\rm Aut}_{{\rm St}} \mathcal{P}}\).

Elements of \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) are modelled as instances of class AutPL. If d is an instance of class Cocode representing an element of \(\mathcal{C}^*\) then AutPL(d) is the corresponding diagonal automorphism.

A permutation \(p \in M_{24}\) can be represented as a list l_p = [p(0),...,p(23)]. If l_p is such a list then AutPL(l_p) is the standard representative of p in \({{\rm Aut}_{{\rm St}} \mathcal{P}}\). Here an error occurs if the mapping from i to p(i) is not in \(M_{24}\). A permutation in \(M_{24}\) can also be given as a mapping from a subset of \(\{0,\ldots,23\}\) to \(\{0,\ldots,23\}\), provided that this mapping extends to a unique element of \(M_{24}\). For details, see class AutPL.

The group \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) operates naturally on \(\mathcal{P}\) by right multiplication. It also operates on \(\mathbb{F}_2^{24}\), \(\mathcal{C}\), and \(\mathcal{C}^*\) by right multiplication. Here the basis vectors of \(\mathbb{F}_2^{24}\) are permuted by \(M_{24}\); so the kernel of that operation is the subgroup \(\mathcal{C}^*\) of \({{\rm Aut}_{{\rm St}} \mathcal{P}}\).

We order the elements \(p\) of \(M_{24}\) in lexicographic order based on the lists l_p = [p(0),...,p(23)]. We number the 244823040 elements of \(M_{24}\) in that order from 0 to 244823039. Thus the number 0 is assigned to the neutral element of \(M_{24}\), and the number 244823039 is assigned to the permutation p with l_p =

\(\small [ 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 0, 1, 2, 3, 4, 5, 6, 7 ]\)

These numbers are used for addressing the corresponding standard representatives in the subgroup \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) of the monster \(\mathbb{M}\).

One way to create an element of \(M_{24}\) is to map an umbral heptad to another umbral heptad. Here an umbral heptad is a set of 7 elements of \(\{0,\ldots,23\}\) such that precisely 6 of these elements are contained in an octad, see [CS99], Chapter 10. Then the 6 elements in one octad must map to the 6 elements in the other octad.

The set [0,1,2,3,4,5,8] is an umbral heptad with 8 not contained in the octad. We may create the standard representative (in \({{\rm Aut}_{{\rm St}} \mathcal{P}}\)) of a random element of \(M_{24}\) as follows:

from random import sample
from mmgroup import Octad, AutPL
# Create a random octad
o = Octad("r")
# Select 6 random elements from that octad
hexad = sample(o.bit_list, 6)
# Select one random element not in that octad
extra = sample((~o).bit_list, 1)
# Create umbral heptad from these random elements
heptad = hexad + extra
# Create a mapping from [0,1,2,3,4,5,8] to that heptad 
hmap = zip([0,1,2,3,4,5,8], heptad)
# Create a permutation in the Mathieu group from that mapping
aut = AutPL(0, hmap) 
# 'aut' is the standard representative of the permutation
# Show 'aut' as a permutation in form of a list 
print(aut.perm)     
# Show the automorphism 'aut' with its permutation number 
print(aut)     

Remark

Class AutPL is a subclass of class mmgroup.structures.AbstractGroupWord which implements elements of an abstract group and the operations on such elements. For an instance g of AutPL, the object g.group is an instance of a subclass of mmgroup.structures.AbstractGroup. That subclass models the group \({{\rm Aut}_{{\rm St}} \mathcal{P}}\).

Generating random elements of certain subgroups of \(M_{24}\)

We support the generation of random elements of certain subgroups of \(M_{24}\). Here any such subgroup stabilizes a subset (or a sets of subsets) of the set \(\bar{\Omega} = \{0,\ldots,23\}\) on which \(M_{24}\) acts. Furthermore, any such group is named by a flag (which is a character), as indicated in the table below. Intersections of these subgroups are described by combining the characters. The character r describes the whole group \(M_{24}\). A string of characters describing such a subgroup should start with r. Whitespace is ignored.

Table of subgroups:

\[\begin{split}\begin{array}{|c|c|c|c|} \hline \mbox{Flag} & \mbox{Mnemonic} & \mbox{Subgroup stabilizing the set} & \mbox{Structure} \\ \hline \mbox{'r'} & \mbox{(random)} & \mbox{the whole set } \bar{\Omega} & M_{24} \\ \mbox{'2'} & \mbox{2-set} & \{2,3\} & M_{22}:2 \\ \mbox{'o'} & \mbox{octad} & \{0,\ldots,7\} & 2^4:A_8 \\ \mbox{'t'} & \mbox{trio} & {\{ \{8i,\ldots,8i+7\} \mid i < 3 \}} & 2^6:(S_3 \times L_3(2)) \\ \mbox{'s'} & \mbox{sextet} & {\{ \{4i,\ldots,4i+3\} \mid i < 6 \}} & 2^6:3.S_6 \\ \mbox{'l'} & \mbox{(line)} & \{ \{2i, 2i+1\} \mid 4 \leq i < 12 \} & 2^{1+6}:L_3(2) \\ \mbox{'3'} & \mbox{3-set} & \{1, 2,3\} & L_3(4):S_3 \\ \hline \end{array}\end{split}\]

For mathematical background we refer to section Subgroups of the Mathieu group M_{24}.

Examples of strings describing subgoups of \(M_{24}\)
String	Action
`'r'`	Generate a random element of \(M_{24}\)
`'r 2o'`	Generate a random element of \(M_{24}\) stabilizing \(\{0,\ldots,7\}\) and \(\{2,3\}\)

class mmgroup.AutPL(d=0, p=0, unique=1)

This class models a standard automorphism of the Parker loop.

Parameters:

d – This parameter describes an element of the Golay cocode. If d is an instance of class AutPL then this describes an automporphism of the Parker loop; in that case parameter p must be set to its default value. Legal types of parameter d see below. The parameter defaults to zero word of the cocode.
p – This parameter describes a permutation in the Mathieu group M_24 or, more precisely, the standard representative of that permutation in the automporphism group of the Parker loop. Legal types of that parameter see below. The parameter defaults to neutral element of Mat24.
unique – If this is True (default) and parameter p is not r then parameter p must describe a unique permutation in the Mathieu group M_24. Otherwise we take the least possible permutation (in lexicographic order) that agrees with parameter p.

Returns:

A standard Parker loop automorphism

Return type:

an instance of class AutPL

Raise:

TypeError if type(value) is not in the table given below.
ValueError if the set of arguments cannot be converted to an instance of class AutPL.

Legal types for parameter `d` in constructor of class `AutPL`
type	Evaluates to
`int`	The number of an element of the Golay cocode.
class `Cocode`	This represents an element of the Golay cocode.
`str`	Create random element depending on `str` `'r'`: Create an arbitrary cocode element `'e'`: Create an even cocode element `'o'`: Create an odd cocode element Any other string is illegal.
class `AutPL`	A deep copy of the given automorphism in `AutPL` is returned. Then parmeter `p` must be set to its default value.

Legal types for parameter `p` in constructor of class `AutPL`
type	Evaluates to
`int`	Here the integer is the number of a permutation in the Mathieu group `M_24`.
`list` of `int`	A list `l_p` of `24` of disjoint integers `0 <= i < 24` is interpreted as a permutation in `M_24` that maps `i` to `l_p[i]`.
`dict`	A dictionary specifies a mapping from a subset of the integers `0 <= i < 24` to integers `0 <= dict[i] < 24`. This mapping must extend to a permutation in `M_24`. If parameter `unique` is `True` (default) then that permutation must be unique in `M_24`.
`zip` object	`zip(x,y)` is equivalent to `dict(zip(x,y))`.
`str`	Create random element depending on the string
	`'r'`	Create random element of `M_24`
	`'r <flags>'`	Create random element of subgroup of `M_24`, depending on `<flags>`, see explanation above.

Let a be an instance of class GcVector, GCode, Cocode, or PLoop, and let g1 , g2 be instances of class AutPL. Then a * g1 is the result of the natural operation of g1 on a, which belongs to the same class as a.

g1 * g2 means group multiplication, and g1 ** n means exponentiation of g1 with the integer n. g1 ** (-1) is the inverse of g. g1 / g2 means g1 * g2 ** (-1).

g1 ** g2 means g2**(-1) * g1 * g2.

as_tuples()

Convert group element to a list of tuples

For a group element g the following should hold:

g.group.word(*g.as_tuples()) == g .

So passing the tuples in the list returned by this method as arguments to g.group or to g.group.word reconstructs the element g.

This shows how to convert a group element to a list of tuples and vice versa.

check()

Check automorphism for consistency via ‘assert’ statements

a.check() returns a.

property cocode

Return number of cocode element in the automorphism.

For an instance g of AutPL we have

g == AutPL(Cocode(g.cocode)) * AutPL(g.perm).

property parity

Return parity of an automorphism

This is s if PLoopOmega maps to (-1)**s * PLoopOmega for s == 0 or s == 1.

property perm

Return permutation of automorphism as a list p_l.

Then the permutation maps i to p_l[i] for i = 0,...,23.

property perm_num

Return the number of the permutation of the automorphism

The Mathieu group M_24 has 244823040 elements numbered from 0 to 244823039 in lexicographic order. Thus the neutral element has number 0.

The Leech lattice modulo 2 and its preimage \(Q_{x0}\)

We deal with an extraspecial group that maps to the Leech lattice modulo 2

Let \(Q_{x0}\) be the group generated by elements \(x_d, x_\delta\) with \(d \in \mathcal{P}, \delta \in \mathcal{C}^*\). Here \(\mathcal{P}\) is the Parker loop and \(\mathcal{C}^*\) is the Golay cocode as in [Con85]. We take the following relations in \(Q_x\) from [Sey20]:

\[x_d x_e = x_{d \cdot e} x_{A(d,e)}, \, x_\delta x_\epsilon = x_{\delta \epsilon}, \, [x_d x_\delta] = x_{-1}^{\langle d, \delta \rangle}; \; d, e \in \mathcal{P}; \; \delta , \epsilon \in \mathcal{C}^* \, .\]

Here \(A(d,e)\) is the associator between \(d\) and \(e\), i.e. the element of \(\mathcal{C}^*\) corresponding to the vector \(d \cap e\); and \([.,.]\) is the commutator in \(Q_{x0}\). Then \(Q_{x0}\) is an extraspecal group of structure \(2_+^{1+24}\).

An element of the group \(Q_x\) is modelled as an instance of class XLeech2.

In that class we encode the element \(x_d \cdot x_\delta\) of \(Q_{x0}\) as an integer \(x\) as follows:

\[x = 2^{12} \cdot d \oplus (\delta \oplus \theta(d)) \, .\]

Here elements of the Parker loop and elements of the cocode are encoded as integers as in section The Parker loop and The Golay code and its cocode. \(\theta\) is the cocycle given in section The basis of the Golay code and of its cocode, and ‘\(\oplus\)’ means bitwise addition modulo 2. Note that a Parker loop element is 13 bits long (with the most significant bit denoting the sign) and that a cocode element is 12 bits long.

There is a natural homomorphism from \(Q_{x0}\) to the Leech lattice \(\Lambda\) modulo 2 with kernel \(\{x_1, x_{-1}\}\), as described in [Con85]. This homomorphism maps the group operation in \(Q_{x0}\) to vector addition in \(\Lambda / 2\Lambda\). With our numbering in \(Q_{x0}\) that homomorphism can be realized by simply dropping the sign bit 25; then vector addition in \(\Lambda / 2\Lambda\) corresponds to the \(\oplus\) operation on such numbers. The natural quadratic form on the vector in \(\Lambda / 2\Lambda\) with the number \(2^{12} \cdot d + \delta\), \(0 \leq d, \delta < 2^{12}\) is the parity of the bit vector \(d \oplus \delta\).

class mmgroup.XLeech2(ploop=0, cocode=0, *args)

This class models an element of the group \(Q_{x0}\).

The group \(Q_{x0}\) is an extraspecial 2 group of structure \(2^{1+24}\).

The group operation is written multiplicatively.

The \(2^{1+24}\) group elements are numbered from 0 to 0x1ffffff. Elements 0 to 0xffffff are considered positive. The element with number 0x1000000 ^ i is the negative of the element with number i.

An element is constructed as a product \(x_d x_\delta\), where \(d\) is in the Parker loop and \(\delta\) is in the Golay cocode.

Parameters:

value – This parameter describes the value of an element of the group \(Q_{x0}\) as indicated in the table below.
cocode – This parameter describes an element \(x_\delta\) (with \(\delta\) in the Golay cocode) to be right multiplied to the element of \(Q_{x0}\) obtained from the first parameter.

Returns:

An element of the group \(Q_{x0}\).

Return type:

an instance of class XLeech2

Raise:

ValueError if the input cannot converted to an element of the group \(Q_{x0}\).
TypeError the ype of an input is illegal.

Caution

Although the group \(Q_{x0}\) has a natural embedding into the subgroup \(G_{x0}\) of the monster group, we do not consider an instance \(q\) of class XLeech2 as an element of \(G_{x0}\). We consider \(q\) as a (possibly negated) basis vector of a space on which the subgroup \(G_{x0}\) of the monster acts monomially by right multiplication.

Depending on its type parameter value is interpreted as follows:

Legal types for constructor of class `XLeech2`
type of `value`	Evaluates to
`int`	Here the code word with number `value` is returned. `0 <= value < 0x2000000` must hold.
class `XLeech2`	A deep copy of the object `value` is created.
class `GCode`	The corresponding Golay code element is converted to a (positive) element of \(Q_{x0}\).
class `PLoop`	The corresponding Parker loop element is converted to an element of \(Q_{x0}\).
class `MM`	Then `value` in an element of the monster group. If that element is in the subgroup \(Q_{x0}\) of the monster, then it is converted to the coresponding instance of class `XLeech2`.
`'r'`	Create random element depending on the string, see explanation below.
A letter `BCTXE`	If `value` is a single capital letter in `BCTXE` then we create an element corresponding to a unit vector in \(\rho_p\) as described below.
Any other string `s`	This is intepreted as the element `MM('q', s)` of the Monster group.

If value is of one of the type listed above then the following parameter is converted to an element of the Golay cocode (as in the constructor of class Cocode multiplied to the converted parameter value from the right.

Alternatively, parameter value may be a single letter. If value is one of the capital letters BCTXE then that letter and the following arguments are passed to the constructor of class MMVector in order to generate a (possible negated) basis vector of the representation \(\rho_p\) of the monster. (Here the characteristic \(p\) is ignored.) If that basis vector corresponds to an element of \(Q_{x0}\) then we construct that element of \(Q_{x0}\); otherwise an error occurs.

If parameter value is the letter 'r' then we generate a random element of \(Q_{x0}\). If an integer i is given as a second parameter 'r' then we generate a random element of \(Q_{x0}\) of type i. Here the type of a vector \(v \in \Lambda / 2 \Lambda\) is the halved norm of the shortest vector in the set \(v + 2 \Lambda\). If i is specified then it must be equal to 0, 2, 3 or 4.

Standard operations

Let q be an instance of this class. The multiplication operator * implements the group operation. Division by an element means multiplication by its inverse, and exponentiation means repeated multiplication, with q**(-1) the inverse of q, as usual.

Multiplication with the integer 1 or -1 means the multiplication with the neutral element or with the central involution \(x_{-1}\).

The opration & denotes the scalar product of the vectors in the Leech lattice modulo 2 obtained from an instance of this class, ignoring the sign.

Standard functions

abs(a) returns the element in the set {a, -a} which is positive.

If an instance \(q\) of class XLeech2 maps to a vector of type 2 in the Leech lattice modulo 2 then \(q\) is also a unit vector in the 196884-dimensional representation \(\rho\) of the monster group.

One may use \(q\) in the constructor of class MM (representing the monster group) for creating the corresponding element of the subgroup \(Q_{x0}\) of the monster group.

as_Leech2_bitvector()

Convert element to a bit vector in a numpy array

The element is returned as a numpy array v of length 24 of 8-bit unsigned integers, with each entry equal to 0 or 1. This array represents a vector in the Leech lattice mod 2 in the standard encoding.

For an instance x of this class we have v[i] = (x.ord >> i) & 1, for 0 <= i < 24.

as_suboctad(strict=False)

Convert element to a suboctad if possible.

Let \(x_d \cdot x_\delta\) be equal to the given element of \(Q_{x0}\). If \(d\) corresponds to a (possibly complemented) octad and \(\delta\) is an even cocode element and can be represented as a subset of \(d\) then the given element is a suboctad. In this case the function returns a pair (octad, suboctad) of integers describing a suboctad a in function SubOctad in Section Octads and suboctads.

If strict is True then the given element must also correspond to a short vector in the Leech lattice mod 2. The function raise ValueError if the given element does not satisfy the conditions mentioned above.

classmethod gen_type(vtype=2, positive=True)

Return generator that yields the vectors of a given type

The function returns a generator that yields all elements of \(Q_{x0}\) that map to a vector of the type vtype in the Leech lattice (mod 2) as instances of class XLeech2.

Parameter vtype must be 0, 2, 3 or 4, where vtype = 2 (default) means the short Leech lattice vectors.

If parameter positive``is ``True (default) then the elements with positive sign are generated only.

isplit()

Split element into a product \(x_d \cdot x_\delta\)

The method returns a pair \((d, \delta)\) such that \(x_d \cdot x_\delta\) is equal to the given element of \(Q_{x0}\).

Here \((d, \delta)\) is returned as a pair of integers.

property mmdata

Return internal representation of corresponding monster element.

That internal representation is returned as a numpy array of 32-bit integers.

octad_number()

Return number of octad.

Let \(x_d \cdot x_\delta\) be equal to the given element of \(Q_{x0}\). If \(d\) corresponds to a (possibly complemented) octad in the Golay code then the function returns the number of that octad as a nonnegative integer less than 759. Otherwise the function raises ValueError.

Here the octads are numbered as in class GCode.

property ord

Return the number of the element of \(Q_{x0}\) .

We have 0 <= i < 0x2000000 for the returned number i.

property sign

Return the sign of the element \(Q_{x0}\).

This is 1 for a positive and -1 for a negative element.

split()

Split element into a product \(x_d \cdot x_\delta\)

The method returns a pair \((d, \delta)\) such that \(x_d \cdot x_\delta\) is equal to the given element of \(Q_{x0}\).

The element \(d\) of the Parker loop is an instance of class PLoop. The element \(\delta\) of the Golay cocode is an instance of class Cocode.

str(): Represent group element as a string

property subtype

Return pair (type, subtype) of the element of \(Q_{x0}\)

Here type is as in property type, and subtype is a one-digit decimal integer describing the subtype of a vector in the Leech lattice modulo 2, as explained in the guide in section Computations in the Leech lattice modulo 2.

property type

Return the type of the element of \(Q_{x0}\).

This is equal to the type of the corresponding vector \(v\) in the Leech lattice \(\Lambda\) modulo 2. The type of a vector \(v \in \Lambda / 2 \Lambda\) is the halved norm of the shortest vector in the set \(v + 2 \Lambda\). That type is equal to 0, 2, 3 or 4.

vector_tuple()

Return unit vector in representation of the monster as tuple

If the element of \(Q_{x0}\) corresponds to a vector of type 2 in the Leech lattice then it also corresponds to a unit vector v in the representation \(\rho\) of \(\mathbb{M}\); otherwise the function raises ValueError.

The function returns a tuple (sign, tag, i0, i1), with sign = +1 or -1. Then the triple (tag, i0, i1) corresponds to a basis vector u in \(\rho\) as described in class MMVector, and we have v = sign * u.

property xsubtype

Return subtype of the element of \(Q_{x0}\)

The function returns the integer 16 * type + subtype, where the pair (type, subtype) is as in property subtype. See section Computations in the Leech lattice modulo 2 in the guide for background.

mmgroup.leech2_orbits_raw(g_list)

Compute orbits of the Conway group on the Leech lattice mod 2

The Conway group \(\mbox{Co}_1\) has a natural action on \(\Lambda / 2 \Lambda\), i.e. on the Leech lattice mod 2. The subgroup \(G_{x0}\) of the Monster (of structure \(2^{1+24}.\mbox{Co}_1\)) has the same action on \(\Lambda / 2 \Lambda\).

Given a list g_list of generators of a subgroup \(H\) of \(G_{x0}\), the function computes the orbits of \(\Lambda / 2 \Lambda\) under the action of \(H\). Here the entrries of the list g_list may be instances of class MM, which are elements of the group \(G_{x0}\).

The function encodes an element of \(\Lambda / 2 \Lambda\) as an integer, as in class XLeech2, setting the sign bit to zero.

The function returns a triple (n_sets, indices, data) that defines the partition of \(\Lambda / 2 \Lambda\). Here the integer n_sets is the number of sets in the partition. indices is an array of indices referring the the array data. Array data stores the \(2^{24}\) elements of \(\Lambda / 2 \Lambda\), so that for 0 <= i < n_sets the i-th set of the partition is equal to the array data[indices[i] : indices[i+1]].

The entries of the array data[indices[i] : indices[i+1]] are sorted. The sets of the partition are sorted by their smallest elements.

The basis of the Golay code and of its cocode

We chose a basis b_0,…, b_11 of the Golay code \(\mathcal{C}\) such that the resulting Golay code is compatible to [CS99], Chapter 11.

As usual in the Python or C language we number the indices of the basis vectors of the space \(\mathbb{F}_2^{24}\) from 0 to 23. Similarly, we number the basis vectors of the Golay code from 0 to 11.

In [CS99] the Golay code is described in terms of the MOG (Miracle Octad Generator), which can be considered as a \(4 \times 6\) matrix for arranging the basis vectors of \(\mathbb{F}_2^{24}\). Our numbering of these basis vectors corresponds to the MOG as follows:

0

4

8

12

16

20

1

5

9

13

17

21

2

6

10

14

18

22

3

7

11

15

19

23

For the cocode \(\mathcal{C}^*\) we use the reciprocal basis c_0,…, c_11 of the basis b_0,…, b_11 of \(\mathcal{C}\). Then the scalar product b_i & c_j of b_i and c_j is equal to 1 if i == j and to 0 otherwise.

The basis vectors b_0,…, b_11 of the Golay code are given in the following table. The table also shows the cocyles of the basis vectors as explained below:

       Basis vectors of the Golay code             Cocycle theta
       binary: bit 0,...,23            hex         bit 0,...,11
 b_0:  0000 1111 0000 1111 1111 1111,  0xfff0f0;   0111 0000 0000
 b_1:  0000 1111 1111 0000 1111 1111,  0xff0ff0;   1011 0000 0000
 b_2:  0000 1111 1111 1111 0000 1111,  0xf0fff0;   1101 0000 0000
 b_3:  0000 1111 1111 1111 1111 0000,  0x0ffff0;   1110 0000 0000
 b_4:  0000 0000 0011 0011 0011 0011,  0xcccc00;   1111 0000 0000
 b_5:  0000 0000 0101 0101 0101 0101,  0xaaaa00;   1111 0000 0000
 b_6:  0000 0011 0000 0011 0101 0110,  0x6ac0c0;   0111 0000 0000
 b_7:  0000 0101 0000 0101 0110 0011,  0xc6a0a0;   0111 0000 0000
 b_8:  0011 0000 0000 0011 0110 0101,  0xa6c00c;   1000 0000 0010
 b_9:  0101 0000 0000 0101 0011 0110,  0x6ca00a;   1000 0000 0010
b_10:  0111 1000 1000 1000 1000 1000,  0x11111e;   0000 0000 0000
b_11:  1111 1111 1111 1111 1111 1111,  0xffffff;   0000 0000 0000

Representatives of the basis vectors c_0,…, c_11 of the Golay cocode are given in the following table:

       Basis vectors of the cocode
       binary: bit 0,...,23            hex
 c_0:  0000 1000 1000 0000 0000 0000,  0x000110
 c_1:  0000 1000 0000 1000 0000 0000,  0x001010
 c_2:  0000 1000 0000 0000 1000 0000,  0x010010
 c_3:  0000 1000 0000 0000 0000 1000,  0x100010
 c_4:  0000 0000 0101 0000 0000 0000,  0x000a00
 c_5:  0000 0000 0011 0000 0000 0000,  0x000c00
 c_6:  0000 0101 0000 0000 0000 0000,  0x0000a0
 c_7:  0000 0011 0000 0000 0000 0000,  0x0000c0
 c_8:  0101 0000 0000 0000 0000 0000,  0x00000a
 c_9:  0011 0000 0000 0000 0000 0000,  0x00000c
c_10:  1000 1000 1000 1000 1000 1000,  0x111111
c_11:  1000 0000 0000 0000 0000 0000,  0x000001

The cocycle \(\theta: \mathcal{C} \times \mathcal{C} \rightarrow \mathbb{F}_2\) is used for the multiplication of two elements of the Parker loop, see section The Parker loop. For basis vectors \(b_i\), \(b_j\) of \(\mathcal{C}\) the column theta in the table above contains the value \(\theta(b_i, b_j)\) in bit \(j\) of row \(i\). From these values other values of the cocycle \(\theta\) can be computed by using

\[\begin{split}\theta(g_1 + g_2, g_3) = \theta(g_1, g_3) + \theta(g_2, g_3) + |g_1 \& g_2 \& g_3|, \\ \theta(g_1, g_2 + g_3) = \theta(g_1, g_2) + \theta(g_1, g_3), \quad g_1, g_2, g_3 \in \mathcal{C} \; .\end{split}\]

Here \(\&\) means the bitwise and operation of bit vectors and \(|.|\) means the bit weight of a bit vector.

The cocycle \(\theta\) has been chosen in accordance with the requirements in [Sey20]. In that context the grey subspace of \(\mathcal{C}\) is spanned by \(b_0,\ldots,b_3,b_{10}, b_{11}\) and the coloured subspace of \(\mathcal{C}\) is spanned by \(b_4,\ldots,b_9\). Similarly, the grey subspace of \(\mathcal{C}^*\) is spanned by \(c_0,\ldots,c_3,c_{10}, c_{11}\) and the coloured subspace of \(\mathcal{C}^*\) is spanned by \(c_4,\ldots,c_9\).

These specific properties of our chosen basis and cocycle are vital for obtaining an effective implementation of a complete generating set of the monster \(\mathbb{M}\).

The Monster group

We deal with the representation of elements of the monster group.

Generators of the monster group \(\mathbb{M}\)

Conway [Con85] has constructed a 196884-dimensional rational representation \(\rho\) of the monster \(\mathbb{M}\) based on representations of two subgroups \(G_{x0} = 2_+^{1+24}.\mbox{Co}_1\) and \(N_0 = 2^{2+11+22}.( M_{24} \times S_3)\) of \(\mathbb{M}\) which generate \(\mathbb{M}\). Here \(G_{x0}\) has a normal extraspecial 2-subgroup \(2_+^{1+24}\) with factor group \(\mbox{Co}_1\), where \(\mbox{Co}_1\) is the automorphism group of the Leech lattice modulo 2. The group \(N_0\) has a normal subgroup \(2^{2+11+22}\), which is a certain 2 group and the factor group is a direct product of the Mathieu group \(M_{24}\) and the symmetric permutation group \(S_3\) of 3 elements.

The group \(N_{x0} = N_0 \cap G_{x0}\) has index 3 in \(N_{0}\) and structure \(2^{1+24} . 2^{11} . M_{24}\). It is generated by elements \(x_\delta\), \(x_\pi\), \(x_e\), \(y_e\), \(z_e\), for all \(x_\delta \in \mathcal{C}^*\), \(\pi \in {{\rm Aut}_{{\rm St}} \mathcal{P}}\) and \(e \in \mathcal{P}\).

Here \(\mathcal{C}^*\) is the Golay cocode defined in section The Golay code and its cocode, \(\mathcal{P}\) is the Parker loop defined in section The Parker loop, and \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) is the automorphism group of \(\mathcal{P}\) defined in section Automorphisms of the Parker loop. The group \(N_{0}\) has a subgroup isomorphic to \({{\rm Aut}_{{\rm St}} \mathcal{P}}\) generated by the generators \(x_\delta, \delta \in \mathcal{C}^*\) and \(x_\pi, \pi \in {{\rm Aut}_{{\rm St}} \mathcal{P}}\). The generators \(x_\delta\) generate the subgroup of diagonal automorphisms of \({{\rm Aut}_{{\rm St}} \mathcal{P}}\).

The group \(N_{0}\) is generated by \(N_{x0}\) and by another element \(\tau\) of \(N_{0}\) or order 3. The group \(G_{x0}\) is generated by \(N_{x0}\) and by another element \(\xi\) of \(G_{x0}\) or order 3. The elements \(x_\delta\), \(x_\pi\), \(x_e\), \(y_e\), \(z_e\), \(\tau\) and \(\xi\) generate the monster group \(\mathbb{M}\). In this package we use the definitions of the generators in [Sey20], which incorporate a modification of [Con85] made in [Iva09]. This leads to simpler relations in \(N_{0}\). The generators \(x_e\), \(y_e\), and \(z_e\) in [Sey20] correspond to the generators \(x_e \cdot z_{-1}^{|e/4|}\), \(y_e \cdot x_{-1}^{|e/4|}\), and \(z_e \cdot y_{-1}^{|e/4|}\) in [Con85].

Representing elements of the monster group

An element of the monster group \(\mathbb{M}\) is represented as an instance of class MM in module mmgroup.

Elements of the monster group are created by the constructor of class MM. Usually, the constructor of class MM takes two arguments tag and i, where tag is a single small letter describing the type of the generator of \(\mathbb{M}\), and i is an integer describing the value of that generator. Alternatively, i may be an instance of the appropriate algebraic structure used for indexing a generator of a given type as indicated in the table below.

Implementation of the generators of the monster group

Math papers may use (at least) Latin or Greek letters for labelling objects, but most programming languages are restricted to ASCII characters. The following table shows how to create generators of the monster group using the constructor of class MM:

Construction of generating elements of the monster
Element	Construction as an instance of class `MM`,
\(x_\delta\)	`MM('d', delta)`, `delta` an instance of class `Cocode`; `MM('d', delta)` returns `MM('d', Cocode(delta))` for `0 <= delta < 0x1000`.
\(x_\pi\)	`MM(pi)`, `pi` an instance of class `AutPL`; `MM('d', delta) * MM('p', n)` is equivalent to `MM(AutPL(delta, n))` for `0 <= delta < 0x1000`, `0 <= n < 244823040` .
\(x_e\)	`MM('x', e)`, `x` an instance of class `PLoop`; `MM(('x', e))` returns `MM('x', PLoop(e))` for `0 <= e < 0x2000`.
\(y_e\)	`MM('y', e)`, `e` as in case \(x_e\).
\(z_e\)	`MM('z', e)`, `e` as in case \(x_e\).
\(\tau^e\)	`MM('t', e)`, exponent `e` is an integer which is taken modulo `3`.
\(\xi^e\)	`MM('l', e)`, exponent `e` is an integer which is taken modulo `3`.

More possibilities for constructing elements of an instance of class MM are given in the description of that class. Multiplication and exponentiation of group elements works a usual.

Multiplication of elements of the monster group

Internally, an element of \(\mathbb{M}\) is represented as a word of the generators given above. Multiplication with the * operator is a concatenation of such words, followed by a reduction step. Multiplication of two reduced elements of the monster group (including the reduction of the result) takes less than 50 milliseconds on the author’s computer.

The reduction after a group operation is done by a new method that tracks pairs of perpendicular 2A axes, see [Sey22] for details.

Python classes implementing the Monster group

class mmgroup.MM(tag=None, i=None, *args, **kwds)

Models an element of the monster group \(\mathbb{M}\)

Let g1 and g2 be instances of class MM representing elements of the monster group. Then g1 * g2 means group multiplication, and g1 ** n means exponentiation of g1 with the integer n. g1 ** (-1) is the inverse of g. g1 / g2 means g1 * g2 ** (-1). We have 1 * g1 == g1 * 1 == g1 and 1 / g1 == g1 ** (-1).

g1 ** g2 means g2**(-1) * g1 * g2.

Let V be a vector space that is a representation of MM, see class MMVector for details. An instance g1 of class MM operates on the vector space V by right multiplication.

Variables:

tag – In the simplest case, parameter tag is a string of length 1 that determines the type of the atomic group element. There are also some special cases for parameter tag `` as indicated below. If ``tag is not given or equal to 1 then the neutral element of the monster group is constructed.
i –
Parameter i is number of the atomic element of a given tag. Depending on the tag, i may be the number of an element of one of the structures PLoop, Cocode, or the number of an element of the Mathieu group M_24, as explained in class AutPL. An element \(\pi\) of the group AutPL is mapped to the element \(x_\pi\) of the Monster group.

The number i may also be an instance of the appropriate class PLoop, Cocode, or AutPL, as indicated in the table below.

Returns:

An element of the monster group

Return type:

an instance of class MM

Standard tags

The tags listed in the following tables are standard tags that can be used for creating generators (or some short words of generators) of the monster group.

Atomic elements of the Monster group
Tag	Number `i`	Type of element
`'p'`	`0-244823039`	The automorphism `AutPL(0, i)` of the Parker loop, see below.
`'d'`	`0-0xfff`	The diagonal automorphism `Cocode(i)` in `AutPL`.
`'x'`	`0-0x1fff`	The element \(x_e\), with `e = PLoop(i)`.
`'y'`	`0-0x1fff`	The element \(y_e\), `e = PLoop(i)`; similar to tag `'x'`.
`'z'`	`0-0x1fff`	The element \(z_e\), `e = PLoop(i)`; similar to tag `'x'`. We have \(x_e y_e z_e = y_e x_e z_e = 1\).
`'t'`	`0-2`	The element \(\tau^i\),
`'l'`	`0-2`	The element \(\xi^i\),
`'q'`	`0-0x1ffffff`	Describes an element of the subgroup \(Q_{x0}\). See remark below.
`'c'`	`0-0xffffff`	A representative of a right coset of \(N_{x0}\) in \(G_{x0}\). See remark below.

Apart from the standard tags there are also some tags for special purposes discussed in the following sections.

Remarks

If i is the string 'r' then a random element with the given tag is generated. If i is the string 'n' then a random element with the given tag is generated, which is different from the neutral element with a very high probability.

If tag == 'd' then i = 'o' generates a random odd and i = 'e' generates a random even diagonal automorphism. In this case i` may also be an instance of class Cocode, representing the diagonal automorphism corresponding to the given element of the Golay cocode.

If tag == 'p' then i may also be an instance of class AutPL. Then the returned atom is the Parker loop automorphism given by that instance. If i is an integer then the Parker loop automorphism AutPL(0, i) is returned. This automorphism is the standard representative of the i-th element of the Mathieu group M_24 in the automorphism group of the Parker loop.

If tag == 'p' then i may also be a string starting with the letter r. This string indicates a certain subgroup of the Mathieu group M_24 as described in section Generating random elements of certain subgroups of M_{24}. Then we generate a random element g of that subgroup, and the returned atom is the standard representative AutPL(0, g) of g in the automorphism group of the Parker loop.

If tag is 'x', 'y' or 'z' then i may also be an instance of class PLoop, representing an element of the Parker loop.

The exponent i for a tag 't' or 'l' is reduced modulo 3.

The tag 'q' is useful for encoding an element of the subgroup \(Q_{x0}\) of the monster. An atom with tag 'q' and index i encodes the element \(x_d \cdot x_{\delta} \cdot x_{\theta(d)}\), with \(d\) = PLoop(i >> 12) \(\in \mathcal{P}`\), \(\delta\) = Cocode(i & 0xfff) \(\in \mathcal{C}^*\), and \(\theta: \mathcal{P} \rightarrow \mathcal{C}^*\) the cocycle of the Parker loop.

The tag 'c' with index i encodes a representative of the right coset \(N_{x0} g, \, g \in G_{x0}\) of \(N_{x0}\) in \(G_{x0}\) that maps the standard frame \(\Omega\) in the Leech lattice modulo 2 to a type-4 vector given by the index i. Here i encodes a vector in the Leech lattice modulo 2 as in the description for tag 'q'. That vector must be of type 4. The sign bit of that vector is ignored. Here i may also be an instance of class XLeech2 representing a type-4 vector. We warn the user that the index i may specify any element of the corresponding right coset \(N_{x0} g\); and that this element may depend on the version of the package.

Generating a random element of the subgroup of the monster

If parameter tag is equal to the string 'r' then parameter i should be a string describing a subgroup of the monster group. E.g. if parameter i is the string 'G_x0' then a uniform distributed element of the subgoup 'G_x0' of the Monster is generated. The group 'G_x0' is the centralizer of the involution \(x_{-1}\); and it has structure \(2^{1+24}.\mbox{Co}_1\). For more information about generating random elements in subgroups of the Monster we refer to Section Generating random elements of certain subgroups of the Monster in the API reference.

Here Parameter i may also be a positive integer. If this is the case then an element of the monster of shape \(g_0 t_1 g_1 t_2 g_2 ... t_i g_i\) is created, where \(g_j\) is a random element of 'G_x0', and \(t_j\) is \(\tau^{\pm 1}\).

Generating an element of monster from its internal representation

If parameter tag is equal to the string 'a' then parameter 'i' should be an array-like object containing the internal representation of an element of the monster group.

Internally, an element of the monster group is represented as an array of unsigned 32-bit integers, where each entry of the array describes a generator. See section Header file mmgroup_generators.h for details.

Special types accepted as tags

In the simplest case the argument tag in the constructor is a string of length 1. There are a few other types which are also accepted as tags. For such a special tag, the following parameter i in the constructor is ignored.

Especially, we may encode a word of standard generators as a list of tuples as indicated in the table below.

Legal types as tags in the constructor of class `MM`
Object of type	Evaluates to
type `list`	A list represents the product of its entries in the given order. An entry `MM(tag, i)` can be abbreviated to the tuple `(tag, i)`.
class `PLoop`	The Parker loop element \(d\) given by that object is mapped to \(x_d \in \mathbb{M}\).
class `AutPL`	The Parker loop automorphism \(\pi\) given by that object is mapped to \(x_\pi \in \mathbb{M}\).
class `Cocode`	The Golay cocode element \(\delta\) given by that object is mapped to \(x_\delta \in \mathbb{M}\).
class `XLeech2`	The element corresponding to that element of \(Q_{x0}\) is created.
class `MM`	A deep copy of the given element of \(\mathbb{M}\) is made.
`str` of length greater than `1`	For an instance `g` of class `MM` we have `MM(str(g)) == g`. So we can reread printed elements of `MM`.

Special strings accepted as a value after tag ‘q’

The following strings are accepted after tag ‘q’. They denote special elements in the group \(Q_{x0}\) as indicated in the following table.

String after tag q

Evaluates to

'+', '-'

\(x_1, x_{-1}\)

'Omega', '-Omega'

\(x_\Omega, x_{-\Omega}\), where \(\Omega\) is the Golay code word \((1, \ldots, 1)\)

'omega', '-omega'

\(x_\omega, x_{-1}x_{\omega}\) , for the cocode word \(\omega\) = [0,1,2,3]

'v+', 'v-'

\(x_\delta, x_{-1} x_{\delta}\), for the cocode word \(\delta\) = [2,3], see [Sey22] background

The strings '+', '-', 'Omega', '-Omega' are also accepted after a tag x, meaning the same element. They are also accepted after tags x, z with the obvious meaning, e.g. ('y', '-Omega') = \(y_{-\Omega}\), ('z', '-') = \(z_{-1}\).

as_Co1_bitmatrix()

Convert element of \(G_{x0}\) to a 24 times 24 bit matrix

The bit matrix is returned as a 24 times 24 bit numpy array of 8-bit unsigned integers, with each entry equal to 0 or 1.

That matrix operates by right multiplication on a vector representing an element of the Leech lattice mod 2. See method mmgroup.XLeech2.as_Leech2_bitvector for the encoding of such a vector.

The function raises ValueError if the element is not in the subgroup \(G_{x0}\) of the Monster.

as_int()

Map element of the Monster to a 255-bit integer

The method returns a 255-bit integer n describing the element of the Monster group. This integer is unique for each element of the Monster, so that it can be used e.g. for storing large subsets of the Monster in a hash table.

Function MM_from_int reconstructs the element of the Monster from the number returned by this function.

Warning:

The numbering used here is not contiguous and not portable between difffernt versions of the mmgroup package!

For writing a element to a file, you should convert it to a string instead!

as_tuples()

Convert group element to a list of tuples

For a group element g the following should hold:

self.__class__(self.as_tuples()) == self .

This shows how to convert a group element to a list of tuples and vice versa.

chi_G_x0(involution=None)

Compute characters of element of subgroup \(G_{x0}\)

If the element is in the subgroup \(G_{x0}\) then the function returns a tuple \((\chi_M, \chi_{299}, \chi_{24}, \chi_{4096})\) of integers. Otherwise it raises ValueError.

Here \(\chi_M\) is the character of the element in the 196833-dimensional rep \(198883_x\) of the monster.

By Conway’s construction of the monster we have:

\(198883_x = 299_x \oplus 24_x \otimes 4096_x \oplus 98280_x\),

for suitable irreducible representations \(299_x, 24_x, 4096_x, 98280_x\) of the group \(G_{x0}\). The corresponding characters of the element of \(G_{x0}\) are returned in the tuple given above.

While the product \(\chi_{24} \cdot \chi_{4096}\) is well defined, the factors \(\chi_{24}\) and \(\chi_{4096}\) are defined up to sign only. We normalize these factors such that the first nonzero value of the pair \((\chi_{24}, \chi_{4096})\) is positive.

If parameter involution is a 2B involution \(i\) then the element \(g\) given by self must centralize that involution \(i\). In this case we compute the corresponding characters of \(g^h\) for a \(h \in \mathbb{M}\) such that \(i^h\) is the central involution of \(G_{x0}\).

chi_powers(max_e=None, ntrials=100, mp=1)

Return order and some character information of the element

Let \(g\) be the element of the Monster given by self; and let \(\chi_M\) be the character given by the 196833-dimensional rep \(198883_x\) of the monster. The method tries to compute characters \(\chi_M(g^e)\) for values \(e\) dividing the order of \(g\). This method is very fast; but it may fail, as discusssed below.

The function returns a triple (o, chi, h), where o is the order of the element \(g\).

Short description:

Part chi of the return value is a dictionary that maps the divisors e of the order o to the character values \(\chi_M(g^e)\). We put chi[e] = None if \(\chi_M(g^e)\) has not been computed.

If o is even then \(\chi_M(g^{o/2})\) is computed with a very high probability. So we can check if \(g\) powers up to a 2A or to a 2B involution. If \(g\) powers up to a a 2B involution then all characters are computed with high pobability.

Exact description:

The method succeeds with high probability if \(g\) powers up to a 2B involution, and also if \(g \in G_{x0}\). In other cases the method usually fails. If the character of an element is computed then the characters of the powers of that element are also computed.

The method tries to find an element \(h\) of the Monster such that computing the character of \(h^{-1} g h\) is easier than computing the character of \(g\). Here \(h = 1\) is possible. The function returns \(h\) in part h of the return value. We use a probabilistic algorithm to compute \(h\).

If \(o\) is even and chi[o//2] is not None then we asssert that \(h^{-1} g^{o/2} h\) is equal to the standard 2A or 2B involution. The standard 2A involution is \(x_\delta\), where \(\delta\) is the Golay cocode element \((2,3)\). The standard 2B involution is the central involution \(x_{-1}\) of \(G_{x0}\). Here the computation of chi[o//2] may fail with a very small probability, depending on the number of trials, as given by parameter ntrials.

If parameter max_e is an integer (i.e. not None), we may omit some computations of chi[e] for e > max_e. We always try to compute chi[o//2] if o is even.

If parameter mp is greater than 1 then we may use up to mp parallel processes.

conjugate_involution(check=True, ntrials=40, verbose=0)

Find an element conjugating an involution into the centre

If the element \(g\) given by self is an involution in the monster then the method computes an element \(h\) of the monster with \(h^{-1} g h = z\), where \(z\) is defined as follows:

If \(g = 1\), we put \(h = z = 1\)

if \(g\) is a 2A involution (in the monster) then we let \(z\) be the involution in \(Q_{x0}\) corresponding to the Golay cocode word with entries \(2,3\) being set.

if \(g\) is a 2B involution (in the monster) then we let \(z\) be the central involution in \(G_{x0}\)

The function returns a pair (I, h), where \(h\) as an element of the instance MM of class MMGroup. We put I = 0 if \(g = 1\). We put I = 1, 2 if \(g\) is a 2A or 2B involution, respectively.

This function may take a long time. Parameter ntrials gives the number of trials to find a suitable element \(h\). Default is ntrials = 40. The function may fail after that number of trials even if the element is a 2B involution.

If parameter check is True (default) then the function first checks if g is an involution.

In future versions support for multiprocessing may be added.

conjugate_involution_G_x0(guide=0, group=None)

Wrapper for corresponding method in class mmgroup.Xsp2_Co1

Here self must be an involution \(g\) in the subgroup \(G_{x0}\) of the Monster. This function performs the same computation as the corresponding method in class mmgroup.Xsp2_Co1. It returns a pair (iclass, a) such that \(h = a^{-1} g a\) is a (fixed) representative of the class of \(g\) in the group \(G_{x0}\). Here h is described by the integer iclass as documented in the corresponding method mentioned above.

If group is None (default) then a is an instance of the same class as g.

copy(): Return a deep copy of the group element

half_order(max_order=119)

Return the (halved) order of the element of the monster group

The function returns a pair (o, h), where o is the order of the element.

If o is even then the function returns the pair (o, h), where h is the element raised to to the (o/2)-th power. Otherwise the function returns the pair (o, None).

Parameter max_order is as in function check_mm_order.

If h is in the subgroup \(G_{x0}`\) then h is returned as a word in the generators of that subgroup.

half_order_chi(ntrials=40)

Return order and some character information of the element

This method is deprecated. use method chi_powers instead!

The function returns a triple (o, chi, h), where o is the order of the element \(g\) of the monster given by self.

If the order \(o\) of \(g\) is odd then the triple (o, None, None) is returned.

If the order of \(g\) is even then we return the triple (o, chi, h). Here h is an element \(h\) of \(\mathbb{M}\) such that \(z = h^{-1} g^{o/2} h\) is the standard 2A or 2B involution as in method conjugate_involution.

If \(g\) powers up to a 2B involution then chi is equal to the character of \(u = h^{-1} g h\). Here the character of the element \(u\) of \(G_{x0}\) is returned as a quadruple as in method chi_G_x0.

If \(g\) powers up to a 2A involution then chi is equal to to None.

in_G_x0()

Check if the element is in the subgroup \(G_{x0}\)

The function returns True if this is the case. If this is the case then the element is converted to a word in the generators of \(G_{x0}\).

This method uses geometric information about the Leech lattice taken from [Iva99].

in_N_x0()

Check if the element is in the subgroup \(N_{x0}\)

The function returns True if this is the case. If this is the case then the element is converted to a word in the generators of \(N_{x0}\).

in_Q_x0()

Check if the element is in the subgroup \(Q_{x0}\)

The function returns True if this is the case. If this is the case then the element is converted to a word in the generators of \(Q_{x0}\).

is_reduced()

Return True if the element of the monster group is reduced

An element g of the monster group represented by an instance of this class may be reduced by calling g.reduce().

property mmdata

Return the internal representation of the group element

Internally, an element of the monster group is represented as an array of unsigned 32-bit integers, where each entry of the array describes a generator. See section Header file mmgroup_generators.h for details.

order(max_order=119)

Return the order of the element of the monster group

We use the method in [LPWW98], section 7, for computing the order of an element of the monster.

If the argument max_order is present then the order of the element is checked up to (and including) max_order only. Then the function returns 0 if the order is greater than max_order. By default, the function returns the exact order of the element.

reduce()

Reduce a group element

This method reduces the group element in place. The reduced form of an element of the Monster is unique; i.e. it depends on the value of the element only, and not on its representation as a word of generators.

The following methods of this class reduce an instance of this class: as_int(). Converting an instance of this class to a string, by using method __str__() or the built-in function str(), also performs a reduction prior to the conversion.

Other methods designed for internal purposes, e.g. as_tuples() or mmdata, may or may not reduce an instance of this class. The result of a group operation may or may not be reduced.

Note that the reduction of an element of the Monster is a time-comsuming operation, so that we’d better do it in a lazy way.

Finding an optimal or shortest representation of an element as a word of generators is beyond our current capabilties. Also, the reduction process depends on many internal details. Thus a future version of this package may return a different reduced form of an element of the Monster.

Functions dealing with elements of the Monster group

mmgroup.MM_from_int(n)

Obtain an element of the Monster from its number n

if g is an instance of class MM then we have

MM_from_int(g.as_int()) == g

Generating random elements of certain subgroups of the Monster

In this section we present various subgroups of the Monster known by the mmgroup package. Each of these groups is labelled ba a string. In the documentation of class MM we have already seen the basic way how to generate a random element of a subgroup of the Monster. E.g. calling method MM('r', 'G_x0') generates an element of the subgroup \(G_{x0}\) of structure \(2^{1+24}.\mbox{Co}_1\). We may use some other names instead of 'G_x0' for generating random elements in other subgroups of the Monster. Details will be given in the following subsections.

At present, these names are used to generate random elements of the corresponding subgroup. In future versions of mmgroup we may also deal with constructive membership testing in these groups, and with intersections of these groups. So we will only label groups, where the embedding of this group in the Monster is sufficiently well understood.

Describing a random subgroup of the Monster

The subgroups of the Monster recognized by the mmgroup package fall in two (not necessarily disjoint) categories. There are small subgroups that are given by the sets of their generators; and there are large 2-local subgroups which are given by their centralizers. Each subgroup has one or more names; and it is described in the following two sections.

The intersection of two groups is obtained by joining their names with an '&' character. E.g, 'G_x0 & N_0' means the intersection of the two groups with names 'G_x0' and 'N_0'. We have chosen the definition of the subgroups carefully, so that at least in principle their intersections can be computed.

But not all possible computations have been implemented. For each group there is a column ‘Supported’ in the following tables, with an entry ‘full’, ‘yes’, or ‘no’. If all groups in a tuple are supported ‘full’ then we may compute intersections of these groups. If a group has an entry ‘yes’ then we may use that group. Otherwise using that group might lead to an error.

A function dealing with the name of a subgroup may raise NotImplementedError if that subgroup is not supported.

Caution:

The user should check the corresponding entry ‘Supported’ in the tables in the follwing two subsections before using the name of a group! Using a name of a group that is not supported might fail without notice!

Some small subgroups of the Monster

The following small subgroups of the Monster are recognized:

Some small subgroups of the Monster
Name	Structure	Generators	Supported
N_0	\(2^{2+11+22}.(S_3 \times M_{24})\)	\(x_d, y_d, x_\delta, x_\pi, \tau\)	full
N_0_e	\(2^{2+11+22}.(3 \times M_{24})\)	\(x_d, y_d, x_\delta, x_\pi, \tau, \delta \; \mbox{even}\)	full
N_x0	\(2^{1+24+11}.M_{24}\)	\(x_d, y_d, x_\delta, x_\pi\); equal to \(G_{x0} \cap N_0\)	full
N_x0_e	\(2^{2+11+22}.M_{24}\)	\(x_d, y_d, x_\delta, x_\pi, \delta \; \mbox{even}\)	full
Q_x0	\(2^{1+24}\)	\(x_d, x_\delta\)	no
AutPL	\(2^{11}.M_{24}\)	\(x_\delta, x_\pi\)	no

Notation for the generators is as in mm_group.

Large 2-local subgroups of the Monster

We have implemented (or will implement) the following 2-local subgroups of the Monster:

Large 2-local subgroups of the Monster
Name	Structure	Normalizer of group generated by	Supported
G_x0, G_1	\(2^{1+24}.\mbox{Co}_1\)	\(x_{-1}\)	full
N_0, G_2	\(2^{2+11+22}.(S_3 \times M_{24})\)	\(x_{-1}, x_{\pm \Omega}\)	full
G_3	\(2^{3+6+12+18}.(L_3(2) \times 3S_6)\)	\(x_{-1}, x_{\pm \Omega}, x_\omega\)	no
G_5t	\(2^{5+10+20}.(S_3 \times L_5(2))\)	\(x_{-1}, x_{\pm \Omega}, x_\omega, x_{\{0,1,4,5\}}, x_{\{0,2,4,6\}}\)	no
G_5l	?	\(x_{-1}, x_{\pm \Omega}, x_\omega, x_{\{0,1,4,5\}}, x_{\{0,2,4,7\}}\)	no
G_10	\(2^{10+16}.\Omega_{10}^+(2)\)	\(x_d, y_d, x_{ij}, \quad 0 \leq i < j < 8,\) \(d \in \{-1, \pm \Omega, d_8\}\)	no
B	\(2.B\)	\(x_{\{2,3\}}\)	yes
2E_6	\(2^2.{}^2E_6(2):S_3\)	\(x_{\{2,3\}}, x_{\{2,4\}}, x_{\{3,4\}}\)	no

Notation is as in the previous section. Furthermore, \(d_8\) is the standard octad \(\{0,1,2,3,4,5,6,7\}\). \(\omega\) is the element of the Golay cocode given by the tetrad \(\{0,1,2,3\}\) as in [Sey20].

The names G_x0 and N_0 are adopted from [Con85]. The names and structures of G_1, G_2, G_3, G_5t, G_5l and G_10 are taken from [Iva09], Chapter 4.1 et seq. We have G_1 = G_x0 and G_2 = N_0. The other names indicate the large simple subgroups involved in that group. Note that all these subgroups are maximal in the Monster, except for G_5l.

Long-term stable storage of elements of the Monster group

The mmgroup package has been used in several research projects. In some of these projects, elements of the Monster group have been stored permanently in a file or published in a research paper. Here it is important to understand how elements of the Monster should be stored permanently, and how they should be reread into an application using a different version of the mmgroup package.

Short recommendation:

Always convert elements of the Monster group to strings before storing them permanently or publishing them! Always convert such strings to instances of class MM before using them!

Detailed explanation:

For permanent storage, an element of the Monster given as an instance of class MM should be converted to a string by using one of the standard python functions str or print. We will ensure that future versions of the mmgroup package can interpret such a string correctly. Here Release 0.0.8 of the mmgroup package is interoperable with all later releases. The standard way to convert such a string back to an instance of class MM is to apply the constructor of that class to that string.

Comparing elements of the Monster by comparing strings is not feasible. Here the strings should be converted to instances of class MM before comparing them. One reason for this restriction is that at present we do not know how to find a shortest possible reduced form of an element. So future versions of mmgroup may implement better reduction algorithms.

Method as_int of class MM converts an element of the Monster group to an integer. It is ok to compare two such integers when they have been generated by the same version of the mmgroup package. When switching to a new version, such integers should be converted to instances of class MM using function MM_from_int in the mmgroup package; and then they should be converted to strings. Pickling instances of class MM with the standard python module pickle is also discouraged, when switching to another version of the mmgroup package.

The representation of the Monster group

We deal with the 196884-dimensional representation of the monster.

The monster \(\mathbb{M}\) has a 196884-dimensional representation \(\rho\) with coefficients in \(\mathbb{Z}[\frac{1}{2}]\), see [Con85]. Representation \(\rho\) is called \(196884_x\) in [Con85]. We obtain a modular representation \(\rho_p\) of \(\mathbb{M}\) by reducing the matrix coefficients of the representation \(\rho\) modulo an odd number \(p\). The representation \(\rho_p\) can be implemented very efficiently if \(p + 1\) is a small power of two. The current version of the mmgroup package supports the representations \(\rho_p\) of \(\mathbb{M}\) for p = 3, 7, 15, 31, 127, 255. In the sequel we are a bit sloppy, calling \(\rho_p\) a vector space also in cases p = 15, 255. The user may select these values for obtaining representations modulo 5 and 17, respectively.

One purpose of the mmgroup package is to give the user the capability to compute in the 196884-dimensional representation \(\rho_p\) of the monster group \(\mathbb{M}\).

For calculating in \(\rho_p\) the user may create an instance of class MM that models an element g of the monster group \(\mathbb{M}\) as described in section The Monster group. Then the user may create an instance v of class MMVector that models a vector in \(\rho_p\), with p as above. The element g of \(\mathbb{M}\) acts on the vector v by right multiplication.

Creating basis vectors of the representation space \(\rho_p\)

By construction of \(\rho_p\) it is natural to label a basis vector of \(\rho_p\) by a tuple (tag, i0, i1) with integers i0, i1, as described in the next section. Here tag is a single capital letter and indices i0, i1 are unsigned integers; these three quantities describe a basis vector of the space V.

To create a basis vector of \(\rho_p\) corresponding to the tuple (tag, i0, i1) the user may call the constructor MMVector(p, tag, i0, i1).

For a fixed characteristic p the function MMV(p) returns an object corresponding to the vector space \(\rho_p\). Thus the sequence

>>> from mmgroup import MMV  
>>> V = MMV(p)  
>>> v = V(tag, i0, i1)

creates the same basis vector v as the statement v = MMVector(p, tag, i0, i1).

Description of the basis vectors of the representation space

The following table shows the tags available for describing basis vectors. The column Vector in that table shows the basis vector in the notation of [Sey20]. The column Tuple shows the basis vector as a tuple (tag, i0, i1).

Basis vectors of the representation of the monster
Vector	Tuple	Remarks
\((ij)_1\)	`('A',i,j)`	`0 <= i,j < 24`; we have \((ij)_1 = (ji)_1\).
\(X_{ij}\)	`('B',i,j)`	`0 <= i,j < 24, i != j`; we have \(X_{ij} = X_{ji}\).
\(X^+_{ij}\)	`('C',i,j)`	`0 <= i,j < 24, i != j`; we have \(X^+_{ij} = X^+_{ji}\).
\(X^+_{d \cdot \delta}\)	`('T',o,s)`	`o` and `s` can be obtained as follows. Let, `x = SubOctad(d, delta)`. Then `x.vector_tuples()` returns the tuple `(1, 'T', o, s)`. \(d \in \mathcal{P}\), \(\delta \in \mathcal{C^*}\), \(d\) an octad, \(\delta \subset d\), \(\delta\) even. We have `0 <= o < 759`, `0 <= s < 64`.
\(X^+_{d \cdot i}\)	`('X',d,i)`	`0 <= d < 2048`, `0 <= i < 24`, `d` represents the element `PLoop(d)` of the Parker loop \(\mathcal{P}\)
\(d^+ \otimes_1 i\)	`('Z',d,i)`	`d` and `i` as in case `('X',d,i)`
\(d^- \otimes_1 i\)	`('Y',d,i)`	`d` and `i` as in case `('X',d,i)`

Remarks

The space \(\rho_p\) is an orthogonal space. Two basis vectors are orthogonal except when equal or opposite. The basis vectors \((ij)_1\) have norm 2 in case \(i \neq j\). All other basis vectors have norm 1.

In the tuple ('T',o,s) the integers o and s describe the instance SubOctad(o, s) of class XLeech2. Here o and s may be anything that is accepted as input for SubOctad(o, s)

In the tuples ('X',d,i), ('Y',d,i), ('Z',d,i), the input d may be an instance of class PLoop or anything such that PLoop(d) is an instance of class PLoop. For an instance d of class PLoop we have:

('X',d,i) == -('X',-d,i) == ('X',~d,i) ,

('Y',d,i) == -('Y',-d,i) == -('Y',~d,i) ,

('Z',d,i) == -('Z',-d,i) == ('Z',~d,i) .

The value of ('X',~d,i) has been set by convention; the other equations are forced.

The basis vector \(d^+ \otimes_1 i\) in [Sey20] is equal to the basis vector \((-1)^{|d/4|} \cdot d^+ \otimes_1 i\) in [Con85]. This modification simplifies the formulas for the operation of the element \(\xi\) of \(\mathbb{M}\) on \(\rho_p\).

A first or second index following a tag may be 'r', indicating a random integral index. Any omitted index after a given index 'r' is interpreted as 'r'. For tags 'A', 'B', 'C', 'T' the second index should be 'r' or omitted if the first index is 'r', since in these cases the two indices are not sufficiently independent.

Representing a vector as a list of tuples

For creating an arbitrary (but yet sparse) vector in \(\rho_p\) the user may call MMVector(p, data_list), where data_list is a list of tuples (factor, tag, i0, i1). Here (tag, i0, i1) describes a unit vector and the (optional) integer factor is a scalar factor for that unit vector. Then the constructor returns the linear combination of the unit vectors given in the list.

In order to generate a random multiple of a basis vector, inside a list of tuples, the (optional) component factor of a tuple can be set to one of the following values:

'u': equivalent to 1

's': a factor 1 or -1 selected at random

'n': a random nonzerodivisor modulo p

'r': a random integer modulo p

Operations on vector in the representation \(\rho_p\)

Vector addition, subtraction and scalar multiplication can be done with operators +, - and * as usual. Elements of the monster group operate on vectors by right multiplication. Only vectors modulo the same characteristic p can be added.

The following code example generates an element g of the monster group and a vector v in the vector space \(\rho_3\) and displays the result g * v of the operation of g on v. Note that a basis vector (tag, i0, i1) is displayed in the form tag_i0_i1. For a displayed index i0 or i1 the suffix h means hexadecimal notation.

>>> # An instance of class MM represents an element of the monster
>>> from mmgroup import MM
>>> # Function MMV is used to create a representation space
>>> from mmgroup import MMV
>>> # Create representation space V for the monster (modulo 3)
>>> V = MMV(3)
>>> # Create an element g of the monster group
>>> g = MM([('d', 0x123), ('p', 217821225)])
>>> # Create a vector v in the representation space V 
>>> v = V([('T', 712, 13), (2, 'X', 0x345, 13)])
>>> # Let g operate on v by right multiplication
>>> print(v * g)
MV<3;-T_444_0fh+X_244h_11>

Special tags for creating vectors in the representation \(\rho_p\)

Apart from the standard tags A, B, C, T, X, Y, and Z, the constructor of class MMVector accepts a variety of special tags. Details are given in the following list:

Special tags for constructing a vector
tag, i0, i1	Evaluates to
`('D', i0)`	Shorthand for `('A', i0, i0)`
`('I', i0, i1)`	Shorthand for the sum of the basis vectors `('A', i0, i0)` + `('A', i1, i1)` - `('A', i0, i1)` - `2 ('B', i0, i1)`, see remark below.
`('J', i0, i1)`	Shorthand for the sum of the basis vectors `('A', i0, i0)` + `('A', i1, i1)` - `('A', i0, i1)` + `2 ('B', i0, i1)`, see remark below.
`('U')`	Tag `'U'` (without any further parameters) stands for the sum `('A', 0, 0)` + `('A', 1, 1)` + … + `('A', 23, 23)`.
`('E', i)`	This is the basis vector with linear index `i`. See the following subsection for details.
`('S', data)`	Here `data` is an array-like object (as defined in the numpy package) that encodes a vector in sparse representation as an array of unsigned 32-bit integers. This is for internal use. For details see the following subsection: Sparse representation of vectors in \(\rho_p\).
`('V', data)`	Here `data` is an array like object (as defined in the numpy package) that encodes a one-dimensional array of integers of length 196884. The order of the entries is as in the next section.
`('R')`	Tag `'R'` (without any further parameters) stands for the generation of a uniform distributed random vector.
`(i, v)`, `i` integer	Here `i` is an integer and `v` is a vector, i.e.an instance of class `MMVector`. Then the vector `i * v` is generated. This is useful for extending the modulus `p` of a vector, see remark below.

Remarks

The vectors labelled by ('I', i0, i1) and ('J', i0, i1) are axes of the elements \(x_\delta\) and \(x_{-1} x_\delta\) of the monster, respectively, see [Con85]. The centralizers of these elements and also of their axes in the monster have structure \(2 \cdot B\), where \(B\) is the Baby Monster, see [Asc86], [Con85], [Iva09] for background. E.g. the axes \(v^+\) and \(v^-\) in [Sey22] may be obtained as MMVector(15, 'I', 2, 3) and MMVector(15, 'J', 2, 3), respectively.

The modulus of a vector can be extended as follows. Assume that v is a vector in \(\rho_3\), given as an instance of class MMVector. Then w = 5 * v is a well-defined vector in \(\rho_{15}\). Vector w can be constructed as follows: V15 = MMV(15); w = V15(5, v). Note that the construction w = V15(5*v) leads to an error, since 5*v is defined modulo 3, but not modulo 15.

Linear order of the basis vectors

By construction of the representation \(\rho_p\), it is most natural to use a tuple (tag, i0, i1) for indexing a basis vector of \(\rho_p\). There is also a linear order of these entries. Such a linear order is required e.g. for expressing a vector in \(\rho_p\) as an array of integers modulo \(p\). Therefore an index given by a tuple (tag, i0, i1) is mapped to linear index 0 <= i < 196884. Legal standard tuples are listed in the following table:

Conditions for indices `i0`, `i1`
Tag	Condition for `i0`	Condition for `i1`
`'A'`	`0 <= i0 < 24`	`0 <= i1 < 24`
`'B', 'C'`	`0 <= i0 < 24`	`0 <= i1 < 24`, `i1 != i0`
`'T'`	`0 <= i0 < 759`	`0 <= i1 < 64`
`'X', 'Y', 'Z'`	`0 <= i0 < 2048`	`0 <= i1 < 24`

For tag = 'A', 'B', 'C', we also have (tag, i0, i1) == (tag, i1, i0).

The linear order of the tuples (tag, i0, i1) is as follows:

offset 0:

(A,0,0), (A,1,1), ..., (A,23,23)

offset 24:

(A,1,0),

(A,2,0), (A,2,1)

…

(A,23,0), (A,23,1), ..., (A,23,22)

offset 300:

Tuples (B,i0,i1), same order as tuples (A,i0,i1) for i0 > i1

offset 576:

Tuples (C,i0,i1), same order as tuples (A,i0,i1) for i0 > i1

offset 852:

(T, 0,0), (T, 0,1), ..., (T, 0,63)

(T, 1,0), (T, 1,1), ..., (T, 1,63)

…

(T,758,0), (T,758,1), ..., (T,758,63)

offset 49428:

(X, 0,0), (X, 0,1), ..., (X, 0,23)

(X, 1,0), (X, 1,1), ..., (X, 1,23)

…

(X,2047,0), (X,2047,1), ..., (X,2047,23)

offset 98580:

Tuples (Z,i0,i1), same order as corresponding tuples (X,i0,i1)

offset 147732:

Tuples (Y,i0,i1), same order as corresponding tuples (X,i0,i1)

Sparse representation of vectors in \(\rho_p\)

Internally, a vector \(\rho_p\) is sometimes given in sparse representation. This is useful for sparse vectors containing many zero entries. In sparse representation the vector is given as an array of unsigned 32-bit integers. Here each entry of the array encodes a multiple of the basis vector. Such an entry it interpreted as follows:

Bit fields in an entry of a sparse representation
Component	`tag`	`i0`	`i1`	`factor`
Bits	`27 - 25`	`24 - 14`	`13 - 8`	`7 - 0`

This corresponds to the tuple (factor, tag, i0, i1) which denotes a multiple of a basis vector as described in subsection Representing a vector as a list of tuples.

Tags are mapped to integers as follows:

Mapping of integers to tags
`'A'`	`'B'`	`'C'`	`'T'`	`'X'`	`'Z'`	`'Y'`
`1`	`2`	`3`	`4`	`5`	`6`	`7`

Other data types accepted as tags for vectors in \(\rho_p\)

Some data types are accepted as tags and interpreted as described in the following table. In this case parameters i0, i1 after a tag must not be set.

Legal types for constructing a vector

type

Evaluates to

List of tuples

This evaluates to a vector as described in subsection Representing a vector as a list of tuples.

An entry of such a list may also be an instance of class MMVector or a string.

class MMVector

A deep copy of the given vector is returned.

class XLeech2

If tag is of type XLeech2 then the (possibly negative) basis vector corresponding to that tag in \(Q_{x0}\) is created.

str

For an vector v in V we have V(str(v)) == v.

This is helpful for rereading printed vectors.

('Axis', g)

If a pair containing the string 'Axis' and a 2A involution g in the Monster group is given then we contruct the axis corresponding to that involution (with norm 8) as described in [Con85]. Here g should be an instance of class XLeech2 or MM. A integer or string g describes the element MM('q', g).

Python classes implementing the representation of the Monster group

class mmgroup.MMVector(p, tag=0, i0=None, i1=None)

Models a vector in a representation of the monster group.

The construction of vectors in the representations \(\rho_p\) of the monster group (using e.g. the constructor of this class) is documented at the beginning of section The representation of the Monster group. There a basis vector of that representation is described as a tuple (tag, i0, i1), where tag is a single capital letter and i0, i1 are integers. So we may invoke the constructor of this class as follows:

Parameters:

p – Modulus p of the representation \(\rho_p\).
tag – Tag of the unit vector to be constructed. In the standard case this is a single capital letter describing the type of the basis vector.
i0 – First index in the tuple describing the basis vector.
i2 – Second index in the tuple describing the basis vector.

Linear operations can be used for for creating linear combination of unit vectors. This is just the simplest case of the construction of a vector in \(\rho_p\). Section The representation of the Monster group contains a large number of further possibilities for creating such vectors.

Addition and subtraction of vectors in the same space work as usual. This is also the case for scalar multiplication with integers. An element g of the monster group (given as an instance of class MM) operates on a vector v (given as an instance of this class) by right multiplication.

An entry of a vector v (given as an instance of this class) may be addressed as v[tag, i0, i1], where tag is a single letter in the string ABCTXYZD and i0 and i1 are integers, such that the tuple (tag, i0, i1) describes a basis vector. Getting and setting entries of a vector is as in the numpy package. Here i0 and i1 may also be slices of integers in the same way as in numpy arrays. Depending on the tag, the value i0 or i1 may also be a single instance of the appropriate class, as described in the remarks after table Basis vectors of the representation of the monster .

The entries of vector v also have a linear order as described at the beginning of section The representation of the Monster group. Here v['E', i] is the i-th entry in that order. Index i may also be a slice of integers in the same way as in a one-dimensional numpy array.

The internal representation of a vector v in this class is not part of the public interface. Use v['E'] to convert v to an one-dimensional array of 8-bit integers of length 196884.

as_sparse()

Return vector in sparse representation

The sparse representation of a vector is returned as a one-dimensional numpy array of 32-bit integers. Here each entry of that array represents a nonzero component of the vector. Such an entry it interpreted as described in method from_sparse of class MMSpace.

Entries with value zero are dropped.

as_tuples()

Return vector in tuple representation

The function returns a list of tuples (factor, tag, i0, i1). Here (tag, i0, i1) describes a basis vector and value is the coordinate of that vector.

Entries with coordinate zero are dropped.

mul_exp(g, e=1, break_g=False)

Multiply the vector with g ** e inplace

Here g is an element of the monster group represented as an instance of class MM and e is an integer. The vector is updated and the updated vector is returned.

Afterwards, the vector contains an attribute last_timing containing the run time of this operation in seconds. This is useful for benchmarking.

By default, we try to simplify the expression g ** e before multiplying it with the vector. If break_g is set, we always do abs(e) multiplications with g or with its inverse.

projection(*args)

Return projection of the vector v onto a subspace.

Each argument describes a subspace of this space V. The projection of the vector to the space W spanned by all these subspaces is returned.

In the current version each argument must be a tuple (tag, i0, i1) that describes a subspace generated by a basis vector. A legal tag is letter in the string ABCTXYZD, as explained in table Basis vectors of the representation of the monster and class MMSpace.

class mmgroup.MMSpace(*args, **kwds)

Models a 196884-dimensional representation of the monster group

This class contains a collection of functions for manipulating vectors in the representation \(\rho_p\) of the monster group. Such vectors are instances of class MMVector. Most of these function are used implicitly in the operators applied to these vectors.

Some of these function may be helpful for the user; so we document them in the mmgroup API reference.

static index_to_short(tag, i0=-1, i1=-1)

Convert index to a short Leech lattice vector

If tag is an integer, this is interpreted a linear index for a basis vector in the representation \(\rho_p\) as in method tuple_to_index. Otherwise the tuple (tag, i0, i1) is interpreted a standard index for such a basis vector. If tag is an instance of class MMVector, which is a nonzero multiple of a basis vector, then that basis vector is taken.

Some but not all of these basis vectors correspond to short vector in the Leech lattice up to sign. If this is the case then the function returns a short vector of the Leech lattice as a numpy array of signed 32-bit integers of length 24. The norm of the returned vector is 32.

The function raises ValueError if the basis vector in \(\rho_p\) does not correspond to a short vector.

The sign of the short vector is undefined, but two calls referring to the same basis vector return the same short vector.

classmethod index_to_tuple(index)

Convert linear index to tuple (tag, i0, i1)

This method reverses the effect of method tuple_to_index. Given a linear index 0 <= i < 196884 for a basis vector, the function returns that index as a tuple (tag, i0, i1) with tags one letter of the string "ABCTXYZ" and integers i0, i1.

See method tuple_to_index for details.

If index is an instance of class MMVector, which is a nonzero multiple of a basis vector, then the index of that basis vector is taken.

classmethod tuple_to_index(tag, i0=-1, i1=-1)

Convert tuple (tag, i0, i1) to a linear index

Remarks:

The tuple ('D', i0) is accepted as a shorthand for ('A', i0,i0).

A tuple ('E', i0) means a linear index i0, i.e. this method returns i0 on input ('E', i0), for 0 <= i0 < 196884.

If tag is an instance of class MMVector, which is a nonzero multiple of a basis vector, then the linear index corresponding to that basis vector is returned.

Auxiliary functions for the representation of the Monster group

mmgroup.characteristics(): Return list of all characteristics p supported

mmgroup.MMV(p)

Return an object corresponding to the space \(\rho_p\)

Here characteristic p is as in the constructor of class MM. Thus the sequence

>>> V = MMV(p)  
>>> v = V(tag, i0, i1)

returns the same vector in \(\rho_p\) as the statement MMVector(p, tag, i0, i1).

Function characteristics in module mmgroup returns the list of legal values for the characteristic p.

Technically, MMV(p) is the partial application of the constructor of class MMVector to the number p.

mmgroup.mmv_scalprod(v1, v2)

Return scalar product of two vectors

The function returns the scalar product of the vectors \(v_1\) and \(v_2\). These two vectors must be instances of class MMVector; and they must be vectors in the same representation \(\rho_p\).

mmgroup.order_vector()

Return the precomputed order vector

The function returns the precomputed order vector \(v_1\) (which is an element of the representation \(\rho_{15}\) of the monster) as an instance of class MMVector.

The properties required for such a vector \(v_1\) are defined in [Sey22].

Long-term stable storage of vectors of the representation

The representations \(\rho_p\) of the Monster are considered as auxiliary tools for computing in the Monster. We do not guarantee the interoperability of vectors in these representations between different versions of the mmgroup package. The internal representation of such vectors is likely to change in the near future. A user with a serious need for such interoperability can consult the author for advice.

The subgroup \(G_{x0}\) of the Monster and the Clifford group

The section describes the fast computation in a certain subgroup \(G_{x0}\) of structure \(2^{1+24}.Co_1\) of the Monster \(\mathbb{M}\) in detail. A person who simply wants do do calculations in the Monster group need not read this section.

Introduction

In Conway’s construction [Con85] the Monster \(\mathbb{M}\) has a subgroup \(G_{x0}\) of structure \(2^{1+24}_+.\mbox{Co}_1\). There \(G_{x0}\) is constructed as a diagonal product of the two groups \(\mbox{Co}_0\) of structure \(2.\mbox{Co}_1\) and \(G(4096_x)\). \(G(4096_x)\) is also of structure \(2^{1+24}_+.\mbox{Co}_1\) but not isomorphic to \(G_{x0}\). Here \(2^{1+24}_+\) means an extraspecial group of plus type. \(\mbox{Co}_0\), and \(\mbox{Co}_1\) are the automorphism groups of the \(24\)-dimensional Leech lattice and of the Leech lattice modulo \(2\), see e.g. [CCN+85] or [CS99] for background.

Computation in \(\mbox{Co}_0\) is easy since that group has a \(24\)-dimensional rational representation. The smallest real representation of the group \(G(4096_x)\) has dimension \(4096\), so naive computation in that representation is rather inefficient.

The group \(G(4096_x)\) is a subgroup of the real Clifford group \(\mathcal{C}_{12}\). The real Clifford group \(\mathcal{C}_{n}\) of structure \(2^{1+2n}_+.\mbox{GO}^+_{2n}(2)\) is defined e.g. in [NRS01]. \(\mathcal{C}_{12}\) is a subgroup of the complex Clifford group \(\mathcal{X}_{n}\) of structure \(\frac{1}{2} ( 2^{1+2n}_+ \times Z_8 ). \mbox{Sp}_{2n}(2)\), which is also defined in [NRS01]. Here a factor \(\frac{1}{2}\) means identification of central subgroups of order \(2\) of the factors of a direct product. \(\mbox{GO}^+_{2n}(2)\) and \(\mbox{Sp}_{2n}(2)\) are the orthogonal subgroup (of \(+\)-type) and the symplectic subgroup of the group \(GL_{2n}(2)\) of invertible \(2n \times 2n\)-matrices with entries in \(\mathbb{F}_2\), as defined in [CCN+85].

Effective computation in the group \(\mathcal{X}_{n}\) has received a lot of attention from the theory of quantum computation, see e.g. [AG04]. In the next section we present efficient algorithms for computing in \(\mathcal{X}_{n}\) and in its \(2^{n}\) dimensional complex representation.

Computation in the Clifford group

In this section we present effective algorithms for computing in the complex Clifford group of structure \(\frac{1}{2} ( 2^{1+2n}_+ \times Z_8 ). \mbox{Sp}_{2n}(2)\) defined in [NRS01]. Here a factor \(\frac{1}{2}\) means identification of central subgroups of order \(2\) of the factors of a direct product as in [CCN+85].

The complex Clifford group \(\mathcal{X}_{n}\) has a unitary complex representation of dimension \(2^n\) which has been studied in the theory of quantum computation, see e.g. [AG04]. For calculations in the monster group it would be sufficient to deal with the subgroup \(\mathcal{C}_{n}\) of \(\mathcal{X}_{n}\) consisting of the real matrices of that representation. However, the extra effort for extending the real to the complex case is marginal, and using our algorithms for the complex Clifford group might be useful in the theory of quantum computation.

Usually, in quantum physics it suffices to calculate in a unitary group up to a scalar multiple of the unit matrix. Therefore we cannot simply cut an paste existing algorithms for calculating in \(\mathcal{X}_{n}\) used in quantum physics. We keep the following exposition independent of the theory of quantum computation, but we do not hide the fact that the main ideas are strongly influenced by that theory.

We present an algorithm that performs matrix multiplication in \(\mathcal{X}_{n}\) in \(O(n)^3\) bit operations. Therefore we store an element of \(\mathcal{X}_{n}\) in \(O(n)^2\) bits. In case \(n=12\) this is considerably more efficient than dealing with complex \(4096 \times 4096\) matrices.

We will introduce certain complex-valued functions defined on a Boolean vector space \(\mathbb{F}_2^n\) which we will call quadratic mappings. Such a function has a natural interpretation as a vector in \(\mathbb{C}^{2^n}\). It will turn out that quadratic mappings are closed under tensor products and under tensor contraction. Since matrix multiplication is just a special case of tensor contraction, we may consider quadratic mappings on \(\mathbb{F}_2^n \times \mathbb{F}_2^n\) as a monoid of \(2^n \times 2^n\) matrices closed under matrix multiplication. It turns out that the unitary matrices in this monoid are just a representation of the Clifford group \(\mathcal{X}_{n}\).

Quadratic mappings

Let \(V = \mathbb{F}_2^n\) be a Boolean vector space and \(\mathbb{T}\) be the unit circle in the set \(\mathbb{C}\) of the complex numbers. Then \(\mathbb{F}_2^n\) is an additive and \(\mathbb{T}\) is a multiplicative Abelian group. For any mapping \(f: V \rightarrow \mathbb{T}\) define the mapping \(\Delta f: V \times V \rightarrow \mathbb{T}\) by

\[\Delta f(x,y) = f(x+y) \cdot f(x)^{-1} \cdot f(y)^{-1} \cdot f(0) .\]

A mapping \(g: V \rightarrow \mathbb{T}\) is bilinear if

\[\begin{split}g(x_1 + x_2, x_3) = g(x_1, x_3) \cdot g(x_2, x_3) , \\ g(x_1, x_2 + x_3) = g(x_1, x_3) \cdot g(x_1, x_3) .\end{split}\]

Then we obviously have \(g(x_1,x_2) = \pm 1\) and \(g(0,x_2) = g(x_1,0) = 1\). Thus there is a unique symmetric bilinear form \(\beta(g): V \times V \rightarrow \mathbb{F}_2\) with \(g(x_1, x_2) = (-1)^{\beta(g)(x_1, x_2)}\). A function \(q: V \rightarrow \mathbb{T}\) is called quadratic if \(q(0) = 1\) and \(\Delta q\) is bilinear. For a quadratic function \(q\) all functional values of \(q\) are fourth roots of unity. We write \(\beta(q)\) for \(\beta(\Delta q)\). Put

\[R_8 = \{ 2^{e/2} \cdot w \mid e \in \mathbb{Z}, w \in \mathbb{C}, w^8 = 1\} \cup \{0\} \; .\]

Let \(e \in R_8\), let \(q: \mathbb{F}_2^m \rightarrow \mathbb{T}\) be a quadratic function, and let \(a: \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n\) be an affine mapping. Then we define a function \(f = f(e, a, q): \mathbb{F}_2^n \rightarrow \mathbb{C}\) by

(1)\[f(e,a,q)(x) = e \cdot \sum_{\{y \in \mathbb{F}_2^m \mid a(y) = x\}} q(y) .\]

We call a function \(f(e,a,q)\) satisfying (1) a quadratic mapping. We call the triple \((e, a, q)\) a representation of the quadratic mapping \(f(e, a, q)\). Occasionally we also consider quadratic mappings \(f(e, a, q)\) where \(q\) is a scalar multiple of a quadratic function with \(q(0) \in R_8\). We sometimes abbreviate \(f(e, a, q)(x)\) to \(f(x)\) if the meaning of \(e, a, q\) is clear from the context.

The following lemma is a direct consequence of the definition of a quadratic mapping.

Lemma 1:

Let \(g, g_1: V = \mathbb{F}_2^n \rightarrow \mathbb{C}\) be quadratic mappings. Then

For any affine mapping \(a : \mathbb{F}_2^{n'} \rightarrow \mathbb{F}_2^{n}\) the composition \(g \circ a\) given by \(x \mapsto g(a(x))\) is a quadratic mapping on \(\mathbb{F}_2^{n'}\).

Hence the definition of a quadratic mapping on the affine space \(V\) is invariant to translations and to basis transformations of \(V\).

The product \(g \cdot g_1\) of the functions \(g\) and \(g_1\) is a quadratic mapping on \(V\).

For any any affine subspace \(W\) of \(V\) restriction of \(g\) to \(W\), and also characteristic function \(\chi_W : V \rightarrow V\) of the subspace \(W\) is a quadratic mapping.

For any linear subspace \(W\) of \(V\) the function \(g^{(W)} : V/W \rightarrow \mathbb{C}\) given by \(x \mapsto \sum_{y \in W} g(x+y)\) is a quadratic mapping.

A function \(f: \mathbb{F}_2 \rightarrow \mathbb{C}\) has a natural interpretation as a vector in \(\mathbb{C}^2\). Similarly, a function \(g: \mathbb{F}_2^n \rightarrow \mathbb{C}\) has a natural interpretation as a tensor in the tensor product \((\mathbb{C}^2)^{\otimes n}\). If \(\mathbb{C}^2\) has basis \((b_0, b_1)\) then the tensor corresponding to \(g\) has coordinate \(g(i_1,\ldots,i_n)\) at the basis vector \(b_{i_1} \otimes \ldots \otimes b_{i_n}\) of \((\mathbb{C}^2)^{\otimes n}\). We call \(g\) the coordinate function of the tensor. If \(g\) is a function \(\mathbb{F}_2^n \rightarrow \mathbb{C}\) and \(x_j \in \mathbb{F}_2^{n_j}\) holds with \(\sum_{j=1}^k n_j = n\) then we put \(g(x_1,\ldots,x_k)\) = \(g(x)\), where \(x\) is the concatenation of the bit vectors \(x_1, \ldots, x_k\).

A vector (or a tensor) in a space over \(\mathbb{F}_2^n\) is called a quadratic state vector (or a quadratic state tensor) if its coordinate function is a quadratic mapping. Using Lemma 1 we can easily show that tensor products and tensor contractions of quadratic state vectors are quadratic state vectors. As we shall see later, they can easily be computed in practice. A matrix is a special kind of a tensor, and matrix multiplication is a special case of the contraction of a tensor product. Thus the matrix product of two quadratic state matrices is also a quadratic state matrix.

For any affine mapping \(a: \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n\) there is a unique linear mapping \(l(a)\) that differs from \(a\) by the constant \(a(0)\). We write \(\ker a\) for \(\ker l(a)\). We call a representation \((e, a, q)\) of a quadratic mapping injective if \(\ker a = 0\). We have:

Lemma 2:

Every quadratic mapping has an injective representation.

Proof

Let \(e \in R_8, a : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n\), and \(q\) a quadratic function on \(\mathbb{F}_2^m\) such that \(g = f(e, a, q)\) and \(m\) is minimal. Assume \(\ker a \neq 0\). Then we construct a tuple \((e', a', q'\)) with \(g = f(e', a', q')\), such that the domain of \(a'\) and of \(q'\) is a proper affine subspace of the domain of \(a\).

Let \(v \in \ker A \setminus \{0\}\) and \(W\) be a subspace of \(\mathbb{F}_2^m\) with \(\left<v \right> \oplus W = \mathbb{F}_2^m\). Then for \(w \in W\) we have \(q(w+v) = q(w) \cdot (-1)^{h(w)} \cdot r\), with \(h\) a linear form on \(W\) given by \(h(w) = \beta(q)(v, w)\) and \(r = q(v)/q(0)\) a fourth root of unity. Since \(v \in \ker A\), we have

\[f(e,a,q)(x) = e \cdot \sum_{\{y \in W \mid a(y) = x\}} q(y) + q(y + v) = e \cdot \sum_{\{y \in W \mid a(y) = x\}} q(y) t(h(y)) \; ,\]

where \(t(z) = 1 + r \cdot (-1)^z\) for \(z \in \mathbb{F}_2\). Let \(W'\) be the support of \(t \circ h\), i.e. \(W' = \{y \in W \mid t(h(y)) \neq 0\}\). In case \(W' = \emptyset\) we have \(f(e,a,q) = 0\). Otherwise it suffices to show that \(W'\) is an affine subspace of \(W\), and that the restriction of \(t \circ h\) to \(W'\) is a quadratic function up to a scalar multiple in \(R_8\).

Since \(r\) is a fourth root of unity, \(t(0)\) and \(t(1)\) are in \(R_8\). If \(h\) is zero then \(t \circ h\) is a constant function on \(W\).

If \(r\) is an imaginary fourth root of unity then \(t(0) \neq 0\) and \(t(1)/t(0) = \pm \sqrt{-1}\). Thus \(t\) is a quadratic function on \(\mathbb{F}_2\) up to the factor \(t(0)\). Since \(h\) is linear, \(t \circ h\) is also a quadratic function on \(W\).

If \(r = \pm 1, h \neq 0\), then the function \(t \circ h\) is constant on \(W'\), and we have \(W' = \ker h\) if \(r = 1\) and \(W' = W \setminus \ker h\) if \(r = -1\).

q.e.d.

One of the basic challenges in this section is the effective computation of an injective representation of a quadratic mapping from an arbitrary representation of that mapping. The proof of Lemma 2 suggests that this job can be done by using standard methods of linear algebra, mainly over \(\mathbb{F}_2\).

The complex Clifford group \(\mathcal{X}_n\) is a group which is defined in [AG04] and [NRS01]. It has a unitary representation in \((\mathbb{C}^2)^{\otimes n}\).

Lemma 3

The unitary complex quadratic state matrices representing endomorphisms of the space \(\mathbb{C}^{2^n}\) make up a representation of the complex Clifford group \(\mathcal{X}_n\) .

Sketch Proof

It is easy to see that all generators of \(\mathcal{X}_n\) in [NRS01] are unitary complex quadratic state matrices. The group \(\mathcal{X}'_n\) of such matrices is closed under multiplication. It is obviously closed under computing the inverse, which is the conjugate transpose for a unitary matrix. Thus \(\mathcal{X}_n\) is a subgroup of \(\mathcal{X}'_n\) . By Lemma 3 the group \(\mathcal{X}'_n\) is finite. By Theorem 6.5 in [NRS01] all finite supergroups of \(\mathcal{X}_n\) in the unitary group are generated by \(\mathcal{X}_n\) and a scalar multiple of the unit matrix by a root of unity. Comparing the scalar multiples of the unit matrix in \(\mathcal{X}_n\) and \(\mathcal{X}'_n\) yields \(\mathcal{X}_n\) = \(\mathcal{X}'_n\).

q.e.d.

Background from the theory of quantum computing

In the theory of quantum computation a state vector representing the state of \(n\) qubits can be written as a vector in \((\mathbb{C}^2)^{\otimes n}\), where the \(2^n\) basis vectors of that space are labelled by the elements of \(\mathbb{F}_2^n\). Here the \(n\) qubits correspond to the \(n\) factors \(\mathbb{F}_2\) of \(\mathbb{F}_2^n\). In [AG04] the unit vectors which are also quadratic state vectors are called stabilizer states. By Lemma 2 the product of a stabilizer state with a unitary quadratic state matrix is a stabilizer state. Thus Lemma 3 implies that the Clifford group \(\mathcal{X}_n\) stabilizes the stabilizer state vectors. In the theory of quantum computation this fact is known as the Gottesman-Knill theorem.

In [AG04] there is a fast algorithm for calculating in the Clifford group \(\mathcal{X}_n\). As usual in quantum theory, this algorithm ignores scalar factors in the matrix representation of \(\mathcal{X}_n\). This means that we have to create our own algorithm for computing in \(\mathcal{X}_n\).

Implementation of quadratic mappings

Let \(g = f(e, a, q): \mathbb{F}_2^n \rightarrow \mathbb{C}\) with \(e \in R_8\), \(a : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n\) an affine mapping, and \(q: \mathbb{F}_2^m \rightarrow \mathbb{T}\). We implement the quadratic mapping \(g\) as a triple \((e, A, Q)\).

Here \(A\) is an \((m + 1) \times n\) bit matrix representing \(a\), and \(Q\) is a symmetric \((m + 1) \times (m + 1)\) bit matrix representing \(q\). All vector and matrix indices start with \(0\) as usual in the C language. For \(x = (x_1,\ldots, x_m) \in \mathbb{F}_2^m\), \(x_0 = 1\) and bit matrices \(A, Q\) as above we put:

\[a(x) =(x_0,\ldots, x_m) \cdot A \quad , \quad q(x) = \exp \left(\pi \sqrt{-1} /2 \cdot \ \sum_{j,k = 0}^m Q_{j,k} x_j x_k \right) \; .\]

We write \(\sqrt{-1}\) for the imaginary unit, and we use the letters \(i, j, \ldots\) as indices.

The user may consider a quadratic mapping \(g : \mathbb{F}_2^n \rightarrow \mathbb{C}\) as a \(2^n\)-dimensional complex vector, regardless of its representation. In C or python its is convenient to write g[i] for the i-th component of such vector g, and to assume that the index \(i = \sum_{j=0}^{n-1} 2^j \cdot i_j\), \(i_j \in \{0,1\}\) denotes the bit vector \((i_{n-1},...i_0)\) in \(\mathbb{F}_2^n\). In accordance with that convention we label the entries of the \(m+1 \times n\) bit matrix \(A\) as follows:

\[\begin{split}A = \left( \begin{array}{lcl} A_{n-1,0} & \ldots & A_{0,0} \\ \vdots & & \vdots \\ A_{n-1,m} & \ldots & A_{0,m} \end{array} \right) \; .\end{split}\]

Any affine mapping \(a : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n\) can be written as \((x_1,\ldots, x_m) \mapsto (1, x_1,\ldots, x_m) \cdot A\) for a suitable \((m + 1) \times n\) bit matrix \(A\) as above.

Wie label the entries of the symmetric \(m+1 \times m+1\) bit matrix \(Q\) as usual. We stress that all bits \(Q_{j,k}, x_j, x_k\) in sum in the expression for \(q(x)\) must be interpreted as integers equal to \(0\) or \(1\) (modulo \(4\)). But since \(Q\) is a symmetric matrix, it suffices to know the off-diagonal entries of \(Q\) modulo \(2\) if we assume \(Q_{j,k} = Q_{k,j}\). Due to the condition \(q(0) = 1\) we only consider matrices \(Q\) with \(Q_{0,0} = 0\). It is easy to check that we can encode any quadratic function \(q: \mathbb{F}_2^m \rightarrow \mathbb{T}\) as a symmetric \((m + 1) \times (m + 1)\) bit matrix \(Q\) (with \(Q_{0,0} = 0\)) uniquely as above.

Given \(e\) and matrices \(A, Q\) as above, we define \(f(e,A,Q) = f(e,a,q)\), where \(a\) and \(q\) are as in the last equation.

We encode a number \(e \in R_8 \setminus \{0\}\) as an integer \(e'\) such that \(e = \exp(e' \pi \sqrt{-1} / 4) \cdot 2^{\lfloor e'/16 \rfloor / 2}\), with \(\lfloor x \rfloor\) the greatest integer \(\leq x\). We encode the constant quadratic mapping \(0\) as a matrix \(A\) with zero rows.

Changing the representation of a quadratic mapping

The representation \(f(e,A,Q)\) of a quadratic mapping \(q\) is not unique. In this section we define some elementary operations \(T_{i,j}, X_{i, j}\) on a triple \((e, a, Q)\) that to not change the quadratic mapping \(f(e,A,Q)\). In the next section we will use these operations to reduce the representation \(f(e,A,Q)\) to a standard form.

Let \((b_1, \ldots, b_m)\) be the standard basis of \(\mathbb{F}_2^m\). For \(1 \leq i, j \leq m, i \neq j\), define the linear transformation \(T_{i,j} : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^m\) by:

\[T_{i,j}(b_j) = b_j + b_i \, , \, T_{i,j}(b_k) = b_k \quad \mbox{for} \quad k \neq j \; .\]

We also define the (affine) translation \(T_{0,j} : \mathbb{F}_2^m \rightarrow \mathbb{F}_2^m\) by \(T_{0,j}(x) = x + b_j\) for all \(x \in \mathbb{F}_2^m\).

Let \(q'\) be the quadratic function \(q \circ T_{i,j}\) given by \(x \mapsto q(T_{i,j}(x))\). Let \(Q'\) be the symmetric bit matrix representing \(q'\). Then for \(i, j > 0, i \neq j\) we have

\[\begin{split}\begin{array}{rcll} Q'_{i,0} = Q'_{0,i} & = & Q_{i,0} + Q_{j,0} + Q_{i,j} + Q_{i,i} \cdot Q_{j,j} \, , \\ Q'_{i,i} & = & Q'_{i,i} + Q_{j,j} \, , \\ Q'_{i,k} = Q'_{k,i} & = & Q_{i,k} + Q_{j,k} & \mbox{for} \quad k > 0, k\neq i \, , \\ Q'_{k,l} & = & Q_{k,l} & \mbox{for all other pairs} \quad (k, l) \; . \end{array}\end{split}\]

The quadratic function \(q \circ T_{0,j}, \; j > 0\) is equal to \(e \cdot q'\) with \(e = \exp(\pi \sqrt{-1} \cdot(Q_{0,i} + Q_{i,i}/2))\). Here \(q'\) is the quadratic function represented by the bit matrix \(Q'\) with

\[\begin{split}\begin{array}{rcll} Q'_{0,0} & = & 0 \, , \\ Q'_{0,k} = Q'_{k,0} & = & Q_{0,k} + Q_{j,k} & \mbox{for} \quad k > 0 \, , \\ Q'_{k,l} & = & Q_{k,l} & \mbox{for all other pairs} \quad (k, l) \; . \end{array}\end{split}\]

For an affine mapping \(a: \mathbb{F}_2^m \rightarrow \mathbb{F}_2^n\) the mapping \(a' = a \circ T_{i,j}\) with \(i \geq 0, j > 0, j \neq i\) is represented by the matrix \(A'\) given by:

\[\begin{split}\begin{array}{rcll} A'(i, l) & = & A(i, l) + A(j, l) \, , \\ A'(k, l) & = & A(k, l) & \mbox{for} \quad k \neq j \; . \end{array}\end{split}\]

This means that adding row and column \(j >0\) to row and and column \(i \geq 0\) of a matrix \(Q\) representing a quadratic function changes that matrix to a matrix \(Q'\) representing \(Q \circ T_{i,j}\), up to a scalar factor (which is a fourth root of unity) and some corrections required for the entries \(Q'_{0,j}, Q'_{j,0}\) and \(Q'_{0,0}\) of \(Q'\). Similarly, adding row \(j\) to row \(i\) of a matrix \(A\) representing an affine mapping from \(\mathbb{F}_2^m\) to \(\mathbb{F}_2^n\) changes matrix \(A\) to a matrix representing the affine mapping \(A \circ T_{i,j}\).

We obviously have \(f(e, A, Q) = f(e, A \circ T_{i,j}, Q \circ T_{i,j})\). So we may perform a row operation on matrix \(A\), and also a row and a column operation on matrix Q without changing f(e, A, Q), (up to a few corrections in line and column \(0\) of \(Q\)).

If \(f(e, A, Q)\) is in echelon form, (as defined in the following section), then it remains in echelon form after applying an operation \(T_{i,j}, i < j\).

For \(i, j > 0\) let \(X_{i,j}\) be the operation on the triple \((e, A, Q)\) that exchanges rows \(i\) with row \(j\) of \(A\) and \(Q\), and also column \(i\) with column \(j\) of \(Q\). The operation \(X_{i,j}\) does not change \(f(e, A, Q)\).

Reducing the representation of a quadratic mapping

We call a representation \((e, A, Q)\) of a quadratic mapping reduced if the following conditions hold:

\(A\) has no nonzero rows.

Let \(A_1\) be the matrix obtained from \(A\) by prepending the column vector \((1,0,\ldots,0)^\top\). Then the leading coefficient of a row of \(A_1\) is always strictly to the right of the leading coefficient of the row above it.

Each column containing a leading coefficient of a row has zeros in all its other entries.

Here the leading coefficient of a row of matrix \(A\) is the first nonzero entry in that row. We call the representation \((e, A, Q)\) echelonized if only the first two of the three conditions above are satisfied.

Obviously, a reduced or echelonized representation \((e, A, Q)\) also injective. It is easy to see that any quadratic mapping has a unique reduced representation.

In this section we present an algorithm for converting a representation of a quadratic function to a reduced representation. Function qstate12_reduce in module qstate12.c implements this algorithm.

A matrix is in row echelon form if

All rows consisting of only zeros are at the bottom.

The leading coefficient of a nonzero row is always strictly to the right of the leading coefficient of the row above it.

A matrix \(A\) is in reduced row echelon form if it is in echelon form, and each column containing a leading coefficient of a row has zeros in all its other entries. See e.g. https://en.wikipedia.org/wiki/Row_echelon_form .

Let \(T_{i,j}, X_{i,j}\) be as in the last section. In order to reduce a representation \((e, A, Q)\) of a quadratic mapping \(f(e, A, Q)\) we apply several operations \(T_{i,j}, X_{i,j}\) on the components \(e, A, Q\). Neither of these two operations changes \(f(e, A, Q)\).

Given \(A\), let \(A_1 = A_1(A)\) be obtained from \(A\) as above. By applying a sequence of operations \(T_{i,j}\), \(X_{i,j}\) we may convert \(A_1\) to reduced echelon form. If \(A_1\) is in reduced echelon form and contains no zero rows at the bottom then the representation \((e, A, Q)\) is reduced. Otherwise we use the following algorithm repeatedly to remove the zero rows from the bottom of \(A\).

Let \(i\) be the index of the last row of \(A\) and assume \(A_{i,j}=0\) for all \(j\).

Let \(i'\) be the highest index with \(Q_{i,i'}=1\). If such an \(i'\) exists then we add row \(i'\) of \(A\) to all rows \(k\) where \(Q_{k,i}=1\) holds and we adjust \(Q\). Afterwards we have \(Q_{i',i}=1\) for at most one index \(i'\).

Case 1: \(Q_{i',i}=0\) for all \(i'\)

The we may delete the last row of \(A\) , adjust \(Q\), and double \(e\) without changing \(f(e, A, Q)\).

Case 2: \(Q_{0,i}=1\)

Then \(f(e, A, Q)\) is the constant function \(0\).

Case 3. \(Q_{i',i}=1, 0 < i' < i\)

Then we add row \(i\) of \(A\) to all rows \(k \notin \{i,i'\}\) where \(Q_{k,i'}=1\) holds and we adjust \(Q\). Afterwards we have \(Q_{k,i'} = Q_{i',k} = Q_{k,i} = Q_{i,k} = 0\) for all \(k \notin \{i,i'\}\), \(Q_{i,i} = 0\) , and \(Q_{i,i'} = Q_{i',i} = 1\). So we may delete rows \(i\) and \(i'\) of \(A\), adjust \(Q\), and double \(e\) without changing \(f(e, A, Q)\).

Case 4: \(Q_{i,i}=1\)

Then \(f(e, A, Q)\) is not changed if we delete the last row \(i\) of \(A\), adjust \(Q\), and multiply \(e\) by \(1 + \sqrt{-1}\).

Remark

The algorithm sketched in this subsection yields an alternative proof of Lemma 2.

Extending a quadratic mapping

Let \(g: \mathbb{F}_2^{n} \rightarrow \mathbb{C}\) be a quadratic mapping with \(g = f(e,A,Q)\), where \(A\) is an \((m+1) \times n\) and \(Q\) is an \((m+1) \times (m+1)\) bit matrix. Define \(g^{(j)}: \mathbb{F}_2^{n+1}\rightarrow \mathbb{C}\) by

\[g^{(j)}(x_{n},\ldots, x_j, x_{j-1}, \ldots, x_0) = g(x_{n},\ldots, x_{j+1}, x_{j-1}, \ldots, x_0) \; .\]

So \(g^{(j)}\) does not depend on bit \(j\) of \(x\).

Then we have \(g^{(j)} = f(e,A',Q')\) for matrices \(A',Q'\) defined as follows. \(A'\) is obtained from \(A'\) by first appending a zero row at the bottom, and then inserting a zero column to the right of bit position \(j\). Finally, we change the entry at the bottom of the inserted column from \(0\) to \(1\). \(Q'\) is obtained from \(Q'\) by appending a zero row at the bottom and a zero column at the right. Then we have

\[f(e,A',Q')(x_{n},\ldots, x_j, x_{j-1}, \ldots, x_0) = f(e,A,Q)(x_{n},\ldots, x_{j+1}, x_{j-1}, \ldots, x_0) \; ,\]

as required. Function qstate12_extend in module qstate12.c implements the extension of a quadratic mapping.

Products and tensor products of quadratic mappings

Let \(g^{(\lambda)}, \lambda = 1, 2\), be arbitrary complex-valued functions on \(\mathbb{F}_2^{n_\lambda}\). Let \(V_\lambda\) be the complex vector space \((\mathbb{C}^2)^{\otimes {n_\lambda}}\) of dimension \(2^{n_\lambda}\). Then \(g^{(\lambda)}\) has a natural interpretation as a vector in \(V_\lambda\). Here the basis vectors of \(V_\lambda\) are labelled by the elements of \(\mathbb{F}_2^{n_\lambda}\). Any function \(h:\mathbb{F}_2^{n_1 + n_2} \rightarrow \mathbb{C}\) can be considered as tensor in the space \(V_1 \otimes V_2\). Then the coordinate of that tensor with respect to the basis vector labeled by \(b_1 \otimes b_2\) , \(b_\lambda \in \mathbb{F}_2^{n_\lambda}\), is equal to \(h(b_1, b_2)\).

For \(\lambda = 1, 2\) let \(g^{(\lambda)} : \mathbb{F}_2^{n_\lambda} \rightarrow \mathbb{C}\) be as above. For \(c \leq j \leq \min(n_1, n_2)\) we define a mapping \((g^{(1)} \odot g^{(2)})_{j,c} : \mathbb{F}_2^{n_1+n_2-j-c} \rightarrow \mathbb{C}\) by

\[\left(g^{(1)} \odot g^{(2)}\right)_{j,c} \;(x', x_1, x_2) = \sum_{x \in \mathbb{F}_2^c} g^{(1)}(x, x', x_1) \cdot g^{(2)}(x, x', x_2) \; ,\]

where \(x' \in \mathbb{F}_2^{j-c}, \; x_\lambda \in \mathbb{F}_2^{n_\lambda-j}\). We abbreviate \((g^{(1)} \odot g^{(2)})_{j,0}\) to \((g^{(1)} \odot g^{(2)})_{0}\).

If \(g^{(1)}\) and \(g^{(2)}\) are quadratic mappings then \((g^{(1)} \odot g^{(2)})_n\) is a quadratic mapping by Lemma 1. Considering the corresponding quadratic state vectors we see that \((g^{(1)} \odot g^{(2)})_0\) is just the tensor product \(g^{(1)} \otimes g^{(2)}\) of \(g^{(1)}\) and \(g^{(2)}\).

The functions \(g^{(\lambda)}, \lambda = 1, 2\) defined above may also be considered as tensors in the spaces \(V_0 \otimes V_\lambda\) with \(V_0 = (\mathbb{C}^2)^{ \otimes j}\), \(V_\lambda = (\mathbb{C}^2)^{ \otimes n_\lambda - j}\). Then \(g^{(1)} \otimes g^{(2)} \in V_0 \otimes V_1 \otimes V_0 \otimes V_2\). We assume that \(V_0\) is equal to it dual space via the standard Euclidean scalar product. Then we obtain the contraction of \(g^{(1)} \otimes g^{(2)}\) over the two copies of \(V_0\) as \((g^{(1)} \otimes g^{(2)})_{j,j}\). The result has to be interpreted as a tensor in the space \(V_1 \otimes V_2\).

The tensors \(g^{(\lambda)}\) in the space \(V_0 \otimes V^\lambda\) given above can also be considered as \(2^{j} \times 2^{k_\lambda}\) matrices \(M_\lambda\), with \(k_\lambda = n_\lambda - j\). Then the contraction \((g^{(1)} \otimes g^{(2)})_{j,j}\) given above corresponds to the matrix product \(M_1^\top \cdot M_2\), which is a \(k_1 \times k_2\) matrix.

In the next two sections we present an algorithm for computing \((g^{(1)} \odot g^{(2)})_{j,c}\) for quadratic mappings \(g^{(1)}, g^{(2)}\). This yields an algorithm for tensor contraction and also for matrix multiplication of quadratic state matrices. Note that the transposition of a quadratic state matrix \(M\) is a rather simple operation that can be achieved by exchanging columns in the \(A\) part of a representation \((e, A, Q)\) of \(M\). The functions qstate12_product and qstate12_matmul in module qmatrix12.c implement the operation \((. \odot .)_{j,c}\) and the matrix multiplication.

The operator \((. \odot .)_{j,c}\) can be implemented in python with the numpy package. Let c1 and c2 be one-dimensional complex numpy arrays of length \(2^{n_1}\) and \(2^{n_2}\) corresponding to the vectors \(g^{(1)}\) and \(g^{(2)}\), respectively. Then a numpy array c3 corresponding to the vector \((g^{(1)} \otimes g^{(2)})_{j,c}\) can be computed as follows:

import numpy as np
c1a = c1.reshape((2**c, 2**(j-c), -1))
c2a = c2.reshape((2**c, 2**(j-c), -1))
c3 = np.einsum("cjk,cjl->jkl", c1a, c2a)
c3 = c3.reshape((-1,))

Without going into details, we remark that in the graphical ZX-calculus (which is used for describing linear maps between qubits) is an appropriate setup for ‘explaining’ the operation \((. \odot .)_{j,c}\), see e.g. https://en.wikipedia.org/wiki/ZX-calculus .

An algorithm for multiplying quadratic mappings

In this section we present an effective algorithm for computing the product \(g^{(1)} \cdot g^{(2)}\) of two quadratic mappings \(g^{(1)}, g^{(2)}: \mathbb{F}_2^n \rightarrow \mathbb{C}\). Such an algorithm is a key ingredient for implementing the operator \((.\odot.)_{j,c}\). For \(\lambda = 1,2\) let \((e^{(\lambda)}, A^{(\lambda)}, Q^{(\lambda)})\) be a reduced representation of \(g^{(\lambda)}\).

We will show that for any \(j \leq n\) there are quadratic mappings \(g^{(\lambda,j)} = f\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)} \big)\) with \(g^{(1,j)} \cdot g^{(2,j)}\) = \(g^{(1)} \cdot g^{(2)}\), where the first \(j\) columns of \(A^{(1,j)}\) and \(A^{(2,j)}\) are equal, and both, \(A^{(1,j)}\) and \(A^{(2,j)}\), are in reduced echelon form. We put \((e^{(\lambda,0 )}, A^{(\lambda, 0)}, Q^{(\lambda, 0)})\) = \((e^{(\lambda)}, A^{(\lambda)}, Q^{(\lambda)})\).

Assume that \(e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}\) satisfy the conditions given above. Then we can compute \(\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big)\) from \(\big(e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}\big)\) as follows:

Case 1: Both, \(A^{(1,j-1)}\) and \(A^{(2,j-1)}\), have a row with leading coefficient in column \(j\).

Since \(A^{(1,j-1)}\) and \(A^{(2,j-1)}\) are in reduced echelon form and the first \(j-1\) columns of these two matrices are equal, we conclude that the first \(j\) columns of \(A^{(1,j-1)}\) and \(A^{(2,j-1)}\) are equal.

So we may put \(\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big) = \big( e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}\big)\) for \(\lambda = 1,2\).

Case 2: Only \(A^{(1,j-1)}\) has a row with leading coefficient in column \(j\).

Assume that this row of \(A^{(1,j-1)}\) has index \(i\). We add row \(i\) to all rows \(k\) of \(A^{(1,j-1)}\) where \(A^{(1,j-1)}_{k,j} \neq A^{(2,j-1)}_{k,j}\). Therefore we apply the operation \(T_{i,k}\) defined in section Changing the representation of a quadratic mapping. So we obtain a representation \(f\big(e^{(1,j-1)'}, A^{(1,j-1)'}, Q^{(1,j-1)'}\big)\) of \(g^{(1,j-1)}\), where the first \(j\) columns of \(A^{(1,j-1)'}\) and \(A^{(2,j-1)}\) are equal, except for the coefficient in row \(i\), column \(j\).

We obtain \(A^{(1,j)}\) from \(A^{(1,j-1)'}\) by deleting row \(i\) of \(A^{(1,j-1)'}\), and \(Q^{(1,j)}\) from \(Q^{(1,j-1)'}\) by deleting row and column \(i\). We put \(e^{(1,j)} = e^{(1,j-1)'}\). We put \(\left(e^{(2,j)},A^{(2,j)},Q^{(2,j)}\right)\) = \(\left(e^{(2,j-1)},A^{(2,j-1)},Q^{(2,j-1)}\right)\).

By construction, matrix \(A^{(1,j)}\) is in reduced echelon from and the first \(j\) columns of \(A^{(1,j)}\) and \(A^{(2,j)}\) are equal.

It remains to show that deleting row \(i\) of matrix \(A^{(1,j-1)'}\) does not change \(g^{(1)} \cdot g^{(2)}\).

Let \(D^{(\lambda)}\) be the submatrix of \(A^{(\lambda,j-1)'}\) that consists of the first \(j\) columns of \(A^{(1,j-1)'}\). For computing \(g^{(1)} \cdot g^{(2)}\) we only have to consider rows of matrix \(D^{(1)}\) that are linear combinations of rows of matrix \(D^{(2)}\), excluding row \(0\) of both matrices. By construction, \(D^{(1)}\) and \(D^{(2)}\) are in reduced echelon form, row \(i\) of \(D^{(1)}\) has its leading coefficient in column \(j\), and in \(D^{(2)}\) there is no row with leading coefficient in column \(j\). Thus row \(i\) of \(D^{(1)}\) is not a linear combination of the rows of \(D^{(2)}\), ignoring row \(0\) of \(D^{(2)}\).

Case 3: Only \(A^{(2,j-1)}\) has a row with leading coefficient in column \(j\).

This case is symmetric to case 2, exchanging the role of \(A^{(1,j-1)}\) and \(A^{(2,j-1)}\).

Case 4: Neither \(A^{(1,j-1)}\) nor \(A^{(2,j-1)}\) has a row with leading coefficient in column \(j\).

Case 4.1: Columns \(j\) of \(A^{(1,j-1)}\) and \(A^{(2,j-1)}\) are equal.

Then we may proceed as in case 1.

Case 4.2: Column \(j\) of \(A^{(1,j-1)}\) and \(A^{(2,j-1)}\) are equal except in row \(0\).

Assume that \(x^{(1)}\) is in the support of \(g^{(1,j-1)}\), \(x^{(2)}\) is in the support of \(g^{(2,j-1)}\), and that the leftmost \(j-1\) bits of \(x^{(1)}\) and \(x^{(2)}\) are equal. Then from the properties of \(A^{(1,j-1)}\) and \(A^{(2,j-1)}\) we conclude that \(x^{(1)}\) and \(x^{(2)}\) must differ in the bit at position \(j\). Thus \(g^{(1,j-1)} \cdot g^{(2,j-1)}\) is the constant function \(0\), and we may put \(e^{(1,j)} = e^{(2,j)} = 0\).

Case 4.3: There is an \(i>0\) with \(A^{(1,j-1)}_{i,j} \neq A^{(2,j-1)}_{i,j}\).

Let \(i\) be the highest row index such that \(A^{(1,j-1)}_{i,j} \neq A^{(2,j-1)}_{i,j}\) holds.

For \(\lambda = 1,2\) we add row \(i\) to all rows \(k\) of \(A^{(\lambda,j-1)}\) where \(A^{(1,j-1)}_{k,j} \neq A^{(2,j-1)}_{k,j}\) by applying operations \(T_{i,k}\).

So we obtain a representation \(f\big(e^{(1,j-1)'}, A^{(1,j-1)'}, Q^{(1,j-1)'}\big)\) of \(g^{(1,j-1)}\), where the first \(j\) columns of \(A^{(1,j-1)'}\) and \(A^{(2,j-1)}\) are equal, except for the coefficient in row \(i\), column \(j\).

For \(j = 1, 2\) we obtain \(A^{(\lambda,j)}\) from \(A^{(\lambda,j-1)'}\) by deleting row \(i\) of \(A^{(\lambda,j-1)'}\). We obtain \(Q^{(\lambda,j)}\) from \(Q^{(\lambda,j-1)'}\) by deleting row and column \(i\). We put \(e^{(\lambda,j)} = e^{(\lambda,j-1)'}\).

A similar argument as in case 2 shows that matrices \(A^{(1,j)}\) and \(A^{(2,j)}\) are as required and that deleting row \(i\) from \(A^{(1,j-1')}\) and \(A^{(2,j-1')}\) does not change \(g^{(1)} \cdot g^{(2)}\).

Now we may compute the product of \(g^{(1)}\) and \(g^{(2)}\) as follows:

\[g^{(1)} \cdot g^{(2)} = g^{(1,n)} \cdot g^{(2,n)} = f\big( e^{(1,n)} \cdot e^{(2,n)}, A^{(1,n)}, Q^{(1,n)} \odot Q^{(2,n)} \big) \; .\]

If the symmetric \((m+1) \times (m+1)\) bit matrices \(Q^{(\lambda)}, \lambda = 1,2\), represent the quadratic functions \(q^{(\lambda)} : \mathbb{F}_2^m \rightarrow\mathbb{T}\), then we define \(Q^{(1)} \odot Q^{(2)}\) as the symmetric \((m+1) \times (m+1)\) bit matrix representing the quadratic function \(q^{(1)} \cdot q^{(2)}\). The entries \(Q^{(1 \odot 2)}_{i,j}\) of \(Q^{(1)} \odot Q^{(2)}\) can be computed as follows:

\[\begin{split}\begin{array}{ll} Q^{(1 \odot 2)}_{i,j} = Q^{(1)}_{i,j} + Q^{(2)}_{i,j} & \quad \mbox{for} \quad i, j > 0 \; , \\ Q^{(1 \odot 2)}_{i,0} = Q^{(1 \odot 2)}_{0,i} = Q^{(1)}_{0,i} + Q^{(2)}_{0,i} + Q^{(1)}_{i,i} \cdot Q^{(2)}_{i,i} & \quad \mbox{for} \quad i > 0 \; , \\ Q^{(1 \odot 2)}_{0,0} = 0 \; , \end{array}\end{split}\]

The corrections in row and column \(0\) of \(Q^{(1 \odot 2)}\) are necessary, since the diagonal entries of \(Q^{(1)}`and :math:`Q^{(2)}\) are to be interpreted modulo \(4\).

So our algorithm allows us to multiply quadratic mappings effectively.

Remark

In certain cases we have to compute \(\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big)\) from \(\big(e^{(\lambda,j-1)}, A^{(\lambda,j-1)}, Q^{(\lambda,j-1)}\big)\); and we have the additional information that e.g. the factor \(g_1\) of the product \(g_1 \cdot g_2\) is a quadratic mapping that does not depend on qubit \(i\). Then the part \(A^{(1,j-1)}\) of the representation of \(g^{(1,j-1)}\) always has a row \(i\) such that \(A^{(1,j-1)}_{i,j}\) is the only nonzero entry in row \(i\) and in column \(j\) of \(A^{(1,j-1)}\). Furthermore, row \(i\) and column \(j\) of \(Q^{(1,j-1)}\) are zero in that case. Thus only cases 1 and 2 can occur in the above computation, and adding row \(i\) of \(A^{(1,j-1)}\) to any other row in that matrix affects column \(j\) of \(A^{(1,j-1)}\) only, and does not affect \(Q^{(1,j-1)}\). In our implementation we make use of this simplification wherever appropriate.

Computing tensor and matrix products

In this section we explain how to compute the operator \((. \odot ,)_{j,c}\). For \(\lambda = 1,2\) let \(g^{(\lambda)} : \mathbb{F}_2^{n_\lambda}\) be quadratic mappings and \(0 \leq c \leq j \leq \min(n_1, n_2)\). We first show how to compute a representation of \((g^{(1)} \odot g^{(2)})_{j}\) from the representations of \(g^{(1)}\) and \(g^{(2)}\).

For actually computing \((g^{(1)} \odot g^{(2)})_j\) we may extend the mapping \(g^{(1)}: \mathbb{F}_2^{j} \times \mathbb{F}_2^{n_1-j} \rightarrow \mathbb{C}\) to a mapping \(g^{(1')}: \mathbb{F}_2^{j} \times \mathbb{F}_2^{n_1-j} \times \mathbb{F}_2^{n_2-j} \rightarrow \mathbb{C}\), with \(g^{(1')}\) not depending on the last factor \(\mathbb{F}_2^{n_2-j}\), as described in one of the last sections. Similarly, we may extend \(g^{(2)}\) to a mapping \(g^{(2')}: \mathbb{F}_2^{j} \times \mathbb{F}_2^{n_1-j} \times \mathbb{F}_2^{n_2-j} \rightarrow \mathbb{C}\), with \(g^{(2')}\) not depending on the factor \(\mathbb{F}_2^{n_2-j}\) in the middle. Then we simply have \((g^{(1)} \odot g^{(2)})_j = g^{(1')} \cdot g^{(2')}\).

Using the techniques discussed in section Extending a quadratic mapping and in the last section we can compute a representation of \((g^{(1)} \odot g^{(2)})_j\) from representations of \(g^{(1)}\) and \(g^{(2)}\).

It remains to compute \((g^{(1)} \odot g^{(2)})_{j,c}\) from \((g^{(1)} \odot g^{(2)})_{j}\). We have

\[\big(g^{(1)} \odot g^{(2)}\big)_{j,c}(x) = \sum_{y \in \mathbb{F}_2^c} \big(g^{(1)} \odot g^{(2)}\big)_{j}(y, x) \quad \mbox{for} \quad x \in \mathbb{F}_2^{n_1+n_2-j-c} \; .\]

Let \(h : \mathbb{F}_2^n \rightarrow \mathbb{C}\) be a quadratic mapping with representation \((e, A, Q)\), and define \(h_c : \mathbb{F}_2^{n-c} \rightarrow \mathbb{C}\) by \(x \mapsto \sum_{y \in \mathbb{F}_2^{c}} h(y,x)\). Then \(h_c\) is a quadratic mapping with representation \((e, A_c, Q)\), where \(A_c\) is obtained from \(A\) by deleting the leftmost \(c\) columns of \(A\).

So we may easily compute \((g^{(1)} \odot g^{(2)})_{j,c}\) from \((g^{(1)} \odot g^{(2)})_{j}\).

Restricting a quadratic mapping

For any function \(g: \mathbb{F}_2^{n} \rightarrow \mathbb{C}\) define \(\hat{g}^{(j)}: \mathbb{F}_2^{n}\rightarrow \mathbb{C}\) by

\[\begin{split}\hat{g}^{(j)}(x_{n-1},\ldots, x_j, \ldots, x_0) = \left\{ \begin{array}{ll} g(x_{n-1},\ldots, x_j, \ldots, x_0) & \quad \mbox{if} \quad x_j = 0 \\ 0 & \quad \mbox{if} \quad \mbox x_j = 1 \end{array} \right.\end{split}\]

Then \(\hat{g}^{(j)} = g \cdot \hat{\chi}^{(j)}\), where \(\hat{\chi}^{(j)} : \mathbb{F}_2^{n} \rightarrow \mathbb{C}\) is a projection function given by \((x_{n-1},\ldots, x_j, \ldots, x_0) \mapsto 1 - x_j\). It is easy to find a representation of the quadratic mapping \(\hat{\chi}^{(j)}\) so that we can compute a representation of \(\hat{g}^{(j)}\) from a representation of a quadratic mapping \(g\). This computation is implemented in function qstate12_restrict_zero in module qstate12.c.

Function \(\hat{g}^{(j)}\) corresponds to a certain kind of a restriction of the function \(g\). Let \(g\) be a quadratic mapping and \((e, A, Q)\) be a representation of \(\hat{g}^{(j)}\). Let \(V = \mathbb{F}_2^{n-1-j} \times \{0\} \times \mathbb{F}_2^{j}\). Let \(g\mid_V\) be the restriction of \(g\) to \(V\). Then \((e, A_j, Q)\) is a representation of the restriction \(g\mid_V\), where \(A_j\) is the matrix obtained from matrix \(A\) by deleting column \(j\). Function qstate12_restrict in module qstate12.c computes a representation of \(g\mid_V\) from a representation of \(g\).

The restriction of a quadratic mapping discussed in this section can be used for describing a measurement of a stabilizer state on a quantum computer, see e.g. [AG04].

Quadratic state matrices

A quadratic state matrix \(S\) of shape \((n_0, n_1)\) is an element of the tensor product \(V_0 \otimes V_1\) with the basis vectors of \(V_k\) being indexed by \(\mathbb{F}_2^{n_k}, k = 0, 1\), such that the coordinate function of \(S\) is a quadratic mapping. That coordinate function is a function \(\mathbb{F}_2^{n_0} \times \mathbb{F}_2^{n_1} \rightarrow \mathbb{C}\).

Thus \(S\) corresponds to a complex \(2^{n_0} \times 2^{n_1}\) matrix. We may implement \(S\) as a quadratic state vector of \(n_0 + n_1\) qubits, augmented by an information about its shape \((n_0, n_1)\) . We let the \(n_0\) qubits with high indices correspond to the rows of \(S\); and we let the \(n_1\) qubits with low indices correspond to the columns of \(S\).

In python we implement a quadratic state matrix as a instance of class QStateMatrix in module mmgroup.structures.qs_matrix. A matrix of shape \((0,n)\) corresponds to a row vector of dimension \(2^{n}\) and a matrix of shape \((n,0)\) corresponds to a column vector of dimension \(2^{n}\). We have seen above that the unitary quadratic state matrices of shape \((n,n)\) form the Clifford group \(\mathcal{X}_{n}\). We have also discussed fast algorithms for multiplication and inversion of such matrices. So class QStateMatrix supports fast computation in Clifford group \(\mathcal{X}_{n}\) for \(n \leq 12\), which is sufficient for computing in the subgroup \(2^{1+24}.\mbox{Co}_1\) of the monster group.

On the C level, a quadratic state matrix is implemented as a structure of type qstate12_type as defined in file clifford12.h. E.g. function qstate12_matmul in file qmatrix12.c multiplies two such quadratic state matrices.

For practical calculations with quadratic state matrices it is vital to keep the following correspondences in mind.

Let \(S\) be a \(2^{n_0} \times 2^{n_1}\) quadratic state matrix. We put \(n = {n_0}+ {n_1}\). We implement Let \(S\) as a quadratic state vector \(V = f(e, A, Q)\), where \(A\) is a \(m \times n\) bit matrix and \(Q\) is a symmetric \(m \times m\) bit matrix \(Q\). So entry \(S[i_0, i_1]\) corresponds to entry \(i_0 \cdot 2^{n_1} + i_1\) of that quadratic state vector \(V\) for \(0 \leq i_0 < 2^{n_0}\) and \(0 \leq i_1 < 2^{n_1}\). Also, entry \(i\) of the quadratic state vector \(V\) corresponds to a row vector of \(n\) bits containing the binary representation of \(i\).

We concatenate matrices \(A\) and \(Q\) to a \(m \times (n + m)\) bit matrix \(M\) with \(M[i,j] = A[i,j]\) and \(M[i,j+n] = Q[i,j]\). In C and in python we implement the bit matrix as an array of unsigned 64-bit integers, so that bit \(M[i,j]\) corresponds to bit \(j\) (of valence \(2^j\)) of entry \(i\) of that array.

Displaying quadratic state vectors and matrices

We use the bra-ket formalism to display quadratic state vectors. We display a column unit vector as a ket. E.g. |1011> means the column unit vector labelled by the bit vector \((1,0,1,1)\) in \((\mathbb{C}^2)^{\otimes 4}\). This corresponds to a state where the qubits with indices \(3,2,1,0\) have values \(1,0,1,1\) , respectively. Similarly, we display a row vector as a bra. So e.g. <110| means the row unit vector labelled by \((1,1,0)\). A \(2^4 \times 2^3\) matrix with an entry one in the row labelled by \((1,0,1,1)\) and the column labelled by \((1,1,0)\), and zeros elsewhere, is displayed as |1011><110|.

We also want to display certain linear combinations of such unit vectors or matrices. As we have seen earlier, the coordinate function of such a state vector in \((\mathbb{C}^2)^{\otimes n}\) is a function \(\mathbb{F}_2^n \rightarrow \mathbb{C}\). We only consider state vectors where the support of the coordinate function is an affine subspace of \(\mathbb{F}_2^n\), and where the nonzero coordinates are in the set \(\{\pm 1, \pm \sqrt{-1}\}\), up to a global scalar factor. Furthermore, the nonzero coordinates must be given by a certain quadratic form \(Q\) that we will specify below.

The support of the coordinate function is an affine subspace \(a_0 + V\), where \(a_0 \in \mathbb{F}_2^n\) and \(V\) is a linear subspace of \(\mathbb{F}_2^n\) with a basis, say, \((a_1,\ldots a_m)\). In order to specify the support of the coordinate function, we write \(a_0\) in bra-ket notation as above, and we write coordinates \(a_1,\ldots,a_m\) underneath the coordinate \(a_0\) without any bras or kets. We may give the basis \((a_1,\ldots, a_m)\) in echelon form, omitting leading zeros. We write \(A\) for the with row vectors \((a_0,\ldots,a_m)^\top\).

We write a lower triangular matrix \(Q\) with diagonal entries '.' or 'j' and off-diagonal entries entries '+' or '-' to the left of the coordinate matrix \(A\). Here an entry '-' means \(-1\), 'j' means \(\sqrt{-1}\), and anything else means \(1\). We write \(q_{i,j}\) for the entries of the matrix matrix \(Q\). Then we put:

\[f(A, Q) = \sum_{x = (x_0,\ldots,x_m) \in \{0,1\}^{m+1}, x_0 = 1} \! \! \! Q(x) \cdot \left| \oplus_{k=0}^m x_k \cdot a_k \right> \, , \quad Q(x) = \prod_{i, j = 0}^m q_{i,j}^{x_i \cdot x_j} \, .\]

We use the same notation if the values \(a_i\) are kets or matrices written in the form |ket><bra|. For example:

.   |10><01|
-.    1  10
-+j       1

means \(1 \cdot \left|10\right> \left<01\right| - 1 \cdot \left|11\right> \left<11\right| - \sqrt{-1} \cdot \left|10\right> \left<00\right| + \sqrt{-1} \cdot \left|11\right>\left<10\right|\).

E.g. the coefficient in the third term of that sum is computed as:

\[\begin{split}Q(1,0,1) = \textstyle{ (1, 0, 1) \left( \begin{array}{ccc} . & & \\ - & . & \\ - & + & j \end{array} \right) \left( \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \right) = (-1) \cdot \sqrt{-1} = -\sqrt{-1}} \; .\end{split}\]

It turns out that up to a scalar factor all elements of the complex Clifford group \(\mathcal{X}_{n}\) and all stabilizer states can be displayed in that way. So we can display any element of \(\mathcal{X}_{n}\) and any stabilizer state of \(2n\) qubits on one page for \(n\) up to about \(25\).

Reducing a quadratic state matrix

We define a special reduced matrix representation \((e, A, Q)\) of a quadratic state matrix \(S\) of shape \((n_0, n_1)\) that differs slightly from the reduced representation of a quadratic state vector. That representation satisfies the following conditions:

We require that the representation \((e, A, Q)\) is echelonized (but not necessarily reduced), as described in section Reducing the representation of a quadratic mapping.

Let \(A'\) be the bit matrix obtained from \(A\) by removing the leftmost \(n_0\) columns from \(A\). We require that a permutation of the rows of matrix \(A'\), excluding row \(0\), is in (not necessarily reduced) echelon form.

Note that the first \(n_0\) columns of the bit matrix \(A\) correspond to the \(2^{n_0}\) rows of the complex matrix \(S\); and that the remaining \(n_1\) columns of \(A\) correspond to the \(2^{n_1}\) columns of \(S\).

Let \(K_0\) be the set of the rows of the bit matrix \(A\) such that all bits in the leftmost \(n_0\) columns of that row are zero. Let \(K_1\) be the set of the rows of \(A\) such that all bits in rightmost \(n_1\) columns of that row are zero. We exclude row \(0\) from \(K_0\) and from \(K_1\).

If the bit matrix \(A\) has \(m'\) rows then the bit matrix \(Q\) is a symmetric \(m' \times m'\) bit matrix. Let \(Q'\) be the submatrix of \(Q\) that consists of all rows with index in \(K_1\) and of all columns with index in \(K_0\) .

We require that submatrix \(Q'\) of \(Q\) has at most one nonzero entry in each row and in each column.

Note that \(K_0 \cap K_1 = \emptyset\), since the representation \((e, A, Q)\) is echelonized.

We may obtain a reduced matrix representation \((e, A, Q)\) of a quadratic state matrix \(S\) of shape \((n_0, n_1)\) as follows:

Starting from a reduced representation \((e_0, A_0, Q_0)\) of a quadratic state vector \(S\) we may obtain a representation \((e_1, A_1, Q_1)\) of the matrix \(S\) satisfying condition (2.) by applying a sequence of transformations \(T_{i,j}, i < j\). Then \(A_1\) is also in echelon form. \(T_{i,j}\) is defined in section Implementation of quadratic mappings.

We apply a sequence of transformations \(T_{i,j}, i < j\), with \(i, j \in K_0\) or \(i, j \in K_1\) to \((e_1, A_1, Q_1)\). These transformations preserve the echelon form of \(A_1\) and also property (2.). Since \(K_0 \cap K_1 = \emptyset\), these transformations act as row and column operations on the submatrix \(Q'\) of \(Q\). So we may achieve property (3.) by a sequence of such transformations, thus obtaining a suitable representation \((e, A, Q)\) of \(S\).

Using a reduced matrix representation \((e, A, Q)\) of a quadratic state matrix \(S\) has a variety of advantages.

We can easily compute the rank of \(S\) as follows:

For \((e, A, Q)\) let \(K_0, K_1, Q'\) be defined as above. Let \(K_2\) be the subset \(K_1\) containing all rows of \(A\) such that the corresponding row of bit matrix \(Q'\) is zero. Then the binary logarithm of the rank of \(S\) is equal to the number of rows of matrix \(A\) with are neither in \(K_0\) nor in \(K_2\). Here we have to exclude row \(0\) of \(A\).

We omit the proof of this fact since we do not need it for our purposes.

That representation can be used for decomposing \(S\) into a product \(M_1 \cdot H \cdot M_2\) of quadratic state matrices, where \(M_1, M_2\) are monomial and \(H\) is a Hadamard-like matrix. By a Hadamard-like matrix we mean a tensor product of \(2 \times 2\) unit matrices and matrices \(\left( \begin{smallmatrix}1 & 1 \\ 1 & -1 \end{smallmatrix} \right)\).

If \(S\) has shape \((n,n)\) then such a decomposition reduces the complexity of multiplying \(S\) with an arbitrary complex vector form \(O(4^n)\) to \(O(n \cdot 2^n)\).

Essentially, we have used such a decomposition for multiplying the non-monomial part of generator \(\xi\) of the monster \(\mathbb{M}\) with a vector of our representation of \(\mathbb{M}\). Since this special case is discussed elsewhere, we do not go into details here.

In the next section we will introduce the Pauli group \(\mathcal{P}_{n}\), which is an important normal subgroup of \(\mathcal{X}_{n}\). Using the reduced matrix representation of an element \(S\) of \(\mathcal{X}_{n}\) we can conjugate any element of \(\mathcal{P}_{n}\) with \(S\) in \(O(n^2)\) bit operations.

With quadratic state matrices, a general matrix multiplication in the Clifford group \(\mathcal{X}_{n}\) costs \(O(n^3)\) bit operations.

Function qstate12_reduce_matrix in file qmatrix12.c converts any representation of a quadratic state matrix to a reduced matrix representation. For the sake of efficiency, we relax condition 3 on matrix \(Q'\) as follows. A permutation of the rows of \(Q'\) is in echelon form when the columns of \(Q'\) are reversed.

The Pauli group

The Pauli group \(\mathcal{P}_{n}\) of \(n\) qubits is the normal subgroup of the Clifford group \(\mathcal{X}_{n}\) generated by the not gates, the phase \(\pi\) gates in \(\mathcal{X}_{n}\), and by the scalar multiples of the unit matrix by a fourth root of unity. It has structure \(\frac{1}{2}(2_+^{1+2n} \times Z_4)\), exponent \(4\) and order \(2^{2n+2}\).

We represent an element of \(\mathcal{P}_{n}\) as a product of \(2n+2\) generators. Each generator may have exponent \(0\) or \(1\). The sequence of these exponents are stored as a bit vector as follows:

Bit \(2n+1\) corresponds to multiplication with the scalar \(\sqrt{-1}\).

Bit \(2n\) corresponds to multiplication with the scalar \(-1\).

Bit \(n+i\) with \(0 \leq i < n\) corresponds to a not gate applied to qubit \(i\).

Bit \(i\) with \(0 \leq i < n\) corresponds to a phase \(\pi\) gate applied to qubit \(i\).

Factors are ordered by bit positions, with the most significant bit position occurring first. In the C language we represent bit vectors a integers as usual.

All generators commute and have order \(2\) except for the following cases:

A phase \(\pi\) gate anticommutes with a not gate applied to the same qubit, i.e their commutator is the scalar \(-1\).

Of course, the scalar \(\sqrt{-1}\) squares to the scalar \(-1\).

Functions qstate12_pauli_vector_mul and qstate12_pauli_vector_exp in module qs_matrix.c perform multiplication and exponentiation in the Pauli group \(\mathcal{P}_{n}\).

Given an element \(p\) of the Pauli group and a reduced matrix representation \((e, A, Q)\) of a unitary quadratic state matrix \(S\), we can quickly compute the conjugate \(S \cdot p \cdot S^{-1}\) as follows:

Right multiply \(S\) with \(p\) by applying the appropriate gates to \(S\). This affects row \(0\) of the bit matrix \(A\) and row and column \(0\) of the symmetric bit matrix \(Q\) only.

Restore the original values \(A[0,j]\) for all \(j < n\) and the original values \(Q[0,k] = Q[k,0]\) for all \(k > n\) by applying appropriate transformations \(T_{0,j}\) to the modified representation \((e, A, Q)\). This does not change the value \(S \cdot p\) of the complex matrix computed in the previous step. \(T_{0,j}\) is defined in section Implementation of quadratic mappings.

We may restore the the remaining original values of row and column \(0\) of \(Q\) by applying phase \(\pi\) gates to \(S\). These gate operations correspond to a left multiplication with a element \(p_1\) of the Pauli group.

We may restore the the remaining original values of row \(0\) of \(A\) by applying not gates to \(S\). These gate operations correspond to a left multiplication with a element \(p_2\) of the Pauli group.

Up to a known scalar factor we have obtained an equation \(S = p_2 \cdot p_1 \cdot S \cdot p\), with \(p_1, p_2\) in the Pauli group. With this equation the requested conjugation is an easy computation in the Pauli group.

Function qstate12_pauli_conjugate in module qs_matrix.c performs this conjugation.

This operation can be simplified considerably if we require the product \(S \cdot p \cdot S^{-1}\) up to a scalar factor only. Then the mapping \(p \mapsto S \cdot p \cdot S^{-1}\) is a symplectic linear transformation on the vector space \(\mathcal{P}_{n} / Z(\mathcal{P}_{n})\) of dimension \(2n\) over \(\mathbb{F}_2\). Here \(Z(\mathcal{P}_{n})\) is the centre of \(\mathcal{P}_{n}\). Function qstate12_to_symplectic in module qs_matrix.c computes this transformation as a \(2n \times 2n\) bit matrix acting on \(\mathbb{F}_2^{2n}\) by right multiplication.

This means that the homomorphism of the Clifford group \(\mathcal{C}_{n}\) group of structure \(\frac{1}{2} ( 2^{1+2n}_+ \times Z_8 ). \mbox{Sp}_{2n}(2)\) onto the symplectic group \(\mbox{Sp}_{2n}(2)\) can be computed very fast.

Using these ideas and a suitable representation of the subgroup \(G_{x0}\) of the monster, we can also compute the homomorphism from the group \(G_{x0}\) of structure \(2^{1+2n}_+ . \mbox{Co}_1\) onto its factor group \(\mbox{Co}_1\) very fast. Here the image in \(\mbox{Co}_1\) will be given as a linear operation on the Leech lattice modulo 2.

Applying a gate to a quadratic mapping

In the theory of quantum computing we may apply so-called gates to a quadratic state vector in \((\mathbb{C}^2)^{\otimes n}\). For our purposes a gate is a linear operation on \((\mathbb{C}^2)^{\otimes n} = (\mathbb{C}^2)^{\otimes k} \otimes (\mathbb{C}^2)^{\otimes n-k}\) which may be written as a tensor product of a unitary \(2^k \times 2^k\) matrix G and a \(2^{n-k} \times 2^{n-k}\) identity matrix for a small number \(1 \leq k \leq 2\). Here we may permute the factors \(\mathbb{C}^2\) of \((\mathbb{C}^2)^{\otimes n}\) arbitrarily before the decomposition into a tensor product as above.

We state without proofs how to apply a certain gates to a quadratic mapping. The gates listed below generate the Clifford group. Here a quadratic mapping represents a quadratic state vector as before. A quadratic state matrix of shape \((n_0, n_1)\) is considered as a quadratic mapping \(\mathbb{F}_2^{n_0} \times \mathbb{F}_2^{n_1} \rightarrow \mathbb{C}\).

The not gate

A not gate operating in qubit \(j\) maps a state \(g\) to a state \(g'\) with \(g'(x) = g(x + e_j)\), where \(e_j = (0,\ldots,0,1,0,\ldots,0)\) and the component \(1\) is at position j. A not gate operating in qubit \(j\) is implemented for \(g = f(e,A,Q)\) by flipping the bit \(A_{0,j}\). The C function state12_gate_not implements a not gate.

The controlled not gate

A controlled not gate is a gate that negates a target qubit \(j \neq j'\) controlled by a qubit \(j'\). Such a gate maps a state \(g\) to a state \(g'\) with \(g'(x) = g(x + \langle e_{j'},x \rangle \cdot e_j)\), where \(\langle .,. \rangle\) is the scalar product of bit vectors. Such a gate is implemented for \(g = f(e,A,Q)\) by adding column \(j'\) of \(A\) to column \(j\) of \(A\). The C function state12_gate_ctrl_not implements a controlled not gate.

The phase \(\phi\) gate

Applying a phase \(\phi\) gate to qubit \(j\) of a state \(g= f(e,A,Q)\) changes the state \(g\) to a state \(g'\) with

\[g'(x_{n-1},\ldots,x_j,\ldots,x_{0}) = \exp(\phi x_j \sqrt{-1}) \cdot g(x_{n-1},\ldots,x_j,\ldots,x_{0}) \; .\]

We consider only phases \(\phi\) which are multiples of \(\pi/2\). For an \((m+1) \times n\) matrix \(A\) let \(A_j\) be the \(j\)-th column of matrix \(A\). Let \(A_{-1}\) be the column vector \((1,0,\ldots,0)^\top\) with \(m+1\) entries. Then a phase \(\pi\) gate on qubit \(j\) maps \(f(e,A,Q)\) to

\[f\left( (-1)^{A_{0,j}} \cdot e, A, Q \odot A_{-1} A_j ^\top \odot A_j A_{-1}^\top \right) \; .\]

A phase \(\pi/2\) gate on qubit \(j\) maps \(f(e,A,Q)\) to

\[f\left( \sqrt{-1}^{A_{0,j}} \cdot e, A, Q \odot A_j A_j ^\top \right) \; .\]

Here we consider \(A_j, A_{-1}\) as a \((m+1) \times 1\) matrices, so that the matrix product \(A_j A_{-1}^\top\) is an \((m+1) \times (m+1)\) matrix. Operator \(\odot\) is as in section Multiplication of quadratic mappings.

The C function qstate12_gate_phi implements phase gate.

The controlled phase \(\pi\) gate

Applying a controlled phase \(\pi\) gate to qubits \(j\) and \(j'\) of a state \(g= f(e,A,Q)\) changes the state \(g\) to a state \(g'\) with

\[g'(\ldots,x_j,\ldots,x_{j'},\ldots ) = (-1)^{x_j x_{j'}} \cdot g(\ldots,x_j,\ldots,x_{j'},\ldots) \; .\]

A controlled phase \(\pi\) gate on qubit \(j\) and \(j'\) maps \(f(e,A,Q)\) to

\[f\left( (-1)^{A_{0,j} \cdot A_{0,j'}} \cdot e, A, Q \odot A_j A_{j'}^\top \odot A_{j'} A_j^\top \right) \; .\]

The C function qstate12_gate_ctrl_phi implements controlled phase gate.

The Hadamard gate

A Hadamard gate at qubit \(j\) is a a mapping that changes a quadratic mapping \(g\) to another quadratic mapping \(1/\sqrt{2} \cdot g'\) with

\[\begin{split}g'(\ldots,x_{j+1},x_j,x_{j+1},\ldots) = \\ g(\ldots,x_{j+1},0,x_{j-1},\ldots) + (-1)^{x_j} \cdot g(\ldots,x_{j+1},1,x_{j-1},\ldots) \; .\end{split}\]

We implement the application of a Hadamard gate on qubit \(j\) to a quadratic mapping \(g\) represented as \((e, A, Q)\) as follows.

We append a zero row at \(A\) and also a zero row and a zero column at \(Q\). Let \(i\) be the index of the appended row and column. Then we change \(Q_{i,k}\) and \(Q_{k,i}\) to \(A_{k,j}\), \(A_{k,j}\) to \(0\) for all \(k \neq i\), and \(A_{i,j}\) to \(1\). Let \(A', Q'\) be the modified matrices \(A', Q'\). Then we have \(g' = f(e, A', Q')\).

The C function state12_gate_h implements a Hadamard gate.

Correctness of the implementation of the Hadamard gate

The correctness of that implementation can be seen as follows. W.l.o.g we assume that \(j\) is the last index \(0\). Let \(x = (x_{n-1},\ldots, x_0) \in \mathbb{F}_2^n\), \(y = (y_0,\ldots, y_m) \in \mathbb{F}_2^{m+1}\) with \(y_0 = 1\), and assume \(y \cdot A = x\) for the matrix product \(y \cdot A\). Then

\[(y, b) \cdot A' = (x_{n-1},\ldots,x_1,b) \quad \mbox{for} \quad b \in \mathbb{F}_2 \; .\]

Let \(q, q'\) be the quadratic mappings given by \(Q, Q'\). Then

\[q'(y, b) = (-1)^{b \cdot \langle y, A_0 \rangle} \cdot q(y) = (-1)^{b \cdot x_0} \cdot q(y) \; ,\]

where \(A_0\) is the last column of \(A\). Thus

\[f(e, A',Q')(x_{n-1},\ldots, x_0) = g(x_{n-1},\ldots, x_1, 0) + (-1)^{x_0} \cdot g(x_{n-1},\ldots, x_1, 1) \; .\]

Computing the trace of a quadratic state matrix

We briefly explain the computation of the trace of a quadratic state matrix \(S\) of shape \((n, n)\). Such a matrix is considered as a mapping \(\mathbb{F}_2^{n} \times \mathbb{F}_2^{n} \rightarrow \mathbb{C}\). So there are \(n\) qubits corresponding to the rows and \(n\) qubits corresponding the columns of the matrix.

For \(i = 0, \ldots, n-1\) we apply a control not gate to the \(i\)-th row qubit, controlled by the \(i\)-th column qubit. This moves the diagonal entries of the matrix \(S\) to row \(0\).

Using the techniques described above we may restrict the modified matrix to row 0, and sum up all entries of that row. This leads to a scalar that has the value of the trace of \(S\).

Class `QStateMatrix` modelling a quadratic state matrix

class mmgroup.structures.qs_matrix.QStateMatrix(*args: Any, **kwargs: Any)

This class models a quadratic state matrix

Quadratic state matrices are described in the API reference in section Computation in the Clifford group.

Parameters:

rows (int or and instance of class QStateMatrix) –
- Binary logarithm of the number of rows of the matrix
- or an instance of class QStateMatrix. Then a deep copy of that instance is created.
cols (A nonnegative int, if parameter rows is an int) – Binary logarithm of the number of columns of the matrix
data – The data of the matrix as described below
mode – Evaluated according as described below

Raise:

TypeError if type(data) is not as expected.
ValueError if data cannot be converted to an instance of class QStateMatrix.

In terms of the theory of quantum computing, rows, cols = 0, n creates a column vector or a -ket |v> corresponding to a state of of n qubits, and rows, cols = n, 0 creates a row vector or a -bra <v| corresponding to a linear function on a state of n qubits.

If rows == cols == n and the created 2**n times 2**n matrix is invertible, then the matrix is (a scalar multiple of) an element of the complex Clifford \(\mathcal{X}_{12}\) of n qubits described in [NRS01].

If rows is an instance of this class then a copy of that instance is created.

If rows and cols are integers then data may be:

None (default). Then the zero matrix is created.

A list of integers. Then that list of integers must encode a valid pair (A, Q) of bit matrices that make up a state, as described in Long-term stable storage of vectors of the representation, subsection Quadratic state matrices. In this case parameter mode is evaluated as follows:

1: create matrix Q from lower triangular part

2: create matrix Q from upper triangular part

Anything else: matrix Q must be symmetric.

An integer v. Then one of the values rows and cols must be zero and the unit (row or column) vector with index v is created. Here a row vector is an 1 times 2**cols and a column vector is a 2**rows times 1 matrix.

As in numpy, matrix multiplication of quadratic state matrices is done with the @ operator and elementwise multiplication of such matrices is done with the * operator. A quadratic state matrix may also be multiplied by a scalar. Here the scalar must be zero or of the form:

\[2^{e/2} \cdot w \, , \quad e \in \mathbb{Z}, \; w \in \mathbb{C}, \, w^8 = 1 \; .\]

Divison by such a scalar is legal.

A matrix of type QStateMatrix may be indexed with square brackets as in numpy in order to obtain entries, rows, columns or submatrices. Then a complex numpy array (or a complex number) is returned as in numpy. It is not possible to change the matrix via item assignment. So the easiest way to obtain a complex version of an instance qs of type QStateMatrix is to write qs[:,:].

A row or column index has a natural interpretation as a bit vector. In the theory of quantum computation a bit of such a bit vector corresponds to a qubit. Let qs be a quadratic state matrix of shape (m, n) and

\[x = \sum_{k=0}^{m-1} 2^k x_k, \; y = \sum_{k=0}^{n-1} 2^k y_k, \, x_k, y_k \in \{0, 1 \}.\]

Then qs[x,y] is the entry of matrix qs with row index corresponding to the bit vector \((x_{m-1},\ldots,x_0)\) and column index corresponding to the bit vector \((y_{n-1},\ldots,y_0)\).

Officially, we support matrices with rows, cols <= 12 only. Methods of this class might work for slightly larger matrices. Any attempt to constuct a too large matrix raises ValueError.

property H: Return conjugate transposed matrix as in numpy

property T: Return transposed matrix as in numpy

conjugate()

Compute complex conjugate of the matrix

Returns:: instance of class QStateMatrix.

copy(): Return a deep copy of the matrix

extend(j, nqb, copy=True)

Insert nqb qubits at position j. .

Let qs be the state of shape (n0+n1), and let n = n0 + n1`. We change ``qs to the following state qs' depending on n + nqb qubits:

qs'(x[n-1],...,x[j],y[nqb-1],...,y[0],x[j-1]...,x[0]) = qs(x[n-1],...,x[j],x[j-1]...,x[0]) .

The function returns ket, i.e. a column vector of shape (n + nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

extend_zero(j, nqb, copy=True)

Insert nqb zero qubits at position j.

Let qs be the state of shape (n0+n1), and let n = n0 + n1`. We change ``qs to the following state qs' depending on n + nqb qubits:

qs'(x[n-1],...,x[j],y[nqb-1],...,y[0],x[j-1]...,x[0]) is equal to qs(x[n-1],...,x[j],x[j-1]...,x[0]) if y[0] = ... = y[nqb-1] = 0 and equal to zero otherwise.

The function returns ket, i.e. a column vector of shape (n + nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

gate_ctrl_not(vc, v)

Apply controlled not gates to a state

Change the state qs to a state qs' with qs'(x) = qs(x (+) <vc,x> * v) where '(+)' is the bitwise xor operation, and <.,.> is the scalar product of bit vectors. The result is not reduced. The scalar product of the bit vectors j and jc must be zero. Otherwise the ctrl not operation is not unitary.

Computing qs.gate_ctrl_not(1 << jc, 1 << j), for jc != j, corresponds to applying a controlled not gate to qubit j contolled by qubit jc. This operation is unitary if and only if the scalar product of j and jc is zero.

gate_ctrl_phi(v1, v2)

Apply controlled phase gates to a state

Change the state qs to a state qs' with qs'(x) = qs(x) * (-1)**(<v1,x>*<v2,x>), where <.,.> is the scalar product of bit vectors and '**' denotes exponentiation. The result is reduced if the input is reduced. Computing qs.gate_ctrl_phi(1 << j1, 1 << j2) corresponds to applying a phase pi gate to qubit j2 controlled by qubit j1.

gate_h(v)

Apply Hadamard gates to a state

Apply a Hadamard gate to all qubits j of the state qs (referred by self) with v & (1 << j) == 1. Aplying a Hadamard gate to gate j changes a state qs to a state 1/sqrt(2) * qs', where qs'(..,x[j+1],x_j,x[j-1],..) = qs(..,x[j+1],0,x[j-1],..) + (-1)**(x_j) * qs(..,x[j+1],1,x[j-1],..) . The result is not reduced.

gate_not(v)

Apply not gates to a state

Change the state qs to a state qs' with qs'(x) = qs(x (+) v), where '(+)' is the bitwise xor operation. The result is reduced if the input is reduced. Computing qs.gate_not(1 << j) corresponds to negating qubit j.

gate_phi(v, phi)

Apply phase gate to a state

Change the state qs to a state qs' with qs'(x) = qs(x) * sqrt(-1)**(phi * <v,x>), where <.,.> is the scalar product of bit vectors and '**' denotes exponentiation. The result is reduced if the input is reduced. Computing qs.gate_phi(1 << j, phi) corresponds to applying a phase (phi * pi/2) gate to qubit j.

inv()

Return inverse matrix

Returns an instance of class QStateMatrix. Raise ValueError if matrix is not invertible.

lb_norm2()

Return binary logarithm of squared operator norm.

The operator norm is the largest absolute singular value of the matrix. For a quadratic state matrix this is a power of \(\sqrt{2}\) or zero.

The function returns -1 if the matrix is zero.

lb_rank()

Return binary logarithm of the rank of the matrix

The rank of a nonzero quadratic state matrix is a power of two. The function returns -1 if the matrix is zero.

order(max_order)

Try to find the order of a matrix

If the matrix m has order e for e <= max_order, i.e. m.power(e) is the unit matrix, then e is returned. Otherwise ValueError is raised.

The function might also succeed if e is slighty larger than max_order. It has run time O(max_order**0.5).

pauli_conjugate(v, arg=True)

Conjugate Pauli group elements by the matrix

The method conjugates an element of the Pauli group or a list of such elements with the quadratic matrix and returns the congugated Pauli group element (or the list of conjugated elements). All Pauli group elements are encoded as in method pauli_vector.

If \(M`is the quadratic state matrix given by this object then the Pauli group element :math:`v\) is mapped to \(M v M^{-1}\).

Matrix \(M\) must be in a Clifford group. The function raises ValueError if this is not the case.

In case arg = False the (complex) arguments of the returned Pauli group elements are not computed.

pauli_vector()

Return matrix as a Pauli vector if it is in the Pauli group

We represent an element of the Pauli group \(\mathcal{P}_{n}\) as a product of \(2n+2\) generators. Each generator may have exponent \(0\) or \(1\). The sequence of these exponents are stored as a bit vector as follows:

Bit \(2n+1\) corresponds to multiplication with the scalar \(\sqrt{-1}\).

Bit \(2n\) corresponds to multiplication with the scalar \(-1\).

Bit \(n+i\) with \(0 \leq i < n\) corresponds to a not gate applied to qubit \(i\).

Bit \(i\) with \(0 \leq i < n\) corresponds to a phase \(\pi\) gate applied to qubit \(i\).

Factors are ordered by bit positions, with the most significant bit position occuring first.

The function returns the bit vector corresponding to this object as an integer. It raises ValueError if the matrix iy not in the Pauli group.

power(e)

Return the e-th power of the matrix

For a matrix m the power with exponent e = 2 is m @ m, and the power with e = -1 is the inverse matrix of m.

reshape(new_shape, copy=True)

Reshape matrix to given shape

Parameters:

new_shape (tuple of two integers) – This shape of the reshaped matrix. It must be a pair of integers. A pair (n0, n1) correponds to a complex 2**n0 times 2**n1 matrix.
copy (bool) – A deep copy of the reshaped matrix is returned if copy is True (default). Otherwise the matrix is reshaped in place.

new_shape[0] + new_shape[1] = self.shape[0] + self.shape[0] must hold.

If one of the values new_shape[0], new_shape[1] is -1 then the other value is calculated from the sum self.shape[0] + self.shape[1].

restrict(j, nqb, copy=True)

This is method restrict_zero with deletion.

Let qs be the state of shape (n0+n1), and let n = n0 + n1`. We change ``qs to the following state qs' depending on n - nqv qubits:

qs'(x[n'-1],...,x[0]) is equal to qs(x[n'-1],...,x[j],0,...,0,x[-1],...,x[0]).

The function returns ket, i.e. a column vector of shape (n - nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

restrict_zero(j, nqb, copy=True)

Restrict nqb qubits starting at postion j to 0.

Let qs be the state of shape (n0+n1), and let n = n0 + n1`. We change ``qs to the following state qs' depending on n qubits:

qs'(x[n-1],...,x[0]) is equal to qs(x[n-1],...,x[0]) if x[j] = ... = x[j+nqb-1] = 0 and equal to zero otherwise. We do not change the shape of qs.

The output is reduced if the input is reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

rot_bits(rot, nrot, start=0)

Rotate qubit indices of the state matrix qs in place

If the state matrix qs has shape (0,n) or (n,0) we rotate the qubits of qs in place as follows:

For n0 <= i < n0 + nrot we map qubit i to qubit n0 + (i + rot) % nrot. E.g. nrot = 3, rot = 1, n0 = 0 means qubits are mapped as 0->1, 1->2, 2->0.

Here the entries of the state matrix are labelled by bit vectors of length n. Let qs(x[0],...,x[n-1]) be the entry of the state matrix corresponding to the bit vector (x[n-1],...,x[0]).

Then the function changes qs to qs' with qs'(...,x[start+nrot],y[nrot-1],...,y[0],x[start-1],...) = qs(...,x[start+nrot],z[nrot-1],...,z[0],x[start-1],...), where z[j] = y[j - rot (mod 3)].

If the state matrix qs has shape (n0, n1) then we label the entries of state matrix by bit vectors of length n0 + n1, with the n1 highest bits corresponding to the rows of the matrix, and the n0 lowest bits corresponding to the columns of the matrix.

property shape

Get shape of the complex matrix represented by the state

The function returns a pair (rows, cols) meaning that the state corresponds to a complex 2**nrows times 2**ncols matrix.

show(reduced=True)

Return a state as a string.

If reduced is True (default) then the reduced representation of the state is displayed. Otherwise the state is displayed ‘as is’.

The standard conversion of a state to a string, i.e. method __str__(), is equivalent to method show().

sumup(j, nqb, copy=True)

Sum up nqb qubits starting at position j.

Let qs be the state of shape (n0+n1), and let n = n0 + n1. We change qs to the following state qs' depending on n - nqb qubits:

qs'(x[n-1],...,x[j+nqb],x[j-1],...,x[0]) = sum_{x[j+nqb-1],...,x[j]} qs1(x[nn1-1],...,x[0]) .

The function returns ket, i.e. a column vector of shape (n - nqb, 0).

If the input is reduced then the result is also reduced.

If parameter copy is True (default) then a copy of the matrix is modified and returned.

to_symplectic()

Convert a quadratic state matrix to a symplectic bit matrix

Here the quadratic state matrix \(Q\) given by self must be an invertible \(2^k\times 2^k\) quadratic state matrix, i.e. \(Q\) must be of shape (k,k). So \(Q\) is in the Clifford group \(\mathcal{C}_k\) of k qubits, up to a scalar factor.

The function computes a \(2k \times 2k\) bit matrix \(A\) with the following property.

If \(v\) is a bit vector representing an element \(g_v\) of the Pauli group of k qubits then \(v \cdot A\) is the vector representing the element \(Q \cdot g_v \cdot Q^{-1}\) of that Pauli group, up to a scalar factor. Here elements of the Pauli group are given as integers representing bit vectors in the same way as in method pauli_vector, ignoring the bits 2k, 2k+1 corresponding to the scalar factor.

So this method computes the natural homomorphism from the Clifford group \(\mathcal{C}_k\) to the symplectic group \(\mbox{S}_{2k}(2)\).

The function returns \(A\) as a numpy array of shape (2*n), with the entries of that array corresponding to the rows of \(A\).

trace()

Return the trace of a square matrix.

The trace is returned as an integer, a floating point number, or a complex number.

xch_bits(sh, mask)

Exchange qubit arguments the state qs in place

We label the entries of the state matrix qs by bit vectors and define qs(x[n-1],...,x[0]), with n = n0 + n1, (n0, n1) = qs.shape as in method rot_bits.

We exchange qubit j with argument qubit j + sh of the state, if bit j of mask is set. If bit j of mask is set then bit j + sh of mask must not be set. No mask bit at position >= n - sh may be set.

E.g. qs.qstate12_xch_bits(1, 0x11) changes the state matrix qs to a state matrix qs' with qs'(...,x6,x5,x4,x3,x2,x1,x0.) = qs(...,x6,x4,x5,x3,x2,x0,x1).

mmgroup.structures.qs_matrix.qs_unit_matrix(nqb)

Return unit matrix as an instance of class QStateMatrix

The returned unit matrix has shape (nqb, nqb). So it represents a 2**nqb times 2**nqb unit matrix.

Computation in the Subgroup G_x0 of the monster

According to Conway’s construction of the monster \(\mathbb{M}\) in [Con85], the subgroup \(G_{x0}\) of structure \(2^{1+24}_+.\mbox{Co}_1\) has a faithful rational representation on the tensor product \(4096_x \otimes 24_x\). Here \(24_x\) is the representation of the group \(\mbox{Co}_1\) as the automorphism group of the real Leech lattice, and \(4096_x\) is the representation of a group \(G(4096_x)\) as a subgroup of the real Clifford group \(\mathcal{C}_{12}\), where the representation of \(\mathcal{C}_{12}\) is as in section Class QStateMatrix modelling a quadratic state matrix. Note that \(G(4096_x)\) is also of structure \(2^{1+24}_+.\mbox{Co}_1\).

We remark that the subgroup \(G_{x0}\) of the monster has five classes of involutions that map to 2B involutions in the monster, see [Wil13]. From Table 2 in [Nor98] we conclude that \(G_{x0}\) has two classes of involutions that map to 2A involutions in the monster. According to [Con85], the restriction of the 196883-dimensional representation of the monster to \(G_{x0}\) leads to a representation of \(G_{x0}\) of shape

\[299_x \oplus 98280_x \oplus 24_x \otimes 4096_x \, .\]

We can compute the characters of all these representations of \(G_{x0}\), e.g. with the C function xsp2co1_traces_fast in file xsp2co1_traces.c, or with function xsp2co1_traces_all in file xsp2co1_elem.c. The calculations in the python module mmgroup.tests.test_involutions.make_involution_samples show that the class of an involution in the group \(G_{x0}\) can be identified by computing the four characters given above.

We use the ideas in section Class QStateMatrix modelling a quadratic state matrix for implementing the representation \(4096_x\). In principle, the representation \(24_x\) is straightforward. The part \(4096_x\) of a representation of an element \(g\) of \(G_{x0}\) determines \(g\) up to sign. So \(g\) is uniquely determined if we store the image under \(g\) of a single vector in the representation \(24_x\). The space \(24_x\) is equivalent to the Leech lattice \(\Lambda\), and we store the image of a fixed shortest vector \(\beta\) in \(\Lambda/ 3 \Lambda\), which is the Leech lattice modulo 3, as follows.

Let \(\phi\) be the natural homomorphism from the subgroup \(Q_{x0}\) of \(G_{x0}\) of structure \(2^{1+24}\) onto \(\Lambda/ 2 \Lambda\), which is the Leech lattice modulo 2.

Let \(g \in G_{x0}\) be represented as a pair \((g_1, g_2) \in G(4096_x) \times \mbox{Co}_1\). Then \(g_2\) can be reconstructed from the image \(\beta \cdot g_2\) of a single shortest vector \(\beta\) in the Leech lattice (modulo 3).

The operation of \(g_2\) on a shortest vector \(\beta' \in \Lambda\) is given by

\[\beta' \mapsto \phi(g^{-1} \cdot \phi^{-1}(\beta' + 2 \Lambda) \cdot g) \in \Lambda / 2 \Lambda,\]

up to sign. Here a short vector in \(\Lambda / 2 \Lambda\) has precisely two opposite shortest preimages in \(\Lambda\), and we may take an arbitrary preimage in \(Q_{x0}\) when applying the inverse \(\phi^{-1}\) of \(\phi\).

We compute the image \(\beta' \cdot g_2\) of an arbitrary shortest vector \(\beta' \in \Lambda\) as follows. Assume first that \(\beta, \beta'\) are shortest vectors in \(\Lambda\) which are not perpendicular to each other, and assume that the shortest Leech lattice vector \(\beta \cdot g_2\) is known for some \(g_2 \in \mbox{Co}_1\). If \(\beta' \cdot g_2\) is known up to sign only, we can compute the sign of \(\beta'\) from the scalar products \((\beta, \beta')\), and \((\beta \cdot g_2, \beta' \cdot g_2)\), which must be equal. Since \(|(\beta, \beta')| \in \{1,2,4\}\), it suffices to compute the scalar products modulo 3. For perpendicular shortest vectors \(\beta, \beta'\) we can easily find a shortest vector \(\beta'' \in \Lambda\) with \((\beta, \beta'') \neq 0\) and \((\beta'', \beta') \neq 0\). So we may compute first \(\beta'' \cdot g_2\) and then \(\beta' \cdot g_2\) from these scalar products.

These ideas lead to a very fast implementation of the subgroup \(G_{x0}\) of the monster \(\mathbb{M}\). Details of that implementation are given in the C interface of the mmgroup project in section Computing in the subgroup G_{x0} of the Monster.

Class mmgroup.Xsp2_Co1 provides an implementation of the group \(G_{x0}\) based on these ideas.

Class `Xsp2_Co1` modelling an element of the group \(G_{x0}\)

class mmgroup.structures.xsp2_co1.Xsp2_Co1(tag=None, atom=None, *args, **kwds)

Models an element the subgroup \(G_{x0}\) of the monster

Here the subgroup \(G_{x0}\) is a subgroup of the monster of structure \(2^{1+24}.\mbox{Co}_1\). It is generated by the elements \(x_\delta, y_d, y_d, x_\pi, \xi\) described in section The Monster group.

The constructor of this class works exactly as the constructor of class MM. Here all elements of the monster \(\mathbb{M}\) occuring in the constructor must lie in the subgroup \(G_{x0}\) of the monster. So in the constructor all tags are legal, except for the tag 't'. A instance of class MM is accepted in the constructor of this class and vice versa.

The group operation and the operation on a vector of class MMVector is the same as in class MM.

This class uses a considerably faster implementation of the group operation as in class MM, as described in section Computation in the Subgroup G_x0 of the monster.

The user hardly ever has to deal with this class, since the implementation of class MM uses the accelerated functions in this class automatically where appropriate.

chi_G_x0()

Compute characters of element

The function returns a tuple \((\chi_M, \chi_{299}, \chi_{24}, \chi_{4096})\) of integers.

Here \(\chi_M\) is the character of the element in the 196833-dimensional rep \(198883_x\) of the monster.

By Conway’s construction of the monster we have:

\(198883_x = 299_x \oplus 24_x \otimes 4096_x \oplus 98280_x\),

for suitable irreducible representations \(299_x, 24_x, 4096_x, 98280_x\) of the group \(G_{x0}\). The corresponding characters of the element of \(G_{x0}\) are returned in the tuple given above.

While the product \(\chi_{24} \cdot \chi_{4096}\) is well defined, the factors \(\chi_{24}\) and \(\chi_{4096}\) are defined up to sign only. We normalize these factors such that the first nonzero value of the pair \((\chi_{24}, \chi_{4096})\) is positive.

conjugate_involution(mmgroup=None)

Find an element conjugating an involution standard element

If the element \(g\) given by self is an involution in the monster then the method computes an element \(h\) of the monster with \(h^{-1} g h = z\), where \(z\) is define as follows:

If \(g = 1\), we put \(h = z = 1\)

if \(g\) is a 2A involution (in the monster) then we let \(z\) be the involution in \(Q_{x0}\) corresponding to the Golay cocode word with entries \(2,3\) being set.

if \(g\) is a 2B involution (in the monster) then we let \(z\) be the central involution in \(G_{x0}\)

The function returns a pair (I, h), where \(h\) as an element of the instance MM of class MMGroup. We put I = 0 if \(g = 1\). We put I = 1, 2 if \(g\) is a 2A or 2B involution, respectively.

The function raises ValueError if \(g\) is not an involution.

This is a wrapper for the C function xsp2co1_elem_conjugate_involution.

Parameter mmgroup is not for public use. In special cases it may specify an alternative class implementing the monster group. Then the function returns \(h\) as an instance of that class.

conjugate_involution_G_x0(guide=0, group=None)

Map an involution in \(G_{x0}\) to a standard form.

Assume that the element \(g\) represented by self is an involution in the group \(G_{x0}\).

The function computes an element \(a\) in \(G_{x0}\) such that \(h = a^{-1} g a\) is a (fixed) representative of the class of \(g\) in the group \(G_{x0}\). The the function returns a pair (iclass, a), where a is the computed element of \(G_{x0}\), and iclass describes the representative \(h\) of the involution class as given in the following list:

iclass = '1A_x+': the neutral element \(x_1\)

iclass = '2B_x-': the central involution \(x_{-1}\)

iclass = '2A_x0': the element \(x_{\{2,3\}}\)

iclass = '2B_x0': the element \(x_{\Omega}\)

iclass = '2A_o+': the element \(y_o\)

iclass = '2B_o-': the element \(x_{-1} y_o\)

iclass = '2B_o0': the element \(x_{\{8,9\}} y_o\)

iclass = '2B_d0': the element \(x_{\{0, 12\}} y_d\)

Here in \(x_{\{i,j\}}\) the index \(\{i,j\}\) indicates a Golay cocode word of length 2 given by the entries \(i\) and \(j\). Octad \(o\) is the standard octad \(\{0,1,2,3,4,5,6,7\}\). Dodecad \(d\) is the standard dodecad \(\{0, 4, 8, 13, 14, 15, 17, 18, 19, 21, 22, 23\}\).

The first two characters of the string iclass denote the class in the Monster containing that class. The last character of the string iclass denotes the sign of the character of the class in the representation \(24_x \otimes 4096_x\).

By default, a is an instance of this class. If parameter group is set to a class representing a suitable subgroup of the monster (e.g. group = mmgroup.MM) then a is returned as an instance of that class.

Parameter guide should usually be zero. If guide is a type-4 vector \(v_4\) in the Leech lattice mod 2 such that the two conditions \(h = a^{-1} g a\) and \(v_4 \cdot a = \Omega\) can both be achieved then we compute an element \(a\) satisfying these two conditions. Otherwise parameter guide is ignored. Here \(\Omega\) is the standard frame in the Leech lattice.

order(max_order=119)

Return the order of the element of the monster group

If the argument max_order is present then the order of the element is checked up to (and including) max_order only. Then the function returns 0 if the order is greater than max_order. By default, the function returns the exact order of the element.

property subtype

Return subtype of an element

Let \(g \in G_{x0}\) be stored in self. The function returns the subtype of a \(g\). If \(g\) maps the standard frame \(\Omega\) of the Leech lattice modulo 2 to a frame of subtype \(t\) then \(g\) has subtype \(t\).

The subtype is returned as a pair of integers as in the corresponding method in class XLeech2, see section Computations in the Leech lattice modulo 2 in the guide for background.

Since the subtype is determined by the size of the denominators of the representation \(4096_x\), it can be computed very fast.

type_Q_x0()

Return type of element if it is in the subgroup \(Q_{x0}\)

If the element is in the subgroup \(Q_{x0}\) of the monster then the function returns the type of the vector in the Leech lattice modulo 2 corresponding to this element. That type is 0, 2, 3, or 4.

The function raises ValueError if the element is not in the subgroup \(Q_{x0}\).

The Coxeter group \(Y_{555}\) and the Bimonster

We want to find a homomorphism from the Coxeter group \(Y_{555}\) into the Bimonster

Module mmgroup.bimm contains an implementation of a (fixed) homomorphism from the Coxeter group \(Y_{555}\) into the Bimonster.

Description of the task to be done

The wreath product \(\mathbb{M} \wr 2\) of the Monster \(\mathbb{M}\) with the group \(Z_2\) of order 2 is called the Bimonster. In ATLAS notation [CCN+85] the Bimonster has structure \((\mathbb{M} \times \mathbb{M}).2\). It is generated by \(\mathbb{M} \times \mathbb{M}\) and an involution swapping the two copies of \(\mathbb{M}\).

A Coxeter group is a group generated by a finite set \(s_1,\ldots, s_k\) of involutions with a set of relations \((s_i, s_j)^{\alpha_{i,j}} = 1\) for each pair \(s_i, s_j\) of involutions. The Coxeter groups discussed in this application are given by graphs, where the vertices of the graph correspond to the generators \(s_i\). In the sequel a vertex of a graph describing a Coxeter group will be called a node. If two nodes \(s_i, s_j\) are connected by an edge then we have a relation \((s_i, s_j)^3 = 1\); otherwise we have a relation \((s_i, s_j)^2 = 1\). In the last case the generators \(s_i\) and \(s_j\) commute.

Norton and Ivanov have shown that the Bimonster is isomorphic to a certain Coxeter group, together with a single additional relation, see [Nor92], [Iva92]. That presentation of the Bimonster is called \(Y_{555}\).

The graph corresponding to the Coxeter relations in \(Y_{555}\) is given in the following Figure 1. The names of the generating reflections of \(Y_{555}\) in that figure are as in the ATLAS [CCN+85].

Figure made with TikZ

Coxeter relations in the group Y_555

We let \(Y_{555}\) be the Coxeter group given by the generators and relations in Figure 1 together with the following additional relation:

\[(a b_1 c_1 a b_2 c_2 a b_3 c_3)^{10} = 1 \, . \]

The purpose of this application is to implement the mapping from the group \(Y_{555}\) to the Bimonster. In the sequel we write \(Y_{555}\) for both, the graph in Figure 1, and the group defined above.

Extending \(Y_{555}\) to the incicdence graph of a projective plane

The graph \(Y_{555}\) can be extended to the incidence graph \(\mbox{IncP3}\) of the projective plane \(\mbox{P3}\) over the field \(\mathbb{F}_3\). The 26-Node Theorem states that there is a homomorphism from the Coxeter group given by \(\mbox{IncP3}\) to the Bimonster \(\mathbb{M} \wr 2\), see [CNS88]. A presentation of the Bimonster with the generators of that Coxeter group and defining relations is well known see e.g. [Nor02], [Far12] for an overview. We also write \(\mbox{IncP3}\) for the Coxeter group corresponding to to the incidence graph \(\mbox{IncP3}\).

In practice it turns out that working with \(\mbox{IncP3}\) is more flexible than working with \(Y_{555}\).

The projective plane \(P3\) contains 13 points \(P_i\) and 13 lines \(L_i\), \(0 \leq i < 13\). Point \(P_i\) is incident with line \(L_j\) if \(i + j \equiv 0, 1, 3,\) or \(9 \pmod{13}\). This construction of \(P3\) is also used in [CNS88], [Nor02], and [Far12]. We may map the 16 nodes of \(Y_{555}\) to a subset of the set of the 26 nodes of \(\mbox{IncP3}\) as follows:

\[\begin{split}\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} a & b_1 & b_2 & b_3 & c_1 & c_2 & c_3 & d_1 & d_2 & d_3 & e_1 & e_2 & e_3 & f_1 & f_2 & f_3 \\ \hline P_0 & L_0 & L_1 & L_3 & P_1 & P_2 & P_{11} & L_8 & L_7 & L_5 & P_5 & P_7 & P_4 & L_4 & L_6 & L_{10} \end{array}\end{split}\]

In the description of the Monster group, the ATLAS [CCN+85] uses the names of the 16 nodes of \(Y_{555}\) given in the table above. It also uses names for remaining 10 nodes of \(P3\), and it states the incidences between all these nodes. We number the remaining nodes in the ATLAS (preserving their incidence relations) as indicated in the follwing table:

\[\begin{split}\begin{array}{c|c|c|c|c|c|c|c|c|c} f & a_1 & a_2 & a_3 & g_1 & g_2 & g_3 & z_1 & z_2 & z_3 \\ \hline L_9 & P_3 & P_{12} & P_{10} & P_9 & P_8 & P_6 & L_{11} & L_2 & L_{12} \end{array}\end{split}\]

Implementing the Bimonster and the homomorphism from \(Y_{555}\) to it

The projective plane over \(\mathbb{F}_3\) and its automorphism group

The module implements the projective plane over \(\mathbb{F}_3\)

Module inc_p3 implements the projective plane P3 over \(\mathbb{F}_3\) and its automorphism group. Points and lines in P3 are implemented as instances of class P3_node, automorphisms of P3 are implemented as instances of class AutP3.

We mainly work with the incidence graph containing the points and the lines of P3 as vertices. The union of the set of the points and of the set of the lines in P3 is called the set of the nodes of the projective plane P3.

class mmgroup.bimm.P3_node(obj)

Models a point or a line the projective plane P3.

We number the 13 points in the projective plane P3 over \(\mathbb{F}_3\) from 0 to 12, and the 13 lines from 13 to 25. Then a point with number i and a line with number j are incident if \(i + j \equiv 0, 1, 3,\) or \(9 \pmod{13}\).

Some strings are also accepted as a description of a point or a line in P3. The 13 points may be denoted as ‘P0’,…,’P12’, and the the 13 lines may be denoted as ‘L0’,…,’L12’.

The names ‘a’, ‘b1’, ‘b2’, ‘b3’, ‘c1’, ‘c2’, ‘c3’, etc. refer to the embedding of the \(Y_{555}\) graph into the projective plane P3, as described in the documentation of the application. For background, see also [CNS88], [Far12].

Parameters:: obj – An integer, a string, or an instance of class AutP3 describing a point or a line in the projective plane P3.

name(): Return the name of the P3 node in standard notation

property ord: Return internal number of instance of class P3_node

y_name(): Return the name of the P3 node in Y_555 notation

class mmgroup.bimm.AutP3(mapping=None, data=None)

Models an automorphism of the projective plane P3.

This class models the automorphism group AutP3 of the projective plane P3 over the field \(\mathbb{F}_3\).

Elements of AutP3 should be given as (partial) mappings of points or lines. The standard way to describe an automorphism in AutP3 is a dictionary containing a partial mapping of points or lines. Here the keys and the values of the dictionary must either all be points or all lines; they must be objects describing points or lines as in the constructor of class AutP3. A mapping between points or lines is accepted if it extends to a unique mapping of the projective plane P3.

Parameters:

mapping – Describes a mapping of points or lines in the projective plane P3 as indicated in the table below.
data – Additional data (optional) that describe a mapping of points or lines in some special cases.

Legal types for parameter `mapping` in the constructor
type	Evaluates to
`None`	Creates the neutral element (default).
class `AutP3`	A deep copy of the given automorphism in class `AutP3` is returned.
`dict`	Dictionary containing a mapping between points or lines as described above.
`zip` object	`zip(x,y)` is equivalent to `dict(zip(x,y))`
`string` ‘r’	Then we construct a random automorphism (depending on parameter `data`) as described below.
`string` ‘p’	Then `data` must be a list of 13 integers (taken modulo 13), that describes a mapping of the 13 points.
`string` ‘l’	Then `data` must be a list of 13 integers (taken modulo 13), that describes a mapping of the 13 lines.

Remarks:

If parameter mapping is the string 'r', then an optional parameter data of type dict or zip that describes a partial mapping of points or lines may follow. In this case we construct a random automorphism of P3 satifying the constraints of the mapping given by parameter data, if present. Such a random automorphism is chosen from a uniform distribution of all possible cases.

For instances g1 and g2 of this class, g1 * g2 means group multiplication, and g1 ** n means exponentiation of g1 with the integer n. g1 ** (-1) is the inverse of g. g1 / g2 means g1 * g2 ** (-1).

g1 ** g2 means g2**(-1) * g1 * g2.

Multiplying an object of class P3_node with an object of class AutP3 means application of an automorphism of P3 to a point or line in P3.

line_map()

Return the automorphism as a line permutation list of length 13

Element g maps line x to line g.line_map[x]. The entries in the list are reduced modulo 13.

map()

Return the automorphism as a permutation list of length 26

Element g maps P3 node``x`` to node g.map[x]. Here the indices and values in the returned list are the numbers of the nodes as in class P3_node.

order(): Return order of element of the group AutP3

point_map()

Return the automorphism as a point permutation list of length 13

Element g maps P3 point``x`` to point g.map[x].

mmgroup.bimm.P3_incidences(*x)

Return list of P3 nodes incident with given P3 nodes

Here each argument of the function is a list of nodes of P3 describing a set \(S_i\) of nodes (i.e. points or lines) of P3. An entry of such a list may be anything that is accepted by the constructor of class P3_node. An integer argument is interpreted as a singleton, i.e. a set of size 1. A comma- separated string of names of P3 nodes is accepted as a set of P3 nodes.

The function returns the sorted list of P3 nodes (i.e instances of class AutP3 that are incident with at least one node in each set \(S_i\) and not contained in any of the sets \(S_i\).

mmgroup.bimm.P3_incidence(*x)

Return (unique) P3 node incident with given P3 nodes

Here each argument describes a P3 node (i.e. a point or a line); it may be anything accepted by the constructor of class P3_node.

If there is a unique P3 node incident with all these P3 nodes then the function returns that node as an instance of class P3_node.

Otherwise the function raises ValueError.

This function is a simplified version of function P3_incidences. Its typical use case is to find a line through two points or the intersection point of two lines.

mmgroup.bimm.P3_remaining_nodes(x1, x2)

Complete points on a line or lines intersecting in a point

If arguments x1, x2 are different points or lines in P3 then the function returns the list of the two remaining points on the line through x1 and x2, or the list of the two remaining lines containing the intersection point of x1 and x2, respectively. Otherwise the function raises ValueError.

Arguments x1, x2 may by anything accepted by the constructor of class P3_node. The result is returned as list of two instances of class P3_node.

mmgroup.bimm.P3_is_collinear(l)

Check if list of P3 nodes contains 3 collinear nodes

Argument l of the function is a list of nodes of P3 describing a set of nodes (i.e. of points or lines) of P3. An entry of such a list may be anything that is accepted by the constructor of class P3_node. A comma-separated string of names of P3 nodes is accepted as a set of nodes.

The function returns True if that set of nodes contains 3 collinear points or 3 collinear lines, and False otherwise.

Norton’s presentation of the Monster group

This module implements Norton’s generators of the Monster.

Norton [Nor02] has given a presentation of the Monster group that greatly simplifies a mapping from the projecive plane presentation of the Monster to the representation of the Monster in [Gri82] and [Con85]. Our implemention of the Monster is based on the representation in [Con85]. So we may use the presentation in [Nor02] to construct a homomorphism from the projecive plane representation of the Monster into our implementation of the Monster that can be computed in practice.

mmgroup.bimm.Norton_generators(check=False)

Return the images of Norton’s generators in the Monster

Norton [Nor02] defines a presention of the Monster with generators \((s,t,u,v,x)\) and relations.

The function returns the images of the presentation of these generators in the Monster under a (fixed) homomorphism. The result is returned as a quintuple of instances of class MM, corresponding to the images of these generators in the Monster.

If parameter check is True then we also check the relations in this presentation.

The Bimonster and its presentation \(Y_{555}\)

This module implements the Bimonster.

Class BiMM in this module implements an element of the Bimonster \(\mathbb{M} \wr 2\) as described in the documentation of this application. Let \(\mbox{IncP3}\) be the Coxeter group as in that documentation. Function P3_BiMM maps a word of generators of \(\mbox{IncP3}\) into the Bimonster. The generators of \(\mbox{IncP3}\) correspond to the points and lines of the projective plane \(\mbox{P3}\) over the field \(\mathbb{F}_3\). A point or a line of \(\mbox{P3}\) is implemented as an instance of class P3_node in module inc_p3.

There is also a natural mapping from the automorphism group of \(\mbox{P3}\) into the Bimonster compatible with the mapping from the Coxeter group into the Bimonster. Function AutP3_BiMM computes that mapping. An automorphism of \(\mbox{P3}\) is implemented as an instance of class AutP3 in module inc_p3. For background see [Nor02].

class mmgroup.bimm.BiMM(*args)

This class models an element of the Bimonster.

The Bimonster is the group \(\mathbb{M} \wr 2\) of structure \((\mathbb{M} \times \mathbb{M}).2\), where \(\mathbb{M}\) is the Monster group.

Parameters:

m1 (Instance of class MM) – An element \(m_1\) of the Monster that embeds into the Bimonster as \((m_1, 1)\). Default is the neutral element \(1\) of the Monster.
m2 (Instance of class MM) – An element \(m_2\) of the Monster that embeds into the Bimonster as \((1, m_2)\). Default is the neutral element \(1\) of the Monster.
e (integer) – An optional exponent of the involution \(\alpha\), default is 0. Conjugation of an element of \(\mathbb{M} \times \mathbb{M}\) by \(\alpha\) means swapping the two factors in the direct product.

Returns:

The element \((m_1, m_2) \cdot \alpha^e\) of the Bimonster

Return type:

Instance of class BiMM

Arguments m1 or m2 may be anything that is accepted by the constructor of class MM as a single argument.

Alternatively, m1 may be an instance of class BiMM; then arguments m2 and e must be dropped.

Let g1 and g2 be instances of class BiMM representing elements of the Bimonster group. g1 * g2 means group multiplication, and g1 ** n means exponentiation of g1 with the integer n. g1 ** (-1) is the inverse of g. g1 / g2 means g1 * g2 ** (-1). We have 1 * g1 == g1 * 1 == g1 and 1 / g1 == g1 ** (-1).

g1 ** g2 means g2**(-1) * g1 * g2.

decompose()

Decompose the element of the Bimonster

The function returns a triple (m1, m2, e) such that the element of the Bimonster is equal to \((m_1, m_2) \cdot \alpha^e\). Here m1 and m2 are instances of class MM representing the elements \(m_1\) and \(m_2\) of the Monster, and e is equal to 0 or 1.

order(): Return the order of the element of the Bimonster

mmgroup.bimm.P3_BiMM(pl=[])

Map a word of generators in \(\mbox{IncP3}\) into the Bimonster

Parameters:: pl (List containing integers, strings, or instances of class P3_node) – List of generators in \(\mbox{IncP3}\). Each entry in the list should be an instance of class P3_node. Such an entry may also be an integer or a string accepted by the constructor of class P3_node.
Returns:: The image of the word of the given generators in the Bimonster
Return type:: Instance of class BiMM

An integer pl or an instance pl of class P3_node is considered as a word of length 1.

pl may also be a string of alphanumric identifiers separated by commas. This is interpreted as a sequence of generators, where the names of the generators are interpreted as in the constructor of class P3_node.

mmgroup.bimm.AutP3_BiMM(g)

Map an automorphism of \(\mbox{P3}\) into the Bimonster

Parameters:: g (Instance of class AutP3) – Automorphism of \(\mbox{P3}\)
Returns:: The image of the automorphism of \(\mbox{P3}\) in the Bimonster
Return type:: Instance of class BiMM

Parameters g may be anything that is accepted by the constructor of class AutP3 as a single argument.

Example: Checking the spider relation in the group \(Y_{555}\)

As stated in the description of the group \(Y_{555}\) , the spider relation in that group is:

\[(a b_1 c_1 a b_2 c_2 a b_3 c_3)^{10} = 1 \, . \]

We can quickly check the spider relation as follows:

# Class BiMM implements an element of the Bimonster.
# Function P3_BiMM maps a product of generators of 
# the Coxeter group IncP3 to the Bimonster.
from mmgroup.bimm import  BiMM, P3_BiMM
# List of generators of IncP3 corresponding to the spider relation 
spider = ['a', 'b1', 'c1', 'a', 'b2', 'c2', 'a', 'b3', 'c3'] * 10
# Let 'Spider' be the image of the spider relation in the Bimonster
Spider = P3_BiMM(spider)
# Check that this is equal to >the neutral element of the Bimonster
assert Spider == BiMM(1)

Alternatively, the spider relation can be verified as follows:

from mmgroup.bimm import  P3_BiMM
# Put Spider1 = a * b_1 * c_1 * a * b_2 * c_2 * a * b_3 * c_3.
# Here we enter that product into the Bimonster as a string
Spider1 = P3_BiMM('a, b1, c1, a, b2, c2, a, b3, c3')
# Check that Spider1 has order 10 in the Bimonster
assert Spider1.order() == 10

Construction of the mapping from the Coxeter group into the Bimonster

Let \(\mbox{IncP3}\) be the Coxeter group generated by the nodes \(P_i, L_i, 0 \leq i < 13\) of the projective plane \(\mbox{P3}\) as above, and let \(\mbox{AutP3}\) be the automorphism group of \(\mbox{P3}\). Let \(\,\mbox{IncP3}:\mbox{AutP3}\,\) be the split extension of the group \(\mbox{IncP3}\) by the factor group \(\mbox{AutP3}\), where \(\mbox{AutP3}\) operates naturally on the generating reflections of the Coxeter group \(\mbox{IncP3}\).

In this section we construct a mapping from \(\,\mbox{IncP3}:\mbox{AutP3}\,\) to the Bimonster.

Therefore we use the Norton’s presentation [Nor02] of the Monster. Then we follow the ideas in Farooq’s thesis [Far12] for extending that presentation of the Monster to a homomorphism from the Coxeter group \(\mbox{IncP3}\) to the Bimonster. We assume that the reader is familiar with [Nor02] and we will adopt notation from ibid.

Norton’s presentation of the Monster and the Bimonster

Norton [Nor02] defines a presentation \((s,t,u,v,x,\alpha)\) of the group \(\mbox{IncP3}:\mbox{AutP3}\), where \(s,t,u \in \mbox{AutP3}\), \(v = \prod_{i=1}^{12} P_i\), \(x = P_0 L_0\), \(\alpha = P_0 v\). Then he adds a relation that maps \(\mbox{IncP3}\) to the Bimonster \(\mathbb{M} \wr 2\), thus obtaining a presentation of \((\mathbb{M} \wr 2):\mbox{AutP3}\). Next he shows that this is actually a presentation of the direct product \((\mathbb{M} \wr 2) \times \mbox{AutP3}\). Then he adds a set of relations that cancel the factor \(\mbox{AutP3}\), leading to a presentation of the Bimonster with the generators \((s,t,u,v,x,\alpha)\). It turns out that all these generators, except for \(\alpha\), are in the subgroup \(\mathbb{M} \times \mathbb{M}\) of index 2 of the Bimonster \(\mathbb{M} \wr 2\). Finally, he gives a further set of relations in the generators \((s,t,u,v,x)\) cancelling the second factor of the direct product \(\mathbb{M} \times \mathbb{M}\), thus obtaining a presentation of the Monster \(\mathbb{M}\). We remark that \(P_i^u = P_{i-1}\) and \(L_i^u = L_{i+1}\), with indices to be taken modulo 13, so that \(P_i\) and \(L_i\) can easily be computed from the generators \((s,t,u,v,x,\alpha)\).

Let \(\mbox{IncP3}^+\) be the subgroup of \(\mbox{IncP3}\) generated be the products of generators \(P_i, L_i\) of \(\mbox{IncP3}\) with an even number of factors. Then \(\mbox{IncP3}^+\) has index 2 in \(\mbox{IncP3}\), and the presentation \((s,t,u,v,x)\) together with the relations mentioned above defines a mapping \(\phi\) from \(\mbox{IncP3}^+ : \mbox{AutP3}\) into the Monster.

Mapping Norton’s presentation into our representation of the Monster

Essentially, our task is to construct an explicit mapping from the generators \((s,t,u,v,x,\alpha)\) of \(\mbox{IncP3} : \mbox{AutP3}\) into the Bimonster \(\mathbb{M} \wr 2\). A first step for achieving this goal is to actually construct a mapping \(\phi\) from the generators \((s,t,u,v,x)\) of \(\mbox{IncP3}^+ : \mbox{AutP3}\) to \(\mathbb{M}\).

In [Nor02] for each point \(P_i\) an element \(P^*_i\) of of the subgroup \(\mathbb{M} \times \mathbb{M}\) of the Bimonster is defined. The elements \(P^*_i\) are called the stars (corresponding to the points \(P_i\)); and it is shown that \(\mbox{AutP3}\) permutes the stars \(P^*_i\) in the same way as it permutes the corresponding points. Actually, the stars \(P^*_i\) are defined as words of generators \(P_i, L_i\) of even length, modulo the relations defining the Bimonster.

According to [Nor02] we have \(\phi(x) = \tau\) for the generator \(x\), where \(\tau\) is the triality element of the Monster. There it is also shown that the stars and the (products of an even number of) points map to elements of the extraspecial subgroup \(Q_{x0}\) (of structure \(2^{1+24}\)) of the Monster. In [Nor02] explicit images of the points and stars in \(Q_{x0}\) are constructed up to sign. More specifically, the images of these elements are given in the Leech lattice modulo 2, which is isomorphic to the quotient of \(Q_{x0}\) by its centre \(\{1, x_{-1}\}\). It is easy to see that the signs of the images of the points and stars may be chosen arbitrarily, with the only restriction that the product \(P^*_0 P^*_1 P^*_3 P^*_9\) must be mapped to the element \(x_{\Omega}\) of \(Q_{x0}\), and not to its negative \(x_{-\Omega}\). It can be shown that the tuple \((P_0 P_1, \ldots, P_0 P_{12}, P^*_1, \ldots, P^*_{12})\), when taken modulo the centre of \(Q_{x0}\), corresponds to a basis of the Leech lattice modulo 2. So for defining the mapping \(\phi\) on the points and the stars it suffices to specify the signs of the images of the entries of that tuple. It turns out that everything works fine if we declare all these signs to be positive. This means that for any such image \(x_d x_\delta \in Q_{x0}\), with \(d \in \mathcal{P}, \delta \in C^*\), we choose \(d\) to be a ‘positive’ element of the Parker loop \(\mathcal{P}\), according to our construction of \(\mathcal{P}\).

With this choice the mapping \(\phi\) is uniquely defined on the points and on the stars; and we shall see that it is also uniquely defined on all generators \((s,t,u,v,x)\) of the presentation given in [Nor02]. The functions PointP3 and StarP3 in module mmgroup.bimm.p3_to_mm compute the mapping \(\phi\) on the points and the stars, respectively.

The mapping \(\phi\) is already defined on \(x\) and on \(v\) (since \(v\) is a product of points). Generators \(s,t,u,\) are defined as automorphisms in \(\mbox{AutP3}\); so it suffices compute \(\phi(a)\) for \(a \in \mbox{AutP3}\).

It is also shown in [Nor02] that the images of elements of \(\mbox{AutP3}\) are in the centralizer \(G_{x0}\) (of structure \(2^{1+24}.\mbox{Co}_1\)) of the element \(x_{-1}\). Note that the images of the points and the stars generate the group \(Q_{x0}\); so the action of any automorphism in \(\mbox{AutP3}\) is determined (as an element of \(G_{x0}\)) by its action on the points and the stars, up to sign. The group \(\mbox{AutP3}\) is the simple group \(L_3(3)\) in ATLAS notation. Thus it is generated by its elements of odd order. For any \(g \in G_{x0}\) at most one of the elements \(g, x_{-1} \cdot g\) has odd order, so that the correct image of any element of \(\mbox{AutP3}\) of odd order (and hence the image of the any element of \(\mbox{AutP3}\)) in \(G_{x0}\) is uniquely defined. So we can also construct the images of the generators \((s,t,u)\). Function Norton_generators in module mmgroup.bimm.p3_to_mm returns the images of the generators \((s,t,u,v,x)\) under our mapping \(\phi\).

Faaroq [Far12] had to perform strenuous calculations for actually computing \(\phi\) on \(\mbox{AutP3}\), since he had to use the representations of the groups \(G_{x0}\) and \(\mathbb{M}\) available in 2012. With our construction of the Monster and of \(G_{x0}\) we are in a much more comfortable situation. Function AutP3_MM in module mmgroup.bimm.p3_to_mm quickly computes the mapping \(\phi\) on \(\mbox{AutP3}\). In the remainder of this subsection we discuss the operation of that function.

The relevant automorphsims \(a \in \mbox{AutP3}\) are given as mappings between the 13 points and the 13 stars, where the stars are transformed in the same way as corresponding points. Using our contruction of \(\phi\) on the points and the stars, the image \(\phi(a)\) can be given as an automorphism of \(Q_{x0}\) in \(G_{x0}\), where \(G_{x0}\) operates on \(Q_{x0}\) by conjugation. Given such an automorphism \(\gamma\) on \(Q_{x0}\), the C function xsp2co1_elem_from_mapping in file xsp2co1_map.c computes the corresponding element \(g\) of the group \(G_{x0}\) up to sign.

We close with some remarks on how the C function xsp2co1_elem_from_mapping works.

Class Xsp2_Co1 in module mmgroup.structures.xsp_co1 wraps fast C functions for computing in the group \(G_{x0}\), so that computations in \(G_{x0}\) are easy. Given an automorphism \(\gamma\) of \(Q_{x0}\) as above, we can easily compute the image \(\gamma(\tilde{\Omega})\), where \(\tilde{\Omega}\) is the vector in the Leech lattice modulo 2 corresponding to the standard frame in the Leech lattice. The C function gen_leech2_reduce_type4 in file gen_leech_reduce.c can compute an element \(h_1 \in G_{x0}\) that maps \(\gamma(\tilde{\Omega})\) to \(\tilde{\Omega}\), see section Computations in the Leech lattice modulo 2 in the guide for developers for mathematical background. So if \(g \in G_{x0}\) corresponds to the automorphism \(\gamma\) then \(g h_1\) corresponds to an automorphism \(\gamma_1\) of \(Q_{x0}\) fixing \(\tilde{\Omega}\). The stabilizer of \(\tilde{\Omega}\) in \(G_{x0}\) is a group \(N_{x0}\) of structure \(2^{1+24}.2^{11}.M_{24}\). The automorphism \(\gamma_1\) can easily be computed from \(\gamma\) and \(h_1\). So it remains the considerably simpler task to compute an element of \(N_{x0}\) corresponding to the automorphism \(\gamma_1\) of \(Q_{x0}\). This computation is done as described in the documentation of the C function xsp2co1_elem_from_mapping.

From the Monster to the Bimonster

In this section we construct a mapping \(\Phi\) from the group \(\,\mbox{IncP3} : \mbox{AutP3} \,\) to the Bimonster using the mapping \(\phi : \mbox{IncP3}^+ : \mbox{AutP3} \rightarrow \mathbb{M}\) defined in the last subsection.

The generator \(\alpha\) in \(\mbox{IncP3} \setminus \mbox{IncP3}^+\) is an involution that acts on \(\mbox{IncP3}^+\) (and also on \(\,\mbox{IncP3} ^+: \mbox{AutP3}\)) by conjugation. Hence by Theorem 3.1 in [CNS88] there is a mapping \(\Phi\) from \(\,\mbox{IncP3} : \mbox{AutP3} \,\) to the Bimonster \(\mathbb{M} \wr 2\) given by:

\[\Phi(y) = (\phi(y), \phi(y^\alpha)) \in \mathbb{M} \times \mathbb{M} \,, \quad \mbox{for} \quad y \in \,\mbox{IncP3} ^+: \mbox{AutP3},\]

and \(\Phi(\alpha)\) is the involution in \(\mathbb{M} \wr 2\) swapping the two copies of \(\mathbb{M}\). For simplicity, we will also write \(\alpha\) for the element \(\Phi(\alpha)\) of \(\mathbb{M} \wr 2\).

Since \(\alpha = \prod_{i=0}^{12} P_i\) commutes with all points \(P_i\) and also with \(\mbox{AutP3}\), we have:

\[\begin{split}\Phi(P_i) = \alpha \cdot (\phi(\alpha \cdot P_i), \phi(\alpha \cdot P_i)) \, , \\ \Phi(a) = (\phi(a), \phi(a)) \,, \quad \mbox{for} \; a \in \mbox{AutP3} \, .\end{split}\]

It remains to compute \(\Phi(L_i)\). Here have to compute \(\phi(L_i^\alpha)\). Therefore we will use the follwing fact:

It easy to show that the elements of the Bimonster \(\mathbb{M} \wr 2\) that are conjugate to \(\alpha\) are precisely the elements of shape \(\alpha \cdot (m, m^{-1})\), \(m \in \mathbb{M}\).

Since \(\Phi(P_0) = \alpha \cdot (\phi(\alpha \cdot P_0), \phi(\alpha \cdot P_0))\) holds for the involution \(P_0\), we conclude that \(\Phi(P_0)\) is conjugate to \(\alpha\) in \(\mathbb{M} \wr 2\). In a Coxeter group all nodes connected by a path of edges are conjugate; so the nodes \(\Phi(L_i)\) are also conjugate to \(\alpha\). Together with the fact stated above we obtain:

\[\Phi(L_i) = \alpha \cdot (\phi(\alpha \cdot L_i), \phi(\alpha \cdot L_i)^{-1}) \, .\]

Note that \(\phi(\alpha \cdot L_0) = \phi(v) \cdot \tau\), where \(\tau\) is the triality element in the Monster. Furthermore, we have

\[\phi(\alpha \cdot L_i) = \phi(\alpha \cdot L_0)^{\phi(u)^i} \,.\]

Version history

List of releases
Version	Date	Description
0.0.1	2020-05-20	First release
0.0.2	2020-06-04	Order oracle added; bugfixes
0.0.3	2020-06-10	Bugfixes in code generator
0.0.4	2020-06-15	MSVC compiler is now supported
0.0.5	2021-08-02	Word shortening in monster implemented
0.0.6	2021-12-01	Group operation accelerated
0.0.7	2021-12-01	Bugfix in version generation
0.0.8	2022-07-12	Performance improved
0.0.9	2022-09-01	Performance improved
0.0.10	2022-10-11	Support for cibuildwheel added
0.0.11	2022-10-19	Bugfixes and macOS version added
0.0.12	2023-01-09	Support for the group Y_555 and the Bimonster
0.0.13	2023-10-27	Supports numbering elements of the Monster, and Python 3.12
0.0.14	2024-01-19	Demonstration code for reduction in the Monster added
1.0.0	2024-01-23	First official release (documentation updated)
1.0.1	2024-02-23	Support for exporting C functions from libraries
1.0.2	2024-02-27	Changes in build system regarding shared libraries

References

[AG04] (1,2,3,4,5,6)

S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. CoRR, 2004. URL: http://arxiv.org/abs/quant-ph/0406196.

[Asc86] (1,2,3,4)

M. Aschbacher. Sporadic Groups. Cambridge University Press, New York, 1986.

[Con85] (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24)

J. H. Conway. A simple construction of the Fischer-Griess monster group. Inventiones Mathematicae, 79:513–540, 1985.

[CCN+85] (1,2,3,4,5,6,7)

J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson. Atlas of Finite Groups. Clarendon Press, Oxford, 1985.

[CS99] (1,2,3,4)

J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, New York, 3rd edition, 1999. ISBN 0-387-98585-9.

[CNS88] (1,2,3,4)

J.H. Conway, S.P. Norton, and L.H. Soicher. The bimonster, the group y_555, and the projective plane of order 3. In Computers in Algebra (Chicago 1985), 27–50. Lecture Notes in Pure and Appl. Math, 111, Dekker, New York, 1988.

[Far12] (1,2,3,4,5)

A. Farooq. Some computations in the monster group and related topics. Doctoral thesis, School of Mathematical Sciences. Queen Mary University of London, 2012. URL: https://qmro.qmul.ac.uk/xmlui/bitstream/handle/123456789/8484/Farooq_A_PhD_final.pdf.

[Gri82] (1,2)

R. L. Griess. The friendly giant. Inventiones Mathematicae, 69:1–102, 1982.

[Iva99]

A. A. Ivanov. Geometry of Sporadic Groups I, Petersen and Tilde Geometries. Cambridge University Press, June 1999. ISBN 0521413621.

[Iva09] (1,2,3)

A. A. Ivanov. The Monster Group and Majorana Involutions. Cambridge University Press, April 2009. ISBN 0521889944.

[Iva92]

A.A. Ivanov. A geometric characterization of the monster. In Groups, combinatorics & Geometry (Durham, 1990), 46–62. London Math Soc. Lecture Notes Ser 165, Cambridge University Press, 1992.

[LPWW98]

S. Linton, R. Parker, P. Walsh, and R. Wilson. Computer construction of the Monster. J. Group Theory, 1:307–337, 1998.

[NRS01] (1,2,3,4,5,6,7)

G. Nebe, E. M. Rains, and N. J. A. Sloane. The invariants of the clifford groups. IJDCC: Designs, Codes and Cryptography, 2001.

[Nor02] (1,2,3,4,5,6,7,8,9,10,11,12,13,14)

S. Norton. Transforming the monster presentation. Preprint, published as an appendix in [Far12], 2002. URL: https://qmro.qmul.ac.uk/xmlui/bitstream/handle/123456789/8484/Farooq_A_PhD_final.pdf.

[Nor98]

S. P. Norton. Anatomy of the monster: i. In The Atlas of Finite Groups - Ten Years On, 198–214. Cambridge University Press, 1998.

[Nor92]

S.P Norton. Constructing the monster. In Groups, combinatorics & Geometry (Durham, 1990), 63–76. London Math Soc. Lecture Notes Ser 165, Cambridge University Press, 1992.

[Sey20] (1,2,3,4,5,6,7,8,9,10,11)

M. Seysen. A computer-friendly construction of the monster. arXiv e-prints, pages arXiv:2002.10921, February 2020. arXiv:2002.10921.

[Sey22] (1,2,3,4,5)

M. Seysen. A fast implementation of the Monster group. arXiv e-prints, pages arXiv:2203.04223, 2022. arXiv:2203.04223.

[Wik23]

Wikipedia. Monster group. 2023. URL: https://en.wikipedia.org/wiki/Monster_group.

[Wil01]

R. A. Wilson. The Monster is a Hurwitz group. J. Group Theory, 4:367–374, 2001.

[Wil13] (1,2)

R. A. Wilson. The Monster and black-box groups. arXiv e-prints, pages arXiv:1310.5016, October 2013. arXiv:1310.5016.

The mmgroup API reference

Introduction

Installation and test

Installation on 64-bit Windows

Installation on Linux and macOS with a 64-bit x86 CPU

Other platforms

Basic structures

The Golay code and its cocode

The Parker loop

Octads and suboctads

Automorphisms of the Parker loop

Generating random elements of certain subgroups of \(M_{24}\)

The Leech lattice modulo 2 and its preimage \(Q_{x0}\)

The basis of the Golay code and of its cocode

The Monster group

Generators of the monster group \(\mathbb{M}\)

Representing elements of the monster group

Implementation of the generators of the monster group

Multiplication of elements of the monster group

Python classes implementing the Monster group

Functions dealing with elements of the Monster group

Generating random elements of certain subgroups of the Monster

Describing a random subgroup of the Monster

Some small subgroups of the Monster

Large 2-local subgroups of the Monster

Long-term stable storage of elements of the Monster group

The representation of the Monster group

Creating basis vectors of the representation space \(\rho_p\)

Description of the basis vectors of the representation space

Representing a vector as a list of tuples

Operations on vector in the representation \(\rho_p\)

Special tags for creating vectors in the representation \(\rho_p\)

Linear order of the basis vectors

Sparse representation of vectors in \(\rho_p\)

Other data types accepted as tags for vectors in \(\rho_p\)

Python classes implementing the representation of the Monster group

Auxiliary functions for the representation of the Monster group

Long-term stable storage of vectors of the representation

The subgroup \(G_{x0}\) of the Monster and the Clifford group

Introduction

Computation in the Clifford group

Quadratic mappings

Background from the theory of quantum computing

Implementation of quadratic mappings

Changing the representation of a quadratic mapping

Reducing the representation of a quadratic mapping

Extending a quadratic mapping

Products and tensor products of quadratic mappings

An algorithm for multiplying quadratic mappings

Computing tensor and matrix products

Restricting a quadratic mapping

Quadratic state matrices

Displaying quadratic state vectors and matrices

Reducing a quadratic state matrix

The Pauli group

Applying a gate to a quadratic mapping

Computing the trace of a quadratic state matrix

Class QStateMatrix modelling a quadratic state matrix

Computation in the Subgroup G_x0 of the monster

Class Xsp2_Co1 modelling an element of the group \(G_{x0}\)

The Coxeter group \(Y_{555}\) and the Bimonster

Description of the task to be done

Extending \(Y_{555}\) to the incicdence graph of a projective plane

Implementing the Bimonster and the homomorphism from \(Y_{555}\) to it

The projective plane over \(\mathbb{F}_3\) and its automorphism group

Norton’s presentation of the Monster group

The Bimonster and its presentation \(Y_{555}\)

Example: Checking the spider relation in the group \(Y_{555}\)

Construction of the mapping from the Coxeter group into the Bimonster

Norton’s presentation of the Monster and the Bimonster

Mapping Norton’s presentation into our representation of the Monster

From the Monster to the Bimonster

Version history

Class `QStateMatrix` modelling a quadratic state matrix

Class `Xsp2_Co1` modelling an element of the group \(G_{x0}\)