Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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


Author: Kai-Uwe Schmidt
Journal: Trans. Amer. Math. Soc. 369 (2017), 429-446
MSC (2010): Primary 11K45; Secondary 60C05, 68R15
DOI: https://doi.org/10.1090/tran6650
Published electronically: March 21, 2016
MathSciNet review: 3557779
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2009e:94051), https://doi.org/10.1016/j.dam.2006.11.021
  • [2] 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
  • [3] 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, https://doi.org/10.1112/blms/bdu052
  • [4] 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 (2006j:60007), https://doi.org/10.1017/S0963548305007170
  • [5] 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 (2008m:68166), https://doi.org/10.1112/plms/pdm027
  • [6] 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 (2009j:60004)
  • [7] Venkat Anantharam, A technique to study the correlation measures of binary sequences, Discrete Math. 308 (2008), no. 24, 6203-6209. MR 2464908 (2010f:94182), https://doi.org/10.1016/j.disc.2007.11.043
  • [8] 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 (2004c:11139), https://doi.org/10.4064/aa103-2-1
  • [9] William Feller, An introduction to probability theory and its applications. Vol. I, Third edition, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020 (37 #3604)
  • [10] 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 (91a:94001), https://doi.org/10.1109/18.54881
  • [11] 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 (99g:11095)
  • [12] 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 (91e:05077)
  • [13] Idris David Mercer, Autocorrelations of random binary sequences, Combin. Probab. Comput. 15 (2006), no. 5, 663-671. MR 2248319 (2007i:60011), https://doi.org/10.1017/S0963548306007589
  • [14] Kai-Uwe Schmidt, The peak sidelobe level of random binary sequences, Bull. Lond. Math. Soc. 46 (2014), no. 3, 643-652. MR 3210719, https://doi.org/10.1112/blms/bdu021
  • [15] V. M. Sidelnikov, The mutual correlation of sequences, Dokl. Akad. Nauk SSSR 196 (1971), 531-534 (Russian). MR 0316165 (47 #4713)
  • [16] L. R. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory IT-20 (1974), no. 3, 397-399.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11K45, 60C05, 68R15

Retrieve articles in all journals with MSC (2010): 11K45, 60C05, 68R15


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
Email: kaiuwe.schmidt@ovgu.de, kus@math.upb.de

DOI: https://doi.org/10.1090/tran6650
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
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society