Document Open Access Logo

Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension

Authors Jack H. Lutz, Neil Lutz

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.53.pdf
  • Filesize: 494 kB
  • 13 pages

Document Identifiers

Author Details

Jack H. Lutz
Neil Lutz

Cite AsGet BibTex

Jack H. Lutz and Neil Lutz. Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.53

Abstract

We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility of this notion in two ways. 1. We prove a point-to-set principle that enables one to use the (relativized, constructive) dimension of a single point in a set E in a Euclidean space to establish a lower bound on the (classical) Hausdorff dimension of E. We then use this principle, together with conditional Kolmogorov complexity in Euclidean spaces, to give a new proof of the known, two-dimensional case of the Kakeya conjecture. This theorem of geometric measure theory, proved by Davies in 1971, says that every plane set containing a unit line segment in every direction has Hausdorff dimension 2. 2. We use conditional Kolmogorov complexity in Euclidean spaces to develop the lower and upper conditional dimensions dim(x|y) and Dim(x|y) of x given y, where x and y are points in Euclidean spaces. Intuitively these are the lower and upper asymptotic algorithmic information densities of x conditioned on the information in y. We prove that these conditional dimensions are robust and that they have the correct information-theoretic relationships with the well-studied dimensions dim(x) and Dim(x) and the mutual dimensions mdim(x:y) and Mdim(x:y).
Keywords
  • algorithmic randomness
  • conditional dimension
  • geometric measure theory
  • Kakeya sets
  • 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. URL: http://dx.doi.org/10.1137/S0097539703446912.
  2. A. S. Besicovitch. Sur deux questions d'intégrabilité des fonctions. Journal de la Société de physique et de mathematique de l'Universite de Perm, 2:105-123, 1919. Google Scholar
  3. A. S. Besicovitch. On Kakeya’s problem and a similar one. Mathematische Zeitschrift, 27:312-320, 1928. Google Scholar
  4. Adam Case and Jack H. Lutz. Mutual dimension. ACM Transactions on Computation Theory, 7(3):12, 2015. Google Scholar
  5. Adam Case and Jack H. Lutz. Mutual dimension and random sequences. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, volume 9235 of Lecture Notes in Computer Science, pages 199-210. Springer, 2015. Google Scholar
  6. Gregory J. Chaitin. On the length of programs for computing finite binary sequences. J. ACM, 13(4):547-569, 1966. Google Scholar
  7. Gregory J. Chaitin. On the length of programs for computing finite binary sequences: statistical considerations. J. ACM, 16(1):145-159, 1969. Google Scholar
  8. Thomas R. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, second edition, 2006. Google Scholar
  9. Roy O. Davies. Some remarks on the Kakeya problem. Proc. Cambridge Phil. Soc., 69:417-421, 1971. Google Scholar
  10. Randall Dougherty, Jack H. Lutz, R. Daniel Mauldin, and Jason Teutsch. Translating the Cantor set by a random real. Transactions of the American Mathematical Society, 366:3027-3041, 2014. Google Scholar
  11. Rod Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, 2010. Google Scholar
  12. Zeev Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math. Soc., 22:1093-1097, 2009. Google Scholar
  13. Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, third edition, 2014. Google Scholar
  14. Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Points on computable curves. In FOCS, pages 469-474. IEEE Computer Society, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.63.
  15. Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, and Philippe Moser. Dimension spectra of random subfractals of self-similar fractals. Ann. Pure Appl. Logic, 165(11):1707-1726, 2014. Google Scholar
  16. Felix Hausdorff. Dimension und äusseres Mass. Mathematische Annalen, 79:157-179, 1919. Google Scholar
  17. Andrei N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1):1-7, 1965. Google Scholar
  18. Leonid A. Levin. On the notion of a random sequence. Soviet Math Dokl., 14(5):1413-1416, 1973. Google Scholar
  19. Leonid A. Levin. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii, 10(3):30-35, 1974. Google Scholar
  20. Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, third edition, 2008. Google Scholar
  21. Jack H. Lutz. Dimension in complexity classes. SIAM J. Comput., 32(5):1236-1259, 2003. Google Scholar
  22. Jack H. Lutz. The dimensions of individual strings and sequences. Inf. Comput., 187(1):49-79, 2003. Google Scholar
  23. Jack H. Lutz and Neil Lutz. Lines missing every random point. Computability, 4(2):85-102, 2015. Google Scholar
  24. Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM J. Comput., 38(3):1080-1112, 2008. URL: http://dx.doi.org/10.1137/070684689.
  25. Jack H. Lutz and Klaus Weihrauch. Connectivity properties of dimension level sets. Mathematical Logic Quarterly, 54:483-491, 2008. Google Scholar
  26. John M. Marstrand. Some fundamental geometrical properties of plane sets of fractional dimensions. Proceedings of the London Mathematical Society, 4(3):257-302, 1954. Google Scholar
  27. Elvira Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett., 84(1):1-3, 2002. Google Scholar
  28. Andre Nies. Computability and Randomness. Oxford University Press, Inc., New York, NY, USA, 2009. Google Scholar
  29. Claude E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27(3-4):379-423, 623-656, 1948. Google Scholar
  30. Ray J. Solomonoff. A formal theory of inductive inference. Information and Control, 7(1-2):1-22, 224-254, 1964. Google Scholar
  31. Elias M. Stein and Rami Shakarchi. Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton Lectures in Analysis. Princeton University Press, 2005. Google Scholar
  32. Terence Tao. From rotating needles to stability of waves: emerging connections between combinatorics, analysis, and PDE. Notices Amer. Math. Soc, 48:294-303, 2000. Google Scholar
  33. Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. A correction. Proceedings of the London Mathematical Society, 43(2):544-546, 1937. Google Scholar
  34. Klaus Weihrauch. Computable Analysis: An Introduction. Springer, 2000. Google Scholar
  35. T. Wolff. Recent work connected with the Kakeya problem. Prospects in Mathematics, pages 129-162, 1999. 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 Imprint Privacy Contact