Base invariance of feasible dimension

• We prove that polynomial-time computable dimension is closed under base change.
• This contrasts with finite-state dimension not being closed under base change.
• Our argument is nontrivial and quite different from the Kolmogorov complexity one.

Effective fractal dimensions were introduced by Lutz (2003) in order to study the dimensions of individual sequences and quantitatively analyze the structure of complexity classes. Interesting connections of effective dimensions with information theory were also found, implying that constructive dimension as well as polynomial-space dimension are invariant under base change while finite-state dimension is not.We consider the intermediate case, polynomial-time dimension, and prove that it is indeed invariant under base change by a nontrivial argument which is quite different from the Kolmogorov complexity ones used in the other cases.Polynomial-time dimension can be characterized in terms of prediction loss rate, entropy, and compression algorithms. Our result implies that in an asymptotic way each of these concepts is invariant under base change.A corollary of the main theorem is any polynomial-time dimension 1 number (which may be established in any base) is an absolutely normal number, providing an interesting source of absolute normality.