Lambda Words: A Class of Rich Words Defined Over an Infinite Alphabet

Norman Carey CUNY Graduate Center 365 Fifth Avenue New York, NY 10016 USA

                      ncarey@gc.cuny.edu

Abstract Lambda words are sequences obtained by encoding the differences between ordered elements of the form i + jθ, where i and j are non-negative integers and 1 < θ < 2. Lambda words are right-infinite words defined over an infinite alphabet that have connections with Sturmian words, Christoffel words, and interspersion arrays. We show that Lambda words are infinite rich words. Furthermore, any Lambda word may be mapped onto a right-infinite word over a three-letter alphabet. Although the mapping preserves palindromes and non-palindromes of the Lambda word, the resulting Gamma word is not rich.

1 Introduction

Here we formalize the Lambda word [9], which is a sequence formed by encoding the differences between ordered elements of the form i + jθ, where i and j are non-negative integers and θ is irrational, 1 < θ < 2. For example, when θ = ϕ = \frac{\sqrt{5}+1}{2}, the ordering begins

(0 + 0ϕ) < (1 + 0ϕ) < (0 + 1ϕ) < (2 + 0ϕ) < (1 + 1ϕ) < · · · .

Taking differences from (0, 1, ϕ, 2, 1 + ϕ, …) we get

1, ϕ − 1, 2 − ϕ, ϕ − 1, ….

There are four differences so far, but two of them are the same, and so the sequence of differences may be represented by the integer sequence, (0, 1, 2, 1, …). This is the beginning of Λ_{ϕ}, the Lambda word generated by ϕ (\underline{A216763}). Showing more terms,

Λ_{ϕ} = (0, 1, 2, 1, 2, 3, 2, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 3, 4, 3, 4, …).

A Lambda word is defined over an infinite alphabet 𝒜 of non-negative integers. Lambda words are related to Christoffel words [4] and Sturmian words [3, 12]. As we will show, they may be derived from interspersion arrays [23]. Lambda words developed from considerations of certain palindromic tonal spaces that contain important musical scales [10]. The main result of this paper is to show that Lambda words are rich words [19, 8].

Lambda words exhibit the following properties:

1. A Lambda word is a right-infinite word defined over an infinite alphabet [9, p. 46].

2. There are no recurrent letters (a fortiori, no recurrent factors) in a Lambda word.

3. The number of occurrences of any letter in a Lambda word may be calculated by means of convergents in the continued fraction expansion of θ.

4. Palindromes in a Lambda word are on alphabets of no more than three letters.

5. A Lambda word is rich.

6. There exists a projection that maps a Lambda word onto a right-infinite word over a three-letter alphabet that preserves palindromes and non-palindromes.

In this paper, after definitions in §2, the structure of the Lambda word is outlined through examples in §3. In §4, properties of continued fractions are discussed. In §5, we demonstrate statements (2) and (3), and in §6, statement (4). The central result of the paper is to prove statement (5) in §7. Statement (6) is demonstrated in §8. We define Lambda words after some basic notation and definitions.

2 The Lambda word

Following Lothaire [27], we say that 𝒜 is a set of symbols, finite or infinite. The symbols are referred to as letters. A finite or infinite sequence of letters from 𝒜 is a word. A finite word over the alphabet 𝒜 is an element of 𝒜^{∗}, the free monoid generated by 𝒜. The monoid operation is concatenation where it is understood that the empty word, ϵ, is a member of 𝒜^{∗} and serves as the identity element. If w is a word over 𝒜^{∗} and w = uv, then u is a prefix and v a suffix respectively of w. Both u and v are factors of w, as is x if w = uxv. The set of factors of a finite or infinite word w is denoted by F(w). A right-infinite word over 𝒜 is a map h from the set of non-negative integers into 𝒜 forming an infinite sequence, h(0), h(1), …, h(n), …, written with or without commas. If w = x_{1}x_{2} ⋯ x_{k} where x_{1}, x_{2}, … x_{k} ∈ 𝒜 then the reversal of w is w̃ = x_{k} ⋯ x_{2}x_{1}. A palindrome is a word p such that p = p̃.

In what follows, 𝒜 denotes an infinite alphabet of non-negative integers, elements of ℕ_{0} = {0, 1, 2, 3, …}. For letters x, y ∈ 𝒜 we write x ≺ y to indicate lexicographic order, which, here, coincides with numerical order.

We define θ ∈ ℝ \ ℚ, 1 < θ < 2 and the set

S(θ) = {i + jθ | i, j ∈ ℕ_{0}}.

S_{θ} will denote the strictly increasing sequence obtained by sorting the elements of S(θ) in ascending order. The n-th term of S_{θ} is denoted by s_{n} = i_{n} + j_{n}θ.

The first-order difference sequence of a given sequence A is written as ΔA. In particular, we will be interested in the difference sequence ΔS_{θ} where the n-th term is denoted by δ_{θ}(n) = s_{n+1} − s_{n}. The differences δ_{θ}(n) are generally decreasing as n increases, but not strictly. Moreover, because ΔS_{θ} contains repetitions, we may assign each element of ΔS_{θ} to an integer (an element in 𝒜) through a bijective mapping λ: Let λ(δ_{θ}(0)) = 0. If n_{1} is the least value such that δ_{θ}(n_{1}) ≠ δ_{θ}(0), then λ(δ_{θ}(n_{1})) = 1. Then λ(δ_{θ}(n_{2})) = 2, where n_{2} is the least value such that δ_{θ}(n_{2}) is unequal to either δ_{θ}(n_{1}) or δ_{θ}(n_{0}), and so on. More than a simple coding of differences, the mapping λ contains a deeper significance through a connection with the continued fraction expansion of θ, to be discussed in §4.1.

Finally, Λ_{θ} = (λ(δ_{θ}(0)), λ(δ_{θ}(1)), λ(δ_{θ}(2)), λ(δ_{θ}(3)), …). That is, Λ_{θ} is the word obtained from the sequence of differences in ΔS_{θ}, encoded by λ. We refer to Λ_{θ} as the Lambda word generated by θ.

3 Examples of Lambda words

Let ϑ = log_{2} 3. The table below presents Λ_{ϑ} (\underline{A216448}) as the encoded differences of the ascending sequence S_{ϑ}.

n  0  1  2  3  4  5  6  7
S_{ϑ} 0 + 0ϑ 1 + 0ϑ 0 + 1ϑ 2 + 0ϑ 1 + 1ϑ 3 + 0ϑ 0 + 2ϑ 2 + 1ϑ
ΔS_{ϑ} 1 − 0ϑ −1 + 1ϑ 2 − 1ϑ −1 + 1ϑ 2 − 1ϑ −3 + 2ϑ 2 − 1ϑ
Λ_{ϑ}  0  1  2  1  2  3  2

Because 1 − 0ϑ is the “0-th” difference in ΔS_{ϑ}, it maps, under λ, to 0. When n is 1 or 3, δ_{ϑ}(n) = −1 + 1ϑ. Then λ(δ_{ϑ}(1)) = λ(δ_{ϑ}(3)) = 1. Similarly, λ(δ_{ϑ}(2)) = λ(δ_{ϑ}(4)) = λ(δ_{ϑ}(6)) = 2, and λ(δ_{ϑ}(5)) = 3, and so on.

According to Kimberling [24], the sequence of integers i_{n} from S_{θ} is the signature of θ, whereas j_{n} gives the signature of 1/θ. Kimberling also introduces the interspersion array. Figure 1 shows the interspersion array associated with the signature sequence of 1/ϑ^{−1}. We modify Kimberling’s definition of the array so as to include zero [23, p. 313]: An array A = (a_{ij}), i ≥ 0, j ≥ 0, of non-negative integers is an interspersion if

