Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence
Journal de théorie des nombres de Bordeaux, Volume 27 (2015) no. 2, pp. 375-388.

We describe some recent results on the Thue-Morse sequence. We also list open questions and conjectures, one of which is due to Shevelev and proved in this paper.

Nous décrivons quelques résultats récents sur la suite de Thue-Morse, ainsi que des questions ou conjectures, dont l’une, due à Shevelev, est résolue dans cet article.

DOI: 10.5802/jtnb.906
Classification: 11B85, 68R15
Jean-Paul Allouche 1

1 Institut de Mathématiques de Jussieu-PRG Équipe Combinatoire et Optimisation Université Pierre et Marie Curie, Case 247 4 Place Jussieu F-75252 Paris Cedex 05 France
@article{JTNB_2015__27_2_375_0,
     author = {Jean-Paul Allouche},
     title = {Thue, {Combinatorics} on words, and conjectures inspired by the {Thue-Morse} sequence},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {375--388},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {27},
     number = {2},
     year = {2015},
     doi = {10.5802/jtnb.906},
     mrnumber = {3393159},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.906/}
}
TY  - JOUR
AU  - Jean-Paul Allouche
TI  - Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2015
SP  - 375
EP  - 388
VL  - 27
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.906/
DO  - 10.5802/jtnb.906
LA  - en
ID  - JTNB_2015__27_2_375_0
ER  - 
%0 Journal Article
%A Jean-Paul Allouche
%T Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence
%J Journal de théorie des nombres de Bordeaux
%D 2015
%P 375-388
%V 27
%N 2
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.906/
%R 10.5802/jtnb.906
%G en
%F JTNB_2015__27_2_375_0
Jean-Paul Allouche. Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence. Journal de théorie des nombres de Bordeaux, Volume 27 (2015) no. 2, pp. 375-388. doi : 10.5802/jtnb.906. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.906/

[1] I. Abou, P. Liardet, Mixing of Prouhet-Thue-Morse and Rudin-Shapiro sequences, Annales Univ. Sci. Budapest., Sect. Comp. 40 (2013), 55–67. | MR | Zbl

[2] J.-P. Allouche, Transcendence of formal power series with rational coefficients, Theoret. Comput. Sci. 218 (1999), 143–160. | MR | Zbl

[3] J.-P. Allouche, Automates et algébricités, J. Théor. Nombres Bordeaux 17 (2005), 1–11. | Numdam | MR | Zbl

[4] J.-P. Allouche, H. Cohen, Dirichlet series and curious infinite products, Bull. Lond. Math. Soc. 17 (1985), 531–538. | MR | Zbl

[5] J.-P. Allouche, J. Shallit, Infinite products associated with counting blocks in binary strings, J. Lond. Math. Soc. 39 (1989), 193–204. | MR | Zbl

[6] J.-P. Allouche, J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and their Applications (Singapore, 1998), 1–16, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 1999. | MR | Zbl

[7] J.-P. Allouche, J. Shallit, Automatic Sequences. Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 2003. | MR | Zbl

[8] J.-P. Allouche, J. Sondow, Infinite products with strongly B-multiplicative exponents, Annales Univ. Sci. Budapest., Sect. Comp. 28 (2008), 35–53. | MR | Zbl

[9] N. Alon, J. Grytzuk, M. Hałuszczak, O. Riordan, Non-repetitive colorings of graphs, Random. Struct. Algor. 21 (2002), 336–346. | MR | Zbl

[10] R. A. Bates, H. Maruri-Aguilar, E. Riccomagno, R. Schwabe, H. P. Wynn, Self-avoiding generating sequences for Fourier lattice designs, in Algebraic Methods in Statistics and Probability II: Ams Special Session Algebraic Methods in Statistics and Probability, March 27-29, 2009, University Of Illinois at Urbana-Champaign, Eds. M. A. G. Viana, H. P. Wynn, Contemporary Mathematics 516 (2010), 37–47. | MR | Zbl

