AnnaChiaraLai Onexpansionsinnon-integerbase Estrattodellatesi

(1)

“MODELLI EMETODIMATEMATICI PER LA TECNOLOGIA E LASOCIETA`” XXIICICLO

AND

UNIVERSITE´ PARIS7 - PARISDIDEROT

DOCTORAT D’INFORMATIQUE

Estratto della tesi

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)

INDICE

Introduzione 1

1. Rappresentazioni in base complessa 4

1.1. Introduzione 4

1.2. Caratterizzazione dell’inviluppo convesso dei numeri rappresentabili 4

1.3. Rappresentabilit`a in base complessa 6

1.4. Conclusioni e sviluppi futuri 6

2. Rappresentazioni in base negativa 7

2.1. Introduzione 7

2.2. Sistemi dinamici simbolici e l’ordine alternato 7

2.3. Caratterizzazione dei(−q)-shifts sofici e di tipo finito 8

2.4. Entropia del(−q)-shift 8

2.5. Il caso Pisot 8

2.6. Conversione sequenziale dalla base positiva alla base negativa 8

2.7. Conclusions et d´eveloppements futurs 8

3. Sezione aurea generalizzata per alfabeti ternari 8

3.1. Introduction 8

3.2. Basi critiche 9

3.3. Alfabeti ternari normali 9

3.4. Basi critiche per alfabeti ternari 9

3.5. Base critiche e sequenze m-admissibles 10

4. Sequenze univoche per alfabeti ternari 10

Riferimenti bibliografici 11

INTRODUZIONE

Questa tesi `e dedicata allo studio degli sviluppi in serie nella forma (1)

∞ i=1

∑

x_i qⁱ

dove i coefficienti x_iappartengono ad un insieme finito di reali positivi, l’alfabeto, e dove la base

è un numero reale o complesso. Per assicurare la convergenza di (1), la base q è supposta stretta- mente maggiore di 1 in modulo. Quando un numero x soddisfa x=_∑^∞_i=1 ^x_qⁱ_i per una successione di cifre (x_i)_i≥1 nell’alfabeto A, diciamo che x è rappresentabile in base q con alfabeto A, e chi- amiamo(x_i)_i≥1 = x₁x₂· · · una rappresentazione di x. La nozione di rappresentabilità è uno dei temi principali di questa tesi, e possiamo studiarla partendo da concetti familiari. Per esempio, quandol’alfabeto è{0, 1}e la base è q=2, allora ogni x∈ [0, 1]soddisfa

x=

∑

∞ i=1

x_i 2ⁱ

per una successione(x_i)_i≥1 = x₁x₂· · · che è la classica rappresentazione binaria di x. La stes- sa rappresentazione decimale di x non è altro che la rappresentazione (x_i)_i≥1 con le cifre in {0, 1, . . . , 9}e base 10. Il fatto che ogni numero in[0, 1]ammetta una rappresentazione decimale è

(3)

banale, ma non generale. Se l’alfabeto A è{0, 2}e la base è q=3, allora è ben noto che Λq,A=Λ_3,{0,2} = {

∞ i=1

∑

x_i

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

coincide con l’insieme di Cantor. In particolare Λ_3,{0,2} è un insieme totalmente disconnesso pro- priamente contenuto nell’intervallo unitario. Prendendo come alfabeto{0, 1, 2}invece di{0, 2}, l’insieme[0, 1]è completamente rappresentabile, i.e. Λ_3,{0,1,2}= [0, 1]. Per sottolineare il fatto che la cifra 1 è necessaria per rappresentare l’intervallo unitario, diciamo che l’alfabeto{0, 2}è a cifre mancanti.

Consideriamo ora una generalizzazione del concetto di rappresentabilit`a. Fissiamo un alfabeto A e una base q, reale o complessa, e supponiamo che per x6∈Λq,Aesiste un intero non negativo n tale che x/qⁿ ∈Λ_q,A. Poich´e

x qⁿ =

∑

^∞

i=1

x_i

qⁱ implique x=

n−1 i=0

∑

xn−iqⁱ+

∑

^∞

i=1

xn+i

qⁱ =x₁qⁿ⁻¹+ · · · +xn−1q+xn+^xⁿ⁺¹ q + · · · possiamo rappresentare x tramite un’espressione della forma x₁· · ·xn. x_n+1· · ·, dove il simbolo

