| Sbornik: Mathematics |
|
|
|
|
|
Prime avoiding numbers form a basis of order M. R. Gabdullinab, A. O. Radomskiic a Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia b University of Illinois Urbana-Champaign, Champaign, IL, USA c HSE University, Moscow, Russia
Bibliographic databases:
     § 1. IntroductionLet $p_n$ be the $n$th prime number and denote the largest gap between two consecutive primes up to $X$. The Prime Number Theorem, together with a simple averaging argument, implies that $G(X)\geqslant (1+ o(1))\log X$, and Rankin [1] in 1938 was the first to prove the bound of the type
$$
\begin{equation*}
G(X)\geqslant(c+o(1))\frac{\log X \log\log X\log\log\log\log X}{(\log\log\log X)^2},
\end{equation*}
\notag
$$
improving the previous results of Westzynthius [2] and Erdős [3]. Rankin proved the bound mentioned for $c=1/3$, and in about the next 80 years this constant was increased many times, the last constant being $c=2e^{\gamma}$ owing to Pintz [4]. In 2016 Ford, Green, Konyagin and Tao [5] and, independently, Maynard [6], using different approaches, showed that $c$ can be taken arbitrarily large, thus giving an affirmative answer to a long-standing conjecture of Erdős [7]. In 2018 all these five authors together, by combining the ideas from [5] and [6], made a further breakthrough [8] by establishing that
$$
\begin{equation}
G(X)\gg \frac{\log X \log\log X \log\log\log\log X}{\log\log\log X}.
\end{equation}
\tag{1.1}
$$
The expected size of $G(X)$ is of order $(\log X)^2$ (see [9] for the precise conjecture of Cramér based on a probabilistic model of primes); this model was also refined by Granville [10] and, more recently, by Banks, Ford and Tao [11]. We also note that the best known upper bound for $G(X)$, due to Baker, Harman and Pintz [12], is $G(X)\ll X^{0.525}$, and we refer the reader to [8] for a further discussion of the quantity $G(X)$. In [13], Ford, Heath-Brown and Konyagin introduced the notion of prime avoidance. Given a positive integer $n$, let $F(n)$ denote the distance of $n$ to the nearest prime number (clearly, the maximum value of $F(n)$ taken over all $n\leqslant X$ has the same order as $G(X)$). They called $n$ a ‘prime avoiding number with constant $c$’ if
$$
\begin{equation*}
F(n)\geqslant c\frac{\log n \log\log n \log\log\log\log n}{(\log\log\log n)^2},
\end{equation*}
\notag
$$
and proved that for any positive integer $k$ there exist $c=c(k)>0$ and infinitely many perfect $k$th powers that are prime avoiding with constant $c$. Using a method from [8] Maier and Rassias [14] extended this result to $k$th prime powers and a stronger version of prime avoidance (with lower bound of the type (1.1)); see also their recent work [15]. In this paper we consider the following additive problem related to prime avoidance: can one prove that each large positive integer $N$ can be represented as the sum of two numbers $n_1$ and $n_2$, where both $F(n_1)$ and $F(n_2)$ are large in terms of $N$? The first instinct to prove such a result can be to use the technique from [8] (which, in general, follows the strategy from some previous papers, starting from [2] by Westzynthius). However, there is a general obstacle, which makes this idea unfit for our setting. In this approach one exploits a ‘smooth’ integer $m$, which is divisible by all small primes up to some (relatively small) $z$, to make sure that the majority of the $G(X)$ successive integers beginning from $m+2$ have a small prime factor; then the aim is to use larger primes to sieve out the remaining numbers and make this procedure as efficient as possible. But if we take $n_1$ and $n_2$ in accordance with this construction, then both are close to such smooth numbers, and their sum (which we want to be $N$) is also close to a smooth number and therefore not arbitrary. Thus one needs to use an entirely different method to attack the problem stated. First, it turns out that some standard technique allows us to establish the following ‘trivial’ statement. Note that the Prime Number Theorem implies that the average value of $F(n)$ (taken over $n\leqslant N$) is at least of order $\log N$. Proposition 1.1. Every sufficiently large positive integer $N$ can be represented as a sum $N=n_1+n_2$, where $F(n_i)\gg \log N$, $i=1,2$. Our goal is to improve the lower bound from this proposition by obtaining a result where $\log N$ is multiplied by some growing function. For a number $\rho\in(0,1)$ we set
$$
\begin{equation}
C(\rho)=\sup\biggl\{\delta\in\biggl(0,\frac 12\biggr)\colon \frac{6\cdot10^{2\delta}}{\log(1/(2\delta))}<\rho\biggr\}.
\end{equation}
\tag{1.2}
$$
Our main result is as follows. Theorem 1.1. Every sufficiently large positive integer $N$ can be represented as a sum $N=n_1+n_2$, where for $i=1,2$. In fact, the proof of Theorem 1.1 implies that there are at least $\exp((\log N)^{1-o(1)})$ such representations (because of many ‘good’ choices of $\mathbf{b}$ in Theorem 4.1 ). Note that numerical calculations show that $C(1/2)>1/325565$. Theorem 1.1 admits the following interpretation. Recall that a set $A\subseteq \mathbb{N}$ is called a basis of order $k$ if every sufficiently large positive integer can be represented as a sum of $k$ summands from $A$. Now consider the set
$$
\begin{equation*}
\bigl\{n\geqslant3\colon F(n)\geqslant (\log n)(\log\log n)^\delta \bigr\}
\end{equation*}
\notag
$$
(which is also kind of a set of prime avoiding numbers). Then Theorem 1.1 implies that this set is a basis of order $2$ for any $\delta<C(1/2)$. To prove Theorem 1.1 we apply the technique from the recent paper [16] by Ford, Konyagin, Maynard, Pomerance and Tao, where the authors used a hypergraph covering lemma of Pippenger–Spencer type (which was introduced in [8]) to detect long gaps in general sieved sets. To state their result, we need the following definition (the symbol $p$ always denotes a prime number). Definition 1.1. A sieving system is a collection $\mathcal{I}$ of sets $I_p \subset \mathbb{Z}/p\mathbb{Z}$ of residue classes modulo $p$ for each prime $p$. Moreover, we have the following definitions. The main result of [16] is that for such a sieving system the sieved set
$$
\begin{equation*}
S_x=S_x(\mathcal{I})=\mathbb{Z}\setminus\bigcup_{p\leqslant x}I_p
\end{equation*}
\notag
$$
(the set of integers which do not belong to any $I_p$ for all $p\leqslant x$) contains a gap of size $x(\log x)^{C(\rho)-o(1)}$, where $C(\rho)$ is defined1 in (1.2) and the rate of decay in $o(1)$ depends on $\mathcal{I}$. Despite the fact that this general bound, as applied to the Eratosthenes sieve (that is, the sieving system with $I_p=\{0\}$ for all $p$), yields only the bound
$$
\begin{equation*}
G(X) \gg (\log X)(\log\log X)^{C(1)-o(1)} \gg (\log X)(\log\log X)^{1/835},
\end{equation*}
\notag
$$
which is weaker than (1.1), it has the advantage of not dealing with ‘smooth’ numbers from the above discussion, and this is crucial for us. To deduce Theorem 1.1 we also work with the one-dimensional Eratosthenes sieving system; however, rather than one set, we need to treat the two sets $S_x-n_1$ and $S_x-N+n_1$ (for some $n_1$) simultaneously; our main goal will be to guarantee inequality (2.2). To do this we use disjoint sets of (‘large’) primes of density $1/2$ (and this is why our result involves the exponent $C(1/2)$) to handle these two sets separately. Fortunately for us, the one-dimensionality is, in fact, needed only for ‘small’ primes, and we are able to make use of it before partitioning the set of large primes. Except for dealing with two sets simultaneously, our proof actually almost repeats the proof of the main result in [16]. However, owing to some new technical issues, there are not so many things from [16] we can use without any changes, and so we decide to provide the full proof in spite of a considerable intersection with the text of [16]. The paper is organized as follows. In § 2 we prove Proposition 1.1 (this is relatively short and based on some ideas we need for our main result); at the same time, we reduce Theorem 1.1 to the problem of sieving out two shifts of $S_{x/2}$. In § 3 we give an outline of the next part of the proof and introduce the necessary notation. The arguments in §§ 4–6 are analogous to those in §§ 3–5 of [16], and our Theorems 4.1 and 5.1 are modifications of Theorems 2 and 3 of [16]. AcknowledgementThe authors would like to thank Sergei Konyagin for introducing them to the problem. § 2. Preliminaries and proof of Proposition 1.1In this section we provide a proof of Proposition 1.1 to illustrate some parts of the general strategy in a more simple context and also make the first reduction of Theorem 1.1. This proof is actually similar to the proof of (1.8) in [16] (which shows the existence of a gap of length $\gg x$ in $S_x$), with the difference that, again, we have to handle two sets instead of one. Proof of Proposition 1.1. Given a number $x\geqslant 2$, let
$$
\begin{equation*}
S_x=\{n\in \mathbb{Z}\colon n\not\equiv0 \ (\operatorname{mod}p) \text{ for each } p\leqslant x\}.
\end{equation*}
\notag
$$
Clearly, $S_x$ is a periodic set with period $P(x)=\prod_{p\leqslant x}p$, which contains all primes larger than $x$. Let $z=x/2$, and let $b'\in \mathbb{Z}/P(z)\mathbb{Z}$ be chosen uniformly at random. We consider the random sets
$$
\begin{equation*}
A_{b'}:=(S_z-b')\cap[-y,y] \quad\text{and}\quad A_{N-b'}:=(S_z-N+b')\cap[-y,y],
\end{equation*}
\notag
$$
where $y=\lfloor 0.08x \rfloor$, and, for a set $S\subset\mathbb{Z}$ and an integer $b$, we write $S-b$ for the set $\{s-b\colon s\in S\}$. We have
$$
\begin{equation*}
\begin{aligned} \, \mathbb{E}|A_{b'}| &=\mathbb{E}\sum_{|n|\leqslant y}1_{n\in S_z-b'}=\sum_{|n|\leqslant y}\prod_{p\leqslant z}\mathbb P(b'\not\equiv -n\ (\operatorname{mod}p)) \\ &=\sum_{|n|\leqslant y}\prod_{p\leqslant z}\biggl(1-\frac1p\biggr)=\frac{(2e^{-\gamma}+o(1))y}{\log z}, \end{aligned}
\end{equation*}
\notag
$$
where $\gamma$ is the Euler constant and, similarly,
$$
\begin{equation*}
\mathbb{E}|A_{N-b'}|=\frac{(2e^{-\gamma}+o(1))y}{\log z}.
\end{equation*}
\notag
$$
Therefore, if $x$ is large enough, then Thus, there is a choice of $b'$ modulo $P(z)$ such that
Let $P_{z,x}=\prod_{z<p\leqslant x}p$ and
$$
\begin{equation*}
S_{z,x}=\{n\in\mathbb{Z}\colon n\not\equiv 0 \ (\operatorname{mod}p)\ \forall p\in(z,x]\}.
\end{equation*}
\notag
$$
Now we choose a number $b$ modulo $P(x)$. We set $b\equiv b'\pmod{P(z)}$ and claim that there is a choice of $b \pmod{P_{z,x}}$ (denoted by $b''$) such that
$$
\begin{equation}
(S_x-b)\cap[-y,y]=(S_x-N+b)\cap [-y,y] = \varnothing.
\end{equation}
\tag{2.1}
$$
To see that this is possible, note that
$$
\begin{equation*}
S_x-b=\{n\in \mathbb{Z}\colon n\not\equiv -b \ (\operatorname{mod}p) \ \forall\, p\leqslant x\} = (S_z-b')\cap (S_{z,x}-b'').
\end{equation*}
\notag
$$
Further, for each element $m\in A_{b'}$ we take a prime $q\in(z,x]$ and, using the Chinese Remainder Theorem, define $b\equiv b_q\pmod q$ such that $m\equiv -b_q \pmod q$; thus, $m\notin S_{z,x}-b''$ and so $m\notin S_x-b$. We proceed similarly for each $m\in A_{N-b'}$. Since there are $(0.5+o(1))x/\log x$ primes in $(z,x]$ and at most $0.4x/\log x$ of the numbers $m\in A_{b'}\cup A_{N-b'}$ have survived, it is possible to perform this ‘clean-up’ stage.
To finish the proof we set $f(n)=\min\{|n-l|\colon l\in S_x\}$. Then equality (2.1) means that
$$
\begin{equation*}
f(b)\geqslant y\quad\text{and} \quad f(N-b)\geqslant y
\end{equation*}
\notag
$$
for our choice of $b\pmod{P(x)}$. Now we choose $x\approx \log (N/2)$ to be the maximum number such that $P(x)\leqslant N/2$. Thus we see that it is possible to select this $b$ so that $b\in [N/4, 3N/4]$; then $N-b\in [N/4,3N/4]$ too. Finally, since $\{{N^{1/2}<p\leqslant N}\} \subset S_x$, we obtain and, similarly, $F(N-b)\gg \log N$. This completes the proof of Proposition 1.1. Now we see that to prove Theorem 1.1 it is enough to show that for any fixed $\delta<C(1/2)$ and $y=\lceil x(\log x)^{\delta} \rceil$ there exists a choice of $b$ modulo $P(x/2)$ such that
$$
\begin{equation}
\bigl|\bigl((S_{x/2}-b)\cup (S_{x/2}-N+b)\bigr)\cap [-y,y]\bigr| \leqslant \biggl(\frac12-\varepsilon\biggr)\frac{x}{\log x}
\end{equation}
\tag{2.2}
$$
for some $\varepsilon>0$. Then arguing in accordance with the clean-up stage of the above proof, one can easily obtain that both $F(b)$ and $F(N-b)$ are $\gg (\log N)(\log\log N)^{\delta}$, and Theorem 1.1 follows. Note that the condition $\delta<C(1/2)$ is equivalent to (recall the definition (1.2) of $C(\rho)$)
$$
\begin{equation}
\frac{6\cdot10^{2\delta}}{\log(1/(2\delta))}<\frac12;
\end{equation}
\tag{2.3}
$$
we use it in this form in § 5.
§ 3. Notation and outlineThroughout the proof of our main result (Theorem 1.1) we use positive parameters $K$, $\xi$ and $M$, which we describe below; one can think of them as being fixed for most of the time (in fact, it is only at the end of § 5 that the precise choice of them is important). The implied constant in $\ll$ and related order estimates can depend on these parameters. We will rely on probabilistic methods; boldface symbols such as $\mathbf{S}'$, $\boldsymbol{\lambda}$ and $\mathbf{n}$ denote random variables (sets, functions, numbers and so on), and the corresponding regular symbols $S'$, $\lambda$ and $n$ denote deterministic counterparts of these variables. For fixed $\delta\in (0,1/2)$ satisfying (2.3) we set and Let $\xi>1$ be a real number (which we will eventually choose to be close to $1$), and let
$$
\begin{equation*}
\mathfrak H=\biggl\{ H\in \{1,\xi, \xi^2,\dots\}\colon \frac{2y}{x} \leqslant H\leqslant \frac{y}{\xi z}\biggr\},
\end{equation*}
\notag
$$
so that each $H$ obeys the inequality
$$
\begin{equation}
2(\log x)^{\delta}\leqslant H\leqslant \frac{y}{z} = \frac{(\log x)^{1/2}}{\log\log x}.
\end{equation}
\tag{3.3}
$$
For each $H$ and $i\in\{1,3\}$ let $\mathcal{Q}_{H,i}$ be the set of primes $i\pmod{4}$ in the interval $(y/(\xi H),y/H]$. Note that
$$
\begin{equation}
|\mathcal Q_{H,i}|\sim \biggl(1-\frac 1\xi\biggr)\frac{y}{2H\log x}
\end{equation}
\tag{3.4}
$$
whenever $x$ is large enough in terms of $\xi$. Let
$$
\begin{equation*}
\mathcal Q=\bigcup_{H\in\mathfrak H}(\mathcal Q_{H,1}\cup\mathcal Q_{H,3})
\end{equation*}
\notag
$$
and for each $q\in \mathcal{Q}$ let $H_q$ denote the unique $H$ such that $q\in \mathcal{Q}_{H,1}\cup\mathcal{Q}_{H,3}$, which is equivalent to Also let $M$ be a number such that As in § 2, we use the notation
$$
\begin{equation*}
S_z=\{n\in\mathbb{Z}\colon n\not\equiv 0 \ (\operatorname{mod}p) \text{ for all } p\leqslant z\}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
S_{z,u}=\{n\in\mathbb{Z}\colon n\not\equiv 0 \ (\operatorname{mod}p) \text{ for all } z<p\leqslant u\}.
\end{equation*}
\notag
$$
We adopt the abbreviations
$$
\begin{equation}
\begin{gathered} \, P=P(z)=\prod_{p\leqslant z}p, \qquad \sigma=\sigma(z)=\prod_{p\leqslant z}\biggl(1-\frac1p\biggr), \\ \mathbf S'=S_z-\mathbf b\quad\text{and} \quad \mathbf S''=S_z-N+\mathbf b, \end{gathered}
\end{equation}
\tag{3.6}
$$
where $\mathbf{b}$ is a residue class chosen uniformly at random in $\mathbb{Z}/P(z)\mathbb{Z}$; thus, both $\mathbf{S}'$ and $\mathbf{S}''$ are random shifts of $S_z$. For fixed $H\in \mathfrak{H}$, we also set
$$
\begin{equation}
\begin{gathered} \, P_1=\prod_{p\leqslant H^M}p, \qquad \sigma_1=\sigma(H^M), \qquad \mathbf b_1\equiv \mathbf b \ (\operatorname{mod}P_1), \\ \mathbf S'_1=S_{H^M}-\mathbf b_1, \qquad \mathbf S''_1=S_{H^M}-N+\mathbf b_1 \end{gathered}
\end{equation}
\tag{3.7}
$$
and
$$
\begin{equation}
\begin{gathered} \, P_2=\prod_{H^M<p\leqslant z}p, \qquad \sigma_2=\sigma(H^M,z), \qquad \mathbf b_2\equiv \mathbf b \ (\operatorname{mod}P_2), \\ \mathbf S'_2=S_{H^M,z}-\mathbf b_2, \qquad \mathbf S''_2=S_{H^M,z}-N+\mathbf b_2, \end{gathered}
\end{equation}
\tag{3.8}
$$
where $\sigma(H^M,z)=\prod_{H^M<p\leqslant z}(1-1/p)$. For each $H\in\mathfrak{H}$ we obviously have
$$
\begin{equation}
P=P_1P_2, \qquad \sigma=\sigma_1\sigma_2, \qquad \mathbf S'=\mathbf S'_1\cap \mathbf S'_2\quad\text{and} \quad \mathbf S''=\mathbf S''_1\cap \mathbf S''_2.
\end{equation}
\tag{3.9}
$$
Note that all quantities defined in (3.7) and (3.8) depend on $H$ and $M$; however, we do not indicate this dependence for brevity (the values of $H$ and $M$ will always be clear from the context). Finally, we set
$$
\begin{equation}
\mathbf{AP}'(KH_q; q,n)=\{n+qh\colon 1\leqslant h\leqslant KH_q\}\cap \mathbf S_1'
\end{equation}
\tag{3.10}
$$
and
$$
\begin{equation}
\mathbf{AP}''(KH_q; q,n)=\{n+qh\colon 1\leqslant h\leqslant KH_q\}\cap \mathbf S_1'',
\end{equation}
\tag{3.11}
$$
where $K$ is a positive integer which will be chosen large enough, and, for $q\equiv1\pmod4$,
$$
\begin{equation}
\boldsymbol{\lambda}(H_q; q,n)= \begin{cases} \sigma_2^{-|\mathbf{AP}'(KH_q;q,n)|} &\text{if } \mathbf{AP}'(KH_q; q,n) \subset \mathbf S'_2, \\ 0 &\text{otherwise}, \end{cases}
\end{equation}
\tag{3.12}
$$
while for $q\equiv3\pmod4$,
$$
\begin{equation}
\boldsymbol{\lambda}(H_q; q,n)= \begin{cases} \sigma_2^{-|\mathbf{AP}''(KH_q;q,n)|} &\text{if } \mathbf{AP}''(KH_q; q,n) \subset \mathbf S''_2, \\ 0 &\text{otherwise}. \end{cases}
\end{equation}
\tag{3.13}
$$
So for each $q\in\mathcal{Q}$, the weights $\boldsymbol{\lambda}(H_q;q,n)$ are random functions which depend on $\mathbf{b}$. Now we give a brief outline of the proof of (2.2). As in [16], there are three main steps. 1. The uniform random stage. We choose $\mathbf{b}$ modulo $P(z)$ uniformly at random; this is equivalent to choosing $b \pmod p$ randomly with uniform probability, independently for each $p\leqslant z$. Then, first of all, we can easily guarantee that both sets $\mathbf{S}'\cap[-y,y]$ and $\mathbf{S}''\cap[-y,y]$ have size of about $2\sigma y$ (see Remark 5.1 below). We also show that with high probability the sets $\mathbf{S}_1'$, $\mathbf{S}_2'$, $\mathbf{S}_1''$ and $\mathbf{S}_2''$ behave as we need them to for all scales $H\in\mathfrak{H}$. 2. The greedy stage. Having chosen an appropriate $b\pmod{P(z)}$ we continue sieving out the sets $S'\cap[-y,y]$ and $S''\cap[-y,y]$. They have a small intersection, so we must work with both of them separately, by using disjoint subsets of ‘large’ (lying between $z$ and $x/2$) primes $\{q\in\mathcal{Q}\colon q\equiv1\pmod4\}$ and $\{q\in\mathcal{Q}\colon q\equiv3\pmod4\}$ of density $1/2$, respectively. To establish (2.2), we select $b$ modulo $P(z,x/2)$ randomly, but depending on the choice of $b$ modulo $P(z)$. Slightly more precisely, for each prime $q\in(z,x/2]$ such that $q\equiv1\pmod4$ we select $b\equiv b_q \pmod q$ so that $\{b_q+kq\colon k\in\mathbb{Z}\}$ knocks out nearly as many elements of $(S_z-b) \cap [-y,y]$ as possible; we do the same for the primes $q\in(z,x/2]$ such that $q\equiv3\pmod4$, to sieve out almost all of $(S_z-N+b)\cap[-y,y]$. This can be done using the so-called hypergraph covering theorem (Lemma 4.1 below). 3. The clean-up stage. Finally, as we saw in § 2, one can use the remaining primes in $(x/2,x]$ to ‘kill’ all numbers in both $S'\cap[-y,y]$ and $S''\cap[-y,y]$ that survived after the greedy stage, and this actually completes the proof of (2.2). We refer the interested reader to [16] for a more detailed discussion of the method. In § 4 we reduce inequality (2.2) to Theorem 4.1, which, in turn, is reduced to Theorem 5.1 in § 5. The final section (§ 6) is devoted to the proof of Theorem 5.1. § 4. Greedy sieving using hypergraph coveringRecall that $\mathbf{S}'$ and $\mathbf{S}''$ are the random sets $(S_z-\mathbf{b})$ and $(S_z-N+\mathbf{b})$, respectively, where $\mathbf{b}$ is chosen uniformly at random from $\mathbb{Z}/P\mathbb{Z}$. As mentioned above, by $S'$ and $S''$ we denote their realizations (with respect to some choice of $b$); the same is applied to the random weights $\boldsymbol{\lambda}$. Theorem 4.1. Fix $\delta$ satisfying (2.3) and suppose that $M-6$, $1/K$ and $\xi-1$ are sufficiently small depending on $\delta$, and that $x$ is sufficiently large depending on $\delta$, $M$, $K$ and $\xi$. Then for any positive $\varepsilon<(M-6)/6$ there exist $b \pmod{P(z)}$ and sets $\mathcal{Q}'\subseteq\{q\in \mathcal{Q}\colon q\equiv1\pmod4\}$ and $\mathcal{Q}''\subseteq\{q\in \mathcal{Q}\colon q\equiv3\pmod4\}$ such that (i) the inequality
$$
\begin{equation}
\bigl|(S'\cup S'')\cap[-y,y]\bigr| \leqslant 9\sigma y
\end{equation}
\tag{4.1}
$$
holds; (ii) for each $q\in \mathcal{Q}'\cup \mathcal{Q}''$
$$
\begin{equation}
\sum_{-(K+1)y<n\leqslant y}\lambda(H_q;q,n)=\biggl(1+O\biggl(\frac{1}{(\log x)^{\delta(1+\varepsilon)}}\biggr)\biggr)(K+2)y;
\end{equation}
\tag{4.2}
$$
(iii) for all but at most $x/(10\log x)$ elements $n$ of $S'\cap[-y,y]$
$$
\begin{equation}
\sum_{q\in \mathcal Q'}\sum_{h\leqslant KH_q}\lambda(H_q;q,n-qh)= \biggl(C_2'+O\biggl(\frac{1}{(\log x)^{\delta(1+\varepsilon)}}\biggr)\biggr)(K+2)y,
\end{equation}
\tag{4.3}
$$
and for all but at most $x/(10\log x)$ elements $n$ of $S''\cap[-y,y]$ where $C_2'$ and $C_2''$ are some quantities independent of $n$ and such that Theorem 4.1 can be considered as a preparation to the greedy stage of sieving out the sets $S'$ and $S''$ by using large primes in $(z,x/2)$. After fixing an appropriate $b\pmod{P(z)}$ and obtaining disjoint sets $\mathcal{Q}'$ and $\mathcal{Q}''$ to work with $S'$ and $S''$, respectively, we will be in a position to apply the following lemma (which is Lemma 3.1 of [16]) to deduce Theorem 1.1 from Theorem 4.1. Lemma 4.1 (on hypergraph covering). Suppose that $0<\delta\leqslant1/2$ and $K\geqslant1$, let $y\geqslant y_0(\delta,K)$ where $y_0(\delta,K)$ ia sufficiently large, and let $V$ be a finite set such that $|V|\leqslant y$. Let $1\leqslant s\leqslant y$, and suppose that $\mathbf{e}_1,\dots,\mathbf{e}_s$ are random subsets of $V$ satisfying the following: Deduction of Theorem 1.1 from Theorem 4.1. Let $b$, $\mathcal{Q}'$ and $\mathcal{Q}''$ be from Theorem 4.1. We use the hypergraph covering lemma (Lemma 4.1). Let and We aim to show that there are choices $n_q$ of $\mathbf{n}_q$ such that the corresponding sets $e_q'$ and $e_q''$ obey the inequalities
$$
\begin{equation}
\biggl|V'\setminus \bigcup_{q\in \mathcal Q'}e_q'\biggr| \leqslant \frac{x}{10\log x}
\end{equation}
\tag{4.13}
$$
and
$$
\begin{equation}
\biggl|V''\setminus \bigcup_{q\in \mathcal Q''}e_q''\biggr| \leqslant \frac{x}{10\log x}.
\end{equation}
\tag{4.14}
$$
Once this is done, we can set $b\equiv -n_q \pmod{q}$ for $q\in \mathcal{Q}'$ and $b\equiv n_q+N \pmod{q}$ for $q\in Q''$ and make an arbitrary choice of $b\pmod{q}$ for $q\in(z,x/2]\setminus (\mathcal{Q}'\cup \mathcal{Q}'')$. Then, since for each $q\in \mathcal{Q}'$
$$
\begin{equation*}
e_q' \subset \{n\in \mathbb{Z}\colon n\equiv n_q \ (\operatorname{mod}q) \}
\end{equation*}
\notag
$$
and for each $q\in \mathcal{Q}''$
$$
\begin{equation*}
e_q'' \subset \{n\in \mathbb{Z}\colon n\equiv n_q \ (\operatorname{mod}q) \},
\end{equation*}
\notag
$$
we obtain
$$
\begin{equation*}
\begin{aligned} \, |(S_{x/2}-b)\cap[-y,y]| &\leqslant |(S'\cap[-y,y])\setminus V'| +\biggl|V'\setminus \bigcup_{q\in \mathcal Q'}e_q'\biggr| \\ &\leqslant \frac{x}{10\log x}+\frac{x}{10\log x}=\frac{x}{5\log x} \end{aligned}
\end{equation*}
\notag
$$
and, similarly,
$$
\begin{equation*}
\begin{aligned} \, |(S_{x/2}-N+b)\cap[-y,y]| &\leqslant |(S''\cap[-y,y])\setminus V''| +\biggl|V''\setminus \bigcup_{q\in \mathcal Q''}e_q''\biggr| \\ &\leqslant \frac{x}{10\log x}+\frac{x}{10\log x}=\frac{x}{5\log x}, \end{aligned}
\end{equation*}
\notag
$$
and (2.2) follows. We apply the hypergraph covering lemma twice, to $V'$ and $V''$, to obtain (4.13) and (4.14), respectively. These two applications are quite similar, so we consider only the one concerned with $V'$. We take $s=|\mathcal{Q}'|$, $\{\mathbf{e}_1,\dots,\mathbf{e}_s\}=\{\mathbf{e}_q'\colon q\in \mathcal{Q}'\}$ and $C_2'$ from Theorem 4.1, and Then using (4.1) we obtain
$$
\begin{equation*}
C_3\eta|V'| \leqslant C_3\eta |S'\cap[-y,y]| \leqslant \frac{9\sigma y}{100(\log x)^{\delta}}\sim \frac{9e^{-\gamma}y}{100(\log x)^{\delta}\log z}\leqslant \frac{x}{10\log x}
\end{equation*}
\notag
$$
for $x$ large enough, and (4.13) follows from (4.11). Thus it suffices to verify the conditions of the hypergraph covering lemma. First, by (3.1),
$$
\begin{equation*}
|\mathbf e'_{q}| \leqslant KH_q \leqslant \frac{Ky}{z} \leqslant \frac{K(\log x)^{1/2}}{\log\log x} \leqslant \frac{K(\log y)^{1/2}}{\log\log y},
\end{equation*}
\notag
$$
so (4.6) follows. Further, let $n\in V'$ and $q\in \mathcal{Q}'$. By (4.12), (4.2) and (3.1),
$$
\begin{equation*}
\begin{aligned} \, \mathbb P(n\in \mathbf e_q') &= \sum_{h=1}^{\lfloor KH_q \rfloor}\mathbb P(\mathbf n_q=n-qh) \ll y^{-1}\sum_{h\leqslant KH_q}\lambda(H_q; q,n-qh) \\ &\ll y^{-1}H_q\sigma_2^{-KH_q} \leqslant y^{-9/10}, \end{aligned}
\end{equation*}
\notag
$$
and (4.7) follows. From (4.3) we also have
$$
\begin{equation*}
\begin{aligned} \, \sum_{q\in \mathcal Q'}\mathbb P(n\in \mathbf e_q') &= \sum_{q\in \mathcal Q'}\sum_{h\leqslant KH_q}\frac{\lambda(H_q; q,n-qh)}{\sum_{-(K+1)y<n'\leqslant y}\lambda(H_q;q,n')} \\ &=C_2'+O\bigl((\log x)^{-\delta(1+\varepsilon)}\bigr), \end{aligned}
\end{equation*}
\notag
$$
which confirms (4.9). Now we turn to (4.8). If both $v$ and $v'$ lie in $\mathbf{e}_q$, then $q$ divides $|v-v'|$, which is at most $2y$. But $q>z>\sqrt{2y}$, thus there can be at most one such $q$ for any fixed $v\neq v'$. Therefore, (4.8) follows from (4.7). This completes the proof of (2.2), and thus Theorem 1.1 follows from Theorem 4.1. § 5. The third reductionIn this section we deduce Theorem 4.1 from the following theorem. Theorem 5.1. Let $M\geqslant2$. Then (i) the inequality
$$
\begin{equation}
\mathbb{E}|\mathbf S'\cap[-y,y]|=\mathbb{E}|\mathbf S''\cap[-y,y]|=\sigma(2y+1)
\end{equation}
\tag{5.1}
$$
holds; (ii) for every $H\in \mathfrak{H}$, every $j\in\{0,1,2\}$ and $i\in\{1,3\}$,
$$
\begin{equation}
\mathbb{E}\sum_{q\in \mathcal Q_{H,i}}\biggl(\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H;q,n)\biggr)^j = \biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)((K+2)y)^j|\mathcal Q_{H,i}|;
\end{equation}
\tag{5.2}
$$
(iii) for every $H\in \mathfrak{H}$ and $j\in\{0,1,2\}$,
$$
\begin{equation}
\begin{aligned} \, \notag &\mathbb{E}\sum_{n\in \mathbf S'\cap[-y,y]}\biggl(\sum_{q\in \mathcal Q_{H,1}}\sum_{h\leqslant KH}\boldsymbol{\lambda}(H;q,n-qh)\biggr)^j \\ &\qquad = \biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)\biggl(\frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor }{\sigma_2}\biggr)^j\sigma (2y+1), \end{aligned}
\end{equation}
\tag{5.3}
$$
and
$$
\begin{equation}
\begin{aligned} \, \notag &\mathbb{E}\sum_{n\in \mathbf S''\cap[-y,y]}\biggl(\sum_{q\in \mathcal Q_{H,3} }\sum_{h\leqslant KH}\boldsymbol{\lambda}(H;q,n-qh)\biggr)^j \\ &\qquad= \biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)\biggl(\frac{|\mathcal Q_{H,3}|\cdot\lfloor KH\rfloor}{\sigma_2}\biggr)^j\sigma (2y+1). \end{aligned}
\end{equation}
\tag{5.4}
$$
We recall that in Theorem 5.1 the random variables $\mathbf{S}'$, $\mathbf{S}''$ and $\boldsymbol{\lambda}$ are defined in terms of the random variable $\mathbf{b}$, chosen uniformly in $\mathbb{Z}/P\mathbb{Z}$, rather than by means of the random variables $\mathbf{n}_q$ we used in § 4. Remark 5.1. It can be shown that Deduction of Theorem 4.1 from Theorem 5.1. First we show that (4.1) holds with probability at least $1/2$. From (5.1) we see that Now we work on parts (ii) and (iii) of Theorem 4.1. Fix $H\in\mathfrak{H}$. From (5.2) we obtain
$$
\begin{equation}
\mathbb{E}\sum_{q\in \mathcal Q_{H,1}}\biggl(\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H;q,n) - (K+2)y\biggr)^2 \ll \frac{y^2|\mathcal Q_{H,1}|}{H^{M-2}}.
\end{equation}
\tag{5.6}
$$
Now let $\boldsymbol{\mathcal Q}_H'$ be the (random) set of $q\in \mathcal{Q}_{H,1}$ for which
$$
\begin{equation}
\biggl|\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H;q,n) - (K+2)y\biggr| \leqslant \frac{y}{H^{1+\varepsilon}}.
\end{equation}
\tag{5.7}
$$
By estimating the left-hand side of (5.6) from below by the sum over $q\in \mathcal{Q}_{H,1}\setminus\boldsymbol{\mathcal Q}'_H$, we find that
$$
\begin{equation}
\mathbb{E}|\mathcal Q_{H,1}\setminus\boldsymbol{\mathcal Q}'_H| \ll \frac{|\mathcal Q_{H,1}|}{H^{M-4-2\varepsilon}}.
\end{equation}
\tag{5.8}
$$
Now we set
$$
\begin{equation*}
\boldsymbol{\mathcal Q}'=\bigcup_{H\in\mathfrak H}\boldsymbol{\mathcal Q}_H' \subseteq \{q\in\mathcal Q\colon q\equiv1\ (\operatorname{mod}4) \}.
\end{equation*}
\notag
$$
In a quite similar way we define the random set
$$
\begin{equation*}
\boldsymbol{\mathcal Q}''=\bigcup_{H\in\mathfrak H}\boldsymbol{\mathcal Q}_H'' \subseteq \{q\in\mathcal Q\colon q\equiv3\ (\operatorname{mod}4) \},
\end{equation*}
\notag
$$
where for each $H\in\mathfrak{H}$ we denote by $\boldsymbol{\mathcal Q}_H''$ the random set of $q\in \mathcal{Q}_{H,3}$ for which
$$
\begin{equation}
\biggl|\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H;q,n) - (K+2)y\biggr| \leqslant \frac{y}{H^{1+\varepsilon}};
\end{equation}
\tag{5.9}
$$
again, we have
$$
\begin{equation}
\mathbb{E}|\mathcal Q_{H,3}\setminus\boldsymbol{\mathcal Q}'_H| \ll \frac{|\mathcal Q_{H,3}|}{H^{M-4-2\varepsilon}}
\end{equation}
\tag{5.10}
$$
for all $H\in\mathfrak{H}$. Now we turn to condition (iii) in Theorem 4.1. Fix $H$. Similarly to (5.6), from (5.3) we have
$$
\begin{equation}
\begin{aligned} \, \notag &\mathbb{E}\sum_{n\in \mathbf S'\cap[-y,y]}\biggl(\sum_{q\in \mathcal Q_{H,1}}\sum_{h\leqslant KH}\boldsymbol{\lambda}(H;q,n-qh)-\frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor}{\sigma_2}\biggr)^2 \\ &\qquad \ll \frac{1}{H^{M-2}}\biggl(\frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor}{\sigma_2}\biggr)^2\sigma y. \end{aligned}
\end{equation}
\tag{5.11}
$$
Let $\boldsymbol{\mathcal E}'_H$ be the set of $n\in \mathbf{S}'\cap[-y,y]$ such that
$$
\begin{equation}
\biggl|\sum_{q\in \mathcal Q_{H,1}}\sum_{h\leqslant KH}\boldsymbol{\lambda}(H;q,n-qh)-\frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor}{\sigma_2}\biggr| \geqslant \frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor}{\sigma_2H^{1+\varepsilon}}.
\end{equation}
\tag{5.12}
$$
Then, since $M>6$ and $\varepsilon$ is small, (5.11) implies that
$$
\begin{equation*}
\mathbb{E}|\boldsymbol{\mathcal E}'_H| \ll \frac{\sigma y}{H^{1+2\varepsilon}},
\end{equation*}
\notag
$$
and so $|\boldsymbol{\mathcal E}'_H|\leqslant {\sigma y}/{H^{1+\varepsilon}}$ with probability $1-O(H^{-\varepsilon})$. Now we estimate the contribution of the ‘bad’ primes $q\in \mathcal{Q}_{H,1}\setminus \boldsymbol{\mathcal Q}'_H$. For each $h\leqslant KH$, from the Cauchy–Schwarz inequality (for vector functions) we obtain
$$
\begin{equation*}
\begin{aligned} \, &\mathbb{E}\sum_{q\in \mathcal Q_{H,1}\setminus\boldsymbol{\mathcal Q}'_H}\sum_{n\in \mathbf S'\cap[-y,y]}\boldsymbol{\lambda}(H;q,n-qh) \\ &\qquad \leqslant\bigl(\mathbb{E}|\mathcal Q_{H,1}\setminus\boldsymbol{\mathcal Q}'_H|\bigr)^{1/2}\biggl(\mathbb{E}\sum_{\mathcal Q_{H,1}\setminus\boldsymbol{\mathcal Q}'_H}\biggl|\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H;q,n)\biggr|^2\biggr)^{1/2}, \end{aligned}
\end{equation*}
\notag
$$
where we have extended the summation of the $\boldsymbol{\lambda}(H;q,\cdot\,)$ to the larger interval $(-(K+1)y,y]$ (note that the weights $\boldsymbol{\lambda}(H;q,\cdot\,)$ are nonnegative). Further, by the triangle inequality, (5.6) and (5.8)
$$
\begin{equation*}
\begin{aligned} \, &\mathbb{E}\sum_{\mathcal Q_{H,1}\setminus\boldsymbol{\mathcal Q}'_H}\biggl|\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H;q,n)\biggr|^2 \\ &\qquad \leqslant2\mathbb{E}\sum_{\mathcal Q_{H,1}\setminus\boldsymbol{\mathcal Q}'_H}\biggl(\biggl|\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H;q,n)-(K+2)y\biggr|^2+(K+2)^2y^2\biggr) \\ &\qquad\ll \frac{y^2|\mathcal Q_{H,1}|}{H^{M-4-2\varepsilon}}. \end{aligned}
\end{equation*}
\notag
$$
Combining the two last estimates (and using (5.8) again), after summing over all $h\leqslant KH$ we obtain
$$
\begin{equation*}
\mathbb{E}\sum_{n\in \mathbf S'\cap[-y,y]}\sum_{q\in \mathcal Q_{H,1}\setminus \boldsymbol{\mathcal Q}'_H}\sum_{h\leqslant KH} \boldsymbol{\lambda}(H;q,n-qh) \ll \frac{y|\mathcal Q_{H,1}|}{H^{M-5-2\varepsilon}}.
\end{equation*}
\notag
$$
Let $\boldsymbol{\mathcal F}'_H$ be the set of $n\in\mathbf{S}'\cap[-y,y]$ such that
$$
\begin{equation}
\sum_{q\in \mathcal Q_{H,1}\setminus \boldsymbol{\mathcal Q}'_H}\sum_{h\leqslant KH} \boldsymbol{\lambda}(H;q,n-qh) \geqslant \frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor}{\sigma_2H^{1+\varepsilon}}.
\end{equation}
\tag{5.13}
$$
Then
$$
\begin{equation*}
\mathbb{E}|\boldsymbol{\mathcal F}'_H| \ll \frac{\sigma_2y}{H^{M-5-3\varepsilon}} \ll \frac{\sigma y \log H}{H^{M-5-3\varepsilon}},
\end{equation*}
\notag
$$
and by Markov’s inequality
$$
\begin{equation*}
|\boldsymbol{\mathcal F}'_H| \leqslant \frac{\sigma y}{H^{1+\varepsilon}}
\end{equation*}
\notag
$$
with probability $1-O(H^{-(M-6-5\varepsilon)})$. Since $\varepsilon<(M-6)/6$, we have $M-6-5\varepsilon>\varepsilon$, and the last probability becomes $1-O(H^{-\varepsilon})$. Analogously, using (5.4), we can define the set $\boldsymbol{\mathcal E}''_H$ of $n\in \mathbf{S}''\cap[-y,y]$ such that
$$
\begin{equation}
\biggl|\sum_{q\in \mathcal Q_{H,3}}\sum_{h\leqslant KH}\boldsymbol{\lambda}(H;q,n-qh)-\frac{|\mathcal Q_{H,3}|\cdot\lfloor KH\rfloor}{\sigma_2}\biggr| \geqslant \frac{|\mathcal Q_{H,3}|\cdot\lfloor KH\rfloor}{\sigma_2H^{1+\varepsilon}},
\end{equation}
\tag{5.14}
$$
and the set $\boldsymbol{\mathcal F}''_H$ of $n\in \mathbf{S}''\cap[-y,y]$ such that
$$
\begin{equation}
\sum_{q\in \mathcal Q_{H,3}\setminus \boldsymbol{\mathcal Q}''_H}\sum_{h\leqslant KH} \boldsymbol{\lambda}(H;q,n-qh) \geqslant \frac{|\mathcal Q_{H,3}|\cdot\lfloor KH\rfloor}{\sigma_2H^{1+\varepsilon}};
\end{equation}
\tag{5.15}
$$
then we have
$$
\begin{equation*}
|\boldsymbol{\mathcal E}''_H|, |\boldsymbol{\mathcal F}''_H| \leqslant \frac{\sigma y}{H^{1+\varepsilon}}
\end{equation*}
\notag
$$
with probability $1-O(H^{-\varepsilon})$. Since $\sum_{H\in\mathfrak{H}}H^{-\varepsilon}\ll (\log x)^{-\delta\varepsilon}$, we see that the probability of the event that there exists $H\in\mathfrak{H}$ such that at least one of the sets $\boldsymbol{\mathcal E}'_H$, $\boldsymbol{\mathcal F}'_H$, $\boldsymbol{\mathcal E}''_H$ or $\boldsymbol{\mathcal F}''_H$ has size greater than $(\sigma y)H^{-1-\varepsilon}$ is $o(1)$. Now we are ready to make a choice of $\mathbf{b} \pmod{P(z)}$. We consider the event that (5.5) holds and that for each $H\in\mathfrak{H}$ all the four sets $\boldsymbol{\mathcal E}'_H$, $\boldsymbol{\mathcal F}'_H$, $\boldsymbol{\mathcal E}''_H$ and $\boldsymbol{\mathcal F}''_H$ have size at most $(\sigma y)H^{-1-\varepsilon}$. By the above discussion this event holds with probability at least $1/2-o(1)$). From now on, we fix $\mathbf{b}\pmod{P(z)}$ such that this event holds, and thus all of our random sets and weights become deterministic. Let
$$
\begin{equation*}
\mathcal{N}'=S'\cap[-y,y]\setminus\bigcup_{H\in\mathfrak H}(\mathcal E'_H\cup\mathcal F'_H)
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\mathcal{N}''=S''\cap[-y,y]\setminus\bigcup_{H\in\mathfrak H}(\mathcal E''_H\cup\mathcal F''_H).
\end{equation*}
\notag
$$
We verify (4.3) for $n\in\mathcal{N}'$, and (4.4) will follow from our construction in an absolutely similar way. The number of exceptional elements satisfies
$$
\begin{equation*}
\biggl|\bigcup_{H\in\mathfrak H}(\mathcal E'_H\cup\mathcal F'_H)\biggr| \leqslant \frac{\sigma y}{(\log x)^{(1+\varepsilon)\delta}},
\end{equation*}
\notag
$$
which is smaller than $x/(10\log x)$ for large $x$. We fix an arbitrary $n\in \mathcal{N}'$. For such $n$ the inequalities reverse to (5.12) and (5.13) hold, and therefore, for each $H\in\mathfrak{H}$,
$$
\begin{equation*}
\sum_{q\in \mathcal Q_{H,1}}\sum_{h\leqslant KH}\lambda(H;q,n-qh)=\biggl(1+O\biggl(\frac{1}{(\log x)^{(1+\varepsilon)\delta}}\biggr)\biggr) \frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor}{\sigma_2}
\end{equation*}
\notag
$$
by our choice of $M$. Summing over all $H\in\mathfrak{H}$, we have
$$
\begin{equation}
\sum_{q\in \mathcal Q'}\sum_{h\leqslant KH_q}\lambda(H_q;q,n-qh)=\biggl(1+O\biggl(\frac{1}{(\log x)^{(1+\varepsilon)\delta}}\biggr)\biggr)C_2'(K+2)y,
\end{equation}
\tag{5.16}
$$
where (recall that $\sigma_2=\sigma_2(H)$)
$$
\begin{equation*}
C_2'=\frac{1}{(K+2)y}\sum_{H\in\mathfrak H} \frac{|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor}{\sigma_2}.
\end{equation*}
\notag
$$
Note that $C_2'$ depends on $x$, $K$, $M$, $\xi$ and $\delta$ but not on $n$. Since
$$
\begin{equation*}
\lfloor KH \rfloor=KH\biggl(1+O\biggl(\frac 1H\biggr)\biggr)=KH(1+O(\log x)^{-\delta})
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\sigma_2^{-1}=\prod_{H^M<p\leqslant z}\biggl(1-\frac 1p\biggr)^{-1}\sim\frac{\log z}{M\log H},
\end{equation*}
\notag
$$
using (3.5) we obtain
$$
\begin{equation*}
C_2'\sim \frac{K}{(K+2)y} \cdot \frac12\biggl(1-\frac1\xi\biggr) \sum_{H\in\mathfrak H}\frac{y/H}{\log x}\cdot\frac{H\log z}{M\log H} \sim \frac{K(1-1/\xi)}{2M(K+2)}\sum_{H\in\mathfrak H}\frac{1}{\log H}
\end{equation*}
\notag
$$
as $x\to\infty$. Recalling the definition of $\mathfrak{H}$, we see that
$$
\begin{equation*}
C_2'\sim \frac{K(1-1/\xi)}{2M(K+2)\log \xi}\sum_{j}\frac{1}{j},
\end{equation*}
\notag
$$
where $j$ ranges over the interval
$$
\begin{equation*}
\frac{\delta\log\log x}{\log \xi} \leqslant j \leqslant \frac{(1/2+o(1))\log\log x}{\log \xi}.
\end{equation*}
\notag
$$
Thus we obtain
$$
\begin{equation*}
C_2'\sim \frac{K(1-1/\xi)}{2M(K+2)\log \xi}\log\frac{1}{2\delta}.
\end{equation*}
\notag
$$
Recall condition (2.3) on $\delta$ and the fact that $K$ and $x$ are sufficiently large, $M$ is sufficiently close to $6$ and $\xi$ is close enough to $1$ (all in terms of $\delta$). We may also assume without loss of generality that $\delta$ is sufficiently close to $C(1/2)$, which gives $\log(1/(2\delta))<13\cdot10^{2\delta}$. Then we see that In combination with (5.16), this implies (4.3). Arguing similarly, one can obtain (4.4) for $n\in \mathcal{N}''$. Theorem 4.1 is proved. It remains to establish Theorem 5.1. This is the aim of § 6 of the paper. § 6. Computing correlationsFirst we introduce some notation. For $H\in\mathfrak{H}$ let $\mathcal{D}_H$ be the set of square-free integers $d$ all of whose prime divisors lie in $(H^M,z]$. Further, for $A>0$ let
$$
\begin{equation}
E_A(m;H)=\sum_{d\in \mathcal D_H\setminus\{1\}}\frac{A^{\omega(d)}}{d}1_{m \equiv 0\,(\operatorname{mod}d)}.
\end{equation}
\tag{6.1}
$$
Note that $E_A(m;H)=E_A(-m;H)$. We need the following two lemmas (see Lemmas 5.1 and 5.2 in [16]). Lemma 6.1. Let $10<H<z^{1/M}$ and $1\leqslant l\leqslant 10KH$, and let $\mathcal{U}\subset \mathcal{V}$ be two finite sets such that $|\mathcal{V}|=l$. Then Remark 6.1. Lemma 5.1 in [16] is in fact formulated for the probability $\mathbb{P}(\mathcal{U}\subset \mathbf{S}_2)$, where $\mathbf{S}_2=S_{H^M,z}+\mathbf{b}_2$. However, it does not make any difference for us since it is easy to see (by making the change of variables $\mathbf{b}_2\mapsto -\mathbf{b}_2$ or $\mathbf{b}_2\mapsto -N+\mathbf{b}_2$) that $\mathbb{P}(\mathcal{U}\subset \mathbf{S}_2)=\mathbb{P}(\mathcal{U}\subset \mathbf{S}'_2)=\mathbb{P}(\mathcal{U}\subset \mathbf{S}''_2)$. Note also that a parameter $B$ is involved in this lemma, since it is related to a $B$-bounded sieving system (recall the definition of a sieving system in § 1); nevertheless, in our case $B=1$ and thus there is no dependence on $B$. Lemma 6.2. Let $10<H<z^{1/M}$, and let $(m_t)_{t\in T}$ be a finite sequence such that for some $X,R>0$ and all $d\in \mathcal{D}_H\setminus\{1\}$ and $a\in\mathbb{Z}/d\mathbb{Z}$. Then for any $A$ such that $0<A\leqslant H^M$ and any integer $j$ Now we are ready to prove Theorem 5.1. Proof of Theorem 5.1, (i). First, we notice that by making a change of variables it is easy to see that
$$
\begin{equation*}
\mathbb{E}|\mathbf S'\cap[-y,y]|=\mathbb{E}|\mathbf S''\cap[-y,y]|.
\end{equation*}
\notag
$$
Thus, it suffices to prove the claim concerned with $\mathbf{S}'$. By the linearity of expectation we obtain
$$
\begin{equation*}
\mathbb{E}|\mathbf S'\cap[-y,y]|=\sum_{-y\leqslant n\leqslant y}\mathbb P(n\in \mathbf S').
\end{equation*}
\notag
$$
Now, since $\mathbf{b}$ is taken uniformly from $\mathbb{Z}/P(z)\mathbb{Z}$, for each fixed $n$, from the Chinese Remainder Theorem we obtain
$$
\begin{equation*}
\mathbb P(n\in \mathbf S')=\prod_{p\leqslant z}\mathbb P(\mathbf b\not\equiv -n \ (\operatorname{mod}p))=\sigma,
\end{equation*}
\notag
$$
and (5.1) follows. Proof of Theorem 5.1, (ii). We prove the claim for $i=1$ (the case $i=3$ can be handled similarly). Fix $H\in\mathfrak{H}$. The case $j=0$ is trivial, and we turn to $j=1$, which is
$$
\begin{equation}
\mathbb{E}\sum_{q\in \mathcal Q_{H,1}}\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H; q,n)= \biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)(K+2)y|\mathcal Q_{H,1}|.
\end{equation}
\tag{6.3}
$$
By (3.12) the left-hand side expands as
$$
\begin{equation*}
\mathbb{E}\sum_{q\in\mathcal Q_{H,1}}\sum_{-(K+1)y<n\leqslant y}\frac{1_{\mathbf{AP}'(KH;q,n)\subset\mathbf S'_2}}{\sigma_2^{|\mathbf{AP}'(KH;q,n)|}}.
\end{equation*}
\notag
$$
Recall that, according to the definitions (3.8) and (3.10), $\mathbf{b}_1$ and $\mathbf{b}_2$ are independent, and so are $\mathbf{AP}'(KH; q,n)=\{n+qh\colon 1\leqslant h\leqslant KH\}\cap \mathbf{S}'_1$ and $\mathbf{S}'_2$. Then the above expression equals
$$
\begin{equation*}
\sum_{q\in\mathcal Q_{H,1}}\sum_{-(K+1)y<n\leqslant y}\, \sum_{b_1\, (\operatorname{mod}P_1)}\frac{\mathbb P(\mathbf b_1=b_1)}{\sigma_2^{|\operatorname{AP}'(KH;q,n)|}}\mathbb P(\operatorname{AP}'(KH; q,n)\subset\mathbf S'_2).
\end{equation*}
\notag
$$
For fixed $q$, $n$ and $b_1$ we apply Lemma 6.1 to the (deterministic) sets $\mathcal{U}=\operatorname{AP}'(KH;q,n)$ and $\mathcal{V}=\{n+qh\colon 1\leqslant h\leqslant KH\}$ and find that the left-hand side of (6.3) is equal to
$$
\begin{equation*}
\sum_{q\in \mathcal Q_{H,1}}\sum_{-(K+1)y<n\leqslant y}\biggl(1+O\biggl(H^{-(M-2)}+H^{-2}\sum_{\substack{1\leqslant h<h'\leqslant KH}}E_{2K^2H^2}(qh-qh';H) \biggr)\biggr).
\end{equation*}
\notag
$$
Now it is enough to show that, for any $1\leqslant h< h'\leqslant KH$, For future reference, we show the more general bound for each $i\in\{1,3\}$, $0<|r|\leqslant KH$, and any integer $s$. Note that $E_A(m;H)$ is an increasing function of $A$.
To show (6.4) we fix $r$ and $s$. For each $d\in\mathcal{D}_{H\setminus\{1\}}$ all prime divisors of $d$ are greater than $H^M>KH\leqslant |r|$, and so $r$ and $d$ are coprime. Hence the congruence $qr\equiv a\pmod{d}$ holds for at most one residue class $q\pmod d$. Therefore, for $d\leqslant y^{1/2}$, by the Brun–Titchmarch inequality (recall that $H\leqslant (\log y)^{1/2}$ by (3.4)) we have
$$
\begin{equation*}
\#\{q\in \mathcal Q_{H,i}\colon qr\equiv a\ (\operatorname{mod}d)\} \ll \frac{y/H}{\varphi(d)\log(y/d)} \ll \frac{y/H}{\varphi(d)\log y}.
\end{equation*}
\notag
$$
For $d>y^{1/2}$ we can forget that $q$ is restricted to be prime and trivially obtain
$$
\begin{equation*}
\#\{q\in \mathcal Q_{H,i}\colon qr\equiv a\ (\operatorname{mod}d)\} \ll \frac{y/H}{d} + 1 \ll \frac{y^{1/2}}{H}.
\end{equation*}
\notag
$$
So for each $d$ we have
$$
\begin{equation*}
\#\{q\in \mathcal Q_{H,i}\colon qr\equiv a\ (\operatorname{mod}d)\} \ll \frac{y/H}{\varphi(d)\log y}+\frac{y^{1/2}}{H}.
\end{equation*}
\notag
$$
Hence, by Lemma 6.2, using (3.4) again we obtain
$$
\begin{equation*}
\sum_{q\in Q_{H,i}} E_{8K^2H^2}(qr+s;H) \ll \frac{y/H}{\log y}\frac{H^2}{H^M}+\frac{y^{1/2}}{H}\exp(O(H^2\log\log y)) \ll \frac{|\mathcal Q_{H,i}|}{H^{M-2}},
\end{equation*}
\notag
$$
since $|\mathcal Q_{H,i}|\asymp (y/H)/\log y$ for each $i\in\{1,3\}$. So (6.4) is proved, and thus the case $j=1$ of Theorem 5.1, (ii), follows.
Now we turn to the case $j=2$ of (ii), which is
$$
\begin{equation*}
\mathbb{E}\sum_{q\in \mathcal Q_{H,1}}\biggl(\sum_{-(K+1)y<n\leqslant y}\boldsymbol{\lambda}(H; q,n)\biggr)^2= \biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)(K+2)^2y^2|\mathcal Q_{H,1}|.
\end{equation*}
\notag
$$
The left-hand side is expanded as
$$
\begin{equation*}
\mathbb{E}\sum_{q\in\mathcal Q_{H,1}}\sum_{-(K+1)y<n_1,n_2\leqslant y}\boldsymbol{\lambda}(H;q,n_1)\boldsymbol{\lambda}(H;q,n_2).
\end{equation*}
\notag
$$
First we note that for each fixed $q$ the contribution of the pairs $(n_1,n_2)$ for which $|n_1-n_2|\leqslant KH$ is negligible: indeed, there are $O(yH)$ such pairs, and each of them contributes at most $\sigma_2^{-2KH}=y^{o(1)}$, so the total contribution of such pairs is $O(y^{1+o(1)}|\mathcal{Q}_{H,1}|)$. Thus we can restrict our attention to those pairs $(n_1,n_2)$ for which the sets $\{n_\nu+qh\colon 1\leqslant h\leqslant KH\}$, $\nu=1,2$, do not intersect; let us call these pairs good. Then it is enough to show that
$$
\begin{equation}
\begin{aligned} \, \notag &\mathbb{E}\sum_{q\in\mathcal Q_{H,1}}\,\,\sum_{\substack{-(K+1)y<n_1,\,n_2\leqslant y\\(n_1,n_2) \text { is good}}}\frac{1_{\mathbf{AP}'(KH;q,n_1)\cup \mathbf{AP}'(KH;q,n_2)\subset\mathbf S'_2}}{\sigma_2^{|\mathbf{AP}'(KH;q,n_1)|+|\mathbf{AP}'(KH;q,n_2)|}} \\ &\qquad =\biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)(K+2)^2y^2|\mathcal Q_{H,1}|. \end{aligned}
\end{equation}
\tag{6.5}
$$
Arguing as in the case $j=1$, for any realization $b_1$ of $\mathbf{b}_1$ and any good pair $(n_1,n_2)$, we can apply Lemma 6.1 to
$$
\begin{equation*}
\mathcal U=\operatorname{AP}'(KH;q,n_1)\sqcup \operatorname{AP}'(KH;q,n_2)
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\mathcal V=\{n_1+qh\colon 1\leqslant h\leqslant KH\}\sqcup \{n_2+qh\colon 1\leqslant h\leqslant KH\}.
\end{equation*}
\notag
$$
Then, since
$$
\begin{equation*}
|\mathcal U|=|\operatorname{AP}'(KH;q,n_1)|+|\operatorname{AP}'(KH;q,n_2)|
\end{equation*}
\notag
$$
and $|\mathcal{V}|= 2\lfloor KH\rfloor$, we see that the left-hand side of (6.5) equals
$$
\begin{equation*}
\begin{aligned} \, & \sum_{q\in\mathcal Q_{H,1}}\,\,\sum_{\substack{-(K+1)y<n_1,\,n_2\leqslant y\\(n_1,n_2)\text{ is good}}} \biggl(1\,{+}\,O\biggl(\frac{1}{H^{M-2}}\,{+}\,H^{-2}\!\!\!\!\!\!\sum_{1\leqslant h,h'\leqslant KH}1_{h\neq h'}E_{8K^2H^2}(qh\,{-}\,qh';H) \\ &\qquad\qquad\qquad\qquad\qquad\quad +1_{n_1\neq n_2}E_{8K^2H^2}(n_1-n_2+qh-qh';H)\biggr)\biggr). \end{aligned}
\end{equation*}
\notag
$$
Recalling that all but $O(yH)$ pairs $(n_1,n_2)$ are good, we obtain from here the main term $(K+2)^2y^2|\mathcal{Q}_{H,1}|$. We also obtain acceptable error terms by using (6.4), except for the summands with $h=h'$. To handle them, we note that for any fixed $n_2$, any positive integer $d$ and any $a\pmod{d}$,
$$
\begin{equation*}
\#\{-(K+1)y<n_1\leqslant y\colon n_1-n_2 \equiv a\ (\operatorname{mod}d)\} \ll \frac{y}{d}+1.
\end{equation*}
\notag
$$
Thus, from Lemma 6.2 we obtain
$$
\begin{equation*}
\sum_{-(K+1)y<n_1, n_2\leqslant y}E_{8K^2H^2}(n_1-n_2;H) \ll \frac{y^2}{H^{M-2}}+y\exp(O(H^2\log\log y)) \ll \frac{y^2}{H^{M-2}}
\end{equation*}
\notag
$$
by (3.4). Now (6.5) and the claim for $j=2$ follow. Proof of Theorem 5.1, (iii). Fix $H$. We prove only (5.3), since (5.4) can be handled in an absolutely similar manner (the only difference between these cases is that the weights $\boldsymbol{\lambda}(H_q; q,n)$ are defined in terms of $\mathbf{S}'$ for $q\equiv1\pmod4$ and in terms of $\mathbf{S}''$ for $q\equiv3\pmod4$). The case $j=0$ follows from part (i) (that is, (5.1)), so we focus on the case $j=1$, which is
$$
\begin{equation*}
\begin{aligned} \, &\mathbb{E}\sum_{n\in \mathbf S'\cap[-y,y]}\sum_{q\in \mathcal Q_{H,1}}\sum_{h\leqslant KH}\boldsymbol{\lambda}(H;q,n-qh) \\ &\qquad= \biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)|\mathcal Q_{H,1}|\cdot\lfloor KH\rfloor\sigma_1 (2y+1). \end{aligned}
\end{equation*}
\notag
$$
It is enough to show that, for any $h\leqslant KH$,
$$
\begin{equation}
\mathbb{E}\sum_{n\in \mathbf S'\cap[-y,y]}\sum_{q\in \mathcal Q_{H,1}}\boldsymbol{\lambda}(H;q,n-qh) = \biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)|\mathcal Q_{H,1}|\sigma_1 (2y+1).
\end{equation}
\tag{6.6}
$$
According to (3.12), the left-hand side is equal to
$$
\begin{equation*}
\mathbb{E}\sum_{n\in\mathbf S'\cap[-y,y]}\sum_{q\in \mathcal Q_{H,1}}\frac{1_{\mathbf{AP}'(KH;q,n-qh)\subset \mathbf S'_2}}{\sigma_2^{|\mathbf{AP}'(KH;q,n-qh)|}}.
\end{equation*}
\notag
$$
By (3.9) the condition $n\in \mathbf{S}'\cap[-y,y]$ implies that $n\in\mathbf{S}'_1\cap[-y,y]$. On the other hand, if $n\in\mathbf{S}'_1$, then $n\in\mathbf{AP}'(KH;q,n-qh)$, and thus the condition $n\in\mathbf{S}'_2$ is covered by the condition $\operatorname{AP}'(KH;q,n-qh)\subset\mathbf{S}'_2$. So the left-hand side of (6.6) can be rewritten as
$$
\begin{equation*}
\mathbb{E}\sum_{n\in\mathbf S'_1\cap[-y,y]}\sum_{q\in \mathcal Q_{H,1}}\frac{1_{\mathbf{AP}'(KH;q,n-qh)\subset \mathbf S'_2}}{\sigma_2^{|\mathbf{AP}'(KH;q,n-qh)|}}.
\end{equation*}
\notag
$$
Recalling that $\mathbf{S}_2'$ is independent of $\mathbf{S}_1'$ and $\mathbf{AP}'(KH;q,n-qh)$ we can apply Lemma 6.1 as before and find that the left-hand side of (6.6) is
$$
\begin{equation*}
\mathbb{E}\sum_{n\in\mathbf S'_1\cap[-y,y]}\sum_{q\in \mathcal Q_{H,1}}\biggl(1+O\biggl(\frac{1}{H^{M-2}}+H^{-2}\sum_{\substack{h',h''\leqslant KH\\h'\neq h''}}E_{2K^2H^2}(qh'-qh'')\biggr)\biggr).
\end{equation*}
\notag
$$
Now, since we see that (6.6) follows from (6.4).
Now we turn to the case $j=2$ of (iii), which is
$$
\begin{equation*}
\begin{aligned} \, & \sum_{h_1,h_2\leqslant KH}\mathbb{E}\sum_{n\in\mathbf S'\cap[-y,y]}\sum_{q_1,q_2\in\mathcal Q_{H,1}}\boldsymbol{\lambda}(H;q_1,n-q_1h_1)\boldsymbol{\lambda}(H;q_2,n-q_2h_2) \\ &\qquad =\biggl(1+O\biggl(\frac{1}{H^{M-2}}\biggr)\biggr)|\mathcal Q_{H,1}|^2\cdot\lfloor KH\rfloor^2\frac{\sigma_1}{\sigma_2}(2y+1). \end{aligned}
\end{equation*}
\notag
$$
By (3.13) the left-hand side is
$$
\begin{equation}
\sum_{h_1,h_2\leqslant KH}\mathbb{E}\sum_{n\in\mathbf S'\cap[-y,y]}\sum_{q_1,q_2\in \mathcal Q_{H,1}}\frac{1_{\mathbf{AP}'(KH;q_1,n-q_1h_1)\cup \mathbf{AP}'(KH;q_2,n-q_2h_2)\subset \mathbf S'_2}}{\sigma_2^{|\mathbf{AP}'(KH;q_1,n-q_1h_1)| +|\mathbf{AP}'(KH;q_2,n-q_2h_2)|}}.
\end{equation}
\tag{6.8}
$$
Note that by (3.4) and (6.7) the contribution from $q_1=q_2$ is at most
$$
\begin{equation*}
H^2\sigma_2^{-2KH}|\mathcal Q_{H,1}|\sigma_1y\leqslant |\mathcal Q_{H,1}|^2y^{o(1)},
\end{equation*}
\notag
$$
which is an acceptable error term. Now, if $q_1\neq q_2$, then the set
$$
\begin{equation*}
\mathbf{AP}'(KH;q_1,n-q_1h_1)\cup \mathbf{AP}'(KH;q_2,n-q_2h_2)
\end{equation*}
\notag
$$
has size $|\mathbf{AP}'(KH;q_1,n-q_1h_1)|+|\mathbf{AP}'(KH;q_2,n-q_2h_2)|-1$, since $n$ is the only common element of these two progressions (recall that $q_1$ and $q_2$ are prime numbers, $q_1, q_2\gg y/H$ and $h_1,h_2\ll H=y^{o(1)}$). As before, we can consider summation over $n\in\mathbf{S}'_1\cap[-y,y]$ in (6.8), and then use Lemma 6.1 to rewrite the terms with $q_1\neq q_2$ in (6.8) as
$$
\begin{equation*}
\lfloor KH\rfloor^2\sigma_2^{-1}\mathbb{E}\!\!\sum_{n\in\mathbf S'_1\cap[-y,y]}\sum_{\substack{q_1,q_2\in \mathcal Q_{H,1}\\ q_1\neq q_2}}\!\!\biggl(1{\kern1pt}{+}\,O\biggl(\frac{1}{H^{M-2}}\,{+}\,\frac{E'(q_1)\,{+}\,E'(q_2)\,{+}\,E''(q_1,q_2)}{H^2}\biggr)\biggr),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
E'(q)=\sum_{\substack{h,h'\leqslant KH \\ h\neq h'}} E_{8K^2H^2}(qh-qh';H)
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
E''(q_1,q_2)=\sum_{\substack{h_1',h_2'\leqslant KH \\ h_1'\neq h_1,h_2'\neq h_2}} E_{8K^2H^2}(q_1h_1'-q_1h_1-q_2h_2'+q_2h_2;H).
\end{equation*}
\notag
$$
The contribution of $E'(q_1)+E'(q_2)$ is acceptably small as we already saw in the proof of the case $j=1$. Finally, we need to show that
$$
\begin{equation*}
\sum_{q_1,q_2\in\mathcal Q_{H,1}}E_{8K^2H^2}(q_1h_1'-q_1h_1-q_2h_2'+q_2h_2;H) \ll \frac{|\mathcal Q_{H,1}|^2}{H^{M-2}}
\end{equation*}
\notag
$$
for all $h_1'$ and $h_2'$ such that $h_1'\neq h_1$ and $h_2'\neq h_2$. Thus it follows from (6.4) as applied to the sum over $q_1$ for $r=h_1'-h_1$ and $s=-q_2h_2'+q_2h_2$ (after which we sum over all the $q_2$). This completes the proof of the case $j=2$, and Theorem 5.1 follows. 
Citation in format AMSBIB
\Bibitem{GabRad24} |
|
||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|