![](\"pictures/banner.png\")
\n",
"\n",
"Nicolas M. Thiéry![](\"pictures/2020-01-18-INI-implementing-semigroup-representation-theory.qrcode.png\")
\n",
"\n",
"![](\"pictures/Flag_of_Europe.svg\")
\n",
"![](\"pictures/odk-elected-logo.svg\"){kind=logo}
\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"heading_collapsed": true,
"slideshow": {
"slide_type": "notes"
}
},
"source": [
"## Abstract\n",
"\n",
"Extending representation theory from finite groups to finite\n",
"semigroups brings interesting challenges, combinatorics, and\n",
"applications. Almost a decade ago, I proposed an algorithm to compute\n",
"the Cartan Matrix of a semigroup algebra -- a combinatorial invariant\n",
"that contains information on how projective modules are built from\n",
"simple modules. It boils down to computing with finite semigroups,\n",
"characters of groups, and combinatorics. Despite this relative\n",
"simplicity, and much to my embarrassment, a full production-grade\n",
"implementation is only finally in reach.\n",
"\n",
"In this talk, I will report on ongoing joint work with my PhD student\n",
"Balthazar Charles to implement this algorithm and adapt it to modular representations,\n",
"and use this occasion to illustrate the evolution of our computational\n",
"landscape toward an ecosystem of interoperable software, thanks to large\n",
"scale collaborations."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Red line of the talk\n",
"\n",
"Balthazar is starting a PhD in \n", " Example: Splitting the state space of a large discrete Markov chain\n", "\n", "- Life is imperfect: many processes have irreversible steps!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Example:** the Tsetlin library\n", "\n", "
![](\"pictures/tsetlin-library.png\")
\n",
"\n",
"- Beautiful eigenvalues!\n",
"- Explanation: very irreversible process$\\Longrightarrow$ basic representation theory" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### There are other angels\n", "\n", "
![](\"pictures/monoidClasses.svg\")
\n",
"\n",
"**Motto**: reduce to the angels: group theory, combinatorics, linear algebra"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Representation theory of semigroups, in a nutshell"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Not semi-simple: simple ≠ indecomposable"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- **Composition factors**"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Construction of simple modules: induced from the simple modules of the groupes"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- Character theory: trace of the action of conjugacy class representatives\n", " $\\Longrightarrow$ tool to recover composition factors" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- **Projective indecomposable modules**: “the largest indecomposable modules”" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- **The Cartan invariants matrix**: composition factors of projective indecomposable modules
\n", " $\\Longrightarrow$ a nice source of combinatorics" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Computing the Cartan Invariant matrix?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Algorithm from finite dimensional algebras:**\n", "- Decompose the center of the semisimple quotient (MeatAxe-style)\n", "- Recover idempotents\n", "- Compute projective modules\n", "- Recover composition factors\n", "\n", "$\\Longrightarrow$ Linear algebra on $\\K S$, if not $End(\\K S)$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Intractable for $\\#S = 31103$ (bihecke monoid of type $A_5$)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Basic insight (T. 2010):**\n", "- Realize that the Cartan invariant matrix is the character of $\\K S$ as $S$-mod-$S$ bimodule\n", "- Computation by characters!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Algorithm:**\n", "- Compute semigroup structure, conjugacy class representatives $CC$\n", "- Compute the character table of $S$ from character table of $G$
\n", " Probable bottleneck: computing the radical of $\\K R$: $O\\left(\\sum\\#R_J^3\\right)$\n", "- Count two sided fixed points for each pair in $CC$ acting on $S$
\n", " Complexity: $O\\left(\\#CC^2\\sum_J n_J+ m_J\\right)$ group operations (Charles, Mitchell, T. '20)\n", "- Recover the composition factors" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Pros:**\n", "- Embarassingly parallel!\n", "- Amenable to modular representations: use Brauer characters" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Implementation:**\n", "- Good: handles my semigroup of size 31k in one hour\n", "- Bad: aperiodic case only so far!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Musing on our computational landscape" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Available building blocks for semigroup representation theory" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Group computations: GAP, Magma\n", "- Semigroup computations: GAP, Semigroups (GAP), KBMag (C), Semigroupe (C), libsemigroups (C++), Sage\n", "- (Modular) representation theory of groups: GAP (but also GAP3+Specht)\n", "- Algebraic Combinatorics: Sage, Symmetrica (C), lrcalc (C), ...\n", "- Linear algebra: MeatAxe, Linbox, Sage, ...\n", "- Coxeter groups: GAP3+Chevie, GAP, Sage, Coxeter3, ...\n", "- Markov chains: Mathematica, ..." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Question: How to proceed?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### The Unicorn way: “There can be only one”" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "That's what happens in the tech industry: a single player takes it all (Amazon, AirBnB, Uber, ...) \n", "\n", "Why not for us?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let's reimplement everything in ~~C++~~, ~~Magma~~, ~~GAP~~, ~~Sage~~, ~~Julia~~, ~~Mathematica~~ your favorite system" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Ok for a quick focused result
\n", " Maybe that's what I should have done, actually, to get my paper out" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Does not scale, due to time scale and man power:
\n", " Our software are the result of decades of hard work and deep expertise" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Promotes competition between systems, at the wrong scale" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Honestly, we don't know what will a good system in 10-20 years
\n", " we need to explore many approaches" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Balthazar's tool box" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n" ], "text/plain": [ "
\n", " Caveats:\n", " - too slow for low-granularity computation\n", " - monolithic adapters: only groups can be used as native groups\n", "- **2012:** Sage's libgap: C-level interface to calling GAP! (Volker Braun et al.)
\n", " Caveat: a patched version of GAP\n", " - hard to maintain\n", " - hard to package\n", " - binary incompatible: $\\Longrightarrow$ no kernel modules $\\Longrightarrow$ no Semigroups\n", "- **2017-2019:** GAP's libgap (Markus Pfeiffer, Sebastian Gutsche, Max Horn, ...)
\n", " Integration in Sage (Erik Bray, ...)
\n", "- **2018** OSCAR: fast bidirectional calls between GAP and Julia (Sebastian Gutsche et al.)\n", "- **2015-:** Semantic interface to GAP (T. et al.)
\n", " Prototype; needs maturation and users to expand its scope" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Example: Interface to Semigroupe / libsemigroups\n", "- **Once upon a time**: Semigroupe by Jean-Éric Pin\n", "- **2010**: Cython bindings (T. et al.)
\n", " Caveats:\n", " - Semigroupe designed as standalone system. Global variable and single semigroup
\n", " $\\Longrightarrow$ Never made its way into Sage\n", "- **2016-**: libsemigroups ( et al.)\n", "- **2017**: Cython bindings (James Mitchell et T.)
\n", " Caveat: too much work to maintain\n", "- **2018**: cppyy bindings
\n", " Caveat: cppyy not yet mature enough\n", "- **2017-2020**: libsemigroups maturation (James Mitchel with help from Florent Hivert, T.):
\n", " API, build system, packaging, ...\n", "- **2019**: libsemigroups+Semigroups packaged in Sage (Dima Pasechnik)\n", "- **2020**: libsemigroups directly usable in Sage via cppyy!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- **Challenge**: how to push features down the stack?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Take home messages" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "###### Main challenge of computational semigroup representation theory?\n", "Combining many different building blocks" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "##### Major evolution of the last decade: we are building an ecosystem of interoperable software\n", "- A place where software pieces can emerge, live, compete, and die when they are superseded or not used anymore, without drowning down years of work\n", "- A place that fosters new ideas, and healthy competition at the granularity of ideas only\n", "\n", "**Hard** but **Doable**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**What it takes**\n", "- Large scale collaboration, across communities\n", "- Elaborating and following best practices; exploit emerging technologies\n", "- Research Software Engineers; funding? people? career paths?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "##### Opportunity: European funding\n", "- **Takes:** lots of work and luck; **Gives:** lot of resources\n", "- EOSC, Cost Networks" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Appendices" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Best practices" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### (Re)Designing our systems to be good citizens of the ecosystem\n", "- Free Software\n", "- Tests and continuous integration\n", "- Mainstream build and installation system\n", "- Mainstream development workflow\n", "- Packaging (conda, linux packages, ...)\n", "- Reduced coupling with dependencies\n", "- Well defined low level API to interact with the system\n", "- Modularity\n", "- Exposing the semantic" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "#### Interfaces\n", "\n", "- Language-level interface:\n", " - Fast comprehensive access to the other system via remote function calls and handles\n", "- Aligning the semantic:\n", " - Automatic conversion of objects\n", " - Adapting" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Externalize and share solutions to common needs\n", "- Reusable specialized high performance libraries\n", "- Development tools\n", "- User interface / interactive environment (Jupyter)\n", "- Interactive widgets (Francy, ...)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Shameless plug:\n", "- Session: **The Jupyter environment for interactive computational mathematics**?
\n", " International Congress for Mathematical Software
\n", " Braunschweig, 13-16 July, 2020
\n", " Call for speakers!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Research Software Engineers\n", "- We need software for our research\n", "- It's our job as researcher to implement the maths we need\n", "- We are killing ourselves with the maintenance and technical work" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Can we do something about it?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Lesson learned from OpenDreamKit:
\n", " A few **Research Software Engineers** can make a major impact\n", "\n", "- We need to do something to secure funding and career paths" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Large scale collaboration\n", "- Constantly coordinating efforts\n", "- Regular joint workshops\n", "- Joint projects?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Cost network?: European Cooperation in Science and Technology" ] } ], "metadata": { "celltoolbar": "Diaporama", "kernelspec": { "display_name": "SageMath 9.0", "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": false, "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 }