Arithmetic autocorrelation and pattern distribution of binary sequences

1.   Introduction

Pseudorandom sequences are widely used in measurement, code-division multiple-access (CDMA) systems, wireless communication systems, digital communication systems, and cryptography. The correlation properties analysis of pseudorandom sequences is an important problem for pseudorandom sequences theory.

The arithmetic autocorrelation of a (purely) periodic binary sequence is investigated by Mandelbaum ^[1] on arithmetic codes. Let $(a_n)$ be a binary sequence of (purely) period $T$. For $1\leq \tau < T$, let $(a_{n+\tau})$ be the shift of $(a_n)$. Put

Write

with unique $s_{n, \tau}\in\{0, 1\}$. If $x_0\geq x_\tau$, $(s_{n, \tau})$ is (purely) periodic with period $T$; otherwise, $(s_{n, \tau})$ is eventually periodic with period $T$ from $T$ on (see ^[2]). In terms of the case, the arithmetic autocorrelation function $A(\tau)$ of $(a_n)$ is defined as

where $N_i = |\{T\leq n\leq 2T-1: s_{n, \tau} = i\}|$, $i = 0, 1$.

Compared to the classical autocorrelation, arithmetic autocorrelation is the with-carry correlation function of pseudorandom sequences. Goresky and Klapper ^[3] extended the arithmetic autocorrelation to cross-correlation and gave large families of binary sequences which have ideal arithmetic cross-correlations. Later, they generalized the arithmetic autocorrelation to non-binary sequences in ^[4,5]. For more background, the reader is referred to ^[6].

The arithmetic correlation of sequences is expected to be as small as possible. A nontrivial bound on the arithmetic autocorrelation of the Legendre sequence was proposed in ^[2]. Hofer, Mérai, and Winterhof ^[7] proved the arithmetic autocorrelation and the correlation measure of higher orders have the relation as follows:

Proposition 1.1. ^[7] Put

Then the arithmetic autocorrelation function of a $T$-periodic binary sequence $(e_n)$ satisfies

where $r = \min\{\tau, T-\tau\}$ for $1\leq \tau\leq T-1$.

We write $f(n) = O(g(n))$ or $f(n)\ll g(n)$ if $|f(n)|\leq cg(n)$ for some absolute constant $c > 0$.

Pattern distribution is an important randomness feature of pseudorandom sequences, which reflects any pattern (for fixed length) appearing in a period of the sequence. More precisely, let $(b_n)$ be a binary sequence with period $T$, and let the binary vector $\underline{f} = \{f_0, f_1, \cdots, f_{\ell-1}\}\in\{0, 1\}^{\ell}$ be any pattern (with fixed length $\ell$). The number of pattern distribution is

Ding ^[8] proved the bounds of the pattern distribution of binary Legendre sequences. Golomb ^[9] presented the pattern distribution of binary $m$-sequences. Liu and Ren ^[10] showed the $M$-ary sequences derived from Sidel'nikov sequences have asymptotical uniform pattern distribution. Mauduit and Sárközy ^[11] introduced a relation of pattern distribution and correlation measure of high order. In view of the relation, Hofer, Mérai, and Winterhof ^[7] obtained another relation between correlation measures of high order and arithmetic autocorrelation, indicating that pseudorandom binary sequences with a small correlation measure of high order also have a small arithmetic autocorrelation; that is Proposition 1.1.

Noting that many binary sequences with large "long term" correlations may have small "short term" pattern distributions and thus they still have small arithmetic autocorrelations. In other words, there are binary sequences that have a great value correlation measure of order $\ell$ for large value lags $d_{\ell-1}$, but a small pattern distribution for short lengths of patterns, and then they may have small arithmetic autocorrelation. We shall establish the relation between the arithmetic autocorrelation and the pattern distribution by using the idea in ^[7] with certain modifications.

Theorem 1.2. Let $E_{T} = \{e_0, e_1, \cdots, e_{T-1}\}\in\{0, 1\}^{T}$ be a binary sequence of period $T$. Let $k\geq 1$, $1\leq \tau\leq T-1$ be integers. For any binary vectors $\underline{a} = \{a_0, \cdots, a_k\}\in\{0, 1\}^{k+1}$, $\underline{b} = \{b_0, \cdots, b_k\}\in\{0, 1\}^{k+1}$ and $\underline{c} = \{c_0, \cdots, c_{k+\tau}\}\in\{0, 1\}^{k+\tau+1}$, we write pattern distribution as

when $\tau > k$, otherwise

Denote

and

