Balanční vlastnosti pevného bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Balanˇcn´ı vlastnosti pevn´eho bodu substituce Karel Bˇrinda

Edita Pelantov´a

Theoretical Informatics Group ˇ FJFI CVUT v Praze

14. prosince 2010

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Sch´ema postupu

Abelovsk´ a komplexita l Balanˇ cn´ı funkce l Diskrepanˇ cn´ı funkce l Funkce Suf (N) l Matice primitivn´ı substituce

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Znaˇcen´ı

Abeceda A = {1, . . . , d} Nekoneˇcn´e slovo u Koneˇcn´e slovo ω Vektor frekvenc´ı µ = (µ(a))a∈A , kde µ(a) = limN→+∞ pro pevn´e body primitivn´ıch substituc´ı existuje

|u0 u1 ···uN−1 |a ; N

Mnoˇzina faktor˚ u slova u L Mnoˇzina faktor˚ u d´elky n slova u Ln

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

´ Uvodn´ ı definice Definice (Balanˇcn´ı funkce) Balanˇcn´ı funkci definujeme jako BN (u) = max

max

a∈A w ,w 0 ∈LN (u)

{||w |a − |w 0 |a |}.

Pokud je Bu (n) omezen´a ˇc´ıslem C , ˇr´ık´ame, ˇze u je C -balancovan´e. ˇ Rekneme, ˇze u je balancovan´e, pokud je 1-balancovan´e. Definice (Abelovsk´a komplexita) Abelovskou komplexitou nekoneˇcn´eho slova u rozum´ıme funkci AC(n) = #{ψ(w )|w ∈ Ln }, kde ψ(w ) = (|w |a )a∈A . Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

´ Uvodn´ ı definice

Definice (Diskrepanˇcn´ı funkce) Diskrepanˇcn´ı funkc´ı (pro pevn´y bod primitivn´ı substituce) mysl´ıme funkci DN (u) = max |u0 · · · uN−1 |a − Nµ(a) . a∈A

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

´ Uvodn´ ı definice Definice (Landauovy symboly) f = O(g ), pokud existuje C > 0 takov´e, ˇze f (x) < C · g (x) ∀x > 0. f = o(g ), pokud lim

x→+∞

f (x) = 0. g (x)

f = Ω(g ), pokud f 6= o(g ), tj. lim sup x→+∞

f (x) > 0. g (x)

f = (O ∩ Ω)(g ), pokud f = O(g ) ∧ f = Ω(g ). Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Vztahy mezi abelovskou komplexitou a balanˇcn´ı funkc´ı

Vˇeta Abelovsk´a komplexita nekoneˇcn´eho slova je omezen´a ⇔ jeho balanˇcn´ı funkce je omezen´a (tedy je C -balancovan´e pro nˇejak´e C ). Vˇeta Pro nekoneˇcn´e slovo u nad bin´ arn´ı abecedou plat´ı: AC(n) = Bn (u) + 1.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Balanˇcn´ı funkce omezen´a ⇔ diskrepanˇcn´ı funkce omezen´a

Vˇeta Necht’ u je nekoneˇcn´e slovo. Potom plat´ı: BN (u) je omezen´a ⇔ DN (u) je omezen´a.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Balanˇcn´ı funkce → diskrepanˇcn´ı funkce

Vˇeta Necht’ u je nekoneˇcn´e slovo, necht’ existuje µ = (µ(a))a∈A a necht’ BN (u) = O(f (N)). Potom plat´ı DN (u) = O(f (N)). Vˇeta plat´ı i pro o m´ısto O.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Balanˇcn´ı funkce L99 diskrepanˇcn´ı funkce

Lemma (Uk´azka nefunkˇcnosti v tomto smˇeru) Necht’ f je re´aln´a rostouc´ı neomezen´a funkce takov´a, ˇze f (N) = o(N). Potom existuje nekoneˇcn´e slovo u nad abecedou A = {0, 1} splˇ nuj´ıc´ı: pro u existuje µ = (µ(a))a∈A ; DN (u) = O(f (N)); ∀N Bu (N) = N.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Balanˇcn´ı funkce L99 diskrepanˇcn´ı funkce

Vˇeta Necht’ u je nekoneˇcn´e line´arnˇe rekurentn´ı slovo. Pokud existuje subline´arn´ı rostouc´ı funkce f takov´a, ˇze DN (u) = O(f (N)), potom plat´ı BN (u) = O(f (N)). Vˇeta plat´ı i pro o m´ısto O.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Definice Necht’ u je nekoneˇcn´e slovo, f je zobrazen´ı A → C a N ∈ N ∪ {+∞}. Potom definujeme X Suf (N) = |u0 · · · uN−1 |a f (a). a∈A

