License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.53
URN: urn:nbn:de:0030-drops-69806
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6980/
Go to the corresponding LIPIcs Volume Portal

Lutz, Jack H. ; Lutz, Neil

Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension

pdf-format:
LIPIcs-STACS-2017-53.pdf (0.5 MB)

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).

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:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6980},
  URN =		{urn:nbn:de:0030-drops-69806},
  doi =		{10.4230/LIPIcs.STACS.2017.53},
  annote =	{Keywords: algorithmic randomness, conditional dimension, geometric measure theory, Kakeya sets, Kolmogorov complexity}
}

Keywords: algorithmic randomness, conditional dimension, geometric measure theory, Kakeya sets, Kolmogorov complexity
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI