Euclidean Strings

Frank Ruskey, U. Victoria, Victoria, CANADA (visiting U. Newcastle, Newcastle, AUSTRALIA)

John Ellis, U. Victoria, Victoria, CANADA Joe Sawada, U. Victoria, Victoria, CANADA Jamie Simpson, Curtin U., Perth, AUSTRALIA

For every rational number there is a string with very nice properties.

Consider strings of natural numbers. Let p = p_{1}p_{2} ⋯ p_{n}, where k = ∑ p_{i}.

Main Result: The string p is a Euclidean string if and only if one of the following conditions holds.

• The string p is a rotation of (p_{1}+1)p_{2} ⋯ p_{n−1}(p_{n}−1). E.g.

01011 = ShiftLeft^{2}( 11010 ).

• The string p is lexicographically maximum among all Lyndon words of length n whose characters sum to k, with gcd(n, k) = 1. E.g.,

01011 = max{00003, 00012, 00021, 00102, 00201, 00111, 01011}

• The string p is the reversal of the histogram of a rational Beatty sequence. E.g.,

index( 01011 ) = {2, 4, 5} = 5 − {0, 1, 3}, where

{0, 1, 3} = {⌊0/3⌋, ⌊5/3⌋, ⌊10/3⌋} = {⌊5j/3⌋ : j = 0, 1, 2}

• The string is created from 0 by the rules x → x + 1 and x → 01^{x}.

E.g.,

0 → 1 → 01 → 12 → 01011

• The string is created from E_{1,0} = 0 and E_{1,1} = 1 by the rule

E_{n,k} = E_{d,c}E_{n−d,k−c},

where dk = cn + 1 (produces binary strings only). E.g.,

E_{5,3} = E_{2,1}E_{3,2} = (E_{1,0}E_{1,1})(E_{2,1}E_{1,1}) = 01(E_{2,1}1) = 01(011) = 01011 Let p = p_{1}p_{2} ⋯ p_{n}. Define

τ(p) := (p_{1}+1)p_{2} ⋯ p_{n−1}(p_{n}−1)
ρ(p) := p_{n}p_{1} ⋯ p_{n−1}

A string is Euclidean if there is an integer d such that

ρ^{d}(p) = τ(p)

E.g., if p = 01011, then ρ^{2}(p) = 11010 = τ(p). In general,

p_{j} = \{ \begin{matrix}p_{1} + 1 & if j = n − d + 1 \\ p_{n} − 1 & if j = n − d \\ p_{j+d} & otherwise \end{matrix}

Consider

S = p_{1}, p_{1+d}, p_{1+2d}, …, p_{1+(r−1)d}, p_{1+rd} = p_{1}.

Observe that p_{n} must be in S:

S = p_{1}, p_{1+d}, p_{1+2d} …, p_{n−d}, p_{n}, …, p_{n−d+1}, p_{1}.

Thus 1+jd = n for some j, and thus (with some thought) gcd(n, d) = 1. Thus S contains all the elements of p. There are only two values in S, differing by one.

S = \underbrace{p_{1}, p_{1+d}, …, p_{n−d}}_{⌊k/n⌋}, \underbrace{p_{n}, …, p_{n−d+1}}_{⌈k/n⌉}, p_{1}.

The Symmetric Euclidean Algorithm

procedure gcd( n, k : ℕ ) returns ℕ; k < n : return( gcd( n − k, k ) ); k = n : return( n ); k > n : return( gcd( n, k − n ) );

procedure Egcd( n, k : ℕ ) returns String; k < n : return( exp(Egcd(n − k, k) ); { exp(x) = 01^{x} } k = n : return( ‘1’ ); k > n : return( inc(Egcd(n, k − n) ); { inc(x) = x + 1 }

Example: Egcd(5,3) = exp(Egcd(2,3)) = exp(inc(Egcd(2,1))) = exp(inc(exp(Egcd(1,1)))) = exp(inc(exp(1))) = exp(inc(01)) = exp(12) = 01011.

The Stern-Brocot Tree

L = nearest left ancestor = k_{L}/n_{L} R = nearest right ancestor = k_{R}/n_{R}

At the node: \frac{k_{L} + k_{R}}{n_{L} + n_{R}}

To get strings concatenate: LR Initially 0/1 and 1/1 (numbers) or 0 and 1 (strings) From this is follows that E_{n,k} = E_{d,c}E_{n−d,k−c}, where kd = nc + 1.

Lyndon words

A Lyndon word is a string that is (strictly) lexicographically smaller than all of its proper rotations.

Note that

ρ^{i}(p) = p_{n−i+1} ⋯ p_{n−1} \underbrace{p_{n}p_{1}} p_{2} ⋯ p_{n−i}

ρ^{i+d}(p) = ρ^{i}(ρ^{d}(p))
= ρ^{i}(τ(p))
= ρ^{i}(p_{n}p_{2} ⋯ p_{n−1}p_{1})
= p_{n−i+1} ⋯ p_{n−1} \underbrace{p_{1}p_{n}} p_{2} ⋯ p_{n−i−1}

Thus

p ≺ ρ^{d}(p) ≺ ρ^{2d}(p) ≺ ⋯ ≺ ρ^{(n−1)d}(p)

Example:

01011 ≺ 01101 ≺ 10101 ≺ 10110 ≺ 11010

Another related result:

Euclidean strings are lexicographically maximum among all Lyndon words of the same length and weight.