talk.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<style>\n",
    "rendered_html {\n",
    "  font-size:0.8em;\n",
    "}\n",
    "</style>\n",
    "<center>\n",
    "    <h1>Computing huge subspaces of polynomials:<br>Symmetries to the rescue!</h1>\n",
    "\n",
    "<br>\n",
    "  <large><a href=\"http://Nicolas.Thiery.name\">Nicolas M. Thiéry</a></large><br>\n",
    "  <a href=\"http://lri.fr\">Laboratoire de Recherche en Informatique</a><br>\n",
    "  <a href=\"http://www.u-psud.fr\">Université Paris Sud</a><br><br>\n",
    "  \n",
    "     \n",
    "  Algebra and Combinatorics at LACIM <br>\n",
    "  CRM 50th anniversary<br>\n",
    "  September 28rd of 2018<br><br>\n",
    "  \n",
    "  Slides and code: https://github.com/nthiery/harmonic-modules<br>\n",
    "\n",
    "  <a href=\"https://mybinder.org/v2/gh/nthiery/harmonic-modules/master?filepath=talk.ipynb\">Live slides</a> on <a href=\"https://mybinder.org\">Binder</a><br>\n",
    "  \n",
    "  Shorthand: https://tinyurl.com/nthiery-harmonic/\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "## Abstract\n",
    "\n",
    "In spring 2017, I visited François Bergeron and we worked on his\n",
    "favorite objects: the spaces H(n,k) of diagonal harmonic polynomials\n",
    "in k sets of n variables. Those spaces connect to many areas of\n",
    "algebraic combinatorics, representation theory and beyond, and the\n",
    "case H(n,2) became famous a decade ago with the n! conjecture and\n",
    "its proof by Haiman.\n",
    "\n",
    "To fuel his ongoing studies François needed to compute the structure\n",
    "of H(5,6). This is a space of dimension 6.10^5 made of polynomials\n",
    "in 30 variables of degree up to 15, each having thousands of terms.\n",
    "\n",
    "In this talk, I'll explain how the calculation can now be completed\n",
    "in 45 minutes with a dozen cores and ~15Go of memory. This exploits\n",
    "a combination of strategies (symmetries, representation theory of\n",
    "the symmetric and general linear group, ...), each of which reduces\n",
    "the complexity in time and memory by one or two orders of magnitude.\n",
    "\n",
    "There will be little prerequisites and it's my hope that some\n",
    "strategies (and maybe the code!) could be used in other contexts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "LaTeX definitions\n",
    "$\\def\\QQ{\\mathbb{Q}}$\n",
    "$\\def\\NN{\\mathbb{N}}$\n",
    "$\\def\\x{\\mathbf{x}}$\n",
    "$\\def\\div{\\operatorname{div}}$\n",
    "$\\def\\harm{\\operatorname{Harm}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "## Motivations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<center>\n",
    "    <img src=\"figures/crm.jpg\"/ width=\"65%\">\n",
    "    <img src=\"figures/uqam.jpg\"/ width=\"65%\">\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Joint work with François Bergeron\n",
    "<center><img src=\"figures/Francois.jpg\" height=\"50%\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "And now **Pauline Hubert**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## One of François's favorite objects\n",
    "<img src=\"figures/book.jpg\" style=\"float:right;\"/><br>\n",
    "The space $\\harm(n,r)$ of **diagonal harmonic polynomials** in\n",
    "$$\\QQ\\begin{bmatrix}\n",
    "        x_{11}&\\cdots&x_{1n}\\\\\n",
    "        \\vdots & & \\vdots\\\\\n",
    "        x_{r1}&\\cdots&x_{rn}\\\\\n",
    "     \\end{bmatrix}$$\n",
    "- $\\harm(n,1)$ : dim=$n!$<br>\n",
    "  graded character: Hall-Littlewood Polynomials<br>\n",
    "  connections with invariant theory, ...\n",
    "- $\\harm(n,2)$ : dim = $(n+1)^{n-1}$<br>\n",
    "  graded character: Macdonald polynomials<br>\n",
    "  $n!$-conjecture of Garsia/Bergeron<br>\n",
    "  proof by Mark Haiman using the Hilbert scheme of points\n",
    "- $\\harm(n,r)$ : dim = ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Project: pushing further the computer exploration\n",
    "\n",
    "**Aim**: dimension and graded character of $\\harm(6,5)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Brute force linear algebra?\n",
    "- polynomials in 30 variables of degree up to 15, with thousands of terms\n",
    "- dimension: $\\approx$ 3.7 million"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1606.19609335363*year"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = 3.7 * 10^6\n",
    "t = d^3 / 10.^9 * units.time.second\n",
    "t.convert(units.time.year)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, +, 30*z, +, 465*z², +, 4960*z³, +, 40920*z⁴, +, 278256*z⁵, +, 1623160*z⁶, \n",
       "+, 8347680*z⁷, +, 38608020*z⁸, +, 163011640*z⁹, +, 635745396*z¹⁰, +, 231180144\n",
       "0*z¹¹, +, 7898654920*z¹², +, 25518731280*z¹³, +, 78378960360*z¹⁴, +, 229911617\n",
       "056*z¹⁵, +, Order(z¹⁶⁾)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "var('z');\n",
    "f = ( 1/(1-z)^30 ).series(z,16); f # the graded dimension of the polynomial ring Q[x_ij]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7271243.21326576⋅year"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = sum(f.coefficients(sparse=False))\n",
    "t = d^1.8 * D / 10.^9 * units.time.second\n",
    "t.convert(units.time.year)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Intractable?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "After a couple weeks of hard work, let's see what we get with 15 Gb and 10 cores:\n",
    "- minutes? hours? days? years?\n",
    "- dimension: ??"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "TODO:\n",
    "- launch the calculation remotely instead of giving away the result now\n",
    "- Configure partition output to be compact list, including in symmetric functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%run old_code/code.py\n",
    "%run -i talk.py\n",
    "%display unicode_art"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 ⊗ s  + s  ⊗ s   + s   ⊗ s    + s    ⊗ s     + s  ⊗ s   + s  ⊗ s   + s   ⊗ \n",
       "     4    1    31    11    211    111    1111    2    22    2    31    21   \n",
       "\n",
       "s    + s   ⊗ s   + s  ⊗ s    + s  ⊗ s   + s   ⊗ s     + s   ⊗ s    + s  ⊗ s   \n",
       " 211    21    22    3    211    3    31    31    1111    31    211    4    211\n",
       "\n",
       " + s  ⊗ s   + s   ⊗ s     + s  ⊗ s    + s  ⊗ s\n",
       "    4    22    41    1111    5    211    6    1111"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "harmonic_bicharacter(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Was it worth the trouble?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Stability property**: $\\harm(6,5)$ contains all the information about $\\harm(6,r)$ for all $r$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "«Coté mathématiques, grâce à tes calculs et à mon apprentissage de Sage, j’ai exploré une mine d’or de liens entre tout ce qu’on fait depuis le début sur les opérateurs de Macdonald, jusqu’à aujourd’hui; algèbre de Hall elliptique, Conjecture Delta, théorie des noeuds et  entrelacs du tore, etc. Je pense que cela sera ce que j’ai fait de mieux dans ma carrière. C’est magnifique et cela simplifie la compréhension de tout, permet de prouver plein de liens nouveaux, prédit comment généraliser, et de plus j’ai des modules qui expliquent cela.»\n",
    "\n",
    "François"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Plan\n",
    "### Motivations\n",
    "### Warming up: harmonic polynomials\n",
    "- Definition\n",
    "- Exploiting the grading\n",
    "\n",
    "### Diagonal harmonic polynomials\n",
    "- Definition\n",
    "- Exploiting the multigrading\n",
    "- Exploiting symmetries: action of $S_r$\n",
    "- Exploiting symmetries: action of $gl_r$?\n",
    "- Exploiting symmetries: action of $S_n$\n",
    "- Exploiting antisymmetries: action of $S_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Harmonic polynomials\n",
    "$\\QQ[X]$: the ring of polynomials $f$ in the $n$ variables $X:=(x_1,\\ldots,x_n)$\n",
    "\n",
    "Partial derivatives: $\\partial_i := \\partial_{x_i} := \\frac{\\partial}{\\partial x_i}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Definition:** $f\\in\\QQ[X]$ **harmonic** if\n",
    "$$ \\partial_1^k\\,f+ \\cdots + \\partial_n^k\\,f = 0, \\qquad \\forall k>0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In particular: $\\quad \\div f = 0, \\quad  \\nabla f = 0, \\quad ...$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Examples:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$1$, $x_1-x_2$ and linear combinations are harmonic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The subspace $\\harm(n)$  of harmonic polynomials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- the joint kernel of the differential operators $D_k := \\partial_1^k + \\cdots + \\partial_n^k$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- a realization of the coinvariants of the symmetric group: $\\QQ[X]\\, /\\, \\langle Sym(X)^+ \\rangle$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- the graded regular representation of $S_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Example\n",
    "$$\\harm(2) = \\langle 1, x_1-x_2 \\rangle_\\QQ$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example on computer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%display unicode_art\n",
    "R = QQ['x1,x2,x3']\n",
    "x1,x2,x3 = X = R.gens()\n",
    "p1 = lambda p: p.derivative(x1)                         # ∂₁\n",
    "p2 = lambda p: p.derivative(x2)                         # ∂₂\n",
    "p3 = lambda p: p.derivative(x3)                         # ∂₃\n",
    "D1 = lambda p: sum( p.derivative(v) for v in X)         # ∂₁  + ∂₂  + ∂₃\n",
    "D2 = lambda p: sum( p.derivative([v,v]) for v in X)     # ∂₁² + ∂₂² + ∂₃²\n",
    "D3 = lambda p: sum( p.derivative([v,v,v]) for v in X)   # ∂₁³ + ∂₂³ + ∂₃³"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D1(x1-x2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "( 0, 0 )"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D1(x1-x3), D1(x2-x3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2*x1 - 2*x2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D1(x1^2-x2^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "( 0, 0, 0 )"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Delta = ( (x1-x2) * (x1-x3) * (x2-x3) )\n",
    "D1(Delta), D2(Delta), D3(Delta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "( 0, 0, 0 )"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = p1 ( Delta )\n",
    "D1(f), D2(f), D3(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### What have we learned?\n",
    "- $\\Delta:=$ $\\prod_{i<j}(x_i-x_j)$ is harmonic\n",
    "- $f$ harmonic $\\Longrightarrow$ $\\partial_i f$ harmonic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Theorem:**  $\\harm(n) = \\langle \\Delta \\rangle_{\\partial_1,\\ldots,\\partial_n}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### On computer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H = Subspace([Delta], [p1,p2,p3])\n",
    "H.dimension()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "( -x1^2*x2 + x1*x2^2 + x1^2*x3 - x2^2*x3 - x1*x3^2 + x2*x3^2,\n",
       "\n",
       " -x1*x2 + 1/2*x2^2 + x1*x3 - 1/2*x3^2, 1/2*x1^2 - x1*x2 + x2*x3 - 1/2*x3^2,\n",
       "\n",
       " x1 - x3, x2 - x3, 1 )"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H.basis()[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ (x2 - x3) * (-x1 + x2) * (x1 - x3), (1/2) * (x2 - x3) * (-2*x1 + x2 + x3),\n",
       "\n",
       " (-1/2) * (-x1 + 2*x2 - x3) * (x1 - x3), x1 - x3, x2 - x3, 1 ]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ factor(v) for v in H.basis()[0]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algorithm: straightforward linear algebra in the monomial basis\n",
    "`Subspace( polynomials, operators )`:\n",
    "- maintain a list $L$ of all the relevant monomials\n",
    "- represent the polynomials as finite vectors with columns indexed by $L$\n",
    "- build a matrix and maintain it in row echelon form\n",
    "- insert new vectors until the subspace is stable under the operators\n",
    "\n",
    "**Tricky part**: make that work with most vector spaces in Sage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "⎛   1   -1    1    1   -1   -1    0    0    0    0    0    0    0    0    0    0⎞\n",
       "⎜   0    0    0    0    0    0    1    0    0  1/2    0    0    0    0 -1/2   -1⎟\n",
       "⎜   0    0    0    0    0    0    0    1  1/2    0    0    0    0    0 -1/2   -1⎟\n",
       "⎜   0    0    0    0    0    0    0    0    0    0    1    0    0   -1    0    0⎟\n",
       "⎜   0    0    0    0    0    0    0    0    0    0    0    1    0   -1    0    0⎟\n",
       "⎝   0    0    0    0    0    0    0    0    0    0    0    0    1    0    0    0⎠"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H.matrix()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Note**: The matrix is block diagonal: harmonic polynomials of degree $0, 1, 2, 3$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Strategy: exploiting the grading"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def add_degrees(d1, d2):\n",
    "    d = d1 + d2\n",
    "    if d < 0: raise ValueError(\"Negative degree\")\n",
    "    return d\n",
    "F = Subspace(generators  = { 3: [Delta]},\n",
    "             operators   = {-1: [p1,p2,p3]},\n",
    "             add_degrees = add_degrees)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F.dimension()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "q^3 + 2*q^2 + 2*q + 1"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F.hilbert_polynomial()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Algorithm**:\n",
    "- construct the graph of the homogeneous components and operators between them\n",
    "- maintain one matrix per homogeneous component and propagate polynomials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "TODO: Draw the graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Potential gain** for an $n\\times n$ matrix $M$ with $k$ blocks of same size:<br>\n",
    "Complexity of linear algebra: $k\\left(\\frac n k\\right)^3 = \\frac 1{k^2} n^3$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "So far, nothing very interesting, since $\\harm(n,1)$ is very well known.\n",
    "Time to move on to diagonal harmonic polynomials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Diagonal harmonic polynomials\n",
    "Polynomial ring in $r$ rows $X_1,\\ldots,X_r=X,Y,\\ldots,Z$ of $n$ variables:\n",
    "$$\\QQ\\begin{bmatrix}\n",
    "        x_1&\\cdots&x_n\\\\\n",
    "        \\vdots & & \\vdots\\\\\n",
    "        z_1&\\cdots&z_n\\\\\n",
    "    \\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Differential operators $(D_\\alpha)_{\\alpha\\in \\NN^r}$:\n",
    "$$D_{(3,0,4)} := \\partial_{x_1}^3\\partial_{z_1}^4 + \\dots + \\partial_{x_n}^3\\partial_{z_n}^4$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Diagonal harmonic polynomials** $\\harm(n,r)$: joint kernel of the $(D_\\alpha)_\\alpha$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "How to compute them?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Computing diagonal harmonic polynomials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Remark**: $\\harm(n,r)$ contains $\\harm(n,1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Polarization operators:**<br>\n",
    "- In two rows of variables:\n",
    "\n",
    "$$P_{(-k,1)} := \\partial_{x_1}^k y_1 +\\cdots+\\partial_{x_n}^k y_n$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Between any two rows $X_i$ and $X_j$ of variables:\n",
    "\n",
    "$$P_{(0\\ldots0,-k,0\\ldots0,1,0\\ldots0)} := \\cdots$$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Fact:**\n",
    "$\\harm(n,r)$ is generated by $\\harm(n,1)$ and the polarization operators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Multigrading\n",
    "**Multidegree**: degree in each row $X_i$ of variables\n",
    "\n",
    "**Example**: $x_1^2x_2 z_2^4$ is of multidegree $(3,0,4)=x^3z^4$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Remark**:\n",
    "- The $D_\\alpha$ preserve the grading: $\\harm(n,r)$ is multigraded\n",
    "- The polarization operators preserve the multigrading\n",
    "- So we can split the linear algebra by homogeneous components"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "TODO: Drawing of the graph\n",
    "TODO: do the calculation directly with Subspace and polarization operators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Example: computing the **Hilbert polynomial** of Harm(3,3):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center><img src=\"figures/harmonic_graph-3-3-P.svg\" width=\"90%\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Symmetries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## The Hilbert polynomial of Harm(3,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^3 + x^2*y + x*y^2 + y^3 + x^2*z + x*y*z + y^2*z + x*z^2 + y*z^2 + z^3 + 2*x^2 + 3*x*y + 2*y^2 + 3*x*z + 3*y*z + 2*z^2 + 2*x + 2*y + 2*z + 1"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 3; r = 3\n",
    "H = sum( harmonic_character(mu) * StandardTableaux(mu).cardinality()\n",
    "         for mu in Partitions(n))\n",
    "H.expand(r, 'xyz')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Note**: This is a symmetric polynomial. How comes?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Remark**\n",
    "- $\\harm(n,r)$ stable under permuting rows of variables\n",
    "- action of the symmmetric group $S_r$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "TODO: Could show the matrices; or later, when illustrating antisymmetries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exploiting the action of $S_r$ on rows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Restrict the computations to decreasing multidegrees:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center><img src=\"figures/harmonic_graph-3-3-m.svg\" width=\"40%\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Requires a bit of care: reordering after polarization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exploiting the action of $S_r$ on rows: gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^3 + x^2*y + x*y^2 + y^3 + x^2*z + x*y*z + y^2*z + x*z^2 + y*z^2 + z^3 + 2*x^2 + 3*x*y + 2*y^2 + 3*x*z + 3*y*z + 2*z^2 + 2*x + 2*y + 2*z + 1"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H.expand(r, 'xyz')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(_.coefficients())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 + 2*m  + 3*m   + m    + 2*m  + m   + m\n",
       "       1      11    111      2    21    3"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m(H)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(_.coefficients())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**In general**: an order of magnitude"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Back to the Hilbert polynomial of Harm(3,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 + 2*m  + 3*m   + m    + 2*m  + m   + m\n",
       "       1      11    111      2    21    3"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m(H)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 + 2*s  + s   + 2*s  + s\n",
       "       1    11      2    3"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s(H)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note**: it's Schur positive! How comes?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The action of $GL(r)$ on rows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- $\\harm(n,r)$ is stable under substituting linear combinations of rows\n",
    "- Action of the general linear group $GL(r)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center><img src=\"figures/harmonic_graph-3-3-P.svg\" width=\"60%\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- The multi homogeneous components are the **weight spaces**\n",
    "- The polarization operators $P_{(-1,1)}$: action on rows of the **lie algebra** $gl(r)$\n",
    "- The Hilbert polynomial is the **$GL(r)$-character** of $\\harm(n,r)$:  $1+2s_1 + 2s_2 +s_3 + s_{11}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exploiting the action of $gl(r)$ on rows?\n",
    "Hope: Restrict the computation to **highest weight spaces**:\n",
    "<center><img src=\"figures/harmonic_graph-3-3-s.svg\" width=\"30%\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Potential gain**:\n",
    "- One or two orders of magnitude\n",
    "- Finish computing $\\harm(7,6)$\n",
    "- François needs it! Presumably Vincent, Nantel, ... as well"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The action of $S_n$ on columns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Remember: $\\Delta:=(x_1-x_2)(x_1-x_3)(x_2-x_3)$ is harmonic because of antisymmetries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- $\\harm(n,r)$ is stable under permuting columns of variables\n",
    "- Multigraded action of the symmetric group $S_n$ or column\n",
    "- Polarization operators: $S_n$-morphisms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center><img src=\"figures/harmonic_graph-3-3-P-s.svg\" width=\"70%\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exploiting the action of $S_n$ on columns: algorithm\n",
    "\n",
    "**Step 1**: Choose a simple representation of $S_n$: $\\lambda$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Step 2**: Apply Young's idempotent $e_\\lambda$ to harmonic polynomials"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Optimization:\n",
    "- Compute the **higher Specht** polynomials for $\\lambda$\n",
    "- Project onto harmonic polynomials     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Step 3**: Apply polarization as usual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exploiting the action of $S_n$ on columns: gain?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "n = 4; r = 3\n",
    "sum(harmonic_character(mu) * StandardTableaux(mu).cardinality()\n",
    "    for mu in Partitions(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "{mu: harmonic_character(mu) for mu in Partitions(n) } "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Finer information: compute directly the $GL(r)-S_n$ bicharacter\n",
    "- Smaller spaces: an order of magnitude\n",
    "- Parallelism\n",
    "- Partial computation: only two partitions missing for $n=7$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The action of $S_n$ on columns: antisymmetries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ ( 0, 1, 1 ):( 1 -1 -1  1  1 -1),\n",
       "\n",
       " ( 2, 1, 0 ):(   1  1/2    1  1/2    1   -1 -1/2  1/2 -1/2 -1/2   -1   -1),\n",
       "\n",
       " ( 0, 0, 2 ):(), ( 0, 2, 0 ):(),\n",
       "\n",
       " ( 0, 1, 2 ):(   1    1  1/2 -1/2 -1/2   -1   -1    1  1/2  1/2   -1 -1/2),\n",
       "\n",
       " ( 1, 1, 0 ):( 1  1 -1 -1  1 -1),\n",
       "\n",
       " ( 1, 0, 2 ):(   1   -1  1/2    1  1/2   -1  1/2 -1/2    1 -1/2   -1 -1/2),\n",
       "\n",
       " ( 1, 0, 1 ):( 1 -1 -1  1  1 -1),\n",
       "\n",
       " ( 1, 1, 1 ):( 1 -1  1 -1  1 -1  1  1 -1 -1  1  1 -1 -1 -1  1 -1  1),\n",
       "\n",
       " ( 0, 3, 0 ):( 1 -1 -1 -1  1  1), ( 3, 0, 0 ):( 1 -1 -1 -1  1  1),\n",
       "\n",
       " ( 2, 0, 1 ):(   1  1/2    1 -1/2  1/2   -1   -1  1/2 -1/2    1   -1 -1/2),\n",
       "\n",
       " ( 0, 2, 1 ):(   1    1  1/2 -1/2 -1/2   -1   -1 -1/2   -1  1/2    1  1/2),\n",
       "\n",
       " ( 1, 2, 0 ):(   1 -1/2   -1  1/2  1/2   -1   -1 -1/2    1  1/2    1 -1/2),\n",
       "\n",
       " ( 0, 0, 3 ):( 1 -1 -1 -1  1  1) }"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 3; r = 3\n",
    "H = DiagonalPolynomialRing(QQ,n,r)\n",
    "HDelta = H.harmonic_space_by_shape([1]*n)\n",
    "HDelta.finalize()\n",
    "{mu:b._matrix for mu,b in HDelta._bases.iteritems()}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Lots of redundancy!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- $\\Delta$ is antisymmetric:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x1^2*x2 - x1*x2^2 - x1^2*x3 + x2^2*x3 + x1*x3^2 - x2*x3^2"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Delta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Polarisation preserves antisymmetries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exploiting antisymmetries\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Algorithm\n",
    "For $\\lambda = (1,\\dots,1)$, $\\Delta$:\n",
    "- Represent a single monomial per $S_n$-orbit (the **diagram space** of François)\n",
    "- Straighten after each application of polarization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Generalization to any partition:\n",
    "- the Young idempotents creates partial antisymmetries by construction\n",
    "- exploit them!\n",
    "- straightening implemented in Cython"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Gain\n",
    "- A factor of up to $n!$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Combining everything together?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Time to wrapup\n",
    "- We all know that symmetries should help\n",
    "- We saw a prototypical example:<br>\n",
    "  - reduction of a computation from years to minutes\n",
    "  - using group representations\n",
    "  - using lie algebra representations?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- It helped that we were just doing linear algebra!\n",
    "- Using the underlying ideal structure?<br>\n",
    "  Gröbner bases + symmetries? (known to be hard)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Designing the code is half of the difficulty:<br>\n",
    "  tension between simplicity for a given purpose and versatility\n",
    "- Now used and further extended by **Pauline Hubert**\n",
    "- **Project**: getting the Subspace code into Sage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " - Ask **Adriano** and **François** for the beautiful mathematics behind!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center><h1>Thank you LACIM, and happy anniversary!</h1></center>"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "SageMath 8.7",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  },
  "livereveal": {
   "auto_select": "first",
   "autolaunch": true,
   "scroll": "true",
   "start_slideshow_at": "selected",
   "transition": "none"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}