# First moment of Hecke eigenvalues at the integers represented by binary
quadratic forms

Manish Kumar Pandey and Lalit Vaishya  (Manish Kumar Pandey ) Department of
Mathematics, UPES, Dehradun-248007, Uttarakhand, India
<EMAIL_ADDRESS><EMAIL_ADDRESS>( Lalit Vaishya) School
of Mathematics, The Institute of Mathematical Sciences, A CI of Homi Bhabha
National Institute, CIT Campus, Taramani, Chennai 600 113, India,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In the article, we consider a question concerning the estimation of summatory
function of the Fourier coefficients of Hecke eigenforms indexed by a sparse
set of integers. In particular, we provide an estimate for the following sum;

$\begin{split}S(f,\mathcal{Q};X)&:=\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n),\end{split}$

where $\flat$ means that sum runs over the square-free positive integers,
$\lambda_{f}(n)$ denotes the normalised $n^{\rm th}$ Fourier coefficients of a
Hecke eigenform $f$ of integral weight $k$ for the congruence subgroup
$\Gamma_{0}(N)$ and $\mathcal{Q}$ is a primitive integral positive-definite
binary quadratic forms of fixed discriminant $D<0$ with the class number
$h(D)=1$. As a consequence, we determine the size, in terms of conductor of
associated $L$-function, for the first sign change of Hecke eigenvalues
indexed by the integers which are represented by $\mathcal{Q}$. This work is
an improvement and generalisation of the previous results.

###### Key words and phrases:

Hecke eigenvalues, Fourier coefficients of cusp form, Rankin-Selberg $L$
function, Symmetric power $L$ functions, Asymptotic behaviour, Binary
quadratic form

###### 2010 Mathematics Subject Classification:

Primary 11F30, 11F11, 11M06; Secondary 11N37

##  1\. Introduction and statements of the results

Let $M_{k}(\Gamma_{0}(N),\chi)$ and $S_{k}(\Gamma_{0}(N),\chi)$ denote the
${\mathbb{C}}$\- vector space of modular forms and cusp forms respectively of
integral weight $k$ for the congruence subgroup $\Gamma_{0}(N)$ with
nebentypus $\chi$. Moreover, if the nebentypus is trivial, we denote the space
of modular forms and cusp forms by $M_{k}(\Gamma_{0}(N))$ and
$S_{k}(\Gamma_{0}(N))$, respectively. A cusp form $f\in S_{k}(\Gamma_{0}(N))$
is said to be a Hecke eigenform (newform) if $f$ is a common eigenform for all
the Hecke operators and the Atkin-Lehner $W$-operators. The space of Hecke
eigenforms (newforms) is denoted by $S^{new}_{k}(\Gamma_{0}(N))$. The Fourier
coefficients of a Hecke eigenform satisfy the famous Ramanujan-Petersson bound
which follows from the work of Deligne [5]. With these notations, let $f\in
S_{k}(\Gamma_{0}(N))$ be a Hecke eigenform with the Fourier series expansion
at the cusp $\infty$ given by:

(1) $f(\tau)=\sum_{n=1}^{\infty}\lambda_{f}(n)n^{\frac{k-1}{2}}q^{n},$

where $q:=e^{2\pi i\tau}$ and $\tau\in\mathbb{H}$. $f$ is said to be
normalised if $\lambda_{f}(1)=1$. The Fourier coefficients $\lambda_{f}(n)$
are known as the normalised $n^{th}$-Fourier coefficients of $f$. The
normalised Fourier coefficient $\lambda_{f}(n)$ is a multiplicative function
and satisfies the Hecke relation [8, Eq. (6.83)]:

(2)
$\lambda_{f}(m)\lambda_{f}(n)=\sum_{d|\gcd(m,n)}\lambda_{f}\left(\frac{mn}{d^{2}}\right),$

for all positive integers $m$ and $n$ coprime to $N$. From Deligne’s estimate
of Fourier coefficients of cusp forms, we have

(3) $|\lambda_{f}(n)|\leq\tau(n)\ll_{\epsilon}n^{\epsilon},$

for any arbitrary small $\epsilon>0,$ where $\tau(n)$ denotes the number of
positive divisors of $n$.

The arithmetic behaviour and distribution of values of arithmetical functions
is the center of attraction in analytic number theory. The randomness in the
behaviour of these arithmetical functions leads to many interesting results.
In this context, the arithmetical function $n\mapsto\lambda_{f}(n)$ (where
$\lambda_{f}(n)$ is the $n^{\rm th}$ Fourier coefficients of a Hecke eigenform
$f$) is one of the interesting host. The problems become more fascinating and
harder if one considers the arithmetic behaviour and distribution over the
sparse set of positive integers. Iwaniec and Kowalski [9] studied the
distribution of $\\{\lambda_{f}(p):p-{\rm prime}\\}$ and proved that there
exist a positive constant $c$ such that

$\displaystyle{\sum_{p\leq X}}\lambda_{f}(p)\ll_{f}X\exp\left(-c\sqrt{\log
X}\right),$

which is an analogue of the prime number theorem for Hecke eigenforms. In this
regard, a most popularly known problem is studied by Blomer [2], where he
considers the distribution of the sequence
$\\{\lambda_{f}(q(n)):n\in\mathbb{N}\\},$ where $q(x)$ is a monic quadratic
polynomial. More precisely, he proves that

$\displaystyle{\sum_{n\leq X}}\lambda_{f}(q(n))\ll X^{\frac{6}{7}+\epsilon},$

for any $\epsilon>0.$ For a polynomial with more than one variable, the
problem has been studied broadly for many arithmetic functions such as Von
Mangoldt function ($n\mapsto\Lambda(n)$) and generalised divisor functions
($n\mapsto\tau_{k}(n)$) etc. In his remarkable work, Acharya [1] has studied a
two variable analog of the sum studied in the work of Blomer [2], where he
studied the distribution of $\\{\lambda_{f}(q(a,b))\\}$ where
$q(x,y)=x^{2}+y^{2}$ and obtained an estimate for the summatory function
$\displaystyle{\sum_{k,l\in\mathbb{Z}\atop k^{2}+l^{2}\leq
X}}\lambda_{f}(q(k,l)).$ For details, we refer to [1].

In this article, our motivation is to generalize the result of Acharya [1] by
studying the distribution of $\\{\lambda_{f}(\mathcal{Q}(\underline{x}))\\}$
where $\mathcal{Q}$ is a primitive integral positive-definite binary quadratic
forms of fixed discriminant $D<0$ with the class number $h(D)=1.$ In previous
works, the second author study the higher power moment
$\displaystyle{\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
X\atop\gcd(n,N)=1}}\lambda_{f}^{j}(n)$ for $j\leq 8$ in [19, 20], and
estimates for more general higher power moment has been carried in [16].
Before stating our result, we fix some notations.

Throughout the paper, Let $\mathcal{Q}(\underline{x})$ be a primitive integral
positive-definite binary quadratic (reduced) form given by;
$\mathcal{Q}(\underline{x})=ax_{1}^{2}+bx_{1}x_{2}+cx_{2}^{2},$ where
$\underline{x}=(x_{1},x_{2})\in\mathbb{Z}^{2}$, $a,b,c\in\mathbb{Z}$ with
$\gcd(a,b,c)=1$ and fixed discriminant $D=b^{2}-4ac<0$. Further, we assume
that for such discriminant $D$, the class number $h(D)$ is $1$. For details,
we refer to [4, chapter 2].

We consider the following sum for an upper-bound estimate:

(4)
$\begin{split}S(f,\mathcal{Q};X)&:=\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n),\end{split}$

where $\lambda_{f}(n)$ denotes the $n^{\rm th}$ Fourier coefficient of a Hecke
eigenform $f$ and symbol $\flat$ means that the sum runs over all square-free
integers. We also produce the explicit dependency in terms of weight $k$ and
level $N$ of the Hecke eigenform $f$, and discriminant $D$ of $\mathcal{Q}.$
More precisely, we obtain the following estimate.

######  Theorem 1.1.

Let $f\in S_{k}(\Gamma_{0}(N))$ be a normalised Hecke eigenform and
$\mathcal{Q}$ be a reduced form of discriminant $D$ with the class number
$h(D)=1$. For sufficiently large $X>0$ and any arbitrary small $\epsilon>0,$
we have

$\begin{split}S(f,\mathcal{Q};X)&=\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n)\ll_{\epsilon}{(Nk^{2}|D|)}^{\frac{1}{2}+\epsilon}X^{\frac{1}{2}+\epsilon}.\\\
\end{split}$

where the implied constant is absolute.

######  Remark 1.1.

If the class number $h(D)>1$, the same estimate (obtained in Theorem 1.1)
holds for the sum

(5)
$\begin{split}S(f,D;X)&:=\sideset{}{{}^{\flat}}{\sum}_{\begin{subarray}{c}n=\mathcal{Q}(\underline{x})\leq
X\\\ ~{}\mathcal{Q}\in\mathcal{S}_{D},\underline{x}\in\mathbb{Z}^{2}\\\
\gcd(n,N)=1\end{subarray}}\lambda_{f}(n),\end{split}$

where $\mathcal{S}_{D}$ denotes the set of in-equivalent primitive integral
positive-definite binary quadratic (reduced) forms of fixed discriminant with
the class number $h(D)=\\#\mathcal{S}_{D}$.

A consequence of the above theorem is a result on the sign change of the
Fourier coefficients. Below, we give a brief description of the sign change
problem and state our second result. It is well-known that if the Fourier
coefficients of a cusp form are real, it changes its sign infinitely often.
The sequence of Fourier coefficients of Hecke eigenform always has a sign
change in the interval of length $X,$ for sufficiently large $X.$ The problem
of getting first ever sign change of $\lambda_{f}(n),$ is quite hard. As
mentioned in [10], it is a $GL_{2}$-analogue of the $GL_{1}$ problem which
concerns about finding least quadratic non-residue. The problem is quite hard
in the sense that $\lambda_{f}(n)$ may take infinitely many values and it can
be very small. We also determine the first sign change of the real sequence of
Hecke eigenvalues over the integers which are represented by some function
$\mathcal{U}$. In particular, if $\mathcal{U}$ is an identity function on
$\mathbb{N}$ or characteristic function on the set of primes, the problem of
first sign changes and counting the number of sign changes in short interval
$[X,X+h],$ for sufficiently large $X$ and some $h<X,$ has been considered by
many authors. Let $\mathcal{I}$ denote the identity function on $\mathbb{N}$
and $n_{f,\mathcal{I}}$ denotes the first sign change of Fourier coefficients
$\lambda_{f}(n)$ of Hecke eignforms $f\in S_{k}(\Gamma_{0}(N)),$ i.e., the
least integer among all $n\in\mathbb{N}$ such that $\lambda_{f}(n)<0$ and
$\gcd(n,N)=1$. The problem of bounding $n_{f,\mathcal{I}}$ in terms of
analytic conductor has attracted many mathematicians. Kohnen and Sengupta [10]
have proved that the bound of $n_{f,\mathcal{I}}$ is given by

$n_{f,\mathcal{I}}\ll kN(\log
k)^{A}\exp\left(c_{2}\sqrt{\frac{\log(N+1)}{\log\log(N+2)}}\right),$

for some constant $A,c_{2}>0$, using analytic properties of automorphic
$L$-functions. Jointly with Iwaniec [7], they improved the bound for
$n_{f,\mathcal{I}}$ and obtained that $n_{f,\mathcal{I}}\ll Q^{29/60},$ where
$Q$ is the analytic conductor, of the $L$-function associated to $f$, given
explicitly in terms of weight and level of the form $f.$ Kowalski et al [11]
has made an important observation that the Hecke relation (2) allows one to
replace $\lambda_{f}(n)$ by a step function when one wants to find the lower
bound of partial sum of $\lambda_{f}(n).$ This allowed to improve the
exponent, i.e., $n_{f,\mathcal{I}}\ll Q^{9/20}.$ In the article [11], they
mentioned that the exponent $9/20$ is not the limit of the method. This was
further improved by Matom$\ddot{\rm a}$ki [14] to $3/8$ by deep analysis of
summatory function of $\lambda_{f}(n)$ over square-free integers and this is
best known bound for $n_{f,\mathcal{I}}$. The current known bound for
$n_{f,\mathcal{I}}$ is still far from the truth as it is known that
$n_{f,\mathcal{I}}\ll(\log kN)^{2}$ under generalised Riemann hypothesis. The
problem of getting the first-ever sign change becomes interesting if the
sequence of integers is indexed by some function other than the identity
function on $\mathbb{N}$. In particular, a result of this sort has been
obtained by the first author in joint work with P. Tiwari [15], where the
sequence of integers is written as a sum of squares, i.e. by considering the
function $Q:\mathbb{Z}^{2}\rightarrow\mathbb{N}$ given by
$Q({x,y})=x^{2}+y^{2}.$ Following the argument of Kohnen and Sengupta [10],
Pandey and Tiwari [15] have proved that

$n_{f,Q}\leq
k^{8}N^{4}\log^{64}(kN)~{}\max\left(\\!\\!N^{4}\exp\left(\\!\\!c{\frac{\log(N+1)}{\log\log(N+2)}}\right)(\log\log(N+2))^{4}\psi^{4}_{k}(N),\log^{120}(kN)\\!\\!\right),$

where $\psi_{k}(N)=\displaystyle{\prod_{p\mid N}\frac{\log(kN)}{\log p}}.$

The method of the first author [15] can be generalised to any primitive
integral positive-definite binary quadratic forms of fixed discriminant with
the class number $1.$ In this work adopting the method of Kowalski et al. and
Matomaki, we improve the previous result of the first author [15] and
generalise the result to any primitive integral positive-definite binary
quadratic form of fixed discriminant with the class number $1$.

Now, we state our second result concerning the first-ever sign change of Hecke
eigenvalues of a normalised Hecke eigenform at the integers represented by
$\mathcal{Q}(\underline{x})$. Let $n_{f,\mathcal{Q}}$ be the least integer
among all $n\in\mathbb{N}$ such that $\lambda_{f}(n)<0,$ with $\gcd(n,N)=1$
and $n$ is represented by $\mathcal{Q}(\underline{x})$. With these notations,
we observe that $n_{f,\mathcal{I}}\neq n_{f,\mathcal{Q}}$ as it is not
necessary that $n_{f,\mathcal{I}}$ can always be represented by
$\mathcal{Q}(\underline{x})$. Moreover, we observe that $n_{f,\mathcal{I}}\leq
n_{f,\mathcal{Q}}.$ Hence, an upper bound estimate for $n_{f,\mathcal{Q}}$
will also work for $n_{f,\mathcal{I}}$. An estimate for $n_{f,\mathcal{Q}}$ is
given by the following result.

######  Theorem 1.2.

