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.

[1] 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.
[2] Verónica Becher and Olivier Carton, Normal numbers and nested perfect necklaces, J. Complexity 54 (2019), 101403, 12. MR 3983214, https://doi.org/10.1016/j.jco.2019.03.003
[3] Jean Berstel and Dominique Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007), no. 3, 996–1022. MR 2300777, https://doi.org/10.1016/j.ejc.2005.07.019
[4] N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch., Proc. 49 (1946), 758–764 = Indagationes Math. 8, 461–467 (1946). MR 18142
[5] Joel N. Franklin, Deterministic simulation of random processes, Math. Comp. 17 (1963), 28–59. MR 149640, https://doi.org/10.1090/S0025-5718-1963-0149640-3
[6] Harold Fredricksen and James Maiorana, Necklaces of beads in 𝑘 colors and 𝑘-ary de Bruijn sequences, Discrete Math. 23 (1978), no. 3, 207–210. MR 523071, https://doi.org/10.1016/0012-365X(78)90002-X
[7] Donald E. Knuth, Construction of a random sequence, Nordisk Tidskr. Informationsbehandling (BIT) 5 (1965), 246–250. MR 197434, https://doi.org/10.1007/bf01937504
[8] N. M. Korobov, On functions with uniformly distributed fractional parts, Doklady Akad. Nauk SSSR (N. S.) 62 (1948), 21–22 (Russian). MR 0027012
[9] 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
[10] 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
[11] N. M. Korobov, On normal periodic systems, Izvestiya Akad. Nauk SSSR. Ser. Mat. 16 (1952), 211–216 (Russian). MR 0049248
[12] N. M. Korobov, On completely uniform distribution and conjunctly normal numbers, Izv. Akad. Nauk SSSR. Ser. Mat. 20 (1956), 649–660 (Russian). MR 0083522
[13] N. M. Korobov, Bounds of trigonometric sums involving completely uniformly distributed functions, Soviet Math. Dokl. 1 (1960), 923–926. MR 0130527
[14] 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
[15] 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
[16] Mordechay B. Levin, Discrepancy estimates of completely uniformly distributed and pseudorandom number sequences, Internat. Math. Res. Notices 22 (1999), 1231–1251. MR 1731474, https://doi.org/10.1155/S1073792899000677
[17] M. B. Levin, On the discrepancy estimate of normal numbers, Acta Arith. 88 (1999), no. 2, 99–111. MR 1700240, https://doi.org/10.4064/aa-88-2-99-111
[18] Paul J. McCarthy, Introduction to arithmetical functions, Universitext, Springer-Verlag, New York, 1986. MR 815514
[19] Harald Niederreiter and Arne Winterhof, Applied number theory, Springer, Cham, 2015. MR 3364863
[20] Frank Ruskey, Carla Savage, and Terry Min Yih Wang, Generating necklaces, J. Algorithms 13 (1992), no. 3, 414–430. MR 1176670, https://doi.org/10.1016/0196-6774(92)90047-G
[21] I. E. Šparlinskiĭ, Completely uniform distribution, Zh. Vychisl. Mat. i Mat. Fiz. 19 (1979), no. 5, 1330–1333, 1359 (Russian). MR 550116