<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\def\N{\mathbb{N}}
\def\pp{\pi_\pi}
\def\e{\epsilon}
\def\t{\theta}
\def\a{\alpha}
\def\b{\beta}

\def\P{\mathbb{P}}
\def\d{\delta}
\def\s{\sigma}

\DeclareMathOperator \Li {Li} \DeclareMathOperator \loglog {loglog}
\def\lam{\lambda}
\def\s{\sigma}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
On the Subsequence of Primes Having Prime \\
\vskip .1in
Subscripts
}
\vskip 1cm
\large
Kevin A. Broughan and A. Ross Barnett \\
University of Waikato \\
Hamilton, New Zealand \\
\href{mailto:kab@waikato.ac.nz}{\tt kab@waikato.ac.nz} \\
\end{center}

\vskip .2 in

\begin{abstract}
We explore the subsequence of primes with prime
subscripts, $(q_n)$, and derive its density and estimates for its
counting function. We obtain bounds for the weighted gaps between
elements of the subsequence and show that for every positive integer
$m$ there is an integer arithmetic progression $(an+b:n\in\N)$ with
at least $m$ of the $(q_n)$ satisfying $q_n=an+b$.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}




%\usepackage{epsf,amssymb,amsmath}
%\usepackage[dvips]{graphicx}






%-----------------------------------------------------------------------------

\section{Introduction}

There are a number of subsets of primes with a conjectured density
of a constant times $x/\log^2 x$. These include the primes separated
by a fixed even integer, Sophie Germain primes and the so-called
``thin primes", i.e., primes of the form $2^e q-1$ where $q$ is prime
\cite{broughan}.

In order to gain some familiarity with sequences of this density we
undertook an investigation of the set of primes of prime order,
called here ``prime-primes", and report on the results of this
investigation here. Some of the properties of this sequence are
reasonably straight forward and the derivation follows that of the
corresponding property for the primes themselves. Others appear to
be quite deep and difficult. Of course the process of taking a prime
indexed subsequence can be iterated, leading to sequences of primes
of density $x/\log^3 x$, $x/\log^4 x$ etc, but these sequences are
not considered here.

In Section 2 upper and lower bounds for the $n^{th}$ prime-prime are
derived, in Section 3 the prime-prime number theorem is proved with
error bounds equivalent to that of the prime number theorem, in
Section 4 an initial study of gaps between prime-primes is begun,
and in Section 5 it is shown that for each $m$ there is an
arithmetic progression containing $m$ prime-primes.



\begin{definition}
A {\it prime-indexed-prime} or {\it prime-prime} is a rational prime
$q$ such that when the set of all primes is written in increasing
order $(p_1, p_2,\cdots)=(2, 3, \cdots)$, we have $q=p_n$ where $n$
is prime also.
\end{definition}

Here is a list of the primes up to 109 with the prime-primes in bold
type so $q_1=p_2=3$ and $q_{10}=p_{29}=109$: 2, {\bf 3}, {\bf 5}, 7,
{\bf 11}, 13, {\bf 17}, 19, 23, 29, {\bf 31}, 37, {\bf 41}, 43, 47,
53, {\bf 59}, 61, {\bf 67}, 71, 73, 79, {\bf 83}, 89, 97, 101, 103,
107, {\bf 109}.
%$$
%\begin{eqnarray*}
%p_1 &amp;=&amp; 2,\\
%p_2 &amp;=&amp; q_1=3, \\
%p_3 &amp;=&amp; q_2=5,~ p_4=7,\\
%p_5 &amp;=&amp; q_3=11,~ p_6=13,\\
%p_7 &amp;=&amp; q_4=17,~p_8=19,~ p_9=23,~ p_{10}=29,\\
%p_{11} &amp;=&amp; q_5=31,~ p_{12}=37,\\
%p_{13} &amp;=&amp; q_6=41,~ p_{14}=43,~ p_{15}=47,~ p_{16}=53,\\
%p_{17} &amp;=&amp; q_7=59,~ p_{18}=61\\
%p_{19} &amp;=&amp; q_8=67,~ p_{20}=71,~ p_{21}=73,~ p_{22}=79,\\
%p_{23} &amp;=&amp; q_9=83, ~p_{24}=89,~ p_{25}=97,~ p_{26}=101,~ p_{27}=103,~ p_{28}=107,\\
%p_{29} &amp;=&amp; q_{10}=109.
%\end{eqnarray*}
\begin{definition}
If $x&gt;0$ the number of prime-primes $q$ up to $x$ is given by $\pp
(x) := \sum_{q\le x} 1$. Then $\pi_\pi(x)= \pi(\pi(x))=\sum_{n=1}^x
\chi_\P (n)\cdot\chi_\P(\pi(n))$, where $\chi_\P(n) :=
\pi(n)-\pi(n-1)$, for $n\in\N$, is the characteristic function of
the primes.
\end{definition}
\section{Bounds for the sequence of prime-primes:}
The following theorem and its corollary gives a set of useful
inequalities for estimating the size of the $n^{th}$ prime-prime and
for comparing it with the $n^{th}$ prime.
\begin{theorem}
\label{thm:bounds}
As $n\rightarrow\infty$:
\begin{eqnarray*}
q_n &amp;&lt;&amp; n (\log n + 2\loglog n)(\log n + \loglog n)- n \log n +O(n \loglog n),\\
q_n &amp;&gt;&amp; n (\log n + 2\loglog n)(\log n + \loglog n)-3n\log n
+O(n\log\log n).
\end{eqnarray*}
\end{theorem}

