Document Open Access Logo

Fractal Intersections and Products via Algorithmic Dimension

Author Neil Lutz

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.58.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Neil Lutz

Cite As Get BibTex

Neil Lutz. Fractal Intersections and Products via Algorithmic Dimension. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 58:1-58:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.58

Abstract

Algorithmic dimensions quantify the algorithmic information density of individual points and may be defined in terms of Kolmogorov complexity. This work uses these dimensions to bound the classical Hausdorff and packing dimensions of intersections and Cartesian products of fractals in Euclidean spaces. This approach shows that a known intersection formula for Borel sets holds for arbitrary sets, and it significantly simplifies the proof of a known product formula. Both of these formulas are prominent, fundamental results in fractal geometry that are taught in typical undergraduate courses on the subject.

Subject Classification

Keywords
  • algorithmic randomness
  • geometric measure theory
  • Hausdorff dimension
  • Kolmogorov complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM Journal of Computing, 37(3):671-705, 2007. URL: http://dx.doi.org/10.1137/s0097539703446912.
  2. Verónica Becher, Jan Reimann, and Theodore A. Slaman. Irrationality exponent, Hausdorff dimension and effectivization. arXiv:1601.00153 [math.NT], 2016. Google Scholar
  3. Christopher J. Bishop. Personal communication, April 27, 2017. Google Scholar
  4. Christopher J. Bishop and Yuval Peres. Fractals in Probability and Analysis. Cambridge University Press, 2017. URL: http://dx.doi.org/10.1017/9781316460238.
  5. Jin-Yi Cai and Juris Hartmanis. On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line. Journal of Computer and System Sciences, 49(3):605-619, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80073-X.
  6. Adam Case and Jack H. Lutz. Mutual dimension. ACM Transactions on Computation Theory, 7(3):12, 2015. URL: http://dx.doi.org/10.1145/2786566.
  7. R. O. Davies. Some remarks on the Kakeya problem. Proceedings of the Cambridge Philosophical Society, 69:417-421, 1971. URL: http://dx.doi.org/10.1017/s0305004100046867.
  8. Rod Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010. URL: http://dx.doi.org/10.1007/978-0-387-68441-3.
  9. Kenneth J. Falconer. The Geometry of Fractal Sets. Cambridge University Press, 1985. URL: http://dx.doi.org/10.1017/cbo9780511623738.
  10. Kenneth J. Falconer. Sets with large intersection properties. Journal of the London Mathematical Society, 49(2):267-280, 1994. URL: http://dx.doi.org/10.1112/jlms/49.2.267.
  11. Kenneth J. Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, third edition, 2014. URL: http://dx.doi.org/10.1002/0470013850.
  12. Felix Hausdorff. Dimension und äusseres Mass. Mathematische Annalen, 79:157-179, 1919. URL: http://dx.doi.org/10.1007/978-3-642-59483-0_2.
  13. Jean-Pierre Kahane. Sur la dimension des intersections. In Jorge Alberto Barroso, editor, Aspects of mathematics and its applications, North-Holland Mathematical Library, 34, pages 419-430. Elsevier, 1986. URL: http://dx.doi.org/10.1016/s0924-6509(09)70272-7.
  14. Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, third edition, 2008. URL: http://dx.doi.org/10.1007/978-0-387-49820-1.
  15. Jack H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187(1):49-79, 2003. URL: http://dx.doi.org/10.1016/s0890-5401(03)00187-1.
  16. Jack H. Lutz and Neil Lutz. Algorithmic information, plane Kakeya sets, and conditional dimension. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 53:1-53:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.53.
  17. Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM Journal of Computing, 38(3):1080-1112, 2008. URL: http://dx.doi.org/10.1007/978-3-540-69733-6_22.
  18. Neil Lutz and D. M. Stull. Bounding the dimension of points on a line. In TV Gopal, Gerhard Jaeger, and Silvia Steila, editors, Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 425-439, 2017. URL: http://dx.doi.org/10.1007/978-3-319-55911-7_31.
  19. John M. Marstrand. Some fundamental geometrical properties of plane sets of fractional dimensions. Proceedings of the London Mathematical Society, 4(3):257-302, 1954. URL: http://dx.doi.org/10.1112/plms/s3-4.1.257.
  20. Per Martin-Löf. The definition of random sequences. Information and Control, 9(6):602-619, 1966. URL: http://dx.doi.org/10.1016/s0019-9958(66)80018-9.
  21. Pertti Mattila. Hausdorff dimension and capacities of intersections of sets in n-space. Acta Mathematica, 152:77-105, 1984. URL: http://dx.doi.org/10.1007/bf02392192.
  22. Pertti Mattila. On the Hausdorff dimension and capacities of intersections. Mathematika, 32:213-217, 1985. URL: http://dx.doi.org/10.1112/s0025579300011001.
  23. Pertti Mattila. Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Cambridge University Press, 1995. URL: http://dx.doi.org/10.1017/cbo9780511623813.
  24. Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett., 84(1):1-3, 2002. URL: http://dx.doi.org/10.1016/s0020-0190(02)00343-5.
  25. Elvira Mayordomo. Effective fractal dimension in algorithmic information theory. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 259-285. Springer New York, 2008. URL: http://dx.doi.org/10.1007/978-0-387-68546-5_12.
  26. Ursula Molter and Ezequiel Rela. Furstenberg sets for a fractal set of directions. Proceedings of the American Mathematical Society, 140:2753-2765, 2012. URL: http://dx.doi.org/10.1090/s0002-9939-2011-11111-0.
  27. Andre Nies. Computability and Randomness. Oxford University Press, Inc., New York, NY, USA, 2009. URL: http://dx.doi.org/10.1093/acprof:oso/9780199230761.001.0001.
  28. Jan Reimann. Computability and fractal dimension. PhD thesis, Heidelberg University, 2004. Google Scholar
  29. Jan Reimann. Effectively closed sets of measures and randomness. Annals of Pure and Applied Logic, 156(1):170-182, 2008. URL: http://dx.doi.org/10.1016/j.apal.2008.06.015.
  30. Boris Ryabko. Noiseless coding of combinatorial sources. Problems of Information Transmission, 22:170-179, 1986. Google Scholar
  31. Boris Ryabko. Algorithmic approach to the prediction problem. Problems of Information Transmission, 29:186-193, 1993. Google Scholar
  32. Boris Ryabko. The complexity and effectiveness of prediction algorithms. Journal of Complexity, 10(3):281-295, 1994. URL: http://dx.doi.org/10.1006/jcom.1994.1015.
  33. Ludwig Staiger. Kolmogorov complexity and Hausdorff dimension. Information and Computation, 103:159-194, 1989. URL: http://dx.doi.org/10.1007/3-540-51498-8_42.
  34. Ludwig Staiger. A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory of Computing Systems, 31:215-229, 1998. URL: http://dx.doi.org/10.1007/s002240000086.
  35. Elias M. Stein and Rami Shakarchi. Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton Lectures in Analysis. Princeton University Press, 2005. Google Scholar
  36. Dennis Sullivan. Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups. Acta Mathematica, 153(1):259-277, 1984. URL: http://dx.doi.org/10.1007/bf02392379.
  37. Claude Tricot. Two definitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, 91(1):57-74, 1982. URL: http://dx.doi.org/10.1017/s0305004100059119.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact