Correlation measures of binary sequences derived from Euler quotients

Huaning Liu; Zhixiong Chen; Chenhuang Wu; Huaning Liu; Zhixiong Chen; Chenhuang Wu

doi:10.3934/math.2022619

AIMS Mathematics

2022, Volume 7, Issue 6: 11087-11101. doi: 10.3934/math.2022619

Previous Article Next Article

Research article

Correlation measures of binary sequences derived from Euler quotients

1.
Research Center for Number Theory and Its Applications, School of Mathematics, Northwest University, Xi'an 710127, Shaanxi, China
2.
Fujian Key Laboratory of Financial Information Processing, Putian University, Putian 351100, Fujian, China
3.
Key Laboratory of Applied Mathematics of Fujian Province University, Putian University, Putian 351100, Fujian, China

Received: 25 November 2021 Revised: 22 March 2022 Accepted: 22 March 2022 Published: 07 April 2022
MSC : 11B50, 11K45, 94A55, 94A60

Fermat-Euler quotients arose from the study of the first case of Fermat's Last Theorem, and have numerous applications in number theory. Recently they were studied from the cryptographic aspects by constructing many pseudorandom binary sequences, whose linear complexities and trace representations were calculated. In this work, we further study their correlation measures by introducing a new approach based on Dirichlet characters, Ramanujan sums and Gauss sums. Our results show that the $4$ -order correlation measures of these sequences are very large. Therefore they may not be suggested for cryptography.

Keywords:

Citation: Huaning Liu, Zhixiong Chen, Chenhuang Wu. Correlation measures of binary sequences derived from Euler quotients[J]. AIMS Mathematics, 2022, 7(6): 11087-11101. doi: 10.3934/math.2022619

Related Papers:

[1]	Yuchan Qi, Huaning Liu . Binary sequences and lattices constructed by discrete logarithms. AIMS Mathematics, 2022, 7(3): 4655-4671. doi: 10.3934/math.2022259
[2]	Kenan Doğan, Murat Şahin, Oğuz Yayla . Families of sequences with good family complexity and cross-correlation measure. AIMS Mathematics, 2025, 10(1): 38-55. doi: 10.3934/math.2025003
[3]	Jianying Rong, Ting Li, Rui Hua, Xuemei Wang . A class of binary sequences with two-valued cross correlations. AIMS Mathematics, 2024, 9(4): 9091-9106. doi: 10.3934/math.2024442
[4]	Vladimir Edemskiy, Chenhuang Wu . On the $k$ -error linear complexity of binary sequences of periods $p^n$ from new cyclotomy. AIMS Mathematics, 2022, 7(5): 7997-8011. doi: 10.3934/math.2022446
[5]	Ling Zhu . Asymptotic expansion of a finite sum involving harmonic numbers. AIMS Mathematics, 2021, 6(3): 2756-2763. doi: 10.3934/math.2021168
[6]	Robert Reynolds . A short note on a extended finite secant series. AIMS Mathematics, 2023, 8(11): 26882-26895. doi: 10.3934/math.20231376
[7]	Zhao Xiaoqing, Yi Yuan . Square-free numbers in the intersection of Lehmer set and Piatetski-Shapiro sequence. AIMS Mathematics, 2024, 9(12): 33591-33609. doi: 10.3934/math.20241603
[8]	Yixin Ren, Huaning Liu . On the correlation of $k$ symbols. AIMS Mathematics, 2024, 9(8): 21455-21470. doi: 10.3934/math.20241042
[9]	Tongjiang Yan, Pazilaiti Ainiwaer, Lianbo Du . On the 1-error linear complexity of two-prime generator. AIMS Mathematics, 2022, 7(4): 5821-5829. doi: 10.3934/math.2022322
[10]	Tariq Mahmood, Liaqat Ali, Muhammad Aslam, Ghulam Farid . On commutativity of quotient semirings through generalized derivations. AIMS Mathematics, 2023, 8(11): 25729-25739. doi: 10.3934/math.20231312

Abstract

1. Introduction

Let $\mathcal{S} = (s_0, s_1, ..., s_{T-1})$ be a binary sequence over $\mathbb{F}_2 = \{0, 1\}$ and $\ell$ a positive integer. Mauduit and Sárközy ^[16] introduced the correlation measure of order $\ell$ for $\mathcal{S}$ , which is defined as

$C_{\ell}(\mathcal{S}) = \max\limits_{U, D}\left|\sum\limits^{U-1}_{n = 0} (-1)^{s_{n+d_{1}}+s_{n+d_{2}}+\ldots+s_{n+d_{\ell}}}\right|,$

where the maximum is taken over all $U\in \mathbb{N}$ and $D = (d_1, d_2, \ldots, d_\ell)$ with integers $0 \leq d_1 < d_2 < \ldots < d_\ell \le T - U$ .

From the viewpoint of cryptography, it is excepted that measure of order $\ell$ of sequences is as"small" (in terms of $T$ , in particular, is $o(T)$ as $T\rightarrow \infty$ ) as possible. Cassaigne, Mauduit and Sárközy ^[4] studied the values of $C_{\ell}(\mathcal{S})$ for $\mathcal{S}\in \left\{0, 1\right\}^{T}$ chosen equiprobable. It was shown in ^[4] that for every integer $\ell\geq 2$ and real $\varepsilon > 0$ , there are numbers $T_0 = T_0(\varepsilon, \ell)$ and $\delta = \delta(\varepsilon, \ell) > 0$ such that for all $T\geq T_0$ we have

$\delta \sqrt{T} < C_{\ell}(\mathcal{S}) < 5\sqrt{\ell T\log T}$

with probability at least $1-\varepsilon$ .

Additionally, we use the following definition for the periodic correlation measure of order $\ell$ of $\mathcal{S}$ ,

$\theta_\ell(\mathcal{S}) = \max\limits_{D}\left|\sum\limits^{T-1}_{n = 0}(-1)^{s_{n+d_{1}}+s_{n+d_{2}}+\ldots+s_{n+d_{\ell}}}\right|,$

where $D = (d_1, d_2, \ldots, d_\ell)$ and $0\le d_1 < d_2 < \ldots < d_\ell < T$ . It is clear that $\theta_2(\mathcal{S})$ is the (classic) auto-correlation of $\mathcal{S}$ and $\theta_\ell(\mathcal{S})\leq C_{\ell}(\mathcal{S})$ . Thus for every integer $\ell\geq 2$ and real $\varepsilon > 0$ , there is number $T_0 = T_0(\varepsilon, \ell)$ such that for all $T\geq T_0$ we have $\theta_\ell(\mathcal{S}) < 5\sqrt{\ell T\log T}$ with probability at least $1-\varepsilon$ .

In this work, we mainly consider the periodic correlation measure of order $4$ for some binary sequences derived from Euler quotients studied recently.

Let $p$ be a prime and let $n$ be an integer with $\gcd(n, p) = 1$ . From Fermat's little theorem we know that $n^{p-1}\equiv 1\ (\bmod\ p)$ . Then the Fermat quotient $Q_p(n)$ is defined as

$Q_{p}(n) = \frac{n^{p-1}-1}{p} \ (\bmod\ p), \quad 0\leq Q_{p}(n) < p.$

We also define $Q_{p}(n) = 0$ if $\gcd(n, p) > 1$ . Fermat quotients arose from the study of the first case of Fermat's last theorem, and have many applications in number theory (see ^{[2,5,12,14,17,19,20,21]} for details). Define the $p^2$ -periodic binary sequence ${\bf{\overline{s}}} = \left(\overline{s}_0, \overline{s}_1, \cdots, \overline{s}_{p^2-1}\right)$ by

