Many problems and results in analytic prime number theory can be formulated in the following general form: given a collection of (affine-)linear forms {L_1(n),\dots,L_k(n)}, none of which is a multiple of any other, find a number {n} such that a certain property {P( L_1(n),\dots,L_k(n) )} of the linear forms {L_1(n),\dots,L_k(n)} are true. For instance:

  • For the twin prime conjecture, one can use the linear forms {L_1(n) := n}, {L_2(n) := n+2}, and the property {P( L_1(n), L_2(n) )} in question is the assertion that {L_1(n)} and {L_2(n)} are both prime.
  • For the even Goldbach conjecture, the claim is similar but one uses the linear forms {L_1(n) := n}, {L_2(n) := N-n} for some even integer {N}.
  • For Chen’s theorem, we use the same linear forms {L_1(n),L_2(n)} as in the previous two cases, but now {P(L_1(n), L_2(n))} is the assertion that {L_1(n)} is prime and {L_2(n)} is an almost prime (in the sense that there are at most two prime factors).
  • In the recent results establishing bounded gaps between primes, we use the linear forms {L_i(n) = n + h_i} for some admissible tuple {h_1,\dots,h_k}, and take {P(L_1(n),\dots,L_k(n))} to be the assertion that at least two of {L_1(n),\dots,L_k(n)} are prime.

For these sorts of results, one can try a sieve-theoretic approach, which can broadly be formulated as follows:

  1. First, one chooses a carefully selected sieve weight {\nu: {\bf N} \rightarrow {\bf R}^+}, which could for instance be a non-negative function having a divisor sum form

    \displaystyle \nu(n) := \sum_{d_1|L_1(n), \dots, d_k|L_k(n); d_1 \dots d_k \leq x^{1-\varepsilon}} \lambda_{d_1,\dots,d_k}

    for some coefficients {\lambda_{d_1,\dots,d_k}}, where {x} is a natural scale parameter. The precise choice of sieve weight is often quite a delicate matter, but will not be discussed here. (In some cases, one may work with multiple sieve weights {\nu_1, \nu_2, \dots}.)

  2. Next, one uses tools from analytic number theory (such as the Bombieri-Vinogradov theorem) to obtain upper and lower bounds for sums such as

    \displaystyle \sum_n \nu(n) \ \ \ \ \ (1)

    or

    \displaystyle \sum_n \nu(n) 1_{L_i(n) \hbox{ prime}} \ \ \ \ \ (2)

    or more generally of the form

    \displaystyle \sum_n \nu(n) f(L_i(n)) \ \ \ \ \ (3)

    where {f(L_i(n))} is some “arithmetic” function involving the prime factorisation of {L_i(n)} (we will be a bit vague about what this means precisely, but a typical choice of {f} might be a Dirichlet convolution {\alpha*\beta(L_i(n))} of two other arithmetic functions {\alpha,\beta}).

  3. Using some combinatorial arguments, one manipulates these upper and lower bounds, together with the non-negative nature of {\nu}, to conclude the existence of an {n} in the support of {\nu} (or of at least one of the sieve weights {\nu_1, \nu_2, \dots} being considered) for which {P( L_1(n), \dots, L_k(n) )} holds

For instance, in the recent results on bounded gaps between primes, one selects a sieve weight {\nu} for which one has upper bounds on

\displaystyle \sum_n \nu(n)

and lower bounds on

\displaystyle \sum_n \nu(n) 1_{n+h_i \hbox{ prime}}

so that one can show that the expression

\displaystyle \sum_n \nu(n) (\sum_{i=1}^k 1_{n+h_i \hbox{ prime}} - 1)

is strictly positive, which implies the existence of an {n} in the support of {\nu} such that at least two of {n+h_1,\dots,n+h_k} are prime. As another example, to prove Chen’s theorem to find {n} such that {L_1(n)} is prime and {L_2(n)} is almost prime, one uses a variety of sieve weights to produce a lower bound for

\displaystyle S_1 := \sum_{n \leq x} 1_{L_1(n) \hbox{ prime}} 1_{L_2(n) \hbox{ rough}}

and an upper bound for

\displaystyle S_2 := \sum_{z \leq p < x^{1/3}} \sum_{n \leq x} 1_{L_1(n) \hbox{ prime}} 1_{p|L_2(n)} 1_{L_2(n) \hbox{ rough}}

and

