Further analysis of the truncated GPY sieve

11 June, 2013 in math.NT, polymath | Tags: polymath8, sieve theory, smooth numbers

This post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, we are rolling the thread over to the current post. We also take the opportunity to correct some errors in the treatment of the truncated GPY sieve from this previous post.

As usual, we let ${x}$ be a large asymptotic parameter, and ${w}$ a sufficiently slowly growing function of ${x}$ . Let ${0 < \varpi < 1/4}$ and ${0 < \delta < 1/4+\varpi}$ be such that ${MPZ[\varpi,\delta]}$ holds (see this previous post for a definition of this assertion). We let ${{\mathcal H}}$ be a fixed admissible ${k_0}$ -tuple, let ${I := [w,x^\delta]}$ , let ${{\mathcal S}_I}$ be the square-free numbers with prime divisors in ${I}$ , and consider the truncated GPY sieve

$\displaystyle \nu(n) := \lambda(n)^2$

where

$\displaystyle \lambda(n) := \sum_{d \in {\mathcal S}_I: d|P(n)} \mu(d) g(\frac{\log d}{\log R})$

where ${R := x^{1/4+\varpi}}$ , ${P}$ is the polynomial

$\displaystyle P(n) := \prod_{h \in {\mathcal H}} (n+h),$

and ${g: {\bf R} \rightarrow {\bf R}}$ is a fixed smooth function supported on ${[-1,1]}$ . As discussed in the previous post, we are interested in obtaining an upper bound of the form

$\displaystyle \sum_{x \leq n \leq 2x} \nu(n) \leq (\alpha+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0} R}$

as well as a lower bound of the form

$\displaystyle \sum_{x \leq n \leq 2x} \nu(n) \theta(n+h) \geq (\beta+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0-1} R}$

for all ${h \in {\mathcal H}}$ (where ${\theta(n) = \log n}$ when ${n}$ is prime and ${\theta(n)=0}$ otherwise), since this will give the conjecture ${DHL[k_0,2]}$ (i.e. infinitely many prime gaps of size at most ${k_0}$ ) whenever

$\displaystyle 1+4\varpi > \frac{4\alpha}{k_0 \beta}. \ \ \ \ \ (1)$

It turns out we in fact have precise asymptotics

$\displaystyle \sum_{x \leq n \leq 2x} \nu(n) = (\alpha+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0} R} \ \ \ \ \ (2)$

and

$\displaystyle \sum_{x \leq n \leq 2x} \nu(n) \theta(n+h) = (\beta+o(1)) (\frac{W}{\phi(W)})^{k_0} \frac{x}{W \log^{k_0} R} \ \ \ \ \ (3)$

although the exact formulae for ${\alpha,\beta}$ are a little complicated. (The fact that ${\alpha,\beta}$ could be computed exactly was already anticipated in Zhang’s paper; see the remark on page 24.) We proceed as in the previous post. Indeed, from the arguments in that post, (2) is equivalent to

$\displaystyle \sum_{d_1,d_2 \in {\mathcal S}_I} \mu(d_1) g(\frac{\log d_1}{\log R}) \mu(d_2) g(\frac{\log d_2}{\log R}) \frac{k_0^{\Omega([d_1,d_2])}}{[d_1,d_2]} \ \ \ \ \ (4)$

$\displaystyle = (\alpha + o(1)) (\frac{W}{\phi(W)})^{k_0} \log^{-k_0} R$

and (3) is similarly equivalent to

$\displaystyle \sum_{d_1,d_2 \in {\mathcal S}_I} \mu(d_1) g(\frac{\log d_1}{\log R}) \mu(d_2) g(\frac{\log d_2}{\log R}) \frac{(k_0-1)^{\Omega([d_1,d_2])}}{[d_1,d_2]} \ \ \ \ \ (5)$

$\displaystyle = (\beta + o(1)) (\frac{W}{\phi(W)})^{k_0-1} \log^{-k_0+1} R.$

Here ${\Omega(d)}$ is the number of prime factors of ${d}$ .

We will work for now with (4), as the treatment of (5) is almost identical.

We would now like to replace the truncated interval ${I = [w,x^\delta]}$ with the untruncated interval ${I \cup J = [w,\infty)}$ , where ${J = (x^\delta,\infty)}$ . Unfortunately this replacement was not quite done correctly in the previous post, and this will now be corrected here. We first observe that if ${F(d_1,d_2)}$ is any finitely supported function, then by Möbius inversion we have

$\displaystyle \sum_{d_1,d_2 \in {\mathcal S}_I} F(d_1,d_2) = \sum_{d_1,d_2 \in {\mathcal S}_{I \cup J}} F(d_1,d_2) \sum_{a \in {\mathcal S}_J} \mu(a) 1_{a|[d_1,d_2]}.$

Note that ${a|[d_1,d_2]}$ if and only if we have a factorisation ${d_1 = a_1 d'_1}$ , ${d_2 = a_2 d'_2}$ with ${[a_1,a_2] = a}$ and ${d'_1 d'_2}$ coprime to ${a_1 a_2}$ , and that this factorisation is unique. From this, we see that we may rearrange the previous expression as

$\displaystyle \sum_{a_1,a_2 \in {\mathcal S}_J} \mu( [a_1,a_2] ) \sum_{d'_1,d'_2 \in {\mathcal S}_{I \cup J}: (d'_1 d'_2, a_1 a_2) = 1} F( a_1 d'_1, a_2 d'_2 ).$

Applying this to (4), and relabeling ${d'_1,d'_2}$ as ${d_1,d_2}$ , we conclude that the left-hand side of (4) is equal to

$\displaystyle \sum_{a_1,a_2 \in {\mathcal S}_J} \mu( [a_1,a_2] ) \sum_{d_1,d_2 \in {\mathcal S}_{I \cup J}: (d_1d_2,a_1a_2)=1}$

$\displaystyle \mu(a_1d_1) g(\frac{\log a_1d_1}{\log R}) \mu(a_2d_2) g(\frac{\log a_2d_2}{\log R}) \frac{k_0^{\Omega([a_1 d_1,a_2 d_2])}}{[a_1 d_1,a_2 d_2]}$

which may be rearranged as

$\displaystyle \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{\mu( (a_1,a_2) ) k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \sum_{d_1,d_2\in {\mathcal S}_{I \cup J}: (d_1d_2,a_1a_2)=1} \ \ \ \ \ (6)$

$\displaystyle \mu(d_1) g(\frac{\log a_1d_1}{\log R}) \mu(d_2) g(\frac{\log a_1 d_2}{\log R}) \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]}.$

This is almost the same formula that we had in the previous post, except that the Möbius function ${\mu((a_1,a_2))}$ of the greatest common divisor ${(a_1,a_2)}$ of ${a_1,a_2}$ was missing, and also the coprimality condition ${(d_1d_2,a_1a_2)=1}$ was not handled properly in the previous post.

We may now eliminate the condition ${(d_1d_2,a_1a_2)=1}$ as follows. Suppose that there is a prime ${p_* \in J}$ that divides both ${d_1d_2}$ and ${a_1a_2}$ . The expression

$\displaystyle \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \sum_{d_1,d_2 \in {\mathcal S}_{I \cup J}: p_* | (d_1d_2,a_1a_2)}$

$\displaystyle |g(\frac{\log a_1d_1}{\log R})| |g(\frac{\log a_1 d_2}{\log R})| \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]}$

can then be bounded by

$\displaystyle \ll \sum_{a_1,a_2} \sum_{d_1,d_2: p_* | (d_1d_2,a_1a_2)} \frac{k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]} (a_1 a_2 d_1 d_2)^{-1/\log R}$

which may be factorised as

$\displaystyle \ll \frac{1}{p_*^2} \prod_p (1 + \frac{O(1)}{p^{1+1/\log R}})$

which by Mertens’ theorem (or the simple pole of ${\zeta(s)}$ at ${s=1}$ ) is

$\displaystyle \ll \frac{\log^{O(1)} R}{p_*^2}.$

Summing over all ${p_* > x^\varpi}$ gives a negligible contribution to (6) for the purposes of (4). Thus we may effectively replace (6) by

$\displaystyle \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{\mu( (a_1,a_2) ) k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} \sum_{d_1,d_2\in {\mathcal S}_{I \cup J}}$

$\displaystyle \mu(d_1) g(\frac{\log a_1d_1}{\log R}) \mu(d_2) g(\frac{\log a_1 d_2}{\log R}) \frac{k_0^{\Omega([d_1,d_2])}}{[d_1, d_2]}.$

The inner summation can be treated using Proposition 10 of the previous post. We can then reduce (4) to

$\displaystyle \sum_{a_1,a_2 \in {\mathcal S}_J} \frac{\mu( (a_1,a_2) ) k_0^{\Omega([a_1,a_2])}}{[a_1,a_2]} G_{k_0}( \frac{\log a_1}{\log R}, \frac{\log a_2}{\log R} ) = \alpha+o(1) \ \ \ \ \ (7)$

where ${G_{k_0}}$ is the function

$\displaystyle G_{k_0}(t_1,t_2) := \int_0^1 g^{(k_0)}(t+t_1) g^{(k_0)}(t+t_2) \frac{t^{k_0-1}}{(k_0-1)!}\ dt.$

Note that ${G}$ vanishes if ${t_1 \geq 1}$ or ${t_2 \geq 1}$ . In practice, we will work with functions ${g}$ in which ${g^{(k_0)}}$ has a definite sign (in our normalisations, ${g^{(k_0)}}$ will be non-positive), making ${G_{k_0}}$ non-negative.

We rewrite the left-hand side of (7) as

$\displaystyle \sum_{a \in {\mathcal S}_J} \frac{k_0^{\Omega(a)}}{a} \sum_{a_1,a_2: [a_1,a_2] = a} \mu((a_1,a_2)) G_{k_0}( \frac{\log a_1}{\log R}, \frac{\log a_2}{\log R} ).$

We may factor ${a = p_1 \ldots p_n}$ for some ${x^\delta < p_1 < \ldots < p_n}$ with ${p_1 \ldots p_n \leq R}$ ; in particular, ${n < \frac{1 + 4\varpi}{4\delta}}$ . The previous expression now becomes

$\displaystyle \sum_{0 \leq n < \frac{1+4\varpi}{4\delta}} k_0^n \sum_{x^\delta < p_1 < \ldots < p_n} \frac{1}{p_1 \ldots p_n}$

$\displaystyle \sum_{\{1,\ldots,n\} = S \cup T} (-1)^{|S \cap T|} G_{k_0}( \sum_{i \in S} \frac{\log p_i}{\log R}, \sum_{j \in T} \frac{\log p_j}{\log R} ).$

