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.
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 |
Handle: | http://hdl.handle.net/20.500.12110/paper_0885064X_v_n_p_Becher |
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 |