Sébastien Labbé

Voici un texte que j'ai transmis à la revue d'urbanisme Dérivations pour son deuxième numéro au sujet du campus du Sart Tilman de l'Université de Liège.

En janvier 2015, j'ai commencé un postdoctorat à l'Université de Liège. Peu après, ma femme et mon fils m'ont rejoint. Nous avons choisis d'habiter au centre-ville de Liège, car nous aimons la vie sans voiture et la proximité des services. Il faut dire qu'il n'y a pas tant de terrains de jeu pour enfants à proximité du centre-ville, mais on a trouvé un modeste parc accueillant (avec un cercle de cacas de chiens à son entrée) qui nous convient.

À mon arrivée, il y avait une liste d'attente pour les crèches du centre-ville et quelques places à la crèche du Sart Tilman. Nous avons donc inscrit mon garçon à la crèche du Sart-Tilman avant qu'il commence l'école. À ce moment, mon algorithme pour me rendre au travail était semble-t-il unique pour deux raisons: (1) traverser le centre-ville à vélo via le Ravel et vérouiller le vélo au pont de la Fragnée et (2) prendre le 48 avec un enfant. En effet, on m'a souvent déconseillé de laisser un vélo à un tel endroit ou encore de m'acheter une voiture maintenant que je suis papa. Bon, pour moi, ça restait quand même la meilleure solution au problème de transport vers le campus Sart Tilman.

Je déposais donc mon fils à la crèche. Il me restait donc à me rendre de la crèche à mon travail. Comme ce n'était pas si loin, je faisais ce trajet à pied. N'importe où dans le monde, on serait porté à croire que marcher de la crèche d'un campus universitaire à son travail sur le même campus est normal et qu'un trajet raisonable pour le faire à pied devrait exister. Les campus à l'américaine sont toujours plein de trajets piétons que l'on reconnaît dans la pelouse usée et qui indiquent toujours le plus court chemin: la diagonale. À la recherche de cette diagonale, je marchais sur la Rue du Sart-Tilman jusqu'au Monument aux héros des combats de la nuit du 5 au 6 août 1914 que peu de gens connaissent. C'est à partir de là que tout se gâte et que le petit chemin le plus court propre aux campus universitaires à l'américaine n'existe plus.

La première fois, muni de l'application Open Street Map sur mon téléphone, j'avais fait l'erreur de contourner l'Institut de Géographie par la rue du Clos Mercator. J'étais abouti sur les bretelles d'autoroute. Chemin désagréable et boueux. À ne pas refaire.

La deuxième fois, j'ai marché dans la pelouse entre l'Institut de Géographie et le Boulevard de Colonster jusqu'au rond point au centre du campus. Ce rond-point n'est pas si désagréable pour les piétons. En effet, les voitures ralentissent à moins de 80 km/h à la vue d'un piéton et prennent leur distance pour s'assurer de rouler toujours à plus de 20 cm de ceux-ci.

J'ai pu faire ce trajet jusqu'aux périodes d'allergies du mois de juin. En effet, comme j'étais finalement le seul à passer par là à tous les jours, mes piétinements n'étaient pas suffisants pour prendre le dessus sur les plantes. À partir de ce moment-là, je marchais sur le Boulevard de Colonster. Il n'y a pas de trottoir à cet endroit, et le manque de visibilité causé par les plantes et le stationnement P11 font en sorte que les voitures ne roulent pas dans la voie de gauche à cet endroit à l'approche du rond point. Je me suis donc habitué aux voitures qui passent très proche des piétons là aussi et même aux conducteurs du bus 58 qui osent même faire des blagues en dirigeant l'autobus sur les piétons pour les éviter à la dernière seconde.

Depuis l'automne, je n'ai plus besoin de faire ce merveilleux trajet de la crèche à l'Institut de mathématiques, car mon fils a commencé à l'école en ville. Je profite maintenant du nouveau trajet piéton qui contourne le rond-point par le sud.

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.