Using Mertens’ theorem, we thus conclude an exact formula for ${\alpha}$ , and similarly for ${\beta}$ :

Proposition 1 (Exact formula) We have

$\displaystyle \alpha = \sum_{0 \leq n < \frac{1+4\varpi}{4\delta}} k_0^n \int_{\frac{4\delta}{1+4\varpi} < t_1 < \ldots < t_n} G_{k_0,n}(t_1,\ldots,t_n) \frac{dt_1 \ldots dt_n}{t_1 \ldots t_n}$

where

$\displaystyle G_{k_0,n}(t_1,\ldots,t_n) := \sum_{\{1,\ldots,n\} = S \cup T} (-1)^{|S \cap T|} G_{k_0}( \sum_{i \in S} t_i, \sum_{j \in T} t_j ).$

Similarly we have

$\displaystyle \beta = \sum_{0 \leq n < \frac{1+4\varpi}{4\delta}} (k_0-1)^n \int_{\frac{4\delta}{1+4\varpi} < t_1 < \ldots < t_n} G_{k_0-1,n}(t_1,\ldots,t_n) \frac{dt_1 \ldots dt_n}{t_1 \ldots t_n}$

where ${G_{k_0-1}}$ and ${G_{k_0-1,n}}$ are defined similarly to ${G_{k_0}}$ and ${G_{k_0,n}}$ by replacing all occurrences of ${k_0}$ with ${k_0-1}$ .

These formulae are unwieldy. However if we make some monotonicity hypotheses, namely that ${g^{(k_0-1)}}$ is positive, ${g^{(k_0)}}$ is negative, and ${g^{(k_0+1)}}$ is positive on ${[0,1)}$ , then we can get some good estimates on the ${G_{k_0}, G_{k_0-1}}$ (which are now non-negative functions) and hence on ${\alpha,\beta}$ . Namely, if ${g^{(k_0)}}$ is negative but increasing then we have

$\displaystyle -g^{(k_0)}(t+t_1) \leq -g^{(k_0)}(\frac{t}{1-t_1})$

for ${0 \leq t_1 < 1}$ and ${t \in [0,1]}$ , which implies that

$\displaystyle G_{k_0}(t_1,t_1) \leq (1-t_1)_+^{k_0} G_{k_0}(0,0)$

for any ${t_1 \geq 0}$ . A similar argument in fact gives

$\displaystyle G_{k_0}(t_1+t_2,t_1+t_2) \leq (1-t_1)_+^{k_0} G_{k_0}(t_2,t_2)$

for any ${t_1,t_2 \geq 0}$ . Iterating this we conclude that

$\displaystyle G_{k_0}(\sum_{i \in S} t_i, \sum_{i \in S} t_i) \leq (\prod_{i \in S} (1-t_i)_+^{k_0}) G_{k_0}(0,0)$

and similarly

$\displaystyle G_{k_0}(\sum_{i \in T} t_i, \sum_{i \in T} t_i) \leq (\prod_{i \in T} (1-t_i)_+^{k_0}) G_{k_0}(0,0).$

From Cauchy-Schwarz we thus have

$\displaystyle G_{k_0}( \sum_{i \in S} t_i, \sum_{i \in T} t_i ) \leq (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) G_{k_0}(0,0).$

Observe from the binomial formula that of the ${3^n}$ pairs ${(S,T)}$ with ${S \cup T = \{1,\ldots,n\}}$ , ${\frac{3^n+1}{2}}$ of them have ${|S \cap T|}$ even, and ${\frac{3^n-1}{2}}$ of them have ${|S \cap T|}$ odd. We thus have

$\displaystyle -\frac{3^n-1}{2} (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) G_{k_0}(0,0) \leq G_{k_0,n}(t_1,\ldots,t_n) \ \ \ \ \ (8)$

$\displaystyle \leq \frac{3^n+1}{2} (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) G_{k_0}(0,0).$

We have thus established the upper bound

$\displaystyle \alpha \leq G_{k_0}(0,0) (1 + \kappa) \ \ \ \ \ (9)$

where

$\displaystyle \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} k_0^n \int_{\frac{4\delta}{1+4\varpi} < t_1 < \ldots < t_n} (\prod_{i=1}^n (1 - t_i)_+^{k_0/2}) \frac{dt_1 \ldots dt_n}{t_1 \ldots t_n}.$

By symmetry we may factorise

$\displaystyle \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} ( \int_{\frac{4\delta}{1+4\varpi} < t \leq 1} (1-t)^{k_0/2}\ \frac{dt}{t})^n.$

The expression ${\kappa}$ is explicitly computable for any given ${\varpi,\delta,k_0}$ . Following the recent preprint of Pintz, one can get a slightly looser, but cleaner, bound by using the upper bound

$\displaystyle 1-t \leq \exp(-t)$

and so

$\displaystyle \kappa \leq \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} (\int_{4\delta/(1+4\varpi)}^\infty \exp( - \frac{k_0}{2} t )\ \frac{dt}{t})^n.$

Note that

$\displaystyle \int_{4\delta/(1+4\varpi)}^\infty \exp( - \frac{k_0}{2} t )\ \frac{dt}{t} = \int_1^\infty \exp( - \frac{2k_0 \delta}{1+4\varpi} t)\ \frac{dt}{t}$

$\displaystyle < \int_1^\infty \exp( - \frac{2k_0 \delta}{1+4\varpi} t)\ dt$

$\displaystyle = \frac{1+4\varpi}{2k_0\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} )$

and hence

$\displaystyle \kappa \leq \tilde \kappa$

where

$\displaystyle \tilde \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{1}{n!} \frac{3^n+1}{2} (\frac{1+4\varpi}{2\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} ))^n.$

In practice we expect the ${n=1}$ term to dominate, thus we have the heuristic approximation

$\displaystyle \kappa \lessapprox \frac{1+4\varpi}{\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} ).$

Now we turn to the estimation of ${\beta}$ . We have an analogue of (8), namely

$\displaystyle -\frac{3^n-1}{2} (\prod_{i=1}^n (1-t_i)^{(k_0-1)/2}) G_{k_0-1}(0,0) \leq G_{k_0-1,n}(t_1,\ldots,t_n)$

$\displaystyle \leq \frac{3^n+1}{2} (\prod_{i=1}^n (1-t_i)^{(k_0-1)/2}) G_{k_0-1}(0,0).$

But we have an improvment in the lower bound in the ${n=1}$ case, because in this case we have

$\displaystyle G_{k_0-1,n}(t) = G_{k_0-1}(t,0) + G_{k_0-1}(0,t) - G_{k_0-1}(t,t).$

From the positive decreasing nature of ${g^{(k_0-1)}}$ we see that ${G_{k_0-1}(t,t) \leq G_{k_0-1}(t,0)}$ and so ${G_{k_0-1,n}(t)}$ is non-negative and can thus be ignored for the purposes of lower bounds. (There are similar improvements available for higher ${n}$ but this seems to only give negligible improvements and will not be pursued here.) Thus we obtain

