Document Open Access Logo

Extending the Reach of the Point-To-Set Principle

Authors Jack H. Lutz , Neil Lutz , Elvira Mayordomo

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.48.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Author Details

Jack H. Lutz
  • Department of Computer Science, Iowa State University, Ames, IA, USA
Neil Lutz
  • Computer Science Department, Swarthmore College, PA, USA
Elvira Mayordomo
  • Departamento de Informática e Ingeniería de Sistemas, Instituto de Investigación en Ingeniería de Aragón, University of Zaragoza, Spain

Funding

  • Lutz, Jack H.: Research supported in part by National Science Foundation grants 1545028 and 1900716. Part of this work was done during a visit to the Institute for Mathematical Sciences at the National University of Singapore.
  • Lutz, Neil: Part of this work was done while this author was at the University of Pennsylvania and at Iowa State University.
  • Mayordomo, Elvira: Research supported in part by projects TIN2016-80347-R and PID2019-104358RB-I00 granted by MCIN/AEI and Government of Aragon COSMOS Group T64_20R, and partly done during a visit to the Institute for Mathematical Sciences at the National University of Singapore.

Acknowledgements

We thank anonymous reviewers for several observations that have improved this paper.

Cite As Get BibTex

Jack H. Lutz, Neil Lutz, and Elvira Mayordomo. Extending the Reach of the Point-To-Set Principle. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.48

Abstract

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces ℝⁿ. These are classical questions, meaning that their statements do not involve computation or related aspects of logic.
In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two fractal dimensions - computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim(x) and Dim(x) to individual points x ∈ X - to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families.
We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces. (For a concrete computational example, the stages E₀, E₁, E₂, … used to construct a self-similar fractal E in the plane are elements of the hyperspace of the plane, and they converge to E in the hyperspace.) Our third main result, proven via our extended point-to-set principle, states that, under a wide variety of gauge families, the classical packing dimension agrees with the classical upper Minkowski dimension on all hyperspaces of compact sets. We use this theorem to give, for all sets E that are analytic, i.e., Σ¹₁, a tight bound on the packing dimension of the hyperspace of E in terms of the packing dimension of E itself.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computability
Keywords
  • algorithmic dimensions
  • geometric measure theory
  • hyperspace
  • point-to-set principle

Metrics

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

