คำศัพท์สตูร์เมียน

Q: นิยามเชิงการจัดเรียง

สำหรับลำดับอนันต์ของสัญลักษณ์ w ให้ σ ( n ) เป็น ฟังก์ชันความ ซับซ้อน ของ w กล่าวคือ σ ( n ) = จำนวน คำย่อย (แฟกเตอร์) ที่แตกต่างกันและต่อเนื่องกัน ใน w ที่มีความยาว n แล้ว w จะเป็น Sturmian ถ้า σ ( n ) = n + 1 สำหรับทุก n

ในทางคณิตศาสตร์โดยเฉพาะอย่างยิ่งใน คณิตศาสตร์ เชิงการจัดเรียงบนคำคำสตูร์เมียน ( ลำดับสตูร์เมียนหรือลำดับบิลเลียด^{[ 1 ]} ) เป็น ลำดับตัวอักษรที่ยาวไม่สิ้นสุดชนิดหนึ่งแนวคิดนี้ตั้งชื่อตามฌาคส์ ชาร์ลส์ ฟรองซัวส์ สตูร์ม

ลำดับดังกล่าวสามารถสร้างขึ้นได้โดยพิจารณาเกมบิลเลียดอังกฤษบนโต๊ะสี่เหลี่ยม ลูกบอลที่ถูกตีจะกระทบขอบแนวตั้งและแนวนอนที่ติดป้าย 0 และ 1 ตามลำดับ ทำให้เกิดลำดับตัวอักษร^{[ 2 ]}ลำดับนี้เป็นคำแบบ Sturmian

คำนิยาม

ลำดับสตูร์เมียนสามารถนิยามได้อย่างเคร่งครัดตามคุณสมบัติเชิงการจัดเรียง หรือในเชิงเรขาคณิต เช่นลำดับการตัดสำหรับเส้นตรงที่มีความชันเป็นจำนวนอตรรกยะ หรือรหัสสำหรับการหมุนที่เป็นจำนวนอตรรกยะโดยทั่วไปแล้วถือว่าเป็นลำดับอนันต์บนตัวอักษรของสัญลักษณ์สองตัวคือ 0 และ 1

นิยามเชิงการจัดเรียง

ลำดับที่มีความซับซ้อนต่ำ

สำหรับลำดับอนันต์ของสัญลักษณ์wให้σ ( n ) เป็นฟังก์ชันความ ซับซ้อน ของwกล่าวคือσ ( n ) = จำนวนคำย่อย (แฟกเตอร์) ที่แตกต่างกันและต่อเนื่องกันในwที่มีความยาวnแล้วwจะเป็น Sturmian ถ้าσ ( n ) = n + 1 สำหรับทุกn

ลำดับที่สมดุล

เซตXของสตริงไบนารีเรียกว่าเซตสมดุลถ้าค่าน้ำหนักแฮมมิงของสมาชิกในเซต Xมีค่าที่แตกต่างกันได้ไม่เกินสองค่า นั่นคือ สำหรับทุกๆ $s\in X$ | s | = kหรือ | s | = k'โดยที่ | s | คือจำนวนของเลข 1 ในs