$\displaystyle \beta \geq G_{k_0-1}(0,0) (1-\kappa') \ \ \ \ \ (10)$

where

$\displaystyle \kappa' := \sum_{2 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n-1}{2} \frac{(k_0-1)^n}{n!}$

$\displaystyle (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{(k_0-1)/2}\ \frac{dt}{t})^n.$

Estimating ${\kappa'}$ similarly to ${\kappa}$ we conclude that

$\displaystyle \kappa' \leq \tilde \kappa'$

where

$\displaystyle \tilde \kappa' := \sum_{2 \leq n < \frac{1+4\varpi}{4\delta}} \frac{1}{n!} \frac{3^n-1}{2} (\frac{1+4\varpi}{2\delta} \exp( - \frac{2(k_0-1) \delta}{1+4\varpi} ))^n.$

By (9), (10), we see that the condition (1) is implied by

$\displaystyle (1+4\varpi) (1-\kappa') > \frac{4G_{k_0}(0,0)}{k_0 G_{k_0-1}(0,0)} (1+\kappa).$

By Theorem 14 and Lemma 15 of this previous post, we may take the ratio ${\frac{4G_{k_0}(0,0)}{k_0 G_{k_0-1}(0,0)}}$ to be arbitrarily close to ${\frac{j_{k_0-2}^2}{k_0(k_0-1)}}$ . We conclude the following theorem.

Theorem 2 Let ${0 < \varpi < 1/4}$ and ${0 < \delta < 1/4 + \varpi}$ be such that ${MPZ[\varpi,\delta]}$ holds. Let ${k_0 \geq 2}$ be an integer, define

$\displaystyle \kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{k_0/2}\ \frac{dt}{t})^n$

and

$\displaystyle \kappa' := \sum_{2 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n-1}{2} \frac{(k_0-1)^n}{n!}$

$\displaystyle (\int_{4\delta/(1+4\varpi)}^1 (1-t)^{(k_0-1)/2}\ \frac{dt}{t})^n$

and suppose that

$\displaystyle (1+4\varpi) (1-\kappa') > \frac{j_{k_0-2}^2}{k_0(k_0-1)} (1+\kappa).$

Then ${DHL[k_0,2]}$ holds.

As noted earlier, we heuristically have

$\displaystyle \tilde \kappa \approx \frac{1+4\varpi}{\delta} \exp( - \frac{2k_0 \delta}{1+4\varpi} )$

and ${\tilde \kappa'}$ is negligible. This constraint is a bit better than the previous condition, in which ${\tilde \kappa'}$ was not present and ${\tilde \kappa}$ was replaced by a quantity roughly of the form ${2 \log(2) k_0 \exp( - \frac{2k_0 \delta}{1+4\varpi})}$ .

91 comments

Comments feed for this article

11 June, 2013 at 10:01 pm

REMIDI UAS SEMESTER 2

[…] Further analysis of the truncated GPY sieve This post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, we are rolling the thread over to the current post. We also take the opportunity to correct some errors in the treatment of the truncat … Wed, 12 Jun 2013 00:54:00 CDT more info… […]

11 June, 2013 at 10:04 pm

The prime tuples conjecture, sieve theory, and the work of Goldston-Pintz-Yildirim, Motohashi-Pintz, and Zhang | What's new

[…] The above argument is not quite correct; a corrected (and improved) version is given at this newer post.] The product is by e.g. Mertens’ theorem, while . So the contribution of this case is […]

11 June, 2013 at 11:31 pm

v08ltu

If it all holds up, using the exponential integral directly instead of the approximant (this saves about 5%), I get that $(\omega,\delta)=(1/891,7/17028)$ and $k_0=22951$ is best. I have $\tilde\kappa\approx 1.6147592\cdot 10^{-5}$ rather than $\tilde\kappa\approx 1.69674148\cdot 10^{-5}$ that comes from the approximant.

11 June, 2013 at 11:53 pm

v08ltu

The relative error in the exponential integral approximation is about $(1+4\omega)/2k_0\delta\approx 1/18.8$ (5%). On the other hand, with $(1-x)\le e^{-x}$ as following Pintz, I think the main effect is at $x$ as above, so only lose 0.15%.

12 June, 2013 at 2:11 am

Gergely Harcos

What is the value of $\tilde \kappa'$ ? Also, what do you get with the improved $\kappa$ and analogous $\kappa'$ that I suggested below? My preliminary calculation tells that we save about 2%.

12 June, 2013 at 1:18 pm

v08ltu

The $\tilde\kappa'$ would be about the square, or $10^{-10}$ . There is really no reason to make any approximations in the $n=1$ case, which should dominate, for there the integrals are easy. But you’ve probably worked this all out by now.

12 June, 2013 at 2:40 pm

Gergely Harcos

Yes, I have now understood this. Thank you!

12 June, 2013 at 1:05 am

Gergely Harcos

This is very nice and clean. We can improve on $\kappa$ as follows. By a similar argument as in the post,

$G_{k_0}(t_1+t_2,t_1+t_2) \leq (1-t_1)_+^{k_0} G_{k_0}(t_2,t_2)$ .

By Cauchy,

$G_{k_0}( \sum_{i \in S} t_i, \sum_{i \in T} t_i )\leq G_{k_0}^{1/2}( \sum_{i \in S} t_i, \sum_{i \in S} t_i )G_{k_0}^{1/2}( \sum_{i \in T} t_i, \sum_{i \in T} t_i ).$

Applying the first observation iteratively on both factors,

$G_{k_0}( \sum_{i \in S} t_i, \sum_{i \in T} t_i ) \leq (\prod_{i=1}^n(1 - t_i)_+^{k_0/2}) G_{k_0}(0,0).$

Therefore in (8) and in the definition of $\kappa$ we can lower $(1 - \frac{1}{2} \sum_{i=1}^n t_i)_+^{k_0}$ to $\prod_{i=1}^n(1 - t_i)_+^{k_0/2}$ , and for the new $\kappa$ we infer

$\kappa \leq \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} (\int_{4\delta/(1+4\varpi)}^1 (1 - t)^{k_0/2}\ \frac{dt}{t})^n$ .

From here we can proceed as in the post, using $(1-t)_+<e^{-t}$ , but the integral should be straightforward numerically.

Some typos:

1. In (3) the factor $\theta(n+h)$ is missing.

2. " $d'_1,d'_2$ coprime to $[a_1,a_2]$ " should be " $d'_1,d'_2$ coprime to $a$ ".

3. "which are now non-negative functions" should be "which are now functions of constant sign".

4. Three displays above (8), $(1-t_2)_+^{-k_0/2}$ should be $(1-t_2)_+^{k_0/2}$ .

[Corrections 1-4 implemented, thanks. -T.]

12 June, 2013 at 1:13 am

Gergely Harcos

Actually the upper bound I stated for the new $\kappa$ is an identity. All in all, the above modification simplifies the proof and produces a better result.

12 June, 2013 at 3:10 am

Eytan Paldi

Can you please state explicitly the identity? (because there is a stable numerical expression for the last one dimensional integral – showing it to be a remainder term for Taylor series approximation of the log function, which gives a new improved upper bound for the integral in terms of a power of $\delta / (1/4 + \varpi)$ instead of the current exponential bound.)

12 June, 2013 at 3:28 am

Gergely Harcos

$\kappa = \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{3^n+1}{2} \frac{k_0^n}{n!} (\int_{4\delta/(1+4\varpi)}^1 (1 - t)^{k_0/2}\ \frac{dt}{t})^n$

12 June, 2013 at 5:43 am

Eytan Paldi

Thanks. Consider now the integral above, denoting $t_0$ for its lower bound and $k$ for the exponent $k_0 / 2$ .
The new upper bound is most simply obtained by replacing in the integrand $1/ t$ by $1/ t_0$ .
Note that for large $t_0$ , the resulting new bound
$(1 - t_0)^{k + 1} / [(k + 1) t_0)]$ should be better then the exponential one since it captures better the integrand behavior for large values of t.

Note that by trying directly to evaluate the integral by expanding
$(1 - t)^k$ in the integral and then integrate termwise, may lead to serious numerical problems since the alternating large binomial coefficients may lead to a significant loss of precision.
Fortunately the above numerical instability can be avoided by using the substitution $u = 1 - t$ so the integrand becomes
$1/(1-u) - \sum_{j=0}^{k -1} u^j$ , so by term-wise integration it follows that the integral is in fact the remainder term for the k-th degree Taylor series approximation of $-\log(1-u)$ in powers of u at
$u = 1 - t_0$ , which implies the same new bound above.

Practical remark: it is important to note that all the coefficients of the above Taylor series approximation of $-\log (1-u)$ in powers of
$u$ are positive and slowly decreasing so its computation at
$u= 1 - t_0$ should be numerically stable!

Final remark: in your integral bound, $k = k_0 /2$ which is integer
only for EVEN $k_0$ (otherwise, it is expressed by incomplete Beta function which can’t be expressed by a finite sum of elementary functions as above, but the new bound still holds!)

12 June, 2013 at 6:28 am

Gergely Harcos

@Eytan: At this point I leave the calculation to computers. SAGE does a good job in evaluating such integrals numerically. For example, for $(\varpi,\delta,k_0)=(\frac{1}{891},\frac{7}{17028},22949)$ I get

$I:=k_0\int_{4\delta/(1+4\varpi)}^1 (1 - t)^{k_0/2}\ \frac{dt}{t}\approx 7.95032915715\times 10^{-6}$ ,

and $1+\kappa$ is essentially $(e^{3I}+e^I)/2$ .

12 June, 2013 at 7:33 am

Terence Tao

Thanks for this! One amusing thing is that the bound $\prod_{i=1}^n (1-t_i)_+^{k_0/2}$ is in fact very slightly worse than $(1-\sum_{i=1}^n t_i/2)^{k_0}$ , but the product formulation ends up being so much cleaner that it is easier to see the opportunity to improve upon the bound involving the exponential function. The above estimates also reveal that the (upper bounds on the) terms in which $S \cap T \neq \emptyset$ are smaller than the others by an additional factor of at least $(1 - \frac{4\delta}{1+4\varpi})^{k_0/2}$ , which in principle can improve the $\frac{3^n+1}{2}$ , $\frac{3^n-1}{2}$ factors to be close to $2^n, 0$ respectively for $n \geq 2$ , although this only leads to negligible improvements at the cost of a messier formula.

12 June, 2013 at 2:14 pm

Gergely Harcos

1. Amusing indeed! In fact the optimized version of

$G_{k_0}(t_1+t_2,t_1+t_2) \leq (1-t_1)_+^{k_0} G_{k_0}(t_2,t_2)$

reads

$G_{k_0}(t_1+t_2,t_1+t_2) \leq (\frac{1-t_1-t_2}{1-t_2})_+^{k_0} G_{k_0}(t_2,t_2)$

which by induction recovers the original

$G_{k_0}(\sum_{i=1}^n t_i,\sum_{i=1}^n t_i) \leq (1-\sum_{i=1}^n t_i)_+^{k_0} G_{k_0}(0,0)$

2. We beat the quarter million barrier for prime gaps!

12 June, 2013 at 2:35 pm

v08ltu

Can one improve the lower bound on $\beta$ via not being so lossy on $G_{k0-1,1}(t)$ , which now appears to go as $A+B-C$ and $B\ge C$ , so it’s nonnegative? (In fact, $A=B$ by symmetry.) Maybe an improvement would use convexity somehow, or simply use the explicit expressions for $g$ ?

12 June, 2013 at 3:05 pm

v08ltu

It could be that we could almost obtain $G_{k_0-1}(t)\gtrapprox 2(1-t)^{k0/2}G(0,0)-(1-t)^{k0}G(0,0)$ , if the upper bound of $G(t,0)\le (1-t)^{k0/2}$ were nearly sharp.

12 June, 2013 at 2:10 am

Eytan Paldi

It seems that there is a typo in the summands in (3).

12 June, 2013 at 2:11 am

Gergely Harcos

