/finite-algebra

♾ (prototype of) library for finite algebra

Primary LanguagePythonGNU Lesser General Public License v3.0LGPL-3.0

finite-algebra

This is (a prototype of) a Python library for finite algebra group theory, which encapsulates elements of a structure as instances of an immutable class, and allows easy and expressive operation with them.

It's designed to be both practical and expressive to use as a calculator (for playing and experiments), and also high-quality and ergonomical enough for use in production code. I've attempted to keep code quality at a minimum, so that it can serve for learning purposes or as base for production code.

Priorities are: flexibility first, readability second, performance third (but we generally care about O(n) complexity).

Disclaimers:

This code is not safe for cryptography; operation time may depend on the values.

This project is mostly a proof-of-concept at this point and I don't anticipate having the energy to develop it further.

Table of contents

Examples

Rubik's cube

The Rubik's cube group can be defined as $(Z_3 \wr S_8) \times (Z_2 \wr S_{12})$ in mathematical notation, which is not too verbose to express using this library:

from groups import WreathProduct, DirectProduct, S8, S12, Z2, Z3

class Corners(WreathProduct):
    BOTTOM = Z3
    TOP = S8

class Edges(WreathProduct):
    BOTTOM = Z2
    TOP = S12

class Rubik(DirectProduct):
    PARTS = Corners, Edges

This is actually not exactly the Rubik's cube, but a supergroup 12 times as large, because it includes states that are reachable by reassembling the cube but not solvable through legal moves. The six legal moves (90-degree turns to each face of the cube), can be derived by first defining rotations to the whole cube:

c0, c1, cA = [0,0,0,0], [1,1,1,1], [1,-1,1,-1]

# 90-degree rotation of whole cube (except centers) around axis X and Y
X = Rubik(
    [ ([0,1,4,5], c0), ([3,2,7,6], c0) ],
    [ ([0,2,4,6], c1), ([1,9,5,8], c0), ([3,10,7,11], c0) ],
)
Y = Rubik(
    [ ([2,1,4,7], cA[::-1]), ([3,0,5,6], cA) ],
    [ ([2,9,4,10], c1), ([0,8,6,11], c1), ([3,1,5,7], c1) ],
)

...and then, defining the turn to the front face ($F$) and conjugating with the subgroup generated by these cube rotations to get turns to the other faces:

# 90-degree clockwise turn to the Front face
F = Rubik([ ([0,1,2,3], c0) ], [ ([0,1,2,3], c0) ])

# conjugating F by cube rotations yields turns to the other faces:
L, R, D, U, B = map(F.conj_by, (X, X.inv, Y, Y.inv, X**2))

We can then calculate the order of certain algorithms:

>>> (F * U * L * U.inv * L.inv * F.inv).order()
6
>>> (F * U).order()
105

Encode states of the cube as naturals:

>>> int(F * U * L * U.inv * L.inv * F.inv)
76973011623110116950

And decode back:

>>> Rubik[76973011623110116950] == F * U * L * U.inv * L.inv * F.inv
True

The default representation of group elements tries to be informative. For example, for this algorithm:

>>> F * U * L * U.inv * L.inv * F.inv
Rubik([ ([1,2], [1,1]), ([4,7], [0,1]) ], [ ([2,4,9], [0,1,1]) ])

we can learn that it:

  • swaps corners 1 and 2 + rotates at least one of them
  • swaps corners 4 and 7 + rotates at least one of them
  • cycles edges 2, 4, 9

The library doesn't provide fancy algorithms to determine generator sets, discover subgroups or solve cubes, though. It is meant to serve more like a base to implement this kind of stuff.

Status

Class structure

Right now there's only basic finite group theory. In particular:

  • Group: Base class & supporting metaclass

  • Common base groups, indexed by SIZE ($n$):

  • Constructions of groups from other groups:

    • DirectProduct: Direct product of an arbitrary amount of groups, with tuple shape

    • SemidirectProduct: (outer) left semidirect product of two groups

    • WreathProduct: Wreath product of two groups, with the top one being a (subgroup of a) symmetric group (inherits from SemidirectProduct)

  • Common application-specific groups:

    • CubeRot: Group of (proper) rotations of a cube (isomorphic to $S_4$, inherits from SymmetricGroup)

Group features

