$\newcommand{\K}{\mathbb{K}}$
Nicolas M. Thiéry
LRI, Université Paris Sud
View the live slides on binder: https://tinyurl.com/swavl3h
Extending representation theory from finite groups to finite semigroups brings interesting challenges, combinatorics, and applications. Almost a decade ago, I proposed an algorithm to compute the Cartan Matrix of a semigroup algebra -- a combinatorial invariant that contains information on how projective modules are built from simple modules. It boils down to computing with finite semigroups, characters of groups, and combinatorics. Despite this relative simplicity, and much to my embarrassment, a full production-grade implementation is only finally in reach.
In this talk, I will report on ongoing joint work with my PhD student Balthazar Charles to implement this algorithm and adapt it to modular representations, and use this occasion to illustrate the evolution of our computational landscape toward an ecosystem of interoperable software, thanks to large scale collaborations.
Balthazar is starting a PhD in modular representation theory of semigroups
Representation theory: also a tool for studying processes
Example: Splitting the state space of a large discrete Markov chain
Life is imperfect: many processes have irreversible steps!
Example: the Tsetlin library
Motto: reduce to the angels: group theory, combinatorics, linear algebra
Algorithm from finite dimensional algebras:
$\Longrightarrow$ Linear algebra on $\K S$, if not $End(\K S)$
Intractable for $\#S = 31103$ (bihecke monoid of type $A_5$)
Basic insight (T. 2010):
Algorithm:
Pros:
Implementation:
Question: How to proceed?
That's what happens in the tech industry: a single player takes it all (Amazon, AirBnB, Uber, ...)
Why not for us?
Let's reimplement everything in C++, Magma, GAP, Sage, Julia, Mathematica your favorite system
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__)
#Partitions.options.convention="French"
%display unicode_art
tensor.symbol = " ⊗ "
%run style/odk.py
T3 = mygap.FullTransformationSemigroup(3)
graph = T3.cayley_graph()
graph.set_latex_options(format="dot2tex")
view(graph)
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)
FrancyWidget(value=<networkx.classes.digraph.DiGraph object at 0x7f44bb028898>)
T5 = mygap.FullTransformationSemigroup(5)
T5.cardinality()
3125
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 ] )>
G = d_classes[1].schutzenberger_group()
G
Group([ (1,2,3,4), (1,2) ])
G = d_classes[1].schutzenberger_group()
G
Group([ (1,2,3,4), (1,2) ])
reps = G.irreducible_representations(GF(3))
for rho in reps:
display([matrix(rho(g).gap()) for g in G.group_generators()])
[ (2), (2) ]
[ (1), (1) ]
⎡ ⎛2 2 0⎞ ⎛2 0 0⎞ ⎤ ⎢ ⎜2 1 0⎟ ⎜0 2 2⎟ ⎥ ⎣ ⎝0 1 1⎠, ⎝0 0 1⎠ ⎦
⎡ ⎛0 1 2⎞ ⎛2 2 0⎞ ⎤ ⎢ ⎜2 2 1⎟ ⎜0 1 0⎟ ⎥ ⎣ ⎝2 2 0⎠, ⎝0 0 1⎠ ⎦
all( [ rho(g)*rho(h) == rho(g*h) for g in G for h in G ] )
True
A = T5.algebra(QQ); A
Algebra of <full transformation monoid of degree 5> over Rational Field
A.an_element() ^ 3
58*B + 72* Transformation( [ 4, 5, 1, 2, 3 ] ) B + 76*1 + 63* Transformation( [ 2, 3, 4, 5, 1 ] ) B + 74*B Transformation( [ 5, 1, 2, 3, 4 ] ) Transformation( [ 3, 4, 5, 1, 2 ] )
@semantic(gap="Group", variant="multiplicative")
class Groups:
class ParentMethods:
@semantic(gap="GeneratorsOfGroup", codomain=Family[Self])
@abstract_method
def group_generators(self):
pass
explore(G)
SageExplorer(children=(VBox(children=(ExplorerTitle(children=(MathTitle(value='Exploring: Group([ (1,2,3,4), (…
StandardTableaux(10).random_element()
┌───┬────┬───┬───┐ │ 1 │ 4 │ 5 │ 9 │ ├───┼────┼───┴───┘ │ 2 │ 7 │ ├───┼────┤ │ 3 │ 10 │ ├───┼────┘ │ 6 │ ├───┤ │ 8 │ └───┘
Sym = SymmetricFunctions(QQ['t']);
s = Sym.s()
s[3,1].coproduct()
1 ⊗ s + s ⊗ s + s ⊗ s + s ⊗ s + s ⊗ s + s ⊗ s + ┌┬┬┐ ┌┐ ┌┬┐ ┌┐ ┌┬┬┐ ┌┐ ┌┬┐ ┌┬┐ ┌┐ ┌┬┐ ┌┬┐ ├┼┴┘ └┘ ├┼┘ └┘ └┴┴┘ ├┤ └┴┘ └┴┘ ├┤ └┴┘ └┴┘ └┘ └┘ └┘ └┘ s ⊗ s + s ⊗ s + s ⊗ 1 ┌┬┐ ┌┐ ┌┬┬┐ ┌┐ ┌┬┬┐ ├┼┘ └┘ └┴┴┘ └┘ ├┼┴┘ └┘ └┘
@interact
def f(p1 = Partition([2,1])._widget_()):
return s[p1].coproduct()
Interactive function <function f at 0x7f44b8ddd730> with 1 widget p1: GridViewWidget(value=[2, 1], children=…
list(RibbonTableaux([[5,4,3],[2,1]], [2,1], 3))
⎡ . . 0 0 0 . . 1 0 0 . . 0 0 0 ⎤ ⎢ . 0 0 2 . 0 0 0 . 1 0 1 ⎥ ⎣ 1 0 1 , 1 0 2 , 2 0 0 ⎦
Sym.llt(3)
level 3 LLT polynomials over Univariate Polynomial Ring in t over Rational Field
Complete description of the environment:
FROM registry.gitlab.com/sagemath/sage/sagemath-dev:9.0-py3
RUN sudo apt-get update && sudo apt-get -qy install graphviz build-essential git g++ && sudo apt-get clean
RUN sage -i gap_packages && rm -rf /home/sage/sage/upstream
RUN sudo apt-get update && sudo apt-get -qq install -y curl \
&& curl -sL https://deb.nodesource.com/setup_10.x | sudo -E bash - \
&& sudo apt-get install -yq nodejs && sudo npm install npm@latest -g
RUN sage -pip install --no-cache-dir --upgrade ipywidgets
RUN sage -pip install --no-cache-dir dot2tex
RUN sage -pip install --no-cache-dir RISE
RUN sage -pip install --no-cache-dir nbdime
#RUN sage -pip install --no-cache-dir cppyy
RUN sage -pip install --no-cache-dir git+https://github.com/nthiery/sage-gap-semantic-interface/
RUN sage -pip install --no-cache-dir git+https://github.com/nthiery/sage-semigroups/
RUN sage -pip install --no-cache-dir git+https://github.com/zerline/francy-widget/
RUN sage -pip install --no-cache-dir git+https://github.com/sagemath/sage-combinat-widgets/@develop
#RUN sage -pip install --no-cache-dir git+https://github.com/sagemath/sage-combinat-widgets/@master
RUN sage -pip install --no-cache-dir git+https://github.com/sagemath/sage-explorer/@develop
Combining many different building blocks
Hard but Doable
What it takes
Shameless plug:
Lesson learned from OpenDreamKit:
A few Research Software Engineers can make a major impact
We need to do something to secure funding and career paths