Document Open Access Logo

Projection Theorems Using Effective Dimension

Authors Neil Lutz, Donald M. Stull

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.71.pdf
  • Filesize: 406 kB
  • 15 pages

Document Identifiers

Author Details

Neil Lutz
  • Department of Computer and Information Science, University of Pennsylvania, 3330 Walnut Street, Philadelphia, PA 19104, USA
Donald M. Stull
  • Inria Nancy-Grand Est, 615 rue du jardin botanique, 54600 Villers-les-Nancy, France

Funding

  • Stull, Donald M.: Research supported in part by National Science Foundation Grants 1247051 and 1545028.

Cite As Get BibTex

Neil Lutz and Donald M. Stull. Projection Theorems Using Effective Dimension. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.71

Abstract

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which shows that for every analytic set E, for almost every line L, the Hausdorff dimension of the orthogonal projection of E onto L is maximal.
We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E, even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
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 J. Comput., 37(3):671-705, 2007. Google Scholar
  2. Christopher J. Bishop and Yuval Peres. Fractals in probability and analysis, volume 162 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2017. Google Scholar
  3. Cristian S. Calude and Marius Zimand. Algorithmically independent sequences. Inf. Comput., 208(3):292-308, 2010. Google Scholar
  4. Roy O. Davies. Some remarks on the Kakeya problem. Proc. Cambridge Phil. Soc., 69:417-421, 1971. Google Scholar
  5. Roy O. Davies. Two counterexamples concerning Hausdorff dimensions of projections. Colloq. Math., 42:53-58, 1979. Google Scholar
  6. K. J. Falconer and J. D. Howroyd. Projection theorems for box and packing dimensions. Math. Proc. Cambridge Philos. Soc., 119(2):287-295, 1996. Google Scholar
  7. K. J. Falconer and J. D. Howroyd. Packing dimensions of projections and dimension profiles. Math. Proc. Cambridge Philos. Soc., 121(2):269-286, 1997. Google Scholar
  8. Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, third edition, 2014. Google Scholar
  9. Kenneth Falconer, Jonathan Fraser, and Xiong Jin. Sixty years of fractal projections. In Fractal geometry and stochastics V, volume 70 of Progr. Probab., pages 3-25. Birkhäuser/Springer, Cham, 2015. Google Scholar
  10. Kenneth J. Falconer and Pertti Mattila. The packing dimension of projections and sections of measures. Math. Proc. Cambridge Philos. Soc., 119(4):695-713, 1996. Google Scholar
  11. John M. Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, 38(5):559-571, 2005. Google Scholar
  12. J. D. Howroyd. Box and packing dimensions of projections and dimension profiles. Math. Proc. Cambridge Philos. Soc., 130(1):135-160, 2001. Google Scholar
  13. Maarit Järvenpää. On the upper Minkowski dimension, the packing dimension, and orthogonal projections. Ann. Acad. Sci. Fenn. Ser. A I Math. Dissertationes, page 34, 1994. Google Scholar
  14. Robert Kaufman. On Hausdorff dimension of projections. Mathematika, 15:153-155, 1968. Google Scholar
  15. Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, third edition, 2008. Google Scholar
  16. Jack H. Lutz. Dimension in complexity classes. SIAM J. Comput., 32(5):1236-1259, 2003. Google Scholar
  17. Jack H. Lutz and Neil Lutz. Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Transactions on Computation Theory, 10(2):7:1-7:22, 2018. Google Scholar
  18. Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM J. Comput., 38(3):1080-1112, 2008. Google Scholar
  19. Neil Lutz. Fractal intersections and products via algorithmic dimension. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, pages 58:1-58:12, 2017. Google Scholar
  20. Neil Lutz and Donald M. Stull. Bounding the dimension of points on a line. In Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 425-439, 2017. Google Scholar
  21. J. M. Marstrand. Some fundamental geometrical properties of plane sets of fractional dimensions. Proc. London Math. Soc. (3), 4:257-302, 1954. Google Scholar
  22. Pertti Mattila. Hausdorff dimension, orthogonal projections and intersections with planes. Ann. Acad. Sci. Fenn. Ser. A I Math., 1(2):227-244, 1975. Google Scholar
  23. Pertti Mattila. Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Cambridge University Press, 1999. Google Scholar
  24. Pertti Mattila. Recent progress on dimensions of projections. In Geometry and analysis of fractals, volume 88 of Springer Proc. Math. Stat., pages 283-301. Springer, Heidelberg, 2014. Google Scholar
  25. Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett., 84(1):1-3, 2002. Google Scholar
  26. Tuomas Orponen. On the packing dimension and category of exceptional sets of orthogonal projections. Ann. Mat. Pura Appl. (4), 194(3):843-880, 2015. Google Scholar
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