\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\IfFileExists{geometry.sty}{\usepackage[margin=2.5cm]{geometry}}{}
\IfFileExists{hyperref.sty}{\usepackage[hidelinks]{hyperref}}{}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{fact}[theorem]{Fact}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\Fq}{\mathbf{F}_q}
\newcommand{\Fthree}{\mathbf{F}_3}
\newcommand{\Z}{\mathbf{Z}}

\title{The Hankel determinants of an automatic sequence\\ need not be automatic}
\author{David Niedbala Giraudin\\\small ORCID 0009-0009-1526-1178}
\date{}

\begin{document}
\maketitle

\begin{abstract}
Allouche, Han and Niederreiter asked whether the sequence of Hankel determinants of a $d$-automatic sequence must be $d$-regular, or must become $d$-automatic after reduction modulo an integer. We answer the first question in the negative, and the second one for the reduction modulo $3$. Let $\alpha$ be the root of $f^4+f^2-Tf+1=0$ in $\Fthree((1/T))$ with $|\alpha|<1$, the quartic of Mills and Robbins, and let $S$ be its coefficient sequence, which is $3$-automatic by Christol's theorem. The Hankel determinants of $S$ vanish in runs whose lengths are unbounded but of the order of the square root of their position, because the partial quotients of $\alpha$ are unbounded while its irrationality exponent is $2$; and a lemma of Schlage-Puchta forbids runs in that regime in an automatic sequence. Hence these Hankel determinants are $k$-automatic for no $k$, and the integer Hankel determinants of any lift of $S$ are $k$-regular for no $k$.
\end{abstract}

\section{Introduction}

