AnnaChiaraLai Onexpansionsinnon-integerbase R´esum´edelathese

(1)

“MODELLI EMETODIMATEMATICI PER LA TECNOLOGIA E LASOCIETA`” XXIICICLO

AND

UNIVERSITE´ PARIS7 - PARISDIDEROT

DOCTORAT D’INFORMATIQUE

R´esum´e de la these

On expansions in non-integer base

Anna Chiara Lai

Dipartimento di Metodi e Modelli Matematici per le Scienze applicate Via Antonio Scarpa, 16 - 00161 Roma.

and

Laboratoire d’Informatique Algorithmique : Fondements et Applications CNRS UMR 7089, Universit´e Paris Diderot - Paris 7,

Case 7014 75205 Paris Cedex 13

(2)

TABLE DES MATIERES`

Introduction 1

1. Repr´esentations en base complexe 4

1.1. Introduction 4

1.2. Caract´erisation de l’enveloppe convexe des nombres repr´esentables 4

1.3. Repr´esentabilit´e en base complexe 6

1.4. Conclusions et d´eveloppements futurs 7

2. Repr´esentations en base n´egative 7

2.1. Introduction 7

2.2. Syst`emes dynamiques symboliques et l’ordre altern´e 7

2.3. Caract´erisation des(−q)-shifts sofiques et de type fini 8

2.4. Entropie du(−q)-shift 8

2.5. Le cas Pisot 8

2.6. Conversion séquentielle de la base positive à la base négative 8

3. Nombre d’or généralisé pour alphabets ternaires 8

3.1. Introduction 8

3.2. Bases critiques 9

3.3. Alphabets ternaires normaux 9

3.4. Bases critiques pour alphabets ternaires 9

3.5. Bases critiques et suites m-admissibles 10

4. Suites univoques pour alphabets ternaires 11

R´ef´erences 11

INTRODUCTION

Cette thèse est consacrée à l’étude des développements en sommes de la forme (1)

∞ i=1

∑

x_i qⁱ

o ù les coefficients x_iappartiennent à un ensemble fini de réels positifs, l’alphabet, et o ù la base est un nombre réel ou complexe. Pour assurer la convergence de (1), la base q est supposée stricte- ment plus grande que 1 en module. Quand un nombre x satisfait x = _∑^∞_i=1^x_qⁱ_i pour une suite de chiffres(x_i)_i≥1dans l’alphabet A, on dit que x est représentable en base q avec alphabet A, et on ap- pelle(x_i)_i≥1 =x₁x₂· · · une représentation de x. La notion de représentabilité est l’un des thèmes principaux de cette thèse, et on peut l’étudier à partir de concepts très familiers. Par exemple, quand l’alphabet est{0, 1}et la base est q=2, alors tout x∈ [0, 1]satisfait :

x=

∑

∞ i=1

x_i 2ⁱ

pour une suite(x_i)_i≥1 = x₁x₂· · · qui est la représentation binaire classique de x. De même la représentation décimale de x n’est rien d’autre que la représentation (x_i)_i≥1 avec chiffres dans {0, 1, . . . , 9}et base 10. Le fait que tout nombre de[0, 1] admet une représentation décimale est

(3)

trivial, mais non général. Si l’alphabet A est ´gal à{0, 2}et la base est q=3, alors il est bien connu que

Λ_q,A=Λ_3,{0,2} = {

∑

∞ i=1

x_i

3ⁱ |x_i∈ {0, 2}, i≥1}

co¨ıncide avec l’ensemble de Cantor. En particulier Λ_3,{0,2}est un ensemble totalement discontinu strictement inclus dans l’intervalle unité. En prenant comme alphabet{0, 1, 2}au lieu de{0, 2}, l’ensemble[0, 1]est totalement représentable, i.e. Λ_3,{0,1,2} = [0, 1]. Pour souligner le fait que le chiffre 1 est nécessaire pour représenter l’intervalle unité, on dira que l’alphabet{0, 2}est à chiffres manquants.

Nous considérons ensuite une généralisation du concept de représentabilité. Fixons un alpha- bet A et une base q, réelle ou complexe, et supposons que pour x6∈Λq,Ail existe un entier positif ou nul n tel que x/qⁿ∈Λ_q,A. Comme

x qⁿ =

∑

^∞

i=1

xi

qⁱ implique x=

n−1 i=0

∑

xn−iqⁱ+

∑

^∞

i=1

xn+i

qⁱ =x1qⁿ⁻¹+ · · · +xn−1q+xn+^xⁿ⁺¹ q + · · · nous pouvons représenter x par une expression de la forme x₁· · ·x_n. x_n+1· · ·, o ù le symbole . indique le facteur d’échelle qⁿ. Si l’on suppose que la base est 10, cette notation prend une forme familière ; en effet 1 . 2 dénote traditionnellement la valeur 10× (₁₀¹ +₁₀²₂).

Si tout nombre d’un ensemble Λ admet une représentation “généralisée” en base q avec alpha- bet A, le couple(A, q)est un système de numération (positionnel) pour Λ.

Voyons quelques exemples. Les réels positifs sont représentables en base entière b > 1 avec alphabet{0, 1, . . . , b−1}, et en base non entière q> 1 et alphabet{0, 1, . . . ,bqc}. Le choix d’une base négative conduit à la représentabilité de R : tout réel peut être représenté en base entière

−b, avec b>1, et alphabet{0, 1, . . . , b−1}; tout réel peut être représenté en base non entière−q et alphabet{0, 1, . . . ,bqc}. Le cas de la base non entière positive est traité dans le papier fonda- teur de Rényi [Rén57], et le cas de la base non entière négative a été récemment introduit dans [IS09]. Les alphabets {0, 1, . . . , b−1} et {0, 1, . . . ,bqc} sont dits canoniques. Pedicini [Ped05] a

étudié la représentabilité en base réelle positive et alphabets à chiffres manquants, et a montré que({a₁, . . . , a_J}, q)est un un système de numération pour les réels positifs si et seulement si q ≤ (a_J−a₁)/ max{aj+1−a_j}. Le cas de la base complexe est plus compliqué, et les résultats de représentabilité ont été obtenus seulement pour certaines classes de bases complexes, par exemple les entiers de Gauss de la forme −n±i avec n ∈ N, les racines√^k

n avec n ∈ Z et k ∈ N, les nombres complexes quadratiques.

Dans le cas d’une base positive non entière, l’ensemble des valeurs représentables Λ_q,Ane peut avoir que deux structures topologiques : soit c’est un intervalle, soit c’est un ensemble totalement discontinu. Clairement le couple(A, q)permet de représenter complètement R⁺ si et seulement si on se trouve dans le premier cas. On peut donc en déduire que tout réel positif ou nul peut être représenté en base q avec alphabet A si et seulement si Λ_q,Aest un ensemble convexe. L’étude de Λ_q,Aest aussi simplifiée grâce au fait que le plus petit et que le plus grand nombre représentables sont explicitement connus :

min Λ_q,A = ^{min A} q−1 =

∑

∞ i=1

min A

qⁱ et max Λ_q,A= ^{max A} q−1 =

∑

∞ i=1

max A qⁱ .

Quand on considère une base complexe, il y a des changements. La convexité de Λ_q,An’est pas une condition nécessaire de représentabilité, par exemple tout nombre complexe est représentable en base −1+i et alphabet {0, 1}, mais Λ_q,A est alors la courbe du dragon, un ensemble non

(4)

convexe. de plus, la frontière de Λ_q,A peut avoir une structure fractale, même quand il y a totale représentabilité.

Notre approche pour le problème de représentabilité en base complexe consiste en l’étude de l’enveloppe convexe de Λ_q,Alorque q a un argument rationnel. Comme la convexité de Λ_q,Aest une condition suffisante pour la représentabilité totale, un tel résultat procure une classe nouvelle de systèmes de numération en base complexe.

Jusqu’ici nous avons parlé de conditions de représentabilité, c’est-à-dire que nous nous sommes intéressée au problème de savoir si un nombre réel ou complexe peut être représenté dans une base donnée avec un alphabet donné. Mais quand on est s ûr de la représentabilité, par exemple en prenant une base non entière±q et l’alphabet canonique Aq = {0, 1, . . . ,bqc}, beaucoup d’autres questions se posent. Par exemple, comment représenter ces nombres, quelles sont les propriétés combinatoires et dynamiques de ces représentations, combien de représentations différentes peut avoir un nombre. Dans ce qui suit nous rappelons rapidement quelques résultats classiques afin de pouvoir conceptualiser nos résultats originaux.

La preuve classique que tout réel positif ou nul admet une représentation en base q et alphabet Aqest obtenue par un algorithme glouton. Les suites ainsi obtenues sont appelées représentations gloutonnes ou q-développements, et elles ont des propriétés intéressantes. Par exemple, le q-développe- ment de x ∈ [0, 1] est la plus grande dans l’ordre lexicographique de toutes les représentation x. Ceci entraˆıne que si l’on tronque le q-développement d’un nombre x, l’erreur ainsi commise est minimale. Un autre trait important est la monotonie par rapport à la valeur numérique : les nombres sont ordonnés par l’ordre lexicographique sur leurs développements. Ces propriétés ont permis de nombreuses recherches dans ce domaine concernant plusieurs champs des mathématiques et de l’informatique théorique, comme la théorie des nombres, la théorie ergodique, la dynamique symbolique, la théorie des automates. En particulier la caractérisation des q-développements donnée par Parry [Par60] a permis l’étude de la cl ôture de l’ensemble des q-développements d’un point de vue dynamique symbolique, c’est-à-dire du q-shift.

Le calcul de l’entropie, la reconnaissabilité par automate fini et l’existence d’automates finis pour effectuer certaines opérations arithmétiques en base positive ont été bien étudiés. Nous ob- tenons des résultats similaires en base négative.

Un autre aspect largement étudié en base positive non entière est l’existence de différentes représentations d’un même nombre. Dans les années 90, Erd˝os, avec Horváth, Jo ó et Komornik, a consacré une série de papiers au nombre de possibles représentations d’un même nombre, en base 1 < q< 2 avec{0, 1}, avec une attention particulière sur les représentations de 1. Ces résultats, ainsi que ceux de Dar óczy et Kátai [DK93], ont permis de clarifier la structure de l’ensemble des représentations uniques dans ce cas. En particulier, quand la base est inférieure au nombre d’or, tout réel positif a au moins deux représentations différentes ; quand la base est comprise entre le nombre d’or et la constante de Komornik-Loreti il existe un ensemble dénombrable de valeurs ayant une représentation unique ; quand la base est supérieure à la constante de Komornik-Loreti l’ensemble des valeurs ayant une représentation unique a la puissance du continu.

Nous prouvons que si la base est positive non entière, il existe une sorte de “nombre d’or généralisé” pour des alphabets arbitraires, c’est-à-dire nous montrons que les représentations ne sont jamais uniques si et seulement si la base est plus petite qu’une valeur critique. Dans le cas d’un alphabet ternaire nous caractérisons explicitement cette base critique et les représentations uniques pour des bases assez petites.

(5)

Le travail de recherche sur les bases complexes a été réalisé sous la supervision de Paola Loreti.

La plupart des résultats sur les bases négatives ont été obtenus en collaboration avec Christiane Frougny et peuvent être trouvés en [FL09]. Les résultats sur l’existence et la caractérisation des bases critiques pour les alphabets généraux sont un travail en collaboration avec Vilmos Komor- nik et Marco Pedicini [KLP].

1. REPRESENTATIONS EN BASE COMPLEXE´

Nous considérons des représentations avec des alphabets arbitraires et des bases de la forme pe^2πiⁿ avec p > 1 et n ∈ N. Nous étudions l’enveloppe convexe de l’ensemble des nombres représentables en donnant tout d’abord une description géométrique puis une caractérisation ex- plicite de ses points extrémaux. Nous donnons aussi une condition de caractérisation pour la convexité de l’ensemble des nombres représentables.

1.1. Introduction. Les premiers systèmes de numération à base complexe semblent être ceux

à base 2i avec alphabet{0, 1, 2, 3}, et à base −1+i avec alphabet {0, 1}, introduits respective- ment par Knuth en [Knu60] et par Penney en [Pen65]. Il y eu ensuite beaucoup de travaux sur la représentabilité en base complexe, e.g. voir [KS75] pour les entiers de Gauss de la forme−n±i avec n ∈ N, [KK81] pour les corps quadratiques, et [DK88] pour le cas général. Loreti and Ko- mornik ont poursuivi le travail de [DK88] en introduisant un algorithme glouton dans le cas des bases complexes à argument non rationnel, [KL07]. Dans les années 80, une recherche pa- rallèlle a été développée par Gilbert. Dans [Gil81] il a décrit la nature fractale de l’ensemble des nombres représentables, par exemple l’ensemble des nombres représentables en base−1+i avec chiffres{0, 1}se trouve être la courbe du dragon [Knu71]. La dimension de Hausdorff de certains ensembles des nombres représentables a été calculée en [Gil84] et une notion plus faible d’auto- similarité a été introduite pour l’étude de la frontière de ces ensembles [Gil87]. Les systèmes de numération à base complexe et la géométrie de l’ensemble des nombres représentables ont été largement étudiés du point de vue de leurs relations avec les IFS et les pavages du plan complexe.

Pour un survol de la topologie des tuiles associées aux bases appartenant à des corps quadratiques nous renvoyons à [AT04].

Les systèmes de numération à base complexe ont plusieurs applications. Par exemple en arithmétique des ordinateurs, ces systèmes permettent de traiter les opérations arithmétiques d’une manière unifiée, sans traiter séparément la partie réelle et la partie imaginaire — voir [Knu71], [Gil84]

et [FS03]. La représentation en base complexe a aussi été utilisée en cryptographie dans le but d’accélérer les calculs comme l’exponentiation modulaire [DJW85] et la multiplication sur des courbes elliptiques [Sol00]. Enfin nous renvoyons à [Pic02] pour une étude sur leur application à la compression d’image sur des pavages fractals.

1.2. Caractérisation de l’enveloppe convexe des nombres représentables. Nous étudions la forme de l’enveloppe convexe des nombres représentables enn base qn,p:=pe^2πⁿⁱavec alphabet A. Nous adoptons les notations suivantes.

Notation 1.1. On note

Λ_n,p,A=:{

∑

∞ k=1

x_kq^−k_n,p|x_k ∈A}

l’ensemble des nombres repr´esentables en base qn,p:=pe^2πⁿⁱavec alphabet A.

Notation 1.2. Soit(x₀· · ·x_n−1)une suite dans{0, 1}ⁿ. On d´efinit(x₀· · ·x_n−1)_q := _∑ⁿ⁻¹_j=0 x_jq^j et on introduit le d´ecalage circulaire σ sur les suites finies : σ(x₀x₁· · ·xn−1):= (x₁· · ·xn−1x₀). La fermeture

(6)

(A) Enveloppe convexe de Λ_3,21/2,{0,1}

(B) En- veloppe convexe de Λ_4,21/2,{0,1}

(C) Enveloppe convexe de Λ_5,21/2,{0,1}

(D) Enveloppe convexe de Λ_6,21/2,{0,1}

(E) Enveloppe convexe de Λ_7,21/2,{0,1}

(F) Enveloppe convexe de Λ_8,21/2,{0,1}

FIGURE 1. L’ensemble Λ_n,21/2,{0,1}, avec n = 3, . . . , 9 est approximé par l’en- semble des représentations de longueur 14. La base q_8,21/2 =1+i est un entier de Gauss qui a été étudié en particulier en [Gil81].

de(x₀· · ·x_n−1)relativement `a σ est not´ee Orb(x₀· · ·x_n−1):= {σ^j(x₀x₁· · ·x_n−1) | j=0, . . . , n−1}. Finalement, soit Orb(x0· · ·xn−1)_q:= {σ^j(x0x₁· · ·xn−1)_q |j=0, . . . , n−1}.

