Numération en base non entière

Une numération en base non entière ou représentation non entière d'un nombre utilise, comme base de la notation positionnelle, un nombre qui n'est pas un entier. Si la base est notée , l'écriture

dénote, comme dans les autres notations positionnelles, le nombre

.

Les nombres sont des entiers positifs ou nuls plus petits que . L'expression est aussi connue sous le terme β-développement (en anglais β-expansion). Tout nombre réel possède au moins un, et éventuellement une infinité de β-développements. La notion a été introduite par le mathématicien hongrois Alfréd Rényi en 1957[1] et étudiée en détail ensuite par William Parry en 1960[2]. Depuis, de nombreux développements ultérieurs ont été apportés, dans le cadre de la théorie des nombres et de l’informatique théorique. Il y a des applications en théorie des codes[3] et dans la modélisation de quasi-cristaux[4],[5].

Construction

Les β-développements généralisent le développement décimal. Les développements décimaux sont uniques quand ils sont finis, les développements infinis ne le sont pas puisque par exemple le développement décimal de l'unité est . Les β-développements, même finis, ne sont pas nécessairement uniques. Ainsi, si , est le nombre d'or, on a , donc 100=011. Un choix canonique pour le β-développement d'un nombre réel est d'appliquer l'algorithme glouton suivant, dû pour l'essentiel à Rényi[1], et formulé comme suit par exemple par Christiane Frougny[6] :

Soit un nombre réel positif ou nul. Soit l'entier tel que . On pose[7] :

et ,

et pour  :

et .

En d'autres termes, ce β-développement canonique de est construit en prenant pour le plus grand entier tel que , puis en prenant le plus grand entier tel que et ainsi de suite. La suite des est notée . Ce choix produit la plus grande séquence en ordre lexicographique représentant . On a

et si

.

Dans une base entière, on obtient la représentation usuelle du nombre ; la construction ci-dessus étend l'algorithme à des valeurs non entières de la base β.

Systèmes de numération généraux

Une généralisation de la notion de β-développement est la suivante[8] : un système de numération (positionnel) est donné par une suite croissante d'entiers positifs, avec et tel que . On associe à la suite les chiffres . La représentation gloutonne d'un entier positif est la séquence

composée de chiffres dans vérifiant

avec les conditions :

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.


Exemples

Base

La base est très proche de la base 2 ; pour convertir un nombre écrit en binaire en base est d'insérer un chiffre nul entre deux chiffres binaires ; par exemple

191110 = 111011101112 = 101010001010100010101

et

511810 = 10011111111102 = 1000001010101010101010100.

Ceci implique en particulier que tout entier peut être écrit en base sans point décimal.

Cette base peut être utilisée pour illustrer la relation entre le côté d'un carré et de sa diagonale puisqu'un carré de côté 1 a une diagonale de de longueur 10 et un carré de côté 10 a une diagonale de longueur 100. Une autre utilisation est d'illustrer la proportion d'argent notée , qui vaut (suite A014176 de l'OEIS), puisqu'elle s'écrit simplement en base . Par ailleurs, l'aire d'un octogone régulier de côté 1 est 1100, l'aire d'un octogone régulier de côté 10 est 110000, l'aire d'un octogone régulier de côté 100 est 11000000, etc...

Base φ

Article détaillé : Base d'or.

La base d'or est le système de numération utilisant le nombre d'or, à savoir comme base. Ce système de numération en base non entière est également désigné plus rarement comme « développement phinaire » (car le symbole pour le nombre d'or est la lettre grecque « phi »), mais aussi « système de numération de Bergman »[9]. Tout nombre réel positif possède une représentation standard en base φ où seuls les chiffres 0 et 1 sont utilisés, et où la suite « 11 » est évitée. Une représentation non standard en base φ avec ces deux chiffres (ou avec d'autres chiffres) peut toujours être réécrite en forme standard, en utilisant les propriétés algébriques du nombre φ — c'est-à-dire que φ + 1 = φ2. Par exemple 11φ = 100φ. Malgré l'usage d'une base irrationnelle, tous les entiers naturels possèdent une représentation unique en développement fini dans la base φ. Les réels positifs qui possèdent une représentation finie dans la base φ sont les entiers de ℚ(5) positifs.

Les autres nombres positifs possèdent des représentations standards infinies en base φ, les nombres rationnels positifs ayant des représentations périodiques. Ces représentations sont uniques, excepté celles des nombres qui ont un développement fini ainsi qu'un développement non fini (de la même manière qu'en base dix : 2,2 = 2,199999… ou 1 = 0,999…).