. indica il fattore di riscalamento qⁿ. Se supponiamo la base essere 10, questa notazione assume una forma familiare; infatti 1 . 2 denota tradizionalmente il valore 10× (₁₀¹ +₁₀²₂).

Se ogni numero di un insieme Λ ammette una rappresentazione generalizzata in base q con alfabeto A, la coppia(A, q)`e `e un sistema di numerazione posizionale per Λ.

Vediamo qualche esempio. I reali positivi sono raprpesentabili in base intera b>1 con alfabeto {0, 1, . . . , b−1}, e in base non intera q>1 e alfabeto{0, 1, . . . ,bqc}. La scelta di una base negativa porta alla rappresentabilità di R: ogni reale pu ò essere rappresentato in base intera−b, con b>1, e alfabeto{0, 1, . . . , b−1}; ogni reale pu ò essere rappresentato in base non intera−q e alfabeto {0, 1, . . . ,bqc}. Il caso di una base non intera positiva è trattato nell’articolo di Rényi [Rén57], e il caso di una base non intera negativa è stato recentemente introdotto in [IS09]. Gli alfabeti {0, 1, . . . , b−1}e{0, 1, . . . ,bqc}vengono detti canonici. Pedicini [Ped05] ha studiato la rappre- sentabilità in base reale positiva e alfabeti con cifre mancanti, mostrando che({a₁, . . . , a_J}, q)è un sistema di numerazione per i reali positivi se e solamente se q ≤ (a_J−a₁)/ max{a_j+1−a_j}. Il caso di una base complessa è pi ù complicato, e i risultati di rappresentabilità sono stati ottoneuti solamente per alcune classi di basi, ad esempio gli interi di Gauss della forma−n±i con n∈N, le radici√^k

n con n∈Z et k∈N, i numeri complessi quadratici.

Nel caso di una base positiva non intera, l’insieme dei valori rappresentabili Λq,Anon pu ò avere che due strutture topologiche: o è un intervallo, oppure è un insieme totalmente disconnesso.

Chiaramente la coppia (A, q) permette di rappresentare completamente R⁺ se e solamente se ci troviamo nel primo caso. Possiamo quindi dedurre che ogni reale non negativo pu ò essere rappresentato in base q con alfabeto A se e solamente se Λ_q,A è un insieme convesso. Lo studio di Λ_q,Aè anche semplificato dal fatto che il pi ù piccolo e il pi ù grande dei numeri rappresentabili sono noti esplicitamente:

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ⁱ .

Quando consideriamo una base complessa, alcuni aspetti cambiano. La convessit`a di Λ_q,Anon

è una condizione necessaria di rappresentabilità, ad esempio ogni numero complesso è rappresentabile in base−1+i e alfabeto{0, 1}, ma Λ_q,A è la curva del drago, un insieme non convesso.

Inoltre la frontriera di Λ_q,A pu `o avere una struttura frattale, anche quando si ha una completa rappresentabilit`a.

(4)

Il nostro approccio al problema della rappresentabilità in base complessa consiste nello studio dell’inviluppo convesso di Λ_q,Aquando q ha un argomento razionale. Poichè la convessità di Λ_q,A

`e una condizione sufficiente per la rappresentabilit`a totale, tale risultati forniscono una nuova classe di sistemi di numerazione in base complessa.

Fin qui abbiamo parlato di condizioni di rappresentabilità, in altre parole ci siamo interessati al problema di stabilire se un numero reale o complesso pu ò essere rappresentato in una base ed un alfabeto dati. Ma quando la rappresentabilità è garantita, ad esempio prendendo una base non intera±q e l’alfabeto canonico Aq = {0, 1, . . . ,bqc}, emergono molte altre domande. Ad esempio potremmo chiederci come rappresentare questi numeri, quali sono le proprietà combinatoriche e dinamiche di queste rappresentazioni, quante rappresentazioni diverse esistono per uno stesso numero. Qui di seguito richiamiamo qualche risultato classico al fine di contestualizzare i nostri risultati originali.

La dimostrazione che ogni reale non negativo ammette una rappresentazione in base q e alfa- beto Aq è classicamente ottenute tramite un algoritmo greedy. Le sequenze cos`ı ottenumer sono chiamate rappresentazioni greedy o q-expansions, e godono di proprietà interessanti. Per esempio, la q-expansion di x∈ [0, 1] è la maggiore nell’ordine lessicografico tra tutte le rappresentazioni di x. Questo significa che tronchiamo la q-expansion di un numero x, l’errore che commettiamo è minimale. Un altro aspetto importante è la monotonia rispetto al valore numerico: i numeri sono ordinati dall’ordine lessicografico sulle loro q-expansions. Queste proprietà hanno permesso nu- merose ricerche in questo ambito, coinvolgendo diversi campi della matematica e dell’informatica teorica, come la teoria dei numeri, la teoria ergodica, la dinamica simbolica, la teoria degli automi.