where the above maximums are taken over all binary vectors $\underline{a}, \underline{b}, \underline{c}$, respectively, and any integer $\tau$ with $1\leq \tau < T$. Put

Then we have

where $r = \min\{\tau, T-\tau\}$ for $1\leq \tau\leq T-1$.

This paper is organized as follows. We establish a relation between arithmetic autocorrelation and pattern distribution of binary sequences; and prove the relation in Section 2. In terms of the relation, we consider the arithmetic autocorrelation of two types of binary sequences constructed by Fermat quotient and generalized cyclotomic classes of order $2$ in Section 3.

2.   Arithmetic autocorrelation and pattern distribution

In this section, our main content is to prove Theorem 1.2 using the idea of Proposition 1.1, with the difference being that we focus on the direct relation between arithmetic autocorrelation and more specific pattern distributions with "short term".

Now we prove Theorem 1.2. As the arithmetic autocorrelation is symmetric with $A(\tau) = A(T-\tau)$(^[7], Proposition 2.1.), we consider $1\leq \tau\leq \lfloor\frac{T}{2}\rfloor$ in the following. Let $1\leq k < m$ be integers. Take $a\in\{0, 1\}$, assume

for $k = 1, \cdots, m-1$ and $n = T, \cdots, 2T-1$. First we let $m+1\leq \tau\leq \lfloor\frac{T}{2}\rfloor$. For fixed $a$, from (1.3) we have the number of patterns

that satisfy the assumptions (2.1) is at least $\frac{T}{2^{2k+2}}-\delta_{2k+2}$. We discuss the specific cases of assumption (2.1). If $a = 1$, from (1.1) we have

This means there is no need to carry to make $s_{n-k, \tau}\geq 0$ for the subtraction of $e_{n-k+\tau} = 0$ from $e_{n-k} = 1$. Hence

Obviously, there are $2^k$ possibilities of the pattern (2.2), then we have at least $\frac{T}{2^{k+2}}-2^k\delta_{2k+2}$ different $n$ with $T\leq n < 2T$ such that $s_{n, \tau} = 1$.

If $a = 0$, from (1.1) we have

This means there is a need to give a carry for the subtraction of $1$ from $0$. Hence

There are also $2^k$ possibilities of the pattern (2.2); thus we have at least $\frac{T}{2^{k+2}}-2^k\delta_{2k+2}$ different $n$ with $T\leq n < 2T$ such that $s_{n, \tau} = 1$.

In both cases, we count at least $\frac{T}{2^{k+1}}-2^{k+1}\delta_{2k+2}$ different $n$ with $T\leq n < 2T$ satisfying $e_{n-k}\neq e_{n-k+\tau}$, $(e_{n-k+j}, e_{n-k+\tau+j})\in\{(0, 0), (1, 1)\}$ for $j = 1, \cdots, k-1$ and $s_{n, \tau} = 1$. Then we have

Analogously, we have the number $N_0$ satisfies

Hence, we obtain

Next, we let $1\leq \tau \leq m$, that indicates some indices in pattern (2.2) coincide, so we have two types of pattern distributions. For fixed $a$, if $k\leq \tau-1$, from (1.3) we have the number of patterns (2.2) that satisfy the assumptions (2.1) is at least

if $k\geq \tau$, we have the pattern as

From (1.4), we know the number of patterns (2.3) satisfies the assumption (2.1) is at least

Similar to before, if $a = 1$, we have

If $a = 0$, we have

In each case, we have $2^k$ possibilities of pattern (2.2) and $2^{\tau-1}$ possible choices of pattern (2.3). Thus, we have at least

different $n$ with $T\leq n < 2T$ satisfies $e_{n-k}\neq e_{n-k+\tau}$, $(e_{n-k+j}, e_{n-k+\tau+j})\in\{(0, 0), (1, 1)\}$ for $j = 1, \cdots, k-1$ and $s_{n, \tau} = 1$.

Let $m' = 2m-\tau$, we obtain

and

Therefore

Choosing

We prove the result of Theorem 1.2.

3.   Arithmetic autocorrelation of binary sequences

We shall study the arithmetic autocorrelation of two pseudorandom binary sequences by applying Theorem 1.2.

3.1.   Binary sequence related to Fermat quotient

Let $p$ be a prime and let $n$ be an integer with $(n, p) = 1$. The Fermat quotient $q_p(n)$ is defined as

We also define $q_p(kp) = 0$ for $k\in \mathbb{Z}$. Fermat quotients have numerous applications in computational and algebraic number theory, and many authors studied their properties (see ^{[12,13,14,15,16,17,18,19]} for details). For example, Gómez and Winterhof ^[15] defined the binary sequence $E_{p^2} = \left(e_0, e_1, \cdots, e_{p^2-1}\right)\in\{0, 1\}^{p^2}$ as follows:

