On the correlation of $ k $ symbols

Yixin Ren; Huaning Liu; Yixin Ren; Huaning Liu

doi:10.3934/math.20241042

AIMS Mathematics

2024, Volume 9, Issue 8: 21455-21470. doi: 10.3934/math.20241042

Previous Article Next Article

Research article Special Issues

On the correlation of $ k $ symbols

Yixin Ren ,
Huaning Liu ^,

Research Center for Number Theory and Its Applications, School of Mathematics, Northwest University, Xi'an 710127, Shaanxi, China

Received: 16 April 2024 Revised: 20 June 2024 Accepted: 24 June 2024 Published: 04 July 2024
MSC : 11K45, 94A55, 94A60

In 2002 Mauduit and Sárközy started to study finite sequences of $ k $ symbols $ E_{N} = \left(e_{1}, e_{2}, \cdots, e_{N}\right)\in \mathcal{A}^{N}, $ where$ \mathcal{A} = \left\{a_{1}, a_{2}, \cdots, a_{k}\right\}, \ \ (k\in \mathbb{N}, k\geq 2) $is a finite set of $ k $ symbols. Bérczi estimated the pseudorandom measures for a truly random sequence $ E_{N} $ of $ k $ symbol. In this paper, we shall study the minimal values of correlation measures for the sequences of $ k $ symbols, developing the methods similar to those introduced by Alon, Anantharam, Gyarmati, and Schmidt, among others.
- pseudorandom sequence,
- $ k $ symbol,
- correlation measure
Citation: Yixin Ren, Huaning Liu. On the correlation of $ k $ symbols[J]. AIMS Mathematics, 2024, 9(8): 21455-21470. doi: 10.3934/math.20241042

Related Papers:

Abstract

In 2002 Mauduit and Sárközy started to study finite sequences of $ k $ symbols $ E_{N} = \left(e_{1}, e_{2}, \cdots, e_{N}\right)\in \mathcal{A}^{N}, $ where$ \mathcal{A} = \left\{a_{1}, a_{2}, \cdots, a_{k}\right\}, \ \ (k\in \mathbb{N}, k\geq 2) $is a finite set of $ k $ symbols. Bérczi estimated the pseudorandom measures for a truly random sequence $ E_{N} $ of $ k $ symbol. In this paper, we shall study the minimal values of correlation measures for the sequences of $ k $ symbols, developing the methods similar to those introduced by Alon, Anantharam, Gyarmati, and Schmidt, among others.

References

