Characteristic Words as Fixed Points of Homomorphisms

Jeffrey Shallit Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1 Canada

                      shallit@watdragon.waterloo.edu

Abstract.

With each real number θ, 0 < θ < 1, we can associate the so-called characteristic word w = w(θ), defined by

w_{n} = ⌊(n + 1)θ⌋ − ⌊nθ⌋,

for n ≥ 1. We prove the following: if θ has a purely periodic continued fraction expansion, then w(θ) is a fixed point of a certain homomorphism φ = φ_{θ}.

I. Introduction.

Let θ be a real number, 0 < θ < 1. Many authors have studied the so-called characteristic word w = w(θ), the infinite word of 0’s and 1’s defined by

w_{n} = ⌊(n + 1)θ⌋ − ⌊nθ⌋  (1)

for n ≥ 1. See, for example, Bernoulli [1772], Markoff [1882], Venkov [1970, pp. 65-68], Stolarsky [1976], Fraenkel, Mushkin, and Tassa [1978], and Porta and Stolarsky [1990]. An extensive bibliography of papers on the subject can be assembled by consulting the references of the last three papers.

For example, if θ = \frac{1}{2}(\sqrt{5} − 1), we find
w = w_{1}w_{2}w_{3} ⋯ = 1011010110 ⋯,  (2)

the so-called Fibonacci word.

It is well-known that the Fibonacci word is the unique fixed point of the homomorphism φ, where φ(0) = 1, φ(1) = 10. For this and other properties see, for example, Berstel [1986].

In this note we generalize this characterization (fixed point of a homomorphism) of the Fibonacci word to the case where θ has a purely periodic continued fraction expansion, i.e. when

θ = [0, a_{1}, a_{2}, …, a_{r}, a_{1}, a_{2}, …, a_{r}, a_{1}, a_{2}, …, a_{r}, …].

We refer to the number r as the period length of θ.

II. The Main Result.

First, we introduce some notation. Let θ be an irrational number, 0 < θ < 1. Write

θ = [0, a_{1}, a_{2}, a_{3}, …].

We define

\frac{p_{n}}{q_{n}} = [0, a_{1}, a_{2}, …, a_{n}].

Note that q_{0} = 1, q_{1} = a_{1}, and for n ≥ 2 we have

q_{n} = a_{n}q_{n−1} + q_{n−2}.  (3)

Let w = w(θ) be the characteristic word of θ as defined in (1) above.

We now define a sequence of strings (X_{i})_{i≥0}. We set X_{0} = 0, a string of length 1, and

X_{i} = w_{1}w_{2}w_{3} ⋯ w_{q_{i}}

for i ≥ 1. Thus for i ≥ 1, X_{i} consists of the first q_{i} symbols in the infinite word w. It is easy to see that X_{1} = 0^{a_{1}−1}1.

The following result essentially appears in the paper of Fraenkel, Mushkin and Tassa [1978]. Since it is crucial to our proof, and since it does not seem to have been explicitly stated before, we give it the status of a lemma:

Lemma 1.

For i ≥ 2 we have

X_{i} = X_{i−1}^{a_{i}}X_{i−2}.

Proof.

Let us borrow a notation from the programming language APL. If x = x_{1}x_{2} ⋯ x_{s} is a finite string, and n is a non-negative integer, we define

nρx = x^{q}x_{1}x_{2} ⋯ x_{r},

where n = qs + r, 0 ≤ r < s. (In other words, the elements of x are used cyclically to fill in a string of length n.)

Fraenkel, Mushkin, and Tassa [1978] proved that

X_{i} = q_{i}ρX_{i−1}

for i ≥ 2, if a_{1} > 1, and for i ≥ 3 if a_{1} = 1.

From this, the lemma follows immediately, since by (3) we have q_{i} = a_{i}q_{i−1} + q_{i−2} for i ≥ 2, and X_{i−2} is a prefix of X_{i−1} (for i ≥ 2 if a_{1} > 1 and for i ≥ 3 if a_{1} = 1).

We can now state the main result:

Theorem 2.

Let θ have a purely periodic continued fraction expansion; i.e.

