An analogue of Cobham’s theorem for fractals
HTML articles powered by AMS MathViewer
- by Boris Adamczewski and Jason Bell PDF
- Trans. Amer. Math. Soc. 363 (2011), 4421-4442 Request permission
Abstract:
We introduce the notion of $k$-self-similarity for compact subsets of $\mathbb {R}^n$ and show that it is a natural analogue of the notion of $k$-automatic subsets of integers. We show that various well-known fractals such as the triadic Cantor set, the Sierpiński carpet or the Menger sponge turn out to be $k$-self-similar for some integers $k$. We then prove an analogue of Cobham’s theorem for compact sets of $\mathbb R$ that are self-similar with respect to two multiplicatively independent bases $k$ and $\ell$. Namely, we show that $X$ is both a $k$- and an $\ell$-self-similar compact subset of $\mathbb {R}$ if and only if it is a finite union of closed intervals with rational endpoints.References
- Boris Adamczewski and Yann Bugeaud, Real and $p$-adic expansions involving symmetric patterns, Int. Math. Res. Not. , posted on (2006), Art. ID 75968, 17. MR 2250005, DOI 10.1155/IMRN/2006/75968
- Boris Adamczewski and Yann Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), no. 2, 547–565. MR 2299740, DOI 10.4007/annals.2007.165.547
- Paul S. Addison, Fractals and chaos, Institute of Physics Publishing, Bristol, 1997. An illustrated course. MR 1483313, DOI 10.1887/0750304006
- J.-P. Allouche, F. von Haeseler, H.-O. Peitgen, A. Petersen, and G. Skordev, Automaticity of double sequences generated by one-dimensional linear cellular automata, Theoret. Comput. Sci. 188 (1997), no. 1-2, 195–209. MR 1479629, DOI 10.1016/S0304-3975(96)00298-8
- J.-P. Allouche, F. von Haeseler, H.-O. Peitgen, and G. Skordev, Linear cellular automata, finite automata and Pascal’s triangle, Discrete Appl. Math. 66 (1996), no. 1, 1–22. MR 1387674, DOI 10.1016/0166-218X(94)00132-W
- Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038, DOI 10.1017/CBO9780511546563
- A. Barbé and F. von Haeseler, Limit sets of automatic sequences, Adv. Math. 175 (2003), no. 2, 169–196. MR 1972631, DOI 10.1016/S0001-8708(02)00043-9
- Bernard Boigelot and Julien Brusten, A generalization of Cobham’s theorem to automata over real numbers, Theoret. Comput. Sci. 410 (2009), no. 18, 1694–1703. MR 2508527, DOI 10.1016/j.tcs.2008.12.051
- Alan Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969), 186–192. MR 250789, DOI 10.1007/BF01746527
- María Isabel Cortez and Fabien Durand, Self-similar tiling systems, topological factors and stretching factors, Discrete Comput. Geom. 40 (2008), no. 4, 622–640. MR 2453331, DOI 10.1007/s00454-008-9108-4
- Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382
- Kenneth Falconer, Fractal geometry, John Wiley & Sons, Ltd., Chichester, 1990. Mathematical foundations and applications. MR 1102677
- Harry Furstenberg, Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation, Math. Systems Theory 1 (1967), 1–49. MR 213508, DOI 10.1007/BF01692494
- F. v. Haeseler, H.-O. Peitgen, and G. Skordev, Self-similar structure of rescaled evolution sets of cellular automata. I, Internat. J. Bifur. Chaos Appl. Sci. Engrg. 11 (2001), no. 4, 913–926. MR 1839903, DOI 10.1142/S0218127401002481
- F. v. Haeseler, H.-O. Peitgen, and G. Skordev, Self-similar structure of rescaled evolution sets of cellular automata. II, Internat. J. Bifur. Chaos Appl. Sci. Engrg. 11 (2001), no. 4, 927–941. MR 1839904, DOI 10.1142/S0218127401002511
- J. Hartmanis and R. E. Stearns, Sets of numbers defined by finite automata, Amer. Math. Monthly 74 (1967), 539–542. MR 211817, DOI 10.2307/2314883
- Kiran S. Kedlaya, Finite automata and algebraic extensions of function fields, J. Théor. Nombres Bordeaux 18 (2006), no. 2, 379–420 (English, with English and French summaries). MR 2289431
- R. Daniel Mauldin and S. C. Williams, Hausdorff dimension in graph directed constructions, Trans. Amer. Math. Soc. 309 (1988), no. 2, 811–829. MR 961615, DOI 10.1090/S0002-9947-1988-0961615-4
- Kurt Mahler, Some suggestions for further research, Bull. Austral. Math. Soc. 29 (1984), no. 1, 101–108. MR 732177, DOI 10.1017/S0004972700021316
- C. A. Rogers, Hausdorff measures, Cambridge University Press, London-New York, 1970. MR 0281862
- J. Sakarovitch, Éléments de théorie des automates, Vuibert, Paris, 2003 (English translation: Elements of Automata Theory, Cambridge University Press, 2009).
- Olivier Salon, Suites automatiques à multi-indices et algébricité, C. R. Acad. Sci. Paris Sér. I Math. 305 (1987), no. 12, 501–504 (French, with English summary). MR 916320
- A. L. Semenov, The Presburger nature of predicates that are regular in two number systems, Sibirsk. Mat. Ž. 18 (1977), no. 2, 403–418, 479 (Russian). MR 0450050
- J. Shallit and J. Stolfi, Two methods for generating fractals, Comput. & Graphics 13 (1989), 185–191.
- Michel Waldschmidt, Diophantine approximation on linear algebraic groups, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 326, Springer-Verlag, Berlin, 2000. Transcendence properties of the exponential function in several variables. MR 1756786, DOI 10.1007/978-3-662-11569-5
- Michel Waldschmidt, Un demi-siècle de transcendance, Development of mathematics 1950–2000, Birkhäuser, Basel, 2000, pp. 1121–1186 (French). MR 1796871
- L. Wegner, Problem P12: Is $www^R$ cube-free? Bull. Eur. Assoc. Theor. Comput. Sci., No. 18 (October 1982), 120.
Additional Information
- Boris Adamczewski
- Affiliation: CNRS, Université de Lyon, Université Lyon 1, Institut Camille Jordan, 43 boulevard du 11 novembre 1918, 69622 Villeurbanne Cedex, France
- MR Author ID: 704234
- Email: Boris.Adamczewski@math.univ-lyon1.fr
- Jason Bell
- Affiliation: Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, British Columbia, Canada V5A 1S6
- MR Author ID: 632303
- Email: jpb@math.sfu.ca
- Received by editor(s): July 5, 2009
- Received by editor(s) in revised form: January 28, 2010, and March 23, 2010
- Published electronically: March 4, 2011
- Additional Notes: The first author was supported by the ANR through the project “DyCoNum”–JCJC06 134288. He also thanks Jean-Paul Allouche for pointing out relevant references.
The second author thanks NSERC for its generous support. - © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 363 (2011), 4421-4442
- MSC (2010): Primary 28A80, 11B85
- DOI: https://doi.org/10.1090/S0002-9947-2011-05357-2
- MathSciNet review: 2792994