In particolare la caratterizzazione delle q-expansions data da Parry [Par60] ha permesso lo studio della chiusura dell’insieme delle q-expansions da un punto di vista dinamico simbolico, i.e. del q-shift.

Il calcolo dell’entropia, la riconoscibilit`a per automi finiti e l’esistenza di automi finiti che permettono di effettuare certe operazioni aritmetiche in base positiva sono stati ampiamente studiati.

Noi otteniamo dei risultati analoghi in base negativa.

Un altro aspetto ampiamente studiato in base positiva non intera è l’esistenza di rappresentazioni diverse per uno stesso numero. Negli anni ’90, Erd˝os, insieme a Horváth, Jo ó e Ko- mornik, ha dedicato una serie di articoli al numero di possibili rappresentazioni di uno stesso numero, in base 1 < q < 2 con alfabeto{0, 1}, con particolare attenzione alle rappresentazioni di 1. Questi risultati, insieme a quello di Dar óczy e Kátai [DK93], hanno permesso di chiarire la struttura dell’insieme delle rappresentazioni uniche in questo caso. In particolare, quando la base è minore della sezione aurea, ogni reale positivo ha almeno due rappresentazioni distinte;

quando la base `e compresa tra la sezione aurea e la costante di Komornik-Loreti esiste un insieme numerabili di valori aventi una rappresentazione unica; quando la base `e maggiore della costante di Komornik-Loreti l’insieme dei valori aventi una rappresentazione unica ha la potenza del continuo.

Noi dimostriamo che se la base è positiva non intera, esiste una sorta di sezione aurea generalizzata per degli alfabeti arbitrari, in altre parole mostriamo che le rappresentazioni non sono mai unichee se e solamente se la base è pi ù piccola di un valore critico. Nel caso di un alfabeto ternario caratterizziamo esplicitamente questa base critica e le rappresentazioni uniche per delle basi sufficientemente piccole.

Il lavoro di ricerca sulle basi complesse `e stato realizzato sotto la supervisione di Paola Loreti.

(5)

La maggior parte dei risultati sulle basi negative sono stati ottenuti in collaborazione con Chris- tiane Frougny e possono essere trovati in [FL09]. I risultati sull’esistenza e la caratterizzazione delle basi critiche per gli alfabeti generali sono un lavoro in collaborazione con Vilmos Komornik e Marco Pedicini [KLP].

1. RAPPRESENTAZIONI IN BASE COMPLESSA

Consideriamo delle rappresentazioni con alfabeti arbitrari e basi della forma pe^2πiⁿ con p >

1 e n ∈ N. Studiamo l’inviluppo convesso dell’insieme dei numeri rappresentabili dandone prima una descrizione geometrica poi una caratterizzazione esplicita dei suoi punti estremali.

