A combinatorial subset sum problem associated with bounded prime gaps

10 June, 2013 in math.CO, math.NT, polymath | Tags: polymath8, subset sum, Yitang Zhang

The purpose of this post is to isolate a combinatorial optimisation problem regarding subset sums; any improvement upon the current known bounds for this problem would lead to numerical improvements for the quantities pursued in the Polymath8 project. (UPDATE: Unfortunately no purely combinatorial improvement is possible, see comments.) We will also record the number-theoretic details of how this combinatorial problem is used in Zhang’s argument establishing bounded prime gaps.

First, some (rough) motivational background, omitting all the number-theoretic details and focusing on the combinatorics. (But readers who just want to see the combinatorial problem can skip the motivation and jump ahead to Lemma 5.) As part of the Polymath8 project we are trying to establish a certain estimate called ${MPZ[\varpi,\delta]}$ for as wide a range of ${\varpi,\delta > 0}$ as possible. Currently the best result we have is:

Theorem 1 (Zhang’s theorem, numerically optimised) ${MPZ[\varpi,\delta]}$ holds whenever ${207\varpi + 43\delta< \frac{1}{4}}$ .

Enlarging this region would lead to a better value of certain parameters ${k_0}$ , ${H}$ which in turn control the best bound on asymptotic gaps between consecutive primes. See this previous post for more discussion of this. At present, the best value ${k_0=23,283}$ of ${k_0}$ is applied by taking ${(\varpi,\delta)}$ sufficiently close to ${(1/899,71/154628)}$ , so improving Theorem 1 in the neighbourhood of this value is particularly desirable.

I’ll state exactly what ${MPZ[\varpi,\delta]}$ is below the fold. For now, suffice to say that it involves a certain number-theoretic function, the von Mangoldt function ${\Lambda}$ . To prove the theorem, the first step is to use a certain identity (the Heath-Brown identity) to decompose ${\Lambda}$ into a lot of pieces, which take the form

$\displaystyle \alpha_{1} \ast \ldots \ast \alpha_{n} \ \ \ \ \ (1)$

for some bounded ${n}$ (in Zhang’s paper ${n}$ never exceeds ${20}$ ) and various weights ${\alpha_{1},\ldots,\alpha_n}$ supported at various scales ${N_1,\ldots,N_n \geq 1}$ that multiply up to approximately ${x}$ :

$\displaystyle N_1 \ldots N_n \sim x.$

We can write ${N_i = x^{t_i}}$ , thus ignoring negligible errors, ${t_1,\ldots,t_n}$ are non-negative real numbers that add up to ${1}$ :

$\displaystyle t_1 + \ldots + t_n = 1.$

A key technical feature of the Heath-Brown identity is that the weight ${\alpha_i}$ associated to sufficiently large values of ${t_i}$ (e.g. ${t_i \geq 1/10}$ ) are “smooth” in a certain sense; this will be detailed below the fold.

The operation ${\ast}$ is Dirichlet convolution, which is commutative and associative. We can thus regroup the convolution (1) in a number of ways. For instance, given any partition ${\{1,\ldots,n\} = S \cup T}$ into disjoint sets ${S,T}$ , we can rewrite (1) as

$\displaystyle \alpha_S \ast \alpha_T$

where ${\alpha_S}$ is the convolution of those ${\alpha_i}$ with ${i \in S}$ , and similarly for ${\alpha_T}$ .

Zhang’s argument splits into two major pieces, in which certain classes of (1) are established. Cheating a little bit, the following three results are established:

Theorem 2 (Type 0 estimate, informal version) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever

$\displaystyle t_i > \frac{1}{2} + 2 \varpi$

for some ${i}$ .

Theorem 3 (Type I/II estimate, informal version) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever one can find a partition ${\{1,\ldots,n\} = 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$

where ${\sigma}$ is a quantity such that

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

Theorem 4 (Type III estimate, informal version) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever one can find ${t_i,t_j,t_k}$ with distinct ${i,j,k \in \{1,\ldots,n\}}$ with

$\displaystyle t_i \leq t_j \leq t_k \leq \frac{1}{2}$

and

$\displaystyle 4t_k + 4t_j + 5t_i > 4 + 16 \varpi + \delta.$

The above assertions are oversimplifications; there are some additional minor smallness hypotheses on ${\varpi,\delta}$ that are needed but at the current (small) values of ${\varpi,\delta}$ under consideration they are not relevant and so will be omitted.

The deduction of Theorem 1 from Theorems 2, 3, 4 is then accomplished from the following, purely combinatorial, lemma:

Lemma 5 (Subset sum lemma) Let ${\varpi,\delta > 0}$ be such that

$\displaystyle 207\varpi + 43\delta < \frac{1}{4}. \ \ \ \ \ (2)$

Let ${t_1,\ldots,t_n}$ be non-negative reals such that

$\displaystyle t_1 + \ldots + t_n = 1.$

Then at least one of the following statements hold:

(Type 0) There is ${1 \leq i \leq n}$ such that ${t_i > \frac{1}{2} + 2 \varpi}$ .

(Type I/II) There is a partition ${\{1,\ldots,n\} = 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$

where ${\sigma}$ is a quantity such that

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

(Type III) One can find distinct ${t_i,t_j,t_k}$ with
$\displaystyle t_i \leq t_j \leq t_k \leq \frac{1}{2}$

and

$\displaystyle 4t_k + 4t_j + 5t_i > 4 + 16 \varpi + \delta.$

The purely combinatorial question is whether the hypothesis (2) can be relaxed here to a weaker condition. This would allow us to improve the ranges for Theorem 1 (and hence for the values of ${k_0}$ and ${H}$ alluded to earlier) without needing further improvement on Theorems 2, 3, 4 (although such improvement is also going to be a focus of Polymath8 investigations in the future).

Let us review how this lemma is currently proven. The key sublemma is the following:

Lemma 6 Let ${1/10 < \sigma < 1/2}$ , and let ${t_1,\ldots,t_n}$ be non-negative numbers summing to ${1}$ . Then one of the following three statements hold:

(Type 0) There is a ${t_i}$ with ${t_i \geq 1/2 + \sigma}$ .

(Type I/II) There is a partition ${\{1,\ldots,n\} = 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}$ .

Proof: Suppose Type I/II never occurs, then every partial sum ${\sum_{i \in S} t_i}$ is either “small” in the sense that it is less than or equal to ${1/2-\sigma}$ , or “large” in the sense that it is greater than or equal to ${1/2+\sigma}$ , since otherwise we would be in the Type I/II case either with ${S}$ as is and ${T}$ the complement of ${S}$ , or vice versa.

Call a summand ${t_i}$ “powerless” if it cannot be used to turn a small partial sum into a large partial sum, thus there are no ${S \subset \{1,\ldots,n\} \backslash \{i\}}$ such that ${\sum_{j \in S} t_j}$ is small and ${t_i + \sum_{j \in S} t_j}$ is large. We then split ${\{1,\ldots,n\} = A \cup B}$ where ${A}$ are the powerless elements and ${B}$ are the powerful elements.

By induction we see that if ${S \subset B}$ and ${\sum_{i \in S} t_i}$ is small, then ${\sum_{i \in S} t_i + \sum_{i \in A} t_i}$ is also small. Thus every sum of powerful summand is either less than ${1/2-\sigma-\sum_{i \in A} t_i}$ or larger than ${1/2+\sigma}$ . Since a powerful element must be able to convert a small sum to a large sum (in fact it must be able to convert a small sum of powerful summands to a large sum, by stripping out the powerless summands), we conclude that every powerful element has size greater than ${2\sigma + \sum_{i \in A} t_i}$ . We may assume we are not in Type 0, then every powerful summand is at least ${2\sigma + \sum_{i \in A} t_i}$ and at most ${1/2 - \sigma - \sum_{i \in A} t_i}$ . In particular, there have to be at least three powerful summands, otherwise ${\sum_{i=1}^n t_i}$ cannot be as large as ${1}$ . As ${\sigma > 1/10}$ , we have ${4\sigma > 1/2-\sigma}$ , and we conclude that the sum of any two powerful summands is large (which, incidentally, shows that there are exactly three powerful summands). Taking ${t_i,t_j,t_k}$ to be three powerful summands in increasing order we land in Type III. $\Box$

Now we see how Lemma 6 implies Lemma 5. Let ${\varpi,\delta}$ be as in Lemma 5. We take ${\sigma}$ almost as large as we can for the Type I/II case, thus we set

$\displaystyle \sigma := \frac{1}{8} - \frac{11}{2} \varpi - \frac{3}{2} \delta - \epsilon \ \ \ \ \ (3)$

for some sufficiently small ${\epsilon>0}$ . We observe from (2) that we certainly have

$\displaystyle \sigma > 2 \varpi$

and

$\displaystyle \sigma > \frac{1}{10}$

with plenty of room to spare. We then apply Lemma 6. The Type 0 case of that lemma then implies the Type 0 case of Lemma 5, while the Type I/II case of Lemma 6 also implies the Type I/II case of Lemma 5. Finally, suppose that we are in the Type III case of Lemma 6. Since

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

we thus have

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

and so we will be done if

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

Inserting (3) and taking ${\epsilon}$ small enough, it suffices to verify that

$\displaystyle \frac{13}{2} (\frac{1}{2}+\frac{1}{8} - \frac{11}{2} \varpi - \frac{3}{2}\delta) > 4 + 16 \varpi + \delta$

but after some computation this is equivalent to (2).

It seems that there is some slack in this computation; some of the conclusions of the Type III case of Lemma 5, in particular, ended up being “wasted”, and it is possible that one did not fully exploit all the partial sums that could be used to create a Type I/II situation. So there may be a way to make improvements through purely combinatorial arguments. (UPDATE: As it turns out, this is sadly not the case: consderation of the case when ${n=4}$ , ${t_1 = 1/4 - 3\sigma/2}$ , and ${t_2=t_3=t_4 = 1/4+\sigma/2}$ shows that one cannot obtain any further improvement without actually improving the Type I/II and Type III analysis.)

A technical remark: for the application to Theorem 1, it is possible to enforce a bound on the number ${n}$ of summands in Lemma 5. More precisely, we may assume that ${n}$ is an even number of size at most ${n \leq 2K}$ for any natural number ${K}$ we please, at the cost of adding the additioal constraint ${t_i > \frac{1}{K}}$ to the Type III conclusion. Since ${t_i}$ is already at least ${2\sigma}$ , which is at least ${\frac{1}{5}}$ , one can safely take ${K=5}$ , so ${n}$ can be taken to be an even number of size at most ${10}$ , which in principle makes the problem of optimising Lemma 5 a fixed linear programming problem. (Zhang takes ${K=10}$ , but this appears to be overkill. On the other hand, ${K}$ does not appear to be a parameter that overly influences the final numerical bounds.)

Below the fold I give the number-theoretic details of the combinatorial aspects of Zhang’s argument that correspond to the combinatorial problem described above.

— 1. Coefficient sequences —

We now give some number-theoretic background material that will serve two purposes. The most immediate purpose is to enable one to understand the precise statement of Theorems 1, 2, 3, 4, as well as the deduction of the first theorem from the other three. A secondary purpose is to establish some reference material which will be used in subsequent posts on the Type I/II and Type III analysis in Zhang’s arguments.

As in previous posts, we let ${x}$ be an asymptotic parameter tending to infinity and define the usual asymptotic notation ${O(), o(), \ll}$ relative to this parameter. It is also convenient to have a large fixed quantity ${A_0>0}$ to be chosen later, in order to achieve a fine localisation of scales.

It will be convenient to set up some notation regarding certain types of sequences, abstracting some axioms appearing in the work of Bombieri-Friedlander-Iwaniec and Zhang:

Definition 7 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) \ \ \ \ \ (4)$

for all ${n}$ , where ${\tau}$ is the divisor function. (In particular, any sequence that is pointwise dominated by a coefficient sequence is again a coefficient sequence.)

(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). \ \ \ \ \ (5)$

Note that this expression is linear in ${\alpha}$ , so in particular we have the triangle inequality

$\displaystyle |\Delta(\alpha+\beta; a\ (q))| \leq |\Delta(\alpha; a\ (q))| + |\Delta(\beta; a\ (q))|. \ \ \ \ \ (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 obey the Elliott-Halberstam conjecture up to scale ${M}$ for some ${1 \ll M \ll N}$ if one has
$\displaystyle \sum_{q < M} \sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\alpha; a\ (q))| \ll N \log^{-A} x \ \ \ \ \ (8)$

for any fixed ${A>0}$ . Thus for instance the Siegel-Walfisz theorem implies the Elliott-Halberstam conjecture up to scale ${\log^C x}$ for any fixed ${C}$ .

(v) 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 ) \ \ \ \ \ (9)$

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

