Euclidean Strings ^{∗}

John Ellis^{†}, Frank Ruskey^{†}, Joe Sawada^{⋆} and Jamie Simpson^{‡}

†Department of Computer Science, University of Victoria

P.O. Box 3055, Victoria, British Columbia, V8W 3P6, Canada

‡Department of Mathematics and Statistics, Curtin University,

Perth, Western Australia, Australia

⋆Department of Computer Science, University of Toronto,

Toronto, Canada

July 4, 2002

Abstract

A string p = p_{0}p_{1} ⋯ p_{n−1} of non-negative integers is a Euclidean string if the string (p_{0} + 1)p_{1} ⋯ (p_{n−1} − 1) is rotationally equivalent (i.e., conjugate) to p. We show that Euclidean strings exist if and only if n and p_{0} + p_{1} + ⋯ + p_{n−1} are relatively prime and that, if they exist, they are unique. We show how to construct them using an algorithm with the same structure as the Euclidean algorithm, hence the name. We show that Euclidean strings are Lyndon words and we describe relationships between Euclidean strings and the Stern-Brocot tree, Fibonacci strings, Beatty sequences, and Sturmian sequences. We also describe an application to a graph embedding problem.

Keywords: Euclidean algorithm, Lyndon word, Stern-Brocot tree, Fibonacci string, Beatty sequence, rational mechanical sequence, Sturmian sequence, Christoffel word, morphism.

∗This work was supported by the Natural Sciences and Engineering Research Council of Canada and by Czech grant GACR 201/99/0242

1 Introduction

The string 010\underline{01}010 has a curious property. The string is not equal to any of its non-trivial rotations, but if we reverse the marked 01 pair, we get the string 010\underline{10}010, which is rotationally equivalent to the original string. In this paper we will investigate this phenomenon in a slightly more general setting.

Our initial interest in strings with this property stems from a certain graph embedding problem which is explained in Section 8 of this paper. Subsequent investigations revealed that these strings had many interesting properties and were related to classic concepts in the subject area of combinatorics on words.

Informally, a Euclidean string is a string of integers with the property that if the first character is increased by one and the last character is decreased by one, then the result is conjugate to the original string. We will show how to generate Euclidean strings by a variant of the Euclidean algorithm, from which they get their name. We prove various characterizations of Euclidean strings, and derive some of their properties. As first pointed out to us by the referees, Euclidean strings are closely related to Sturmian words; in fact, we will eventually show that the binary Euclidean strings are exactly the so-called lower rational mechanical words. The rational mechanical words are also called Christoffel words and characteristic sequences [17], [1], and arise in several different fields. All words studied in this paper are finite. The Sturmian words are infinite but their finite subwords are related to the Euclidean strings.

1.1 Definitions

Let p = p_{0}p_{1} ⋯ p_{n−1} denote a string of n non-negative integers. When the length of p is at least 2, we let ρ(p) denote a right rotation of p by one position, i.e., ρ(p) = p_{n−1}p_{0}p_{1} ⋯ p_{n−2}. Then let ρ^{d}(p) denote a right rotation through d positions and ρ^{−d}(p) denote a left rotation through d positions. Let τ(p) be the string obtained from p by replacing p_{0} by p_{0} + 1 and p_{n−1} by p_{n−1} − 1.

Definition 1 The string p is a Euclidean string if it is of unit length or if there exists an integer d such that τ(p) = ρ^{d}(p).

For example, p = 22322322322323 is a Euclidean string because

τ(p) = 32322322322322 = ρ^{3}(p).

We will refer to the parameter d in the definition as a displacement of the Euclidean string. For consistency we define the displacement of a unit length Euclidean string to be one. Two strings p and q are said to be conjugate if there is an integer d such that p = ρ^{d}(q). So another way of defining a Euclidean string is as a string p which is conjugate to τ(p).

Definition 2 The weight of a Euclidean string is ∑_{i=0}^{n−1} p_{i}, i.e., the sum of all its elements.

Definition 3 The cost of a unit length Euclidean string is p_{0} − 1. Otherwise, the cost, relative to a displacement d, is ∑_{i=0}^{d−1} p_{i}, i.e., the sum of the d elements to the right of and including p_{0}.

Throughout the paper we use k to denote the weight and c to denote the cost of a Euclidean string. We denote a Euclidean string of length n and weight k by E_{n,k}. In arithmetic expressions, mod will denote the remainder after integer division. We adopt the convention that all arithmetic on the string indices is done modulo n, the length of the string, e.g., we write p_{i+j} for p_{(i+j) mod n}.

1.2 Organization

In Section 2 we show that a Euclidean string exists if and only if its length and weight are relatively prime and that, if it exists, it is unique, as are the cost and displacement. Thus there is a natural bijection between the set of Euclidean strings and the set of rational numbers. We show how to efficiently compute Euclidean strings, together with their displacements and costs, using a variant of the Euclidean algorithm.

In Section 3 we show some interesting properties relating the complement, the reversal and the “dual” of a Euclidean string. In Section 4 we show that Euclidean strings are Lyndon words and deduce some related properties. A Lyndon word is one which is lexicographically less than all of its non-trivial conjugates. The relationship between Lyndon words and Sturmian words is explained in [17].

In Section 4 we show a correspondence between the set of all binary Euclidean strings and the Stern-Brocot tree of reduced fractions. The Stern-Brocot tree is an infinite construction of the set of all non-negative fractions k/n between 0 and 1 where k and n are relatively prime. The tree is a rooted binary tree in which each node in the tree is defined in terms of its nearest left ancestor (L), and nearest right ancestor (R). If a node x has L = k′/n′ and R = k′′/n′′ then x = (k′ + k′′)/(n′ + n′′). Similar results are discussed by Berstel and de Luca [3].

