Tutorial: Implementing Algebraic Structures#

Author: Nicolas M. Thiéry <nthiery at users.sf.net>, Jason Bandlow <jbandlow@gmail.com> et al.

This tutorial will cover four concepts:

endowing free modules and vector spaces with additional algebraic structure
defining morphisms
defining coercions and conversions
implementing algebraic structures with several realizations

At the end of this tutorial, the reader should be able to reimplement by himself the example of algebra with several realizations:

Sage

sage: Sets().WithRealizations().example()
The subset algebra of {1, 2, 3} over Rational Field

Python

>>> from sage.all import *
>>> Sets().WithRealizations().example()
The subset algebra of {1, 2, 3} over Rational Field

Namely, we consider an algebra \(A(S)\) whose basis is indexed by the subsets \(s\) of a given set \(S\). \(A(S)\) is endowed with three natural basis: F, In, Out; in the first basis, the product is given by the union of the indexing sets. The In basis and Out basis are defined respectively by:

\[In_s = \sum_{t\subset s} F_t \qquad F_s = \sum_{t\supset s} Out_t\]

Each such basis gives a realization of \(A\), where the elements are represented by their expansion in this basis. In the running exercises we will progressively implement this algebra and its three realizations, with coercions and mixed arithmetic between them.

This tutorial heavily depends on Tutorial: Using free modules and vector spaces. You may also want to read the less specialized thematic tutorial How to implement new algebraic structures.

Morphisms#

To better understand relationships between algebraic spaces, one wants to consider morphisms between them:

Sage

sage: A.module_morphism?                      # not tested
sage: A = MyCyclicGroupAlgebra(QQ, 2, prefix='a')
sage: B = MyCyclicGroupAlgebra(QQ, 6, prefix='b')
sage: A, B
(Jason's group algebra of Ring of integers modulo 2 over Rational Field, Jason's group algebra of Ring of integers modulo 6 over Rational Field)

Python

>>> from sage.all import *
>>> A.module_morphism?                      # not tested
>>> A = MyCyclicGroupAlgebra(QQ, Integer(2), prefix='a')
>>> B = MyCyclicGroupAlgebra(QQ, Integer(6), prefix='b')
>>> A, B
(Jason's group algebra of Ring of integers modulo 2 over Rational Field, Jason's group algebra of Ring of integers modulo 6 over Rational Field)

Sage

sage: def func_on_basis(g):
....:     r"""
....:     This function is the 'brain' of a (linear) morphism
....:     from A --> B.
....:     The input is the index of basis element of the domain (A).
....:     The output is an element of the codomain (B).
....:     """
....:     if g==1: return B.monomial(Zmod(6)(3))# g==1 in the range A
....:     else:    return B.one()

Python

>>> from sage.all import *
>>> def func_on_basis(g):
...     r"""
...     This function is the 'brain' of a (linear) morphism
...     from A --> B.
...     The input is the index of basis element of the domain (A).
...     The output is an element of the codomain (B).
...     """
...     if g==Integer(1): return B.monomial(Zmod(Integer(6))(Integer(3)))# g==1 in the range A
...     else:    return B.one()

We can now define a morphism that extends this function to \(A\) by linearity:

Sage

sage: phi = A.module_morphism(func_on_basis, codomain=B)
sage: f = A.an_element()
sage: f
2*a[0] + 2*a[1]
sage: phi(f)
2*b[0] + 2*b[3]

Python

>>> from sage.all import *
>>> phi = A.module_morphism(func_on_basis, codomain=B)
>>> f = A.an_element()
>>> f
2*a[0] + 2*a[1]
>>> phi(f)
2*b[0] + 2*b[3]

Exercise#

Define a new free module In with basis indexed by the subsets of \(S\), and a morphism phi from In to F defined by

\[\phi(In_s) = \sum_{t\subset s} F_t\]

Coercions#

Once we have defined a morphism from \(X \to Y\), we can register it as a coercion. This will allow Sage to apply the morphism automatically whenever we combine elements of \(X\) and \(Y\) together. See http://sagemath.com/doc/reference/coercion.html for more information. As a training step, let us first define a morphism \(X\) to \(Y\), and register it as a coercion:

Sage

sage: def triang_on_basis(p):
....:     return Y.sum_of_monomials(mu for mu in Partitions(sum(p)) if mu >= p)

sage: triang_on_basis([3,2])
y[[3, 2]] + y[[4, 1]] + y[[5]]
sage: X_to_Y = X.module_morphism(triang_on_basis, triangular='lower', unitriangular=True, codomain=Y)
sage: X_to_Y.<tab>                            # not tested
sage: X_to_Y.register_as_coercion()

Python

>>> from sage.all import *
>>> def triang_on_basis(p):
...     return Y.sum_of_monomials(mu for mu in Partitions(sum(p)) if mu >= p)

>>> triang_on_basis([Integer(3),Integer(2)])
y[[3, 2]] + y[[4, 1]] + y[[5]]
>>> X_to_Y = X.module_morphism(triang_on_basis, triangular='lower', unitriangular=True, codomain=Y)
>>> X_to_Y.<tab>                            # not tested
>>> X_to_Y.register_as_coercion()

Now we can not only convert elements from \(X\) to \(Y\), but we can also do mixed arithmetic with these elements:

Sage

