Polymath Wiki - User contributions [en]

Selberg sieve variational problem

2014-10-24T03:30:22Z

WikiSysop:

Let <math>M_k</math> be the quantity

:<math>\displaystyle M_k := \sup_F \frac{\sum_{m=1}^k J_k^{(m)}(F)}{I_k(F)}</math>
where <math>F</math> ranges over square-integrable functions on the simplex
:<math>\displaystyle {\mathcal R}_k := \{ (t_1,\ldots,t_k) \in [0,+\infty)^k: t_1+\ldots+t_k \leq 1 \}</math>
with <math>I_k, J_k^{(m)}</math> being the quadratic forms
:<math>\displaystyle I_k(F) := \int_{{\mathcal R}_k} F(t_1,\ldots,t_k)^2\ dt_1 \ldots dt_k</math>
and
:<math>\displaystyle J_k^{(m)}(F) := \int_{{\mathcal R}_{k-1}} (\int_0^{1-\sum_{i \neq m} t_i} F(t_1,\ldots,t_k)\ dt_m)^2 dt_1 \ldots dt_{m-1} dt_{m+1} \ldots dt_k.</math>

It is known that <math>DHL[k,m+1]</math> holds whenever <math>EH[\theta]</math> holds and <math>M_k > \frac{2m}{\theta}</math>. Thus for instance, <math>M_k > 2</math> implies <math>DHL[k,2]</math> on the Elliott-Halberstam conjecture, and <math>M_k>4</math> implies <math>DHL[k,2]</math> unconditionally.

== Upper bounds ==

We have the upper bound
:<math>\displaystyle M_k \leq \frac{k}{k-1} \log k</math> (1)
that is proven as follows.

The key estimate is
:<math> \displaystyle \int_0^{1-t_2-\ldots-t_k} F(t_1,\ldots,t_k)\ dt_1)^2 \leq \frac{\log k}{k-1} \int_0^{1-t_2-\ldots-t_k} F(t_1,\ldots,t_k)^2 (1 - t_1-\ldots-t_k+ kt_1)\ dt_1.</math>. (2)

Assuming this estimate, we may integrate in <math>t_2,\ldots,t_k</math> to conclude that
:<math>\displaystyle J_k^{(1)}(F) \leq \frac{\log k}{k-1} \int F^2 (1-t_1-\ldots-t_k+kt_1)\ dt_1 \ldots dt_k</math>
which symmetrises to
:<math>\sum_{m=1}^k J_k^{(m)}(F) \leq k \frac{\log k}{k-1} \int F^2\ dt_1 \ldots dt_k</math>
giving the desired upper bound (1).

It remains to prove (2). By Cauchy-Schwarz, it suffices to show that
:<math>\displaystyle \int_0^{1-t_2-\ldots-t_k} \frac{dt_1}{1 - t_1-\ldots-t_k+ kt_1} \leq \frac{\log k}{k-1}.</math>
But writing <math>s = t_2+\ldots+t_k</math>, the left-hand side evaluates to
:<math>\frac{1}{k-1} (\log k(1-s) - \log (1-s) ) = \frac{\log k}{k-1}</math>
as required.

== Lower bounds ==

We will need some parameters <math>c, T, \tau > 0</math> and <math>a > 1</math> to be chosen later (in practice we take c close to <math>1/\log k</math>, T a small multiple of c, and <math>\tau</math> a small multiple of c/k.

For any symmetric function F on the simplex <math>{\mathcal R}_k</math>, one has

:<math>J_k^{(1)}(F) \leq \frac{M_k}{k} I_k(F)</math>

and so by scaling, if F is a symmetric function on the dilated simplex <math>r \cdot {\mathcal R}_k</math>, one has

:<math>J_k^{(1)}(F) \leq \frac{r M_k}{k} I_k(F)</math>

after adjusting the definition of the functionals <math>I_k, J_k^{(1)}</math> suitably for this rescaled simplex.

Now let us apply this inequality r in the interval <math>[1,1+\tau]</math> and to truncated tensor product functions

:<math>F(t_1,\ldots,t_k) = 1_{t_1+\ldots+t_k\leq r} \prod_{i=1}^k m_2^{-1/2} g(t_i)</math>

for some bounded measurable <math>g: [0,T] \to {\mathbf R}</math>, not identically zero, with <math>m_2 := \int_0^T g(t)^2\ dt</math>. We have the probabilistic interpretations

:<math>J_k^{(1)}(F) := m_2^{-1} {\mathbf E} ( \int_{[0, r - S_{k-1}]} g(t)\ dt)^2</math>

and

:<math>I(F) := m_2^{-1} {\mathbf E} \int_{[0,r - S_{k-1}]} g(t)^2\ dt</math>
:<math> = {\mathbf P} (S_k \leq r)</math>

where <math>S_{k-1} := X_1 + \ldots X_{k-1}</math>, <math>S_k := X_1 + \ldots + X_k</math> and <math>X_1,\ldots,X_k</math> are iid random variables in [0,T] with law <math>m_2^{-1} g(t)^2\ dt</math>, and we adopt the convention that <math>\displaystyle \int_{[a,b]} f</math> vanishes when <math>b < a</math>. We thus have

:<math> {\mathbf E} ( \int_{[0, r - S_{k-1}]} g(t)\ dt)^2 \leq \frac{r M_k}{k} m_2 {\mathbf P} ( S_k \leq r ) </math> (*)

for any r.

We now introduce the random function <math>h = h_r</math> by

:<math> h(t) := \frac{1}{r - S_{k-1} + (k-1) t} 1_{S_{k-1} < r}.</math>

Observe that if <math>S_{k-1} < r</math>, then

:<math> \int_{[0, r-S_{k-1}]} h(t)\ dt = \frac{\log k}{k-1}</math>

and hence by the Legendre identity

:<math>( \int_{[0, r - S_{k-1}]} g(t)\ dt)^2 = \frac{\log k}{k-1} \int_{[0, r - S_{k-1}]} \frac{g(t)^2}{h(t)}\ dt - \frac{1}{2} \int_{[0,r-S_{k-1}]} \int_{[0,r-S_{k-1}]} \frac{(g(s) h(t)-g(t) h(s))^2}{h(s) h(t)}\ ds dt.</math>

We also note that (using the iid nature of the <math>X_i</math> to symmetrise)

:<math> {\mathbf E} \int_{[0, r - S_{k-1}]} g(t)^2/h(t)\ dt = m_2 {\mathbf E} 1_{S_k \leq r} / h( X_k ) </math>
:<math> = m_2 {\mathbf E} 1_{S_k \leq r} (1 - X_1 - \ldots - X_k + k X_k ) </math>
:<math> = m_2 {\mathbf E} 1_{S_k \leq r} </math>
:<math> = m_2 {\mathbf P}( S_k \leq r ).</math>

Inserting these bounds into (*) and rearranging, we conclude that

:<math> r \Delta_k {\mathbf P} ( S_k \leq r ) \leq \frac{k}{2m_2} {\mathbf E} \int_{[0,r-S_{k-1}]} \int_{[0,r-S_{k-1}]} \frac{(g(s) h(t)-g(t) h(s))^2}{h(s) h(t)}\ ds dt</math>

where <math>\Delta_k := \frac{k}{k-1} \log k - M_k</math> is the defect from the upper bound. Splitting the integrand into regions where s or t is larger than or less than T, we obtain

:<math> r \Delta_k {\mathbf P} ( S_k \leq r ) \leq Y_1 + Y_2</math>

where

:<math>Y_1 := \frac{k}{m_2} {\mathbf E} \int_{[0,T]} \int_{[T,r-S_{k-1}]} \frac{g(t)^2}{h(t)} h(s)\ ds dt</math>

and

:<math>Y_2 := \frac{k}{2 m_2} {\mathbf E} \int_{[0,\min(r-S_{k-1},T)]} \int_{[0,\min(r-S_{k-1},T)]} \frac{(g(s) h(t)-g(t) h(s))^2}{h(s) h(t)}\ ds dt.</math>

We now focus on <math>Y_1</math>. It is only non-zero when <math>S_{k-1} \leq r-T</math>. Bounding <math>h(s) \leq \frac{1}{(k-1)s}</math>, we see that

:<math>Y_1 \leq \frac{k}{(k-1) m_2} {\mathbf E} \int_0^T \frac{g(t)^2}{h(t)}\ dt \times \log_+ \frac{r-S_{k-1}}{T}</math>

where <math>\log_+(x)</math> is equal to <math>\log x</math> when <math>x \geq 1</math> and zero otherwise. We can rewrite this as

:<math>Y_1 \leq \frac{k}{k-1} {\mathbf E} 1_{S_k \leq r} \frac{1}{h(X_k)} \log_+ \frac{r-S_{k-1}}{T}.</math>

We write <math>\frac{1}{h(X_k)} = r-S_k + kX_k</math> and <math>\frac{r-S_{k-1}}{T} = \frac{r-S_k}{T} + \frac{X_k}{T}</math>. Using the bound <math>\log_+(x+y) \leq \log_+(x) + \log_+(1+y)</math> we have

<math>\log_+ \frac{r-S_{k-1}}{T} \leq \log_+ \frac{r-S_{k}}{T} + \log(1 + \frac{X_k}{T})</math>

and thus (bounding <math>\log(1+\frac{X_k}{T}) \leq \frac{X_k}{T}</math>).

:<math>Y_1 \leq \frac{k}{k-1} {\mathbf E} (r-S_k + kX_k) \log_+ \frac{r-S_{k}}{T} + (r-S_k)_+ \frac{X_k}{T} + k X_k \log(1+\frac{X_k}{T})</math>.

Symmetrising, we conclude that

:<math>Y_1 \leq \frac{k}{k-1} (Z_1 + Z_2 + Z_3)</math>

where

:<math>Z_1 := {\mathbf E} r \log_+ \frac{r-S_{k}}{T}</math>

:<math>Z_2 := {\mathbf E} (r-S_k)_+ \frac{S_k}{kT}</math>

:<math>Z_3 := m_2^{-1} \int_0^T kt \log(1 + \frac{t}{T}) g(t)^2\ dt.</math>

For <math>Z_2</math>, which is a tiny term, we use the crude bound

:<math>Z_2 \leq \frac{r^2}{4kT}.</math>

For <math>Z_1</math>, we use the bound

:<math>\log_+ x \leq \frac{(x+2a\log a - a)^2}{4a^2 \log a}</math>

valid for any <math>a>1</math>, which can be verified because the LHS is concave for <math>x \geq 1</math>, while the RHS is convex and is tangent to the LHS as x=a. We then have

:<math>\log_+ \frac{r-S_{k}}{T} \leq \frac{(r-S_k+2aT\log a-aT)^2}{4a^2 T^2\log a}</math>

and thus

:<math>Z_1 \leq r (\frac{(r-k\mu+2aT\log a-aT)^2 + k \sigma^2}{4a^2 T^2 \log a} )</math>

where

:<math> \mu := m_2^{-1} \int_0^T t g(t)^2\ dt </math>
:<math> \sigma^2 := m_2^{-1} \int_0^T t^2 g(t)^2\ dt - \mu^2. </math>

A good choice for <math>a=a[r]</math> here is <math>a = \frac{r-k\mu}{T}</math> (assuming <math>1-k\mu \geq T</math>), in which case the formula simplifies to

:<math>Z_1 \leq r (\log \frac{r-k\mu}{T} + \frac{k \sigma^2}{4(r-k\mu)^2 \log a})</math>

Thus far, our arguments have been valid for arbitrary functions <math>g</math>. We now specialise to functions of the form

:<math> g(t) := \frac{1}{c+(k-1)t}.</math>

Note the identity

:<math>\displaystyle g(t) - h(t) = (r - S_{k-1} - c) g(t) h(t)</math>

on <math>[0, \min(r-S_{k-1},T)]</math>. Thus

:<math>Y_2 = \frac{k}{2 m_2} {\mathbf E} \int_{[0,\min(r-S_{k-1},T)]} \int_{[0,\min(r-S_{k-1},T)]} \frac{((g-h)(s) h(t)-(g-h)(t) h(s))^2}{h(s) h(t)}\ ds dt</math>

:<math>= \frac{k}{2 m_2} {\mathbf E} (r - S_{k-1} - c)^2 \int_{[0,\min(r-S_{k-1},T)]} \int_{[0,\min(r-S_{k-1},T)]} (g(s)-g(t))^2 h(s) h(t)\ ds dt.</math>

Bounding <math>(g(s)-g(t))^2 \leq g(s)^2+g(t)^2</math> and using symmetry, we conclude

:<math>Y_2 \leq \frac{k}{m_2} {\mathbf E} (r - S_{k-1} - c)^2 \int_{[0,\min(r-S_{k-1},T)]} \int_{[0,\min(r-S_{k-1},T)]} g(s)^2 h(s) h(t)\ ds dt.</math>

Since <math>\int_0^{r-S_{k-1}} h(t)\ dt = \frac{\log k}{k-1}</math>, we conclude that

:<math>Y_2 \leq \frac{k}{k-1} Z_4</math>

where <math>Z_4 = Z_4[r]</math> is the quantity

:<math>Z_4 := \frac{\log k}{m_2} {\mathbf E} (r - S_{k-1} - c)^2 \int_{[0,\min(r-S_{k-1},T)]} g(s)^2 h_r(s)\ ds.</math>

Putting all this together, we have

:<math> r \Delta_k {\mathbf P} ( S_k \leq r ) \leq \frac{k}{k-1} (r (\log \frac{r-k\mu}{T} + \frac{k \sigma^2}{4(r-k\mu)^2 \log a}) + \frac{r^2}{4kT} + Z_3 + Z_4[r] ).</math>

At this point we encounter a technical problem that <math>Z_4</math> diverges logarithmically (up to a cap of <math>\log k</math>) as <math>S_{k-1}</math> approaches r. To deal with this issue we average in r, and specifically over the interval <math>[1,1+\tau]</math>. One can calculate that

:<math> \int_0^1 (1+u\tau) 1_{x > 1+u\tau}\ du \leq (1+\tau/2) \frac{(x-k\mu)^2}{(1+\tau-k\mu)^2}</math>

for all x if we have <math>1-k\mu \geq \tau</math> (because the two expressions touch at <math>x=1+\tau</math>, with the RHS being convex with slope at least <math>(1+\tau/2)/\tau</math> there. and the LHS lying underneath this tangent line). Assuming this, we conclude that

:<math> \int_0^1 (1+u\tau) {\mathbf P} ( S_k \leq 1+u\tau )\ du \leq (1 + \frac{\tau}{2}) (1 - \frac{k \sigma^2}{(1+\tau-k\mu)^2})</math>

provided that <math>k \mu < 1 - \tau</math>, and hence

:<math> \Delta_k (1 + \frac{\tau}{2}) (1 - \frac{k \sigma^2}{(1+\tau-k\mu)^2}) \leq \frac{k}{k-1} ( \frac{1}{\tau} \int_1^{1+\tau} (r (\log \frac{r-k\mu}{T} + \frac{k \sigma^2}{4a^2 T^2 \log a}) + \frac{r^2}{4kT}) dr + Z_3 + \int_0^1 Z_4[1+u\tau]\ du ).</math>

Now we deal with the <math>Z_4</math> integral. We split into two contributions, depending on whether <math>1+u\tau-S_{k-1} \leq 2c</math> or not. If <math>1+u\tau-S_{k-1}\leq 2c</math>, then we may bound
:<math> (1+u\tau-S_{k-1}-c)^2 \leq c^2</math>

when <math>1+u\tau-S_{k-1} \geq 0</math>, so this portion of <math>\int_0^1 Z_4[1+u\tau]\ du</math> may be bounded by

:<math> \frac{\log k}{m_2} c^2 {\mathbf E} \int_{[0,T]} g(s)^2 (\int_0^1 h_{1+u\tau}(s) 1_{1+a\tau-S_{k-1} \geq s}\ du)\ ds.</math>

Observe that

:<math>\int_0^1 h_{1+u\tau}(s) 1_{1+u\tau-S_{k-1} \geq s}\ du = \int_0^1 \frac{du}{1-S_{k-1}+u\tau+(k-1)s} 1_{1-S_{k-1}+u\tau \geq s}</math>
:<math> = \frac{1}{\tau} \int_{[\max(ks, 1-S_{k-1}+(k-1)s), 1-S_{k-1}+\tau+(k-1)s]} \frac{du}{u}</math>
:<math> \leq \frac{1}{\tau} \log \frac{ks+\tau}{ks}</math>

and so this portion of <math>\int_0^1 Z_4[1+a\tau]\ da</math> is bounded by
:<math>W X</math>

where

:<math>W := m_2^{-1} \int_{[0,T)]} g(s)^2 \log(1+\frac{\tau}{ks})\ ds.</math>
:<math>X := \frac{\log k}{\tau} c^2</math>

As for the portion when <math>1+u\tau-S_{k-1} > 2c</math>, we bound <math>h_{1+u\tau}(s) \leq \frac{1}{2c+(k-1)t}</math>, and so this portion of <math>\int_0^1 Z_4[1+u\tau]\ du</math> may be bounded by

:<math>\int_0^1 \frac{\log k}{c} {\mathbf E} (1 + u\tau - S_{k-1} - c)^2 V\ du</math>
:<math>= V U</math>

where

:<math>V := \frac{c}{m_2} \int_0^T \frac{g(t)^2}{2c + (k-1)t}\ dt.</math>
:<math>U := \frac{\log k}{c} \int_0^1 (1 + u\tau - (k-1)\mu - c)^2+ (k-1)\sigma^2\ du</math>

We thus arrive at the final bound

:<math> \Delta_k \leq \frac{k}{k-1} \frac{ \frac{1}{\tau} \int_1^{1+\tau} (r (\log \frac{r-k\mu}{T} + \frac{k \sigma^2}{4(r-k\mu)^2 \log a}) + \frac{r^2}{4kT}) dr + Z_3 + W X + VU}{ (1+\tau/2)(1 - \frac{k\sigma^2}{(1+\tau-k\mu)^2})}</math>

provided that <math>k \mu < 1 - \tau</math> and the denominator is positive.

=== Asymptotic analysis ===

We work in the asymptotic regime <math>k \to \infty</math>. Setting

:<math>c:= \frac{1}{\log k} + \frac{\alpha}{\log^2 k}</math>
:<math>T:= \frac{\beta}{\log k}</math>
:<math>\tau := \frac{\gamma}{\log k}</math>

for some absolute constants <math>\alpha \in {\mathbf R}</math> and <math>\beta,\gamma > 0</math>, one calculates

:<math>1-k\mu= \frac{\alpha+\log\beta- 1+ o(1)}{\log k}</math>
:<math>k\sigma^2 = \frac{\beta+o(1)}{\log^2 k}</math>

and so the constraint <math>1-k\mu > \tau</math> becomes

:<math>\alpha + \log \beta + \gamma \leq 1.</math>

With <math>r =1 + \frac{u\gamma}{\log k}</math> for <math>0 \leq u \leq 1</math>, one has

:<math> a = \frac{1-\alpha-\log \beta+u \gamma +o(1)}{\beta}</math>
:<math> Z_1 \leq \log a + \frac{1}{4\beta a \log^2 a}</math>

and one also calculates
:<math> Z_2, Z_3 = o(1)</math>
:<math>W = \int_0^\infty \frac{1}{(1+t)^2} \log(1+\frac{\gamma}{t})\ dt +o(1)</math>
:<math> = \frac{\gamma \log(\gamma)}{\gamma-1} + o(1)</math>
:<math>X = \frac{1}{\gamma} + o(1)</math>
:<math> V = \int_0^1\frac{dt}{(1+t)^2 (2+t)} + o(1) = 1 - \log(2) + o(1)</math>
:<math> U = \int_0^1 (u\gamma -\alpha-\log \beta)^2\ du + \beta + o(1)</math>
:<math> = \frac{(\gamma-\alpha-\log\beta)^3 + (\alpha+\log\beta)^3}{3}+ \beta + o(1)</math>

and hence

:<math>\Delta \leq \frac{ \int_0^1 (\log a(u) + \frac{1}{4\beta a(u) \log^2 a(u)})\ du + \frac{\log(\gamma)}{\gamma-1} + \frac{1-\log(2)}{3} ((\gamma-\alpha-\log\beta)^3 + (\alpha+\log\beta)^3+3\beta) }{1 - \frac{\beta}{(1-\alpha-\log \beta-\gamma)^2} }+ o(1)</math>

assuming that <math>\alpha+\log \beta + \gamma< 1</math> and
:<math> 1 - \frac{\beta}{(1-\alpha-\log \beta-\gamma)^2} > 0,</math>
and where <math>a(u):=\frac{1-\alpha-\log \beta+u \gamma}{\beta}</math>.

In particular, by setting <math>\alpha,\beta,\gamma</math> as absolute constants obeying these constraints, we have <math>\Delta \leq O(1)</math>, and so

:<math> M_k = \log k+O(1).</math>

== More general variational problems ==

It appears that for the purposes of establish DHL type theorems, one can increase the range of F in which one is taking suprema over (and extending the range of integration in the definition of <math>J_k^{(m)}(F)</math> accordingly). Firstly, one can enlarge the simplex <math>{\mathcal R}_k</math> to the larger region