In Section 5 we show that every Fibonacci string is conjugate to a Euclidean string. A Fibonacci string is defined by the morphism b ↦ a, a ↦ ab.

In Section 6 we show that Euclidean strings are related to Beatty sequences. A Beatty sequence is a sequence of the form a_{j} = ⌊αj + β⌋ where α > 1 and j ∈ ℤ. We show that a Euclidean string is the reversal of the histogram of a rational Beatty sequence.

In Section 7 we show the relation of Euclidean strings to Sturmian strings; in particular that the Euclidean strings are the (lower) rational mechanical words. For real numbers α and β, the lower mechanical word s_{α,β} has n-th character ⌊(n + 1)α + β⌋ − ⌊nα + β⌋ ([17, Section 2.1.2]). If α is a positive rational number and β = 0, then we refer to these are rational mechanical words. A string s is Sturmian if and only if it is irrational mechanical ([17, Theorem 2.1.13]. The definition of a Sturmian word is not directly related to the content of this paper; the interested reader is referred to Lothaire [17] for many fascinating results. Following [17], we define a word w Proposition 2.2.12 of [17] implies that the rational mechanical words with 0 < α < 1 have the form 0w1, where w is a central word. The set of all central words is denoted PER and studied in [6].

We conclude in Section 8 with the application to a graph embedding problem that was the original motivation for the investigation. Some of the results in this paper were first presented in [9].

2 Characterization and generation

Lemma 1 Any length n Euclidean string p_{0}p_{1} ⋯ p_{n−1} has the following properties:

a) the length and the weight are relatively prime and

b) it is unique, for given length and weight, as are its displacement and cost and

c) for all i in {jd mod n : 0 ≤ j ≤ n − (k mod n) − 1}, p_{i} = ⌊k/n⌋ and for all i in {(n − 1 + jd) mod n : 0 ≤ j ≤ (k mod n) − 1}, p_{i} = ⌈k/n⌉ or, alternatively, p_{i} = |{j : n−1 + jd ≡ i mod n, 0 ≤ j < k}| and

d) dk ≡ 1 mod n.

Proof Let p be a Euclidean string of length n and weight k and with a displacement d so that ρ^{d}(p) = τ(p). We can deduce from the definition of a Euclidean string that

if (0 ≤ j ≤ n − d − 2) or (n − d + 1 ≤ j ≤ n − 1) then p_{j} = p_{j+d}  (1)
p_{n−d−1} = p_{n−1} − 1 and p_{n−d} = p_{0} + 1  (2)

Consider the sequence of string elements

S = p_{0}, p_{d}, p_{2d}, ⋯, p_{jd}

where all the indices are taken modulo n and where j is the smallest positive integer such that jd ≡ 0 mod n. Such a j must exist. It must be that p_{n−d} is the penultimate item in S since it is the predecessor of p_{0}. By (2) p_{n−d} = p_{0} + 1. But, by equations (1) and (2), every element in the sequence is equal to its predecessor in the sequence, unless the element is p_{0} or p_{n−1}. Since the sequence starts and ends with p_{0}, it must then also contain p_{n−1}, because p_{n−d−1} is the only remaining element which can break the sequence of identical elements. So S is a sequence of string elements,

S = p_{0}, p_{d}, p_{2d}, ⋯, p_{n−d−1}, p_{n−1}, ⋯, p_{n−d}, p_{0}.

where every element is identical to its successor except for p_{n−d−1} and p_{n−d}.

It follows that there are only two values in S, differing by one. Let them be x = p_{0} and x + 1 = p_{n−1}. Then S consists of a sequence of x’s followed by a sequence of (x + 1)’s. Let there be r of the x’s. Tt must be that the first (x+1) is p_{n−1} and that n−1 ≡ rd mod n, i.e., rd ≡ −1 mod n, which implies that gcd(r, n) = 1 and that gcd(d, n) = 1. Since gcd(d, n) = 1, it must be that S contains all the elements of p.

Then x = ⌊k/n⌋ and x + 1 = ⌈k/n⌉, rx + (n − r)(x + 1) = k and hence k + r ≡ 0 mod n. We can then derive the items in the lemma as follows.

a) From gcd(r, n) = 1 and k + r ≡ 0 mod n we derive gcd(n, k) = 1.

b) We have that rd ≡ −1 mod n, where r = n − (k mod n). This implies that d has a unique value in the reduced residue set modulo n. Hence the sequence S is unique and the corresponding Euclidean string is unique.

c) Since r, the number of smaller elements, is necessarily n−(k mod n), the first two statements follow. The third statement follows from the observation that, since gcd(d, n) = 1, |{j : n−1 + jd ≡ i mod n, 0 ≤ j < n}| = 1 for all i.

d) From k + r ≡ 0 mod n and rd ≡ −1 mod n we derive dk ≡ 1 mod n.

□

In the following proof we will make use of two string operations, increment and expand. Increment, denoted inc, adds one to every integer in the string. Expand, denoted exp, replaces every integer i in the string by 01^{i}, where 1^{i} denotes a string of i ones. In other words, exp and inc are the morphisms

i ↦ i + 1, and i ↦ 01^{i}.

We have not seen these morphisms used before in the literature of combinatorics on words. However, they will be crucial to proving some of our new results and in deriving simpler proofs of some known results.

Lemma 2 If n and k are relatively prime, positive integers, then there exists a Euclidean string of length n and weight k.

Proof The proof is constructive. The function E-string constructs a Euclidean string, of length n and weight k, when n and k are relatively prime. It mirrors the structure of the symmetric Euclidean algorithm, and is the reason that we call our strings “Euclidean strings.”

