The mmgroup API reference¶
Introduction¶
The mmgroup package is a python implementation of Conway’s construction [Con85] of the monster group \(\mathbb{M}\). In mathematics the monster group \(\mathbb{M}\) is the largest sporadic finite simple group. The group \(\mathbb{M}\) 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\) .
It has a rational representation \(\rho\) of dimension \(196884\) with coefficients in \(\mathbb{Z}[\frac{1}{2}]\), see [Con85]. So we obtain a modular representation \(\rho_p\) of \(\mathbb{M}\) by reducing the rational representation \(\rho\) modulo an arbitrary odd number \(p\). The current version of the mmgroup package supports the representations \(\rho_p\) of \(\mathbb{M}\) for \(p = 3, 7, 15, 31, 127, 255\).
The mmgroup package uses highly optimized C programs for calculating in the representations of \(\rho_p\) of \(\mathbb{M}\), which are most efficient if \(p+1\) is a small power of two. Most of these C programs have been generated automatically by a program code generator which is also part of this project, but not part of the public interface described in this document.
In the description of the mmgroup package we use the notation in [Sey20], where an explicit description of the representations \(\rho(g), g \in G\) is given for a generating subset \(G\) of \(\mathbb{M}\).
Installation¶
Installation on 64bit Windows¶
For installing the mmgroup package on a 64bit Windows system you simply type:
pip install mmgroup
32bit Windows systems are not supported.
Installation on Linux¶
There is experimantal support for installing the mmgroup package on a Linux system from a source distribution. Details are given in the guide for developers.
Basic structures¶
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
to0xfff
. Biti
in that number refers to the coefficient of thei
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 classGCode
.
Depending on its type parameter value is interpreted as follows:
¶ type
Evaluates to
int
Here the code word with number
value
is returned.0 <= value < 0x1000
must hold.list
ofint
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 to3
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 typeGcVector
is converted to a Golay code word and returned. Up to3
erroneous bits in that vector are corrected.class
SubOctad
The octad part of the
SubOctad
value
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
orParity
) are done as usual.The bitwise and operator
&
means bitwise and of two code words of typeGCode
. The result of such an operation on two Golay code words is a Golay cocode word of typeCocode
.The bitwise
&
operator of a Golay code word and a Golay cocode word of typeCocode
is not well defined as a bit vector, but it has a welldefined parity. So in this case the result of the&
operator is a parity object of typeParity
.For the bitwise
&
operator bit vectors of typeGcVector
, see classGcVector
.The
~
operator means bitwise complement as usual; it returns the complemented code word, which is also of typeGCode
.Standard functions
len(g)
returns the bit weight of the Golay code wordg
, i.e. the number of bits set in the wordg
.Special functions
Let
g1
,g2
, andg3
be Golay code vectors of typeGCode
.The expression
g1/4
is a shorthand forParity(len(g1)/4)
. It returnslen(g1)/4
modulo2
as a parity object of typeParity
.GcVector(g1 & g2)
returns the bitwise intersection ofg1
andg2
as a bit vector of typeGcVector
.(g1 & g2)/2
is a shorthand forParity(len(GcVector(g1 & g2))/2)
. It returns the halved bit weight ofg1 & g2
modulo2
as a parity object of typeParity
. This value is also called the commutator ofg1
andg2
.g1 & g2 & g3
returns the parity of the bitwise intersection ofg1
,g2
, andg3
as a parity object of typeParity
. This value is also called the associator ofg1
,g2
, andg3
.abs(g1)
is a shorthand forabs(PLoop(g1))
, see classPLoop
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 to0
or1
.
 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 numbero
. 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 numberi
.
 split()¶
Split the Golay code word
g
. Returns
A triple
(0, eo, v)
withg = Omega * eo + v
.
Here
Omega
is the Golay code word containing one bits only,eo
is0
or1
, andv
is a Golay code word of typeGCode
with0 <= 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)
withg = Omega * eo + o
.
Here
Omega
is the Golay code word containing one bits only,eo
is0
or1
, andv
is a Golay code word of typeGCode
which is either the zero code word or an octad, i.e. a code word of weight8
.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 modulo2
. 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 typeGCode
. Returns
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 classPLoop
.Let
g1
andg2
be Golay code words of typeGCode
. ThenPLoop(g1)
andPLoop(g2)
are the corresponding positive Parker loop elements, andg1.theta(g2)
is an integer modulo2
of typeParity
. 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 numberv
. Biti
of the numberv
is thei
th coordinate of the corresponding bit vector.
 class mmgroup.GcVector(value)¶
Models a 24bit vector in the underlying space of the Golay code.
The \(2^{24}\) bit vectors are numbered from
0
to0xffffff
. Biti
in that number refers to the coefficient of thei
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 classGcVector
.
Depending on its type parameter value is interpreted as follows:
¶ type
Evaluates to
int
Here the bit vector with number
value
is returned.0 <= value < 0x1000000
must hold.list
ofint
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
orParity
) are done as usual. The sum of a bit vector and a Golay code word (of typeGCode
) is a bit vector. The sum of a bit vector and a cocode word (of typeCocode
) is a cocode word of typeCocode
.The bitwise and operators
&
,
, and~
operate on two bit vectors as expected. If the other operand is a Golay code vector (of typeGCode
) then it is converted to a bit vector.Standard functions
len(v)
returns the bit weight of the bit vectorv
, i.e. the number of bits set in the vectorv
. 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 to0
or1
.
 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 numberi
.
 syndrome(i=None)¶
Return syndrome of cocode element as a bit vector.
 Parameters
i –
None
(default) or an integer0 <= 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
isNone
and the syndrome is not unique.
v.syndrome(i)
is equivalent toCocode(v).syndrome(i)
.
 syndrome_list(i=None)¶
Return syndrome of cocode element as list of bit positions.
 Parameters
i –
None
(default) or an integer0 <= 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
isNone
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 toCocode(v).syndrome_list(i)
.
 property vector¶
