You are currently browsing the monthly archive for juin 2019.

It is an open and interesting problem to determine whether there exist two infinite sets B,C of integers such that B+C\subset\mathcal{P}, where \mathcal{P} is the set of primes. Let’s call this the prime sumset conjecture.

Observe that a set A contains an infinite sumset if, and only if, there exists an infinite set B such that \bigcap_{b\in B}(A-b) is infinite.

We will examine the connections between the Hardy-Littlewood prime-tuple conjecture (HL), the theorems on bounded gaps between primes and the prime-sumset conjecture.

HL and an easy reformulation

HL may easily be seen to be equivalent to the following statement: for any finite set H\subset\mathbb{Z} that does not cover all the classes modulo any prime, i.e. such that H\text{ mod } p\neq \mathbb{Z}/p\mathbb{Z} for every p, there exists an infinite set A\subset \mathbb{N} such that A+H\subset \mathcal{P}. The condition on H is obviously necessary for the conclusion to hold. However HL does not directly imply anything for infinite set of shifts H.

Conversely, if the primes contain a sumset A+B with A,B infinite, then for any finite H\subset B, HL is satisfied for the set H of shifts — but not necessarily for every admissible set.

A stronger form of the HL conjecture, sometimes attributed to Dickson, is the following: let k and (a_1,\ldots,a_k,b_1,\ldots,b_k) be an integer tuple such that (a_j,b_j)=1 for each j and for any prime p, there exists x such that \prod_j(a_jx+b_j)\neq 0\text{ mod } p. Then there exists arbitrarily large x such that a_jx+b_j is prime for every j\leq k.

HL implies prime-sumset

Granville proved that the Hardy-Littlewood conjecture implies the prime-sumset conjecture. Since his proof is more general and complicated, we explain here simply why this is so.

We construct successively integers a_n\in 2\mathbb{Z} and b_n\in 2\mathbb{Z}+1 such that the sets A_n=\{a_k : k\leq n\} and B_n=\{a_k : k\leq n\} satisfy A_n+B_n\subset \mathcal{P}.

Start with a_1=2 and b_1=1 for instance. We can then add a_2=4 and b_2=3. We note that a_3=10 and b_3=37 works.In general, the property we seek to maintain is that A_n \text{ mod } p does not cover the wholeset \mathbb{Z}/p\mathbb{Z} of congruence classes for any p (forp\leq n, otherwise there is no risk) and neither does B_n\text{ mod } p.

One systematic way to achieve this is to always seek a_n>n+1 in the congruence class a_{n-1}\text{ mod } \prod_{p\leq n}p and b_n in the class b_{n-1}\text{ mod } \prod_{p\leq n}, starting from a_1=2 and b_1=1. Assume we have already constructed A_n and B_n with this property.

We seek a_{n+1} in the form qx+a_n for some x\geq 1 and q=\prod_{p\leq n+1}p. Then we must ensure that qx+a_n+b_i is a prime for every i\leq n.

Note that a_n+b_i is a prime greater than n+1 for every i\leq n by the induction hypothesis, whereas q is a product of primes smaller than n+1, so (q,a_n+b_i)=1 for any i. Now for p\leq n the set \{a_n+b_i \text{ mod } p : i\leq n\} equals the set \{a_n+b_{i} : i\leq p-1\} since b_{i}\equiv b_{p-1}\text{ mod } p. Thus we can find x such that qx+a_n+B_n is included in the primes. Let a_{n+1}=qx+a_n. We then define b_{n+1} analogously.

Bounded gaps as an ersatz for HL

Although HL remains clearly out of reach, the breakthroughs of Zhang and then Maynard imply that HL holds for arbitrarily large sets H of shifts. Indeed, Maynard’s theorem implies not only that \liminf p_{n+1}-p_n<\infty where  p_n is the increasing sequence of prime numbers, but also that \liminf p_{n+k}-p_n=L_k<\infty for any k. That is, there exists L_k such that for infinitely many integers n, the interval [n,n+L_k] contains at least k+1 primes. As a result, by the pigeonhole principle, there exists a set H\subset [0,L_k] of cardinality k+1 such that A+H\subset \mathcal{P} for some infinite set A. This argument does not seem to extend to infinite sets H. One would need an infinite increasing sequence H_n of sets such that the set A_n of x such that x+H_n\subset \mathcal{P} is infinite.

But even that would not be enough. Indeed, consider a set such as

\displaystyle{A=\bigcup_k A_k}

where A_k=\{4^k+2^i,\, i\in[k]\}. This clearly has unbounded gaps, and for any n there exists an infinite set A_n such that A_n+\{2^i,\, i\in[n]\} is included in A.

One may see that this set does not contain an infinite sumset though. First note that for any integer b which is not a difference between two distinct powers of two, the set A\cap (A-b) is finite. Further, if b\geq 0 is the difference between two powers of two, it may be realised in a unique way as b=2^i-2^j. Therefore, A\cap (A-b)=\bigcup_{k\geq i} \{4^k+2^j\}. Now take B=\{0<b_1<b_2<\cdots\}. Suppose b_1=2^i-2^j. We may suppose that each b_r is a difference between two powers of two, in fact b_r=2^{i_r}-2^j, otherwise \bigcap_{b\in B}(A-b) is empty. We have A\cap (A-b_1)\cap \cdots\cap (A-b_r)=2^j+\{4^k\,:\,k\geq i_r\}. Therefore \bigcap_{b\in B}(A-b) is empty.

This implies that A does not contain an infinite sumset.

A simple proof that any thick set contains an infinite sumset

It has been proven that any set of positive Banach density contains an infinite sumset. The proof, even in the simplified version of Host, is far from elementary. It may have been noted before, but I found a simple proof in the case of sets of density 1, also called thick sets. Note that such a set A necessarily contains arbitrarily long intervals, sets of the form [d_k,d_k+k] for infinitely many (say all) k. Now we construct inductively b_1<b_2<\ldots and c_1<c_2<\ldots such that B+C is inside A. First, set a_1=d_1 and a_{i+1}=d_{a_i}. Then set b_i=a_{2i} and c_{i}=a_{2i+1}. Then note that [a_i,a_i+a_j] is inside A whenever i>j. As a result, we infer that b_i+c_j is in A for all i,j.