Theorem 1.1. Pour tout n≥1, p>1 et q_n,p=pe^2πⁿⁱ, l’enveloppe convexe H_con(Λ_n,p,A)est un polygone avec les propri´et´es suivantes :

(a) les arêtes sont deux à deux parallèles à q⁰_n,p, . . . , qⁿ⁻¹_n,p ; (b) si n est impair alors Hcon(Λ_n,p,A)a 2n points extrêmaux ; (c) si n est pair alors Hcon(Λ_n,p,A)a n points extrêmaux.

Example 1.1. Si n = 3 et si p > 1 alors pour tout alphabet A l’enveloppe convexe de Λ_n,p,A est un hexagone. Si n=4 et si p>1 alors pour tout alphabet A l’enveloppe convexe of Λ_n,p,Aest un rectangle.

Theorem 1.2. Soit n≥1, p>1 et A un alphabet, et notonsE (Λ_n,p,A)l’ensemble des points extrˆemaux de Hcon(Λ_n,p,A). Si n est impair alors :

(7)

E (Λ_n,p,A) = ^{max A}−min A pⁿ−1

³

Orb(1^bn/2c0^n−bn/2c)qn,p∪Orb(1^dn/2e0^n−dn/2e)qn,p

´ +

n−1 j=0

∑

min A q_n,p^j ;

