×

The formal inverse of the period-doubling sequence. (English) Zbl 1412.68176

The period-doubling sequence \((d_n)_{n\ge 0}\in\{0,1\}^{\mathbb{N}}\) is the fixed point of the morphism given by \(0\mapsto 01\) and \(1\mapsto 00\). It is quite a classical example of a 2-automatic sequence. Let \(D(X)=\sum_{n\ge 0} d_n X^n\) be the associated generating function. In this paper, the authors study its compositional inverse, i.e., a formal power series \(U(X)=\sum_{n\ge 0} u_n X^n\) such that \(U(D(X))=X=D(U(X))\). Following a method of M. Gawron and M. Ulas [Discrete Math. 339, No. 5, 1459–1470 (2016; Zbl 1338.11037)], they provide polynomial equations satisfied by \(U(X)\) and associated recurrence relations and show that the sequence \((u_n)_{n\ge 0}\) is \(2\)-automatic. Then the characteristic sequence of this formal inverse, i.e., the increasing sequence of indices such that \(u_n=1\), is shown to be \(k\)-regular for no \(k\). Surprisingly, Fibonacci numbers appear to be connected to these constructions.

MSC:

68R15 Combinatorics on words
11B85 Automata sequences
68Q45 Formal languages and automata

Citations:

Zbl 1338.11037

Software:

OEIS

References:

[1] G. Allouche, J.-P. Allouche and J. Shallit, Kolam indiens, dessins sur le sable aux ˆıles Vanuatu, courbe de Sierpi´nski et morphismes de mono¨ıde, Ann. Inst. Fourier (Grenoble) 56(2006), 2115-2130. · Zbl 1147.11015
[2] J.-P. Allouche, A. Andr´e, J. Berstel, S. Brlek, W. Jockusch, S. Plouffe and B. E. Sagan, A relative of the Thue-Morse sequence, Discrete Math. 139 (1995), 455-461. · Zbl 0839.11007
[3] J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and Their Applications, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, 1999, pp. 1-16. 20 · Zbl 1005.11005
[4] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003. · Zbl 1086.11015
[5] G . Christol, T. Kamae, M. Mend‘es France and G. Rauzy, Suite alg´ebriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401-419. · Zbl 0472.10035
[6] A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164-192. · Zbl 0253.02029
[7] F. Durand, Cobham’s theorem for substitutions, J. Eur. Math. Soc. 13 (2011), 1799– 1814. · Zbl 1246.11073
[8] P. Fatou, S´eries trigonom´etriques et s´eries de Taylor, Acta Math. 30 (1906), 335-400. · JFM 37.0283.01
[9] M. Gawron and M. Ulas, On formal inverse of the Prouhet-Thue-Morse sequence, Discrete Math. 339 (2016), 1459-1470. · Zbl 1338.11037
[10] L. Merta, Composition inverses of the variations of the Baum-Sweet sequence, 2018. Preprint available athttps://arxiv.org/abs/1803.00292. · Zbl 1452.11029
[11] L. Merta, Formal inverses of the generalized Thue-Morse sequences and variations of the Rudin-Shapiro sequence, 2018. Preprint available athttps://arxiv.org/abs/1810. 03533. · Zbl 1454.11058
[12] M. Rigo, Formal Languages, Automata and Numeration Systems. 1. Introduction to Combinatorics on Words, Networks and Telecommunications Series, John Wiley & Sons, 2014. · Zbl 1326.68002
[13] M. Rigo, Formal Languages, Automata and Numeration Systems. 2. Applications to Recognizability and Decidability, Networks and Telecommunications Series, John Wiley & Sons, 2014. · Zbl 1326.68003
[14] L. Schaeffer, Deciding Properties of Automatic Sequences, Master’s Thesis, University of Waterloo, Waterloo, Ontario, 2013.
[15] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,https://oeis.org. · Zbl 1044.11108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.