\displaystyle S_3 := \sum_{n \leq x} 1_{L_1(n) \hbox{ prime}} 1_{L_2(n)=pqr \hbox{ for some } z \leq p \leq x^{1/3} < q \leq r},

where {z} is some parameter between {1} and {x^{1/3}}, and “rough” means that all prime factors are at least {z}. One can observe that if {S_1 - \frac{1}{2} S_2 - \frac{1}{2} S_3 > 0}, then there must be at least one {n} for which {L_1(n)} is prime and {L_2(n)} is almost prime, since for any rough number {m}, the quantity

\displaystyle 1 - \frac{1}{2} \sum_{z \leq p < x^{1/3}} 1_{p|m} - \frac{1}{2} \sum_{z \leq p \leq x^{1/3} < q \leq r} 1_{m = pqr}

is only positive when {m} is an almost prime (if {m} has three or more factors, then either it has at least two factors less than {x^{1/3}}, or it is of the form {pqr} for some {p \leq x^{1/3} < q \leq r}). The upper and lower bounds on {S_1,S_2,S_3} are ultimately produced via asymptotics for expressions of the form (1), (2), (3) for various divisor sums {\nu} and various arithmetic functions {f}.

Unfortunately, there is an obstruction to sieve-theoretic techniques working for certain types of properties {P(L_1(n),\dots,L_k(n))}, which Zeb Brady and I recently formalised at an AIM workshop this week. To state the result, we recall the Liouville function {\lambda(n)}, defined by setting {\lambda(n) = (-1)^j} whenever {n} is the product of exactly {j} primes (counting multiplicity). Define a sign pattern to be an element {(\epsilon_1,\dots,\epsilon_k)} of the discrete cube {\{-1,+1\}^k}. Given a property {P(l_1,\dots,l_k)} of {k} natural numbers {l_1,\dots,l_k}, we say that a sign pattern {(\epsilon_1,\dots,\epsilon_k)} is forbidden by {P} if there does not exist any natural numbers {l_1,\dots,l_k} obeying {P(l_1,\dots,l_k)} for which

\displaystyle (\lambda(l_1),\dots,\lambda(l_k)) = (\epsilon_1,\dots,\epsilon_k).

Example 1 Let {P(l_1,l_2,l_3)} be the property that at least two of {l_1,l_2,l_3} are prime. Then the sign patterns {(+1,+1,+1)}, {(+1,+1,-1)}, {(+1,-1,+1)}, {(-1,+1,+1)} are forbidden, because prime numbers have a Liouville function of {-1}, so that {P(l_1,l_2,l_3)} can only occur when at least two of {\lambda(l_1),\lambda(l_2), \lambda(l_3)} are equal to {-1}.

Example 2 Let {P(l_1,l_2)} be the property that {l_1} is prime and {l_2} is almost prime. Then the only forbidden sign patterns are {(+1,+1)} and {(+1,-1)}.

Example 3 Let {P(l_1,l_2)} be the property that {l_1} and {l_2} are both prime. Then {(+1,+1), (+1,-1), (-1,+1)} are all forbidden sign patterns.

We then have a parity obstruction as soon as {P} has “too many” forbidden sign patterns, in the following (slightly informal) sense:

Claim 1 (Parity obstruction) Suppose {P(l_1,\dots,l_k)} is such that that the convex hull of the forbidden sign patterns of {P} contains the origin. Then one cannot use the above sieve-theoretic approach to establish the existence of an {n} such that {P(L_1(n),\dots,L_k(n))} holds.

Thus for instance, the property in Example 3 is subject to the parity obstruction since {0} is a convex combination of {(+1,-1)} and {(-1,+1)}, whereas the properties in Examples 1, 2 are not. One can also check that the property “at least {j} of the {k} numbers {l_1,\dots,l_k} is prime” is subject to the parity obstruction as soon as {j \geq \frac{k}{2}+1}. Thus, the largest number of elements of a {k}-tuple that one can force to be prime by purely sieve-theoretic methods is {k/2}, rounded up.

