Sébastien Labbé

Yesterday I received this email (in french):

Salut,
avec Thomas on a une question bête:

K.<x>=NumberField(x*x-x-1)

J'aimerais multiplier une matrice avec des coefficients en x par un vecteur
contenant des variables a et b.  Il dit "unsupported operand parent for *,
Matrix over number field, vector over symbolic ring"

Est ce grave ?

Here is my answer. Indeed, in Sage, symbolic variables can't multiply with elements in an Number Field in x:

sage: x = var('x')
sage: K.<x> = NumberField(x*x-x-1)
sage: a = var('a')
sage: a*x
Traceback (most recent call last)
...
TypeError: unsupported operand parent(s) for '*': 'Symbolic Ring' and
'Number Field in x with defining polynomial x^2 - x - 1'

But, we can define a polynomial ring with variables in a,b and coefficients in the NumberField. Then, we are able to multiply a with x:

sage: x = var('x')
sage: K.<x> = NumberField(x*x-x-1)
sage: K
Number Field in x with defining polynomial x^2 - x - 1
sage: R.<a,b> = K['a','b']
sage: R
Multivariate Polynomial Ring in a, b over Number Field in x with
defining polynomial x^2 - x - 1
sage: a*x
(x)*a

With two square brackets, we obtain powers series:

sage: R.<a,b> = K[['a','b']]
sage: R
Multivariate Power Series Ring in a, b over Number Field in x with
defining polynomial x^2 - x - 1
sage: a*x*b
(x)*a*b

It works with matrices:

sage: MS = MatrixSpace(R,2,2)
sage: MS
Full MatrixSpace of 2 by 2 dense matrices over Multivariate Power
Series Ring in a, b over Number Field in x with defining polynomial
x^2 - x - 1
sage: MS([0,a,b,x])
[  0   a]
[  b (x)]
sage: m1 = MS([0,a,b,x])
sage: m2 = MS([0,a+x,b*b+x,x*x])
sage: m1 + m2 * m1
[              (x)*b + a*b       (x + 1) + (x + 1)*a]
[                (x + 2)*b (3*x + 1) + (x)*a + a*b^2]

(En réaction à la lettre d’opinion Une fois encore de Paul Dostie, en page 4 de l’édition du 1er janvier 2016 de l'Écho de Frontenac. Cette réponse a été publiée le 7 janvier 2016 sur le site de l'Écho de Frontenac sous le titre choisi par le journal Difficile équilibre. Lire la réponse de Paul Dostie Prise 2 publiée le 14 janvier 2016.)

Cher Paulo,

Je comprends ton inquiétude. La rue Frontenac sera bientôt reconstruite et l'on voudrait si possible éviter de regretter les décisions qui sont prises aujourd'hui. Ton invitation à "apporter de l'eau au moulin" est légitime, mais pourquoi alors passe-t-elle sous silence la démarche qui a eu lieu à Lac-Mégantic pour repenser le centre-ville (dont la rue Frontenac) à l'image de ses citoyens à l'époque d'un 21e siècle qui ne fait que commencer?

Je comprends aussi ton désespoir à trouver un équilibre entre les contraires. Tu voudrais éviter que "l'architecture projetée ressemble à du déjà vu", mais que la chaussée de la rue Frontenac soit large comme avant. Tu mentionnes la cession du boulevard des Vétérans à l'industrie touristique, alors qu'ironiquement tu cites l'avenue des Champs-Élysées comme modèle de rue large et belle. Selon Wikipédia, la qualification de "plus belle avenue du monde" des Champs-Élysées serait due à Achille Hermant et date de 1856. Or, les choses ont changé depuis 160 ans et on s'inquiète plutôt depuis plusieurs années d'une certaine "banalisation" des Champs avec des magasins que l'on retrouve, identiques, partout ailleurs dans le monde.

Même si c'est une ville qui comporte à peine 15 millions d'habitants de plus que Lac-Mégantic, je trouve que la référence à Paris est une occasion de mentionner des initiatives de développement durable que Paris a prises ces dernières années et continue de prendre.

