{ "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 }