Introduction
A unit fraction is a fraction of the form 1 / n 1/n 1/ n n n n unit fraction representation of a rational number is a way of writing it as a sum of finitely many distinct unit fractions. The greedy algorithm gives an elementary proof that every positive rational number has such a representation (see, for instance, [26 ] ). Questions about unit fractions are among the oldest in number theory, and many of them are still open (see the surveys [3 , 18 ] ).
In this paper we study unit fraction representations in which every denominator lies in a given set A ⊆ N A \subseteq\mathbb{N} A ⊆ N [5 , 6 , 11 , 13 , 17 , 27 , 30 , 31 ] . A well-known problem of this kind is the coloring conjecture of Erdős and Graham [13 ] , which says that if the integers greater than 1 are colored with finitely many colors, then there exists a monochromatic finite subset B B B 1 = ∑ n ∈ B 1 / n 1=\sum_{n\in B}1/n 1 = ∑ n ∈ B 1/ n [8 ] proved this conjecture, and Bloom [1 ] later proved a stronger density version. More precisely, Bloom showed that every set A ⊆ [ 1 , N ] A\subseteq[1,N] A ⊆ [ 1 , N ]
∑ n ∈ A 1 n ≫ log log log N log log N log N \sum_{n\in A}\frac{1}{n}\gg\frac{\log\log\log N}{\log\log N}\log N n ∈ A ∑ n 1 ≫ log log N log log log N log N contains a subset B B B ∑ n ∈ B 1 / n = 1 \sum_{n\in B}1/n=1 ∑ n ∈ B 1/ n = 1 [22 ] then relaxed the requirement to ∑ n ∈ A 1 / n ≥ ( log N ) 4 / 5 + o ( 1 ) \sum_{n\in A}1/n\ge(\log N)^{4/5+o(1)} ∑ n ∈ A 1/ n ≥ ( log N ) 4/5 + o ( 1 ) [17 ] (see also [33 ] ) and raised again by Bloom [2 ] , is the following.
Question 1.1. For which sets A ⊆ N A\subseteq\mathbb{N} A ⊆ N ∑ n ∈ B 1 / n \sum_{n\in B}1/n ∑ n ∈ B 1/ n B ⊆ A B\subseteq A B ⊆ A
In the same paper [2 ] , Bloom showed that for every fixed nonzero integer h h h { p − h : p prime , p > h } \{p-h:p\text{ prime},\ p>h\} { p − h : p prime , p > h } [29 Conjecture 4.1] . However, the primes themselves do not have this property; for example, 1 cannot be written as a sum of reciprocals of distinct primes. Pomerance [1 , 7 ] constructed another set without this property, by taking the set of all n n n c n / log n cn/\log n c n / log n c > 0 c>0 c > 0 n ≤ N n\le N n ≤ N ( log log N ) 2 (\log\log N)^2 ( log log N ) 2 log log N \log\log N log log N
In the other direction, one can ask how thin a set can be and still have this property. Our main result is that the set of shifted Golomb primes, defined below, has this property. The Golomb primes form a very sparse subset of primes, Erdős [12 ] showed that the sum of their reciprocals up to N N N log log log N \log\log\log N log log log N
To motivate the definition of Golomb primes, it helps to first describe the primes as the output of a sieve. Set p 1 = 2 p_1=2 p 1 = 2 p 1 , … , p k p_1,\ldots,p_k p 1 , … , p k p k + 1 p_{k+1} p k + 1 p k p_k p k p k + 1 ≢ 0 ( m o d p i ) p_{k+1}\not\equiv0\pmod{p_i} p k + 1 ≡ 0 ( mod p i ) 1 ≤ i ≤ k 1\le i\le k 1 ≤ i ≤ k [16 ] used a similar sieve on the primes, removing the residue class 1 in place of the class 0. His motivation came from studying integers n n n ( n , ϕ ( n ) ) = 1 (n,\phi(n))=1 ( n , ϕ ( n )) = 1 [14 , 25 ] . These are exactly the n n n n n n
Definition. The Golomb primes are defined inductively as follows. Let g 1 : = 3 g_1:=3 g 1 := 3 g 1 , … , g k g_1,\ldots,g_k g 1 , … , g k g k + 1 g_{k+1} g k + 1 g k g_k g k g k + 1 ≢ 1 ( m o d g i ) g_{k+1}\not\equiv1\pmod{g_i} g k + 1 ≡ 1 ( mod g i ) 1 ≤ i ≤ k 1\le i\le k 1 ≤ i ≤ k G \mathcal{G} G
G = { 3 , 5 , 17 , 23 , 29 , 53 , 83 , 89 , 113 , … } . \mathcal{G}=\{3,5,17,23,29,53,83,89,113,\ldots\}. G = { 3 , 5 , 17 , 23 , 29 , 53 , 83 , 89 , 113 , … } . The Golomb primes are a natural analogue of the primes, but apart from the work of Erdős [12 ] , little is known about them. Let G ( x ) = G ∩ [ 1 , x ] \mathcal{G}(x)=\mathcal{G}\cap[1,x] G ( x ) = G ∩ [ 1 , x ] x x x [12 ] proved the following:
Theorem 1.2 (Erdős [12 ] ). We have
∣ G ( x ) ∣ = ( 1 + o ( 1 ) ) x log x log log x (1) |\mathcal{G}(x)|=(1+o(1))\frac{x}{\log x\log\log x} \tag*{(1)} ∣ G ( x ) ∣ = ( 1 + o ( 1 )) log x log log x x (1) and
∏ q ∈ G ( x ) ( 1 − 1 q − 1 ) = 1 + o ( 1 ) log log x . (2) \prod_{q\in\mathcal{G}(x)}\left(1-\frac{1}{q-1}\right)=\frac{1+o(1)}{\log\log x}. \tag*{(2)} q ∈ G ( x ) ∏ ( 1 − q − 1 1 ) = log log x 1 + o ( 1 ) . (2) Further, there exists a constant c > 0 c>0 c > 0
∑ q ∈ G ( x ) 1 q = log log log x − c + o ( 1 ) . (3) \sum_{q\in\mathcal{G}(x)}\frac{1}{q}=\log\log\log x-c+o(1). \tag*{(3)} q ∈ G ( x ) ∑ q 1 = log log log x − c + o ( 1 ) . (3) By equation (1) , the Golomb primes up to x x x 1 / log log x 1/\log\log x 1/ log log x x x x [2 ] , which requires positive relative density, does not apply to the Golomb primes. On the other hand, by equation (3) the sum of reciprocals of Golomb primes up to x x x log log log x \log\log\log x log log log x Golomb-prime-free if no Golomb prime divides it. More precisely, we prove the following.
Theorem 1.3 (Main result). Let h h h nonzero integer , and let a , b ∈ Z + a,b\in\mathbb{Z}^{+} a , b ∈ Z + ( a , b ) = 1 (a,b)=1 ( a , b ) = 1 ( b , h ) = 1 (b,h)=1 ( b , h ) = 1 ( b , h − 1 ) (b,h-1) ( b , h − 1 ) h = 1 h=1 h = 1 b b b y ≥ ∣ h ∣ y\ge|h| y ≥ ∣ h ∣ B B B y y y
a b = ∑ g ∈ B 1 g − h . (4) \frac{a}{b}=\sum_{g\in B}\frac{1}{g-h}. \tag*{(4)} b a = g ∈ B ∑ g − h 1 . (4) The conditions on b b b § 6 ).
To prove Theorem 1.3, we need information on the distribution of Golomb primes in arithmetic progressions. We prove the following Siegel–Walfisz-type theorem for Golomb primes, which may be of independent interest.
Let G ( x ; b , h ) \mathcal{G}(x;b,h) G ( x ; b , h ) g ≤ x g\le x g ≤ x g ≡ h ( m o d b ) g\equiv h\pmod b g ≡ h ( mod b )
Theorem 1.4 (Golomb primes in arithmetic progressions). Fix A > 0 A > 0 A > 0 For all 1 ≤ b ≤ ( log x ) A 1 \le b \le(\log x)^A 1 ≤ b ≤ ( log x ) A and all nonzero h ∈ Z h \in\mathbb{Z} h ∈ Z such that ( b , h ) = 1 (b,h)=1 ( b , h ) = 1 and ( b , h − 1 ) (b,h-1) ( b , h − 1 )
∣ G ( x ; b , h ) ∣ = ( 1 + o ( 1 ) ) x ϕ ( b ) log x log log x ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . |\mathcal{G}(x;b,h)|=(1+o(1))\frac{x}{\phi(b)\log x\log\log x}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. ∣ G ( x ; b , h ) ∣ = ( 1 + o ( 1 )) ϕ ( b ) log x log log x x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . where the o ( 1 ) o(1) o ( 1 ) term depends on A A A
Theorem 1.4 says that the Golomb primes are equidistributed among the allowed residue classes h h h b b b x / ( log x log log x ) x/(\log x\log\log x) x / ( log x log log x ) x x x Theorem 1.2 ), and the factor 1 / ϕ ( b ) 1/\phi(b) 1/ ϕ ( b ) [9 Chapter 4] . Now suppose that a Golomb prime q q q b b b q ∤ h − 1 q\nmid h-1 q ∤ h − 1 ( b , h − 1 ) (b,h-1) ( b , h − 1 ) p ≡ h ( m o d b ) p\equiv h\pmod b p ≡ h ( mod b ) p ≡ h ( m o d q ) p\equiv h\pmod q p ≡ h ( mod q ) p ≢ 1 ( m o d q ) p\not\equiv1\pmod q p ≡ 1 ( mod q ) q ∣ b q\mid b q ∣ b p ≢ 1 ( m o d q ) p\not\equiv1\pmod q p ≡ 1 ( mod q ) p ≡ h ( m o d b ) p\equiv h\pmod b p ≡ h ( mod b ) ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 \prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1} ∏ q ∣ b q ∈ G ( 1 − q − 1 1 ) − 1
We call the positive integers g − h g-h g − h g ∈ G g\in\mathcal{G} g ∈ G h h h h h h
G n s m ( x ; b , h ; z ) : = # { g ∈ G ( x ; b , h ) : g > h and g − h has a prime-power divisor greater than z } . G_{\mathrm{nsm}}(x;b,h;z):=\#\{g\in\mathcal{G}(x;b,h):g>h\text{ and }g-h\text{ has a prime-power divisor greater than }z\}. G nsm ( x ; b , h ; z ) := # { g ∈ G ( x ; b , h ) : g > h and g − h has a prime-power divisor greater than z } . Theorem 1.5. Fix A > 0 A > 0 A > 0 For all sufficiently large x x x all integers h ≠ 0 h\ne0 h = 0 with ∣ h ∣ ≤ x 0.01 |h|\le x^{0.01} ∣ h ∣ ≤ x 0.01 and all 1 ≤ b ≤ ( log x ) A 1\le b\le(\log x)^A 1 ≤ b ≤ ( log x ) A such that ( b , h ) = 1 (b,h)=1 ( b , h ) = 1 and ( b , h − 1 ) (b,h-1) ( b , h − 1 )
G n s m ( x ; b , h ; x 0.99 ) ≤ ( 0.259 + o ( 1 ) ) x ϕ ( b ) log x log log x ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . G_{\mathrm{nsm}}(x;b,h;x^{0.99})\le(0.259+o(1))\frac{x}{\phi(b)\log x\log\log x}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. G nsm ( x ; b , h ; x 0.99 ) ≤ ( 0.259 + o ( 1 )) ϕ ( b ) log x log log x x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . where the o ( 1 ) o(1) o ( 1 ) term depends on A A A
A comparison with Theorem 1.4 shows that at most about 26% of the Golomb primes g ≤ x g\le x g ≤ x g ≡ h ( m o d b ) g\equiv h\pmod b g ≡ h ( mod b ) g − h g-h g − h x 0.99 x^{0.99} x 0.99 h h h Theorem 3.2 ).
The main difficulty in proving Theorem 1.3 is that the Golomb primes are sparse and that little is known about them beyond Erdős’ result, Theorem 1.2. Theorems 1.4 and 1.5 let us find subsets of shifted Golomb primes to which a proposition of the kind introduced by Croot [8 ] applies. Because the Golomb primes are sparse, the shifted Golomb primes in a single interval ( N 0.997 , N ] (N^{0.997},N] ( N 0.997 , N ] 1 / log log N 1/\log\log N 1/ log log N log log N \log\log N log log N P P P b b b
Acknowledgements
The author thanks her advisors Giorgis Petridis and Paul Pollack for many helpful discussions and their constant encouragement. The author was supported by NSF DMS Award 2054214.
Use of AI statement
The author used Claude Fable 5.1 and Claude Opus 5.5 to check the mathematical arguments for errors and gaps, and to proofread the paper. Apart from one suggestion by Fable 5.1, described below, all proof ideas are the author’s own.
The author originally planned to use [22 Proposition 5.2] in place of Proposition 6.1 . While writing the paper, she found that the argument needs condition (iii) of Proposition 6.1 with a smaller value of η \eta η [22 Proposition 5.2] allows. She asked Fable 5.1 whether the proof of [22 Proposition 5.2] could be adapted to give the smaller value. It replied that the improvement does not follow directly, and suggested combining Bloom’s treatment of the minor arcs [1 ] with the fact that the set A A A Proposition 6.1 is in Appendix § 7 . The author has checked all proofs and takes full responsibility for the content of the paper.
Notation and outline of the proof
Notation
We use the following notation.
We use P \mathcal{P} P P ( x ) \mathcal{P}(x) P ( x ) ≤ x \leq x ≤ x P ( x ; b , h ) \mathcal{P}(x;b,h) P ( x ; b , h ) ≤ x \leq x ≤ x h h h b b b
We use G \mathcal{G} G G ( x ) \mathcal{G}(x) G ( x ) ≤ x \leq x ≤ x G ( x ; b , h ) \mathcal{G}(x;b,h) G ( x ; b , h ) ≤ x \leq x ≤ x h h h b b b
An h h h g − h g-h g − h g ∈ G g\in\mathcal{G} g ∈ G n n n n n n
We follow the convention that ( b , 0 ) = b (b,0)=b ( b , 0 ) = b n n n 0 0 0
For a finite set A A A
R ( A ) : = ∑ n ∈ A 1 n . R(A):=\sum_{n\in A}\frac{1}{n}. R ( A ) := n ∈ A ∑ n 1 . For a prime power q q q q ∥ n q\mathbin{\|}n q ∥ n q ∣ n q\mid n q ∣ n ( q , n / q ) = 1 (q,n/q)=1 ( q , n / q ) = 1
A q : = { n ∈ A : q ∥ n } and R ( A ; q ) : = ∑ n ∈ A q q n . A_q:=\{n\in A:q\mathbin{\|}n\}\qquad\text{and}\qquad R(A;q):=\sum_{n\in A_q}\frac{q}{n}. A q := { n ∈ A : q ∥ n } and R ( A ; q ) := n ∈ A q ∑ n q . We write Q A Q_A Q A q q q q ∥ n q\mathbin{\|}n q ∥ n n ∈ A n\in A n ∈ A [ D ] [D] [ D ] D D D [1 ] and is used mainly in § 6 and Appendix § 7 .
ω ( n ) \omega(n) ω ( n ) n n n l l l ν l ( n ) \nu_l(n) ν l ( n ) l l l n n n k k k l k ∣ n l^k\mid n l k ∣ n e ( θ ) = e 2 π i θ e(\theta)=e^{2\pi i\theta} e ( θ ) = e 2 π i θ ∥ θ ∥ \|\theta\| ∥ θ ∥ θ \theta θ
log k \log_k log k k k k log 2 x = log log x \log_2 x=\log\log x log 2 x = log log x log 3 x = log log log x \log_3 x=\log\log\log x log 3 x = log log log x Li ( x ) : = ∫ 2 x d t log t \operatorname{Li}(x):=\int_2^x\frac{dt}{\log t} Li ( x ) := ∫ 2 x l o g t d t
Unless stated otherwise, p p p r r r l l l g g g q q q § 6 and Appendix § 7 , q q q
We use standard asymptotic notation. For quantities X X X Y Y Y Y > 0 Y>0 Y > 0 X = O ( Y ) X=O(Y) X = O ( Y ) X ≪ Y X\ll Y X ≪ Y ∣ X ∣ ≤ C Y |X|\leq CY ∣ X ∣ ≤ C Y C > 0 C>0 C > 0 X ≍ Y X\asymp Y X ≍ Y X = Θ ( Y ) X=\Theta(Y) X = Θ ( Y ) X ≪ Y X\ll Y X ≪ Y Y ≪ X Y\ll X Y ≪ X X = o ( Y ) X=o(Y) X = o ( Y ) X / Y → 0 X/Y\to0 X / Y → 0 O h O_h O h ≪ A \ll_A ≪ A
Outline of the proof of Theorem 1.3
The proofs in [1 , 2 , 22 ] all rely on a proposition of the kind introduced by Croot [8 ] . Roughly speaking, it says the following. Let A ⊆ ( M , N ] A \subseteq(M,N] A ⊆ ( M , N ] Q = lcm ( A ) Q = \operatorname{lcm}(A) Q = lcm ( A )
x Q = ∑ 1 ≤ i ≤ k 1 n i \frac{x}{Q}=\sum_{1\leq i\leq k}\frac{1}{n_i} Q x = 1 ≤ i ≤ k ∑ n i 1 has a solution in distinct n 1 , … , n k ∈ A n_1,\ldots,n_k\in A n 1 , … , n k ∈ A
Every n ∈ A n\in A n ∈ A n n n N 0.99 N^{0.99} N 0.99
Every n ∈ A n\in A n ∈ A log log n \log\log n log log n
Every prime power dividing Q Q Q A A A
x / Q x/Q x / Q ∑ n ∈ A 1 / n \sum_{n\in A}1/n ∑ n ∈ A 1/ n
The precise version we use is Proposition 6.1. Applying it to the h h h
The first is to find subsets of shifted Golomb primes satisfying the hypotheses of the proposition, as not much is known about the arithmetic of Golomb primes beyond the estimates of Erdős [12 ] recalled in Theorem 1.2 . We therefore prove two new results: a Siegel–Walfisz-type theorem for Golomb primes in arithmetic progressions (Theorem 1.4) in Section 4, and an upper bound for the number of h h h
The second difficulty is that shifted Golomb primes are too sparse for a single application of the proposition to suffice. In the earlier works [1 , 2 , 8 , 22 ] , it is enough to apply the proposition to a suitable set in one interval [ M , N ] [M,N] [ M , N ] A ⊆ ( M , N ] A\subseteq(M,N] A ⊆ ( M , N ] M ≥ N 0.997 M\geq N^{0.997} M ≥ N 0.997 h h h 1 / log 2 N 1/\log^2 N 1/ log 2 N Lemma 6.2 ). For large N N N a / b a/b a / b
Instead, we split the h h h J ≍ log 2 N J\asymp\log^2 N J ≍ log 2 N ( N j + 1 , N j ] (N_{j+1},N_j] ( N j + 1 , N j ] N j + 1 = N j e − 0.003 N_{j+1}=N_j e^{-0.003} N j + 1 = N j e − 0.003 j j j A j A_j A j P P P ( log 2 N ) 2 (\log^2 N)^2 ( log 2 N ) 2 b ∣ P b\mid P b ∣ P P ∣ lcm ( A j ) P\mid\operatorname{lcm}(A_j) P ∣ lcm ( A j ) j j j Lemma 6.6 ). We need this to apply Proposition 6.1 to represent a suitable fraction y j / P y_j/P y j / P b ∣ P b\mid P b ∣ P y j y_j y j
∑ j = 1 J y j P = a b . \sum_{j=1}^{J}\frac{y_j}{P}=\frac{a}{b}. j = 1 ∑ J P y j = b a . The intervals are disjoint, so adding these representations gives a representation of a / b a/b a / b g − h g-h g − h
Some technical estimates
This section collects some tools we use in the rest of the paper. We first recall two elementary estimates of Mertens which we use several times:
∑ p k ≤ X 1 p k = log log X + c + O ( 1 log X ) for some constant c , (5) \sum_{p^k\leq X}\frac{1}{p^k}=\log\log X+c+O\left(\frac{1}{\log X}\right)\quad\text{for some constant }c, \tag*{(5)} p k ≤ X ∑ p k 1 = log log X + c + O ( log X 1 ) for some constant c , (5) and
∏ p ≤ X ( 1 − 1 p ) − 1 = ( e γ + o ( 1 ) ) log X . (6) \prod_{p\leq X}\left(1-\frac{1}{p}\right)^{-1}=(e^\gamma+o(1))\log X. \tag*{(6)} p ≤ X ∏ ( 1 − p 1 ) − 1 = ( e γ + o ( 1 )) log X . (6) Here the sum in (5) runs over prime powers p k p^k p k (6) runs over primes p p p
We also use the Bombieri–Vinogradov theorem [4 , 32 ] . For ( a , q ) = 1 (a,q)=1 ( a , q ) = 1 π ( x ; q , a ) \pi(x;q,a) π ( x ; q , a ) p ≤ x p\leq x p ≤ x p ≡ a ( m o d q ) p\equiv a\pmod q p ≡ a ( mod q )
E ( x ; q , a ) : = π ( x ; q , a ) − Li ( x ) ϕ ( q ) . E(x;q,a):=\pi(x;q,a)-\frac{\operatorname{Li}(x)}{\phi(q)}. E ( x ; q , a ) := π ( x ; q , a ) − ϕ ( q ) Li ( x ) . In the form given in [9 Chapter 28] , combined with partial summation, the theorem states that for every fixed A > 0 A>0 A > 0
∑ q ≤ x 1 / 2 / ( log x ) A + 8 max ( a , q ) = 1 ∣ E ( x ; q , a ) ∣ ≪ A x ( log x ) A + 3 . (7) \sum_{q\leq x^{1/2}/(\log x)^{A+8}}\max_{\substack{(a,q)=1}}|E(x;q,a)|\ll_A\frac{x}{(\log x)^{A+3}}. \tag*{(7)} q ≤ x 1/2 / ( l o g x ) A + 8 ∑ ( a , q ) = 1 max ∣ E ( x ; q , a ) ∣ ≪ A ( log x ) A + 3 x . (7) Next, we state a result for the sum of the reciprocals of the Golomb primes in an interval ( y , x ] (y,x] ( y , x ]
Lemma 3.1. For 3 ≤ y < x 3\leq y<x 3 ≤ y < x
∑ q ∈ G y < q ≤ x 1 q = ( 1 + o ( 1 ) ) ( log 3 x − log 3 y ) + O ( 1 log y log 2 y ) . \sum_{\substack{q\in\mathcal{G}\\y<q\leq x}}\frac{1}{q}=(1+o(1))(\log_3 x-\log_3 y)+O\left(\frac{1}{\log y\log_2 y}\right). q ∈ G y < q ≤ x ∑ q 1 = ( 1 + o ( 1 )) ( log 3 x − log 3 y ) + O ( log y log 2 y 1 ) . where the o ( 1 ) o(1) o ( 1 ) 0 0 0 y → ∞ y\to\infty y → ∞
Proof. By partial summation and Theorem 1.2, we have
∑ q ∈ G y < q ≤ x 1 q = x ( 1 + o ( 1 ) ) x log x log 2 x − y ( 1 + o ( 1 ) ) y log y log 2 y + ∫ y x 1 + o ( 1 ) u log u log 2 u d u . \sum_{\substack{q\in\mathcal{G}\\y<q\leq x}}\frac{1}{q}
=\frac{x(1+o(1))}{x\log x\log_2 x}-\frac{y(1+o(1))}{y\log y\log_2 y}+\int_y^x\frac{1+o(1)}{u\log u\log_2 u}\,du. q ∈ G y < q ≤ x ∑ q 1 = x log x log 2 x x ( 1 + o ( 1 )) − y log y log 2 y y ( 1 + o ( 1 )) + ∫ y x u log u log 2 u 1 + o ( 1 ) d u . Since
∫ y x d u u log u log 2 u = log 3 x − log 3 y , \int_y^x\frac{du}{u\log u\log_2 u}=\log_3 x-\log_3 y, ∫ y x u log u log 2 u d u = log 3 x − log 3 y , this gives
∑ q ∈ G y < q ≤ x 1 q = ( 1 + o ( 1 ) ) ( log 3 x − log 3 y ) + O ( 1 log y log 2 y ) . \sum_{\substack{q\in\mathcal{G}\\y<q\leq x}}\frac{1}{q}=(1+o(1))(\log_3 x-\log_3 y)+O\left(\frac{1}{\log y\log_2 y}\right). q ∈ G y < q ≤ x ∑ q 1 = ( 1 + o ( 1 )) ( log 3 x − log 3 y ) + O ( log y log 2 y 1 ) . We also need three sieve estimates, which we use in § 4 , § 5 and in Appendix § 7 .
Theorem 3.2 (Fundamental lemma of sieve theory; [21 Theorem 18.11] ). Let A \mathcal{A} A P \mathcal{P} P P ( z ) P(z) P ( z ) p ∈ P p\in\mathcal{P} p ∈ P p < z p<z p < z S ( A , P , z ) = ∣ A ∖ ⋃ p ∣ P ( z ) A p ∣ S(\mathcal{A},\mathcal{P},z)=\left|\mathcal{A}\setminus\bigcup_{p\mid P(z)}\mathcal{A}_p\right| S ( A , P , z ) = A ∖ ⋃ p ∣ P ( z ) A p A d \mathcal{A}_d A d d d d A \mathcal{A} A
(1) There exist a multiplicative function w w w X X X r d r_d r d d ∣ P ( z ) d\mid P(z) d ∣ P ( z )
∣ A d ∣ = w ( d ) d X + r d for all d ∣ P ( z ) , and w ( p ) < p for all p ∣ P ( z ) . |\mathcal{A}_d|=\frac{w(d)}{d}X+r_d\quad\text{for all }d\mid P(z),\qquad\text{and}\qquad w(p)<p\quad\text{for all }p\mid P(z). ∣ A d ∣ = d w ( d ) X + r d for all d ∣ P ( z ) , and w ( p ) < p for all p ∣ P ( z ) . (2) There are constants κ ≥ 0 \kappa\geq0 κ ≥ 0 C ≥ 0 C\geq0 C ≥ 0
∏ p ∈ P y 1 < p ≤ y 2 ( 1 − w ( p ) p ) − 1 ≤ ( 1 + C log y 1 ) ( log y 2 log y 1 ) κ \prod_{\substack{p\in\mathcal{P}\\y_1<p\leq y_2}}\left(1-\frac{w(p)}{p}\right)^{-1}\leq\left(1+\frac{C}{\log y_1}\right)\left(\frac{\log y_2}{\log y_1}\right)^\kappa p ∈ P y 1 < p ≤ y 2 ∏ ( 1 − p w ( p ) ) − 1 ≤ ( 1 + log y 1 C ) ( log y 1 log y 2 ) κ uniformly for 3 2 ≤ y 1 ≤ y 2 ≤ z \frac{3}{2}\leq y_1\leq y_2\leq z 2 3 ≤ y 1 ≤ y 2 ≤ z
Then, uniformly for all u ≥ 1 u \ge1 u ≥ 1
S ( A , P , z ) = X ∏ p < z p ∈ P ( 1 − w ( p ) p ) ( 1 + O κ , C ( u − u / 2 ) ) + O ( ∑ d ≤ z u d ∣ P ( z ) ∣ r d ∣ ) . S(\mathcal{A},\mathcal{P},z) = X \prod_{\substack{p<z\\p\in\mathcal{P}}} \left(1-\frac{w(p)}{p}\right)\left(1+O_{\kappa,C}(u^{-u/2})\right)+O\left(\sum_{\substack{d\le z^u\\d\mid P(z)}}|r_d|\right). S ( A , P , z ) = X p < z p ∈ P ∏ ( 1 − p w ( p ) ) ( 1 + O κ , C ( u − u /2 ) ) + O d ≤ z u d ∣ P ( z ) ∑ ∣ r d ∣ . We also use the following form of the fundamental lemma for the Selberg sieve, which is stated in [19 Theorem 7.2] . This can be proved using Theorem 3.2 , but this form is more convenient.
Theorem 3.3 (Selberg sieve). Let A \mathcal{A} A P \mathcal{P} P P ( z ) P(z) P ( z ) p ∈ P p\in\mathcal{P} p ∈ P p < z p<z p < z S ( A , P , z ) = ∣ A ∖ ⋃ p ∣ P ( z ) A p ∣ S(\mathcal{A},\mathcal{P},z)=|\mathcal{A}\setminus\bigcup_{p\mid P(z)}\mathcal{A}_p| S ( A , P , z ) = ∣ A ∖ ⋃ p ∣ P ( z ) A p ∣ ∣ A d ∣ = w ( d ) d X + R d |\mathcal{A}_d|=\frac{w(d)}{d}X+R_d ∣ A d ∣ = d w ( d ) X + R d d ∣ P ( z ) d\mid P(z) d ∣ P ( z ) w w w
(1) 0 ≤ w ( p ) p ≤ 1 − c 0\le\frac{w(p)}{p}\le1-c 0 ≤ p w ( p ) ≤ 1 − c c > 0 c>0 c > 0
(2) ∣ R d ∣ ≤ w ( d ) |R_d|\le w(d) ∣ R d ∣ ≤ w ( d ) d ∣ P ( z ) d\mid P(z) d ∣ P ( z )
(3) ∑ y ≤ p ≤ z p ∈ P w ( p ) log p p ≤ κ log ( z y ) + A 2 \sum_{\substack{y\le p\le z\\p\in\mathcal{P}}}\frac{w(p)\log p}{p}\le\kappa\log\left(\frac{z}{y}\right)+A_2 ∑ y ≤ p ≤ z p ∈ P p w ( p ) l o g p ≤ κ log ( y z ) + A 2 2 ≤ y ≤ z 2\le y\le z 2 ≤ y ≤ z κ \kappa κ A 2 A_2 A 2
If, in addition, X ≥ z X\ge z X ≥ z
S ( A , P , z ) = X ∏ p < z p ∈ P ( 1 − w ( p ) p ) ( 1 + O ( exp ( − log X 2 log z ) ) ) . S(\mathcal{A},\mathcal{P},z)=X\prod_{\substack{p<z\\p\in\mathcal{P}}}\left(1-\frac{w(p)}{p}\right)\left(1+O\left(\exp\left(-\frac{\log X}{2\log z}\right)\right)\right). S ( A , P , z ) = X p < z p ∈ P ∏ ( 1 − p w ( p ) ) ( 1 + O ( exp ( − 2 log z log X ) ) ) . In Theorems 3.2 and 3.3 , A p \mathcal{A}_p A p n ∈ A n\in\mathcal{A} n ∈ A p ∣ n p\mid n p ∣ n p ∣ P ( z ) p\mid P(z) p ∣ P ( z ) A \mathcal{A} A p p p [28 Lemma 2.4] .
Observation 3.4. Let A \mathcal{A} A P \mathcal{P} P P ( z ) P(z) P ( z ) Theorem 3.2 . For each prime p ∣ P ( z ) p\mid P(z) p ∣ P ( z ) A \mathcal{A} A w ( p ) ≥ 1 w(p)\ge1 w ( p ) ≥ 1 p p p d ∣ P ( z ) d\mid P(z) d ∣ P ( z ) B d \mathcal{B}_d B d n ∈ A n\in\mathcal{A} n ∈ A p ∣ d p\mid d p ∣ d k = max p ∣ P ( z ) w ( p ) k=\max_{p\mid P(z)}w(p) k = max p ∣ P ( z ) w ( p ) p p p a p , 1 , a p , 2 , … , a p , k a_{p,1},a_{p,2},\ldots,a_{p,k} a p , 1 , a p , 2 , … , a p , k w ( p ) < k w(p)<k w ( p ) < k a 1 , … , a k ≤ 0 a_1,\ldots,a_k\le0 a 1 , … , a k ≤ 0 a i ≡ a p , i ( m o d p ) a_i\equiv a_{p,i}\pmod p a i ≡ a p , i ( mod p ) i i i p ∣ P ( z ) p\mid P(z) p ∣ P ( z )
F ( T ) = ∏ i = 1 k ( T − a i ) and A ~ = { F ( n ) : n ∈ A } . F(T)=\prod_{i=1}^{k}(T-a_i)\qquad\text{and}\qquad\widetilde{\mathcal{A}}=\{F(n):n\in\mathcal{A}\}. F ( T ) = i = 1 ∏ k ( T − a i ) and A = { F ( n ) : n ∈ A } . Since each factor n − a i n-a_i n − a i n n n F F F A \mathcal{A} A p ∣ P ( z ) p\mid P(z) p ∣ P ( z ) p ∣ F ( n ) p\mid F(n) p ∣ F ( n ) n ≡ a p , i ( m o d p ) n\equiv a_{p,i}\pmod p n ≡ a p , i ( mod p ) i i i n n n p p p d ∣ P ( z ) d\mid P(z) d ∣ P ( z ) ∣ B d ∣ |\mathcal{B}_d| ∣ B d ∣ A ~ \widetilde{\mathcal{A}} A d d d ∣ A ∖ ⋃ p ∣ P ( z ) B p ∣ |\mathcal{A}\setminus\bigcup_{p\mid P(z)}\mathcal{B}_p| ∣ A ∖ ⋃ p ∣ P ( z ) B p ∣ A ~ \widetilde{\mathcal{A}} A P ( z ) P(z) P ( z ) Theorems 3.2 and 3.3 to A ~ \widetilde{\mathcal{A}} A B d \mathcal{B}_d B d d d d A \mathcal{A} A
In the rest of the paper we use Theorems 3.2 and 3.3 in this form. We abuse notation and write A d \mathcal{A}_d A d S ( A , P , z ) S(\mathcal{A},\mathcal{P},z) S ( A , P , z ) B d \mathcal{B}_d B d S ( A ~ , P , z ) S(\widetilde{\mathcal{A}},\mathcal{P},z) S ( A , P , z ) [10 Theorem 5.6] .
Lemma 3.5. Let x x x z = x 1 / 4 ( log x ) 100 z = \frac{x^{1/4}}{(\log x)^{100}} z = ( l o g x ) 100 x 1/4 r ≤ z r \le z r ≤ z p ≤ x p \le x p ≤ x w ( r ) w(r) w ( r ) r r r r r r w ( r ) ≤ min { 2 , r − 2 } w(r) \le\min\{2,r-2\} w ( r ) ≤ min { 2 , r − 2 }
2 e 2 γ x ( 1 + o ( 1 ) ) log x ∏ r ≤ z ( 1 − w ( r ) r − 1 ) . \frac{2e^{2\gamma}x(1+o(1))}{\log x}\prod_{r\le z}\left(1-\frac{w(r)}{r-1}\right). log x 2 e 2 γ x ( 1 + o ( 1 )) r ≤ z ∏ ( 1 − r − 1 w ( r ) ) . Proof. Let A \mathcal{A} A p ≤ x p \le x p ≤ x P \mathcal{P} P z = x 1 / 4 ( log x ) 100 z = \frac{x^{1/4}}{(\log x)^{100}} z = ( l o g x ) 100 x 1/4 A p \mathcal{A}_p A p A \mathcal{A} A w ( p ) w(p) w ( p ) p p p n ∣ P ( z ) n \mid P(z) n ∣ P ( z ) A n \mathcal{A}_n A n ≤ x \le x ≤ x w ( n ) w(n) w ( n ) n n n n n n
∣ A n ∣ = w ( n ) ϕ ( n ) Li ( x ) + r A ( n ) , |\mathcal{A}_n|=\frac{w(n)}{\phi(n)}\operatorname{Li}(x)+r_{\mathcal{A}}(n), ∣ A n ∣ = ϕ ( n ) w ( n ) Li ( x ) + r A ( n ) , where r A ( n ) r_{\mathcal{A}}(n) r A ( n ) E ( x ; n , a ) E(x;n,a) E ( x ; n , a ) w ( n ) w(n) w ( n ) a a a E ( x ; n , a ) E(x;n,a) E ( x ; n , a ) (7) . Since w ( n ) ≤ 2 ω ( n ) w(n)\le2^{\omega(n)} w ( n ) ≤ 2 ω ( n )
∣ r A ( n ) ∣ ≤ 2 ω ( n ) E ( x ; n ) , where E ( x ; n ) : = max ( a , n ) = 1 ∣ E ( x ; n , a ) ∣ . |r_{\mathcal{A}}(n)|\le2^{\omega(n)}E(x;n),\qquad\text{where}\qquad E(x;n):=\max_{\substack{(a,n)=1}}|E(x;n,a)|. ∣ r A ( n ) ∣ ≤ 2 ω ( n ) E ( x ; n ) , where E ( x ; n ) := ( a , n ) = 1 max ∣ E ( x ; n , a ) ∣. We check the conditions and apply [10 Theorem 5.6] to the set A \mathcal{A} A X = Li ( x ) X=\operatorname{Li}(x) X = Li ( x ) q = 1 q=1 q = 1 u = 1 u=1 u = 1 z = x 1 / 4 / ( log x ) 100 z=x^{1/4}/(\log x)^{100} z = x 1/4 / ( log x ) 100
S ( A , P , z ) ≤ Li ( x ) ∏ r ≤ z ( 1 − w ( r ) r − 1 ) { 2 e 2 γ + O ( log 2 x log x ) } + ∑ n < z 2 n ∣ P ( z ) 3 ω ( n ) ∣ r A ( n ) ∣ . S(\mathcal{A},\mathcal{P},z)\le\operatorname{Li}(x)\prod_{r\le z}\left(1-\frac{w(r)}{r-1}\right)\left\{2e^{2\gamma}+O\left(\frac{\log^2 x}{\log x}\right)\right\}+\sum_{\substack{n<z^2\\n\mid P(z)}}3^{\omega(n)}|r_{\mathcal{A}}(n)|. S ( A , P , z ) ≤ Li ( x ) r ≤ z ∏ ( 1 − r − 1 w ( r ) ) { 2 e 2 γ + O ( log x log 2 x ) } + n < z 2 n ∣ P ( z ) ∑ 3 ω ( n ) ∣ r A ( n ) ∣. We bound the last sum using the Cauchy–Schwarz inequality:
∑ n < z 2 n ∣ P ( z ) 3 ω ( n ) ∣ r A ( n ) ∣ ≤ ∑ n < z 2 n ∣ P ( z ) 6 ω ( n ) E ( x ; n ) ≤ ( ∑ n < z 2 n ∣ P ( z ) 36 ω ( n ) E ( x ; n ) ) 1 / 2 ( ∑ n < z 2 n ∣ P ( z ) E ( x ; n ) ) 1 / 2 . \sum_{\substack{n<z^2\\n\mid P(z)}}3^{\omega(n)}|r_{\mathcal{A}}(n)|\le\sum_{\substack{n<z^2\\n\mid P(z)}}6^{\omega(n)}E(x;n)\le\left(\sum_{\substack{n<z^2\\n\mid P(z)}}36^{\omega(n)}E(x;n)\right)^{1/2}\left(\sum_{\substack{n<z^2\\n\mid P(z)}}E(x;n)\right)^{1/2}. n < z 2 n ∣ P ( z ) ∑ 3 ω ( n ) ∣ r A ( n ) ∣ ≤ n < z 2 n ∣ P ( z ) ∑ 6 ω ( n ) E ( x ; n ) ≤ n < z 2 n ∣ P ( z ) ∑ 3 6 ω ( n ) E ( x ; n ) 1/2 n < z 2 n ∣ P ( z ) ∑ E ( x ; n ) 1/2 . Since z 2 = x 1 / 2 / ( log x ) 200 z^2=x^{1/2}/(\log x)^{200} z 2 = x 1/2 / ( log x ) 200 (7) gives
∑ n < z 2 n ∣ P ( z ) E ( x ; n ) ≤ ∑ n ≤ x 1 / 2 / ( log x ) 200 max ( a , n ) = 1 ∣ E ( x ; n , a ) ∣ ≪ x ( log x ) 195 , \sum_{\substack{n<z^2\\n\mid P(z)}}E(x;n)\le\sum_{n\le x^{1/2}/(\log x)^{200}}\max_{\substack{(a,n)=1}}|E(x;n,a)|\ll\frac{x}{(\log x)^{195}}, n < z 2 n ∣ P ( z ) ∑ E ( x ; n ) ≤ n ≤ x 1/2 / ( l o g x ) 200 ∑ ( a , n ) = 1 max ∣ E ( x ; n , a ) ∣ ≪ ( log x ) 195 x , so the second factor is O ( x 1 / 2 / ( log x ) 97 ) O(x^{1/2}/(\log x)^{97}) O ( x 1/2 / ( log x ) 97 ) E ( x ; n ) ≪ x / ϕ ( n ) E(x;n)\ll x/\phi(n) E ( x ; n ) ≪ x / ϕ ( n )
( ∑ n < z 2 n ∣ P ( z ) 36 ω ( n ) E ( x ; n ) ) 1 / 2 ≪ x 1 / 2 ( ∑ n < z 2 n ∣ P ( z ) 36 ω ( n ) ϕ ( n ) ) 1 / 2 ≪ x 1 / 2 ( ∏ p ≤ z ( 1 + 36 p − 1 ) ) 1 / 2 ≪ x 1 / 2 ( log x ) 18 . \left(\sum_{\substack{n<z^2\\n\mid P(z)}}36^{\omega(n)}E(x;n)\right)^{1/2}\ll x^{1/2}\left(\sum_{\substack{n<z^2\\n\mid P(z)}}\frac{36^{\omega(n)}}{\phi(n)}\right)^{1/2}\ll x^{1/2}\left(\prod_{p\le z}\left(1+\frac{36}{p-1}\right)\right)^{1/2}\ll x^{1/2}(\log x)^{18}. n < z 2 n ∣ P ( z ) ∑ 3 6 ω ( n ) E ( x ; n ) 1/2 ≪ x 1/2 n < z 2 n ∣ P ( z ) ∑ ϕ ( n ) 3 6 ω ( n ) 1/2 ≪ x 1/2 ( p ≤ z ∏ ( 1 + p − 1 36 ) ) 1/2 ≪ x 1/2 ( log x ) 18 . So the total error is O ( x / ( log x ) 79 ) O(x/(\log x)^{79}) O ( x / ( log x ) 79 ) ∏ r ≤ z ( 1 − w ( r ) r − 1 ) ≫ ( log x ) − 2 \prod_{r\le z}\left(1-\frac{w(r)}{r-1}\right)\gg(\log x)^{-2} ∏ r ≤ z ( 1 − r − 1 w ( r ) ) ≫ ( log x ) − 2 Li ( x ) = ( 1 + o ( 1 ) ) x / log x \operatorname{Li}(x)=(1+o(1))x/\log x Li ( x ) = ( 1 + o ( 1 )) x / log x
S ( A , P , z ) ≤ 2 e 2 γ x ( 1 + o ( 1 ) ) log x ∏ r ≤ z ( 1 − w ( r ) r − 1 ) , S(\mathcal{A},\mathcal{P},z)\le\frac{2e^{2\gamma}x(1+o(1))}{\log x}\prod_{r\le z}\left(1-\frac{w(r)}{r-1}\right), S ( A , P , z ) ≤ log x 2 e 2 γ x ( 1 + o ( 1 )) r ≤ z ∏ ( 1 − r − 1 w ( r ) ) , which is the claimed bound.
Golomb primes in arithmetic progressions: proof of Theorem 1.4
In this section we prove Theorem 1.4, which we restate here.
Theorem 1.4 (Golomb primes in arithmetic progressions). Fix A > 0 A > 0 A > 0 1 ≤ b ≤ ( log x ) A 1 \le b \le(\log x)^A 1 ≤ b ≤ ( log x ) A h ∈ Z h \in\mathbb{Z} h ∈ Z ( b , h ) = 1 (b,h)=1 ( b , h ) = 1 ( b , h − 1 ) (b,h-1) ( b , h − 1 )
∣ G ( x ; b , h ) ∣ = ( 1 + o ( 1 ) ) x ϕ ( b ) log x log log x ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . \lvert G(x;b,h)\rvert=(1+o(1))\frac{x}{\phi(b)\log x\log\log x}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. ∣ G ( x ; b , h )∣ = ( 1 + o ( 1 )) ϕ ( b ) log x log log x x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . where the o ( 1 ) o(1) o ( 1 ) A A A
Recall that P \mathcal{P} P P ( x ; b , h ) \mathcal{P}(x;b,h) P ( x ; b , h ) p ≤ x p\le x p ≤ x p ≡ h ( m o d b ) p\equiv h\pmod b p ≡ h ( mod b ) G ( x ; b , h ) \mathcal{G}(x;b,h) G ( x ; b , h ) g ≤ x g\le x g ≤ x g ≡ h ( m o d b ) g\equiv h\pmod b g ≡ h ( mod b ) r r r l l l g g g q q q
To estimate ∣ G ( x ; b , h ) ∣ \lvert\mathcal{G}(x;b,h)\rvert ∣ G ( x ; b , h )∣ P ( x ; b , h ) \mathcal{P}(x;b,h) P ( x ; b , h ) p ≡ 1 ( m o d q ) p\equiv1\pmod q p ≡ 1 ( mod q ) q q q q ≤ z 0 : = exp ( log x 3 log 3 x ) q\le z_0:=\exp\left(\frac{\log x}{3\log_3 x}\right) q ≤ z 0 := exp ( 3 l o g 3 x l o g x ) Theorem 3.2 ). We then show that the remaining Golomb primes z 0 < q ≤ x z_0<q\le x z 0 < q ≤ x
Let x x x 1 ≤ b ≤ ( log x ) A 1\le b\le(\log x)^A 1 ≤ b ≤ ( log x ) A Theorem 3.2 with
A = P ( x ; b , h ) , X = Li ( x ) ϕ ( b ) , P = { g ∈ G : g ∤ b } . \mathcal{A}=\mathcal{P}(x;b,h),\qquad X=\frac{\operatorname{Li}(x)}{\phi(b)},\qquad\mathcal{P}=\{g\in\mathcal{G}:g\nmid b\}. A = P ( x ; b , h ) , X = ϕ ( b ) Li ( x ) , P = { g ∈ G : g ∤ b } . Further, let u = log 3 x u=\log_3 x u = log 3 x z = z 0 = exp ( log x 3 log 3 x ) z=z_0=\exp\left(\frac{\log x}{3\log_3 x}\right) z = z 0 = exp ( 3 l o g 3 x l o g x ) E ( x ; q , a ) E(x;q,a) E ( x ; q , a ) § 3 . For squarefree d ∣ P ( z 0 ) d\mid P(z_0) d ∣ P ( z 0 ) ( d , b ) = 1 (d,b)=1 ( d , b ) = 1 h d ( m o d d b ) h_d\pmod{db} h d ( mod d b ) h d ≡ h ( m o d b ) h_d\equiv h\pmod b h d ≡ h ( mod b ) h d ≡ 1 ( m o d d ) h_d\equiv1\pmod d h d ≡ 1 ( mod d ) ( h , b ) = 1 (h,b)=1 ( h , b ) = 1 d b db d b
∣ A d ∣ = Li ( x ) ϕ ( d ) ϕ ( b ) + E ( x ; d b , h d ) . \lvert\mathcal{A}_d\rvert=\frac{\operatorname{Li}(x)}{\phi(d)\phi(b)}+E(x;db,h_d). ∣ A d ∣ = ϕ ( d ) ϕ ( b ) Li ( x ) + E ( x ; d b , h d ) . Thus, with w ( g ) g = 1 g − 1 \frac{w(g)}{g}=\frac{1}{g-1} g w ( g ) = g − 1 1 r d = E ( x ; d b , h d ) r_d=E(x;db,h_d) r d = E ( x ; d b , h d ) Theorem 3.2 are satisfied with κ = 1 \kappa=1 κ = 1 u − u / 2 ≤ ( log 2 x ) − 2 u^{-u/2}\le(\log_2x)^{-2} u − u /2 ≤ ( log 2 x ) − 2
S ( A , P , z 0 ) = Li ( x ) ϕ ( b ) ∏ g ∈ G ( z 0 ) g ∤ b ( 1 − 1 g − 1 ) ( 1 + O ( ( log 2 x ) − 2 ) ) + O ( ∑ d < z 0 u d ∣ P ( z 0 ) ∣ E ( x ; d b , h d ) ∣ ) . (8) S(\mathcal{A},\mathcal{P},z_0)=\frac{\operatorname{Li}(x)}{\phi(b)}
\prod_{\substack{g\in\mathcal{G}(z_0)\\g\nmid b}}\left(1-\frac{1}{g-1}\right)\left(1+O\left((\log_2x)^{-2}\right)\right)+O\left(\sum_{\substack{d<z_0^u\\d\mid P(z_0)}}\lvert E(x;db,h_d)\rvert\right). \tag*{(8)} S ( A , P , z 0 ) = ϕ ( b ) Li ( x ) g ∈ G ( z 0 ) g ∤ b ∏ ( 1 − g − 1 1 ) ( 1 + O ( ( log 2 x ) − 2 ) ) + O d < z 0 u d ∣ P ( z 0 ) ∑ ∣ E ( x ; d b , h d )∣ . (8) We now bound the error term. As d ≤ z 0 u = x 1 / 3 d\le z_0^u=x^{1/3} d ≤ z 0 u = x 1/3 d b ≤ x 1 / 3 ( log x ) A ≤ x 1 / 2 / ( log x ) A + 8 db\le x^{1/3}(\log x)^A\le x^{1/2}/(\log x)^{A+8} d b ≤ x 1/3 ( log x ) A ≤ x 1/2 / ( log x ) A + 8 (7) gives
S ( A , P , z 0 ) = ( 1 + o ( 1 ) ) Li ( x ) ϕ ( b ) ∏ g ∈ G ( z 0 ) g ∤ b ( 1 − 1 g − 1 ) + O ( x ( log x ) A + 3 ) . S(\mathcal{A},\mathcal{P},z_0)=(1+o(1))\frac{\operatorname{Li}(x)}{\phi(b)}
\prod_{\substack{g\in\mathcal{G}(z_0)\\g\nmid b}}\left(1-\frac{1}{g-1}\right)+O\left(\frac{x}{(\log x)^{A+3}}\right). S ( A , P , z 0 ) = ( 1 + o ( 1 )) ϕ ( b ) Li ( x ) g ∈ G ( z 0 ) g ∤ b ∏ ( 1 − g − 1 1 ) + O ( ( log x ) A + 3 x ) . Since ϕ ( b ) ≤ ( log x ) A \phi(b)\le(\log x)^A ϕ ( b ) ≤ ( log x ) A Theorem 1.2 and z 0 = exp ( log x 3 log 3 x ) z_0=\exp\left(\frac{\log x}{3\log_3x}\right) z 0 = exp ( 3 l o g 3 x l o g x )
∏ g ∈ G ( z 0 ) g ∤ b ( 1 − 1 g − 1 ) = 1 + o ( 1 ) log 2 x ∏ g ∈ G g ∤ b ( 1 − 1 g − 1 ) − 1 . \prod_{\substack{g\in\mathcal{G}(z_0)\\g\nmid b}}\left(1-\frac{1}{g-1}\right)=\frac{1+o(1)}{\log_2x}\prod_{\substack{g\in\mathcal{G}\\g\nmid b}}\left(1-\frac{1}{g-1}\right)^{-1}. g ∈ G ( z 0 ) g ∤ b ∏ ( 1 − g − 1 1 ) = log 2 x 1 + o ( 1 ) g ∈ G g ∤ b ∏ ( 1 − g − 1 1 ) − 1 . Since Li ( x ) = ( 1 + o ( 1 ) ) x log x \operatorname{Li}(x) = (1 + o(1)) \frac{x}{\log x} Li ( x ) = ( 1 + o ( 1 )) l o g x x
S ( A , P , z 0 ) = ( 1 + o ( 1 ) ) x ϕ ( b ) log x log 2 x ∏ g ∈ G g ∤ b ( 1 − 1 g − 1 ) − 1 . S(\mathcal{A},\mathcal{P},z_0) = (1 + o(1))\frac{x}{\phi(b)\log x\log_2 x}\prod_{\substack{g\in\mathcal{G}\\g\nmid b}}\left(1-\frac{1}{g-1}\right)^{-1}. S ( A , P , z 0 ) = ( 1 + o ( 1 )) ϕ ( b ) log x log 2 x x g ∈ G g ∤ b ∏ ( 1 − g − 1 1 ) − 1 . Note that S ( A , P , z 0 ) S(\mathcal{A},\mathcal{P},z_0) S ( A , P , z 0 ) p ≤ x p\le x p ≤ x p ≡ h ( m o d b ) p\equiv h\pmod b p ≡ h ( mod b ) p − 1 p-1 p − 1 g ≤ z 0 g\le z_0 g ≤ z 0 g ∤ b g\nmid b g ∤ b G ( x ; b , h ) \mathcal{G}(x;b,h) G ( x ; b , h ) S ( A , P , z 0 ) S(\mathcal{A},\mathcal{P},z_0) S ( A , P , z 0 ) ∣ G ( x ; b , h ) ∣ |\mathcal{G}(x;b,h)| ∣ G ( x ; b , h ) ∣ S ( A , P , z 0 ) S(\mathcal{A},\mathcal{P},z_0) S ( A , P , z 0 )
B ( x ; b , h ; q ) : = # { p ≤ x : p ≡ h ( m o d b ) , p ≡ 1 ( m o d q ) , p ≢ 1 ( m o d q ) for all q ∈ G ( z 0 ) } . B(x;b,h;q):=\#\{p\le x:p\equiv h\pmod b,\ p\equiv1\pmod q,\ p\not\equiv1\pmod q\text{ for all }q\in\mathcal{G}(z_0)\}. B ( x ; b , h ; q ) := # { p ≤ x : p ≡ h ( mod b ) , p ≡ 1 ( mod q ) , p ≡ 1 ( mod q ) for all q ∈ G ( z 0 )} . Every prime p ≠ 2 p\ne2 p = 2 S ( A , P , z 0 ) S(\mathcal{A},\mathcal{P},z_0) S ( A , P , z 0 ) B ( x ; b , h ; q ) B(x;b,h;q) B ( x ; b , h ; q ) q ∈ ( z 0 , x ] q\in(z_0,x] q ∈ ( z 0 , x ]
S ( A , P , z 0 ) − 1 − ∑ g ∈ G z 0 < g ≤ x B ( x ; b , h ; g ) ≤ ∣ G ( x ; b , h ) ∣ ≤ S ( A , P , z 0 ) . (9) S(\mathcal{A},\mathcal{P},z_0)-1-\sum_{\substack{g\in\mathcal{G}\\z_0<g\le x}}B(x;b,h;g)\le|\mathcal{G}(x;b,h)|\le S(\mathcal{A},\mathcal{P},z_0). \tag*{(9)} S ( A , P , z 0 ) − 1 − g ∈ G z 0 < g ≤ x ∑ B ( x ; b , h ; g ) ≤ ∣ G ( x ; b , h ) ∣ ≤ S ( A , P , z 0 ) . (9) We split the range of g g g t = x exp ( − log x ( log 2 x ) 4 / 5 ) t=x\exp\left(-\frac{\log x}{(\log_2 x)^{4/5}}\right) t = x exp ( − ( l o g 2 x ) 4/5 l o g x ) g g g (9) using the following two lemmas.
Lemma 4.1. For z 0 = exp ( log x 3 log 3 x ) z_0=\exp\left(\frac{\log x}{3\log_3 x}\right) z 0 = exp ( 3 l o g 3 x l o g x ) t = x exp ( − log x ( log 2 x ) 4 / 5 ) t=x\exp\left(-\frac{\log x}{(\log_2 x)^{4/5}}\right) t = x exp ( − ( l o g 2 x ) 4/5 l o g x )
∑ g ∈ G z 0 < g ≤ t B ( x ; b , h ; g ) ≪ x log 4 x ϕ ( b ) log x ( log 2 x ) 6 / 5 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . \sum_{\substack{g\in\mathcal{G}\\z_0<g\le t}}B(x;b,h;g)\ll\frac{x\log_4 x}{\phi(b)\log x(\log_2 x)^{6/5}}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. g ∈ G z 0 < g ≤ t ∑ B ( x ; b , h ; g ) ≪ ϕ ( b ) log x ( log 2 x ) 6/5 x log 4 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . Lemma 4.2. For t = x exp ( − log x ( log 2 x ) 4 / 5 ) t=x\exp\left(-\frac{\log x}{(\log_2 x)^{4/5}}\right) t = x exp ( − ( l o g 2 x ) 4/5 l o g x )
∑ g ∈ G t < g ≤ x B ( x ; b , h ; g ) ≪ x ( log 3 x ) 3 ϕ ( b ) log x ( log 2 x ) 2 . \sum_{\substack{g\in\mathcal{G}\\t<g\le x}}B(x;b,h;g)\ll\frac{x(\log_3 x)^3}{\phi(b)\log x(\log_2 x)^2}. g ∈ G t < g ≤ x ∑ B ( x ; b , h ; g ) ≪ ϕ ( b ) log x ( log 2 x ) 2 x ( log 3 x ) 3 . We first assume the lemmas and deduce Theorem 1.4 from them. By Lemmas 4.1 and 4.2, we have
∑ g ∈ G z 0 < g ≤ x B ( x ; b , h ; g ) ≪ A x log 4 x ϕ ( b ) log x ( log 2 x ) 6 / 5 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 + x ( log 3 x ) 3 ϕ ( b ) log x ( log 2 x ) 2 . \sum_{\substack{g\in\mathcal{G}\\z_0<g\le x}}B(x;b,h;g)\ll_A\frac{x\log_4 x}{\phi(b)\log x(\log_2 x)^{6/5}}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}+\frac{x(\log_3 x)^3}{\phi(b)\log x(\log_2 x)^2}. g ∈ G z 0 < g ≤ x ∑ B ( x ; b , h ; g ) ≪ A ϕ ( b ) log x ( log 2 x ) 6/5 x log 4 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 + ϕ ( b ) log x ( log 2 x ) 2 x ( log 3 x ) 3 . Note that ( log 3 x ) 3 / ( log 2 x ) 2 = o ( log 4 x / ( log 2 x ) 6 / 5 ) (\log_3 x)^3/(\log_2 x)^2=o(\log_4 x/(\log_2 x)^{6/5}) ( log 3 x ) 3 / ( log 2 x ) 2 = o ( log 4 x / ( log 2 x ) 6/5 )
∑ g ∈ G z 0 < g ≤ x B ( x ; b , h ; g ) ≪ A x log 4 x ϕ ( b ) log x ( log 2 x ) 6 / 5 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . \sum_{\substack{g\in\mathcal{G}\\z_0<g\le x}}B(x;b,h;g)\ll_A\frac{x\log_4 x}{\phi(b)\log x(\log_2 x)^{6/5}}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. g ∈ G z 0 < g ≤ x ∑ B ( x ; b , h ; g ) ≪ A ϕ ( b ) log x ( log 2 x ) 6/5 x log 4 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . This is smaller than the main term. Combining this with (9) and the asymptotic formula for S ( A , P , z 0 ) S(\mathcal{A},\mathcal{P},z_0) S ( A , P , z 0 )
∣ G ( x ; b , h ) ∣ = ( 1 + o A ( 1 ) ) x ϕ ( b ) log x log 2 x ∏ g ∣ b g ∈ G ( 1 − 1 g − 1 ) − 1 . |\mathcal{G}(x;b,h)|=(1+o_A(1))\frac{x}{\phi(b)\log x\log_2 x}\prod_{\substack{g\mid b\\g\in\mathcal{G}}}\left(1-\frac{1}{g-1}\right)^{-1}. ∣ G ( x ; b , h ) ∣ = ( 1 + o A ( 1 )) ϕ ( b ) log x log 2 x x g ∣ b g ∈ G ∏ ( 1 − g − 1 1 ) − 1 . This proves Theorem 1.4, assuming Lemmas 4.1 and 4.2 , which we now prove.
Proof of Lemma 4.1 . Recall that
B ( x ; b , h ; g ) = # { p ≤ x : p ≡ h ( m o d b ) , p ≡ 1 ( m o d g ) , p ≢ 1 ( m o d q ) for all q ∈ G ( z 0 ) } . B(x;b,h;g)=\#\{p\le x:p\equiv h\pmod b,\ p\equiv1\pmod g,\ p\not\equiv1\pmod q\text{ for all }q\in\mathcal{G}(z_0)\}. B ( x ; b , h ; g ) = # { p ≤ x : p ≡ h ( mod b ) , p ≡ 1 ( mod g ) , p ≡ 1 ( mod q ) for all q ∈ G ( z 0 )} . Fix a Golomb prime g ∈ ( z 0 , t ] g\in(z_0,t] g ∈ ( z 0 , t ] g > z 0 > b g>z_0>b g > z 0 > b ( g , b ) = 1 (g,b)=1 ( g , b ) = 1 h ~ ∈ [ 0 , g b ) \widetilde{h}\in[0,gb) h ∈ [ 0 , g b ) h ~ ≡ h ( m o d b ) \widetilde{h}\equiv h\pmod b h ≡ h ( mod b ) h ~ ≡ 1 ( m o d g ) \widetilde{h}\equiv1\pmod g h ≡ 1 ( mod g ) p p p B ( x ; b , h ; g ) B(x;b,h;g) B ( x ; b , h ; g )
p = g b m + h ~ , with 0 ≤ m ≤ x g b . p=gbm+\widetilde{h},\qquad\text{with }0\le m\le\frac{x}{gb}. p = g bm + h , with 0 ≤ m ≤ g b x . The value m = 0 m=0 m = 0 p = h ~ p=\widetilde{h} p = h ∣ G ( t ) ∣ ≤ t |\mathcal{G}(t)|\le t ∣ G ( t ) ∣ ≤ t Lemma 4.1 . This is negligible compared to the bound we are aiming to prove; hence it suffices to count the primes p = g b m + h ~ p=gbm+\widetilde{h} p = g bm + h 1 ≤ m ≤ x / ( g b ) 1\le m\le x/(gb) 1 ≤ m ≤ x / ( g b ) ( h ~ , g b ) = 1 (\widetilde{h},gb)=1 ( h , g b ) = 1 q ≤ z 0 q\le z_0 q ≤ z 0 ( h ~ − 1 , g b ) (\widetilde{h}-1,gb) ( h − 1 , g b ) p p p B ( x ; b , h ; g ) B(x;b,h;g) B ( x ; b , h ; g ) p ≢ 0 ( m o d r ) p\not\equiv0\pmod r p ≡ 0 ( mod r ) r ∈ P r\in\mathcal{P} r ∈ P r ≠ p r\ne p r = p p ≢ 1 ( m o d q ) p\not\equiv1\pmod q p ≡ 1 ( mod q ) q ∈ G ( z 0 ) q\in\mathcal{G}(z_0) q ∈ G ( z 0 ) p p p m m m
For all r ∈ P r\in\mathcal{P} r ∈ P r ∤ g b r\nmid gb r ∤ g b p = g b m + h ~ ≢ 0 ( m o d r ) p=gbm+\widetilde{h}\not\equiv0\pmod r p = g bm + h ≡ 0 ( mod r ) m ≢ − h ~ g b ( m o d r ) m\not\equiv-\frac{\widetilde{h}}{gb}\pmod r m ≡ − g b h ( mod r )
For all q ∈ G ( z 0 ) q\in\mathcal{G}(z_0) q ∈ G ( z 0 ) q ∤ g b q\nmid gb q ∤ g b p = g b m + h ~ ≢ 1 ( m o d q ) p=gbm+\widetilde{h}\not\equiv1\pmod q p = g bm + h ≡ 1 ( mod q ) m ≢ − h ~ − 1 g b ( m o d q ) m\not\equiv-\frac{\widetilde{h}-1}{gb}\pmod q m ≡ − g b h − 1 ( mod q )
Note also that − h ~ g b -\frac{\widetilde{h}}{gb} − g b h − h ~ − 1 g b -\frac{\widetilde{h}-1}{gb} − g b h − 1 g b gb g b
We apply Theorem 3.3 to the set A \mathcal{A} A m ≤ x / ( g b ) m\le x/(gb) m ≤ x / ( g b ) κ = 2 \kappa=2 κ = 2 X = x g b X=\frac{x}{gb} X = g b x z 1 = exp ( log x 2 ( log 2 x ) 4 / 5 ) z_1=\exp\left(\frac{\log x}{2(\log_2 x)^{4/5}}\right) z 1 = exp ( 2 ( l o g 2 x ) 4/5 l o g x ) l l l
∣ A l ∣ = x g b l + O ( 1 ) if l ∤ b , and ∣ A l ∣ = 0 otherwise. |\mathcal{A}_l|=\frac{x}{gbl}+O(1)\qquad\text{if }l\nmid b,\text{ and }|\mathcal{A}_l|=0\text{ otherwise.} ∣ A l ∣ = g b l x + O ( 1 ) if l ∤ b , and ∣ A l ∣ = 0 otherwise. For a Golomb prime q q q
∣ A q ∣ = 2 x g b q + O ( 1 ) if q ∤ b , and ∣ A q ∣ = 0 otherwise. |\mathcal{A}_q|=\frac{2x}{gbq}+O(1)\qquad\text{if }q\nmid b,\text{ and }|\mathcal{A}_q|=0\text{ otherwise.} ∣ A q ∣ = g b q 2 x + O ( 1 ) if q ∤ b , and ∣ A q ∣ = 0 otherwise. Thus w ( l ) = 1 w(l)=1 w ( l ) = 1 l ∈ P ∖ G l\in\mathcal{P}\setminus\mathcal{G} l ∈ P ∖ G l ∤ b l\nmid b l ∤ b w ( q ) = 2 w(q)=2 w ( q ) = 2 q ∈ G q\in\mathcal{G} q ∈ G q ∤ b q\nmid b q ∤ b w ( r ) = 0 w(r)=0 w ( r ) = 0 r ∈ P r\in\mathcal{P} r ∈ P w w w d ∣ P ( z 1 ) d\mid P(z_1) d ∣ P ( z 1 ) g ≤ t g\le t g ≤ t X = x / ( g b ) ≥ x / ( t b ) ≥ z 1 X=x/(gb)\ge x/(tb)\ge z_1 X = x / ( g b ) ≥ x / ( t b ) ≥ z 1 Theorem 3.3 applies, and 1 + O ( exp ( − log X 2 log z 1 ) ) = O ( 1 ) 1+O\left(\exp\left(-\frac{\log X}{2\log z_1}\right)\right)=O(1) 1 + O ( exp ( − 2 l o g z 1 l o g X ) ) = O ( 1 )
S ( A , P , z 1 ) ≪ x g b ∏ l ∈ P ∖ G l ∤ b l ≤ z 1 ( 1 − 1 l ) ∏ q ∈ G q ∤ b q ≤ z 1 ( 1 − 2 q ) . S(\mathcal{A},\mathcal{P},z_1)\ll\frac{x}{gb}\prod_{\substack{l\in\mathcal{P}\setminus\mathcal{G}\\ l\nmid b\\ l\le z_1}}\left(1-\frac{1}{l}\right)\prod_{\substack{q\in\mathcal{G}\\ q\nmid b\\ q\le z_1}}\left(1-\frac{2}{q}\right). S ( A , P , z 1 ) ≪ g b x l ∈ P ∖ G l ∤ b l ≤ z 1 ∏ ( 1 − l 1 ) q ∈ G q ∤ b q ≤ z 1 ∏ ( 1 − q 2 ) . Since 1 − 2 q = ( 1 − 1 q ) ( 1 − 1 q − 1 ) 1-\frac{2}{q}=\left(1-\frac{1}{q}\right)\left(1-\frac{1}{q-1}\right) 1 − q 2 = ( 1 − q 1 ) ( 1 − q − 1 1 ) b b b z 1 z_1 z 1
S ( A , P , z 1 ) ≪ x g b ∏ r ∈ P r ≤ z 1 ( 1 − 1 r ) ∏ q ∈ G q ≤ z 1 ( 1 − 1 q − 1 ) ∏ r ∣ b r ∈ P ( 1 − 1 r ) − 1 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . S(\mathcal{A},\mathcal{P},z_1)\ll\frac{x}{gb}\prod_{\substack{r\in\mathcal{P}\\ r\le z_1}}\left(1-\frac{1}{r}\right)\prod_{\substack{q\in\mathcal{G}\\ q\le z_1}}\left(1-\frac{1}{q-1}\right)\prod_{\substack{r\mid b\\ r\in\mathcal{P}}}\left(1-\frac{1}{r}\right)^{-1}\prod_{\substack{q\mid b\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. S ( A , P , z 1 ) ≪ g b x r ∈ P r ≤ z 1 ∏ ( 1 − r 1 ) q ∈ G q ≤ z 1 ∏ ( 1 − q − 1 1 ) r ∣ b r ∈ P ∏ ( 1 − r 1 ) − 1 q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . By Mertens’ theorem (6) , Theorem 1.2 and the definition of Euler’s totient function ϕ \phi ϕ
S ( A , P , z 1 ) ≪ x g ϕ ( b ) log z 1 log 2 z 1 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . S(\mathcal{A},\mathcal{P},z_1) \ll\frac{x}{g\phi(b)\log z_1\log_2 z_1}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. S ( A , P , z 1 ) ≪ g ϕ ( b ) log z 1 log 2 z 1 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . Since log z 1 = log x 2 ( log 2 x ) 4 / 5 \log z_1=\frac{\log x}{2(\log_2 x)^{4/5}} log z 1 = 2 ( l o g 2 x ) 4/5 l o g x log 2 z 1 = log 2 x + O ( log 3 x ) \log_2 z_1=\log_2 x+O(\log_3 x) log 2 z 1 = log 2 x + O ( log 3 x )
S ( A , P , z 1 ) ≪ x g ϕ ( b ) log x ( log 2 x ) 1 / 5 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . S(\mathcal{A},\mathcal{P},z_1) \ll\frac{x}{g\phi(b)\log x(\log_2 x)^{1/5}}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. S ( A , P , z 1 ) ≪ g ϕ ( b ) log x ( log 2 x ) 1/5 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . As B ( x ; b , h ; g ) ≤ S ( A , P , z 1 ) B(x;b,h;g)\le S(\mathcal{A},\mathcal{P},z_1) B ( x ; b , h ; g ) ≤ S ( A , P , z 1 ) g g g
∑ g ∈ G z 0 < g ≤ t B ( x ; b , h ; g ) ≪ x ϕ ( b ) log x ( log 2 x ) 1 / 5 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 ∑ g ∈ G z 0 < g ≤ t 1 g . \sum_{\substack{g\in\mathcal{G}\\z_0<g\le t}}B(x;b,h;g)\ll\frac{x}{\phi(b)\log x(\log_2 x)^{1/5}}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}\sum_{\substack{g\in\mathcal{G}\\z_0<g\le t}}\frac{1}{g}. g ∈ G z 0 < g ≤ t ∑ B ( x ; b , h ; g ) ≪ ϕ ( b ) log x ( log 2 x ) 1/5 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 g ∈ G z 0 < g ≤ t ∑ g 1 . By Lemma 3.1, it follows that
∑ g ∈ G z 0 < g ≤ t B ( x ; b , h ; g ) ≪ x ϕ ( b ) log x ( log 2 x ) 1 / 5 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 ( log 3 t − log 3 z 0 + O ( 1 log z 0 log 2 z 0 ) ) . (10) \sum_{\substack{g\in\mathcal{G}\\z_0<g\le t}}B(x;b,h;g)\ll\frac{x}{\phi(b)\log x(\log_2 x)^{1/5}}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}\left(\log_3 t-\log_3 z_0+O\left(\frac{1}{\log z_0\log_2 z_0}\right)\right). \tag*{(10)} g ∈ G z 0 < g ≤ t ∑ B ( x ; b , h ; g ) ≪ ϕ ( b ) log x ( log 2 x ) 1/5 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 ( log 3 t − log 3 z 0 + O ( log z 0 log 2 z 0 1 ) ) . (10) By the definitions of t t t z 0 z_0 z 0
log 3 t = log 3 x + O ( 1 ( log 2 x ) 9 / 5 ) , log 3 z 0 = log 3 x + O ( log 4 x log 2 x ) , 1 log z 0 log 2 z 0 = O ( log 3 x log 2 x log x ) . \log_3 t=\log_3 x+O\left(\frac{1}{(\log_2 x)^{9/5}}\right),\qquad\log_3 z_0=\log_3 x+O\left(\frac{\log_4 x}{\log_2 x}\right),\qquad\frac{1}{\log z_0\log_2 z_0}=O\left(\frac{\log_3 x\log_2 x}{\log x}\right). log 3 t = log 3 x + O ( ( log 2 x ) 9/5 1 ) , log 3 z 0 = log 3 x + O ( log 2 x log 4 x ) , log z 0 log 2 z 0 1 = O ( log x log 3 x log 2 x ) . So the factor in parentheses in (4.3) is ≪ log 4 x / log 2 x \ll\log_4 x/\log_2 x ≪ log 4 x / log 2 x
∑ g ∈ G z 0 < g ≤ t B ( x ; b , h ; g ) ≪ x log 4 x ϕ ( b ) log x ( log 2 x ) 6 / 5 ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . \sum_{\substack{g\in\mathcal{G}\\z_0<g\le t}}B(x;b,h;g)\ll\frac{x\log_4 x}{\phi(b)\log x(\log_2 x)^{6/5}}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. g ∈ G z 0 < g ≤ t ∑ B ( x ; b , h ; g ) ≪ ϕ ( b ) log x ( log 2 x ) 6/5 x log 4 x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . This completes the proof of Lemma 4.1. □
Proof of Lemma 4.2. Let g ∈ ( t , x ] g\in(t,x] g ∈ ( t , x ] p p p B ( x ; b , h ; g ) B(x;b,h;g) B ( x ; b , h ; g )
for some positive integer m m m m < x / t m<x/t m < x / t p ≤ x p\le x p ≤ x g > t g>t g > t m m m p p p g g g m m m g ∈ ( t , x ] g\in(t,x] g ∈ ( t , x ] g m + 1 gm+1 g m + 1 B ( x ; b , h ; g ) B(x;b,h;g) B ( x ; b , h ; g ) M \mathcal{M} M m m m g g g m m m
Since p = g m + 1 p=gm+1 p = g m + 1 g g g m m m
If q ∈ G ( z 0 ) q\in\mathcal{G}(z_0) q ∈ G ( z 0 ) p = g m + 1 ≢ 1 ( m o d q ) p=gm+1\not\equiv1\pmod q p = g m + 1 ≡ 1 ( mod q ) q ∤ m q\nmid m q ∤ m m m m x / t < z 0 x/t<z_0 x / t < z 0 m m m
p = g m + 1 ≡ h ( m o d b ) p=gm+1\equiv h\pmod b p = g m + 1 ≡ h ( mod b ) g m ≡ h − 1 ( m o d b ) gm\equiv h-1\pmod b g m ≡ h − 1 ( mod b ) ( g , b ) = 1 (g,b)=1 ( g , b ) = 1
( m , b ) = ( h − 1 , b ) = : D . (m,b)=(h-1,b)=:D. ( m , b ) = ( h − 1 , b ) =: D . Writing m = m ′ D m=m'D m = m ′ D h − 1 = h ′ D h-1=h'D h − 1 = h ′ D b = b ′ D b=b'D b = b ′ D D D D
g m ′ ≡ h ′ ( m o d b ′ ) , gm'\equiv h'\pmod{b'}, g m ′ ≡ h ′ ( mod b ′ ) , which implies
g ≡ h ′ m ′ ( m o d b ′ ) . g\equiv\frac{h'}{m'}\pmod{b'}. g ≡ m ′ h ′ ( mod b ′ ) . Thus
M ⊆ { 1 ≤ m ≤ x t : 2 ∣ m , q ∤ m for all q ∈ G , ( m , b ) = D } . (11) \mathcal{M}\subseteq\left\{1\le m\le\frac{x}{t}:2\mid m,\ q\nmid m\text{ for all }q\in\mathcal{G},\ (m,b)=D\right\}. \tag*{(11)} M ⊆ { 1 ≤ m ≤ t x : 2 ∣ m , q ∤ m for all q ∈ G , ( m , b ) = D } . (11) Let z 2 = x 1 / 2 z_2=x^{1/2} z 2 = x 1/2 g g g m ∈ M m\in\mathcal{M} m ∈ M
As g g g g ≢ 0 ( m o d r ) g\not\equiv0\pmod r g ≡ 0 ( mod r ) r ≤ z 2 r\le z_2 r ≤ z 2
As g g g g ≢ 1 ( m o d q ) g\not\equiv1\pmod q g ≡ 1 ( mod q ) q ≤ z 2 q\le z_2 q ≤ z 2
As p = g m + 1 p=gm+1 p = g m + 1 p > z 2 p>z_2 p > z 2 p ≢ 0 ( m o d r ) p\not\equiv0\pmod r p ≡ 0 ( mod r ) r ≤ z 2 r\le z_2 r ≤ z 2 r ∤ m r\nmid m r ∤ m g ≢ − 1 m ( m o d r ) g\not\equiv-\frac{1}{m}\pmod r g ≡ − m 1 ( mod r )
The conditions modulo 3 give one more restriction on m m m 3 ∤ b ′ ( m + 1 ) 3\nmid b'(m+1) 3 ∤ b ′ ( m + 1 ) 3 ∈ G 3\in\mathcal{G} 3 ∈ G 3 ∤ m 3\nmid m 3 ∤ m m ≡ 1 ( m o d 3 ) m\equiv1\pmod3 m ≡ 1 ( mod 3 ) g g g 0 0 0 1 1 1 − 1 / m ≡ 2 ( m o d 3 ) -1/m\equiv2\pmod3 − 1/ m ≡ 2 ( mod 3 ) m ∈ M m\in\mathcal{M} m ∈ M 3 ∣ b ′ ( m + 1 ) 3\mid b'(m+1) 3 ∣ b ′ ( m + 1 )
For each m ∈ M m\in\mathcal{M} m ∈ M A m \mathcal{A}_m A m g ≤ x / m g\le x/m g ≤ x / m
g ≡ h ′ m ′ ( m o d b ′ ) g\equiv\frac{h'}{m'}\pmod{b'} g ≡ m ′ h ′ ( mod b ′ ) so that
∣ A m ∣ = x m b ′ + O ( 1 ) . |\mathcal{A}_m|=\frac{x}{mb'}+O(1). ∣ A m ∣ = m b ′ x + O ( 1 ) . We now apply Theorem 3.3 to A = A m \mathcal{A}=\mathcal{A}_m A = A m κ = 3 \kappa=3 κ = 3 z = z 2 z=z_2 z = z 2 g g g
w ( l ) = 2 w(l)=2 w ( l ) = 2 l ∈ P ∖ G l\in\mathcal{P}\setminus\mathcal{G} l ∈ P ∖ G l ∤ m l\nmid m l ∤ m l ∤ b l\nmid b l ∤ b
w ( l ) = 1 w(l)=1 w ( l ) = 1 l ∈ P ∖ G l\in\mathcal{P}\setminus\mathcal{G} l ∈ P ∖ G l ∣ m l\mid m l ∣ m l ∤ b ′ l\nmid b' l ∤ b ′
w ( q ) = 3 w(q)=3 w ( q ) = 3 q ∈ G q\in\mathcal{G} q ∈ G q ∤ b ′ q\nmid b' q ∤ b ′ q ∤ ( m + 1 ) q\nmid(m+1) q ∤ ( m + 1 )
w ( q ) = 2 w(q)=2 w ( q ) = 2 q ∈ G q\in\mathcal{G} q ∈ G q ∤ b q\nmid b q ∤ b q ∣ m + 1 q\mid m+1 q ∣ m + 1 − 1 / m ≡ 1 ( m o d q ) -1/m\equiv1\pmod q − 1/ m ≡ 1 ( mod q )
and w ( r ) = 0 w(r)=0 w ( r ) = 0 r ∣ b ′ r\mid b' r ∣ b ′
We extend w w w d ∣ P ( z 2 ) d\mid P(z_2) d ∣ P ( z 2 ) x / m b ′ > x 0.98 x/mb'>x^{0.98} x / m b ′ > x 0.98
S ( A m , P , z 2 ) ≪ x m b ′ ∏ l ∣ m b ′ l ∈ P ∖ G l ≤ x 1 / 2 ( 1 − 2 l ) ∏ l ∣ m l ∣ b ′ l ∈ P ∖ G l ≤ x 1 / 2 ( 1 − 1 l ) ∏ q ∣ b ′ ( m + 1 ) q ∈ G q ≤ x 1 / 2 ( 1 − 3 q ) ∏ q ∣ b q ∣ ( m + 1 ) q ∈ G q ≤ x 1 / 2 ( 1 − 2 q ) . S(\mathcal{A}_m,\mathcal{P},z_2)\ll\frac{x}{mb'}
\prod_{\substack{l\mid mb'\\ l\in\mathcal{P}\setminus\mathcal{G}\\ l\le x^{1/2}}}\left(1-\frac{2}{l}\right)
\prod_{\substack{l\mid m\\ l\mid b'\\ l\in\mathcal{P}\setminus\mathcal{G}\\ l\le x^{1/2}}}\left(1-\frac{1}{l}\right)
\prod_{\substack{q\mid b'(m+1)\\ q\in\mathcal{G}\\ q\le x^{1/2}}}\left(1-\frac{3}{q}\right)
\prod_{\substack{q\mid b\\ q\mid(m+1)\\ q\in\mathcal{G}\\ q\le x^{1/2}}}\left(1-\frac{2}{q}\right). S ( A m , P , z 2 ) ≪ m b ′ x l ∣ m b ′ l ∈ P ∖ G l ≤ x 1/2 ∏ ( 1 − l 2 ) l ∣ m l ∣ b ′ l ∈ P ∖ G l ≤ x 1/2 ∏ ( 1 − l 1 ) q ∣ b ′ ( m + 1 ) q ∈ G q ≤ x 1/2 ∏ ( 1 − q 3 ) q ∣ b q ∣ ( m + 1 ) q ∈ G q ≤ x 1/2 ∏ ( 1 − q 2 ) . Writing 1 − 2 l = ( 1 − 1 l ) ( 1 − 1 l − 1 ) 1-\frac{2}{l}=\left(1-\frac{1}{l}\right)\left(1-\frac{1}{l-1}\right) 1 − l 2 = ( 1 − l 1 ) ( 1 − l − 1 1 ) l > 2 l>2 l > 2 1 − 3 q = ( 1 − 2 q ) ( 1 − 1 q − 2 ) 1-\frac{3}{q}=\left(1-\frac{2}{q}\right)\left(1-\frac{1}{q-2}\right) 1 − q 3 = ( 1 − q 2 ) ( 1 − q − 2 1 ) q > 3 q>3 q > 3
S ( A m , P , z 2 ) ≪ x m b ′ ∏ l ∣ b ′ l ∈ P ∖ G l ≤ x 1 / 2 ( 1 − 1 l ) ∏ l ∣ m l ∣ b ′ l ∈ P ∖ G 2 < l ≤ x 1 / 2 ( 1 − 1 l − 1 ) ∏ q ∣ b ′ q ∈ G q ≤ x 1 / 2 ( 1 − 2 q ) ∏ q ∣ b ′ q ∣ m + 1 q ∈ G 3 < q ≤ x 1 / 2 ( 1 − 1 q − 2 ) . S(\mathcal{A}_m,\mathcal{P},z_2)\ll\frac{x}{mb'}
\prod_{\substack{l\mid b'\\ l\in\mathcal{P}\setminus\mathcal{G}\\ l\le x^{1/2}}}\left(1-\frac{1}{l}\right)
\prod_{\substack{l\mid m\\ l\mid b'\\ l\in\mathcal{P}\setminus\mathcal{G}\\ 2<l\le x^{1/2}}}\left(1-\frac{1}{l-1}\right)
\prod_{\substack{q\mid b'\\ q\in\mathcal{G}\\ q\le x^{1/2}}}\left(1-\frac{2}{q}\right)
\prod_{\substack{q\mid b'\\ q\mid m+1\\ q\in\mathcal{G}\\ 3<q\le x^{1/2}}}\left(1-\frac{1}{q-2}\right). S ( A m , P , z 2 ) ≪ m b ′ x l ∣ b ′ l ∈ P ∖ G l ≤ x 1/2 ∏ ( 1 − l 1 ) l ∣ m l ∣ b ′ l ∈ P ∖ G 2 < l ≤ x 1/2 ∏ ( 1 − l − 1 1 ) q ∣ b ′ q ∈ G q ≤ x 1/2 ∏ ( 1 − q 2 ) q ∣ b ′ q ∣ m + 1 q ∈ G 3 < q ≤ x 1/2 ∏ ( 1 − q − 2 1 ) . Collecting the terms, we get
S ( A m , P , z 2 ) ≪ x m b ′ ∏ r ∈ P 2 < r ≤ x 1 / 2 ( 1 − 2 r ) ∏ r ∣ b ′ r ∈ P r > 2 ( 1 − 2 r ) − 1 ∏ l ∣ m l ∣ b ′ l ∈ P ∖ G 2 < l ≤ x 1 / 2 ( 1 − 1 l − 1 ) − 1 × ∏ q ∈ G 3 < q ≤ x 1 / 2 ( 1 − 1 q − 2 ) ∏ q ∣ b ′ q ∈ G q > 3 ( 1 − 1 q − 2 ) − 1 ∏ q ∣ b ′ q ∣ m + 1 q ∈ G q > 3 ( 1 − 1 q − 2 ) − 1 . \begin{aligned}
S(\mathcal{A}_m,\mathcal{P},z_2)&\ll\frac{x}{mb'}
\prod_{\substack{r\in\mathcal{P}\\ 2<r\le x^{1/2}}}\left(1-\frac{2}{r}\right)
\prod_{\substack{r\mid b'\\ r\in\mathcal{P}\\ r>2}}\left(1-\frac{2}{r}\right)^{-1}
\prod_{\substack{l\mid m\\ l\mid b'\\ l\in\mathcal{P}\setminus\mathcal{G}\\ 2<l\le x^{1/2}}}\left(1-\frac{1}{l-1}\right)^{-1}\\
&\qquad{}\times
\prod_{\substack{q\in\mathcal{G}\\ 3<q\le x^{1/2}}}\left(1-\frac{1}{q-2}\right)
\prod_{\substack{q\mid b'\\ q\in\mathcal{G}\\ q>3}}\left(1-\frac{1}{q-2}\right)^{-1}
\prod_{\substack{q\mid b'\\ q\mid m+1\\ q\in\mathcal{G}\\ q>3}}\left(1-\frac{1}{q-2}\right)^{-1}.
\end{aligned} S ( A m , P , z 2 ) ≪ m b ′ x r ∈ P 2 < r ≤ x 1/2 ∏ ( 1 − r 2 ) r ∣ b ′ r ∈ P r > 2 ∏ ( 1 − r 2 ) − 1 l ∣ m l ∣ b ′ l ∈ P ∖ G 2 < l ≤ x 1/2 ∏ ( 1 − l − 1 1 ) − 1 × q ∈ G 3 < q ≤ x 1/2 ∏ ( 1 − q − 2 1 ) q ∣ b ′ q ∈ G q > 3 ∏ ( 1 − q − 2 1 ) − 1 q ∣ b ′ q ∣ m + 1 q ∈ G q > 3 ∏ ( 1 − q − 2 1 ) − 1 . Every integer 1 < n ≤ x 1<n\le x 1 < n ≤ x ≪ log x \ll\log x ≪ log x
∏ q ∣ n , q > 3 q ∈ G ( 1 − 1 q − 2 ) − 1 ≪ log 3 ( x ) . \prod_{\substack{q\mid n,\ q>3\\q\in\mathcal G}}\left(1-\frac{1}{q-2}\right)^{-1}\ll\log_3(x). q ∣ n , q > 3 q ∈ G ∏ ( 1 − q − 2 1 ) − 1 ≪ log 3 ( x ) . Using this with n = b ′ n=b' n = b ′ n = m + 1 n=m+1 n = m + 1
S ( A m , P , z 2 ) ≪ A x ( log 3 x ) 2 m b ′ ∏ 2 < r ≤ x 1 / 2 r ∈ P ( 1 − 2 r ) ∏ r ∣ b ′ r ∈ P r > 2 ( 1 − 2 r ) − 1 ∏ l ∣ m l ∉ G l ∈ P 2 < l ≤ x 1 / 2 ( 1 − 1 l − 1 ) − 1 ∏ q ∈ G 3 < q ≤ x 1 / 2 ( 1 − 1 q − 2 ) . S(\mathcal A_m,\mathcal P,z_2)\ll_A \frac{x(\log_3 x)^2}{mb'}\prod_{\substack{2<r\le x^{1/2}\\r\in\mathcal P}}\left(1-\frac{2}{r}\right)\prod_{\substack{r\mid b'\\r\in\mathcal P\\r>2}}\left(1-\frac{2}{r}\right)^{-1}\prod_{\substack{l\mid m\\l\notin\mathcal G\\l\in\mathcal P\\2<l\le x^{1/2}}}\left(1-\frac{1}{l-1}\right)^{-1}
\prod_{\substack{q\in\mathcal G\\3<q\le x^{1/2}}}\left(1-\frac{1}{q-2}\right). S ( A m , P , z 2 ) ≪ A m b ′ x ( log 3 x ) 2 2 < r ≤ x 1/2 r ∈ P ∏ ( 1 − r 2 ) r ∣ b ′ r ∈ P r > 2 ∏ ( 1 − r 2 ) − 1 l ∣ m l ∈ / G l ∈ P 2 < l ≤ x 1/2 ∏ ( 1 − l − 1 1 ) − 1 q ∈ G 3 < q ≤ x 1/2 ∏ ( 1 − q − 2 1 ) . Consequently,
∑ g ∈ G t < g ≤ x B ( x ; b , h ; g ) ≤ ∑ m ∈ M 1 ≤ m ≤ x / t S ( A m , P , z 2 ) ≪ A x ( log 3 x ) 2 b ′ ∏ 2 < r ≤ x 1 / 2 r ∈ P ( 1 − 2 r ) ∏ r ∣ b ′ r ∈ P r > 2 ( 1 − 2 r ) − 1 ∏ q ∈ G 3 < q ≤ x 1 / 2 ( 1 − 1 q − 2 ) ∑ m ∈ M 1 ≤ m ≤ x / t 1 m ∏ l ∣ m l ∉ G l ∈ P 2 < l ≤ x 1 / 2 ( 1 − 1 l − 1 ) − 1 . (12) \sum_{\substack{g\in\mathcal G\\t<g\le x}}B(x;b,h;g)\le\sum_{\substack{m\in\mathcal M\\1\le m\le x/t}}S(\mathcal A_m,\mathcal P,z_2)\ll_A\frac{x(\log_3 x)^2}{b'}\prod_{\substack{2<r\le x^{1/2}\\r\in\mathcal P}}\left(1-\frac{2}{r}\right)\prod_{\substack{r\mid b'\\r\in\mathcal P\\r>2}}\left(1-\frac{2}{r}\right)^{-1}
\prod_{\substack{q\in\mathcal G\\3<q\le x^{1/2}}}\left(1-\frac{1}{q-2}\right)
\sum_{\substack{m\in\mathcal M\\1\le m\le x/t}}\frac{1}{m}\prod_{\substack{l\mid m\\l\notin\mathcal G\\l\in\mathcal P\\2<l\le x^{1/2}}}\left(1-\frac{1}{l-1}\right)^{-1}. \tag*{(12)} g ∈ G t < g ≤ x ∑ B ( x ; b , h ; g ) ≤ m ∈ M 1 ≤ m ≤ x / t ∑ S ( A m , P , z 2 ) ≪ A b ′ x ( log 3 x ) 2 2 < r ≤ x 1/2 r ∈ P ∏ ( 1 − r 2 ) r ∣ b ′ r ∈ P r > 2 ∏ ( 1 − r 2 ) − 1 q ∈ G 3 < q ≤ x 1/2 ∏ ( 1 − q − 2 1 ) m ∈ M 1 ≤ m ≤ x / t ∑ m 1 l ∣ m l ∈ / G l ∈ P 2 < l ≤ x 1/2 ∏ ( 1 − l − 1 1 ) − 1 . (12) Let f ( m ) f(m) f ( m ) m m m
f ( m ) = 1 m ∏ l ∣ m l ∉ G l ∈ P 2 < l ≤ x 1 / 2 ( 1 − 1 l − 1 ) − 1 . f(m)=\frac{1}{m}\prod_{\substack{l\mid m\\l\notin\mathcal G\\l\in\mathcal P\\2<l\le x^{1/2}}}\left(1-\frac{1}{l-1}\right)^{-1}. f ( m ) = m 1 l ∣ m l ∈ / G l ∈ P 2 < l ≤ x 1/2 ∏ ( 1 − l − 1 1 ) − 1 . Recall from equation (11) that every m ∈ M m\in\mathcal M m ∈ M ( m , b ) = D (m,b)=D ( m , b ) = D
D = 2 v D ′ with ( 2 , D ′ ) = 1 , D=2^vD'\qquad\text{with}\qquad(2,D')=1, D = 2 v D ′ with ( 2 , D ′ ) = 1 , and let a = max { 1 , v } a=\max\{1,v\} a = max { 1 , v } f f f
∑ m ∈ M 1 ≤ m ≤ x / t f ( m ) ≤ ( f ( 2 a ) + f ( 2 a + 1 ) + ⋯ ) ∏ l ∤ D l ∉ G l ∈ P 2 < l ≤ x / t ( 1 + f ( l ) + f ( l 2 ) + ⋯ ) ∏ l ∣ D l ∣ b ′ , l ≠ 2 l ∈ P ∖ G ( f ( l ν l ( D ) ) + f ( l ν l ( D ) + 1 ) + ⋯ ) ∏ l ∣ D l ∣ b ′ , l ≠ 2 l ∈ P ∖ G ( f ( l ν l ( D ) ) ) . \sum_{\substack{m\in\mathcal M\\1\le m\le x/t}}f(m)\le\left(f(2^a)+f(2^{a+1})+\cdots\right)\prod_{\substack{l\nmid D\\l\notin\mathcal G\\l\in\mathcal P\\2<l\le x/t}}\left(1+f(l)+f(l^2)+\cdots\right)
\prod_{\substack{l\mid D\\l\mid b',\ l\ne2\\l\in\mathcal P\setminus\mathcal G}}\left(f(l^{\nu_l(D)})+f(l^{\nu_l(D)+1})+\cdots\right)\prod_{\substack{l\mid D\\l\mid b',\ l\ne2\\l\in\mathcal P\setminus\mathcal G}}\left(f(l^{\nu_l(D)})\right). m ∈ M 1 ≤ m ≤ x / t ∑ f ( m ) ≤ ( f ( 2 a ) + f ( 2 a + 1 ) + ⋯ ) l ∤ D l ∈ / G l ∈ P 2 < l ≤ x / t ∏ ( 1 + f ( l ) + f ( l 2 ) + ⋯ ) l ∣ D l ∣ b ′ , l = 2 l ∈ P ∖ G ∏ ( f ( l ν l ( D ) ) + f ( l ν l ( D ) + 1 ) + ⋯ ) l ∣ D l ∣ b ′ , l = 2 l ∈ P ∖ G ∏ ( f ( l ν l ( D ) ) ) . For the last product, note that if a prime l l l D D D b ′ b' b ′ ν l ( b ′ ) > ν l ( D ) \nu_l(b')>\nu_l(D) ν l ( b ′ ) > ν l ( D ) ( m , b ) = D (m,b)=D ( m , b ) = D ν l ( m ) = ν l ( D ) \nu_l(m)=\nu_l(D) ν l ( m ) = ν l ( D )
1 2 a − 1 ∏ l ∈ P ∖ G 2 < l ≤ x / t ( 1 + 1 l − 2 ) ∏ l ∣ D l ∈ P ∖ G l ≠ 2 1 l ν l ( D ) − 1 ( l − 2 ) ∏ l ∣ D l ∈ P ∖ G l ≠ 2 1 l ν l ( D ) . \frac{1}{2^{a-1}}\prod_{\substack{l\in\mathcal P\setminus\mathcal G\\2<l\le x/t}}\left(1+\frac{1}{l-2}\right)\prod_{\substack{l\mid D\\l\in\mathcal P\setminus\mathcal G\\l\ne2}}\frac{1}{l^{\nu_l(D)-1}(l-2)}\prod_{\substack{l\mid D\\l\in\mathcal P\setminus\mathcal G\\l\ne2}}\frac{1}{l^{\nu_l(D)}}. 2 a − 1 1 l ∈ P ∖ G 2 < l ≤ x / t ∏ ( 1 + l − 2 1 ) l ∣ D l ∈ P ∖ G l = 2 ∏ l ν l ( D ) − 1 ( l − 2 ) 1 l ∣ D l ∈ P ∖ G l = 2 ∏ l ν l ( D ) 1 . Since 1 + 1 l − 2 = ( 1 − 1 l − 1 ) − 1 1+\frac{1}{l-2}=\left(1-\frac{1}{l-1}\right)^{-1} 1 + l − 2 1 = ( 1 − l − 1 1 ) − 1
∑ m ∈ M 1 ≤ m ≤ x / t f ( m ) ≪ 1 D ∏ l ∈ P ∖ G 2 < l ≤ x / t ( 1 − 1 l − 1 ) − 1 ∏ l ∣ D , l ∣ b ′ l ∈ P ∖ G ( 1 − 1 l ) − 1 ∏ l ∣ b ′ , l ≠ 2 l ∈ P ∖ G ( 1 − 1 l − 1 ) . \sum_{\substack{m\in\mathcal M\\1\le m\le x/t}}f(m)\ll\frac{1}{D}\prod_{\substack{l\in\mathcal P\setminus\mathcal G\\2<l\le x/t}}\left(1-\frac{1}{l-1}\right)^{-1}\prod_{\substack{l\mid D,\ l\mid b'\\l\in\mathcal P\setminus\mathcal G}}\left(1-\frac{1}{l}\right)^{-1}\prod_{\substack{l\mid b',\ l\ne2\\l\in\mathcal P\setminus\mathcal G}}\left(1-\frac{1}{l-1}\right). m ∈ M 1 ≤ m ≤ x / t ∑ f ( m ) ≪ D 1 l ∈ P ∖ G 2 < l ≤ x / t ∏ ( 1 − l − 1 1 ) − 1 l ∣ D , l ∣ b ′ l ∈ P ∖ G ∏ ( 1 − l 1 ) − 1 l ∣ b ′ , l = 2 l ∈ P ∖ G ∏ ( 1 − l − 1 1 ) . Inserting this bound into equation (12) , we obtain
∑ g ∈ G t < g ≤ x B ( x ; b , h ; g ) ≪ A x ( log 3 x ) 2 b ′ D ∏ r ∈ P 2 < r ≤ x 1 / 2 ( 1 − 2 r ) ∏ r ∣ b ′ r ∈ P r > 2 ( 1 − 2 r ) − 1 ∏ q ∈ G 3 < q ≤ x 1 / 2 ( 1 − 1 q − 2 ) ∏ l ∈ P ∖ G 2 < l ≤ x / t ( 1 − 1 l − 1 ) − 1 ∏ l ∣ D , l ∣ b ′ l ∈ P ∖ G ( 1 − 1 l ) − 1 ∏ l ∣ b ′ , l ≠ 2 l ∈ P ∖ G ( 1 − 1 l − 1 ) . \sum_{\substack{g\in\mathcal G\\t<g\le x}}B(x;b,h;g)\ll_A\frac{x(\log_3x)^2}{b'D}\prod_{\substack{r\in\mathcal P\\2<r\le x^{1/2}}}\left(1-\frac{2}{r}\right)\prod_{\substack{r\mid b'\\r\in\mathcal P\\r>2}}\left(1-\frac{2}{r}\right)^{-1}\prod_{\substack{q\in\mathcal G\\3<q\le x^{1/2}}}\left(1-\frac{1}{q-2}\right)\prod_{\substack{l\in\mathcal P\setminus\mathcal G\\2<l\le x/t}}\left(1-\frac{1}{l-1}\right)^{-1}\prod_{\substack{l\mid D,\ l\mid b'\\l\in\mathcal P\setminus\mathcal G}}\left(1-\frac{1}{l}\right)^{-1}\prod_{\substack{l\mid b',\ l\ne2\\l\in\mathcal P\setminus\mathcal G}}\left(1-\frac{1}{l-1}\right). g ∈ G t < g ≤ x ∑ B ( x ; b , h ; g ) ≪ A b ′ D x ( log 3 x ) 2 r ∈ P 2 < r ≤ x 1/2 ∏ ( 1 − r 2 ) r ∣ b ′ r ∈ P r > 2 ∏ ( 1 − r 2 ) − 1 q ∈ G 3 < q ≤ x 1/2 ∏ ( 1 − q − 2 1 ) l ∈ P ∖ G 2 < l ≤ x / t ∏ ( 1 − l − 1 1 ) − 1 l ∣ D , l ∣ b ′ l ∈ P ∖ G ∏ ( 1 − l 1 ) − 1 l ∣ b ′ , l = 2 l ∈ P ∖ G ∏ ( 1 − l − 1 1 ) . Since D D D D D D P ∖ G \mathcal P\setminus\mathcal G P ∖ G
ϕ ( b ) = b ′ D ∏ r ∣ b ′ r ∈ P ( 1 − 1 r ) ∏ r ∣ D , r ∤ b ′ r ∈ P ( 1 − 1 r ) \phi(b)=b'D\prod_{\substack{r\mid b'\\r\in\mathcal P}}\left(1-\frac{1}{r}\right)\prod_{\substack{r\mid D,\ r\nmid b'\\r\in\mathcal P}}\left(1-\frac{1}{r}\right) ϕ ( b ) = b ′ D r ∣ b ′ r ∈ P ∏ ( 1 − r 1 ) r ∣ D , r ∤ b ′ r ∈ P ∏ ( 1 − r 1 ) and bounding ∏ r ≤ x 1 / 2 ( 1 − 1 r ) \prod_{r\le x^{1/2}}\left(1-\frac{1}{r}\right) ∏ r ≤ x 1/2 ( 1 − r 1 ) (6) , we obtain
∑ g ∈ G t < g ≤ x B ( x ; b , h ; g ) ≪ A x ( log 3 x ) 2 ϕ ( b ) ( log x ) ∏ l ∈ P ∖ G x / t < l ≤ x 1 / 2 ( 1 − 1 l − 1 ) ∏ q ∈ G 3 < q ≤ x 1 / 2 ( 1 − 2 q − 1 ) ∏ q ∣ b ′ q ∈ G ( 1 − 1 q − 1 ) − 1 . \sum_{\substack{g\in\mathcal G\\t<g\le x}}B(x;b,h;g)\ll_A\frac{x(\log_3x)^2}{\phi(b)(\log x)}\prod_{\substack{l\in\mathcal P\setminus\mathcal G\\x/t<l\le x^{1/2}}}\left(1-\frac{1}{l-1}\right)\prod_{\substack{q\in\mathcal G\\3<q\le x^{1/2}}}\left(1-\frac{2}{q-1}\right)\prod_{\substack{q\mid b'\\q\in\mathcal G}}\left(1-\frac{1}{q-1}\right)^{-1}. g ∈ G t < g ≤ x ∑ B ( x ; b , h ; g ) ≪ A ϕ ( b ) ( log x ) x ( log 3 x ) 2 l ∈ P ∖ G x / t < l ≤ x 1/2 ∏ ( 1 − l − 1 1 ) q ∈ G 3 < q ≤ x 1/2 ∏ ( 1 − q − 1 2 ) q ∣ b ′ q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . The product over l l l 1 1 1 1 − 2 q − 1 < ( 1 − 1 q − 1 ) 2 1-\frac{2}{q-1}<\left(1-\frac{1}{q-1}\right)^2 1 − q − 1 2 < ( 1 − q − 1 1 ) 2 3 < q ≤ x 1 / 2 3<q\le x^{1/2} 3 < q ≤ x 1/2 ≪ ( log 2 x ) − 2 \ll(\log_2x)^{-2} ≪ ( log 2 x ) − 2 q ∣ b ′ q\mid b' q ∣ b ′ ≪ log 3 x \ll\log_3x ≪ log 3 x
∑ g ∈ G t < g ≤ x B ( x ; b , h ; g ) ≪ x ( log 3 x ) 3 ϕ ( b ) ( log x ) ( log 2 x ) 2 . \sum_{\substack{g\in\mathcal G\\t<g\le x}}B(x;b,h;g)\ll\frac{x(\log_3x)^3}{\phi(b)(\log x)(\log_2x)^2}. g ∈ G t < g ≤ x ∑ B ( x ; b , h ; g ) ≪ ϕ ( b ) ( log x ) ( log 2 x ) 2 x ( log 3 x ) 3 . Remark 4.3. OpenAI has announced a proof that no Dirichlet L L L Re s > 7 / 8 \operatorname{Re}s>7/8 Re s > 7/8 [24 ] . Using this, one can show that Theorem 1.4 holds uniformly for 1 ≤ b ≤ x 1 / 8 − 2 ε 1\le b\le x^{1/8-2\varepsilon} 1 ≤ b ≤ x 1/8 − 2 ε ε > 0 \varepsilon>0 ε > 0
(i) For the main term, we use the bound ∣ E ( x ; q , a ) ∣ ≪ x 7 / 8 / log x |E(x;q,a)|\ll x^{7/8}/\log x ∣ E ( x ; q , a ) ∣ ≪ x 7/8 / log x (7) . We then apply Theorem 3.2 with z 0 = exp ( ε log x log 3 x ) z_0=\exp\left(\frac{\varepsilon\log x}{\log_3x}\right) z 0 = exp ( l o g 3 x ε l o g x )
(ii) Lemmas 4.1 and 4.2 hold, with the same bounds, for t = x b exp ( − log x ( log 2 x ) 4 / 5 ) t=\frac{x}{b}\exp\left(-\frac{\log x}{(\log_2x)^{4/5}}\right) t = b x exp ( − ( l o g 2 x ) 4/5 l o g x )
Non-smooth shifted Golomb primes: proof of Theorem 1.5
In this section we prove Theorem 1.5, which we restate here.
Theorem 1.5. Fix A > 0 A > 0 A > 0 x x x h ≠ 0 h \ne0 h = 0 ∣ h ∣ ≤ x 0.01 |h| \le x^{0.01} ∣ h ∣ ≤ x 0.01 1 ≤ b ≤ ( log x ) A 1 \le b \le(\log x)^A 1 ≤ b ≤ ( log x ) A ( b , h ) = 1 (b,h)=1 ( b , h ) = 1 ( b , h − 1 ) (b,h-1) ( b , h − 1 )
G n s m ( x ; b , h ; x 0.99 ) ≤ ( 0.259 + o ( 1 ) ) x ϕ ( b ) log x log log x ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . G_{\mathrm{nsm}}(x;b,h;x^{0.99}) \le(0.259+o(1))\frac{x}{\phi(b)\log x\log\log x}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. G nsm ( x ; b , h ; x 0.99 ) ≤ ( 0.259 + o ( 1 )) ϕ ( b ) log x log log x x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . where the o ( 1 ) o(1) o ( 1 ) A A A
We show that among the Golomb primes g ≤ x g \le x g ≤ x g ≡ h ( m o d b ) g \equiv h \pmod b g ≡ h ( mod b ) g − h g-h g − h x 0.99 x^{0.99} x 0.99
Recall the definition
G n s m ( x ; b , h ; z ) : = # { g ∈ G ( x ; b , h ) : g > h and g − h has a prime power divisor > z } , G_{\mathrm{nsm}}(x;b,h;z):=\#\{g\in\mathcal{G}(x;b,h):g>h\text{ and }g-h\text{ has a prime power divisor }>z\}, G nsm ( x ; b , h ; z ) := # { g ∈ G ( x ; b , h ) : g > h and g − h has a prime power divisor > z } , where G ( x ; b , h ) \mathcal{G}(x;b,h) G ( x ; b , h ) g ≤ x g \le x g ≤ x g ≡ h ( m o d b ) g \equiv h \pmod b g ≡ h ( mod b ) ≤ x \le x ≤ x p k > x 0.99 p^k>x^{0.99} p k > x 0.99 k ≥ 2 k\ge2 k ≥ 2 O ( x 0.505 ) O(x^{0.505}) O ( x 0.505 ) p p p k p k_p k p p k p > x 0.99 p^{k_p}>x^{0.99} p k p > x 0.99 p p p k p = 2 k_p=2 k p = 2 x 0.495 x^{0.495} x 0.495
∑ x 0.495 ≤ p < x 0.99 x p 2 = O ( x x 0.495 ) = O ( x 0.505 ) . \sum_{x^{0.495}\le p<x^{0.99}}\frac{x}{p^2}=O\left(\frac{x}{x^{0.495}}\right)=O(x^{0.505}). x 0.495 ≤ p < x 0.99 ∑ p 2 x = O ( x 0.495 x ) = O ( x 0.505 ) . For primes ≤ x 0.495 \le x^{0.495} ≤ x 0.495
∑ p < x 0.495 x p k p ≤ ∑ p < x 0.495 x x 0.99 = O ( x 0.505 ) . \sum_{p<x^{0.495}}\frac{x}{p^{k_p}}\le\sum_{p<x^{0.495}}\frac{x}{x^{0.99}}=O(x^{0.505}). p < x 0.495 ∑ p k p x ≤ p < x 0.495 ∑ x 0.99 x = O ( x 0.505 ) . So prime powers p k p^k p k k ≥ 2 k\ge2 k ≥ 2 O ( x 0.505 ) O(x^{0.505}) O ( x 0.505 ) g g g g − h g-h g − h p > x 0.99 p>x^{0.99} p > x 0.99
G n s m ′ ( x ; b , h ; x 0.99 ) : = # { g ∈ G ( x ; b , h ) : g > h and g − h has a prime divisor > x 0.99 } , G'_{\mathrm{nsm}}(x;b,h;x^{0.99}):=\#\{g\in\mathcal{G}(x;b,h):g>h\text{ and }g-h\text{ has a prime divisor }>x^{0.99}\}, G nsm ′ ( x ; b , h ; x 0.99 ) := # { g ∈ G ( x ; b , h ) : g > h and g − h has a prime divisor > x 0.99 } , so that G n s m ( x ; b , h ; x 0.99 ) ≤ G n s m ′ ( x ; b , h ; x 0.99 ) + O ( x 0.505 ) G_{\mathrm{nsm}}(x;b,h;x^{0.99})\le G'_{\mathrm{nsm}}(x;b,h;x^{0.99})+O(x^{0.505}) G nsm ( x ; b , h ; x 0.99 ) ≤ G nsm ′ ( x ; b , h ; x 0.99 ) + O ( x 0.505 ) g g g G n s m ′ ( x ; b , h ; x 0.99 ) G'_{\mathrm{nsm}}(x;b,h;x^{0.99}) G nsm ′ ( x ; b , h ; x 0.99 ) p > x 0.99 p>x^{0.99} p > x 0.99 g − h g-h g − h b ∣ g − h b\mid g-h b ∣ g − h p > b p>b p > b
for a positive integer m m m m m m p p p
N m = # { p : x 0.99 < p < x / m b , p m b + h is a Golomb prime } . N_m=\#\{p:x^{0.99}<p<x/mb,\ pmb+h\text{ is a Golomb prime}\}. N m = # { p : x 0.99 < p < x / mb , p mb + h is a Golomb prime } . Since p > x 0.99 p>x^{0.99} p > x 0.99 m b ≤ ( x + ∣ h ∣ ) / x 0.99 ≤ 2 x 0.01 mb\le(x+|h|)/x^{0.99}\le2x^{0.01} mb ≤ ( x + ∣ h ∣ ) / x 0.99 ≤ 2 x 0.01 p p p g g g m m m
( m b , h ) = 1 (mb,h)=1 ( mb , h ) = 1 g g g
( m b , h − 1 ) (mb,h-1) ( mb , h − 1 ) q q q g ≡ 1 ( m o d q ) g\equiv1\pmod q g ≡ 1 ( mod q )
Since g g g p p p 2 ∣ m b 2\mid mb 2 ∣ mb 2 ∣ h 2\mid h 2 ∣ h
Since g > 3 g>3 g > 3 g ≡ 2 ( m o d 3 ) g\equiv2\pmod3 g ≡ 2 ( mod 3 ) 3 ∤ h ( h − 1 ) 3\nmid h(h-1) 3 ∤ h ( h − 1 ) h ≡ 2 ( m o d 3 ) h\equiv2\pmod3 h ≡ 2 ( mod 3 ) 3 ∣ g − h = p m b 3\mid g-h=pmb 3 ∣ g − h = p mb 3 ∣ m b 3\mid mb 3 ∣ mb 3 ∣ m b h ( h − 1 ) 3\mid mbh(h-1) 3 ∣ mbh ( h − 1 )
We therefore define M \mathcal{M} M
M : = { m : m b ≤ 2 x 0.01 , 2 ∣ m b , 3 ∣ m b h ( h − 1 ) , ( m b , h ) = 1 , ( m b , h − 1 ) is Golomb-prime-free } . \mathcal{M}:=\{m: mb\le2x^{0.01},\ 2\mid mb,\ 3\mid mbh(h-1),\ (mb,h)=1,\ (mb,h-1)\text{ is Golomb-prime-free}\}. M := { m : mb ≤ 2 x 0.01 , 2 ∣ mb , 3 ∣ mbh ( h − 1 ) , ( mb , h ) = 1 , ( mb , h − 1 ) is Golomb-prime-free } . If N m ≠ 0 N_m\ne0 N m = 0 m ∈ M m\in\mathcal{M} m ∈ M
G n s m ′ ( x ; b , h ; x 0.99 ) = ∑ m ∈ M N m . (13) G'_{\mathrm{nsm}}(x;b,h;x^{0.99})=\sum_{m\in\mathcal{M}}N_m. \tag*{(13)} G nsm ′ ( x ; b , h ; x 0.99 ) = m ∈ M ∑ N m . (13) Fix m ∈ M m\in\mathcal{M} m ∈ M g g g g ≢ 0 ( m o d r ) g\not\equiv0\pmod r g ≡ 0 ( mod r ) r < g r<g r < g g ≢ 1 ( m o d q ) g\not\equiv1\pmod q g ≡ 1 ( mod q ) q < g q<g q < g g g g p p p
If r ∤ m b r\nmid mb r ∤ mb r ∤ h r\nmid h r ∤ h g = p m b + h ≢ 0 ( m o d r ) g=pmb+h\not\equiv0\pmod r g = p mb + h ≡ 0 ( mod r ) p ≢ − h m b ( m o d r ) p\not\equiv-\frac{h}{mb}\pmod r p ≡ − mb h ( mod r )
If q ∤ m b q\nmid mb q ∤ mb q ∤ h − 1 q\nmid h-1 q ∤ h − 1 g = p m b + h ≢ 1 ( m o d q ) g=pmb+h\not\equiv1\pmod q g = p mb + h ≡ 1 ( mod q ) p ≢ − h − 1 m b ( m o d q ) p\not\equiv-\frac{h-1}{mb}\pmod q p ≡ − mb h − 1 ( mod q )
Applying Lemma 3.5 with z m = ( x / m b ) 1 / 4 ( log ( x / m b ) ) 100 ≥ ( x 0.99 / 2 ) 1 / 4 ( log x ) 100 = : z z_m=\frac{(x/mb)^{1/4}}{(\log(x/mb))^{100}}\ge\frac{(x^{0.99}/2)^{1/4}}{(\log x)^{100}}=:z z m = ( l o g ( x / mb ) ) 100 ( x / mb ) 1/4 ≥ ( l o g x ) 100 ( x 0.99 /2 ) 1/4 =: z
N m ≤ ( 1 + o ( 1 ) ) 2 e 2 γ x m b log ( x m b ) ∏ l ≤ z l ∤ m b l ∤ h l ∈ P ∖ G ( 1 − 1 l − 1 ) ∏ q ≤ z q ∤ m b q ∤ h ( h − 1 ) q ∈ G ( 1 − 2 q − 1 ) ∏ q ≤ z q ∤ m b q ∣ h ( h − 1 ) q ∈ G ( 1 − 1 q − 1 ) . N_m\le(1+o(1))\frac{2e^{2\gamma}x}{mb\log\left(\frac{x}{mb}\right)}
\prod_{\substack{l\le z\\ l\nmid mb\\ l\nmid h\\ l\in\mathcal{P}\setminus\mathcal{G}}}\left(1-\frac{1}{l-1}\right)
\prod_{\substack{q\le z\\ q\nmid mb\\ q\nmid h(h-1)\\ q\in\mathcal{G}}}\left(1-\frac{2}{q-1}\right)
\prod_{\substack{q\le z\\ q\nmid mb\\ q\mid h(h-1)\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right). N m ≤ ( 1 + o ( 1 )) mb log ( mb x ) 2 e 2 γ x l ≤ z l ∤ mb l ∤ h l ∈ P ∖ G ∏ ( 1 − l − 1 1 ) q ≤ z q ∤ mb q ∤ h ( h − 1 ) q ∈ G ∏ ( 1 − q − 1 2 ) q ≤ z q ∤ mb q ∣ h ( h − 1 ) q ∈ G ∏ ( 1 − q − 1 1 ) . Since m b ≤ 2 x 0.01 mb\le2x^{0.01} mb ≤ 2 x 0.01 log ( x / m b ) ≥ ( 0.99 + o ( 1 ) ) log x \log(x/mb)\ge(0.99+o(1))\log x log ( x / mb ) ≥ ( 0.99 + o ( 1 )) log x
N m ≤ ( 1 + o ( 1 ) ) 2 e 2 γ x 0.99 m b log x ∏ 2 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) ∏ 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) ∏ 2 < r ≤ z r ∣ m b r ∈ P ( 1 − 1 r − 1 ) − 1 × ∏ 2 < l ≤ z l ∣ h l ∈ P ∖ G ( 1 − 1 l − 1 ) − 1 ∏ 3 < q ≤ z q ∣ h ( h − 1 ) q ∈ G ( 1 − 1 q − 2 ) − 1 ∏ 3 < q ≤ z q ∣ m b q ∈ G ( 1 − 1 q − 2 ) − 1 . \begin{aligned}
N_m\le{}&(1+o(1))\frac{2e^{2\gamma}x}{0.99mb\log x}
\prod_{\substack{2<r\le z\\ r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)
\prod_{\substack{3<q\le z\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)
\prod_{\substack{2<r\le z\\ r\mid mb\\ r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)^{-1}\\
&\times\prod_{\substack{2<l\le z\\ l\mid h\\ l\in\mathcal{P}\setminus\mathcal{G}}}\left(1-\frac{1}{l-1}\right)^{-1}
\prod_{\substack{3<q\le z\\ q\mid h(h-1)\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}
\prod_{\substack{3<q\le z\\ q\mid mb\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}.
\end{aligned} N m ≤ ( 1 + o ( 1 )) 0.99 mb log x 2 e 2 γ x 2 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) 2 < r ≤ z r ∣ mb r ∈ P ∏ ( 1 − r − 1 1 ) − 1 × 2 < l ≤ z l ∣ h l ∈ P ∖ G ∏ ( 1 − l − 1 1 ) − 1 3 < q ≤ z q ∣ h ( h − 1 ) q ∈ G ∏ ( 1 − q − 2 1 ) − 1 3 < q ≤ z q ∣ mb q ∈ G ∏ ( 1 − q − 2 1 ) − 1 . Splitting the products over r ∣ m b r\mid mb r ∣ mb q ∣ m b q\mid mb q ∣ mb b b b m m m b b b
N m ≤ ( 1 + o ( 1 ) ) 2 e 2 γ x 0.99 m b log x ∏ 2 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) ∏ 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) ∏ r ∣ b 2 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) − 1 × ∏ r ∣ m 2 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) − 1 ∏ l ∣ h 2 < l ≤ z l ∈ P ∖ G ( 1 − 1 l − 1 ) − 1 ∏ q ∣ h ( h − 1 ) 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) − 1 × ∏ q ∣ b 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) − 1 ∏ q ∣ m 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) − 1 . (14) \begin{aligned}
N_m\le{}&(1+o(1))\frac{2e^{2\gamma}x}{0.99mb\log x}
\prod_{\substack{2<r\le z\\ r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)
\prod_{\substack{3<q\le z\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)
\prod_{\substack{r\mid b\\ 2<r\le z\\ r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)^{-1}\\
&\times\prod_{\substack{r\mid m\\ 2<r\le z\\ r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)^{-1}
\prod_{\substack{l\mid h\\ 2<l\le z\\ l\in\mathcal{P}\setminus\mathcal{G}}}\left(1-\frac{1}{l-1}\right)^{-1}
\prod_{\substack{q\mid h(h-1)\\ 3<q\le z\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}\\
&\times\prod_{\substack{q\mid b\\ 3<q\le z\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}
\prod_{\substack{q\mid m\\ 3<q\le z\\ q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}. \tag*{(14)}
\end{aligned} N m ≤ ( 1 + o ( 1 )) 0.99 mb log x 2 e 2 γ x 2 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) r ∣ b 2 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) − 1 × r ∣ m 2 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) − 1 l ∣ h 2 < l ≤ z l ∈ P ∖ G ∏ ( 1 − l − 1 1 ) − 1 q ∣ h ( h − 1 ) 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) − 1 × q ∣ b 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) − 1 q ∣ m 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) − 1 . (14) Let f ( m ) f(m) f ( m ) m m m
f ( m ) = 1 m ∏ r ∣ m 2 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) − 1 ∏ q ∣ m 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) − 1 . f(m)=\frac{1}{m}\prod_{\substack{r\mid m\\2<r\leq z\\r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)^{-1}\prod_{\substack{q\mid m\\3<q\leq z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}. f ( m ) = m 1 r ∣ m 2 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) − 1 q ∣ m 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) − 1 . We need two lemmas. The first bounds the sum of f ( m ) f(m) f ( m ) m ∈ M m\in\mathcal{M} m ∈ M ( 2 x 0.01 , z ] (2x^{0.01},z] ( 2 x 0.01 , z ]
Lemma 5.1. We have
∑ m ∈ M f ( m ) ≤ ∏ r ∈ P r ∣ b ( 1 − 1 r ) − 1 ∏ l ∣ b l ∤ h l ∈ P ∖ G 2 < l ≤ 2 x 0.01 ( 1 − 1 l − 1 ) − 1 ∏ q ∣ b q ∤ h ( h − 1 ) q ∈ G 3 < q ≤ 2 x 0.01 ( 1 − 1 q − 2 ) − 1 . \sum_{m\in\mathcal{M}}f(m)\leq\prod_{\substack{r\in\mathcal{P}\\r\mid b}}\left(1-\frac{1}{r}\right)^{-1}\prod_{\substack{l\mid b\\l\nmid h\\l\in\mathcal{P}\setminus\mathcal{G}\\2<l\leq2x^{0.01}}}\left(1-\frac{1}{l-1}\right)^{-1}\prod_{\substack{q\mid b\\q\nmid h(h-1)\\q\in\mathcal{G}\\3<q\leq2x^{0.01}}}\left(1-\frac{1}{q-2}\right)^{-1}. m ∈ M ∑ f ( m ) ≤ r ∈ P r ∣ b ∏ ( 1 − r 1 ) − 1 l ∣ b l ∤ h l ∈ P ∖ G 2 < l ≤ 2 x 0.01 ∏ ( 1 − l − 1 1 ) − 1 q ∣ b q ∤ h ( h − 1 ) q ∈ G 3 < q ≤ 2 x 0.01 ∏ ( 1 − q − 2 1 ) − 1 . Lemma 5.2. We have
∏ 2 x 0.01 < q ≤ z q ∈ G ( 1 − 1 q − 1 ) − 1 = 1 + O ( 1 log 2 x ) . \prod_{\substack{2x^{0.01}<q\leq z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}=1+O\left(\frac{1}{\log_{2}x}\right). 2 x 0.01 < q ≤ z q ∈ G ∏ ( 1 − q − 1 1 ) − 1 = 1 + O ( log 2 x 1 ) . We first finish the proof of Theorem 1.5, assuming these two lemmas. Summing (5.2) over m ∈ M m\in\mathcal{M} m ∈ M ∑ m ∈ M f ( m ) \sum_{m\in\mathcal{M}}f(m) ∑ m ∈ M f ( m )
∑ m ∈ M N m ≤ ( 1 + o ( 1 ) ) 2 e 2 γ x 0.99 b log x ∏ 2 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) ∏ 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) ∏ r ∣ b 2 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) − 1 × ∏ l ∣ h 2 < l ≤ z l ∈ P ∖ G ( 1 − 1 l − 1 ) − 1 ∏ q ∣ h ( h − 1 ) 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) − 1 ∏ q ∣ b 3 < q ≤ z q ∈ G ( 1 − 1 q − 2 ) − 1 ∏ r ∈ P r ∣ b ( 1 − 1 r ) − 1 × ∏ l ∣ b l ∤ h l ∈ P ∖ G 2 < l ≤ 2 x 0.01 ( 1 − 1 l − 1 ) − 1 ∏ q ∣ b q ∤ h ( h − 1 ) q ∈ G 3 < q ≤ 2 x 0.01 ( 1 − 1 q − 2 ) − 1 . \begin{aligned}
\sum_{m\in\mathcal{M}}N_m
&\leq(1+o(1))\frac{2e^{2\gamma}x}{0.99b\log x}
\prod_{\substack{2<r\leq z\\r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)
\prod_{\substack{3<q\leq z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)
\prod_{\substack{r\mid b\\2<r\leq z\\r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)^{-1}\\
&\qquad{}\times
\prod_{\substack{l\mid h\\2<l\leq z\\l\in\mathcal{P}\setminus\mathcal{G}}}\left(1-\frac{1}{l-1}\right)^{-1}
\prod_{\substack{q\mid h(h-1)\\3<q\leq z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}
\prod_{\substack{q\mid b\\3<q\leq z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-2}\right)^{-1}
\prod_{\substack{r\in\mathcal{P}\\r\mid b}}\left(1-\frac{1}{r}\right)^{-1}\\
&\qquad{}\times
\prod_{\substack{l\mid b\\l\nmid h\\l\in\mathcal{P}\setminus\mathcal{G}\\2<l\leq2x^{0.01}}}\left(1-\frac{1}{l-1}\right)^{-1}
\prod_{\substack{q\mid b\\q\nmid h(h-1)\\q\in\mathcal{G}\\3<q\leq2x^{0.01}}}\left(1-\frac{1}{q-2}\right)^{-1}.
\end{aligned} m ∈ M ∑ N m ≤ ( 1 + o ( 1 )) 0.99 b log x 2 e 2 γ x 2 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) r ∣ b 2 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) − 1 × l ∣ h 2 < l ≤ z l ∈ P ∖ G ∏ ( 1 − l − 1 1 ) − 1 q ∣ h ( h − 1 ) 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) − 1 q ∣ b 3 < q ≤ z q ∈ G ∏ ( 1 − q − 2 1 ) − 1 r ∈ P r ∣ b ∏ ( 1 − r 1 ) − 1 × l ∣ b l ∤ h l ∈ P ∖ G 2 < l ≤ 2 x 0.01 ∏ ( 1 − l − 1 1 ) − 1 q ∣ b q ∤ h ( h − 1 ) q ∈ G 3 < q ≤ 2 x 0.01 ∏ ( 1 − q − 2 1 ) − 1 . Combining terms we get
∑ m ∈ M N m ≤ ( 1 + o ( 1 ) ) 2 e 2 γ x 0.99 ϕ ( b ) log x ∏ q ≤ z q ∈ G ( 1 − 1 q − 1 ) ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 ∏ 2 x 0.01 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) × ∏ 2 x 0.01 < q ≤ z q ∈ G ( 1 − 1 q − 1 ) − 1 . \begin{aligned}
\sum_{m\in\mathcal{M}}N_m
&\leq(1+o(1))\frac{2e^{2\gamma}x}{0.99\phi(b)\log x}
\prod_{\substack{q\leq z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)
\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}
\prod_{\substack{2x^{0.01}<r\leq z\\r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)\\
&\qquad{}\times
\prod_{\substack{2x^{0.01}<q\leq z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}.
\end{aligned} m ∈ M ∑ N m ≤ ( 1 + o ( 1 )) 0.99 ϕ ( b ) log x 2 e 2 γ x q ≤ z q ∈ G ∏ ( 1 − q − 1 1 ) q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 2 x 0.01 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) × 2 x 0.01 < q ≤ z q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . By Theorem 1.2, the product over q ≤ z q\leq z q ≤ z ( 1 + o ( 1 ) ) / log 2 x (1+o(1))/\log_{2}x ( 1 + o ( 1 )) / log 2 x
∏ 2 x 0.01 < r ≤ z r ∈ P ( 1 − 1 r − 1 ) = ( 1 + o ( 1 ) ) log ( 2 x 0.01 ) log z = 0.04 0.99 + o ( 1 ) , (15) \prod_{\substack{2x^{0.01}<r\leq z\\r\in\mathcal{P}}}\left(1-\frac{1}{r-1}\right)
=(1+o(1))\frac{\log(2x^{0.01})}{\log z}
=\frac{0.04}{0.99}+o(1), \tag*{(15)} 2 x 0.01 < r ≤ z r ∈ P ∏ ( 1 − r − 1 1 ) = ( 1 + o ( 1 )) log z log ( 2 x 0.01 ) = 0.99 0.04 + o ( 1 ) , (15) and by Lemma 5.2
∏ 2 x 0.01 < q ≤ z q ∈ G ( 1 − 1 q − 1 ) − 1 = 1 + O ( 1 log 2 x ) . \prod_{\substack{2x^{0.01}<q\le z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}=1+O\left(\frac{1}{\log_2 x}\right). 2 x 0.01 < q ≤ z q ∈ G ∏ ( 1 − q − 1 1 ) − 1 = 1 + O ( log 2 x 1 ) . We conclude that
G n s m ′ ( x ; b , h ; x 0.99 ) = ∑ m ∈ M N m ≤ ( 1 + o ( 1 ) ) 0.08 e 2 γ x 0.99 2 ϕ ( b ) log x log 2 x ∏ q ∣ b q ∈ G ( 1 − 1 q − 1 ) − 1 . G'_{\mathrm{nsm}}(x;b,h;x^{0.99})=\sum_{m\in\mathcal{M}}N_m\leq(1+o(1))\frac{0.08e^{2\gamma}x}{0.99^2\phi(b)\log x\log_2 x}\prod_{\substack{q\mid b\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}. G nsm ′ ( x ; b , h ; x 0.99 ) = m ∈ M ∑ N m ≤ ( 1 + o ( 1 )) 0.9 9 2 ϕ ( b ) log x log 2 x 0.08 e 2 γ x q ∣ b q ∈ G ∏ ( 1 − q − 1 1 ) − 1 . Since 0.08 e 2 γ / 0.99 2 < 0.259 0.08e^{2\gamma}/0.99^2<0.259 0.08 e 2 γ /0.9 9 2 < 0.259 G n s m ( x ; b , h ; x 0.99 ) ≤ G n s m ′ ( x ; b , h ; x 0.99 ) + O ( x 0.505 ) G_{\mathrm{nsm}}(x;b,h;x^{0.99})\leq G'_{\mathrm{nsm}}(x;b,h;x^{0.99})+O(x^{0.505}) G nsm ( x ; b , h ; x 0.99 ) ≤ G nsm ′ ( x ; b , h ; x 0.99 ) + O ( x 0.505 )
Proof of Lemma 5.1 . Since f f f
∑ m ∈ M f ( m ) ≤ ∏ r ∈ P r ≤ 2 x 0.01 F ( r ) . \sum_{m\in\mathcal{M}}f(m)\leq\prod_{\substack{r\in\mathcal{P}\\r\leq2x^{0.01}}}F(r). m ∈ M ∑ f ( m ) ≤ r ∈ P r ≤ 2 x 0.01 ∏ F ( r ) . where F ( r ) F(r) F ( r ) r r r
F ( l ) = 1 + f ( l ) + f ( l 2 ) + ⋯ = 1 + 1 l − 2 = ( 1 − 1 l − 1 ) − 1 . F(l)=1+f(l)+f(l^2)+\cdots=1+\frac{1}{l-2}=\left(1-\frac{1}{l-1}\right)^{-1}. F ( l ) = 1 + f ( l ) + f ( l 2 ) + ⋯ = 1 + l − 2 1 = ( 1 − l − 1 1 ) − 1 . F ( l ) = 1 + f ( l ) + f ( l 2 ) + ⋯ = 1 + 1 l + 1 l 2 + ⋯ = ( 1 − 1 l ) − 1 . F(l)=1+f(l)+f(l^2)+\cdots=1+\frac{1}{l}+\frac{1}{l^2}+\cdots=\left(1-\frac{1}{l}\right)^{-1}. F ( l ) = 1 + f ( l ) + f ( l 2 ) + ⋯ = 1 + l 1 + l 2 1 + ⋯ = ( 1 − l 1 ) − 1 . For l = 2 l=2 l = 2 F ( 2 ) = 1 F(2)=1 F ( 2 ) = 1 2 ∤ b h 2\nmid bh 2 ∤ bh 2 ∣ m 2\mid m 2 ∣ m m ∈ M m\in\mathcal{M} m ∈ M F ( 2 ) = 1 F(2)=1 F ( 2 ) = 1 2 ∣ h 2\mid h 2 ∣ h F ( 2 ) = 2 = ( 1 − 1 2 ) − 1 F(2)=2=\left(1-\frac{1}{2}\right)^{-1} F ( 2 ) = 2 = ( 1 − 2 1 ) − 1 2 ∣ b 2\mid b 2 ∣ b
F ( q ) = 1 + f ( q ) + f ( q 2 ) + ⋯ = 1 + 1 q − 3 = ( 1 − 1 q − 2 ) − 1 . F(q)=1+f(q)+f(q^2)+\cdots=1+\frac{1}{q-3}=\left(1-\frac{1}{q-2}\right)^{-1}. F ( q ) = 1 + f ( q ) + f ( q 2 ) + ⋯ = 1 + q − 3 1 = ( 1 − q − 2 1 ) − 1 . F ( q ) = 1 + f ( q ) + f ( q 2 ) + ⋯ = 1 + 1 q + 1 q 2 + ⋯ = ( 1 − 1 q ) − 1 . F(q)=1+f(q)+f(q^2)+\cdots=1+\frac{1}{q}+\frac{1}{q^2}+\cdots=\left(1-\frac{1}{q}\right)^{-1}. F ( q ) = 1 + f ( q ) + f ( q 2 ) + ⋯ = 1 + q 1 + q 2 1 + ⋯ = ( 1 − q 1 ) − 1 . For q = 3 q=3 q = 3 F ( 3 ) ≤ 1 F(3)\leq1 F ( 3 ) ≤ 1 3 ∤ b h ( h − 1 ) 3\nmid bh(h-1) 3 ∤ bh ( h − 1 ) 3 ∣ m 3\mid m 3 ∣ m m ∈ M m\in\mathcal{M} m ∈ M F ( 3 ) = 1 F(3)=1 F ( 3 ) = 1 3 ∣ h ( h − 1 ) 3\mid h(h-1) 3 ∣ h ( h − 1 ) F ( 3 ) = 3 2 = ( 1 − 1 3 ) − 1 F(3)=\frac{3}{2}=\left(1-\frac{1}{3}\right)^{-1} F ( 3 ) = 2 3 = ( 1 − 3 1 ) − 1 3 ∣ b 3\mid b 3 ∣ b
If r ∣ h r\mid h r ∣ h r r r h − 1 h-1 h − 1 r ∤ m r\nmid m r ∤ m m ∈ M m\in\mathcal{M} m ∈ M F ( r ) = 1 F(r)=1 F ( r ) = 1
Combining these, we obtain
∑ m ∈ M f ( m ) ≤ ∏ r ∈ P r ∣ b ( 1 − 1 r ) − 1 ∏ l ∈ P ∖ G 2 < l ≤ 2 x 0.01 l ∤ b l ∤ h ( 1 − 1 l − 1 ) − 1 ∏ q ∈ G 3 < q ≤ 2 x 0.01 q ∤ b q ∤ h ( h − 1 ) ( 1 − 1 q − 2 ) − 1 . \sum_{m\in\mathcal{M}}f(m)\leq
\prod_{\substack{r\in\mathcal{P}\\r\mid b}}\left(1-\frac{1}{r}\right)^{-1}
\prod_{\substack{l\in\mathcal{P}\setminus\mathcal{G}\\2<l\leq2x^{0.01}\\l\nmid b\\l\nmid h}}\left(1-\frac{1}{l-1}\right)^{-1}
\prod_{\substack{q\in\mathcal{G}\\3<q\leq2x^{0.01}\\q\nmid b\\q\nmid h(h-1)}}\left(1-\frac{1}{q-2}\right)^{-1}. m ∈ M ∑ f ( m ) ≤ r ∈ P r ∣ b ∏ ( 1 − r 1 ) − 1 l ∈ P ∖ G 2 < l ≤ 2 x 0.01 l ∤ b l ∤ h ∏ ( 1 − l − 1 1 ) − 1 q ∈ G 3 < q ≤ 2 x 0.01 q ∤ b q ∤ h ( h − 1 ) ∏ ( 1 − q − 2 1 ) − 1 . This finishes the proof of Lemma 5.1 . □
Proof of Lemma 5.2. Taking logarithms, we have
log ( ∏ 2 x 0.01 < q ≤ z q ∈ G ( 1 − 1 q − 1 ) − 1 ) = ∑ 2 x 0.01 < q ≤ z q ∈ G − log ( 1 − 1 q − 1 ) . \log\left(\prod_{\substack{2x^{0.01}<q\le z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}\right)=\sum_{\substack{2x^{0.01}<q\le z\\q\in\mathcal{G}}}-\log\left(1-\frac{1}{q-1}\right). log 2 x 0.01 < q ≤ z q ∈ G ∏ ( 1 − q − 1 1 ) − 1 = 2 x 0.01 < q ≤ z q ∈ G ∑ − log ( 1 − q − 1 1 ) . Expanding the logarithm, we see that the right-hand side equals
∑ 2 x 0.01 < q ≤ z q ∈ G 1 q + O ( x − 0.01 ) , \sum_{\substack{2x^{0.01}<q\le z\\q\in\mathcal{G}}}\frac{1}{q}+O(x^{-0.01}), 2 x 0.01 < q ≤ z q ∈ G ∑ q 1 + O ( x − 0.01 ) , which, by Lemma 3.1, is
( 1 + o ( 1 ) ) ( log 3 z − log 3 ( 2 x 0.01 ) ) + O ( 1 log x log 2 x ) . (1+o(1))\left(\log_3 z-\log_3(2x^{0.01})\right)+O\left(\frac{1}{\log x\log_2 x}\right). ( 1 + o ( 1 )) ( log 3 z − log 3 ( 2 x 0.01 ) ) + O ( log x log 2 x 1 ) . Since z = x 0.99 / 4 ( log x ) 100 z=\frac{x^{0.99/4}}{(\log x)^{100}} z = ( l o g x ) 100 x 0.99/4
log 3 ( z ) − log 3 ( 2 x 0.01 ) = O ( 1 log 2 x ) . \log_3(z)-\log_3(2x^{0.01})=O\left(\frac{1}{\log_2 x}\right). log 3 ( z ) − log 3 ( 2 x 0.01 ) = O ( log 2 x 1 ) . Substituting these estimates, we obtain
log ( ∏ 2 x 0.01 < q ≤ z q ∈ G ( 1 − 1 q − 1 ) − 1 ) = O ( 1 log 2 x ) , \log\left(\prod_{\substack{2x^{0.01}<q\le z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}\right)=O\left(\frac{1}{\log_2 x}\right), log 2 x 0.01 < q ≤ z q ∈ G ∏ ( 1 − q − 1 1 ) − 1 = O ( log 2 x 1 ) , and therefore
∏ 2 x 0.01 < q ≤ z q ∈ G ( 1 − 1 q − 1 ) − 1 = 1 + O ( 1 log 2 x ) . \prod_{\substack{2x^{0.01}<q\le z\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}=1+O\left(\frac{1}{\log_2 x}\right). 2 x 0.01 < q ≤ z q ∈ G ∏ ( 1 − q − 1 1 ) − 1 = 1 + O ( log 2 x 1 ) . This completes the proof of Lemma 5.2. □
Proof of Theorem 1.3
The goal of this section is to prove the main result which we restate below:
Theorem 1.3 (Main result). Let h h h a , b ∈ Z + a,b\in\mathbb{Z}^+ a , b ∈ Z + ( a , b ) = 1 (a,b)=1 ( a , b ) = 1 ( b , h ) = 1 (b,h)=1 ( b , h ) = 1 ( b , h − 1 ) (b,h-1) ( b , h − 1 ) h = 1 h=1 h = 1 b b b y ≥ ∣ h ∣ y\ge|h| y ≥ ∣ h ∣ B B B y y y
a b = ∑ g ∈ B 1 g − h . (16) \frac{a}{b}=\sum_{g\in B}\frac{1}{g-h}. \tag*{(16)} b a = g ∈ B ∑ g − h 1 . (16) We first explain why the conditions on b b b ( a , b ) = 1 (a,b)=1 ( a , b ) = 1 B B B ∣ h ∣ |h| ∣ h ∣ b b b g − h g-h g − h g ∈ B g\in B g ∈ B
If a prime p p p b b b h h h p ∣ g − h p\mid g-h p ∣ g − h p ∣ g p\mid g p ∣ g p = g p=g p = g g > ∣ h ∣ ≥ p g>|h|\ge p g > ∣ h ∣ ≥ p ( b , h ) = 1 (b,h)=1 ( b , h ) = 1
If a Golomb prime q q q b b b h − 1 h-1 h − 1 q ∣ g − h q\mid g-h q ∣ g − h q ∣ g − 1 q\mid g-1 q ∣ g − 1 g > q g>q g > q g ≤ q g\le q g ≤ q 0 < g − 1 < q 0<g-1<q 0 < g − 1 < q ( b , h − 1 ) (b,h-1) ( b , h − 1 )
We also note that it is enough to prove Theorem 1.3 when a / b ≤ 1 a/b \le1 a / b ≤ 1 a / b > 1 a/b > 1 a / b > 1 1 1 1 a / b a/b a / b a ′ / b a'/b a ′ / b 0 < a ′ / b ≤ 1 0 < a'/b \le1 0 < a ′ / b ≤ 1
a b = 1 + ⋯ + 1 + a ′ b . \frac{a}{b}=1+\cdots+1+\frac{a'}{b}. b a = 1 + ⋯ + 1 + b a ′ . Here a ′ = a − k b a'=a-kb a ′ = a − k b k k k b b b ( a ′ , b ) = ( a , b ) = 1 (a',b)=(a,b)=1 ( a ′ , b ) = ( a , b ) = 1 a ′ / b a'/b a ′ / b 1 1 1 1 1 1 a / b ≤ 1 a/b \le1 a / b ≤ 1 y y y a / b a/b a / b g − h g-h g − h g g g y y y a / b ≤ 1 a/b \le1 a / b ≤ 1 a / b ≤ 1 a/b \le1 a / b ≤ 1
Our main tool is the following proposition. It is a variant of [22 Proposition 5.2] and [1 Proposition 3.1] , both of which go back to [8 Proposition 3] . The difference is that we need condition (iii) with a smaller value of η \eta η [22 Proposition 5.2] allows. We obtain this by using the fact that A A A
In the proposition we use the notation as stated in § 2 : for a finite set A A A
R ( A ) = ∑ n ∈ A 1 n . R(A)=\sum_{n\in A}\frac{1}{n}. R ( A ) = n ∈ A ∑ n 1 . and for every prime power q q q q ∥ n q\parallel n q ∥ n q ∣ n q\mid n q ∣ n ( q , n / q ) = 1 (q,n/q)=1 ( q , n / q ) = 1 A q A_q A q n ∈ A n\in A n ∈ A q ∥ n q\parallel n q ∥ n
R ( A ; q ) = ∑ n ∈ A q q n , R(A;q)=\sum_{n\in A_q}\frac{q}{n}, R ( A ; q ) = n ∈ A q ∑ n q , and Q A Q_A Q A q q q q ∥ n q\parallel n q ∥ n n ∈ A n\in A n ∈ A q q q q ∈ G q\in\mathcal{G} q ∈ G
Proposition 6.1. Let h h h N N N h h h N 0.997 ≤ M ≤ N / 10 4 N^{0.997}\le M\le N/10^4 N 0.997 ≤ M ≤ N /1 0 4 A ⊆ { p − h : p prime } ∩ ( M , N ] A\subseteq\{p-h:p\text{ prime}\}\cap(M,N] A ⊆ { p − h : p prime } ∩ ( M , N ]
Every n ∈ A n\in A n ∈ A N 0.99 N^{0.99} N 0.99 n n n N 0.99 N^{0.99} N 0.99
99 100 log 2 N ≤ ω ( n ) ≤ 2 log 2 N \frac{99}{100}\log_2 N\le\omega(n)\le2\log_2 N 100 99 log 2 N ≤ ω ( n ) ≤ 2 log 2 N n ∈ A n\in A n ∈ A
R ( A ; q ) ≥ η = ( log N ) − 1 / 200 R(A;q)\ge\eta=(\log N)^{-1/200} R ( A ; q ) ≥ η = ( log N ) − 1/200 q ∈ Q A q\in Q_A q ∈ Q A
R ( A ) ≥ ( log N ) − 1 / 101 R(A)\ge(\log N)^{-1/101} R ( A ) ≥ ( log N ) − 1/101
Let Q = lcm ( A ) Q=\operatorname{lcm}(A) Q = lcm ( A ) x ∈ N x\in\mathbb{N} x ∈ N
x Q ∈ [ R ( A ) log N , ( log N log N + 1 ) R ( A ) ] , \frac{x}{Q}\in\left[\frac{R(A)}{\log N},\left(\frac{\log N}{\log N+1}\right)R(A)\right], Q x ∈ [ log N R ( A ) , ( log N + 1 log N ) R ( A ) ] , then there exists B ⊆ A B\subseteq A B ⊆ A R ( B ) = x / Q R(B)=x/Q R ( B ) = x / Q
We prove Proposition 6.1 in Appendix A. In the rest of this section we deduce Theorem 1.3 from it.
Let N N N a a a b b b h h h y y y Proposition 6.1 to write a / b a/b a / b h h h g − h g-h g − h g ∈ G g\in\mathcal{G} g ∈ G
We break the h h h ( N j + 1 , N j ] (N_{j+1},N_j] ( N j + 1 , N j ] 1 ≤ j ≤ J 1\le j\le J 1 ≤ j ≤ J N 1 = N N_1=N N 1 = N N j + 1 = N j e − 0.003 N_{j+1}=N_j^{e^{-0.003}} N j + 1 = N j e − 0.003 J = ⌊ 333 log 2 N ⌋ J=\lfloor333\log_2 N\rfloor J = ⌊ 333 log 2 N ⌋
The reciprocal sum of the h h h Θ ( 1 log 2 N ) \Theta\left(\frac{1}{\log_2 N}\right) Θ ( l o g 2 N 1 )
We prune each block to a set A j A_j A j Proposition 6.1 , with R ( A j ) = Θ ( 1 log 2 N ) R(A_j)=\Theta\left(\frac{1}{\log_2 N}\right) R ( A j ) = Θ ( l o g 2 N 1 )
(iv) We show that a fixed modulus P P P b b b ( log 2 N ) 2 (\log_{2} N)^{2} ( log 2 N ) 2 lcm ( A j ) \operatorname{lcm}(A_j) lcm ( A j ) j j j
(v) We represent suitable fractions y j / P y_j/P y j / P h h h A j A_j A j
(vi) Finally, we add the representations of y j / P y_j/P y j / P a / b a/b a / b
For 1 ≤ j ≤ J 1 \leq j \leq J 1 ≤ j ≤ J A j ′ A'_j A j ′ h h h ( N j + 1 , N j ] (N_{j+1},N_j] ( N j + 1 , N j ]
Lemma 6.2. For fixed h h h
R ( A j ′ ) = ∑ N j + 1 < g − h ≤ N j g ∈ G 1 g − h = ( 1 + o ( 1 ) ) 0.003 log 2 N j , R(A'_j)=\sum_{\substack{N_{j+1}<g-h\leq N_j\\g\in\mathcal{G}}}\frac{1}{g-h}=(1+o(1))\frac{0.003}{\log_{2}N_j}, R ( A j ′ ) = N j + 1 < g − h ≤ N j g ∈ G ∑ g − h 1 = ( 1 + o ( 1 )) log 2 N j 0.003 , uniformly for 1 ≤ j ≤ J 1 \leq j \leq J 1 ≤ j ≤ J
Proof. We have
∑ N j + 1 < g − h ≤ N j g ∈ G 1 g − h = ∑ N j + 1 < g − h ≤ N j g ∈ G 1 g + O h ( ∑ N j + 1 < g − h ≤ N j g ∈ G 1 g 2 ) = ∑ N j + 1 < g ≤ N j g ∈ G 1 g + ∑ N j < g ≤ N j + h g ∈ G 1 g − ∑ N j + 1 < g ≤ N j + 1 + h g ∈ G 1 g + O h ( ∑ N j + 1 < g − h ≤ N j g ∈ G 1 g 2 ) = ∑ N j + 1 < g ≤ N j g ∈ G 1 g + O h ( N j − 0.9 ) . \begin{aligned}
\sum_{\substack{N_{j+1}<g-h\leq N_j\\g\in\mathcal{G}}}\frac{1}{g-h}
=
\sum_{\substack{N_{j+1}<g-h\leq N_j\\g\in\mathcal{G}}}\frac{1}{g}
+O_h\left(\sum_{\substack{N_{j+1}<g-h\leq N_j\\g\in\mathcal{G}}}\frac{1}{g^2}\right) \\
&=
\sum_{\substack{N_{j+1}<g\leq N_j\\g\in\mathcal{G}}}\frac{1}{g}
+
\sum_{\substack{N_j<g\leq N_j+h\\g\in\mathcal{G}}}\frac{1}{g}
-
\sum_{\substack{N_{j+1}<g\leq N_{j+1}+h\\g\in\mathcal{G}}}\frac{1}{g}
+O_h\left(\sum_{\substack{N_{j+1}<g-h\leq N_j\\g\in\mathcal{G}}}\frac{1}{g^2}\right) \\
&=
\sum_{\substack{N_{j+1}<g\leq N_j\\g\in\mathcal{G}}}\frac{1}{g}
+O_h(N_j^{-0.9}).
\end{aligned} N j + 1 < g − h ≤ N j g ∈ G ∑ g − h 1 = N j + 1 < g − h ≤ N j g ∈ G ∑ g 1 + O h N j + 1 < g − h ≤ N j g ∈ G ∑ g 2 1 = N j + 1 < g ≤ N j g ∈ G ∑ g 1 + N j < g ≤ N j + h g ∈ G ∑ g 1 − N j + 1 < g ≤ N j + 1 + h g ∈ G ∑ g 1 + O h N j + 1 < g − h ≤ N j g ∈ G ∑ g 2 1 = N j + 1 < g ≤ N j g ∈ G ∑ g 1 + O h ( N j − 0.9 ) . Since N j + 1 = N j e − 0.003 N_{j+1}=N_j e^{-0.003} N j + 1 = N j e − 0.003 log 2 N j + 1 = log 2 N j − 0.003 \log_{2}N_{j+1}=\log_{2}N_j-0.003 log 2 N j + 1 = log 2 N j − 0.003
log 3 N j + 1 = log 3 N j − 0.003 log 2 N j + O ( 1 ( log 2 N j ) 2 ) . \log_{3}N_{j+1}
=
\log_{3}N_j-\frac{0.003}{\log_{2}N_j}
+O\left(\frac{1}{(\log_{2}N_j)^2}\right). log 3 N j + 1 = log 3 N j − log 2 N j 0.003 + O ( ( log 2 N j ) 2 1 ) . Therefore, by Lemma 3.1,
∑ N j + 1 < g − h ≤ N j g ∈ G 1 g − h = ( 1 + o ( 1 ) ) ( log 3 N j − log 3 N j + 1 ) + O ( 1 log N j + 1 log 2 N j + 1 ) + O h ( N j − 0.9 ) = ( 1 + o ( 1 ) ) 0.003 log 2 N j . \begin{aligned}
\sum_{\substack{N_{j+1}<g-h\leq N_j\\g\in\mathcal{G}}}\frac{1}{g-h}
=
(1+o(1))(\log_{3}N_j-\log_{3}N_{j+1})
+O\left(\frac{1}{\log N_{j+1}\log_{2}N_{j+1}}\right)
+O_h(N_j^{-0.9}) \\
&=(1+o(1))\frac{0.003}{\log_{2}N_j}.
\end{aligned} N j + 1 < g − h ≤ N j g ∈ G ∑ g − h 1 = ( 1 + o ( 1 )) ( log 3 N j − log 3 N j + 1 ) + O ( log N j + 1 log 2 N j + 1 1 ) + O h ( N j − 0.9 ) = ( 1 + o ( 1 )) log 2 N j 0.003 . We now prove three estimates, Lemmas 6.3, 6.4 and 6.5, which we use to show that the pruning steps below remove only a small part of the reciprocal sum.
Lemma 6.3. There is a constant δ > 0.00005 \delta>0.00005 δ > 0.00005
# { p ≤ N : ω ( p − h ) < 0.99 log 2 N } ≪ h N ( log 2 N ) O ( 1 ) ( log N ) 1 + δ . \#\{p\leq N:\omega(p-h)<0.99\log_{2}N\}\ll_h\frac{N(\log_{2}N)^{O(1)}}{(\log N)^{1+\delta}}. # { p ≤ N : ω ( p − h ) < 0.99 log 2 N } ≪ h ( log N ) 1 + δ N ( log 2 N ) O ( 1 ) . Proof. By [15 Corollary 1] , for every nonzero integer a a a k ≥ 1 k\geq1 k ≥ 1
# { − a < p ≤ x : ω ( p + a s ) = k } ≪ ∣ a ∣ ϕ ( ∣ a ∣ ) x ( log log x + O ( 1 ) ) k − 1 ( k − 1 ) ! ( log x ) 2 , \#\left\{-a<p\leq x:\omega\left(\frac{p+a}{s}\right)=k\right\}
\ll\frac{|a|}{\phi(|a|)}\frac{x(\log\log x+O(1))^{k-1}}{(k-1)!(\log x)^2}, # { − a < p ≤ x : ω ( s p + a ) = k } ≪ ϕ ( ∣ a ∣ ) ∣ a ∣ ( k − 1 )! ( log x ) 2 x ( log log x + O ( 1 ) ) k − 1 , where s = ( 2 , a + 1 ) s=(2,a+1) s = ( 2 , a + 1 ) a = − h a=-h a = − h s = ( 2 , h + 1 ) s=(2,h+1) s = ( 2 , h + 1 ) h h h s = 1 s=1 s = 1 h h h s = 2 s=2 s = 2 ω ( p − h 2 ) ≤ ω ( p − h ) \omega\left(\frac{p-h}{2}\right)\leq\omega(p-h) ω ( 2 p − h ) ≤ ω ( p − h ) ω ( p − h ) < 0.99 log 2 N \omega(p-h)<0.99\log_{2}N ω ( p − h ) < 0.99 log 2 N ω ( p − h s ) < 0.99 log 2 N \omega\left(\frac{p-h}{s}\right)<0.99\log_{2}N ω ( s p − h ) < 0.99 log 2 N k < 0.99 log 2 N k < 0.99\log_{2} N k < 0.99 log 2 N
# { h < p ≤ N : ω ( p − h ) < 0.99 log 2 N } ≪ h ∑ k < 0.99 log 2 N N ( log log N + O ( 1 ) ) k − 1 ( k − 1 ) ! ( log N ) 2 \#\{h < p \le N : \omega(p-h) < 0.99\log_{2} N\} \ll_{h} \sum_{k<0.99\log_{2} N}\frac{N(\log\log N+O(1))^{k-1}}{(k-1)!(\log N)^{2}} # { h < p ≤ N : ω ( p − h ) < 0.99 log 2 N } ≪ h k < 0.99 l o g 2 N ∑ ( k − 1 )! ( log N ) 2 N ( log log N + O ( 1 ) ) k − 1 The term with k = 1 k=1 k = 1 N / ( log N ) 2 N/(\log N)^{2} N / ( log N ) 2 log ( t ! ) = t log t − t + O ( log t ) \log(t!)=t\log t-t+O(\log t) log ( t !) = t log t − t + O ( log t )
≪ N ( log N ) 2 ∑ 2 ≤ k < 0.99 log 2 N exp ( ( k − 1 ) ( log 3 N − log ( k − 1 ) + 1 + O ( 1 log 2 N + log ( k − 1 ) k − 1 ) ) ) ≪ N ( log 2 N ) O ( 1 ) ( log N ) 2 ∑ 2 ≤ k < 0.99 log 2 N exp ( ( k − 1 ) ( log 3 N − log ( k − 1 ) + 1 ) ) \begin{aligned}
\ll\frac{N}{(\log N)^{2}}\sum_{2\le k<0.99\log_{2} N}\exp\left((k-1)\left(\log_{3}N-\log(k-1)+1+O\left(\frac{1}{\log_{2}N}+\frac{\log(k-1)}{k-1}\right)\right)\right) \\
&\ll\frac{N(\log_{2}N)^{O(1)}}{(\log N)^{2}}\sum_{2\le k<0.99\log_{2} N}\exp\left((k-1)(\log_{3}N-\log(k-1)+1)\right)
\end{aligned} ≪ ( log N ) 2 N 2 ≤ k < 0.99 l o g 2 N ∑ exp ( ( k − 1 ) ( log 3 N − log ( k − 1 ) + 1 + O ( log 2 N 1 + k − 1 log ( k − 1 ) ) ) ) ≪ ( log N ) 2 N ( log 2 N ) O ( 1 ) 2 ≤ k < 0.99 l o g 2 N ∑ exp ( ( k − 1 ) ( log 3 N − log ( k − 1 ) + 1 ) ) The function f ( t ) = t ( log 3 N − log t + 1 ) f(t)=t(\log_{3}N-\log t+1) f ( t ) = t ( log 3 N − log t + 1 ) 0 < t < log 2 N 0<t<\log_{2}N 0 < t < log 2 N exp ( 0.99 ( 1 − log 0.99 ) log 2 N ) \exp(0.99(1-\log0.99)\log_{2}N) exp ( 0.99 ( 1 − log 0.99 ) log 2 N ) log 2 N \log_{2}N log 2 N
≪ N ( log 2 N ) O ( 1 ) ( log N ) 2 exp ( 0.99 ( 1 − log 0.99 ) log 2 N ) = N ( log 2 N ) O ( 1 ) ( log N ) 1 + δ , \begin{aligned}
\ll\frac{N(\log_{2}N)^{O(1)}}{(\log N)^{2}}\exp(0.99(1-\log0.99)\log_{2}N) \\
&= \frac{N(\log_{2}N)^{O(1)}}{(\log N)^{1+\delta}},
\end{aligned} ≪ ( log N ) 2 N ( log 2 N ) O ( 1 ) exp ( 0.99 ( 1 − log 0.99 ) log 2 N ) = ( log N ) 1 + δ N ( log 2 N ) O ( 1 ) , where δ > 0.00005 \delta>0.00005 δ > 0.00005
Lemma 6.4. We have
# { p ≤ N : ω ( p − h ) > 2 log 2 N } ≪ h N ( log 2 N ) O ( 1 ) ( log N ) 2 log 2 . \#\{p\le N:\omega(p-h)>2\log_{2}N\}\ll_{h}\frac{N(\log_{2}N)^{O(1)}}{(\log N)^{2\log2}}. # { p ≤ N : ω ( p − h ) > 2 log 2 N } ≪ h ( log N ) 2 l o g 2 N ( log 2 N ) O ( 1 ) . Proof. As in the proof of Lemma 6.3, we apply [15 Corollary 1] with a = − h a=-h a = − h s = ( 2 , h + 1 ) s=(2,h+1) s = ( 2 , h + 1 ) s ≤ 2 s\le2 s ≤ 2 ω ( p − h s ) ≥ ω ( p − h ) − 1 \omega\left(\frac{p-h}{s}\right)\ge\omega(p-h)-1 ω ( s p − h ) ≥ ω ( p − h ) − 1 p > h p>h p > h ω ( p − h ) > 2 log 2 N \omega(p-h)>2\log_{2}N ω ( p − h ) > 2 log 2 N ω ( p − h s ) > 2 log 2 N − 1 \omega\left(\frac{p-h}{s}\right)>2\log_{2}N-1 ω ( s p − h ) > 2 log 2 N − 1
# { h < p ≤ N : ω ( p − h ) > 2 log 2 N } ≪ h ∑ k > 2 log 2 N − 1 N ( log log N + O ( 1 ) ) k − 1 ( k − 1 ) ! ( log N ) 2 \#\{h<p\le N:\omega(p-h)>2\log_{2}N\}\ll_{h}\sum_{k>2\log_{2}N-1}\frac{N(\log\log N+O(1))^{k-1}}{(k-1)!(\log N)^{2}} # { h < p ≤ N : ω ( p − h ) > 2 log 2 N } ≪ h k > 2 l o g 2 N − 1 ∑ ( k − 1 )! ( log N ) 2 N ( log log N + O ( 1 ) ) k − 1 Let k 0 k_{0} k 0 k 0 > 2 log 2 N − 1 k_{0}>2\log_{2}N-1 k 0 > 2 log 2 N − 1 k ≥ k 0 k\ge k_{0} k ≥ k 0
log 2 N + O ( 1 ) k − 1 ≤ log 2 N + O ( 1 ) 2 log 2 N ≤ 0.6 , \frac{\log_{2}N+O(1)}{k-1}\le\frac{\log_{2}N+O(1)}{2\log_{2}N}\le0.6, k − 1 log 2 N + O ( 1 ) ≤ 2 log 2 N log 2 N + O ( 1 ) ≤ 0.6 , for N N N
# { h < p ≤ N : ω ( p − h ) > 2 log 2 N } ≪ h N ( log N ) 2 ( log 2 N + O ( 1 ) ) k 0 − 1 ( k 0 − 1 ) ! ( 1 + 0.6 + 0.6 2 + ⋯ ) ≪ N ( log N ) 2 ( log 2 N + O ( 1 ) ) k 0 − 1 ( k 0 − 1 ) ! . \begin{aligned}
\#\{h<p\le N:\omega(p-h)>2\log_{2}N\}\ll_{h}\frac{N}{(\log N)^{2}}\frac{(\log_{2}N+O(1))^{k_{0}-1}}{(k_{0}-1)!}(1+0.6+0.6^{2}+\cdots) \\
&\ll\frac{N}{(\log N)^{2}}\frac{(\log_{2}N+O(1))^{k_{0}-1}}{(k_{0}-1)!}.
\end{aligned} # { h < p ≤ N : ω ( p − h ) > 2 log 2 N } ≪ h ( log N ) 2 N ( k 0 − 1 )! ( log 2 N + O ( 1 ) ) k 0 − 1 ( 1 + 0.6 + 0. 6 2 + ⋯ ) ≪ ( log N ) 2 N ( k 0 − 1 )! ( log 2 N + O ( 1 ) ) k 0 − 1 . Note that k 0 = 2 log 2 N + O ( 1 ) k_0 = 2\log_2 N + O(1) k 0 = 2 log 2 N + O ( 1 ) log ( t ! ) = t log t − t + O ( log t ) \log(t!) = t\log t - t + O(\log t) log ( t !) = t log t − t + O ( log t )
≪ N ( log N ) 2 exp ( 2 log 2 N ( log 3 N − log ( 2 log 2 N ) + 1 ) + O ( log 3 N ) ) ≪ N ( log 2 N ) O ( 1 ) ( log N ) 2 exp ( 2 log 2 N ( 1 − log 2 ) ) = N ( log 2 N ) O ( 1 ) ( log N ) 2 ( log N ) 2 − 2 log 2 = N ( log 2 N ) O ( 1 ) ( log N ) 2 log 2 . \begin{aligned}
\ll\frac{N}{(\log N)^2}\exp\left(2\log_2 N(\log_3 N-\log(2\log_2 N)+1)+O(\log_3 N)\right) \\
&\ll\frac{N(\log_2 N)^{O(1)}}{(\log N)^2}\exp\left(2\log_2 N(1-\log2)\right) \\
&= \frac{N(\log_2 N)^{O(1)}}{(\log N)^2}(\log N)^{2-2\log2} \\
&= \frac{N(\log_2 N)^{O(1)}}{(\log N)^{2\log2}}.
\end{aligned} ≪ ( log N ) 2 N exp ( 2 log 2 N ( log 3 N − log ( 2 log 2 N ) + 1 ) + O ( log 3 N ) ) ≪ ( log N ) 2 N ( log 2 N ) O ( 1 ) exp ( 2 log 2 N ( 1 − log 2 ) ) = ( log N ) 2 N ( log 2 N ) O ( 1 ) ( log N ) 2 − 2 l o g 2 = ( log N ) 2 l o g 2 N ( log 2 N ) O ( 1 ) . Lemma 6.5. Let N N N A ⊆ [ 1 , N ] A \subseteq[1,N] A ⊆ [ 1 , N ] η > 0 \eta> 0 η > 0 A ′ ⊆ A A' \subseteq A A ′ ⊆ A
R ( A ′ ) ≥ R ( A ) − 1.5 η log 2 N and R ( A ′ ; q ) ≥ η for all q ∈ Q A ′ . R(A') \ge R(A)-1.5\eta\log_2 N \qquad\text{and}\qquad R(A';q)\ge\eta\quad\text{for all }q\in Q_{A'}. R ( A ′ ) ≥ R ( A ) − 1.5 η log 2 N and R ( A ′ ; q ) ≥ η for all q ∈ Q A ′ . Proof. We construct A ′ A' A ′ A 0 = A A_0=A A 0 = A A i A_i A i q i ∈ Q A i q_i\in Q_{A_i} q i ∈ Q A i R ( A i ; q i ) < η R(A_i;q_i)<\eta R ( A i ; q i ) < η ( A i ) q i (A_i)_{q_i} ( A i ) q i A i + 1 = A i ∖ ( A i ) q i A_{i+1}=A_i\setminus(A_i)_{q_i} A i + 1 = A i ∖ ( A i ) q i
R ( A i + 1 ) = R ( A i ) − R ( A i ; q i ) q i ≥ R ( A i ) − η q i . R(A_{i+1})=R(A_i)-\frac{R(A_i;q_i)}{q_i}\ge R(A_i)-\frac{\eta}{q_i}. R ( A i + 1 ) = R ( A i ) − q i R ( A i ; q i ) ≥ R ( A i ) − q i η . Since A A A k k k A ′ : = A k A':=A_k A ′ := A k R ( A ′ ; q ) ≥ η R(A';q)\ge\eta R ( A ′ ; q ) ≥ η q ∈ Q A ′ q\in Q_{A'} q ∈ Q A ′ q i ∉ Q A i ′ q_i\notin Q_{A_{i'}} q i ∈ / Q A i ′ i ′ > i i'>i i ′ > i q 0 , … , q k − 1 q_0,\ldots,q_{k-1} q 0 , … , q k − 1 N N N
R ( A ′ ) ≥ R ( A ) − ∑ i = 0 k − 1 η q i ≥ R ( A ) − η ∑ q ≤ N q prime power 1 q ≥ R ( A ) − 1.5 η log 2 N . R(A')\ge R(A)-\sum_{i=0}^{k-1}\frac{\eta}{q_i}\ge R(A)-\eta\sum_{\substack{q\le N\\q\text{ prime power}}}\frac{1}{q}\ge R(A)-1.5\eta\log_2 N. R ( A ′ ) ≥ R ( A ) − i = 0 ∑ k − 1 q i η ≥ R ( A ) − η q ≤ N q prime power ∑ q 1 ≥ R ( A ) − 1.5 η log 2 N . We now prune A j ′ A'_j A j ′ A j A_j A j N = N j N=N_j N = N j M = N j + 1 M=N_{j+1} M = N j + 1
We first remove the elements of A j ′ A'_j A j ′ N j 0.99 N_j^{0.99} N j 0.99 ( A j ′ ) n s m (A'_j)_{\mathrm{nsm}} ( A j ′ ) nsm n = g − h ∈ ( A j ′ ) n s m n=g-h\in(A'_j)_{\mathrm{nsm}} n = g − h ∈ ( A j ′ ) nsm n ≤ t ≤ N j n\le t\le N_j n ≤ t ≤ N j g − h g-h g − h N j 0.99 ≥ t 0.99 N_j^{0.99}\ge t^{0.99} N j 0.99 ≥ t 0.99 b = 1 b=1 b = 1
R ( ( A j ′ ) n s m ) ≤ 0.259 log N j log 2 N j + ∫ N j + 1 N j 0.259 t log t log 2 t d t ≤ ( 1 + o ( 1 ) ) 0.000777 log 2 N j . R((A'_j)_{\mathrm{nsm}})\le\frac{0.259}{\log N_j\log_2 N_j}+\int_{N_{j+1}}^{N_j}\frac{0.259}{t\log t\log_2 t}\,dt\le(1+o(1))\frac{0.000777}{\log_2 N_j}. R (( A j ′ ) nsm ) ≤ log N j log 2 N j 0.259 + ∫ N j + 1 N j t log t log 2 t 0.259 d t ≤ ( 1 + o ( 1 )) log 2 N j 0.000777 . We then remove the elements n n n ω ( n ) < 0.99 log 2 N j \omega(n)<0.99\log_2 N_j ω ( n ) < 0.99 log 2 N j ω ( n ) > 2 log 2 N j \omega(n)>2\log_2 N_j ω ( n ) > 2 log 2 N j ( A j ′ ) ω (A'_j)_\omega ( A j ′ ) ω
R ( ( A j ′ ) ω ) ≪ ( log 2 N j ) O ( 1 ) ( log N j ) δ + ( log 2 N j ) O ( 1 ) ( log N j ) 2 log 2 − 1 = o ( 1 log 2 N j ) . R((A'_j)_\omega)\ll\frac{(\log_2 N_j)^{O(1)}}{(\log N_j)^\delta}+\frac{(\log_2 N_j)^{O(1)}}{(\log N_j)^{2\log2-1}}=o\left(\frac{1}{\log_2 N_j}\right). R (( A j ′ ) ω ) ≪ ( log N j ) δ ( log 2 N j ) O ( 1 ) + ( log N j ) 2 l o g 2 − 1 ( log 2 N j ) O ( 1 ) = o ( log 2 N j 1 ) . Finally, we apply Lemma 6.5 to the remaining set, with N j N_j N j N N N η = ( log N j ) − 1 / 200 \eta=(\log N_j)^{-1/200} η = ( log N j ) − 1/200 A j A_j A j
1.5 ( log N j ) − 1 / 200 log 2 N j = o ( 1 / log 2 N j ) . 1.5(\log N_j)^{-1/200}\log_2 N_j=o(1/\log_2 N_j). 1.5 ( log N j ) − 1/200 log 2 N j = o ( 1/ log 2 N j ) . Collecting these bounds and using Lemma 6.2 , we get
R ( A j ) ≥ ( 1 + o ( 1 ) ) 0.003 log 2 N j − ( 1 + o ( 1 ) ) 0.000777 log 2 N j − o ( 1 log 2 N j ) = ( 1 + o ( 1 ) ) 0.002223 log 2 N j , R(A_j) \ge(1+o(1))\frac{0.003}{\log_2 N_j}-(1+o(1))\frac{0.000777}{\log_2 N_j}-o\left(\frac{1}{\log_2 N_j}\right)=(1+o(1))\frac{0.002223}{\log_2 N_j}, R ( A j ) ≥ ( 1 + o ( 1 )) log 2 N j 0.003 − ( 1 + o ( 1 )) log 2 N j 0.000777 − o ( log 2 N j 1 ) = ( 1 + o ( 1 )) log 2 N j 0.002223 , uniformly for 1 ≤ j ≤ J 1\le j\le J 1 ≤ j ≤ J A j A_j A j Proposition 6.1 with N j N_j N j N N N R ( A j ) ≫ 1 / log 2 N j R(A_j)\gg1/\log_2 N_j R ( A j ) ≫ 1/ log 2 N j
Let x 0 = 2 log 3 N x_0=2\log_3 N x 0 = 2 log 3 N
P : = b ∏ l ≤ x 0 l ∉ G l ∤ b h l . P:=b\prod_{\substack{l\le x_0\\l\notin\mathcal{G}\\l\nmid bh}}l. P := b l ≤ x 0 l ∈ / G l ∤ bh ∏ l . where l l l l ≤ x 0 l\le x_0 l ≤ x 0 b h bh bh Theorem 1.2 , the product of the primes l ≤ x 0 l\le x_0 l ≤ x 0 exp ( 2 log 3 N − ( 2 + o ( 1 ) ) log 3 N / log 5 N ) \exp(2\log_3 N-(2+o(1))\log_3 N/\log_5 N) exp ( 2 log 3 N − ( 2 + o ( 1 )) log 3 N / log 5 N ) b h bh bh b ∣ h ∣ b|h| b ∣ h ∣ N N N
( log 2 N ) 1.9 ≤ P ≤ b ( log 2 N ) 2.1 . (17) (\log_2 N)^{1.9}\le P\le b(\log_2 N)^{2.1}. \tag*{(17)} ( log 2 N ) 1.9 ≤ P ≤ b ( log 2 N ) 2.1 . (17) We now show that P P P lcm ( A j ) \operatorname{lcm}(A_j) lcm ( A j ) 1 ≤ j ≤ J 1\le j\le J 1 ≤ j ≤ J
Lemma 6.6. For N N N a a a b b b h h h P ∣ Q j P\mid Q_j P ∣ Q j 1 ≤ j ≤ J 1\le j\le J 1 ≤ j ≤ J Q j = lcm ( A j ) Q_j=\operatorname{lcm}(A_j) Q j = lcm ( A j )
Proof. Fix j j j m m m b b b l l l P P P ( h , m ) = 1 (h,m)=1 ( h , m ) = 1 ( h − 1 , m ) (h-1,m) ( h − 1 , m ) A j ′ A'_j A j ′ m m m g − h g-h g − h g ≡ h ( m o d m ) g\equiv h\pmod m g ≡ h ( mod m )
( 1 + o ( 1 ) ) 0.003 ϕ ( m ) log 2 N j ∏ q ∣ m q ∈ G ( 1 − 1 q − 1 ) − 1 , (18) (1+o(1))\frac{0.003}{\phi(m)\log_2 N_j}\prod_{\substack{q\mid m\\q\in\mathcal{G}}}\left(1-\frac{1}{q-1}\right)^{-1}, \tag*{(18)} ( 1 + o ( 1 )) ϕ ( m ) log 2 N j 0.003 q ∣ m q ∈ G ∏ ( 1 − q − 1 1 ) − 1 , (18) and by Theorem 1.5 (with m m m b b b ( A j ′ ) n s m (A'_j)_{\mathrm{nsm}} ( A j ′ ) nsm 0.259 + o ( 1 ) 0.259+o(1) 0.259 + o ( 1 ) (18) . On the other hand, the second and third pruning steps remove elements with total reciprocal sum
≪ ( log 2 N j ) O ( 1 ) ( log N j ) δ + ( log 2 N j ) O ( 1 ) ( log N j ) 2 log 2 − 1 + log 2 N j ( log N j ) 1 / 200 ≪ ( log N j ) − δ / 2 , \ll\frac{(\log_2 N_j)^{O(1)}}{(\log N_j)^\delta}+\frac{(\log_2 N_j)^{O(1)}}{(\log N_j)^{2\log2-1}}+\frac{\log_2 N_j}{(\log N_j)^{1/200}}\ll(\log N_j)^{-\delta/2}, ≪ ( log N j ) δ ( log 2 N j ) O ( 1 ) + ( log N j ) 2 l o g 2 − 1 ( log 2 N j ) O ( 1 ) + ( log N j ) 1/200 log 2 N j ≪ ( log N j ) − δ /2 , which is much smaller than the reciprocal sum of the elements of A j ′ A'_j A j ′ m m m A j A_j A j m m m
( 0.74 + o ( 1 ) ) 0.003 ϕ ( m ) log 2 N j > 0. (0.74+o(1))\frac{0.003}{\phi(m)\log_2 N_j}>0. ( 0.74 + o ( 1 )) ϕ ( m ) log 2 N j 0.003 > 0. In particular, some element of A j A_j A j m m m m ∣ Q j m\mid Q_j m ∣ Q j b b b l l l P P P P ∣ Q j P\mid Q_j P ∣ Q j
Define y j : = ⌊ P R ( A j ) ⌋ − 1 y_j:=\lfloor P R(A_j)\rfloor-1 y j := ⌊ P R ( A j )⌋ − 1
y j P = R ( A j ) − ε j for some ε j ∈ [ 1 P , 2 P ] . \frac{y_j}{P}=R(A_j)-\varepsilon_j\qquad\text{for some }\varepsilon_j\in\left[\frac{1}{P},\frac{2}{P}\right]. P y j = R ( A j ) − ε j for some ε j ∈ [ P 1 , P 2 ] . We now use Proposition 6.1 , with N j N_j N j N N N y j / P y_j/P y j / P A j A_j A j P ∣ Q j P\mid Q_j P ∣ Q j Lemma 6.6 , we have y j / P = x j / Q j y_j/P=x_j/Q_j y j / P = x j / Q j x j : = y j Q j / P ∈ N x_j:=y_jQ_j/P\in\mathbb{N} x j := y j Q j / P ∈ N y j / P y_j/P y j / P [ R ( A j ) log N j , ( log N j log N j + 1 ) R ( A j ) ] \left[\frac{R(A_j)}{\log N_j},\left(\frac{\log N_j}{\log N_j+1}\right)R(A_j)\right] [ l o g N j R ( A j ) , ( l o g N j + 1 l o g N j ) R ( A j ) ]
y j P = R ( A j ) − ε j ≥ R ( A j ) − 2 P > R ( A j ) 2 , \frac{y_j}{P}=R(A_j)-\varepsilon_j\ge R(A_j)-\frac{2}{P}>\frac{R(A_j)}{2}, P y j = R ( A j ) − ε j ≥ R ( A j ) − P 2 > 2 R ( A j ) , as 1 / P ≤ ( log 2 N ) − 1.9 1/P\le(\log_2 N)^{-1.9} 1/ P ≤ ( log 2 N ) − 1.9 R ( A j ) ≫ 1 / log 2 N R(A_j)\gg1/\log_2 N R ( A j ) ≫ 1/ log 2 N ε j ≥ R ( A j ) log N j + 1 \varepsilon_j\ge\frac{R(A_j)}{\log N_j+1} ε j ≥ l o g N j + 1 R ( A j )
ε j ≥ 1 P ≥ 1 b ( log 2 N ) 2.1 ≥ R ( A j ) log N j + 1 . \varepsilon_j\ge\frac{1}{P}\ge\frac{1}{b(\log_2 N)^{2.1}}\ge\frac{R(A_j)}{\log N_j+1}. ε j ≥ P 1 ≥ b ( log 2 N ) 2.1 1 ≥ log N j + 1 R ( A j ) . Since log 2 N j = log 2 N − 0.003 ( j − 1 ) \log_2N_j=\log_2N-0.003(j-1) log 2 N j = log 2 N − 0.003 ( j − 1 ) J = ⌊ 333 log 2 N ⌋ J=\lfloor333\log_2N\rfloor J = ⌊ 333 log 2 N ⌋ R ( A j ) R(A_j) R ( A j )
∑ 1 ≤ j ≤ J R ( A j ) ≥ ( 1 + o ( 1 ) ) ∑ 1 ≤ j ≤ J 0.002223 log 2 N − 0.003 ( j − 1 ) = ( 0.741 + o ( 1 ) ) log 1000 > 5. \sum_{1\le j\le J}R(A_j)\ge(1+o(1))\sum_{1\le j\le J}\frac{0.002223}{\log_2N-0.003(j-1)}=(0.741+o(1))\log1000>5. 1 ≤ j ≤ J ∑ R ( A j ) ≥ ( 1 + o ( 1 )) 1 ≤ j ≤ J ∑ log 2 N − 0.003 ( j − 1 ) 0.002223 = ( 0.741 + o ( 1 )) log 1000 > 5. Since ∑ j ≤ J ε j ≤ 2 J / P = o ( 1 ) \sum_{j\le J}\varepsilon_j\le2J/P=o(1) ∑ j ≤ J ε j ≤ 2 J / P = o ( 1 ) ∑ j ≤ J y j / P > 1 ≥ a / b \sum_{j\le J}y_j/P>1\ge a/b ∑ j ≤ J y j / P > 1 ≥ a / b
a b = ∑ j ≤ k y j P \frac{a}{b}=\sum_{j\le k}\frac{y_j}{P} b a = j ≤ k ∑ P y j for some k k k 0 ≤ k < J 0\le k<J 0 ≤ k < J
∑ 1 ≤ j ≤ k y j P < a b < ∑ 1 ≤ j ≤ k + 1 y j P . \sum_{1\le j\le k}\frac{y_j}{P}<\frac{a}{b}<\sum_{1\le j\le k+1}\frac{y_j}{P}. 1 ≤ j ≤ k ∑ P y j < b a < 1 ≤ j ≤ k + 1 ∑ P y j . Since b ∣ P b\mid P b ∣ P a b − ∑ 1 ≤ j ≤ k y j P \frac{a}{b}-\sum_{1\le j\le k}\frac{y_j}{P} b a − ∑ 1 ≤ j ≤ k P y j 1 / P 1/P 1/ P
1 P ≤ a b − ∑ 1 ≤ j ≤ k y j P < y k + 1 P ≤ ( log N k + 1 log N k + 1 + 1 ) R ( A k + 1 ) . \frac{1}{P}\le\frac{a}{b}-\sum_{1\le j\le k}\frac{y_j}{P}<\frac{y_{k+1}}{P}\le\left(\frac{\log N_{k+1}}{\log N_{k+1}+1}\right)R(A_{k+1}). P 1 ≤ b a − 1 ≤ j ≤ k ∑ P y j < P y k + 1 ≤ ( log N k + 1 + 1 log N k + 1 ) R ( A k + 1 ) . Moreover, since b ≤ log 2 N b\le\log_2N b ≤ log 2 N
1 P ≥ 1 b ( log 2 N ) 2.1 ≥ 1 ( log 2 N ) 3.1 ≥ R ( A k + 1 ) log N k + 1 . \frac{1}{P}\ge\frac{1}{b(\log_2N)^{2.1}}\ge\frac{1}{(\log_2N)^{3.1}}\ge\frac{R(A_{k+1})}{\log N_{k+1}}. P 1 ≥ b ( log 2 N ) 2.1 1 ≥ ( log 2 N ) 3.1 1 ≥ log N k + 1 R ( A k + 1 ) . Hence, by Proposition 6.1 and Lemma 6.6, we can use A k + 1 A_{k+1} A k + 1 a b − ∑ 1 ≤ j ≤ k y j P \frac{a}{b}-\sum_{1\le j\le k}\frac{y_j}{P} b a − ∑ 1 ≤ j ≤ k P y j A j A_j A j a / b a/b a / b 1 / ( g − h ) 1/(g-h) 1/ ( g − h ) g g g A j A_j A j N J + 1 N_{J+1} N J + 1 N J + 1 > y + ∣ h ∣ N_{J+1}>y+|h| N J + 1 > y + ∣ h ∣ N N N y y y
Proof of Proposition 6.1
The setup follows the proof of [22 Proposition 5.2] , and our treatment of the minor arcs follows [1 Proposition 3.1] . Throughout this appendix, q q q
τ = x / Q R ( A ) . \tau=\frac{x/Q}{R(A)}. τ = R ( A ) x / Q . Then τ ∈ [ 1 log N , log N 1 + log N ] \tau\in\left[\frac{1}{\log N},\frac{\log N}{1+\log N}\right] τ ∈ [ l o g N 1 , 1 + l o g N l o g N ] x / Q x/Q x / Q B ⊆ A B \subseteq A B ⊆ A n ∈ A n \in A n ∈ A B B B τ \tau τ E ( R ( B ) ) = τ R ( A ) = x / Q \mathbb{E}(R(B))=\tau R(A)=x/Q E ( R ( B )) = τ R ( A ) = x / Q
1 R ( B ) − x / Q ∈ Z = 1 Q ∑ − Q / 2 < t ≤ Q / 2 e ( t ( R ( B ) − x Q ) ) . \mathbf{1}_{R(B)-x/Q\in\mathbb{Z}}=\frac{1}{Q}\sum_{-Q/2<t\le Q/2}e\left(t\left(R(B)-\frac{x}{Q}\right)\right). 1 R ( B ) − x / Q ∈ Z = Q 1 − Q /2 < t ≤ Q /2 ∑ e ( t ( R ( B ) − Q x ) ) . Taking expectations and using independence, we get
P ( R ( B ) − x Q ∈ Z ) = 1 Q ∑ − Q / 2 < t ≤ Q / 2 e ( − t x Q ) ∏ n ∈ A E e ( t 1 n ∈ B n ) = 1 Q ∑ − Q / 2 < t ≤ Q / 2 e ( − t x Q ) ∏ n ∈ A ( 1 − τ + τ e ( t n ) ) . \begin{aligned}
\mathbb{P}\left(R(B)-\frac{x}{Q}\in\mathbb{Z}\right)=\frac{1}{Q}\sum_{-Q/2<t\le Q/2}e\left(-\frac{tx}{Q}\right)\prod_{n\in A}\mathbb{E}e\left(\frac{t\mathbf{1}_{n\in B}}{n}\right) \\
&=\frac{1}{Q}\sum_{-Q/2<t\le Q/2}e\left(-\frac{tx}{Q}\right)\prod_{n\in A}\left(1-\tau+\tau e\left(\frac{t}{n}\right)\right).
\end{aligned} P ( R ( B ) − Q x ∈ Z ) = Q 1 − Q /2 < t ≤ Q /2 ∑ e ( − Q t x ) n ∈ A ∏ E e ( n t 1 n ∈ B ) = Q 1 − Q /2 < t ≤ Q /2 ∑ e ( − Q t x ) n ∈ A ∏ ( 1 − τ + τ e ( n t ) ) . Since the left-hand side is real, we may take real parts on the right-hand side, and therefore
P ( R ( B ) − x Q ∈ Z ) = 1 Q ∑ − Q / 2 < t ≤ Q / 2 Re ( e ( − t x Q ) ∏ n ∈ A ( 1 − τ + τ e ( t n ) ) ) . (19) \mathbb{P}\left(R(B)-\frac{x}{Q}\in\mathbb{Z}\right)=\frac{1}{Q}\sum_{-Q/2<t\le Q/2}\operatorname{Re}\left(e\left(-\frac{tx}{Q}\right)\prod_{n\in A}\left(1-\tau+\tau e\left(\frac{t}{n}\right)\right)\right). \tag*{(19)} P ( R ( B ) − Q x ∈ Z ) = Q 1 − Q /2 < t ≤ Q /2 ∑ Re ( e ( − Q t x ) n ∈ A ∏ ( 1 − τ + τ e ( n t ) ) ) . (19) We will prove later, using a major-arc and minor-arc analysis, that the right-hand side of (A.1) is at least 1 / ( 2 Q ) 1/(2Q) 1/ ( 2 Q ) P ( ∣ R ( B ) − x / Q ∣ ≥ 1 ) < 1 / ( 4 Q ) \mathbb{P}(|R(B)-x/Q|\ge1)<1/(4Q) P ( ∣ R ( B ) − x / Q ∣ ≥ 1 ) < 1/ ( 4 Q )
P ( R ( B ) = x / Q ) > 1 2 Q − 1 4 Q = 1 4 Q > 0. \mathbb{P}(R(B)=x/Q)>\frac{1}{2Q}-\frac{1}{4Q}=\frac{1}{4Q}>0. P ( R ( B ) = x / Q ) > 2 Q 1 − 4 Q 1 = 4 Q 1 > 0. By condition (i) of Proposition 6.1 , every q ∈ Q A q\in\mathcal{Q}_A q ∈ Q A N 0.99 N^{0.99} N 0.99
Q ≤ ∏ q ≤ N 0.99 q p r i m e p o w e r q ≤ e 2 N 0.99 . (20) Q\le\prod_{\substack{q\le N^{0.99}\\q\ \mathrm{prime\ power}}}q\le e^{2N^{0.99}}. \tag*{(20)} Q ≤ q ≤ N 0.99 q prime power ∏ q ≤ e 2 N 0.99 . (20) Using Hoeffding’s inequality [20 Theorem 2] for the independent random variables 1 n ∈ B / n ∈ [ 0 , 1 / n ] \mathbf{1}_{n\in B}/n\in[0,1/n] 1 n ∈ B / n ∈ [ 0 , 1/ n ] E ( R ( B ) ) = x / Q \mathbb{E}(R(B))=x/Q E ( R ( B )) = x / Q
P ( ∣ R ( B ) − x / Q ∣ ≥ 1 ) ≤ 2 exp ( − 2 ∑ n ∈ A 1 / n 2 ) ≤ 2 exp ( − 2 M 2 N ) ≤ 2 exp ( − 2 N 0.994 ) < 1 4 Q . \mathbb{P}(|R(B)-x/Q|\ge1)\le2\exp\left(-\frac{2}{\sum_{n\in A}1/n^2}\right)\le2\exp\left(-\frac{2M^2}{N}\right)\le2\exp(-2N^{0.994})<\frac{1}{4Q}. P ( ∣ R ( B ) − x / Q ∣ ≥ 1 ) ≤ 2 exp ( − ∑ n ∈ A 1/ n 2 2 ) ≤ 2 exp ( − N 2 M 2 ) ≤ 2 exp ( − 2 N 0.994 ) < 4 Q 1 . It remains to show that
∑ − Q / 2 < t ≤ Q / 2 Re ( e ( − t x Q ) ∏ n ∈ A ( 1 − τ + τ e ( t n ) ) ) ≥ 1 2 . (21) \sum_{-Q/2<t\le Q/2}\operatorname{Re}\left(e\left(-\frac{tx}{Q}\right)\prod_{n\in A}\left(1-\tau+\tau e\left(\frac{t}{n}\right)\right)\right)\ge\frac{1}{2}. \tag*{(21)} − Q /2 < t ≤ Q /2 ∑ Re ( e ( − Q t x ) n ∈ A ∏ ( 1 − τ + τ e ( n t ) ) ) ≥ 2 1 . (21) We do so by splitting the range of t t t
M = { t ∈ ( − Q 2 , Q 2 ] : ∣ t ∣ ≤ M 2 } , m = { t ∈ ( − Q 2 , Q 2 ] : ∣ t ∣ > M 2 } . \mathfrak{M}=\left\{t\in\left(-\frac{Q}{2},\frac{Q}{2}\right]:|t|\le\frac{M}{2}\right\},\qquad\mathfrak{m}=\left\{t\in\left(-\frac{Q}{2},\frac{Q}{2}\right]:|t|>\frac{M}{2}\right\}. M = { t ∈ ( − 2 Q , 2 Q ] : ∣ t ∣ ≤ 2 M } , m = { t ∈ ( − 2 Q , 2 Q ] : ∣ t ∣ > 2 M } . We will use the following standard estimates.
Fact A.1 ([22 Fact 2.5] ). Let θ ∈ [ − 1 / 2 , 1 / 2 ] \theta\in[-1/2,1/2] θ ∈ [ − 1/2 , 1/2 ] λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ]
∣ ( 1 − λ ) + λ e ( θ ) − e ( λ θ ) ( 1 − 2 π 2 λ ( 1 − λ ) θ 2 ) ∣ ≪ ∣ θ ∣ 3 ; \left|(1-\lambda)+\lambda e(\theta)-e(\lambda\theta)\left(1-2\pi^2\lambda(1-\lambda)\theta^2\right)\right|\ll|\theta|^3; ( 1 − λ ) + λ e ( θ ) − e ( λ θ ) ( 1 − 2 π 2 λ ( 1 − λ ) θ 2 ) ≪ ∣ θ ∣ 3 ; ∣ 1 − λ + λ e ( θ ) ∣ ≤ 1 − 8 λ ( 1 − λ ) θ 2 ≤ exp ( − 8 λ ( 1 − λ ) θ 2 ) . |1-\lambda+\lambda e(\theta)|\le1-8\lambda(1-\lambda)\theta^2\le\exp(-8\lambda(1-\lambda)\theta^2). ∣1 − λ + λ e ( θ ) ∣ ≤ 1 − 8 λ ( 1 − λ ) θ 2 ≤ exp ( − 8 λ ( 1 − λ ) θ 2 ) . Since A ⊆ ( M , N ] A \subseteq(M,N] A ⊆ ( M , N ] ∣ A ∣ ≥ M R ( A ) ≥ N 0.997 ( log N ) − 1 / 101 ≥ N 0.95 |A| \ge MR(A) \ge N^{0.997}(\log N)^{-1/101} \ge N^{0.95} ∣ A ∣ ≥ M R ( A ) ≥ N 0.997 ( log N ) − 1/101 ≥ N 0.95 τ ∈ [ ( log N ) − 2 , 1 − ( log N ) − 2 ] \tau\in[(\log N)^{-2},1-(\log N)^{-2}] τ ∈ [( log N ) − 2 , 1 − ( log N ) − 2 ] [22 Lemma 3.1] , whose proof uses Fact A.1, we have
∑ t ∈ m Re ( e ( − t x Q ) ∏ n ∈ A ( 1 − τ + τ e ( t n ) ) ) ≥ 3 4 . (22) \sum_{t\in\mathfrak{m}} \operatorname{Re}\left(e\left(-\frac{tx}{Q}\right)\prod_{n\in A}\left(1-\tau+\tau e\left(\frac{t}{n}\right)\right)\right)\ge\frac{3}{4}. \tag*{(22)} t ∈ m ∑ Re ( e ( − Q t x ) n ∈ A ∏ ( 1 − τ + τ e ( n t ) ) ) ≥ 4 3 . (22) We now turn to the minor arc, where we closely follow Bloom [1 ] . For each t ∈ m t\in\mathfrak{m} t ∈ m
I t = { m ∈ Z : ∣ m − t ∣ < K 2 } , where K = M N − 2 / log 2 N . I_t=\left\{m\in\mathbb{Z}:|m-t|<\frac{K}{2}\right\},\qquad\text{where }K=MN^{-2/\log_2N}. I t = { m ∈ Z : ∣ m − t ∣ < 2 K } , where K = M N − 2/ l o g 2 N . Define
A I t = { n ∈ A : ∥ t / n ∥ < K 2 n } = { n ∈ A : n ∣ m for some m ∈ I t } , A_{I_t}=\left\{n\in A:\left\|t/n\right\|<\frac{K}{2n}\right\}=\{n\in A:n\mid m\text{ for some }m\in I_t\}, A I t = { n ∈ A : ∥ t / n ∥ < 2 n K } = { n ∈ A : n ∣ m for some m ∈ I t } , and
m 1 = { t ∈ m : ∣ A ∖ A I t ∣ ≥ M log N } , m 2 = m ∖ m 1 . \mathfrak{m}_1=\left\{t\in\mathfrak{m}:|A\setminus A_{I_t}|\ge\frac{M}{\log N}\right\},\qquad\mathfrak{m}_2=\mathfrak{m}\setminus\mathfrak{m}_1. m 1 = { t ∈ m : ∣ A ∖ A I t ∣ ≥ log N M } , m 2 = m ∖ m 1 . For ease of notation, we define
F ( t ) = e ( − t x Q ) ∏ n ∈ A ( 1 − τ + τ e ( t n ) ) . F(t)=e\left(-\frac{tx}{Q}\right)\prod_{n\in A}\left(1-\tau+\tau e\left(\frac{t}{n}\right)\right). F ( t ) = e ( − Q t x ) n ∈ A ∏ ( 1 − τ + τ e ( n t ) ) . Since Re F ( t ) ≥ − ∣ F ( t ) ∣ \operatorname{Re}F(t)\ge-|F(t)| Re F ( t ) ≥ − ∣ F ( t ) ∣ ∑ t ∈ m ∣ F ( t ) ∣ ≤ 1 / 4 \sum_{t\in\mathfrak{m}}|F(t)|\le1/4 ∑ t ∈ m ∣ F ( t ) ∣ ≤ 1/4 ∣ 1 − τ + τ e ( t / n ) ∣ ≤ exp ( − 8 τ ( 1 − τ ) ∥ t / n ∥ 2 ) |1-\tau+\tau e(t/n)|\le\exp(-8\tau(1-\tau)\|t/n\|^2) ∣1 − τ + τ e ( t / n ) ∣ ≤ exp ( − 8 τ ( 1 − τ ) ∥ t / n ∥ 2 ) n ∈ A n\in A n ∈ A t ∈ m 1 t\in\mathfrak{m}_1 t ∈ m 1 ∥ t / n ∥ ≥ K / ( 2 n ) ≥ K / ( 2 N ) \|t/n\|\ge K/(2n)\ge K/(2N) ∥ t / n ∥ ≥ K / ( 2 n ) ≥ K / ( 2 N ) M / log N M/\log N M / log N n ∈ A n\in A n ∈ A Q ≤ e 2 N 0.99 Q\le e^{2N^{0.99}} Q ≤ e 2 N 0.99
∑ t ∈ m 1 ∣ F ( t ) ∣ ≤ ∑ t ∈ m 1 exp ( − 8 τ ( 1 − τ ) ∑ n ∈ A ∥ t / n ∥ 2 ) ≤ ∑ t ∈ m 1 exp ( − 8 τ ( 1 − τ ) K 2 M 4 N 2 log N ) ≤ ∑ − Q / 2 < t ≤ Q / 2 e − 2 N 0.9905 ≤ 1 8 . \begin{aligned}
\sum_{t\in\mathfrak{m}_1}|F(t)|
&\le\sum_{t\in\mathfrak{m}_1}\exp\left(-8\tau(1-\tau)\sum_{n\in A}\|t/n\|^2\right)\\
&\le\sum_{t\in\mathfrak{m}_1}\exp\left(-8\tau(1-\tau)\frac{K^2M}{4N^2\log N}\right)\\
&\le\sum_{-Q/2<t\le Q/2}e^{-2N^{0.9905}}\le\frac18.
\end{aligned} t ∈ m 1 ∑ ∣ F ( t ) ∣ ≤ t ∈ m 1 ∑ exp ( − 8 τ ( 1 − τ ) n ∈ A ∑ ∥ t / n ∥ 2 ) ≤ t ∈ m 1 ∑ exp ( − 8 τ ( 1 − τ ) 4 N 2 log N K 2 M ) ≤ − Q /2 < t ≤ Q /2 ∑ e − 2 N 0.9905 ≤ 8 1 . It remains to show that ∑ t ∈ m 2 ∣ F ( t ) ∣ ≤ 1 / 8 \sum_{t\in\mathfrak{m}_2}|F(t)|\le1/8 ∑ t ∈ m 2 ∣ F ( t ) ∣ ≤ 1/8 q ∈ Q A q\in\mathcal{Q}_A q ∈ Q A t t t
# { n ∈ A q : ∥ t / n ∥ ≥ K 2 n } < 25 N 2 log N log 2 N τ ( 1 − τ ) K 2 = : L , \#\left\{n\in A_q:\|t/n\|\ge\frac{K}{2n}\right\}<\frac{25N^2\log N\log_2N}{\tau(1-\tau)K^2}=:L, # { n ∈ A q : ∥ t / n ∥ ≥ 2 n K } < τ ( 1 − τ ) K 2 25 N 2 log N log 2 N =: L , and we let D t ⊆ Q A D_t\subseteq\mathcal{Q}_A D t ⊆ Q A t t t q ∈ Q A ∖ D t q\in\mathcal{Q}_A\setminus D_t q ∈ Q A ∖ D t L L L n ∈ A q n\in A_q n ∈ A q ∥ t / n ∥ ≥ K / ( 2 n ) ≥ K / ( 2 N ) \|t/n\|\ge K/(2n)\ge K/(2N) ∥ t / n ∥ ≥ K / ( 2 n ) ≥ K / ( 2 N )
∏ n ∈ A q ∣ 1 − τ + τ e ( t / n ) ∣ ≤ exp ( − 2 τ ( 1 − τ ) L K 2 N 2 ) = N − 50 log 2 N . \prod_{n\in A_q}|1-\tau+\tau e(t/n)|\le\exp\left(-\frac{2\tau(1-\tau)LK^2}{N^2}\right)=N^{-50\log_2N}. n ∈ A q ∏ ∣1 − τ + τ e ( t / n ) ∣ ≤ exp ( − N 2 2 τ ( 1 − τ ) L K 2 ) = N − 50 l o g 2 N . Since each factor ∣ 1 − τ + τ e ( t / n ) ∣ |1-\tau+\tau e(t/n)| ∣1 − τ + τ e ( t / n ) ∣ n ∈ A n\in A n ∈ A ω ( n ) ≤ 2 log 2 N \omega(n)\le2\log_2N ω ( n ) ≤ 2 log 2 N A q A_q A q n ∈ A q n\in A_q n ∈ A q q ∥ n q\mathbin{\|}n q ∥ n
∣ F ( t ) ∣ 2 log 2 N ≤ ∏ n ∈ A ∣ 1 − τ + τ e ( t / n ) ∣ ω ( n ) = ∏ q ∈ Q A ∏ n ∈ A q ∣ 1 − τ + τ e ( t / n ) ∣ ≤ ∏ q ∈ Q A ∖ D t N − 50 log 2 N = N − 50 log 2 N ∣ Q A ∖ D t ∣ . \begin{aligned}
|F(t)|^{2\log_2N}\le\prod_{n\in A}|1-\tau+\tau e(t/n)|^{\omega(n)}
=\prod_{q\in\mathcal{Q}_A}\prod_{n\in A_q}|1-\tau+\tau e(t/n)| \\
&\le\prod_{q\in\mathcal{Q}_A\setminus D_t}N^{-50\log_2N}
=N^{-50\log_2N|\mathcal{Q}_A\setminus D_t|}.
\end{aligned} ∣ F ( t ) ∣ 2 l o g 2 N ≤ n ∈ A ∏ ∣1 − τ + τ e ( t / n ) ∣ ω ( n ) = q ∈ Q A ∏ n ∈ A q ∏ ∣1 − τ + τ e ( t / n ) ∣ ≤ q ∈ Q A ∖ D t ∏ N − 50 l o g 2 N = N − 50 l o g 2 N ∣ Q A ∖ D t ∣ . This gives
∣ F ( t ) ∣ ≤ N − 25 ∣ Q A ∖ D t ∣ for t ∈ m 2 . (23) |F(t)|\le N^{-25|\mathcal{Q}_A\setminus D_t|}\qquad\text{for }t\in\mathfrak{m}_2. \tag*{(23)} ∣ F ( t ) ∣ ≤ N − 25∣ Q A ∖ D t ∣ for t ∈ m 2 . (23) Recall that [ D ] [D] [ D ] D \mathcal{D} D
Lemma A.2. For every t ∈ m 2 t \in\mathfrak{m}_2 t ∈ m 2 x ( t ) ∈ I t x(t) \in I_t x ( t ) ∈ I t q ∣ x ( t ) q \mid x(t) q ∣ x ( t ) q ∈ D t q \in D_t q ∈ D t [ D t ] ∣ x ( t ) [D_t] \mid x(t) [ D t ] ∣ x ( t )
We first complete the proof of Proposition 6.1 assuming Lemma A.2, and then prove the lemma. Let t ∈ m 2 t \in\mathfrak{m}_2 t ∈ m 2 D t ≠ Q A D_t \ne\mathcal{Q}_A D t = Q A Q = [ Q A ] \mathcal{Q} = [\mathcal{Q}_A] Q = [ Q A ] x ( t ) x(t) x ( t ) x ( t ) ≠ 0 x(t) \ne0 x ( t ) = 0 ∣ t ∣ > M / 2 > K / 2 |t| > M/2 > K/2 ∣ t ∣ > M /2 > K /2 ∣ x ( t ) ∣ < ∣ t ∣ + K / 2 ≤ Q / 2 + K / 2 < Q |x(t)| < |t| + K/2 \le Q/2 + K/2 < Q ∣ x ( t ) ∣ < ∣ t ∣ + K /2 ≤ Q /2 + K /2 < Q Q ∣ x ( t ) Q \mid x(t) Q ∣ x ( t )
Now let 1 ≤ s ≤ ∣ Q A ∣ 1 \le s \le|\mathcal{Q}_A| 1 ≤ s ≤ ∣ Q A ∣ t ∈ m 2 t \in\mathfrak{m}_2 t ∈ m 2 ∣ Q A ∖ D t ∣ = s |\mathcal{Q}_A \setminus D_t| = s ∣ Q A ∖ D t ∣ = s ∣ Q A ∣ < N |\mathcal{Q}_A| < N ∣ Q A ∣ < N N s N^s N s Q A ∖ D t \mathcal{Q}_A \setminus D_t Q A ∖ D t D t D_t D t D D D t ∈ m 2 t \in\mathfrak{m}_2 t ∈ m 2 D t = D D_t = D D t = D K / 2 K/2 K /2 [ D ] [D] [ D ] [ − Q , Q ] [-Q,Q] [ − Q , Q ] 2 Q / [ D ] + 1 ≤ 3 Q / [ D ] 2Q/[D] + 1 \le3Q/[D] 2 Q / [ D ] + 1 ≤ 3 Q / [ D ] K + 1 K + 1 K + 1 t t t Q Q Q [ D ] ∏ q ∈ Q A ∖ D q [D]\prod_{q\in\mathcal{Q}_A\setminus D}q [ D ] ∏ q ∈ Q A ∖ D q q ∈ Q A q \in\mathcal{Q}_A q ∈ Q A N 0.99 N^{0.99} N 0.99 t t t
3 Q [ D ] ( K + 1 ) ≤ 3 N 0.99 s ( K + 1 ) ≤ N s + 1 . \frac{3Q}{[D]}(K+1) \le3N^{0.99s}(K+1) \le N^{s+1}. [ D ] 3 Q ( K + 1 ) ≤ 3 N 0.99 s ( K + 1 ) ≤ N s + 1 . Using (A.5), we get
∑ t ∈ m 2 ∣ F ( t ) ∣ ≤ ∑ t ∈ m 2 N − 25 ∣ Q A ∖ D t ∣ ≤ ∑ s = 1 N N − 25 s N s + 1 N s ≤ ∑ s = 1 N N − 22 s ≤ N − 21 ≤ 1 8 . \sum_{t\in\mathfrak{m}_2}|F(t)| \le\sum_{t\in\mathfrak{m}_2}N^{-25|\mathcal{Q}_A\setminus D_t|} \le\sum_{s=1}^{N}N^{-25s}N^{s+1}N^s \le\sum_{s=1}^{N}N^{-22s} \le N^{-21} \le\frac{1}{8}. t ∈ m 2 ∑ ∣ F ( t ) ∣ ≤ t ∈ m 2 ∑ N − 25∣ Q A ∖ D t ∣ ≤ s = 1 ∑ N N − 25 s N s + 1 N s ≤ s = 1 ∑ N N − 22 s ≤ N − 21 ≤ 8 1 . Together with the bound for m 1 \mathfrak{m}_1 m 1 ∑ t ∈ m ∣ F ( t ) ∣ ≤ 1 / 4 \sum_{t\in\mathfrak{m}}|F(t)| \le1/4 ∑ t ∈ m ∣ F ( t ) ∣ ≤ 1/4 Proposition 6.1 , assuming Lemma A.2.
Proof of Lemma A.2
We will use the following technical lemmas. The first three are Lemmas 4.1, 4.2 and 4.3 of Bloom [1 ] , and the fourth follows from a sieve estimate, Lemma 3.5.
Lemma A.3. If 0 < ∣ n 1 − n 2 ∣ ≤ N 0 < |n_1-n_2| \le N 0 < ∣ n 1 − n 2 ∣ ≤ N
∑ q ∣ ( n 1 , n 2 ) 1 q ≪ log 3 N , \sum_{q\mid(n_1,n_2)}\frac{1}{q}\ll\log_3 N, q ∣ ( n 1 , n 2 ) ∑ q 1 ≪ log 3 N , where the summation is restricted to prime powers.
Lemma A.4. Let 1 2 > ε > 0 \frac{1}{2} > \varepsilon> 0 2 1 > ε > 0 N N N ε \varepsilon ε A A A R ( A ) ≥ ( log N ) − ε / 2 R(A) \ge(\log N)^{-\varepsilon/2} R ( A ) ≥ ( log N ) − ε /2 ( 1 − ε ) log 2 N ≤ ω ( n ) ≤ 2 log 2 N (1-\varepsilon)\log_2 N \le\omega(n) \le2\log_2 N ( 1 − ε ) log 2 N ≤ ω ( n ) ≤ 2 log 2 N n ∈ A n \in A n ∈ A
∑ q ∈ Q A 1 q ≥ ( 1 − 2 ε ) e − 1 log 2 N . \sum_{q\in\mathcal{Q}_A}\frac{1}{q}\ge(1-2\varepsilon)e^{-1}\log_2 N. q ∈ Q A ∑ q 1 ≥ ( 1 − 2 ε ) e − 1 log 2 N . Lemma A.5. There is a constant c > 0 c > 0 c > 0 N ≥ M ≥ N 1 / 2 N \ge M \ge N^{1/2} N ≥ M ≥ N 1/2 1 ≤ k ≤ c log 2 N 1 \le k \le c\log_2 N 1 ≤ k ≤ c log 2 N A ⊂ [ M , N ] A \subset[M,N] A ⊂ [ M , N ] ω ( n ) ≤ ( log N ) 1 / k \omega(n) \le(\log N)^{1/k} ω ( n ) ≤ ( log N ) 1/ k n ∈ A n \in A n ∈ A
For all q q q R ( A ; q ) ≥ ( log N ) − 1 / 2 R(A;q) \ge(\log N)^{-1/2} R ( A ; q ) ≥ ( log N ) − 1/2 d d d
(i) q d > M exp ( − ( log N ) 1 − 1 / k ) qd > M\exp(-(\log N)^{1-1/k}) q d > M exp ( − ( log N ) 1 − 1/ k )
(ii) ω ( d ) ≤ 5 log k log 2 N \omega(d) \le\frac{5}{\log k}\log_2 N ω ( d ) ≤ l o g k 5 log 2 N
(iii) ∑ n ∈ A q , q d ∣ n ( q d , n / q d ) = 1 q d n ≫ R ( A ; q ) ( log N ) 2 / k \sum_{\substack{n\in A_q,\ qd\mid n\\(qd,n/qd)=1}}\frac{qd}{n}\gg\frac{R(A;q)}{(\log N)^{2/k}} ∑ n ∈ A q , q d ∣ n ( q d , n / q d ) = 1 n q d ≫ ( l o g N ) 2/ k R ( A ; q )
Lemma A.6. There is an absolute constant C 2 > 0 C_2 > 0 C 2 > 0 h ∈ Z ∖ { 0 } h \in\mathbb{Z} \setminus\{0\} h ∈ Z ∖ { 0 } X X X h h h P ′ \mathcal{P}' P ′ p p p 3 ≤ p ≤ X 1 / 10 3 \le p \le X^{1/10} 3 ≤ p ≤ X 1/10 p ∤ h p \nmid h p ∤ h
# { n ∈ [ X , 2 X ) : n + h is prime and p ∤ n for all p ∈ P ′ } ≤ C 2 X log X ∏ p ∈ P ′ ( 1 − 1 p − 1 ) . \#\{n \in[X,2X): n+h\text{ is prime and }p\nmid n\text{ for all }p\in\mathcal{P}'\} \le C_2\frac{X}{\log X}\prod_{p\in\mathcal{P}'}\left(1-\frac{1}{p-1}\right). # { n ∈ [ X , 2 X ) : n + h is prime and p ∤ n for all p ∈ P ′ } ≤ C 2 log X X p ∈ P ′ ∏ ( 1 − p − 1 1 ) . This follows from Lemma 3.5 , applied to the primes up to 2 X + h 2X+h 2 X + h h h h p p p p ∈ P ′ p \in\mathcal{P}' p ∈ P ′ p p p p ∤ h p \nmid h p ∤ h
Proof of Lemma A.2. We closely follow the proof of [1 Proposition 5.1] . The only new ingredient is Lemma A.6 , which uses that A A A A ( 1 ) A^{(1)} A ( 1 ) A ( 2 ) A^{(2)} A ( 2 ) [1 ] instead passes to one of these sets. Throughout the proof, we assume that N N N h h h
Fix t ∈ m 2 t \in\mathfrak{m}_2 t ∈ m 2 t t t I = I t I=I_t I = I t A I = A I t A_I=A_{I_t} A I = A I t A I A_I A I n ∈ A n \in A n ∈ A I I I t ∉ m 1 t \notin\mathfrak{m}_1 t ∈ / m 1 ∣ A ∖ A I ∣ < M / log N |A \setminus A_I| < M/\log N ∣ A ∖ A I ∣ < M / log N A q ∖ A I = { n ∈ A q : ∥ t / n ∥ ≥ K / ( 2 n ) } A_q \setminus A_I=\{n\in A_q:\|t/n\|\ge K/(2n)\} A q ∖ A I = { n ∈ A q : ∥ t / n ∥ ≥ K / ( 2 n )} q ∈ Q A q\in\mathcal{Q}_A q ∈ Q A D t D_t D t
∣ A q ∖ A I ∣ < L for all q ∈ D t . |A_q\setminus A_I|<L\qquad\text{for all }q\in D_t. ∣ A q ∖ A I ∣ < L for all q ∈ D t . Let E I E_I E I q ∈ Q A q \in\mathcal{Q}_A q ∈ Q A R ( A I ; q ) > ( log N ) − 1 / 100 / 2 R(A_I;q)>(\log N)^{-1/100}/2 R ( A I ; q ) > ( log N ) − 1/100 /2
R ( A I ; q ) = ∑ n ∈ A q ∩ A I q n . R(A_I;q)=\sum_{n\in A_q\cap A_I}\frac{q}{n}. R ( A I ; q ) = n ∈ A q ∩ A I ∑ n q . For every q ∈ D t q\in D_t q ∈ D t A q ∖ A I A_q\setminus A_I A q ∖ A I M M M Proposition 6.1 ,
R ( A I ; q ) = R ( A ; q ) − ∑ n ∈ A q ∖ A I q n ≥ η − q L M . R(A_I;q)=R(A;q)-\sum_{n\in A_q\setminus A_I}\frac{q}{n}\ge\eta-\frac{qL}{M}. R ( A I ; q ) = R ( A ; q ) − n ∈ A q ∖ A I ∑ n q ≥ η − M q L . Since q ≤ N 0.99 q\le N^{0.99} q ≤ N 0.99 τ ( 1 − τ ) ≥ 1 2 ( log N ) − 2 \tau(1-\tau)\ge\frac{1}{2}(\log N)^{-2} τ ( 1 − τ ) ≥ 2 1 ( log N ) − 2 K = M N − 2 / log 2 N K=MN^{-2/\log_2 N} K = M N − 2/ l o g 2 N M ≥ N 0.997 M\ge N^{0.997} M ≥ N 0.997
q L M = 25 q N 2 log N log 2 N τ ( 1 − τ ) K 2 M ≤ 50 N 0.99 N 2 + 4 / log 2 N ( log N ) 3 log 2 N M 3 ≤ N − 0.001 + o ( 1 ) ≤ η 2 . \frac{qL}{M}=\frac{25qN^2\log N\log_2N}{\tau(1-\tau)K^2M}\le\frac{50N^{0.99}N^{2+4/\log_2N}(\log N)^3\log_2N}{M^3}\le N^{-0.001+o(1)}\le\frac{\eta}{2}. M q L = τ ( 1 − τ ) K 2 M 25 q N 2 log N log 2 N ≤ M 3 50 N 0.99 N 2 + 4/ l o g 2 N ( log N ) 3 log 2 N ≤ N − 0.001 + o ( 1 ) ≤ 2 η . Hence R ( A I ; q ) ≥ η / 2 R(A_I;q)\ge\eta/2 R ( A I ; q ) ≥ η /2 D t ⊆ E I D_t\subseteq E_I D t ⊆ E I
For q ∈ E I q\in E_I q ∈ E I R ( A I ; q ) ≥ ( log N ) − 1 / 2 R(A_I;q)\ge(\log N)^{-1/2} R ( A I ; q ) ≥ ( log N ) − 1/2 Lemma A.5 with A A A A I A_I A I k = log 2 N / log ( 2 log 2 N ) k=\log_2N/\log(2\log_2N) k = log 2 N / log ( 2 log 2 N ) ( log N ) 1 − 1 / k = log N / ( 2 log 2 N ) (\log N)^{1-1/k}=\log N/(2\log_2N) ( log N ) 1 − 1/ k = log N / ( 2 log 2 N ) d q d_q d q
q d q > M exp ( − log N 2 log 2 N ) = M N − 1 / ( 2 log 2 N ) > K qd_q>M\exp\left(-\frac{\log N}{2\log_2N}\right)=MN^{-1/(2\log_2N)}>K q d q > M exp ( − 2 log 2 N log N ) = M N − 1/ ( 2 l o g 2 N ) > K and ω ( d q ) < 1 500 log 2 N \omega(d_q)<\frac{1}{500}\log_2N ω ( d q ) < 500 1 log 2 N
∑ n ∈ A q ∩ A I , q d q ∣ n ( q d q , n / q d q ) = 1 q d q n ≫ R ( A I ; q ) ( 2 log 2 N ) 2 ≫ 1 ( log N ) 1 / 100 ( log 2 N ) 2 . \sum_{\substack{n\in A_q\cap A_I,\ qd_q\mid n\\(qd_q,n/qd_q)=1}}\frac{qd_q}{n}
\gg\frac{R(A_I;q)}{(2\log_2N)^2}\gg\frac{1}{(\log N)^{1/100}(\log_2N)^2}. n ∈ A q ∩ A I , q d q ∣ n ( q d q , n / q d q ) = 1 ∑ n q d q ≫ ( 2 log 2 N ) 2 R ( A I ; q ) ≫ ( log N ) 1/100 ( log 2 N ) 2 1 . By the definition of A I A_I A I n ∈ A I n\in A_I n ∈ A I q d q ∣ n qd_q\mid n q d q ∣ n I I I I I I x q x_q x q n n n q d q > K qd_q>K q d q > K K K K I I I q ∣ x q q\mid x_q q ∣ x q
Let
A I ( q ) = { n q d q : n ∈ A q ∩ A I with q d q ∣ n and ( q d q , n q d q ) = 1 } . A_I^{(q)}=\left\{\frac{n}{qd_q}:n\in A_q\cap A_I\text{ with }qd_q\mid n\text{ and }\left(qd_q,\frac{n}{qd_q}\right)=1\right\}. A I ( q ) = { q d q n : n ∈ A q ∩ A I with q d q ∣ n and ( q d q , q d q n ) = 1 } . so that, assuming N N N R ( A I ( q ) ) ≥ ( log N ) − 1 / 99 R(A_I^{(q)}) \ge(\log N)^{-1/99} R ( A I ( q ) ) ≥ ( log N ) − 1/99 m = n / ( q d q ) ∈ A I ( q ) m=n/(qd_q)\in A_I^{(q)} m = n / ( q d q ) ∈ A I ( q ) ω ( m ) ≥ ω ( n ) − 1 − ω ( d q ) ≥ ( 99 100 − 1 500 ) log 2 N − 1 ≥ 97 99 log 2 N \omega(m)\ge\omega(n)-1-\omega(d_q)\ge\left(\frac{99}{100}-\frac{1}{500}\right)\log_2 N-1\ge\frac{97}{99}\log_2 N ω ( m ) ≥ ω ( n ) − 1 − ω ( d q ) ≥ ( 100 99 − 500 1 ) log 2 N − 1 ≥ 99 97 log 2 N ω ( m ) ≤ 2 log 2 N \omega(m)\le2\log_2 N ω ( m ) ≤ 2 log 2 N Lemma A.4 with ε = 2 99 \varepsilon=\frac{2}{99} ε = 99 2
∑ r ∈ Q A I ( q ) 1 r ≥ 95 99 e − 1 log 2 N . \sum_{r\in\mathcal{Q}_{A_I^{(q)}}}\frac{1}{r}\ge\frac{95}{99}e^{-1}\log_2 N. r ∈ Q A I ( q ) ∑ r 1 ≥ 99 95 e − 1 log 2 N . Trivially, Q A I ( q ) ⊆ Q A \mathcal{Q}_{A_I^{(q)}}\subseteq\mathcal{Q}_A Q A I ( q ) ⊆ Q A x q x_q x q r ∈ Q A I ( q ) r\in\mathcal{Q}_{A_I^{(q)}} r ∈ Q A I ( q ) x q x_q x q
∑ r ∈ Q A r ∣ x q 1 r ≥ 95 99 e − 1 log 2 N ≥ 0.35 log 2 N . (24) \sum_{\substack{r\in\mathcal{Q}_A\\r\mid x_q}}\frac{1}{r}\ge\frac{95}{99}e^{-1}\log_2 N\ge0.35\log_2 N. \tag*{(24)} r ∈ Q A r ∣ x q ∑ r 1 ≥ 99 95 e − 1 log 2 N ≥ 0.35 log 2 N . (24) For any two n 1 ≠ n 2 ∈ I n_1\ne n_2\in I n 1 = n 2 ∈ I 0 < ∣ n 1 − n 2 ∣ < K ≤ N 0<|n_1-n_2|<K\le N 0 < ∣ n 1 − n 2 ∣ < K ≤ N
∑ q ∣ ( n 1 , n 2 ) 1 q ≤ C log 3 N ≤ 0.01 log 2 N (25) \sum_{q\mid(n_1,n_2)}\frac{1}{q}\le C\log_3 N\le0.01\log_2 N \tag*{(25)} q ∣ ( n 1 , n 2 ) ∑ q 1 ≤ C log 3 N ≤ 0.01 log 2 N (25) for N N N Lemma A.3 ; here C C C
Since every q ∈ Q A q\in\mathcal{Q}_A q ∈ Q A N N N
∑ q ∈ Q A 1 q ≤ ( 1 + o ( 1 ) ) log 2 N . \sum_{q\in\mathcal{Q}_A}\frac{1}{q}\le(1+o(1))\log_2 N. q ∈ Q A ∑ q 1 ≤ ( 1 + o ( 1 )) log 2 N . It follows that there are at most two distinct values of x q ∈ I x_q\in I x q ∈ I q q q E I \mathcal{E}_I E I w 1 w_1 w 1 w 2 w_2 w 2 w 3 w_3 w 3
( 1 + o ( 1 ) ) log 2 N ≥ ∑ q ∈ Q A 1 q ≥ ∑ i = 1 3 ∑ q ∣ w i q ∈ Q A 1 q − ∑ 1 ≤ i < j ≤ 3 ∑ q ∣ ( w i , w j ) 1 q (1+o(1))\log_2 N\ge\sum_{q\in\mathcal{Q}_A}\frac{1}{q}\ge\sum_{i=1}^{3}\sum_{\substack{q\mid w_i\\q\in\mathcal{Q}_A}}\frac{1}{q}-\sum_{1\le i<j\le3}\sum_{q\mid(w_i,w_j)}\frac{1}{q} ( 1 + o ( 1 )) log 2 N ≥ q ∈ Q A ∑ q 1 ≥ i = 1 ∑ 3 q ∣ w i q ∈ Q A ∑ q 1 − 1 ≤ i < j ≤ 3 ∑ q ∣ ( w i , w j ) ∑ q 1 ≥ 3 ( 0.35 log 2 N ) − 3 ( 0.01 log 2 N ) = 1.02 log 2 N , \ge3(0.35\log_2 N)-3(0.01\log_2 N)=1.02\log_2 N, ≥ 3 ( 0.35 log 2 N ) − 3 ( 0.01 log 2 N ) = 1.02 log 2 N , which is a contradiction.
If all the x q x_q x q q ∈ E I q\in\mathcal{E}_I q ∈ E I x ( t ) x(t) x ( t ) q ∈ D t ⊆ E I q\in\mathcal{D}_t\subseteq\mathcal{E}_I q ∈ D t ⊆ E I x ( t ) x(t) x ( t ) E I \mathcal{E}_I E I x ( t ) ∈ I x(t)\in I x ( t ) ∈ I w 1 = x q 1 w_1=x_{q_1} w 1 = x q 1 w 2 = x q 2 w_2=x_{q_2} w 2 = x q 2 q 1 , q 2 ∈ E I q_1,q_2\in\mathcal{E}_I q 1 , q 2 ∈ E I w 1 ≠ w 2 w_1\ne w_2 w 1 = w 2
A ( i ) = { n ∈ A : n ∣ w i } ( i = 1 , 2 ) and A ( 0 ) = A ∖ ( A ( 1 ) ∪ A ( 2 ) ) . A^{(i)}=\{n\in A:n\mid w_i\}\quad(i=1,2)\qquad\text{and}\qquad A^{(0)}=A\setminus(A^{(1)}\cup A^{(2)}). A ( i ) = { n ∈ A : n ∣ w i } ( i = 1 , 2 ) and A ( 0 ) = A ∖ ( A ( 1 ) ∪ A ( 2 ) ) . We first show that A ( 1 ) A^{(1)} A ( 1 ) A ( 2 ) A^{(2)} A ( 2 ) A A A P ( 1 ) \mathcal{P}^{(1)} P ( 1 ) p p p 3 ≤ p ≤ M 1 / 10 3\le p\le M^{1/10} 3 ≤ p ≤ M 1/10 p ∤ h p\nmid h p ∤ h p ∤ w 2 p\nmid w_2 p ∤ w 2 p ∣ r p\mid r p ∣ r r ∈ Q A r\in\mathcal{Q}_A r ∈ Q A r ∣ w 1 r\mid w_1 r ∣ w 1 ∑ p ∈ P ( 1 ) 1 / p \sum_{p\in\mathcal{P}^{(1)}}1/p ∑ p ∈ P ( 1 ) 1/ p q = q 1 q=q_1 q = q 1 O ( 1 ) O(1) O ( 1 ) p = 2 p=2 p = 2 p ∣ h p\mid h p ∣ h M 1 / 10 < p ≤ N M^{1/10}<p\le N M 1/10 < p ≤ N O h ( 1 ) O_h(1) O h ( 1 ) log M ≥ 0.997 log N \log M\ge0.997\log N log M ≥ 0.997 log N w 1 w_1 w 1 w 2 w_2 w 2 ∑ q ∣ ( w 1 , w 2 ) 1 / q \sum_{q\mid(w_1,w_2)}1/q ∑ q ∣ ( w 1 , w 2 ) 1/ q O ( log 3 N ) O(\log_3 N) O ( log 3 N )
∑ p ∈ P ( 1 ) 1 p ≥ 0.35 log 2 N − O h ( 1 ) − ∑ q ∣ ( w 1 , w 2 ) 1 q ≥ 0.35 log 2 N − O h ( 1 ) − O ( log 3 N ) ≥ 0.34 log 2 N . \sum_{p\in\mathcal{P}^{(1)}}\frac{1}{p}\ge0.35\log_2 N-O_h(1)-\sum_{q\mid(w_1,w_2)}\frac{1}{q}\ge0.35\log_2 N-O_h(1)-O(\log_3 N)\ge0.34\log_2 N. p ∈ P ( 1 ) ∑ p 1 ≥ 0.35 log 2 N − O h ( 1 ) − q ∣ ( w 1 , w 2 ) ∑ q 1 ≥ 0.35 log 2 N − O h ( 1 ) − O ( log 3 N ) ≥ 0.34 log 2 N . Every n ∈ A ( 2 ) n\in A^{(2)} n ∈ A ( 2 ) w 2 w_2 w 2 p ∤ n p\nmid n p ∤ n p ∈ P ( 1 ) p\in\mathcal{P}^{(1)} p ∈ P ( 1 ) n + h n+h n + h n ∈ A n\in A n ∈ A j 0 = ⌊ log ( N / M ) / log 2 ⌋ j_0=\lfloor\log(N/M)/\log2\rfloor j 0 = ⌊ log ( N / M ) / log 2 ⌋ X j = 2 j M X_j=2^jM X j = 2 j M 0 ≤ j ≤ j 0 0\leq j\leq j_0 0 ≤ j ≤ j 0 ( M , N ] ⊆ ⋃ j = 0 j 0 [ X j , 2 X j ) (M,N]\subseteq\bigcup_{j=0}^{j_0}[X_j,2X_j) ( M , N ] ⊆ ⋃ j = 0 j 0 [ X j , 2 X j )
For each j j j X j ≥ M X_j\geq M X j ≥ M p ∈ P ( 1 ) p\in\mathcal{P}^{(1)} p ∈ P ( 1 ) 3 ≤ p ≤ M 1 / 10 ≤ X j 1 / 10 3\leq p\leq M^{1/10}\leq X_j^{1/10} 3 ≤ p ≤ M 1/10 ≤ X j 1/10 p ∤ h p\nmid h p ∤ h
∣ A ( 2 ) ∩ [ X j , 2 X j ) ∣ ≤ C 2 X j log X j ∏ p ∈ P ( 1 ) ( 1 − 1 p − 1 ) ≤ C 2 X j log M exp ( − ∑ p ∈ P ( 1 ) 1 p ) ≤ C 2 X j log M ( log N ) − 0.34 . \begin{aligned}
\lvert A^{(2)}\cap[X_j,2X_j)\rvert\leq C_2\frac{X_j}{\log X_j}\prod_{p\in\mathcal{P}^{(1)}}\left(1-\frac{1}{p-1}\right) \\
&\leq C_2\frac{X_j}{\log M}\exp\left(-\sum_{p\in\mathcal{P}^{(1)}}\frac{1}{p}\right)\leq C_2\frac{X_j}{\log M}(\log N)^{-0.34}.
\end{aligned} ∣ A ( 2 ) ∩ [ X j , 2 X j )∣ ≤ C 2 log X j X j p ∈ P ( 1 ) ∏ ( 1 − p − 1 1 ) ≤ C 2 log M X j exp − p ∈ P ( 1 ) ∑ p 1 ≤ C 2 log M X j ( log N ) − 0.34 . Since j 0 ≪ log N j_0\ll\log N j 0 ≪ log N log M ≥ 0.997 log N \log M\geq0.997\log N log M ≥ 0.997 log N
R ( A ( 2 ) ) ≤ ∑ j = 0 j 0 ∣ A ( 2 ) ∩ [ X j , 2 X j ) ∣ X j ≤ ( j 0 + 1 ) C 2 log M ( log N ) − 0.34 ≪ ( log N ) − 0.34 . R(A^{(2)})\leq\sum_{j=0}^{j_0}\frac{\lvert A^{(2)}\cap[X_j,2X_j)\rvert}{X_j}\leq\frac{(j_0+1)C_2}{\log M}(\log N)^{-0.34}\ll(\log N)^{-0.34}. R ( A ( 2 ) ) ≤ j = 0 ∑ j 0 X j ∣ A ( 2 ) ∩ [ X j , 2 X j )∣ ≤ log M ( j 0 + 1 ) C 2 ( log N ) − 0.34 ≪ ( log N ) − 0.34 . Similarly, R ( A ( 1 ) ) ≪ ( log N ) − 0.34 R(A^{(1)})\ll(\log N)^{-0.34} R ( A ( 1 ) ) ≪ ( log N ) − 0.34 R ( A ) ≥ ( log N ) − 1 / 101 R(A)\geq(\log N)^{-1/101} R ( A ) ≥ ( log N ) − 1/101 N N N
R ( A ( 0 ) ) ≥ R ( A ) 2 . R(A^{(0)})\geq\frac{R(A)}{2}. R ( A ( 0 ) ) ≥ 2 R ( A ) . Let A ′ A' A ′ n ∈ A I ∩ A ( 0 ) n\in A_I\cap A^{(0)} n ∈ A I ∩ A ( 0 ) q ∈ Q A q\in Q_A q ∈ Q A q ∥ n q\parallel n q ∥ n E I \mathcal{E}_I E I n ∈ A ( 0 ) ∖ A ′ n\in A^{(0)}\setminus A' n ∈ A ( 0 ) ∖ A ′ A ∖ A I A\setminus A_I A ∖ A I A q ∩ A I A_q\cap A_I A q ∩ A I q ∈ Q A ∖ E I q\in Q_A\setminus\mathcal{E}_I q ∈ Q A ∖ E I E I \mathcal{E}_I E I ∣ A ∖ A I ∣ < M / log N \lvert A\setminus A_I\rvert<M/\log N ∣ A ∖ A I ∣ < M / log N
R ( A ( 0 ) ∖ A ′ ) ≤ ∣ A ∖ A I ∣ M + ∑ q ∈ Q A ∖ E I 1 q R ( A I ; q ) ≪ log 2 N ( log N ) 1 / 100 . R(A^{(0)}\setminus A')\leq\frac{\lvert A\setminus A_I\rvert}{M}+\sum_{q\in Q_A\setminus\mathcal{E}_I}\frac{1}{q}R(A_I;q)\ll\frac{\log_2 N}{(\log N)^{1/100}}. R ( A ( 0 ) ∖ A ′ ) ≤ M ∣ A ∖ A I ∣ + q ∈ Q A ∖ E I ∑ q 1 R ( A I ; q ) ≪ ( log N ) 1/100 log 2 N . Since R ( A ( 0 ) ) ≥ R ( A ) / 2 ≥ ( log N ) − 1 / 101 / 2 R(A^{(0)})\geq R(A)/2\geq(\log N)^{-1/101}/2 R ( A ( 0 ) ) ≥ R ( A ) /2 ≥ ( log N ) − 1/101 /2 R ( A ′ ) ≫ ( log N ) − 1 / 101 R(A')\gg(\log N)^{-1/101} R ( A ′ ) ≫ ( log N ) − 1/101 A ′ A' A ′ M M M
∣ A ′ ∣ ≥ M R ( A ′ ) ≫ M ( log N ) 1 / 101 . \lvert A'\rvert\geq MR(A')\gg\frac{M}{(\log N)^{1/101}}. ∣ A ′ ∣ ≥ M R ( A ′ ) ≫ ( log N ) 1/101 M . Every n ∈ A ′ ⊆ A I n\in A'\subseteq A_I n ∈ A ′ ⊆ A I I I I ∣ I ∣ ≤ K + 1 ≤ 2 K \lvert I\rvert\leq K+1\leq2K ∣ I ∣ ≤ K + 1 ≤ 2 K v ∈ I v\in I v ∈ I v ≠ w 1 v\neq w_1 v = w 1 v ≠ w 2 v\neq w_2 v = w 2 A ′ ⊆ A ( 0 ) A'\subseteq A^{(0)} A ′ ⊆ A ( 0 ) A ′ ′ = { n ∈ A ′ : n ∣ v } A''=\{n\in A':n\mid v\} A ′′ = { n ∈ A ′ : n ∣ v }
∣ A ′ ′ ∣ ≥ ∣ A ′ ∣ 2 K ≫ N 2 / log 2 N ( log N ) − 1 / 101 , \lvert A''\rvert\geq\frac{\lvert A'\rvert}{2K}\gg N^{2/\log_2 N}(\log N)^{-1/101}, ∣ A ′′ ∣ ≥ 2 K ∣ A ′ ∣ ≫ N 2/ l o g 2 N ( log N ) − 1/101 , and hence ∣ A ′ ′ ∣ > N 3 / ( 2 log 2 N ) \lvert A''\rvert>N^{3/(2\log_2 N)} ∣ A ′′ ∣ > N 3/ ( 2 l o g 2 N )
However, if n ∈ A ′ ′ n\in A'' n ∈ A ′′ n ∣ v n\mid v n ∣ v n ∣ w 1 w 2 n\mid w_1w_2 n ∣ w 1 w 2 q q q n ∈ A q n\in A_q n ∈ A q E I \mathcal{E}_I E I w 1 w_1 w 1 w 2 w_2 w 2 n n n
( v , w 1 w 2 ) ≤ ( v , w 1 ) ( v , w 2 ) ≤ ∣ v − w 1 ∣ ∣ v − w 2 ∣ ≤ N 2 . (v,w_1w_2)\leq(v,w_1)(v,w_2)\leq\lvert v-w_1\rvert\lvert v-w_2\rvert\leq N^2. ( v , w 1 w 2 ) ≤ ( v , w 1 ) ( v , w 2 ) ≤ ∣ v − w 1 ∣ ∣ v − w 2 ∣ ≤ N 2 . Therefore, the size of A ′ ′ A'' A ′′ ( v , w 1 w 2 ) ≤ N 2 (v,w_1w_2)\leq N^2 ( v , w 1 w 2 ) ≤ N 2 N ( 1 + o ( 1 ) ) 2 log 2 / log 2 N N^{(1+o(1))2\log2/\log_2 N} N ( 1 + o ( 1 )) 2 l o g 2/ l o g 2 N [23 Theorem 2.11] ), and hence we have a contradiction for large enough N N N 2 log 2 < 3 / 2 2\log2<3/2 2 log 2 < 3/2 x q x_q x q q ∈ E I q\in\mathcal{E}_I q ∈ E I
References
Department of Mathematics, University of Georgia, Athens, GA 30602, USA
Email address: rishika.agrawal@uga.edu