ให้wเป็นลำดับอนันต์ของ 0 และ 1 และให้ ${\mathcal {L}__{n}(w)$ ให้ เป็นเซตของคำย่อยที่มีความยาวn ทั้งหมด ของwลำดับwเป็นลำดับสตูร์เมียน ถ้า ${\mathcal {L}__{n}(w)$ มีความสมดุลสำหรับทุกค่าnและw และ ในที่สุดจะไม่เป็นคาบ

นิยามทางเรขาคณิต

ลำดับการตัดของจำนวนอตรรกยะ

ให้wเป็นลำดับอนันต์ของ 0 และ 1 ลำดับwเรียกว่าลำดับสตูร์เมียน ถ้าสำหรับบางค่า $x\in [0,1)$ และบางอย่างที่ไม่สมเหตุสมผล $\theta \in (0,\infty )$ โดย ที่ wจะถูกรับรู้ว่าเป็นลำดับการตัดของเส้น $f(t)=\theta t+x$ .

ความแตกต่างของลำดับบีตตี

ให้w = ( w ) เป็นลำดับอนันต์ของ 0 และ 1 ลำดับwเรียกว่าลำดับสตูร์เมียน (Sturmian) ถ้ามันเป็นผลต่างของลำดับบีตตี (Beatty) ที่ ไม่เอกพันธุ์ (non-homogeneous) นั่นคือ สำหรับบางค่า $x\in [0,1)$ และบางอย่างที่ไม่สมเหตุสมผล $\theta \in (0,1)$

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

สำหรับทุกคน $n$ หรือ

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

สำหรับทุกคน $n$ .

การเข้ารหัสการหมุนที่ไม่สมเหตุสมผล

ภาพเคลื่อนไหวแสดงลำดับสตูร์เมียนที่สร้างขึ้นโดยการหมุนแบบไม่สมเหตุสมผลด้วยθ ≈ 0.2882 และx ≈ 0.0789

สำหรับ $\theta \in [0,1)$ , กำหนด $T_{\theta }:[0,1)\to [0,1)$ โดย $t\mapsto t+\theta {\bmod {1}}$ . สำหรับ $x\in [0,1)$ กำหนดให้ การเข้ารหัส θของxเป็นลำดับ ( x ) โดยที่

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

ให้wเป็นลำดับอนันต์ของ 0 และ 1 ลำดับwเรียกว่าลำดับสตูร์เมียน ถ้าสำหรับบางค่า $x\in [0,1)$ และบางอย่างที่ไม่สมเหตุสมผล $\theta \in (0,\infty )$ w คือการเข้ารหัสθของx

การอภิปราย

ตัวอย่าง

ตัวอย่างที่มีชื่อเสียงของคำ Sturmian (มาตรฐาน) คือ^คำ Fibonacci [ ^{3 ]}ความชันของมันคือ $1/\phi$ , ที่ไหน $\phi$ คืออัตราส่วนทองคำ

ลำดับอคาบสมดุล

เซตSของคำไบนารีจำกัดจะสมดุลก็ต่อเมื่อสำหรับแต่ละnเซตย่อยS ของคำที่มีความยาวnมีคุณสมบัติที่ว่าน้ำหนักแฮมมิงของคำในS มีค่าที่แตกต่างกันได้ไม่เกินสองค่าลำดับที่สมดุล คือลำดับที่เซตของตัวประกอบสมดุล ลำดับที่สมดุลมี ตัวประกอบที่แตกต่างกันที่มีความยาวnไม่เกินn + 1 ตัว^[⁴^]^:⁴³ ลำดับที่ไม่เป็นคาบคือลำดับที่ไม่ประกอบด้วยลำดับจำกัดตามด้วยวัฏจักรจำกัด ลำดับที่ไม่เป็นคาบมีตัวประกอบที่แตกต่างกันที่มีความยาว n อย่างน้อย n + 1 ตัว[ 4 ] : ⁴³^{ลำดับ}^เป็น^สตู^ร์ เมียนก็ต่อเมื่อเป็นลำดับที่สมดุลและไม่เป็นคาบ^[⁴^]^:⁴³

ความชันและจุดตัด

ลำดับ $(a_{n})_{n\in \mathbb {N} }$ เหนือ {0,1} เป็นคำแบบ Sturmian ก็ต่อเมื่อมีจำนวนจริง สองจำนวน คือความชัน $\alpha$ และการสกัดกั้น $\rho$ , กับ $\alpha$ อตรรกยะเช่นนั้น

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

สำหรับทุกคน $n$ [ ⁵^]^:²⁸⁴^[⁶^]^:¹⁵²ดังนั้นคำศัพท์ของ Sturmian จึงให้^การแบ่งส่วนของเส้นตรงที่มีความชัน $\alpha$ และจุดตัดρโดยไม่เสียความเป็นทั่วไป เราสามารถสมมติได้เสมอว่า $0<\alpha <1$ เนื่องจากสำหรับจำนวนเต็มk ใดๆ เรามี

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

คำศัพท์ของสตูร์เมียนทั้งหมดที่สอดคล้องกับความลาดชันเดียวกัน $\alpha$ มีปัจจัยชุดเดียวกัน คำว่า $c_{\alpha }$ ซึ่งสอดคล้องกับจุดตัด $\rho =0$ เป็นคำมาตรฐานหรือคำลักษณะเฉพาะของความลาดชัน $\alpha$ [ ⁵^]^:^{283ดังนั้น}ถ้า $0<\alpha <1$ คำที่มีลักษณะเฉพาะ $c_{\alpha }$ คือผลต่างแรกของลำดับบีตตีที่สอดคล้องกับจำนวนอตรรกยะ $\alpha$ .

คำมาตรฐาน $c_{\alpha }$ นอกจากนี้ยังเป็นขีดจำกัดของลำดับคำด้วย $(s_{n})_{n\geq 0}$ กำหนดแบบเรียกซ้ำดังนี้:

อนุญาต $[0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]$ เป็นการ ขยาย เศษส่วนต่อเนื่องของ $\alpha$ และกำหนด

$s_{0}=1$
$s_{1}=0$
$s_{n+1}=s_{n}^{d_{n}}s_{n-1}{\text{ for }}n>0$

โดยที่ผลคูณระหว่างคำต่างๆ ก็คือการนำ คำเหล่านั้นมาต่อกัน ทุกคำในลำดับนั้น $(s_{n})_{n>0}$ เป็นคำนำหน้าของคำถัดไป ดังนั้นลำดับนั้นจึงลู่เข้าสู่คำอนันต์ ซึ่งก็คือ $c_{\alpha }$ .

ลำดับคำที่ไม่มีที่สิ้นสุด $(s_{n})_{n\geq 0}$ ลำดับที่กำหนดโดยการเรียกซ้ำข้างต้นเรียกว่าลำดับมาตรฐานสำหรับคำมาตรฐาน $c_{\alpha }$ และลำดับอนันต์d = ( d₁ d₂ d₃ , ...) ของจำนวนเต็มที่ไม่เป็นลบ โดยที่ ≥ 0 และ > 0 n ≥ 2) เรียกว่าลำดับคำสั่ง

คำ Sturmian wบน {0,1} มีลักษณะเฉพาะก็ต่อเมื่อทั้ง 0 wและ 1 wเป็น Sturmian ^{[ 7 ]}

ความถี่

ถ้าsเป็นคำลำดับอนันต์และwเป็นคำจำกัด ให้ μ ( w ) แทนจำนวนครั้งที่w ปรากฏ เป็นปัจจัยในคำนำหน้าของsที่มีความยาวN + | w | − 1 ถ้าμ ( w ) มีลิมิตเมื่อN →∞ เราจะเรียกสิ่งนี้ว่าความถี่ ของwซึ่งแทนด้วยμ ( w ) ^{[ 4 ]}^{: 73}

สำหรับคำ Sturmian sทุกปัจจัยจำกัดจะมีความถี่ทฤษฎีบทสามช่องว่างบ่งชี้ว่าปัจจัยที่มีความยาวคงที่nมีความถี่ที่แตกต่างกันไม่เกินสามค่า และถ้ามีสามค่า ค่าหนึ่งจะเป็นผลรวมของอีกสองค่า^{[ 4 ]}^{: 73}

คำที่ไม่ใช่ไบนารี

สำหรับคำที่มีขนาดตัวอักษรkมากกว่า 2 เรากำหนดคำ Sturmian ให้เป็นคำที่มีฟังก์ชันความซับซ้อนn + k − 1 ^[⁶^]^:⁶ สามารถอธิบายได้ในแง่ของลำดับการตัดสำหรับพื้นที่k มิติ ^[⁶^]^:⁸⁴ คำจำกัดความทางเลือกคือคำที่มีความซับซ้อนน้อยที่สุดภายใต้เงื่อนไขที่ไม่เป็นคาบสุดท้าย^[⁶^]^:⁸⁵

ตัวเลขจริงที่เกี่ยวข้อง

จำนวนจริงที่ตัวเลขตามฐานคงที่บางฐานประกอบกันเป็นคำสตูร์เมียนเรียกว่าจำนวนอดิศัย^{[ 6 ]}^{: 64, 85}

เอนโดมอร์ฟิซึมแบบสตูร์เมียน

เอ็นโดมอร์ฟิซึมของอิสระ monoid B ^∗ บนตัวอักษร B 2 ตัวคือSturmianถ้ามันจับคู่คำ Sturmian ทุกคำกับคำ Sturmian ^{[ 8 ]}^{[ 9 ]}และเฉพาะ Sturmianถ้ามันจับคู่คำ Sturmian บางคำกับคำ Sturmian ^{[ 10 ]} Sturmian endomorphisms เป็น submonoid ของ monoid ของ endomorphisms ของB ^∗^{[ 8 ]}

กำหนดเอนโดมอร์ฟิซึม φ และ ψ ของB ^∗โดยที่B = {0,1} โดย φ(0) = 01, φ(1) = 0 และ ψ(0) = 10, ψ(1) = 0 จากนั้นI , φ และ ψ เป็นแบบ Sturmian ^{[ 11 ]}และเอนโดมอร์ฟิซึมแบบ Sturmian ของB ^∗ก็คือเอนโดมอร์ฟิซึมในซับโมโนอิดของโมโนอิดเอนโดมอร์ฟิซึมที่สร้างขึ้นโดย { I ,φ,ψ} ^{[ 9 ]}^{[ 10 ]}^{[ 7 ]}

มอร์ฟิซึมจะเป็นแบบสตูร์เมียนก็ต่อเมื่อภาพของคำ 10010010100101 เป็นลำดับที่สมดุล กล่าวคือ สำหรับแต่ละnน้ำหนักแฮมมิงของคำย่อยที่มีความยาวnจะมีค่าที่แตกต่างกันไม่เกินสองค่า^{[ 9 ]}^{[ 12 ]}

ประวัติศาสตร์

แม้ว่าการศึกษาคำศัพท์แบบ Sturmian จะย้อนกลับไปถึงJohann III Bernoulli (1772) ^{[ 13 ]}^{[ 5 ]}^{: 295}แต่เป็นGustav A. HedlundและMarston Morseในปี 1940 ที่บัญญัติศัพท์Sturmianเพื่ออ้างถึงลำดับดังกล่าว^{[ 5 ]}^{: 295}^{[ 14 ]}เพื่อเป็นเกียรติแก่นักคณิตศาสตร์Jacques Charles François Sturmเนื่องมาจากความสัมพันธ์กับ ทฤษฎีบท การเปรียบเทียบ Sturm ^{[ 6 ]}^{: 114}

ดูเพิ่มเติม

อ่านเพิ่มเติม

Bugeaud, Yann (2012). การกระจายโมดูลหนึ่งและการประมาณค่าไดโอแฟนไทน์ Cambridge Tracts in Mathematics. เล่มที่ 193. เคมบริดจ์: สำนักพิมพ์มหาวิทยาลัยเคม บริดจ์ ISBN 978-0-521-11169-0. Zbl 1260.11001 .
Lothaire, M. (2011). พีชคณิตเชิงการจัดเรียงบนคำ . สารานุกรมคณิตศาสตร์และการประยุกต์. เล่มที่ 90. พร้อมคำนำโดย Jean Berstel และ Dominique Perrin (พิมพ์ซ้ำจาก ฉบับปกแข็งปี 2002). สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ . ISBN 978-0-521-18071-9. Zbl 1221.68183 .

[ 1 ]

[ 2 ]

คำ

[

5

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

ไม่มีชื่อบทความ