Cette base est présentée, entre autres, par George Bergman [10] en 1957 ; l'étude de la base d'or a produit des fruits en informatique, par exemple pour la conception de convertisseurs analogique-numérique et de processeurs tolérants au bruit[11].

Base e

La base e du logarithme naturel se comporte comme le logarithme décimal, et ln(1e) = 0, ln(10e) = 1, ln(100e) = 2 and ln(1000e) = 3.

La base e est le choix le plus économique comme base [12], quand l’économie d'une base est mesurée comme le produit de la base multiplié par la longueur de la chaîne nécessaire pour représenter un intervalle de valeurs.

Base π

La base π peut être utilisée pour illustrer simplement la relation entre le diamètre d'un cercle et sa circonférence, qui correspond à son périmètre; de la relation circonférence = diamètre × π, il résulte qu'un cercle de diamètre 1π a une circonférence 10π, un cercle de diamètre 10π a une circonférence 100π, etc. Similairement, comme aire = π × rayon2, un cercle de rayon 1π a une aire égale à 10π, un cercle de rayon 10π a une aire égale à 1000π etc[13].

Propriétés

Selon que β est un nombre de Pisot, un nombre de Parry ou un nombre de Bertrand, les propriétés des développements varient. Elles ont aussi fait l'objet d'étude dans le cadre des suites automatiques[8].

Unicité

Dans aucun système de numération positionnel tout nombre admet une expression unique. Par exemple, en base dix, le nombre 1 possède les deux représentations 1,000... et 0,999.... L'ensemble des nombres qui ont deux représentations est dense dans l'ensemble des réels Petkovšek 1990; la classification des nombres réels qui possèdent un β-développement unique est plus compliqué que pour les bases entières Glendinning et Sidorov 2001.

Système de Parry

Si le développement du nombre réel 1 est

, avec ,

on dit que le développement de 1 est fini. Dans ce cas, on pose , sinon, on pose . Quand est ultimement périodique, le nombre est appelé un nombre de Parry et le système est un système de Parry. Le nombre d'or est un nombre de Parry ; en effet, on a et . On doit à Parry la caractérisation suivante des β-développement pour les nombres de Parry[14] :