and showed that the upper bound of the $f$-correlation measure of order $\ell$ is $\ell p^{\frac{5}{3}}$. The high linear complexity of $E_{p^2}$ was studied in ^[20]. Chen ^[21] described the trace representation of the above binary sequence $E_{p^2}$ by determining the defining pairs of all binary characteristic sequences of cosets. There is the research on generalizations of the sequence $E_{p^2}$ (see ^[22,23]). The binary sequence $E_{p^2}$ has the desired pseudorandomness; however, the arithmetic correlation of the sequence $E_{p^2}$ remains open. We would study the arithmetic autocorrelation of the sequence $E_{p^2}$ through Theorem 1.2.

In order to calculate the pattern distribution of the binary sequence $E_{p^2}$, an upper bound estimate for multiplicative character sums of Fermat quotients is needed.

Lemma 3.1. ^[15] Let $\chi_1, \cdots, \chi_{\ell}$ be nontrivial multiplicative characters modulo $p$. Then we have

for any integers $0\leq d_1 < \cdots < d_{\ell}\leq p^2-1$ and $1\leq N\leq p^2$.

We use the lemma to analyze the pattern distribution of the binary sequence.

Lemma 3.2. Let $E_{p^2}$ be the binary sequence with period $p^2$ defined in $(3.1)$. Let $1\leq k < \tau < p^2$ be integers. For any pattern $\underline{a} = \{a_0, \cdots, a_k\}\in\{0, 1\}^{k+1}$ and $\underline{b} = \{b_0, \cdots, b_k\}\in\{0, 1\}^{k+1}$, we know

then

for $1\leq k < \frac{1}{6\log_2 p}$.

Proof. From the definition of pattern distribution, we have

In the following, we classify and discuss the first sum in the above equation. Let $\eta$ be the Legendre symbol modulo $p$. When $U\neq\emptyset$ and $V = \emptyset$, by (3.1) and Lemma 3.1, we have

where $|U|$ denotes the number of elements in set $U$. When $U = \emptyset$ and $V\neq\emptyset$, we also have

When $U\neq\emptyset$ and $V\neq\emptyset$, by (3.1) and Lemma 3.1 we obtain

Combing (3.3)–(3.5), we immediately obtain

This completes the proof of lemma. □

Lemma 3.3. Let $E_{p^2}$ be the binary sequence with period $p^2$ defined in (3.1). Let $1\leq \tau\leq k$ be integers. For any pattern $\underline{c} = \{c_0, c_1, \cdots, c_{k+\tau}\}\in\{0, 1\}^{k+\tau+1}$, we have

then

for $1\leq k < \frac{1}{6\log_2 p}$.

Proof. Similar to the proof of Lemma 3.2. Let $\eta$ be the Legendre symbol modulo $p$, from (3.1) and Lemma 3.1 we have

Hence, we obtain

This completes the proof of lemma. □

As a direct result of Theorem 1.2, Lemmas 3.2 and 3.3, we obtain the arithmetic autocorrelation of binary sequence in (3.1).

Theorem 3.4. Let $E_{p^2}$ be the binary sequence with period $p^2$ defined by (3.1). The arithmetic autocorrelation of sequence $E_{p^2}$ satisfies

where $r = \min\{\tau, p^2-\tau\}$ for $1\leq \tau\leq p^2-1$.

We illustrate the upper bound derived from Theorem 3.4 with some actual maximum arithmetic autocorrelation values of the binary sequence $E_{p^2}$ in Figure 1. Then Theorem 3.4 implies that the binary sequence $E_{p^2}$ has a small arithmetic autocorrelation for a large enough period $p^2$. In addition, the $\varepsilon$-correlation measure of sequence $E_{p^2}$ was mentioned in ^[15], we have the upper bound of arithmetic autocorrelation of order of magnitude $O(p^{\frac{11}{6}}(\log p)^{\frac{1}{2}})$ from Proposition 1.1 that equals the upper bound of arithmetic autocorrelation of order of magnitude in Theorem 3.4.

3.2.   The generalized cyclotomic sequence of order $2$

Let $p$ and $q$ be distinct primes, $T = pq$. Let $\gcd(p-1, q-1) = d$ and $e = \frac{(p-1)(q-1)}{d}$. By the Chinese Remainder Theorem: there exists a common primitive root $g$ of both $p$ and $q$, and an integer $x$ such that