Return the number of the bit vector.
We have
0 <= i < 0x1000000
for the returned numberi
.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
to0xfff
. Biti
in that number refers to the coefficient of thei
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:
¶ type
Evaluates to
int
Here the cocode element with number
value
is returned.0 <= value <= 0x1000
must hold.list
ofint
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
SubOctad
The cocode part of the
SubOctad
value
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
orParity
) are done as usual.g & c
andc & g
are legal operations for a Golay code elementg
of typeGCode
and a cocode elementc
of typeCocode
. The result of this operation is not well defined as a bit vector, but it has a welldefined parity. Thusg & c
returns a parity object of typeParity
.Standard functions
Let
c
be a cocode element of typeCocode
.len(c)
returns the bit weight of a shortest representative of the Golay code elementc
.Special functions
The expression
c % 2
is a shorthand forParity(len(c))
. It returns the parity ofc
as a parity object of typeParity
. property cocode¶
Return the number of the cocode element.
We have
0 <= i < 0x1000
for the returned numberi
.Same as property
ord
.
 property ord¶
Return the number of the cocode element.
We have
0 <= i < 0x1000
for the returned numberi
.
 syndrome(i=None)¶
Return syndrome of cocode element as a bit vector.
 Parameters
i –
None
(default) or an integer0 <= 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
isNone
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 weight4
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 integer0 <= 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
isNone
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.
 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 classParity
, or on instances of this class combined with integers.The values
1**p
and(1)**p
are defined as usual for an objectp
of classParity
. Similarly,g**p
is defined ifg
is an element of a group defined in this package and has order1
or2
. More precisely,g
must be an instance of classAbstractGroupWord
here.Bitwise operations
&
,
, and^
are illegal on instances of classParity
.Parity(x)
is defined ifx
an integer, an instance of classParity
, or an instance of any class defined is this package which has a natural parity, e.g. an instance of classGcVector
orCocode
.int(p)
evaluates to0
or1
for an instance of classParity
.Implementation remarks
If an object
x
has an attribute or a propertyparity
thenParity(x)
meansParity(x.parity)
andx + p
meansParity(x) + p
for any instancep
of class Parity.If an object
x
has an attribute or a propertyparity_class
thenx * p
andp * x
meanParity(parity_class(x) * int(p))
. If that attribute or a property has valueTrue
thenx * p
andp * x
meanParity(x * int(P))
. property ord¶
Return
1
if the parity is odd and0
if it is even
The Parker loop¶
We deal with the Parker loop, which is a nonassociative 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\) = \((0,\tilde{\Omega})\), 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 corresponsing
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 posivtive 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 nonassociative loop with \(2^{1+12}\) elements. Each element can be interpreted as a signed Golay code word, see class
GCode
. Accordingly, classPLoop
is a subclass of classGCode
.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 isPLoopOne
.PLoopOmega
is the (positive) element corresponding to the allone vector of the Golay code.The \(2^{1+12}\) Parker loop elements are numbered from
0
to0x1fff
. Elements0
to0xfff
are are positive and corresponding to the Golay code words with the same number. The element with number0x1000 ^ i
is the negative of the element with numberi
. 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 classPLoop
.
Depending on its type parameter value is interpreted as follows:
¶ type
Evaluates to
int
Here the code word with number
value
is returned.0 <= value < 0x2000
must hold. We havePLoop(0) == PLoopOne
,PLoop(0x1000) == PLoopOne
, andPLoop(0x800) == ~PLoopOne == PLoopOmega
.list
ofint
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
SubOctad
The octad part of the
SubOctad
value
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 nonassociative loop operation. Division by a Parker loop element means multiplication by its inverse, and exponentiation means repeated multiplication, witha**(1)
the loop inverse ofa
, as usual.The
~
operator maps the Parker loop elementa
toa * PLoopOmega
, leaving the sign ofa
unchanged.Multiplication with the integer
1
or1
means the multiplication with the neutral elementPLoopOne
or with its negativePLoopOne
, respectively.If any of the oprations
+
,
or&
is applied to a Parker loop element, that element is converted to a Golay code word of typeGCode
, ignoring the sign. This conversion also takes place if a Parker loop element is multiplied or divided by an integer different from1
or1
.Standard functions
len(a)
is a shorthand forlen(GCode(a))
. Here functionGCode(a)
convertsa
to a Golay code word of typeGCode
.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 numberi
.
 parity_class¶
alias of
mmgroup.structures.gcode.GCode
 property sign¶
Return the sign of the Parker loop element.
This is
1
for a positive and1
for a negative element.
 split()¶
Split sign and Omega from Parker loop element
a
. Returns
a triple
(es, eo, v)
witha = (1)**e1 * PLoopOmega**eo * v
.
Here
v
is the unique (positive) element of the Parker loop of typePLoop
with0 <= v.ord < 0x800
satisfying that equation.es
andeo
are0
or1
.
 split_octad()¶
Split Parker loop element
a
into central element and octad Returns
a triple
(es, eo, o)
witha = (1)**e1 * PLoopOmega**eo * o
.
Here
o
is either the neutral Parker loop elementPLoopOne
or Parker loop element corresponding to a positive octad.es
andeo
are0
or1
. An octad is a Golay code word (of typeGCode
) of weight8
. 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 is0
 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 word1,...,1
.e1
andeo
may also be parity objects of typeParity
.
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 wellknown 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\). Class SubOctad
models such a pair. The constructor of class 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 class 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 SubOctad
that pair is given by
(so.octad, so.suboctad)
.
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:
¶ type
Evaluates to
int
Here the (positive) octad with number
octad
is returned. There are 759 octads in the Golay code. So0 <= octad < 759
must hold.list
ofint
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
SubOctad
The octad part of the
SubOctad
octad
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.
 class mmgroup.SubOctad(octad, suboctad=0)¶
Models a pair (octad, suboctad)
 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 pair (octad, suboctad)
 Return type
an instance of class
SubOctad
 Raise
