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.
Reviewer: Michel Rigo (Liège)
Keywords:
formal inverse; period-doubling sequence; Fibonacci sequence; automatic sequence; \(k\)-regular sequence; Christol’s theoremCitations:
Zbl 1338.11037Software:
OEISOnline Encyclopedia of Integer Sequences:
Utterly odd numbers: numbers whose binary representation ends in an odd number of ones.Period-doubling sequence (or period-doubling word): fixed point of the morphism 0 -> 01, 1 -> 00.
Numbers whose binary expansion ends in an even number of 1’s.
Formal inverse of the period-doubling sequence A096268.
Positions of 1’s in A317542, the formal inverse of the period-doubling sequence A096268.
Positions of 0’s in A317542, the formal inverse of the period-doubling sequence A096268.
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.