$\begin{eqnarray*} \overline{s}_t = \left\{\begin{array}{ll} 0, & {\rm{if}}\;\; 0\leq \frac{Q_p(t)}{p} < \frac{1}{2}, \\ 1, & {\rm{if}}\;\; \frac{1}{2}\leq \frac{Q_p(t)}{p} < 1. \end{array} \right. \end{eqnarray*}$

The second author (partially with other co-authors) studied the well-distribution measure and correlation measure of order $2$ of ${\bf{\overline{s}}}$ by using estimates for exponential sums of Fermat quotients in ^[11], the linear complexity of ${\bf{\overline{s}}}$ in ^[7,10], and the trace representation of ${\bf{\overline{s}}}$ by determining the defining pairs of all binary characteristic sequences of cosets in ^[6]. In ^[15] the first author with another co-author showed that the $4$ -order correlation measure of ${\bf{\overline{s}}}$ is very large.

Let $m\geq 2$ be an odd number and let $n$ be an integer coprime to $m$ . The Euler's theorem says that $n^{\phi(m)}\equiv 1\ (\bmod\ m)$ , where $\phi$ is the Euler's totient function. Then the Euler quotient $Q_{m}(n)$ is defined as

$Q_{m}(n) = \frac{n^{\phi(m)}-1}{m} \ (\bmod\ m), \quad 0\leq Q_{m}(n) < m.$

We also define $Q_{m}(n) = 0$ if $\gcd(n, m) > 1$ . Agoh, Dilcher and Skula ^[1] studied the detailed properties of Euler quotients. For example, from Proposition 2.1 of ^[1] we have

$\begin{eqnarray} &Q_{m}(n_1n_2)\equiv Q_{m}(n_1)+Q_{m}(n_2) \ (\bmod\ m) \qquad {\rm{for}} \; n_1, n_2\in \mathbb{Z} \;{\rm{with}} \; \gcd(n_1n_2, m) = 1, \end{eqnarray}$

(1.1)

$\begin{eqnarray} &Q_{m}(n+cm)\equiv Q_{m}(n)+cn^{-1}\phi(m) \ (\bmod\ m) \qquad {\rm{for}} \;\; n, c\in\mathbb{Z} \;{\rm{with}} \; \gcd(n, m) = 1. \end{eqnarray}$

(1.2)

Recently many binary sequences were constructed from Euler quotients. For example, let $m = p^{\tau}$ for a fixed number $\tau\geq 1$ , the $p^{\tau+1}$ -periodic sequence ${\bf{\widetilde{s}}} = \left(\widetilde{s}_0, \widetilde{s}_1, \cdots, \widetilde{s}_{p^{\tau+1}-1}\right)$ is defined by

$\begin{eqnarray} \widetilde{s}_t = \left\{\begin{array}{ll} 0, & {\rm{if}}\;\; 0\leq \frac{Q_{p^{\tau}}(t)}{p^{\tau}} < \frac{1}{2}, \\ 1, & {\rm{if}}\;\; \frac{1}{2}\leq \frac{Q_{p^{\tau}}(t)}{p^{\tau}} < 1. \end{array} \right. \end{eqnarray}$

(1.3)

The linear complexity of ${\bf{\widetilde{s}}}$ had been investigated in ^[13] and the trace representation of ${\bf{\widetilde{s}}}$ was given in ^[8].

Moreover, let $m = pq$ be an odd semiprime with $p\mid (q-1)$ , the $pq^2$ -periodic sequence ${\bf{\widehat{s}}} = \left(\widehat{s}_0, \widehat{s}_1, \cdots, \widehat{s}_{pq^2-1}\right)$ is defined by

$\begin{eqnarray} \widehat{s}_t = \left\{\begin{array}{ll} 0, & {\rm{if}}\;\; 0\leq \frac{Q_{pq}(t)}{pq} < \frac{1}{2}, \\ 1, & {\rm{if}}\;\; \frac{1}{2}\leq \frac{Q_{pq}(t)}{pq} < 1. \end{array} \right. \end{eqnarray}$

(1.4)

Recently the minimal polynomials and linear complexities were determined in ^[22] for ${\bf{\widehat{s}}}$ , and the trace representation of ${\bf{\widehat{s}}}$ has been given in ^[23] provided that $2^{q-1}\not\equiv 1 \ (\bmod\ q^2)$ .

In this work, we shall further study the (periodic) correlation measures of ${\bf{\widetilde{s}}}$ and ${\bf{\widehat{s}}}$ by introducing a new approach based on Dirichlet characters, Ramanujan sums and Gauss sums. We state below the main result.

Theorem 1.1. Let $k\geq 5$ be a prime and let $m$ be an odd number with $k\mid m$ . Suppose that $Q_{m}(n)$ is $km$ -periodicand the $km$ -periodic sequence ${\bf{s}} = \left(s_0, s_1, \cdots, s_{km-1}\right)\in\{0, 1\}^{km}$ is defined by

$\begin{eqnarray} s_t = \left\{\begin{array}{ll} 0, & {\rm{if}}\;\; 0\leq \frac{Q_{m}(t)}{m} < \frac{1}{2}, \\ 1, & {\rm{if}}\;\; \frac{1}{2}\leq \frac{Q_{m}(t)}{m} < 1. \end{array} \right. \end{eqnarray}$

(1.5)

Then there exists absolute constant $\delta > 0$ such that

$\begin{eqnarray*} \sum\limits_{t = 0}^{km-1}(-1)^{s_t+s_{t+m}+s_{t+2m}+s_{t+3m}} \geq \frac{1}{3}km-\delta k^{\frac{1}{2}}m(\log m)^4. \end{eqnarray*}$

The restriction $k\geq 5$ can not be relaxed since otherwise we have $s_t = s_{t+3m}$ for all $0\leq t\leq km-1$ . The assumptions $k\mid m$ , $k$ is a prime and $m$ is odd will be vital in the proof of Lemmas 2.1 and 2.2 in Section 2. Taking special values of $m$ and $k$ in Theorem 1.1, we immediately get the correlation measures of ${\bf{\widetilde{s}}}$ and ${\bf{\widehat{s}}}$ .

Corollary 1.1. Let $p\geq 5$ be a prime and let $\tau\geq 1$ be a fixed integer. Let the $p^{\tau+1}$ -periodic sequence ${\bf{\widetilde{s}}} = \left(\widetilde{s}_0, \widetilde{s}_1, \cdots, \widetilde{s}_{p^{\tau+1}-1}\right)$ be defined as in $(1.3)$ .Then we have

$\sum\limits_{t = 0}^{p^{\tau+1}-1}(-1)^{\widetilde{s}_t+\widetilde{s}_{t+p^{\tau}} +\widetilde{s}_{t+2p^{\tau}}+\widetilde{s}_{t+3p^{\tau}}} \geq\frac{1}{3}p^{\tau+1}-\delta p^{\tau+\frac{1}{2}}(\log p^{\tau})^4.$

Corollary 1.2. Let $p$ and $q$ be two distinct odd primes with $p\mid (q-1)$ and $q\geq 5$ , and letthe $pq^2$ -periodic sequence ${\bf{\widehat{s}}} = \left(\widehat{s}_0, \widehat{s}_1, \cdots, \widehat{s}_{pq^2-1}\right)$ be defined as in $(1.4)$ .Then we have

$\sum\limits_{t = 0}^{pq^2-1}(-1)^{\widehat{s}_t+\widehat{s}_{t+pq}+\widehat{s}_{t+2pq}+\widehat{s}_{t+3pq}} \geq \frac{1}{3}pq^2-\delta pq^{\frac{3}{2}}(\log pq)^4.$

Our results indicate that the correlation measures of order $4$ of ${\bf{\widetilde{s}}}$ and ${\bf{\widehat{s}}}$ are very large provided that $p$ and $q$ are sufficiently large. Therefore these sequences are not suitable for cryptography.

To prove Theorem 1.1, we introduce basic properties of Dirichlet characters, Ramanujan sums and Gauss sums, and then prove two lemmas on the mean values of characters sums in Section 2. We express $(-1)^{s_t}$ in terms of character sums in Section 3 to finish the proof of Theorem 1.1 by using the results showed in Section 2.

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

2. Dirichlet characters and Gauss sums

Let $N > 1$ be an integer. The Ramanujan sum is denoted by

$c_{N}(n) = \sum\limits_{\begin{array}{*{20}{c}} {t = 0}\\ {\gcd (t, N) = 1} \end{array}}^{N - 1} {{e_N}(tn)},$

where $e_{N}(x) = \hbox{e}^{2\pi\sqrt{-1}x/N}$ . We have

$\begin{eqnarray} c_{N}(n) = \mu\left(\frac{N}{\gcd(n, N)}\right)\phi(N)\phi\left(\frac{N}{\gcd(n, N)}\right)^{-1}, \end{eqnarray}$

(2.1)

where $\mu$ is the Möbius function.

We recall that a Dirichlet character $\chi$ modulo $N$ is a function satisfying:

(i). $\chi(t_1t_2) = \chi(t_1)\chi(t_2)$ ,

(ii). $\chi(t+N) = \chi(t)$ ,

(iii). $\chi(t) = 0$ for $\gcd(t, N) > 1$ ,

(iv). $\chi$ is not identically zero.

When $\chi(n) = 1$ for all $n$ with $\gcd(n, N) = 1$ we say $\chi$ is the trivial character modulo $N$ . An integer $d\mid N$ is called an induced modulus for $\chi$ if $\chi(a) = 1$ whenever $\gcd(a, N) = 1$ and $a\equiv 1\ (\bmod\ d)$ . A Dirichlet character $\chi$ mod $N$ is said to be primitive mod $N$ if it has no induced modulus $d < N$ . The smallest induced modulus $d$ for $\chi$ is called the conductor of $\chi$ . Every non-trivial character $\chi$ modulo $N$ can be uniquely written as $\chi = \chi_0\chi^{*}$ , where $\chi_0$ is the trivial character modulo $N$ and $\chi^{*}$ is the primitive character modulo the conductor of $\chi$ .

For a Dirichlet character $\chi$ mod $N$ , the Gauss sum associated with $\chi$ is defined by

$G(n, \chi) = \sum\limits_{t = 0}^{N-1}\chi(t)e_N(tn).$

Let $N^{*}$ be the conductor for $\chi$ and let $\chi^{*}$ be the induced primitive character.

Let $N_1$ be the maximal divisor of $N$ such that $N_1$ and $N^{*}$ have the same prime divisors. Then we have

$\begin{eqnarray} G(n, \chi) = \left\{\begin{array}{l} \chi^*\left(\frac{n}{\gcd(n, N)}\right)^{-1}\chi^*\left(\frac{N}{N^*\gcd(n, N)}\right) \mu\left(\frac{N}{N^*\gcd(n, N)}\right) \\ \quad\times\phi(N)\phi\left(\frac{N}{\gcd(n, N)}\right)^{-1}G(1, \chi^*), \ \ \qquad{\rm{if}}\;\; N^* = \frac{N_1}{\gcd(n, N_1)}, \\ 0, \qquad\qquad\qquad\qquad\qquad\qquad\qquad {\rm{if}}\;\; N^*\neq\frac{N_1}{\gcd(n, N_1)}. \end{array} \right. \end{eqnarray}$

(2.2)

See Chapter 8 of ^[3] or Chapter 1 of ^[18] for more details of Dirichlet characters, Ramanujan sums and Gauss sums.

Now we prove two lemmas on the mean values of characters sums.

Lemma 2.1. Let $k\geq 5$ be a prime and let $m$ be an odd number with $k\mid m$ .Let $\chi$ be a Dirichletcharacter modulo $km$ such that $\chi^m$ is trivial and $\chi^{m'}$ is not trivialfor all $1\leq m' < m$ . For integers $a_1$ , $a_2$ , $a_3$ and $a_4$ we have

$\begin{eqnarray*} &&\sum\limits_{t = 0}^{km-1}\chi\left(t^{a_1}(t+m)^{a_2}(t+2m)^{a_3}(t+3m)^{a_4}\right) \\ && = \left\{\begin{array}{ll} k\phi(m), & if\;\; m\; \mid (a_1+a_2+a_3+a_4)\; and\; k\;\mid (a_2+2a_3+3a_4), \\ O\left(\phi(m)\phi(k)^{-1}k^{\frac{3}{2}}\right), & otherwise. \end{array} \right. \end{eqnarray*}$

Proof. Note that if $k\geq 5$ , then the polynomials $t$ , $t+m$ , $t+2m$ and $t+3m$ are distinct. By the condition $k\mid m$ and the properties of residue systems we get

$\begin{eqnarray*} &&\sum\limits_{t = 0}^{km-1}\chi\left(t^{a_1}(t+m)^{a_2}(t+2m)^{a_3}(t+3m)^{a_4}\right) \nonumber\\ && = \mathop{\sum\limits_{y = 0}^{m-1}}_{\gcd(y, m) = 1}\sum\limits_{z = 0}^{k-1} \chi\left((y+zm)^{a_1}(y+zm+m)^{a_2}(y+zm+2m)^{a_3}(y+zm+3m)^{a_4}\right) \nonumber\\ && = \mathop{\sum\limits_{y = 0}^{m-1}}_{\gcd(y, m) = 1}\sum\limits_{z = 0}^{k-1} \chi\left((y^{a_1}+a_1y^{a_1-1}zm)(y^{a_2}+a_2y^{a_2-1}(z+1)m)\right) \nonumber\\ &&\qquad\times\chi\left((y^{a_3}+a_3y^{a_3-1}(z+2)m) (y^{a_4}+a_4y^{a_4-1}(z+3)m)\right)\nonumber\\ && = \mathop{\sum\limits_{y = 0}^{m-1}}_{\gcd(y, m) = 1}\chi\left(y^{a_1+a_2+a_3+a_4}\right)\nonumber\\ &&\qquad\times\sum\limits_{z = 0}^{k-1}\chi\left((1+a_1y^{-1}zm)(1+a_2y^{-1}(z+1)m) (1+a_3y^{-1}(z+2)m)(1+a_4y^{-1}(z+3)m)\right). \end{eqnarray*}$

By the condition $k\mid m$ we further deduce that

$\begin{eqnarray*} &&\chi(1+(n+k)m) = \chi(1+nm), \\ && \chi(1+n_1m)\chi(1+n_2m) = \chi(1+(n_1+n_2)m), \end{eqnarray*}$

which show that $\chi\left(1+nm\right)$ is a non-trivial additive character modulo $k$ . Since $k$ is a prime, there is uniquely an integer $\beta$ such that $1\leq \beta\leq k-1$ and $\chi\left(1+nm\right) = e_k(\beta n)$ . Hence,

$\begin{eqnarray*} &&\sum\limits_{t = 0}^{km-1}\chi\left(t^{a_1}(t+m)^{a_2}(t+2m)^{a_3}(t+3m)^{a_4}\right) = \mathop{\sum\limits_{y = 0}^{m-1}}_{\gcd(y, m) = 1}\chi\left(y^{a_1+a_2+a_3+a_4}\right) \nonumber\\ &&\qquad\times\sum\limits_{z = 0}^{k-1}e_k\left(\beta(a_1y^{-1}z+a_2y^{-1}(z+1) +a_3y^{-1}(z+2)+a_4y^{-1}(z+3))\right). \end{eqnarray*}$

By the orthogonality relation for additive character

$\begin{eqnarray} \sum\limits_{u = 0}^{N-1}e_N(u\theta) = \left\{\begin{array}{ll} N, & {\rm{if}}\;\; N\mid \theta, \\ 0, & {\rm{if}}\;\; N\nmid \theta, \end{array} \right. \end{eqnarray}$

(2.3)

we have

$\begin{eqnarray*} &&\sum\limits_{z = 0}^{k-1}e_k\left(\beta(a_1y^{-1}z+a_2y^{-1}(z+1) +a_3y^{-1}(z+2)+a_4y^{-1}(z+3))\right)\\ && = e_k\left(\beta(a_2+2a_3+3a_4)y^{-1}\right) \sum\limits_{z = 0}^{k-1}e_k\left(\beta y^{-1}(a_1+a_2+a_3+a_4)z\right)\\ && = \left\{\begin{array}{ll} ke_k\left(\beta(a_2+2a_3+3a_4)y^{-1}\right), & {\rm{if}}\;\; k\mid (a_1+a_2+a_3+a_4), \\ 0, & {\rm{if}}\;\; k\nmid (a_1+a_2+a_3+a_4). \end{array} \right. \end{eqnarray*}$

Then from

$\begin{eqnarray*} &&\sum\limits_{t = 0}^{km-1}\chi\left(t^{a_1}(t+m)^{a_2}(t+2m)^{a_3}(t+3m)^{a_4}\right)\\ && = \left\{\begin{array}{ll} k\mathop {\mathop \sum \limits_{y = 0}^{m - 1} }\limits_{\gcd (y, m) = 1} \chi^{a_1+a_2+a_3+a_4}\left(y\right) e_k\left(\beta(a_2+2a_3+3a_4)y^{-1}\right), & {\rm{if}}\;\; k\mid (a_1+a_2+a_3+a_4), \\ 0, & {\rm{if}}\;\; k\nmid (a_1+a_2+a_3+a_4). \end{array} \right. \end{eqnarray*}$

Since $k\mid m$ , we know that $\chi^{a_1+a_2+a_3+a_4}$ is a multiplicative character modulo $m$ if $k\mid a_1+a_2+a_3+a_4$ . Then

$\mathop{\sum\limits_{y = 0}^{m-1}}\limits_{\gcd(y, m) = 1}\chi^{a_1+a_2+a_3+a_4}\left(y\right) e_k\left(\beta(a_2+2a_3+3a_4)y^{-1}\right) = \\ \mathop{\sum\limits_{y = 0}^{m-1}}\limits_{\gcd(y, m) = 1}\chi^{-(a_1+a_2+a_3+a_4)}\left(y\right) e_m\left(\frac{m}{k}\beta(a_2+2a_3+3a_4)y\right)$

is a Gauss sum associated with $\chi^{-(a_1+a_2+a_3+a_4)}$ modulo $m$ . By the assumption $\chi^m$ is trivial and $\chi^{m'}$ is not trivial for all $1\leq m' < m$ we know that $\chi^{-(a_1+a_2+a_3+a_4)}$ is trivial if and only if $m\mid a_1+a_2+a_3+a_4$ . Then from (2.1) and (2.2) we get

$\mathop{\sum\limits_{y = 0}^{m-1}}\limits_{\gcd(y, m) = 1}\chi^{-(a_1+a_2+a_3+a_4)}\left(y\right) e_m\left(\frac{m}{k}\beta(a_2+2a_3+3a_4)y\right) = \phi(m),$

if $m\mid (a_1+a_2+a_3+a_4)$ and $k\mid (a_2+2a_3+3a_4)$ , and

$\begin{eqnarray*} &&\Bigg|\mathop{\sum\limits_{y = 0}^{m-1}}_{\gcd(y, m) = 1}\chi^{-(a_1+a_2+a_3+a_4)}\left(y\right) e_m\left(\frac{m}{k}\beta(a_2+2a_3+3a_4)y\right)\Bigg|\\ &&\leq\left\{\begin{array}{ll} \phi(m)\phi(k)^{-1}, & {\rm{if}}\;\; m\mid (a_1+a_2+a_3+a_4) \;{\rm{and}}\; k\nmid (a_2+2a_3+3a_4), \\ 0, & {\rm{if}}\;\; m\nmid (a_1+a_2+a_3+a_4) \;{\rm{and}}\; k\mid (a_2+2a_3+3a_4), \\ \phi(m)\phi(k)^{-1}k^{\frac{1}{2}}, & {\rm{if}}\;\; m\nmid (a_1+a_2+a_3+a_4) \;{\rm{and}}\; k\nmid (a_2+2a_3+3a_4). \end{array} \right. \end{eqnarray*}$

Therefore

$\begin{eqnarray*} &&\sum\limits_{t = 0}^{km-1}\chi\left(t^{a_1}(t+m)^{a_2}(t+2m)^{a_3}(t+3m)^{a_4}\right) \\ && = \left\{\begin{array}{ll} k\phi(m), & {\rm{if}}\;\; m\mid (a_1+a_2+a_3+a_4) \;{\rm{and}}\; k\mid (a_2+2a_3+3a_4), \\ O\left(\phi(m)\phi(k)^{-1}k^{\frac{3}{2}}\right), & \hbox{otherwise}. \end{array} \right. \end{eqnarray*}$

Lemma 2.2. Let $m$ be an odd number and let $k$ be a positive integer with $k\leq m$ . Define

$\begin{eqnarray*} \Xi_{m, k}&: = &\mathop{\mathop{ \sum\limits_{1\leq|a_1|, |a_2|, |a_3|, |a_4|\leq\frac{m-1}{2}} }_{a_1+a_2+a_3+a_4\equiv 0\ (\bmod m)}}_{a_2+2a_3+3a_4\equiv 0\ (\bmod k)} \; \; \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-a_1l_1\right) \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(-a_2l_2\right)\nonumber\\ &&\times\sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right) \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right). \end{eqnarray*}$

Then we have

$\begin{eqnarray*} \Xi_{m, k} = \frac{1}{48}m^4+O\left(\frac{m^4(\log m)^3}{k}\right). \end{eqnarray*}$

Proof. Roughly speaking, by the upper bound for exponential sum

$\begin{eqnarray} \left|\sum\limits_{l = \frac{m+1}{2}}^{m-1}e_m(-al)\right|\leq\frac{m}{2|a|}, \qquad\hbox{where}\qquad 1\leq |a|\leq\frac{m-1}{2}, \end{eqnarray}$

(2.4)

we know that only the terms when $|a_1|, |a_2|, |a_3|, |a_4|$ all are small contribute significantly to the main term in $\Xi_{m, k}$ . Furthermore, for small enough $|a_1|, |a_2|, |a_3|, |a_4|$ the system of congruence equations

$\left\{\begin{array}{l} a_1+a_2+a_3+a_4\equiv 0\ (\bmod\ m), \\ a_2+2a_3+3a_4\equiv 0\ (\bmod\ k), \end{array} \right.$

is just a system of equations

$\left\{\begin{array}{l} a_1+a_2+a_3+a_4 = 0, \\ a_2+2a_3+3a_4 = 0. \end{array} \right.$

Specifically, for absolute constant $c > 0$ we get from (2.4) that

$\begin{eqnarray*} &&\sum\limits_{ck\leq|a_1|\leq\frac{m-1}{2}}\mathop{ \sum\limits_{1\leq|a_2|, |a_3|, |a_4|\leq\frac{m-1}{2}} }_{a_1+a_2+a_3+a_4\equiv 0\ (\bmod m)} \left|\sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-a_1l_1\right)\right| \cdot\left|\sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(-a_2l_2\right)\right|\nonumber\\ &&\qquad\times\left|\sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right)\right|\cdot \left|\sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right)\right| \nonumber\\ &&\ll\sum\limits_{1\leq|a_2|\leq\frac{m-1}{2}}\frac{m}{|a_2|} \sum\limits_{1\leq|a_3|\leq\frac{m-1}{2}}\frac{m}{|a_3|}\sum\limits_{1\leq|a_4|\leq\frac{m-1}{2}} \frac{m}{|a_4|}\mathop{\sum\limits_{ck\leq|a_1|\leq\frac{m-1}{2}}}_{a_1+a_2+a_3+a_4\equiv 0\ (\bmod m)} \frac{m}{k} \nonumber\\ &&\ll\frac{m^4(\log m)^3}{k}. \end{eqnarray*}$

By applying the above $\ll$ estimate directly to each of $a_1$ , $a_2$ , $a_3$ , $a_4$ sequentially we have

$\begin{eqnarray*} \Xi_{m, k}& = &\sum\limits_{1\leq|a_1|, |a_2|\leq\frac{5k}{32}}\mathop{\mathop{ \sum\limits_{1\leq|a_3|, |a_4|\leq\frac{k}{32}} }_{a_1+a_2+a_3+a_4\equiv 0\ (\bmod m)}}_{a_2+2a_3+3a_4\equiv 0\ (\bmod k)} \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-a_1l_1\right) \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(-a_2l_2\right)\nonumber\\ &&\times \sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right) \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right)+O\left(\frac{m^4(\log m)^3}{k}\right)\nonumber\\ & = &\sum\limits_{1\leq|a_1|, |a_2|\leq\frac{5k}{32}}\; \; \mathop{\mathop{ \sum\limits_{1\leq|a_3|, |a_4|\leq\frac{k}{32}} }_{a_1+a_2+a_3+a_4 = 0}}_{a_2+2a_3+3a_4 = 0}\; \; \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-a_1l_1\right) \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(-a_2l_2\right)\nonumber\\ &&\times \sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right) \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right)+O\left(\frac{m^4(\log m)^3}{k}\right)\nonumber\\ & = &\sum\limits_{1\leq|a_3|, |a_4|\leq\frac{k}{32}}\; \; \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-(a_3+2a_4)l_1\right) \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left((2a_3+3a_4)l_2\right)\nonumber\\ &&\times\sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right) \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right)+O\left(\frac{m^4(\log m)^3}{k}\right). \end{eqnarray*}$

