The Hankel determinants of the Baum-Sweet sequence are 2-automatic

Introduction

The Baum–Sweet sequence $b=(b_n)_{n\geq0}$ over $\mathbb{F}_2$ is defined by $b_0=1$ and, for $n\geq1$, $b_n=1$ if and only if the binary expansion of $n$ has no block of zeros of odd length; equivalently $b_{2n+1}=b_n$, $b_{4n}=b_n$, $b_{4n+2}=0$. Its generating series $f=\sum_{n\geq0}b_nt^{-n}$ is the unique root in $\mathbb{F}_2((t^{-1}))$ of

Baum and Sweet [4] showed that all partial quotients of $f$ have degree 1 or 2. Mills and Robbins [8] gave the expansion explicitly (§ 3), and Mkaouar [6] proved that the sequence of partial quotients is not automatic, although it is the image of a fixed point of a non-uniform substitution on 20 letters.

For $c\geq0$ let $H_n^{(c)}=\det(b_{c+i+j})_{0\leq i,j<n}$ (with $H_0^{(c)}=1$) and

Hankel determinants of automatic sequences have been studied since Allouche, Peyrière, Wen and Wen [2]; Hu and Han [5] proved automaticity for the reduced Hankel determinants modulo 2 of a family of $\pm1$ sequences, and Allouche, Han and Niederreiter [1 Section 7] ask whether the Hankel determinants of a $d$-automatic sequence are $d$-regular or, reduced modulo some integer, $d$-automatic. For the Baum–Sweet sequence and reduction modulo 2 (the determinants of the 0, 1 matrices modulo 2 are the determinants over $\mathbb{F}_2$) the answer is positive.

$\chi_1)$ reading the most significant digit first has 15 (resp. 8) states, and the one reading the least significant digit first has 74 (resp. 68) states.

Let $\Theta=tf^2$. From $tf^3+f=t$ one gets $\Theta^3+\Theta=t(tf^3+f)^2=t^3$, so $\Theta$ is a root of $Z^3+Z+t^3$ in $\mathbb{F}_2((t^{-1}))$, and $f/t=1/(1+\Theta)$. Since $\Theta=t^3/(1+\Theta^2)$, $\Theta$ is hyperquadratic in the sense of Lasjaunias [La00]. As in § 3 we write $X=t$ when $t$ is used as a partial quotient.

This refines the bounds $N/3\leq L(b,N)\leq(2N+1)/3$ of Ḿerai and Winterhof [9 Corollary 3]. Some bound $|2L(b,N)-N|\leq C$ follows from the boundedness of the partial quotients of $f/t$; the point is the exact window and the fact that it is attained. Allouche, Han and Niederreiter [1 Section 7] ask for which automatic sequences the profile can be computed exactly, and Theorem 1.1 gives it by an automaton. We also obtain the transfer relation $\chi_0(n)=\chi_1(n)\chi_1(n-1)$ for $n\geq1$ (Proposition 5.2).

The proofs reduce every infinite statement to a finite one: an induction on the Mills–Robbins recursion closed by finitely many boundary words (Lemma 4.1), a transducer with finitely many configurations (Theorem 5.1), and a self-similarity of the dyadic blocks (Proposition 3.2) that a finite automaton is shown to satisfy (§ 6). The finite verifications are carried out by the ancillary script, described in § 8.

Continued fractions and Hankel determinants

For $\alpha=\sum_{n\geq1}s_{n-1}t^{-n}\in\mathbb{F}_2((t^{-1}))$ with convergents $P_j/Q_j$, one has $\det(s_{i+j})_{0\leq i,j<n}\ne0$ if and only if $n\in\{\deg Q_j:j\geq0\}$; this is the classical link between Hankel determinants and the Padé table, see e.g. [1]. We apply it to

