\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On Rational Approximation of the \\ \vskip .1in Binary Thue-Morse-Mahler Number } \vskip 1cm \large Yann Bugeaud\\ Math\'ematiques\\ Universit\'e de Strasbourg\\ 7 rue Ren\'e Descartes \\ 67084 Strasbourg\\ France\\ \href{mailto:bugeaud@math.unistra.fr}{\tt bugeaud@math.unistra.fr}\\ \ \\ Martine Queff\'elec\\ Math\'ematiques\\ Universit\'e de Lille\\ 59655 Villeneuve d'Ascq C\'edex\\ France\\ \href{mailto:Martine.Queffelec@univ-lille1.fr}{\tt Martine.Queffelec@univ-lille1.fr} \end{center} \vskip .2 in \centerline{\it \`A Jean-Paul, en toute amiti\'e} \begin{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$. \end{abstract} \section{Introduction and results} Let $$ {\bf t} = t_1 t_2 t_3 \cdots = 0110100110010110100101100110100110010110 \cdots $$ denote the Thue-Morse word on $\{0, 1\}$, that is, the fixed point starting with $0$ of the morphism $\tau$ defined by $\tau(0) = 01$ and $\tau(1) = 10$. Let $b \ge 2$ be an integer. In a fundamental paper, Mahler \cite{Mah29} established that the Thue-Morse-Mahler number $$ \xi_{{\bf t}, b} = \sum_{k \ge 1} \, {t_{k} \over b^{k}} = {1 \over b^2} + {1 \over b^3} + {1 \over b^5} + {1 \over b^8} + {1 \over b^{9}} + \cdots $$ is transcendental (see Dekking \cite{De77} for an alternative proof, reproduced in \cite[Section 13.4]{AlSh03}). Since the irrationality exponent of $\xi_{{\bf t}, b}$ is equal to $2$ (see \cite{Bu11}), the transcendence of $\xi_{{\bf t}, b}$ cannot be proved by applying Roth's theorem. In the present note, we focus on the so-called Thue-Morse constant $$ \xi_{\bf t} := \xi_{{\bf t}, 2} = 0.412454 \cdots $$ Allouche and Shallit \cite[Open Problem 9, p.\ 403]{AlSh03} asked whether $\xi_{\bf 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 $\xi_{\bf t}$ does not increase to infinity. Observe that the fact that the irrationality exponent of $\xi_{\bf 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., \cite{Sloa}) shows that $$ \begin{array}{lll} \xi_{\bf 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,\ldots] \\ \end{array} $$ and the determination of the first thousands of partial quotients of $\xi_{\bf t}$ suggests that it has unbounded partial quotients. Throughout, for $n \ge 0$, we denote by $$ {\mathcal F}_n := 2^{2^n} + 1 $$ the $n$-th Fermat number. Our main result is the following. \begin{theorem} For any $n \ge 1$ the integers ${\mathcal F}_n$ and $2^{2 \cdot 2^n} {\mathcal F}_n$ are denominators of convergents to $\xi_{\bf t}$. The Thue-Morse constant $\xi_{\bf 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, $\xi_{\bf t}$ has infinitely many partial quotients greater than or equal to $50$. \label{theorem1} \end{theorem} It follows from the fact that the integers $2^{2 \cdot 2^n} {\mathcal F}_n$, $n \ge 1$, are denominators of convergents to $\xi_{\bf t}$ that the transcendence of $\xi_{\bf t}$ is an immediate consequence of the $p$-adic extension of Roth's theorem, established by Ridout \cite{Rid57}. It seems to us that this observation is new. The proof of Theorem~\ref{theorem1} provides us with an explicit description of infinite families of convergents to $\xi_{\bf 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 (\ref{2.2}) below) for $n$ around $15$ allow a modest computer to give the exact sequence of partial quotients of $\xi_{\bf 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. % apply Legendre's result. They are only intermediate convergents. %And I don't see how to get some information on the size of the partial quotients, %even using Worley's theorem. \section{Proofs} For $n \ge 0$, set \begin{equation} \xi_n := \sum_{j=1}^{2^n} t_j 2^{-j}, \quad \zeta_n := \sum_{j=1}^{2^n} (1-t_j) 2^{-j} = 1 - 2^{-2^n} - \xi_n. \label{2.1} \end{equation} Furthermore, for $n \ge 1$, let \begin{equation} r_n := \xi_n (1 + 2^{-2^n} + 2^{-2 \cdot 2^n} + 2^{-3 \cdot 2^n} + \cdots) = {\xi_n \over 1 - 2^{-2^n}} \label{2.2} \end{equation} be the rational number whose binary expansion is purely periodic with period $t_1 t_2 \cdots t_{2^n}$. \begin{lemma} Let $(k_n)_{n \ge 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({\mathcal F}_{n-1}-2), $$ for $n \ge 1$. Then, for $n \ge 1$, the rational number $r_n$ defined in (\ref{2.2}) can be written ${k_n / {\mathcal F}_{n-1}}$ under its reduced form. \label{lemma1} \end{lemma} \begin{proof} It follows from (\ref{2.2}) that $$ r_n= \xi_n \, {2^{2^n}\over2^{2^n}-1}, \quad \hbox{for $n \ge 1$}. $$ Since $\tau^{n+1}(0)=\tau^n(0) \tau^n(1)$, we get $$ \xi_{n+1}=\xi_n+ {\zeta_n \over 2^{2^n}}. $$ We deduce from (\ref{2.1}) that $$ \xi_{n+1}=\xi_n \Bigl(1-{1\over2^{2^n}} \Bigr)+{2^{2^n}-1\over2^{2^{n+1}}}. $$ We then get $$ r_{n+1}=r_n{2^{2^n}-1\over2^{2^n}+1}+{1\over2^{2^n}+1} =r_n{{\mathcal F}_n-2\over {\mathcal F}_n}+{1\over {\mathcal F}_n}. $$ Since ${\mathcal F}_n-2={\mathcal F}_{n-1}({\mathcal F}_{n-1}-2)$, $k_1= 1$ and $r_1={1 \over3}={k_1\over {\mathcal F}_0}$, an immediate induction gives $$ r_{n+1}={k_n({\mathcal F}_n-2)\over {\mathcal F}_n{\mathcal F}_{n-1}} +{1\over {\mathcal F}_n}={k_{n+1}\over {\mathcal F}_n}, $$ where $k_{n+1}=1+k_n({{\mathcal F}_{n-1}}-2)$. It only remains for us to prove that for $n \ge 0$ the integers $k_{n+1}$ and ${\mathcal F}_n$ are coprime. Observe that, for $n\geq1$, we have $$ {\mathcal F}_n-2={\mathcal F}_0{\mathcal F}_1\cdots {\mathcal F}_{n-1}, $$ and $\gcd ({\mathcal F}_m,{\mathcal F}_n)=1$ when $m\not=n$. Since $$ k_{n+1}-1= k_n({\mathcal F}_{n-1}-2) $$ we deduce $$ \begin{array}{lll} 2k_{n+1}-{\mathcal F}_n&=&2k_n({\mathcal F}_{n-1}-2)-({\mathcal F}_n-2)\\ &=& ({\mathcal F}_{n-1}-2) (2k_n-{\mathcal F}_{n-1})\\ &=&({\mathcal F}_1-2)\cdots ({\mathcal F}_{n-1}-2)(2k_1-{\mathcal F}_0), \end{array} $$ or, equivalently, $$ {\mathcal F}_n-2k_{n+1} =\prod_{j=1}^{n-1} {\mathcal F}_0{\mathcal F}_1\cdots {\mathcal F}_{j-1}. $$ If a prime number $p$ divides simultaneously $k_{n+1}$ and ${\mathcal F}_n$, it must divide the product $$\prod_{j=1}^{n-1} {\mathcal F}_0{\mathcal F}_1\cdots {\mathcal F}_{j-1}.$$ This gives a contradiction, since ${\mathcal F}_n$ is coprime with the latter product. Consequently, $k_{n+1}$ and ${\mathcal F}_n$ have no common prime divisor. This finishes the proof of the lemma. \end{proof} \begin{lemma} For $n \ge 2$, the rational number $r_n$ defined in (\ref{2.2}) is a convergent to $\xi_{\bf t}$. \label{lemma2} \end{lemma} \begin{proof} For $n \ge 1$, set $\pi_n=\sum_{j=1}^{2^n}{\varepsilon_j\over 2^j}$, where $(\varepsilon_j)_{j \ge 1}$ is the Thue-Morse sequence on $\{\pm1\}$ beginning with $1$. A classical computation shows that $$ \pi_n={1\over2} \, \prod_{j=0}^{n-1} \Bigl(1-{1\over 2^{2^j}} \Bigr) $$ and we check that $0.175 < \pi_n < 0.1751$ if $n\geq 4$. Writing the sequences of digits of $\xi_{\bf t}$ and $r_n$ as a concatenation of blocks of length $2^n$ from $\{\tau^n(0),\tau^n(1)\}$, we get $$ \tau^n(0)\tau^n(1)\tau^n(1) \tau^n(0)\cdots $$ and $$ \tau^n(0)\tau^n(0)\tau^n(0) \tau^n(0)\cdots , $$ respectively. Thus, $$ \xi_{\bf t}-r_n=0+{\pi_n \over2^{2^n}} + {\pi_n \over2^{2^{n+1}}} +0+\cdots $$ This gives \begin{eqnarray} 0.175 ({1\over2^{2^n}}+{1\over2^{2^{n+1}}}) &\le& \xi_{\bf t}-r_n \nonumber\\ &\leq& 0.1751({1\over2^{2^n}}+{1\over2^{2^{n+1}}}+\cdots) \nonumber\\ &\leq& 0.1751 {1\over2^{2^n}}(1+{1\over2^{2^n}}+{1\over2^{2.2^n}}+\cdots) \nonumber\\ &\leq& 0.1751 {1\over2^{2^n}-1}. \label{2.3} \end{eqnarray} In particular, we get $$ 0 < \xi_{\bf t}-r_n <{1\over 2 {\mathcal F}^2_{n-1}}, \quad \mbox{for $n\geq 4$.} $$ The Legendre theorem (see e.g., \cite{BuLiv}) then implies that $r_n$ is a convergent to $\xi_{\bf t}$ for $n \ge 4$. We further check that $r_2$ and $r_3$ are convergents to $\xi_{\bf t}$. \end{proof} \begin{lemma} For every $n \ge 1$, the integer $2^{2 \cdot 2^n}{\mathcal F}_n$ is the denominator of a convergent to $\xi_{\bf t}$. \label{lemma3} \end{lemma} \begin{proof} For $n \ge 1$, we consider the rational number $R_n$ whose binary expansion has preperiod $\tau^n(0)$ and period $\tau^n(1)$. Clearly, $$ R_n=\xi_n+{1\over 2^{2^n}}(1-r_n) $$ and, by (\ref{2.2}), $$ R_n=r_n{2^{2^n}-2\over 2^{2^n}}+{1\over2^{2^n}}. $$ Since, by Lemma~\ref{lemma1} $$ r_n={k_n\over {\mathcal F}_{n-1}}\ \ {\rm with}\ (k_n,{\mathcal F}_{n-1})=1, $$ we finally get that $$ R_n=k_n{2^{2^n}-2\over 2^{2^n}{\mathcal F}_{n-1}}+{1\over2^{2^n}} ={{\mathcal F}_{n-1}+k_n(2^{2^n}-2) \over 2^{2^n}{\mathcal F}_{n-1}} $$ is under its reduced form. It remains to estimate the gap between $\xi_{\bf t}$ and $R_n$. Arguing as in the proof of Lemma~\ref{lemma2}, we see that $$ {\pi_n \over 2^{3\cdot2^n}} < R_n - \xi_{\bf t} < \pi_n({1\over2^{3\cdot2^n}}+{1\over2^{4\cdot2^n}}+\cdots) ={\pi_n\over2^{3\cdot2^n}}(1+{1\over 2^{2^n}}+\cdots) $$ $$ ={\pi_n\over2^{3\cdot2^n}}({2^{2^n}\over 2^{2^n}-1}) ={\pi_n\over2^{4\cdot2^{n-1}}(2^{2^{n-1}}-1){\mathcal F}_{n-1}} $$ $$ \le {1\over2(2^{2\cdot2^{n-1}}{\mathcal F}_{n-1})^2}, \ \ \hbox{for}\ n\ge 4. $$ The lemma then follows from Legendre's theorem and the simple verification that $R_1, R_2$ and $R_3$ are convergents to $\xi_{\bf t}$. \end{proof} \begin{lemma} For $n \ge 1$, let $c_n/ (2^{3 \cdot 2^n} - 1)$ be the rational number whose binary expansion is purely periodic of period $\tau^n (0) \tau^n (1) \tau^n (1)$. Then, for $n \ge 3$, its numerator and its denominator are both divisible by $3 \times (2^{2^{n-1}}-1)$. \label{lemma4} \end{lemma} \begin{proof} Let $w_0w_1\cdots w_{{3 \cdot 2^n} - 1}$ denote $\tau^n(110)$ if $n$ is even and $\tau^n(001)$ if $n$ is odd. Then, we check that $$ c_n=\sum_{j=0}^{{3 \cdot 2^n} - 1} w_j2^{j}. $$ Let $A_n=\sum_{j=1}^{2^n} t_j2^{j-1}$ and $B_n=\sum_{j=1}^{2^n} (1-t_j)2^{j-1}$ be the integers associated to $\tau^n (0)$ and $\tau^n(1)$, respectively. Since \begin{equation} A_n+B_n=2^{2^n}-1,\ \ B_n-A_n=\prod_{j=0}^{n-1}(2^{2^j}-1)=:T_n, \label{2.4} \end{equation} we deduce that \begin{equation} c_n=B_n+2^{2^n}B_n+2^{2\cdot2^n}A_n \quad \hbox{or} \quad A_n+2^{2^n}A_n+2^{2\cdot2^n}B_n, \label{2.5} \end{equation} depending on the parity of $n$. Clearly, $2^{2^{n-1}}- 1$ divides $2^{2^n}-1$ and $2^{3 \cdot 2^n} - 1$. As it divides also $T_n$, it divides $A_n$ and $B_n$ and thus $c_n$. Furthermore, for $n\ge 1$, we have \begin{equation} 2^{2^n}\equiv 4 \ \ (\bmod \, 9), \quad \hbox{if $n$ is odd} \label{2.6} \end{equation} and \begin{equation} 2^{2^n}\equiv 7 \ \ (\bmod \, 9), \quad \hbox{if $n$ is even.} \label{2.7} \end{equation} It then follows from Eqs.\ (\ref{2.4}) to (\ref{2.7}) that $9$ divides $c_n$ for $n \ge 3$. Since $9$ also divides $2^{3 \cdot 2^n} - 1$ for $n \ge 2$, this proves the lemma. For $n \ge 1$, let $p'_n/q'_n$ denote the rational number $c_n / (2^{3 \cdot 2^n} - 1)$ written in its lowest form. The lemma asserts that $q'_n$ divides $(2^{3 \cdot 2^n} - 1) / (3 \times (2^{2^{n-1}}-1))$. For later use, we observe that $$ {\pi_n \over 2^{5 \cdot2^n}} < {c_n \over 2^{3 \cdot 2^n} - 1} - \xi_{\bf t} < {\pi_n\over2^{5 \cdot2^n}} \cdot {2^{2^n}\over 2^{2^n}-1}, $$ and, since $$ q'_n \le {2^{3 \cdot 2^n} - 1 \over 3 (2^{2^{n-1}}-1)} \le {2^{5 \cdot 2^{n-1}} \over 3} \cdot {2^{2^{n- 1}} \over 2^{2^{n-1}} - 1}, $$ we deduce that \begin{equation} 0 < {p'_n \over q'_n} - \xi_{\bf t} < {\pi_n \over (3 q'_n)^2} \cdot {2^{2^n}\over 2^{2^n}-1} \cdot {2^{2^n}\over (2^{2^{n-1}}-1)^2}, \label{2.8} \end{equation} for $n \ge 3$. \end{proof} We can now prove Theorem~\ref{theorem1}. \begin{proof}[Proof of Theorem~\ref{theorem1}] The combination of Lemmas~\ref{lemma1} to \ref{lemma3} establishes the first assertion of Theorem~\ref{theorem1}. Recall that (see e.g., \cite{BuLiv}), for $\ell \ge 1$, we have \begin{equation} |q_{\ell} \xi_{\bf t} - p_\ell| = {1 \over q_\ell} \cdot {1 \over [a_{\ell + 1}; a_{\ell + 2}, \ldots ] + [0; a_{\ell}, a_{\ell-1}, \ldots ]}, \label{2.9} \end{equation} where $(p_{\ell}/q_{\ell})_{\ell \ge 0}$ denotes the sequence of convergents to $\xi_{\bf t}$. By (\ref{2.3}) and (\ref{2.9}), there exist arbitrarily large integers $\ell$ such that \begin{equation} [a_{\ell + 1}; a_{\ell + 2}, \ldots ] + [0; a_{\ell}, a_{\ell-1}, \ldots ] \doteq 1/0.175 \doteq 5.71. \label{2.10} \end{equation} Let $\ell$ be a positive integer for which (\ref{2.10}) holds. If $a_\ell \ge 2$, then $a_{\ell + 1}$ must be equal to $5$ and $a_{\ell + 2}$ is at most $4$. If $a_{\ell} = 1$, then $a_{\ell+1}$ equals $4$ or $5$. Finally, we use Eqs.\ (\ref{2.3}), (\ref{2.9}), Lemma~\ref{lemma4}, and Eq.\ (\ref{2.8}) to deduce that there exist arbitrarily large integers $\ell$ such that $$ [a_{\ell + 1}; a_{\ell + 2}, \ldots ] + [0; a_{\ell}, a_{\ell-1}, \ldots ] \ge 3^2 / 0.1751 \ge 51.3. $$ This implies that infinitely many partial quotients are at least equal to $50$. This concludes the proof of the theorem. \end{proof} \section{Acknowledgments} We are grateful to the referee for numerous comments, including the suggestion to study the rational numbers introduced in Lemma~\ref{lemma4}. \begin{thebibliography}{10} \bibitem{AlSh03} J.-P. Allouche and J. Shallit. {\it Automatic Sequences: Theory, Applications, Generalizations}. Cambridge University Press, 2003. \bibitem{BuLiv} Y. Bugeaud, {\it Approximation By Algebraic Numbers}. Cambridge Tracts in Mathematics 160, Cambridge University Press, 2004. \bibitem{Bu11} Y. Bugeaud. {On the irrationality exponent of the Thue-Morse-Mahler numbers}, {\em Ann. Institut Fourier (Grenoble) } {\bf 61} (2011), 2065--2076. \bibitem{De77} F. M. Dekking, {Transcendance du nombre de Thue-Morse}, {\em C. R. Acad. Sci. Paris S\'er. I Math.} {\bf 285} (1977), 157--160. \bibitem{Mah29} K. Mahler, {Arithmetische Eigenschaften der L\"osungen einer Klasse von Funktionalgleichungen}, {\em Math. Ann.} {\bf 101} (1929), 342--366. Corrigendum {\bf 103} (1930), 532. \bibitem{Rid57} D. Ridout, {Rational approximations to algebraic numbers}, {\em Mathematika} {\bf 4} (1957), 125--131. \bibitem{Sloa} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, \url{http://oeis.org/}, 2012. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11J04. \noindent \emph{Keywords: } Continued fraction, Thue-Morse constant, Fermat number. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A004249}, \seqnum{A010060}, and \seqnum{A014572}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 20 2012; revised version received June 6 2012. Published in {\it Journal of Integer Sequences}, March 2 2013. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .