The distribution of primes in densely divisible moduli

23 June, 2013 in math.NT, polymath | Tags: exponential sums, polymath8, Yitang Zhang | by Terence Tao

As in previous posts, we use the following asymptotic notation: ${x}$ is a parameter going off to infinity, and all quantities may depend on ${x}$ unless explicitly declared to be “fixed”. The asymptotic notation ${O(), o(), \ll}$ is then defined relative to this parameter. A quantity ${q}$ is said to be of polynomial size if one has ${q = O(x^{O(1)})}$ , and bounded if ${q=O(1)}$ . We also write ${X \lessapprox Y}$ for ${X \ll x^{o(1)} Y}$ , and ${X \sim Y}$ for ${X \ll Y \ll X}$ .

The purpose of this post is to collect together all the various refinements to the second half of Zhang’s paper that have been obtained as part of the polymath8 project and present them as a coherent argument (though not fully self-contained, as we will need some lemmas from previous posts).

In order to state the main result, we need to recall some definitions.

Definition 1 (Singleton congruence class system) Let ${I \subset {\bf R}}$ , and let ${{\mathcal S}_I}$ denote the square-free numbers whose prime factors lie in ${I}$ . A singleton congruence class system on ${I}$ is a collection ${{\mathcal C} = (\{a_q\})_{q \in {\mathcal S}_I}}$ of primitive residue classes ${a_q \in ({\bf Z}/q{\bf Z})^\times}$ for each ${q \in {\mathcal S}_I}$ , obeying the Chinese remainder theorem property

$\displaystyle a_{qr}\ (qr) = (a_q\ (q)) \cap (a_r\ (r)) \ \ \ \ \ (1)$

whenever ${q,r \in {\mathcal S}_I}$ are coprime. We say that such a system ${{\mathcal C}}$ has controlled multiplicity if the

$\displaystyle \tau_{\mathcal C}(n) := |\{ q \in {\mathcal S}_I: n = a_q\ (q) \}|$

obeys the estimate

$\displaystyle \sum_{C^{-1} x \leq n \leq Cx: n = a\ (r)} \tau_{\mathcal C}(n)^2 \ll \frac{x}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{o(1)}. \ \ \ \ \ (2)$

for any fixed ${C>1}$ and any congruence class ${a\ (r)}$ with ${r \in {\mathcal S}_I}$ . Here ${\tau}$ is the divisor function.

Next we need a relaxation of the concept of ${y}$ -smoothness.

Definition 2 (Dense divisibility) Let ${y \geq 1}$ . A positive integer ${q}$ is said to be ${y}$ -densely divisible if, for every ${1 \leq R \leq q}$ , there exists a factor of ${q}$ in the interval ${[y^{-1} R, R]}$ . We let ${{\mathcal D}_y}$ denote the set of ${y}$ -densely divisible positive integers.

Now we present a strengthened version ${MPZ'[\varpi,\delta]}$ of the Motohashi-Pintz-Zhang conjecture ${MPZ[\varpi,\delta]}$ , which depends on parameters ${0 < \varpi < 1/4}$ and ${0 < \delta < 1/4}$ .

Conjecture 3 ( ${MPZ'[\varpi,\delta]}$ ) Let ${I \subset {\bf R}}$ , and let ${(\{a_q\})_{q \in {\mathcal S}_I}}$ be a congruence class system with controlled multiplicity. Then

$\displaystyle \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}: q< x^{1/2+2\varpi}} |\Delta(\Lambda 1_{[x,2x]}; a_q)| \ll x \log^{-A} x \ \ \ \ \ (3)$

for any fixed ${A>0}$ , where ${\Lambda}$ is the von Mangoldt function.

The difference between this conjecture and the weaker conjecture ${MPZ[\varpi,\delta]}$ is that the modulus ${q}$ is constrained to be ${x^\delta}$ -densely divisible rather than ${x^\delta}$ -smooth (note that ${I}$ is no longer constrained to lie in ${[1,x^\delta]}$ ). This relaxation of the smoothness condition improves the Goldston-Pintz-Yildirim type sieving needed to deduce ${DHL[k_0,2]}$ from ${MPZ'[\varpi,\delta]}$ ; see this previous post.

The main result we will establish is

Theorem 4 ${MPZ'[\varpi,\delta]}$ holds for any ${\varpi,\delta>0}$ with

$\displaystyle 148\varpi+33\delta < 1. \ \ \ \ \ (4)$

This improves upon previous constraints of ${87\varpi + 17 \delta < \frac{1}{4}}$ (see this blog comment) and ${207 \varpi + 43 \delta < \frac{1}{4}}$ (see Theorem 13 of this previous post), which were also only established for ${MPZ[\varpi,\delta]}$ instead of ${MPZ'[\varpi,\delta]}$ . Inserting Theorem 4 into the Pintz sieve from this previous post gives ${DHL[k_0,2]}$ for ${k_0 = 1467}$ (see this blog comment), which when inserted in turn into newly set up tables of narrow prime tuples gives infinitely many prime gaps of separation at most ${H = 12,012}$ .

— 1. Reduction to Type I/II and Type III estimates —

Following Zhang, we can perform a combinatorial reduction to reduce Theorem 4 to two sub-estimates. To state this properly we need some more notation. We need a large fixed constant ${A_0>0}$ (that determines how finely we slice up the scales).

Definition 5 (Coefficient sequences) A coefficient sequence is a finitely supported sequence ${\alpha: {\bf N} \rightarrow {\bf R}}$ that obeys the bounds

$\displaystyle |\alpha(n)| \ll \tau^{O(1)}(n) \log^{O(1)}(x) \ \ \ \ \ (5)$

for all ${n}$ .

(i) If ${\alpha}$ is a coefficient sequence and ${a\ (q) = a \hbox{ mod } q}$ is a primitive residue class, the (signed) discrepancy ${\Delta(\alpha; a\ (q))}$ of ${\alpha}$ in the sequence is defined to be the quantity
$\displaystyle \Delta(\alpha; a \ (q)) := \sum_{n: n = a\ (q)} \alpha(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1} \alpha(n). \ \ \ \ \ (6)$

(ii) A coefficient sequence ${\alpha}$ is said to be at scale ${N}$ for some ${N \geq 1}$ if it is supported on an interval of the form ${[(1-O(\log^{-A_0} x)) N, (1+O(\log^{-A_0} x)) N]}$ .

(iii) A coefficient sequence ${\alpha}$ at scale ${N}$ is said to obey the Siegel-Walfisz theorem if one has
$\displaystyle | \Delta(\alpha 1_{(\cdot,q)=1}; a\ (r)) | \ll \tau(qr)^{O(1)} N \log^{-A} x \ \ \ \ \ (7)$

for any ${q,r \geq 1}$ , any fixed ${A}$ , and any primitive residue class ${a\ (r)}$ .

(iv) A coefficient sequence ${\alpha}$ at scale ${N}$ is said to be smooth if it takes the form ${\alpha(n) = \psi(n/N)}$ for some smooth function ${\psi: {\bf R} \rightarrow {\bf C}}$ supported on ${[1-O(\log^{-A_0} x), 1+O(\log^{-A_0} x)]}$ obeying the derivative bounds
$\displaystyle \psi^{(j)}(t) = O( \log^{j A_0} x ) \ \ \ \ \ (8)$

for all fixed ${j \geq 0}$ (note that the implied constant in the ${O()}$ notation may depend on ${j}$ ).

We can now state the two subestimates needed. The first controls sums of Type I or Type II:

Theorem 6 (Type I/II estimate) Let ${\varpi, \delta, \sigma > 0}$ be fixed quantities such that

$\displaystyle 17 \varpi + 4\delta + \sigma < \frac{1}{4} \ \ \ \ \ (9)$

and

$\displaystyle 20 \varpi + 6\delta + 3\sigma < \frac{1}{2} \ \ \ \ \ (10)$

and

$\displaystyle 32 \varpi + 9\delta + \sigma < \frac{1}{2} \ \ \ \ \ (11)$

and

$\displaystyle 48\varpi + 7 \delta < \frac{1}{2} \ \ \ \ \ (12)$

and let ${\alpha,\beta}$ be coefficient sequences at scales ${M,N}$ respectively with

$\displaystyle MN \sim x \ \ \ \ \ (13)$

and

$\displaystyle x^{\frac{1}{2}-\sigma} \ll N \ll M \ll x^{\frac{1}{2}+\sigma} \ \ \ \ \ (14)$

with ${\beta}$ obeying a Siegel-Walfisz theorem. Then for any ${I \subset {\bf R}}$ and any singleton congruence class system ${(\{a_q\})_{q \in {\mathcal S}_I}}$ with controlled multiplicity we have

$\displaystyle \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}: q< x^{1/2+2\varpi}} |\Delta(\alpha \ast \beta; a_q)| \ll x \log^{-A} x.$

This improves upon Theorem 16 in this previous post, in which the modulus was required to be ${x^\delta}$ -smooth, and the constraints (9), (10), (11) were replaced by the stronger constraint ${ 11 \varpi + 3\delta + 2 \sigma < \frac{1}{4}}$ , and (12) was similarly replaced by a stronger constraint ${39 \varpi + 5\delta < \frac{1}{4}}$ . Of the three constraints (9), (10), (11), the second constraint (10) is more stringent in practice, while the constraint (12) is dominated by other constraints (such as (4)).

The second subestimate controls sums of Type III:

Theorem 7 (Type III estimate) Let ${\varpi, \delta > 0}$ be fixed quantities. Let ${N_1,N_2,N_3, M > 1}$ be scales obeying the relations

$\displaystyle N_1 \gg N_2,N_3$

$\displaystyle M N_1^4 N_2^4 N_3^5 > x^{4+16\varpi + \delta+\epsilon} \ \ \ \ \ (15)$

$\displaystyle N_1^3 N_2^3 N_3^4 > x^{3+12\varpi + \delta+\epsilon} \ \ \ \ \ (16)$

and

$\displaystyle N_1 N_2 \gtrapprox x^{1/2+6\varpi+\epsilon} \ \ \ \ \ (17)$

and

$\displaystyle MN_1 N_2 N_3 \sim x$

for some fixed ${\epsilon>0}$ . Let ${\alpha,\psi_1,\psi_2,\psi_3}$ be coefficient sequences at scales ${M,N_1,N_2,N_3}$ respectively, with ${\psi_1,\psi_2,\psi_3}$ smooth. Then for any ${I \subset {\bf R}}$ , and any singleton congruence class system ${(\{a_q\})_{q \in {\mathcal S}_I}}$ we have

$\displaystyle \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}: q< x^{1/2+2\varpi}} |\Delta(\alpha \ast \psi_1 \ast \psi_2 \ast \psi_3; a_q)| \ll x \log^{-A} x$

for any fixed ${A>0}$ .

This improves upon Theorem 17 in this previous post, in which the modulus was required to be ${x^\delta}$ -smooth, and the constraints (15), (16) were replaced by the stronger constraint ${N_1^4 N_2^4 N_3^5 > x^{4+16\varpi + \delta+\epsilon}}$ . Of the two constraints (15), (16), the first constraint (15) is more stringent in practice.

Let us now recall the combinatorial argument (from this previous post) that allows one to deduce Theorem 4 from Theorems 6 and 7. As in Section 3 of this previous post, we let ${K \geq 1}$ be a fixed integer ( ${K=10}$ will suffice). Using the Heath-Brown identity as discussed in that section, we reduce to establishing the bound

$\displaystyle \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}: q< x^{1/2+2\varpi}} |\Delta(\alpha_1 \ast \ldots \ast \alpha_{2J}; a_q)| \ll x \log^{-A} x$

where ${1 \leq J \leq K}$ , ${1 \ll N_1,\ldots,N_{2J} \ll x}$ are quantities with the following properties:

(i) Each ${\alpha_i}$ is a coefficient sequence at scale ${N_i}$ . More generally the convolution ${\alpha_S}$ of the ${\alpha_i}$ for ${i \in S}$ is a coefficient sequence at scale ${\prod_{i \in S} N_i}$ .
(ii) If ${N_i \gg x^{1/K+\epsilon}}$ for some fixed ${\epsilon>0}$ , then ${\alpha_i}$ is smooth.
(iii) If ${N_i \gg x^\epsilon}$ for some fixed ${\epsilon>0}$ , then ${\alpha_i}$ obeys a Siegel-Walfisz theorem. More generally, ${\alpha_S}$ obeys a Siegel-Walfisz theorem if ${\prod_{i \in S} N_i \gg x^\epsilon}$ for some fixed ${\epsilon>0}$ .
(iv) ${N_1 \ldots N_{2J} \sim x}$ .

We can write ${N_i \sim x^{t_i}}$ for ${i=1,\ldots,2J}$ , where the ${t_i}$ are non-negative reals that sum to ${1}$ . We apply Lemma 6 from this previous post with some parameter

$\displaystyle 1/10 < \sigma < 1/2 \ \ \ \ \ (18)$

to be chosen later and conclude one of the following:

(Type 0) There is a ${t_i}$ with ${t_i \geq 1/2 + \sigma}$ .
(Type I/II) There is a partition ${\{1,\ldots,2J\} = S \cup T}$ such that
$\displaystyle \frac{1}{2} - \sigma < \sum_{i \in S} t_i \leq \sum_{i \in T} t_i < \frac{1}{2} + \sigma.$
(Type III) There exist distinct ${i,j,k}$ with ${2\sigma \leq t_i \leq t_j \leq t_k \leq 1/2-\sigma}$ and ${t_i+t_j,t_i+t_k,t_j+t_k \geq 1/2 + \sigma}$ .

In the Type 0 case, we can write ${\alpha_1 \ast \ldots \ast \alpha_{2j}}$ in a form in which Theorem 15 from this previous post applies. Similarly, in the Type I/II case we can write ${\alpha_1 \ast \ldots \ast \alpha_{2j}}$ in a form in which Theorem 6 applies, provided that the conditions (9), (10), (11) are obeyed (the condition (12) is implied by (4)). Now suppose we are in the Type III case. For ${K}$ large enough (e.g. ${K=10}$ ), we see that ${t_i,t_j,t_k \geq \frac{1}{K}+\epsilon}$ for some fixed ${\epsilon}$ . Theorem 7 will then apply with

$\displaystyle N_1 \sim x^{t_k}$

$\displaystyle N_2 \sim x^{t_j}$

$\displaystyle N_3 \sim x^{t_i}$

$\displaystyle M \sim x^{1-t_i-t_j-t_k}$

provided that we can verify the hypotheses (15), (16), (17), which will follow if we have

$\displaystyle (1-t_i-t_j-t_k) + 4t_k + 4t_j + 5t_i > 4 + 16 \varpi + \delta$

and

$\displaystyle 3t_k + 3 t_j + 4 t_i > 3 + 12 \varpi + \delta$

and

$\displaystyle t_k + t_j > \frac{1}{2} + 6 \varpi.$

Since ${t_i+t_j,t_i+t_k,t_j+t_k \geq 1/2+\sigma}$ , we have

$\displaystyle (1-t_i-t_j-t_k) + 4t_k + 4t_j + 5t_i > 1 + 5 (\frac{1}{2}+\sigma)$

and

$\displaystyle 3t_k + 3t_j + 4t_i > 5 (\frac{1}{2}+\sigma)$

so we will be done if we can find ${\sigma}$ obeying the constraints (18), (9), (10), (11) as well as the constraints

$\displaystyle 1 + 5 (\frac{1}{2}+\sigma) > 4 + 16 \varpi + \delta \ \ \ \ \ (19)$

and

$\displaystyle 5 (\frac{1}{2}+\sigma) > 3 + 12 \varpi + \delta \ \ \ \ \ (20)$

and

$\displaystyle \sigma > 6 \varpi. \ \ \ \ \ (21)$

The condition (20) is a consequence of (19) and can thus be omitted.

We rewrite all of the constraints in terms of upper and lower bounds on ${\sigma}$ . The upper bounds take the form

$\displaystyle \sigma < 1/2 \ \ \ \ \ (22)$

$\displaystyle \sigma < \frac{1}{4} - 17 \varpi - 4 \delta \ \ \ \ \ (23)$

$\displaystyle \sigma < \frac{1}{6} - \frac{20}{3} \varpi - 2 \delta \ \ \ \ \ (24)$

$\displaystyle \sigma < \frac{1}{2} - 32 \varpi - 9\delta \ \ \ \ \ (25)$

while the lower bounds take the form

$\displaystyle \sigma > \frac{1}{10} \ \ \ \ \ (26)$

$\displaystyle \sigma > \frac{1}{10} + \frac{16}{5} \varpi + \frac{1}{5} \delta. \ \ \ \ \ (27)$

$\displaystyle \sigma > 6\varpi \ \ \ \ \ (28)$

Clearly (22) is implied by (23), and (26) is implied by (27); restricting to the case ${\varpi < 1/60}$ (which follows from (4)), (28) is also implied by (26). Assuming (4), we also see that (23), (25) are implied by (24), so we reduce to establishing that

$\displaystyle \frac{1}{10} + \frac{16}{5} \varpi + \frac{1}{5} \delta < \frac{1}{6} - \frac{20}{3} \varpi - 2 \delta$

but this rearranges to (4).

It remains to establish Theorem 6 and Theorem 7.

— 2. Type I/II analysis —

We begin the proof of Theorem 6, closely following the arguments from Section 5 of this previous post. We can restrict ${q}$ to the range

$\displaystyle q \gtrapprox x^{1/2}$

for some sufficiently slowly decaying ${o(1)}$ , since otherwise we may use the Bombieri-Vinogradov theorem (Theorem 4 from this previous post). Thus, by dyadic decomposition, we need to show that

$\displaystyle \sum_{d \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}: D \leq d < 2D} |\Delta(\alpha \ast \beta; a_d)| \ll NM \log^{-A} x. \ \ \ \ \ (29)$

for any ${D}$ in the range

$\displaystyle x^{1/2} \lessapprox D \lessapprox x^{1/2+2\varpi}.$

Let

$\displaystyle \mu > 0 \ \ \ \ \ (30)$

be an exponent to be optimised later (in the Type I case, it will be infinitesimally close to zero, while in the Type II case, it will be infinitesimally larger than ${2\varpi}$ ).

By Lemma 11 of this previous post, we know that for all ${d}$ in ${[D,2D]}$ outside of a small number of exceptions, we have

$\displaystyle \prod_{p|d: p \leq D_0} p \lessapprox 1 \ \ \ \ \ (31)$

where

$\displaystyle D_0 := \exp(\log^{1/3} x).$

Specifically, the number of exceptions in the interval ${[D,2D]}$ is ${O(D \log^{-A} x)}$ for any fixed ${A>0}$ . The contribution of the exceptional ${d}$ can be shown to be acceptable by Cauchy-Schwarz and trivial estimates (see Section 5 of this previous post), so we restrict attention to those ${d}$ for which (31) holds. In particular, as ${d}$ is restricted to be ${x^\delta}$ -densely divisible we may factor

$\displaystyle d=qr$

