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 ${\displaystyle (b_{n})_{n\geq 0}}$ composée de ${\displaystyle 0}$ et de ${\displaystyle 1}$ définie par :

${\displaystyle b_{n}=1}$ si la représentation binaire de ${\displaystyle n}$ ne contient pas de bloc composé d'un nombre impair de ${\displaystyle 0}$;

${\displaystyle b_{n}=0}$ sinon.

Par exemple, ${\displaystyle b_{4}=1}$ parce que la représentation binaire de 4 est 100 et ne contient qu'un bloc de deux 0; en revanche, ${\displaystyle 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, ${\displaystyle b_{76}=1}$, parce que la représentation binaire de 76 est 1001100.

La suite commence en ${\displaystyle 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 suite A086747 de l'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 ${\displaystyle 1}$ arrive en l'état ${\displaystyle a}$ si et seulement c'est le développement binaire d'un entier ${\displaystyle n}$ tel que ${\displaystyle b_{n}=1}$. Le langage reconnu par l'automate a pour expression rationnelle l'expression ${\displaystyle (00+1)^{*}}$.

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

${\displaystyle b_{n}={\begin{cases}0&{\text{si }}m{\text{ est pair}}\\b_{(m-1)/2}&{\text{si }}m{\text{ est impair}}.\end{cases}}}$

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

${\displaystyle b_{2n+1}=b_{n}}$

${\displaystyle b_{4n}=b_{n}}$

${\displaystyle b_{4n+2}=0}$

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

Le mot infini de Baum et Sweet

${\displaystyle 1101|1001|0100|1001|1001|0000|0100|1001\cdots }$

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

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

à partir de a. Ceci donne ${\displaystyle a,ab,abcb,abcbbdcb,\ldots }$ et enfin :

${\displaystyle abcb|bdcb|cbdd|bdcb|bccb|dddd|\cdots }$

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

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

La série

${\displaystyle b(X)=\sum _{n=0}^{\infty }b_{n}X^{n}}$

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

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

donc ${\displaystyle Y=b(X)}$ est solution de l'équation sur ${\displaystyle F_{2}}$

${\displaystyle Y^{3}+XY+1=0}$.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Baum–Sweet sequence » (voir la liste des auteurs).
• Leonard E. Baum et Melvin M. Sweet, « Continued fractions of algebraic power series in characteristic ${\displaystyle 2}$ », Ann. of Math. (2), vol. 103, n^o 3,‎ 1976, p. 593-610
• Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : Theory, Applications, Generalizations, Cambridge University Press, 2003, 571 p. (ISBN 978-0-521-82332-6, zbMATH 1086.11015, lire en ligne)
• Łukasz Merta, « Composition inverses of the variations of the Baum–Sweet sequence », Theoretical Computer Science, vol. 784,‎ 2019, p. 81–98 (DOI 10.1016/j.tcs.2019.03.041).

Lien externe

(en) Eric W. Weisstein, « Baum–Sweet Sequence », sur MathWorld