{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:37:56Z","timestamp":1753882676450,"version":"3.41.2"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"abstract":"<jats:p>This work solves an open question in finite-state compressibility posed by Lutz and Mayordomo about compressibility of real numbers in different bases.<\/jats:p>\n          <jats:p>\n            Finite-state compressibility, or equivalently, finite-state dimension, quantifies the asymptotic\n            <jats:italic>lower density of information<\/jats:italic>\n            in an infinite sequence. Absolutely normal numbers, being finite-state incompressible in every base, are precisely those numbers which have finite-state dimension equal to 1 in every base. At the other extreme, for example, every rational number has finite-state dimension equal to 0 in every base.\n          <\/jats:p>\n          <jats:p>\n            Generalizing this, Lutz and Mayordomo posed the question: are there numbers which have absolute positive finite-state dimension strictly between 0 and 1 - equivalently, is there a real number\n            <jats:italic>\u03be<\/jats:italic>\n            and a compressibility ratio\n            <jats:italic>s<\/jats:italic>\n            \u2208 (0, 1) such that for every base\n            <jats:italic>b<\/jats:italic>\n            , the compressibility ratio of the base-\n            <jats:italic>b<\/jats:italic>\n            expansion of\n            <jats:italic>\u03be<\/jats:italic>\n            is precisely\n            <jats:italic>s<\/jats:italic>\n            ? It is conceivable that there is no such number. Indeed, some works explore \u201czero-one\u201d laws for other feasible dimensions -\n            <jats:italic>i.e.<\/jats:italic>\n            sequences with certain properties either have feasible dimension 0 or 1, taking no value strictly in between.\n          <\/jats:p>\n          <jats:p>\n            However, we answer the question of Lutz and Mayordomo affirmatively by proving a more general result. We show that given any sequence of rational numbers\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJaX\">\\(\\langle q_b \\rangle _{b=2}^{\\infty } \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , we can\n            <jats:italic>explicitly construct<\/jats:italic>\n            a single number\n            <jats:italic>\u03be<\/jats:italic>\n            such that for any base\n            <jats:italic>b<\/jats:italic>\n            , the finite-state dimension\/compression ratio of\n            <jats:italic>\u03be<\/jats:italic>\n            in base\n            <jats:italic>b<\/jats:italic>\n            is\n            <jats:italic>\n              q\n              <jats:sub>b<\/jats:sub>\n            <\/jats:italic>\n            . As a special case, this result implies the existence of absolutely dimensioned numbers for\n            <jats:italic>any<\/jats:italic>\n            given rational dimension between 0 and 1, as posed by Lutz and Mayordomo.\n          <\/jats:p>\n          <jats:p>In our construction, we combine ideas from Wolfgang Schmidt\u2019s construction of absolutely normal numbers from Schmidt (1962), upper bounds on the discrepancy of certain sequences and several new estimates related to exponential sums.<\/jats:p>","DOI":"10.1145\/3729207","type":"journal-article","created":{"date-parts":[[2025,4,18]],"date-time":"2025-04-18T11:23:26Z","timestamp":1744975406000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Real numbers equally compressible in every base"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0214-0598","authenticated-orcid":false,"given":"Satyadev","family":"Nandakumar","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8426-4326","authenticated-orcid":false,"given":"Subin","family":"Pulari","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa170213-5-8"},{"key":"e_1_2_1_2_1","series-title":"SIAM journal on computing 37, 3","volume-title":"Effective strong dimension in algorithmic information and computational complexity","author":"Athreya B","year":"2007","unstructured":"Krishna\u00a0B Athreya, John\u00a0M Hitchcock, Jack\u00a0H Lutz, and Elvira Mayordomo. 2007. Effective strong dimension in algorithmic information and computational complexity. SIAM journal on computing 37, 3 (2007), 671\u2013705."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-015-1209-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/mcom"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms"},{"volume-title":"Probability and measure","author":"Billingsley Patrick","key":"e_1_2_1_6_1","unstructured":"Patrick Billingsley. 1995. Probability and measure(third ed.). John Wiley & Sons, Inc., New York. xiv+593 pages. A Wiley-Interscience Publication."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.040"},{"volume-title":"Elements of Information Theory","author":"Cover M.","key":"e_1_2_1_8_1","unstructured":"T.\u00a0M. Cover and J.\u00a0A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons, Inc., New York, N.Y."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00244-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10474-007-6201-8"},{"key":"e_1_2_1_11_1","first-page":"129","article-title":"The discrepancy of the sequence {(2nx)}. Nederl. Akad. Wetensch","volume":"26","author":"Gaal S.","year":"1964","unstructured":"S. Gaal and L. G\u00e1l. 1964. The discrepancy of the sequence {(2nx)}. Nederl. Akad. Wetensch. Proc. Ser. A 67 = Indag. Math. 26 (1964), 129\u2013143.","journal-title":"Proc. Ser. A 67 = Indag. Math."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00138-5"},{"volume-title":"Mathematical Foundations of Information Theory","author":"Khinchin Ya.","key":"e_1_2_1_13_1","unstructured":"A.\u00a0Ya. Khinchin. 1957. Mathematical Foundations of Information Theory. Dover Publications."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"J.\u00a0F. Koksma. 1974. Diophantische Approximationen. Springer-Verlag Berlin-New York. viii+157 pages. Reprint.","DOI":"10.1007\/978-3-642-65618-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.12.003"},{"key":"e_1_2_1_16_1","unstructured":"L. Kuipers and H. Niederreiter. 1974. Uniform distribution of sequences. Wiley-Interscience [John Wiley & Sons] New York-London-Sydney. xiv+390 pages."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701417723"},{"key":"e_1_2_1_18_1","volume-title":"CCR 2012: 7th conference on computability, complexity and randomnes (July","author":"Lutz H.","year":"2012","unstructured":"Jack\u00a0H. Lutz. 2012. Alan Turing in the twenty-first century: normal numbers, randomness, and finite automata. CCR 2012: 7th conference on computability, complexity and randomnes (July 2012). https:\/\/www.newton.ac.uk\/seminar\/2265\/"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104746"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-26-3-241-251"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.661"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Wolfgang\u00a0M. Schmidt. 1961\/62. \u00dcber die Normalit\u00e4t von Zahlen zu verschiedenen Basen. Acta Arith. 7(1961\/62) 299\u2013309. doi: 10.4064\/aa-7-3-299-309","DOI":"10.4064\/aa-7-3-299-309"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289514"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.286190"},{"key":"e_1_2_1_25_1","volume-title":"Stein and Rami Shakarchi","author":"M.","year":"2003","unstructured":"Elias\u00a0M. Stein and Rami Shakarchi. 2003. Complex analysis. Princeton Lectures in Analysis, Vol.\u00a0 2. Princeton University Press, Princeton, NJ. xviii+379 pages."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,18]],"date-time":"2025-04-18T11:23:31Z","timestamp":1744975411000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,18]]},"references-count":26,"alternative-id":["10.1145\/3729207"],"URL":"https:\/\/doi.org\/10.1145\/3729207","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,4,18]]},"assertion":[{"value":"2023-08-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3729207"}}