I mentioned this above (see item #1 in “Some typos”).

12 June, 2013 at 5:13 am

Gergely Harcos

Using the small improvement I described above, SAGE tells me that $(\omega,\delta)=(1/891,7/17028)$ and $k_0=22949$ is best. For this choice, $\kappa\approx 1.5900816\times 10^{-5}$ and $\kappa'\approx 1.2662224\times 10^{-10}$ .

12 June, 2013 at 12:50 pm

Eytan Paldi

A suggestion to further optimize $\varpi , \delta$ :
It seems that always the minimization of $k_0(\varpi, \delta)$ is done

1. Subject to the (unnecessary) restriction that $1 / \varpi$ is an integer, and

2. $\delta$ is determined by $\varpi$ to satisfy the admissibility inequality constraint as EQUALITY constraint (i.e. the maximal $\delta$
possible under the constraint).

My suggestion to deal with these two problems is:

1′. To refine the optimization of $1/ \varpi$ in its neighborhood by allowing it to be a multiple of 0.1 (or 0.01) in the interval (890, 892).

2′. Using the previously optimized (not necessarily integer!) value of
$1/ \varpi$ FIXED, and optimizing the previous value of
$1/ \delta$ as an integer satisfying the admissibility constraint (in order to get a GLOBAL search for $\delta$ – not only near the admissibility boundary!) and then using a finer LOCAL optimization search for
$1/ \delta$ as a multiple of 0.1 (or 0.01).

Since both steps (1′), (2′) can only reduce the value of $k_0$ , by alternating between this steps, k_0 should converge to a local minimum (by making the local search in (1′), (2′) finer enough.)
One may find many variants to this “alternating search” optimization, in particular a coarse GLOBAL search may be added at the beginning of (1′) in each iteration, using the value of $\delta$ from the previous iteration FIXED (in order to keep a GLOBAL optimization at each iteration.)

Remark: Note that the current values of $\varpi$ and $\delta$
have the same order of magnitude!

12 June, 2013 at 3:05 pm

Gergely Harcos

1. The expressions for $\kappa$ and $\kappa'$ are decreasing in $\delta$ , hence for a given $\varpi$ we do not lose anything by taking the $\delta$ satisfying $207\varpi+43\delta=\frac{1}{4}$ .

2. I believe that $k_0=22949$ is optimal for the current version of Theorem 2. I don’t have a formal proof, but it is advantageous to see how the ratio of $(1+4\varpi) (1-\kappa')$ and $\frac{j_{k_0-2}^2}{k_0(k_0-1)} (1+\kappa)$ changes as we vary $k_0$ or $\varpi$ . For $\varpi=\frac{1}{891}$ , the ratio is $0.9999998754$ when $k_0=22948$ , it is $1.0000000161$ when $k_0=22949$ , and it is $1.0000001568$ when $k_0=22950$ . For $k_0=22949$ , the ratio is $0.9999996427$ when $\varpi=\frac{1}{890}$ , it is $1.0000000161$ when $\varpi=\frac{1}{891}$ , and it is $0.9999990240$ when $\varpi=\frac{1}{892}$ .

12 June, 2013 at 4:07 pm

Eytan Paldi

Thank you for the data!
It follows therefore that for each given $\varpi$ the optimal
$\delta$ is determined such that the admissibility constraint should becomes equality (i.e. the maximal permissible $\delta$ ), which leaves $\varpi$ as the ONLY free parameter to minimize $k_0$ . Therefore (since $1/ \varpi$ is NOT restricted to be an integer), I suggest to vary $1/ \varpi$ with small steps (0.1 say) in the interval (890, 892) to see if one of these 19 values of $\varpi$ leads
to a new record of $k_0$ . (since it involves a small number of trials, I think it worth the effort!)

13 June, 2013 at 5:45 am

Eytan Paldi

I’m trying to analyze your data about the ratio above as a function of
$1/ \varpi$ and $k_0$ as free parameters ( $\delta$ is not free because of its dependence on $\varpi$ via the restriction equality.)
It is easy to see from your data the almost linear dependence of the ratio
on $k_0$ in $[22948, 22950]$ for $1/ \varpi = 891$ (which was quite expected), but the dependence of this ratio on $1/ \varpi$ in
$1 /\varpi$ in $[890, 892]$ for $k_0 = 22949$ must be WRONG because

1. The ratio should be $> 1$ for the admissible pair
$(1/ \varpi , k_0) = (892, 22949)$ , while the ratio you gave was
$0.9999990240$ .

2. For $k_0 = 22949$ the dependence of the above ratio on
$1/ \varpi$ in $[890, 892]$ is NOT monotonic (as it should be.)

It seems that the problem is due to a WRONG computation of the above ratio for the pair $(1 /\varpi , k_0) = (892, 22949)$ . Can you check it please and let me know the correct ratio. Thanks

13 June, 2013 at 5:53 am

Gergely Harcos

I am confident my calculations are correct, and v08ltu independently confirmed them. Terry Tao also checks everything here.

13 June, 2013 at 6:00 am

Eytan Paldi

But how is it possible that the admissible pair (892, 22249) gave a ratio LESS than 1? (it contradict the admissibility criterion in theorem 2!)

13 June, 2013 at 6:27 am

Gergely Harcos

There is no contradiction to Theorem 2. Let us fix $k_0=22949$ . In the interval $(\frac{1}{892},\frac{1}{890})$ the expression $\frac{4\delta}{1+4\varpi}$ (for the optimized $\delta$ ) is decreasing, hence $\kappa$ and $\kappa'$ are increasing. So in Theorem 2 we are looking at the ratio of two increasing quantities: $1+4\varpi$ and $\frac{j_{k_0-2}^2}{k_0(k_0-1)}\cdot\frac{1+\kappa}{1-\kappa'}$ . The fact that the ratio has a local maximum in $(\frac{1}{892},\frac{1}{890})$ simply reflects the fact that $1+4\varpi$ grows faster than $\frac{1+\kappa}{1-\kappa'}$ on the left end of this interval, but this tendency changes somewhere inside the interval.

13 June, 2013 at 6:55 am

Eytan Paldi

It seems VERY strange that the criterion in theorem 2 is sufficient to decide that for $k_0 = 22949$ , the parameter $\varpi = 1/891$ is admissible (since the above ratio is greater than 1), while for
$\varpi = 1/ 892$ (which obviously should be admissible) it can’t do so (because of ratio less than 1).
It is still possible (since the criterion is only sufficient), but it still seems very strange!

13 June, 2013 at 8:42 am

Gergely Harcos

The phenomenon is not so strange if you think of the role and meaning of the parameter $\delta$ . Ideally it would be infinite, i.e. we would use all divisors for the sieve leading to Theorem 2. In that case we would not have to consider $\kappa$ and $\kappa'$ at all (they would be zero), and the crucial ratio would be proportional to $1+4\varpi$ , i.e. monotonic as you expect it to be. The reason that we do need a finite $\delta$ is our lack of understanding of the equidistribution of primes to large moduli, including those with possibly large prime factors. Zhang’s discovery is that for sufficiently small $\varpi$ , we can allow sufficiently many (but not all) prime factors to participate in the moduli, and this is measured by $\delta$ . At this point we have two opposite forces: Theorem 2 wants a $\delta$ as large as possible, but the necessary hypothesis $MPZ[\varpi,\delta]$ is only available for sufficiently small $\delta$ depending on $\varpi$ . So the question is: which $\varpi$ gives the best compromising value of $\delta$ , one that is sufficiently small for the hypothesis to hold provably, and one that is sufficiently large for a good value of $k_0$ . As things stand now, the best value lies somewhere between $\frac{1}{892}$ and $\frac{1}{890}$ . It is a complicated proof!

12 June, 2013 at 3:13 pm

v08ltu

I always use tenths of an integer in the reciprocal of $\omega$ , but the $k_0$ -result has never needed such precision in reporting.

12 June, 2013 at 4:19 pm

Eytan Paldi

It depends on the sensitivity of $k_0$ to small changes in
$1/ \varpi$ as well as how the above ratio is close to 1 (i,e, very small changes may lead to a downward “jump” to $k_0 -1$ if the ratio is sufficiently close to 1.)

12 June, 2013 at 1:40 pm

v08ltu

I agree with this bound.

12 June, 2013 at 9:00 am

Craig Helfgott

I have one question, and it may be obvious, but it is confusing me: When you derive (6) from the preceding line, you are apparently factorizing $k_0^{\Omega([a_1 d_1, a_2 d_2])}$ as $k_0^{\Omega([a_1, a_2])} k_0^{\Omega([d_1, d_2])}$ . Why is this allowed?

12 June, 2013 at 9:04 am

Craig Helfgott

Okay, went back to the previous post for the definition of $\Omega$ . Sorry, I thought you were using Big-Omega notation.

12 June, 2013 at 1:10 pm

unknown mathematician

Dear Prof. Tao and other top mathematicians here,
Is the purpose of this to turn Zhang´s paper obsolete even before it appears in print? It seems that this is already the case.

I wonder if had the author of the paper being studied been one of the top people in the area (one of you) if it would have generated such a collective effort to improve the result. I have never seen anything like this before.

I am a big fan of many math blogs and this is one of my favorites, but I cannot help the feeling that there is something not very nice happening here.

12 June, 2013 at 1:29 pm

Ghaith

Dear unknown mathematician, I don’t think this is the case. Zhang’s result is amazing (I certainly wasn’t expecting to see something like it that soon). I think the collective effort you observe is natural since this is the most exciting thing to happen in number theory in a while. As a result, some people (e.g. me!) have gotten far more interested in learning about the proof. I think that the progress that has been made since then is impressive, and impressively rapid.

12 June, 2013 at 2:35 pm

Gergely Harcos

Not at all! First Zhang’s paper already appeared in “print” (the final version is on the journal webpage, the physical paper is not important). Second, nothing can make the work of Zhang or Goldston-Pintz-Yildirim obsolate, since the ground-breaking ideas are there. I think what is happening is this. A few months ago noone (except for Zhang perhaps) thought that we would see bounded gaps between primes. Zhang’s “70 million” is not an astronomical constant like $10^{3000}$ that was customary in similar advances such as ternary Goldbach, Waring for cubes, Catalan’s conjecture etc. So one simply wonders what Zhang’s method with some tweaks is capable of. I find this a nice way to pay respect to Zhang, respond to the basic curiosity “So how small are those gaps, really?”, have fun together as a PolyMath group, and understand the argument as well as possible. There is really no reason to hold back progress, time is our real enemy.

12 June, 2013 at 4:28 pm

Dan Goldston

All this interest and activity generated by Zhang’s work is a tribute to the importance of his contribution. It is true that the paper will not appear in print for years, but it is accepted for publication and available for others to build on. I think that anyone working on this problem for years to come is going to study Zhang’s paper for his insight.

13 June, 2013 at 1:58 am

Pete

Obviously I don’t know how Zhang feels about it, but for sure I would be extremely happy if a result of mine was getting this kind of attention. It says: this result is not just worth a paper in Annals, it is worth weeks or months of time of the world’s best mathematicians (and it will surely be judged worth prize(s) as well).

Eventually there will be a (probably) Polymath long paper which gives substantially better bounds than Zhang’s original. It will probably also be published in Annals. But it will surely be written to be very clear that the improvements are absolutely relying on Zhang’s fundamental breakthrough. And no-one will get prizes for it.

There are also different levels of achievement on this problem. Pre-Zhang, the best known result was only somewhat better than the trivial point that the minimum gap isn’t larger than the average gap (and this was already a big result). Probably it was expected that the next result would be some slowly-growing-function gap, and as several people already said, no-one expected to see bounded gaps any time soon. In that context, if you can prove any bounded gaps theorem, then you are happy: you don’t really care if the bound is in the thousands, millions, or some tower of exponents (and exponentials usually appear in these kinds of things the first time, in some sense Zhang got lucky that his approach doesn’t need any). Zhang himself fairly obviously did not care too much: he deliberately didn’t optimise his work in the interests of writing a more readable paper, whereas the polymath version will probably have a lot of strange numbers and optimisations done by computer, as well as the ‘genuine’ improvements by modifying the approach, which will make it a lot harder going.

The books will record the fact of bounded gaps in the primes as ‘Zhang’s Theorem’, and the polymath result will be a note as an ‘improved Zhang’s Theorem’ or such: it seems very likely that the approach will not get to any gap such as 16, or 6, let alone 2, which would merit a new name.

13 June, 2013 at 2:06 am

Gergely Harcos

Actually before Zhang it was known that around $x$ we can find prime gaps of size less than $(\log x)^{3/7+o(1)}$ , a result by Pintz improving on a similar result of Goldston-Pintz-Yildirim with exponent $1/2$ in place of $3/7$ . I would not call this “somewhat better than the trivial point”, it was already a fantastic result.

13 June, 2013 at 3:35 am

Pete

Sure, but when log is easy and the aim is 2, polylog doesn’t look like a big step. I think the point you (and I) are trying to make is that even polylog was already very hard.

13 June, 2013 at 5:48 am

Gergely Harcos

I always thought of $(\log x)^{1/2}$ as being half-way between the trivial gaps and bounded gaps (although, admittedly, I did not expect to see bounded gaps in my life). In some sense Zhang justified this feeling of mine.

13 June, 2013 at 2:42 am

bengreen

I think these are pretty good responses to unknown mathematician’s comment. If polymath wasn’t happening, the alternatives would be that Zhang’s 70000000 just sat there for everyone to admire, or else people would publish piecemeal improvements and there would be one enormous mess deciding priorities (for those who cared) and even correctness. Even now, with the bound on $H$ around 300000, there could yet be over 100000 papers on the subject of improving the gap if we were proceeding in this way. The polymath is the perfect solution to this problem in my view. It’s highly inclusive and no-one fusses over priorities and credit. In addition, as pointed out above, these great ideas – not just of Zhang, but also of GPY, BFFI, etc – are getting publicly celebrated and debated. I can’t really imagine why that would annoy any of them.

To echo Pete’s comment, Zhang pretty explicitly states that his exponents are not optimised. Most likely he knew a few of the improvements that have come to light already in the polymath discussion, but he deferred from mentioning them so as to write a more readable paper. Anyway, I don’t get any kind of sense that the contributors to this blog are rushing to show Zhang how he could have done better, if that was the aspect of this thought to be “not very nice” by unknown mathematician.

13 June, 2013 at 5:44 am

Gergely Harcos

Actually $H$ is now below 250000 :-)

16 June, 2013 at 9:05 am

unknown mathematician

First I want to thank you for all the responses to my comment. I also want to apologize for my very poor choice of words in it. I do have the highest respect for the mathematicians here not only for their mathematical abilities but also for the very high ethical stand assumed. As was mentioned before I too, would feel honored if one of my papers would get this much attention from a mathematician like Terence Tao.

I did not say that Zhang would not be given the proper credit for his work. His name is already in History and every response to my comment made that clear.

The only thing I still suspect ( I cannot be sure for I am not a number theorist) is that after all the work done here, if there are still insights in the original paper that have not been “dissected” here.

This went too far and I do regret to have written the above comment but cannot undo it … yet.

13 June, 2013 at 4:10 am

Mark Bennet

I think that Zhang gets huge credit through this approach to his work, because it is clear that the improvements are founded on his work and insight – as an interested non-specialist that’s what I read – and he will also see the cascade of ideas and improvements his work has started.

Another advantage, as yet unstated, is that the Polymath approach here also tests the limits of what is possible using Zhang’s insights and maps the various barriers to progress. So that helps to see where new insight is necessary to go further.

13 June, 2013 at 7:10 am

Andre K.

Dear Unknown Mathematician,
My feeling reading this blog is exactly the opposite of yours. I see it as a tribute to Zhang. I would be very proud to see so many advances based on my own ideas. Also, for people like me, amateur mathematicians (did my undergrad in math but moved on to other jobs), a blog like this is a magnificent window on how ‘real mathematicians’ work. It is an opportunity to see the work build up with all the unfruitful paths that do not work out and the little by little progress that is made. Otherwise, we would only see the final product – the paper in a journal. I commend Terence Tao for exposing all of us to this wonderful adventure. Andre K.

12 June, 2013 at 2:21 pm

Gergely Harcos

Some typos: In the display below the definition of $\kappa$ , $\exp(-k_0/2)$ should be $\exp(-t)$ . In the definition of $\kappa'$ , $\exp(-\frac{k_0}{2}t)$ should be $(1-t)^{k_0/2}$ , and integration should end at $t=1$ . In Theorem 2, the values of $\kappa$ and $\kappa'$ should be updated similarly.

[Corrected, thanks – T.]

12 June, 2013 at 3:32 pm

Gergely Harcos

Actually, in the definition of $\kappa'$ , the exponent $k_0/2$ should be $(k_0-1)/2$ . Two occurrences.

[Corrected, thanks – T.]

12 June, 2013 at 11:23 pm

Gergely Harcos

In the definition of $\kappa'$ , the denominator should be $n!$ instead of $n$ . Two occurrences.
[Corrected, thanks – T.]

13 June, 2013 at 5:00 pm

Non-Mathematician

I am absolutely a non-mathematician and find this site fascinating, and feel good for Zhang every time I visit here. No I don’t read the math discussions, but only read the shrinking numbers (and why they got crossed out.)

14 June, 2013 at 1:37 am

Gergely Harcos

I claim that $G_{k_0,n}(t_1,\ldots,t_n)$ is nonnegative, hence $\kappa'=0$ is admissible in Theorem 2. For the proof let us consider functions of the form

$(t_1,t_2)\mapsto\int_\mathbb{R}g_1(t+t_1)g_2(t+t_2)\ d\nu(t)$

where $d\nu(t)$ is a fixed measure on $\mathbb{R}$ , and $g_1,g_2:\mathbb{R}\to\mathbb{R}$ are decreasing nonnegative functions such that the integrand is integrable. Let us call a function $G(t_1,t_2)$ nice, if it is a sum of functions of the above form. We observe that if $G(t_1,t_2)$ is nice, then $G(t_1+\tau,t_2)$ and $G(t_1,t_2+\tau)$ are nice for for any $\tau\in\mathbb{R}$ . Moreover, $G(t_1,t_2)-G(t_1+\tau,t_2)$ and $G(t_1,t_2)-G(t_1,t_2+\tau)$ are nice for any $\tau\geq 0$ . It follows that

$(\Delta_\tau G)(t_1,t_2):=G(t_1+\tau,t_2)+G(t_1,t_2+\tau)-G(t_1+\tau,t_2+\tau)$

is nice for any $\tau\geq 0$ . Now we see that, for any $t_1,\dots,t_n\geq 0$ , the function $\Delta_{t_1}\dots\Delta_{t_n}G$ is nice, hence its value at $(0,0)$ is nonnegative. However, we can check by induction on $n$ that this this value is nothing but

$\sum_{\{1,\ldots,n\} = S \cup T} (-1)^{|S \cap T|} G( \sum_{i \in S} t_i, \sum_{i \in T} t_i ).$

Specializing to $G=G_{k_0}$ gives the claim.

14 June, 2013 at 10:12 am

Terence Tao

Actually, could you give more detail as to why $G(t_1,t_2) - G(t_1+\tau,t_2)$ is nice? Taking Newton quotients this would seem to imply that $-\frac{\partial}{\partial t_1} G(t_1,t_2)$ is also nice, which looks like a statement that would need control on higher derivatives of $g_1$ .

In our specific case, we do know that the Bessel-type function $g$ has derivatives with a fixed (alternating) sign, but one has to be careful when truncating at the endpoint $t=1$ since one only has a limited amount of regularity at this endpoint.

14 June, 2013 at 6:38 pm

Gergely Harcos

You are right, I announced the result too quickly. I think the new values of $\kappa$ and $\kappa'$ are still ok, we don’t need any regularity at $t=1$ .

To fix the proof, let us call a function $g:\mathbb{R}\to\mathbb{R}$ appropriate if it is supported on some $[a,b]$ such that $g^{(j)}$ has sign $(-1)^j$ in $(a,b)$ . If $g(t)$ is appropriate, then so is $g(t+\tau)$ for any $\tau\in\mathbb{R}$ , while $g(t)-g(t+\tau)$ is a sum of two appropriate functions for any $\tau\geq 0$ . Hence if we restrict to appropriate functions $g_1,g_2:\mathbb{R}\to\mathbb{R}$ in the definition of nice functions, and we take $d\nu(t)=t^{k_0-1}dt$ restricted to $[0,1]$ , then the argument goes through to yield

$0\leq(\Delta_{t_1}\dots\Delta_{t_n}G)(0,0)\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})G(0,0)$ .

