Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

   
 
 

 

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
DOI: https://doi.org/10.1090/S0002-9947-2014-05912-6
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.


References [Enhancements On Off] (What's this?)

  • [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 (2009g:68070), https://doi.org/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 (95k:68085), https://doi.org/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 (2012g:03001)
  • [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 (85f:04003)
  • [5] K. J. Falconer, The geometry of fractal sets, Cambridge Tracts in Mathematics, vol. 85, Cambridge University Press, Cambridge, 1986. MR 867284 (88d:28001)
  • [6] Kenneth Falconer, Fractal geometry, 2nd ed., John Wiley & Sons Inc., Hoboken, NJ, 2003. Mathematical foundations and applications. MR 2118797 (2006b:28001)
  • [7] L. A. Levin, The concept of a random sequence, Dokl. Akad. Nauk SSSR 212 (1973), 548-550 (Russian). MR 0366096 (51 #2346)
  • [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 (2010c:68058)
  • [9] G. G. Lorentz, On a problem of additive number theory, Proc. Amer. Math. Soc. 5 (1954), 838-841. MR 0063389 (16,113f)
  • [10] Jack H. Lutz, The dimensions of individual strings and sequences, Inform. and Comput. 187 (2003), no. 1, 49-79. MR 2018734 (2005k:68099), https://doi.org/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 (15,691g)
  • [12] Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602-619. MR 0223179 (36 #6228)
  • [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 (96h:28006)
  • [14] Elvira Mayordomo, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inform. Process. Lett. 84 (2002), no. 1, 1-3. MR 1926330 (2003h:68053), https://doi.org/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 $ \Omega $ and halting self-similar sets, Hokkaido Math. J. 31 (2002), no. 1, 219-253. MR 1888278 (2002k:68082)
  • [17] William P. Ziemer, Modern real analysis, second ed., 2004.

Similar Articles

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: https://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

American Mathematical Society