Sturmian word: Difference between revisions

Content added Content deleted

Inline

Revision as of 23:27, 31 January 2024

A Sturmian word is a binary sequence, finite or infinite, that makes up the cutting sequence for a positive real number x, as shown in the picture.

The Sturmian word can be computed thus as an algorithm:

If $x>1$ , then it is the inverse of the Sturmian word for $1/x$ . So we have reduced to the case of $0<x\leq 1$ .
Iterate over $floor(1x),floor(2x),floor(3x),\dots$
If $kx$ is an integer, then the program terminates. Else, if $floor((k-1)x)=floor(kx)$ , then the program outputs 0, else, it outputs 10.

The problem:

Given a positive rational number ${\frac {m}{n}}$ , specified by two positive integers $m,n$ , output its entire Sturmian word.
Given a quadratic real number ${\frac {b{\sqrt {a}}+m}{n}}>0$ , specified by integers $a,b,m,n$ , where $a$ is not a perfect square, output the first $k$ letters of Sturmian words when given a positive number $k$ .

(If the programming language can represent infinite data structures, then that works too.)

Stretch goal: calculate the Sturmian word for other kinds of definable real numbers, such as cubic roots.

The key difficulty is accurately calculating $floor(k{\sqrt {a}})$ for large $k$ . Floating point arithmetic would lose precision. One can either do this simply by directly searching for some integer $a'$ such that $a'^{2}\leq k^{2}a<(a'+1)^{2}$ , or by more trickly methods, such as the continued fraction approach.

First calculate the continued fraction convergents to ${\sqrt {a}}$ . Let ${\frac {m}{n}}$ be a convergent to ${\sqrt {a}}$ , such that $n\geq k$ , then since the convergent sequence is the best rational approximant for denominators up to that point, we know for sure that, if we write out ${\frac {0}{k}},{\frac {1}{k}},\dots$ , the sequence would stride right across the gap $(m/n,2x-m/n)$ . Thus, we can take the largest $l$ such that $l/k\leq m/n$ , and we would know for sure that $l=floor(k{\sqrt {a}})$ .

In summary,

floor(k{\sqrt {a}})=floor(mk/n)

where

m/n

is the first continued fraction approximant to

{\sqrt {a}}

with a denominator

n\geq k

where $m/n$ is the first continued fraction approximant to ${\sqrt {a}}$ with a denominator $n\geq k$

@@ Line 11: / Line 11: @@
 * Given a positive rational number <math>\frac mn</math>, specified by two positive integers <math>m, n</math>, output its entire Sturmian word.
-* Given a quadratic real number <math>\frac{\sqrt{a} + m}{n}</math>, specified by three positive integers <math>a, m, n </math>, where <math>a</math> is not a perfect square, output the first <math>k</math> letters of its Sturmian word when given a positive number <math>k</math>.
+* Given a quadratic real number <math>\frac{b\sqrt{a} + m}{n} > 0</math>, specified by integers <math>a, b, m, n </math>, where <math>a</math> is not a perfect square, output the first <math>k</math> letters of Sturmian words when given a positive number <math>k</math>.
 (If the programming language can represent infinite data structures, then that works too.)
@@ Line 19: / Line 19: @@
 The key difficulty is accurately calculating <math>floor(k\sqrt a) </math> for large <math>k</math>. Floating point arithmetic would lose precision. One can either do this simply by directly searching for some integer <math>a'</math> such that <math>a'^2 \leq k^2a < (a'+1)^2</math>, or by more trickly methods, such as the continued fraction approach.
-First calculate the continued fraction representation of <math>\sqrt a</math>, then obtaining the convergent sequence to <math>\sqrt a</math>. Let <math>\frac mn </math> be a convergent to <math>\sqrt a</math>, such that <math>n \geq k</math>, then since the convergent sequence is the '''best rational approximant''' for denominators up to that point, we know for sure that, if we write out <math>\frac{0}{k}, \frac{1}{k}, \dots</math>, the sequence would stride right across the gap <math>(m/n, 2x - m/n)</math>. Thus, we can take the largest <math>l</math>  such that <math>l/k \leq m/n</math>, and we would know for sure that <math>l = floor(k\sqrt a)</math>.
+First calculate the [[continued fraction convergents]] to <math>\sqrt a</math>. Let <math>\frac mn </math> be a convergent to <math>\sqrt a</math>, such that <math>n \geq k</math>, then since the convergent sequence is the '''best rational approximant''' for denominators up to that point, we know for sure that, if we write out <math>\frac{0}{k}, \frac{1}{k}, \dots</math>, the sequence would stride right across the gap <math>(m/n, 2x - m/n)</math>. Thus, we can take the largest <math>l</math>  such that <math>l/k \leq m/n</math>, and we would know for sure that <math>l = floor(k\sqrt a)</math>.
 In summary,<math display="block">floor(k\sqrt a) = floor(mk/n)</math>where <math>m/n</math> is the first continued fraction approximant to <math>\sqrt a</math> with a denominator <math>n \geq k</math>
+where <math>m/n</math> is the first continued fraction approximant to <math>\sqrt a</math> with a denominator <math>n \geq k</math>