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.
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.
Jean-Paul Allouche 1
@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, Tome 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 -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 -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 in base , Publ. Math. Debrecen 79 (2011), 395–400. | MR | Zbl
[27] J.-M. Deshouillers, A footnote to The least non zero digit of in base , 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 -multiples in base , 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 , 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 and 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.
Cité par Sources :