Une suite d'entiers naturels est le β-développement d'un nombre réel de [0,1[ si et seulement si les suites décalées sont lexicographiquement inférieures à d∗β(1) pour tout .

Système de Pisot

Un nombre de Pisot-Vijayaraghavan (ou plus simplement nombre de Pisot) est un entier algébrique réel dont tous les conjugués (réels ou complexes) sont de module strictement inférieur à 1. Un système de Pisot est un système dont la base β est un nombre de Pisot.

Ces nombres jouent un rôle dans la classification des nombres dont les β-développements sont périodiques. Soit β > 1, et soit la plus petite extension de corps] des nombres rationnels contenant β. Alors tout nombre réel dans l'intervalle [0,1[ qui a un β-développement ultimement périodique β appartient à . Plus précisément[15], on a :

  • Si tout nombre dans a un β-développement ultimement périodique, alors β est un nombre de Pisot ou un nombre de Salem;
  • Si β est un nombre de Pisot, alors est l'ensemble des nombres qui ont un β-développement ultimement périodique. L'ensemble des mots représentant les entiers naturels est un langage régulier[8].

Un nombre de Pisot est aussi un nombre de Parry[16], de sorte qu'un système de Pisot est un système de Parry.

Système de Bertrand

Les systèmes de numération de Bertrand ont été introduits et étudiés par Anne Bertrand-Mathys[16]. Un système de numération général 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 du nombre 6 n'est pas une représentation gloutonne puisque .

La caractérisation suivante est due à Anne Bertrand :

Théorème — Soit un système de numération, et soit l'ensemble des facteurs apparaissant dans les β-développements des nombres réels de l'intervalle semi-ouvert [0,1[. Le système est un système de Bertrand si et seulement s'il existe un nombre réel β>1 tel que . Dans ce cas, pour , le système de numération vérifie la relation de récurrence .

Un nombre de Bertrand est un nombre réel β>1 vérifiant ces conditions.

Exemple : Le système de numération donné par la récurrence et est tel que

Les systèmes de Parry sont un sous-ensemble strict des systèmes de Bertrand; l'exemple ci-dessus est n'est pas un système de Parry[8].

Articles connexes

Notes et références

  1. a et b Rényi 1957
  2. Parry 1960.
  3. Kautz 1965
  4. Burdik et al. 1998
  5. Thurston 1989
  6. Frougny 1992
  7. Pour tout nombre réel positif ou nul, on note la partie entière et et la partie fractionnaire de .
  8. a b c et d Massuir, Peltomäki et Rigo 2019.
  9. Stakhov 2009, p. 476.
  10. Bergman 1957, p. 109.
  11. Stakhov 2009, p. 477.
  12. Hayes 2001
  13. « Weird Number Bases », sur DataGenetics (consulté le 1er février 2018)
  14. Parry 1960.
  15. Schmidt 1980
  16. a et b Bertrand-Mathis 1989.

Bibliographie

  • George Bergman, « A Number System with an Irrational Base », Mathematics Magazine, vol. 31, no 2,‎ , p. 98-110 (DOI 10.2307/3029218, JSTOR 3029218)
  • 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).
  • 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).
  • Yann Bugeaud, Distribution modulo one and Diophantine approximation, vol. 193, Cambridge, Cambridge University Press, coll. « Cambridge Tracts in Mathematics », (ISBN 978-0-521-11169-0, zbMATH 1260.11001)
  • Čestmír Burdík, Christiane Frougny, Jean-Pierre Gazeau et Rudolf Krejcar, « Beta-integers as natural counting systems for quasicrystals », Journal of Physics A: Mathematical and General, vol. 31, no 30,‎ , p. 6449–6472 (ISSN 0305-4470, DOI 10.1088/0305-4470/31/30/011, Math Reviews 1644115).
  • Aviezri S. Fraenkel, « Systems of Numeration », The American Mathematical Monthly, vol. 92, no 2,‎ , p. 105-114.
  • Christiane Frougny, « How to write integers in non-integer base », dans LATIN '92, vol. 583/1992, Springer Berlin / Heidelberg, coll. « Lecture Notes in Computer Science », (ISBN 978-3-540-55284-0, ISSN 0302-9743, DOI 10.1007/BFb0023826, lire en ligne), p. 154–164.
  • Christiane Frougny, « Numeration Systems », dans M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (no 90), (ISBN 978-0-521-81220-7), p. 203-268.
  • Paul Glendinning et Nikita Sidorov, « Unique representations of real numbers in non-integer bases », Mathematical Research Letters, vol. 8, no 4,‎ , p. 535–543 (ISSN 1073-2780, DOI 10.4310/mrl.2001.v8.n4.a12, Math Reviews 1851269, lire en ligne).
  • Brian Hayes, « Third base », American Scientist, vol. 89, no 6,‎ , p. 490–494 (DOI 10.1511/2001.40.3268, lire en ligne).
  • William H. Kautz, « Fibonacci codes for synchronization control », Institute of Electrical and Electronics Engineers. Transactions on Information Theory, vol. IT-11, no 2,‎ , p. 284–292 (ISSN 0018-9448, DOI 10.1109/TIT.1965.1053772, Math Reviews 0191744, lire en ligne).
  • 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 (DOI 10.1016/j.aam.2019.03.003).
  • William 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, Math Reviews 0142719).
  • Marko Petkovšek, « Ambiguous numbers are dense », The American Mathematical Monthly, vol. 97, no 5,‎ , p. 408–411 (ISSN 0002-9890, DOI 10.2307/2324393, JSTOR 2324393, Math Reviews 1048915).
  • Alfréd Rényi, « Representations for real numbers and their ergodic properties », Acta Mathematica Academiae Scientiarum Hungaricae, vol. 8, nos 3–4,‎ , p. 477–493 (ISSN 0001-5954, DOI 10.1007/BF02020331, Math Reviews 0097374).
  • Michel Rigo, Formal Languages, Automata and Numeration Systems, vol. 2 : Applications to Recognizability and Decidability, London/Hoboken, NJ, ISTE/John Wiley & Sons, Inc., .
  • Klaus Schmidt, « On periodic expansions of Pisot numbers and Salem numbers », The Bulletin of the London Mathematical Society, vol. 12, no 4,‎ , p. 269–278 (ISSN 0024-6093, DOI 10.1112/blms/12.4.269, Math Reviews 576976).
  • Alexey Stakhov, The Mathematics of Harmony: From Euclid to Contemporary Mathematics and Computer Science, World Scientific, (ISBN 9812775838, présentation en ligne)

Lien externe