Use case: modular representation theory of semigroups

Nicolas M. Thiéry
LRI, Université Paris Sud


Run this live on binder:


Scenario

Balthazar is starting a PhD in modular representation theory of semigroups

Mathematical context

  • Representation theory of groups: a grand old topic; 10k+ papers in a century
  • Representation theory of the symmetric group $\mathfrak{S}_n$: beautiful combinatorics
  • Modular representation theory of groups: 1k+ papers in the last 50 years
  • Representation theory of semigroups: dozens of papers in the last decades
  • Motto of semigroup theory: reduce to combinatorics + group theory

Strategy

  • Implement a algorithm of 2010 in full generality
    Computing the Cartan Matrix of a semigroup
  • Adapt this algorithm to the modular</modular> case
  • Explore the representation theory of the transformation semigroup $T_n$
    beautiful combinatorics?

Needs

  • Program and explore
  • Take advantage of all the existing computational tools

Balthazar's Virtual Research Environment

Built from many tools in our toolkit :

In [1]:
import sage_annotations
from mygap import mygap
mygap.LoadPackage("Semigroups");

import sage_semigroups
import sage_combinat_widgets

from   sage_explorer import explore
from sage_explorer.sage_explorer import Settings
Settings.add_property('cardinality', predicate=Groups().Finite().__contains__)
Settings.add_property('conjugacy_classes', predicate=Groups().Finite().__contains__)
Settings.add_property('multiplication_table', predicate=Groups().Finite().__contains__)

%display unicode_art
tensor.symbol = " ⊗ "
%run style/odk.py

Semigroup theory</a>

In [2]:
T5 = mygap.FullTransformationSemigroup(5)
In [3]:
T3 = mygap.FullTransformationSemigroup(3)
graph = T3.cayley_graph()
graph.set_latex_options(format="dot2tex")
view(graph)
In [ ]:
from francy_widget import FrancyWidget
from networkx import DiGraph
g = DiGraph()
g.add_edges_from([(e[0], e[1]) for e in graph.edges()])
FrancyWidget(g)
In [4]:
T5.cardinality()
Out[4]:
3125
In [5]:
d_classes = T5.d_classes()
for d_class in d_classes:
    print(d_class)
<Green's D-class: IdentityTransformation>
<Green's D-class: Transformation( [ 1, 2, 3, 4, 1 ] )>
<Green's D-class: Transformation( [ 1, 1, 2, 3, 1 ] )>
<Green's D-class: Transformation( [ 3, 1, 3, 1, 3 ] )>
<Green's D-class: Transformation( [ 1, 1, 1, 1, 1 ] )>
In [6]:
G = d_classes[1].schutzenberger_group()
G
Out[6]:
Group([ (1,2,3,4), (1,2) ])

Modular representation of groups

In [7]:
reps = G.irreducible_representations(GF(3))
for rho in reps:
    display([matrix(rho(g).gap()) for g in G.group_generators()])
[ (1), (1) ]
[ (2), (2) ]
⎡ ⎛2 1 0⎞  ⎛0 0 1⎞ ⎤
⎢ ⎜1 1 0⎟  ⎜0 2 0⎟ ⎥
⎣ ⎝1 0 1⎠, ⎝1 0 0⎠ ⎦
⎡ ⎛2 1 1⎞  ⎛0 1 1⎞ ⎤
⎢ ⎜0 0 1⎟  ⎜1 0 2⎟ ⎥
⎣ ⎝2 0 0⎠, ⎝0 0 1⎠ ⎦
In [8]:
all( [ rho(g)*rho(h) == rho(g*h) for g in G for h in G ] )
Out[8]:
True

Why is that impressive?

Diving behind the scene

  • Sage uses GAP for groups
  • GAP uses MeatAxe (C library)
    parallelism of MeatAxe64
  • Sage uses GAP's Semigroup packages for semigroups
    J. Mitchell et al.
  • Semigroups uses libsemigroups (C++ library)
    J. Mitchell, inspired by Semigroupe of J.-E. Pin
  • libsemigroups uses HPC Combi
    F. Hivert , with feedback from J. Mitchell

Low level interface to GAP: libgap

One of ODK case studies for interfacing with other systems

  • libgap used to be a fragile hard to maintain fork of GAP
    Volker Braun

  • libgap is now a standard feature of GAP
    M. Horn, A. Konovalov , M. Pfeiffer , J. Demeyer , E. M. Bray , N. Thiéry , D. Pasechnik
    GAP-Sage Days 2016, 2017, 2018

  • Made possible by GAP's build system refactoring
    M. Horn, A. Konovalov , ...

  • A major step for sustainable packaging of GAP and Sage

libsemigroups</a>

One of ODK case study for extracting independent low-level libraries C++

  • libsemigroups API design:
    J. Mitchell with F. Hivert and N. Thiéry: Cernay 2017, 2018

  • libsemigroups Python bindings
    J. Mitchell and N. Thiéry : Edinburgh, 2017, Cernay 2017, 2018

  • libsemibroups usable directly in Jupyter thanks to xeus-cling
    S. Corlay, J. Mabile, L. Gouarin

  • libsemigroups packaging
    J. Mitchell and N. Thiéry : Jupyter for Mathematics Workshop, Edinburgh, 2017

Sage-GAP lightweight Math-in-the-Middle interface

In action

In [9]:
A = T5.algebra(QQ); A
Out[9]:
Algebra of <full transformation monoid of degree 5> over Rational Field
In [10]:
A.an_element() ^ 3
Out[10]:
58*B                                    + 74*
    Transformation( [ 4, 5, 1, 2, 3 ] )      

B                                    + 72*B                                   
 Transformation( [ 3, 4, 5, 1, 2 ] )       Transformation( [ 2, 3, 4, 5, 1 ] )

 + 76*1 + 63*B
              Transformation( [ 5, 1, 2, 3, 4 ] )

How it works

  • Enriched libgap handles with
  • Semantic carried over using
  • Alignments provided as annotations

    @semantic(mmt="Group", variant="multiplicative")
      class Groups:
    
          class ParentMethods:
    
              @semantic(gap="GeneratorsOfGroup", codomain=Family[Self])
              @abstract_method
              def group_generators(self):
                  pass
    

That's not all!