To control error terms, we will frequently use the following crude bounds:

Lemma 8 (Crude estimates) Let ${\alpha}$ be a coefficient sequence, let ${C>0}$ be fixed, and let ${1 \ll y \ll x^C}$ . Then we have

$\displaystyle \sum_{d \leq y} \frac{|\alpha(d)|^C}{d} \ll \log^{O(1)} x \ \ \ \ \ (10)$

and

$\displaystyle \sum_{d \leq y} |\alpha(d)|^C \ll y \log^{O(1)} x; \ \ \ \ \ (11)$

more generally one has

$\displaystyle \sum_{d \leq y: d = a\ (q)} |\alpha(d)|^C \ll \frac{y}{q} \tau^{O(1)}(q) \log^{O(1)} x + y^{o(1)}; \ \ \ \ \ (12)$

for any congruence class ${a\ (q)}$ (not necessarily primitive). In particular, if ${\alpha}$ is at scale ${N}$ for some ${1 \ll N \ll x^C}$ , one has

$\displaystyle \sum_{d} |\alpha(d)|^C \ll N \log^{O(1)} x \ \ \ \ \ (13)$

and

$\displaystyle \sum_{d: d = a\ (q)} |\alpha(d)|^C \ll \frac{N}{q} \tau^{O(1)}(q) \log^{O(1)} x + N^{o(1)} \ \ \ \ \ (14)$

and hence from (5) we have the crude discrepancy bound

$\displaystyle |\Delta(\alpha; a \ (q))| \ll\frac{N}{q} \tau^{O(1)}(q) \log^{O(1)} x + N^{o(1)}. \ \ \ \ \ (15)$

(In particular, the Siegel-Walfisz estimate (7) is trivial unless ${r = O(\log^{O(1+A)} x)}$ .) Finally, we have the crude bound

$\displaystyle \alpha(d) = O( x^{o(1)} ) \ \ \ \ \ (16)$

for all ${1 \leq d \leq x^C}$ .

Proof: To prove (10) it suffices from (4) to show that

$\displaystyle \sum_{d \leq x^C} \frac{\tau(n)^{O(1)}}{n} \ll \log^{O(1)} x,$

but this follows from e.g. Lemma 8 of this previous post. From (10) we also deduce (11). To show (12), it suffices to show that

$\displaystyle \sum_{d \leq y: d = a\ (q)} \tau^{O(1)}(d) \ll \frac{y}{q} \tau^{O(1)}(q) \log^{O(1)} y + y^{o(1)}$

(i.e. a Brun-Titchmarsh type inequality for powers of the divisor function); this estimate follows from this paper of Shiu or this paper of Barban-Vehov, and can also be proven using the methods in this previous blog post. (The factor of ${\tau^{O(1)}(q)}$ is needed to account for the possibility that ${a\ (q)}$ is not primitive, while the ${y^{o(1)}}$ term accounts for the possibility that ${q}$ is as large as ${y^{1-o(1)}}$ .) Finally, (16) follows from the standard divisor bound; see this previous post. $\Box$

As a general rule, we may freely use (16) when we are expecting a net power savings ${x^{-\epsilon}}$ to come from another part of the analysis, and we may freely use the other estimates in Lemma 8 when we have a net super-logarithmic savings ${\log^{-A} x}$ from elsewhere in the analysis. When we have neither a net power savings or a net super-logarithmic savings from other sources then we usually cannot afford to use any of the bounds in Lemma 8.

The concept of a coefficient sequence is stable under the operation of Dirichlet convolution operation

$\displaystyle f \ast g(n) := \sum_{d|n} f(d) g(\frac{n}{d}):$

Lemma 9 Let ${\alpha,\beta}$ be coefficient sequences. Then:

(i) ${\alpha \ast \beta}$ is also a coefficient sequence.

(ii) If ${\alpha,\beta}$ are coefficient sequences at scales ${M,N}$ respectively, then ${\alpha \ast \beta}$ is a coefficient sequence at scale ${MN}$ .

(iii) If ${\alpha,\beta}$ are coefficient sequences at scales ${M,N}$ respectively, with ${x^c \ll N \ll x^C}$ for some fixed ${C,c>0}$ , and ${\beta}$ obeys a Siegel-Walfisz theorem, then ${\alpha \ast \beta}$ also obeys a Siegel-Walfisz theorem (at scale ${NM}$ ).

(iv) If ${\alpha,\beta}$ are coefficient sequences at scales ${M,N}$ respectively, with ${x^c \ll N \ll x^C}$ for some fixed ${C,c>0}$ , and ${\beta}$ obeys the Elliott-Halberstam conjecture up to some scale ${L}$ , then ${\alpha \ast \beta}$ (viewed as a coefficient sequence at scale ${NM}$ ) also obeys the Elliott-Halberstam conjecture up to scale ${L}$ .

(v) If ${L}$ is the logarithm function, then ${L \alpha}$ is a coefficient sequence. Furthermore, if ${\alpha}$ is smooth at some scale ${N}$ , then ${L\alpha}$ is smooth at that scale also.

Proof: To verify (i), observe from (4) that for any ${n}$ one has

$\displaystyle \alpha \ast \beta(n) \ll \sum_{d|n} (\log^{O(1)}) x \tau(d)^{O(1)} \tau(\frac{n}{d})^{O(1)}$

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

so that ${\alpha \ast \beta}$ is again a coefficient sequence. The claim (ii) then follows by considering the support of ${\alpha \ast \beta}$ .

Now we verify (iii). We need to show that

$\displaystyle |\Delta((\alpha \ast \beta)1_{(\cdot,q)=1}, a\ (r))| \ll \tau(qr)^{O(1)} N \log^{-A} x$

for any ${q}$ and any residue class ${a\ (r)}$ . By restricting ${\alpha,\beta}$ to integers coprime to ${qr}$ (and noting that the restricted version of ${\beta}$ still obeys the Siegel-Walfisz property if one divides out by a suitable power of ${\tau(qr)}$ ) we may assume that ${\alpha,\beta}$ are supported on integers coprime to ${qr}$ , at which point we may drop the ${1_{(\cdot,qr)=1}}$ constraint. As noted in Lemma 8 we may also assume that ${r = O( \log^{A+O(1)} x)}$ .

We now have

$\displaystyle \sum_{n = a\ (r)} \alpha \ast \beta(n) = \sum_{b,c\in ({\bf Z}/r{\bf Z})^\times: a=bc} (\sum_{d = b\ (r)} \alpha(d)) (\sum_{m = c\ (r)} \beta(m))$

and

$\displaystyle \sum_{n} \alpha \ast \beta(n) = (\sum_d \alpha(d)) (\sum_m \beta(m))$

$\displaystyle = \sum_{b,c \in ({\bf Z}/r{\bf Z})^\times: a=bc} (\sum_{d = b\ (r)} \alpha(d)) (\sum_m \beta(m))$

and by the triangle inequality so we may upper bound ${|\Delta(\alpha \ast \beta, a\ (r))|}$ by

$\displaystyle \sum_{b,c \in ({\bf Z}/r{\bf Z})^\times: a=bc} |\sum_{d = b\ (r)} \alpha(d)| | \Delta(\beta; c\ (r))|.$

Applying (7) for ${\beta}$ and (14) for ${\alpha}$ , we may bound this by

$\displaystyle \ll \tau(r)^{O(1)} \log^{-A' + O(1)} x \sum_{b,c \in ({\bf Z}/r{\bf Z})^\times: a=bc} ( \frac{N}{r} + N^{o(1)} ) M$

for any fixed ${A'}$ , which is acceptable using the bound on ${r}$ .

Now we verify (iv), which is similar to (iii). Arguing as before, we have the inequality

$\displaystyle \sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\alpha \ast \beta; a\ (q))| \ll (\sum_{d} |\alpha(d)|) \sup_{c \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\beta; c\ (q))|.$

The claim then follows from (13) and the Elliott-Halberstam hypothesis for ${\beta}$ .

Finally, (v) is an easy consequence of the product rule and is left to the reader. $\Box$

We also have some basic sequences that obey the Siegel-Walfisz property:

Lemma 10 Let ${\alpha}$ be a smooth coefficient sequence at some scale ${N}$ with ${x^c \ll N \ll x^C}$ for some fixed ${C, c>0}$ . Then

(i) ${\alpha}$ obeys the Siegel-Walfisz theorem.

(ii) In fact, ${\alpha}$ obeys the Elliott-Halberstam conjecture up to scale ${x^{-\epsilon} N}$ for any fixed ${\epsilon>0}$ .

(iii) ${\mu\alpha}$ obeys the Siegel-Walfisz theorem, where ${\mu}$ is the Möbius function.

Note that some lower bound on ${N}$ is necessary here, since one cannot hope for a sequence to be equidistributed to the extent predicted by the Siegel-Walfisz theorem (7) if the sequence is only supported on a logarithmic range!

Proof: We first prove (i). Our task is to show that

$\displaystyle |\Delta(\alpha 1_{(\cdot,q)=1}, a\ (r))| \ll \tau(qr)^{O(1)} N \log^{-A} x$

for any ${q}$ and any residue class ${a\ (r)}$ . By applying the Möbius inversion formula

$\displaystyle 1_{(n,q)=1} = \sum_{d|q} \mu(d) 1_{n = 0\ (d)}$

and the triangle inequality (6) we thus see that it suffices to show that

$\displaystyle |\Delta(\alpha 1_{d|\cdot}, a\ (r))| \ll \tau(dr)^{O(1)} N \log^{-A} x$

for any ${d}$ . We may assume that ${r}$ is coprime to ${d}$ as the left-hand side vanishes otherwise. Our task is now to show that

$\displaystyle \sum_{n: n = 0\ (d); n = a\ (r)} \alpha(n) = \frac{1}{\phi(r)} \sum_{n: n = 0\ (d); (n,r)=1} \alpha(n) + \tau(dr)^{O(1)} N \log^{-A} x.$

For this it will suffice to establish the claim

$\displaystyle \sum_{n} \alpha(n) 1_{n = a\ (q)} = \frac{1}{q} (\sum_n \alpha(n)) + O( \tau(q)^{O(1)} N \log^{-A} x ) \ \ \ \ \ (17)$

for any residue class ${a\ (q)}$ (not necessarily primitive). Note that we may assume that ${q = O( \log^{A+O(1)}(x) )}$ as the claim follows from (14) otherwise. We use the Fourier expansion

$\displaystyle 1_{n=a\ (q)} = \frac{1}{q} \sum_{h \in {\bf Z}/q{\bf Z}} e_q(-ah) e_q(hn)$

where ${e_q(n) := e^{2\pi i n/q}}$ for ${n \in {\bf Z}/q{\bf Z}}$ or (by abuse of notation) for ${n \in {\bf Z}}$ . We can thus write the left-hand side of (17) as

$\displaystyle \frac{1}{q} \sum_{h \in {\bf Z}/q{\bf Z}} e_q(-ah) \sum_n \alpha(n) e_q(hn).$

The ${h=0}$ term here is the first term on the right-hand side of (17). Thus it will suffice to show that

$\displaystyle |\sum_n \alpha(n) e_q(hn)| \ll N \log^{-A} x$

for all non-zero ${h \in {\bf Z}/q{\bf Z}}$ . But if we write ${\alpha(n) = \psi(n/N)}$ , then by the Poisson summation formula the left-hand side is equal to

$\displaystyle N \sum_m \hat \psi( N m - N h / q )$

where ${\hat \psi(t) := \int_{\bf R} \psi(s) e^{-2\pi i st}\ ds}$ is the Fourier transform of ${\psi}$ . From the smoothness bounds (9) and integration by parts we have

$\displaystyle |\hat \psi(t)| \ll |t|^{-j} \log^{(j-1) A_0} x$

for any fixed ${j>0}$ , so for ${j}$ large enough (actually ${j=2}$ is enough) we obtain the claim thanks to the lower bound ${N \gg x^c}$ and the upper bound ${q = O( \log^{A+O(1)} x)}$ . We remark that the same argument (now with ${j}$ as large as needed) in fact shows the much stronger bound

$\displaystyle \sum_{n} \alpha(n) 1_{n = a\ (q)} = \frac{1}{q} (\sum_n \alpha(n)) + O( \tau(q)^{O(1)} N x^{-A} )$

for any fixed ${A,\epsilon>0}$ and any ${q < x^{-\epsilon} N}$ , which also gives (ii).

To prove (iii), we can argue similarly to before and reduce to showing that

$\displaystyle | \sum_{n} \mu(n) \alpha(n) 1_{n = a\ (q)}| \ll \tau(q)^{O(1)} N \log^{-A} x$

for any ${a\ (q)}$ , but this follows from the Siegel-Walfisz theorem for the Möbius function (which can be deduced from the more usual Siegel-Walfisz theorem for the von Mangoldt function, or else proven by essentially the same method) and summation by parts (if one wishes, one can also reduce to the case of primitive residue classes using the multiplicativity of ${\mu}$ ). $\Box$

We remark that the Siegel-Walfisz theorem for the Möbius function is ineffective, although in practice one can obtain effective substitutes for this theorem that can make applications (such as the one for bounded prime gaps) effective, see e.g. the last section of this article of Pintz for further discussion. One amusing remark in this regard is that if there do happen to be infinitely many Siegel zeroes, then an old result of Heath-Brown shows that there are infinitely mnay twin primes already, so the ineffective case of Siegel-Walfisz’s theorem is in some sense the best case scenario for us!

Lemmas 9 and 10 combine to give plenty of coefficient sequences obeying the Siegel-Walfisz property. This will become useful when the time comes to deduce Theorem 1 from (the precise versions of) Theorems 2, 3, 4.

— 2. Congruence class systems —

The Elliott-Halberstam conjecture on a sequence at scale ${N}$ requires taking a supremum over all primitive residue classes. At present, we do not know how to achieve such a strong claim for non-smooth arithmetic sequences such as ${\Lambda}$ or ${\mu}$ once the modulus goes beyond the level ${N^{1/2}}$ , even if one restricts to smooth moduli. However, Zhang’s work (as well as some of the precursor work of Bombieri, Fouvry, Friedlander, and Iwaniec) allow one to get a restricted version of the Elliott-Halberstam conjecture if one restricts the congruences one is permitted to work with.

Much as with the coefficient sequence axioms, it is convenient to abstract the axioms that a given system of congruence classes will be obeying. For any set ${I \subset {\bf R}}$ , let ${{\mathcal S}_I}$ denote the set of squarefree natural numbers whose prime divisors lie in ${I}$ .

Definition 11 Let ${I \subset {\bf R}}$ . A congruence class system on ${I}$ is a collection ${{\mathcal C} = (C(q))_{q \in {\mathcal S}_I}}$ of sets ${C(q)}$ residue classes for each ${q \in {\mathcal S}_I}$ obeying the following axioms:

(i) (Primitivity) For each ${q \in {\mathcal S}_I}$ , ${C(q)}$ is a subset of ${({\bf Z}/q{\bf Z})^\times}$ .

(ii) (Chinese remainder theorem) For any coprime ${q,r \in {\mathcal S}_I}$ , we have ${C(q) \times C(r) \equiv C(qr)}$ , using the canonical identification between ${({\bf Z}/q{\bf Z})^\times \times ({\bf Z}/r{\bf Z})^\times}$ and ${({\bf Z}/qr{\bf Z})^\times}$ .

(iii) (Uniform bound) There is a fixed ${k_0}$ such that ${|C(p)| \leq k_0}$ for all primes ${p \in I}$ .

If ${|C(p)|=1}$ for all ${p \in I}$ , thus ${C(q) = (a_q)_{q \in {\mathcal S}_I}}$ , we say that ${(C(q))_{q \in {\mathcal S}_I}}$ is a singleton congruence class system.

For any integer ${n}$ , let ${\tau_{\mathcal C}(n)}$ denote the multiplicity function

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

or equivalently

$\displaystyle \tau_{\mathcal C}(n) := 2^{|\{ p \in I: n\ (p) \in C(p) \}|}$

A congruence class system is said to have controlled multiplicity if for any congruence class ${a\ (r)}$ with ${r \in {\mathcal S}_I}$ , we have

$\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)}. \ \ \ \ \ (18)$

for any fixed ${C>1}$ .

Note from Axiom (ii) that a congruence class system can be specified through its values ${C(p)}$ at primes ${p \in I}$ . A simple example of a singleton congruence class system with controlled multiplicity is a fixed congruence class ${C(q) = \{ a\ (q) \}}$ for some fixed non-zero ${a}$ , with ${I}$ avoiding all the prime divisors of ${a}$ . This is a special case of the following more general fact:

Lemma 12 Let ${{\mathcal H}}$ be a fixed admissible ${k_0}$ -tuple for some fixed ${k_0 \geq 2}$ , and let ${h_i \in {\mathcal H}}$ . For any modulus ${q}$ , set

$\displaystyle C_i(q) := \{ a \in ({\bf Z}/q{\bf Z})^\times: P(a) =0 \}$

where ${P(a) := \prod_{h \in {\mathcal H}} (a+h-h_i)}$ . Then for any ${I \subset {\bf R}}$ , ${(C_i(q))_{q \in {\mathcal S}_I}}$ is a congruence class system on ${I}$ with controlled multiplicity.

Similarly, if ${b\ (W)}$ is such that ${b+h-h_i}$ is coprime to ${W}$ for all ${h \in {\mathcal H}}$ and ${I \subset{\bf R}}$ , then the system ${(C_{i,b,W}(q))_{q \in {\mathcal S}_I}}$ defined by setting ${C_{i,b,W}(p) := C_i(p)}$ when ${p}$ is coprime to ${W}$ , and ${C_{i,b,W}(p) := \{ b\ (p)\}}$ when ${p}$ divides ${W}$ , with ${C_{i,b,W}(q)}$ then defined for arbitrary ${q \in {\mathcal S}_I}$ by the Chinese remainder theorem, is also a congruence system on ${I}$ with controlled multiplicity.

Proof: We just prove the first claim, as the second is similar. Axioms (i)-(iii) are obvious; it remains only to verify the controlled multiplicity. Let ${a\ (r)}$ be a congruence class with ${r \in {\mathcal S}_I}$ .

$\displaystyle \sum_{x \ll n \ll x: m = a\ (r)} 2^{2|\{ p \in I: p \not | n; p | P(n) \}|}.$

We can split

$\displaystyle |\{ p \in I: p \not | n; p | P(n) \}| \leq \sum_{h \in {\mathcal H}} |\{ p \in I: p | n + h - h_i\}|$

and hence

$\displaystyle 2^{2|\{ p \in I: p \not | n; p | P(n) \}|} \leq \sum_{h \in {\mathcal H}} 2^{2k_0 |\{ p \in I: p | n + h - h_i\}|}$

$\displaystyle = \sum_{h \in {\mathcal H}} \tau(n+h-h_i)^{2k_0}$

so it suffices to show that

$\displaystyle \sum_{x \ll n \ll x: n = a\ (r)} \tau(n+h-h_i)^{2k_0} \ll \frac{x}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{o(1)} \ \ \ \ \ (19)$

for each ${h \in {\mathcal H}}$ . Writing ${b := a+h-h_i}$ , this becomes

$\displaystyle \sum_{x \ll n \ll x: n = b\ (r)} \tau(n)^{2k_0} \ll \frac{x}{r} \tau(r)^{O(1)} \log^{O(1)} x + x^{o(1)}.$

The claim then follows Lemma 8. $\Box$

The more precise statement of Theorem 1 is now as follows:

Theorem 13 (Zhang’s theorem, numerically optimised) Let ${\varpi, \delta > 0}$ be fixed parameters such that

$\displaystyle 207 \varpi + 43 \delta < \frac{1}{4}. \ \ \ \ \ (20)$

Let ${I \subset [1,x^\delta]}$ , and let ${(C(q))_{q \in {\mathcal S}_I}}$ be a congruence class system with controlled multiplicity. Then

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

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

For the application to prime gaps we only need to apply Theorem 13 to the congruence class system associated to a fixed ${k}$ -tuple ${{\mathcal H}}$ through Lemma 12, but one could imagine that this theorem could have future application with some other congruence class systems.

One advantage of the abstract formulation of a congruence class systems is that we get a cheap reduction to the singleton case:

