Finite-state dimension, introduced as a finite-state analogue of Hausdorff dimension, quantifies the lower asymptotic density of information in an infinite sequence as perceived by finite-state automata. It admits several equivalent formulations; two particularly useful are via finite-state gambling strategies and via the optimal asymptotic compression ratio achieved by information-lossless finite-state compressors. Normal sequences represent the highest level of algorithmic randomness visible to finite automata, and are exactly those sequences having finite-state dimension equal to 1. This motivates a bounded-memory notion of randomness extraction: can a finite-state transducer, reading a single sequence streamingly, extract a normal output from a single input source? More modestly, can it always transform the input into an output of strictly higher finite-state dimension? Finite-state transducers can perform surprisingly effective one-pass transformations: even with constant memory they can implement variable-length coding schemes including Shannon-Fano coding, remove local redundancy, and increase the apparent randomness rate on many structured or stochastic inputs. We show randomness extraction using transducers is impossible in a strong, explicit form. For every rational s ∈ (0,1), we construct a near linear-time computable binary sequence X with dim_FS(X) = s such that for every finite-state transducer T, the output satisfies dim_FS(T(X)) ≤ s. Thus, for these sequences, finite-state transduction cannot extract normality - indeed it cannot even improve finite-state dimension. Our proof proceeds by a structural analysis of finite-state transducers together with a dimension-preserving diagonal construction that, for each target s, builds a sequence whose organization defeats every such transducer’s attempt to concentrate randomness. The result is a finite-state analogue of Miller’s non-extractability phenomenon for effective dimension, but its proof relies on substantially different techniques, tailored to the finite-state setting. Furthermore, we show that the impossibility persists even with multiple independent input streams. We treat two notions of independence: (i) Kolmogorov-complexity–based independence (via joint prefix complexity), and (ii) a finite-state notion of relative independence, formulated via relative finite-state dimension. By sharp contrast with the effective-dimension setting - where two independent sources suffice for a uniform effective procedure that boosts randomness rate arbitrarily close to 1 - we show that finite-state dimension exhibits no comparable multi-source extraction phenomenon. Specifically, for every rational s ∈ (0,1) and every fixed k ≥ 2, there exist k independent sources, each of finite-state dimension s, such that for every k-input finite-state transducer T, the output satisfies dim_FS(T(X_1,… ,X_k)) ≤ s. Thus, even independent streams do not allow bounded-memory transduction to output a normal sequence or to increase finite-state dimension.

Finite-state dimension quantifies the asymptotic density of information in an infinite sequence as seen by finite automata, and can be viewed as a bounded-memory analogue of Hausdorff dimension. The theory is by now well developed for base-b expansions. In this paper we initiate the study of finite-state dimension in the setting of continued fractions. This setting brings several new difficulties. The natural reference measure is the Gauss measure, which is the canonical invariant probability measure for the Gauss transformation governing the continued fraction shift. Unlike in the base-b setting, however, this measure is not a product measure. In addition, the digit space is inherently infinite, so the symbolic setting is markedly less rigid than the usual finite-alphabet framework. Continued fraction analogues of effective dimension have received considerable attention in recent years, but a finite-state theory in this setting has so far been missing. Finite-state dimension in the classical setting admits several equivalent formulations. We begin from the original finite-state s-gale viewpoint. In the continued fraction setting, however, the betting odds are no longer fixed in advance: unlike in the base-b case, the fair payoff for the next symbol is determined by conditional Gauss probabilities, and these vary with the current continued fraction cylinder. This makes the choice of a finite-state betting model genuinely nontrivial. We first examine a natural local finite-state betting model for truncated continued fraction digits, in which a gambler may use both the visible local context and an additional finite internal memory. We show that this model is too strong: there is a fixed finite-state gambler that wins at a positive exponential rate on every continued fraction normal point. Consequently, full dimension in this model does not characterize continued fraction normality, and the classical Schnorr-Stimm dichotomy fails. We then isolate the source of this failure and introduce a restricted context-gambler model in which the gambler is allowed to use only the visible truncated context, with no additional hidden finite-state memory. For this restricted model, we obtain, in direct analogy with the base-b setting, an entropy-rate characterization of finite-state dimension in terms of conditional entropy rates, and from this derive an exact finite-state characterization of continued fraction normality: an irrational real has finite-state dimension 1 if and only if its continued fraction expansion is normal. Finally, we prove that the Schnorr-Stimm dichotomy does hold in this restricted setting: on a continued fraction normal point every such gambler either preserves constant capital or loses at an exponential rate, while on every non-normal point some such gambler wins at an exponential rate.