sage: Y(x[Partition([3,2])])
y[[3, 2]] + y[[4, 1]] + y[[5]]
sage: Y([2,2,1]) + x[Partition([2,2,1])]
2*y[[2, 2, 1]] + y[[3, 1, 1]] + y[[3, 2]] + y[[4, 1]] + y[[5]]

Python

>>> from sage.all import *
>>> Y(x[Partition([Integer(3),Integer(2)])])
y[[3, 2]] + y[[4, 1]] + y[[5]]
>>> Y([Integer(2),Integer(2),Integer(1)]) + x[Partition([Integer(2),Integer(2),Integer(1)])]
2*y[[2, 2, 1]] + y[[3, 1, 1]] + y[[3, 2]] + y[[4, 1]] + y[[5]]

Exercise#

Use the inverse of phi to implement the inverse coercion from F to In. Reimplement In as an algebra, with a product method making it use phi and its inverse.

Implementing algebraic structures with several realizations#

We now return to the subset algebra and use it as an example to show how to implement several different bases for an algebra with automatic coercions between the different bases. We have already implemented three bases for this algebra: the F, In, and Out bases, as well as coercions between them. In real calculations it is convenient to tie these parents together by implementing an object A that models the abstract algebra itself. Then, the parents F, In and Out will be realizations of A, while A will be a parent with realizations. See Sets().WithRealizations for more information about the expected user interface and the rationale.

Here is a brief template highlighting the overall structure:

class MyAlgebra(Parent, UniqueRepresentation):
    def __init__(self, R, ...):
        category = Algebras(R).Commutative()
        Parent.__init__(self, category=category.WithRealizations())
        # attribute initialization, construction of the morphisms
        # between the bases, ...

    class Bases(Category_realization_of_parent):
        def super_categories(self):
            A = self.base()
            category = Algebras(A.base_ring()).Commutative()
            return [A.Realizations(), category.Realizations().WithBasis()]

        class ParentMethods:
            r"""Code that is common to all bases of the algebra"""

        class ElementMethods:
            r"""Code that is common to elements of all bases of the algebra"""

    class FirstBasis(CombinatorialFreeModule, BindableClass):
        def __init__(self, A):
            CombinatorialFreeModule.__init__(self, ..., category=A.Bases())

        # implementation of the multiplication, the unit, ...

    class SecondBasis(CombinatorialFreeModule, BindableClass):
        def __init__(self, A):
            CombinatorialFreeModule.__init__(self, ..., category=A.Bases())

        # implementation of the multiplication, the unit, ...

The class MyAlgebra implements a commutative algebra A with several realizations, which we specify in the constructor of MyAlgebra. The two bases classes MyAlgebra.FirstBasis and MyAlgebra.SecondBasis implement different realizations of A that correspond to distinguished bases on which elements are expanded. They are initialized in the category MyAlgebra.Bases of all bases of A, whose role is to factor out their common features. In particular, this construction says that they are:

realizations of A
realizations of a commutative algebra, with a distinguished basis

Note

There is a bit of redundancy here: given that A knows it is a commutative algebra with realizations the infrastructure could, in principle, determine that its realizations are commutative algebras. If this was done then it would be possible to implement Bases.super_categories by returning:

[A.Realizations().WithBasis()]

However, this has not been implemented yet.

Note

Inheriting from BindableCass just provides syntactic sugar: it makes MyAlgebras().FirstBasis() a shorthand for MyAlgebras.FirstBasis(MyAlgebras().FirstBasis()) (binding behavior). The class Bases inherits this binding behavior from Category_realization_of_parent , which is why we can write MyAlgebras().Bases instead of MyAlgebras.Bases(MyAlgebras())

Note

More often than not, the constructors for all of the bases will be very similar, if not identical; so we would want to factor it out. Annoyingly, the natural approach of putting the constructor in Bases.ParentMethods does not work because this is an abstract class whereas the constructor handles the concrete implementation of the data structure. Similarly, it would be better if it was only necessary to specify the classes the bases inherit from once, but this can’t code go into Bases for the same reason.

The current recommended solution is to have an additional class Basis that factors out the common concrete features of the different bases:

...

class Basis(CombinatorialFreeModule, BindableClass):
    def __init__(self, A):
        CombinatorialFreeModule.__init__(self, ..., category=A.Bases())

class FirstBasis(Basis):
    ...

class SecondBasis(Basis):
    ...

This solution works but it is not optimal because to share features between the two bases code needs to go into two locations, Basis and Bases, depending on whether they are concrete or abstract, respectively.

We now urge the reader to browse the full code of the following example, which is meant as a complete template for constructing new parents with realizations:

Sage

sage: A = Sets().WithRealizations().example(); A
The subset algebra of {1, 2, 3} over Rational Field

sage: A??                                     # not implemented

Python

>>> from sage.all import *
>>> A = Sets().WithRealizations().example(); A
The subset algebra of {1, 2, 3} over Rational Field

>>> A??                                     # not implemented

Review#

Congratulations on reading this far!

We have now been through a complete tour of the features needed to implement an algebra with several realizations. The infrastructure for realizations is not tied specifically to algebras; what we have learned applies mutatis mutandis in full generality, for example for implementing groups with several realizations.

Tutorial: Implementing Algebraic Structures#

Subclassing free modules and including category information#

Review#

Exercises#

Morphisms#

Exercise#

Diagonal and Triangular Morphisms#

Exercise#

Coercions#

Exercise#

A digression: new bases and quotients of symmetric functions#

Implementing algebraic structures with several realizations#

Review#