Proposition 14 (Reduction to singletons) In order to prove Theorem 13, it suffices to do so for good singleton class congruence systems.

Proof: Let ${(C(q))_{q \in {\mathcal S}_I}}$ be a good congruence class system. By removing all primes ${p}$ with ${|C(p)|=0}$ from ${I}$ we may assume without loss of generality that ${1 \leq |C(p)| \leq k_0}$ for all ${p \in I}$ and some fixed ${k_0}$ .

We use the probabilistic method. Construct a random singleton congruence class system ${(\tilde C(q))_{q \in {\mathcal S}_I}}$ by selecting ${a_p}$ uniformly at random from ${C(p)}$ independently for all ${p \in I}$ , and then set ${\tilde C(p) = \{ a_p\}}$ and extend by the Chinese remainder theorem. Writing ${\tilde C(q) = \{ a_q \}}$ , we observe that the property that ${(C(q))_{q \in {\mathcal S}_I}}$ enjoys of being a congruence class system of controlled multiplicity is inherited by ${(\tilde C(q))_{q \in {\mathcal S}_I}}$ . From hypothesis we then have that

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

for any fixed ${A}$ ; taking expectations we conclude that

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} \frac{1}{|C(q)|} \sum_{a \in C(q)} |\Delta(\Lambda 1_{[x,2x]}; a\ (q))| \ll x \log^{-A} x.$

On the other hand, from Lemma 8 we have

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} |C(q)| \sum_{a \in C(q)} |\Delta(\Lambda 1_{[x,2x]}; a\ (q))| \ll x \log^{O(1)} x,$

and the claim then follows from Cauchy-Schwarz. $\Box$

This reduction is not essential to Zhang’s argument (indeed, it is not used in Zhang’s paper), but it does allow for a slightly simpler notation (since the summation over ${a}$ is eliminated).

We can now also state the precise versions of Theorems 2, 3, 4 that we need:

Theorem 15 (Type 0 estimate, precise version) Let ${0 < \varpi < 1/2}$ be fixed, and let ${\alpha,\psi}$ be coefficient sequences at scales ${M,N}$ respectively with ${\psi}$ smooth,

$\displaystyle x \ll MN \ll x,$

and

$\displaystyle N > x^{1/2+2\varpi+\epsilon}$

for some fixed ${\epsilon>0}$ . Then ${\alpha \ast \psi}$ obeys the Elliott-Halberstam conjecture up to scale ${x^{1/2+2\varpi}}$ . In particular, 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: q< x^{1/2+2\varpi}} |\Delta(\alpha \ast \psi; a_q\ (q))| \ll x \log^{-A} x.$

Proof: This is immediate from Lemma 10(ii) and Lemma 9(iv). $\Box$

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

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

and

$\displaystyle 37\varpi + 5 \delta < \frac{1}{4} \ \ \ \ \ (22)$

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

$\displaystyle x \ll MN \ll x$

and

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

with ${\beta}$ obeying a Siegel-Walfisz theorem. Then for any ${I \subset [1,x^\delta]}$ 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: q< x^{1/2+2\varpi}} |\Delta(\alpha \ast \beta; a_q\ (q))| \ll x \log^{-A} x.$

The condition (22) is dominated by (20) and can thus be ignored, at least at our current numerical ranges of parameters. We remark that this theorem is the only theorem that actually uses the controlled multiplicity hypothesis.

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

$\displaystyle N_3 \ll N_2 \ll N_1 \ll x^{1/2}$

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

and

$\displaystyle x \ll MN_1 N_2 N_3 \ll 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 [1,x^\delta]}$ , and any singleton congruence class system ${(\{a_q\})_{q \in {\mathcal S}_I}}$ we have

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

for any fixed ${A>0}$ .

As we saw, Theorem 15 is easy to establish. On the other hand, Theorem 16 and Theorem 17 are far deeper and will be the subject of future blog posts. We will not discuss them further here, but now turn to the question of how to deduce Theorem 13 from Theorems 15, 16, 17 using Lemma 5.

— 3. Decomposing the von Mangoldt function —

The basic strategy is to decompose the von Mangoldt function ${\Lambda}$ as a combination of Dirichlet convolutions of other functions such as ${\mu}$ , the constant function ${1}$ , and the logarithmic function ${L: n \mapsto \log n}$ . The simplest identity of this form is

$\displaystyle \Lambda = \mu \ast L \ \ \ \ \ (23)$

but this is unsuitable for our purposes because when we localise ${\Lambda}$ to scale ${x}$ , the ${\mu}$ factor could also be localised at scales as large as ${x}$ , and our understanding of the equidistribution properties of the Möbius function is basically no better than that of the von Mangoldt function, so we have not gained anything with this decomposition.

To get around this we need to find decompositions that don’t let rough functions such as the Möbius function get up to scales anywhere close to ${x}$ . One promising identity in this regard is Linnik’s identity, which takes the form

$\displaystyle \Lambda = L - L \ast 1^* + L \ast 1^* \ast 1^* - L \ast 1^* \ast 1^* \ast 1^* + \ldots$

where ${1^*(n) := 1_{n \neq 1}}$ is the restriction of the constant function ${1}$ to numbers larger than ${1}$ ; this is just the coefficient version of the formal geometric series identity

$\displaystyle -\frac{\zeta'(s)}{\zeta(s)} = -\zeta'(s) + \zeta'(s) (\zeta(s)-1) - \zeta'(s) (\zeta(s)-1)^2 + \ldots.$

There are no Möbius functions in sight on the right-hand side, which is promising. However, Linnik’s identity has an unbounded number of terms, which render it unsuitable for our argument (we have various factors of ${\tau^{O(1)}(n)}$ and ${\log^{O(1)} x}$ whose exponent would become unbounded if we had to deal with Dirichlet convolutions of unbounded length, which would swamp any gain of ${\log^{-A} x}$ that we are trying to detect). So we will rely on a truncated variant of Linnik’s identity, known as the Heath-Brown identity.

We will need a fixed positive natural number ${K}$ (Zhang takes ${K=10}$ ; the precise choice here does not seem to be terribly important). From the identities ${\Lambda = \mu \ast L}$ and ${\delta = \mu \ast 1}$ , where ${\delta(n) = 1_{n=1}}$ is the Dirichlet convolution identity, we see that we can write ${\Lambda}$ as a ${2K}$ -fold convolution

$\displaystyle \Lambda = \mu^{*K} \ast 1^{*K-1} \ast L \ \ \ \ \ (24)$

where ${\mu^{*K}}$ denotes the convolution of ${K}$ copies of ${\mu}$ .

As with (23), the identity (24) is not directly useful for our strategy because one of the ${\mu}$ factors can still get as large as the scale ${x}$ that we are studying ${\Lambda}$ at. However, as Heath-Brown observed, we can manipulate (24) into a useful form by truncating the Möbius function ${\mu}$ . More precisely, we split the Möbius function ${\mu}$ as

$\displaystyle \mu = \mu_\leq + \mu_>$

where ${\mu_\leq}$ is the Möbius function restricted to the interval ${[1,(2x)^{1/K}]}$ , and ${\mu_>}$ is the Möbius function restricted to the interval ${((2x)^{1/K},\infty)}$ . The reason for this splitting is that the ${K}$ -fold Möbius convolution ${\mu_>^{*K}}$ vanishes on ${[1,2x]}$ , and in particular we have

$\displaystyle 0 = \mu_>^{*K} \ast 1^{*K-1} \ast L$

on ${[x,2x]}$ . Expanding out ${\mu_> = \mu - \mu_\leq}$ and using the binomial formula, we conclude that

$\displaystyle 0 = \sum_{j=0}^K (-1)^{j} \binom{K}{j} \mu^{*K-j} \ast \mu_{\leq}^{j} \ast 1^{*K-1} \ast L \ \ \ \ \ (25)$

on ${[x,2x]}$ .

By (24), the ${j=0}$ term of (25) is just ${\Lambda}$ . For all the other terms, we can cancel ${\mu^{*K-j}}$ against ${1^{*K-j}}$ using the Möbius inversion formula ${\delta = \mu \ast 1}$ to conclude the Heath-Brown identity

$\displaystyle \Lambda =\sum_{j=1}^K (-1)^{j-1} \binom{K}{j} \mu_{\leq}^j \ast 1^{*j-1} \ast L$

on ${[x,2x]}$ . Now we see that each of the Möbius factors ${\mu_{\leq}}$ cannot reach scales much larger than ${x^{1/K}}$ , although the factors ${\mu_{\leq}^j}$ may collectively still get close to ${x}$ when ${j}$ is close to ${K}$ . From the triangle inequality and Proposition 14, we thus see that to establish Theorem 13, it suffices to establish the bounds

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} |\Delta((\mu_{\leq}^j \ast 1^{*j-1} \ast L) 1_{[x,2x]}; a_q\ (q))| \ll x \log^{-A} x \ \ \ \ \ (26)$

whenever ${\varpi,\delta > 0}$ are fixed and obey (20), ${I \subset [1,x^\delta]}$ , ${1 \leq j \leq K}$ , ${A}$ is fixed, and ${(a_q)_{q \in {\mathcal S}_I}}$ is a singleton congruence class system with controlled multiplicity.

This is now looking closer to the type of estimates that can be handled by Theorems 15, 16, 17, but there are still some technical issues to resolve, namely the presence of the cutoff ${1_{[x,2x]}}$ and also the fact that the functions ${\mu_{\leq}}$ , ${1}$ , ${L}$ are not localised to any given scale, but are instead spread out at across many scales. This however can be dealt with by a routine dyadic decomposition (which, in harmonic analysis, is sometimes referred to as Littlewood-Paley decomposition, at least when applied in the frequency domain), though here instead of using the usual dyadic range ${\{ 2^m: m \geq 0 \}}$ of scales, one uses instead a sub-dyadic range ${{\mathcal D} := \{ (1 + \log^{-A_0} x)^m: m \geq 0\}}$ to eliminate edge effects. (This trick dates back at least to the work of Fouvry; thanks to Emmanuel Kowalski for this reference.)

More precisely, let ${A_0}$ be a large fixed number to be chosen later, and let ${\psi: {\bf R} \rightarrow {\bf R}}$ be a smooth function supported on ${[-1-\log^{-A_0} x, 1+\log^{-A_0} x]}$ that equals ${1}$ on ${[-1,1]}$ and obeys the derivative estimates

$\displaystyle |\psi^{(j)}(t)| \ll \log^{jA_0} x$

for any fixed ${j \geq 0}$ (note that the implied constant here can depend on ${j}$ ). We then have a smooth partition of unity

$\displaystyle 1 = \sum_{N \in {\mathcal D}} \psi_N(n)$

indexed by the multiplicative semigroup ${{\mathcal D}}$ for any natural number ${n}$ , where

$\displaystyle \psi_N(n) := \psi( n/N ) - \psi( (1+\log^{-A_0} x) n/N ).$

We can thus decompose

$\displaystyle \mu_{\leq} = \sum_{M \in {\mathcal D}} \mu_{\leq} \psi_M$

