Utilisateur:ManiacParisien/Brouillons/Math-1
Extensions[modifier | modifier le code]
Des extensions de la notion de suite automatiques à d'autres systèmes de numération ont été étudiées[1]. Les auteurs présentent le classement, par généralisation successive [1] :
- Base entière Base Pisot Base Parry Base Bertrand Système abstrait.
La base de numération, un entier , est successivement remplacé par un nombre de Pisot, un nombre de Parry ou un nombre de Bertrand.
Système de numération[modifier | modifier le code]
Plus généralement, un système de numération (positionnel) est ici une suite croissante d'entiers positifs, avec et tel que . On associe à l'alphabet . La représentation gloutonne d'un entier positif n est le mot
sur vérifiant
avec les condition :
- et pour .
C'est bien entendu la dernière des conditions que détermine le caractère glouton de la représentation. On note
l'ensemble des mots représentant les entiers naturels.
Beta-développement[modifier | modifier le code]
Soit β > 1 un nombre réel ; la valeur de
le nombre
la suite
est le développement en base de pourvu que les sont des entiers naturels inférieurs à β. Le concept de développement en base β ou β-développement, a été introduit par (Rényi 1957) et a été étudié en détail par W. Parry[2] . Tout nombre réel possède un développement en base β, éventuellement infini.
Selon que β est un nombre de Pisot, un nombre de Parry ou un nombre de Bertrand, les propriétés des développements varient.
Système de Pisot[modifier | modifier le code]
Les suites Pisot-automatiques se comportent dans beaucoup de leurs propriétés comme les suites k-automatiques. Leur propriété la plus importante est que les deux suites admettent des caractérisations en terme de logique du premier ordre. Pour les suite -automatiques, elle est due à Büchi[3] ; pour les suite de Pisot elle a été prouvée par Véronique Bruyère et Georges Hansel[4]. Une présentation est donnée dans le livre de Miche Rigo[5]
Système de Parry[modifier | modifier le code]
Pour un nombre réel \beta>1, Soit un nombre de Parry, Un système de numération U est un système de Parry s'il existe un nombre de Parry β tel que .
Système de Bertrand[modifier | modifier le code]
Les systèmes de Bertrand ont été introduits et étudiés par Anne Bertrand-Mathys[6].
Un système de numération est un système de Bertrand si, pour tout mot non vide sur , on a
- si et seulement si .
Le système de numération usuel en base est un système de Bertrand. De même, le système de numération de Fibonacci usuel ; en revanche, si on considère la suite définie par elle n'est plus de Bertrand parce que le nombre 2 est la représentation gloutonne de l'entier 2, et la représentation 20(=2\cdot 3+0) du nombre 6 n'est pas une représentation gloutonne puisque .
La caractérisation suivante est due à Anne Bertrand :
Soit un système de numération, et soit l'ensemble des facteurs apparaissant dans les β-développements des nomres réels de l'intervalle semi-ouvert [0,1[. U est un système de Bertrand si et seulement s'il existe un nomre réel β>1 tel que . Dans ce cas, pour , le système de numération vérifie la relation de récurrence
Notes et références[modifier | modifier le code]
- Adeline Massuir, Jarkko Peltomäki et Michel Rigo, « Automatic sequences based on Parry or Bertrand numeration systems », Advances in Applied Mathematics, vol. 108, , p. 11–30 (ISSN 0196-8858, DOI 10.1016/j.aam.2019.03.003).
- W. Parry, « On theβ-expansions of real numbers », Acta Mathematica Academiae Scientiarum Hungaricae, vol. 11, nos 3-4, , p. 401–416 (ISSN 0001-5954, DOI 10.1007/BF02020954)
- Julius R. Büchi, « Weak second-order arithmetic and finite automata », Z. Math. Log. Grundl. Math., vol. 6, , p. 66-92.
- Véronique Bruyère et Georges Hansel, « Bertrand numeration systems and recognizability », Theoretical Computer Science, vol. 181, no 1, , p. 17–43 (DOI 10.1016/S0304-3975(96)00260-5).
- Michel Rigo, Formal Languages, Automata and Numeration Systems, vol. 2 : Applications to Recognizability and Decidability, London/Hoboken, NJ, ISTE/John Wiley & Sons, Inc.,
- Anne Bertrand-Mathis, « Comment écrire les nombres entiers dans une base qui n'est pas entière », Acta Mathematica Hungarica, vol. 54, nos 3-4, , p. 237–241 (ISSN 0236-5294, DOI 10.1007/BF01952053).