Diamo anche una condizione necessaria e sufficiente per la convessit`a dell’insieme dei numeri rappresentabili.

1.1. Introduzione. I primi sistemi di numerazione in base complessa sembrano essere quello in base 2i con alfabeto{0, 1, 2, 3}, e in base−1+i con alfabeto{0, 1}, introdotti rispettivamente da Knuth in [Knu60] e da Penney in [Pen65]. In seguito sono stati dedicati molti altri lavori sulla rappresentabilità in base complessa, e.g. si veda [KS75] per gli interi di Gauss della forma−n±i con n∈N, [KK81] per i campi quadratici, e [DK88] per il caso generale. Loreti e Komornik hanno proseguito il lavoro [DK88] introducendo un algoritmo greedy nel caso di basi complesse con argomento non razionale, [KL07]. Negli anni ’80, una linea di ricerca parallela è stata sviluppata da Gilbert. In [Gil81] Gilbert ha descritto la natura frattale dell’insieme dei numeri rappresentabili, ad esempio l’insieme dei numeri rappresentabile in base−1+i con cifre{0, 1} è risultato essere la curva del drago [Knu71]. La dimensione di Hausdorff di alcuni insieme di numeri rappresentabili è stata calcolata in [Gil84] e una nozione debole di auto-similarità è stata introdotta per lo studio della frontiera di questi insiemi [Gil87]. I sistemi di numerazione in base complessa e la geometria dell’insieme dei numeri rappresentabili sono stati ampiamenti studiati dal punto di vista delle loro relazioni con le le IFS e le tassellazioni del piano complesso. Per una panoramica sulla topologia delle tassellazioni associate alle basi appartenenti a campi quadratici rinviamo a [AT04].

I sistemi di numerazione in base complessa hanno diversi hanno diverse applicazioni. Ad esempio nell’aritmetica dei calcolatori, questi sistemi permettono di effettuare le operazioni aritmetica in una maniera unificata, senza dover trattare separatamente la parte reale e quella im- maginaria — si veda [Knu71], [Gil84] e [FS03]. La reppresentazione in base complessa `e stata anche utilizzata in crittografia per accelerare calcoli come l’esponenziazione modulare [DJW85] e la moltiplicazioni sulle curve ellittiche [Sol00].

1.2. Caratterizzazione dell’inviluppo convesso dei numeri rappresentabili. Studiamo la for- ma dell’inviluppo convesso dei numeri rappresentabili in base qn,p := pe^2πⁿⁱ con alfabeto A.

Adottiamo le seguenti notazioni.

Notazione 1.1. Denotiamo

Λ_n,p,A=:{

∑

^∞

k=1

x_kq^−k_n,p|x_k ∈A}

l’insieme dei numeri rappresentabili in base q_n,p:=pe^2πⁿⁱcon alfabeto A.

Notazione 1.2. Sia(x₀· · ·xn−1)una successione in{0, 1}ⁿ. Definiamo(x₀· · ·xn−1)_q := _∑ⁿ⁻¹_j=0 x_jq^je indroduciamo lo shift circolare σ sulle sequenze finite : σ(x0x1· · ·xn−1):= (x1· · ·xn−1x0). La chiusura di(x₀· · ·x_n−1)rispetto σ `e indicata Orb(x₀· · ·x_n−1):= {σ^j(x₀x₁· · ·x_n−1) |j=0, . . . , n−1}. Infine, sia Orb(x0· · ·xn−1)_q:= {σ^j(x0x1· · ·xn−1)_q |j=0, . . . , n−1}.

(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}

FIGURA 1. L’insieme Λ_n,21/2,{0,1}, con n = 3, . . . , 9 è approssimato dall’insieme delle rappresentazioni di lunghezza 14. La base q_8,21/2 = 1+i è un intero di Gauss che è stato studiato in particolare in [Gil81].

Teorema 1.1. Per ogni n≥ 1, p > 1 e qn,p = pe^2πⁿⁱ, l’inviluppo convesso Hcon(Λ_n,p,A)`e un poligono con le seguenti propriet`a:

(a) i lati sono due a due paralleli a q⁰_n,p, . . . , qⁿ⁻¹_n,p ;

(b) se n `e dispari allora Hcon(Λ_n,p,A)ha 2n punti estremali;

(c) se n `e pari allora Hcon(Λ_n,p,A)ha n punti estremali.

Esempio 1.1. Se n=3 e se p>1 allora per ogni alfabeto A l’inviluppo convesso di Λ_n,p,A`e un esagono.

Se n=4 e se p>1 allora per ogni alfabeto A l’inviluppo convesso di Λ_n,p,A`e un rettangolo.

Teorema 1.2. Sia n ≥1, p >1 e A un alfabeto, e denotiamoE (Λ_n,p,A)l’insieme dei punti estremali di Hcon(Λ_n,p,A). Se n `e dispari allora:

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^j_n,p;

