## 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.

## Additional Information

**Kai-Uwe Schmidt**- Affiliation: Faculty of Mathematics, Otto-von-Guericke University, Universitätsplatz 2, 39106 Magdeburg, Germany
- Address at time of publication: Department of Mathematics, Paderborn University, Warburger Strasse 100, 33098 Paderborn, Germany
- MR Author ID: 789692
- Email: kaiuwe.schmidt@ovgu.de, kus@math.upb.de
- Received by editor(s): January 10, 2014
- Received by editor(s) in revised form: November 24, 2014, and January 6, 2015
- Published electronically: March 21, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**369**(2017), 429-446 - MSC (2010): Primary 11K45; Secondary 60C05, 68R15
- DOI: https://doi.org/10.1090/tran6650
- MathSciNet review: 3557779