Normal numbers and nested perfect necklaces

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2019
Materias:	Low discrepancy Normal numbers Perfect necklaces Number theory Binary expansions DeBruijn sequences Explicit method Low-discrepancy sequences Mathematical operations Matrix algebra
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v_n_p_Becher http://hdl.handle.net/20.500.12110/paper_0885064X_v_n_p_Becher
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_0885064X_v_n_p_Becher
record_format	dspace
spelling	paper:paper_0885064X_v_n_p_Becher2023-06-08T15:46:39Z Normal numbers and nested perfect necklaces 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 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. 2019 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v_n_p_Becher http://hdl.handle.net/20.500.12110/paper_0885064X_v_n_p_Becher
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	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
spellingShingle	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 Normal numbers and nested perfect necklaces
topic_facet	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
description	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.
title	Normal numbers and nested perfect necklaces
title_short	Normal numbers and nested perfect necklaces
title_full	Normal numbers and nested perfect necklaces
title_fullStr	Normal numbers and nested perfect necklaces
title_full_unstemmed	Normal numbers and nested perfect necklaces
title_sort	normal numbers and nested perfect necklaces
publishDate	2019
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v_n_p_Becher http://hdl.handle.net/20.500.12110/paper_0885064X_v_n_p_Becher
_version_	1768543616260636672

Normal numbers and nested perfect necklaces

Ejemplares similares