Let $k\geq 2$ be an integer and $N$ be a square-free positive integer. Let
$f\in S_{k}(\Gamma_{0}(N))$ be a Hecke eigenform and $\mathcal{Q}$ be a
primitive integral positive-definite binary quadratic form of fixed
discriminant $D$ with the class number $1.$. Then, for any arbitrarily small
$\epsilon>0$,

$n_{f,\mathcal{Q}}\ll_{\epsilon}(Nk^{2}|D|^{2})^{\frac{3}{4}+\epsilon}$

where the implied constant is absolute.

######  Remark 1.2.

For the primitive integral positive-definite binary quadratic form of the
following fundamental discriminants $D=-3,-4,-8,-7,-11,-19,-43,-67,-163$ and
non-fundamental discriminants $D=-12,-16,-27,-28,$ the class number $h(D)=1$.
The list of reduced forms corresponding to these discriminants is given in [3,
Page 19- 20]. Theorem 1.2 holds only for primitive integral positive-definite
binary quadratic form of such discriminants.

######  Remark 1.3.

If the class number $h(D)>1$ for the discriminant $D<0$, then there are $h(D)$
many reduced forms corresponding to discriminants $D$. Moreover, let $n_{f,D}$
be the least integer among all $n\in\mathbb{N}$ such that $\lambda_{f}(n)<0,$
with $\gcd(n,N)=1$ and $n$ is represented by some of them from $h(D)$ many
reduced forms corresponding to discriminants $D$. Then,

(6)
$\begin{split}n_{f,D}\ll_{\epsilon}(Nk^{2}|D|^{2})^{\frac{3}{4}+\epsilon}h(D)^{-3/2}.\end{split}$

Acknowledgement : We would like to thank Prof. B. Ramakrishnan for encouraging
us to work on this problem and for his guidance and suggestions while
preparing the manuscript. We also thank R. Acharya for his helpful
suggestions. The second author would like to thank IMSc, Chennai for its
hospitality and financial support through an institute fellowship.

##  2\. Key Ingredients

In order to obtain our first result, we need to study the following sum:

$\begin{split}S(f,\mathcal{Q};X)&=\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n).\end{split}$

where symbol $\flat$ means that the sum runs over all square-free integers.
The function $r_{\mathcal{Q}}(n)$ being always non-negative allows us to write
the above partial sums defined in terms of known arithmetical functions modulo
certain weight, i.e.,

(7) $\begin{split}S(f,\mathcal{Q};X)&=\sideset{}{{}^{\flat}}{\sum}_{n\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n)r_{\mathcal{Q}}(n)=w_{D}\sideset{}{{}^{\flat}}{\sum}_{n\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n),\end{split}$

where $r_{\mathcal{Q}}(n)$ denotes the number of representations of $n$ by the
quadratic form $\mathcal{Q}(\underline{x})$, $w_{D}$ is size of group of units
and $r_{\mathcal{Q}}(n)=w_{D}r^{*}_{\mathcal{Q}}(n)$. We define the generating
function $\theta_{\mathcal{Q}}(\tau)$ for $r_{\mathcal{Q}}(n)$ associated to
binary quadratic form $\mathcal{Q}(\underline{x})$ as follows:

$\begin{split}\theta_{\mathcal{Q}}(\tau)&:=\displaystyle{\sum_{\underline{x}\in{\mathbb{Z}}^{2}}q^{\mathcal{Q}(\underline{x})}}\quad=\quad\displaystyle{\sum_{n=0}^{\infty}r_{\mathcal{Q}}(n)q^{n}},\qquad\quad~{}~{}~{}q=e^{2\pi
i\tau}.\\\ \end{split}$

The generating function $\theta_{\mathcal{Q}}(\tau)\in
M_{1}(\Gamma_{0}(|D|),\chi_{D})$ (see [8, Theorem 10.9]), where $\chi_{D}$ is
the Dirichlet character modulo $|D|$ which is given by Jacobi symbol
$\chi_{D}(d):=\left(\frac{D}{d}\right)$. It is well-known that
$r_{\mathcal{Q}}(n)\ll n^{\epsilon}$.

We are considering the quadratic forms $\mathcal{Q}(\underline{x})$ of
discriminant $D<0$ such that the class number $h(D)$ is $1$ and there is a
well-known formula for $r_{\mathcal{Q}}(n)$ given by [8, section 11.2]:

(8) $r_{\mathcal{Q}}(n)=w_{D}\sum_{d|n}\chi_{D}(d),\ \ {\rm~{}where~{}}\ \ \ \
\ w_{D}=\begin{cases}6{\rm~{}~{}~{}~{}~{}if~{}~{}~{}~{}~{}~{}}D=-3,\\\
4{\rm~{}~{}~{}~{}~{}if~{}~{}~{}~{}~{}~{}}D=-4,\\\
2{\rm~{}~{}~{}~{}~{}if~{}~{}~{}~{}~{}~{}}D<-4.\end{cases}$

The formula for $r_{\mathcal{Q}}(n)$ depends only on the discriminant $D$ but
not on the choice of $a,b$ and $c$ appearing in the definition of binary
quadratic from $\mathcal{Q}(\underline{x}).$ For details, we refer to [19, 20,
Section 2].

In order to obtain an upper bound for the sum $S(f,\mathcal{Q};X),$ We
consider the following Dirichlet series:

(9) $\begin{split}L(f,\mathcal{Q};s)&=\sideset{}{{}^{\flat}}{\sum}_{n\geq
1\atop\gcd(n,N)=1}\frac{\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)}{n^{s}},\end{split}$

where $r^{*}_{\mathcal{Q}}(n)=\displaystyle{\sum_{d|n}}~{}\chi_{D}(d).$ The
Dirichlet series $L(f,\mathcal{Q};s)$ converges absolutely and uniformly for
$\Re(s)>1.$ To obtain an upper bound for the sum $S(f,\mathcal{Q};X),$ we
first decompose $L(f,\mathcal{Q};s)$ in terms of known Hecke $L$-functions.
Before stating the decomposition of $L(f,\mathcal{Q};s)$ in terms of well-
known function, we define the $L$-functions associated to a Hecke eigenform.
The Hecke $L$-function associated to a normalised Hecke eigenform
$f(\tau)=\displaystyle{\sum_{n=1}^{\infty}\lambda_{f}(n)n^{\frac{k-1}{2}}q^{n}}\in
S_{k}(\Gamma_{0}(N))$ is given by:

(10) $\begin{split}L(s,f)&=\sum_{n\geq
1}\frac{\lambda_{f}(n)}{n^{s}}=\prod_{p\mid
N}\left(1-\frac{\lambda_{f}(p)}{p^{s}}\right)^{-1}\prod_{p\nmid
N}\left(1-\frac{\lambda_{f}(p)}{p^{s}}+\frac{1}{p^{2s}}\right)^{-1},\qquad\Re(s)>1.\end{split}$

The completed Hecke $L$-function is defined as follows:

(11)
$\begin{split}\Lambda(s,f):=\left(\frac{\sqrt{N}}{2\pi}\right)^{s}\Gamma(s+k-1)~{}~{}L(s,f),\end{split}$

which is analytically continued to the whole complex plane and satisfies a
nice functional equation $(s\rightarrow 1-s).$ For a given Dirichlet character
$\chi$ of modulus $m,$ the twist of $f$ is defined as
$f\otimes\chi(\tau):=\displaystyle{\sum_{n=1}^{\infty}\lambda_{f}(n)\chi(n)n^{\frac{k-1}{2}}q^{n}}\in
S_{k}(\Gamma_{0}(M),\chi^{2}),$ where $M\mid Nm^{2}.$ The twisted Hecke $L$\-
function associated to $f\otimes\chi$ is given as follows:

(12) $\begin{split}L(s,f\otimes\chi)&=\sum_{n\geq
1}\frac{\lambda_{f}(n)\chi(n)}{n^{s}}=\\!\\!\prod_{p\mid
M}\\!\\!\left(1-\frac{\lambda_{f}(p)\chi(p)}{p^{s}}\right)^{-1}\\!\\!\\!\prod_{p\nmid
M}\left(1-\frac{\lambda_{f}(p)\chi(p)}{p^{s}}+\frac{1}{p^{2s}}\right)^{-1}\\!\\!.\\\
\end{split}$

This also converges absolutely, uniformly and non-vanishing for $\Re(s)>1.$
The completed twisted Hecke $L$-function is defined as follows:

(13)
$\begin{split}\Lambda(s,f\otimes\chi):=\left(\frac{\sqrt{M}}{2\pi}\right)^{s}\Gamma(s+k-1)L(s,f\otimes\chi),\end{split}$

which also has analytic continuation to whole $\mathbb{C}$-plane and satisfies
a nice functional equation $(s\rightarrow 1-s).$ For details, see [8, Section
7.2]. The decomposition of $L(f,\mathcal{Q};s)$ is given by the following
Lemma.

######  Lemma 2.1.

For $\Re(s)>1$, we have

(14) $\begin{split}L(f,\mathcal{Q};s)&=L(s,f)L(s,f\otimes{\chi_{D}})G(s),\\\
\end{split}$

where $L(s,f)$ and $L(s,f\otimes{\chi_{D}})$ are Hecke $L$-function and
twisted Hecke $L$-function, respectively and the Euler product for $G(s)$ is
given by

$\begin{split}&\prod_{p\mid
N}\left(1-\frac{\lambda_{f}(p)}{p^{s}}\right)\prod_{p\mid
N}\left(1-\frac{\lambda_{f}(p)\chi_{D}(p)}{p^{s}}\right)\prod_{p\nmid N\atop
p\mid|D|}\left(1-\frac{\lambda_{f}(p)\chi_{D}(p)}{p^{s}}+\frac{1}{p^{2s}}\right)^{-1}\\\
&\prod_{p\nmid
N}\left(\begin{cases}1+\frac{2-2\lambda^{2}_{f}(p)-\lambda^{2}_{f}(p)\chi_{D}(P)}{p^{2s}}+\frac{\lambda_{f}(p)(1+\chi_{D}(p))(1+\lambda^{2}_{f}(p)\chi_{D}(p))}{p^{3s}}\\\
\qquad\qquad+\frac{1-2\lambda^{2}_{f}(p)(1+\chi_{D}(P))}{p^{4s}}+\frac{\lambda_{f}(p)(1+\chi_{D}(P))}{p^{5s}}\end{cases}\right).\end{split}$

It converges absolutely and uniformly in the half plane $\Re(s)>\frac{1}{2}$
and non-zero for $\Re(s)=1$.

###### Proof.

We know that $\lambda_{f}(n)$ and $r^{*}_{\mathcal{Q}}(n)$ are multiplicative
function. So, for $\Re(s)>1,$ we have

$\begin{split}L(f,\mathcal{Q};s)&=\\!\\!\\!\\!\sideset{}{{}^{\flat}}{\sum}_{n\geq
1\atop\gcd(n,N)=1}\frac{\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)}{n^{s}}=\prod_{p\nmid
N}\left(1+\frac{\mu^{2}(p)\lambda_{f}(p)r^{*}_{\mathcal{Q}}(p)}{p^{s}}\right)\\\
&=\prod_{p\nmid
N}\left(1+\frac{\lambda_{f}(p)(1+\chi_{D}(p))}{p^{s}}\right)=L(s,f)L(s,f\otimes\chi_{D})G(s),\\\
\end{split}$

where the Euler product for $G(s)$ is given in lemma. ∎

######  Lemma 2.2.

[9, Chapter 5] Let $\epsilon>0$ be an arbitrarily small real number. The
hybrid convexity bound of Hecke $L$-function and twisted Hecke $L$-function is
given by:

(15)
$\begin{split}L(s,f)&\ll_{\epsilon}\left(Nk^{2}(|s|+3)^{2}\right)^{\frac{1}{4}+\epsilon}~{}\\\
{\rm and}\quad
L(s,f\otimes{\chi_{D}})&\ll_{\epsilon}\left(Nk^{2}|D|^{2}(|s|+3)^{2}\right)^{\frac{1}{4}+\epsilon}~{}\\\
\end{split}$

on the line $\Re(s)=\frac{1}{2}+\epsilon.$ The second integral moment is given
by

(16)
$\begin{split}\int_{T}^{2T}\left|L\left(\frac{1}{2}+\epsilon+it,f\right)\right|^{2}dt&\ll_{\epsilon}(Nk^{2}T^{2})^{\frac{1}{2}+\epsilon}\\\
\int_{T}^{2T}\left|L\left(\frac{1}{2}+\epsilon+it,f\otimes\chi_{D}\right)\right|^{2}dt&\ll_{\epsilon}(Nk^{2}|D|^{2}T^{2})^{\frac{1}{2}+\epsilon}\end{split}$

uniformly for any $|T|\geq 1$.

###  2.1.  Mean value of a multiplicative function over the integers
represented by a reduced form of discriminant $D$ with $h(D)=1$

Let $\eta$ be a fixed positive integer. We define the following sum given by

$\begin{split}\mathcal{E}_{\eta}(X)&=\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
X\atop\gcd(n,N)=1}\eta^{\omega(n)},\end{split}$

where $\omega(n)$ denotes the number of distinct prime divisors of a positive
integer $n$. The above sum can be expressed in terms of known arithmetical
function given by

(17)
$\begin{split}\mathcal{E}_{\eta}(X)&=\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
X\atop\gcd(n,N)=1}\eta^{\omega(n)}=\sum_{n\leq
X\atop\gcd(n,N)=1}\mu^{2}(n)\eta^{\omega(n)}r^{*}_{\mathcal{Q}}(n).\\\
\end{split}$

In order to obtain an estimate for $\mathcal{E}_{\eta}(X)$ we first decompose
the associated Dirichlet series (say $D(s)$) in terms of known $L$-functions
and then apply the Perron’s formula and use the standard argument. The
associated Dirichlet series $D(s)$ is given by

$\begin{split}D(s)&=\sum_{n\geq
1\atop\gcd(n,N)=1}\frac{\mu^{2}(n)\eta^{\omega(n)}r^{*}_{\mathcal{Q}}(n)}{n^{s}}.\end{split}$

The Dirichlet series $D(s)$ converges for $\Re(s)>1$. Following the argument
as in the proof of Lemma 2.1, one has the decomposition of $D(s)$ as follows.

(18) $\begin{split}D(s)&=\prod_{p\nmid
N}\left(1+\frac{\mu^{2}(p)\eta^{\omega(p)}r^{*}_{\mathcal{Q}}(p)}{p^{s}}\right)=\prod_{p\nmid
N}\left(1+\frac{\eta(1+\chi_{D}(p))}{p^{s}}\right)=\zeta^{\eta}(s)L^{\eta}(s,\chi_{D})P(s),\\\
\end{split}$

where $\zeta(s)$ is the Riemann zeta function, and $L(s,\chi_{D})$ is the
Dirichlet $L$\- function associated to the quadratic character $\chi_{D}$ and
$P(s)$ is given in terms of Euler product as follows:

