Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



M. Levin’s construction of absolutely normal numbers with very low discrepancy

Authors: Nicolás Álvarez and Verónica Becher
Journal: Math. Comp. 86 (2017), 2927-2946
MSC (2010): Primary 11K16, 11K38, 68-04; Secondary 11-04
Published electronically: March 29, 2017
MathSciNet review: 3667031
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Among the currently known constructions of absolutely normal numbers, the one given by Mordechay Levin in 1979 achieves the lowest discrepancy bound. In this work we analyze this construction in terms of computability and computational complexity. We show that, under basic assumptions, it yields a computable real number. The construction does not give the digits of the fractional expansion explicitly, but it gives a sequence of increasing approximations whose limit is the announced absolutely normal number. The $n$-th approximation has an error less than $2^{-2^{n}}$. To obtain the $n$-th approximation the construction requires, in the worst case, a number of mathematical operations that is doubly exponential in $n$. We consider variants on the construction that reduce the computational complexity at the expense of an increment in discrepancy.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K16, 11K38, 68-04, 11-04

Retrieve articles in all journals with MSC (2010): 11K16, 11K38, 68-04, 11-04

Additional Information

Nicolás Álvarez
Affiliation: Departamento de Ciencias e Ingeniería de la Computación, ICIC, Universidad Nacional del Sur-CONICET, Bahía Blanca, Argentina

Verónica Becher
Affiliation: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & CONICET, Argentina
MR Author ID: 368040

Keywords: Normal numbers, discrepancy, algorithms
Received by editor(s): September 28, 2015
Received by editor(s) in revised form: March 28, 2016, and May 9, 2016
Published electronically: March 29, 2017
Additional Notes: The first author was supported by a doctoral fellowship from CONICET, Argentina.
The second author was supported by Agencia Nacional de Promoción Científica y Tecnológica and CONICET, Argentina.
Article copyright: © Copyright 2017 American Mathematical Society