[11] E. Berlekamp, J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, vol. 1 and 2, Academic Press, 1982. | MR | Zbl

[12] E. Berlekamp, J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, vol. 3, Second Edition, A. K. Peters, 2003. | MR | Zbl

[13] C. Bernhardt, Evil twins alternate with odious twins, Math. Mag. 82 (2009), 57–62. | Zbl

[14] J. Berstel, Axel Thue’s papers on repetitions in words: a translation, Publications du LaCIM, Département de mathématiques et d’informatique 20, Université du Québec à Montréal, 1995, 85 pages. Electronic version available at http://lacim.uqam.ca/publications_pdf/20.pdf

[15] P. Borwein, C. Ingalls, The Prouhet-Tarry-Escott problem revisited, Enseign. Math. 40 (1994), 3–27. | MR | Zbl

[16] S. J. Brams, A. D. Taylor, The Win-Win Solution: Guaranteeing Fair Shares to Everybody, Norton, New York, 1999.

[17] X. Le Breton, Linear independence of automatic formal power series, Discr. Math. 306 (2006), 1776–1780. | MR | Zbl

[18] Y. Bugeaud, Distribution Modulo One and Diophantine Approximation, Cambridge Tracts in Mathematics 193, Cambridge University Press, Cambridge, 2012. | MR | Zbl

[19] F. Carlson, Über Potenzreihen mit ganzzahligen Koeffizienten, Math. Zeitschift 9 (1921), 1–13. | MR

[20] A. Černý, On Prouhet’s solution to the equal powers problem, Theoret. Comput. Sci. 491 (2013), 33–46. | MR | Zbl

[21] G. Christol, Ensembles presque périodiques k-reconnaissables, Theoret. Comput. Sci. 9 (1979), 141–145. | MR | Zbl

[22] G. Christol, Globally bounded solutions of differential equation, in Analytic number theory (Tokyo, 1988), Lecture Notes in Math., 1434, Springer, Berlin, (1990), 45–64. | MR | Zbl

[23] G. Christol, T. Kamae, M. Mendès France, G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401–419. | Numdam | MR | Zbl

[24] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 1969, 186–192. | MR | Zbl

[25] J. Cooper, A. Dutle, Greedy Galois games, Amer. Math. Monthly 120 (2013), 441–451. | MR | Zbl

[26] J.-M. Deshouillers, I. Z. Ruzsa, The least non zero digit of n! in base 12, Publ. Math. Debrecen 79 (2011), 395–400. | MR | Zbl

[27] J.-M. Deshouillers, A footnote to The least non zero digit of n! in base 12, Unif. Distrib. Theory 7 (2012), 71–73. | MR

[28] J.-M. Deshouillers, Private communication.

[29] G. Eisenstein, Über eine allgemeine Eigenschaft der Reihenentwicklungen aller algebraischen Funktionen, Berlin. Sitzber. (1852), 441–443.

[30] P. Fatou, Séries trigonométriques et séries de Taylor, Acta Math. 30 (1906), 335–400. | MR

[31] P. Flajolet, G. N. Martin, Probabilistic counting algorithms for data base applications, J. Comput. Sys. Sci. 31 (1985), 182–209. | MR | Zbl

[32] A. S. Fraenkel, Aperiodic subtraction games, Electron. J. Combin. 18 (2011), Paper 19. | MR | Zbl

[33] A. S. Fraenkel, The vile, dopey, evil and odious game players, Discr. Math. 312 (2012), 42–46. | MR | Zbl

[34] G. Hansel, À propos d’un théorème de Cobham, in Actes de la fête des mots, D. Perrin Éd., GRECO de programmation, Rouen (1982).

[35] E. Heine, Der Eisensteinsche Satz über Reihen-Entwicklung algebraischer Functionen, J. Reine Angew. Math. 45 (1853), 285–302. | MR | Zbl

