Feasible analysis, randomness, and base invariance

Abstract

We show that polynomial time randomness of a real number does not depend on the choice of a base for representing it. Our main tool is an ‘almost Lipschitz’ condition that we show for the cumulative distribution function associated to martingales with the savings property. Based on a result of Schnorr, we prove that for any base r, n⋅log2n-randomness in base r implies normality in base r, and that n4-randomness in base r implies absolute normality. Our methods yield a construction of an absolutely normal real number which is computable in polynomial time.