Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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

Registro:

Documento: Artículo
Título:M. Levin's construction of absolutely normal numbers with very low discrepancy
Autor:Álvarez, N.; Becher, V.
Filiación:Departamento de Ciencias e Ingeniería de la Computación, ICIC, Universidad Nacional del Sur-CONICET, Bahía Blanca, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires and CONICET, Buenos Aires, Argentina
Palabras clave:Algorithms; Discrepancy; Normal numbers
Año:2017
Volumen:86
Número:308
Página de inicio:2927
Página de fin:2946
DOI: http://dx.doi.org/10.1090/mcom/3188
Título revista:Mathematics of Computation
Título revista abreviado:Math. Comput.
ISSN:00255718
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v86_n308_p2927_Alvarez

Referencias:

  • Abramowitz, M., Stegun, I.A., (1992) Handbook of Mathematical Functions with Formulas, , Graphs, and Mathematical Tables, Reprint of the 1972 edition, Dover Publications, Inc., New York. MR1225604
  • Becher, V., Bugeaud, Y., Slaman, T.A., On simply normal numbers to different bases (2016) Math. Ann, 364 (1-2), pp. 125-150. , MR3451383
  • Becher, V., Figueira, S., An example of a computable absolutely normal number (2002) Theoret. Comput. Sci, 270 (1-2), pp. 947-958. , MR1871106
  • Becher, V., Figueira, S., Picchi, R., Turing's unpublished algorithm for normal numbers (2007) Theoret. Comput. Sci, 377 (1-3), pp. 126-138. , MR2323391
  • Becher, V., Heiber, P.A., Slaman, T.A., A computable absolutely normal Liouville number (2015) Math. Comp, 84 (296), pp. 2939-2952. , MR3378855
  • Becher, V., Heiber, P.A., Slaman, T.A., A polynomial-time algorithm for computing absolutely normal numbers (2013) Inform. and Comput, 232, pp. 1-9. , MR3132518
  • Becher, V., Slaman, T.A., On the normality of numbers to different bases (2014) J. Lond. Math. Soc, 90 (2), pp. 472-494. , MR3263961 (2)
  • Blum, L., Shub, M., Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness. recursive functions and universal machines, Bull (1989) Amer. Math. Soc, 21 (1), pp. 1-46. , MR974426. (N.S.)
  • Borel, É., Les probabilités d'enombrables et leurs applications arithmétiques (1909) Supplemento di Rendiconti del Circolo Matematico di Palermo, 27, pp. 247-271
  • Bugeaud, Y., (2012) Distribution Modulo One and Diophantine Approximation, 193. , Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge. MR2953186
  • Champernowne, D.G., The construction of decimals normal in the scale of ten J. London Math. Soc. S1-8, (4), p. 254. , MR1573965
  • Downey, R.G., Hirschfeldt, D.R., (2010) Algorithmic Randomness and Complexity, , Theory and Applications of Computability, Springer, New York. MR2732288
  • Drmota, M., Tichy, R.F., (1997) Sequences Discrepancies and Applications, Lecture Notes in Mathematics, 1651. , Springer-Verlag, Berlin. MR1470456
  • Gaal, S., Gál, L., The discrepancy of the sequence (2nx) (1964) Nederl. Akad. Wetensch. Proc. Ser. A 67 = Indag. Math, 26, pp. 129-143. , MR0163089
  • Koksma, J.F., (1950) Some Theorems on Diophantine Inequalities, , Scriptum no. 5, Math. Centrum Amsterdam. MR0038379
  • Kuipers, L., Niederreiter, H., (2006) Uniform Distribution of Sequences, , Dover Publications, Inc., New York
  • Levin, M.B., The uniform distribution of the sequence (aλx) (Russian), pp. 207-222. , Mat. Sb. (N.S.) 98(140) (1975), no. 2 (10), 333. MR0406947
  • Levin, M.B., Absolutely normal numbers (Russian. with French summary), Vestnik Moskov (1979) Univ. Ser. I Mat. Mekh, 1, pp. 31-37 and 87. , MR525299
  • Levin, M.B., On the discrepancy estimate of normal numbers (1999) Acta Arith, 88 (2), pp. 99-111. , MR1700240
  • Madritsch, M., Tichy, R., (2015) Dynamical systems and uniform distribution of sequences, , arXiv:1501.07411v1
  • Scheerer, A.-M., Computable absolutely normal numbers and discrepancies Math. Comp., to appear
  • Schiffer, J., Discrepancy of normal numbers (1986) ActaArith, 47 (2), pp. 175-186. , MR867496
  • Schmidt, W.M., Über die Normalität von Zahlen zu verschiedenen Basen (German) (1961) Acta Arith, 7, pp. 299-309. , MR0140482
  • Turing, A.M., (1992) Pure Mathematics CollectedWorks of A. M. Turing, , North-Holland Publishing Co., Amsterdam. Edited and with an introduction and postscript by J. L. Britton; With a preface by P. N. Furbank. MR1150052

Citas:

---------- APA ----------
Álvarez, N. & Becher, V. (2017) . M. Levin's construction of absolutely normal numbers with very low discrepancy. Mathematics of Computation, 86(308), 2927-2946.
http://dx.doi.org/10.1090/mcom/3188
---------- CHICAGO ----------
Álvarez, N., Becher, V. "M. Levin's construction of absolutely normal numbers with very low discrepancy" . Mathematics of Computation 86, no. 308 (2017) : 2927-2946.
http://dx.doi.org/10.1090/mcom/3188
---------- MLA ----------
Álvarez, N., Becher, V. "M. Levin's construction of absolutely normal numbers with very low discrepancy" . Mathematics of Computation, vol. 86, no. 308, 2017, pp. 2927-2946.
http://dx.doi.org/10.1090/mcom/3188
---------- VANCOUVER ----------
Álvarez, N., Becher, V. M. Levin's construction of absolutely normal numbers with very low discrepancy. Math. Comput. 2017;86(308):2927-2946.
http://dx.doi.org/10.1090/mcom/3188