On the correlation of $k$ symbols

1.   Introduction

The need for pseudorandom sequences arises in cryptographic applications and many papers have been written on this subject. In ^[1], Mauduit and Sárközy introduced the following measures of pseudorandomness for finite pseudorandom binary sequences:

The well-distribution measure of $E_N$ is defined by

where the maximum is taken over all $a$, $b$, $t\in \mathbb{N}$ with

The correlation measure of order $l$ of $E_N$ is defined as

where the maximum is taken over all

and $M$ with

The sequence $E_N$ can be considered as a "good" pseudorandom sequence if both $W\left(E_N\right)$ and $C_l\left(E_N\right)$ (at least for small $l$) are "small" in terms of $N$. Cassaigne et al.^[2,3] studied the well-distribution measures and correlation measures for the Liouville function. Fouvry et al.^[4] examined pseudorandomness measures of Kloosterman sums' signs. Goubin et al.^[5] introduced a construction related to the Legendre symbol for binary sequences. Gyarmati ^[6] utilized the concept of an index discrete logarithm to construct binary sequences with strong pseudorandom properties. Gyarmati^[] studied the psedorandom properties of the power generator, which includes the RSA generator and the Blum-Blum-Shub generator. Liu et al.^[8,9,10] explored pseudorandom binary sequences via multiplicative inverse, Gowers norm, and the Legendre symbol. Louboutin et al.^[11] also obtained the quantitative results on the pseudorandomness of the sequence $(-1)^{n+n*}$. Mauduit et al.^[12] presented a new construction utilizing properties of additive characters. Mauduit et al.^[1,13] investigated a Champernowne-type sequence, the Rudin-Shapiro sequence and the Thue-Morse sequence, extending the approach that involved Legendre symbols. The pseudorandomness of binary sequences over elliptic curves was analyzed in ^[14,15]. Sárközy et al.^[16,17,18] studied binary sequences with strong pseudorandom properties, and utilized character sum estimates by Eichenauer-Hermann and Niederreiter. Cassaigne et al.^[19] estimated $W(E_N)$ and $C_l(E_N)$ for a truly random binary lattice.

Proposition 1.1. ^[19] For all $\epsilon > 0$, there are numbers

and

such that for $N > N_0$ and a random sequence $E_N\in \left\{-1, +1\right\}^N$, we have

Proposition 1.2. ^[19] For all $l\in\mathbb{N}$, $l\geq 2$ and $\epsilon > 0$, there are numbers

and

such that for $N > N_0$ and a random sequence $E_N\in \left\{-1, +1\right\}^N$, we have

Alon et al. extended Propositions 1.1 and 1.2 in ^[20] and provided the lower bound of $C_{2l}(E_N)$ for general sequence $E_N\in \left\{-1, +1\right\}^N$ in ^[21].

Proposition 1.3. ^[21] For any integers $l$ and $N$ such that

and any $E_N \in \{-1, 1\}^N$, we have

Proposition 1.4.^[21] There is an absolute constant $c > 0$ such that, for any positive integers $m$ and $N$ with

and

for all $E_N\in\{-1, +1\}^N$.

Proposition 1.5. ^[21] Let $l$ and $N$ be positive integers with

If $N$ is large enough, then

for all $E_N\in\{-1, +1\}^N$.

Gyarmati^[22] provided lower bound for $C_{2m+1}(E_N)C_{2l}(E_N)$ with $2m+1 > 2l$.

Proposition 1.6. ^[22] If $(m, l)\in\mathbb{N}^2$, $2m+1 > 2l$, and $N\in \mathbb{N}$, then for any $E_N\in\{-1, +1\}^N$, we have

Anantharam^[23] improved Proposition 1.6 in the case $m = l = 1$.

Proposition 1.7.^[23] For any $N\in \mathbb{N}$ big enough and $E_N\in\{-1, +1\}^N$, we have

Gyarmati and Mauduit^[24] generalized the results from ^[22,23].

Proposition 1.8.^[24] For any positive integers $m, l$ and $N$, and any $E_N \in \{-1, 1\}^N$, we have

where the implied constant depends on $m$ and $l$, where

Additionally, they provided the following example showing that Proposition 1.8 is optimal:

Example 1.1. For

we have

and

Aistleitner^[25] provided a tail characterisation of the limiting distribution of $W(E_N)/\sqrt{N}$. Schmidt ^[26] proved that the limiting distribution of

exists, and provided simple proofs of Propositions 1.3 and 1.4. Moreover, Schmidt^[26] obtained explicit constants for Proposition 1.4.

