The Hankel determinants of an automatic sequence need not be automatic

Introduction

Let $\mathbf{a}=(a_n)_{n\geq0}$ be a sequence over a commutative ring and let

be its Hankel determinants. When $\mathbf{a}$ is automatic, these determinants have repeatedly turned out to be automatic as well. All the Hankel determinants of the Thue–Morse sequence are nonzero, by the sixteen simultaneous recurrences of Allouche, Peyrière, Wen and Wen [2], who also obtained the corresponding two-dimensional array as a substitution tiling; the Hankel determinants of a quadratic power series over a finite field are ultimately periodic [10]; Bugeaud and Han [7] gave a combinatorial proof of the Thue–Morse case; and Hu and Han [11] established the automaticity of the reduced Hankel determinants modulo 2 of an explicit family of automatic sequences. In the last section of [1] (Section 6 of the arXiv version), Allouche, Han and Niederreiter accordingly ask whether the sequence of Hankel determinants of a $d$-automatic sequence must be a $d$-regular sequence, or must become $d$-automatic once reduced modulo some integer, and point to [11] for positive results in that direction.

The purpose of this note is to show that neither holds in general.

The answer to the question of [1] is therefore negative: outright for the regularity half, and modulo 3 for the reduction half. Statement (a) does not depend on the chosen lift, since any two lifts agree modulo 3.

The mechanism is Diophantine rather than combinatorial. By the classical dictionary between Hankel determinants and continued fractions, $H_n$ vanishes exactly when $n$ is not the degree of a convergent denominator of $\alpha$, so that a partial quotient of degree $D$ produces a run of $D-1$ consecutive zeros. The quartic (1), singled out by Mills and Robbins [14] and whose continued fraction expansion was determined by Buck and Robbins [8], has unbounded partial quotients, which makes those runs unbounded; but its irrationality exponent is 2, by a theorem of Lasjaunias [12], which forces the runs to be of the order of the square root of their position. A lemma of Schlage-Puchta [16] states that an automatic sequence with unbounded runs of a letter must have runs of length proportional to their position. The two requirements are incompatible. That combination — unbounded partial quotients together with the extremal exponent 2 — is what makes this particular sequence available: for a long time no other algebraic Laurent series was known to have it [6].

Two classical facts

Let $\mathbb{F}_q((1/T))$ be the field of formal Laurent series in $1/T$ with $\lvert P/Q\rvert=q^{\deg P-\deg Q}$, and let

be irrational, with continued fraction $\alpha=[0;a_1,a_2,\ldots]$, $a_i\in\mathbb{F}_q[T]$, and convergents $P_j/Q_j$. Put $d_j=\deg Q_j=\sum_{1\leq i\leq j}\deg a_i$, so $d_0=0$, and let $S=(s_n)_{n\geq0}$ with $s_n=\sigma_{n+1}$ be the coefficient sequence, with Hankel determinants $H_n$ as above.

This is the classical correspondence between the Padé table of $\alpha$ and its continued fraction expansion; in the language of stream ciphers it is equivalent to Niederreiter’s description of the linear complexity profile [15].

See Lasjaunias [13 p. 214].

Recall finally that a sequence over a finite alphabet is $k$-automatic if it is produced by a finite automaton reading the base-$k$ expansion of the index [4], and that by the theorem of Christol, Kamae, Mendès France and Rauzy [9] a Laurent series over $\mathbb{F}_q$ is algebraic over $\mathbb{F}_q(T)$ if and only if its coefficient sequence is $q$-automatic.

The Mills–Robbins quartic

Mills and Robbins [14] observed that (1) has a unique root $\alpha$ with $\lvert\alpha\rvert<1$ in $\mathbb{F}_p((1/T))$ for every prime $p$, with a remarkable expansion for $p=3$. Buck and Robbins [8] proved it: with

where $\Omega^{(3)}$ denotes the sequence obtained by cubing each entry and the commas denote concatenation, one has $\alpha=[0;\Omega_\infty]$.

Lemma 3.1. Let $D_n$ be the sum of the degrees of the entries of $\Omega_n$ and $M_n$ the largest of them. Then

so that the partial quotients of $\alpha$ have unbounded degree and

Proof. From (2), $D_n=2D_{n-1}+3D_{n-2}+2$ with $D_0=0$, $D_1=1$, and $M_n=\max(M_{n-1},3M_{n-2},1)$ with $M_0=0$, $M_1=1$; both closed forms follow by induction. Given a partial quotient $a_{j+1}$, let $n$ be least such that $a_{j+1}$ occurs in $\Omega_n$ but not in its initial segment $\Omega_{n-1}$. Then $\deg a_{j+1}\le M_n$ while $d_j\ge D_{n-1}$, and

so $\deg a_{j+1}\le2\sqrt{d_j}$ for $j$ large. Hence $\deg a_{j+1}/d_j\to0$, and Fact 2.2 gives $\nu(\alpha)=2$. □