It is not hard to show from (2.4) that

$\begin{eqnarray*} &&\sum\limits_{\frac{k}{32} < |a_3|\leq\frac{m-1}{2}}\; \; \sum\limits_{1\leq|a_4|\leq\frac{k}{32}}\; \; \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-(a_3+2a_4)l_1\right) \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left((2a_3+3a_4)l_2\right)\nonumber\\ &&\qquad\times\sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right) \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right) \nonumber\\ &&\ll\sum\limits_{\frac{k}{32} < |a_3|\leq\frac{m-1}{2}}\; \; \sum\limits_{1\leq|a_4|\leq\frac{k}{32}} m\cdot\left|\sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left((2a_3+3a_4)l_2\right)\right| \cdot\frac{m}{|a_3|}\cdot\frac{m}{|a_4|}\nonumber\\ &&\ll\frac{m^3}{k}\sum\limits_{1\leq|a_4|\leq\frac{k}{32}}\frac{1}{|a_4|} \sum\limits_{\frac{k}{32} < |a_3|\leq\frac{m-1}{2}} \left|\sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left((2a_3+3a_4)l_2\right)\right|\nonumber\\ &&\leq\frac{m^3}{k}\sum\limits_{1\leq|a_4|\leq\frac{k}{32}}\frac{1}{|a_4|} \sum\limits_{0\leq |a_3|\leq\frac{m-1}{2}} \left|\sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left((2a_3+3a_4)l_2\right)\right|\nonumber\\ && = \frac{m^3}{k}\sum\limits_{1\leq|a_4|\leq\frac{k}{32}}\frac{1}{|a_4|} \sum\limits_{0\leq |a_3|\leq\frac{m-1}{2}} \left|\sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(a_3l_2\right)\right|\nonumber\\ &&\ll\frac{m^3}{k}\cdot \log k\cdot m\log m\ll\frac{m^4(\log m)^2}{k}, \end{eqnarray*}$