(19) $\begin{split}P(s)&=\prod_{p\mid
N}\left[\left(1-\frac{1}{p^{s}}\right)\left(1-\frac{\chi_{D}(p)}{p^{s}}\right)\right]^{\eta}\prod_{p\nmid
N}\left[\left(1-\frac{1}{p^{s}}\right)^{\eta}\left(1-\frac{\chi_{D}(p)}{p^{s}}\right)^{\eta}\left(1+\frac{\eta(1+\chi_{D}(p))}{p^{s}}\right)\right].\\\
\\\ \end{split}$

The last product converges absolutely and uniformly for $\Re(s)>1/2$ and non-
zero at $s=1.$ Using the Perron’s formula, an estimate for
$\mathcal{E}_{\eta}(X)$ is given in the following proposition.

######  Proposition 2.3.

Let $\mathcal{E}_{\eta}(X)$ be as in (17). Then there exist an absolute
constant $C=C(\eta)$ such that

(20)
$\begin{split}\mathcal{E}_{\eta}(X)&=\frac{P(1)L(1,\chi_{D})^{\eta}}{\Gamma(\eta)}X(\log
X)^{\eta-1}\left(1+O_{\eta}\left(\frac{L_{N}^{2e\eta+2}}{\sqrt{\log
X}}\right)\right)\end{split}$

uniformly for $N\geq 1$ and $X\geq\exp(CL_{N}^{2e\eta+2})$ where
$L_{N}=\log(\omega(N)+3).$

Proof of the Proposition 2.3: Following the argument of [12, Lemma 4.1], we
obtained our result. Here, we give details of our proof. By Perron’s formula
and (18), we have

(21) $\begin{split}\mathcal{E}_{\eta}(X)&=\sum_{n\leq
X\atop\gcd(n,N)=1}\mu^{2}(n)\eta^{\omega(n)}r^{*}_{\mathcal{Q}}(n)=\frac{1}{2\pi
i}\int_{b-iT}^{b+iT}\zeta^{\eta}(s)L^{\eta}(s,\chi_{D})P(s)\frac{X^{s}}{s}ds+O(R)\\\
\end{split}$

where $b=1+\frac{1}{\log X}$, $T\geq 3$ and

(22)
$\begin{split}R&=X\sum_{n=1}^{\infty}\frac{\eta^{\omega(n)}r^{*}_{\mathcal{Q}}(n)}{n^{b}(1+T|\log(X/n)|)}.\end{split}$

From the Weil bound ($r^{*}_{\mathcal{Q}}(n)\ll_{\epsilon}n^{\epsilon}$ for
any $\epsilon>0$), we chose $\epsilon=1/2\log X$ so that
$r^{*}_{\mathcal{Q}}(n)\ll_{\epsilon}n^{1/2\log X}$ and use it to get (with
$b_{0}=1+\frac{1}{2\log X}$)

(23) $\begin{split}R&\ll
X\sum_{n=1}^{\infty}\frac{\eta^{\omega(n)}}{n^{b_{0}}(1+T|\log(X/n)|)}.\end{split}$

We break the above summation into following two parts and obtain an estimate
for $R$.
$(i)$ $n$ with $|\log(X/n)|\leq T^{-1/2}$ $(ii)$ $n$ with
$|\log(X/n)|>T^{-1/2}$.
In the first case, the estimate for the summation over $n$ with
$|\log(X/n)|\leq T^{-1/2}$ is obtained as follows.

$\begin{split}&X\sum_{|n-X|\leq
XT^{-1/2}}\frac{\eta^{\omega(n)}}{n^{b_{0}}(1+T|\log(X/n)|)}\ll\sum_{|n-X|\leq
XT^{-1/2}}\left(\frac{X}{n}\right)^{b_{0}}\frac{\eta^{\omega(n)}}{(1+T|\log(X/n)|)}\\\
&\ll\sum_{|n-X|\leq XT^{-1/2}}\eta^{\omega(n)}\ll\left(\sum_{|n-X|\leq
XT^{-1/2}}\eta^{2\omega(n)}\right)^{\frac{1}{2}}\left(\sum_{|n-X|\leq
XT^{-1/2}}\right)^{\frac{1}{2}}\ll\frac{X(\log
X)^{\frac{\eta^{2}-1}{2}}}{T^{1/4}}.\end{split}$

Which is obtained using the Cauchy-Schwarz inequality and argument as in [12,
Lemma 4.1]. In the second case, an estimate is obtained as follows.

$\begin{split}&X\sum_{|n-X|>XT^{-1/2}}\frac{\eta^{\omega(n)}}{n^{b_{0}}(1+T|\log(X/n)|)}\ll\frac{X}{T^{1/4}}\sum_{|n-X|>XT^{-1/2}}\frac{\eta^{\omega(n)}}{n^{b_{0}}}\ll\frac{X}{T^{1/4}}(\log
X)^{\eta-1}.\\\ \end{split}$

Thus, we have

(24) $\begin{split}R&\ll
X\sum_{n=1}^{\infty}\frac{\eta^{\omega(n)}}{n^{b_{0}}(1+T|\log(X/n)|)}\ll{\rm
max}\left\\{\frac{X(\log X)^{\frac{\eta^{2}-1}{2}}}{T^{1/4}},\frac{X(\log
X)^{\frac{\eta-1}{2}}}{T^{1/2}}\right\\}.\end{split}$

To complete the proof, we need to evaluate the integral given in (21). Let $c$
be a positive constant and $\sigma_{c}(T):=1-\frac{c}{\log T}$. Following the
argument as in [12], let $r=1/2\log X$ and assume that $1-r>\sigma_{c}(T)$.
The truncated Hankel contour $\Gamma$ is a positively oriented contour formed
from the circle $|s-1|=r$ excluding the points $s=1-r$ and joining the half
segment $[\sigma_{c}(T),1-r]$ which is traced out twice with respective
argument $+\pi$ and $-\pi$. We apply the Cauchy residue theorem to the closed
path consisting of vertical line segment $[b-iT,b+iT]$ and
$\mathcal{P}_{v}^{\pm}:=[\sigma_{c/2}(T),\sigma_{c/2}(T)\pm iT]$, two
horizontal line segment $\mathcal{P}_{h}^{\pm}:=[\sigma_{c/2}(T)\pm iT,b\pm
iT]$ and the Hankel contour $\Gamma$.

For $\Re(s)\geq\sigma_{c}(T)$, we observe that

(25) $\begin{split}P(s)&\ll\left|\prod_{p\mid
N}\left(1+\frac{1}{p^{s}}\right)^{\eta}\prod_{p\mid
N}\left(1-\frac{\chi_{D}(p)}{p^{s}}\right)^{\eta}\right|\ll\prod_{p\mid
N}\left(1+\frac{1}{p^{\sigma_{c}(T)}}\right)^{2\eta}\\\
&\ll\exp\\{2\eta\exp(2cL_{N}/\log T)\log L_{N}\\}\ll L_{N}^{2e\eta}\\\
\end{split}$

using Merten’s third theorem and $p_{n}\approx n\log n$ ( $p_{n}$ denotes the
$n^{\rm th}$ prime), provided $T\geq\exp(2cL_{N})$. From the above estimate
and Cauchy’s integral formula, we obtain that (for
$\Re(s)\geq\sigma_{c/2}(T)$)

(26) $\begin{split}P^{\prime}(s)&=\frac{1}{2\pi
i}\int_{|z-\sigma_{c/2}(T)|=\frac{c}{\log
T}}\frac{P(z)}{(z-s)^{2}}dz\ll\exp\\{2\eta\exp(2cL_{N}/\log T)\log
L_{N}\\}\log T\\\ &\ll L_{N}^{2e\eta}\log T.\end{split}$

From the bound $\zeta(s)\ll\log T$ for
$s\in\mathcal{P}_{h}^{\pm}\cup\mathcal{P}_{h}^{\pm}\cup\Gamma$, and (25), it
is easy to have

(27) $\begin{split}\frac{1}{2\pi
i}\int_{\mathcal{P}_{h}^{\pm}\cup\mathcal{P}_{h}^{\pm}}\zeta^{\eta}(s)L^{\eta}(s,\chi_{D})P(s)\frac{X^{s}}{s}ds\ll
L_{N}^{2e\eta}\left(\frac{X}{T}+X^{\sigma_{c/2}(T)}\right)(\log
T)^{\eta-1}.\\\ \end{split}$

Using the property of $\zeta(s)$ and bound for $P^{\prime}(s)$ (given in
(26)), we have (for $s\in\Gamma$)

(28)
$\begin{split}\frac{((s-1)\zeta(s))^{\eta}}{s}L^{\eta}(s,\chi_{D})P(s)=L^{\eta}(1,\chi_{D})P(1)+O_{\eta}(L^{\eta}(1,\chi_{D})L_{N}^{2e\eta}\log
T|s-1|)\end{split}$

provided $T\geq\exp(2cL_{N})$. This allows to get

(29)
$\begin{split}&\int_{\Gamma}\zeta^{\eta}(s)L^{\eta}(s,\chi_{D})P(s)\frac{X^{s}}{s}ds\\\
&\quad=L^{\eta}(1,\chi_{D})P(1)\int_{\Gamma}(s-1)^{-\eta}X^{s}ds+O_{\eta}\left(L^{\eta}(1,\chi_{D})L_{N}^{2e\eta}\log
T\int_{\Gamma}|s-1|^{1-\eta}X^{s}ds\right).\end{split}$

Using [18, Corollary II.0.18], we have

$\begin{split}\int_{\Gamma}(s-1)^{-\eta}X^{s}ds&=X(\log
X)^{\eta-1}\left\\{1+O_{\eta}(e^{-\frac{c\log X}{2\log T}})\right\\}\\\
\quad{\rm
and}\quad\int_{\Gamma}|s-1|^{1-\eta}X^{s}ds&\ll\int_{\sigma_{c/2}(T)}^{1-r}(1-y)^{1-\eta}X^{y}dy+X^{1+r}r^{2-\eta}\ll
X(\log X)^{\eta-2}.\end{split}$

Thus, we have

(30)
$\begin{split}&\int_{\Gamma}\zeta^{\eta}(s)L^{\eta}(s,\chi_{D})P(s)\frac{X^{s}}{s}ds\\\
&\quad=\frac{L^{\eta}(1,\chi_{D})P(1)}{\Gamma(\eta)}X(\log
X)^{\eta-1}\left\\{1+O_{\eta}\left(e^{-\frac{c\log X}{2\log
T}}\right)\right\\}+O_{\eta}\left(L^{\eta}(1,\chi_{D})L_{N}^{2e\eta}X\log
T(\log X)^{\eta-2}\right).\end{split}$

Applying Cauchy residue theorem and Combining all the estimates, we have

$\begin{split}&\frac{1}{2\pi
i}\int_{b-iT}^{b+iT}\zeta^{\eta}(s)L^{\eta}(s,\chi_{D})P(s)\frac{X^{s}}{s}ds\\\
&=\frac{L^{\eta}(1,\chi_{D})P(1)}{\Gamma(\eta)}X(\log
X)^{\eta-1}\left\\{1+O_{\eta}(e^{-\frac{c\log X}{2\log
T}})\right\\}+O_{\eta}\left(L^{\eta}(1,\chi_{D})L_{N}^{2e\eta}\log TX(\log
X)^{\eta-2}\right)\\\
&\quad+O_{\eta}(L_{N}^{2e\eta}\left(\frac{X}{T}+X^{\sigma_{c/2}(T)}\right)(\log
T)^{\eta-1}).\end{split}$

Thus, we have

(31) $\begin{split}\mathcal{E}_{\eta}(X)&=\sum_{n\leq
X\atop\gcd(n,N)=1}\mu^{2}(n)\eta^{\omega(n)}r^{*}_{\mathcal{Q}}(n)=\frac{L^{\eta}(1,\chi_{D})P(1)}{\Gamma(\eta)}X(\log
X)^{\eta-1}+{\rm Err}\\\ \end{split}$

where

$\begin{split}{\rm
Err}&=O_{\eta}\left(\frac{L^{\eta}(1,\chi_{D})P(1)}{\Gamma(\eta)}X(\log
X)^{\eta-1}(e^{-\frac{c\log X}{2\log
T}})\right)+O_{\eta}\left(L^{\eta}(1,\chi_{D})L_{N}^{2e\eta}\log TX(\log
X)^{\eta-2}\right)\\\
&\quad+O_{\eta}\left(L_{N}^{2e\eta}\left(\frac{X}{T}+X^{\sigma_{c/2}(T)}\right)(\log
T)^{\eta-1}\right)+O_{\eta}\left({\rm max}\left\\{\frac{X(\log
X)^{\frac{\eta^{2}-1}{2}}}{T^{1/4}},\frac{X(\log
X)^{\frac{\eta-1}{2}}}{T^{1/2}}\right\\}\right).\end{split}$

Clearly, it is easy to see that

$P(1)\gg L_{N}^{-2}$

using Merten’s theorem. We choose $T=\exp({c_{1}\sqrt{\log X}})$ so that
$T\geq\exp(2cL_{N})$ is satisfied. Hence, for each $X\geq\exp(2cL_{N}^{2})$,
The error term satisfies following bound.

$\begin{split}{\rm Err}&\ll\frac{L^{\eta}(1,\chi_{D})P(1)}{\Gamma(\eta)}X(\log
X)^{\eta-1}\frac{L_{N}^{2e\eta+2}}{\sqrt{\log X}}.\end{split}$

Thus, we have the required result. This completes the proof.

Let $Y$ be a positive real number. From Deligne’s estimate, it is well-known
that for each prime $p$, $\lambda_{f}(p)=2\cos\theta_{p},$ and more generally

$\lambda_{f}(p^{m})=\frac{\sin((m+1)\theta_{p})}{\sin~{}\theta_{p}},$

for any positive integer $m.$ We define a multiplicative function $h_{Y}$
supported on square-free positive integers. The function $h_{Y}$ is given by:

(32) $\begin{split}&\qquad\quad h_{Y}(p)=\begin{cases}\alpha\left(\frac{\log
p}{\log Y}\right),\qquad{\rm if}\qquad p\leq Y\quad{\rm and}\quad p\nmid N,\\\
-2,\qquad\qquad\quad{\rm if}\qquad p>Y\quad{\rm and}\quad p\nmid N,\\\
0,\qquad\qquad\qquad{\rm if}\qquad p\mid N,\end{cases}\\\ \end{split}$

where $\quad\alpha:[0,1]\rightarrow{[-2,2]}$ is such that, $\alpha(0)=2$ and
$\alpha(t)=2\cos(\frac{\pi}{m+1})$ if $\frac{1}{m+1}<t\leq\frac{1}{m}$ for
$m\in\mathbf{N}$. We make use of the function $h_{Y}$ to obtain a lower bound
for the sum $S(f,\mathcal{Q};Y^{u})$ for some $u\geq 1$, following the idea of
[11].

######  Proposition 2.4.