:<math>{\mathcal R}'_k = \{ (t_1,\ldots,t_k) \in [0,1]^k: t_1+\ldots+t_k \leq 1 + \min(t_1,\ldots,t_k) \}</math>

provided that one works with a generalisation of <math>EH[\theta]</math> which controls more general Dirichlet convolutions than the von Mangoldt function (a precise assertion in this regard may be found in BFI). In fact (as shown [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/ here]) one can work in any larger region <math>R</math> for which

:<math>R + R \subset \{ (t_1,\ldots,t_k) \in [0,2/\theta]^k: t_1+\ldots+t_k \leq 2 + \max(t_1,\ldots,t_k) \} \cup \frac{2}{\theta} \cdot {\mathcal R}_k</math>

provided that all the marginal distributions of F are supported on <math>{\mathcal R}_{k-1}</math>, thus (assuming F is symmetric)

:<math>\int_0^\infty F(t_1,\ldots,t_{k-1},t_k)\ dt_k = 0 </math> when <math>t_1+\ldots+t_{k-1} > 1.</math>

For instance, one can take <math>R = \frac{1}{\theta} \cdot {\mathcal R}_k</math>, or one can take <math>R = \{ (t_1,\ldots,t_k) \in [0,1/\theta]^k: t_1 +\ldots +t_{k-1} \leq 1 \}</math> (although the latter option breaks the symmetry for F). See [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/ this blog post] for more discussion.

If the marginal distributions of F are supported in <math>(1+\varepsilon) \cdot {\mathcal R}_{k-1}</math> instead of <math>{\mathcal R}_{k-1}</math>, one still has a usable lower bound in which <math>J_k^{(m)}(F)</math> is replaced by the slightly smaller quantity <math>J_{k,\varepsilon}^{(m)}(F)</math>; see [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/ this blog post] for more discussion.

== World records ==