si n est pair :

E (Λ_n,p,A) = ^{max A}−min A

pⁿ−1 Orb(1^n/20^n/2)qn,p+

n−1 j=0

∑

min A q_n,p^j ;

1.3. Représentabilité en base complexe. Nous prouvons la caractérisation suivante des ensembles représentables convexes.

Theorem 1.3. L’ensemble des nombres repr´esentables en base q_n,p et alphabet A = {a₁, . . . , a_J} est convexe si et seulement si

j=1,...,J−1max a_j+1−a_j≤ ^{max A}−min A pⁿ−1 .

(A) Λ_3,21/3,{0,1} (B) Λ_3,21/3+0.1,{0,1} (C) Λ_3,21/3+0.2,{0,1}

(D) Λ_3,21/3+0.3,{0,1} (E) Λ_3,21/3+0.4,{0,1} (F) Λ_3,21/3+0.5,{0,1}

FIGURE2. Λ_3,21/3+0.1k,{0,1}, avec k = 0, . . . , 5, est approxim´e par l’ensemble des repr´esentations de longueur 14.

Example 1.2. Si p< 2^1/n et A= {0, 1}alors Λ_n,p,Aest un 2n-polygone quand n est impair, et est un n-polygone quand n est pair.

Example 1.3. Si A= {0, 1, . . . ,bpⁿc}alors Λ_n,p,Aest un ensemble convexe.

