Numération en base non entière
# 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_{10}$ = $11101110111_2$ = 101010001010100010101$_{√2{\displaystyle{\sqrt{2}}}}$

et

    $5118_{10}$ = $1001111111110_2$ = 1000001010101010101010100$_{√2{\displaystyle{\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$_{√2{\displaystyle{\sqrt{2}}}}$ a une diagonale de longueur 10$_{√2{\displaystyle{\sqrt{2}}}}$ et un carré de côté 10$_{√2{\displaystyle{\sqrt{2}}}}$ a une diagonale de longueur 100$_{√2{\displaystyle{\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$_{√2{\displaystyle{\sqrt{2}}}}$ est 1100$_{√2{\displaystyle{\sqrt{2}}}}$, l'aire d'un octogone régulier de côté 10$_{√2{\displaystyle{\sqrt{2}}}}$ est 110000$_{√2{\displaystyle{\sqrt{2}}}}$, l'aire d'un octogone régulier de côté 100$_{√2{\displaystyle{\sqrt{2}}}}$ est 11000000$_{√2{\displaystyle{\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 = $φ^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 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^2,$ 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.

