\documentclass[12pt]{article}

%%%%%%%%%%%%%%%%%%
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{txfonts}
\usepackage{enumerate}
\usepackage{fancyhdr}

%%%custom definitions
\renewcommand{\qedsymbol}{\nobreak
\fbox{\tiny \textsc{q.e.d.}}
}
\DeclareMathAlphabet{\mathscr}{OT1}{pzc}{m}{it}
%nice references
\newcounter{tmp}
\newcommand{\tmp}[1]{\setcounter{tmp}{#1}}
\newcommand{\refenumi}[1]{\tmp{\ref{#1}}\labelenumis{tmp}}
\renewcommand{\labelenumi}{(\roman{enumi})}
\newcommand{\labelenumis}[1]{(\roman{#1})}
%%%

%%%semantic definitions
\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\nonnegative}{\mathbb{N}}
\newcommand{\Prime}{\mathbb{P}}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\assign}{\leftarrow}
\newcommand{\for}{\hspace{1 pc}\mbox{for }}
\newcommand{\minus}{\backslash}
\newcommand{\normal}{\mbox{ }{\large \lhd}\mbox{ }}
\newcommand{\semidirect}{\mbox{ }{\Huge \rtimes}\mbox{ }}
\newcommand{\term}[1]{\textbf{#1}}
\renewcommand{\implies}{\Rightarrow}
\DeclareMathOperator*{\lcm}{lcm}
%%%

%%%local definitions
\newcommand{\PPub}[1]{#1\left(\ln #1 + \ln \ln #1\right)}
\newcommand{\PPlb}[1]{#1\left(\ln #1 + \ln \ln #1 - 1\right)}
\newcommand{\symnot}{\neg}
\newcommand{\symand}{\wedge}
\newcommand{\symor}{\vee}
\newcommand{\symimply}{\rightarrow}
\newcommand{\structure}[1]{\mathscr{#1}}
\newcommand{\stirling}[1]{\sqrt{2\pi (#1)}(\frac{#1}{e})^{#1}}
\newcommand{\tuple}[1]{\bar{#1}}
\DeclareMathOperator{\symxor}{XOR}
\DeclareMathOperator{\symnand}{NAND}
\DeclareMathOperator{\setSent}{Sent}
\DeclareMathOperator{\algTerm}{Term}
\DeclareMathOperator{\Pub}{up}
\DeclareMathOperator{\Plb}{lp}
%%%

%%%Theorem environment
\newtheorem{alg}{Algorithm}
\newtheorem{conj}{Conjecture}
\newtheorem{cor}{Corollary}
\newtheorem*{cor*}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem*{claim*}{Claim}
\newtheorem{dfn}{Definition}
\newtheorem{ex}{Example}
\newtheorem{lem}{Lemma}
\newtheorem{prob}{Problem}
\newtheorem{prop}{Proposition}
\newtheorem{soln}{Solution}
\newtheorem{thm}{Theorem}
\newtheorem*{thm*}{Theorem}
%%%

\begin{document}
%%% Title boilerplate
\title{Primes}
\author{\textsc{D. Dakota Blair}}
\baselineskip=4ex
\maketitle
%%%

\begin{abstract}
A question of primes.
\end{abstract}
\section{Nice bounds on $\pi(x)$ and other theorems}
\begin{thm}[Dusart 1998] The prime counting function $\pi(x)$ is bounded by
\[
\frac{x}{\ln x - 1} \leq \pi(x) \leq \frac {x}{\ln x - 1.1}
\]
where the lower bound works for $x \geq 60184$ and the upper bound works for
$x \geq 5393$.
\label{thm:dusart98}
\end{thm}
\begin{thm}[Dusart 1999] The $i$th prime $p_i$ is bounded by
\[
i(\ln i + \ln \ln i - 1) \leq p_i \leq i(\ln i + \ln \ln i) \for i \geq 6.
\]
\label{thm:dusart99}
\end{thm}

\pagebreak
\section{Does there exist a prime for every Hamming weight?}
That is, for every number $n$,
is there a prime where the number of $1$s in its binary expansion $n$?

Let $H(n)$ represent the hamming weight of $n$.

Given $n$, the smallest number $m$ such that $H(m)=n$ is $2^n-1$.
If $m$ is prime then it is a Mersenne Prime.
Then given $k$, the largest odd number $m$ with $H(m)=n$ and $k$ zeros
in its binary expansion is
$M_{n,k} = (2^{n-1}-1)(2^{k+1}) + 1 = 2^{n+k} - 2^{k+1} + 1$.
Define $H_n = \{k | k \in \integer, H(k) = n\}$,
\[
U_{n,k} = \left\{m \left|
m \mbox{ is odd, } H(m)=n,
m < (2^{n-1}-1)(2^{k+1})+1\right\}\right.,
\]
and similarly
\[
U_n = \bigcup_{k \in \nonnegative} U_{n,k}.
\]

Answering this question is equivalent to deciding the statement
$U_n \intersect \Prime \neq \emptyset$.

The number of odd numbers with $n$ ones and $k$ zeros is
\[
{n+k-1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!} = | U_{n,k} |.
\]

Let the number of integers
(respectively primes, composites, odds, numbers in $U_{n,k}$)
between the $n$th Mersenne number and $M_{n,k}$ be
$T_{n,k}$ ($P_{n,k}, C_{n,k}, O_{n,k}, Q_{n,k}$), so
\[
T_{n,k} = M_{n,k} - 2^n = 2^{n + k} - 2^{k+1} - 2^n + 1,
\]
\[
P_{n,k} = \pi(M_{n,k}) - \pi(2^n - 1) \leq l_{M_{n,k}} - u_{2^n - 1}
\]
\[
C_{n,k} = T_{n,k} - P_{n,k},
\]
\[
O_{n,k} = \frac{T_{n,k}-1}{2} + 1 = 2^{n + k - 1} - 2^k - 2^{n-1} + 1 ,
\]
and
\[
Q_{n,k} = \sum_{j=0}^k {n + j - 1 \choose j} = {n+k \choose k}.
\]
Further, let $R_{n,k}$ be some useful refinement of $T_{n,k}$ such as
the number of odd numbers between $2^n - 1$ and $M_{n,k}$.
So if for some $k$
\[
P_{n,k} > R_{n,k} - Q_{n,k}
\]
we would have that $U_n$ is nonempty.

Since $Q_{n,k} = {n+k \choose k}$ it is maximized when $n = k$ and
$Q_{n,n} = {2n \choose n} = \frac{2^{2n}}{2} = 2^{2n-1}.$
Note that $O_{n,n} = 2^{2n-1} - 2^n - 2^{n-1} + 1$, so if we can show
\[
P_{n,n} > 2^n + 2^{n-1} - 1 = 3 \cdot 2^{n-1} - 1
\]
is true for every $n$ we would have that $U_n$ is nonempty for every $n$.
What about $n=3$?
Since $P_{3,3} \approx 11.17, O_{3,3} = 11$ and $11.17 > 11$.
But these bounds only work for larger $n$ so more care is needed, but
this seems to be a valid path to a proof.

Note that our bounds are valid for
$x > 60184$ and $log_2(60184) \approx 15.8 < 16$
then we may use $n=16$ as our base case. The advantage of this is that
examples are known for $n$ up to 1024, hence proving this result will
be enough to show that it is true for all $n$.
Now if only I didn't have complex analysis homework to worry about!
%Using Stirling's approximation we see
%\[
%{n+k-1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!}
%= \frac{\stirling{n+k-1}}{\stirling{k}\stirling{n-1}}.
%\]

%We're really only interested in a fixed $n$ and variable $k$ so
%\[
%{n+k-1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!}
%= \frac{(n)(n+1)\cdots(n+k-1)}{k!}
%. 
%\]

%\begin{tabular}{l|l}
%$k$ & ${n+k-1 \choose k}$ \\ \hline
%$1$ & $n$\\
%$2$ & $\frac{n^2}{2} + \frac{3n}{2} + 1$
%\end{tabular}

%On the other hand, fixing $k$ reveals that the leading
%coefficient of ${n+k-1 \choose k}$ is $\frac{n^k}{k!}$.

%If this problem is easy, this should be enough to prove that 
%$U_n \intersect \Prime \neq \emptyset$,
%but that seems unlikely as $k!$ increases much faster than $n^k$.
%But $k$ is arbitrary, so it really depends on how nice of a bound
%can be placed on $p_i$.

\subsection{Given a number, what are bounds that
guarantee a prime in between?}
Denote the number of primes less than or equal to $k$ as $\pi(k)$,
the $i$th prime as $p_i$,
the probability that $k$ is prime as $P_\Prime(k)$,
the probability that at least one element of a set $k \in S \subset \integer$
is prime as $P_\Prime(S)$.
Note $\displaystyle\lim_{i\rightarrow\infty}\frac{p_{i+1}-p_i}{p_i} = 0$.
Let $l_k < \pi(k) < u_k$, $\Plb_i < p_i < \Pub_i$.
Then $p_{l_k} < k < p_{u_k}$ and, in particular,
\[
\Plb_{l_k} < k < \Pub_{u_k}.
\]

So $P_\Prime(\Pub_{u_k}) < P_\Prime(k)$.

Is it possible to prove
$U_n \intersect \Prime \neq \emptyset$ by computing the quantity
\[
P_\Prime(U_{n,k})?
%\sum_{i \in U_{n,k}} P_\Prime(i)?
\]
Thus our previous notations $\Plb_i$ and $\Pub_i$ may be defined as the
bounds given in theorems \ref{thm:dusart98} and \ref{thm:dusart99}.
Now using our earlier calculation we see that given a sufficiently large
integer $k$
\[
\PPlb{\frac{k}{\ln k - 1}} \leq k \leq \PPub{\frac{k}{\ln k - 1.1}}.
\]
These bounds are interesting in that they guarantee at least two primes in
the given interval, but they are awfully weak. We would like a good estimate
of $P_\Prime(u_k)$. This is given by
\[
P_\Prime(u_k) \geq \frac{l_k}{k} = \frac{1}{\ln k - 1}. 
\]
So we can now give our first estimate of the desired quantity.
Let $m = \max U_{n,k} = (2^{n-1} - 1)(2^{k+1}) + 1$, then
\[
P_\Prime(U_{n,k}) = 1 - (1-P_\Prime(u_{m}))^{n+k-1 \choose k}
= 1 - \left(1-\frac{1}{\ln m - 1}\right)^{n+k-1 \choose k}
= 1 - \left(\frac{\ln m - 2}{\ln m - 1}\right)^{n+k-1 \choose k}
%\sum_{i \in U_{n,k}} P_\Prime(i) \geq
%\frac{{n + k - 1 \choose k}}{\ln ((2^{n-1} - 1)(2^{k+1}) + 1) - 1} \geq
%\frac{{n + k - 1 \choose k}}{(n+k)\ln 2}
\]
Although interesting, this does not directly help as this amounts to a merely
heuristic argument.

\section{How many primes for a given Hamming weight are there?}
If a lower bound exists, then this proves the answer to the first question is yes.

Proving a lower bound might make use of the density of primes.

That is, calculate the probability of the numbers described above being prime,
then determine how many one must pick in order to ``ensure'' a prime.

\end{document}