Le parc Martin Luther King est un grand parc accessible depuis quelques années dans le 17e arrondissement et qui atteindra 10 hectares une fois terminé. Construit sur les anciens terrains d'une gare ferroviaire dans une optique de développement durable réussie, il déborde de citoyens qui profitent des multiples lieux pour faire du sport, faire jouer les enfants, profiter de la nature (étang, ruches, arbres, etc.) et faire changement des parcs à la Louis XIV.

Le processus de réinvention d'une ville par ses citoyens n'est pas unique à Lac-Mégantic: c'est l'air du temps. Et Paris dirigée par Anne Hidalgo, première femme maire de Paris se réinvente aussi. Son site web paris.fr héberge des ateliers de réflexion sur la co-construction de Paris. Un projet en cours s'intitule "Réinventons nos places !" (les rond-points géants de Paris s'appellent des Places) dont le but est d'apaiser l’espace public, rééquilibrer les usages au profit des piétons et des circulations douces. Bastille, Fête, Gambetta, Italie, Madeleine, Nation et Panthéon sont les sept premières places visées par la démarche de concertation citoyenne. Soyons certains que la chaussée sera bientôt beaucoup moins large pour les voitures... Soulignons aussi l'approbation par le Conseil de Paris en décembre 2015 du projet de piétonniser dès l'été 2016 les quais de la rive droite de la Seine sur une longueur de 3,3 km suite à une large consultation.

Pour ce qui est du stationnement, je conseille la lecture du texte Espace public et stationnement rédigé par l'association Rue de l'avenir. Ce document explique que l'espace utilisé par les stationnements peut avoir d'autres utilités plus utiles.

Sébastien Labbé

These is a summary of the functionalities present in slabbe-0.2.spkg optional Sage package. It works on version 6.8 of Sage but will work best with sage-6.10 (it is using the new code for cartesian_product merged the the betas of sage-6.10). It contains 7 new modules:

• finite_word.py
• language.py
• lyapunov.py
• matrix_cocycle.py
• mult_cont_frac.pyx
• ranking_scale.py
• tikz_picture.py

Cheat Sheets

The best way to have a quick look at what can be computed with the optional Sage package slabbe-0.2.spkg is to look at the 3-dimensional Continued Fraction Algorithms Cheat Sheets available on the arXiv since today. It gathers a handful of informations on different 3-dimensional Continued Fraction Algorithms including well-known and old ones (Poincaré, Brun, Selmer, Fully Subtractive) and new ones (Arnoux-Rauzy-Poincaré, Reverse, Cassaigne).

Installation

sage -i http://www.slabbe.org/Sage/slabbe-0.2.spkg    # on sage 6.8
sage -p http://www.slabbe.org/Sage/slabbe-0.2.spkg    # on sage 6.9 or beyond

Examples

Computing the orbit of Brun algorithm on some input in \(\mathbb{R}^3_+\) including dual coordinates:

sage: from slabbe.mult_cont_frac import Brun
sage: algo = Brun()
sage: algo.cone_orbit_list((100, 87, 15), 4)
[(13.0, 87.0, 15.0, 1.0, 2.0, 1.0, 321),
 (13.0, 72.0, 15.0, 1.0, 2.0, 3.0, 132),
 (13.0, 57.0, 15.0, 1.0, 2.0, 5.0, 132),
 (13.0, 42.0, 15.0, 1.0, 2.0, 7.0, 132)]

Computing the invariant measure:

sage: fig = algo.invariant_measure_wireframe_plot(n_iterations=10^6, ndivs=30)
sage: fig.savefig('a.png')

Drawing the cylinders:

sage: cocycle = algo.matrix_cocycle()
sage: t = cocycle.tikz_n_cylinders(3, scale=3)
sage: t.png()

Computing the Lyapunov exponents of the 3-dimensional Brun algorithm:

sage: from slabbe.lyapunov import lyapunov_table
sage: lyapunov_table(algo, n_orbits=30, n_iterations=10^7)
  30 succesful orbits     min       mean      max       std
+-----------------------+---------+---------+---------+---------+
  $\theta_1$              0.3026    0.3045    0.3051    0.00046
  $\theta_2$              -0.1125   -0.1122   -0.1115   0.00020
  $1-\theta_2/\theta_1$   1.3680    1.3684    1.3689    0.00024

