Introduction and background
Define the integer sequence ( w ( n ) : n ∈ N ) (w(n):n\in\mathbb{N}) ( w ( n ) : n ∈ N ) so that
w ( n ) = { ∑ α p p α p ∥ n n p α p if n > 1 and n = ∏ p α p ; 0 if n = 1 , (1) w(n)=
\begin{cases}
\sum_{\alpha_p p^{\alpha_p}\parallel n}\frac{n}{p^{\alpha_p}} & \text{if } n>1\text{ and }n=\prod p^{\alpha_p};\\
0 & \text{if } n=1,
\end{cases} \tag*{(1)} w ( n ) = { ∑ α p p α p ∥ n p α p n 0 if n > 1 and n = ∏ p α p ; if n = 1 , (1)
and define V ( x ) = { w ( n ) : 1 ≤ n ≤ x } V(x)=\{w(n):1\le n\le x\} V ( x ) = { w ( n ) : 1 ≤ n ≤ x } . For n > 1 n>1 n > 1 , the function in (1) is the function denoted by w 1 ( n ) w_1(n) w 1 ( n ) by Erdős [3 ] , who also considered its iterates. Such iterates will not be considered in this paper, so we write w ( n ) = w 1 ( n ) w(n)=w_1(n) w ( n ) = w 1 ( n ) . We also adopt the empty-sum convention such that w ( 1 ) = 0 w(1)=0 w ( 1 ) = 0 . A problem introduced by Erdős in 1980 [3 ] is given by whether or not V ( x ) = o ( x ) V(x)=o(x) V ( x ) = o ( x ) , and Erdős described this problem by stating it “perhaps is not hopeless.” This same problem is also given as an unsolved problem in Guy’s famous text on unsolved problems in number theory [4 p. 64] , and it seems that this same problem has remained open, in view of the extant references citing Erdős’s work [3 ] , and in view of the extant material in the entries in the Online Encyclopedia of Integer Sequences1 that agree (up to initial terms) with the integer sequence defined in (1), namely, the OEIS entries A028236 and A066504. We succeed, based on our extensive interactions with GPT-6 Astra Pro, in solving Erdős’s problem, by proving that V ( x ) ≠ o ( x ) V(x)\ne o(x) V ( x ) = o ( x ) . Furthermore, we prove the stronger result such that lim inf x → ∞ V ( x ) x > 0 \liminf_{x\to\infty}\frac{V(x)}{x}>0 lim inf x → ∞ x V ( x ) > 0 .
2020 Mathematics Subject Classification. Primary 11N64; Secondary 11N36.
Key words and phrases. arithmetic function, Brun–Titchmarsh inequality, asymptotic estimate, sieve method, prime factorization.
Brief outline
Our proof uses integers of the form n = e t r p ≤ x n=etrp\le x n = e t r p ≤ x , where e ≡ 2 ( m o d 4 ) e\equiv2\pmod{4} e ≡ 2 ( mod 4 ) and t t t , r r r , and p p p are primes in suitably separated ranges. We construct a set of such integers whose cardinality is bounded below by a fixed positive multiple of x x x , and we bound the number of ordered pairs of its elements having the same value under w w w by a fixed multiple of x x x . The desired lower bound for V ( x ) V(x) V ( x ) then follows from the Cauchy–Schwarz inequality. Writing a = e t r a=etr a = e t r , the identity w ( a p ) = p w ( a ) + a w(ap)=p\,w(a)+a w ( a p ) = p w ( a ) + a reduces the equality w ( a p ) = w ( b q ) w(ap)=w(bq) w ( a p ) = w ( b q ) to a linear equation in the primes p p p and q q q , to which we apply a uniform sieve estimate.
The two smaller prime factors have different roles in estimating the resulting weights. For fixed distinct c c c and d d d in this construction, writing a = c r a=cr a = cr and b = d s b=ds b = d s , every positive common divisor of w ( c r ) w(cr) w ( cr ) , w ( d s ) w(ds) w ( d s ) , and c r − d s cr-ds cr − d s divides the nonzero integer c 2 w ( d ) − d 2 w ( c ) c^{2}w(d)-d^{2}w(c) c 2 w ( d ) − d 2 w ( c ) . The chosen ranges ensure that this integer is smaller in absolute value than the primes r r r and s s s , allowing an average over r r r and s s s through the Brun–Titchmarsh inequality. Writing c = e t c=et c = e t and d = f u d=fu d = f u , we then average over t t t : For fixed e e e , f f f , and u u u , the same integer is the value of a quadratic polynomial in t t t whose content is gcd ( e , f ) 2 \gcd(e,f)^2 g cd( e , f ) 2 . A uniform estimate for polynomial values at primes, followed by a harmonic gcd estimate, controls the remaining weight. Related polynomial averages control the prime-factor weights contributed by the sieve. The case c = d c=d c = d is treated separately.
Preliminaries
Let D ⊆ [ 0 , ∞ ) D\subseteq[0,\infty) D ⊆ [ 0 , ∞ ) be unbounded, and let F , G : D → R F,G:D\to\mathbb{R} F , G : D → R be functions that may depend on parameters ρ 1 , ρ 2 , … , ρ n \rho_1,\rho_2,\ldots,\rho_n ρ 1 , ρ 2 , … , ρ n . Assume that: For each fixed admissible choice of these parameters, the relation G ( x ) ≥ 0 G(x)\ge0 G ( x ) ≥ 0 holds for all sufficiently large x ∈ D x\in D x ∈ D . We then write F ≪ ρ 1 , ρ 2 , … , ρ n G F\ll_{\rho_1,\rho_2,\ldots,\rho_n}G F ≪ ρ 1 , ρ 2 , … , ρ n G as x → ∞ x\to\infty x → ∞ through D D D to indicate that: For each fixed and admissible choice of ρ 1 , ρ 2 , … , ρ n \rho_1,\rho_2,\ldots,\rho_n ρ 1 , ρ 2 , … , ρ n , there are constants C = C ( ρ 1 , ρ 2 , … , ρ n ) > 0 C=C(\rho_1,\rho_2,\ldots,\rho_n)>0 C = C ( ρ 1 , ρ 2 , … , ρ n ) > 0 and x 0 = x 0 ( ρ 1 , ρ 2 , … , ρ n ) ≥ 0 x_0=x_0(\rho_1,\rho_2,\ldots,\rho_n)\ge0 x 0 = x 0 ( ρ 1 , ρ 2 , … , ρ n ) ≥ 0 (possibly depending on the given parameters) such that ∣ F ( x ) ∣ ≤ C G ( x ) \lvert F(x)\rvert\le CG(x) ∣ F ( x )∣ ≤ C G ( x ) holds for all x ∈ D x\in D x ∈ D such that x ≥ x 0 x\ge x_0 x ≥ x 0 . Observe that C C C and x 0 x_0 x 0 are independent of x x x . Also observe that no uniformity with respect to the given parameters is asserted. We may then define ≪ \ll ≪ accordingly, via an empty set of parameters.
We require the use of a number of familiar and fundamental arithmetic functions. In this direction, we let ω ( n ) \omega(n) ω ( n ) denote the number of distinct prime divisors of n ≥ 2 n\ge2 n ≥ 2 , with the convention such that ω ( 1 ) = 0 \omega(1)=0 ω ( 1 ) = 0 . We recall the usual notation π ( x ) \pi(x) π ( x ) for the prime-counting function giving the number of primes not exceeding x x x , and we recall one of the most fundamental results in all of number theory, namely, the prime number theorem asserting that π ( x ) ∼ x log x \pi(x)\sim\frac{x}{\log x} π ( x ) ∼ l o g x x . We also make use of the usual notation for the counting function for primes in arithmetic progressions, writing
π ( x ; d , a ) = ∣ { p : p is prime , p ≤ x , p ≡ a ( m o d d ) } ∣ (2) \pi(x;d,a)=\lvert\{p:p\text{ is prime},\ p\le x,\ p\equiv a\pmod d\}\rvert \tag*{(2)} π ( x ; d , a ) = ∣{ p : p is prime , p ≤ x , p ≡ a ( mod d )}∣ (2)
for x ∈ R ≥ 0 x\in\mathbb{R}_{\ge0} x ∈ R ≥ 0 , d ∈ Z ≥ 1 d\in\mathbb{Z}_{\ge1} d ∈ Z ≥ 1 , and a ∈ Z a\in\mathbb{Z} a ∈ Z . Recalling that Euler’s totient function is defined so that φ ( n ) = ∣ { a ∈ Z : 1 ≤ a ≤ n , gcd ( a , n ) = 1 } ∣ \varphi(n)=\lvert\{a\in\mathbb{Z}:1\le a\le n,\gcd(a,n)=1\}\rvert φ ( n ) = ∣{ a ∈ Z : 1 ≤ a ≤ n , g cd( a , n ) = 1 }∣ , a well known generalization of the prime number theorem is such that π ( x ; d , a ) ∼ x φ ( d ) log x \pi(x;d,a) \sim\frac{x}{\varphi(d)\log x} π ( x ; d , a ) ∼ φ ( d ) l o g x x (i.e., for fixed d d d and a a a satisfying gcd ( a , d ) = 1 \gcd(a,d)=1 g cd( a , d ) = 1 and as x → ∞ x \to\infty x → ∞ ), but we require an explicit bound for π ( x ; d , a ) \pi(x;d,a) π ( x ; d , a ) given below.
A fundamental property concerning the arithmetic function defined in (2) is the Brun–Titchmarsh inequality . A formulation of this result attributed to Montgomery and Vaughan [5 ] gives us that: If d d d and a a a are positive integers that are relatively prime, then
π ( x ; d , a ) < 2 x φ ( d ) log ( x d ) (3) \pi(x;d,a) < \frac{2x}{\varphi(d)\log\left(\frac{x}{d}\right)} \tag*{(3)} π ( x ; d , a ) < φ ( d ) log ( d x ) 2 x (3)
holds for all x > d x>d x > d , referring to Crandall and Pomerance’s text for background [2 p. 43] . We require the relation in (3) for our main construction.
We henceforth adopt the convention whereby variables denoted with p p p in indexing sets for sums and products are prime, and we recall Euler’s product formula for the totient function giving that
φ ( n ) = n ∏ p ∣ n ( 1 − 1 p ) (4) \varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right) \tag*{(4)} φ ( n ) = n p ∣ n ∏ ( 1 − p 1 ) (4)
for each positive integer n n n (with the empty product being interpreted as being equal to 1). We also recall Bézout’s identity giving us that: For integers A A A and B B B that are not both equal to 0, there exist integers u u u and v v v such that A u + B v = gcd ( A , B ) Au+Bv=\gcd(A,B) A u + B v = g cd( A , B ) .
We require some fundamental inequalities often applied in analysis and number theory, including a formulation of Hölder’s inequality giving us that: For real numbers p , q > 1 p,q>1 p , q > 1 such that 1 p + 1 q = 1 \frac{1}{p}+\frac{1}{q}=1 p 1 + q 1 = 1 , and for a positive integer N N N , and for complex numbers a 1 , a 2 , … , a N a_1,a_2,\ldots,a_N a 1 , a 2 , … , a N and b 1 , b 2 , … , b N b_1,b_2,\ldots,b_N b 1 , b 2 , … , b N , the inequality
∑ i = 1 N ∣ a i b i ∣ ≤ ( ∑ i = 1 N ∣ a i ∣ p ) 1 p ( ∑ i = 1 N ∣ b i ∣ q ) 1 q (5) \sum_{i=1}^{N}|a_i b_i|\leq\left(\sum_{i=1}^{N}|a_i|^p\right)^{\frac{1}{p}}\left(\sum_{i=1}^{N}|b_i|^q\right)^{\frac{1}{q}} \tag*{(5)} i = 1 ∑ N ∣ a i b i ∣ ≤ ( i = 1 ∑ N ∣ a i ∣ p ) p 1 ( i = 1 ∑ N ∣ b i ∣ q ) q 1 (5)
holds.
We also make use of some familiar terminology arising in the number-theoretic study of polynomials. For a nonzero polynomial P P P with integer coefficients, the content of P P P , denoted by cont ( P ) \operatorname{cont}(P) cont ( P ) , refers to the positive greatest common divisor of its coefficients. A primitive polynomial is a nonzero polynomial with integer coefficients whose coefficients have greatest common divisor 1.
Main construction
We begin by briefly establishing some basic and required properties concerning the integer sequence in (1) .
Lemma 1. For each positive integer n n n , the equality gcd ( n , w ( n ) ) = 1 \gcd(n,w(n))=1 g cd( n , w ( n )) = 1 holds.
Proof. This is immediate for n = 1 n=1 n = 1 . If p α ∥ n > 1 p^\alpha\parallel n>1 p α ∥ n > 1 , then all terms in the expansion of w ( n ) w(n) w ( n ) displayed in (1) apart from n p α \frac{n}{p^\alpha} p α n are divisible by p p p , whereas the exceptional term is not. Thus no prime divisor of n n n divides w ( n ) w(n) w ( n ) , proving the claim. □ \square □
Lemma 2. Suppose that a a a is a positive integer and p p p is a prime such that p ∤ a p \nmid a p ∤ a . Then the relation w ( a p ) = p w ( a ) + a w(ap)=p\,w(a)+a w ( a p ) = p w ( a ) + a holds.
Proof. This is a special case of the relation such that: If a a a and b b b are positive and relatively prime integers, then w ( a b ) = a w ( b ) + b w ( a ) w(ab)=a\,w(b)+b\,w(a) w ( ab ) = a w ( b ) + b w ( a ) , and, in turn, this follows in a direct way from the definition in (1) . □ \square □
Lemma 3. The upper bound such that w ( n ) ≤ n log n log 2 w(n)\le n\frac{\log n}{\log2} w ( n ) ≤ n l o g 2 l o g n holds for each positive integer n n n . Moreover, if 2 ∥ n 2\parallel n 2 ∥ n , then n 2 ≤ w ( n ) \frac{n}{2}\le w(n) 2 n ≤ w ( n ) .
Proof. For n = 1 n=1 n = 1 , the upper bound holds because w ( 1 ) = 0 w(1)=0 w ( 1 ) = 0 and log 1 = 0 \log1=0 log 1 = 0 . Suppose that n > 1 n>1 n > 1 . The sum defining w ( n ) w(n) w ( n ) has ω ( n ) \omega(n) ω ( n ) terms, each at most n n n , so that w ( n ) ≤ n ω ( n ) w(n)\le n\omega(n) w ( n ) ≤ nω ( n ) .
The product of the distinct prime divisors of n n n divides n n n , and each of these primes is at least 2 2 2 . Consequently, the relation n ≥ 2 ω ( n ) n\ge2^{\omega(n)} n ≥ 2 ω ( n ) holds. Taking logarithms gives ω ( n ) ≤ log n log 2 \omega(n)\le\frac{\log n}{\log2} ω ( n ) ≤ l o g 2 l o g n , and therefore w ( n ) ≤ n ω ( n ) ≤ n log n log 2 w(n)\le n\omega(n)\le\frac{n\log n}{\log2} w ( n ) ≤ nω ( n ) ≤ l o g 2 n l o g n .
If 2 ∥ n 2\parallel n 2 ∥ n , then the sum defining w ( n ) w(n) w ( n ) contains the term n 2 \frac{n}{2} 2 n , and every remaining term is nonnegative, and hence the desired relation whereby w ( n ) ≥ n 2 w(n)\ge\frac{n}{2} w ( n ) ≥ 2 n . □ \square □
The B \mathit{B} B -function
Let N N N denote an integer exceeding 1 1 1 . Let β > 0 \beta>0 β > 0 and K > 0 K>0 K > 0 be real. A key to our construction is given by the function B β , K ( N ) B_{\beta,K}(N) B β , K ( N ) defined so that
B β , K ( N ) = ∏ p ∣ N ( 1 + K p − β ) (6) B_{\beta,K}(N)=\prod_{p\mid N}(1+Kp^{-\beta}) \tag*{(6)} B β , K ( N ) = p ∣ N ∏ ( 1 + K p − β ) (6)
and so that B β , K ( 1 ) = 1 B_{\beta,K}(1)=1 B β , K ( 1 ) = 1 .
Lemma 4. The relation B β , K ( M N ) ≤ B β , K ( M ) B β , K ( N ) B_{\beta,K}(MN)\le B_{\beta,K}(M)B_{\beta,K}(N) B β , K ( M N ) ≤ B β , K ( M ) B β , K ( N ) holds for integers M , N ≥ 1 M,N\ge1 M , N ≥ 1 .
Proof. It is immediate from (6) that
B β , K ( M ) B β , K ( N ) = B β , K ( M N ) B β , K ( gcd ( M , N ) ) (7) B_{\beta,K}(M)B_{\beta,K}(N)=B_{\beta,K}(MN)B_{\beta,K}(\gcd(M,N)) \tag*{(7)} B β , K ( M ) B β , K ( N ) = B β , K ( M N ) B β , K ( g cd( M , N )) (7) for integers M , N ≥ 1 M,N\ge1 M , N ≥ 1 , and from (7) , we obtain the desired relation. □ \square □
Lemma 5. Let α \alpha α , δ \delta δ , and γ \gamma γ denote fixed real numbers such that
0 < γ < α < δ . (8) 0<\gamma<\alpha<\delta. \tag*{(8)} 0 < γ < α < δ . (8) Then there exists a positive constant C α , δ , γ C_{\alpha,\delta,\gamma} C α , δ , γ depending only on α \alpha α , δ \delta δ , and γ \gamma γ such that: For each real number
Y ≥ 2 , (9) Y\ge2, \tag*{(9)} Y ≥ 2 , (9) for each positive integer h h h such that
1 ≤ h ≤ Y γ (10) 1\le h\le Y^\gamma \tag*{(10)} 1 ≤ h ≤ Y γ (10)
and for each positive integer b b b that is relatively prime with h h h , we have that
∑ Y α < p ≤ Y δ p ≡ b m o d h 1 p ≤ C α , δ , γ φ ( h ) , (11) \sum_{\substack{Y^{\alpha}<p\leq Y^{\delta}\\p\equiv b\ \mathrm{mod}\ h}} \frac{1}{p}\leq\frac{C_{\alpha,\delta,\gamma}}{\varphi(h)}, \tag*{(11)} Y α < p ≤ Y δ p ≡ b mod h ∑ p 1 ≤ φ ( h ) C α , δ , γ , (11)
so that
∑ Y α < p ≤ Y δ p ≡ b m o d h 1 p ≪ α , δ , γ 1 φ ( h ) , \sum_{\substack{Y^{\alpha}<p\leq Y^{\delta}\\p\equiv b\ \mathrm{mod}\ h}} \frac{1}{p}\ll_{\alpha,\delta,\gamma}\frac{1}{\varphi(h)}, Y α < p ≤ Y δ p ≡ b mod h ∑ p 1 ≪ α , δ , γ φ ( h ) 1 ,
uniformly over all Y Y Y , h h h , and b b b satisfying the given conditions. Moreover, one may take
C α , δ , γ = 2 ( δ − γ ) log 2 + 2 log ( δ − γ α − γ ) . C_{\alpha,\delta,\gamma}=\frac{2}{(\delta-\gamma)\log2}+2\log\left(\frac{\delta-\gamma}{\alpha-\gamma}\right). C α , δ , γ = ( δ − γ ) log 2 2 + 2 log ( α − γ δ − γ ) .
Proof. Since Y > 1 Y>1 Y > 1 and γ < α \gamma<\alpha γ < α , we find that h ≤ Y γ < Y α h\leq Y^{\gamma}<Y^{\alpha} h ≤ Y γ < Y α . So, a given element t t t in [ Y α , Y δ ] [Y^{\alpha},Y^{\delta}] [ Y α , Y δ ] is such that t > h t>h t > h . From the above formulation of the Brun–Titchmarsh inequality, we find that
π ( t ; h , b ) ≤ 2 t φ ( h ) log ( t h ) (12) \pi(t;h,b)\leq\frac{2t}{\varphi(h)\log\left(\frac{t}{h}\right)} \tag*{(12)} π ( t ; h , b ) ≤ φ ( h ) log ( h t ) 2 t (12)
for all t ∈ [ Y α , Y δ ] t\in[Y^{\alpha},Y^{\delta}] t ∈ [ Y α , Y δ ] . For each prime p p p occurring in the sum shown in (11) , we find that
1 p = 1 Y δ + ∫ p Y δ d t t 2 . (13) \frac{1}{p}=\frac{1}{Y^{\delta}}+\int_p^{Y^{\delta}}\frac{dt}{t^2}. \tag*{(13)} p 1 = Y δ 1 + ∫ p Y δ t 2 d t . (13)
Summing both sides of (13) and reversing the order of (finite) summation and integration, we find that
∑ Y α < p ≤ Y δ p ≡ b m o d h 1 p = π ( Y δ ; h , b ) − π ( Y α ; h , b ) Y δ + ∫ Y α Y δ π ( t ; h , b ) − π ( Y α ; h , b ) t 2 d t , \sum_{\substack{Y^{\alpha}<p\leq Y^{\delta}\\p\equiv b\ \mathrm{mod}\ h}}\frac{1}{p}
=\frac{\pi(Y^{\delta};h,b)-\pi(Y^{\alpha};h,b)}{Y^{\delta}}+\int_{Y^{\alpha}}^{Y^{\delta}}\frac{\pi(t;h,b)-\pi(Y^{\alpha};h,b)}{t^2}\,dt, Y α < p ≤ Y δ p ≡ b mod h ∑ p 1 = Y δ π ( Y δ ; h , b ) − π ( Y α ; h , b ) + ∫ Y α Y δ t 2 π ( t ; h , b ) − π ( Y α ; h , b ) d t ,
and this, in turn, produces the equality
∑ Y α < p ≤ Y δ p ≡ b m o d h 1 p = π ( Y δ ; h , b ) Y δ − π ( Y α ; h , b ) Y α + ∫ Y α Y δ π ( t ; h , b ) t 2 d t . (14) \sum_{\substack{Y^{\alpha}<p\leq Y^{\delta}\\p\equiv b\ \mathrm{mod}\ h}}\frac{1}{p}
=\frac{\pi(Y^{\delta};h,b)}{Y^{\delta}}-\frac{\pi(Y^{\alpha};h,b)}{Y^{\alpha}}+\int_{Y^{\alpha}}^{Y^{\delta}}\frac{\pi(t;h,b)}{t^2}\,dt. \tag*{(14)} Y α < p ≤ Y δ p ≡ b mod h ∑ p 1 = Y δ π ( Y δ ; h , b ) − Y α π ( Y α ; h , b ) + ∫ Y α Y δ t 2 π ( t ; h , b ) d t . (14)
From (14) and from the consequence in (12) of the Brun–Titchmarsh inequality, we find that
∑ Y α < p ≤ Y δ p ≡ b m o d h 1 p ≤ π ( Y δ ; h , b ) Y δ + ∫ Y α Y δ π ( t ; h , b ) t 2 d t ≤ 2 φ ( h ) log ( Y δ h ) + 2 φ ( h ) ∫ Y α Y δ d t t log ( t h ) = 2 φ ( h ) ( 1 log ( Y δ h ) + log ( log ( Y δ h ) log ( Y α h ) ) ) , \begin{aligned}
\sum_{\substack{Y^{\alpha}<p\leq Y^{\delta}\\p\equiv b\ \mathrm{mod}\ h}}\frac{1}{p}
&\leq\frac{\pi(Y^{\delta};h,b)}{Y^{\delta}}+\int_{Y^{\alpha}}^{Y^{\delta}}\frac{\pi(t;h,b)}{t^2}\,dt\\
&\leq\frac{2}{\varphi(h)\log\left(\frac{Y^{\delta}}{h}\right)}+\frac{2}{\varphi(h)}\int_{Y^{\alpha}}^{Y^{\delta}}\frac{dt}{t\log\left(\frac{t}{h}\right)} \\
&= \frac{2}{\varphi(h)}\left(\frac{1}{\log\left(\frac{Y^{\delta}}{h}\right)}+\log\left(\frac{\log\left(\frac{Y^{\delta}}{h}\right)}{\log\left(\frac{Y^{\alpha}}{h}\right)}\right)\right),
\end{aligned} Y α < p ≤ Y δ p ≡ b mod h ∑ p 1 ≤ Y δ π ( Y δ ; h , b ) + ∫ Y α Y δ t 2 π ( t ; h , b ) d t ≤ φ ( h ) log ( h Y δ ) 2 + φ ( h ) 2 ∫ Y α Y δ t log ( h t ) d t = φ ( h ) 2 log ( h Y δ ) 1 + log log ( h Y α ) log ( h Y δ ) ,
noting that log ( Y α h ) > 0 \log\left(\frac{Y^{\alpha}}{h}\right)>0 log ( h Y α ) > 0 follows from (8) and
log h ≤ γ log Y , (15) \log h\leq\gamma\log Y, \tag*{(15)} log h ≤ γ log Y , (15)
with (15) being implied by (10) . Also, we find that
log ( Y δ h ) log ( Y α h ) = δ log Y − log h α log Y − log h = 1 + ( δ − α ) log Y α log Y − log h . (16) \frac{\log\left(\frac{Y^{\delta}}{h}\right)}{\log\left(\frac{Y^{\alpha}}{h}\right)}
=\frac{\delta\log Y-\log h}{\alpha\log Y-\log h}
=1+\frac{(\delta-\alpha)\log Y}{\alpha\log Y-\log h}. \tag*{(16)} log ( h Y α ) log ( h Y δ ) = α log Y − log h δ log Y − log h = 1 + α log Y − log h ( δ − α ) log Y . (16)
We then find that (15) and (16) together give us that
log ( Y δ h ) log ( Y α h ) ≤ 1 + δ − α α − γ = δ − γ α − γ . (17) \frac{\log\left(\frac{Y^{\delta}}{h}\right)}{\log\left(\frac{Y^{\alpha}}{h}\right)}
\leq1+\frac{\delta-\alpha}{\alpha-\gamma}
=\frac{\delta-\gamma}{\alpha-\gamma}. \tag*{(17)} log ( h Y α ) log ( h Y δ ) ≤ 1 + α − γ δ − α = α − γ δ − γ . (17)
From (17) and the above bound for the given sum of reciprocals of primes, we find that
∑ Y α < p ≤ Y δ p ≡ b ( m o d h ) 1 p ≤ 2 φ ( h ) ( 1 log ( Y δ h ) + log ( δ − γ α − γ ) ) . (18) \sum_{\substack{Y^{\alpha}<p\leq Y^{\delta}\\p\equiv b\pmod h}}\frac{1}{p}
\leq\frac{2}{\varphi(h)}\left(\frac{1}{\log\left(\frac{Y^{\delta}}{h}\right)}+\log\left(\frac{\delta-\gamma}{\alpha-\gamma}\right)\right). \tag*{(18)} Y α < p ≤ Y δ p ≡ b ( mod h ) ∑ p 1 ≤ φ ( h ) 2 log ( h Y δ ) 1 + log ( α − γ δ − γ ) . (18)
Now, from (15) , we find that
log ( Y δ h ) ≥ ( δ − γ ) log Y . (19) \log\left(\frac{Y^{\delta}}{h}\right)\geq(\delta-\gamma)\log Y. \tag*{(19)} log ( h Y δ ) ≥ ( δ − γ ) log Y . (19)
A combined application of (9) , (18) , and (19) then gives us the desired result. □
Lemma 6. Let α \alpha α and δ \delta δ be fixed, with 0 < α < δ 0<\alpha<\delta 0 < α < δ , and let β , κ > 0 \beta,\kappa>0 β , κ > 0 be fixed. Also, let d d d be a fixed nonnegative integer, and let M > 0 M>0 M > 0 be fixed. For each real Y ≥ 2 Y\geq2 Y ≥ 2 , let P ( T ) = P = P Y ∈ Z [ T ] P(T)=P=P_Y\in\mathbb{Z}[T] P ( T ) = P = P Y ∈ Z [ T ] denote a nonzero polynomial of degree at most d d d possibly depending on Y Y Y such that
∣ P ( t ) ∣ ≤ Y M (20) |P(t)|\leq Y^{M} \tag*{(20)} ∣ P ( t ) ∣ ≤ Y M (20) for Y α < t ≤ Y δ Y^{\alpha}<t\leq Y^{\delta} Y α < t ≤ Y δ . Then
∑ Y α < p ≤ Y δ P ( p ) ≠ 0 β β , κ ( ∣ P ( p ) ∣ ) p ≪ α , δ , β , κ , d , M β β , κ ( cont ( P ) ) , (21) \sum_{\substack{Y^{\alpha}<p\leq Y^{\delta}\\P(p)\ne0}}\frac{\beta_{\beta,\kappa}(|P(p)|)}{p}
\ll_{\alpha,\delta,\beta,\kappa,d,M}\beta_{\beta,\kappa}(\operatorname{cont}(P)), \tag*{(21)} Y α < p ≤ Y δ P ( p ) = 0 ∑ p β β , κ ( ∣ P ( p ) ∣ ) ≪ α , δ , β , κ , d , M β β , κ ( cont ( P )) , (21) as Y → ∞ Y\to\infty Y → ∞ , uniformly in P P P .
Proof. We write P = cont ( P ) Q P=\operatorname{cont}(P)Q P = cont ( P ) Q , where Q Q Q is primitive. Observe that Q ∈ Z [ T ] Q\in\mathbb{Z}[T] Q ∈ Z [ T ] and that deg Q = deg P ≤ d \deg Q=\deg P\le d deg Q = deg P ≤ d , and observe that
∣ Q ( u ) ∣ = ∣ P ( u ) ∣ cont ( P ) ≤ ∣ P ( u ) ∣ (22) |Q(u)|=\frac{|P(u)|}{\operatorname{cont}(P)}
\le|P(u)| \tag*{(22)} ∣ Q ( u ) ∣ = cont ( P ) ∣ P ( u ) ∣ ≤ ∣ P ( u ) ∣ (22)
for u ∈ ( Y α , Y δ ] u\in(Y^\alpha,Y^\delta] u ∈ ( Y α , Y δ ] . From (22) and the assumption in (20) , we see that
∣ Q ( u ) ∣ ≤ Y M (23) |Q(u)|\le Y^M \tag*{(23)} ∣ Q ( u ) ∣ ≤ Y M (23)
for u ∈ ( Y α , Y δ ] u\in(Y^\alpha,Y^\delta] u ∈ ( Y α , Y δ ] . Thus P P P and Q Q Q satisfy the same required conditions specified above.
Since cont ( P ) > 0 \operatorname{cont}(P)>0 cont ( P ) > 0 , we find that P ( p ) ≠ 0 ⟺ Q ( p ) ≠ 0 P(p)\ne0\Longleftrightarrow Q(p)\ne0 P ( p ) = 0 ⟺ Q ( p ) = 0 for a given prime p p p , and thus the sum on the left of (21) runs over the same primes as the corresponding sum obtained by replacing the condition P ( p ) ≠ 0 P(p)\ne0 P ( p ) = 0 with Q ( p ) ≠ 0 Q(p)\ne0 Q ( p ) = 0 . So, for a prime p p p in either sum, the value ∣ Q ( p ) ∣ |Q(p)| ∣ Q ( p ) ∣ is a positive integer, with
∣ P ( p ) ∣ = cont ( P ) ∣ Q ( p ) ∣ . (24) |P(p)|=\operatorname{cont}(P)|Q(p)|. \tag*{(24)} ∣ P ( p ) ∣ = cont ( P ) ∣ Q ( p ) ∣. (24)
From (24) and Lemma 4, we find that
B β , K ( ∣ P ( p ) ∣ ) = B β , K ( cont ( P ) ∣ Q ( p ) ∣ ) ≤ B β , K ( cont ( P ) ) B β , K ( ∣ Q ( p ) ∣ ) . (25) B_{\beta,K}(|P(p)|)=B_{\beta,K}(\operatorname{cont}(P)|Q(p)|)
\le B_{\beta,K}(\operatorname{cont}(P))B_{\beta,K}(|Q(p)|). \tag*{(25)} B β , K ( ∣ P ( p ) ∣ ) = B β , K ( cont ( P ) ∣ Q ( p ) ∣ ) ≤ B β , K ( cont ( P )) B β , K ( ∣ Q ( p ) ∣ ) . (25)
From (25) (recalling a previous note on the index set of the sum in (21) ), we obtain that
∑ Y α < p ≤ Y δ P ( p ) ≠ 0 B β , K ( ∣ P ( p ) ∣ ) p ≤ B β , K ( cont ( P ) ) ∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 B β , K ( ∣ Q ( p ) ∣ ) p . (26) \sum_{\substack{Y^\alpha<p\le Y^\delta\\P(p)\ne0}}\frac{B_{\beta,K}(|P(p)|)}{p}
\le B_{\beta,K}(\operatorname{cont}(P))
\sum_{\substack{Y^\alpha<p\le Y^\delta\\Q(p)\ne0}}\frac{B_{\beta,K}(|Q(p)|)}{p}. \tag*{(26)} Y α < p ≤ Y δ P ( p ) = 0 ∑ p B β , K ( ∣ P ( p ) ∣ ) ≤ B β , K ( cont ( P )) Y α < p ≤ Y δ Q ( p ) = 0 ∑ p B β , K ( ∣ Q ( p ) ∣ ) . (26)
Now, for a primitive polynomial Q Q Q , we have that cont ( Q ) = 1 \operatorname{cont}(Q)=1 cont ( Q ) = 1 and that B β , K ( cont ( Q ) ) = B β , K ( 1 ) = 1 B_{\beta,K}(\operatorname{cont}(Q))=B_{\beta,K}(1)=1 B β , K ( cont ( Q )) = B β , K ( 1 ) = 1 . So, from (26) , we find that the desired result holds if and only if
∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 B β , K ( ∣ Q ( p ) ∣ ) p ≪ α , δ , β , K , d , M 1 \sum_{\substack{Y^\alpha<p\le Y^\delta\\Q(p)\ne0}}\frac{B_{\beta,K}(|Q(p)|)}{p}
\ll_{\alpha,\delta,\beta,K,d,M}1 Y α < p ≤ Y δ Q ( p ) = 0 ∑ p B β , K ( ∣ Q ( p ) ∣ ) ≪ α , δ , β , K , d , M 1
holds uniformly for every nonzero primitive polynomial Q ∈ Z [ T ] Q\in\mathbb{Z}[T] Q ∈ Z [ T ] of degree at most d d d satisfying ∣ Q ( u ) ∣ ≤ Y M |Q(u)|\le Y^M ∣ Q ( u ) ∣ ≤ Y M for every real u ∈ ( Y α , Y δ ] u\in(Y^\alpha,Y^\delta] u ∈ ( Y α , Y δ ] .
Expanding the product in (6) , we find that
B β , K ( n ) = ∑ m ∣ n m s q u a r e f r e e K ω ( m ) m β (27) B_{\beta,K}(n)=\sum_{\substack{m\mid n\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^\beta} \tag*{(27)} B β , K ( n ) = m ∣ n m squarefree ∑ m β K ω ( m ) (27)
for n ≥ 1 n\ge1 n ≥ 1 (noting that the sum in (27) is not necessarily only over prime divisors). Now, fix a real number
θ ∈ ( 0 , α ) , (28) \theta\in(0,\alpha), \tag*{(28)} θ ∈ ( 0 , α ) , (28)
with the choice of θ \theta θ depending only on α \alpha α . Also, consider the index set associated with the sum in (27) (consisting of positive and squarefree integers m m m such that m ∣ n m \mid n m ∣ n ), and consider indices of this form such that m > Y θ m > Y^\theta m > Y θ . Since m > Y θ m > Y^\theta m > Y θ in this case, we find that 1 m β ≤ ( Y θ ) − β 2 1 m β 2 \frac{1}{m^\beta} \le(Y^\theta)^{-\frac{\beta}{2}}\frac{1}{m^{\frac{\beta}{2}}} m β 1 ≤ ( Y θ ) − 2 β m 2 β 1 , so that
∑ m ∣ n m s q u a r e f r e e m > Y θ K ω ( m ) m β ≤ Y − θ β 2 ∑ m ∣ n m s q u a r e f r e e m > Y θ K ω ( m ) m β 2 ≤ Y − θ β 2 ∑ m ∣ n m s q u a r e f r e e K ω ( m ) m β 2 . (29) \sum_{\substack{m\mid n\\m\ \mathrm{squarefree}\\m>Y^\theta}} \frac{K^{\omega(m)}}{m^\beta}
\le Y^{-\frac{\theta\beta}{2}}\sum_{\substack{m\mid n\\m\ \mathrm{squarefree}\\m>Y^\theta}} \frac{K^{\omega(m)}}{m^{\frac{\beta}{2}}}
\le Y^{-\frac{\theta\beta}{2}}\sum_{\substack{m\mid n\\m\ \mathrm{squarefree}}} \frac{K^{\omega(m)}}{m^{\frac{\beta}{2}}}. \tag*{(29)} m ∣ n m squarefree m > Y θ ∑ m β K ω ( m ) ≤ Y − 2 θ β m ∣ n m squarefree m > Y θ ∑ m 2 β K ω ( m ) ≤ Y − 2 θ β m ∣ n m squarefree ∑ m 2 β K ω ( m ) . (29)
Now, observe that
∑ m ∣ n m s q u a r e f r e e K ω ( m ) m β 2 = ∏ p ∣ n p p r i m e ( 1 + K p β 2 ) ≤ ∏ p ∣ n p p r i m e ( 1 + K ) = ( 1 + K ) ω ( n ) . \sum_{\substack{m\mid n\\m\ \mathrm{squarefree}}} \frac{K^{\omega(m)}}{m^{\frac{\beta}{2}}}
= \prod_{\substack{p\mid n\\p\ \mathrm{prime}}}\left(1+\frac{K}{p^{\frac{\beta}{2}}}\right)
\le\prod_{\substack{p\mid n\\p\ \mathrm{prime}}}(1+K)
= (1+K)^{\omega(n)}. m ∣ n m squarefree ∑ m 2 β K ω ( m ) = p ∣ n p prime ∏ ( 1 + p 2 β K ) ≤ p ∣ n p prime ∏ ( 1 + K ) = ( 1 + K ) ω ( n ) .
From this and (29) together, we find that
Y − θ β 2 ∑ m ∣ n m s q u a r e f r e e K ω ( m ) m β 2 ≤ Y − θ β 2 ( 1 + K ) ω ( n ) . (30) Y^{-\frac{\theta\beta}{2}}\sum_{\substack{m\mid n\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^{\frac{\beta}{2}}}
\le Y^{-\frac{\theta\beta}{2}}(1+K)^{\omega(n)}. \tag*{(30)} Y − 2 θ β m ∣ n m squarefree ∑ m 2 β K ω ( m ) ≤ Y − 2 θ β ( 1 + K ) ω ( n ) . (30)
Now, rewrite the right-hand side of (30) so that
Y − θ β 2 ( 1 + K ) ω ( n ) = Y − θ β 2 + ϵ ( Y , n ) , (31) Y^{-\frac{\theta\beta}{2}}(1+K)^{\omega(n)}
=Y^{-\frac{\theta\beta}{2}+\epsilon(Y,n)}, \tag*{(31)} Y − 2 θ β ( 1 + K ) ω ( n ) = Y − 2 θ β + ϵ ( Y , n ) , (31)
where the error term ϵ ( Y , n ) \epsilon(Y,n) ϵ ( Y , n ) in (31) is such that
ϵ ( Y , n ) = ω ( n ) log ( 1 + K ) log Y . (32) \epsilon(Y,n)=\frac{\omega(n)\log(1+K)}{\log Y}. \tag*{(32)} ϵ ( Y , n ) = log Y ω ( n ) log ( 1 + K ) . (32)
We seek, at this point, to estimate the error term defined in (32). Suppose that Y > exp ( 1 ) Y>\exp(1) Y > exp ( 1 ) . We partition the distinct prime divisors of n n n according to whether such factors are ≤ log Y \le\sqrt{\log Y} ≤ log Y or > log Y >\sqrt{\log Y} > log Y . Of course, there are at most log Y \sqrt{\log Y} log Y prime divisors in this first part of the given partition (i.e., since there are at most log Y \sqrt{\log Y} log Y positive integers ≤ log Y \le\sqrt{\log Y} ≤ log Y ). To estimate the number of prime divisors in the second part, we now restrict our attention to positive integers n ≤ Y M n\le Y^M n ≤ Y M . Now, let k k k denote the number of distinct prime divisors of n n n exceeding log Y \sqrt{\log Y} log Y . Their product divides n n n , so that
( log Y ) k ≤ n ≤ Y M , (33) \left(\sqrt{\log Y}\right)^k\le n\le Y^M, \tag*{(33)} ( log Y ) k ≤ n ≤ Y M , (33)
and, from (33) , we deduce that k ≤ 2 M log Y log log Y k \le\frac{2M\log Y}{\log\log Y} k ≤ l o g l o g Y 2 M l o g Y . Combining the given bounds on the cardinalities of the sets of prime divisors of n n n that we have formed, we find that
ω ( n ) ≤ log Y + 2 M log Y log log Y . (34) \omega(n) \le\sqrt{\log Y}+\frac{2M\log Y}{\log\log Y}. \tag*{(34)} ω ( n ) ≤ log Y + log log Y 2 M log Y . (34)
for each real Y > exp ( 1 ) Y>\exp(1) Y > exp ( 1 ) and for each positive integer n ≤ Y M n\le Y^M n ≤ Y M . Since K K K and M M M are fixed, the definition of ε ( Y , n ) \varepsilon(Y,n) ε ( Y , n ) in (32) and the bound in (34) together give us that
0 ≤ sup n ∈ Z 1 ≤ n ≤ Y M ε ( Y , n ) ≤ log ( 1 + K ) ( 1 log Y + 2 M log log Y ) . (35) 0\le\sup_{\substack{n\in\mathbb{Z}\\1\le n\le Y^M}}\varepsilon(Y,n)\le\log(1+K)\left(\frac{1}{\sqrt{\log Y}}+\frac{2M}{\log\log Y}\right). \tag*{(35)} 0 ≤ n ∈ Z 1 ≤ n ≤ Y M sup ε ( Y , n ) ≤ log ( 1 + K ) ( log Y 1 + log log Y 2 M ) . (35)
From (35) , we find that
lim Y → ∞ ( sup n ∈ Z 1 ≤ n ≤ Y M ε ( Y , n ) ) = 0. (36) \lim_{Y\to\infty}\left(\sup_{\substack{n\in\mathbb{Z}\\1\le n\le Y^M}}\varepsilon(Y,n)\right)=0. \tag*{(36)} Y → ∞ lim n ∈ Z 1 ≤ n ≤ Y M sup ε ( Y , n ) = 0. (36)
Since θ β > 0 \theta\beta>0 θ β > 0 , we have that ε ( Y , n ) ≤ θ β 4 \varepsilon(Y,n)\le\frac{\theta\beta}{4} ε ( Y , n ) ≤ 4 θ β for all sufficiently large Y Y Y and for every positive integer n ≤ Y M n\le Y^M n ≤ Y M . Now, the relations among (29) and (30) and (31) together give us that
0 ≤ ∑ m ∣ n m s q u a r e f r e e m > Y θ K ω ( m ) m β ≤ Y − θ β 2 + ε ( Y , n ) . (37) 0\le\sum_{\substack{m\mid n\\m\ \mathrm{squarefree}\\m>Y^\theta}}\frac{K^{\omega(m)}}{m^\beta}\le Y^{-\frac{\theta\beta}{2}+\varepsilon(Y,n)}. \tag*{(37)} 0 ≤ m ∣ n m squarefree m > Y θ ∑ m β K ω ( m ) ≤ Y − 2 θ β + ε ( Y , n ) . (37)
So, from (36) and (37) , we find that
∑ m ∣ n m s q u a r e f r e e m > Y θ K ω ( m ) m β → 0 (38) \sum_{\substack{m\mid n\\m\ \mathrm{squarefree}\\m>Y^\theta}}\frac{K^{\omega(m)}}{m^\beta}\to0 \tag*{(38)} m ∣ n m squarefree m > Y θ ∑ m β K ω ( m ) → 0 (38)
as Y → ∞ Y\to\infty Y → ∞ , uniformly for integers n ∈ [ 1 , Y M ] n\in[1,Y^M] n ∈ [ 1 , Y M ] . So, from (27) and (38) together, we find that
B β , K ( n ) = ∑ m ∣ n m s q u a r e f r e e m ≤ Y θ K ω ( m ) m β + o ( 1 ) (39) \mathcal{B}_{\beta,K}(n)=\sum_{\substack{m\mid n\\m\ \mathrm{squarefree}\\m\le Y^\theta}}\frac{K^{\omega(m)}}{m^\beta}+o(1) \tag*{(39)} B β , K ( n ) = m ∣ n m squarefree m ≤ Y θ ∑ m β K ω ( m ) + o ( 1 ) (39)
as Y → ∞ Y\to\infty Y → ∞ , uniformly for integers n ∈ [ 1 , Y M ] n\in[1,Y^M] n ∈ [ 1 , Y M ] .
Recall that if Q ( p ) ≠ 0 Q(p)\ne0 Q ( p ) = 0 for a prime p ∈ ( Y α , Y δ ] p\in(Y^\alpha,Y^\delta] p ∈ ( Y α , Y δ ] , then ∣ Q ( p ) ∣ |Q(p)| ∣ Q ( p ) ∣ is a positive integer. So, from this and (23) together, we find that: If Q ( p ) ≠ 0 Q(p)\ne0 Q ( p ) = 0 , then 1 ≤ ∣ Q ( p ) ∣ ≤ Y M 1 \le|Q(p)| \le Y^M 1 ≤ ∣ Q ( p ) ∣ ≤ Y M whenever p ∈ ( Y α , Y δ ] p \in(Y^\alpha, Y^\delta] p ∈ ( Y α , Y δ ] . So, from this and the estimate in (39) , we find that
B β , K ( ∣ Q ( p ) ∣ ) = ∑ m ∣ ∣ Q ( p ) ∣ m s q u a r e f r e e m ≤ Y θ K ω ( m ) m β + o ( 1 ) (40) B_{\beta,K}(|Q(p)|)=\sum_{\substack{m\mid|Q(p)|\\m\ \mathrm{squarefree}\\m\le Y^\theta}}\frac{K^{\omega(m)}}{m^\beta}+o(1) \tag*{(40)} B β , K ( ∣ Q ( p ) ∣ ) = m ∣ ∣ Q ( p ) ∣ m squarefree m ≤ Y θ ∑ m β K ω ( m ) + o ( 1 ) (40)
as Y → ∞ Y \to\infty Y → ∞ , uniformly over all nonzero primitive polynomials Q ∈ Z [ T ] Q \in\mathbb{Z}[T] Q ∈ Z [ T ] of degree at most d d d satisfying ∣ Q ( u ) ∣ ≤ Y M |Q(u)| \le Y^M ∣ Q ( u ) ∣ ≤ Y M for each real value u ∈ ( Y α , Y δ ] u \in(Y^\alpha,Y^\delta] u ∈ ( Y α , Y δ ] , and all primes p ∈ ( Y α , Y δ ] p \in(Y^\alpha,Y^\delta] p ∈ ( Y α , Y δ ] for which Q ( p ) ≠ 0 Q(p) \ne0 Q ( p ) = 0 .
Now, by taking h = b = 1 h=b=1 h = b = 1 and γ = θ ∈ ( 0 , α ) \gamma=\theta\in(0,\alpha) γ = θ ∈ ( 0 , α ) in Lemma 5, this same lemma gives us that
∑ Y α < p ≤ Y δ 1 p ≪ α , δ 1 (41) \sum_{Y^\alpha<p\le Y^\delta}\frac{1}{p}\ll_{\alpha,\delta}1 \tag*{(41)} Y α < p ≤ Y δ ∑ p 1 ≪ α , δ 1 (41)
for all real Y ≥ 2 Y \ge2 Y ≥ 2 . Multiplying both sides of (40) by 1 p \frac{1}{p} p 1 (for a prime p p p such that Y α < p ≤ Y δ Y^\alpha< p \le Y^\delta Y α < p ≤ Y δ and such that Q ( p ) ≠ 0 Q(p) \ne0 Q ( p ) = 0 ), and then applying the summation operator ∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 \sum_{\substack{Y^\alpha<p\le Y^\delta\\Q(p)\ne0}} ∑ Y α < p ≤ Y δ Q ( p ) = 0 to both sides of the resultant identity, and by then exploiting the relation in (41) to control the resulting error term, we find that
∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 B β , K ( ∣ Q ( p ) ∣ ) p = ∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 1 p ∑ m ∣ ∣ Q ( p ) ∣ m s q u a r e f r e e m ≤ Y θ K ω ( m ) m β + o ( 1 ) (42) \sum_{\substack{Y^\alpha<p\le Y^\delta\\Q(p)\ne0}}\frac{B_{\beta,K}(|Q(p)|)}{p}
=
\sum_{\substack{Y^\alpha<p\le Y^\delta\\Q(p)\ne0}}\frac{1}{p}
\sum_{\substack{m\mid|Q(p)|\\m\ \mathrm{squarefree}\\m\le Y^\theta}}\frac{K^{\omega(m)}}{m^\beta}
+o(1) \tag*{(42)} Y α < p ≤ Y δ Q ( p ) = 0 ∑ p B β , K ( ∣ Q ( p ) ∣ ) = Y α < p ≤ Y δ Q ( p ) = 0 ∑ p 1 m ∣ ∣ Q ( p ) ∣ m squarefree m ≤ Y θ ∑ m β K ω ( m ) + o ( 1 ) (42)
as Y → ∞ Y \to\infty Y → ∞ , uniformly over all nonzero primitive polynomials Q ∈ Z [ T ] Q \in\mathbb{Z}[T] Q ∈ Z [ T ] of degree at most d d d such that ∣ Q ( u ) ∣ ≤ Y M |Q(u)| \le Y^M ∣ Q ( u ) ∣ ≤ Y M for each real value u ∈ ( Y α , Y δ ] u \in(Y^\alpha,Y^\delta] u ∈ ( Y α , Y δ ] .
Interchanging the order of summation in the double sum on the right of (42), we find that
∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 B β , K ( ∣ Q ( p ) ∣ ) p = ∑ 1 ≤ m ≤ Y θ m s q u a r e f r e e K ω ( m ) m β ∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 m ∣ ∣ Q ( p ) ∣ 1 p + o ( 1 ) (43) \sum_{\substack{Y^\alpha<p\le Y^\delta\\Q(p)\ne0}}\frac{B_{\beta,K}(|Q(p)|)}{p}
=
\sum_{\substack{1\le m\le Y^\theta\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^\beta}
\sum_{\substack{Y^\alpha<p\le Y^\delta\\Q(p)\ne0\\m\mid|Q(p)|}}\frac{1}{p}
+o(1) \tag*{(43)} Y α < p ≤ Y δ Q ( p ) = 0 ∑ p B β , K ( ∣ Q ( p ) ∣ ) = 1 ≤ m ≤ Y θ m squarefree ∑ m β K ω ( m ) Y α < p ≤ Y δ Q ( p ) = 0 m ∣ ∣ Q ( p ) ∣ ∑ p 1 + o ( 1 ) (43)
as Y → ∞ Y \to\infty Y → ∞ , with the same uniformity in Q Q Q as before. Now, recall the given bounds on θ \theta θ indicated in (28). We thus find that each pair ( m , p ) (m,p) ( m , p ) arising in the double sum in (43) is such that
1 ≤ m ≤ Y θ < Y α < p . (44) 1\le m\le Y^\theta<Y^\alpha<p. \tag*{(44)} 1 ≤ m ≤ Y θ < Y α < p . (44)
From (44), since p p p is prime, we deduce that gcd ( p , m ) = 1 \gcd(p,m)=1 g cd( p , m ) = 1 . Now, for an arbitrary positive integer m m m , define
ρ Q ( m ) = ∣ { b ∈ Z : 1 ≤ b ≤ m , gcd ( b , m ) = 1 , Q ( b ) ≡ 0 ( m o d m ) } ∣ . \rho_Q(m)=\left|\{b\in\mathbb{Z}:1\le b\le m,\ \gcd(b,m)=1,\ Q(b)\equiv0\pmod m\}\right|. ρ Q ( m ) = ∣ { b ∈ Z : 1 ≤ b ≤ m , g cd( b , m ) = 1 , Q ( b ) ≡ 0 ( mod m )} ∣ .
For each positive integer m ≤ Y θ m\le Y^\theta m ≤ Y θ , by grouping the primes appearing in the inner sum on the right of (43) by their residue classes modulo m m m , and by applying Lemma 5 with h = m h=m h = m and γ = θ \gamma=\theta γ = θ , we find that
∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 m ∣ Q ( p ) 1 p ≤ ∑ 1 ≤ b ≤ m gcd ( b , m ) = 1 Q ( b ) ≡ 0 ( m o d m ) ∑ Y α < p ≤ Y δ p ≡ b ( m o d m ) 1 p ≪ α , δ , θ ρ Q ( m ) φ ( m ) . (45) \sum_{\substack{Y^\alpha<p\le Y^\delta\\ Q(p)\ne0\\ m\mid Q(p)}}\frac{1}{p}
\le
\sum_{\substack{1\le b\le m\\ \gcd(b,m)=1\\ Q(b)\equiv0\pmod m}}
\sum_{\substack{Y^\alpha<p\le Y^\delta\\ p\equiv b\pmod m}}\frac{1}{p}
\ll_{\alpha,\delta,\theta}\frac{\rho_Q(m)}{\varphi(m)}. \tag*{(45)} Y α < p ≤ Y δ Q ( p ) = 0 m ∣ Q ( p ) ∑ p 1 ≤ 1 ≤ b ≤ m g c d ( b , m ) = 1 Q ( b ) ≡ 0 ( mod m ) ∑ Y α < p ≤ Y δ p ≡ b ( mod m ) ∑ p 1 ≪ α , δ , θ φ ( m ) ρ Q ( m ) . (45)
Since Q Q Q is primitive, its reduction modulo any prime q q q is a nonzero polynomial of degree at most d d d over the field Z / q Z \mathbb{Z}/q\mathbb{Z} Z / q Z , and thus it has at most d d d roots, with
ρ Q ( q ) ≤ d . (46) \rho_Q(q)\le d. \tag*{(46)} ρ Q ( q ) ≤ d . (46)
By the Chinese remainder theorem, we have that
ρ Q ( m ) = ∏ q ∣ m q p r i m e ρ Q ( q ) (47) \rho_Q(m)=\prod_{\substack{q\mid m\\ q\ \mathrm{prime}}}\rho_Q(q) \tag*{(47)} ρ Q ( m ) = q ∣ m q prime ∏ ρ Q ( q ) (47)
for each positive squarefree integer m m m , with ρ Q ( 1 ) = 1 \rho_Q(1)=1 ρ Q ( 1 ) = 1 corresponding to the empty product. So, from (46) and (47) together, by fixing D = max { 1 , d } D=\max\{1,d\} D = max { 1 , d } , we find that
ρ Q ( m ) ≤ D ω ( m ) (48) \rho_Q(m)\le D^{\omega(m)} \tag*{(48)} ρ Q ( m ) ≤ D ω ( m ) (48)
for each positive and squarefree integer m m m .
So, a combined application of (43) , (45) , and (48) then gives us that
∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 β β , K ( ∣ Q ( p ) ∣ ) p ≤ C α , δ , θ ∑ 1 ≤ m ≤ Y θ m s q u a r e f r e e ( K D ) ω ( m ) m β φ ( m ) + o ( 1 ) (49) \sum_{\substack{Y^\alpha<p\le Y^\delta\\ Q(p)\ne0}}\frac{\beta_{\beta,K}(|Q(p)|)}{p}
\le C_{\alpha,\delta,\theta}\sum_{\substack{1\le m\le Y^\theta\\ m\ \mathrm{squarefree}}\frac{(KD)^{\omega(m)}}{m^\beta\varphi(m)}+o(1)} \tag*{(49)} Y α < p ≤ Y δ Q ( p ) = 0 ∑ p β β , K ( ∣ Q ( p ) ∣ ) ≤ C α , δ , θ 1 ≤ m ≤ Y θ m squarefree m β φ ( m ) ( K D ) ω ( m ) + o ( 1 ) ∑ (49)
as Y → ∞ Y\to\infty Y → ∞ , with the same uniformity in Q Q Q , where C α , δ , θ > 0 C_{\alpha,\delta,\theta}>0 C α , δ , θ > 0 depends only on α \alpha α , δ \delta δ , and θ \theta θ .
By Euler’s product formula in (4) , we write
( K D ) ω ( m ) m β φ ( m ) = ∏ p ∣ m K D p β ( p − 1 ) (50) \frac{(KD)^{\omega(m)}}{m^\beta\varphi(m)}
=\prod_{p\mid m}\frac{KD}{p^\beta(p-1)} \tag*{(50)} m β φ ( m ) ( K D ) ω ( m ) = p ∣ m ∏ p β ( p − 1 ) K D (50)
for squarefree m m m . Now, define R Y = ∏ p ≤ Y θ p R_Y=\prod_{p\le Y^\theta}p R Y = ∏ p ≤ Y θ p . Using (50) , we find that
∏ p ≤ Y θ ( 1 + K D p β ( p − 1 ) ) = ∑ m ∣ R Y ∏ p ∣ m K D p β ( p − 1 ) = ∑ m ∣ R Y ( K D ) ω ( m ) m β φ ( m ) . (51) \begin{aligned}
\prod_{p\le Y^\theta}\left(1+\frac{KD}{p^\beta(p-1)}\right)
=\sum_{m\mid R_Y}\prod_{p\mid m}\frac{KD}{p^\beta(p-1)} \\
&=\sum_{m\mid R_Y}\frac{(KD)^{\omega(m)}}{m^\beta\varphi(m)}. \tag*{(51)}
\end{aligned} p ≤ Y θ ∏ ( 1 + p β ( p − 1 ) K D ) = m ∣ R Y ∑ p ∣ m ∏ p β ( p − 1 ) K D = m ∣ R Y ∑ m β φ ( m ) ( K D ) ω ( m ) . (51)
If m m m is squarefree and 1 ≤ m ≤ Y θ 1\le m\le Y^\theta 1 ≤ m ≤ Y θ , then each prime divisor p p p of m m m is such that p ≤ m ≤ Y θ p\le m\le Y^\theta p ≤ m ≤ Y θ . So, every prime divisor of m m m occurs in R Y R_Y R Y . Since m m m is squarefree, this implies that m ∣ R Y m \mid R_Y m ∣ R Y , and we thus find, using (51) , that
∑ 1 ≤ m ≤ Y θ m s q u a r e f r e e ( K D ) ω ( m ) m β φ ( m ) ≤ ∑ m ∣ R Y ( K D ) ω ( m ) m β φ ( m ) = ∏ p ≤ Y θ ( 1 + K D p β ( p − 1 ) ) . (52) \sum_{\substack{1\le m\le Y^\theta\\ m\ \mathrm{squarefree}}}\frac{(KD)^{\omega(m)}}{m^\beta\varphi(m)}
\le\sum_{m\mid R_Y}\frac{(KD)^{\omega(m)}}{m^\beta\varphi(m)}
= \prod_{p\le Y^\theta}\left(1+\frac{KD}{p^\beta(p-1)}\right). \tag*{(52)} 1 ≤ m ≤ Y θ m squarefree ∑ m β φ ( m ) ( K D ) ω ( m ) ≤ m ∣ R Y ∑ m β φ ( m ) ( K D ) ω ( m ) = p ≤ Y θ ∏ ( 1 + p β ( p − 1 ) K D ) . (52)
Using the inequality 1 + u ≤ exp ( u ) 1+u\le\exp(u) 1 + u ≤ exp ( u ) for u ≥ 0 u\ge0 u ≥ 0 , and by appealing to the inequality p − 1 ≥ p 2 p-1\ge\frac{p}{2} p − 1 ≥ 2 p holding for each prime p p p , we find that
∏ p ≤ Y θ ( 1 + K D p β ( p − 1 ) ) ≤ exp ( K D ∑ p ≤ Y θ 1 p β ( p − 1 ) ) ≤ exp ( 2 K D ∑ n = 2 ∞ 1 n 1 + β ) . (53) \prod_{p\le Y^\theta}\left(1+\frac{KD}{p^\beta(p-1)}\right)
\le\exp\left(KD\sum_{p\le Y^\theta}\frac{1}{p^\beta(p-1)}\right)
\le\exp\left(2KD\sum_{n=2}^{\infty}\frac{1}{n^{1+\beta}}\right). \tag*{(53)} p ≤ Y θ ∏ ( 1 + p β ( p − 1 ) K D ) ≤ exp K D p ≤ Y θ ∑ p β ( p − 1 ) 1 ≤ exp ( 2 K D n = 2 ∑ ∞ n 1 + β 1 ) . (53)
and we see that the right-hand side of the latter inequality above is finite since β > 0 \beta>0 β > 0 , and that this right-hand side depends only on β \beta β , K K K , and d d d , recalling that D = max { 1 , d } D=\max\{1,d\} D = max { 1 , d } .
So, from a combined application of (49) , (52) , and (53) , for fixed θ ∈ ( 0 , α ) \theta\in(0,\alpha) θ ∈ ( 0 , α ) , we find that
∑ Y α < p ≤ Y δ Q ( p ) ≠ 0 B β , K ( ∣ Q ( p ) ∣ ) p ≪ α , δ , β , K , d , M 1 (54) \sum_{\substack{Y^\alpha<p\le Y^\delta\\ Q(p)\ne0}}\frac{\mathcal{B}_{\beta,K}(|Q(p)|)}{p}
\ll_{\alpha,\delta,\beta,K,d,M}1 \tag*{(54)} Y α < p ≤ Y δ Q ( p ) = 0 ∑ p B β , K ( ∣ Q ( p ) ∣ ) ≪ α , δ , β , K , d , M 1 (54)
as Y → ∞ Y\to\infty Y → ∞ , uniformly over all nonzero primitive polynomials Q ∈ Z [ T ] Q\in\mathbb{Z}[T] Q ∈ Z [ T ] of degree at most d d d satisfying ∣ Q ( u ) ∣ ≤ Y M |Q(u)|\le Y^M ∣ Q ( u ) ∣ ≤ Y M for every real u ∈ ( Y α , Y δ ] u\in(Y^\alpha,Y^\delta] u ∈ ( Y α , Y δ ] . Applying the estimate in (54) to Q = P cont ( P ) Q=\frac{P}{\operatorname{cont}(P)} Q = cont ( P ) P in (26) , we find that
∑ Y α < p ≤ Y δ P ( p ) ≠ 0 B β , K ( ∣ P ( p ) ∣ ) p ≪ α , δ , β , K , d , M B β , K ( cont ( P ) ) \sum_{\substack{Y^\alpha<p\le Y^\delta\\ P(p)\ne0}}\frac{\mathcal{B}_{\beta,K}(|P(p)|)}{p}
\ll_{\alpha,\delta,\beta,K,d,M}\mathcal{B}_{\beta,K}(\operatorname{cont}(P)) Y α < p ≤ Y δ P ( p ) = 0 ∑ p B β , K ( ∣ P ( p ) ∣ ) ≪ α , δ , β , K , d , M B β , K ( cont ( P ))
as Y → ∞ Y\to\infty Y → ∞ , uniformly over all nonzero polynomials P ∈ Z [ T ] P\in\mathbb{Z}[T] P ∈ Z [ T ] satisfying the conditions of the lemma, thus completing our proof. □ \square □
Remark 1. The constant implicit in (21) can be made explicit. With the parameters as in the preceding lemma, set
D = max { 1 , d } , η = α β 4 M , R = max { 2 , ( K η log 2 ) 2 β } , D=\max\{1,d\},\qquad\eta=\frac{\alpha\beta}{4M},\qquad R=\max\left\{2,\left(\frac{K}{\eta\log2}\right)^{\frac{2}{\beta}}\right\}, D = max { 1 , d } , η = 4 M α β , R = max { 2 , ( η log 2 K ) β 2 } ,
and define the finite product
A = ∏ p ≤ R max { 1 , 1 + K p − β 2 p η } . A=\prod_{p\le R}\max\left\{1,\frac{1+Kp^{-\frac{\beta}{2}}}{p^\eta}\right\}. A = p ≤ R ∏ max { 1 , p η 1 + K p − 2 β } .
One may take
C = ( 2 ( δ − α 2 ) log 2 + 2 log ( 2 δ − α α ) ) ( exp ( 2 K D β ) + A ) . C=\left(\frac{2}{\left(\delta-\frac{\alpha}{2}\right)\log2}+2\log\left(\frac{2\delta-\alpha}{\alpha}\right)\right)\left(\exp\left(\frac{2KD}{\beta}\right)+A\right). C = ( ( δ − 2 α ) log 2 2 + 2 log ( α 2 δ − α ) ) ( exp ( β 2 K D ) + A ) .
For this choice of C C C , it can be shown (omitting details) that the inequality
∑ Y α < p ≤ Y δ P ( p ) ≠ 0 B β , K ( ∣ P ( p ) ∣ ) p ≤ C B β , K ( cont ( P ) ) \sum_{\substack{Y^\alpha<p\le Y^\delta\\P(p)\ne0}}\frac{B_{\beta,K}(|P(p)|)}{p}\le C B_{\beta,K}(\operatorname{cont}(P)) Y α < p ≤ Y δ P ( p ) = 0 ∑ p B β , K ( ∣ P ( p ) ∣ ) ≤ C B β , K ( cont ( P ))
holds for every real Y ≥ 2 Y\ge2 Y ≥ 2 and every polynomial P P P satisfying the hypotheses of the preceding lemma.
Lemma 7. Let β > 0 \beta>0 β > 0 and K > 0 K>0 K > 0 be fixed. Then there exists a constant C β , K > 0 C_{\beta,K}>0 C β , K > 0 , depending only on β \beta β and K K K , such that
∑ 1 ≤ a ≤ Z 1 ≤ b ≤ Z B β , K ( gcd ( a , b ) ) a b ≤ C β , K ( log Z ) 2 \sum_{\substack{1\le a\le Z\\1\le b\le Z}}\frac{B_{\beta,K}(\gcd(a,b))}{ab}\le C_{\beta,K}(\log Z)^2 1 ≤ a ≤ Z 1 ≤ b ≤ Z ∑ ab B β , K ( g cd( a , b )) ≤ C β , K ( log Z ) 2 for each real value Z ≥ 2 Z\ge2 Z ≥ 2 , where a a a and b b b are positive integers. Equivalently, the relation
∑ 1 ≤ a ≤ Z 1 ≤ b ≤ Z B β , K ( gcd ( a , b ) ) a b ≪ β , K ( log Z ) 2 \sum_{\substack{1\le a\le Z\\1\le b\le Z}}\frac{B_{\beta,K}(\gcd(a,b))}{ab}\ll_{\beta,K}(\log Z)^2 1 ≤ a ≤ Z 1 ≤ b ≤ Z ∑ ab B β , K ( g cd( a , b )) ≪ β , K ( log Z ) 2 holds.
Proof. Expanding the right-hand side of (6), we find that
B β , K ( gcd ( a , b ) ) = ∑ m ∣ a m ∣ b m s q u a r e f r e e K ω ( m ) m β . B_{\beta,K}(\gcd(a,b))=\sum_{\substack{m\mid a\\m\mid b\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^\beta}. B β , K ( g cd( a , b )) = m ∣ a m ∣ b m squarefree ∑ m β K ω ( m ) .
Using an interchange of finite summation operators, we find that
∑ 1 ≤ a ≤ Z 1 ≤ b ≤ Z B β , K ( gcd ( a , b ) ) a b = ∑ 1 ≤ m ≤ Z m s q u a r e f r e e K ω ( m ) m β ( ∑ 1 ≤ a ≤ Z m ∣ a 1 a ) 2 = ∑ 1 ≤ m ≤ Z m s q u a r e f r e e K ω ( m ) m β + 2 ( ∑ 1 ≤ k ≤ Z / m 1 k ) 2 . (55) \begin{aligned}
\sum_{\substack{1\le a\le Z\\1\le b\le Z}}\frac{B_{\beta,K}(\gcd(a,b))}{ab}
&=\sum_{\substack{1\le m\le Z\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^\beta}\left(\sum_{\substack{1\le a\le Z\\m\mid a}}\frac{1}{a}\right)^2\\
&=\sum_{\substack{1\le m\le Z\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^{\beta+2}}\left(\sum_{1\le k\le Z/m}\frac{1}{k}\right)^2. \tag*{(55)}
\end{aligned} 1 ≤ a ≤ Z 1 ≤ b ≤ Z ∑ ab B β , K ( g cd( a , b )) = 1 ≤ m ≤ Z m squarefree ∑ m β K ω ( m ) 1 ≤ a ≤ Z m ∣ a ∑ a 1 2 = 1 ≤ m ≤ Z m squarefree ∑ m β + 2 K ω ( m ) 1 ≤ k ≤ Z / m ∑ k 1 2 . (55)
A standard estimate for harmonic numbers gives us that ∑ 1 ≤ k ≤ Z 1 k ≤ 1 + log ( Z m ) ≤ 1 + log Z \sum_{1\le k\le Z}\frac{1}{k}\le1+\log\left(\frac{Z}{m}\right)\le1+\log Z ∑ 1 ≤ k ≤ Z k 1 ≤ 1 + log ( m Z ) ≤ 1 + log Z . This and (55) together give us that
∑ 1 ≤ a ≤ Z 1 ≤ b ≤ Z B β , K ( gcd ( a , b ) ) a b ≤ ( 1 + log Z ) 2 ∑ 1 ≤ m ≤ Z m s q u a r e f r e e K ω ( m ) m β + 2 . \sum_{\substack{1\le a\le Z\\1\le b\le Z}}\frac{B_{\beta,K}(\gcd(a,b))}{ab}\le(1+\log Z)^2\sum_{\substack{1\le m\le Z\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^{\beta+2}}. 1 ≤ a ≤ Z 1 ≤ b ≤ Z ∑ ab B β , K ( g cd( a , b )) ≤ ( 1 + log Z ) 2 1 ≤ m ≤ Z m squarefree ∑ m β + 2 K ω ( m ) .
Direct analogues of the derivation of the “sum-to-product” comparison in (52) and subsequent arguments give us that
∑ 1 ≤ m ≤ Z m s q u a r e f r e e K ω ( m ) m β + 2 ≤ ∏ p ≤ Z ( 1 + K p β + 2 ) ≤ exp ( K ∑ p ≤ Z 1 p β + 2 ) ≤ exp ( K ∑ n = 2 ∞ 1 n β + 2 ) ≤ exp ( K β + 1 ) , \begin{aligned}
\sum_{\substack{1\le m\le Z\\m\ \mathrm{squarefree}}}\frac{K^{\omega(m)}}{m^{\beta+2}}&\le\prod_{p\le Z}\left(1+\frac{K}{p^{\beta+2}}\right)\\
&\le\exp\left(K\sum_{p\le Z}\frac{1}{p^{\beta+2}}\right)\\
&\le\exp\left(K\sum_{n=2}^{\infty}\frac{1}{n^{\beta+2}}\right)\\
&\le\exp\left(\frac{K}{\beta+1}\right),
\end{aligned} 1 ≤ m ≤ Z m squarefree ∑ m β + 2 K ω ( m ) ≤ p ≤ Z ∏ ( 1 + p β + 2 K ) ≤ exp K p ≤ Z ∑ p β + 2 1 ≤ exp ( K n = 2 ∑ ∞ n β + 2 1 ) ≤ exp ( β + 1 K ) ,
where the last inequality follows from ∑ n = 2 ∞ 1 n β + 2 ≤ ∫ 1 ∞ d t t β + 2 = 1 β + 1 \sum_{n=2}^{\infty}\frac{1}{n^{\beta+2}}\le\int_1^\infty\frac{dt}{t^{\beta+2}}=\frac{1}{\beta+1} ∑ n = 2 ∞ n β + 2 1 ≤ ∫ 1 ∞ t β + 2 d t = β + 1 1 . Finally, since Z ≥ 2 ⇒ 1 + log Z ≤ ( 1 + 1 log 2 ) log Z Z\ge2\Rightarrow1+\log Z\le\left(1+\frac{1}{\log2}\right)\log Z Z ≥ 2 ⇒ 1 + log Z ≤ ( 1 + l o g 2 1 ) log Z , we find that a permissible choice for the constant C β , K C_{\beta,K} C β , K is C β , K = ( 1 + 1 log 2 ) 2 exp ( K β + 1 ) C_{\beta,K}=\left(1+\frac{1}{\log2}\right)^2\exp\left(\frac{K}{\beta+1}\right) C β , K = ( 1 + l o g 2 1 ) 2 exp ( β + 1 K ) .
If a a a and b b b are positive integers and p p p and q q q are primes such that p ∤ a p\nmid a p ∤ a and q ∤ b q\nmid b q ∤ b , Lemma 2 gives us that
w ( a p ) = w ( b q ) ⟺ w ( a ) p − w ( b ) q = b − a . (56) w(ap)=w(bq)\Longleftrightarrow w(a)p-w(b)q=b-a. \tag*{(56)} w ( a p ) = w ( b q ) ⟺ w ( a ) p − w ( b ) q = b − a . (56)
Because of this, we need a uniform upper bound for the number of ordered prime pairs satisfying a linear equation as in (56) .
The proof of Lemma 8 below uses Selberg’s upper bound sieve method; see [1 Section 7.2] for a general treatment. In that proof, we bound S S S by a sum of squares of weighted divisor sums and choose the weights λ h \lambda_h λ h so that the resulting quadratic form equals 1 G ( z ) \frac{1}{G(z)} G ( z ) 1 , leading to (96) . We give the argument in detail for the two linear polynomials in (73) , including the estimates needed to obtain a bound uniform in a a a , b b b , A A A , and B B B .
Lemma 8. There exist absolute constants C > 0 C>0 C > 0 and
x 0 ≥ 8 (57) x_0\ge8 \tag*{(57)} x 0 ≥ 8 (57) such that the following holds. Let
x ≥ x 0 (58) x\ge x_0 \tag*{(58)} x ≥ x 0 (58) be real, and let a a a , b b b , A A A , and B B B be positive integers such that
1 ≤ a , b ≤ x 0.054 , (59) 1 \le a,b \le x^{0.054}, \tag*{(59)} 1 ≤ a , b ≤ x 0.054 , (59)
a 2 ≤ A ≤ x 0.055 , and (60) \frac{a}{2} \le A \le x^{0.055}, \quad\textit{and} \tag*{(60)} 2 a ≤ A ≤ x 0.055 , and (60)
b 2 ≤ B ≤ x 0.055 . (61) \frac{b}{2} \le B \le x^{0.055}. \tag*{(61)} 2 b ≤ B ≤ x 0.055 . (61)
Then the number of ordered pairs ( p , q ) (p,q) ( p , q ) of primes satisfying
A p − B q = b − a , Ap-Bq=b-a, A p − B q = b − a ,
x 2 a < p ≤ x a , and (62) \frac{x}{2a}<p\le\frac{x}{a}, \quad\textit{and} \tag*{(62)} 2 a x < p ≤ a x , and (62)
x 2 b < q ≤ x b (63) \frac{x}{2b}<q\le\frac{x}{b} \tag*{(63)} 2 b x < q ≤ b x (63)
is 0 0 0 if gcd ( A , B ) ∤ ( b − a ) \gcd(A,B)\nmid(b-a) g cd( A , B ) ∤ ( b − a ) and is at most
C ( x gcd ( A , B ) a b ( log x ) 2 B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 ) (64) C\left(\frac{x\gcd(A,B)}{ab(\log x)^2}\mathcal{B}_{1,2}(AB|a-b|)+x^{0.03}\right) \tag*{(64)} C ( ab ( log x ) 2 x g cd( A , B ) B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 ) (64)
if gcd ( A , B ) \gcd(A,B) g cd( A , B ) divides b − a b-a b − a . The same constants C C C and x 0 x_0 x 0 work for each choice of a a a , b b b , A A A , and B B B satisfying the stated conditions (and where the integers a a a , b b b , A A A , and B B B may depend on x x x ).
Proof. Since gcd ( A , B ) \gcd(A,B) g cd( A , B ) divides A u − B v Au-Bv A u − B v for all integers u u u , v v v , the equation A u − B v = b − a Au-Bv=b-a A u − B v = b − a has no solutions when gcd ( A , B ) ∤ ( b − a ) \gcd(A,B)\nmid(b-a) g cd( A , B ) ∤ ( b − a ) . So, we henceforth assume that gcd ( A , B ) \gcd(A,B) g cd( A , B ) divides b − a b-a b − a .
By Bézout’s identity (recalling Section 2) together with the assumption that gcd ( A , B ) ∣ ( b − a ) \gcd(A,B)\mid(b-a) g cd( A , B ) ∣ ( b − a ) , we are permitted to fix integers u 0 u_0 u 0 and v 0 v_0 v 0 such that
A u 0 − B v 0 = b − a . (65) Au_0-Bv_0=b-a. \tag*{(65)} A u 0 − B v 0 = b − a . (65)
Since A gcd ( A , B ) \frac{A}{\gcd(A,B)} g c d ( A , B ) A and B gcd ( A , B ) \frac{B}{\gcd(A,B)} g c d ( A , B ) B are coprime, all integer solutions of A u − B v = b − a Au-Bv=b-a A u − B v = b − a are parametrized uniquely by
u = u 0 + B gcd ( A , B ) k (66) u=u_0+\frac{B}{\gcd(A,B)}k \tag*{(66)} u = u 0 + g cd( A , B ) B k (66)
and
v = v 0 + A gcd ( A , B ) k (67) v=v_0+\frac{A}{\gcd(A,B)}k \tag*{(67)} v = v 0 + g cd( A , B ) A k (67)
for k ∈ Z k\in\mathbb{Z} k ∈ Z . Each pair ( p , q ) (p,q) ( p , q ) of primes counted in the lemma corresponds to one of these integer solutions with u = p u=p u = p and v = q v=q v = q and hence to an integer k k k such that
x 2 a < u 0 + B gcd ( A , B ) k ≤ x a \frac{x}{2a}<u_0+\frac{B}{\gcd(A,B)}k\le\frac{x}{a} 2 a x < u 0 + g cd( A , B ) B k ≤ a x
and
x 2 b < v 0 + A gcd ( A , B ) k ≤ x b . \frac{x}{2b}<v_0+\frac{A}{\gcd(A,B)}k\le\frac{x}{b}. 2 b x < v 0 + g cd( A , B ) A k ≤ b x .
The relations in (68) give us that
gcd ( A , B ) B ( x 2 a − u 0 ) ≤ k ≤ gcd ( A , B ) B ( x a − u 0 ) . (68) \frac{\gcd(A,B)}{B}\left(\frac{x}{2a}-u_0\right)\le k\le\frac{\gcd(A,B)}{B}\left(\frac{x}{a}-u_0\right). \tag*{(68)} B g cd( A , B ) ( 2 a x − u 0 ) ≤ k ≤ B g cd( A , B ) ( a x − u 0 ) . (68)
so the corresponding integers k k k lie in an interval of length
x gcd ( A , B ) 2 a B ≤ x gcd ( A , B ) a b , \frac{x\gcd(A,B)}{2aB} \le\frac{x\gcd(A,B)}{ab}, 2 a B x g cd( A , B ) ≤ ab x g cd( A , B ) ,
where we have used the relation B ≥ b 2 B \ge\frac{b}{2} B ≥ 2 b appearing in (61).
As above, we assume that x 0 ≥ 8 x_0 \ge8 x 0 ≥ 8 . From the relations in (62) and (63), along with the bounds a , b ≤ x 0 0.054 a,b \le x_0^{0.054} a , b ≤ x 0 0.054 and A , B ≤ x 0 0.055 A,B \le x_0^{0.055} A , B ≤ x 0 0.055 given in (59), (60), and (61), we find that
min { p , q } > x 2 max { a , b } ≥ 1 2 x 0.946 , \begin{aligned}
\min\{p,q\} &> \frac{x}{2\max\{a,b\}} \\
&\ge\frac{1}{2}x^{0.946},
\end{aligned} min { p , q } > 2 max { a , b } x ≥ 2 1 x 0.946 ,
for each prime pair ( p , q ) (p,q) ( p , q ) satisfying the conditions of the lemma. In turn, this gives us that
min { p , q } > x 0.055 ≥ max { A , B } . (69) \begin{aligned}
\min\{p,q\} &> x^{0.055} \\
&\ge\max\{A,B\}. \tag*{(69)}
\end{aligned} min { p , q } > x 0.055 ≥ max { A , B } . (69)
Recalling that we are letting u = p u=p u = p and v = q v=q v = q , we obtain from (66) and (67) that
p = u 0 + B gcd ( A , B ) k . (70) p=u_0+\frac{B}{\gcd(A,B)}k. \tag*{(70)} p = u 0 + g cd( A , B ) B k . (70)
and
q = v 0 + A gcd ( A , B ) k . (71) q=v_0+\frac{A}{\gcd(A,B)}k. \tag*{(71)} q = v 0 + g cd( A , B ) A k . (71)
Now, observe that gcd ( u 0 , B gcd ( A , B ) ) \gcd\left(u_0,\frac{B}{\gcd(A,B)}\right) g cd( u 0 , g c d ( A , B ) B ) divides both sides of (71) and that gcd ( v 0 , A gcd ( A , B ) ) \gcd\left(v_0,\frac{A}{\gcd(A,B)}\right) g cd( v 0 , g c d ( A , B ) A ) divides both sides of (72). Since p p p and q q q are prime, and since
1 ≤ gcd ( u 0 , B gcd ( A , B ) ) ≤ B < p 1 \le\gcd\left(u_0,\frac{B}{\gcd(A,B)}\right) \le B < p 1 ≤ g cd( u 0 , g cd( A , B ) B ) ≤ B < p
and
1 ≤ gcd ( v 0 , A gcd ( A , B ) ) ≤ A < q , 1 \le\gcd\left(v_0,\frac{A}{\gcd(A,B)}\right) \le A < q, 1 ≤ g cd( v 0 , g cd( A , B ) A ) ≤ A < q ,
the divisibility relations just established give us that a prime pair satisfying the lemma’s conditions can exist only if
gcd ( u 0 , B gcd ( A , B ) ) = gcd ( v 0 , A gcd ( A , B ) ) = 1. (72) \gcd\left(u_0,\frac{B}{\gcd(A,B)}\right)
=
\gcd\left(v_0,\frac{A}{\gcd(A,B)}\right)
=1. \tag*{(72)} g cd( u 0 , g cd( A , B ) B ) = g cd( v 0 , g cd( A , B ) A ) = 1. (72)
So, if either of the linear polynomials in Z [ T ] \mathbb{Z}[T] Z [ T ] among
u 0 + B gcd ( A , B ) T and v 0 + A gcd ( A , B ) T (73) u_0+\frac{B}{\gcd(A,B)}T
\qquad\text{and}\qquad
v_0+\frac{A}{\gcd(A,B)}T \tag*{(73)} u 0 + g cd( A , B ) B T and v 0 + g cd( A , B ) A T (73)
is not primitive, then (recalling the preceding result on the equalities in (73)) the number of prime pairs satisfying the lemma’s conditions is 0. So, it remains to prove the bound involving (64) when each of the polynomials indicated in (73) is primitive. So, we henceforth assume that each of the polynomials in (73) is primitive.
For each positive integer m m m , let ρ ( m ) \rho(m) ρ ( m ) denote the number of residue classes k k k mod m m m satisfying
( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) ≡ 0 ( m o d m ) . (74) \left(u_0+\frac{B}{\gcd(A,B)}k\right)\left(v_0+\frac{A}{\gcd(A,B)}k\right)\equiv0\pmod{m}. \tag*{(74)} ( u 0 + g cd( A , B ) B k ) ( v 0 + g cd( A , B ) A k ) ≡ 0 ( mod m ) . (74)
From our assumption that each of the polynomials in (73) is primitive, we find that their reductions modulo any prime p p p are nonzero polynomials of degree at most 1 1 1 . Now, observe that the defining congruence in (74) , for m = p m=p m = p , holds precisely when
( u 0 + B gcd ( A , B ) k ) ≡ 0 ( m o d p ) (75) \left(u_0+\frac{B}{\gcd(A,B)}k\right)\equiv0\pmod{p} \tag*{(75)} ( u 0 + g cd( A , B ) B k ) ≡ 0 ( mod p ) (75)
or
( v 0 + A gcd ( A , B ) k ) ≡ 0 ( m o d p ) . (76) \left(v_0+\frac{A}{\gcd(A,B)}k\right)\equiv0\pmod{p}. \tag*{(76)} ( v 0 + g cd( A , B ) A k ) ≡ 0 ( mod p ) . (76)
Since each of the reduced versions, modulo p p p , of the polynomials among (73) is nonzero and has degree at most 1 1 1 over Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z , each of the two congruences among (75) and (76) is satisfied by at most one residue class modulo p p p , so that
ρ ( p ) ≤ 2 (77) \rho(p)\le2 \tag*{(77)} ρ ( p ) ≤ 2 (77)
for each prime p p p .
If ρ ( 2 ) = 2 \rho(2)=2 ρ ( 2 ) = 2 , then, for each integer k k k , at least one of u 0 + B gcd ( A , B ) k u_0+\frac{B}{\gcd(A,B)}k u 0 + g c d ( A , B ) B k and v 0 + A gcd ( A , B ) k v_0+\frac{A}{\gcd(A,B)}k v 0 + g c d ( A , B ) A k is even. By way of contradiction, suppose that an ordered pair ( p , q ) (p,q) ( p , q ) of primes satisfies the lemma’s conditions. Now, consider the integer parameter k k k associated with ( p , q ) (p,q) ( p , q ) according to (70) and (71) . For the integer k k k associated with ( p , q ) (p,q) ( p , q ) , the two linear expressions equal p p p and q q q ; since ρ ( 2 ) = 2 \rho(2)=2 ρ ( 2 ) = 2 , at least one of these integers is even, so 2 ∣ p q 2\mid pq 2 ∣ pq . Consequently, we find that p p p or q q q is even. So, we have that p = 2 p=2 p = 2 or q = 2 q=2 q = 2 , and thus min { p , q } = 2 \min\{p,q\}=2 min { p , q } = 2 . On the other hand, the condition p > x 2 a p>\frac{x}{2a} p > 2 a x in (62) , the condition q > x 2 b q>\frac{x}{2b} q > 2 b x in (63) , the condition a , b ≤ x 0.054 a,b\le x^{0.054} a , b ≤ x 0.054 in (59) , and the condition x ≥ x 0 ≥ 8 x\ge x_0\ge8 x ≥ x 0 ≥ 8 given by (57) and (58) together give us that
min { p , q } > x 2 max { a , b } ≥ 1 2 x 0.946 ≥ 1 2 8 0.946 > 2. \begin{aligned}
\min\{p,q\}&>\frac{x}{2\max\{a,b\}}\\
&\ge\frac{1}{2}x^{0.946}\\
&\ge\frac{1}{2}8^{0.946}\\
&>2.
\end{aligned} min { p , q } > 2 max { a , b } x ≥ 2 1 x 0.946 ≥ 2 1 8 0.946 > 2.
This contradicts that min { p , q } = 2 \min\{p,q\}=2 min { p , q } = 2 . So, when ρ ( 2 ) = 2 \rho(2)=2 ρ ( 2 ) = 2 , no ordered pair of primes satisfies the lemma’s conditions for x ≥ x 0 ≥ 8 x\ge x_0\ge8 x ≥ x 0 ≥ 8 (as required by (57) and (58) ).
So, since ρ ( 2 ) ≤ 2 \rho(2) \le2 ρ ( 2 ) ≤ 2 , we may henceforth assume that ρ ( 2 ) ≤ 1 \rho(2) \le1 ρ ( 2 ) ≤ 1 , since the case ρ ( 2 ) = 2 \rho(2) = 2 ρ ( 2 ) = 2 gives zero prime pairs satisfying the lemma’s conditions. Now, recall that (77) holds for each prime p p p . So, since ρ ( p ) ≤ 2 < p \rho(p) \le2 < p ρ ( p ) ≤ 2 < p for each odd prime p p p , this and a previous argument together give us that
0 ≤ ρ ( p ) < p (78) 0 \le\rho(p) < p \tag*{(78)} 0 ≤ ρ ( p ) < p (78)
for each prime p p p .
For the time being, suppose that p p p is a prime such that p ∤ 2 A B ∣ a − b ∣ p \nmid2AB|a-b| p ∤ 2 A B ∣ a − b ∣ . Thus p ∤ A p \nmid A p ∤ A and p ∤ B p \nmid B p ∤ B . If p p p were to divide B gcd ( A , B ) \frac{B}{\gcd(A,B)} g c d ( A , B ) B , then p p p would divide gcd ( A , B ) B gcd ( A , B ) \gcd(A,B)\frac{B}{\gcd(A,B)} g cd( A , B ) g c d ( A , B ) B , contradicting that p ∤ B p \nmid B p ∤ B . So, again with the assumption that p ∤ 2 A B ∣ a − b ∣ p \nmid2AB|a-b| p ∤ 2 A B ∣ a − b ∣ , each of the integers among B gcd ( A , B ) \frac{B}{\gcd(A,B)} g c d ( A , B ) B and A gcd ( A , B ) \frac{A}{\gcd(A,B)} g c d ( A , B ) A is invertible modulo p p p . So, each of the congruences among (75) and (76) has exactly one solution modulo p p p . The two congruences among (75) and (76) have distinct solutions modulo p p p , since a common solution k k k mod p p p would, recalling the consequence of Bézout’s identity in (65) , imply that
b − a = A u 0 − B v 0 = A ( u 0 + B gcd ( A , B ) k ) − B ( v 0 + A gcd ( A , B ) k ) ≡ 0 ( m o d p ) , \begin{aligned}
b-a &= Au_0-Bv_0 \\
&= A\left(u_0+\frac{B}{\gcd(A,B)}k\right)-B\left(v_0+\frac{A}{\gcd(A,B)}k\right) \\
&\equiv0 \pmod{p},
\end{aligned} b − a = A u 0 − B v 0 = A ( u 0 + g cd( A , B ) B k ) − B ( v 0 + g cd( A , B ) A k ) ≡ 0 ( mod p ) ,
but this would contradict that p ∤ ∣ a − b ∣ p \nmid|a-b| p ∤ ∣ a − b ∣ .
By Euclid’s lemma, the congruence defining ρ ( p ) \rho(p) ρ ( p ) , i.e., the m = p m=p m = p case of (74) , holds precisely when at least one of the congruences among (75) and (76) holds. As demonstrated above, if p p p is a prime such that p ∤ 2 A B ∣ a − b ∣ p \nmid2AB|a-b| p ∤ 2 A B ∣ a − b ∣ , then each of the congruences among (75) and (76) has exactly one solution modulo p p p , and these solutions are distinct. So, for a prime p p p , we obtain the implication such that
p ∤ 2 A B ∣ a − b ∣ ⟹ ρ ( p ) = 2. p \nmid2AB|a-b| \Longrightarrow\rho(p)=2. p ∤ 2 A B ∣ a − b ∣ ⟹ ρ ( p ) = 2.
By the Chinese remainder theorem, for each positive and squarefree integer m m m , we have that
ρ ( m ) = ∏ p ∣ m ρ ( p ) , (79) \rho(m)=\prod_{p\mid m}\rho(p), \tag*{(79)} ρ ( m ) = p ∣ m ∏ ρ ( p ) , (79)
with the understanding that ρ ( 1 ) = 1 \rho(1)=1 ρ ( 1 ) = 1 and with the empty product being interpreted as 1.
Now, let
z = x 0.005 . (80) z=x^{0.005}. \tag*{(80)} z = x 0.005 . (80)
So, each ordered 2-tuple ( p , q ) (p,q) ( p , q ) of primes satisfying the lemma’s conditions is such that
min { p , q } > x 0.055 > z , (81) \min\{p,q\}>x^{0.055}>z, \tag*{(81)} min { p , q } > x 0.055 > z , (81)
where the initial inequality in (81) was established in (69) , and where the latter inequality in (81) follows from the assumptions such that x ≥ x 0 ≥ 8 x \ge x_0 \ge8 x ≥ x 0 ≥ 8 .
Recalling (68) , we let S S S denote the number of integers k k k in the interval
[ gcd ( A , B ) B ( x 2 a − u 0 ) , gcd ( A , B ) B ( x a − u 0 ) ] (82) \left[\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{2a}-u_0\right),\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{a}-u_0\right)\right] \tag*{(82)} [ B gcd ( A , B ) ( 2 a x − u 0 ) , B gcd ( A , B ) ( a x − u 0 ) ] (82)
such that the integer
( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) \left(u_0+\frac{B}{\operatorname{gcd}(A,B)}k\right)\left(v_0+\frac{A}{\operatorname{gcd}(A,B)}k\right) ( u 0 + gcd ( A , B ) B k ) ( v 0 + gcd ( A , B ) A k )
has no prime divisor at most z z z . So, again recalling (68) , according to the given definition of S S S , the number of ordered prime pairs satisfying the lemma’s conditions is at most S S S . Observe that the interval in (82) is of length x gcd ( A , B ) 2 a B \frac{x\operatorname{gcd}(A,B)}{2aB} 2 a B x gcd ( A , B ) . Consequently, the number of integers in any fixed residue class modulo m m m lying in the interval in (82) differs from x gcd ( A , B ) 2 a B m \frac{x\operatorname{gcd}(A,B)}{2aBm} 2 a B m x gcd ( A , B ) by at most 1. So, the number of integers k k k in the interval in (82) satisfying the congruence in (74) differs from x gcd ( A , B ) ρ ( m ) 2 a B m \frac{x\operatorname{gcd}(A,B)\rho(m)}{2aBm} 2 a B m x gcd ( A , B ) ρ ( m ) by at most ρ ( m ) \rho(m) ρ ( m ) .
Define
G ( z ) = ∑ 1 ≤ h ≤ z h squarefree ∏ p ∣ h ρ ( p ) p − ρ ( p ) , (83) \mathcal{G}(z)=\sum_{\substack{1\le h\le z\\h\ \text{squarefree}}}\prod_{p\mid h}\frac{\rho(p)}{p-\rho(p)}, \tag*{(83)} G ( z ) = 1 ≤ h ≤ z h squarefree ∑ p ∣ h ∏ p − ρ ( p ) ρ ( p ) , (83)
where the term corresponding to h = 1 h=1 h = 1 is interpreted as 1. From the inequalities shown in (78) , we find that each term in the sum in (83) is nonnegative, and, moreover, since the term corresponding to h = 1 h=1 h = 1 equals 1, we find that G ( z ) ≥ 1 \mathcal{G}(z)\ge1 G ( z ) ≥ 1 . For a positive integer h h h , define λ h \lambda_h λ h so that λ 1 = 1 \lambda_1=1 λ 1 = 1 and so that λ h = 0 \lambda_h=0 λ h = 0 whenever h > z h>z h > z or h h h is not squarefree, and, for remaining values of h h h , let λ h \lambda_h λ h (for the time being) be understood as a fixed real number (to be made explicit later).
For every integer k k k counted by S S S , we have
∑ 1 ≤ h ≤ z h ∣ ( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) λ h = λ 1 = 1 , (84) \sum_{\substack{1\le h\le z\\h\mid\left(u_0+\frac{B}{\operatorname{gcd}(A,B)}k\right)\left(v_0+\frac{A}{\operatorname{gcd}(A,B)}k\right)}}\lambda_h=\lambda_1=1, \tag*{(84)} 1 ≤ h ≤ z h ∣ ( u 0 + gcd ( A , B ) B k ) ( v 0 + gcd ( A , B ) A k ) ∑ λ h = λ 1 = 1 , (84)
since any index h > 1 h>1 h > 1 in the sum would have a prime divisor p ≤ h ≤ z p\le h\le z p ≤ h ≤ z , and the relations among p ∣ h p\mid h p ∣ h and h ∣ ( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) h\mid\left(u_0+\frac{B}{\operatorname{gcd}(A,B)}k\right)\left(v_0+\frac{A}{\operatorname{gcd}(A,B)}k\right) h ∣ ( u 0 + gcd ( A , B ) B k ) ( v 0 + gcd ( A , B ) A k ) would imply p ∣ ( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) p\mid\left(u_0+\frac{B}{\operatorname{gcd}(A,B)}k\right)\left(v_0+\frac{A}{\operatorname{gcd}(A,B)}k\right) p ∣ ( u 0 + gcd ( A , B ) B k ) ( v 0 + gcd ( A , B ) A k ) , contradicting the requirement in the definition of S S S that no prime at most z z z can divide this product. Since each integer k k k counted by S S S contributes 1, according to (84) , to the following sum and since the remaining terms are squares of real numbers, we find that
S ≤ ∑ k ∈ Z gcd ( A , B ) B ( x 2 a − u 0 ) ≤ k k ≤ gcd ( A , B ) B ( x a − u 0 ) ( ∑ 1 ≤ h ≤ z h ∣ ( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) λ h ) 2 . (85) S\le\sum_{\substack{k\in\mathbb{Z}\\
\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{2a}-u_0\right)\le k\\
k\le\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{a}-u_0\right)}}
\left(\sum_{\substack{1\le h\le z\\h\mid\left(u_0+\frac{B}{\operatorname{gcd}(A,B)}k\right)\left(v_0+\frac{A}{\operatorname{gcd}(A,B)}k\right)}}\lambda_h\right)^2. \tag*{(85)} S ≤ k ∈ Z B gcd ( A , B ) ( 2 a x − u 0 ) ≤ k k ≤ B gcd ( A , B ) ( a x − u 0 ) ∑ 1 ≤ h ≤ z h ∣ ( u 0 + gcd ( A , B ) B k ) ( v 0 + gcd ( A , B ) A k ) ∑ λ h 2 . (85)
Expanding the square in (85) (as a double sum) and interchanging the order of finite summation, we find that
S ≤ ∑ 1 ≤ h , j ≤ z λ h λ j ∑ k ∈ Z gcd ( A , B ) B ( x 2 a − u 0 ) ≤ k k ≤ gcd ( A , B ) B ( x a − u 0 ) lcm ( h , j ) ( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) 1 , (86) S \le\sum_{1 \le h,j \le z} \lambda_h\lambda_j
\sum_{\substack{k\in\mathbb{Z}\\
\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{2a}-u_0\right)\le k\\
k\le\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{a}-u_0\right)\\
\operatorname{lcm}(h,j)\left(u_0+\frac{B}{\operatorname{gcd}(A,B)}k\right)\left(v_0+\frac{A}{\operatorname{gcd}(A,B)}k\right)}} 1, \tag*{(86)} S ≤ 1 ≤ h , j ≤ z ∑ λ h λ j k ∈ Z B gcd ( A , B ) ( 2 a x − u 0 ) ≤ k k ≤ B gcd ( A , B ) ( a x − u 0 ) lcm ( h , j ) ( u 0 + gcd ( A , B ) B k ) ( v 0 + gcd ( A , B ) A k ) ∑ 1 , (86)
where h h h and j j j range over positive integers. Fix positive integers h , j ≤ z h,j\le z h , j ≤ z . The divisibility condition associated with the inner sum in (86) is equivalent to
( u 0 + B gcd ( A , B ) k ) ( v 0 + A gcd ( A , B ) k ) ≡ 0 ( m o d lcm ( h , j ) ) . (87) \left(u_0+\frac{B}{\operatorname{gcd}(A,B)}k\right)\left(v_0+\frac{A}{\operatorname{gcd}(A,B)}k\right)\equiv0 \pmod{\operatorname{lcm}(h,j)}. \tag*{(87)} ( u 0 + gcd ( A , B ) B k ) ( v 0 + gcd ( A , B ) A k ) ≡ 0 ( mod lcm ( h , j )) . (87)
From the definition of ρ ( m ) \rho(m) ρ ( m ) (recalling (74) ), the congruence in (87) is satisfied by exactly ρ ( lcm ( h , j ) ) \rho(\operatorname{lcm}(h,j)) ρ ( lcm ( h , j )) residue classes modulo lcm ( h , j ) \operatorname{lcm}(h,j) lcm ( h , j ) . We are counting the integers in these classes that lie in
[ gcd ( A , B ) B ( x 2 a − u 0 ) , gcd ( A , B ) B ( x a − u 0 ) ] , (88) \left[\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{2a}-u_0\right),\frac{\operatorname{gcd}(A,B)}{B}\left(\frac{x}{a}-u_0\right)\right], \tag*{(88)} [ B gcd ( A , B ) ( 2 a x − u 0 ) , B gcd ( A , B ) ( a x − u 0 ) ] , (88)
noting that the interval in (88) is of length x gcd ( A , B ) 2 a B \frac{x\operatorname{gcd}(A,B)}{2aB} 2 a B x gcd ( A , B ) . From a previous argument, the number of integers in each fixed residue class modulo lcm ( h , j ) \operatorname{lcm}(h,j) lcm ( h , j ) lying in the interval in (88) differs from x gcd ( A , B ) 2 a B lcm ( h , j ) \frac{x\operatorname{gcd}(A,B)}{2aB\operatorname{lcm}(h,j)} 2 a B lcm ( h , j ) x gcd ( A , B ) by at most 1. Since the ρ ( lcm ( h , j ) ) \rho(\operatorname{lcm}(h,j)) ρ ( lcm ( h , j )) residue classes are disjoint, by adding the number of integers belonging to each residue class, with only integers in the interval (88) being counted, we obtain exactly the inner sum over k k k in (86) .
Fix h h h and j j j . Let N i N_i N i denote the number of integers in (88) belonging to the i t h i^{\mathrm{th}} i th of the ρ ( lcm ( h , j ) ) \rho(\operatorname{lcm}(h,j)) ρ ( lcm ( h , j )) residue classes satisfying the congruence relation in (87) . As above, we have established that
∣ N i − x gcd ( A , B ) 2 a B lcm ( h , j ) ∣ ≤ 1 \left|N_i-\frac{x\operatorname{gcd}(A,B)}{2aB\operatorname{lcm}(h,j)}\right|\le1 N i − 2 a B lcm ( h , j ) x gcd ( A , B ) ≤ 1
for each index i i i . By construction, the inner sum in (86) over k k k is precisely ∑ i = 1 ρ ( lcm ( h , j ) ) N i \sum_{i=1}^{\rho(\operatorname{lcm}(h,j))}N_i ∑ i = 1 ρ ( lcm ( h , j )) N i . An application of the triangle inequality then gives us that
∣ ∑ i = 1 ρ ( lcm ( h , j ) ) N i − x gcd ( A , B ) ρ ( lcm ( h , j ) ) 2 a B lcm ( h , j ) ∣ = ∣ ∑ i = 1 ρ ( lcm ( h , j ) ) ( N i − x gcd ( A , B ) 2 a B lcm ( h , j ) ) ∣ ≤ ∑ i = 1 ρ ( lcm ( h , j ) ) ∣ N i − x gcd ( A , B ) 2 a B lcm ( h , j ) ∣ . ≤ ∑ i = 1 ρ ( lcm ( h , j ) ) 1 = ρ ( lcm ( h , j ) ) . \begin{aligned}
\left|\sum_{i=1}^{\rho(\operatorname{lcm}(h,j))}N_i-\frac{x\operatorname{gcd}(A,B)\rho(\operatorname{lcm}(h,j))}{2aB\operatorname{lcm}(h,j)}\right| \\
&=\left|\sum_{i=1}^{\rho(\operatorname{lcm}(h,j))}\left(N_i-\frac{x\operatorname{gcd}(A,B)}{2aB\operatorname{lcm}(h,j)}\right)\right| \\
&\le\sum_{i=1}^{\rho(\operatorname{lcm}(h,j))}\left|N_i-\frac{x\operatorname{gcd}(A,B)}{2aB\operatorname{lcm}(h,j)}\right|. \\
&\le\sum_{i=1}^{\rho(\operatorname{lcm}(h,j))} 1 \\
&= \rho(\operatorname{lcm}(h,j)).
\end{aligned} i = 1 ∑ ρ ( lcm ( h , j )) N i − 2 a B lcm ( h , j ) x gcd ( A , B ) ρ ( lcm ( h , j )) = i = 1 ∑ ρ ( lcm ( h , j )) ( N i − 2 a B lcm ( h , j ) x gcd ( A , B ) ) ≤ i = 1 ∑ ρ ( lcm ( h , j )) N i − 2 a B lcm ( h , j ) x gcd ( A , B ) . ≤ i = 1 ∑ ρ ( lcm ( h , j )) 1 = ρ ( lcm ( h , j )) .
So, we have showed that
x gcd ( A , B ) ρ ( lcm ( h , j ) ) 2 a B lcm ( h , j ) − ρ ( lcm ( h , j ) ) ≤ ∑ i = 1 ρ ( lcm ( h , j ) ) N i ≤ x gcd ( A , B ) ρ ( lcm ( h , j ) ) 2 a B lcm ( h , j ) + ρ ( lcm ( h , j ) ) . \frac{x\gcd(A,B)\rho(\operatorname{lcm}(h,j))}{2aB\operatorname{lcm}(h,j)}-\rho(\operatorname{lcm}(h,j))
\le\sum_{i=1}^{\rho(\operatorname{lcm}(h,j))}N_i
\le
\frac{x\gcd(A,B)\rho(\operatorname{lcm}(h,j))}{2aB\operatorname{lcm}(h,j)}+\rho(\operatorname{lcm}(h,j)). 2 a B lcm ( h , j ) x g cd( A , B ) ρ ( lcm ( h , j )) − ρ ( lcm ( h , j )) ≤ i = 1 ∑ ρ ( lcm ( h , j )) N i ≤ 2 a B lcm ( h , j ) x g cd( A , B ) ρ ( lcm ( h , j )) + ρ ( lcm ( h , j )) .
Multiplying the upper bound by λ h λ j \lambda_h\lambda_j λ h λ j when λ h λ j ≥ 0 \lambda_h\lambda_j\geq0 λ h λ j ≥ 0 , and the lower bound by λ h λ j \lambda_h\lambda_j λ h λ j when λ h λ j < 0 \lambda_h\lambda_j<0 λ h λ j < 0 , with the inequality reversed in the latter case, gives
λ h λ j ∑ i = 1 ρ ( lcm ( h , j ) ) N i ≤ x gcd ( A , B ) 2 a B λ h λ j ρ ( lcm ( h , j ) ) lcm ( h , j ) + ∣ λ h λ j ∣ ρ ( lcm ( h , j ) ) . \lambda_h\lambda_j\sum_{i=1}^{\rho(\operatorname{lcm}(h,j))}N_i
\leq\frac{x\gcd(A,B)}{2aB}\lambda_h\lambda_j\frac{\rho(\operatorname{lcm}(h,j))}{\operatorname{lcm}(h,j)}
+|\lambda_h\lambda_j|\rho(\operatorname{lcm}(h,j)). λ h λ j i = 1 ∑ ρ ( lcm ( h , j )) N i ≤ 2 a B x g cd( A , B ) λ h λ j lcm ( h , j ) ρ ( lcm ( h , j )) + ∣ λ h λ j ∣ ρ ( lcm ( h , j )) .
Summing the last inequality over all pairs of positive integers h , j ≤ z h,j\leq z h , j ≤ z and using (87), we obtain
S ≤ x gcd ( A , B ) 2 a B ∑ 1 ≤ h , j ≤ z λ h λ j ρ ( lcm ( h , j ) ) lcm ( h , j ) + ∑ 1 ≤ h , j ≤ z ∣ λ h λ j ∣ ρ ( lcm ( h , j ) ) . (89) S\leq\frac{x\gcd(A,B)}{2aB}
\sum_{1\leq h,j\leq z}\lambda_h\lambda_j
\frac{\rho(\operatorname{lcm}(h,j))}{\operatorname{lcm}(h,j)}
+
\sum_{1\leq h,j\leq z}|\lambda_h\lambda_j|\rho(\operatorname{lcm}(h,j)). \tag*{(89)} S ≤ 2 a B x g cd( A , B ) 1 ≤ h , j ≤ z ∑ λ h λ j lcm ( h , j ) ρ ( lcm ( h , j )) + 1 ≤ h , j ≤ z ∑ ∣ λ h λ j ∣ ρ ( lcm ( h , j )) . (89)
Since A gcd ( A , B ) \frac{A}{\gcd(A,B)} g c d ( A , B ) A and B gcd ( A , B ) \frac{B}{\gcd(A,B)} g c d ( A , B ) B are relatively prime, for each prime p p p , at least one of the congruences among (76) and (77) has a coefficient of k k k that is invertible modulo p p p and therefore has a solution, so ρ ( p ) ≥ 1 \rho(p)\geq1 ρ ( p ) ≥ 1 . Now, for every positive squarefree integer m m m , we have ρ ( m ) = ∏ p ∣ m ρ ( p ) > 0 \rho(m)=\prod_{p\mid m}\rho(p)>0 ρ ( m ) = ∏ p ∣ m ρ ( p ) > 0 by (80), and expanding the finite product gives
m ρ ( m ) = ∏ p ∣ m p ρ ( p ) = ∏ p ∣ m ( 1 + p − ρ ( p ) ρ ( p ) ) = ∑ d ∣ m ∏ p ∣ d p − ρ ( p ) ρ ( p ) . (90) \begin{aligned}
\frac{m}{\rho(m)}
=\prod_{p\mid m}\frac{p}{\rho(p)}
=\prod_{p\mid m}\left(1+\frac{p-\rho(p)}{\rho(p)}\right) \\
&=\sum_{d\mid m}\prod_{p\mid d}\frac{p-\rho(p)}{\rho(p)}. \tag*{(90)}
\end{aligned} ρ ( m ) m = p ∣ m ∏ ρ ( p ) p = p ∣ m ∏ ( 1 + ρ ( p ) p − ρ ( p ) ) = d ∣ m ∑ p ∣ d ∏ ρ ( p ) p − ρ ( p ) . (90)
For positive squarefree integers h h h and j j j , the prime factorization formula for ρ \rho ρ , as given in (80), together with the identity in (91) applied to m = gcd ( h , j ) m=\gcd(h,j) m = g cd( h , j ) , gives
ρ ( lcm ( h , j ) ) lcm ( h , j ) = ρ ( h ) ρ ( j ) h j gcd ( h , j ) ρ ( gcd ( h , j ) ) = ρ ( h ) ρ ( j ) h j ∑ d ∣ h d ∣ j ∏ p ∣ d p − ρ ( p ) ρ ( p ) . (91) \begin{aligned}
\frac{\rho(\operatorname{lcm}(h,j))}{\operatorname{lcm}(h,j)}
=\frac{\rho(h)\rho(j)}{hj}\frac{\gcd(h,j)}{\rho(\gcd(h,j))} \\
&=\frac{\rho(h)\rho(j)}{hj}\sum_{\substack{d\mid h\\d\mid j}}\prod_{p\mid d}\frac{p-\rho(p)}{\rho(p)}. \tag*{(91)}
\end{aligned} lcm ( h , j ) ρ ( lcm ( h , j )) = hj ρ ( h ) ρ ( j ) ρ ( g cd( h , j )) g cd( h , j ) = hj ρ ( h ) ρ ( j ) d ∣ h d ∣ j ∑ p ∣ d ∏ ρ ( p ) p − ρ ( p ) . (91)
Since λ h = 0 \lambda_h=0 λ h = 0 whenever h h h is not squarefree, only squarefree h h h and j j j contribute to the first double sum in (90). Applying (92) to these terms, we obtain
∑ 1 ≤ h , j ≤ z λ h λ j ρ ( lcm ( h , j ) ) lcm ( h , j ) = ∑ 1 ≤ h , j ≤ z h , j squarefree λ h ρ ( h ) h λ j ρ ( j ) j ∑ d ∣ h d ∣ j ∏ p ∣ d p − ρ ( p ) ρ ( p ) = ∑ 1 ≤ d ≤ z d squarefree ( ∏ p ∣ d p − ρ ( p ) ρ ( p ) ) ∑ 1 ≤ h , j ≤ z d ∣ h , d ∣ j λ h ρ ( h ) h λ j ρ ( j ) j . \begin{aligned}
\sum_{1\le h,j\le z}\lambda_h\lambda_j\frac{\rho(\operatorname{lcm}(h,j))}{\operatorname{lcm}(h,j)} \\
&= \sum_{\substack{1\le h,j\le z\\h,j\ \text{squarefree}}}\frac{\lambda_h\rho(h)}{h}\frac{\lambda_j\rho(j)}{j}\sum_{\substack{d\mid h\\d\mid j}}\prod_{p\mid d}\frac{p-\rho(p)}{\rho(p)} \\
&= \sum_{\substack{1\le d\le z\\d\ \text{squarefree}}}\left(\prod_{p\mid d}\frac{p-\rho(p)}{\rho(p)}\right)\sum_{\substack{1\le h,j\le z\\d\mid h,\ d\mid j}}\frac{\lambda_h\rho(h)}{h}\frac{\lambda_j\rho(j)}{j}.
\end{aligned} 1 ≤ h , j ≤ z ∑ λ h λ j lcm ( h , j ) ρ ( lcm ( h , j )) = 1 ≤ h , j ≤ z h , j squarefree ∑ h λ h ρ ( h ) j λ j ρ ( j ) d ∣ h d ∣ j ∑ p ∣ d ∏ ρ ( p ) p − ρ ( p ) = 1 ≤ d ≤ z d squarefree ∑ p ∣ d ∏ ρ ( p ) p − ρ ( p ) 1 ≤ h , j ≤ z d ∣ h , d ∣ j ∑ h λ h ρ ( h ) j λ j ρ ( j ) .
In the last equality, we have interchanged the finite sums. Every common divisor d d d of squarefree integers h , j ≤ z h,j\le z h , j ≤ z is itself squarefree and satisfies d ≤ z d\le z d ≤ z . We have also omitted the squarefree restrictions on the inner indices h h h and j j j , since any additional terms vanish by the definition of the weights.
For each fixed d d d , the indices h h h and j j j range independently over the same set of positive multiples of d d d not exceeding z z z . Thus the inner double sum factors as
∑ 1 ≤ h , j ≤ z d ∣ h , d ∣ j λ h ρ ( h ) h λ j ρ ( j ) j = ( ∑ 1 ≤ h ≤ z d ∣ h λ h ρ ( h ) h ) ( ∑ 1 ≤ j ≤ z d ∣ j λ j ρ ( j ) j ) = ( ∑ 1 ≤ h ≤ z d ∣ h λ h ρ ( h ) h ) 2 , \begin{aligned}
\sum_{\substack{1\le h,j\le z\\d\mid h,\ d\mid j}}\frac{\lambda_h\rho(h)}{h}\frac{\lambda_j\rho(j)}{j} \\
&=\left(\sum_{\substack{1\le h\le z\\d\mid h}}\frac{\lambda_h\rho(h)}{h}\right)\left(\sum_{\substack{1\le j\le z\\d\mid j}}\frac{\lambda_j\rho(j)}{j}\right) \\
&=\left(\sum_{\substack{1\le h\le z\\d\mid h}}\frac{\lambda_h\rho(h)}{h}\right)^2,
\end{aligned} 1 ≤ h , j ≤ z d ∣ h , d ∣ j ∑ h λ h ρ ( h ) j λ j ρ ( j ) = 1 ≤ h ≤ z d ∣ h ∑ h λ h ρ ( h ) 1 ≤ j ≤ z d ∣ j ∑ j λ j ρ ( j ) = 1 ≤ h ≤ z d ∣ h ∑ h λ h ρ ( h ) 2 ,
where the last equality follows by renaming the summation variable in the second factor. Consequently, we have that
∑ 1 ≤ h , j ≤ z λ h λ j ρ ( lcm ( h , j ) ) lcm ( h , j ) = \sum_{1\le h,j\le z}\lambda_h\lambda_j\frac{\rho(\operatorname{lcm}(h,j))}{\operatorname{lcm}(h,j)}
= 1 ≤ h , j ≤ z ∑ λ h λ j lcm ( h , j ) ρ ( lcm ( h , j )) =
∑ 1 ≤ d ≤ z d squarefree ( ∏ p ∣ d p − ρ ( p ) ρ ( p ) ) ( ∑ 1 ≤ h ≤ z d ∣ h λ h ρ ( h ) h ) 2 . \sum_{\substack{1\le d\le z\\d\ \text{squarefree}}}\left(\prod_{p\mid d}\frac{p-\rho(p)}{\rho(p)}\right)\left(\sum_{\substack{1\le h\le z\\d\mid h}}\frac{\lambda_h\rho(h)}{h}\right)^2. 1 ≤ d ≤ z d squarefree ∑ p ∣ d ∏ ρ ( p ) p − ρ ( p ) 1 ≤ h ≤ z d ∣ h ∑ h λ h ρ ( h ) 2 .
For each positive squarefree integer h ≤ z h \le z h ≤ z , we now specify
λ h = ( − 1 ) ω ( h ) G ( z ) ( ∏ p ∣ h p p − ρ ( p ) ) ∑ 1 ≤ m ≤ z m s q u a r e f r e e gcd ( m , h ) = 1 ∏ p ∣ m ρ ( p ) p − ρ ( p ) . (92) \lambda_h = \frac{(-1)^{\omega(h)}}{\mathcal{G}(z)}
\left(\prod_{p\mid h}\frac{p}{p-\rho(p)}\right)
\sum_{\substack{1\le m\le z\\ m\ \mathrm{squarefree}\\ \gcd(m,h)=1}}
\prod_{p\mid m}\frac{\rho(p)}{p-\rho(p)}. \tag*{(92)} λ h = G ( z ) ( − 1 ) ω ( h ) p ∣ h ∏ p − ρ ( p ) p 1 ≤ m ≤ z m squarefree g c d ( m , h ) = 1 ∑ p ∣ m ∏ p − ρ ( p ) ρ ( p ) . (92)
while retaining λ h = 0 \lambda_h=0 λ h = 0 for all other positive integers h h h . Taking h = 1 h=1 h = 1 in (92) , and using the relations ω ( 1 ) = 0 \omega(1)=0 ω ( 1 ) = 0 and gcd ( m , 1 ) = 1 \gcd(m,1)=1 g cd( m , 1 ) = 1 together with the empty-product convention, we obtain
λ 1 = 1 G ( z ) ∑ 1 ≤ m ≤ z m s q u a r e f r e e ∏ p ∣ m ρ ( p ) p − ρ ( p ) = G ( z ) G ( z ) = 1. \lambda_1=\frac{1}{\mathcal{G}(z)}
\sum_{\substack{1\le m\le z\\m\ \mathrm{squarefree}}}
\prod_{p\mid m}\frac{\rho(p)}{p-\rho(p)}
=\frac{\mathcal{G}(z)}{\mathcal{G}(z)}=1. λ 1 = G ( z ) 1 1 ≤ m ≤ z m squarefree ∑ p ∣ m ∏ p − ρ ( p ) ρ ( p ) = G ( z ) G ( z ) = 1.
For every positive squarefree integer h ≤ z h\le z h ≤ z , the sum over m m m in the formula in (92) is at most G ( z ) \mathcal{G}(z) G ( z ) , since z h ≤ z \frac{z}{h}\le z h z ≤ z and all the summands are nonnegative, so
∣ λ h ∣ ≤ ∏ p ∣ h p p − ρ ( p ) ≤ ∏ p ∣ h p = h , |\lambda_h|\le\prod_{p\mid h}\frac{p}{p-\rho(p)}
\le\prod_{p\mid h}p=h, ∣ λ h ∣ ≤ p ∣ h ∏ p − ρ ( p ) p ≤ p ∣ h ∏ p = h ,
where the second inequality follows from p − ρ ( p ) ≥ 1 p-\rho(p)\ge1 p − ρ ( p ) ≥ 1 .
Because ρ ( m ) \rho(m) ρ ( m ) counts residue classes modulo m m m , we have ρ ( m ) ≤ m \rho(m)\le m ρ ( m ) ≤ m for every positive integer m m m , and hence, using lcm ( h , j ) ≤ h j \operatorname{lcm}(h,j)\le hj lcm ( h , j ) ≤ hj and ∣ λ h ∣ ≤ h |\lambda_h|\le h ∣ λ h ∣ ≤ h also when λ h = 0 \lambda_h=0 λ h = 0 , we obtain
∑ 1 ≤ h , j ≤ z ∣ λ h λ j ∣ ρ ( lcm ( h , j ) ) ≤ ∑ 1 ≤ h , j ≤ z h 2 j 2 = ( ∑ 1 ≤ h ≤ z h 2 ) 2 ≤ ( ⌊ z ⌋ z 2 ) 2 ≤ z 6 , \begin{aligned}
\sum_{1\le h,j\le z}|\lambda_h\lambda_j|\rho(\operatorname{lcm}(h,j))
\le\sum_{1\le h,j\le z}h^2j^2 \\
&=\left(\sum_{1\le h\le z}h^2\right)^2
\le\left(\lfloor z\rfloor z^2\right)^2
\le z^6,
\end{aligned} 1 ≤ h , j ≤ z ∑ ∣ λ h λ j ∣ ρ ( lcm ( h , j )) ≤ 1 ≤ h , j ≤ z ∑ h 2 j 2 = ( 1 ≤ h ≤ z ∑ h 2 ) 2 ≤ ( ⌊ z ⌋ z 2 ) 2 ≤ z 6 ,
so that (81) then gives us the upper bound
∑ 1 ≤ h , j ≤ z ∣ λ h λ j ∣ ρ ( lcm ( h , j ) ) ≤ x 0.03 (93) \sum_{1\le h,j\le z}|\lambda_h\lambda_j|\rho(\operatorname{lcm}(h,j))\le x^{0.03} \tag*{(93)} 1 ≤ h , j ≤ z ∑ ∣ λ h λ j ∣ ρ ( lcm ( h , j )) ≤ x 0.03 (93)
for the latter double sum in (90).
For each positive squarefree integer h h h not exceeding z z z , multiplying (93) by ρ ( h ) h \frac{\rho(h)}{h} h ρ ( h ) , using the relation in (80) and then changing variables from m m m to n = h m n=hm n = hm , this gives us that
λ h ρ ( h ) h = ( − 1 ) ω ( h ) G ( z ) ( ∏ p ∣ h ρ ( p ) p − ρ ( p ) ) ∑ 1 ≤ m ≤ z / h m s q u a r e f r e e gcd ( m , h ) = 1 ∏ p ∣ m ρ ( p ) p − ρ ( p ) = ( − 1 ) ω ( h ) G ( z ) ∑ 1 ≤ n ≤ z n s q u a r e f r e e h ∣ n ∏ p ∣ n ρ ( p ) p − ρ ( p ) . (94) \begin{aligned}
\frac{\lambda_h\rho(h)}{h}
&= \frac{(-1)^{\omega(h)}}{G(z)}
\left(\prod_{p\mid h}\frac{\rho(p)}{p-\rho(p)}\right)
\sum_{\substack{1\le m\le z/h\\ m\ \mathrm{squarefree}\\ \gcd(m,h)=1}}
\prod_{p\mid m}\frac{\rho(p)}{p-\rho(p)} \\
&= \frac{(-1)^{\omega(h)}}{G(z)}
\sum_{\substack{1\le n\le z\\ n\ \mathrm{squarefree}\\ h\mid n}}
\prod_{p\mid n}\frac{\rho(p)}{p-\rho(p)}. \tag*{(94)}
\end{aligned} h λ h ρ ( h ) = G ( z ) ( − 1 ) ω ( h ) p ∣ h ∏ p − ρ ( p ) ρ ( p ) 1 ≤ m ≤ z / h m squarefree g c d ( m , h ) = 1 ∑ p ∣ m ∏ p − ρ ( p ) ρ ( p ) = G ( z ) ( − 1 ) ω ( h ) 1 ≤ n ≤ z n squarefree h ∣ n ∑ p ∣ n ∏ p − ρ ( p ) ρ ( p ) . (94)
For each positive squarefree integer d ≤ z d\le z d ≤ z , summing the preceding identity over squarefree multiples h ≤ z h\le z h ≤ z of d d d , interchanging the finite sums, and recalling that λ h = 0 \lambda_h=0 λ h = 0 for nonsquarefree h h h , we obtain
∑ 1 ≤ h ≤ z d ∣ h λ h ρ ( h ) h = 1 G ( z ) ∑ 1 ≤ n ≤ z n s q u a r e f r e e d ∣ n ( ∏ p ∣ n ρ ( p ) p − ρ ( p ) ) ∑ h ∣ n d ∣ h ( − 1 ) ω ( h ) . (95) \sum_{\substack{1\le h\le z\\ d\mid h}}\frac{\lambda_h\rho(h)}{h}
=
\frac{1}{G(z)}
\sum_{\substack{1\le n\le z\\ n\ \mathrm{squarefree}\\ d\mid n}}
\left(\prod_{p\mid n}\frac{\rho(p)}{p-\rho(p)}\right)
\sum_{\substack{h\mid n\\ d\mid h}}(-1)^{\omega(h)}. \tag*{(95)} 1 ≤ h ≤ z d ∣ h ∑ h λ h ρ ( h ) = G ( z ) 1 1 ≤ n ≤ z n squarefree d ∣ n ∑ p ∣ n ∏ p − ρ ( p ) ρ ( p ) h ∣ n d ∣ h ∑ ( − 1 ) ω ( h ) . (95)
For each positive squarefree integer n n n divisible by d d d , the substitution h = d e h=de h = d e , with e e e ranging over the positive divisors of n d \frac{n}{d} d n , gives us that ω ( h ) = ω ( d ) + ω ( e ) \omega(h)=\omega(d)+\omega(e) ω ( h ) = ω ( d ) + ω ( e ) , since gcd ( d , e ) = 1 \gcd(d,e)=1 g cd( d , e ) = 1 , and hence
∑ h ∣ n d ∣ h ( − 1 ) ω ( h ) = ( − 1 ) ω ( d ) ∑ e ∣ n / d ( − 1 ) ω ( e ) = ( − 1 ) ω ( d ) ∏ p ∣ n / d ( 1 − 1 ) = { ( − 1 ) ω ( d ) , n = d , 0 , n > d . \begin{aligned}
\sum_{\substack{h\mid n\\ d\mid h}}(-1)^{\omega(h)}
=
(-1)^{\omega(d)}
\sum_{e\mid n/d}(-1)^{\omega(e)} \\
&=
(-1)^{\omega(d)}
\prod_{p\mid n/d}(1-1) \\
&=
\begin{cases}
(-1)^{\omega(d)}, & n=d,\\
0, & n>d.
\end{cases}
\end{aligned} h ∣ n d ∣ h ∑ ( − 1 ) ω ( h ) = ( − 1 ) ω ( d ) e ∣ n / d ∑ ( − 1 ) ω ( e ) = ( − 1 ) ω ( d ) p ∣ n / d ∏ ( 1 − 1 ) = { ( − 1 ) ω ( d ) , 0 , n = d , n > d .
For each positive squarefree integer d ≤ z d\le z d ≤ z , substituting the above evaluation for ∑ h ∣ n d ∣ h ( − 1 ) ω ( h ) \sum_{\substack{h\mid n\\ d\mid h}}(-1)^{\omega(h)} ∑ h ∣ n d ∣ h ( − 1 ) ω ( h ) into the right-hand side of (96) leaves only the term corresponding to n = d n=d n = d , yielding
∑ 1 ≤ h ≤ z d ∣ h λ h ρ ( h ) h = ( − 1 ) ω ( d ) G ( z ) ∏ p ∣ d ρ ( p ) p − ρ ( p ) . \sum_{\substack{1\le h\le z\\ d\mid h}}\frac{\lambda_h\rho(h)}{h}
=
\frac{(-1)^{\omega(d)}}{G(z)}
\prod_{p\mid d}\frac{\rho(p)}{p-\rho(p)}. 1 ≤ h ≤ z d ∣ h ∑ h λ h ρ ( h ) = G ( z ) ( − 1 ) ω ( d ) p ∣ d ∏ p − ρ ( p ) ρ ( p ) .
Substituting this identity into the sum of squares for the first double sum in the bound for S S S displayed in (89) , and using ( − 1 ) 2 ω ( d ) = 1 (-1)^{2\omega(d)}=1 ( − 1 ) 2 ω ( d ) = 1 , we obtain
∑ 1 ≤ h , j ≤ z λ h λ j ρ ( lcm ( h , j ) ) lcm ( h , j ) = ∑ 1 ≤ d ≤ z d squarefree ( ∏ p ∣ d p − ρ ( p ) ρ ( p ) ) ( ( − 1 ) ω ( d ) G ( z ) ∏ p ∣ d ρ ( p ) p − ρ ( p ) ) 2 = 1 G ( z ) 2 ∑ 1 ≤ d ≤ z d squarefree ∏ p ∣ d ρ ( p ) p − ρ ( p ) = 1 G ( z ) . \begin{aligned}
\sum_{1\le h,j\le z}\lambda_h\lambda_j\frac{\rho(\operatorname{lcm}(h,j))}{\operatorname{lcm}(h,j)}
=
\sum_{\substack{1\le d\le z\\ d\ \text{squarefree}}}
\left(\prod_{p\mid d}\frac{p-\rho(p)}{\rho(p)}\right)
\left(\frac{(-1)^{\omega(d)}}{G(z)}\prod_{p\mid d}\frac{\rho(p)}{p-\rho(p)}\right)^2 \\
&=\frac{1}{G(z)^2}
\sum_{\substack{1\le d\le z\\ d\ \text{squarefree}}}
\prod_{p\mid d}\frac{\rho(p)}{p-\rho(p)} \\
&=\frac{1}{G(z)}.
\end{aligned} 1 ≤ h , j ≤ z ∑ λ h λ j lcm ( h , j ) ρ ( lcm ( h , j )) = 1 ≤ d ≤ z d squarefree ∑ p ∣ d ∏ ρ ( p ) p − ρ ( p ) G ( z ) ( − 1 ) ω ( d ) p ∣ d ∏ p − ρ ( p ) ρ ( p ) 2 = G ( z ) 2 1 1 ≤ d ≤ z d squarefree ∑ p ∣ d ∏ p − ρ ( p ) ρ ( p ) = G ( z ) 1 .
Substituting 1 G ( z ) \frac{1}{G(z)} G ( z ) 1 for the first double sum in (89) , and using the upper bound of x 0.03 x^{0.03} x 0.03 in (93) for the latter double sum, we obtain
S ≤ x gcd ( A , B ) 2 a B G ( z ) + x 0.03 . (96) S\le\frac{x\gcd(A,B)}{2aB G(z)}+x^{0.03}. \tag*{(96)} S ≤ 2 a B G ( z ) x g cd( A , B ) + x 0.03 . (96)
Since ρ ( p ) = 2 \rho(p)=2 ρ ( p ) = 2 whenever p ∤ 2 A B ∣ a − b ∣ p\nmid2AB|a-b| p ∤ 2 A B ∣ a − b ∣ , omitting the nonnegative terms with gcd ( h , 2 A B ∣ a − b ∣ ) > 1 \gcd(h,2AB|a-b|)>1 g cd( h , 2 A B ∣ a − b ∣ ) > 1 from G ( z ) G(z) G ( z ) and using the relation 2 p − 2 ≥ 2 p \frac{2}{p-2}\ge\frac{2}{p} p − 2 2 ≥ p 2 for p > 2 p>2 p > 2 gives
G ( z ) ≥ ∑ 1 ≤ h ≤ z h squarefree gcd ( h , 2 A B ∣ a − b ∣ ) = 1 ∏ p ∣ h 2 p − 2 ≥ ∑ 1 ≤ h ≤ z h squarefree gcd ( h , 2 A B ∣ a − b ∣ ) = 1 2 ω ( h ) h . \begin{aligned}
G(z)\ge
\sum_{\substack{1\le h\le z\\ h\ \text{squarefree}\\ \gcd(h,2AB|a-b|)=1}}
\prod_{p\mid h}\frac{2}{p-2} \\
&\ge
\sum_{\substack{1\le h\le z\\ h\ \text{squarefree}\\ \gcd(h,2AB|a-b|)=1}}
\frac{2^{\omega(h)}}{h}.
\end{aligned} G ( z ) ≥ 1 ≤ h ≤ z h squarefree g c d ( h , 2 A B ∣ a − b ∣ ) = 1 ∑ p ∣ h ∏ p − 2 2 ≥ 1 ≤ h ≤ z h squarefree g c d ( h , 2 A B ∣ a − b ∣ ) = 1 ∑ h 2 ω ( h ) .
Writing each positive squarefree integer h h h uniquely as h = d m h=dm h = d m , where d d d is the product of the prime divisors of h h h that divide 2 A B ∣ a − b ∣ 2AB|a-b| 2 A B ∣ a − b ∣ and m = h d m=\frac{h}{d} m = d h , and using ω ( h ) = ω ( d ) + ω ( m ) \omega(h)=\omega(d)+\omega(m) ω ( h ) = ω ( d ) + ω ( m ) , we obtain
∑ 1 ≤ h ≤ z h squarefree 2 ω ( h ) h = ∑ d ∣ 2 A B ∣ a − b ∣ d squarefree 2 ω ( d ) d ∑ 1 ≤ m ≤ z / d m squarefree gcd ( m , 2 A B ∣ a − b ∣ ) = 1 2 ω ( m ) m . \sum_{\substack{1\le h\le z\\ h\ \text{squarefree}}}\frac{2^{\omega(h)}}{h}
=
\sum_{\substack{d\mid2AB|a-b|\\ d\ \text{squarefree}}}\frac{2^{\omega(d)}}{d}
\sum_{\substack{1\le m\le z/d\\ m\ \text{squarefree}\\ \gcd(m,2AB|a-b|)=1}}
\frac{2^{\omega(m)}}{m}. 1 ≤ h ≤ z h squarefree ∑ h 2 ω ( h ) = d ∣ 2 A B ∣ a − b ∣ d squarefree ∑ d 2 ω ( d ) 1 ≤ m ≤ z / d m squarefree g c d ( m , 2 A B ∣ a − b ∣ ) = 1 ∑ m 2 ω ( m ) .
Since z d ≤ z \frac{z}{d}\le z d z ≤ z and all summands are nonnegative, replacing m ≤ z d m\le\frac{z}{d} m ≤ d z by m ≤ z m\le z m ≤ z in each inner sum and using the expansion of B 1 , 2 \mathcal{B}_{1,2} B 1 , 2 over squarefree divisors gives
∑ 1 ≤ h ≤ z h s q u a r e f r e e 2 ω ( h ) h ≤ ( ∑ d ∣ 2 A B ∣ a − b ∣ d s q u a r e f r e e 2 ω ( d ) d ) ∑ 1 ≤ m ≤ z m s q u a r e f r e e gcd ( m , 2 A B ∣ a − b ∣ ) = 1 2 ω ( m ) m = B 1 , 2 ( 2 A B ∣ a − b ∣ ) ∑ 1 ≤ m ≤ z m s q u a r e f r e e gcd ( m , 2 A B ∣ a − b ∣ ) = 1 2 ω ( m ) m . \begin{aligned}
\sum_{\substack{1\le h\le z\\ h\ \mathrm{squarefree}}}\frac{2^{\omega(h)}}{h}
\le
\left(\sum_{\substack{d\mid2AB|a-b|\\ d\ \mathrm{squarefree}}}\frac{2^{\omega(d)}}{d}\right)
\sum_{\substack{1\le m\le z\\ m\ \mathrm{squarefree}\\ \gcd(m,2AB|a-b|)=1}}\frac{2^{\omega(m)}}{m} \\
&= B_{1,2}(2AB|a-b|)
\sum_{\substack{1\le m\le z\\ m\ \mathrm{squarefree}\\ \gcd(m,2AB|a-b|)=1}}\frac{2^{\omega(m)}}{m}.
\end{aligned} 1 ≤ h ≤ z h squarefree ∑ h 2 ω ( h ) ≤ d ∣ 2 A B ∣ a − b ∣ d squarefree ∑ d 2 ω ( d ) 1 ≤ m ≤ z m squarefree g c d ( m , 2 A B ∣ a − b ∣ ) = 1 ∑ m 2 ω ( m ) = B 1 , 2 ( 2 A B ∣ a − b ∣ ) 1 ≤ m ≤ z m squarefree g c d ( m , 2 A B ∣ a − b ∣ ) = 1 ∑ m 2 ω ( m ) .
Since the sum over m m m on the right is at most G ( z ) G(z) G ( z ) , dividing by the positive quantity B 1 , 2 ( 2 A B ∣ a − b ∣ ) B_{1,2}(2AB|a-b|) B 1 , 2 ( 2 A B ∣ a − b ∣ ) gives
G ( z ) ≥ 1 B 1 , 2 ( 2 A B ∣ a − b ∣ ) ∑ 1 ≤ h ≤ z h s q u a r e f r e e 2 ω ( h ) h . (97) G(z)\ge\frac{1}{B_{1,2}(2AB|a-b|)}
\sum_{\substack{1\le h\le z\\ h\ \mathrm{squarefree}}}\frac{2^{\omega(h)}}{h}. \tag*{(97)} G ( z ) ≥ B 1 , 2 ( 2 A B ∣ a − b ∣ ) 1 1 ≤ h ≤ z h squarefree ∑ h 2 ω ( h ) . (97)
Since every positive squarefree integer h h h has exactly 2 ω ( h ) 2^{\omega(h)} 2 ω ( h ) ordered factorizations h = m n h=mn h = mn into positive integers, and restricting to odd m , n ≤ z m,n\le\sqrt{z} m , n ≤ z only removes nonnegative terms, we have
∑ 1 ≤ h ≤ z h s q u a r e f r e e 2 ω ( h ) h = ∑ m , n ≥ 1 m n ≤ z m n s q u a r e f r e e 1 m n ≥ ∑ 1 ≤ m , n ≤ z m , n o d d m n s q u a r e f r e e 1 m n . \begin{aligned}
\sum_{\substack{1\le h\le z\\ h\ \mathrm{squarefree}}}\frac{2^{\omega(h)}}{h}
=
\sum_{\substack{m,n\ge1\\ mn\le z\\ mn\ \mathrm{squarefree}}}\frac{1}{mn} \\
&\ge
\sum_{\substack{1\le m,n\le\sqrt{z}\\ m,n\ \mathrm{odd}\\ mn\ \mathrm{squarefree}}}\frac{1}{mn}.
\end{aligned} 1 ≤ h ≤ z h squarefree ∑ h 2 ω ( h ) = m , n ≥ 1 mn ≤ z mn squarefree ∑ mn 1 ≥ 1 ≤ m , n ≤ z m , n odd mn squarefree ∑ mn 1 .
Separating the ordered pairs of odd positive integers m , n ≤ z m,n\le\sqrt{z} m , n ≤ z according to whether m n mn mn is squarefree, and factoring the sum over all such pairs, gives
∑ 1 ≤ m , n ≤ z m , n o d d m n s q u a r e f r e e 1 m n = ( ∑ 1 ≤ m ≤ z m o d d 1 m ) 2 − ∑ 1 ≤ m , n ≤ z m , n o d d m n n o t s q u a r e f r e e 1 m n . \sum_{\substack{1\le m,n\le\sqrt{z}\\ m,n\ \mathrm{odd}\\ mn\ \mathrm{squarefree}}}\frac{1}{mn}
=
\left(\sum_{\substack{1\le m\le\sqrt{z}\\ m\ \mathrm{odd}}}\frac{1}{m}\right)^2
-
\sum_{\substack{1\le m,n\le\sqrt{z}\\ m,n\ \mathrm{odd}\\ mn\ \mathrm{not\ squarefree}}}\frac{1}{mn}. 1 ≤ m , n ≤ z m , n odd mn squarefree ∑ mn 1 = 1 ≤ m ≤ z m odd ∑ m 1 2 − 1 ≤ m , n ≤ z m , n odd mn not squarefree ∑ mn 1 .
Now, if m m m and n n n are odd positive integers and m n mn mn is not squarefree, then some odd prime p p p satisfies p 2 ∣ m n p^2\mid mn p 2 ∣ mn , and considering the exponents of p p p in m m m and n n n shows that at least one proposition among p 2 ∣ m p^2\mid m p 2 ∣ m , p 2 ∣ n p^2\mid n p 2 ∣ n , and ( p ∣ m and p ∣ n ) (p\mid m\text{ and }p\mid n) ( p ∣ m and p ∣ n ) holds.
For each odd prime p p p , substituting m = p 2 k m=p^{2}k m = p 2 k and using the relation z p 2 ≤ z \frac{\sqrt{z}}{p^{2}}\le\sqrt{z} p 2 z ≤ z gives
∑ 1 ≤ m , n ≤ z m , n o d d p 2 ∣ m 1 m n = 1 p 2 ( ∑ 1 ≤ k ≤ z p 2 k o d d 1 k ) ( ∑ 1 ≤ n ≤ z n o d d 1 n ) ≤ 1 p 2 ( ∑ 1 ≤ m ≤ z m o d d 1 m ) 2 , \sum_{\substack{1\le m,n\le\sqrt{z}\\m,n\ \mathrm{odd}\\p^{2}\mid m}}\frac{1}{mn}
=\frac{1}{p^{2}}\left(\sum_{\substack{1\le k\le\frac{\sqrt{z}}{p^{2}}\\k\ \mathrm{odd}}}\frac{1}{k}\right)\left(\sum_{\substack{1\le n\le\sqrt{z}\\n\ \mathrm{odd}}}\frac{1}{n}\right)
\le\frac{1}{p^{2}}\left(\sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}}}\frac{1}{m}\right)^{2}, 1 ≤ m , n ≤ z m , n odd p 2 ∣ m ∑ mn 1 = p 2 1 1 ≤ k ≤ p 2 z k odd ∑ k 1 1 ≤ n ≤ z n odd ∑ n 1 ≤ p 2 1 1 ≤ m ≤ z m odd ∑ m 1 2 ,
and interchanging m m m and n n n gives the same upper bound when p 2 ∣ m p^{2}\mid m p 2 ∣ m is replaced by p 2 ∣ n p^{2}\mid n p 2 ∣ n .
For each odd prime p p p , separating the sums over m m m and n n n , substituting m = p k m=pk m = p k , and using z p ≤ z \frac{\sqrt{z}}{p}\le\sqrt{z} p z ≤ z , we obtain
∑ 1 ≤ m , n ≤ z m , n o d d p ∣ m , p ∣ n 1 m n = ( ∑ 1 ≤ m ≤ z m o d d p ∣ m 1 m ) 2 = 1 p 2 ( ∑ 1 ≤ k ≤ z p k o d d 1 k ) 2 ≤ 1 p 2 ( ∑ 1 ≤ m ≤ z m o d d 1 m ) 2 . \sum_{\substack{1\le m,n\le\sqrt{z}\\m,n\ \mathrm{odd}\\p\mid m,\ p\mid n}}\frac{1}{mn}
=\left(\sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}\\p\mid m}}\frac{1}{m}\right)^{2}
=\frac{1}{p^{2}}\left(\sum_{\substack{1\le k\le\frac{\sqrt{z}}{p}\\k\ \mathrm{odd}}}\frac{1}{k}\right)^{2}
\le\frac{1}{p^{2}}\left(\sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}}}\frac{1}{m}\right)^{2}. 1 ≤ m , n ≤ z m , n odd p ∣ m , p ∣ n ∑ mn 1 = 1 ≤ m ≤ z m odd p ∣ m ∑ m 1 2 = p 2 1 1 ≤ k ≤ p z k odd ∑ k 1 2 ≤ p 2 1 1 ≤ m ≤ z m odd ∑ m 1 2 .
Since every ordered pair of odd positive integers m , n ≤ z m,n\le\sqrt{z} m , n ≤ z with m n mn mn not squarefree satisfies p 2 ∣ m p^{2}\mid m p 2 ∣ m , p 2 ∣ n p^{2}\mid n p 2 ∣ n , or both p ∣ m p\mid m p ∣ m and p ∣ n p\mid n p ∣ n for some prime 2 < p ≤ z 2<p\le\sqrt{z} 2 < p ≤ z , summing the three bounds over these primes, with repeated counting contributing only additional nonnegative terms, gives
∑ 1 ≤ m , n ≤ z m , n o d d m n n o t s q u a r e f r e e 1 m n ≤ 3 ( ∑ 2 < p ≤ z 1 p 2 ) ( ∑ 1 ≤ m ≤ z m o d d 1 m ) 2 . \sum_{\substack{1\le m,n\le\sqrt{z}\\m,n\ \mathrm{odd}\\mn\ \mathrm{not\ squarefree}}}\frac{1}{mn}
\le3\left(\sum_{2<p\le\sqrt{z}}\frac{1}{p^{2}}\right)\left(\sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}}}\frac{1}{m}\right)^{2}. 1 ≤ m , n ≤ z m , n odd mn not squarefree ∑ mn 1 ≤ 3 2 < p ≤ z ∑ p 2 1 1 ≤ m ≤ z m odd ∑ m 1 2 .
Euler’s evaluation for 1 + 1 2 2 + 1 3 2 + ⋯ = π 2 6 1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots=\frac{\pi^2}{6} 1 + 2 2 1 + 3 2 1 + ⋯ = 6 π 2 allows us to obtain the bound
∑ 2 < p ≤ z 1 p 2 ≤ 1 4 . (98) \sum_{2<p\le\sqrt{z}}\frac{1}{p^2}\le\frac{1}{4}. \tag*{(98)} 2 < p ≤ z ∑ p 2 1 ≤ 4 1 . (98)
Using (99) and the bound for the sum with m n mn mn not squarefree gives
∑ 1 ≤ m , n ≤ z m , n o d d m n s q u a r e f r e e 1 m n ≥ ( 1 − 3 4 ) ( ∑ 1 ≤ m ≤ z m o d d 1 m ) 2 = 1 4 ( ∑ 1 ≤ m ≤ z m o d d 1 m ) 2 . \begin{aligned}
\sum_{\substack{1\le m,n\le\sqrt{z}\\m,n\ \mathrm{odd}\\mn\ \mathrm{squarefree}}}\frac{1}{mn}\ge\left(1-\frac{3}{4}\right)\left(\sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}}}\frac{1}{m}\right)^2 \\
&=\frac{1}{4}\left(\sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}}}\frac{1}{m}\right)^2.
\end{aligned} 1 ≤ m , n ≤ z m , n odd mn squarefree ∑ mn 1 ≥ ( 1 − 4 3 ) 1 ≤ m ≤ z m odd ∑ m 1 2 = 4 1 1 ≤ m ≤ z m odd ∑ m 1 2 .
A standard/classical estimate for skew/odd harmonic numbers (which are of the form 1 + 1 3 + ⋯ + 1 2 n + 1 1+\frac{1}{3}+\cdots+\frac{1}{2n+1} 1 + 3 1 + ⋯ + 2 n + 1 1 for nonnegative integers n n n ) gives us that
∑ 1 ≤ m ≤ z m o d d 1 m ≥ 1 4 log z . (99) \sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}}}\frac{1}{m}\ge\frac{1}{4}\log z. \tag*{(99)} 1 ≤ m ≤ z m odd ∑ m 1 ≥ 4 1 log z . (99)
Combining the lower bound obtained from odd factor pairs with the estimate in (100), and noting that z ≥ 1 z\ge1 z ≥ 1 implies log z ≥ 0 \log z\ge0 log z ≥ 0 , we obtain
∑ 1 ≤ h ≤ z h s q u a r e f r e e 2 ω ( h ) h ≥ 1 4 ( ∑ 1 ≤ m ≤ z m o d d 1 m ) 2 ≥ 1 4 ( 1 4 log z ) 2 = ( log z ) 2 64 . \begin{aligned}
\sum_{\substack{1\le h\le z\\h\ \mathrm{squarefree}}}\frac{2^{\omega(h)}}{h}\ge\frac{1}{4}\left(\sum_{\substack{1\le m\le\sqrt{z}\\m\ \mathrm{odd}}}\frac{1}{m}\right)^2 \\
&\ge\frac{1}{4}\left(\frac{1}{4}\log z\right)^2=\frac{(\log z)^2}{64}.
\end{aligned} 1 ≤ h ≤ z h squarefree ∑ h 2 ω ( h ) ≥ 4 1 1 ≤ m ≤ z m odd ∑ m 1 2 ≥ 4 1 ( 4 1 log z ) 2 = 64 ( log z ) 2 .
Combining this estimate with the lower bound for G ( z ) \mathcal{G}(z) G ( z ) displayed in (98), we obtain
G ( z ) ≥ 1 B 1 , 2 ( 2 A B ∣ a − b ∣ ) ∑ 1 ≤ h ≤ z h s q u a r e f r e e 2 ω ( h ) h ≥ ( log z ) 2 64 B 1 , 2 ( 2 A B ∣ a − b ∣ ) . \begin{aligned}
\mathcal{G}(z)\ge\frac{1}{\mathcal{B}_{1,2}(2AB|a-b|)}\sum_{\substack{1\le h\le z\\h\ \mathrm{squarefree}}}\frac{2^{\omega(h)}}{h} \\
&\ge\frac{(\log z)^2}{64\mathcal{B}_{1,2}(2AB|a-b|)}.
\end{aligned} G ( z ) ≥ B 1 , 2 ( 2 A B ∣ a − b ∣ ) 1 1 ≤ h ≤ z h squarefree ∑ h 2 ω ( h ) ≥ 64 B 1 , 2 ( 2 A B ∣ a − b ∣ ) ( log z ) 2 .
Since z = x 0.005 > 1 z=x^{0.005}>1 z = x 0.005 > 1 , substituting this lower bound for G ( z ) G(z) G ( z ) into the upper bound for S S S shown in (96) gives
S ≤ x gcd ( A , B ) 2 a B G ( z ) + x 0.03 ≤ x gcd ( A , B ) 2 a B 64 B 1 , 2 ( 2 A B ∣ a − b ∣ ) ( log z ) 2 + x 0.03 = 32 x gcd ( A , B ) a B ( log z ) 2 B 1 , 2 ( 2 A B ∣ a − b ∣ ) + x 0.03 . \begin{aligned}
S &\le\frac{x\gcd(A,B)}{2aB G(z)}+x^{0.03}\\
&\le\frac{x\gcd(A,B)}{2aB}\frac{64\mathcal{B}_{1,2}(2AB|a-b|)}{(\log z)^2}+x^{0.03}\\
&=\frac{32x\gcd(A,B)}{aB(\log z)^2}\mathcal{B}_{1,2}(2AB|a-b|)+x^{0.03}.
\end{aligned} S ≤ 2 a B G ( z ) x g cd( A , B ) + x 0.03 ≤ 2 a B x g cd( A , B ) ( log z ) 2 64 B 1 , 2 ( 2 A B ∣ a − b ∣ ) + x 0.03 = a B ( log z ) 2 32 x g cd( A , B ) B 1 , 2 ( 2 A B ∣ a − b ∣ ) + x 0.03 .
Applying Lemma 4 with β = 1 \beta=1 β = 1 , K = 2 K=2 K = 2 , M = 2 M=2 M = 2 , and N = A B ∣ a − b ∣ N=AB|a-b| N = A B ∣ a − b ∣ , and using B 1 , 2 ( 2 ) = 2 \mathcal{B}_{1,2}(2)=2 B 1 , 2 ( 2 ) = 2 , we obtain
B 1 , 2 ( 2 A B ∣ a − b ∣ ) ≤ B 1 , 2 ( 2 ) B 1 , 2 ( A B ∣ a − b ∣ ) = 2 B 1 , 2 ( A B ∣ a − b ∣ ) . (100) \mathcal{B}_{1,2}(2AB|a-b|)\le\mathcal{B}_{1,2}(2)\mathcal{B}_{1,2}(AB|a-b|)=2\mathcal{B}_{1,2}(AB|a-b|). \tag*{(100)} B 1 , 2 ( 2 A B ∣ a − b ∣ ) ≤ B 1 , 2 ( 2 ) B 1 , 2 ( A B ∣ a − b ∣ ) = 2 B 1 , 2 ( A B ∣ a − b ∣ ) . (100)
Using (100) , together with B ≥ b 2 B\ge\frac{b}{2} B ≥ 2 b and log z = log x 200 \log z=\frac{\log x}{200} log z = 200 l o g x , we obtain
S ≤ 64 x gcd ( A , B ) a B ( log z ) 2 B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 ≤ 128 x gcd ( A , B ) a b ( log z ) 2 B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 = 5 120 000 x gcd ( A , B ) a b ( log x ) 2 B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 . \begin{aligned}
S\le\frac{64x\gcd(A,B)}{aB(\log z)^2}\mathcal{B}_{1,2}(AB|a-b|)+x^{0.03} \\
&\le\frac{128x\gcd(A,B)}{ab(\log z)^2}\mathcal{B}_{1,2}(AB|a-b|)+x^{0.03} \\
&=\frac{5\,120\,000x\gcd(A,B)}{ab(\log x)^2}\mathcal{B}_{1,2}(AB|a-b|)+x^{0.03}.
\end{aligned} S ≤ a B ( log z ) 2 64 x g cd( A , B ) B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 ≤ ab ( log z ) 2 128 x g cd( A , B ) B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 = ab ( log x ) 2 5 120 000 x g cd( A , B ) B 1 , 2 ( A B ∣ a − b ∣ ) + x 0.03 .
Since the number of ordered prime pairs satisfying the lemma’s conditions is at most S S S , the required estimate follows with C = 5 120 000 C=5\,120\,000 C = 5 120 000 and x 0 = 8 x_0=8 x 0 = 8 , completing the proof. □
Lemma 9. Let U U U and c c c be positive integers satisfying gcd ( U , c ) = 1 \gcd(U,c)=1 g cd( U , c ) = 1 , and let R ≥ 2 R\ge2 R ≥ 2 be real. Then
∑ 1 ≤ m , n ≤ R m ≠ n gcd ( U m + c , U n + c ) ≪ R 2 log R , \sum_{\substack{1\le m,n\le R\\m\ne n}}\gcd(Um+c,Un+c)\ll R^2\log R, 1 ≤ m , n ≤ R m = n ∑ g cd( U m + c , U n + c ) ≪ R 2 log R , where the sum is over ordered pairs of positive integers, and the implied constant is absolute. In particular, the bound is uniform in U U U , c c c , and R R R .
Proof. For every positive integer m m m , we have
gcd ( U , U m + c ) = gcd ( U , c ) = 1. (101) \gcd(U,Um+c)=\gcd(U,c)=1. \tag*{(101)} g cd( U , U m + c ) = g cd( U , c ) = 1. (101)
Suppose that m m m and n n n are distinct positive integers not exceeding R R R , and that a positive integer h h h divides both U m + c Um+c U m + c and U n + c Un+c U n + c . Since h ∣ U m + c h\mid Um+c h ∣ U m + c , the coprimality relations shown in (101) imply that gcd ( h , U ) = 1 \gcd(h,U)=1 g cd( h , U ) = 1 . Also, subtracting the two integers divisible by h h h gives h ∣ ( ( U m + c ) − ( U n + c ) ) = U ( m − n ) h\mid((Um+c)-(Un+c))=U(m-n) h ∣ (( U m + c ) − ( U n + c )) = U ( m − n ) . Because gcd ( h , U ) = 1 \gcd(h,U)=1 g cd( h , U ) = 1 , it follows that h ∣ m − n h\mid m-n h ∣ m − n . The assumption m ≠ n m\ne n m = n therefore gives 1 ≤ h ≤ ∣ m − n ∣ ≤ R − 1 < R 1\le h\le|m-n|\le R-1<R 1 ≤ h ≤ ∣ m − n ∣ ≤ R − 1 < R . Thus every positive common divisor of U m + c Um+c U m + c and U n + c Un+c U n + c is less than R R R and is relatively prime to U U U .
For each positive integer h < R h<R h < R satisfying gcd ( h , U ) = 1 \gcd(h,U)=1 g cd( h , U ) = 1 , define
N h = ∣ { m ∈ Z : 1 ≤ m ≤ R , h ∣ U m + c } ∣ . N_h=\left|\{m\in\mathbb{Z}:1\le m\le R,\quad h\mid Um+c\}\right|. N h = ∣ { m ∈ Z : 1 ≤ m ≤ R , h ∣ U m + c } ∣ .
We first bound N h ( N h − 1 ) N_h(N_h-1) N h ( N h − 1 ) .
If N h ≥ 1 N_h\ge1 N h ≥ 1 , write the integers counted by N h N_h N h in increasing order as m 1 < m 2 < ⋯ < m N h m_1<m_2<\cdots<m_{N_h} m 1 < m 2 < ⋯ < m N h . For 1 ≤ i < N h 1\le i<N_h 1 ≤ i < N h , we have h ∣ ( ( U m i + 1 + c ) − ( U m i + c ) ) h\mid\bigl((Um_{i+1}+c)-(Um_i+c)\bigr) h ∣ ( ( U m i + 1 + c ) − ( U m i + c ) ) . Since gcd ( h , U ) = 1 \gcd(h,U)=1 g cd( h , U ) = 1 , this implies that h ∣ ( m i + 1 − m i ) h\mid(m_{i+1}-m_i) h ∣ ( m i + 1 − m i ) . Each difference m i + 1 − m i m_{i+1}-m_i m i + 1 − m i is positive, so m i + 1 − m i ≥ h m_{i+1}-m_i\ge h m i + 1 − m i ≥ h . Adding these inequalities yields ( N h − 1 ) h ≤ m N h − m 1 ≤ R − 1 < R (N_h-1)h\le m_{N_h}-m_1\le R-1<R ( N h − 1 ) h ≤ m N h − m 1 ≤ R − 1 < R . This inequality also holds when N h = 1 N_h=1 N h = 1 , since its left-hand side is then zero. Consequently, each of the relations among N h − 1 ≤ R h N_h-1\le\frac{R}{h} N h − 1 ≤ h R and N h ≤ R h + 1 N_h\le\frac{R}{h}+1 N h ≤ h R + 1 holds. Both N h N_h N h and N h − 1 N_h-1 N h − 1 are nonnegative when N h ≥ 1 N_h\ge1 N h ≥ 1 , so we may multiply these bounds to obtain
N h ( N h − 1 ) ≤ ( R h + 1 ) R h = R 2 h 2 + R h . (102) N_h(N_h-1)\le\left(\frac{R}{h}+1\right)\frac{R}{h}=\frac{R^2}{h^2}+\frac{R}{h}. \tag*{(102)} N h ( N h − 1 ) ≤ ( h R + 1 ) h R = h 2 R 2 + h R . (102)
If N h = 0 N_h=0 N h = 0 , the same bound in (102) holds, because its left-hand side vanishes. We have therefore proved that
N h ( N h − 1 ) ≤ R 2 h 2 + R h (103) N_h(N_h-1)\le\frac{R^2}{h^2}+\frac{R}{h} \tag*{(103)} N h ( N h − 1 ) ≤ h 2 R 2 + h R (103)
for every positive integer h < R h<R h < R with gcd ( h , U ) = 1 \gcd(h,U)=1 g cd( h , U ) = 1 .
For distinct positive integers m , n ≤ R m,n\le R m , n ≤ R , the greatest common divisor of U m + c Um+c U m + c and U n + c Un+c U n + c is itself one of their positive common divisors. Since all positive common divisors are less than R R R and relatively prime to U U U , we have
gcd ( U m + c , U n + c ) ≤ ∑ 1 ≤ h < R gcd ( h , U ) = 1 h ∣ U m + c h ∣ U n + c h . \gcd(Um+c,Un+c)\le
\sum_{\substack{1\le h<R\\ \gcd(h,U)=1\\ h\mid Um+c\\ h\mid Un+c}}h. g cd( U m + c , U n + c ) ≤ 1 ≤ h < R g c d ( h , U ) = 1 h ∣ U m + c h ∣ U n + c ∑ h .
Indeed, the sum on the right includes the term h = gcd ( U m + c , U n + c ) h=\gcd(Um+c,Un+c) h = g cd( U m + c , U n + c ) , and every other term is positive.
For each fixed h h h , the number of ordered pairs of distinct integers counted by N h N_h N h is N h ( N h − 1 ) N_h(N_h-1) N h ( N h − 1 ) . Therefore, summing the preceding inequality over m , n m,n m , n and interchanging the finite sums gives
∑ 1 ≤ m , n ≤ R m ≠ n gcd ( U m + c , U n + c ) ≤ ∑ 1 ≤ m , n ≤ R m ≠ n ∑ 1 ≤ h < R gcd ( h , U ) = 1 h ∣ U m + c h ∣ U n + c h = ∑ 1 ≤ h < R gcd ( h , U ) = 1 h ∑ 1 ≤ m , n ≤ R m ≠ n h ∣ U m + c h ∣ U n + c 1 = ∑ 1 ≤ h < R gcd ( h , U ) = 1 h N h ( N h − 1 ) . (104) \begin{aligned}
\sum_{\substack{1\le m,n\le R\\m\ne n}}\gcd(Um+c,Un+c)
\le
\sum_{\substack{1\le m,n\le R\\m\ne n}}
\sum_{\substack{1\le h<R\\\gcd(h,U)=1\\h\mid Um+c\\h\mid Un+c}}h \\
&=
\sum_{\substack{1\le h<R\\\gcd(h,U)=1}}h
\sum_{\substack{1\le m,n\le R\\m\ne n\\h\mid Um+c\\h\mid Un+c}}1 \\
&= \sum_{\substack{1\le h<R\\ \gcd(h,U)=1}} hN_h(N_h-1). \tag*{(104)}
\end{aligned} 1 ≤ m , n ≤ R m = n ∑ g cd( U m + c , U n + c ) ≤ 1 ≤ m , n ≤ R m = n ∑ 1 ≤ h < R g c d ( h , U ) = 1 h ∣ U m + c h ∣ U n + c ∑ h = 1 ≤ h < R g c d ( h , U ) = 1 ∑ h 1 ≤ m , n ≤ R m = n h ∣ U m + c h ∣ U n + c ∑ 1 = 1 ≤ h < R g c d ( h , U ) = 1 ∑ h N h ( N h − 1 ) . (104)
Applying (103) , and then including the nonnegative terms corresponding to integers h h h with gcd ( h , U ) > 1 \gcd(h,U)>1 g cd( h , U ) > 1 , we obtain
∑ 1 ≤ m , n ≤ R m ≠ n gcd ( U m + c , U n + c ) ≤ ∑ 1 ≤ h < R gcd ( h , U ) = 1 h ( R 2 h 2 + R h ) . ≤ ∑ 1 ≤ h < R h ( R 2 h 2 + R h ) = R 2 ∑ 1 ≤ h < R 1 h + R ∑ 1 ≤ h < R 1. \begin{aligned}
\sum_{\substack{1\le m,n\le R\\m\ne n}}\gcd(Um+c,Un+c)
\le
\sum_{\substack{1\le h<R\\\gcd(h,U)=1}}h\left(\frac{R^2}{h^2}+\frac{R}{h}\right). \\
&\le\sum_{1\le h<R}h\left(\frac{R^2}{h^2}+\frac{R}{h}\right) \\
&=R^2\sum_{1\le h<R}\frac{1}{h}+R\sum_{1\le h<R}1.
\end{aligned} 1 ≤ m , n ≤ R m = n ∑ g cd( U m + c , U n + c ) ≤ 1 ≤ h < R g c d ( h , U ) = 1 ∑ h ( h 2 R 2 + h R ) . ≤ 1 ≤ h < R ∑ h ( h 2 R 2 + h R ) = R 2 1 ≤ h < R ∑ h 1 + R 1 ≤ h < R ∑ 1.
Classical bounds for harmonic numbers give us that ∑ 1 ≤ h < R 1 h ≤ 1 + log R \sum_{1\le h<R}\frac{1}{h}\le1+\log R ∑ 1 ≤ h < R h 1 ≤ 1 + log R . Also, we see that ∑ 1 ≤ h < R 1 ≤ ⌊ R ⌋ ≤ R \sum_{1\le h<R}1\le\lfloor R\rfloor\le R ∑ 1 ≤ h < R 1 ≤ ⌊ R ⌋ ≤ R . Combining these estimates gives
∑ 1 ≤ m , n ≤ R m ≠ n gcd ( U m + c , U n + c ) ≤ R 2 ( 1 + log R ) + R 2 = R 2 ( 2 + log R ) . (105) \sum_{\substack{1\le m,n\le R\\m\ne n}}\gcd(Um+c,Un+c)
\le R^2(1+\log R)+R^2=R^2(2+\log R). \tag*{(105)} 1 ≤ m , n ≤ R m = n ∑ g cd( U m + c , U n + c ) ≤ R 2 ( 1 + log R ) + R 2 = R 2 ( 2 + log R ) . (105)
Finally, since R ≥ 2 R\ge2 R ≥ 2 , we find that 2 + log R ≤ ( 1 + 2 log 2 ) log R 2+\log R\le\left(1+\frac{2}{\log2}\right)\log R 2 + log R ≤ ( 1 + l o g 2 2 ) log R . Thus, from (105), we find that
∑ 1 ≤ m , n ≤ R m ≠ n gcd ( U m + c , U n + c ) ≤ ( 1 + 2 log 2 ) R 2 log R . \sum_{\substack{1\le m,n\le R\\m\ne n}}\gcd(Um+c,Un+c)
\le\left(1+\frac{2}{\log2}\right)R^2\log R. 1 ≤ m , n ≤ R m = n ∑ g cd( U m + c , U n + c ) ≤ ( 1 + log 2 2 ) R 2 log R .
The constant on the right is independent of U U U , c c c , and R R R , as required. □
Theorem 1. There exist absolute constants c 0 > 0 c_0>0 c 0 > 0 and x 0 ≥ 1 x_0\ge1 x 0 ≥ 1 such that V ( x ) ≥ c 0 x V(x)\ge c_0x V ( x ) ≥ c 0 x for every real x ≥ x 0 x\ge x_0 x ≥ x 0 . Consequently, the relation
lim inf x → ∞ V ( x ) x > 0 (106) \liminf_{x\to\infty}\frac{V(x)}{x}>0 \tag*{(106)} x → ∞ lim inf x V ( x ) > 0 (106) holds, and, in particular, the relation V ( x ) ≠ o ( x ) V(x)\ne o(x) V ( x ) = o ( x ) holds.
Proof. Let x x x be a sufficiently large real number, and put
Y = x 1 1000 . (107) Y=x^{\frac{1}{1000}}. \tag*{(107)} Y = x 1000 1 . (107)
We take x x x large enough that Y ≥ 2 Y\ge2 Y ≥ 2 . Every further lower bound on x x x imposed below will depend only on fixed numerical constants and on the uniform constants in the preceding lemmas.
Define
E = { e ∈ Z : Y < e ≤ Y 2 , e ≡ 2 ( m o d 4 ) } , \mathcal{E}=\{e\in\mathbb{Z}:Y<e\le Y^2,\ e\equiv2\pmod{4}\}, E = { e ∈ Z : Y < e ≤ Y 2 , e ≡ 2 ( mod 4 )} ,
and define the two sets of primes
T = { p : Y 10 < p ≤ Y 11 } , R = { p : Y 40 < p ≤ Y 41 } . \mathcal{T}=\{p:Y^{10}<p\le Y^{11}\},\qquad\mathcal{R}=\{p:Y^{40}<p\le Y^{41}\}. T = { p : Y 10 < p ≤ Y 11 } , R = { p : Y 40 < p ≤ Y 41 } .
Set
C = { e t : e ∈ E , t ∈ T } , A = { c r : c ∈ C , r ∈ R } , \mathcal{C}=\{et:e\in\mathcal{E},\ t\in\mathcal{T}\},\qquad\mathcal{A}=\{cr:c\in\mathcal{C},\ r\in\mathcal{R}\}, C = { e t : e ∈ E , t ∈ T } , A = { cr : c ∈ C , r ∈ R } ,
and
N x = { a p : a ∈ A , p prime , x 2 a < p ≤ x a } . (108) \mathcal{N}_x=\left\{ap:a\in\mathcal{A},\ p\text{ prime},\ \frac{x}{2a}<p\leq\frac{x}{a}\right\}. \tag*{(108)} N x = { a p : a ∈ A , p prime , 2 a x < p ≤ a x } . (108)
These definitions imply
Y 11 < c ≤ Y 13 ( c ∈ C ) , Y 51 < a ≤ Y 54 ( a ∈ A ) . (109) Y^{11}<c\leq Y^{13}\quad(c\in\mathcal{C}),\qquad Y^{51}<a\leq Y^{54}\quad(a\in\mathcal{A}). \tag*{(109)} Y 11 < c ≤ Y 13 ( c ∈ C ) , Y 51 < a ≤ Y 54 ( a ∈ A ) . (109)
In particular, every prime divisor of e ∈ E e\in\mathcal{E} e ∈ E is smaller than every t ∈ T t\in\mathcal{T} t ∈ T , and every such t t t is smaller than every r ∈ R r\in\mathcal{R} r ∈ R . Moreover, for a p ∈ N x ap\in\mathcal{N}_x a p ∈ N x , we have that
p > x 2 a ≥ 1 2 Y 946 > Y 41 . p>\frac{x}{2a}\geq\frac{1}{2}Y^{946}>Y^{41}. p > 2 a x ≥ 2 1 Y 946 > Y 41 .
Thus, in the factorization a p = e t r p ap=etrp a p = e t r p , the primes t t t , r r r , p p p are, in increasing order, the three largest prime divisors, and each occurs with exponent one. The fundamental theorem of arithmetic therefore implies that every factorization among
c = e t , (110) c=et, \tag*{(110)} c = e t , (110)
a = c r = e t r , and (111) a=cr=etr,\qquad\text{and} \tag*{(111)} a = cr = e t r , and (111)
n = a p = e t r p (112) n=ap=etrp \tag*{(112)} n = a p = e t r p (112)
in the sets above is unique. By the uniqueness asserted for the factorization a = c r a=cr a = cr in (111) , we have
c r = d s ⟺ c = d and r = s ( c , d ∈ C , r , s ∈ R ) . (113) cr=ds\quad\Longleftrightarrow\quad c=d\text{ and }r=s\quad(c,d\in\mathcal{C},\ r,s\in\mathcal{R}). \tag*{(113)} cr = d s ⟺ c = d and r = s ( c , d ∈ C , r , s ∈ R ) . (113)
Also,
N x ⊆ ( x 2 , x ] ∩ Z . (114) \mathcal{N}_x\subseteq\left(\frac{x}{2},x\right]\cap\mathbb{Z}. \tag*{(114)} N x ⊆ ( 2 x , x ] ∩ Z . (114)
Since e ≡ 2 ( m o d 4 ) e\equiv2\pmod{4} e ≡ 2 ( mod 4 ) and t , r t,r t , r are odd, we have
2 ∥ c ( c ∈ C ) , 2 ∥ a ( a ∈ A ) . (115) 2\parallel c\quad(c\in\mathcal{C}),\qquad2\parallel a\quad(a\in\mathcal{A}). \tag*{(115)} 2 ∥ c ( c ∈ C ) , 2 ∥ a ( a ∈ A ) . (115)
By the prime number theorem, the asymptotic equivalence π ( v ) − π ( v 2 ) ∼ v 2 log v \pi(v)-\pi\left(\frac{v}{2}\right)\sim\frac{v}{2\log v} π ( v ) − π ( 2 v ) ∼ 2 l o g v v holds. So, there exists an absolute v 0 v_0 v 0 such that
π ( v ) − π ( v 2 ) ≥ v 4 log v (116) \pi(v)-\pi\left(\frac{v}{2}\right)\geq\frac{v}{4\log v} \tag*{(116)} π ( v ) − π ( 2 v ) ≥ 4 log v v (116)
for all v ≥ v 0 v\geq v_0 v ≥ v 0 . Now, for every a ∈ A a\in\mathcal{A} a ∈ A , we have x 0.946 ≤ x a ≤ x x^{0.946}\leq\frac{x}{a}\leq x x 0.946 ≤ a x ≤ x . Consequently, for all sufficiently large x x x , the inequality in (116) applies simultaneously to each v = x a v=\frac{x}{a} v = a x , giving
π ( x a ) − π ( x 2 a ) ≥ x 4 a log ( x a ) ≥ x 4 a log x . (117) \pi\left(\frac{x}{a}\right)-\pi\left(\frac{x}{2a}\right)\geq\frac{x}{4a\log\left(\frac{x}{a}\right)}\geq\frac{x}{4a\log x}. \tag*{(117)} π ( a x ) − π ( 2 a x ) ≥ 4 a log ( a x ) x ≥ 4 a log x x . (117)
For v ≥ 1 v \ge1 v ≥ 1 , the number of positive integers e ≤ v e \le v e ≤ v with e ≡ 2 ( m o d 4 ) e \equiv2 \pmod{4} e ≡ 2 ( mod 4 ) is ⌊ v + 2 4 ⌋ = v 4 + O ( 1 ) \left\lfloor\frac{v+2}{4} \right\rfloor= \frac{v}{4} + O(1) ⌊ 4 v + 2 ⌋ = 4 v + O ( 1 ) . Partial summation therefore gives
∑ e ∈ E 1 e = ⌊ Y 2 + 2 4 ⌋ Y 2 − ⌊ Y + 2 4 ⌋ Y + ∫ Y Y 2 ⌊ v + 2 4 ⌋ v 2 d v = 1 4 log Y + O ( Y − 1 ) . (118) \sum_{e\in\mathcal{E}} \frac{1}{e}
= \frac{\left\lfloor\frac{Y^{2}+2}{4} \right\rfloor}{Y^{2}}
- \frac{\left\lfloor\frac{Y+2}{4} \right\rfloor}{Y}
+ \int_Y^{Y^2} \frac{\left\lfloor\frac{v+2}{4} \right\rfloor}{v^2}\,dv
= \frac{1}{4}\log Y + O(Y^{-1}). \tag*{(118)} e ∈ E ∑ e 1 = Y 2 ⌊ 4 Y 2 + 2 ⌋ − Y ⌊ 4 Y + 2 ⌋ + ∫ Y Y 2 v 2 ⌊ 4 v + 2 ⌋ d v = 4 1 log Y + O ( Y − 1 ) . (118)
For either ( η , ζ ) = ( 10 , 11 ) (\eta,\zeta)=(10,11) ( η , ζ ) = ( 10 , 11 ) or ( η , ζ ) = ( 40 , 41 ) (\eta,\zeta)=(40,41) ( η , ζ ) = ( 40 , 41 ) , partial summation also gives
∑ Y η < p ≤ Y ζ 1 p = π ( Y ζ ) Y ζ − π ( Y η ) Y η + ∫ Y η Y ζ π ( v ) v 2 d v . \sum_{Y^\eta<p\le Y^\zeta}\frac{1}{p}
= \frac{\pi(Y^\zeta)}{Y^\zeta}
- \frac{\pi(Y^\eta)}{Y^\eta}
+ \int_{Y^\eta}^{Y^\zeta}\frac{\pi(v)}{v^2}\,dv. Y η < p ≤ Y ζ ∑ p 1 = Y ζ π ( Y ζ ) − Y η π ( Y η ) + ∫ Y η Y ζ v 2 π ( v ) d v .
The two endpoint terms tend to zero by the prime number theorem. The error in replacing the integral by ∫ Y η Y ζ d v v log v \int_{Y^\eta}^{Y^\zeta}\frac{dv}{v\log v} ∫ Y η Y ζ v l o g v d v is at most
( sup v ≥ Y η ∣ π ( v ) log v v − 1 ∣ ) ∫ Y η Y ζ d v v log v = o ( 1 ) , \left(\sup_{v\ge Y^\eta}\left|\frac{\pi(v)\log v}{v}-1\right|\right)
\int_{Y^\eta}^{Y^\zeta}\frac{dv}{v\log v}
= o(1), ( v ≥ Y η sup v π ( v ) log v − 1 ) ∫ Y η Y ζ v log v d v = o ( 1 ) ,
since the supremum tends to zero and the integral equals log ( ζ η ) \log\left(\frac{\zeta}{\eta}\right) log ( η ζ ) . It follows that
∑ t ∈ T 1 t = log ( 11 10 ) + o ( 1 ) , ∑ r ∈ R 1 r = log ( 41 40 ) + o ( 1 ) . (119) \sum_{t\in\mathcal{T}}\frac{1}{t}
= \log\left(\frac{11}{10}\right)+o(1),
\qquad
\sum_{r\in\mathcal{R}}\frac{1}{r}
= \log\left(\frac{41}{40}\right)+o(1). \tag*{(119)} t ∈ T ∑ t 1 = log ( 10 11 ) + o ( 1 ) , r ∈ R ∑ r 1 = log ( 40 41 ) + o ( 1 ) . (119)
The uniqueness asserted for the factorization n = a p n=ap n = a p in (112) gives us that
∣ N x ∣ = ∑ a ∈ A ( π ( x a ) − π ( x 2 a ) ) . |\mathcal{N}_x|
= \sum_{a\in\mathcal{A}}
\left(\pi\left(\frac{x}{a}\right)-\pi\left(\frac{x}{2a}\right)\right). ∣ N x ∣ = a ∈ A ∑ ( π ( a x ) − π ( 2 a x ) ) .
and the uniqueness asserted for the factorization a = e t r a=etr a = e t r in (111) gives us that
∑ a ∈ A 1 a = ( ∑ e ∈ E 1 e ) ( ∑ t ∈ T 1 t ) ( ∑ r ∈ R 1 r ) . \sum_{a\in\mathcal{A}}\frac{1}{a}
= \left(\sum_{e\in\mathcal{E}}\frac{1}{e}\right)
\left(\sum_{t\in\mathcal{T}}\frac{1}{t}\right)
\left(\sum_{r\in\mathcal{R}}\frac{1}{r}\right). a ∈ A ∑ a 1 = ( e ∈ E ∑ e 1 ) ( t ∈ T ∑ t 1 ) ( r ∈ R ∑ r 1 ) .
Combining (117), (118), and (119), and using log Y = log x 1000 \log Y=\frac{\log x}{1000} log Y = 1000 l o g x , gives
∣ N x ∣ ≫ x log Y log x ≫ x . (120) |\mathcal{N}_x| \gg\frac{x\log Y}{\log x}\gg x. \tag*{(120)} ∣ N x ∣ ≫ log x x log Y ≫ x . (120)
For distinct a , b ∈ A a,b\in\mathcal{A} a , b ∈ A , define G ( a , b ) = gcd ( w ( a ) , w ( b ) , ∣ a − b ∣ ) G(a,b)=\gcd(w(a),w(b),|a-b|) G ( a , b ) = g cd( w ( a ) , w ( b ) , ∣ a − b ∣ ) and D ( a , b ) = w ( a ) w ( b ) ∣ a − b ∣ D(a,b)=w(a)w(b)|a-b| D ( a , b ) = w ( a ) w ( b ) ∣ a − b ∣ . Observe that both G ( a , b ) G(a,b) G ( a , b ) and D ( a , b ) D(a,b) D ( a , b ) are positive integers.
Fix distinct c , d ∈ C c,d\in\mathcal{C} c , d ∈ C , and let U = w ( c ) U=w(c) U = w ( c ) and W = w ( d ) W=w(d) W = w ( d ) . Since r > c r>c r > c and s > d s>d s > d whenever r , s ∈ R r,s\in\mathcal{R} r , s ∈ R , Lemma 2 gives that w ( c r ) = U r + c w(cr)=Ur+c w ( cr ) = U r + c and that w ( d s ) = W s + d w(ds)=Ws+d w ( d s ) = W s + d . By (113), the relation c r ≠ d s cr\ne ds cr = d s holds for all such r , s r,s r , s .
Suppose that h ∣ G ( c r , d s ) h\mid G(cr,ds) h ∣ G ( cr , d s ) . Applying Lemma 1 with n = c r n=cr n = cr and n = d s n=ds n = d s , we obtain gcd ( c r , w ( c r ) ) = gcd ( d s , w ( d s ) ) = 1 \gcd(cr,w(cr))=\gcd(ds,w(ds))=1 g cd( cr , w ( cr )) = g cd( d s , w ( d s )) = 1 . Since h ∣ w ( c r ) h\mid w(cr) h ∣ w ( cr ) and h ∣ w ( d s ) h\mid w(ds) h ∣ w ( d s ) , it follows that gcd ( h , c r ) = gcd ( h , d s ) = 1 \gcd(h,cr)=\gcd(h,ds)=1 g cd( h , cr ) = g cd( h , d s ) = 1 . We thus find that h h h and c d r s cdrs c d r s are relatively prime. If a prime were to divide both h h h and U U U , then the relation h ∣ ( U r + c ) h\mid(Ur+c) h ∣ ( U r + c ) would force that same prime to divide c c c , contrary to gcd ( h , c ) = 1 \gcd(h,c)=1 g cd( h , c ) = 1 . So, we can deduce that h h h and U U U are coprime. The corresponding argument gives us that gcd ( h , W ) = 1 \gcd(h,W)=1 g cd( h , W ) = 1 , so
gcd ( h , c d U W ) = 1. (121) \gcd(h,cdUW)=1. \tag*{(121)} g cd( h , c d U W ) = 1. (121)
The congruences
U r ≡ − c ( m o d h ) , W s ≡ − d ( m o d h ) Ur\equiv-c \pmod{h},\qquad Ws\equiv-d \pmod{h} U r ≡ − c ( mod h ) , W s ≡ − d ( mod h )
therefore each specify one reduced residue class modulo h h h . Here the residue classes are reduced because both c c c and d d d are relatively prime to h h h . Moreover, h ∣ c r − d s h\mid cr-ds h ∣ cr − d s . Multiplying c r ≡ d s ( m o d h ) cr\equiv ds\pmod{h} cr ≡ d s ( mod h ) by U W UW U W and substituting the preceding two congruences gives
− c 2 W ≡ − d 2 U ( m o d h ) . -c^{2}W\equiv-d^{2}U\pmod{h}. − c 2 W ≡ − d 2 U ( mod h ) .
As a consequence, each of the relations among
h ∣ H ( c , d ) and H ( c , d ) = c 2 w ( d ) − d 2 w ( c ) (122) h\mid H(c,d)\qquad\text{and}\qquad H(c,d)=c^{2}w(d)-d^{2}w(c) \tag*{(122)} h ∣ H ( c , d ) and H ( c , d ) = c 2 w ( d ) − d 2 w ( c ) (122)
holds.
The integer H ( c , d ) H(c,d) H ( c , d ) is nonzero. Indeed, if it were zero, then c 2 w ( d ) = d 2 w ( c ) c^{2}w(d)=d^{2}w(c) c 2 w ( d ) = d 2 w ( c ) . Applying Lemma 1 with n = c n=c n = c and n = d n=d n = d , we obtain gcd ( c , w ( c ) ) = gcd ( d , w ( d ) ) = 1 \gcd(c,w(c))=\gcd(d,w(d))=1 g cd( c , w ( c )) = g cd( d , w ( d )) = 1 . Consequently, the equalities among
gcd ( c 2 , w ( c ) ) = gcd ( d 2 , w ( d ) ) = 1 (123) \gcd(c^{2},w(c))=\gcd(d^{2},w(d))=1 \tag*{(123)} g cd( c 2 , w ( c )) = g cd( d 2 , w ( d )) = 1 (123)
hold, and from (123) , we find that the equality c 2 w ( d ) = d 2 w ( c ) c^{2}w(d)=d^{2}w(c) c 2 w ( d ) = d 2 w ( c ) would imply that c 2 ∣ d 2 c^{2}\mid d^{2} c 2 ∣ d 2 and that d 2 ∣ c 2 d^{2}\mid c^{2} d 2 ∣ c 2 . Hence c 2 = d 2 c^{2}=d^{2} c 2 = d 2 , and positivity would imply c = d c=d c = d , contrary to our choice of c , d c,d c , d . Also, applying the upper bound in Lemma 3 with n = c n=c n = c and n = d n=d n = d , and using c , d ≤ Y 1 / 3 c,d\le Y^{1/3} c , d ≤ Y 1/3 , we obtain
0 < ∣ H ( c , d ) ∣ ≤ c 2 w ( d ) + d 2 w ( c ) ≤ 26 log 2 Y Y 39 log Y < Y 39.5 (124) \begin{aligned}
0<|H(c,d)|&\le c^{2}w(d)+d^{2}w(c)\\
&\le\frac{26}{\log^{2}Y}Y^{39}\log Y<Y^{39.5} \tag*{(124)}
\end{aligned} 0 < ∣ H ( c , d ) ∣ ≤ c 2 w ( d ) + d 2 w ( c ) ≤ log 2 Y 26 Y 39 log Y < Y 39.5 (124)
for all sufficiently large Y Y Y , uniformly in c , d c,d c , d .
The sum over the positive divisors of G ( c r , d s ) G(cr,ds) G ( cr , d s ) includes the term corresponding to h = G ( c r , d s ) h=G(cr,ds) h = G ( cr , d s ) , so
G ( c r , d s ) 3 2 ≤ ∑ h ∣ G ( c r , d s ) h 3 2 . G(cr,ds)^{\frac{3}{2}}\le\sum_{h\mid G(cr,ds)}h^{\frac{3}{2}}. G ( cr , d s ) 2 3 ≤ h ∣ G ( cr , d s ) ∑ h 2 3 .
Using (121) and (122) , interchanging finite sums, and then dropping the condition h ∣ c r − d s h\mid cr-ds h ∣ cr − d s , we obtain
∑ r , s ∈ R G ( c r , d s ) 3 2 r s ≤ ∑ h ∣ ∣ H ( c , d ) ∣ gcd ( h , c d U W ) = 1 h 3 2 ∑ r , s ∈ R h ∣ U r + c h ∣ W s + d h ∣ c r − d s 1 r s . ≤ ∑ h ∣ ∣ H ( c , d ) ∣ gcd ( h , c d U W ) = 1 h 3 2 ( ∑ r ∈ R h ∣ U r + c 1 r ) ( ∑ s ∈ R h ∣ W s + d 1 s ) . \begin{aligned}
\sum_{r,s\in\mathcal{R}}\frac{G(cr,ds)^{\frac{3}{2}}}{rs}
\le
\sum_{\substack{h\mid|H(c,d)|\\ \gcd(h,cdUW)=1}}h^{\frac{3}{2}}
\sum_{\substack{r,s\in\mathcal{R}\\ h\mid Ur+c\\ h\mid Ws+d\\ h\mid cr-ds}}\frac{1}{rs}. \\
&\le\sum_{\substack{h\mid\lvert H(c,d)\rvert\\ \gcd(h,cdUW)=1}} h^{\frac{3}{2}}\left(\sum_{\substack{r\in R\\ h\mid Ur+c}}\frac{1}{r}\right)\left(\sum_{\substack{s\in R\\ h\mid Ws+d}}\frac{1}{s}\right).
\end{aligned} r , s ∈ R ∑ r s G ( cr , d s ) 2 3 ≤ h ∣ ∣ H ( c , d ) ∣ g c d ( h , c d U W ) = 1 ∑ h 2 3 r , s ∈ R h ∣ U r + c h ∣ W s + d h ∣ cr − d s ∑ r s 1 . ≤ h ∣ ∣ H ( c , d )∣ g c d ( h , c d U W ) = 1 ∑ h 2 3 r ∈ R h ∣ U r + c ∑ r 1 s ∈ R h ∣ W s + d ∑ s 1 .
Each inner sum is over one reduced residue class modulo h h h . We then choose its representative to be a positive integer, as required in Lemma 5. By (124), Lemma 5 applies with α = 40 \alpha=40 α = 40 , δ = 41 \delta=41 δ = 41 , and γ = 39.5 \gamma=39.5 γ = 39.5 . Its constant is independent of c , d , U , W , h c,d,U,W,h c , d , U , W , h . After applying the Lemma 5, we may include the remaining divisors of ∣ H ( c , d ) ∣ \lvert H(c,d)\rvert ∣ H ( c , d )∣ , since all terms are nonnegative. This gives
∑ r , s ∈ R G ( c r , d s ) 3 2 r s ≪ ∑ h ∣ ∣ H ( c , d ) ∣ h 3 2 φ ( h ) 2 . (125) \sum_{r,s\in R}\frac{G(cr,ds)^{\frac{3}{2}}}{rs}\ll\sum_{h\mid\lvert H(c,d)\rvert}\frac{h^{\frac{3}{2}}}{\varphi(h)^2}. \tag*{(125)} r , s ∈ R ∑ r s G ( cr , d s ) 2 3 ≪ h ∣ ∣ H ( c , d )∣ ∑ φ ( h ) 2 h 2 3 . (125)
For every positive integer N N N , Euler’s formula for φ \varphi φ and the fundamental theorem of arithmetic give
∑ h ∣ N h 3 2 φ ( h ) 2 = ∏ p ν ∥ N ( 1 + 1 ( 1 − p − 1 ) 2 ∑ j = 1 ν p − j 2 ) ≤ ∏ p ∣ N ( 1 + p − 1 2 ( 1 − p − 1 ) 2 ( 1 − p − 1 2 ) ) . (126) \begin{aligned}
\sum_{h\mid N}\frac{h^{\frac{3}{2}}}{\varphi(h)^2}
=\prod_{p^\nu\parallel N}\left(1+\frac{1}{(1-p^{-1})^2}\sum_{j=1}^{\nu}p^{-\frac{j}{2}}\right) \\
&\le\prod_{p\mid N}\left(1+\frac{p^{-\frac{1}{2}}}{(1-p^{-1})^2(1-p^{-\frac{1}{2}})}\right). \tag*{(126)}
\end{aligned} h ∣ N ∑ φ ( h ) 2 h 2 3 = p ν ∥ N ∏ ( 1 + ( 1 − p − 1 ) 2 1 j = 1 ∑ ν p − 2 j ) ≤ p ∣ N ∏ ( 1 + ( 1 − p − 1 ) 2 ( 1 − p − 2 1 ) p − 2 1 ) . (126)
For every p ≥ 2 p\ge2 p ≥ 2 , the relations among 1 ( 1 − p − 1 ) 2 ( 1 − p − 1 2 ) ≤ 4 1 − 2 − 1 2 = 8 + 4 2 < 14 \frac{1}{(1-p^{-1})^2(1-p^{-\frac{1}{2}})}\le\frac{4}{1-2^{-\frac{1}{2}}}=8+4\sqrt{2}<14 ( 1 − p − 1 ) 2 ( 1 − p − 2 1 ) 1 ≤ 1 − 2 − 2 1 4 = 8 + 4 2 < 14 hold. This and (126) together give us that
∑ h ∣ N h 3 2 φ ( h ) 2 ≤ B 1 2 , 14 ( N ) (127) \sum_{h\mid N}\frac{h^{\frac{3}{2}}}{\varphi(h)^2}\le B_{\frac{1}{2},14}(N) \tag*{(127)} h ∣ N ∑ φ ( h ) 2 h 2 3 ≤ B 2 1 , 14 ( N ) (127)
for N ≥ 2 N\ge2 N ≥ 2 , and we may check that (127) also holds for N = 1 N=1 N = 1 (in which case both sides of (127) equal 1). We then see that (125) and (127) together imply
∑ r , s ∈ R G ( c r , d s ) 3 2 r s ≪ B 1 2 , 14 ( ∣ H ( c , d ) ∣ ) . (128) \sum_{r,s\in R}\frac{G(cr,ds)^{\frac{3}{2}}}{rs}\ll B_{\frac{1}{2},14}(\lvert H(c,d)\rvert). \tag*{(128)} r , s ∈ R ∑ r s G ( cr , d s ) 2 3 ≪ B 2 1 , 14 (∣ H ( c , d )∣) . (128)
Our goal, at this point, is to estimate a sum involving the right-hand side of (128) for distinct c , d ∈ C c,d\in C c , d ∈ C . As an intermediary step, we begin by bounding an associated sum over elements t ∈ T t\in T t ∈ T such that e t ≠ f u et\ne fu e t = f u . Fix e , f ∈ E e,f\in E e , f ∈ E and u ∈ T u\in T u ∈ T , put d = f u d=fu d = f u , and define the polynomial
P ( T ) = e 2 w ( d ) T 2 − d 2 w ( e ) T − d 2 e . P(T)=e^{2w(d)}T^2-d^{2w(e)}T-d^2e. P ( T ) = e 2 w ( d ) T 2 − d 2 w ( e ) T − d 2 e .
Its leading coefficient is positive, so P P P is nonzero and has degree two. For t ∈ T t\in T t ∈ T , we have t > e t>e t > e , and therefore w ( e t ) = t w ( e ) + e w(et)=tw(e)+e w ( e t ) = tw ( e ) + e by Lemma 2. It follows that
P ( t ) = H ( e t , d ) . P(t)=H(et,d). P ( t ) = H ( e t , d ) .
The content of P P P is
cont ( P ) = gcd ( e 2 w ( d ) , d 2 w ( e ) , d 2 e ) = gcd ( e 2 w ( d ) , d 2 ) = gcd ( e 2 , d 2 ) = gcd ( e , d ) 2 = gcd ( e , f ) 2 . \operatorname{cont}(P)=\gcd(e^{2}w(d),d^{2}w(e),d^{2}e)
=\gcd(e^{2}w(d),d^{2})
=\gcd(e^{2},d^{2})
=\gcd(e,d)^{2}=\gcd(e,f)^{2}. cont ( P ) = g cd( e 2 w ( d ) , d 2 w ( e ) , d 2 e ) = g cd( e 2 w ( d ) , d 2 ) = g cd( e 2 , d 2 ) = g cd( e , d ) 2 = g cd( e , f ) 2 .
By Lemma 1, applied with n = e n=e n = e and n = d n=d n = d , we have gcd ( w ( e ) , e ) = gcd ( w ( d ) , d ) = 1 \gcd(w(e),e)=\gcd(w(d),d)=1 g cd( w ( e ) , e ) = g cd( w ( d ) , d ) = 1 . These identities justify the second and third equalities, respectively. The last equality uses the fact that u u u is prime and u > e u>e u > e , so that gcd ( e , u ) = 1 \gcd(e,u)=1 g cd( e , u ) = 1 .
For each real v v v with Y 10 < v ≤ Y 11 Y^{10}<v\leq Y^{11} Y 10 < v ≤ Y 11 , we apply the upper bound in Lemma 3 with n = d n=d n = d and n = e n=e n = e . Using e ≤ Y 2 e\leq Y^{2} e ≤ Y 2 , d ≤ Y 13 d\leq Y^{13} d ≤ Y 13 , and v ≤ Y 11 v\leq Y^{11} v ≤ Y 11 , we obtain
∣ P ( v ) ∣ ≤ e 2 w ( d ) v 2 + d 2 w ( e ) v + d 2 e ≤ 15 log 2 2 Y 39 log Y + Y 28 ≤ Y 40 . \lvert P(v)\rvert\leq e^{2}w(d)v^{2}+d^{2}w(e)v+d^{2}e
\leq\frac{15}{\log^{2}2}Y^{39}\log Y+Y^{28}\leq Y^{40}. ∣ P ( v )∣ ≤ e 2 w ( d ) v 2 + d 2 w ( e ) v + d 2 e ≤ log 2 2 15 Y 39 log Y + Y 28 ≤ Y 40 .
for all sufficiently large Y Y Y , uniformly in e e e , f f f , u u u . Thus the polynomial averaging estimate (21) applies with
α = 10 , δ = 11 , β = 1 2 , K = 14 , M = 40 , \alpha=10,\qquad\delta=11,\qquad\beta=\frac{1}{2},\qquad K=14,\qquad M=40, α = 10 , δ = 11 , β = 2 1 , K = 14 , M = 40 ,
and degree bound two. For t ∈ T t\in\mathcal{T} t ∈ T , the preceding nonvanishing argument shows that P ( t ) = 0 P(t)=0 P ( t ) = 0 if and only if e t = f u et=fu e t = f u . This gives us that
∑ t ∈ T e t ≠ f u B 1 2 , 14 ( ∣ H ( e t , f u ) ∣ ) t ≪ B 1 2 , 14 ( gcd ( e , f ) 2 ) = B 1 2 , 14 ( gcd ( e , f ) ) . (129) \sum_{\substack{t\in\mathcal{T}\\ et\ne fu}}\frac{\mathcal{B}_{\frac{1}{2},14}(\lvert H(et,fu)\rvert)}{t}
\ll\mathcal{B}_{\frac{1}{2},14}(\gcd(e,f)^{2})
=\mathcal{B}_{\frac{1}{2},14}(\gcd(e,f)). \tag*{(129)} t ∈ T e t = f u ∑ t B 2 1 , 14 (∣ H ( e t , f u )∣) ≪ B 2 1 , 14 ( g cd( e , f ) 2 ) = B 2 1 , 14 ( g cd( e , f )) . (129)
The last equality holds because an integer and its square have exactly the same prime divisors.
The implied constant in (129) is independent of e e e , f f f , and u u u . Indeed, the parameters in (21) have the fixed values specified above, and the bound ∣ P ( v ) ∣ ≤ Y 40 \lvert P(v)\rvert\leq Y^{40} ∣ P ( v )∣ ≤ Y 40 holds uniformly for all admissible choices of these factors. Thus (129) holds simultaneously for all such choices once Y Y Y exceeds one absolute threshold. We may therefore multiply by 1 e f u \frac{1}{efu} e f u 1 and sum over e , f ∈ E e,f\in\mathcal{E} e , f ∈ E and u ∈ T u\in\mathcal{T} u ∈ T , with the dependence on e e e and f f f retained in the explicit factor B 1 2 , 14 ( gcd ( e , f ) ) \mathcal{B}_{\frac{1}{2},14}(\gcd(e,f)) B 2 1 , 14 ( g cd( e , f )) .
By the uniqueness asserted for the factorization in (110) , each c ∈ C c\in\mathcal{C} c ∈ C determines exactly one pair ( e , t ) ∈ E × T (e,t)\in\mathcal{E}\times\mathcal{T} ( e , t ) ∈ E × T satisfying c = e t c=et c = e t , and each d ∈ C d\in\mathcal{C} d ∈ C determines exactly one pair ( f , u ) ∈ E × T (f,u)\in\mathcal{E}\times\mathcal{T} ( f , u ) ∈ E × T satisfying d = f u d=fu d = f u . Conversely, each such choice of factors determines c , d ∈ C c,d\in\mathcal{C} c , d ∈ C . Since c ≠ d c\ne d c = d if and only if e t ≠ f u et \ne fu e t = f u , and c d = e f t u cd = ef tu c d = e f t u , we obtain
∑ c , d ∈ C c ≠ d B 1 2 , 14 ( ∣ H ( c , d ) ∣ ) c d = ∑ e , f ∈ C 1 e f ∑ u ∈ T 1 u ∑ t ∈ T e t ≠ f u B 1 2 , 14 ( ∣ H ( e t , f u ) ∣ ) t ≪ ( ∑ u ∈ T 1 u ) ∑ e , f ∈ C B 1 2 , 14 ( gcd ( e , f ) ) e f ≪ ( log Y ) 2 . \begin{aligned}
\sum_{\substack{c,d\in\mathcal{C}\\c\ne d}} \frac{\mathcal{B}_{\frac{1}{2},14}(|H(c,d)|)}{cd}
= \sum_{e,f\in\mathcal{C}} \frac{1}{ef}\sum_{u\in\mathcal{T}} \frac{1}{u}\sum_{\substack{t\in\mathcal{T}\\et\ne fu}} \frac{\mathcal{B}_{\frac{1}{2},14}(|H(et,fu)|)}{t} \\
&\ll\left(\sum_{u\in\mathcal{T}}\frac{1}{u}\right)\sum_{e,f\in\mathcal{C}}\frac{\mathcal{B}_{\frac{1}{2},14}(\gcd(e,f))}{ef}
\ll(\log Y)^2.
\end{aligned} c , d ∈ C c = d ∑ c d B 2 1 , 14 ( ∣ H ( c , d ) ∣ ) = e , f ∈ C ∑ e f 1 u ∈ T ∑ u 1 t ∈ T e t = f u ∑ t B 2 1 , 14 ( ∣ H ( e t , f u ) ∣ ) ≪ ( u ∈ T ∑ u 1 ) e , f ∈ C ∑ e f B 2 1 , 14 ( g cd( e , f )) ≪ ( log Y ) 2 .
Here (119) bounds the sum over u u u . For the remaining sum, all terms are nonnegative, so we include all positive integers e , f ≤ Y 2 e,f\le Y^2 e , f ≤ Y 2 and apply the harmonic gcd averaging lemma with β = 1 2 \beta=\frac{1}{2} β = 2 1 , K = 14 K=14 K = 14 , and Z = Y 2 Z=Y^2 Z = Y 2 . Combining this estimate with (128) gives
∑ c , d ∈ C c ≠ d ∑ r , s ∈ R G ( c r , d s ) 3 2 c d r s ≪ ( log Y ) 2 . (130) \sum_{\substack{c,d\in\mathcal{C}\\c\ne d}}\sum_{r,s\in\mathcal{R}}\frac{G(cr,ds)^{\frac{3}{2}}}{cdrs}\ll(\log Y)^2. \tag*{(130)} c , d ∈ C c = d ∑ r , s ∈ R ∑ c d r s G ( cr , d s ) 2 3 ≪ ( log Y ) 2 . (130)
For every p ≥ 2 p\ge2 p ≥ 2 , we have ( 1 + 2 p ) 3 ≤ 1 + 14 p \left(1+\frac{2}{p}\right)^3\le1+\frac{14}{p} ( 1 + p 2 ) 3 ≤ 1 + p 14 (as may be seen by expanding the left-hand side). Multiplying over the prime divisors of a positive integer N N N gives
B 1 , 2 ( N ) 3 ≤ B 1 , 14 ( N ) . (131) \mathcal{B}_{1,2}(N)^3\le\mathcal{B}_{1,14}(N). \tag*{(131)} B 1 , 2 ( N ) 3 ≤ B 1 , 14 ( N ) . (131)
Fix c , d ∈ C c,d\in\mathcal{C} c , d ∈ C and s ∈ R s\in\mathcal{R} s ∈ R , allowing c = d c=d c = d , and put U = w ( c ) U=w(c) U = w ( c ) and W = w ( d ) W=w(d) W = w ( d ) . Consider
F ( T ) = ( U T + c ) ( c T − d s ) . (132) F(T)=(UT+c)(cT-ds). \tag*{(132)} F ( T ) = ( U T + c ) ( c T − d s ) . (132)
This is a polynomial of degree two with positive leading coefficient U c Uc U c . Its coefficients are U c Uc U c , c 2 − U d s c^2-Uds c 2 − U d s , and − c d s -cds − c d s . Since U = w ( c ) U=w(c) U = w ( c ) , Lemma 1, applied with n = c n=c n = c , gives gcd ( U , c ) = 1 \gcd(U,c)=1 g cd( U , c ) = 1 . Consequently, the equalities among
gcd ( U , c 2 − U d s ) = gcd ( U , c 2 ) = 1 \gcd(U,c^2-Uds)=\gcd(U,c^2)=1 g cd( U , c 2 − U d s ) = g cd( U , c 2 ) = 1
hold. It follows that
cont ( F ) = gcd ( U c , c 2 − U d s , c d s ) = gcd ( c , c 2 − U d s , c d s ) = gcd ( c , U d s ) = gcd ( c , d s ) = gcd ( c , d ) . \begin{aligned}
\operatorname{cont}(F)&=\gcd(Uc,c^2-Uds,cds)\\
&=\gcd(c,c^2-Uds,cds)\\
&=\gcd(c,Uds)\\
&=\gcd(c,ds)=\gcd(c,d).
\end{aligned} cont ( F ) = g cd( U c , c 2 − U d s , c d s ) = g cd( c , c 2 − U d s , c d s ) = g cd( c , U d s ) = g cd( c , d s ) = g cd( c , d ) .
In the second equality, the factor U U U can be removed because it is relatively prime to c 2 − U d s c^2-Uds c 2 − U d s . The third equality uses c ∣ c d s c\mid cds c ∣ c d s and c 2 − U d s ≡ − U d s c^2-Uds\equiv-Uds c 2 − U d s ≡ − U d s (mod c c c ). The fourth uses gcd ( c , U ) = 1 \gcd(c,U)=1 g cd( c , U ) = 1 , and the last uses gcd ( c , s ) = 1 \gcd(c,s)=1 g cd( c , s ) = 1 , since s s s is prime and s > c s>c s > c .
Applying the upper bound in Lemma 3 with n = c n=c n = c and n = d n=d n = d , and using U = w ( c ) U=w(c) U = w ( c ) , W = w ( d ) W=w(d) W = w ( d ) , and c , d ≤ Y 13 c,d\le Y^{13} c , d ≤ Y 13 , we obtain
U , W ≤ 13 log 2 Y 13 log Y ≤ Y 14 U,W\le\frac{13}{\log2}Y^{13}\log Y\le Y^{14} U , W ≤ log 2 13 Y 13 log Y ≤ Y 14
for all sufficiently large Y Y Y , uniformly for c , d ∈ C c,d\in\mathcal{C} c , d ∈ C . For every real v v v with Y 40 < v ≤ Y 41 Y^{40}<v\le Y^{41} Y 40 < v ≤ Y 41 , we therefore have
0 < U v + c ≤ 2 Y 55 , ∣ c v − d s ∣ ≤ Y 54 . 0<Uv+c\le2Y^{55},\qquad|cv-ds|\le Y^{54}. 0 < U v + c ≤ 2 Y 55 , ∣ c v − d s ∣ ≤ Y 54 .
The second inequality holds because both c v cv c v and d s ds d s lie between zero and Y 54 Y^{54} Y 54 . Thus
∣ F ( v ) ∣ ≤ 2 Y 109 ≤ Y 110 . |F(v)|\le2Y^{109}\le Y^{110}. ∣ F ( v ) ∣ ≤ 2 Y 109 ≤ Y 110 .
The polynomial averaging estimate (21) consequently applies with α = 40 \alpha=40 α = 40 , δ = 41 \delta=41 δ = 41 , β = 1 \beta=1 β = 1 , K = 14 K=14 K = 14 , degree bound two, and M = 110 M=110 M = 110 , uniformly in c , d , s c,d,s c , d , s .
For r ∈ R r\in\mathcal{R} r ∈ R , the factor U r + c Ur+c U r + c is positive, so, from the definition of F F F in (132) , we have that F ( r ) F(r) F ( r ) is nonvanishing if and only if c r cr cr and d s ds d s are distinct. Moreover, whenever c r ≠ d s cr\ne ds cr = d s , we also have that D ( c r , d s ) = ( W s + d ) ∣ F ( r ) ∣ D(cr,ds)=(Ws+d)|F(r)| D ( cr , d s ) = ( W s + d ) ∣ F ( r ) ∣ . Using Lemma 4 and (21) together, this gives us that
∑ r ∈ R c r ≠ d s B 1 , 14 ( D ( c r , d s ) ) r ≤ B 1 , 14 ( W s + d ) ∑ r ∈ R F ( r ) ≠ 0 B 1 , 14 ( ∣ F ( r ) ∣ ) r ≪ B 1 , 14 ( W s + d ) B 1 , 14 ( gcd ( c , d ) ) . \sum_{\substack{r\in\mathcal{R}\\cr\ne ds}}\frac{B_{1,14}(D(cr,ds))}{r}
\le B_{1,14}(Ws+d)\sum_{\substack{r\in\mathcal{R}\\F(r)\ne0}}\frac{B_{1,14}(|F(r)|)}{r}
\ll B_{1,14}(Ws+d)B_{1,14}(\gcd(c,d)). r ∈ R cr = d s ∑ r B 1 , 14 ( D ( cr , d s )) ≤ B 1 , 14 ( W s + d ) r ∈ R F ( r ) = 0 ∑ r B 1 , 14 ( ∣ F ( r ) ∣ ) ≪ B 1 , 14 ( W s + d ) B 1 , 14 ( g cd( c , d )) .
Since W = w ( d ) W=w(d) W = w ( d ) , Lemma 1, applied with n = d n=d n = d , gives us that gcd ( W , d ) = 1 \gcd(W,d)=1 g cd( W , d ) = 1 , so that the polynomial W T + d WT+d W T + d is primitive. Moreover,
0 < W v + d ≤ 2 Y 55 ≤ Y 56 ( Y 40 < v ≤ Y 41 ) . 0<Wv+d\le2Y^{55}\le Y^{56}\qquad(Y^{40}<v\le Y^{41}). 0 < W v + d ≤ 2 Y 55 ≤ Y 56 ( Y 40 < v ≤ Y 41 ) .
Applying (21) to this polynomial with degree bound one and M = 56 M=56 M = 56 , with the other parameters unchanged, gives
∑ s ∈ R B 1 , 14 ( W s + d ) s ≪ 1. \sum_{s\in\mathcal{R}}\frac{B_{1,14}(Ws+d)}{s}\ll1. s ∈ R ∑ s B 1 , 14 ( W s + d ) ≪ 1.
Multiplying the preceding bound for the sum over r r r by 1 s \frac{1}{s} s 1 and summing over s ∈ R s\in\mathcal{R} s ∈ R consequently yields
∑ r , s ∈ R c r ≠ d s B 1 , 14 ( D ( c r , d s ) ) r s ≪ B 1 , 14 ( gcd ( c , d ) ) . (133) \sum_{\substack{r,s\in\mathcal{R}\\cr\ne ds}}\frac{B_{1,14}(D(cr,ds))}{rs}\ll B_{1,14}(\gcd(c,d)). \tag*{(133)} r , s ∈ R cr = d s ∑ r s B 1 , 14 ( D ( cr , d s )) ≪ B 1 , 14 ( g cd( c , d )) . (133)
The implied constant and the lower bound on Y Y Y in (133) are independent of c c c and d d d . Both applications of (21) use fixed numerical parameters and fixed degree bounds, and their real-interval estimates hold uniformly over the remaining factors. We may therefore sum (133) with weights 1 c d \frac{1}{cd} c d 1 over c , d ∈ C c,d\in\mathcal{C} c , d ∈ C . Applying the uniqueness assertion accompanying (110) to both c , d ∈ C c,d\in\mathcal{C} c , d ∈ C , we obtain unique factors e , f ∈ E e,f\in\mathcal{E} e , f ∈ E and t , u ∈ T t,u\in\mathcal{T} t , u ∈ T such that c = e t c=et c = e t and d = f u d=fu d = f u . Both t t t and u u u exceed both e e e and f f f . If t ≠ u t\ne u t = u , then gcd ( t , f u ) = gcd ( u , e t ) = 1 \gcd(t,fu)=\gcd(u,et)=1 g cd( t , f u ) = g cd( u , e t ) = 1 , so gcd ( e t , f u ) = gcd ( e , f ) \gcd(et,fu)=\gcd(e,f) g cd( e t , f u ) = g cd( e , f ) . If t = u t=u t = u , then gcd ( e t , f u ) = t gcd ( e , f ) \gcd(et,fu)=t\gcd(e,f) g cd( e t , f u ) = t g cd( e , f ) . Hence
gcd ( e t , f u ) = { gcd ( e , f ) , t ≠ u , t gcd ( e , f ) , t = u . \gcd(et,fu)=
\begin{cases}
\gcd(e,f), & t\ne u,\\
t\gcd(e,f), & t=u.
\end{cases} g cd( e t , f u ) = { g cd( e , f ) , t g cd( e , f ) , t = u , t = u .
In the t = u t=u t = u case, applying Lemma 4 with β = 1 \beta=1 β = 1 , K = 14 K=14 K = 14 , M = t M=t M = t , and N = gcd ( e , f ) N=\gcd(e,f) N = g cd( e , f ) , and using B 1 , 14 ( t ) = 1 + 14 t \mathcal{B}_{1,14}(t)=1+\frac{14}{t} B 1 , 14 ( t ) = 1 + t 14 and t ≥ 2 t\ge2 t ≥ 2 , we obtain
B 1 , 14 ( t gcd ( e , f ) ) ≤ ( 1 + 14 t ) B 1 , 14 ( gcd ( e , f ) ) ≤ 8 B 1 , 14 ( gcd ( e , f ) ) . \mathcal{B}_{1,14}(t\gcd(e,f))\leq\left(1+\frac{14}{t}\right)\mathcal{B}_{1,14}(\gcd(e,f))\leq8\mathcal{B}_{1,14}(\gcd(e,f)). B 1 , 14 ( t g cd( e , f )) ≤ ( 1 + t 14 ) B 1 , 14 ( g cd( e , f )) ≤ 8 B 1 , 14 ( g cd( e , f )) .
The same bound therefore holds in both cases, and we obtain
∑ c , d ∈ C B 1 , 14 ( gcd ( c , d ) ) c d = ∑ e , f ∈ E 1 e f ∑ t , u ∈ T B 1 , 14 ( gcd ( e t , f u ) ) t u \sum_{c,d\in\mathcal{C}}\frac{\mathcal{B}_{1,14}(\gcd(c,d))}{cd}
=
\sum_{e,f\in\mathcal{E}}\frac{1}{ef}\sum_{t,u\in\mathcal{T}}\frac{\mathcal{B}_{1,14}(\gcd(et,fu))}{tu} c , d ∈ C ∑ c d B 1 , 14 ( g cd( c , d )) = e , f ∈ E ∑ e f 1 t , u ∈ T ∑ t u B 1 , 14 ( g cd( e t , f u ))
≤ 8 ( ∑ t ∈ T 1 t ) 2 ∑ e , f ∈ E B 1 , 14 ( gcd ( e , f ) ) e f ≪ ( log Y ) 2 . \begin{aligned}
\leq8\left(\sum_{t\in\mathcal{T}}\frac{1}{t}\right)^2\sum_{e,f\in\mathcal{E}}\frac{\mathcal{B}_{1,14}(\gcd(e,f))}{ef} \\
&\ll(\log Y)^2.
\end{aligned} ≤ 8 ( t ∈ T ∑ t 1 ) 2 e , f ∈ E ∑ e f B 1 , 14 ( g cd( e , f )) ≪ ( log Y ) 2 .
The final inequality uses (119) and the harmonic gcd averaging lemma with β = 1 \beta=1 β = 1 , K = 14 K=14 K = 14 , and Z = Y 2 Z=Y^2 Z = Y 2 , after including all positive integers e , f ≤ Y 2 e,f\leq Y^2 e , f ≤ Y 2 . Summing (133) with weights 1 c d \frac{1}{cd} c d 1 and using (131) now gives
∑ a , b ∈ A a ≠ b B 1 , 2 ( D ( a , b ) ) 3 a b ≪ ( log Y ) 2 . (134) \sum_{\substack{a,b\in\mathcal{A}\\a\ne b}}\frac{\mathcal{B}_{1,2}(D(a,b))^3}{ab}\ll(\log Y)^2. \tag*{(134)} a , b ∈ A a = b ∑ ab B 1 , 2 ( D ( a , b ) ) 3 ≪ ( log Y ) 2 . (134)
By the uniqueness asserted for the factorization a = c r a=cr a = cr in (111) , applied to both a a a and b b b , each ordered pair ( a , b ) ∈ A 2 (a,b)\in\mathcal{A}^2 ( a , b ) ∈ A 2 determines exactly one choice of c , d ∈ C c,d\in\mathcal{C} c , d ∈ C and r , s ∈ R r,s\in\mathcal{R} r , s ∈ R such that a = c r a=cr a = cr and b = d s b=ds b = d s . Under these substitutions, the condition c r ≠ d s cr\ne ds cr = d s is equivalent to a ≠ b a\ne b a = b .
Applying the formulation of Hölder’s inequality indicated in (5) with exponents 3 2 \frac{3}{2} 2 3 and 3 3 3 to the finite sum over c , d ∈ C c,d\in\mathcal{C} c , d ∈ C , c ≠ d c\ne d c = d , and r , s ∈ R r,s\in\mathcal{R} r , s ∈ R , we obtain
∑ c , d ∈ C , r , s ∈ R c ≠ d G ( c r , d s ) B 1 , 2 ( D ( c r , d s ) ) c d r s ≤ ( ∑ c , d ∈ C , r , s ∈ R c ≠ d G ( c r , d s ) 3 / 2 c d r s ) 2 / 3 ( ∑ c , d ∈ C , r , s ∈ R c ≠ d B 1 , 2 ( D ( c r , d s ) ) 3 c d r s ) 1 / 3 . \sum_{\substack{c,d\in\mathcal{C},\,r,s\in\mathcal{R}\\c\ne d}}\frac{G(cr,ds)\mathcal{B}_{1,2}(D(cr,ds))}{cdrs}
\leq
\left(\sum_{\substack{c,d\in\mathcal{C},\,r,s\in\mathcal{R}\\c\ne d}}\frac{G(cr,ds)^{3/2}}{cdrs}\right)^{2/3}
\left(\sum_{\substack{c,d\in\mathcal{C},\,r,s\in\mathcal{R}\\c\ne d}}\frac{\mathcal{B}_{1,2}(D(cr,ds))^3}{cdrs}\right)^{1/3}. c , d ∈ C , r , s ∈ R c = d ∑ c d r s G ( cr , d s ) B 1 , 2 ( D ( cr , d s )) ≤ c , d ∈ C , r , s ∈ R c = d ∑ c d r s G ( cr , d s ) 3/2 2/3 c , d ∈ C , r , s ∈ R c = d ∑ c d r s B 1 , 2 ( D ( cr , d s ) ) 3 1/3 .
The first factor is bounded according to (130). For the latter factor, we find that c ≠ d ⇒ c r ≠ d s c \ne d \Rightarrow cr \ne ds c = d ⇒ cr = d s by virtue of (113), so that, with the use of (134), we obtain that
∑ c , d ∈ C c ≠ d ∑ r , s ∈ R B 1 , 2 3 ( D ( c r , d s ) ) c d r s ≤ ∑ c , d ∈ C c r ≠ d s ∑ r , s ∈ R B 1 , 2 3 ( D ( c r , d s ) ) c d r s = ∑ a , b ∈ A a ≠ b B 1 , 2 3 ( D ( a , b ) ) a b ≪ ( log Y ) 2 . \sum_{\substack{c,d\in\mathcal{C}\\c\ne d}}\sum_{r,s\in\mathcal{R}}\frac{\mathcal{B}_{1,2}^{3}(D(cr,ds))}{cdrs}\le\sum_{\substack{c,d\in\mathcal{C}\\cr\ne ds}}\sum_{r,s\in\mathcal{R}}\frac{\mathcal{B}_{1,2}^{3}(D(cr,ds))}{cdrs}
=\sum_{\substack{a,b\in\mathcal{A}\\a\ne b}}\frac{\mathcal{B}_{1,2}^{3}(D(a,b))}{ab}
\ll(\log Y)^2. c , d ∈ C c = d ∑ r , s ∈ R ∑ c d r s B 1 , 2 3 ( D ( cr , d s )) ≤ c , d ∈ C cr = d s ∑ r , s ∈ R ∑ c d r s B 1 , 2 3 ( D ( cr , d s )) = a , b ∈ A a = b ∑ ab B 1 , 2 3 ( D ( a , b )) ≪ ( log Y ) 2 .
The foregoing arguments combine to give us that
∑ c , d ∈ C c ≠ d ∑ r , s ∈ R G ( c r , d s ) B 1 , 2 ( D ( c r , d s ) ) c d r s ≪ ( log Y ) 2 . (135) \sum_{\substack{c,d\in\mathcal{C}\\c\ne d}}\sum_{r,s\in\mathcal{R}}\frac{G(cr,ds)\mathcal{B}_{1,2}(D(cr,ds))}{cdrs}\ll(\log Y)^2. \tag*{(135)} c , d ∈ C c = d ∑ r , s ∈ R ∑ c d r s G ( cr , d s ) B 1 , 2 ( D ( cr , d s )) ≪ ( log Y ) 2 . (135)
For each a ∈ A a\in\mathcal{A} a ∈ A , we have 2 ∣ a 2\mid a 2 ∣ a by (115). Applying both bounds in Lemma 3 with n = a n=a n = a , we obtain
a 2 ≤ w ( a ) ≤ a log a log 2 ≤ 54 log 2 Y 54 log Y ≤ Y 55 = x 0.055 (136) \frac{a}{2}\le w(a)\le\frac{a\log a}{\log2}\le\frac{54}{\log2}Y^{54}\log Y\le Y^{55}=x^{0.055} \tag*{(136)} 2 a ≤ w ( a ) ≤ log 2 a log a ≤ log 2 54 Y 54 log Y ≤ Y 55 = x 0.055 (136)
for all sufficiently large Y Y Y , uniformly in a a a . Also, a ≤ Y 54 = x 0.054 a\le Y^{54}=x^{0.054} a ≤ Y 54 = x 0.054 by (109). For distinct a , b ∈ A a,b\in\mathcal{A} a , b ∈ A , the bounds in (136), applied to both a a a and b b b , together with a , b ≤ x 0.054 a,b\le x^{0.054} a , b ≤ x 0.054 , show that Lemma 8 applies with A = w ( a ) A=w(a) A = w ( a ) and B = w ( b ) B=w(b) B = w ( b ) .
Fix c , d ∈ C c,d\in\mathcal{C} c , d ∈ C with c ≠ d c\ne d c = d and r , s ∈ R r,s\in\mathcal{R} r , s ∈ R , and put a = c r a=cr a = cr and b = d s b=ds b = d s . For primes in the defining intervals for a p , b q ∈ N x ap,bq\in\mathcal{N}_x a p , b q ∈ N x , we have p ∤ a p\nmid a p ∤ a and q ∤ b q\nmid b q ∤ b , so Lemma 2 gives the biconditional equivalence such that w ( a p ) = w ( b q ) ⟺ w ( a ) p − w ( b ) q = b − a w(ap)=w(bq)\Longleftrightarrow w(a)p-w(b)q=b-a w ( a p ) = w ( b q ) ⟺ w ( a ) p − w ( b ) q = b − a . If gcd ( w ( a ) , w ( b ) ) \gcd(w(a),w(b)) g cd( w ( a ) , w ( b )) does not divide b − a b-a b − a , there are no such pairs. If it does divide b − a b-a b − a , then G ( a , b ) = gcd ( w ( a ) , w ( b ) ) G(a,b)=\gcd(w(a),w(b)) G ( a , b ) = g cd( w ( a ) , w ( b )) . In both cases, Lemma 8 bounds the number of ordered prime pairs by
C ( x G ( a , b ) a b ( log x ) 2 B 1 , 2 ( D ( a , b ) ) + x 0.03 ) , (137) C\left(\frac{xG(a,b)}{ab(\log x)^2}\mathcal{B}_{1,2}(D(a,b))+x^{0.03}\right), \tag*{(137)} C ( ab ( log x ) 2 x G ( a , b ) B 1 , 2 ( D ( a , b )) + x 0.03 ) , (137)
with one absolute constant C C C .
Now, for fixed c , d ∈ C c,d\in\mathcal{C} c , d ∈ C and r , s ∈ R r,s\in\mathcal{R} r , s ∈ R , let M x ( c , d , r , s ) M_x(c,d,r,s) M x ( c , d , r , s ) denote the cardinality of the set of all pairs ( p , q ) (p,q) ( p , q ) such that p p p and q q q are prime, x 2 c r < p ≤ x c r \frac{x}{2cr}<p\le\frac{x}{cr} 2 cr x < p ≤ cr x , x 2 d s < q ≤ x d s \frac{x}{2ds}<q\le\frac{x}{ds} 2 d s x < q ≤ d s x , and w ( c r p ) = w ( d s q ) w(crp)=w(dsq) w ( cr p ) = w ( d s q ) . Also, let E ≠ ( x ) E_{\ne}(x) E = ( x ) denote the number of ordered pairs ( n 1 , n 2 ) ∈ N x 2 (n_1,n_2)\in\mathcal{N}_x^2 ( n 1 , n 2 ) ∈ N x 2 satisfying w ( n 1 ) = w ( n 2 ) w(n_1)=w(n_2) w ( n 1 ) = w ( n 2 ) for which the unique factorizations n 1 = c r p n_1=crp n 1 = cr p and n 2 = d s q n_2=dsq n 2 = d s q have c ≠ d c\ne d c = d . The uniqueness established in (111) and (112) then gives us the counting identity such that
E ≠ ( x ) = ∑ c , d ∈ C c ≠ d ∑ r , s ∈ R M x ( c , d , r , s ) . (138) E_{\ne}(x)=\sum_{\substack{c,d\in\mathcal{C}\\c\ne d}}\sum_{r,s\in\mathcal{R}}M_x(c,d,r,s). \tag*{(138)} E = ( x ) = c , d ∈ C c = d ∑ r , s ∈ R ∑ M x ( c , d , r , s ) . (138)
For c , d ∈ C c,d \in\mathcal{C} c , d ∈ C with c ≠ d c \ne d c = d and r , s ∈ R r,s \in\mathcal{R} r , s ∈ R , we have c r ≠ d s cr \ne ds cr = d s by (113) . The application of Lemma 8 recorded in (137) , with a = c r a=cr a = cr and b = d s b=ds b = d s , gives
M T ( c , d , r , s ) ≤ C ( x ( log x ) 2 G ( c r , d s ) B 1 , 2 ( D ( c r , d s ) ) c d r s + x 0.03 ) . (139) M_{\mathcal{T}}(c,d,r,s) \le C\left(\frac{x}{(\log x)^2}\frac{G(cr,ds)B_{1,2}(D(cr,ds))}{cdrs}+x^{0.03}\right). \tag*{(139)} M T ( c , d , r , s ) ≤ C ( ( log x ) 2 x c d r s G ( cr , d s ) B 1 , 2 ( D ( cr , d s )) + x 0.03 ) . (139)
With regard to the index sets associated with the quadruple sum in (138) , the number of corresponding 4-tuples is at most ∣ C ∣ 2 ∣ R ∣ 2 = ∣ A ∣ 2 |\mathcal{C}|^2|\mathcal{R}|^2=|\mathcal{A}|^2 ∣ C ∣ 2 ∣ R ∣ 2 = ∣ A ∣ 2 , and this is because the unique factorization property in (111) gives us that ∣ A ∣ = ∣ C ∣ ∣ R ∣ |\mathcal{A}|=|\mathcal{C}||\mathcal{R}| ∣ A ∣ = ∣ C ∣∣ R ∣ . This and (138) and (139) together give us that
E ≠ ( x ) ≤ C x ( log x ) 2 ∑ c , d ∈ C c ≠ d ∑ r , s ∈ R G ( c r , d s ) B 1 , 2 ( D ( c r , d s ) ) c d r s + C ∣ A ∣ 2 x 0.03 . (140) E_{\ne}(x) \le\frac{Cx}{(\log x)^2}
\sum_{\substack{c,d\in\mathcal{C}\\c\ne d}}
\sum_{r,s\in\mathcal{R}}
\frac{G(cr,ds)B_{1,2}(D(cr,ds))}{cdrs}
+C|\mathcal{A}|^2x^{0.03}. \tag*{(140)} E = ( x ) ≤ ( log x ) 2 C x c , d ∈ C c = d ∑ r , s ∈ R ∑ c d r s G ( cr , d s ) B 1 , 2 ( D ( cr , d s )) + C ∣ A ∣ 2 x 0.03 . (140)
Since A \mathcal{A} A consists of positive integers at most Y 54 Y^{54} Y 54 , we have ∣ A ∣ ≤ Y 54 |\mathcal{A}|\le Y^{54} ∣ A ∣ ≤ Y 54 . Applying (135) to the right-hand side of (140) , we obtain
C x ( log x ) 2 ∑ c , d ∈ C c ≠ d ∑ r , s ∈ R G ( c r , d s ) B 1 , 2 ( D ( c r , d s ) ) c d r s + C ∣ A ∣ 2 x 0.03 ≪ x ( log Y ) 2 ( log x ) 2 + Y 108 x 0.03 ≪ x + Y 138 ≪ x . \begin{aligned}
\frac{Cx}{(\log x)^2}
\sum_{\substack{c,d\in\mathcal{C}\\c\ne d}}
\sum_{r,s\in\mathcal{R}}
\frac{G(cr,ds)B_{1,2}(D(cr,ds))}{cdrs}
+C|\mathcal{A}|^2x^{0.03} \\
&\ll\frac{x(\log Y)^2}{(\log x)^2}+Y^{108}x^{0.03} \\
&\ll x+Y^{138} \\
&\ll x.
\end{aligned} ( log x ) 2 C x c , d ∈ C c = d ∑ r , s ∈ R ∑ c d r s G ( cr , d s ) B 1 , 2 ( D ( cr , d s )) + C ∣ A ∣ 2 x 0.03 ≪ ( log x ) 2 x ( log Y ) 2 + Y 108 x 0.03 ≪ x + Y 138 ≪ x .
Here x = Y 1000 x=Y^{1000} x = Y 1000 , so x 0.03 = Y 30 x^{0.03}=Y^{30} x 0.03 = Y 30 and Y 138 = o ( x ) Y^{138}=o(x) Y 138 = o ( x ) . Consequently, the relation
E ≠ ( x ) ≪ x (141) E_{\ne}(x)\ll x \tag*{(141)} E = ( x ) ≪ x (141)
holds.
Fix c ∈ C c\in\mathcal{C} c ∈ C and distinct r , s ∈ R r,s\in\mathcal{R} r , s ∈ R , and let p p p and q q q be primes such that x 2 c r < p ≤ x c r \frac{x}{2cr}<p\le\frac{x}{cr} 2 cr x < p ≤ cr x and x 2 c s < q ≤ x c s \frac{x}{2cs}<q\le\frac{x}{cs} 2 cs x < q ≤ cs x . Since c r , c s ≤ Y 54 cr,cs\le Y^{54} cr , cs ≤ Y 54 and p , q > 1 2 Y 946 > Y 54 p,q>\frac{1}{2}Y^{946}>Y^{54} p , q > 2 1 Y 946 > Y 54 for sufficiently large x x x , we have p ∤ c r p\nmid cr p ∤ cr and q ∤ c s q\nmid cs q ∤ cs . Using the identities w ( c r p ) = p w ( c r ) + c r w(crp)=p\,w(cr)+cr w ( cr p ) = p w ( cr ) + cr and w ( c s q ) = q w ( c s ) + c s w(csq)=q\,w(cs)+cs w ( cs q ) = q w ( cs ) + cs , we find that the equality w ( c r p ) = w ( c s q ) w(crp)=w(csq) w ( cr p ) = w ( cs q ) is equivalent to
w ( c r ) p − w ( c s ) q = c ( s − r ) . (142) w(cr)p-w(cs)q=c(s-r). \tag*{(142)} w ( cr ) p − w ( cs ) q = c ( s − r ) . (142)
If this equation has no integer solutions, it contributes no prime pairs. Otherwise, fix one integer solution ( p 0 , q 0 ) (p_0,q_0) ( p 0 , q 0 ) . For any other integer solution ( p , q ) (p,q) ( p , q ) , subtracting the two equations gives w ( c r ) ( p − p 0 ) = w ( c s ) ( q − q 0 ) w(cr)(p-p_0)=w(cs)(q-q_0) w ( cr ) ( p − p 0 ) = w ( cs ) ( q − q 0 ) . The integers w ( c r ) gcd ( w ( c r ) , w ( c s ) ) \frac{w(cr)}{\gcd(w(cr),w(cs))} g c d ( w ( cr ) , w ( cs )) w ( cr ) and w ( c s ) gcd ( w ( c r ) , w ( c s ) ) \frac{w(cs)}{\gcd(w(cr),w(cs))} g c d ( w ( cr ) , w ( cs )) w ( cs ) are relatively prime. It follows that w ( c s ) gcd ( w ( c r ) , w ( c s ) ) ∣ ( p − p 0 ) \frac{w(cs)}{\gcd(w(cr),w(cs))}\mid(p-p_0) g c d ( w ( cr ) , w ( cs )) w ( cs ) ∣ ( p − p 0 ) . Thus the possible values of p p p lie in one residue class modulo w ( c s ) gcd ( w ( c r ) , w ( c s ) ) \frac{w(cs)}{\gcd(w(cr),w(cs))} g c d ( w ( cr ) , w ( cs )) w ( cs ) . Now, observe that the interval x 2 c r < p ≤ x c r \frac{x}{2cr}<p\le\frac{x}{cr} 2 cr x < p ≤ cr x is of length x 2 c r \frac{x}{2cr} 2 cr x . Distinct integers in that residue class differ by at least the modulus, so the interval contains at most x gcd ( w ( c r ) , w ( c s ) ) 2 c r w ( c s ) + 1 \frac{x\gcd(w(cr),w(cs))}{2crw(cs)}+1 2 cr w ( cs ) x g c d ( w ( cr ) , w ( cs )) + 1 possible values of p p p . Each determines at most one q q q through (142) . Since 2 ∥ c s 2 \parallel cs 2 ∥ cs , the lower bound in Lemma 3, applied with n = c s n=cs n = cs , gives w ( c s ) ≥ c s 2 w(cs) \ge\frac{cs}{2} w ( cs ) ≥ 2 cs . Therefore the number of ordered prime pairs in the required intervals satisfying (142) is at most
x gcd ( w ( c r ) , w ( c s ) ) c 2 r s + 1. (143) \frac{x\gcd(w(cr),w(cs))}{c^{2}rs}+1. \tag*{(143)} c 2 r s x g cd( w ( cr ) , w ( cs )) + 1. (143)
This bound also holds when there are no integer solutions.
For fixed c ∈ C c \in C c ∈ C , let U = w ( c ) U=w(c) U = w ( c ) . Since c > 1 c>1 c > 1 , the definition of w w w gives us that U > 0 U>0 U > 0 . By Lemma 1, applied with n = c n=c n = c , we have that gcd ( U , c ) = 1 \gcd(U,c)=1 g cd( U , c ) = 1 . Moreover, the equality gcd ( w ( c r ) , w ( c s ) ) = gcd ( U r + c , U s + c ) \gcd(w(cr),w(cs))=\gcd(Ur+c,Us+c) g cd( w ( cr ) , w ( cs )) = g cd( U r + c , U s + c ) holds. Since r , s > Y 40 r,s>Y^{40} r , s > Y 40 , Lemma 9, applied with R = Y 41 R=Y^{41} R = Y 41 , gives
∑ r , s ∈ R r ≠ s gcd ( w ( c r ) , w ( c s ) ) r s ≤ Y − 80 ∑ 1 ≤ m , n ≤ Y 41 m ≠ n gcd ( U m + c , U n + c ) ≪ Y − 80 Y 82 log ( Y 41 ) ≪ Y 2 log Y . \begin{aligned}
\sum_{\substack{r,s\in\mathcal{R}\\r\ne s}}\frac{\gcd(w(cr),w(cs))}{rs}
\le Y^{-80}\sum_{\substack{1\le m,n\le Y^{41}\\m\ne n}}\gcd(Um+c,Un+c) \\
&\ll Y^{-80}Y^{82}\log(Y^{41})\ll Y^{2}\log Y.
\end{aligned} r , s ∈ R r = s ∑ r s g cd( w ( cr ) , w ( cs )) ≤ Y − 80 1 ≤ m , n ≤ Y 41 m = n ∑ g cd( U m + c , U n + c ) ≪ Y − 80 Y 82 log ( Y 41 ) ≪ Y 2 log Y .
The constant is independent of c c c and U = w ( c ) U=w(c) U = w ( c ) . Moreover, by (109) , the relations among
∑ c ∈ C 1 c 2 ≤ ∑ n > Y 11 1 n 2 ≤ ∫ [ Y 11 ] ∞ d v v 2 = 1 [ Y 11 ] ≪ Y − 11 \sum_{c\in C}\frac{1}{c^{2}}\le\sum_{n>Y^{11}}\frac{1}{n^{2}}
\le\int_{[Y^{11}]}^{\infty}\frac{dv}{v^{2}}
=\frac{1}{[Y^{11}]}
\ll Y^{-11} c ∈ C ∑ c 2 1 ≤ n > Y 11 ∑ n 2 1 ≤ ∫ [ Y 11 ] ∞ v 2 d v = [ Y 11 ] 1 ≪ Y − 11
hold, where n n n ranges over positive integers. We also find that ∣ C ∣ ≤ Y 13 |C|\le Y^{13} ∣ C ∣ ≤ Y 13 and that ∣ R ∣ ≤ Y 41 |\mathcal{R}|\le Y^{41} ∣ R ∣ ≤ Y 41 . Summing (143) over c ∈ C c\in C c ∈ C and distinct r , s ∈ R r,s\in\mathcal{R} r , s ∈ R consequently shows that the number of ordered equal-value pairs with c = d c=d c = d and r ≠ s r\ne s r = s is at most
x ∑ c ∈ C 1 c 2 ∑ r , s ∈ R r ≠ s gcd ( w ( c r ) , w ( c s ) ) r s + ∣ C ∣ ∣ R ∣ 2 ≪ x Y − 11 Y 2 log Y + Y 13 + 82 . x\sum_{c\in C}\frac{1}{c^{2}}\sum_{\substack{r,s\in\mathcal{R}\\r\ne s}}\frac{\gcd(w(cr),w(cs))}{rs}+|C||\mathcal{R}|^{2}\ll xY^{-11}Y^{2}\log Y+Y^{13+82}. x c ∈ C ∑ c 2 1 r , s ∈ R r = s ∑ r s g cd( w ( cr ) , w ( cs )) + ∣ C ∣∣ R ∣ 2 ≪ x Y − 11 Y 2 log Y + Y 13 + 82 .
As a consequence, we have that
( # of ordered equal-value pairs s.t. c = d and r ≠ s ) ≪ x Y − 9 log Y + Y 95 . (\#\text{ of ordered equal-value pairs s.t. }c=d\text{ and }r\ne s)\ll xY^{-9}\log Y+Y^{95}. ( # of ordered equal-value pairs s.t. c = d and r = s ) ≪ x Y − 9 log Y + Y 95 .
From this and the equality x = Y 1000 x=Y^{1000} x = Y 1000 equivalent to (107) , we find that
( # of ordered equal-value pairs s.t. c = d and r ≠ s ) = o ( x ) . (144) (\#\text{ of ordered equal-value pairs s.t. }c=d\text{ and }r\ne s)=o(x). \tag*{(144)} ( # of ordered equal-value pairs s.t. c = d and r = s ) = o ( x ) . (144)
Finally, if c = d c=d c = d and r = s r=s r = s , then a = b a=b a = b . The equality w ( a p ) = w ( a q ) w(ap)=w(aq) w ( a p ) = w ( a q ) then yields w ( a ) ( p − q ) = 0 w(a)(p-q)=0 w ( a ) ( p − q ) = 0 . Since w ( a ) > 0 w(a)>0 w ( a ) > 0 , it follows that p = q p=q p = q . These are precisely the pairs ( n , n ) (n,n) ( n , n ) with n ∈ N x n \in\mathcal{N}_x n ∈ N x . There are
∣ N x ∣ ≤ x (145) |\mathcal{N}_x| \le x \tag*{(145)} ∣ N x ∣ ≤ x (145)
such pairs.
Define E ( x ) = ∣ { ( n 1 , n 2 ) ∈ N x 2 : w ( n 1 ) = w ( n 2 ) } ∣ E(x)=|\{(n_1,n_2)\in\mathcal{N}_x^2:w(n_1)=w(n_2)\}| E ( x ) = ∣ {( n 1 , n 2 ) ∈ N x 2 : w ( n 1 ) = w ( n 2 )} ∣ . For each ordered pair ( n 1 , n 2 ) ∈ N x 2 (n_1,n_2)\in\mathcal{N}_x^2 ( n 1 , n 2 ) ∈ N x 2 with w ( n 1 ) = w ( n 2 ) w(n_1)=w(n_2) w ( n 1 ) = w ( n 2 ) , there exist elements c c c and d d d in C \mathcal{C} C , elements r r r and s s s in R \mathcal{R} R , and primes p p p and q q q such that n 1 = c r p n_1=crp n 1 = cr p , n 2 = d s q n_2=dsq n 2 = d s q , x 2 c r < p ≤ x c r \frac{x}{2cr}<p\le\frac{x}{cr} 2 cr x < p ≤ cr x , and x 2 d s < q ≤ x d s \frac{x}{2ds}<q\le\frac{x}{ds} 2 d s x < q ≤ d s x . By (109) , we have that c r , d s ≤ Y 54 cr,ds\le Y^{54} cr , d s ≤ Y 54 . Since x = Y 1000 x=Y^{1000} x = Y 1000 and Y ≥ 2 Y\ge2 Y ≥ 2 , it follows that p , q > 1 2 Y 946 > Y 54 p,q>\frac{1}{2}Y^{946}>Y^{54} p , q > 2 1 Y 946 > Y 54 . Thus p p p and q q q are the largest prime divisors of n 1 n_1 n 1 and n 2 n_2 n 2 , respectively. Consequently, the primes p p p and q q q and the integers c r = n 1 p cr=\frac{n_1}{p} cr = p n 1 and d s = n 2 q ds=\frac{n_2}{q} d s = q n 2 are uniquely determined by ( n 1 , n 2 ) (n_1,n_2) ( n 1 , n 2 ) . By (113) , the pairs ( c , r ) (c,r) ( c , r ) and ( d , s ) (d,s) ( d , s ) are then uniquely determined. Therefore, for each such ordered pair ( n 1 , n 2 ) (n_1,n_2) ( n 1 , n 2 ) , exactly one of the following conditions holds: c ≠ d c\ne d c = d ; c = d c=d c = d and r ≠ s r\ne s r = s ; or c = d c=d c = d and r = s r=s r = s .
We have thus partitioned the pairs counted by E ( x ) E(x) E ( x ) into three disjoint classes, writing
E ( x ) = E ≠ ( x ) + E(x)=E_{\ne}(x)+ E ( x ) = E = ( x ) +
number of ordered equal-value pairs with c = d c=d c = d and r ≠ s + ∣ N x ∣ r\ne s+|\mathcal{N}_x| r = s + ∣ N x ∣ .
By (144) , the preceding equality gives us that
E ( x ) = E ≠ ( x ) + o ( x ) + ∣ N x ∣ . E(x)=E_{\ne}(x)+o(x)+|\mathcal{N}_x|. E ( x ) = E = ( x ) + o ( x ) + ∣ N x ∣.
From the relation E ≠ ( x ) ≪ x E_{\ne}(x)\ll x E = ( x ) ≪ x highlighted in (141) and from the bound for ∣ N x ∣ |\mathcal{N}_x| ∣ N x ∣ highlighted in (145) , we thus obtain that
E ( x ) ≪ x . (146) E(x)\ll x. \tag*{(146)} E ( x ) ≪ x . (146)
For each nonnegative integer v v v , define R x ( v ) = ∣ { n ∈ N x : w ( n ) = v } ∣ R_x(v)=|\{n\in\mathcal{N}_x:w(n)=v\}| R x ( v ) = ∣ { n ∈ N x : w ( n ) = v } ∣ . Only finitely many R x ( v ) R_x(v) R x ( v ) are nonzero, with ∑ v ≥ 0 R x ( v ) = ∣ N x ∣ \sum_{v\ge0}R_x(v)=|\mathcal{N}_x| ∑ v ≥ 0 R x ( v ) = ∣ N x ∣ and ∑ v ≥ 0 R x ( v ) 2 = E ( x ) \sum_{v\ge0}R_x(v)^2=E(x) ∑ v ≥ 0 R x ( v ) 2 = E ( x ) . The second equality holds because R x ( v ) 2 R_x(v)^2 R x ( v ) 2 counts the ordered pairs of elements of N x \mathcal{N}_x N x that both have value v v v under w w w .
Let v 1 , v 2 , … , v k v_1,v_2,\ldots,v_k v 1 , v 2 , … , v k be the distinct values attained by w w w on N x \mathcal{N}_x N x . Applying the Cauchy–Schwarz inequality to the vectors ( R x ( v 1 ) , R x ( v 2 ) , … , R x ( v k ) ) (R_x(v_1),R_x(v_2),\ldots,R_x(v_k)) ( R x ( v 1 ) , R x ( v 2 ) , … , R x ( v k )) and ( 1 , 1 , … , 1 ) (1,1,\ldots,1) ( 1 , 1 , … , 1 ) , we obtain that
∣ N x ∣ 2 = ( ∑ v ≥ 0 R x ( v ) > 0 R x ( v ) ) 2 ≤ ∣ { v ≥ 0 : R x ( v ) > 0 } ∣ ∑ v ≥ 0 R x ( v ) 2 = ∣ { w ( n ) : n ∈ N x } ∣ E ( x ) . |\mathcal{N}_x|^2=\left(\sum_{\substack{v\ge0\\R_x(v)>0}}R_x(v)\right)^2
\le|\{v\ge0:R_x(v)>0\}|\sum_{v\ge0}R_x(v)^2
=|\{w(n):n\in\mathcal{N}_x\}|E(x). ∣ N x ∣ 2 = v ≥ 0 R x ( v ) > 0 ∑ R x ( v ) 2 ≤ ∣ { v ≥ 0 : R x ( v ) > 0 } ∣ v ≥ 0 ∑ R x ( v ) 2 = ∣ { w ( n ) : n ∈ N x } ∣ E ( x ) .
By (108) and (114) together, each element in N x \mathcal{N}_x N x is a positive integer that does not exceed x x x . Also, (120) implies that N x \mathcal{N}_x N x is nonempty for all sufficiently large x x x , so E ( x ) ≥ ∣ N x ∣ > 0 E(x) \geq|\mathcal{N}_x| > 0 E ( x ) ≥ ∣ N x ∣ > 0 . Hence
V ( x ) ≥ ∣ { w ( n ) : n ∈ N x } ∣ ≥ ∣ N x ∣ 2 E ( x ) . V(x) \geq\left|\{w(n): n \in\mathcal{N}_x\}\right| \geq\frac{|\mathcal{N}_x|^2}{E(x)}. V ( x ) ≥ ∣ { w ( n ) : n ∈ N x } ∣ ≥ E ( x ) ∣ N x ∣ 2 .
By (120) and (146), there exist absolute constants c 1 , c 2 > 0 c_1,c_2 > 0 c 1 , c 2 > 0 such that, for all sufficiently large real x x x , each of the relations among ∣ N x ∣ ≥ c 1 x |\mathcal{N}_x| \geq c_1x ∣ N x ∣ ≥ c 1 x and E ( x ) ≤ c 2 x E(x) \leq c_2x E ( x ) ≤ c 2 x holds. It follows that V ( x ) ≥ c 1 2 c 2 x V(x) \geq\frac{c_1^2}{c_2}x V ( x ) ≥ c 2 c 1 2 x . Taking c 0 = c 1 2 c 2 c_0 = \frac{c_1^2}{c_2} c 0 = c 2 c 1 2 and choosing one absolute x 0 x_0 x 0 large enough for all the preceding estimates proves the asserted bound for every real x ≥ x 0 x \geq x_0 x ≥ x 0 . Dividing by x x x and taking the lower limit gives us that (106) holds, as desired. □
Conclusion
Since we have proved, as in Theorem 1, that lim inf x → ∞ V ( x ) x \liminf_{x\to\infty}\frac{V(x)}{x} lim inf x → ∞ x V ( x ) is strictly positive, this raises the question as to how lim inf x → ∞ V ( x ) x \liminf_{x\to\infty}\frac{V(x)}{x} lim inf x → ∞ x V ( x ) can be evaluated explicitly or numerically estimated in a meaningful way (noting that it is immediate that lim inf x → ∞ V ( x ) x ≤ 1 \liminf_{x\to\infty}\frac{V(x)}{x} \leq1 lim inf x → ∞ x V ( x ) ≤ 1 ). Omitting details, our construction above, as in our proof of Theorem 1, can be used to show that
lim inf x → ∞ V ( x ) x > 3 × 10 − 20 . \liminf_{x\to\infty}\frac{V(x)}{x} > 3 \times10^{-20}. x → ∞ lim inf x V ( x ) > 3 × 1 0 − 20 .
We very much encourage future research endeavors based on the problems of bounding, numerically estimating, and evaluating lim inf x → ∞ V ( x ) x \liminf_{x\to\infty}\frac{V(x)}{x} lim inf x → ∞ x V ( x ) . This also raises a further open question: Does the limit lim x → ∞ V ( x ) x \lim_{x\to\infty}\frac{V(x)}{x} lim x → ∞ x V ( x ) exist?
The behavior of V ( x ) x \frac{V(x)}{x} x V ( x ) for integers x ∈ [ 1 , 10 000 ] x \in[1,10\,000] x ∈ [ 1 , 10 000 ] is illustrated in the plot indicated in Figure 1 .
Figure 1. A plot of the values of V ( x ) x \frac{V(x)}{x} x V ( x ) for integers x ∈ [ 1 , 10 000 ] x \in[1,10\,000] x ∈ [ 1 , 10 000 ] , generated using the ListLinePlot command in Mathematica.
AI disclosure. The following AI disclosure is based on AI disclosures used and written by the author previously (with numerous parts taken verbatim from previous AI disclosures used and written by the author).
Our solution above to Erdős’s problem is, as indicated above, based on our extensive interactions with GPT-6 Astra Pro, and this is described in more detail below. All AI-generated suggestions were substantially revised, corrected, and independently verified by the author, who assumes full responsibility for the mathematical content. The author’s use of AI is fully in accordance with editorial standards on the responsible, ethical, and transparent use of AI.
The author inputted a prompt into GPT-6 Astra Pro containing an equivalent version of the problem from Guy’s text solved above (with an explicit attribution to Guy’s text on unsolved problems in number theory), concluding with an explicit request that GPT-6 Astra Pro solve the given problem. After 16m 16s of thinking, GPT-6 Astra Pro provided a response beginning with the following, and provided a very rudimentary outline of a potential proof:
“I obtain a negative answer. The argument below gives the stronger conclusion lim inf x → ∞ V ( x ) x > 0 \liminf_{x\to\infty} \frac{V(x)}{x} > 0 lim inf x → ∞ x V ( x ) > 0 . In particular, V ( x ) ≠ o ( x ) V(x) \ne o(x) V ( x ) = o ( x ) . This is a proposed proof developed here. Because it would resolve the published question, it should receive independent specialist review before submission. I have written out the uniform estimates and the exceptional cases on which the argument depends.”
After extensive clarifications, corrections, revisions, suggestions, verifications, calculations, etc., through extensive discussions between the author and GPT-6 Astra Pro, and after extensive and careful reviews of such discussions on the part of the author, this provided a basis for the above solution, written by the author, to Erdős’s problem.
Specific examples of corrections, revisions, clarifications, constructions, etc., on the part of the author include a modification of a previous version of the bound in (57) to construct a corrected proof associated with the ρ ( 2 ) = 2 \rho(2)=2 ρ ( 2 ) = 2 case involved in the proof of Lemma 8, the use of (14) in relation to (16)–(19), the use of the bound in (99) for quadratic harmonic numbers, the use of the bound in (100) for skew harmonic numbers, the use of an upper bound for harmonic numbers in relation to (105), the many uses of and references to Lemmas 1–4 throughout the paper, the justification related to the derivation of (146) as to how the pairs ( c , r ) (c,r) ( c , r ) and ( d , s ) (d,s) ( d , s ) are uniquely determined by invoking (113), the justification based on the uniqueness of the factorization in (110) and related to the bounds for
∑ c , d ∈ C c ≠ d B 1 2 , 14 ( ∣ H ( c , d ) ∣ ) c d \sum_{\substack{c,d\in C\\c\ne d}}\frac{\mathcal{B}_{\frac{1}{2},14}(|H(c,d)|)}{cd} c , d ∈ C c = d ∑ c d B 2 1 , 14 ( ∣ H ( c , d ) ∣ )
, the relation in (144) and its derivation, the use of and derivation of the inequality
∑ c , d ∈ C c ≠ d ∑ r , s ∈ R B 1 , 2 ( D ( c r , d s ) ) 3 c d r s ≤ ∑ a , b ∈ A a ≠ b B 1 , 2 ( D ( a , b ) ) 3 a b \sum_{\substack{c,d\in C\\c\ne d}}\sum_{r,s\in R}\frac{\mathcal{B}_{1,2}(D(cr,ds))^3}{cdrs}\le\sum_{\substack{a,b\in A\\a\ne b}}\frac{\mathcal{B}_{1,2}(D(a,b))^3}{ab} c , d ∈ C c = d ∑ r , s ∈ R ∑ c d r s B 1 , 2 ( D ( cr , d s ) ) 3 ≤ a , b ∈ A a = b ∑ ab B 1 , 2 ( D ( a , b ) ) 3
in the derivation of (135) , the counting identity in (138) and the use of the bounds in (139) and (140) to justify both (141) and (146) , a correction of an incorrect statement in the proof of Theorem 1 concerning how the right-hand side of (128) relates to (129) and to the estimate
∑ c , d ∈ C c ≠ d B 1 2 , 14 ( ∣ H ( c , d ) ∣ ) c d ≪ ( log Y ) 2 \sum_{\substack{c,d\in C\\c\ne d}}\frac{\mathcal{B}_{\frac{1}{2},14}(|H(c,d)|)}{cd}\ll(\log Y)^2 c , d ∈ C c = d ∑ c d B 2 1 , 14 ( ∣ H ( c , d ) ∣ ) ≪ ( log Y ) 2
established in the proof of Theorem 1, the use of the consequence in (79) of the Chinese remainder theorem in relation to (90) , (91) , and (94) , the use of (118) in relation to the derivation of (120) , etc.
Extensive Mathematica programs for numerically verifying the above construction have been carefully prepared and written and tested by the author and are available upon request.
Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 4R2, Canada
Email address: jh241966@dal.ca