This claim is not precisely a theorem, because it presumes a certain “Liouville pseudorandomness conjecture” (a very close cousin of the more well known “Möbius pseudorandomness conjecture”) which is a bit difficult to formalise precisely. However, this conjecture is widely believed by analytic number theorists, see e.g. this blog post for a discussion. (Note though that there are scenarios, most notably the “Siegel zero” scenario, in which there is a severe breakdown of this pseudorandomness conjecture, and the parity obstruction then disappears. A typical instance of this is Heath-Brown’s proof of the twin prime conjecture (which would ordinarily be subject to the parity obstruction) under the hypothesis of a Siegel zero.) The obstruction also does not prevent the establishment of an {n} such that {P(L_1(n),\dots,L_k(n))} holds by introducing additional sieve axioms beyond upper and lower bounds on quantities such as (1), (2), (3). The proof of the Friedlander-Iwaniec theorem is a good example of this latter scenario.

Now we give a (slightly nonrigorous) proof of the claim.

Proof: (Nonrigorous) Suppose that the convex hull of the forbidden sign patterns contain the origin. Then we can find non-negative numbers {p_{\epsilon_1,\dots,\epsilon_k}} for sign patterns {(\epsilon_1,\dots,\epsilon_k)}, which sum to {1}, are non-zero only for forbidden sign patterns, and which have mean zero in the sense that

\displaystyle \sum_{(\epsilon_1,\dots,\epsilon_k)} p_{\epsilon_1,\dots,\epsilon_k} \epsilon_i = 0

for all {i=1,\dots,k}. By Fourier expansion (or Lagrange interpolation), one can then write {p_{\epsilon_1,\dots,\epsilon_k}} as a polynomial

\displaystyle p_{\epsilon_1,\dots,\epsilon_k} = 1 + Q( \epsilon_1,\dots,\epsilon_k)

where {Q(t_1,\dots,t_k)} is a polynomial in {k} variables that is a linear combination of monomials {t_{i_1} \dots t_{i_r}} with {i_1 < \dots < i_r} and {r \geq 2} (thus {Q} has no constant or linear terms, and no monomials with repeated terms). The point is that the mean zero condition allows one to eliminate the linear terms. If we now consider the weight function

\displaystyle w(n) := 1 + Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) )

then {w} is non-negative, is supported solely on {n} for which {(\lambda(L_1(n)),\dots,\lambda(L_k(n)))} is a forbidden pattern, and is equal to {1} plus a linear combination of monomials {\lambda(L_{i_1}(n)) \dots \lambda(L_{i_r}(n))} with {r \geq 2}.

The Liouville pseudorandomness principle then predicts that sums of the form

\displaystyle \sum_n \nu(n) Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) )

and

\displaystyle \sum_n \nu(n) Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) ) 1_{L_i(n) \hbox{ prime}}

or more generally

\displaystyle \sum_n \nu(n) Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) ) f(L_i(n))

should be asymptotically negligible; intuitively, the point here is that the prime factorisation of {L_i(n)} should not influence the Liouville function of {L_j(n)}, even on the short arithmetic progressions that the divisor sum {\nu} is built out of, and so any monomial {\lambda(L_{i_1}(n)) \dots \lambda(L_{i_r}(n))} occurring in {Q( \lambda(L_1(n)), \dots, \lambda(L_k(n)) )} should exhibit strong cancellation for any of the above sums. If one accepts this principle, then all the expressions (1), (2), (3) should be essentially unchanged when {\nu(n)} is replaced by {\nu(n) w(n)}.

Suppose now for sake of contradiction that one could use sieve-theoretic methods to locate an {n} in the support of some sieve weight {\nu(n)} obeying {P( L_1(n),\dots,L_k(n))}. Then, by reweighting all sieve weights by the additional multiplicative factor of {w(n)}, the same arguments should also be able to locate {n} in the support of {\nu(n) w(n)} for which {P( L_1(n),\dots,L_k(n))} holds. But {w} is only supported on those {n} whose Liouville sign pattern is forbidden, a contradiction. \Box

Claim 1 is sharp in the following sense: if the convex hull of the forbidden sign patterns of {P} do not contain the origin, then by the Hahn-Banach theorem (in the hyperplane separation form), there exist real coefficients {c_1,\dots,c_k} such that

\displaystyle c_1 \epsilon_1 + \dots + c_k \epsilon_k < -c

for all forbidden sign patterns {(\epsilon_1,\dots,\epsilon_k)} and some {c>0}. On the other hand, from Liouville pseudorandomness one expects that

\displaystyle \sum_n \nu(n) (c_1 \lambda(L_1(n)) + \dots + c_k \lambda(L_k(n)))