Dealing with tikzpictures

Since I create lots of tikzpictures in my code and also because I was unhappy at how the view command of Sage handles them (a tikzpicture is not a math expression to put inside dollar signs), I decided to create a class for tikzpictures. I think this module could be useful in Sage so I will propose its inclusion soon.

I am using the standalone document class which allows some configurations like the border:

sage: from slabbe import TikzPicture
sage: g = graphs.PetersenGraph()
sage: s = latex(g)
sage: t = TikzPicture(s, standalone_configs=["border=4mm"], packages=['tkz-graph'])

The repr method does not print all of the string since it is often very long. Though it shows how many lines are not printed:

sage: t
\documentclass[tikz]{standalone}
\standaloneconfig{border=4mm}
\usepackage{tkz-graph}
\begin{document}
\begin{tikzpicture}
%
\useasboundingbox (0,0) rectangle (5.0cm,5.0cm);
%
\definecolor{cv0}{rgb}{0.0,0.0,0.0}
...
... 68 lines not printed (3748 characters in total) ...
...
\Edge[lw=0.1cm,style={color=cv6v8,},](v6)(v8)
\Edge[lw=0.1cm,style={color=cv6v9,},](v6)(v9)
\Edge[lw=0.1cm,style={color=cv7v9,},](v7)(v9)
%
\end{tikzpicture}
\end{document}

There is a method to generates a pdf and another for generating a png. Both opens the file in a viewer by default unless view=False:

sage: pathtofile = t.png(density=60, view=False)
sage: pathtofile = t.pdf()

Compare this with the output of view(s, tightpage=True) which does not allow to control the border and also creates a second empty page on some operating system (osx, only one page on ubuntu):

sage: view(s, tightpage=True)

One can also provide the filename where to save the file in which case the file is not open in a viewer:

sage: _ = t.pdf('petersen_graph.pdf')

Another example with polyhedron code taken from this Sage thematic tutorial Draw polytopes in LateX using TikZ:

