Sturmiskt ord

Fibonacci -ordet är ett exempel på ett sturmiskt ord. Början av skärsekvensen som visas här illustrerar början av ordet 0100101001.

Inom matematiken är ett sturmiskt ord ( Sturmisk sekvens eller biljardsekvens ), uppkallat efter Jacques Charles François Sturm , en viss sorts oändligt lång sekvens av tecken . En sådan sekvens kan genereras genom att överväga ett spel engelsk biljard på ett fyrkantigt bord. Den slagna bollen kommer successivt att träffa de vertikala och horisontella kanterna märkta 0 och 1 och genererar en sekvens av bokstäver. Denna sekvens är ett sturmiskt ord.

Definition

Sturmian-sekvenser kan definieras strikt i termer av deras kombinatoriska egenskaper eller geometriskt som skärsekvenser för linjer med irrationell lutning eller kodningar för irrationella rotationer . De anses traditionellt vara oändliga sekvenser på alfabetet av de två symbolerna 0 och 1.

Kombinatoriska definitioner

Sekvenser av låg komplexitet

För en oändlig sekvens av symboler w , låt σ ( n ) vara komplexitetsfunktionen för w ; dvs σ ( n ) = antalet distinkta sammanhängande delord (faktorer) i w av längden n . Då w Sturmian om σ ( n ) = n + 1 för alla n .

Balanserade sekvenser

En uppsättning X av binära strängar kallas balanserad om Hamming-vikten för element i X tar högst två distinkta värden. Det vill säga för alla $s\in X$ | s | ₁ = k eller | s | ₁ = k' där | s | ₁ är antalet 1:or i s .

Låt w vara en oändlig följd av 0:or och 1:or och låt ${\mathcal {L}}_{n}(w)$ beteckna mängden av alla längd- n underord av w . Sekvensen w är Sturmian om ${\mathcal {L}}_{n}(w)$ är balanserad för alla n och w till slut inte är periodisk.

Geometriska definitioner

Skär sekvens av irrationell

Låt w vara en oändlig följd av 0:or och 1:or. Sekvensen w är Sturmian om för vissa $x\in [0,1)$ och vissa irrationella $\theta \in (0,\infty )$ , w realiseras som skärsekvensen för linjen $f(t)=\theta t+x$ .

Skillnaden mellan Beatty-sekvenser

Låt w = ( w _n ) vara en oändlig sekvens av 0:or och 1:or. Sekvensen w är Sturmian om den är skillnaden mellan icke-homogena Beatty-sekvenser , det vill säga för vissa $x\in [0,1)$ och några irrationella $\theta \in (0,1)$

w_{n}=\lgolv n\theta +x\rgolv -\lgolv (n-1)\theta +x\ rfloor

för alla $n$ eller

w_{n}=\lceil n\theta +x\rceil -\lceil (n-1)\theta +x\ rceil

för alla $n$ .

Kodning av irrationell rotation

Animation som visar Sturmian-sekvensen genererad av en irrationell rotation med θ ≈ 0,2882 och x ≈ 0,0789

För $\theta \in [0,1)$ , definiera $T_{\theta }:[0,1)\to [0,1)$ av $t\mapsto t+\theta {\bmod {1}}$ . För $x\in [0,1)$ definierar θ -kodningen av x att vara sekvensen ( x _n ) där

x_{n}={\begin{cases}1&{\text{if }}T_{\theta }^{n}(x)\i [0,\theta ),\\0&{\text{ else}}.\end{cases}}

Låt w vara en oändlig följd av 0:or och 1:or. Sekvensen w är Sturmian om för vissa $x\in [0,1)$ och vissa irrationella $\theta \in (0,\infty )$ , w är θ -kodningen av x .

Diskussion

Exempel

Ett känt exempel på ett (standard) Sturmian-ord är Fibonacci-ordet ; dess lutning är $1/\phi$ , där $\phi$ är det gyllene snittet .

Balanserade aperiodiska sekvenser

En uppsättning S av ändliga binära ord balanseras om för varje n delmängden Sn av ord med längden n har egenskapen att Hamming _- vikten för orden i Sn tar högst två distinkta värden _. En balanserad sekvens är en för vilken uppsättningen av faktorer är balanserad. En balanserad sekvens har högst n +1 distinkta faktorer med längden n . En aperiodisk sekvens är en som inte består av en ändlig sekvens följt av en ändlig cykel. En aperiodisk sekvens har minst n + 1 distinkta faktorer med längden n . En sekvens är Sturmisk om och bara om den är balanserad och aperiodisk.

Lutning och avlyssning

En sekvens $(a_{n})_{n\in \mathbb {N} }$ över {0,1} är ett Sturmian-ord om och bara om det finns två reella tal , lutningen $\alpha$ och skärningen $\rho$ , med $\alpha$ irrationell , så att

a_{n}=\lgolv \alpha (n+1)+\rho \rgolv -\lgolv \ alpha n+\rho \rfloor -\lfloor \alpha \rfloor