\begin{proof}
We use the inequalities of Rosser and Schoenfeld \cite{rosser}.
Namely
\begin{eqnarray*}
p_n &amp;&lt;&amp; n(\log n + \loglog n -1/2)\text{~valid for $n\ge 20$},\\
p_n &amp;&gt;&amp; n(\log n + \loglog n -3/2)\text{~valid for $n\ge 2$},
\end{eqnarray*}
by first substituting $p_n$ for $n$, then using both the upper and
lower bounds on each side, and finally simplifying.
\end{proof}

\begin{corollary}
The following inequalities are also satisfied by the $(q_n)$: as
$n\rightarrow\infty$:
\begin{eqnarray*}
&amp;(a)&amp;~q_n = n\log^2 n + 3 n\log n \loglog n + O(n\log n),\\
&amp;(b)&amp;~ q_n \sim n\log^2 n,\\
&amp;(c)&amp;~ \frac{q_n}{q_{n+1}}\rightarrow 1,\\
&amp;(d)&amp;~ q_n\sim\log n\cdot p_n,\\
&amp;(e)&amp;~ \text{for all $\e&gt;0$ there is an $n_\e\in\N$ such that for
all
$n\ge n_\e$, $q_n\le p_n^{1+\e}$},\\
&amp;(f)&amp;~ \text{for $n&gt;1$, $q_n&lt; p_n^\frac{3}{2}$},\\
&amp;(g)&amp;~ \text{For all $m,n\in\N$, $q_n\cdot q_m &gt; q_{m n}$},\\
&amp;(h)&amp;~ \text{For real $a&gt;1$ and $n$ sufficiently large, $q_{\lfloor
a n\rfloor}
&gt; a q_n$}.
\end{eqnarray*}
\end{corollary}
\begin{proof}
The inequalities (a)-(e) follow from Theorem \ref{thm:bounds}. Item
(f) follows by an explicit computation up to $n=2000$ and then by
contradiction, assuming $n(\log n+\loglog n-2)&lt;p_n&lt;n(\log n+ \loglog
n)$, for $n&gt;2000$. Item (g) follows from the corresponding theorem
of Ishikawa \cite{ishikawa} for primes and (h) from that of Giordano
\cite{giordano}.
\end{proof}


\section{The prime-prime number theorem and inequalities}

Here we obtain two forms for the asymptotic order of the counting
function of the prime-primes:
\begin{theorem}
\label{thm:counting}
 As $x\rightarrow\infty$,
$$
\pp(x) \sim \frac{x}{\log^2 x},\text{and}~~ \pp(x) = \Li(\Li(x)) +
O\big(x \exp(-A \log^\frac{3}{5} x \loglog^{-\frac{1}{5}} x)\big),
$$
for some absolute constant $A&gt;0$, where the implied ``big-O"
constant is also absolute.
\end{theorem}