and $ord_T(g) = e$. A generalized cyclotomic class of order $d$ is defined by Whiteman ^[24] as

Let $\mathbb{Z}_{pq}$ be the residue class ring modulo $pq$. Whiteman ^[24] proved

The generalized cyclotomic classes is an important approach to constructing pseudorandom sequences. Let $P = \{p, 2p, \cdots, (q-1)p\}$, $Q = \{q, 2q, \cdots, (p-1)q\}$, and $Q_0 = Q\cup \{0\}$. Take $d = 2$, Ding ^[25] defined the generalized cyclotomic sequence of order $2$ $S_{pq} = \{s_0, s_1, \cdots, s_{pq-1}\}$ by

obviously, the sequence is periodic with $pq$ and can be expressed as ^[26]

where $(\frac{\cdot}{p})$ is the Legendre symbol.

The high linear complexity and low autocorrelation values with certain properties of the primes of the generalized cyclotomic sequences $S_{pq}$ have been determined by Ding ^[25,27], respectively. Brandst$\ddot{a}$tter and Winterhof ^[28] got the lower bound of linear complexity profile and the upper bound of aperiodic autocorrelation. Dai et al. ^[29] showed the trace representation of the generalized cyclotomic sequence $S_{pq}$. Hofer and Winterhof ^[30] demonstrated the $2$-adic complexity of the above generalized cyclotomic sequence $S_{pq}$ is close to the period. More generalization refers to ^{[31,32,33,34]}. As we know, the arithmetic autocorrelation of the generalized cyclotomic sequence of order $2$ has yet to be concerned.

We would study the arithmetic autocorrelation of the generalized cyclotomic sequence $S_{pq}$ based on the upper bound estimates of multiplicative character sums with composite moduli.

Lemma 3.5. ^[35] Let $p, q$ be distinct prime numbers and $f(x) = a_{\ell}x^{\ell}+\cdots+a_1x+a_0\in \mathbb{Z}[x]$ and $X, Y$ are real numbers with $0 < Y\leq pq$. Let $\chi$ be a primitive multiplicative character modulo $pq$ and write $\chi = \chi_1\chi_2$, where $\chi_1$ is a character modulo $p$ of order $d_p > 1$ and $\chi_2$ is a character modulo $q$ of order $d_q > 1$. Assume that in $\mathbb{F}_p[x]$, $f(x)$ is not the constant multiple of the $d_p$-power of a polynomial and it has $s_p$ distinct zeros in $\overline{\mathbb{F}}_p$, and in $\mathbb{F}_q[x]$, $f(x)$ is not the constant multiple of the $d_q$-power of a polynomial, and it has $s_q$ distinct zeros in $\overline{\mathbb{F}}_q$, we have

We first represent the generalized cyclotomic sequence using a multiplicative character. Let $\chi$ be the multiplicative character modulo $pq$. By the orthogonality relations of multiplicative character, we have

That means

Let $\mathcal{H} = \{\chi \bmod pq\ |\chi(g) = 1\ \text{and}\ \chi\ \text{is non-trivial}\}$. Since the order of $\chi$ modulo $pq$ is $2$, we have $|\mathcal{H}| = 1$ and $\chi\in \mathcal{H}$ is the primitive multiplicative character modulo $pq$, denoted by $\chi_{pq}$. Hence

According to Theorem 1.2, we will calculate the pattern distribution of the generalized cyclotomic sequence of order $2$ in (3.8).

Lemma 3.6. Let $p$ and $q$ be two distinct primes with $\gcd(p-1, q-1) = 2$. Let $S_{pq}$ be the binary sequence with period $pq$ defined in (3.8). Let $1\leq k < \tau < pq$ be integers. For any pattern $\underline{a} = \{a_0, \cdots, a_k\}\in\{0, 1\}^{k+1}$ and $\underline{b} = \{b_0, \cdots, b_k\}\in\{0, 1\}^{k+1}$, we know

then

for $1\leq k < \frac{\log_2 p+\log_2 q}{4}$.

Proof. From (1.3) we have

Next, we discuss the above three sum equations separately. By (3.9) and Lemma 3.5 we have

and

Similarly, we have

Hence, we obtain

This completes the proof of lemma. □

Lemma 3.7. Let $p$ and $q$ be two distinct primes with $\gcd(p-1, q-1) = 2$. Let $S_{pq}$ be the binary sequence with period $pq$ defined in (3.8). Let $1\leq \tau\leq k$ be integers. For any pattern $\underline{c} = \{c_0, c_1, \cdots, c_{k+\tau}\}\in\{0, 1\}^{k+\tau+1}$, we know

