|
12
|
|
|
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.
Edit: At some point, I deleted my answer because I was unsatisfied with it. It has now been improved significantly.
|
|
|
|
|
11
|
|
|
We can take $f(n)=\alpha n$ for any $\alpha<0.7375$. In particular, the set of primes with 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.
Edit: At some point, I deleted my answer because I was unsatisfied with it. It has now been improved significantly.
|
|
|
| |
|
Post Undeleted by Eric Naslund
|
|
|
|
|
|
|
10
|
|
|
I deleted my answer. It resolved everything in this question in an elementary way We can take $f(n)=\alpha n$ for any $\alpha<0.7375$. In particular, but I am not interested the set of primes with twice as many ones that zeros in sharing my solution at this timetheir binary expansion is infinite.Likely I will come back and edit this later, making posted a better and more improved answer. To those short article on the arXiv which deals with enough reputation to read 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, you can simply look 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 edit history if you were interestedbound $$\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. Regards,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.
|
|
|
|
|
9
|
|
|
In this answer we resolve the main questions asked, proving that the set $A$ is infinite, and that the set of primes with at least a proportion $\alpha$ of $1$'s is infinite for all $0<\alpha <\frac{17}{24}$. In other words, we are able to show that $A[f]$ is infinite for $f(n)=\gamma n$, for all $\gamma<\frac{5}{24}$, that is a positive constant times $n$. Note as well, for $\alpha>\frac{1}{2}$, the set of integers with at least $\alpha$ 1's has density $N^\beta$, and if we take $\alpha$ close to $\frac{17}{24}$, we will have $\beta\approx 0.87$. For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. We show that: Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$ Theorem 2. (Main Theorem) Let $\frac{1}{2}>\epsilon>0$ be fixed, and let $\alpha=\frac{17}{24}-\epsilon.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$ I would like to emphasize that the binomial distribution/normal distribution has very small tails. This is the key idea that our proof will try to exploit. Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digitsdeleted my answer.The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of It resolved everything in this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's. Proof of Theorem 2: Let $\alpha=\frac{17}{24}-2\epsilon$. Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ $\delta=\frac{7}{12}+\epsilon,$ and consider the integers question in the interval $$\left[2^{n}-2^{\delta n},2^{n}-1\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with less then $\alpha$ of their binary digits equal to 1, that is with more then $1-\alpha$ zeros. Since the first digits are all $1$ , of our last $\delta n$ digits, we would need to have at least $(1-\alpha)=\frac{7}{24}+2\epsilon$ zeros. By the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{\delta n}{2}-\left(\frac{7}{24}+2\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-n\frac{3}{2}\epsilon\right).$$ Hencean elementary way, there are almost no vectors but I am not interested in this interval with a proportion less then $\alpha$ of their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have sharing my solution at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$ Theorem 3: We have that $$S_\frac{1}{2}(x)\sim \frac{1}{2}\pi(x).$$ time. Likely I did not include will come back and edit this prooflater, as it requires making a better and more work, but it follows using similar ideas. Note that this is different then the asymptotics given in the other improved answer.There they count the number with exactly $\frac{1}{2}$, here we count To those with at least $\frac{1}{2}$. Remark: Under the Riemann Hypothesisenough reputation to read this, using the same proof we you can extend simply look at the range to $\alpha<\frac{3}{4}$. For our current theorem, it may be possible, edit history if one is carefulyou were interested. Regards,to remove the $-\epsilon$, and prove that the set is infinite for $\alpha=\frac{17}{24}$.
|
|
|
| |
|
Post Deleted by Eric Naslund
|
|
|
|
|
|
|
|
8
|
|
edited May 20 2012 at 10:41 |
In this answer we resolve the main questionquestions asked, proving that the set $A$ is infinite. Furthermore, we show and that the set of primes with at least a proportion $\alpha$ of $1$'s is infinite for all $0<\alpha <\frac{17}{24}$.
In other words, we are able to show that $A[f]$ is infinite for $f(n)=\gamma n$, for all $\gamma<\frac{5}{24}$, that is a positive constant times $n$. Note as well, for $\alpha>\frac{1}{2}$, this the set of integers with at least $\alpha$ 1's has density $N^\beta$ for some N^\beta$, and if we take $\beta<1$. \alpha$ close to $\frac{17}{24}$, we will have $\beta\approx 0.87$.
For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. We show that:
Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$
Theorem 2. (Main Theorem) Let $\frac{1}{2}>\epsilon>0$ be fixed, and let $\alpha=\frac{17}{24}-\epsilon.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$
I would like to emphasize that the binomial distributions tails are distribution/normal distribution has very small tails. This is the key idea that our proof will try to exploit.
Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digits. The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's.
Proof of Theorem 2: Let $\alpha=\frac{17}{24}-2\epsilon$. Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then \delta=\frac{7}{12}+\epsilon,$ and consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}-1\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more less then $\alpha$ of their binary digits equal to zero1, that is with more then $1-\alpha$ zeros. Since the first digits are all $1$ , of our last $\delta n$ digits, we would need to have at least $(1-\alpha)=\frac{7}{24}+2\epsilon$ zeros. By the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{\delta n}{2}-\left(\frac{7}{24}+2\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-n\frac{3}{2}\epsilon\right).$$ Hence, there are almost no vectors in this interval with a proportion less then $\alpha$ of their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
Theorem 3: We have that $$S_\frac{1}{2}(x)\sim \frac{1}{2}\pi(x).$$
I did not include this proof, as it requires more work, but it follows using similar ideas. Note that this is different then the asymptotics given in the other answer. There they count the number with exactly $\frac{1}{2}$, here we count those with at least $\frac{1}{2}$.
Remark: Under the Riemann Hypothesis, using the same proof we can extend the range to $\alpha<\frac{3}{4}$. For our current theorem, it may be possible, if one is careful, to remove the $-\epsilon$, and prove that the set is infinite for $\alpha=\frac{17}{24}$.
|
|
|
|
|
7
|
|
edited May 19 2012 at 9:47 |
In this answer we resolve the main question, proving that the set $A$ is infinite. Furthermore, we show that the set of primes with at least a proportion $\alpha$ of $1$'s is infinite for all $0<\alpha <\frac{17}{24}$. In other words, we are able to show that $A[f]$ is infinite for $f(n)=\frac{5}{24}n$, f(n)=\gamma n$, for all $\gamma<\frac{5}{24}$, that is a positive constant times $n$. Note as well, for $\alpha>\frac{1}{2}$, this set has density $N^\beta$ for some $\beta<1$.
For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. We show that:
Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$
Theorem 2. (Main Theorem) Let $\frac{1}{2}>\epsilon>0$ be fixed, and let $\alpha=\frac{17}{24}-\epsilon.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$
I would like to emphasize that the binomial distributions tails are very small. This is the key idea that our proof will try to exploit.
Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digits. The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's.
Proof of Theorem 2: Let $\alpha=\frac{17}{24}-2\epsilon$. Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}-1\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more then $\alpha$ of their binary digits equal to zero. Since the first digits are all $1$ , of our last $\delta n$ digits, we would need to have at least $(1-\alpha)=\frac{7}{24}+2\epsilon$ zeros. By the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{\delta n}{2}-\left(\frac{7}{24}+2\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-n\frac{3}{2}\epsilon\right).$$ Hence, there are almost no vectors in this interval with a proportion less then $\alpha$ of their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
Theorem 3: We have that $$S_\frac{1}{2}(x)\sim \frac{1}{2}\pi(x).$$
I did not include this proof, as it requires more work, but it follows using similar ideas. Note that this is different then the asymptotics given in the other answer. There they count the number with exactly $\frac{1}{2}$, here we count those with at least $\frac{1}{2}$.
Remark: Under the Riemann Hypothesis, using the same proof we can extend the range to $\alpha<\frac{3}{4}$. For our current theorem, it may be possible, if one is careful, to remove the $-\epsilon$, and prove that the set is infinite for $\alpha=\frac{17}{24}$.
|
|
|
|
|
6
|
|
edited May 18 2012 at 20:39 |
In this answer we resolve the main question, proving that the set $A$ is infinite. Furthermore, we show that the set of primes with at least a proportion $\alpha$ of $1$'s is infinite for all $0<\alpha <\frac{17}{24}$. In other words, we are able to show that $A[f]$ is infinite for $f(n)=\frac{5}{24}n$, that is a positive constant times $n$. Note as well, for $\alpha>\frac{1}{2}$, this set has density $N^\beta$ for some $\beta<1$.
For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. We show that:
Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$
Theorem 2. (Main Theorem) Let $\frac{1}{2}>\epsilon>0$, \frac{1}{2}>\epsilon>0$ be fixed, and let $\alpha=\frac{17}{24}.$ \alpha=\frac{17}{24}-\epsilon.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$
I would like to emphasize that the binomial distributions tails are very small. This is the key idea that our proof will try to exploit.
Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digits. The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's.
Proof of Theorem 2: Let $\alpha=\frac{17}{24}-2\epsilon$. Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}-1\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more then $\alpha$ of their binary digits equal to zero. Since the first digits are all $1$ , of our last $\delta n$ digits, we would need to have at least $(1-\alpha)=\frac{7}{24}+2\epsilon$ zeros. By the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{\delta n}{2}-\left(\frac{7}{24}+2\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-n\frac{3}{2}\epsilon\right).$$ Hence, there are almost no vectors in this interval with a proportion less then $\alpha$ of their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
Theorem 3: We have that $$S_\frac{1}{2}(x)\sim \frac{1}{2}\pi(x).$$
I did not include this proof, as it requires more work, but it follows using similar ideas. Note that this is different then the asymptotics given in the other answer. There they count the number with exactly $\frac{1}{2}$, here we count those with at least $\frac{1}{2}$.
|
|
|
|
|
5
|
|
edited May 18 2012 at 20:22 |
Remark: I just realized that I can modify my proof to show the set is infinite for $\alpha<\frac{17}{24}\approx 0.7$. (Maybe with a $-\epsilon$) This corresponds to taking $f(n)=\frac{5}{24}n$. Will update in an hour. In this answer we resolve the main question, and prove proving that the set $A$ is infinite. Furthermore, we show that the set of primes with at least a proportion $\alpha$ of $1$'s is infinite for all $0<\alpha <\frac{17}{24}$. In other words, we are able to show that $A[f]$ is infinite for $f(n)=\frac{5}{24}n$, that is a positive constant times $n$. Note as well, for $\alpha>\frac{1}{2}$, this set has density $N^\beta$ for some $\beta<1$. Theorem 2. (Main Theorem) Let $\alpha=\frac{1}{2}.$ \frac{1}{2}>\epsilon>0$, and let $\alpha=\frac{17}{24}.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$ Proof of Theorem 2: Let $\alpha=\frac{17}{24}-2\epsilon$. Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}-1\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more then half $\alpha$ of their binary digits equal to zero. Since the first digits are all $1$ , our of the our last $\delta n$ digits, we would need to have at least $\delta-\frac{1}{2}$ (1-\alpha)=\frac{7}{24}+2\epsilon$ zeros. As $\delta-\frac{1}{2}=\frac{1}{12}+\epsilon,$ we see that again by By the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{\delta n}{2}-\left(\frac{1}{12}+\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-nC\right).$$ n}{2}-\left(\frac{7}{24}+2\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-n\frac{3}{2}\epsilon\right).$$ Hence, there are almost no vectors in this interval with a proportion less then $\frac{1}{2}$ \alpha$ of their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
|
|
|
|
|
4
|
|
edited May 18 2012 at 20:09 |
Remark: I just realized that I can modify my proof to show the set is infinite for $\alpha<\frac{17}{24}\approx 0.7$. (Maybe with a $-\epsilon$) This corresponds to taking $f(n)=\frac{5}{24}n$. Will update in an hour.
In this answer we resolve the main question, and prove that the set $A$ is infinite. For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. We show that:
Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$
Theorem 2. (Main Theorem) Let $\alpha=\frac{1}{2}.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$
I would like to emphasize that the binomial distributions tails are very small. This is the key idea that our proof will try to exploit.
Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digits. The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's.
Proof of Theorem 2: Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}-1\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more then half their binary digits equal to zero. Since the first digits are all $1$ , our of the last $\delta n$ digits, we would need to have at least $\delta-\frac{1}{2}$ zeros. As $\delta-\frac{1}{2}=\frac{1}{12}+\epsilon,$ we see that again by the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{n}{2}-\left(\frac{1}{12}+\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-\frac{\left(\frac{\delta n}{2}-\left(\frac{1}{12}+\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-nC\right).$$ Hence, there are almost no vectors in this interval with less then $\frac{1}{2}$ their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
Theorem 3: We have that $$S_\frac{1}{2}(x)\sim \frac{1}{2}\pi(x).$$
I did not include this proof, as it requires more work, but it follows using similar ideas. Note that this is different then the asymptotics given in the other answer. There they count the number with exactly $\frac{1}{2}$, here we count those with at least $\frac{1}{2}$.
|
|
|
|
|
3
|
|
edited May 18 2012 at 19:45 |
Remark: I just realized that I can modify my proof to show the set is infinite for $\alpha<\frac{17}{24}\approx 0.7$. (Maybe with a $-\epsilon$) This corresponds to taking $f(n)=\frac{5}{24}n$. Will update in an hour.
In this answer we resolve the main question, and prove that the set $A$ is infinite. For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. We show that:
Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$
Theorem 2. (Main Theorem) Let $\alpha=\frac{1}{2}.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$
I would like to emphasize is that the binomial distributions tails are very small. This is the key idea that our proof will try to exploit.Also, because of this, dealing with fixed $\alpha>\frac{1}{2}$ seems almost entirely out of reach.
Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digits. The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's.
Proof of Theorem 2: Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}\right].$$ n},2^{n}-1\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more then half their binary digits equal to zero. Since the first digits are all $1$ , our of the last $\delta n$ digits, we would need to have at least $\delta-\frac{1}{2}$ zeros. As $\delta-\frac{1}{2}=\frac{1}{12}+\epsilon,$ we see that again by the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{n}{2}-\left(\frac{1}{12}+\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-nC\right).$$ Hence, there are almost no vectors in this interval with less then $\frac{1}{2}$ their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
Theorem 3: We have that $$S_\frac{1}{2}(x)\sim \frac{1}{2}\pi(x).$$
I did not include this proof, as it requires more work, but it follows using similar ideas. Note that this is different then the asymptotics given in the other answer. There they count the number with exactly $\frac{1}{2}$, here we count those with at least $\frac{1}{2}$.
|
|
|
|
|
2
|
|
edited May 18 2012 at 19:30 |
In this answer we resolve the main question, and prove that the set $A$ is infinite. For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. In this answer we resolve the main question, and proveWe show that:
Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$
Theorem 2. (Main Theorem) Let $\alpha=\frac{1}{2}.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$
The key idea
I would like to emphasize is that the binomial distributions tails are very small. Because This is the key idea that our proof will try to exploit. Also, because of this, dealing with fixed $\alpha>\frac{1}{2}$ seems almost entirely out of reach.
Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digits. The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's.
Proof of Theorem 2: Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more then half their binary digits equal to zero. Since the first digits are all $1$ , our of the last $\delta n$ digits, we would need to have at least $\delta-\frac{1}{2}$ zeros. As $\delta-\frac{1}{2}=\frac{1}{12}+\epsilon,$ we see that again by the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{n}{2}-\left(\frac{1}{12}+\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-nC\right).$$ Hence, there are almost no vectors in this interval with less then $\frac{1}{2}$ their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
Theorem 3: We have that $$S_\frac{1}{2}(x)\sim \frac{1}{2}\pi(x).$$
I did not include this proof, as it requires more work, but it follows using similar ideas. Note that this is different then the asymptotics given in the other answer. There they count the number with exactly $\frac{1}{2}$, here we count those with at least $\frac{1}{2}$.
|
|
|
|
|
1
|
|
answered May 18 2012 at 19:20 |
For $0<\alpha<1,$ let $S_{\alpha}(x)$ denote the number of primes less then $x$ such that a proportion of at least $\alpha$ of the digits are $1$'s. In this answer we resolve the main question, and prove:
Theorem 1. Fix $0<\alpha<\frac{1}{2}.$ Then we have $$S_{\alpha}(x)\sim\pi(x).$$
Theorem 2. Let $\alpha=\frac{1}{2}.$ Then as $x\rightarrow \infty$, $$S_{\alpha}(x)\rightarrow\infty.$$
The key idea I would like to emphasize is that the binomial distributions tails are very small. Because of this, dealing with fixed $\alpha>\frac{1}{2}$ seems almost entirely out of reach.
Proof of Theorem 1: Let $N=2^{n}$ so that we are dealing with $n$ digits. The Chernoff inequality tells us that for the binomial distribution, $$\Pr\left(X\leq\alpha n\right)\leq\exp\left(-\frac{\left(\frac{n}{2}-\alpha n\right)^{2}}{n}\right)=\exp\left(-n\left(\frac{1}{2}-\alpha\right)^{2}\right).$$ As $n\rightarrow\infty,$ the density of this set goes to zero extremely fast, faster then $\frac{1}{\log N},$ so we see that almost all primes must have a proportion of at least $\alpha$ 1's.
Proof of Theorem 2: Here we use Huxleys theorem on prime gaps which states that for any $\epsilon>0 ,$ we have $$\pi\left(x+x^{\frac{7}{12}+\epsilon}\right)-\pi(x)\sim\frac{x^{\frac{7}{12}+\epsilon}}{\log x}.$$ Let $N=2^{n},$ and consider $M=2^{\delta n}$ for $\delta=\frac{7}{12}+\epsilon.$ Then consider the integers in the interval $$\left[2^{n}-2^{\delta n},2^{n}\right].$$ The first $\left(1-\delta\right)n$ digits must all be ones, and the last $\delta n$ digits will be binomially distributed. Out of these vectors, consider all those with more then half their binary digits equal to zero. Since the first digits are all $1$ , our of the last $\delta n$ digits, we would need to have at least $\delta-\frac{1}{2}$ zeros. As $\delta-\frac{1}{2}=\frac{1}{12}+\epsilon,$ we see that again by the Chernoff inequality, the number of such vectors is $$\leq2^{\delta n}\exp\left(-\frac{\left(\frac{n}{2}-\left(\frac{1}{12}+\epsilon\right)n\right)^{2}}{n}\right)=2^{\delta n}\exp\left(-nC\right).$$ Hence, there are almost no vectors in this interval with less then $\frac{1}{2}$ their digits equal to $1$. By Huxleys result, there are $\frac{1}{\log (2^N)}2^{\delta n}$ primes, and hence we conclude that almost all of these primes have at least half their digits equal to $1.$ Since this works for all sufficiently large $n,$ we have shown that $$S_{\alpha}(x)\rightarrow\infty$$ as $x\rightarrow\infty.$
|
|
|
