Introduction
Let ω ( m ) = ∑ p ∣ m 1 \omega(m)=\sum_{p\mid m}1 ω ( m ) = ∑ p ∣ m 1 be the prime divisor function. Elliott and Halberstam proved, using the Bombieri–Vinogradov Theorem, that [5 ]
∑ p < n 2 ω ( n − p ) = ϕ ( n ) + O ( n log n ( log log n ) 2 ) . (1) \sum_{p<n}2^{\omega(n-p)}=\phi(n)+O\left(\frac{n}{\log n}(\log\log n)^2\right). \tag*{(1)} p < n ∑ 2 ω ( n − p ) = ϕ ( n ) + O ( log n n ( log log n ) 2 ) . (1)
Here and later p p p denotes a prime and ϕ \phi ϕ is Euler’s totient function. Elliott gave a talk at the meeting held in Urbana–Champaign, June 5–7, 2014, in memory of Paul and Felice Bateman, and Heini Halberstam, where he revisited his works with Halberstam. A telegraphic representation of the talk was published, which contains the following conjecture [6 ] : for each real λ \lambda λ ,
∑ p < n ω ( n − p ) ≤ 2 log log n + λ ( 2 log log n ) 1 / 2 2 ω ( n − p ) ⟶ ϕ ( n ) 2 π ∫ − ∞ λ e − u 2 / 2 d u , n → ∞ . (2) \sum_{\substack{p<n\\ \omega(n-p)\le2\log\log n+\lambda(2\log\log n)^{1/2}}}2^{\omega(n-p)}
\longrightarrow\frac{\phi(n)}{\sqrt{2\pi}}\int_{-\infty}^{\lambda}e^{-u^2/2}\,du,\qquad n\to\infty. \tag*{(2)} p < n ω ( n − p ) ≤ 2 l o g l o g n + λ ( 2 l o g l o g n ) 1/2 ∑ 2 ω ( n − p ) ⟶ 2 π ϕ ( n ) ∫ − ∞ λ e − u 2 /2 d u , n → ∞. (2)
In this note we establish the conjecture.
Theorem 1. The asymptotic relation (1.2) holds for each real λ \lambda λ .
Without the 2 ω ( n − p ) 2^{\omega(n-p)} 2 ω ( n − p ) weight, variants of (1.2) were known for a long time [8 , 10 ] .
The strategy of proof of Theorem 1 is as follows. By work of Granville and Soundararajan [7 ] , Theorem 1 can be reduced to understanding the distribution of 2 ω ( n − p ) 2^{\omega(n-p)} 2 ω ( n − p ) in arithmetic progressions. More precisely, for a a a in a certain range it is required to consider
∑ p < n a ∣ n − p 2 ω ( n − p ) . \sum_{\substack{p<n\\ a\mid n-p}}2^{\omega(n-p)}. p < n a ∣ n − p ∑ 2 ω ( n − p ) .
Similar as in [5 ] , we obtain the asymptotics for this by using the distribution of primes in arithmetic progressions. However, as the required range of a a a is large, larger than any bounded power of log n \log n log n , the Bombieri–Vinogradov Theorem is no longer enough for this. The requirements for the replacement of the Bombieri–Vinogradov Theorem in the proof of Theorem 1 are strong:
We need to handle arithmetic progressions with modulus larger than n 1 / 2 n^{1/2} n 1/2 .
The weight on the moduli contains a component of non-negligible range to be handled with absolute value, arising from a a a .
The progression to be considered is of the form p ≡ n ( d ) p\equiv n(d) p ≡ n ( d ) , where n n n is of the same order of magnitude as the range of summation of p p p .
We succeed by showing that these conditions can be handled by an application of a recent result due to Blomer, the second-named author, Li and Myerson [2 ] .
Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 851318).
Initial reduction
Theorem 1 can be restated as follows. Let X n X_n X n be a random variable taking the value m ∈ { 1 , 2 , … , n } m \in\{1,2,\ldots,n\} m ∈ { 1 , 2 , … , n } with probability proportional to 2 ω ( m ) 1 n − m a prime 2^{\omega(m)}1_{n-m\text{ a prime}} 2 ω ( m ) 1 n − m a prime . Then
ω ( X n ) − 2 log log n ( 2 log log n ) 1 / 2 ⟶ d N ( 0 , 1 ) , n → ∞ , (3) \frac{\omega(X_n)-2\log\log n}{(2\log\log n)^{1/2}} \mathrel{\mathop{\longrightarrow}^{d}} N(0,1), \qquad n\to\infty, \tag*{(3)} ( 2 log log n ) 1/2 ω ( X n ) − 2 log log n ⟶ d N ( 0 , 1 ) , n → ∞ , (3)
where N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) is the standard gaussian distribution and the arrow indicates convergence in distribution. Let
C k : = E X k , C k ′ : = E ∣ X ∣ k , (4) \begin{aligned}
C_k&:=\mathbb{E}X^k,\\
C'_k&:=\mathbb{E}|X|^k, \tag*{(4)}
\end{aligned} C k C k ′ := E X k , := E ∣ X ∣ k , (4)
where X ∼ N ( 0 , 1 ) X\sim N(0,1) X ∼ N ( 0 , 1 ) . It is known that for (2.1) to hold it suffices to show that
E ( ω ( X n ) − 2 log log n ( 2 log log n ) 1 / 2 ) k → C k , n → ∞ , (5) \mathbb{E}\left(\frac{\omega(X_n)-2\log\log n}{(2\log\log n)^{1/2}}\right)^k\to C_k,\qquad n\to\infty, \tag*{(5)} E ( ( 2 log log n ) 1/2 ω ( X n ) − 2 log log n ) k → C k , n → ∞ , (5)
holds for every integer k ≥ 1 k\ge1 k ≥ 1 [4 ] 1 . To approach (2.3) it is convenient to use a general result of Granville and Soundararajan [7 ] .
Proposition 1 (Granville–Soundararajan). Let f : N → R ≥ 0 f:\mathbb{N}\to\mathbb{R}_{\geq0} f : N → R ≥ 0 be an arithmetic function and P \mathcal{P} P be a squarefree integer. Let h : N → R ≥ 0 h:\mathbb{N}\to\mathbb{R}_{\geq0} h : N → R ≥ 0 be a multiplicative function with h ( p ) ≤ p h(p)\leq p h ( p ) ≤ p for p ∣ P p\mid\mathcal{P} p ∣ P . For a ∣ P a\mid\mathcal{P} a ∣ P define r a r_a r a via
∑ m ≤ n a ∣ m f ( m ) = h ( a ) a ∑ m ≤ n f ( m ) + r a . \sum_{\substack{m\leq n\\a\mid m}}f(m)=\frac{h(a)}{a}\sum_{m\leq n}f(m)+r_a. m ≤ n a ∣ m ∑ f ( m ) = a h ( a ) m ≤ n ∑ f ( m ) + r a .
Let
μ P = ∑ p ∣ P h ( p ) p , σ P 2 = ∑ p ∣ P h ( p ) p ( 1 − h ( p ) p ) . \mu_{\mathcal{P}}=\sum_{p\mid\mathcal{P}}\frac{h(p)}{p},\qquad\sigma_{\mathcal{P}}^2=\sum_{p\mid\mathcal{P}}\frac{h(p)}{p}\left(1-\frac{h(p)}{p}\right). μ P = p ∣ P ∑ p h ( p ) , σ P 2 = p ∣ P ∑ p h ( p ) ( 1 − p h ( p ) ) .
Uniformly for 1 ≤ k ≤ σ P 2 / 3 1\leq k\leq\sigma_{\mathcal{P}}^{2/3} 1 ≤ k ≤ σ P 2/3 we have
∑ m ≤ n f ( m ) ( ∑ p ∣ P 1 p ∣ m − μ P ) k = σ P k ∑ m ≤ n f ( m ) ( C k + O ( ( k 3 / 2 σ P − 1 ) 1 + 2 ∣ k ∣ C k ′ ) ) + O ( μ P k ∑ a ∣ P ω ( a ) ≤ k ∣ r a ∣ ) , \sum_{m\leq n}f(m)\left(\sum_{p\mid\mathcal{P}}1_{p\mid m}-\mu_{\mathcal{P}}\right)^k
=\sigma_{\mathcal{P}}^k\sum_{m\leq n}f(m)\left(C_k+O\left((k^{3/2}\sigma_{\mathcal{P}}^{-1})^{1+2|k|}C'_k\right)\right)+O\left(\mu_{\mathcal{P}}^k\sum_{\substack{a\mid\mathcal{P}\\\omega(a)\leq k}}|r_a|\right), m ≤ n ∑ f ( m ) p ∣ P ∑ 1 p ∣ m − μ P k = σ P k m ≤ n ∑ f ( m ) ( C k + O ( ( k 3/2 σ P − 1 ) 1 + 2∣ k ∣ C k ′ ) ) + O μ P k a ∣ P ω ( a ) ≤ k ∑ ∣ r a ∣ ,
where C k C_k C k , C k ′ C'_k C k ′ are given by (2.2).
For f ≡ 1 f\equiv1 f ≡ 1 this is [GS07, Prop. 3] and the proof works the same way for general f ≥ 0 f\geq0 f ≥ 0 . Proposition 1 allows us to reduce the proof of Theorem 1 to a level-of-distribution result. We now state this reduction in somewhat more general terms, for the proof of Theorem 1 only the case θ = 2 \theta=2 θ = 2 will be used.
Corollary 1. Fix θ > 0 \theta>0 θ > 0 and k ∈ N k\in\mathbb{N} k ∈ N . For every n ≫ 1 n\gg1 n ≫ 1 let Y n Y_n Y n be a random variable taking values in { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } and set
I n : = ( exp ( exp ( log 1 / 3 log n ) ) , n exp ( − log 1 / 3 log n ) ) , T : = n 1 / log 1 / 3 log n , P = ∏ p ∈ I n p . I_n:=\left(\exp\left(\exp\left(\log^{1/3}\log n\right)\right),n^{\exp\left(-\log^{1/3}\log n\right)}\right),\qquad T:=n^{1/\log^{1/3}\log n},\qquad\mathcal{P}=\prod_{p\in I_n}p. I n := ( exp ( exp ( log 1/3 log n ) ) , n e x p ( − l o g 1/3 l o g n ) ) , T := n 1/ l o g 1/3 l o g n , P = p ∈ I n ∏ p .
Suppose that, as n → ∞ n \to\infty n → ∞
∑ ω ( a ) ≤ k p ∣ a ⇒ p ∈ [ 2 , T ) ∖ I n μ 2 ( a ) = 1 P ( a divides Y n ) = o ( ( log log n ) k / 2 ) , (6) \sum_{\substack{\omega(a)\le k\\ p\mid a\ \Rightarrow\ p\in[2,T)\setminus\mathcal{I}_n\\ \mu^2(a)=1}} \mathbb{P}(a\text{ divides }Y_n)=o\left((\log\log n)^{k/2}\right), \tag*{(6)} ω ( a ) ≤ k p ∣ a ⇒ p ∈ [ 2 , T ) ∖ I n μ 2 ( a ) = 1 ∑ P ( a divides Y n ) = o ( ( log log n ) k /2 ) , (6)
∑ ω ( a ) ≤ k a ∣ P ∣ P ( a divides Y n ) − θ ω ( a ) a ∣ = o ( ( log log n ) − k / 2 ) . (7) \sum_{\substack{\omega(a)\le k\\ a\mid\mathcal{P}}}\left|\mathbb{P}(a\text{ divides }Y_n)-\frac{\theta^{\omega(a)}}{a}\right|=o\left((\log\log n)^{-k/2}\right). \tag*{(7)} ω ( a ) ≤ k a ∣ P ∑ P ( a divides Y n ) − a θ ω ( a ) = o ( ( log log n ) − k /2 ) . (7)
Then we have
E ( ω ( Y n ) − θ log log n ( θ log log n ) 1 / 2 ) k → C k , n → ∞ . \mathbb{E}\left(\frac{\omega(Y_n)-\theta\log\log n}{(\theta\log\log n)^{1/2}}\right)^k\to C_k,\qquad n\to\infty. E ( ( θ log log n ) 1/2 ω ( Y n ) − θ log log n ) k → C k , n → ∞.
Proof. We consider a given n n n and apply Proposition 1 with f ( m ) = P ( Y n = m ) f(m)=\mathbb{P}(Y_n=m) f ( m ) = P ( Y n = m ) , h ( m ) = θ ω ( m ) h(m)=\theta^{\omega(m)} h ( m ) = θ ω ( m ) . Define
ω P ( n ) = ∑ p ∣ P 1 p ∣ n , μ = ∑ p ∣ P θ p , σ 2 = ∑ p ∣ P θ p ( 1 − θ p ) , r a = P ( a divides Y n ) − θ ω ( a ) a . \omega_{\mathcal{P}}(n)=\sum_{p\mid\mathcal{P}}1_{p\mid n},\qquad\mu=\sum_{p\mid\mathcal{P}}\frac{\theta}{p},\qquad\sigma^2=\sum_{p\mid\mathcal{P}}\frac{\theta}{p}\left(1-\frac{\theta}{p}\right),\qquad r_a=\mathbb{P}(a\text{ divides }Y_n)-\frac{\theta^{\omega(a)}}{a}. ω P ( n ) = p ∣ P ∑ 1 p ∣ n , μ = p ∣ P ∑ p θ , σ 2 = p ∣ P ∑ p θ ( 1 − p θ ) , r a = P ( a divides Y n ) − a θ ω ( a ) .
We find that
∑ m = 1 n P ( Y n = m ) ( ω P ( m ) − μ σ ) k = ∑ m = 1 n P ( Y n = m ) ( C k + O ( σ − 1 − 2 ∣ k ∣ ) ) + O ( μ k σ k ∑ ω ( a ) ≤ k a ∣ P ∣ r a ∣ ) (8) \sum_{m=1}^{n}\mathbb{P}(Y_n=m)\left(\frac{\omega_{\mathcal{P}}(m)-\mu}{\sigma}\right)^k
=
\sum_{m=1}^{n}\mathbb{P}(Y_n=m)\left(C_k+O(\sigma^{-1-2\lvert k\rvert})\right)
+O\left(\frac{\mu^k}{\sigma^k}\sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}|r_a|\right) \tag*{(8)} m = 1 ∑ n P ( Y n = m ) ( σ ω P ( m ) − μ ) k = m = 1 ∑ n P ( Y n = m ) ( C k + O ( σ − 1 − 2 ∣ k ∣ ) ) + O σ k μ k ω ( a ) ≤ k a ∣ P ∑ ∣ r a ∣ (8)
holds for every fixed k ≥ 1 k\ge1 k ≥ 1 . Since ∑ p ≤ x 1 / p = log log x + O ( 1 ) \sum_{p\le x}1/p=\log\log x+O(1) ∑ p ≤ x 1/ p = log log x + O ( 1 ) we have
μ , σ 2 = θ log log n + O ( log 1 / 3 log n ) . (9) \mu,\sigma^2=\theta\log\log n+O(\log^{1/3}\log n). \tag*{(9)} μ , σ 2 = θ log log n + O ( log 1/3 log n ) . (9)
We express (8) as
E ( ω P ( Y n ) − μ σ ) k − C k ≪ ( log log n ) − 1 / 2 + ( log log n ) k / 2 ∑ ω ( a ) ≤ k a ∣ P ∣ r a ∣ . (10) \mathbb{E}\left(\frac{\omega_{\mathcal{P}}(Y_n)-\mu}{\sigma}\right)^k-C_k
\ll(\log\log n)^{-1/2}+(\log\log n)^{k/2}\sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}|r_a|. \tag*{(10)} E ( σ ω P ( Y n ) − μ ) k − C k ≪ ( log log n ) − 1/2 + ( log log n ) k /2 ω ( a ) ≤ k a ∣ P ∑ ∣ r a ∣. (10)
By (7) , the right-hand side of (10) goes to 0 0 0 as n → ∞ n\to\infty n → ∞ . Let T = n 1 / log 1 / 3 log n T=n^{1/\log^{1/3}\log n} T = n 1/ l o g 1/3 l o g n . We have the identity
ω ( Y n ) − θ log log n ( θ log log n ) 1 / 2 = A 1 A 2 + A 3 + A 4 + A 5 \frac{\omega(Y_n)-\theta\log\log n}{(\theta\log\log n)^{1/2}}=A_1A_2+A_3+A_4+A_5 ( θ log log n ) 1/2 ω ( Y n ) − θ log log n = A 1 A 2 + A 3 + A 4 + A 5
for
A 1 = σ ( θ log log n ) 1 / 2 , A 2 = ω P ( Y n ) − μ σ , A 3 = μ − θ log log n ( θ log log n ) 1 / 2 , A_1=\frac{\sigma}{(\theta\log\log n)^{1/2}},\qquad A_2=\frac{\omega_{\mathcal{P}}(Y_n)-\mu}{\sigma},\qquad A_3=\frac{\mu-\theta\log\log n}{(\theta\log\log n)^{1/2}}, A 1 = ( θ log log n ) 1/2 σ , A 2 = σ ω P ( Y n ) − μ , A 3 = ( θ log log n ) 1/2 μ − θ log log n ,
A 4 = ∑ p ∈ [ 2 , T ) ∖ I n 1 p ∣ Y n ( θ log log n ) 1 / 2 , A 5 = ∑ p ∈ [ T , n ] 1 p ∣ Y n ( θ log log n ) 1 / 2 . A_4=\frac{\sum_{p\in[2,T)\setminus\mathcal{I}_n}1_{p\mid Y_n}}{(\theta\log\log n)^{1/2}},\qquad A_5=\frac{\sum_{p\in[T,n]}1_{p\mid Y_n}}{(\theta\log\log n)^{1/2}}. A 4 = ( θ log log n ) 1/2 ∑ p ∈ [ 2 , T ) ∖ I n 1 p ∣ Y n , A 5 = ( θ log log n ) 1/2 ∑ p ∈ [ T , n ] 1 p ∣ Y n .
By (9) , the constants A 1 A_1 A 1 and A 3 A_3 A 3 tend to $1a n d and an d 0, respectively. We have observed \text{, respectively. We have observed} , respectively. We have observed \mathbb{E}A_2^k\to C_k. A n i n t e g e r . An integer . A nin t e g er mc a n h a v e a t m o s t can have at most c anha v e a t m os t \log m/\log Tp r i m e f a c t o r s o f s i z e a t l e a s t prime factors of size at least p r im e f a c t or so f s i z e a tl e a s t T, i m p l y i n g , implying , im pl y in g A_5\ll ( log log n ) − 1 / 6 (\log\log n)^{-1/6} ( log log n ) − 1/6 and so E A 5 k → 0 \mathbb{E}A_5^k \to0 E A 5 k → 0 as n → ∞ n \to\infty n → ∞ . To handle A 4 A_4 A 4 we use (6) which yields
E A 4 k = ∑ p 1 , … , p k ∈ [ 2 , T ) ∖ I n P ( [ p 1 , … , p k ] divides Y n ) ( θ log log n ) k / 2 ≪ ( log log n ) − k / 2 ∑ ω ( a ) < k p ∣ a ⇒ p ∈ [ 2 , T ) ∖ I n μ 2 ( a ) = 1 P ( a divides Y n ) = o ( 1 ) . \begin{aligned}
\mathbb{E}A_4^k=\frac{\sum_{p_1,\ldots,p_k\in[2,T)\setminus\mathcal{I}_n}\mathbb{P}([p_1,\ldots,p_k]\text{ divides }Y_n)}{(\theta\log\log n)^{k/2}} \\
&\ll(\log\log n)^{-k/2}
\sum_{\substack{\omega(a)<k\\ p\mid a\Rightarrow p\in[2,T)\setminus\mathcal{I}_n\\ \mu^2(a)=1}}\mathbb{P}(a\text{ divides }Y_n)=o(1).
\end{aligned} E A 4 k = ( θ log log n ) k /2 ∑ p 1 , … , p k ∈ [ 2 , T ) ∖ I n P ([ p 1 , … , p k ] divides Y n ) ≪ ( log log n ) − k /2 ω ( a ) < k p ∣ a ⇒ p ∈ [ 2 , T ) ∖ I n μ 2 ( a ) = 1 ∑ P ( a divides Y n ) = o ( 1 ) .
We have shown E ∣ A 3 + A 4 + A 5 ∣ k → 0 \mathbb{E}|A_3+A_4+A_5|^k\to0 E ∣ A 3 + A 4 + A 5 ∣ k → 0 and E ( A 1 A 2 ) k → C k \mathbb{E}(A_1A_2)^k\to C_k E ( A 1 A 2 ) k → C k . By Hölder, (5) follows.
Corollary 1 may also be proved by generalizing an argument of Billingsley [3 ] . To deduce Theorem 1 from Corollary 1 we apply it with Y n = X n Y_n=X_n Y n = X n and θ = 2 \theta=2 θ = 2 . This reduces matters to the following lemma, whose proof we postpone to the next section.
Lemma 1. Let η > 0 \eta>0 η > 0 be sufficiently small. Fix k ≥ 1 k\ge1 k ≥ 1 . Then
∑ 1 ≤ a ≤ n η ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) ∣ P ( a divides X n ) − 2 ω ( a ) a + 2 D a ϕ ( a ) log n ∣ ≪ k ( log log n ) O k ( 1 ) log n . \sum_{\substack{1\le a\le n^\eta\\ \omega(a)\le k\\ (a,n)=1}}\mu^2(a)\left|\mathbb{P}(a\text{ divides }X_n)-\frac{2^{\omega(a)}}{a}+\frac{2D_a}{\phi(a)\log n}\right|
\ll_k\frac{(\log\log n)^{O_k(1)}}{\log n}. 1 ≤ a ≤ n η ω ( a ) ≤ k ( a , n ) = 1 ∑ μ 2 ( a ) P ( a divides X n ) − a 2 ω ( a ) + ϕ ( a ) log n 2 D a ≪ k log n ( log log n ) O k ( 1 ) .
where
D a : = ∑ d ∣ a ∞ g ( d ) log d , g ( d ) = ∏ p k ∥ d ( − 1 ) k − 1 ( p − 2 ) ( p − 1 ) − k . D_a:=\sum_{d\mid a^\infty}g(d)\log d,\qquad g(d)=\prod_{p^k\parallel d}(-1)^{k-1}(p-2)(p-1)^{-k}. D a := d ∣ a ∞ ∑ g ( d ) log d , g ( d ) = p k ∥ d ∏ ( − 1 ) k − 1 ( p − 2 ) ( p − 1 ) − k .
We remark that the occurrence of the somewhat unexpected lower order term involving D a D_a D a may merit further study.
Proof of Theorem 1, assuming Lemma 1. By Corollary 1 it suffices to establish (6) and (7) (with θ = 2 \theta=2 θ = 2 and Y n = X n Y_n=X_n Y n = X n ). To deduce this from Lemma 1, we must explain how to deal with two issues: the condition ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 being present in the lemma, and the existence of the lower order term involving D a D_a D a . The contribution of a a a -s with ( a , n ) > 1 (a,n)>1 ( a , n ) > 1 to (6) is negligible since
P ( a divides X n ) ≪ n − 1 + o ( 1 ) (11) \mathbb{P}(a\text{ divides }X_n)\ll n^{-1+o(1)} \tag*{(11)} P ( a divides X n ) ≪ n − 1 + o ( 1 ) (11)
uniformly for a a a with ( a , n ) > 1 (a,n)>1 ( a , n ) > 1 . The contribution of a a a -s with ( a , n ) > 1 (a,n)>1 ( a , n ) > 1 to (7) is negligible by (11) and by
∑ ω ( a ) ≤ k a ∣ P ( a , n ) > 1 2 ω ( a ) a ≪ k ( 1 + ∑ p ∣ P 1 p ) k − 1 ∑ p ∣ n 1 p ≪ k exp ( − exp ( log 1 / 4 log n ) ) . \sum_{\substack{\omega(a)\le k\\ a\mid\mathcal{P}\\ (a,n)>1}}\frac{2^{\omega(a)}}{a}
\ll_k\left(1+\sum_{p\mid\mathcal{P}}\frac1p\right)^{k-1}\sum_{p\mid n}\frac1p
\ll_k\exp\left(-\exp\left(\log^{1/4}\log n\right)\right). ω ( a ) ≤ k a ∣ P ( a , n ) > 1 ∑ a 2 ω ( a ) ≪ k 1 + p ∣ P ∑ p 1 k − 1 p ∣ n ∑ p 1 ≪ k exp ( − exp ( log 1/4 log n ) ) .
where we used ∑ p ≤ x 1 / p = log log x + O ( 1 ) \sum_{p\le x}1/p=\log\log x+O(1) ∑ p ≤ x 1/ p = log log x + O ( 1 ) and the fact that n n n has ≪ log n \ll\log n ≪ log n prime factors. Next, we use ∑ d ∣ a ∞ ∣ g ( d ) ∣ = 2 ω ( a ) − 1 2 ∣ a \sum_{d\mid a^\infty}|g(d)|=2^{\omega(a)-1}2^{|a} ∑ d ∣ a ∞ ∣ g ( d ) ∣ = 2 ω ( a ) − 1 2 ∣ a to bound D a D_a D a as
D a ≪ ∑ p ∣ a i ≥ 1 log ( p i ) ∑ p i ∣ d ∣ a ∞ ∣ g ( d ) ∣ ≪ 2 ω ( a ) ∑ p ∣ a i ≥ 1 log ( p i ) ( p − 2 ) ( p − 1 ) − i ≪ 2 ω ( a ) log a D_a\ll\sum_{\substack{p\mid a\\ i\ge1}}\log(p^i)\sum_{p^i\mid d\mid a^\infty}|g(d)|
\ll2^{\omega(a)}\sum_{\substack{p\mid a\\ i\ge1}}\log(p^i)(p-2)(p-1)^{-i}
\ll2^{\omega(a)}\log a D a ≪ p ∣ a i ≥ 1 ∑ log ( p i ) p i ∣ d ∣ a ∞ ∑ ∣ g ( d ) ∣ ≪ 2 ω ( a ) p ∣ a i ≥ 1 ∑ log ( p i ) ( p − 2 ) ( p − 1 ) − i ≪ 2 ω ( a ) log a
and it follows that for any squarefree Q \mathcal{Q} Q ,
∑ ω ( a ) ≤ k a ∣ Q ∣ D a ∣ ϕ ( a ) log n ≪ k 1 log n ( 1 + ∑ p ∣ Q 1 p ) k − 1 ∑ p ∣ Q log p p . \sum_{\substack{\omega(a)\le k\\ a\mid\mathcal{Q}}}\frac{|D_a|}{\phi(a)\log n}
\ll_k\frac1{\log n}\left(1+\sum_{p\mid\mathcal{Q}}\frac1p\right)^{k-1}\sum_{p\mid\mathcal{Q}}\frac{\log p}{p}. ω ( a ) ≤ k a ∣ Q ∑ ϕ ( a ) log n ∣ D a ∣ ≪ k log n 1 1 + p ∣ Q ∑ p 1 k − 1 p ∣ Q ∑ p log p .
In the notation of Corollary 1, we specialize to Q = P \mathcal{Q}=\mathcal{P} Q = P and Q = ∏ p ∈ [ 2 , T ) ∖ I n p \mathcal{Q}=\prod_{p\in[2,T)\setminus\mathcal{I}_n}p Q = ∏ p ∈ [ 2 , T ) ∖ I n p and find D a D_a D a contributes negligibly to (6) and (7) by invoking ∑ p ≤ x log p p = log x + O ( 1 ) \sum_{p\le x}\frac{\log p}{p}=\log x+O(1) ∑ p ≤ x p l o g p = log x + O ( 1 ) and ∑ p ≤ x 1 p = log log x + O ( 1 ) \sum_{p\le x}\frac1p=\log\log x+O(1) ∑ p ≤ x p 1 = log log x + O ( 1 ) . ▫
Proof of Lemma 1
We shall work with arithmetic sums instead of probabilities. Given a ≥ 1 a \ge1 a ≥ 1 let
A a ( n ) : = ∑ p < n : a ∣ n − p 2 ω ( n − p ) A_a(n) := \sum_{\substack{p<n:\\a\mid n-p}} 2^{\omega(n-p)} A a ( n ) := p < n : a ∣ n − p ∑ 2 ω ( n − p )
so that P ( a divides X n ) = A a ( n ) / A 1 ( n ) \mathbb{P}(a\text{ divides }X_n)=A_a(n)/A_1(n) P ( a divides X n ) = A a ( n ) / A 1 ( n ) . Lemma 1 is equivalent to
∑ 1 ≤ a ≤ n η ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) ∣ A a ( n ) − ϕ ( n ) ( 2 ω ( a ) a − 2 D a ϕ ( a ) log n ) ∣ ≪ k n log n ( log log n ) O k ( 1 ) (12) \sum_{\substack{1\le a\le n^\eta\\ \omega(a)\le k\\ (a,n)=1}} \mu^2(a)\left|A_a(n)-\phi(n)\left(\frac{2^{\omega(a)}}{a}-\frac{2D_a}{\phi(a)\log n}\right)\right| \ll_k \frac{n}{\log n}(\log\log n)^{O_k(1)} \tag*{(12)} 1 ≤ a ≤ n η ω ( a ) ≤ k ( a , n ) = 1 ∑ μ 2 ( a ) A a ( n ) − ϕ ( n ) ( a 2 ω ( a ) − ϕ ( a ) log n 2 D a ) ≪ k log n n ( log log n ) O k ( 1 ) (12)
where we utilized (1.1), ϕ ( n ) ≫ n / log log n \phi(n)\gg n/\log\log n ϕ ( n ) ≫ n / log log n and ∑ p ≤ x 1 / p = log log x + O ( 1 ) \sum_{p\le x}1/p=\log\log x+O(1) ∑ p ≤ x 1/ p = log log x + O ( 1 ) to replace A 1 ( n ) A_1(n) A 1 ( n ) by ϕ ( n ) \phi(n) ϕ ( n ) . We write 2 ω ( n − p ) 2^{\omega(n-p)} 2 ω ( n − p ) as a divisor sum using 2 ω ( m ) = ∑ d ∣ m μ 2 ( d ) 2^{\omega(m)}=\sum_{d\mid m}\mu^2(d) 2 ω ( m ) = ∑ d ∣ m μ 2 ( d ) and μ 2 ( d ) = ∑ e 2 ∣ d μ ( e ) \mu^2(d)=\sum_{e^2\mid d}\mu(e) μ 2 ( d ) = ∑ e 2 ∣ d μ ( e ) , separate the contribution of large square divisors, and apply divisor switching. We have
2 ω ( n ) = ∑ n = d s μ 2 ( d ) = ∑ n = e 2 d s μ ( e ) = ∑ n = e 2 d s e > V μ ( e ) + ∑ n = e 2 d s e ≤ V d ≤ D μ ( e ) + ∑ n = e 2 d s e ≤ V s < n / ( e 2 D ) μ ( e ) 2^{\omega(n)}=\sum_{n=ds}\mu^2(d)=\sum_{n=e^2ds}\mu(e)=\sum_{\substack{n=e^2ds\\e>V}}\mu(e)+\sum_{\substack{n=e^2ds\\e\le V\\d\le D}}\mu(e)+\sum_{\substack{n=e^2ds\\e\le V\\s<n/(e^2D)}}\mu(e) 2 ω ( n ) = n = d s ∑ μ 2 ( d ) = n = e 2 d s ∑ μ ( e ) = n = e 2 d s e > V ∑ μ ( e ) + n = e 2 d s e ≤ V d ≤ D ∑ μ ( e ) + n = e 2 d s e ≤ V s < n / ( e 2 D ) ∑ μ ( e )
with the choices
V = n 2 η , D = n 1 / 2 + 2 η . V=n^{2\eta},\qquad D=n^{1/2+2\eta}. V = n 2 η , D = n 1/2 + 2 η .
Then, given a ≥ 1 a\ge1 a ≥ 1 , we split A a ( n ) A_a(n) A a ( n ) accordingly:
A a ( n ) = ∑ p < n a ∣ n − p ( ∑ n − p = e 2 d s e > V μ ( e ) + ∑ n − p = e 2 d s e ≤ V d ≤ D μ ( e ) + ∑ n − p = e 2 d s e ≤ V s < ( n − p ) / ( e 2 D ) μ ( e ) ) = : S 0 ( a ) + S 1 ( a ) + S 2 ( a ) . A_a(n)=\sum_{\substack{p<n\\a\mid n-p}}\left(\sum_{\substack{n-p=e^2ds\\e>V}}\mu(e)+\sum_{\substack{n-p=e^2ds\\e\le V\\d\le D}}\mu(e)+\sum_{\substack{n-p=e^2ds\\e\le V\\s<(n-p)/(e^2D)}}\mu(e)\right)=:S_0(a)+S_1(a)+S_2(a). A a ( n ) = p < n a ∣ n − p ∑ n − p = e 2 d s e > V ∑ μ ( e ) + n − p = e 2 d s e ≤ V d ≤ D ∑ μ ( e ) + n − p = e 2 d s e ≤ V s < ( n − p ) / ( e 2 D ) ∑ μ ( e ) =: S 0 ( a ) + S 1 ( a ) + S 2 ( a ) .
We write π ( x ; q , b ) \pi(x;q,b) π ( x ; q , b ) for the number of primes in [ 1 , x ] [1,x] [ 1 , x ] that are congruent to b b b modulo q q q . With this notation we have
S 0 ( a ) = ∑ V < e ≤ n d ≤ n μ ( e ) π ( n − 1 ; [ d e 2 , a ] , n ) , S_0(a)=\sum_{\substack{V<e\le\sqrt n\\d\le n}}\mu(e)\pi(n-1;[de^2,a],n), S 0 ( a ) = V < e ≤ n d ≤ n ∑ μ ( e ) π ( n − 1 ; [ d e 2 , a ] , n ) ,
S 1 ( a ) = ∑ e ≤ V d ≤ D μ ( e ) π ( n − 1 ; [ d e 2 , a ] , n ) , S_1(a)=\sum_{\substack{e\le V\\d\le D}}\mu(e)\pi(n-1;[de^2,a],n), S 1 ( a ) = e ≤ V d ≤ D ∑ μ ( e ) π ( n − 1 ; [ d e 2 , a ] , n ) ,
S 2 ( a ) = ∑ e ≤ V s < ( n − 2 ) / ( e 2 D ) μ ( e ) π ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) . S_2(a)=\sum_{\substack{e\le V\\s<(n-2)/(e^2D)}}\mu(e)\pi(n-se^2D-1;[se^2,a],n). S 2 ( a ) = e ≤ V s < ( n − 2 ) / ( e 2 D ) ∑ μ ( e ) π ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) .
Write E ( m ; q , a ) = π ( m ; q , a ) − Li ( m ) 1 ( q , a ) = 1 φ ( a ) E(m;q,a)=\pi(m;q,a)-\dfrac{\operatorname{Li}(m)1_{(q,a)=1}}{\varphi(a)} E ( m ; q , a ) = π ( m ; q , a ) − φ ( a ) Li ( m ) 1 ( q , a ) = 1 and accordingly
S i ( a ) = M i ( a ) + E i ( a ) ( i = 1 , 2 ) . S_i(a)=M_i(a)+E_i(a)\qquad(i=1,2). S i ( a ) = M i ( a ) + E i ( a ) ( i = 1 , 2 ) .
for
M 1 ( a ) = Li ( n − 1 ) ∑ e ≤ V d ≤ D ( e d , n ) = 1 μ ( e ) ϕ ( [ d e 2 , a ] ) , E 1 ( a ) = ∑ e ≤ V d ≤ D ( e d , n ) = 1 μ ( e ) E ( n − 1 ; [ d e 2 , a ] , n ) , M_1(a)=\operatorname{Li}(n-1)\sum_{\substack{e\le V\\ d\le D\\ (ed,n)=1}}\frac{\mu(e)}{\phi([de^2,a])},\qquad E_1(a)=\sum_{\substack{e\le V\\ d\le D\\ (ed,n)=1}}\mu(e)E(n-1;[de^2,a],n), M 1 ( a ) = Li ( n − 1 ) e ≤ V d ≤ D ( e d , n ) = 1 ∑ ϕ ([ d e 2 , a ]) μ ( e ) , E 1 ( a ) = e ≤ V d ≤ D ( e d , n ) = 1 ∑ μ ( e ) E ( n − 1 ; [ d e 2 , a ] , n ) ,
M 2 ( a ) = ∑ e ≤ V d < ( n − 2 ) / ( e 2 D ) ( d e , n ) = 1 μ ( e ) Li ( n − d e 2 D − 1 ) ϕ ( [ d e 2 , a ] ) , E 2 ( a ) = ∑ e ≤ V d < ( n − 2 ) / ( e 2 D ) ( d e , n ) = 1 μ ( e ) E ( n − d e 2 D − 1 ; [ d e 2 , a ] , n ) . M_2(a)=\sum_{\substack{e\le V\\ d<(n-2)/(e^2D)\\ (de,n)=1}}\frac{\mu(e)\operatorname{Li}(n-de^2D-1)}{\phi([de^2,a])},\qquad E_2(a)=\sum_{\substack{e\le V\\ d<(n-2)/(e^2D)\\ (de,n)=1}}\mu(e)E(n-de^2D-1;[de^2,a],n). M 2 ( a ) = e ≤ V d < ( n − 2 ) / ( e 2 D ) ( d e , n ) = 1 ∑ ϕ ([ d e 2 , a ]) μ ( e ) Li ( n − d e 2 D − 1 ) , E 2 ( a ) = e ≤ V d < ( n − 2 ) / ( e 2 D ) ( d e , n ) = 1 ∑ μ ( e ) E ( n − d e 2 D − 1 ; [ d e 2 , a ] , n ) .
The rest of the proof is separated into four parts which together establish (3.1).
Lemma 2. We have ∑ a ≤ n η ∣ S 0 ( a ) ∣ ≪ n 1 − η 2 \sum_{a\le n^\eta}|S_0(a)|\ll n^{1-\frac{\eta}{2}} ∑ a ≤ n η ∣ S 0 ( a ) ∣ ≪ n 1 − 2 η .
Lemma 3. For every B > 0 B>0 B > 0 , ∑ a ≤ n η ∣ E 1 ( a ) ∣ ≪ B n ( log n ) − B \sum_{a\le n^\eta}|E_1(a)|\ll_B n(\log n)^{-B} ∑ a ≤ n η ∣ E 1 ( a ) ∣ ≪ B n ( log n ) − B .
Lemma 4. For every B > 0 B>0 B > 0 , ∑ a ≤ n η ∣ E 2 ( a ) ∣ ≪ B n ( log n ) − B \sum_{a\le n^\eta}|E_2(a)|\ll_B n(\log n)^{-B} ∑ a ≤ n η ∣ E 2 ( a ) ∣ ≪ B n ( log n ) − B .
Lemma 5. Fix k ≥ 1 k\ge1 k ≥ 1 . Suppose a ≤ n η a\le n^\eta a ≤ n η , ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k and μ 2 ( a ) = 1 \mu^2(a)=1 μ 2 ( a ) = 1 . We have
M 1 ( a ) + M 2 ( a ) = ϕ ( n ) ( 2 ω ( a ) a − 2 D a ϕ ( a ) log n ) + O k ( n ( log log n ) 2 a log n ) . M_1(a)+M_2(a)=\phi(n)\left(\frac{2^{\omega(a)}}{a}-\frac{2D_a}{\phi(a)\log n}\right)+O_k\left(\frac{n(\log\log n)^2}{a\log n}\right). M 1 ( a ) + M 2 ( a ) = ϕ ( n ) ( a 2 ω ( a ) − ϕ ( a ) log n 2 D a ) + O k ( a log n n ( log log n ) 2 ) .
Proof of Lemma 2
The upper bound π ( n − 1 ; q , n ) ≤ n / q \pi(n-1;q,n)\le n/q π ( n − 1 ; q , n ) ≤ n / q gives
∣ S 0 ( a ) ∣ ≤ ∑ V < e ≤ n d ≤ n ∑ p < n [ d e 2 , a ] ∣ n − p 1 ≤ ∑ e > V d ≤ n n [ d e 2 , a ] ≤ ∑ e > V d ≤ n n d e 2 ≪ n log n V , |S_0(a)|\le\sum_{\substack{V<e\le\sqrt n\\ d\le n}}\sum_{\substack{p<n\\ [de^2,a]\mid n-p}}1\le\sum_{\substack{e>V\\ d\le n}}\frac{n}{[de^2,a]}\le\sum_{\substack{e>V\\ d\le n}}\frac{n}{de^2}\ll\frac{n\log n}{V}, ∣ S 0 ( a ) ∣ ≤ V < e ≤ n d ≤ n ∑ p < n [ d e 2 , a ] ∣ n − p ∑ 1 ≤ e > V d ≤ n ∑ [ d e 2 , a ] n ≤ e > V d ≤ n ∑ d e 2 n ≪ V n log n ,
which implies the result.
Proof of Lemma 4
Isolating the contribution of ( s e 2 a , n ) ≠ 1 (se^2a,n)\ne1 ( s e 2 a , n ) = 1 , we have
∑ a ≤ n η ∣ E 2 ( a ) ∣ = ∑ a ≤ n η ∣ ∑ e ≤ V s < ( n − 2 ) / ( e 2 D ) μ ( e ) E ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) ∣ ≤ ∑ d ≤ n 1 / 2 − η ( d , n ) = 1 τ 2 ( d ) max y ≤ n ∣ E ( y ; d , n ) ∣ + n o ( 1 ) \begin{aligned}
\sum_{a\le n^\eta}|E_2(a)|=\sum_{a\le n^\eta}\left|\sum_{\substack{e\le V\\ s<(n-2)/(e^2D)}}\mu(e)E(n-se^2D-1;[se^2,a],n)\right| \\
&\le\sum_{\substack{d\le n^{1/2-\eta}\\ (d,n)=1}}\tau^2(d)\max_{y\le n}|E(y;d,n)|+n^{o(1)}
\end{aligned} a ≤ n η ∑ ∣ E 2 ( a ) ∣ = a ≤ n η ∑ e ≤ V s < ( n − 2 ) / ( e 2 D ) ∑ μ ( e ) E ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) ≤ d ≤ n 1/2 − η ( d , n ) = 1 ∑ τ 2 ( d ) y ≤ n max ∣ E ( y ; d , n ) ∣ + n o ( 1 )
by the divisor bound, where d d d stands for [ s e 2 , a ] [se^2,a] [ s e 2 , a ] . The conclusion follows by applying Cauchy–Schwarz and then the Bombieri–Vinogradov Theorem [5 ] .
Proof of Lemma 3
As E 1 ( a ) E_1(a) E 1 ( a ) requires us to break the 1 / 2 1/2 1/2 -barrier in the level of distribution, it is the more delicate error term. We have
∑ a ≤ n η ∣ E 1 ( a ) ∣ = ∑ a ≤ n η ∣ ∑ e ≤ V μ ( e ) ∑ d ≤ D E ( n − 1 ; [ d e 2 , a ] , n ) ∣ = ∑ a ≤ n η ∣ ∑ e ≤ V b ∣ ( a e ) ∞ μ ( e ) ∑ d ≤ D b ∣ d ( d / b , a e ) = 1 E ( n − 1 ; [ d e 2 , a ] , n ) ∣ = ∑ a ≤ n η ∣ ∑ e ≤ V b ∣ ( a e ) ∞ μ ( e ) ∑ d ′ ≤ D / b ( d ′ , a e ) = 1 E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ∣ , \begin{aligned}
\sum_{a\le n^\eta} |E_1(a)| = \sum_{a\le n^\eta} \left|\sum_{e\le V} \mu(e) \sum_{d\le D} E(n-1; [de^2,a],n)\right| \\
&= \sum_{a\le n^\eta} \left|\sum_{\substack{e\le V\\ b\mid(ae)^\infty}} \mu(e) \sum_{\substack{d\le D\\ b\mid d\\ (d/b,ae)=1}} E(n-1;[de^2,a],n)\right| \\
&= \sum_{a\le n^\eta} \left|\sum_{\substack{e\le V\\ b\mid(ae)^\infty}} \mu(e) \sum_{\substack{d'\le D/b\\ (d',ae)=1}} E(n-1;d'[be^2,a],n)\right|,
\end{aligned} a ≤ n η ∑ ∣ E 1 ( a ) ∣ = a ≤ n η ∑ e ≤ V ∑ μ ( e ) d ≤ D ∑ E ( n − 1 ; [ d e 2 , a ] , n ) = a ≤ n η ∑ e ≤ V b ∣ ( a e ) ∞ ∑ μ ( e ) d ≤ D b ∣ d ( d / b , a e ) = 1 ∑ E ( n − 1 ; [ d e 2 , a ] , n ) = a ≤ n η ∑ e ≤ V b ∣ ( a e ) ∞ ∑ μ ( e ) d ′ ≤ D / b ( d ′ , a e ) = 1 ∑ E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ,
where we substituted d ′ = d b d'=db d ′ = d b . Let E 1 , 1 E_{1,1} E 1 , 1 denote the contribution to the above with b ≤ J = n 2 η b\le J=n^{2\eta} b ≤ J = n 2 η and E 1 , 2 E_{1,2} E 1 , 2 the remainder. For E 1 , 1 E_{1,1} E 1 , 1 we apply the triangle inequality to arrive at
E 1 , 1 ≤ ∑ a ≤ n η ∑ e ≤ V ∑ b ≤ J b ∣ ( a e ) ∞ μ 2 ( e ) ∣ ∑ d ′ ≤ D / b ( d ′ , a e ) = 1 E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ∣ . E_{1,1}\le\sum_{a\le n^\eta}\sum_{e\le V}\sum_{\substack{b\le J\\ b\mid(ae)^\infty}}\mu^2(e)\left|\sum_{\substack{d'\le D/b\\ (d',ae)=1}}E(n-1;d'[be^2,a],n)\right|. E 1 , 1 ≤ a ≤ n η ∑ e ≤ V ∑ b ≤ J b ∣ ( a e ) ∞ ∑ μ 2 ( e ) d ′ ≤ D / b ( d ′ , a e ) = 1 ∑ E ( n − 1 ; d ′ [ b e 2 , a ] , n ) .
To make the summation range of d ′ d' d ′ independent of the other variables, we apply a standard finer-than-dyadic decomposition on the summation over d ′ d' d ′ (see e.g. the proof of [1 ] ). It thus suffices to estimate
E 1 , 1 , D ′ = ∑ a ≤ n η ∑ e ≤ V ∑ b ≤ J b ∣ ( a e ) ∞ μ 2 ( e ) ∣ ∑ d ′ ≤ D ′ ( d ′ , a e ) = 1 E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ∣ E_{1,1,D'}=\sum_{a\le n^\eta}\sum_{e\le V}\sum_{\substack{b\le J\\ b\mid(ae)^\infty}}\mu^2(e)\left|\sum_{\substack{d'\le D'\\ (d',ae)=1}}E(n-1;d'[be^2,a],n)\right| E 1 , 1 , D ′ = a ≤ n η ∑ e ≤ V ∑ b ≤ J b ∣ ( a e ) ∞ ∑ μ 2 ( e ) d ′ ≤ D ′ ( d ′ , a e ) = 1 ∑ E ( n − 1 ; d ′ [ b e 2 , a ] , n )
for any D ′ ≤ D D'\le D D ′ ≤ D . If [ b e 2 , a ] = g [be^2,a]=g [ b e 2 , a ] = g then a a a , b b b and e e e divide g g g and the condition ( d ′ , a e ) = 1 (d',ae)=1 ( d ′ , a e ) = 1 is equivalent to ( d ′ , g ) = 1 (d',g)=1 ( d ′ , g ) = 1 . Thus
E 1 , 1 , D ′ ≤ ∑ g < n 8 η τ ( g ) 3 ∣ ∑ d ′ ≤ D ′ ( d ′ , g ) = 1 E ( n − 1 ; d ′ g , n ) ∣ . E_{1,1,D'}\le\sum_{g<n^{8\eta}}\tau(g)^3\left|\sum_{\substack{d'\le D'\\ (d',g)=1}}E(n-1;d'g,n)\right|. E 1 , 1 , D ′ ≤ g < n 8 η ∑ τ ( g ) 3 d ′ ≤ D ′ ( d ′ , g ) = 1 ∑ E ( n − 1 ; d ′ g , n ) .
We quote [2 ] specialised to a 2 = c = c 0 = 1 a_2=c=c_0=1 a 2 = c = c 0 = 1 .
Proposition 2. There exists some absolute constant ϖ > 0 \varpi>0 ϖ > 0 such that the following holds. Let x ≥ 2 x\ge2 x ≥ 2 , d , C ∈ N d,C\in\mathbb{N} d , C ∈ N , a ∈ Z ∖ { 0 } a\in\mathbb{Z}\setminus\{0\} a ∈ Z ∖ { 0 } such that
Q ≤ x 1 / 2 + ϖ , ∣ a ∣ ≤ x 1 + ϖ , ∣ λ d ∣ ≪ τ ( d ) C Q\le x^{1/2+\varpi},\qquad|a|\le x^{1+\varpi},\qquad|\lambda_d|\ll\tau(d)^C Q ≤ x 1/2 + ϖ , ∣ a ∣ ≤ x 1 + ϖ , ∣ λ d ∣ ≪ τ ( d ) C
hold. Then for any B > 0 B>0 B > 0 we have
∑ d ≤ x ϖ λ d sup w m o d d ( w , d ) = 1 ∣ ∑ q ≤ Q ( q , a d ) = 1 ( ∑ n ≤ x n ≡ a m o d q n ≡ w m o d d Λ ( n ) − 1 ϕ ( q d ) ∑ n ≤ x ( n , q d ) = 1 Λ ( n ) ) ∣ ≪ C , B x ( log x ) − B . \sum_{d\le x^\varpi}\lambda_d\sup_{\substack{w\bmod d\\ (w,d)=1}}\left|\sum_{\substack{q\le Q\\ (q,ad)=1}}\left(\sum_{\substack{n\le x\\ n\equiv a\ \mathrm{mod}\ q\\ n\equiv w\ \mathrm{mod}\ d}}\Lambda(n)-\frac{1}{\phi(qd)}\sum_{\substack{n\le x\\ (n,qd)=1}}\Lambda(n)\right)\right|\ll_{C,B}x(\log x)^{-B}. d ≤ x ϖ ∑ λ d w mod d ( w , d ) = 1 sup q ≤ Q ( q , a d ) = 1 ∑ n ≤ x n ≡ a mod q n ≡ w mod d ∑ Λ ( n ) − ϕ ( q d ) 1 n ≤ x ( n , q d ) = 1 ∑ Λ ( n ) ≪ C , B x ( log x ) − B .
As commented after [2 ] , this holds for the characteristic function of the primes replacing the von Mangoldt function and so implies E 1 , 1 , D ′ ≪ B n ( log n ) − B E_{1,1,D'}\ll_B n(\log n)^{-B} E 1 , 1 , D ′ ≪ B n ( log n ) − B . To prove Lemma 3, it remains to estimate E 1 , 2 E_{1,2} E 1 , 2 and we claim
E 1 , 2 ≪ n 1 − η / 2 . (13) E_{1,2}\ll n^{1-\eta/2}. \tag*{(13)} E 1 , 2 ≪ n 1 − η /2 . (13)
By the trivial bound E ( n − 1 ; q , a ) ≪ 1 + n / q E(n-1;q,a) \ll1+n/q E ( n − 1 ; q , a ) ≪ 1 + n / q we have
E 1 , 2 ≪ n ∑ a < n η e ≤ V d ′ < D / J 1 d ′ ∑ J < b ≤ D / d ′ b ∣ ( a e ) ∞ 1 [ b e 2 , a ] . E_{1,2} \ll n \sum_{\substack{a<n^\eta\\ e\le V\\ d'<D/J}} \frac{1}{d'} \sum_{\substack{J<b\le D/d'\\ b\mid(ae)^\infty}} \frac{1}{[be^2,a]}. E 1 , 2 ≪ n a < n η e ≤ V d ′ < D / J ∑ d ′ 1 J < b ≤ D / d ′ b ∣ ( a e ) ∞ ∑ [ b e 2 , a ] 1 .
Since [ b e 2 , a ] = b e 2 a / ( b e 2 , a ) [be^2,a]=be^2a/(be^2,a) [ b e 2 , a ] = b e 2 a / ( b e 2 , a ) , by dyadic decomposition to get (13) it suffices to show
∑ a ∼ A e ∼ V ∑ b ∼ J b ∣ ( a e ) ∞ ( b e 2 , a ) ≪ ( 2 + log A V ) C ε J ε A 2 V (14) \sum_{\substack{a\sim A\\ e\sim V}} \sum_{\substack{b\sim J\\ b\mid(ae)^\infty}} (be^2,a) \ll(2+\log AV)^{C_\varepsilon} J^\varepsilon A^2V \tag*{(14)} a ∼ A e ∼ V ∑ b ∼ J b ∣ ( a e ) ∞ ∑ ( b e 2 , a ) ≪ ( 2 + log A V ) C ε J ε A 2 V (14)
for all ε > 0 \varepsilon>0 ε > 0 . Here C ε > 0 C_\varepsilon>0 C ε > 0 depends only on ε > 0 \varepsilon>0 ε > 0 (later occurrences of C ε C_\varepsilon C ε might have a different value), a ∼ A a\sim A a ∼ A means a ∈ [ A , 2 A ) a\in[A,2A) a ∈ [ A , 2 A ) and e ∼ V e\sim V e ∼ V , b ∼ J b\sim J b ∼ J should be interpreted in the same way. Estimate (14) implies E 1 , 2 ≪ n 1 + η ( log n ) C ε / J 1 − ε ≪ n 1 − η / 2 E_{1,2}\ll n^{1+\eta}(\log n)^{C_\varepsilon}/J^{1-\varepsilon}\ll n^{1-\eta/2} E 1 , 2 ≪ n 1 + η ( log n ) C ε / J 1 − ε ≪ n 1 − η /2 and so (13) if ε \varepsilon ε is sufficiently small.
To demonstrate (14) , let h = ( b e 2 , a ) h=(be^2,a) h = ( b e 2 , a ) . If h ∣ b e 2 h\mid be^2 h ∣ b e 2 then h = h 1 h 2 h=h_1h_2 h = h 1 h 2 for some (not necessarily unique) h 1 ∣ b h_1\mid b h 1 ∣ b and h 2 ∣ e 2 h_2\mid e^2 h 2 ∣ e 2 . This implies h 2 ′ ∣ e h'_2\mid e h 2 ′ ∣ e for h 2 ′ = ∏ p k ∥ h 2 p ⌈ k / 2 ⌉ h'_2=\prod_{p^k\parallel h_2}p^{\lceil k/2\rceil} h 2 ′ = ∏ p k ∥ h 2 p ⌈ k /2 ⌉ . We can bound (14) by
≤ ∑ h 1 h 2 ∣ a ∼ A h 1 h 2 ∑ h 2 ′ ∣ e ∼ V e ∼ V / h 2 ′ b ∼ J / h 1 b ∣ ( a e ) ∞ 1 ≤ ∑ h 1 h 2 ∣ a ∼ A h 1 h 2 ∑ e ′ ∼ V / h 2 ′ b ′ ∼ J / h 1 b ′ ∣ ( a e ′ ) ∞ 1. \le\sum_{h_1h_2\mid a\sim A}h_1h_2\sum_{\substack{h'_2\mid e\sim V\\ e\sim V/h'_2\\ b\sim J/h_1\\ b\mid(ae)^\infty}}1
\le\sum_{h_1h_2\mid a\sim A}h_1h_2\sum_{\substack{e'\sim V/h'_2\\ b'\sim J/h_1\\ b'\mid(ae')^\infty}}1. ≤ h 1 h 2 ∣ a ∼ A ∑ h 1 h 2 h 2 ′ ∣ e ∼ V e ∼ V / h 2 ′ b ∼ J / h 1 b ∣ ( a e ) ∞ ∑ 1 ≤ h 1 h 2 ∣ a ∼ A ∑ h 1 h 2 e ′ ∼ V / h 2 ′ b ′ ∼ J / h 1 b ′ ∣ ( a e ′ ) ∞ ∑ 1.
By Rankin’s trick,
∑ b ≤ B b ∣ m ∞ 1 ≤ B ε ∏ p ∣ m ( 1 − p − ε ) − 1 ≤ B ε exp ( C ε ∑ p ∣ m p − ε ) ≤ B ε exp ( C ε ω ( m ) ) \sum_{\substack{b\le B\\ b\mid m^\infty}}1\le B^\varepsilon\prod_{p\mid m}(1-p^{-\varepsilon})^{-1}\le B^\varepsilon\exp\left(C_\varepsilon\sum_{p\mid m}p^{-\varepsilon}\right)\le B^\varepsilon\exp(C_\varepsilon\omega(m)) b ≤ B b ∣ m ∞ ∑ 1 ≤ B ε p ∣ m ∏ ( 1 − p − ε ) − 1 ≤ B ε exp C ε p ∣ m ∑ p − ε ≤ B ε exp ( C ε ω ( m ))
for every ε > 0 \varepsilon>0 ε > 0 . Hence
∑ e ′ ∼ V / h 2 ′ b ′ ∼ J / h 1 b ′ ∣ ( a e ′ ) ∞ 1 ≪ ∑ e ′ ∼ V / h 2 ′ ( J / h 1 ) ε exp ( C ε ( ω ( a ) + ω ( e ′ ) ) ) ≪ ( J / h 1 ) ε V ( 2 + log V ) C ε exp ( C ε ω ( a ) ) \sum_{\substack{e'\sim V/h'_2\\ b'\sim J/h_1\\ b'\mid(ae')^\infty}}1
\ll\sum_{e'\sim V/h'_2}(J/h_1)^\varepsilon\exp(C_\varepsilon(\omega(a)+\omega(e')))
\ll(J/h_1)^\varepsilon V(2+\log V)^{C_\varepsilon}\exp(C_\varepsilon\omega(a)) e ′ ∼ V / h 2 ′ b ′ ∼ J / h 1 b ′ ∣ ( a e ′ ) ∞ ∑ 1 ≪ e ′ ∼ V / h 2 ′ ∑ ( J / h 1 ) ε exp ( C ε ( ω ( a ) + ω ( e ′ ))) ≪ ( J / h 1 ) ε V ( 2 + log V ) C ε exp ( C ε ω ( a ))
and so, since h 1 h 2 ≪ A h_1h_2\ll A h 1 h 2 ≪ A ,
∑ a ∼ A e ∼ V ∑ b ∼ J b ∣ ( a e ) ∞ ( b e 2 , a ) ≪ ( 2 + log V ) C ε J ε V ∑ h 1 h 2 ∣ a ∼ A h 1 1 − ε h 2 exp ( C ε ω ( a ) ) ≪ ( 2 + log V ) C ε J ε A V ∑ a ∼ A exp ( C ε ω ( a ) ) τ ( a ) 2 ≪ ( 2 + log A V ) C ε J ε A 2 V . \begin{aligned}
\sum_{\substack{a\sim A\\ e\sim V}}\sum_{\substack{b\sim J\\ b\mid(ae)^\infty}}(be^2,a)
\ll(2+\log V)^{C_\varepsilon}J^\varepsilon V\sum_{h_1h_2\mid a\sim A}h_1^{1-\varepsilon}h_2\exp(C_\varepsilon\omega(a)) \\
&\ll(2+\log V)^{C_\varepsilon}J^\varepsilon AV\sum_{a\sim A}\exp(C_\varepsilon\omega(a))\tau(a)^2
\ll(2+\log AV)^{C_\varepsilon}J^\varepsilon A^2V.
\end{aligned} a ∼ A e ∼ V ∑ b ∼ J b ∣ ( a e ) ∞ ∑ ( b e 2 , a ) ≪ ( 2 + log V ) C ε J ε V h 1 h 2 ∣ a ∼ A ∑ h 1 1 − ε h 2 exp ( C ε ω ( a )) ≪ ( 2 + log V ) C ε J ε A V a ∼ A ∑ exp ( C ε ω ( a )) τ ( a ) 2 ≪ ( 2 + log A V ) C ε J ε A 2 V .
Proof of Lemma 5
Let 1 ≤ a ≤ n η 1\le a\le n^\eta 1 ≤ a ≤ n η be squarefree. By completing the e e e range we have
M 1 ( a ) = Li ( n − 1 ) ∑ e ≥ 1 d ≤ D ( d e , n ) = 1 μ ( e ) ϕ ( [ d e 2 , a ] ) + O ( n V ) , M 2 ( a ) = ∑ e ≥ 1 d < ( n − 2 ) / ( e 2 D ) ( d e , n ) = 1 μ ( e ) Li ( n − d e 2 D − 1 ) ϕ ( [ d e 2 , a ] ) + O ( n V ) . M_1(a)=\operatorname{Li}(n-1)\sum_{\substack{e\ge1\\ d\le D\\ (de,n)=1}}\frac{\mu(e)}{\phi([de^2,a])}+O\left(\frac{n}{V}\right),
\qquad
M_2(a)=\sum_{\substack{e\ge1\\ d<(n-2)/(e^2D)\\ (de,n)=1}}\frac{\mu(e)\operatorname{Li}(n-de^2D-1)}{\phi([de^2,a])}+O\left(\frac{n}{V}\right). M 1 ( a ) = Li ( n − 1 ) e ≥ 1 d ≤ D ( d e , n ) = 1 ∑ ϕ ([ d e 2 , a ]) μ ( e ) + O ( V n ) , M 2 ( a ) = e ≥ 1 d < ( n − 2 ) / ( e 2 D ) ( d e , n ) = 1 ∑ ϕ ([ d e 2 , a ]) μ ( e ) Li ( n − d e 2 D − 1 ) + O ( V n ) .
The n / V n/V n / V error is more than sufficient for Lemma 5. We now decompose, up to admissible error terms both M 1 ( a ) M_1(a) M 1 ( a ) and M 2 ( a ) M_2(a) M 2 ( a ) as follows. Let
M 1 ( a ) = M 1 , 1 ( a ) + M 1 , 2 ( a ) + O ( n / V ) , M_1(a)=M_{1,1}(a)+M_{1,2}(a)+O(n/V), M 1 ( a ) = M 1 , 1 ( a ) + M 1 , 2 ( a ) + O ( n / V ) ,
M 2 ( a ) = M 2 , 1 ( a ) + M 2 , 2 ( a ) + O ( n / V ) , M_2(a)=M_{2,1}(a)+M_{2,2}(a)+O(n/V), M 2 ( a ) = M 2 , 1 ( a ) + M 2 , 2 ( a ) + O ( n / V ) ,
where we split according to d e 2 ≤ D de^{2} \le D d e 2 ≤ D or not
M 1 , 1 ( a ) = Li ( n − 1 ) ∑ d e 2 ≤ D ( d e , n ) = 1 μ ( e ) ϕ ( [ d e 2 , a ] ) . M_{1,1}(a)=\operatorname{Li}(n-1)\sum_{\substack{de^{2}\le D\\(de,n)=1}}\frac{\mu(e)}{\phi([de^{2},a])}. M 1 , 1 ( a ) = Li ( n − 1 ) d e 2 ≤ D ( d e , n ) = 1 ∑ ϕ ([ d e 2 , a ]) μ ( e ) .
M 1 , 2 ( a ) = Li ( n − 1 ) ∑ d e 2 > D d ≤ D ( d e , n ) = 1 μ ( e ) ϕ ( [ d e 2 , a ] ) . M_{1,2}(a)=\operatorname{Li}(n-1)\sum_{\substack{de^{2}>D\\d\le D\\(de,n)=1}}\frac{\mu(e)}{\phi([de^{2},a])}. M 1 , 2 ( a ) = Li ( n − 1 ) d e 2 > D d ≤ D ( d e , n ) = 1 ∑ ϕ ([ d e 2 , a ]) μ ( e ) .
and where for M 2 M_{2} M 2 we use Li ( n − d e 2 D − 1 ) = Li ( n − 1 ) + O ( d e 2 D / log n ) \operatorname{Li}(n-de^{2}D-1)=\operatorname{Li}(n-1)+O(de^{2}D/\log n) Li ( n − d e 2 D − 1 ) = Li ( n − 1 ) + O ( d e 2 D / log n ) so that
M 2 , 1 ( a ) = Li ( n − 1 ) ∑ d e 2 < ( n − 2 ) / D ( d e , n ) = 1 μ ( e ) ϕ ( [ d e 2 , a ] ) . M_{2,1}(a)=\operatorname{Li}(n-1)\sum_{\substack{de^{2}<(n-2)/D\\(de,n)=1}}\frac{\mu(e)}{\phi([de^{2},a])}. M 2 , 1 ( a ) = Li ( n − 1 ) d e 2 < ( n − 2 ) / D ( d e , n ) = 1 ∑ ϕ ([ d e 2 , a ]) μ ( e ) .
M 2 , 2 ( a ) ≪ D log n ∑ d e 2 < ( n − 2 ) / D d e 2 μ 2 ( e ) ϕ ( [ d e 2 , a ] ) . M_{2,2}(a)\ll\frac{D}{\log n}\sum_{de^{2}<(n-2)/D}\frac{de^{2}\mu^{2}(e)}{\phi([de^{2},a])}. M 2 , 2 ( a ) ≪ log n D d e 2 < ( n − 2 ) / D ∑ ϕ ([ d e 2 , a ]) d e 2 μ 2 ( e ) .
We claim that for square-free 1 ≤ a ≤ n η 1\le a\le n^{\eta} 1 ≤ a ≤ n η with ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k ,
M 1 , 2 ( a ) , M 2 , 2 ( a ) ≪ k n log log n a log n . (15) M_{1,2}(a),M_{2,2}(a)\ll_{k}\frac{n\log\log n}{a\log n}. \tag*{(15)} M 1 , 2 ( a ) , M 2 , 2 ( a ) ≪ k a log n n log log n . (15)
M 1 , 1 ( a ) + M 1 , 2 ( a ) = Li ( n − 1 ) 2 ω ( a ) a ( ϕ ( n ) n log n + O k ( ( log log n ) 2 ) ) − 2 Li ( n − 1 ) ϕ ( n ) n D a ϕ ( a ) . (16) M_{1,1}(a)+M_{1,2}(a)=\operatorname{Li}(n-1)\frac{2^{\omega(a)}}{a}\left(\frac{\phi(n)}{n}\log n+O_{k}((\log\log n)^{2})\right)-\frac{2\operatorname{Li}(n-1)\phi(n)}{n}\frac{D_{a}}{\phi(a)}. \tag*{(16)} M 1 , 1 ( a ) + M 1 , 2 ( a ) = Li ( n − 1 ) a 2 ω ( a ) ( n ϕ ( n ) log n + O k (( log log n ) 2 ) ) − n 2 Li ( n − 1 ) ϕ ( n ) ϕ ( a ) D a . (16)
which implies Lemma 5, as we can replace Li ( n − 1 ) \operatorname{Li}(n-1) Li ( n − 1 ) by n / log n + O ( n / log 2 n ) n/\log n+O(n/\log^{2}n) n / log n + O ( n / log 2 n ) , incurring an acceptable error.
We now bound M 1 , 2 ( a ) M_{1,2}(a) M 1 , 2 ( a ) . We have
M 1 , 2 ( a ) ≪ n log n ∑ D < d e 2 ≤ D e 2 μ 2 ( e ) ϕ ( [ d e 2 , a ] ) ≪ n log log n log n ∑ D < d e 2 ≤ D e 2 1 [ d e 2 , a ] . M_{1,2}(a)\ll\frac{n}{\log n}\sum_{D<de^{2}\le De^{2}}\frac{\mu^{2}(e)}{\phi([de^{2},a])}\ll\frac{n\log\log n}{\log n}\sum_{D<de^{2}\le De^{2}}\frac{1}{[de^{2},a]}. M 1 , 2 ( a ) ≪ log n n D < d e 2 ≤ D e 2 ∑ ϕ ([ d e 2 , a ]) μ 2 ( e ) ≪ log n n log log n D < d e 2 ≤ D e 2 ∑ [ d e 2 , a ] 1 .
Since a a a is squarefree, letting ( d e 2 , a ) = g (de^{2},a)=g ( d e 2 , a ) = g there are g 1 , g 2 g_{1},g_{2} g 1 , g 2 (not necessarily unique) with g = g 1 g 2 g=g_{1}g_{2} g = g 1 g 2 , g 1 ∣ e g_{1}\mid e g 1 ∣ e and g 2 ∣ d g_{2}\mid d g 2 ∣ d . Thus,
∑ D < d e 2 ≤ D e 2 1 [ d e 2 , a ] = a − 1 ∑ e ≥ 1 e − 2 ∑ D / e 2 < d ≤ D ( d e 2 , a ) ( d e 2 , a ) d − 1 ≤ a − 1 ∑ g 1 g 2 ∣ a g 1 g 2 ∑ g 1 ∣ e e − 2 ∑ D / e 2 < d ≤ D g 2 ∣ d d − 1 ≪ a − 1 ∑ g 1 g 2 ∣ a g 1 − 1 ( 1 + log g 1 ) ≪ a − 1 3 ω ( a ) . \begin{aligned}
\sum_{D<de^{2}\le De^{2}}\frac{1}{[de^{2},a]}=a^{-1}\sum_{e\ge1}e^{-2}\sum_{\substack{D/e^{2}<d\le D\\(de^{2},a)}}(de^{2},a)d^{-1} \\
&\le a^{-1}\sum_{g_{1}g_{2}\mid a}g_{1}g_{2}\sum_{g_{1}\mid e}e^{-2}\sum_{\substack{D/e^{2}<d\le D\\g_{2}\mid d}}d^{-1} \\
&\ll a^{-1}\sum_{g_{1}g_{2}\mid a}g_{1}^{-1}(1+\log g_{1})\ll a^{-1}3^{\omega(a)}.
\end{aligned} D < d e 2 ≤ D e 2 ∑ [ d e 2 , a ] 1 = a − 1 e ≥ 1 ∑ e − 2 D / e 2 < d ≤ D ( d e 2 , a ) ∑ ( d e 2 , a ) d − 1 ≤ a − 1 g 1 g 2 ∣ a ∑ g 1 g 2 g 1 ∣ e ∑ e − 2 D / e 2 < d ≤ D g 2 ∣ d ∑ d − 1 ≪ a − 1 g 1 g 2 ∣ a ∑ g 1 − 1 ( 1 + log g 1 ) ≪ a − 1 3 ω ( a ) .
Since ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k in Lemma 5, this is sufficient for (3.4).
We now bound M 2 , 2 ( a ) M_{2,2}(a) M 2 , 2 ( a ) . Writing m = d e 2 m=de^{2} m = d e 2 , we have
M 2 , 2 ( a ) ≪ D log n ∑ m < n / D m 2 # { p 2 ∣ m } ϕ ( [ m , a ] ) . (17) M_{2,2}(a)\ll\frac{D}{\log n}\sum_{m<n/D}\frac{m2^{\#\{p^{2}\mid m\}}}{\phi([m,a])}. \tag*{(17)} M 2 , 2 ( a ) ≪ log n D m < n / D ∑ ϕ ([ m , a ]) m 2 # { p 2 ∣ m } . (17)
We let g = ( a , m ) g=(a,m) g = ( a , m ) in the right-hand side of (17) and observe 1 / φ ( [ m , a ] ) ≤ 1 / φ ( a ) φ ( m / g ) 1/\varphi([m,a])\leq1/\varphi(a)\varphi(m/g) 1/ φ ([ m , a ]) ≤ 1/ φ ( a ) φ ( m / g ) to find
M 2 , 2 ( a ) ≪ D log n φ ( a ) ∑ g ∣ a g ∑ g ∣ m < n / D ( m / g ) 2 # { p 2 ∣ m } φ ( m / g ) . M_{2,2}(a)\ll\frac{D}{\log n\varphi(a)}\sum_{g\mid a}g\sum_{g\mid m<n/D}\frac{(m/g)2^{\#\{p^2\mid m\}}}{\varphi(m/g)}. M 2 , 2 ( a ) ≪ log n φ ( a ) D g ∣ a ∑ g g ∣ m < n / D ∑ φ ( m / g ) ( m / g ) 2 # { p 2 ∣ m } .
Let S ( x ) : = ∑ m ≤ X ( m / φ ( m ) ) 2 # { p 2 ∣ m } S(x):=\sum_{m\leq X}(m/\varphi(m))2^{\#\{p^2\mid m\}} S ( x ) := ∑ m ≤ X ( m / φ ( m )) 2 # { p 2 ∣ m } . This sum is ≪ X \ll X ≪ X [9 ] . Hence
M 2 , 2 ( a ) ≪ D log n φ ( a ) ∑ g ∣ a g 2 ω ( g ) S ( n D g ) ≪ n log n φ ( a ) 3 ω ( a ) , M_{2,2}(a)\ll\frac{D}{\log n\varphi(a)}\sum_{g\mid a}g2^{\omega(g)}S\left(\frac{n}{Dg}\right)\ll\frac{n}{\log n\varphi(a)}3^{\omega(a)}, M 2 , 2 ( a ) ≪ log n φ ( a ) D g ∣ a ∑ g 2 ω ( g ) S ( D g n ) ≪ log n φ ( a ) n 3 ω ( a ) ,
which suffices for (15) .
We now prove (16) . We have
M 1 , 1 ( a ) = Li ( n − 1 ) ∑ m ≤ D ( m , n ) = 1 μ 2 ( m ) φ ( [ m , a ] ) . M_{1,1}(a)=\operatorname{Li}(n-1)\sum_{\substack{m\leq D\\(m,n)=1}}\frac{\mu^2(m)}{\varphi([m,a])}. M 1 , 1 ( a ) = Li ( n − 1 ) m ≤ D ( m , n ) = 1 ∑ φ ([ m , a ]) μ 2 ( m ) .
and
M 2 , 1 ( a ) = Li ( n − 1 ) ∑ m < ( n − 2 ) / D ( m , n ) = 1 μ 2 ( m ) φ ( [ m , a ] ) . M_{2,1}(a)=\operatorname{Li}(n-1)\sum_{\substack{m<(n-2)/D\\(m,n)=1}}\frac{\mu^2(m)}{\varphi([m,a])}. M 2 , 1 ( a ) = Li ( n − 1 ) m < ( n − 2 ) / D ( m , n ) = 1 ∑ φ ([ m , a ]) μ 2 ( m ) .
We claim that
∑ m < X ( m , n ) = 1 μ 2 ( m ) φ ( [ m , a ] ) = 2 ω ( a ) a ( φ ( n ) n log X + O k ( ( log log n ) 2 ) ) − φ ( n ) n D a φ ( a ) (18) \sum_{\substack{m<X\\(m,n)=1}}\frac{\mu^2(m)}{\varphi([m,a])}=\frac{2^{\omega(a)}}{a}\left(\frac{\varphi(n)}{n}\log X+O_k\left((\log\log n)^2\right)\right)-\frac{\varphi(n)}{n}\frac{D_a}{\varphi(a)} \tag*{(18)} m < X ( m , n ) = 1 ∑ φ ([ m , a ]) μ 2 ( m ) = a 2 ω ( a ) ( n φ ( n ) log X + O k ( ( log log n ) 2 ) ) − n φ ( n ) φ ( a ) D a (18)
holds uniformly for a ≤ n η a\leq n^\eta a ≤ n η and X ≥ n 1 / 3 X\geq n^{1/3} X ≥ n 1/3 with ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 , μ 2 ( a ) = 1 \mu^2(a)=1 μ 2 ( a ) = 1 and ω ( a ) ≤ k \omega(a)\leq k ω ( a ) ≤ k . With this we can evaluate M 1 , 1 ( a ) + M 2 , 1 ( a ) M_{1,1}(a)+M_{2,1}(a) M 1 , 1 ( a ) + M 2 , 1 ( a ) by applying (18) with X = D X=D X = D and X = n / D X=n/D X = n / D to obtain (16) .
To show (18) , we introduce the multiplicative function
f n , a ( m ) : = 1 ( m , n ) = 1 μ 2 ( m ) φ ( a ) / φ ( [ m , a ] ) . f_{n,a}(m):=\mathbf{1}_{(m,n)=1}\mu^2(m)\varphi(a)/\varphi([m,a]). f n , a ( m ) := 1 ( m , n ) = 1 μ 2 ( m ) φ ( a ) / φ ([ m , a ]) .
Elliott and Halberstam established [5 ]
∑ m < X f n , 1 ( m ) = φ ( n ) n log X + O ( ( log log n ) 2 ) (19) \sum_{m<X}f_{n,1}(m)=\frac{\varphi(n)}{n}\log X+O((\log\log n)^2) \tag*{(19)} m < X ∑ f n , 1 ( m ) = n φ ( n ) log X + O (( log log n ) 2 ) (19)
for n ≤ X 5 n\leq X^5 n ≤ X 5 . We have f n , a = f n , 1 ∗ g n , a f_{n,a}=f_{n,1}*g_{n,a} f n , a = f n , 1 ∗ g n , a where g n , a g_{n,a} g n , a is multiplicative, supported on odd divisors of a ∞ a^\infty a ∞ and defined on p k p^k p k via g n , a ( p k ) = ( − 1 ) k − 1 ( p − 2 ) / ( p − 1 ) k g_{n,a}(p^k)=(-1)^{k-1}(p-2)/(p-1)^k g n , a ( p k ) = ( − 1 ) k − 1 ( p − 2 ) / ( p − 1 ) k . Hence, by (19) ,
∑ m < X ( m , n ) = 1 μ 2 ( m ) φ ( [ m , a ] ) = ∑ m < X f n , a ( m ) φ ( a ) = φ ( n ) n φ ( a ) ∑ d ≤ X / n 1 / 5 g n , a ( d ) log ( X / d ) + O ( E φ ( a ) ) (20) \sum_{\substack{m<X\\(m,n)=1}}\frac{\mu^2(m)}{\varphi([m,a])}=\sum_{m<X}\frac{f_{n,a}(m)}{\varphi(a)}=\frac{\varphi(n)}{n\varphi(a)}\sum_{d\leq X/n^{1/5}}g_{n,a}(d)\log(X/d)+O\left(\frac{E}{\varphi(a)}\right) \tag*{(20)} m < X ( m , n ) = 1 ∑ φ ([ m , a ]) μ 2 ( m ) = m < X ∑ φ ( a ) f n , a ( m ) = n φ ( a ) φ ( n ) d ≤ X / n 1/5 ∑ g n , a ( d ) log ( X / d ) + O ( φ ( a ) E ) (20)
for
E : = ∑ d < X ∣ g n , a ( d ) ∣ ( log log n ) 2 + ∑ d > X / n 1 / 5 ∣ g n , a ( d ) ∣ log d . (21) E:=\sum_{d<X}|g_{n,a}(d)|(\log\log n)^2+\sum_{d>X/n^{1/5}}|g_{n,a}(d)|\log d. \tag*{(21)} E := d < X ∑ ∣ g n , a ( d ) ∣ ( log log n ) 2 + d > X / n 1/5 ∑ ∣ g n , a ( d ) ∣ log d . (21)
To bound the first sum in E E E we use ∑ d ≥ 1 ∣ g n , a ( d ) ∣ = 2 ω ( a ) − 1 2 1 2 ∣ a ≪ k 1 \sum_{d\geq1}|g_{n,a}(d)|=2^{\omega(a)-1}2^{\mathbf{1}_{2\mid a}}\ll_k1 ∑ d ≥ 1 ∣ g n , a ( d ) ∣ = 2 ω ( a ) − 1 2 1 2 ∣ a ≪ k 1 . We turn to the second sum in E E E . If d d d is in the support of g n , a g_{n,a} g n , a then
∣ g n , a ( d ) ∣ ≤ ∏ p ∣ d ∏ p i ∣ d p − i ∏ p i ∣ d ( 1 + 1 p − 1 ) i − 1 ≤ a d ∏ p i ∣ d ( 1 + 1 p − 1 ) i − 1 ≤ a d ( 3 / 2 ) log 3 d . |g_{n,a}(d)|\leq\prod_{p\mid d}\prod_{p^i\mid d}p^{-i}\prod_{p^i\mid d}\left(1+\frac{1}{p-1}\right)^{i-1}\leq\frac{a}{d}\prod_{p^i\mid d}\left(1+\frac{1}{p-1}\right)^{i-1}\leq\frac{a}{d}(3/2)^{\log_3d}. ∣ g n , a ( d ) ∣ ≤ p ∣ d ∏ p i ∣ d ∏ p − i p i ∣ d ∏ ( 1 + p − 1 1 ) i − 1 ≤ d a p i ∣ d ∏ ( 1 + p − 1 1 ) i − 1 ≤ d a ( 3/2 ) l o g 3 d .
If ω ( a ) ≤ k \omega(a) \le k ω ( a ) ≤ k then there are ≪ k ( log T ) k \ll_k (\log T)^k ≪ k ( log T ) k integers d ∈ [ T , 2 T ) d \in[T,2T) d ∈ [ T , 2 T ) with d ∣ a ∞ d \mid a^\infty d ∣ a ∞ , so
∑ d ∈ [ T , 2 T ) ∣ g n , a ( d ) ∣ ≪ k a ( log T ) k T T log ( 3 / 2 ) / log 3 . \sum_{d\in[T,2T)} \lvert g_{n,a}(d)\rvert\ll_k \frac{a(\log T)^k}{T}T^{\log(3/2)/\log3}. d ∈ [ T , 2 T ) ∑ ∣ g n , a ( d )∣ ≪ k T a ( log T ) k T l o g ( 3/2 ) / l o g 3 .
This implies that under our assumptions, E / ϕ ( a ) ≪ k ( log log n ) 2 / a E/\phi(a) \ll_k (\log\log n)^2/a E / ϕ ( a ) ≪ k ( log log n ) 2 / a . With the same E E E as in (3.10), we express the main term in (3.9) as
∑ d ≤ X / n 1 / 5 g n , a ( d ) log ( X / d ) = log X ∏ p ∣ a ( ∑ i = 0 ∞ g n , a ( p i ) ) − ∑ d ≥ 1 g n , a ( d ) log d + O ( E ) . \sum_{d\le X/n^{1/5}}g_{n,a}(d)\log(X/d)=\log X\prod_{p\mid a}\left(\sum_{i=0}^{\infty}g_{n,a}(p^i)\right)-\sum_{d\ge1}g_{n,a}(d)\log d+O(E). d ≤ X / n 1/5 ∑ g n , a ( d ) log ( X / d ) = log X p ∣ a ∏ ( i = 0 ∑ ∞ g n , a ( p i ) ) − d ≥ 1 ∑ g n , a ( d ) log d + O ( E ) .
times ϕ ( n ) / ( n ϕ ( a ) ) \phi(n)/(n\phi(a)) ϕ ( n ) / ( n ϕ ( a )) . The product is 2 ω ( a ) ϕ ( a ) / a 2^{\omega(a)}\phi(a)/a 2 ω ( a ) ϕ ( a ) / a and the d d d -sum is D a D_a D a .
References
Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK
E-mail addresses: [email protected] [email protected]