Sébastien Labbé

In 2015, Emmanuel Jeandel and Michael Rao discovered a very nice set of 11 Wang tiles which can be encoded geometrically into the following set of 11 geometrical shapes:

Jeandel and Rao proved that you may tile the plane with infinitely many translated copies of these tiles, but never periodically:

There is an easy way to construct Jeandel-Rao tilings from a well-chosen polygonal partition of the plane.

This is the polygonal partition:

A lattice, represented below by the set of intersection of two perpendicular set of gridlines, is placed at a random position on top of the partition:

Each point of the lattice can be associated to an index from 0 to 10 according to which polygon of the partition it falls in. This defines a configuration of indices associated to each integer coordinate:

This procedure can be done all the way up to infinity. The chosen placement of the lattice defines a valid tiling of the plane with Jeandel-Rao tiles!

Since the size of the fundamental domain of the polygonal partition is irrational (width is golden mean, height is golden mean + 3, while the distance between two parallel gridlines is 1 unit), the generated configuration must be non-periodic.

It was a pleasure for me to do illustrate this to Emmanuel Jeandel during the workshop Multidimensional symbolic dynamics and lattice models of quasicrystals at CIRM in April 2024 in Marseille.

Do it yourself

Here are the 3 files allowing to reproduce this experiment:

• A 33 x 19 rectangular valid patch of 627 tiles to use to cut a 1 meter x 60 cm wooden flat sheet (in svg format for laser cutting, pieces should have a side length of exactly 3 cm after the operation)
• The polygonal partition to be printed on a A3 paper (1 unit = 3 cm)
• The lattice \(\mathbb{Z}^2\) represented by gridlines 3cm apart to be printed on A4 paper (1 unit = 3 cm)

Alternate files for laser cutting the tiles

I first cut those tiles in August 2018 before a conference in Durham with the help of David Renault. We made more of them in June 2019. Each time David does some changes to the file that I provide to him with InkScape. Here are three alternate files for laser cutting the tiles.

• as modified by David Renault in June 2019 just before laser cutting
• where the indices of the tiles are underlined
• where the indices of the tiles are underlined and modified by David

Discussion

The construction of valid tilings with Jeandel-Rao tiles from a polygonal partition is a generalization of a well-known phenomenon in one dimension, namely, the fact that Sturmian sequences of complexity \(n+1\) are coded by irrational rotations. For example, here is an easy way to construct Sturmian sequences using a partition of the line into two intervals of different lengths. Similarly as above, every point from a set of equidistanced points is coded by letter A or B according to which of the two intervals it falls in.

The question that one may ask is whether all Jeandel-Rao tilings can be constructed from such a starting point in the partition. For Sturmian sequences, the answer is yes and the starting point can be described using the Ostrowski numeration system and the continued fraction expansion of the slope defined from the ratio of frequencies of the letters in the sequence. In one dimension, the proof is thus based on the desubstitution of Sturmian sequences on the one hand, and the Rauzy induction of irrational rotations on the other hand.

The same approach can be performed for Jeandel-Rao tilings using 2-dimensional desubstitution of Wang tilings and 2-dimensional Rauzy induction of toral \(\mathbb{Z}^2\)-rotations. Surprisingly, the two totally different methods applied on two completely different objects lead to the same sequence of eventually periodic 2-dimensional substitutions. Thus, every Jeandel-Rao tiling that can be desubstituted indefinitely can be constructed from the coding of some starting point in the polygonal partition.

Unfortunately, not all Jeandel-Rao tilings can be desubstituted indefinitely because of the existence of a horizontal fault line breaking the substitutive structure. Some configuration have a biinfinite horizontal row of the same tile labeled 0 in them. This allows to slide the lower half of configuration along the fault line and the configuration remains valid. A conjecture is that the remaining configurations are rare (of probability zero according to any shift-invariant probability measure). More precisely, I believe that all of the problematic ones can be described by a pair of starting points on the bottom segment of the polygonal partition. During the sabbatical year of Casey Mann and Jennifer Mcloud-Mann in Bordeaux in 2019-2020, we tried hard to prove that conjecture without success. It seems to be a difficult problem. Instead we described the nonexpansive directions in Jeandel-Rao tilings which reminds of the behavior of Penrose tilings with respect to Conway worms, their resolutions and essential holes (annulus of tiles which can be completed uniquely outside of the annulus, but not inside).

Texte mis à jour le 27 février 2024