We apply this for $g_1(t)=g_2(t)=t^{(1-k_0)/2} J_{k_0-1}(j_{k_0-2}\sqrt{t})$ restricted to $[0,1]$ to see that the new $\kappa$ is admissible. To obtain $\kappa'=0$ , we use instead $d\nu(t)=t^{k_0-2}dt$ and $g_1(t)=g_2(t)=t^{(2-k_0)/2} J_{k_0-2}(j_{k_0-2}\sqrt{t})$ , all restricted to $[0,1]$ .

So do you agree that Theorem 2 holds with the new values of $\kappa$ and $\kappa'$ ?

14 June, 2013 at 6:47 pm

Gergely Harcos

Actually $G(0,0)$ should be $\|G\|(0,0)$ here and also in my comment today at 4:56 am. Note that for $g_1=g_2$ these values
are equal.

15 June, 2013 at 7:58 am

Terence Tao

I’m not yet clear why $g(t)-g(t+\tau)$ is the sum of two appropriate functions, particularly in the case when $a < t < b < t+\tau$ when one has to cross a point of potential discontinuity of $g$ . Could you elaborate?

15 June, 2013 at 5:35 pm

Gergely Harcos

Sorry my setup was still incompatible with my intuition. I think I got it right now, see my longer post below, sent a few minutes ago.

14 June, 2013 at 4:56 am

Gergely Harcos

This is a continuation of my previous comment. Let us introduce the notation

$\|G\|(t_1,t_2):=(\int_\mathbb{R}g_1^2(t+t_1)\ d\nu(t))^{1/2}(\int_\mathbb{R}g_2^2(t+t_2)\ d\nu(t))^{1/2}$

so that $G(t_1,t_2)\leq \|G\|(t_1,t_2)$ by Cauchy, with equality when $g_1=g_2$ and $t_1=t_2$ . Let us also fix $d\nu(t):=t^{k_0-1}dt$ . Then we can see, as in the main post, that replacing $G(t_1,t_2)$ by $G(t_1+\tau,t_2)$ or $G(t_1,t_2+\tau)$ for any $\tau\in\mathbb{R}$ multiplies the function $\|G\|$ by at most $(1-\tau)_+^{k_0/2}$ , while replacing $G(t_1,t_2)$ by $G(t_1,t_2)-G(t_1+\tau,t_2)$ or $G(t_1,t_2)-G(t_1,t_2+\tau)$ for any $\tau\geq 0$ cannot increase $\|G\|$ . It follows, by Minkowski’s inequality, that $\|\Delta_\tau G\|\leq 2(1-\tau)_+^{k_0/2}\|G\|$ for any $\tau\geq 0$ , hence for any $t_1,\dots,t_n\geq 0$ we have

