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 $\beta >1$, l'écriture

$x=d_{n}\cdots d_{2}d_{1}d_{0},d_{-1}d_{-2}\cdots d_{-m}\cdots$

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

$x=\beta ^{n}d_{n}+\cdots +\beta ^{2}d_{2}+\beta d_{1}+d_{0}+\beta ^{-1}d_{-1}+\beta ^{-2}d_{-2}+\cdots +\beta ^{-m}d_{-m}+\cdots$.

Les nombres $d_{i}$ sont des entiers positifs ou nuls plus petits que $\beta$. 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 et étudiée en détail ensuite par William Parry en 1960. 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 et dans la modélisation de quasi-cristaux.

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 $1,000\cdots =0,999\cdots$. Les β-développements, même finis, ne sont pas nécessairement uniques. Ainsi, si $\beta =\varphi$, est le nombre d'or, on a $1+\varphi =\varphi ^{2}$, 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, et formulé comme suit par exemple par Christiane Frougny :

Soit $x$ un nombre réel positif ou nul. Soit $k$ l'entier tel que $\beta ^{k}\leq x<\beta ^{k+1}$. On pose :

$d_{k}=\lfloor x/\beta ^{k}\rfloor$ et $r_{k}=\{x/\beta ^{k}\}$,

et pour $k>j>-\infty$ :

$d_{j}=\lfloor r_{j+1}\beta \rfloor$ et $r_{j}=\{r_{j+1}\beta \}$.

En d'autres termes, ce β-développement canonique de $x$ est construit en prenant pour $d_{k}$ le plus grand entier tel que $\beta ^{k}d_{k}\leq x$, puis en prenant le plus grand entier $d_{k-1}$ tel que $\beta ^{k}d_{k}+\beta ^{k-1}d_{k-1}\leq x$ et ainsi de suite. La suite des $d_{j}$ est notée $d_{\beta }(x)$. Ce choix produit la plus grande séquence en ordre lexicographique représentant $x$. On a

$x=\sum _{n\leq k}d_{n}\beta ^{n}$

et si $0<x\leq 1$

$x=\sum _{n\geq 0}d_{n}\beta ^{-n}$.

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 : un système de numération (positionnel) est donné par une suite croissante $U=(U_{n})_{n\geq 0}$ d'entiers positifs, avec $U_{0}=1$ et tel que $C_{U}:=\sup {(U_{n+1}/U_{n}}<+\infty$. On associe à la suite $U$ les chiffres $A_{U}=\{0,1,\ldots C_{U}\}$. La représentation gloutonne d'un entier positif $n$ est la séquence

$\operatorname {rep} _{U}(n)=w_{\ell -1}\cdots w_{0}$

composée de chiffres dans $A_{U}$ vérifiant

$n=\sum _{i=0}^{\ell -1}w_{i}U_{i}$

avec les conditions :

$w_{\ell -1}\neq 0$ et $\sum _{i=0}^{j-1}w_{i}U_{i}<U_{j}$ pour $j=1,\ldots ,\ell$.

C'est bien entendu la dernière des conditions qui détermine le caractère glouton de la représentation. On note

$\operatorname {rep} _{U}(\mathbb {N} )=\{\operatorname {rep} _{U}(n)\mid n\in \mathbb {N} \}$

l'ensemble des mots représentant les entiers naturels.

Exemples

Base √2

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

1911₁₀ = 11101110111₂ = 101010001010100010101_{${\sqrt {2}}$}

et

5118₁₀ = 1001111111110₂ = 1000001010101010101010100_{${\sqrt {2}}$}.

