2026-07-29T14:18:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16474 2024-03-06T10:57:35Z ddc:004 open_access

The Dimension Spectrum Conjecture for Planar Lines Stull, D. M. Algorithmic randomness Kolmogorov complexity effective dimension Let L_{a,b} be a line in the Euclidean plane with slope a and intercept b. The dimension spectrum sp(L_{a,b}) is the set of all effective dimensions of individual points on L_{a,b}. Jack Lutz, in the early 2000s posed the dimension spectrum conjecture. This conjecture states that, for every line L_{a,b}, the spectrum of L_{a,b} contains a unit interval. In this paper we prove that the dimension spectrum conjecture is true. Specifically, let (a,b) be a slope-intercept pair, and let d = min{dim(a,b), 1}. For every s ∈ [0, 1], we construct a point x such that dim(x, ax + b) = d + s. Thus, we show that sp(L_{a,b}) contains the interval [d, 1+ d]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik D. M. Stull 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.133 urn:nbn:de:0030-drops-164749 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.133 eng https://creativecommons.org/licenses/by/4.0/legalcode