If I understand correctly, in the following thread

Are There Primes of Every Hamming Weight?

two users of the site claim that it has been already proven that, for every sufficiently large $n \in \mathbb{N}$, there exist primes numbers with Hamming weight equal to $n$. Their claim is apparently supported by Theorem 1.2 of the paper "Primes with an average sum of digits" by M. Drmota, C. Mauduit, and J. Rivat.

Do you know if there is a text out there in which the deduction of the existence of primes with Hamming weight $n$ from the said theorem by Drmota, Mauduit, and Rivat is established in a thorough manner? Like other users of the site (see the sections of comments in the aforementioned thread), I am not totally sure of the veracity of such a claim. In case that you believe that there is no author out there that has dealt with this topic in detail but you consider that you've gotten the idea of the proof, would you be so kind as to explain it below as though I were a five-year old?

Thanks in advance for your help!

  • 1
    $\begingroup$ The statement follows immediately from Theorem 1.1 in the linked paper if you take $q=2$ and $k=n$. You just have to note that the expression in the bracket tends to infinity as $x\to\infty$. $\endgroup$
    – Wojowu
    May 29, 2019 at 21:55
  • $\begingroup$ @Wojowu For which values of $n$ does this expression tend to infinity? We cannot expect to take $n=2$ for example since this would give infinitely many Fermat primes. $\endgroup$ May 29, 2019 at 22:17
  • 1
    $\begingroup$ Careful! Take x = q^{k/\mu_q} and apply Theorem 1.1. The term in parentheses is 1 + O((\log{x})^{-1/2+\eps}). For k >> 1 this will be > 1/2. Also for k >> 1 the thing it’s multiplied by will be > 10. So the left-hand side is > 1. You see that needing k sufficiently large comes from the fact that the exponential in the parentheses has to beat the error term (and in particular the implicit constant). Hope that makes sense! $\endgroup$
    – alpoge
    May 29, 2019 at 22:52
  • $\begingroup$ [If you were to fix k and take x to infinity the exponential term would die way faster than the log term in the parentheses, unless I’ve misread something, which is why I said careful in the previous comment.] $\endgroup$
    – alpoge
    May 29, 2019 at 22:53
  • $\begingroup$ @alpoge I think you're right: we need the fact that the statement is uniform in $k$. $\endgroup$ May 29, 2019 at 23:00

1 Answer 1


As Wojowu and alpoge have said in the comments, this follows immediately from Theorem 1.1 of Drmota-Mauduit-Rivat paper, but here is more detail on exactly why, as requested.

Theorem 1.1 of the Drmota-Mauduit-Rivat paper with $q=2$ and $k=n$ and $\epsilon=1/4$ gives that the number of primes $p\leq x$ with Hamming weight $n$ is equal to

$$\frac{\pi(x)}{\sqrt{\frac{\pi}{2}\log_2x}} \left( e^{-\frac{(n-\frac{1}{2}\log_2x)^2}{\frac{1}{2}\log_2x}}+O((\log x)^{-1/4})\right),$$

where the implicit constant in the $O(\cdot)$ notation is absolute.

In particular, if $n=\lfloor\frac{1}{2}\log_2(x)\rfloor$, the main term inside the brackets is at least $e^{-2/\log_2x}$ and the error term is $O(e^{-\log\log x/4})$. The main term is greater than the error term (and in particular the whole expression is positive and hence $\geq 1$) provided

$$2/\log_2x < \frac{1}{4}\log\log x-C,$$

where $C>0$ is the logarithm of whatever constant is hidden in the $O(\cdot)$ notation.

This obviously holds for all large $x$, say all $x\geq X$, and we have found at least one (actually many) primes with Hamming weight $n$ whenever $n\geq \log_2(X)/2$. To find out exactly what this threshold is, you need to work out what the implicit constant in the $O(\cdot)$ notation is, which presumably can be done by carefully tracking the constants throughout their proof (although likely this constant will be terrible).

  • $\begingroup$ Thanks for your answer! $\endgroup$
    – Jamai-Con
    Mar 18, 2021 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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