Distribution of primes in smooth moduli

From Polymath1Wiki

(Difference between revisions)
Jump to: navigation, search
(Congruence class systems)
(Combinations)
Line 302: Line 302:
|Level 1
|Level 1
|Level 1
|Level 1
-
|<math>207\varpi + 43\delta < 1/4 </math>
+
|<math>828\varpi + 172\delta < 1 </math>
|[http://terrytao.wordpress.com/2013/06/10/a-combinatorial-subset-sum-problem-associated-with-bounded-prime-gaps/ details]  
|[http://terrytao.wordpress.com/2013/06/10/a-combinatorial-subset-sum-problem-associated-with-bounded-prime-gaps/ details]  
|-
|-
Line 308: Line 308:
|Level 1
|Level 1
|Level 2
|Level 2
-
|<math>87\varpi + 17\delta < 1/4 </math>
+
|<math>348\varpi + 68\delta < 1 </math>
|[http://terrytao.wordpress.com/2013/06/14/estimation-of-the-type-iii-sums/#comment-234670 details]
|[http://terrytao.wordpress.com/2013/06/14/estimation-of-the-type-iii-sums/#comment-234670 details]
|-
|-
Line 356: Line 356:
|Level 1a
|Level 1a
|Level 3
|Level 3
-
|<math>788 \varpi+195 \delta < 7</math>
+
|<math>112 \frac{4}{7} \varpi+27 \frac{6}{7} \delta < 1</math>
| [http://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236387 details]
| [http://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236387 details]
|-
|-
Line 362: Line 362:
|Level 1c
|Level 1c
|Level 4
|Level 4
-
|<math>18\varpi+5\delta < \frac{1}{6}</math>
+
|<math>108\varpi+30\delta < 1</math>
| [https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236502 details]
| [https://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/#comment-236502 details]
| Type II and Type III estimates are now so strong that the bottleneck is the border between Type I and <math>\sigma>1/10</math>.
| Type II and Type III estimates are now so strong that the bottleneck is the border between Type I and <math>\sigma>1/10</math>.

Revision as of 02:53, 28 June 2013

A key input to Zhang's proof that bounded gaps occur infinitely often is a distribution result on primes in smooth moduli, which we have called MPZ[\varpi,\delta] (and later strengthened to MPZ'[\varpi,\delta]. These estimates are obtained as a combination of three other estimates), which we will call Type_I[\varpi,\delta,\sigma], Type_{II}[\varpi,\delta], and Type_{III}[\varpi,\delta,\sigma].

Contents

Definitions

Asymptotic notation

x is a parameter going off to infinity, and all quantities may depend on x unless explicitly declared to be "fixed". The asymptotic notation O(), o(), \ll is then defined relative to this parameter. A quantity q is said to be of polynomial size if one has q = O(xO(1)), and bounded if q = O(1). We also write X \lessapprox Y for X \ll x^{o(1)} Y, and \displaystyle X \sim Y for X \ll Y \ll X.

Coefficient sequences

We need a fixed quantity A0 > 0.

A coefficient sequence is a finitely supported sequence \alpha: {\mathbf N} \rightarrow {\mathbf R} that obeys the bounds

\displaystyle  |\alpha(n)| \ll \tau^{O(1)}(n) \log^{O(1)}(x)
  • If α is a coefficient sequence and a\ (q) = a \hbox{ mod } q is a primitive residue class, the (signed) discrepancy \Delta(\alpha; a\ (q)) of α 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).
  • A coefficient sequence α 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].
  • A coefficient sequence α 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

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

  • A coefficient sequence α at scale N is said to be smooth if it takes the form α(n) = ψ(n / N) for some smooth function \psi: {\mathbf R} \rightarrow {\mathbf 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 )

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

Congruence class systems

Let I \subset {\mathbf R}, and let {\mathcal S}_I denote the square-free numbers whose prime factors lie in I.

  • A singleton congruence class system on I is a collection {\mathcal C} = (\{a_q\})_{q \in {\mathcal S}_I} of primitive residue classes a_q \in ({\mathbf Z}/q{\mathbf Z})^\times for each </math>q \in {\mathcal S}_I</math>, obeying the Chinese remainder theorem property
\displaystyle  a_{qr}\ (qr) = (a_q\ (q)) \cap (a_r\ (r))

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

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

obeys the estimate

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

for any fixed C > 1 and any congruence class a\ (r) with r \in {\mathcal S}_I. Here τ is the divisor function. (The original definition here did not include the τ(n)C factor, but this turns out to be convenient for the Level 1c Type II estimates, and causes no additional difficulty in verifying this condition in applications.)

Smooth and densely divisible numbers

A natural number n is said to be y-smooth if all of its prime factors are less than or equal to y. We say that n is y-densely divisible if, for every 1 \leq R \leq n, one can find a factor of n in the interval [y − 1R,R]. Note that y-smooth numbers are automatically y-densely divisible, but the converse is not true in general.

MPZ

Let 0 < \varpi < 1/4 and 0 < \delta < \varpi + 1/4 be fixed. Let Λ denote the von Mangoldt function.

  • We say that the estimate MPZ[\varpi,\delta] holds if one has the estimate
\displaystyle  \sum_{q \in {\mathcal S}_I: q< x^{1/2+2\varpi}} |\Delta(\Lambda 1_{[x,2x]}; a_q)| \ll x \log^{-A} x

for any fixed A > 0, any I \subset [1,x^\delta], and any congruence class system  (\{a_q\})_{q \in {\mathcal S}_I} of controlled multiplicity.

  • We say that the estimate MPZ'[\varpi,\delta] holds if one has the estimate
\displaystyle  \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}: q< x^{1/2+2\varpi}} |\Delta(\Lambda 1_{[x,2x]}; a_q)| \ll x \log^{-A} x

for any fixed A > 0, any I \subset {\mathbf R}, and any congruence class system  (\{a_q\})_{q \in {\mathcal S}_I} of controlled multiplicity.

Type I, Type II, and Type III

Let 0 < \varpi < 1/4, 0 < \delta < 1/4+\varpi, and 0 < σ < 1 / 2 be fixed.

  • We say that Type_I[\varpi,\delta,\sigma] holds if, whenever M,N are quantities with
\displaystyle MN \sim x

and

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

or equivalently

\displaystyle x^{1/2+2\varpi+c} \ll M \ll x^{1/2+\sigma}

for some fixed c > 0, and α,β are coefficient sequences at scale M,N respectively with β obeying a Siegel-Walfisz theorem, I \subset [1,x^\delta], and (\{a_q\})_{q \in {\mathcal S}_I} is a congruence class system of controlled multiplicity, then one has

\sum_{q \in {\mathcal S}_I: q < x^{1/2+2\varpi}} |\Delta( \alpha * \beta; a_q\ (q))| \leq x \log^{-A} x

for all fixed A > 0.

  • We say that Type_{II}[\varpi,\delta] holds if, whenever M,N are quantities with
\displaystyle MN \sim x

and

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

or equivalently

\displaystyle x^{1/2} \ll M \ll x^{1/2+2\varpi+c}

for some sufficiently small fixed c > 0, and α,β are coefficient sequences at scale M,N respectively with β obeying a Siegel-Walfisz theorem, I \subset [1,x^\delta], and (\{a_q\})_{q \in {\mathcal S}_I} is a congruence class system of controlled multiplicity, then one has

\sum_{q \in {\mathcal S}_I: q < x^{1/2+2\varpi}} |\Delta( \alpha * \beta; a_q\ (q))| \leq x \log^{-A} x

for all fixed A > 0.

  • We say that Type_{III}[\varpi,\delta,\sigma] holds if, whenever M,N1,N2,N3 are quantities with
\displaystyle MN \sim x
\displaystyle N_1N_2, N_2 N_3, N_1 N_3 \gg x^{1/2 + \sigma}
\displaystyle x^{2\sigma} \ll N_1,N_2,N_3 \ll x^{1/2-\sigma},

α,ψ123 are coefficient sequences at scale M,N1,N2,N3 respectively with ψ123 smooth, I \subset [1,x^\delta], and (\{a_q\})_{q \in {\mathcal S}_I} is a congruence class system of controlled multiplicity, then one has

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

for all fixed A > 0.

  • We define Type'_I[\varpi,\delta,\sigma], Type'_{II}[\varpi,\delta], Type_{III}[\varpi,\delta,\sigma] analogously to Type_I[\varpi,\delta,\sigma], Type_{II}[\varpi,\delta], Type_{III}[\varpi,\delta,\sigma] but with the hypothesis I \subset [1,x^\delta] replaced with I \subset \mathbf{R}, and {\mathcal S}_I replaced with {\mathcal S}_I \cap {\mathcal D}_{x^\delta}. These estimates are slightly stronger than their unprimed counterparts.

There should also be a second "double-primed" variant Type''_I[\varpi,\delta,\sigma], Type''_{II}[\varpi,\delta], Type''_{III}[\varpi,\delta,\sigma] of these estimates, intermediate in strength between the primed and unprimed estimates, in which one assumes a suitable "double dense divisibility" hypothesis, which has not yet been determined precisely.

Note: thus far in the Type III analysis, the controlled multiplicity hypothesis has yet to be used.

The combinatorial lemma

Combinatorial lemma Let 0 < \varpi < 1/4, 0 < \delta < 1/4 + \varpi, and 1 / 10 < σ < 1 / 2 be fixed.
  • If Type_I[\varpi,\delta,\sigma], Type_{II}[\varpi,\delta], and Type_{III}[\varpi,\delta,\sigma] all hold, then MPZ[\varpi,\delta] holds.
  • Similarly, if Type'_I[\varpi,\delta,\sigma], Type'_{II}[\varpi,\delta], and Type'_{III}[\varpi,\delta,\sigma] all hold, then MPZ'[\varpi,\delta] holds.

This lemma is (somewhat implicitly) proven here. It reduces the verification of MPZ[\varpi,\delta] and MPZ'[\varpi,\delta] to a comparison of the best available Type I, Type II, and Type III estimates, as well as the constraint σ > 1 / 10.

Type I estimates

In all of the estimates below, 0 < \varpi < 1/4, 0 < \delta < 1/4 + \varpi, and σ > 0 are fixed.

Level 1

Type I-1 We have Type'_I[\varpi,\delta,\sigma] (and hence Type_I[\varpi,\delta,\sigma]) whenever
\displaystyle 11\varpi +3\delta + 2 \sigma < \frac{1}{4}.

This result is implicitly proven here. (There, only Type_I[\varpi,\delta,\sigma] is proven, but the method extends without difficulty to Type'_I[\varpi,\delta,\sigma].) It uses the method of Zhang, and is ultimately based on exponential sums for incomplete Kloosterman sums on smooth moduli obtained via completion of sums.

Level 2

Type I-2 We have Type'_I[\varpi,\delta,\sigma] (and hence Type_I[\varpi,\delta,\sigma]) whenever
\displaystyle 17\varpi +4\delta + \sigma < \frac{1}{4}
and
\displaystyle 20\varpi +6\delta + 3\sigma < \frac{1}{2}
and
\displaystyle 32\varpi +9\delta + \sigma < \frac{1}{2}.

This estimate is implicitly proven here. It improves upon the Level 1 estimate by using the q-van der Corput A-process in the d2 direction.

Level 3

Type I-3 We have Type'_I[\varpi,\delta,\sigma] (and hence Type_I[\varpi,\delta,\sigma]) whenever
\displaystyle 54\varpi + 15 \delta + 5 \sigma < 1.

This estimate is established here (it was previously tentatively established in this comment with an additional condition 32 \varpi + 9 \delta + \sigma < 1/2, which can now be dropped, thanks to an improved control on a secondary error term in the exponential sum estimates). It improves upon the Level 2 estimate by taking advantage of dense divisibility to optimise the direction of averaging.

Level 4

By iterating the q-van der Corput A-process, one should be able to obtain Type''_I[\varpi,\delta,\sigma] assuming a constraint of the form

\displaystyle 40\varpi + C \delta + 4 \sigma < 1

for some constant C that has not yet been determined (in part because we have not yet decided what "doubly densely divisible" means); see this comment.

Level 5

Further improvement to the (still sketchy) Level 4 estimate should be obtainable by taking advantage of averaging in auxiliary "h" parameters in order to reduce the contribution of the diagonal terms.

Type II estimates

In all of the estimates below, 0 < \varpi < 1/4 and 0 < \delta < 1/4 + \varpi are fixed.

Level 1

Type II-1 We have Type'_{II}[\varpi,\delta] (and hence Type_{II}[\varpi,\delta]) whenever
\displaystyle 58\varpi + 10\delta < \frac{1}{2}.

This estimate is implicitly proven here. (There, only Type_I[\varpi,\delta,\sigma] is proven, but the method extends without difficulty to Type'_I[\varpi,\delta,\sigma].) It uses the method of Zhang, and is ultimately based on exponential sums for incomplete Kloosterman sums on smooth moduli obtained via completion of sums.

Level 1a

Type II-1a We have Type'_{II}[\varpi,\delta] (and hence Type_{II}[\varpi,\delta]) whenever
\displaystyle 48\varpi + 7\delta < \frac{1}{2}.

This estimate is implicitly proven here. It is a slight refinement of the Level 1 estimate based on a more careful inspection of the error terms in the completion of sums method.

Level 1b

Type II-1b We have Type'_{II}[\varpi,\delta] (and hence Type_{II}[\varpi,\delta]) whenever
\displaystyle 38\varpi + 7\delta < \frac{1}{2}.

This refinement of the Level 1a estimate came from realising that in the Type II case, the R parameter can be selected to lie in the range [x^{1/2-2\varpi-\delta-\varepsilon}, x^{1/2-2\varpi-\varepsilon}] rather than [x^{-2\varpi-\delta-\varepsilon} N, x^{-2\varpi-\varepsilon} N]. See this comment for details.

Level 1c

Type II-1c We have Type'_{II}[\varpi,\delta] (and hence Type_{II}[\varpi,\delta]) whenever
\displaystyle 34\varpi + 7\delta < \frac{1}{2}.

This further refinement of the Level 1b estimate came from realising that R can in fact range in [x^{-\delta-\varepsilon} N, x^{-\varepsilon} N] if one strengthens the controlled multiplicity hypothesis slightly; see this comment for details.

Level 2

In analogy with the Type I-2 estimates, one could hope to improve the Type II estimates by using the q-van der Corput process in the d2 direction. Interestingly, however, it appears that the Type II numerology lies outside of the range in which the van der Corput process is beneficial (at least if one only applies it once), so the Level 2 estimate looks to be inferior to the Level 1b estimate.

Level 3

In analogy with the Type I-3 estimates, one should be able to improve the Type II estimates by using the q-van der Corput process in an optimised direction. As with Level 2 estimates though, it appears that Level 3 estimates are inferior to the Level 1b estimate.

Level 4

In analogy with the Type I-4 estimates, one should be able to improve the Type II estimates by iterating the q-van der Corput A-process.

Level 5

In analogy with the Type I-5 estimates, one should be able to improve the Type II estimates by taking advantage of averaging in the h parameters.

Type III estimates

In all of the estimates below, 0 < \varpi < 1/4, 0 < \delta < 1/4 + \varpi, and σ > 0 are fixed.

Level 1

Type III-1 We have Type'_{III}[\varpi,\delta,\sigma] (and hence Type_{III}[\varpi,\delta,\sigma]) whenever
\displaystyle \frac{13}{2} (\frac{1}{2} + \sigma) > 8 (\frac{1}{2} + 2 \varpi) + \delta

This estimate is implicitly proven here. (There, only Type_{III}[\varpi,\delta,\sigma] is proven, but the method extends without difficulty to Type'_{III}[\varpi,\delta,\sigma].) It uses the method of Zhang, using Weyl differencing and not exploiting the averaging in the α or q parameters. The constraint can also be written as a lower bound on σ:

\displaystyle \sigma > \frac{3}{26} + \frac{32}{13} \varpi + \frac{2}{13} \delta.

Level 2

Type III-2 We have Type'_{III}[\varpi,\delta,\sigma] (and hence Type_{III}[\varpi,\delta,\sigma]) whenever
\displaystyle 1 + 5 (\frac{1}{2} + \sigma) > 8 (\frac{1}{2} + 2 \varpi) + \delta

This estimate is implicitly proven here. It is a refinement of the Level 1 estimate that takes advantage of the α averaging. The constraint may also be written as a lower bound on σ:

\displaystyle \sigma > \frac{1}{10} + \frac{16}{5} \varpi + \frac{1}{5} \delta.

Level 3

Type III-3 We have Type'_{III}[\varpi,\delta,\sigma] (and hence Type_{III}[\varpi,\delta,\sigma]) whenever
\displaystyle \frac{3}{2} (\frac{1}{2} + \sigma) > \frac{7}{4} (\frac{1}{2} + 2 \varpi) + \frac{3}{8} \delta .

This estimate is proven in this comment. It uses the newer method of Fouvry, Kowalski, Michel, and Nelson that avoids Weyl differencing. The constraint may also be written as a lower bound on σ:

\displaystyle \sigma > \frac{1}{12} + \frac{7}{3} \varpi + \frac{1}{4} \delta.

Level 4

Type III-4 We have Type'_{III}[\varpi,\delta,\sigma] (and hence Type_{III}[\varpi,\delta,\sigma]) whenever
\displaystyle \frac{1}{4} + \frac{3}{4} \frac{3}{2} (\frac{1}{2} + \sigma) > \frac{7}{4} (\frac{1}{2} + 2 \varpi) + \frac{1}{4} \delta .

This estimate is proven in this comment. It modifies the Level 3 argument by exploiting averaging in the α parameter (this was suggested already by Fouvry, Kowalski, Michel, and Nelson).The constraint may also be written as a lower bound on σ:

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

Level 5

One may also hope to improve upon Level 4 estimates by exploiting Ramanujan sum cancellation (as Zhang did in his Level 1 argument).

Combinations

By combining a Type I estimate, a Type II estimate, and a Type III estimate together one can get estimates of the form MPZ[\varpi,\delta] or MPZ[\varpi',\delta'] for \varpi,\delta small enough by using the combinatorial lemma. Here are the combinations that have been arisen so far in the Polymath8 project:

Type I Type II Type III Result Details Notes
Level 1 Level 1 Level 1 828\varpi + 172\delta < 1 details
Level 1 Level 1 Level 2 348\varpi + 68\delta < 1 details
Level 2 Level 1a Level 1 178\varpi + 52\delta < 1 details
Level 2 Level 1a Level 2 148\varpi + 33\delta < 1 details
Level 3? Level 1a Level 2 140 \varpi + 32\delta < 1? details
Level 4? Level 1a Level 1 96\varpi + C \delta < 1? details
Level 4? Level 2? Level 1 88\varpi + C \delta < 1? details
Level 4? Level 2? Level 2 74\varpi + C \delta < 1? details
Level 2 Level 1a Level 3 116\varpi + 22.5 \delta < 1 details refinement
Level 3 Level 1a Level 3 112 \frac{4}{7} \varpi+27 \frac{6}{7} \delta < 1 details
Level 3 Level 1c Level 4 108\varpi+30\delta < 1 details Type II and Type III estimates are now so strong that the bottleneck is the border between Type I and σ > 1 / 10.

For simplicity, only the constraint that is relevant for near-maximal values of \varpi is shown.

Here is some Maple code for finding the constraints coming from a certain set of inequalities (e.g. Type I level 3, Type II level 1c, and Type III level 4). To reduce the complexity of the output, one can introduce an artificial cutoff of, say, \varpi > 1/200, in the base constraints to restrict attention to the regime of large values of \varpi.

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