function E-string (n, k : ℤ^{+}) : String over ℕ^{∗}; if k < n → return( exp(E-string (n − k, k)) ) [] k = n → return( ‘1’ ); [] k > n → return( inc(E-string (n, k − n)) ) fi

We demonstrate the correctness of the procedure by induction on the number of invocations to the increment and expand procedures. For the base case, where n = k = 1, the procedure returns the string ‘1’, which conforms to Definition 1.

It can not be the case that n = k and n > 1 because n and k are relatively prime. Suppose k > n, in which case the increment operation is applied to the result of invoking the procedure with parameters (n, k − n). Since n and k are relatively prime, so are n and k − n. Hence we may assume that a Euclidean string of length n and weight k − n, say p, is returned. It is clear that since τ(p) = ρ^{d}(p), where d is the displacement of p, then τ(inc(p)) = ρ^{d}(inc(p)). Further, the incrementation increases the weight of the string from k − n to k. Hence inc(p) is a Euclidean string of length n and weight k. The displacement is unchanged by the operation. The cost (recall Definition 3) is increased by d, since the values of the leftmost d elements are each increased by one.

Now suppose n > k, in which case the expand operation is applied to the result of invoking the procedure with parameters (n − k, k). Since n and k are relatively prime, so are n − k and k. Hence we may assume that a Euclidean string of length n − k and weight k, say p, is returned and that τ(p) = ρ^{d}(p) where d is the displacement of p. Now:

exp(p) = 01^{p_{0}}01^{p_{1}} ⋯ 01^{p_{n−k−1}}.

It follows that τ(exp(p)) = ρ^{d+c}(exp(p)), where c is the cost of p, because the leftmost d elements in p are replaced by d + c elements by the expansion. Further, the length of the expanded string is the number of 0’s plus the number of 1’s which is (n − k) + k = n, but the weight of the expanded string remains k. Hence exp(p) is a Euclidean string of length n and weight k. The expansion increases the dispacement by c and the cost is unchanged. □

An example of the computation of a string is given in Figure 1. In that figure the cost and dispacement are also shown. The computation of these parameters is discussed in the next section.

The unwinding of the recursion can be viewed as a walk from the root in an infinite binary tree T . In T each node is labelled by an ordered pair (x, y). The left child of (x, y) is (x, x + y) and the right child is (x + y, y). The root is (1, 1). See Figure 2. Every reduced Figure 1: Computing the Euclidean string E_{14,33}. The symbol I denotes an increment, E denotes an expansion and the caret denotes the exchange point (Lemma 5).

fraction x/y occurs once in this tree and a breadth first traversal of this tree provides a proof that the rational numbers are countable [4]. Figure 3 shows the corresponding tree of strings.

From Lemma 2 and Lemma 1(a), we immediately obtain Theorem 1 below. This theorem implies that the number of Euclidean strings of length n is the Euler totient function ϕ(n).

Theorem 1 There exists a Euclidean string of length n and weight k if and only if gcd(n, k) = 1.

If d is known, then we can use Lemma 1 (c), to generate the Euclidean string in time linear in the length of the string. Below is a procedure which computes the displacement and cost, d and c. Variables c and d are global and the initial call is disp-cost(n, k). The correctness of the procedure follows immediately from the definition of each parameter, i.e., an incrementation requires that the cost be increased by d, whereas an expansion requires that the displacement be increased by c. For consistency we have defined the displacement and cost of a unit length Euclidean string to be 1 and k − 1 respectively. Also note that one of the terminating conditions must be reached.

procedure disp-cost (n, k : ℤ^{+})

if k < n → disp-cost( n − k, k ); d := d + c

[] k = n → c, d := 0,1

Figure 2: The tree of reduced fractions. Figure 3: The corresponding tree of strings.

[] k > n → disp-cost( n, k − n ); c := c + d fi

The following lemma describes a relationship between cost and displacement.

Lemma 3 If n + k ≥ 2 then dk = cn + 1.

Proof Let d_{n,k} and c_{n,k} denote the displacement and cost respectively of a Euclidean string of length n and weight k. We argue by induction on the number of recursive invocations of the procedure. For the basis we note that if n = 1 and k = 1 the initialisation defined by the algorithm satisfies the lemma.

For the induction suppose first that n < k. By the inductive hypothesis: d_{n,k−n}(k − n) = c_{n,k−n}n+1. Hence d_{n,k−n}(k−n)+d_{n,k−n}n = (c_{n,k−n} +d_{n,k−n})n+1. Hence d_{n,k−n}k = (c_{n,k−n} + d_{n,k−n})n + 1. But, when n < k, the algorithm sets d_{n,k} = d_{n,k−n} and c_{n,k} = c_{n,k−n} + d_{n,k−n}. Hence d_{n,k}k = c_{n,k}n + 1.

Suppose k < n. By the inductive hypothesis: d_{n−k,k}k = c_{n−k,k}(n − k) + 1. Hence (d_{n−k,k} + c_{n−k,k})k = c_{n−k,k}n + 1. But, when n < k, the algorithm sets d_{n,k} = d_{n−k,k} + c_{n−k,k} and c_{n,k} = c_{n−k,k}. Hence d_{n,k}k = c_{n,k}n + 1. □

So d and −c are in fact the constants computed by the standard extended Euclidean algorithm, see for example [5, page 811]. We have already shown, in Lemma 1 (d), that dk ≡ 1 mod n, i.e., d is the multiplicative inverse of k modulo n. Lemma 3 immediately yields an analogous corollary, which is crucial to the application described in the final section of this paper and taken from [8].

Corollary 1 The number c is the multiplicative inverse of (k − n) modulo k, i.e., c(k − n) ≡ 1 mod k.