is negligible (as compared against {\sum_n \nu(n)} for any reasonable sieve weight {\nu}. We conclude that for some {n} in the support of {\nu}, that

\displaystyle c_1 \lambda(L_1(n)) + \dots + c_k \lambda(L_k(n)) > -c \ \ \ \ \ (4)

and hence {(\lambda(L_1(n)),\dots,\lambda(L_k(n)))} is not a forbidden sign pattern. This does not actually imply that {P(L_1(n),\dots,L_k(n))} holds, but it does not prevent {P(L_1(n),\dots,L_k(n))} from holding purely from parity considerations. Thus, we do not expect a parity obstruction of the type in Claim 1 to hold when the convex hull of forbidden sign patterns does not contain the origin.

Example 4 Let {G} be a graph on {k} vertices {\{1,\dots,k\}}, and let {P(l_1,\dots,l_k)} be the property that one can find an edge {\{i,j\}} of {G} with {l_i,l_j} both prime. We claim that this property is subject to the parity problem precisely when {G} is two-colourable. Indeed, if {G} is two-colourable, then we can colour {\{1,\dots,k\}} into two colours (say, red and green) such that all edges in {G} connect a red vertex to a green vertex. If we then consider the two sign patterns in which all the red vertices have one sign and the green vertices have the opposite sign, these are two forbidden sign patterns which contain the origin in the convex hull, and so the parity problem applies. Conversely, suppose that {G} is not two-colourable, then it contains an odd cycle. Any forbidden sign pattern then must contain more {+1}s on this odd cycle than {-1}s (since otherwise two of the {-1}s are adjacent on this cycle by the pigeonhole principle, and this is not forbidden), and so by convexity any tuple in the convex hull of this sign pattern has a positive sum on this odd cycle. Hence the origin is not in the convex hull, and the parity obstruction does not apply. (See also this previous post for a similar obstruction ultimately coming from two-colourability).

Example 5 An example of a parity-obstructed property (supplied by Zeb Brady) that does not come from two-colourability: we let {P( l_{\{1,2\}}, l_{\{1,3\}}, l_{\{1,4\}}, l_{\{2,3\}}, l_{\{2,4\}}, l_{\{3,4\}} )} be the property that {l_{A_1},\dots,l_{A_r}} are prime for some collection {A_1,\dots,A_r} of pair sets that cover {\{1,\dots,4\}}. For instance, this property holds if {l_{\{1,2\}}, l_{\{3,4\}}} are both prime, or if {l_{\{1,2\}}, l_{\{1,3\}}, l_{\{1,4\}}} are all prime, but not if {l_{\{1,2\}}, l_{\{1,3\}}, l_{\{2,3\}}} are the only primes. An example of a forbidden sign pattern is the pattern where {\{1,2\}, \{2,3\}, \{1,3\}} are given the sign {-1}, and the other three pairs are given {+1}. Averaging over permutations of {1,2,3,4} we see that zero lies in the convex hull, and so this example is blocked by parity. However, there is no sign pattern such that it and its negation are both forbidden, which is another formulation of two-colourability.

Of course, the absence of a parity obstruction does not automatically mean that the desired claim is true. For instance, given an admissible {5}-tuple {h_1,\dots,h_5}, parity obstructions do not prevent one from establishing the existence of infinitely many {n} such that at least three of {n+h_1,\dots,n+h_5} are prime, however we are not yet able to actually establish this, even assuming strong sieve-theoretic hypotheses such as the generalised Elliott-Halberstam hypothesis. (However, the argument giving (4) does easily give the far weaker claim that there exist infinitely many {n} such that at least three of {n+h_1,\dots,n+h_5} have a Liouville function of {-1}.)

Remark 1 Another way to get past the parity problem in some cases is to take advantage of linear forms that are constant multiples of each other (which correlates the Liouville functions to each other). For instance, on GEH we can find two {E_3} numbers (products of exactly three primes) that differ by exactly {60}; a direct sieve approach using the linear forms {n,n+60} fails due to the parity obstruction, but instead one can first find {n} such that two of {n,n+4,n+10} are prime, and then among the pairs of linear forms {(15n,15n+60)}, {(6n,6n+60)}, {(10n+40,10n+100)} one can find a pair of {E_3} numbers that differ by exactly {60}. See this paper of Goldston, Graham, Pintz, and Yildirim for more examples of this type.

I thank John Friedlander and Sid Graham for helpful discussions and encouragement.