{| class="wikitable" border=1
! <math>k</math>
! colspan="3" | <math>M_k</math>
! colspan="2" | <math>M'_k</math>
! colspan="2" | <math>M''_k</math> (prism)
! colspan="2" | <math>M''_k</math> (symmetric)
! colspan="2" | <math>M''_k</math> (non-convex)
! colspan="2" | <math>M_{k,\varepsilon,1/2}</math>
|-
!
! 1D
! Lower
! Upper
! Lower
! Upper
! Lower
! Upper
! Lower
! Upper
! Lower
! Upper
! Lower
! Upper
|-
| 2
| 1.383
| [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257360 1.38593...]
| [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257360 1.38593...]
| 2
| 2
| 2
| 2
| 2
| 2
|
|
| [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/#comment-263557 1.690608]
| 2
|-
| 3
| 1.635
| [http://users.ugent.be/~ibogaert/KrylovMk/ 1.64644]
| 1.648
| [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/#comment-263186 1.8429]
| 2.080
| [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257276 1.914]
| 2.38593...
| [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/#comment-264262 1.902626]
| 3
| [http://terrytao.wordpress.com/2014/01/17/polymath8b-vi-a-low-dimensional-variational-problem/#comment-267087 1.847]
| 3
| [http://terrytao.wordpress.com/2014/04/14/polymath8b-x-writing-the-paper-and-chasing-down-loose-ends/#comment-326155 1.91726]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 2.4142]
|-
| 4
| 1.820
| [http://users.ugent.be/~ibogaert/KrylovMk/ 1.845407]
| 1.848
| [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257276 1.937]
| 2.198
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258581 1.951]
| 2.648
| [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257276 1.937]
| 4
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-273973 2.05411]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 2.5946]
|-
| 5
| 1.965
| [http://users.ugent.be/~ibogaert/KrylovMk/ 2.007145]
| 2.011797
| [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257360 2.059]
| 2.311
|
| 2.848
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272523 2.20264]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 2.7466]
|-
| 10
| 2.409
| [http://users.ugent.be/~ibogaert/KrylovMk/ 2.54547]
| 2.55842
|
| 2.7466
|
|
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272462 2.68235]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 3.2716]
|-
| 20
| 2.810
| [http://users.ugent.be/~ibogaert/KrylovMk/ 3.12756]
| 3.1534
|
| 3.2716
|
|
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272462 3.21470]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 3.8564]
|-
| 30
| 3.015
| [http://users.ugent.be/~ibogaert/KrylovMk/ 3.48313]
| 3.51848
|
| 3.6079
|
|
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272462 3.51943]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 4.2182]
|-
| 40
| 3.145
| [http://users.ugent.be/~ibogaert/KrylovMk/ 3.73919]
| 3.783467
|
| 3.8564
|
|
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272462 3.71480]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 4.4815]
|-
| 50
| 3.236
| [http://users.ugent.be/~ibogaert/KrylovMk/ 3.93586]
| 3.99186
|
| 4.0540
|
|
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-297456 4.0043]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 4.6889]
|-
| 51
| 3.244
| [http://users.ugent.be/~ibogaert/KrylovMk/ 3.95304]
| 4.0105
|
| 4.0717
|
|
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272506 4.011910]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 4.7075]
|-
| 53
| 3.259
| [http://users.ugent.be/~ibogaert/KrylovMk/ 3.986213]
| 4.0466
|
| 4.1062
|
|
|
|
|
|
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271862 4.000161]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 4.744]
|-
| 54
| 3.266
| [http://users.ugent.be/~ibogaert/KrylovMk/ 4.00223]
| 4.0642
|
| 4.1230
|-
| 55
| 3.273
| [http://users.ugent.be/~ibogaert/KrylovMk/ 4.01788]
| 4.0816
|
| 4.1396
|-
| 59
| 3.299
| [http://users.ugent.be/~ibogaert/KrylovMk/ 4.07704]
| 4.1478399
|
| 4.2030
|}

{| class="wikitable" border=1
! <math>k</math>
! colspan="1" | <math>M_{k,\varepsilon,1}</math>
! colspan="1" | <math>M'_{k,\varepsilon,1}</math> (sym)
! colspan="1" | <math>M''_{k,\varepsilon,1}</math> (prism)
! colspan="1" | <math>M''_{k,\varepsilon,1}</math> (sym)
! colspan="1" | <math>M''_{k,\varepsilon,1}</math> (non-convex)
! colspan="1" | <math>\hat M_{k,\varepsilon,1}</math>
! colspan="1" | <math>\hat M'_{k,\varepsilon,1}</math> (sym)
! colspan="1" | <math>\hat M''_{k,\varepsilon,1}</math> (sym)
! colspan="1" | <math>\hat M''_{k,\varepsilon,1}</math> (prism)
|-
| 2
| [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257360 1.38593...]
| 2
| 2
| 2
| 2
| [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/#comment-263557 1.690608]
| 2
|-
| 3
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-262398 1.8615]
| [http://terrytao.wordpress.com/2014/01/17/polymath8b-vi-a-low-dimensional-variational-problem/#comment-266257 1.956713]
| [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/#comment-265050 1.936708]
| [http://terrytao.wordpress.com/2014/01/17/polymath8b-vi-a-low-dimensional-variational-problem/#comment-266724 1.962998]
| [http://terrytao.wordpress.com/2014/01/17/polymath8b-vi-a-low-dimensional-variational-problem/#comments 1.9400]
| [http://terrytao.wordpress.com/2014/04/14/polymath8b-x-writing-the-paper-and-chasing-down-loose-ends/#comment-326155 1.91726]
| [http://terrytao.wordpress.com/2014/01/17/polymath8b-vi-a-low-dimensional-variational-problem/#comment-268443 1.992]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-270725 2.0012]
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271881 1.965]
|-
| 4
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-262403 2.0023]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-262403 2.0023]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-262403 2.0023]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-262403 2.0023]
|
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-273973 2.05411]
|}

For k>2, all upper bounds on <math>M_k</math> come from (1). Upper bounds on <math>M'_k</math> come from the inequality <math>M'_k \leq \frac{k}{k-1} M_{k-1}</math> that follows from an averaging argument, and upper bounds on <math>M''_k</math> (on EH, using the prism <math>\{ t_1+\ldots+t_{k-1},t_k \leq 1\}</math> as the domain) come from the inequality <math>M''_k \leq M_{k-1} + 1</math> by comparing <math>M''_k</math> with a variational problem on the prism (details [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257013 here]). The 1D bound <math> 4k(k-1)/j_{k-2}^2</math> is the optimal value for <math>M_k</math> when the underlying function <math>F</math> is restricted to be of the "one-dimensional" form <math>F(t_1,\ldots,t_k) = f(t_1+\ldots+t_k)</math>.

For k=2, <math>M'_2=M''_2 = 2</math> can be computed exactly by taking F to be the indicator function of the unit square (for the lower bound), and by using Cauchy-Schwarz (for the upper bound). <math>M_2=\frac{1}{1-W(1/e)} \approx 1.38593</math> [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/#comment-257360 can be computed exactly] as the solution to the equation <math>2-\frac{1}{x} + \log(1-\frac{1}{x}) = 0</math>.

The quantity <math>M_{k,\varepsilon,\theta}</math> is defined as the supremum of <math> \sum_{m=1}^k J_{k,\varepsilon}^{(m)}(F) / I_k(F)</math> where F is now supported on <math>[0,1/\theta]^k \cap (1+\varepsilon) \cdot {\mathcal R}_k</math>, and <math>J_{k,\varepsilon}^{(m)}</math> is defined as <math>J_k^{(m)}</math> but now restricted to <math>(1-\varepsilon) \cdot {\mathcal R}_k</math>, and <math>0 \leq \varepsilon \leq \max(1/(k-1),1/\theta-1)</math> is a parameter to be optimised in. The quantity <math>M'_{k,\varepsilon,\theta}</math> is defined similarly, but with F now supported on <math>[0,1/\theta]^k \cap (1+\varepsilon) \cdot {\mathcal R}'_k \cap \max(\frac{k}{k-1},\frac{1}{\theta}) \cdot {\mathcal R}_k</math>. Finally, <math>M''_{k,\varepsilon,\theta}</math> is also defined similarly, but with F supported on a region R as above, with all marginals supported on <math>(1+\varepsilon) \cdot {\mathcal R}_{k-1}</math>.

The quantities <math>\hat M_{k,\varepsilon,\theta}, \hat M'_{k,\varepsilon,\theta}, \hat M''_{k,\varepsilon,\theta}</math> are defined similarly to <math>M_{k,\varepsilon,\theta}, M'_{k,\varepsilon,\theta}, M''_{k,\varepsilon,\theta}</math>, but with the truncation of <math>R</math> to <math>[0,1/\theta]^k</math> removed.

For k=3, we also have the non-convex candidate <math>R = \{ x+y,x+z \leq 1 \} \cup \{ x+y,y+z\leq 1 \} \cup \{ x+z,y+z \leq 1 \}</math>.

The crude upper bound of <math>k</math> for any of the <math>M_k</math> type quantities comes from the parity problem obstruction that each separate event "<math>n+h_i</math> prime" can occur with probability at most 1/2.

Here are some [[notes on polytope decomposition]] for the k=3 case.

{| class="wikitable" border=1
|-
! Quantity
! Polytope constraints
! Vanishing marginals?
! Epsilon trick?
! Need GEH?
|-
| <math>M_k</math>
| <math>t_1+\dots+t_k \leq 1</math>
| No
| No
| No
|-
| <math>M'_k</math>
| <math>t_1+\dots+t_k - t_j \leq 1</math> for all <math>j</math>
| No
| No
| Yes
|-
| <math>M''_k</math> (prism)
| <math>t_1+\dots+t_{k-1} \leq 1</math>
<math>t_k \leq 1/\theta</math>
| Yes
| No
| Yes
|-
| <math>M''_k</math> (symmetric)
| <math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>
<math>t_j \leq 1/\theta</math> for all <math>j</math>
| Yes
| No
| Yes
|-
| <math>M''_3</math> (nonconvex)
<math>(k,\theta)=(3,1)</math>
| <math>t_1+t_2,t_1+t_3 \leq 1</math> OR
<math>t_1+t_2,t_2+t_3 \leq 1</math> OR

<math>t_1+t_3,t_1+t_3 \leq 1</math>
| Yes
| No
| Yes
|-
| <math>M''_3</math> (nonconvex II)
<math>(k,\theta)=(3,1)</math>
| <math>2t_1+t_2+t_3,t_1+2t_2+t_3 \leq 2</math> OR
<math>2t_1+t_2+t_3,t_1+t_2+2t_3 \leq 2</math> OR

<math>t_1+2t_2+t_3,t_1+t_2+2t_3 \leq 2</math>; AND ALSO

<math>t_1,t_2,t_3 \leq 1</math>
| Yes
| No
| Yes
|-
| <math>\hat M''_k</math> (symmetric)
| <math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>
| Yes
| No
| Yes!
|-
| <math>\hat M''_k</math> (prism)
| <math>t_1+\dots+t_{k-1} \leq 1</math>

<math>t_k \leq \frac{2}{\theta}</math>
| Yes
| No
| Yes!
|-
| <math>M_{k,\varepsilon,\theta}</math>
| <math>t_1+\dots+t_k \leq 1+\varepsilon</math>
<math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>

<math>t_j \leq \frac{1}{\theta}</math> for all <math>j</math>
| No
| Yes
| Yes
|-
| <math>M'_{k,\varepsilon,\theta}</math> (symmetric)
| <math>t_1+\dots+t_k-t_j \leq 1+\varepsilon</math> for all <math>j</math>
<math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>

<math>t_j \leq \frac{1}{\theta}</math> for all <math>j</math>
| No
| Yes
| Yes
|-
| <math>M''_{k,\varepsilon,\theta}</math> (prism)
| <math>t_1+\dots+t_{k-1} \leq 1</math>
<math>t_k \leq \frac{1}{\theta}</math>
| Yes
| Yes
| Yes
|-
| <math>M''_{k,\varepsilon,\theta}</math> (symmetric)
| <math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>
<math>t_j \leq \frac{1}{\theta}</math> for all <math>j</math>
| Yes
| Yes
| Yes
|-
| <math>M''_{3,\varepsilon,1}</math> (non-convex)
<math>(k,\theta)=(3,1)</math>
| <math>t_1+t_2,t_1+t_3 \leq 1</math> OR
<math>t_1+t_2,t_2+t_3 \leq 1</math> OR

<math>t_1+t_3,t_1+t_3 \leq 1</math>
| Yes
| Yes
| Yes
|-
| <math>\hat M_{k,\varepsilon,\theta}</math>
| <math>t_1+\dots+t_k \leq 1+\varepsilon</math>
<math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>
| No
| Yes
| Yes!
|-
| <math>\hat M'_{k,\varepsilon,\theta}</math> (symmetric)
| <math>t_1+\dots+t_k-t_j \leq 1+\varepsilon</math> for all <math>j</math>
<math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>
| No
| Yes
| Yes!
|-
| <math>\hat M''_{k,\varepsilon,\theta}</math> (symmetric)
| <math>t_1+\dots+t_k \leq \max(\frac{k}{k-1},\frac{1}{\theta})</math>
| Yes
| Yes
| Yes!
|}

Selberg sieve variational problem

2014-10-24T03:29:45Z

WikiSysop:

Talk:Main Page

2014-10-22T21:35:28Z

WikiSysop: /* Test edit */

== Polymath Logo ==

It would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

:Done. A logo is being trialled. [[User:MichaelNielsen|MichaelNielsen]] 00:59, 14 December 2012 (UTC)

== Links ==

* ?!? wikisysop whats the problem with the [[Jun Fukuyama's P≠NP Paper]] link? [[User:vzn|vzn]] 12/9/2012

: ... [earlier conversation]

::Returning to this conversation after a couple of days of other commitments intervened. Note that I'm now signed in as [[User:MichaelNielsen|MichaelNielsen]], which seems more appropriate than my WikiSysop login. [[User:MichaelNielsen|MichaelNielsen]] 01:02, 14 December 2012 (UTC)

::To the issue: it wasn't at all clear that you were proposing a collaborative evaluation of his proof. Now that you have, I quite agree that it'd be good to have a sensible process for proposing problems on the wiki. At the moment those have mostly been going on the page [[Other proposed projects]], which is linked prominently on the main page. At present I don't see a problem with putting this proposal on that page. What do you think? [[User:MichaelNielsen|MichaelNielsen]] 01:08, 14 December 2012 (UTC)

::Over the longer run (and independent of this particular proposal), there is a real issue, which is that we need some better process for deciding what's a reasonable way of proposing projects, which is both open enough, but also doesn't waste people's time on uninteresting proposals. This seems like a tricky balance to get right. In an ideal world, wiki software would make it so users only saw things which will be of interest to them. Unfortunately, we don't yet live in that world. [[User:MichaelNielsen|MichaelNielsen]] 01:11, 14 December 2012 (UTC)

== Misc ==

* could someone fix the editing help link on the bottom of the wiki edit page & on home page? isnt there a built in help page for this wiki software? it currently leads to [http://michaelnielsen.org/polymath1/index.php?title=Help:Contents empty page]. not very user friendly eh? in particular is there a tag that substitutes in the current time for discussion edits? [[user:vzn|vzn]] 12/10/2012

: software is apparently [http://www.mediawiki.org/wiki/Help:Contents mediawiki]? [[User:Vzn|Vzn]] 19:08, 31 December 2012 (UTC)

* idea: some kind of voting/weighting/ranking system for prioritizing/sorting projects and gauging user interest/support [[user:vzn|vzn]] 12/10/2012 

: note that stackexchange (used by [http://mathoverflow.net mathoverflow]) has very neat capabilities and functionality. imagine a stackexchange dedicated to polymath. this would allow voting on polymath-related items such as proposals, partial results/directions/ideas etc. unfortunately the stackexchange requirements for membership base are high, it possibly requires a few hundred users minimum to commit, but maybe they could consider a special worthwhile case? new stackexchange proposals are on [http://area51.stackexchange.com area51]. [[User:Vzn|Vzn]] 17:23, 28 December 2012 (UTC)

== Test edit ==

Please ignore. [[User:WikiSysop|WikiSysop]] 21:35, 22 October 2014 (UTC)

Bounded gaps between primes

2014-03-06T01:39:17Z

WikiSysop: Date corrected (via Jan Jannink)

This is the home page for the Polymath8 project, which has two components:

* Polymath8a, "Bounded gaps between primes", was a project to improve the bound H=H_1 on the least gap between consecutive primes that was attained infinitely often, by developing the techniques of Zhang. This project concluded with a bound of H = 4,680.
* Polymath8b, "Bounded intervals with many primes", is an ongoing project to improve the value of H_1 further, as well as H_m (the least gap between primes with m-1 primes between them that is attained infinitely often), by combining the Polymath8a results with the techniques of Maynard.

== World records ==

=== Current records ===

This table lists the current best upper bounds on <math>H_m</math> - the least quantity for which it is the case that there are infinitely many intervals <math>n, n+1, \ldots, n+H_m</math> which contain <math>m+1</math> consecutive primes - both on the assumption of the Elliott-Halberstam conjecture (or more precisely, a generalization of this conjecture, formulated as Conjecture 1 in [BFI1986]), without this assumption, and without EH or the use of Deligne's theorems. The boldface entry - the bound on <math>H_1</math> without assuming Elliott-Halberstam, but assuming the use of Deligne's theorems - is the quantity that has attracted the most attention. The conjectured value <math>H_1=2</math> for <math>H_1</math> is the twin prime conjecture.

{| border=1
|-
!<math>m</math>!!Conjectural!!Assuming EH!!Without EH!! Without EH or Deligne
|-
|1
| 2
| [http://terrytao.wordpress.com/2014/01/28/polymath8b-vii-using-the-generalised-elliott-halberstam-hypothesis-to-enlarge-the-sieve-support-yet-further/#comment-268732 6] (on GEH)
[http://arxiv.org/abs/1311.4600 12] (on EH only)
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272506 252]
| [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-272506 252]
|-
|2
| 6
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-261984 270]
| [http://terrytao.wordpress.com/2014/01/17/polymath8b-vi-a-low-dimensional-variational-problem/#comment-268356 395,106]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comments 474,266]
|-
|3
| 8
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258528 52,116]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258810 24,462,654]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258810 32,313,878]
|-
|4
| 12
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comments 474,266]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258810 1,497,901,734]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258587 2,186,561,568]
|-
|5
| 16
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-259813 4,137,854]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258419 82,575,303,678]
| [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/#comment-258626 131,161,149,090]
|-
|<math>m</math>
|<math>\displaystyle (1+o(1)) m \log m</math>
|<math>\displaystyle O( m e^{2m} )</math>
|<math>O( m \exp((4 - \frac{52}{283}) m) )</math>
|<math>O( m \exp((4 - \frac{4}{43}) m) )</math>
|}

We have been working on improving a number of other quantities, including the quantity <math>H_m</math> mentioned above:

* <math>H = H_1</math> is a quantity such that there are infinitely many pairs of consecutive primes of distance at most <math>H</math> apart. Would like to be as small as possible (this is a primary goal of the Polymath8 project).
* <math>k_0</math> is a quantity such that every admissible <math>k_0</math>-tuple has infinitely many translates which each contain at least two primes. Would like to be as small as possible. Improvements in <math>k_0</math> lead to improvements in <math>H</math>. (The relationship is roughly of the form <math>H \sim k_0 \log k_0</math>; see the page on [[finding narrow admissible tuples]].) More recent improvements on <math>k_0</math> have come from solving a [[Selberg sieve variational problem]].
* <math>\varpi</math> is a technical parameter related to a specialized form of the [http://en.wikipedia.org/wiki/Elliott%E2%80%93Halberstam_conjecture Elliott-Halberstam conjecture]. Would like to be as large as possible. Improvements in <math>\varpi</math> lead to improvements in <math>k_0</math>, as described in the page on [[Dickson-Hardy-Littlewood theorems]]. In more recent work, the single parameter <math>\varpi</math> is replaced by a pair <math>(\varpi,\delta)</math> (in previous work we had <math>\delta=\varpi</math>). These estimates are obtained in turn from Type I, Type II, and Type III estimates, as described at the page on [[distribution of primes in smooth moduli]].

=== Timeline of bounds ===

A table of bounds as a function of time may be found at [[timeline of prime gap bounds]]. In this table, infinitesimal losses in <math>\delta,\varpi</math> are ignored.

== Polymath threads ==

# [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart I just can’t resist: there are infinitely many pairs of primes at most 59470640 apart], Scott Morrison, 30 May 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/ The prime tuples conjecture, sieve theory, and the work of Goldston-Pintz-Yildirim, Motohashi-Pintz, and Zhang], Terence Tao, 3 June 2013. Inactive
# [http://polymathprojects.org/2013/06/04/polymath-proposal-bounded-gaps-between-primes/ Polymath proposal: bounded gaps between primes], Terence Tao, 4 June 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/04/online-reading-seminar-for-zhangs-bounded-gaps-between-primes/ Online reading seminar for Zhang’s “bounded gaps between primes”], Terence Tao, 4 June 2013. Inactive
# [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/ More narrow admissible sets], Scott Morrison, 5 June 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/08/the-elementary-selberg-sieve-and-bounded-prime-gaps/ The elementary Selberg sieve and bounded prime gaps], Terence Tao, 8 June 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/10/a-combinatorial-subset-sum-problem-associated-with-bounded-prime-gaps/ A combinatorial subset sum problem associated with bounded prime gaps], Terence Tao, 10 June 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/11/further-analysis-of-the-truncated-gpy-sieve/ Further analysis of the truncated GPY sieve], Terence Tao, 11 June 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/12/estimation-of-the-type-i-and-type-ii-sums/ Estimation of the Type I and Type II sums], Terence Tao, 12 June 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/14/estimation-of-the-type-iii-sums/ Estimation of the Type III sums], Terence Tao, 14 June 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/ A truncated elementary Selberg sieve of Pintz], Terence Tao, 18 June, 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/22/bounding-short-exponential-sums-on-smooth-moduli-via-weyl-differencing/ Bounding short exponential sums on smooth moduli via Weyl differencing], Terence Tao, 22 June, 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/23/the-distribution-of-primes-in-densely-divisible-moduli/ The distribution of primes in densely divisible moduli], Terence Tao, 23 June, 2013. Inactive
# [http://terrytao.wordpress.com/2013/06/30/bounded-gaps-between-primes-polymath8-a-progress-report/ Bounded gaps between primes (Polymath8) – a progress report], Terence Tao, 30 June 2013. Inactive
# [http://sbseminar.wordpress.com/2013/07/02/the-quest-for-narrow-admissible-tuples/ The quest for narrow admissible tuples], Andrew Sutherland, 2 July 2013. Inactive
# [http://terrytao.wordpress.com/2013/07/07/the-distribution-of-primes-in-doubly-densely-divisible-moduli/ The distribution of primes in doubly densely divisible moduli], Terence Tao, 7 July 2013. Inactive.
# [http://terrytao.wordpress.com/2013/07/27/an-improved-type-i-estimate/ An improved Type I estimate], Terence Tao, 27 July 2013. Inactive
# [http://terrytao.wordpress.com/2013/08/17/polymath8-writing-the-paper/ Polymath8: writing the paper], Terence Tao, 17 August 2013. Inactive
# [http://terrytao.wordpress.com/2013/09/02/polymath8-writing-the-paper-ii/ Polymath8: writing the paper, II], Terence Tao, 2 September 2013. Inactive
# [http://terrytao.wordpress.com/2013/09/22/polymath8-writing-the-paper-iii/ Polymath8: writing the paper, III], Terence Tao, 22 September 2013. Inactive
# [http://terrytao.wordpress.com/2013/10/15/polymath8-writing-the-paper-iv/ Polymath8: writing the paper, IV], Terence Tao, 15 October 2013. Inactive
# [http://terrytao.wordpress.com/2013/11/17/polymath8-writing-the-first-paper-v-and-a-look-ahead/ Polymath8: Writing the first paper, V, and a look ahead], Terence Tao, 17 November 2013. Inactive
# [http://terrytao.wordpress.com/2013/11/19/polymath8b-bounded-intervals-with-many-primes-after-maynard/ Polymath8b: Bounded intervals with many primes, after Maynard], Terence Tao, 19 November 2013. Inactive
# [http://terrytao.wordpress.com/2013/11/22/polymath8b-ii-optimising-the-variational-problem-and-the-sieve/ Polymath8b, II: Optimising the variational problem and the sieve] Terence Tao, 22 November 2013. Inactive
# [http://terrytao.wordpress.com/2013/12/08/polymath8b-iii-numerical-optimisation-of-the-variational-problem-and-a-search-for-new-sieves/ Polymath8b, III: Numerical optimisation of the variational problem, and a search for new sieves], Terence Tao, 8 December 2013. Inactive
# [http://terrytao.wordpress.com/2013/12/20/polymath8b-iv-enlarging-the-sieve-support-more-efficient-numerics-and-explicit-asymptotics/ Polymath8b, IV: Enlarging the sieve support, more efficient numerics, and explicit asymptotics], Terence Tao, 20 December 2013. Inactive
# [http://terrytao.wordpress.com/2014/01/08/polymath8b-v-stretching-the-sieve-support-further/ Polymath8b, V: Stretching the sieve support further], Terence Tao, 8 January 2014. Inactive
# [http://terrytao.wordpress.com/2014/01/17/polymath8b-vi-a-low-dimensional-variational-problem/ Polymath8b, VI: A low-dimensional variational problem], Terence Tao, 17 January 2014. Inactive
# [http://terrytao.wordpress.com/2014/01/28/polymath8b-vii-using-the-generalised-elliott-halberstam-hypothesis-to-enlarge-the-sieve-support-yet-further/ Polymath8b, VII: Using the generalised Elliott-Halberstam hypothesis to enlarge the sieve support yet further], Terence Tao, 28 January 2014. Inactive
# [http://terrytao.wordpress.com/2014/02/07/new-equidistribution-estimates-of-zhang-type-and-bounded-gaps-between-primes-and-a-retrospective/ “New equidistribution estimates of Zhang type, and bounded gaps between primes” – and a retrospective], Terence Tao, 7 February 2013. Active
# [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/ Polymath8b, VIII: Time to start writing up the results?], Terence Tao, 9 February 2014. Inactive
# [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/ Polymath8b, IX: Large quadratic programs], Terence Tao, 21 February 2014. Active

== Writeup ==

* Files for the draft paper for the Polymath8a project may be found in [https://www.dropbox.com/sh/j2r8yia6lkzk2gv/_5Sn7mNN3T this directory].
** The compiled PDF for this paper is available [https://www.dropbox.com/s/16bei7l944twojr/newgap.pdf here].
** The paper is now on the arXiv as "[http://arxiv.org/abs/1402.0811 New equidistribution estimates of Zhang type, and bounded gaps between primes]".
* Files for the draft paper for the Polymath8 retrospective may be found in [https://www.dropbox.com/sh/j2r8yia6lkzk2gv/WqefTsWlmC/Retrospective this directory].
** The compiled PDF for this paper is available [https://www.dropbox.com/sh/j2r8yia6lkzk2gv/AtpnawVMGK/Retrospective/retrospective.pdf here].

Here are the [[Polymath8 grant acknowledgments]].

== Code and data ==

* [https://github.com/semorrison/polymath8 Hensely-Richards sequences], Scott Morrison
** [http://tqft.net/misc/finding%20k_0.nb A mathematica notebook for finding k_0], Scott Morrison
** [https://github.com/avi-levy/dhl python implementation], Avi Levy
* [http://www.opertech.com/primes/k-tuples.html k-tuple pattern data], Thomas J Engelsma
** [https://perswww.kuleuven.be/~u0040935/k0graph.png A graph of this data]
** [http://www.opertech.com/primes/webdata/ Tuples giving this data]
* [https://github.com/vit-tucek/admissible_sets Sifted sequences], Vit Tucek
* [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23555 Other sifted sequences], Christian Elsholtz
* [http://www.ams.org/journals/mcom/2001-70-236/S0025-5718-01-01348-5/S0025-5718-01-01348-5.pdf Size of largest admissible tuples in intervals of length up to 1050], Clark and Jarvis
* [http://math.mit.edu/~drew/admissable_v0.1.tar C implementation of the "greedy-greedy" algorithm], Andrew Sutherland
* [https://www.dropbox.com/sh/jjxi0jmcskx1xcz/iBBVwZTj-x Dropbox for sequences], pedant
* [https://docs.google.com/spreadsheet/ccc?key=0Ao3urQ79oleSdEZhRS00X1FLQjM3UlJTZFRqd19ySGc&usp=sharing Spreadsheet for admissible sequences], Vit Tucek
* [http://www.cs.cmu.edu/~xfxie/project/admissible/admissibleV1.1.zip Java code for optimising a given tuple V1.1], xfxie
* [https://math.mit.edu/~primegaps/MaynardMathematicaNotebook.txt Mathematica Notebook for optimising M_k], James Maynard
* Some [[notes on polytope decomposition]]

=== Tuples applet ===

Here is [https://math.mit.edu/~primegaps/sieve.html?ktuple=632 a small javascript applet] that illustrates the process of sieving for an admissible 632-tuple of diameter 4680 (the sieved residue classes match the example in the paper when translated to [0,4680]).

The same applet [https://math.mit.edu/~primegaps/sieve.html can also be used to interactively create new admissible tuples]. The default sieve interval is [0,400], but you can change the diameter to any value you like by adding “?d=nnnn” to the URL (e.g. use https://math.mit.edu/~primegaps/sieve.html?d=4680 for diameter 4680). The applet will highlight a suggested residue class to sieve in green (corresponding to a greedy choice that doesn’t hit the end points), but you can sieve any classes you like.

You can also create sieving demos similar to the k=632 example above by specifying a list of residues to sieve. A longer but equivalent version of the “?ktuple=632″ URL is

https://math.mit.edu/~primegaps/sieve.html?d=4680&r=1,1,4,3,2,8,2,14,13,8,29,31,33,28,6,49,21,47,58,35,57,44,1,55,50,57,9,91,87,45,89,50,16,19,122,114,151,66

The numbers listed after “r=” are residue classes modulo increasing primes 2,3,5,7,…, omitting any classes that do not require sieving — the applet will automatically skip such primes (e.g. it skips 151 in the k=632 example).

A few caveats: You will want to run this on a PC with a reasonably wide display (say 1360 or greater), and it has only been tested on the current versions of Chrome and Firefox.

== Errata ==

Page numbers refer to the file linked to for the relevant paper.

# Errata for Zhang's "[http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf Bounded gaps between primes]"
## Page 5: In the first display, <math>\mathcal{E}</math> should be multiplied by <math>\mathcal{L}^{2k_0+2l_0}</math>, because <math>\lambda(n)^2</math> in (2.2) can be that large, cf. (2.4).
## Page 14: In the final display, the constraint <math>(n,d_1=1</math> should be <math>(n,d_1)=1</math>.
## Page 35: In the display after (10.5), the subscript on <math>{\mathcal J}_i</math> should be deleted.
## Page 36: In the third display, a factor of <math>\tau(q_0r)^{O(1)}</math> may be needed on the right-hand side (but is ultimately harmless).
## Page 38: In the display after (10.14), <math>\xi(r,a;q_1,b_1;q_2,b_2;n,k)</math> should be <math>\xi(r,a;k;q_1,b_1;q_2,b_2;n)</math>.
## Page 42: In (12.3), <math>B</math> should probably be 2.
## Page 47: In the third display after (13.13), the condition <math>l \in {\mathcal I}_i(h)</math> should be <math>l \in {\mathcal I}_i(sh)</math>.
## Page 49: In the top line, a comma in <math>(h_1,h_2;,n_1,n_2)</math> should be deleted.
## Page 51: In the penultimate display, one of the two consecutive commas should be deleted.
## Page 54: Three displays before (14.17), <math>\bar{r_2}(m_1+m_2)q</math> should be <math>\bar{r_2}(m_1+m_2)/q</math>.
# Errata for Motohashi-Pintz's "[http://arxiv.org/pdf/math/0602599v1.pdf A smoothed GPY sieve]", version 1. Update: the errata below have been corrected in the most recent arXiv version of the paper.
## Page 31: The estimation of (5.14) by (5.15) does not appear to be justified. In the text, it is claimed that the second summation in (5.14) can be treated by a variant of (4.15); however, whereas (5.14) contains a factor of <math>(\log \frac{R}{|D|})^{2\ell+1}</math>, (4.15) contains instead a factor of <math>(\log \frac{R/w}{|K|})^{2\ell+1}</math> which is significantly smaller (K in (4.15) plays a similar role to D in (5.14)). As such, the crucial gain of <math>\exp(-k\omega/3)</math> in (4.15) does not seem to be available for estimating the second sum in (5.14).
# Errata for Pintz's "[http://arxiv.org/pdf/1306.1497v1.pdf A note on bounded gaps between primes]", version 1. Update: the errata below have been corrected in subsequent versions of Pintz's paper.
## Page 7: In (2.39), the exponent of <math>3a/2</math> should instead be <math>-5a/2</math> (it comes from dividing (2.38) by (2.37)). This impacts the numerics for the rest of the paper.
## Page 8: The "easy calculation" that the relative error caused by discarding all but the smooth moduli appears to be unjustified, as it relies on the treatment of (5.14) in Motohashi-Pintz which has the issue pointed out in 2.1 above.

== Other relevant blog posts ==

* [http://terrytao.wordpress.com/2008/11/19/marker-lecture-iii-small-gaps-between-primes/ Marker lecture III: “Small gaps between primes”], Terence Tao, 19 Nov 2008.
* [http://blogs.ethz.ch/kowalski/2009/01/22/the-goldston-pintz-yildirim-result-and-how-far-do-we-have-to-walk-to-twin-primes/ The Goldston-Pintz-Yildirim result, and how far do we have to walk to twin primes ?], Emmanuel Kowalski, 22 Jan 2009.
* [http://www.math.columbia.edu/~woit/wordpress/?p=5865 Number Theory News], Peter Woit, 12 May 2013.
* [http://golem.ph.utexas.edu/category/2013/05/bounded_gaps_between_primes.html Bounded Gaps Between Primes], Emily Riehl, 14 May 2013.
* [http://blogs.ethz.ch/kowalski/2013/05/21/bounded-gaps-between-primes/ Bounded gaps between primes!], Emmanuel Kowalski, 21 May 2013.
* [http://blogs.ethz.ch/kowalski/2013/06/04/bounded-gaps-between-primes-some-grittier-details/ Bounded gaps between primes: some grittier details], Emmanuel Kowalski, 4 June 2013.
** [http://www.math.ethz.ch/~kowalski/zhang-notes.pdf The slides from the talk mentioned in that post]
* [http://aperiodical.com/2013/06/bound-on-prime-gaps-bound-decreasing-by-leaps-and-bounds/ Bound on prime gaps bound decreasing by leaps and bounds], Christian Perfect, 8 June 2013.
* [http://blogs.ams.org/blogonmathblogs/2013/06/14/narrowing-the-gap/ Narrowing the Gap], Brie Finegold, AMS Blog on Math Blogs, 14 June 2013.
* [http://blogs.ethz.ch/kowalski/2013/06/22/bounded-gaps-between-primes-the-dawn-of-some-enlightenment/ Bounded gaps between primes: the dawn of (some) enlightenment], Emmanuel Kowalski, 22 June 2013.
* [http://blogs.ethz.ch/kowalski/2013/06/25/a-ternary-divisor-variation/ A ternary divisor variation], Emmanuel Kowalski, 25 June 2013.
* [http://blogs.ethz.ch/kowalski/2013/09/09/conductors-of-one-variable-transforms-of-trace-functions/ Conductors of one-variable transforms of trace functions], Emmanuel Kowalski, 9 September 2013.
* [http://gilkalai.wordpress.com/2013/09/20/polymath-8-a-success/ Polymath 8 – a Success!], Gil Kalai, 20 September 2013.
* [http://blogs.ethz.ch/kowalski/2013/10/24/james-maynard-auteur-du-theoreme-de-lannee/ James Maynard, auteur du théorème de l’année], Emmanuel Kowalski, 24 October 2013.
* [http://blogs.ethz.ch/kowalski/2013/12/08/reflections-on-reading-the-polymath8a-paper/ Reflections on reading the Polymath8(a) paper], Emmanuel Kowalski, 8 December 2013.

== MathOverflow ==

* [http://mathoverflow.net/questions/131185/philosophy-behind-yitang-zhangs-work-on-the-twin-primes-conjecture Philosophy behind Yitang Zhang’s work on the Twin Primes Conjecture], 20 May 2013.
* [http://mathoverflow.net/questions/131825/a-technical-question-related-to-zhangs-result-of-bounded-prime-gaps A technical question related to Zhang’s result of bounded prime gaps], 25 May 2013.
* [http://mathoverflow.net/questions/132452/how-does-yitang-zhang-use-cauchys-inequality-and-theorem-2-to-obtain-the-error How does Yitang Zhang use Cauchy’s inequality and Theorem 2 to obtain the error term coming from the <math>S_2</math> sum], 31 May 2013.
* [http://mathoverflow.net/questions/132632/tightening-zhangs-bound-closed Tightening Zhang’s bound], 3 June 2013.
** [http://meta.mathoverflow.net/discussion/1605/tightening-zhangs-bound/ Metathread for this post]
* [http://mathoverflow.net/questions/132731/does-zhangs-theorem-generalize-to-3-or-more-primes-in-an-interval-of-fixed-len Does Zhang’s theorem generalize to 3 or more primes in an interval of fixed length?], 3 June 2013.

== Wikipedia and other references ==

* [http://en.wikipedia.org/wiki/Bessel_function Bessel function]
* [http://en.wikipedia.org/wiki/Bombieri-Vinogradov_theorem Bombieri-Vinogradov theorem]
* [http://en.wikipedia.org/wiki/Brun%E2%80%93Titchmarsh_theorem Brun-Titchmarsh theorem]
* [http://www.encyclopediaofmath.org/index.php/Dispersion_method Dispersion method]
* [http://en.wikipedia.org/wiki/Prime_gap Prime gap]
* [http://en.wikipedia.org/wiki/Second_Hardy%E2%80%93Littlewood_conjecture Second Hardy-Littlewood conjecture]
* [http://en.wikipedia.org/wiki/Twin_prime_conjecture Twin prime conjecture]

== Recent papers and notes ==

* [http://arxiv.org/abs/1304.3199 On the exponent of distribution of the ternary divisor function], Étienne Fouvry, Emmanuel Kowalski, Philippe Michel, 11 Apr 2013.
* [http://www.renyi.hu/~revesz/ThreeCorr0grey.pdf On the optimal weight function in the Goldston-Pintz-Yildirim method for finding small gaps between consecutive primes], Bálint Farkas, János Pintz and Szilárd Gy. Révész, To appear in: Paul Turán Memorial Volume: Number Theory, Analysis and Combinatorics, de Gruyter, Berlin, 2013. 23 pages. [http://arxiv.org/abs/1306.2133 arXiv]
* [http://arxiv.org/abs/1305.0348 The existence of small prime gaps in subsets of the integers], Jacques Benatar, 2 May, 2013.
* [http://annals.math.princeton.edu/articles/7954 Bounded gaps between primes], Yitang Zhang, to appear, Annals of Mathematics. Released 21 May, 2013.
* [http://arxiv.org/abs/1305.6289 Polignac Numbers, Conjectures of Erdös on Gaps between Primes, Arithmetic Progressions in Primes, and the Bounded Gap Conjecture], Janos Pintz, 27 May 2013.
* [http://arxiv.org/abs/1305.6369 A poor man's improvement on Zhang's result: there are infinitely many prime gaps less than 60 million], T. S. Trudgian, 28 May 2013.
* [http://www.math.ethz.ch/~kowalski/friedlander-iwaniec-sum.pdf The Friedlander-Iwaniec sum], É. Fouvry, E. Kowalski, Ph. Michel., May 2013.
* [http://www.aimath.org/news/primegaps70m/ Zhang's Theorem on Bounded Gaps Between Primes], Dan Goldston, May? 2013.
* [http://terrytao.files.wordpress.com/2013/06/bounds.pdf Notes on Zhang's prime gaps paper], Terence Tao, 1 June 2013.
* [http://arxiv.org/abs/1306.0511 Bounded prime gaps in short intervals], Johan Andersson, 3 June 2013.
* [http://arxiv.org/abs/1306.0948 Bounded length intervals containing two primes and an almost-prime II], James Maynard, 5 June 2013.
* [http://arxiv.org/abs/1306.1497 A note on bounded gaps between primes], Janos Pintz, 6 June 2013.
* [https://sites.google.com/site/avishaytal/files/Primes.pdf Lower Bounds for Admissible k-tuples], Avishay Tal, 15 June 2013.
* Notes in a truncated elementary Selberg sieve ([http://terrytao.files.wordpress.com/2013/06/file-1.pdf Section 1], [http://terrytao.files.wordpress.com/2013/06/file-2.pdf Section 2], [http://terrytao.files.wordpress.com/2013/06/file-3.pdf Section 3]), Janos Pintz, 18 June 2013.
* [http://www.renyi.hu/~gharcos/gaps.pdf Lecture notes: bounded gaps between primes], Gergely Harcos, 1 Oct 2013.
* [http://math.mit.edu/~drew/PrimeGaps.pdf New bounds on gaps between primes], Andrew Sutherland, 17 Oct 2013.
* [http://www.dms.umontreal.ca/~andrew/CurrentEventsArticle.pdf Bounded gaps between primes], Andrew Granville, 29 Oct 2013.
* [http://www.dms.umontreal.ca/~andrew/CEBBrochureFinal.pdf Primes in intervals of bounded length], Andrew Granville, 19 Nov 2013.
* [http://arxiv.org/abs/1311.4600 Small gaps between primes], James Maynard, 19 Nov 2013.
* [http://arxiv.org/abs/1311.5319 A note on the theorem of Maynard and Tao], Tristan Freiberg, 21 Nov 2013.
* [http://arxiv.org/abs/1311.7003 Consecutive primes in tuples], William D. Banks, Tristan Freiberg, and Caroline L. Turnage-Butterbaugh, 27 Nov 2013.
* [http://arxiv.org/abs/1312.2926 Close encounters among the primes], John Friedlander, Henryk Iwaniec, 10 Dec 2013.
* [http://arxiv.org/abs/1401.7555 A Friendly Intro to Sieves with a Look Towards Recent Progress on the Twin Primes Conjecture], David Lowry-Duda, 25 Jan, 2014.
* [http://arxiv.org/abs/1401.6614 The twin prime conjecture], Yoichi Motohashi, 26 Jan 2014.
* [http://arxiv.org/abs/1401.6677 Bounded gaps between primes in Chebotarev sets], Jesse Thorner, 26 Jan 2014.
* [http://arxiv.org/abs/1402.4849 Bounded gaps between primes], Ben Green, 19 Feb 2014.

== Media ==

* [http://www.nature.com/news/first-proof-that-infinitely-many-prime-numbers-come-in-pairs-1.12989 First proof that infinitely many prime numbers come in pairs], Maggie McKee, Nature, 14 May 2013.
* [http://www.newscientist.com/article/dn23535-proof-that-an-infinite-number-of-primes-are-paired.html Proof that an infinite number of primes are paired], Lisa Grossman, New Scientist, 14 May 2013.
* [https://www.simonsfoundation.org/features/science-news/unheralded-mathematician-bridges-the-prime-gap/ Unheralded Mathematician Bridges the Prime Gap], Erica Klarreich, Simons science news, 20 May 2013.
** The article also appeared on Wired as "[http://www.wired.com/wiredscience/2013/05/twin-primes/ Unknown Mathematician Proves Elusive Property of Prime Numbers]".
* [http://www.slate.com/articles/health_and_science/do_the_math/2013/05/yitang_zhang_twin_primes_conjecture_a_huge_discovery_about_prime_numbers.html The Beauty of Bounded Gaps], Jordan Ellenberg, Slate, 22 May 2013.
* [http://www.newscientist.com/article/dn23644 Game of proofs boosts prime pair result by millions], Jacob Aron, New Scientist, 4 June 2013.
* [http://www.lemonde.fr/sciences/article/2013/06/24/l-union-fait-la-force-des-mathematiciens_3435624_1650684.html L'union fait la force des mathématiciens], Philippe Pajot, Le Monde, 24 June, 2013.
* [http://blogs.discovermagazine.com/crux/2013/07/10/primal-madness-mathematicians-hunt-for-twin-prime-numbers/ Primal Madness: Mathematicians’ Hunt for Twin Prime Numbers], Amir Aczel, Discover Magazine, 10 July, 2013.
* [http://nautil.us/issue/5/fame/the-twin-prime-hero The Twin Prime Hero], Michael Segal, Nautilus, Issue 005, 2013.
* [http://news.anu.edu.au/2013/11/19/prime-time/ Prime Time], Casey Hamilton, Australian National University, 19 November 2013.
* [https://www.simonsfoundation.org/quanta/20131119-together-and-alone-closing-the-prime-gap/ Together and Alone, Closing the Prime Gap], Erica Klarreich, Quanta, 19 November 2013.
** The article also appeared on Wired as "[http://www.wired.com/wiredscience/2013/11/prime/ Sudden Progress on Prime Number Problem Has Mathematicians Buzzing]".
** [http://science.slashdot.org/story/13/11/20/1256229/mathematicians-team-up-to-close-the-prime-gap Mathematicians Team Up To Close the Prime Gap], Slashdot, 20 November 2013.
* [http://www.spektrum.de/alias/mathematik/ein-grosser-schritt-zum-beweis-der-primzahlzwillingsvermutung/1216488 Ein großer Schritt zum Beweis der Primzahlzwillingsvermutung], Hans Engler, Spektrum, 13 December 2013.
* [http://phys.org/news/2014-01-mathematical-puzzle-unraveled.html An old mathematical puzzle soon to be unraveled?], Benjamin Augereau, Phys.org, 15 January 2014.
* [http://www.spektrum.de/alias/zahlentheorie/neuer-durchbruch-auf-dem-weg-zur-primzahlzwillingsvermutung/1222001 Neuer Durchbruch auf dem Weg zur Primzahlzwillingsvermutung], Christoph Poppe, Spektrum, 30 January 2014.
* [http://news.cnet.com/8301-17938_105-57618696-1/yitang-zhang-a-prime-number-proof-and-a-world-of-persistence/ Yitang Zhang: A prime-number proof and a world of persistence], Leslie Katz, CNET, February 12, 2014.
* [http://podacademy.org/podcasts/maths-isnt-standing-still/ Maths isn’t standing still], Adam Smith and Vicky Neale, Pod Academy, March 3, 2014.

== Bibliography ==

Additional links for some of these references (e.g. to arXiv versions) would be greatly appreciated.

* [BFI1986] Bombieri, E.; Friedlander, J. B.; Iwaniec, H. Primes in arithmetic progressions to large moduli. Acta Math. 156 (1986), no. 3-4, 203–251. [http://www.ams.org/mathscinet-getitem?mr=834613 MathSciNet] [http://link.springer.com/article/10.1007%2FBF02399204 Article]
* [BFI1987] Bombieri, E.; Friedlander, J. B.; Iwaniec, H. Primes in arithmetic progressions to large moduli. II. Math. Ann. 277 (1987), no. 3, 361–393. [http://www.ams.org/mathscinet-getitem?mr=891581 MathSciNet] [https://eudml.org/doc/164255 Article]
* [BFI1989] Bombieri, E.; Friedlander, J. B.; Iwaniec, H. Primes in arithmetic progressions to large moduli. III. J. Amer. Math. Soc. 2 (1989), no. 2, 215–224. [http://www.ams.org/mathscinet-getitem?mr=976723 MathSciNet] [http://www.ams.org/journals/jams/1989-02-02/S0894-0347-1989-0976723-6/ Article]
* [B1995] Jörg Brüdern, Einführung in die analytische Zahlentheorie, Springer Verlag 1995
* [CJ2001] Clark, David A.; Jarvis, Norman C.; Dense admissible sequences. Math. Comp. 70 (2001), no. 236, 1713–1718 [http://www.ams.org/mathscinet-getitem?mr=1836929 MathSciNet] [http://www.ams.org/journals/mcom/2001-70-236/S0025-5718-01-01348-5/home.html Article]
* [FI1981] Fouvry, E.; Iwaniec, H. On a theorem of Bombieri-Vinogradov type., Mathematika 27 (1980), no. 2, 135–152 (1981). [http://www.ams.org/mathscinet-getitem?mr=610700 MathSciNet] [http://www.math.ethz.ch/~kowalski/fouvry-iwaniec-on-a-theorem.pdf Article]
* [FI1983] Fouvry, E.; Iwaniec, H. Primes in arithmetic progressions. Acta Arith. 42 (1983), no. 2, 197–218. [http://www.ams.org/mathscinet-getitem?mr=719249 MathSciNet] [http://matwbn.icm.edu.pl/ksiazki/aa/aa42/aa4226.pdf Article]
* [FI1985] Friedlander, John B.; Iwaniec, Henryk, Incomplete Kloosterman sums and a divisor problem. With an appendix by Bryan J. Birch and Enrico Bombieri. Ann. of Math. (2) 121 (1985), no. 2, 319–350. [http://www.ams.org/mathscinet-getitem?mr=786351 MathSciNet] [http://www.jstor.org/stable/1971175 JSTOR] [http://www.jstor.org/stable/1971176 Appendix]
* [GPY2009] Goldston, Daniel A.; Pintz, János; Yıldırım, Cem Y. Primes in tuples. I. Ann. of Math. (2) 170 (2009), no. 2, 819–862. [http://arxiv.org/abs/math/0508185 arXiv] [http://www.ams.org/mathscinet-getitem?mr=2552109 MathSciNet]
* [GR1998] Gordon, Daniel M.; Rodemich, Gene Dense admissible sets. Algorithmic number theory (Portland, OR, 1998), 216–225, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998. [http://www.ams.org/mathscinet-getitem?mr=1726073 MathSciNet] [http://www.ccrwest.org/gordon/ants.pdf Article]
* [GR1980] S. W. Graham, C. J. Ringrose, Lower bounds for least quadratic nonresidues. Analytic number theory (Allerton Park, IL, 1989), 269–309, Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990. [http://www.ams.org/mathscinet-getitem?mr=1084186 MathSciNet] [http://link.springer.com/content/pdf/10.1007%2F978-1-4612-3464-7_18.pdf Article]
* [HB1978] D. R. Heath-Brown, Hybrid bounds for Dirichlet L-functions. Invent. Math. 47 (1978), no. 2, 149–170. [http://www.ams.org/mathscinet-getitem?mr=485727 MathSciNet] [http://link.springer.com/article/10.1007%2FBF01578069 Article]
* [HB1986] D. R. Heath-Brown, The divisor function d3(n) in arithmetic progressions. Acta Arith. 47 (1986), no. 1, 29–56. [http://www.ams.org/mathscinet-getitem?mr=866901 MathSciNet] [http://matwbn.icm.edu.pl/ksiazki/aa/aa47/aa4713.pdf Article]
* [HR1973] Hensley, Douglas; Richards, Ian, On the incompatibility of two conjectures concerning primes. Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972), pp. 123–127. Amer. Math. Soc., Providence, R.I., 1973. [http://www.ams.org/mathscinet-getitem?mr=340194 MathSciNet] [http://www.ams.org/journals/bull/1974-80-03/S0002-9904-1974-13434-8/S0002-9904-1974-13434-8.pdf Article]
* [HR1973b] Hensley, Douglas; Richards, Ian, Primes in intervals. Acta Arith. 25 (1973/74), 375–391. [http://www.ams.org/mathscinet-getitem?mr=396440 MathSciNet] [https://eudml.org/doc/205282 Article]
* [MP2008] Motohashi, Yoichi; Pintz, János A smoothed GPY sieve. Bull. Lond. Math. Soc. 40 (2008), no. 2, 298–310. [http://arxiv.org/abs/math/0602599 arXiv] [http://www.ams.org/mathscinet-getitem?mr=2414788 MathSciNet] [http://blms.oxfordjournals.org/content/40/2/298 Article]
* [MV1973] Montgomery, H. L.; Vaughan, R. C. The large sieve. Mathematika 20 (1973), 119–134. [http://www.ams.org/mathscinet-getitem?mr=374060 MathSciNet] [http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=6718308 Article]
* [M1978] Hugh L. Montgomery, The analytic principle of the large sieve. Bull. Amer. Math. Soc. 84 (1978), no. 4, 547–567. [http://www.ams.org/mathscinet-getitem?mr=466048 MathSciNet] [http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.bams/1183540922 Article]
* [R1974] Richards, Ian On the incompatibility of two conjectures concerning primes; a discussion of the use of computers in attacking a theoretical problem. Bull. Amer. Math. Soc. 80 (1974), 419–438. [http://www.ams.org/mathscinet-getitem?mr=337832 MathSciNet] [http://www.ams.org/journals/bull/1974-80-03/S0002-9904-1974-13434-8/home.html Article]
* [S1961] Schinzel, A. Remarks on the paper "Sur certaines hypothèses concernant les nombres premiers". Acta Arith. 7 1961/1962 1–8. [http://www.ams.org/mathscinet-getitem?mr=130203 MathSciNet] [http://matwbn.icm.edu.pl/ksiazki/aa/aa7/aa711.pdf Article]
* [S2007] K. Soundararajan, Small gaps between prime numbers: the work of Goldston-Pintz-Yıldırım. Bull. Amer. Math. Soc. (N.S.) 44 (2007), no. 1, 1–18. [http://www.ams.org/mathscinet-getitem?mr=2265008 MathSciNet] [http://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01142-6/ Article] [http://arxiv.org/abs/math/0605696 arXiv]

Main Page

2013-07-29T22:02:48Z

WikiSysop:

{{RightTOC}}
This is the wiki for ''polymath'' projects - massively collaborative online mathematical projects. The idea of such projects originated in Tim Gowers' blog post [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?]

Many polymath projects will be proposed, planned, and run at [http://polymathprojects.org/ This Blog].

A Polymath [[logo]] is being trialled. If you have more suggestions, please add them to the [[logo]] page, or add to the discussion at [[Talk:logo]].

The wiki is currently locked down due to a major influx of spam (July 29, 2013). Please email mn@michaelnielsen.org if you'd like an account set up, and I'll do my best to reply quickly.

== Existing polymath projects ==

* [[Polymath1]]: New proofs and bounds for the density Hales-Jewett theorem. Initiated Feb 1, 2009; research results have now been published.
* [[Definable Banach Spaces|Polymath2]]: Must an “explicitly defined” Banach space contain <math>c_0</math> or <math>l_p</math>? Initiated Feb 17, 2009; attempts to relaunch via wiki, June 9 2010.
* [[imo 2009 q6|Mini-polymath1]]: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
* [[The polynomial Hirsch conjecture|Polymath3]]. The polynomial Hirsch conjecture. Proposed July 17, 2009; launched, September 30, 2010.
* [[finding primes|Polymath4]]: A deterministic way to find primes. Proposed July 27, 2009; launched Aug 9, 2009. Research results have been accepted for publication.
* [[The Erdős discrepancy problem|Polymath5]]: The Erdős discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010.
* [[imo 2010|Mini-polymath2]]: Solving Problem 5 the 2010 International Mathematical Olympiad. Proposed Jun 12, 2010; launched and solved, Jul 8 2010.
* [[Improving the bounds for Roth's theorem|Polymath6]]: Improving the bounds for Roth's theorem. Proposed Feb 5, 2011.
* [[imo 2011|Mini-polymath3]]: Solving a problem from the 2011 International Mathematical Olympiad. Proposed Jun 9, 2011; launched and solved, Jul 19, 2011.
* [[imo 2012|Mini-polymath4]]: Solving a problem from the 2012 International Mathematical Olympiad. Proposed, Jun 3, 2012; launched, July 12 2012.
* [[The hot spots conjecture|Polymath7]]: Establishing the Hot Spots conjecture for acute-angled triangles. Proposed, May 31st, 2012; launched, Jun 8, 2012.
* [[Bounded gaps between primes|Polymath8]]: Improving the bounds for small gaps between primes. Proposed, June 4, 2013; launched, June 4, 2013.

== Polymath-like projects ==

* [http://theses.portonvictor.org/node/2 Mathematics research projects]
* Scott Aaronson's "philomath project": "[http://scottaaronson.com/blog/?p=453 Sensitivity vs. Block sensitivity]" (see also [http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice this Math Overflow question]). Launched Jul 13, 2010.
* A wiki page clearinghouse for the [[Deolalikar P vs NP paper]]. Launched Aug 10, 2010.
* <del>[http://researchtrends.wikia.com/wiki/Main_Page Math Research Trends Wiki] "research in the middle"</del> This project is recommended to be discontinued in favor of [http://portonmath.wordpress.com/2013/03/23/collaborative-research/ collaborative research at PlanetMath].
* The page for the [[ABC conjecture]] contains links and information about Mochizuki's claimed proof of this conjecture.

== Proposed polymath projects ==

* [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ The cap set problem]. Proposed March 25, 2009 (see also these [http://gilkalai.wordpress.com/2009/05/11/around-the-cap-set-problem-b/ two] [http://gilkalai.wordpress.com/2009/05/18/the-cap-set-problem-and-frankl-rodl-theorem-c/ followup] posts).
* [[Boshernitzan’s problem]]. Proposed July 27, 2009.
* [http://gowers.wordpress.com/2009/09/16/possible-future-polymath-projects/ Possible future polymath projects]. Discussion opened September 16, 2009.
* [http://rjlipton.wordpress.com/2011/05/12/a-possible-polymath-project/ A possible polymath project:] Proposal by Richard Lipton to attack a conjecture due to Erdos, about a class of Diophantine equations.

A (partial) list of proposed projects can be found [http://polymathprojects.org/category/polymath-proposals/ here].

If you have a tentative proposal for a polymath project, you can either make a post on it on your own blog, or place it [[other proposed projects|here]].

== Discussions about polymath ==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] Tim Gowers, January 27, 2009.
* [http://lucatrevisan.wordpress.com/2009/02/01/a-peoples-history-of-mathematics/ A people's history of mathematics] Luca Trevisan, February 1, 2009.
* [http://michaelnielsen.org/blog/?p=553 The polymath project] Michael Nielsen, February 3, 2009.
* [http://www.neverendingbooks.org/index.php/yet-another-math20-proposal.html Yet another math 2.0 proposal] Lieven le Bruyn, February 11, 2009.
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] Tim Gowers, March 10, 2009.
* [http://maxwelldemon.com/2009/03/14/polymath/ Polymath] Edmund Harriss, March 14, 2009.
* [http://science.slashdot.org/article.pl?sid=09/03/18/194228 Massive open collaboration in mathematics declared a success] Slashdot, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=581 How changing the technology of collaboration can change the nature of collaboration] Michael Nielsen, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=584 The polymath project: scope of participation] Michael Nielsen, March 20, 2009.
* [http://gowers.wordpress.com/2009/03/24/can-polymath-be-scaled-up/ Can polymath be scaled up?] Tim Gowers, March 24, 2009.
* [http://whatisresearch.wordpress.com/2009/03/24/concluding-notes-on-the-polymath-project-and-a-challenge/ Concluding notes on the polymath project - and a challenge] Vilpulniak, March 24, 2009.
* [http://michaelnielsen.org/blog/on-scaling-up-the-polymath-project/ On scaling up the polymath project] Michael Nielsen, March 25, 2009.
* [http://numberwarrior.wordpress.com/2009/03/25/a-gentle-introduction-to-the-polymath-project/ A gentle introduction to the polymath project] Jason Dyer, March 25, 2009.
* [http://blogs.telegraph.co.uk/technology/iandouglas/9656357/tim_gowers_and_the_polymaths/ Tim Gowers and the polymaths] Ian Douglas (the Telegraph), April 29, 2009
* [http://terrytao.wordpress.com/2009/07/22/imo-2009-q6-mini-polymath-project-impressions-reflections-analysis/ IMO 2009 Q6 as mini-polymath project: impressions, reflections, analysis] Terence Tao, July 22, 2009.
* [http://polymathprojects.org/2009/07/27/selecting-the-next-polymath-project/ Selecting the next polymath project] Terence Tao, July 27, 2009.
* [http://blog.jonudell.net/2009/07/31/polymath-equals-user-innovatio/ Polymath equals user innovation] Jon Udell, July 31, 2009.
* [http://scienceblogs.com/christinaslisrant/2009/08/an_overview_of_the_polymath_pr.php An overview of the polymath project] Christina Pikas, August 1, 2009
* [http://whatisresearch.wordpress.com/2009/08/09/collaborative-mathematics-etc/ Collaborative mathematics etc.] Vipulniak, August 9, 2009
* [http://www.nature.com/nature/journal/v461/n7266/full/461879a.html Massively collaborative mathematics] Tim Gowers, Michael Nielsen, Nature, October 15, 2009
* [http://portonmath.wordpress.com/2009/10/25/collaborative-research-of-filters/ Collaborative math research – a real example] Victor Porton, October 24, 2009
* [http://whatisresearch.wordpress.com/2009/10/26/polymath-again/ Polymath again] Vipulniak, October 26, 2009
* [http://www.kennislink.nl/publicaties/wiskunde-met-zijn-allen Wiskunde met zijn allen] (Dutch), Alex van den Brandhof, Kennislink, November 12, 2009
* [http://www.sciencenews.org/view/generic/id/50532/title/Mathematics_by_collaboration Mathematics by collaboration], Julie Rehmeyer, ScienceNews, December 8, 2009
* [http://www.nytimes.com/projects/magazine/ideas/2009/#m Massively Collaborative Mathematics], Jordan Ellenberg, The Ninth Annual Year in Ideas, New York Times, 2009.
* [http://www.hypios.com/thinking/2010/01/13/massively-collaborative-mathematics-lessons-from-polymath1/ Massively Collaborative Mathematics: lessons from polymath1], Hypios, Jan 13 2010
* [http://ths1104.wordpress.com/2010/02/13/open-reflexions-sur-fond-de-polymaths/ Open réflexions sur fond de Polymaths] (French), ths1104, Feb 13 2010
* [http://www.javiertordable.com/blog/2010/02/25/collaborative-mathematics-future-of-science Collaborative Mathematics and The Future of Science] Javier Tordable, February 26 2010
* [http://www.scientificamerican.com/article.cfm?id=problem-solved-tic-tac-toe-blog Problem Solved, LOL: A Complex Tic-Tac-Toe Puzzle Falls Thanks to Blog Comments] Davide Castelvecchi, Scientific American, March 17 2010
* [http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-toe-and-the-future-of-math/ Blogging, Tic Tac Toe, and the Future of Math] Steve Landsburg, The Big Questions, April 4 2010
* [http://www.siam.org/news/news.php?issue=0043.03 Massively Collaborative Mathematics] Julie Rehmeyer, SIAM News, Volume 43(3), April 2010 (to appear)
* [http://www.princeton.edu/~mbarany/publications.html#WikiSymPolymath `But this is blog maths and we're free to make up conventions as we go along': Polymath1 and the Modalities of `Massively Collaborative Mathematics.'] Michael Barany, Proceedings of the 6th International Symposium on Wikis and Open Collaboration, Gdansk, Poland, 2010.
* [http://www.cs.cmu.edu/~jcransh/papers/cranshaw_kittur.pdf J. Cranshaw and A. Kittur. The Polymath Project: Lessons from a successful online collaboration in mathematics]. In Proceedings of the Conference on Human Factors in Computing Systems, Vancouver, BC, Canada, May 2011.
* [http://www.newscientist.com/article/mg21028113.900-how-to-build-the-global-mathematics-brain.html How to build the global mathematics brain], Jacob Aron, New Scientist, 4 May 2011.
* [http://www.newscientist.com/article/mg21028112.900-mathematics-becomes-more-sociable.html Mathematics becomes more sociable], New Scientist, 5 May 2011.
* [http://polymathprojects.files.wordpress.com/2011/03/polymathias.jpg Mathematical Advances: Lone or Massively Collaborative Endeavors?] from IAS Institute Letter for fall 2010 based on a discussion organized by IAS fall 2010.
* [http://today.uconn.edu/blog/2010/10/will-crowdsourcing-revolutionize-scholarship Will ‘Crowdsourcing’ Revolutionize Scholarship?] An article in UConn Today by Jeremy Teitelbaum, Fall 2010.
* [http://online.wsj.com/article/SB10001424052970204644504576653573191370088.html The New Einsteins Will Be Scientists Who Share] The Wall street journal, October 2011.
Additional links are very welcome.

== Other links ==

* [http://polymathprojects.org/ The polymath blog]
* [http://polymathprojects.org/general-polymath-rules/ General polymath rules]

== Note on anonymous editing ==

To help combat spam, anonymous editing has been disabled, and a captcha system added to hinder automated account creation. If this is causing problems, please email mn@michaelnielsen.org.

== Note on image uploads ==

Image uploads have been disabled, as they were causing problems with spam. If you'd like to upload an image, please email mn@michaelnielsen.org

Main Page

2013-07-26T01:43:34Z

WikiSysop: Reverted edits by AIRDoylewrnrfpi (Talk) to last version by Teorth

{{RightTOC}}
This is the wiki for ''polymath'' projects - massively collaborative online mathematical projects. The idea of such projects originated in Tim Gowers' blog post [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?]

Many polymath projects will be proposed, planned, and run at [http://polymathprojects.org/ This Blog].

A Polymath [[logo]] is being trialled. If you have more suggestions, please add them to the [[logo]] page, or add to the discussion at [[Talk:logo]].

== Existing polymath projects ==

* [[Polymath1]]: New proofs and bounds for the density Hales-Jewett theorem. Initiated Feb 1, 2009; research results have now been published.
* [[Definable Banach Spaces|Polymath2]]: Must an “explicitly defined” Banach space contain <math>c_0</math> or <math>l_p</math>? Initiated Feb 17, 2009; attempts to relaunch via wiki, June 9 2010.
* [[imo 2009 q6|Mini-polymath1]]: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
* [[The polynomial Hirsch conjecture|Polymath3]]. The polynomial Hirsch conjecture. Proposed July 17, 2009; launched, September 30, 2010.
* [[finding primes|Polymath4]]: A deterministic way to find primes. Proposed July 27, 2009; launched Aug 9, 2009. Research results have been accepted for publication.
* [[The Erdős discrepancy problem|Polymath5]]: The Erdős discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010.
* [[imo 2010|Mini-polymath2]]: Solving Problem 5 the 2010 International Mathematical Olympiad. Proposed Jun 12, 2010; launched and solved, Jul 8 2010.
* [[Improving the bounds for Roth's theorem|Polymath6]]: Improving the bounds for Roth's theorem. Proposed Feb 5, 2011.
* [[imo 2011|Mini-polymath3]]: Solving a problem from the 2011 International Mathematical Olympiad. Proposed Jun 9, 2011; launched and solved, Jul 19, 2011.
* [[imo 2012|Mini-polymath4]]: Solving a problem from the 2012 International Mathematical Olympiad. Proposed, Jun 3, 2012; launched, July 12 2012.
* [[The hot spots conjecture|Polymath7]]: Establishing the Hot Spots conjecture for acute-angled triangles. Proposed, May 31st, 2012; launched, Jun 8, 2012.
* [[Bounded gaps between primes|Polymath8]]: Improving the bounds for small gaps between primes. Proposed, June 4, 2013; launched, June 4, 2013.

== Polymath-like projects ==

* [http://theses.portonvictor.org/node/2 Mathematics research projects]
* Scott Aaronson's "philomath project": "[http://scottaaronson.com/blog/?p=453 Sensitivity vs. Block sensitivity]" (see also [http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice this Math Overflow question]). Launched Jul 13, 2010.
* A wiki page clearinghouse for the [[Deolalikar P vs NP paper]]. Launched Aug 10, 2010.
* <del>[http://researchtrends.wikia.com/wiki/Main_Page Math Research Trends Wiki] "research in the middle"</del> This project is recommended to be discontinued in favor of [http://portonmath.wordpress.com/2013/03/23/collaborative-research/ collaborative research at PlanetMath].
* The page for the [[ABC conjecture]] contains links and information about Mochizuki's claimed proof of this conjecture.

== Proposed polymath projects ==

* [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ The cap set problem]. Proposed March 25, 2009 (see also these [http://gilkalai.wordpress.com/2009/05/11/around-the-cap-set-problem-b/ two] [http://gilkalai.wordpress.com/2009/05/18/the-cap-set-problem-and-frankl-rodl-theorem-c/ followup] posts).
* [[Boshernitzan’s problem]]. Proposed July 27, 2009.
* [http://gowers.wordpress.com/2009/09/16/possible-future-polymath-projects/ Possible future polymath projects]. Discussion opened September 16, 2009.
* [http://rjlipton.wordpress.com/2011/05/12/a-possible-polymath-project/ A possible polymath project:] Proposal by Richard Lipton to attack a conjecture due to Erdos, about a class of Diophantine equations.

A (partial) list of proposed projects can be found [http://polymathprojects.org/category/polymath-proposals/ here].

If you have a tentative proposal for a polymath project, you can either make a post on it on your own blog, or place it [[other proposed projects|here]].

== Discussions about polymath ==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] Tim Gowers, January 27, 2009.
* [http://lucatrevisan.wordpress.com/2009/02/01/a-peoples-history-of-mathematics/ A people's history of mathematics] Luca Trevisan, February 1, 2009.
* [http://michaelnielsen.org/blog/?p=553 The polymath project] Michael Nielsen, February 3, 2009.
* [http://www.neverendingbooks.org/index.php/yet-another-math20-proposal.html Yet another math 2.0 proposal] Lieven le Bruyn, February 11, 2009.
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] Tim Gowers, March 10, 2009.
* [http://maxwelldemon.com/2009/03/14/polymath/ Polymath] Edmund Harriss, March 14, 2009.
* [http://science.slashdot.org/article.pl?sid=09/03/18/194228 Massive open collaboration in mathematics declared a success] Slashdot, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=581 How changing the technology of collaboration can change the nature of collaboration] Michael Nielsen, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=584 The polymath project: scope of participation] Michael Nielsen, March 20, 2009.
* [http://gowers.wordpress.com/2009/03/24/can-polymath-be-scaled-up/ Can polymath be scaled up?] Tim Gowers, March 24, 2009.
* [http://whatisresearch.wordpress.com/2009/03/24/concluding-notes-on-the-polymath-project-and-a-challenge/ Concluding notes on the polymath project - and a challenge] Vilpulniak, March 24, 2009.
* [http://michaelnielsen.org/blog/on-scaling-up-the-polymath-project/ On scaling up the polymath project] Michael Nielsen, March 25, 2009.
* [http://numberwarrior.wordpress.com/2009/03/25/a-gentle-introduction-to-the-polymath-project/ A gentle introduction to the polymath project] Jason Dyer, March 25, 2009.
* [http://blogs.telegraph.co.uk/technology/iandouglas/9656357/tim_gowers_and_the_polymaths/ Tim Gowers and the polymaths] Ian Douglas (the Telegraph), April 29, 2009
* [http://terrytao.wordpress.com/2009/07/22/imo-2009-q6-mini-polymath-project-impressions-reflections-analysis/ IMO 2009 Q6 as mini-polymath project: impressions, reflections, analysis] Terence Tao, July 22, 2009.
* [http://polymathprojects.org/2009/07/27/selecting-the-next-polymath-project/ Selecting the next polymath project] Terence Tao, July 27, 2009.
* [http://blog.jonudell.net/2009/07/31/polymath-equals-user-innovatio/ Polymath equals user innovation] Jon Udell, July 31, 2009.
* [http://scienceblogs.com/christinaslisrant/2009/08/an_overview_of_the_polymath_pr.php An overview of the polymath project] Christina Pikas, August 1, 2009
* [http://whatisresearch.wordpress.com/2009/08/09/collaborative-mathematics-etc/ Collaborative mathematics etc.] Vipulniak, August 9, 2009
* [http://www.nature.com/nature/journal/v461/n7266/full/461879a.html Massively collaborative mathematics] Tim Gowers, Michael Nielsen, Nature, October 15, 2009
* [http://portonmath.wordpress.com/2009/10/25/collaborative-research-of-filters/ Collaborative math research – a real example] Victor Porton, October 24, 2009
* [http://whatisresearch.wordpress.com/2009/10/26/polymath-again/ Polymath again] Vipulniak, October 26, 2009
* [http://www.kennislink.nl/publicaties/wiskunde-met-zijn-allen Wiskunde met zijn allen] (Dutch), Alex van den Brandhof, Kennislink, November 12, 2009
* [http://www.sciencenews.org/view/generic/id/50532/title/Mathematics_by_collaboration Mathematics by collaboration], Julie Rehmeyer, ScienceNews, December 8, 2009
* [http://www.nytimes.com/projects/magazine/ideas/2009/#m Massively Collaborative Mathematics], Jordan Ellenberg, The Ninth Annual Year in Ideas, New York Times, 2009.
* [http://www.hypios.com/thinking/2010/01/13/massively-collaborative-mathematics-lessons-from-polymath1/ Massively Collaborative Mathematics: lessons from polymath1], Hypios, Jan 13 2010
* [http://ths1104.wordpress.com/2010/02/13/open-reflexions-sur-fond-de-polymaths/ Open réflexions sur fond de Polymaths] (French), ths1104, Feb 13 2010
* [http://www.javiertordable.com/blog/2010/02/25/collaborative-mathematics-future-of-science Collaborative Mathematics and The Future of Science] Javier Tordable, February 26 2010
* [http://www.scientificamerican.com/article.cfm?id=problem-solved-tic-tac-toe-blog Problem Solved, LOL: A Complex Tic-Tac-Toe Puzzle Falls Thanks to Blog Comments] Davide Castelvecchi, Scientific American, March 17 2010
* [http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-toe-and-the-future-of-math/ Blogging, Tic Tac Toe, and the Future of Math] Steve Landsburg, The Big Questions, April 4 2010
* [http://www.siam.org/news/news.php?issue=0043.03 Massively Collaborative Mathematics] Julie Rehmeyer, SIAM News, Volume 43(3), April 2010 (to appear)
* [http://www.princeton.edu/~mbarany/publications.html#WikiSymPolymath `But this is blog maths and we're free to make up conventions as we go along': Polymath1 and the Modalities of `Massively Collaborative Mathematics.'] Michael Barany, Proceedings of the 6th International Symposium on Wikis and Open Collaboration, Gdansk, Poland, 2010.
* [http://www.cs.cmu.edu/~jcransh/papers/cranshaw_kittur.pdf J. Cranshaw and A. Kittur. The Polymath Project: Lessons from a successful online collaboration in mathematics]. In Proceedings of the Conference on Human Factors in Computing Systems, Vancouver, BC, Canada, May 2011.
* [http://www.newscientist.com/article/mg21028113.900-how-to-build-the-global-mathematics-brain.html How to build the global mathematics brain], Jacob Aron, New Scientist, 4 May 2011.
* [http://www.newscientist.com/article/mg21028112.900-mathematics-becomes-more-sociable.html Mathematics becomes more sociable], New Scientist, 5 May 2011.
* [http://polymathprojects.files.wordpress.com/2011/03/polymathias.jpg Mathematical Advances: Lone or Massively Collaborative Endeavors?] from IAS Institute Letter for fall 2010 based on a discussion organized by IAS fall 2010.
* [http://today.uconn.edu/blog/2010/10/will-crowdsourcing-revolutionize-scholarship Will ‘Crowdsourcing’ Revolutionize Scholarship?] An article in UConn Today by Jeremy Teitelbaum, Fall 2010.
* [http://online.wsj.com/article/SB10001424052970204644504576653573191370088.html The New Einsteins Will Be Scientists Who Share] The Wall street journal, October 2011.
Additional links are very welcome.

== Other links ==

* [http://polymathprojects.org/ The polymath blog]
* [http://polymathprojects.org/general-polymath-rules/ General polymath rules]

== Note on anonymous editing ==

To help combat spam, anonymous editing has been disabled, and a captcha system added to hinder automated account creation. If this is causing problems, please email mn@michaelnielsen.org.

== Note on image uploads ==

Image uploads have been disabled, as they were causing problems with spam. If you'd like to upload an image, please email mn@michaelnielsen.org

W-trick

2013-07-05T10:05:41Z

WikiSysop: Reverted edits by Cheaptara (Talk) to last version by Teorth

The W-trick is a simple trick to remove some of the structure from the set of primes, and also to increase the density of primes slightly. Basically, instead of looking at the set <math>{\mathcal P} := \{2,3,5,7,\ldots\}</math> of primes, one instead looks at the set <math>{\mathcal P}_{W,b} := \{ n: Wn+b \in {\mathcal P} \}</math>, where <math>W := \prod_{p \leq w} p</math> is the product of all primes less than some threshold w, and b is a number coprime to W (in many cases one can just take b=1). It is a result in elementary number theory that <math>W = \exp((1+o(1))w)</math>, thus W is of exponential size in w. If one seeks primes less than N, one must therefore set w no larger than <math>\log N</math> or so.

The set <math>{\mathcal P}_{W,b}</math> is a little bit denser than the primes; the primes less than N have density about <math>1/\log N</math> by the prime number theorem, but <math>{\mathcal P}_{W,b}</math> has density about <math> \frac{W}{\phi(W)} \frac{1}{\log N} \approx \frac{\log w}{\log N}</math>; raising w to <math>O(\log N)</math> (which is the largest feasible value), the density of the W-tricked primes thus increases slightly from <math>1/\log N</math> to about <math>\log \log N / \log N</math>.

The W-tricked primes <math>{\mathcal P}_{W,b}</math> also behave more 'pseudorandomly' than the primes themselves. For instance, the primes are of course highly biased to favour odd numbers over even numbers, but the W-tricked primes have no such bias once w is at least 2 (by the prime number theorem in arithmetic progressions). More generally, the primes do not equidistribute modulo q for any q, but the W-tricked primes do as soon as w is greater than or equal to all the prime factors of q.

Finding narrow admissible tuples

2013-06-16T15:18:40Z

WikiSysop: Reverted edits by WikiSysop (Talk) to last version by AndrewVSutherland

For any natural number <math>k_0</math>, an ''admissible <math>k_0</math>-tuple'' is a finite set <math>{\mathcal H}</math> of integers of cardinality <math>k_0</math> which avoids at least one residue class modulo <math>p</math> for each prime <math>p</math>. (Note that one only needs to check those primes <math>p</math> of size at most <math>k_0</math>, so this is a finitely checkable condition.) Let <math>H(k_0)</math> denote the minimal diameter <math>\max {\mathcal H} - \min {\mathcal H}</math> of an admissible <math>k_0</math>-tuple. As part of the [[Bounded gaps between primes|Polymath8]] project, we would like to find as good an upper bound on <math>H(k_0)</math> as possible for given values of <math>k_0</math>. To a lesser extent, we would also be interested in lower bounds on this quantity. There is some scattered numerical evidence that the optimal value of H is roughly of size <math>k_0 \log k_0 + k_0</math> for <math>k_0</math> in the range of interest.

== Upper bounds ==

Upper bounds are primarily constructed through various "sieves" that delete one residue class modulo <math>p</math> from an interval for a lot of primes <math>p</math>. Examples of sieves, in roughly increasing order of efficiency, are listed below.

=== Zhang sieve ===

The Zhang sieve uses the tuple

:<math>{\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}</math>

where <math>m</math> is taken to optimize the diameter <math>p_{m+k_0}-p_{m+1}</math> while staying admissible (in practice, this basically means making <math>m</math> as small as possible). Certainly any <math>m</math> with <math>p_{m+1} > k_0</math> works; in particular, one can just take <math>{\mathcal H}</math> to be the first <math>k_0</math> primes past <math>k_0</math>, but this is not optimal. Applying the prime number theorem then gives the upper bound <math>H \leq (1+o(1)) k_0\log k_0</math>.

=== Hensley-Richards sieve ===

The Hensley-Richards sieve [HR1973], [HR1973b], [R1974] uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1}\}</math>

where m is again optimised to minimize the diameter while staying admissible.

=== Asymmetric Hensley-Richards sieve ===

The asymmetric Hensley-Richard sieve uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1-i}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1+i}\}</math>

where <math>i</math> is an integer and <math>i,m</math> are optimised to minimize the diameter while staying admissible.

=== Schinzel sieve ===
Given <math>0<y<z<x</math>, the Schinzel sieve (discussed in [S1961], [HR1973], [GR1998], [CJ2001]) sieves the interval <math>[1,x]</math> by <math>1 \bmod p</math> for primes <math>p \le y</math> and by <math>0\bmod p</math> for primes <math>y . Provided that <math>z</math> is large enough (<math>z=k_0</math> clearly suffices), the first <math>k_0</math> survivors form an admissible <math>k_0</math>-tuple (but not necessarily the narrowest one in the interval).
The case <math>y=1</math> corresponds to a sieve of Eratosthenes; if one minimizes <math>z</math> and takes the first <math>k_0</math> survivors greater than 1, this yields the same admissible <math>k_0</math> tuple as Zhang, with the minimal possible value of <math>m</math>.

=== Shifted Schinzel sieve ===
As a generalization of the Schinzel sieve, one may instead sieve shifted intervals <math>[s,s+x]</math>. This is effectively equivalent to sieving the interval <math>[0,x]</math> of the residue classes <math>-s\ \bmod\ p</math> for primes <math>p\le y</math> and <math> 1-s\ \bmod\ p</math> for primes <math>y<p\le z</math>.

=== Greedy sieve ===
Within a given interval, one sieves a single residue class <math>a \bmod p</math> for increasing primes <math>p=2,3,5,\ldots</math>, with <math>a</math> chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize <math>a\in[0,p-1]</math>, maximize <math>a\in [0,p-1]</math>, minimize <math>|a-\lfloor p/2\rfloor|</math>, or randomly. If not all residue classes modulo <math>p</math> are occupied by survivors, then <math>a</math> will be chosen so that no survivors are sieved.
This necessarily occurs once <math>p</math> exceeds the number of survivors but typically happens much sooner. One then chooses the narrowest <math>k_0</math>-tuple <math>{\mathcal H}</math> among the survivors (if there are fewer than <math>k_0</math> survivors, retry with a wider interval).

=== Greedy-greedy sieve ===
Heuristically, the performance of the greedy sieve is significantly improved by starting with a shifted Schinzel sieve on <math>[s,\ s+x]</math> using <math>y = 2</math> and <math>z = \sqrt{x}</math> and then continuing in a greedy fashion, as [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart#comment-23566 proposed by Sutherland]. One first optimizes the shift value <math>s</math> over some larger interval (e.g. <math>[-k_0\log\ k_0,\ k_0\log\ k_0]</math>) and then continues the sieving over primes <math>p > z</math> greedily choosing the best residue class for each prime according to a chosen tie-breaking rule (in Sutherland's original implementation, ties are broken downward in <math>[0,\ p-1]</math>).

=== Seeded greedy sieve ===
Given an initial sequence <math>{\mathcal S}</math> that is known to contain an admissible <math>k_0</math>-tuple, one can apply greedy sieving to the minimal interval containing <math>{\mathcal S}</math> until an admissible sequence of survivors remains, and then choose the narrowest <math>k_0</math>=tuple it contains. The sieving methods above can be viewed as the special case where <math>{\mathcal S}</math> is the set of integers in some interval. The main difference is that the choice of <math>{\mathcal S}</math> affects when ties occur and how they are broken with greedy sieving.
One approach is to take <math>{\mathcal S}</math> to be the union of two <math>k_0</math>-tuples that lie in roughly the same interval (see Iterated merging) below.

=== Iterated merging ===
Given an admissible <math>k_0</math>-tuple <math>\mathcal{H}_1</math>, one can attempt to improve it using an iterated merging approach [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23680 suggested by Castryck]. One first uses a greedy (or greedy-Schinzel) sieve to construct an admissible <math>k_0</math>-tuple <math>\mathcal{H}_2</math> in roughly the same interval as <math>\mathcal{H}_1</math>, then performs a randomized greedy sieve using the seed set <math>\mathcal{S} = \mathcal{H}_1 \cup \mathcal{H}_2</math> to obtain an admissible <math>k_0</math>-tuple <math>\mathcal{H}_3</math>. If <math>\mathcal{H}_3</math> is narrower than <math>\mathcal{H}_2</math>, replace <math>\mathcal{H}_2</math> with <math>\mathcal{H}_3</math>, otherwise try again with a new <math>\mathcal{H}_3</math>.
Eventually the diameter of <math>\mathcal{H}_2</math> will become less than or equal to that of <math>\mathcal{H}_1</math>.
As long as <math>\mathcal{H}_1\ne \mathcal{H}_2</math>, one can continue to attempt to improve <math>\mathcal{H}_2</math>, but in practice one stops after some number of retries.

As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23733 described by Sutherland], one can then replace <math>\mathcal{H}_1</math> with <math>\mathcal{H}_2</math> and begin the process anew, yielding a randomized algorithm that can be run indefinitely. Key parameters to this algorithm are the choice of the interval used when constructing <math>\mathcal{H}_2</math>, which is typically made wider than the minimal interval containing <math>\mathcal{H}_1</math> by a small factor <math>\delta</math> on each side (Sutherland suggests <math>\delta = 0.0025</math>), and the number of failed attempts allowed while attempting to impove <math>\mathcal{H}_2</math>.

Eventually this process will tend to converge to particular <math>\mathcal{H}_1</math> that it cannot improve (or more generally, a set of similar <math>\mathcal{H}_1</math>'s with the same diameter). Interleaving iterated merging with the local optimizations described below often allows the algorithm to make further progress.

----

Iterated merging can be viewed as a form of simulated annealing. The set <math>\mathcal{S}</math> initially contains at least two admissible <math>k_0</math>-tuples (typically many more), and as the algorithm proceeds the set <math>\mathcal{S}</math> converges toward <math>\mathcal{H}_1</math> and the number of admissible <math>k_0</math>-tuples it contains declines. One can regard the cardinality of the difference between <math>\mathcal{S}</math> and <math>\mathcal{H}_1</math> as a measure of the "temperature" of a gradually cooling system, since the number of choices available to the algorithm declines as this cardinality is reduced (more precisely, one may consider the entropy of the possible sequence of tie-breaking choices available for a given <math>\mathcal{S}</math>).

=== Local optimizations ===

Let <math>\mathcal H = \{h_1,\ldots, h_{k_0}\}</math> be an admissible <math>k_0</math>-tuple with endpoints <math>h_1</math> and <math>h_{k_0}</math>, and let <math>\mathcal I</math> be the interval <math>[h_1,h_{k_0}]</math>. If there exists an integer <math>h\in\mathcal I</math> such that removing one of <math>\mathcal H</math>'s endpoints and inserting <math>h</math> yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, then call <math>\mathcal H</math> ''contractible'', and if not, say that <math>\mathcal H</math> non-contractible. Note that <math>\mathcal H'</math> necessarily has smaller diameter than <math>\mathcal H</math>. Any of the sieving methods described above may produce admissible <math>k_0</math>-tuples that are contractible, so it is worth testing for contractibility as a post-processing step after sieving and replacing <math>\mathcal H</math> by <math>\mathcal H'</math> if this test succeeds.

We can also ''shift'' <math>\mathcal H </math> to the left by removing its right end point <math>h_{k_0}</math> and replacing it with the greatest integer <math>h_0 < h_1</math> that yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, and we can similarly shift <math>\mathcal H</math> to the right. The diameter of <math>\mathcal H'</math> need not be less than <math>\mathcal H</math>, but if it is, it provides a useful replacement. More generally, by shifting <math>\mathcal H</math> repeatedly we can produce a sequence of admissible <math>k_0</math>-tuples that lie successively further to the left or right. In general the diameter of these tuples may grow as we do so, but it will also occasionally decline, and we may be able to find a shifted <math>\mathcal H'</math> with smaller diameter than <math>\mathcal H</math>.

----

A more sophisticated local optimization involves a process of ``adjustment" [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23766 proposed by Savitt].
Let <math>\mathcal H </math> be an admissible <math>k_0</math>-tuple.
For a prime <math>p</math> and an integer <math>a</math>, let <math>[a;p]</math> denote the residue class <math>a\bmod p</math>, i.e. the set of integers <math>\{ x : x = a \bmod p\}</math>.
Call <math>[a;p]</math> occupied if it contains an element of <math>\mathcal H </math>.

Suppose that <math>[a;p]</math> and <math>[b;q]</math> are occupied residue classes, for some distinct primes <math>p</math> and <math>q</math>, and that <math>[a';p]</math> and <math>[b';q]</math> are unoccupied.
Let <math>\mathcal U</math> be the intersection of <math>\mathcal H</math> with <math>[a;p] \cup [b;q]</math>, and let <math>\mathcal V</math> be a subset of the integers that lie in the intersection of the interval <math>I</math> containing <math>H</math> and the set <math>[a';p] \cup [b';q]</math> such that
the set <math>\mathcal H' </math> formed by removing the elements of <math>\mathcal U</math> from <math>\mathcal H </math> and adding the elements of <math>\mathcal V </math> is admissible.
A necessary (and often sufficient) condition for and integer <math>v</math> to lie in <math>\mathcal V</math> is that <math>v</math> must not lie in a residue class <math>[c;r]</math> that is the unique unoccupied residue class modulo <math>r</math> for any prime <math>r</math> other than <math>p</math> or <math>q</math>.

The admissible set <math>\mathcal H' </math> lies in the interval <math>\mathcal I</math> containing <math>\mathcal H</math>, so its diameter is no greater than that of <math>\mathcal H</math>, however its cardinality may differ. If it happens that <math>\mathcal H' </math> contains more elements than <math>\mathcal H </math>, then by eliminating points at either end of <math>\mathcal H' </math> we obtain an admissible <math>k_0</math>-tuple that is narrower than <math>\mathcal H</math> and may ``adjust" <math>\mathcal H </math> by replacing it with <math>\mathcal H' </math>.
The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible <math>k_0</math>-tuples.

=== Further refinements ===

== Lower bounds ==

There is a substantial amount of literature on bounding the quantity <math>\pi(x+y)-\pi(x)</math>, the number of primes in a shifted interval <math>[x+1,x+y]</math>, where <math>x,y</math> are natural numbers. As a general rule, whenever a bound of the form

: <math> \pi(x+y) - \pi(x) \leq F(y) </math> (*)

is established for some function <math>F(y)</math> of <math>y</math>, the method of proof also gives a bound of the form

: <math> k_0 \leq F( H(k_0)+1 ).</math> (**)

Indeed, if one assumes the prime tuples conjecture, any admissible <math>k_0</math>-tuple of diameter <math>H</math> can be translated into an interval of the form <math>[x+1,x+H+1]</math> for some <math>x</math>. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for <math>x>y</math>, the set of primes between <math>x+1</math> and <math>x+y</math> is admissible, so the method of proof of (*) invariably also gives (**) as well.

Examples of lower bounds are as follows;

=== Brun-Titchmarsh inequality ===

The Brun-Titchmarsh theorem gives

: <math> \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}</math>

which then gives the lower bound

: <math> H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0</math>.

Montgomery and Vaughan deleted the o(1) error from the Brun-Titchmarsh theorem [MV1973, Corollary 2], giving the more precise inequality

: <math> k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.</math>

=== First Montgomery-Vaughan large sieve inequality ===

The first Montgomery-Vaughan large sieve inequality [MV1973, Theorem 1] gives

: <math> k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2</math>

for any <math>Q > 1</math>, which is a parameter that one can optimise over (the optimal value is comparable to <math>H(k_0)^{1/2}</math>).

=== Second Montgomery-Vaughan large sieve inequality ===

The second Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] gives

: <math> k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1}</math>

for any <math>z > 1</math>, which is a parameter similar to <math>Q</math> in the previous inequality, and <math>c</math> is an absolute constant. In the original paper of Montgomery and Vaughan, <math>c</math> was taken to be <math>3/2</math>; this was then reduced to <math>\sqrt{22}/\pi</math> [B1995, p.162] and then to <math>3.2/\pi</math> [M1978]. It is conjectured that <math>c</math> can be taken to in fact be <math>1</math>.

== Benchmarks ==

Efforts to fill in the blank fields in this table are very welcome.

{| border=1
|-
!<math>k_0</math>!!3,500,000!! 181,000 !! 34,429 !! 26,024 !! 23,283 !! 22,949 || 10,719 !! 6,329 || 5,000
|-
! Upper bounds
|-
| First <math>k_0</math> primes past <math>k_0</math>
| [http://arxiv.org/abs/1305.6369 59,874,594]
| 2,530,338
| 420,878
| 310,134
| 275,082
| 270,698
| 117,714
|
| 50,840
|-
|Zhang sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 59,093,364]
| [http://math.mit.edu/~drew/admissible_181000_2486370.txt 2,486,370]
| [http://math.mit.edu/~drew/admissible_34429_411932.txt 411,932]
| [http://math.mit.edu/~drew/admissible_26024_303558.txt 303,558]
| [http://math.mit.edu/~drew/admissible_23282_268536.txt 268,536]
| [http://math.mit.edu/~drew/admissible_22949_264414.txt 264,414]
| [http://math.mit.edu/~drew/admissible_10719_114806.txt 114,806]
| [http://math.mit.edu/~drew/admissible_6329_64176.txt 64,176]
| [http://math.mit.edu/~drew/admissible_5000_49578.txt 49,578]
|-
|Hensley-Richards sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2422558.txt 2,422,558]
| [http://math.mit.edu/~drew/admissible_34429_402790.txt 402,790]
| [http://math.mit.edu/~drew/admissible_26024_297454.txt 297,454]
| [http://math.mit.edu/~drew/admissible_23283_262794.txt 262,794]
| [http://math.mit.edu/~drew/admissible_22949_258780.txt 258,780]
| [http://math.mit.edu/~drew/admissible_10719_112868.txt 112,868]
|
| [http://math.mit.edu/~drew/admissible_5000_48634.txt 48,634]
|-
|Asymmetric Hensley-Richards
|
| [http://math.mit.edu/~drew/admissible_181000_2418054.txt 2,418,054]
| [http://math.mit.edu/~drew/admissible_34429_401700.txt 401,700]
| [http://math.mit.edu/~drew/admissible_26024_296154.txt 296,154]
| [http://math.mit.edu/~drew/admissible_23283_262286.txt 262,286]
| [http://math.mit.edu/~drew/admissible_22949_258302.txt 258,302]
| [http://math.mit.edu/~drew/admissible_10719_112562.txt 112,562]
|
| [http://math.mit.edu/~drew/admissible_5000_48484.txt 48,484]
|-
|Shifted Schinzel sieve
|
| [http://math.mit.edu/~drew/admissible_181000_2413228.txt 2,413,228]
| [http://math.mit.edu/~drew/admissible_34429_400512.txt 400,512]
| [http://math.mit.edu/~drew/admissible_26024_295162.txt 295,162]
| [http://math.mit.edu/~drew/admissible_23283_262206.txt 262,206]
| [http://math.mit.edu/~drew/admissible_22949_258000.txt 258,000]
| [http://math.mit.edu/~drew/admissible_10719_112440.txt 112,440]
|
| [http://math.mit.edu/~drew/admissible_5000_48726.txt 48,726]
|-
| Greedy-greedy sieve
|
| [http://math.mit.edu/~drew/admissible_181000_2326476.txt 2,326,476]
| [http://math.mit.edu/~drew/admissible_34429_388076.txt 388,076]
| [http://math.mit.edu/~drew/admissible_26024_286308.txt 286,308]
| [http://math.mit.edu/~drew/admissible_23283_253968.txt 253,968]
| [http://math.mit.edu/~drew/admissible_22949_249992.txt 249,992]
| [http://math.mit.edu/~drew/admissible_10719_108694.txt 108,694]
|
| [http://math.mit.edu/~drew/admissible_5000_46968.txt 46,968]
|-
|Best known tuple
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2326476.txt 2,326,476]
| [http://math.mit.edu/~drew/admissible_34429_386382.txt 386,382]
| [http://math.mit.edu/~drew/admissible_26024_285210.txt 285,210]
| [http://math.mit.edu/~drew/admissible_23283_252804.txt 252,804]
| [http://math.mit.edu/~drew/admissible_22949_248898.txt 248,898]
| [http://math.mit.edu/~drew/admissible_10719_108462.txt 108,462]
| [http://math.mit.edu/~drew/admissible_6329_60744.txt 60,744]
| [http://math.mit.edu/~drew/admissible_5000_46824.txt 46,824]
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 56,238,957
| 2,372,232
| 394,096
| 290,604
| 257,405
| 253,381
| 110,119
| 61,727
| 47,586
|-
! Lower bounds
|-
|MV with <math>c=1</math> (conjectural)
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 32,503,908]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 1,395,694]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 234,872]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 173,420]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 153,691]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 151,298]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 66,314]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 37,274]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 28,781]
|-
|MV with <math>c=3.2/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 32,469,985]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 1,393,869]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 234,529]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 173,140]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 153,447]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 151,056]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 66,211]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 37,207]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 28,737]
|-
|MV with <math>c=\sqrt{22}/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 31,765,216]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 1,357,096]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23641 227,078]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,860]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 148,719]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 146,393]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 63,917]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 35,903]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 27,708]
|-
|Second Montgomery-Vaughan
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 31,756,667]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 1,356,644]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23634 226,987]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,793]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 148,656]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 146,338]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 63,886]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 35,887]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 27,696]
|-
|Brun-Titchmarsh
| 30,137,225
| 1,272,083
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23611 211,046]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555]
| 137,756
| 135,599
| 58,863
| 32,916
| 25,351
|-
|First Montgomery-Vaughan
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 28,080,007]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 1,184,954]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 196,729]
196,719

[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 197,096]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 145,711]
145,461
| 128,971
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 126,931]
| 55,149
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 55,178]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 30,982]
| 24,012
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 24,037]
|}

{| border=1
|-
!<math>k_0</math> !! 4,000 !! 3,000 !! 2,000 !! 1,000 !! 672
|-
! Upper bounds
|-
| First <math>k_0</math> primes past <math>k_0</math>
| 39,660
| 28,972
| 18,386
| 8,424
| 5,406
|-
|Zhang sieve
| [http://math.mit.edu/~drew/admissible_4000_38596.txt 38,596]
| [http://math.mit.edu/~drew/admissible_3000_28008.txt 28,008]
| [http://math.mit.edu/~drew/admissible_2000_17766.txt 17,766]
| [http://math.mit.edu/~drew/admissible_1000_8212.txt 8,212]
| [http://math.mit.edu/~drew/admissible_672_5216.txt 5,216]
|-
|Hensley-Richards sieve
| [http://math.mit.edu/~drew/admissible_4000_38498.txt 38,498]
| [http://math.mit.edu/~drew/admissible_3000_27806.txt 27,806]
| [http://math.mit.edu/~drew/admissible_2000_17726.txt 17,726]
| [http://math.mit.edu/~drew/admissible_1000_8258.txt 8,258]
| [http://math.mit.edu/~drew/admissible_672_5314.txt 5,314]
|-
|Asymmetric Hensley-Richards
| [http://math.mit.edu/~drew/admissible_4000_37932.txt 37,932]
| [http://math.mit.edu/~drew/admissible_3000_27638.txt 27,638]
| [http://math.mit.edu/~drew/admissible_2000_17676.txt 17,676]
| [http://math.mit.edu/~drew/admissible_1000_8168.txt 8,168]
| [http://math.mit.edu/~drew/admissible_672_5220.txt 5,220]
|-
|Shifted Schinzel sieve
| [http://math.mit.edu/~drew/admissible_4000_38168.txt 38,168]
| [http://math.mit.edu/~drew/admissible_3000_27632.txt 27,632]
| [http://math.mit.edu/~drew/admissible_2000_17616.txt 17,616]
| [http://math.mit.edu/~drew/admissible_1000_8160.txt 8,160]
| [http://math.mit.edu/~drew/admissible_672_5196.txt 5,196]
|-
| Greedy-greedy sieve
| [http://math.mit.edu/~drew/admissible_4000_36756.txt 36,756]
| [http://math.mit.edu/~drew/admissible_3000_26754.txt 26,754]
| [http://math.mit.edu/~drew/admissible_2000_17054.txt 17,054]
| [http://math.mit.edu/~drew/admissible_1000_7854.txt 7,854]
| [http://math.mit.edu/~drew/admissible_672_5030.txt 5,030]
|-
|Best known tuple
| [http://math.mit.edu/~drew/admissible_4000_36636.txt 36,636*]
| [http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_3000_26606_-29486.txt 26,606]
| [http://math.mit.edu/~drew/admissible_2000_16984.txt 16,984*]
| [http://math.mit.edu/~drew/admissible_1000_7806.txt 7,806*]
| [http://math.mit.edu/~drew/admissible_672_5010.txt 5,010*]
|-
| Engelsma data
| 36,622
| 26,622
| 16,978
| 7,802
| 4,998
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 37,176
| 27,019
| 17,202
| 7,907
| 5,046
|-
! Lower bounds
|-
|MV with <math>c=1</math> (conjectural)
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 22,564]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 16,456]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,500]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,858]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 3,124]
|-
|MV with <math>c=3.2/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 22,523]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 16,428]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,480]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,847]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 3,118]
|-
|MV with <math>c=\sqrt{22}/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 21,701]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 15,758]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,061]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,648]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 2,979]
|-
|Second Montgomery-Vaughan
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 21,690]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 15,751]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,056]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,645]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 2,977]
|-
|Brun-Titchmarsh
| 19,785
| 14,358
| 9,118
| 4,167
| 2,648
|-
|First Montgomery-Vaughan
| 18,768
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 18,859]
| 13,696
| 8,448
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 8,615]
| 3,959
| 2,558
|}

<nowiki>*</nowiki> indicates that the widths listed are the best known tuples that have been found by the methods that gave the entries for larger values of <math>k_0</math>, but are not as narrow as the literally best known tuples ([http://www.opertech.com/primes/k-tuples.html due to Engelsma]).

For the Zhang tuples the optimal <math>m < \pi(10^{10})</math> that produced an admissible <math>k_0</math>-tuple was used. This is not always the least <math>m</math> that produces an admissible <math>k_0</math>-tuple; for <math>k_0=</math>22,949, for example, the minimal <math>m=</math>586 yields an admissible <math>k_0</math>-tuple of diameter of 264,460, but <math>m=</math>599 yields a narrower admissible <math>k_0</math>-tuple with the listed diameter of 264,414. A list of table entries for which this occurs can be found [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23917 here] (and also for <math>k_0</math>=6,329).

The shifted Schinzel tuples were generated with <math>y=2</math> using an optimally chosen interval contained in <math>[-k_0\log k_0, k_0\log k_0]</math> (the interval is not in every case guaranteed to be optimal, particularly for larger values of <math>k_0</math>, but it is believed to be so).

The greedy-greedy tuples were generated using Sutherland's original algorithm, breaking ties downward in every case (and the optimal interval in <math>[-k_0\log k_0, k_0\log k_0]</math> was selected on this basis).
As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23588 noted by Castryck], breaking ties upward may produce better results in some cases.

Finding narrow admissible tuples

2013-06-16T15:18:27Z

WikiSysop: test

Bounded gaps between primes

2013-06-10T19:12:05Z

2013-06-04T13:13:05Z

WikiSysop: Removing note about accounts

{{RightTOC}}
This is the wiki for ''polymath'' projects - massively collaborative online mathematical projects. The idea of such projects originated in Tim Gowers' blog post [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?]

Many polymath projects will be proposed, planned, and run at [http://polymathprojects.org/ This Blog].

A Polymath [[logo]] is being trialled. If you have more suggestions, please add them to the [[logo]] page, or add to the discussion at [[Talk:logo]].

== Existing polymath projects ==

* [[Polymath1]]: New proofs and bounds for the density Hales-Jewett theorem. Initiated Feb 1, 2009; research results have now been published.
* [[Definable Banach Spaces|Polymath2]]: Must an “explicitly defined” Banach space contain <math>c_0</math> or <math>l_p</math>? Initiated Feb 17, 2009; attempts to relaunch via wiki, June 9 2010.
* [[imo 2009 q6|Mini-polymath1]]: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
* [[The polynomial Hirsch conjecture|Polymath3]]. The polynomial Hirsch conjecture. Proposed July 17, 2009; launched, September 30, 2010.
* [[finding primes|Polymath4]]: A deterministic way to find primes. Proposed July 27, 2009; launched Aug 9, 2009. Research results have been accepted for publication.
* [[The Erdős discrepancy problem|Polymath5]]: The Erdős discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010.
* [[imo 2010|Mini-polymath2]]: Solving Problem 5 the 2010 International Mathematical Olympiad. Proposed Jun 12, 2010; launched and solved, Jul 8 2010.
* [[Improving the bounds for Roth's theorem|Polymath6]]: Improving the bounds for Roth's theorem. Proposed Feb 5, 2011.
* [[imo 2011|Mini-polymath3]]: Solving a problem from the 2011 International Mathematical Olympiad. Proposed Jun 9, 2011; launched and solved, Jul 19, 2011.
* [[imo 2012|Mini-polymath4]]: Solving a problem from the 2012 International Mathematical Olympiad. Proposed, Jun 3, 2012; launched, July 12 2012.
* [[The hot spots conjecture|Polymath7]]: Establishing the Hot Spots conjecture for acute-angled triangles. Proposed, May 31st, 2012; launched, Jun 8, 2012.

== Polymath-like projects ==

* [http://theses.portonvictor.org/node/2 Mathematics research projects]
* Scott Aaronson's "philomath project": "[http://scottaaronson.com/blog/?p=453 Sensitivity vs. Block sensitivity]" (see also [http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice this Math Overflow question]). Launched Jul 13, 2010.
* A wiki page clearinghouse for the [[Deolalikar P vs NP paper]]. Launched Aug 10, 2010.
* <del>[http://researchtrends.wikia.com/wiki/Main_Page Math Research Trends Wiki] "research in the middle"</del> This project is recommended to be discontinued in favor of [http://portonmath.wordpress.com/2013/03/23/collaborative-research/ collaborative research at PlanetMath].
* The page for the [[ABC conjecture]] contains links and information about Mochizuki's claimed proof of this conjecture.

== Proposed polymath projects ==

* [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ The cap set problem]. Proposed March 25, 2009 (see also these [http://gilkalai.wordpress.com/2009/05/11/around-the-cap-set-problem-b/ two] [http://gilkalai.wordpress.com/2009/05/18/the-cap-set-problem-and-frankl-rodl-theorem-c/ followup] posts).
* [[Boshernitzan’s problem]]. Proposed July 27, 2009.
* [http://gowers.wordpress.com/2009/09/16/possible-future-polymath-projects/ Possible future polymath projects]. Discussion opened September 16, 2009.
* [http://rjlipton.wordpress.com/2011/05/12/a-possible-polymath-project/ A possible polymath project:] Proposal by Richard Lipton to attack a conjecture due to Erdos, about a class of Diophantine equations.

A (partial) list of proposed projects can be found [http://polymathprojects.org/category/polymath-proposals/ here].

If you have a tentative proposal for a polymath project, you can either make a post on it on your own blog, or place it [[other proposed projects|here]].

== Discussions about polymath ==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] Tim Gowers, January 27, 2009.
* [http://lucatrevisan.wordpress.com/2009/02/01/a-peoples-history-of-mathematics/ A people's history of mathematics] Luca Trevisan, February 1, 2009.
* [http://michaelnielsen.org/blog/?p=553 The polymath project] Michael Nielsen, February 3, 2009.
* [http://www.neverendingbooks.org/index.php/yet-another-math20-proposal.html Yet another math 2.0 proposal] Lieven le Bruyn, February 11, 2009.
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] Tim Gowers, March 10, 2009.
* [http://maxwelldemon.com/2009/03/14/polymath/ Polymath] Edmund Harriss, March 14, 2009.
* [http://science.slashdot.org/article.pl?sid=09/03/18/194228 Massive open collaboration in mathematics declared a success] Slashdot, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=581 How changing the technology of collaboration can change the nature of collaboration] Michael Nielsen, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=584 The polymath project: scope of participation] Michael Nielsen, March 20, 2009.
* [http://gowers.wordpress.com/2009/03/24/can-polymath-be-scaled-up/ Can polymath be scaled up?] Tim Gowers, March 24, 2009.
* [http://whatisresearch.wordpress.com/2009/03/24/concluding-notes-on-the-polymath-project-and-a-challenge/ Concluding notes on the polymath project - and a challenge] Vilpulniak, March 24, 2009.
* [http://michaelnielsen.org/blog/on-scaling-up-the-polymath-project/ On scaling up the polymath project] Michael Nielsen, March 25, 2009.
* [http://numberwarrior.wordpress.com/2009/03/25/a-gentle-introduction-to-the-polymath-project/ A gentle introduction to the polymath project] Jason Dyer, March 25, 2009.
* [http://blogs.telegraph.co.uk/technology/iandouglas/9656357/tim_gowers_and_the_polymaths/ Tim Gowers and the polymaths] Ian Douglas (the Telegraph), April 29, 2009
* [http://terrytao.wordpress.com/2009/07/22/imo-2009-q6-mini-polymath-project-impressions-reflections-analysis/ IMO 2009 Q6 as mini-polymath project: impressions, reflections, analysis] Terence Tao, July 22, 2009.
* [http://polymathprojects.org/2009/07/27/selecting-the-next-polymath-project/ Selecting the next polymath project] Terence Tao, July 27, 2009.
* [http://blog.jonudell.net/2009/07/31/polymath-equals-user-innovatio/ Polymath equals user innovation] Jon Udell, July 31, 2009.
* [http://scienceblogs.com/christinaslisrant/2009/08/an_overview_of_the_polymath_pr.php An overview of the polymath project] Christina Pikas, August 1, 2009
* [http://whatisresearch.wordpress.com/2009/08/09/collaborative-mathematics-etc/ Collaborative mathematics etc.] Vipulniak, August 9, 2009
* [http://www.nature.com/nature/journal/v461/n7266/full/461879a.html Massively collaborative mathematics] Tim Gowers, Michael Nielsen, Nature, October 15, 2009
* [http://portonmath.wordpress.com/2009/10/25/collaborative-research-of-filters/ Collaborative math research – a real example] Victor Porton, October 24, 2009
* [http://whatisresearch.wordpress.com/2009/10/26/polymath-again/ Polymath again] Vipulniak, October 26, 2009
* [http://www.kennislink.nl/publicaties/wiskunde-met-zijn-allen Wiskunde met zijn allen] (Dutch), Alex van den Brandhof, Kennislink, November 12, 2009
* [http://www.sciencenews.org/view/generic/id/50532/title/Mathematics_by_collaboration Mathematics by collaboration], Julie Rehmeyer, ScienceNews, December 8, 2009
* [http://www.nytimes.com/projects/magazine/ideas/2009/#m Massively Collaborative Mathematics], Jordan Ellenberg, The Ninth Annual Year in Ideas, New York Times, 2009.
* [http://www.hypios.com/thinking/2010/01/13/massively-collaborative-mathematics-lessons-from-polymath1/ Massively Collaborative Mathematics: lessons from polymath1], Hypios, Jan 13 2010
* [http://ths1104.wordpress.com/2010/02/13/open-reflexions-sur-fond-de-polymaths/ Open réflexions sur fond de Polymaths] (French), ths1104, Feb 13 2010
* [http://www.javiertordable.com/blog/2010/02/25/collaborative-mathematics-future-of-science Collaborative Mathematics and The Future of Science] Javier Tordable, February 26 2010
* [http://www.scientificamerican.com/article.cfm?id=problem-solved-tic-tac-toe-blog Problem Solved, LOL: A Complex Tic-Tac-Toe Puzzle Falls Thanks to Blog Comments] Davide Castelvecchi, Scientific American, March 17 2010
* [http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-toe-and-the-future-of-math/ Blogging, Tic Tac Toe, and the Future of Math] Steve Landsburg, The Big Questions, April 4 2010
* [http://www.siam.org/news/news.php?issue=0043.03 Massively Collaborative Mathematics] Julie Rehmeyer, SIAM News, Volume 43(3), April 2010 (to appear)
* [http://www.princeton.edu/~mbarany/publications.html#WikiSymPolymath `But this is blog maths and we're free to make up conventions as we go along': Polymath1 and the Modalities of `Massively Collaborative Mathematics.'] Michael Barany, Proceedings of the 6th International Symposium on Wikis and Open Collaboration, Gdansk, Poland, 2010.
* [http://www.cs.cmu.edu/~jcransh/papers/cranshaw_kittur.pdf J. Cranshaw and A. Kittur. The Polymath Project: Lessons from a successful online collaboration in mathematics]. In Proceedings of the Conference on Human Factors in Computing Systems, Vancouver, BC, Canada, May 2011.
* [http://www.newscientist.com/article/mg21028113.900-how-to-build-the-global-mathematics-brain.html How to build the global mathematics brain], Jacob Aron, New Scientist, 4 May 2011.
* [http://www.newscientist.com/article/mg21028112.900-mathematics-becomes-more-sociable.html Mathematics becomes more sociable], New Scientist, 5 May 2011.
* [http://polymathprojects.files.wordpress.com/2011/03/polymathias.jpg Mathematical Advances: Lone or Massively Collaborative Endeavors?] from IAS Institute Letter for fall 2010 based on a discussion organized by IAS fall 2010.
* [http://today.uconn.edu/blog/2010/10/will-crowdsourcing-revolutionize-scholarship Will ‘Crowdsourcing’ Revolutionize Scholarship?] An article in UConn Today by Jeremy Teitelbaum, Fall 2010.
* [http://online.wsj.com/article/SB10001424052970204644504576653573191370088.html The New Einsteins Will Be Scientists Who Share] The Wall street journal, October 2011.
Additional links are very welcome.

== Other links ==

* [http://polymathprojects.org/ The polymath blog]
* [http://polymathprojects.org/general-polymath-rules/ General polymath rules]

== Note on anonymous editing ==

To help combat spam, anonymous editing has been disabled, and a captcha system added to hinder automated account creation. If this is causing problems, please email mn@michaelnielsen.org.

== Note on image uploads ==

Image uploads have been disabled, as they were causing problems with spam. If you'd like to upload an image, please email mn@michaelnielsen.org

Talk:Main Page

2013-04-13T15:59:58Z

WikiSysop: Test edit

== Polymath Logo ==

It would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

:Done. A logo is being trialled. [[User:MichaelNielsen|MichaelNielsen]] 00:59, 14 December 2012 (UTC)

== Links ==

* ?!? wikisysop whats the problem with the [[Jun Fukuyama's P≠NP Paper]] link? [[User:vzn|vzn]] 12/9/2012

: ... [earlier conversation]

::Returning to this conversation after a couple of days of other commitments intervened. Note that I'm now signed in as [[User:MichaelNielsen|MichaelNielsen]], which seems more appropriate than my WikiSysop login. [[User:MichaelNielsen|MichaelNielsen]] 01:02, 14 December 2012 (UTC)

::To the issue: it wasn't at all clear that you were proposing a collaborative evaluation of his proof. Now that you have, I quite agree that it'd be good to have a sensible process for proposing problems on the wiki. At the moment those have mostly been going on the page [[Other proposed projects]], which is linked prominently on the main page. At present I don't see a problem with putting this proposal on that page. What do you think? [[User:MichaelNielsen|MichaelNielsen]] 01:08, 14 December 2012 (UTC)

::Over the longer run (and independent of this particular proposal), there is a real issue, which is that we need some better process for deciding what's a reasonable way of proposing projects, which is both open enough, but also doesn't waste people's time on uninteresting proposals. This seems like a tricky balance to get right. In an ideal world, wiki software would make it so users only saw things which will be of interest to them. Unfortunately, we don't yet live in that world. [[User:MichaelNielsen|MichaelNielsen]] 01:11, 14 December 2012 (UTC)

== Misc ==

* could someone fix the editing help link on the bottom of the wiki edit page & on home page? isnt there a built in help page for this wiki software? it currently leads to [http://michaelnielsen.org/polymath1/index.php?title=Help:Contents empty page]. not very user friendly eh? in particular is there a tag that substitutes in the current time for discussion edits? [[user:vzn|vzn]] 12/10/2012

: software is apparently [http://www.mediawiki.org/wiki/Help:Contents mediawiki]? [[User:Vzn|Vzn]] 19:08, 31 December 2012 (UTC)

* idea: some kind of voting/weighting/ranking system for prioritizing/sorting projects and gauging user interest/support [[user:vzn|vzn]] 12/10/2012 

: note that stackexchange (used by [http://mathoverflow.net mathoverflow]) has very neat capabilities and functionality. imagine a stackexchange dedicated to polymath. this would allow voting on polymath-related items such as proposals, partial results/directions/ideas etc. unfortunately the stackexchange requirements for membership base are high, it possibly requires a few hundred users minimum to commit, but maybe they could consider a special worthwhile case? new stackexchange proposals are on [http://area51.stackexchange.com area51]. [[User:Vzn|Vzn]] 17:23, 28 December 2012 (UTC)

== Test edit ==

Please ignore. --[[User:WikiSysop|WikiSysop]] 15:59, 13 April 2013 (UTC)

Main Page

2013-01-17T13:30:55Z

WikiSysop:

{{RightTOC}}
This is the wiki for ''polymath'' projects - massively collaborative online mathematical projects. The idea of such projects originated in Tim Gowers' blog post [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?]

Many polymath projects will be proposed, planned, and run at [http://polymathprojects.org/ This Blog].

A Polymath [[logo]] is being trialled. If you have more suggestions, please add them to the [[logo]] page, or add to the discussion at [[Talk:logo]].

Jan 17, 2013: The creation of new accounts is temporarily suspended, due to spam. Please email mn@michaelnielsen.org if you'd like an account set up.

== Existing polymath projects ==

* [[Polymath1]]: New proofs and bounds for the density Hales-Jewett theorem. Initiated Feb 1, 2009; research results have now been published.
* [[Definable Banach Spaces|Polymath2]]: Must an “explicitly defined” Banach space contain <math>c_0</math> or <math>l_p</math>? Initiated Feb 17, 2009; attempts to relaunch via wiki, June 9 2010.
* [[imo 2009 q6|Mini-polymath1]]: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
* [[The polynomial Hirsch conjecture|Polymath3]]. The polynomial Hirsch conjecture. Proposed July 17, 2009; launched, September 30, 2010.
* [[finding primes|Polymath4]]: A deterministic way to find primes. Proposed July 27, 2009; launched Aug 9, 2009. Research results have been accepted for publication.
* [[The Erdős discrepancy problem|Polymath5]]: The Erdős discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010.
* [[imo 2010|Mini-polymath2]]: Solving Problem 5 the 2010 International Mathematical Olympiad. Proposed Jun 12, 2010; launched and solved, Jul 8 2010.
* [[Improving the bounds for Roth's theorem|Polymath6]]: Improving the bounds for Roth's theorem. Proposed Feb 5, 2011.
* [[imo 2011|Mini-polymath3]]: Solving a problem from the 2011 International Mathematical Olympiad. Proposed Jun 9, 2011; launched and solved, Jul 19, 2011.
* [[imo 2012|Mini-polymath4]]: Solving a problem from the 2012 International Mathematical Olympiad. Proposed, Jun 3, 2012; launched, July 12 2012.
* [[The hot spots conjecture|Polymath7]]: Establishing the Hot Spots conjecture for acute-angled triangles. Proposed, May 31st, 2012; launched, Jun 8, 2012.

== Polymath-like projects ==

* Scott Aaronson's "philomath project": "[http://scottaaronson.com/blog/?p=453 Sensitivity vs. Block sensitivity]" (see also [http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice this Math Overflow question]). Launched Jul 13, 2010.
* A wiki page clearinghouse for the [[Deolalikar P vs NP paper]]. Launched Aug 10, 2010.
* [http://researchtrends.wikia.com/wiki/Main_Page Math Research Trends Wiki] "research in the middle"
* The page for the [[ABC conjecture]] contains links and information about Mochizuki's claimed proof of this conjecture.

== Proposed polymath projects ==

* [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ The cap set problem]. Proposed March 25, 2009 (see also these [http://gilkalai.wordpress.com/2009/05/11/around-the-cap-set-problem-b/ two] [http://gilkalai.wordpress.com/2009/05/18/the-cap-set-problem-and-frankl-rodl-theorem-c/ followup] posts).
* [[Boshernitzan’s problem]]. Proposed July 27, 2009.
* [http://gowers.wordpress.com/2009/09/16/possible-future-polymath-projects/ Possible future polymath projects]. Discussion opened September 16, 2009.
* [http://rjlipton.wordpress.com/2011/05/12/a-possible-polymath-project/ A possible polymath project:] Proposal by Richard Lipton to attack a conjecture due to Erdos, about a class of Diophantine equations.

A (partial) list of proposed projects can be found [http://polymathprojects.org/category/polymath-proposals/ here].

If you have a tentative proposal for a polymath project, you can either make a post on it on your own blog, or place it [[other proposed projects|here]].

== Discussions about polymath ==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] Tim Gowers, January 27, 2009.
* [http://lucatrevisan.wordpress.com/2009/02/01/a-peoples-history-of-mathematics/ A people's history of mathematics] Luca Trevisan, February 1, 2009.
* [http://michaelnielsen.org/blog/?p=553 The polymath project] Michael Nielsen, February 3, 2009.
* [http://www.neverendingbooks.org/index.php/yet-another-math20-proposal.html Yet another math 2.0 proposal] Lieven le Bruyn, February 11, 2009.
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] Tim Gowers, March 10, 2009.
* [http://maxwelldemon.com/2009/03/14/polymath/ Polymath] Edmund Harriss, March 14, 2009.
* [http://science.slashdot.org/article.pl?sid=09/03/18/194228 Massive open collaboration in mathematics declared a success] Slashdot, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=581 How changing the technology of collaboration can change the nature of collaboration] Michael Nielsen, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=584 The polymath project: scope of participation] Michael Nielsen, March 20, 2009.
* [http://gowers.wordpress.com/2009/03/24/can-polymath-be-scaled-up/ Can polymath be scaled up?] Tim Gowers, March 24, 2009.
* [http://whatisresearch.wordpress.com/2009/03/24/concluding-notes-on-the-polymath-project-and-a-challenge/ Concluding notes on the polymath project - and a challenge] Vilpulniak, March 24, 2009.
* [http://michaelnielsen.org/blog/on-scaling-up-the-polymath-project/ On scaling up the polymath project] Michael Nielsen, March 25, 2009.
* [http://numberwarrior.wordpress.com/2009/03/25/a-gentle-introduction-to-the-polymath-project/ A gentle introduction to the polymath project] Jason Dyer, March 25, 2009.
* [http://blogs.telegraph.co.uk/technology/iandouglas/9656357/tim_gowers_and_the_polymaths/ Tim Gowers and the polymaths] Ian Douglas (the Telegraph), April 29, 2009
* [http://terrytao.wordpress.com/2009/07/22/imo-2009-q6-mini-polymath-project-impressions-reflections-analysis/ IMO 2009 Q6 as mini-polymath project: impressions, reflections, analysis] Terence Tao, July 22, 2009.
* [http://polymathprojects.org/2009/07/27/selecting-the-next-polymath-project/ Selecting the next polymath project] Terence Tao, July 27, 2009.
* [http://blog.jonudell.net/2009/07/31/polymath-equals-user-innovatio/ Polymath equals user innovation] Jon Udell, July 31, 2009.
* [http://scienceblogs.com/christinaslisrant/2009/08/an_overview_of_the_polymath_pr.php An overview of the polymath project] Christina Pikas, August 1, 2009
* [http://whatisresearch.wordpress.com/2009/08/09/collaborative-mathematics-etc/ Collaborative mathematics etc.] Vipulniak, August 9, 2009
* [http://www.nature.com/nature/journal/v461/n7266/full/461879a.html Massively collaborative mathematics] Tim Gowers, Michael Nielsen, Nature, October 15, 2009
* [http://portonmath.wordpress.com/2009/10/25/collaborative-research-of-filters/ Collaborative math research – a real example] Victor Porton, October 24, 2009
* [http://whatisresearch.wordpress.com/2009/10/26/polymath-again/ Polymath again] Vipulniak, October 26, 2009
* [http://www.kennislink.nl/publicaties/wiskunde-met-zijn-allen Wiskunde met zijn allen] (Dutch), Alex van den Brandhof, Kennislink, November 12, 2009
* [http://www.sciencenews.org/view/generic/id/50532/title/Mathematics_by_collaboration Mathematics by collaboration], Julie Rehmeyer, ScienceNews, December 8, 2009
* [http://www.nytimes.com/projects/magazine/ideas/2009/#m Massively Collaborative Mathematics], Jordan Ellenberg, The Ninth Annual Year in Ideas, New York Times, 2009.
* [http://www.hypios.com/thinking/2010/01/13/massively-collaborative-mathematics-lessons-from-polymath1/ Massively Collaborative Mathematics: lessons from polymath1], Hypios, Jan 13 2010
* [http://ths1104.wordpress.com/2010/02/13/open-reflexions-sur-fond-de-polymaths/ Open réflexions sur fond de Polymaths] (French), ths1104, Feb 13 2010
* [http://www.javiertordable.com/blog/2010/02/25/collaborative-mathematics-future-of-science Collaborative Mathematics and The Future of Science] Javier Tordable, February 26 2010
* [http://www.scientificamerican.com/article.cfm?id=problem-solved-tic-tac-toe-blog Problem Solved, LOL: A Complex Tic-Tac-Toe Puzzle Falls Thanks to Blog Comments] Davide Castelvecchi, Scientific American, March 17 2010
* [http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-toe-and-the-future-of-math/ Blogging, Tic Tac Toe, and the Future of Math] Steve Landsburg, The Big Questions, April 4 2010
* [http://www.siam.org/news/news.php?issue=0043.03 Massively Collaborative Mathematics] Julie Rehmeyer, SIAM News, Volume 43(3), April 2010 (to appear)
* [http://www.princeton.edu/~mbarany/publications.html#WikiSymPolymath `But this is blog maths and we're free to make up conventions as we go along': Polymath1 and the Modalities of `Massively Collaborative Mathematics.'] Michael Barany, Proceedings of the 6th International Symposium on Wikis and Open Collaboration, Gdansk, Poland, 2010.
* [http://www.cs.cmu.edu/~jcransh/papers/cranshaw_kittur.pdf J. Cranshaw and A. Kittur. The Polymath Project: Lessons from a successful online collaboration in mathematics]. In Proceedings of the Conference on Human Factors in Computing Systems, Vancouver, BC, Canada, May 2011.
* [http://www.newscientist.com/article/mg21028113.900-how-to-build-the-global-mathematics-brain.html How to build the global mathematics brain], Jacob Aron, New Scientist, 4 May 2011.
* [http://www.newscientist.com/article/mg21028112.900-mathematics-becomes-more-sociable.html Mathematics becomes more sociable], New Scientist, 5 May 2011.
* [http://polymathprojects.files.wordpress.com/2011/03/polymathias.jpg Mathematical Advances: Lone or Massively Collaborative Endeavors?] from IAS Institute Letter for fall 2010 based on a discussion organized by IAS fall 2010.
Additional links are very welcome.

== Other links ==

* [http://polymathprojects.org/ The polymath blog]
* [http://polymathprojects.org/general-polymath-rules/ General polymath rules]

== Note on anonymous editing ==

To help combat spam, anonymous editing has been disabled, and a captcha system added to hinder automated account creation. If this is causing problems, please email mn@michaelnielsen.org.

== Note on image uploads ==

Image uploads have been disabled, as they were causing problems with spam. If you'd like to upload an image, please email mn@michaelnielsen.org

Talk:Main Page

2012-12-11T02:35:52Z

WikiSysop:

== Polymath Logo ==

It would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

== Links ==

?!? wikisysop whats the problem with the [[Jun Fukuyama's P≠NP Paper]] link?
"Additional links are very welcome." ... yeah right. --[[user:vzn|vzn]] 12/9/2012

:The section is entitled "Discussions about Polymath", and the statement "Additional links are very welcome" refers to additional links about the Polymath Project, not arbitrary links. The page on Fukuyama's paper is not a discussion about the Polymath Project. More generally, at present I don't see how Fukuyama's paper is related to the Polymath Project. [[User:WikiSysop|WikiSysop]] 00:38, 11 December 2012 (UTC)

::it was put iin the section "polymath like projects" already containing a link to evaluations of the Deolalikar proof, a now apparently defunct project after 2.5 yrs. isnt this proof claim similar? [[user:vzn|vzn]] 12/10/2012

:::It's not relevant to that section, either, unless there's a Polymath-like proof evaluation going on, like that which went on at Lipton's blog for Deolalikar's attempt. I'm not aware of any such large-scale effort. [[User:WikiSysop|WikiSysop]] 02:26, 11 December 2012 (UTC)

::::oh! apparently mistakenly thought that the pt of polymath was to ''promote'' and "facilitate'' such efforts even at the seed stage! ok fine, how many comments on a blog, and/or by whom would pass the ''required threshold''? or do you "know it when you see it"? [[user:vzn|vzn]] 12/10/2012

:::::Do you agree that it's not currently relevant to the wiki? It could perhaps become relevant in the future, but at the moment I don't see how anyone could reasonably argue that it's relevant. [[User:WikiSysop|WikiSysop]] 02:35, 11 December 2012 (UTC)

could someone fix the editing help link on the bottom of the wiki edit page? it leads to empty page. not very user friendly eh? in particular is there a tag that substitutes in the current time for discussion edits? [[user:vzn|vzn]] 12/10/2012

Talk:Main Page

2012-12-11T02:28:19Z

WikiSysop:

Talk:Main Page

2012-12-11T02:27:48Z

WikiSysop:

2012-02-21T21:09:03Z

WikiSysop: uploaded a new version of "Image:Elsevier poster.jpg": Credit to Michael Eisen (http://www.michaeleisen.org/blog/?p=975)

Journal publishing reform

2012-02-21T21:04:48Z

WikiSysop:

File:Elsevier poster.jpg

2012-02-21T21:03:33Z

WikiSysop: uploaded a new version of "Image:Elsevier poster.jpg"

2012-01-23T19:19:31Z

WikiSysop:

== Pledges, boycotts, and petitions ==

* [http://www.researchwithoutwalls.org/ Research Without Walls]
* http://www.openaccesspledge.com/
* http://www-fourier.ujf-grenoble.fr/petitions/index.php?petition=3
* http://thecostofknowledge.com/
* http://math.berkeley.edu/~kirby/journals.html

== Blog posts ==

* [http://blog.mathunion.org/journals/?no_cache=1&tx_t3blog_pi1%5BblogList%5D%5BshowUid%5D=17&tx_t3blog_pi1%5BblogList%5D%5Byear%5D=2011&tx_t3blog_pi1%5BblogList%5D%5Bmonth%5D=12&tx_t3blog_pi1%5BblogList%5D%5Bday%5D=07&cHash=bb9177d8192db5b5756aca088ea79677 What might be done about high prices of journals?], IMU blog on mathematical journals, July 12 2011.
* [http://gowers.wordpress.com/2012/01/21/elsevier-my-part-in-its-downfall/ Elsevier - my part in its downfall], Timothy Gowers, January 21, 2012.
* [http://gowers.wordpress.com/2012/01/23/httpthecostofknowledge-com/ The cost of knowledge], Timothy Gowers, January 23 2012.

== Media ==

* http://classic.the-scientist.com/blog/display/55679/
* http://www.guardian.co.uk/business/2008/may/30/armstrade.weaponstechnology
* [http://www.reddit.com/r/math/comments/oqirf/one_mathematicians_stance_against_elsevier/ One mathematicians stance against Elsevier], Reddit, January 22 2012.

== Elsevier mathematics journals ==

This list is taken from [http://www.elsevier.com/wps/find/P11.cws_home/mathjournals here]

* Acta Mathematica Scientia
* Advances in Applied Mathematics
* Advances in Engineering Software
* Advances in Mathematics
* Annales de l'Institut Henri Poincaré (C) Analyse Non Linéaire
* Annals of Pure & Applied Logic
* Annual Reviews in Control
* Applied & Computional Harmonic Analysis
* Applied Mathematical Modelling
* Applied Mathematics & Computation
* Applied Mathematics Letters
* Applied Numerical Mathematics
* Artificial Intelligence
* Automatica
* Biometric Technology Today
* Biosystems
* Bulletin des Sciences Mathématiques
* Chaos, Solitons & Fractals
* Communications in Nonlinear Science and Numerical Simulation
* Comptes Rendus Mathematique
* Computational Geometry
* Computational Statistics & Data Analysis
* Computer Methods in Applied Mechanics and Engineering
* Computers & Mathematics with Applications
* Control Engineering Practice
* Differential Geometry and its Applications
* Discrete Applied Mathematics
* Discrete Mathematics
* Discrete Optimization
* Electronic Notes in Discrete Mathematics
* Electronic Notes in Theoretical Computer Science
* Engineering Analysis with Boundary Elements
* Engineering Applications of Artificial Intelligence
* European Journal of Combinatorics
* European Journal of Operational Research
* Expositiones Mathematicae
* Finite Fields and their Applications
* Fuzzy Sets and Systems
* Historia Mathematica
* Indagationes Mathematicae
* Information Sciences
* International Journal of Forecasting
* International Journal of Non-Linear Mechanics
* Journal de Mathématiques Pures et Appliquées
* Journal of Algebra
* Journal of Algorithms
* Journal of Applied Logic
* Journal of Approximation Theory
* Journal of Combinatorial Theory, series A
* Journal of Combinatorial Theory, series B
* Journal of Complexity
* Journal of Computational & Applied Mathematics
* Journal of Computer and System Sciences
* Journal of Differential Equations
* Journal of Discrete Algorithms
* Journal of Econometrics
* Journal of Functional Analysis
* Journal of Geometry and Physics
* Journal of Mathematical Analysis & Applications
* Journal of Mathematical Economics
* Journal of Multivariate Analysis
* Journal of Number Theory
* Journal of Process Control
* Journal of Pure & Applied Algebra
* Journal of Statistical Planning & Inference
* Journal of the Franklin Institute
* Journal of the Korean Statistical Society
* Linear Algebra and its Applications
* Mathematical and Computer Modelling
* Mathematical Biosciences
* Mathematical Social Science
* Mathematics and Computers in Simulation
* Neural Networks
* Nonlinear Analysis
* Nonlinear Analysis: Hybrid Systems
* Nonlinear Analysis: Real world applications
* Operations Research Letters
* Pattern Recognition
* Physica A: Statistical Mechanics and its Applications
* Physica D: Nonlinear Phenomena
* Simulation Modelling Practice & Theory
* Statistical Methodology
* Statistics and Probability Letters
* Stochastic Processes and their Applications
* Systems & Control Letters
* Topology
* Topology & its Applications

Main Page

2011-12-08T14:16:34Z

WikiSysop: Reverted edits by Evaste (Talk) to last version by Gilkalai

{{RightTOC}}
This is the wiki for ''polymath'' projects - massively collaborative online mathematical projects. The idea of such projects originated in Tim Gowers' blog post [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?]

Many polymath projects will be proposed, planned, and run at [http://polymathprojects.org/ this blog].

A Polymath [[logo]] is being trialled. If you have more suggestions, please add them to the [[logo]] page, or add to the discussion at [[Talk:logo]].

== Existing polymath projects ==

* [[Polymath1]]: New proofs and bounds for the density Hales-Jewett theorem. Initiated Feb 1, 2009; research results have now been submitted for publication.
* [[Definable Banach Spaces|Polymath2]]: Must an “explicitly defined” Banach space contain <math>c_0</math> or <math>l_p</math>? Initiated Feb 17, 2009; attempts to relaunch via wiki, June 9 2010.
* [[imo 2009 q6|Mini-polymath1]]: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
* [[The polynomial Hirsch conjecture|Polymath3]]. The polynomial Hirsch conjecture. Proposed July 17, 2009; launched, September 30, 2010.
* [[finding primes|Polymath4]]: A deterministic way to find primes. Proposed July 27, 2009; launched Aug 9, 2009. Research results have been submitted for publication.
* [[The Erdős discrepancy problem|Polymath5]]. The Erdős discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010.
* [[imo 2010|Mini-polymath2]]: Solving Problem 5 the 2010 International Mathematical Olympiad. Proposed Jun 12, 2010; launched Jul 8, 2010; solved, Jul 8 2010.
* [[Improving the bounds for Roth's theorem|Polymath6]]. Improving the bounds for Roth's theorem. Proposed Feb 5, 2011.
* [[imo 2011|Mini-polymath3]]: Solving a problem from the 2011 International Mathematical Olympiad. Proposed Jun 9, 2010.

== Polymath-like projects ==

* Scott Aaronson's "philomath project": "[http://scottaaronson.com/blog/?p=453 Sensitivity vs. Block sensitivity]" (see also [http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice this Math Overflow question]). Launched Jul 13, 2010.
* A [[wiki]] page clearinghouse for [[Deolalikar P vs NP paper]]. Launched Aug 10, 2010.

== Proposed polymath projects ==

* [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ The cap set problem]. Proposed March 25, 2009 (see also these [http://gilkalai.wordpress.com/2009/05/11/around-the-cap-set-problem-b/ two] [http://gilkalai.wordpress.com/2009/05/18/the-cap-set-problem-and-frankl-rodl-theorem-c/ followup] posts).
* [[Boshernitzan’s problem]]. Proposed July 27, 2009.
* [http://gowers.wordpress.com/2009/09/16/possible-future-polymath-projects/ Possible future polymath projects]. Discussion opened September 16, 2009.
* [http://rjlipton.wordpress.com/2011/05/12/a-possible-polymath-project/ A possible polymath project:] Proposal by Richard Lipton to attack a conjecture due to Erdos, about a class of Diophantine equations.

A (partial) list of proposed projects can be found [http://en.wordpress.com/tag/polymath-proposals/ here].

If you have a tentative proposal for a polymath project, you can either make a post on it on your own blog, or place it [[other proposed projects|here]].

== Discussions about polymath ==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] Tim Gowers, January 27, 2009.
* [http://lucatrevisan.wordpress.com/2009/02/01/a-peoples-history-of-mathematics/ A people's history of mathematics] Luca Trevisan, February 1, 2009.
* [http://michaelnielsen.org/blog/?p=553 The polymath project] Michael Nielsen, February 3, 2009.
* [http://www.neverendingbooks.org/index.php/yet-another-math20-proposal.html Yet another math 2.0 proposal] Lieven le Bruyn, February 11, 2009.
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] Tim Gowers, March 10, 2009.
* [http://maxwelldemon.com/2009/03/14/polymath/ Polymath] Edmund Harriss, March 14, 2009.
* [http://science.slashdot.org/article.pl?sid=09/03/18/194228 Massive open collaboration in mathematics declared a success] Slashdot, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=581 How changing the technology of collaboration can change the nature of collaboration] Michael Nielsen, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=584 The polymath project: scope of participation] Michael Nielsen, March 20, 2009.
* [http://gowers.wordpress.com/2009/03/24/can-polymath-be-scaled-up/ Can polymath be scaled up?] Tim Gowers, March 24, 2009.
* [http://whatisresearch.wordpress.com/2009/03/24/concluding-notes-on-the-polymath-project-and-a-challenge/ Concluding notes on the polymath project - and a challenge] Vilpulniak, March 24, 2009.
* [http://michaelnielsen.org/blog/on-scaling-up-the-polymath-project/ On scaling up the polymath project] Michael Nielsen, March 25, 2009.
* [http://numberwarrior.wordpress.com/2009/03/25/a-gentle-introduction-to-the-polymath-project/ A gentle introduction to the polymath project] Jason Dyer, March 25, 2009.
* [http://blogs.telegraph.co.uk/technology/iandouglas/9656357/tim_gowers_and_the_polymaths/ Tim Gowers and the polymaths] Ian Douglas (the Telegraph), April 29, 2009
* [http://terrytao.wordpress.com/2009/07/22/imo-2009-q6-mini-polymath-project-impressions-reflections-analysis/ IMO 2009 Q6 as mini-polymath project: impressions, reflections, analysis] Terence Tao, July 22, 2009.
* [http://polymathprojects.org/2009/07/27/selecting-the-next-polymath-project/ Selecting the next polymath project] Terence Tao, July 27, 2009.
* [http://blog.jonudell.net/2009/07/31/polymath-equals-user-innovatio/ Polymath equals user innovation] Jon Udell, July 31, 2009.
* [http://scienceblogs.com/christinaslisrant/2009/08/an_overview_of_the_polymath_pr.php An overview of the polymath project] Christina Pikas, August 1, 2009
* [http://whatisresearch.wordpress.com/2009/08/09/collaborative-mathematics-etc/ Collaborative mathematics etc.] Vipulniak, August 9, 2009
* [http://www.nature.com/nature/journal/v461/n7266/full/461879a.html Massively collaborative mathematics] Tim Gowers, Michael Nielsen, Nature, October 15, 2009
* [http://portonmath.wordpress.com/2009/10/25/collaborative-research-of-filters/ Collaborative math research – a real example] Victor Porton, October 24, 2009
* [http://whatisresearch.wordpress.com/2009/10/26/polymath-again/ Polymath again] Vipulniak, October 26, 2009
* [http://www.kennislink.nl/publicaties/wiskunde-met-zijn-allen Wiskunde met zijn allen] (Dutch), Alex van den Brandhof, Kennislink, November 12, 2009
* [http://www.sciencenews.org/view/generic/id/50532/title/Mathematics_by_collaboration Mathematics by collaboration], Julie Rehmeyer, ScienceNews, December 8, 2009
* [http://www.nytimes.com/projects/magazine/ideas/2009/#m Massively Collaborative Mathematics], Jordan Ellenberg, The Ninth Annual Year in Ideas, New York Times, 2009.
* [http://www.hypios.com/thinking/2010/01/13/massively-collaborative-mathematics-lessons-from-polymath1/ Massively Collaborative Mathematics: lessons from polymath1], Hypios, Jan 13 2010
* [http://ths1104.wordpress.com/2010/02/13/open-reflexions-sur-fond-de-polymaths/ Open réflexions sur fond de Polymaths] (French), ths1104, Feb 13 2010
* [http://www.javiertordable.com/blog/2010/02/25/collaborative-mathematics-future-of-science Collaborative Mathematics and The Future of Science] Javier Tordable, February 26 2010
* [http://www.scientificamerican.com/article.cfm?id=problem-solved-tic-tac-toe-blog Problem Solved, LOL: A Complex Tic-Tac-Toe Puzzle Falls Thanks to Blog Comments] Davide Castelvecchi, Scientific American, March 17 2010
* [http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-toe-and-the-future-of-math/ Blogging, Tic Tac Toe, and the Future of Math] Steve Landsburg, The Big Questions, April 4 2010
* [http://www.siam.org/news/news.php?issue=0043.03 Massively Collaborative Mathematics] Julie Rehmeyer, SIAM News, Volume 43(3), April 2010 (to appear)
* [http://www.princeton.edu/~mbarany/cv.html#WikiSymPolymath `But this is blog maths and we're free to make up conventions as we go along': Polymath1 and the Modalities of `Massively Collaborative Mathematics.'] Michael Barany, Proceedings of the 6th International Symposium on Wikis and Open Collaboration, Gdansk, Poland, 2010.
* [http://www.cs.cmu.edu/~jcransh/papers/cranshaw_kittur.pdf J. Cranshaw and A. Kittur. The Polymath Project: Lessons from a successful online collaboration in mathematics]. In Proceedings of the Conference on Human Factors in Computing Systems, Vancouver, BC, Canada, May 2011.
* [http://www.newscientist.com/article/mg21028113.900-how-to-build-the-global-mathematics-brain.html How to build the global mathematics brain], Jacob Aron, New Scientist, 4 May 2011.
* [http://www.newscientist.com/article/mg21028112.900-mathematics-becomes-more-sociable.html Mathematics becomes more sociable], New Scientist, 5 May 2011.
* [http://polymathprojects.files.wordpress.com/2011/03/polymathias.jpg Mathematical Advances: Lone or Massively Collaborative Endeavors?] from IAS Institute Letter for fall 2010 based on a discussion organized by IAS fall 2010.
Additional links are very welcome.

== Other links ==

* [http://polymathprojects.org/ The polymath blog]
* [http://polymathprojects.org/general-polymath-rules/ General polymath rules]

== Note on anonymous editing ==

To help combat spam, anonymous editing has been disabled, and a captcha system added to hinder automated account creation. If this is causing problems, please email mn@michaelnielsen.org.