Normal numbers and nested perfect necklaces

VERÓNICA BECHER; OLIVIER CARTON

JOURNAL OF COMPLEXITY

ACADEMIC PRESS INC ELSEVIER SCIENCE

Lugar: Amsterdam; Año: 2019 vol. 54 p. 1403 - 1403

0885-064X

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 x mod 1)_{ngeq 1}$ have discrepancy $O((log N)^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 mbox{$(2^n x mod 1)_{ngeq 1}$} have discrepancy $O((log N)^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 $n$-th digit of the binary expansion of a real number built from nested perfect necklaces requires $O(log n)$ elementary mathematical operations.