\begin{proof}
The first asymptotic relation follows from a substitution: As
$x\rightarrow\infty$:
\begin{eqnarray*}
\pi(\pi(x)) &amp;=&amp; \frac{\pi(x)}{\log \pi (x)} + O\Big(\frac{\pi(x)}{\log^2\pi(x)}\Big)\\
&amp;=&amp; \frac{\frac{x}{\log x}+O(\frac{x}{\log^2
x})}{\log\Big(\frac{x}{\log x}+O(\frac{x}{\log^2 x}) \Big)}
+ O\Big(\frac{x\loglog x}{\log^4 x}\Big)\\
&amp;=&amp; \frac{x/\log x}{\log(x/\log x)+O(1/\log x)} + O\Big(\frac{x\loglog x}{\log^4 x}\Big),\\
&amp;=&amp; \frac{x}{\log^2 x[1+O(\frac{\loglog x}{\log x})]} +
O\Big(\frac{x\loglog x}{\log^4 x}\Big),\\
&amp;=&amp; \frac{x}{\log^2 x} + O\Big(\frac{x\loglog x}{\log^3 x}\Big).
\end{eqnarray*}

Now let $\Delta(x):= O\big(x \exp(-A \log^\frac{3}{5} x
\loglog^{-\frac{1}{5}} x)\big)$ and use the equation \cite{korobov,
vinogradov}
$$
\pi(x)=\Li(x)+\Delta(x).
$$
By the Mean Value Theorem there is a real number $\t$ with $|\t|&lt;1$
such that
\begin{eqnarray*}
\pi(\pi(x)) &amp;=&amp; \Li[\Li(x)+\Delta(x)] + \Delta(\pi(x)),\\
&amp;=&amp; \Li(\Li(x))+ \frac{\Delta(x)}{\log[\Li(x)+\t \Delta(x)]} +\Delta(x),\\
&amp;=&amp; \Li(\Li(x)) +\Delta(x).
\end{eqnarray*}
\end{proof}

\begin{proposition}
The following inequalities are true for every integer $k&gt;1$ and real
$x,y$ sufficiently large:
\begin{eqnarray*}
&amp;(a)&amp;~\pp(k x)&lt; k \pp(x),\\
&amp;(b)&amp;~\pp(x+y)\le \pp(x)+ 4 \pp(y),\\
&amp;(c)&amp;~\pp(x+y)-\pp(x) \ll \frac{y}{\log^2 y}.
\end{eqnarray*}
\end{proposition}
\begin{proof}
(a) We apply the theorem of Panaitopol \cite{pana}, namely that for
all $k&gt;1$ and $x$ sufficiently large $\pi(k x) &lt; k \pi(x)$ to derive
\begin{eqnarray*}
\pp(k x)= \pi(\pi(k x)) \le \pi(k \pi(x)) &lt; k\pi(\pi(x)) = k \pp(x).
\end{eqnarray*}

 (b) Now apply the inequality of Montgomery and Vaughan
\cite{mont} as well as the theorem of Panaitopol:
\begin{eqnarray*}
\pp(x+y) &amp;=&amp; \pi(\pi(x+y)) \le \pi(\pi(x)+2\pi(y))\\ &amp;\le&amp;
\pi(\pi(x))+2\pi(2\pi(y))&lt; \pp(x)+4 \pp(y).
\end{eqnarray*}
(c) This follows directly from (b) and Theorem \ref{thm:counting}.
\end{proof}
In part (c) compare the expression when $\pp$ is replaced by $\pi$
\cite[p.\ 34]{mont2}.

The following integral expression shows that, approximately, the
local density of the prime-primes is $dt/\log^2 t$:
\begin{proposition}
As $x\rightarrow\infty$
\begin{eqnarray*}
\Li(\Li(x)) &amp;=&amp; \int_2^x \big(\frac{1}{\log^2 t}+\frac{\loglog
t}{\log^3 t}\big) dt + O\big(\frac{x(\loglog x)^2}{\log^4 t}\big)\\
&amp;=&amp; \int_2^x \frac{dt}{\log^2 t}+O\big(\frac{x\loglog x}{\log^3
x}\big)
\end{eqnarray*}
\end{proposition}