where we used the trivial bound $\left|\sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-(a_3+2a_4)l_1\right)\right|\ll m$ . By applying the above $\ll$ estimate to each of $a_3$ , $a_4$ sequentially we have

$\begin{eqnarray} \Xi_{m, k}& = &\sum\limits_{1\leq|a_3|, |a_4|\leq\frac{m-1}{2}}\; \; \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-(a_3+2a_4)l_1\right) \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left((2a_3+3a_4)l_2\right)\\ &&\quad\times\sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right) \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right)+O\left(\frac{m^4(\log m)^3}{k}\right)\\ & = &\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1}\; \; \sum\limits_{1\leq|a_3|\leq\frac{m-1}{2}}e_m\left((-l_1+2l_2-l_3)a_3\right) \\ &&\quad\times\sum\limits_{1\leq|a_4|\leq\frac{m-1}{2}}e_m\left((-2l_1+3l_2-l_4)a_4\right) +O\left(\frac{m^4(\log m)^3}{k}\right) \\ & = &\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1}\; \; \sum\limits_{0\leq|a_3|\leq\frac{m-1}{2}}e_m\left((-l_1+2l_2-l_3)a_3\right) \\ &&\quad\times\sum\limits_{0\leq|a_4|\leq\frac{m-1}{2}}e_m\left((-2l_1+3l_2-l_4)a_4\right) \\ &&-\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1}\; \; \sum\limits_{0\leq|a_3|\leq\frac{m-1}{2}}e_m\left((-l_1+2l_2-l_3)a_3\right) \\ &&-\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1}\; \; \sum\limits_{0\leq|a_4|\leq\frac{m-1}{2}}e_m\left((-2l_1+3l_2-l_4)a_4\right) \\ &&+\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1}1 +O\left(\frac{m^4(\log m)^3}{k}\right) \\ & = &m^2\mathop{\mathop{ \sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1} }_{2l_2\equiv l_1+l_3 (\bmod m)}}_{3l_2\equiv 2l_1+l_4 (\bmod m)}1 -\frac{m(m-1)}{2}\mathop{ \sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3\leq m-1} }_{2l_2\equiv l_1+l_3 (\bmod m)}1 \\ &&-\frac{m(m-1)}{2}\mathop{ \sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_4\leq m-1} }_{3l_2\equiv 2l_1+l_4 (\bmod m)}1+\frac{(m-1)^4}{16}\\ &&+O\left(\frac{m^4(\log m)^3}{k}\right), \end{eqnarray}$