(7)

se n `e pari:

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. Rappresentabilit`a in base complessa. Proviamo la seguente caratterizzazione degli insiemi di rappresentabili convessi.

Teorema 1.3. L’insiemde dei numeri rappresentabili in base qn,pe alfabeto A = {a₁, . . . , a_J}`e convesso se e solo se

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}

FIGURA2. Λ_3,21/3+0.1k,{0,1}, con k = 0, . . . , 5, `e approssimato dall’insieme delle rappresentazioni di lunghezza 14.

Esempio 1.2. Se p< 2^1/ne A= {0, 1}allora Λ_n,p,Aè un 2n-gono quando n è dispari, ed è un n-gono quando n è pari.

Esempio 1.3. Se A= {0, 1, . . . ,bpⁿc}allora Λ_n,p,A`e un insieme convesso.

1.4. Conclusioni e sviluppi futuri. Ricordiamo che l’insieme dei numeri rappresentabili pu `o essere visto come l’attrattore di un IFS lineare F_q,A, che dipende dalla base e dall’alfabeto. La caratterizzazione dell’invilupppo convesso dell’insieme dei numeri rappresentabili fornisce un moetodi operativo per definire un dominio limitato per F_q,A.

Abbiamo dato una condizione sufficiente perch`e la dimensione di Hausdorff dell’insieme dei rappresentabili sia piena, ma il problema generale resta aperto. Le relazioni stabiliti in questo

(8)

capitolo potranno aiutare a trovare una soluzione — almeno per le basi di argomento razionale. La definizione di un algoritmo greedy globale e una caratterizzazione parziale basata su un confronto cifra a cifra potrebbe essere incoraggiata da questi argomenti.

2. RAPPRESENTAZIONI IN BASE NEGATIVA

Ito e Sadahiro hanno recentemente introdotto e caratterizzato le rappresentazioni in base non- intera negativa in [IS09] e hanno mostrato che il(−q)-shift è sofico se e solo se la(−q)-expansion del numero −_q+1^q è definitivamente periodica. Il nostro intento è quello di proseguire il loro lavoro, mostrando che molte proprietà dei sistemi di numerazione in base positiva si estendono al caso negativo, essendo la differenza principale che gli insiemi dei numeri rappresentabili sono diversi.

2.1. Introduzione. Le rappresentazioni in base negativa intera−b, con b ≥ 2, sembrano essere state introdotte da Gr ¨unwald in [Gru85], e riscoperte da diversi autori, si veda il commento stori- co realizzato da Knuth [Knu71]. La scelta di una base negativa−b e dell’alfabeto{0, . . . , b−1}

è interessante, perchè produce una rappresentazione senza segno per tutti i numeri (positivi o negativi). È facile vedere che una sequenza senza 0 iniziali rappresenta un intero positivo se e solo se la sua lunghezza è pari. Osserviamoc che(w.)_−b :=_∑^k_i=0w_k(−b)ⁱper ogni w =w_k· · ·w₀ in{0, . . . , b−1}^∗senza 0 all’inizio. La proprietà classica di monotonia tra l’ordine lessicografico sulle parole e i valori numerici non è pi ù soddisfatta in base negativa, per esempio 3 = (111.)₋₂, 4 = (100.)₋₂e 111 >_lex 100. Ciononostante è possibile ristabilire tale corrispondenza introducendo un altro ordine sulle parole, indicato in seguito da≺e chiamato ordine alternato.

Le rappresentazioni in base negativa appaiono anche in alcuni sistemi di numerazione in base complessa, per esempio la base q=2i soddisfa q²= −4 (si veda [Fro99] per uno studio delle loro propriet`a dal punto di vista della teoria degli automi).

2.2. Sistemi dinamici simbolici e l’ordine alternato.

Definizione 2.1. Siano x=x₁x₂· · ·, y=y₁y₂· · · delle parole infinite o finite della stessa lunghezza su un alfabeto.

