Lutz, Jack H. ;
Lutz, Neil
Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
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 pointtoset 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, twodimensional 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(xy) and Dim(xy) 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 informationtheoretic relationships with the wellstudied dimensions dim(x) and Dim(x) and the mutual dimensions mdim(x:y) and Mdim(x:y).
BibTeX  Entry
@InProceedings{lutz_et_al:LIPIcs:2017:6980,
author = {Jack H. Lutz and Neil Lutz},
title = {{Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {53:153:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6980},
URN = {urn:nbn:de:0030drops69806},
doi = {10.4230/LIPIcs.STACS.2017.53},
annote = {Keywords: algorithmic randomness, conditional dimension, geometric measure theory, Kakeya sets, Kolmogorov complexity}
}
06.03.2017
Keywords: 

algorithmic randomness, conditional dimension, geometric measure theory, Kakeya sets, Kolmogorov complexity 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

06.03.2017 