(2.5)

where we used (2.3) in the last equality.

Following the same arguments in Lemma 2.2 of ^[15] we have

$\begin{eqnarray} \mathop{\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3\leq m-1} }_{2l_2\equiv l_1+l_3 (\bmod m)}1& = &\mathop{\sum\limits_{1\leq u_1, u_2, u_3\leq\frac{m-1}{2}}}_{2(u_2+\frac{m-1}{2})\equiv u_1+\frac{m-1}{2}+u_3+\frac{m-1}{2} (\bmod m)}1 = \mathop{\sum\limits_{1\leq u_1, u_2, u_3\leq\frac{m-1}{2}}}_{2u_2\equiv u_1+u_3 (\bmod m)}1 \\ & = &\mathop{\sum\limits_{1\leq u_1, u_2, u_3\leq\frac{m-1}{2}}}_{2u_2 = u_1+u_3}1 = \mathop{\sum\limits_{1\leq u_1, u_3\leq\frac{m-1}{2}}}_{2\mid u_1+u_3}1 = \sum\limits_{1\leq u_1\leq \frac{m-1}{2}}\left(\frac{m}{4}+O(1)\right) \\ & = &\frac{m^2}{8}+O(m) \end{eqnarray}$

(2.6)

and

$\begin{eqnarray*} \mathop{\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_4\leq m-1} }_{3l_2\equiv 2l_1+l_4 (\bmod m)}1 & = &\mathop{\sum\limits_{1\leq u_1, u_2, u_4\leq\frac{m-1}{2}}}_{3(u_2+\frac{m-1}{2})\equiv 2(u_1+\frac{m-1}{2})+u_4+\frac{m-1}{2} (\bmod m)}1 = \mathop{\sum\limits_{1\leq u_1, u_2, u_4\leq\frac{m-1}{2}}}_{2u_1\equiv 3u_2-u_4 (\bmod m)}1 \nonumber \\ & = &\mathop{\mathop{\sum\limits_{1\leq u_1, u_2, u_4\leq\frac{m-1}{2}}}_{3-\frac{m-1}{2}\leq 3u_2-u_4\leq 0}}_{2u_1 = 3u_2-u_4+m}1 +\mathop{\mathop{\sum\limits_{1\leq u_1, u_2, u_4\leq\frac{m-1}{2}}}_{1\leq 3u_2-u_4\leq m}}_{2u_1 = 3u_2-u_4}1 +\mathop{\mathop{\sum\limits_{1\leq u_1, u_2, u_4\leq\frac{m-1}{2}}}_{m+1\leq 3u_2-u_4\leq \frac{3(m-1)}{2}-1}}_{2u_1 = 3u_2-u_4-m}1 \nonumber \\ & = &\mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{3-\frac{m-1}{2}\leq 3u_2-u_4\leq 0}}_{2\mid 3u_2-u_4+m}1 +\mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{1\leq 3u_2-u_4\leq m}}_{2\mid 3u_2-u_4}1 +\mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{m+1\leq 3u_2-u_4\leq \frac{3(m-1)}{2}-1}}_{2\mid 3u_2-u_4-m}1 \nonumber \\ & = &\mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{3u_2\leq u_4}}_{2\nmid 3u_2-u_4}1 +\mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{u_4+1\leq 3u_2\leq u_4+m}}_{2\mid 3u_2-u_4}1 +\mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{u_4+m+1\leq 3u_2\leq \frac{3(m-1)}{2}+u_4-1}}_{2\nmid 3u_2-u_4}1. \end{eqnarray*}$