1. the rows of A comprise a partition of the non-negative integers;

2. every row of A is an increasing sequence;

3. every column of A is an increasing (possibly finite) sequence;

4. if (u_{j}) and (v_{j}) are distinct rows of A and if p and q are any indices for which u_{p} < v_{q} < u_{p+1}, then u_{p+1} < v_{q+1} < u_{p+2}.

According to Kimberling and Brown [25], an array such as the one shown in Figure 1 is transposable, because substituting 1/θ for θ yields the transpose of the array. Adding one to each element in column one produces \underline{A022330}, and the same addition on elements of the first row gives \underline{A022331}. The relationship between transposable interspersions and Lambda words is this: Connecting the elements of the Figure 1 array in ascending order determines a sequence of vectors that begins (1, 0), (−1, 1), (2, −1), (−1, 1), and these are also the coefficients for the successive elements of the difference sequence ΔS_{ϑ}. Labeling each distinct vector starting with 0 yields Λ_{ϑ} = (0, 1, 2, 1, …). (See \underline{A167267} for a transposable interspersion of the signature sequence of ϕ.)

0 1 3 5 8 12 16 21 27 33 40 47
2 4 7 10 14 19 24 30 37 44 52
6 9 13 17 22 28 34 41 49
11 15 20 25 31 38 45 53
18 23 29 35 42 50
26 32 39 46 54
36 43 51

48

\begin{matrix}0 → 1 & 1 → 2 & 2 → 3 & 3 → 4 & 4 → 5 & 5 → 6 & 6 → 7 & 7 → 8 \\ (1, 0) & (−1, 1) & (2, −1) & (−1, 1) & (2, −1) & (−3, 2) & (2, −1) & (2, −1) \\ 0 & 1 & 2 & 1 & 2 & 3 & 2 & 2 \end{matrix}

Figure 1: Interspersion array for sequence i(ϑ^{−1}) and its path of vectors.

Λ_{ϑ} = 0, 1, 2, 1, 2, 3, 2, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 3, 4, 3, 4, 3, 3, 4, 3, 3, 5, 3, 3, 4, 3, 3, 5, 3, 3, 3, 5, 3, 3, 5, 3, 3, 3, 5, 3, 3, 5, 6, 5, 3, 3, 5, 3, 3, 5, 6, 5, 3, 3, 5, 6, 5, 3, 5, 6, 5, 3, 3, 5, 6, 5, 3, 5, 6, 5, 6, 5, 3, 5, 6, 5, 3, 5, 6, 5, 6, 5, 3, 5, 6, 5, 6, 5, 5, 6, 5, 6, 5, 3, 5, 6, 5, 6, 5, 5, 6, 5, 6, 5, 6, 5, 5, 6, 5, 6, 5, 5, 6, 5, 6, 5, 6, 5, 5, 6, 5, 6, 5, 5, 7, 5, 5, 6, 5, 6, 5, 5, 6, 5, 6, 5, 5, 7, 5, 5, 6, 5, 6, 5, 5, 7, 5, 5, 6, 5, 5, 7, 5, 5, 6, 5, 6, 5, 5, 7, 5, 5, 6, 5, 5, 7, 5, 5, 7, 5, 5, 6, 5, 5, 7, 5, 5, 6, 5, 5, 7, 5, 5, 7, 5, 5, 6, 5, 5, 7, 5, 5, 7, 5, 5, …

Figure 2: Graph of first 200 elements of Λ_{ϑ}.

Figure 2 provides a graphical representation of the first 200 elements of Λ_{ϑ}. It shows that Λ_{ϑ} gradually increases with n, but with repetitions and switchbacks, allowing for an abundance of palindromes. Figure 2 suggests other properties of Lambda words. For example, each integer appears a finite number of times: After smaller integers die out, larger ones take their place.

Of particular interest is \underline{A216763}, the Fibonacci Lambda word, Λ_{ϕ}, where ϕ = \frac{\sqrt{5}+1}{2}. Figure 3 presents its first 196 elements. Because of the slow convergence of the continued fraction of ϕ, successive members of Λ_{ϕ} differ by at most unity.

Λ_{ϕ} = 0, 1, 2, 1, 2, 3, 2, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 3, 4, 3, 4, 3, 3, 4, 3, 4, 5, 4, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 4, 5, 4, 3, 4, 5, 4, 4, 5, 4, 5, 4, 4, 5, 4, 4, 5, 4, 5, 4, 4, 5, 4, 5, 6, 5, 4, 5, 4, 4, 5, 4, 5, 6, 5, 4, 5, 4, 5, 6, 5, 4, 5, 6, 5, 4, 5, 4, 5, 6, 5, 4, 5, 6, 5, 5, 6, 5, 4, 5, 6, 5, 4, 5, 6, 5, 5, 6, 5, 4, 5, 6, 5, 5, 6, 5, 6, 5, 5, 6, 5, 4, 5, 6, 5, 5, 6, 5, 6, 5, 5, 6, 5, 5, 6, 5, 6, 5, 5, 6, 5, 6, 5, 5, 6, 5, 5, 6, 5, 6, 5, 5, 6, 5, 6, 7, 6, 5, 6, 5, 5, 6, 5, 6, 5, 5, 6, 5, 6, 7, 6, 5, 6, 5, 5, 6, 5, 6, 7, 6, 5, 6, 5, 6, 7, 6, 5, 6, 5, 5, 6, 5, 6, 7, 6, 5, 6, 5, …

Figure 3: Graph of first 196 elements of Λ_{ϕ}.

The Lambda word generated by π − 2, \underline{A216764}, presents a very different profile, as shown in Figure 4. The continued fraction expansion, [1, 7, 15, 1, 292, …], converges relatively rapidly. Note that the greatest difference between successive values so far is 7, which follows from the value of the second partial quotient of the expansion. Further on, the word will exhibit differences of 15, 292, and so on.

Λ_{π−2} = 0, 1, 2, 1, 1, 3, 1, 1, 1, 4, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 8, 9, 8, 1, 1, 1, 1, 1, 1, 8, 9, 8, 9, 8, 1, 1, 1, 1, 1, 8, 9, 8, 9, 8, 9, 8, 1, 1, 1, 1, 8, 9, 8, 9, 8, 9, 8, 9, 8, 1, 1, 1, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 1, 1, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 1, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 8, 10, 8, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 8, 10,8, 8, 10, 8, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 8, 10, 8, 8, 10, 8, 8, 10, 8, 8, 9, 8, 9, 8, 9, 8, 9, 8, …

Figure 4: Graph of first 193 elements of Λ_{π−2}.

4 Lambda words and continued fractions

The structure of a Lambda word is determined by the continued fraction expansion of θ, its generating value. We demonstrate some of these relationships here, beginning with a theorem about differences in ΔS_{θ}. Standard theorems regarding continued fractions can be found in many texts [11, 22, 29, 26]. If [t_{0}; t_{1}, …, t_{k}, …] is a continued fraction, then the t_{k} are its partial quotients and c_{0} = [t_{0}], c_{1} = [t_{0}; t_{1}], c_{2} = [t_{0}; t_{1}, t_{2}], etc., are its principal convergents. There are two formal convergents for any continued fraction: c_{−2} = 0/1 and c_{−1} = 1/0. If c_{k} = a_{k}/b_{k}, then gcd(a_{k}, b_{k}) = 1. Moreover, c_{k+1} = (t_{k+1}a_{k} + a_{k−1})/(t_{k+1}b_{k} + b_{k−1}). If t_{k} > 1 we define integer t such that 1 ≤ t < t_{k}. Then [t_{0}; t_{1}, …, t_{k−1}, t] is an intermediate convergent of the continued fraction. In this paper, the term “convergent” means a principal convergent or an intermediate convergent. Khinchin [26] devises the term “best approximation of the second kind” for a rational p/q of some real number θ if |qθ − p| < |q′θ − p′| whenever p ≥ p′. (A best approximation of the first kind involves the value |θ − p/q| and plays no role here. A “best approximation” will refer to one of the second kind.)