and similarly

$\displaystyle 1 = \sum_{N \in {\mathcal D}} \psi_N$

and

$\displaystyle L = \sum_{N \in {\mathcal D}} L\psi_N.$

For ${1 \leq j \leq K}$ , the expression

$\displaystyle (\mu_{\leq}^j \ast 1^{*j-1} \ast L) 1_{[x,2x]}$

can thus be split as

$\displaystyle \sum_{N_1,\ldots,N_2j \in {\mathcal D}} (\mu_{\leq} \psi_{N_1} \ast \ldots \ast \mu_{\leq} \psi_{N_j} \ast \psi_{N_{j+1}} \ast \ldots \ast \psi_{N_{2j-1}} \ast L \psi_{N_{2j}}) 1_{[x,2x]}$

which we can rewrite as

$\displaystyle \sum_{N_1,\ldots,N_{2j} \in {\mathcal D}} \log(N_{2j}) \mu_{\leq} \psi_{N_1} \ast \ldots \ast \mu_{\leq} \psi_{N_j} \ast \psi_{N_1} \ast \ldots \ast \psi_{N_{2j-1}} \ast \psi'_{N_{2j}} 1_{[x,2x]}$

where ${\psi'_N := \frac{L}{\log N} \psi_N}$ is a variant of ${\psi_N}$ .

Observe that the summand vanishes unless

$\displaystyle N_1,\ldots,N_j \ll x^{1/K}$

and

$\displaystyle (1 - O(\log^{-A_0} x)) x \leq N_1 \ldots N_{2j} \leq (1 + O(\log^{-A_0} x)) 2x$

and the ${1_{[x,2x]}}$ factor can be eliminated except in the boundary cases when

$\displaystyle N_1 \ldots N_{2j} = (1 + O(\log^{-A_0} x)) x$

$\displaystyle N_1 \ldots N_{2j} = (1 + O(\log^{-A_0} x)) 2x.$

Let us deal with the contribution of the boundary cases to (26). If we let ${\alpha}$ be the sum of all the boundary summands, then we have

$\displaystyle \alpha(n) \ll \tau(n)^{O(1)} (\log^{O(1)} x) (1_{n = x + O(x \log^{-A_0} x)} + 1_{2n = x + O(x \log^{-A_0} x)}).$

From Lemma 8 we have that

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

and

$\displaystyle \sum_{n = a\ (q)} |\alpha(n)|^2 \ll \frac{x}{q} \tau(q)^{O(1)} \log^{O(1)} x$

for any fixed ${C > 0}$ and any ${q \leq x^{1/2+2\varpi}}$ . On the other hand, ${\alpha}$ is supported on two intervals of length ${O( x \log^{-A_0} x )}$ . Thus by Cauchy-Schwarz one has

$\displaystyle \sum_n |\alpha(n)| \ll x \log^{-A_0/2+O(1)} x$

and

$\displaystyle \sum_{n = a\ (q)} |\alpha(n)| \ll \frac{x}{q} \tau(q)^{O(1)} \log^{-A_0/2+O(1)} x$

for any fixed ${\epsilon>0}$ . We thus have

$\displaystyle |\Delta(\alpha; a\ (q))| \ll \frac{x}{q} \tau(q)^{O(1)} \log^{-A_0/2+O(1)} x$

and hence by Lemma 8 again

$\displaystyle \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} |\Delta(\alpha; a_q\ (q))| \ll x \log^{-A_0/2+O(1)} x$

which is acceptable for (26) if we take ${A_0}$ large enough. Thus it suffices to deal with the contribution of the interior summands, in which the cutoff ${1_{[x,2x]}}$ may be dropped. There are ${O(\log^{2j(A_0+1)} x)}$ such summands, and the ${\log(N_j)}$ factor is bounded by ${\log x}$ , so it will suffice to show that

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