By elementary calculations we get

$\begin{array} {l} \mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{3u_2\leq u_4}}_{2\nmid 3u_2-u_4}1 = \sum\limits_{1\leq u_4\leq \frac{m-1}{2}}\mathop{\sum\limits_{1\leq u_2\leq\frac{1}{3}u_4}} _{2\nmid 3u_2-u_4}1 = \sum\limits_{1\leq u_4\leq \frac{m-1}{2}}\left(\frac{1}{6}u_4+O(1)\right) = \frac{1}{48}m^2+O(m), \\ \mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{u_4+1\leq 3u_2\leq u_4+m}}_{2\mid 3u_2-u_4}1 = \\\sum\limits_{1\leq u_4\leq\frac{m-1}{2}}\mathop{\sum\limits_{\frac{u_4+1}{3}\leq u_2\leq\frac{u_4+m}{3}}}_{2\mid 3u_2-u_4}1 = \sum\limits_{1\leq u_4\leq\frac{m-1}{2}}\left(\frac{m}{6}+O(1)\right) = \frac{1}{12}m^2+O(m), \\ \mathop{\mathop{\sum\limits_{1\leq u_2, u_4\leq\frac{m-1}{2}}}_{u_4+m+1\leq 3u_2\leq \frac{3(m-1)}{2}+u_4-1}}_{2\nmid 3u_2-u_4}1 = \sum\limits_{1\leq u_4\leq\frac{m-1}{2}}\mathop{\sum\limits_{\frac{u_4+m+1}{3}\leq u_2\leq\frac{m-1}{2}}}_{2\nmid 3u_2-u_4}1 = \\ \sum\limits_{1\leq u_4\leq\frac{m-1}{2}}\left(\frac{m}{12}-\frac{u_4}{6}+O(1)\right) = \frac{1}{48}m^2+O(m). \end{array}$

Hence,

$\begin{eqnarray} \mathop{\sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_4\leq m-1} }_{3l_2\equiv 2l_1+l_4 (\bmod m)}1 = \frac{1}{48}m^2+\frac{1}{12}m^2+\frac{1}{48}m^2+O(m) = \frac{1}{8}m^2+O(m). \end{eqnarray}$

(2.7)

Furthermore, we have

$\begin{eqnarray*} \mathop{\mathop{ \sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1} }_{2l_2\equiv l_1+l_3 (\bmod m)}}_{3l_2\equiv 2l_1+l_4 (\bmod m)}1 & = &\mathop{\mathop{\sum\limits_{1\leq u_1, u_2, u_3, u_4\leq\frac{m-1}{2}}}_{2(u_2+\frac{m-1}{2})\equiv u_1+\frac{m-1}{2}+u_3+\frac{m-1}{2} (\bmod m)} }_{3(u_2+\frac{m-1}{2})\equiv 2(u_1+\frac{m-1}{2})+u_4+\frac{m-1}{2} (\bmod m)}1 = \mathop{\mathop{\sum\limits_{1\leq u_1, u_2, u_3, u_4\leq\frac{m-1}{2}}}_{2u_2\equiv u_1+u_3 (\bmod m)}}_{3u_2\equiv 2u_1+u_4 (\bmod m)}1 \nonumber \\ & = &\mathop{\mathop{\sum\limits_{1\leq u_1, u_2, u_3, u_4\leq\frac{m-1}{2}}}_{2u_2 = u_1+u_3}} _{6u_2\equiv 4u_1+2u_4 (\bmod m)}1 = \mathop{\mathop{\sum\limits_{1\leq u_1, u_3, u_4\leq\frac{m-1}{2}}}_{2\mid u_1+u_3}} _{3u_3-u_1\equiv 2u_4 (\bmod m)}1. \end{eqnarray*}$

For $1\leq u_1, u_3, u_4\leq \frac{m-1}{2}$ with $2\mid u_1+u_3$ , we know that

$\begin{eqnarray*} &&-\frac{m-1}{2}+3\leq 3u_3-u_1\leq\frac{3(m-1)}{2}-1, \quad 2\mid 3u_3-u_1, \\ && 1\leq 2u_4\leq m-1, \quad 2\mid 2u_4. \end{eqnarray*}$

Then $3u_3-u_1\equiv 2u_4\ (\bmod\ m) \Longleftrightarrow 3u_3-u_1 = 2u_4$ . Hence,

$\begin{eqnarray} \mathop{\mathop{ \sum\limits_{\frac{m+1}{2}\leq l_1, l_2, l_3, l_4\leq m-1} }_{2l_2\equiv l_1+l_3 (\bmod m)}}_{3l_2\equiv 2l_1+l_4 (\bmod m)}1 & = &\mathop{\mathop{\sum\limits_{1\leq u_1, u_3, u_4\leq\frac{m-1}{2}}}_{2\mid u_1+u_3}} _{3u_3-u_1 = 2u_4}1 = \mathop{\mathop{\sum\limits_{1\leq u_1, u_3\leq\frac{m-1}{2}}}_{2\mid u_1+u_3}} _{1\leq 3u_3-u_1\leq m-1}1 = \mathop{\mathop{\sum\limits_{1\leq u_1, u_3\leq\frac{m-1}{2}}}_{2\mid u_1+u_3}} _{u_1+1\leq 3u_3\leq u_1+m-1}1 \\ & = &\sum\limits_{1\leq u_1\leq\frac{m-1}{2}}\mathop{\sum\limits_{\frac{u_1+1}{3}\leq u_3\leq\frac{u_1+m-1}{3}}}_{2\mid u_1+u_3}1 = \sum\limits_{1\leq u_1\leq\frac{m-1}{2}}\left(\frac{m}{6}+O(1)\right) \\ & = &\frac{1}{12}m^2+O(m). \end{eqnarray}$