1.4. Conclusions et développements futurs. Nous remarquons que l’ensemble des nombres repré- sentables peut être vu comme l’attracteur d’un IFS linéaire F_q,A, qui dépend de la base et de l’alphabet. La caractérisation de l’enveloppe convexe de l’ensemble des nombres représentables donne une méthode opératoire pour définir un domaine borné de F_q,A.

(8)

Nous avons donné une condition suffisante pour la dimension de Hausdorff pleine de l’ensemble des nombres représentables, mais le problème général reste ouvert. Les relations établies dans ce chapitre pourraient aider à trouver une solution — au moins pour les bases à argument rationnel. La définition d’un algorithme glouton global et une caractérisation partielle basée sur une comparaison chiffre à chiffre pourrait suivre par ces arguments.

2. REPRESENTATIONS EN BASE N´ EGATIVE´

Ito et Sadahiro ont récemment introduits et caractérisés les représentations en base négative non entière−q en [IS09]. Ils ont montré que le(−q)-shift est sofique si et seulement si le(−q)- développement du nombre−_q+1^q est ultimement périodique. Notre but est de poursuivre leur travail, en montrant que beaucoup de propriétés des systèmes de numération à base positive s’éten- dent au cas négatif, la diff´rence principale étant que les ensembles des nombres représentables sont différents.

