{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\def\\CC{\\bf C}\n", "\\def\\QQ{\\bf Q}\n", "\\def\\RR{\\bf R}\n", "\\def\\ZZ{\\bf Z}\n", "\\def\\NN{\\bf N}\n", "$$\n", "# SMAI 2011, Guidel, 23 mai 2011: Sage pour le calcul symbolique, alg\u00e9brique et combinatoire\n", "\n", "Cet expos\u00e9 compl\u00e8te le tutoriel d'introduction \u00e0 Sage en explorant plus en avant les possibilit\u00e9s de Sage pour le calcul symbolique, alg\u00e9brique et combinatoire. Nous mettrons en particulier en avant l'int\u00e9r\u00eat d'avoir une large palette d'outils \u00e0 l'int\u00e9rieur d'un m\u00eame syst\u00e8me de calcul, ainsi que la d\u00e9marche de Sage visant \u00e0 mod\u00e9liser les math\u00e9matiques au plus pr\u00e8s. On peut par exemple manipuler non seulement des matrices, mais ausi des syst\u00e8mes d'\u00e9quations, des morphismes ou des sous-espaces vectoriels. On peut aussi mod\u00e9liser des connaissances math\u00e9matiques comme: \u00abL'anneau des polyn\u00f4mes en une variable sur un corps est euclidien\u00bb. Cette mod\u00e9lisation s'appuie sur un pont naturel entre th\u00e9orie des cat\u00e9gories d'un c\u00f4t\u00e9 et programmation orient\u00e9e objet (un des multiples paradigmes de programmation du langage Python) de l'autre.\n", "\n", "Si le temps le permet, nous montrerons un exemple r\u00e9el dans un contexte de recherche illustrant des constructions avanc\u00e9es et la combinaison de multiples outils de calculs.\n", "\n", "## Calcul symbolique\n", "\n", "Le coeur des syst\u00e8mes comme Maple et Maxima est le calcul sur les expressions, avec sa simplicit\u00e9 pour les nouveaux venus et sa souplesse. Modulo la d\u00e9claration explicite des variables et des petites variantes de syntaxe, l'utilisateur casuel retrouvera ses petits.\n", "\n", "Une expression:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "sin(x)^6 + cos(x)^6 + 3*sin(x)^2*cos(x)^2" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = cos(x)^6 + sin(x)^6 + 3 * sin(x)^2 * cos(x)^2; f" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Simplifions-la:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.simplify_trig()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Une sommation d\u00e9finie:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(n, k)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var('n,k')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1/2*sqrt(pi)/factorial(n + 1/2)\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(binomial(n, k) * factorial(k) / factorial(n+1+k), k, 0, n)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{\\sqrt{\\pi}}{2 \\, \\left(n + \\frac{1}{2}\\right)!}" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pretty_print(_)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Calcul de $\\lim\\limits_{x\\rightarrow \\frac{\\pi}{4} }\\dfrac{\\cos\\left(\\frac{\\pi}{4}-x \\right)-\\tan x }{1-\\sin\\left(\\frac{\\pi}{4}+x \\right)}$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+Infinity" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f(x) = (cos(pi/4-x)-tan(x)) / (1-sin(pi/4 + x))\n", "limit(f(x), x = pi/4, dir='minus')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Calcul, selon la valeur de $x$, de $\\int_0^{\\infty} \\frac{x \\cos u}{u^2+x^2} du$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "u" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var('u')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1/2*pi*e^(-x)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = x * cos(u) / (u^2 + x^2)\n", "assume(x>0)\n", "f.integrate(u, 0, infinity)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-1/2*pi*e^x" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "forget(); assume(x<0); f.integrate(u, 0, infinity)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'arithm\u00e9tique est g\u00e9r\u00e9e en interne (pynac) et le reste est d\u00e9l\u00e9gu\u00e9 \u00e0 Maxima. En relatif, cet aspect reste un des points faibles de Sage.\n", "\n", "## Polyn\u00f4mes\n", "\n", "Chaque fois que possible, Sage privil\u00e9gie la mod\u00e9lisation explicite de la structure alg\u00e9brique dans laquelle on souhaite mener le calcul. Cela permet de travailler naturellement et efficacement dans des constructions alg\u00e9briques plus avanc\u00e9es:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Finite Field of size 2" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z2 = GF(2); Z2" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = Z2['x']; P" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Full MatrixSpace of 3 by 3 dense matrices over Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M = MatrixSpace(P, 3); M" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ x + 1 x^2 x^2]\n", "[ x x^2 + x x + 1]\n", "[ x^2 + 1 x^2 + x + 1 x^2]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = M.random_element(); m # random" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Full MatrixSpace of 3 by 3 dense matrices over Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m.parent()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ x^4 + x^3 + x x^3 + x^2 x^4 + x^2]\n", "[ x^2 + x + 1 x^4 + x + 1 x^3 + x^2 + 1]\n", "[ x^4 x^4 + x^3 + x^2 + 1 x^3 + 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m * (m-1) # random" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^6 + x^5 + x^3 + x^2 + x + 1" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m.det() # random" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "et d'y traiter rigoureusement, par exemple, les questions de factorisation:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*(3*x + 1)^2*(x^2 - 2)\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = 54*x^4+36*x^3-102*x^2-72*x-12\n", "p.factor()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Integer Ring :\n", "2 * 3 * (3*x + 1)^2 * (x^2 - 2)\n", "Rational Field :\n", "(54) * (x + 1/3)^2 * (x^2 - 2)\n", "Complex Field with 16 bits of precision :\n", "(54.00) * (x - 1.414) * (x + 0.3333)^2 * (x + 1.414)\n", "Number Field in sqrt2 with defining polynomial x^2 - 2 :\n", "(54) * (x - sqrt2) * (x + sqrt2) * (x + 1/3)^2\n", "Finite Field of size 5 :\n", "(4) * (x + 2)^2 * (x^2 + 3)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for A in [ZZ, QQ, ComplexField(16), QQ[sqrt(2)], GF(5)]:\n", " print A, \":\"; print A['x'](p).factor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Alg\u00e8bre lin\u00e9aire\n", "\n", "Dans les exemples ci-dessous, nous ferons de l'alg\u00e8bre lin\u00e9aire sur le corps fini $\\ZZ/7\\ZZ$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Finite Field of size 7\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K = GF(7); K" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 3, 4, 5, 6]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(K)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous avons choisi ce corps \u00e0 titre d'illustration pour avoir des r\u00e9sultats *lisibles*. On aurait pu prendre des coefficients entiers, rationnels, ou num\u00e9riques \u00e0 plus ou moins haute pr\u00e9cision. Les aspects num\u00e9riques seront abord\u00e9s plus en d\u00e9tail dans l'expos\u00e9 suivant. Notons au passage que, m\u00eame en calcul exact, il est possible de manipuler de relativement grosses matrices:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9278" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M = random_matrix(K, 10000, sparse=True, density=3/10000)\n", "M.rank() # random" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "D\u00e9finissons donc une matrice \u00e0 coefficients dans $\\ZZ/7\\ZZ$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[5 5 4 3]\n", "[0 3 3 4]\n", "[0 1 5 4]\n", "[6 0 6 3]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = matrix(K, 4, [5,5,4,3,0,3,3,4,0,1,5,4,6,0,6,3]); A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Calculons le polyn\u00f4me caract\u00e9ristique de cette matrice:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 5*x^3 + 6*x + 2" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = A.characteristic_polynomial(); P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On v\u00e9rifie le th\u00e9or\u00e8me de Cayley-Hamilton sur cet exemple:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notons que l'information sur le corps de base est pr\u00e9serv\u00e9e:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Finite Field of size 7" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.parent()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "ce qui influe directement sur la factorisation de ce polyn\u00f4me:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + 3) * (x + 6) * (x + 5)^2\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factor(P)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 5*x^3 + 6*x + 2" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factor(x^4 + 5*x^3 + 6*x + 2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le calcul ci-dessus nous donne les valeurs propres: -3=4,-6=1 et -5=2. Quels sont les espaces propres?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\n", "(4, Vector space of degree 4 and dimension 1 over Finite Field of size 7\n", "User basis matrix:\n", "[1 4 6 1]),\n", "(1, Vector space of degree 4 and dimension 1 over Finite Field of size 7\n", "User basis matrix:\n", "[1 3 3 4]),\n", "(2, Vector space of degree 4 and dimension 2 over Finite Field of size 7\n", "User basis matrix:\n", "[1 0 2 3]\n", "[0 1 6 0])\n", "]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.eigenspaces_left()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "R\u00e9cup\u00e9rons ces espaces propres:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Vector space of degree 4 and dimension 2 over Finite Field of size 7\n", "User basis matrix:\n", "[1 0 2 3]\n", "[0 1 6 0]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E = dict(A.eigenspaces_left())\n", "E[2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`E[2]` n'est pas une *liste de vecteurs* ni une matrice, mais un *objet* qui mod\u00e9lise l'espace propre $E_2$, comme le sous-espace de $(\\ZZ/7\\ZZ)^4$ d\u00e9crit par sa base \u00e9chelon r\u00e9duite. On peut donc lui poser des questions:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E[2].dimension()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\n", "(1, 0, 2, 3),\n", "(0, 1, 6, 0)\n", "]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E[2].basis()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Vector space of dimension 4 over Finite Field of size 7" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "V = E[2].ambient_vector_space(); V" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voire faire des calculs avec:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Vector space of degree 4 and dimension 3 over Finite Field of size 7\n", "Basis matrix:\n", "[1 0 0 0]\n", "[0 1 0 5]\n", "[0 0 1 5]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E[2] + E[4]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "v = V([1,2,0,3])\n", "v in E[2]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E[2].echelon_coordinates(v)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E[2].is_subspace(E[4])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E[2].is_subspace(V)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Vector space quotient V/W of dimension 2 over Finite Field of size 7 where\n", "V: Vector space of dimension 4 over Finite Field of size 7\n", "W: Vector space of degree 4 and dimension 2 over Finite Field of size 7\n", "User basis matrix:\n", "[1 0 2 3]\n", "[0 1 6 0]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Q = V/E[2]; Q" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2, 4)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Q( V([0,0,0,1]) )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On veut maintenant manipuler $A$ comme un morphisme sur $V$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Free module morphism defined by the matrix\n", "[5 5 4 3]\n", "[0 3 3 4]\n", "[0 1 5 4]\n", "[6 0 6 3]\n", "Domain: Vector space of dimension 4 over Finite Field of size 7\n", "Codomain: Vector space of dimension 4 over Finite Field of size 7\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "phi = End(V)(A); phi" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 0, 0, 0)\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "v = V.an_element()\n", "v" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5, 5, 4, 3)\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "phi(v)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 2, 3, 4)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(phi^-1)(v)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Free module morphism defined by the matrix\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "Domain: Vector space of dimension 4 over Finite Field of size 7\n", "Codomain: Vector space of dimension 4 over Finite Field of size 7\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "phi^4 + 5*phi^3 + 6*phi + 2" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Vector space of degree 4 and dimension 3 over Finite Field of size 7\n", "Basis matrix:\n", "[1 0 0 0]\n", "[0 1 0 5]\n", "[0 0 1 5]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(phi - 1).image()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(phi - 1).kernel() == E[1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Free module morphism defined by the matrix\n", "[2 0]\n", "[0 2]\n", "Domain: Vector space of degree 4 and dimension 2 over Finite Field of ...\n", "Codomain: Vector space of degree 4 and dimension 2 over Finite Field of ..." ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "phi.restrict(E[2])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### En r\u00e9sum\u00e9\n", "\n", "- *\u00ab Mathematics is the art of reducing any problem to linear algebra \u00bb* William Stein\n", "- Il serait en principe suffisant d'implanter l'alg\u00e8bre lin\u00e9aire sur les matrices\n", "- Le pari de Sage: *mod\u00e9liser au plus pr\u00e8s les math\u00e9matiques*, pour que l'utilisateur ou le programmeur puisse s'exprimer dans le langage adapt\u00e9 au probl\u00e8me consid\u00e9r\u00e9.\n", "\n", "## Combinatoire\n", "\n", "Selon le m\u00eame principe, lorsque l'on demande toutes les partitions de l'entier 5, le r\u00e9sultat est un objet qui mod\u00e9lise cet ensemble:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Partitions of the integer 5" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = Partitions(5); P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour obtenir la *liste* de ces objets, il faut le demander explicitement:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.list()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Cela permet de manipuler *formellement* des grands ensembles:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Partitions(100000).cardinality()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et de calculer paresseusement avec. Ici, on tire au hasard une main de cinq cartes \u00e0 jouer:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2598960" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Symboles = Set([\"Coeur\", \"Carreau\", \"Pique\", \"Trefle\"])\n", "Valeurs = Set([2, 3, 4, 5, 6, 7, 8, 9, 10, \"Valet\", \"Dame\", \"Roi\", \"As\"])\n", "Cartes = CartesianProduct(Valeurs, Symboles).map(tuple)\n", "Mains = Subsets(Cartes, 5)\n", "Mains.cardinality()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{(2, 'Coeur'), (6, 'Pique'), (10, 'Carreau'), ('As', 'Pique'), ('Valet', 'Coeur')}" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Mains.random_element() # random" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "et l\u00e0 on manipule un mot infini d\u00e9fini comme point fixe d'un morphisme:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "word: acabbbabaacabbbcacacbbbcacacbbbcacacbbac..." ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = WordMorphism('a->acabb,b->bcacacbb,c->baba')\n", "m.fixed_point('a')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Probas?\n", "\n", "Une session r\u00eav\u00e9e:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X = random_variable(BernouilliDistribution(1/2))\n", "Y = random_variable(BinomialDistribution(3, 1/3))\n", "Z = X + 2*Y\n", "Z.mean()\n", "Z.variance()\n", "plot(Z.distribution())\n", "event = ( Z <= 1 )\n", "event.probability()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Ce type de mod\u00e9lisation serait-il utile?\n", " - Pour l'enseignement?\n", " - Pour fournir des mod\u00e8les exacts pour des tests statistiques? (\u00e0 la [StatXact](http://www.cytel.com/software/StatXact.aspx))\n", "- Implantable \u00e0 partir des fondamentaux de Sage? (combinatoire, int\u00e9gration, ...)?\n", "\n", "## Combinatoire alg\u00e9brique\n", "\n", "Et pour faire joli, un syst\u00e8me de racine affine et un groupe de Weyl:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "L = RootSystem(['A',2,1]).weight_space()\n", "L.plot(size=[[-1..1],[-1..1]], alcovewalks=[[0,2,0,1,2,1,2,0,2,1]])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "W = WeylGroup([\"B\", 3])\n", "W.cayley_graph(side = \"left\").plot3d(color_by_label = True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graphes\n", "\n", "Nous montrons maintenant quelques fonctionnalit\u00e9s de Sage autour des graphes:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = graphs.ChvatalGraph()\n", "g.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "c = g.hamiltonian_cycle()\n", "g.show(edge_colors = {\"red\": c.edges()} )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Gr\u00e2ce \u00e0 GAP et \u00e0 (un port de) Nauty, on peut \u00e9tudier de pr\u00e8s les questions de sym\u00e9tries et d'isomorphisme dans les graphes. Voici tous les graphes simples sur cinq sommets avec moins de quatre ar\u00eates:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "show(graphs(5, lambda G: G.size() <= 4))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le groupe de sym\u00e9tries (automorphismes) du graphe de Petersen:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "petersen = graphs.PetersenGraph()\n", "petersen.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Permutation Group with generators [(3,7)(4,5)(8,9), (2,6)(3,8)(4,5)(7,9), (1,4,5)(2,3,8,6,9,7), (1,10)(2,4,6,5)(3,9,8,7)]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "group = petersen.automorphism_group(); group" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et quelques-unes de ses propri\u00e9t\u00e9s:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "120\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "group.cardinality()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 1 1 1 1 1 1]\n", "[ 1 -1 1 -1 1 -1 1]\n", "[ 4 -2 0 1 1 0 -1]\n", "[ 4 2 0 -1 1 0 -1]\n", "[ 5 1 1 1 -1 -1 0]\n", "[ 5 -1 1 -1 -1 1 0]\n", "[ 6 0 -2 0 0 0 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "group.character_table()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 60, 120]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[N.cardinality() for N in group.normal_subgroups()]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "group.is_isomorphic(SymmetricGroup(5))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Calculons quelques propri\u00e9t\u00e9s classiques de ce graphe. Il faut trois couleurs pour le colorier:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "petersen.chromatic_number()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "petersen.show(partition=petersen.coloring())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Mais ce n'est cependant pas un graphe parfait:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "petersen.is_perfect()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Tant que l'on ne supprime pas plus de quatre sommets ou quatre ar\u00eates, le graphe reste connexe:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "petersen.vertex_connectivity()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "petersen.edge_connectivity()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Programmation lin\u00e9aire\n", "\n", "La plupart des calculs pr\u00e9c\u00e9dents se ram\u00e8nent \u00e0 de la *programmation lin\u00e9aire en entiers*. Pour commencer, nous montrons comment r\u00e9soudre le programme lin\u00e9aire suivant:\n", "\n", "> $\\begin{array}{lrrrl}\\text{Max : } & x&+ y &- 3z\\\\\\text{Tel que : }& x&+2y &&\\leq 4 \\\\ & &- y &+ 5z &\\leq 8\\\\ \\end{array}$\n", "\n", "\u00e0 l'aide de Sage:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8.800000000...\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = MixedIntegerLinearProgram()\n", "x, y, z = p['x'], p['y'], p['z']\n", "p.set_objective ( x + y + 3*z )\n", "p.add_constraint( x + 2*y <= 4 )\n", "p.add_constraint( - y + 5*z <= 8 )\n", "p.solve()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p.get_values(x), p.get_values(y), p.get_values(z)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous resolvons maintenant le m\u00eame syst\u00e8me en imposant que $z$ soit entier:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8.0" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.set_integer(z)\n", "p.solve()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p.get_values(x), p.get_values(y), p.get_values(z)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Maintenant, nous montrons comment Sage calcule un ensemble ind\u00e9pendant maximal du graphe de Petersen:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 3, 6, 7]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "I = petersen.independent_set(); I" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "petersen.show(vertex_colors = {'red' : I})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La recherche d'un ensemble ind\u00e9pendant maximal peut s'encoder en le programme lin\u00e9aire en nombres entiers suivant:\n", "\n", "> $\\begin{array}{ll}\\text{Max : } & \\displaystyle\\sum_{v\\in E(G)} b_v \\\\\\text{Tel que : } & \\forall u,v\\in E(G),\\ b_u+b_v \\leq 1 \\\\ & b_v\\text{ variable binaire }\\end{array}$\n", "\n", "Ce qui en Sage donne:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "LP = MixedIntegerLinearProgram(maximization=True)\n", "b = LP.new_variable()\n", "LP.set_objective(sum([b[v] for v in petersen]))\n", "for (u,v) in petersen.edges(labels=None): # For any edge, we define a constraint\n", " LP.add_constraint(b[u]+b[v],max=1)\n", "LP.set_binary(b)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On trouve alors un ind\u00e9pendant de taille quatre:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4.0\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "LP.solve()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{0: 0.0, 1: 1.0, 2: 0.0, 3: 0.0, 4: 1.0, 5: 0.0, 6: 0.0, 7: 1.0, 8: 1.0, 9: 0.0}\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b_sol = LP.get_values(b)\n", "print b_sol" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 4, 7, 8]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "I = [ v for v in petersen.vertices() if b_sol[v] ]; I" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "petersen.show(vertex_colors = {'red' : I})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour finir, on manipule l'ensemble de tous les points entiers d'un polytope:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "A = random_matrix(ZZ,3,6,x=7)\n", "L = LatticePolytope(A)\n", "L.plot3d()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Un grand merci au passage \u00e0 Nathann Cohen qui a fourni une bonne part des exemples et fonctionnalit\u00e9s ci-dessus.\n", "\n", "## Cat\u00e9gories\n", "\n", "Comme on l'a vu, Sage a une large gamme de fonctionnalit\u00e9s, d\u00e9velopp\u00e9es par des enseignants, chercheurs et volontaires d'horizons tr\u00e8s diff\u00e9rents. Il int\u00e8gre de plus des outils dont les approches sont vari\u00e9es. Comment s'assurer qu'il conserve une certaine coh\u00e9rence interne?\n", "\n", "Revenons sur notre corps fini:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Finite Field of size 7" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K = GF(7); K" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Toujours dans l'id\u00e9e de mod\u00e9liser les math\u00e9matiques au plus pr\u00e8s, Sage a des informations sur la *structure math\u00e9matique* de $K$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Category of finite fields" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K.category()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voil\u00e0 ce qu'il peut en d\u00e9duire:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "graph = K.category().category_graph()\n", "graph.set_latex_options(format=\"dot2tex\")\n", "view(graph, viewer=\"pdf\", tightpage=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En quoi est-ce utile?\n", "\n", "1. Coh\u00e9rence des sp\u00e9cifications:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ " K.cardinality()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "42\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ " Partitions(10).cardinality()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ " EllipticCurve([GF(5)(0),0,1,-1,0]).cardinality()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Cela n'est cependant pas encore parfaitement au point:\n", "```{.python .input}\n", " LatticePolytope(A).npoints() # random\n", "```\n", "```{.json .output}\n", " [{\"data\": {\"text/plain\": \"4\"}, \"execution_count\": 1, \"metadata\": {}, \"output_type\": \"execute_result\"}]\n", "```\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. Partage de code g\u00e9n\u00e9rique:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "* 0 1 2 3 4 5 6\n", " +--------------\n", "0| 0 0 0 0 0 0 0\n", "1| 0 1 2 3 4 5 6\n", "2| 0 2 4 6 1 3 5\n", "3| 0 3 6 2 5 1 4\n", "4| 0 4 1 5 2 6 3\n", "5| 0 5 3 1 6 4 2\n", "6| 0 6 5 4 3 2 1\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ " K.multiplication_table(names = 'elements')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'sage.categories.magmas'" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ " K.multiplication_table.__module__" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " La hierarchie de cat\u00e9gorie est traduite automatiquement en une hierarchie de classes:\n", "```{.python .input}\n", " for cls in K.__class__.mro():\n", " print cls\n", "```\n", "```{.json .output}\n", " [{\"data\": {\"text/plain\": \"\\n...\\n\\n\\n\\n\\n\\n\\n...\\n\\n...\\n\\n...\\n\"}, \"execution_count\": 1, \"metadata\": {}, \"output_type\": \"execute_result\"}]\n", "```\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "3. Partage de tests g\u00e9n\u00e9riques:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "running ._test_additive_associativity() . . . pass\n", "running ._test_an_element() . . . pass\n", "running ._test_associativity() . . . pass\n", "running ._test_category() . . . pass\n", "running ._test_distributivity() . . . pass\n", "running ._test_elements() . . .\n", " Running the test suite of self.an_element()\n", " running ._test_category() . . . pass\n", " running ._test_eq() . . . pass\n", " running ._test_not_implemented_methods() . . . pass\n", " running ._test_pickling() . . . pass\n", " pass\n", "running ._test_elements_eq() . . . pass\n", "running ._test_enumerated_set_contains() . . . pass\n", "running ._test_enumerated_set_iter_cardinality() . . . pass\n", "running ._test_enumerated_set_iter_list() . . . pass\n", "running ._test_eq() . . . pass\n", "running ._test_len() . . . pass\n", "running ._test_not_implemented_methods() . . . pass\n", "running ._test_one() . . . pass\n", "running ._test_pickling() . . . pass\n", "running ._test_prod() . . . pass\n", "running ._test_some_elements() . . . pass\n", "running ._test_zero() . . . pass" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ " TestSuite(K).run(verbose=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A demonstration of Sage + GAP4 + GAP3 + Chevie + Semigroupe\n", "\n", "Let us create the Coxeter group W:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Permutation Group with generators [(3,8)(4,64)(7,12)(10,14)(11,16)(13,18)(15,20)(17,22)(19,23)(21,26)(24,27)(25,29)(28,30)(31,33)(34,36)(37,39)(40,43)(42,46)(45,48)(47,50)(49,52)(51,53)(59,60)(63,68)(67,72)(70,74)(71,76)(73,78)(75,80)(77,82)(79,83)(81,86)(84,87)(85,89)(88,90)(91,93)(94,96)(97,99)(100,103)(102,106)(105,108)(107,110)(109,112)(111,113)(119,120), (2,7)(3,63)(4,8)(5,10)(6,11)(9,13)(15,17)(19,21)(20,24)(22,27)(23,28)(26,30)(29,32)(33,35)(36,38)(37,40)(39,42)(41,45)(43,46)(44,47)(52,54)(53,55)(58,59)(62,67)(64,68)(65,70)(66,71)(69,73)(75,77)(79,81)(80,84)(82,87)(83,88)(86,90)(89,92)(93,95)(96,98)(97,100)(99,102)(101,105)(103,106)(104,107)(112,114)(113,115)(118,119), (1,5)(2,62)(3,7)(6,9)(8,12)(11,15)(13,17)(16,20)(18,22)(21,25)(26,29)(28,31)(30,33)(32,35)(34,37)(36,39)(38,41)(42,45)(46,48)(47,49)(50,52)(55,56)(57,58)(61,65)(63,67)(66,69)(68,72)(71,75)(73,77)(76,80)(78,82)(81,85)(86,89)(88,91)(90,93)(92,95)(94,97)(96,99)(98,101)(102,105)(106,108)(107,109)(110,112)(115,116)(117,118), (1,61)(2,6)(5,9)(7,11)(10,13)(12,16)(14,18)(15,19)(17,21)(20,23)(22,26)(24,28)(27,30)(31,34)(33,36)(35,38)(41,44)(45,47)(48,50)(49,51)(52,53)(54,55)(56,57)(62,66)(65,69)(67,71)(70,73)(72,76)(74,78)(75,79)(77,81)(80,83)(82,86)(84,88)(87,90)(91,94)(93,96)(95,98)(101,104)(105,107)(108,110)(109,111)(112,113)(114,115)(116,117)]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "W = CoxeterGroup([\"H\",4]); W" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is constructed as a group of permutations, from root data given by GAP3+Chevie (thanks to Franco's interface):" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "CoxeterGroup(\"H\",4)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "W._gap_group" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Gap3" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(W._gap_group).parent()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "with operations on permutations implemented in Sage:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3,8)(4,64)(7,12)(10,14)(11,16)(13,18)(15,20)(17,22)(19,23)(21,26)(24,27)(25,29)(28,30)(31,33)(34,36)(37,39)(40,43)(42,46)(45,48)(47,50)(49,52)(51,53)(59,60)(63,68)(67,72)(70,74)(71,76)(73,78)(75,80)(77,82)(79,83)(81,86)(84,87)(85,89)(88,90)(91,93)(94,96)(97,99)(100,103)(102,106)(105,108)(107,110)(109,112)(111,113)(119,120)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "W.an_element()^3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "and group operations implemented in GAP 4:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "34" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(W.conjugacy_classes_representatives())" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "14400" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "W.cardinality()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, assume we want to do intensive computations on this group, requiring heavy access to the left and right Cayley graphs (e.g. Bruhat interval calculations, representation theory, ...). Then we can use Jean-Eric Pin's Semigroupe, a software written in C:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "S = semigroupe.AutomaticSemigroup(W.semigroup_generators(), W.one(),\n", " category = CoxeterGroups().Finite())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following triggers the full expansion of the group and its Cayley graph in memory:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "14400" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S.cardinality()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And we can now iterate through the elements, in length-lexicographic order w.r.t. their reduced word:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "t" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var('t')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "t^60 + 4*t^59 + 9*t^58 + 16*t^57 + 25*t^56 + 36*t^55 + 49*t^54 + 64*t^53 + 81*t^52 + 100*t^51 + 121*t^50 + 144*t^49 + 168*t^48 + 192*t^47 + 216*t^46 + 240*t^45 + 264*t^44 + 288*t^43 + 312*t^42 + 336*t^41 + 359*t^40 + 380*t^39 + 399*t^38 + 416*t^37 + 431*t^36 + 444*t^35 + 455*t^34 + 464*t^33 + 471*t^32 + 476*t^31 + 478*t^30 + 476*t^29 + 471*t^28 + 464*t^27 + 455*t^26 + 444*t^25 + 431*t^24 + 416*t^23 + 399*t^22 + 380*t^21 + 359*t^20 + 336*t^19 + 312*t^18 + 288*t^17 + 264*t^16 + 240*t^15 + 216*t^14 + 192*t^13 + 168*t^12 + 144*t^11 + 121*t^10 + 100*t^9 + 81*t^8 + 64*t^7 + 49*t^6 + 36*t^5 + 25*t^4 + 16*t^3 + 9*t^2 + 4*t + 1" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum( t^p.length() for p in S)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 1], [2, 3]]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S[0:10]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 1, 2, 1, 3, 2, 1, 2, 1, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 3, 2, 1, 2, 3, 4]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S[-1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The elements of S are handles to C objects from `Semigroupe` :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = S.an_element()\n", "x" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Products are calculated by `Semigroupe` :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 1, 2, 3, 2, 4, 3]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x * x" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Powering operations are handled by Sage:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x^3" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 1, 2, 3, 2, 1, 2, 1, 3, 2, 4, 3, 2, 1, 2, 1, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x^(10^10000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Altogether, S is a full fledged Sage Coxeter group, which passes all the generic tests:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "running ._test_an_element() . . . pass\n", "...\n", "running ._test_has_descent() . . . pass\n", "...\n", "running ._test_reduced_word() . . . pass\n", "..." ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "TestSuite(S).run(verbose = True, skip = \"_test_associativity\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And of course it works for general semigroups too, and can further compute much more information about those, like the (Knuth-Bendix completion of the) relations between the generators:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "W = CoxeterGroup([\"A\",3])\n", "S = semigroupe.AutomaticSemigroup(W.simple_reflections(), W.one())" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "aa = 1\n", "bb = 1\n", "ca = ac\n", "cc = 1\n", "bab = aba\n", "cbc = bcb\n", "cbac = bcba" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S.print_relations()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "which contains the usual commutation + braid relations.\n", "\n", "Let's try now the 0-Hecke monoid:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "24" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sage.combinat.j_trivial_monoids import *\n", "S = semigroupe.AutomaticSemigroup(W.simple_projections(), W.one(), by_action = True)\n", "S.cardinality()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "aa = a\n", "bb = b\n", "ca = ac\n", "cc = c\n", "bab = aba\n", "cbc = bcb\n", "cbac = bcba\n", "abacba = 0\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S.print_relations()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "24\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S.cardinality()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[121321]\n", "-[121321] - [21321] + [2132] + [13] - [12132] + [2321] - [132] + [1213] - [12321] + [1232] + [1321] - [213]\n", "[232] - [2321] - [1232] + [12321]\n", "[121321] - [21321] + [32] + [12] - [12132] - [2] + [] - [121] + [2321] - [12321] - [321] + [23] + [2132] + [13] - [232] - [123] + [21] - [213] + [1213] - [3] + [1232] + [1321] - [1] - [132]\n", "[121] - [1213] + [12321] - [1321]\n", "-[12] + [21321] - [2132] - [232] + [12132] + [2] - [21] + [121] + [132] - [1213] - [1321] + [213]\n", "-[121321] + [21321] - [32] + [12132] - [2321] + [12321] + [321] - [23] - [2132] - [13] + [232] + [123] + [213] - [1213] + [3] - [1232] - [1321] + [132]\n", "-[121] - [13] + [1213] - [12321] + [1321] + [1]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = semigroupe.AutomaticSemigroup(W.simple_projections(), W.one(), by_action = True,\n", " category = JTrivialMonoids().Finite())\n", "H = S.algebra(QQ)\n", "H._repr_term = lambda x: '['+''.join(str(i) for i in x.reduced_word())+']'\n", "for x in H.orthogonal_idempotents():\n", " print x" ] } ], "metadata": { "kernelspec": { "display_name": "sagemath", "name": "sagemath" } }, "nbformat": 4, "nbformat_minor": 2 }