\section{Introduction}


Let $U=\{0\leq u_1<u_2<...<u_k<n \}$ be a subset of size $k\geq2$ of a circle ${\mathbb T}_n={\mathbb R}/n\mathbb{Z}$ or of a cyclic group $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$. Denote by $s_i=u_{i+1}-u_i\in{\mathbb R}^+$, $i=1,...,k-1$, the consecutive distances between elements of $U$, and write $s_k=u_1+n-u_k\in{\mathbb R}^+$. Following Arnold \cite[\S9]{Arn}, we define the stochasticity parameter $S(U)$ of the set $U$ by
$$S(U)=\sum_{i=1}^{k}s_i^2.
$$
While we study this parameter only in the discrete case of $\mathbb{Z}_n$, we would like to  focus for a moment on the continuous case of ${\mathbb T}_n$, which is useful for some heuritics in what follows. Since $\frac{n}{k} =\frac{1}{k}\sum_{i=1}^ks_i\leq \left(\frac{1}{k}\sum_{i=1}^ks_i^2\right)^{1/2}$ and $\sum_{i=1}^ks_i^2 < \left(\sum_{i=1}^ks_i\right)^2=n^2$, we see that 
$$ \min_{|U|=k} S(U)= \frac{n^2}{k}
$$
(the minimum is attained when all $s_i$ are equal to $n/k$) and
$$\sup_{|U|=k} S(U)=n^2
$$
($S(U)$ is close to this value when $U$ is contained in a small interval). Now let $U$ be a random subset of ${\mathbb T}_n$ of size $k$ (we identify it with a random point of $\{(s_1,...,s_k)\in[0,1]^k: \sum_{i=1}^ks_i=n\}$ with the normalized Lebesgue measure).  
It is not hard to show that $\P\left(s_i>t\right)=\P\left(s_1>t\right) = \left(\frac{n-t}{n}\right)^{k-1}$ for each $i$ and $t\in(0,n)$, and we thus have
${\mathbb E} s_i=n/k$ and ${\mathbb E} s_i^2=\frac{2n^2}{k(k+1)}$. It follows that
\begin{equation}\label{ES(U)}
{\mathbb E} S(U)=\frac{2n^2}{k+1}
\end{equation}
and
\begin{equation}\label{rand}
\P(s_i>t{\mathbb E} s_i) = (1-t/k)^{k-1} =  e^{-t} (1+o(1)), \quad k\to\infty,	
\end{equation}
uniformly for $0\leq t \leq t_0$ for any fixed $t_0>0$, and so for large $k$ the normalized gaps $s_i/{\mathbb E} s_i$ have the exponential distribution with parameter $1$. 
 
Now let $U$ be a subset of a cyclic group $\mathbb{Z}_n$ of a fixed size $k$. Again, it is easy to show that $S(U)$ is minimal when the points of $U$ are equidistributed, and is maximal when $U$ is an interval; thus, too small or too large value of $S(U)$ points out nonrandom behaviour of $U$. Having noted these extreme cases, 
we will be interested in the situations where  $S(U)$ is less or greater than the average $s(k,\mathbb{Z}_n)$ of the stochasticity parameter taken over all subsets of $\mathbb{Z}_n$ of size $k$, which can be interpreted as the stochasticity parameter of a random set of size $k$. In what follows we write $s(k)$ instead of $s(k,\mathbb{Z}_n)$ for the brevity, since the ambient group will always be clear from context; we also mention here the discrete analog of (\ref{ES(U)}):
\begin{equation}\label{1.3} 
s(k)=\frac{n(2n-k+1)}{k+1};
\end{equation}
note that this agrees with (\ref{ES(U)}) in the sense that  $s(k)\sim \frac{2n^2}{k+1}$ whenever $k=o(n)$.

In this work we study the set $R_M=\{a^2: a\in\mathbb{Z}_M \}$ of quadratic residues modulo $M$. It has multiplicative structure, and, as one may expect, there are many evidences for its random behaviour as an additive set: say, in the case of a prime modulo $p$, the probability that a random element of $\mathbb{Z}_p$ is a quadratic residue is close to $1/2$, and it can be shown (see Lemma \ref{lem2.2}) that for any arbitrary disjoint subsets $C_1$ and $C_2$ of $\mathbb{Z}_p$ the events $x+c_1\in R_p$ and $x+c_2\notin R_p$, $c_1\in C_1$, $c_2\in C_2$, are mutually independent, provided that $|C_1|+|C_2|\ll \log p$ (in particular, $R_p$ contains any additive configurations of length $\ll\log p$). The last phenomenon also comes up in the case of square-free modulo $m$; see Lemma \ref{lem2.3}. In the general case, the main evidence for random behaviour of $R_M$ is the following. Write $R_M=\{0=r_1<r_2<...<r_{|R_M|}\}$, set $r_{|R_M|+1}=M$, and take an index $i$ randomly and uniformly in $\{1,...,|R_M|\}$; then on average we have ${\mathbb E}(r_{i+1}-r_i)=\frac{M}{|R_M|}$. The limit distribution of the distances $r_{i+1}-r_i$ was found by Kurlberg and Rudnick  (see \cite{KR} and \cite{Kur}); they proved that
\begin{equation}\label{KR} 
\P\left(r_{i+1}-r_i>u\frac{M}{|R_M|}\right)=e^{-u}(1+o(1)), \qquad  \o(M)\to\infty,
\end{equation}
uniformly in the range $0\leq u\leq u_0$ for any fixed $u_0$, which is exactly the distribution (\ref{rand}) of gaps for a random set. This result supports the conjecture that
$$
S(R_M)=\frac{M^2}{|R_M|}{\mathbb E}\left(\frac{r_{i+1}-r_i}{M/|R_M|}\right)^2 \sim \frac{M^2}{|R_M|}\int_0^{\infty}x^2e^{-x}dx=\frac{2M^2}{|R_M|}, \quad \o(M)\to\infty;
$$
however, to make this rigorous we need good upper bounds for the contribution of large gaps between residues. On the other hand, if $\o(M)\to\infty$, then $|R_M|\to\infty$ and $M/|R_M|\to\infty$, and we have by (\ref{1.3}) 
$$s(|R_M|)=M\frac{2M-|R_M|+1}{|R_M|+1}\sim\frac{2M^2}{|R_M|}, \quad \o(M)\to\infty,
$$	
as we should expect. The quantity $s(|R_M|)$ turns out to be a better approximation for $S(R_M)$ than $\frac{2M^2}{|R_M|}$, since it also covers the case of a prime modulo $M=p$: Garaev, Konyagin, and Malykhin \cite{GKM} proved that 
\begin{equation}\label{GKM} 
S(R_p)= s(|R_p|)(1+o(1)), \quad p\to\infty,
\end{equation}
(and in fact they showed the same for all large multiplicative subgroups of $\mathbb{Z}_p^*$), but it is easy to compute that $s(|R_p|)=p\frac{2p-(p+1)/2+1}{(p+1)/2}\sim 3p$, whereas $\frac{2p^2}{|R_p|}=\frac{2p^2}{(p+1)/2}\sim 4p$.

One may wonder whether (\ref{GKM}) is still true if we consider all positive integers instead of primes. We show that this is false.	

\begin{theorem}\label{th1.1}
	We have
	$$\varliminf_{M\to\infty}\frac{S(R_M)}{s(|R_M|)}<1<\varlimsup_{M\to\infty}\frac{S(R_M)}{s(|R_M|)}\,.
	$$	
\end{theorem}

Note that the trivial lower bound $S(R_M)\geq\frac{M^2}{|R_M|}$ (obtained from Cauchy-Schwarz), together with (\ref{1.3}), implies that $\varliminf_{M\to\infty}\frac{S(R_M)}{s(|R_M|)}\geq0.5$; on the other hand, we do not know if $\varlimsup_{M\to\infty}\frac{S(R_M)}{s(|R_M|)}$ is finite and just mention here a recent work of Aryan \cite{Ary}, where it was shown that
$$S(R_M)\ll M2^{\o(M)}\log M \prod_{p|M}\left(1+\frac{1}{\sqrt{p}}\right)\left(1-\frac1p\right)
$$
for square-free $M$.


Our second result is concerned with a more delicate comparison $S(R_M)$ with $s(|R_M|)$. 

\begin{theorem}\label{th1.2}
	The set $\{ M\in \mathbb{N}: S(R_M)<s(|R_M|) \}$ 
	has positive density.
\end{theorem}
(Here and in what follows we consider the lower asymptotic density of a set $A\subseteq\mathbb{N}$, which is defined as $\varliminf_{N\to\infty}\frac{|A\cap\{1,\ldots,N\}|}{N}$.)

\bigskip 

Both Theorems \ref{th1.1} and \ref{th1.2} are obtained by the same method. To prove Theorem \ref{th1.1} (which is technically easier), we consider moduli of the form $M=Ap$, where $A$ is fixed and $p$ is a large prime; it turns out that the situation highly depends on this additional factor. 

\begin{theorem}\label{th1.3}
	Let $M=Ap$, where $A$ is square-free, $A\leq 0.1p^{0.1}$, and $(A,p)=1$. Then
	$$S(R_M)= 2f_A(0.5)p + O(A^3p^{0.95}),
	$$
	where $f_A$ is a rational function determined by $A$.
\end{theorem}

The coefficients of the function $f_A$ depend on the distances between quadratic residues modulo $A$ and can be written down explicitly; see Lemma \ref{lem5.3}. 

