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