för alla $n$ . Således ger ett sturmiskt ord en diskretisering av den raka linjen med lutningen $\alpha$ och skärningen ρ . Utan förlust av generalitet kan vi alltid anta ${\displaystyle 0<\alpha <1} ,$ eftersom vi för alla heltal k har

\lfloor (\alpha +k)(n+1)+\rho \rfloor -\lfloor (\alpha +k)n+\rho \rfloor -\lfloor \alpha +k\rfloor =a_{n}.

Alla Sturmiska ord som motsvarar samma lutning $\alpha$ har samma uppsättning faktorer; ordet $c_{\alpha }$ som motsvarar skärningen $\rho =0$ är standardordet eller karakteristiska ordet för lutningen $\alpha$ . Därför, om $0<\alpha <1$ , är det karakteristiska ordet $c_{\alpha }$ den första skillnaden i Beatty-sekvensen som motsvarar det irrationella talet $\ alfa$ .

Standardordet $c_{\alpha }$ är också gränsen för en sekvens av ord $(s_{n})_{n\geq 0}$ definierade rekursivt enligt följande :

Låt $[0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]$ vara den fortsatta fraktionsexpansionen av $\alpha$ , och definiera

$s_{0}=1$
$s_{1}=0$
$s_{n+1}=s_{n}^{d_{n}}s_{n-1}{\text{ för }} n>0$

där produkten mellan ord bara är deras sammanlänkning . Varje ord i sekvensen $(s_{n})_{n>0}$ är ett prefix till nästa, så att själva sekvensen konvergerar till ett oändligt ord, som är $c_{\alpha }$ .

Den oändliga sekvensen av ord $(s_{n})_{n\geq 0}$ som definieras av ovanstående rekursion kallas standardsekvensen för standardordet $c_{\ alfa }$ , och den oändliga sekvensen d = ( d ₁ , d ₂ , d ₃ , ...) av icke-negativa heltal, med d ₁ ≥ 0 och d _n > 0 ( n ≥ 2), kallas dess direktivsekvens .

Ett sturmiskt ord w över {0,1} är karakteristiskt om och endast om både 0 w och 1 w är sturmiskt.

Frekvenser

Om s är ett oändligt ord och w är ett finit ord, låt μ _N ( w ) beteckna antalet förekomster av w som en faktor i prefixet för s med längden N + | w | − 1. Om μ _N ( w ) har en gräns som N →∞, kallar vi detta frekvensen av w , betecknad med μ ( w ).

För ett Sturmian-ord s har varje finit faktor en frekvens. Tre -gap-satsen innebär att faktorerna med fast längd n har högst tre distinkta frekvenser, och om det finns tre värden så är ett summan av de andra två.

Icke-binära ord

För ord över ett alfabet med storleken k större än 2, definierar vi ett Sturmian-ord som ett med komplexitetsfunktionen n + k − 1. De kan beskrivas i termer av skärsekvenser för k -dimensionellt rymd. En alternativ definition är som ord av minimal komplexitet som inte är i slutändan periodiska.

Tillhörande reella tal

Ett reellt tal för vilket siffrorna med avseende på någon fast bas bildar ett sturmiskt ord är ett transcendentalt tal .

Sturmian endomorphisms

En endomorfism av den fria monoiden B ^∗ på ett 2-bokstavs alfabet B är Sturmian om den mappar varje Sturmian ord till ett Sturmian ord och lokalt Sturmian om det mappar något Sturmian ord till ett Sturmian ord. De Sturmiska endomorfismerna bildar en submonoid av monoiden av endomorfismer av B ^∗ .

Definiera endomorfismer φ och ψ av B ^∗ , där B = {0,1}, med φ(0) = 01, φ(1) = 0 och ψ(0) = 10, ψ(1) = 0. Då I , φ och ψ är Sturmian, och Sturmian endomorphisms av B ^∗ är just de endomorphisms i submonoiden av endomorphism monoiden som genereras av { I ,φ,ψ}.

En morfism är Sturmian om och endast om bilden av ordet 10010010100101 är en balanserad sekvens ; det vill säga, för varje n tar Hamming -vikterna för underord med längd n högst två distinkta värden.

Historia

Även om studiet av Sturmian-ord går tillbaka till Johann III Bernoulli (1772), var det Gustav A. Hedlund och Marston Morse 1940 som myntade termen Sturmian för att referera till sådana sekvenser, för att hedra matematikern Jacques Charles François Sturm pga. samband med Sturms jämförelsesats .

Se även

Vidare läsning

Bugeaud, Yann (2012). Distribution modulo ett och Diophantine approximation . Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press . ISBN 978-0-521-11169-0 . Zbl 1260.11001 .
Lothaire, M. (2011). Algebraisk kombinatorik på ord . Encyclopedia of Mathematics och dess tillämpningar. Vol. 90. Med förord av Jean Berstel och Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press . ISBN 978-0-521-18071-9 . Zbl 1221.68183 .