Sturmisk ord

I matematikk , i kombinatorikk og spesielt i kombinasjon av ord , er et Sturmian-ord (eller en Sturmian-sekvens ) et uendelig ord av en bestemt type som har flere likeverdige definisjoner, av aritmetisk eller kombinatorisk art. Den mest direkte definisjonen er som følger: et uendelig ord er Sturmian hvis det har nøyaktig n + 1 faktorer (i betydningen blokker av påfølgende symboler) med lengde n , for ethvert naturlig tall n . Det mest kjente eksemplet på Sturmian-ord er det uendelige Fibonacci-ordet . På den annen side er ordet Prouhet-Thue-Morse ikke Sturmian.

Adjektivet "Sturmian" ble tilskrevet disse suitene til ære for matematikeren Charles Sturm av Gustav Hedlund og Marston Morse , i deres artikkel fra 1940, med henvisning til Sturm-suitene .

Tilsvarende definisjoner

I kombinatorikk på ord , et uendelig ord er følgende uendelig symboler konstruert fra et alfabet over. Enhver sammenhengende og endelig sammenheng av et slikt ord er en faktor i dette ordet.

Sturmisk ord

En uendelig ord x sies å være Sturmian hvis, for et hvilket som helst naturlig tall n , ordet x har nøyaktig n + 1 forskjellige forhold av lengde n .

Definisjonen innebærer at den må ha to forskjellige faktorer med lengde 1; dette innebærer at alfabetet som brukes er nødvendigvis et alfabet med to bokstaver. Uten tap av generalitet kan vi anta at disse bokstavene er 0 og 1.

Mekanisk ord

Den andre definisjonen er nærmere geometri eller regning. En sekvens på {0,1} er et mekanisk ord hvis og bare hvis det er to reelle tall og , med irrasjonell , slik at for alle : $(a_ {n}) _ {{n \ in \ mathbb {N}}}$ $\ alfa$ $\ rho$ $0 <\ alpha <1$ $ikke$

a_n = \ lfloor \ alpha (n + 1) + \ rho \ rfloor - \ lfloor \ alpha n + \ rho \ rfloor

eller

a_n = \ lceil \ alpha (n + 1) + \ rho \ rceil - \ lceil \ alpha n + \ rho \ rceil

I det første tilfellet blir ordet oppnådd notert og sies å være mekanisk lavere , i det andre tilfellet blir ordet oppnådd notert og sies å være mekanisk høyere . Tallet er skråningen , og tallet er skjæringspunktet . $s _ {\ alpha, \ rho}$ $s '_ {\ alpha, \ rho}$ $\ alfa$ $\ rho$

To mekaniske ord med samme skråning har nøyaktig samme sett med faktorer.

Et Sturmian-ord kan representeres av en diskretisering av en linje. I dette tilfellet er vi interessert i skjæringspunktene for linjen med hele rutenettet. Vi får en serie kutt ( " klippesekvens " på engelsk) som koder for de vertikale og horisontale skjæringspunktene. Forholdet til de mekaniske ordene er skjær . Vi kan også vurdere rutene krysset av linjen. De øvre og nedre konturene av disse rutene danner henholdsvis de øvre og nedre mekaniske ordene.

I stedet for det mekaniske ordet, finner vi også begrepet rotasjonsord , av følgende grunn. Vi definerer rotasjonen , av vinkelen , på enhetssirkelen med $R_ \ alpha$ $\ alfa$

R_ \ alpha (x) = x + \ alpha \ bmod 1

