On Rational Approximation of the Binary Thue-Morse-Mahler Number

Yann Bugeaud Mathématiques Université de Strasbourg 7 rue René Descartes 67084 Strasbourg France

                bugeaud@math.unistra.fr

Martine Queffélec Mathématiques Université de Lille 59655 Villeneuve d’Ascq Cédex France

            Martine.Queffelec@univ-lille1.fr

À Jean-Paul, en toute amitié

Abstract

We investigate the rational approximation of the binary Thue-Morse-Mahler number. We prove that its continued fraction expansion has infinitely many partial quotients equal to 4 or 5 and infinitely many partial quotients greater than or equal to 50.

1 Introduction and results

Let

t = t_{1}t_{2}t_{3} ⋯ = 0110100110010110100101100110100110010110 ⋯

denote the Thue-Morse word on {0, 1}, that is, the fixed point starting with 0 of the morphism τ defined by τ(0) = 01 and τ(1) = 10.

Let b ≥ 2 be an integer. In a fundamental paper, Mahler [5] established that the Thue-Morse-Mahler number

ξ_{t,b} = ∑_{k≥1} \frac{t_{k}}{b^{k}} = \frac{1}{b^{2}} + \frac{1}{b^{3}} + \frac{1}{b^{5}} + \frac{1}{b^{8}} + \frac{1}{b^{9}} + ⋯

is transcendental (see Dekking [4] for an alternative proof, reproduced in [1, Section 13.4]). Since the irrationality exponent of ξ_{t,b} is equal to 2 (see [3]), the transcendence of ξ_{t,b} cannot be proved by applying Roth’s theorem.

In the present note, we focus on the so-called Thue-Morse constant

ξ_{t} := ξ_{t,2} = 0.412454 ⋯

Allouche and Shallit [1, Open Problem 9, p. 403] asked whether ξ_{t} has bounded partial quotients. We make a small contribution to the resolution of this question by showing that the sequence of partial quotients to ξ_{t} does not increase to infinity. Observe that the fact that the irrationality exponent of ξ_{t} equals 2 prevents its sequence of partial quotients to increase too rapidly to infinity. However, there are uncountably many real numbers having irrationality exponent equal to 2 and whose sequence of partial quotients is increasing.

A computation (see e.g., [7]) shows that

ξ_{t} = [0; 2, 2, 2, 1, 4, 3, 5, 2, 1, 4, 2, 1, 5, 44, 1, 4, 1, 2, 4, 1, 1, 1, 5, 14,
1, 50, 15, 5, 1, 1, 1, 4, 2, 1, 4, 1, 43, 1, 4, 1, 2, 1, 3, 16, 1, 2, 1, 2, 1, 50, 1,
2, 424, 1, 2, 5, 2, 1, 1, 1, 5, 5, 2, 22, 5, 1, 1, 1, 1274, 3, 5, 2, 1, 1, 1, 4, 1, 1,
15, 154, 7, 2, 1, 2, 2, 1, 2, 1, 1, 50, 1, 4, 1, 2, 867374, 1, 1, 1, 5, 5, 1, 1, 6,
1, 2, 7, 2, 1650, 23, 3, 1, 1, 1, 2, 5, 3, 84, 1, 1, 1, 1284, 2, …]

and the determination of the first thousands of partial quotients of ξ_{t} suggests that it has unbounded partial quotients.

Throughout, for n ≥ 0, we denote by

F_{n} := 2^{2^{n}} + 1

the n-th Fermat number.

Our main result is the following.

Theorem 1. For any n ≥ 1 the integers F_{n} and 2^{2·2^{n}}F_{n} are denominators of convergents to ξ_{t}. The Thue-Morse constant ξ_{t} has infinitely many partial quotients equal to 4 or 5. Furthermore, there are infinitely many pairs of consecutive partial quotients both less than or equal to 5. Finally, ξ_{t} has infinitely many partial quotients greater than or equal to 50.

It follows from the fact that the integers 2^{2·2^{n}}F_{n}, n ≥ 1, are denominators of convergents to ξ_{t} that the transcendence of ξ_{t} is an immediate consequence of the p-adic extension of Roth’s theorem, established by Ridout [6]. It seems to us that this observation is new.

The proof of Theorem 1 provides us with an explicit description of infinite families of convergents to ξ_{t}, which can be used to compute very quickly the first partial quotients of the Thue-Morse constant. In particular, the continued fraction expansions of the rational numbers r_{n} (defined in (2) below) for n around 15 allow a modest computer to give the exact sequence of partial quotients of ξ_{t} beyond current tables.