so that $\chi_0$ and $\chi_1$ are the indicator functions of $\Sigma_0=\{\deg Q_j(\alpha_0)\}$ and $\Sigma_1=\{\deg Q_j(\alpha_1)\}$. If $\alpha=[0;q_1,q_2,\ldots]$ then $\deg Q_j=\deg q_1+\cdots+\deg q_j$. By Niederreiter’s theorem [10 Theorem 1], the linear complexity of $s_0,\ldots,s_{N-1}$ is $\deg Q_j$, where $j$ is determined by $\deg Q_{j-1}+\deg Q_j\leq N<\deg Q_j+\deg Q_{j+1}$.

The Mills–Robbins expansion and its dyadic structure

Write $T=\{X,X+1,X^2,X^2+1\}$ (with $X=t$), let $\tau$ exchange $X\leftrightarrow X+1$ and $X^2\leftrightarrow X^2+1$, and, for a word $w$, let $\widetilde{w}$ be its reversal. Put $\Gamma_0=X+1$, $\Gamma_1=X+1,X^2+1$, $\Gamma_2=X+1,X^2+1,X,X^2,X+1$ and, for $n\geq3$,

where $\tau'$ applies $\tau$ to the first letter only, and

Each $\Gamma_n$ is a prefix of $\Gamma_{n+1}$; let $\Gamma_\infty$ be the limit. Mills and Robbins proved [8], see [6 p. 363], that

For a word $w$ over $T$ let $D(w)$ be the sum of the degrees of its letters, and let $\varphi$ be one of the codings $\varphi_1,\varphi_0$ defined by $\varphi_\varepsilon(c)=1$ if $\deg c=1$ and $\varphi_1(c)=01$, $\varphi_0(c)=00$ if $\deg c=2$. Both preserve lengths: $|\varphi(w)|=D(w)$.

Put $A_n=\varphi(\Gamma_n)$, $B_n=\varphi(\widetilde{\Gamma}_n)$, $L_n=\varphi(\Lambda_n)$ and, for $m\ge5$,

By the recursion, the palindromy of $\Lambda_n$ and $\deg\tau(c)=\deg c$, we have $A_n=A_{n-1}G_n$ and $B_n=G_nB_{n-1}$ for $n\ge5$, and $|G_m|=2^m$ by Lemma 3.1.

In binary, with $n=2^m+x$, the four cases read: (R1) $n=111y$ with $y\ne0$, and then $\omega(n)=\omega(y)$; (R2) $n=1001^a0z$ with $|z|=j\ge5$, and then $\omega(n)=\omega(1z)$; (R3) $n=1001^{m-7}w$ with $|w|=5$, $w\ne11111$, and then $\omega(n)=B_4[\operatorname{val}(w)]$; (R4) all remaining $n$, namely $1001^{m-2}$, $101u$, $110u$ and $1110^{m-2}$. In (R4), $L_m$ is explicit: it is $\varphi$ of the palindrome $\Lambda_m$, whose middle part $\varphi((X,X^2)^k)$ is periodic of period 3.

The factors of length three

A transducer for t/f

For a matrix $M=\begin{pmatrix}p&q\\r&s\end{pmatrix}$ over $\mathbb{F}_2[t]$ and a series $y$ write $M(y)=(py+q)/(ry+s)$. To compute the continued fraction of $z=t/f$ from $f=[1;X,\Gamma_\infty]$ we keep a matrix $M$ with $z=M(y)$, where $y$ is the remaining tail of $f$. Reading a partial quotient $a$ of $f$ replaces $M$ by $M\begin{pmatrix}a & 1 \\ 1 & 0\end{pmatrix}$; emitting a partial quotient $\kappa$ of $z$ replaces $M$ by $\begin{pmatrix}0 & 1 \\ 1 & \kappa\end{pmatrix}M$. Both preserve $\det M$ up to sign, hence $\det M=t$ throughout (we start from $M=\begin{pmatrix}0 & t \\ 1 & 0\end{pmatrix}$).

