A polynomial-time algorithm for computing absolutely normal numbers

DOI10.1016/J.IC.2013.08.013MaRDI QIDQ386000zbMATH OpenOpenAlexWikidataFDO

Authors Verónica Becher, Pablo Ariel Heiber, Theodore A. Slaman

Publication date 13 December 2013

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2013.08.013

zbMATH Keywords

absolutely normal numberalgorithmcomputable

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Number-theoretic algorithms; complexity (11Y16)

Review text

The authors provide an algorithm that computes an absolutely normal number (i.e., a real number whose digits in its infinite expansion with respect to each base are distributed uniformly) so that the first \(n\) digits in its binary expansion are obtained in time polynomial in \(n\); in fact, just above quadratic. Their algorithm (an efficient variant of Turing's approach on absolutely normal numbers) uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the cost of slowness of convergence to normality (an interesting question is whether the trade-off between rate of computation and rate of convergence to normality is an inherent aspect of any such computation).

Recommendations

• Computing absolutely normal numbers in nearly linear time
• Computable absolutely Pisot normal numbers
• On the construction of absolutely normal numbers
• Computable absolutely normal numbers and discrepancies
• A computable absolutely normal Liouville number

Cites work

• An example of a computable absolutely normal number
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Distribution modulo one and Diophantine approximation
• scientific article; zbMATH DE number 52515 (Why is no real title available?)
• Turing's unpublished algorithm for normal numbers
• Über die Normalität von Zahlen zu verschiedenen Basen

Cited in

(22)

• Liouville, computable, Borel normal and Martin-Löf random numbers
• Computing absolutely normal numbers in nearly linear time
• Unexpected distribution phenomenon resulting from Cantor series expansions
• Normality in non-integer bases and polynomial time randomness
• Feasible analysis, randomness, and base invariance
• Finite-state independence and normal sequences
• Computable absolutely Pisot normal numbers
• Normality of different orders for Cantor series expansions
• Normal numbers and computer science
• Derandomization in game-theoretic probability
• A note on the points with dense orbit under the expansions of different bases
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• On a question of Mendès France on normal numbers
• Quadratic-Time Algorithms for Normal Elements
• Computable absolutely normal numbers and discrepancies
• M. Levin's construction of absolutely normal numbers with very low discrepancy
• Dynamical systems and uniform distribution of sequences
• A computable absolutely normal Liouville number
• An example of a computable absolutely normal number
• On sequential structures in incompressible multidimensional networks
• Super-dense sets and their role in the theory of normal numbers
• Turing's unpublished algorithm for normal numbers

This page was built for publication: A polynomial-time algorithm for computing absolutely normal numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386000)