Normal numbers and nested perfect necklaces

DOI10.1016/J.JCO.2019.03.003MaRDI QIDQ2274407zbMATH OpenOpenAlexFDO

Authors Verónica Becher, Olivier Carton

Publication date 19 September 2019

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.03713

zbMATH Keywords

low discrepancynormal numbersperfect necklaces

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Irregularities of distribution, discrepancy (11K38) Random number generation in numerical analysis (65C10) Complexity and performance of numerical algorithms (65Y20) Combinatorics on words (68R15)

Abstract: 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}xmod1{)}_{ngeq1}$ 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 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}xmod1{)}_{ngeq1}$ have discrepancy $O((logN{)}^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.

Recommendations

• M. Levin's construction of absolutely normal numbers with very low discrepancy
• On the construction of absolutely normal numbers
• Low discrepancy sequences failing Poissonian pair correlations
• Good permutations for extreme discrepancy
• Normal numbers and the normality measure

Cites work

• An alternative construction of normal numbers
• Discrépance de suites associées à un système de numération (en dimension s)
• Distribution modulo one and Diophantine approximation
• scientific article; zbMATH DE number 3906565 (Why is no real title available?)
• scientific article; zbMATH DE number 3243913 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Irregularities of distribution, VII
• Limit theorems for lacunary series and uniform distribution mod 1
• On the discrepancy estimate of normal numbers
• Perfect necklaces
• Sequences, discrepancies and applications
• The law of the iterated logarithm for discrepancies of \(\{\theta^{n}x\}\)

Cited in

(10)

• Enumerative questions on rooted weighted necklaces
• Insertion in constructed normal numbers
• Low discrepancy sequences failing Poissonian pair correlations
• Extending de Bruijn sequences to larger alphabets
• Completely uniformly distributed sequences based on de Bruijn sequences
• The exact order of discrepancy for Levin's normal number in base 2
• Discrepancy bounds for normal numbers generated by necklaces in arbitrary base
• On extremal factors of de Bruijn-like graphs
• Lyndon pairs and the lexicographically greatest perfect necklace
• A note on matrices over \(\mathbb{Z}\) with entries stemming from binomial coefficients and from Catalan numbers once pure and once taken modulo 2

This page was built for publication: Normal numbers and nested perfect necklaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274407)