Abstract
We study the relationship between two measures of pseudorandomness for families of binary sequences: family complexity and cross-correlation measure introduced by Ahlswede et al. in 2003 and recently by Gyarmati et al., respectively. More precisely, we estimate the family complexity of a family \((e_{i,1},\ldots ,e_{i,N})\in \{-1,+1\}^N\), \(i=1,\ldots ,F\), of binary sequences of length \(N\) in terms of the cross-correlation measure of its dual family \((e_{1,n},\ldots ,e_{F,n})\in \{-1,+1\}^F\), \(n=1,\ldots ,N\). We apply this result to the family of sequences of Legendre symbols with irreducible quadratic polynomials modulo \(p\) with middle coefficient \(0\), that is, \(e_{i,n}=\big (\frac{n^2-bi^2}{p}\big )_{n=1}^{(p-1)/2}\) for \(i=1,\ldots ,(p-1)/2\), where \(b\) is a quadratic nonresidue modulo \(p\), showing that this family as well as its dual family has both a large family complexity and a small cross-correlation measure up to a rather large order.
Similar content being viewed by others
References
Ahlswede, R., Khachatrian, L.H., Mauduit, C., Sárközy, A.: A complexity measure for families of binary sequences. Period. Math. Hung. 46(2), 107–118 (2003). MR 2004667 (2004j:11085)
Golomb, S.W., Gong, G.: Signal Design for Good Correlation. Cambridge University Press, Cambridge (2005). MR 2156522 (2006d:94021)
Goubin, L., Mauduit, C., Sárközy, A.: Construction of large families of pseudorandom binary sequences. J. Number Theory 106(1), 56–69 (2004). MR 2049592 (2004m:11121)
Gyarmati, K., Mauduit, C., Sárközy, A.: The cross correlation measure for families of binary sequences. In: Larcher, G., Pillichshammer, F., Winterhof, A., Xing, C. (eds.) Applications of Algebra and Number Theory. Cambridge University Press, Cambridge (to appear)
Gyarmati, K.: On the complexity of a family based on irreducible polynomials. Finite Fields Appl. (to appear)
Gyarmati, K.: On the complexity of a family related to the Legendre symbol. Period. Math. Hung. 58(2), 209–215 (2009). MR 2531165 (2010f:11131)
Gyarmati, K.: Measures of pseudorandomness. In: Charpin, P., Pott, A., Winterhof, A. (eds.) Finite Fields and Their Applications: Character Sums and Polynomials, Radon Series on Computation and Applied Mathematics, vol. 11, pp. 43–64. Walter de Gruyter, Berlin (2013)
Iwaniec, H., Kowalski, E.: Analytic Number Theory, American Mathematical Society Colloquium Publications, vol. 53. American Mathematical Society, Providence, RI (2004). MR 2061214 (2005h:11005)
Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol. Acta Arith. 82(4), 365–377 (1997). MR 1483689 (99g:11095)
Tietäväinen, A.: Vinogradov’s Method and SomeApplications, Number Theory and Its Applications (Ankara, 1996),Lecture Notes in Pure and Applied Mathematics, vol. 204, pp. 261–282. Dekker, New York (1999). MR 1661670 (99k:11186)
Topuzoğlu, A., Winterhof, A.: Pseudorandom Sequences, Topics in Geometry, Coding Theory and Cryptography, Algebra Applications, vol. 6, pp. 135–166. Springer, Dordrecht (2007)
Winterhof, A.: Some estimates for character sums and applications. Des. Codes Cryptogr. 22(2), 123–131 (2001). MR 1813781 (2002g:11128)
Acknowledgments
The authors thank the anonymous referee for some useful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author is supported by the Austrian Science Fund (FWF): Project F5511-N26 which is part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”. The second author is supported by the Scientific and Technological Research Council of Turkey (TÜBİTAK) under Grant No. 2219.
Rights and permissions
About this article
Cite this article
Winterhof, A., Yayla, O. Family complexity and cross-correlation measure for families of binary sequences. Ramanujan J 39, 639–645 (2016). https://doi.org/10.1007/s11139-014-9649-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11139-014-9649-5
Keywords
- Pseudorandomness
- Binary sequences
- Family complexity
- Cross-correlation measure
- Legendre sequence
- Polynomials over finite fields