Discrete Correlation of Order 2 of Generalized Rudin-Shapiro Sequences on Alphabets of Arbitrary Size

Pierre-Adrien Tahay

doi:10.2478/udt-2020-0001

Abstract

In 2009, Grant, Shallit, and Stoll [Acta Arith. 140 (2009), [345–368] constructed a large family of pseudorandom sequences, called generalized Rudin--Shapiro sequences, for which they established some results about the average of discrete correlation coefficients of order 2 in cases where the size of the alphabet is a prime number or a squarefree product of primes. We establish similar results for an even larger family of pseudorandom sequences, constructed via difference matrices, in the case of an alphabet of any size. The constructions generalize those from Grant et al. In the case where the size of the alphabet is squarefree and where there are at least two prime factors, we obtain an improvement in the error term by comparison with the result of Grant et al.

References

[1] ALLOUCHE, J.-P.—BOUSQUET-MÉLOU, M.: Facteurs des suites de Rudin–Shapiro généralisées, Bull. Belg. Math. Soc. Simon Stevin 1 (1994), 145–164.
Search in Google Scholar Back to article
[2] ALLOUCHE, J.-P.—LIARDET, P.: Generalized Rudin–Shapiro sequences,Acta Arith. 60 (1991), 1–27.10.4064/aa-60-1-1-27
Search in Google Scholar Back to article
[3] ALLOUCHE, J.-P.—SHALLIT, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.10.1017/CBO9780511546563
Search in Google Scholar Back to article
[4] GE, G.: On (g, 4; 1)-difference matrices, Discrete Math. 301 (2005), 164–174.10.1016/j.disc.2005.07.004
Search in Google Scholar Back to article
[5] GRANT, E.—SHALLIT, J.—STOLL, T.: Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin–Shapiro sequences,ActaArith. 140 (2009), 345–368.
Search in Google Scholar Back to article
[6] HEDAYAT, A. S.—SLOANE, N. J. A.—STUFKEN, J.: Orthogonal Arrays. Springer, New York, NY, 1999.10.1007/978-1-4612-1478-6
Search in Google Scholar Back to article
[7] KATZ, D. J.: Sequences with low correlation, Lecture Notes in Comput. Sci. 11321 (2018), 149–172.10.1007/978-3-030-05153-2_8
Search in Google Scholar Back to article
[8] KONIECZNY, J.: Gowers norms for the Thue–Morse and Rudin–Shapiro sequences, Ann. Inst. Fourier 69 (2019), 1897–1913.10.5802/aif.3285
Search in Google Scholar Back to article
[9] LAMPIO, P. H.J.: Classification of difference matrices and complex Hadamard matrices. PhD Thesis, Aalto University, 2015.
Search in Google Scholar Back to article
[10] LAMPIO,P.H.J.—ÖSTERG ARD, P. R. J.: Classification of difference matrices over cyclic groups, J. Statist. Plann. Inference 141 (2011), 1194–1207.10.1016/j.jspi.2010.09.023
Search in Google Scholar Back to article
[11] MAUDUIT, C.—RIVAT, J.: Prime numbers along Rudin–Shapiro sequences, J. Eur. Math. Soc. 17 (2015), 2595–2642.10.4171/JEMS/566
Search in Google Scholar Back to article
[12] MAUDUIT, C.—RIVAT, J.: Rudin–Shapiro sequences along squares,Trans.Amer. Math. Soc. 370 (2018), 7899–7921.10.1090/tran/7210
Search in Google Scholar Back to article
[13] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol,Acta Arith. 82 (1997), 365–377.10.4064/aa-82-4-365-377
Search in Google Scholar Back to article
[14] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences,J. Number Theory 73 (1998), 256–276.10.1006/jnth.1998.2286
Search in Google Scholar Back to article
[15] MÉRAI, L.—RIVAT, J.—SÁRKÖZY, A.: The measures of pseudorandomness and the NIST tests,In: Number-theoretic methods in cryptology, Lecture Notes in Comput. Sci. Vol. 10737, Springer, Cham, 2018, 197–216.
Search in Google Scholar Back to article
[16] QUEFFÉLEC, M.: Une nouvelle propriété des suites de Rudin–Shapiro, Ann. Inst. Fourier (Grenoble) 37 (1987), 115–138.10.5802/aif.1089
Search in Google Scholar Back to article
[17] QUEFFÉLEC, M.: Questions around the Thue–Morse sequence, Unif. Distrib. Theory 13 (2018), 1–25.10.1515/udt-2018-0001
Search in Google Scholar Back to article
[18] RIDER, D.: Transformations of Fourier coefficients, Pacific J. Math. 19 (1966), 347–355.10.2140/pjm.1966.19.347
Search in Google Scholar Back to article

Discrete Correlation of Order 2 of Generalized Rudin-Shapiro Sequences on Alphabets of Arbitrary Size

Abstract

Paradigm

My account