DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.13

Algorithmic Information Bounds for Distances and Orthogonal Projections

Authors: Peter Cholak, Marianna Csörnyei, Neil Lutz, Patrick Lutz, Elvira Mayordomo, and D. M. Stull

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

We introduce a new technique for proving bounds on the Kolmogorov complexity of geometric objects in Euclidean space, such as points and lines. We apply this technique to prove two theorems on algorithmic information theory, both of which have consequences for well-known problems in geometric measure theory. First, we show that for any point x in the plane and any other point y sufficiently independent of x, the distance between x and y retains at least half the complexity of the original point x. By the point-to-set principle of J. Lutz and N. Lutz, this yields an improved lower bound on the Hausdorff dimension of pinned distance sets, a topic closely related to Falconer’s distance set conjecture. Second, we prove an analogous result for orthogonal projections: for any point x in the plane and any line through the origin which is sufficiently independent of x, the projection of x onto that line retains at least half the complexity of x. As a consequence, we obtain a generalization of a theorem of Bourgain on exceptional sets for orthogonal projections.

Cite as

Peter Cholak, Marianna Csörnyei, Neil Lutz, Patrick Lutz, Elvira Mayordomo, and D. M. Stull. Algorithmic Information Bounds for Distances and Orthogonal Projections. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cholak_et_al:LIPIcs.MFCS.2026.13,
  author =	{Cholak, Peter and Cs\"{o}rnyei, Marianna and Lutz, Neil and Lutz, Patrick and Mayordomo, Elvira and Stull, D. M.},
  title =	{{Algorithmic Information Bounds for Distances and Orthogonal Projections}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.13},
  URN =		{urn:nbn:de:0030-drops-273941},
  doi =		{10.4230/LIPIcs.MFCS.2026.13},
  annote =	{Keywords: effective fractal dimensions, algorithmic randomness, Kolmogorov complexity}
}

Search Results

Documents authored by Cholak, Peter

Algorithmic Information Bounds for Distances and Orthogonal Projections

Abstract

Cite as

Thanks for your feedback!

Could not send message