sage: V = [[1,0,1],[1,0,0],[1,1,0],[0,0,-1],[0,1,0],[-1,0,0],[0,1,1],[0,0,1],[0,-1,0]]
sage: P = Polyhedron(vertices=V).polar()
sage: s = P.projection().tikz([674,108,-731],112)
sage: t = TikzPicture(s)
sage: t
\documentclass[tikz]{standalone}
\begin{document}
\begin{tikzpicture}%
        [x={(0.249656cm, -0.577639cm)},
        y={(0.777700cm, -0.358578cm)},
        z={(-0.576936cm, -0.733318cm)},
        scale=2.000000,
...
... 80 lines not printed (4889 characters in total) ...
...
\node[vertex] at (1.00000, 1.00000, -1.00000)     {};
\node[vertex] at (1.00000, 1.00000, 1.00000)     {};
%%
%%
\end{tikzpicture}
\end{document}
sage: _ = t.pdf()

Some years ago, I wrote code in Sage to solve the Quantumino puzzle. I also used it to make a one-minute video illustrating the Dancing links algorithm which I am proud to say it is now part of the Dancing links wikipedia page.

Let me recall that the goal of the Quantumino puzzle is to fill a \(2\times 5\times 8\) box with 16 out of 17 three-dimensional pentaminos. After writing the sage code to solve the puzzle, one question was left: how many solutions are there? Is the official website realist or very prudent when they say that there are over 10.000 potential solutions? Can it be computed in hours? days? months? years? The only thing I knew was that the following computation (letting the 0-th pentamino aside) never finished on my machine:

sage: from sage.games.quantumino import QuantuminoSolver
sage: QuantuminoSolver(0).number_of_solutions()   # long time :)

Since I spent already too much time on this side-project, I decided in 2012 to stop investing any more time on it and to really focus on finishing writing my thesis.

So before I finish writing my thesis, I knew that the computation was not going to take a light-year, since I was able to finish the computation of the number of solutions when the 0-th pentamino is put aside and when one pentamino is pre-positioned somewhere in the box. That computation completed in 4 hours on my old laptop and gave about 5 millions solutions. There are 17 choices of pentatminos to put aside, there are 360 distinct positions of that pentamino in the box, so I estimated the number of solution to be something like \(17\times 360\times 5000000 = 30 \times 10^9\). Most importantly, I estimated the computation to take \(17\times 360\times 4= 24480\) hours or 1020 days. Therefore, I knew I could not do it on my laptop.

But last year, I received an email from the designer of the Quantumino puzzle:

-------- Message transféré --------
Sujet : quantumino
Date : Tue, 09 Dec 2014 13:22:30 +0100
De : Nicolaas Neuwahl
Pour : Sebastien Labbe

hi sébastien labbé,

i'm the designer of the quantumino puzzle.
i'm not a mathematician, i'm an architect. i like mathematics.
i'm quite impressed to see the sage work on quantumino, also i have not the
knowledge for full understanding.

i have a question for you - can you tell me HOW MANY different quantumino-
solutions exist?

ty and bye

nicolaas neuwahl

This summer was a good timing to launch the computation on my beautiful Intel® Core™ i5-4590 CPU @ 3.30GHz × 4 at Université de Liège. First, I improved the Sage code to allow a parallel computation of number of solutions in the dancing links code (#18987, merged in a Sage 6.9.beta6). Secondly, we may remark that each tiling of the \(2\times 5\times 8\) box can be rotated in order to find 3 other solutions. It is possible to gain a factor 4 by avoiding to count 4 times the same solution up to rotations (#19107, still needs work from myself). Thanks to Vincent Delecroix for doing the review on both ticket. Dividing the estimated 1024 days of computation needed by a factor \(4\times 4=16\) gives an approximation of 64 days to complete the computation. Two months, just enough to be tractable!

With those two tickets (some previous version to be honest) on top of sage-6.8, I started the computation on August 4th and the computation finished last week on September 18th for a total of 45 days. The computation was stopped only once on September 8th (I forgot to close firefox and thunderbird that night...).

The number of solutions and computation time for each pentamino put aside together with the first solution found is shown in the table below. We remark that some values are equal when the aside pentaminoes are miror images (why!?:).

634 900 493 solutions	634 900 493 solutions
2 days, 6:22:44.883358	2 days, 6:19:08.945691
509 560 697 solutions	509 560 697 solutions
2 days, 0:01:36.844612	2 days, 0:41:59.447773
628 384 422 solutions	628 384 422 solutions
2 days, 7:52:31.459247	2 days, 8:44:49.465672
1 212 362 145 solutions	1 212 362 145 solutions
3 days, 17:25:00.346627	3 days, 19:10:02.353063
197 325 298 solutions	556 534 800 solutions
22:51:54.439932	1 day, 19:05:23.908326
664 820 756 solutions	468 206 736 solutions
2 days, 8:48:54.767662	1 day, 20:14:56.014557
1 385 955 043 solutions	1 385 955 043 solutions
4 days, 1:40:30.270929	4 days, 4:44:05.399367
694 998 374 solutions	694 998 374 solutions
2 days, 11:44:29.631	2 days, 6:01:57.946708
1 347 221 708 solutions
3 days, 21:51:29.043459

Therefore the total number of solutions up to rotations is 13 366 431 646 which is indeed more than 10000:)

sage: L = [634900493, 634900493, 509560697, 509560697, 628384422,
628384422, 1212362145, 1212362145, 197325298, 556534800, 664820756,
468206736, 1385955043, 1385955043, 694998374, 694998374, 1347221708]
sage: sum(L)
13366431646
sage: factor(_)
2 * 23 * 271 * 1072231

My code will be available on github.

About the video on wikipedia.

I must say that the video is not perfect. On wikipedia, the file talk page of the video says that the Jerky camera movement is distracting. That is because I managed to make the video out of images created by .show(viewer='tachyon') which changes the coordinate system, hardcodes a lot of parameters, zoom properly, simplifies stuff to make sure the user don't see just a blank image. But, for making a movie, we need access to more parameters especially the placement of the camera (to avoid the jerky movement). I know that Tachyon allows all of that. It is still a project that I have to create a more versatile Graphics3D -> Tachyon conversion allowing to construct nice videos of evolving mathematical objects. That's another story.

Voici le nombre d'équipes par tournoi pendant la saison 2014-2015 selon les données d'Alexandre Dion, directeur des opérations de la FQU

Série 1000:
Mars Attaque  116
Bye Bye        56
Coup de Foudre 56
Movember       64

Série 666:
La Flotte      14 ?
Oktober Disk   40
Bonne Année    48

Série 333 :
Victo Bowl     22
La Virée        8
Atache t'ajjuq 13

Dans chaque série, il y a un tournoi deux fois plus grand que les autres en terme de nombre d'équipes:

• en série 1000, le Mars attaque accueille 120 équipes vs 60 pour les autres,
• en série 666, Oktober Disk et Bonne Année accueillent 40 équipes vs 20 pour La Flotte,
• en série 333, le Victobowl accuillent 20 équipes vs 10 pour les autres.

En général, il y a une corrélation entre la facilité/difficulté de gagner un tournoi et le nombre d'équipes présentes. Mais pas toujours. Par exemple, gagner le Mars Attaque n'est pas tellement plus difficile que de gagner le Coup de foudre, car ce sont les mêmes équipes dans le top 10.

Je rappelle que depuis la saison 2014-2015,

• en série 1000, 100 équipes obtiennent des points,
• en série 666, 50 équipes obtiennent des points,
• en série 333, 24 équipes obtiennent des points.

La longueur de ces échelles permet de donner des points à toutes les équipes (sauf les 20 dernières du Mars Attaque). Ceci avait été une volonté formulée par la FQU en août 2014.

Le système a toujours permis de donner des points de façon équitable de tournois en tournois aux équipes fortes : 1000 points si tu gagnes tel tournoi, 1000 points si tu gagnes tel autre tournoi: c'est égal. Mais pas aux équipes faibles! Si une équipe perd tous ses matchs, elle peut tantôt avoir 0 pts (au Mars Attaque) et tantôt avoir près de 200 points (La Flotte). La raison de ce problème est que les tournois d'une même série n'accueillent pas le même nombre d'équipes. Comme on l'a vu plus haut, dans chaque série, il y a des tournois deux fois plus petits que d'autres. C'est ce qui donne beaucoup ou peu de points à la dernière équipe :

• Série 1000: 100 points sont donnés à la dernière équipe (disons 60e) du Coup de Foudre et 0 pts à la dernière du Mars Attaque
• Série 666: 173 points sont donnés à la dernière équipe (disons 20e) de La Flotte et 2 pts à la dernière du Bonne année (48e)
• Série 333: 122 points sont donnés à la dernière équipe (disons 8e) de la Virée et 2 pts à la dernière du VictoBowl (22e)

Et plus problématique encore, si moi, je décide d'organiser un tournoi de la série 333 dans le fin fond de la forêt et que seulement trois équipes hyper faibles y participent, alors 333, 286 et 248 points seront respectivement donnés à ces équipes faibles ce qui est beaucoup trop.

Afin de corriger ce problème, il existe une solution. Il suffit d'établir un nombre minimal d'équipes par série. Par exemple:

• Série 1000: minimum 40 équipes
• Série 666: minimum 20 équipes
• Série 333: minimum 10 équipes

Si un tournoi atteint le minimum, alors on donne les points de façon habituelle. Si un tournoi accueille moins d'équipes que le minimum requis. Alors, les "équipes manquantes" obtiennent les meilleurs points offerts par le tournoi. Je m'explique. Si j'organise un tournoi 333 qui accueille seulement trois équipes. Alors, il manque 7 équipes pour avoir le minimum. Donc, l'équipe qui gagne mon tournoi obtient les points d'une 8e place d'une tournoi du 333 donc, 122 points. Un autre exemple réel et basé sur la saison dernière celui-là. Si 14 équipes vont à La Flotte, alors il manque 6 équipes. Donc l'équipe gagnante du tournoi La Flotte obtient les points d'une 7e place dans la série 666, donc 432 points.