Sujet de stage de M2

Titre : Défauts dans les cercles discrets

Encadrants : Thierry Monteil et Gwénaël Richomme

Parcours : CASAR ou Math-Info ou Mathématiques fondamentales

Description :

On peut approcher une courbe dessinée sur un quadrillage par les cases qu'elle rencontre (c'est par exemple le cas lorsqu'on veut tracer une courbe sur un écran d'ordinateur). La précision augmente lorsque le maillage du quadrillage diminue.

On peut coder cette représentation comme suit : lorsque la courbe croise le quadrillage selon une verticale, on écrit un "0", lorsqu'elle le croise selon une horizontale, on écrit un "1" (on néglige les cas ou la courbe rencontre un coin). On obtient ainsi un mot binaire, qui permet de dessiner la trace de la courbe sur le quadrillage de proche en proche.

Le cas des segments est particulièrement bien connu et on sait caractériser combinatoirement les mots binaires obtenus : ce sont exactement les mots dits 1-équilibrés, c'est-à-dire les mots w tels que si u et v sont deux sous-mots de w de même longueur, alors le nombre de "0" apparaissant dans u et le nombre de "0" apparaissant dans v diffèrent d'au plus 1. On peut comprendre la notion d'équilibre comme la constance de la pente de la courbe (la pente correspond au rapport entre le nombre de "1" et le nombre de "0" apparaissant dans le mot considéré).

Par exemple le segment SegmentGrille.png est codé par le mot "001000100100", et sa pente vaut à peu près 1/3.

Imaginons maintenant que nous souhaitons coder une courbe circulaire. On pourrait se dire que, comme cette courbe est très régulière (infiniment dérivable), elle admet des tangentes en tous points, de sorte que lorsque la maille du quadrillage tend vers 0, les mots produits ressembleront localement à des mots 1-équilibrés.

Dans l'article On the properties of discrete circles, rings, and disks, Zenon Kulpa a déterminé la suite des rayons des cercles présentant un coin anguleux, il s'agit des entiers r qui satisfont l'équation diophantienne r^2 = 2i^2 - i + 1. Dans notre vocabulaire, il s'agit des cercles dont le codage contient le mot "0011", qui n'est pas 1-équilibré.

En fait, ce mot peut être interprété comme une erreur sur le mot "0101" qui est 1-équilibré. De tels mots sont appellés mots tangents en ce qu'ils modélisent les tangentes des courbes régulières. Il existe de nombreux mots qui apparaissent dans le codage des cercles à des échelles arbitrairement fines sans pour autant être 1-équilibrés.

Le but de ce stage est de comprendre la répartition de ces mots dans les codages des cercles.

Bibliographie :

Remarques :

Ce sujet est complémentaire d'un sujet sur les mots 2-équilibrés, mais nous ne pourrons encadrer qu'un-e étudiant-e au total.