We can as well consider the real numbers whose expansion in some integer base b is given by the Thue-Morse sequence. The combinatorial part remains unchanged. In particular, it follows from Ridout’s theorem that these numbers are transcendental. However, the rational approximations we construct are not good enough to be convergents.

2 Proofs

For n ≥ 0, set

ξ_{n} := ∑_{j=1}^{2^{n}} t_{j}2^{−j}, ζ_{n} := ∑_{j=1}^{2^{n}}(1 − t_{j})2^{−j} = 1 − 2^{−2^{n}} − ξ_{n}.  (1)

Furthermore, for n ≥ 1, let

r_{n} := ξ_{n}(1 + 2^{−2^{n}} + 2^{−2·2^{n}} + 2^{−3·2^{n}} + ⋯) = \frac{ξ_{n}}{1 − 2^{−2^{n}}}  (2)

be the rational number whose binary expansion is purely periodic with period t_{1}t_{2} ⋯ t_{2^{n}}.

Lemma 2. Let (k_{n})_{n≥1} be the sequence defined by k_{1} = 1 and the recurrence relation

k_{n+1} = 1 + k_{n}(2^{2^{n−1}} − 1) = 1 + k_{n}(F_{n−1} − 2),

for n ≥ 1. Then, for n ≥ 1, the rational number r_{n} defined in (2) can be written k_{n}/F_{n−1} under its reduced form.

Proof. It follows from (2) that

r_{n} = ξ_{n} \frac{2^{2^{n}}}{2^{2^{n}} − 1}, for n ≥ 1.

Since τ^{n+1}(0) = τ^{n}(0)τ^{n}(1), we get

ξ_{n+1} = ξ_{n} + \frac{ζ_{n}}{2^{2^{n}}} .

We deduce from (1) that

ξ_{n+1} = ξ_{n}(1 − \frac{1}{2^{2^{n}}} ) + \frac{2^{2^{n}} − 1}{2^{2^{n+1}}}.

We then get

r_{n+1} = r_{n} \frac{2^{2^{n}} − 1}{2^{2^{n}} + 1} + \frac{1}{2^{2^{n}} + 1} = r_{n} \frac{F_{n} − 2}{F_{n}} + \frac{1}{F_{n}} .

Since F_{n} − 2 = F_{n−1}(F_{n−1} − 2), k_{1} = 1 and r_{1} = \frac{1}{3} = \frac{k_{1}}{F_{0}} , an immediate induction gives

r_{n+1} = \frac{k_{n}(F_{n} − 2)}{F_{n}F_{n−1}} + \frac{1}{F_{n}} = \frac{k_{n+1}}{F_{n}} ,

where k_{n+1} = 1 + k_{n}(F_{n−1} − 2).

It only remains for us to prove that for n ≥ 0 the integers k_{n+1} and F_{n} are coprime. Observe that, for n ≥ 1, we have

F_{n} − 2 = F_{0}F_{1} ⋯ F_{n−1},

and gcd(F_{m}, F_{n}) = 1 when m ≠ n.

Since

k_{n+1} − 1 = k_{n}(F_{n−1} − 2)

we deduce

2k_{n+1} − F_{n} = 2k_{n}(F_{n−1} − 2) − (F_{n} − 2)
= (F_{n−1} − 2)(2k_{n} − F_{n−1})
= (F_{1} − 2) ⋯ (F_{n−1} − 2)(2k_{1} − F_{0}),

or, equivalently,

F_{n} − 2k_{n+1} = ∏_{j=1}^{n−1} F_{0}F_{1} ⋯ F_{j−1}.

If a prime number p divides simultaneously k_{n+1} and F_{n}, it must divide the product

∏_{j=1}^{n−1} F_{0}F_{1} ⋯ F_{j−1}.

This gives a contradiction, since F_{n} is coprime with the latter product. Consequently, k_{n+1} and F_{n} have no common prime divisor. This finishes the proof of the lemma.

Lemma 3. For n ≥ 2, the rational number r_{n} defined in (2) is a convergent to ξ_{t}.

Proof. For n ≥ 1, set π_{n} = ∑_{j=1}^{2^{n}} \frac{ε_{j}}{2^{j}}, where (ε_{j})_{j≥1} is the Thue-Morse sequence on \{±1\} beginning with 1. A classical computation shows that

π_{n} = \frac{1}{2} ∏_{j=0}^{n−1}(1 − \frac{1}{2^{2^{j}}} )

and we check that 0.175 < π_{n} < 0.1751 if n ≥ 4. Writing the sequences of digits of ξ_{t} and r_{n} as a concatenation of blocks of length 2^{n} from {τ^{n}(0), τ^{n}(1)}, we get

τ^{n}(0)τ^{n}(1)τ^{n}(1)τ^{n}(0) ⋯

