Finite-State Dimension and Real Arithmetic

2006/02/09 by Doty, David, Lutz, Jack H., Nandakumar, Satyadev · 3 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.cs/0602032

Abstract

We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives a new proof of, Wall's 1949 theorem stating that the sum or product of a nonzero rational number and a Borel normal number is always Borel normal.

Cited by

• A Markov-Chain Characterization of Finite-State Dimension and a Generalization of Agafonov's Theorem
• Multi-Head Finite-State Dimension
• Finite-State Dimension and The Davenport Erdős Theorem

Related

• Real numbers equally compressible in every base
• Finite-State Relative Dimension, dimensions of A. P. subsequences and a Finite-State van Lambalgen's theorem
• Finite-State Dimension and The Davenport Erdős Theorem
• Normality preserving operations for Cantor series expansions and\n associated fractals part II
• A Weyl Criterion for Finite-State Dimension and Applications