TypeError if argument octad or suboctad is not of correct type.
ValueError 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 class
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 from0
to758
and the suboctads form0
to63
, depending on the octad. Note that every octad has64
suboctads.Depending on its type parameter suboctad is interpreted as follows:
¶ 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
ofint
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.
class
SubOctad
The
suboctad
part of theSubOctad
value
is taken.str
 Create random element depending on the string
'r'
: Create arbitrary suboctad
Remark
For an object
so
of typeSubOctad
useOctad(so)
to obtain its octad as a Parker loop element andCocode(so)
obtain its suboctad as a cocode element. You may obtain more information from the properties of the objectso
.If parameter
octad
is of typeSubOctad
orXLeech2
the this parameter already describes a pair(octad, suboctad)
. as_tuple()¶
Return data as a tuple
The function returns a tuple
(sign, 'T', octad, suboctad)
wheresign
,octad
, andsuboctad
are the integers given by the corresponding properties in classSubOctad
.Such a tuple is used for indexing vectors in the representation of the monster group.
 property cocode¶
Return number of cocode word corresponding to the suboctad.
We have
0 <= c < 0x1000
for the returned numberc
.
 property gcode¶
Return number of Golay code word corresponding to the octad.
We have
0 <= g < 0x1000
for the returned numberg
.
 property octad¶
Return number of octad.
We have
0 <= o < 759
for the returned numbero
.
 property sign¶
Return the sign of the octad.
This is
1
for a positive and1
for a negative octad.
 property suboctad¶
Return the number of the suboctad.
We have
0 <= s < 64
for the returned numbers
.Let
[b0, b1,..., b7
] be the bits set in the octad of an instance of this class in natural order. 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 withXOR
.¶ [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 numbers = 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
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}\).
The easiest 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}}\).
 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 classAutPL
then this describes an automporphism of the Parker loop; in that case parameterp
must be set to its default value. Legal types of parameterd
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 ofMat24
.unique – If this is
True
(default) and parameterp
is notr
then parameterp
must describe a unique permutation in the Mathieu groupM_24
. Otherwise we take the least possible permutation (in lexicographic order) that agrees with parameterp
.
 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
.
¶ 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 parmeterp
must be set to its default value.¶ type
Evaluates to
int
Here the integer is the number of a permutation in the Mathieu group
M_24
.list
ofint
A list
l_p
of24
of disjoint integers0 <= i < 24
is interpreted as a permutation inM_24
that mapsi
tol_p[i]
.dict
A dictionary specifies a mapping from a subset of the integers
0 <= i < 24
to integers0 <= dict[i] < 24
. This mapping must extend to a permutation inM_24
. If parameterunique
isTrue
(default) then that permutation must be unique.zip
objectzip(x,y)
is equivalent todict(zip(x,y))
.str
 Create random element depending on
str
'r'
: Create an random element ofM_24
Any other string is illegal.
Let
a
be an instance of classGcVector
,GCode
,Cocode
, orPLoop
, and letg1
,g2
be instances of classAutPL
. Thena * g1
is the result of the natural operation ofg1
ona
, which belongs to the same class asa
.g1 * g2
means group multiplication, andg1 ** n
means exponentiation ofg1
with the integern
.g1 ** (1)
is the inverse ofg
.g1 / g2
meansg1 * g2 ** (1)
.g1 ** g2
meansg2**(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 tog.group.word
reconstructs the elementg
.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()
returnsa
.
 property cocode¶
Return number of cocode element in the automorphism.
For an instance
g
ofAutPL
we haveg == AutPL(Cocode(g.cocode)) * AutPL(g.perm)
.
 property parity¶
Return parity of an automorphism
This is
s
ifPLoopOmega
maps to(1)**s * PLoopOmega
fors == 0
ors == 1
.
 property perm¶
Return permutation of automorphism as a list
p_l
.Then the permutation maps
i
top_l[i]
fori = 0,...,23
.
 property perm_num¶
Return the number of the permutation of the automorphism
The Mathieu group
M_24
has244823040
elements numbered from0
to244823039
in lexicographic order. Thus the neutral element has number0
.
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]:
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:
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
to0x1ffffff
. Elements0
to0xffffff
are considered positive. The element with number0x1000000 ^ i
is the negative of the element with numberi
.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.
Depending on its type parameter value is interpreted as follows:
¶ 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
SubOctad
The
SubOctad
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 Create random element depending on the string classXLeech2
.str
see explanation below.
If value is of one of the type listed above then the following parameter is coneted to an element of the Golay cocode (as in the constructor of class
Cocode
multiplied to the converted parmetervalue
from the right.Alternatively, parameter
value
may be a single letter. Ifvalue
is one of the capital lettersBCTXE
then that letter and the following arguments are passed to the constructor of classMMVector
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 integeri
is given as a second parameter'r'
then we generate a random element of \(Q_{x0}\) of typei
. 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\). Ifi
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, withq**(1)
the inverse ofq
, as usual.Multiplication with the integer
1
or1
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.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 \(G_{x0}\) acts monomially by right multiplication.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 196884dimensional 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. property mmdata¶
Return internal representation of corresponding monster element.
That internal representation is returned as a numpy array of 32bit integers.
 property ord¶
Return the number of the element of \(Q_{x0}\) .
We have
0 <= i < 0x2000000
for the returned numberi
.
 property sign¶
Return the sign of the element \(Q_{x0}\).
This is
1
for a positive and1
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 classCocode
.
 str()¶
Represent group element as a string
 property subtype¶
Return pair
(type, subtype)
of the element of \(Q_{x0}\)Here
type
is as in propertytype
, and subtype is a onedigit 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.
 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 propertysubtype
. See section Computations in the Leech lattice modulo 2 in the guide for background.
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
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 generating of the monster group
using the constructor of class MM
:
Element 
Construction as an instance of class 

\(x_\delta\) 

\(x_\pi\) 

\(x_e\) 

\(y_e\) 

\(z_e\) 

\(\tau^e\) 

