Abstract
We establish that constructive continued fraction dimension originally defined using sgales [Nandakumar and Vishnoi, 2022] is robust, but surprisingly, that the effective continued fraction dimension and effective (baseb) Hausdorff dimension of the same real can be unequal in general.
We initially provide an equivalent characterization of continued fraction dimension using Kolmogorov complexity. In the process, we construct an optimal lower semicomputable sgale for continued fractions. We also prove new bounds on the Lebesgue measure of continued fraction cylinders, which may be of independent interest.
We apply these bounds to reveal an unexpected behavior of continued fraction dimension. It is known that feasible dimension is invariant with respect to base conversion [Hitchcock and Mayordomo, 2013]. We also know that MartinLöf randomness and computable randomness are invariant not only with respect to base conversion, but also with respect to the continued fraction representation [Nandakumar and Vishnoi, 2022]. In contrast, for any 0 < ε < 0.5, we prove the existence of a real whose effective Hausdorff dimension is less than ε, but whose effective continued fraction dimension is greater than or equal to 0.5. This phenomenon is related to the "nonfaithfulness" of certain families of covers, investigated by Peres and Torbin [Peres and Torbin] and by Albeverio, Ivanenko, Lebid and Torbin [Albeverio et al., 2020].
We also establish that for any real, the constructive Hausdorff dimension is at most its effective continued fraction dimension.
BibTeX  Entry
@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2023.70,
author = {Nandakumar, Satyadev and S, Akhil and Vishnoi, Prateek},
title = {{Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {70:170:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18604},
URN = {urn:nbn:de:0030drops186041},
doi = {10.4230/LIPIcs.MFCS.2023.70},
annote = {Keywords: Algorithmic information theory, Kolmogorov complexity, Continued fractions, Effective Hausdorff dimension}
}
Keywords: 

Algorithmic information theory, Kolmogorov complexity, Continued fractions, Effective Hausdorff dimension 
Collection: 

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 
Issue Date: 

2023 
Date of publication: 

21.08.2023 