2.1. Introduction. Les représentations en base négative entière−b, avec b≥2, semblent avoir été introduites par Gr ünwald en [Gru85], et redécouvertes par plusieurs auteurs, voir le commentaire historique fait par Knuth [Knu71]. Le choix d’une base négative−b et de l’alphabet{0, . . . , b−1} est intéressant, car il produit une représentation sans signe pour tous les nombres (positifs ou nègatifs). Il est facile de voir qu’une suite sans 0 en tête représente un entier positif si et seulement si sa longueur est paire. Nous notons(w.)_−b := _∑^k_i=0w_k(−b)ⁱ pour tout w = w_k· · ·w₀ dans{0, . . . , b−1}^∗sans 0 en tête. La propriété classique de monotonicité entre l’ordre lexicographique sur les mots et les valeurs numériques n’est plus satisfaite en base négative, par exemple 3= (111.)₋₂, 4= (100.)₋₂et 111>_lex100. Cependant il est possible de retrouver une telle corres- pondance en introduisant un autre ordre sur les mots, dénoté dans la suite par≺et appelé ordre alterné.

Les représentations en base négative apparaissent aussi dans certains systèmes de numération

à base complexe, par exemple la base q = 2i satisfait q² = −4 (voir [Fro99] pour une étude de leurs propriétés du point de vue de la théorie des automates).

2.2. Syst`emes dynamiques symboliques et l’ordre altern´e.

Definition 2.1. Soit x = x₁x2· · ·, y = y₁y2· · · des mots infinis ou finis de mˆeme longueur sur un alphabet.

Soit x6=y et soit i le plus petit indice tel que x_i6=y_i. L’ordre altern´e≺satisfait : (2) x≺y si et seulement si (−1)ⁱ(x_i−y_i) <0.

Pour tout mot infini fixé s, nous considérons le système dynamique symbolique S= {w= (w_i)_i∈Z∈ A^Z| ∀n, s¹wnwn+1· · · }.

Nous avons alors :

Proposition 2.1. Le sous-shift S= {w= (w_i)_i∈Z∈ A^Z| ∀n, s¹wnwn+1· · · }est reconnaissable par un automate infini d´enombrable.

Proposition 2.2. Soit le syst`eme dynamique symbolique S = {w = (w_i)_i∈Z ∈ A^Z | ∀n, s ¹ w_nw_n+1· · · }. Alors

(a) S est un sous-shift sofique si et seulement si s est ultimement p´eriodique ; (b) S est un sous-shift de type fini si et seulement si s est purement p´eriodique.

(9)

2.3. Caractérisation des (−q)-shifts sofiques et de type fini. Le (−q)-shift est la fermeture de l’ensemble des (−q)-développements de Ito et Sadahiro. Par leur caractérisation du (−q)-shift, [IS09], on peut obtenir le résultat suivant.

Theorem 2.1. The (−q)-shift est un syst`eme de type fini si et seulement si γ−q(−_q+1^q )est purement p´eriodique.

2.4. Entropie du(−q)-shift. L’entropie topologique du(−q)-shift est ´egale `a l’entropie topolo- gique du q-shift classique.

Theorem 2.2. L’entropie topologique du(−q)-shift est ´egale `a log q.

2.5. Le cas Pisot. Certains résultats en base de Pisot positive s’étendent au cas négatif.

Theorem 2.3. Si q est un nombre de Pisot, tout element de Q(q) ∩I−qhas an eventually periodic(−q)- expansion.

Theorem 2.4. Si q est un nombre de Pisot, alors la normalisation en base−q sur tout alphabet, l’addition en base−q et la conversion de la base−q `a la base q sont r´ealisables par transducteur fini.

2.6. Conversion séquentielle de la base positive à la base négative. Nous donnons un algo- rithme poids forts d’abord pour cette conversion.

Proposition 2.3. Soit q >2. La conversion d’un q-développement d’un nombre à une représentation en base−q du même nombre peut être réalisée par un algorithme en ligne.

2.7. Conclusions et développements futurs. Ces résultats confirment que les(−q)-développements sont une généralisation naturelle des q-développements classiques, la différence principale por- tant sur les ordres — alterné pour les bases négatives et lexicographique pour les positives. Il pourrait être intéressant de généraliser ces ordres au cas des bases complexes.

Nous pensons aussi que le proposition2.3peut être étendue au cas q≥2 et que l’on peut montrer que la conversion d’une base positive Pisot à la base négative est réalisable par un automate fini en ligne.

3. NOMBRE D’OR GEN´ ERALIS´ E POUR ALPHABETS TERNAIRES´

Nous nous intéressons maintenant aux développements en base réelle q>1 avec chiffres dans un alphabet arbitraire A = {a1, . . . , aJ}. Pour un alphabet à deux lettres A = {a1, a2}le nombre d’or G := (1+√

5)/2 joue un r ôle spécial : il existe des développements uniques non triviaux en base q si et seulement si q > G. Notre but est de déterminer des critères analogues pour les alphabets ternaires A= {a₁, a₂, a₃}.