Related Versions

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 on Computing, 37(3):671-705, 2007. Google Scholar
  2. Patrick Billingsley. Ergodic Theory and Information. John Wiley & Sons, 1965. Google Scholar
  3. Christopher J. Bishop and Yuval Peres. Fractals in Probability and Analysis. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2016. URL: https://doi.org/10.1017/9781316460238.
  4. Rod G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010. Google Scholar
  5. Rod G. Downey and Denis R. Hirschfeldt. Algorithmic randomness. Communications of the ACM, 62(5):70-80, 2019. Google Scholar
  6. Rod G. Downey and Denis R. Hirschfeldt. Computability and randomness. Notices of the American Mathematical Society, 66(7):1001-1012, 2019. Google Scholar
  7. Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications, 3rd edition. John Wiley & Sons, 2014. Google Scholar
  8. Felix Hausdorff. Dimension und äußeres Maß. Math. Ann., 79:157-179, 1919. English translation: Dimension and Outer Measure. In Gerald A. Edgar, editor, Classics on Fractals, pages 75-100. Addison-Wesley, 1993. Google Scholar
  9. Felix Hausdorff. Grundzüge der Mengenlehre. AMS Chelsea Publishing, 2005. Leipzig, 1914. English translation: Felix Hausdorff, Set Theory, AMS Chelsea Publishing, 2005. Google Scholar
  10. David Hilbert. On the infinite. In Jean van Heijenoort, editor, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard University Press, 1967. Translation by Stefan Bauer-Mengelberg of Hilbert’s 1925 essay. Google Scholar
  11. John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Scaled dimension and nonuniform complexity. Journal of Computer and System Sciences, 69:97-122, 2004. Google Scholar
  12. Greg Hjorth and Alexander S. Kechris. New dichotomies for Borel equivalence relations. Bull. Symbolic Logic, 3(3):329-346, 1997. URL: https://doi.org/10.2307/421148.
  13. H. Joyce and D. Preiss. On the existence of subsets of finite positive packing measure. Mathematika, 42(1):15-24, 1995. Google Scholar
  14. Anatole Katok and Boris Hasselblatt. Introduction to the Modern Theory of Dynamical Systems. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1995. Google Scholar
  15. Nets Hawk Katz and Terence Tao. Some connections between Falconer’s distance set conjecture and sets of Furstenburg type. New York Journal of Mathematics, 7:149-187, 2001. Google Scholar
  16. Robert Kaufman. On Hausdorff dimension of projections. Mathematika, 15(2):153-155, 1968. Google Scholar
  17. Alexander S. Kechris, Slawomir Solecki, and Stevo Todorcevic. Borel chromatic numbers. Adv. Math., 141(1):1-44, 1999. URL: https://doi.org/10.1006/aima.1998.1771.
  18. Takayuki Kihara and Arno Pauly. Point degree spectra of represented spaces. CoRR, abs/1405.6866, 2014. URL: http://arxiv.org/abs/1405.6866.
  19. Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, Berlin, 2019. Fourth Edition. Google Scholar
  20. Jack H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187(1):49-79, 2003. Google Scholar
  21. Jack H. Lutz. The point-to-set principle, the Continuum Hypothesis, and the dimensions of Hamel bases. Technical report, arXiv, 2020. URL: http://arxiv.org/abs/2109.10981.
  22. 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
  23. Jack H. Lutz and Neil Lutz. Who asked us? How the theory of computing answers questions about analysis. In Dingzhu Du and Jie Wang, editors, Complexity and Approximation: In Memory of Ker-I Ko, pages 48-56. Springer, 2020. Google Scholar
  24. Jack H. Lutz and Elvira Mayordomo. Algorithmic fractal dimensions in geometric measure theory. In Vasco Brattka and Peter Hertling, editors, Handbook of Computability and Complexity in Analysis. Springer, 2021. Google Scholar
  25. Neil Lutz. Fractal intersections and products via algorithmic dimension. ACM Trans. Comput. Theory, 13(3), 2021. Google Scholar
  26. Neil Lutz and D. M. Stull. Projection theorems using effective dimension. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 71:1-71:15, 2018. Google Scholar
  27. Neil Lutz and D.M. Stull. Bounding the dimension of points on a line. Information and Computation, 275, 2020. Google Scholar
  28. Pertti Mattila. Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability. Cambridge University Press, 1995. Google Scholar
  29. Elvira Mayordomo. Effective Hausdorff dimension in general metric spaces. Theory of Computing Systems, 62:1620-1636, 2018. Google Scholar
  30. Mark McClure. Entropy dimensions of the hyperspace of compact sets. Real Anal. Exchange, 21(1):194-202, 1995. URL: https://projecteuclid.org:443/euclid.rae/1341343235.
  31. Mark McClure. The Hausdorff dimension of the hyperspace of compact sets. Real Anal. Exchange, 22:611-625, 1996. Google Scholar
  32. Yiannis N. Moschovakis. Descriptive Set Theory, volume 100 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing, 1980. Google Scholar
  33. Andre Nies. Computability and Randomness. Oxford University Press, 2009. Google Scholar
  34. Tuomas Orponen. Combinatorial proofs of two theorems of Lutz and Stull. Mathematical Proceedings of the Cambridge Philosophical Society, pages 1-12, 2021. Google Scholar
  35. Yakov Pesin. Dimension Theory in Dynamical Systems: Contemporary Views and Applications. University of Chicago Press, 1998. Google Scholar
  36. Claude A. Rogers. Hausdorff Measures. Cambridge University Press, 1998. Originally published in 1970. Google Scholar
  37. M. Sipser. A complexity-theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 330-335, 1983. Google Scholar
  38. M. Sipser. A topological view of some problems in complexity theory. In Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science, pages 567-572, 1984. Google Scholar
  39. M. Sipser. The history and status of the P versus NP question. In Proceedings of the 24th Annual ACM Symposium on the theory of Computing, pages 603-618, 1992. Google Scholar
  40. Theodore Slaman. Kolmogorov complexity and capacitability of dimension. In Computability Theory (hybrid meeting), Report No. 21/2021, Mathematisches Forschungsinstitut Oberwolfach, 2021. Google Scholar
  41. Ludwig Staiger. Exact constructive and computable dimensions. Theory Comput. Syst., 61(4):1288-1314, 2017. Google Scholar
  42. Claude Tricot. Two definitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, 91:57-74, 1982. Google Scholar
  43. Shmuel Weinberger. Computers, Rigidity, and Moduli: The Large-Scale Fractal Geometry of Riemannian Moduli Space. Princeton University Press, Princeton, NJ, USA, 2004. Google Scholar
  44. Stephen Willard. General Topology. Dover Publications, 2004. 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