Let $U\geq 1$ be a real number, $h_{Y}(n)$ (defined in (32)) and $\alpha(t)$
be as above with $\alpha_{0}>0$. Let $N\leq X^{U}$ be a positive integer.
Then, we have

$\begin{split}\sum_{n\leq
Y^{u}\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)&=(\sigma(u)+o_{\alpha,U}(1))\frac{P(1)L(1,\chi_{D})^{\alpha_{0}}}{\Gamma(\alpha_{0})}(\log
Y^{u})^{\alpha_{0}-1}Y^{u}\end{split}$

uniformly for $u\in\left[\frac{1}{U},U\right]$ where $P(s)$ is given in (19)
and

$\begin{split}\sigma(u)&=(u)^{\alpha_{0}-1}+\sum_{j=1}^{\infty}\frac{(-1)^{j}}{j}I_{j}(u)\\\
\end{split}$

with

$\begin{split}I_{j}(u)&=\int_{\Delta_{j}}(u-t_{1}-t_{2}-\cdots-
t_{j})^{\alpha_{0}-1}\prod_{i=1}^{j}(\alpha_{0}-\alpha(t))\frac{dt_{1}dt_{2}\cdots
dt_{j}}{{t_{1}t_{2}\cdots t_{j}}}\\\ \end{split}$

and

$\begin{split}&\Delta_{j}=\\{(t_{1},t_{2},\cdots,t_{j})\in[0,\infty)\mid|t_{1}+t_{2}+\cdots+t_{j}|\leq
u\\}.\end{split}$

Proof of Proposition 2.4: We follow the argument of [14, Lemma 6] to give a
brief proof of the Proposition 2.4. From inclusion-exclusion type identity, we
have

$\begin{split}\sum_{n\leq
Y^{u}\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)&=\sum_{n\leq
Y^{u}\atop\gcd(n,N)=1}\alpha_{0}^{\omega(n)}r^{*}_{\mathcal{Q}}(n)\\\
&\quad+\sum_{j=1}^{\infty}\frac{(-1)^{j}}{j}\\!\\!\\!\\!\\!\\!\\!\\!\sum_{p_{1}p_{2}\cdots
p_{j}\leq Y^{u}\atop\gcd({p_{1}p_{2}\cdots
p_{j},N)=1}}\prod_{i=1}^{j}(\alpha_{0}-h_{Y}(p_{i}))r^{*}_{\mathcal{Q}}(p_{i})\sum_{n\leq\frac{Y^{u}}{p_{1}p_{2}\cdots
p_{j}}\atop\gcd(n,N)=1}\alpha_{0}^{\omega(n)}r^{*}_{\mathcal{Q}}(n).\end{split}$

From the Chebatorev density theorem, as the class number $h(D)=1$, the density
of primes represented by ${\mathcal{Q}}$ of discriminant $D$ is $1/2$, and for
such primes, we have $r^{*}_{\mathcal{Q}}(p)=2$ and $0$ otherwise. See [21,
Eq. 1.1 & 1.2] On applying Proposition 2.3, we have

$\begin{split}&\sum_{n\leq
Y^{u}\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)\\\
&=\frac{P(1)L(1,\chi_{D})^{\eta}}{\Gamma(\eta)}Y^{u}\begin{cases}(\log
Y^{u})^{\alpha_{0}-1}\\\
\displaystyle{+\sum_{j=1}^{\infty}\frac{(-1)^{j}}{j}\sum_{p_{1}p_{2}\cdots
p_{j}\leq Y^{u}\atop\gcd({p_{1}p_{2}\cdots
p_{j},N)=1}}\prod_{i=1}^{j}(\alpha_{0}-h_{Y}(p_{i}))r^{*}_{\mathcal{Q}}(p_{i})\frac{(\log\frac{Y^{u}}{p_{1}p_{2}\cdots
p_{j}})^{\alpha_{0}-1}}{{p_{1}p_{2}\cdots p_{j}}}}\end{cases}\\\
&=\frac{P(1)L(1,\chi_{D})^{\eta}}{\Gamma(\eta)}Y^{u}\begin{cases}(\log
Y^{u})^{\alpha_{0}-1}\\\
\displaystyle{+\sum_{j=1}^{\infty}\frac{(-1)^{j}}{j}\sum_{p_{1}p_{2}\cdots
p_{j}\leq Y^{u}\atop\gcd({p_{1}p_{2}\cdots
p_{j},N)=1}}\prod_{i=1}^{j}(\alpha_{0}-h_{Y}(p_{i}))\frac{(\log\frac{Y^{u}}{p_{1}p_{2}\cdots
p_{j}})^{\alpha_{0}-1}}{{p_{1}p_{2}\cdots p_{j}}}}.\end{cases}\end{split}$

Thus, we have the exactly the same expression as in the proof of [14, Lemma
6]. So, removing the coprimality condition from the expression and then using
the prime number theorem, we have the required result.

######  Remark 2.1.

Let $\alpha$ be a step function given by;
$\alpha:[0,\infty)\rightarrow\mathbb{R}$ with $\alpha(t)=\alpha_{k}$ when
$t\in[x_{k},x_{k+1}]$ for each $k=0,1,2,\cdots K$. Here $K>0$ and
$[x_{k},x_{k+1}]$ is partition of $[0,\infty)$ (in our case $x_{0}=0$,
$x_{k}=\frac{1}{k}$, $\alpha_{0}=2$ and $\alpha_{k}=2\cos(\frac{\pi}{k+1})$).
In [14, Lemma 6], it was mentioned that the function, $\sigma(u)$ is the
unique solution of the integral equation

$u\sigma(u)=\int_{0}^{u}\sigma(t)\alpha(u-t)dt$

with the initial condition $\sigma(u)=u^{\alpha_{0}-1}$ for $u\in(0,x_{1}]$.
For the step function $\alpha$, it is shown that $\sigma(4/3)>0$ in [14, Lemma
8]. Hence, for $u=u_{0}=4/3$, we have

(33) $\begin{split}\sum_{n\leq
Y^{u_{0}}\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)&=(\sigma(u_{0})+o_{\alpha,U}(1))\frac{P(1)L(1,\chi_{D})^{\alpha_{0}}}{\Gamma(\alpha_{0})}(\log
Y)^{\alpha_{0}-1}Y^{u_{0}}>0.\end{split}$

##  3\. Proof of Results

Proof of Theorem 1.1: Let $1\leq Z\leq\frac{X}{2}$. In order to obtain an
upper bound for the sum $S(f,\mathcal{Q};X)$ given in (3), we introduce a
smooth compactly supported function $w(x)$ satisfying: $w(x)=1$ for
$x\in[2Z,X],$ $w(x)=0$ for $x<Z$ and $x>X+Z,$ and $w^{(r)}(x)\ll_{r}Z^{-r}$
for all $r\geq 0.$ In general, for any arithmetical function $f(n),$ we have

(34) $\sum_{n\leq
X}f(n)=\sum_{n=1}^{\infty}f(n)w(n)+O\left(\sum_{n<2Z}|f(n)|\right)+O\left(\sum_{X<n<X+Z}|f(n)|\right).$

Moreover, by Mellin’s inverse transform, we have

(35) $\sum_{n=1}^{\infty}f(n)w(n)=\frac{1}{2\pi
i}\int_{(b)}\tilde{w}(s)\left(\sum_{n\geq 1}\frac{f(n)}{n^{s}}\right)ds,$

where $b$ is a positive real number larger than the abscissa of absolute
convergence of $\displaystyle{\sum_{n\geq 1}\frac{f(n)}{n^{s}}}$ and the
Mellin’s transform $\tilde{w}(s)$ is given by following integral:

$\tilde{w}(s)=\int_{0}^{\infty}w(x)x^{s}\frac{dx}{x}.$

We observe that due to integration by parts,

(36)
$\tilde{w}(s)=\frac{1}{s(s+1)\cdots(s+m-1)}\int_{0}^{\infty}w^{(m)}(x)x^{s+m-1}dx\ll\frac{Z}{X^{1-\sigma}}\left(\frac{X}{|s|Z}\right)^{m},$

for any $m\geq 0,$ where $\sigma=\Re(s).$ For details, we refer to [6, Section
3].

From Equation (34) with $f(n)=\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n),$ we have

$\begin{split}\sideset{}{{}^{\flat}}{\sum}_{n\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)&=\sideset{}{{}^{\flat}}{\sum}_{n\geq
1\atop\gcd(n,N)=1}\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)w(n)\\\
&\quad+O\left(\sideset{}{{}^{\flat}}{\sum}_{n<2Z\atop\gcd(n,N)=1}|\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)|\right)+O\left(\sideset{}{{}^{\flat}}{\sum}_{X<n<X+Z\atop\gcd(n,N)=1}|\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)|\right).\end{split}$

Moreover, by Mellin’s inverse transform, we have

(37) $\sideset{}{{}^{\flat}}{\sum}_{n\geq
1\atop\gcd(n,N)=1}\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)w(n)=\frac{1}{2\pi
i}\int_{(b)}\tilde{w}(s)L(f,\mathcal{Q};s)ds,$

where $b=1+\epsilon$ for some arbitrarily small $\epsilon>0.$ Since
$\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)\ll n^{\epsilon},$ for any $\epsilon>0,$
hence,

(38)
$\begin{split}O\left(\sideset{}{{}^{\flat}}{\sum}_{n<2Z\atop\gcd(n,N)=1}|\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)|\right)+O\left(\sideset{}{{}^{\flat}}{\sum}_{X<n<X+Z\atop\gcd(n,N)=1}|\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)|\right)\ll
Z^{1+\epsilon}.\end{split}$

We know that $L(f,\mathcal{Q};s)$ is holomorphic for all $s\in\mathbb{C}$. We
shift the line of integration from $\Re(s)=1+\epsilon$ to
$\Re(s)=\frac{1}{2}+\epsilon$ and apply Cauchy’s residue theorem to get

(39) $\sideset{}{{}^{\flat}}{\sum}_{n\geq
1\atop\gcd(n,N)=1}\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)w(n)=\frac{1}{2\pi
i}\int_{(1+\epsilon)}\tilde{w}(s)L(f,\mathcal{Q};s)ds=\frac{1}{2\pi
i}\int_{(1/2+\epsilon)}\tilde{w}(s)L(f,\mathcal{Q};s)ds.$

Since $\tilde{w}(s)\ll\frac{Z}{X^{1-\sigma}}\left(\frac{X}{|s|Z}\right)^{m}$
for any $m\geq 0,$ so the contribution for the integral over $|s|\geq
T=\frac{X^{1+\epsilon}}{Z}$ on the right hand side of (39) is negligibly
small, i.e., $O(X^{-A})$ for any large $A>0$ if one chooses sufficiently large
$m>0.$ Hence, we have

$\begin{split}\frac{1}{2\pi
i}\int_{(1/2+\epsilon)}\tilde{w}(s)L(f,\mathcal{Q};s)ds&=\frac{1}{2\pi
i}\int_{1/2+\epsilon-
iT}^{1/2+\epsilon+iT}\tilde{w}(s)L(f,\mathcal{Q};s)ds+O(X^{-A})\\\
&\ll\int_{-T}^{T}|\tilde{w}(1/2+\epsilon+it)||L(f,\mathcal{Q};1/2+\epsilon+it)|dt+O(X^{-A})\\\
&\ll\int_{0}^{T}\frac{X^{\frac{1}{2}+\epsilon}}{|\frac{1}{2}+\epsilon+it|}|L(f,\mathcal{Q};1/2+\epsilon+it)|dt+O(X^{-A})\\\
&\ll\left(\int_{0}^{1}+\int_{1}^{T}\right)\frac{X^{\frac{1}{2}+\epsilon}}{|\frac{1}{2}+\epsilon+it|}|L(f,\mathcal{Q};1/2+\epsilon+it)|dt+O(X^{-A}),\\\
\end{split}$

where the estimate in the last lines is obtained by substituting the bound for
$\tilde{w}(s)$ when $m=1.$ Now, we substitute the decomposition
$L(f,\mathcal{Q};s)=L(s,f)L(s,f\otimes\chi_{D})G(s)$ from Lemma 2.1 and by
absolute convergence of $G(s)$ for $\Re(s)>\frac{1}{2}$, we get

$\begin{split}&\frac{1}{2\pi
i}\int_{(1/2+\epsilon)}\tilde{w}(s)L(f,\mathcal{Q};s)ds\\\
&\ll\left(\int_{0}^{1}+\int_{1}^{T}\right)\frac{X^{\frac{1}{2}+\epsilon}}{|\frac{1}{2}+\epsilon+it|}|L(1/2+\epsilon+it,f)L(1/2+\epsilon+it,f\otimes\chi_{D})|dt+O(X^{-A})\\\
&\ll(Nk^{2}|D|X)^{\frac{1}{2}+\epsilon}+X^{\frac{1}{2}+\epsilon}\int_{1}^{T}\frac{|L(1/2+\epsilon+it,f)L(1/2+\epsilon+it,f\otimes\chi_{D})|}{t}dt+O(X^{-A}).\\\
\end{split}$

We apply the dyadic division method and then Cauchy-Schwartz inequality to get

$\begin{split}&\frac{1}{2\pi
i}\int_{(1/2+\epsilon)}\tilde{w}(s)L(f,\mathcal{Q};s)ds\\\
&\ll\begin{cases}(Nk^{2}|D|X)^{\frac{1}{2}+\epsilon}+O(X^{-A})\\\
+~{}X^{\frac{1}{2}+\epsilon}\underset{1\leq T_{1}\leq T}{\rm
max}\\!\\!\left\\{\frac{1}{T_{1}}\\!\\!\left(\int_{\frac{T_{1}}{2}}^{T_{1}}|L(1/2+\epsilon+it,f)|^{2}dt\right)^{\frac{1}{2}}\\!\\!\left(\int_{\frac{T_{1}}{2}}^{T_{1}}L(1/2+\epsilon+it,f\otimes\chi_{D})|^{2}dt\right)^{\frac{1}{2}}\right\\}\\\
\end{cases}\\\
&\ll(Nk^{2}|D|X)^{\frac{1}{2}+\epsilon}+X^{\frac{1}{2}+\epsilon}\underset{1\leq
T_{1}\leq T}{\rm
max}\left(\frac{1}{T_{1}}(Nk^{2}T_{1}^{2})^{\frac{1}{4}+\epsilon}(Nk^{2}|D|^{2}T_{1}^{2})^{\frac{1}{4}+\epsilon}\right)+O(X^{-A})\\\
&\ll(Nk^{2}|D|X)^{\frac{1}{2}+\epsilon}.\end{split}$

The last inequality is obtained by substituting $T=\frac{X^{1+\epsilon}}{Z}$
and choosing $Z=X^{\frac{1}{2}+\epsilon}$. Thus

(40) $\begin{split}&\frac{1}{2\pi
i}\int_{(1/2+\epsilon)}\tilde{w}(s)L(f,\mathcal{Q};s)ds\ll(Nk^{2}|D|X)^{\frac{1}{2}+\epsilon}.\\\
\end{split}$

