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.

Depuis quelques jours ce site web est hébergé à l'adresse www.slabbe.org. Le déménagement devrait être transparent sauf pour les abonnements au flux RSS de ce blogue auquel je n'ai pas encore trouvé une manière de rendre le déménagement transparent.

Si vous êtes abonné au flux RSS de ce blogue, mieux vaut faire la transition à la main et se réabonner à la nouvelle adresse:

http://www.slabbe.org/blogue/feed/atom/index.xml

En 2013, j'avais écrit cet article d'opinions au sujet de l'organisation de l'ultimate en France. Certaines choses ont évolué pour le mieux depuis (un match d'ultimate pour décider de la meilleure équipe d'ultimate en France) d'autres non. Aujourd'hui, en 2015, j'ai trois propositions à suggérer à la fédération française d'ultimate (FFDF) et je vais les décrire dans trois messages de blogue distincts au fur et à la mesure que je trouve le temps pour les rédiger. Ma première proposition (avril 2015) concernait la mise à jour de la règle de bris d'égalité. Ma deuxième proposition (mai 2015) concernait la restructuration du Championnat de France pour s'assurer de rassembler les meilleures équipes du pays via des phases de qualifications régionales. Ma troisième (juin 2015) concerne la sélection de l'Équipe de France et c'est celle que je décris dans ce texte.

Sélection de l'équipe de France

En France si j'ai bien compris, pour former l'équipe nationale, on sélectionne d'abord le sélectionneur qui lui va ensuite sélectionner les joueurs qui formeront une équipe. Ça semble être la façon de fonctionner dans tous les sports. Du moins, pour le soccer, je sais que c'est comme ça surtout après la Coupe du monde en Afrique du Sud, car on n'en avait entendu parler...

J'imagine que c'est difficile d'imaginer un autre système si tous les sports fonctionnent de cette manière. Pourtant il en existe d'autres manières. Et comme je connais d'autres manières, je me questionne sur quelle est la meilleure compte tenu du contexte de l'ultimate en France en 2015.

Une équipe

Selon mon expérience, une équipe avec des joueurs donnés a besoin de trois ans pour atteindre son sommet de performance. À ce sujet, vous pouvez lire un texte que j'avais écrit en 2013 au sujet du nombre d'années qu'ont pris les 5 équipes québécoises qui ont gagné les championnats canadiens au cours des dernières années. La première année, c'est l'apprentissage à jouer ensemble, ce qui inclut beaucoup trop d'erreurs de communication sur le terrain pour pouvoir viser la performance. La deuxième année, c'est une première occasion de viser la performance, mais souvent l'expérience d'équipe n'y est pas et on perd en demie-finale ou en finale à cause d'erreurs qui ne s'étaient jamais produites avant, car c'est la première fois qu'on essayait de performer. Puis, la troisième année, habituellement, c'est la bonne, car la communication est bonne et on a l'expérience des matchs importants et des erreurs à ne pas refaire dans les situations importantes.

Ces trois années ne sont pas des années où on regarde le temps passer. Le développement de l'équipe ne se fait pas tout seul. Il lui faut des rencontres hebdomadaires sinon bihebdomadaires pendant toute la période pour assurer cette progression. Il faut du temps pour définir un système de jeu d'équipe incluant les mouvements en défensives et en attaque. On parle par exemple de 500 heures de temps de pratique et peut-être de 300 heures de tournois. C'est un long travail. Tellement de travail et d'énergie qu'un joueur de cette équipe ne pourrait jamais imaginer jouer dans deux équipes visant le même niveau de jeu.

Pour moi, une équipe, c'est beaucoup plus qu'une sélection. Bien sûr, les équipes de France d'ultimate font des entraînements (des stages comme ils sont appelés) une dizaine par année peut-être. Mais avec les transports, le temps et les coûts élevés que nécessitent chacun de ces entraînements, il est difficile d'atteindre le nombre d'heures d'entraînement qu'un club peut se permettre. D'autant plus que les mêmes joueurs en France sont sur-solicités en participant à de multiples équipes en parallèle. En effet, il est tout à fait normal en France pour un joueur de participer au championnat de France mixte, au championnat de France open, au championnat du monde sur plage et au championnat d'Europe des nations avec quatre équipes différentes et dans la même année. À mon avis, cet éparpillement est tout à fait orthogonal à l'optimisation des résultats de l'une ou de l'autre de ces équipes.

En considérant le contexte actuel de l'ultimate, les équipes qui représentent la France à l'international sont loin d'atteindre le niveau de jeu qu'elles pourraient atteindre si elles étaient choisies autrement.

Comment devrait-on choisir les équipes de France?

Je crois que la sélection des joueurs qui représentent la France à l'international devrait se baser un peu plus sur la structure actuelle de formation des équipes en France: les clubs.

Une équipe se rend en finale des Championnats de France. Une équipe gagne les Championnats de France. Cela prend déjà au moins deux bonnes années d'énergie à ces deux équipes pour se rendre là. Deux bonnes années d'apprentissages et d'adaptations suites aux défaites qui ont précédé la joute et la victoire du championnat de France. Certainement que plusieurs des joueurs qui jouent la finale du Championnat de France feront partie de l'équipe qui représentera la France peu importe la méthode qui sera choisie pour sélectionner l'équipe de France. La question que je me pose est: pourquoi ne pas profiter des apprentissages, de l'expérience et d'un système de jeu qui a fait ces preuves devant toute la communauté d'ultimate d'une nation pour représenter cette même nation à l'international?

Selon moi c'est ce qui serait le mieux pour la France: l'équipe qui remporte le Championnat de France devient le comité de sélection de l'équipe de France pour les prochains Championnats du monde et d'Europe des nations. C'est elle qui choisi les entraîneurs. C'est elle qui choisit les joueurs. C'est elle qui sait comment utiliser la prochaine année pour continuer son développement et pour repousser plus loin les limites et se basant sur les acquis qui ont fait leur preuve.

La Fédération peut très bien ajouter des règles de représentation nationale. Par exemple, le club doit sélectionner au moins 5 joueurs faisant partie d'un autre club. Ce sera au club champion de décider quels sont les 5 (ou plus) joueurs qui compléteront le mieux l'équipe championne en place. Typiquement, ces joueurs supplémentaires proviendront de l'équipe finaliste mais ce n'est pas obligé. La fédération pourrait aussi exiger que ces joueurs proviennent d'au moins trois autres clubs pour permettre une plus grande diffusion des connaissances et expériences acquises du fait de faire partie de l'équipe nationale.

Les avantages d'une sélection basée sur le championnat de France

Je vois plusieurs avantages à ce modèle pour la sélection de l'équipe de France:

• Permet d'éviter l'éparpillement (un joueur joue soit pour son club, soit pour l'équipe nationale) donc la concentration sur un seul et même but sur une même année;
• Permet de former une équipe automatiquement efficace, car on sait qui sont les chefs, les leaders. On écoute les gagnants, quoi de plus naturel?
• Fait en sorte que l'équipe de France se base sur une équipe existante qui a fait ses preuves dont la phase d'apprentissage et de multiples erreurs de communication est passée;
• Fait en sorte qu'une année est suffisante pour intégrer les nouveaux joueurs choisis parmi les autres clubs;
• Fait en sorte que l'équipe de France est une équipe mature et prête à performer;
• À plus long terme, ce modèle oriente les clubs sur le développement d'équipes performantes plutôt que de joueurs spectaculaires (mais inefficaces) espérant être sélectionnés.

Pour une France forte. Pour une France performante à l'international d'ici quelques années.