with ${q,r}$ coprime and square-free, with ${q \in {\mathcal S}_{I'}}$ with ${I' := [D_0,\infty) \cap I}$ , and

$\displaystyle x^{-\mu-\delta} N \lessapprox r \lessapprox x^{-\mu} N$

and

$\displaystyle x^{1/2} \lessapprox qr \lessapprox x^{1/2+2\varpi}.$

By dyadic decomposition, it thus sufices to show that

$\displaystyle \sum_{q \in {\mathcal S}_{I'}: q \sim Q} \sum_{r \in {\mathcal S}_I: r \sim R; (q,r)=1} |\Delta(\alpha \ast \beta; a_{qr})| \ll NM \log^{-A} x.$

for any fixed ${A>0}$ , where ${Q, R \geq 1}$ obey the size conditions

$\displaystyle x^{-\mu-\delta} N \lessapprox R \lessapprox x^{-\mu} N \ \ \ \ \ (32)$

and

$\displaystyle x^{1/2} \lessapprox QR \lessapprox x^{1/2 + 2\varpi}. \ \ \ \ \ (33)$

Fix ${Q,R}$ . We abbreviate ${\sum_{q \in {\mathcal S}_{I'}: q \sim Q}}$ and ${\sum_{r \in {\mathcal S}_I: r \sim R}}$ by ${\sum_q}$ and ${\sum_r}$ respectively, thus our task is to show that

$\displaystyle \sum_q \sum_{r: (q,r)=1} |\Delta(\alpha \ast \beta; a_{qr})| \ll NM \log^{-A} x.$

We now split the discrepancy

$\displaystyle \Delta(\alpha \ast \beta; a_{qr}) = \sum_{n = a_{qr}\ (qr)} \alpha \ast \beta(n) - \frac{1}{\phi(qr)} \sum_{n: (n,qr)=1} \alpha \ast \beta(n)$

as the sum of the subdiscrepancies

$\displaystyle \sum_{n: n = a_{qr}\ (qr)} \alpha \ast \beta(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a_r\ (r)} \alpha \ast \beta(n)$

and

$\displaystyle \frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a_r\ (r)} \alpha \ast \beta(n) - \frac{1}{\phi(qr)} \sum_{n: (n,qr)=1} \alpha \ast \beta(n).$

In Section 5 of this previous post, it was established that

$\displaystyle \sum_{q} \sum_{r; (q,r)=1} |\frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a_r\ (r)} \alpha \ast \beta(n) - \frac{1}{\phi(qr)} \sum_{n: (n,qr)=1} \alpha \ast \beta(n)| \ll$

$\displaystyle NM \log^{-A} x$

so it suffices to show that

$\displaystyle \sum_{q} \sum_{r; (q,r)=1} |\sum_{n: n = a_{qr}\ (qr)} \alpha \ast \beta(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a_r\ (r)} \alpha \ast \beta(n)| \ \ \ \ \ (34)$

$\displaystyle \ll NM \log^{-A} x.$

As in the previous notes, we will not take advantage of the ${r}$ summation, and use crude estimates to reduce to showing that

$\displaystyle \sum_{q; (q,r)=1} |\sum_{n: n = a_q\ (q); n = a_r\ (r)} \alpha \ast \beta(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a_r\ (r)} \alpha \ast \beta(n)| \ \ \ \ \ (35)$

$\displaystyle \ll NM R^{-1} \tau(r)^{O(1)} \log^{-A} x$

for each individual ${r \in {\mathcal S}_I}$ with ${r \sim R}$ , which we now fix. Repeating the previous arguments, it sufices to show that

$\displaystyle \sum_{q; (q,r)=1} |\sum_{n: n = b_q\ (q); n = a_r\ (r)} \alpha \ast \beta(n) - \sum_{n: n = b'_q\ (q); n = a_r\ (r)} \alpha \ast \beta(n)| \ \ \ \ \ (36)$

$\displaystyle \ll NM R^{-1} \tau(r)^{O(1)} \log^{-A} x$

whenever ${(b_q)_{q \in {\mathcal S}_{I'}}, (b'_q)_{q \in {\mathcal S}_{I'}}}$ are good singleton congruence class systems.

By duality and Cauchy-Schwarz exactly as in Section 5 of the previous post, it suffices to show that

$\displaystyle \sum_{m} \psi_M(m) |\sum_{q,n: mn = a_r\ (r); (q,r)=1} c_{q} \beta(n) (1_{mn = b_{q}\ (q)} - 1_{mn = b'_{q}\ (q)})|^2 \ \ \ \ \ (37)$

$\displaystyle \ll N^2 M R^{-2} \tau(r)^{O(1)} \log^{-A} x$

for any fixed ${A>0}$ , where ${\psi_M}$ is a smooth coefficient sequence at scale ${M}$ . Expanding out the square, it suffices to show that

$\displaystyle \sum_{m} \psi_M(m) \sum_{q_1,q_2,n_1,n_2: mn_1=mn_2 = a_r\ (r); (q_1,r)=(q_2,r)=1} \ \ \ \ \ (38)$

$\displaystyle c_{q_1} c_{q_2} \beta(n_1) \beta(n_2) 1_{mn_1 = b_{q_1}\ (q_1)} 1_{mn_2 = b'_{q_2}\ (q_2)}$

$\displaystyle = X + O( N^2 M R^{-2} \tau(r)^{O(1)} \log^{-A} x )$

where ${q_1,q_2}$ is subject to the same constraints as ${q}$ (thus ${q_i \in {\mathcal S}_{I'}}$ and ${Q \ll q_i \ll Q}$ for ${i=1,2}$ ), and ${X}$ is some quantity that is independent of the choice of congruence classes ${(b_q)_{q \in {\mathcal S}_I}}$ , ${(b'_q)_{q \in {\mathcal S}_I}}$ .

As in the previous notes, we can dispose of the case when ${q_1,q_2}$ share a common factor by using the controlled multiplicity hypothesis, provided we have the hypothesis

$\displaystyle x^\mu \geq x^{-1/2+2\varpi+c} N \ \ \ \ \ (39)$

which we file away for later. (There was also the condition ${R \ll x^{-c+o(1)} M}$ from equation (33) of previous notes, but this condition is implied by (30) for ${c}$ small enough since ${N \ll M}$ .) This reduces us to establishing

$\displaystyle \sum_{m} \psi_M(m) \sum_{q_1,q_2,n_1,n_2: mn_1=mn_2 = a_r\ (r); (q_1,r)=(q_2,r)=(q_1,q_2)=1} \ \ \ \ \ (40)$

$\displaystyle c_{q_1} c_{q_2} \beta(n_1) \beta(n_2) 1_{mn_1 = b_{q_1}\ (q_1)} 1_{mn_2 = b'_{q_2}\ (q_2)}$

$\displaystyle = X + O( N^2 M R^{-2} \log^{-A} x ).$

It remains to verify (40). Observe that ${n_1}$ must be coprime to ${q_1r}$ and ${n_2}$ coprime to ${q_2r}$ , with ${n_1 = n_2\ (r)}$ , to have a non-zero contribution to the sum. We then rearrange the left-hand side as

$\displaystyle \sum_{q_1,q_2: (q_1,r)=(q_2,r)=(q_1,q_2)=1} \sum_{m} \psi_M(m) \sum_{n_1,n_2: n_1=n_2\ (r); (n_1,q_1r)=(n_2,q_2)=1}$

$\displaystyle c_{q_1} c_{q_2} \beta(n_1) \beta(n_2) 1_{m = a_r/n_1\ (r); m = b_{q_1}/n_1\ (q_1); m = b'_{q_2}/n_2 (q_2)};$

note that these inverses in the various rings ${{\bf Z}/r{\bf Z}}$ , ${{\bf Z}/q_1{\bf Z}}$ , ${{\bf Z}/q_2{\bf Z}}$ are well-defined thanks to the coprimality hypotheses.

We may write ${n_2 = n_1+kr}$ for some ${k = O(N/R)}$ . By the triangle inequality, and relabeling ${n_1}$ as ${n}$ , it thus suffices to show that for any particular

$\displaystyle k = O(N/R), \ \ \ \ \ (41)$

one has

$\displaystyle \sum_{q_1,q_2: (q_1,r)=(q_2,r)=(q_1,q_2)=1} \sum_{m} \psi_M(m) \sum_{n; (n,q_1r)=(n+kr,q_2)=1} \ \ \ \ \ (42)$

$\displaystyle c_{q_1} c_{q_2} \beta(n) \beta(n+kr) 1_{m = a_r/n\ (r); m = b_{q_1}/n\ (q_1); m = b'_{q_2}/(n+kr) (q_2)}$

$\displaystyle = X_k + O( N M R^{-1} \log^{-A} x )$

for some ${X_k}$ independent of the ${b_q}$ and ${b'_q}$ .

Applying completion of sums (Section 2 from the previous post), we reduce to showing that

$\displaystyle \sum_{1 \leq h \leq H} \sum_{q_1,q_2 \sim Q} |\sum_{n} \beta(n) \beta(n+kr) \Phi(h,q_1,q_2; n)| \lessapprox x^{-\epsilon} Q^2 N \ \ \ \ \ (43)$

for a sufficiently small fixed ${\epsilon>0}$ , where

$\displaystyle H := x^\epsilon Q^2 R/M \ \ \ \ \ (44)$

and ${\Phi = \Phi_{k,r}}$ is the phase

$\displaystyle \Phi(h,q_1,q_2;n) := 1_{(q_1,r)=(q_2,r)=(q_1,q_2)=(n,r)=(n,q_1)=(n+kr,q_2)=1} \ \ \ \ \ (45)$

$\displaystyle e_r( \frac{a_r h}{nq_1 q_2} ) e_{q_1}( \frac{b_{q_1}h}{n r q_2} ) e_{q_2}( \frac{b'_{q_2} h}{(n+kr) r q_1} ),$

and we have dropped all hypotheses on ${q_1,q_2}$ other than magnitude, and we abbreviate ${\sum_{1 \leq h \leq H}}$ as ${\sum_h}$ .

We now split into two cases, one which works when ${M, N}$ are not too close to ${x^{1/2}}$ , and one which works when ${M, N}$ are close to ${x^{1/2}}$ . Here is the Type I estimate:

Theorem 8 (Type I case) If the inequalities

$\displaystyle 17\varpi + \sigma + 4\mu + 4\delta < \frac{1}{4} \ \ \ \ \ (46)$

and

$\displaystyle 20\varpi + 3\sigma + 6\mu + 6\delta < \frac{1}{2} \ \ \ \ \ (47)$

and

$\displaystyle 32 \varpi + \sigma + 9 \mu + 9\delta < \frac{1}{2}. \ \ \ \ \ (48)$

and

$\displaystyle M \gtrapprox x^{1/2+2\varpi+c'} \ \ \ \ \ (49)$

hold for some fixed ${c'>0}$ , then (43) holds for a sufficiently small fixed ${\epsilon>0}$ .

The hypotheses (46), (47), (48) improve upon Theorem 13 from this previous post, which had instead the more strict condition

$\displaystyle 11\varpi + 3\mu + 3\delta + 2 \sigma < \frac{1}{4}.$

In practice the condition (47) is dominant.

Now we give the Type II estimate:

Theorem 9 (Type II case) If the inequality

$\displaystyle 24\varpi + 7 \mu + 7 \delta + 5 \sigma < \frac{1}{2} \ \ \ \ \ (50)$

holds, then (43) holds for a sufficiently small fixed ${\epsilon>0}$ .

This result improves upon Theorem 14 from this previous post which had the stronger condition

$\displaystyle 24\varpi + 10 \mu + 10 \delta + 7 \sigma < \frac{1}{2}.$

In practice, (50) will not hold with the original value of ${\sigma}$ in Theorem 6; instead, we only use Theorem 9 the case ${M \lessapprox x^{1/2+2\varpi+c'}}$ excluded by Theorem 8, in which case we will be able to lower ${\sigma}$ down to be ${2\varpi+c'}$ and verify (50) in that case.

Assuming these theorems, let us now conclude the proof of Theorem 6. First suppose we are in the “Type I” regime when (49) holds for some fixed ${c'>0}$ . Then by (13) we have

$\displaystyle N \ll x^{1/2-2\varpi-c'}$

which means that the condition (39) is now weaker than (30) (for ${c}$ small enough) and may be omitted. By (9), (10), (11), we can simultaneously obey (30), (46), (47), (48) by setting ${\mu}$ sufficiently close to zero, and the claim now follows from Theorem 8.

Now suppose instead that we are in the “Type II” regime where (49) fails for some small ${c'>0}$ , so that by (13) we have

$\displaystyle x^{1/2-2\varpi-c'} \ll N \ll M \ll x^{1/2+2\varpi+c'}.$

From this we see that we may replace ${\sigma}$ by ${2\varpi+c'}$ in (14) and in all of the above analysis. If we set ${\mu := 2\varpi + c'}$ then the conditions (30), (39) are obeyed (again taking ${c}$ small enough). Theorem 9 will then give us what we want provided that

$\displaystyle 24\varpi + 7 (2\varpi+c') + 7 \delta + 5 (2\varpi+c') < \frac{1}{2}$

which is satisfied for ${c'}$ small enough thanks to (12).

In the next two sections we establish Theorem 8 and Theorem 9.

— 3. The Type I sum —

We now prove Theorem 8. It suffices to show that

$\displaystyle |\sum_h \sum_{q_1,q_2 \sim Q} c_{h,q_1,q_2} \sum_{n} \beta(n) \beta(n+kr) \Phi(h,q_1,q_2; n)| \lessapprox x^{-\epsilon} Q^2 N$

for any bounded real coefficients ${c_{h,q_1,q_2} = O(1)}$ . Performing the manipulations from Section 6 of this previous post, we reduce to showing that

$\displaystyle \sum_{h,h'} \sum_{q_2,q'_2 \sim Q} |\sum_{n} \psi_N(n) \Phi(h,q_1,q_2;n) \overline{\Phi(h',q_1,q'_2;n)}| \lessapprox x^{-2\epsilon} Q^2 N \ \ \ \ \ (51)$

for any ${q_1 \sim Q}$ .

To prove (51), we isolate the diagonal case ${h'q_2 = hq'_2}$ and the non-diagonal case ${h'q_2 \neq h q'_2}$ . For the diagonal case, we argue as in Section 6 of the previous post and reduce to verifying that

$\displaystyle QR \lessapprox x^{-3\varepsilon} M$

but this follows from (33), (49) for ${\epsilon}$ small enough.

Now we treat the non-diagonal case ${h'q_2 \neq hq'_2}$ . The key estimate here is

Lemma 10 In the non-diagonal case ${h'q_2 \neq hq'_2}$ , we have

$\displaystyle |\sum_{n} \psi_N(n) \Phi(h,q_1,q_2;n) \overline{\Phi(h',q_1,q'_2;n)}| \ \ \ \ \ (52)$

$\displaystyle \lessapprox N^{1/2} Q^{1/4} R^{1/4} + N^{1/2} Q + R^{-1/4} N (hq'_2-h'q_2,r)^{1/4}.$

Proof: From (45) we may of course assume that

$\displaystyle (q_1,r) = (q_2,r) = (q_1,q_2) = (q'_2,r) = (q_1,q'_2) = 1.$

Arguing as in Section 6 of this previous post, we may write the left-hand side of (52) as

$\displaystyle | \sum_{n} \psi_N(n) 1_{(n,d_1) = (n+kr,d_2)=1} e_{d_1}( \frac{c_1}{n} ) e_{d_2}( \frac{c_2}{n+kr} )|$

where ${d_1 := q_1 r}$ , ${d_2 := [q_2, q'_2]}$ , and ${c_1,c_2}$ are integers with

$\displaystyle (c_1, r) = (hq'_2-h'q_2, r). \ \ \ \ \ (53)$

Now for the new input that was not present in the previous Type I analysis. Applying Proposition 5(iii) from this previous post, and noting that ${D_1,d_2}$ are coprime, we can bound the left-hand side of (52) as

$\displaystyle \lessapprox N^{1/2} d_1^{1/4} +N^{1/2} d_2^{1/2} + \frac{(c_1,d_1)^{1/4}}{d_1^{1/4}} N.$

Since ${d_1 \ll QR}$ , ${d_2 \ll Q^2}$ , and

$\displaystyle \frac{(c_1,d_1)^{1/4}}{d_1^{1/4}} \leq \frac{(c_1,r)^{1/4}}{r^{1/4}} = \frac{(hq'_2-h'q_2,r)^{1/4}}{r^{1/4}}$

the claim follows. $\Box$

Note from the divisor bound that for each choice of ${h,q'_2}$ and ${a = O(HQ)}$ , there are ${\lessapprox 1}$ choices of ${h', q_2}$ such that ${hq'_2 - h'q_2 = a}$ . From this and Lemma 5 of this previous post we see that

$\displaystyle \sum_{h,h'} \sum_{q_2,q'_2 \sim Q} (hq'_2-h'q_2,r) 1_{hq'_2 \neq h'q_2} \lessapprox H^2 Q^2$

and thus also if ${(hq'_2-h'q_2,r)}$ is replaced by ${(hq'_2-h'q_2,r)^{1/4}}$ . From this and Lemma 10 we see that the non-diagonal contribution to (51) is

$\displaystyle \lessapprox H^2 Q^2 ( N^{1/2} Q^{1/4} R^{1/4} + N^{1/2} Q + R^{-1/4} N )$

so to conclude (51) we need to show that

$\displaystyle H^2 Q^{9/4} R^{1/4} N^{1/2} \lessapprox x^{-2\epsilon} Q^2 N$

and

$\displaystyle H^2 Q^3 N^{1/2} \lessapprox x^{-2\epsilon} Q^2 N$

and

$\displaystyle H^2 Q^2 R^{-1/4} N \lessapprox x^{-2\epsilon} Q^2 N$

Using (44), (13) we can rewrite these criteria as

$\displaystyle (QR)^{17/4} \lessapprox x^{2-4\epsilon} N^{1/2} (R/N)^2$

and

$\displaystyle (QR)^5 \lessapprox x^{2-4\epsilon} N^{3/2} (R/N)^3$

and

$\displaystyle (QR)^4 \lessapprox x^{2-4\epsilon} N^{1/4} (R/N)^{9/4}$

respectively. Applying (33), (32), it suffices to verify that

$\displaystyle \frac{17}{4} (\frac{1}{2} + 2 \varpi) < 2 + \frac{1}{2} ( \frac{1}{2}-\sigma ) - 2 (\mu + \delta)$

and

$\displaystyle 5 (\frac{1}{2} + 2 \varpi) < 2 + \frac{3}{2} ( \frac{1}{2}-\sigma ) - 3 (\mu + \delta)$

and

$\displaystyle 4 (\frac{1}{2} + 2 \varpi) < 2 + \frac{1}{4} ( \frac{1}{2}-\sigma ) - \frac{9}{4} (\mu + \delta).$

respectively. These rearrange to (46), (47), (48) respectively, and the claim follows.

— 4. The Type II sum —

We now prove Theorem 9. Arguing as in Section 7 of this previous post, it suffices to show that

$\displaystyle \sum_{h,h'} \sum_{q_1, q'_1, q_2,q'_2 \sim Q} |\sum_{n} \psi_N(n) \Phi(h,q_1,q_2;n) \overline{\Phi(h',q'_1,q'_2;n)}| \ \ \ \ \ (54)$

$\displaystyle \lessapprox x^{-2\epsilon} Q^4 N.$

As in the previous post, the diagonal case ${h'q_1 q_2 = h q'_1 q'_2}$ is acceptable provided that

$\displaystyle R \ll x^{-3\epsilon+o(1)} M,$

but this is automatic from (32) and (30) if ${\epsilon}$ is small enough.

We have the following analogue of Lemma 10:

Lemma 11 In the off-diagonal case ${h'q_1q_2 \neq h q'_1 q'_2}$ , we have

$\displaystyle |\sum_{n} \psi_N(n) \Phi(h,q_1,q_2;n) \overline{\Phi(h',q'_1,q'_2;n)}| \ \ \ \ \ (55)$

$\displaystyle \lessapprox Q^{2} R^{1/2} + R^{-1} N (hq'_1q'_2-h'q_1q_2,r)$

This is an improved version of the estimate (48) from this previous post in which several inefficiencies in the second term on the right-hand side have been removed.

Proof: From (45) we may assume

$\displaystyle (q_1,r) = (q'_1,r) = (q_2,r) = (q'_2,r) = (q_1,q_2) = (q'_1,q'_2) = 1$

and by the arguments from the previous post we may rewrite the left-hand side of (55) as

$\displaystyle | \sum_{n} \psi_N(n) 1_{(n,d_1) = (n+kr,d_2)=1} e_{d_1}( \frac{c_1}{n} ) e_{d_2}( \frac{c_2}{n+kr} ) |$

where

$\displaystyle d_1 := [q_1,q'_1]r; \quad d_2 := [q_2,q'_2]$

and

$\displaystyle (c_1, r) = (hq'_1q'_2-h'q_1q_2, r).$

By Proposition 5(ii) of this previous post, we may the bound this quantity by

$\displaystyle \lessapprox [d_1,d_2]^{1/2} + \frac{N}{d_1 d_2} (d_1,d_2)^2 (c_1,d'_1) (c_2,d'_2)$

where ${d'_1:= d_1/(d_1,d_2)}$ , ${d'_2 := d_2/(d_1,d_2)}$ . We may bound

$\displaystyle \frac{N}{d_1 d_2} (d_1,d_2)^2 (c_1,d'_1) (c_2,d'_2) \leq N \frac{(c_1,d'_1)}{d'_1} \leq N \frac{(c_1,r)}{r}$

since ${r}$ divides ${d_1}$ but is coprime to ${d_2}$ , and the claim follows. $\Box$

Arguing as in the previous section we have

$\displaystyle \sum_{h,h'} \sum_{q_1, q'_1, q_2,q'_2 \sim Q} 1_{hq'_1q'_2 \neq h'q_1q_2} (hq'_1q'_2-h'q_1q_2,r) \lessapprox H^2 Q^4$

and so the off-diagonal contribution to (54) is

$\displaystyle \lessapprox H^2 Q^6 R^{1/2} + H^2 Q^4 R^{-1} N.$

To conclude (54) we thus need to show that

$\displaystyle H^2 Q^6 R^{1/2} \lessapprox x^{-2\epsilon} Q^4 N$

and

$\displaystyle H^2 Q^4 R^{-1} N \lessapprox x^{-2\epsilon} Q^4 N.$

Using (44), (13) we can rewrite these criteria as

$\displaystyle (QR)^6 \lessapprox x^{2-4\epsilon} N^{5/2} (R/N)^{7/2}$

and

$\displaystyle (QR)^4 \lessapprox x^{2-4\epsilon} N (R/N)^3$

respectively. Applying (33), (32), it suffices to verify that

$\displaystyle 6 (\frac{1}{2} + 2 \varpi) < 2 + \frac{5}{2} ( \frac{1}{2}-\sigma ) - \frac{7}{2} (\mu + \delta)$

and

$\displaystyle 4 (\frac{1}{2} + 2 \varpi) < 2 + ( \frac{1}{2}-\sigma ) - 3 (\mu + \delta)$

which can be rearranged as

$\displaystyle 24 \varpi + 7 \mu + 7 \delta + 5 \sigma < 1/2$

and

$\displaystyle 8 \varpi + 3 \mu + 3 \delta + \sigma <1/2$

respectively, and thus both follow from (50).

— 5. The Type III estimate —

Now we prove Theorem 7. Our arguments will closely track those of Section 2 of this previous post, except that we will carry the ${\alpha}$ averaging with us for significantly longer in the argument.

Let ${\varpi,\delta,N_1,N_2,N_3,M,\alpha,\psi_1,\psi_2,\psi_3}$ obey the hypotheses of the theorem. It will suffice to establish the bound

$\displaystyle |\Delta(\alpha \ast \psi_1 \ast \psi_2 \ast \psi_3; a)| \lessapprox x^{-\epsilon} \frac{x}{d} \ \ \ \ \ (56)$

for all ${d \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}}$ with ${d < x^{1/2+2\varpi}}$ and all ${a \in ({\bf Z}/d{\bf Z})^\times}$ , and some sufficiently fixed ${\epsilon>0}$ .

Fix ${d}$ . It suffices to show that

$\displaystyle \sum_{n: n = a\ (d)} \psi_1 \ast \psi_2 \ast \alpha \ast \psi_3(n) = X + O( x^{-\epsilon+o(1)} \frac{x}{d} )$

for some ${X}$ that does not depend on ${a}$ . Applying completion of sums, we can express the left-hand side as the main term

$\displaystyle \frac{1}{d} (\sum_{n_1} \psi_1(n_1)) (\sum_{n: (n,d)=1} \psi_2 \ast \alpha \ast \psi_3(n))$

plus the error terms

$\displaystyle O( (\log^{O(1)} x) \frac{N_1}{d} \sum_{1 \leq h \le H} |\sum_{n: (n,d)=1} \psi_2 \ast \alpha \ast \psi_3(n) e_d( \frac{ah}{n} )| )$

and a tiny error

$\displaystyle O( x^{-A+ O(1)} )$

for any fixed ${A>0}$ , where

$\displaystyle H := x^\epsilon \frac{d}{N_1}.$

It thus suffices to show that

$\displaystyle \sum_{1 \leq h \le H} |\sum_{n: (n,d)=1} \psi_2 \ast \alpha \ast \psi_3(n) e_d( \frac{ah}{n} ) | \lessapprox x^{-\epsilon} M N_2 N_3. \ \ \ \ \ (57)$

it will suffice to prove the following claim:

Proposition 12 Let ${\delta>0}$ be fixed, and let

$\displaystyle H, N_2, N_3, d, B \gg 1 \ \ \ \ \ (58)$

be such that ${d}$ is ${x^\delta}$ -densely divisible and

$\displaystyle H \lessapprox x^{\epsilon} \frac{d}{N_2} \ \ \ \ \ (59)$

and

$\displaystyle M N_2^4 N_3^5 \gtrapprox B^{-6} d^4 H^4 x^{\delta+c} \ \ \ \ \ (60)$

and

$\displaystyle N_2^3 N_3^4 \gtrapprox B^{-4} d^3 H^3 x^{\delta+c} \ \ \ \ \ (61)$

and

$\displaystyle N_2 \gtrapprox H x^c \ \ \ \ \ (62)$

$\displaystyle M N_2^2 N_3 \gtrapprox B^{-2} d H^2 x^c \ \ \ \ \ (63)$

for some fixed ${c>0}$ , and let ${\psi_2,\psi_3}$ be smooth coefficient sequences at scale ${N_2,N_3}$ respectively. Then

$\displaystyle \sum_{1 \leq h \le H: (h,d)=1} |\sum_{n: (n,d)=1} \psi_2 \ast \alpha \ast \psi_3(n) e_d( \frac{ah}{n} ) | \lessapprox x^{-\epsilon} B M N_2 N_3$

if ${\epsilon}$ is sufficiently small.

Let us now see why the above proposition implies (57). To prove (57), we may of course assume ${H \geq 1}$ as the claim is trivial otherwise. We can split

$\displaystyle \sum_{1 \leq h \leq H} F(h) = \sum_{d = d_1 d_2} \sum_{1 \leq h' \leq H/d_2: (h',d_1)=1} F( d_2 h' )$

for any function ${F(h)}$ of ${h}$ , so that (57) can be written as

$\displaystyle \sum_{d = d_1 d_2} \sum_{1 \leq h' \leq H/d_2: (h',d_1)=1} |\sum_{n: (n,d_1 d_2)=1} \psi_2 \ast \alpha \ast \psi_3(n) e_{d_1}( \frac{ah'}{n} )|$

which we expand as

$\displaystyle \sum_{d = d_1 d_2} \sum_{1 \leq h' \leq H/d_2: (h',d_1)=1} |\sum_{m: (m,d_1 d_2)=1} \alpha(m) \sum_{n_2: (n_2,d_1 d_2)=1}$

$\displaystyle \sum_{n_3: (n_3,d_1d_2)=1} \psi_2(n_2) \psi_3(n_3) e_{d_1}( \frac{ah'}{mn_2 n_3} )|$

In order to apply Proposition 12 we need to modify the ${(n_2,d_1d_2)=1}$ , ${(n_3,d_1d_2)=1}$ constraints. By Möbius inversion one has

$\displaystyle \sum_{n_2: (n_2,d_1d_2)=1} F(n_2) = \sum_{b_2|d_2} \mu(b_2) \sum_{n_2: (n_2,d_1)=1} F(b_2 n_2)$

for any function ${F}$ , and similarly for ${n_3}$ , so by the triangle inequality we may bound the previous expression by

$\displaystyle \sum_{d = d_1 d_2} \sum_{b_2|d_2} \sum_{b_3|d_2} F( d_1, d_2, b_1, b_2 ) \ \ \ \ \ (64)$

where

$\displaystyle F(d_1,d_2,b_1,b_2) := \sum_{1 \leq h' \leq H/d_2: (h',d_1)=1}$

$\displaystyle |\sum_{m: (m,d_1d_2)=1} \alpha(m) \sum_{n_2: (n_2,d_1)=1} \sum_{n_3: (n_3,d_1)=1} \psi_2(b_2n_2) \psi_3(b_3n_3)$

$\displaystyle e_{d_1}( \frac{ah'}{mb_2b_3 n_2 n_3} )|$

We may discard those values of ${d_2}$ for which ${H' := H/d_2}$ is less than one, as the summation is vacuous in that case. We then apply Proposition (12) with ${d,N_2,N_3,H}$ replaced by ${d_1,N_2/b_2,N_3/b_3,H'}$ respectively (but with ${M}$ unchanged), ${\alpha}$ replaced with its restriction to values coprime to ${d_1,d_2}$ , and ${B}$ set equal to ${b_2 b_3}$ , ${x^\delta}$ replaced by ${d_2 x^\delta}$ , and ${\psi_2,\psi_3}$ replaced by ${\psi_2(b_2\cdot)}$ and ${\psi_3(b_3\cdot)}$ . One can check that all the hypotheses of Proposition 12 are obeyed (with (60) coming from (15), (61) coming from (16), and (62), (63) coming from (17)), so we may bound (64) by

$\displaystyle \lessapprox x^{-\epsilon} M N_2 N_3 \sum_{d = d_1 d_2} \sum_{b_2|d_2} \sum_{b_3|d_2} 1$

which by the divisor bound is ${\lessapprox x^{-\epsilon} M N_2 N_3}$ , which is acceptable.

It remains to prove Proposition 12. Note from (58), (59) one has

$\displaystyle d \gg x^{-\epsilon} N_2. \ \ \ \ \ (65)$

Expanding out the ${\psi_2 \ast \psi_3}$ convolution, our task is to show that

$\displaystyle \sum_{1 \leq h \le H: (h,d)=1} |\sum_{n_2: (n_2,d)=1} \sum_{n_3: (n_3,d)=1} \psi_2(n_2) (\alpha \ast \psi_3)(n_3) e_d( \frac{ah}{n_2n_3} )| \ \ \ \ \ (66)$

$\displaystyle \ll x^{-\epsilon} B MN_2 N_3.$

The next step is Weyl differencing. We will need a step size ${r \geq 1}$ which we will optimise in later. We set

$\displaystyle K := \lfloor x^{-\epsilon} N_2 r^{-1} H^{-1}\rfloor; \ \ \ \ \ (67)$

we will make the hypothesis that

$\displaystyle K \geq 1 \ \ \ \ \ (68)$

and save this condition to be verified later.

By shifting ${n_2}$ by ${khr}$ for ${1 \leq k \leq K}$ and then averaging, we may write the left-hand side of (66) as

$\displaystyle \sum_{1 \leq h \le H: (h,d)=1} |\frac{1}{K} \sum_{1 \leq k \leq K} \sum_{n_2: (n_2,d)=1} \sum_{n_3: (n_3,d)=1}$

$\displaystyle \psi_2(n_2+hkr) (\alpha \ast \psi_3)(n_3) e_d( \frac{ah}{(n_2+hkr)n_3} )|.$

By the triangle inequality, it thus suffices to show that

$\displaystyle \sum_{1 \leq h \leq H: (h,d)=1} \sum_{n_2: (n_2,d)=1} |\sum_{1 \leq k \leq K} \psi_2(n_2+hkr) \ \ \ \ \ (69)$

$\displaystyle \sum_{n_3: (n_3,d)=1} (\alpha \ast \psi_3)(n_3) e_d( \frac{ah}{(n_2+hkr)n_3} )| \ll x^{-\epsilon} B K M N_2 N_3.$

Next, we combine the ${h}$ and ${n_2}$ summations into a single summation over ${{\bf Z}/d{\bf Z}}$ . We first use a Taylor expansion and (67) to write

$\displaystyle \psi_2(n_2+hkr) = \sum_{j=0}^J \frac{1}{j!} (h/H)^j N_2^{j} \psi_2^{(j)}(n_2) (Hkr/N_2)^j + O( x^{-J\epsilon+o(1)})$

for any fixed ${J}$ . If ${J}$ is large enough, then the error term will be acceptable, so it suffices to establish (69) with ${\psi_2(n_2+hkr)}$ replaced by ${(h/H)^j N_2^j \psi_2^{(j)}(n_2) (hkr/N_2)^j}$ for any fixed ${j \geq 0}$ . We can rewrite

$\displaystyle e_d( \frac{ah}{(n_2+hkr)n_3} ) = e_d( \frac{a}{(l+kr) n_3} )$

where ${l \in {\bf Z}/d{\bf Z}}$ is such that ${(l+kr,d)=1}$ and

$\displaystyle l = \frac{n_2}{h}\ (d).$

Thus we can estimate the left-hand side of (69) by

$\displaystyle \sum_{l \in {\bf Z}/d{\bf Z}} \nu(l) |\sum_{1 \leq k \leq K: (l+kr,d)=1} (Hkr/N_2)^j \ \ \ \ \ (70)$

$\displaystyle \sum_{n_3: (n_3,d)=1} (\alpha \ast \psi_3)(n_3) e_d( \frac{a}{(l+kr) n_3})|$

where

$\displaystyle \nu(l) := \sum_{1 \leq h \leq H: (h,d)=1} \sum_{n_2} 1_{l = \frac{n_2}{h}\ (d)} N_2^j |\psi_2^{(j)}(n_2)|.$

Here we have bounded ${(h/H)^j}$ by ${O(1)}$ .

We will eliminate the ${\nu}$ expression via Cauchy-Schwarz. Observe from the smoothness of ${\psi_2}$ that

$\displaystyle \nu(l) \ll x^{o(1)} |\{ (h,n_2): 1 \leq h \leq H; 1 \ll n_2 \ll N_2; (h,d)=1; l = \frac{n_2}{h}\ (d) \}|$

and thus

$\displaystyle \sum_l \nu(l)^2 \ll x^{o(1)} |\{ (h,h',n_2,n'_2): 1 \leq h,h' \leq H; 1\ll n_2,n'_2 \ll N_2;$

$\displaystyle (h,d)=(h',d) = 1; \frac{n_2}{h} = \frac{n'_2}{h'}\ (d) \}|.$

Note that ${\frac{n_2}{h} = \frac{n'_2}{h'}\ (d)}$ implies ${n_2 h' = n'_2 h\ (d)}$ . But from (59) we have ${1 \leq n_2 h', n'_2 h \ll x^\epsilon d}$ , so in fact we have ${n_2 h' = n'_2 h + k d}$ for some ${k = O(x^\epsilon)}$ . Thus

$\displaystyle \sum_l \nu(l)^2 \ll x^{\epsilon+o(1)} |\{ (h,h',n_2,n'_2): 1 \leq h' \leq H; 1\ll n_2 \ll N_2;$

$\displaystyle n_2 h' = n'_2 h + k d \hbox{ for some } k = O(x^\epsilon)\}|.$

From the divisor bound, we see that for each fixed ${n_2, h'}$ there are ${O(x^{\epsilon+o(1)})}$ choices for ${n'_2,h}$ , thus

$\displaystyle \sum_l \nu(l)^2 \lessapprox x^{\epsilon} N_2 H.$

From this, (70), and Cauchy-Schwarz, we see that to prove (69) it will suffice to show that

$\displaystyle \sum_{l \in {\bf Z}/d{\bf Z}} |\sum_{1 \leq k \leq K: (l+kr,d)=1} (Hkr/N_2)^j \ \ \ \ \ (71)$

$\displaystyle \sum_{n_3: (n_3,d)=1} (\alpha \ast \psi_3)(n_3) e_d( \frac{a}{(l+kr) n_3})|^2$

$\displaystyle \ll x^{-3\epsilon} B^{2} K^2 M^2 N_2 N_3^2 H^{-1}.$

We square out (71) as

$\displaystyle \sum_{1 \leq k,k' \leq K}\sum_{l \in {\bf Z}/d{\bf Z}: (l+kr,d)=(l+k'r,d)=1} (Hkr/N_2)^j (Hk'r/N_2)^j$

$\displaystyle \sum_{m,m': (mm',d)=1} \alpha(m) \overline{\alpha(m')}$

$\displaystyle \sum_{n_3,n'_3: (n_3,d)=(n'_3,d)=1} \psi_3(n_3) \overline{\psi_3}(n'_3) e_d( \frac{a}{(l+kr)mn_3)} - \frac{a}{(l+k'r)m'n'_3} ).$

If we shift ${l}$ by ${kr}$ , then relabel ${k'-k}$ by ${k}$ , and use the fact that ${Hkr/N_2, Hk'r/N_2 = O(1)}$ , we can reduce this to

$\displaystyle \sum_{|k| \leq K}$

$\displaystyle |\sum_{l \in {\bf Z}/d{\bf Z}: (l,d)=(l+kr,d)=1} \sum_{n_3,n'_3: (n_3,d)=(n'_3,d)=1} \sum_{m,m': (mm',d)=1} \alpha(m) \overline{\alpha(m')}$

$\displaystyle \psi_3(n_3) \overline{\psi_3}(n'_3) e_d( \frac{a}{lmn_3} - \frac{a}{(l+kr)m' n'_3} )|$

$\displaystyle \ll x^{-3\epsilon} M^2 B^{2} K N_2 N_3^2 H^{-1}.$

Next we perform another completion of sums, this time in the ${n_3,n'_3}$ variables, to bound

$\displaystyle |\sum_{l \in {\bf Z}/d{\bf Z}: (l,d)=(l+kr,d)=1} \sum_{n_3,n'_3: (n_3,d)=(n'_3,d)=1} \sum_{m,m': (mm',d)=1} \alpha(m) \overline{\alpha(m')}$

$\displaystyle \psi_3(n_3) \overline{\psi_3}(n'_3) e_d( \frac{a}{lmn_3} - \frac{a}{(l+kr)m'n'_3} )|$

$\displaystyle \lessapprox \sum_{|m|, |m'| \ll M: (mm',d)=1} \sum_{|t|, |t'| \leq M'} (\frac{N_3}{d})^2 | U(k; t,t'; m,m'; d)|+ x^{-A}$

for any fixed ${A>0}$ , where

$\displaystyle M' := x^{\epsilon} \frac{d}{N_3} \ \ \ \ \ (72)$

(the prime is there to distinguish this quantity from ${M}$ ) and

$\displaystyle U(k;t,t';m,m';d) := \sum_{l \in {\bf Z}/d{\bf Z}: (l,d)=(l+kr,d)=1} \sum_{n_3,n'_3 \in ({\bf Z}/d{\bf Z})^\times}$

$\displaystyle e_d( \frac{a}{lmn_3} - \frac{a}{(l+kr)m'n'_3} + tn_3 - t' n'_3).$

Making the change of variables ${u := \frac{a}{mn_3}\ (d)}$ and ${u' := \frac{a}{m'n'_3}\ (d)}$ , we see that

$\displaystyle U(k;t,t';m,m';d) = T( kr; at/m, at'/m'; d)$

where

$\displaystyle T(k; m,m'; q) := \sum_{l \in {\bf Z}/q{\bf Z}: (l,q)=(l+k,q)=1} \sum_{u \in ({\bf Z}/q{\bf Z})^\times} \sum_{u' \in ({\bf Z}/q{\bf Z})^\times}$

$\displaystyle e_q( \frac{u}{l} - \frac{u'}{l+k} + \frac{m}{u} - \frac{m'}{u'} ).$

Applying the Bombieri-Birch bound (Theorem 4 from this previous post), and recalling that ${a \in ({\bf Z}/d{\bf Z})^\times}$ , we reduce to showing that

$\displaystyle \sum_{|k| \leq K} \sum_{|m|, |m'| \leq M: (mm',d)=1} \sum_{|t|, |t'| \leq M'} \frac{(kr,t/m-t'/m',d)}{(kr,d)^{1/2}} (\frac{N_3}{d})^2 d^{3/2}$

$\displaystyle \lessapprox x^{-4\epsilon} B^{2} K M^2 N_2 N_3^2 H^{-1}.$

We may cross multiply and write

$\displaystyle (kr,t/m-t'/m',d) = (kr,tm'-t'm,d).$

By the divisor bound, for each choice of ${t,m'}$ and ${tm'-t'm}$ there is ${\lessapprox 1}$ choices for ${t'}$ and ${m}$ . Thus it suffices to show that

$\displaystyle MM' \sum_{|k| \leq K} \sum_{|b| \ll MM'} \frac{(kr,b,d)}{(kr,d)^{1/2}} (\frac{N_3}{d})^2 d^{3/2} \lessapprox x^{-4\epsilon} B^{2} K M^2 N_2 N_3^2 H^{-1}.$

We now choose ${r}$ to be a factor of ${d}$ , thus

$\displaystyle d = qr$

for some ${q}$ coprime to ${r}$ . We compute the sum on the left-hand side:

Lemma 13 If ${r|d}$ , then we have

$\displaystyle \sum_{|k| \leq K} \sum_{|b| \ll MM'} \frac{(kr,b,d)}{(kr,d)^{1/2}}$

$\displaystyle \lessapprox ( r^{1/2} K + d^{1/2} + MM' K r^{-1/2} ).$

Proof: We first consider the contribution of the diagonal case ${b=0}$ . This term may be estimated by

$\displaystyle \ll \sum_{|k| \leq K} (kr,d)^{1/2} = r^{1/2} \sum_{|k| \leq K} (k,q)^{1/2}.$

The ${k=0}$ term gives ${d^{1/2}}$ , while the contribution of the non-zero ${k}$ are also acceptable by Lemma 5 from this previous post.

For the non-diagonal case ${b \neq 0}$ , we see from Lemma 5 from this previous post that

$\displaystyle \sum_{|b| \ll M M': b \neq 0} (kr,b,d) \lessapprox MM';$

since ${(kr,d) \geq r}$ , we obtain a bound of ${\lessapprox MM' K r^{-1/2}}$ from this case as required. $\Box$

From this lemma, we see that we are done if we can find ${r}$ obeying

$\displaystyle MM' (r^{1/2} K + d^{1/2} + MM' K r^{-1/2} ) (\frac{N_3}{d})^2 d^{3/2} \ll x^{-5\epsilon} B^{2} K M^2 N_2 N_3^2 H^{-1}. \ \ \ \ \ (73)$

as well as the previously recorded condition (68). We can split the condition (73) into three subconditions:

$\displaystyle M' r^{1/2} d^{-1/2} \ll x^{-5\epsilon} B^{2} M N_2 H^{-1}$

$\displaystyle M' K^{-1} \ll x^{-5\epsilon} B^{2} M N_2 H^{-1}$

$\displaystyle (M')^2 r^{-1/2} d^{-1/2} \ll x^{-5\epsilon} B^{2} N_2 H^{-1}.$

Substituting the definitions (67), (72) of ${K, M'}$ , we can rewrite all of these conditions as lower and upper bounds on ${r}$ . Indeed, (68) follows from (say)

$\displaystyle r \ll x^{-2\epsilon} N_2 H^{-1} \ \ \ \ \ (74)$

while the other three conditions rearrange to

$\displaystyle r \ll x^{-12\epsilon} B^{4} M^2 N_2^2 N_3^2 H^{-2} d^{-1} \ \ \ \ \ (75)$

$\displaystyle r \ll x^{-7\epsilon} B^{2} M N_2^2 N_3 H^{-2} d^{-1} \ \ \ \ \ (76)$

and

$\displaystyle r \gg x^{14\epsilon} B^{-4} N_2^{-2} N_3^{-4} H^2 d^{3}.$

We can replace the first two constraints by the stronger constraint

$\displaystyle r \ll x^{-12\epsilon} B^{2} M N_2^2 N_3 H^{-2} d^{-1} \ \ \ \ \ (77)$

We combine these constraints as

$\displaystyle R_1 \ll r \ll R_2, R_3$

where

$\displaystyle R_1 := x^{14\epsilon} B^{-4} N_2^{-2} N_3^{-4} H^2 d^{3}$

$\displaystyle R_2 := x^{-2\epsilon} N_2 H^{-1}$

$\displaystyle R_3 := x^{-12\epsilon} B^{2} M N_2^2 N_3 H^{-2} d^{-1}.$

From (60), (61) we have

$\displaystyle R_2,R_3 \gtrapprox x^{\delta+c} R_1;$

and from (62), (63) we have ${R_2,R_3 \gg 1}$ . Since ${d}$ is ${x^\delta}$ -densely divisible, we will be done as soon as we verify that

$\displaystyle R_1 \ll d,$

since ${d}$ will then have a factor in ${[x^{-\delta} R, R]}$ where ${R := \max(\min(R_2,R_3,d),1)}$ , which works if ${R_1 \ll x^{-\delta} d}$ (and if ${R_1 \gg x^{-\delta} d}$ we can just take ${d}$ as the factor).

It remains to establish ${R_1 \ll d}$ . But this bound can be rewritten as

$\displaystyle x^{20\epsilon} B^{-6} d^3 H^3 \ll N_2^3 N_3^6$

and the claim follows from (61), (58).

86 comments

Comments feed for this article

23 June, 2013 at 11:12 pm

Terence Tao

Once again recording the latest critical numerology. If we ignore $\delta$ and infinitesimals, then we have

$\varpi = 1/148, \quad \delta = 0$

and the critical term in the Heath-Brown identity is now of the form

$\alpha_0 \ast \psi_1 \ast \psi_2 \ast \psi_3$

where $\psi_1, \psi_2, \psi_3$ are smooth and at scale $x^{(1/2+\sigma)/2}$ and $\alpha_0$ is at scale $x^{1 - 3 (1/2+\sigma)/2}$ with

$\sigma = 9/74 \approx 0.1216,$

thus $\psi_1,\psi_2,\psi_3$ are at scale $x^{23/74} \approx x^{0.3108}$ , and $\alpha$ is at scale $x^{5/74} \approx x^{0.0676}$ . We are still a little bit above the combinatorial constraint $\sigma > 1/10$ but we will be bumping against that pretty soonish.

This critical case is on the Type I / Type III border; both arguments apply to this case, and improving either of them at this choice of parameters should lead to an improvement in the final value of $\varpi$ . (On the other hand, the Type II analysis is not critical here, and we do not urgently need to improve that analysis further for the time being). With the Type I analysis, we may group $\psi_1 \ast \psi_2$ and $\alpha_0 \ast \psi_3$ as $\alpha$ and $\beta$ respectively, and the parameter scales are

$N = x^{1/2 - \sigma} = x^{14/37} \approx x^{0.3784}$

$M = x^{1/2+\sigma} = x^{23/37} \approx x^{0.6216}$

$d, D \approx x^{1/2 + 2 \varpi} = x^{19/37} \approx x^{0.5135}$

$r, R \approx N = x^{14/37} \approx x^{0.3784}$

$q, q_1, q_2, q'_2 \approx Q \approx D/N = x^{5/37} \approx x^{0.1351}$

$k \approx N/R \approx 1$

$h, h', H \approx Q^2 R/M \approx x^{1/37} \approx x^{0.0270}$ .

In Lemma 10, it is the middle term $N^{1/2} Q$ which dominates slightly, suggesting that there is a little bit of gain to be had by refactoring to reduce $d_2$ and increase $d_1$ .

Meanwhile, in the Type III analysis, the numerology is

$M = x^{5/74} \approx x^{0.0676}; \quad N_1=N_2=N_3 = x^{23/74} \approx x^{0.3108}$

$d \approx x^{1/2+2\varpi} = x^{19/37} \approx x^{0.5135}$

$h,H \approx d/N_2 \approx x^{15/74} \approx x^{0.2027}$

$B \approx 1$

$M' \approx d/N_3 \approx x^{15/74} \approx x^{0.2027}$

$r,R_1,R_3 \approx x^{3/37} \approx x^{0.0811}$

$R_2 \approx x^{7/74} \approx x^{0.0946}$

$k,K \approx N_2/rH \approx x^{1/37} \approx x^{0.0270}$

In Lemma 13 the last two terms on the RHS are equal and dominant.

30 June, 2013 at 11:01 pm

v08ltu

I am confused, in (49) you give a constraint for Type II that has $5\sigma\le 1/2$ (in particular), but then you take $\sigma\approx 0.1216$ ? Is $\mu$ allowed to be negative?

30 June, 2013 at 11:04 pm

v08ltu

OK, I guess you explain it right below (49), that “ $\sigma$ ” is really not such, but a different thing that is really only $2\omega$ .

23 June, 2013 at 11:50 pm

v08ltu

I think reshufffling the divisors to reduce $\sqrt NQ$ slightly, would make $101\omega+21\delta\le 3/4$ dominant, maybe with such extra $\delta$ ‘s from this shuffling. The theoretical limit from $\omega=3/404$ is then $k_0=1267$ , and I can achieve $k_0=1268$ rather easily.

24 June, 2013 at 12:20 am

David Roberts

$k_0 = 1267$ gives us $H = 10 182$ and $k_0 = 1268$ gives us $H = 10 206$ .

To get $H$ below 10 000 using current admissible tuples we need $k_0 = 1246$ .

(commenting mostly to get updates, but this will save others searching though the files for records)

24 June, 2013 at 8:36 am

Terence Tao

Hmm, I get slightly different numerology, though there are a number of details and lower order terms to check. As $q_1 r$ , $q_2 r$ , $q'_2 r$ are already $x^\delta$ -densely divisible by construction, one should be able to reshuffle to improve the bound in (51) to

$\lessapprox x^{\delta/6} N^{1/2} (Q^3 R)^{1/6} + N R^{-1/4} (hq'_2 -h'q_2,r)^{1/4}$

(I think), which leads to a primary constraint of

$x^{\delta/6} H^2 Q^2 N^{1/2} (Q^3 R)^{1/6} \ll Q^2 N$

(ignoring epsilons) for Theorem 8, which after some algebra is giving me the constraint

$\frac{\delta}{6} + \frac{9}{2} (\frac{1}{2}+2\varpi) < 2 + \frac{5}{6} (\frac{1}{2} - \delta) - \frac{7}{3}(\mu+\delta)$

which simplifies to

$54 \varpi + 5 \sigma + 15 \delta < 1$

which when rebalanced against $\sigma > \frac{1}{10} + \frac{16}{5} \varpi + \frac{1}{5} \delta$ which is the best Type III constraint we currently have, seems to give

$140 \varpi + 32 \delta < 1$

which is a little more strict than your condition, though still an improvement over $148 \varpi + 33 \delta < 1$ .

24 June, 2013 at 7:03 pm

Hannes

I think $140 \varpi + 32 \delta < 1$ leads to $k_0=1345$ by choosing $A=625$ , $\delta'=0.0547$ and $\varpi=1/140 - 0.55 \cdot 10^{-10}$ .

24 June, 2013 at 7:18 pm

Hannes

I retract that. Error from too low numerical precision.

24 June, 2013 at 10:28 pm

Hannes

I think this is more correct.
For $k_0=1346$ choose:
$A=560, \delta'=0.00715, \varpi=\frac{1}{140}-\frac{0.3672}{10^5}$ .

25 June, 2013 at 8:43 am

Terence Tao

Confirmed by maple…

varpi := 1/140 - 0.3672 / 10^5; k0 := 1346; deltap := 0.00715; A := 560;

delta := (1 - 140 * varpi) / 32; theta := deltap / (1/4 + varpi); # Gergely's improved value for thetat thetat := ((deltap - delta)/2 + varpi) / (1/4 + varpi); deltat := delta / (1/4 + varpi); j := BesselJZeros(k0-2,1); eps := 1 - j^2 / (k0 * (k0-1) * (1+4*varpi)); kappa1 := int( (1-t)^((k0-1)/2)/t, t = theta..1, numeric); kappa2 := (k0-1) * int( (1-t)^(k0-1)/t, t=theta..1, numeric); # using Gergely and Eytan's improved kappa_3 alpha := j^2 / (4 * (k0-1)); e := exp( A + (k0-1) * int( exp(-(A+2*alpha)*t)/t, t=deltat..theta, numeric ) ); # using Gergely's exact expression for denominator gd := (j^2/2) * BesselJ(k0-3,j)^2; # using Eytan's exact expression for numerator tn := sqrt(thetat)*j; gn := (tn^2/2) * (BesselJ(k0-2,tn)^2 - BesselJ(k0-3,tn)*BesselJ(k0-1,tn)); kappa3 := (gn/gd) * e; eps2 := 2*(kappa1+kappa2+kappa3);

# we win if eps2 < eps

24 June, 2013 at 5:33 am

Gergely Harcos

I am a bit confused when you say (several times) that $MPZ[\varpi,\delta]$ is stronger than $MPZ'[\varpi,\delta]$ . I think it is the other way, since $MPZ'[\varpi,\delta]$ bounds a sum with more summands. In fact in the post https://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/ you said “we can prove a stronger result than $MPZ[\varpi,\delta]$ in this regime in a couple ways”.

24 June, 2013 at 7:50 am

Terence Tao

Gah, you’re right, I do have it the wrong way around, I will fix this.

24 June, 2013 at 1:16 pm

Pace Nielsen

In (2), the $n$ on the RHS should be $x$ .

In the statement of Theorem 9, you may wish to include the assumption $M \ll x^{1/2+2\varpi +c}$ .

In the statement of Lemma 13, you may wish to include the assumption that $r | d$ .

[Corrected, thanks – T.]

24 June, 2013 at 8:14 pm

Pace Nielsen

A few more minor corrections.

1. In the second bullet point (for type I/II) I believe the $n$ should be $2j$ , which gets confusing since in the next line there is a second meaning for $j$ .

2. In the line after those bullets “Type O” should be “Type 0”.

3. A few lines later when it says “the condition (9), (10) are obeyed” I believe you also want to include (11).

4. Earlier in the sentence containing equation (30), the $q$ should be $d$ .

5. In the offset equation before (31), did you want to write $r \sim R$ instead of $R \ll r \ll R$ (and similarly for $q,Q$ )?

6. In the second line of (37), there is an extra right parenthesis.

7. In the second offset equation after Lemma 10, there is a missing right absolute value bar.

8. In the statement of Proposition 12, it ends with “for some fixed $\epsilon > 0$ .” However, $\epsilon$ occurs earlier in (58). Furthermore, in the type III analysis done at the beginning of the post, I believe you take $\epsilon$ arbitrarily small. (I believe you meant, in Proposition 12, for $\epsilon$ to be a fixed, but arbitrarily small, constant [defined before (58)].)

[Corrected, thanks – T.]

25 June, 2013 at 4:46 pm

Terence Tao

Emmanuel Kowalski has just posted on his blog at

http://blogs.ethz.ch/kowalski/2013/06/25/a-ternary-divisor-variation

a sketch of his new Type III estimate with Fouvry, Michel, and Nelson. I will reproduce their argument in the notation of the blog post above. The objective is to obtain an estimate of the form

$\sum_{q \sim Q} |\Delta(\alpha * \psi_1 * \psi_2 * \psi_3; a_q\ (q))| \lessapprox x^{-\varepsilon} M N_1 N_2 N_3$

for $Q$ as large as possible (in particular, as large as $x^{1/2+2\varpi}$ ), but restricted to be square-free and $x^\delta$ -densely divisible. By the dense divisibility, it will suffice to show that

$\sum_{r \sim R} \sum_{s \sim S: (r,s)=1} |\Delta(\alpha * \psi_1 * \psi_2 * \psi_3; a_{rs}\ (rs))| \lessapprox x^{-\varepsilon} M N$

for $RS=Q$ that we can specify to accuracy $x^\delta$ , thus we may place $R$ in $[x^{-\delta} R_0, R_0]$ for some $R_0$ to be chosen later, and $N = N_1 N_2 N_3$ .

FKMN do not exploit any averaging in $\alpha$ or $s$ ; one can probably exploit the former to improve upon their results but we will not do so here. Removing those averages, we are now looking at

$\sum_{r \sim R: (r,s)=1} |\Delta(\psi_1 * \psi_2 * \psi_3; a_{rs}\ (rs))| \lessapprox x^{-\varepsilon} N / S.$

This may be rewritten as

$\sum_r c_r \sum_{n_1,n_2,n_3} \psi_1(n_1) \psi_2(n_2) \psi_3(n_3) 1_{n_1n_2n_3 = a_{rs}\ (rs)}$

$= X + O( x^{o(1)} N / S )$

where $X$ does not depend on the residues $a_{rs}$ , and the $c_r$ are bounded and only supported on those $r \sim R$ coprime to $s$ . Performing completion of sums in the $n_1,n_2,n_3$ variables, the left-hand side can be expressed as

$\frac{1}{H} \sum_{h_1=O(H_1), h_2 = O(H_2), h_3 = O(H_3); h_1h_2h_3 \neq 0} | \sum_r c_r$

$\sum_{x,y,z \in {\bf Z}/rs{\bf Z}: xyz = a_{rs}\ (rs)} e_{rs}(h_1 x + h_2 y + h_3 z)$ (*)

plus terms which do not depend on $a_{rs}$ (coming from the cases when at least one of the $h_i$ vanish), where $H_i = Q/N_i$ and $H = H_1 H_2 H_3 = Q^3/N$ . The inner sum may be rescaled as

$rs K_3( a_{rs} h_1 h_2 h_3; rs )$

where $K_3$ is the hyper-Kloosterman sum

$K_3(a;q) = \frac{1}{q} \sum_{x,y,z \in {\bf Z}/q{\bf Z}: xyz=a} e_q(x+y+z)$ .

The $h_1,h_2,h_3$ now only appear through their product, and so we may gather terms and write the expression (*) as

$\frac{Q}{H} \sum_{h = O(H): h \neq 0} \tilde d_3(h) \sum_r c'_r K_3( a_{rs} h; rs )$

where $\tilde d_3(h)$ is the number of representations $h=h_1h_2h_3$ with $h_i=O(H_i)$ and $H = H_1 H_2 H_3 = Q^3 / N$ , and $c'_r = rs c_r / Q$ is another bounded sequence. The objective is now to show

$\sum_{h = O(H): h \neq 0} \tilde d_3(h) |\sum_r c'_r K_3( a_{rs} h; rs )| \lessapprox x^{-\varepsilon} N H / S Q.$

Note that $NH/SQ = Q R$ . Deligne tells us that $K_3 \lessapprox 1$ , which bounds the LHS by $H R$ , but this only works in the Bombieri-Vinogradov regime $Q \ll N^{1/2}$ . To do better we apply Cauchy-Schwarz to eliminate the $\tilde d_3$ term and gain another unweighted index $h$ to sum over. From the divisor bound one has

$\sum_{h = O(H): h \neq 0} \tilde d_3(h)^2 \lessapprox H$

so it suffices to show that

$\sum_{h = O(H)} |\sum_r c'_r K_3( a_{rs} h; rs )|^2 \lessapprox x^{-2\varepsilon} Q^2 R^2 / H.$ (**)

We can rearrange the LHS as

$\sum_{r_1, r_2} c'_{r_1} \overline{c'_{r_2}}$

$\sum_{h = O(H)} K_3(a_{r_1s} h; r_1s) \overline{K_3(a_{r_2s} h; r_2s)}$ .

The summand is periodic in h with period $[r_1,r_2] s$
One then performs completion of sums in $h$ , using the Chinese remainder theorem and Deligne’s estimates to estimate the completed sums, and eventually ends up with a bound on the inner sum of the form

$\lessapprox (\frac{H}{[r_1,r_2] s} + 1)$
$d (s/d)^{1/2} r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}$

where $r_0 := (r_1,r_2)$ and $d := (r_1^3-r_2^3, s)$ . So now one has to sum

$\sum_{r_1,r_2 \sim R: (r_1r_2, s) = 1}$
$(\frac{H r_0}{r_1 r_2 s} + 1) d (s/d)^{1/2} r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}.$

A computation shows that for each choice of $r_0 = O(R)$ and $d|s$ , the number of pairs $r_1,r_2$ with $r_0=(r_1,r_2)$ and $d = (r_1^3-r_2^3,s)$ is $\lessapprox \frac{R^2}{r_0^2 d} + \frac{R}{r_0}$ . So now one is summing

$\sum_{d|s} \sum_{r_0=O(R)} (\frac{R^2}{r_0^2 d} + \frac{R}{r_0})$

$(\frac{H r_0}{r_1 r_2 s} + 1) d (s/d)^{1/2} r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}$ .

One can perform the $d$ summation without difficulty and end up with

$\lessapprox \sum_{r_0=O(R)} (\frac{R^2 s^{1/2}}{r_0^2} + \frac{R s}{r_0})$

$(\frac{H r_0}{r_1 r_2 s} + 1) r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}$ ,

and then performing the $r_0$ summation this becomes

$\lessapprox H R S^{-1/2} + R^3 S^{1/2} + HR + S R^2$ .

The first term is bounded by the third and can be dropped. We also crudely bound the secondary term $SR^2$ by $S^{3/2}R^2$ .
To make this less than $x^{-2\varepsilon} Q^2 R^2 / H$ , this is equivalent to requiring (ignoring epsilons)

$H^2/Q^2, H^{2/3}/Q^{1/3} \lessapprox R \lessapprox Q^3 / H^2$ .

The expression $H^{2/3}/Q^{1/3}$ is a geometric average $(H^2/Q^2)^{2/3} (Q^3/H^2)^{1/3}$ of the other two and so the $H^2/Q^2$ term may be dropped. This already forces $H \lessapprox Q^{5/4}$ . As we may specify $R$ to accuracy $x^\delta$ , we win as soon as

$x^\delta H^{2/3} / Q^{1/3} \lessapprox Q^3 / H^2$

which rearranges to

$H \lessapprox x^{-3\delta/8} Q^{5/4}$

or equivalently

$N \gtrapprox x^{3\delta/8} Q^{7/4}$

thus

$N_1 N_2 N_3 \gtrapprox x^{\frac{7}{4}(\frac{1}{2}+2\varpi) + \frac{3}{8} \delta}$ .

In terms of $\sigma$ , this gives a constraint

$\frac{3}{2} (\frac{1}{2} + \sigma) > \frac{7}{4} (\frac{1}{2} + 2 \varpi) + \frac{3}{8} \delta$

which can be rearranged as

$\sigma > \frac{1}{12} + \frac{7}{3} \varpi + \frac{1}{4} \delta$ . (1)

We also have

$\sigma > 1/10$ . (2)

If we play this against the Type I constraints

$17 \varpi + 4 \delta + \sigma < \frac{1}{4}$ (3)

$20 \varpi + 6\delta + 3\sigma < \frac{1}{2}$ (4)

$32 \varpi + 9 \delta + \sigma < \frac{1}{2}$ (5)

$48\varpi + 7 \delta < \frac{1}{2}$ (6)

in the main post, one ends up with

$116 \varpi + \frac{51}{2} \delta < 1$ (1+3)

$108 \varpi + 25 \delta < 1$ (1+4)

$412 \varpi + 111 \delta < 5$ (1+5)

$280 \varpi + 80 \delta < 3$ (2+3)

$100 \varpi + 30 \delta < 1$ (2+4)

$160 \varpi + 45 \delta < 2$ (2+5)

$96 \varpi + 14 \delta < 1$ (6)

leaving one with the final constraint

$116 \varpi + 30 \delta < 1$

coming from merging the (1+3) and (2+4) estimates (this is not quite optimal, but will do for now).

This should be improvable once we flesh out the improved Type I estimates currently being discussed at https://terrytao.wordpress.com/2013/06/22/bounding-short-exponential-sums-on-smooth-moduli-via-weyl-differencing/ . But the fact that all the different combinations (1+3), …, (6) are beginning to surface means that we will have to start fighting on a lot of fronts to get more improvement from here on.

25 June, 2013 at 6:27 pm

Hannes

$k_0=1007, A=396, \delta'=0.0085, \varpi=1/116 - 0.62/10^5$

25 June, 2013 at 6:36 pm

David Roberts

And if confirmed, a prime gap bound of 7860.

25 June, 2013 at 9:26 pm

Terence Tao

confirmed by maple, going on the wiki :)

varpi := 1/116 - 0.62 / 10^5; k0 := 1007; deltap := 0.0085; A := 396;

delta := (1 - 116 * varpi) / 30; theta := deltap / (1/4 + varpi); # Gergely's improved value for thetat thetat := ((deltap - delta)/2 + varpi) / (1/4 + varpi); deltat := delta / (1/4 + varpi); j := BesselJZeros(k0-2,1); eps := 1 - j^2 / (k0 * (k0-1) * (1+4*varpi)); kappa1 := int( (1-t)^((k0-1)/2)/t, t = theta..1, numeric); kappa2 := (k0-1) * int( (1-t)^(k0-1)/t, t=theta..1, numeric); # using Gergely and Eytan's improved kappa_3 alpha := j^2 / (4 * (k0-1)); e := exp( A + (k0-1) * int( exp(-(A+2*alpha)*t)/t, t=deltat..theta, numeric ) ); # using Gergely's exact expression for denominator gd := (j^2/2) * BesselJ(k0-3,j)^2; # using Eytan's exact expression for numerator tn := sqrt(thetat)*j; gn := (tn^2/2) * (BesselJ(k0-2,tn)^2 - BesselJ(k0-3,tn)*BesselJ(k0-1,tn)); kappa3 := (gn/gd) * e; eps2 := 2*(kappa1+kappa2+kappa3);

# we win if eps2 < eps

25 June, 2013 at 10:57 pm

Hannes

Asking Maple for more digits (Digits := …) will cause this script to fail. However, I believe it will work after correcting the typo in the expression for delta. :-)

[Corrected, thanks – T.]

26 June, 2013 at 7:35 am

Terence Tao

Actually the treatment of the degenerate $h_1,h_2,h_3$ terms is a bit more difficult than I claimed, because the rescaling identity

$\sum_{x,y,z \in {\bf Z}/rs{\bf Z}: xyz = a_{rs}\ (rs)} e_{rs}(h_1 x + h_2 y + h_3 z)$

$= \sum_{x,y,z \in {\bf Z}/rs{\bf Z}: xyz = a_{rs} h_1 h_2 h_3\ (rs)} e_{rs}(x + y + z)$

is only true when $h_1,h_2,h_3$ are coprime to $rs$ . One should be able to eliminate the non-coprime cases by introducing some “B” parameters as in the blog post treatment of the Type III case but it will get a bit messy. In principle it should work because whenever one or two of the $h_i$ share a common prime $p$ with $rs$ , one picks up two or one Ramanujan sums in the $p$ modulus which should safely counteract all the losses coming elsewhere from having to enforce such divisibility conditions. One also has to deal with the case when all of the $h_1,h_2,h_3$ have a common factor; this should be handled by factoring out these common factors from $h_1,h_2,h_3,r,s$ and inserting “B” terms to measure the losses and gains. In past experience there were always many powers of B to spare, so I don’t think this is a major issue, but it does need to be addressed at some point.

26 June, 2013 at 10:08 am

Terence Tao

OK, the treatment of the non-coprime case ends up being slightly tricky, one has to force coprimality $(h,q)=1$ before performing the factoring $q=rs$ because one needs to optimise the factoring with respect to the common factor in order to get a convergent series.

Here are some details. The key estimate is

Proposition Let $H, Q$ be of polynomial size. If $c_q$ are bounded and supported on $y$ -densely divisible squarefree $q \sim Q$ , then

$\sum_{h = O(H)} | \sum_{q: (h,q)=1} c_q K_3( a_q h; q)| \lessapprox y^{3/16} H^{1/2} Q^{11/4} + y^{1/8} H Q^{3/4}$ .

Proof By pigeonholing and dense divisbility we may factor $q=rs$ with $r \sim R$ , $s \sim S$ with

$y^{-1/4} Q^{1/2} \ll R \ll y^{3/4} Q^{1/2}$

and

$y^{-3/4} Q^{1/2} \ll S \ll y^{1/4} Q^{1/2}$ .

It then suffices to show that

$\sum_{h = O(H)} | \sum_{r: (h,r)=1} \sum_{s: (h,s)=(h,r)=1} c_{r,s} K_3( a_{rs} h; {rs})| \lessapprox x^{3\delta/16} H Q^{7/4} + x^{\delta/4} H^2 Q^{1/2}$ (*)

for some bounded $c_{r,s}$ that is supported on coprime $r \sim R$ and $s \sim s$ .

We pull the s summation out and then Cauchy-Schwarz in h to bound this by

$\lessapprox H^{1/2} \sum_s (\sum_{h: (h,s)=1} |\sum_{r: (h,r)=1} c_{r,s} K_3( a_{rs} h; {rs})|^2)^{1/2}$ .

The sum inside the parentheses can be estimated using the previous arguments as

$\lessapprox R^3 S^{1/2} + HR + S^{3/2} R^2$

so the LHS of (*) is

$\lessapprox H^{1/2} S (R^3 S^{1/2} + HR + S^{3/2} R^2 )^{1/2}$

which we can rewrite as

$\lessapprox H^{1/2} Q^{5/4} R^{1/4} + H Q^{1/2} S^{1/2} + H^{1/2} Q S^{3/4}$

and the claim then follows from the upper bounds on R,S. $\Box$

Now back to the Type III estimates. We wish to show

$\sum_q c_q \sum_{n_1,n_2,n_3} \psi_1(n_1) \psi_2(n_2) \psi_3(n_3) 1_{n_1 n_2 n_3 = a_q\ (q)} = X + O(x^{-\varepsilon} N)$

where $X$ does not depend on the $a_q$ . After completion of sums and removing the degenerate frequencies, this becomes

$\sum_{h_1=O(H_1),h_2=O(H_2),h_3=O(H_3): h_1h_2h_3 \neq 0} |\sum_q c'_q F(h_1,h_2,h_3,a_q;q)| \lessapprox x^{-\varepsilon} Q^2$

where

$F(h_1,h_2,h_3,a_q;q) := \frac{1}{q} \sum_{x,y,z \in {\bf Z}/q{\bf Z}: xyz=a_q\ (q)} e_q( h_1 x + h_2 y + h_3 z)$

would morally be the hyper-Kloosterman sum $K_3(h_1h_2h_3a_q;q)$ except that we do not yet have that $h_1,h_2,h_3$ are coprime to $q$ .

Suppose that $(h_i,q) = b_i$ . Writing $h_i= b_i h'_i$ , $b := [b_1,b_2,b_3]$ and $q = b q'$ , we can use the Chinese remainder theorem and Ramanujan sum bounds to factor $F(h_1,h_2,h_3,a_q;q)$ as $K_3( h'_1 h'_2 h'_3 a_{q'} / b^3; q' )$ times a factor independent of $q'$ of magnitude $\frac{b_1 b_2 b_3}{b^2}$ (we skip this computation, it boils down to checking a bunch of cases when $q$ consists of a single prime $p$ ). For each fixed $b_1,b_2,b_3$ , we apply the Proposition with H replaced by $H/b_1b_2b_3$ and $Q$ replaced by $Q/b$ , noting that the modulus $q'$ is now only $b x^\delta$ -densely divisible instead of $x^\delta$ -densely divisible, and one ends up with a total bound of

$\lessapprox \sum_{b_1,b_2,b_3} (b x^\delta)^{3/16} (\frac{H}{b_1b_2b_3})^{1/2} (Q/b)^{11/4}$

$+ (bx^\delta)^{1/8} \frac{H}{b_1b_2b_3} (Q/b)^{3/4}.$

Fortunately, the net power of b here in the denominator is greater than 1, and the b summation converges (as can be seen by taking Euler products) to get a bound of

$\lessapprox x^{3\delta/16} H^{1/2} Q^{11/4} + x^{\delta/8} H Q^{3/4}$

which is $\lessapprox x^{-\varepsilon} Q^2$ as required if

$H \lessapprox x^{-3\delta/8 - 2\varepsilon} Q^{5/4}$

and we are back to the same numerology as before. So the coprimality thing is a moderate pain to deal with, but fortunately doesn’t seem to ultimately impact the final estimates.

26 June, 2013 at 7:51 am

Pace Nielsen

Plugging in the constraints (1+3), (1+4), (1+5), (2+3), (2+4), (2+5), and (6) into Mathematica’s “Reduce” function (which I love by the way) yields the final constraints (if I copied everything correctly):

$100\varpi +30\delta < 1$ when $\varpi\leq 3/620$

$116\varpi + 25.5\delta < 1$ when $3/620 < \varpi\leq 233/18460$

$82.4\varpi + 2.2\delta < 1$ when $233/18460 < \varpi$

26 June, 2013 at 10:15 am

Terence Tao

Thanks! There is also the trivial constraint $\delta > 0$ which presumably kills off the third case here, so for the regime of $\varpi$ we are currently shooting for, the $116 \varpi + 25.5 \delta < 1$ condition is dominant.

2 July, 2013 at 9:47 am

Gergely Harcos

In the Wiki page (http://michaelnielsen.org/polymath1/index.php?title=Distribution_of_primes_in_smooth_moduli) the condition $116 \varpi + 25.5 \delta < 1$ has been misprinted as $116 \varpi + 22.5 \delta < 1$ .

[Fixed, thanks – T.]

26 June, 2013 at 10:26 am

Gergely Harcos

Can you share your code? Sounds like a nice function of Mathematica indeed.

26 June, 2013 at 10:56 am

Pace Nielsen

The code is actually quite simple which is why I like the function so much. If I had been thinking straight, I would have added the extra conditions $0 < \varpi < 1/4$ , etc. The downside is that it is all automated, and so (in the final write-up) we may need to rederive the necessary inequalities. (But that shouldn't be too hard, given that we would know what to look for.)

All I typed was: Reduce[116p + (51/2)d<1 && 108p+25d<1 && … ]

This should be able to deal with any sort of polytope issues (at least for a small number of variables).

26 June, 2013 at 11:04 am

Hannes

An alternative is to just draw the lines… This is maple code:
with(plots):


eq := [116*varpi + 51/2*delta = 1,

       108*varpi +   25*delta = 1,

       412*varpi +  111*delta = 5,

       280*varpi +   80*delta = 3,

       100*varpi +   30*delta = 1,

       160*varpi +   45*delta = 2,

        96*varpi +   14*delta = 1]:
max_v := min(seq( eval(solve(e, varpi), delta=0), e in eq ));

max_d := min(seq( eval(solve(e, delta), varpi=0), e in eq ));

implicitplot(eq, varpi=0..max_v, delta=0..max_d, color=[blue,black,black,black,red,black,black]);

26 June, 2013 at 11:10 am

Gergely Harcos

Thank you guys, such tricks save time!

26 June, 2013 at 1:54 pm

Terence Tao

I found some Maple code (LinearMultivariateSystem) that does something similar, and allows me to plug in the Type I, Type II, and Type III constraints directly without having to manually play off the inequalities against each other. The (varpi,delta,sigma) polytope ends up being a bit messy but it does confirm that the main constraint is $116 \varpi + 25.5 \delta < 1$ when $1/124 \leq \varpi < 1/116$ .

with(SolveTools[Inequality]);


base := [ sigma > 1/10, sigma < 1/2, varpi > 0, varpi < 1/4, delta > 0, delta < 1/4+varpi ];
typeI_1 := [ 11 * varpi + 3 * delta + 2 * sigma < 1/4 ];
typeI_2 := [ 17 * varpi + 4 * delta + sigma < 1/4, 20 * varpi + 6 * delta + 3 * sigma < 1/2, 32 * varpi + 9 * delta + sigma < 1/2 ];
typeII_1 := [ 58 * varpi + 10 * delta < 1/2 ];
typeII_1a := [48 * varpi + 7 * delta < 1/2 ];
typeIII_1 := [ (13/2) * (1/2 + sigma) > 8 * (1/2 + 2*varpi) + delta ];
typeIII_2 := [ 1 + 5 * (1/2 + sigma) > 8 * (1/2 + 2*varpi) + delta ];
typeIII_3 := [ 3/2 * (1/2 + sigma) > (7/4) * (1/2 + 2*varpi) + (3/8) * delta ];
constraints := [ op(base), op(typeI_2), op(typeII_1a), op(typeIII_3) ];

LinearMultivariateSystem(constraints, [varpi,delta,sigma]);

25 June, 2013 at 7:00 pm

Terence Tao

This comment is an attempt to summarise the many different advances we have (whether worked out in full, or only partially sketched so far) on the problem of getting $\varpi,\delta$ as large as possible. To simplify this overview I will not make a distinction between $MPZ[\varpi,\delta]$ or $MPZ'[\varpi,\delta]$ (so I will not distinguish between smoothness, dense divisibility, or “double dense divisibility”).

These estimates are obtained by a combination of three types of estimates: Type I estimates, Type II estimates, and Type III estimates. We have various levels of technological advance on each of these estimates, with a question mark indicating that this technology has not yet been fully fleshed out:

Type I-1: Zhang’s original argument bounding Type I estimates. Uses the bound on incomplete Kloosterman sums coming from completion of sums.

Type I-2: A refinement to Type I-1 coming from using q-van der Corput in the d_2 direction to improve the bounds on incomplete Kloosterman sums.

Type I-3?: A refinement to Type I-2 coming from refactoring the modulus d=d_1 d_2 to optimise the direction in which to apply q-van der Corput.

Type I-4?: A further refinement coming from iterating the q-van der Corput method.

Type I-5??: A yet further refinement taking advantage of additional averaging to reduce the contribution of diagonal terms.

Type II-1, Type II-2?, Type II-3?, Type II-4?, Type II-5??: Analogues of Type I-1 to Type I-5?? for the Type II sums.

Type III-1: Zhang’s original argument bounding Type III modulus, using Weyl differencing and not taking advantage of the alpha averaging.

Type III-2: Refinement of Type III-1 taking advantage of the alpha averaging to reduce the contribution of diagonal terms.

Type III-3: The new Fouvry-Kowalski-Michel argument avoiding Weyl differencing. Does not take advantage of the alpha averaging.

Type III-4?: Combining Fouvry-Kowalski-Michel with the alpha averaging.

Now a quick summary of progress so far:

* Zhang’s original argument uses Type I-1 + Type II-1 + Type III-1. This was optimised to give the constraint $207\varpi + 43\delta < 1/4$ .

* By upgrading Type III-1 to Type III-2, we computed the numerology for Type I-1 + Type II-1 + Type III-2 and got $87\varpi + 17 \delta < 1/4$ .

* By upgrading Type I-1 to Type I-2, we computed the numerology for Type I-2 + Type II-1 + Type III-2 and got $148 \varpi + 33 \delta < 1$ , as described in the post above. (I had earlier computed Type I-2 + Type II-1 + Type III-1 to get the inferior constraint $178\varpi + 52 \delta < 1$ .)

* By upgrading Type I-2 to Type I-3?, and using Type I-3? + Type II-1 + Type III-2, we have tentatively computed either $101\varpi + 21\delta < 3/4$ or $140 \varpi + 32\delta < 1$ (this discrepancy is not yet resolved).

* A very sketchy projection of Type I-4? + Type II-1 + Type III-2 suggests that $\varpi$ could get as large as 1/74 (or 1/88 if we only use Type III-1 instead of Type III-2), except that the Type II-1 estimates start failing at 1/96. However this can presumably be overcome by upgrading Type II-1 to something better, such as Type II-2? or Type II-3?; we have not yet bothered to do anything to the Type II sums but we should probably do so soon.

* In the comments above, I have worked out the numerology for Type I-2 + Type II-1 + Type III-3 and obtained $116 \varpi + 30 \delta < 1$ .

Clearly there is a lot more progress to be made. Ideally we can work out the details of all the different estimates above and arrive at Type I-5 + Type II-5 + Type III-4 which should give significantly better values of $\varpi,\delta$ than we currently have.

One can view each of these estimates as working on some polytope in $(\varpi,\delta,\sigma)$ parameter space, with $MPZ[\varpi,\delta]$ (or some variant thereof) holding if one can find a $1/10 < \sigma < 1/2$ such that $(\varpi,\delta,\sigma)$ simultaneously lies in a Type I-polytope, a Type II-polytope, and a Type III-polytope.

I think I will write up a wiki page to organise all this.

25 June, 2013 at 9:22 pm

Terence Tao

The wiki page is now up:

http://michaelnielsen.org/polymath1/index.php?title=Distribution_of_primes_in_smooth_moduli

In the next day or two I’ll start on systematically working out the various levels of Type I, Type II, and Type III estimates that we currently have, which should lead to a sequence of improvements to $\varpi, \delta$ .

25 June, 2013 at 9:58 pm

aviwlevy

There seems to be a missing comment hyperlink under Type I, Level 4 on the new wiki page.

[Corrected, thanks – T.]

25 June, 2013 at 9:42 pm

Emmanuel Kowalski

I hope it is explicit enough in what I wrote on my blogs that we worked with Paul Nelson on this…

[Sorry about that! I’ve updated the attributions accordingly. -T.]

25 June, 2013 at 9:54 pm

Emmanuel Kowalski

Thanks; the summary page of the Wiki also has one mistake, and also the summary two comments above (Type III-3, Type III-4?)…

[Corrected, thanks – T.]

26 June, 2013 at 2:51 pm

Terence Tao

The purpose of this comment is to record the details of the “Level 3” Type I estimate, which optimises the direction in which the q-van der Corput A-process (aka Weyl differencing) is applied, in the context of densely divisible moduli. This was sketched already in https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli but is done here a little more carefully (in particular, a secondary constraint on $\varpi,\delta,\sigma$ can now be shown to be dropped).

First, a convenient fact: if $a, b$ are both $y$ -densely divisible, then $[a,b]$ is also $y$ -densely divisible. This is because at least one of $a,b$ must be as large as $[a,b]^{1/2}$ ; if say $a$ is this large then one can use the factors of $a$ , together with the factors of $a$ times $[a,b]/a$ , to demonstrate the dense divisibility of $[a,b]$ .

In particular, in the context of Lemma 10 above, the quantity $q_1 r [q_2,q'_2]$ is $x^\delta$ -densely divisible, because $q_1 r, q_2 r, q'_2 r$ are $x^\delta$ -densely divisible by construction.

Next, a Kloosterman sum bound: if

$S := \sum_n \psi_N(n) e_{d_1}(\frac{c_1}{n}) e_{d_2}(\frac{c_2}{n+l})$

with $d_1,d_2$ squarefree and coprime with $d_1 d_2$ $x^\delta$ -densely divisible, then for any other factorisation $d = s_1 s_2$ of $d$ , we may use the k=1 van der Corput bound from this comment and bound

$|S| \lessapprox N^{1/2} (s'_1)^{1/2} + N^{1/2} (s'_2)^{1/4}$

if $N < d'$ , where $d' := d / (c_1,d_1) (c_2,d_2)$ , $s'_1 = (s_1,d')$ , and $s'_2 := (s_2,d')$ . If we choose a factorisation $d_1 d_2 = s_1 s_2$ with $x^{-2\delta/3} (d_1d_2)^{1/3} \leq s_1 \leq x^{\delta/3} (d_1 d_2)^{1/3}$ in this case, we end up with

$|S| \lessapprox N^{1/2} x^{\delta/6} (d_1 d_2)^{1/6}$ .

In the opposite case when $N > d'$ , we basically have from completion of sums that

$|S| \lessapprox \frac{N}{d'} |\sum_{n \in {\bf Z}/d'{\bf Z}} e_{d_1}(\frac{c_1}{n}) e_{d_2}(\frac{c_2}{n+l})|$

(strictly speaking we need to improve $N > d'$ to $N > x^\varepsilon d'$ to get something like this, but let’s ignore this detail) and by computing the degenerate completed Kloosterman sum we obtain a bound of $\lessapprox N/d' = \frac{(c_1,d_1)}{d_1} \frac{(c_2,d_2)}{d_2}N$ here. So the net bound on $S$ is

$|S| \lessapprox N^{1/2} x^{\delta/6} (d_1 d_2)^{1/6} + \frac{(c_1,d_1)}{d_1} \frac{(c_2,d_2)}{d_2}N.$

Using this bound, we can improve the RHS in Lemma 10 of this post to

$N^{1/2} x^{\delta/6} (Q^3 R)^{1/6}+ (hq'_2-h'q_2,r) R^{-1} N$ .

(one can get further improvements to the second term in the RHS by also studying the other components of $(c_1,d_1)$ and $(c_2,d_2)$ , but I don’t think we need these improvements yet.) The non-diagonal contribution to (50) is then

$\lessapprox H^2 Q^2 ( N^{1/2} x^{\delta/6} (Q^3 R)^{1/6}+ R^{-1} N)$

which needs to be $\lessapprox x^{-\varepsilon} Q^2 N$

leading to the conditions

$H^2 (Q^3 R)^{1/6} \lessapprox x^{-\delta/6 - \varepsilon} N^{1/2}$

and

$H^2 R^{-1} \lessapprox x^{-\varepsilon}$ .

As $H = x^\varepsilon Q^2 R / M$ and $NM \sim x$ , this becomes

$(QR)^{9/2} \lessapprox x^{2-\delta/6 - 3\varepsilon} (R/N)^{7/3} N^{5/6}$

$(QR)^4 \lessapprox x^{2-3\varepsilon} (R/N)^3 N$

which since $QR \lessapprox x^{1/2+2\varpi}$ , $N \gtrapprox x^{1/2-\sigma}$ , and $x^{-\delta-\mu} N \lessapprox R \lessapprox x^{-\mu} N$ for an infinitesimal $\mu$ , leads to the constraints

$\frac{9}{2} (\frac{1}{2} + 2 \varpi) < 2 - \frac{5}{2} \delta + \frac{5}{6} (\frac{1}{2} - \sigma)$

and

$4 (\frac{1}{2} + 2 \varpi) < 2 - 3 \delta + \frac{1}{2} - \sigma$

which may be rearranged as

$54 \varpi + 15 \delta + 5 \sigma < 1$

and

$8 \varpi + 3 \delta + \sigma < \frac{1}{2}$ .

The second constraint is clearly dominated by the first and so may be dropped. We conclude the “Level 3” bound that the Type I estimates hold for $54 \varpi + 15 \delta +5 \sigma < 1$ . Combining the Level 3 Type I estimates with the current best Type II estimate (which I’ve called Level 1a on the wiki) and the best Type III estimate (Level 3), Maple gives the slightly messy constraint

$788 \varpi + 195 \delta < 7$

for $1/140 < \varpi < 7/788$

which is a little bit better than the previous bound of $118 \varpi + 25.5 \delta < 1$ .

with(SolveTools[Inequality]); base := [ sigma > 1/10, sigma < 1/2, varpi > 0, varpi < 1/4, delta > 0, delta < 1/4+varpi ]; typeI_1 := [ 11 * varpi + 3 * delta + 2 * sigma < 1/4 ]; typeI_2 := [ 17 * varpi + 4 * delta + sigma < 1/4, 20 * varpi + 6 * delta + 3 * sigma < 1/2, 32 * varpi + 9 * delta + sigma < 1/2 ]; typeI_3 := [ 54 * varpi + 15 * delta + 5 * sigma < 1 ]; typeII_1 := [ 58 * varpi + 10 * delta < 1/2 ]; typeII_1a := [48 * varpi + 7 * delta < 1/2 ]; typeIII_1 := [ (13/2) * (1/2 + sigma) > 8 * (1/2 + 2*varpi) + delta ]; typeIII_2 := [ 1 + 5 * (1/2 + sigma) > 8 * (1/2 + 2*varpi) + delta ]; typeIII_3 := [ 3/2 * (1/2 + sigma) > (7/4) * (1/2 + 2*varpi) + (3/8) * delta ]; constraints := [ op(base), op(typeI_3), op(typeII_1a), op(typeIII_3) ]; LinearMultivariateSystem(constraints, [varpi,delta,sigma]);

26 June, 2013 at 6:48 pm

Hannes

I think $k_0 = 962, A = 388, \delta' = 0.0069, \varpi = 7/788 - 0.5932/10^5$ works.

26 June, 2013 at 7:04 pm

Terence Tao

Maple confirms, as usual… it gives H = 7470. Thanks!

k0 := 962; varpi := 7/788 - 0.5932/10^5; delta := (7 - 788*varpi) / 195; deltap := 0.0069; A := 388; theta := deltap / (1/4 + varpi); thetat := ((deltap - delta)/2 + varpi) / (1/4 + varpi); deltat := delta / (1/4 + varpi); j := BesselJZeros(k0-2,1); eps := 1 - j^2 / (k0 * (k0-1) * (1+4*varpi)); kappa1 := int( (1-t)^((k0-1)/2)/t, t = theta..1, numeric); kappa2 := (k0-1) * int( (1-t)^(k0-1)/t, t=theta..1, numeric); alpha := j^2 / (4 * (k0-1)); e := exp( A + (k0-1) * int( exp(-(A+2*alpha)*t)/t, t=deltat..theta, numeric ) ); gd := (j^2/2) * BesselJ(k0-3,j)^2; tn := sqrt(thetat)*j; gn := (tn^2/2) * (BesselJ(k0-2,tn)^2 - BesselJ(k0-3,tn)*BesselJ(k0-1,tn)); kappa3 := (gn/gd) * e; eps2 := 2*(kappa1+kappa2+kappa3); # we win if eps2 < eps

27 June, 2013 at 9:48 am

Anonymous

There is a typo in the last line of the code, it should be constraints.

[Corrected, thanks – T.]

26 June, 2013 at 9:53 pm

Terence Tao

I’ve been looking at the Type II estimates. My plan was to mimic the “Level 2” and “Level 3” improvements for the Type I estimates to obtain analogous gains in Type II, but I found an interesting phenomenon, in that the critical numerology for the Type II estimates actually fall outside of the range in which the van der Corput type lemmas gain over the completion of sums bound, so the Level 2 and Level 3 estimates are actually worse than the Level 1 estimates. However, I was able to extract a different gain by observing that the parameter R, which currently in the Type II case is constrained to the interval

$[x^{-2\varpi-\delta-\varepsilon} N, x^{-2\varpi-\varepsilon} N]$

could instead be constrained to

$[x^{1/2-2\varpi-\delta-\varepsilon}, x^{1/2-2\varpi-\varepsilon}]$

(which, in retrospect, is closer to what Zhang did originally, though he used $-3\varpi$ instead of $-2\varpi-\varepsilon$ ) and this gives slightly better numerology, improving the old constraint of $48\varpi + 7 \delta < 1/2$ to $38 \varpi + 7 \delta < 1/2$ . In a bit more detail, the two constraints coming out of the Type II analysis are

$(QR)^6 \lessapprox x^{2-4\varepsilon} N^{-1} R^{7/2}$

and

$(QR)^4 \lessapprox x^{2-4\varepsilon} N^{-2} R^{3}$

and if one inserts the bounds $QR \lessapprox x^{1/2+2\varpi}$ , $N \lessapprox x^{1/2}$ , and $R \gtrapprox x^{1/2-2\varpi-\delta-\varepsilon}$ one obtains the constraints

$19 \varpi + \frac{7}{2} \delta < \frac{1}{4}$

and

$14 \varpi + 3 \delta < \frac{1}{2}$

which lead to the stated constraint $38 \varpi + 7 \delta < \frac{1}{2}$ .

Setting $\delta=0$ , the critical numerology for Type 2 is then $\varpi = 1/76$ , $N=M=x^{1/2}$ , $R = x^{1/2-2\varpi}$ , $Q = x^{2\varpi}$ , $H = x^{6\varpi}$ . In Lemma 11, the modulus $d := r[q_1,q'_1,q_2,q'_2]$ should be of size $Q^4 R \approx x^{1/2+14\varpi}$ , while $N$ is of size $x^{1/2}$ , so $N \sim d^{19/26} \approx d^{0.731}$ , which is too large for a single van der Corput estimate to be useful (but potentially a combination of the A and B process might barely squeeze a slight gain in this regime).

27 June, 2013 at 4:45 am

Eytan Paldi

Perhaps the parameters ( $(1/2, -2, -1) and (1/2, -2, 0)$ ) defining the range of $R$ are still not the optimal ones? (if so, they may be optimized.)

27 June, 2013 at 8:59 am

Terence Tao

A good question!

The constraints on R arise in the following ways. Generally, one would like R to be as large as possible, as most of the bounds we need are of the form $X \lessapprox Y R^\alpha$ for various positive exponents $\alpha$ , and various quantities $X,Y$ that do not depend on R. (Ultimately, this is because R represents the portion of the modulus that we do not perform Cauchy-Schwarz on (when moving from (35) to (36) in the main post.) On the other hand, due to the $x^\delta$ -densely divisible hypothesis, we can only localise R to an interval of the form $[x^{-\delta} R_0, R_0]$ , where we are free to choose $R_0$ . So we would generally like $R_0$ to be large as possible as well.

However, there is a “diagonal” contribution coming from the case when $q_1,q_2$ have a common factor which needs to also be addressed; this is only briefly mentioned in this post (near (38)), but is done in more detail in the treatment of (32) in https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/ . The treatment of this case is complicated, but produces three upper bounds required on R, namely

$R \lessapprox x^{-c} N$

$R \lessapprox x^{-c} M$

$QR \times R \lessapprox x^{-c} NM$ (*)

Note that these quantities also necessarily obey the conditions $NM \sim x$ and $QR \lessapprox x^{1/2+2\varpi}$ .

In the Type I case (when $N \lessapprox x^{1/2-2\varpi}$ ) it is the first constraint that dominates, so that one sets $R_0 := x^{-c} N$ for some small c. But in the Type II case (when $x^{1/2-2\varpi} \lessapprox N \lessapprox x^{1/2}$ ) it is the last case that dominates, so the largest $R_0$ can be here is $x^{1/2-2\varpi-c}$ .

However, it is possible that one could treat (32) a bit more efficiently. It seems unlikely that R could usefully ever be larger than N (otherwise it becomes pointless to try to Cauchy-Schwarz on the residue class $n \hbox{ mod } r$ ) but I don’t immediately have a good explanation as to why the condition (*) is so necessary. One might indeed be able to save a few more factors of $\varpi$ this way.

27 June, 2013 at 9:40 am

Terence Tao

Actually, now that I look at it I think that (*) can indeed be removed, although it requires some technical modifications to the argument. Specifically, the controlled multiplicity hypothesis

$\sum_{C^{-1} x \leq n \leq Cx: n = a\ (r)} \tau_{{\mathcal C}}(n)^2 \ll \frac{n}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{O(1)}$

(which should have been stated in this post, but was omitted accidentally) needs to be strengthened slightly to

$\sum_{C^{-1} x \leq n \leq Cx: n = a\ (r)} \tau_{{\mathcal C}}(n)^2 \tau(n)^C \ll \frac{n}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{O(1)}$ (**)

but in the applications we need, this strengthening is available.

Henceforth all equation references are referring to https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/ .

We redo the estimation of the non-coprime contribution (32). Repeating the arguments in the previous post, we arrive at the task of bounding

$\sum_{q_0>1: (q_0,r)=1} \sum_m \psi_M(m) \sum_{n_1,n_2: n_1 = n_2\ (r); b'_{q_0} n_1 = b_{q_0} n_2\ (q_0); mn_1 = a_r\ (r); mn_1 = b_{q_0}\ (q_0)}$

$|\beta(n_1)| |\beta(n_2)| \tau_b(mn_1)^2$

by $\ll N^2 M R^{-2} \log^{-A} x$ (plus a symmetric term that is treated similarly). As before, we crucially have that $q_0$ has no prime factors smaller than $D_0$ .

We now deviate from the previous post (which performed the m summation at this point) by introducing the new variable $s := mn_1$ , which is comparable to x, and rearranging the above expression as

$\sum_{q_0>1: (q_0,r)=1} \sum_{s \sim x: s = a_r\ (r); s = b_{q_0}\ (r)} \tau_b(s)^2$

$\sum_{s = m n_1} \psi_M(m) |\beta(n_1)| \sum_{n_2: n_2=n_1\ (r); b_{q_0} n_2 = b'_{q_0} n_2\ (q_0)} |\beta(n_2)|$ .

The $n_2$ sum is $\ll \frac{N}{q_0 R} \tau(rq_0)^{O(1)} \log^{O(1)} x + x^{o(1)}$ by crude estimates. By the divisor bound, the $\sum_{s=mn_1}$ sum is then $\ll \frac{N}{q_0 R} \tau(s)^{O(1)} \tau(rq_0)^{O(1)} \log^{O(1)} x + x^{o(1)}$ by crude bounds. By using the improved controlled multiplicity hypothesis (**), the $x$ sum is then

$\ll \frac{x}{q_0R} \frac{N}{q_0 R} \tau(rq_0)^{O(1)} \log^{O(1)} x + \frac{x}{q_0 R} x^{o(1)}.$

(noting that $q_0 R \leq QR \ll x^{1/2+2\varpi} \ll x$ ), and then finally the $q_0$ sum is

$D_0^{-1} \frac{xN}{R^2} \tau(r)^{O(1)} \log^{O(1)} x + \frac{x^{1+o(1)}}{R}$

and this is acceptable given the single condition

$R \lessapprox x^{-\varepsilon} N$

for some fixed $\varepsilon > 0$ . So we can set $R_0 := x^{-\varepsilon} N$ in both the Type I and Type II cases. Returning to the Type II analysis from my comment above, the constraints

$(QR)^6 \lessapprox x^{2-4\varepsilon} N^{-1} R^{7/2}$

and

$(QR)^4 \lessapprox x^{2-4\varepsilon} N^{-2} R^{3}$

should now be rearranged as

$(QR)^6 \lessapprox x^{2-4\varepsilon} (R/N)^{7/2} N^{5/2}$

and

$(QR)^4 \lessapprox x^{2-4\varepsilon} (R/N)^3 N$

and using the bounds $R/N \gg x^{-\delta} R_0/N \gg x^{-\delta-\varepsilon}$ , $QR \ll x^{1/2+2\varpi}$ and $N \gg x^{1/2-2\varpi-c}$ , we are left with the constraints

$6(\frac{1}{2} + 2 \varpi) < 2 - \frac{7}{2} \delta + \frac{5}{2} (\frac{1}{2} - 2\varpi)$

and

$4(\frac{1}{2} + 2 \varpi) < 2 - 3 \delta + (\frac{1}{2} - 2\varpi)$

which rearrange to

$34 \varpi + 7 \delta < \frac{1}{2}$

and

$10 \varpi + 3 \delta < \frac{1}{2}$ .

The second condition is redundant, leaving us with a "Level 1c" Type II constraint of $34 \varpi + 7 \delta < \frac{1}{2}$ , improving upon the previous constraint $38 \varpi + 7 \delta < \frac{1}{2}$ . Since even the most optimistic projections we have so far do not foresee $\varpi$ going below 1/74, it now looks like the Type II estimates are good enough for the near-term that they will not cause any further difficulty.

Thanks for raising the question!

27 June, 2013 at 10:04 am

Eytan Paldi

I’m glad to see such fast improvement! (my last suggestion to optimize the parameters at the end of the project was sent before I read your response!)
Anyway, perhaps at the end of the project, it may be possible to optimize similar parameters when all the necessary limitations on them will become clear from the detailed proof.

27 June, 2013 at 9:45 am

Eytan Paldi

Perhaps such optimization (if possible) should be tried at the end of the project (when all the needed restrictions on the parameters will be known from the detailed proof.)

27 June, 2013 at 10:25 am

Pace Nielsen

I’ve been trying to figure out how the combinatorial lemma has influenced the creation of types 0,I,II,III; and conversely, how some natural cut-offs in estimating certain sums has influenced the creation of the combinatorial lemma. Further, I wanted to know if there was some sort of combinatorial improvement that could be made. In that spirit, let me describe how I now view things. This likely won’t be earthshattering for the experts, but may be helpful to those “occasional number-theorists” like myself.

For record keeping, let $\varphi_1,\ldots,\varphi_m$ be coefficient sequences at scales $M_1,\ldots, M_m$ , and let $\psi_1,\ldots,\psi_n$ be smooth coefficient sequences at scales $N_1, \ldots, N_n$ . We take positive real numbers $s_1,\ldots, s_m, t_1,\ldots, t_n$ such that $x^{s_i} \ll M_i \ll x^{s_i}$ and $x^{t_j} \ll N_j \ll x^{t_j}$ . We also assume $x \ll M_1 \cdots M_m N_1 \cdots N_n \ll x$ , and so $\sum_{i}s_i+\sum_{j}t_j=1$ . (Note: These real numbers are not fixed, but can change with $x$ . However, I’m postulating (from the answer to Avi Levy’s recent question), we can assume some sort of law of excluded middle, which I will use implicitly throughout this comment.) For simplicity, we assume $s_1\geq \ldots \geq s_m$ and $t_1\geq \ldots \geq t_n$ . Furthermore, we may assume $t_n\geq s_1$ from how the coefficient sequences are created; the non-smooth sequences are (basically) convolutions of even smaller smooth sequences. (This assumption isn’t essential, but often helps simplify things.)

We want to estimate quantities (with possible future modifications to “doubly dense divisibility”) of the form

$\sum_{q\in \mathcal{S}_I \cap \mathcal{D}_{x^{\delta}}:q<x^{1/2+2\varpi}}|\Delta(\varphi_1\ast\cdots \ast \varphi_m\ast \psi_1\ast\cdots\ast \psi_n;a_q)|$ .

Intuitively speaking, we want more $\psi$ 's than $\varphi$ 's, since smoothness helps us. It is also my impression that we don't want too many terms in the Dirichlet convolution, or the sums is difficult to bound well. (But this is not always the case. For instance, the case $m=1,n=0$ is not always better than the Type I/II case where $m=2,n=0$ .) We often will combine some of the convolutions into a single term, but at the cost of sometimes losing smoothness. We say that the sum above is of signature $(m;n)$ .

Now come the combinatorics. I want to address two specific cases. First consider when $\sigma=1/4$ . This is on the cups of what is not allowed using (the current) Type I-4 bounds. I believe that this will turn out to be a natural barrier, otherwise (as we'll see shortly) one could reprove Zhang's result without any Type III analysis.

Consider what happens when $t_1$ is large. Indeed, if $t_1 \geq 1/2+2\varpi +\epsilon$ then we are in the Type 0 case. What happens if $t_1$ is not quite so large? In the range $1/2-2\varpi -\epsilon \leq t_1 \leq 1/2+2\varpi+\epsilon$ we can reduce to the Type II regime, by combining all coefficient sequences except $\psi_1$ into a single term. Note that we have an added bonus; one of the two convolved functions is smooth! In the range $1/2-\sigma \leq t_1 \leq 1/2-2\varpi-\epsilon$ we can similarly reduce to Type I, again with the bonus that the smaller of the two coefficient sequences is smooth.

Now, let's consider the other end of the spectrum, where $t_1$ is small. If $t_1 < 1/4$ then $s_i,t_j<1/4$ for all $i,j$ . Thus, recombining the sequences we can reduce to signature $(2;0)$ where $1/4 < s_1,s_2< 3/4$ . This is again Type I/II (but without the added bonus of at least one sequence being smooth). Further, when $\sigma=1/4$ , this covers all possible cases.

Finally, we will look at the case when $\sigma=1/12$ , which is outside the current combinatorial bounds. The cases when $t_1$ is large are dealt with in exactly the same way as above. Similarly, if $t_1 < 2\sigma=1/6$ , we can reduce to the Type I/II analysis as above. So, we reduce to the case when $1/6\leq t_1 \leq 5/12$ .

Zhang's combinatorial method here seems to consist of counting how many other $t$ 's can possibly belong to this same interval, while (without loss of generality) restricting $s_i<1/6$ , and further thinking of any $t<1/6$ as an $s$ (i.e. forgetting about the smoothness of such sequences).

(A) Suppose $t_1$ is the only $t$ in the given interval. Then $\sum_i s_i\geq 7/12$ , and taking just enough of the $\varphi$ 's and attaching them to $\psi$ , we reduce to Type I/II.

(B) Suppose $t_1, t_2$ are the only $t$ 's in the given interval. Attaching all of the $\varphi$ 's to $\psi_2$ would give a sequence of size $1-t_1\geq 7/12$ , and so there is some subcollection of the $\varphi$ 's which when attached to $\psi_2$ given a sequence of size between $5/12,7/12$ . Attaching the remainder of the $\varphi$ 's to $\psi_1$ reduces to Type I/II.

(C) If there are more than six $t$ 's in the interval, then we reach a contradiction since in that case $\sum_{j}t_j \geq 7(1/6)$ .

(D) If there are exactly six $t$ 's in the interval, then we have $t_1=t_2=\cdots=t_6=1/6$ . We reduce to type II by combining $\psi_1,\psi_2,\psi_3$ , and then combining the remaining sequences.

(E) If there are exactly five $t$ 's in the interval, then we have a new situation that wasn't covered by the combinatorial lemma. (This is one of the reasons for the cutoff at $\sigma=1/10$ .) This can happen, for instance if $t_1=t_2=\cdots=t_5=1/5$ . There are a few ways to deal with this new situation; depending on which of the signatures $(1,5),(1,4),(2,4),(1,3),\ldots$ is most manageable.

(F) Suppose $t_1,t_2,t_3,t_4$ are the only $t$ 's in the interval (and so $n=4$ ). If $5/12\leq t_i+t_j\leq 7/12$ for some pair $i\neq j$ , then we reduce to Type I/II. If $t_i+t_j<5/12$ for every distinct pair, then $\sum_i s_i=1-\sum_j t_j \geq 1-5/12-5/12=1/6$ . Thus, combining/convolving the sequences $\psi_1,\psi_2$ and all $\varphi$ 's, we have size $\geq 1/6+1/6+1/6=1/2$ . As in case (B), we reduce to Type I/II.

Thus, we reduce to when $7/12 < t_1+t_2$ . If $7/12 <t_2+t_3$ then we are in Type III (combining $\psi_4$ with all the $\varphi$ 's). So, we may also assume $t_2+t_3< 5/12$ . Thus, we have

$7/24 < t_1 < 10/24, 4/24< t_3,t_4<5/24$

But $5/12<7/24+4/24=11/24$ and so $7/12<t_1+t_4$ . Thus $9/24= 7/12-5/24<7/12-t_4<t_1$ . This situation is possible, for example when we have (approximately)

$t_1, t_2,t_3=5/24,\ t_4=9/24$ .

(G) Finally, consider the case when $n=3$ . As before, we may assume we *cannot* recombine and reduce to types I/II/III. If $t_1+t_2<5/12$ then we easily obtain $t_3\leq t_2< 5/24$ and so $\sum_i s_i \geq 9/24$ . This easily reduces to Type I/II. So $7/12<t_1+t_2$ , and as we are not in Type III we have $t_2+t_3 < 5/12$ . As in (F), we can reduce to the case where

$9/24 < t_1 < 10/24, 4/24 < t_3 < 5/24$

and so we also obtain, $t_2< 6/24$ . This leaves $\sum_i s_i \geq 1/6$ . Thus, we can combine some of the $\varphi$ 's with $\psi_1$ , and reduce to Type I/II again. So there are no extra cases here.

Observations:———-

Can we improve on this? There are at least two ways to proceed; whether they improve things remains to be seen. Instead of counting the number of indices in the interval $2\sigma\leq t_i\leq 1/2-\sigma$ , we could continue with the (possibly more natural) process of considering signatures in order. So, for example, we might consider what happens for the signature $(1,2)$ (with the two smooth sequences having fairly "large" scales), and ply this against the Type III analysis. Indeed, this is somewhat suggested by the current form that the Type III computations take. Those estimate gives $3t_1 + 3t_2 + 4t_3\approx 3+12\varpi +\delta+\epsilon$ (where here we can take $t_2<t_3$ if we like, which we do). So, we want $t_3$ as large as possible (and hence we want $t_3=t_1$ ). Thus, we are naturally led to consider the case when there are two, nearly equal, large scales.

Another (possibly less helpful) option would be to consider signatures of the form $(3,0)$ . If we could do a Type III analysis without the smoothness hypothesis, this would remove the combinatorial constraint $1/10<\sigma$ .

27 June, 2013 at 11:00 am

Terence Tao

Thanks for this analysis!

It’s a nice observation that the Type I/II case could stretch to cover all cases if $\sigma$ could be raised to 1/4. This might lead to a simpler proof of Zhang’s theorem (in particular, not relying on Deligne’s version of the Weil conjectures, only Weil’s original results which nowadays can also be proven by elementary means) for sufficiently small $\varpi$ by eliminating the Type III analysis. But for the task of getting $\varpi$ as big as possible we presumably need an “all hands on deck” approach in which we throw all the estimates we have at the problem.

Actually, now that I think about it, $\sigma=1/6$ might already be big enough for this purpose, as this is the meeting point between $2\sigma$ and $1/2-\sigma$ . So the Level 3 or Level 4 Type I estimates (combined with Type II) might already give a proof of Zhang’s theorem!

In the other direction, with regards to trying to push $\sigma$ below 1/10, I think the two new critical cases to consider will be a “Type IV” sum in which n=4 and $(t_1,t_2,t_3,t_4)$ is close to $(1/5,1/5,1/5,2/5)$ and a “Type V” sum in which n=5 and $(t_1,t_2,t_3,t_4,t_5)$ is close to $(1/5,1/5,1/5,1/5,1/5)$ (I have not figured out exactly what “close to” means though). This basically corresponds to distribution results (for smooth or densely divisible moduli) for the higher order divisor functions $d_4$ and $d_5$ . I am unsure if there are any fancy arguments in the literature (beyond the Zhang-based ones) that beat Bombieri-Vinogradov in this context; it seems that $d_3$ is pretty much state of the art. But this is certainly a good direction to focus attention on, though perhaps not by Polymath8; new ways to control $d_4$ and $d_5$ would be very interesting beyond just the ability to squeeze a few more improvements to $\varpi$ , $k_0$ , and $H$ . (I could imagine that Polymath8 eventually gets to the point where the $\sigma > 1/10$ constraint is the dominant obstruction, and then calls it a day, leaving it to others in the field to start attacking $d_4$ and $d_5$ and get some improvements to $\varpi$ etc. as a bonus.)

27 June, 2013 at 2:08 pm

Pace Nielsen

Yes, I believe that you are right that $\sigma=1/6$ is already good enough (if you can deal with the “endpoint” case of $t_1=t_2=t_3=1/3$ ). It would be neat to see that lead to a simpler proof of Zhang’s theorem.

27 June, 2013 at 2:16 pm

Pace Nielsen

I see from your new Level 4 Type III analysis, that some of my observations may have been unwarranted. However, it still may be the case that those sums of signature $(1;2)$ naturally fit “inbetween” the Type I/II sums (whose signature is $(2;0)$ ) and the Type III sums (whose signature is $(1;3)$ ).

27 June, 2013 at 5:35 pm

David Roberts

If we can get to the point where $\sigma > 1/10$ is the main obstruction, where does that leave us with $\varpi$ , taking all optimistic projections into account? And what about $k_0$ ?

27 June, 2013 at 7:20 pm

Terence Tao

Actually, with the Level 4 Type III estimates, we’ve just reached this point – so $\varpi$ is basically stuck at 1/108 right now until we improve the Type I estimates again beyond Level 3. We do have an in principle improvement here (“Level 4”) by using an iterated van der Corput, but it is not yet implemented. In principle, this estimate give something like $40\varpi + 4 \sigma < 1$ (ignoring deltas), so if we play that against $\sigma > 1/10$ that should give $\varpi < 3/200$ , though 3/200 ~ 1/67 is large enough that the Type II and Type III estimates will have to be improved again before we can actually reach this point.

28 June, 2013 at 5:40 am

xfxie

If $40\varpi + 4 \delta < 1$ , it is easily to obtain $k_0 = 300$ (e.g., for $\varpi=1/40-1.9582/10^5, \delta'=0.0079, A=86$ , based on a rough search using a simple nonlinear optimizer calling with the maple script), if the calculation is correct. This will totally fall into the region of Engelsma's exact bounds.

28 June, 2013 at 7:16 am

Anonymous

Unfortunately Xfxie the inequality in Tao’s comment is in “sigma” not “delta” the inequality above comes from the type 1 inequality and still needs to be confronted with type 3’s to eliminate sigma and get the final inequality. There is no delta in the inequality because he just wants a rough idea of the result (and because that factor wasn’t calculated yet).
Can you share the optimizer you are using I guess it could save some time here.

28 June, 2013 at 7:30 am

xfxie

@Anonymous: I have to reply here because cannot find the reply button under your thread.

The optimizer code is currently located on my home machine. I will try to post the code tonight or soon.

27 June, 2013 at 11:59 am

Terence Tao

In this comment I will upgrade another estimate, specifically to upgrade the “Level 3” Type III estimate of Fouvry, Kowalski, Michel, and Nelson to a “Level 4” estimate that exploits averaging in the alpha parameter to reduce the contribution of the diagonal terms (this idea was used in the “Level 2” estimates and was also suggested by FKMN). We will be largely repeating the arguments from the previous comment https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236237 .

As in that comment, the objective is to show that

$\sum_{r \sim R} \sum_{s \sim S: (r,s)=1} |\Delta(\alpha * \psi_1 * \psi_2 * \psi_3; a_{rs}\ (rs))| \lessapprox x^{-\varepsilon} M N$

for $RS=Q$ that we can specify to accuracy $x^\delta$ , thus we may place $R$ in $[x^{-\delta} R_0, R_0]$ for some $R_0$ to be chosen later, and $N = N_1 N_2 N_3$ .

FKMN discard the averaging in $\alpha$ or $s$ . For Level 4 estimates, we still discard the s averaging (there isn’t really any plausible way we know of to exploit it thus far) but keep the alpha average. We are now looking at

$\sum_{r \sim R: (r,s)=1} |\Delta(\alpha * \psi_1 * \psi_2 * \psi_3; a_{rs}\ (rs))| \lessapprox x^{-\varepsilon} M N / S.$

This may be rewritten as

$\sum_r c_r \sum_m \alpha(m) \sum_{n_1,n_2,n_3} \psi_1(n_1) \psi_2(n_2) \psi_3(n_3) 1_{m n_1n_2n_3 = a_{rs}\ (rs)}$

$= X + O( x^{o(1)} M N / S )$

where $X$ does not depend on the residues $a_{rs}$ , and the $c_r$ are bounded and only supported on those $r \sim R$ coprime to $s$ . We can similarly restrict $\alpha$ to those $m$ that are coprime to $s$ .
Performing completion of sums in the $n_1,n_2,n_3$ variables, the left-hand side can be expressed as

$\frac{1}{H} \sum_{h_1=O(H_1), h_2 = O(H_2), h_3 = O(H_3); h_1h_2h_3 \neq 0} | \sum_r c_r \sum_{m: (m,r)=1} \alpha(m)$

$\sum_{x,y,z \in {\bf Z}/rs{\bf Z}: mxyz = a_{rs}\ (rs)} e_{rs}(h_1 x + h_2 y + h_3 z)|$ (*)

plus terms which do not depend on $a_{rs}$ (coming from the cases when at least one of the $h_i$ vanish), where $H_i = Q/N_i$ and $H = H_1 H_2 H_3 = Q^3/N$ . Ignoring for this discussion the coprimality problem mentioned in a previous comment, the inner sum may be rescaled as

$rs K_3( a_{rs} h_1 h_2 h_3 / m; rs )$

as before, so we may gather terms and write the expression (*) as

$\frac{Q}{H} \sum_{h = O(H): h \neq 0} \tilde d_3(h) \sum_r c'_r \sum_{m: (m,r)=1} \alpha(m) K_3( a_{rs} h / m; rs )$

as before. The objective is now to show

$\sum_{h = O(H): h \neq 0} \tilde d_3(h) |\sum_r c'_r \sum_{m: (m,r)=1} \alpha(m) K_3( a_{rs} h / m; rs )| \lessapprox x^{-\varepsilon} QRM.$

By Cauchy-Schwarz as in the previous comment it suffices to show that

$\sum_{h = O(H)} |\sum_r c'_r \sum_{m: (m,r)=1} \alpha(m) K_3( a_{rs} h / m; rs )|^2 \lessapprox x^{-2\varepsilon} Q^2 R^2 / H.$ (**)

We can rearrange the LHS as

$\sum_{r_1, r_2} c'_{r_1} \overline{c'_{r_2}} \sum_{m_1,m_2: (m_1,r_1)=(m_2,r_2)=1} \alpha(m_1) \overline{\alpha(m_2)}$

$\sum_{h = O(H)} K_3(a_{r_1s} h / m_1; r_1s) \overline{K_3(a_{r_2s} h / m_2; r_2s)}$ .

$\lessapprox (\frac{H}{[r_1,r_2] s} + 1)$
$d (s/d)^{1/2} r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}$

where $r_0 := (r_1,r_2,m_2-m_1)$ and $d := (m_2r_1^3-m_1 r_2^3, s)$ ; the insertion of the m factors is the key new improvement here. So now one has to sum

$\sum_{r_1,r_2 \sim R: (r_1r_2, s) = 1} \sum_{m_1,m_2 \sim M: (m_1,r_1s)=(m_2,r_2s)=1}$
$(\frac{H r_0}{r_1 r_2 s} + 1) d (s/d)^{1/2} r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}.$

The diagonal case $m_1=m_2$ contributes a term of

$\lessapprox M( R^3 S^{1/2} + HR + R^2 S )$

by repeating the arguments from the previous comment. Now we turn to the off-diagonal contributions $m_1 \neq m_2$ . Among other things this forces $r_0$ to divide $m_1-m_2$ , which already gives a noticeable gain (and forces $r_0$ to be only as large as $O(M)$ ).

Fix $m_1,m_2$ . The same computation as the previous comment shows that for each choice of $r_0 | m_1-m_2$ and $d|s$ , the number of pairs $r_1,r_2$ with $r_0=(r_1,r_2,m_1-m_2)$ and $d = (m_2r_1^3-m_1r_2^3,s)$ is $\lessapprox \frac{R^2}{r_0^2 d} + \frac{R}{r_0}$ . (There are $O(R/r_0)$ choices for $r_1$ , and for fixed $r_1$ there are $O( R_0/r_0d + 1)$ choices for $r_2$ .)

So now one is summing

$\sum_{m_1 \neq m_2} \sum_{d|s} \sum_{r_0|m_1-m_2} (\frac{R^2}{r_0^2 d} + \frac{R}{r_0})$

$(\frac{H r_0}{r_1 r_2 s} + 1) d (s/d)^{1/2} r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}$ .

One can perform the $d$ summation without difficulty and end up with

$\lessapprox \sum_{m_1 \neq m_2} \sum_{r_0|m_1-m_2} (\frac{R^2 s^{1/2}}{r_0^2} + \frac{R s}{r_0})$

$(\frac{H r_0}{r_1 r_2 s} + 1) r_0 (r_1/r_0)^{1/2} (r_2/r_0)^{1/2}$ ,

and then performing the $r_0$ summation (which is now improved due to the constraint $r_0|m_1-m_2$ ) this becomes

$\lessapprox M^2( H R S^{-1/2} + R^3 S^{1/2} + H + S R^2 )$ .

Collecting terms, it is now

$M^2 ( H R S^{-1/2} + R^3 S^{1/2} + H + S R^2 ) + M HR$

that we wish to be $\lessapprox x^{-2\varepsilon} M^2 Q^2 R^2 / H$ .
Ignoring epsilons, this gives rise to upper and lower bounds on R:

$R \gtrapprox H^{4/3}/Q^{5/3}$

$R \lessapprox Q^3 / H^2$

$R \gtrapprox H/Q$

$R \gtrapprox H^2 / (Q^2 M)$ .

So we now have

$H^2/Q^2M, H/Q, H^{4/3}/Q^{5/3} \lessapprox R \lessapprox Q^3 / H^2$ .

Since $R$ has to be at least 1, we need $H \lessapprox Q^{3/2}$ , which also makes all the lower bounds on $R$ at most $Q$ . We then win if

$H^2/Q^2M, H/Q, H^{4/3}/Q^{5/3} \lessapprox x^{-\delta} Q^3 / H^2$

which rearranges to

$H \lessapprox x^{-\delta/4} Q^{5/4} M^{1/4}, x^{-\delta/3} Q^{4/3}, x^{-3\delta/10} Q^{7/5}$ .

These are stronger than the previous constraint $H \lessapprox Q^{3/2}$ which may now be discarded. Also the last constraint $H \lessapprox x^{-3\delta/10} Q^{7/5}$ is weaker than $H \lessapprox x^{-\delta/3} Q^{4/3}$ and may also be dropped. As $H = Q^3/N$ , the constraints may be rewritten as

$N \gtrapprox x^{\delta/4} Q^{7/4} M^{-1/4}, x^{\delta/3} Q^{5/3}$

thus

$N_1 N_2 N_3 \gtrapprox x^{\frac{7}{4}(\frac{1}{2}+2\varpi) + \frac{1}{4} \delta} M^{-1/4}$

and

$N_1 N_2 N_3 \gtrapprox x^{\frac{5}{3}(\frac{1}{2}+2\varpi) + \frac{1}{3} \delta}$

In terms of $\sigma$ , this gives a constraint

$\frac{1}{4} + \frac{3}{4} \frac{3}{2} (\frac{1}{2} + \sigma) > \frac{7}{4} (\frac{1}{2} + 2 \varpi) + \frac{1}{4} \delta$

$\frac{3}{2} (\frac{1}{2} + \sigma) > \frac{5}{3} (\frac{1}{2} + 2 \varpi) + \frac{1}{3} \delta$

which can be rearranged as

$\sigma > \frac{1}{18} + \frac{28}{9} \varpi + \frac{2}{9} \delta$

and

$\sigma > \frac{1}{18} + \frac{20}{9} \varpi + \frac{2}{9} \delta$ .

the first condition dominates, so it looks like the Level 4 Type III constraint is

$\sigma > \frac{1}{18} + \frac{28}{9} \varpi + \frac{2}{9} \delta$ .

which when combined with the latest Type I and Type II estimates (Level 3 and Level 1c respectively) seems to give the final constraint

$18 \varpi + 5 \delta < \frac{1}{6}$

which is basically formed by the collision of the $\sigma > 1/10$ constraint and the Level 3 Type I constraint of $54 \varpi + 15 \delta + 5\sigma < 1$ . Thus the Level 4 Type III estimates are so strong that they are no longer providing the dominant contribution, it is now the clash between Type I and the combinatorial constraint $\sigma > 1/10$ which is the bottleneck; Type III won’t become relevant again until $\varpi$ hits 1/70. (This also means that the above analysis will be fairly robust to numerical errors.)

with(SolveTools[Inequality]); base := [ sigma > 1/10, sigma 0, varpi 0, delta < 1/4+varpi ]; typeI_1 := [ 11 * varpi + 3 * delta + 2 * sigma < 1/4 ]; typeI_2 := [ 17 * varpi + 4 * delta + sigma < 1/4, 20 * varpi + 6 * delta + 3 * sigma < 1/2, 32 * varpi + 9 * delta + sigma < 1/2 ]; typeI_3 := [ 54 * varpi + 15 * delta + 5 * sigma < 1 ]; typeII_1 := [ 58 * varpi + 10 * delta < 1/2 ]; typeII_1a := [48 * varpi + 7 * delta < 1/2 ]; typeII_1b := [38 * varpi + 7 * delta < 1/2 ]; typeII_1c := [34 * varpi + 7 * delta 8 * (1/2 + 2*varpi) + delta ]; typeIII_2 := [ 1 + 5 * (1/2 + sigma) > 8 * (1/2 + 2*varpi) + delta ]; typeIII_3 := [ 3/2 * (1/2 + sigma) > (7/4) * (1/2 + 2*varpi) + (3/8) * delta ]; typeIII_4 := [ 3/2 * (1/2 + sigma) > (5/3) * (1/2 + 2*varpi) + (1/3) * delta ]; constraints := [ op(base), op(typeI_3), op(typeII_1c), op(typeIII_4) ]; LinearMultivariateSystem(constraints, [varpi,delta,sigma]);

27 June, 2013 at 12:45 pm

Hannes

Here I think one can choose $k_0 = 902, A = 360, \delta' = 0.0069, \varpi = 1/(6\cdot 18) - 0.735/10^5$ .

27 June, 2013 at 2:38 pm

Terence Tao

Maple okays it :) Thanks to the shiny new narrow admissible tuples page (now accepting submissions!), this gives H = 6,966. (Four orders of magnitude improvement!)

k0 := 902; varpi := 1/(6*18) - 0.735/10^5; delta := (1/6 - 18*varpi)/5; deltap := 0.0069; A := 360; theta := deltap / (1/4 + varpi); thetat := ((deltap - delta)/2 + varpi) / (1/4 + varpi); deltat := delta / (1/4 + varpi); j := BesselJZeros(k0-2,1); eps := 1 - j^2 / (k0 * (k0-1) * (1+4*varpi)); kappa1 := int( (1-t)^((k0-1)/2)/t, t = theta..1, numeric); kappa2 := (k0-1) * int( (1-t)^(k0-1)/t, t=theta..1, numeric); alpha := j^2 / (4 * (k0-1)); e := exp( A + (k0-1) * int( exp(-(A+2*alpha)*t)/t, t=deltat..theta, numeric ) ); gd := (j^2/2) * BesselJ(k0-3,j)^2; tn := sqrt(thetat)*j; gn := (tn^2/2) * (BesselJ(k0-2,tn)^2 - BesselJ(k0-3,tn)*BesselJ(k0-1,tn)); kappa3 := (gn/gd) * e; eps2 := 2*(kappa1+kappa2+kappa3); # we win if eps2 < eps

27 June, 2013 at 7:16 pm

Hannes

This script looks strange. Copy-error?

[Oops, the first three lines were missing; should be there now. -T.]

28 June, 2013 at 8:24 am

Pace Nielsen

Using this Level 4 Type III analysis, I have an idea [*very* sketchy at the moment] that has the potential to remove any reference to $\sigma$ (thus removing Type I computations), unify Type 0 and Type III into a single result, and trivialize Type II computations.

Let us begin as above, but with the new objective to obtain the bound

$\sum_{r\sim R}\sum_{s\in S:(r,s)=1}|\Delta(\alpha\ast \psi_1\ast\cdots\ast\psi_{n};a_{rs}\ (rs))|\lessapprox x^{-\epsilon}MN$

Proceeding as in the comment, the main term of interest in the LHS is

$\frac{1}{H}\sum_{h_1=O(H_1),\ldots, h_n=O(H_n); h_1\cdots h_n\neq 0}|\sum_r c_r\sum_{m:(m,r)=1}\alpha(m)$

$\sum_{x_1,\ldots, x_n\in {\bf Z}/rs{\bf Z}: mx_1\cdots x_n=a_{rs}\ (rs)} e_{rs}(h_1x_1+\cdots +h_n x_n)|$ (*)

Setting $h=h_1\cdots h_n$ , and proceeding as before, the changes are twofold. First, replace $\tilde d_3$ by $\tilde d_n$ . I believe that this causes no trouble, and can still be handled by the divisor bound. Second, we replace $K_3$ by $K_n$ . Here is where my idea becomes especially sketchy. We need to find a bound on

$\sum_{h=O(H)}K_n(a_{r_1s}h;r_1 s)\overline{K_n(a_{r_2 s}h;r_2 s)}$

of some manageable order. To continue, supposing we get something similar to

$(\frac{H}{[r_1,r_2]s}+1) d(s/d)^{1/2}r_0(r_1/r_0)^{1/2}(r_2/r_0)^{1/2}$

(which is what was obtained above in the $n=3$ case, possibly here with $d$ involving $n$ th powers), then the rest of the post seems to follow along similar lines. We still end with something *close* to the two conditions

$N \gtrapprox x^{\frac{7}{4}(\frac{1}{2}+2\varpi)+\frac{1}{4}\delta}M^{-1/4}$

and

$N \gtrapprox x^{\frac{5}{3}(\frac{1}{2}+2\varpi)+\frac{1}{3}\delta}$ .

These equations (when precisely stated) may now rely on $n$ , but for simplicity I’ll ignore that. Fix $\epsilon > 0$ and restrict to the case $M\lessapprox x^{\epsilon}$ . Considering all $n$ up to a large (but fixed) size, the only combinatorial case not covered is when all scales are smaller than $x^{\epsilon}$ . If $\epsilon$ is fine enough we can cover that final case with a Type II analysis (in a significantly shorter interval).

At any rate, it might be interesting to work out what happens when $n=4,5$ , as that will partially address the current $\sigma=1/10$ obstruction.

28 June, 2013 at 8:47 am

Ph.M

I don’t know for the validity of the argument yet, but the Deligne type estimates for the K_n sums and product thereof possibly with an extra additive character (because polya-vinogradov) are valid exactly as for n=3 and are consequences of http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.dmj/1077229697

28 June, 2013 at 8:51 am

Terence Tao

It is worth checking out the numerology for, say, n=4, $M = 1$ , $N_1=N_2=N_3=N_4 = x^{1/4}$ (even though this particular case can also be handled by Type II methods) and $RS = x^{1/2+\varepsilon}$ , $\varpi,\delta \approx 0$ to see if we can just beat Bombieri-Vinogradov for $d_4$ in the most favorable case by this method. I think the numerology may become a less favorable though (the normalisation of $K_4(a, q)$ for instance, should have a factor of $\frac{1}{q^{3/2}}$ in front rather than $\frac{1}{q}$ to reflect the expected square root cancellation). There is also the additional issue that a certain amount of algebraic geometry (ell-adic sheaf cohomology, this sort of thing) is needed to actually justify the expected square root cancellation for sums such as $\sum_h K_4(a_{r_1} h; rs) \overline{K_4(a_{r_2} h; rs)} e_{rs}(ch)$ but we can cross that bridge when we come to it.

28 June, 2013 at 9:10 am

Ph.M

As said above algebraic geometry is not at all a problem here; my greatest worry as you said is that $H=Q^n/N_1\cdots N_n$ will get huge if $n$ is large so that an important term in Polya-Vinogradov will be the zero frequency: for these one need a weight dropping phenomenon (more than square-root cancellation) for the complete sums, $n=4$ say,

$\displaystyle \sum_{h(p)}K_n(h;p)$

and

$\displaystyle \sum_{h(p), (h,p)=1}\overline{K_n(h;p)}K_n(ah;p)$

where $(a,p)=1$ : these sums can probably be evaluated in an elementary way and then their size may determine whether this has a chance for $n\geq 4$ .

28 June, 2013 at 12:23 pm

Pace Nielsen

Thanks for the pointers. It looks like this idea won’t work out, but it gives me good motivation to understand the arguments better.

If it does turn out that $n=4$ gives a natural barrier, there is yet another way to beat the combinatorial restriction. If we are not in type 0,I,II, then we can still reduce to the case where there exist at least three real numbers in the range $2\sigma \leq t_i\leq 1/2-\sigma$ . In general, we no longer have that $t_1+t_2+t_3 \geq \frac{3}{2}(\frac{1}{2}+\sigma)$ , but we can use the poorer lower bound $t_1+t_2+t_3\geq 6\sigma$ . Unfortunately, with the current Level 4 Type III bounds, this gives

$\sigma \geq \frac{5}{36} +\frac{7}{9}\varpi+ \frac{1}{18}\delta \geq 1/10$

so it doesn’t help us (yet).

28 June, 2013 at 2:55 pm

Terence Tao

After a nice discussion over lunch with Philippe Michel (who happens to be in LA currently), I now have a clearer idea of why the Type III argument of FKMN beats Bombieri-Vinogradov for n=3 but just barely fails to do so for n=4.

Let’s start with n=3, taking $N_1=N_2=N_3 = x^{1/3}$ and $Q = x^{1/2}$ for simplicity (so we are just at the border of Bombieri-Vinogradov. Philippe pointed out that it is convenient to write things in terms of powers of Q, thus $N_1,N_2,N_3 \sim Q^{2/3}$ here. We want to understand the expression

$\sum_{n_1,n_2,n_3 \sim Q^{2/3}: n_1 n_2 n_3 = a\ (q)} 1$

on the average for typical (smooth) $q \sim Q$ (I will suppress the dependence of $a$ on $q$ here for simplicity). The trivial bound here is $O( \frac{Q^{2/3} Q^{2/3} Q^{2/3}}{q} ) = O( Q )$ , so we want to control this sum with accuracy $o(Q)$ or better. Using completion of sums, we can rewrite the above expression (morally) as

$\frac{1}{(Q^{1/3})^3} \sum_{h_1,h_2,h_3 = O(Q^{1/3})} \sum_{n_1,n_2,n_3 \in {\bf Z}/q{\bf Z}: n_1n_2 n_3 = a\ (q)}$

$e_q( h_1 n_1 + h_2 n_2 + h_3 n_3 )$

which (if we discard the cases where $h_1h_2h_3$ vanishes or otherwise has a common factor with $q$ ) is basically

$\sum_{h_1,h_2,h_3 = O(Q^{1/3})} K_3( a h_1 h_2 h_3; q )$

(the $\frac{1}{(Q^{1/3})^3}$ out the front is absorbed into the normalisation of $K_3$ . Deligne (for the surface $\{xyz = a\}$ ) tells us that $|K_3(ah_1h_2h_3;q)| \lessapprox 1$ , giving us back $O(Q)$ . So a direct application of Deligne only recovers the trivial bound; but once we do even a little bit of Cauchy-Schwarz and take advantage of the averaging in q we can do better (again using Deligne, but now for a hyper-Kloosterman correlation rather than for a single hyper-Kloosterman sum). Eventually it turns out that we can get $N_1N_2N_3$ as low as $Q^{7/4}$ (down from the current level of $Q^2$ ), which corresponds to a 4/7 level of distribution.

Now we take n=4, in the model case when $Q = x^{1/2}$ and $N_1 =N_2 = N_3 =N_4 = x^{1/4} = Q^{1/2}$ . We are now staring at

$\sum_{n_1,n_2,n_3,n_4 \sim Q^{1/2}: n_1 n_2 n_3 n_4 = a\ (q)} 1$

(before averaging in q). The trivial bound is $O( \frac{(Q^{1/2})^4}{q} ) = O( Q )$ as before. After completion of sums we get

$\frac{1}{(Q^{1/2})^4} \sum_{h_1,h_2,h_3,h_4 = O(Q^{1/2})} \sum_{n_1,n_2,n_3,n_4 \in {\bf Z}/q{\bf Z}: n_1n_2 n_3 n_4 = a\ (q)}$

$e_q( h_1 n_1 + h_2 n_2 + h_3 n_3 + h_4 n_4)$

(note here that completion of sums did not shorten the length $O(Q^{1/2})$ of incomplete summation, in contrast to the n=3 case when it reduced a sum of length $O(Q^{2/3})$ to the dual length of $O( Q^{1/3})$ . With the normalisation of $K_4$ (which now has a $q^{-3/2}$ in front instead of $q^{-1}$ ), this morally becomes

$Q^{-1/2} \sum_{h_1,h_2,h_3,h_4 = O(Q^{1/2})} K_4( a h_1 h_2 h_3 h_4; q ).$

Deligne still tells us that $|K_4(a h_1 h_2 h_3 h_4; q)| \lessapprox 1$ , but this now gives a net bound of $O( Q^{3/2} )$ , so we fall short by $Q^{1/2}$ of even recovering Bombieri-Vinogradov here. We can _barely_ recover this by averaging in q as per FKMN. Namely, we are now trying to prove something like

$|\sum_{q \sim Q} c_q \sum_{h = O(Q^2)} \tilde \tau_4(h) K_4(ah; q)| \lessapprox Q^{5/2}$

for some bounded $c_q$ and some divisor-like function $\tilde \tau_4$ . Performing Cauchy-Schwarz in h, this becomes

$|\sum_{q,q' \sim Q} c_q \overline{c_{q'}} \sum_{h = O(Q^2)} K_4(ah;q) \overline{K_4(ah;q')}| \lessapprox Q^3$ .

The diagonal term $q=q'$ is barely acceptable, and the off-diagonal terms are also barely accceptable using hyper-Kloosterman correlation (if we replace $h=O(Q^2)$ with $h \in {\bf Z}/qq'{\bf Z}$ ). So we can barely recover Bombieri-Vinogradov with basically no room to maneuver. So it looks like we would have to come up with a new trick in order to use this sort of argument to get something non-trivial in the n=4 case.

28 June, 2013 at 4:38 pm

Gergely Harcos

Is it $e( h_1 n_1 + h_2 n_2 + h_3 n_3 )$ or $e_q( h_1 n_1 + h_2 n_2 + h_3 n_3 )$ in the completed sum?

[It’s $e_q$ ; I’ve corrected the text. -T]

28 June, 2013 at 4:54 pm

Ph.M

What about doing this analysis with Cauchy in (h,r) (instead of h alone) with q=rs with r very small but >1 and s close to Q ?

28 June, 2013 at 8:12 pm

Terence Tao

Dear Philippe,

If we try to Cauchy-Schwarz in more variables, the off-diagonal terms $s \neq s'$ become better, but the diagonal terms $s=s'$ become worse; since both the diagonal and off-diagonal terms barely make it to Bombieri-Vinogradov, I don’t see a way to rebalance the Cauchy-Schwarz to do better. A little more precisely, we now write the Bombieri-Vinogradov type estimate to be proven as

$|\sum_{h = O(Q^2)} \sum_{r \sim R} \sum_{s \sim S} c_{rs} \tilde \tau_4(h) K_4(ah;rs)| \lessapprox Q^{5/2}$

with $Q = RS$ . If we Cauchy-Schwarz in h,r as you suggest we end up with

$|\sum_{h = O(Q^2)} \sum_{r \sim R} \sum_{s,s' \sim S} c_{rs} \overline{c_{rs'}} K_4(ah;rs) \overline{K_4(ah,rs')} |$

$\lessapprox Q^3 / R$

The diagonal contribution $s=s'$ now has size $O( Q^2 R S ) = O(Q^3 )$ which is now a little bit too big to even get back Bombieri-Vinogradov.

Having said this, though, I think this rebalancing trick may work for the Type I and Type II sums to get a further gain from what we already have (or plan to have). In both the Type I and Type II sums, one is eventually looking at a sum of the form

$\sum_h \sum_{q_1,q_2 \sim Q} c_{h,q_1,q_2} \sum_n \beta(n) \beta(n+kr) \Phi( h, q_1, q_2; n )$

where $\Phi$ is a certain explicit phase and the coefficients $c_{h,q_1,q_2}, \beta$ are essentially bounded (and never mind what k and r are, it’s not important for this discussion); see equation (39) of https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/ . In the Type I sum, Zhang performs Cauchy-Schwarz in the $n,q_1$ variables and finds that the diagonal terms $h'q_2 = hq'_2$ are OK (as long as $M \gg x^{1/2+2\varpi+c}$ or equivalently $N \ll x^{1/2-2\varpi-c}$ for some small fixed $c>0$ ) and then works hard to control the off-diagonal terms $h'q_2 \neq hq'_2$ . In the Type II sum, the diagonal terms $h'q_2=hq'_2$ coming from Cauchy-Schwarz in $n,q_1$ are no longer OK and so Zhang uses Cauchy-Schwarz in just $h$ in order to make the diagonal terms $h'q_1q_2=hq'_1q'_2$ better, at the cost of making the off-diagonal terms $h'q_1q_2 \neq hq'_1q'_2$ worse (but because in Type II, $M$ and $N$ are much closer to $x^{1/2}$ than in Type I, one still can get reasonable estimates here.

But in light of your suggestion, I see that there are other Cauchy-Schwarz’s available: in particular,in Type I we can factor $q_2 = r_2 s_2$ and Cauchy-Schwarz in $n,q_1,r_2$ rather than just $n,q_1$ in order to make the diagonal terms do a bit more of the work and the off-diagonal terms do a bit less of the work. Similar optimisations are available in the Type II case (indeed one could imagine that one could now treat Type I and Type II in a unified fashion with a continuum of Cauchy-Schwarz options).

I’ll add this idea to the queue of possible Type I/Type II improvements (I’ll dub it “Level 6”). There are still two earlier potential Type I/Type II improvements (which I’ve called “Level 4” and “Level 5”) that should be worked out too; I think I can get a preliminary version of Level 4 worked out soon and will post it here. (It’s sort of a strange situation to have more ideas for progress than time available to work the ideas out properly; it’s almost always the other way around :-).)

27 June, 2013 at 6:18 pm

Mark Bennet

As someone who is following the discussion here with some interest, can I suggest that the constraints in current form would be easier to follow and compare when reading posts and tables (eg on the wiki page) if they were normalised to $a\varpi + b\delta < 1$ (ie clear fractions)

[Fair enough – I’ve edited the wiki accordingly. -T]

28 June, 2013 at 9:24 pm

Terence Tao

In this comment I am recording a preliminary “Level 4” estimate for Type I. However I am punting on the issue of exactly how to define “double dense divisibility” (which should roughly capture the notion that a modulus $q$ can be factored as $q = d_1 d_2 d_3$ with $d_1,d_2,d_3$ placed more or less wherever one wants) and revert to the older notion of $x^\delta$ -smoothness. This will worsen the numerology when converting from $\varpi,\delta$ to $k_0$ (basically, this forces one to take $\tilde \delta = \delta$ , so that $\kappa_3$ vanishes and $A$ is irrelevant) but I think the gain from improving $\varpi,\delta$ will still be greater than the loss from having to revert to a more primitive sieve. (This is presumably a temporary issue, that can be resolved once we work out what double dense divisibility should be.) Unfortunately I have bad news – due to arithmetic errors in my previous projection at https://terrytao.wordpress.com/2013/06/22/bounding-short-exponential-sums-on-smooth-moduli-via-weyl-differencing/#comment-236039 , this argument ends up being a lot worse than anticipated, and in fact is inferior to the Level 3 estimate.

Anyway, to the details. As with this previous comment https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236387 , the starting point is a bound for the incomplete Kloosterman sum

$S := \sum_n \psi_N(n) e_{d_1}(\frac{c_1}{n}) e_{d_2}(\frac{c_2}{n+l})$

with $d_1,d_2$ squarefree and coprime with $d_1 d_2$ $x^\delta$ -smoooth, then for any other factorisation $d = s_1 s_2 s_3$ of $d$ , we may use the k=2 van der Corput bound from this comment and bound

$|S| \lessapprox N^{1/2} (s'_1)^{1/2} + N^{3/4} (s'_2)^{1/4} + N^{3/4} (s'_3)^{1/8}$

if $N \lessapprox d'$ , where $d' := d / (c_1,d_1) (c_2,d_2)$ , $s'_1 = (s_1,d')$ , $s'_2 := (s_2,d')$ , and $s'_3 := (s_3,d')$ . As $d$ is $x^\delta$ -smooth, we may choose a factorisation $d_1 d_2 = s_1 s_2 s_3$ with

$x^{-5\delta/7} N^{3/7} d^{1/7} \leq s_1 \leq x^{2\delta/7} N^{3/7} d^{1/7}$

and

$x^{-3\delta/7} N^{-1/7} d^{2/7} \leq s_2 \leq x^{4\delta/7} N^{-1/7} d^{2/7}$

(note that $d \geq r \sim R \sim x^{-\varepsilon} N$ , so $N^{-1/7} d^{2/7} \geq 1$ ) so that

$s_3 \leq x^{8\delta/7} N^{-2/7} d^{4/7}$

and thus

$|S| \lessapprox x^{\delta/7} N^{5/7} (d_1 d_2)^{1/14}$ .

Using completion of sums to handle the opposite case $N \gtrapprox x^\varepsilon d'$ as in the previous comment, we conclude that

$|S| \lessapprox N^{5/7} x^{\delta/7} (d_1 d_2)^{1/14} + \frac{(c_1,d_1)}{d_1} \frac{(c_2,d_2)}{d_2}N.$

Using this bound, we can improve the RHS in Lemma 10 of this post to

$N^{5/7} x^{\delta/7} (Q^3 R)^{1/14}+ (hq'_2-h'q_2,r) R^{-1} N$ .

The non-diagonal contribution to (50) is then

$\lessapprox H^2 Q^2 ( N^{5/7} x^{\delta/7} (Q^3 R)^{1/14}+ R^{-1} N)$

which needs to be $\lessapprox x^{-\varepsilon} Q^2 N$

leading to the conditions

$H^2 (Q^3 R)^{1/14} \lessapprox x^{-\delta/7 - \varepsilon} N^{2/7}$

and

$H^2 R^{-1} \lessapprox x^{-\varepsilon}$ .

As $H = x^\varepsilon Q^2 R / M$ and $NM \sim x$ , this becomes

$(QR)^{59/14} \lessapprox x^{2-\delta/7 - 3\varepsilon} (R/N)^{15/7} N^{3/7}$

$(QR)^4 \lessapprox x^{2-3\varepsilon} (R/N)^3 N$

which since $QR \lessapprox x^{1/2+2\varpi}$ , $N \gtrapprox x^{1/2-\sigma}$ , and $x^{-\delta-\mu} N \lessapprox R \lessapprox x^{-\mu} N$ for an infinitesimal $\mu$ , leads to the constraints

$\frac{59}{14} (\frac{1}{2} + 2 \varpi) < 2 - \frac{16}{7} \delta + \frac{3}{7} (\frac{1}{2} - \sigma)$

and

$4 (\frac{1}{2} + 2 \varpi) < 2 - 3 \delta + \frac{1}{2} - \sigma$

which may be rearranged as

$\frac{236}{3} \varpi + \frac{64}{3} \delta + 4 \sigma < 1$

and

$8 \varpi + 3 \delta + \sigma < \frac{1}{2}$ .

The second constraint is clearly dominated by the first and so may be dropped. We conclude the “Level 4” bound that the Type I estimates hold for $\frac{236}{3} \varpi + \frac{64}{3} \delta + 4 \sigma < 1$ . This is significantly worse than the previous claim of $40 \varpi + C \delta + 4 \sigma < 1$ coming from https://terrytao.wordpress.com/2013/06/22/bounding-short-exponential-sums-on-smooth-moduli-via-weyl-differencing/#comment-236039 ; there were two arithmetic errors in the previous analysis, namely that a factor of $x^{4\varpi}$ actually should have been $x^{8\varpi}$ , and also an expression $\frac{1}{2} + 2\sigma +4 \varpi$ should have been $\frac{1}{2} + 2 \sigma + 6 \varpi$ . Playing this estimate off against the combinatorial constraint $\sigma > 1/10$ gives $\varpi < 9/1180 \approx 1/131$ , which is a little worse than what we currently have. The moral here seems to be that the small gain coming from the second van der Corput is not quite strong enough to compensate for the large number of additional factors of $\varpi$ one loses when trying to use that estimate.

On the plus side, it means that we don't have to think about double dense divisibility immediately…

29 June, 2013 at 4:42 am

Eytan Paldi

In the page “distribution of primes in smooth moduli” the coefficient of
$\varpi$ should be $236/3$ .

[Corrected, thanks – T.]

29 June, 2013 at 5:25 am

Gergely Harcos

A comment and a typo:

1. Besides (38), we also need the hypothesis $R \lessapprox x^{-c} M$ , which is (33) from the earlier thread (https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/). This is automatic from (31) when $M, N$ are not too close to $x^{1/2}$ , e.g. under (48), but it requires $\mu\geq c$ in general. If (48) fails, then we choose $\mu := 2\varpi + c$ , which is admissible.

2. “(45), (46), (49)” should be “(45), (46), (47)”: 3 occurrences.

[Corrected, thanks – T.]

29 June, 2013 at 10:31 am

Gergely Harcos

I thought we had to be a bit more careful about $c$ . Clearly, $R \ll x^{-c+o(1)} M$ holds for $c$ small enough, but “small enough” really means “depending on $\mu$ “. On the other hand, in deriving Theorem 6 from Theorems 8 and 9, we make a choice of $\mu$ depending on $c$ . So without further comment, $\mu$ and $c$ depend mutually on each other and the two dependencies might be contradictory. So I thought we had to make sure that for the choice of $\mu$ we make, $c$ is sufficiently small relative to it so that $R \ll x^{-c+o(1)} M$ holds. This is why I said that assuming (48) any $\mu>0$ is good, while not assuming (48) any $\mu\geq c$ is good. Sorry if I am missing something. I wish you a good trip!

29 June, 2013 at 11:02 am

Terence Tao

Ah, I see what you are saying now. What’s happening is that I’m using c for two independent small quantities; I’ll change the second c to c’ to avoid circular dependenices.

29 June, 2013 at 11:45 am

Gergely Harcos

Thank you, it is clear now!

29 June, 2013 at 7:53 am

Terence Tao

I am beginning to suspect that the Type I/II analysis could be simplified by removing the somewhat intricate arguments Zhang uses to enforce that $q_1,q_2$ are coprime. (This would also remove the “controlled multiplicity” hypothesis from the congruence classes, and also remove most of the upper bound constraints on $R$ , potentially leading to some improvement in the numerology.) I have to check the details, but I think one of the main reasons Zhang needed coprimality (other than to make certain formulae look nicer) is that his exponential sum estimate on incomplete Kloosterman sums (Lemma 11 from Zhang’s paper) was a bit inefficient in the non-coprime case (his factors of $(c_1,d_1) (c_2,d_2)$ in that Lemma should really be $(c_1,d'_1) (c_2,d'_2)$ where $d'_i = d_i/(d_1,d_2)$ ). Otherwise, having common factors between the q’s actually _helps_ the analysis by making the overall modulus $r[q_1,q_2,q'_2]$ smaller. Again, I have to check the details…

p.s. I’m leaving for Budapest today, probably will be out of action here for a day or so.

29 June, 2013 at 10:55 am

Terence Tao

OK, I now see where coprimality is really used. If one skips the reduction to the coprime case $(q_1,q_2)=1$ in the Type I/II analysis, one eventually has a little difficulty with the “main term” $X_k$ in the analysis (the display after (36) in https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/ ), which becomes

$\sum_{q_1,q_2: (q_1,r)=(q_2,r)=1: (q_1,q_2)|k} \sum_{n: (n,q_1r) = (n+kr,q_2)=1}$
$\frac{c_{q_1} c_{q_2} \beta(n) \beta(n+kr)}{r[q_1,q_2]} 1_{b_{q_1} = b'_{q_2}\ (q_1,q_2)} \sum_m \psi_M(m).$

The problem comes from the new factor $1_{b_{q_1} = b'_{q_2}\ (q_1,q_2)}$ , which in the non-coprime case depends on the choice of $b_{q_1}, b'_{q_2}$ and so cannot actually be dumped into the main term $X_k$ in the non-coprime case. However in that case one can estimate this expression crudely, using $q_0 = (q_1,q_2)$ , as

$\frac{MN \log^{O(1)} x}{R} \sum_{q_0 > 1: q_0 | k} \frac{1}{q_0}$

and on averaging in k we and using the lower bound $q_0 \geq D_0$ we can show that this expression is (barely) acceptable as an error term rather than a main term. So we can’t get rid of the reduction that makes $q$ free of tiny primes. On the other hand, by reworking the argument in the above way we can avoid the need to assume controlled multiplicity altogether in Zhang’s theorem, thus strengthening it slightly.

I also now see that the condition $R \lessapprox x^{-\varepsilon} N$ is necessary for the dispersion method to work, otherwise the condition $mn = a_r\ (r)$ basically determines $n$ from $m, r$ and there is nothing to disperse!

30 June, 2013 at 12:39 pm

Bounded gaps between primes (Polymath8) – a progress report | What's new

[…] sketch of Zhang’s argument for establishing Type I estimates (details may be found at these two posts). It is based on previous arguments of Bombieri, Friedlander, and Iwaniec, relying on various […]

30 June, 2013 at 12:40 pm

Terence Tao

Rolling over to a new thread at https://terrytao.wordpress.com/2013/06/30/bounded-gaps-between-primes-polymath8-a-progress-report/ (we traditionally do this every 100 comments or so, but the comments in this thread are particularly lengthy and technical and so I thought it would be good to recap with a fresh thread).

30 June, 2013 at 3:56 pm

Gergely Harcos

I think that Theorem 8 can be improved in that (47) can be omitted. We observe first that (52) can be supplemented by

$(c_1, q_1) = (hq'_2-h'q_2, q_1)$ ,

as follows from the explicit formula

$c_1 := (hq'_2 - h'q_2) (a_r \bar{q_1} \bar{q_2} \bar{q'_2} q_1 + b_{q_1} \bar{r} \bar{q_2} \bar{q'_2} r)\ (d_1).$

Using also $d_1=q_1r\sim QR$ , the last term in (51) can be improved to

$(QR)^{-1/4} N (hq'_2-h'q_2,q_1r)^{1/4}$ .

The improvement is really by a factor of $Q^{-1/4}(hq'_2-h'q_2,q_1)^{1/4}$ , since $(q_1,r)=1$ . By going back to earlier parts of the argument, we see that we need to average this over $q_1\sim Q$ , and then sum over $h,h',q_2,q_2'$ with $hq_2'\neq h'q_2$ . This way we gain a factor of $\lessapprox Q^{-1/4}$ over the original contribution of the last term in (51). Therefore, instead of

$H^2 Q^2 R^{-1/4} N \lessapprox x^{-2\epsilon} Q^2 N$ ,

we only need to ensure

$H^2 Q^2 (QR)^{-1/4} N \lessapprox x^{-2\epsilon} Q^2 N$ ,

that is,

$(QR)^{15/4} \lessapprox x^{2-4\epsilon} (R/N)^2$ .

In short, the last display of Section 3 can be replaced by

$\frac{15}{4}(\frac{1}{2} + 2 \varpi) < 2-2(\mu + \delta)$ ,

which rearranges to

$15\varpi+4\mu+4\delta<\frac{1}{4}$ .

So this would replace (47), but it follows from (45), hence can be omitted.

I hope I did not make a mistake. I also report two typos:

1. In the line before (52), $d_2:=[q_1,q_2]$ should be $d_2:=[q_2,q_2']$ .

2. In the fifth display of Section 6 of https://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/, $c_{h',q_1,q'_2}$ should be $\overline{c_{h',q_1,q'_2}}$ .

[Corrected, thanks. It looks like this improvement does not make the dominant inequalities any better, at least currently, but it may become useful at some later stage. -T]

4 July, 2013 at 11:55 pm

Gergely Harcos

Just a minor comment. In the last line in the proof of Lemma 11, “since $r$ divides $d_1$ but not $d_2$ ” should be “since $r$ divides $d_1$ but is coprime to $d_2$ “.

[Corrected, thanks – T.]

7 July, 2013 at 11:17 pm

The distribution of primes in doubly densely divisible moduli | What's new

[…] improves upon the previous constraint of (see this previous post), although that latter statement was stronger in that it only required single dense divisibility […]

8 July, 2013 at 3:03 pm

Gergely Harcos

Just a typo: in (36), $n = a_r\ (r)$ should be $mn = a_r\ (r)$ .

[Corrected, thanks – T.]

10 July, 2013 at 7:13 pm

Gergely Harcos

A question and some typos:

1. In the third display below Proposition 12, we have the constraint $(m,d_1)=1$ . Why is it not $(m,d_1d_2)=1$ as dictated by $(n,d_1d_2)=1$ from the previous display?

2. In the first display below Proposition 12, $F(d_2 h)$ should be $F(d_2 h')$ .

3. In the second and third display below Proposition 12, $(h,d_1)$ should be $(h',d_1)$ .

4. In the display following (63), $(h,d_1)$ should be $(h',d_1)$ .

[Corrected, thanks. The additional constraint $(m,d_2)=1$ does indeed need to be placed on $m$ but this is harmless as one simply applies Proposition 12 with a suitably truncated version of $\alpha$ . -T]

11 July, 2013 at 5:25 am

Gergely Harcos

Another question and two typos:

1. In the discussion below Proposition 12, you say that (62) with the appropriate parameters follows from (17). My calculation tells me that instead of (17) we need the slightly stronger bound $N_1 N_2 \gtrapprox x^{1/2+6\varpi+\epsilon}$ . More precisely, we want

$M (\frac{N_2}{b_2})^2 (\frac{N_3}{b_3}) \gtrapprox (b_2 b_3)^{-2} d_1 (x^\epsilon \frac{d_1}{N_1})^2 x^c$ ,

$M N_1^2 N_2^2 N_3 \gtrapprox b_3^{-1} d_1^3 x^{2\epsilon+c}$ ,

$x N_1 N_2 \gtrapprox (x^{1/2+2\varpi})^3 x^{2\epsilon+c}$ ,

$N_1 N_2 \gtrapprox x^{1/2+6\varpi+2\epsilon+c}$ .

Am I missing something?

2. “values coprime to $d_1$ ” should be “values coprime to $d_1d_2$ “.

3. In (63) and in the display before (64), $b_3|d_3$ should be $b_3|d_2$ .

[Corrected, thanks. Increasing $3\varpi$ to $6\varpi$ causes some changes in the final calculations, but fortunately only for non-dominant inequalities, and the final constraint on $\varpi,\delta$ remains unchanged. -T.]

11 July, 2013 at 8:26 pm

Gergely Harcos

A few suggestions and typos:

1. In (66) and subsequent displays, I would put $\alpha \ast \psi_3(n_3)$ into parentheses.

2. In the proof of Proposition 12 you remark that (59) implies $1 \leq n_2 h', n'_2 h \leq d$ . I think (59) only implies $1 \leq n_2 h', n'_2 h \lessapprox x^{\epsilon} d$ , so the subsequent bound for $\sum_l \nu(l)^2$ needs an extra factor of $x^{\epsilon}$ .

3. In the three display following (71), the condition $(m,d)=(m',d)=1$ is missing, and $\overline{\psi_3}(n_3)$ should be $\overline{\psi_3}(n_3')$ .

4. In the second display below (71), a factor $M^2$ is missing on the right hand side.

5. In the third display below (72), the term $e_q( \frac{t}{l} - \frac{t'}{l+k} + \frac{m}{t} - \frac{m'}{t'} )$ is missing. Also, for the sake of the reader, it would be better to use the variables $u,u'$ instead of $t,t'$ in this definition.

6. In the fourth display below (72), the condition $(m',d)=1$ is missing.

7. In (74) and in the third display below (77), $n^{-2\epsilon}$ should be $x^{-2\epsilon}$ .

8. For the sake of the reader I would add more detail regarding the choice of $r|d$ below (77). There is a constant $C>0$ such that $R:=C\min(R_2,R_3)$ exceeds $1$ . If $R\leq d$ , then there is a divisor $r|d$ such that $Rx^{-\delta}\leq r\leq R$ , and any such divisor is admissible by $Rx^{-\delta}\gg R_1$ . Otherwise $R>d$ , hence $r:=d$ is admissible by $R_1\ll d$ .

[Corrected, thanks – T.]

12 July, 2013 at 9:09 am

Gergely Harcos

Dear Terry, sorry for the trouble or if I am wrong, but:

1. We also need to change $n_2 h' = n'_2 h$ to $|n_2 h' - n'_2 h|/d\in\mathbb{Z}\cap[0,O(x^\epsilon)]$ in the second display before (71) and the line that precedes it.

2. In the fourth display below (72), the condition $(m,d)=1$ should be $(mm',d)=1$ .

3. In the third display below (77), $n^{-2\epsilon}$ should be $x^{-2\epsilon}$ .

[Corrected, thanks – T.]

12 July, 2013 at 9:53 am

Gergely Harcos

Somehow these last corrections have not appeared, perhaps due to an upload problem?

[Oops, sorry about that – it should be OK now – T]

	Anonymous on Two announcements: AI for Math…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on Two announcements: AI for Math…
	Anonymous on Two announcements: AI for Math…
	Lior Silberman on Two announcements: AI for Math…
	Terence Tao on Marton’s conjecture in a…
	Terence Tao on 275A, Notes 3: The weak and st…
	Aditya Guha Roy on Two announcements: AI for Math…
	Two announcements: A… on Marton’s conjecture in a…
	Anonymous on Petition to support maths, sta…
	Anonymous on AI Mathematical Olympiad…
	Anonymous on Petition to support maths, sta…
	Anonymous on 254A, Notes 2: The central lim…
	Anonymous on 275A, Notes 3: The weak and st…

The distribution of primes in densely divisible moduli

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

86 comments

Leave a reply to Terence Tao Cancel reply

For commenters

The distribution of primes in densely divisible moduli

Share this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

86 comments

Leave a reply to Terence Tao Cancel reply

For commenters