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:

M. B. Levin used Sobol–Faure low discrepancy sequences with Pascal triangle matrices modulo 2 to construct, a real number x such that the first N terms of the sequence (2 n xmod1) n≥1 have discrepancy O((logN) 2 ∕N). This is the lowest discrepancy known for this kind of sequences. In this note we characterize Levin's construction in terms of nested perfect necklaces, which are a variant of the classical de Bruijn sequences. Moreover, we show that every real number x whose binary expansion is the concatenation of nested perfect necklaces of exponentially increasing order satisfies that the first N terms of (2 n xmod1) n≥1 have discrepancy O((logN) 2 ∕N). For the order being a power of 2, we give the exact number of nested perfect necklaces and an explicit method based on matrices to construct each of them. The computation of the nth digit of the binary expansion of a real number built from nested perfect necklaces requires O(logn) elementary mathematical operations. © 2019 Elsevier Inc.

Registro:

Documento: Artículo
Título:Normal numbers and nested perfect necklaces
Autor:Becher, V.; Carton, O.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales & ICC, Universidad de Buenos Aires & CONICET, Argentina
Institut de Recherche en Informatique Fondamentale, Université Paris Diderot, France
Palabras clave:Low discrepancy; Normal numbers; Perfect necklaces; Number theory; Binary expansions; DeBruijn sequences; Explicit method; Low discrepancy; Low-discrepancy sequences; Mathematical operations; Normal numbers; Perfect necklaces; Matrix algebra
Año:2019
DOI: http://dx.doi.org/10.1016/j.jco.2019.03.003
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity
ISSN:0885064X
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v_n_p_Becher

Referencias:

  • Álvarez, N., Becher, V., Ferrari, P.A., Yuhjtman, S.A., Perfect necklaces (2016) Adv. Appl. Math., 80, pp. 48-61
  • Borel, E., Les probabilités d'enombrables et leurs applications arithmétiques (1909) Supplemento di Rendiconti del Circolo Matematico di Palermo, 27, pp. 247-271
  • de Bruijn, N.G., A combinatorial problem (1946) K. Ned. Akad. Wet., 49, pp. 758-764. , Indagationes Mathematicae 8 (1946) 461-467
  • Bugeaud, Y., Distribution modulo one and diophantine approximation (2012) Cambridge Tracts in Mathematics, 193. , Cambridge University Press Cambridge
  • Drmota, M., Tichy, R., (1997) Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, 1651. , Springer-Verlag
  • Faure, H., Discrépance de suites associées à un système de numération (en dimension s) (1982) Acta Arith., 41
  • Fukuyama, K., The law of the iterated logarithm for discrepancies of {θ n x} (2008) Acta Math. Hungar., 118 (1), pp. 155-170
  • Gál, S., Gál, L., The discrepancy of the sequence {(2 n x)} (1964) K. Ned. Akad. Wet. Proc. Seres A 67 = Indag. Math., 26, pp. 129-143
  • Korobov, N., On completely uniform distributions and jointly normal numbers (1956) Izv. AN SSSR, ser. matem., 20
  • Kuipers, L., Niederreiter, H., Uniform Distribution of Sequences (2006), Dover Publications, Inc. New York; Levin, M.B., On the upper bounds of discrepancy of completely uniform distributed and normal sequences (1995) Abstr. Am. Math. Soc., 16, pp. 556-557. , AMS-IMU joint meeting, Jerusalem, Israel, May 24–26, 1995
  • Levin, M.B., On the discrepancy estimate of normal numbers (1999) Acta Arith., 88 (2), pp. 99-111
  • Philipp, W., Limit theorems for lacunary series and uniform distribution mod 1 (1975) Acta Arith., 26 (3), pp. 241-251
  • Schmidt, W., Irregularities of distribution. vii (1972) Acta Arith., 21, pp. 45-50
  • Ugalde, E., An alternative construction of normal numbers (2000) J. Théor. Nombres Bordeaux, 12, pp. 165-177

Citas:

---------- APA ----------
Becher, V. & Carton, O. (2019) . Normal numbers and nested perfect necklaces. Journal of Complexity.
http://dx.doi.org/10.1016/j.jco.2019.03.003
---------- CHICAGO ----------
Becher, V., Carton, O. "Normal numbers and nested perfect necklaces" . Journal of Complexity (2019).
http://dx.doi.org/10.1016/j.jco.2019.03.003
---------- MLA ----------
Becher, V., Carton, O. "Normal numbers and nested perfect necklaces" . Journal of Complexity, 2019.
http://dx.doi.org/10.1016/j.jco.2019.03.003
---------- VANCOUVER ----------
Becher, V., Carton, O. Normal numbers and nested perfect necklaces. J. Complexity. 2019.
http://dx.doi.org/10.1016/j.jco.2019.03.003