2026-07-24T05:16:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6980 2024-03-06T10:39:14Z ddc:004 open_access

Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension Lutz, Jack H. Lutz, Neil algorithmic randomness conditional dimension geometric measure theory Kakeya sets Kolmogorov complexity 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jack H. Lutz and Neil Lutz 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.53 urn:nbn:de:0030-drops-69806 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.53 eng https://creativecommons.org/licenses/by/3.0/legalcode