Baum–Söt sekvens

Inom matematik är Baum -Sweet-sekvensen en oändlig automatisk sekvens av 0:or och 1:or som definieras av regeln:

b _n = 1 om den binära representationen av n inte innehåller något block med på varandra följande nollor av udda längd;

bn ₌ 0 annars;

för n ≥ 0.

Till exempel, b ₄ = 1 eftersom den binära representationen av 4 är 100, som bara innehåller ett block med på varandra följande nollor av längden 2; medan b ₅ = 0 eftersom den binära representationen av 5 är 101, som innehåller ett block med på varandra följande nollor av längden 1.

Med början på n = 0 är de första få termerna i Baum–Sweet-sekvensen:

1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1 ... (sekvens A086747 i OEIS )

Historisk motivation

Sekvensens egenskaper studerades först av Leonard E. Baum och Melvin M. Sweet 1976. 1949 antog Khinchin att det inte existerar ett icke-kvadratiskt algebraiskt reellt tal som har avgränsade partiella kvoter i sin fortsatta bråkexpansion. Ett motexempel till denna gissning är fortfarande inte känt. Baum och Sweets papper visade att samma förväntningar inte uppfylls för algebraiska potensserier. De gav ett exempel på kubikpotensserier i $\mathbb {F} _{2}((X^{-1}))$ vars partiella kvoter är avgränsade. (Maktseriens grad i Baum och Sweets resultat är analog med graden av fältförlängning som är associerad med den algebraiska reella i Khinchins gissning.)

En av serierna som tas upp i Baum and Sweets tidning är en rot till

$f^{3}+x^{-1}f+1=0.$

Författarna visar att det enligt Hensels lemma finns en unik sådan rot i $\mathbb {F} _{2}((X^{-1}))$ eftersom man reducerar definiera ekvationen för $f$ modulo $X^{-1}$ ger $f^{3}+1$ , vilket påverkar som

$f^{3}+1=(f+1)(f^{2}+f+1).$

De fortsätter med att bevisa att denna unika rot har partiella kvoter av grad $\leq 2$ . Innan de gör det anger de (i anmärkningen efter sats 2, s 598) att roten kan skrivas i formen

$f=\summa _{k\geq 0}f_{i}X^{-k}$

där $f_{0}=1$ och $f_{k}=1$ för $k\geq 1$ om och endast om den binära expansionen av $n$ innehåller bara jämna längder av $0$ s. Detta är ursprunget till Baum-Sweet-sekvensen.

Mkaouar och Yao bevisade att partialkvoterna för den fortsatta fraktionen för $f$ ovan inte bildar en automatisk sekvens. Sekvensen av partiella kvoter kan emellertid genereras av en olikformig morfism.

Egenskaper

Baum–Sweet-sekvensen kan genereras av en 3- tillståndsautomat .

Värdet av term b _n i Baum–Sweet-sekvensen kan hittas rekursivt enligt följande. Om n = m ·4 ^k , där m inte är delbart med 4 (eller är 0), då

$b_{n}={\begin{cases}1&{\text{if }}n=0\\0&{\text{if }}m{\text{ är jämnt}}\\b_{(m -1)/2}&{\text{om }}m{\text{ är udda}}.\end{case}}$

₀ Således b ₇₆ = b ₉ = b ₄ = b = 1, vilket kan verifieras genom att observera att den binära representationen av 76, som är 1001100, inte innehåller några på varandra följande block med nollor med udda längd.

, som skapas genom att sammanfoga termerna i Baum–Sweet-sekvensen, är en fast punkt i morfismen eller strängersättningsreglerna

00 → 0000

01 → 0100

→ 1001 10

11 → 1101

som följer:

11 → 1101 → 11011001 → 1101100101001001 → 11011001010010011001000001001001 ...

Från morfismreglerna kan man se att Baum–Sweet-ordet innehåller block av på varandra följande nollor av valfri längd ( b _n = 0 för alla 2 ^k heltal i intervallet 5,2 ^k ≤ n < 6,2 ^k ), men det innehåller inget block av tre på varandra följande 1:or.

Mer kortfattat, med Cobhams lilla teorem kan Baum–Sweet-ordet uttryckas som en kodning $\tau$ applicerad på den fixerade punkten av en enhetlig morfism $\varphi$ . Sannerligen, morfismen

$\varphi (A)=AB,\varphi (B)=CB, \varphi (C)=BD,\varphi (D)=DD$

och kodning

$\tau (A)=1,\tau (B)=1,\tau (C)= 0,\tau (D)=0$

skapa ordet på det sättet.

Anteckningar

•    Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatiska sekvenser: teori, tillämpningar, generaliseringar . Cambridge University Press . ISBN 978-0-521-82332-6 . Zbl 1086.11015 .