(2.8)

Combining (2.5)–(2.8) we immediately get

$\begin{eqnarray*} \Xi_{m, k}& = &m^2\left(\frac{m^2}{12}+O(m)\right) -2\cdot\frac{m(m-1)}{2}\left(\frac{m^2}{8}+O(m)\right)+\frac{(m-1)^4}{16} \\ &&+O\left(\frac{m^4(\log m)^3}{k}\right)\\ & = &\frac{1}{48}m^4+O\left(\frac{m^4(\log m)^3}{k}\right). \end{eqnarray*}$

This completes the proof of Lemma 2.2.

3. Correlation measures of order $4$

Now we prove Theorem 1.1. By the orthogonality relations of additive character sums we get

$s_t = \frac{1}{m}\sum\limits_{|a|\leq\frac{m-1}{2}}\sum\limits_{l = \frac{m+1}{2}}^{m-1}e_m\left(a(Q_{m}(t)-l)\right).$

Hence,

$(-1)^{s_t} = 1-2s_t = -\frac{2}{m}\sum\limits_{1\leq|a|\leq\frac{m-1}{2}} \sum\limits_{l = \frac{m+1}{2}}^{m-1}e_m\left(-al\right)e_m\left(aQ_{m}(t)\right)+\frac{1}{m}.$

Define

$\chi_{km}(n) = \left\{ \begin{array}{ll} e_m\left(Q_m(n)\right), & {\rm{if}}\;\; \gcd(n, m) = 1, \\ 0, & {\rm{if}}\;\; \gcd(n, m) > 1. \end{array} \right.$

Following from the assumption that $Q_m(n)$ is $km$ -periodic we get $\chi_{km}(n+km) = \chi_{km}(n)$ , and by (1.1) we have

$\chi_{km}(n_1n_2) = \chi_{km}(n_1)\chi_{km}(n_2).$

Then $\chi_{km}(n)$ is a Dirichlet character modulo $km$ such that $\chi_{km}^m$ is trivial and $\chi_{km}^{m'}$ is not trivial for all $1\leq m' < m$ . Therefore

$\begin{eqnarray} (-1)^{s_t} = -\frac{2}{m}\sum\limits_{1\leq|a|\leq\frac{m-1}{2}} \sum\limits_{l = \frac{m+1}{2}}^{m-1}e_m\left(-al\right)\chi_{km}\left(t^a\right) +\frac{1}{m}. \end{eqnarray}$

(3.1)

By (2.4) we get

$\begin{eqnarray} &&\left|-\frac{2}{m}\sum\limits_{1\leq|a|\leq\frac{m-1}{2}} \sum\limits_{l = \frac{m+1}{2}}^{m-1}e_m\left(-al\right)\chi_{km}\left(t^a\right)\right| \leq\frac{2}{m}\sum\limits_{1\leq|a|\leq\frac{m-1}{2}} \left|\sum\limits_{l = \frac{m+1}{2}}^{m-1}e_m\left(-al\right)\right| \\ &&\leq\frac{2}{m}\sum\limits_{1\leq|a|\leq\frac{m-1}{2}}\frac{m}{2|a|}\ll \log m. \end{eqnarray}$

(3.2)

Then from (3.1) and (3.2) we have

$\begin{eqnarray} &&\sum\limits_{t = 0}^{km-1}(-1)^{s_t+s_{t+m}+s_{t+2m}+s_{t+3m}} = \mathop{\sum\limits_{t = 0}^{km-1}}_{\gcd(t, m) = 1}(-1)^{s_t+s_{t+m}+s_{t+2m}+s_{t+3m}} +\mathop{\sum\limits_{t = 0}^{km-1}}_{\gcd(t, m) > 1}1 \\ && = \mathop{\sum\limits_{t = 0}^{km-1}}_{\gcd(t, m) = 1} \Bigg(-\frac{2}{m}\sum\limits_{1\leq|a_1|\leq\frac{m-1}{2}} \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-a_1l_1\right)\chi_{km}\left(t^{a_1}\right) +\frac{1}{m}\Bigg)\\ &&\qquad\times\Bigg(-\frac{2}{m}\sum\limits_{1\leq|a_2|\leq\frac{m-1}{2}} \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(-a_2l_2\right)\chi_{km}\left((t+m)^{a_2}\right) +\frac{1}{m}\Bigg)\\ &&\qquad\times\Bigg(-\frac{2}{m}\sum\limits_{1\leq|a_3|\leq\frac{m-1}{2}} \sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right)\chi_{km}\left((t+2m)^{a_3}\right) +\frac{1}{m}\Bigg)\\ &&\qquad\times\Bigg(-\frac{2}{m}\sum\limits_{1\leq|a_4|\leq\frac{m-1}{2}} \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right)\chi_{km}\left((t+3m)^{a_4}\right) +\frac{1}{m}\Bigg)+\mathop{\sum\limits_{t = 0}^{km-1}}_{\gcd(t, m) > 1}1 \\ && = \frac{2^4}{m^4}\sum\limits_{1\leq|a_1|\leq\frac{m-1}{2}}\; \; \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-a_1l_1\right) \sum\limits_{1\leq|a_2|\leq\frac{m-1}{2}}\; \; \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(-a_2l_2\right) \\ &&\qquad\times\sum\limits_{1\leq|a_3|\leq\frac{m-1}{2}}\; \; \sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right)\sum\limits_{1\leq|a_4|\leq\frac{m-1}{2}}\; \; \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right) \\ &&\qquad\times \sum\limits_{t = 0}^{km-1}\chi_{km}\left(t^{a_1}(t+m)^{a_2}(t+2m)^{a_3}(t+3m)^{a_4}\right) \\ &&\qquad+\mathop{\sum\limits_{t = 0}^{km-1}}_{\gcd(t, m) > 1}1+O\left(k(\log m)^3\right). \end{eqnarray}$

(3.3)

Combining (2.4), (3.3), Lemmas 2.1 and 2.2 we get

$\begin{eqnarray*} &&\sum\limits_{t = 0}^{km-1}(-1)^{s_t+s_{t+m}+s_{t+2m}+s_{t+3m}}\\ && = \frac{2^4k\phi(m)}{m^4}\mathop{\mathop{ \sum\limits_{1\leq|a_1|, |a_2|, |a_3|, |a_4|\leq\frac{m-1}{2}} }_{a_1+a_2+a_3+a_4\equiv 0\ (\bmod m)}}_{a_2+2a_3+3a_4\equiv 0\ (\bmod k)}\; \; \sum\limits_{l_1 = \frac{m+1}{2}}^{m-1}e_m\left(-a_1l_1\right) \sum\limits_{l_2 = \frac{m+1}{2}}^{m-1}e_m\left(-a_2l_2\right)\nonumber\\ &&\qquad\times \sum\limits_{l_3 = \frac{m+1}{2}}^{m-1}e_m\left(-a_3l_3\right) \sum\limits_{l_4 = \frac{m+1}{2}}^{m-1}e_m\left(-a_4l_4\right) \nonumber\\ &&\qquad+O\Bigg(\frac{1}{m^4}\Bigg(\sum\limits_{1\leq|a|\leq\frac{m-1}{2}} \Bigg|\sum\limits_{l = \frac{m+1}{2}}^{m-1}e_m\left(-al\right)\Bigg|\Bigg)^4 \phi(m)\phi(k)^{-1}k^{\frac{3}{2}}\Bigg) \\ &&\qquad+\mathop{\sum\limits_{t = 0}^{km-1}}_{\gcd(t, m) > 1}1+O\left(k(\log m)^3\right)\\ && = km-\frac{2}{3}k\phi(m)+O\left(k^{\frac{1}{2}}m(\log m)^4\right). \end{eqnarray*}$