$\|\Delta_{t_1}\dots\Delta_{t_n}G\|\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})\|G\|$ .

In particular, using the point $(0,0)$ we infer

$(\Delta_{t_1}\dots\Delta_{t_n}G)(0,0)\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})G(0,0)$ .

Specializing to the nice function $G=G_{k_0}$ we obtain finally

$0\leq G_{k_0,n}(t_1,\ldots,t_n)\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})G(0,0)$ .

This is an improved version of (8), and yields Theorem 2 with the smaller values $\kappa':=0$ and

$\kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{1}{n!} (2k_0\int_{4\delta/(1+4\varpi)}^1 (1-t)^{k_0/2}\ \frac{dt}{t})^n$ .

14 June, 2013 at 5:20 am

Gergely Harcos

In practice one can replace $1+\kappa$ by the clean

$1+\tilde\kappa:=\exp(2k_0\int_{4\delta/(1+4\varpi)}^1 (1-t)^{k_0/2}\ \frac{dt}{t})$ .

14 June, 2013 at 5:51 am

Eytan Paldi

In fact, you reduced (in the sum) the factor $(3^n + 1) / 2$ to
$2^n$ but since (in general) $n=1$ dominates, the improvement in $\kappa$ might be small. I think that the elimination of $\kappa'$ could be more significant.

14 June, 2013 at 5:56 am

Gergely Harcos

The elimination of $\kappa'$ is also insignificant, because it has no $n=1$ term. At the moment the improved values serve esthetic purposes, but for smaller values of $k_0$ they might be useful eventually.

14 June, 2013 at 8:45 am

Terence Tao

Very neat! I’m impressed that you got all this positivity just from the monotone nature of $g^{(k_0)}$ and $g^{(k_0-1)}$ ; I would have thought that further properties of higher derivatives would be needed, but apparently not.

As you say it probably doesn’t lead to any improvement on $k_0$ with our current values of $\varpi,\delta$ but may make a contribution in the future.

14 June, 2013 at 5:32 am

Eytan Paldi

In proposition 1, in both sums n should start with 1 (not 0)

14 June, 2013 at 6:00 am

Gergely Harcos

No they are ok. The $n=0$ terms are the leading terms $G_{k_0}(0,0)$ and $G_{k_0-1}(0,0)$ , while the $n\geq 1$ terms are compared to these, the respective ratios being bounded by $\kappa$ and $\kappa'$ .

14 June, 2013 at 6:23 am

Eytan Paldi

But $n=0$ means that there are no integration variables!

14 June, 2013 at 6:33 am

Gergely Harcos

Yes. It is an empty multiplicative integral, i.e. equal to 1 (just like an empty product). This is a convention that Terry uses. If you look at the second display before Proposition 1, you will see that the $n=0$ term corresponds to the $a=1$ term there (because this is the only number with no prime factor), and this term equals $G_{k_0}(0,0)$ .

14 June, 2013 at 6:46 am

Eytan Paldi

I don’t understand why do you call this empty integral “multiplicative” and the logic behind its definition as 1 (irrespective of its integrand)
Anyway, for clarification I suggest to separate the $n=0$ summand from the sum (because I don’t think this convention to be a standard one.)

14 June, 2013 at 8:05 am

Terence Tao

The logic is similar to the reason why powers $x^n$ for $x \neq 0$ , or more generally products $\prod_{i=1}^n x_i$ for $x_i \neq 0$ , are by convention set equal to $1$ when $n=0$ (see the Wikipedia entry on “empty products“), and can in fact be deduced from that standard convention as follows.

${\bf R}^n$ is the standard real $n$ -dimensional vector space. Thus ${\bf R}^0$ is the standard zero-dimensional vector space, i.e. the point $\{0\}$ . More formally, ${\bf R}^n$ by definition is the set of $n$ -tuples $(x_1,\ldots,x_n)$ , with the zero tuple $(0,\ldots,0)$ identified with $0$ ; thus, ${\bf R}^0$ is the set of $0$ -tuples $()$ , but there is only one such tuple (cf. the $x^0=1$ rule mentioned earlier), and we identify this tuple with $0$ .

To normalise n-dimensional Riemann or Lebesgue integration, we define the measure of a box $\prod_{i=1}^n [a_i,b_i] = \{ (x_1,\ldots,x_n): x_i \in [a_i,b_i] \hbox{ for all }1 \leq i \leq n\}$ when $b_i > a_i$ for all $i$ to equal $\prod_{i=1}^n (b_i-a_i)$ . In the zero dimensional case $n=0$ , the box is a singleton set consists only of the empty tuple $()$ (as can be seen by carefully checking the definition, noting that universal quantification over an empty set is vacuously true), and the product $\prod_{i=1}^n (b_i-a_i)$ is one by the empty product convention. Thus we see that ${\bf R}^0$ has Lebesgue measure one. (Another way of seeing this is recalling that $n$ -dimensional Lebesgue measure in ${\bf R}^n$ is the same thing as $n$ -dimensional Hausdorff measure on ${\bf R}^n$ , and that 0-dimensional Hausdorff measure is counting measure.) In particular, if $F: {\bf R}^0 \to {\bf C}$ is a function, the empty integral

$\int_{{\bf R}^0} F$

is equal to the value $F( 0 )$ of $F$ at the origin $0 = ()$ . Thus for instance

$\int_{\frac{4\delta}{1+\varpi} < t_1 < \ldots < t_n} G_{k-1,n}(t_1,\ldots,t_n) \frac{dt_1 \ldots dt_n}{t_1 \ldots t_n}$

when $n=0$ is equal to the evaluation of the integrand $G_{k-1,n}(t_1,\ldots,t_n) \frac{1}{t_1 \ldots t_n}$ at the origin (note carefully that the region of integration is the singleton set $\{0\} = \{()\}$ rather than the empty set). The denominator looks scary, but recall that the empty product is 1, so that $t_1 \ldots t_n = 1$ when $n=0$ , and so the expression simplifies to $G_{k-1,0}()$ , which is $G_{k-1}(0,0)$ if one works through the definitions.

In the special case when one is integrating a tensor product

$\int_{{\bf R}^n} F_1(x_1) \ldots F_n(x_n)\ dx_1 \ldots dx_n$

for well-behaved functions $F_i$ then it is particularly clear that the $n=0$ case of this integral should be $1$ , since Fubini’s theorem factors this integral as

$\prod_{i=1}^n \int_{{\bf R}} F_i(x_i)\ dx_i$

and by convention the empty product is 1 (informally, the zero-dimensional integral of a “multiplicative” integrand is automatically 1). Another relevant example comes from the identity

$\int_{0 < x_1 < \ldots < x_n < 1}\ dx_1 \ldots dx_n = \frac{1}{n!}$

which extends without difficulty to the $n=0$ case using the correct conventions for zero-dimensional integration and for $0!$ .

Basically, all of n-dimensional integration theory extends without difficulty to the 0-dimensional case when one adopts the correct conventions, much as the theory of exponentiation $(n,x) \mapsto x^n$ for non-zero x and natural number n extends without difficulty to the $n=0$ case when one adopts the correct conventions. Isolating the $n=0$ case can be done if desired, but is not necessary (much as one could write, for instance, the Taylor series $\exp(x) = \sum_{n=0}^\infty \frac{x^n}{n!}$ as $\exp(x) = 1 + \sum_{n=1}^\infty \frac{x^n}{n!}$ if one was for some reason uncomfortable with the standard conventions for $x^0$ and $0!$ ). In order to keep the presentation short and avoid needless duplication of effort in handling a seemingly degenerate case that does not actually need any special attention, I have generally elected keep the n=0 case combined with the positive n cases.

14 June, 2013 at 6:34 am

Anonymous

Pintz’s paper on arxiv has already been corrected can someone update the wiki to reflect that?

[Done, thanks – T.]

14 June, 2013 at 11:04 am

Eytan Paldi

I understand the extension of integration on 0-th euclidean space using its Housdorff measure (which makes sense as “natural”), but I am not sure about the extension of Fubini theorem for this case. Also, It is not clear to me whether this is the only “natural” (and even “the” standard) extension.
(For example, “the” sum of the natural numbers was “naturally” interpreted by Ramanujan as $\zeta (-1) = -1/12$ .)

15 June, 2013 at 9:02 am

Eytan Paldi

Minor remark: perhaps it is better in proposition 1 to replace the summation index i (running over T) by j.

15 June, 2013 at 11:23 am

Eytan Paldi

In the 4-th and 6-th lines before (10), the index n should be 1.

[As explicitly stated just before these lines, the text here is restricted to the case $n=1$ (except for the parenthetical comment, which is explicitly restricted to the higher $n$ cases.) -T.]

15 June, 2013 at 1:34 pm

Eytan Paldi

A combinatorial question: the numbers $(3^n + 1)/2 , (3^n - 1)/2$ of partitions above to S and T are REGARDING the order of S and T.
Is it necessary? (otherwise, the bounds may be improved.)

15 June, 2013 at 5:15 pm

Eytan Paldi

In the fifth line above theorem 2, “we see” may be inserted before “that”.

15 June, 2013 at 5:32 pm

Gergely Harcos

This is my third attempt to improve (8) to

$0\leq G_{k_0,n}(t_1,\ldots,t_n)\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})G_{k_0}(0,0)$

for $g_{k_0}(t):=t^{(1-k_0)/2} J_{k_0-1}(j_{k_0-2}\sqrt{t})$ . This implies my earlier claimed improved value for $\kappa$ , while $\kappa':=0$ follows similarly.

Let us restrict to functions $g:[0,1]\to\mathbb{R}$ supported on some initial segment $[0,\sigma]\subset[0,1]$ such that $g^{(j)}$ is bounded and of sign $(-1)^j$ on $(0,\sigma)$ . Such functions will be called $\sigma$ -appropriate. For $0\leq\tau\leq\sigma$ let us consider the functions

$(R_\tau g)(t):=g(t+\tau)$ and $(D_\tau g)(t):=g(t)-g(t+\tau)$

initially defined on $[0,\sigma-\tau]$ and then extended to be zero on $(\sigma-\tau,1]$ . We observe that $R_\tau g$ and $D_\tau g$ are $(\sigma-\tau)$ -appropriate, and their sum equals $g$ on $[0,\sigma-\tau]$ . As in the main post, for the inner product