Proposition 1.9.^[26] There exists a sequence of real numbers $c_r$, $c_r > \frac{1}{9}$ for each $r\geq 3$ and

as $r\rightarrow \infty$, such that for all positive integers $m$ and $N$ with

we have

for all $E_N\in\{-1, +1\}^N$.

In 2002, Mauduit and Sárközy^[27] started to study finite sequences of $k$ symbols

where

is a finite set of $k$ symbols. Let

be the set of the $k$-th roots of unity $e^{\frac{2\pi ij}{k}}, j = 1, 2, \cdots, k$. Let $\mathcal{F}$ denote the set of bijections $\varphi$: $\mathcal{A}\longleftrightarrow \mathcal{E}$. The $\mathcal{E}$-well-distribution measure of $E_N$ is defined by

where the maximum is taken over all $\varphi\in\mathcal{F}$ and $a$, $b$, $t\in \mathbb{N}$ with

The $\mathcal{E}$-correlation measure of order $l$ of $E_N$ is defined as

where the maximum is taken over all

and $M$ with

The sequences of $k$ symbol are considered as "good" pseudorandom sequences if both $\Delta\left(E_N\right)$ and $\Gamma_l\left(E_N\right)$ (at least for small $l$) are "small" in terms of $N$ (in particular, both are $o(N)$ as $N\rightarrow \infty$, and ideally it is $N^{\frac{1}{2}+\varepsilon}$). Ahlswede et al.^[28,29] devised "many", "good", PR sequences on $k$ symbols by using multiplicative character and irreducible polynomials. Gomez and Winterhof^[30] derived results on the pseudorandomness $k$ symbols sequences of the Fermat quotients modulo $p$. Two families of sequences of $k$ symbols were constructed using the integers modulo $pq$ for distinct odd primes $p$ and $q$ in ^[31]. Mak^[] utilized rational functions and multiplicative inverses to construct several pseudorandom sequences of $k$ symbols. Mauduit and Sárközy^[27] asked us to say something about the "average" size of the measures. Bérczi^[33] estimated $\Delta\left(E_N\right)$ and $\Gamma_l\left(E_N\right)$ for a truly random sequences of $k$ symbol.

Proposition 1.10.^[33] For all $\epsilon > 0$, there are numbers

and

such that for $N > N_0$ and a random sequence $E_N\in \mathcal{A}^N$, we have

Proposition 1.11.^[33] For all $k\in\mathbb{N}$, $k\geq 2$ and $\epsilon > 0$, there are numbers

and

such that for $N > N_0$ and a random sequence $E_N\in \mathcal{A}^N$, we have

Proposition 1.12.^[33] For all even $k\in\mathbb{N}$, $l\in\mathbb{N}$ and $\epsilon > 0$, there are numbers

such that for $N > N_0$ and a random sequence $E_N\in \mathcal{A}^N$, we have

In this paper we shall develop the previous research methods to study the correlation measures of sequences of $k$ symbols. Based on the research method of ^[21,23,26], we prove Theorems 1.1–1.4. Inspired by the work of Gyarmati and Mauduit^[22,24], we formulate Problem 1.1. Our results are the following:

Theorem 1.1. For any integers $l$ and $N$ with

and any $E_N \in \mathcal{A}^N$, we have

Theorem 1.2. Let the sequence $\{c_r\}$ be defined as in Proposition 1.9. Then, for any positive integers $m$ and $N$ with

and for any $E_N \in \mathcal{A}^N$, we have

Theorem 1.3. Let $l$ and $N$ be positive integers with

If $N$ is large enough, then for all $E_N \in \mathcal{A}^N$, we have

Theorem 1.4. For any $N\in \mathbb{N}$ large enough and $E_N\in\mathcal{A}^N$, we have

Proposition 1.8 and our theorems inspire the following problem:

Problem 1.1. Let $m$ and $l$ be positive integers. Is it true that for large enough $N$ and every $E_N\in\mathcal{A}^N$, we have

The rest of this paper is organized as follows. We shall introduce Welch's bound and prove Theorems 1.1–1.3 in Section 2, and we will prove Theorem 1.4 in Section 3.

2.   Welch's bound and proof of Theorems 1.1–1.3

Schmidt^[26] provided simple proofs for Propositions 1.3 and 1.4 by using Welch's bound on the maximal non-trivial scalar products over a set of vectors.

Lemma 2.1.^[34] Let $M$ and $L\geq 2$ be positive integers, and let $v_1, \cdots, v_{L}$ be elements of $\mathbb{C}^{M}$. For

and

we define the scalar product

where the bar means complex conjugation. Suppose that

for each $i$. Then, for all integers $r\geq 1$, we have