Then there exists absolute constant $\delta > 0$ such that

$\begin{eqnarray*} \sum\limits_{t = 0}^{km-1}(-1)^{s_t+s_{t+m}+s_{t+2m}+s_{t+3m}} \geq \frac{1}{3}km-\delta k^{\frac{1}{2}}m(\log m)^4. \end{eqnarray*}$

This proves the result.

4. Final remarks

In this work, we have claimed that two families of binary sequences (see (1.3) and (1.4)) studied in the past several years have 'large' values on the correlation measures of order $4$ . They would be very vulnerable if used in cryptography.

It seems interesting to consider the case when the full peaks on the periodic correlation measure of these sequences appear, i.e., their periodic correlation measure of order $\ell$ equals to the period, see ^[9]. Such problem may be related to their linear complexity.

Acknowledgments

H. Liu was partially supported by National Natural Science Foundation of China under Grant No. 12071368, and the Science and Technology Program of Shaanxi Province of China under Grant No. 2019JM-573 and 2020JM-026.

Z. Chen and C. Wu were partially supported by the Provincial Natural Science Foundation of Fujian under grant No. 2020J01905, by the Science and Technology Project of Putian City under grant No. 2021R4001-10, and by the Putian Univ. under grant No. PTU-P-61772292.

Conflict of interest

The authors declared that they have no conflicts of interest to this work.

References

[1]	T. Agoh, K. Dilcher, L. Skula, Fermat quotients for composite moduli, J. Number Theory, 66 (1997), 29–50. https://doi.org/10.1006/jnth.1997.2162 doi: 10.1006/jnth.1997.2162
[2]	H. Aly, A. Winterhof, Boolean functions derived from Fermat quotients, Cryptogr. Commun., 3 (2011), 165–174. https://doi.org/10.1007/s12095-011-0043-5 doi: 10.1007/s12095-011-0043-5
[3]	T. Apostol, Introduction to analytic number theory, New York: Springer, 1976. https://doi.org/10.1007/978-1-4757-5579-4
[4]	J. Cassaigne, C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences vii: the measures of pseudorandomness, Acta Arith., 103 (2002), 97–118. https://doi.org/10.4064/aa103-2-1 doi: 10.4064/aa103-2-1
[5]	M. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23–38. https://doi.org/10.4064/aa152-1-3 doi: 10.4064/aa152-1-3
[6]	Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 1–10. https://doi.org/10.1007/s11432-014-5092-x doi: 10.1007/s11432-014-5092-x
[7]	Z. Chen, X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317–323. https://doi.org/10.1007/s10623-012-9608-3 doi: 10.1007/s10623-012-9608-3
[8]	Z. Chen, X. Du, R. Marzouk, Trace representation of pseudorandom binary sequences derived from Euler quotients, Appl. Algebra Eng. Commun. Comput., 26 (2015), 555–570. https://doi.org/10.1007/s00200-015-0265-4 doi: 10.1007/s00200-015-0265-4
[9]	Z. Chen, A. Gómez, D. Gómez-Pérez, A. Tirkel, Correlation measure, linear complexity and maximum order complexity for families of binary sequences, Finite Fields Th. Appl., 78 (2022), 101977. https://doi.org/10.1016/j.ffa.2021.101977 doi: 10.1016/j.ffa.2021.101977
[10]	Z. Chen, L. Hu, X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105–108. https://doi.org/10.1007/s11277-010-0104-7 doi: 10.1007/s11277-010-0104-7
[11]	Z. Chen, A. Ostafe, A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In: Lecture notes in computer science, Berlin: Springer, 2010, 73–85. https://doi.org/10.1007/978-3-642-13797-6_6
[12]	Z. Chen, A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discrete Math., 28 (2014), 1–7. https://doi.org/10.1137/130907951 doi: 10.1137/130907951
[13]	X. Du, Z. Chen, L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Inform. Process. Lett., 112 (2012), 604–609. https://doi.org/10.1016/j.ipl.2012.04.011 doi: 10.1016/j.ipl.2012.04.011
[14]	D. Gómez-Pérez, 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
[15]	H. Liu, X. Liu, On the correlation measures of orders $3$ and $4$ of binary sequence of period $p^2$ derived from Fermat quotients, Adv. Math. Commun., in press. https://doi.org/10.3934/amc.2021008
[16]	C. Mauduit, A. Sárközy, On finite pseudorandom binary sequencs I: measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365–377. https://doi.org/10.4064/aa-82-4-365-377 doi: 10.4064/aa-82-4-365-377
[17]	A. Ostafe, I. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discrete Math., 25 (2011), 50–71. https://doi.org/10.1137/100798466 doi: 10.1137/100798466
[18]	C. D. Pan, C. B. Pan, Goldbach conjecture (Chinese), Beijing: Science Press, 2011.
[19]	I. Shparlinski, Fermat quotients: exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228–1238. https://doi.org/10.1112/blms/bdr058 doi: 10.1112/blms/bdr058
[20]	I. Shparlinski, Character sums with Fermat quotients, Q. J. Math., 62 (2011), 1031–1043. https://doi.org/10.1093/qmath/haq028 doi: 10.1093/qmath/haq028
[21]	I. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456–462. https://doi.org/10.1017/S000497271000198X doi: 10.1017/S000497271000198X
[22]	J. Zhang, S. Gao, C. Zhao, Linear complexity of a family of binary $pq^2$ -periodic sequences from Euler quotients, IEEE Trans. Inf. Theory, 66 (2020), 5774–5780. https://doi.org/10.1109/TIT.2020.2979838 doi: 10.1109/TIT.2020.2979838
[23]	J. Zhang, C. Hu, X. Fan, C. Zhao, Trace representation of the binary $pq^2$ -periodic sequences derived from Euler quotients, Cryptogr. Commun., 13 (2021), 343–359. https://doi.org/10.1007/s12095-021-00475-1 doi: 10.1007/s12095-021-00475-1

Reader Comments

Your name:*

Email:*
© 2022 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)

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

AIMS Mathematics

1.8 3.4

Metrics

Article views(1551) PDF downloads(57) Cited by(0)

Preview PDF

Download XML

Export Citation

Article outline

Show full outline

AIMS Mathematics

Correlation measures of binary sequences derived from Euler quotients

Related Papers:

Abstract

1. Introduction

2. Dirichlet characters and Gauss sums

3. Correlation measures of order $4$

4. Final remarks

Acknowledgments

Conflict of interest

References

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Other Articles By Authors

Catalog

Abstract

1. Introduction

2. Dirichlet characters and Gauss sums

3. Correlation measures of order $4$

4. Final remarks

Acknowledgments

Conflict of interest

References

AIMS Mathematics

Correlation measures of binary sequences derived from Euler quotients

Related Papers:

Abstract

1. Introduction

2. Dirichlet characters and Gauss sums

3. Correlation measures of order 4 4

4. Final remarks

Acknowledgments

Conflict of interest

References

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Other Articles By Authors

Related pages

Tools

Export File

Citation

Format

Content

Catalog

Abstract

1. Introduction

2. Dirichlet characters and Gauss sums

3. Correlation measures of order 4 4

4. Final remarks

Acknowledgments

Conflict of interest

References

3. Correlation measures of order $4$

3. Correlation measures of order $4$