The base Group class provides a number of features to make elements idiomatic and expressive while reducing the amount of boilerplate required for subclasses, in a way similar to dataclass. These are:

  • Operator overloading (* for group operation)
  • Default ** implementation using exponentiation by squaring (with optional reduction using element order if possible)
  • The class itself implements the sequence protocol to enumerate and index elements by naturals
  • int() gets the index of an element; bool() tests for non-identity
  • Order of the group offered as ORDER property on class
  • Identity element offered as ID property on class
  • Elements are comparable, hashable and immutable (by default this is provided through the index, but there's a central _cmpkey method that is recommended to override)
  • Default behavior for repr(element) and str(element)
  • "Short syntax" system for concise expression of composite group elements
  • Optional order() API for groups that offer an efficient way to calculate the order of an element
  • Convenience shortcuts: conj, conj_by, comm to compute conjugate and commutator elements
  • Automagical group creation for common groups

The SymmetricGroup class supports some more features, such as:

  • Cycle composition / decomposition (used by default for representations)
  • Sign, cycle type, order computation
  • Efficient exponentiation

The WreathProduct class supports cycle decomposition as well, annotating each cycle with the associated bottom elements. It uses this for efficient order calculation as well.

The CubeRot class is a specialization of SymmetricGroup with SIZE=4 that represents elements in terms of cube face + orientation, and allows splitting elements into these two.

Many of these features are introduced in Getting started below. Refer to the code of the Group and GroupMeta classes for more info, especially if you're planning to implement your own group from scratch.

Compatibility

We're targeting Python 3.7 (for among other things, __getname__ module support), but we're not there yet. For now Python 3.10 is needed.

Typing support: 🤡. Yes, there are annotations all over the code and they've helped catch bugs, but they are often incorrect and sometimes deferred to Any because I don't think Python's type system is powerful enough to express the abstraction required by this library (in particular, generic type arguments that are resolved at subclass time rather than instance time). If you're a Python wizard and want to fix this, contributions are very welcome.

There's a lot of FIXMEs and some hacks, mostly performance-related though.

Getting started

Element enumeration / indexing

Each group is a class that ultimately inherits from Group. For example, the S3 class implements the symmetric group over 3 elements, written $S_3$:

>>> from groups import S3
>>> S3
<class 'groups.S3'>

Elements of the group are instances of that class. The class is actually a sequence of all its elements, so we can iterate over them:

>>> for element in S3: print(repr(element))
S3.ID
S3.from_cycles([1,2])
S3.from_cycles([0,1])
S3.from_cycles([0,1,2])
S3.from_cycles([0,2,1])
S3.from_cycles([0,2])

And we can use the ORDER class property to count them. This is faster than len(list(S3)) because it computes the number directly:

>>> S3.ORDER
6

Note: Since it's a sequence, len(S3) is also supported. However ORDER should be preferred if possible, since for large groups it can exceed the maximum size of a sequence and raise OverflowError. Indexing and iteration still work normally in these cases.

We can also obtain an element by its index, as you'd expect:

>>> S3[3]
S3.from_cycles([0,1,2])

And we can obtain the index of an element by converting to an int:

>>> int(S3[3])
3

This is useful for compact serialization, among other things.

In technical terms, all Group subclasses are required to implement a bijection from the group to the naturals. Which particular bijection is implemented (meaning, the order in which the elements are iterated / mapped to indexes) depends on the implementation, but it is guaranteed all elements are mapped to one (unique) index in the sequence.

It is conventional to map the identity element (S3.ID) to index 0 (S3[0]), but this is again not a guarantee.

Working with elements

Two elements can be operated with the * operator:

>>> a = S3.from_cycles([0,1,2])
>>> b = S3.from_cycles([1,2])
>>> a * b
S3.from_cycles([0,1])

The inverse of an element can be obtained through its inv property or with ** -1:

>>> a.inv
S3.from_cycles([0,2,1])
>>> a ** -1
S3.from_cycles([0,2,1])

The identity element of the group can be obtained through the ID property of the class, as you saw above:

>>> S3.ID * a == a
True
>>> a * S3.ID == a
True

The truth value of an element is False for the identity and True for every other element:

>>> bool(S3.ID)
False
>>> bool(a)
True

Elements can also be compared; this is expected to be consistent with the bijection, so comparing two elements is equivalent to comparing their indexes:

>>> a >= b
True
>>> int(a) >= int(b)
True

Elements are also hashable, which means you can use them as keys in a set or dictionary:

>>> { S3.ID: 'identity', b: 'my favorite element' }
{S3.ID: 'identity', S3.from_cycles([1,2]): 'my favorite element'}

Elements can also be exponentiated to an integer; this is often faster than multiplying N instances of the element, as it uses group-specific optimizations if possible:

>>> a ** -22340981
S3.from_cycles([0,1,2])

Most groups provide an efficient way to compute the order of an element, through the order() method:

>>> a.order()
3

Other operations include obtaining conjugate and commutator elements, see methods conj, conj_by, comm for more info.

Using SymmetricGroup

The symmetric group over N elements is a group made of all the permutations of a set of N elements. This is implemented through the SymmetricGroup class, which is a non-final group class. This means you can't use it directly:

>>> from groups import SymmetricGroup
>>> SymmetricGroup
<class 'groups.SymmetricGroup'>
>>> list(SymmetricGroup)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "groups.py", line 103, in __iter__
    return cls._enumerate()
  File "groups.py", line 578, in _enumerate
    options.append(value.pop())
AttributeError: type object 'SymmetricGroup' has no attribute 'SIZE'

Instead, you need to subclass it and define SIZE (the amount of elements of the set) on your subclass. For example, the symmetric group over 10 elements can be defined as follows:

>>> class MyGroup(SymmetricGroup):
...    SIZE = 10

This also gives you a chance to override methods to customize the default representation of elements, or other properties.

For now though we'll keep working with S3, which is a subclass of SymmetricGroup with SIZE = 3 defined by the library (see automagical group creation below).

Elements can be constructed directly by feeding the permutation tuple to the constructor:

>>> S3((0, 1, 2))
S3.ID
>>> S3((1, 0, 2))
S3.from_cycles([0,1])

And the permutation tuple can be obtained back through the value property:

>>> b.value
(0, 2, 1)

The tuple specifies the permutation in one-line notation: each slot has the zero-based index of the slot it's sent to. They're the "raw", natural representation of a permutation. They're fine for computers but not helpful to understand what the permutation does; for this it's better to separate the permutation into disjoint cycles:

>>> b.cycles()
[[1, 2], [0]]

This tells us the permutation swaps slots 1 and 2, while leaving 0 unchanged (fixed). The reverse operation, the from_cycles() class method, allows us to construct a permutation from a series of cycles:

>>> S3.from_cycles([1, 2], [0]) == a
True

We can omit fixed points from the list of cycles for brevity, if we wish:

>>> S3.from_cycles([1, 2]) == a
True

Because this notation is more informative to humans, it's the notation used by repr() of an element, as we've already seen.

This is a common convention for all groups: the class constructor usually accepts a "raw" representation of the element (in this case, a permutation tuple) and does little more than wrap it inside the element. The wrapped value is then often accessible under .value. In case alternative, more elaborated ways to express an element are wanted, they're offered as methods (in this case, cycles() and from_cycles()). repr() of an element tends to use these more informative representations where possible.

Finally, SymmetricGroup also exposes some other minor operations of interest, such as sign() to get the sign of the permutation. Refer to the class for more info.

Automagical group creation

The module defines a __getattr__ that will recognize accesses to certain name patterns and auto-create the group in the module. This is what allowed us to write:

from groups import S3

instead of:

from groups import SymmetricGroup

class S3(SymmetricGroup):
   SIZE = 3

With the added benefit that the created S3 lives in this module and the same class will be reused by everyone.

Right now the only supported pattern is PREFIX + NATURAL, with the following prefixes:

  • S<n>: SymmetricGroup
  • Z<n>: CyclicGroup

Composing groups using DirectProduct

A direct product is probably the simplest and most natural way to combine groups to get a new group. This is implemented through the DirectProduct class.

>>> from groups import DirectProduct, S5

Like SymmetricGroup, it is a non-final group class. But instead of specifying SIZE, here we need to specify PARTS as a tuple of the groups to combine:

>>> class MyGroup2(DirectProduct):
...   PARTS = S5, S3

The elements of MyGroup2 are, conceptually, pairs with the first item being an element of S5, and the second item an element of S3:

>>> c = MyGroup2(S5.ID, a)
>>> c
MyGroup2(ID, [[0,1,2]])

Simlar to NamedTuple, DirectProduct allows MyGroup2 to behave like a tuple:

>>> len(c)
2
>>> c[0]
S5.ID
>>> c[1]
S3.from_cycles([0,1,2])
>>> tuple(c)
(S5.ID, S3.from_cycles([0,1,2]))

Although if we need to, we can access its underlying tuple directly through the value property like we did on SymmetricGroup:

>>> c.value
(S5.ID, S3.from_cycles([0,1,2]))

Otherwise, MyGroup2 acts like any other Group. Multiplying two elements simply multiplies each part (S5 and S3) separately. And its elements are enumerated right-to-left, as itertools.product() would do:

>>> for element in MyGroup2: print(repr(element))
MyGroup2(ID, ID)
MyGroup2(ID, [[1,2]])
MyGroup2(ID, [[0,1]])
MyGroup2(ID, [[0,1,2]])
MyGroup2(ID, [[0,2,1]])
MyGroup2(ID, [[0,2]])
MyGroup2([[3,4]], ID)
MyGroup2([[3,4]], [[1,2]])
MyGroup2([[3,4]], [[0,1]])
MyGroup2([[3,4]], [[0,1,2]])
MyGroup2([[3,4]], [[0,2,1]])
MyGroup2([[3,4]], [[0,2]])
MyGroup2([[2,3]], ID)
MyGroup2([[2,3]], [[1,2]])
[...]

There's something special about these representations, though. It uses a system called short syntax that lets us write:

MyGroup2([[0,1], [3,4]], ID)

instead of:

MyGroup2(S5.from_cycles([0,1], [3,4]), S3.ID)

The way this works is that DirectProduct's constructor will call S5.short_value() with the first argument, and S3.short_value() with the second. short_value() will return its argument unchanged if it's already an instance of the class, and will otherwise attempt to coerce the value into an element of the group in several ways.

One of them is the special ID object that can be imported from groups. For most groups, if short_value() detects it was fed this dummy object, it will return Group.ID; otherwise it will attempt to construct an element directly with this value. This means we could've also written MyGroup2((1,0,2,4,3), ID) or equivalently MyGroup2(S5((1,0,2,4,3)), ID).

But for SymmetricGroup, there's an additional supported syntax: if the value is a list, it will pass its items to from_cycles() to construct the element. This is what you see above.

This system allows us to omit the name of the class (and a lengthy method call in this case) in contexts where the expected class (group) is known. It comes with a reverse operation called short_repr() which formats the element into short syntax, which DirectProduct.__repr__ uses to produce the output you see above.

Implementing custom groups

Sometimes it may be necessary to implement a group from scratch. To start we need to subclass Group and define the constructor (+ getters), as usual:

from groups import Group

class MyFancyGroup(Group):
    def __init__(self, value):
        # TODO: validate `value`
        self._value = value

    @property
    def value(self):
        return self._value

Then define the three core methods of the group: the _id() classmethod to obtain the identity element, _mul() to operate two elements, and the inv property to invert an element:

    @classmethod
    def _id(cls) -> 'MyFancyGroup':
        return cls(...) # TODO

    def _mul(self, other: 'MyFancyGroup') -> 'MyFancyGroup':
        # (`other` has already been validated to be an instance of this class)
        return type(self)(...) # TODO

    @property
    def inv(self) -> 'MyFancyGroup':
        return type(self)(...) # TODO

It is also necessary to provide the bijection with the naturals by implementing _index() and _fromindex() (map elements to naturals and viceversa) and _order() (returns the amount of elements of the group):

    def _index(self) -> int:
        return ... # TODO: must return an integer 0 <= n < ORDER

    @classmethod
    def _fromindex(cls, index: int) -> 'MyFancyGroup':
        # (`index` has already been validated to be an integer 0 <= n < ORDER)
        return ... # TODO

    @classmethod
    def _order(cls) -> int:
        return ... # TODO: amount of group elements

This is all that's needed for a compliant group class; however some methods are recommended to be overriden for ergonomics and performance. By default, elements of the groups will be formatted using their index (MyFancyGroup[2349]) but it's strongly recommended to provide informative formatting. Sometimes using a call to the constructor (MyFancyGroup(<value>)) is enough: to do this, override value_repr() to return a representation of <value> to fill in, e.g.:

    def value_repr(self) -> str:
        return repr(self.value)

This causes the default implementation of __repr__ to format a call to the constructor. If more sophisticated formatting is needed, __repr__ can be overriden directly. To customize the way short syntax works for this group, you may want to override short_repr and short_value. See the Group class source code for more details.

You should also implement order() if there's an efficient way to calculate the order of elements of the group:

    def order(self) -> int:
        return ... # smallest positive `n` such that `self ** n == ID`

All missing optional methods are for performance. The group uses _index() for comparison and hashing, but this is often inefficient because a compact index isn't necessary for those purposes. In this case you can override _cmpkey() to delegate comparison and hashing ops to something other than the index, e.g.:

    def _cmpkey(self):
        return self.value

If you do this, make sure the returned value compares consistently with the bijection you defined above. If you want to use something other than _cmpkey() for hashing (e.g. to skip fields for the hash) you may also override __hash__().

Another useful optimization may be to override _pow() if the group allows exponentiation in a more efficient way than the default exponentiation by squaring.