Dans ce texte, nous allons discuter des différentes manières de faire (et de ne pas faire) l'horaire d'un pool de 4 équipes dans un tournoi d'ultimate. Pour simplifier les choses, nous allons supposer que deux terrains sont disponibles pour faire jouer les 4 équipes en même temps et que tous les matchs du pool seront jouées sur une même journée. On suppose aussi qu'il existe un préclassement des équipes de 1 à 4 (1 étant la meilleure équipe, et 4 étant l'équipe présumée la plus faible).

Un peu de théorie

Tout d'abord, faisons un peu de théorie. Nous désirons respecter les trois Principes de base suivants:

• Principe no 1: Terminer avec les matchs les plus importants
• Principe no 2: Commencer avec les matchs les moins importants
• Principe no 3: Terminer avec le match le plus important

Pourquoi veut-on ces principes? Simplement parce que les équipes ne sont pas à leur meilleur potentiel en début de journée. Il est préférable de mesurer les équipes impliquées dans un match important le plus possible en fin de journée ou fin de pool.

Les matchs les plus importants sont les matchs entre des équipes préclassées proches une de l'autre (1 v 2, 2 v 3, 3 v 4). Les matchs les moins importants sont les matchs entre équipes préclassées loin une de l'autre (1 v 3, 2 v 4, 1 v 4).

Aussi, on dira que le match le plus important du pool sera celui qui fait intervenir la dernière équipe à être sélectionnée pour l'étape suivante et la meilleure équipe qui se fait éliminer du championnat. Par exemple, si seules les deux meilleures équipes passent en quart-de-finale (comme en Coupe du monde de football), alors le match le plus important du pool est le match 2 v 3. Si seule la meilleure équipe du pool est sélectionnée pour l'étape suivante, alors le match le plus important est le match 1 v 2. Si seule la dernière équipe est éliminée du championnat après le pool (comme pendant les Championnats canadiens d'ulimate), alors le match 3 v 4 est le match le plus important du pool.

Attention avant de vouloir adapter les principes discuté ici pour des pools plus grands impliquant 6 équipes et plus où les matchs seront répartis sur plus d'une journée. La question se pose alors de savoir si la priorité est de faire jouer les matchs les plus importants à la fin du pool ou à la fin de la première journée. Cela est un autre sujet: continuons plutôt de considérer le cas d'un pool de 4 équipes.

Option 1

La première option à laquelle on peut penser est de faire jouer les équipes dans l'ordre suivant. On se met dans la peau de la meilleure équipe, et on veut la faire jouer contre des équipes de plus en plus forte au fur et à mesure que la journée avance:

Sans savoir quel est le match le plus important, on peut déjà dire que c'est déjà un très mauvais choix de format pour deux raisons:

• (Principe no 1 non respecté) Le match 2 v 3 est un match important et ne devrait pas être joué pour commencer le pool.
• (Principe no 2 non respecté) Les matchs 1 v 3 et 2 v 4 sont moins importants et devraient être joués en début de pool.

C'est ce format que la FFFD a choisi comme format de tournoi pour les pools de 4 équipes pour les Championnat de France Beach Mixte N1 N2 et N3 du 23-24 septembre 2023. Le format de la FFFD est fait de 4 pools de 4 équipes et seuls les top 2 de chaque pool sont qualifiées pour l'étape suivante (quart-de-finales). Cela signifie que le match le plus important est le match 2 v 3, qui devrait donc être joué à la fin du pool (Principe no 3 non respecté). Or, c'est le match qui est joué en premier le samedi matin. Bref, ce n'est pas idéal, car le format décide avec haute probabilité qui va jouer dans le top 8 au tout premier match du samedi matin alors que les équipes ne sont pas à leur plein potentiel.

Option 2

L'option classique d'un pool de 4 équipes est le format suivant:

On a que

• Le Principe 2 est respecté, car on commence avec les matchs les moins importants.
• Le Principe 1 est respecté, car on termine avec les matchs les plus importants (2 v 3, puis 1 v 2 et 3 v 4).
• Le Principe 3 est respecté si le match le plus important est le match 1 v 2 ou 3 v 4.

C'est le format de base recommandé par USA Ultimate pour 4 équipes dans le manuel des formats de tournois d'ultimate qui existe depuis 1993.

Observons que l'option 2 est compatible avec l'existence d'une 4e ronde de matchs de croisement après la phase de pools et avant la phase à élimination directe. Il s'agit de croiser les équipes terminant en 2e et 3e position dans les pools distincts. Par exemple, avec quatre pools A-B-C-D, les matchs de croisement (aussi appelés pré-quarts dans ce cas-ci) sont A2 v D3, A3 v D2, B2 v C3, B3 v C2 dont les gagnants se retrouvent en quart-de-finales contre les gagnants des pools.

Les matchs de croisement permettent de gérer la situation où on a trois équipes fortes qui se retrouvent dans le même pool. Le match de croisement permet à une équipe qui termine 3e d'un pool de tenter de gagner contre une équipe qui a terminé 2e dans un autre pool pour se qualifier pour l'étape suivante.

Avec des matchs de croisement 2e v 3e, seule la 4e équipe est éliminée à la fin des matchs de pool. Le match 3 v 4 du pool est donc le match le plus important. Cette situation est donc compatible avec l'option 2 (Principe no 3 respecté).

Option 3

Lorsque seules 2 équipes sur 4 sont qualifiées pour l'étape suivante, alors le match 2 v 3 devient le match le plus important du pool. En ce sens, l'option 2 ci-haut ne respecte pas le Principe no 3, car le match 2 v 3 est joué en deuxième ronde.

Dans ce cas, il est préférable de procéder ainsi:

On a que:

• Le Principe 2 est respecté, car on commence avec les matchs les moins importants.
• Le Principe 1 est quasiment respecté, car on termine avec les matchs les plus importants (1 v 2 et 3 v 4 puis 2 v 3).
• Le Principe 3 est respecté, car on termine avec le match le plus important (2 v 3).

C'est ce format que la FIFA choisit lors de la Coupe du monde pour les pools de 4 équipes où le match 2 v 3 est le match le plus important du pool. Voici une copie écran de la page Wikipédia sur la Coupe du monde de football 2026:

Option 4

Il existe une 4e option proposée dans le manuel de USA Ultimate qui mérite d'être mentionnée:

Lorsque le préclassement est incertain, ce format augmente les chances que les équipes invaincues se rencontrent en troisième ronde. Si le préclassement est respecté dans les matchs, alors l'option 4 est équivalente à l'option 2.

Conclusion

Si vous organisez un tournoi, merci de ne pas réinventer la roue. Les formats de tournois ont été beaucoup étudiés dans le passé (USA Ultimate, FIFA, etc.). Merci de consulter par exemple le manuel des formats des tournois de USA Ultimate ou ce qui se passe dans les autres fédérations et à l'international.

Pour ce qui est de l'horaire des pools de 4 équipes, voici mes recommandations

• si une ou trois équipes du pool sont qualifiées pour l'étape suivante, alors je recommande d'utiliser l'option 2: le format classique recommandé dans le manuel des formats de tournoi de USA Ultimate.
• si deux équipes du pool sont qualifiées pour l'étape suivante, alors je recommande d'utiliser l'option 3: le format des pools de la Coupe du monde de football de la FIFA.
• dans tous les cas, je recommande de proscrire l'option 1.

On Wednesday June 28th, 2023, I give short a Introduction to Python/SageMath as an online course organized by Pierre-Guy Plamondon in Mathematical Summer in Paris (MSP23) on WorkAdventure. Below is the material that will be presented or suggested.

Exercises:

1. Install and open a Jupyter notebook and do the User Interface Tour in the help menu.
2. Programming with Python. Here is a list of Jupyter notebooks to learn programming in Python: ProgrammingExercises.zip or ProgrammingExercises.tar.xz
3. Reproduce the computations made by BuzzFeedNews in a github repository of your choice, for instance about the fentanyl and cocaine overdose deaths (2018) or about The Tennis Racket (2016).
4. Solve some problems from the Project Euler. Project Euler contains more than 500 exercises that have to be solved with a computer
5. Reproduce one or more images from the matplotlib library.
6. Download the book Mathematical Computation with Sage by Paul Zimmermann et al. about the SageMath open source software. Reproduce the computations made in a section of your choice in the book.
7. Visit https://ask.sagemath.org/questions/ and try to reproduce some of the best answers to questions of interest for you.
8. Choose a section of your choice in the SageMath very large Reference Manual and reproduce the computations made in it.

When working on the above, two principles applies:

• Once you finished solving a notebook or a problem on Project Euler on your own you need to explain your solution to at least one other person (who has already solved the same notebook or problem).
• Once you reproduced the computation made by BuzzFeedNews, matplotlib image or some computation, you need to present and explain it to at least one other person.

Supplementary material:

9. Experimenting with Dynamical systems in SageMath: DynamicalSystemExercices.zip
10. Some more notebooks and exercices from this course given by Vincent Delecroix at AIMS in Rwanda (2016).

Le chapeau est une tuile apériodique découverte par David Smith, Joseph Samuel Myers, Craig S. Kaplan, et Chaim Goodman-Strauss le 20 mars 2023. Suite à un exposé donné le 26 mars au National Museum of Mathematics, la nouvelle s'est vite répandue. En effet, cette découverte a été mentionnée les jours suivants dans des blogues puis dans Le New York Times le 28 mars, Le Monde le 29 mars, puis The Guardian et QuantaMagazine le 4 avril. Un vidéo de 20 minutes, réalisé par Passe-Science et publié début le 3 mai, explique le résultat et son contexte.

Déjà des articles proposant des résultats plus approfondis sur la tuile par des experts du domaine sont parus sur arXiv en mai 2023. Ils interprêtent les pavages comme des coupes et projection de réseaux de dimension supérieure. Le deuxième propose même une partition de la fenêtre de l'espace interne, un peu comme pour les pavages de Jeandel-Rao, à la différence qu'ici la partition a des bords fractales ce qui est pour moi une grande surprise.

Comme je faisais une intervention dans l'école de mon garçon à Bègles le 3 mai et au Lycée Kastler de Talence le 4 mai, j'ai réalisé un projet de découpe laser sur la tuile apériodique afin de partager cette récente découverte.

La première question était de construire un pavage d'un rectangle assez grand avec la pièce apériodique. Pour ce faire, j'ai ajouté un nouveau module dans mon package optionel au logiciel SageMath.

Le module réalise une réduction à une instance du problème de la couverture universelle, qui peut être résolu dans SageMath en utilisant l'algorithme des liens dansants de Donald Knuth, les solveurs SAT ou les programmes d'optimisation linéaire (solveur MILP). Le code utilise le système de coordonnées défini dans le fichier validate/kitegrid.pdf qui se trouve dans le code source associé à l'article.

Voici un exemple de construction d'un pavage avec la tuile apériodique. Le calcul est fait dans le logiciel SageMath muni de la version de développement de mon package optionnel slabbe qui peut être installé avec la commande sage -pip install slabbe. Ici, j'utilise le solveur SAT Glucose, développé au LaBRI. On peut installer glucose dans SageMath avec la commande sage -i glucose.

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(16, 17)
sage: G = s.draw_one_solution(solver='glucose')
sage: G.save('solution_16x17.png')
sage: G

Dans la manière de résoudre la question ci-haut, le problème est représenté par un problème de couverture exacte qui consiste à recouvrir exactement les entiers de 1 à n avec des sous-ensembles choisis dans une liste de sous-ensembles déterminés. Ici, on représente l'espace à recouvrir de manière discrète en comptant 6 points du plan par hexagone (un point pour chaque kite contenu dans un hexagone). Rappelons que la pièce Chapeau qui nous intéresse est formée d'une union d'exactement 8 de ces kites.

sage: s.plot_domain()

Ensuite, on construit une matrice de 0 et de 1 avec autant de colonnes que de points ci-haut (16 * 17 * 2 * 6 = 3264) et autant de lignes qu'il y a de copies isométriques de la pièce intersectant le domaine. Pour chaque copie de la pièce, une ligne dans la matrice contient des 1 exactement dans les colonnes associées aux kites occupés par la pièce.

sage: s.the_dlx_solver()
Dancing links solver for 3264 columns and 7116 rows

Le calcul ci-haut qui a construit la matrice (sparse) indique qu'il y a 7116 copies isométriques de la pièce qui intersectent (complètement ou partiellement) le domaine. Quand on voudra dessiner une solution, on ignorera les pièces incomplètes.

On peut maintenant résoudre le problème.

sage: s = MonotileSolver(8,8)
sage: %time L = s.one_solution()   # l'algo des liens dansants de Knuth est utilisé par défaut
CPU times: user 798 ms, sys: 32.2 ms, total: 830 ms
Wall time: 1min 20s

Le contenu d'une solution est une liste de nombres indiquant les lignes de la matrice de 0/1 à considérer pour former une solution. C'est-à-dire que la sous-matrice restreinte aux lignes données comporte exactement un 1 dans chaque colonne:

sage: L
[81,
 85,
 125,
 128,
 ...
 1772,
 1783,
 1794,
 1815]

Ici, il se trouve que les solveurs SAT sont plus efficaces que l'algo des liens dansants pour trouver une solution:

sage: %time L = s.one_solution(solver='glucose')
CPU times: user 326 ms, sys: 16.1 ms, total: 342 ms
Wall time: 526 ms
sage: %time L = s.one_solution(solver='kissat')
CPU times: user 335 ms, sys: 3.64 ms, total: 339 ms
Wall time: 461 ms

En effet, Glucose se comporte plutôt bien pour résoudre des problèmes de pavages du plan lorsqu'il existe une solution. Mais lorsqu'il n'y a pas de solution, l'algo des liens dansants de Knuth est parfois mieux. Aussi, l'algo des liens dansants de Knuth est très efficace pour énumérer toutes les solutions.

Le solveur Kissat a été ajouté dans SageMath par moi-même comme package optionnel cette année suite à une discussion avec Laurent Simon au café du LaBRI. On peut installer le solveur kissat dans SageMath avec la commande sage -i kissat.

Ici on extrait le contour des pièces d'une solution (tel que chaque arête est dessinée une seule fois afin d'éviter que la découpeuse laser passe deux fois par chaque arête ce qui peut endommager ou brûler le bord des pièces en bois) et on crée un fichier pdf ou svg. Je choisis une taille de 16 double-hexagones horizontalement et 17 verticalement, car cela crée un fichier qui correspond à une taille de 1m x 60cm. C'est la taille de la découpeuse laser à notre disposition:

sage: s = MonotileSolver(16, 17)
sage: tikz = s.one_solution_tikz(solver='glucose')
sage: tikz.pdf('solution_16x17.pdf')
sage: tikz.svg('solution_16x17.svg')     # or

Avec l'aide de David Renault, mon collègue du LaBRI qui enseigne à l'ENSEIRB et qui m'a déjà accompagné dans la réalisation de projets de découpe laser, nous avons découpé le fichier ci-haut le jeudi 27 avril au EirLab, l'atelier de fabrication numérique (FabLab) de l'ENSEIRB-MATMECA:

Comme toujours, il faut quelque peu modifier le fichier svg dans Inkscape avant de lancer la découpe laser. Voici le fichier modifié juste avant la découpe.

Maintenant, on peut s'amuser avec les pièces:

Avec mes garçons, nous avons trouvé une forme intéressante qui recouvre le plan périodiquement à l'exception d'un trou hexagonal. Il se trouve que la même forme peut-être créée de deux façons différentes: sur l'image ci-bas la forme à droite est la globalement la même, mais elle n'est pas obtenue de la même façon que celle en haut à gauche. Pourtant, toutes deux ont le même contour extérieur et le même trou hexagonal.

Cette observation, déjà faite par d'autres, a mené au recouvrement d'une sphère avec la pièce et un trou pentagonal:

Dans ce message, je suggère un format de tournoi pour 7 équipes permettant de qualifier une équipe pour l'étape suivante (compétitions nationales par exemple). En bref, la solution suggérée est:

• Faire tournoi à la ronde sur trois jours (2 matchs par jour par équipe)
• Le quatrième jour, les équipes classées #5, #6 et #7 sont éliminées et font un tournoi à la ronde entre elles (donc deux matchs chacune).
• Le quatrième jour, on a les demie-finales #1 vs #4 et #2 vs #3 ainsi que les finales et petite finale.

Plus précisément, voici les détails jour par jour.

Jour 1

Le jour 1, il y a surtout des matchs le top 4 entre eux, et le 5-6-7 entre eux:

Note: le match 1v2 peut être devancé de 30 minutes pour laisser plus de temps entre les deux matchs de l'équipe 1.

Jour 2

Le jour 2, il y a des matchs importants pour séparer le top 4 du 5-6-7:

Note: le match 4 v 6 peut être devancé de 30 minutes pour laisser plus de temps entre les deux matchs de l'équipe 4.

Jour 3

Le jour 3, il y a surtout des matchs moins importants entre équipes éloignées dans le préclassement:

Note: le match 4 v 7 peut être devancé de 30 minutes pour laisser plus de temps entre les deux matchs de l'équipe 4.

Jour 4

Le jour 4, on fait:

• Tournoi à la ronde entre les équipes #5, #6, #7
• Demi finales: #1 vs #4 et #2 vs #3
• Petite finale
• Finale

Je me suis demandé si à la fin du troisième jour, on fait jouer des pré-demis: #6 vs #3 et #5 vs #4, mais ce n'est pas ce qui est recommandé dans le manuel de USAU Ultimate pour un format à 7 équipes dont une seule est qualifiée pour la montée. En effet, cela donne moins d'importance à bien jouer dans le tournoi à la ronde, et donne moins d'importance aux deux premiers jours. Comme une seule équipe est qualifiée, c'est normal je pense d'en éliminer 3 après le tournoi à la ronde.