## 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