Suites de Beatty

Une suite de Beatty est associée à un nombre r irrationnel. Le terme d'indice 0 est supposé non défini, et le terme d'indice n s'obtient en

Alors la suite de Beatty associée à r est une suite d'entiers. L'idée dans ce qui va suivre est de représenter r par une suite d'entiers, comme c'est déjà le cas avec la suite des chiffres de son développement décimal. Mais la suite de Beatty a des propriétés particulières, qui seront utilisées pour engendrer les pavages de Wang apériodiques.

Pour construire un nombre irrationnel, on doit utiliser la syntaxe de JavaScript, par exemple Math.sin 1 pour le sinus d'un radian, ou Math.cos 1 pour son cosinus, ou Math.exp -1 pour e-1, Math.log 10 pour ln(10), ou encore Math.sqrt 5 pour √(5); mais il y a aussi des constantes prédéfinies:

Pour afficher le début de la suite de Beatty de √(2), il suffit de lancer le script suivant, et pour la suite de Beatty d'un autre irrationnel, il suffit de modifier la première ligne, définissant r:

Suites de Beatty d'irrationnels supérieurs à 1

En explorant la situation avec l'outil ci-dessus, on constate que, si r est supérieur à 1, la suite de Beatty est strictement croissante. Cela permet de la considérer comme une partie de N. Le fait qu'il soit possible de savoir par un algorithme si un entier n est membre de la suite de Beatty de r, s'exprime en disant que la suite de Beatty de r est récursivement énumérable (notion dûe à Kurl Gödel dans les années 1940). On peut représenter la partie récursivement énumérable de N comme une suite de 0 (si n'est pas membre de la suite) et de 1 (si n est dans la suite). Pour améliorer l'affichage, on joint les termes de cette suite de 0 et de 1 en une chaîne de caractères :

La suite de 0 et de 1 s'appelle fc parce que c'est la fonction caractéristique de la suite. On a donc une nouvelle manière de représenter un irrationnel en binaire, différente de la numération binaire :

Théorème de Rayleigh

Le fait que la suite de Beatty de r est récursivement énumérable peut se traduire dans le contexte actuel par la phrase suivante: Emilio peut être programmé pour cocher les cases affichées ci-dessus. Maintenant, que se passe-t-il si on inverse les "0" et les "1"?

Les suites de Beatty sont connues depuis ce résultat de Lord Rayleigh: En inversant les 0 et les 1 de la suite de Beatty de r, le résultat obtenu est à nouveau une suite de Beatty (d'un irrationnel s). Par exemple, la suite de Beatty affichée ci-dessus est celle de 2+√(2).

Contrairement à ce qu'on aurait pu croire, le fait qu'un ensemble d'entiers est récursivement énumérable, n'implique pas nécessairement que son complémentaire le soit aussi (si Emilio est capable de cocher des cases selon un motif précis, il n'est pas forcément capable de faire l'inverse: Cocher les cases qui n'étaient pas cochées dans la version initiale. C'est essentiellement la conséquence du fait qu'Emilio est chargé de cocher une infinité de cases). Si c'est le cas, on dit que l'ensemble est récursif. Le théorème de Rayleigh permet donc d'affirmer que la fonction caractéristique de la suite de Beatty d'un irrationnel supérieur à 1 est récursif.

Différence des termes consécutifs

Autre chose qu'on a pu constater avec la suite de Beatty d'un irrationnel r supérieur à 1: Les sauts ne sont que de deux sortes :

Pour √(2), il n'y a que des sauts de 1 ou de 2 (c'est lié à l'algorithme de Bresenham appliqué à la représentation pixellisée de la droite d'équation y=√(2)×x, l'escalier passant au plus près de la droite, la hauteur des marches ne peut prendre que deux valeurs possibles). Alors, en soustrayant 1 à chaque terme de la différence, on n'a à nouveau que des "0" et des "1", soit une nouvelle représentation binaire de √(2) !!!. L'une des idées maîtresses de Kari et Culik est que, si on étend la suite de Beatty à des entiers négatifs, la suite infinie dans les deux sens ainsi obtenue détermine entièrement r (à partir des "1" et des "2" de la suite ci-dessus, on peut retrouver que la suite vient de √(2), du moment qu'on dispose de tous ses termes, soit une infinité). Une autre idée et qu'il est possible de calculer la suite par une sorte de récurrence: Une machine de Mealy (ayant un nombre fini d'états, l'état actuel étant entièrement déterminé par l'ancien état et le chiffre lu par l'automate).

Mots de Fibonacci

Mais d'abord, voici pour rappel le calcul de la suite de Fibonacci en CoffeeScript:

suite = []
[a,b] = [1,0]
for n in [1..20]
    [a,b] = [b,a+b]
    suite.push b
alert suite

(script à copier-coller vers une des fenêtres de script de cet article)

On essaye une petite variante, consistant à mettre les termes 1 et 0 entre guillemets :

Le mot "010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010" obtenu, prolongé à l'infini, s'appelle mot de Fibonacci. C'est un cas particulier de mot sturmien. Et les mots sturmiens sont associés aux suites de Beatty. Ainsi le mot de Fibonacci, suite infinie de 0 et de 1, peut-il être l'ensemble des valeur d'une suite de Beatty d'un irrationnel r supérieur à 1 ? Si oui, lequel ? Indice: Essayez avec son complémentaire (en échangeant les "1" et les "0")...

Machines à multiplier

Le point de départ de la construction de Kari et Culik est d'examiner ce que devient une suite (des différences) de Beatty sous l'effet d'un produit : Comment la suite de Beatty de r et-elle modifiée lorsqu'on divise r par 2 ?

Pas facile de voir le procédé, surtout en remplaçant le facteur 1/2 par un facteur plus compliqué ! Mais pour peu qu'on remplace la valeur de r par une fraction, on constate que la suite (des différences) de Beatty est périodique (et même, pour les statisticiens, la moyenne des chiffres de ces suites périodiques est asymptotiquement r), et qu'Emilio devient capable de transformer la première suite en la seconde (du moment qu'on lui laisse un temps infini, puisque les suites, si elles sont périodiques, sont aussi infinies). Kari et Culik n'ayant pas la chance de connaître Emilio, lui ont préféré une machine de Mealy, ayant un nombre fini d'états, et changeant d'état à chaque top d'une horloge, le nouvel état dépendant à la fois de l'état précédent et de la lettre que la machine de Mealy est en train de lire.

Machines de Mealy

Pour tout r de l'intervalle [1,2] (donc avec une suite de Beatty différenciée ne comportant que des 1 et des 2), r/2 se trouve dans l'intervalle [1/2,1] et sa suite de Beatty différenciée ne comporte que des 0 et des 1. La machine de Mealy associée à la division par 2 est donc une machine à transformer des 1 et des 2 en des 0 et des 1 :