On the Compressibility of Real Numbers: Certain insights using Fourier analytic methods
Subin Pulari (post-doc M2F)

Abstract: Measuring the informational content of real numbers has been a significant area of inquiry in algorithmic information theory. Finite-state compressibility (or finite-state dimension) of a real number is a value in [0, 1] which quantifies the amount of information/randomness in the real number as measured using finite-state automata. Finite-state dimension is the lower asymptotic ratio of compression achievable on an infinite string using information-lossless finite-state compressors. Interestingly, the finite-state dimension of a real number is also equal to the block Shannon entropy rate of the infinite sequence representing the expansion of the real number in a base b. A line of work, originating from Schnorr and Stimm (1972), has established that a number is Borel normal in base b if and only if its base b expansion has finite-state compressibility equal to 1, i.e., is incompressible. Hence, normal numbers are precisely the class of numbers that are incompressible using finite-state compressors.

Most of the prior research on finite-state dimension has relied on combinatorial methods. In this talk we explore how tools from Fourier analysis can be employed to gain new insights into the compressibility of real numbers, including the resolution of an open question:

1. One of the most powerful classical tools for investigating normal numbers (numbers having finite-state dimension 1) is the 1916 Weyl criterion, which characterizes normality in terms of exponential sums. It was unknown whether Weyl criterion could be generalized from characterizing numbers with finite-state dimension 1 to characterizing numbers with arbitrary finite-state dimensions in [0,1]. Such a generalization could make it a quantitative tool for studying data compression, prediction, etc. In this part of the talk, we generalize the Weyl criterion (1916) for normal numbers to characterize sequences having arbitrary finite-state dimension in [0,1]. We also demonstrate several applications of this formulation.

2. 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 0 finite-state dimension in every base. Generalizing this, Lutz and Mayordomo asked the following question: Does there exist any s strictly between 0 and 1 and a real number r such that r has finite state dimension equal to s in every base?. In this part of the talk, we use several tools involving exponential sums and techniques from Schmidt's work in 1960 to construct, for any given s in (0,1], a real number r having finite-state compressibility equal to s in every base. We thereby answer the open question affirmatively.