3.1. Introduction. Dans les années cinquante, Rényi [Rén57] a introduit un nouveau système de numération en base non entière q avec un alphabet de chiffres entiers{0, 1, . . . ,bqc}. Depuis, ces représentations ont été beaucoup étudiées, tant du point de vue de la théorie de la mesure que de la théorie des nombres. L’une des propriétés les plus intéressantes de ces systèmes est la redon- dance des représentations. Par exemple, Sidorov a montré que si 1 < q < 2 alors presque tout nombre a un continuum de développements distincts [Sid03]. D’autres travaux ont été consacré

à l’étude des développements uniques et à leurs propriétés topologiques, voir [EJK90], [EHJ91], [DK93],[KL98] et [DVK09].

Puisque l’unicité d’un développement est préservée quand on prend une base plus grande ([DK93]), il existe des bases frontières séparant les structures topologiques possibles de l’ensemble des développements uniques, noté Uq. Par exemple, pour les bases inférieures au nombre d’or,

(10)

l’ensemble Uqne contient que deux éléments, appelés développements triviaux ([DK93]). Par ailleurs il a été montré en [GS01] que pour les bases comprises entre le nombre d’or et la constante de Komornik-Loreti Uqest un ensemble dénombrable, et pour les bases plus grandes que la constante de Komornik-Loreti Uqa un continuum d’éléments.

Dans le cas d’un alphabet général, o ù la distance entre chiffres consécutifs n’est pas nécessairement constante, beaucoup de résultats s’étendent, e.g. en [Ped05] les développements uniques sont ca- ractérisés lexicographiquement.

L’étude des développements avec alphabets arbitraires est reliée à des problèmes de contro- labilité en robotique. En [CP01] les chiffres d’un alphabet arbitraire sont considérés somme les contr ôles d’un système unidimensionnel discret, et l’ensemble des nombres représentables est interprété comme l’ensemble des points atteignables depuis l’origine.

3.2. Bases critiques.

Theorem 3.1 (Existence de bases critiques). Soit A = {a₁, . . . , a_J}. Pour tout ensemble X ⊂ A^Nil existe un nombre

1≤q_X≤Q_A:= (max A−min A)/ max

j=1,...,J−1{a_j+1−a_j} tel que

q>q_X =⇒ toute suite x∈X est univoque en base q;

1<q<q_X =⇒ pas toute suite x∈X est univoque en base q.

De plus :

Corollary 3.1. Il existe un nombre 1<G_A≤Q_Atel que

q>G_A=⇒ il existe des suites univoques non triviales;

1<q<G_A=⇒ il n’existe pas de suites univoques non triviales.

La valeur G_Aest appel´ee base critique de l’alphabet A.

3.3. Alphabets ternaires normaux. Un alphabet ternaire est normal s’il est de la forme{0, 1, m} avec m≥2. Le problème de la caractérisation des bases critiques pour les alphabets ternaires est simplifié par les résultats suivants.

Proposition 3.1. Tout alphabet ternaire A peut être normalisé en utilisant uniquement des translations, des multiplications scalaires et des opérations duales.

Proposition 3.2. Tout alphabet ternaire ainsi que sa forme normale partagent le même nombre d’or généralisé.

3.4. Bases critiques pour alphabets ternaires. La base critique des alphabets de la forme A = {a₁, a₂, a₃}avec

m :=max

½a₃−a₁

a2−a1,a₃−a₁ a3−a2

¾

est la valeur pmd´efinie dans le r´esultat suivant.

Theorem 3.2. Il existe une fonction continue p :[2, ∞) →R, m7→p_msatisfaisant 2≤ p_m≤P_m:=1+

r m

m−1 pour tous les m tels que :

(11)

(a) pour tout m ≥2, il existe des d´eveloppements uniques non triviaux si q > pmet il n’y en a pas si q<pm;

(b) pm=2 si et seulement si m=2^kpour un entier positif k ;

(c) l’ensemble C := {m ≥ 2 : pm = Pm}est un ensemble de Cantor, i.e., un ensemble fermé non dénombrable sans intérieur ni points isolés ; son plus petit éleément est 1+x ≈ 2.3247 o ù x est le plus petit nombre de Pisot, i.e., la racine positive de l’équation x³=x+1 ;

(d) toute composante connexe(m_d, M_d)de[2, ∞) \C a un point µ_dtel que p est strictement d´ecroissant dans[m_d, µ_d]et strictement croissant dans[µ_d, M_d].

3.5. Bases critiques et suites m-admissibles. Pour tout m ≥ 2 fix´e une suite δ = δ₁δ2· · · avec chiffres dans{1, m}est dite m-admissible si elle satisfait :

1δ2δ3· · · ≤δn+1δn+2· · · ≤mδ2δ3· · ·. Si δ est m-admissible, nous consid´erons aussi la suite :

(3) δ⁰ :=min{(δn+i)_i≥1|δn =0; n≥1} Remark 3.1. On peut prouver que δ⁰est toujours un suffixe de δ.