$\langle g_1,g_2 \rangle :=\int_0^1 g_1(t)g_2(t)\ t^{k_0-1}dt$

we have $\|R_\tau g\|\leq (1-\tau)_+^{k_0/2}\|g\|$ . Moreover, $0\leq D_\tau g\leq g$ implies $\|D_\tau g\|\leq \|g\|$ .

Let $g_1,g_2:[0,1]\to\mathbb{R}$ be $\sigma$ -appropriate. For any $t_1,\dots,t_n\geq 0$ with sum at most $\sigma$ , let us consider the bilinear form

$\langle g_1,g_2\rangle_{t_1,\dots,t_n} := \sum_{\{1,\ldots,n\} = S \cup T} (-1)^{|S \cap T|} \langle \prod_{i \in S} R_{t_i}g_1,\prod_{i \in T}R_{t_i}g_2 \rangle.$

Then we have

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}=\langle R_{t_n}g_1,g_2 \rangle_{t_1,\dots,t_{n-1}}+\langle g_1,R_{t_n}g_2 \rangle_{t_1,\dots,t_{n-1}} -\langle R_{t_n}g_1,R_{t_n}g_2 \rangle_{t_1,\dots,t_{n-1}}$ .

Noting that $g_1-R_{t_n}g_1$ equals $D_{t_n}g_1$ on the support of $R_{t_n}g_2$ , we infer

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}=\langle R_{t_n}g_1,g_2 \rangle_{t_1,\dots,t_{n-1}}+\langle D_{t_n}g_1,R_{t_n}g_2 \rangle_{t_1,\dots,t_{n-1}}$ .

The point is the we have two terms with signs $+,+$ instead of three terms with signs $+,+,-$ . By induction and the above remarks, we readily establish

$0\leq\langle g_1,g_2\rangle_{t_1,\dots,t_n}\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})\|g_1\|\|g_2\|$ .

Specializing to $g_1=g_2=g_{k_0}$ and $\sigma=1$ yields

$0\leq G_{k_0,n}(t_1,\ldots,t_n)\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})G_{k_0}(0,0)$ .

15 June, 2013 at 7:55 pm

Terence Tao

Dear Gergely,

I think that the assertion that $g_1 - R_{t_n} g_1$ equals $D_{t_n} g_1$ on the support of $R_{t_n} g_2$ is not quite enough to conclude that $\langle g_1, R_{t_n} g_2 \rangle_{t_1,\ldots,t_{n-1}} - \langle R_{t_n} g_1, R_{t_n} g_2 \rangle_{t_1,\ldots,t_{n-1}}$ is equal to $\langle D_{t_n} g_1, R_{t_n} g_2 \rangle_{t_1,\ldots,t_{n-1}}$ except when $n=1$ , because of the non-local nature of the $\langle,\rangle_{t_1,\ldots,t_n}$ bilinear form.

16 June, 2013 at 3:18 am

Gergely Harcos

You are right, I overlooked again. I found a new approach, please have a look at my comment below. Thanks for your patience and checking everything carefully!

16 June, 2013 at 3:15 am

Gergely Harcos

Terry is right, I was wrong again. But here is my fourth attempt to prove the same!

I will use the notation from my previous comment. Let $g_1,g_2:[0,1]\to\mathbb{R}$ be $\sigma$ -appropriate functions, and let
$t_1,\dots,t_n\geq 0$ be arbitrary numbers with sum $t:=\sum_{i=1}^n t_i<\sigma$ . I claim that the function

$\tau\mapsto\langle R_\tau g_1,g_2\rangle_{t_1,\dots,t_n}$ is decreasing on $(0,\sigma-t)$ .

As a simple consequence, we shall have

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}\geq 0$ for $\sum_{i=1}^n t_i<\sigma$ .

We prove the monotonicity claim by induction on $n$ . For $n=0$ the statement follows from the fact that $g_1$ and $g_2$ are nonnegative and decreasing. Now assume the statement for $n-1\geq 0$ in place of $n$ . For $0<\tau_1<\tau_2<\sigma-t$ we obtain, by definition,

$\langle R_{\tau_1} g_1,g_2\rangle_{t_1,\dots,t_n}-\langle R_{\tau_2} g_1,g_2\rangle_{t_1,\dots,t_n}=\int_{\tau_1}^{\tau_2}\langle g_1^{\tau},g_2\rangle_{t_1,\dots,t_n}\ d\tau$ ,

where $g_1^{\tau}:=-R_\tau g_1'$ is $(\sigma-\tau)$ -appropriate. Hence it suffices to show that

$\langle g_1^{\tau},g_2\rangle_{t_1,\dots,t_n}\geq 0$ for $\tau\in(\tau_1,\tau_2)$ .

Renaming $g_1^{\tau}$ to $g_1$ , and $\sigma-\tau$ to $\sigma$ , we have reduced the induction step to the already mentioned consequence

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}\geq 0$ for $\sum_{i=1}^n t_i<\sigma$ .

To see the last inequality, we combine the identity

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}=\langle R_{t_n}g_1,g_2 \rangle_{t_1,\dots,t_{n-1}}+ \langle g_1,R_{t_n}g_2 \rangle_{t_1,\dots,t_{n-1}}-\langle R_{t_n}g_1,R_{t_n}g_2 \rangle_{t_1,\dots,t_{n-1}}$

with the induction hypothesis. We obtain

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}\geq\langle R_{t_n}g_1,g_2 \rangle_{t_1,\dots,t_{n-1}}\geq 0$ ,

and we are done. As a useful consequence, the identity now implies

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}\leq \langle R_{t_n}g_1,g_2 \rangle_{t_1,\dots,t_{n-1}}+\langle g_1,R_{t_n}g_2 \rangle_{t_1,\dots,t_{n-1}}$ .

By induction again and the remarks in my previous comment, we can now readily establish

$0\leq\langle g_1,g_2\rangle_{t_1,\dots,t_n}\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})\|g_1\|\|g_2\|$ .

Specializing to $g_1=g_2=g_{k_0}$ and $\sigma=1$ yields

$0\leq G_{k_0,n}(t_1,\ldots,t_n)\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})G_{k_0}(0,0)$ .

16 June, 2013 at 5:16 am

Gergely Harcos

Actually I am still not happy with the argument. Here are some thoughts that resonate with Terry’s earlier warnings.

1. We need to allow $g_1$ (resp. $g_2$ ) to be $\sigma_1$ -appropriate (resp. $\sigma_2$ -appropriate) with possibly different $\sigma_1,\sigma_2\geq\sigma$ . We have no regularity at $\sigma_1$ and $\sigma_2$ , so we cannot really go beyond the range $t<\min(\sigma_1,\sigma_2)$ by considering higher derivatives. This means that the final conclusion

$0\leq\langle g_1,g_2\rangle_{t_1,\dots,t_n}\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})\|g_1\|\|g_2\|$

is restricted to $\sum_{i=1}^n t_i<1$ . Perhaps some combinatorial ideas can establish the lower bound in general, e.g. by cleverly arranging the terms in $\langle g_1,g_2\rangle_{t_1,\dots,t_n}$ , and then the upper bound follows as well. In fact we would only need the lower bound for $g_1=g_2$ .

2. For similar reasons we cannot really deduce $\langle g_1,g_2\rangle_{t_1,\dots,t_n}\geq 0$ for $t<\sigma$ from the fact that $\tau\mapsto\langle R_\tau g_1,g_2\rangle_{t_1,\dots,t_n}$ is decreasing on $(0,\sigma-t)$ . This can be remedied, however, by adding nonnegativity to the monotonicity statement, and inducting on $n$ for the stronger statement.

16 June, 2013 at 7:43 am

Terence Tao

Perhaps one should focus on the n=2 case for now, as this would generate the lion’s share of the savings even if it does not lead to the most elegant results.

In any event, for the specific example of Bessel functions, we should be able to get some more improvement in kappa from direct calculation of the n=1 terms rather than by upper bounds, but this would require numerical integration of Bessel functions of high order (not too computationally infeasible, but it may require a little more than simply using the off-the-shelf integration command for Maple/SAGE/Mathematica/etc. if one is to be confident about the accuracy of the integral). Although one thing that is working in our favour is that $k_0$ is now dropping to levels (such as 6329) in which accurate numerical computations for the relevant integrals look quite feasible.

16 June, 2013 at 10:07 pm

Gergely Harcos

You are right about $n=2$ , let me post a new comment about this below.

16 June, 2013 at 5:53 am

Eytan Paldi

There is a simpler and better way than using the trick with the (somewhat crude) inequality $|g(t + \tau)| \le |g(t / (1 - \tau))|$ above, the idea is to find the MINIMAL function $K(\tau)$ satisfying

$|g(t + \tau)| \le K(\tau) |g(t)|$ whenever $t, \tau , t + \tau$ are in
$[0, 1]$ , but for a specific $g$ proportional to the Bessel solution!
As it turns out, the solution is implied by the following sub-multiplicativity property for g (proportional to the Bessel solution) normalized to g(0) = 1:

$g(t + \tau) \le g(\tau) g(t)$ , whenever $t, \tau, t + \tau$ are in
$[0, 1]$

Clearly, this property should give simpler and better bounds. (I’ll send the details in some hours.)

16 June, 2013 at 10:09 pm

Gergely Harcos

For $n=1,2$ it is straightforward to generalize the treatment of $G_{k_0-1,1}(t)$ in the post. Let $g_1,g_2:[0,1]\to\mathbb{R}$ be nonnegative, continuous, and decreasing. Then

$\langle g_1,g_2\rangle_{t} = \langle R_{t}g_1,g_2 \rangle + \langle g_1,R_{t}g_2 \rangle - \langle R_{t}g_1,R_{t}g_2 \rangle\geq \langle R_{t}g_1,g_2 \rangle\geq 0$ ,

and

$\langle g_1,g_2\rangle_{t} \leq \langle R_{t}g_1,g_2 \rangle + \langle g_1,R_{t}g_2 \rangle\leq 2(1-t)_+^{k_0/2}\|g_1\|\|g_2\|.$

This implies

$\langle g_1,g_2\rangle_{t_1,t_2}=\langle R_{t_2}g_1,g_2 \rangle_{t_1}+ \langle g_1,R_{t_2}g_2 \rangle_{t_1}-\langle R_{t_2}g_1,R_{t_2}g_2 \rangle_{t_1}$

$\leq 2(1-t_1)_+^{k_0/2}(\|R_{t_2}g_1\|\|g_2\|+\|g_1\|\|R_{t_2}g_2\|)$