\begin{proof}
Use the expression \cite[p.\ 86]{edwards}
$$
\Li(x)=
\frac{x}{\log(x)}+\frac{x}{\log^2(x)}+\cdots+\frac{(n-1)!x}{\log^n(x)}+O\big(\frac{x}{\log^{n+1}(x)}\big).
$$
in the case $n=1$, so
$$
\Li(x)=
\frac{x}{\log(x)}+O\big(\frac{x}{\log^2(x)}\big).
$$
Then let
\begin{eqnarray*}
F(x) &amp;:=&amp; \Li(\Li(x))\\&amp;=&amp;\int_2^y \frac{1}{\log t} dt, \text{~where}\\
y&amp;=&amp;\int_2^x \frac{1}{\log u} du.
\end{eqnarray*}
Then
\begin{eqnarray*} F'(x) &amp;=&amp;1/[\log x\log(\Li(x))]\\
&amp;=&amp; 1/[\log^2 x(1-\frac{\loglog x}{\log x}+O(\frac{1}{\log^2 x})]\\
&amp;=&amp; \frac{1}{\log^2 x}[1+\frac{\loglog x}{\log x}+O(\frac{(\loglog x)^2}{\log^2 x})\\
&amp;=&amp; \frac{1}{\log^2 x}+ \frac{\loglog x}{\log^3 x}+O(\frac{(\loglog
x)^2}{\log^4 x})
\end{eqnarray*}
so therefore
$$
F(x)= \int_2^x (\frac{1}{\log^2 t}+\frac{\log\log t}{\log^3 t})dt +
O(\frac{x(\log\log x)^2}{\log^4 x}).
$$
To derive the second expression, split the integral for the second
term in the integrand of the first expression at $\sqrt{x}$.
\end{proof}

\section{Extreme values of gaps between prime-primes}

Note that for $n&gt;1$ the number of primes between each pair of prime
primes is always odd, so $q_{n+1}-q_n\ge 6$. It is natural to
conjecture that this gap size of 6 is taken on an infinite number of
times, as is every even gap size larger than 6. 

Since for $n&gt;2$, $q_{n+1}\le 2q_n$ \cite{dressler}, we have
$q_{n+1}-q_n\le q_n^\t$ for $\t=1.0$. The same best current value
for primes, due to Baker, Harman and Pintz \cite{baker, baker2},
namely
$$
p_{n+1}-p_n \ll_\e p_n^{\t+\e},~~\t=0.525
$$
works for prime-primes. To see this replace $x$ by $\pi(x)$ in their
equation \cite[p.\ 562]{baker2} $$ \pi(x+x^{0.525})-\pi(x) \ge
\frac{9}{10}\frac{x^{0.525}}{\log x}
$$
to derive the formula, for every $\e&gt;0$ and $x$ sufficiently large
$$
\pp(x+x^{0.525+\e})-\pp(x) \ge \frac{9}{10}\frac{
x^{0.525-\e}}{\log^2 x}.
$$

The first proposition below is modeled directly on the corresponding
result for primes. The second is also closely related to the
derivation for primes, \cite[p.\ 155]{prachar}.
\begin{proposition}
For every integer $m&gt;1$ there exists an even number $\d$ such that
more than $m$ prime-primes are at distance $\d$.
\end{proposition}
\begin{proof}
Let $n\in\N$, $S:= \{q_1,\cdots,q_{n+1}\}$ be a finite initial
subset of the ordered sequence of prime-primes, and let $D:=
\{q_{j+1}-q_j: 1\le j\le n\}$ be the $n$ differences of consecutive
elements of $S$.


If $|D|\ge \lfloor \frac{n}{m}\rfloor$, then
\begin{eqnarray*}
q_{n+1}-q_1 &amp;=&amp; (q_2-q_1)+(q_3-q_2)+\cdots+ (q_{n+1}-q_n)\\
&amp;\ge&amp; 6 + 8 + \cdots + 2\lfloor \frac{n}{m}\rfloor\\
&amp;\ge&amp; \frac{n^2}{m^2}+ O(1).
\end{eqnarray*}
By Theorem \ref{thm:bounds}, we can choose $n$ sufficiently large so
$q_{n+1} &lt; 2 n \log^2 n$ and the inequality for $q_{n+1}-q_1$ is not
satisfied.

Therefore we can assume $n$ is sufficiently large so $|D|&lt; \lfloor
\frac{n}{m} \rfloor$. Then one of the differences must appear more
than $m$ times. Call the size of this difference $\d$.
\end{proof}

\begin{proposition}
$$
\liminf_{n\rightarrow\infty} \frac{q_{n+1}-q_n}{\log^2 q_n} \le 1.
$$
\end{proposition}
\begin{proof}
Let $\e&gt;0$ be given. Define two positive constants $\a,\b$ with
$$
\a=\frac{\b+1}{\b-1}
$$
with $\b&gt;3$ and so $1&lt;\a&lt;2$. Let $\e&gt;0$ be another positive constant
with $\e&lt; 1/\a-1/2$. Let $L:= 1+2\e$ and let
$$
\{q_m,\cdots,q_{m+k}\}
$$
be all of the prime-primes in the interval $[x,\b x]$. Now suppose
(to obtain a contradiction) that for all $n$ with $m\le n\le m+k-1$
we have
$$
q_{n+1}-q_n \ge L \log^2 q_n.
$$
Then
\begin{eqnarray*}
(\b-1)x &amp;\ge&amp; q_{m+k}-q_m\\
&amp;\ge&amp; L \sum_{n=m}^{m+k-1} \log^2 q_n\\
&amp;\ge&amp; L k \log^2 x.
\end{eqnarray*}

But by Theorem \ref{thm:counting}, for all $x$ sufficiently large
$$
(1-\frac{\e}{2})\frac{x}{\log^2 x} &lt; \pp(x) &lt;
(1+\frac{\e}{2})\frac{x}{\log^2 x}
$$
so
\begin{eqnarray*}
k &amp;\ge&amp; \pp(\b x)-\pp(x)-1\\
&amp;\ge&amp; \frac{(1-\frac{\e}{2})\b x}{\log^2 \b
x}-\frac{(1+\frac{\e}{2})x}{\log^2
x}-1\\
&amp;\ge&amp; \frac{x(\b-1-\e(\b+1))}{\log^2 x}\text{ for $x$ sufficiently
large}.
\end{eqnarray*}
Therefore $(\b-1) \ge L(\b-1-\e(\b+1))$, or in other words $1\ge
(1+2\e)(1-\a \e)$, which is impossible.

Therefore there exists an $n$ such that $q_n\in [x,\b x]$ and
$$
\frac{q_{n+1}-q_n}{\log^2 q_n}&lt; 1+2\e
$$
so $\liminf_{n\rightarrow\infty} (q_{n+1}-q_n)/\log^2 q_n \le 1$.
\end{proof}

Using a similar approach one can show that $
\limsup_{n\rightarrow\infty} \frac{q_{n+1}-q_n}{\log^2 q_n} \ge 1. $
It is expected however that the limit infinum of the ratio should be
zero and the limit supremum infinity. Fig.\ 1 is based on the
normalized nearest neighbor gaps for the first two million
prime-primes with a bin size of 0.025 and with the $x$-axis 160
corresponding to a normalized gap value of 4.0.

\begin{figure}[H]
\leftline{\includegraphics*[scale=0.75, bb=81 3 482
251]{pppgaps.eps}} \caption{Normalized gap frequencies.}
\end{figure}

\section{Prime-primes in arithmetic progressions}

Using the prime number graph technique of Pomerance
\cite{pomerance}, applied to the sequences $(n,q_n)$ and $(n,\log
q_n)$, we are able to demonstrate the existence of infinite subsets
of the $q_n$ such as the following:

\begin{proposition}
\ 
(a) There exists an
infinite set of $n\in\N$ with $2q_n \le q_{n-i}+q_{n+i}$ for all
$0&lt;i&lt;n$.

(b) There exists an infinite set of $n\in\N$ with $q_n^2 &gt; q_{n-i} q_{n+i}$ for all $0&lt; i &lt; n$.
\end{proposition}


Now we show that there are arithmetic progressions $(an+b:n\in\N)$
containing specified numbers of prime-primes, not necessarily
consecutive, satisfying $q_n=an+b$. Although modelled on the
technique of Pomerance, \cite[Theorem 4.1]{pomerance}, the key step
is introducing functions, named $f(u)$ and $g(u)$, but delaying
their explicit definitions until sufficient information becomes
available.
\begin{theorem}
\label{thm:progressions}
 For every integer $m&gt;1$ there exists an
arithmetic progression $(a n+b: n\in\N)$, with $a,b\in\N$, with at
least $m$ prime-primes satisfying $q_n=an+b$.
\end{theorem}

\begin{proof}
\ 

1. Definitions: Let $u&gt;0$ be a real variable and $f(u)&gt;0$ and $g(u)&gt;0$ two real decreasing functions both tending to zero as
$u\rightarrow\infty$, to be chosen later. Let $v=u+u\cdot f(u)$ so
\begin{eqnarray}
\log v &amp;=&amp; \log u (1+ O\big(\frac{f(u)}{\log u}\big)),\text{ and}\\
\log \Li(v) &amp;=&amp; \log \Li(u)(1+O\big(\frac{f(u)}{\log u}\big)).
\end{eqnarray}

Let $T$ be a parallelogram in the first quadrant of the $x$--$y$ plane
bounded by the lines $x=u$, $x=v$,
\begin{eqnarray*}
y&amp;=&amp; \Li(\Li(u)) + 2u g(u) + \frac{x-u}{k},\text{and}\\
y&amp;=&amp; \Li(\Li(u)) -2u g(u) + \frac{x-u}{k},
\end{eqnarray*}
where $k=\log\Li(u)\log u$.

Claim: If $|y-\Li(\Li(x))|&lt; u g(u)$ then $(x,y)\in T$. This is
demonstrated in 2.--4. below.

2. The upper bound: since $y&lt;\Li(\Li(x))+u g(u)$ we have, for some
$u&lt;\xi&lt;x$,
\begin{eqnarray*}
y &amp;&lt;&amp; \Li(\Li(u)) + \frac{x-u}{\log\Li(\xi)\log \xi} + 2u g(u),\\
&amp;\le&amp; \Li(\Li(u)) + \frac{x-u}{\log\Li(u)\log u} + 2u g(u).
\end{eqnarray*}

3. The lower bound: We have $\Li(\Li(x)) - u g(u) &lt; y$ and need
$\Li(\Li(u))+ \frac{x-u}{\log\Li(u)\log u} -2 u g(u) &lt; y$ so it is
sufficient to have
\begin{eqnarray*}
&amp;~&amp;\frac{x-u}{\log\Li(u)\log u}-\frac{x-u}{\log\Li(\xi)\log \xi} \le u g(u)\text{ or}\\
&amp;~&amp;\frac{v-u}{\log\Li(u)\log u}-\frac{v-u}{\log\Li(v)\log v} \le u g(u),\text{ which is equivalent to}\\
&amp;~&amp; f(u)[\frac{1}{\log\Li(u)\log u}-\frac{1}{\log\Li(v)\log v}] \le g(u),\text{ or by (1) and (2)}\\
&amp;~&amp; \frac{f(u)}{\log\Li(u)\log u}[1- \frac{1}{1+O(f(u)/\log u)}] =
O\big(\frac{f(u)^2}{\log^3 u}\big)\le M \cdot\frac{f(u)^2}{\log^3
u})\le g(u)~~(3)
\end{eqnarray*}
for some $M&gt;0$.

 4. Counting points and lines: by  2.\ and 3.\ each
point $(q_n,n)$ with $u\le q_n\le v$ is in $T$, so the number of
such points is, by Theorem \ref{thm:counting}, bounded below by the
numerator in the expression below. The number of lines with slope
$1/k$ passing through the integer lattice points of $T$ is bounded
above by the denominator of this expression. Therefore for $u$
sufficiently large:
\begin{eqnarray*}
\frac{\# \text{points}}{\# \text{ lines}} &amp;\ge&amp; \frac{\frac{u f(u)}{2}\cdot\frac{1}{\log^2 u}}{(\log\Li(u)\log u)4u g(u)}\\
 &amp;\ge&amp; \frac{f(u)/8}{(\log u)^4 g(u)}~~~~(4)
\end{eqnarray*}

Now let $f(u):= \frac{1}{\log^\a u}$ and $g(u):= \frac{1}{\log^\b
u}$ where $\a,\b&gt;0$ are chosen so that
$$
\a+4&lt; \b &lt; 2\a+3.
$$
For example $\a=2,~\b=6.5$. Then in (4)
$$
\frac{f(u)}{(\log u)^4 g(u)}=\log^{\b-\a-4} u \rightarrow\infty
$$
and in (3)
$$
\frac{f(u)^2}{(\log u)^3 g(u)}=\log^{\b-2\a-3} u \rightarrow 0+,
$$
so choose $u$ sufficiently large that $f(u)^2/(\log^3 u g(u)) \le
1/M$, thus ensuring the validity of the lower bound.

With these choices, the number of points divided by the number of
lines tends to positive infinity, so for every natural number $m$
there is at least one line on the graph of $(q_n,n)$ with $m$ of
these points. Finally we note that since $k$ varies continuously
with $u$, we can choose $k\in\N$ and so $q_n=an+b$ with $a,b\in\N$
since $a=k$.
\end{proof}

\section{Epilog}
Leading on from Section 5, a natural aim is to show that there are
an infinite number of prime-primes congruent, say, to 1 modulo 4, or
some other explicit arithmetic progression. Then show that every
arithmetic progression $(an+b:n\in\N)$, with $(a,b)=1$, contains an
infinite number of prime-primes. This has been demonstrated
numerically, with the number of prime-primes falling approximately
evenly between the equivalence classes modulo $a$.


This problem appears to have considerable more depth than the
results given here. For example it is, on the face of it, more
difficult than the corresponding theorem of Dirichlet for primes,
because the primes in residue classes given by that theorem do not
appear in any particular order.


\section{Acknowledgements}
We acknowledge the assistance given by a helpful referee, especially
in making us aware of the result in the paper of Baker, Harman and
Pintz. The figure was produced using Mathematica.

\begin{thebibliography}{10}

\bibitem{baker}
R. C. Baker and G. Harman, {\rm The difference between consecutive
primes}, {\it Proc. London Math. Soc.} (3) {\bf 72} (1996),
261--280.

\bibitem{baker2}
R. C. Baker, G. Harman and J. Pintz, {\rm The difference between
consecutive primes, II}, {\it Proc. Lond. Math. Soc.} (3) {\bf 83}
(2001), 532--562.

\bibitem{broughan}
K. A. Broughan and Q. Zhou, {\rm Flat primes and thin primes},
(preprint).

\bibitem{dressler}
R. E. Dressler and S. T. Parker, {\rm Primes with a prime
subscript}, {\it J. ACM} {\bf 22} (1975), 380--381.

\bibitem{edwards}
H. M. Edwards,{\it Riemann's Zeta Function}, Dover, 2001.

\bibitem{giordano}
G. Giordano, {\rm The existence of primes in small intervals}, {\it
Indian J. Math.} {\bf 31} (1989), 105--110.

\bibitem{ishikawa}
H. Ishikawa, {\rm \"Uber die Verteilung der Primzahlen}, {\it Sci.
Rep. Tokyo Univ. Lit. Sci. Sect. A} {\bf 2} (1934), 27--40.

\bibitem{korobov}
N. M. Korobov, {\rm Estimates of trigonometric sums and their
applications} {\it Uspehi Mat. Nauk} {\bf 13} (1958), 185--192.

\bibitem{mont}
H. L. Montgomery and R. C. Vaughan, {\rm The large sieve}, {\it
Mathematika} {\bf 20} (1973), 119--134.

\bibitem{mont2}
H. L. Montgomery, {\rm Topics in Multiplicative Number Theory}, {\it
Springer Lecture Notes in Mathematics}, Vol. 227, Springer-Verlag,
1971.

\bibitem{pana}
L. Panaitopol,  {\rm Eine Eigenschaft der Funktion \"uber die
Verteilung der Primzahlen}, {\it Bull. Math. Soc. Sci. Math. R. S.
Roumanie},  {\bf 23} (1979), 189--194.

\bibitem{pomerance}
C. Pomerance, {\rm The prime number graph}, {\it Math. Comp.} {\bf
33} (1979), 399--408.

\bibitem{prachar}
K. Prachar, {\it Primzahlverteilung}, Springer-Verlag, 1957.

\bibitem{rosser}
J. B. Rosser and L. Schoenfeld, {\rm Approximate formulas for some
functions of prime numbers}, {\it Illinois J. Math.} {\bf 6} (1962),
64--94.

\bibitem{vinogradov}
I. M. Vinogradov, {\rm A new estimate of the function
$\zeta(1+it)$.} {\it Izv. Akad. Nauk SSSR. Ser. Mat.} {\bf 22}
(1958), 161--164.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A41; Secondary 11B05, 11B25, 11B83.

\noindent \emph{Keywords: } prime-prime,
prime-prime number theorem, prime-prime gaps,
prime-primes in progressions.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A006450}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 5 2008;
revised version received January 14 2009. 
Published in {\it Journal of Integer Sequences}, January 17 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>