4 added 110 characters in body

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 cab 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: http://mathoverflow.net/questions/22629/are-there-primes-of-every-hamming-weight

3 I linked to what I believe are the two earlier MO questions Gil meant to reference.

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

2 edited body

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

1