The correlation measures of finite sequences: limiting distributions and minimum values

Schmidt, Kai-Uwe

doi:10.1090/tran6650

The correlation measures of finite sequences: limiting distributions and minimum values
HTML articles powered by AMS MathViewer

by Kai-Uwe Schmidt PDF

Trans. Amer. Math. Soc. 369 (2017), 429-446 Request permission

Abstract:

Three measures of pseudorandomness of finite binary sequences were introduced by Mauduit and Sárközy in 1997 and have been studied extensively since then: the normality measure, the well-distribution measure, and the correlation measure of order $r$. Our main result is that the correlation measure of order $r$ for random binary sequences converges strongly, and so has a limiting distribution. This solves a problem due to Alon, Kohayakawa, Mauduit, Moreira, and Rödl. We also show that the best known lower bounds for the minimum values of the correlation measures are simple consequences of a celebrated result due to Welch concerning the maximum nontrivial scalar products over a set of vectors.

References

R. Ahlswede, J. Cassaigne, and A. Sárközy, On the correlation of binary sequences, Discrete Appl. Math. 156 (2008), no. 9, 1478–1487. MR 2411570, DOI 10.1016/j.dam.2006.11.021
Christoph Aistleitner, On the limit distribution of the well-distribution measure of random binary sequences, J. Théor. Nombres Bordeaux 25 (2013), no. 2, 245–259 (English, with English and French summaries). MR 3228306
Christoph Aistleitner, On the limit distribution of the normality measure of random binary sequences, Bull. Lond. Math. Soc. 46 (2014), no. 5, 968–980. MR 3262198, DOI 10.1112/blms/bdu052
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimal values, Combin. Probab. Comput. 15 (2006), no. 1-2, 1–29. MR 2195573, DOI 10.1017/S0963548305007170
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc. (3) 95 (2007), no. 3, 778–812. MR 2368283, DOI 10.1112/plms/pdm027
Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651, DOI 10.1002/9780470277331
Venkat Anantharam, A technique to study the correlation measures of binary sequences, Discrete Math. 308 (2008), no. 24, 6203–6209. MR 2464908, DOI 10.1016/j.disc.2007.11.043
Julien Cassaigne, Christian Mauduit, and András Sárközy, On finite pseudorandom binary sequences. VII. The measures of pseudorandomness, Acta Arith. 103 (2002), no. 2, 97–118. MR 1904866, DOI 10.4064/aa103-2-1
William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
P. Vijay Kumar and Chao-Ming Liu, On lower bounds to the maximum correlation of complex roots-of-unity sequences, IEEE Trans. Inform. Theory 36 (1990), no. 3, 633–640. MR 1053856, DOI 10.1109/18.54881
Christian Mauduit and András Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), no. 4, 365–377. MR 1483689, DOI 10.4064/aa-82-4-365-377
Colin McDiarmid, On the method of bounded differences, Surveys in combinatorics, 1989 (Norwich, 1989) London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148–188. MR 1036755
Idris David Mercer, Autocorrelations of random binary sequences, Combin. Probab. Comput. 15 (2006), no. 5, 663–671. MR 2248319, DOI 10.1017/S0963548306007589
Kai-Uwe Schmidt, The peak sidelobe level of random binary sequences, Bull. Lond. Math. Soc. 46 (2014), no. 3, 643–652. MR 3210719, DOI 10.1112/blms/bdu021
V. M. Sidel′nikov, The mutual correlation of sequences, Dokl. Akad. Nauk SSSR 196 (1971), 531–534 (Russian). MR 0316165
L. R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory IT-20 (1974), no. 3, 397–399.