A partir d’une suite m-admissible fixée δ on peut définir p⁰_m,δet p⁰⁰_m,δcomme les solutions positive des équations :

∑

∞ i=1

δ_i

(p⁰_m,δ)ⁱ =m−1

∑

∞ i=1

m−δ_i⁰ (p⁰⁰_m,δ)ⁱ =1.

et p_m,δ := max{p⁰_m,δ, p⁰⁰_m,δ}. Les propriétés suivantes forment le cœur de la preuve du théoreme 3.2.

Proposition 3.3. Fixons m≥2 :

(a) si δ est une suite m-admissible telle que p_m,δ≤Pm, alors p_m,δest égale à la base critique de Am; (b) il existe une unique suite m-admissible δmtelle que p_m,δ_m est égale à la base critique de Am; (c) δmest purement périodique quand p_m,δ_m <1+^q_m−1^m , qui veut dire presque partout ; (d) pour tout q> p_m,δ_m ≡GAmla suite δ⁰_mest univoque en base q.

Remark 3.2. Si δ est une suite m-admissible alors δ2δ3· · · est une suite sturmienne.

3.6. Conclusions et développements futurs. Nous avons tout d’abord considéré des alphabets arbitraires et nous avons prouvé l’existence d’une valeur critique entre la non existence et l’existence de suites univoques. Cette notion étend les propriétés classiques du nombre d’or pour les alphabets binaires. La caractérisation dans le cas des alphabets ternaires montre que la base cri- tique est un nombre algébrique pour presque tout m. Nous pensons que les résultats sur les suites m-admissibles pourront s’étendre aux alphabets avec plus de trois lettres.

4. SUITES UNIVOQUES POUR ALPHABETS TERNAIRES

Nous caractérisons les développements uniques sur des alphabets ternaires, montrant au pas- sage que l’ensemble des développements univoques en base q, noté U_q, est un ensemble dénombrable régulier pour tout q plus petit qu’une valeur explicitement déterminé dépendante de l’alphabet.

(12)

Theorem 4.1. Soit m tel que GAm < 1+^q_m−1^m et soit Uq l’ensemble des d´eveloppements uniques en base q∈ (G_A_m, 1+^q_m−1^m ]. Soit δ_mla suite (p´eriodique) comme dans la proposition3.3(b). Alors

Uq= {m^tx|x∈Orb(δm), x=1x⁰, x⁰ ∈ A^ω_m; t≥0}

∪ {0^tx|x∈Orb(δm), x=1x⁰, x⁰∈ A^ω_m, πq(x) <1; t≥0}. Le résultat s’étend à de nombreux alphabets ternaires.

Corollary 4.1. Soit m tel que G_A_m <1+^q_m−1^m et soit A= {a₁, a2, a3}a tel que m :=max

½a₃−a₁

a₂−a₁,a₃−a₁ a₃−a₂

¾

