The Thue–Morse–Pascal double sequence and similar structures

Mihai Prunescu

doi:10.1016/j.crma.2011.07.022

Combinatorics/Number Theory

The Thue–Morse–Pascal double sequence and similar structures
[Suite double de Thue–Morse–Pascal et structures semblables]

Présenté par : the Editorial Board

Mihai Prunescu ^1,²

¹ Brain Products GmbH, Friedrichring 1, 79098 Freiburg, Germany
² Simion Stoilow Institute of Mathematics of the Romanian Academy, Research unit 5, P.O. Box 1-764, RO-014700 Bucharest, Romania

Comptes Rendus. Mathématique, Volume 349 (2011) no. 17-18, pp. 939-942.

Résumé
Abstract

Si une suite bidimensionnelle récurrente avec conditions initiales définies par substitution linéaire et une suite bidimensionnelle engendrée par substitution plane sont identiques sur un carré initial assez grand, alors elles coïncident partout. Après avoir démontré ce principe on lʼapplique à quelques exemples concrets. Lʼun dʼentre-eux est la suite bidimensionnelle de Thue–Morse–Pascal définie par deux exemplaires de la suite de Prouhet–Thue–Morse comme couple de conditions initiales et lʼaddition du triangle de Pascal modulo 2 comme règle de récurrence. Il sʼensuit que la suite bidimensionnelle de Thue–Morse–Pascal est le résultat de 15 règles de substitution, chacune dʼentre-elles consistant de la substitution dʼune certaine matrice $4 \times 4$ avec une matrice $8 \times 8$ .

If a recurrent two-dimensional sequence with initial conditions defined by linear substitution and a two-dimensional sequence that is generated by planar substitution are identical over a sufficiently large initial square, then they will coincide over all. After proving this general principle, we apply it to some concrete examples. One of them, the Thue–Morse–Pascal two-dimensional sequence, is defined by two copies of the Prouhet–Thue–Morse sequence as pair of initial conditions and by the Pascal Triangle Addition modulo 2 as rule of recurrence. As it follows, the Thue–Morse–Pascal two-dimensional sequence is the result of 15 substitution rules, each of them consisting of the substitution of some $4 \times 4$ matrix with an $8 \times 8$ matrix.

Reçu le : 2011-07-03
Accepté le : 2011-07-26
Publié le : 2011-08-31

DOI : 10.1016/j.crma.2011.07.022

Affiliations des auteurs :

Mihai Prunescu ^{1, 2}

¹ Brain Products GmbH, Friedrichring 1, 79098 Freiburg, Germany
² Simion Stoilow Institute of Mathematics of the Romanian Academy, Research unit 5, P.O. Box 1-764, RO-014700 Bucharest, Romania

@article{CRMATH_2011__349_17-18_939_0,
     author = {Mihai Prunescu},
     title = {The {Thue{\textendash}Morse{\textendash}Pascal} double sequence and similar structures},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {939--942},
     publisher = {Elsevier},
     volume = {349},
     number = {17-18},
     year = {2011},
     doi = {10.1016/j.crma.2011.07.022},
     language = {en},
}

TY  - JOUR
AU  - Mihai Prunescu
TI  - The Thue–Morse–Pascal double sequence and similar structures
JO  - Comptes Rendus. Mathématique
PY  - 2011
SP  - 939
EP  - 942
VL  - 349
IS  - 17-18
PB  - Elsevier
DO  - 10.1016/j.crma.2011.07.022
LA  - en
ID  - CRMATH_2011__349_17-18_939_0
ER  -

%0 Journal Article
%A Mihai Prunescu
%T The Thue–Morse–Pascal double sequence and similar structures
%J Comptes Rendus. Mathématique
%D 2011
%P 939-942
%V 349
%N 17-18
%I Elsevier
%R 10.1016/j.crma.2011.07.022
%G en
%F CRMATH_2011__349_17-18_939_0

Mihai Prunescu. The Thue–Morse–Pascal double sequence and similar structures. Comptes Rendus. Mathématique, Volume 349 (2011) no. 17-18, pp. 939-942. doi : 10.1016/j.crma.2011.07.022. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2011.07.022/

Bibliographie
Cité par

[1] J.-P. Allouche; J. Shallit Automatic Sequences – Theory, Applications, Generalizations, Cambridge University Press, 2003

[2] J.-P. Allouche; J. Shallit The ubiquitous Prouhet–Thue–Morse sequence, Singapore, 1998 (Springer Series Discrete Mathematics in Theoretical Computer Science), Springer, London (1999), pp. 1-16

[3] P. Arnoux; V. Berthé; T. Fernique; D. Jamet Functional stepped surfaces, flips and generalized substitutions, Theoretical Computer Science, Volume 380 (2007), pp. 251-265

[4] Directions in Mathematical Quasicrystals (M. Baake; R.V. Moody, eds.), CRM Monograph Series, AMS, Providence, RI, 2000

[5] D. Frettlöh Duality of model sets generated by substitution, Romanian Journal of Pure and Applied Mathematics, Volume 50 (2005), pp. 619-639

[6] B. Grunbaum; G.C. Shephard Tilings and Patterns, Dover Publications, 2011

[7] J. Kari Theory of cellular automata: A survey, Theoretical Computer Science, Volume 334 (2005), pp. 3-33

[8] A. Lindenmayer; P. Prusinkiewicz The Algorithmic Beauty of Plants, Springer-Verlag, 1996

[9] B.B. Mandelbrot The Fractal Geometry of Nature, W.H. Freeman and Company, San Francisco, 1977 (p. 1982)

[10] The Mathematics of Aperiodic Order (R.V. Moody, ed.), Proceedings of the NATO Advanced Study Institute on Long Range Aperiodic Order, Kluwer Academic Publishings, 1997

[11] An.A. Muchnik; Yu.L. Pritykin; A.L. Semenov Sequences close to periodic, Russian Mathematical Surveys, Volume 64 (2009) no. 5, pp. 805-871

[12] D.E. Passoja; A. Lakhtakia Carpets and rugs: An exercise in numbers, Leonardo, Volume 25 (1992) no. 1, pp. 69-71

[13] R. Penrose Pentaplexity, Mathematical Intelligencer, Volume 2 (1979) no. 1, pp. 32-37

[14] N. Priebe Frank Multi-dimensional constant-length substitution sequences, Topology and Applications, Volume 152 (2005), pp. 44-69

[15] M. Prunescu Undecidable properties of recurrent double sequences, Notre Dame Journal of Formal Logic, Volume 49 (2008) no. 2, pp. 143-151

[16] M. Prunescu Self-similar carpets over finite fields, European Journal of Combinatorics, Volume 30 (2009) no. 4, pp. 866-878

[17] M. Prunescu Recurrent double sequences that can be generated by context-free substitutions, Fractals, Volume 18 (2010) no. 1, pp. 65-73

[18] M. Prunescu, Some new counterexamples to context-free substitution in recurrent double sequences over finite sets, Preprint, 2010, submitted for publication, http://home.mathematik.uni-freiburg.de/prunescu/RecDoubleCounterexe.pdf.

[19] M. Prunescu, Recurrent two-dimensional sequences generated by homomorphisms of finite abelian p-groups with periodic initial conditions, Preprint, 2010, Fractals, in press, http://home.mathematik.uni-freiburg.de/prunescu/RecDoublePerBord.pdf.

[20] M. Prunescu Linear recurrent double sequences with constant border in $M_{2} (F_{2})$ are classified according to their geometric content, Symmetry (An MDPI Journal), Volume 3 (2011) no. 3, pp. 402-442

[21] R.M. Robinson Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, Volume 12 (1971) no. 3, pp. 177-209

[22] G. Rozenberg; A. Salomaa Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, Springer-Verlag, 1992

[23] O. Salon, Suites automatiques à multi-indices, in: Séminaire de Théorie des Nombres de Bordeaux, Exposé 4, 1986–1987, 4-01–4-27; followed by an Appendix by J. Shallit, 4-29A–4-36A.

[24] O. Salon Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris, Sér. I, Volume 305 (1987), pp. 501-504

[25] H. Wang Proving theorems by pattern recognition, Bell System Technical Journal, Volume 40 (1961) no. 1, pp. 1-41

[26] S.J. Willson Cellular automata can generate fractals, Discrete Applied Mathematics, Volume 8 (1984), pp. 91-99

[27] S. Wolfram A New Kind of Science, Wolfram Media, 2002 (ISBN: 1-57955-008-8)

Cité par Sources :

Commentaires - Politique