3 Some properties of Euclidean strings

Let R(p) denote the reversal (or mirror image) of p, i.e., R(p) = p_{n−1}p_{n−2} ⋯ p_{1}p_{0}.

Lemma 4 If p is a Euclidean string of length at least 2 and with displacement d, then p = R(τ(p)) = R(ρ^{d}(p)) and τ(p) = R(p).

Proof We proceed by induction on the number of applications of the expand and increment operations in the construction of p. The statement is true for strings of length 2 and for strings of the form 01^{k}. All strings are derived from some string in one of these forms, see Figure 3.

For the induction, suppose p = R(τ(p)). The application of the increment operation obviously preserves the truth of the statement. Let exp(p) denote the expansion of p. We have asumed that p_{0}p_{1} ⋯ p_{n−2}p_{n−1} = (p_{n−1} − 1)p_{n−2} ⋯ p_{1}(p_{0} + 1).

But exp(p) = 01^{p_{0}}01^{p_{1}} ⋯ 01^{p_{n−2}}01^{p_{n−1}}.
Hence τ(exp(p)) = 11^{p_{0}}01^{p_{1}} ⋯ 01^{p_{n−2}}01^{p_{n−1}−1}0.
Hence R(τ(exp(p))) = 01^{p_{n−1}−1}01^{p_{n−2}} ⋯ 01^{p_{1}}01^{p_{0}+1}
= 01^{p_{0}}01^{p_{1}} ⋯ 01^{p_{n−2}}01^{p_{n−1}}

the last equation being obtained from the first. □

Lemma 4 implies that w = p_{1}p_{2} ⋯ p_{n−2} is a palindrome. Since we eventually show that Euclidean strings are rational mechanical, that w is a palindrome is also implied by the fact that the central words are palidromes ([17, Corollary 2.2.9]). It also implies that in any Euclidean string of length at least 3 there is another adjacent pair of elements, besides those on the ends, whose exchange results in a string rotationally equivalent to the original. This is the “curious property” noted in the first paragraph of this paper. We make this explicit in the following lemma. Let swap(p) be the string obtained from p by exchanging elements p_{n−d−1} and p_{n−d}.

Lemma 5 If p is a Euclidean string with displacement d, then swap(p) = ρ^{−d}(p).

Proof From the proof of Lemma 1 we know that p_{n−d−1} + 1 = p_{n−d}. Hence the exchange of those two elements is equivalent to a sequence of rotations, reversals and a τ operation as expressed in the following equation:

