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, p. 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 : https://doi.org/10.5802/jtnb.906
Classification:  11B85,  68R15
@article{JTNB_2015__27_2_375_0,
     author = {Allouche, Jean-Paul},
     title = {Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {27},
     number = {2},
     year = {2015},
     pages = {375-388},
     doi = {10.5802/jtnb.906},
     mrnumber = {3393159},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2015__27_2_375_0}
}
Allouche, Jean-Paul. 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. http://www.numdam.org/item/JTNB_2015__27_2_375_0/

[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 3129155 | Zbl 1289.11025

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

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

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

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

[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 1843077 | Zbl 1005.11005

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

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

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

[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 2730738 | Zbl 1196.62104

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

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

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

[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 1279058 | Zbl 0810.11016

[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 2251109 | Zbl 1132.11012

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

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

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

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

[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 1071744 | Zbl 0705.12006

[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 614317 | Zbl 0472.10035

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

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

[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 2907974 | Zbl 1249.11044

[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 2943161

[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 1555035

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

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

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

[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 1578830 | Zbl 045.1235cj

[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 3277474

[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 2956425 | Zbl 1258.91020

[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 3032385 | Zbl 1290.05013

[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 2680394 | Zbl 1213.11025

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

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

[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 1942263 | Zbl 1167.43300

[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 http://arxiv.org/abs/0710.3177 | MR 2337257

[48] V. Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, Preprint (2007), available electronically at http://arxiv.org/abs/0710.1354

[49] V. Shevelev, Two digit theorems, Preprint (2007), available electronically at http://arxiv.org/abs/0710.0144

[50] V. Shevelev, New digit results and several problems, Preprint (2007), available electronically at http://arxiv.org/abs/0709.3821

[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 http://arxiv.org/abs/0709.0885

[52] V. Shevelev, A conjecture on primes and a step towards justification, Preprint (2007), available electronically at http://arxiv.org/abs/0706.0786

[53] V. Shevelev, On excess of the odious primes, Preprint (2007), available electronically at http://arxiv.org/abs/0707.1761

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

[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 2469946 | Zbl 1232.11012

[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 http://arxiv.org/abs/0907.0880

[57] V. Shevelev, P. J. C. Moses, A family of digit functions with large periods, Preprint (2012), available electronically at http://arxiv.org/abs/1209.5705

[58] V. Shevelev, P. J. C. Moses, Tangent power sums and their applications, Preprint (2012), available electronically at http://arxiv.org/abs/1207.0404 | MR 3285131

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

[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.