Feasible analysis, randomness, and base invariance

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.Fil: Figueira, Santiago. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Nies, André. The University Of Auckland; Nueva Zeland