Sia x6=y e sia i il pi `u piccolo indice tale che x_i 6=y_i. L’ordine alternato≺soddisfa:

(2) x≺y se solo se (−1)ⁱ(x_i−y_i) <0.

Per ogni parola infinita fissata s, consideriamo il sistema dinamico simbolico S= {w= (w_i)_i∈Z∈ A^Z| ∀n, s¹wnwn+1· · · }. Abbiamo quindi :

Proposizione 2.1. Il sotto-shift S= {w= (w_i)_i∈Z∈ A^Z| ∀n, s¹wnwn+1· · · }`e riconoscibile da un automa infinito numerabile.

Proposizione 2.2. Consideriamo il sistema dinamico simbolico S = {w = (w_i)_i∈Z ∈ A^Z | ∀n, s ¹ w_nw_n+1· · · }. Allora

(a) S `e un sotto-shift sofico se e solo se s `e definitivamente periodico;

(b) S `e un sotto-shift di tipo finito se e solo se s `e puramente periodico.

2.3. Caratterizzazione dei(−q)-shifts sofici e di tipo finito. Il(−q)-shift `e la chiusura dell’in- sieme delle(−q)-expansions di Ito e Sadahiro. Dalla loro caratterizzazione del(−q)-shift, [IS09], possiamo ottenere il seguente risultato.

Teorema 2.1. Il(−q)-shift `e un sistema di tipo finito se e solo se γ−q(−_q+1^q )`e puramente periodico.

(9)

2.4. Entropia del(−q)-shift. L’entropia topologica del(−q)-shift `e uguale all’entropia del q-shift classico.

Teorema 2.2. L’entropia topologica del(−q)-shift `e uguale a log q.

2.5. Il caso Pisot. Alcuni risultati in base di Pisot si estendono al caso negativo.

Teorema 2.3. Se q `e un numero di Pisot, ogni elemento di Q(q) ∩I−qha una(−q)-expansion definitiva- mente periodica.

Teorema 2.4. Se q `e un numero di Pisot, allora la normalizzazione in base−q rispetto ad ogni alfabeto, l’addizione in base−q e la conversione dalla base−q alla base q sono realizzabili da un trasduttore finito.

2.6. Conversione sequenziale dalla base positiva alla base negativa.

Proposizione 2.3. Sia q>2. La conversione di una q-expansion di un numero ad una rappresentazione in base−q dello stesso numero pu`o essere realizzato da un algoritmo on-line.

2.7. Conclusions et d´eveloppements futurs. Questi risultati confermano che le(−q)-expansions sono una generalizzazione naturale delle q-expansions classiche e la cui differenza principale `e sugli ordini — alternato sulle basi negative e lessicografico per quelle positive. Potrebbe essere interessante generalizzare questi ordini al caso di basi complesse.

Riteniamo anche che la proposizione2.3possa essere estesa al caso q ≥ 2 e che sia possibile mostrare che la conversione di una base positiva Pisot alla base negativa sia realizzabile da un automa on-line finito.

3. SEZIONE AUREA GENERALIZZATA PER ALFABETI TERNARI

Siamo ora interessati agli sviluppi in base reale q > 1 con le cifre in un alfabeto arbitrario A = {a₁, . . . , a_J}. Per un alfabeto a due lettere A = {a₁, a₂}la sezione aurea G := (1+√

5)/2 gioca un ruolo speciale: esistono degli sviluppi unici non banali in base q se e solo se q > G. Il nostro intento è quello di terminare dei criteri analoghi per gli alfabeti ternari A= {a₁, a₂, a₃}. 3.1. Introduction. Negli anni cinquanta, Rényi [Rén57] ha introdotto un nuovo sistema di nu- merazione in base non intera q con un alfabeto di cifre intere {0, 1, . . . ,bqc}. In seguito queste rapprsentazioni sono state ampiamente studiate, sia da un punto di vista della teoria della misura che da quello della teoria dei numeri. Una delle proprietà pi ù interessanti di questi sistemi è la ridondanza delle rappresentazioni. Per esempio, Sidorov ha mostrato che se 1 < q < 2 allora quasi ogni numero ha un continuum di rappresentazioni distinte [Sid03]. Altri lavori sono stati dedicati allo studio degli sviluppi unici e alle loro proprietà topologiche, si veda [EJK90], [EHJ91], [DK93],[KL98] et [DVK09].

Poiché l’unicità di uno sviluppo è preservata prendendo una base pi ù grande ([DK93]), esistono delle basi di frontiera che separanno le possibili strutture topologiche dell’insieme degli sviluppi unici, indicato con U_q. Ad esempio, per le basi minori della sezione aurea, l’insieme U_q non contiene che due elementi, chiamati sviluppi banali ([DK93]). In particolare è stato dimostrato in [GS01] che le per le basi comprese tra la sezione aurea e la costante di Komornik-Loreti U_q

`e un insieme numerabile, e per le basi pi `u grandi della costante di Komornik-Loreti Uq ha un continuum di elementi.

Nel caso di un alfabeto generale, dove la distanza tra le cifre consecutive non `e necessaria- mente costante, molti risultati si estendono, e.g. in [Ped05] gli sviluppi unici sono caratterizzati lessicograficamente.