swap(p) = ρ^{−d}(R(τ(R(ρ^{d}(p)))).

Thus, by Lemma 4,

swap(p) = ρ^{−d}(R(τ(p))).

By Lemma 4, τ(p) = R(p), and thus

swap(p) = ρ^{−d}(R(R(p))) = ρ^{−d}(p).
□

In the example illustrated in Figure 1, the second exchangable pair is indicated by the caret symbol.

If p is a binary string then the complement of p, denoted C(p), is the string obtained from the morphism that sends 0 to 1, and 1 to 0. The following lemma is implicit in [3, Cor. 3.1].

Lemma 6 If n and k are relatively prime and n > k, then C(R(E_{n,k})) = E_{n,n−k}.

Proof Let p be E_{n,k}, where n > k. The weight of C(p) is n−k. By Lemma 4 R(p) = τ(p) = ρ^{d}(p). We note that

τ(C(R(p))) = τ(C(τ(p))) = C(p),

and that

ρ^{−d}(C(R(p))) = ρ^{−d}(C(ρ^{d}(p))) = C(p).

Hence τ(C(R(p))) = ρ^{−d}(C(R(p))); i.e., C(R(p)) = E_{n,n−k}. □

Definition 4 The morphism δ(p) is defined for all strings of positive integers p. It is obtained by replacing every integer i in the string by the string 0^{i−1}1.

The following theorem shows a relationship between E_{n,k} and its “dual” E_{k,n}.

Theorem 2 If n and k are relatively prime and n < k, then δ(R(E_{n,k})) = E_{k,n}.

Proof We observe that for any string p of positive integers

δ(p) = ρ^{−1}(C(exp(inc^{−1}(p))))
Hence, δ(R(p)) = ρ^{−1}(C(exp(inc^{−1}(R(p)))))
= ρ^{−1}(C(exp(R(inc^{−1}(p)))))
= ρ^{−1}(C(ρ(R(exp(R(inc^{−1}(p)))))) since exp(R(p)) = ρ(R(exp(p)))
= C(R(exp(inc^{−1}(p)))).

Now, suppose p = E_{n,k} where n < k implying that E_{n.k} is a string of positive integers. From the discussion in Section 2, we have that inc(E_{n,k−n}) = E(n, k) and exp(E_{n,k−n}) = E_{k,k−n}. Hence exp(inc^{−1}(E_{n,k})) = E_{k,k−n}. From Lemma 6 C(R(E_{k,k−n})) = E_{k,n}. Hence δ(R(E_{n,k})) = E_{k,n}. □

A Lyndon word is one which is lexicographically less than all of its non-trivial rotations (conjugates). We use the symbols ≺ and ≻ to denote “is lexicographically less than” and “greater than” respectively.

We say that a length n string p is rotationally monotone if there exists an integer e such that

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

For example 01011 is rotationally monotone with e = 2, since 01011 ≺ 01101 ≺ 10101 ≺ 10110 ≺ 11010.

Lemma 7 Every Euclidean string is rotationally monotone.

Proof Let p be a Euclidean string of length n and displacement d. Note that

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

If i ≠ 0, then

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

Since p_{0} ≺ p_{n−1} we have ρ^{i+d}(p) ≺ ρ^{i}(p). Thus

ρ^{d}(p) ≻ ρ^{2d}(p) ≻ ⋯ ≻ ρ^{(n−1)d}(p) ≻ ρ^{nd}(p) = p,

and so p is rotationally monotone with e = −d. □

A partial converse of Lemma 7 is also true: every binary string that is rotationally monotone is a Euclidean string. This can by proven by the same sort of reasoning used in the proof of Lemma 1.

It follows from Lemma 7 that every Euclidean string is a Lyndon word. This result was proven earlier in [3, Theorem 3.2] by a different technique.

Corollary 2 Every Euclidean string is a Lyndon word.

Definition 5 The content of a string is the multiset of characters that occur in the string. In other words, for the string p = p_{1}p_{2} ⋯ p_{n}, the content of p, denoted content(p), is the multiset {p_{1}, …, p_{n}}.

The following lemma is an immediate consequences of the definitions of the increment and expand functions, denoted inc and exp, respectively.

Lemma 8 If p and q are strings, where p ≺ q, then exp(p) ≺ exp(q) and inc(p) ≺ inc(q).

Lemma 9 Among all numeric Lyndon words with the same length n and weight k, where n > 1 and gcd(n, k) = 1, the lexicographically largest has exactly two symbol types, ⌊k/n⌋ and ⌈k/n⌉.

Proof Every Lyndon word with n > 1 has at least two symbols, and must start with the smallest symbol in its content. Since gcd(n, k) = 1, the values ⌊k/n⌋ and ⌈k/n⌉ are distinct. The string ⌊k/n⌋^{s}⌈k/n⌉^{t}, with s+t = n and t = k mod n, is a Lyndon word, because it is smaller than any of its non-trivial conjugates. Clearly, no length n Lyndon word with weight k could have a first symbol larger than ⌊k/n⌋. □

Lemma 10 If q is a binary Lyndon word different from 1, then exp^{−1} is well-defined and exp^{−1}(q) is a Lyndon word.

Proof It is well-defined since a binary Lyndon word starts with a 0 and ends with a 1 (except for the single character strings 1 and 0; the string 1 was excluded, and 0 is a fixed-point of exp^{−1}).

Now suppose that exp^{−1}(q) = uv, where vu ≺ uv. By Lemma 8, we have exp(vu) ≺ q. But this is a contradiction since exp(vu) = exp(v)exp(u) is a rotation of q. □

Theorem 3 If p is a Euclidean string and q is a different Lyndon word with the same length and weight, then q ≺ p.

Proof We argue by induction on the sum of the length and weight of the string. The theorem is obviously true for strings of length one or two. By the Lemma 9 we may assume that content(p) = content(q), and that that content consists of two consecutive non-negative integers.

If p and q are not binary, then inductively inc^{−1}(q) ≺ inc^{−1}(p), from which Lemma 8 gives q ≺ p.

If p and q are both binary strings, then by Lemma 10 exp^{−1}(q) exists and is a Lyndon word. If content(exp^{−1}(q)) ≠ content(exp^{−1}(p)), then by Lemma 9 exp^{−1}(q) ≺ exp^{−1}(p). If content(exp^{−1}(q)) = content(exp^{−1}(p)), then inductively, exp^{−1}(q) ≺ exp^{−1}(p). Thus, in either case, by Lemma 8, q ≺ p. □

Lyndon words are counted by length and “weight” in [13]. For example, the number of q-ary Lyndon words of length n and weight equal to t mod q is

L_{q}(n, t) = \frac{1}{qn} ∑_{{d|n \atop gcd(d,q)|t}} gcd(d, q)μ(d)q^{n/d}.

4 Stern-Brocot strings

In this section we demonstrate an interesting correspondence between the Stern-Brocot tree of reduced fractions and the set of all binary Euclidean strings.

Figure 4: The Stern-Brocot tree of reduced fractions

The Stern-Brocot tree [16] is an infinite construction of the set of all non-negative fractions k/n between 0 and 1 where k and n are relatively prime. The tree is a rooted binary tree in which each node in the tree is constructed by using its nearest left ancestor (L), and nearest right ancestor (R). A nearest left ancestor to a node u is the ancestor v such that the length of the path v to u is minimum and contains exactly one right child. A nearest right ancestor

Figure 5: The Stern-Brocot tree of Euclidean strings.

to a node u is the ancestor v such that the length of the path v to u is minimum and contains exactly one left child. If a node x has L = k′/n′ and R = k′′/n′′ then x = (k′ + k′′)/(n′ + n′′). To start this recursive construction, L is initialized to 0/1 and R is initialized to 1/1. The Stern-Brocot tree is illustrated in Figure 4. Traversing the tree “in-order” produces a Farey series [12].

We now construct an equivalent tree composed of binary strings where each fraction k/n in the Stern-Brocot corresponds to a length n binary string with k ones. In this new tree, each string α is the concatenation of its nearest left ancestor L and its nearest right ancestor R. If L and R are initially assigned the characters 0 and 1 respectively, then we obtain the corresponding Stern-Brocot fraction by computing the number of ones in the string along with the length. This tree of strings, denoted S, is illustrated in Figure 5. Interestingly, this tree includes all and only the binary Euclidean strings.

Theorem 4 The length n binary string α is Euclidean if and only if α is in S. Furthermore, if n > 1 where α = LR, then τ(LR) = ρ^{|L|}(LR).

Proof We proceed by induction on the length of the string. Suppose the length n binary string α is in S. In the base cases, strings 0, 1 and 01 are Euclidean and τ(01) = 10 = ρ(01).

Now consider two cases depending on whether α is a left-child or a right-child.

If α is a left-child then by construction R = LR′ where R′ is the nearest right ancestor of R. By induction τ(LR′) = ρ^{|L|}(LR′) which implies that τ(LLR′) = ρ^{|L|}(LLR′). Thus by definition α is Euclidean and τ(LR) = ρ^{|L|}(LR).

If α is a right-child then by construction L = L′R where L′ is the nearest left ancestor of L. By induction τ(L′R) = ρ^{|L′|}(L′R) which implies that τ(L′RR) = ρ^{|L|}(L′RR). Thus by definition α is Euclidean and τ(LR) = ρ^{|L|}(LR).

Thus every string in S is Euclidean. Since this tree corresponds to the Stern-Brocot tree, there exists a length n string in S with k ones whenever k and n are relatively prime. By Theorem 1, this implies that if α is a binary Euclidean string, then it is in S. □

Theorem 4 implies that every Euclidean string of length greater than or equal to two is the concatenation of two shorter Euclidean strings. We note that this result is similar to Exercise 2.2.3 of [17].

Corollary 3 Every binary Euclidean string E_{n,k} where n ≥ 2 and with displacement d and cost c is the concatenation of the Euclidean strings E_{d,c} and E_{n−d,k−c}.

Proof By Theorem 4, the displacement of the binary Euclidean string α is |L| where α is the concatenation of L and R. Since L is binary, the cost of α is the weight of L. □

The tree of binary Euclidean strings, Figure 5, suggests yet another way of generating any such string, i.e., by way of a sequence of string concatenations, defined by a path down the tree to the node corresponding to the fraction k/n. Corollary 3 implies that the diplacement and cost can be computed simultaneously.

The algorithm uses global variables for current left ancestor L = E_{n_{1},k_{1}}, for the current right ancestor R = E_{n_{2},k_{2}} and for n and k. The variable L should be initialized to “0” and R to “1”. The initial call to generate E_{n,k} is Stern-Brocot(0,0,0,1).

procedure Stern-Brocot ( n_{1}, k_{1}, n_{2}, k_{2}: ℤ^{+} ); local n_{3}, k_{3} : ℤ^{+};

n_{3} := n_{1} + n_{2}; k_{3} := k_{1} + k_{2};

if k_{3}/n_{3} < k/n → R := LR; Stern-Brocot(n_{1}, k_{1}, n_{3}, k_{3}); [] k_{3}/n_{3} = k/n → print(LR, n_{1}, k_{1}); [] k_{3}/n_{3} > k/n → L := LR; Stern-Brocot(n_{3}, k_{3}, n_{2}, k_{2}); fi

There are exactly n − 1 concatenations. Hence, if the strings are represented by linked lists, the time complexity of the algorithm is linear.

All the ancestors of E_{n,k} can be generated by removing the k_{3}/n_{3} = k/n clause and placing the print statement after the update to n_{3} and k_{3}. By Lemma 1 c), the Euclidean string E_{n,k}, where n < k, can be obtained from the binary string E_{n,k mod n} by replacing the zeros by ⌊k/n⌋ and the ones by ⌈k/n⌉. The displacement is unchanged, and if the cost of E_{n,k mod n} is c then the cost of E_{n,k} is d⌊k/n⌋ + c.

5 Fibonacci strings

We go on to show a relationship between Fibonacci and Euclidean strings.

Definition 6 A Fibonacci string is defined by the morphism b ↦ a, a ↦ ab.

For example, the first seven Fibonacci strings are:

b, a, ab, aba, abaab, abaababa, abaababaabaab.

Let F_{i} denote i-th Fibonnacci string with length f_{i}. It is known that, F_{i} = F_{i−1}F_{i−2} and hence that f_{i} is the i-th Fibonacci number. Fibonacci strings occur as the worst case inputs to certain algorithms and they possess many interesting properties [7], [14], [15], [19], [11].

Let G = G_{1}, G_{2}, G_{3}, ⋯ be an infinite sequence of Euclidean strings where each G_{i} is defined as follows:

G_{i} = \{ \begin{matrix}1 & if i = 1, \\ 0 & if i = 2, \\ right(G_{i−1}) & if i > 2 and i odd, \\ left(G_{i−1}) & if i > 2 and i even, \end{matrix}

where right(α) is the right-child of α in the Stern-Brocot tree of strings S and left(α) is the left-child of α in the tree S. This construction implies that G_{i} = G_{i−2}G_{i−1} when i > 2 and i is even; if i > 2 and i odd, then G_{i} = G_{i−1}G_{i−2}.

Lemma 11 Every Fibonacci string is conjugate to a Euclidean string. If a=0 and b=1, then

F_{i} = \{ \begin{matrix}G_{i} & if i ≤ 2, \\ ρ^{−(f_{i−2}+1)}(G_{i}) & if i > 2 and i odd, \\ ρ^{−1}(G_{i}) & if i > 2 and i even. \end{matrix}

Proof This result is easy to verify for i < 5. For i ≥ 5,

F_{i} = F_{i−1}F_{i−2}
= F_{i−2}F_{i−3}F_{i−2}
= F_{i−3}F_{i−4}F_{i−3}F_{i−3}F_{i−4}.

We now consider two cases depending on the parity of i.

If i odd then since i − 3 is even, F_{i−3} = xa for some string x. If we let F_{i−4} = y then we have:

F_{i} = xayxaxay.

Now, by induction F_{i−1} = xayxa = ρ^{−1}(G_{i−1}), which implies that G_{i−1} = axayx. Similarly, F_{i−2} = xay = ρ^{−(f_{i−4}+1)}(G_{i−2}), which implies that G_{i−2} = ayx. Since i is odd, G_{i} = G_{i−1}G_{i−2} = axayxayx and ρ^{−(f_{i−2}+1)}(G_{i}) = xayxaxay = F_{i}.

If i is even then since i − 4 is even, F_{i−4} = xa for some string x. If we let F_{i−3} = y then we have:

F_{i} = yxayyxa.

Now, by induction F_{i−1} = yxay = ρ^{−(f_{i−3}+1)}(G_{i−1}), which implies that G_{i−1} = ayyx. Similarly, F_{i−2} = yxa = ρ^{−1}(G_{i−2}), which implies that G_{i−2} = ayx. Since i is even, G_{i} = G_{i−2}G_{i−1} = ayxayyx and ρ(G_{i}) = yxayyxa = F_{i}. □

From Lemmas 11 and 2 we see that we can construct the Lyndon word corresponding to any Fibonacci word. One of the referees has pointed out that the results of this section can be generalized to Sturmian words.

6 Beatty sequences

In this section we show that Euclidean strings are related to Beatty sequences. A Beatty sequence is a sequence of the form a_{j} = ⌊αj + β⌋ where α > 1 and j ∈ ℤ. See for example [2] and [10]. Generally α and β can be rational or irrational but we will only be concerned with the case where α is rational and β = 0.

Lemma 12 Consider the Beatty sequence comprising the elements in the set a_{j} = ⌊\frac{n}{k}j⌋ : j ∈ ℤ, where gcd(n, k) = 1. For each integer j there exists an i where 0 ≤ i ≤ k − 1 such that

id + ⌊\frac{n}{k}j⌋ ≡ 0 mod n

where d is the multiplicative inverse of k, modulo n.

Proof Since dk ≡ 1 mod n, for any z, z ≡ zdk mod n. Hence, for any j

− ⌊\frac{n}{k}j⌋ ≡ (nj − k ⌊\frac{n}{k}j⌋)d mod n.

Consider the term in parentheses, which is a way of writing nj mod k. Because n and k are relatively prime, the term in parentheses can take on any integer value in the interval [0, k − 1]. Thus for any j there exists i ∈ [0, k − 1] such that

id + ⌊\frac{n}{k}j⌋ ≡ 0 mod n.

Similarly for any i ∈ [0, k − 1] there exists j satisfying this congruence. □

Corollary 4 The string p_{0}p_{1} ⋯ p_{n−1} is E_{n,k} where p_{i} = |{j : n−⌊nj/k⌋−1 = i, 0 ≤ j < k}|.

Proof By Lemma 1(c), p_{i} = |{j : n−1 + jd ≡ i mod n, 0 ≤ j < k}|, where d is the displacement of the string. By Lemma 1(d), dk ≡ 1 mod n. Hence, by Lemma 12, the set on the right hand side of the equation is identical to the set \{j : (n − ⌊\frac{n}{k}j⌋ − 1) = i, 0 ≤ j < k\}. □

This gives us one more algorithm for computing a Euclidean string. First initialize p_{0}p_{1} ⋯ p_{n−1} to be all zeroes. Then execute the following line of code, which uses the C increment operator.

for j = 0, 1, …, k−1 do ++p_{n−⌊nj/k⌋−1}

That is, a Euclidean string is the reversal of the histogram of a rational Beatty sequence.

As previously noted, it is faster to reduce an (n, k) instance where k > n to the instance (n, k mod n). After the application of Corollary 4 we construct the correct string by replacing the ones by ⌈k/n⌉ and the zeros by ⌊k/n⌋.

7 Relations with Sturmian sequences

Following [17] (pg. 59), the rational mechanical words, for rational number 0 ≤ p/q ≤ 1 with gcd(p, q) = 1, may be defined as the finite words

t_{p,q} = a_{0}a_{1} ⋯ a_{q−1}, t′_{p,q} = a′_{0}a_{2} ⋯ a′_{q−1}

by

a_{i} = ⌊(i + 1)\frac{p}{q}⌋ − ⌊i\frac{p}{q}⌋ , a′_{i} = ⌈(i + 1)\frac{p}{q}⌉ − ⌈i\frac{p}{q}⌉

These words are also known as Christoffel words and as characteristic words [1].

Theorem 5 Let n and k be relatively prime with 0 < k < n. Then E_{n,k} = t_{k,n}.

Proof

Recall Corollary 4. If n > k > 0 then for all indices i, where i ∈ \{n − ⌊\frac{n}{k}j⌋ − 1 : 0 ≤ j ≤ k − 1}, in the Euclidean word E_{n,k} we have p_{i} = 1, and p_{i} = 0 for all other indices.

Suppose that p_{i} = 0. Then there exists j, 0 ≤ j < k − 1 such that

n − ⌊\frac{n}{k}j⌋ − 1 > i > n − ⌊\frac{n}{k}(j + 1)⌋ − 1.

That is,

n − ⌊\frac{n}{k}j⌋ − 1 > i and i > n − ⌊\frac{n}{k}(j + 1)⌋ − 1
⇒ n − 1 − i > ⌊\frac{n}{k}j⌋ and ⌊\frac{n}{k}(j + 1)⌋ ≥ n − i
⇒ n − 1 − i > \frac{n}{k}j and \frac{n}{k}(j + 1) ≥ n − i
⇒ k − \frac{k}{n} − \frac{ik}{n} > j and j + 1 ≥ k − \frac{ik}{n}
⇒ k − j > \frac{k}{n}(1 + i) and \frac{k}{n}i ≥ k − j − 1.
⇒ ⌊\frac{k}{n}(1 + i)⌋ = ⌊\frac{k}{n}i⌋
⇒ ⌊\frac{k}{n}(1 + i)⌋ − ⌊\frac{k}{n}i⌋ = 0.

Thus a_{i} = 0 in t_{k,n}. The implications may all be reversed so we have a_{i} = 1 in t_{k,n} if and only if p_{i} = 1 is in the Euclidean word. Thus the words are the same. □

8 An application

The original motivation for studying these strings came from a graph embedding problem, in particular, the problem of many-to-one mappings from the nodes of a 2-dimensional grid onto the nodes of a hypercube. Here we require that the size of the grid is maximum with respect to the size of the hypercube and some specified “load”, i.e., the maximum number of grid nodes that can be mapped onto a single hypercube node. We ask whether there exists a mapping with dilation one, i.e., in which any pair of grid nodes connected by an edge are either mapped to the same hypercube node, or to the ends of an edge in the hypercube. A solution to this problem which uses the analysis of Euclidean strings is given in [8], for loads at least 4.

We give a very informal description of why the Euclidean strings are useful. The mapping into the hypercube is established via a mapping into a torus which is a subgraph of the

Figure 6: Grid to Torus Mapping

hypercube. Consider Figure 6. This diagram defines a partial mapping from part of a 13 × 21 grid onto an 8 × 16 torus with load 2. For each element in the grid, the number at each grid position specifies the torus row onto which the grid node is to be mapped. The shading distinguishes torus columns, numbered across the top. Thus for example, the second grid element in the top row of the grid is to be mapped to row 8, column 1 of the torus.

Suppose we chop off the “steps” at the right hand end, as indicated by the “cut” and insert the detached piece at the left end. Note that the shapes at the ends “match”. If the numbers also matched (a separate problem) we would have a load 2, dilation 1 embedding of the 13 × 16 grid into the 8 × 16 torus with load 2. Because that torus is a subgraph of the degree 7 hypercube, this embedding is also an embedding into the hypercube.

We may define the left and right “profiles” of a hypercube column in the diagram to be the sequence of step heights on the left or right of the column taken circularly. For example the left profile of column 2 is (3, 2, 3, 2, 3). Note that each successive profile is a rotation of its predecessor. For the cut and paste method to work we want the left profile of the leftmost column to match the right profile of the rightmost column.

The Euclidean string analysis permits us to argue that it is always possible to find a profile such that left and right end profiles of the pattern match. The profile pattern in Figure 6 is periodic with period 13. In general the width of the grid is not a multiple of this period. Further, it is necessary to “drop” one of more torus nodes from the pattern because the number of nodes in the grid is usually strictly less than the number of nodes in the torus times the load.

Consider the effect of dropping one torus node from the profile. For example, let us drop the circled element from column 1. One element in the profile is incremented and one is decremented by one. The resulting profile is now (3, 2, 3, 3, 2), which is a rotation of the unmodified profile and which matches the left profile of column 6.

The analysis of Euclidean strings establishes that we can always find a profile with the properties we need, namely that the result of dropping an element is a profile that is rotationally equivalent to the original.

9 Acknowledgement

The authors are grateful to the referees for carefully reading the paper and pointing out that Euclidean strings are related to Sturmian sequences. To our chagrin, we then discovered that there is a sizeable literature on Sturmian sequences, and on the Christoffel words in particular, and that some of what we thought we had discovered was already known, if in a slightly different form.

References

[1] J.-P. Allouche and J.O. Shallit, Automatic Sequences, Cambridge University Press, 2002.

[2] S. Beatty, Problem 3173, Amer. Math. Monthly, 33 (1926), 159.

[3] J. Berstel and A. de Luca, Sturmian words, Lyndon words and trees, Theoretical Computer Science, 178 (1997) 171-203.

[4] N. Calkin and H.S. Wilf, Recounting the Rationals, American Mathematical Monthly 107 (2000) 360–363.

[5] T. H. Corman, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, McGraw-Hill (1990).

[6] A. de Luca and F. Mignosi, Some combinatorial properties of Sturmian words, Theoretical Computer Science, 136 (1994) 361-385.

[7] X. Droubay, Palindromes in the Fibonacci Word, Information Processing Letters, 55 (1995) 217–221.

[8] J. Ellis, S. Chow and D. Manke Embedding grids into cylinders, toruses and hypercubes, submitted for publication.

[9] J. Ellis, F. Ruskey and J. Sawada Euclidean Strings, Proceedings of the Eleventh Australasian Workshop on Combinatorial Algorithms, L. Brankovic, J. Ryan (Eds), University of Newcastle, Australia (2000), 87–92.

[10] A. S. Fraenkel, The bracket function and complementary sets of integers, Canadian Jnl. Math., 21 (1967) 6–27.

[11] A. S. Fraenkel and J. Simpson, The exact number of squares in Fibonacci words, Theoretical Computer Science, 218, (1999), 95–106.

[12] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, (1960).

[13] F. Ruskey, A. Gulliver, C.R. Miers, and J. Sawada, The Number of Lyndon Words and Irreducible Polynomials of Given Trace, SIAM J. Discrete Mathematics, 14 (2001) 240–245.

[14] C.S. Iliopoulos, D. Moore, and W.F. Smyth, The covers of a circular Fibonacci string, J. Combin. Math. Combin. Comput. 26 (1998), 227–236.

[15] C.S. Iliopoulos, D. Moore, and W.F. Smyth, A characterization of the squares in a Fibonacci string, Theoretical Computer Science, 172 (1997), no. 1-2, 281–291.

[16] D.E. Knuth, R.L. Graham, and O. Patashnik, Concrete Mathematics, Addison-Wesley (1989).

[17] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002.

[18] A. de Luca and F. Mignosi, Some combinatorial properties of Sturmian words, Theoretical Computer Science, 136 (1994) 361–385.

[19] W. Zhi-Xiong and W. Zhi-Ying, Some properties of the singlular words of the Fibonacci word, Séminaire Lotharingien de Combinatoire, 30 (1993).