{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T04:08:33Z","timestamp":1749614913909,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            We establish that effective continued fraction dimension originally defined using\n            <jats:italic>s<\/jats:italic>\n            -gales [\n            <jats:xref ref-type=\"bibr\">21<\/jats:xref>\n            ] is robust, but surprisingly, that the effective continued fraction dimension and effective (base-\n            <jats:italic>b<\/jats:italic>\n            ) Hausdorff dimension of the same real can be unequal in general. We initially provide an equivalent characterization of continued fraction dimension using Kolmogorov complexity. We also prove new bounds on the Lebesgue measure of continued fraction cylinders, which may be of independent interest.\n          <\/jats:p>\n          <jats:p>\n            We apply these bounds to reveal an unexpected behavior of continued fraction dimension. It is known that effective dimension is invariant with respect to base conversion [\n            <jats:xref ref-type=\"bibr\">8<\/jats:xref>\n            ]. We also know that Martin-L\u00f6f randomness and computable randomness are invariant not only with respect to base conversion, but also with respect to the continued fraction representation [\n            <jats:xref ref-type=\"bibr\">21<\/jats:xref>\n            ]. In contrast, for any\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(0 \\lt \\varepsilon \\lt 0.5\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , we prove the existence of a real whose effective Hausdorff dimension is less than\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varepsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            but whose effective continued fraction dimension is greater than or equal to 0.5. This phenomenon is related to the \u201cnon-faithfulness\u201d of certain families of covers [\n            <jats:xref ref-type=\"bibr\">1<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">23<\/jats:xref>\n            ].\n          <\/jats:p>\n          <jats:p>We also establish that, for any real number, the effective continued fraction dimension of the real number is always greater than or equal to its effective Hausdorff dimension.<\/jats:p>","DOI":"10.1145\/3723323","type":"journal-article","created":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T10:46:28Z","timestamp":1741862788000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0214-0598","authenticated-orcid":false,"given":"Satyadev","family":"Nandakumar","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8509-7387","authenticated-orcid":false,"given":"Akhil","family":"S","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0575-0655","authenticated-orcid":false,"given":"Prateek","family":"Vishnoi","sequence":"additional","affiliation":[{"name":"School of Computing and Electrical Engineering, Indian Institute of Technology Mandi, Mandi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.31392\/MFAT-npu26_4.2020.01"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2","DOI":"10.1002\/mana.201500471"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1145\/321892.321894"},{"doi-asserted-by":"publisher","key":"e_1_3_2_5_2","DOI":"10.5948\/UPO9781614440277"},{"doi-asserted-by":"publisher","key":"e_1_3_2_6_2","DOI":"10.1007\/978-0-387-68441-3"},{"key":"e_1_3_2_7_2","volume-title":"Ergodic Theory: With a View towards Number Theory","author":"Einsiedler M.","year":"2010","unstructured":"M. Einsiedler and T. Ward. 2010. Ergodic Theory: With a View towards Number Theory. Springer London. 2010936100 Retrieved from https:\/\/books.google.co.in\/books?id=PiDET2fS7H4C"},{"doi-asserted-by":"publisher","key":"e_1_3_2_8_2","DOI":"10.1002\/0470013850"},{"doi-asserted-by":"publisher","key":"e_1_3_2_9_2","DOI":"10.1016\/j.ipl.2013.04.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_10_2","DOI":"10.1007\/978-94-015-9940-5"},{"key":"e_1_3_2_11_2","first-page":"1413","article-title":"On the notion of a random sequence","volume":"14","author":"Levin L. A.","year":"1973","unstructured":"L. A. Levin. 1973. On the notion of a random sequence. Soviet Math. Doklady 14 (1973), 1413\u20131416.","journal-title":"Soviet Math. Doklady"},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1007\/978-0-387-49820-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_13_2","DOI":"10.1007\/3-540-45022-X_76"},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1137\/S0097539701417723"},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1016\/S0890-5401(03)00187-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_16_2","DOI":"10.1137\/070684689"},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.1016\/S0019-9958(66)80018-9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_18_2","DOI":"10.1016\/S0020-0190(02)00343-5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.4204\/EPTCS.143.6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_20_2","DOI":"10.1007\/s00224-018-9848-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1145\/1374376.1374383"},{"doi-asserted-by":"publisher","key":"e_1_3_2_22_2","DOI":"10.1016\/j.ic.2022.104876"},{"doi-asserted-by":"publisher","key":"e_1_3_2_23_2","DOI":"10.5555\/1572527"},{"key":"e_1_3_2_24_2","article-title":"Continued fractions and dimensional gaps","author":"Peres Yuval","unstructured":"Yuval Peres and Gyorgiy Torbin. [n.d.]. Continued fractions and dimensional gaps. In Preparation ([n.d.]).","journal-title":"In Preparation"},{"unstructured":"Adrian-Maria Scheerer. 2017. On the continued fraction expansion of absolutely normal numbers. arxiv:1701.07979 [math.NT].","key":"e_1_3_2_25_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.1007\/BFb0112458"},{"doi-asserted-by":"publisher","key":"e_1_3_2_27_2","DOI":"10.1016\/S0304-3975(01)00102-5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.1017\/S0004972716000101"},{"key":"e_1_3_2_29_2","volume-title":"Algorithmic Information Theory & Continued Fractions","author":"Vishnoi Prateek","year":"2023","unstructured":"Prateek Vishnoi. 2023. Algorithmic Information Theory & Continued Fractions. Ph. D. Dissertation. Indian Institute of Technology Kanpur."},{"key":"e_1_3_2_30_2","first-page":"382","volume-title":"Theory and Applications of Models of Computation: 17th Annual Conference, TAMC 2022, Tianjin, China, September 16\u201318, 2022, Proceedings","author":"Vishnoi Prateek","year":"2023","unstructured":"Prateek Vishnoi. 2023. Normality, randomness and Kolmogorov complexity of continued fractions. In Theory and Applications of Models of Computation: 17th Annual Conference, TAMC 2022, Tianjin, China, September 16\u201318, 2022, Proceedings. Springer, 382\u2013392."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3723323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T11:52:55Z","timestamp":1749556375000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3723323"],"URL":"https:\/\/doi.org\/10.1145\/3723323","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,6,9]]},"assertion":[{"value":"2024-04-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}