License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.57
URN: urn:nbn:de:0030-drops-158675
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15867/
Go to the corresponding LIPIcs Volume Portal

Stull, D. M.

Optimal Oracles for Point-To-Set Principles

pdf-format:
LIPIcs-STACS-2022-57.pdf (0.6 MB)

Abstract

The point-to-set principle [Lutz and Lutz, 2018] characterizes the Hausdorff dimension of a subset E ⊆ ℝⁿ by the effective (or algorithmic) dimension of its individual points. This characterization has been used to prove several results in classical, i.e., without any computability requirements, analysis. Recent work has shown that algorithmic techniques can be fruitfully applied to Marstrand’s projection theorem, a fundamental result in fractal geometry.
In this paper, we introduce an extension of point-to-set principle - the notion of optimal oracles for subsets E ⊆ ℝⁿ. One of the primary motivations of this definition is that, if E has optimal oracles, then the conclusion of Marstrand’s projection theorem holds for E. We show that every analytic set has optimal oracles. We also prove that if the Hausdorff and packing dimensions of E agree, then E has optimal oracles. Moreover, we show that the existence of sufficiently nice outer measures on E implies the existence of optimal Hausdorff oracles. In particular, the existence of exact gauge functions for a set E is sufficient for the existence of optimal Hausdorff oracles, and is therefore sufficient for Marstrand’s theorem. Thus, the existence of optimal oracles extends the currently known sufficient conditions for Marstrand’s theorem to hold.
Under certain assumptions, every set has optimal oracles. However, assuming the axiom of choice and the continuum hypothesis, we construct sets which do not have optimal oracles. This construction naturally leads to a generalization of Davies' theorem on projections.

BibTeX - Entry

@InProceedings{stull:LIPIcs.STACS.2022.57,
  author =	{Stull, D. M.},
  title =	{{Optimal Oracles for Point-To-Set Principles}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15867},
  URN =		{urn:nbn:de:0030-drops-158675},
  doi =		{10.4230/LIPIcs.STACS.2022.57},
  annote =	{Keywords: Algorithmic randomness, Kolmogorov complexity, geometric measure theory}
}

Keywords: Algorithmic randomness, Kolmogorov complexity, geometric measure theory
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

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