Translating the Cantor set by a random real

Dougherty, Randall; Lutz, Jack; Mauldin, R. Daniel; Teutsch, Jason

doi:10.1090/S0002-9947-2014-05912-6

Translating the Cantor set by a random real
HTML articles powered by AMS MathViewer

by Randall Dougherty, Jack H. Lutz, R. Daniel Mauldin and Jason Teutsch PDF

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

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

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. MR 2341912, DOI 10.1137/S0097539703446912
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, DOI 10.1016/S0022-0000(05)80073-X
Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
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, DOI 10.4064/fm-113-3-187-199
K. J. Falconer, The geometry of fractal sets, Cambridge Tracts in Mathematics, vol. 85, Cambridge University Press, Cambridge, 1986. MR 867284
Kenneth Falconer, Fractal geometry, 2nd ed., John Wiley & Sons, Inc., Hoboken, NJ, 2003. Mathematical foundations and applications. MR 2118797, DOI 10.1002/0470013850
L. A. Levin, The concept of a random sequence, Dokl. Akad. Nauk SSSR 212 (1973), 548–550 (Russian). MR 0366096
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, DOI 10.1007/978-0-387-49820-1
G. G. Lorentz, On a problem of additive number theory, Proc. Amer. Math. Soc. 5 (1954), 838–841. MR 63389, DOI 10.1090/S0002-9939-1954-0063389-3
Jack H. Lutz, The dimensions of individual strings and sequences, Inform. and Comput. 187 (2003), no. 1, 49–79. MR 2018734, DOI 10.1016/S0890-5401(03)00187-1
J. M. Marstrand, The dimension of Cartesian product sets, Proc. Cambridge Philos. Soc. 50 (1954), 198–202. MR 60571, DOI 10.1017/s0305004100029236
Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 223179, DOI 10.1016/S0019-9958(66)80018-9
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, DOI 10.1017/CBO9780511623813
Elvira Mayordomo, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inform. Process. Lett. 84 (2002), no. 1, 1–3. MR 1926330, DOI 10.1016/S0020-0190(02)00343-5
Jan Reimann, Computability and fractal dimension, Ph.D. thesis, University of Heidelberg, December 2004.
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, DOI 10.14492/hokmj/1350911778
William P. Ziemer, Modern real analysis, second ed., 2004.