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
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.
- 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
Retrieve articles in Mathematics of Computation with MSC (2010): 11-04, 11K36, 68-04
Retrieve articles in all journals with MSC (2010): 11-04, 11K36, 68-04
Additional Information
Emilio Almansi
Affiliation:
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Email:
ealmansi@gmail.com
Verónica Becher
Affiliation:
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & ICC CONICET, Argentina
MR Author ID:
368040
Email:
vbecher@dc.uba.ar
Keywords:
Completely uniformly distributed sequences,
algorithms
Received by editor(s):
September 24, 2019
Received by editor(s) in revised form:
December 29, 2019, and January 4, 2020
Published electronically:
April 6, 2020
Additional Notes:
Supported by Universidad de Buenos Aires and CONICET, Argentina
Article copyright:
© Copyright 2020
American Mathematical Society