and

τ^{n}(0)τ^{n}(0)τ^{n}(0)τ^{n}(0) ⋯,

respectively. Thus,

ξ_{t} − r_{n} = 0 + \frac{π_{n}}{2^{2^{n}}} + \frac{π_{n}}{2^{2^{n+1}}} + 0 + ⋯

This gives

0.175(\frac{1}{2^{2^{n}}} + \frac{1}{2^{2^{n+1}}} ) ≤ ξ_{t} − r_{n}
≤ 0.1751(\frac{1}{2^{2^{n}}} + \frac{1}{2^{2^{n+1}}} + ⋯)
≤ 0.1751\frac{1}{2^{2^{n}}} (1 + \frac{1}{2^{2^{n}}} + \frac{1}{2^{2.2^{n}}} + ⋯)
≤ 0.1751\frac{1}{2^{2^{n}} − 1}.  (3)

In particular, we get

0 < ξ_{t} − r_{n} < \frac{1}{2F_{n−1}^{2}} , for n ≥ 4.

The Legendre theorem (see e.g., [2]) then implies that r_{n} is a convergent to ξ_{t} for n ≥ 4. We further check that r_{2} and r_{3} are convergents to ξ_{t}.

Lemma 4. For every n ≥ 1, the integer 2^{2·2^{n}}F_{n} is the denominator of a convergent to ξ_{t}.

Proof. For n ≥ 1, we consider the rational number R_{n} whose binary expansion has preperiod τ^{n}(0) and period τ^{n}(1). Clearly,

R_{n} = ξ_{n} + \frac{1}{2^{2^{n}}} (1 − r_{n})

and, by (2),

R_{n} = r_{n} \frac{2^{2^{n}} − 2}{2^{2^{n}}} + \frac{1}{2^{2^{n}}} .

Since, by Lemma 2

r_{n} = \frac{k_{n}}{F_{n−1}} with (k_{n}, F_{n−1}) = 1,

we finally get that

R_{n} = k_{n} \frac{2^{2^{n}} − 2}{2^{2^{n}}F_{n−1}} + \frac{1}{2^{2^{n}}} = \frac{F_{n−1} + k_{n}(2^{2^{n}} − 2)}{2^{2^{n}}F_{n−1}}

is under its reduced form.

It remains to estimate the gap between ξ_{t} and R_{n}. Arguing as in the proof of Lemma 3, we see that

\frac{π_{n}}{2^{3·2^{n}}} < R_{n} − ξ_{t} < π_{n}(\frac{1}{2^{3·2^{n}}} + \frac{1}{2^{4·2^{n}}} + ⋯) = \frac{π_{n}}{2^{3·2^{n}}} (1 + \frac{1}{2^{2^{n}}} + ⋯)

= \frac{π_{n}}{2^{3·2^{n}}} (\frac{2^{2^{n}}}{2^{2^{n}} − 1}) = \frac{π_{n}}{2^{4·2^{n−1}}(2^{2^{n−1}} − 1)F_{n−1}}

≤ \frac{1}{2(2^{2·2^{n−1}}F_{n−1})^{2}} , for n ≥ 4.

The lemma then follows from Legendre’s theorem and the simple verification that R_{1}, R_{2} and R_{3} are convergents to ξ_{t}.

Lemma 5. For n ≥ 1, let c_{n}/(2^{3·2^{n}} − 1) be the rational number whose binary expansion is purely periodic of period τ^{n}(0)τ^{n}(1)τ^{n}(1). Then, for n ≥ 3, its numerator and its denominator are both divisible by 3 × (2^{2^{n−1}} − 1).

Proof. Let w_{0}w_{1} ⋯ w_{3·2^{n}−1} denote τ^{n}(110) if n is even and τ^{n}(001) if n is odd. Then, we check that

c_{n} = ∑_{j=0}^{3·2^{n}−1} w_{j}2^{j}.

Let A_{n} = ∑_{j=1}^{2^{n}} t_{j}2^{j−1} and B_{n} = ∑_{j=1}^{2^{n}}(1 − t_{j})2^{j−1} be the integers associated to τ^{n}(0) and τ^{n}(1), respectively. Since

A_{n} + B_{n} = 2^{2^{n}} − 1, B_{n} − A_{n} = ∏_{j=0}^{n−1}(2^{2^{j}} − 1) =: T_{n},  (4)

we deduce that

c_{n} = B_{n} + 2^{2^{n}}B_{n} + 2^{2·2^{n}}A_{n} or A_{n} + 2^{2^{n}}A_{n} + 2^{2·2^{n}}B_{n},  (5)

depending on the parity of n.

