License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.48
URN: urn:nbn:de:0030-drops-177008
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17700/
Nandakumar, Satyadev ;
Pulari, Subin
Real Numbers Equally Compressible in Every Base
Abstract
This work solves an open question in finite-state compressibility posed by Lutz and Mayordomo [Lutz and Mayordomo, 2021] about compressibility of real numbers in different bases.
Finite-state compressibility, or equivalently, finite-state dimension, quantifies the asymptotic lower density of information in an infinite sequence.
Absolutely normal numbers, being finite-state incompressible in every base of expansion, 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.
Generalizing this, Lutz and Mayordomo in [Lutz and Mayordomo, 2021] (see also Lutz [Lutz, 2012]) posed the question: are there numbers which have absolute positive finite-state dimension strictly between 0 and 1 - equivalently, is there a real number ξ and a compressibility ratio s ∈ (0,1) such that for every base b, the compressibility ratio of the base-b expansion of ξ is precisely s? It is conceivable that there is no such number. Indeed, some works explore "zero-one" laws for other feasible dimensions [Fortnow et al., 2011] - i.e. sequences with certain properties either have feasible dimension 0 or 1, taking no value strictly in between.
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 ⟨q_b⟩_{b=2}^∞, we can explicitly construct a single number ξ such that for any base b, the finite-state dimension/compression ratio of ξ in base-b is q_b. As a special case, this result implies the existence of absolutely dimensioned numbers for any given rational dimension between 0 and 1, as posed by Lutz and Mayordomo.
In our construction, we combine ideas from Wolfgang Schmidt’s construction of absolutely normal numbers from [Schmidt, 1961], results regarding low discrepancy sequences and several new estimates related to exponential sums.
BibTeX - Entry
@InProceedings{nandakumar_et_al:LIPIcs.STACS.2023.48,
author = {Nandakumar, Satyadev and Pulari, Subin},
title = {{Real Numbers Equally Compressible in Every Base}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {48:1--48:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17700},
URN = {urn:nbn:de:0030-drops-177008},
doi = {10.4230/LIPIcs.STACS.2023.48},
annote = {Keywords: Finite-state dimension, Finite-state compression, Absolutely dimensioned numbers, Exponential sums, Weyl criterion, Normal numbers}
}
|
Keywords: |
|
Finite-state dimension, Finite-state compression, Absolutely dimensioned numbers, Exponential sums, Weyl criterion, Normal numbers |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
