Linear independence of series related to the Thue–Morse sequence along powers

Abstract

The Thue–Morse sequence $\{t(n)\}_{n\geqslant 0}$ is the indicator function of the parity of the number of ones in the binary expansion of nonnegative integers n, where $t(n)=1$ (resp. $=0$) if the binary expansion of n has an odd (resp. even) number of ones. In this paper, we generalize a recent result of E. Miyanohara by showing that, for a fixed Pisot or Salem number $\beta>\sqrt {\varphi }=1.272019\ldots $, the set of the numbers

$$\begin{align*}1,\quad \sum_{n\geqslant1}\frac{t(n)}{\beta^{n}},\quad \sum_{n\geqslant1}\frac{t(n^2)}{\beta^{n}},\quad \dots, \quad \sum_{n\geqslant1}\frac{t(n^k)}{\beta^{n}},\quad \dots \end{align*}$$

is linearly independent over the field $\mathbb {Q}(\beta )$, where $\varphi :=(1+\sqrt {5})/2$ is the golden ratio. Our result yields that for any integer $k\geqslant 1$ and for any $a_1,a_2,\ldots ,a_k\in \mathbb {Q}(\beta )$, not all zero, the sequence {$a_1t(n)+a_2t(n^2)+\cdots +a_kt(n^k)\}_{n\geqslant 1}$ cannot be eventually periodic.

1 Introduction

Let $s_2(n)$ denote the number of ones in the binary expansion of n. The Thue–Morse sequence $\mathbf {t}=\{t(n)\}_{n\geqslant 0}$ is defined, for $n\geqslant 0$ , by $t(n)=1$ if $s_2(n)$ is odd, and $t(n)=0$ if $s_2(n)$ is even. The Thue–Morse sequence is paradigmatic in the areas of complexity and symbolic dynamics, and as such is an object of current interest in a variety of areas. While the sequence goes back at least to the 1851 paper of Prouhet [6], its interest in the context of complexity is usually attributed to Thue [8, 9] who showed that $\textbf {t}$ is overlap-free; that is, viewing $\textbf {t}$ as a one-sided infinite word $t(0)t(1)t(2)\cdots $ , it contains no subwords of the form $awawa$ , where $a\in \{0,1\}$ and w is a finite binary word, possibly empty (cf. [1, p. 15]). This shows that $\textbf {t}$ contains no three consecutive identical subwords (namely, $\textbf {t}$ is cube-free) and consequently $\textbf {t}$ is nonperiodic. Thus, we find that the number $\sum _{n\geqslant 1}t(n)b^{-n}$ is irrational for any integer $b\geqslant 2$ , but more strongly, a result of Mahler [3] provides the transcendence of $\sum _{n\geqslant 1}t(n)\alpha ^{-n}$ for any algebraic number $\alpha $ with $|\alpha |>1$ .

On the other hand, the Thue–Morse sequence along powers has also been studied by several authors. In 2007, Moshe [5] investigated the subword complexity of the sequence along squares $\{t(n^2)\}_{n\geqslant 1}$ (see Section 4 for details) and solved a problem of Allouche and Shallit [1, p. 350] answering that every finite word ${a_0a_1\cdots a_{m-1}\ (a_i\in \{0,1\})}$ of length m appears in the infinite word $t(0)t(1)t(4)\cdots $ . Moreover, this result was generalized by Drmota, Mauduit, and Rivat [2] who proved that the sequence $\{t(n^2)\}_{n\geqslant 1}$ is normal (to the base $2$ ); that is, for any $m\geqslant 1$ and any $a_0a_1\cdots a_{m-1}\ (a_i\in \{0,1\})$ , we have