θ = [0, a_{1}, a_{2}, …, a_{r}, a_{1}, a_{2}, …, a_{r}, a_{1}, a_{2}, …, a_{r}, …].

Define the homomorphism φ by φ(0) = X_{r}, φ(1) = X_{r}X_{r−1}. Then

φ^{n}(X_{i}) = X_{rn+i}

for all integers i, n ≥ 0.

Proof.

By induction on rn + i.

If rn + i = 0, then n = 0 and i = 0. Clearly φ^{0}(X_{0}) = X_{0}.

If rn + i = 1, then either n = 0, i = 1, or r = 1, n = 1, and i = 0. In the former case we have φ^{0}(X_{1}) = X_{1}. In the latter case we have φ(X_{0}) = φ(0) = X_{1} by definition of φ.

Now assume the result is true for all n′, i′ with rn′ + i′ < s, and s ≥ 2. We prove it for rn + i = s.

Case I: i ≥ 2. We find

φ^{n}(X_{i}) = φ^{n}(X_{i−1}^{a_{i}}X_{i−2}) (by Lemma 1)
= φ^{n}(X_{i−1}^{a_{i}})φ^{n}(X_{i−2})
= φ^{n}(X_{i−1})^{a_{i}}φ^{n}(X_{i−2})
= X_{rn+i−1}^{a_{i}}X_{rn+i−2} (by induction)
= X_{rn+i} (by Lemma 1).

Case II: i = 1, n ≥ 1. We find

φ^{n}(X_{1}) = φ^{n−1}(φ(X_{1}))

= φ^{n−1}(φ(0^{a_{1}−1}1)) = φ^{n−1}(φ(0)^{a_{1}−1}φ(1)) = φ^{n−1}(X_{r}^{a_{1}−1}X_{r}X_{r−1}) = φ^{n−1}(X_{r}^{a_{1}}X_{r−1}) = φ^{n−1}(X_{r})^{a_{1}}φ^{n−1}(X_{r−1}) = X_{rn}^{a_{1}}X_{rn−1} (by induction) = X_{rn+1} (by Lemma 1).

Case III: i = 0, n ≥ 1, r ≥ 2. We find

φ^{n}(X_{0}) = φ^{n−1}(φ(X_{0}))

= φ^{n−1}(X_{r}) = φ^{n−1}(X_{r−1}^{a_{r}}X_{r−2}) (by Lemma 1) = φ^{n−1}(X_{r−1})^{a_{r}}φ^{n−1}(X_{r−2}) = X_{rn−1}^{a_{r}}X_{rn−2} (by induction) = X_{rn} (by Lemma 1).

Case IV: i = 0, n ≥ 2, r = 1. We find

φ^{n}(X_{0}) = φ^{n−2}(φ^{2}(X_{0}))

= φ^{n−2}(φ(X_{1})) = φ^{n−2}(φ(0^{a_{1}−1}1)) = φ^{n−2}(X_{1})^{a_{1}−1}φ^{n−2}(X_{1}X_{0}) = X_{n−1}^{a_{1}−1}X_{n−1}X_{n−2} (by induction) = X_{n} (by Lemma 1).

This completes the proof. Since in particular X_{rn} = φ^{n}(X_{0}), we find

Corollary 3.

The infinite word w is a fixed point of the homomorphism φ defined above.

III. Some examples.

Example 1.

Let θ = [0, a, a, a, …] = \frac{1}{2}(\sqrt{a^{2} + 4} − a). Thus r = 1; we find p_{1}/q_{1} = 1/a. Then we find X_{0} = 0 and X_{1} = 0^{a−1}1. Thus w(θ) is a fixed point of the homomorphism φ, where φ(0) = 0^{a−1}1, φ(1) = 0^{a−1}10. For a = 1 this gives the classical Fibonacci word, mentioned in Section I.

Note that φ satisfies the equation

φ^{2}(0) = φ(0)^{a}0,

and so is an “algebraic” homomorphism; see Shallit [1988].

Example 2.

Let θ = [0, a, b, a, b, …] = (\sqrt{ab(ab + 4)} − ab)/2a. Thus r = 2; we find p_{1}/q_{1} = 1/a and p_{2}/q_{2} = b/(ab + 1). Thus X_{0} = 0, X_{1} = 0^{a−1}1, and X_{2} = (0^{a−1}1)^{b}0. From this, we see that w(θ) is a fixed point of the homomorphism φ, where φ(0) = (0^{a−1}1)^{b}0, φ(1) = (0^{a−1}1)^{b}0^{a}1.

References

Bernoulli [1772]

J. Bernoulli, Recueil pour les Astronomes, Volume I, Sur une nouvelle espece de calcul, Berlin, 1772, pp. 255-284.

Berstel [1986]

J. Berstel, Fibonacci words–a survey, in The Book of L, G. Rozenberg and A. Salomaa, eds., Springer-Verlag, 1986, pp. 13–27.

Fraenkel, Mushkin, and Tassa [1978]

A. S. Fraenkel, M. Mushkin, and U. Tassa, Determination of [nθ] by its sequence of differences, Canad. Math. Bull. 21 (1978), 441–446.

Markoff [1882] A. A. Markoff, Sur une question de Jean Bernoulli, Math. Ann. 19 (1882), 27–36.

Porta and Stolarsky [1990]

H. Porta and K. B. Stolarsky, Half-silvered mirrors and Wythoff’s game, Canad. Math. Bull. 33 (1990), 119–125.

Shallit [1988] J. Shallit, A generalization of automatic sequences, Theor. Comput. Sci. 61 (1988), 1–16.

Stolarsky [1976]

K. B. Stolarsky, Beatty sequences, continued fractions, and certain shift operators, Canad. Math. Bull. 19 (1976), 473–482.

Venkov [1970] B. A. Venkov, Elementary Number Theory, Wolters-Noordhoff, Groningen, 1970.

First version: December 30, 1990

Last revised: January 3, 1991

Postscript. (December 13 1991)

In what must be one of the more remarkable instances of simultaneous discovery of the same theorem, after this manuscript was completed, I learned from J.-P. Allouche of the work of T. C. Brown [1990] and J.-P. Borel and F. Laubie [1990]. These papers contain essentially the same result as I reported above in Theorem 2, and more. (However, I believe my proof of Theorem 2 to be simpler than Brown’s.)

Furthemore, Allouche later discovered the paper of Ito and Yasutomi [1990], in which the same result appears. Then, in April 1991, at the “Thémate” Conference, I was given a preprint of Nishioka, Shiokawa, and Tamura [1991], in which the result appears once again!

In May 1991, in conversations with A. D. Pollington, I learned that some of these results can be found, in a somewhat concealed fashion, in a little-known paper of Cohn [1974]. Pollington himself has a paper [1991] on this topic!

I also discovered that Lemma 1 essentially already appeared in an little-known paper of H. J. S. Smith [1876].

Finally, Theorem 2 can be used to greatly simplify the proof of one direction of a beautiful theorem of F. Mignosi [1989].

Additional References

Borel and Laubie [1991]

J.-P. Borel and F. Laubie, Construction de mots de Christofell [sic], to appear, C. R. Acad. Sci. Paris, 1991.

Brown [1991]

T. Brown, A characterization of the quadratic irrationals, to appear, Canad. Math. Bull., 1991.

Cohn [1974]

H. Cohn, Some direct limits of primitive homotopy words and of Markoff geodesics, in Discontinuous Groups and Riemann Surfaces, Ann. of Math. Studies 79, Princeton University Press, 1974, pp. 81-98.

Ito and Yasutomi [1990]

S. Ito and S. Yasutomi, On continued fractions, substitutions and characteristic sequences [nx + y] − [(n − 1)x + y], Japan J. Math. 16 (1990), 287-306.

Mignosi [1989]

F. Mignosi, Infinite words with linear subword complexity, Theoret. Comput. Sci. 65 (1989), 221-242.

Nishioka, Shiokawa, and Tamura [1991]

K. Nishioka, I. Shiokawa, and J. Tamura, Arithmetical properties of a certain power series, manuscript, April (?) 1991.

Pollington [1991] A. D. Pollington, Substitution Invariant Cutting Sequences, manuscript, October 1991.

Smith [1876] H. J. S. Smith, Note on continued fractions, Messenger of Math. 6 (1876), 1-14.