de sorte que G_A=G_A_m <1+^q_m−1^m . Soit φ_Ala fonction de normalisation chiffre-`a-chiffre :

φ_A(a) =











0 si a=a₁et ^a_a³^−a¹

2−a₁ ≥ ^a_a³^−a¹

3−a₂

or a=a₃et^a_a³^−a¹

2−a₁ < ^a_a³^−a¹

3−a₂

1 si a=a₂

m si a=a₃et ^a_a³₂^−a_−a¹₁ ≥ ^a_a³^−a¹

3−a2

si a=a₁et ^a_a³₂^−a_−a¹₁ < ^a_a³^−a¹

3−a₂

.

Alors pour tout q∈ (G_A_m, 1+^q_m−1^m ], l’ensemble U_A,qdes suites univoques avec chiffres dans A et base q satisfait :

U_A,q= {φ⁻¹_A (m^tx) |x∈Orb(sm), x=1x⁰, x⁰ ∈ A^ω_m; t≥0}

∪ {φ⁻¹_A (0^tx) |x∈Orb(sm), x=1x⁰, x⁰∈ A^ω_m, πq(x) <1; t≥0}.

4.1. Conclusions et développements futurs. Dans ce chapitre nous avons mis l’accent sur les développements univoques minimaux, i.e. les développements univoques qui apparaissent d’abord quand on choisit une base plus grande que la base critique. Notre caractérisation concerne l’en- semble des alphabets ternaires o ù le rapport entre les distances est m, et les suites m-admissibles.

C’est un ensemble d’alphabets très grand, car l’ensemble des rapports pour les suites m-admissibles apériodiques est un ensemble de Cantor. Nous avons montré que, quand la suite m-admissible est périodique, l’ensemble Uqdes suites univoques en base q≤Pmest composé uniquement de suites ultimement est périodiques avec une préprériode constante. Ceci implique que U_qest reconnaissable par automate fini. Le suffixe périodique des suites minimales univoques est alors une suite périodique sturmienne. Une investigation plus poussée de cette relation pourrait se montrer utile pour une généralisation à des alphabets arbitraires.

R ´EFERENCES´

[AT04] S. Akiyama and J. M. Thuswaldner. A survey on topological properties of tiles related to number systems. Geom. Dedicata, 109 :89–105, 2004.

[CP01] Y. Chitour and B. Piccoli. Controllability for discrete control systems with a finite control set. Mathematics of Control Signal and Systems, 14 :173–193, 2001.

[DJW85] V. A. Dimitrov, G. A. Jullien, and Miller W.C. Complexity and fast algorithms for mul- tiexponentiation. 31 :141–147, 1985.

[DK88] Z. Dar ´oczy and I. K´atai. Generalized number systems in the complex plane. Acta Math.

Hungar., 51(3-4) :409–416, 1988.

[DK93] Z. Dar ´oczy and I. K´atai. Univoque sequences. Publ. Math. Debrecen, 42(3-4) :397–407, 1993.

(13)

[DVK09] M. De Vries and V. Komornik. Unique expansions of real numbers. Adv. Math., 221 :390–

427, 2009.

[EHJ91] P. Erd˝os, M. Horv´ath, and I. Jo ´o. On the uniqueness of the expansions 1=∑ q⁻ⁿⁱ. Acta Math. Hungar., 58(3-4) :333–342, 1991.

[EJK90] P. Erd ¨os, I. Jo ´o, and V. Komornik. Characterization of the unique expansions 1 =

∑^∞_i=1q⁻ⁿⁱ and related problems. Bull. Soc. Math. France, 118(3) :377–390, 1990.

[FL09] Ch. Frougny and A. C. Lai. On negative bases. Proceedings of DLT09, Lecture notes in computer science, 5583 :252–263, 2009.

[Fro99] Ch. Frougny. On-line addition in real base. Proceedings of MFCS 1999, Lectures Notes in Computer Science, 1672 :1–11, 1999.

[FS03] Ch. Frougny and A. Surarerks. On-line multiplication in real and complex base. Com- puter Arithmetic, IEEE Symposium on, 0 :212, 2003.

[Gil81] W. J. Gilbert. Geometry of radix representations. In The geometric vein, pages 129–139.

Springer, New York, 1981.

[Gil84] W. J. Gilbert. Arithmetic in complex bases. Math. Mag., 57(2) :77–81, 1984.

[Gil87] W. J. Gilbert. Complex bases and fractal similarity. Ann. Sci. Math. Qu´ebec, 11(1) :65–77, 1987.

[Gru85] V. Grunwald. Intorno all’ aritmetica dei sistemi numerici a base negativa con particolare riguardo al sistema numerico a base negativo-decimale per lo studio delle sue analogie coll’ aritmetica ordinaria (decimale). Giornale di Matematiche di Battaglini, 23(367) :203–

221, 1885.

[GS01] P. Glendinning and N. Sidorov. Unique representations of real numbers in non-integer bases. Math. Res. Lett., 8(4) :535–543, 2001.

[IS09] S. Ito and T. Sadahiro. Beta-expansions with negative bases. Integers, 9(3) :239–259, 2009.

[KK81] I. K´atai and B. Kov´acs. Canonical number systems in imaginary quadratic fields. Acta Math. Acad. Sci. Hungar., 37(1-3) :159–164, 1981.

[KL98] V. Komornik and P. Loreti. Unique developments in non-integer bases. Amer. Math.

Monthly, 105(7) :636–639, 1998.

[KL07] V. Komornik and P. Loreti. Expansions in complex bases. Canad. Math. Bull., 50(3) :399–

408, 2007.

[KLP] V. Komornik, A. C. Lai, and M. Pedicini. Generalized golden ratios of ternary alphabets.

To appear on Journal of European Mathematical Society.

[Knu60] D. E. Knuth. An imaginary number system. Comm. ACM, 3 :245–247, 1960.

[Knu71] D. E. Knuth. The art of computer programming. Vol. 2. Addison-Wesley Publishing Co., Reading, Mass., first edition, 1971. Seminumerical algorithms, Addison-Wesley Series in Computer Science and Information Processing.

[KS75] I. K´atai and J. Szab ´o. Canonical number systems for complex integers. Acta Sci. Math.

(Szeged), 37(3-4) :255–260, 1975.

[Par60] W. Parry. On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar., 11 :401–

416, 1960.

[Ped05] M. Pedicini. Greedy expansions and sets with deleted digits. Theoret. Comput. Sci., 332(1- 3) :313–336, 2005.

[Pen65] W. Penney. A “binary” system for complex numbers. J. ACM, 12(2) :247–248, 1965.

[Pic02] D. Pich´e. Complex bases, number systems and their application to the fractal wavelet image coding. PhD thesis (Univ. Waterloo, Ontario, 0, 2002.

(14)

[R´en57] A. R´enyi. Representations for real numbers and their ergodic properties. Acta Math.

Acad. Sci. Hungar, 8 :477–493, 1957.

[Sid03] N. Sidorov. Almost every number has a continuum of β-expansions. Amer. Math.

Monthly, 110(9) :838–842, 2003.

[Sol00] J. A. Solinas. Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr., 19(2-3) :195–

249, 2000. Towards a quarter-century of public key cryptography.