V pˇr´ıpadˇe koneˇcn´eho slova ω definujeme X S f (ω) = |ω|a f (a). a∈A

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Definice Necht’ u je nekoneˇcn´e slovo a existuje µ. Potom pro i ∈ {1, . . . , d − 1} zavedeme vektory fi n´asledovnˇe: ( 1 pro i = j; fi (j) = µ(i) v ostatn´ıch pˇr´ıpadech. µ(i)−1

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Vˇeta N´asleduj´ıc´ı tvrzen´ı jsou ekvivalentn´ı: DN (u) = O(g (n)), resp. o(g (n));
∀f = (f (i))i∈A ∈ Cd (f ⊥µ): Suf (N) = O(g (N)), resp. o(g (N)). V prvn´ım tvrzen´ı z´avis´ı konstanta v O na u, ve druh´em tvrzen´ı na u a na f . Vˇeta N´asleduj´ıc´ı tvrzen´ı jsou ekvivalentn´ı: DN (u) = Ω(g (N));
∃f = (f (i))i∈A ∈ Cd (f ⊥µ): Suf (N) = Ω(g (N)). Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Pˇr´ıprava Horn´ı odhad Doln´ı odhad Kritick´ e pˇr´ıpady

Uspoˇr´ad´an´ı spektra

Vˇeta (Perronova-Frobeniova) Necht’ A je nez´aporn´a ireducibiln´ı matice. Pak jej´ı spektr´aln´ı polomˇer ρ(A) je vlastn´ım ˇc´ıslem matice A s algebraickou n´asobnost´ı 1. Vlastn´ı ˇadn´emu jin´emu vlastn´ımu ˇc´ıslu vektor k ρ(A) lze volit kladn´y. Z´ neodpov´ıd´a nez´aporn´y vlastn´ı vektor. Pokud tento vektor budeme volit tak, ˇze souˇcet jeho sloˇzek bude 1, bude se jednat o vektor frekvenc´ı.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Pˇr´ıprava Horn´ı odhad Doln´ı odhad Kritick´ e pˇr´ıpady

Uspoˇr´ad´an´ı spektra

SMϕ = {θi 2 ≤ i ≤ d 0 } ∪ {θ1 = θ} N´asobnost vlastn´ıho ˇc´ısla θi v minim´aln´ım polynomu Mϕ oznaˇcme αi .   |θi | > |θk | nebo ∀i < k ∈ {2, . . . , d 0 } :  |θi | = |θk | ∧ αi ≥ αk Dalˇs´ı dodateˇcn´a podm´ınka: |θi | = |θk | = 1 ∧ αi = αk ∧ θi nen´ı koˇrenem jednotky ∧ θk je koˇrenem jednotky ⇒ i < k. Jednoznaˇcnˇe urˇcen´e: θ, |θ2 |, α2 .

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Pˇr´ıprava Horn´ı odhad Doln´ı odhad Kritick´ e pˇr´ıpady

Horn´ı odhad

Vˇeta Necht’ u je pevn´ym bodem primitivn´ı substituce. Potom: pokud |θ2 | < 1, pak DN (u) je omezen´a;
pokud |θ2 | > 1, pak DN (u) = O (log N α2 −1 )N log |θ2 |/ log θ ; pokud |θ2 | = 1, pak DN (u) = O (log N α2 ). Konstanty v O z´avis´ı pouze na u.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Pˇr´ıprava Horn´ı odhad Doln´ı odhad Kritick´ e pˇr´ıpady

Doln´ı odhad

Vˇeta Necht’ u je pevn´ym bodem primitivn´ı substituce. Pokud |θ2 | ≥ 1, potom   DN (u) = Ω (log N α2 −1 )N log |θ2 |/ log θ .

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Pˇr´ıprava Horn´ı odhad Doln´ı odhad Kritick´ e pˇr´ıpady

Kritick´e pˇr´ıpady Vˇeta Necht’ u je pevn´ym bodem primitivn´ı substituce. Pokud |θ2 | = 1 a θ2 nen´ı koˇren jednotky, pak DN (u) = (O ∩ Ω) ((log N)α2 ) . Vˇeta Necht’ u je pevn´ym bodem primitivn´ı substituce ϕ. Pokud θ2 nen´ı koˇrenem jednotky, pak: Aϕ,u 6= 0 ⇒ DN (u) = (O ∩ Ω) ((log N)α2 );
Aϕ,u = 0 ⇒ DN (u) = (O ∩ Ω) (log N)α2 −1 .

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Vˇeta (Adamczewski) Necht’ U je pevn´ym bodem primitivn´ı substituce ϕ. Potom plat´ı: 1

pokud |θ2 | < 1, pak BN (u) je omezen´a;

2

pokud |θ2 | > 1, pak BN (u) = (O ∩ Ω)((log N)α2 −1 N logθ |θ2 | );

3

4

pokud |θ2 | = 1 a θ2 nen´ı koˇrenem jednotky, pak BN (u) = (O ∩ Ω)((log N)α2 ); pokud |θ2 | = 1 a θ2 je koˇrenem jednotky, pak BN (u) = (O ∩ Ω)((log N)α2 ), pokud Aϕ,u 6= 0; BN (u) = (O ∩ Ω)((log N)α2 −1 ), pokud Aϕ,u = 0.

Konstanta Aϕ,u z´avis´ı na (ϕ, u).

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

D˚ usledek Necht’ u je pevn´ym bodem primitivn´ı substituce ϕ. Pak m´a u balanˇcn´ı funkci omezenou pr´avˇe tehdy, kdyˇz plat´ı jedno z n´asleduj´ıc´ıch tvrzen´ı: |θ2 | < 1; |θ2 | = 1, α2 = 1, θ2 je koˇrenem jednotky a Aϕ,u = 0.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce

´ Uvod Abelovsk´ a komplexita ↔ balanˇ cn´ı funkce Balanˇ cn´ı funkce ↔ diskrepanˇ cn´ı funkce Diskrepanˇ cn´ı funkce ↔ funkce Suf (N) Funkce Suf (N) ↔ matice primitivn´ı substituce Propojen´ı vztah˚ u

Reference

B Adamczewski. Balances for fixed points of primitive substitutions. THEORETICAL COMPUTER SCIENCE, 307(1):47–75, SEP 26 2003. 3rd Conference on WORDS, PALERMO, ITALY, SEP, 2001. B Adamczewski. Symbolic discrepancy and self-similar dynamics. ANNALES DE L INSTITUT FOURIER, 54(7):2201+, 2004.

Karel Bˇrinda, Edita Pelantov´ a

Balanˇ cn´ı vlastnosti pevn´ eho bodu substituce