Let $\mathbf{a}=(a_n)_{n \geq 0}$ be a sequence over a commutative ring and let
\[
H_n = \det\big(a_{i+j}\big)_{0 \leq i,j \leq n-1} \qquad (n \geq 1), \qquad H_0 = 1,
\]
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\`ere, Wen and Wen~\cite{APWW}, 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~\cite{Han16}; Bugeaud and Han~\cite{BH} gave a combinatorial proof of the Thue--Morse case; and Hu and Han~\cite{HH} established the automaticity of the reduced Hankel determinants modulo $2$ of an explicit family of automatic sequences. In the last section of~\cite{AHN} (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~\cite{HH} for positive results in that direction.

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

\begin{theorem}\label{thm:main}
Let $\alpha \in \Fthree((1/T))$ be the unique solution with $|\alpha|<1$ of
\begin{equation}\label{eq:MR}
f^4+f^2-Tf+1 = 0,
\end{equation}
let $S=(s_n)_{n \geq 0}$ be its coefficient sequence, which is $3$-automatic, and let $(H_n)_{n \geq 0}$ be the Hankel determinants of $S$ over $\Fthree$. Let $\widetilde{S}$ be the lift of $S$ to $\{0,1,2\} \subset \Z$ and let $(\widetilde{H}_n)_{n \geq 0}$ be the Hankel determinants of $\widetilde{S}$, computed in $\Z$. Then
\begin{enumerate}
\item[(a)] $(H_n)_{n \geq 0}$ is $k$-automatic for no $k \geq 2$; equivalently, $(\widetilde{H}_n \bmod 3)$ is $k$-automatic for no $k \geq 2$;
\item[(b)] $(\widetilde{H}_n)_{n \geq 0}$ is $k$-regular for no $k \geq 2$.
\end{enumerate}
\end{theorem}

The answer to the question of~\cite{AHN} 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~\eqref{eq:MR}, singled out by Mills and Robbins~\cite{MR} and whose continued fraction expansion was determined by Buck and Robbins~\cite{BR}, has unbounded partial quotients, which makes those runs unbounded; but its irrationality exponent is $2$, by a theorem of Lasjaunias~\cite{L97}, which forces the runs to be of the order of the square root of their position. A lemma of Schlage-Puchta~\cite{SP} 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~\cite{AAB}.

\section{Two classical facts}

Let $\Fq((1/T))$ be the field of formal Laurent series in $1/T$ with $|P/Q| = q^{\deg P - \deg Q}$, and let
\[
\alpha = \sum_{n \geq 1} \sigma_n T^{-n}, \qquad |\alpha| < 1,
\]
be irrational, with continued fraction $\alpha = [0;a_1,a_2,\dots]$, $a_i \in \Fq[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 \geq 0}$ with $s_n = \sigma_{n+1}$ be the coefficient sequence, with Hankel determinants $H_n$ as above.

\begin{fact}\label{fact:dict}
For every $n \geq 0$, $H_n \neq 0$ if and only if $n = d_j$ for some $j \geq 0$. Hence the zeros of $(H_n)$ occur in runs, the $j$-th of which occupies the integers strictly between $d_j$ and $d_{j+1}$ and has length $\deg a_{j+1}-1$.
\end{fact}

This is the classical correspondence between the Pad\'e 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~\cite{N88}.

\begin{fact}\label{fact:nu}
The irrationality exponent $\nu(\alpha) = -\limsup_{|Q| \to \infty} \log|\alpha-P/Q|/\log|Q|$ satisfies
\[
\nu(\alpha) = 2 + \limsup_{j \to \infty} \frac{\deg a_{j+1}}{d_j}.
\]
\end{fact}

See Lasjaunias~\cite[p.~214]{L00}.

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~\cite{AS03}, and that by the theorem of Christol, Kamae, Mend\`es France and Rauzy~\cite{CKMR} a Laurent series over $\Fq$ is algebraic over $\Fq(T)$ if and only if its coefficient sequence is $q$-automatic.

\section{The Mills--Robbins quartic}\label{sec:MR}

Mills and Robbins~\cite{MR} observed that~\eqref{eq:MR} has a unique root $\alpha$ with $|\alpha|<1$ in $\mathbf{F}_p((1/T))$ for every prime $p$, with a remarkable expansion for $p=3$. Buck and Robbins~\cite{BR} proved it: with
\begin{equation}\label{eq:BR}
\Omega_0 = \emptyset, \quad \Omega_1 = T, \quad \Omega_n = \Omega_{n-1},\,-T,\,\Omega_{n-2}^{(3)},\,-T,\,\Omega_{n-1} \quad (n \geq 2),
\end{equation}
where $\Omega^{(3)}$ denotes the sequence obtained by cubing each entry and the commas denote concatenation, one has $\alpha = [0;\Omega_\infty]$.

\begin{lemma}\label{lem:degrees}
Let $D_n$ be the sum of the degrees of the entries of $\Omega_n$ and $M_n$ the largest of them. Then
\[
D_n = \frac{3^n-1}{2}, \qquad M_n = 3^{\lfloor (n-1)/2 \rfloor} \qquad (n \geq 1),
\]
so that the partial quotients of $\alpha$ have unbounded degree and
\[
\deg a_{j+1} \leq 2\sqrt{d_j} \quad \text{for all large } j, \qquad \text{whence} \qquad \nu(\alpha) = 2 .
\]
\end{lemma}

\begin{proof}
From~\eqref{eq:BR}, $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} \leq M_n$ while $d_j \geq D_{n-1}$, and
\[
\frac{M_n}{\sqrt{D_{n-1}}} \leq \frac{3^{(n-1)/2}}{\sqrt{(3^{n-1}-1)/2}} \longrightarrow \sqrt{2},
\]
so $\deg a_{j+1} \leq 2\sqrt{d_j}$ for $j$ large. Hence $\deg a_{j+1}/d_j \to 0$, and Fact~\ref{fact:nu} gives $\nu(\alpha)=2$.
\end{proof}

That $\nu(\alpha)=2$ is the theorem of Lasjaunias~\cite{L97}, who proves the sharper two-sided estimate: there are constants $\lambda_1,\lambda_2>0$ with $|\alpha-P/Q| \leq |Q|^{-(2+\lambda_1/\sqrt{\deg Q})}$ for infinitely many $P/Q$ and $|\alpha-P/Q| \geq |Q|^{-(2+\lambda_2/\sqrt{\deg Q})}$ for all large $|Q|$. Only the elementary form above is used here.

Since $\alpha$ is algebraic over $\Fthree(T)$ by~\eqref{eq:MR}, its coefficient sequence $S$ is $3$-automatic by~\cite{CKMR}.

\section{The non-automaticity lemma}

\begin{lemma}[Schlage-Puchta {\cite[Thm.~3]{SP}}]\label{lem:sp}
Let $u=(u_n)_{n \geq 1}$ be an automatic sequence over a finite alphabet and let $\mathtt{a}$ be a letter such that $u$ contains runs of $\mathtt{a}$ of arbitrary length. Then there is a constant $c>0$ such that, for infinitely many integers $x$, one has $u_n = \mathtt{a}$ for every $n \in [x,(1+c)x]$.
\end{lemma}

The proof in~\cite{SP} 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~\cite{ASY}, where it is deduced from the theory of $k$-synchronized functions.

\section{Proof of Theorem~\ref{thm:main}}

\emph{Part (a).} Suppose $(H_n)_{n \geq 0}$ were $k$-automatic for some $k \geq 2$; it takes its values in the finite alphabet $\Fthree$. By Fact~\ref{fact:dict} and Lemma~\ref{lem:degrees} 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~\ref{lem:sp} 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} \geq x$; since $H_{d_{j+1}} \neq 0$ by Fact~\ref{fact:dict} while $H_n = 0$ throughout $[x,(1+c)x]$, in fact $d_{j+1} > (1+c)x$. Hence
\[
\deg a_{j+1} = d_{j+1}-d_j > (1+c)x - x = cx > c\,d_j .
\]
As $x$ runs through $X$ the index $j$ tends to infinity, so $\limsup_j \deg a_{j+1}/d_j \geq c > 0$. But Lemma~\ref{lem:degrees} gives $\deg a_{j+1}/d_j \leq 2/\sqrt{d_j} \to 0$, 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 $\widetilde{H}_n \equiv H_n \pmod 3$; any other lift of $S$ gives the same reduction.

\smallskip

\emph{Part (b).} The reduction modulo $m$ of a $k$-regular sequence is $k$-automatic for every $m \geq 1$~\cite{AS92}. If $(\widetilde{H}_n)$ were $k$-regular for some $k$, its reduction modulo $3$ would then be $k$-automatic, contradicting~(a). \qed

\section{Remarks}

\begin{remark}
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~\cite{AHN} --- are of course not touched by this argument, and several of them are automatic.
\end{remark}

\begin{remark}
The first half of the question of~\cite{AHN} 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.
\end{remark}

\section{Numerical verification}

The proof above uses three external results --- the expansion of~\cite{BR}, the theorem of~\cite{CKMR} and the lemma of~\cite{SP} --- and does not depend on any computation. The ancillary file \texttt{verify\_hankel.py} (Python~3 with \texttt{numpy}, about a minute) checks, in exact arithmetic over $\Fthree$, the following facts on the sequence of Section~\ref{sec:MR}. The series $\alpha$ is computed to $12\,000$ coefficients from~\eqref{eq:MR}. For the first $1\,307$ entries $a_{j+1}$ of $\Omega_\infty$, the convergents $P_j/Q_j$ built from~\eqref{eq:BR} satisfy $|Q_j\alpha-P_j|=3^{-d_{j+1}}$, so that these entries are indeed the partial quotients of $\alpha$. The Hankel determinants $H_n$, $0\le n\le 300$, computed by Gaussian elimination, are nonzero exactly at the degrees $d_j$, as Fact~\ref{fact:dict} states. The word $\Omega_{16}$ has $1\,136\,688$ entries, of degrees $1,3,9,\dots,2187$; the formulas of Lemma~\ref{lem:degrees} 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}$.

\paragraph{Acknowledgements.} Technical assistance: Claude (Anthropic).

\begin{thebibliography}{99}

\bibitem{AHN} J.-P. Allouche, G.-N. Han, H. Niederreiter, \emph{Perfect linear complexity profile and Apwenian sequences}, Finite Fields Appl. \textbf{68} (2020), Article 101761, 13 pp.; arXiv:2008.12160.

\bibitem{APWW} J.-P. Allouche, J. Peyri\`ere, Z.-X. Wen, Z.-Y. Wen, \emph{Hankel determinants of the Thue--Morse sequence}, Ann. Inst. Fourier (Grenoble) \textbf{48} (1998), 1--27.

\bibitem{AS92} J.-P. Allouche, J. Shallit, \emph{The ring of $k$-regular sequences}, Theoret. Comput. Sci. \textbf{98} (1992), 163--197.

\bibitem{AS03} J.-P. Allouche, J. Shallit, \emph{Automatic Sequences. Theory, Applications, Generalizations}, Cambridge University Press, 2003.

\bibitem{ASY} J.-P. Allouche, J. Shallit, R. Yassawi, \emph{How to prove that a sequence is not automatic}, arXiv:2104.13072 (2021).

\bibitem{AAB} K. Ayadi, A. Azaza, S. Beldi, \emph{Diophantine approximation and continued fraction expansion for quartic power series over $\mathbf{F}_3$}, Indian J. Pure Appl. Math. (2021), doi:10.1007/s13226-021-00203-8.

\bibitem{BH} Y. Bugeaud, G.-N. Han, \emph{A combinatorial proof of the non-vanishing of Hankel determinants of the Thue--Morse sequence}, Electron. J. Combin. \textbf{21} (2014), no.~3, Paper 3.26.

\bibitem{BR} M. Buck, D. Robbins, \emph{The continued fraction expansion of an algebraic power series satisfying a quartic equation}, J. Number Theory \textbf{50} (1995), 335--344.

\bibitem{CKMR} G. Christol, T. Kamae, M. Mend\`es France, G. Rauzy, \emph{Suites alg\'ebriques, automates et substitutions}, Bull. Soc. Math. France \textbf{108} (1980), 401--419.

\bibitem{Han16} G.-N. Han, \emph{Hankel continued fraction and its applications}, Adv. Math. \textbf{303} (2016), 295--321.

\bibitem{HH} Y. Hu, G.-N. Han, \emph{On the automaticity of the Hankel determinants of a family of automatic sequences}, Theoret. Comput. Sci. \textbf{795} (2019), 154--164.

\bibitem{L97} A. Lasjaunias, \emph{Diophantine approximation and continued fraction expansions of algebraic power series in positive characteristic}, J. Number Theory \textbf{65} (1997), 206--225.

\bibitem{L00} A. Lasjaunias, \emph{A survey of Diophantine approximation in fields of power series}, Monatsh. Math. \textbf{130} (2000), 211--229.

\bibitem{MR} W. H. Mills, D. P. Robbins, \emph{Continued fractions for certain algebraic power series}, J. Number Theory \textbf{23} (1986), 388--404.

\bibitem{N88} H. Niederreiter, \emph{Sequences with almost perfect linear complexity profile}, in: Advances in Cryptology --- EUROCRYPT '87, Lecture Notes in Comput. Sci. \textbf{304}, Springer, 1988, 37--51.

\bibitem{SP} J.-C. Schlage-Puchta, \emph{A criterion for non-automaticity of sequences}, J. Integer Seq. \textbf{6} (2003), Article 03.3.8.

\end{thebibliography}

\end{document}