Clearly, 2^{2^{n−1}} − 1 divides 2^{2^{n}} − 1 and 2^{3·2^{n}} − 1. As it divides also T_{n}, it divides A_{n} and B_{n} and thus c_{n}.

Furthermore, for n ≥ 1, we have

2^{2^{n}} ≡ 4 (mod 9), if n is odd  (6)

and

2^{2^{n}} ≡ 7 (mod 9), if n is even.  (7)

It then follows from Eqs. (4) to (7) that 9 divides c_{n} for n ≥ 3. Since 9 also divides 2^{3·2^{n}} − 1 for n ≥ 2, this proves the lemma.

For n ≥ 1, let p′_{n}/q′_{n} denote the rational number c_{n}/(2^{3·2^{n}} − 1) written in its lowest form. The lemma asserts that q′_{n} divides (2^{3·2^{n}} − 1)/(3 × (2^{2^{n−1}} − 1)). For later use, we observe that

\frac{π_{n}}{2^{5·2^{n}}} < \frac{c_{n}}{2^{3·2^{n}} − 1} − ξ_{t} < \frac{π_{n}}{2^{5·2^{n}}} · \frac{2^{2^{n}}}{2^{2^{n}} − 1},

and, since

q′_{n} ≤ \frac{2^{3·2^{n}} − 1}{3(2^{2^{n−1}} − 1)} ≤ \frac{2^{5·2^{n−1}}}{3} · \frac{2^{2^{n−1}}}{2^{2^{n−1}} − 1},

we deduce that

0 < \frac{p′_{n}}{q′_{n}} − ξ_{t} < \frac{π_{n}}{(3q′_{n})^{2}} · \frac{2^{2^{n}}}{2^{2^{n}} − 1} · \frac{2^{2^{n}}}{(2^{2^{n−1}} − 1)^{2}} ,  (8)

for n ≥ 3.

We can now prove Theorem 1.

Proof of Theorem 1. The combination of Lemmas 2 to 4 establishes the first assertion of Theorem 1. Recall that (see e.g., [2]), for ℓ ≥ 1, we have

|q_{ℓ}ξ_{t} − p_{ℓ}| = \frac{1}{q_{ℓ}} · \frac{1}{[a_{ℓ+1}; a_{ℓ+2}, …] + [0; a_{ℓ}, a_{ℓ−1}, …]},  (9)

where (p_{ℓ}/q_{ℓ})_{ℓ≥0} denotes the sequence of convergents to ξ_{t}. By (3) and (9), there exist arbitrarily large integers ℓ such that

[a_{ℓ+1}; a_{ℓ+2}, …] + [0; a_{ℓ}, a_{ℓ−1}, …] ≐ 1/0.175 ≐ 5.71.  (10)

Let ℓ be a positive integer for which (10) holds. If a_{ℓ} ≥ 2, then a_{ℓ+1} must be equal to 5 and a_{ℓ+2} is at most 4. If a_{ℓ} = 1, then a_{ℓ+1} equals 4 or 5.

Finally, we use Eqs. (3), (9), Lemma 5, and Eq. (8) to deduce that there exist arbitrarily large integers ℓ such that

[a_{ℓ+1}; a_{ℓ+2}, …] + [0; a_{ℓ}, a_{ℓ−1}, …] ≥ 3^{2}/0.1751 ≥ 51.3.

This implies that infinitely many partial quotients are at least equal to 50. This concludes the proof of the theorem.

3 Acknowledgments

We are grateful to the referee for numerous comments, including the suggestion to study the rational numbers introduced in Lemma 5.

References

[1] J.-P. Allouche and J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.

[2] Y. Bugeaud, Approximation By Algebraic Numbers. Cambridge Tracts in Mathematics 160, Cambridge University Press, 2004.

[3] Y. Bugeaud. On the irrationality exponent of the Thue-Morse-Mahler numbers, Ann. Institut Fourier (Grenoble) 61 (2011), 2065–2076.

[4] F. M. Dekking, Transcendance du nombre de Thue-Morse, C. R. Acad. Sci. Paris Sér. I Math. 285 (1977), 157–160.

[5] K. Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen, Math. Ann. 101 (1929), 342–366. Corrigendum 103 (1930), 532.

[6] D. Ridout, Rational approximations to algebraic numbers, Mathematika 4 (1957), 125– 131.

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

2010 Mathematics Subject Classification: Primary 11J04. Keywords: Continued fraction, Thue-Morse constant, Fermat number.

(Concerned with sequences \underline{A004249}, \underline{A010060}, and \underline{A014572}.)

Received April 20 2012; revised version received June 6 2012. Published in Journal of Integer Sequences, March 2 2013.

Return to Journal of Integer Sequences home page.