Translating the Cantor set by a random real

Authors:
Randall Dougherty, Jack H. Lutz, R. Daniel Mauldin and Jason Teutsch

Journal:
Trans. Amer. Math. Soc. **366** (2014), 3027-3041

MSC (2010):
Primary 68Q30; Secondary 11K55, 28A78

Published electronically:
January 8, 2014

MathSciNet review:
3180738

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We determine the constructive dimension of points in random translates of the Cantor set. The Cantor set ``cancels randomness'' in the sense that some of its members, when added to Martin-Löf random reals, identify a point with lower constructive dimension than the random itself. In particular, we find the Hausdorff dimension of the set of points in a random Cantor set translate with a given constructive dimension.

**[1]**Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo,*Effective strong dimension in algorithmic information and computational complexity*, SIAM J. Comput.**37**(2007), no. 3, 671–705 (electronic). MR**2341912**, 10.1137/S0097539703446912**[2]**Jin-Yi Cai and Juris Hartmanis,*On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line*, J. Comput. System Sci.**49**(1994), no. 3, 605–619. MR**1306136**, 10.1016/S0022-0000(05)80073-X**[3]**Rodney G. Downey and Denis R. Hirschfeldt,*Algorithmic randomness and complexity*, Theory and Applications of Computability, Springer, New York, 2010. MR**2732288****[4]**P. Erdős, K. Kunen, and R. Daniel Mauldin,*Some additive properties of sets of real numbers*, Fund. Math.**113**(1981), no. 3, 187–199. MR**641304****[5]**K. J. Falconer,*The geometry of fractal sets*, Cambridge Tracts in Mathematics, vol. 85, Cambridge University Press, Cambridge, 1986. MR**867284****[6]**Kenneth Falconer,*Fractal geometry*, 2nd ed., John Wiley & Sons, Inc., Hoboken, NJ, 2003. Mathematical foundations and applications. MR**2118797****[7]**L. A. Levin,*The concept of a random sequence*, Dokl. Akad. Nauk SSSR**212**(1973), 548–550 (Russian). MR**0366096****[8]**Ming Li and Paul Vitányi,*An introduction to Kolmogorov complexity and its applications*, 3rd ed., Texts in Computer Science, Springer, New York, 2008. MR**2494387****[9]**G. G. Lorentz,*On a problem of additive number theory*, Proc. Amer. Math. Soc.**5**(1954), 838–841. MR**0063389**, 10.1090/S0002-9939-1954-0063389-3**[10]**Jack H. Lutz,*The dimensions of individual strings and sequences*, Inform. and Comput.**187**(2003), no. 1, 49–79. MR**2018734**, 10.1016/S0890-5401(03)00187-1**[11]**J. M. Marstrand,*The dimension of Cartesian product sets*, Proc. Cambridge Philos. Soc.**50**(1954), 198–202. MR**0060571****[12]**Per Martin-Löf,*The definition of random sequences*, Information and Control**9**(1966), 602–619. MR**0223179****[13]**Pertti Mattila,*Geometry of sets and measures in Euclidean spaces*, Cambridge Studies in Advanced Mathematics, vol. 44, Cambridge University Press, Cambridge, 1995. Fractals and rectifiability. MR**1333890****[14]**Elvira Mayordomo,*A Kolmogorov complexity characterization of constructive Hausdorff dimension*, Inform. Process. Lett.**84**(2002), no. 1, 1–3. MR**1926330**, 10.1016/S0020-0190(02)00343-5- [15]
Jan Reimann,
*Computability and fractal dimension*, Ph.D. thesis, University of Heidelberg, December 2004. **[16]**Kohtaro Tadaki,*A generalization of Chaitin’s halting probability Ω and halting self-similar sets*, Hokkaido Math. J.**31**(2002), no. 1, 219–253. MR**1888278**, 10.14492/hokmj/1350911778- [17]
William P. Ziemer,
*Modern real analysis*, second ed., 2004.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2010):
68Q30,
11K55,
28A78

Retrieve articles in all journals with MSC (2010): 68Q30, 11K55, 28A78

Additional Information

**Randall Dougherty**

Affiliation:
Department of Mathematics, Center for Communications Research–La Jolla, 4320 Westerra Court, San Diego, California 92121

Email:
rdough@ccrwest.org

**Jack H. Lutz**

Affiliation:
Department of Computer Science, Iowa State University, Ames, Iowa 50011

Email:
lutz@cs.iastate.edu

**R. Daniel Mauldin**

Affiliation:
Department of Mathematics, University of North Texas, Denton, Texas 76203

Email:
mauldin@unt.edu

**Jason Teutsch**

Affiliation:
Department of Mathematics, Ruprecht-Karls-Universität Heidelberg, D-69120 Heidelberg, Germany

Email:
teutsch@math.uni-heidelberg.de

DOI:
http://dx.doi.org/10.1090/S0002-9947-2014-05912-6

Keywords:
Algorithmic randomness,
fractal geometry,
additive number theory

Received by editor(s):
March 25, 2011

Received by editor(s) in revised form:
July 11, 2012

Published electronically:
January 8, 2014

Additional Notes:
The second author’s research was supported by NSF Grants 0652569 and 0728806.

The third author’s research was supported by NSF Grant DMS-0700831.

The fourth author’s research was supported by Deutsche Forschungsgemeinschaft grant ME 1806/3-1.

Article copyright:
© Copyright 2014
by the authors