Are There Primes of Every Hamming Weight? - MathOverflow

Are There Primes of Every Hamming Weight?

2010-04-26T18:29:45Z

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}$?

Answer by ogerard for Are There Primes of Every Hamming Weight?

2010-04-27T14:28:54Z

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.

Answer by Ben Green for Are There Primes of Every Hamming Weight?

2010-04-27T16:01:07Z

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.

Answer by Felipe Voloch for Are There Primes of Every Hamming Weight?

2010-04-27T16:07:08Z

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$.

Answer by Junkie for Are There Primes of Every Hamming Weight?

2010-04-27T20:12:28Z

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