Using (\ref{1.3}) for the same $M$, we find  
\begin{equation*}\label{rand2}
s(|R_M|)=\left(\frac{4A^2}{|R_A|}-A\right)p+O(A^2|R_A|^{-1});
\end{equation*}
thus, to deduce Theorem \ref{th1.1} from Theorem \ref{th1.3}, it is enough to compare $2f_A(0.5)$ and $\frac{4A^2}{|R_A|}-A$ and find two appropriate values of $A$ which give us both possible inequalities. Numerical computations\footnote{See https://github.com/fractalon/arXiv2010.04982\_appendix. The author is grateful to Konstantin Olmezov for this code.} show that $2f_A(0.5)<\frac{4A^2}{|R_A|}-A$
for all $3\leq A\leq 100$, $A\neq89$, and
$2f_A(0.5)>\frac{4A^2}{|R_A|}-A$ for $A=89$. It implies Theorem \ref{th1.1}.

Now we turn to Theorem \ref{th1.2}. To prove it, we develop the previous idea and allow $M$ to have not one but many large prime divisors, and also vary the parameter $A$ (keeping it relatively small). Let us be more precise. Let $C_0>2$ be a large absolute constant; we denote by $\o(M)$ the number of prime divisors of $M$ and by $P^-(n)$ the least prime divisor of $n$. We consider the set $\O$ of sufficiently large positive integers $M$ such that


\begin{itemize}
	
	\item[(i)] $M$ is square-free;
	
	\item[(ii)] $0.9\log\log M < \o(M) < 1.1\log\log M$;	

	\item[(iii)] $M$ has the representation of the form $M=Am$, where $3\leq A \leq (\log M)^{0.1}$ and $P^-(m)>(\log M)^{C_0}$ (note that this representation is unique).
	
\end{itemize}

We will show that $S(R_M)<s(|R_M|)$ for $M\in\O$. In fact, one can avoid the condition (i) here, but it simplifies our argument and added for convenience. Further, due to Hardy and Ramanujan \cite{HR}, (ii) holds for almost all integers (that is, for a set of density $1$), and thus we can assume it without affecting the density of $\O$. Finally, the third condition (iii) is crucial for us: we will need it for making some error terms small, and anyway it occurs in different steps of our proof. 

We deduce Theorem \ref{th1.2} from the following two results.

\begin{theorem}\label{th1.4}
The density of the set $\O$ is equal to $e^{-\gamma}\frac{3}{5\pi^2C_0}$, where $\gamma$ is the Euler constant. 	
\end{theorem}

Denote by $\delta$ the density of the set $\{M\in\mathbb{N}: S(R_M)<s(|R_M|)\}$. One could extract the exact value of $C_0$ from our argument and thus obtain a lower bound for $\delta$, but this bound would be very poor. It is possible (using some additional ideas we do not present in this work) to get some better bounds, but it seems to be very hard to show that $\delta\geq 0.1$ using our method. Thus we did not try to optimize our lower bounds for $\d$, and keep the paper relatively short.


\begin{theorem}\label{th1.5}
For $M\in \O$ we have
	\begin{equation*}
	S(R_M)= \frac{2M^2}{|R_M|} - MA|R_A|^{-1}+O(M(\log M)^{-0.4}).
	\end{equation*} 
\end{theorem}


On the other hand, (\ref{1.3}) implies $M^{-1}s(k)=\frac{2M-k+1}{k+1}=\frac{2(M+1)}{k+1}-1=
\frac{2M}{k}-1+O\left(\frac{M}{k^2}\right).
$
Applying this to $M\in\O$, we obtain
\begin{equation}\label{1.6}
s(|R_M|)=\frac{2M^2}{|R_M|}-M+O((\log M)^2).
\end{equation}
Since $|R_A|<A$ for any $A\geq3$, Theorem \ref{th1.2} follows from Theorems \ref{th1.4} and \ref{th1.5} and the identity (\ref{1.6}). Besides, we immediately obtain an analog of (\ref{GKM}).

\begin{cor} We have
	$$S(R_M)=s(|R_M|)(1+o(1)), \quad M\to\infty, \, M\in \O.
	$$	
\end{cor}


Let $K_l$ be the number of gaps of length $l$ in $R_M$, that is, the number of elements $x\in R_M$ such that $x+l\in R_M$ but $x+j\notin R_M$ for $1\leq j\leq l-1$. To deal with $S(R_M)$, we write it as $\sum_{l\geq1}K_ll^2$ and, choosing a parameter $D$, divide the range of summation into small ($l\leq D$) and large ($l>D$) gaps. Note that for computing the contribution of small gaps in the setting of Theorem \ref{th1.5} one may use the limit distribution (\ref{KR}) of the distances between quadratic residues. Nevertheless, in order to be able to compute the second term in the asymptotics for $S(R_M)$, one should avoid $o(1)$-terms which occur in (\ref{KR}); so we use another technique (and consider special moduli). Finally, we note that our method seems to be insufficient to prove that the inequality $S(R_M)>s(|R_M|)$ holds for a large set of $M$; nevertheless, we believe that the set of such $M$ also has positive density.


In Sections \ref{Sec2}-\ref{Sec5} we will be simultaneously proving Theorems \ref{th1.3} and \ref{th1.5}. Section \ref{Sec2} is devoted to general results concerning additive configurations related to quadratic residues. In Section \ref{Sec3} we find the asymptotics for the contribution of small gaps into $S(R_M)$, and in Section \ref{Sec4} we show that the contribution of large gaps is asymptotically small. In Section \ref{Sec5} we finish the proofs of both Theorems \ref{th1.3} and \ref{th1.5}. Further, in Section \ref{Sec6} we prove Theorem \ref{th1.4}. Finally, in Section \ref{Sec7} we prove for completeness the identity (\ref{1.3}).


\section{Additive configurations related to quadratic residues}\label{Sec2} 

We begin with a classical estimate for complete character sums.

\begin{lem}\label{lem2.1} 
	Let $p$ be a prime, $\chi_1,\ldots,\chi_r$ be characters modulo $p$ with some $\chi_i\neq\chi_0$, where $\chi_0$ is the principal character, and $a_1,\ldots,a_r$ be distinct elements of $\mathbb{Z}_p$. Then
	$$\left|\sum_{x\in\mathbb{Z}_p}\chi_1(x+a_1)\chi_2(x+a_2)\ldots\chi_r(x+a_r)\right|\leq r\sqrt p.	
	$$	
\end{lem}

\begin{proof}
See \cite{Joh}, Lemma 1.
\end{proof}

To prove our Theorems \ref{th1.3} and \ref{th1.5}, we will need estimates for the number of some additive configurations related to quadratic residues. Let $M$ be a positive integer; for disjoint subsets $C_1$ and $C_2$ of $\mathbb{Z}_M$ we define the sets
\[
R_M(C_1)=\{x\in\mathbb{Z}_M: x+c_1\in R_M \mbox{ for all $c_1\in C_1$} \},
\]
\[
N_M(C_2)=\{x\in\mathbb{Z}_M: x+c_2\notin R_M   \mbox{ for all $c_2\in C_2$} \},
\]
and
\begin{equation*
RN_M(C_1,C_2)=R_M(C_1)\cap N_M(C_2)
\end{equation*}
(we do not exclude the cases where $C_1$ or $C_2$ is empty). The following two lemmas provide bounds for these quantities in the cases of prime and square-free moduli. For $x\in\mathbb{Z}_M$, we denote by $R_M(x)$ the indicator $\mathbb{I}(x\in R_M)$; $\theta$ is used for a number bounded in magnitude by $1$, which can vary from line to line.

\begin{lem}\label{lem2.2}
	Let $p$ be a prime. Then
	\begin{equation*} 
	|RN_p(C_1,C_2)|= p2^{-(|C_1|+|C_2|)}+0.5\theta(|C_1|+|C_2)|(p^{1/2}+1).
	\end{equation*}
\end{lem}

\begin{proof} We use the method from \cite{Dav}. Let $\chi$ be the Legendre symbol modulo $p$ and $1_p(x)$ be the indicator $\mathbb{I}(x=0)$. Then $R_p(x)=\frac12(1+\chi(x)+1_p(x))$
and $1-R_p(x)=\frac12(1-\chi(x)-1_p(x))$. Since the functions $R_p(x)$, $1-R_p(x)$, and $\frac{1\pm\chi(x+c_i)}{2}$ are bounded in magnitude by $1$, we have
\begin{multline*}
|RN_p(C_1,C_2)|=\sum_{x\in\mathbb{Z}_p}\prod_{c_1\in C_1}R_p(x+c_1)\prod_{c_2\in C_2}(1-R_p(x+c_2))=\\
\sum_{x\in\mathbb{Z}_p}\prod_{c_1\in C_1}\frac{1+\chi(x+c_1)+1_p(x+c_1)}{2}\prod_{c_2\in C_2}\frac{1-\chi(x+c_2)-1_p(x+c_2)}{2}=\\
2^{-(|C_1|+|C_2|)}\sum_{x\in\mathbb{Z}_p}\prod_{c_1\in C_1}(1+\chi(x+c_1))\prod_{c_2\in C_2}(1-\chi(x+c_2))+0.5\theta(|C_1|+|C_2|).
\end{multline*}
Denote $k=|C_1|+|C_2|$. Expanding the product in the last expression, we obtain the term $p$ and $2^k-1$ character sums; there are exactly ${k\choose r}$ of them of the type $\sum_{x\in\mathbb{Z}_p}\prod_{j=1}^r\chi(x+a_j)$, each of which is bounded by $rp^{1/2}$ by Lemma \ref{lem2.1}. Since $\sum_{r=1}^k{k\choose r}r=k2^{k-1}$, we get
\begin{equation*}
2^k|RN_p(C_1,C_2)|=p+0.5\theta k2^k(p^{1/2}+1),
\end{equation*} 
and the claim follows.   
\end{proof}



\begin{lem}\label{lem2.3} 
Let $m$ be a square-free positive integer, $p_1=P^-(m)$ and $t=\o(m)$, and let $C_1$ and $C_2$ be disjoint subsets of non-negative integers less than $p_1$, $|C_1|=s_1$, $|C_2|=s_2$. Then for all $r\in\mathbb{N}$ we have 
	\begin{equation*} 
	|RN_m(C_1,C_2)|=m2^{-s_1t}(1-2^{-t})^{s_2}+O(m2^{-s_1t}\left(E_1+E_2\right)),
	\end{equation*}
	where 
$$E_1= \sum_{k=0}^{\min\{r,s_2\}}{s_2\choose k}2^{-kt}E(s_1+k),
$$
$$E(\nu)=\sum_{d|m,d>1}\frac{\left(\nu2^{\nu}\right)^{\o(d)}}{d^{1/2}}, \quad 	E_2=\sum_{k=r}^{s_2}{s_2\choose k}2^{-kt}
$$
(we adopt the convention that $E_2=0$ for $r>s_2$).
\end{lem}



Note that the probability that a random element $x\in \mathbb{Z}_m$ is a quadratic residue is about $2^{-t}$. The main term $m2^{-s_1t}(1-2^{-t})^{s_2}$ in this lemma agrees with this, also telling us that the events $x+c_1\in R_m$, $c_1\in C_1$, and $x+c_2\notin R_m$, $c_2\in C_2$, are nearly independent, provided that the error terms are small. 

\begin{proof} We may assume $r\leq s_2+1$. For a subset $C\subseteq C_2$, we write for the brevity
$$R_C:=R_m(C_1\cup C)=\{x\in\mathbb{Z}_m: x+c\in R_m \mbox{ for all $c\in C_1\cup C$}\}.
$$
Note that $|RN_m(C_1,C_2)|=\left|R_{\varnothing}\setminus\bigcup_{c\in C_2}R_{\{c\}}\right|=|K_{\varnothing}|-|\bigcup_{c\in C_2}R_{\{c \}}|$.
Then by the inclusion-exclusion principle
\begin{equation}\label{2.2}
|RN_m(C_1,C_2)|=|R_{\varnothing}|-\sum_{|C|=1}|R_{C}|+\sum_{|C|=2}|R_C|-\ldots+(-1)^{s_2}|R_{C_2}|,
\end{equation}
and by the Bonferroni inequalities (see, for example, \cite{TV}, Ch.1, Exercise 1.1.3) we have
\begin{equation}\label{2.3} 
|RN_m(C_1,C_2)|=|R_{\varnothing}|-\sum_{|C|=1}|R_C|+\sum_{|C|=2}|R_C|-\ldots+(-1)^{r-1}\sum_{|C|=r-1}|R_C|+O\left(\sum_{|C|=r}|R_C|\right)
\end{equation}
for all $r\leq s_2$.

Now we fix $C\subseteq C_2$ and work with $|R_C|$. By multiplicity and the assumption that elements of $C_1\bigsqcup C_2$ are less than $p_1$ (and, hence, are distinct modulo $p$ for any $p|m$), we can rewrite it as
\begin{equation*}
|R_C|=\prod_{p|m}|R_p(C_1\cup C)|.
\end{equation*}
Let $|C|=k$. By Lemma \ref{lem2.2}, $|R_p(C_1\cup C)|=p2^{-(s_1+k)}\left(1+\theta(s_1+k)2^{s_1+k}p^{-1/2}\right)$ for some $|\theta|\leq1$. Thus, we see that 
\begin{equation}\label{2.4} 
|R_C|=m2^{-(s_1+k)t}+O\left(m2^{-(s_1+k)t}E(s_1+k)\right),
\end{equation}
with $E(s_1+k)$ defined in the statement of the lemma.

We first consider the case $r=s_2+1$. By (\ref{2.2}) and (\ref{2.4}),
\begin{multline*}
2^{s_1t}m^{-1}|RN_m(C_1,C_2)|=1-{s_2\choose 1}2^{-t}+{s_2\choose 2}2^{-2t}+\ldots  +(-1)^{s_2}2^{-s_2t}+\\+O\left(\sum_{k=0}^{s_2}{s_2\choose k}2^{-kt}E(s_1+k)\right)=
(1-2^{-t})^{s_2}+O(E_1), 
\end{multline*}
and the claim follows.

Now suppose that $r\leq s_2$. From (\ref{2.3}) and (\ref{2.4}) we obtain 
\begin{multline*}
2^{s_1t}m^{-1}RN_m(C_1,C_2)=1-{s_2\choose 1}2^{-t}+{s_2\choose 2}2^{-2t}+\ldots +(-1)^{r-1}{s_2\choose {r-1}}2^{-(r-1)t}+\\
+O\left(\sum_{k=0}^{r}{s_2\choose k}2^{-kt}E(s_1+k)+{s_2\choose {r}}2^{-rt}\right)=
(1-2^{-t})^{s_2}+E, 
\end{multline*}
where
\[
E\ll E_1+{s_2\choose {r}}2^{-rt}+\left|\sum_{k=r}^{s_2}(-1)^k{s_2 \choose k}2^{-kt}\right| \ll E_1+\sum_{k=r}^{s_2}{s_2 \choose k}2^{-kt}=E_1+E_2,
\]
as desired. This concludes the proof.    
\end{proof}


\begin{cor}\label{cor2.4}
Let $m$ be a square-free positive integer with $p_1=P^-(m)$ large enough, $t=\o(m)$, and let $C_1=\{0,l\}$ and $C_2$ be disjoint subsets of non-negative integers less than $p_1$. Suppose that $s=|C_2|\leq 0.13\cdot2^t\log p_1$ and $t\leq p_1^{0.01}$. Then
\[ |RN_m(C_1,C_2)|=m2^{-2t}(1-2^{-t})^s+O(m2^{-2t}(1+2^{1-t})^sp_1^{-0.48}),	
\]	
\end{cor}


\begin{proof} We set $r=[\frac{0.49\log p_1}{\log2}]$ in the previous lemma and estimate the quantities $E(k+2)$ for $0\leq k\leq r$.
Since then $t(k+2)2^{k+2}<p_1^{1/2}$, we have
\begin{multline*}
E(k+2)=\sum_{d|m,d>1}\frac{((k+2)2^{k+2})^{\o(d)}}{d^{1/2}} \leq \sum_{l=1}^t\left(\frac{(k+2)2^{k+2}}{p_1}\right)^l{t\choose l} = \\ \left(1+(k+2)2^{k+2}p_1^{-1/2}\right)^t-1 \leq  
\exp(t(k+2)2^{k+2}p_1^{-1/2})-1 \ll tr2^kp_1^{-1/2}.
\end{multline*}
We thus see that
$$E_1=\sum_{k=0}^{\min\{r,s\}}{s \choose k}2^{-kt}E(k+2) \ll trp_1^{-1/2}\sum_{k=0}^s{s\choose k}2^{(1-t)k} = (1+2^{1-t})^strp_1^{-1/2} \ll (1+2^{1-t})^sp_1^{-0.48}.
$$
Further, 
$${s \choose k}2^{-kt}\leq \frac{s^k}{k!2^{kt}} \ll   \left(\frac{se}{k2^t}\right)^k.
$$
Besides, we have $se\leq 0.13e2^t\log p_1 < 0.5r2^t$, and therefore
$$E_2=\sum_{k=r}^s{s \choose k}2^{-kt}  \ll \sum_{k=r}^{\infty}\left(\frac{se}{r2^t}\right)^k \ll 2^{-r} \ll  p_1^{-0.49}.
$$
The claim now follows from Lemma \ref{lem2.3}.  
\end{proof}


\begin{cor}\label{cor2.5}
	Let $m$ be a square-free positive integer with $p_1=P^-(m)$ large enough, $t=\o(m)$, and let $C$ be a subset of non-negative integers less than $p_1$. Suppose that $|C|\geq \a2^t\log p_1$ for some fixed $\a\in(0,0.13)$ and $t\leq p_1^{0.01}$. Then
	\[ |N_m(C)| \ll mp_1^{-\a}. 
	\]
\end{cor}

\begin{proof} Let $s=|C|$; since $N_m(C')\leq N_m(C'')$ whenever $C'\supseteq C''$, we may assume that $s=[\a2^t\log p_1]+1$. Arguing as in the proof of the previous lemma and using the inequality $(1+x)\leq e^x$, $x\in{\mathbb R}$, we get from Lemma \ref{lem2.3}
$$m^{-1}|N_m(C)| \ll (1-2^{-t})^s+(1+2^{1-t})^sp_1^{-0.48}\ll p_1^{-\a},
$$
as desired.   
\end{proof}


\section{Contribution of small gaps}\label{Sec3}  


For $2\leq j\leq A$ and $i\in \mathbb{Z}_A$, we set $I(i,j)=\{i+1,...,i+j-1\}\pmod{A}$ and
\begin{equation}\label{3.1} 
r(i,j)=\#\big(I(i,j)\cap R_A\big);
\end{equation}
also we adopt the convention that $r(i,1)=0$. Obviously, $0\leq r(i,j)\leq |R_A|$.

\begin{lem}\label{lem3.1}
Let $D\geq1$, $(A,m)=1$, $M=Am$, and $D_0=D|R_A|A^{-1}+|R_A|$. Suppose that for any $s\leq D_0$ we have an estimate of the type
$$\sum_{u\in\mathbb{Z}_{m}} R_m(u)R_m(u+l)\prod_{j=1}^{s}(1-R_m(u+\nu_j))=m2^{-2t}(1-2^{-t})^s+O(L(m,s))
$$	 
uniformly on distinct positive integers $\nu_1,\ldots,\nu_s,l$ less than $D$.
Then 
\begin{equation}\label{3.2}
\sum_{l\leq D} K_ll^2 =
m2^{-2t}\sum_{j=1}^{A}\sum_{i\in R_A\cap(R_A-j)}\sum_{Ak+j\leq D}y_t^{|R_A|k+r(i,j)}(Ak+j)^2+O(E(M,D_0)),
\end{equation}
where
$$E(M,D_0)=A^3|R_A|^{-1}\sum_{s\leq D_0}L(m,s)s^2 + A^3|R_A|\sum_{s=0}^{|R_A|}L(m,s).
$$
\end{lem}

\begin{proof} Since $(A,m)=1$, we have $R_M(x)=R_A(x)R_m(x)$, and hence
\begin{equation}\label{3.3}
R_M(x)=\begin{cases}
R_m(x), \, x\in R_A,\\
0, \, \mbox{otherwise.}
\end{cases}
\end{equation}
Fix $l\leq D$. We can write 
\begin{equation*}
K_l=\sum_{x\in\mathbb{Z}_M}R_M(x)R_M(x+l)\prod_{\nu=1}^{l-1}(1-R_M(x+\nu))=\sum_{i=0}^{A-1}K_l(i),
\end{equation*}
where
\begin{equation*}
K_l(i)=\sum_{x\in\mathbb{Z}_M: x\equiv i\pmod{A}}R_M(x)R_M(x+l)\prod_{\nu=1}^{l-1}(1-R_M(x+\nu)).
\end{equation*}
Further, using (\ref{3.3}) we get
\begin{equation}\label{3.4}
K_l=\sum_{i\in R_A\cap(R_A-l)}K_l(i).
\end{equation}
Now fix  $i\in R_A\cap(R_A-l)$. Let $\nu_1,\ldots,\nu_s$ be the numbers $\nu\in\{1,\ldots,l-1\}$ such that $(\nu+i)\pmod{A}\in R_A$. We write $l=Ak+j$ for some $k\geq0$ and $1\leq j\leq A$; then $k=\lfloor\frac{l}{A}\rfloor$ for $1\leq j\leq A-1$ and $k=\frac{l}{A}-1$ otherwise. Therefore, $\frac{l}{A}-1\leq k\leq \frac{l}{A}$ and
\begin{equation}\label{3.5}
s=s(l,i,A)=|R_A|k+r(i,j) = l|R_A|A^{-1}+\theta'|R_A|
\end{equation}
for some $\theta'\in[-1,1]$. In particular, $s(l,i,A)\leq D|R_A|A^{-1}+|R_A|=D_0$ for any $l\leq D$. Taking into account (\ref{3.3}) and recalling that $(A,m)=1$, we obtain from the assumption of the lemma  
\begin{multline*}
K_l(i)=\sum_{x\in\mathbb{Z}_M: x\equiv i\pmod{A}}R_m(x)R_m(x+l)\prod_{j=1}^{s}(1-R_m(x+\nu_j))=\\
\sum_{u\in\mathbb{Z}_{m}} R_m(Au+i)R_m(Au+i+l)\prod_{j=1}^{s}(1-R_m(Au+i+\nu_j))=\\
\sum_{u\in\mathbb{Z}_{m}} R_m(u)R_m(u+l)\prod_{j=1}^{s}(1-R_m(u+\nu_j))=m2^{-2t}(1-2^{-t})^{s(l,i,A)}+O(L(m,s(l,i,A))).
\end{multline*}
Since $l\equiv j\pmod{A}$, from here, (\ref{3.4}), and (\ref{3.5}) we have
\begin{equation*}\label{N_l}
K_l=m2^{-2t}\sum_{i\in R_A\cap(R_A-j)}y_t^{|R_A|k+r(i,j)}+O\left(\sum_{i\in R_A\cap (R_A-l)}L(m,s(l,i,A))\right),
\end{equation*}
where we write $y_t=1-2^{-t}$ for the brevity. Summing this estimate over $l\leq D$, we get 
\begin{equation*}
\sum_{l\leq D} K_ll^2 =
m2^{-2t}\sum_{j=1}^{A}\sum_{i\in R_A\cap(R_A-j)}\sum_{Ak+j\leq D}y_t^{|R_A|k+r(i,j)}(Ak+j)^2+O(E(M,D_0)),
\end{equation*}
where
$$
E(M,D_0)=\sum_{l\leq D}\sum_{i\in R_A\cap (R_A-l)}L(m,s(l,i,A))l^2.
$$
Note that (\ref{3.5}) implies $l\leq sA|R_A|^{-1}+A$. Further, if $l$ runs from $Ak+1$ to $Ak+A$ and $i$ runs over $R_A\cap (R_A-l)$, then $s(l,i,A)$ takes values from  $|R_A|k$ to $|R_A|k+|R_A|$. Hence, for any $s\geq0$ there are at most $O(A|R_A|)$ pairs $(l,i)$ with $s(A,l,i)=s$. Thus,
\begin{multline*}
E(M,D_0)\ll \sum_{s=0}^{D_0}L(m,s)A|R_A|\left(sA|R_A|^{-1}+A\right)^2 \ll \\ A^3|R_A|^{-1}\sum_{s\leq D_0}L(m,s)s^2 + A^3|R_A|\sum_{s=0}^{|R_A|}L(m,s).
\end{multline*}
This concludes the proof. 
\end{proof}

Let $\varepsilon_0\in(0,1)$ be a parameter to be chosen later.


\begin{lem}\label{lem3.2}
	Let $M=Ap$ with prime $p$ and $(A,p)=1$. Suppose that $A\leq 0.1p^{\varepsilon_0}$ and let $D=A|R_A|^{-1}p^{\varepsilon_0}$. Then
	$$E(M,D_0)\ll A^3|R_A|^{-1}p^{1/2+4\varepsilon_0}.
	$$ 
\end{lem}

\begin{proof} Lemma \ref{lem2.2} gives us the assumption of Lemma \ref{lem3.1} with $L(p,s)=(s+2)p^{1/2}$; also we have $D_0=p^{\varepsilon_0}+|R_A|$. Thus,
\begin{multline*}
E(M,D_0)\ll A^3|R_A|^{-1}p^{1/2}\sum_{s\leq D_0}s^3+A^3|R_A|p^{1/2}\sum_{s\leq |R_A|}s\ll A^3|R_A|^{-1}p^{1/2}\left(D_0^4+|R_A|^4\right) \ll \\
A^3|R_A|^{-1}p^{1/2}\left(p^{4\varepsilon_0}+|R_A|^4\right) \ll A^3|R_A|^{-1}p^{1/2+4\varepsilon_0},
\end{multline*}	
as desired.
\end{proof}


Let $M\in\O$ and $M=Am$. In what follows we will often use the fact that the condition (iii) in the definition of $\O$ implies $A\leq 2^t$, where $t=\o(m)$.


\begin{lem}\label{lem3.3}
Let $M\in \O$ and $D=0.13 A|R_A|^{-1}2^t\log p_1$. Then
$$E(M,D_0)\ll MA^22^tp_1^{-0.21}.
$$ 
\end{lem}

\begin{proof} Note that $M\in\O$ implies $t\leq p_1^{0.01}$. Then Corollary \ref{cor2.4} gives us the assumption of Lemma \ref{lem3.1} with
$$L(m,s) = m2^{-2t}(1+2^{1-t})^sp_1^{-0.48};
$$
set $D_0=0.13\cdot2^t\log p_1+|R_A|$. Also $M\in\O$ gives us $|R_A|\leq A\leq 2^t$. Then
\begin{equation*}
m^{-1}\sum_{s=0}^{|R_A|}L(m,s) \ll p_1^{-0.48}2^{-t}\exp(O(|R_A|2^{-t})) \ll p_1^{-0.48}2^{-t}.
\end{equation*}
Further,
\begin{multline*}
m^{-1}\sum_{s\leq D_0}L(m,s)s^2\ll 2^{-2t}p_1^{-0.48}\sum_{s\leq D_0}s^2(1+2^{1-t})^{s}\ll 2^{-2t}p_1^{-0.48}D_0^2\sum_{s\leq D_0}(1+2^{1-t})^s\ll\\
2^{-t}p_1^{-0.48}D_0^2(1+2^{1-t})^{D_0} \ll 2^{t}p_1^{-0.21}.
\end{multline*}
Then
\[
E(M,D_0)\ll mA^3|R_A|^{-1}\left(2^tp_1^{-0.21}+|R_A|^22^{-t}p_1^{-0.48} \right) \ll MA^22^tp_1^{-0.21}.
\]
The claim follows.
\end{proof}


To work with the main term in (\ref{3.2}), we introduce the function 
\begin{equation}\label{3.6}
g_A(y)=\sum_{j=1}^{A}\sum_{i\in R_A\cap(R_A-j)}y^{r(i,j)}\sum_{k\geq 0}y^{|R_A|k}(Ak+j)^2, \quad y\in(0,1);
\end{equation}
in the next section we will simplify this expression. Note that $g_A$ does not depend on $m$. 

Now we need an estimate for the ``tail'' of $g_A$. We set
\begin{equation*}
G_A(y,D)=\sum_{j=1}^{A}\sum_{i\in R_A\cap(R_A-j)}y^{r(i,j)}\sum_{Ak+j>D}y^{|R_A|k}(Ak+j)^2.
\end{equation*}


\begin{lem}\label{lem3.4}
	For any $N\geq2$ and $x\in (0,1)$, we have
	\begin{equation*}
	\sum_{n\geq N}n^2x^{n}\ll  x^N(1-x)^{-1}(N^2+(1-x)^{-2}).
	\end{equation*} 
\end{lem}

\begin{proof} We may assume that $N$ is a positive integer. For $x\in(0,1)$, we have $\sum_{n\geq N}x^n=x^N(1-x)^{-1}$;
by differentiating it twice, we obtain
\begin{multline*}
\sum_{n\geq N}n(n-1)x^{n-2}=N(N-1)x^{N-2}(1-x)^{-1}+2Nx^{N-1}(1-x)^{-2}+2x^N(1-x)^{-3} \\
\ll x^{N-2}(1-x)^{-1}\left(N^2+(1-x)^{-2}\right).
\end{multline*}
Since $n^2\ll n(n-1)$ for $n\geq2$, we have 
$$	\sum_{n\geq N}n^2x^{n} \ll x^2\sum_{n\geq N}n(n-1)x^{n-2} \ll x^N(1-x)^{-1}\left(N^2+(1-x)^{-2}\right),
$$
and the claim follows. 
\end{proof}

\begin{lem}\label{lem3.5}
	Let $M=Ap$ with prime $p$ and $(A,p)=1$. Suppose that $A\leq 0.1p^{\varepsilon_0}$ and let $D=A|R_A|^{-1}p^{\varepsilon_0}$. Then
	$$G_A(0.5,D)\ll 2^{-0.8p^{\varepsilon_0}}.
	$$ 
\end{lem}


\begin{proof} First, we note that
\[
\sum_{j=1}^A\sum_{i\in R_A\cap(R_A-j)}1\leq \sum_{i=1}^AR_A(i)\sum_{j=1}^AR_A(i+j)=|R_A|^2.
\]
Hence,
\begin{multline*} 
G_A(0.5,D)\leq \sum_{j=1}^A\sum_{i\in R_A\cap(R_A-j)}\max_{1\leq j\leq A}\sum_{Ak+j>D}2^{-|R_A|k}(Ak+j)^2 \leq \\
|R_A|^2\sum_{Ak+A>D}2^{-|R_A|k}(Ak+A)^2 \ll A^2|R_A|^2\sum_{k>|R_A|^{-1}p^{\varepsilon_0}-1}k^22^{-|R_A|k}.
\end{multline*}
Using the previous lemma, we get from here
\begin{multline*} 
G_A(0.5,D)\ll A^2|R_A|^22^{-|R_A|(p^{\varepsilon_0}|R_A|^{-1}-1)}\left(|R_A|^{-2}p^{2\varepsilon_0}+1\right) \ll A^2p^{2\varepsilon_0}2^{-0.9p^{\varepsilon_0}} \ll 2^{-0.8p^{\varepsilon_0}}. 
\end{multline*} 
This concludes the proof. 
\end{proof}


\begin{lem}\label{lem3.6} 
	Let $M\in \O$ and $D=0.13A|R_A|^{-1}2^t\log p_1$. Then
	\begin{equation*}
	G_A(y_t,D) \ll A^42^{3t}p_1^{-0.12}. 
	\end{equation*}
\end{lem} 


\begin{proof} As before, 	
\begin{multline*} 
G_A(y_t,D)\leq \sum_{j=1}^A\sum_{i\in R_A\cap(R_A-j)}\max_{1\leq j\leq A}\sum_{Ak+j>D}y_t^{|R_A|k}(Ak+j)^2 \leq \\
|R_A|^2\sum_{Ak+A>D}y_t^{|R_A|k}(Ak+A)^2 \ll A^2|R_A|^2\sum_{k>D/A-1}k^2y_t^{|R_A|k}.
\end{multline*}
Further, $y_t^{|R_A|}\leq y_t = 1-2^{-t}$, and hence $(1-y_t^{|R_A|})^{-1}\leq 2^t$; also $1/2\leq y_t<1$. Using Lemma \ref{lem3.4} and the inequality $1-x\leq e^{-x}$, we see that
\begin{multline*} 
G_A(y_t,D)\ll A^2|R_A|^2 y_t^{|R_A|D/A}2^t\left( D^2A^{-2}+2^{2t}\right) \ll \\ A^2|R_A|^22^{3t}(|R_A|^{-2}(\log p_1)^2+1)p_1^{-0.13} \ll A^42^{3t}p_1^{-0.12}.
\end{multline*} 
This concludes the proof. 
\end{proof}

Combining the results of this section, we obtain the following two corollaries.


\begin{cor}\label{cor3.7}
	Let $M=Ap$ with prime $p$ and $(A,p)=1$. Suppose that $A\leq 0.1p^{\varepsilon_0}$ and let $D=A|R_A|^{-1}p^{\varepsilon_0}$. Then	
$$\sum_{l\leq D}K_ll^2 = 0.25g_A(0.5)p+O(A^3p^{1/2+4\varepsilon_0}).
$$
\end{cor}

\begin{proof} Set $D_0=p^{\varepsilon_0}+|R_A|$. By Lemmas \ref{lem3.1}, \ref{lem3.2} and \ref{lem3.5}, we have
\begin{multline*}
\sum_{l\leq D}K_ll^2 = 0.25p\left(g_A(0.5)+G_A(0.5,D)\right)+O(E(M,D_0)) = \\ 0.25g_A(0.5)p+O(A^3|R_A|^{-1}p^{1/2+4\varepsilon_0}+p2^{-0.8p^{\varepsilon_0}}).
\end{multline*}
The claim follows.	
\end{proof}


\begin{cor}\label{cor3.8}
Let $M\in \O$ and $D=0.13 A|R_A|^{-1}2^t\log p_1$. Then	
$$\sum_{l\leq D}K_ll^2 = m2^{-2t}g_A(y_t) + O(MA^32^tp_1^{-0.12}).
$$
\end{cor}

\begin{proof}
Set $D_0=0.13\cdot2^t\log p_1+|R_A|$. By Lemmas \ref{lem3.1}, \ref{lem3.3} and \ref{lem3.6}, we have
\begin{multline*}
\sum_{l\leq D}K_ll^2 = m2^{-2t}\left(g_A(y_t)+G_A(y_t,D)\right)+O(E(M,D_0)) = \\ m2^{-2t}g_A(y_t)+O(MA^32^tp_1^{-0.12}+MA^22^tp_1^{-0.21}).
\end{multline*}
The claim follows.	
\end{proof}




\section{Contribution of large gaps}\label{Sec4}

To bound the contribution of large gaps, we will need Burgess' estimates for character sums.

\begin{lem}\label{lem4.1} 
	Let $k$ be square-free, $\chi$ be a nonprincipal character modulo $k$, and $\varepsilon>0$, $r\in\mathbb{N}$. Then for any $x\in\mathbb{Z}_k$ and $h\in \mathbb{N}$ we have
	$$\left|\sum_{i=0}^{h-1}\chi(x+i)\right|\ll_{r,\varepsilon}h^{1-1/r}k^{(r+1)/4r^2+\varepsilon}. 
	$$	
\end{lem}

\begin{proof} See \cite{burg1},  Theorem 2.    
\end{proof}


\begin{lem}\label{lem4.2} 
	Let $k$ be square-free, $\chi$ be a primitive character modulo $k$, and $\varepsilon>0$, $r\in\mathbb{N}$. Then 
	$$\sum_{x\in\mathbb{Z}_k}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|^{2r} \ll_{r,\varepsilon} kh^r+k^{1/2+\varepsilon}h^{2r}.
	$$	
\end{lem}

\begin{proof} See \cite{burg2}, Lemma 8.  
\end{proof}



Let $H\in\mathbb{N}$. For the brevity, we denote by $N_M(H)=N_M(\{0,1,...,H-1\})$ the set of $x\in\mathbb{Z}_M$ such that all elements $x,x+1,\ldots,x+H-1$ are quadratic non-residues modulo $M$. 


\begin{lem} \label{lem4.3}
	Let $M$ be a square-free positive integer. Suppose that $h\geq (2C\tau(M))^{50}$,
where $C$ is an absolute constant. Then 
	$$|N_M(h)| \ll M\tau(M)^4h^{-1.47}. 
	$$
\end{lem} 

\begin{proof} Let $\L$ be the set of nontrivial real characters modulo $M$, and $\chi_p$ be the Legendre symbol modulo $p$. For any quadratic nonresidue $x\in\mathbb{Z}_M$ we have 
	$$
	\sum_{\chi\in\L}\chi(x)=\prod_{p|M}(1+\chi_p(x))-1=-1;
	$$
	therefore, for any $x\in N_M(h)$ 
	\begin{equation}\label{4.1} 
	\left|\sum_{\chi\in\L}\sum_{i=0}^{h-1}\chi(x+i)\right|=h.
	\end{equation}
	Denote by $k(\chi)$ the conductor of $\chi\in\L$ and set
	$$\L_1=\{\chi\in\L: k(\chi)\leq h^3\}, \quad \L_2=\{\chi\in L: k(\chi)>h^3\}.
	$$
	We want to show that
	\begin{equation}\label{4.2} 
	\sum_{\chi\in\L_1}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|\leq h/2.
	\end{equation}
	For any $\chi\in\L_1$ Lemma \ref{lem4.1} implies
	$$\left|\sum_{i=0}^{h-1}\chi(x+i)\right|\ll_{r,\varepsilon} h^{1-1/r}h^{3(1/4r+1/4r^2+\varepsilon)}= h^{1-(1-3/r)/(4r)+3\varepsilon}.
	$$
	Taking $r=6$ and $\varepsilon=0.0001$, we obtain
	$$\sum_{\chi\in\L_1}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|\leq Ch^{1-1/48+0.0003}|\L_1|\leq Ch^{0.98}|\L_1|
	$$
	for some absolute constant $C>0$, and (\ref{4.2}) follows from $2C|\L_1|\leq 2C|\L|=2C\tau(M)\leq h^{0.02}$.

From (\ref{4.1}) and (\ref{4.2}) we see that
	$$\sum_{\chi\in\L_2}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|\geq h/2,
	$$
	for all $x\in N_M(h)$, and thus
	\begin{equation}\label{4.3} 
	\sum_{x\in Y(h)}\sum_{\chi\in\L_2}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|\geq |Y(h)|h/2.
	\end{equation}
	On the other hand, for any $\chi\in\L_2$ we have from Lemma \ref{lem4.2} (with $\varepsilon=0.01$)
	\begin{equation*}
	\sum_{x\in Y(h)}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|^{2r}\leq \sum_{x\in\mathbb{Z}_M}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|^{2r}\ll \frac{M}{k_{\chi}} \sum_{x\in \mathbb{Z}_{k_{\chi}}}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|^{2r}\ll_r Mh^r+Mh^{2r}k_{\chi}^{-0.49}.
	\end{equation*}
	Setting $r=2$, we have for all $\chi\in\L_2$
	$$\sum_{x\in Y(h)}\left|\sum_{i=0}^{h-1}\chi(x+i)\right|^{4} \ll Mh^{2.53}.
	$$
	Using H\"older's inequality, we find from (\ref{4.3})
	$$
	|Y(h)|h\ll \sum_{\chi\in\L_2}\sum_{x\in Y(h)}\left|\sum_{i=0}^{h-1}\chi(x+i)\right| \ll \tau(M)|Y(h)|^{3/4}(Mh^{2.53})^{1/4},
	$$
	and hence,
	$$
	|Y(h)|\ll M\tau(M)^4h^{-1.47}.  
	$$
	The claim follows.
\end{proof}


\begin{rem}\label{rem4.4}
	One can deduce from this argument that the size of maximal gap in the set $R_M$ is at most $O(M^{1/3})$, but we do not need it here.	
\end{rem}


Let $R_M=\{0=r_1<r_2<\ldots<r_{|R_M|}\}$ be the set of quadratic residues modulo $M$. 

\begin{lem}\label{lem4.5}
	We have
	$$
	\sum_{2^{\nu+1}\leq r_i-r_{i-1} < 2^{\nu+2} }(r_i-r_{i-1})^2 \leq |N_M(2^\nu)|2^{\nu+4}.
	$$
\end{lem}

\begin{proof} If $r_i-r_{i-1}\geq 2^{\nu+1}$, then for all $1\leq k\leq 2^{\nu}$ the elements $r_{i-1}+k$ belong to $N_M(2^{\nu})$. Therefore the number of such $i$ is at most $2^{-\nu}|N_M(2^{\nu})|$. The claim follows. 
\end{proof}



\begin{lem}\label{lem4.6}
Let $M=Ap$, where $(A,p)=1$, $p$ is large enough, and $A\leq p^{\varepsilon_0}$. Then for $D=A|R_A|^{-1}p^{\varepsilon_0}$ we have
$$\sum_{l>D}K_ll^2 \ll A^2p^{1-0.47\varepsilon_0}.
$$
\end{lem}

\begin{proof} Using the previous lemma, we obtain
\[
\sum_{l>D}K_ll^2 \leq \sum_{\nu\,:\, 2^{\nu}>D}\sum_{2^{\nu-1}\leq u_j-u_{j-1}<2^{\nu}}(u_j-u_{j-1})^2 \ll \sum_{\nu\,:\, 2^{\nu}>D}|N_M(2^{\nu-2})|2^{\nu}. 
\]
Note that since $p$ is large enough, then for some absolute constant $C_1$ we have $(4C\tau(A))^{50}\leq C_1A^{1/2} \leq 0.25p^{\varepsilon_0} \leq 0.25D$; thus $2^{\nu}>D$ implies $2^{\nu-2}>(2C\tau(M))^{50}$. Then Lemma \ref{lem4.3} gives us
\[
\sum_{l>D}K_ll^2\ll 2^{4\o(M)}M\sum_{\nu\,:\, 2^{\nu+2}>D}2^{-0.47\nu} \ll \tau(A)^4ApD^{-0.47} \ll A^2p^{1-0.47\varepsilon_0},
\]
as desired.
\end{proof}


\begin{cor}\label{cor4.7}
	Let $M=Ap$ with large enough prime $p$ and $(A,p)=1$. Suppose that $A\leq 0.1p^{0.1}$. Then	
	$$S(R_M) = 0.25g_A(0.5)p+O(A^3p^{0.95}).
	$$
\end{cor}

\begin{proof} Set $D=A|R_A|^{-1}p^{\varepsilon_0}$ with some $\varepsilon_0\geq0.1$. By Corollary \ref{cor3.7} and Lemma \ref{lem4.6}, we have
	$$S(R_M)=\sum_{l\leq D}K_ll^2+\sum_{l>D}K_ll^2 = 0.25g_A(0.5)p+O(A^3p^{1/2+4\varepsilon_0}+A^2p^{1-0.47\varepsilon_0})	.
	$$	
	Now we set $\varepsilon_0=\frac{1}{2\cdot4.47}=0.11...$. Then $1-0.47\varepsilon_0=1/2+4\varepsilon_0<0.95$, and the claim follows.	
\end{proof}



Now we work with $M\in\O$. 

\begin{lem}\label{lem4.8}
Let $M\in\O$, $D=0.13\frac{A}{|R_A|}2^t\log p_1$, and $D'<p_1$. Then
$$\sum_{D<l\leq D'}K_ll^2 \ll mD'p_1^{-0.03}.
$$	
\end{lem}

\begin{proof}
Lemma \ref{lem4.5} gives us	
\begin{equation}\label{4.4}
\sum_{D<l\leq D'} K_ll^2 \leq \sum_{\nu\,:\, D<2^{\nu}\leq 2D'}\sum_{2^{\nu-1}\leq u_j-u_{j-1}<2^{\nu}}(u_j-u_{j-1})^2 \ll \sum_{\nu\,:\, D<2^{\nu}\leq 2D'}|N_M(2^{\nu-2})|2^{\nu}. 
\end{equation}
Recall that $M\in\O$ implies $A\leq 2^t<D$. Suppose that $2^{\nu}>D$ and denote $h=2^{\nu-2}$. Then in the interval $\{0,...,2^{\nu-2}-1\}$ there are at least 
$$|R_A|[hA^{-1}]\geq |R_A|A^{-1}h-|R_A|\geq [0.03\cdot2^t\log p_1]=:s
$$
quadratic residues modulo $A$; denote the set of them by $C$. By Corollary \ref{cor2.5}
$$N_M(h)\leq N_m(C) \ll mp_1^{-0.03},
$$
and from (\ref{4.4}) we have
\[
\sum_{D<l\leq D'} K_ll^2 \ll D'mp_1^{-0.03}.
\]
This completes the proof.
\end{proof}

\begin{lem}\label{lem4.9}
Let $M\in\O$. Then for $D'=2^{51\o(M)}$ we have
\[
\sum_{l>D'}K_ll^2\ll M2^{-19\o(M)}.
\]	
\end{lem}

\begin{proof}
Lemma \ref{lem4.5} gives us	
\[
\sum_{l>D'}K_ll^2 \leq \sum_{\nu\,:\, 2^{\nu}>D'}\sum_{2^{\nu-1}\leq u_j-u_{j-1}<2^{\nu}}(u_j-u_{j-1})^2 \ll \sum_{\nu\,:\, 2^{\nu}>D'}|N_M(2^{\nu-2})|2^{\nu}. 
\]
Note $2^{\nu}>D=\tau(M)^{51}$, together with $M\in\O$, implies $2^{\nu-2}>(2C\tau(M))^{50}$. Then we apply Lemma \ref{lem4.3} and obtain
\[
\sum_{l>D'}K_ll^2 \ll M2^{4\o(M)}\sum_{\nu: 2^{\nu}>D'}2^{-0.47} \ll M2^{-19\o(M)}.
\]
The claim follows.
\end{proof}



\begin{cor}\label{cor4.10}
	Let $M\in \O$. Then	
	$$S(R_M) = m2^{-2t}g_A(y_t) + O(M(\log M)^{-1}).
	$$
\end{cor}

\begin{proof}
Set $D=0.13 A|R_A|^{-1}2^t\log p_1$ and $D'=2^{51\o(M)}$. Combining Corollary \ref{cor3.8}, Lemma \ref{lem4.8} and Lemma \ref{lem4.9}, we have
\begin{multline*}
S(R_M)=\sum_{l\leq D}K_ll^2+\sum_{l<l\leq D'}K_ll^2 + \sum_{l>D'}K_ll^2=\\ m2^{-2t}g_A(y_t) + O(MA^32^tp_1^{-0.13}+m2^{51\o(M)}p_1^{-0.03}+M2^{-19\o(M)}).	
\end{multline*}
Recall that $M\in\O$ implies $A\leq 2^t$, $p_1>(\log M)^{C_0}$, and $\o(M)/\log\log M\in[0.9,1.1]$. Then taking $C_0$ large enough concludes the proof. 
\end{proof}




\section{The end of the proofs of Theorems \ref{th1.3} and \ref{th1.5}}\label{Sec5}

Having proved Corollaries \ref{cor4.7} and \ref{cor4.10}, we found the assumed asymptotics for $S(R_M)$ in terms of the function $g_A$. Now we are aiming to extract further information about it. Recall that for any $y\in(0,1)$
\begin{equation}\label{5.1}
g_A(y)=\sum_{j=1}^{A}\sum_{i\in R_A\cap(R_A-j)}y^{r(i,j)}\sum_{k\geq 0}y^{|R_A|k}(Ak+j)^2;
\end{equation}
We begin with the following simple lemma, which allows us to simplify this expression.

\begin{lem}\label{lem5.1}
For all $x\in(0,1)$ we have
\begin{equation*} 
\sum_{n=0}^{\infty}x^n=\frac{1}{1-x}, \qquad \sum_{n=1}^{\infty}nx^{n}=\frac{x}{(1-x)^2},
\qquad \sum_{n=1}^{\infty}n^2x^{n}=\frac{x(1+x)}{(1-x)^3}.
\end{equation*}
\end{lem} 

\begin{proof} This can be obtained by standard direct calculations.
\end{proof}


We apply this lemma to the inner sum in the definition (\ref{5.1}) of the function $g_A$. We have
\begin{equation*}
\sum_{k=0}^{\infty}y^{|R_A|k}=\frac{1}{1-y^{|R_A|}}, \qquad  \sum_{k=0}^{\infty}ky^{|R_A|k}=\frac{y^{|R_A|}}{(1-y^{|R_A|})^2}, \qquad 
\sum_{k=0}^{\infty}k^2y^{|R_A|k}=\frac{y^{|R_A|}(1+y^{|R_A|})}{(1-y^{|R_A|})^3},
\end{equation*}
and hence
\begin{equation}\label{5.2} 
g_A(y)=\frac{A^2y^{|R_A|}(1+y^{|R_A|})P_0(y)}{(1-y^{|R_A|})^3}+\frac{2Ay^{|R_A|}P_1(y)}{(1-y^{|R_A|})^2} +\frac{P_2(y)}{1-y^{|R_A|}}, 
\end{equation}
where
$$P_0(y)=\sum_{i\in R_A}\sum_{j\in R_A-i}y^{r(i,j)},
$$
$$P_1(y)=\sum_{i\in R_A}\sum_{j\in R_A-i}jy^{r(i,j)},
$$
$$P_2(y)=\sum_{i\in R_A}\sum_{j\in R_A-i}j^2y^{r(i,j)}.
$$

Let $s_1,\ldots,s_{|R_A|}$ be the distances between consecutive quadratic residues modulo $A$; here and further we consider the indeces of $s_i$ modulo $|R_A|$. For $k=0,...,|R_A|-1$ we set $\a_k=\sum_{i=1}^{|R_A|}\left(\sum_{l=i}^{i+k}s_l\right)^2$. In particular, $\a_0=\sum_{i=1}^{|R_A|}s_i^2=S(R_A)$ and $\a_{|R_A|-1}=A^2|R_A|$. 

Now we compute the polynomials $P_0$, $P_1$, and $P_2$. 


\begin{lem}\label{lem5.2}
We have $P_0(y)=|R_A|\sum_{k=0}^{|R_A|-1}y^k$, $P_1(y)=A\sum_{k=0}^{|R_A|-1}(k+1)y^k$, and $P_2(y)=\sum_{k=0}^{|R_A|-1}\a_ky^k$. 
\end{lem}

\begin{proof} Recall that $r(i,j)=\#((i,i+j)\cap R_A)$  (see (\ref{3.1})). Clearly, for any fixed $i\in R_A$, the function $r(i,j)$ takes values $0,1,\ldots,|R_A|-1$ exactly once. Let $s\in\{0,1,2\}$, and denote by $\{i_{\nu} \}_{\nu\in\mathbb{Z}_{|R_A|}}$ the set $R_A$. We have
\begin{multline*}
P_s(y)=\sum_{i\in R_A}\sum_{j\in R_A-i}j^sy^{r(i,j)}=
\sum_{k=0}^{|R_A|-1}y^k\sum_{i,i+j\in R_A}j^s\mathbb{I}(\#((i,i+j)\cap R_A)=k))=\\
\sum_{k=0}^{|R_A|-1}y^k\sum_{\nu=1}^{|R_A|}(i_{\nu+k+1}-i_{\nu})^s=
\sum_{k=0}^{|R_A|-1}y^k\sum_{i=1}^{|R_A|}\left(\sum_{l=i}^{i+k}s_l\right)^s.
\end{multline*}
Now if $s=0$, then we obtain $P_0(y)=|R_A|\sum_{k=0}^{|R_A|-1}y^k$. If $s=1$, then $\sum_{i=1}^{|R_A|}\sum_{l=i}^{i+k}s_l=\sum_{l=1}^{|R_A|}s_l(k+1)=(k+1)A$, and thus $P_1(y)=A\sum_{k=0}^{|R_A|-1}(k+1)y^k$. Finally, if $s=2$, then $P_2(y)=\sum_{k=0}^{|R_A|-1}\a_ky^k$ by the definition of the numbers $\a_k$. This completes the proof.
\end{proof}

Lemma \ref{lem5.2} gives us    
$$(1-y)P_0(y)=|R_A|(1-y^{|R_A|})
$$
and
$$
(1-y)^2P_1(y)=A(1-y)\left(\sum_{k=0}^{|R_A|-1}y^k-|R_A|y^{|R_A|}\right)=
A(1-y^{|R_A|})-A|R_A|(1-y)y^{|R_A|}.
$$
Hence,
\begin{equation}\label{5.3}
\frac{A^2y^{|R_A|}(1+y^{|R_A|})(1-y)^3P_0(y)}{(1-y^{|R_A|})^3}=
\frac{A^2|R_A|y^{|R_A|}(1+y^{|R_A|})(1-y)^2}{(1-y^{|R_A|})^2}. 
\end{equation}
and 
\begin{equation}\label{5.4} 
\frac{2Ay^{|R_A|}(1-y)^3P_1(y)}{(1-y^{|R_A|})^2}=
\frac{2A^2(1-y)y^{|R_A|}}{1-y^{|R_A|}}-
\frac{2A^2|R_A|y^{2|R_A|}(1-y)^2}{(1-y^{|R_A|})^2}. 
\end{equation}
Now we compute the function $f_A(y)=(1-y)^3g_A(y)$. From (\ref{5.2}), (\ref{5.3}), and  (\ref{5.4}) we have
\begin{multline}\label{5.5} 
f_A(y)=
\frac{A^2|R_A|(1-y)^2y^{|R_A|}}{1-y^{|R_A|}}+
\frac{2A^2(1-y)y^{|R_A|}}{1-y^{|R_A|}}+
\frac{(1-y)^3P_2(y)}{1-y^{|R_A|}}=\\
\frac{A^2y^{|R_A|}(2+|R_A|(1-y))+(1-y)^2P_2(y)}{1+y+\ldots+y^{|R_A|-1}}. 
\end{multline}

We continue working with the function $f_A$. 

\begin{lem}\label{lem5.3} 
	We have
	$$f_A(y)=\frac{F(y)}{Q(y)}, 
	$$
where $Q(y)=Q_A(y)=1+y+\ldots+y^{|R_A|-1}$ and $F(y)=F_A(y)=\sum_{k=0}^{|R_A|}\b_ky^k$ be the reciprocal polynomial with the coefficients  
$\b_0=\b_{|R_A|}=\sum_is_i^2$ 
and
$\b_k=2\sum_{i=1}^{|R_A|}s_is_{i+k}$ 
for $0<k<|R_A|$.

\end{lem}

\begin{proof} From (\ref{5.5}) and Lemma \ref{lem5.2} we see that
\begin{equation*}
F(y)=(1-2y+y^2)\sum_{k=0}^{|R_A|-1}\a_ky^k+A^2(|R_A|+2)y^{|R_A|}-A^2|R_A|y^{|R_A|+1}.
\end{equation*}
Now we write $F(y)=\sum_{k=0}^{|R_A|+1}\gamma_ky^k$ and compute $\gamma_k$. Firstly,
$$\gamma_0=\a_0=\sum_{i=1}^{|R_A|}s_i^2,
$$
and
$$\gamma_1=\a_1-2\a_0=\sum_{i=1}^{|R_A|}(s_i+s_{i+1})^2-2\sum_{i=1}^{|R_A|}s_i^2=2\sum_{i}s_is_{i+1}.
$$
Further, observe that 
\begin{equation*} \a_k=\sum_i(s_i+\ldots+s_{i+k})^2=
(k+1)\sum_is_i^2+2\sum_{l=1}^k(k+1-l)\sum_{i}s_is_{i+l};
\end{equation*} 
then for $2\leq k\leq |R_A|-1$ we have  
$$\gamma_k=\a_{k-2}-2\a_{k-1}+\a_k=2\sum_is_is_{i+k}.
$$
It remains to calculate $\gamma_{|R_A|}$ and $\gamma_{|R_A|+1}$. Recall that $\a_{|R_A|-1}=A^2|R_A|$. Then we have 
$$
\gamma_{|R_A|+1}=\a_{|R_A|-1}-A^2|R_A|=0
$$   
and
$$\gamma_{|R_A|}=-2\a_{|R_A|-1}+\a_{|R_A|-2}+(|R_A|+2)A^2=\a_{|R_A|-2}+2A^2-A^2|R_A|.
$$
Finally,
\begin{multline*}
\a_{|R_A|-2}=\sum_{i}\left(\sum_{l=i}^{i+|R_A|-2}s_{i+l}\right)^2=\sum_{i=1}^{|R_A|}(A-s_i)^2=\\
A^2|R_A|-2A\sum_is_i+\sum_is_i^2=A^2|R_A|-2A^2+\a_0,
\end{multline*} 
and therefore $\gamma_{|R_A|}=\gamma_0=\sum_is_i^2$. Thus $F(y)=\sum_{k=0}^{|R_A|}\b_ky^k$, as desired.
\end{proof}

Since $f_A(y)=(1-y)^3g_A(y)$, we have $g_A(0.5)=8f_A(0.5)$ and $g_A(y_t)=2^{3t}f_A(y_t)$ for $y_t=1-2^{-t}$. Now Theorem \ref{th1.3} follows immediately from Corollary \ref{cor4.7}; also we can rewrite Corollary \ref{cor4.10} as  
\begin{equation}\label{5.6}
S(R_M)=m2^tf_A(y_t)+O(M(\log M)^{-1})
\end{equation}
for $M\in\O$. To finish the proof of Theorem \ref{th1.5}, we expand the function $f_A$ to the Taylor series at the point $y=1$.


We see from Lemma \ref{lem5.3} that $f_A$ obeys the functional equation
$$f_A(y)=yf_A\left(\frac1y\right).
$$
We then obtain
\begin{equation}\label{5.7}
f'_A\left(\frac1y\right)=f_A(y)-yf_A'(y)
\end{equation}
and
\begin{equation}\label{5.8}
f_A''\left(\frac1y\right)=y^3f''_A(y).
\end{equation}
Also from (\ref{5.1}) we have
\begin{equation}\label{5.9}
f_A(1)=\frac{2A^2}{|R_A|},
\end{equation}
and (\ref{5.7}) immediately implies $f'_A(1)=0.5f_A(1)=A^2|R_A|^{-1}$. Then by the Taylor expansion 
\begin{equation}\label{5.10}
m2^tf_A(y_t)=m2^{t+1}A^2|R_A|^{-1}-mA^2|R_A|^{-1}+\frac12f''_A(\theta_{A,t})m2^{-t}
\end{equation}
for some $\theta_{A,t}\in(1-2^{-t},1)$, and it remains to estimate the second derivative of $f_A$. 

\begin{lem}\label{lem5.4}
	Suppose that $|R_A|\leq 2^{t}$. Then
	$$
	f''_A(y)\ll A^2|R_A|$$
	for $y\in(y_t,1)$.
\end{lem}


\begin{proof} Due to (\ref{5.8}), it suffices to prove the lemma for $1\leq y\leq 1+O(2^{-t})$ instead of $y\in(y_t,1)$. Firstly,
\begin{equation}\label{5.11}
\left(\frac{F(y)}{Q(y)}\right)''=\frac{F''(y)Q^2(y)-2F'(y)Q'(y)Q(y)-F(y)Q''(y)Q(y)+2F(y)Q'^2(y)}{Q^3(y)}.  
\end{equation}
Further, for $1\leq y\leq 1+O(2^{-t})$ by the assumption on $|R_A|$ we have $y^k \asymp 1$ uniformly for $0\leq k\leq |R_A|$ and thus
$$Q(y)\asymp |R_A|, \qquad Q'(y)\asymp |R_A|^2, \qquad Q''(y) \asymp |R_A|^3.
$$ 
Taking into account (\ref{5.9}), we find
$$F(y)\ll \sum_{k=0}^{|R_A|}\b_k=F(1)=f_A(1)Q(1)=2A^2,
$$
$$F'(y)=\sum_{k=1}^{|R_A|}k\b_ky^{k-1}\ll A^2|R_A|, \qquad F''(y)\ll A^2|R_A|^2. 
$$
Thus for $1\leq y\leq 1+O(2^{-t})$ we have from (\ref{5.11}) 
$$f_A''(y) \ll \frac{A^2|R_A|^4}{|R_A|^3}=A^2|R_A|,
$$
and the claim follows. 
\end{proof}


Now combining (\ref{5.6}), (\ref{5.10}) and the bound from Lemma \ref{lem5.4}, we get 
\begin{equation}\label{5.12}
S(R_M) = M2^{t+1}A|R_A|^{-1}-MA|R_A|^{-1} + O(M(\log M)^{-1}+MA|R_A|2^{-t}).
\end{equation}
Recalling that $M\in\O$ implies $A\leq (\log M)^{0.1}$ and $2^{-t}\leq2^{-(0.9+o(1))\log\log M}$, we get 
\begin{equation}\label{5.13}
A|R_A|2^{-t}\leq (\log M)^{-0.4}. 
\end{equation}
Further, since $\prod_{i=1}^t(1+p_i^{-1})\leq\exp(\sum_{i=1}^tp_i^{-1})=1+O(tp_1^{-1}),
$
we have
\begin{equation*}
|R_M|=|R_A|\prod_{i=1}^t\frac{p_i+1}{2}=|R_A|m2^{-t}(1+O(tp_1^{-1})), 
\end{equation*}
and hence
\begin{equation*}
\frac{M}{|R_M|}=A|R_A|^{-1}2^t(1+O(tp_1^{-1}))=A|R_A|^{-1}2^t+O((\log M)^{1-C_0})
\end{equation*}
and
\begin{equation}\label{5.14}
\frac{2M}{|R_M|^2}=M2^{t+1}A|R_A|^{-1}+O(M(\log M)^{1-C_0}).
\end{equation}
Putting (\ref{5.12}), (\ref{5.13}), and (\ref{5.14}) together and recalling that $C_0>2$, we conclude the proof of Theorem \ref{th1.5}.



\section{Proof of Theorem \ref{th1.4}} \label{Sec6}

Let $X>0$ be a large number and $\O(X)=\{M\leq X: M\in\O \}$. We first prove the lower bound for $|\O(X)|$. To do this, we consider the set $\O_1(X)$ of sufficiently large positive integers $\sqrt{X}<M\leq X$ such that

\begin{itemize}
	
	\item[(i)] $M$ is square-free;
	
	\item[(ii)] $0.9\log\log X < \o(M) < 1.05\log\log X$;	
	
	\item[(iii)] $M$ has the representation $M=Am$, where $P^-(m)>(\log X)^{C_0}$ and \\ $3\leq A\leq0.5(\log X)^{0.1}$.
	
\end{itemize}
Clearly, $\O_1(X)\subseteq \O(X)$. We are going to show that $|\O_1(X)|= (\eta+o(1))X$, where $\eta=e^{-\gamma}\frac{3}{5\pi^2C_0}$ and $\gamma$ is the Euler constant. It is well-known that the number of $M\leq X$ violating (ii) is $O(X(\log X)^{-c})$ for some absolute constant $c>0$ (see, for example, \cite{Ten}, Exercise 04). Further, let $S(X)$ be the set of square-free $m\leq X$ such that $P^-(m)>(\log X)^{C_0}$. We are aiming to prove that
\begin{equation}\label{6.1}
|S(X)| = \frac{e^{-\gamma}X}{C_0\log\log X}+O\left(\frac{X}{(\log\log X)^2}\right). 
\end{equation}
Set $z=(\log X)^{C_0}$ and $P(z)=\prod_{p\leq z}p$. Obviuosly $S(X) = S_1\setminus S_2$, where 
$$S_1=\{m\leq X: (m,P(z))=1\}
$$
and
$$S_2=\{m\leq X: \exists p>z \mbox{ with } p^2|m \}.
$$
Standard sieve methods (see, for example, \cite{Mur}, Exercises 9.1.1 and 9.1.9) yield  that 
\begin{equation*} 
|S_1| = \frac{e^{-\gamma}X}{\log z}+O\left(\frac{X}{\log^2 z}\right) = \frac{e^{-\gamma}X}{C_0\log\log X}+O\left(\frac{X}{(\log\log X)^2}\right); 
\end{equation*}
also we have
\begin{equation*}
|S_2|\leq \sum_{p>z}\left[\frac{X}{p^2}\right] \leq Xz^{-1} = X(\log X)^{-C_0}.
\end{equation*}
These two estimates imply (\ref{6.1}). 

Now for any $A\leq 0.5(\log X)^{0.1}$ we have $\log\log (X/A)=\log\log X+O\left(\frac{\log\log X}{\log X}\right)$ and thus 
$$|S(X/A)|=\frac{e^{-\gamma}X}{C_0A\log\log X}+O\left(\frac{X}{A(\log\log X)^2}\right).
$$
Also it is well-known that $\sum_{A\leq y}\mu^2(A)=\frac{6}{\pi^2}y+O(\sqrt{y})$; from here we have $\sum_{3\leq A\leq y}\frac{\mu^2(A)}{A}=\frac{6}{\pi^2}\log y+O(1)$. Thus, using (\ref{6.1}), we obtain
\begin{multline*}
|\O_1(X)| = \sum_{3\leq A\leq 0.5(\log X)^{0.1}} \mu^2(A)|S(X/A)|+O\left(\frac{X}{(\log X)^c}\right) = \\ 
\frac{e^{-\gamma}X}{C_0\log\log X}\sum_{3\leq A\leq0.5(\log X)^{0.1}}\frac{\mu^2(A)}{A}+o(X)=(\eta+o(1))X.
\end{multline*}

To prove the upper bound $|\O(X)|$, we consider the set $\O_2(X)$ of positive integers $\sqrt{X}<M\leq X$ such that

\begin{itemize}
	
	\item[(i')] $M$ is square-free;
	
	\item[(ii')] $0.85\log\log X < \o(M) < 1.1\log\log X$;	
	
	\item[(iii')] $M$ has the representation $M=Am$, where $P^-(m)>(0.5\log X)^{C_0}$ and \\ $3\leq A\leq(\log X)^{0.1}$.

\end{itemize}

Arguing as before, we see that $|\O_2(X)|=(\eta+o(1))X$. Finally, any $M\in\O(X)$ with $M>\sqrt{X}$ belongs to $\O_2(X)$, and thus $|\O(X)|\leq(\eta+o(1))X$. 

This completes the proof of Theorem \ref{th1.4}.



\section{Proof of the identity (\ref{1.3})} \label{Sec7}

We have
\begin{equation}\label{7.1}
{M \choose k}s(k)=\sum_{|U|=k}S(U)=\frac{1}{k}\sum_{x\in\mathbb{Z}_M}\sum_{\substack{|U|=k\\mathbf U\ni x}}S(U)=\frac{M}{k}\sum_{\substack{|U|=k\\mathbf U\ni 0}}S(U).
\end{equation}
Set $\ensuremath{\mathcal{A}}_{M,k}=\left\{\overline{x}=(x_1,\ldots,x_k)\in \mathbb{N}^k : \sum_{i=1}^kx_i=M\right\}$; then $|\ensuremath{\mathcal{A}}_{M,k}|={M-1 \choose k-1}$. Note that a set $U=\{0=u_1<u_2<\ldots<u_k<M\}\subseteq \mathbb{Z}_M$ containing $0$ is uniquely determined by a $k$-tuple $\overline{x}\in \ensuremath{\mathcal{A}}_{M,k}$ of the distances between its elements. Then by (\ref{7.1}) and the symmetry
$$
{M-1 \choose k-1}s(k)=\sum_{\substack{|U|=k\\mathbf U\ni 0}}S(U) = \sum_{\overline{x}\in\ensuremath{\mathcal{A}}_{M,k}}\sum_{i=1}^k{x_i^2}=k\sum_{\overline{x}\in\ensuremath{\mathcal{A}}_{M,k}}{x_1^2}.
$$
Further, the number of $\overline{x}\in\ensuremath{\mathcal{A}}_{M,k}$ with $x_1=a$ (here $a=1,...,M-k+1$) is equal to $|\ensuremath{\mathcal{A}}_{M-a,k-1}|={M-a-1 \choose k-2}$. Thus
\begin{equation}\label{s(k)2}
{M-1 \choose k-1}s(k)=k\sum_{\nu=1}^{M-k+1}a^2{M-1-a \choose k-2}.
\end{equation}
It remains to compute the latter sum. By induction on $v$ it is easy to prove the identities (first (\ref{7.3}), then using it, (\ref{7.4}), and then (\ref{7.5}))
\begin{equation}\label{7.3}
\sum_{a=0}^v{u+v-a \choose u} = {u+v+1 \choose u+1},
\end{equation}
\begin{equation}\label{7.4}
\sum_{a=1}^va{u+v-a \choose u} = {u+v+1 \choose u+2},
\end{equation}
\begin{equation}\label{7.5}
\sum_{a=1}^va^2{u+v-a \choose u} = 2{u+v+1 \choose u+3}+{u+v+1 \choose u+2}.
\end{equation}
Using (\ref{7.5}) for $u=k-2$ and $v=M-k+1$, we get from (\ref{s(k)2}) 
$$s(k)=k\frac{2{M \choose k+1}+{M \choose k}}{{M-1 \choose k-1}}=M\frac{2M-k+1}{k+1}\,,
$$
as desired.


\bigskip 


\textbf{Acknowledgements.} This work is supported by the Russian Science Foundation under grant 19--11--00001. The author is a Young Russian Mathematics award winner and would like to thank its sponsors and jury. The author also would like to thank Sergei Konyagin and Yuri Malykhin for helpful discussions, and Pavel Sobyanin and Konstantin Olmezov for computational work concerned with the values $f_A(0.5)$ for small $A$. 