(10)

Lo studio degli sviluppi con alfabeti arbitrari `e legato a dei problemi di controllabilit`a in robot- tica. In [CP01] le cifre di un alfabeto arbitrario sono considerate controlli di un sistema unidimen- sionale discreto, e l’insieme dei numeri rappresentabili come l’insieme dei punti raggiungibili dall’origine.

3.2. Basi critiche.

Teorema 3.1 (Esistenza delle basi critiche). Sia A= {a₁, . . . , a_J}. Per ogni insieme X⊂ A^Nesiste un numero

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

j=1,...,J−1{aj+1−a_j} tale che

q>qX =⇒ ogni successione x∈X `e univoca in base q;

1<q<qX =⇒ non ogni successione x∈X `e univoca in base q.

Inoltre :

Corollario 3.1. Esiste un numero 1<G_A≤Q_Atale che

q>G_A=⇒ esistono delle sequenze univoche non banali;

1<q<GA=⇒ non esistono sequenze univoche non banali.

Il valore G_A `e chiamato base critica dell’alfabeto A.

3.3. Alfabeti ternari normali. Un alfabeto ternario `e normale se `e della forma{0, 1, m}con m≥2.

Il problema della caratterizzazione delle basi critiche per gli alfabeti ternari `e semplificato dai risultati seguneti.

Proposizione 3.1. Ogni alfabeto ternario A pu`o essere normalizzato utilizzando unicamente traslazioni, riscalamenti e l’operazione duale.

Proposizione 3.2. Ogni alfabeto ternario e la sua forma normale hanno la stessa base critica.

3.4. Basi critiche per alfabeti ternari. La base critica di alfabeti della forma A= {a₁, a₂, a₃}con m :=max

½a₃−a₁

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

¾

`e il valore pmdefinito nel risultato seguente.

Teorema 3.2. Esiste una funzione continua p :[2, ∞) →R, m7→ p_mche soddisfa 2≤ pm≤Pm:=1+

r m

m−1 per ogni m, tale che:

(a) per ogni m≥2, esistono degli sviluppi unici non banali se q>pme non ce ne sono se q< pm; (b) pm=2 se e solo se m=2^kper un intero positivo k;

(c) l’insieme C := {m≥2 : pm =Pm}è un insieme di Cantor, i.e., un insieme chiuso non numerabile senza interno nè punti isolati; il cui pi ù piccolo elemento è 1+x ≈2.3247 dove x è il pi ù piccolo numero di Pisot, i.e., la radice positiva dell’equazione x³=x+1;

(d) ogni componente connessa(m_d, M_d)di[2, ∞) \C ha un punto µ_dtale che p `e strettamente decres- cente in[m_d, µ_d]e strettamente crescente in[µ_d, M_d].

(11)

3.5. Base critiche e sequenze m-admissibles. Per ogni m ≥ 2 fissata una sequenza δ= δ₁δ₂· · · con cifre in{1, m}`e detta m-ammissibile se soddisfa:

1δ₂δ₃· · · ≤δ_n+1δ_n+2· · · ≤mδ₂δ₃· · ·. Se δ `e m-ammissibile, consideriamo anche la sequenza:

(3) δ⁰ :=min{(δ_n+i)_i≥1|δ_n =0; n≥1} Remark 3.1. `E possibile dimostrare che δ⁰`e sempre suffisso di δ.

A partire da una sequenza m-ammissibile fissata δ possiamo definire p⁰_m,δe p⁰⁰_m,δcome le soluzione positive delle equazioni:

∑

∞ i=1

δi

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

∑

∞ i=1

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

e p_m,δ := max{p⁰_m,δ, p⁰⁰_m,δ}. Le propriet`a seguenti costituiscono il nucleo della dimostrazione del teorema3.2.

