Completely uniformly distributed sequences based on de Bruijn sequences

Almansi, Emilio; Becher, Verónica

doi:10.1090/mcom/3534

Completely uniformly distributed sequences based on de Bruijn sequences

Authors: Emilio Almansi and Verónica Becher
Journal: Math. Comp. 89 (2020), 2537-2551
MSC (2010): Primary 11-04, 11K36; Secondary 68-04
DOI: https://doi.org/10.1090/mcom/3534
Published electronically: April 6, 2020
MathSciNet review: 4109577
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We study a construction published by Donald Knuth in 1965 yielding a completely uniformly distributed sequence of real numbers. Knuth’s work is based on de Bruijn sequences of increasing orders and alphabet sizes, which grow exponentially in each of the successive segments composing the generated sequence. In this work we present a similar, albeit simpler, construction using linearly increasing alphabet sizes, and we give an elementary proof showing that the generated sequence is also completely uniformly distributed. In addition, we present an alternative proof of the same result based on Weyl’s criterion.

References

E. Almansi, Completely Equidistributed Sequences Based on De Bruijn Sequences, Tesis de Licenciatura en Ciencias de la Computación. Director: V. Becher, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina, September 2019.

Verónica Becher and Olivier Carton, Normal numbers and nested perfect necklaces, J. Complexity 54 (2019), 101403, 12. MR 3983214, DOI https://doi.org/10.1016/j.jco.2019.03.003

Jean Berstel and Dominique Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007), no. 3, 996–1022. MR 2300777, DOI https://doi.org/10.1016/j.ejc.2005.07.019

N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch., Proc. 49 (1946), 758–764 = Indagationes Math. 8, 461–467 (1946). MR 18142

Joel N. Franklin, Deterministic simulation of random processes, Math. Comp. 17 (1963), 28–59. MR 149640, DOI https://doi.org/10.1090/S0025-5718-1963-0149640-3

Harold Fredricksen and James Maiorana, Necklaces of beads in $k$ colors and $k$-ary de Bruijn sequences, Discrete Math. 23 (1978), no. 3, 207–210. MR 523071, DOI https://doi.org/10.1016/0012-365X%2878%2990002-X

Donald E. Knuth, Construction of a random sequence, Nordisk Tidskr. Informationsbehandling (BIT) 5 (1965), 246–250. MR 197434, DOI https://doi.org/10.1007/bf01937504

N. M. Korobov, On functions with uniformly distributed fractional parts, Doklady Akad. Nauk SSSR (N. S.) 62 (1948), 21–22 (Russian). MR 0027012

N. M. Korobov, Fractional parts of exponential functions, Trudy Mat. Inst. Steklov., v. 38, Trudy Mat. Inst. Steklov., v. 38, Izdat. Akad. Nauk SSSR, Moscow, 1951, pp. 87–96 (Russian). MR 0049245

N. M. Korobov, Normal periodic systems and their applications to the estimation of sums of fractional parts, Izvestiya Akad. Nauk SSSR. Ser. Mat. 15 (1951), 17–46 (Russian). MR 0043146

N. M. Korobov, On normal periodic systems, Izvestiya Akad. Nauk SSSR. Ser. Mat. 16 (1952), 211–216 (Russian). MR 0049248

N. M. Korobov, On completely uniform distribution and conjunctly normal numbers, Izv. Akad. Nauk SSSR. Ser. Mat. 20 (1956), 649–660 (Russian). MR 0083522

N. M. Korobov, Bounds of trigonometric sums involving completely uniformly distributed functions, Soviet Math. Dokl. 1 (1960), 923–926. MR 0130527

N. M. Korobov, Exponential sums and their applications, Mathematics and its Applications (Soviet Series), vol. 80, Kluwer Academic Publishers Group, Dordrecht, 1992. Translated from the 1989 Russian original by Yu. N. Shakhov. MR 1162539

L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0419394

Mordechay B. Levin, Discrepancy estimates of completely uniformly distributed and pseudorandom number sequences, Internat. Math. Res. Notices 22 (1999), 1231–1251. MR 1731474, DOI https://doi.org/10.1155/S1073792899000677

M. B. Levin, On the discrepancy estimate of normal numbers, Acta Arith. 88 (1999), no. 2, 99–111. MR 1700240, DOI https://doi.org/10.4064/aa-88-2-99-111

Paul J. McCarthy, Introduction to arithmetical functions, Universitext, Springer-Verlag, New York, 1986. MR 815514

Harald Niederreiter and Arne Winterhof, Applied number theory, Springer, Cham, 2015. MR 3364863

Frank Ruskey, Carla Savage, and Terry Min Yih Wang, Generating necklaces, J. Algorithms 13 (1992), no. 3, 414–430. MR 1176670, DOI https://doi.org/10.1016/0196-6774%2892%2990047-G

I. E. Šparlinskiĭ, Completely uniform distribution, Zh. Vychisl. Mat. i Mat. Fiz. 19 (1979), no. 5, 1330–1333, 1359 (Russian). MR 550116