Ceci implique en particulier que tout entier peut être écrit en base ${\sqrt {2}}$ 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_{${\sqrt {2}}$} a une diagonale de longueur 10_{${\sqrt {2}}$} et un carré de côté 10_{${\sqrt {2}}$} a une diagonale de longueur 100_{${\sqrt {2}}$}. Une autre utilisation est d'illustrer la proportion d'argent notée $\delta _{Ag}$, qui vaut $1+{\sqrt {2}}\simeq 2{,}414~213~562$ (suite A014176 de l'OEIS), puisqu'elle s'écrit simplement $\delta _{Ag}=11_{\sqrt {2}}$ en base ${\sqrt {2}}$. Par ailleurs, l'aire d'un octogone régulier de côté 1_{${\sqrt {2}}$} est 1100_{${\sqrt {2}}$}, l'aire d'un octogone régulier de côté 10_{${\sqrt {2}}$} est 110000_{${\sqrt {2}}$}, l'aire d'un octogone régulier de côté 100_{${\sqrt {2}}$} est 11000000_{${\sqrt {2}}$}, etc...

Base φ

La base d'or est le système de numération utilisant le nombre d'or, à savoir $\varphi ={\frac {1+{\sqrt {5}}}{2}}$ 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 ». 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 = φ². 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 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.

Base e

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

La base e est le choix le plus économique comme base $\beta >1$ , quand l’économie d'une base est mesurée comme le produit de la base 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 = π × rayon², un cercle de rayon 1_π a une aire égale à 10_π, un cercle de rayon 10_π a une aire égale à 1000_π etc.

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.

Unicité

Il n'existe aucun système de numération positionnel dans lequel tout nombre admettrait 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ée que pour les bases entières (Glendinning et Sidorov 2001).

Système de Parry

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

$d_{\beta }(1)=t_{1}\cdots t_{m}0^{\omega }$, avec $t_{m}\neq 0$,

on dit que le développement de 1 est fini. Dans ce cas, on pose $d_{\beta }^{*}(1)=(t_{1}\cdots t_{m-1}(t_{m}-1))^{\omega }$, sinon, on pose $d_{\beta }^{*}(1)=d_{\beta }(1)$. Quand $d_{\beta }^{*}(1)$ est ultimement périodique, le nombre $\beta$ est appelé un nombre de Parry et le système est un système de Parry. Le nombre d'or $\varphi$ est un nombre de Parry ; en effet, on a $d_{\beta }(1)=11$ et $d_{\beta }^{*}(1)=(10)^{\omega }$. On doit à Parry la caractérisation suivante des β-développement pour les nombres de Parry :

Une suite $x=(x_{i})_{i\geq 1}$ d'entiers naturels est le β-développement d'un nombre réel de [0,1[ si et seulement si les suites décalées $(x_{n+i})_{i\geq 1}$ sont lexicographiquement inférieures à $d_{\beta }^{*}(1)$d∗β(1) pour tout $n\geq 0$.

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 $\mathbb {Q} (\beta )$ 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 à $\mathbb {Q} (\beta )$. Plus précisément, on a :

• Si tout nombre dans $\mathbb {Q} (\beta )\cap [0,1[$ 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 $\mathbb {Q} (\beta )\cap [0,1[$ 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.

Un nombre de Pisot est aussi un nombre de Parry, 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-Mathis. Un système de numération général $U$ est un système de Bertrand si, pour tout mot non vide $w$ sur $A_{U}$, on a

$w\in \operatorname {rep} _{U}(\mathbb {N} )$ si et seulement si $w0\in \operatorname {rep} _{U}(\mathbb {N} )$.

Le système de numération usuel en base $k$ 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 $F=\{1,3,4,7,\ldots \}$ définie par $F_{0}=1,F_{1}=3,F_{n+2}=F_{n+1}+F_{n},$ 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\times 3+0)$ du nombre 6 n'est pas une représentation gloutonne puisque $\operatorname {rep} _{F}(6)=102(=4+2\times 1)$.

La caractérisation suivante est due à Anne Bertrand :

Théorème — Soit $U=(U_{n})$ un système de numération, et soit $F(D_{\beta })$ l'ensemble des facteurs apparaissant dans les β-développements $D_{\beta }$ des nombres réels de l'intervalle semi-ouvert [0,1[. Le système $U$ est un système de Bertrand si et seulement s'il existe un nombre réel β>1 tel que $F(D_{\beta })=0^{*}\operatorname {rep} _{U}(\mathbb {N} )$. Dans ce cas, pour $d_{\beta }^{*}((1)=(t_{i})$, le système de numération vérifie la relation de récurrence $U_{n+1}=t_{1}U_{n}+\cdots U_{0}t_{n}+1$.

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 $U_{n+1}=3U_{n}+1$ et $U_{0}=1$ est tel que

$0^{*}\operatorname {rep} _{U}(\mathbb {N} )=\{0,1,2\}^{*}\cup \{0,1,2\}^{*}30^{*}$

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.

Articles connexes

• Développement décimal
• Série entière
• Numération d'Ostrowski

Bibliographie

• George Bergman, « A Number System with an Irrational Base », Mathematics Magazine, vol. 31, n^o 2,‎ 1957, 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, n^os 3-4,‎ 1989, 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, n^o 1,‎ 1997, 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 », 2012, 300 p. (ISBN 978-0-521-11169-0, zbMATH 1260.11001, lire en ligne)
• Č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, n^o 30,‎ 1998, p. 6449–6472 (ISSN 0305-4470, DOI 10.1088/0305-4470/31/30/011, MR 1644115, CiteSeer^x 10.1.1.30.5106).
• Aviezri S. Fraenkel, « Systems of Numeration », The American Mathematical Monthly, vol. 92, n^o 2,‎ 1985, 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 », 1992 (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 » (n^o 90), 2002 (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, n^o 4,‎ 2001, p. 535–543 (ISSN 1073-2780, DOI 10.4310/mrl.2001.v8.n4.a12, MR 1851269, lire en ligne).
• Brian Hayes, « Third base », American Scientist, vol. 89, n^o 6,‎ 2001, 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, n^o 2,‎ 1965, p. 284–292 (ISSN 0018-9448, DOI 10.1109/TIT.1965.1053772, MR 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,‎ 2019, 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, n^os 3–4,‎ 1960, p. 401–416 (ISSN 0001-5954, DOI 10.1007/bf02020954, MR 0142719).
• Marko Petkovšek, « Ambiguous numbers are dense », The American Mathematical Monthly, vol. 97, n^o 5,‎ 1990, p. 408–411 (ISSN 0002-9890, DOI 10.2307/2324393, JSTOR 2324393, MR 1048915).
• Alfréd Rényi, « Representations for real numbers and their ergodic properties », Acta Mathematica Academiae Scientiarum Hungaricae, vol. 8, n^os 3–4,‎ 1957, p. 477–493 (ISSN 0001-5954, DOI 10.1007/BF02020331, MR 0097374).
• Michel Rigo, Formal Languages, Automata and Numeration Systems, vol. 2 : Applications to Recognizability and Decidability, London/Hoboken, NJ, ISTE/John Wiley & Sons, Inc., 2014.
• Klaus Schmidt, « On periodic expansions of Pisot numbers and Salem numbers », The Bulletin of the London Mathematical Society, vol. 12, n^o 4,‎ 1980, p. 269–278 (ISSN 0024-6093, DOI 10.1112/blms/12.4.269, MR 576976).
• Alexey Stakhov, The Mathematics of Harmony : From Euclid to Contemporary Mathematics and Computer Science, World Scientific, 2009, 694 p. (ISBN 978-981-277-583-2 et 981-277-583-8, présentation en ligne)
• W. P. Thurston, Groups, tilings and finite state automata, coll. « Summer AMS Colloquium Lectures », 1989 (lire en ligne)

Lien externe

• (en) Eric W. Weisstein, « Base », sur MathWorld