In addition to the best “two-sided” approximations described, Richards [30] further defines a best one-sided approximation: Take p/q < θ. If 0 < qθ −p < q′θ −p′ whenever q ≥ q′, then p/q is a best lower, or left, approximation. For any best left approximation it follows that p = ⌊qθ⌋. When p/q is a best higher, or right approximation, θ < p/q, and q = ⌊p/θ⌋. With 1 < θ < 2, any intermediate convergent is a best one-sided approximation and (with a single exception) any principal convergent is a best two-sided approximation. Certainly, any best two-sided approximation is the best on its side as well. (The exception is in the case of the formal convergent 0/1. It is not a best left approximation because the convergent 1/1 is also less than θ and has the same denominator.)

Theorem 1. |A − Bθ| ∈ ΔS_{θ} ⟺ A/B is a best approximation (of the second kind) of θ.

Proof. (See also [11, Theorem 1].)

⇒. We prove the case δ_{θ}(n) = Bθ − A, i.e., A < Bθ.

δ_{θ}(n) = s_{n+1} − s_{n} = (i_{n+1} + j_{n+1}θ) − (i_{n} + j_{n}θ) = Bθ − A.

Then (j_{n+1} − j_{n})θ = Bθ and i_{n} − i_{n+1} = A, and so s_{n+1} ≥ Bθ and s_{n} ≥ A. Define g such that

g = (s_{n+1} − Bθ) = (s_{n} − A).  (1)

Then g ∈ S_{θ}. Assume Bθ − A > 0 but A/B is not a best left approximation. Then there exist successive best left approximations p/q and p′/q′ with q ≤ B < q′ such that qθ − p < Bθ − A.

Then

0 < qθ − p < Bθ − A.

Adding A + g we obtain

A + g < A + g − p + qθ < Bθ + g.

Clearly, A + g − p + qθ = s_{n′} ∈ S_{θ}, and so, by (1), s_{n} < s_{n′} < s_{n+1}. Contradiction. (For the case δ_{θ}(n) = A − Bθ, redefine g as ĝ = (s_{n+1} − A) = (s_{n} − Bθ).)

⇐. The second part of the proof is again by contradiction: Assume A/B is a best left approximation. Now assume that A = s_{n} and Bθ = s_{n+k} with k > 1. Then we must have s_{n+1} = i + jθ such that

A < i + jθ < Bθ  (2)

Then j < B. Because ⌊Bθ⌋ = A, we see that i < A.

Subtracting A from (2) we obtain

0 < jθ − (A − i) < Bθ − A.  (3)

Because A/B is a best left approximation, there is no integer k such that jθ−k < Bθ−A. In particular, jθ−(A−i) ≮ Bθ−A. contradicting (3). Then if A/B is a best left approximation, δ_{θ}(n) = (Bθ − A), therefore (Bθ − A) ∈ ΔS_{θ}.

4.1 The mapping λ formalized

The continued fraction allows for an algorithmic form of the mapping λ: In the case of the formal convergent 1/0, define λ(1 − 0θ) = λ(δ_{θ}(0)) = 0. Otherwise, for each distinct difference |A − Bθ|, express A/B as a finite continued fraction [1; t_{1}, t_{2}, …, t_{k}]. Then λ may be computed as

λ|A − Bθ| = ∑_{i=0}^{k} t_{i}.

|A − Bϑ| A/B [1; t_{1}, …, t_{k}] ∑_{i=0}^{k} t_{i}
1  1/0  0
ϑ − 1  1/1 [1]  1
2 − ϑ  2/1 [1, 1]  2
2ϑ − 3 3/2 [1, 1, 1]  3
5 − 3ϑ 5/3 [1, 1, 1, 1]  4
8 − 5ϑ 8/5 [1, 1, 1, 2]  5
7ϑ − 11 11/7 [1, 1, 1, 2, 1]  6
12ϑ − 19 19/12 [1, 1, 1, 2, 2]  7
27 − 17ϑ 27/17 [1, 1, 1, 2, 2, 1]  8
46 − 29ϑ 46/29 [1, 1, 1, 2, 2, 2]  9
65 − 41ϑ 65/41 [1, 1, 1, 2, 2, 3] 10

Figure 5: Computing λ|A − Bϑ| by sums of partial quotients.

Figure 5 shows the first eleven convergents of the continued fraction expansion of ϑ = log_{2} 3 under λ. Every non-negative integer is equal to exactly one of the summations, which is guaranteed for all θ by the second half of the proof of Theorem 1. As a result, the mapping λ associates the difference |A − Bθ| with the row of the Stern-Brocot tree on which A/B is found [32, 20, pp. 116–117].

4.2 The Hurwitz chain

In what follows we will make use of an oft-noted connection between Farey series, continued fractions, and mediants [17, 30]. If a/b < c/d are consecutive fractions in a Farey series then bc − ad = 1 = gcd(a, b) = gcd(c, d). Then we say that (a/b, c/d) form a Farey pair. Whenever a/b < θ < c/d, the Farey pair is also a pair of best left-right approximations of θ. The Hurwitz chain for θ contains all such pairs (a/b, c/d) [21]. If (a/b, c/d) belongs to the Hurwitz chain for θ, then, if a/b is an intermediate convergent, c/d is the previous principal convergent and conversely. Otherwise, a/b and c/d are consecutive principal convergents. The mediant of these fractions, (a + c)/(b + d) falls between them and is also a convergent. This implies that (a + c)/(b + d) forms a member of the Hurwitz chain for θ with either a/b or c/d.

Let A/B and p/q be a pair of best left-right approximations of θ such that |A − Bθ| > |p−qθ|. Then either (A/B, p/q) or (p/q, A/B) belongs to the Hurwitz chain for θ. If A/B is a principal convergent, then p/q is the principal convergent that immediately follows A/B, and if A/B is an intermediate convergent, then p/q is the principal convergent that immediately precedes A/B. Furthermore, q > B when A/B is a principal convergent, q < B otherwise. Either way, (A + p)/(B + q) is the first convergent that succeeds both.

5 Counting letters

A recurrent factor of an infinite word is a factor that appears infinitely often. Here we show that there are no recurrent letters, consequently, no recurrent factors in a Lambda word. We let λ|A − Bθ| = x and let |Λ_{θ}|_{x} represent the number of times the letter x occurs in Λ_{θ}.

Theorem 2. |Λ_{θ}|_{x} = pq.

Proof. We prove the theorem for A/B < θ; the proof for A/B > θ is left as an exercise. First, let us define

\begin{aligned}X & = & Bθ & − & A \\ Y & = & p & − & qθ \\ Z & = & (B + q)θ & − & (A + p) \end{aligned}

Then Z = X − Y. It follows that A/B < (A + p)/(B + q) < θ < p/q. Furthermore, Y < X and Z < X. We define a subset S(θ)_{x} of S(θ) such that