If $y=a+1/y'$ with $\deg a\ge1$, $\deg y'\ge1$, then $M(y)-p/r=\det M/(r(ry+s))$, and $\deg(ry+s)=\deg(ra+s)$ as soon as $\deg(ra+s)\ge\deg r$. Hence, if $\deg(ra+s)\ge\deg r$ and $\deg r+\deg(ra+s)>\deg\det M$ for every letter $a$ that can follow, the polynomial part $\kappa$ of $p/r$ is the polynomial part of $z$, and if $\deg\kappa\ge1$ it is a correct partial quotient of $z$: we emit it. We emit greedily as long as this holds for every letter allowed by $F$ after the last two letters read.

Proof. A finite computation over the 12 configurations and the letters allowed by $F$ (Lemma 4.1), performed by the script.

Proof of Theorem 1.2. By Theorem 5.1, $t/f=[X+1;a_1,a_2,\ldots]$ with $a_i=\psi(i\text{-th block})$, and $\Theta=t/f+1=[X;a_1,a_2,\ldots]$.

Proof. $\alpha_1=f+1=[0;X,\Gamma_\infty]$, so $\Sigma_1$ consists of 0, 1 and the numbers $1+D_i$, where $D_i$ is the total degree of the first $i$ letters of $\Gamma_\infty$; this is $\chi_1=1\!1\,\varphi_1(\Gamma_\infty)$. Next $\alpha_0=f/t=[0;t/f]$, so $\Sigma_0$ consists of 0 and the cumulative degrees of the partial quotients of $t/f$. By Theorem 5.1 these are 1 and the numbers $D_i+1$ for which the $i$-th letter of $\Gamma_\infty$ has degree 1; this is $\chi_0=1\!1\,\varphi_0(\Gamma_\infty)$. For the last statement: $\chi_0(n)=1$ means that position $n$ ends a letter of degree 1, $\chi_1(n)=1$ that it ends a letter; a letter of degree 2 is coded 01 by $\varphi_1$, so $n$ ends a letter of degree 1 if and only if both $n$ and $n-1$ end letters.

Remark 5.3. Equivalently, $\Sigma_1=\Sigma_0\cup(\Sigma_0-1)$ (restricted to $n\ge0$). One inclusion holds for every sequence: by the Desnanot–Jacobi identity $H_{n+1}^{(0)}H_{n-1}^{(2)}=H_n^{(0)}H_n^{(2)}-(H_n^{(1)})^2$, if $H_n^{(0)}=H_{n+1}^{(0)}=0$ then $H_n^{(1)}=0$, that is $\Sigma_1\subseteq\Sigma_0\cup(\Sigma_0-1)$. The reverse inclusion is specific: it fails for most random binary sequences.

Proof of Theorem 1.1

By Proposition 5.2, $\chi_c(n+1)=\omega(n)$ with $\omega=1\varphi_c(\Gamma_\infty)$ for $n\ge0$. The word $\omega$ is determined by its first 256 letters and the rules (R1)–(R4) of Proposition 3.2, since each rule expresses $\omega(n)$, $n\ge256$, through a smaller index or an explicit word. It therefore suffices to show that the output $\widehat{\omega}(n)$ of $\mathcal{A}$ on the binary expansion of $n$ satisfies the same rules and agrees with $\omega$ on $[0,256)$. Since $\delta(0,0)=0$, leading zeros do not matter. Each rule is a statement about all words of a regular shape, and is checked in a finite product automaton:

• (R1): for all $y$ with $|y|\ge6$, $y\ne0$, the states reached from $\delta(0,111)$ and from 0 by reading $y$ have the same output (reachability in $\mathcal{A}\times\mathcal{A}\times\{\text{length}\le6\}\times\{y=0?\}$);

• (R2): the same for the states reached from $\delta(0,1001^a0)$, $a\ge0$ (a finite set of states), and from $\delta(0,1)$, by words of length at least 5;

• (R3): $\widehat{\omega}(1001^c w)=B_4[w]$ for $c\ge1$ and the 31 words $w$;