Lemma 2.2.[21, Lemma 2.6] Let $l$ and $n$ be positive integers with

If $n$ is large enough, then there is a family $\mathcal{L}$ of $l$-element subsets of $\{1, 2, \cdots, n\}$ with $|\mathcal{L}| = n$ and such that

for all distinct $L$ and $L'\in \mathcal{L}$.

Now we use Lemma 2.1 to prove Theorems 1.1–1.3. Let

be given and let $M$ be an integer with

We write

Next, we fix a family $\mathcal{L}$ of subsets of the set $\{1, 2, \cdots, N'\}$. Let $\varphi$ be a bijection in $\mathcal{F}$. For

and $L_{i}\in \mathcal{L}, L_{i}\neq \emptyset$, we define the vector

by

Clearly

and for $i\neq j$, we have

Let $L\Theta L'$ be the symmetric difference of the sets $L$ and $L'$, and let

We get

Then, from Lemma 2.1, we have for all integers $r\geq 1$,

2.1.   Proof of Theorem 1.1

We write

Clearly, $1\leq N'\leq N-1$ and

We take for $\mathcal{L}$ a set system of

pairwise disjoint $l$-element subsets $L_1, \cdots, L_t$ of $\{1, 2, \cdots, N'\}$. Noting that $L_i\cap L_j$ is empty for $i\neq j$, and $K = \{2l\}$. By (2.1) and (2.2), we get

This proves Theorem 1.1.

2.2.   Proof of Theorem 1.2

Proof. Let $m$ and $N$ with

Write

we get

We take for $\mathcal{L}$ the set system of all $m$-element subsets of $\{0, 1, \cdots, N'\}$. Hence,

By (2.1) we get

Then, repeating the proof of Theorem 1.3 in ^[26]. Write

for some $\delta\in\{0, 1, 2\}$,

Define $f$: $\{1, 2, \cdots, \left\lfloor\frac{N}{3}\right\rfloor\}\rightarrow \mathbb{Q}$ by

A standard calculation shows that $f$ is monotonically increasing for

and is monotonically decreasing for

Therefore, the minimum value of $f(m)$ is either $f(1)$ or

Moreover, we readily verify that $f(1) > 2$ and

Hence,

Finally,

This completes the proof of Theorem 1.2. □

2.3.   Proof of Theorem 1.3

Proof. Let $l$ and $N$ be positive integers with

Write

we get

and

By Lemma 2.2, we obtain a family $\mathcal{L}$ of $l$-element subsets of $\left\{1, 2, \cdots, N'\right\}$ with

for any two distinct $L, L'\in \mathcal{L}$. Then, from (2.1), we have

which proves Theorem 1.3. □

3.   Proof of Theorem 1.4

Proof. Let $E_N\in\mathcal{A}^N$ be given and let $\varphi$ be a bijection in $\mathcal{F}$. Let $L, M\in\mathbb{N}$ with $L+M\leq N$. We get

On the other hand, we also get

Combining (3.1) and (3.2), we get

where

Switch elements on both sides of the inequality

Case Ⅰ. Assume that

Taking

and

in (3.4), we get

Then, from Theorem 1.1, we immediately have

Case Ⅱ. Suppose that

If

then

While if

then we take

and

in (3.4). Hence, for large enough $N$, we get

Then,

Therefore,

Note that $\Gamma_3\left(E_N\right)\geq 1$. Thus, we get

So, we have

Now combining (3.5)–(3.7), we get

This completes the proof of Theorem 1.4. □

4.   Conclusions

In this paper, our focus centered on exploring the lower bounds of correlation measures of sequences composed of $k$ symbols. This research contributes to a deeper understanding of the sequence properties essential for various applications in mathematics and cryptography.

Author contributions

Yixin Ren: writing-review and editing, writing-original draft, validation, resources, methodology, formal analysis, conceptualization. Huaning Liu: writing-review and editing, resources, methodology, supervision, validation, formal analysis, funding acquisition.

Use of AI tools declaration

The authors declare they have used Artificial Intelligence (AI) tools in the creation of this article.

AI tools used: we utilize ChatGPT to implement linguistic adjustments to the first paragraph of the second page and the conclusion of the article.

Acknowledgments

The authors express their gratitude to the referees for their nice suggestions and comments. This paper is supported by National Natural Science Foundation of China under Grant No. 12071368, the Science and Technology Program of Shaanxi Province of China under Grant No. 2024JC-JCQN-04, and Shaanxi Fundamental Science Research Project for Mathematics and Physics under Grant No. 22JSY017.

Conflict of interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.