S(θ)_{x} = {s_{n} | δ_{θ}(n) = X where λ(X) = x}.

That is, s_{n} ∈ S(θ)_{x} ⟺ s_{n} + X = s_{n+1}. We will show that there are pq elements in S(θ)_{x}, and so |Λ_{θ}|_{x} = pq. In order to do so, we prove that

S(θ)_{x} = {a + bθ | A ≤ a < (A + p); 0 ≤ b < q}  (4)

Because s_{n} ∈ S(θ) it immediately follows that 0 ≤ b.

Further, s_{n} + X ∈ S(θ) implies a + bθ + (Bθ − A) ∈ S(θ) and so A ≤ a.

If s_{n} ∈ S(θ)_{x} and b − q ≥ 0, then it would follow that s_{n} + Y = a + bθ + (p − qθ) ∈ S(θ). But Y < X and so s_{n} < s_{n} +Y < s_{n} +X, that is, s_{n+1} ≠ s_{n} +X. Thus, s_{n} ∉ S(θ)_{x}, contrary to hypothesis. Therefore b < q.

If a ≥ A + p, then a + bθ + ((B + q)θ − (A + p)) = s_{n} + Z ∈ S(θ). But Z < X and so s_{n} < s_{n} + Z < s_{n} + X, contradicting s_{n+1} = s_{n} + X. Then a < A + p.

Therefore A ≤ a < (A + p) and 0 ≤ b < q and so there are pq elements in S(θ)_{x}, i.e., |Λ_{θ}|_{x} = pq.

We note that, when A/B > θ, we have

S(θ)_{x} = {a + bθ | 0 ≤ a < p; B ≤ b < B + q}.  (5)

6 Two-Letter factors of Lambda words

To determine the limit on the number of different letters in palindromes in a Lambda word, we explore the two-letter factors of the word, which we define as members of the set F_{2}(Λ_{θ}). For x, y ∈ 𝒜, we determine the conditions under which xy ∈ F_{2}(Λ_{θ}).

6.1 Letter repetitions

To begin, we investigate the two-letter factors of the form xx = x^{2}. Let t be the greatest integer such that x^{t} is a factor of Λ_{θ}. Let t_{k} be the k-th partial quotient of the continued fraction expansion of θ = [1; t_{1}, …, t_{k}, …].

Theorem 3. If x = λ|A − Bθ| where A/B is an intermediate convergent, xx ∉ F_{2}(Λ_{θ}). If A/B is the principal convergent a_{k}/b_{k}, xx ∈ F_{2}(Λ_{θ}). There are two special cases when A/B is a_{−1}/b_{−1} or a_{0}/b_{0}.

Proof. Let |A − Bθ| = X. If a xx is a factor of Λ_{θ}, then S(θ)_{x} would have to include both a + bθ and a + bθ + X. If x^{t} is a factor, then a + bθ + (t − 1)X must be an element of S(θ)_{x}. We can solve for t by invoking the conditions on a and b in S(θ)_{x}, as shown in (4) and (5).

\begin{matrix}A ≤ a + (t − 1)A < A + p \\ 0 ≤ b + (t − 1)B < q \end{matrix} \} by (4)

\begin{matrix}0 ≤ a + (t − 1)A < p \\ B ≤ b + (t − 1)B < B + q \end{matrix} \} by (5)

We are interested in the maximal value for t, so we substitute minimal values for a and b, which simplifies to two results

t < 1 + \frac{p}{A} and t < 1 + \frac{q}{B} .  (6)

When A/B is an intermediate convergent, p/q is the previous principal convergent, and so B > q (and A > p). Therefore t < 1 + (q/B) < 2, i.e., t = 1. Therefore, when A/B is an intermediate convergent xx ∉ F_{2}(Λ_{θ}).

If A/B is a principal convergent, then it is associated with the partial quotient t_{k}, and p/q is the the next convergent, associated with t_{k+1}. Let p′/q′ represent the principal convergent that immediately precedes A/B. Then q/B = t_{k+1} + (q′/B). Whenever k > 0, q′/B ≤ 1, and so we can solve for t: t < 1 + t_{k+1} + (q′/B). Then t = 1 + t_{k+1}. (Alternatively, t < 1 + t_{k+1} + (p′/A) yields the same result for k > 0.) Because t_{k+1} ≥ 1, then t > 1 and so whenever A/B is a principal convergent, xx ∈ F_{2}(Λ_{θ}).

There are two special cases that involve principal convergents when k = −1 or 0. In both cases, t = t_{k+1}: For k = −1, A/B = 1/0, p/q = 1/1. The first inequality of (6) resolves to t < 2, but the second entails division by zero and is rejected. Then t = t_{k+1} = t_{0} = 1 and xx ∉ F_{2}(Λ_{θ}). For k = 0, A/B = 1/1, p/q = (1 + t_{1})/t_{1} The inequalities in (6) resolve to t < 2 + t_{1} and t < 1 + t_{1}. Both must be satisfied but the second is more restrictive, so again t = t_{1} = t_{k+1} Then xx ∈ F_{2}(Λ_{θ}) whenever t_{1} ≥ 2.

6.2 Square-free two-letter factors

For u, v, ∈ 𝒜 u ≠ v, we examine conditions under which uv ∈ F_{2}(Λ_{θ}). We let r be a word over 𝒜 such that r ∈ F(Λ_{θ}). We begin by examining cases of pairs of letters (u, v) with u ≺ v such that vru ∉ F(Λ_{θ}).

Recall that X − Y = Z. We define W = X + Y. We write a/b ⊕ c/d = (a + c)/(b + d) to indicate that the fraction on the right side is the mediant of the two on the left. Similarly, a/b ⊖ c/d = (a − c)/(b − d). We define a function f on the difference |A − Bθ| such that f|A − Bθ| = A/B. The pair (f(X), f(Y)) is a member of the Hurwitz chain for θ. Then f(X) ⊕ f(Y) = f(Z) and so (f(Y), f(Z)) is also a member of the Hurwitz chain. It follows that f(X) ⊖ f(Y) = f(W) and so either (f(W), f(X)) or (f(W), f(X)) is a member of the Hurwitz chain as well. Certainly f(W), f(X), f(Y), and f(Z) are all convergents to θ, and so by Theorem 1, W, X, Y, and Z, are differences in ΔS_{θ}. See Figure 6.

\underline{Differences}

W =  X + Y  = | (B − q)θ − (A − p) |
X =  | Bθ  −  A |
Y =  | p  − qθ |
Z =  X − Y  = | (B + q)θ − (A + p) |

\underline{Ratios}

f(W) = f(X) ⊖ f(Y) = | A − p | / | B − q |
f(X) =  A/B
f(Y) =  p/q
f(Z) = f(X) ⊕ f(Y) =  (A + p)/(B + q)

\underline{Letters}

λ(W) =  w
λ(X) =  x
λ(Y) =  y
λ(Z) =  z

Figure 6: Differences, ratios, and letters that govern potential two-letter factors.

The following theorem provides groundwork for Theorem 5, which will show that uv is a factor if and only if f((U), f(V)) belongs to the Hurwitz chain for θ. As before, for difference U, we let λ(U) = u.

Let r be a (possibly empty) factor of Λ_{θ}.

Theorem 4. If (f(X), f(Y)) belongs to the Hurwitz chain for θ, zrw ∉ F(Λ_{θ}). Furthermore, wz ∉ F_{2}(Λ_{θ}).

Proof. We prove the first part of the theorem by showing that the difference W never comes after Z in ΔS_{θ}. We prove the case X = A − Bθ:

