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

DOI10.1090/MCOM/3188MaRDI QIDQ5270840zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Nicolás Alvarez, Verónica Becher

Publication date 3 July 2017

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.02004

zbMATH Keywords

algorithmsdiscrepancynormal numbers

Mathematics Subject Classification ID

Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Irregularities of distribution, discrepancy (11K38)

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 double exponential in $n$. We consider variants on the construction that reduce the computational complexity at the expense of an increment in discrepancy.

Recommendations

• On the construction of absolutely normal numbers
• Computable absolutely normal numbers and discrepancies
• A computable absolutely normal Liouville number
• Computing absolutely normal numbers in nearly linear time
• A polynomial-time algorithm for computing absolutely normal numbers

Cites work

• A computable absolutely normal Liouville number
• A polynomial-time algorithm for computing absolutely normal numbers
• Algorithmic randomness and complexity.
• An example of a computable absolutely normal number
• Computable absolutely normal numbers and discrepancies
• Discrepancy of normal numbers
• Distribution modulo one and Diophantine approximation
• Dynamical systems and uniform distribution of sequences
• scientific article; zbMATH DE number 52515 (Why is no real title available?)
• scientific article; zbMATH DE number 3489222 (Why is no real title available?)
• scientific article; zbMATH DE number 3621876 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 3243913 (Why is no real title available?)
• scientific article; zbMATH DE number 3057477 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On simply normal numbers to different bases
• On the discrepancy estimate of normal numbers
• On the normality of numbers to different bases
• Sequences, discrepancies and applications
• The Construction of Decimals Normal in the Scale of Ten
• Turing's unpublished algorithm for normal numbers
• Über die Normalität von Zahlen zu verschiedenen Basen

Cited in

(7)

• Normal numbers and nested perfect necklaces
• On the construction of absolutely normal numbers
• Normal numbers and computer science
• Normal numbers and the normality measure
• Computable absolutely normal numbers and discrepancies
• A computable absolutely normal Liouville number
• The exact order of discrepancy for Levin's normal number in base 2

This page was built for publication: M. Levin's construction of absolutely normal numbers with very low discrepancy

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