[1]	C. Mauduit, A. Sárközy, On finite pseudorandom binary sequencs Ⅰ: measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365–377. http://doi.org/10.4064/AA-82-4-365-377 doi: 10.4064/AA-82-4-365-377
[2]	J. Cassaigne, S. Ferenczi, C. Mauduit, J. Rivat, A. Sárközy, On finite pseudorandom binary sequencs Ⅲ: the Liouville function, Ⅰ, Acta Arith., 87 (1999), 367–390. http://doi.org/10.4064/AA-87-4-367-390 doi: 10.4064/AA-87-4-367-390
[3]	J. Cassaigne, S. Ferenczi, C. Mauduit, J. Rivat, A. Sárközy, On finite pseudorandom binary sequencs Ⅳ: the Liouville function, Ⅱ, Acta Arith., 95 (2000), 343–359. http://doi.org/10.4064/aa-95-4-343-359 doi: 10.4064/aa-95-4-343-359
[4]	E. Fouvry, P. Michel, J. Rivat, A. Sárközy, On the pseudorandomness of the signs of Kloosterman sums, J. Aust. Math. Soc., 77 (2004), 425–436. https://doi.org/10.1017/S1446788700014543 doi: 10.1017/S1446788700014543
[5]	L. Goubin, C. Mauduit, A. Sárközy, Construction of large families of pseudorandom binary sequences, J. Number Theory, 106 (2004), 56–69. https://doi.org/10.1016/j.jnt.2003.12.002 doi: 10.1016/j.jnt.2003.12.002
[6]	K. Gyarmati, On a family of pseudorandom binary sequences, Period. Math. Hung., 49 (2004), 45–63. https://doi.org/10.1007/s10998-004-0522-y doi: 10.1007/s10998-004-0522-y
[7]	K. Gyarmati, Pseudorandom sequences constructed by the power generator, Period. Math. Hung., 52 (2006), 9–26. https://doi.org/10.1007/s10998-006-0009-0 doi: 10.1007/s10998-006-0009-0
[8]	H. Liu, A family of pseudorandom binary sequences constructed by the multiplicative inverse, Acta Arith., 130 (2007), 167–180. http://doi.org/10.4064/aa130-2-6 doi: 10.4064/aa130-2-6
[9]	H. Liu, Gowers uniformity norm and pseudorandom measures of the pseudorandom binary sequences, Int. J. Number Theory, 7 (2011), 1279–1302. https://doi.org/10.1142/S1793042111004137 doi: 10.1142/S1793042111004137
[10]	H. Liu, J. Gao, Large families of pseudorandom binary sequences constructed by using the Legendre symbol, Acta Arith., 154 (2012), 103–108. http://doi.org/10.4064/aa154-1-6 doi: 10.4064/aa154-1-6
[11]	S. R. Louboutin, J. Rivat, A. Sárközy, On a problem of D. H. Lehmer, Proc. Amer. Math. Soc., 135 (2007), 969–975.
[12]	C. Mauduit, J. Rivat, A. Sárközy, Construction of pseudorandom binary sequences using additive characters, Monatsh. Math., 141 (2004), 197–208. https://doi.org/10.1007/s00605-003-0112-8 doi: 10.1007/s00605-003-0112-8
[13]	C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences. Ⅱ: the Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction, J. Number Theory, 73 (1998), 256–276. https://doi.org/10.1006/jnth.1998.2286 doi: 10.1006/jnth.1998.2286
[14]	L. Mérai, Remarks on pseudorandom binary sequences over elliptic curves, Fund. Inf., 114 (2012), 301–308. https://doi.org/10.3233/FI-2012-630 doi: 10.3233/FI-2012-630
[15]	L. Mérai, Construction of pseudorandom binary sequences over elliptic curves using multiplicative characters, Publ. Math. Debrecen, 80 (2012), 199–213. https://doi.org/10.5486/PMD.2011.5057 doi: 10.5486/PMD.2011.5057
[16]	C. Mauduit, A. Sárközy, Construction of pseudorandom binary sequences by using the multiplicative inverse, Acta Math. Hung., 108 (2005), 239–252. https://doi.org/10.1007/s10474-005-0222-y doi: 10.1007/s10474-005-0222-y
[17]	J. Rivat, A. Sárközy, Modular constructions of pseudorandom binary sequences with composite moduli, Period. Math. Hung., 51 (2005), 75–107. https://doi.org/10.1007/s10998-005-0031-7 doi: 10.1007/s10998-005-0031-7
[18]	A. Sárközy, A finite pseudorandom binary sequence, Stud. Sci. Math. Hung., 38 (2001), 377–384. https://doi.org/10.1556/SScMath.38.2001.1-4.28 doi: 10.1556/SScMath.38.2001.1-4.28
[19]	J. Cassaigne, C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences Ⅶ: the measures of pseudorandomness, Acta Arith., 103 (2002), 97–118. http://doi.org/10.4064/AA103-2-1 doi: 10.4064/AA103-2-1
[20]	N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. Rödl, Measures of pseudorandomness for finite sequences: typical values, Proc. London Math. Soc., 95 (2007), 778–812. https://doi.org/10.1112/plms/pdm027 doi: 10.1112/plms/pdm027
[21]	N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. Rödl, Measures of pseudorandomness for finite sequences: minimal values, Comb. Probab. Comput., 15 (2006), 1–29. https://doi.org/10.1017/S0963548305007170 doi: 10.1017/S0963548305007170
[22]	K. Gyarmati, On the correlation of binary sequences, Stud. Sci. Math. Hung., 42 (2005), 79–93. https://doi.org/10.1556/sscmath.42.2005.1.7 doi: 10.1556/sscmath.42.2005.1.7
[23]	V. Anantharam, A technique to study the correlation measures of binary sequences, Discrete Math., 308 (2008), 6203–6209. https://doi.org/10.1016/j.disc.2007.11.043 doi: 10.1016/j.disc.2007.11.043
[24]	K. Gyarmati, C. Mauduit, On the correlation of binary sequences, Ⅱ, Discrete Math., 312 (2012), 811–818. https://doi.org/10.1016/j.disc.2011.09.013 doi: 10.1016/j.disc.2011.09.013
[25]	C. Aistleitner, On the limit distribution of the well-distribution measure of random binary sequences, J. Theor. Nombr. Bordx., 25 (2013), 245–259. https://doi.org/10.5802/jtnb.834 doi: 10.5802/jtnb.834
[26]	K. U. Schmidt, The correlation measures of finite sequences: limiting distributions and minimum values, TTrans. Amer. Math. Soc., 369 (2017), 429–446. http://doi.org/10.1090/tran6650 doi: 10.1090/tran6650
[27]	C. Mauduit, A. Sárközy, On finite pseudorandom sequences of $k$ symbols, Indagat. Math., 13 (2002), 89–101. https://doi.org/10.1016/S0019-3577(02)90008-X doi: 10.1016/S0019-3577(02)90008-X
[28]	R. Ahlswede, C. Mauduit, A. Sárközy, Large families of pseudorandom sequences of $k$ symbols and their complexity-part Ⅰ, In: R. Ahlswede, L. Bäumer, N. Cai, H. Aydinian, V. Blinovsky, C. Deppe, et al., General theory of information transfer and combinatorics, Springer-Verlag, 2006,293–307. https://doi.org/10.1007/11889342_16
[29]	R. Ahlswede, C. Mauduit, A. Sárközy, Large families of pseudorandom sequences of $k$ symbols and their complexity, part Ⅱ, Electron. Notes Discrete Math., 21 (2005), 199–201. https://doi.org/10.1016/j.endm.2005.07.023 doi: 10.1016/j.endm.2005.07.023
[30]	D. Gomez, A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hung., 64 (2012), 161–168. https://doi.org/10.1007/s10998-012-3747-1 doi: 10.1007/s10998-012-3747-1
[31]	Z. Chen, X. Du, C. Wu, Pseudorandomness of certain sequences of $k$ symbols with length $pq$, J. Comput. Sci. Technol., 26 (2011), 276–282. https://doi.org/10.1007/s11390-011-9434-5 doi: 10.1007/s11390-011-9434-5
[32]	K. Mak, More constructions of pseudorandom sequences of $k$ symbols, Finite Fields Appl., 25 (2014), 222–233. https://doi.org/10.1016/j.ffa.2013.09.006 doi: 10.1016/j.ffa.2013.09.006
[33]	B. Gergely, On finite pseudorandom sequences of $k$ symbols, Period. Math. Hung., 47 (2003), 29–44. https://doi.org/10.1023/B:MAHU.0000010809.50836.79 doi: 10.1023/B:MAHU.0000010809.50836.79
[34]	L. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory, 20 (1974), 397–399. https://doi.org/10.1109/TIT.1974.1055219 doi: 10.1109/TIT.1974.1055219

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)