\(\xi^e\) 

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
in the generators given above. The user should be aware of the fact
that multiplication with the *
operator is a concatenation of such
words, followed by (rather incomplete) reduction step. This means that
multplying words may still lead to an exponential growth of the word
length.
On can apply the method simplify
to an element of the monster group.
This method shortens a word representing an element of \(\mathbb{M}\)
to a reasonable length with a very high probability. However, applying
this method usually takes a long time. On the author’s computer it may
take several minutes to shorten the product of two (previously shortened)
random words. This is yet considerably faster than the run time reported
in [Wil13].
In such a word we always reduce substrings of generators of the
subgroup \(N_0\) of \(\mathbb{M}\) to a standard form,
which is easy. We apply no relations to the remaining generator
\(\xi\), except for \(\xi^3=1\). Method simplify
uses
the techique described in [Wil03] for shortening a word
in the monster group.
Future development¶
Future versions of this package may implement improved reduction strategies for words of generators of \(\mathbb{M}\) :
Long words of generators of \(\mathbb{M}\) can be shortened with high probability by method
mmgroup.MM.simplify
. This method uses the algorithm in [Wil03]. This may take a long time. Here improvements in future versions are desirable.
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
andg2
be instances of classMM
representing elements of the monster group. Theng1 * g2
means group multiplication, andg1 ** n
means exponentiation ofg1
with the integern
.g1 ** (1)
is the inverse ofg
.g1 / g2
meansg1 * g2 ** (1)
. We have1 * g1 == g1 * 1 == g1
and1 / g1 == g1 ** (1)
.g1 ** g2
meansg2**(1) * g1 * g2
.Let
V
be a vector space that is a representation ofMM
, see classMMVector
for details. An instanceg1
of classMM
operates on the vector spaceV
by right multiplication. Variables
tag – In the simplest case, parameter
tag
is a string of length1
that determines the type of the atomic group element. There are also some special cases for parametertag `` as indicated below. If ``tag
is not given or equal to1
then the neutral element of the monster group is constructed.i –
Parameter
i
is number of the atomic element of a giventag
. Depending on the tag,i
may be the number of an element of one of the structuresPLoop
,Cocode
, or the number of an element of the Mathieu groupM_24
, as explained in classAutPL
. An element \(\pi\) of the groupAutPL
is mapped to the element \(x_\pi\) of the Monster group.The number
i
may also be an instance of the appropriate classPLoop
,Cocode
, orAutPL
, 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.
¶ Tag
Number
i
Type of element
'p'
0244823039
The automorphism
AutPL(0, i)
of the Parker loop, see below.'d'
00xfff
The diagonal automorphism
Cocode(i)
inAutPL
.'x'
00x1fff
The element \(x_e\), with
e = PLoop(i)
.'y'
00x1fff
The element \(y_e\),
e = PLoop(i)
; similar to tag'x'
.'z'
00x1fff
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'
02
The element \(\tau^i\),
'l'
02
The element \(\xi^i\),
'q'
00x1ffffff
Describes an element of the subgroup \(Q_{x0}\). See remark below.
'c'
00xffffff
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. Ifi
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'
theni = 'o'
generates a random odd andi = 'e'
generates a random even diagonal automorphism. In this case i` may also be an instance of classCocode
, representing the diagonal automorphism correspnding to the given element of the Golay cocode.If
tag == 'p'
theni
may also be an instance of classAutPL
. Then the returned atom is the Parker loop automorphism given by that instance. Ifi
is an integer then the Parker loop automorphismAutPL(0, i)
is returned. This automorphism is the standard rpresentative of the ith element of the Mathieu groupM_24
in the automorphism group of the Parker loop.If
tag
is'x'
,'y'
or'z'
theni
may also be an instance of classPLoop
, representing an element of the Parker loop.The exponent
i
for a tag't'
or'l'
is reduced modulo3
.The tag
'q'
is useful for encoding an element of the subgroup \(Q_{x0}\) of the monster. An atom with tag'q'
and indexi
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 indexi
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 type4 vector given by the indexi
. Herei
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.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. Then a uniform distributed element from that subgroup is generated. The follwing subgroups are recognized:¶ Parameter
i
Subgroup
'M'
The monster group itself
'G_x0'
Subroup
'G_x0'
generated by \(x_d, x_\delta, y_d, x_\pi, \xi\)'N_0'
Subroup
'N_0'
generated by \(x_d, x_\delta, y_d, x_\pi, \tau\)'N_x0'
Subroup
'N_x0'
generated by \(x_d, x_\delta, y_d, x_\pi\)'N_0_e'
Subroup of
'N_0'
of index 2 generated by \(x_d, x_\delta, y_d, x_\pi, \tau\), \(\delta\) even'N_x0_e'
Subroup of
'N_x0'
of index 2 generated by \(x_d, x_\delta, y_d, x_\pi\), \(\delta\) evenSubgroup
'G_x0'
has structure \(2^{1+24}.\mbox{Co}_1\), and subgroup'N_0'
has structure \(2^{2+11+22}.\mbox{M}_{24}\).'N_x0'
is a subgroup of'N_0'
of index 3.If Parameter
i
is an positive integer 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 arraylike 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 32bit 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 length1
. There are a few other types which are also accepted as tags. For such a special tag, the following parameteri
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.
¶ 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 than1
For an instance
g
of classMM
we haveMM(str(g)) == g
.So we can reread printed elements of
MM
. 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()¶
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 196833dimensional 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.
 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)
, whereo
is the order of the element.If
o
is even then the function returns the pair(o, h)
, whereh
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 functioncheck_mm_order
.If
h
is in the subgroup \(G_{x0}\) thenh
is returned as a word in the generators of that subgroup.
 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 reducedAn element
g
of the monster group represented by an instance of this class may be reduced by callingg.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 32bit 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 returns0
if the order is greater thanmax_order
. By default, the function returns the exact order of the element.
 reduce(copy=False)¶
Reduce a group element
If group elements are implemented as words, some functions may produce unreduced words. This function reduces the group element in place.
Note that all operators return reduced words. Functions return reduced words unless stated otherwise. However, reducing all words representing the same group element to the same word may be beyond the capabilties of a program.
If
copy
is set then a reduced copy of the element is returned, in case that the input element is not already reduced.
 simplify(ntrials=None, verbose=0)¶
Try to simplify an element of the monster group
This function tries to simplify an element of the monster group. It may take a long time, but this is the only way to prevent the explosion of the word lengths of elements of the monster group.
The current version uses the word shortening algorithm in [Wil03]. Parameter
ntrials
specifies the number of trials. Here the default value forntrials
should be used, since the parameter may be dropped in future versions.The word shortening algorithm and the implementation of this method is experimental and may change in future versions!
The representation of the monster group¶
We deal with the 196884dimensional representation of the monster.
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}\). Here
\(\rho\) is the rational representation 196884_x
of the
monster constructed in in [Con85], and \(\rho_p\)
is obtained from \(\rho\) by taking all matrix coefficients
modulo a small odd number p
. This package supports the
cases p = 3, 7, 15, 31, 127, 255
.
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.
For calculating in \(\rho_p\) the user may create an instance
of class MM
that models an element g
of the 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.
Vector v
acts on the element g
of \(\mathbb{M}\) 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
function MMV(p)
returns
an object correponding 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)
.
Vector 
Tuple 
Remarks 

\((ij)_1\) 


\(X_{ij}\) 


\(X^+_{ij}\) 


\(X^+_{d \cdot \delta}\) 

\(d \in \mathcal{P}\),
\(\delta \in \mathcal{C^*}\),
\(d\) an octad,
\(\delta \subset d\),
\(\delta\) even. See class
We have 
\(X^+_{d \cdot i}\) 


\(d^+ \otimes_1 i\) 


\(d^ \otimes_1 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 norm1
.In the tuple
('T',o,s)
the integerso
ands
describe the instanceSubOctad(o, s)
of classSubOctad
. Hereo
ands
may be anything that is accepted as input forSubOctad(o, s)
In the tuples
('X',d,i)
,('Y',d,i)
,('Z',d,i)
, the inputd
may be an instance of classPLoop
or anything such thatPLoop(d)
is an instance of classPLoop
. For an instanced
of classPLoop
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 to1
's'
: a factor1
or1
selected at random
'n'
: a random nonzerodivisor modulop
'r'
: a random integer modulop
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>
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:
Tag 
Condition for 
Condition for 













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)
fori0 > i1
offset
576
:Tuples
(C,i0,i1)
, same order as tuples(A,i0,i1)
fori0 > 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 vector containing many zero entries. In sparse representation the vector is given as an array of unsigned 32bit integers. Here each entry of the array encodes a multiple of the basis vector. Such an entry it interpreted as follows:
Component 




Bits 




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:














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 dscribed as a tuple
(tag, i0, i1)
, wheretag
is a single capital letter andi0
,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 cast 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 classMM
) operates on a vectorv
(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 adressed asv[tag, i0, i1]
, wheretag
is a single letter in the stringABCTXYZD
andi0
andi1
are integers, such that the tuple(tag, i0, i1)
describes a basis vector. Getting and setting entries of a vector is as in thenumpy
package. Herei0
andi1
may also be slices of integers in the same way as innumpy
arrays. Depending on thetag
, the valuei0
ori1
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 beginnning of section The representation of the monster group. Herev['E', i]
is thei
th entry in that order. Indexi
may also be a slice of integers in the same way as in a onedimensionalnumpy
array.The internal representation of a vector
v
in this class is not part of the public interface. Usev['E']
to convertv
to an onedimensional array of8
bit integers of length 196884. as_sparse()¶
Return vector in sparse representation
The sparse representation of a vector is returned as a onedimensional numpy array of 32bit 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 classMMSpace
.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 andvalue
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
inplaceHere
g
is an element of the moster group represented as an instance of classMM
ande
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. Ifbreak_g
is set, we always doabs(e)
muliplications withg
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 spaceW
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 legaltag
is letter in the stringABCTXYZD
, as explained in table Basis vectors of the representation of the monster and classMMSpace
.
 class mmgroup.MMSpace(*args, **kwds)¶
Models a
196884
dimensional representation of the monster groupThis class contains a collection of functions for manipulating vectors in the rpresentation \(\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 methodtuple_to_index
. Otherwise the tuple(tag, i0, i1)
is interpreted a standard index for such a basis vector. Iftag
is an instance of classMMVector
, 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 length24
. The norm of the returned vector is32
.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 index0 <= i < 196884
for a basis vector, the function returns that index as a tuple(tag, i0, i1)
withtags
one letter of the string"ABCTXYZ"
and integersi0
,i1
.See method
tuple_to_index
for details.If
index
is an instance of classMMVector
, 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 indexRemarks:
The tuple
('D', i0)
is accepted as a shorthand for('A', i0,i0)
.A tuple
('E', i0)
means a linear indexi0
, i.e. this method returnsi0
on input('E', i0)
, for0 <= i0 < 196884
.If
tag
is an instance of classMMVector
, 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 correponding to the space \(\rho_p\)
Here characteristic
p
is as in the constructor of classMM
. 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 modulemmgroup
returns the list of legal values for the characteristicp
.Technically,
MMV(p)
is the partial application of the constructor of classMMVector
to the numberp
.
The subgroup \(2^{1+24}.Co_1\) of the monster and the Clifford group¶
The section describes the fast computation in a certain subgroup \(G_{x0}\) 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 operation. 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 complexvalued 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
A mapping \(g: V \rightarrow \mathbb{T}\) is bilinear if
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
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
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(v) \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
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 ot 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.
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 GottesmanKnill 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:
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}^{n1} 2^j \cdot i_j\),
\(i_j \in \{0,1\}\) denotes the bit vector
\((i_{n1},...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:
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 offdiagonal 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:
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
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
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:
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
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
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 complexvalued 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_2jc} \rightarrow \mathbb{C}\) by
where \(x' \in \mathbb{F}_2^{jc}, \; x_\lambda \in \mathbb{F}_2^{n_\lambdaj}\). 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. Condsidering 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
onedimensional 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**(jc), 1))
c2a = c2.reshape((2**c, 2**(jc), 1))
c3 = np.einsum("cjk,cjl>jkl", c1a, c2a)
c3 = c3.reshape((1,))
Without going into details, we remark that in the graphical ZXcalculus (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/ZXcalculus .
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,j1)}, A^{(\lambda,j1)}, Q^{(\lambda,j1)}\) satisfy the conditions given above. Then we can compute \(\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big)\) from \(\big(e^{(\lambda,j1)}, A^{(\lambda,j1)}, Q^{(\lambda,j1)}\big)\) as follows:
Case 1: Both, \(A^{(1,j1)}\) and \(A^{(2,j1)}\), have a row with leading coefficient in column \(j\).
Since \(A^{(1,j1)}\) and \(A^{(2,j1)}\) are in reduced echelon form and the first \(j1\) columns of these two matrices are equal, we conclude that the first \(j\) columns of \(A^{(1,j1)}\) and \(A^{(2,j1)}\) are equal.
So we may put \(\big(e^{(\lambda,j)}, A^{(\lambda,j)}, Q^{(\lambda,j)}\big) = \big( e^{(\lambda,j1)}, A^{(\lambda,j1)}, Q^{(\lambda,j1)}\big)\) for \(\lambda = 1,2\).
Case 2: Only \(A^{(1,j1)}\) has a row with leading coefficient in column \(j\).
Assume that this row of \(A^{(1,j1)}\) has index \(i\). We add row \(i\) to all rows \(k\) of \(A^{(1,j1)}\) where \(A^{(1,j1)}_{k,j} \neq A^{(2,j1)}_{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,j1)'}, A^{(1,j1)'}, Q^{(1,j1)'}\big)\) of \(g^{(1,j1)}\), where the first \(j\) columns of \(A^{(1,j1)'}\) and \(A^{(2,j1)}\) are equal, except for the coefficient in row \(i\), column \(j\).
We obtain \(A^{(1,j)}\) from \(A^{(1,j1)'}\) by deleting row \(i\) of \(A^{(1,j1)'}\), and \(Q^{(1,j)}\) from \(Q^{(1,j1)'}\) by deleting row and column \(i\). We put \(e^{(1,j)} = e^{(1,j1)'}\). We put \(\left(e^{(2,j)},A^{(2,j)},Q^{(2,j)}\right)\) = \(\left(e^{(2,j1)},A^{(2,j1)},Q^{(2,j1)}\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,j1)'}\) does not change \(g^{(1)} \cdot g^{(2)}\).
Let \(D^{(\lambda)}\) be the submatrix of \(A^{(\lambda,j1)'}\) that consists of the first \(j\) columns of \(A^{(1,j1)'}\). 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,j1)}\) has a row with leading coefficient in column \(j\).
This case is symmetric to case 2, exchanging the role of \(A^{(1,j1)}\) and \(A^{(2,j1)}\).
Case 4: Neither \(A^{(1,j1)}\) nor \(A^{(2,j1)}\) has a row with leading coefficient in column \(j\).
Case 4.1: Columns \(j\) of \(A^{(1,j1)}\) and \(A^{(2,j1)}\) are equal.
Then we may proceed as in case 1.
Case 4.2: Column \(j\) of \(A^{(1,j1)}\) and \(A^{(2,j1)}\) are equal except in row \(0\).
Assume that \(x^{(1)}\) is in the support of \(g^{(1,j1)}\), \(x^{(2)}\) is in the support of \(g^{(2,j1)}\), and that the leftmost \(j1\) bits of \(x^{(1)}\) and \(x^{(2)}\) are equal. Then from the properties of \(A^{(1,j1)}\) and \(A^{(2,j1)}\) we conclude that \(x^{(1)}\) and \(x^{(2)}\) must differ in the bit at position \(j\). Thus \(g^{(1,j1)} \cdot g^{(2,j1)}\) 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,j1)}_{i,j} \neq A^{(2,j1)}_{i,j}\).
Let \(i\) be the highest row index such that \(A^{(1,j1)}_{i,j} \neq A^{(2,j1)}_{i,j}\) holds.
For \(\lambda = 1,2\) we add row \(i\) to all rows \(k\) of \(A^{(\lambda,j1)}\) where \(A^{(1,j1)}_{k,j} \neq A^{(2,j1)}_{k,j}\) by applying operations \(T_{i,k}\).
So we obtain a representation \(f\big(e^{(1,j1)'}, A^{(1,j1)'}, Q^{(1,j1)'}\big)\) of \(g^{(1,j1)}\), where the first \(j\) columns of \(A^{(1,j1)'}\) and \(A^{(2,j1)}\) are equal, except for the coefficient in row \(i\), column \(j\).
For \(j = 1, 2\) we obtain \(A^{(\lambda,j)}\) from \(A^{(\lambda,j1)'}\) by deleting row \(i\) of \(A^{(\lambda,j1)'}\). We obtain \(Q^{(\lambda,j)}\) from \(Q^{(\lambda,j1)'}\) by deleting row and column \(i\). We put \(e^{(\lambda,j)} = e^{(\lambda,j1)'}\).
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,j1')}\) and \(A^{(2,j1')}\) does not change \(g^{(1)} \cdot g^{(2)}\).
Now we may compute the product of \(g^{(1)}\) and \(g^{(2)}\) as follows:
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 symmtric \((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:
The corrections in row and column \(0\) of \(Q^{(1 \odot 2)}\) are necessary, since the diagonal entries of \(Q^{(1)}\) are to be interpreted modulo \(4\).
So our algorithm allows us to multiply guadratic 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,j1)}, A^{(\lambda,j1)}, Q^{(\lambda,j1)}\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,j1)}\) of the representation of \(g^{(1,j1)}\) always has a row \(i\) such that \(A^{(1,j1)}_{i,j}\) is the only nonzero entry in row \(i\) and in column \(j\) of \(A^{(1,j1)}\). Furthermore, row \(i\) and column \(j\) of \(Q^{(1,j1)}\) are zero in that case. Thus only cases 1 and 2 can occur in the above computation, and adding row \(i\) of \(A^{(1,j1)}\) to any other row in that matrix affects column \(j\) of \(A^{(1,j1)}\) only, and does not affect \(Q^{(1,j1)}\). In our implmentation 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_1j} \rightarrow \mathbb{C}\) to a mapping \(g^{(1')}: \mathbb{F}_2^{j} \times \mathbb{F}_2^{n_1j} \times \mathbb{F}_2^{n_2j} \rightarrow \mathbb{C}\), with \(g^{(1')}\) not depending on the last factor \(\mathbb{F}_2^{n_2j}\), 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_1j} \times \mathbb{F}_2^{n_2j} \rightarrow \mathbb{C}\), with \(g^{(2')}\) not depending on the factor \(\mathbb{F}_2^{n_2j}\) in the middle. Then we simply have \((g^{(1)} \odot g^{(2)})_j = g^{(1')} \cdot g^{(2')}\).
Using the techniqes 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
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^{nc} \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
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_{n1},\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^{n1j} \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 containg 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 64bit 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 braket 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 subpace 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 braket 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 offdiagonal 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:
We use the same notation if the values \(a_i\) are
kets or matrices witten in the form ket><bra
.
For example:
. 10><01
. 1 10
+j 1
means \(1 \cdot \left10\right> \left<01\right  1 \cdot \left11\right> \left<11\right  \sqrt{1} \cdot \left10\right> \left<00\right + \sqrt{1} \cdot \left11\right>\left<10\right\).
E.g. the coefficient in the third term of that sum is computed as:
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 necessarly 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\) satifying condition (2.) by applying a seqence 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 corrsponding 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 Hadamardlike matrix. By a Hadamardlike 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 nonmonimial 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 conugate 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 effiency,
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 occuring 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 symmetic 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.
Applying a gate to a quadratic mapping¶
In the theory of quantum computing we may apply socalled gates to a quadratic state vector in \((\mathbb{C}^2)^{\otimes n}\). For our puposes a gate is a linear operation on \((\mathbb{C}^2)^{\otimes n} = (\mathbb{C}^2)^{\otimes k} \otimes (\mathbb{C}^2)^{\otimes nk}\) which may be written as a tensor product of a unitary \(2^k \times 2^k\) matrix G and a \(2^{nk} \times 2^{nk}\) identitiy 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 decompostion 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_{n1},\ldots,x_j,\ldots,x_{0}) = \exp(\phi x_j \sqrt{1}) \cdot g(x_{n1},\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_{j1},\ldots) + (1)^{x_j} \cdot g(\ldots,x_{j+1},1,x_{j1},\ldots) \; .\end{split}\]We implement the application of a Hadamard gate on qubit \(j\) to a quadatic 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 imlpementation can be seen as follows. W.l.o.g we assume that \(j\) is the last index \(0\). Let \(x = (x_{n1},\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_{n1},\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_{n1},\ldots, x_0) = g(x_{n1},\ldots, x_1, 0) + (1)^{x_0} \cdot g(x_{n1},\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, n1\) 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 classQStateMatrix
) –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 parameterrows
is anint
) – Binary logarithm of the number of columns of the matrixdata – 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 classQStateMatrix
.
In terms of the theory of quantum computing,
rows, cols = 0, n
creates a column vector or a ketv>
corresponding to a state of ofn
qubits, androws, cols = n, 0
creates a row vector or a bra<v
corresponding to a linear function on a state ofn
qubits.If
rows == cols == n
and the created2**n
times2**n
matrix is invertible, then the matrix is (a scalar multiple of) an element of the complex Clifford \(\mathcal{X}_{12}\) ofn
qubits described in [NRS01].If
rows
is an instance of this class then a copy of that instance is created.If
rows
andcols
are integers thendata
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 The subgroup 2^{1+24}.Co_1 of the monster and the Clifford group, subsection Quadratic state matrices. In this case parametermode
is evaluated as follows:1: create matrix
Q
from lower triangular part2: create matrix
Q
from upper triangular partAnything else: matrix
Q
must be symmetric.
An integer
v
. Then one of the valuesrows
andcols
must be zero and the unit (row or column) vector with indexv
is created. Here a row vector is an1
times2**cols
and a column vector is a2**rows
times1
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 innumpy
in order to obtain entries, rows, columns or submatrices. Then a complexnumpy
array (or a complex number) is returned as innumpy
. It is not possible to change the matrix via item assignment. So the easiest way to obtain a complex version of an instanceqs
of typeQStateMatrix
is to writeqs[:,:]
.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}^{m1} 2^k x_k, \; y = \sum_{k=0}^{n1} 2^k y_k, \, x_k, y_k \in \{0, 1 \}.\]Then
qs[x,y]
is the entry of matrixqs
with row index corresponding to the bit vector \((x_{m1},\ldots,x_0)\) and column index corresponding to the bit vector \((y_{n1},\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 positionj
. .Let
qs
be the state of shape(n0+n1)
, and letn = n0 + n1`. We change ``qs
to the following stateqs'
depending onn + nqb
qubits:qs'(x[n1],...,x[j],y[nqb1],...,y[0],x[j1]...,x[0])
=qs(x[n1],...,x[j],x[j1]...,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 positionj
.Let
qs
be the state of shape(n0+n1)
, and letn = n0 + n1`. We change ``qs
to the following stateqs'
depending onn + nqb
qubits:qs'(x[n1],...,x[j],y[nqb1],...,y[0],x[j1]...,x[0])
is equal toqs(x[n1],...,x[j],x[j1]...,x[0])
ify[0] = ... = y[nqb1] = 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 stateqs'
withqs'(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 vectorsj
andjc
must be zero. Otherwise thectrl not
operation is not unitary.Computing
qs.gate_ctrl_not(1 << jc, 1 << j)
, forjc != j
, corresponds to applying a controlled not gate to qubitj
contolled by qubitjc
. This operation is unitary if and only if the scalar product ofj
andjc
is zero.
 gate_ctrl_phi(v1, v2)¶
Apply controlled phase gates to a state
Change the state
qs
to a stateqs'
withqs'(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. Computingqs.gate_ctrl_phi(1 << j1, 1 << j2)
corresponds to applying a phasepi
gate to qubitj2
controlled by qubitj1
.
 gate_h(v)¶
Apply Hadamard gates to a state
Apply a Hadamard gate to all qubits
j
of the stateqs
(referred byself
) withv & (1 << j) == 1
. Aplying a Hadamard gate to gatej
changes a stateqs
to a state1/sqrt(2) * qs'
, whereqs'(..,x[j+1],x_j,x[j1],..)
=qs(..,x[j+1],0,x[j1],..)
+(1)**(x_j) * qs(..,x[j+1],1,x[j1],..)
. The result is not reduced.
 gate_not(v)¶
Apply not gates to a state
Change the state
qs
to a stateqs'
withqs'(x) = qs(x (+) v)
, where'(+)'
is the bitwise xor operation. The result is reduced if the input is reduced. Computingqs.gate_not(1 << j)
corresponds to negating qubitj
.
 gate_phi(v, phi)¶
Apply phase gate to a state
Change the state
qs
to a stateqs'
withqs'(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. Computingqs.gate_phi(1 << j, phi)
corresponds to applying a phase(phi * pi/2)
gate to qubitj
.
 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 ordere
fore <= max_order
, i.e.m.power(e)
is the unit matrix, thene
is returned. OtherwiseValueError
is raised.The function might also succeed if
e
is slighty larger thanmax_order
. It has run timeO(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 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 matrixFor a matrix
m
the power with exponente = 2
ism @ m
, and the power withe = 1
is the inverse matrix ofm
.
 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 complex2**n0
times2**n1
matrix.copy (
bool
) – A deep copy of the reshaped matrix is returned ifcopy
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]
is1
then the other value is calculated from the sumself.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 letn = n0 + n1`. We change ``qs
to the following stateqs'
depending onn  nqv
qubits:qs'(x[n'1],...,x[0])
is equal toqs(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 postionj
to0
.Let
qs
be the state of shape(n0+n1)
, and letn = n0 + n1`. We change ``qs
to the following stateqs'
depending onn
qubits:qs'(x[n1],...,x[0]) is equal to qs(x[n1],...,x[0])
ifx[j] = ... = x[j+nqb1] = 0
and equal to zero otherwise. We do not change the shape ofqs
.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 placeIf the state matrix
qs
has shape(0,n)
or(n,0)
we rotate the qubits ofqs
in place as follows:For
n0 <= i < n0 + nrot
we map qubiti
to qubitn0 + (i + rot) % nrot
. E.g.nrot = 3, rot = 1, n0 = 0
means qubits are mapped as0>1, 1>2, 2>0
.Here the entries of the state matrix are labelled by bit vectors of length
n
. Letqs(x[0],...,x[n1])
be the entry of the state matrix corresponding to the bit vector(x[n1],...,x[0])
.Then the function changes
qs to qs'
withqs'(...,x[start+nrot],y[nrot1],...,y[0],x[start1],...)
=qs(...,x[start+nrot],z[nrot1],...,z[0],x[start1],...)
, wherez[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 lengthn0 + n1
, with then1
highest bits corresponding to the rows of the matrix, and then0
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 complex2**nrows
times2**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 methodshow()
.
 sumup(j, nqb, copy=True)¶
Sum up
nqb
qubits starting at positionj
.Let
qs
be the state of shape(n0+n1)
, and letn = n0 + n1
. We changeqs
to the following stateqs'
depending onn  nqb
qubits:qs'(x[n1],...,x[j+nqb],x[j1],...,x[0])
=sum_{x[j+nqb1],...,x[j]} qs1(x[nn11],...,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.
 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 placeWe label the entries of the state matrix
qs
by bit vectors and defineqs(x[n1],...,x[0])
, withn = n0 + n1
,(n0, n1) = qs.shape
as in methodrot_bits
.We exchange qubit
j
with argument qubitj + sh
of the state, if bitj
ofmask
is set. If bitj
ofmask
is set then bitj + sh
ofmask
must not be set. Nomask
bit at position >=n  sh
may be set.E.g.
qs.qstate12_xch_bits(1, 0x11)
changes the state matrixqs
to a state matrixqs'
withqs'(...,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 a2**nqb
times2**nqb
unit matrix.
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/quantph/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)
J. H. Conway. A simple construction of the FischerGriess monster group. Inventiones Mathematicae, 1985.
 CCN+85(1,2,3,4)
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. SpringerVerlag, New York, 3rd edition, 1999. ISBN 0387985859.
 Iva99
A. A. Ivanov. Geometry of Sporadic Groups I, Petersen and Tilde Geometries. Cambridge University Press, June 1999. ISBN 0521413621.
 Iva09(1,2)
A. A. Ivanov. The Monster Group and Majorana Involutions. Cambridge University Press, April 2009. ISBN 0521889944.
 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.
 Sey20(1,2,3,4,5,6,7,8,9,10)
M. Seysen. A computerfriendly construction of the monster. arXiv eprints, pages arXiv:2002.10921, February 2020. arXiv:2002.10921.
 Wil03(1,2,3)
R. Wilson. Computing in the monster. In Group, Combinatorics & Geometry, Durham 2001, 327–337. World Scientific Publishing, 2003.
 Wil13
R. A. Wilson. The Monster and blackbox groups. arXiv eprints, pages arXiv:1310.5016, October 2013. arXiv:1310.5016.