$$\begin{align*}\lim_{N\to\infty}\frac{\#\{n<N\mid t(n^2)=a_0,t((n+1)^2)=a_1,\dots,t((n+m-1)^2)=a_{m-1} \}}{N} =\frac{1}{2^m}. \end{align*}$$

As a consequence, the number $\sum _{n\geqslant 1}t(n^2)2^{-n}$ is normal in base $2$ . Recently, Spiegelhofer [7] proved that the sequence along cubes $\{t(n^3)\}_{n\geqslant 1}$ is simply normal;

$$\begin{align*}\lim_{N\to\infty}\frac{\#\{n<N\mid t(n^3)=0\}}{N} =\frac{1}{2}. \end{align*}$$

In this direction, it is expected that the sequence $\{t(P(n))\}_{n\geqslant 0}$ is normal for any nonnegative integer-valued polynomial P of degree at least $3$ ; however, it is unsolved (cf. [2, Conjecture 1]).

A Pisot (resp. Salem) number is an algebraic integer $\beta>1$ whose Galois conjugates other than $\beta $ have moduli less than $1$ (resp. less than or equal to $1$ and at least one conjugate lies on the unit circle). Recently, Miyanohara [4] showed that if $\beta $ is a Pisot or Salem number with $\beta>2$ , then the number $\sum _{n\geqslant 1}t(n^2){\beta ^{-n}}$ does not belong to the field $\mathbb {Q}(\beta )$ . Note that his method depends on elementary arguments without the use of the normality of $\{t(n^2)\}_{n\geqslant 0}$ . In this paper, we generalize Miyanohara’s results by proving the following theorem. Throughout the paper, $\varphi :=(1+\sqrt {5})/2$ denotes the golden ratio.

Theorem 1.1 Let $\beta $ be a Pisot or Salem number with $\beta>\sqrt {\varphi }=1.272019\ldots $ . Then, for any integer $k\geqslant 1$ , the $k+1$ numbers

$$\begin{align*}1,\quad \sum_{n\geqslant 1}\frac{t(n)}{\beta^n},\quad \sum_{n\geqslant 1}\frac{t(n^2)}{\beta^n},\quad \ldots,\quad \sum_{n\geqslant 1}\frac{t(n^k)}{\beta^n} \end{align*}$$

are linearly independent over the field $\mathbb {Q}(\beta )$ . In particular, for any integer $k\geqslant 1$ , the number $\sum _{n\geqslant 1}^{}t(n^k)\beta ^{-n}$ does not belong to $\mathbb {Q}(\beta )$ .

It should be noted that all Pisot numbers are covered in Theorem 1.1, since the smallest Pisot number is the plastic ratio $\rho =1.324717\ldots $ . On the other hand, all Salem numbers are not; for example, the smallest known Salem number is $\lambda =1.176280\ldots $ (see Sect. 4 for details). Let $\beta $ be as in Theorem 1.1. Then, as an immediate corollary of Theorem 1.1, for any nontrivial $\mathbb {Q}(\beta )$ -linear combination of the Thue–Morse sequence along powers

(1.1) $$ \begin{align} s(n):=a_1t(n)+a_2t(n^2)+\cdots+a_kt(n^k) \end{align} $$

the number $\sum _{n\geqslant 1}s(n)\beta ^{-n}$ does not belong to $\mathbb {Q}(\beta )$ , and hence the sequence $\{s(n)\}_{n\geqslant 0}$ cannot be eventually periodic.

The present paper is organized as follows. In Section 2, for each integer $r=1,2,\dots ,k$ , we will investigate the appearance of zeros in the sequences defined by the difference of $t(n^r)$ and a certain shift $t((n+n_0)^r)$ . This observation makes it possible to find a good rational approximation to

$$\begin{align*}\xi:=\sum_{n\geqslant 1}s(n)\beta^{-n}, \end{align*}$$

where the sequence $\{s(n)\}_{n\geqslant 1}$ is defined in (1.1). Section 3 is devoted to the proof of Theorem 1.1. In the last Section 4, we will give remarks and further questions related to our results.

2 Some useful equalities and unequalities

The first lemma allows us to optimize our choice of rational approximations.

Lemma 2.1 For any integer $k\geqslant 2$ , there exist positive integers m and n such that the system of simultaneous congruences

(2.1) $$ \begin{align} X&\equiv 2^{2m-1}-1\quad \pmod{2^{2m}},\nonumber\\ 3^{k-1}X&\equiv 2^{2n}-1\quad \pmod{2^{2n+1}}\end{align} $$

has an integer solution.

Proof For an even integer $k{\kern-1pt}\geqslant{\kern-1pt} 2$ , clearly $x{\kern-1pt}={\kern-1pt}1$ is a solution of (2.1) with $m{\kern-1pt}={\kern-1pt}n{\kern-1pt}={\kern-1pt}1$ . Thus, let $k=2\ell +1\geqslant 3$ be odd. Then there exist an integer $s\geqslant 3$ and $a\in \{0,1\}$ satisfying

$$ \begin{align*} 3^{k-1}=9^{\ell}\equiv 1+2^s+a2^{s+1}\quad \pmod {2^{s+2}}. \end{align*} $$

If $s=2u+1\geqslant 3$ is odd, we set $x:=2^{2u+1}-1+(1-a)2^{2u+2}$ , so that

$$ \begin{align*} 3^{k-1} x&\equiv (1+2^{2u+1}+a2^{2u+2})(2^{2u+1}-1+(1-a) 2^{2u+2})\quad \pmod{2^{2u+3}}\\ &\equiv 2^{2u+2}-1\quad \pmod{2^{2u+3}}, \end{align*} $$

and hence the integer x is a solution of (2.1) with $m=n=u+1$ . If $s=2u\geqslant 4$ is even, then setting $x:=2^{2u+1}-1+2^{2u+2}$ , we obtain

$$ \begin{align*} 3^{k-1} x&\equiv (1+2^{2u})(-1)\equiv 2^{2u}-1\quad \pmod {2^{2u+1}}, \end{align*} $$

and the integer x is a solution of (2.1) with $m=u+1$ and $n=u$ . Lemma 2.1 is proved.

Let $x\geqslant 1$ be an integer solution of the system of congruences (2.1). Then the binary expansions of the integers x and $x3^{k-1}$ have the forms

$$\begin{align*}(x)_2=w_10\overbrace{11\cdots1}^{2m-1}\qquad \mathrm{and}\qquad (x3^{k-1})_2=w_20\overbrace{11\cdots1}^{2n}, \end{align*}$$

respectively, for some binary words $w_1$ and $w_2$ , and hence we obtain the equalities

(2.2) $$ \begin{align} t(1+x)=t(x)\qquad\mathrm{and} \qquad t(1+x3^{k-1})=1-t(x3^{k-1}). \end{align} $$

Let $k\geqslant 2$ be an integer, and let $\nu (k):=\nu _2(k)$ be the $2$ -adic valuation of k. Fix positive integers m, n, x (depending only on k) as in Lemma 2.1. Since $k2^{-\nu (k)}$ is an odd integer, the congruence

(2.3) $$ \begin{align} k2^{-\nu(k)}\,Y\equiv x\quad \pmod{2^{2m+2n+1}} \end{align} $$

has an integer solution. Let $y\leqslant 2^{2m+2n+1}$ be the least positive integer solution of (2.3).

The remaining lemmas give us quantitative information about our approximations, as well as allowing us to optimize the range of $\beta $ in Theorem 1.1. Throughout the paper, let N be a sufficiently large integer. In the following Lemmas 2.2 and 2.3, we investigate the Thue–Morse values of the integers

(2.4) $$ \begin{align} (y2^{kN-\nu(k)+\delta}+j)^k= \sum_{\ell=0}^{k}\binom{k}{\ell}y^\ell j^{k-\ell}\cdot 2^{(kN-\nu(k)+\delta)\ell},\qquad \delta\in\{0,1\} \end{align} $$

for $j=0,1,\dots ,2^{N}+4$ and $j=2^N+2h\ (h=3,4,\dots ,2^{N-3})$ . Define

$$\begin{align*}A_{\ell,j}:=\binom{k}{\ell}y^\ell j^{k-\ell},\qquad \ell=0,1,\dots,k,\quad j=1,2,\dots,2^N+2^{N-2}. \end{align*}$$

When $1\leqslant \ell \leqslant k$ , we have

(2.5) $$ \begin{align} A_{\ell,j}\leqslant 2^k\cdot(2^{2m+2n+1})^k\cdot (5\cdot 2^{N-2})^{k-1}<2^{kN-\nu(k)+\delta} \end{align} $$

since N is sufficiently large. Hence, using (2.4) and (2.5), we obtain

(2.6) $$ \begin{align} t\left( (y2^{kN-\nu(k)+\delta}+j)^k \right)&\equiv t\left(A_{0,j}+A_{1,j}2^{kN-\nu(k)+\delta}\right)+\sum_{\ell=2}^{k}t\left(A_{\ell,j}2^{(kN-\nu(k)+\delta)\ell}\right)\nonumber\\ &\equiv t\left(j^k+zj^{k-1}2^{kN+\delta}\right)+\sum_{\ell=2}^{k}t\left(A_{\ell,j}\right)\quad \pmod{2}, \end{align} $$

where $z:=k2^{-\nu (k)}y$ . Note that the integers $A_{\ell ,j}$ are independent of $\delta $ .

Lemma 2.2 For every integer $j=0,1,\dots ,2^N-1$ and $j=2^N+2h\ (h=0,1,\dots ,2^{N-3})$ , we have

(2.7) $$ \begin{align} t\left((y2^{kN-\nu(k)}+j)^k\right)= t\left((y2^{kN-\nu(k)+1}+j)^k\right). \end{align} $$

Proof Let $\delta \in \{0,1\}$ . For $j=0,1,\dots ,2^N-1$ , we have

(2.8) $$ \begin{align} j^k<2^{kN}\qquad \mathrm{and}\qquad 2^{kN}\mid zj^{k-1}2^{kN+\delta}, \end{align} $$

and moreover, for $j=2^N+2h\ (h=0,1,\dots ,2^{N-3})$ ,

(2.9) $$ \begin{align} j^k\leqslant (5\cdot 2^{N-2})^k<2^{kN+k-1}\quad\mbox{and}\quad 2^{kN+k-1}\mid z(2^{N-1}+h)^{k-1}2^{kN+k-1+\delta}, \end{align} $$

since $2^{kN+k-1}\mid zj^{k-1}2^{kN+\delta }$ . Hence, by (2.8) and (2.9),

(2.10) $$ \begin{align} t(j^k+zj^{k-1}2^{kN+\delta})\equiv t(j^k)+t(zj^{k-1})\quad \pmod{2}, \end{align} $$

so that (2.6) and (2.10) yield

(2.11) $$ \begin{align} t\left((y2^{kN-\nu(k)+\delta}+j)^k\right)\equiv t(j^k)+t(zj^{k-1}) +\sum_{\ell=2}^{k}t(A_{\ell,j})\quad \pmod{2} \end{align} $$

for $j=0,1,\dots ,2^N-1$ and $j=2^N+2h\ (h=0,1,\dots ,2^{N-3})$ . Thus, Lemma 2.2 is proved since the right-hand side in (2.11) is independent of $\delta $ .

Next, we show that the equality (2.7) also holds for $j=2^N+3$ , but not for $j=2^N+1$ .

Lemma 2.3 We have

$$ \begin{align*} t\left((y2^{kN-\nu(k)}+2^N+1)^k\right)\neq t\left((y2^{kN-\nu(k)+1}+2^N+1)^k\right)\end{align*} $$

and

$$ \begin{align*} t\left((y2^{kN-\nu(k)}+2^N+3)^k\right)= t\left((y2^{kN-\nu(k)+1}+2^N+3)^k\right). \end{align*} $$

Proof Let $\delta \in \{0,1\}$ and $j:=2^N+i\ (i=1,3)$ . Then we have

(2.12) $$ \begin{align} j^k+zj^{k-1}2^{kN+\delta}&= \sum_{\ell=0}^{k}\binom{k}{\ell}i^{k-\ell}\cdot 2^{N\ell}+\sum_{\ell=0}^{k-1}\binom{k-1}{\ell}zi^{k-1-\ell}\cdot 2^{N(\ell+k)+\delta}\nonumber\\&= \sum_{\ell=0}^{k-1}\binom{k}{\ell}i^{k-\ell}\cdot 2^{N\ell}+ (1+zi^{k-1}2^{\delta})\cdot 2^{kN} \nonumber\\&\quad+ \sum_{\ell=k+1}^{2k-1}\binom{k-1}{\ell-k}zi^{2k-\ell-1}\cdot 2^{N\ell+\delta}. \end{align} $$

Since the integers

$$\begin{align*}B_{\ell,i}:=\binom{k}{\ell}i^{k-\ell}, \quad 1+zi^{k-1}2^\delta, \quad C_{\ell,i}:=\binom{k-1}{\ell-k}zi^{2k-\ell-1} \end{align*}$$

are independent of N, it follows from (2.12) that

(2.13) $$ \begin{align} t\left(j^k+zj^{k-1}2^{kN+\delta}\right)\equiv\sum_{\ell=0}^{k-1}t(B_{\ell,i})+t\left(1+zi^{k-1}2^{\delta}\right)+ \sum_{\ell=k+1}^{2k-1}t(C_{\ell,i})\quad \pmod{2}. \end{align} $$

Moreover, combining Lemma 2.1 with (2.3), we obtain

$$ \begin{align*} zi^{k-1}=k2^{-\nu(k)}yi^{k-1}&\equiv xi^{k-1}\quad \pmod{2^{2m+2n+1}}\\ &\equiv \begin{cases} 2^{2m-1}-1\quad \pmod{2^{2m}},&\mbox{if}\ i=1,\\ 2^{2n}-1\quad \pmod{2^{2n+1}},&\mbox{if}\ i=3, \end{cases} \end{align*} $$

so that by (2.2)

(2.14) $$ \begin{align} t(1+zi^{k-1})= \begin{cases} t(zi^{k-1}),&\mbox{if}\ i=1,\\ 1-t(zi^{k-1}),&\mbox{if}\ i=3. \end{cases} \end{align} $$

Thus, by (2.6), (2.13), and (2.14), we obtain

$$ \begin{align*} t\left( (y2^{kN-\nu(k)+1}+j)^k \right)-& t\left( (y2^{kN-\nu(k)}+j)^k \right)\\ &\equiv t\left(j^k+zj^{k-1}2^{kN+1}\right)-t\left(j^k+zj^{k-1}2^{kN}\right)\\[0.2cm] &\equiv t(1+2zi^{k-1})-t(1+zi^{k-1})\\[0.2cm] &\equiv 1+t(zi^{k-1})- \begin{cases} t(zi^{k-1}),&\mbox{if}\ i=1,\\ 1-t(zi^{k-1}),&\mbox{if}\ i=3, \end{cases}\\[0.2cm] &\equiv \begin{cases} 1,&\mbox{if}\ j=2^N+1,\\ 0,&\mbox{if}\ j=2^N+3, \end{cases}\quad \pmod{2}, \end{align*} $$

which finishes the proof of the Lemma 2.3.

Define

$$\begin{align*}\lambda:=1+\frac{1}{2(k-1)}>1, \end{align*}$$

and let $\lfloor \alpha \rfloor $ denote the integral part of the real number $\alpha $ .

Lemma 2.4 For every integer $r=1,\dots ,k-1$ and $j=0,1,\dots ,2^{\lfloor \lambda N\rfloor }$ , we have

(2.15) $$ \begin{align} t\left((y2^{kN-\nu(k)}+j)^r\right)= t\left((y2^{kN-\nu(k)+1}+j)^r\right). \end{align} $$

Proof Let $\delta \in \{0,1\}$ and $r, j$ be fixed integers as in the lemma. Then we have

$$\begin{align*}(y2^{kN-\nu(k)+\delta}+j)^r=\sum_{\ell=0}^{r}\binom{r}{\ell}y^{\ell}j^{r-\ell}\cdot 2^{(kN-\nu(k)+\delta)\ell}. \end{align*}$$

Since

$$\begin{align*}D_{\ell,j}:=\binom{r}{\ell}y^{\ell}j^{r-\ell}\leqslant 2^{k-1}\cdot(2^{2m+2n+1})^{k-1}\cdot (2^{\lambda N})^{k-1}<2^{kN-\nu(k)+\delta}, \end{align*}$$

we obtain

$$\begin{align*}t\left((y2^{kN-\nu(k)+\delta}+j)^r\right)\equiv \sum_{\ell=0}^{r}t(D_{\ell,j})\quad \pmod{2}, \end{align*}$$

which is independent of $\delta $ . Lemma 2.4 is proved.

3 Proof of Theorem 1.1

Let $\beta $ be a Pisot or Salem number with $\beta>\sqrt {\varphi }=1.272019\ldots $ . Suppose to the contrary that there exist an integer $k\geqslant 1$ and algebraic numbers $a_0,a_1,\ldots ,a_k\in \mathbb {Q}(\beta )$ , not all zero, such that

(3.1) $$ \begin{align} a_0+a_1\sum_{n\geqslant 1}\frac{t(n)}{\beta^n}+a_2\sum_{n\geqslant 1}\frac{t(n^2)}{\beta^n}+\cdots+a_k\sum_{n\geqslant 1}\frac{t(n^k)}{\beta^n}=0. \end{align} $$

We may assume that $a_0,a_1,\ldots ,a_k\in \mathbb {Z}[\beta ]$ and $a_k\neq 0$ . As mentioned in Section 1, the number $\sum _{n\geqslant 1}^{}t(n)\alpha ^{-n}$ is transcendental for any algebraic number $\alpha $ with $|\alpha |>1$ , and thus we have $k\geqslant 2$ . Define the sequence $\{s(n)\}_{n\geqslant 1}$ by

$$ \begin{align*} s(n):=a_1t(n)+a_2t(n^2)+\cdots+a_kt(n^k),\quad n\geqslant 1, \end{align*} $$

and

$$\begin{align*}\xi:=\sum_{n\geqslant1}^{}\frac{s(n)}{\beta^n}. \end{align*}$$

Note that $\{s(n)\}_{n\geqslant 1}$ is bounded and the number $\xi =-a_0\in \mathbb {Z}[\beta ]$ by (3.1). Let $\nu (k),y$ be as in Section 2, and let N be a sufficiently large integer such that Lemmas 2.2–2.4 all hold. For convenience, let

$$\begin{align*}\kappa(N):=kN-\nu(k). \end{align*}$$

Define the algebraic integers $p_N,q_N\in \mathbb {Z}[\beta ]$ by

$$\begin{align*}p_N:=(\beta^{y2^{\kappa(N)}}-1)\sum_{n=1}^{y2^{\kappa(N)}-1}s(n)\beta^{y2^{\kappa(N)}-n}+\sum_{n=y2^{\kappa(N)}}^{y2^{\kappa(N)+1}-1}s(n)\beta^{y2^{\kappa(N)+1}-n} \end{align*}$$

and $q_N:=(\beta ^{y2^{\kappa (N)}}-1)\beta ^{y2^{\kappa (N)}}$ , respectively. Then, we obtain

(3.2) $$ \begin{align} \frac{p_N}{q_N}&=\sum_{n=1}^{y2^{\kappa(N)-1}}\frac{s(n)}{\beta^{n}}+\frac{\beta^{y2^{\kappa(N)}}}{\beta^{y2^{\kappa(N)}}-1}\cdot \sum_{n=y2^{\kappa(N)}}^{y2^{\kappa(N)+1}-1}\frac{s(n)}{\beta^{n}}\nonumber\\[0.2cm] &=\sum_{n=1}^{y2^{\kappa(N)}-1}\frac{s(n)}{\beta^{n}}+ \left( 1+\frac{1}{\beta^{y2^{\kappa(N)}}}+ \left(\frac{1}{\beta^{y2^{\kappa(N)}}} \right)^2+\cdots \right) \sum_{n=y2^{\kappa(N)}}^{y2^{\kappa(N)+1}-1}\frac{s(n)}{\beta^{n}}\nonumber\\[0.2cm] &= \sum_{n=1}^{y2^{\kappa(N)+1}-1}\frac{s(n)}{\beta^{n}} + \frac{1}{\beta^{y2^{\kappa(N)}}} \sum_{n=y2^{\kappa(N)}}^{y2^{\kappa(N)+1}-1}\frac{s(n)}{\beta^{n}} + O\left( \left( \frac{1} {\beta^{y2^{\kappa(N)}}} \right)^2 \right)\cdot O \left( \frac{1}{\beta^{y2^{\kappa(N)}}} \right)\nonumber\\[0.2cm] &= \sum_{n=1}^{y2^{\kappa(N)+1}-1} \frac{s(n)}{\beta^{n}} + \sum_{j=0}^{y2^{\kappa(N)}-1} \frac{s(y2^{\kappa(N)}+j)} {\beta^{y2^{\kappa(N)+1}+j}} +O\left( \frac{1}{\beta^{3y2^{\kappa(N)}}} \right). \end{align} $$

By the equalities (2.7) and (2.15) with $j=0,1,\dots ,2^N$ , we have

(3.3) $$ \begin{align} s(y2^{\kappa(N)}+j)=s(y2^{\kappa(N)+1}+j),\qquad j=0,1,\ldots,2^N. \end{align} $$

Hence, by (3.2) and (3.3),

(3.4) $$ \begin{align} \frac{p_N}{q_N}= \sum_{n=1}^{y2^{\kappa(N)+1}+2^N}\frac{s(n)}{\beta^{n}} + \sum_{j=2^N+1}^{2^{\lfloor \lambda N\rfloor}} \frac{s(y2^{\kappa(N)}+j)}{\beta^{y2^{\kappa(N)+1}+j}} +O\left( \frac{1}{\beta^{y2^{\kappa(N)+1}+2^{\lfloor \lambda N\rfloor}}} \right), \end{align} $$

where we used $1<\lambda <2\leq k$ in the big O notation. Therefore, by using (3.4) and the equalities (2.15) with $j=2^N+1,\dots ,2^{\lfloor \lambda N\rfloor }$ , we obtain

(3.5) $$ \begin{align} \xi-\frac{p_N}{q_N}= a_k\sum_{j=2^N+1}^{2^{\left\lfloor \lambda N\right\rfloor}} \frac{u(j) }{\beta^{y2^{\kappa(N)+1}+j}} + O\left(\frac{1}{\beta^{y2^{\kappa(N)+1}+ 2^{\left\lfloor\lambda N\right\rfloor}}}\right), \end{align} $$

where

$$\begin{align*}u(j):=t\left((y2^{\kappa(N)+1}+j)^k\right)-t\left((y2^{\kappa(N)}+j)^k\right),\quad j\geqslant 2^N+1. \end{align*}$$

Note that $|u(j)|\leqslant 1$ since $u(j)\in \{-1,0,1\}$ for every integer j. Moreover, by the definition of $q_N$ , we have $q_N\leqslant \beta ^{y2^{\kappa (N)+1}}$ , and so by (3.5),

(3.6) $$ \begin{align} q_N\xi-p_N=O\left(\frac{1}{\beta^{2^N}}\right). \end{align} $$

On the other hand, applying Lemmas 2.2 and 2.3, we obtain

(3.7) $$ \begin{align} \left| \sum_{j=2^N+1}^{2^{\left\lfloor \lambda N\right\rfloor}} \frac{u(j)}{\beta^{j}}\right| & \geqslant \frac{1}{\beta^{2^N+1}}- \sum_{j=2^N+5}^{2^{\left\lfloor \lambda N\right\rfloor}} \frac{|u(j)| }{\beta^{j}}\nonumber \\[0.2cm] &= \frac{1}{\beta^{2^N+1}} - \sum_{ \substack{j\geqslant 2^N+5\\j\mathrm{:odd}} }^{} \frac{1 }{\beta^{j}} - \sum_{ \substack{ j\geqslant 2^N+2^{N-2}+1\\j\mathrm{:even}} }^{} \frac{1 }{\beta^{j}} \nonumber\\[0.2cm] &\geqslant \frac{1}{\beta^{2^N+1}}- \frac{\beta^2}{\beta^2-1} \left( \frac{1}{\beta^{2^N+5}} + \frac{1}{\beta^{5\cdot 2^{N-2}+2}} \right)\nonumber\\[0.2cm] &= \frac{\beta^4-\beta^2-1}{\beta^3(\beta^2-1)}\cdot\frac{1}{\beta^{2^N}}+O\left( \frac{1}{\beta^{5\cdot 2^{N-2}}} \right), \end{align} $$

and hence, by (3.5) and (3.7),

$$ \begin{align*} \beta^{y2^{\kappa(N)+1}} \left| \xi-\frac{p_N}{q_N}\right|& \geqslant |a_k|\cdot \left| \sum_{j=2^N+1}^{2^{\left\lfloor \lambda N\right\rfloor}} \frac{u(j) }{\beta^{j}} \right|+ O\left( \frac{1}{ \beta^{2^{\left\lfloor\lambda N\right\rfloor}} } \right)\\[0.2cm] &= |a_k|\cdot\frac{\beta^4-\beta^2-1}{\beta^3(\beta^2-1)}\cdot\frac{1}{\beta^{2^N}}+O\left( \frac{1}{\beta^{5\cdot 2^{N-2}}} \right)+O\left( \frac{1}{ \beta^{2^{\left\lfloor\lambda N\right\rfloor}} } \right). \end{align*} $$

Thus, noting that $\beta>\sqrt {\varphi }$ , $a_k\neq 0$ , and that both $5\cdot 2^{N-2}-2^N$ and $2^{\lfloor \lambda N\rfloor }-2^N$ tend to infinity as $n\to \infty $ , we obtain

(3.8) $$ \begin{align} \left|\xi-\frac{p_N}{q_N}\right|>0. \end{align} $$

Combining (3.6) and (3.8), there is a positive constant $c_1$ such that

(3.9) $$ \begin{align} 0<\left|q_N\xi-p_N\right|<\frac{c_1}{\beta^{2^N}} \end{align} $$

for every sufficiently large N.

Now, we complete the proof. When $\beta $ is a rational integer, (3.9) is clearly impossible for large N, since $q_N\xi -p_N$ is a nonzero rational integer. So, suppose not, and let $\beta =:\beta _1,\beta _2,\ldots ,\beta _d\ (d\geqslant 2)$ be the Galois conjugates over $\mathbb {Q}$ of $\beta $ . Since $\xi =-a_0\in \mathbb {Z}[\beta ]$ , there exist rational integers $A_0,A_1,\ldots ,A_{d-1}$ such that $ \xi =\sum _{i=0}^{d-1}{A_i}\beta ^i. $ Define the polynomial over $\mathbb {Z}[\beta ]$

$$\begin{align*}F_N(X):=q_N(X)\xi(X)-p_N(X), \end{align*}$$

where

$$ \begin{align*} p_N(X)&:=(X^{y2^{\kappa(N)}}-1)\sum_{n=1}^{y2^{\kappa(N)}-1}s(n)X^{y2^{\kappa(N)}-n}+\sum_{n=y2^{\kappa(N)}}^{y2^{\kappa(N)+1}-1}s(n)X^{y2^{\kappa(N)+1}-n},\\ q_N(X)&:=(X^{y2^{\kappa(N)}}-1)X^{y2^{\kappa(N)}},\\ \xi(X)&:=\sum_{i=0}^{d-1}A_iX^i. \end{align*} $$

Note that $p_N(\beta )=p_N$ , $q_N(\beta )=q_N$ , and $\xi (\beta )=\xi $ . By (3.9),

(3.10) $$ \begin{align} 0<|F_N(\beta)|=\left|q_N\xi-p_N\right|<\frac{c_1}{\beta^{2^N}}. \end{align} $$

Moreover, since $\beta $ is a Pisot or Salem number, we have $|\beta _i|\leqslant 1\ (i=2,3,\dots ,d)$ , and so by the definitions of $p_N(X),q_N(X),\xi (X)$ , there exists a positive constant $c_2$ independent of N such that

(3.11) $$ \begin{align} 0<|F_N(\beta_i)|\leqslant c_2\cdot y2^{\kappa(N)},\qquad i=2,3,\dots,d, \end{align} $$

where the first inequality follows since $F_N(\beta _i)$ are the Galois conjugates of ${F_N(\beta )\neq 0}$ . Therefore, considering the norm over $\mathbb {Q}(\beta )/\mathbb {Q}$ of the algebraic integer $F_N(\beta )$ , we obtain, by (3.10) and (3.11),

$$\begin{align*}1\leqslant |N_{\mathbb{Q}(\beta)/\mathbb{Q}}F_N(\beta)| =\prod_{i=1}^{d-1}|F_N(\beta_i)| < \frac{c_1 c_2^{d-1}\cdot (y2^{\kappa(N)})^d}{\beta^{2^N}}, \end{align*}$$

which is impossible for sufficiently large N, since $\kappa (N)=O(N)=o(2^N)$ . The proof of Theorem 1.1 is now complete.

4 Concluding remarks and further questions

As there is no known nontrivial lower bound on Salem numbers, for our Theorem 1.1 to apply to all Salem numbers, we would need our result to be valid for $\beta>1$ . It seems very unlikely that the type of optimization that we have done here could be carried out to reach that range. A similar approach could increase the range a bit, but a new idea is probably necessary to get the full range of possible $\beta $ . Here, our proof works for Pisot and Salem numbers, but it seems reasonable to conjecture that Theorem 1.1 holds for any algebraic number $\beta $ with $|\beta |>1$ , though without more information on the structure of the sequences $\{t(n^k)\}_{n\geqslant 0}$ this seems out of reach at the moment.

When we first started our investigation, we wanted to show that the three numbers

$$\begin{align*}1,\quad \sum_{n\geqslant 1}\frac{t(n)}{b^n},\quad \sum_{n\geqslant 1}\frac{t(n^2)}{b^n} \end{align*}$$

are linearly independent over $\mathbb {Q}$ for any positive integer $b\geqslant 2$ . Considering this question, two properties of the Thue–Morse sequence stood out to us. First, the sequence $\{t(n)\}_{n\geqslant 0}$ is produced by a finite automaton (see [1, Section 5.1]), so it is not a very complicated sequence. Second, the sequence $\{t(n^2)\}_{n\geqslant 0}$ is extremely complicated – as we mentioned in Section 1, the sequence $\{t(n^2)\}_{n\geqslant 0}$ is normal; that is, all $2^m$ patterns of finite subwords of length m occur with frequency $2^{-m}$ . A result of Wall [10, Corollary 1, p. 15] states that if $\xi $ is normal and $q_1\neq 0$ and $q_2$ are rational numbers, then $q_1\xi +q_2$ is also normal, which implies the $\mathbb {Q}$ -linear independence of the above three numbers when $b=2$ . It seems reasonable to think that for any rational numbers $q_1\neq 0$ and $q_2$ , the number

$$\begin{align*}q_2+q_1\sum_{n\geqslant 1}\frac{t(n)}{b^n} \end{align*}$$

must have a “not very complicated” base-b expansion. In fact, this is the case since $\{t(n)\}_{n\geqslant 0}$ is produced by a finite automaton (see [1, Section 13.1]). There is a gap in the literature regarding sequences and numbers that fall in between automatic and normal. We make explicit a question that would be a first step in this direction.

Recall, for any sequence f taking values in $\{0,1\}$ , we let $p_f(m)$ denote the (subword) complexity of f as a one-sided infinite word. In particular, $p_f(m)$ counts the number of distinct blocks of length m in f. So, for example, f is eventually periodic if and only if $p_f(m)$ is uniformly bounded, and if f is $2$ -normal, then $p_f(m)=2^m$ for all m, since every binary word of any length appears in a $2$ -normal binary word. The entropy of f is the limit, $h(f):=\lim _{m\to \infty }(\log p_f(m))/m\in [0,\log 2]$ . Considering the Thue–Morse sequence (or word) $\textbf {t}$ , since $\textbf {t}$ is generated by a finite automaton, we have that $p_{\textbf {t}}(m)=O(m)$ , so $h(\textbf {t})=0$ . In the present paper, we considered the sequences $\textbf {t}^k:=\{t(n^k)\}_{n\geqslant 0}.$ Moshe [5] established that $p_{\textbf {t}^k}(m)\geqslant 2^{m/2^{k-2}}$ for any $k\geqslant 2$ ; that is, that $h(\textbf {t}^k)\geqslant (\log 2)/2^{k-2}>0$ . The question about numbers with lower complexity seems immediate.

Question 4.1 For a real number $\xi $ , let $p_\xi (m,b)$ be the number of b-ary words of length m appearing in the base-b expansion of $\xi $ . Is it true that for any two rational numbers $q_1\neq 0$ and $q_2$ , we have $p_{q_1\xi +q_2}(m,b)=O(p_\xi (m,b))\ ?$