Suite de Baum-Sweet

En mathématiques, et en combinatoire des mots, la suite de Baum-Sweet ou suite de Baum et Sweet est une suite automatique $(b_n{)}_{n\ge 0}$ composée de $0$ et de $1$ définie par :

$b_n=1$ si la représentation binaire de $n$ ne contient pas de bloc composé d'un nombre impair de $0$;

$b_n=0$ sinon.

Par exemple, $b_4=1$ parce que la représentation binaire de 4 est 100 et ne contient qu'un bloc de deux 0; en revanche, $b_5=0$ parce que la représentation binaire de 5 est 101 et contient un bloc formé d'un seul 0. De même, $b_{76}=1$, parce que la représentation binaire de 76 est 1001100.

La suite commence en $n=0$; ses premiers termes sont :

1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1 ... (c'est la Modèle:OEIS)

La suite est nommée d'après Leonard E. Baum et Melvin M. Sweet qui ont été les premiers à l'étudier en 1976.

Propriétés

Automate pour la suite de Baum et Sweet.

La suite de Baum et Sweet est 2-automatique. Elle peut donc être engendrée par un automate fini. Dans l'automate ci-contre, un mot commençant par $1$ arrive en l'état $a$ si et seulement c'est le développement binaire d'un entier $n$ tel que $b_n=1$. Le langage reconnu par l'automate a pour expression rationnelle l'expression $(00+1{)}^{*}$.

Les termes $b_n$ s'évaluent aussi par récurrence. Posons $n{=}^{j}m$, où $m$ n'est pas divisible par $4$. Alors on a :

$b_n=\{\begin{array}{cc}0& \text{si }m\text{ est pair}\\ b_{(m-1)/2}& \text{si }m\text{ est impair}.\end{array}$

Cette relation équivaut au calcul du 2-noyau. On a en effet :

$b_{2n+1}=b_n$

$b_{4n}=b_n$

$b_{4n+2}=0$

Le 2-noyau est donc composé de 3 suites.

Le mot infini de Baum et Sweet

$1101|1001|0100|1001|1001|0000|0100|1001\cdots$

est morphique. On itère d'abord le morphisme 2-uniforme :

$\begin{array}{ccc}a& \mapsto & ab\\ b& \mapsto & bc\\ c& \mapsto & bd\\ d& \mapsto & dd\end{array}$

à partir de a. Ceci donne $a,ab,abcb,abcbbdcb,\dots$ et enfin :

$abcb|bdcb|cbdd|bdcb|bccb|dddd|\cdots$

On applique enfin le morphisme lettre-à-lettre qui envoie $a$ et $b$ sur $1$, et $c$ et $d$ sur $0$.

Le mot de Baum et Sweet contient des plages arbitrairement longues de $0$ : ce mot n'est donc pas uniformément récurrent. En revanche, le mot ne contient pas de facteur composé de trois $1$ consécutifs.

La série

$b(X)=\sum _{n=0}^{\mathrm{\infty }}{b}_n{X}^n$

s'écrit, avec les relations de récurrence, sous la forme :

$b(X)=\sum _{n=0}^{\mathrm{\infty }}{b}_n{X}^{2n+1}+\sum _{n=0}^{\mathrm{\infty }}{b}_n{X}^{4n}=Xb(X^2)+b(X^4)$

donc $Y=b(X)$ est solution de l'équation sur $F_2$

$Y^3+XY+1=0$.

Références

• Modèle:Article
• Modèle:Ouvrage
• Modèle:Article.