\begin{aligned}W & = & X & + & Y \\ X & = & A & − & Bθ \\ Y & = & qθ & − & p \\ Z & = & (A + p) & − & (B + q)θ \end{aligned}

The smallest member of S_{θ} for which δ_{θ}(n) = Z is (B + q)θ. Therefore, if W appears after Z, then there exists δ_{θ}(m) = W such that s_{m} ≥ A + p > (B + q)θ. Consequently, s_{m} > (B + q)θ − Y = p + Bθ. But s_{m} < s_{m} + Y < s_{m} + X < s_{m} + W and at least one of these is true: s_{m} + Y ∈ S_{θ} and/or s_{m} + X ∈ S_{θ}. Then W ≠ δ_{θ}(m) whenever s_{m} ≥ (B + q)θ. Therefore zrw ∉ F(Λ_{θ}).

It is also true that wz is not a factor. The first part of the proof has shown that δ_{θ}(n) ≠ W when s_{n} > (B + q)θ and so we need only show that if s_{m} = (B + q)θ, then δ_{θ}(m − 1) ≠ W. Clearly, (B + q)θ − Y ∈ S_{θ}. However, (B + q)θ − W < (B + q)θ − Y < (B + q)θ = s_{m} and so W ≠ δ_{θ}(m − 1).

Certainly if z′ ⪰ z then z′rw is not a factor of Λ_{θ}.

Theorem 3 revealed the conditions under which x^{2} ∈ F_{2}(Λ_{θ}). The following theorem demonstrates the conditions under which xy ∈ F_{2}(Λ_{θ}) is comprised of different letters. Let u = λ(U), v = λ(V), and u ≠ v.

Theorem 5. uv ∈ F_{2}(Λ_{θ}) ⟺ (f(U), f(V)) belongs to the Hurwitz chain for θ.

Proof. Theorem 4 has limited membership in F_{2}(Λ_{θ}) for a fixed {x, y} to a pair of letters in {w, x, y, z}. Then U, V ∈ {W, X, Y, Z}. Let U = |A^{∗} − B^{∗}θ|, V = |p^{∗} − q^{∗}θ|. By Theorem 1, A^{∗}/B^{∗} and p^{∗}/q^{∗} are convergents.

⇒ Assume uv ∈ F_{2}(Λ_{θ}). If (f(U), f(V)) does not belong to the Hurwitz chain then at least one of these is false:

1. |A^{∗}q^{∗} − B^{∗}p^{∗}| = 1

2. f(U) and f(V) lie on opposite sides of θ.

We test both conditions. Assume |A^{∗}q^{∗} − B^{∗}p^{∗}| ≠ 1. Because |Aq − Bp| = 1, then |A^{∗}q^{∗} − B^{∗}p^{∗}| = 1 for all pairs of {f(W), f(X), f(Y), f(Z), } except the pair {f(W), f(Z)}. But Theorem 4 has already shown that neither zw nor wz belong to F_{2}(Λ_{θ}), therefore condition 1 is true, that is, |A^{∗}q^{∗} − B^{∗}p^{∗}| = 1.

Now assume that f(U) and f(V) are both greater than θ. Let δ_{θ}(n) = U, δ_{θ}(n + 1) = V, with U > V (otherwise relabel U ↔ V). If uv ∈ F_{2}(Λ_{θ}), then we have contiguous elements s_{n}, s_{n} + U, s_{n} + U + V. If s_{n} = a + bθ, then b ≥ B^{∗} + q^{∗}, so s_{n} + V ∈ s_{θ}, but s_{n} < s_{n} + V < s_{n} + U + V, which implies that U = V, a contradiction. Similarly when f(U) and f(V) are both less than θ. Therefore both conditions are true and so uv ∈ F_{2}(Λ_{θ}) implies that (f(U), f(V)) is a member of the Hurwitz chain.

⇐ Now assume (f(U), f(V)) is a member of the Hurwitz chain for θ. We show that uv ∈ F_{2}(Λ_{θ}). We let (f(U), f(V)) = (f(X), f(Y)), remembering that (f(X), f(Y)) may represent any member of the Hurwitz chain for θ. The limits on S(θ)x in Theorem 2 will be utilized to show that max(S(θ)_{x}) + X ∈ S(θ)_{y} and so xy = uv ∈ F_{2}(Λ_{θ}). Let P/Q be the principal convergent that immediately follows p/q. Again letting X = Bθ − A, Y = p − qθ,

max(S(θ)_{x}) + X = (A + p − 1 + (q − 1)θ) + (Bθ − A) = p − 1 + (B + q − 1)θ.

Then

p − 1 + (B + q − 1)θ ∈ S(θ))_{y} = {a + bθ | 0 ≤ a < P; q ≤ b < q + Q}