whenever ${N_1,\ldots,N_{2j} \in {\mathcal D}}$ and ${\alpha_1,\ldots,\alpha_{2j}}$ are such that each ${\alpha_i}$ takes the form ${\mu_{\leq} \psi_{N_i}}$ , ${\psi_{N_i}}$ , or ${\psi'_{N_i}}$ . In particular, from Lemmas 9, (10) we observe the following facts for any ${1 \leq i \leq 2j}$ and ${S \subset \{1,\ldots,2j\}}$ :

(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) ${x \ll N_1 \ldots N_{2j} \ll x}$ .

Now we can prove (27). We can write ${x^{t_i} \ll N_i \ll x^{t_i}}$ for ${i=1,\ldots,2j}$ , where the ${t_i}$ are non-negative reals that sum to ${1}$ . We apply Lemma 5 and conclude that the ${t_i}$ obey one of the three conclusions (Type 0), (Type I/II), (Type III) of that lemma. Furthermore, in the Type III case, an inspection of Lemma 6 reveals that we have an additional lower bound ${t_i,t_j,t_k \geq 2\delta}$ available, which in particular implies that ${t_i,t_j,t_k \geq \frac{1}{K} + \epsilon}$ for some fixed ${\epsilon>0}$ if ${K}$ is large enough ( ${K=10}$ will certainly do).

In the Type 0 case, we can write ${\alpha_1 \ast \ldots \ast \alpha_{2j}}$ in a form in which Theorem 15 applies. Similarly, in the Type I/II case we can write ${\alpha_1 \ast \ldots \ast \alpha_{2j}}$ in a form in which Theorem 16 applies, and in the Type III case we can write ${\alpha_1 \ast \ldots \ast \alpha_{2j}}$ in a form in which Theorem 17 applies. Thus in all cases we can establish (27), and Theorem 13 follows.

64 comments

Comments feed for this article

10 June, 2013 at 11:49 am

Omar Aboura

“…we land in Type I/II” should be Type III

[Corrected, thanks – T.]

10 June, 2013 at 12:02 pm

bengreen

Terry, a couple of quick comments: first, I think the $\frac{1}{10}$ term coming from Heath-Brown is a bit of a red herring and should be ignored; my impression is that Heath-Brown is a kind of cut off version of Linnik’s identity and that one should think conceptually in terms of the latter (see my earlier post on this). The only reason you can’t actually use Linnik is that the terms resulting form it do not obey the requisite $\tau(n)^{O(1)}$ bounds.

Second, I convinced myself that the hard case is $n = 4$ and $t_1 = \frac{1}{16} + 3\epsilon$ , $t_2 = t_3 = t_4 = \frac{5}{16} - \epsilon$ , with $\epsilon$ small. I thought that in this case you can either use Type III directly (in Zhang’s notation, with $\mu = t_1, \nu_1 = \nu_2 = \nu_3 = t_2 = t_3 = t_4$ , or you use Type I by grouping the $t_1, t_2$ terms and the $t_3, t_4$ terms. Is there some other way to proceed?

10 June, 2013 at 12:40 pm

v08ltu

It the statement of Theorem 4, it should be subscripts that are distinct, not the $t$ themselves. More roundly, there is a restriction $MN_1\le x_1$ in (A4), which says something about how large the $t$ can be, namely $\sum_{u\ge 4}t_u+t_1\le 3/8+11\omega/2+3\delta/2$ I think, assuming one orders the $t$ -values decreasingly. This is stronger than the stated bound of 1/2 in your Theorem 4.

10 June, 2013 at 12:49 pm

Terence Tao

That condition is indeed stated in Zhang’s paper, but I think it is not actually used in the Type III argument, it is just what comes out of the combinatorial analysis (represented here by Lemma 6). In particular, the quantity $11\varpi/2 + 3\delta/2$ is associated to the Type I analysis rather than the Type III analysis.

10 June, 2013 at 12:55 pm

v08ltu

There is also the issue that, in Zhang’s notation, only $\nu$ can go into a Type III convolution, as it involves just the characteristic function $\chi$ while the $\mu$ involve the Mobius function. I am not sure how this is portrayed in your $t$ -values, perhaps it falls out somewhere.

10 June, 2013 at 1:01 pm

Terence Tao

Yes, this is the “K” issue mentioned at the bottom of the post. As Ben says, one should morally be using the Linnik decomposition in which there are no Mobius factors present (this corresponds to setting $K=\infty$ ). But the Linnik decomposition has an unbounded number of terms and is not directly available, so we use the Heath-Brown decomposition at some level K (Zhang takes $K=10$ ) instead. As such, any factor $t_i$ that is less than or equal to $1/K$ could potentially be coming from a Mobius factor $\mu$ rather than a (piecewise) smooth factor $\chi$ . But in practice the $t_i$ in the Type III analysis will be larger than $1/K$ if we set $K$ large enough (basically because of the lower bound $t_i > 2\sigma$ in Lemma 6) so this is not an issue.

I plan to expand this post shortly with the formal number-theoretic versions of the above statements (rather than just the oversimplified combinatorial cartoon) which will mention these various technicalities.

10 June, 2013 at 1:01 pm

meditationatae

I’ve thought of negating the Conclusion of the Subset sum lemma. It would start: There exist non-negative reals $t_1, \ldots, t_n$ such that $t_1 + \ldots + t_n = 1$ such that none of the following statements hold , etc. If we are given the $t_i$ , it seems to me that a straightforward simple computation will show whether or not any of the three statements hold. In particular, for the statement of Type I/II, one only needs to look at $sigma$ as large as possible while still satisfying the inequality $11\varpi + 3\delta + 2\sigma < \frac{1}{4}.$ That's why I think that "ruling-out" candidate pairs $(\varpi, \delta)$ from the Conclusion of the Subset sum lemma could be easy, given the right choice of $t_1, \ldots, t_n.$ The second observation is as follows: Let $0<c 0$ satisfy the conclusion of the Subset sum lemma, so does $c\varpi , c\delta$ . I was thinking of the case $n=10$ , and I’m curious if $n=8$ might give better bounds. David Bernier

10 June, 2013 at 1:15 pm

pavfer

Hmm, funny,
So,
in each election, in which all voted, there is
either
one party with 55% or more,
or
all parties groupable into two coalitions, each between 45% and 55%,
or
at least three possible 2-party coalitions with 55% or more,
with both coalition partners “non-marginal” and “not-almost-winning”.

Nice :-)

10 June, 2013 at 2:27 pm

Polymath8: Bounded Gaps Between Primes | Combinatorics and more

[…] proof and improving the upper bound for the gaps. Here are links for three posts (I, II, III) on Terry Tao’s blog and for a post on the polymath blog. And here is the table for the world […]

10 June, 2013 at 2:35 pm

qianghua

“Mor precisely” should be More precisely.

[Corrected, thanks – T.]

10 June, 2013 at 2:54 pm

v08ltu

I do realise that you are trying to simplify the picture, but there is some subtlety in why $N_3$ in Zhang is the smallest (not the largest, as might be suggested by selecting $t_k$ the biggest in your Theorem 4).

The point is that Zhang dispenses (via 1-variable Kloos bound) the small $d_1$ in 13.10-13.11 via a bound with $N_3$ in it. This is then used later in comparison to $H=d_1/N_1$ in the middle of page 47 (namely that $H^2=o(d_1)$ ). I don’t know how much of this is mandatory, the arguments could be arranged, and as I pointed out a few days ago, Zhang could also use the Deligne 2-variable bound (treating $H$ trivially) on 13.7 to handle smaller $d$ , see the remark of FI upon their Theorem 4.

It might be that taking $N_3$ the smallest simply means that Zhang can work uniformly, w/o worrying about side issues of the variable ranges.

10 June, 2013 at 2:59 pm

v08ltu

I mean selecting $t_i$ , in the last line of your Theorem 4. In the previous line, you do indeed put the inequalities correct.

10 June, 2013 at 3:04 pm

v08ltu

Let me try to explain my thought, over again. If you look at the bottom line of Theorem 4, you would want to take $t_i$ (with the 5 factor) as the largest. But the previous line in Theorem 4 prohibits this. However, does Zhang’s methodology in these parts (S13&14) really require one to take $t_i\le t_j\le t_k$ , and if not, to what extent can it be modified? Though, perhaps the “critical” case near 5/16 could dominate the analysis anyway.

10 June, 2013 at 5:35 pm

Terence Tao

I’ve now expanded the post significantly to give the number-theoretic details of how Zhang deduces his distribution theorem on the von Mangoldt function from the Type I/II and Type III estimates. (This was primarily achieved by cannibalising part of an enormous post I was writing for all of Zhang’s Theorem 2, before I decided to break it up into more manageable pieces.) The material here can basically be viewed as an exposition of Section 6 of Zhang.

10 June, 2013 at 9:23 pm

Emmanuel Kowalski

Note: the use of intervals of type [x,x(1+L^{-A})^m] is completely standard in this game (it’s already done in Fouvry-Iwaniec or even Fouvry’s “Autour du théorème de Bombieri-Vinogradov”, which is a bit earlier, and I’m sure it was not new then.)

[Article updated to reflect this reference, thanks – T.]

11 June, 2013 at 12:32 am

Nick Cook

(Along the lines of what Ben Green suggested.) If we’re not in type 0 or I/II in the proof of Lemma 6, then the three largest, $t_i$ are in $[2\sigma, 1/2-\sigma]$ ; call them $t_1\ge t_2\ge t_3$ , and let $R$ denote the sum of the rest of the $t_i$ . We could do better than bounding $t_i+t_j\ge (1/2+\sigma)$ for all three pairs if $t_3$ is somewhat smaller than $t_1,t_2$ . That is, if $t_3\le(1-R-\alpha)/3$ for some $\alpha\ge 0$ , we can pick $\sigma$ to ensure Type III of lemma 5 as long as $60\varpi+13\delta\le\alpha$ . If this is not the case, and if $R$ is small enough (smaller than $(1-\beta-\alpha)/13$ for some positive $\beta$ ) then we can again conclude Type III of lemma 5 if $48\varpi+3\delta\le\beta$ (using the relation $4t_1+4t_2+5t_3=4(1-R)+t_3$ ). This leaves the case that $R$ is too large. But then we could pick $\alpha,\beta$ small enough that this puts one of the terms in $(1/2-\sigma,1/2+\sigma)$ , i.e. Type I/II, which we already excluded.

Unfortunately, fiddling with this has not yielded improvement around the special point $(\varpi,\delta)$ you mention (but does seem to increase the feasible region for $(\varpi,\delta)$ in the region $\delta>>\varpi$ ). Perhaps something along these lines could be made to work.

11 June, 2013 at 12:39 am

Michael

I have done the question as a linear programming exercise.
Let $u_i=t_i-t_{i-1}$ and $u_{10}=t_{10}$ , where $t_1\geq t_2\geq \ldots \geq t_{10}$ The conditions I can glean from Lemma 5 are (treating $\delta$ as fixed)

$u_1+2u_2+...+10u_{10}=1\\ -t_2-t_3+\sigma\leq-1/2\\ 5t_1+4t_2+4t_3-16\varpi\geq 4+\delta\\ 11\varpi/2+\sigma\leq1/8-3/2\delta\\ \varpi\geq\delta\\ \sigma\geq 1/10\\ t_1+\sigma\leq 1/2\\ t_3\geq 2\sigma$

then I minimize $\varpi$ as the $u_i$ change.

With the value of $\delta = 1/1000$ I get $\varpi \leq 1/234.0426$ ,
but if I use $4t_1 + 4t_2 + 5t_3$ instead of get $\varpi \leq 1/48.1444$

I don’t have a connection between $\delta$ and $\varpi$ .

11 June, 2013 at 12:56 am

Michael

I just got $3\delta+11\varpi\leq 1/20$ – that is, just let $\sigma=1/10$
What have I missed?

11 June, 2013 at 9:56 am

Terence Tao

Dear Michael,

I think the main issue is that the negation of the Type I/II case is actually rather complicated; in principle there are as many as $2^{10}$ different constraints coming out of this negation, due to all the possible ways to form the subset S. In practice many of these cases are redundant and can be ignored, but it is not immediately obvious that one can discard all but a handful of them as you seem to be doing.

11 June, 2013 at 4:29 pm

Michael

The order of the coordinates doesn’t matter, so I assume $t_1\geq t_2\geq ... t_{10}$ .

You showed that, if it isn’t Type 0 or i/ii, there are exactly three powerful coordinates, any one of which is between $2\sigma$ and $1/2-\sigma$ . This is covered by $t_3\geq 2\sigma$ and
$t_1 \leq 1-\sigma$ . Any two of the powerful coordinates is more than $1/2+\sigma$ , and that is covered by
$t_2+t+3\geq 1/2+\sigma$ .

11 June, 2013 at 2:54 am

Gergely Harcos

Condition (2) in Lemma 5 is optimal, at least for $11\varpi+3\delta\leq\frac{1}{4}$ which is implicit in the Type I/II condition. More precisely, when $207\varpi+43\delta\geq\frac{1}{4}$ , we have the counterexample $t_1=\frac{1}{4}-\frac{3\sigma}{2}$ , $t_2=t_3=t_4=\frac{1}{4}+\frac{\sigma}{2}$ , where $\sigma:=\frac{1}{8}-\frac{11\varpi}{2}-\frac{3\delta}{2}$ . In other words, if we want a better condition than (2), then we have to improve the existing bounds for $n=4$ . (This response was inspired by Ben’s comment above.)

11 June, 2013 at 6:03 am

Dustin G. Mixon

To get strict inequality in $11\varpi+3\delta+2\sigma<\frac{1}{4}$ , you actually want $\sigma<\frac{1}{8}-\frac{11\varpi}{2}-\frac{3\delta}{2}$ , but your counterexample is good. Is the implicit requirement that $11\varpi+3\delta<\frac{1}{4}$ a fundamental limit in Zhang's technique, or can this be weakened as well?

11 June, 2013 at 12:27 pm

Gergely Harcos

My $\sigma$ is not the same as $\sigma$ in Lemma 5. My $\sigma$ (perhaps I should have called it $\sigma_0$ ) is a convenient variable for defining the counterexample, and the example is ok (you can check by hand that it is neither of the three types in Lemma 5). About Zhang’s technique: the condition in Lemma 5 is a certain natural limit, as shown by my example, but hopefully this limit is not a fundamental one.

11 June, 2013 at 10:13 am

Terence Tao

Ah well, so no cheap numerical pickup here :). Still, at least we now know what the enemy is. Plugging in the explicit numerical values (ignoring infinitesimals)

$\varpi = 1/899 \approx 0.00111$

$\delta = 71/154628 \approx 0.000460$

which are our current optimal values we have

$\sigma = 4569/38657 \approx 0.118193$

$t_1 = 11243/154628 \approx 0.072710$

$t_2=t_3=t_4 = 47795/154628 \approx 0.309097$ .

The Type I/II analysis lets one win when any partial sum lies between $1/2-\sigma = 29519/77314 \approx 0.381807$ and $1/2+\sigma = 47795/77314 \approx 0.618193$ , which at this endpoint case are also the values of $t_1+t_2=t_1+t_3=t_1+t_4$ and $t_2+t_3=t_2+t_4=t_1+t_4$ respectively. On the number theory side, this case corresponds to the component of $\Lambda$ that takes the form

$\psi_1 \ast \psi_2 \ast \psi_3 \ast \psi_4$

where $\psi_i$ is smooth and at scale $x^{t_i}$ for $i=1,2,3,4$ . I was hoping that maybe the smoothness of the first factor $\psi_1$ (called $\alpha$ in the Type III analysis) could be exploitable, but then I realised that one could make the above counterexample more complicated by splitting the $t_1$ term up arbitrarily into many small pieces and so one does not necessarily get to assume $\alpha$ is smooth in the critical case.

Still, at least we have some explicit numerical values to work with when we try to improve either the Type I/II or Type III analysis: specifically, one needs to get some power gain in Theorem 16 with $M \approx x^{0.381807}$ and $N \approx x^{0.618193}$ , or Theorem 17 with $M \approx x^{0.072710}$ and $N_1=N_2=N_3 \approx x^{0.309097}$ .

11 June, 2013 at 4:28 am

meditationatae

In the definition of singleton congruence class system, which goes with Definition 11, I think the sentence should begin with: “If $|C(p)|=1$ for all primes $p \in I$ , […]” . David Bernier

[Corrected, thanks – T.]

11 June, 2013 at 4:32 am

Dustin G. Mixon

Sometimes you write (22) when I think you mean (2).

[Corrected, thanks – T.]

11 June, 2013 at 11:45 am

Eytan Paldi

In fact, it is possible (for each given n) to replace (2) by finding explicitly the EXACT necessary and sufficient conditions on $\varpi$ and
$\delta$ such that lemma 5 holds. (It may happen, however, that for very small values of n, the admissible set for $(\varpi , \delta)$ defined by the necessary and sufficient conditions is empty, but as we already know for sufficiently large n it is nonempty.) A systematic way of doing this is as follows:

1. To find the COMPLEMENT of the above admissible set, containing exactly the pairs $\varpi , \delta$ for which the conclusion of lemma 5 does not hold (i.e. there is a non-negative non-decreasing sequence
$t_1,...,t_n$ with sum 1, which does NOT belong to any type.)

Note that for type (0 ) there are n conditions, negating the lemma condition for each $t_i$ , for type (I / II) there are $n(n-1)/2$ conditions (negating the lemma conditions for each partition), along with the existence of some $/sigma$ satisfying its lemma conditions, and for type (III) there are $n(n-1)(n-2)/6$ conditions (one for each triple
$(t_i, t_j, t_k)$ such that $t_i < t_j < t_k < 1/2$ and negating the last inequality in lemma 5 for this triple.)

2. Use any method of quantifier elimination (see e.g. chapter 14 in "algorithms in real algebraic geometry" by S. Basu, R. Pollack and M-F Roy, Springer -Verlag, 2003.) to get the desired necessary and sufficient conditions for the complement of the above admissible set for the pairs $(\varpi , \delta)$ .

