Proving the Duffin-Schaeffer conjecture without GCD graphs
Manuel Hauke Santiago Vazquez Saez Aled Walker


We present a novel proof of the Duffin–Schaeffer conjecture in metric Diophantine approximation. Our proof is heavily motivated by the ideas of Koukoulopoulos–Maynard's breakthrough first argument, but simplifies and strengthens several technical aspects. In particular, we avoid any direct handling of GCD graphs and their `quality'. We also consider the metric quantitative theory of Diophantine approximations, improving the (logΨ(N))^-C error-term of Aistleitner–Borda and the first named author to exp(-(logΨ(N))^1/2 - ε). 

Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall τ-Metric
      
The Nguyen


Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, IL 61801, United States

Email:   thevn2@illinois.edu 

    April 29, 2024
=======================================================================================================================================================



§ INTRODUCTION

The Duffin–Schaeffer conjecture was a long-standing open problem in the area of Diophantine approximation. It was concerned with the following broad question: given an arbitrary fixed function ψ: ℕ→ℝ_⩾ 0, and a typical irrational number α∈ [0,1], when should one expect to find infinitely many rational numbers a/n with 

    |α - a/n|⩽ψ(n)/n?

If ψ is reasonably `well-behaved' (such as ψ(n) = 1/n, or ψ(n) = 1/(n log n), or in general a function with nψ(n) monotonically decreasing) then a satisfactory answer was already known by Khintchine <cit.> in 1924. But if ψ is a wilder function, in particular if ψ(n) = 0 for all but a very sparse set of denominators n, then it is much more challenging to understand whether inequality (<ref>) is satisfied infinitely often.

In 1941, Duffin and Schaeffer <cit.> proposed a criterion on the approximation function ψ which should determine whether such approximations exist. 
After certain partial progress, by Duffin and Schaeffer themselves, Gallagher <cit.>, Erdős̋ <cit.>, Vaaler<cit.>, Pollington and Vaughan <cit.>, and more recently in <cit.>, the Duffin–Schaeffer conjecture was finally resolved by Koukoulopoulos and Maynard <cit.> in July 2019. 

[Theorem 1, <cit.>]

Let ψ:ℕ⟶ℝ_⩾ 0 be a function satisfying

    ∑_n=1^∞ψ(n) φ(n)/n = ∞,
 where φ denotes the Euler totient function. Then, for almost all α∈ [0,1], inequality (<ref>) has infinitely many coprime integer solutions (a,n). 

By refining and developing the Koukoulopoulos–Maynard method, Aistleitner, Borda and the first named author were able to count solutions to (<ref>). 
[Theorem 1, <cit.>]

Let ψ: ℕ→ [0,1/2] be a function satisfying (<ref>). Write S(N,α) for the number of coprime integer solutions (a,n) to the inequality (<ref>) subject to 1 ⩽ n ⩽ N, and let 
    Ψ(N): = ∑_n = 1^N2 φ(n) ψ(n)/n.
 Then, for all A>0 and almost all α∈ [0,1] 
    S(N, α) = Ψ(N)( 1 + O _α,A( 1/(logΨ(N))^A))
 as N →∞. In particular, for almost all α∈ [0,1] one has S(N,α) →∞ if Ψ(N) →∞. 


These results may be motivated as follows. Assuming that ψ takes values in [0,1/2], to avoid some minor degeneracy issues (Theorem <ref> for the case where ψ(n) ⩾12 for infinitely many n was resolved in <cit.>), define 

    𝒜_n: = ⋃_0 ⩽ a ⩽ n 
    (a,n) = 1[ a/n - ψ(n)/n, a/n + ψ(n)/n] ∩ [0,1].
 Then, writing λ for the Lebesgue measure, we have 
    λ(𝒜_n) = 2 φ(n) ψ(n)/n.
 Viewing α as a random variable chosen uniformly at random from [0,1], one has S(N, α) = ∑_n ⩽ N1_[α∈𝒜_n] and Ψ(N) = ∑_n ⩽ Nλ(𝒜_n) = 𝔼_α S(N, α). Theorem <ref> is therefore the statement that the random variable S(N, α) concentrates around its mean. For more background on the motivation behind the Duffin–Schaeffer conjecture, we direct the reader to the introductions of <cit.>.
 

In this paper, we revisit the proofs of Theorems <ref> and <ref>. It transpires that the core ideas of <cit.> may be `repackaged' and, when combined with some new arguments, the overall proofs may be substantially shortened[by roughly 75%, in terms of the number of pages required] and conceptually simplified. Though we consider our main novel contribution to be the statement and proof of the technical estimate Theorem <ref> below, as a corollary we also reduce the size of the error term in Theorem <ref>.
[Improved error term for quantitative metric approximations]

Under the same hypothesis as Theorem <ref>, for all ε >0 and almost every α∈ [0,1],
 
    S(N,α) = Ψ(N)(1 + O_ε,α(exp(-(logΨ(N))^1/2 -ε))),
 

Moreover, as we will explain below, our Theorem <ref> is potentially strong enough to prove a near square-root cancellation error term O_ε(Ψ(N)^-1/2 + ε) in Corollary <ref>. 
Up to the Ψ(N)^ε term, the error term is in accordance with the one known for 
the Khintchine setup, that is, considering monotonic ψ and not only counting coprime approximations, see <cit.> or <cit.>. Furthermore we note that due to the diagonal contribution, a square-root error term is the best that can be obtained by an L^2-approach; to the best of the authors' knowledge, all proofs in this area rely on this tool.

However, any significant improvement on Corollary 1.3 would also require development to the sieve-theoretic estimates of [2, Lemma 5], on which our argument relies. As it happens, an independent work of Koukoulopoulos–Maynard–Yang <cit.>, elaborated at the same time as our present manuscript, established such an almost square-root cancellation, by improving on precisely these sieve elements. They also prove a version of our main technical estimates (Theorem 1.7 below). However, their arguments use the complicated technical formalism of GCD graphs, which we deliberately avoid.



Theorems <ref> and <ref> were proved by bounding _α(S(N,α)) above. As 
    _α(S(N,α)) = ∑_n,m ⩽ Nλ(𝒜_n ∩𝒜_m) - Ψ(N)^2,
 one requires a so-called `overlap estimate' on λ(𝒜_n ∩𝒜_m). Utilising a 0-1 law of Gallagher <cit.>, Koukoulopoulos–Maynard were satisfied with proving an upper bound ∑_n,m ⩽ Nλ(𝒜_n ∩𝒜_m) ≪Ψ(N)^2 that might lose a constant factor in the implied constant. It was enough therefore to use an older overlap estimate of Pollington–Vaughan on λ(𝒜_n ∩𝒜_m) (<cit.> and <cit.>), which also lost such a factor. However, as Aistleitner, Borda and the first named author needed to prove _α(S(N, α)) = o_N →∞(1), they required an asymptotic on ∑_n,m ⩽ Nλ(𝒜_n ∩𝒜_m). They thus required an upper bound of the form λ(𝒜_n ∩𝒜_m) ⩽λ(𝒜_n) λ(𝒜_m)(1 + E(n,m)), with E(n,m) an error that could be shown to be o(1) on average over n and m. The Pollington–Vaughan overlap estimate was insufficient. 

Here we state the refined overlap estimate from <cit.>, along with a corollary we will use later. Note the breakdown of independence of the events α∈𝒜_n and α∈𝒜_m when n has many prime factors that do not divide m (or vice versa), or when (n,m) is large. 

[Overlap estimate]

	For any positive integers n ≠ m and any reals u ⩾ 1 and T ⩾ 2, we have
	
    λ (𝒜_n ∩𝒜_m) ⩽λ (𝒜_n) λ (𝒜_m) ( 1 + O ( u^-u/2 + T^u log (D+2) log T/D) ) ∏_p |nm/(n,m)^2, 
     p>T( 1+ 1/p-1)

	with an absolute implied constant, where 
 
    D = D(n,m):= max(  m ψ(n), n ψ(m) )/ (n,m).
 In particular, writing
F_ρ(x) = exp((log x)^1/2-ρ), we have for any 0 < ρ < 1/2 that
	
    λ (𝒜_n∩𝒜_m) ⩽λ (𝒜_n) λ (𝒜_m) ( 1 + O_ρ(F_ρ(D)^-1) ) ∏_p |nm/(n,m)^2, 
     p>F_ρ(D)( 1+ 1/p-1)

	with an implied constant depending only on ρ.
 Furthermore, we have 
 
    λ(𝒜_n∩𝒜_m) ≪λ (𝒜_n) λ (𝒜_m) ∏_p |nm/(n,m)^2, 
     p>D( 1+ 1/p).




    Equation (<ref>) is precisely <cit.>, which has a short three-page proof combining the classical overlap approach of Pollington–Vaughan with the Fundamental Lemma of sieve theory. Equation (<ref>) then follows from (<ref>) by choosing 
    u = √(log D) and T = F_ρ(D). Equation (<ref>) follows from (<ref>) by choosing u= 2, T = D^1/10 and applying Mertens' Theorem in the form of ∏_D^1/10 < p < D(1 + 1/p-1) ≪ 1. (In fact equation (<ref>) would also follow from Pollington–Vaughan, in <cit.> or <cit.>). 


Using (<ref>), one seeks a bound of the form 

    ∑_n,m ⩽ Nλ(𝒜_n∩𝒜_m) ⩽Ψ(N)^2(1 + o_N →∞(1)),
 for some quantitative o_N →∞(1) term. After this the estimate _α(S(N,α)) = o_N →∞(1) would follow immediately, and Theorem <ref> would be proved by a standard procedure that combines Chebyshev's inequality and the first Borel-Cantelli Lemma; this allows moving, at a minimal cost in the speed of convergence, from a variance bound to almost sure asymptotics, provided the quantitative decay is sufficiently rapid, see e.g. <cit.>. In the case of Theorem <ref>, this is handled on pp. 210-211 of <cit.>, and we also make use of this method in Section <ref> to obtain Corollary <ref>. 

 We are required to show that the contribution to ∑_n,m ⩽ Nλ(𝒜_n∩𝒜_m) coming from pairs (n,m) with small D (i.e. pairs for which (n,m) is large) is negligible, when considered simultaneously with the potential contribution from pairs (n,m) for which 
    ∏_p |nm/(n,m)^2
     p > T( 1 + 1/p-1)
 is much larger than 1. This is the content of <cit.>, Koukoulopoulos–Maynard's breakthrough estimate. The matter is also considered in <cit.>, whose proofs build on the Koukoulopoulos–Maynard method with refined estimates. Our main technical result is a general bilinear bound whose short self-contained proof implies all of these results. 

To prepare the statement of this bilinear bound, we introduce some notation for the weight associated to certain sets of integers and pairs of integers. 
[Measures]
Let ψ,θ: ℕ⟶ℝ_⩾ 0 be finitely supported, and let f,g:ℕ⟶ℝ_⩾ 0 be multiplicative functions. For v ∈ℕ we define 
    μ_ψ^f(v): = f(v) ψ(v)/v.
 When V ⊂ℕ we define 
    μ_ψ^f(V) := ∑_v ∈ Vμ_ψ^f(v) = ∑_v ∈ Vf(v) ψ(v)/v.
 If ℰ⊂ℕ×ℕ, we define 
    μ_ψ,θ^f,g(ℰ): = ∑_(v,w) ∈ℰμ_ψ^f(v) μ_θ^g(w).
 

We now define a general set of pairs of integers (v,w) for which D is small and  many large primes divide vw/(v,w)^2. 


Let ψ,θ: ℕ⟶ℝ_⩾ 0 be finitely supported, with V_ψ = ψ and W_θ = θ, and let t ⩾ 1 and C ∈ℝ. Then we define 
    ℰ_ψ,θ^t, C: = {(v,w) ∈ V_ψ× W_θ:   D_ψ,θ(v,w) ⩽ 1,  ∑_p |vw/(v,w)^2
     p ⩾ t1/p⩾ C},
 where 
    D_ψ,θ(v,w) = max(wψ(v), v θ(w))/(v,w).
 


We can now state our main result. 

[Main technical result]

Let ε∈ (0,2/5]. Then there exists p_0(ε) >0 such that the following holds. Let ψ,θ: ℕ⟶ℝ_⩾ 0 be finitely supported, V_ψ = ψ, W_θ = θ and 
    𝒫_ψ,θ: = {p:  ∃  (v,w) ∈ V_ψ× W_θ s.t.  p | vw}.
 Let P_ψ,θ(ε): = p_0(ε) + |𝒫_ψ,θ∩ [1, p_0(ε)]|. Let f,g:ℕ⟶ℝ_⩾ 0 be multiplicative functions for which 

    (1 ⋆ f)(n) ⩽ n,     and     (1 ⋆ g)(n) ⩽ n       (for all n ⩾ 1).
 
Suppose that ℰ⊂ℰ_ψ, θ^t, C∩ (V × W).
Then for all t ⩾ 1 and any C ∈ℝ we have

    μ_ψ,θ^f,g(ℰ) ⩽ 1000^P_ψ,θ(ε)( μ_ψ^f(V) μ_θ^g(W) e^-Ct)^1/2 + ε.





 §.§ Remarks



  * The conditions of the theorem are satisfied if f = g = φ, in which case μ_ψ^f(V_ψ) =  Ψ(N)/2 and the bound (<ref>) directly relates to the Duffin–Schaeffer setting. 

  * Since P_ψ,θ(ε) ⩽ 2 p_0(ε), we may conclude from (<ref>) that 
    μ_ψ,θ^f,g(ℰ) ≪_ε( μ_ψ^f(V) μ_θ^g(W) e^-Ct)^1/2 + ε,
 where the implied constant is independent of all functions and parameters except ε. We have stated (<ref>) in a more precise form in order to effect an induction argument later in the paper. 

  * Though Theorem <ref> may only seem to apply when D_ψ,θ(v,w) ⩽ 1, and not when
 D_ψ,θ(v,w) ⩽ t or D is bounded by some other parameter, we can immediately derive bounds in these more general cases, by rescaling the functions ψ and θ. To illustrate this, we show below that the key <cit.> of Koukouloupolos–Maynard indeed follows immediately from Theorem <ref>. In Section <ref>, we will also give the quick deductions that improve upon <cit.>, which lead eventually to Corollary <ref>.

  * The bound (<ref>) represents near square-root cancellation from the condition on the gcds given by D_ψ,θ(v,w) ⩽ 1, together with a further decay when pairs (v,w) have many large prime factors that do not divide v and w to the same exponent. This suggests that Corollary <ref> might be provable with near square-root cancellation too, but unfortunately the sieve argument inherent in the overlap estimate Lemma <ref> has too weak a relationship between the parameters u, T, and D to make full use of the strength of Theorem <ref>. 

  * The upper bound 2/5 in the range of ε in Theorem <ref> could be replaced by any fixed value less than 1/2, at the cost of replacing 1000 with a larger constant.
We chose 2/5 as the exponent in (<ref>) as 1/2 + 2/5 = 9/10 corresponds to the appearance of exponents 9 and 10 in Koukoulopoulos–Maynard's definition of the `quality' of a GCD graph <cit.>.




 §.§ Theorem <ref> implies the Duffin–Schaeffer conjecture