Proposizione 3.3. Fissiamo m≥2 :

(a) se δ è una sequenza m-ammissibile tale che p_m,δ≤Pm, allora p_m,δè uguale alla base critica di Am; (b) esiste un’unica sequenza m-ammissibile δ_mtale che m, δ_mè uguale alla base critica di A_m;

(c) δ_m`e puramente periodica quando p_m,δ_m <1+^q_m−1^m , cio`e quasi ovunque;

(d) per ogni q>p_m,δ_m ≡G_A_mla sequenza δ_m⁰ `e univoca in base q.

Remark 3.2. Se δ `e una sequenza m-ammissibile allora δ₂δ₃· · · `e una sequenza sturmiana.

3.6. Conclusioni e sviluppi futuri. Abbiamo considerato alfabeti arbitrari e dimostrato l’esisten- za di un valore critico tra la non-esistenza e l’esistebza di sequenze univoche. Questa nozione estende proprietà classiche della sezione aurea per gli alfabeti binari. La caratterizzazione nel ca- so di alfabeti ternari mostra che la base critica è un numero algebrico per quasi ogni m. Riteniamo che i risultati sulle sequenze m-ammissibili possano estendersi ad alfabeti con pi ù di tre cifre.

4. SEQUENZE UNIVOCHE PER ALFABETI TERNARI

Caratterizziamo gli sviluppi unici per gli alfabeti ternari, mostrando incidentalmente che l’in- sieme degli sviluppi unici in base base q, indicato con U_q, `e un insieme numerabile regolare per ogni q minore di un valore dipendente dall’alfabeto ed esplicitamente determinato.

Teorema 4.1. Sia m tale che G_A_m < 1+^q_m−1^m e sia Uq l’insieme degli sviluppi unici in base q ∈ (G_A_m, 1+^q_m−1^m ]. Sia δmla sequenza (periodica) come nella proposizione3.3(b). Allora

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}. Il risultato si estende a numerosi alfabeti ternari.

Corollario 4.1. Sia m tale che G_A_m <1+^q_m−1^m e sia A= {a₁, a₂, a₃}a tale che

m :=max

½a3−a₁

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

¾

(12)

in modo che GA=GAm <1+^q_m−1^m . Sia φAla funzione di normalizzazione cifra-a -cifra :

φ_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=a3et ^a_a³₂^−a_−a¹₁ ≥ ^a_a³^−a¹

3−a2

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

3−a₂

.

Allora per ogni q ∈ (G_A_m, 1+^q_m−1^m ], l’insieme U_A,q delle sequenze univoche con cifre in A e base q soddisfa:

U_A,q= {φ⁻¹_A (m^tx) |x∈Orb(s_m), 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. Conclusioni e sviluppi futuri. Dans ce In questo capitolo ci siamo concentrati sugli sviluppi unici minimali, i.e. gli sviluppi unici che compaiono per primi scegliendo una base pi ù grande della base critica. La nostra caratterizzazione riguarda l’insieme degli alfabeti ternari in cui il rap- porto tra i salti è m, e le sequenze m-ammissibili. Questo è un insieme di alfabeti molto grande, in quanto l’insieme dei rapporti per cui le sequenze m-ammissibili sono aperiodiche è un insieme di Cantor. Abbiamo mostrato che quando la sequenza m-ammissibile è periodica, l’insieme Uq

delle sequenze univoche in base q ≤ Pm è composto unicamente da sequenze definitivamente periodiche con un antiperiodo costante. Questo implica che Uq è riconoscibile da un automa finito. Il suffisso periodico delle sequenze univoche minimali è una sequenza sturmiana periodica. Un’investigazione pi ù approfondita di questa relazione potrebbe mostrarsi utile per una generalizzazione agli alfabeti arbitrari.

RIFERIMENTI BIBLIOGRAFICI

[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 multiexponentiation. 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.

[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.

(13)

[FS03] Ch. Frougny and A. Surarerks. On-line multiplication in real and complex base.

Computer 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.

[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.