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$ (for$p\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. 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 and $c_1 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$.