Normal numbers and nested perfect necklaces


Abstract in English

M. B. Levin used Sobol-Faure low discrepancy sequences with Pascal matrices modulo $2$ to construct, for each integer $b$, a real number $x$ such that the first $N$ terms of the sequence $(b^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 Levins construction in terms of nested perfect necklaces, which are a variant of the classical de Bruijn necklaces. Moreover, we show that every real number $x$ whose base $b$ expansion is the concatenation of nested perfect necklaces of exponentially increasing order satisfies that the first $N$ terms of $(b^n x mod 1)_{ngeq 1}$ have discrepancy $O((log N)^2/N)$. For base $2$ and 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.

Download