Here we show that Theorem <ref> can be applied in order to prove the Duffin–Schaeffer conjecture. To be more precise, we show that <cit.> follows immediately from  Theorem <ref>. We will omit further details of how the Duffin–Schaeffer conjecture may be deduced from <cit.>; this follows a similar (but more straightforward) path as the proof of our quantitative application in Section <ref>. One may also consult <cit.> for the argument. 

[Proposition 5.4 in Koukoulopoulos–Maynard <cit.>]
    Let Y ⩾ X ⩾ 1 and ψ: ℤ∩ [X,Y] → [0,∞) such that
    
    1 ⩽∑_X ⩽ n ⩽ Yψ(n)φ(n)/n⩽ 2.

    For each t ⩾ 1, denote
    
    ℰ_t := {(v,w) ∈ (ℤ∩ [X,Y])^2: D(v,w) ⩽ t, ∑_p |vw/(v,w)^2
     p ⩾ t1/p⩾ 10 }.

    Then 
    
    ∑_(v,w) ∈ℰ_tψ(v)φ(v)/vψ(w)φ(w)/w≪1/t.




    Defining ψ(q) := 1_[q ∈ [X,Y]]ψ(q)/t, we observe that
    ℰ_t = ℰ_ψ,ψ^t,10 (in the notation of Definition <ref>). Thus applying 
    Theorem <ref> with f = g = φ, we obtain
    
    ∑_(v,w) ∈ℰ_tψ(v)φ(v)/vψ(w)φ(w)/w = t^2 μ_ψ,ψ^φ,φ(ℰ_ψ,ψ^t,10)    ≪_ε
        t^2 (μ_ψ^φ([X,Y] ∩ℤ) μ_ψ^φ([X,Y] ∩ℤ) e^-10t)^1/2 + ε
       ≪_ε t^1 - 2εe^-10t(12 + ε)
       ≪_ε1/t

as required. 


To finish this introduction, we indicate the structure of the remainder of the paper. In Section <ref>, we discuss the general proof strategy for Theorem <ref> and reduce matters to proving two sub-propositions (Proposition <ref> and Proposition <ref> below). This involves a brief discussion of the relationship between our approach and Koukoulopoulos–Maynard <cit.>. The subsequent three sections are devoted to proving these propositions. In Section <ref> we deduce Corollary <ref> from Theorem <ref>.
In the appendices, we explain a relationship between our proof and the classical construction of Duffin and Schaeffer; we also make some remarks about the lemmas involving the anatomy of integers from Section <ref>. 



 §.§ Acknowledgements

This material is based upon work supported by the Swedish Research Council under grant no. 2021-06594 while the first and third authors were in residence at Institut Mittag-Leffler in Djursholm, Sweden, during the winter semester of 2024. We would like to thank the organisers of the semester programme (Pär Kurlberg, Morten Risager, and Anders Södergren). The first named author was supported by the EPSRC grant EP/X030784/1. The second named author is supported by a PhD studentship through the London School of Geometry and Number Theory. We are further grateful to Sam Chow, Andrew Granville, Ben Green, Dimitris Koukoulopoulos, and James Maynard, for several interesting conversations on topics related to this paper. 



 §.§ Notation

We use the standard O- and o-notations as well as the Vinogradov notations ≪,≫.
If ℰ⊂ V × W is a set of pairs and v ∈ V, then Γ_ℰ(v): = {w: (v,w) ∈ℰ} and we write ℰ|_V = {v ∈ V: ∃ w ∈ W: (v,w) ∈ℰ} (with Γ_ℰ(w), ℰ|_W defined analogously). For a prime p we use the standard p-adic valuation ν_p on the rationals, and for n ∈ℕ, we write p^i ‖ n if ν_p(n) = i. 
For multiplicative functions f,g, we define the Dirichlet convolution (f ⋆ g) (n) := ∑_d | n f(n)g(nd). Throughout the paper, it is understood that if ε∈ (0,1/2) is given, then q := 2/1 - 2 ε and q^': = 2/1+ 2ε.





§ PROOF STRATEGY



For the rest of the article, we fix a function p_0: (0,1/2) →ℝ_⩾ 0 whose values will be large enough for following arguments to hold.

Our proof of Theorem <ref> splits naturally into two parts. First, we analyse the structure of potential counterexamples to the theorem, showing that any counterexample must enjoy some weak combinatorial and arithmetic structure. Second, we use the presence of such a structure to prove (<ref>) directly. This is the same strategy as used in work of Green and the third named author <cit.>, which studied the gcd condition in isolation. 


[Structure of minimal potential counterexample]