Remark: In general such (symbolic) quantifier elimination are used for general systems of polynomial inequalities, but in our case of systems of linear inequalities I think that the computational complexity should be manageable – the resulting admissible set should be a finite union of certain polygons. As I know, there should be several software implementations of quantifier elimination algorithms.

11 June, 2013 at 12:40 pm

Gergely Harcos

Dear Terry, perhaps it would be useful to emphasize in the post that (2) is optimal for Lemma 6, so that others don’t try to improve it. On the other front, I try to catch up with Zhang’s paper.

Some other small suggestions:

1. In the proof of Lemma 5 it would be useful to emphasize (for the sake of the reader) that a powerful summand is not only able to convert a small sum to a large sum, but it can do this for a small sum with powerful summands only (as powerless summands can be omitted).

2. In the sentence “We then apply Lemma 5” and the next one, the numbers 5 and 6 should be flipped.

[Corrections and suggestions implemented, thanks – T.]

11 June, 2013 at 2:31 pm

Eytan Paldi

Is it possible that for larger n, (2) is not optimal for lemma 5?

11 June, 2013 at 4:26 pm

Dustin G. Mixon

No – Use the same counterexample, except take the $n-4$ other $t_i$ ‘s to be zero.

11 June, 2013 at 6:08 pm

Eytan Paldi

In fact, your suggestion is the same counter example with $n = 4$ since the other $n - 4$ parameters can be ignored!
But your example can be modified to have the remaining parameters equal to a sufficiently small number to still get a non-degenerate counter example!

12 June, 2013 at 1:03 pm

Estimation of the Type I and Type II sums | What's new