[36] C. Kuzmics, T. Palfrey, B. W. Rogers, Symmetric play in repeated allocation games, Preprint, Bielfeld, Institute of Mathematical Economics, 468 (2012), available at the URL http://ssrn.com/abstract=2106108 | MR

[37] L. Levine, K. E. Stange, How to make the most of a shared meal: plan the last bite first, Amer. Math. Monthly 119 (2012), 550–565. | MR | Zbl

[38] G. Louchard, H. Prodinger, The largest missing value in a composition of an integer and some Allouche-Shallit-type identities, J. Integer Seq. 16, Article 13.2.2 (2013), 16 | MR | Zbl

[39] C. Mauduit, J. Rivat, Sur un problème de Gelfond : la somme des chiffres des nombres premiers, Ann. of Math. (2) 171 (2010), 1591–1646. | MR | Zbl

[40] M. Mendès France, Nombres normaux. Applications aux fonctions pseudo-aléatoires, J. Analyse Math. 20 (1967), 1–56. | MR | Zbl

[41] M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 22 (1921), 84–100. | MR

[42] On-Line Encyclopedia of Integer Sequences, available electronically at http://oeis.org

[43] I. Palacios-Huerta, Tournaments, fairness and the Prouhet-Thue-Morse sequence, Economic inquiry 50 (2012), 848–849.

[44] E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, C. R. Acad. Sci. Paris 33 (1851), 225. See also http://upload.wikimedia.org/wikipedia/commons/c/c2/NoteProuhet.png

[45] R. M. Richman, Recursive binary sequences of differences, Complex Systems 13 (2001), 381–392. | MR | Zbl

[46] D. Robbins, Solution to Problem E 2692, Amer. Math. Monthly 86 (1979), 394-395.

[47] V. Shevelev, On monotonic strengthening of Newman-like phenomenon on (2m+1)-multiples in base 2m, Preprint (2007), available electronically at | arXiv | MR

[48] V. Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, Preprint (2007), available electronically at | arXiv

[49] V. Shevelev, Two digit theorems, Preprint (2007), available electronically at | arXiv

[50] V. Shevelev, New digit results and several problems, Preprint (2007), available electronically at | arXiv

[51] V. Shevelev, Two algorithms for evaluation of the Newman digit sum, and a new proof of Coquet’s theorem, Preprint (2007), available electronically at | arXiv

[52] V. Shevelev, A conjecture on primes and a step towards justification, Preprint (2007), available electronically at | arXiv

[53] V. Shevelev, On excess of the odious primes, Preprint (2007), available electronically at | arXiv

[54] V. Shevelev, Generalized Newman phenomena and digit conjectures on primes, Int. J. Math. Math. Sci. (2008) Art. ID 908045, 12. | MR | Zbl

[55] V. Shevelev, Exact exponent in the remainder term of Gelfond’s digit theorem in the binary case, Acta Arith. 136 (2009), 91–100. | MR | Zbl

[56] V. Shevelev, Equations of the form t(x+a)=t(x) and t(x+a)=1-t(x) for Thue-Morse sequence, Preprint 2009 and 2012, available electronically at | arXiv

[57] V. Shevelev, P. J. C. Moses, A family of digit functions with large periods, Preprint (2012), available electronically at | arXiv

[58] V. Shevelev, P. J. C. Moses, Tangent power sums and their applications, Preprint (2012), available electronically at | arXiv | MR

[59] R. P. Stanley, Differentiably finite power series, European J. Combin. 1 (1980), 175–188. | MR | Zbl

[60] A. Thue, Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1–22. Reprinted in Selected mathematical papers of Axel Thue, T. Nagell, ed., Universitetsforlaget, Oslo, (1977), 139–158.

[61] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1–67. Reprinted in Selected mathematical papers of Axel Thue, T. Nagell, ed., Universitetsforlaget, Oslo, (1977), 413–478.

[62] D. R. Woods, Elementary problem proposal E 2692, Amer. Math. Monthly 85 (1978), 48.

Cited by Sources: