Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde

Allouche, Gabrielle; Allouche, Jean-Paul; Shallit, Jeffrey

Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2115-2130.

Nous montrons que le tracé d’un kolam indien classique, que l’on retrouve aussi dans la tradition des dessins sur le sable aux îles Vanuatu, peut être engendré par un morphisme de monoïde. La suite infinie morphique ainsi obtenue est reliée à la célèbre suite de Prouhet-Thue-Morse, mais elle n’est $k$-automatique pour aucun entier $k\ge 1$.

We prove that the drawing of a classical Indian kolam (which one also finds in the tradition of drawings on the sand in the Vanuatu islands) can be described by a morphism of monoids. The corresponding infinite sequence is related to the celebrated Prouhet-Thue-Morse sequence, but it is not $k$-automatic for any integer $k\ge 1$.

[1] Allouche, J.-P.; Arnold, A.; Berstel, J.; Brlek, S.; Jockusch, W.; Plouffe, S.; Sagan, B. E. A relative of the Thue-Morse sequence, Discrete Math., Volume 139 (1995), pp. 455-461 | DOI | MR | Zbl

[2] Allouche, J.-P.; Davison, J. L.; Queffélec, M.; Zamboni, L. Q. Transcendence of Sturmian or morphic continued fractions, J. Number Theory, Volume 91 (2001), pp. 39-66 | DOI | MR | Zbl

[3] Allouche, J.-P.; Mendès France, M.; Axel, F.; Gratias, D. Automata and automatic sequences, Beyond quasicrystals (Les Éditions de Physique, Springer), Les Houches, 1994 (1995), pp. 293-367 | MR | Zbl

[4] Allouche, J.-P.; Shallit, J.; Ding, C.; Helleseth, T.; Niederreiter, H. The ubiquitous Prouhet-Thue-Morse sequence, Sequences and Their Applications, Springer, Proceedings of SETA’98 (1999), pp. 1-16 | MR | Zbl

[5] Allouche, J.-P.; Shallit, J. Automatic Sequences : Theory, Applications, Generalizations, Cambridge University Press, 2003 | MR | Zbl

[6] Ascher, M. Ethnomathematics : A Multicultural View of Mathematical Ideas, Pacific Grove, CA and Chapman & Hall, New York, 1991 (Brooks Cole Publishing Co.) | MR | Zbl

[7] Ascher, M. Mathématiques d’ailleurs. Nombres, formes et jeux dans les sociétés traditionnelles, Le Seuil, Paris (1998) (avec une postface de K. Chemla et S. Pahaut)

[8] Ascher, M. Mathematics Elsewhere : An Exploration of Ideas Across Cultures, Princeton University Press, 2002 | MR | Zbl

[9] Ascher, M. Les figures de kolam en Inde du sud, Dossier Pour La Science, Mathématiques Exotiques (2005), pp. 53-57

[10] Belotserkovets, A. Propriétés combinatoires de suites symboliques qui codent des courbes de Péano, Université de Novosibirsk (2003) (Masters thesis en russe)

[11] Brlek, S. Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., Volume 24 (1989), pp. 83-96 | DOI | MR | Zbl

[12] Carlitz, L.; Scoville, R.; E. Hoggatt, Jr., V. Representations for a special sequence, Fibonacci Quart., Volume 10 (1972), p. 499-518, 550 | MR | Zbl

[13] Cassaigne, J. Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comput. Sci., Volume 218 (1999), pp. 3-12 | DOI | MR | Zbl

[14] Cobham, A. Uniform tag sequences, Math. Systems Theory, Volume 6 (1972), pp. 164-192 | DOI | MR | Zbl

[15] Durand, F. A generalization of Cobham’s theorem, Theory Comput. Syst., Volume 31 (1998), pp. 169-185 | DOI | MR | Zbl

[16] Gerdes, P. Une tradition géométrique en Afrique, les dessins sur le sable, I, II & III, L’Harmattan, 1995 | Zbl

[17] Gerdes, P. Ethnomathematics as a new research field, illustrated by studies of mathematical ideas in African history. Filling a Gap in the History of Science., Science and Cultural Diversity, Cuadernos de Quipu No 5. México, J. J. Saldaña (et al.), éd., IASCUD, International Association for Science and Cultural Diversity (2001) (http://iascud.univalle.edu.co/indicelibro.htm)

[18] Hall, R. W. A course in multicultural mathematics (Primus, à paraître)

[19] Kitaev, S.; Mansour, T.; Séébold, P. Generating the Peano curve and counting occurrences of some patterns, J. Autom. Lang. Comb., Volume 9 (2004), pp. 439-455 | MR | Zbl

[20] Norman, M. G.; Moscato, P. The euclidean traveling salesman problem and a space-filling curve, Chaos, Solitons and Fractals, Volume 6 (1995), pp. 389-397 | DOI | Zbl

[21] Platzman, L. K.; Bartholdi III, J. J. Spacefilling curves and the planar travelling salesman problem, J. Assoc. Comput. Mach., Volume 36 (1989), pp. 719-737 | MR | Zbl

[22] Prusinkiewicz, P.; Samavati, F. F.; Smith, C.; Karwowski, R. L-System description of subdivision curves, Int. J. Shape Model., Volume 9 (2003), pp. 41-59 | DOI | Zbl

[23] Rosenfeld, A.; Siromoney, R. Picture languages : a survey, Languages of Design, Volume 1 (1993), pp. 229-245

[24] Salon, O. Suites automatiques à multi-indices, Sém. Théor. Nombres Bordeaux (1986-1987), pp. 27 (Exposé 4, 4-01-4-27 ; suivi par un appendice par J. Shallit, 4-29A-4-36A) | Zbl

[25] Séébold, P. Tag-systems for the Hilbert curve (J. Autom. Lang. Comb., à paraître)

[26] Séébold, P. The Peano curve and iterated morphisms, 10${}^{\mathrm{es}}$ Journées Montoises d’Informatique Théorique, Liège (Belgique) (2004), pp. 338-351 (Rapport ULg, Institut de Mathématiques 04.006)

[27] Séébold, P.; Slowinski, K. The shortest way to draw a connected picture, Computer Graphics Forum, Volume 10 (1991), pp. 319-327 | DOI

[28] Shallit, J. A generalization of automatic sequences, Theoret. Comput. Sci., Volume 61 (1988), pp. 1-16 | DOI | MR | Zbl

[29] Shallit, J. Automaticity IV : sequences, sets, and diversity, J. Théorie Nombres, Bordeaux, Volume 8 (1996), pp. 347-367 | DOI | Numdam | MR | Zbl

[30] Shallit, J.; Stolfi, J. Two methods for generating fractals, Computers and Graphics, Volume 13 (1989), pp. 185-191 | DOI

[31] Sierpinski, W. Sur une courbe dont tout point est un point de ramification, C. R. Acad. Sci., Volume 160 (1915), pp. 302-305

[32] Sierpinski, W. Sur une courbe cantorienne qui contient une image biunivoque et continue de toute courbe donnée, C. R. Acad. Sci., Volume 162 (1916), pp. 629-632

[33] Siromoney, G.; Siromoney, R.; Ehrig, H.; Nagl, M.; Rosenfeld, A.; Rozenberg, G. Rosenfeld’s cycle grammars and kolam, Graph grammars and their application to computer science (Lect. Notes Comput. Sci.), Volume 291, Springer, Third International Workshop (1987), pp. 564-579 | MR | Zbl

[34] Siromoney, G.; Siromoney, R.; Krithivasan, K. Array grammars and kolam, Computer Graphics and Image Processing, Volume 3 (1974), pp. 63-82 | DOI | MR

[35] Siromoney, G.; Siromoney, R.; Robinsin, T. Kambi kolam and cycle grammars, A perspective in theoretical computer science-commemorative volume for Gift Siromoney ((R. Narasimhan ed.). Series in Computer Science), Volume 16, World Scientific, Singapore (1989), pp. 267-300

[36] Siromoney, R.; Subramanian, K. G. Space-filling curves and infinite graphs, Graph-grammars and their application to computer science (Lect. Notes Comput. Sci.), Volume 153, Springer, Haus Ohrbeck/Ger. 1982, 2nd International. Workshop (1983), pp. 380-391 | Zbl

[37] Tamura, J. Some problems having their origin in the power series ${\sum }_{n=1}^{\infty }{z}^{\left[\alpha n\right]}$, Reports of the meeting on analytic theory of numbers and related topics, Gakushuin University, 1992, pp. 190-212