For a fixed alphabet A, an infinite sequence X is said to be normal if every word w over A appears in X with the same frequency as any other word of the same length. A classical result of Agafonov (1966) relates normality to finite automata as follows: a sequence X is normal if and only if any subsequence of X selected by a finite automaton is itself normal. Another theorem of Schnorr and Stimm (1972) gives an alternative characterization: a sequence X is normal if and only if no gambler can win large amounts of money by betting on the sequence X using a strategy that can be described by a finite automaton. Both of these theorems are established in the setting of deterministic finite automata. This raises the question as to whether they can be extended to the setting of probabilistic finite automata. In the case of the Agafonov theorem, a partial positive answer was given by Léchine et al. (MFCS 2024) in a restricted case of probabilistic automata with rational transition probabilities. In this paper, we settle the full conjecture by proving that both the Agafonov and the Schnorr-Stimm theorems hold true for arbitrary probabilistic automata. Specifically, we show that a sequence X is normal if and only if any probabilistic automaton selects a normal subsequence of X with probability 1 and also show that a sequence X is normal if and only if any probabilistic finite-state gambler fails to win on X with probability 1.

Hausdorff $Φ$-dimension is a notion of Hausdorff dimension developed using a restricted class of coverings of a set. We introduce an effective version of Hausdorff $Φ$-dimension, which we call constructive $Φ$-dimension. We prove a point-to-set principle for $Φ$-dimension. We also provide a characterization of constructive $Φ$-dimension using Kolmogorov complexity and $s$-gales. Finally, we apply these tools to study faithfulness of coverings $Φ$. A family of coverings $Φ$ is said to be faithful to Hausdorff dimension if the $Φ$-dimension and Hausdorff dimension coincide for every set. Similarly, $Φ$ is said to be faithful to constructive dimension if the constructive $Φ$-dimension and constructive dimension coincide for every set. We derive the necessary and sufficient conditions for the constructive dimension faithfulness of the coverings generated by the Cantor series expansion, based on the terms of the expansion. Using the point-to-set principle for Cantor coverings, we show that the same condition characterises Hausdorff dimension faithfulness of Cantor coverings, thereby giving an information theoretic proof of the result by Albeverio, Ivanenko, Lebid, and Torbin. We investigate the question of weather the notions of faithfulness at Hausdorff and constructive levels are equivalent. Using a new technique for the construction of sequences satisfying a certain Kolmogorov complexity condition, we show that the notions of ``faithfulness'' of Cantor coverings at the Hausdorff and constructive levels are equivalent, independent of the log-limit condition.

Finite-state dimension, introduced early in this century as a finite-state 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. Finite-state dimension is a robust concept that now has equivalent formulations in terms of finite-state gambling, lossless finite-state data compression, finite-state prediction, entropy rates, and automatic Kolmogorov complexity. The 1972 Schnorr-Stimm dichotomy theorem gave the first automata-theoretic characterization of normal sequences, which had been studied in analytic number theory since Borel defined them in 1909. This theorem implies, in present-day terminology, that a sequence (or a real number having this sequence as its base-b expansion) is normal if and only if it has finite-state 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 finite-state dimension 1 to arbitrary finite-state 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 finite-state dimension 1 to a criterion that characterizes every finite-state dimension. This turns out not to be a routine generalization of the original Weyl criterion. Even though exponential sums may diverge for non-normal numbers, finite-state 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 finite-state dimension of the sequence. This new and surprising connection helps us bring Fourier analytic techniques to bear in proofs in finite-state dimension, yielding a new perspective. We demonstrate the utility of our criterion by substantially improving known results about preservation of finite-state dimension under arithmetic. We strictly generalize the results by Aistleitner and Doty, Lutz and Nandakumar for finite-state 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 finite-state 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.

This work solves an open question in finite-state compressibility posed by Lutz and Mayordomo 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 (2021) 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 \in (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 - 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 $\langle q_b \rangle$, 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 (1962), results regarding low discrepancy sequences and several new estimates related to exponential sums.

We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arbitrarily slow [Ulrich Krengel, 1978]. In contrast, we show that for a class of PSPACE L¹ functions, and a class of PSPACE computable measure-preserving ergodic transformations, the ergodic average exists and is equal to the space average on every EXP random. We establish a partial converse that PSPACE non-randomness can be characterized as non-convergence of ergodic averages. Further, we prove that there is a class of resource-bounded randoms, viz. SUBEXP-space randoms, on which the corresponding ergodic theorem has an exact converse - a point x is SUBEXP-space random if and only if the corresponding effective ergodic theorem holds for x.