## Are There Primes of Every Hamming Weight?

That is, for every integer $n \in \mathbb{Z}_{>0}$ does there exist a prime which is the sum of $n$ distinct powers of $2$?

In this case, the Hamming weight of a number is the number of $1$s in its binary expansion.

Many problems of this sort have been considered, but perhaps not in such language. For instance, the question "Are there infinitely many Fermat primes?" corresponds to asking, "Are there infinitely many distinct primes with Hamming weight exactly $2$?" Also related is the question of whether there are infinitely many Mersenne primes.

These examples suggest a class of such problems, "Do there exist infinitely many primes which are the sum of exactly $n$ distinct powers of two?"

Since this question is open even for the $n=2$ case, I pose a much weaker question here.

What is known is that for every $n \leq 1024$ there is such a prime.

The smallest such prime is listed in the Online Encyclopedia of Integer Sequences A061712.

The number of zeros in the smallest such primes are listed in A110700. The number of zeros in a number with a given Hamming weight is a reasonable measure of how large that number is. The conjecture at OEIS is quite a bit stronger than the question I pose.

Is there a theorem ensuring such primes for every $n \in \mathbb{Z}_{>0}$?

-
Welcome to MO, dakota. – Joel David Hamkins Apr 26 2010 at 18:32
I think you want positive integer n, since the negative integers have no chance, and n=0 also does not occur. – Joel David Hamkins Apr 26 2010 at 18:39
This will surely be an open problem. – Kevin Buzzard Apr 26 2010 at 19:23
(A very weak version assuming a difficult conjecture) It would follow from the existence of arbitrarily long Cunnigham Chains (en.wikipedia.org/wiki/Cunningham_chain) that there are arbitrarily long strings of consecutive integers n,n+1,...,n+k such that they are all the Hamming numbers of primes. Based on the links with this, and difficult conjectures like the Fermat Primes and Schinzel's hypothesis, I agree with Kevin that this looks like an open problem. – Thomas Bloom Apr 26 2010 at 21:04
See the reference mentioned in artofproblemsolving.com/Forum/… This doesn't resolve the question for all $n$, just for sufficiently large $n$, of course, but I do not think that the existence of a few exceptional values (which is highly unlikely) will make a lot of difference for anything. – fedja Apr 26 2010 at 22:49

Fedja is absolutely right: this has been proven, for sufficiently large $n$, by Drmota, Mauduit and Rivat.

Although it looks at first sight as though this question is as hopeless as any other famous open problem on primes, it is easy to explain why this is not the case. Of the numbers between $1$ and $N := 2^{2n}$, the proportion whose digit sum is precisely $n$ is a constant over $\sqrt{\log N}$. These numbers are therefore quite "dense", and there is a technique in prime number theory called the method of bilinear sums (or the method of Type I/II sums) which in principle allow one to seriously think about finding primes in such a set. This is what Drmota, Mauduit and Rivat do.

I do not believe that their method has currently been pushed as far as (for example) showing that there are infinitely many primes with no 0 when written in base 1000000.

Let me also remark that they depend in a really weird way on some specific properties of these digit representation functions, in particular concerning the sum of the absolute values of their Fourier coefficients, which is surprisingly small. That is, it is not the case that they treat these Hamming sets as though they were "typical" sets of density $1/\sqrt{\log N}$.

I think one might also mention a celebrated paper of Friedlander and Iwaniec, http://arxiv.org/abs/math/9811185. In this work they prove that there are infinitely many primes of the form $x^2 + y^4$. This sequence has density just $c/N^{1/4}$ in the numbers up to $N$, so the analysis necessary to make the bilinear forms method work is really tough. Slightly later, Heath-Brown adapted their ideas to handle $x^3 + 2y^3$. Maybe that's in some sense the sparsest explicit sequence in which infinitely many primes are known (except of course for silly sequences like $s_n$ equals the first prime bigger than $2^{2^n}$).

Finally, let me add the following: proving that, for some fixed $n$, there are infinitely many primes which are the sum of $n$ powers of two - this is almost certainly an open problem of the same kind of difficulty as Mersenne primes and so on.

-
This is an excellent summary of the solution of this problem. I accept this answer. – dakota Apr 27 2010 at 18:04
Does Drmota, Mauduit, and Rivat's result come with an explicit bound on n? – Qiaochu Yuan Apr 27 2010 at 21:01
Qiaochu: no, but I believe it would give one in principle, in the sense that there is no ineffectivity arising from a potential Siegel Zero. People I know who have done the kind of explicit calculations necessary to extract actual bounds from arguments like this attest that it is very painful, and the bounds are often pretty awful to boot. – Ben Green Apr 27 2010 at 21:36

For this context, though not so highbrow: Wagstaff, Prime Numbers with a Fixed Number of One Bits or Zero Bits in Their Binary Representation, Experiment Math 10 (2001), 267-273.

http://www.expmath.org/restricted/10/10.2/wagstaff.ps

-

Standard heuristics on the distribution of primes indicate that there should be infinitely many primes of each Hamming weight $h \ge 3$. If that is true, together with the fact that 2 has weight one and 3 has weight two, you get a positive answer to your question. Turning these heuristics into a proof is likely to be very impossible with current "technology". So it's quite amazing that the proof described in Ben Green's answer exists.

Details of the heuristic. Fix a hamming weight $h \ge 3$. Let's look at integers of Hamming weight $h$ of the form $2^n + \sum_{j=1}^{h-2} 2^{a_j} + 1$, where $0 < a_1 < \cdots < a_{h-2} < n$. There are $n-1\choose{h-2}$ such integers and the probability of each of them being composite is $1-1/n\log 2$. If (BIG IF) these probabilities are independent then you expect that the probability of them all being composite is very small and you expect there to be primes of that form for infinitely many (or even all sufficiently large) $n$.

-

This is not an answer but an observation.

Let $n$ be an integer and $H(n)$ its Hamming weight.

$H(n) <= 1+ \max( { H(d) |\ d\ {\rm divisor\ of\ } n-1 })$

in particular for $p$ a prime greater than 2

$H(p) <= 1+ \max( { H(d) |\ d\ {\rm proper\ divisor\ of }\ p-1 })$

It could suggest ways to attack this and related questions.

-