Suppose Theorem <ref> were false. Fix functions ψ,θ: ℕ⟶ℝ_⩾ 0 with finite support such that |𝒫_ψ,θ| is minimal over all such pairs of functions for which there exist instances of ε, t, C, f, g, and ℰ⊂ℰ^t,C_ψ,θ satisfying the hypotheses of Theorem <ref> for which (<ref>) fails. Fix such instances of  ε, t, C, f, g, and ℰ. Write q^': = 2/1 + 2ε. Then there exists ℰ^'⊂ℰ for which


  * (ℰ^' is a near counterexample): μ_ψ,θ^f,g(ℰ^') > 1/2· 1000^P_ψ,θ(ε)( μ_ψ^f(V^') μ_θ^g(W^') e^-Ct)^1/q^' where
 V^':= ℰ^'|_V, W^': = ℰ^'|_W.

  * (ℰ^' is combinatorially structured): for all v ∈ V^' and w ∈ W^', 
    μ_θ^g(Γ_ℰ^'(v)) ⩾1/q^'μ_ψ,θ^f,g(ℰ^')/μ_ψ^f(V^')    and    μ_ψ^f(Γ_ℰ^'(w)) ⩾1/q^'μ_ψ,θ^f,g(ℰ^')/μ_θ^g(W^') .
 

  * (ℰ^' is arithmetically structured): there exists N ∈ℕ such that for all primes p and for all (v,w) ∈ℰ^', |ν_p(v/N)| + |ν_p(w/N)|⩽ 1. 





 §.§ Remarks



  * There will be special roles in this paper for the exponents q := 2/1 - 2 ε and q^': = 2/1+ 2ε. Note that these are conjugate exponents (1/q + 1/q^' = 1), q>2, and 1/q^' is the exponent appearing on the right-hand side of the inequality (<ref>).

  * Speaking in graph-theoretic terms, the combinatorial structure in part (2) is a form of one-sided regularity for the bipartite graph whose vertex set is V^'⊔ W^' and whose edge set is ℰ^'. Indeed, suppose we denote the (weighted) density δ of this graph by 
    δ: = μ_ψ,θ^f,g(ℰ^')/μ_ψ^f(V^') μ_θ^g (W^').
 Given v ∈ V^', the average (weighted) size of the neighbourhood Γ_ℰ^'(v) is  δμ_θ^g(W^'). Part (2) says that for every such v the size of the neighbourhood is at least 1/q^' times this expected value, and the analogous conclusion for every w ∈ W^' too. We note that (2) is not a new manoeuvre in this problem, being closely modelled on <cit.>. However, we have chosen to avoid graph-theoretic terminology in this article.
    
  * The arithmetic structure from part (3) can be fruitfully compared to the example constructed by Duffin–Schaeffer <cit.> (see the Appendix, or <cit.> for a more general approach), showing that Khintchine's Theorem is in general not true without the monotonicity condition.
Indeed, the proof of Proposition <ref> does not use the full strength of (<ref>); it is enough that f(n)/n and g(n)/n are non-negative 1-bounded multiplicative functions.
Since Proposition <ref> therefore can also be applied to 
f(n) = g(n) = n, the arithmetical structure part of Proposition <ref> can also be applied to the non-coprime
setting. We provide a more detailed discussion in the Appendix.



Proposition <ref> is then combined with the following result. 
[Resolution of minimal potential counterexample]

Fix ψ,θ, ε, C, t, f,g satisfying the hypotheses of Theorem <ref>. Suppose ℰ^'⊂ℰ^t,C_ψ,θ satisfies properties (2) and (3) from Proposition <ref> (with these parameters). Then ℰ^' cannot satisfy property (1) of Proposition <ref>. 


Manifestly the conclusion of Proposition <ref> contradicts the conclusion of Proposition <ref>, so it follows that no counterexamples to Theorem <ref> can exist. The proof of Proposition <ref> is a direct computation, rather similar to equation (<ref>) in the Appendix, but just using the condition |ν_p(v/N)| + |ν_p(w/N)|⩽ 1 rather than any exact formula as in (<ref>). 


It is worth reflecting briefly on how this strategy compares with the Koukoulopoulos–Maynard approach to proving <cit.>. Koukoulopoulos–Maynard also used a two-stage strategy, beginning with a potential counterexample ℰ and iterating until a highly structured counterexample ℰ^' was found; this counterexample was then ruled out by direct calculation. The difference is that Koukoulopoulos–Maynard sought an immensely structured counterexample ℰ^' (the `good GCD graph' of <cit.>): it required fixed integers a,b such that for all (v,w) ∈ℰ^', a | v, b| w and (a,b) = (v,w). This is a strictly stronger arithmetic structure than the one found in part (3) of Proposition <ref>. The presence of such integers a and b implies the structure found in part (3), taking N = (a,b), but in our paper we do not require N| v and N | w. 

This stronger structure makes proving the equivalent of Proposition <ref> a little easier (this argument is found in <cit.>). However, in order to locate such rigid structure, Koukoulopoulos–Maynard needed to fundamentally change the arithmetic weighting of the pairs ℰ, and iterate this altered quantity instead (introduced as the `quality' of a GCD graph in <cit.>). This alteration to the arithmetic weighting introduced a potentially unbounded loss, which then had to be won back elsewhere in the argument. This is the miraculous `cancellation of φ factors' in expression <cit.>, in which a factor of φ(a)φ(b)/ab cancels in numerator and denominator. 

Our approach via Propositions <ref> and <ref> avoids this potentially confusing flourish; in fact, the notion of GCD graphs and their `quality' is avoided completely. For readers familiar with the technical elements of <cit.>, the particular part we avoid is the iteration on primes in ℛ^♯ that occurs in the delicate <cit.>. The five cases (a)-(e) from <cit.> do feature obliquely in our argument, via the five possible options for the pair of valuations (ν_p(v/N), ν_p(w/N)) allowed by part (3) of Proposition <ref>, namely {(-1,0), (0,-1), (0,0), (0,1), (1,0)}. Yet these cases can be handled in a unified way during the proof of Proposition <ref>, keeping the proof relatively efficient. The structure developed by Koukoulopoulos–Maynard using the other quality iterations can be efficiently packaged in Lemma <ref> and Lemma <ref> below, which recast the argument as a structure theorem for measures on ℤ×ℤ (with no iteration required). 

To mention another complication present in <cit.> that we avoid, Koukoulopoulos–Maynard had to carefully control the number of iterations that occurred in their method, for fear of weakening the condition of p | vw/(v,w)^2 too much through the iteration. This is the source of the separation of conditions (d)(i) and (d)(ii) in <cit.>. We absorb this concern into the `minimal counterexample' property in Proposition <ref>, thus avoiding a case analysis and leading to a further simplification of the argument. 




§ PROOF OF PROPOSITION <REF>

Take ψ,θ,ε,C,t,f,g,ℰ,V,W as in the statement of Proposition <ref>, i.e. forming a minimal counterexample to Theorem <ref>. Suppose p ∈𝒫_ψ,θ. For i,j ⩾ 0, define V_i: = {v ∈ V:   p^i ‖ v} and W_j: = {w ∈ W:   p^j ‖ w}. Since ℰ is a counterexample to Theorem <ref> we must have μ_ψ,θ^f,g(ℰ) >0, so we may define 
    m(i,j): = μ_ψ,θ^f,g(ℰ∩ (V_i × W_j))/μ_ψ,θ^f,g(ℰ).
 We have m(i,j) ⩾ 0, and 
    ∑_i,j ⩾ 0 m(i,j) = 1,
 meaning that m defines a finitely-supported measure on ℤ_⩾ 0×ℤ_⩾ 0. 

Using the minimality assumption on ℰ, we may upper-bound m(i,j) by a bilinear expression with exponential decay away from the diagonal i=j. 

[Bilinear upper bound]

Let ψ,θ,ε,C,t,f,g,ℰ,m(i,j) be as above.
Writing for i,j ⩾ 0, α_i: = μ_ψ^f(V_i)/ μ_ψ^f(V) and β_j: = μ_θ^g(W_j)/μ_θ^g(W), we have

    m(i,j) ⩽ 1000^-1_[p ⩽ p_0(ε)]  p^-| i-j|/q   (α_i β_j e^ 1_i ≠ j) ^1/q'.



We will bound m(i,j) by bounding μ_ψ,θ^f,g(ℰ) from below and μ_ψ,θ^f,g(ℰ∩ (V_i × W_j)) from above. The naïve combination of these bounds will control m(i,j) as required. 

Indeed, since ℰ is a counterexample to Theorem <ref> we have 
    μ_ψ,θ^f,g(ℰ) ⩾ 1000^P_ψ,θ(ε)( μ_ψ^f(V) μ_θ^g(W) e^-Ct)^1/2 + ε.
 In order to bound μ_ψ,θ^f,g(ℰ∩ (V_i × W_j)) from above we will remove the influence of the prime p and then use the minimality assumption. The main barrier is notational.  Define ψ_i,j, θ_i,j: ℕ⟶ℝ_⩾ 0 by 
    ψ_i,j(v) := 
    p^j - min(i,j)ψ(p^i v)    if (p,v) = 1, 
    
    0    if  p | v,
 and
    θ_i,j(w) := 
    p^i - min(i,j)θ(p^jw)    if (p,w) = 1, 
    
    0    if  p | w,
 with
 
    ℰ_i,j := {(v,w): (p^i v, p^j w) ∈ℰ∩ (V_i × W_j)},  V_i:= { v:   p^iv ∈ V_i},  W_j:= {w:   p^j w ∈ W_j}.
 Then 

    μ_ψ_i,j^f(V_i) = p^j - min(i,j)∑_v ∈V_i f(v) ψ(p^i v)/v= p^j- min(i,j)(p^i/f(p^i))μ_ψ^f(V_i),

and similarly

    μ_θ_i,j^g(W_j) = p^i - min(i,j)( p^j/g(p^j))μ_θ^g(W_j).

Also

    μ_ψ,θ^f,g(ℰ∩ (V_i × W_j))
       =(  f(p^i) g(p^j)/p^i+j)p^-| i-j|μ_ψ_i,j, θ_i,j^f,g(ℰ_i,j).
 

The set ℰ_i,j is of the type that is considered in Theorem <ref>, enabling us to use the minimality assumption on ℰ to upper-bound the contribution from ℰ_i,j. Indeed, if (v,w) ∈ℰ_i,j then neither v nor w have a factor of p and

    (p^i v, p^j w) ⩾max(p^j w ψ(p^i v), p^i v θ(p^j w)).

Therefore 

    (v,w)    ⩾max( p^j - min(i,j)w ψ(p^i v), p^i - min(i,j) v θ (p^jw))
       = max( w ψ_i,j(v), v  θ_i,j(w)).

In addition,

    ∑_r ⩾ t 
     r |p^i+jvw/(p^iv,p^jw)^21/r⩾ C,

where r runs over primes here. Hence 

    ∑_r ⩾ t 
     r |vw/(v,w)^21/r⩾ C - 1_[i ≠ j]/p⩾ C - 1_[i ≠ j]/t.

So ℰ_i,j⊂ℰ^t, C - 1_[i ≠ j]/t_ψ_i,j, θ_i,j. Finally 
    𝒫_ψ_i,j, θ_i,j = 𝒫_ψ,θ∖{p}.
 Therefore, by the minimality assumption on |𝒫_ψ,θ|, the bound (<ref>) holds for μ_ψ_i,j, θ_i,j^f,g(ℰ_i,j). Hence,

    μ_ψ,θ^f,g(ℰ∩ (V_i × W_j)) 
       =(f(p^i) g(p^j)/p^i+j)p^-| i-j|μ_ψ_i,j, θ_i,j^f,g(ℰ_i,j) 
       ⩽(f(p^i) g(p^j)/p^i+j)p^-| i-j| 1000^P_ψ,θ(ε) - 1_[p ⩽ p_0(ε)](μ_ψ_i,j^f(V_i)μ_θ_i,j^g(W_j) e^-t(C- 1_[i ≠ j]/t))^1/2 + ε
       =(f(p^i) g(p^j)/p^i+j)^1/2 - ε p^-| i-j| (1/2 - ε)1000^P_ψ,θ(ε) - 1_[p ⩽ p_0(ε)]( μ_ψ^f( V_i) μ_θ^g(W_j) e^-t(C- 1_[i ≠ j]/t))^1/2 + ε
       ⩽  p^-| i-j| (1/2 - ε)1000^P_ψ,θ(ε) - 1_[p ⩽ p_0(ε)]( μ_ψ^f( V_i) μ_θ^g(W_j) e^-Ct +1_[i ≠ j])^1/2 + ε,

since f(p^i) ⩽ p^i and g(p^j) ⩽ p^j. 

Combining with the lower bound on μ_ψ,θ^f,g(ℰ) from equation (<ref>), and using 1/2 + ε⩽ 1, we obtain 
    m(i,j) ⩽ 1000^-1_[p ⩽ p_0(ε)]  p^-| i-j| (1/2 - ε)  (α_i β_j e^1_[i ≠ j]) ^1/2 + ε,
 as required. 

To make use of this bilinear upper bound, we will adapt a structural lemma on such measures from work of Green and the third named author <cit.>. 
[Decay away from the diagonal]

Let q >2, and write q^' for the conjugate index to q (i.e. 1/q + 1/q^' = 1). Let c_1 ⩽ 1, 0 < c_2 < 1, λ∈ (0, 1-c_2], and C_3 >0. Suppose that m is a finitely-supported probability measure on ℤ^2. Suppose that there are sequences x = (x_i)_i ∈ℤ, y = (y_j)_j ∈ℤ of non-negative reals such that ‖ x‖_ℓ^q^'(ℤ) = ‖ y ‖_ℓ^q^'(ℤ) = 1, and such that for all (i,j) ∈ℤ^2 we have 

    m(i,j) ⩽
    c_1 x_i y_j    if  i =j, 
    
    c_1 C_3 λ^| i-j| x_i y_j    if  i ≠ j.
 Then c_1 ⩾c_2/1 + (2 C_3 - 1) λ, and there exists k ∈ℤ such that 

    ∑_| i-k| + | j-k|⩾ 2 m(i,j) ≪_q, c_2, C_3 (λ^q)^2/q^' + (λ^q)^1 + 1/q.




 §.§ Remarks



  * We may take k to be an index for which x_ky_k = sup_i x_i y_i. The position m(k,k) is a natural choice for the place where m(i,j) is concentrated, as (k,k) is the index for which the bilinear upper bound (<ref>) is weakest.

  * The exponents in (<ref>) are written to indicate how each exponent is strictly greater than q. This is the critical property for the application. 

  * The implied constant in (<ref>) may be calculated, and tends to infinity as either q → 2, c_2 → 0, or C_3 →∞.

  * The proof of Lemma <ref> breaks down completely if c_1 > 1. It was therefore vital in Lemma <ref> that the multiplicative loss of a factor of e in the upper bound occurred only on the off-diagonal i ≠ j terms. This corresponds to the anatomy condition on primes p | vw/(v,w)^2 only involving the primes that divide v and w to different exponents. 




This is very similar to <cit.>. The difference is the introduction of the parameter C_3. 

We first prove the lower bound on c_1. Indeed, since ∑_i,j m(i,j) = 1 and q^'∈ (1,2) we have 

    1/c_1⩽∑_i ∈ℤ x_i y_i + C_3∑_i ≠ jλ^| i-j| x_i y_j    ⩽∑_i ∈ℤ (x_i y_i)^q^'/2 + C_3∑_m ∈ℤ
     m ≠ 0λ^| m|∑_i ∈ℤ (x_i y_i+m)^q^'/2
       ⩽( 1 + C_3 ∑_m ∈ℤ
     m ≠ 0λ^| m|)·sup_m ∈ℤ∑_i ∈ℤ (x_i y_i+m)^q^'/2⩽1 + (2C_3 - 1)λ/1 - λ· 1,
 where the final inequality followed by Cauchy–Schwarz and the assumption that ‖ x‖_ℓ^q^'(ℤ) = ‖ y ‖_ℓ^q^'(ℤ) = 1. The lower bound on c_1 follows from rearranging. 


Turning to (<ref>), write sup_i x_iy_i = 1 - γ for some γ∈ [0,1], and suppose this supremum is attained when i=k (such an index k exists since
∑_i ∈ℤx_iy_i converges). Then x_k,y_k ⩾ 1- γ, and so x_k^q^', y_k^q^'⩾ 1 - q^'γ. Therefore

    ∑_i ≠ k x_i^q^', ∑_j ≠ k y_j^q^'⩽ q^'γ⩽ 2γ and  x_i,y_j ⩽ (q^')^1/q^'γ^1/q^'⩽ 2γ^1/q^' when  i,j ≠ k.

For n = 1,2,3,4,5,6 write ∑_n: = ∑_(i,j) ∈ S_n m(i,j), where S_1,…,S_6 are the following sets, which partition ℤ^2:

    S_1 : = {(i,j) ∈ℤ^2: i ≠ j≠ k ≠ i},      S_2: = {(k,j):  | j-k|⩾ 2},
 
    S_3: = {(i,k):  | i-k|⩾ 2},      S_4: = {(k,k ± 1), (k ± 1, k)},      S_5: = {(i,i): i ≠ k},
 and finally S_6: = {(k,k)}. We bound the ∑_n in turn. 


Bound for ∑_1. By (<ref>), if i ≠ k we have x_i ≪ x_i^q^'/2γ^1/q^' (1 - q^'/2) (and analogously for y_j if j ≠ k). Hence 
    ∑_1⩽ C_3 ∑_i,j ≠ k 
     i ≠ jλ^| i-j| x_i y_j  ≪_C_3γ^2/q^' (1 - q^'/2)∑_i,j ≠ k 
     i ≠ jλ^| i-j| (x_i y_j)^q^'/2= γ^2/q^' - 1∑_m ≠ 0λ^| m|∑_i, i+m ≠ k (x_i y_i+m)^q^'/2.
 By Cauchy–Schwarz and (<ref>), for each fixed m we have 
    ∑_i,i+m ≠ k(x_i y_i+m)^q^'/2⩽( ∑_i ≠ k x_i^q^')^1/2( ∑_j ≠ k y_j^q^')^1/2≪γ.
 Furthermore ∑_m ≠ 0λ^| m| = 2λ/1 - λ⩽2(1 -c_2)/c_2. Therefore ∑_1 ≪_c_2,C_3γ^2/q^'. 


Bounds for ∑_2, ∑_3. For ∑_2, we use the trivial bound x_k ⩽ 1 to derive 
    ∑_2⩽ C_3∑_| j-k|⩾ 2(λ/1 - c_2)^| j-k| (1 - c_2)^| j-k| y_j ⩽ C_3 ( λ/1 - c_2)^2∑_| j-k|⩾ 2 (1 - c_2)^| j-k| y_j.
 Continuing, using (<ref>) to bound y_j, we get 

    ∑_| j-k|⩾ 2 (1 - c_2)^| j-k| y_j ≪γ^1/q^'(1 - q^'/2)∑_| j-k|⩾ 2 (1 - c_2)^| j-k| y_j^q^'/2   ≪γ^1/q^'(1 - q^'/2)( ∑_j ≠ k (1 - c_2)^2 | j-k|)^1/2( ∑_j ≠ k y_j^q^')^1/2
       ≪γ^1/q^'( ∑_j ≠ k (1 - c_2)^2 | j-k|)^1/2.

Computing this geometric series, we obtain the overall bound 
    ∑_2≪_c_2,C_3γ^1/q^'λ^2 .
 An identical argument yields the same bound for ∑_3. 


Bound for ∑_4. From (<ref>) we immediately get ∑_4 ≪_C_3γ^1/q^'λ. 


Bound for ∑_5. Arguing similarly to the ∑_1 case, we have 
    ∑_5⩽∑_i ≠ k x_iy_i ≪γ^2/q^' (1 - q^'/2)∑_i ≠ k (x_i y_i)^q^'/2≪γ^2/q^' - 1( ∑_i ≠ k x_i^q^')^1/2( ∑_j ≠ k y_j^q^')^1/2≪γ^2/q^'.
 

Bound for ∑_5 + ∑_6. By the fact that sup_i x_i y_i = 1 - γ, we have 
    ∑_5 + ∑_6⩽∑_i x_i y_i ⩽ (1 - γ)^1 - q^'/2∑_i (x_i y_i)^q^'/2⩽ (1 - γ)^1 - q^'/2⩽ 1 - (1 - q^'/2) γ,
 where again we used Cauchy–Schwarz. 


Putting everything together we have 

    1 = ∑_n=1^6 ∑_n   ⩽ 1 - (1 - q^'2) γ + O_c_2,C_3(γ^1/q^'λ).

Since q > 2, we have q^' <2. Rearranging the above, and using 1 - 1/q^' = 1/q, we get 

    γ≪_c_2,C_3,qλ^q.

Finally, 
    ∑_| i-k| + | j-k|⩾ 2 m(i,j)    = ∑_1 + ∑_2 + ∑_3 + ∑_5≪_c_2,C_3γ^2/q^' + γ^1/q^'λ^2.

Substituting the bound (<ref>) for the γ terms in the above, we obtain the claimed bound.

We now apply Lemma <ref> to the bound given in Lemma <ref>. In this case, λ = p^-1/2 + ε, x_i = (α_i)^1/2 + ε, y_j = (β_j)^1/2 + ε, q = 2/1 - 2 ε, q^' = 2/1 + 2 ε, c_1 = 1000^-1_[p ⩽ p_0(ε)], and C_3 = e. Finally, since ε < 2/5 we may take c_2 = 1 - 2^-1/2 + 2/5 = 1 - 2^-1/10. Extending x_i, y_j, m(i,j) to negative integers by extending by 0, and since ∑_i α_i = ∑_j β_j = 1, these sequences satisfy the hypotheses ‖ x‖_ℓ^q^'(ℤ) = ‖ y ‖_ℓ^q^'(ℤ) = 1.

The first conclusion of Lemma <ref> then implies that 
    1000^-1_[p ⩽ p_0(ε)] = c_1 ⩾c_2/1 + (2C_3 - 1) λ⩾c_2/2 C_3⩾1 - 2^-1/10/ 2e  > 1/1000.
 Therefore p > p_0(ε). Next, we have the existence of some k_p ∈ℤ_⩾ 0 such that 
    ∑_| i-k_p| + | j-k_p|⩾ 2 m(i,j) ≪_ελ^2q/q^' + λ^2 + q/q^' = p^-1 - 2ε + p^-3/2 + ε⩽ p^-1 - 2 ε + p^-11/10
 as ε⩽ 2/5. It is at this point in the argument where we see the importance of having ε bounded away from 1/2, so that both these exponents are strictly less than -1. 

By considering all primes p ∈𝒫_ψ,θ (which we have shown must all be at least p_0(ε)), and taking the union bound, we conclude that 

    μ_ψ,θ^f,g( {(v,w) ∈ℰ:  ∃ p ∈𝒫_ψ,θ s.t. |ν_p(v) - k_p | + |ν_p(w) - k_p|⩾ 2})
       ≪_εμ_ψ, θ^f,g(ℰ) ∑_p > p_0(ε) (p^-1 - 2 ε + p^-11/10).

Since p_0(ε) is sufficiently large, we conclude that 

    μ_ψ,θ^f,g( {(v,w) ∈ℰ:  ∃ p ∈𝒫_ψ,θ s.t. |ν_p(v) - k_p | + |ν_p(w) - k_p|⩾ 2}) <μ_ψ, θ^f,g(ℰ)/2.



We now construct ℰ^'. Let N = ∏_p ∈𝒫_ψ,θ p^k_p, and begin by considering 
    ℰ^*: = {(v,w) ∈ℰ:  for all primes  p,  |ν_p(v/N)| + |ν_p(w/N)|⩽ 1}.
 Let V^*: = ℰ^*|_V and W^*: = ℰ^*|_W. Since |ν_p(v/N)| + |ν_p(w/N)| = 0 for all primes p ∉𝒫_ψ,θ and all (v,w) ∈ V × W, the bound (<ref>) implies 

    μ_ψ,θ^f,g(ℰ^*) ⩾μ_ψ, θ^f,g(ℰ)/2   > 1/2· 1000^P_ψ,θ(ε)( μ_ψ^f(V) μ_θ^g(W) e^-Ct)^1/q^'
       ⩾1/2· 1000^P_ψ,θ(ε)( μ_ψ^f(V^*) μ_θ^g(W^*) e^-Ct)^1/q^'.

Now define ℰ^'⊂ℰ^* to be minimal (with respect to inclusion) 
such that property (1) of Proposition <ref> is satisfied. By construction we have that ℰ^' exists (since ℰ^* is finite and satisfies property (1) itself). ℰ^' also satisfies property (3) (since ℰ^* satisfies property (3)). It remains to demonstrate property (2). 

Indeed, letting V^': = ℰ^' |_V and  W^': = ℰ^' |_W, suppose for contradiction that there exists some v ∈ V^' for which 

    μ_θ^g(Γ_ℰ^'(v)) < 1/q^'μ_ψ,θ^f,g(ℰ^')/μ_ψ^f(V^').

(The case with the contradiction coming from some w ∈ W^' is identical). Consider 
    ℰ^new := ℰ^'∩ ((V^'∖{v}) × W^'),
 and define V^new: = ℰ^new |_V and W^new: = ℰ^new |_W. Since v ∈ V^' = ℰ^'|_V, there must be some w ∈ W^' such that (v,w) ∈ℰ^'
and thus |ℰ^new| < |ℰ^'|. Yet ℰ^new also satisfies property (1) of Proposition <ref>, contradicting the minimality of ℰ^'. Indeed, observe first that μ_ψ^f(V^new) ≠ 0, as otherwise 
    μ_ψ^f(v)μ_θ^g(Γ_ℰ^'(v)) = μ_ψ, θ^f,g(ℰ^'),
 contradicting the upper bound (<ref>). Then 

    μ_ψ,θ^f,g(ℰ^new)    = μ_ψ,θ^f,g(ℰ^') - μ_ψ^f(v) μ_θ^g(Γ_ℰ^'(v)) 
       >  μ_ψ,θ^f,g(ℰ^') - μ_ψ^f(v) /q^'μ_ψ,θ^f,g(ℰ^')/μ_ψ^f(V^')
       =μ_ψ,θ^f,g(ℰ^')/μ_ψ^f(V^')μ_ψ^f(V^new)(1 + μ_ψ^f(v)/q μ_ψ(V^new))
       ⩾μ_ψ,θ^f,g(ℰ^')/μ_ψ^f(V^')μ_ψ^f(V^new)(1 + μ_ψ^f(v)/μ_ψ^f(V^new))^1/q
       = μ_ψ,θ^f,g(ℰ^') ( μ_ψ^f(V^new)/μ_ψ^f(V^'))^1/q^'.

Hence 
    μ_ψ,θ^f,g(ℰ^new) (μ_ψ^f(V^new)μ_θ^g(W^new))^-1/q^' > μ_ψ,θ^f,g(ℰ^') (μ_ψ^f(V^')μ_θ^g(W^new))^-1/q^'⩾μ_ψ,θ^f,g(ℰ^') (μ_ψ^f(V^')μ_θ^g(W^'))^-1/q^'.
 Since ℰ^' satisfies property (1) of Proposition <ref> by construction, we conclude that ℰ^new also satisfies property (1). But this contradicts the minimality of ℰ^'. 

Therefore ℰ^'⊂ℰ satisfies properties (1), (2) and (3), and Proposition <ref> is resolved. 



§ ANATOMY LEMMAS


In this section, we present some statements concerning the anatomic conditions occurring in the statement of Theorem <ref>. We remark that while Lemma <ref> essentially appears in <cit.>, Lemma <ref> is a new ingredient in our approach.

[Unweighted anatomy property]

For any real x,t ⩾ 1 and c ∈ℝ, 

    |{n ⩽ x:  ∑_p ⩾ t 
     p | n1/p⩾ c }|≪ x e^-100ct.



This is <cit.>. It is stated there for c ∈ (0,1). However, the proof does not use the upper bound c<1, and if c⩽ 0 the statement is trivial.

[Divisor anatomy property]

Let f be a non-negative multiplicative function that satisfies (<ref>). Then for any M ∈ℕ, real t ⩾ 1 and c ∈ℝ, 
    ∑_mn = M 
    ∑_p ⩾ t 
     p| m1/p⩾ c f(n) ≪ Me^-100ct.



If c<0 the statement is trivial as ∑_n| M f(n) ⩽ M, so assume that c⩾ 0. Then 

    ∑_mn = M 
    ∑_p ⩾ t 
     p| m1/p⩾ c f(n)    ⩽exp(-100ct) ∑_mn = Mexp(∑_p ⩾ t 
     p| m100 t/p)f(n)
       = e^-100ct( ∏_p < t 
     p| M (1 ⋆ f)(p^ν_p(M))) ( ∏_p ⩾ t 
     p| M(f(p^ν_p(M)) + e^100 t/p (1 ⋆ f)(p^ν_p(M) - 1))
       =Me^-100ct( ∏_p < t 
     p| M(1 ⋆ f)(p^ν_p(M))/p^ν_p(M)) ( ∏_p ⩾ t 
     p| M( (1 ⋆ f)(p^ν_p(M))/p^ν_p(M) + (e^100 t/p - 1) (1 ⋆ f)(p^ν_p(M) - 1)/p^ν_p(M))
       ⩽ Me^-100ct∏_p ⩾ t 
     p | M( 1 + | e^100 t/p - 1 |/p).

Since 
    ∏_p ⩾ t(1 + | e^100t/p - 1|/p) ⩽∏_p ⩾ t(1 + O(t/p^2))⩽ e^ O(∑_p ⩾ tt/p^2)≪ 1,

the lemma is proved. 




§ PROOF OF PROPOSITION <REF>

Let ψ,θ,ε,C,t,f,g,ℰ^' be as in the statement of Proposition <ref>, and N be the natural number from property (3) of Proposition <ref> that ℰ^' satisfies. We will initially prove that 

    μ_ψ,θ^f,g(ℰ^') ≪ (μ_ψ^f(V^') μ_θ^g(W^') e^-25 Ct)^1/2,

where V^': = ℰ^' |_V and  W^': = ℰ^' |_W.
This is nearly in contradiction to property (1) of Proposition <ref> , except that the exponent is 1/2 rather than 1/2 + ε. There is a short final argument to deal with this point. 


 For each (v,w) ∈ V^'× W^', we define

    v^-   := ∏_p :  ν_p(v/N) = -1 p,      v^+  :=  ∏_p :  ν_p(v/N) = +1 p,
    
    w^-   := ∏_p :  ν_p(w/N) = -1 p,       w^+:=  ∏_p :  ν_p(w/N) = +1 p.

Since ℰ^' satisfies property (3), if (v,w) ∈ℰ^' we have that all four of v^-, v^+, w^-, w^+ are coprime, and 
    v = Nv^+/v^-,      w = N w^+/w^-.
 Therefore, as (v,w) ∈ℰ^t,C_ψ,θ, 
    ψ(v) ⩽(v,w)/w = 1/v^- w^+,     θ(w) ⩽(v,w)/v = 1/v^+ w^-.
 Let w_0 ∈ W^' maximise w_0^+, and let v_0(w) ∈Γ_ℰ^'(w) maximise v_0^+(w) (over Γ_ℰ^'(w)). By applying property (2) twice, we have 

    μ_ψ,θ^f,g(ℰ^')/(μ_ψ^f(V^') μ_θ^g(W^'))^1/2⩽ (q^')^1/2( μ_ψ,θ^f,g(ℰ^')/μ_ψ(V^'))^1/2μ_ψ^f(Γ_ℰ^'(w_0))^1/2⩽ q^'( ∑_v ∈Γ_ℰ^'(w_0)μ_ψ^f(v) μ_θ^g(Γ_ℰ^'(v)))^1/2.

Using the bounds 

    ψ(v) ⩽1/v^- w_0^+,     θ(w) ⩽1/v^+_0(w) w^-
 for  (v,w) ∈ℰ^' with (v,w_0) ∈ℰ^', we obtain 

    ∑_v ∈Γ_ℰ^'(w_0)μ_ψ^f(v) μ_θ^g(Γ_ℰ^'(v))    = ∑_v ∈Γ_ℰ^'(w_0)f(v) ψ(v)/v∑_w ∈Γ_ℰ^'(v) g(w) θ(w)/w
       ⩽1/w_0^+∑_w ∈ W^' g(w)/w w^-·1/v_0^+(w)∑_v ∈Γ_ℰ^'(w)f(v)/v v^-.


Since this is a sum over all pairs (v,w) ∈ℰ^'⊂ℰ^t,C_ψ,θ, and vw/(v,w)^2 = v^- v^+ w^- w^+, for every such pair we know that 
    ∑_ p ⩾ t 
     p | v^- v^+ w^- w^+1/p⩾ C.
 Hence either ∑_p ⩾ t:   p | v^-1/p⩾C/4 or similarly with p| v^+, p| w^- or p | w^+. Therefore 
    ∑_v ∈Γ_ℰ^'(w_0)μ_ψ^f(v) μ_θ^g(Γ_ℰ^'(v))  ⩽ S_1 + S_2 + S_3 + S_4,
 where 

    S_1 := 1/w_0^+∑_w ∈ W^' g(w)/w w^-·1/v_0^+(w)∑_v ∈Γ_ℰ^' (w)
    ∑_p ⩾ t 
     p | v^-1/p⩾C/4f(v)/v v^-,

and S_2, S_3, S_4 are similar expressions with the anatomy condition placed on p| v^+, p| w^-, and p| w^+ respectively. 


Bounding S_1: We bound the inner sum from (<ref>). Since v = v^+ ·N/v^- and v^+ ⩽ v_0^+(w), we can reparametrise v in terms of variables v^+ and v^- and obtain

    ∑_v ∈Γ_ℰ^' (w)
    ∑_p ⩾ t 
     p | v^-1/p⩾C/4f(v)/v v^-   ⩽∑_v^+ ⩽ v_0^+(w)∑_v^- | N 
    (v^-, v^+) = 1 
    ∑_p⩾ t 
     p | v^-1/p⩾C/4 f(v^+ ·N/v^-)/Nv^+.

We factorise the f term to remove the influence of v^+. Indeed, writing 
    N|_v^+: = ∏_p |(N,v^+) p^ν_p(N),
 we have 

    f(v^+ ·N/v^-)/Nv^+   =  f(v^+ · (N|_v^+) ·N/N|_v^+v^-)/v^+ · (N|_v^+) ·N/N|_v^+  = f(v^+ · (N|_v^+))/v^+ · (N|_v^+)·f(N/N|_v^+v^-)/N/N|_v^+⩽f(N/N|_v^+v^-)/N/N|_v^+.

For notational convenience, in the following we write N^+ for N/N|_v^+. In this notation, the right-hand side of (<ref>) is 

    ⩽∑_v^+ ⩽ v_0^+(w)( 1/N^+∑_v^- | N^+ 
    ∑_p⩾ t 
     p | v^-1/p⩾C/4 f(N^+v^-))⩽∑_v^+ ⩽ v_0^+(w)( 1/N^+∑_mn = N^+ 
    ∑_p ⩾ t 
     p | m1/p⩾C/4 f(n)) ≪ v_0^+(w) e^-25Ct,

by Lemma <ref>. Therefore, the right-hand side of expression (<ref>) is 
    ≪e^-25Ct/w_0^+∑_w ∈ W^'g(w)/w w^-≪e^-25Ct/w_0^+∑_w^+ ⩽ w_0^+∑_w^- | N 
    (w^-, w^+) = 1g(w^+ ·N/w^-)/N w^+≪ e^-25Ct,
 where the final step followed from the method we used to bound expression (<ref>), using (1 ⋆ g)(n) ⩽ n instead of Lemma <ref>. Hence S_1 ≪ e^-25Ct. 


Bounding S_2. We have 

    S_2: = 1/w_0^+∑_w ∈ W^'g(w)/w w^-·1/v_0^+(w)∑_ v ∈Γ_ℰ^'(w) 
    ∑_p ⩾ t 
     p| v^+1/p⩾C/4f(v)/v v^-.

We bound the inner sum. Once again using v = v^+ ·N/v^- and v^+ ⩽ v_0^+(w), we can reparametrise v in terms of variables v^+ and v^-. Using similar estimates as in the S_1 case, we derive

    ∑_ v ∈Γ_ℰ^'(w) 
    ∑_p ⩾ t 
     p| v^+1/p⩾C/4f(v)/v v^-⩽∑_v^+ ⩽ v_0^+(w) 
    ∑_p ⩾ t 
     p| v^+1/p⩾C/4∑_v^- | N 
    (v^-, v^+) = 1 f(v^+ ·N/v^-)/N v^+   ⩽∑_v^+ ⩽ v_0^+(w) 
    ∑_p ⩾ t 
     p| v^+1/p⩾C/4( 1/N^+∑_v^- | N^+ f( N^+v^-)) 
       = ∑_v^+ ⩽ v_0^+(w) 
    ∑_p ⩾ t 
     p| v^+1/p⩾C/4 1 ≪ v_0^+(w) e^-25Ct,

where the final step uses Lemma <ref> rather than Lemma <ref>. The bound S_2 ≪ e^-25Ct then follows as in the S_1 case. 


Bounding S_3, S_4. The bound S_3 ≪ e^-25 Ct follows by an analogous argument to the one for bounding S_1, with the non-trivial application of Lemma <ref> now made on the w sum instead of the v sum; the bound S_4 ≪ e^-25 Ct follows by an analogous argument to the one for bounding S_2, with the non-trivial application of Lemma <ref> made on the w sum instead of the v sum. 


Therefore S_1 + S_2 + S_3 + S_4 ≪ e^-25 Ct. Substituting this bound into (<ref>) and using q^' < 2, we have 
    μ_ψ,θ^f,g(ℰ^')/(μ_ψ^f(V^') μ_θ^g(W^'))^1/2≪ e^-25/2 Ct
 resolving equation (<ref>).  



Let ℰ^' be as in the statement. We will show that, provided p_0(ε) is sufficiently large, 

    μ_ψ,θ^f,g(ℰ^') ⩽ (μ_ψ^f(V^')(μ_θ^g(W^') e^-Ct)^1/q^'.
 This will imply that ℰ^' does not satisfy property (1) of Proposition <ref>, and complete the proof. 

To deal with a trivial case, if C<0 then we may replace this value with C=0 whilst still preserving ℰ^'⊂ℰ^ψ,θ_t,C and strengthening the conclusion (<ref>). So we may suppose that C ⩾ 0. We may also suppose that p_0(ε) (and therefore also P_ψ,θ(ε)) is sufficiently large. Now suppose that 
    μ_ψ(V^') μ_θ(W^') ⩽1000^q P_ψ,θ(ε)/2^q e^-Ct q/q^' .
 Then trivially we have 
    μ_ψ,θ^f,g(ℰ^') ⩽μ_ψ^f(V^') μ_θ^g(W^') ⩽1/2· 1000^P_ψ,θ(ε)  (μ_ψ^f(V^') μ_θ^g(W^') e^-Ct)^1/q^',
 contradicting property (1) of Proposition <ref> and resolving Proposition <ref>. We may therefore assume that (<ref>) fails. 

Using (<ref>), for some absolute constant K we have

    μ_ψ,θ^f,g(ℰ^')    ⩽ K(μ_ψ^f(V^') μ_θ^g(W^') e^-25Ct)^1/2
       ⩽ K(μ_ψ^f(V^') μ_θ^g(W^') e^-25Ct)^1/2·(  2^q e^Ct q/q^'/1000^q P_ψ,θ(ε)·μ_ψ^f(V^') μ_θ^g(W^'))^ε
       ⩽ ( μ_ψ^f(V^') μ_θ^g(W^'))^1/2 + ε e^-Ct(25/2 - εq/q^')
       ⩽ ( μ_ψ^f(V^') μ_θ^g(W^') e^-Ct)^1/2 + ε

since ε⩽2/5, by a short computation and P_ψ,θ can be chosen sufficiently large. This proves (<ref>), and thus completes the whole argument. 




§ THE QUANTITATIVE APPLICATION


In this section, we deduce Corollary <ref> on quantitative metric Diophantine approximation. Along the way we will derive improved (and generalised) versions of  <cit.>. 
This is the second moment estimate we will prove, which improves upon  <cit.>:
[Improved second moment bound]

For any ψ:ℕ→ [0,1/2], let 𝒜_n, Ψ(N) be defined as in (<ref>) and (<ref>). Then for any ε > 0, we have
    
    ∑_n,m=1^N λ (𝒜_n∩𝒜_m) = Ψ(N)^2(1 + O_ε(exp(-log(Ψ(N))^1/2 -ε)).





We can assume that Ψ(N) →∞ since otherwise, the statement holds trivially.
    We follow a standard argument, adapting <cit.>.
Note that ∫_0^1 S(N,α)  dα = Ψ(N), and by Corollary <ref> we have for any ρ > 0,

    ∫_0^1 (S(N,α) - Ψ(N) )^2 dα    =    ∑_n,m ⩽ Nλ( 𝒜_n∩𝒜_m) - Ψ(N)^2 = O_ρ(Ψ(N)^2/F_ρ(Ψ(N))),

where F_ρ(x) := exp(log(x)^1/2-ρ). 
Now let 0 < δ < 1/100 be arbitrary. We define 

    N_k = min{N ∈ℕ: Ψ(N) ⩾exp((log k)^c(δ))  },      k ⩾ 1,

where c(δ) := (1/2-δ)^-1 > 1.
Furthermore, let

    ℬ_k = {α∈ [0,1]: | S(N_k,α) - Ψ(N_k) | ⩾Ψ(N_k)/F_δ(Ψ(N_k))}.

By Chebyshev's inequality and applying (<ref>) with ρ = δ/3, we have

    λ( ℬ_k ) ≪_δF_δ(Ψ(N_k))^2/F_δ/3(Ψ(N_k)))≪_δ
    (F_δ/2(Ψ(N_k)))^-1≪_δ k^-2.

This implies ∑_k=1^∞λ(ℬ_k) < ∞, and thus the first Borel–Cantelli Lemma implies that almost all α are contained in at most finitely many sets ℬ_k. Thus for almost all α, there exists k_0(α) such that for all k ⩾ k_0(α),

    | S(N_k,α) - Ψ(N_k) | ⩽Ψ(N_k)/F_δ(Ψ(N_k)).

Since ψ⩽ 1/2 by assumption, we have Ψ(N_k+1) ⩽exp((log (k+1))^c(δ)) + 1/2, and so


    Ψ(N_k+1)/Ψ(N_k)   ⩽exp((log (k+1))^c(δ) - (log k)^c(δ)) + O(1/Ψ(N_k))
       ⩽exp(O_δ((log k)^c(δ)/klog k)) + O(1/Ψ(N_k))
    
       ⩽ 1 + O_δ((log k)^c(δ)-1/k)
    
       ⩽ 1 + O_δ(1/F_2δ(Ψ(N_k+1))).

Here we used log(1 + x) ⩽ x, e^x = 1 + O(x) when x ∈ (0,1], binomial approximation and c(δ) > 1.

Therefore, for any N with N_k ⩽ N ⩽ N_k+1, using (<ref>), we have

    S(N,α) ⩽ 
    S(N_k+1, α )
       ⩽Ψ(N_k+1) + O(Ψ(N_k+1)/F_2δ(Ψ(N_k+1)))
    
       =Ψ(N) + O(Ψ(N_k+1)/F_2δ(Ψ(N_k+1)))
       = Ψ(N) + O(Ψ(N)/F_2δ(Ψ(N))).

By an analogous argument we obtain a matching lower bound from the inequality S(N,α) ⩾ S(N_k,α) . Finally we obtain that for all N ⩾ N_0(α),

    | S(N,α)- Ψ(N) | = O (  Ψ(N)/F_2δ(Ψ(N))).

By choosing ε = δ/2, this proves Corollary <ref>. 

It remains to prove Corollary <ref>. To do so, we record the following consequences of Theorem <ref>. Here and throughout, ψ:[1,N]∩ℕ→ [0,1/2] is the finitely supported function from Corollary <ref>, and D(n,m) = D_ψ,ψ(n,m) = max(mψ(n),mψ(n))/(n,m) as before. For the sake of readability, we define 
    L_x (n,m) := ∑_p |nm/(n,m)^2, 
     p ⩾ x1/p.



[GCD condition bound]

    For any s,ε > 0, let 
    
    ℰ_s := 
        {(n,m): 1 ⩽ n,m⩽ N, D(n,m) ⩽Ψ(N)/s}.

    Then we have
    
    ∑_(n,m) ∈ℰ_sψ(q)φ(q)/qψ(r)φ(r)/r≪_εΨ(N)^2/s^1-2ε.


This improves over <cit.>, which had a power of s^1/5 in place of s^1 - 2ε. This followed from the fact that ε = 2/5 corresponds to the approach considered in Koukoulopoulos–Maynard <cit.>. We remark that this improvement is not vital to the application to Corollary <ref>, however. 

    Apply Theorem <ref> with f=g=φ, t=1, C=0, and functions ψ(q) = θ(q) = ψ(q)s/Ψ(N). Then D_ψ, θ(n,m) =  D(n,m) s/Ψ(N)⩽ 1.




    Let s,t,A ⩾ 0 fixed, let η∈ (0,1/2) and let
    
    ℰ_s,t,A := 
        {(n,m): 1 ⩽ n,m⩽ N: D(n,m) ⩽ s Ψ(N), L_t(n,m) ⩾1/A}.

    Then we have
    
    ∑_(n,m) ∈ℰ_s,t,Aψ(q)φ(q)/qψ(r)φ(r)/r≪_ηΨ(N)^2s^1/2 + ηe^-(1 - η)t/A.




    Apply Theorem <ref> with ψ(q) = θ(q) = ψ(q)/sΨ(N), C = 1/A, ε = 1/2 - η. Technically, we only proved Theorem <ref> when ε∈ (0,2/5], but we remarked that the method of proof proceeds unaltered if ε∈ (0,1/2), at the cost of increasing 1000 to a larger constant. We remark that in order to prove Corollary <ref>, we do not need the full strength of this result; in fact, every η > 0 suffices.


We note that without the anatomic condition on L_t for t ⩽ A, when s ⩾ 1 the bound above is worse than the trivial estimate. However, in the application below, the anatomic condition that determines t,A depends on s and is of (much) faster decay than the polynomial growth in s in the first part. In the special case of <cit.> (see <cit.> for the detailed formulation and definitions), we improve from Ψ(N)^2/F(t)^1/2 to Ψ(N)^2/e^(F(t)^3/4-δ) (for any δ > 0), i.e. we improve from polynomial to exponential decay.


We follow again the ideas of <cit.> which are a refined version of the proof in <cit.>. In our setting, the estimates are even more delicate, and therefore we provide the full deduction. 

Fix ε∈ (0,1/100], set δ = ε/2 and let

    F_ρ(x):=exp ( (logΨ(x))^1/2-ρ)

for 0 < ρ < 12. We can assume that Ψ(N) is larger than any prescribed constant, since otherwise the statement follows trivially.
In the subsequent estimates, we will frequently use Mertens' Theorem in the following two forms (for the second formulation, see <cit.>):


    ∑_p ⩽ x1/p   ⩽loglog x + O(1),
    ∃ a > 0: ∑_x ⩽ p ⩽ y1/p   = loglog y - loglog x + O(exp(-a √(log x))).

Furthermore, we will use at various places the obvious implication

    L_s(n,m) > L_t(n,m) ⇒ s < t.



We partition the index set [1,N]^2 into the sets

    ℰ^1   = { (n,m) ∈ [1,N]^2   :   m=n }, 
    ℰ^2   = { (n,m) ∈ [1,N]^2   :   n ≠ m,    D(n,m) ⩽√(Ψ(N)),    L_Ψ(N)(n,m) ⩽ 1 }, 
    
    ℰ^3   = { (n,m) ∈ [1,N]^2   :   n ≠ m,    D(n,m) ⩽√(Ψ(N)),    L_Ψ(N)(n,m) > 1 }, 
    
    ℰ^4   = { (n,m) ∈ [1,N]^2   :   n ≠ m,    D(n,m) > √(Ψ(N)),    L_F_δ(D(n,m)) (n,m) ⩽4/F_2δ(Ψ(N))}, 
    ℰ^5   = { (n,m) ∈ [1,N]^2   :   n ≠ m,    D(n,m) > √(Ψ(N)),    L_F_δ(D(n,m)) (n,m) > 4/F_2δ(Ψ(N))}.



The contribution of ℰ^1 is clearly negligible:

    ∑_(n,m) ∈ℰ^1λ (𝒜_n∩𝒜_m) = ∑_n=1^N λ (𝒜_n) = Ψ (N).

Now we consider ℰ^2. For any (n,m) ∈ℰ^2, the condition L_Ψ(N)(n,m) ⩽ 1 together with (<ref>) ensures that

    ∏_p |nm/ (n,m)^2( 1 + 1/p-1) 
       ≪∏_p |nm/ (n,m)^2( 1 + 1/p) 
       ⩽exp( ∑_p<Ψ(N)1/p + ∑_p |nm/ (n,m)^2, 
     p ⩾Ψ(N)1/p) 
       ≪exp ( loglogΨ (N) + O(1)) 
       ≪ (logΨ (N))^2.

The overlap estimate in the form of (<ref>) shows that for any (n,m) ∈ℰ^2,

    λ (𝒜_n∩𝒜_m) ≪λ (𝒜_n) λ (𝒜_m) (logΨ (N))^2 .

Applying Proposition <ref> with s=√(Ψ(N)) and ε = 14 leads to

    ∑_(n,m) ∈ℰ^2λ (𝒜_n∩𝒜_m) ≪Ψ(N)^2/Ψ(N)^1/4,

which is also negligible. 

Next we consider ℰ^3. 
Writing r(j) = exp(exp(j)), and given (n,m) ∈ℰ^3, let j(n,m) be the maximal integer j such that L_r(j)(n,m) >1. This implies
L_r(j+1)(n,m) <1, and since by (n,m) ∈ℰ^3 we have L_Ψ(N) > 1, (<ref>) implies that j(n,m) ⩾⌊loglogΨ (N) ⌋. 
Hence (<ref>) implies

    ∏_p |nm/ (n,m)^2( 1 + 1/p-1)    ≪exp( ∑_p |nm/ (n,m)^2, 
     p < r(j+1)1/p + ∑_p |nm/ (n,m)^2, 
     p ⩾ r(j+1)1/p) 
       ≪exp( loglog (r(j+1)) + O(1) ) 
       ≪exp (2j) = (log r(j))^2 .

Thus the overlap estimate (<ref>) gives

    λ (𝒜_n∩𝒜_m) ≪λ (𝒜_n) λ (𝒜_m) (log r(j))^2 ,

and applying Proposition <ref> with s=1, t = r(j), A = 1 leads to

    ∑_(n,m) ∈ℰ^3λ (𝒜_n∩𝒜_m)    = ∑_j ⩾⌊loglogΨ (N) ⌋∑_(n,m) ∈ℰ^3, 
     j(n,m)=jλ (𝒜_n∩𝒜_m) 
       ≪Ψ(N)^2∑_j ⩾⌊loglogΨ (N) ⌋ (log r(j))^2 exp(-r(j)/2) 
       ⩽Ψ(N)^2∫_x = loglogΨ (N)/2^∞ (log r(x))^2 exp(-r(x)/2) dx 
       ≪Ψ(N)^2∫_y = r(loglogΨ (N)/2)^∞log y/y e^-y/2 dy
       ≪Ψ(N)^2/Ψ(N)

by a considerable margin.


Now we consider ℰ^4. For any (n,m) ∈ℰ^4,

    ∏_p |nm/ (n,m)^2, 
     p>F_δ(D(n,m))( 1+1/p-1) ⩽exp( 2 L_F_δ(D(n,m)) (n,m) ) = 1+O ( 1/F_2δ(Ψ(N))) .

The overlap estimate (<ref>) with ρ = δ thus gives

    λ (𝒜_n∩𝒜_m) ⩽λ (𝒜_n) λ (𝒜_m) ( 1 + O ( 1/F_2δ(Ψ(N))) )

and hence,

    ∑_(n,m) ∈ℰ^4λ (𝒜_n∩𝒜_m) ⩽Ψ (N)^2 + O ( Ψ(N)^2/F_2δ(Ψ(N))).


Finally, we consider ℰ^5. 
Defining for shorter notation H(x) := exp(F_5δ(x)), we note that any (n,m) ∈ℰ^5 has to lie in at least one of the following sets:


    ℱ^1 := {   (n,m) ∈ [1,N]^2: 
    √(Ψ(N))⩽ D(n,m) < H(Ψ(N)), 
    
       L_F_δ(D(n,m))(n,m) ⩾4/F_2δ(Ψ(N)), L_√(D(n,m))(n,m) ⩽ 10
    },
    ℱ^2 := {   (n,m) ∈ [1,N]^2: 
    D(n,m) > H(Ψ(N)),  L_F_δ(D(n,m))(n,m) ⩾4/F_2δ(Ψ(N))},
    ℱ^3 := {   (n,m) ∈ [1,N]^2:  D(n,m) > √(Ψ(N)),  L_√(D(n,m))(n,m) ⩾ 10
    }.


We start to treat ℱ^1.
By (<ref>) we have for every (n,m) ∈ℱ^1 that

    λ(𝒜_n∩𝒜_m) ≪λ(𝒜_n)λ(𝒜_m).

Furthermore, using D(n,m) ⩾√(Ψ(N)), we have 
    L_F_δ(√(Ψ(N)))(n,m) ⩾ L_F_δ(D(n,m))(n,m) ⩾4/F_2δ(Ψ(N)).
 An application of Proposition <ref> with s = H(Ψ(N)), t = F_δ(√(Ψ(N))),
A = F_2δ(Ψ(N))/4 leads to


    ∑_(n,m) ∈ℱ^1λ(𝒜_n∩𝒜_m) ≪Ψ(N)^2 H(Ψ(N))exp(- F_δ(√(Ψ(N)))/F_2δ(Ψ(N))) ≪Ψ(N)^2/exp(F_3δ(Ψ(N)))≪Ψ(N)^2/Ψ(N).


Next, we treat ℱ^2. For simpler notation, let t(i) := expexp(i/F_2δ(Ψ(N))).
For any (n,m) ∈ℱ^2, let i(n,m) be the maximal integer i such that

    L_F_δ(t(i))(n,m) > 2/F_2δ(Ψ(N)).
 Note that

    L_F_δ( H(Ψ(N)) (n,m) ⩾ L_F_δ(D(n,m)) (n,m) > 2/F_2δ(Ψ(N)),

but

    L_F_δ(t(i+1))(n,m) < 2/F_2δ(Ψ(N)),

thus by (<ref>) we have


    i(n,m)    ⩾1/2F_2δ(Ψ(N))loglog H(Ψ(N))
    ⩾ F_2δ(Ψ(N))(log F_6δ(Ψ(N))).


Let (n,m) ∈ℱ^2 such that i(n,m)=i. 
Using (<ref>) and (<ref>) shows that

    ∏_p |nm/ (n,m)^2( 1+1/p-1)    ≪exp( ∑_p |nm/ (n,m)^2, 
     p < F_δ(t(i+1))1/p + ∑_p |nm/ (n,m)^2, 
     p ⩾ F_δ(t(i+1))1/p) 
       ≪exp(loglog F_δ(t(i+1)) + O(1)) 
       ≪exp( i/F_2δ(Ψ(N))).
 The overlap estimate (<ref>) thus gives

    λ (𝒜_n∩𝒜_m) ≪λ (𝒜_n) λ (𝒜_m) exp( i/F_2δ(Ψ(N))) .


Note that (<ref>) gives

    ∑_F_δ(t(i)) ⩽ p ⩽ F_δ(t(i+1))1/p   ⩽loglog F_δ(t(i+1)) - loglog F_δ(t(i)) + O(
    exp(-a √(log F_δ(t(i)))))
       ⩽2/F_2δ(Ψ(N)).

Here we used (<ref>), the mean value theorem and that for large enough x, h'(x) ⩽ 1 where h(x) := loglog F_δ(exp(exp(x/F_2δ(Ψ(N))))).
Combined with (<ref>), it follows that

    L_F_δ(t(i)) (n,m) ⩽2/F_2δ(Ψ(N)) + 2/F_2δ(Ψ(N)) = 4/F_2δ(Ψ(N)),

and since (n,m) ∈ℱ^2 implies per definition L_F_δ(D(n,m))(n,m) ⩾4/F_2δ(Ψ(N)), (<ref>) shows that
D(n,m) ⩽ t(i). Therefore, Proposition <ref> with 
s = t(i), T = F_δ(t(i)) and A = F_2δ(Ψ(N))/4 gives 


    ∑_(n,m) ∈ℰ^5, 
     i(n,m)=iλ (𝒜_n∩𝒜_m)    ≪Ψ(N)^2exp( 2i/F_2δ(Ψ(N)))t(i) exp(-F_δ(t(i))/F_2δ(Ψ(N))).

Note that by (<ref>), t(i) ⩾Ψ(N) and thus, the above is bounded by

    Ψ(N)^2exp( 2i/F_2δ(Ψ(N)))t(i)exp(-F_δ(t(i))/F_2δ(t(i)))
    ≪    Ψ(N)^2exp( 2i/F_2δ(Ψ(N)))t(i)exp(-F_2δ(t(i)))
    
    =     Ψ(N)^2log(t(i))^2t(i)exp(-F_2δ(t(i)))
    
    ≪    Ψ(N)^2 t(i)^2exp(-F_3δ(t(i))).


Summing over all possible values of i (see (<ref>)), we obtain

    ∑_(n,m) ∈ℱ^2λ (𝒜_n∩𝒜_m)    ≪Ψ(N)^2∑_i ⩾ F_2δ(Ψ(N))(log F_6δ(Ψ(N))) t(i)^2exp(-F_3δ(t(i))) 
       ≪Ψ(N)^2∫_ F_2δ(Ψ(N))(log F_7δ(Ψ(N)))^∞ t(x)^2exp(-F_3δ(t(x))) dx
    
       ≪Ψ(N)^2∫_exp(F_7δ(Ψ(N)))^∞ y exp(-F_3δ(y)) dy
       ≪Ψ(N)^2/Ψ(N) .


Thus we are left to treat ℱ^3. Let r(j) = exp(exp(j)), and for (n,m) ∈ℱ^3, let j(n,m) be the maximal integer j such that L_√(r(j))(n,m) >5.
Since D(n,m) ⩾√(Ψ(N)), (<ref>) implies j(n,m) ⩾loglogΨ (N)/2. Let (n,m) ∈ℱ^3 with j(n,m)=j. By definition, L_√(r(j+1))(n,m) ⩽ 5, hence (<ref>) implies

    ∏_p |nm/ (n,m)^2( 1 + 1/p-1)    ≪exp( ∑_p |nm/ (n,m)^2, 
     p < √(r(j+1))1/p + ∑_p |nm/ (n,m)^2, 
     p ⩾√(r(j+1))1/p) 
       ≪exp( loglog√(r(j+1)) + O(1) ) 
       ≪exp (2j) = (log r(j))^2 .

Thus the overlap estimate gives

    λ (𝒜_n∩𝒜_m) ≪λ (𝒜_n) λ (𝒜_m) (log r(j))^2.

By (<ref>), and another application of the mean value theorem, we obtain

    ∑_√(r(j))⩽ p ⩽√(r(j+1))1/p   ≤loglog r(j+1) - loglog r(j) + O(
    exp(-a √(log r(j))))⩽ 2.

Thus 

    L_√(r(j))(n,m) ⩽ 7,

hence D(n,m) ⩽ r(j). Applying Proposition <ref> with 
s = r(j), T = √(r(j)) and A = 1 gives similarly to (<ref>)

    ∑_(n,m) ∈ℱ^3λ(𝒜_n∩𝒜_m) 
    ≪Ψ(N).


Combining (<ref>) - (<ref>) and (<ref>)-(<ref>) finally shows that

    ∑_n,m=1^N λ (𝒜_n∩𝒜_m) ⩽Ψ(N)^2(1 + O_δ(exp(-log(Ψ(N))^1/2 -2δ))).

    Since δ = ε/2, this completes the proof.




§ THE STRUCTURE OF THE DUFFIN–SCHAEFFER COUNTEREXAMPLE


Here we review the structure of the counterexample to Khintchine's Theorem without monotonicity, given by Duffin and Schaeffer <cit.>; we then discuss the relationship between this example and the rest of the present paper. In brief, we will argue that:


  * Proposition <ref> shows that `any counterexample to the Duffin–Schaeffer conjecture must arithmetically resemble the Duffin–Schaeffer counterexample to Khintchine's Theorem without monotonicity';

  * Proposition <ref> is a generalisation of arguments from <cit.>, showing that any such counterexamples to Khintchine's Theorem without monotonicty fail to be counterexamples when a φ(q)/q weight is introduced. 

Since Proposition <ref> works provided f(n)/n and g(n)/n are 1-bounded multiplicative functions (in particular if f(n) ≡ g(n) ≡ n), a similar analysis may be possible for the setting of Khintchine's theorem directly. This is the subject of ongoing work of the first and third named authors. 



We start by recalling the Khintchine set-up. Translated to set-theoretic language,
Khintchine's Theorem asks under which conditions on ψ: ℕ→ [0,12] one has


    λ(lim sup_n →∞ E_n) = 1

where


    E_n:=  E_n(ψ) := ⋃_0 ⩽ a ⩽ n [ a/n - ψ(n)/n, a/n + ψ(n)/n] ∩ [0,1].

The condition 
∑_n ∈ℕψ(n) = 1/2∑_n ∈ℕλ(E_n) = ∞
is necessary, since otherwise an application of the first Borel–Cantelli Lemma proves that 
λ(lim sup_n →∞ E_n) = 0. If ∑_n ∈ℕψ(n) = ∞, one needs to have some approximate form of independence for the events E_n in order to be able to use the second Borel–Cantelli lemma and conclude that λ(lim sup_n →∞ E_n) = 1. Khintchine <cit.> showed that it sufficed to assume that nψ(n) was monotonically decreasing.
We remark that nowadays, it is well-known that Khintchine's Theorem is still true under the weaker assumption that ψ is non-increasing. We refer the reader to Harman's monograph <cit.>.

However Duffin and Schaeffer <cit.> observed that, following the trivial fact that a rational number can be written in various ways, these events can be highly dependent. Sometimes even the total dependence of the form E_n ⊆ E_m, n ≠ m takes place:
If n| m, then every fraction a/n can also be written as some b/m (since we are not assuming coprimality of numerator and denominator). Therefore, if ψ(m) is proportionally larger than ψ(n), every interval contributing to E_n is already contained in E_m.

To take this dependency to the extreme, one may pick highly composite numbers and include only their divisors in the support of ψ, trying to maximize the occurrences of E_n ⊆ E_m described above.
To formalize this, given (ε_k)_k ∈ℕ by ε_k = 2^-k >0, we construct finite, pairwise disjoint sets (V_k)_k ∈ℕ⊂ℕ such that ∑_v ∈ V_kλ(E_v) > 1 but
λ(⋃_v ∈ V_k E_v) < 2ε_k. We pick N_k = ∏_N_0(k) ⩽ p < N_1(k)p, where N_0(k) < N_1(k) ∈ℕ with N_0(k) = N_1(k-1); N_1(k) is chosen later to be sufficiently large. Define ψ_k: ℕ→ℝ_⩾ 0 by 

    ψ_k(n) = ε_k/d   if  n = N_k/d for some  d ∈ℕ, d ≠ N_k  dividing  N_k,
    
    0    otherwise,

and set ψ := ∑_k ∈ℕψ_k.
In this way, we obtain (by implicitly using the above mentioned property that rational numbers can be written in various ways) that

    λ( ⋃_n ∈ψ_k E_n) = 
    λ(⋃_n | N_k
    n ≠ 1E_n) = λ(E_N_k) = 2ε_k,
 but 
    ∑_n ∈ψ_kλ(E_n) = 
    ∑_n | N_k
    n ≠ 1λ(E_n) = 2ε_k ∑_d | N_k
    d ≠ N_k1/d =
    2ε_k∏_p ∈ [N_0(k),N_1(k)](1 + 1/p) - 2ε_k/N_k.

This can be made arbitrarily large when N_1(k) is chosen sufficiently large, so in particular larger than 1. Therefore, we have

    ∑_n ∈ℕψ(n) =1/2∑_k ∈ℕ∑_n | N_k,
    n ≠ 1λ(E_n) = ∞,

 but 
    λ(lim sup_n →∞E_n) ⩽lim sup_K_0 →∞∑_k ⩾ K_0λ(⋃_n | N_k,
    n ≠ 1 E_n) = 0.
 So this function ψ contradicts a naïve generalisation of Khintchine's Theorem to all approximation functions. 

If we change to the coprime setting considered in the Duffin–Schaeffer conjecture, clearly the issue of several representations of rational numbers disappears. Writing 
    𝒜_n: = ⋃_0 ⩽ a ⩽ n 
    (a,n) = 1[ a/n - ψ(n)/n, a/n + ψ(n)/n] ∩ [0,1]
 as in the introduction, and considering the same ψ_k from the Duffin–Schaeffer construction, we see  
    ∑_n ∈ψ_kλ(𝒜_n) = ∑_n| N_kλ(𝒜_n) = 2∑_n| N_kφ(n) ψ(n)/n⩽ 2∑_n | N_kφ(n) ·ε_k/N_k/n/n = 2ε_k/N_k∑_d | N_kφ(d) = 2ε_k,

thus ∑_n ∈ℕλ(𝒜_n) = 2∑_n ∈ℕψ(n)φ(n)/n⩽ 2∑_k ∈ℕε_k < ∞. Since ∑_n ∈ℕλ(𝒜_n) is convergent, the construction ψ does not lead to a counterexample to the Duffin–Schaeffer conjecture. 


There are similarities between this phenomenon, as expressed in the calculation (<ref>), and the proof of Proposition <ref>. To demonstrate the point, rather than the hypotheses of Proposition <ref> suppose that a slightly stronger version of property (3) from Proposition <ref> holds: take ψ: ℕ→ [0,1/2] with finite support and suppose there exists some N such that for all non-equal v,w ∈ψ and for all primes p one has |ν_p(v/N) |  + |ν_p(w/N) |⩽ 1. To consider the appropriate scaling, suppose also that for all v,w ∈ψ one has D_ψ,ψ(v,w) ⩽ε_k (as opposed to D_ψ,ψ(v,w) ⩽ 1). This is similar to the hypotheses of Proposition <ref>, at least morally. Then as in the proof of (<ref>), in particular expression (<ref>), for each v ∈ψ there exist coprime square-free v^-, v^+ with v^- | N such that v = N v^+/v^- and ψ(v) ⩽_k/v^- v_0^+ (where v_0^+ = max{ v^+:    v ∈ψ}). If v^+ ≡ 1 for all v, then in fact v = N/v^- and ψ(v) ⩽_k/v^-, and so ψ is bounded above by the Duffin–Schaeffer examples ψ_k described above in (<ref>). Thus immediately (<ref>) implies that ∑_n ∈ψλ(𝒜_n) ⩽ 2ε_k, and moreover this happens `for the same reasons' as the Duffin–Schaeffer example above fails to contradict their conjecture. 

The techniques from our proof of (<ref>) resolve the case when v^+ varies. Indeed, in general we have

    1/2∑_n ∈ψλ(𝒜_n) = ∑_n ∈ψφ(n) ψ(n)/n⩽_k/v_0^+∑_v ∈ψφ(v)/v v^-   ⩽_k/v_0^+∑_ v^+,v^- ∈ℕ
     v^+ ⩽ v_0^+ 
    
    v^- | N 
    (v^+,v^-) = 1φ(v^+ ·N/v^-)/Nv^+
       ⩽_k/v_0^+∑_v^+ ⩽ v_0^+1/N^+∑_v^- | N^+φ(N^+v^-) ⩽_k,
 where N^+ = N/(N,v^+). This argument is similar to the one used for the bound (<ref>). 


There are further windows into the relationship between Duffin–Schaeffer counterexamples and Proposition <ref>. Indeed, there is a refinement of the Duffin–Schaeffer counterexample, in which the component functions ψ_k are defined by 

    ψ_k(n) = ε_k/p   if  n = N_k/p for some prime  p | N_k,
    
    0    otherwise.
 This still provides a counterexample to Khintchine's Theorem without monotonicity (since ∑_p 1/p = ∞), but we observe that this example satisfies |ν_p(v/N_k)| + |ν_p(w/N_k)|⩽ 1 for all v ≠ w for which v,w ∈ψ_k. So in fact Proposition <ref> is more precisely saying that any counterexample to Theorem <ref> must contain within a structure similar to the refined Duffin–Schaeffer example (<ref>). 



§ IMPROVED ANATOMY LEMMAS


The exponential saving obtained in the lemmas of Section <ref> is weaker than the super-exponential decay obtained in the corresponding lemma of Koukoulopoulos–Maynard <cit.>. One can in fact obtain such stronger decay in our settings, in a wide range of uniformity in the parameters c and t: we discuss this below. However, it seems non-trivial to include these improvements within the proof of Proposition <ref>, since the parameter C_3 involved in Lemma <ref> will no longer be O(1) (but will depend on C and t). There are extra complications, involving the ranges of parameters on which one can improve the anatomy bounds. This is the subject of current work of the second named author. 



To obtain stronger bounds in Lemmas <ref> and <ref>, one may adapt the following trick from the proof of <cit.>. 


    
    Let ε∈ (0,1/2). Then for any t ⩾ 1 and c ∈ℝ with ε clog t sufficiently large,
    
    { n ⩽ x: ∑_p ⩾ t 
     p| n1/p⩾ c}⊆{ n ⩽ x: ∑_p ⩾ t ^e^(1-2 ε)c
     p| n 1/p⩾ε c}.

    

    Set T = t ^e^(1-2 ε)c. From the assumptions and Mertens' Second Theorem (with the basic error term <cit.>)
    
    ∑_t ⩽ p ⩽ T1/p = (1-2 ε)c + O(1/log t) ⩽ (1- ε) c.

    Therefore, whenever ∑_p⩾ t 
 p| n1/p⩾ c we must also have ∑_p⩾ T 
 p| n1/p⩾ε c and the lemma follows.

One could expand the range of c in Lemma <ref> using an improved error term in Mertens' Second Theorem, for example the bound recalled in (<ref>) above. However, there are other limiting factors which will constrain our choice of c below to the range c ≫ (log t)^-1, so for simplicity we chose to use the basic error term in Lemma <ref>. 

    
    Let ε∈ (0,1). Suppose t ⩾ e^e and c > 0 with ε c log t/loglog t sufficiently large. Then for any real x⩾ 1,
    
    | { n ⩽ x: ∑_p ⩾ t 
     p| n1/p⩾ c}|
            ≪ xe^-100t ^e^(1- ε)c.



    Take δ := ε/3. Then δ∈ (0, 1/3) and Lemmas <ref> and <ref> imply
    
    | { n ⩽ x: ∑_p ⩾ t 
     p| n 1/p⩾ c}|
            ≪ xe^-100δ ct ^e^(1-2δ)c.

    Now observe that
    
    δ ct ^e^(1-2 δ)c⩾δ c t ^δ ct ^e^(1-3 δ)c⩾δ c log (t) t ^e ^(1-3 δ) c⩾ t ^e^(1-3 δ)c
    =  t ^e^(1-ε)c

    where we are using that ε c log t⩾ 3loglog t. 


A very similar argument applies to the second anatomy lemma.

    
Let ε∈ (0,1). Suppose t ⩾ e^e and c > 0 with ε c log t/loglog t sufficiently large. Let f be a non-negative multiplicative function that satisfies (<ref>). Then for any M ∈ℕ,
    
    ∑_mn = M 
    ∑_p ⩾ t 
     p| m1/p⩾ c f(n)
        ≪ Me^-100t ^e^(1-ε)c.



    See the proof of Lemma <ref>. The implicit constant does not depend on the size of ε c log t/loglog t, provided this quantity is initially chosen to be sufficiently large, nor on the choice of f. 


The constant 100 appearing in the exponents of equations  (<ref>) and (<ref>) is arbitrary (and was chosen in Section <ref> to line up with the choice in <cit.>). One could replace 100 with any positive constant A, at the expense of different implicit constants in equations (<ref>) and (<ref>). Making the A dependency explicit, and optimising for the parameter A, would allow us to relax the condition ε c log t/loglog t≫ 1 to ε clog t ≫ 1. We do not pursue this technical line here, however.


Finally, we show that Lemma <ref> is very close to optimal. 


  Suppose t ⩾ 1 and c, ε > 0 with ε clog t sufficiently large. Then for any real x ⩾ 1,
    
    | { n ⩽ x: ∑_p ⩾ t 
     p| n1/p⩾ c}|
            ⩾ xe^-t ^e^(1+ε)c -1.




 If n_0 satisfies ∑_p ⩾ t
 p| n_0 1/p⩾ c then the same holds for all multiples of n_0, and
    
    | { n ⩽ x: ∑_p ⩾ t 
     p| n 1/p⩾ c}|
            ⩾x/n_0 - 1.

   Set T = t ^e^(1+ε)c, so that again by Mertens' Second Theorem 
    
    ∑_t⩽ p⩽ T1/p = (1+ ε)c + O(1/log t)
            ⩾ c.

    Setting n_0 = ∏_t⩽ p ⩽ Tp, then clearly n_0 has the desired property and n_0 ⩽ e^O(T)⩽ e^t ^e^(1+2 ε)c since ε c log t is sufficiently large. The lemma follows by rescaling ε.


A similar idea allows us to obtain a lower bound when clog t is small. (We choose the upper-bound 1/2 for concreteness.) 


    There is an absolute constant K>0 for which the following holds. If t is sufficiently large, then for any real x ⩾ 1 and c ∈ℝ with clog t ⩽ 1/2,

    
    | { n ⩽ x: ∑_p ⩾ t 
     p| n1/p⩾ c}|
            ⩾ xe^-Kt -1.





  Take T = 3t. Then 
    
    ∑_t⩽ p ⩽ T1/p⩾π(3t)-π(t)/3t = (2+o(1))t/log t/3t⩾1/2log t⩾ c.

    Therefore, we may take n_0 = ∏_t⩽ p ⩽ Tp and the lemma follows in the same way as before.



plain



