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.
@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}, 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 = {http://www.numdam.org/articles/10.5802/jtnb.906/} }
TY - JOUR AU - Allouche, Jean-Paul 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 - http://www.numdam.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 Allouche, Jean-Paul %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 http://www.numdam.org/articles/10.5802/jtnb.906/ %R 10.5802/jtnb.906 %G en %F 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, Tome 27 (2015) no. 2, pp. 375-388. doi : 10.5802/jtnb.906. http://www.numdam.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
[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
[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
[27] J.-M. Deshouillers, A footnote to The least non zero digit of
[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
[48] V. Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root
[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
[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.
- Characterizations of families of morphisms and words via binomial complexities, European Journal of Combinatorics, Volume 118 (2024), p. 35 (Id/No 103932) | DOI:10.1016/j.ejc.2024.103932 | Zbl:7824157
- Infinite products involving the period-doubling sequence, Monatshefte für Mathematik, Volume 203 (2024) no. 4, pp. 765-778 | DOI:10.1007/s00605-023-01923-1 | Zbl:1541.11027
- Lattice paths and the Prouhet-Thue-Morse sequence, Theoretical Computer Science, Volume 1022 (2024), p. 7 (Id/No 114885) | DOI:10.1016/j.tcs.2024.114885 | Zbl:7952129
- , 2023 IEEE International Symposium on Information Theory (ISIT) (2023), p. 1294 | DOI:10.1109/isit54713.2023.10206676
- Pseudoperiodic words and a question of Shevelev, Discrete Mathematics and Theoretical Computer Science. DMTCS, Volume 25 (2023) no. 2, p. 25 (Id/No 5) | DOI:10.46298/dmtcs.9919 | Zbl:7908406
- Linear combinations of Dirichlet series associated with the Thue-Morse sequence, Integers, Volume 22 (2022), p. paper | Zbl:1511.11078
- The zeta-regularized product of odious numbers, Advances in Applied Mathematics, Volume 126 (2021), p. 8 (Id/No 101944) | DOI:10.1016/j.aam.2019.101944 | Zbl:1469.11348
- Minimal automaton for multiplying and translating the Thue-Morse set, The Electronic Journal of Combinatorics, Volume 28 (2021) no. 3, p. research | DOI:10.37236/9068 | Zbl:1517.68179
- Greedy approximations by signed harmonic sums and the Thue-Morse sequence, Advances in Mathematics, Volume 366 (2020), p. 42 (Id/No 107068) | DOI:10.1016/j.aim.2020.107068 | Zbl:1436.11080
- State Complexity of the Multiples of the Thue-Morse Set, Electronic Proceedings in Theoretical Computer Science, Volume 305 (2019), p. 34 | DOI:10.4204/eptcs.305.3
- State complexity of the multiples of the Thue-Morse set, Proceedings of the tenth international symposium on games, automata, logics, and formal verification, GandALF 2019, Bordeaux, France, September 2–3, 2019, Waterloo: Open Publishing Association (OPA), 2019, pp. 34-49 | Zbl:1543.68165
- Infinite Products Involving Binary Digit Sums, Recent Advances in Mathematical and Statistical Methods, Volume 259 (2018), p. 59 | DOI:10.1007/978-3-319-99719-3_6
- Anti-power prefixes of the Thue-Morse word, The Electronic Journal of Combinatorics, Volume 24 (2017) no. 1, p. research | Zbl:1355.05005
- Selected non-holonomic functions in lattice statistical mechanics and enumerative combinatorics, Journal of Physics A: Mathematical and Theoretical, Volume 49 (2016) no. 7, p. 074001 | DOI:10.1088/1751-8113/49/7/074001
Cité par 14 documents. Sources : Crossref, zbMATH