og to semi-åpne mellomrom , . For den nedre mekaniske sekvensen har vi så hvis og hvis . Det samme gjelder den øverste raden, med intervallene , halvåpne på den andre siden. $I_0 = [0,1- \ alpha [$ $I_1 = [1- \ alpha, 1 [$ $a_n = 0$ $R ^ n_ \ alpha (\ rho) \ i I_0$ $a_ {n} = 1$ $R ^ n_ \ alpha (\ rho) \ i I_1$ $I'_0 =] 0,1- \ alpha]$ $I'_1 =] 1- \ alpha, 1]$

Balansert ord

Et sett med ord sies å være balansert hvis antall symboler i og i avviker med maksimalt for to ord og av samme lengde 1. For eksempel er settet med faktorer av lengde 3 av Fibonacci-ordet balansert, siden antallet i et ord i dette settet er enten 1 eller 2. På den annen side er settet ikke balansert, siden den første av ordene har 2 bokstaver , og den siste ingen. Et uendelig ord sies å være balansert hvis alle faktorene er balanserte. $X$ $x$ $y$ $X$ ${\ displaystyle 0}$ $x$ $y$ $\ {001,010,100,101 \}$ ${\ displaystyle 0}$ $\ {00.11 \}$ ${\ displaystyle 0}$

Likhet med definisjoner

Teorem (Morse og Hedlund, 1940) - La et uendelig ord på et binært alfabet. Følgende forhold er ekvivalente: $x$

$x$ er Sturmian;
$x$ er mekanikk i irrasjonell skråning;
$x$ er balansert og ikke til slutt periodisk.

Standardord eller karakteristisk ord

Når går linjen gjennom opprinnelsen. De nedre og øvre mekaniske ordene skiller seg bare i det første symbolet, som er 0 for det første og 1 for det andre. Vi skriver ned resten av ordet, derfor og . $\ rho = 0$ $c_ \ alfa$ $s _ {\ alpha, \ rho} = 0c_ \ alpha$ $s '_ {\ alpha, \ rho} = 1c_ \ alpha$

Ordet sies å være en standard ord eller en skråning karakteristikk . Det karakteristiske ordet består derfor også av forskjellene mellom ordene i Beatty-sekvensen som tilsvarer tallet . $c_ \ alfa$ $\ alfa$ $c_ \ alfa$ $\ alfa$

Dette karakteristiske ordet kan også oppnås på følgende måte: La utvidelsen i fortsatte brøker av , og definer: $[0; d_1 + 1, d_2, \ ldots, d_n, \ ldots]$ $\ alfa$

$s_0 = 1$ ;
$s_1 = 0$ ;
$s_ {n + 1} = s_n ^ {d_n} s_ {n-1}$ for . $n> 0$

(Husk at produktet av to ord er deres sammenkobling). Hvert ord i sekvensen er prefikset til de følgende, slik at selve sekvensen konvergerer til et uendelig ord som er . Selve ordene kalles også standardord . Standardord med minst lengde 2 slutter med 01 eller 10. Et sentralt ord er et standardord uten de to siste bokstavene. $(s_n) _ {n> 0}$ $c_ \ alfa$ $s_n$

Et kjent eksempel på et Sturmian-ord er Fibonacci-ordet ; hellingen er verdt 1 / φ 2 = 1 / (1 + φ), der φ er det gyldne tallet . Den kontinuerlige brøkekspansjonen av skråningen er 1 / (1 + φ) = [0; 2, 1, 1, 1, ...], så d n = 1 for alle n og s n er faktisk endelige Fibonacci-ord.

Egenskaper og karakteriseringer

Mange egenskaper ved det uendelige Fibonacci-ordet strekker seg til Sturmiske ord:

Settet med faktorer i et Sturmisk ord lukkes av et speilbilde .
Et Sturmisk ord er jevnt tilbakevendende .

Noen egenskaper er til og med karakteristiske for sturmiske ord:

Et uendelig ord er Sturmian hvis og bare hvis det har nøyaktig to palindromiske faktorer med ulik lengde, og en palindromisk faktor med jevn lengde, for hvilken som helst lengde.

En annen egenskap gjelder faktorene:

To Sturmian-ord har samme sett med faktorer hvis og bare de har samme skråning.

For å angi følgende karakterisering introduserer vi begrepet returord. Enten et uendelig ord med jevne mellomrom, og enten et prefiks av . Ettersom settet med forekomster av in er et syndetisk sett , har sekvensen til begynnelsen av forekomster av , klassifisert i stigende rekkefølge, avgrenset påfølgende forskjeller. Hver faktor som starter ved en indeksposisjon , og slutter ved posisjonen , er et returord . Det er derfor bare et begrenset antall returord for in . For prefikset 0100 av Fibonacci-ordet, $x$ $u$ $x$ $u$ $x$ $(k_1 = 0, k_2, \ ldots, k_n, \ ldots)$ $u$ $x$ $k_ {n}$ $k_ {n + 1} -1$ $u$ $x$

\ understreket {0} 1001 \ understrek {0} 10 \ understrek {0} 1001 \ understrek {0} 1001 \ understrek {0} 100 \ ldots

vi ser at prefikset 0100 vises i posisjonene 0,5,8, 13, 18, ...; returordene er de to ordene og . Egenskapen til å ha to returord er karakteristisk: $01001$ $010$

Et uendelig ord er Sturmian hvis og bare, for ethvert prefiks av , det er nøyaktig to ord som returnerer til in . $x$ $u$ $x$ $u$ $x$

Den gjentakelse funksjon av en Sturmian ord er den funksjon definert ved: er den minste heltall slik at en hvilken som helst faktor av denne lengde inneholder alle lengde faktorer . Denne funksjonen avhenger bare av hellingen til det Sturmiske ordet. La derfor være den kontinuerlige brøkutvidelsen av skråningen, og la q n være nevnerne for reduksjonene . Så vi har: $x$ $R_x$ $R_x (n)$ $x$ $ikke$ $[0,1 + d_1, d_2, \ ldots, d_n, \ ldots]$

Induksjonsfunksjonen til et Sturmisk ord x tilfredsstiller

R_x (n) = q_ {N + 1} + q_N + n-1

, hvor er slik at

IKKE

q_N \ le n <q_ {N + 1}

Denne formelen ble allerede funnet av Morse og Hedlund i 1940.

Den kritiske eksponenten eller indeksen til et Sturmian-ord er den høyeste kraften i et ord som kan vises som en faktor i det Sturmian-ordet. Mer presist, la oss fikse et uendelig ord x. Vi betegner med ind , og vi kaller indeks de , den øvre grensen av rasjonelle tall slik at det er en faktor av . Her er lengdeordet | som er av formen , hvor er et prefiks av . For eksempel . Vi har da følgende karakterisering: $(w)$ $w$ $r$ $w ^ r$ $x$ $w ^ r$ $r | w$ $ww \ cdots ww '$ $w '$ $w$ $(010) ^ {7/3} = 0100100$

Et jevnt tilbakevendende uendelig ord er Sturmian ord hvis og bare hvis det er en uendelighet av faktorer for eksempel $x$ $w$ $x$

R_x (| w |) = | w | \ text {ind} (w) +1

Historie

Selv om studien av Sturmian-ord går tilbake til Jean Bernoulli (i 1772), ble den første store studien utført av Gustav Hedlund og Marston Morse i 1940 .

Merknader og referanser

( fr ) Denne artikkelen er helt eller delvis hentet fra den engelske Wikipedia- artikkelen med tittelen " Sturmian word " ( se forfatterlisten ) .

Morse og Hedlund 1940 .

Se også

Relaterte artikler

Bibliografi

(no) Marston Morse og Gustav A. Hedlund , “ Symbolsk dynamikk II. Sturmian trajectories ” , Amer. J. Math. , vol. 62,1940, s. 1-42 ( matematiske anmeldelser 0000745 ).
(en) M. Lothaire , Algebraic Combinatorics on Words , Cambridge UK, Cambridge University Press ,2002, 504 s. ( ISBN 978-0-521-81220-7 , leses online ) , kap. 2 ("Sturmian Words"), forhåndsvisning på Google Bøker .
.
Aldo de Luca , “ Sturmian words: structure, combinatorics, and their arithmetics ”, Theoretical Computer Science , vol. 183, n o 1,1997, s. 45–82 ( DOI 10.1016 / S0304-3975 (96) 00310-6 , les online ).