staple
With cedram.org

Search the site

Table of contents for this issue | Previous article | Next article
Jean-Paul Allouche
Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence
Journal de théorie des nombres de Bordeaux, 27 no. 2 (2015), p. 375-388, doi: 10.5802/jtnb.906
Article PDF | Reviews MR 3393159
Class. Math.: 11B85, 68R15

Résumé - Abstract

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.

Bibliography

[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. Cedram |  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 |  JFM 48.1208.02
[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 |  JFM 37.0283.01
[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 |  JFM 48.0786.06
[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.  JFM 39.0283.01
[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.  JFM 44.0462.01
[62] D. R. Woods, Elementary problem proposal E 2692, Amer. Math. Monthly 85 (1978), 48.