[…] seminar of Zhang’s paper for the polymath8 project. (There are two other continuations; this previous post, which deals with the combinatorial aspects of the second part of Zhang’s paper, and a post […]

12 June, 2013 at 10:43 pm

Terence Tao

I have an idea which may be able to largely eliminate the role of $\delta$ in Zhang’s analysis. The main reason that we can’t take $\delta$ to be too large is because of the following inefficiency: when we want to factor a $x^\delta$ -smooth number $d \sim D$ into two factors $d=qr$ with $q,r$ chose to some preselected $Q,R$ with $QR \sim D$ , we can’t quite hit our targets $Q,R$ with perfect accuracy, and must instead settle for loose bounds like

$x^{-\delta} R \leq r \leq R$ . (*)

This gap of $x^\delta$ between where we would like our parameters to be, and where they eventually end up, leads to most of the dependencies on the $\delta$ parameter in Zhang’s theorem $MPZ[\varpi,\delta]$ . (There are a couple places where $\delta$ needs to be small relative to other quantities, but these conditions on $\delta$ are very mild compared to the main effect of $\delta$ on the conditions for $MPZ[\varpi,\delta]$ .)

Now, if all we know about $d$ is that it is $x^\delta$ -smooth, then we can’t do much better than (*), at least when $D, Q, R$ are close to integer powers of $x^\delta$ , since $n$ could simply be the product of primes that are close to $x^\delta$ . (One could eke out an incredibly tiny improvement to (*) in the case that $D,Q,R$ are not integer powers of $\delta$ , but this is not the direction I am pursuing here.)

On the other hand, if we return to the sieve theory side of things, most of the moduli n for which we actually want an Elliott-Halberstam estimate are not of the form “product of primes that are close to $x^\delta$ ” – most of them also contain a bunch of prime factors that are significantly less than $x^\delta$ . I have to do the sieve calculations carefully, but there is a chance that one could show that “most” of the moduli d in the sieve have enough prime factors that their factors are spread much more densely between 1 and d (as measured in log-scale) than (*) suggests, and that one should in fact be able to find a factor r that is basically within $x^{o(1)}$ of $R$ rather than within $x^\delta$ . If so, this should largely eliminate the influence that $\delta$ has on the Type I and Type II sums (so long as it is reasonably small, say 1/100 or so, as opposed to the current level of 1/2000 or so). (Amusingly, one may need to use some inverse Littlewood-Offord theory to make this intuition precise, which is something that I happen to be quite familiar with.)

This is all contingent though on checking that “most” moduli in the sieve have this desired property (in the sense that the contribution of the exceptional moduli is small). Will think about this…

12 June, 2013 at 11:22 pm

v08ltu

My impression would be that the $d$ which are “bad” in this sense are a positive proportion in the contribution, but it would be like the Dickman function at $4/\omega$ or something, so quite quite small. But this is just a guess.

12 June, 2013 at 11:49 pm

v08ltu

If I parse Ford’s paper correctly: http://annals.math.princeton.edu/wp-content/uploads/annals-v168-n2-p01.pdf

His theorem p371 states that the proportion of numbers with a factor in [y,z] looks like $u^\delta(log 2/u)^{-3/2}$ where $z=y^{1+u}$ and $\delta=1-{1+\log\log 2\over \log 2}\approx 0.086071$ . For $u=1/1000$ say, this is 2.7%, so most numbers don’t have a factor in such a range.

13 June, 2013 at 12:50 am

bengreen

Terry, I think you’re quite likely to be right about this. The calculation does need to be done *inside* the sieve, though, because there are “many” $d$ in $[X,2X]$ with all prime factors pretty near $X^{\delta}$ , where “many” means at least $X/(\log X)^{1/\delta}$ or so. And the sieve weights may more than cancel that denominator of a power of $\log$ . But certainly the prime factors of a typical $d$ , even a typical smooth one, are going to be quite spread out and hence arrangeable to be more-or-less whatever size one wants. One could even get interdisciplinary about this and cite this play:

https://www.msri.org/general_events/19160

or, more seriously

http://www.dms.umontreal.ca/~andrew/PDF/Anatomy.pdf‎

In fact it seems to me that we don’t really care about being $X^{\delta}$ -smooth at all. The key property is that if $S = \{ \frac{\log p}{\log X} : p | d\}$ then the set of subset sums of $S$ is $\delta$ -dense: this is what lets you arrange factorisations of any desired size (within $\delta$ ). We could even redefine $\delta$ to be this parameter, couldn’t we? It’s obviously less than or equal to the old $\delta$ . And, now you are talking about ruling out sets whose subset sums are strangely distributed, I see why inverse Littlewood-Offord comes into the game. Nice observation!

I suppose one really (for the moment) only cares about being able to arrange factorisations nicely in the vicinity of the important threshold at the Type I/III border; this may give some extra saving.

13 June, 2013 at 3:43 am

v08ltu

“But certainly the prime factors of a typical d, even a typical smooth one, are going to be quite spread out and hence arrangeable to be more-or-less whatever size one wants.”

For a typical $d$ isn’t the $r$ th prime factor typically like $e^{e^r}$ , which doesn’t allow one that much wiggle room, if you want to force divisors where you want? You may typically have two divisors within a factor or two of each other, but that doesn’t mean that you can force a divisor to be in (too short) an interval wherever you want. If I read the above quoted theorem of Ford (following Tenenbaum) correctly, the percentage of numbers with a factor in a specific power-range like $[y,y^{1.001}]$ is quite small (2.7%). Of course we have the smoothness hypothesis, but I don’t know whether this will be a panacea (it will allow us to reduce $\delta$ , but not to an infinitesimal, or irrevelancy). Just my opinion.

13 June, 2013 at 4:02 am

bengreen

I take your point. But it should certainly allow one to reduce $\delta$ (or, rather, perhaps we should change the definition of $\delta$ ).

13 June, 2013 at 9:40 am

Terence Tao

Thanks for all the feedback! The issue is a bit more subtle than I had expected: even after restricting to $x^\delta$ -smooth numbers, the proportion of numbers which fail to be, say, $x^{\delta/2}$ -divisor-dense (i.e. their set of divisors manages to miss an interval of the form $[x^{-\delta/2} R, R]$ for some medium-sized $R$ ) does have a very small but positive density. But because the Selberg sieve $\nu(n) = (\sum_{d|n} \mu(d) a_d)^2$ has a lot of cancellation in it (as evidenced by the Mobius function factor), “very small density” does not automatically translate to “negligible for the purposes of sieve theory” – a naive attempt to estimate the error by taking absolute values everywhere sets one back a few factors of a logarithm (if one uses the GPY sieve, one in fact loses the horrific amount of $\log^{k_0} x$ , but I am hoping with the elementary Selberg sieve one only loses something like $\log x$ or $\log^2 x$ , which is too large to be absorbed by a smallness of density but it makes it more plausible that one could exploit the cancellation of the Mobius function to control things).

Of course, one does not necessarily need to compare a new sieve with an old sieve to show that the new sieve is effective – one might be able to compute all the relevant sieve asymptotics for a GPY sieve restricted to “dense-divisor” numbers directly. One thing that works in our favor here is that the property of having a dense set of divisors is sort of multiplicative: if q and r have dense sets of divisors, then qr does as well. But one may have to select the precise definition of having “dense divisors” carefully; as I said before, there is a lot of cancellation going on in the sieve calculations and one cannot afford to disrupt that.

It seems that if one is willing to just halve the influence of $\delta$ rather than eliminate it entirely (roughly speaking, this would replace the condition $207 \varpi + 43\delta < 1/4$ by $207 \varpi + 43 \delta/2 < 1/4$ , at least in principle) then one can get a fair amount of control on the exceptional $x^\delta$ -smooth numbers $q$ that avoid having any divisor in $[x^{-\delta/2} R, R]$ , basically by a modification of the combinatorial arguments that happen to be in the main post here. Indeed, call a factor of $q$ "small" if it is less than $x^{-\delta/2} R$ and "large" if it is larger than $R$ . Call a prime dividing $q$ "powerless" if it cannot turn a small factor into a large factor and "powerful" otherwise; in particular, powerful primes lie between $x^{\delta/2}$ and $x^\delta$ . Now look at the minimal large factor of $q$ , it has to consist entirely of powerful primes as we can strike out all the powerless primes without making the factor small. Furthermore, if one orders the powerful primes as $p_1 < \ldots < p_k$ , then the minimal large factor has to consist of an initial segment $p_1 \ldots p_i$ since otherwise one could swap one powerful prime by a smaller one which reduces the product by at most $x^{\delta/2}$ and thus cannot make the product small. Thus every product of i or more powerful primes is large, and every product of i-1 or less primes is small (otherwise the above arguments would also show that $p_1 \ldots p_{i-1}$ is large, contradicting minimality of $p_1,\ldots,p_i$ ). Thus (roughly speaking) all the powerful primes lie between $R^{1/i}$ and $(x^{-\delta} R)^{1/(i-1)}$ , which in practice is quite a narrow band. Also all the powerless primes when multiplied together cannot exceed $x^{\delta/2}$ (since otherwise no prime less than $x^\delta$ could be powerful enough to bridge the gap $[x^{-\delta/2} R, R]$ once the effect of the powerless primes are factored in). This is quite a special configuration (the density of such numbers inside the $x^\delta$ -smooth numbers appears to be something like $\exp(-1/\delta)$ from a back-of-the-envelope calculation). Of course as I said before this doesn't immediately allow one to declare victory due to the cancellation in the sieve but it is a promising sign.

13 June, 2013 at 4:00 pm

v08ltu

I guess my concern was: the $\{{\log p\over\log X}\}$ for an “average” d are like $\{{e-1\over e^k}\}_{k=1}^\infty$ (this is a very vague statement, the geometric series should be $1/e$ to some extent, and I made it add up to 1). So that is more sparse than powers of 2, and you cover little with subset sums. But if you are pre-assuming that numbers have no large prime factors, say more than $X^{1/1000}$ , then I don’t know, but would guess that the above set is looking more like $\frac{e^{k/1000}-1}{e^{k/1000}}$ typically, which looks much denser in its subset sums.

13 June, 2013 at 7:48 pm

v08ltu

Actually it should be $e^{1/1000}-1$ in the numerator, which is about the ${1\over 1000}$ which is an upper bound of $\{{\log p\over\log X}\}$ with these smooths.

13 June, 2013 at 8:58 pm

meditationatae

For some reason, the link to Anatomy.pdf by Granville, when clicked, yields “gibberish”. But searching/googling for: The Anatomy of Integers and Permutations Andrew Granville should work …

13 June, 2013 at 9:46 pm

andrescaicedo

There is a small typo (some extra spaces), just remove %E2%80%8E

14 June, 2013 at 8:47 am

Estimation of the Type III sums | What's new

18 June, 2013 at 8:46 am

Terence Tao

A quick note: Janos Pintz has kindly sent me some handwritten notes (with permission to share them with this project) in which he has (somewhat independently of our own discussion) worked out a way to implement the idea mentioned in comments above of relaxing the condition that the modulus $d$ be $x^\delta$ -smooth. Basically, the idea is to restrict instead to the wider class of squarefree moduli $d$ which are $x^{C\delta}$ -smooth for some large C and also obey the property

$\prod_{p|d: p < x^\delta} p \geq x^{(C-1)\delta}$

since the greedy algorithm then shows that such a $d$ will contain a factor $r$ between $x^{-\delta} R$ and $R$ for any $1 \leq R \leq d$ . His notes show that the truncation error in the the elementary Selberg sieve (discussed back in https://terrytao.wordpress.com/2013/06/08/the-elementary-selberg-sieve-and-bounded-prime-gaps/ , and is a little different from the analytic Selberg sieve which we are currently using) caused by restricting to such numbers is negligible; I’ll try to write up a blog post on this shortly.

In practice the effect of this will come close to the ideal of being able to ignore delta completely (e.g. the condition $87 \varpi + 17\delta < 1/4$ morally becomes $87 \varpi < 1/4$ ).

With this and the improvement on Type III sums that Michel has just announced at https://terrytao.wordpress.com/2013/06/14/estimation-of-the-type-iii-sums/#comment-235003 , it looks like we will have some more progress on these bounds in a few days…

18 June, 2013 at 10:30 am

Anonymous

i don’t see any announcement in the last link…

[Link corrected, thanks – T.]

18 June, 2013 at 6:19 pm

A truncated elementary Selberg sieve of Pintz | What's new

[…] a more general systetm of congruence classes obeying a certain controlled multiplicity axiom; see this post. Secondly, and more importantly for this post, the requirement that the modulus lies in can be […]

21 June, 2013 at 10:52 am

Pace Nielsen

In (18), I think that the $n$ on the RHS of the formula should be an $x$ (as $n$ is the summation variable).

[Corrected, thanks – T.]

23 June, 2013 at 9:14 pm

The distribution of primes in densely divisible moduli | What's new

[…] improves upon previous constraints of (see this blog comment) and (see Theorem 13 of this previous post), albeit for instead of . Inserting Theorem 4 into the Pintz sieve from this previous post gives […]

25 June, 2013 at 10:53 am

Gergely Harcos

Three comments and some typos:

1. Before (27) you say there are $O(\log^{2jA_0} x)$ summands. I think the number is a bit larger, namely $O(\log^{2j(A_0+1)} x)$ . This is because there are about $\log^{A_0} x$ elements of $\mathcal{D}$ in every dyadic range, hence about $\log^{A_0+1} x$ elements in $[1,x]$ .

2. In the proof of (iv) in Lemma 9, there is no need to introduce $C>0$ and proceed by Cauchy-Schwarz (in fact I had difficulty following the original argument). By (13) and the first display in this part of the proof, we have directly

$\sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\alpha \ast \beta; a\ (q))| \ll (N \log^{O(1)} x)\sup_{c \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\beta; c\ (q))|$ ,

so that, using the assumption on $\beta$ ,

$\sum_{q<L}\sup_{a \in ({\bf Z}/q{\bf Z})^\times} |\Delta(\alpha \ast \beta; a\ (q))| \ll NM \log^{-A+O(1)} x$ .

3. At the end of the proof of Lemma 12, there is no need to reduce to $b\ (r)$ primitive, since (12) does not assume primitivity.

4a. In the proof of Lemma 9, third line, $\log^{O(1)}$ should be $\log^{O(1)}x$ .

4b. In Section 3, $\mu_<$ should be $\mu_\leq$ .

4c. In Section 3, $\varphi: {\bf R} \rightarrow {\bf R}$ should be $\psi: {\bf R} \rightarrow {\bf R}$ , and $\varphi^{(j)}(t)$ should be $\psi^{(j)}(t)$ .

4d. $\psi(x/N)$ should be $\psi(n/N)$ .

4e. In (21) and in the proof of Proposition 14, $\Delta(\Lambda 1_{[x,2x]}; a)$ should be $\Delta(\Lambda 1_{[x,2x]}; a\ (q))$ .

4f. In the proof of Theorem 15, Lemma 7 should be Lemma 9, and the link to it should be updated.

4g. In Theorem 17, "any be a singleton" should be "for any singleton".

[Corrected, thanks! – T.]

30 June, 2013 at 12:39 pm

Bounded gaps between primes (Polymath8) – a progress report | What's new

[…] convolution. The precise identity is a little complicated (although not difficult to prove); see this post for details. Using this identity, we can indeed reduce (2) to slightly more complicated versions of […]

1 July, 2013 at 10:01 pm

Avi Levy

In the sentence before (26), there is a citation to an unidentified “Proposition”

[Corrected, thanks – T.]

7 July, 2013 at 11:17 pm

The distribution of primes in doubly densely divisible moduli | What's new

[…] 4, 5, 6 will be given below the fold, while the proof of Lemma 7 follows from the arguments in this previous post. We remark that in our current arguments, the double dense divisibility is only fully used in the […]

27 July, 2013 at 6:55 pm

An improved Type I estimate | What's new

[…] Again, these conditions are implied by (8). The claim then follows from the Heath-Brown identity and dyadic decomposition as in this previous post. […]

17 October, 2013 at 11:46 am

Stijn Hanson

In Lemma 8 it proves equation (10) using a simple bound and then Proposition 5 from “The elementary Selberg sieve and bounded prime gaps” but that’s a proof of MPZ from EH and doesn’t appear to contain any sums of the required form (requiring either squarefree-ness or some coprimality condition on the summands). Is there some numbering/linking mix-up here or am I just not reading it properly?

17 October, 2013 at 12:03 pm

Terence Tao

Hmm, that is a numbering issue; one can use for instance Lemma 8 from the previous post. (These estimates can also be found in standard multiplicative number theory texts, e.g. Corollary 2.15 of Montgomery-Vaughan. A good rule of thumb regarding these sorts of estimates is that the number of divisors $\tau(n)$ of a large number $n$ is typically of size $\log^{O(1)} n$ ; this is closely related to the Erdos-Kac theorem, which is a precise version of the assertion that the number of prime factors of a number $n$ is typically of size $\log\log n$ .)

9 February, 2014 at 3:03 pm

Stijn Hanson

Sorry, could you expand a little on how the “crude bounds” give the last displayed equation of Proposition 14?

9 February, 2014 at 3:41 pm

Terence Tao

One can bound $|\Delta(\Lambda 1_{[x,2x]}, a\ (q))|$ by $O( \tau(q)^{O(1)} \frac{x}{q} \log^{O(1)} x )$ and $|C(q)|$ by $\tau(q)^{O(1)}$ .

10 February, 2014 at 3:56 pm

Stijn Hanson

ok, I roughly see how those bounds help (presumably by using $\tau(q) \ll o(n^{\epsilon})$ for all $\epsilon > 0$ but how exactly do you get $|C(q)| \ll \tau(q)^{O(1)}$ ? I’m looking at the bounds in the definition and the closest asymptotic bound I can easily see is $|C(q)| \leq \phi(q)$ . Sorry, I’m probably being really thick.

10 February, 2014 at 7:28 pm

Terence Tao

Use hypotheses (ii) and (iii) of Definition 11, rather than hypothesis (i). (iii) gives the case when q is prime, and (ii) then gives the general squarefree case as a consequence.

More generally, bounds on multiplicative functions should usually be proven by first considering the prime case (or the prime power case, if one is not restricted to squarefree numbers).

24 September, 2014 at 2:29 pm

Derived multiplicative functions | What's new

[…] to , where and are arbitrary parameters and denotes the -fold convolution of , and discussed in this previous blog post; this is the top order component […]

2 December, 2015 at 1:51 pm

A conjectural local Fourier-uniformity of the Liouville function | What's new

[…] (e.g. Vaughan’s identity or Heath-Brown’s identity), as discussed for instance in this previous post (which is focused more on the von Mangoldt function, but analogous identities exist for the […]

6 July, 2017 at 12:07 am

Correlations of the von Mangoldt and higher divisor functions I. Long shift ranges | What's new

[…] step, which is again standard, is the use of the Heath-Brown identity (as discussed for instance in this previous blog post) to split up into a number of components that have a Dirichlet convolution structure. Because the […]

19 December, 2021 at 2:11 pm

Prashanth

Prof. Tao,
I know this is a very old post, but I stumbled on to this when I was researching all the ways to interpret np-complete problems using number theoretical concepts. Can we somehow relate NP-complete version of the subset sum problem with bounded gaps between primes and generate an equivalence statement for p vs np ? Did you make any attempts in this regards or are you aware of similar attempts? I’m not asking whether we can settle p vs np this way, but can we relate these two fields even if the relation on the number theory side may not be something provable.

Thanks,
Prashanth

	Dan Asimov on Inequalities, convergence, and…
	Dan Asimov on Inequalities, convergence, and…
	Anonymous on AI to Assist Mathematical Reas…
	Terence Tao on AI to Assist Mathematical Reas…
	Mathur Maynard Amadi on Inequalities, convergence, and…
	Alex Kontorovich on Inequalities, convergence, and…
	Gabe Khan on Inequalities, convergence, and…
	"不等式、收敛与连续性作为“特… on Inequalities, convergence, and…
	Some interesting thi… on PCAST Working Group on Generat…
	jack morava on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…
	Mark Lewko on Inequalities, convergence, and…
	Wednesday assorted l… on Inequalities, convergence, and…

A combinatorial subset sum problem associated with bounded prime gaps

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

64 comments

Leave a Reply Cancel reply

For commenters

A combinatorial subset sum problem associated with bounded prime gaps

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

64 comments

Leave a Reply Cancel reply

For commenters