• (R4): $\ell_m[i]$ depends only on the parity of $m$, on $i\bmod3$, and on whether $i$ is one of the first four or last four positions; in the regions $101u$ and $110u$ the index $i$ is $\operatorname{val}(u)+1$ and $2^{|u|}+\operatorname{val}(u)+1$, so the expected value is computed by a small automaton tracking $\operatorname{val}(u)$ mod 3, the parity of $|u|$ and whether $u\in0^*,0^*1,0^*10$ (resp. $1^*,1^*0,1^*01$); the two remaining words $1001^{m-2},1110^{m-2}$ have value 1.

All these checks succeed for $c = 0$ and $c = 1$ (script, Part 5). Hence $\widehat{\omega} = \omega$, and $\chi_c(n+1) = \widehat{\omega}(n)$ for all $n$.

From $\mathcal{A}$ one builds an automaton $\mathcal{B}_c$ for $n \mapsto\chi_c(n) = \widehat{\omega}(n-1)$ whose states are the pairs (state of $\mathcal{A}$ on $n$, state of $\mathcal{A}$ on $n-1$), plus an initial state for $n = 0$: reading a digit updates both, since $2n+1-1 = 2n$ and $2n-1 = 2(n-1)+1$. All automata here read the most significant digit first and accept leading zeros. Minimising $\mathcal{B}_c$ gives 15 and 8 states. For the other reading direction, the minimal automaton reading least significant digits first has one state per element of the 2-kernel $\{n \mapsto\chi_c(2^k n + r) : k \ge0, 0 \le r < 2^k\}$ (by the Myhill–Nerode theorem; see [3 Section 6.6]). The kernel element of $(k,r)$ is the sequence $n \mapsto o(\delta(\sigma_n,w))$, where $\sigma_n$ is the state of $\mathcal{B}_c$ on $n$ and $w$ the $k$ digits of $r$. Every state of $\mathcal{B}_c$ is some $\sigma_n$, so two kernel elements are equal if and only if the maps $\sigma\mapsto o(\delta(\sigma,w))$ coincide on the states of $\mathcal{B}_c$. Enumerating these maps over all words $w$ gives 74 and 68. □

Proof of Corollary 1.3

By Proposition 5.2 and Theorem 5.1, the consecutive elements of $\Sigma_0 = \{d_0 < d_1 < \ldots\}$ differ by the degrees of the partial quotients of $t/f$, that is by 1 or 3, both occurring. By Niederreiter’s theorem, $L = L(b,N) = d_j$ with $d_{j-1} + d_j \le N < d_j + d_{j+1}$, so $2L - N \le d_j - d_{j-1} \le3$ and $2L - N \ge1 - (d_{j+1} - d_j) \ge-2$. If $d_j - d_{j-1} = 3$, the values 3, 2, 1, 0 occur on this interval of $N$; if $d_{j+1} - d_j = 3$, the values 1, 0, $-1$, $-2$ occur. □

Verification

The ancillary file verify_baum_sweet_hankel.py (Python 3, no dependency, exact arithmetic over $\mathbb{F}_2$, under a minute) performs all the finite checks used above: Lemma 4.1 (the set $\mathcal{F}$, the base cases and the seven boundary factors of each class $n$ mod 6); Theorem 5.1 (the 12 configurations, the certainty of every emission, the bookkeeping of $E-D$); and the rules (R1)–(R4) for $\mathcal{A}$, the base table, the minimal automata and the kernels. It also checks the statements against first principles: the Hankel determinants by Gaussian elimination for $n \le300$; the continued fractions of $\alpha_0$ and $\alpha_1$ by Euclid’s algorithm, against $\Gamma_\infty$ and against the automaton, for $n < 2^{16}$; and the linear complexity by the Berlekamp–Massey algorithm for $N \le3000$.

Acknowledgement

Acknowledgement. Technical assistance: Claude (Anthropic).