{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Use case: modular representation theory of semigroups\n",
"\n",
"\n",
"\n",
"Nicolas M. Thiéry
\n",
"LRI, Université Paris Sud\n",
"
\n",
"\n",
"Run this live on binder:\n",
"\n",
"\n",
"\n",
"\n",
"
\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Scenario\n",
"\n",
"Balthazar is starting a PhD in modular representation theory of semigroups"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"### Mathematical context\n",
"- Representation theory of groups: a grand old topic; 10k+ papers in a century \n",
"- Representation theory of the symmetric group $\\mathfrak{S}_n$: beautiful combinatorics"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Modular representation theory of groups: 1k+ papers in the last 50 years"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Representation theory of semigroups: dozens of papers in the last decades"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Motto of semigroup theory: reduce to **combinatorics** + **group theory**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"### Strategy\n",
"- Implement a algorithm of 2010 in full generality
\n",
" Computing the Cartan Matrix of a semigroup\n",
"- Adapt this algorithm to the modular case\n",
"- Explore the representation theory of the transformation semigroup $T_n$
\n",
" beautiful combinatorics?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"### Needs\n",
"- **Program** and **explore**\n",
"- Take advantage of **all the existing computational tools**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Balthazar's Virtual Research Environment\n",
"\n",
"Built from many tools in our toolkit :"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import sage_annotations\n",
"from mygap import mygap\n",
"mygap.LoadPackage(\"Semigroups\");\n",
"\n",
"import sage_semigroups\n",
"import sage_combinat_widgets\n",
"\n",
"from sage_explorer import explore\n",
"from sage_explorer.sage_explorer import Settings\n",
"Settings.add_property('cardinality', predicate=Groups().Finite().__contains__)\n",
"Settings.add_property('conjugacy_classes', predicate=Groups().Finite().__contains__)\n",
"Settings.add_property('multiplication_table', predicate=Groups().Finite().__contains__)\n",
"\n",
"%display unicode_art\n",
"tensor.symbol = \" ⊗ \"\n",
"%run style/odk.py"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Semigroup theory"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"T5 = mygap.FullTransformationSemigroup(5)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"T3 = mygap.FullTransformationSemigroup(3)\n",
"graph = T3.cayley_graph()\n",
"graph.set_latex_options(format=\"dot2tex\")\n",
"view(graph)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from francy_widget import FrancyWidget\n",
"from networkx import DiGraph\n",
"g = DiGraph()\n",
"g.add_edges_from([(e[0], e[1]) for e in graph.edges()])\n",
"FrancyWidget(g)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3125"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"T5.cardinality()"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"\n",
"\n",
"\n",
"\n"
]
}
],
"source": [
"d_classes = T5.d_classes()\n",
"for d_class in d_classes:\n",
" print(d_class)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Group([ (1,2,3,4), (1,2) ])"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G = d_classes[1].schutzenberger_group()\n",
"G"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Modular representation of groups"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[ (1), (1) ]"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"[ (2), (2) ]"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"⎡ ⎛2 1 0⎞ ⎛0 0 1⎞ ⎤\n",
"⎢ ⎜1 1 0⎟ ⎜0 2 0⎟ ⎥\n",
"⎣ ⎝1 0 1⎠, ⎝1 0 0⎠ ⎦"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"⎡ ⎛2 1 1⎞ ⎛0 1 1⎞ ⎤\n",
"⎢ ⎜0 0 1⎟ ⎜1 0 2⎟ ⎥\n",
"⎣ ⎝2 0 0⎠, ⎝0 0 1⎠ ⎦"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"reps = G.irreducible_representations(GF(3))\n",
"for rho in reps:\n",
" display([matrix(rho(g).gap()) for g in G.group_generators()])"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"all( [ rho(g)*rho(h) == rho(g*h) for g in G for h in G ] )"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Why is that impressive?\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"### Diving behind the scene\n",
"- Sage uses GAP for groups"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- GAP uses MeatAxe (C library)
\n",
" parallelism of MeatAxe64 "
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Sage uses GAP's Semigroup packages for semigroups
\n",
" J. Mitchell et al."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Semigroups uses libsemigroups (C++ library)
\n",
" J. Mitchell, inspired by Semigroupe of J.-E. Pin"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- libsemigroups uses HPC Combi
\n",
" F. Hivert , with feedback from J. Mitchell"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Low level interface to GAP: libgap\n",
"One of ODK case studies for interfacing with other systems\n",
"\n",
"- libgap used to be a fragile hard to maintain fork of GAP
\n",
" Volker Braun\n",
" \n",
"- libgap is now a standard feature of GAP
\n",
" M. Horn, A. Konovalov , M. Pfeiffer , J. Demeyer , E. M. Bray , N. Thiéry , D. Pasechnik
\n",
" GAP-Sage Days 2016, 2017, 2018\n",
"\n",
"- Made possible by GAP's build system refactoring
\n",
" M. Horn, A. Konovalov , ...\n",
"\n",
"- A major step for sustainable packaging of GAP and Sage"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### libsemigroups\n",
"\n",
"One of ODK case study for extracting independent low-level libraries C++\n",
"\n",
"- libsemigroups API design:
\n",
" J. Mitchell with F. Hivert and N. Thiéry: Cernay 2017, 2018\n",
"\n",
"- libsemigroups Python bindings
\n",
" J. Mitchell and N. Thiéry : Edinburgh, 2017, Cernay 2017, 2018\n",
"\n",
"- libsemibroups usable directly in Jupyter thanks to xeus-cling
\n",
" S. Corlay, J. Mabile, L. Gouarin \n",
"\n",
"- libsemigroups packaging
\n",
" J. Mitchell and N. Thiéry : Jupyter for Mathematics Workshop, Edinburgh, 2017"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Sage-GAP lightweight Math-in-the-Middle interface\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"#### In action"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Algebra of over Rational Field"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = T5.algebra(QQ); A"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"58*B + 74*\n",
" Transformation( [ 4, 5, 1, 2, 3 ] ) \n",
"\n",
"B + 72*B \n",
" Transformation( [ 3, 4, 5, 1, 2 ] ) Transformation( [ 2, 3, 4, 5, 1 ] )\n",
"\n",
" + 76*1 + 63*B\n",
" Transformation( [ 5, 1, 2, 3, 4 ] )"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A.an_element() ^ 3"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"#### How it works\n",
"- Enriched libgap handles with\n",
"- Semantic carried over using\n",
"- Alignments provided as annotations\n",
"```python\n",
" @semantic(mmt=\"Group\", variant=\"multiplicative\")\n",
" class Groups:\n",
"\n",
" class ParentMethods:\n",
"\n",
" @semantic(gap=\"GeneratorsOfGroup\", codomain=Family[Self])\n",
" @abstract_method\n",
" def group_generators(self):\n",
" pass\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## That's not all! "
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"scrolled": false,
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "cd025de1cdc44b229e507dec26834e29",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"SageExplorer(children=(VBox(children=(ExplorerTitle(children=(MathTitle(value='Exploring: Group([ (1,2,3,4), (…"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"explore(G)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Combinatorial Representation Theory of $\\mathfrak S_n$"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"┌───┬───┬───┬────┐\n",
"│ 1 │ 3 │ 6 │ 10 │\n",
"├───┼───┼───┴────┘\n",
"│ 2 │ 5 │\n",
"├───┼───┤\n",
"│ 4 │ 9 │\n",
"├───┼───┘\n",
"│ 7 │\n",
"├───┤\n",
"│ 8 │\n",
"└───┘"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"StandardTableaux(10).random_element()"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"Sym = SymmetricFunctions(QQ['t']);\n",
"s = Sym.s()"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1 ⊗ s + s ⊗ s + s ⊗ s + s ⊗ s + s ⊗ s + s ⊗ s + \n",
" ┌┬┬┐ ┌┐ ┌┬┐ ┌┐ ┌┬┬┐ ┌┐ ┌┬┐ ┌┬┐ ┌┐ ┌┬┐ ┌┬┐ \n",
" ├┼┴┘ └┘ ├┼┘ └┘ └┴┴┘ ├┤ └┴┘ └┴┘ ├┤ └┴┘ └┴┘ \n",
" └┘ └┘ └┘ └┘ \n",
"\n",
"s ⊗ s + s ⊗ s + s ⊗ 1\n",
" ┌┬┐ ┌┐ ┌┬┬┐ ┌┐ ┌┬┬┐ \n",
" ├┼┘ └┘ └┴┴┘ └┘ ├┼┴┘ \n",
" └┘ └┘ "
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"s[3,1].coproduct()"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "cdd72893fafb4a59a2e5d0c66ac868a0",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"Interactive function with 1 widget\n",
" p1: GridViewWidget(value=[2, 1], children=…"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"@interact\n",
"def f(p1 = Partition([2,1])._widget_()):\n",
" return s[p1].coproduct()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Modular combinatorial representation theory of $\\mathfrak S_n$"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"⎡ . . 0 0 0 . . 1 0 0 . . 0 0 0 ⎤\n",
"⎢ . 0 0 2 . 0 0 0 . 1 0 1 ⎥\n",
"⎣ 1 0 1 , 1 0 2 , 2 0 0 ⎦"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(RibbonTableaux([[5,4,3],[2,1]], [2,1], 3))"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"level 3 LLT polynomials over Univariate Polynomial Ring in t over Rational Field"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Sym.llt(3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Really, why is that impressive?\n",
"Balthazar has at his fingertips the **best computational tools** developed by **different math communities**, all from a **single Virtual Research Environment**:\n",
"- Modular representation theory of groups\n",
"- Combinatorial Representation theory\n",
"- Semigroup theory\n",
"- Algebraic Combinatorics\n",
"\n",
"And:\n",
"\n",
"- Experimental code from his research group\n",
"- His own code"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### For 20 years, I had been dreaming of this ...
And my students too!\n",
"\n",
"\n",
" \n",
" | \n",
" | \n",
" | \n",
" | \n",
" | \n",
" | \n",
" | \n",
"
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Hurdles:\n",
"- Nicolas ~2000: no group theory and combinatorics and computer algebra under the same roof\n",
"- Nicolas 2009-2012: Sage! But interface to GAP so slow ...\n",
"- Tom 2009-2012 and Aladin 2012-2015: Semigroup not available in Sage $\\Longrightarrow$ lots of reimplementation in Sage\n",
"- Justine ~2018: lack of flexible enough interface $\\Longrightarrow$ hopping back and forth between GAP and Sage\n",
"- Justine and Pauline ~2016-2019: advisor busy with EU grant ..."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Thanks to WP6\n",
"Balthazar can:\n",
"- easily **record** and **reuse** data he computes (e.g. character tables, ...)
\n",
" py-persist, Memoize\n",
"- **document** it with metadata\n",
"- **publish** it online, e.g. on http://data.mathhub.info !"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Thanks to training, WP2\n",
"Balthazar can use his **Basic Lab Skills** to:\n",
"- Prepare **proper computational logbooks**\n",
"\n",
"- **Track** his work with version control (nbdime )\n",
"\n",
"- Turn his notebooks into slideshows\n",
"\n",
"- **Publish** his work on a public repository, e.g. on [GitHub](github.com://OpenDreamKit/demo-semigroup-representation-theory/)\n",
"\n",
"- Document the software dependencies, e.g. as a [Dockerfile](./Dockerfile)\n",
"\n",
"- Make it easy for others to **reuse** and **reproduce**, e.g. on [Binder](https://mybinder.org/v2/gh/OpenDreamKit/demo-semigroup-representation-theory/master?filepath=demo.ipynb)\n",
"\n",
"- Run his computations elsewhere, e.g. on a powerful VRE\n",
"\n",
"- Use **live-collaboration** , e.g. to get help from his advisor!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Enabled by WP3\n",
"Modularity, ease of installation and deployment, sustainability:\n",
"- Packaging in Docker, Debian, Conda
\n",
" E. Bray , J Rüth , et al. et al.
\n",
" Cernay 2016, 2017, 2019\n",
"- Ease to install packages in GAP: GAP's PackageManager
\n",
" Michael Torpey \n",
"- Integration in Sage of libsemigroups and Semigroups
\n",
" D. Paseshnik et al.\n",
"- Ease of authoring and distributing packages for Sage
\n",
" Sage package repository with pip ( et al.)
\n",
" Examples: sage-annotations , sage-explorer , sage-combinat-widgets , sage-gap-semantic interface , sage-semigroups
\n",
" N. Thiéry , O. Bénassy et al.\n",
"- Migration to Python 3
\n",
" F. Chapoton, E. Bray , D. Paseshnik , J Demeyer , ..."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Thanks to community building, WP2\n",
"\n",
"
\n",
"\n",
"Balthazar is part of a diverse and supportive community\n",
"\n",
"
\n",
"\n",
"\n"
]
}
],
"metadata": {
"celltoolbar": "Diaporama",
"kernelspec": {
"display_name": "SageMath 8.9.beta7",
"language": "sage",
"name": "sagemath"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
},
"rise": {
"auto_select": "first",
"autolaunch": true,
"background-image": "linear-gradient(rgba(255, 255, 255, 0.9), rgba(255, 255, 255, 0.9)), url(../../../public/images/banner.png);",
"scroll": true,
"start_slideshow_at": "selected",
"transition": "none"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}