Abstract
Finitestate dimension, introduced early in this century as a finitestate version of classical Hausdorff dimension, is a quantitative measure of the lower asymptotic density of information in an infinite sequence over a finite alphabet, as perceived by finite automata. Finitestate dimension is a robust concept that now has equivalent formulations in terms of finitestate gambling, lossless finitestate data compression, finitestate prediction, entropy rates, and automatic Kolmogorov complexity. The 1972 SchnorrStimm dichotomy theorem gave the first automatatheoretic characterization of normal sequences, which had been studied in analytic number theory since Borel defined them in 1909. This theorem implies, in presentday terminology, that a sequence (or a real number having this sequence as its baseb expansion) is normal if and only if it has finitestate dimension 1. One of the most powerful classical tools for investigating normal numbers is the 1916 Weyl’s criterion, which characterizes normality in terms of exponential sums. Such sums are well studied objects with many connections to other aspects of analytic number theory, and this has made use of Weyl’s criterion especially fruitful. This raises the question whether Weyl’s criterion can be generalized from finitestate dimension 1 to arbitrary finitestate dimensions, thereby making it a quantitative tool for studying data compression, prediction, etc. i.e., Can we characterize all compression ratios using exponential sums?.
This paper does exactly this. We extend Weyl’s criterion from a characterization of sequences with finitestate dimension 1 to a criterion that characterizes every finitestate dimension. This turns out not to be a routine generalization of the original Weyl criterion. Even though exponential sums may diverge for nonnormal numbers, finitestate dimension can be characterized in terms of the dimensions of the subsequence limits of the exponential sums. In case the exponential sums are convergent, they converge to the Fourier coefficients of a probability measure whose dimension is precisely the finitestate dimension of the sequence.
This new and surprising connection helps us bring Fourier analytic techniques to bear in proofs in finitestate dimension, yielding a new perspective. We demonstrate the utility of our criterion by substantially improving known results about preservation of finitestate dimension under arithmetic. We strictly generalize the results by Aistleitner and Doty, Lutz and Nandakumar for finitestate dimensions under arithmetic operations. We use the method of exponential sums and our Weyl criterion to obtain the following new result: If y is a number having finitestate strong dimension 0, then dim_FS(x+qy) = dim_FS(x) and Dim_FS(x+qy) = Dim_FS(x) for any x ∈ ℝ and q ∈ ℚ. This generalization uses recent estimates obtained in the work of Hochman [Hochman, 2014] regarding the entropy of convolutions of probability measures.
BibTeX  Entry
@InProceedings{lutz_et_al:LIPIcs.MFCS.2023.65,
author = {Lutz, Jack H. and Nandakumar, Satyadev and Pulari, Subin},
title = {{A Weyl Criterion for FiniteState Dimension and Applications}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {65:165:16},
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/18599},
URN = {urn:nbn:de:0030drops185997},
doi = {10.4230/LIPIcs.MFCS.2023.65},
annote = {Keywords: Finitestate dimension, Finitestate compression, Weyl’s criterion, Exponential sums, Normal numbers}
}
Keywords: 

Finitestate dimension, Finitestate compression, Weyl’s criterion, Exponential sums, Normal numbers 
Collection: 

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

2023 
Date of publication: 

21.08.2023 