From equations (37), (38), (39) and (40) and choosing
$Z=X^{\frac{1}{2}+\epsilon}$, we have the required result.

Concerning about second result, one needs to obtain a lower estimate for the
sum $S(f,\mathcal{Q};Y^{u_{0}})$ under the certain assumption. Below, we
sketch the proof to get a lower estimate for the sum
$S(f,\mathcal{Q};Y^{u_{0}})$.

A lower bound for the sum $S(f,\mathcal{Q};Y^{u_{0}})$: We recall that
multiplicative function $h_{Y}$, supported on square-free positive integers,
is given by:

$\begin{split}&\qquad\quad h_{Y}(p)=\begin{cases}\alpha\left(\frac{\log
p}{\log Y}\right),\qquad{\rm if}\qquad p\leq Y\quad{\rm and}\quad p\nmid N,\\\
-2,\qquad\qquad\quad{\rm if}\qquad p>Y\quad{\rm and}\quad p\nmid N,\\\
0,\qquad\qquad\qquad{\rm if}\qquad p\mid N,\end{cases}\\\ \end{split}$

where$\quad\alpha:[0,1]\rightarrow{[-2,2]}$ is such that, $\alpha(0)=2$ and
$\alpha(t)=2\cos(\frac{\pi}{m+1})$ if $\frac{1}{m+1}<t\leq\frac{1}{m}$ for
$m\in\mathbf{N}$.

Assume that $\lambda_{f}(n)\geq 0$ for every square-free positive integer
$n\leq Y,$ which are represented by $\mathcal{Q}(\underline{x}).$ Then, Hecke
relation together with the assumption $\lambda_{f}(p)\geq 0$ for every prime
$p\leq Y^{1/m}$ implies that $\lambda_{f}(p)\geq
2\cos\left(\frac{\pi}{m+1}\right).$ This shows that $\lambda_{f}(p)\geq
h_{Y}(p),$ for all primes upto $Y.$ Multiplicativity of these arithmetical
functions shows that $\lambda_{f}(n)\geq h_{Y}(n),$ for all $n\leq Y.$ Similar
to [11], it is observed that for $X=Y^{u_{0}}$ with $u_{0}=4/3$,

(41) $\begin{split}S(f,\mathcal{Q};X)&=\sideset{}{{}^{\flat}}{\sum}_{n\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)\geq\sideset{}{{}^{\flat}}{\sum}_{n\leq
X\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)>0.\end{split}$

Precisely, to see (41), let $g_{Q}$ be a multiplicative function defined by
convolution identity $\lambda^{*}_{f}(n)=(g_{Q}*h^{*}_{Y})(n)$, where
$\lambda^{*}_{f}(n)=\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)$ and
$h^{*}_{y}(n)=h_{Y}(n)r^{*}_{\mathcal{Q}}(n).$ This gives that
$g_{Q}(p)=\lambda_{f}(p)r^{*}_{\mathcal{Q}}(p)-h_{Y}(p)r^{*}_{\mathcal{Q}}(p).$
If $p$ is not represented by $\mathcal{Q}(\underline{x}),$ then $g_{Q}(p)=0.$
If $p$ is represented by $\mathcal{Q}(\underline{x}),$ then $g_{Q}(p)\geq 0$
for all $p$ not dividing $N$ and upto $Y$ by definition of $h_{Y}(p).$ For
$p>Y,$ with $p\nmid N,$ we have $h_{Y}(p)r^{*}_{\mathcal{Q}}(p)=-4$ and
$-2\leq\lambda_{f}(p)\leq 2.$ Hence, $g_{Q}(p)\geq 4a+4\geq 0$ as $-1\leq
a\leq 1.$ Here, we have written the value taken by
$\lambda_{f}(p)r^{*}_{\mathcal{Q}}(p)$ as $4a$. Thus, we have $g_{Q}(n)\geq 0$
for all square-free positive integers $n.$ Now, we see that

$\begin{split}S(f,\mathcal{Q};X)&=\sideset{}{{}^{\flat}}{\sum}_{n\leq
X\atop\gcd(n,N)=1}\lambda_{f}(n)r^{*}_{\mathcal{Q}}(n)=\sideset{}{{}^{\flat}}{\sum}_{n\leq
X\atop\gcd(n,N)=1}\sum_{d\mid n}g_{Q}(d)h_{Y}(n/d)r^{*}_{\mathcal{Q}}(n/d)\\\
&=\sideset{}{{}^{\flat}}{\sum}_{d\leq
X\atop\gcd(d,N)=1}g_{Q}(d)\sideset{}{{}^{\flat}}{\sum}_{m\leq
X/d\atop\gcd(m,N)=1}h_{Y}(m)r^{*}_{\mathcal{Q}}(m)\geq\sum_{n\leq
X\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)\end{split}$

as $g_{Q}(1)=1$ and $g_{Q}(n)\geq 0$ for each square-free positive integer
$n.$ Hence, a positive lower bound for the sum $S(f,\mathcal{Q};X)$ occurs and
it is given by the sum $\displaystyle{\sum_{n\leq
X^{u_{0}}\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)}$ for some $u_{0}<1$
given in Proposition 2.4.

Proof of Theorem 1.2: Let $X=Y^{u}$ with $u>1$. By definition,
$n_{f,\mathcal{Q}}$ be the largest integer among all $n\in\mathbb{N}$ such
that $\lambda_{f}(n)\geq 0,$ with $\gcd(n,N)=1$ and
$n=\mathcal{Q}(\underline{x})$ for some $\underline{x}\in\mathbb{Z}^{2}$. Let
us write $n_{f,\mathcal{Q}}=Y.$ In other word, $\lambda_{f}(n)\geq 0,$ for
each $n\leq Y$ with $\gcd(n,N)=1$ and $n=\mathcal{Q}(\underline{x})$ for some
$\underline{x}\in\mathbb{Z}^{2}.$ A key idea to estimate $Y$ is to compare
lower and upper bound for the sum

$\begin{split}S(f,\mathcal{Q};Y^{u})&=\sideset{}{{}^{\flat}}{\sum}_{n=\mathcal{Q}(\underline{x})\leq
Y^{u}\atop\gcd(n,N)=1}\lambda_{f}(n)=\sideset{}{{}^{\flat}}{\sum}_{n\leq
Y^{u}\atop\gcd(n,N)=1}\lambda_{f}(n)r_{Q}(n).\\\ \end{split}$

From Proposition 1.1 and (33), we have (for $u\leq u_{0}$)

$\begin{split}0<\frac{P(1)L(1,\chi_{D})^{2}}{\Gamma(\alpha_{0})}Y^{u}\log
Y^{u}\ll\sideset{}{{}^{\flat}}{\sum}_{n\leq
Y^{u}\atop\gcd(n,N)=1}h_{Y}(n)r^{*}_{\mathcal{Q}}(n)\leq
S(f,\mathcal{Q};Y^{u})\ll{(Nk^{2}|D|)}^{\frac{1}{2}+\epsilon}Y^{\frac{u}{2}+\epsilon}.\end{split}$

This shows that

$\begin{split}Y^{u/2+\epsilon}\ll{(Nk^{2}|D|)}^{\frac{1}{2}+\epsilon}L(1,\chi_{D})^{2}\qquad\Longrightarrow\qquad
Y\ll{(Nk^{2})}^{\frac{1}{u}+\epsilon}|D|^{\frac{2}{u}+\epsilon}\end{split}$

Now, we substitute $u=u_{0}=4/3$ (as $u_{0}=4/3$ such that $\sigma(u_{0})>0$)
to get

$Y\ll{(Nk^{2}|D|^{2})}^{\frac{3}{4}+\epsilon}.$

This completes the proof.

Data availability statements: Data sharing is not applicable to this article
as no datasets were generated or analyzed.

## References

  * [1] R. Acharya, A twist of the Gauss circle problem by holomorphic cusp forms, Res. number theory 8, 5 (2022).
  * [2] V. Blomer, Sum of Hecke eigenvalues over values of quadratic polynomials, Int. Math. Res. Not. IMRN (2008).
  * [3] D. A. Buell, Binary Quadratic Forms: Classical Theory and Modern Computations, springer - Verlag, New york, 1989.
  * [4] D. A. Cox, Primes of the form $x^{2}+ny^{2}$: Fermat, Class Field Theory, and Complex Multiplication, Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts 119, John Wiley & Sons, 2014.
  * [5] P. Deligne, La conjecture de Weil I. Inst. Hautes Etudes Sci. Publ. Math. 43, (1974), 273–307 .
  * [6] Y. Jiang and Guangshi Lu, Sum of coefficients of $L$\- functions and applications, J. Number Theory, 171 (2017), 56–70.
  * [7] H. Iwaniec, W. Kohnen and J. Sengupta, The first negative Hecke eigenvalue, Int. J. Number Theory 3 (2007), 355–363.
  * [8] H. Iwaniec, Topics in Classical Automorphic Forms, Grad. Stud. Math., vol. 17, American Mathematical Society, Providence, RI, 1997.
  * [9] H. Iwaniec and E. Kowalski, Analytic Number Theory, Amer. Math. Soc. Colloq. Publ., vol. 53, American Mathematical Society, Providence, RI, 2004.
  * [10] W. Kohnen and J. Sengupta, On the first sign change of Hecke eigenvalues of newforms. Math. Z. 254 (1) (2006), 173–184.
  * [11] E. Kowalski, Y.-K. Lau, K. Soundararajan and J. Wu. On modular signs, Math. Proc. Camb. Phil. Soc. 149 (3) (2010), 389–411.
  * [12] Y.-K. LAU, J.-Y. LIU and J. WU. The first negative coefficient of symmetric square $L$-functions. Ramanujan J 27(2012), 419–441
  * [13] Mathematica software, version 12.1. https://www.wolfram.com/mathematica/
  * [14] Matom$\ddot{\rm a}$ki, On signs of Fourier coefficients of cusp forms, Math. Proc. Camb. Phil. Soc. 152 (2), 2012, 207–222.
  * [15] M.K. Pandey and P. Tiwari, On the first sign change of Fourier coefficients of cusp forms at sum of two squares, Res. Number Theory (2021).
  * [16] M.K. Pandey and Lalit Vaishya, Asymptotic of Fourier coefficients of Hecke eigenforms at integers represented by binary quadratic form of fixed discriminant, (to appear) Publ. Math. Debrecen (2023).
  * [17] A. Perelli, General $L$-functions, Ann. Mat. Pura. Appl., 130(4), 1982, 287-306.
  * [18] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge Stud. Adv. Math., vol. 163, Cambridge University Press, Cambridge, 2015.
  * [19] Lalit Vaishya, Signs of Fourier coefficients of cusp forms at integers represented by an integral binary quadratic form, Proc. Indian Acad. Sci.( Math. Sci.), Vol 131, No. 41 (2021).
  * [20] Lalit Vaishya, Average estimates and sign change of Fourier coefficients of Hecke eigenforms at integers represented by binary quadratic forms of fixed discriminant, Submitted (2021).
  * [21] Asif Zaman, Primes represented by positive definite binary quadratic forms, The Quarterly Journal of Mathematics, vol. 69, Issue 4 (2018), 1353-–1386


# Correlation measures of binary sequences derived from Euler quotients

Huaning Liu1, Zhixiong Chen2, Chenhuang Wu2
1\. Research Center for Number Theory and Its Applications,
School of Mathematics, Northwest University,
Xi’an 710127, Shaanxi, P. R. China
2\. Provincial Key Laboratory of Applied Mathematics,
Putian University, Putian 351100, Fujian, P. R. China

###### Abstract

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 using
the 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. Euler quotient, binary sequence, correlation measure, character sum

##  1 Introduction

Let $\mathcal{S}=(s_{0},s_{1},...)$ be a binary sequence over
$\mathbb{F}_{2}=\\{0,1\\}$ and $k$ a positive integer. Mauduit and Sárközy
[16] introduced the _( $N$-th) correlation measure of order $k$_ for the first
$N$ terms of $\mathcal{S}$, which is defined as

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

where the maximum is taken over all $U\leq N-k+1$ and
$D=(d_{1},d_{2},\ldots,d_{k})$ with integers $0\leq
d_{1}<d_{2}<\ldots<d_{k}\leq N-U$.

From the viewpoint of cryptography, it is excepted that the $N$-th correlation
measure of order $k$ of sequences is as “small” (in terms of $N$, in
particular, is $o(N)$ as $N\rightarrow\infty$) as possible. It was shown in
[4] that for a “truely” random sequence $\mathcal{S}$, $C_{k}(\mathcal{S},N)$
(for some fixed $k$) is around $N^{1/2}$ with “near 1” probability.

Additionally, if $\mathcal{S}$ is $T$-periodic (in this case, we will denote
$\mathcal{S}$ as $\mathcal{S}=(s_{0},s_{1},\ldots,s_{T-1})$), we use the
following definition for the _periodic correlation measure of order $k$_ of
$\mathcal{S}$,

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

where $D=(d_{1},\ldots,d_{k})$, with $0\leq d_{1}<d_{2}<\ldots<d_{k}<T$. It is
clear that $\theta_{2}(\mathcal{S})$ is the (classic) auto-correlation of
$\mathcal{S}$.

In this work, we mainly consider the periodic correlation measure of order $k$
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 the
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
$\displaystyle\mathbf{\overline{s}}=\left(\overline{s}_{0},\overline{s}_{1},\cdots,\overline{s}_{p^{2}-1}\right)$
by