$\leq 4(1-t_1)_+^{k_0/2}(1-t_2)_+^{k_0/2}\|g_1\|\|g_2\|$ .

In addition,

$\langle g_1,g_2\rangle_{t_1,t_2}=\langle R_{t_1+t_2}g_1,R_{t_1+t_2}g_2\rangle$

$+\langle R_{t_1+t_2}g_1,(1-R_{t_1})g_2\rangle+\langle (1-R_{t_1})g_1,R_{t_1+t_2}g_2\rangle$

$+\langle (R_{t_1}-R_{t_1+t_2})g_1,R_{t_2}g_2\rangle+\langle R_{t_2}g_1,(R_{t_1}-R_{t_1+t_2})g_2\rangle\geq 0$ .

This shows that

$0\leq G_{k_0,n}(t_1,\ldots,t_n)\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})G_{k_0}(0,0)$

is valid for $n=1,2$ , and the same is true with $k_0-1$ in place of $k_0$ . As a result, in the expression for $\kappa'$ , the term $n=2$ can be omitted, while for $\kappa$ the $n=2$ term can be multiplied by $\frac{2^{n+1}}{3^n+1}=\frac{4}{5}$ .

17 June, 2013 at 4:21 pm

Eytan Paldi

In the third line above (8), it should be trinomial (instead of binomial)

[Depends on how you count it. I used the sum and difference of binomial formulae $3^n = \sum_{i=0}^n 2^{n-i} \binom{n}{i}$ and $1 = \sum_{i=0}^n (-1)^i 2^{n-i} \binom{n}{i}$ to arrive at these conclusions. -T.]

17 June, 2013 at 5:23 pm

Eytan Paldi

Thanks! (I used the equivalent expansions $(1+1+1)^n$ and
$(1-1+1)^n$ )

18 June, 2013 at 9:03 am

Gergely Harcos

I think I proved that for any nonnegative, continuous, and decreasing functions $g_1,g_2:[0,1]\to\mathbb{R}$ , and for any $0\leq t_1,\dots,t_n<1$ ,

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}\geq 0$ .

We use the convention that $g_1,g_2$ are extended to be zero on $(1,\infty)$ , and we borrow notation from our earlier attempt (https://terrytao.wordpress.com/2013/06/11/further-analysis-of-the-truncated-gpy-sieve/#comment-234683). Combining nonnegativity with the recursion identity

$\langle g_1,g_2\rangle_{t_1,\dots,t_n}=\langle R_{t_n}g_1,g_2 \rangle_{*}+\langle g_1,R_{t_n}g_2 \rangle_{*}-\langle R_{t_n}g_1,R_{t_n}g_2 \rangle_{*}$ ,

where * abbreviates $t_1,\dots,t_{n-1}$ , we obtain by induction

$0\leq\langle g_1,g_2\rangle_{t_1,\dots,t_n}\leq 2^n(\prod_{i=1}^n(1-t_i)_+^{k_0/2})\|g_1\|\|g_2\|$ .

This yields Theorem 2 with $\kappa':=0$ and

$\kappa := \sum_{1 \leq n < \frac{1+4\varpi}{4\delta}} \frac{1}{n!} (2k_0\int_{4\delta/(1+4\varpi)}^1 (1-t)^{k_0/2}\ \frac{dt}{t})^n$ .

The main idea of the proof is that $g_1,g_2$ can be approximated arbitrarily well in sup-norm by decreasing step functions, which in turn are nonnegative linear combinations of the characteristic functions $\alpha_\tau:=1_{[0,1-\tau]}$ extended by zero on $(1-\tau,\infty)$ . Hence it suffices to verify

$\langle \alpha_s,\alpha_t\rangle_{t_1,\dots,t_n}\geq 0$ for any $0\leq s\leq t<1$ .

We work with the measure $x^{k_0-1}dx$ supported on $[0,1]$ , hence we have the scaling property

$\langle \alpha_s,\alpha_t\rangle_{t_1,\dots,t_n}=(1-s)^{k_0}\langle \alpha_0,\alpha_{\frac{t-s}{1-s}}\rangle_{t_1,\dots,t_n}$ .

That is, we can restrict to $s=0$ without loss of generality, and it suffices to show

$\langle \alpha_0,\alpha_t\rangle_{t_1,\dots,t_n}\geq 0$ for any $0\leq t<1$ .

We shall prove more, namely that the left hand side decreases in $t$ . This implies nonnegativity, as the left hand side approaches zero for $t\to 1-$ .

With the convention that $\alpha_\tau=0$ for $\tau\geq 1$ , the recursion identity expresses the left hand side as

$\langle \alpha_{t_n},\alpha_t \rangle_{*}+\langle \alpha_0,\alpha_{t+t_n} \rangle_{*}-\langle \alpha_{t_n},\alpha_{t+t_n} \rangle_{*}$ .

By the scaling property, we can rewrite this as

$(1-t_n)^{k_0}\langle\alpha_0,\alpha_{\frac{t-t_n}{1-t_n}}\rangle_{*}+\langle\alpha_0,\alpha_{t+t_n}\rangle_{*} -(1-t_n)^{k_0}\langle\alpha_0,\alpha_{\frac{t}{1-t_n}}\rangle_{*}$ for $t_n\leq t$ ,

$(1-t)^{k_0}\langle\alpha_0,\alpha_{\frac{t_n-t}{1-t}}\rangle_{*}+\langle\alpha_0,\alpha_{t+t_n}\rangle_{*} -(1-t_n)^{k_0}\langle\alpha_0,\alpha_{\frac{t}{1-t_n}}\rangle_{*}$ for $t\leq t_n$ .

Based on these scaled recursion formulae, we shall prove the following claim by induction on $n$ : for any fixed $t_1,\dots,t_n$ , there is a finite set $S\subset[0,1]$ such that on any interval $I\subset[0,1]\setminus S$ the function $f(t):=\langle\alpha_0,\alpha_t\rangle_{t_1,\dots,t_n}$ is of the form $a_I(1-t)^{k_0}+b_I$ with nonnegative constants $a_I,b_I\geq 0$ . The claim implies that $f(t)$ decreases on $[0,1]\setminus S$ , hence in fact on $[0,1]$ by its continuity in $t$ .

Now we show the claim by induction on $n$ . For $n=0$ the statement follows from $\langle\alpha_0,\alpha_t\rangle=\frac{1}{k_0}(1-t)_+^{k_0}$ . Let us assume the statement for $n-1\geq 0$ in place of $n$ . Let us fix $t_1,\dots,t_n$ , and consider the exceptional set $S$ corresponding to $t_1,\dots,t_{n-1}$ . Let $\tilde S\subset[0,1]$ be the set of points $t\in[0,1]$ such that any of the following expressions lies in $S$ : $\frac{t-t_n}{1-t_n}$ , $\frac{t_n-t}{1-t}$ , $t+t_n$ , $\frac{t}{1-t_n}$ . Add $t_n$ also to $\tilde S$ . Now let $I\subset[0,1]\setminus \tilde S$ be any interval. By the scaled recursion formulae and the induction hypothesis, there are nonnegative constants $a_I,b_I\geq 0$ , such that $f(t):=\langle\alpha_0,\alpha_t\rangle_{t_1,\dots,t_n}$ takes one of the following two forms on all of $I$ :

$(1-t_n)^{k_0}(a_I(1-\frac{t-t_n}{1-t_n})^{k_0}+b_I)+(a_I(1-t-t_n)^{k_0}+b_I)$

$-(1-t_n)^{k_0}(a_I(1-\frac{t}{1-t_n})^{k_0}+b_I)$ ,

$(1-t)^{k_0}(a_I(1-\frac{t_n-t}{1-t})^{k_0}+b_I)+(a_I(1-t-t_n)^{k_0}+b_I)$

$-(1-t_n)^{k_0}(a_I(1-\frac{t}{1-t_n})^{k_0}+b_I)$ .

The first expression simplifies to $a_I(1-t)^{k_0}+b_I$ , while the second simplifies to

$b_I(1-t)^{k_0}+a_I(1-t_n)^{k_0}+(1-(1-t_n)^{k_0})b_I$ .

In both cases $f(t)$ is of the form $\tilde a_I(1-t)^{k_0}+\tilde b_I$ on $I$ , where $\tilde a_I,\tilde b_I\geq 0$ are nonnegative constants, hence we are done.

18 June, 2013 at 9:17 am

Gergely Harcos

Actually this proof gives the stronger statement that I anticipated before:

$\tau\mapsto\langle R_\tau g_1,g_2\rangle_{t_1,\dots,t_n}$ decreases on $[0,1]$ .

18 June, 2013 at 9:52 am

Gergely Harcos

Actually, I erred again, in the last step: I proceeded as if each of $\frac{t-t_n}{1-t_n}$ , $\frac{t_n-t}{1-t}$ , $t+t_n$ , $\frac{t}{1-t_n}$ mapped $I$ into the same interval lying in $[0,1]\setminus S$ . This is clearly false. Nevertheless, I believe the ideas in this approach are good ones. One needs to understand $\langle \alpha_0,\alpha_t\rangle_{t_1,\dots,t_n}$ explicitly enough to conclude that it is nonnegative. I believe this is doable (although not really important for the project).

19 June, 2013 at 7:09 am

Gergely Harcos

The statement I tried to prove here is false, see https://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/#comment-235214

18 June, 2013 at 6:19 pm

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

[…] post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, […]

18 June, 2013 at 6:40 pm

Terence Tao

Time to close this thread and move on to the next one:

https://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/

	MarcNg on 254A, Notes 9 – second m…
	Emanuele Rodolà on Eigenvectors from eigenvalues
	Terence Tao on Eigenvectors from eigenvalues
	Bill Province on Eigenvectors from eigenvalues
	Timothy Chow on Eigenvectors from eigenvalues
	isaac mor on Almost all Collatz orbits atta…
	Raphael on Eigenvectors from eigenvalues
	J. M. on Eigenvectors from eigenvalues
	Khot,Minzer,Safra on… on (Ben Green) The Polynomial Fre…
	Bill Province on Eigenvectors from eigenvalues
	Raphael on Eigenvectors from eigenvalues
	Chris Godsil on Eigenvectors from eigenvalues
	Terence Tao on Eigenvectors from eigenvalues
	Terence Tao on Eigenvectors from eigenvalues
	Arturo Portnoy on Eigenvectors from eigenvalues

Further analysis of the truncated GPY sieve

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

91 comments

Leave a Reply Cancel reply

For commenters

Further analysis of the truncated GPY sieve

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

91 comments

Leave a Reply Cancel reply

For commenters