This question is also motivated by the developement around my old MO question about Mobius randomness. It is also motivated by Joe O'Rourke's question on finding primes in sparse sets.

Let $A$ be the set of all natural numbers with more ones than zeroes in their binary expansion. Are there infinitely many primes in $A$?

More generally, for a function $f(n)$ defined on the natural numbers let $A[f]$ denotes the set of integers with $n$ digits and at least $n/2+f(n)$ ones, for $n=1,2,...$. Does $A[f]$ contains infinitely many primes?

Bourgain proved the Mobius randomness of $A$ and this seems closely related to this question. But I am not sure about the exact connection. (In fact Bourgain proved Mobius randomness for every $A$ described by a balanced monotone Boolean function of the binary digits.)

Showing infinitely many primes for sparse $[f]$ would be interesting. Proving this for $f(n)=\alpha n$ where $\alpha>0$ is small would be terrific. Of course, if $f(n)=n/2$ we are talking about Mersenne's prime so I would not expect an answer here. (Showing infinite primes for $A$ with smaller size than $\sqrt n$ will cross some notable barrier.)

A similar question can be asked about balanced (and unbaland) sets described by $AC^0$-formulas. This corresponds to Ben Green's $AC^0$ prime number theorem but also here I am not sure what it will take to move from Mobius randomness to infinitude of primes.

Another related question: Are There Primes of Every Hamming Weight?

  • 27
    $\begingroup$ This is probably not the answer you were looking for and certainly isn't meant as an answer, but for what it's worth, it seems this would follow from applying Goldbach's conjecture to numbers of the form $2^n$ and noting that if two odd numbers add up to $2^n$, then at least one of them has more ones than zeroes in its binary representation. Goldbach's conjecture is open, but just saying. $\endgroup$ – user22202 May 18 '12 at 10:47
  • $\begingroup$ hope you don't mind the comment! :) $\endgroup$ – user22202 May 18 '12 at 10:57
  • 1
    $\begingroup$ The result is also true assuming the Heath-Brown conjecture that the smallest prime in an arithmetic progression is $\le d^2$, where $d$ is the common difference of the progression. Unfortunately with this approach, the best unconditional result is $\alpha\approx 1/5$. $\endgroup$ – Gjergji Zaimi May 18 '12 at 14:44
  • 2
    $\begingroup$ @unknown: a very nice comment, but will this necessarily produce infinitely many primes? @Gil: who is Eric (I assume not the demi-bee)? $\endgroup$ – Igor Rivin May 18 '12 at 15:01
  • 4
    $\begingroup$ So now we have an answer conditional on Goldbach's conjecture, an answer conditional on the GRH, and an answer conditional on Legendre's conjecture (strengthening the result on Cramer). How strange... $\endgroup$ – Charles May 18 '12 at 17:30

The OP's conjecture follows from theorem 1.1 in "Primes with an average sum of digits" by Drmota, Mauduit and Rivat. They prove that the number of primes $\le x$ with $k$ binary digits is given by $$\frac{\pi(x)}{\sqrt{(\pi/2) \log x }}\left(e^{-\frac{2(k-\frac{1}{2}\log x)^2}{\log x}}+O(\log x^{-\frac{1}{2}+\epsilon})\right).$$ So inparticular this shows the stronger result in your question corresponding to the function $f(n)=\alpha \sqrt{n}$. (So one has infinitely many primes with $\frac{n}{2}+\alpha\sqrt{n}$ ones in their binary expansion.) The authors say that they weren't able to get any bounds for $f(n)=\alpha n$ with any $\alpha > 0$.

  • 2
    $\begingroup$ The thread mathoverflow.net/questions/22629/… contains an excellent answer of Ben Green's giving a very rough overview of the method used in the paper by M. Drmota, C. Mauduit and J. Rivat, as well as other interesting comments related to Gil's question. $\endgroup$ – Daniel m3 May 19 '12 at 18:25

We can take $f(n)=\alpha n$ for any $\alpha<0.7375$. In particular, the set of primes with more than twice as many ones that zeros in their binary expansion is infinite.

I posted a short article on the arXiv which deals with exactly this kind of problem. Let $s_2(n)$ denote the sum of digits base $2$. Since $x$ has approximately $\log_2(x)$ binary digits, we are looking at when $s_2(n)\geq \alpha \log_2 (n)$. In that 4 page note we prove that

$$\left|\left\{ p\leq x,\ p\ \text{prime}\ : s_2(n)\geq \alpha\log_2(x) \right\} \right|\gg_{\epsilon}\ x^{2\left(1-\alpha\right)}e^{-c\left(\log x\right)^{1/2+\epsilon}}.$$

Moreover, such a result extends naturally to base $q$, yielding the bound

$$\left|\left\{ p\leq x,\ p\ \text{prime}\ :\ s_{q}(p)\geq\alpha(q-1)\log_{q}(x)\right\} \right|\gg_{\epsilon}\ x^{2\left(1-\alpha\right)}e^{-c\left(\log x\right)^{1/2+\epsilon}}$$ where $s_q(n)$ is the sum of digits of $n$ in base $q$.

The proof takes advantage of the fact that the multinomial distribution is sharply peaked. The number $0.7375$ appears because $1-0.525/2=0.7375$, and $0.525$ is the exponent appearing in Baker Harman and Pintz's work on prime gaps.


If Linnik's constant is two, as conjectured (and something like that follows from GRH), then the least prime congruent to $2^n-1$ modulo $2^n$ has more ones than zeros in its binary expansion. Since Linnik's constant is down to $5.2$ unconditionally, you get something a bit weaker unconditionally too.


I suppose this will follow from the plausible Cramer's conjecture about prime gap of $O(\log^2{p_n})$.

Let $n=(2^k-1)2^m$ with $m < k$ and $2^m>C\log^2{n}$ (actually $ m > \log{(C\log^2({2^m(2^k-1))}}/\log{(2)} $ will do.)

$n$ has $k$ ones and (much) less zeros. The interval $(n,n+C\log^2{n})$ with $2^m>C\log^2{n}$ will contain a prime $p=n+\delta$. $\delta$ will contribute at least one $1$ to the zero bits of $n$ keeping all of the ones. There are infinitely many choices for $m,k$ producing distinct primes..

Legendre conjecture probably will do too.

Note that the doubly logarithmic choice of $m$ contributes relatively few zeros.

Added So if you believe Cramer's conjecture, there are infinitely many $n$ for which $n$ bit primes have only $O(\log{n})$ zeros in their Binary expansion.

(btw, I would be very interested in unconditional answer to the question).

  • 2
    $\begingroup$ Legendre's conjecture works since it implies that there is a prime in [(16^n-1)^2, (16^n)^2]. Any such prime is an 8n-bit number starting with 4n-1 ones and ending with a 1. But not all the remaining digits can be 0, since that number is divisible by 3. Thus at least 4n+1 out of 8n bits are 1. $\endgroup$ – Charles May 18 '12 at 15:06
  • $\begingroup$ Thanks Charles. Can the RH gap bound of $O(\sqrt{x}\log{x})$ prove this question? $\endgroup$ – joro May 18 '12 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.