$\newcommand{\K}{\mathbb{K}}$
Nicolas M. Thiéry
LRI, Université Paris Sud
View the live slides on binder: https://tinyurl.com/swavl3h
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)
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