then

for $1\leq k < \frac{\log_2 p+\log_2 q}{4}$.

Proof. By (3.9) and Lemma 3.5, we have

This concludes the proof of lemma. □

Substituting the results of Lemmas 3.6 and 3.7 into Theorem 1.2, we immediately have the arithmetic autocorrelation of the binary generalized cyclotomic sequence.

Theorem 3.8. Let $p$ and $q$ be two distinct primes with $\gcd(p-1, q-1) = 2$. Let $S_{pq}$ be the binary sequence with period $pq$ defined by (3.8). The arithmetic autocorrelation of sequence $S_{pq}$ satisfies

where $r = \min\{\tau, p^2-\tau\}$ for $1\leq \tau\leq p^2-1$.

We enumerate some actual maximum arithmetic autocorrelation values and the upper bounds obtained from Theorem 3.8 for small periods of binary sequence $S_{pq}$ in Figure 2. The graph shows that the upper bound is greater than the actual maximum value of arithmetic autocorrelation. Then the result derived from Theorem 3.8 indicates the arithmetic autocorrelation of the sequence $S_{pq}$ is rather small for a sufficiently large period $pq$.

Remark 3.9. Rivat and Sárközy ^[35] studied the pseudorandom correlation measure of the binary Jacobi sequence of period $pq$ defined with polynomial $f(n)$. For $f(n) = n$, their results imply

that means "long term" correlation of order $4$ of the generalized cyclotomic sequence $S_{pq}$ in (3.8) is large. Then we cannot obtain the arithmetic autocorrelation of the sequence by Proposition 1.1. In contrast to this, we get a rather small "short term" pattern distribution, resulting in a small arithmetic autocorrelation of the binary sequence $S_{pq}$.

4.   Final remarks

Let $p, q$ and $T$ be prime numbers, and $d$, $n$, and $k$ be integers. We list the previously known and currently proposed arithmetic autocorrelation functions $A(\tau)$ as well as conditions with binary sequences in Table 1.

Goresky and Klapper ^[4,5] presented the expected arithmetic autocorrelation over all binary sequences with period $T$, which is $\frac{T}{2^{T-\gcd(\tau, T)}}$ for fixed $\tau$. Subsequently, Hofer, Mérai, and Winterhof ^[7] gave the upper bound of arithmetic autocorrelation for any pseudorandom binary sequence of period $T$ with a small correlation measure, $A(\tau) = O(T^{\frac{3}{4}}(\log_2 T)^{\frac{1}{2}})$. They studied the arithmetic autocorrelation of several sequences, including binary sequences from the Legendre symbol, the Sidelnikov–Lempel–Cohn–Eastman sequence, and the sequence from the trace function, as in the 3–6-th row of Table 1. The arithmetic autocorrelation of these sequences is relatively small with respect to its period when the period is sufficiently large, but obtaining these results relies on a small correlation measure of high order. Moreover, Goresky and Klapper ^[3] proved $\ell$-sequence have ideal arithmetic autocorrelation, as in the $1$-th row of Table 1; however, the classical autocorrelation equals the period, which is not desired. Chen et al. ^[36] presented the arithmetic autocorrelation of the binary $m$-sequence, which amounts to half of the period, as in the $8$-th row of Table 1. Compared with these sequences, the generalized cyclotomic sequence of order $2$ studied in Theorem 3.8 has rather small arithmetic autocorrelation with upper bound of order of magnitude $O(p^{\frac{3}{4}}q^{\frac{3}{4}}(\log(pq))^{3/2})$ for sufficiently large period $pq$, although its correlation measure of order $4$ is quite large. As well as binary sequence $E_{p^2}$ studied in Theorem 3.4, which has a small upper bound of arithmetic autocorrelation relative to its large enough period, its $f$-correlation measure is also small.

5.   Conclusions

In this paper we constructed the relation between arithmetic autocorrelation and pattern distribution of binary sequences. Based on this relation, we proved the arithmetic autocorrelation of the binary sequence defined in ^[15]; and pointed out that the generalized cyclotomic sequence defined in ^[25] has a small "short term" pattern distribution and gave an upper bound of arithmetic autocorrelation. Our results indicate that some pseudorandom sequences with large "long term" pseudorandom correlations of order $k$ may have small arithmetic correlations; and therefore can also be used for research in certain cryptographic fields. It may be interesting to find and study these pseudorandom sequences.

Use of AI tools declaration

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

Acknowledgments

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

Conflict of interest

The authors declare there are no conflicts of interest.