That $\nu(\alpha)=2$ is the theorem of Lasjaunias [12], who proves the sharper two-sided estimate: there are constants $\lambda_1,\lambda_2>0$ with $|\alpha-P/Q|\le|Q|^{-(2+\lambda_1/\sqrt{\deg Q})}$ for infinitely many $P/Q$ and $|\alpha-P/Q|\ge|Q|^{-(2+\lambda_2/\sqrt{\deg Q})}$ for all large $|Q|$. Only the elementary form above is used here. Since $\alpha$ is algebraic over $\mathbb{F}_3(T)$ by (1), its coefficient sequence $S$ is 3-automatic by [9].

The non-automaticity lemma

Lemma 4.1 (Schlage-Puchta [16 Thm. 3]). Let $u=(u_n)_{n\ge1}$ be an automatic sequence over a finite alphabet and let $a$ be a letter such that $u$ contains runs of $a$ of arbitrary length. Then there is a constant $c>0$ such that, for infinitely many integers $x$, one has $u_n=a$ for every $n\in[x,(1+c)x]$.

The proof in [16] is short: one pumps the leading digits of the base-$k$ expansion and uses the finiteness of the state set. The statement is also recorded as Example 15 of the survey [5], where it is deduced from the theory of $k$-synchronized functions.

Proof of Theorem 1.1

Part (a). Suppose $(H_n)_{n\ge0}$ were $k$-automatic for some $k\ge2$; it takes its values in the finite alphabet $\mathbb{F}_3$. By Fact 2.1 and Lemma 3.1 it contains runs of the letter 0 of arbitrary length, the $j$-th run having length $\deg a_{j+1}-1$ and the degrees of the partial quotients being unbounded. Lemma 4.1 then provides $c>0$ and an infinite set $X$ of integers such that $H_n=0$ for all $n\in[x,(1+c)x]$ and all $x\in X$.

Fix $x\in X$ large and let $j$ be the largest index with $d_j<x$; it exists because $d_0=0<x$ and $d_j\to\infty$. By maximality $d_{j+1}\ge x$; since $H_{d_{j+1}}\ne0$ by Fact 2.1 while $H_n=0$ throughout $[x,(1+c)x]$, in fact $d_{j+1}>(1+c)x$. Hence

As $x$ runs through $X$ the index $j$ tends to infinity, so $\limsup_j\deg a_{j+1}/d_j\ge c>0$. But Lemma 3.1 gives $\deg a_{j+1}/d_j\le2/\sqrt{d_j}\to0$, a contradiction.

For the second formulation, a determinant is a polynomial with integer coefficients in its entries, so reduction modulo 3 commutes with it and $\overline{H}_n\equiv H_n\pmod3$; any other lift of $S$ gives the same reduction.

Part (b). The reduction modulo $m$ of a $k$-regular sequence is $k$-automatic for every $m\ge1$ [3]. If $(\overline{H}_n)$ were $k$-regular for some $k$, its reduction modulo 3 would then be $k$-automatic, contradicting (a). □

Remarks

Remark 6.1. The obstruction is a matter of scale, not of shape. Zero runs that are bounded are compatible with automaticity, and so are zero runs of length proportional to their position; what no automatic sequence can have is runs which are unbounded and yet sublinear, and that is exactly what the exponent 2 imposes here. Sequences at the opposite extreme, those with no zero at all in their Hankel determinants — the sequences with perfect linear complexity profile, equivalently the apwenian sequences of [1] — are of course not touched by this argument, and several of them are automatic.

Remark 6.2. The first half of the question of [1] is thus settled in full: no $k$ makes $(\widetilde{H}_n)$ regular. For the second half, what is proved here is that the reduction modulo 3 — the modulus in which the sequence itself is defined — is automatic in no base; the behaviour of $(\widetilde{H}_n \bmod m)$ for other moduli $m$ is not addressed.

Numerical verification

The proof above uses three external results — the expansion of [8], the theorem of [9] and the lemma of [16] — and does not depend on any computation. The ancillary file verify_hankel.py (Python 3 with numpy, about a minute) checks, in exact arithmetic over $\mathbb{F}_3$, the following facts on the sequence of § 3. The series $\alpha$ is computed to 12 000 coefficients from (1). For the first 1 307 entries $a_{j+1}$ of $\Omega_\infty$, the convergents $P_j/Q_j$ built from (2) satisfy $\lvert Q_j\alpha-P_j\rvert=3^{-d_{j+1}}$, so that these entries are indeed the partial quotients of $\alpha$. The Hankel determinants $H_n$, $0\le n\le300$, computed by Gaussian elimination, are nonzero exactly at the degrees $d_j$, as Fact 2.1 states. The word $\Omega_{16}$ has 1 136 688 entries, of degrees $1,3,9,\ldots,2187$; the formulas of Lemma 3.1 hold for $n\le16$, and the largest value of $\deg a_{j+1}/d_j$ over the range $2^{24}\le d_j<2^{25}$ is about $1.2\cdot10^{-4}$.

Acknowledgements. Technical assistance: Claude (Anthropic).