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
HTML articles powered by AMS MathViewer

by Emilio Almansi and Verónica Becher HTML | PDF

Math. Comp. 89 (2020), 2537-2551 Request permission

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 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 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 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 10.1016/0012-365X(78)90002-X
Donald E. Knuth, Construction of a random sequence, Nordisk Tidskr. Informationsbehandling (BIT) 5 (1965), 246–250. MR 197434, DOI 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. 38 (1951), 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, DOI 10.1007/978-94-015-8032-8
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. 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 10.1155/S1073792899000677
M. B. Levin, On the discrepancy estimate of normal numbers, Acta Arith. 88 (1999), no. 2, 99–111. MR 1700240, DOI 10.4064/aa-88-2-99-111
Paul J. McCarthy, Introduction to arithmetical functions, Universitext, Springer-Verlag, New York, 1986. MR 815514, DOI 10.1007/978-1-4613-8620-9
Harald Niederreiter and Arne Winterhof, Applied number theory, Springer, Cham, 2015. MR 3364863, DOI 10.1007/978-3-319-22321-6
Frank Ruskey, Carla Savage, and Terry Min Yih Wang, Generating necklaces, J. Algorithms 13 (1992), no. 3, 414–430. MR 1176670, DOI 10.1016/0196-6774(92)90047-G
I. E. Šparlinskiĭ, Completely uniform distribution, Zh. Vychisl. Mat. i Mat. Fiz. 19 (1979), no. 5, 1330–1333, 1359 (Russian). MR 550116