On the automaticity of the Hankel determinants of a family of automatic sequences

DOI10.1016/J.TCS.2019.06.009MaRDI QIDQ2330106zbMATH OpenOpenAlexFDO

Authors Yining Hu, Guo-Niu Han

Publication date 18 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.05864

zbMATH Keywords

automatic sequence Hankel determinant irrationality exponent

Mathematics Subject Classification ID

Automata sequences (11B85) Measures of irrationality and of transcendence (11J82)

Abstract: Hankel determinants and automatic sequences are two classical subjects widely studied in Mathematics and Theoretical Computer Science. However, these two topics were considered totally independently, until in 1998, when Allouche, Peyri`ere, Wen and Wen proved that all the Hankel determinants of the Thue-Morse sequence are nonzero. This property allowed Bugeaud to prove that the irrationality exponents of the Thue-Morse-Mahler numbers are exactly 2. Since then, the Hankel determinants of several other automatic sequences, in particular, the paperfolding sequence, the Stern sequence, the period-doubling sequence, are studied by Coons, Vrbik, Guo, Wu, Wen, Bugeaud, Fu, Han, Fokkink, Kraaikamp, and Shallit. On the other hand, it is known that the Hankel determinants of a rational power series are ultimately zero, and the Hankel determinants of a quadratic power series over finite fields are ultimately periodic. It is therefore natural to ask if we can obtain similar results about the Hankel determinants of algebraic series. In the present paper, we provide a partial answer to this question by establishing the automaticity of the reduced Hankel determinants modulo

2

of

p m 1

-automatic sequences with kernel of cardinality at most

2

.

Review text

The paper is concerned with a family of automatic sequences which generalises the Thue-Morse sequence. Let \(d\ge 2\) be a positive integer and \(\mathbf{v} = \{v_1,v_2,\ldots,v_{d-1}\}\) be a \(\pm1\) sequence with \(v_0=1\). The generating function of \(\mathbf{v}\) is \(\tilde{\mathbf{v}}(x) = \sum_{i=0}^{d-1} v_ix^i\). Define the \(\pm1\) sequence \(\mathbf{f}\) by the power series \(\tilde{\mathbf{f}}(x) = \sum_{n=0}^\infty f_nx^n = \prod_{k=0}^\infty\tilde{\mathbf{v}}(x^{d^k})\) so that \(f_n = \prod_{i=1}^{d-1} v_i^{s_{d,i}(n)}\) where \(s_{d,i}(n)\) counts the number of occurrences of the digit \(i\) in the base \(d\) representation of \(n\). The power series \(\tilde{\mathbf{f}}\) is an example of a Mahler function and satisfies the functional equation \(\tilde{\mathbf{f}}(x) = \tilde{\mathbf{v}}(x)\tilde{\mathbf{f}}(x^d)\), giving the recurrence relations \(f_0=1, f_{dn+1}=v_if_n\) for \(n\ge 0, 0\le i\le d-1\). Let \(H_n(\mathbf{f})\) be the \(n\times n\) Hankel determinant of the sequence \(\mathbf{f}\). Since the Hankel determinant of order \(n\) of a \(\pm1\) sequence is always divisible by \(2^{n-1}\), define the reduced Hankel determinant \(H_n(\mathbf{f})/2^{n-1}\).The main result of the paper is that the sequence of reduced Hankel determinants modulo 2 is \(d\)-automatic. \textit{J.-P. Allouche} et al. [Ann. Inst. Fourier 48, No. 1, 1--27 (1998; Zbl 0974.11010)] proved that the Hankel determinants of the Thue-Morse sequence are non-zero. The proof of automaticity in the paper uses an algorithm of \textit{H. Fu} and \textit{G.-N. Han} [in: Proceedings of the 41st international symposium on symbolic and algebraic computation, ISSAC 2016, New York, NY: ACM, 231--238 (2016; Zbl 1364.11070)]. Two examples are given to illustrate the algorithm and exhibit the recurrence relations and the minimal automaton whose output is the sequence of reduced Hankel determinants modulo 2. \textit{Y. Bugeaud} et al. [Int. Math. Res. Not. 2016, No. 5, 1467--1496 (2016; Zbl 1415.11101)] showed that if \(f(x)\) is a Mahler function and \(b\ge 2\) is an integer satisfying certain regularity conditions and there is an increasing sequence of positive integers \((a_i)_{i\ge 0}\) such that \(H_{a_i}(f) \ne 0\) for all integers \(i\ge 0\) and \(\lim\sup_{i\rightarrow \infty} a_{i+1}/a_i = \rho\), then \(f(1/b)\) is transcendental and its irrationality exponent satisfies \(\mu(f(1/b)) \le (1+\rho)\min\{\rho^2,d\}\). These conditions are satisfied by the automatic sequences considered in the paper because the reduced Hankel determinants are automatic. In particular, if \(\rho=1\) then the irrationality exponent of \(f(1/b)\) is 2. Bugeaud et al. showed that this applies to the Thue-Morse sequence which therefore has irrationality exponent exactly 2.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: On the automaticity of the Hankel determinants of a family of automatic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330106)