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

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 c...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Álvarez, N., Becher, V.
Formato: JOUR
Materias:
Algorithms
Discrepancy
Normal numbers
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_00255718_v86_n308_p2927_Alvarez
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_00255718_v86_n308_p2927_Alvarez
record_format dspace
spelling todo:paper_00255718_v86_n308_p2927_Alvarez2023-10-03T14:36:16Z M. Levin's construction of absolutely normal numbers with very low discrepancy Álvarez, N. Becher, V. Algorithms Discrepancy Normal numbers 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 -2n. 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. © 2017 American Mathematical Society. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_00255718_v86_n308_p2927_Alvarez
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Algorithms
Discrepancy
Normal numbers
spellingShingle Algorithms
Discrepancy
Normal numbers
Álvarez, N.
Becher, V.
M. Levin's construction of absolutely normal numbers with very low discrepancy
topic_facet Algorithms
Discrepancy
Normal numbers
description 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 -2n. 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. © 2017 American Mathematical Society.
format JOUR
author Álvarez, N.
Becher, V.
author_facet Álvarez, N.
Becher, V.
author_sort Álvarez, N.
title M. Levin's construction of absolutely normal numbers with very low discrepancy
title_short M. Levin's construction of absolutely normal numbers with very low discrepancy
title_full M. Levin's construction of absolutely normal numbers with very low discrepancy
title_fullStr M. Levin's construction of absolutely normal numbers with very low discrepancy
title_full_unstemmed M. Levin's construction of absolutely normal numbers with very low discrepancy
title_sort m. levin's construction of absolutely normal numbers with very low discrepancy
url http://hdl.handle.net/20.500.12110/paper_00255718_v86_n308_p2927_Alvarez
work_keys_str_mv AT alvarezn mlevinsconstructionofabsolutelynormalnumberswithverylowdiscrepancy
AT becherv mlevinsconstructionofabsolutelynormalnumberswithverylowdiscrepancy
_version_ 1807316613779685376

Ejemplares similares