Introduction and motivation
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 that [9 ]
∑ 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)
holds for n ≥ 3 n\ge3 n ≥ 3 . 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 [10 Conj. B] : 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 (2) \sum_{\substack{p<n\\ \omega(n-p)\le2\log\log n+\lambda(2\log\log n)^{1/2}}}2^{\omega(n-p)}
\to\frac{\phi(n)}{\sqrt{2\pi}}\int_{-\infty}^{\lambda}e^{-u^2/2}\,du \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 (2)
as n → ∞ n\to\infty n → ∞ . In this note we establish the conjecture.
Theorem 1.1. The asymptotic relation (1.2) holds for each real λ \lambda λ .
Theorem 1.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)}\mathbf{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}}\xrightarrow{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. The proof of Theorem 1.1 will follow from
Proposition 1.2. Fix k , B ≥ 1 k,B\ge1 k , B ≥ 1 . For any 1 ≤ R ≤ n 1 / 100 1\le R\le n^{1/100} 1 ≤ R ≤ n 1/100 and S ⊆ N S\subseteq\mathbb{N} S ⊆ N we have
∑ a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) ∣ P ( a divides X n ) − 2 ω ( a ) a ∣ ≪ k , B ( log log n ) 3 + log R log n ∑ a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) a + 1 log B n . \sum_{\substack{a\le R,\ a\in S\\ \omega(a)\le k\\ (a,n)=1}}\mu^2(a)\left|\mathbb{P}(a\text{ divides }X_n)-\frac{2^{\omega(a)}}{a}\right|
\ll_{k,B}\frac{(\log\log n)^3+\log R}{\log n}\sum_{\substack{a\le R,\ a\in S\\ \omega(a)\le k\\ (a,n)=1}}\frac{\mu^2(a)}{a}+\frac{1}{\log^B n}. a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 ∑ μ 2 ( a ) P ( a divides X n ) − a 2 ω ( a ) ≪ k , B log n ( log log n ) 3 + log R a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 ∑ a μ 2 ( a ) + log B n 1 .
The reduction of Theorem 1.1 to Proposition 1.2 is explained in §3. The proof of Proposition 1.2 is given in §4 and uses the classical tools utilized in [9 ] (the Brun–Titchmarsh and Bombieri–Vinogradov Theorems). Proposition 1.2 has little content when log R ≍ log n \log R\asymp\log n log R ≍ log n . This is remedied by the following proposition, proved using recent work on primes in arithmetic progressions [6 ] .
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).
Proposition 1.3. There is an absolute constant η > 0 \eta> 0 η > 0 with the following property. For every k ≥ 1 k \ge1 k ≥ 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 ) C k log n (4) \sum_{\substack{a \le n\\ \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)^{C_k}}{\log n} \tag*{(4)} 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 ) C k (4) where C k C_k C k is a positive constant depending only on k k k ,
D a : = ∑ d ∣ a ∞ g ( d ) log d , g ( d ) : = ∏ p k ∥ d ( − 1 ) k − 1 ( p − 2 ) ( p − 1 ) − k . (5) 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}. \tag*{(5)} D a := d ∣ a ∞ ∑ g ( d ) log d , g ( d ) := p k ∥ d ∏ ( − 1 ) k − 1 ( p − 2 ) ( p − 1 ) − k . (5) Since ∑ d ∣ a ∞ ∣ g ( d ) ∣ = 2 ω ( a ) − 1 2 ω ( a ) \sum_{d\mid a^\infty}|g(d)|=2^{\omega(a)-1}2^{\omega(a)} ∑ d ∣ a ∞ ∣ g ( d ) ∣ = 2 ω ( a ) − 1 2 ω ( a ) , we have
∣ D a ∣ ≤ ∑ p ∣ a ∑ i ≥ 1 log ( p i ) ∑ p i ∣ ∣ d ∣ a ∞ ∣ g ( d ) ∣ ≤ 2 ω ( a ) ∑ p ∣ a ∑ i ≥ 1 log ( p i ) ∣ g ( p i ) ∣ ≪ 2 ω ( a ) log a . (6) |D_a|\le\sum_{p\mid a}\sum_{i\ge1}\log(p^i)\sum_{p^i\mid\mid d\mid a^\infty}|g(d)|
\le2^{\omega(a)}\sum_{p\mid a}\sum_{i\ge1}\log(p^i)|g(p^i)|\ll2^{\omega(a)}\log a. \tag*{(6)} ∣ D a ∣ ≤ p ∣ a ∑ i ≥ 1 ∑ log ( p i ) p i ∣∣ d ∣ a ∞ ∑ ∣ g ( d ) ∣ ≤ 2 ω ( a ) p ∣ a ∑ i ≥ 1 ∑ log ( p i ) ∣ g ( p i ) ∣ ≪ 2 ω ( a ) log a . (6)
Proposition 1.3 is proved in §5. The lower order term in (4) leads to the following application. Given an integer m > 1 m>1 m > 1 we write it as m = ∏ i = 1 Ω ( m ) p i ( m ) m=\prod_{i=1}^{\Omega(m)}p_i(m) m = ∏ i = 1 Ω ( m ) p i ( m ) where Ω ( m ) \Omega(m) Ω ( m ) is the number of prime factors of m m m (multiplicity counted) and p 1 ( m ) ≥ ⋯ ≥ p Ω ( m ) ( m ) p_1(m)\ge\cdots\ge p_{\Omega(m)}(m) p 1 ( m ) ≥ ⋯ ≥ p Ω ( m ) ( m ) . We define
V ( m ) : = ( log p i ( m ) log m ) i ≥ 1 (7) V(m):=\left(\frac{\log p_i(m)}{\log m}\right)_{i\ge1} \tag*{(7)} V ( m ) := ( log m log p i ( m ) ) i ≥ 1 (7)
where p i ( m ) : = 1 p_i(m):=1 p i ( m ) := 1 for i > Ω ( m ) i>\Omega(m) i > Ω ( m ) . This vector sums to 1 and its entries are nonincreasing. Let PD ( θ ) \operatorname{PD}(\theta) PD ( θ ) be the Poisson–Dirichlet distribution with parameter θ \theta θ (see Chapter 1 of [5 ] for its definition).
Corollary 1.4. If V ( X n ) V(X_n) V ( X n ) tends in distribution to PD ( θ ) \operatorname{PD}(\theta) PD ( θ ) for some θ > 0 \theta>0 θ > 0 then θ = 2 \theta=2 θ = 2 .
Let X ~ n \widetilde{X}_n X n be the 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 ) 2^{\omega(m)} 2 ω ( m ) . As observed by Elliott [10 ] ,
ω ( X ~ n ) − 2 log log n ( 2 log log n ) 1 / 2 → d N ( 0 , 1 ) , n → ∞ . (8) \frac{\omega(\widetilde{X}_n)-2\log\log n}{(2\log\log n)^{1/2}}\xrightarrow{d}N(0,1),\qquad n\to\infty. \tag*{(8)} ( 2 log log n ) 1/2 ω ( X n ) − 2 log log n d N ( 0 , 1 ) , n → ∞. (8)
See §6 for a self-contained proof of (8) . As shown in [8 ] , V ( X ~ n ) V(\widetilde{X}_n) V ( X n ) tends to PD ( 2 ) \operatorname{PD}(2) PD ( 2 ) . We expect Theorem 1.1 and Corollary 1.4 to hold because X n X_n X n is distributed like X ~ n \widetilde{X}_n X n , only with support restricted to shifted primes which are believed to behave in most ways like random integers.
The structure of the paper is as follows. In the next short section we show how Corollary 1.4 follows from Proposition 1.3. Afterwards in §3 we reduce the conjecture of Elliott we prove, Theorem 1.1 to Proposition 1.2. In §4 we show how Proposition 1.2 follows from the classical Bombieri–Vinogradov and Brun–Titchmarsh Theorems. At this point the proof of Theorem 1.1 is complete. In the penultimate §5 we go beyond the Bombieri–Vinogradov range by employing a result in [6 ] , based on spectral theory of automorphic forms, to prove Proposition 1.3. As mentioned in the last paragraph, we conclude the paper with a short proof of (8) .
Proof of Corollary 1.4
We now show how Corollary 1.4 follows from Proposition 1.3. Suppose V ( X n ) → d PD ( θ ) V(X_n)\xrightarrow{d}\operatorname{PD}(\theta) V ( X n ) d PD ( θ ) , and in particular V ( X n ) i → d PD ( θ ) i V(X_n)_i\xrightarrow{d}\operatorname{PD}(\theta)_i V ( X n ) i d PD ( θ ) i for all i i i . Since 2 ω ( n − p ) = n o ( 1 ) 2^{\omega(n-p)}=n^{o(1)} 2 ω ( n − p ) = n o ( 1 ) , we have P ( X n ≤ T ) ≪ T / n 1 + o ( 1 ) \mathbb{P}(X_n\le T)\ll T/n^{1+o(1)} P ( X n ≤ T ) ≪ T / n 1 + o ( 1 ) , so that log X n / log n \log X_n/\log n log X n / log n tends to 1 in probability. This implies V ~ ( X n ) i → d PD ( θ ) i \widetilde{V}(X_n)_i\xrightarrow{d}\operatorname{PD}(\theta)_i V ( X n ) i d PD ( θ ) i for V ~ ( X n ) i : = log p i ( X n ) / log n \widetilde{V}(X_n)_i:=\log p_i(X_n)/\log n V ( X n ) i := log p i ( X n ) / log n . By [12 Thm. 2.1] ,
lim n → ∞ E ∑ i = 1 ∞ 1 V ~ ( X n ) i ∈ [ a , b ] = θ ∫ a b ( 1 − t ) θ − 1 t d t \lim_{n\to\infty}\mathbb{E}\sum_{i=1}^{\infty}\mathbf{1}_{\widetilde{V}(X_n)_i\in[a,b]}=\theta\int_a^b\frac{(1-t)^{\theta-1}}{t}\,dt n → ∞ lim E i = 1 ∑ ∞ 1 V ( X n ) i ∈ [ a , b ] = θ ∫ a b t ( 1 − t ) θ − 1 d t
for all 0 < a < b < 1 0<a<b<1 0 < a < b < 1 (the sum appears infinite but can be truncated at i ≤ ⌊ 1 / a ⌋ i\le\lfloor1/a\rfloor i ≤ ⌊ 1/ a ⌋ since ∑ i ≥ 1 V ~ ( X n ) i ≤ 1 \sum_{i\ge1}\widetilde{V}(X_n)_i\le1 ∑ i ≥ 1 V ( X n ) i ≤ 1 ). This is simplified as
lim n → ∞ ∑ p ∈ [ n a , n b ] ∑ k ≥ 1 P ( p k divides X n ) = θ ∫ a b ( 1 − t ) θ − 1 t d t . (9) \lim_{n\to\infty}\sum_{p\in[n^a,n^b]}\sum_{k\ge1}\mathbb{P}(p^k\text{ divides }X_n)=\theta\int_a^b\frac{(1-t)^{\theta-1}}{t}\,dt. \tag*{(9)} n → ∞ lim p ∈ [ n a , n b ] ∑ k ≥ 1 ∑ P ( p k divides X n ) = θ ∫ a b t ( 1 − t ) θ − 1 d t . (9)
Since P ( d ∣ X n ) ≪ n o ( 1 ) / d \mathbb{P}(d\mid X_n)\ll n^{o(1)}/d P ( d ∣ X n ) ≪ n o ( 1 ) / d , (2.1) is equivalent to
lim n → ∞ ∑ n a ≤ p ≤ n b P ( p ∣ X n ) = θ ∫ a b ( 1 − t ) θ − 1 t d t . (10) \lim_{n\to\infty}\sum_{n^a\le p\le n^b}\mathbb{P}(p\mid X_n)=\theta\int_a^b\frac{(1-t)^{\theta-1}}{t}\,dt. \tag*{(10)} n → ∞ lim n a ≤ p ≤ n b ∑ P ( p ∣ X n ) = θ ∫ a b t ( 1 − t ) θ − 1 d t . (10)
By Proposition 1.3 with k = 1 k=1 k = 1 we have
lim n → ∞ ∑ n a ≤ p ≤ n b P ( p ∣ X n ) = 2 ∫ a b 1 − t t d t \lim_{n\to\infty}\sum_{n^a\le p\le n^b}\mathbb{P}(p\mid X_n)=2\int_a^b\frac{1-t}{t}\,dt n → ∞ lim n a ≤ p ≤ n b ∑ P ( p ∣ X n ) = 2 ∫ a b t 1 − t d t
by Mertens’ theorem [13 Thm. 2.7(d)] , as long as b < η b<\eta b < η . This is consistent with (2.2) only if θ = 2 \theta=2 θ = 2 .
Remark 2.1. More generally, let k ≥ 1 k\ge1 k ≥ 1 and a continuous function f : R k → C f:\mathbb{R}^k\to\mathbb{C} f : R k → C such that the (closure of the) support of f f f is ⊆ { ( x 1 , … , x k ) : x 1 , … , x k > 0 , x 1 + ⋯ + x k < η } \subseteq\{(x_1,\ldots,x_k):x_1,\ldots,x_k>0,\ x_1+\cdots+x_k<\eta\} ⊆ {( x 1 , … , x k ) : x 1 , … , x k > 0 , x 1 + ⋯ + x k < η } . Then with additional work one can compute
lim n → ∞ E ∑ j 1 , … , j k d i s t i n c t f ( V ( X n ) j 1 , … , V ( X n ) j k ) \lim_{n\to\infty}\mathbb{E}\sum_{j_1,\ldots,j_k\ {\rm distinct}}f\bigl(V(X_n)_{j_1},\ldots,V(X_n)_{j_k}\bigr) n → ∞ lim E j 1 , … , j k distinct ∑ f ( V ( X n ) j 1 , … , V ( X n ) j k )
using Proposition 1.3 and show that it coincides with
E ∑ j 1 , … , j k d i s t i n c t f ( L j 1 , … , L j k ) \mathbb{E}\sum_{j_1,\ldots,j_k\ {\rm distinct}}f(L_{j_1},\ldots,L_{j_k}) E j 1 , … , j k distinct ∑ f ( L j 1 , … , L j k )
where ( L 1 , L 2 , … ) (L_1,L_2,\ldots) ( L 1 , L 2 , … ) is distributed according to PD ( 2 ) \operatorname{PD}(2) PD ( 2 ) . In the language of Bharadwaj and Rodgers [3 ] , this means we can compute the correlation functions of large prime factors of X n X_n X n and show they tend to those of the Poisson–Dirichlet process with parameter θ = 2 \theta=2 θ = 2 , at least for test functions with restricted support.
Reduction
We now reduce Theorem 1.1 to Proposition 1.2. In other words, we make precise the well-known principle (see for example [11 ] ) that Erdős–Kac type results can be deduced from level of distribution information.
Let
C k : = E X k , C k ′ : = E ∣ X ∣ k , (11) C_k:=\mathbb{E}X^k,\qquad C'_k:=\mathbb{E}|X|^k, \tag*{(11)} C k := E X k , C k ′ := E ∣ X ∣ k , (11)
where X ∼ N ( 0 , 1 ) X\sim N(0,1) X ∼ N ( 0 , 1 ) . It is known that for (1.3) to hold it suffices to show that
E ( ω ( X n ) − 2 log log n ( 2 log log n ) 1 / 2 ) k → C k , n → ∞ , (12) \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*{(12)} E ( ( 2 log log n ) 1/2 ω ( X n ) − 2 log log n ) k → C k , n → ∞ , (12)
holds for every integer k ≥ 1 k\ge1 k ≥ 1 [7 Ch. 3.3.5] . To approach (3.2) we use
Proposition 3.1. [11 ] Let f : N → R ≥ 0 f:\mathbb{N}\to\mathbb{R}_{\ge0} 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}_{\ge0} h : N → R ≥ 0 be a multiplicative function with h ( p ) ≤ p h(p)\le 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\le n\\a\mid m}}f(m)=\frac{h(a)}{a}\sum_{m\le 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\le k\le\sigma_{\mathcal{P}}^{2/3} 1 ≤ k ≤ σ P 2/3 we have
∑ m = 1 n f ( m ) ( ∑ p ∣ P 1 p ∣ m − μ P ) k = σ P k ∑ m = 1 n f ( m ) ( C k + O ( ( k 3 / 2 σ P − 1 ) 1 + 12 ∣ k ∣ C k ′ ) ) + O ( μ P k ∑ ω ( a ) ≤ k a ∣ P ∣ r a ∣ ) , \sum_{m=1}^n f(m)\left(\sum_{p\mid\mathcal{P}}1_{p\mid m}-\mu_{\mathcal{P}}\right)^k
=\sigma_{\mathcal{P}}^k\sum_{m=1}^n f(m)\left(C_k+O\left((k^{3/2}\sigma_{\mathcal{P}}^{-1})^{1+12|k|}C'_k\right)\right)+O\left(\mu_{\mathcal{P}}^k\sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}|r_a|\right), m = 1 ∑ n f ( m ) p ∣ P ∑ 1 p ∣ m − μ P k = σ P k m = 1 ∑ n f ( m ) ( C k + O ( ( k 3/2 σ P − 1 ) 1 + 12∣ k ∣ C k ′ ) ) + O μ P k ω ( a ) ≤ k a ∣ P ∑ ∣ r a ∣ ,
where C k C_k C k , C k ′ C'_k C k ′ are given by (3.1).
For f ≡ 1 f\equiv1 f ≡ 1 Proposition 3.1 is [11 Prop. 3] and the proof works the same way for general f ≥ 0 f\ge0 f ≥ 0 . We derive from Proposition 3.1 the following criterion, to be proved below.
Corollary 3.2. For every sufficiently large n n n 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 ) ) I_n := \left(\exp(\exp(\log^{1/3}\log n)),n^{\exp(-\log^{1/3}\log n)}\right) 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 / 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 , P : = ∏ p ∈ I n p \mathcal{P}:=\prod_{p\in I_n}p P := ∏ p ∈ I n p .
Fix k ≥ 1 k\ge1 k ≥ 1 . Suppose that
∑ ω ( a ) ≤ k a ∣ ∏ p < T p / P P ( a divides Y n ) = o ( ( log log n ) k / 2 ) (13) \sum_{\substack{\omega(a)\le k\\a\mid\prod_{p<T}p/\mathcal{P}}}\mathbb{P}(a\text{ divides }Y_n)=o\left((\log\log n)^{k/2}\right) \tag*{(13)} ω ( a ) ≤ k a ∣ ∏ p < T p / P ∑ P ( a divides Y n ) = o ( ( log log n ) k /2 ) (13) as n → ∞ n\to\infty n → ∞ , and that for some multiplicative function g : N → [ 0 , 1 ] g:\mathbb{N}\to[0,1] g : N → [ 0 , 1 ] ,
∑ ω ( a ) ≤ k a ∣ P ∣ P ( a divides Y n ) − g ( a ) ∣ = o ( ( log log n ) − k / 2 ) (14) \sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}\left|\mathbb{P}(a\text{ divides }Y_n)-g(a)\right|=o\left((\log\log n)^{-k/2}\right) \tag*{(14)} ω ( a ) ≤ k a ∣ P ∑ ∣ P ( a divides Y n ) − g ( a ) ∣ = o ( ( log log n ) − k /2 ) (14) as n → ∞ n\to\infty n → ∞ . If ∑ p ≤ x g ( p ) = θ log log x + O ( 1 ) \sum_{p\le x}g(p)=\theta\log\log x+O(1) ∑ p ≤ x g ( p ) = θ log log x + O ( 1 ) for some θ > 0 \theta>0 θ > 0 and ∑ p ≤ x g 2 ( p ) = O ( 1 ) \sum_{p\le x}g^2(p)=O(1) ∑ p ≤ x g 2 ( p ) = O ( 1 ) then
E ( ω ( Y n ) − θ log log n ( θ log log n ) 1 / 2 ) k → C k (15) \mathbb{E}\left(\frac{\omega(Y_n)-\theta\log\log n}{(\theta\log\log n)^{1/2}}\right)^k\to C_k \tag*{(15)} E ( ( θ log log n ) 1/2 ω ( Y n ) − θ log log n ) k → C k (15) as n → ∞ n\to\infty n → ∞ .
Proof. We consider a given n n n and apply Proposition 3.1 with f ( m ) = P ( Y n = m ) f(m)=\mathbb{P}(Y_n=m) f ( m ) = P ( Y n = m ) , h ( m ) = g ( m ) m h(m)=g(m)m h ( m ) = g ( m ) m . Define
ω P ( n ) = ∑ p ∣ P 1 p ∣ n \omega_{\mathcal{P}}(n)=\sum_{p\mid\mathcal{P}}1_{p\mid n} ω P ( n ) = ∑ p ∣ P 1 p ∣ n , μ = ∑ p ∣ P g ( p ) \mu=\sum_{p\mid\mathcal{P}}g(p) μ = ∑ p ∣ P g ( p ) , σ 2 = ∑ p ∣ P g ( p ) ( 1 − g ( p ) ) \sigma^2=\sum_{p\mid\mathcal{P}}g(p)(1-g(p)) σ 2 = ∑ p ∣ P g ( p ) ( 1 − g ( p )) , R a = P ( a divides Y n ) − g ( a ) R_a=\mathbb{P}(a\text{ divides }Y_n)-g(a) R a = P ( a divides Y n ) − g ( 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 − 12 ∣ k ∣ ) ) + O ( μ k σ k ∑ ω ( a ) ≤ k a ∣ P ∣ R a ∣ ) (16) \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-12|k|})\right)
+O\left(\frac{\mu^k}{\sigma^k}\sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}|R_a|\right) \tag*{(16)} m = 1 ∑ n P ( Y n = m ) ( σ ω P ( m ) − μ ) k = m = 1 ∑ n P ( Y n = m ) ( C k + O ( σ − 1 − 12∣ k ∣ ) ) + O σ k μ k ω ( a ) ≤ k a ∣ P ∑ ∣ R a ∣ (16)
holds for every fixed k ≥ 1 k\ge1 k ≥ 1 (implied constants may depend on k k k ). We claim
μ , σ 2 = θ log log n + O ( log 1 / 3 log n ) . (17) \mu,\sigma^2=\theta\log\log n+O(\log^{1/3}\log n). \tag*{(17)} μ , σ 2 = θ log log n + O ( log 1/3 log n ) . (17)
Indeed, by our assumptions on ∑ p ≤ x g ( p ) \sum_{p\le x}g(p) ∑ p ≤ x g ( p ) and ∑ p ≤ x g 2 ( p ) \sum_{p\le x}g^2(p) ∑ p ≤ x g 2 ( p ) ,
0 ≤ μ − σ 2 = ∑ p ∣ P g 2 ( p ) ≤ ∑ p ≤ n g 2 ( p ) = O ( 1 ) 0\le\mu-\sigma^2=\sum_{p\mid\mathcal{P}}g^2(p)\le\sum_{p\le n}g^2(p)=O(1) 0 ≤ μ − σ 2 = p ∣ P ∑ g 2 ( p ) ≤ p ≤ n ∑ g 2 ( p ) = O ( 1 )
and
μ = ∑ p < n exp ( − log 1 / 3 log n ) g ( p ) − ∑ p ≤ exp ( exp ( log 1 / 3 log n ) ) g ( p ) = θ log log ( n exp ( − log 1 / 3 log n ) ) + O ( 1 ) − θ log log ( exp ( exp ( log 1 / 3 log n ) ) ) + O ( 1 ) = θ log log n + O ( log 1 / 3 log n ) . \begin{aligned}
\mu
&=\sum_{p<n^{\exp(-\log^{1/3}\log n)}}g(p)-\sum_{p\le\exp(\exp(\log^{1/3}\log n))}g(p)\\
&=\theta\log\log\left(n^{\exp(-\log^{1/3}\log n)}\right)+O(1)-\theta\log\log\left(\exp(\exp(\log^{1/3}\log n))\right)+O(1)\\
&=\theta\log\log n+O(\log^{1/3}\log n).
\end{aligned} μ = p < n e x p ( − l o g 1/3 l o g n ) ∑ g ( p ) − p ≤ e x p ( e x p ( l o g 1/3 l o g n )) ∑ g ( p ) = θ log log ( n e x p ( − l o g 1/3 l o g n ) ) + O ( 1 ) − θ log log ( exp ( exp ( log 1/3 log n )) ) + O ( 1 ) = θ log log n + O ( log 1/3 log n ) .
We express (16) as
E ( ω P ( Y n ) − μ σ ) k − C k ≪ ( log log n ) − 1 / 2 + ( log log n ) k / 2 ∑ ω ( a ) ≤ k a ∣ P ∣ R a ∣ . (18) \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*{(18)} E ( σ ω P ( Y n ) − μ ) k − C k ≪ ( log log n ) − 1/2 + ( log log n ) k /2 ω ( a ) ≤ k a ∣ P ∑ ∣ R a ∣. (18)
By (14) , the right-hand side of (3.8) goes to 0 0 0 as n → ∞ n\to\infty 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
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_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 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
for T T T and I n I_n I n as in the statement of the corollary. By (17) , the (constant) random variables A 1 A_1 A 1 and A 3 A_3 A 3 tend to 1 1 1 and 0 0 0 , respectively. We have observed E A 2 k → C k \mathbb{E}A_2^k\to C_k E A 2 k → C k by (18) . An integer m m m can have at most log m / log T \log m/\log T log m / log T prime factors of size at least T T T , implying A 5 ≪ ( log log n ) − 1 / 6 A_5\ll(\log\log n)^{-1/6} A 5 ≪ ( 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 (13) 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 ≪ ∑ ω ( a ) ≤ k a ∣ ∏ p < T p / P P ( a divides Y n ) ( log log n ) k / 2 = o ( 1 ) . \mathbb{E}A_4^k=\frac{\sum_{p_1,\ldots,p_k\in[2,T)\setminus I_n}\mathbb{P}([p_1,\ldots,p_k]\text{ divides }Y_n)}{(\theta\log\log n)^{k/2}}\ll\frac{\sum_{\substack{\omega(a)\le k\\a\mid\prod_{p<T}p/\mathcal{P}}}\mathbb{P}(a\text{ divides }Y_n)}{(\log\log n)^{k/2}}=o(1). 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 a ∣ ∏ p < T p / P 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, (15) follows. □
Corollary 3.2 may also be proved by generalizing an argument of Billingsley [4 ] . To deduce Theorem 1.1 from Corollary 3.2 we apply it with Y n = X n Y_n=X_n Y n = X n , g ( m ) = 2 ω ( m ) / m g(m)=2^{\omega(m)}/m g ( m ) = 2 ω ( m ) / m and θ = 2 \theta=2 θ = 2 . This reduces matters to showing that
∑ ω ( a ) ≤ k a ∣ ∏ p < T p / P P ( a divides X n ) = o ( ( log log n ) k / 2 ) (19) \sum_{\substack{\omega(a)\le k\\a\mid\prod_{p<T}p/\mathcal{P}}}\mathbb{P}(a\text{ divides }X_n)=o\left((\log\log n)^{k/2}\right) \tag*{(19)} ω ( a ) ≤ k a ∣ ∏ p < T p / P ∑ P ( a divides X n ) = o ( ( log log n ) k /2 ) (19)
and
∑ ω ( a ) ≤ k a ∣ P ∣ P ( a divides X n ) − 2 ω ( a ) a ∣ = o ( ( log log n ) − k / 2 ) (20) \sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}\left|\mathbb{P}(a\text{ divides }X_n)-\frac{2^{\omega(a)}}{a}\right|=o\left((\log\log n)^{-k/2}\right) \tag*{(20)} ω ( a ) ≤ k a ∣ P ∑ P ( a divides X n ) − a 2 ω ( a ) = o ( ( log log n ) − k /2 ) (20)
hold as n → ∞ n\to\infty n → ∞ , for every k ≥ 1 k\ge1 k ≥ 1 , where T T T and P \mathcal{P} P are defined in Corollary 3.2. We explain why Proposition 1.2 implies (19) –(20) . Applying Proposition 1.2 with S = { a : a divides ∏ p < T p / P } S=\{a:a\text{ divides }\prod_{p<T}p/\mathcal{P}\} S = { a : a divides ∏ p < T p / P } , B = 1 B=1 B = 1 and R = T k R=T^k R = T k we obtain
∑ ω ( a ) ≤ k a ∣ ∏ p < T p / P ( a , n ) = 1 ∣ P ( a divides X n ) − 2 ω ( a ) a ∣ ≪ k log R log n ∑ ω ( a ) ≤ k a ∣ ∏ p < T p / P 1 a + 1 log n . \sum_{\substack{\omega(a)\le k\\a\mid\prod_{p<T}p/\mathcal{P}\\(a,n)=1}}\left|\mathbb{P}(a\text{ divides }X_n)-\frac{2^{\omega(a)}}{a}\right|\ll_k\frac{\log R}{\log n}\sum_{\substack{\omega(a)\le k\\a\mid\prod_{p<T}p/\mathcal{P}}}\frac1a+\frac1{\log n}. ω ( a ) ≤ k a ∣ ∏ p < T p / P ( a , n ) = 1 ∑ P ( a divides X n ) − a 2 ω ( a ) ≪ k log n log R ω ( a ) ≤ k a ∣ ∏ p < T p / P ∑ a 1 + log n 1 .
and the triangle inequality yields
∑ ω ( a ) ≤ k a ∣ ∏ p < T p / P ( a , n ) = 1 P ( a divides X n ) ≪ k ∑ ω ( a ) ≤ k a ∣ ∏ p < T p / P 1 a + 1 log n ≪ k ( 1 + ∑ p ∣ ∏ p < T p / P 1 p ) k ≪ k ( log log n ) k / 3 \sum_{\substack{\omega(a)\le k\\a\mid\prod_{p<T}p/\mathcal{P}\\(a,n)=1}}\mathbb{P}(a\text{ divides }X_n)\ll_k\sum_{\substack{\omega(a)\le k\\a\mid\prod_{p<T}p/\mathcal{P}}}\frac1a+\frac1{\log n}\ll_k\left(1+\sum_{p\mid\prod_{p<T}p/\mathcal{P}}\frac1p\right)^k\ll_k(\log\log n)^{k/3} ω ( a ) ≤ k a ∣ ∏ p < T p / P ( a , n ) = 1 ∑ P ( a divides X n ) ≪ k ω ( a ) ≤ k a ∣ ∏ p < T p / P ∑ a 1 + log n 1 ≪ k 1 + p ∣ ∏ p < T p / P ∑ p 1 k ≪ k ( log log n ) k /3
using Mertens’ theorem [13 Thm. 2.7(d)] . Since
P ( a divides X n ) ≪ n − 1 + o ( 1 ) (21) \mathbb{P}(a\text{ divides }X_n)\ll n^{-1+o(1)} \tag*{(21)} P ( a divides X n ) ≪ n − 1 + o ( 1 ) (21)
holds uniformly for a a a with ( a , n ) > 1 (a,n)>1 ( a , n ) > 1 , (19) is obtained. To obtain (20) we apply Proposition 1.2 with S = { a : a divides P } S=\{a:a\text{ divides }\mathcal{P}\} S = { a : a divides P } , B = 1 B=1 B = 1 and R = ( max I n ) k R=(\max I_n)^k R = ( max I n ) k (for I n I_n I n defined in Corollary 3.2), obtaining
∑ ω ( a ) ≤ k a ∣ P ( a , n ) = 1 ∣ P ( a divides X n ) − 2 ω ( a ) a ∣ ≪ k log R log n ∑ ω ( a ) ≤ k a ∣ P 1 a + 1 log n . (22) \sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}\\(a,n)=1}}\left|\mathbb{P}(a\text{ divides }X_n)-\frac{2^{\omega(a)}}{a}\right|\ll_k\frac{\log R}{\log n}\sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}\frac1a+\frac1{\log n}. \tag*{(22)} ω ( a ) ≤ k a ∣ P ( a , n ) = 1 ∑ P ( a divides X n ) − a 2 ω ( a ) ≪ k log n log R ω ( a ) ≤ k a ∣ P ∑ a 1 + log n 1 . (22)
We conclude since log R / log n ≪ k exp ( − log 1 / 3 log n ) \log R/\log n\ll_k\exp(-\log^{1/3}\log n) log R / log n ≪ k exp ( − log 1/3 log n ) holds by definition of R R R and
∑ ω ( a ) ≤ k a ∣ P 1 a ≤ ( 1 + ∑ p ∣ P 1 p ) k ≪ k ( log log n ) k . \sum_{\substack{\omega(a)\le k\\a\mid\mathcal{P}}}\frac1a\le\left(1+\sum_{p\mid\mathcal{P}}\frac1p\right)^k\ll_k(\log\log n)^k. ω ( a ) ≤ k a ∣ P ∑ a 1 ≤ 1 + p ∣ P ∑ p 1 k ≪ k ( log log n ) k .
holds by Mertens’ theorem [13 Thm. 2.7(d)] . The condition ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 in (22) is harmless by (21) and the fact that ∑ p ∣ ( P , n ) 1 / p \sum_{p\mid(P,n)}1/p ∑ p ∣ ( P , n ) 1/ p goes to 0 faster than any power of log log n \log\log n log log n by the construction of P P P .
Proof of Proposition 1.2
We have 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 ) where
A a ( n ) : = ∑ p < n a ∣ n − p 2 ω ( n − p ) . (23) A_a(n):=\sum_{\substack{p<n\\a\mid n-p}}2^{\omega(n-p)}. \tag*{(23)} A a ( n ) := p < n a ∣ n − p ∑ 2 ω ( n − p ) . (23)
Using (1) we see that Proposition 1.2 will follow if we show
∑ a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) ∣ A a ( n ) − ϕ ( n ) 2 ω ( a ) a ∣ ≪ k , B ϕ ( n ) log R + n ( log log n ) 2 log n ∑ a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) a + n log B n . (24) \sum_{\substack{a\le R,\ a\in S\\\omega(a)\le k\\(a,n)=1}}\mu^2(a)\left|A_a(n)-\phi(n)\frac{2^{\omega(a)}}{a}\right|\ll_{k,B}\frac{\phi(n)\log R+n(\log\log n)^2}{\log n}\sum_{\substack{a\le R,\ a\in S\\\omega(a)\le k\\(a,n)=1}}\frac{\mu^2(a)}{a}+\frac{n}{\log^B n}. \tag*{(24)} a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 ∑ μ 2 ( a ) A a ( n ) − ϕ ( n ) a 2 ω ( a ) ≪ k , B log n ϕ ( n ) log R + n ( log log n ) 2 a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 ∑ a μ 2 ( a ) + log B n n . (24)
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 ) and separate into different ranges:
2 ω ( m ) = ∑ m = d s μ 2 ( d ) = ∑ m = d s d ≤ D μ 2 ( d ) + ∑ m = d s D < s < m / D μ 2 ( d ) + ∑ m = e 2 d s s ≤ D e ≤ V μ ( e ) + ∑ m = e 2 d s s ≤ D e > V μ ( e ) , 2^{\omega(m)}=\sum_{m=ds}\mu^2(d)=\sum_{\substack{m=ds\\d\le D}}\mu^2(d)+\sum_{\substack{m=ds\\D<s<m/D}}\mu^2(d)+\sum_{\substack{m=e^2ds\\s\le D\\e\le V}}\mu(e)+\sum_{\substack{m=e^2ds\\s\le D\\e>V}}\mu(e), 2 ω ( m ) = m = d s ∑ μ 2 ( d ) = m = d s d ≤ D ∑ μ 2 ( d ) + m = d s D < s < m / D ∑ μ 2 ( d ) + m = e 2 d s s ≤ D e ≤ V ∑ μ ( e ) + m = e 2 d s s ≤ D e > V ∑ μ ( e ) ,
with the choices
V = log n and D = n R 2 exp ( ( log log n ) 2 ) . (25) V=\log n\qquad\text{and}\qquad D=\frac{\sqrt n}{R^2\exp((\log\log n)^2)}. \tag*{(25)} V = log n and D = R 2 exp (( log log n ) 2 ) n . (25)
and m m m is equal to n − p n-p n − p . We split A a ( n ) A_a(n) A a ( n ) accordingly:
A a ( n ) = ∑ p < n a ∣ n − p ( ∑ n − p = d s d ≤ D μ 2 ( d ) + ∑ n − p = d s D < s < ( n − p ) / D μ 2 ( d ) + ∑ n − p = e 2 d s s ≤ D e ≤ V μ ( e ) + ∑ n − p = e 2 d s s ≤ D e > V μ ( e ) ) = : S 0 ( a ) + S 1 ( a ) + S 2 ( a ) + S 3 ( a ) . \begin{aligned}
A_a(n)=\sum_{\substack{p<n\\a\mid n-p}}\left(\sum_{\substack{n-p=ds\\d\le D}}\mu^2(d)+\sum_{\substack{n-p=ds\\D<s<(n-p)/D}}\mu^2(d)+\sum_{\substack{n-p=e^2ds\\s\le D\\e\le V}}\mu(e)+\sum_{\substack{n-p=e^2ds\\s\le D\\e>V}}\mu(e)\right) \\
&=:S_0(a)+S_1(a)+S_2(a)+S_3(a).
\end{aligned} A a ( n ) = p < n a ∣ n − p ∑ n − p = d s d ≤ D ∑ μ 2 ( d ) + n − p = d s D < s < ( n − p ) / D ∑ μ 2 ( d ) + n − p = e 2 d s s ≤ D e ≤ V ∑ μ ( e ) + n − p = e 2 d s s ≤ D e > V ∑ μ ( e ) =: S 0 ( a ) + S 1 ( a ) + S 2 ( a ) + S 3 ( a ) .
Writing π ( 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 , we have
S 0 ( a ) = ∑ d ≤ D μ 2 ( d ) π ( n − 1 ; [ d , a ] , n ) , S 1 ( a ) = ∑ D < s < ( n − 2 ) / D ∑ p < n − D s p ≡ n ( [ a , s ] ) μ 2 ( ( n − p ) / s ) , S_0(a)=\sum_{d\le D}\mu^2(d)\pi(n-1;[d,a],n),\qquad S_1(a)=\sum_{D<s<(n-2)/D}\ \sum_{\substack{p<n-Ds\\p\equiv n\ ([a,s])}}\mu^2((n-p)/s), S 0 ( a ) = d ≤ D ∑ μ 2 ( d ) π ( n − 1 ; [ d , a ] , n ) , S 1 ( a ) = D < s < ( n − 2 ) / D ∑ p < n − D s p ≡ n ([ a , s ]) ∑ μ 2 (( n − p ) / s ) ,
S 2 ( a ) = ∑ s ≤ D e ≤ V μ ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) , S 3 ( a ) = ∑ s ≤ D e > V μ ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) . S_2(a)=\sum_{\substack{s\le D\\e\le V}}\mu(e)\pi(n-1;[se^2,a],n),\qquad S_3(a)=\sum_{\substack{s\le D\\e>V}}\mu(e)\pi(n-1;[se^2,a],n). S 2 ( a ) = s ≤ D e ≤ V ∑ μ ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) , S 3 ( a ) = s ≤ D e > V ∑ μ ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) .
Let
Li ( m ) = ∫ 2 m d t log t \operatorname{Li}(m)=\int_2^m\frac{dt}{\log t} Li ( m ) = ∫ 2 m log t d t
be the logarithmic integral. Write E ( m ; q , a ) = π ( m ; q , a ) − Li ( m ) 1 ( q , a ) = 1 ϕ ( q ) E(m;q,a)=\pi(m;q,a)-\dfrac{\operatorname{Li}(m)\mathbf{1}_{(q,a)=1}}{\phi(q)} E ( m ; q , a ) = π ( m ; q , a ) − ϕ ( q ) Li ( m ) 1 ( q , a ) = 1 and accordingly S i ( a ) = M i ( a ) + E i ( a ) S_i(a)=M_i(a)+E_i(a) S i ( a ) = M i ( a ) + E i ( a ) ( i = 0 , 2 ) (i=0,2) ( i = 0 , 2 ) for
M 0 ( a ) = Li ( n − 1 ) ∑ d ≤ D ( d , n ) = 1 μ 2 ( d ) ϕ ( [ d , a ] ) , E 0 ( a ) = ∑ d ≤ D μ 2 ( d ) E ( n − 1 ; [ d , a ] , n ) , M_0(a)=\operatorname{Li}(n-1)\sum_{\substack{d\le D\\(d,n)=1}}\frac{\mu^2(d)}{\phi([d,a])},\qquad E_0(a)=\sum_{d\le D}\mu^2(d)E(n-1;[d,a],n), M 0 ( a ) = Li ( n − 1 ) d ≤ D ( d , n ) = 1 ∑ ϕ ([ d , a ]) μ 2 ( d ) , E 0 ( a ) = d ≤ D ∑ μ 2 ( d ) E ( n − 1 ; [ d , a ] , n ) ,
M 2 ( a ) = Li ( n − 1 ) ∑ s ≤ D , e ≤ V ( s e , n ) = 1 μ ( e ) ϕ ( [ s e 2 , a ] ) , E 2 ( a ) = ∑ s ≤ D e ≤ V μ ( e ) E ( n − 1 ; [ s e 2 , a ] , n ) . (26) M_2(a)=\operatorname{Li}(n-1)\sum_{\substack{s\le D,\ e\le V\\(se,n)=1}}\frac{\mu(e)}{\phi([se^2,a])},\qquad E_2(a)=\sum_{\substack{s\le D\\e\le V}}\mu(e)E(n-1;[se^2,a],n). \tag*{(26)} M 2 ( a ) = Li ( n − 1 ) s ≤ D , e ≤ V ( se , n ) = 1 ∑ ϕ ([ s e 2 , a ]) μ ( e ) , E 2 ( a ) = s ≤ D e ≤ V ∑ μ ( e ) E ( n − 1 ; [ s e 2 , a ] , n ) . (26)
We first observe some basic properties of ϕ \phi ϕ . We have
ϕ ( n 1 ) ϕ ( n 2 ) = ϕ ( ( n 1 , n 2 ) ) ϕ ( [ n 1 , n 2 ] ) . (27) \phi(n_1)\phi(n_2)=\phi((n_1,n_2))\phi([n_1,n_2]). \tag*{(27)} ϕ ( n 1 ) ϕ ( n 2 ) = ϕ (( n 1 , n 2 )) ϕ ([ n 1 , n 2 ]) . (27)
and
φ ( n 1 ) φ ( n 2 ) ≤ φ ( n 1 n 2 ) (28) \varphi(n_1)\varphi(n_2) \le\varphi(n_1n_2) \tag*{(28)} φ ( n 1 ) φ ( n 2 ) ≤ φ ( n 1 n 2 ) (28)
for every n 1 , n 2 ≥ 1 n_1,n_2 \ge1 n 1 , n 2 ≥ 1 . We have
∑ m ≤ A 1 φ ( m ) = C log A + O ( 1 ) (29) \sum_{m\le A} \frac{1}{\varphi(m)} = C\log A + O(1) \tag*{(29)} m ≤ A ∑ φ ( m ) 1 = C log A + O ( 1 ) (29)
for A ≥ 1 A \ge1 A ≥ 1 [13 p. 42] . The estimate
∑ n > A 1 φ ( n 2 ) ≪ 1 A (30) \sum_{n>A} \frac{1}{\varphi(n^2)} \ll\frac{1}{A} \tag*{(30)} n > A ∑ φ ( n 2 ) 1 ≪ A 1 (30)
holds for each A > 0 A>0 A > 0 , since it is equivalent to ∑ A ≤ n < 2 A n 2 φ ( n 2 ) ≪ A \sum_{A\le n<2A} \frac{n^2}{\varphi(n^2)} \ll A ∑ A ≤ n < 2 A φ ( n 2 ) n 2 ≪ A which follows from [13 Thm. 2.14] . Moreover, n ≥ φ ( n ) ≫ n / log log n n\ge\varphi(n)\gg n/\log\log n n ≥ φ ( n ) ≫ n / log log n [13 Thm. 2.9] . The following lemmas estimate the contributions of S i S_i S i to the left-hand side of (24) and will be proved below.
Lemma 4.1. Suppose 1 ≤ R ≤ n 1 / 100 1\le R\le n^{1/100} 1 ≤ R ≤ n 1/100 . Fix k ≥ 1 k\ge1 k ≥ 1 . Then for squarefree 1 ≤ a ≤ R 1\le a\le R 1 ≤ a ≤ R with ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k and ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 ,
∣ S 1 ( a ) ∣ + ∣ S 3 ( a ) ∣ ≪ k φ ( n ) a log n ( log R + ( log log n ) 2 ) . |S_1(a)|+|S_3(a)|\ll_k \frac{\varphi(n)}{a\log n}\left(\log R+(\log\log n)^2\right). ∣ S 1 ( a ) ∣ + ∣ S 3 ( a ) ∣ ≪ k a log n φ ( n ) ( log R + ( log log n ) 2 ) .
Lemma 4.2. Suppose 1 ≤ R ≤ n 1 / 100 1\le R\le n^{1/100} 1 ≤ R ≤ n 1/100 . Then for every B > 0 B>0 B > 0 ,
∑ a ≤ R ( ∣ E 0 ( a ) ∣ + ∣ E 2 ( a ) ∣ ) ≪ B n log B n . \sum_{a\le R} \left(|E_0(a)|+|E_2(a)|\right)\ll_B \frac{n}{\log^B n}. a ≤ R ∑ ( ∣ E 0 ( a ) ∣ + ∣ E 2 ( a ) ∣ ) ≪ B log B n n .
Lemma 4.3. For squarefree 1 ≤ a ≤ n 1\le a\le n 1 ≤ a ≤ n with ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k ,
M 2 ( a ) − M 0 ( a ) ≪ k n a log n . M_2(a)-M_0(a)\ll_k \frac{n}{a\log n}. M 2 ( a ) − M 0 ( a ) ≪ k a log n n .
Lemma 4.4. Fix k ≥ 1 k\ge1 k ≥ 1 . Uniformly for D ≥ n 1 / 3 D\ge n^{1/3} D ≥ n 1/3 and squarefree 1 ≤ a ≤ n 1 / 100 1\le a\le n^{1/100} 1 ≤ a ≤ n 1/100 with ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 and ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k ,
∑ d < D ( d , n ) = 1 μ 2 ( d ) φ ( [ d , a ] ) = 2 ω ( a ) a ( φ ( n ) n log D + O k ( ( log log n ) 2 ) ) − φ ( n ) n D a φ ( a ) . (31) \sum_{\substack{d<D\\(d,n)=1}} \frac{\mu^2(d)}{\varphi([d,a])}
=
\frac{2^{\omega(a)}}{a}
\left(\frac{\varphi(n)}{n}\log D+O_k((\log\log n)^2)\right)
-\frac{\varphi(n)}{n}\frac{D_a}{\varphi(a)}. \tag*{(31)} d < D ( d , n ) = 1 ∑ φ ([ d , a ]) μ 2 ( d ) = a 2 ω ( a ) ( n φ ( n ) log D + O k (( log log n ) 2 ) ) − n φ ( n ) φ ( a ) D a . (31)
Note that M 0 ( a ) M_0(a) M 0 ( a ) coincides with Li ( n − 1 ) \operatorname{Li}(n-1) Li ( n − 1 ) times the left-hand side of (31) . Applying the last 4 lemmas and recalling our choice of D D D in (25) we obtain
∑ a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) ∣ A a ( n ) − φ ( n ) 2 ω ( a ) a + Li ( n − 1 ) 2 D a φ ( n ) n φ ( a ) ∣ ≪ k , B φ ( n ) log R + n ( log log n ) 2 log n ∑ a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 μ 2 ( a ) a + n log B n . (32) \sum_{\substack{a\le R,\ a\in S\\ \omega(a)\le k\\ (a,n)=1}}
\mu^2(a)\left|A_a(n)-\varphi(n)\frac{2^{\omega(a)}}{a}+\operatorname{Li}(n-1)\frac{2D_a\varphi(n)}{n\varphi(a)}\right|
\ll_{k,B}
\frac{\varphi(n)\log R+n(\log\log n)^2}{\log n}
\sum_{\substack{a\le R,\ a\in S\\ \omega(a)\le k\\ (a,n)=1}}
\frac{\mu^2(a)}{a}+\frac{n}{\log^B n}. \tag*{(32)} a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 ∑ μ 2 ( a ) A a ( n ) − φ ( n ) a 2 ω ( a ) + Li ( n − 1 ) n φ ( a ) 2 D a φ ( n ) ≪ k , B log n φ ( n ) log R + n ( log log n ) 2 a ≤ R , a ∈ S ω ( a ) ≤ k ( a , n ) = 1 ∑ a μ 2 ( a ) + log B n n . (32)
for 1 ≤ R ≤ n 1 / 100 1\le R\le n^{1/100} 1 ≤ R ≤ n 1/100 . The contribution of the lower order term Li ( n − 1 ) 2 D a φ ( n ) / ( n φ ( a ) ) \operatorname{Li}(n-1)2D_a\varphi(n)/(n\varphi(a)) Li ( n − 1 ) 2 D a φ ( n ) / ( n φ ( a )) can be absorbed in the right-hand side of (32) using (6) , giving (24) . This will complete the proof of Proposition 1.2.
Proof of Lemma 4.1
Let 1 ≤ a ≤ R 1\le a\le R 1 ≤ a ≤ R be a squarefree integer with ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 and ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k . In estimating S 1 ( a ) S_1(a) S 1 ( a ) we consider separately ( s , n ) = 1 (s,n)=1 ( s , n ) = 1 and ( s , n ) > 1 (s,n)>1 ( s , n ) > 1 :
∣ S 1 ( a ) ∣ ≤ ∑ D < s < n / D π ( n − 1 ; [ a , s ] , n ) = ∑ D < s < n / D ( s , n ) = 1 π ( n − 1 ; [ a , s ] , n ) + ∑ D < s < n / D ( s , n ) > 1 π ( n − 1 ; [ a , s ] , n ) = : T 1 + T 2 . |S_1(a)|\le\sum_{D<s<n/D}\pi(n-1;[a,s],n)
=\sum_{\substack{D<s<n/D\\(s,n)=1}}\pi(n-1;[a,s],n)
+\sum_{\substack{D<s<n/D\\(s,n)>1}}\pi(n-1;[a,s],n)
=:T_1+T_2. ∣ S 1 ( a ) ∣ ≤ D < s < n / D ∑ π ( n − 1 ; [ a , s ] , n ) = D < s < n / D ( s , n ) = 1 ∑ π ( n − 1 ; [ a , s ] , n ) + D < s < n / D ( s , n ) > 1 ∑ π ( n − 1 ; [ a , s ] , n ) =: T 1 + T 2 .
To bound T 2 T_2 T 2 , note π ( n − 1 ; [ a , s ] , n ) ≤ ∑ p ∣ n 1 ≪ log n \pi(n-1;[a,s],n)\le\sum_{p\mid n}1\ll\log n π ( n − 1 ; [ a , s ] , n ) ≤ ∑ p ∣ n 1 ≪ log n holds for ( s , n ) > 1 (s,n)>1 ( s , n ) > 1 , and so
T 2 ≪ n log n D T_2\ll\frac{n\log n}{D} T 2 ≪ D n log n
which is ≪ n / ( a log n ) ≪ ϕ ( n ) ( log log n ) 2 / ( a log n ) \ll n/(a\log n)\ll\phi(n)(\log\log n)^2/(a\log n) ≪ n / ( a log n ) ≪ ϕ ( n ) ( log log n ) 2 / ( a log n ) by our choice of D D D , and the assumption a ≤ R a\le R a ≤ R . To bound T 1 T_1 T 1 we use the Brun–Titchmarsh Theorem:
T 1 ≪ n log n ∑ D < s < n / D ( s , n ) = 1 1 ϕ ( [ a , s ] ) . (33) T_1\ll\frac{n}{\log n}\sum_{\substack{D<s<n/D\\(s,n)=1}}\frac{1}{\phi([a,s])}. \tag*{(33)} T 1 ≪ log n n D < s < n / D ( s , n ) = 1 ∑ ϕ ([ a , s ]) 1 . (33)
The theorem saves log n \log n log n since [ a , s ] ≤ R n / D ≤ n 3 / 4 [a,s]\le Rn/D\le n^{3/4} [ a , s ] ≤ R n / D ≤ n 3/4 by our choice of D D D , and the assumption a ≤ R a\le R a ≤ R . To estimate the sum in (33) we let g = ( a , s ) g=(a,s) g = ( a , s ) and change the order of summation:
∑ D < s < n / D ( s , n ) = 1 1 ϕ ( [ a , s ] ) ≤ 1 ϕ ( a ) ∑ g ∣ a ∑ D < s < n / D ( s , n ) = 1 ( a , s ) = g ϕ ( g ) ϕ ( s ) ≤ 1 ϕ ( a ) ∑ g ∣ a ∑ D / g < s ′ < n / ( D g ) ( s ′ , n ) = 1 1 ϕ ( s ′ ) . \sum_{\substack{D<s<n/D\\(s,n)=1}}\frac{1}{\phi([a,s])}
\le\frac{1}{\phi(a)}\sum_{g\mid a}\sum_{\substack{D<s<n/D\\(s,n)=1\\(a,s)=g}}\frac{\phi(g)}{\phi(s)}
\le\frac{1}{\phi(a)}\sum_{g\mid a}\sum_{\substack{D/g<s'<n/(Dg)\\(s',n)=1}}\frac{1}{\phi(s')}. D < s < n / D ( s , n ) = 1 ∑ ϕ ([ a , s ]) 1 ≤ ϕ ( a ) 1 g ∣ a ∑ D < s < n / D ( s , n ) = 1 ( a , s ) = g ∑ ϕ ( s ) ϕ ( g ) ≤ ϕ ( a ) 1 g ∣ a ∑ D / g < s ′ < n / ( D g ) ( s ′ , n ) = 1 ∑ ϕ ( s ′ ) 1 .
where we used (4.5) in the first inequality and (4.6) in the second one. By [13 p. 43] ,
∑ B < m ≤ A ( m , n ) = 1 1 ϕ ( m ) ≪ ϕ ( n ) n log ( A / B ) + 2 ω ( n ) log B B (34) \sum_{\substack{B<m\le A\\(m,n)=1}}\frac{1}{\phi(m)}
\ll\frac{\phi(n)}{n}\log(A/B)+2^{\omega(n)}\frac{\log B}{B} \tag*{(34)} B < m ≤ A ( m , n ) = 1 ∑ ϕ ( m ) 1 ≪ n ϕ ( n ) log ( A / B ) + 2 ω ( n ) B log B (34)
holds for A ≥ B ≥ 2 A\ge B\ge2 A ≥ B ≥ 2 . Applying (34) with ( A , B ) = ( n / ( D g ) , D / g ) (A,B)=(n/(Dg),D/g) ( A , B ) = ( n / ( D g ) , D / g ) we find that
T 1 ≪ n log n 1 ϕ ( a ) ϕ ( n ) n log ( 2 + n D 2 ) ∑ g ∣ a 1 ≪ k ϕ ( n ) a log n log ( 2 + n D 2 ) T_1\ll\frac{n}{\log n}\frac{1}{\phi(a)}\frac{\phi(n)}{n}\log\left(2+\frac{n}{D^2}\right)\sum_{g\mid a}1\ll_k\frac{\phi(n)}{a\log n}\log\left(2+\frac{n}{D^2}\right) T 1 ≪ log n n ϕ ( a ) 1 n ϕ ( n ) log ( 2 + D 2 n ) g ∣ a ∑ 1 ≪ k a log n ϕ ( n ) log ( 2 + D 2 n )
since a a a is squarefree and ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k , which is acceptable by our choice of D D D . It remains to estimate S 3 ( a ) S_3(a) S 3 ( a ) . We consider separately ( s e , n ) = 1 (se,n)=1 ( se , n ) = 1 and ( s e , n ) > 1 (se,n)>1 ( se , n ) > 1 :
∣ S 3 ( a ) ∣ ≤ ∑ s ≤ D e ≤ V ( s e , n ) = 1 μ 2 ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) + ∑ s ≤ D e ≤ V ( s e , n ) > 1 μ 2 ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) = : T 3 + T 4 . |S_3(a)|\le\sum_{\substack{s\le D\\e\le V\\(se,n)=1}}\mu^2(e)\pi(n-1;[se^2,a],n)+\sum_{\substack{s\le D\\e\le V\\(se,n)>1}}\mu^2(e)\pi(n-1;[se^2,a],n)=:T_3+T_4. ∣ S 3 ( a ) ∣ ≤ s ≤ D e ≤ V ( se , n ) = 1 ∑ μ 2 ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) + s ≤ D e ≤ V ( se , n ) > 1 ∑ μ 2 ( e ) π ( n − 1 ; [ s e 2 , a ] , n ) =: T 3 + T 4 .
To bound T 4 T_4 T 4 we observe π ( n − 1 ; [ s e 2 , a ] , n ) ≤ ∑ p ∣ n 1 ≪ log n \pi(n-1;[se^2,a],n)\le\sum_{p\mid n}1\ll\log n π ( n − 1 ; [ s e 2 , a ] , n ) ≤ ∑ p ∣ n 1 ≪ log n holds when ( s e , n ) > 1 (se,n)>1 ( se , n ) > 1 , which leads to
T 4 ≪ log n ∑ s ≤ D ∑ e ≤ n / s 1 ≪ log n n D T_4\ll\log n\sum_{s\le D}\sum_{e\le\sqrt{n/s}}\!1\ll\log n\sqrt{nD} T 4 ≪ log n s ≤ D ∑ e ≤ n / s ∑ 1 ≪ log n n D
which is ≪ n / ( a log n ) ≪ ϕ ( n ) ( log log n ) 2 / ( a log n ) \ll n/(a\log n)\ll\phi(n)(\log\log n)^2/(a\log n) ≪ n / ( a log n ) ≪ ϕ ( n ) ( log log n ) 2 / ( a log n ) due to our choice of D D D , and since a ≤ R a\le R a ≤ R . To bound T 3 T_3 T 3 we use the Brun–Titchmarsh Theorem when e ≤ V log n e\le V\log n e ≤ V log n and otherwise use π ( n − 1 ; m , n ) ≤ n / m ≤ n / ϕ ( m ) \pi(n-1;m,n)\le n/m\le n/\phi(m) π ( n − 1 ; m , n ) ≤ n / m ≤ n / ϕ ( m ) :
T 3 ≪ n log n ∑ s ≤ D V log n ≥ e > V μ 2 ( e ) ϕ ( [ s e 2 , a ] ) + n ∑ s ≤ D e > V log n μ 2 ( e ) ϕ ( [ s e 2 , a ] ) . T_3\ll\frac{n}{\log n}\sum_{\substack{s\le D\\V\log n\ge e>V}}\frac{\mu^2(e)}{\phi([se^2,a])}+n\sum_{\substack{s\le D\\e>V\log n}}\frac{\mu^2(e)}{\phi([se^2,a])}. T 3 ≪ log n n s ≤ D V l o g n ≥ e > V ∑ ϕ ([ s e 2 , a ]) μ 2 ( e ) + n s ≤ D e > V l o g n ∑ ϕ ([ s e 2 , a ]) μ 2 ( e ) .
The theorem saves log n \log n log n when e ≤ V log n e\le V\log n e ≤ V log n because [ s e 2 , a ] ≤ D ( V log n ) 2 R ≤ n 1 / 2 [se^2,a]\le D(V\log n)^2R\le n^{1/2} [ s e 2 , a ] ≤ D ( V log n ) 2 R ≤ n 1/2 by our choices of V V V and D D D , and since a ≤ R a\le R a ≤ R . Let g = ( a , s e 2 ) g=(a,se^2) g = ( a , s e 2 ) and observe there are coprime g 1 g_1 g 1 and g 2 g_2 g 2 such that g = g 1 g 2 g=g_1g_2 g = g 1 g 2 , g 1 ∣ s g_1\mid s g 1 ∣ s and g 2 ∣ e g_2\mid e g 2 ∣ e . It follows that
∑ s ≤ D e > V ′ 1 ϕ ( [ s e 2 , a ] ) ≤ ∑ g 1 g 2 ∣ a g 1 ∣ s ≤ D ϕ ( g 1 ) ϕ ( s ) ∑ g 2 ∣ e > V ′ ϕ ( g 2 ) ϕ ( e 2 ) ϕ ( a ) ≤ log n V ′ ∑ g 1 g 2 ∣ a 1 ϕ ( a ) ≪ k log n V ′ 1 a (35) \sum_{\substack{s\le D\\e>V'}}\frac{1}{\phi([se^2,a])}
\le\sum_{\substack{g_1g_2\mid a\\g_1\mid s\le D}}\frac{\phi(g_1)}{\phi(s)}
\sum_{g_2\mid e>V'}\frac{\phi(g_2)}{\phi(e^2)\phi(a)}
\le\frac{\log n}{V'}\sum_{g_1g_2\mid a}\frac{1}{\phi(a)}
\ll_k\frac{\log n}{V'}\frac{1}{a} \tag*{(35)} s ≤ D e > V ′ ∑ ϕ ([ s e 2 , a ]) 1 ≤ g 1 g 2 ∣ a g 1 ∣ s ≤ D ∑ ϕ ( s ) ϕ ( g 1 ) g 2 ∣ e > V ′ ∑ ϕ ( e 2 ) ϕ ( a ) ϕ ( g 2 ) ≤ V ′ log n g 1 g 2 ∣ a ∑ ϕ ( a ) 1 ≪ k V ′ log n a 1 (35)
for every V ′ ≥ 1 V'\ge1 V ′ ≥ 1 . Here we used (4.5)–(4.8). Applying (35) with V ′ = V , V log n V'=V,V\log n V ′ = V , V log n we find T 3 ≪ n / ( a log n ) ≪ ϕ ( n ) ( log log n ) 2 / ( a log n ) T_3\ll n/(a\log n)\ll\phi(n)(\log\log n)^2/(a\log n) T 3 ≪ n / ( a log n ) ≪ ϕ ( n ) ( log log n ) 2 / ( a log n ) since V = log n V=\log n V = log n .
Proof of Lemma 4.2
By Cauchy–Schwarz and the trivial bound E ( n − 1 ; b , n ) ≪ n / b E(n-1;b,n)\ll n/b E ( n − 1 ; b , n ) ≪ n / b , we have
∑ a ≤ R ∣ E 0 ( a ) ∣ ≤ ∑ b ≤ D R τ ( b ) 2 ∣ E ( n − 1 ; b , n ) ∣ ≤ ∑ b ≤ D R τ ( b ) 4 ∣ E ( n − 1 ; b , n ) ∣ ∑ b ≤ D R ∣ E ( n − 1 ; b , n ) ∣ ≪ n ( log n ) O ( 1 ) ∑ b ≤ D R ∣ E ( n − 1 ; b , n ) ∣ \begin{aligned}
\sum_{a\le R}|E_0(a)|\le\sum_{b\le DR}\tau(b)^2|E(n-1;b,n)| \\
&\le\sqrt{\sum_{b\le DR}\tau(b)^4|E(n-1;b,n)|}\sqrt{\sum_{b\le DR}|E(n-1;b,n)|}
\ll\sqrt{n}(\log n)^{O(1)}\sqrt{\sum_{b\le DR}|E(n-1;b,n)|}
\end{aligned} a ≤ R ∑ ∣ E 0 ( a ) ∣ ≤ b ≤ D R ∑ τ ( b ) 2 ∣ E ( n − 1 ; b , n ) ∣ ≤ b ≤ D R ∑ τ ( b ) 4 ∣ E ( n − 1 ; b , n ) ∣ b ≤ D R ∑ ∣ E ( n − 1 ; b , n ) ∣ ≪ n ( log n ) O ( 1 ) b ≤ D R ∑ ∣ E ( n − 1 ; b , n ) ∣
where b b b stands for [ d , a ] [d,a] [ d , a ] and τ \tau τ is the divisor function. Since D R ≪ B n ( log n ) − B DR \ll_B \sqrt{n}(\log n)^{-B} D R ≪ B n ( log n ) − B for every B > 0 B>0 B > 0 , the Bombieri–Vinogradov Theorem [9 Lemma] implies that
∑ b ≤ D R ∣ E ( n − 1 ; b , n ) ∣ ≪ B n ( log n ) − B \sum_{b\le DR} \lvert E(n-1;b,n)\rvert\ll_B n(\log n)^{-B} b ≤ D R ∑ ∣ E ( n − 1 ; b , n )∣ ≪ B n ( log n ) − B
and so
∑ a ≤ R ∣ E 0 ( a ) ∣ ≪ B n ( log n ) − B \sum_{a\le R} \lvert E_0(a)\rvert\ll_B n(\log n)^{-B} a ≤ R ∑ ∣ E 0 ( a )∣ ≪ B n ( log n ) − B
for every B > 0 B>0 B > 0 . Similarly, letting b : = [ s e 2 , a ] b:=[se^2,a] b := [ s e 2 , a ] ,
∑ a ≤ R ∣ E 2 ( a ) ∣ ≤ ∑ b ≤ D V 2 R τ ( b ) 3 ∣ E ( n − 1 ; b , n ) ∣ ≪ B n ( log n ) − B . \sum_{a\le R} \lvert E_2(a)\rvert\le\sum_{b\le DV^2R}\tau(b)^3\lvert E(n-1;b,n)\rvert\ll_B n(\log n)^{-B}. a ≤ R ∑ ∣ E 2 ( a )∣ ≤ b ≤ D V 2 R ∑ τ ( b ) 3 ∣ E ( n − 1 ; b , n )∣ ≪ B n ( log n ) − B .
Proof of Lemma 4.3
4.3. Proof of Lemma 4.3. We complete the e e e -range in M 2 ( a ) M_2(a) M 2 ( a ) , obtaining
M 2 ( a ) = Li ( n − 1 ) ∑ e ≥ 1 s e 2 ≤ D ( s e , n ) = 1 μ ( e ) ϕ ( [ s e 2 , a ] ) + M 2 , 1 ( n ) M_2(a)=\operatorname{Li}(n-1)\sum_{\substack{e\ge1\\ se^2\le D\\ (se,n)=1}}\frac{\mu(e)}{\phi([se^2,a])}+M_{2,1}(n) M 2 ( a ) = Li ( n − 1 ) e ≥ 1 s e 2 ≤ D ( se , n ) = 1 ∑ ϕ ([ s e 2 , a ]) μ ( e ) + M 2 , 1 ( n )
where, by (27) –(28) ,
M 2 , 1 ( n ) ≪ n log n ∑ e ≤ D e > V μ 2 ( e ) ϕ ( [ s e 2 , a ] ) ≤ n ϕ ( a ) log n ∑ e ≤ D e > V μ 2 ( e ) ϕ ( ( s e 2 , a ) ) ϕ ( s ) ϕ ( e 2 ) . M_{2,1}(n)\ll\frac{n}{\log n}\sum_{\substack{e\le D\\ e>V}}\frac{\mu^2(e)}{\phi([se^2,a])}\le\frac{n}{\phi(a)\log n}\sum_{\substack{e\le D\\ e>V}}\frac{\mu^2(e)\phi((se^2,a))}{\phi(s)\phi(e^2)}. M 2 , 1 ( n ) ≪ log n n e ≤ D e > V ∑ ϕ ([ s e 2 , a ]) μ 2 ( e ) ≤ ϕ ( a ) log n n e ≤ D e > V ∑ ϕ ( s ) ϕ ( e 2 ) μ 2 ( e ) ϕ (( s e 2 , a )) .
Since a a a is squarefree, if we let g = ( s e 2 , a ) g=(se^2,a) g = ( s e 2 , a ) , then there are coprime g 1 , g 2 g_1,g_2 g 1 , g 2 (not necessarily unique) such that g = g 1 g 2 g=g_1g_2 g = g 1 g 2 , g 1 ∣ e g_1\mid e g 1 ∣ e and g 2 ∣ s g_2\mid s g 2 ∣ s , and so (using (29) –(30) )
M 2 , 1 ( n ) ≪ n ϕ ( a ) log n ∑ g 1 g 2 ∣ a ∑ g 1 ∣ e e > V μ 2 ( e ) ϕ ( g 1 ) ϕ ( e 2 ) ∑ g 2 ∣ s s ≤ D ϕ ( g 2 ) ϕ ( s ) ≪ k n a V = n a log n M_{2,1}(n)\ll\frac{n}{\phi(a)\log n}\sum_{g_1g_2\mid a}\sum_{\substack{g_1\mid e\\ e>V}}\frac{\mu^2(e)\phi(g_1)}{\phi(e^2)}\sum_{\substack{g_2\mid s\\ s\le D}}\frac{\phi(g_2)}{\phi(s)}\ll_k\frac{n}{aV}=\frac{n}{a\log n} M 2 , 1 ( n ) ≪ ϕ ( a ) log n n g 1 g 2 ∣ a ∑ g 1 ∣ e e > V ∑ ϕ ( e 2 ) μ 2 ( e ) ϕ ( g 1 ) g 2 ∣ s s ≤ D ∑ ϕ ( s ) ϕ ( g 2 ) ≪ k aV n = a log n n
when ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k . Now write
Li ( n − 1 ) ∑ e ≥ 1 s e 2 ≤ D ( s e , n ) = 1 μ ( e ) ϕ ( [ s e 2 , a ] ) = M 0 ( a ) + M 2 , 2 ( a ) \operatorname{Li}(n-1)\sum_{\substack{e\ge1\\ se^2\le D\\ (se,n)=1}}\frac{\mu(e)}{\phi([se^2,a])}=M_0(a)+M_{2,2}(a) Li ( n − 1 ) e ≥ 1 s e 2 ≤ D ( se , n ) = 1 ∑ ϕ ([ s e 2 , a ]) μ ( e ) = M 0 ( a ) + M 2 , 2 ( a )
where
M 2 , 2 ( a ) = Li ( n − 1 ) ∑ D < s e 2 ≤ D e 2 ( s e , n ) = 1 μ ( e ) ϕ ( [ s e 2 , a ] ) ≪ n log n ∑ D < s e 2 ≤ D e 2 1 ϕ ( [ s e 2 , a ] ) . M_{2,2}(a)=\operatorname{Li}(n-1)\sum_{\substack{D<se^2\le De^2\\ (se,n)=1}}\frac{\mu(e)}{\phi([se^2,a])}\ll\frac{n}{\log n}\sum_{D<se^2\le De^2}\frac{1}{\phi([se^2,a])}. M 2 , 2 ( a ) = Li ( n − 1 ) D < s e 2 ≤ D e 2 ( se , n ) = 1 ∑ ϕ ([ s e 2 , a ]) μ ( e ) ≪ log n n D < s e 2 ≤ D e 2 ∑ ϕ ([ s e 2 , a ]) 1 .
Using the same g g g , g 1 g_1 g 1 and g 2 g_2 g 2 as before,
∑ D < s e 2 ≤ D e 2 μ 2 ( e ) ϕ ( [ s e 2 , a ] ) ≤ 1 ϕ ( a ) ∑ e ≥ 1 1 ϕ ( e 2 ) ∑ D / e 2 < s ≤ D ϕ ( g ) ϕ ( s ) ≤ 1 ϕ ( a ) ∑ g 1 g 2 ∣ a ∑ g 1 ∣ e μ 2 ( e ) ϕ ( g 1 ) ϕ ( e 2 ) ∑ D / e 2 ≤ s ≤ D g 2 ∣ s ϕ ( g 2 ) ϕ ( s ) ≪ 1 a \sum_{D<se^2\le De^2}\frac{\mu^2(e)}{\phi([se^2,a])}\le\frac{1}{\phi(a)}\sum_{e\ge1}\frac{1}{\phi(e^2)}\sum_{D/e^2<s\le D}\frac{\phi(g)}{\phi(s)}\le\frac{1}{\phi(a)}\sum_{g_1g_2\mid a}\sum_{g_1\mid e}\frac{\mu^2(e)\phi(g_1)}{\phi(e^2)}\sum_{\substack{D/e^2\le s\le D\\ g_2\mid s}}\frac{\phi(g_2)}{\phi(s)}\ll\frac{1}{a} D < s e 2 ≤ D e 2 ∑ ϕ ([ s e 2 , a ]) μ 2 ( e ) ≤ ϕ ( a ) 1 e ≥ 1 ∑ ϕ ( e 2 ) 1 D / e 2 < s ≤ D ∑ ϕ ( s ) ϕ ( g ) ≤ ϕ ( a ) 1 g 1 g 2 ∣ a ∑ g 1 ∣ e ∑ ϕ ( e 2 ) μ 2 ( e ) ϕ ( g 1 ) D / e 2 ≤ s ≤ D g 2 ∣ s ∑ ϕ ( s ) ϕ ( g 2 ) ≪ a 1
where we used (27) –(30) .
Proof of Lemma 4.4
4.4. Proof of Lemma 4.4. For a a a coprime to n n n let
f n , a ( d ) : = μ 2 ( d ) ϕ ( a ) ϕ ( [ d , a ] ) 1 ( d , n ) = 1 f_{n,a}(d):=\frac{\mu^2(d)\phi(a)}{\phi([d,a])}1_{(d,n)=1} f n , a ( d ) := ϕ ([ d , a ]) μ 2 ( d ) ϕ ( a ) 1 ( d , n ) = 1
which is multiplicative in d d d . Elliott and Halberstam established [9 p. 202]
∑ d ≤ D f n , 1 ( d ) = ϕ ( n ) n log D + O ( ( log log n ) 2 ) (36) \sum_{d\le D}f_{n,1}(d)=\frac{\phi(n)}{n}\log D+O((\log\log n)^2) \tag*{(36)} d ≤ D ∑ f n , 1 ( d ) = n ϕ ( n ) log D + O (( log log n ) 2 ) (36)
for n ≤ D 5 n \le D^5 n ≤ D 5 . We have, for a a a coprime to n n n , f n , a = f n , 1 ∗ g a f_{n,a}=f_{n,1}*g_a f n , a = f n , 1 ∗ g a where g a ( d ) = g ( d ) 1 d ∣ a ∞ g_a(d)=g(d)1_{d\mid a^\infty} g a ( d ) = g ( d ) 1 d ∣ a ∞ and g g g is defined in (5) . Hence, by (36) ,
∑ d ≤ D ( d , n ) = 1 μ 2 ( d ) ϕ ( [ d , a ] ) = ∑ d ≤ D f n , a ( d ) ϕ ( a ) = ϕ ( n ) n ϕ ( a ) ∑ d ≤ D / n 1 / 5 g a ( d ) log ( D / d ) + O ( E ϕ ( a ) ) (37) \sum_{\substack{d\le D\\(d,n)=1}}\frac{\mu^2(d)}{\phi([d,a])}
=\sum_{d\le D}\frac{f_{n,a}(d)}{\phi(a)}
=\frac{\phi(n)}{n\phi(a)}\sum_{d\le D/n^{1/5}}g_a(d)\log(D/d)+O\left(\frac{E}{\phi(a)}\right) \tag*{(37)} d ≤ D ( d , n ) = 1 ∑ ϕ ([ d , a ]) μ 2 ( d ) = d ≤ D ∑ ϕ ( a ) f n , a ( d ) = n ϕ ( a ) ϕ ( n ) d ≤ D / n 1/5 ∑ g a ( d ) log ( D / d ) + O ( ϕ ( a ) E ) (37)
for
E : = ∑ d ≤ D ∣ g a ( d ) ∣ ( log log n ) 2 + ∑ d > D / n 1 / 5 ∣ g a ( d ) ∣ log d . (38) E:=\sum_{d\le D}|g_a(d)|(\log\log n)^2+\sum_{d>D/n^{1/5}}|g_a(d)|\log d. \tag*{(38)} E := d ≤ D ∑ ∣ g a ( d ) ∣ ( log log n ) 2 + d > D / n 1/5 ∑ ∣ g a ( d ) ∣ log d . (38)
To bound the first sum in E E E we use ∑ d ≥ 1 ∣ g a ( d ) ∣ = 2 ω ( a ) − 1 2 ∣ a ≪ k 1 \sum_{d\ge1}|g_a(d)|=2^{\omega(a)-1}2_{|a}\ll_k1 ∑ d ≥ 1 ∣ g a ( d ) ∣ = 2 ω ( a ) − 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 a g_a g a then d d d is odd and
∣ g a ( d ) ∣ ≤ ∏ p ∣ 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 d / log 3 . |g_a(d)|\le\prod_{p\mid d}p^{-i}\prod_{p^i\mid d}\left(1+\frac{1}{p-1}\right)^{i-1}\le\frac{a}{d}\prod_{p^i\mid d}\left(1+\frac{1}{p-1}\right)^{i-1}\le\frac{a}{d}\left(\frac{3}{2}\right)^{\log d/\log3}. ∣ g a ( d ) ∣ ≤ p ∣ 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 ( 2 3 ) l o g d / l o g 3 .
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 a ( d ) ∣ ≪ k a ( log T ) k T T log ( 3 / 2 ) / log 3 . \sum_{d\in[T,2T)}|g_a(d)|\ll_k\frac{a(\log T)^k}{T}T^{\log(3/2)/\log3}. d ∈ [ T , 2 T ) ∑ ∣ g 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 (38) , we express the sum in the right-hand side of (37) as
∑ d ≤ D / n 1 / 5 g a ( d ) log ( D / d ) = log D ∏ p ∣ a ( ∑ i = 0 ∞ g a ( p i ) ) − ∑ d ≥ 1 g a ( d ) log d + O ( E ) . \sum_{d\le D/n^{1/5}}g_a(d)\log(D/d)=\log D\prod_{p\mid a}\left(\sum_{i=0}^{\infty}g_a(p^i)\right)-\sum_{d\ge1}g_a(d)\log d+O(E). d ≤ D / n 1/5 ∑ g a ( d ) log ( D / d ) = log D p ∣ a ∏ ( i = 0 ∑ ∞ g a ( p i ) ) − d ≥ 1 ∑ g a ( d ) log d + O ( E ) .
The p p p -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 .
Proof of Proposition 1.3
As in the proof of Proposition 1.2, we work with A a ( n ) A_a(n) A a ( n ) (defined in (23) ) and reduce the lemma to proving
∑ 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 ) . (39) \sum_{\substack{1\le a\le n\\\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*{(39)} 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 ) . (39)
We write 2 ω ( n − p ) 2^{\omega(n-p)} 2 ω ( n − p ) as a divisor sum, separate the contribution of large square divisors, and apply divisor switching. We have, for m = n − p m=n-p m = n − p ,
2 ω ( m ) = ∑ m = d s μ 2 ( d ) = ∑ m = e 2 d s μ ( e ) = ∑ m = e 2 d s e > V μ ( e ) + ∑ m = e 2 d s e ≤ V d ≤ D μ ( e ) + ∑ m = e 2 d s e ≤ V s < m / ( e 2 D ) μ ( e ) 2^{\omega(m)}=\sum_{m=ds}\mu^2(d)=\sum_{m=e^2ds}\mu(e)=\sum_{\substack{m=e^2ds\\e>V}}\mu(e)+\sum_{\substack{m=e^2ds\\e\le V\\d\le D}}\mu(e)+\sum_{\substack{m=e^2ds\\e\le V\\s<m/(e^2D)}}\mu(e) 2 ω ( m ) = m = d s ∑ μ 2 ( d ) = m = e 2 d s ∑ μ ( e ) = m = e 2 d s e > V ∑ μ ( e ) + m = e 2 d s e ≤ V d ≤ D ∑ μ ( e ) + m = e 2 d s e ≤ V s < m / ( e 2 D ) ∑ μ ( e )
with the choices
V = n 2 η and D = n 1 / 2 + 2 η . V=n^{2\eta}\qquad\text{and}\qquad D=n^{1/2+2\eta}. V = n 2 η and 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 ) .
so that
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_0(a)=\sum_{\substack{v<e\le\sqrt n\\ d\le n}}\mu(e)\pi(n-1;[de^2,a],n),\qquad S_1(a)=\sum_{\substack{e\le V\\ d\le D}}\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 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)-\frac{\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 ) = N i ( a ) + E i ( a ) ( i = 1 , 2 ) . S_i(a)=N_i(a)+E_i(a)\qquad(i=1,2). S i ( a ) = N i ( a ) + E i ( a ) ( i = 1 , 2 ) .
for
N 1 ( a ) = Li ( n − 1 ) ∑ e ≤ V d ≤ D ( d e , n ) = 1 μ ( e ) φ ( [ d e 2 , a ] ) , E 1 ( a ) = ∑ e ≤ V d ≤ D ( d e , n ) = 1 μ ( e ) E ( n − 1 ; [ d e 2 , a ] , n ) , N_1(a)=\operatorname{Li}(n-1)\sum_{\substack{e\le V\\ d\le D\\ (de,n)=1}}\frac{\mu(e)}{\varphi([de^2,a])},\qquad E_1(a)=\sum_{\substack{e\le V\\ d\le D\\ (de,n)=1}}\mu(e)E(n-1;[de^2,a],n), N 1 ( a ) = Li ( n − 1 ) e ≤ V d ≤ D ( d e , n ) = 1 ∑ φ ([ d e 2 , a ]) μ ( e ) , E 1 ( a ) = e ≤ V d ≤ D ( d e , n ) = 1 ∑ μ ( e ) E ( n − 1 ; [ d e 2 , a ] , n ) ,
N 2 ( a ) = ∑ e ≤ V s < ( n − 2 ) / ( e 2 D ) ( s e , n ) = 1 μ ( e ) Li ( n − s e 2 D − 1 ) φ ( [ s e 2 , a ] ) , E 2 ( a ) = ∑ e ≤ V s < ( n − 2 ) / ( e 2 D ) ( s e , n ) = 1 μ ( e ) E ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) . N_2(a)=\sum_{\substack{e\le V\\ s<(n-2)/(e^2D)\\ (se,n)=1}}\frac{\mu(e)\operatorname{Li}(n-se^2D-1)}{\varphi([se^2,a])},\qquad E_2(a)=\sum_{\substack{e\le V\\ s<(n-2)/(e^2D)\\ (se,n)=1}}\mu(e)E(n-se^2D-1;[se^2,a],n). N 2 ( a ) = e ≤ V s < ( n − 2 ) / ( e 2 D ) ( se , n ) = 1 ∑ φ ([ s e 2 , a ]) μ ( e ) Li ( n − s e 2 D − 1 ) , E 2 ( a ) = e ≤ V s < ( n − 2 ) / ( e 2 D ) ( se , n ) = 1 ∑ μ ( e ) E ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) .
The rest of the proof is separated into four lemmas, proved below, which together establish (5.1). This will complete the proof of Proposition 1.3.
Lemma 5.1. We have ∑ a ≤ n η ∣ S 0 ( a ) ∣ ≪ n 1 − η \sum_{a\le n^\eta}|S_0(a)|\ll n^{1-\eta} ∑ a ≤ n η ∣ S 0 ( a ) ∣ ≪ n 1 − η .
Lemma 5.2. For every B > 0 B>0 B > 0 , ∑ a ≤ n η ( a , n ) = 1 ∣ E 1 ( a ) ∣ ≪ B n ( log n ) − B \sum_{\substack{a\le n^\eta\\(a,n)=1}}|E_1(a)|\ll_B n(\log n)^{-B} ∑ a ≤ n η ( a , n ) = 1 ∣ E 1 ( a ) ∣ ≪ B n ( log n ) − B .
Lemma 5.3. For every B > 0 B>0 B > 0 , ∑ a ≤ n η ( a , n ) = 1 ∣ E 2 ( a ) ∣ ≪ B n ( log n ) − B \sum_{\substack{a\le n^\eta\\(a,n)=1}}|E_2(a)|\ll_B n(\log n)^{-B} ∑ a ≤ n η ( a , n ) = 1 ∣ E 2 ( a ) ∣ ≪ B n ( log n ) − B .
Lemma 5.4. Fix k ≥ 1 k\ge1 k ≥ 1 . Suppose 1 ≤ a ≤ n η 1\le a\le n^\eta 1 ≤ a ≤ n η is squarefree with ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k and ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 . We have
N 1 ( a ) + N 2 ( a ) = φ ( n ) ( 2 ω ( a ) a − 2 D a φ ( a ) log n ) + O k ( n ( log log n ) 2 a log n ) . N_1(a)+N_2(a)=\varphi(n)\left(\frac{2^{\omega(a)}}{a}-\frac{2D_a}{\varphi(a)\log n}\right)+O_k\left(\frac{n(\log\log n)^2}{a\log n}\right). N 1 ( a ) + N 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 5.1
The 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 ) ∣ ≤ ∑ 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{e\ge V\\ d\le n}}\frac{n}{[de^2,a]}\le\sum_{\substack{e\ge V\\ d\le n}}\frac{n}{de^2}\ll\frac{n\log n}{V}. ∣ S 0 ( a ) ∣ ≤ 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 5.3
Letting d : = [ s e 2 , a ] d:=[se^2,a] d := [ s e 2 , a ] , we have
∑ a ≤ n η ( a , n ) = 1 ∣ E 2 ( a ) ∣ = ∑ a ≤ n η ( a , n ) = 1 ∣ ∑ e ≤ V s < ( n − 2 ) / ( e 2 D ) ( s e , n ) = 1 μ ( e ) E ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) ∣ ≤ ∑ d ≤ n 1 / 2 − η ( d , n ) = 1 τ 3 ( d ) max y ≤ n ∣ E ( y ; d , n ) ∣ . \sum_{\substack{a\le n^\eta\\(a,n)=1}}|E_2(a)|
=\sum_{\substack{a\le n^\eta\\(a,n)=1}}\left|\sum_{\substack{e\le V\\s<(n-2)/(e^2D)\\(se,n)=1}}\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^3(d)\max_{y\le n}|E(y;d,n)|. a ≤ n η ( a , n ) = 1 ∑ ∣ E 2 ( a ) ∣ = a ≤ n η ( a , n ) = 1 ∑ e ≤ V s < ( n − 2 ) / ( e 2 D ) ( se , n ) = 1 ∑ μ ( e ) E ( n − s e 2 D − 1 ; [ s e 2 , a ] , n ) ≤ d ≤ n 1/2 − η ( d , n ) = 1 ∑ τ 3 ( d ) y ≤ n max ∣ E ( y ; d , n ) ∣.
The conclusion follows by applying Cauchy–Schwarz and the Bombieri–Vinogradov Theorem [9 Lemma] (cf. the proof of Lemma 4.2).
Proof of Lemma 5.2
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. In the previous two lemmas, η \eta η can be close to 1 1 1 , but not here. We have
∑ a ≤ n η ( a , n ) = 1 ∣ E 1 ( a ) ∣ = ∑ a ≤ n η ( a , n ) = 1 ∣ ∑ e ≤ V ( e , n ) = 1 μ ( e ) ∑ d ≤ D ( d , n ) = 1 E ( n − 1 ; [ d e 2 , a ] , n ) ∣ = ∑ a ≤ n η ( a , n ) = 1 ∣ ∑ e ≤ V ( e , n ) = 1 b ∣ ( a e ) ∞ μ ( e ) ∑ d ≤ D / b ( d / b , n a e ) = 1 E ( n − 1 ; [ d e 2 , a ] , n ) ∣ = ∑ a ≤ n η ( a , n ) = 1 ∣ ∑ e ≤ V ( e , n ) = 1 b ∣ ( a e ) ∞ μ ( e ) ∑ d ′ ≤ D / b ( d ′ , n a e ) = 1 E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ∣ , \begin{aligned}
\sum_{\substack{a\le n^\eta\\(a,n)=1}} |E_1(a)|=\sum_{\substack{a\le n^\eta\\(a,n)=1}}\left|\sum_{\substack{e\le V\\(e,n)=1}}\mu(e)\sum_{\substack{d\le D\\(d,n)=1}}E(n-1;[de^2,a],n)\right| \\
&=\sum_{\substack{a\le n^\eta\\(a,n)=1}}\left|\sum_{\substack{e\le V\\(e,n)=1\\b\mid(ae)^\infty}}\mu(e)\sum_{\substack{d\le D/b\\(d/b,nae)=1}}E(n-1;[de^2,a],n)\right| \\
&=\sum_{\substack{a\le n^\eta\\(a,n)=1}}\left|\sum_{\substack{e\le V\\(e,n)=1\\b\mid(ae)^\infty}}\mu(e)\sum_{\substack{d'\le D/b\\(d',nae)=1}}E(n-1;d'[be^2,a],n)\right|,
\end{aligned} a ≤ n η ( a , n ) = 1 ∑ ∣ E 1 ( a ) ∣ = a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 ∑ μ ( e ) d ≤ D ( d , n ) = 1 ∑ E ( n − 1 ; [ d e 2 , a ] , n ) = a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 b ∣ ( a e ) ∞ ∑ μ ( e ) d ≤ D / b ( d / b , na e ) = 1 ∑ E ( n − 1 ; [ d e 2 , a ] , n ) = a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 b ∣ ( a e ) ∞ ∑ μ ( e ) d ′ ≤ D / b ( d ′ , na e ) = 1 ∑ E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ,
where we substituted d = b d ′ d=bd' d = b d ′ . 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 η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 μ 2 ( e ) ∑ b ≤ J b ∣ ( a e ) ∞ ∣ ∑ d ′ ≤ D / b ( d ′ , n a e ) = 1 E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ∣ . E_{1,1}\le\sum_{\substack{a\le n^\eta\\(a,n)=1}}\sum_{\substack{e\le V\\(e,n)=1}}\mu^2(e)\sum_{\substack{b\le J\\b\mid(ae)^\infty}}\left|\sum_{\substack{d'\le D/b\\(d',nae)=1}}E(n-1;d'[be^2,a],n)\right|. E 1 , 1 ≤ a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 ∑ μ 2 ( e ) b ≤ J b ∣ ( a e ) ∞ ∑ d ′ ≤ D / b ( d ′ , na e ) = 1 ∑ E ( n − 1 ; d ′ [ b e 2 , a ] , n ) .
To make the summation range of d ′ d' d ′ independent of b b b , we apply a standard finer-than-dyadic decomposition on the d ′ d' d ′ summation (see e.g. the proof of [2 Thm. 1.1] ). More precisely, set λ = 1 + ( log n ) − B − 100 \lambda=1+(\log n)^{-B-100} λ = 1 + ( log n ) − B − 100 and decompose E 1 , 1 E_{1,1} E 1 , 1 into the contribution of d ′ ≤ D / J d'\le D/J d ′ ≤ D / J and at most ( log n ) B + 101 (\log n)^{B+101} ( log n ) B + 101 sums with the additional condition ( D / J ) λ k < d ′ ≤ ( D / J ) λ k + 1 (D/J)\lambda^k<d'\le(D/J)\lambda^{k+1} ( D / J ) λ k < d ′ ≤ ( D / J ) λ k + 1 for some k ≥ 0 k\ge0 k ≥ 0 . Thus, by the triangle inequality,
∑ b ≤ J b ∣ ( a e ) ∞ ∣ ∑ d ′ ≤ D / b ( d ′ , n a e ) = 1 ∣ ≤ ∑ b ≤ J b ∣ ( a e ) ∞ ∣ ∑ d ′ ≤ D / J ( d ′ , n a e ) = 1 ∣ + ∑ b ≤ J b ∣ ( a e ) ∞ k ≥ 0 ∣ ∑ ( D / J ) k < d ′ ≤ ( D / J ) k + 1 ( d ′ , n a e ) = 1 ∣ . \sum_{\substack{b\le J\\b\mid(ae)^\infty}}\left|\sum_{\substack{d'\le D/b\\(d',nae)=1}}\right|
\le\sum_{\substack{b\le J\\b\mid(ae)^\infty}}\left|\sum_{\substack{d'\le D/J\\(d',nae)=1}}\right|+\sum_{\substack{b\le J\\b\mid(ae)^\infty\\k\ge0}}\left|\sum_{\substack{(D/J)^k<d'\le(D/J)^{k+1}\\(d',nae)=1}}\right|. b ≤ J b ∣ ( a e ) ∞ ∑ d ′ ≤ D / b ( d ′ , na e ) = 1 ∑ ≤ b ≤ J b ∣ ( a e ) ∞ ∑ d ′ ≤ D / J ( d ′ , na e ) = 1 ∑ + b ≤ J b ∣ ( a e ) ∞ k ≥ 0 ∑ ( D / J ) k < d ′ ≤ ( D / J ) k + 1 ( d ′ , na e ) = 1 ∑ .
For each b ≤ J b\le J b ≤ J there exists a unique k 0 ( b ) k_0(b) k 0 ( b ) such that ( D / J ) λ k 0 ( b ) < D / b ≤ ( D / J ) λ k 0 ( b ) + 1 (D/J)\lambda^{k_0(b)}<D/b\le(D/J)\lambda^{k_0(b)+1} ( D / J ) λ k 0 ( b ) < D / b ≤ ( D / J ) λ k 0 ( b ) + 1 . For k < k 0 ( b ) k<k_0(b) k < k 0 ( b ) the condition d ′ ≤ D / b d'\le D/b d ′ ≤ D / b is implied by the other range condition ( d ′ ≤ ( D / J ) λ k + 1 ) (d'\le(D/J)\lambda^{k+1}) ( d ′ ≤ ( D / J ) λ k + 1 ) and for k > k 0 ( b ) k>k_0(b) k > k 0 ( b ) the sum over d ′ d' d ′ is empty. The term with k = k 0 ( b ) k=k_0(b) k = k 0 ( b ) can be estimated trivially, indeed it is
∑ a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 μ 2 ( e ) ∑ b ≤ J b ∣ ( a e ) ∞ k = k 0 ( b ) ∑ ( D / J ) λ k < d ′ ≤ ( D / J ) λ k + 1 ( d ′ , n a e ) = 1 ∣ E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ∣ ≪ ∑ a ≤ n η ( a , n ) = 1 ∑ e ≤ V ∑ b ≤ J b ∣ ( a e ) ∞ k = k 0 ( b ) ∑ ( D / J ) λ k < d ′ ≤ ( D / J ) λ k + 1 n φ ( d ′ ) φ ( [ b e 2 , a ] ) ≪ n ( log log n ) 2 ∑ a ≤ n b ′ ≤ J 2 τ ( b ′ ) [ b ′ , a ] ∑ ( D / J ) λ k 0 ( b ) < d ′ ≤ ( D / J ) λ k 0 ( b ) + 1 1 d ′ ≪ n ( log n ) 4 log λ ≪ ( log n ) − B − 50 , \begin{aligned}
\sum_{\substack{a\le n^\eta\\(a,n)=1}}\sum_{\substack{e\le V\\(e,n)=1}}\mu^2(e)\sum_{\substack{b\le J\\b\mid(ae)^\infty\\k=k_0(b)}}\sum_{\substack{(D/J)\lambda^k<d'\le(D/J)\lambda^{k+1}\\(d',nae)=1}}\left|E(n-1;d'[be^2,a],n)\right| \\
&\ll\sum_{\substack{a\le n^\eta\\(a,n)=1}}\sum_{e\le V}\sum_{\substack{b\le J\\b\mid(ae)^\infty\\k=k_0(b)}}\sum_{(D/J)\lambda^k<d'\le(D/J)\lambda^{k+1}}\frac{n}{\varphi(d')\varphi([be^2,a])} \\
&\ll n(\log\log n)^2\sum_{\substack{a\le n\\b'\le J^2}}\frac{\tau(b')}{[b',a]}\sum_{(D/J)\lambda^{k_0(b)}<d'\le(D/J)\lambda^{k_0(b)+1}}\frac{1}{d'} \\
&\ll n(\log n)^4\log\lambda\ll(\log n)^{-B-50},
\end{aligned} a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 ∑ μ 2 ( e ) b ≤ J b ∣ ( a e ) ∞ k = k 0 ( b ) ∑ ( D / J ) λ k < d ′ ≤ ( D / J ) λ k + 1 ( d ′ , na e ) = 1 ∑ E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ≪ a ≤ n η ( a , n ) = 1 ∑ e ≤ V ∑ b ≤ J b ∣ ( a e ) ∞ k = k 0 ( b ) ∑ ( D / J ) λ k < d ′ ≤ ( D / J ) λ k + 1 ∑ φ ( d ′ ) φ ([ b e 2 , a ]) n ≪ n ( log log n ) 2 a ≤ n b ′ ≤ J 2 ∑ [ b ′ , a ] τ ( b ′ ) ( D / J ) λ k 0 ( b ) < d ′ ≤ ( D / J ) λ k 0 ( b ) + 1 ∑ d ′ 1 ≪ n ( log n ) 4 log λ ≪ ( log n ) − B − 50 ,
recalling λ = 1 + ( log n ) − B − 100 \lambda=1+(\log n)^{-B-100} λ = 1 + ( log n ) − B − 100 . Here b ′ b' b ′ stands for b e 2 be^2 b e 2 , in the second inequality we used ϕ ( m ) ≥ m / log log m \phi(m)\ge m/\log\log m ϕ ( m ) ≥ m / log log m [13 Thm. 2.9] and in third one we used ∑ a ≤ T , b ′ ≤ S τ ( b ′ ) τ ( b ′ ) ≪ T S ( log ( T S + 2 ) ) 3 \sum_{a\le T,b'\le S}\tau(b')\tau(b')\ll TS(\log(TS+2))^3 ∑ a ≤ T , b ′ ≤ S τ ( b ′ ) τ ( b ′ ) ≪ T S ( log ( T S + 2 ) ) 3 .
Consequently after some simple reshuffling of the terms with k < k 0 ( b ) k<k_0(b) k < k 0 ( b ) with the help of the triangle inequality, we have reduced the required E 1 , 1 E_{1,1} E 1 , 1 estimate for Lemma 5.2 to showing
E 1 , 1 , D ′ ≪ n ( log n ) − 2 B − 101 , (40) E_{1,1,D'}\ll n(\log n)^{-2B-101}, \tag*{(40)} E 1 , 1 , D ′ ≪ n ( log n ) − 2 B − 101 , (40)
for any D ′ ≤ D D' \le D D ′ ≤ D , where
E 1 , 1 , D ′ = ∑ a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 μ 2 ( e ) ∑ b ≤ J b ∣ ( a e ) ∞ ∣ ∑ d ′ ≤ D ′ ( d ′ , n a e ) = 1 E ( n − 1 ; d ′ [ b e 2 , a ] , n ) ∣ . E_{1,1,D'}=\sum_{\substack{a\le n^\eta\\(a,n)=1}}\sum_{\substack{e\le V\\(e,n)=1}}\mu^2(e)\sum_{\substack{b\le J\\b\mid(ae)^\infty}}\left|\sum_{\substack{d'\le D'\\(d',nae)=1}}E(n-1;d'[be^2,a],n)\right|. E 1 , 1 , D ′ = a ≤ n η ( a , n ) = 1 ∑ e ≤ V ( e , n ) = 1 ∑ μ 2 ( e ) b ≤ J b ∣ ( a e ) ∞ ∑ d ′ ≤ D ′ ( d ′ , na e ) = 1 ∑ E ( n − 1 ; d ′ [ b e 2 , a ] , n ) .
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 η ( g , n ) = 1 τ ( g ) 3 ∣ ∑ d ′ ≤ D ′ ( d ′ , n g ) = 1 E ( n − 1 ; d ′ g , n ) ∣ . E_{1,1,D'}\le\sum_{\substack{g\le n^\eta\\(g,n)=1}}\tau(g)^3\left|\sum_{\substack{d'\le D'\\(d',ng)=1}}E(n-1;d'g,n)\right|. E 1 , 1 , D ′ ≤ g ≤ n η ( g , n ) = 1 ∑ τ ( g ) 3 d ′ ≤ D ′ ( d ′ , n g ) = 1 ∑ E ( n − 1 ; d ′ g , n ) .
We quote [6 Prop. 6.1] specialised to a 2 = c = c 0 = 1 a_2=c=c_0=1 a 2 = c = c 0 = 1 .
Proposition 5.5. There is an absolute constant ϖ > 0 \varpi>0 ϖ > 0 with the following property. Let x ≥ 2 x\ge2 x ≥ 2 , Q ≥ 2 Q\ge2 Q ≥ 2 , C ∈ N C\in\mathbb{N} C ∈ N , a ∈ Z ∖ { 0 } a\in\mathbb{Z}\setminus\{0\} a ∈ Z ∖ { 0 } and a sequence ( λ d ) d (\lambda_d)_d ( λ d ) d such that
∣ a ∣ ≤ x 1 + ϖ , ∣ λ d ∣ ≪ τ ( d ) C , Q ≤ x 1 / 2 + ϖ |a|\le x^{1+\varpi},\qquad|\lambda_d|\ll\tau(d)^C,\qquad Q\le x^{1/2+\varpi} ∣ a ∣ ≤ x 1 + ϖ , ∣ λ d ∣ ≪ τ ( d ) C , Q ≤ x 1/2 + ϖ 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\pmod q\\n\equiv w\pmod 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 [6 Prop. 6.1] , this holds for the characteristic function of the primes replacing the von Mangoldt function and so implies (5.2). To prove Lemma 5.2, it remains to estimate E 1 , 2 E_{1,2} E 1 , 2 and we claim
E 1 , 2 ≪ n 1 − η / 2 . (41) E_{1,2}\ll n^{1-\eta/2}. \tag*{(41)} E 1 , 2 ≪ n 1 − η /2 . (41)
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 a ∼ A 1 d ∑ J < b ≤ D / d ′ b ∣ ( a e ) ∞ 1 [ b e 2 , a ] . E_{1,2}\ll n\sum_{\substack{a\le n^\eta\\e\le V\\d'<D/J\\a\sim A}}\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 a ∼ A ∑ 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 (5.3) 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 (42) \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*{(42)} a ∼ A e ∼ V ∑ b ∼ J b ∣ ( a e ) ∞ ∑ ( b e 2 , a ) ≪ ( 2 + log A V ) C ε J ε A 2 V (42)
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 (5.4) 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 (5.3) if ε \varepsilon ε is sufficiently small.
To demonstrate (5.4), 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\|h_2}p^{\lceil k/2\rceil} h 2 ′ = ∏ p k ∥ h 2 p ⌈ k /2 ⌉ . We can bound the left-hand side of (5.4) by
≤ ∑ h 1 h 2 ∣ a ∼ A h 1 h 2 ∑ h 2 ′ ∣ e ∼ V 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_{\substack{h_1h_2\mid a\sim A}}h_1h_2\sum_{\substack{h'_2\mid e\sim V\\b\sim J\\h_1\mid b\mid(ae)^\infty}}1
\le\sum_{\substack{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 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_{\substack{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 .
This proves (42) , and completes the proof of Lemma 5.2.
Proof of Lemma 5.4
Let 1 ≤ a ≤ n η 1\leq a\leq n^\eta 1 ≤ a ≤ n η be squarefree with ( a , n ) = 1 (a,n)=1 ( a , n ) = 1 . The expression N 1 ( a ) N_1(a) N 1 ( a ) matches M 2 ( a ) M_2(a) M 2 ( a ) defined in (26) , so
N 1 ( a ) = Li ( n − 1 ) ∑ d ≤ D ( d , n ) = 1 μ 2 ( d ) ϕ ( [ d , a ] ) + O ( n a log n ) . N_1(a)=\operatorname{Li}(n-1)\sum_{\substack{d\leq D\\(d,n)=1}}\frac{\mu^2(d)}{\phi([d,a])}+O\left(\frac{n}{a\log n}\right). N 1 ( a ) = Li ( n − 1 ) d ≤ D ( d , n ) = 1 ∑ ϕ ([ d , a ]) μ 2 ( d ) + O ( a log n n ) .
by Lemma 4.3, its proof and our choice of V V V . The d d d -sum is estimated in Lemma 4.4, giving
N 1 ( a ) = ϕ ( n ) ( 2 ω ( a ) a log D log n − D a ϕ ( a ) log n ) + O k ( n ( log log n ) 2 a log n ) . N_1(a)=\phi(n)\left(\frac{2^{\omega(a)}}{a}\frac{\log D}{\log n}-\frac{D_a}{\phi(a)\log n}\right)+O_k\left(\frac{n(\log\log n)^2}{a\log n}\right). N 1 ( a ) = ϕ ( n ) ( a 2 ω ( a ) log n log D − ϕ ( a ) log n D a ) + O k ( a log n n ( log log n ) 2 ) .
where we used (6) . It remains to deal with N 2 ( a ) N_2(a) N 2 ( a ) . By completing the e e e -range we have
N 2 ( a ) = ∑ e ≥ 1 s e 2 < ( n − 2 ) / D ( s e , n ) = 1 μ ( e ) Li ( n − s e 2 D − 1 ) ϕ ( [ s e 2 , a ] ) + O ( n V ) . N_2(a)=\sum_{\substack{e\geq1\\ se^2<(n-2)/D\\(se,n)=1}}\frac{\mu(e)\operatorname{Li}(n-se^2D-1)}{\phi([se^2,a])}+O\left(\frac{n}{V}\right). N 2 ( a ) = e ≥ 1 s e 2 < ( n − 2 ) / D ( se , n ) = 1 ∑ ϕ ([ s e 2 , a ]) μ ( e ) Li ( n − s e 2 D − 1 ) + O ( V n ) .
We now use Li ( n − s e 2 D − 1 ) = Li ( n − 1 ) + O ( s e 2 D / log n ) \operatorname{Li}(n-se^2D-1)=\operatorname{Li}(n-1)+O(se^2D/\log n) Li ( n − s e 2 D − 1 ) = Li ( n − 1 ) + O ( s e 2 D / log n ) to decompose N 2 ( a ) N_2(a) N 2 ( a ) as
N 2 ( a ) = N 2 , 1 ( a ) + N 2 , 2 ( a ) + O ( n V ) N_2(a)=N_{2,1}(a)+N_{2,2}(a)+O\left(\frac{n}{V}\right) N 2 ( a ) = N 2 , 1 ( a ) + N 2 , 2 ( a ) + O ( V n )
where
N 2 , 1 ( a ) = Li ( n − 1 ) ∑ s e 2 < ( n − 2 ) / D ( s e , n ) = 1 μ ( e ) ϕ ( [ s e 2 , a ] ) = Li ( n − 1 ) ∑ m < ( n − 2 ) / D ( m , n ) = 1 μ 2 ( m ) ϕ ( [ m , a ] ) N_{2,1}(a)=\operatorname{Li}(n-1)\sum_{\substack{se^2<(n-2)/D\\(se,n)=1}}\frac{\mu(e)}{\phi([se^2,a])}
=\operatorname{Li}(n-1)\sum_{\substack{m<(n-2)/D\\(m,n)=1}}\frac{\mu^2(m)}{\phi([m,a])} N 2 , 1 ( a ) = Li ( n − 1 ) s e 2 < ( n − 2 ) / D ( se , n ) = 1 ∑ ϕ ([ s e 2 , a ]) μ ( e ) = Li ( n − 1 ) m < ( n − 2 ) / D ( m , n ) = 1 ∑ ϕ ([ m , a ]) μ 2 ( m )
and
N 2 , 2 ( a ) ≪ D log n ∑ s e 2 < ( n − 2 ) / D ( s e , n ) = 1 μ 2 ( e ) s e 2 ϕ ( [ s e 2 , a ] ) = D log n ∑ m < ( n − 2 ) / D ( m , n ) = 1 m 2 # { p 2 ∣ m } ϕ ( [ m , a ] ) . (43) N_{2,2}(a)\ll\frac{D}{\log n}\sum_{\substack{se^2<(n-2)/D\\(se,n)=1}}\frac{\mu^2(e)se^2}{\phi([se^2,a])}
=\frac{D}{\log n}\sum_{\substack{m<(n-2)/D\\(m,n)=1}}\frac{m2^{\#\{p^2\mid m\}}}{\phi([m,a])}. \tag*{(43)} N 2 , 2 ( a ) ≪ log n D s e 2 < ( n − 2 ) / D ( se , n ) = 1 ∑ ϕ ([ s e 2 , a ]) μ 2 ( e ) s e 2 = log n D m < ( n − 2 ) / D ( m , n ) = 1 ∑ ϕ ([ m , a ]) m 2 # { p 2 ∣ m } . (43)
We let g = ( a , m ) g=(a,m) g = ( a , m ) in the right-hand side of (43) and use (27) –(28) to find
N 2 , 2 ( a ) ≪ D ϕ ( a ) log n ∑ g ∣ a g ∑ m ≤ n / D g ∣ m ( m / g ) 2 # { p 2 ∣ m } ϕ ( m / g ) . N_{2,2}(a)\ll\frac{D}{\phi(a)\log n}\sum_{g\mid a}g\sum_{\substack{m\leq n/D\\g\mid m}}\frac{(m/g)2^{\#\{p^2\mid m\}}}{\phi(m/g)}. N 2 , 2 ( a ) ≪ ϕ ( a ) log n D g ∣ a ∑ g m ≤ n / D g ∣ m ∑ ϕ ( 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/\phi(m))2^{\#\{p^2\mid m\}} S ( X ) := ∑ m ≤ X ( m / ϕ ( m )) 2 # { p 2 ∣ m } . Note S ( X ) ≪ X S(X)\ll X S ( X ) ≪ X by [13 Thm. 2.14] . Hence
N 2 , 2 ( a ) ≪ D ϕ ( a ) log n ∑ g ∣ a g 2 ω ( g ) S ( n D g ) ≪ n ϕ ( a ) log n 3 ω ( a ) ≪ k n a log n . N_{2,2}(a)\ll\frac{D}{\phi(a)\log n}\sum_{g\mid a}g2^{\omega(g)}S\left(\frac{n}{Dg}\right)\ll\frac{n}{\phi(a)\log n}3^{\omega(a)}\ll_k\frac{n}{a\log n}. N 2 , 2 ( a ) ≪ ϕ ( a ) log n D g ∣ a ∑ g 2 ω ( g ) S ( D g n ) ≪ ϕ ( a ) log n n 3 ω ( a ) ≪ k a log n n .
To conclude we apply Lemma 4.4 with n / D n/D n / D in place of D D D to estimate N 2 , 1 ( a ) N_{2,1}(a) N 2 , 1 ( a ) , obtaining
N 2 ( a ) = ϕ ( n ) ( 2 ω ( a ) a log ( n / D ) log n − D a ϕ ( a ) log n ) + O k ( n ( log log n ) 2 a log n ) . N_2(a)=\phi(n)\left(\frac{2^{\omega(a)}}{a}\frac{\log(n/D)}{\log n}-\frac{D_a}{\phi(a)\log n}\right)+O_k\left(\frac{n(\log\log n)^2}{a\log n}\right). N 2 ( a ) = ϕ ( n ) ( a 2 ω ( a ) log n log ( n / D ) − ϕ ( a ) log n D a ) + O k ( a log n n ( log log n ) 2 ) .
Elementary proof of (1.8)
Let X ∼ N ( 0 , 1 ) X \sim N(0,1) X ∼ N ( 0 , 1 ) . By Lévy’s continuity theorem [7 Thm. 3.3.17] , (1.8) is equivalent to
E e i t ( ω ( X ~ n ) − 2 log log n ( 2 log log n ) 1 / 2 ) = ( ∑ m ≤ n 2 ω ( m ) ) − 1 ∑ m ≤ n 2 ω ( m ) e i t ( ω ( m ) − 2 log log n ( 2 log log n ) 1 / 2 ) → E e i t X = e − t 2 / 2 , t ∈ R , \mathbb{E}e^{it\left(\frac{\omega(\widetilde{X}_n)-2\log\log n}{(2\log\log n)^{1/2}}\right)}
=\left(\sum_{m\le n}2^{\omega(m)}\right)^{-1}\sum_{m\le n}2^{\omega(m)}e^{it\left(\frac{\omega(m)-2\log\log n}{(2\log\log n)^{1/2}}\right)}
\to\mathbb{E}e^{itX}=e^{-t^2/2},\qquad t\in\mathbb{R}, E e i t ( ( 2 l o g l o g n ) 1/2 ω ( X n ) − 2 l o g l o g n ) = ( m ≤ n ∑ 2 ω ( m ) ) − 1 m ≤ n ∑ 2 ω ( m ) e i t ( ( 2 l o g l o g n ) 1/2 ω ( m ) − 2 l o g l o g n ) → E e i tX = e − t 2 /2 , t ∈ R ,
a relation that is readily verified using the Selberg–Delange method, as observed by Elliott [10 p. 1364] . We give an elementary proof of (1.8) using Corollary 3.2. One only needs to verify (3.3) and (3.4), both of which follow from the next lemma, whose proof is a streamlined version of the arguments in [8 §3] .
Lemma 6.1. For positive integers 1 ≤ a ≤ n 1\le a\le n 1 ≤ a ≤ n such that ω ( a ) ≤ k \omega(a)\le k ω ( a ) ≤ k we have
P ( a divides X ~ n ) = 2 ω ( a ) a ( 1 − log a log n + O k ( 1 log n + ∑ p ∣ a 1 p ) ) . \mathbb{P}(a\text{ divides }\widetilde{X}_n)=\frac{2^{\omega(a)}}{a}\left(1-\frac{\log a}{\log n}+O_k\left(\frac{1}{\log n}+\sum_{p\mid a}\frac{1}{p}\right)\right). P ( a divides X n ) = a 2 ω ( a ) 1 − log n log a + O k log n 1 + p ∣ a ∑ p 1 . Proof. Let S a ( n ) : = ∑ a ∣ r ≤ n 2 ω ( r ) S_a(n):=\sum_{a\mid r\le n}2^{\omega(r)} S a ( n ) := ∑ a ∣ r ≤ n 2 ω ( r ) . We have
S a ( n ) = ∑ m ≤ n / a 2 ω ( a m ) = ∑ d ∣ a ∞ 2 ω ( a d ) ∑ m ′ ≤ n / ( a d ) ( m ′ , a ) = 1 2 ω ( m ′ ) = A + B S_a(n)=\sum_{m\le n/a}2^{\omega(am)}
=\sum_{d\mid a^\infty}2^{\omega(ad)}
\sum_{\substack{m'\le n/(ad)\\(m',a)=1}}2^{\omega(m')}
=A+B S a ( n ) = m ≤ n / a ∑ 2 ω ( am ) = d ∣ a ∞ ∑ 2 ω ( a d ) m ′ ≤ n / ( a d ) ( m ′ , a ) = 1 ∑ 2 ω ( m ′ ) = A + B where d d d stands for ( m , a ∞ ) (m,a^\infty) ( m , a ∞ ) , A A A is the contribution of d = 1 d=1 d = 1 and B B B is the contribution of d > 1 d>1 d > 1 . We have
0 ≤ B ≤ ∑ 1 < d ∣ a ∞ 2 ω ( a d ) S 1 ( n / ( a d ) ) 0\le B\le\sum_{1<d\mid a^\infty}2^{\omega(ad)}S_1(n/(ad)) 0 ≤ B ≤ 1 < d ∣ a ∞ ∑ 2 ω ( a d ) S 1 ( n / ( a d )) by dropping the coprimality condition. For A A A we have
A = 2 ω ( a ) ( ∑ m ′ ≤ n / a 2 ω ( m ′ ) − ∑ 1 < d ∣ a ∞ 2 ω ( d ) ∑ m ′ ′ ≤ n / ( a d ) ( m ′ ′ , a ) = 1 2 ω ( m ′ ′ ) ) A=2^{\omega(a)}\left(\sum_{m'\le n/a}2^{\omega(m')}-\sum_{1<d\mid a^\infty}2^{\omega(d)}
\sum_{\substack{m''\le n/(ad)\\(m'',a)=1}}2^{\omega(m'')}\right) A = 2 ω ( a ) m ′ ≤ n / a ∑ 2 ω ( m ′ ) − 1 < d ∣ a ∞ ∑ 2 ω ( d ) m ′′ ≤ n / ( a d ) ( m ′′ , a ) = 1 ∑ 2 ω ( m ′′ ) and so, by dropping the coprimality condition ( m ′ ′ , a ) = 1 (m'',a)=1 ( m ′′ , a ) = 1 ,
0 ≤ 2 ω ( a ) ∑ m ≤ n / a 2 ω ( m ) − A ≤ ∑ 1 < d ∣ a ∞ 2 ω ( a ) + ω ( d ) ∑ m ≤ n / ( a d ) 2 ω ( m ) . 0\le2^{\omega(a)}\sum_{m\le n/a}2^{\omega(m)}-A
\le\sum_{1<d\mid a^\infty}2^{\omega(a)+\omega(d)}
\sum_{m\le n/(ad)}2^{\omega(m)}. 0 ≤ 2 ω ( a ) m ≤ n / a ∑ 2 ω ( m ) − A ≤ 1 < d ∣ a ∞ ∑ 2 ω ( a ) + ω ( d ) m ≤ n / ( a d ) ∑ 2 ω ( m ) . We have proved
∣ S a ( n ) − 2 ω ( a ) S 1 ( n / a ) ∣ ≤ ∑ 1 < d ∣ a ∞ ( 2 ω ( a d ) + 2 ω ( a ) + ω ( d ) ) S 1 ( n / ( d a ) ) . (44) \left|S_a(n)-2^{\omega(a)}S_1(n/a)\right|
\le\sum_{1<d\mid a^\infty}\left(2^{\omega(ad)}+2^{\omega(a)+\omega(d)}\right)S_1(n/(da)). \tag*{(44)} S a ( n ) − 2 ω ( a ) S 1 ( n / a ) ≤ 1 < d ∣ a ∞ ∑ ( 2 ω ( a d ) + 2 ω ( a ) + ω ( d ) ) S 1 ( n / ( d a )) . (44) We divide (6.1) by S 1 ( n ) S_1(n) S 1 ( n ) and use S 1 ( n ) = ζ ( 2 ) − 1 n log n ( 1 + O ( 1 / log n ) ) S_1(n)=\zeta(2)^{-1}n\log n(1+O(1/\log n)) S 1 ( n ) = ζ ( 2 ) − 1 n log n ( 1 + O ( 1/ log n )) [13 p. 42] .
Remark 6.2. Recall the notation (1.7). Given k ≥ 1 k\ge1 k ≥ 1 and a continuous function f : R k → C f:\mathbb{R}^k\to\mathbb{C} f : R k → C such that the (closure of the) support of f f f is ⊆ { ( x 1 , … , x k ) : x 1 , … , x k > 0 , x 1 + ⋯ + x k < 1 } \subseteq\{(x_1,\ldots,x_k):x_1,\ldots,x_k>0,\ x_1+\cdots+x_k<1\} ⊆ {( x 1 , … , x k ) : x 1 , … , x k > 0 , x 1 + ⋯ + x k < 1 } , with further work one can compute
lim n → ∞ E ∑ j 1 , … , j k d i s t i n c t f ( V ( X ~ n ) j 1 , … , V ( X ~ n ) j k ) \lim_{n\to\infty}\mathbb{E}\sum_{\substack{j_1,\ldots,j_k\ \mathrm{distinct}}}f\left(V(\widetilde{X}_n)_{j_1},\ldots,V(\widetilde{X}_n)_{j_k}\right) n → ∞ lim E j 1 , … , j k distinct ∑ f ( V ( X n ) j 1 , … , V ( X n ) j k )
using Lemma 6.1 and show that it coincides with
E ∑ j 1 , … , j k d i s t i n c t f ( L j 1 , … , L j k ) \mathbb{E}\sum_{\substack{j_1,\ldots,j_k\ \mathrm{distinct}}}f(L_{j_1},\ldots,L_{j_k}) E j 1 , … , j k distinct ∑ f ( L j 1 , … , L j k )
where ( L 1 , L 2 , … ) (L_1,L_2,\ldots) ( L 1 , L 2 , … ) is distributed according to PD ( 2 ) \operatorname{PD}(2) PD ( 2 ) . This in turn will imply that V ( X ~ n ) V(\widetilde{X}_n) V ( X n ) tends in distribution to PD ( 2 ) \operatorname{PD}(2) PD ( 2 ) , see [1 ] and especially Remark 12 of [3 ] .
Acknowledgements. We thank Brad Rodgers for discussions around Corollary 1.4 and useful suggestions, and the anonymous referees for corrections, suggestions as well useful comments which led us to a simplified proof of Elliott’s conjecture using Proposition 1.2.
Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK Email address: gorodetsky@maths.ox.ac.uk
Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK Email address: lasse.grimmelt@maths.ox.ac.uk