$\displaystyle\overline{s}_{t}=\left\\{\begin{array}[]{ll}\displaystyle
0,&\hbox{if \ }0\leq\frac{Q_{p}(t)}{p}<\frac{1}{2},\\\ \displaystyle
1,&\hbox{if \ }\frac{1}{2}\leq\frac{Q_{p}(t)}{p}<1.\end{array}\right.$

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

$\displaystyle Q_{m}(n_{1}n_{2})\equiv Q_{m}(n_{1})+Q_{m}(n_{2})\ (\bmod\
m)\quad\hbox{for}\quad\gcd(n_{1}n_{2},m)=1,$ (2)

and

$\displaystyle Q_{m}(n+cm)\equiv Q_{m}(n)+cn^{-1}\phi(m)\ (\bmod\
m)\quad\hbox{for}\quad\gcd(n,m)=1.$ (3)

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
$\displaystyle\mathbf{\widetilde{s}}=\left(\widetilde{s}_{0},\widetilde{s}_{1},\cdots,\widetilde{s}_{p^{\tau+1}-1}\right)$
is defined by

$\displaystyle\widetilde{s}_{t}=\left\\{\begin{array}[]{ll}\displaystyle
0,&\hbox{if \ }0\leq\frac{Q_{p^{\tau}}(t)}{p^{\tau}}<\frac{1}{2},\\\
\displaystyle 1,&\hbox{if \
}\frac{1}{2}\leq\frac{Q_{p^{\tau}}(t)}{p^{\tau}}<1.\end{array}\right.$ (6)

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

Moreover, let $m=pq$ be a product of two distinct odd primes $p$ and $q$ with
$p\mid(q-1)$, the $pq^{2}$-periodic sequence
$\displaystyle\mathbf{\widehat{s}}=\left(\widehat{s}_{0},\widehat{s}_{1},\cdots,\widehat{s}_{pq^{2}-1}\right)$
is defined by

$\displaystyle\widehat{s}_{t}=\left\\{\begin{array}[]{ll}\displaystyle
0,&\hbox{if \ }0\leq\frac{Q_{pq}(t)}{pq}<\frac{1}{2},\\\ \displaystyle
1,&\hbox{if \ }\frac{1}{2}\leq\frac{Q_{pq}(t)}{pq}<1.\end{array}\right.$ (9)

Very recently the minimal polynomials and linear complexities were determined
in [22] for $\mathbf{\widehat{s}}$, and the trace representation of
$\mathbf{\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
$\mathbf{\widetilde{s}}$ and $\mathbf{\widehat{s}}$ by using the approach
based on Dirichlet characters, Ramanujan sums and Gauss sums. We state below
the main result.

######  Theorem 1.

Let $m\geq 2$ be an odd number. Suppose that $Q_{m}(n)$ is $km$-periodic with
$k>3$ and $k\mid m$. Define the $km$-periodic sequence
$\displaystyle\mathbf{s}=\left(s_{0},s_{1},\cdots,s_{km-1}\right)\in\\{0,1\\}^{km}$
by

$\displaystyle s_{t}=\left\\{\begin{array}[]{ll}\displaystyle 0,&\hbox{if \
}0\leq\frac{Q_{m}(t)}{m}<\frac{1}{2},\\\ \displaystyle 1,&\hbox{if \
}\frac{1}{2}\leq\frac{Q_{m}(t)}{m}<1.\end{array}\right.$ (12)

Then we have

$\sum_{t=0}^{km-1}(-1)^{s_{t}+s_{t+m}+s_{t+2m}+s_{t+3m}}=km-\frac{2}{3}k\phi(m)+O\left(\phi(m)\phi(k)^{-1}k^{\frac{3}{2}}(\log
m)^{4}\right).$

Taking special values of $m$ and $k$ in Theorem 1, we immediately get the
correlation measures of $\mathbf{\widetilde{s}}$ and $\mathbf{\widehat{s}}$.

######  Corollary 1.

Let $p>2$ be a prime and let $\tau\geq 1$ be a fixed integer. Let the
$p^{\tau+1}$-periodic sequence
$\displaystyle\mathbf{\widetilde{s}}=\left(\widetilde{s}_{0},\widetilde{s}_{1},\cdots,\widetilde{s}_{p^{\tau+1}-1}\right)$
be defined as in $(\ref{Sequence-Eulerquotients-1})$. Then we have

$\sum_{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}}}=\frac{1}{3}p^{\tau+1}+O\left(p^{\tau+\frac{1}{2}}(\log
p^{\tau})^{4}\right).$

######  Corollary 2.

Let $p$ and $q$ be two distinct odd primes with $p\mid(q-1)$, and let the
$pq^{2}$-periodic sequence
$\displaystyle\mathbf{\widehat{s}}=\left(\widehat{s}_{0},\widehat{s}_{1},\cdots,\widehat{s}_{pq^{2}-1}\right)$
be defined as in $(\ref{Sequence-Eulerquotients-2})$. Then we have

$\sum_{t=0}^{pq^{2}-1}(-1)^{\widehat{s}_{t}+\widehat{s}_{t+pq}+\widehat{s}_{t+2pq}+\widehat{s}_{t+3pq}}=\frac{1}{3}pq^{2}+\frac{2}{3}q^{2}+O\left(pq^{\frac{3}{2}}(\log
pq)^{4}\right).$

Our results indicate that the correlation measures of order $4$ of
$\displaystyle\mathbf{\widetilde{s}}$ and $\displaystyle\mathbf{\widehat{s}}$
are very large. Therefore these sequences may not be suggested for
cryptography.

To prove Theorem 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 Sect. 2. We express $(-1)^{s_{t}}$ in terms of character
sums in Sect. 3 to finish the proof of Theorem 1 by using the results showed
in Sect. 2.

##  2 Dirichlet characters and Gauss sums

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

$c_{N}(n)=\mathop{\sum_{t=0}^{N-1}}_{\gcd(t,N)=1}e_{N}(tn),$

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

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

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

If the function $\chi$ satisfies the following conditions:

(i). $\chi(n_{1}n_{2})=\chi(n_{1})\chi(n_{2})$ for all integers $n_{1}$,
$n_{2}$,

(ii). $\chi(n+N)=\chi(n)$ for all integers $n$,

(iii). $\chi(n)=0$ for $\gcd(n,N)>1$,
then $\chi$ is one of the Dirichlet characters modulo $N$. When $\chi(n)=1$
for all $n$ with $\gcd(n,N)=1$ we say $\chi$ is the trivial character modulo
$N$. The integer $d$ 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_{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

$\displaystyle
G(n,\chi)=\left\\{\begin{array}[]{l}\left(\chi^{*}\right)^{-1}\left(\frac{n}{\gcd(n,N)}\right)\chi^{*}\left(\frac{N}{N^{*}\gcd(n,N)}\right)\mu\left(\frac{N}{N^{*}\gcd(n,N)}\right)\\\
\quad\times\phi(N)\phi^{-1}\left(\frac{N}{\gcd(n,N)}\right)G(1,\chi^{*}),\qquad\hbox{if
\ }N^{*}=\frac{N_{1}}{\gcd(n,N_{1})},\\\
0,\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\hbox{if \
}N^{*}\neq\frac{N_{1}}{\gcd(n,N_{1})}.\end{array}\right.$ (17)

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 1.

Let $m\geq 2$ be an odd number and let $k>3$ be an integer with $k\mid m$. Let
$\chi$ be a Dirichlet character modulo $km$ with $\chi^{m}$ being trivial. For
integers $a_{1}$, $a_{2}$, $a_{3}$ and $a_{4}$ we have

$\displaystyle\sum_{t=0}^{km-1}\chi\left(t^{a_{1}}(t+m)^{a_{2}}(t+2m)^{a_{3}}(t+3m)^{a_{4}}\right)$
$\displaystyle=\left\\{\begin{array}[]{ll}\displaystyle k\phi(m),&\hbox{if \
}m\mid(a_{1}+a_{2}+a_{3}+a_{4})\hbox{ \ and \ }k\mid(a_{2}+2a_{3}+3a_{4}),\\\
\displaystyle
O\left(\phi(m)\phi(k)^{-1}k^{\frac{3}{2}}\right),&\hbox{otherwise}.\end{array}\right.$

###### Proof.

By the properties of residue systems we get

$\displaystyle\sum_{t=0}^{km-1}\chi\left(t^{a_{1}}(t+m)^{a_{2}}(t+2m)^{a_{3}}(t+3m)^{a_{4}}\right)$
$\displaystyle=\mathop{\sum_{y=0}^{m-1}}_{\gcd(y,m)=1}\sum_{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)$
$\displaystyle=\mathop{\sum_{y=0}^{m-1}}_{\gcd(y,m)=1}\sum_{z=0}^{k-1}\chi\left((y^{a_{1}}+a_{1}y^{a_{1}-1}zm)(y^{a_{2}}+a_{2}y^{a_{2}-1}(z+1)m)\right)$
$\displaystyle\qquad\times\chi\left((y^{a_{3}}+a_{3}y^{a_{3}-1}(z+2)m)(y^{a_{4}}+a_{4}y^{a_{4}-1}(z+3)m)\right)$
$\displaystyle=\mathop{\sum_{y=0}^{m-1}}_{\gcd(y,m)=1}\chi\left(y^{a_{1}+a_{2}+a_{3}+a_{4}}\right)$
$\displaystyle\qquad\times\sum_{z=0}^{k-1}\chi\left((1+a_{1}y^{-1}zm)(1+a_{2}y^{-1}(z+1)m)(1+a_{3}y^{-1}(z+2)m)(1+a_{4}y^{-1}(z+3)m)\right).$

Clearly $\chi\left(1+nm\right)$ is a primitive additive character modulo $k$,
so there is uniquely an integer $\beta$ such that $1\leq\beta\leq k$,
$\gcd(\beta,k)=1$ and $\chi\left(1+nm\right)=e_{k}(\beta n)$. Hence,

$\displaystyle\sum_{t=0}^{km-1}\chi\left(t^{a_{1}}(t+m)^{a_{2}}(t+2m)^{a_{3}}(t+3m)^{a_{4}}\right)$
$\displaystyle=\mathop{\sum_{y=0}^{m-1}}_{\gcd(y,m)=1}\chi\left(y^{a_{1}+a_{2}+a_{3}+a_{4}}\right)$
$\displaystyle\qquad\times\sum_{z=0}^{k-1}e_{k}\left(\beta(a_{1}y^{-1}z+a_{2}y^{-1}(z+1)+a_{3}y^{-1}(z+2)+a_{4}y^{-1}(z+3))\right)$
$\displaystyle=\left\\{\begin{array}[]{ll}\displaystyle
k\mathop{\sum_{y=0}^{m-1}}_{\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\right),&\hbox{if
\ }k\mid(a_{1}+a_{2}+a_{3}+a_{4}),\\\ \displaystyle 0,&\hbox{if \
}k\nmid(a_{1}+a_{2}+a_{3}+a_{4}).\end{array}\right.$

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 from (13), (17) and the
properties of Ramanujan sums and Gauss sums we get

$\displaystyle\sum_{t=0}^{km-1}\chi\left(t^{a_{1}}(t+m)^{a_{2}}(t+2m)^{a_{3}}(t+3m)^{a_{4}}\right)$
$\displaystyle=\left\\{\begin{array}[]{ll}\displaystyle k\phi(m),&\hbox{if \
}m\mid(a_{1}+a_{2}+a_{3}+a_{4})\hbox{ \ and \ }k\mid(a_{2}+2a_{3}+3a_{4}),\\\
\displaystyle
O\left(\phi(m)\phi(k)^{-1}k^{\frac{3}{2}}\right),&\hbox{otherwise}.\end{array}\right.$

∎

######  Lemma 2.

Let $m\geq 2$ be an odd number and let $k>3$ be an integer with $k\mid m$.
Define

$\displaystyle\Xi_{m,k}$ $\displaystyle:=$
$\displaystyle\mathop{\mathop{\sum_{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_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{1}l_{1}\right)\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{2}l_{2}\right)$
$\displaystyle\times\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right).$

Then we have

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

###### Proof.

For absolute constant $c>0$ we get

$\displaystyle\sum_{ck\leq|a_{1}|\leq\frac{m-1}{2}}\mathop{\sum_{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_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{1}l_{1}\right)\right|\cdot\left|\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{2}l_{2}\right)\right|$
$\displaystyle\qquad\times\left|\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\right|\cdot\left|\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)\right|$
$\displaystyle\ll\sum_{1\leq|a_{2}|\leq\frac{m-1}{2}}\frac{m}{|a_{2}|}\sum_{1\leq|a_{3}|\leq\frac{m-1}{2}}\frac{m}{|a_{3}|}\sum_{1\leq|a_{4}|\leq\frac{m-1}{2}}\frac{m}{|a_{4}|}\mathop{\sum_{ck\leq|a_{1}|\leq\frac{m-1}{2}}}_{a_{1}+a_{2}+a_{3}+a_{4}\equiv
0\ (\bmod m)}\frac{m}{k}$ $\displaystyle\ll\frac{m^{4}(\log m)^{3}}{k}.$

Hence,

$\displaystyle\Xi_{m,k}$ $\displaystyle:=$
$\displaystyle\sum_{1\leq|a_{1}|,|a_{2}|\leq\frac{5k}{32}}\mathop{\mathop{\sum_{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_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{1}l_{1}\right)\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{2}l_{2}\right)$
$\displaystyle\times\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)+O\left(\frac{m^{4}(\log
m)^{3}}{k}\right)$ $\displaystyle=$
$\displaystyle\sum_{1\leq|a_{1}|,|a_{2}|\leq\frac{5k}{32}}~{}~{}\mathop{\mathop{\sum_{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_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{1}l_{1}\right)\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{2}l_{2}\right)$
$\displaystyle\times\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)+O\left(\frac{m^{4}(\log
m)^{3}}{k}\right)$ $\displaystyle=$
$\displaystyle\sum_{1\leq|a_{3}|,|a_{4}|\leq\frac{k}{32}}~{}~{}\sum_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-(a_{3}+2a_{4})l_{1}\right)\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left((2a_{3}+3a_{4})l_{2}\right)$
$\displaystyle\times\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)+O\left(\frac{m^{4}(\log
m)^{3}}{k}\right).$

It is not hard to show that

$\displaystyle\sum_{\frac{k}{32}<|a_{3}|\leq\frac{m-1}{2}}~{}~{}\sum_{1\leq|a_{4}|\leq\frac{k}{32}}~{}~{}\sum_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-(a_{3}+2a_{4})l_{1}\right)\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left((2a_{3}+3a_{4})l_{2}\right)$
$\displaystyle\qquad\times\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)$
$\displaystyle\ll\sum_{\frac{k}{32}<|a_{3}|\leq\frac{m-1}{2}}~{}~{}\sum_{1\leq|a_{4}|\leq\frac{k}{32}}m\cdot\left|\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left((2a_{3}+3a_{4})l_{2}\right)\right|\cdot\frac{m}{k}\cdot\frac{m}{|a_{4}|}$
$\displaystyle\ll\frac{m^{3}}{k}\sum_{1\leq|a_{4}|\leq\frac{k}{32}}\frac{1}{|a_{4}|}\sum_{\frac{k}{32}<|a_{3}|\leq\frac{m-1}{2}}\left|\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left((2a_{3}+3a_{4})l_{2}\right)\right|$
$\displaystyle\ll\frac{m^{4}(\log m)^{2}}{k}.$

Therefore

$\displaystyle\Xi_{m,k}$ $\displaystyle=$
$\displaystyle\sum_{1\leq|a_{3}|,|a_{4}|\leq\frac{m-1}{2}}~{}~{}\sum_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-(a_{3}+2a_{4})l_{1}\right)\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left((2a_{3}+3a_{4})l_{2}\right)$
(21)
$\displaystyle\quad\times\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)+O\left(\frac{m^{4}(\log
m)^{3}}{k}\right)$ $\displaystyle=$ $\displaystyle\sum_{\frac{m+1}{2}\leq
l_{1},l_{2},l_{3},l_{4}\leq
m-1}~{}~{}\sum_{1\leq|a_{3}|\leq\frac{m-1}{2}}e_{m}\left((-l_{1}+2l_{2}-l_{3})a_{3}\right)$
$\displaystyle\quad\times\sum_{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)$ $\displaystyle=$ $\displaystyle\sum_{\frac{m+1}{2}\leq
l_{1},l_{2},l_{3},l_{4}\leq
m-1}~{}~{}\sum_{|a_{3}|\leq\frac{m-1}{2}}e_{m}\left((-l_{1}+2l_{2}-l_{3})a_{3}\right)$
$\displaystyle\quad\times\sum_{|a_{4}|\leq\frac{m-1}{2}}e_{m}\left((-2l_{1}+3l_{2}-l_{4})a_{4}\right)$
$\displaystyle-\sum_{\frac{m+1}{2}\leq l_{1},l_{2},l_{3},l_{4}\leq
m-1}~{}~{}\sum_{|a_{3}|\leq\frac{m-1}{2}}e_{m}\left((-l_{1}+2l_{2}-l_{3})a_{3}\right)$
$\displaystyle-\sum_{\frac{m+1}{2}\leq l_{1},l_{2},l_{3},l_{4}\leq
m-1}~{}~{}\sum_{|a_{4}|\leq\frac{m-1}{2}}e_{m}\left((-2l_{1}+3l_{2}-l_{4})a_{4}\right)$
$\displaystyle+\sum_{\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)$ $\displaystyle=$
$\displaystyle m^{2}\mathop{\mathop{\sum_{\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_{\frac{m+1}{2}\leq l_{1},l_{2},l_{3}\leq
m-1}}_{2l_{2}\equiv l_{1}+l_{3}(\bmod m)}1$
$\displaystyle-\frac{m(m-1)}{2}\mathop{\sum_{\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}$ $\displaystyle+O\left(\frac{m^{4}(\log
m)^{3}}{k}\right).$

By using the idea of Lemma 2.2 of [15] we have

$\displaystyle\mathop{\sum_{\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^{2}}{8}+O(m),$ (22)
$\displaystyle\mathop{\sum_{\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^{2}}{8}+O(m)$ (23)

and

$\displaystyle\mathop{\mathop{\sum_{\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^{2}}{12}+O(m).$ (24)

Combining (21)-(24) we immediately get

$\displaystyle\Xi_{m,k}$ $\displaystyle=$ $\displaystyle
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}$
$\displaystyle+O\left(\frac{m^{4}(\log m)^{3}}{k}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{48}m^{4}+O\left(\frac{m^{4}(\log m)^{3}}{k}\right).$

This completes the proof of Lemma 2. ∎

##  3 Correlation measures of order $4$

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

$s_{t}=\frac{1}{m}\sum_{|a|\leq\frac{m-1}{2}}\sum_{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_{1\leq|a|\leq\frac{m-1}{2}}\sum_{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),&\hbox{if
\ }\gcd(n,m)=1,\\\ 0,&\hbox{if \ }\gcd(n,m)>1.\end{array}\right.$

Clearly $\chi_{km}(n+km)=\chi_{km}(n)$, and by (2) we have
$\chi_{km}(n_{1}n_{2})=\chi_{km}(n_{1})\chi_{km}(n_{2})$. Then $\chi_{km}(n)$
is a Dirichlet character modulo $km$ with $\chi_{km}^{m}$ being trivial.
Therefore

$\displaystyle(-1)^{s_{t}}=-\frac{2}{m}\sum_{1\leq|a|\leq\frac{m-1}{2}}\sum_{l=\frac{m+1}{2}}^{m-1}e_{m}\left(-al\right)\chi_{km}\left(t^{a}\right)+\frac{1}{m}.$
(25)

By (25), Lemmas 1 and 2 we get

$\displaystyle\sum_{t=0}^{km-1}(-1)^{s_{t}+s_{t+m}+s_{t+2m}+s_{t+3m}}$ (26)
$\displaystyle=\mathop{\sum_{t=0}^{km-1}}_{\gcd(t,m)=1}(-1)^{s_{t}+s_{t+m}+s_{t+2m}+s_{t+3m}}+\mathop{\sum_{t=0}^{km-1}}_{\gcd(t,m)>1}1$
$\displaystyle=\frac{2^{4}}{m^{4}}\sum_{1\leq|a_{1}|\leq\frac{m-1}{2}}~{}~{}\sum_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{1}l_{1}\right)\sum_{1\leq|a_{2}|\leq\frac{m-1}{2}}~{}~{}\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{2}l_{2}\right)$
$\displaystyle\qquad\times\sum_{1\leq|a_{3}|\leq\frac{m-1}{2}}~{}~{}\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{1\leq|a_{4}|\leq\frac{m-1}{2}}~{}~{}\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)$
$\displaystyle\qquad\times\sum_{t=0}^{km-1}\chi_{km}\left(t^{a_{1}}(t+m)^{a_{2}}(t+2m)^{a_{3}}(t+3m)^{a_{4}}\right)$
$\displaystyle\qquad+\mathop{\sum_{t=0}^{km-1}}_{\gcd(t,m)>1}1+O\left(k(\log
m)^{3}\right)$
$\displaystyle=\frac{2^{4}k\phi(m)}{m^{4}}\mathop{\mathop{\sum_{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_{l_{1}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{1}l_{1}\right)\sum_{l_{2}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{2}l_{2}\right)$
$\displaystyle\qquad\times\sum_{l_{3}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{3}l_{3}\right)\sum_{l_{4}=\frac{m+1}{2}}^{m-1}e_{m}\left(-a_{4}l_{4}\right)$
$\displaystyle\qquad+k(m-\phi(m))+O\left(\phi(m)\phi(k)^{-1}k^{\frac{3}{2}}(\log
m)^{4}\right)+O\left(k(\log m)^{3}\right)$
$\displaystyle=km-\frac{2}{3}k\phi(m)+O\left(\phi(m)\phi(k)^{-1}k^{\frac{3}{2}}(\log
m)^{4}\right).$

This proves Theorem 1.

##  4 Final remarks

In this work, we have claimed that two families of binary sequences (see (6)
and (9)) 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 $k$ equals to the period, see [9]. Such problem
may be related to their linear complexity.

Acknowledgements. 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 National Natural Science
Foundation of China under grant No. 61772292, by the Provincial Natural
Science Foundation of Fujian under grant No. 2020J01905 and by the Program for
Innovative Research Team in Science and Technology in Fujian Province
University under grant No. 2018-49.

## References

  * [1] T. Agoh, K. Dilcher and L. Skula, Fermat quotients for composite moduli, Journal of Number Theory,  66 (1997): pp. 29–50.
  * [2] H. Aly and A. Winterhof, Boolean functions derived from Fermat quotients, Cryptography and Communications,  3 (2011): pp. 165–174.
  * [3] T. M. Apostol, Introduction to analytic number theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1976.
  * [4] J. Cassaigne, C. Mauduit and A. Sárközy, On finite pseudorandom binary sequences, VII: The measures of pseudorandomness, Acta Arithmetica,  103 (2002), pp. 97–118.
  * [5] M. C. Chang, Short character sums with Fermat quotients, Acta Arithmetica,  152 (2012): pp. 23–38.
  * [6] Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Science China Information Sciences,  57 (2014), 112109, 10 pp.
  * [7] Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Designs, Codes and Cryptography,  67 (2013): pp. 317–323.
  * [8] Z. Chen, X. Du and R. Marzouk, Trace representation of pseudorandom binary sequences derived from Euler quotients, Applicable Algebra in Engineering, Communication and Computing,  26 (2015): pp. 555–570.
  * [9] Z. Chen, A. Gómez, D. Gómez-Pérez and A. Tirkel, Correlation, linear complexity, maximum order complexity on families of binary sequences. CoRR abs/2107.11840 (2021)
  * [10] Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Communications,  9 (2012): pp. 105–108.
  * [11] Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, in ”Arithmetic of finite fields”, Lecture Notes in Computer Science 6087, Springer, Berlin, 2010, 73–85.
  * [12] Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM Journal on Discrete Mathematics,  28 (2014): pp. 1–7.
  * [13] X. Du, Z. Chen and L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Information Processing Letters,  112 (2012), pp. 604–609.
  * [14] D. Gómez-Pérez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Periodica Mathematica Hungarica,  64 (2012): pp. 161–168.
  * [15] H. Liu and X. Liu, On the correlation measures of orders $3$ and $4$ of binary sequence of period $p^{2}$ derived from Fermat quotients, Advances in Mathematics of Communications,  doi: 10.3934/amc.2021008.
  * [16] C. Mauduit and A. Sárközy, On finite pseudorandom binary sequencs I: measure of pseudorandomness, the Legendre symbol, Acta Arithmetica,  82 (1997), pp. 365–377.
  * [17] A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM Journal on Discrete Mathematics,  25 (2011): pp. 50–71.
  * [18] C. Pan and C. Pan, Goldbach conjecture. Science Press Beijing, Beijing, 1992.
  * [19] I. E. Shparlinski, Fermat quotients: exponential sums, value set and primitive roots, Bulletin of the London Mathematical Society,  43 (2011): pp. 1228–1238.
  * [20] I. E. Shparlinski, Character sums with Fermat quotients, The Quarterly Journal of Mathematics,  62 (2011): pp. 1031–1043.
  * [21] I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bulletin of the Australian Mathematical Society,  83 (2011): pp. 456–462.
  * [22] J. Zhang, S. Gao and C. Zhao, Linear complexity of a family of binary $pq^{2}$-periodic sequences from Euler quotients, IEEE Transactions on Information Theory,  66 (2020): pp. 5774–5780.
  * [23] J. Zhang, C. Hu, X. Fan and C. Zhao, Trace representation of the binary $pq^{2}$-periodic sequences derived from Euler quotients, Cryptography and Communications,  13 (2021): pp. 343–359.


# GeoGCN: Geometric Dual-domain Graph Convolution Network for Point Cloud
Denoising

###### Abstract

We propose GeoGCN, a novel geometric dual-domain graph convolution network for
point cloud denoising (PCD). Beyond the traditional wisdom of PCD, to fully
exploit the geometric information of point clouds, we define two kinds of
surface normals, one is called Real Normal (RN), and the other is Virtual
Normal (VN). RN preserves the local details of noisy point clouds while VN
avoids the global shape shrinkage during denoising. GeoGCN is a new PCD
paradigm that, 1) first regresses point positions by spatial-based GCN with
the help of VNs, 2) then estimates initial RNs by performing Principal
Component Analysis on the regressed points, and 3) finally regresses fine RNs
by normal-based GCN. Unlike existing PCD methods, GeoGCN not only exploits two
kinds of geometry expertise (i.e., RN and VN) but also benefits from training
data. Experiments validate that GeoGCN outperforms SOTAs in terms of both
noise-robustness and local-and-global feature preservation.

Index Terms—  GeoGCN, Point cloud denoising, Surface normal, Deep learning,
Graph convolution network

##  1 Introduction

Point clouds have seen growing popularity with wide applications of autonomous
driving, and Metaverse in recent years [1]. They are often acquired by
advanced 3D sensors, where noise inevitably creeps in, due to measurement and
reconstruction errors. Noise reduces the accuracy of captured surfaces and
should be reduced before many geometric tasks.

Given a measurement $\textbf{P}^{\star}=(\textbf{P}+\varepsilon)$ with noise
$\varepsilon$, point cloud denoising (PCD) aims to recover a clean point cloud
P to represent the sampled underlying surface. Current PCD methods are roughly
divided into conventional methods and learning-based methods. The former may
exploit certain surface assumptions, like sparsity or non-local similarity, to
remove noise while attempting to preserve the surface’s geometry [2, 3, 4, 5].
However, they are time-consuming and require careful trial-and-error parameter
tuning. Recent years have witnessed extensive efforts in learning-based
methods [6, 7, 8]. They usually take a small patch reflecting the local
geometry as input to encode the geometric information and predict a
displacement for each point. Few learning-based PCD methods can benefit from
the global geometry to enhance the performance of denoising.

We propose a novel and effective PCD method that exploits geometry expertise
and benefit from training data. Our method is inspired by the following two
observations.

(1) The local geometry helps smooth the local noisy points while retaining
sharp features; the global geometry helps constrain the overall shape of noisy
point clouds. Thus, the two types of geometry are potentially combined to
complement each other to promote the PCD performance. Based on the
aforementioned analysis, we define two types of normals as surface geometry
signals: Real Normal (RN) and Virtual Normal (VN). RNs are locally estimated
and utilized to retain the local details, and VNs are globally estimated and
utilized to constrain the global shape.

(2) A point cloud with noise removed can more accurately estimate its surface
normals than its noisy version. Meanwhile, more accurate surface normals can
better remove noise than their raw surface normals. Thus, we design a cascaded
two-stream network that first regresses point coordinates and then point
normals, in which RNs and VNs are integrated. The regressed point coordinates
can be used to estimate the initial RNs by PCA. The regressed RNs can be used
to fit the new point coordinates to yield the final PCD result.

Our main contributions are as follows:
(1) We define two types of surface normals: RN is exploited to update the
vertex coordinates to optimize the local details of noisy point clouds, and VN
is used as a loss function to constrain the global shape of noisy point
clouds.
(2) We propose a novel point cloud denoising paradigm based on a dual-domain
graph convolutions, which learns the defined RNs and VNs from the spatial and
normal domains and synthesizes RNs and VNs to improve the PCD performance.

##  2 Method

Fig. 1: The pipeline of GeoGCN: The input of GeoGCN are patches of noisy
points. The S-GCN regresses the initial denoised patches. Then, PCA is
performed on the initial denoised patches to achieve initial RNs, which are
concatenated with the initial denoised points to feed into N-GCN. The N-GCN is
used to regress the fine RNs. The final denoising module generates the final
denoised point clouds.

###  2.1 Overview

Current network architectures seldom leverage geometry expertise. In our PCD
method, we exploit two kinds of geometry expertise. (1) We formulate RN and VN
representing the local and global geometry respectively and naturally
integrate them into Dynamic Graph Convolutional Neural Network (DGCNN) [9] to
enhance the denoising results. (2) We establish both the “point-to-normal” and
“normal-to-point” relationships. The two relationships make our method robust
to noise and faithful to the underlying noise-free surface.

GeoGCN consists of two parts (see Fig. 1): Spatial-domain Graph Convolution
Network (S-GCN) and Normal-domain Graph Convolution Network (N-GCN). First,
S-GCN takes a patch of the noisy point cloud as input to regress the initial
denoised patch. The defined VNs are utilized as the loss function to constrain
the shape of the point cloud. Then, we perform principal component analysis
(PCA) [10] on the initial denoised patches to achieve initial RNs. Finally, we
concatenate the initial denoised points and corresponding RNs and feed them to
N-GCN to generate the fine RNs. The fine RNs are utilized to update the vertex
coordinates of the initial denoised points to optimize the local details.

###  2.2 S-GCN

S-GCN is a sub-network in the spatial domain. We input a patch of the noisy
point cloud into S-GCN to regress the initial denoised patch. Through two loss
functions, we constrain the training process in both the global and local
geometry.

Virtual Normal. We formulate Virtual Normal (VN) as the global geometry of a
given point cloud. To this end, we construct a series of triangles by randomly
picking up three points in the point cloud, and consider the normals of these
triangles as the virtual normals (see Fig. 2). These VNs enable to preserve
the global shape during denoising.

Specifically, we randomly select N groups of three-points in the initial
denoised point cloud outputted by S-GCN. We take two restrictions to ensure
that VNs can well reflect the global geometry information of the point cloud.
First, three points in each group should not form a line. We control the three
angles of each triangle to avoid thin triangles. Thus, all three angles of any
triangle range within $[45^{\circ},90^{\circ}]$. Second, the edge length of
each triangle should be longer than a pre-fixed threshold, since a triangle
with short edge lengths is sensitive to noise.

Fig. 2: The schematic diagram of VN.

Loss. After selecting $N$ groups of three-points satisfying the restrictions,
we mark their indexes and find the corresponding points in the clean point
cloud. Virtual Normal Loss is formulated to constrain the global shape of a
point cloud as

$Loss_{\mathrm{VN}}=\frac{1}{N}\sum_{i=0}^{N}{\left.|n_{i}^{pred}-n_{i}^{gt}\right.|}$
(1)

where $n_{i}^{pred}$ is VNs from the initial denoised points, and $n_{i}^{gt}$
is VNs from the clean point cloud.

We also formulate Earth Mover Distance (EMD) [11] to regress coordinates in
S-GCN as

$Loss_{\mathrm{EMD}}=EMD\left(P,Q\right)=\frac{\sum_{i=1}^{m}\sum_{j=1}^{n}{f_{ij}d_{ij}}}{\sum_{i=1}^{m}\sum_{j=1}^{n}f_{ij}}$
(2)

where $P$ and $Q$ represent the initial denoised point cloud outputted by
S-GCN and the ground truth, respectively. $d_{ij}$ represents the distance
from the $i^{th}$ point of $P$ to the $j^{th}$ point of $Q$. $f_{ij}$
indicates whether to move the $i^{th}$ point of $P$ to the $j^{th}$ point of
$Q$. $EMD$ represents the total cost of moving all points in $P$ to all points
in $Q$.

###  2.3 N-GCN

N-GCN is a sub-network in the normal domain. We concatenate the initial
denoised points and corresponding RNs calculated by PCA, then feed them into
N-GCN to generate the fine RNs.

Real Normal. Principal Component Analysis (PCA) is employed to analyze the
covariance in a local structure around a noisy point. Real Normal is the
eigenvector corresponding to the smallest eigenvalue of the covariance. Such
normals can well reflect the local geometry of a point.

Loss. PCA normals are un-oriented, and obtaining a consistent normal
orientation requires additional effort. Our solution is to either add or
subtract the predicted RNs from the ground truth, in which the smaller value
is adopted. Such an operation ensures that the regressed RNs are closer to the
straight line with the ground truth. Thus, we formulate the $L_{2}$ loss in
N-GCN to regress RNs as

$Loss_{\mathrm{RN}}=\sum_{i=1}^{n}{min\left(\left(n_{i}^{gt}-n_{i}^{pred}\right)^{2},\left(n_{i}^{gt}+n_{i}^{pred}\right)^{2}\right)}$
(3)

where $n_{i}^{pred}$ represents RNs output by N-GCN and $n_{i}^{gt}$ is GT.

###  2.4 Total Loss

The total loss is formulated as

$Loss=\alpha Loss_{\mathrm{EMD}}+\left(1-\alpha\right)Loss_{\mathrm{VN}}+\beta
Loss_{\mathrm{RN}}$ (4)

where $\alpha$ and $\beta$ are the weights. We empirically set $\alpha$=0.9
and $\beta=0.1$ that behave well during denoising.

###  2.5 Final Denoising

To obtain more accurate point cloud denoising results, we utilize the
regressed RNs to fit the regressed points. The final denoising point is
generated by [12]

$p_{i}^{\prime}=p_{i}+\gamma\sum_{p_{j}\in
N_{i}}\left(p_{j}-p_{i}\right)\left(W_{\sigma}\left(n_{i},n_{j}\right)n_{i}^{T}n_{i}+\lambda
n_{j}^{T}n_{j}\right)$ (5)

where $p_{i}^{\prime}$ and $p_{i}$ are the point after and before denoising,
$N_{i}$ is the neighboring points of $p_{i}$.
$W_{\sigma}\left(n_{i},n_{j}\right)=\exp{\left(-\frac{\left.|n_{i}-n_{j}\right.|^{2}}{\sigma^{2}}\right)}$
is a weight function, $\lambda$=0.5, $\gamma=\frac{1}{3\left|N_{i}\right|}$ is
the step size, and the number of iterations is set to 10.

##  3 Results and Discussions

###  3.1 Dataset

The training dataset consists of 22 point cloud models with accurate
coordinates and normals, including 11 CAD models and 11 non-CAD models. Each
model contains 100k points randomly sampled from its original surface. We add
different scales of Gaussian noise to each model, with noise scales of 0.25%,
0.5%, 1%, and 1.5%, respectively. Thus, the training dataset consists of 88
point cloud models with noise, and 22 point cloud models with accurate
coordinates and normals.

The test dataset consists of both synthesized noisy models and real-scanned
models. For synthesized data, we add Gaussian noise at a scale of 0.5%. In
addition, we test 5 real scanned point clouds.

###  3.2 Training Details

Our GeoGCN is implemented by PyTorch. We train it on a PC equipped with an
Intel 12700F CPU and an NVIDIA RTX-1080Ti GPU. We utilize the SGD optimizer
with a batch size of 64. 8000 patches are selected in each model to feed into
GeoGCN, with 1000 points for each patch. We set the training epochs and
initial learning rate to be 10 and 1e-3 respectively. The learning rate
decreases from 1e-3 to 1e-6 when the epoch increases. It takes about 15 hours
to train our GeoGCN.

###  3.3 Quantitative Comparison

We compare the proposed GeoGCN with point cloud denoising methods including
the traditional ones, i.e., WLOP [13], CLOP [14], RIMLS [15], GPF [16], and
the learning-based ones, i.e., PCN [17], Pointfilter [18], and TD [19].

To comprehensively evaluate GeoGCN, we calculate the Chamfer distance (CD)
[20] and Mean Square Error (MSE) [21] over the test dataset. As illustrated in
Table 1, our method achieves the lowest average errors.

Table 1: The average errors of CD and MSE of all methods. Methods Metrics |  CD ($10^{-5}$) |  MSE ($10^{-3}$)
---|---|---
Noisy |  3.656 |  5.868
WLOP |  1.898 |  4.361
CLOP |  1.537 |  4.138
RIMLS |  1.242 |  4.173
GPF |  2.375 |  4.896
PCN |  1.027 |  4.075
PF |  0.997 |  3.986
TD |  1.576 |  4.443
Ours |  0.987 |  3.954
Fig. 3: Denoising a real-scanned point cloud scene.

###  3.4 Visual Comparison

We evaluate GeoGCN on raw scanned point clouds corrupted with raw noise. Since
the ground-truth models of these raw scanned point sets are not available, we
only demonstrate the visual comparisons with other methods but not with GT. As
shown in Fig. 3, we compare our method with WLOP [13], Pointfilter [18], TD
[19], and RePCD [22]. As observed from these results, the headrest of our
method is better than others. With the help of VNs and RNs, our method
recovers the local details of the model, while optimizing the global shape.

###  3.5 Ablation Study

We perform ablation study to validate the effectiveness of VNs for global
shape preservation and RNs for local shape preservation. GeoGCN is decomposed
into three parts:
(1) S1: Learning the mapping from the noisy point clouds to the initial
denoised points;
(2) S2: Adding Virtual Normal Loss;
(3) S3: Learning the mapping from the initial RNs to the fine RNs, and using
fine RNs to update the initial denoised points.

Fig. 4: Denoising performance of GeoGCN.

As illustrated in Table 2 and Fig. 4, the average errors and visualizations of
S1 are significantly better than that of the input, indicating that the
initial denoised points from the first sub-network S-GCN are effective.
Compared with S1, the average errors of S2 are smaller, indicating that VNs
can improve the performance of the proposed model by preserving global
geometric information. The average errors and visualizations of S3 are the
best, indicating that utilizing the fine RNs regressed by the second sub-
network N-GCN can effectively update the vertex coordinates of the initial
denoised points and recover the local details.

Table 2: The average errors of MSE ($10^{-3}$). |  CAD |  non-CAD
---|---|---
Input |  6.1111 |  6.3123
S1 |  4.5687 |  4.8653
S2 |  4.2851 |  4.5342
S3 |  3.8976 |  4.0462

##  4 Conclusion

Point cloud denoising is a fundamental yet not well-solved problem in 3D
vision and graphics. Few efforts have been made to both benefit from the
training data and absorb the geometric domain knowledge for point cloud
denoising. We propose to formulate two kinds of normals as surface geometric
signals, one is real normal to reflect the surface’s local geometry and the
other is virtual normal to reflect its global geometry. The two types of
normals are flexibly integrated into current GCN architectures. We consider
that a noise-free point cloud can more accurately estimate its surface normals
than its noisy version; more accurate surface normals can better remove noise
than their raw surface normals. Thus, we propose a cascaded two-stream network
that first regresses point coordinates in the spatial domain and then point
normals in the normal domain, in which RNs and VNs are integrated. Experiments
show clear improvements of our method over its competitors in terms of noise-
robustness and global-and-local shape preservation.

## References

  * [1] Ying Li, Lingfei Ma, Zilong Zhong, Fei Liu, Michael A Chapman, Dongpu Cao, and Jonathan Li,  “Deep learning for lidar point clouds in autonomous driving: A review,”  IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 8, pp. 3412–3432, 2020.
  * [2] Yaron Lipman, Daniel Cohen-Or, David Levin, and Hillel Tal-Ezer,  “Parameterization-free projection for geometry reconstruction,”  ACM Transactions on Graphics (TOG), vol. 26, no. 3, pp. 22–es, 2007\.
  * [3] Gaël Guennebaud and Markus Gross,  “Algebraic point set surfaces,”  in ACM siggraph 2007 papers, pp. 23–es. 2007.
  * [4] Chinthaka Dinesh, Gene Cheung, and Ivan V Bajić,  “Point cloud denoising via feature graph laplacian regularization,”  IEEE Transactions on Image Processing, vol. 29, pp. 4143–4158, 2020\.
  * [5] Honghua Chen, Mingqiang Wei, Yangxing Sun, Xingyu Xie, and Jun Wang,  “Multi-patch collaborative point cloud denoising via low-rank recovery with graph constraint,”  TVCG, vol. 26, no. 11, pp. 3255–3270, 2019.
  * [6] Riccardo Roveri, A Cengiz Öztireli, Ioana Pandele, and Markus Gross,  “Pointpronets: Consolidation of point clouds with convolutional neural networks,”  in Computer Graphics Forum, 2018, vol. 37, pp. 87–99.
  * [7] Lequan Yu, Xianzhi Li, Chi-Wing Fu, Daniel Cohen-Or, and Pheng-Ann Heng,  “Pu-net: Point cloud upsampling network,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 2790–2799.
  * [8] Lequan Yu, Xianzhi Li, Chi-Wing Fu, Daniel Cohen-Or, and Pheng-Ann Heng,  “Ec-net: an edge-aware point set consolidation network,”  in ECCV, 2018, pp. 386–402.
  * [9] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon,  “Dynamic graph cnn for learning on point clouds,”  Acm Transactions On Graphics (tog), vol. 38, no. 5, pp. 1–12, 2019\.
  * [10] Hervé Abdi and Lynne J Williams,  “Principal component analysis,”  Wiley interdisciplinary reviews: computational statistics, vol. 2, no. 4, pp. 433–459, 2010.
  * [11] Le Hou, Chen-Ping Yu, and Dimitris Samaras,  “Squared earth mover’s distance-based loss for training deep neural networks,”  arXiv preprint arXiv:1611.05916, 2016.
  * [12] Haoran Zhou, Honghua Chen, Yidan Feng, Qiong Wang, Jing Qin, Haoran Xie, Fu Lee Wang, Mingqiang Wei, and Jun Wang,  “Geometry and learning co-supported normal estimation for unstructured point cloud,”  in CVPR, 2020, pp. 13238–13247.
  * [13] Hui Huang, Dan Li, Hao Zhang, Uri Ascher, and Daniel Cohen-Or,  “Consolidation of unorganized point clouds for surface reconstruction,”  ACM Trans. Graph., vol. 28, no. 5, pp. 1–7, 2009.
  * [14] Reinhold Preiner, Oliver Mattausch, Murat Arikan, Renato Pajarola, and Michael Wimmer,  “Continuous projection for fast l1 reconstruction.,”  ACM Trans. Graph., vol. 33, no. 4, pp. 47–1, 2014.
  * [15] A Cengiz Öztireli, Gael Guennebaud, and Markus Gross,  “Feature preserving point set surfaces based on non-linear kernel regression,”  in Computer graphics forum, 2009, vol. 28, pp. 493–501.
  * [16] Xuequan Lu, Shihao Wu, Honghua Chen, Sai-Kit Yeung, Wenzhi Chen, and Matthias Zwicker,  “Gpf: Gmm-inspired feature-preserving point set filtering,”  TVCG, vol. 24, no. 8, pp. 2315–2326, 2017.
  * [17] Marie-Julie Rakotosaona, Vittorio La Barbera, Paul Guerrero, Niloy J Mitra, and Maks Ovsjanikov,  “Pointcleannet: Learning to denoise and remove outliers from dense point clouds,”  in Computer Graphics Forum, 2020, vol. 39, pp. 185–203.
  * [18] Dongbo Zhang, Xuequan Lu, Hong Qin, and Ying He,  “Pointfilter: Point cloud filtering via encoder-decoder modeling,”  TVCG, vol. 27, no. 3, pp. 2015–2027, 2020.
  * [19] Pedro Hermosilla, Tobias Ritschel, and Timo Ropinski,  “Total denoising: Unsupervised learning of 3d point cloud cleaning,”  in CVPR, 2019, pp. 52–60.
  * [20] M Akmal Butt and Petros Maragos,  “Optimum design of chamfer distance transforms,”  TIP, vol. 7, no. 10, pp. 1477–1484, 1998.
  * [21] David M Allen,  “Mean square error of prediction as a criterion for selecting variables,”  Technometrics, vol. 13, no. 3, pp. 469–475, 1971.
  * [22] Honghua Chen, Zeyong Wei, Xianzhi Li, Yabin Xu, Mingqiang Wei, and Jun Wang,  “Repcd-net: Feature-aware recurrent point cloud denoising network,”  IJCV, vol. 130, no. 3, pp. 615–629, 2022.