because 0 ≤ p − 1 < P and q ≤ (B + q − 1) < q + Q. Then uv ∈ F_{2}(Λ_{θ}. We can also show that max(S(θ)_{x}) − Y ∈ S(θ)_{y} and so vu also belongs to F_{2}(Λ_{θ}).

For a fixed (f(X), f(Y)), members of the Hurwitz chain for θ always include both (f(Y), f(Z)) and (f(X), f(Y)). If f(W) is on the same side of θ as f(X), then (f(W), f(Y)) belongs to the Hurwitz chain. Otherwise, (f(W), f(X)) does. Then there are six two-letter square-free factors over {w, x, y, z}: yz, xy, wx (or wy), and their reversals.

Corollary 6. Palindromes in Λ_{θ} are over alphabets of at most three letters.

Proof. By Theorem 4 it follows that if z′ ⪰ z then z′rw ∉ F(Λ_{θ}) and so z′rwr̃z′ ∉ F(Λ_{θ}) and wr̃z′rw ∉ F(Λ_{θ}). Then any palindrome in Λ_{θ} is over some alphabet 𝒳 = {x, y, z} ⊂ 𝒜.

7 Rich words

The topic of palindromic complexity [1, 14, 15] concerns the question of the number of distinct palindromes contained in a word of length k. Words that achieve the maximal number of palindromes have been known alternately as “rich” words [1, 7, 19] or “full” words [5, 6]. We will use the term “rich” here, as it seems to be found more in current usage. It is known [13] that a word of length k contains at most k + 1 distinct palindromes (including the empty word). A word that achieves this maximal number of distinct palindromes is a rich word [19]. Alternately, a rich word contains k non-empty distinct palindromes. Thus, the word “large” is rich, as each of its five letters is a palindrome. The word “small” is also rich, because “s”, “m”, “a” “l” and “ll” constitute five non-empty palindromes. On the other hand, “edge” is not rich as it contains only three distinct non-empty palindromes. All words of up to length three are rich.

Droubay, Justin, and Pirillo [13] demonstrate an equivalent definition of rich words: A word is rich if each of its prefixes terminates with a uni-occurrent palindromic suffix (ups). For example, the relevant prefixes of the rich word “indeed” are “i”, “in”, “ind”, “inde”, “indee”, “indeed”, and the empty word. The italics capture the uni-occurrent palindromic suffixes. Because the reverse of a rich word is also rich, we can also say that a word is rich if each suffix contains a uni-occurrent palindromic prefix.

It follows that a word is rich if all of its factors are rich, which extends the concept to include infinite rich words. A right-infinite word is rich if each prefix of the word terminates in a ups. Recent studies of rich words have examined Sturmian [28], episturmian [18], and other words on finite alphabets. The results here extend the topic to the Lambda word, a word defined over an an infinite alphabet. By way of motivation, we again examine Λ_{ϑ} where ϑ = log_{2} 3. The beginning of this sequence was shown in Figure 2. As Figure 7 shows, all of its first twelve prefixes end with a ups.

\begin{matrix}0 & \underline{0} \\ 1 & 0, \underline{1} \\ 2 & 0, 1, \underline{2} \\ 3 & 0, \underline{1, 2, 1} \\ 4 & 0, 1, \underline{2, 1, 2} \\ 5 & 0, 1, 2, 1, 2, \underline{3} \\ 6 & 0, 1, 2, 1, \underline{2, 3, 2} \\ 7 & 0, 1, 2, 1, 2, 3, \underline{2, 2} \\ 8 & 0, 1, 2, 1, 2, \underline{3, 2, 2, 3} \\ 9 & 0, 1, 2, 1, \underline{2, 3, 2, 2, 3, 2} \\ 10 & 0, 1, 2, 1, 2, 3, 2, 2, \underline{3, 2, 3} \\ 11 & 0, 1, 2, 1, 2, 3, 2, 2, 3, 2, 3, \underline{4} \end{matrix}

Figure 7: Uni-occurrent palindromic suffixes in the first twelve prefixes of Λ_{ϑ}.

The following proposition and four lemmas set up Theorem 12, which proves that Λ_{θ} is rich. We will show that every prefix of Λ_{θ} is terminated by a ups.

7.1 Additive complements

Two definitions are required: If c + c′ = h, then c′ is the complement of c with respect to h. A strictly increasing sequence C = (c_{1}, …, c_{n}) where complements are defined with respect to c_{1} + c_{n}, is said to be a sequence of additive complements (or simply, “sequence of complements”) if c′ ∈ C whenever c ∈ C. It follows that if c_{a} < c_{b}, then c_{a}′ > c_{b}′ and also that c_{k}′ = c_{n+1−k} where 1 ≤ k ≤ n. Proposition 7. (Trivial). C is a sequence of complements iff ΔC is a palindrome.

The proof is immediate from the definitions.

7.2 Beatty sequences

Setting k ∈ ℕ allows for two values that approximate θ:

\frac{⌊kθ⌋}{k} < θ < \frac{k}{⌊k(θ^{−1})⌋}.

These approximations include the “best approximations of the second kind” but form a larger set, comprised of the best left approximation for every denominator k, and the best right one for every numerator k. We also have

\begin{aligned}⌊kθ⌋ & < & kθ \\ ⌊k(θ^{−1})⌋θ & < & k. \end{aligned}  (7)

Summing the values in (7) gives rise to two integer sequences:

\begin{aligned}K^{(−)} & = & ⌊kθ⌋ + k \\ K^{(+)} & = & ⌊k(θ^{−1})⌋ + k \end{aligned}

where k runs through the positive integers.

For the next lemma, we utilize the notion of complementary Beatty sequences, the word “complement” here used in a sense distinct from above. A Beatty sequence [2, 16] is an infinite sequence of integers ⌊kα⌋ where α is an irrational number. Complementary Beatty Sequences ⌊kα⌋ and ⌊kβ⌋ are formed whenever 1/α + 1/β = 1. Any positive integer belongs to exactly one of ⌊kα⌋ or to ⌊kβ⌋.

Lemma 8. K^{(−)} and K^{(+)} form a complementary pair of Beatty sequences.

Proof. If α = (θ + 1), we get the Beatty Sequence ⌊kα⌋ = ⌊k(θ + 1)⌋ = ⌊kθ + k⌋ = ⌊kθ⌋ + k = K^{(−)}. Solving 1/(θ + 1) + 1/β = 1 for β gives \frac{θ+1}{θ}, which yields Beatty Sequence ⌊kβ⌋ = ⌊k(\frac{θ+1}{θ})⌋ = ⌊\frac{kθ}{θ} + \frac{k}{θ}⌋ = k + ⌊\frac{k}{θ}⌋ = K^{(+)}. Consequently, every positive integer belongs either to K^{(−)} or to K^{(+)}.

7.3 Nuclear sequences and palindromes

We utilize the limits shown in (7) to form two classes of contiguous subsequences of S_{θ}, indexed by K^{(−)} or K^{(+)}:

\begin{matrix}N_{K^{(−)}} = (s_{n} | ⌊kθ⌋ ≤ s_{n} ≤ kθ) \\ N_{K^{(+)}} = (s_{n} | ⌊k(θ^{−1})⌋θ ≤ s_{n} ≤ k) \end{matrix}

Letting K = K^{(−)}∪K^{(+)}, then N_{K} refers to a member of either of these types of “nuclear” sequences. (It is not difficult to show that the nuclear sequences cover S_{θ}, i.e., for all n, there is at least one K such that s_{n} ∈ N_{K}. The result is not required in what follows.)

Lemma 9. N_{K} is a sequence of complements.

Proof. We prove that both N_{K^{(−)}} and N_{K^{(+)}} are complementary sequences. We begin with N_{K^{(−)}} = (s_{n} | ⌊kθ⌋ ≤ s_{n} ≤ kθ). Let s′_{n} represent the complement of s_{n}. That is,

s_{n} + s′_{n} = ⌊kθ⌋ + kθ.  (8)

Clearly if s_{n} ∈ N_{K^{(−)}}, ⌊kθ⌋ ≤ s′_{n} ≤ kθ. Now we show that s′_{n} ∈ S_{θ}. Let s_{n} = i + jθ, s′_{n} = i′ + j′θ. Then ⌊kθ⌋ ≤ i + jθ ≤ kθ. This implies ⌊kθ⌋ = ⌊i + jθ⌋, which gives i ≤ ⌊kθ⌋ and j ≤ k. Rewrite Equation (8) as

i + i′ + (j + j′)θ = ⌊kθ⌋ + kθ

Because θ is irrational,

\begin{matrix}0 ≤ i + i′ = ⌊kθ⌋ \\ 0 ≤ j + j′ = k. \end{matrix}

Then, 0 ≤ i′ ≤ ⌊kθ⌋ and 0 ≤ j′ ≤ k, which means s′_{n} = i′ +j′θ ∈ S_{θ} and therefore s′_{n} ∈ N_{K^{(−)}} whenever s_{n} ∈ N_{K^{(−)}}. Then N_{K^{(−)}} is a sequence of complements.

Next we prove the same for N_{K^{(+)}} = (s_{n} | ⌊k(θ^{−1})⌋θ ≤ s_{n} ≤ k). Rewrite Equation (8) as

s_{n} + s′_{n} = ⌊k(θ^{−1})⌋θ + k.  (9)

and so if s_{n} ∈ N_{K^{(+)}}, ⌊k(θ^{−1})⌋θ ≤ s′_{n} ≤ k.

If s_{n} = i + jθ ∈ N_{K^{(+)}} we have i + jθ < k, and so i ≤ k. Dividing the inequality ⌊k(θ^{−1})⌋θ ≤ i + jθ ≤ k through by θ we get ⌊\frac{k}{θ}⌋ ≤ \frac{i}{θ} + j ≤ \frac{k}{θ}, and so ⌊\frac{k}{θ}⌋ = ⌊\frac{i}{θ} + j⌋, or j ≤ ⌊\frac{k}{θ}⌋. Then

\begin{matrix}0 ≤ i + i′ = k \\ 0 ≤ j + j′ = ⌊k(θ^{−1})⌋. \end{matrix}

Therefore both i′ ≥ 0 and j′ ≥ 0, and so s′_{n} = i′ +j′θ ∈ S_{θ} and N_{K^{(+)}} is also a sequence of complements. Thus for all K, N_{K} is a sequence of complements of S_{θ}. Then, by Proposition 7, ΔN_{K} is a palindrome.

We refer to ΔN_{K} as a nuclear palindrome.

7.4 Maximal sequences and palindromes

In general, it is possible to expand a nuclear palindrome, adding elements symmetrically to the left and the right as we will demonstrate below. First we simplify our notation and let

A = \begin{cases}min(N_{K^{(−)}}) \\ max(N_{K^{(+)}}) \end{cases} Bθ = \begin{cases}max(N_{K^{(−)}}) \\ min(N_{K^{(+)}}) \end{cases}

It follows that A+Bθ = min(N_{K})+max(N_{k}) that is, complements in N_{K} are defined with respect to A+Bθ. Furthermore, A+B = K. We can, in general, find longer complementary sequences of A + Bθ. Whenever i + jθ ∈ N_{K}, 0 ≤ i ≤ A and 0 ≤ j ≤ B. However, these limits hold on i and j whenever s_{n} < max(N_{K+1}). Then let

\begin{aligned}T_{K} & = & (s_{n} | max(N_{K}) ≤ s_{n} < max(N_{K+1})) \\ T′_{K} & = & (s_{n} | s′_{n} ∈ T_{K}) \end{aligned}

where, again, complements are defined with respect to A + Bθ. Clearly, the sequences (T_{K}) and (T′_{K}) have the same number of elements and min(T′_{K}) + max(T_{K}) = A + Bθ. Let C_{K} = T′_{K} ∪ N_{k} ∪ T_{K}. We call C_{K} a “maximal” sequence.

Lemma 10. C_{K} is a sequence of complements.

Proof. Like N_{K}, C_{K} is a contiguous sequence of complements with respect to A + Bθ. If s_{n} ∈ N_{K}, then s′_{n} ∈ N_{K}. If s_{n} ∈ T_{K} (resp. T′_{K}), then s′_{n} ∈ T′_{K} (resp. T_{K}).

Consequently, by Proposition 7, ΔC_{K} is a (maximal) palindrome.

7.5 Medial subpalindromes

For palindrome p, if p = xp′x̃ and p′ ≠ ϵ, then p′ is a medial subpalindrome of p. (The term “central factor” is also used [13, p. 2]). It is easy to see that p′ itself is a palindrome. Clearly, Δ(N_{K}) is a medial subpalindrome of Δ(C_{K}) because

Δ(C_{K}) = ΔT′_{K} ∪ Δ(N_{K}) ∪ ΔT_{K} = { \atop ΔT_{K}} ∪ Δ(N_{K}) ∪ ΔT_{K}.

(The reversal of ΔT_{K} is ΔT′_{K}.)

Let ΔM be a medial subpalindrome of Δ(C_{K}) such that

ΔN_{K} ⊆ ΔM ⊆ ΔC_{K}.  (10)

Let S_{M} = (s_{m} | 0 ≤ s_{m} ≤ max(M)). Then ΔS_{M} is a non-empty prefix of ΔS_{θ} and max(M) > 0.

Lemma 11. The palindrome ΔM is a ups of ΔS_{M}.

Proof. Clearly, ΔN_{K} is a medial subpalindrome in ΔM and ΔM is a palindromic suffix of ΔS_{M}. Therefore if ΔN_{K} is uni-occurrent in ΔS_{M} then ΔM is also. The maximal values for i and jθ in S_{M} are A and Bθ. Then ΔN_{K} is uni-occurrent in ΔS_{M} and ΔM is a ups in ΔS_{M}.

Theorem 12. Λ_{θ} is a rich word.

Proof. From (10) it follows that max(N_{K}) ≤ max(M) ≤ max(C_{K}). Then max(M) is any member of T_{K}. Furthermore, for any s_{n} > 0, there is exactly one T_{K} such that s_{n} ∈ T_{K} because max(T_{K}) < max(N_{K+1}) = min(T_{K+1}). Therefore every (non-empty) prefix of ΔS_{M} of ΔS_{θ} ends with ups ΔM. The bijection λ guarantees that Λ_{θ} is a rich word.

8 A projection of Λ_{θ} onto Γ_{θ}, a word over a three-letter alphabet

In Corollary 6, we found that any palindrome in Λ_{θ} is over a three-letter alphabet 𝒳 = {x, y, z} ⊂ 𝒜. This suggests that we may map any Lambda word onto a word with only three symbols that preserves both palindromes and non-palindromes of the Lambda word. We construct a mapping γ such that γ(W) = γ(Z). We also require γ(X) ≠ γ(Y), where, as before f(X) and f(Y) form a member of the Hurwitz chain for θ. Finally, both γ(X) and γ(Y) must be distinct from γ(Z).

\begin{matrix}A/B & λ|A − Bϑ| & γ|A − Bϑ| \\ 1/0 & 0 & 0 \\ 1/1 & 1 & 1 \\ 2/1 & 2 & 2 \\ 3/2 & 3 & 0 \\ 5/3 & 4 & 1 \\ 8/5 & 5 & 2 \\ 11/7 & 6 & 1 \\ 19/12 & 7 & 0 \\ 27/17 & 8 & 1 \\ 46/29 & 9 & 2 \\ 65/41 & 10 & 1 \\ 84/53 & 11 & 2 \end{matrix}

Figure 8: The mappings λ|A − Bϑ| and γ|A − Bϑ|.

Let A/B be a convergent of θ and let a_{k}/b_{k} be the principal convergent that immediately precedes A/B. Then the pair (A/B, a_{k}/b_{k}) forms a member of the Hurwitz chain for θ. We assign seed values to the first member of the chain (1/1, 1/0):

\begin{aligned}γ|a_{−1} − b_{−1}θ| & = & γ(1 − 0θ) & = & 0 \\ γ|a_{0} − b_{0}θ| & = & γ(−1 + 1θ) & = & 1 \end{aligned}

and then define recursively:

γ|A − Bθ| = 3 − (γ|a_{k} − b_{k}θ| + γ|(A − a_{k}) − (B − b_{k})θ|).  (11)

Because f(A/B) = f(a_{k}/b_{k}) ⊕ f ((A − a_{k})/(B − b_{k})), we can interpret (11) as γ(Z) = 3 − (γ(Y) + γ(X). We can rearrange (11) into

γ|(A − a_{k}) − (B − b_{k})θ| = 3 − (γ|A − Bθ| + γ|a_{k} − b_{k}θ|)  (12)

which may be construed as γ(W) = 3 − (γ(X) + γ(Y)). The set {γ(X), γ(Y), γ(Z)} maps bijectively onto {0, 1, 2} and so does {γ(W), γ(X), γ(Y)}. Therefore,

γ(W) + γ(X) + γ(Y) = γ(X) + γ(Y) + γ(Z) = 3.

Moreover, for a fixed (X, Y), γ(W) = γ(Z) as required. Letting ϑ = log_{2} 3, Figure 8 shows the projection of the infinite alphabet 𝒜 of Λ_{ϑ} onto {0, 1, 2}.

When θ = ϕ, the “golden” ratio, we can rewrite (11) and (12) as

γ|a_{k+1} − b_{k+1}ϕ| = 3 − (γ|a_{k} − b_{k}ϕ| + γ|a_{k−1} − b_{k−1}ϕ|) = γ|a_{k−2} − b_{k−2}|ϕ.

Because γ|a_{0} − b_{0}θ| = 1, it follows that γ|a_{k} − b_{k}ϕ| ≡ k + 1 (mod 3). That is, the successive values for γ|A − Bϕ| repeat the pattern (0, 1, 2). With any other value of θ, intermediate convergents may come between a_{k}/b_{k} and a_{k+1}/b_{k+1}. If γ|a_{k} − b_{k}θ| = n, then, under γ, the images of the intermediate convergents that follow alternate between n + 1 (mod 3) and n − 1 (mod 3). When θ is a quadratic irrational, the successive values for γ|A − Bθ| are eventually cyclic, whereas other values of θ exhibit no cyclic patterns. This, of course, reflects the patterning of partial quotients in the continued fraction expansions of these values.

The mapping γ partitions the set of convergents of θ into three classes, in contrast to the well-observed partitioning into two classes that depends on whether A/B is greater than or less than θ. The properties of this tripartite classification could warrant further investigation.

The mapping defined in (11) projects Λ_{θ} onto the Gamma word generated by θ, Γ_{θ}, a word defined over {0, 1, 2}. The table below illustrates that projection when θ = ϑ = log_{2} 3:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ Λ_{ϑ} & 0 & 1 & 2 & 1 & 2 & 3 & 2 & 2 & 3 & 2 & 3 & 4 & 3 & 2 & 3 & 4 & 3 \\ Γ_{ϑ} & 0 & 1 & 2 & 1 & 2 & 0 & 2 & 2 & 0 & 2 & 0 & 1 & 0 & 2 & 0 & 1 & 0 \\ n & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 \\ Λ_{ϑ} & 3 & 4 & 3 & 4 & 3 & 3 & 4 & 3 & 3 & 5 & 3 & 3 & 4 & 3 & 3 & 5 & 3 \\ Γ_{ϑ} & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 2 & 0 \end{matrix}

Although Γ_{θ} preserves palindromes and non-palindromes of Λ_{θ}, Γ_{θ} is itself not rich: If any factor of a word is not rich, the word itself is not rich. The first six-letter factor of Γ_{ϑ}, 012120, has no uni-occurrent palindromic suffix and is therefore not rich, a property that Γ_{ϑ} inherits. Certainly there are recurrent factors in the Gamma word but it is not known if all factors of all Gamma words are recurrent.

9 Acknowledgments

The author wishes to thank the editor and anonymous readers for their invaluable help. Thanks are also due to David Clampitt for many timely suggestions and corrections and to the other members of Micrologus, Emmanuel Amiot and Thomas Noll. Also, thanks to Srečko Brlek who provided insight into full (or rich) words at a conference at IRCAM.

References

[1] J.-P. Allouche, M. Baake, J. Cassaigne, and D. Damanik, Palindrome complexity. Theoret. Comput. Sci. 292 (2003), 9–31.

[2] S. Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, Solutions to Problem 3173. Amer. Math. Monthly 34 (1927), 159–160.

[3] J. Berstel and P. Séébold, Sturmian words, in Algebraic Combinatorics on Words, Encyc. Math. Appl., Vol. 90, Cambridge Univ. Press, 2002, pp. 45–110.

[4] J. Berstel, A. Lauve, C. Reutenauer, and F. V. Saliola, Combinatorics on Words: Christoffel Words and Repetitions in Words, CRM Monograph Series, Vol. 27, Amer. Math. Soc., 2008.

[5] A. Blondin Massé, S. Brlek, S. Labbé, and L. Vuillon, Palindromic complexity of codings of rotations, Theoret. Comput. Sci. 412 (2011), 6455–6463.

[6] S. Brlek, S. Hamel, M. Nivat, and C. Reutenauer: On the palindromic complexity of infinite words, Internat. J. Found. Comput. Sci. 15 (2004), 293–306.

[7] M. Bucci, A. de Luca, and A. De Luca, Rich and periodic-like words, in DLT 2009, Proceedings of the 13th International Conference on Developments in Language Theory, Lect. Notes in Comput. Sci., Vol. 5583, Springer, 2009, pp. 145–155.

[8] M. Bucci, A. De Luca, A. Glen, and L. Q. Zamboni, A new characteristic property of rich words, Theoret. Comput. Sci. 410 (2009), 2860–2863.

[9] N. Carey, On a class of locally symmetric sequences: The right infinite word Λ_{θ}, in Mathematics and Computation in Music, Lect. Notes in Comp. Sci., Vol. 6726, Springer, 2011, pp. 42–55.

[10] N. Carey and D. Clampitt, Regions: A theory of tonal spaces in early medieval treatises, J. Music Th. 40 (1996), 113–147.

[11] N. Carey and D. Clampitt, Two theorems concerning rational approximations, J. Math. Mus. 6 (2012), 61–66.

[12] A. Carpi and A. de Luca, Central sturmian words: Recent developments, in Developments in Language Theory, Lect. Notes in Comp. Sci., Vol. 3572, Springer, 2005, pp. 36–56.

[13] X. Droubay, J. Justin, and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001), 539–553.

[14] X. Droubay, Palindromes in the Fibonacci word, Inform. Process. Lett. 55 (1995), 217– 221.

[15] X. Droubay, and G. Pirillo, Palindromes and Sturmian words, Theoret. Comput. Sci. 223 (1999), 73–85.

[16] M. Gardner, Penrose Tiles and Trapdoor Ciphers … and the Return of Dr. Matrix, W. H. Freeman, 1989.

[17] J. Goldman, Hurwitz sequences, the Farey process, and general continued fractions, Adv. Math. 72 (1988), 239–260.

[18] A. Glen, and J. Justin, Episturmian words: a survey, RAIRO Theor. Inform. Appl. 43 (2009), 402–433.

[19] A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni, Palindromic richness, European J. Combin. 30 (2009), 510–531.

[20] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, 1994.

[21] A. Hurwitz, Über die angenäherte Darstellung der Zahlen durch rationale Brüche, Math. Ann. 44 (1894), 417–436.

[22] B. Jones, The Theory of Numbers, Holt, Rinehart, and Winston, 1955.

[23] C. Kimberling, Interspersions and dispersions, Proc. Amer. Math. Soc. 117 (1993), 313–321.

[24] C. Kimberling, Fractal sequences and interspersions, Ars Combin. 45 (1997), 157–168.

[25] C. Kimberling and J. Brown, Partial complements and transposable dispersions, J. Integer. Seq. 7 (2004), Article 04.1.6.

[26] A. Khinchin, Continued Fractions, trans. ed. by H. Eagle. Original Russian edition, 1935. Univ. Chicago Press, 1964.

[27] M. Lothaire, Algebraic Combinatorics on Words, Encyc. Math. Appl., Vol. 90, Cambridge Univ. Press, 2002.

[28] A. Luca, A. Glen, and L. Q. Zamboni, Rich, Sturmian, and trapezoidal words, Theoret. Comput. Sci. 407 (2008), 569–573.

[29] C. D. Olds, Continued Fractions, Random House, 1963.

[30] I. Richards, Continued fractions without tears, Math. Mag. 54 (1981) 163–171.

[31] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[32] M. A. Stern, Über eine zahlentheoretische Funktion. J. reine angew. Math. 55 (1858) 193–220.

2013 Mathematics Subject Classification Primary 68R15; Secondary 06F05, 11J70, 11Y55. Keywords: combinatorics on words, palindrome, rich word, continued fraction, Hurwitz chain.

(Concerned with sequences \underline{A022330}, \underline{A022331}, \underline{A167267}, \underline{A216448}, \underline{A216763}, and \underline{A216764}.)

Received September 15 2012; revised version received January 18 2013; February 17 2013. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.