<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}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 0.7cm{\LARGE\bf 
Maximal Gaps Between Prime $k$-Tuples: \\
\vskip .1in
A Statistical Approach
}
\vskip 0.7cm
\large
Alexei Kourbatov\\
JavaScripter.net/math\\
15127 NE 24th St., \#578\\
Redmond, WA 98052 \\
USA\\
\href{mailto:akourbatov@gmail.com}{\tt akourbatov@gmail.com}
\end{center}

\vskip .2 in

\begin{abstract}
Combining the Hardy-Littlewood $k$-tuple conjecture with a heuristic application of extreme-value statistics,
we propose a family of estimator formulas for predicting maximal gaps between prime $k$-tuples.
Extensive computations show that the estimator $a\log(x/a)-ba$ satisfactorily predicts the maximal gaps below $x$,
in most cases within an error of $\pm2a$, where $a=C_k\log^kx$ is the expected average gap between the same type of $k$-tuples.
Heuristics suggest that maximal gaps between prime $k$-tuples near $x$
are asymptotically equal to $a\log(x/a)$, and thus have the order $O(\log^{k+1}x)$.
The distribution of maximal gaps around the ``trend'' curve $a\log(x/a)$ is close to the Gumbel distribution.
We explore two implications of this model of gaps: record gaps between primes and
Legendre-type conjectures for prime $k$-tuples. 
\end{abstract}

\section{Introduction}
Gaps between consecutive primes have been extensively studied.
The prime number theorem \cite[p.\,10]{hw}
suggests that ``typical'' prime gaps near $p$ have the size about $\log p$. 
On the other hand, maximal prime gaps grow no faster than $O(p^{0.525})$ \cite[p.\,13]{hw}.
Cram\'er \cite{cram} conjectured that gaps between consecutive
primes $p_{n}-p_{n-1}$ are at most about as large as $\log^2p$, that is,
$\lim \sup (p_{n}-p_{n-1})/\log^2p_n = 1$ when $p_n \to \infty$. 
%
Moreover, Shanks~\cite{shanks} stated that maximal prime gaps $G(p)$ 
satisfy the asymptotic equality $\sqrt{G(p)}\sim\log p$. 
All maximal gaps between primes are now known, 
up to low 19-digit primes (OEIS \seqnum{A005250}) \cite{nicely,oeis}. 
This data apparently supports the Cram\'er and Shanks conjectures\footnote{While 
the Shanks conjecture $\sqrt{G(p)}\sim\log p$ is plausible, 
the ``inverted'' Shanks conjecture $p\sim e^{\sqrt{G(p)}}$ is likely false. 
(In general, $X\sim Y \not\Rightarrow e^X\sim e^Y$; for example, $x+\log x\sim x$, 
but $e^{x+\log x}\mspace{-4mu}= xe^x \not\sim e^x$ as $x\to\infty$.)
Wolf \cite[p.\,21]{wolf} proposes an improvement: a gap $G(p)$ is likely to first appear near $p\sim\sqrt{G(p)}e^{\sqrt{G(p)}}$.
}: 
thus far, if we divide by $\log^2p$ the maximal gap ending at $p$,  
the resulting ratio is always less than one~--- but tends to grow 
closer to one, albeit very slowly and irregularly.


Less is known about maximal gaps between prime constellations, or prime $k$-tuples. 
One can conjecture that average gaps between prime $k$-tuples near $p$ 
are $O(\log^{k}p)$ as $p \to \infty$, in agreement with the Hardy-Littlewood $k$-tuple conjecture \cite{hl}.  
%
Kelly and Pilling \cite{kpII}, %(2001), 
Fischer~\cite{fischer} %(2006), 
and Wolf \cite{wolf2} %(2013) 
report heuristics and computations for gaps between {\em twin primes} ($k=2$).
%
Kelly and Pilling \cite{kpIII} also provide physically-inspired heuristics for prime triplets ($k=3$);
Fischer \cite{fischer2} conjectures formulas for maximal gaps between $k$-tuples for both $k=2$ and $k=3$.
%
All of these conjectures and heuristics, as well as extensive computations, suggest that 
maximal gaps between prime $k$-tuples are at most about $\log p$ times the average gap, 
which implies that maximal gaps are $O(\log^{k+1}p)$ as $p \to \infty$. 

In this article we use {\em extreme value statistics} to derive a general formula 
predicting the size of record gaps between $k$-tuples below $p$: 
maximal gaps are approximately %$\max(a, a\log(p/a) - ba)$, 
%
$a\log(p/a) - ba$, with probable error $O(a)$.
%
Here $a = C_k\log^kp$ is the {\em expected average gap} near $p$, and 
$C_k$ and $b$ are parameters depending on the type of $k$-tuple. %; $C_k&lt;1$ and $|b|&lt;1.5$ for $k\ge2$.
This formula approximates maximal gaps 
better and in a wider range than a linear function of $\log^{k+1}p$. 
%
We will mainly focus on three types of prime $k$-tuples:
\begin{itemize}
\item $k=2$: twin primes (maximal gaps are OEIS \seqnum{A113274});
\item $k=4$: prime quadruplets (maximal gaps are OEIS \seqnum{A113404});
\item $k=6$: prime sextuplets (maximal gaps are OEIS \seqnum{A200503}).
\end{itemize}
The observations can be readily applied to other $k$-tuples; 
however, numerical values of constants $C_k$ will change depending on the specific type of $k$-tuple. 
See, e.\,g., the following OEIS sequences for data on maximal gaps between prime $k$-tuples for other $k$: 
\begin{itemize}
\item $k=3$: prime triplets (maximal gaps are \seqnum{A201596} and \seqnum{A201598});
\item $k=5$: prime quintuplets (maximal gaps are \seqnum{A201073} and \seqnum{A201062});
\item $k=7$: prime septuplets (maximal gaps are \seqnum{A201051} and \seqnum{A201251});
\item $k=10$: prime decuplets (maximal gaps are \seqnum{A202281} and \seqnum{A202361}). 
\end{itemize}



\section{Definitions, notations, examples}

\noindent
{\em Twin primes} are pairs of consecutive primes that have the form $\{p$, $p+2\}$. 
(This is the densest repeatable pattern of two primes.)
%
{\em Prime quadruplets} are clusters of four consecutive primes of the form $\{p$, $p+2$, $p+6$, $p+8\}$ 
(densest repeatable pattern of four primes).
%
{\em Prime sextuplets} are clusters of six consecutive primes of the form $\{p$, $p+4$, $p+6$, $p+10$, $p+12$, $p+16\}$ 
(densest repeatable pattern of six primes).

{\em Prime $k$-tuples} are clusters of $k$ consecutive primes that have a repeatable pattern. 
Thus, twin primes are a specific type of prime $k$-tuples, with $k = 2$; 
prime quadruplets are another specific type of prime $k$-tuples, with $k = 4$; 
and prime sextuplets are yet another type of prime $k$-tuples, with $k = 6$. 
(The densest $k$-tuples possible for a given $k$ may also be called 
{\em prime constellations} or {\em prime $k$-tuplets}.)

{\em Gaps} between prime $k$-tuples are distances between the initial primes in two consecutive $k$-tuples of the same type. 
If the prime at the end of the gap is $p$, we denote the gap $g_k(p)$. 
For example, the gap between the quadruplets $\{11,13,17,19\}$ and $\{101,103,107,109\}$ is $g_4(101) = 90$. 
The gap between the twin primes $\{17,19\}$ and $\{29,31\}$ is $g_2(29) = 12$.
Hereafter $p$ always denotes a prime. 
In the context of gaps between prime $k$-tuples, $p$ will refer to 
the first prime of the $k$-tuple at the end of the gap; we call $p$ the {\em end-of-gap} prime.
(Note that primes {\em preceding} the gap might be {\em orders of magnitude smaller} than the gap size itself;
e.\,g., the gap $g_6(16057)=15960$  starts at $\{97,101,103,107,109,113\}$;
the gap $g_6(1091257)=1047480$ starts at $\{43777,43781,43783,43787,43789,43793\}$.)

A {\em maximal gap} is a gap that is strictly greater than all preceding gaps. 
In other words, a maximal gap is the first occurrence of a gap at least this size. 
As an example, consider gaps between prime quadruplets (4-tuples): 
the gap of 90 preceding the quadruplet $\{101,103,107,109\}$ is a maximal gap 
(i.e. the first occurrence of a gap of at least 90), while 
the gap of 90 preceding $\{191,193,197,199\}$ is not a maximal gap 
(not the first occurrence of a gap at least this size). 
A synonym for {\em maximal gap} is {\em record gap}. 
By $G_k(x)$ we will denote the largest gap between $k$-tuples below $x$. 
({\em Note:} Statements like this will always refer to a {\em specific type of $k$-tuples}.)
We readily see that
\begin{eqnarray*}
g_k(p) &amp;\le&amp; G_k(p) \quad\mbox{ wherever $g_k(p)$ is defined, and} \\
g_k(p) &amp;=&amp; G_k(p) \quad\mbox{ if $g_k(p)$ is a maximal gap.}
\end{eqnarray*}
In rare cases, the equality $g_k(p)=G_k(p)$ may also hold for non-maximal gaps $g_k(p)$;
e.\,g., $g_4(191)=G_4(191)=90$ even though the gap $g_4(191)$ is not maximal.

The {\it average gap} between $k$-tuples near $x$ 
is denoted $\overline{g_k(x)}$ and defined here as
$$
\overline{g_k(x)}
=
\frac{\displaystyle\sum_{{1\over2}x \,\le\, p-g_k(p) \,&lt;\, p \,\le\, {3\over2}x}\mspace{-48mu}g_k(p)\hphantom{x}}
     {\mspace{-32mu}\displaystyle\sum_{{1\over2}x \,\le\, p-g_k(p) \,&lt;\, p \,\le\, {3\over2}x}\mspace{-48mu}1}   
= 
\frac{\mbox{the sum of all gaps between $k$-tuples with }p\in[{1\over2}x,{3\over2}x]}
     {\mbox{total count of gaps between $k$-tuples with }p\in[{1\over2}x,{3\over2}x]}
\,.
$$
(The value of $\overline{g_k(x)}$ is undefined if there are less than two $k$-tuples with ${1\over2}x \le p \le {3\over2}x$.)  

The {\it expected average gap} between $k$-tuples near $x$ (for any $x\ge3$) 
is defined formally as $a = a(x) = C_k \log^k x$, 
where the positive coefficient $C_k$ is determined by the type of the $k$-tuples.
(See the {\em Conjectures} section for further details on this.)



\section{Motivation: is a simple linear fit for $G_k(p)$ adequate?}

The first ten or so terms in sequences of record gaps 
(e.\,g., \seqnum{A113274}, \seqnum{A113404}, \seqnum{A200503}) 
seem to indicate that maximal gaps between $k$-tuples below $p$ grow about as fast as a linear function of $\log^{k+1}p$.
For {\em twin primes} ($k=2$), Rodriguez and Rivera \cite{rr} gave simple linear approximations of record gaps,
while Fischer \cite{fischer2} and Wolf \cite{wolf2} proposed more sophisticated non-linear formulas. 
%
Why bother with any non-linearity at all?
%
Let us look at the data. 
Table~1 presents the least-squares zero-intercept trendlines \cite{hays,exceltrendline} 
for record gaps between $k$-tuples below $10^{15}$ ($k=2$, 4, 6).


\begin{center}TABLE 1 \\Least-squares zero-intercept trendlines for maximal gaps between prime $k$-tuples \\[0.5em]
\begin{tabular}{cccc}
\hline
    &amp;\multicolumn{3}{c}{\phantom{\fbox{$1^1$}}Trendline equation for maximal gaps between prime $k$-tuples:}    \\
\multicolumn{1}{l}
{End-of-gap prime $p$}&amp;{twin primes}            &amp;{prime quadruplets}      &amp;{prime sextuplets}       \\
                      &amp;{($k=2$; $\xi=\log^3p$)} &amp;{($k=4$; $\xi=\log^5p$)} &amp;{($k=6$; $\xi=\log^7p$)} \\
[0.5ex]\hline
\vphantom{\fbox{$1^1$}}
$1 &lt; p &lt; 10^6$     &amp; $y=0.4576\xi$ &amp;  $y=0.0627\xi$ &amp; $y=0.0016\xi$  \\
$10^6&lt;p&lt; 10^9$     &amp; $y=0.4756\xi$ &amp;  $y=0.1031\xi$ &amp; $y=0.0147\xi$  \\
$10^9&lt;p&lt;10^{12}$   &amp; $y=0.5203\xi$ &amp;  $y=0.1245\xi$ &amp; $y=0.0181\xi$  \\
$10^{12}&lt;p&lt;10^{15}$&amp; $y=0.5628\xi$ &amp;  $y=0.1451\xi$ &amp; $y=0.0249\xi$  \\
\hline
\end{tabular}
\end{center}
%
Table 1 shows that, for a fixed $k$, record gaps between $k$-tuples farther from zero have a {\em steeper} trendline
(when plotted against $\log^{k+1}p$). This is not a ``one-slope-fits-all'' situation!
%
There is a good reason to expect that the same tendency holds in general for any $k$:
As we will see in the next sections, there exist {\em curves} that predict the record gap sizes, 
on average, better than any linear function of $\log^{k+1} p$~--- 
and the farther from zero, the steeper are these curves (approaching certain limit values of slope, $C_k$).
Nevertheless, a linear approximation can also be useful; computations and heuristics suggest that
a linear function of $\log^{k+1}p$ can serve as a convenient {\em upper bound} for gaps. 
For example:
{\em Maximal gaps between twin primes are less than} $0.76\log^3 p$.
In what follows, we will combine the Hardy-Littlewood $k$-tuple conjecture with extreme value statistics 
to better predict the sizes of maximal gaps between prime $k$-tuples of any given type,
accounting for their non-linear growth trend. 


\section{Conjectures}

In this section we state several conjectures based on plausible heuristics 
and supported by extensive computations.
As far as rigorous proofs are concerned, we do not even know 
whether there are infinitely many $k$-tuples of a given type~--- 
e.\,g., whether there are infinitely many twin primes for $k$ = 2. 
(The famous {\it twin prime conjecture} thus far remains unproven. 
{\it A fortiori} there is no known proof of the more general $k$-tuple conjecture described below.) 

\subsection{The Hardy-Littlewood $k$-tuple conjecture}

The Hardy-Littlewood $k$-tuple conjecture \cite{hl}
predicts the approximate total counts of prime $k$-tuples (with a given admissible\footnote{Any 
pattern of $k$ primes is deemed admissible (repeatable) 
unless it is prohibited by divisibility considerations.
For instance, the pattern of $\{p$, $p+2$, $p+4\}$ is prohibited: 
one of the numbers $p$, $p+2$, $p+4$ must be divisible by 3. 
But $\{p$, $p+2$, $p+6\}$ is not prohibited, hence admissible. 
Riesel \cite[pp.\,60--68]{riesel} has a more detailed discussion of the $k$-tuple conjecture and admissible patterns.  
}
pattern):
$$
\mbox{The total number of prime $k$-tuples below $x$} ~\sim~ H_k \int_2^x {dt \over \log^k t}.
$$
%
The actual counts of $k$-tuples match this prediction with a surprising accuracy \cite[p.\,62]{riesel}.
The coefficients $H_k$ are called the Hardy-Littlewood constants.
Note that, in general, the constants $H_k$ depend on $k$ {\it and} on the specific type of $k$-tuple
(e.\,g., there are three types of prime octuplets, with two different constants).
%
Hardy and Littlewood not only conjectured the above integral formula
but also provided a recipe for computing the constants $H_k$ as products over subsets of primes.
For example, in special cases with $k=2,4,6$ we have
%
\begin{eqnarray*}
H_2 &amp;=&amp; 2 \prod_{p\ge3} {{p(p-2)}\over{(p-1)^2}} ~\approx~ 1.32032  \qquad
\mbox{ (for twin primes),} \\
%
H_4 &amp;=&amp; {27\over2} \prod_{p\ge5} {{p^3(p-4)}\over{(p-1)^4}} ~\approx~ 4.15118 \qquad 
\mbox{ (for prime quadruplets),} \\
%
%H_6 &amp;=&amp; {759375\over8192} \prod_{p\ge7} {{p^5(p-6)}\over{(p-1)^6}} ~\approx~ 17.2986 \qquad 
H_6 &amp;=&amp; {15^5\over2^{13}} \prod_{p\ge7} {{p^5(p-6)}\over{(p-1)^6}} ~\approx~ 17.2986 \qquad 
\mbox{ (for prime sextuplets)}. 
\end{eqnarray*}
%
These formulas for $H_k$ have slow convergence. 
Riesel \cite{riesel} and Cohen \cite{cohen} describe efficient methods for
computing $H_k$ with a high precision. Forbes \cite{forbes} provides 
the values of $H_k$ for dense $k$-tuples, or {\it $k$-tuplets}, up to $k=24$.
The $k$-tuple conjecture implies that
\begin{itemize}
\item The sequence of maximal gaps between prime $k$-tuples of any given type is infinite.
      (Thus, all OEIS sequences mentioned in {\em Introduction} are infinite.)
%
\item When $x\to\infty$, the largest gaps below $x$ will grow (asymptotically) at least as fast as average gaps, i.\,e., 
      as fast as $O(\log^{k}x)$ or {\it faster}.
\end{itemize}
But exactly how much faster? Conjectures (D) and (E) below give plausible answers.



\subsection{Conjectured asymptotics for gaps between $k$-tuples}

Let $C_k$ denote the reciprocal to the corresponding Hardy-Littlewood constant: $C_k=H_k^{-1}$.
The following formulas provide rough estimates of the gap $g_k(p)$ ending at a prime $p$: 

\smallskip\noindent
(A) {\it Average} gaps between prime $k$-tuples near $p$ are 
$
\overline{g_k(p)} \sim C_k\log^k p.
$

\smallskip\noindent
(B) {\it Maximal} gaps between prime $k$-tuples are $O(\log^{k+1} p)$: 
$$
g_k(p) &lt; M_k \log^{k+1} p, \quad \mbox{ where } M_k \approx C_k \quad \mbox{ (and possibly } M_k=C_k).
$$
%To describe the asymptotic behavior of maximal gaps, we 
Defining the {\it expected average gap} near $x$ to be
$a = C_k \log^{k} x$~ ($x\ge3$), we further conjecture:

\noindent
(C) {\it Maximal} gaps below $x$ are asymptotically equal to $C_k \log^{k+1} x$:
$$G_k(x) \sim C_k \log^{k+1}x \quad \mbox{ as } x \to \infty, \quad \mbox{with probable error } O(a\log a).
$$

\noindent
(D) {\it Maximal} gaps below $x$ are more accurately described by this asymptotic equality: 
$$
G_k(x) ~\sim~ a\log(x/a) \quad \mbox{ as } x \to \infty, 
\qquad \mbox{ with probable error } O(a).
$$

\noindent
(E) For any given type of $k$-tuple, there exists a real $b$ (e.\,g., $b\approx{2\over k}$) %($|b|&lt;4$) 
such that the difference $G_k(x) - a(\log(x/a)-b)$ changes its sign infinitely often\footnote{ 
Moreover, on finite intervals $x\in[3,X_{\mbox{\tiny max}}]$ the difference $G_k(x) - a(\log(x/a)-b)$ 
changes its sign more often than $G_k(x) - L(\log^{k+1}\negthinspace x)$, 
where $L(\log^{k+1}\negthinspace x)$ is any linear function of $\log^{k+1}\negthinspace x$ 
and $X_{\mbox{\tiny max}}$ is large enough.
} 
as $x\to\infty$.

\smallskip
A key ingredient in these conjectures is provided by the constants $C_k = {H_k}^{-1}$: %In particular, for $k=2,4,6$ we have
$$
C_2 = H_2^{-1} \approx 0.75739,  \qquad
C_4 = H_4^{-1} \approx 0.240895, \qquad
C_6 = H_6^{-1} \approx 0.057808.
$$
%
Another key ingredient is a statistical formula: for certain kinds of random events occurring
%
%at mean intervals $a$, an approximate record interval\footnote{...}
%between events is $a\log(T/a)$, where $T$ is the total observation time.
% 
at mean intervals $a$, the record interval between events observed in time $T$ is likely\footnote{
%
In particular, if intervals between rare random events have the exponential distribution, with mean interval $a$ sec
and CDF $1-e^{-t/a}$, then the {\bf\em most probable record interval} 
observed within $T$ sec is about $a\log(T/a)$ sec (provided that $a\ll T$).
After many observations ending at times $a \ll T_1 \ll T_2 \ll T_3\ldots$ 
almost surely for some $T_i$ we will observe record intervals {\bf\em exceeding} $a\log(T_i/a)$.
However, for other values of $T_i$ we will also observe record intervals {\bf\em below} $a\log(T_i/a)$.
%
It is this formula for the most probable extreme, with the aid of the estimate SD\,$=O(a)$ 
for the standard deviation of extremes, that allows us to heuristically predict the bounds, errors, asymptotics, 
and sign changes in conjectures (B), (C), (D), (E).
}
near $a\log(T/a)$.
In {\em Appendix} we derive this formula for $a=\mbox{const}$. 
Here, we heuristically apply this formula for a slowly changing $a$ (i.\,e., $a = C_k \log^{k} x$).
%
For now, we can informally summarize the behavior of maximal gaps between $k$-tuples near $p$ as follows:
Maximal gaps are {\bf{\em at most}} about $\log p$ times the average gap. 


\subsection{Estimators for maximal gaps between $k$-tuples}

Prime $k$-tuples are rare and seemingly ``random''. 
Life offers many examples of unusually large intervals between rare random events, 
such as the longest runs of dice rolls without getting a twelve; 
maximal intervals between clicks of a Geiger counter measuring very low radioactivity, etc. 
%
Reasoning as in {\em Appendix}, one can statistically estimate the mathematical expectation of maximal intervals 
between rare random events by expressing them in terms of the average intervals: 
$$
\mbox{Expected maximal intervals} ~=~ a \log (T/a) + O(a), \eqno{(*)}
$$
where $a$ is the average interval between the rare events, and 
$T$ is the total observation time or length ($1 \ll a \ll T$). 

To account for the observed non-linear growth of record gaps  between prime $k$-tuples (Table 1), 
we will simulate gap sizes using estimator formulas very similar to the above $(*)$.
%
We define a family of estimators for the maximal gap that ends at $p$:
%
\begin{eqnarray}
E_1(G_k(p)) &amp;=&amp; \max(a,\, a\log(p/a) - ba),      \qquad    \mbox{ probable error: $O(a);$ }\\
E_2(G_k(p)) &amp;=&amp; \max(a,\, a\log(p/a)),    \qquad\qquad\,   \mbox{ probable error: $O(a);$ }\\
E_3(G_k(p)) &amp;=&amp; a\log p ~=~ C_k \log^{k+1} p, \qquad\quad  \mbox{ probable error: $O(a\log a).$ }
\end{eqnarray}
%
Here, the role of the statistically average interval $a$ is played by the expected average gap between $k$-tuples: 
as before, we set $a = C_k \log^k p$. 
The role of the total observation time $T$ is played by $p$ (we are ``observing'' gaps that occur from 0 to $p$).
We also empirically choose $b={2\over k}$.
(The latter choice is not set in stone; by varying the parameter $b$ in $E_1$ one can get 
an infinite family of useful estimators
with similar asymptotics. In Section 6 we will see that $b\approx3$ appears
quite suitable for modeling {\em prime gaps}, in which case $k=1$, $a=\log p$, and $C_1=1$.) 
It is easy to see that, for any fixed $k\ge1$ %, any $p\ge3$, 
and any fixed $b\ge0$, we have
$$
a \le E_1 \le E_2 &lt; E_3 \mbox{ ~for all } p\ge3, \quad \mbox{ but at the same time } \quad 
a \ll E_1 \sim E_2 \sim E_3 \mbox{ ~as } p \to \infty.
$$
%
Indeed, when $p \to \infty$ we have
$$
E_1(G_k(p)) = a \log(p/a)-ab = a\log p-a(\log a + b) = a\log p- o(\log^{k+1}p) \sim E_3(G_k(p)).
$$
% 
{\em Note:} We use the max function in the estimators to guarantee that $E_i(G_k(p)) \ge a$.
This precaution is needed because, if $p$ is not large enough, $\log(p/a)$ might be negative or too small.
We want our estimators to give positive predictions no less than $a$ even in such cases.

The above conjectures (C), (D), (E) tell us that $E_1$ and $E_2$ are better estimators than $E_3$:
the probable error of $E_3$ is greater than that of $E_1$ or $E_2$. 
In Section 5.1 we will compare the predictions obtained with these estimators 
to the actual sizes of maximal gaps. %between prime $k$-tuples.


%\subsection{The perils of probabilistic models and the blessings of extreme value statistics}
\subsection{Why extreme value statistics?}

In number theory, probabilistic models such as Cram\'er's model \cite{cram} face serious difficulties.
One such difficulty will be noted in Section 6.
%(Cram\'er's model may incorrectly estimate local average gaps between primes.) 
Pintz \cite{cvc} points out additional problems with Cram\'er's model.
Number-theoretic objects (such as primes or prime $k$-tuples) are too peculiar; 
they are clearly {\em not} independent and cannot be flawlessly simulated by 
independent and identically distributed (i.i.d.)~random variables 
or ``events'' or ``coin tosses'' that we usually deal with in probabilistic models.
%
Why then should one build heuristics for prime $k$-tuples based on extreme value statistics?

An obvious reason is that we are studying {\em extreme} gaps, so it would be unwise 
to outright dismiss the existing extreme value theory without giving it a try.
%
%Sometimes valid formulas may be derived even from oversimplified assumptions. 
%
When our goal is just to guess the right formula, rigor is not the highest priority; 
it is perhaps more important to accumulate as much evidence as possible,
look for counterexamples, and make reasonable simplifications. 
The above formula for the expected maximal interval $(*)$ appears to be at the right level of simplification
and fits the actual record gaps fairly well even without the $O(a)$ term (as we will see in Section 5.1).
To fine-tune formula $(*)$ for record gaps between prime $k$-tuples, we simply have to find a suitable $O(a)$ term. 
The latter can be done using number-theoretic insights and/or numerical evidence.

Extreme value theory also offers additional benefits.
% it can make quite a few {\em testable predictions} that would be difficult to make otherwise. 
Not only does it tell us the mathematical expectation of extremes in random sequences~--- 
it also predicts {\it distributions} of extremes.
While in general there are infinitely many probability distribution laws,
there exist {\em only three types of limiting extreme value distributions}
applicable to sequences of i.i.d.~random variables: 
the Gumbel, Fr\'echet, and Weibull distributions \cite{bgt}.
%
%The celebrated Fisher-Tippet-Gnedenko theorem \cite{ft},\,\cite{gnedenko} 
%rules out all types of non-degenerate limiting extreme value distributions other than the above three.
%
When no limiting extreme value distribution exists, a known type of 
extreme value distribution may still be a good approximation 
\cite{gsw,schilling}.
%
A large body of knowledge has been accumulated that extends the same types of extreme value 
distributions from i.i.d.~random variables to certain kinds of dependent variables, for example, 
$m$-dependent random variables \cite{watson},
exchangeable variables \cite{berman},\,\cite[pp.\,163--191]{galambos}, 
and other situations \cite{bgt,galambos}.
%
Although no theorem currently extends the known types of extreme value distributions 
to record gaps between primes or prime $k$-tuples, 
we might have an aesthetic expectation %\footnote{ In Littlewood's terminology, a {\em hunch}. \cite[p.\,191]{lwmisc}}
that ``the usual suspects'' would show up here, too.
It turns out that one common type of extreme value distribution~--- the Gumbel distribution~--- does show up! 
(See Section 5.2, {\em The distribution of maximal gaps}.)

\section{Numerical results}

Using a fast deterministic algorithm based on strong pseudoprime tests \cite[pp.~91--92]{riesel}, 
the~author computed all maximal gaps between prime $k$-tuplets up to $10^{15}$ for $k=4$,~6. 
Fischer (2008) \cite{fischer} reported a similar computation for $k=2$. Below we analyze this data.

%Let us look at the actual sequences of record gaps obtained from lengthy computations, 
%and compare them to gap sizes predicted by the heuristic estimators $E_1$, $E_2$, $E_3$ defined above.


\subsection{The growth of maximal gaps}

Figure 1 shows record gaps between twin primes (\seqnum{A113274}) for $p&lt;10^{15}$;
the curves are predictions obtained with estimators $E_1$, $E_2$, $E_3$ defined above.
%
Figure 2 shows similar data for prime quadruplets (\seqnum{A113404}),
%
and Figure 3 for prime sextuplets (\seqnum{A200503}).
Tables 2--4 give the relevant numerical data; see also OEIS sequences mentioned in {\em Introduction}.


Here are some observations suggested by these numerical results. 
(As before, $a$ denotes the expected average gap, $a=C_k \log^k p$, and $b={2\over k}$ unless stated otherwise.)

\begin{enumerate}
%
\item Estimators $E_1$ and $E_2$ overestimate some of the actual record gaps, but underestimate others. 
      For $k\le6$, the data shows that $E_1$ is closer to a median-unbiased
      estimator.\footnote{A median-unbiased estimator $E_{\mbox{\tiny med}}(x)$ has as many observed values above it as below it.}
      (We can make it even closer by tweaking the $b$ value; 
      e.\,g., setting $b\approx1.2597$ for twin primes, or $b\approx0.7497$ for prime quadruplets, 
      would turn $E_1$ into a median-unbiased estimator for maximal gaps below $10^{15}$.)
%
\item About 90\% of the observed gaps are within $\pm2a$ of the~$E_1$ curve.
      Over 50\% of the observed gaps are within $\pm a$ of $E_1$. 
This level of accuracy appears to be in line with heuristics based on statistical models 
(where the relevant extreme-value distributions have %the mode $\mu\approx a\log(x/a)$ and 
the standard deviation $\pi a/\sqrt{6}\approx1.28a$; see {\em Appendix}).

\item Consider median-unbiased estimators $E_{\mbox{\tiny med}}(G_k(p))=a(\log(p/a)-b_{\mbox{\tiny med}})$ for $p&lt;10^{15}$.
      Computations show that the value of $b_{\mbox{\tiny med}}$ tends to decrease when $k$ increases; also,
      our empirical value $b={2\over k}$ in the $E_1$ estimator %decreases with increasing $k$; however, $b={2\over k}$ and
      is a little closer to zero than the median-unbiased value $b_{\mbox{\tiny med}}$.
      (For a simple way to refine $b$, see remark at the end of sect.\,5.2.)

\begin{figure}[H] 
  \centering
  % file name: fig1maxgaps2tuples.eps
  \includegraphics[bb=21 38 765 513,width=5.67in,keepaspectratio]{fig1maxgaps2tuples}
  \caption{Maximal gaps between twin primes $\{p, p+2\}$ 
           (\seqnum{A113274}).
           Plotted (bottom to top): expected average gap $a=0.75739\log^2 p$, 
           estimators $E_1=a\log(p/a)-ba$, $E_2=a\log(p/a)$, $E_3=a\log p=0.75739\log^3 p$,
           where $p$ is the end-of-gap prime; $b=1$.
  }
  \label{fig:2tuples-maximal-gaps}
\end{figure}



\item For relatively small values of $p$ that we deal with, the estimator $E_3$ may seem useless (too far above the realistic values). 
      %This is deceptive because 
      However, all three estimators are asymptotically equivalent,
      $E_1 \sim E_2 \sim E_3$ when $p\to\infty$.

\item The estimator $E_3=C_k \log^{k+1}p$ overestimates all known record gaps. 
      In most cases, the error of $E_3$ is close to $a \log a$, exactly as expected from extreme-value statistics.
      Thus $E_3$ may be a good candidate for an {\em upper bound} for all record gaps;
      so in statement (B) of section 4.2 we may have $M_k=C_k=H_k^{-1}$, and
$$
G_k(p)&lt;C_k \log^{k+1}p \qquad\mbox{(an analog of Cram\'er's conjecture)}.
$$
It would be interesting to see any counterexamples, i.\,e., gaps exceeding $C_k \log^{k+1}p$.
%
\begin{figure}[hb] % float placement: (h)ere, page (t)op, page (b)ottom, other (p)age
  \centering
  % file name: fig2maxgaps4tuples.eps
  \includegraphics[bb=22 15 780 495,width=5.67in,height=5.67in,keepaspectratio]{fig2maxgaps4tuples}
  \caption{Maximal gaps between prime quadruplets
           $\{p, p+2, p+6, p+8\}$ 
           (\seqnum{A113404}).
           Plotted (bottom to top): expected average gap $a=0.24089\log^4 p$, 
           estimators $E_1=a\log(p/a)-ba$, $E_2=a\log(p/a)$, $E_3=a\log p=0.24089\log^5 p$,
           where $p$ is the end-of-gap prime; $b=1/2$.
  }
  \label{fig:4tuples-maximal-gaps-1204a}
\end{figure}
%
\end{enumerate}

\smallskip\noindent
{\bf Absolute error.} The absolute error $|E_i-G_k(p)|$ tends to grow (but not monotonically) as $p\to\infty$
for all three estimators $E_1$, $E_2$, $E_3$.
Heuristically, we expect the absolute error to be unbounded and, on average, continue to grow 
for all three estimators. Probable absolute errors are $O(a)$ for $E_1$ and $E_2$, and $O(a\log a)$ for $E_3$. 

\smallskip\noindent
{\bf Relative error.} The relative error $|\varepsilon_i|=|E_i-G_k(p)|/G_k(p)$ tends to decrease (but not monotonically) 
for all three estimators as $p\to\infty$.
It may not be obvious from Figures~\ref{fig:2tuples-maximal-gaps}--\ref{fig:6tuples-maximal-gaps}, 
but we must have $|\varepsilon_i|\to0$ either for {\it all three} estimators or for {\it none} of them.
({\em Note}: the limit of $|\varepsilon_i|$ as $p\to\infty$ might not exist at all; 
that would invalidate most of our conjectures.)

\smallskip\noindent
{\bf Error in average-gap units {\em a}.} 
The error $(E_3-G_k(p))/a$, i.\,e., the $E_3$ error expressed as a number of expected average gaps, 
grows about as fast as $\log a$ (but not monotonically). 
Judging from limited numerical data, the corresponding error $(E_i-G_k(p))/a$ seems bounded as $p\to\infty$ 
if we use estimators $E_1$ or $E_2$. 
Heuristically, for $E_1$ and $E_2$ this error should remain bounded for the majority (but not all) of the record gaps.


\begin{figure}[htb] % float placement: (h)ere, page (t)op, page (b)ottom, other (p)age
  \centering
  % file name: fig3maxgaps6tuples.eps
  \includegraphics[bb=13 11 783 500,width=5.67in,height=5.67in,keepaspectratio]{fig3maxgaps6tuples}
  \caption{Maximal gaps between prime sextuplets $\{p$, $p+4$, $p+6$, $p+10$, $p+12$, $p+16\}$ 
           (\seqnum{A200503}).
           Plotted (bottom to top): expected average gap $a=0.057808\log^6 p$, 
           estimators $E_1=a\log(p/a)-ba$, $E_2=a\log(p/a)$, $E_3=a\log p=0.057808\log^7 p$,
           where $p$ is the end-of-gap prime; $b=1/3$. 
  }
  \label{fig:6tuples-maximal-gaps}
\end{figure}

\smallskip\noindent
Overall, the prediction that record gaps are about 
$a\log(p/a)+O(a)$ appears correct for the vast majority of actual gaps, as far as we have checked ($p&lt;10^{15}$). 
Note that the ``optimal'' $O(a)$ term ($-ba$ in the $E_1$ estimator) is negative, at least for $k\le6$.
For larger values of $k$, the parameter $b$ gets closer to zero. %(and might change sign).
Empirically, for $k$-tuples with $k\ge6$, 
the $E_1$ estimator will likely produce good results even with $b\approx0$. %(and $|b|\le\gamma\approx 0.5772).$ 
Therefore, for large $k$ we might want to simplify the model and use $b=0$, i.\,e., use the estimator $E_2=\max(a,a\log(p/a))$, 
the dotted curve in the above figure. 
However, maximal gap estimators with certain special properties 
(e.g., median-unbiased estimators) will still require nonzero values of $b$.

\newpage

\begin{center}TABLE 2 \\Maximal gaps between twin primes $\{p$, $p+2\}$ below $10^{15}$ \\[0.5em]
%\small
\begin{tabular}{rrr|rrr}  
\hline
End-of-gap prime  &amp; Gap $g_2$ &amp; $g^*_2$~\vphantom{\fbox{$1^1$}} &amp; 
End-of-gap prime  &amp; Gap $g_2$ &amp; $g^*_2$~\vphantom{\fbox{$1^1$}} \\
[0.5ex]\hline
\vphantom{\fbox{$1^1$}}
5&amp;2&amp;0.084&amp;24857585369&amp;6552&amp;$-2.765$ \\
11&amp;6&amp;0.451&amp;40253424707&amp;6648&amp;$-3.585$\\
29&amp;12&amp;0.180&amp;42441722537&amp;7050&amp;$-2.811$\\
59&amp;18&amp;$-0.115$&amp;43725670601&amp;7980&amp;$-0.830$\\
101&amp;30&amp;0.025&amp;65095739789&amp;8040&amp;$-1.625$\\
347&amp;36&amp;$-1.205$&amp;134037430661&amp;8994&amp;$-1.323$\\
419&amp;72&amp;$-0.112$&amp;198311695061&amp;9312&amp;$-1.604$\\
809&amp;150&amp;1.247&amp;223093069049&amp;9318&amp;$-1.865$\\
2549&amp;168&amp;$-0.396$&amp;353503447439&amp;10200&amp;$-1.262$\\
6089&amp;210&amp;$-1.011$&amp;484797813587&amp;10338&amp;$-1.747$\\
13679&amp;282&amp;$-1.189$&amp;638432386859&amp;10668&amp;$-1.792$\\
18911&amp;372&amp;$-0.486$&amp;784468525931&amp;10710&amp;$-2.195$\\
24917&amp;498&amp;0.645&amp;794623910657&amp;11388&amp;$-1.032$\\
62927&amp;630&amp;0.290&amp;1246446383771&amp;11982&amp;$-1.081$\\
188831&amp;924&amp;0.834&amp;1344856603427&amp;12138&amp;$-0.998$\\
688451&amp;930&amp;$-1.728$&amp;1496875698749&amp;12288&amp;$-1.002$\\
689459&amp;1008&amp;$-1.161$&amp;2156652280241&amp;12630&amp;$-1.309$\\
851801&amp;1452&amp;1.577&amp;2435613767159&amp;13050&amp;$-0.916$\\
2870471&amp;1512&amp;$-0.721$&amp;4491437017589&amp;14262&amp;$-0.481$\\
4871441&amp;1530&amp;$-1.689$&amp;13104143183687&amp;14436&amp;$-2.773$\\
9925709&amp;1722&amp;$-2.070$&amp;14437327553219&amp;14952&amp;$-2.255$\\
14658419&amp;1902&amp;$-1.948$&amp;18306891202907&amp;15396&amp;$-2.181$\\
17384669&amp;2190&amp;$-0.918$&amp;18853633240931&amp;15720&amp;$-1.793$\\
30754487&amp;2256&amp;$-1.805$&amp;     23275487681261 &amp;16362&amp;$-1.398$\\
32825201&amp;2832&amp;0.601  &amp;     23634280603289 &amp;16422&amp;$-1.351$\\
96896909&amp;2868&amp;$-1.646$&amp;     38533601847617 &amp;16590&amp;$-2.291$\\
136286441&amp;3012&amp;$-1.812$&amp;   43697538408287 &amp;16896&amp;$-2.178$\\
234970031&amp;3102&amp;$-2.611$&amp;   56484333994001 &amp;17082&amp;$-2.539$\\
248644217&amp;3180&amp;$-2.451$&amp;   74668675834661 &amp;18384&amp;$-1.507$\\
255953429&amp;3480&amp;$-1.454$&amp;  116741875918727&amp;19746&amp;$-0.864$\\
390821531&amp;3804&amp;$-1.260$&amp;  136391104748621&amp;19992&amp;$-0.940$\\
698547257&amp;4770&amp;0.571&amp;    221346439686641&amp;20532&amp;$-1.467$\\
2466646361&amp;5292&amp;$-0.816$&amp; 353971046725277&amp;21930&amp;$-0.955$\\
4289391551&amp;6030&amp;$-0.075$&amp; 450811253565767&amp;22548&amp;$-0.834$\\
19181742551&amp;6282&amp;$-2.831$&amp;742914612279527&amp;23358&amp;$-1.149$\\
24215103971&amp;6474&amp;$-2.888$&amp; &amp; &amp; \\
\hline
\end{tabular}
\end{center}
\normalsize

\newpage

\begin{center}TABLE 3 \\Maximal gaps between prime quadruplets $\{p$, $p+2$, $p+6$, $p+8\}$ below $10^{15}$ \\[0.5em]
%\small
\begin{tabular}{rrr|rrr}  
\hline
End-of-gap prime  &amp; Gap $g_4$ &amp; $g^*_4$~\vphantom{\fbox{$1^1$}} &amp; 
End-of-gap prime  &amp; Gap $g_4$ &amp; $g^*_4$~\vphantom{\fbox{$1^1$}} \\
[0.5ex]\hline
\vphantom{\fbox{$1^1$}}
11&amp;6&amp;0.430&amp;3043668371&amp;557340&amp;$-0.750$\\
101&amp;90&amp;0.902&amp;3593956781&amp;635130&amp;0.188\\
821&amp;630&amp;0.770&amp;5676488561&amp;846060&amp;2.366\\
1481&amp;660&amp;0.192&amp;25347516191&amp;880530&amp;$-1.576$\\
3251&amp;1170&amp;$-0.014$&amp;27330084401&amp;914250&amp;$-1.358$\\
5651&amp;2190&amp;0.194&amp;35644302761&amp;922860&amp;$-1.966$\\
9431&amp;3780&amp;0.518&amp;56391153821&amp;1004190&amp;$-2.244$\\
31721&amp;6420&amp;$-0.125$&amp;60369756611&amp;1070490&amp;$-1.697$\\
43781&amp;8940&amp;0.211&amp;71336662541&amp;1087410&amp;$-1.967$\\
97841&amp;9030&amp;$-0.998$&amp;76429066451&amp;1093350&amp;$-2.089$\\
135461&amp;13260&amp;$-0.539$&amp;87996794651&amp;1198260&amp;$-1.383$\\
187631&amp;16470&amp;$-0.434$&amp;96618108401&amp;1336440&amp;$-0.242$\\
326141&amp;24150&amp;$-0.094$&amp;151024686971&amp;1336470&amp;$-1.535$\\
768191&amp;28800&amp;$-1.004$&amp;164551739111&amp;1348440&amp;$-1.663$\\
1440581&amp;29610&amp;$-1.957$&amp;171579255431&amp;1370250&amp;$-1.577$\\
1508621&amp;39990&amp;$-0.977$&amp;211001269931&amp;1499940&amp;$-0.986$\\
3047411&amp;56580&amp;$-0.812$&amp;260523870281&amp;1550640&amp;$-1.150$\\
3798071&amp;56910&amp;$-1.217$&amp;342614346161&amp;2550750&amp;6.412\\
5146481&amp;71610&amp;$-0.714$&amp;1970590230311&amp;2561790&amp;0.197\\
5610461&amp;83460&amp;$-0.049$&amp;4231591019861&amp;2915940&amp;$-0.076$\\
9020981&amp;94530&amp;$-0.379$&amp;5314238192771&amp;2924040&amp;$-0.748$\\
17301041&amp;114450&amp;$-0.678$&amp;7002443749661&amp;2955660&amp;$-1.421$\\
22030271&amp;157830&amp;0.996&amp;8547354997451&amp;3422490&amp;0.447\\
47774891&amp;159060&amp;$-0.861$&amp;15114111476741&amp;3456720&amp;$-1.200$\\
66885851&amp;171180&amp;$-1.135$&amp;16837637203481&amp;3884670&amp;0.533\\
76562021&amp;177360&amp;$-1.202$&amp;30709979806601&amp;4228350&amp;0.134\\
87797861&amp;190500&amp;$-1.023$&amp;43785656428091&amp;4537920&amp;0.307\\
122231111&amp;197910&amp;$-1.515$&amp;47998985015621&amp;4603410&amp;0.278\\
132842111&amp;268050&amp;0.677&amp;55341133421591&amp;4884900&amp;0.972\\
204651611&amp;315840&amp;1.022&amp;92944033332041&amp;5851320&amp;2.995\\
628641701&amp;395520&amp;0.099&amp;412724567171921&amp;6499710&amp;0.021\\
1749878981&amp;435240&amp;$-1.669$&amp;473020896922661&amp;6544740&amp;$-0.293$\\
2115824561&amp;440910&amp;$-2.020$&amp;885441684455891&amp;6568590&amp;$-2.253$\\
2128859981&amp;513570&amp;$-0.617$&amp;947465694532961&amp;6750330&amp;$-1.932$\\
2625702551&amp;536010&amp;$-0.749$&amp;979876644811451&amp;6983730&amp;$-1.356$\\
2933475731&amp;539310&amp;$-0.982$&amp; &amp; &amp; \\			
\hline
\end{tabular}
\end{center}
\normalsize

{\vskip 2mm}
\noindent
{\em Notes:} Computing Tables 3 and 4 took the author two weeks on a quad-core 2.5 GHz CPU.
Table 2 reflects Fischer's extensive computation \cite{fischer}. 
For earlier computations of maximal gaps by Boncompagni, Rodriguez, and Rivera, see also OEIS \seqnum{A113274}, \seqnum{A113404} \cite{oeis,rr}. 
\normalsize


\begin{center}TABLE 4 \\Maximal gaps between prime 6-tuples $\{p$, $p+4$, $p+6$, $p+10$, $p+12$, $p+16\}$ below $10^{15}$ \\[0.5em]
\small
\begin{tabular}{rrr|rrr}  
\hline
End-of-gap prime  &amp; Gap $g_6$ &amp; $g^*_6$~\vphantom{\fbox{$1^1$}} &amp; 
End-of-gap prime  &amp; Gap $g_6$ &amp; $g^*_6$~\vphantom{\fbox{$1^1$}} \\
[0.5ex]\hline
\vphantom{\fbox{$1^1$}}
97&amp;90&amp;1.856&amp;422248594837&amp;159663630&amp;$-2.389$\\
16057&amp;15960&amp;1.414&amp;427372467157&amp;182378280&amp;$-1.353$\\
43777&amp;24360&amp;0.949&amp;610613084437&amp;194658240&amp;$-1.751$\\
1091257&amp;1047480&amp;1.570&amp;660044815597&amp;215261760&amp;$-1.079$\\
6005887&amp;2605680&amp;1.176&amp;661094353807&amp;230683530&amp;$-0.427$\\
14520547&amp;2856000&amp;$-0.048$&amp;853878823867&amp;245336910&amp;$-0.573$\\
40660717&amp;3605070&amp;$-1.035$&amp;1089869218717&amp;258121710&amp;$-0.786$\\
87423097&amp;4438560&amp;$-1.646$&amp;1248116512537&amp;263737740&amp;$-0.968$\\
94752727&amp;5268900&amp;$-1.380$&amp;1475318162947&amp;311017980&amp;0.246\\
112710877&amp;17958150&amp;3.778&amp;1914657823357&amp;322552230&amp;$-0.170$\\
403629757&amp;21955290&amp;1.526&amp;1954234803877&amp;342447210&amp;0.436\\
1593658597&amp;23910600&amp;$-1.149$&amp;3428617938787&amp;421877610&amp;1.085\\
2057241997&amp;37284660&amp;0.730&amp;9368397372277&amp;475997340&amp;$-0.740$\\
5933145847&amp;40198200&amp;$-1.318$&amp;10255307592697&amp;507945690&amp;$-0.256$\\
6860027887&amp;62438460&amp;1.224&amp;13787085608827&amp;509301870&amp;$-1.159$\\
14112464617&amp;64094520&amp;$-0.506$&amp;21017344353277&amp;629540730&amp;0.084\\
23504713147&amp;66134250&amp;$-1.523$&amp;33158448531067&amp;659616720&amp;$-0.819$\\
24720149677&amp;70590030&amp;$-1.228$&amp;41349374379487&amp;797025180&amp;0.985\\
29715350377&amp;77649390&amp;$-1.038$&amp;72703333384387&amp;813158010&amp;$-0.682$\\
29952516817&amp;83360970&amp;$-0.556$&amp;89166606828697&amp;823158840&amp;$-1.190$\\
45645253597&amp;90070470&amp;$-1.064$&amp;122421855415957&amp;854569590&amp;$-1.723$\\
53086708387&amp;93143820&amp;$-1.202$&amp;139865086163977&amp;888931050&amp;$-1.642$\\
58528934197&amp;98228130&amp;$-1.063$&amp;147694869231727&amp;1010092650&amp;$-0.077$\\
93495691687&amp;117164040&amp;$-0.935$&amp;186010652137897&amp;1018139850&amp;$-0.755$\\
97367556817&amp;131312160&amp;$-0.108$&amp;202608270995227&amp;1139590200&amp;0.603\\
240216429907&amp;151078830&amp;$-1.388$&amp;332397997564807&amp;1152229260&amp;$-0.967$\\
414129003637&amp;154904820&amp;$-2.566$&amp;424682861904937&amp;1204960680&amp;$-1.155$\\
419481585697&amp;158654580&amp;$-2.420$&amp;437805730243237&amp;1457965740&amp;1.725\\
\hline
\end{tabular}
\end{center}
\normalsize

\phantom{\vspace{1cm}}

\subsection{The distribution of maximal gaps}

We have just seen that maximal gaps between prime $k$-tuples below $p$ grow about as fast as $a\log(p/a)$.
Thus, the curve $a\log(p/a)$ (the dotted curve in Figures~1--3) may be regarded as a ``trend.''
Now we are going to take a closer look at the distribution of maximal gaps in the neighborhood of this ``trend'' curve. 
In our analysis, we will also include the case $k=1$, record gaps between primes (\seqnum{A005250}). 
%for which the expected average gap is $a=\log p$, as suggested by the prime number theorem.
For each $k=1$, $2$, $4$, $6$, we will make a histogram of shifted and scaled ({\em standardized}) record gaps:
subtract the ``trend'' $a\log(p/a)$ from actual gaps, and then 
divide the result by the ``natural unit'' $a$, the expected average gap.  
%
This way, all record gaps $g_k(p)$ are mapped to standardized values $g_k^*$ (shown in Tables 2--4):
$$
g_k(p) ~~\to~~ g_k^* = \frac{g_k(p)-a\log(p/a)}{a} % ~=~ \frac{g_k(p)}{a}-\log{p\over a}
, \quad \mbox{ where~ } a = C_k \log^k p.
$$
Record gaps that exceed $a\log(p/a)$ are mapped to standardized values $g_k^* &gt; 0$, 
while those below $a\log(p/a)$ are mapped to $g_k^* &lt; 0$.
Note that the majority of known record gaps are below the dotted curve in Figures 1--3; 
accordingly, most of the standardized values $g_k^*$ are negative.
%
It is also immediately apparent that the histograms and fitting distributions are skewed: 
the right tail is longer and heavier.
This skewness is a well-known characteristic of {\em extreme value distributions}~---
and it comes as no surprise that a good fit obtained with the help of distribution-fitting software \cite{easyfit} 
is the {\em Gumbel distribution}, a common type of extreme value distribution (see {\em Appendix}).
%
\begin{figure}[tbh] % float placement: (h)ere, page (t)op, page (b)ottom, other (p)age
\centering
% file name: fig4histograms.eps
\includegraphics[bb=11 25 778 320,width=6in,height=4.8in,keepaspectratio]{fig4histograms}
\caption{The distribution of standardized maximal gaps $g_k^*$: 
histograms and the fitting Gumbel distribution PDFs.
For $k=1$ (primes), the histogram shows record gaps below $4\times10^{18}$.
For $k=2,4,6$ ($k$-tuples), the histograms show record gaps below $10^{15}$. 
}
\label{fig:fig4histograms}
\end{figure}
%

Here is why we can say that the Gumbel distribution is indeed a good fit:

\smallskip\noindent 
(1) Based on goodness-of-fit statistics (the Anderson-Darling test as well as the Kolmogorov-Smirnov test), 
one {\bf\em cannot reject} the hypothesis that the standardized values 
$g_k^*$ might be values of independent identically distributed random variables with the Gumbel distribution.

\smallskip\noindent
(2) Although a few other distributions could not be rejected either,
the Anderson-Darling and Kolmogorov-Smirnov goodness-of-fit statistics for the Gumbel distribution are better
than the respective statistics for any other two-parameter distribution we tried 
(including~normal, uniform, logistic, Laplace, Cauchy, power-law, etc.),
and better than for several three-parameter distributions 
(e.\,g.,~triangular, error, Beta-PERT, and others).

\smallskip
An equally good or even marginally better fit is the three-parameter
{\em generalized extreme value} (GEV) distribution, which in fact includes the Gumbel distribution as a special case.
The {\em shape parameter} in the fitted GEV distribution turns out very close to zero; 
note that a GEV distribution with a zero shape parameter is precisely the Gumbel distribution.
%
The {\em scale} parameter of the fitted Gumbel distribution is close to one.
The {\em mode} $\mu^{*}$ of the fitted distribution is negative.
Figure~\ref{fig:fig4histograms} gives the approximate value of $\mu^{*}$ for $k=1,2,4,6$;
$\mu^{*}$ is the coordinate of the maximum of the distribution PDF (probability density function). 


{\it Note}: Now that we have a more precise value of the mode $\mu^*$, 
we can refine the parameter $b$ in the $E_1$ estimator: %to estimate the record gaps, 
use $-b=\mu^* + \gamma$, 
which estimates the {\em mean} of the fitted Gumbel distribution in Fig.\,\ref{fig:fig4histograms}.
Here $\gamma = 0.5772\cdots$ is the Euler-Mascheroni constant.

\section{On maximal gaps between primes}

Let us now apply our model of gaps to {\em maximal gaps between primes} 
(\seqnum{A005250}) \cite{oeis},\,\cite{nicely}: 
\begin{quotation}
Maximal prime gaps are about $a\log(p/a)-ba$, with $a=\log p$ and $b\approx3$. 
\end{quotation}
If all record gaps behave like those in Figure~\ref{fig:1tuples-maximal-gaps}
(showing the 75 known record gaps between primes $p&lt;4\times10^{18}$), 
this would confirm the Cram\'er and Shanks conjectures: 
maximal prime gaps are smaller than $\log^2 p$~--- but smaller only by $O(a\log a)$. 
We also easily see that the Cram\'er and Shanks conjectures are compatible with our estimate of record gaps.
Indeed, for $a = \log p$ and {\em any fixed} $b\ge0$, we have $\log^2 p &gt; a(\log(p/a)-b) \sim \log^2 p$ as $p\to\infty$. 

\begin{figure}[h] % float placement: (h)ere, page (t)op, page (b)ottom, other (p)age
  \centering
  % file name: fig5maxgapsprimes.eps
  \includegraphics[bb=14 19 783 486,width=5.67in,height=5.67in,keepaspectratio]{fig5maxgapsprimes}
  \caption{Maximal gaps between consecutive primes (\seqnum{A005250}).
           Plotted (bottom to top): expected average gap $a=\log p$, 
           estimators $E_1=a\log(p/a)-ba$, $E_2=a\log(p/a)$ (dotted), $E_3=a\log p=\log^2 p$,
           where $p$ is the end-of-gap prime; $b=3$. 
  }
  \label{fig:1tuples-maximal-gaps}
\end{figure}

\noindent
{\em Notes}:
Maier's theorem (1985) \cite{maier} states that there are (relatively short) intervals 
where typical gaps between primes are greater than the average ($\log p$) expected from the prime number theorem. 
Based in part on Maier's theorem, Granville \cite{granville} adjusted the Cram\'er conjecture and proposed that, 
as $p\to\infty$, $\lim \sup(G(p)/\log^2p) \ge 2e^{-\gamma} = 1.1229\ldots$ 
This would mean that an infinite subsequence of maximal gaps must lie above the Cram\'er-Shanks upper limit 
$\log^2p$, i.\,e., above the $E_3$ line in Figure~\ref{fig:1tuples-maximal-gaps} --- 
and this hypothetical subsequence (or an infinite subset thereof) 
must approach a line whose slope is about 1.1229 times steeper! 
%
However, for now, there are no known maximal prime gaps above $\log^2p$. 
Interestingly, Maier himself did not voice serious concerns that the Cram\'er or Shanks conjecture might be 
in danger because of his theorem; thus, Maier and Pomerance \cite{mp} simply remarked in 1990:
%
\begin{quotation}\noindent{\small
Cram\'er conjectured that $\lim\sup G(x)/\log^2\negthinspace x = 1$, while Shanks made the stronger conjecture that 
$G(x)\sim\log^2x$, but we are still a long way from proving these statements.
}
\end{quotation}


\section{Corollaries: Legendre-type conjectures}

Assuming the conjectures of Section 4, 
one can state (and verify with the aid of a computer) 
a number of interesting corollaries. 
The following conjectures generalize Legendre's conjecture about primes between squares.
%
\begin{itemize}
\item For each integer $n &gt; 0$, there is always a prime between $n^2$ and $(n+1)^2$. ({\em Legendre})  
\item For each integer $n &gt; 122$, there are twin primes between $n^2$ and $(n+1)^2$. (\seqnum{A091592}) 
\item For each integer $n &gt; 3113$, there is a prime triplet between $n^2$ and $(n+1)^2$. 
\item For each integer $n &gt; 719377$, there is a prime quadruplet between $n^2$ and $(n+1)^2$. 
\item For each integer $n &gt; 15467683$, there is a prime quintuplet between $n^2$ and $(n+1)^2$. 
\item There exists a sequence $\{s_k\}$ such that, for each integer $n &gt; s_k$, 
      there is a prime $k$-tuplet between $n^2$ and $(n+1)^2$. 
      (This $\{s_k\}$ is OEIS \seqnum{A192870}: $0, 122, 3113, 719377, \ldots$)
\end{itemize}
%
Another family of Legendre-type conjectures for prime $k$-tuplets 
can be obtained by replacing squares with cubes, 4th, 5th, and higher powers of $n$:
\begin{itemize}
\item For each integer $n &gt; 0$, there are twin primes between $n^3$ and $(n+1)^3$.
\item For each integer $n &gt; 0$, there is a prime triplet between $n^4$ and $(n+1)^4$.
\item For each integer $n &gt; 0$, there is a prime quadruplet between $n^5$ and $(n+1)^5$.
\item For each integer $n &gt; 0$, there is a prime quintuplet between $n^6$ and $(n+1)^6$.
\item For each integer $n &gt; 6$, there is a prime sextuplet between $n^7$ and $(n+1)^7$.
\end{itemize}
%
A further generalization is also possible:
\begin{itemize}
\item There is a prime $k$-tuplet between $n^r$ and $(n+1)^r$ for each integer $n &gt; n_0(k, r)$, 
      where $n_0(k,r)$ is a function of $k\ge1$ and $r &gt; 1$. 
\end{itemize}
%
To justify the above Legendre-type conjectures, we can assume the $k$-tuple conjecture 
plus statement (B) (sect.\,4.2) bounding the size of gaps between $k$-tuples: 
$g_k(p)&lt;M_k \log^{k+1}p$. We can now use the following elementary argument:
%
Consider a fixed $r &gt; 1$, and let $x$ be a number in the interval between $n^r$ and $(n+1)^r$. 
Then, for large $n$, the interval size $d_r=(n+1)^r-n^r\sim rn^{r-1}$ 
will be asymptotic to $rx^{(r-1)/r}$: 
because $x\sim n^r$ and $d_r \sim rn^{r-1}$ when $n \to\infty$, 
we have $n\sim x^{1/r}$ and $d_r \sim rx^{(r-1)/r}$ when $x \to\infty$. 
%
But any positive power of $x$ grows faster than any positive power of $\log x$ when $x \to\infty$.
So $x^{(r-1)/r}$ must grow faster than $\log^{k+1} x$. Therefore, the intervals 
$[n^r,(n+1)^r]$ --- whose sizes are about $rx^{(r-1)/r}$ --- will eventually become
much larger than the largest gaps between prime $k$-tuples containing primes $p \approx x$.
For smaller $n$, a computer check finishes the job.

However, {\bf\em this is not a proof}: we have relied on unproven assumptions.
%
As Hardy and Wright pointed out in 1938 (referring to the infinitude of twin primes and prime triplets),
\begin{quotation}\noindent{\small
Such conjectures, with larger sets of primes, can be multiplied, but their
proof or disproof is at present beyond the resources of mathematics. \cite[p.\ 6]{hw}
}
\end{quotation} 
%
Many years have passed, yet conjectures like these remain exceedingly difficult to prove.


\section{Appendix: a note on statistics of extremes}

In this appendix we use extreme value statistics to derive a simple formula expressing the 
expected maximal interval between rare random events in terms of the average interval:
$$
E(\mbox{max interval}) = a \log(T/a) + O(a)  \qquad\qquad   (1 \ll a \ll T), 
$$
where $a$ is the average interval between the rare events, 
$T$ is the total observation time or length, as applicable,
and $E(\mbox{max interval})$ stands for the {\em mathematical expectation} of the maximal interval.
%
The formula holds for random events occurring at exponentially distributed (real-valued) intervals, 
as well as for events occurring at geometrically distributed discrete (integer-valued) intervals. 
(For more information on extreme value distributions of random sequences see Gumbel's classical book \cite{gumbel} 
or more recent books \cite{bgt,galambos}.
For extreme value distributions of discrete random sequences, such as head runs in coin toss sequences, 
see also the papers of Schilling \cite{schilling} or 
Gordon, Schilling, and Waterman \cite{gsw} and further references therein.) 

 
\subsection{Two problems about random events}
For illustration purposes, we will use two problems:

\medskip\noindent
{\bf Problem A. }
Consider a non-stop toll bridge with very light traffic. Let 
$P &gt; 1/2$ be the probability that no car crosses the toll line during a one-second interval, and 
$q = 1 - P$ the probability to see a car at the toll line during any given second. 
Suppose we observe the bridge for a total of $T$ seconds, where $T$ is large, while $P$ is constant.

\medskip\noindent
{\bf Problem B. } Consider a biased coin with a probability of heads $P &gt; 1/2$ (and the probability of tails $q = 1 - P$). 
We toss the coin a total of $T$ times, where $T$ is large.

\medskip\noindent
In both problems, answer the following questions about the rare events (cars or tails):

\medskip\noindent
(1) What is the {\it expected total number} of rare events %(cars or tails) 
in the observation series of length $T$?

\medskip\noindent
(2) What is the {\it expected average interval} $a$ between events (i.\,e., between cars/tails)?

\medskip\noindent
(3) What is the {\it expected maximal interval} between events, as a function of $a$?

\medskip\noindent
Notice that the first two questions are much easier than the third.
Here are the easy answers:

\medskip\noindent
(1) Because the probability of the event is $q$ at any given second/toss, 
we expect a total of $nq$ events after $n$ seconds/tosses, 
and a total of $Tq$ events at the end of the entire observation series of length $T$.

\medskip\noindent
(2) To estimate the expected average interval $a$ between events, 
we divide the total length $T$ of our observation series by the expected total number of events $Tq$. 
So a reasonable estimate\footnote{
For a small $q$, the estimate $a \approx 1/q$ is quite accurate: its error is only $O(1)$.
To prove this, we can use specific distributions of intervals between events.
Thus, if in Problem A the intervals between cars are distributed exponentially (CDF $1-P^t=1-e^{-t/a}$),
then the mean interval is $a=1/\log(1/P) = 1/q+O(1)$. 
If in Problem B the observed runs of heads are distributed geometrically (CDF $1-P^{r+1}$),
then the mean run of heads is $P/q = 1/q+O(1)$. 
}
of the expected average interval between events is $a \approx T/(Tq) = 1/q$.

\medskip\noindent
(3) Quite obviously, we can predict that the expected maximal interval is less than $T$, but not less than $a$:
$$
    a  \le  E(\mbox{max interval})  &lt;  T. 
$$
The expected maximal interval will likely depend on both $a$ and $T$:
$$
    E(\mbox{max interval})  =  f(a,T). 
$$
It is also reasonable to expect that $f(a,T)$ should be an increasing function of both arguments, $a$ and $T$.
Can we say anything more specific about the expected maximal interval?

 
\subsection{An estimate of the most probable maximal interval}
In both problems A and B we will assume that $1 \ll a \ll T$ --- or, in plain English:
\begin{itemize}
\item the events are {\it rare} ($1\ll a$), and
\item our observations continue for long enough to see many events ($a \ll T$).
\end{itemize}
In Problem A, to estimate the most probable maximal interval between cars we proceed as follows:
%
After $n$ seconds of observations, we would have seen about $nq$ cars, 
hence about $nq$ intervals between cars. The intervals are independent of each other and real-valued. 
A known good model for the distribution of these intervals is the {\it exponential distribution}
that has the cumulative distribution function (CDF) $1-P^{\,t}$: %$= 1 - e^{-t/\beta}$:

%with probability 1, each interval must be at least 0 seconds;

with probability $P$, any given interval between cars is at least 1 second;

with probability $P^2$, any given interval is at least 2 seconds;

with probability $P^3$, any given interval is at least 3 seconds;$\ldots$

with probability $P^{\,t}$, any given interval is at least $t$ seconds.

\smallskip\noindent
Thus, after $n$ seconds of observations and about $nq$ carless intervals, we would reasonably expect 
that at least one interval is no shorter than $t$ seconds if we choose $t$ such that
$$
    P^{\,t} \times (nq) \ge 1. 
$$
Now it is easy to estimate the most probable maximal interval $t_{\max}$:
$$
    P^{\,t_{\max}}  \approx  1/(nq)
$$
$$
    (1/P)^{t_{\max}}  \approx  nq
$$
$$
    t_{\max}  \approx  \log_{1/P}(nq). 
$$
In Problem B we can estimate the longest run of heads $R_n$ after $n$ coin tosses reasoning very similarly. 
One notable difference is that now the head runs are discrete (have integer lengths). 
Accordingly, they are modeled using the {\it geometric distribution}. 
Schilling \cite{schilling} has this estimate for the longest run of heads after $n$ tosses, 
given the heads probability $P$:
$$
    R_n  \approx  \log_{1/P}(nq). 
$$
In both problems, the estimates for the most probable maximal interval (as a function of $P$ and $n$) 
have the same form $\log_{1/P}(nq)$. Therefore, it is reasonable to expect that the answers to our 
original question (3) in both problems A and B will also be the same or similar functions of 
the average interval $a$, even though the problems are modeled using different distributions of intervals. 
We will soon see that this indeed is the case.

 
\subsection{If random events are rare...}
If the events (cars in Problem A, or tails in Problem B) are rare, 
then $P$ is close to 1, and $q$ is close to 0. 
%
Using the Taylor series expansion of $\log(1/(1 - q))$, we can write:
$$
\log(1/P) = \log\left({1 \over{1-q}}\right) = q + {q^2\over 2} + {q^3\over 3} + \ldots  = q + O(q^2) 
$$
or, omitting the $O(q^2)$ terms,
\begin{eqnarray*}
\log(1/P) &amp;\approx&amp;  q,   \qquad\qquad\mbox{ and therefore } \\
{1 \over \log(1/P)} &amp;\approx&amp; {1\over q} ~\approx~ a \qquad (\mbox{moreover, we have } {1\over\log(1/P)}=a \mbox{ \,in Problem A}). 
\end{eqnarray*}
So we can transform the estimate of most probable maximal intervals, $\log_{1/P}(nq)$, like this:
\begin{eqnarray*}
 \log_{1/P}(nq)  &amp;=&amp;       { \log(nq) \over \log(1/P) }  \\
                 &amp;\approx&amp; {1\over q} \log(nq)           \\
                 &amp;\approx&amp; a \,\log{n\over a}.   \hphantom{\mspace{100mu}}
\end{eqnarray*}
For a long series of observations, with the total length or duration $n = T$ 
(e.\,g.~$T$ tosses of a biased coin, or $T$ seconds of observing the bridge), our estimate becomes
%the estimate for the most probable maximal interval becomes $a \log(T/a)$.
$$
\mbox{the most probable maximal interval} ~\approx~ a \,\log{T\over a} \,,
$$
where $a$ is the average interval between events.

 
\subsection{Expected maximal intervals}
The specific formulas for expected maximal intervals between rare events 
depend on the nature of events in the problem (whether 
the initial distribution of intervals is {\it exponential} or {\it geometric}). 
However, as $T \to\infty$, in the formulas for both cases the highest-order term turns out to be the same: 
$a \log(T/a)$, which was precisely our estimate for the most probable maximal interval.

\medskip\noindent
{\bf (A) Exponential initial distribution.}
Fisher and Tippett \cite{ft}, Gnedenko \cite{gnedenko}, Gumbel \cite{gumbel} and other authors 
showed that, for initial distributions of {\it exponential type}
(including, as a special case, the exponential distribution) 
the limiting distribution of maximal terms in a random sequence is the 
{\it double exponential distribution}~--- often called the {\it Gumbel distribution}. 
In particular, if intervals between cars in Problem A have exponential distribution 
with CDF $1-P^{\,t} = 1-e^{-t/a}$,
then the distribution of maximal intervals has these characteristics\footnote{Instead of the 
{\it scale parameter} $a$,
Gumbel \cite[p.\,157]{gumbel} uses the parameter $\alpha=1/a$. 
%
The {\it mode} $\mu_N$ (most probable value, also called the {\it location parameter}) in the $N$-event extreme-value distribution 
resulting from an exponential initial distribution is equal to the 
{\it characteristic extreme} $a \log N$ \cite[p.\,114]{gumbel}. 
The shape of the $N$-event extreme-value distribution approaches that of the limiting distribution as $N\to\infty$.
}:
\begin{eqnarray*}
\mbox{$N$-event CDF:}&amp;\hphantom{=}&amp; (1-e^{-t/a})^N = (1-\textstyle{1\over N}e^{-(t-\mu_N)/a})^N 
\quad\mbox{(distribution for $N\approx Tq$ events), } \\
\mbox{Limiting CDF:} &amp;\hphantom{=}&amp; \exp(-e^{-(t-\mu)/a})\qquad\mbox{(Gumbel distribution) \cite[{\rm p.\,157}]{gumbel},}\\
\mbox{Scale} &amp;=&amp;  a   ~=~ 1/\log(1/P) \quad\mbox{ (equal to the expected average interval)},\\
%\mbox{Most probable value}~=~
\mbox{Mode}  &amp;=&amp;  \mu  ~=~ \mu_N ~=~ a \log N ~\approx~a \log(T/a) ~\approx~\log_{1/P}(Tq) , \\
\mbox{Median}  &amp;=&amp;  \mu-a\log\log2 ~\approx~ a \log(T/a) + 0.3665a, \\
%\mbox{Expected value} ~=~ 
\mbox{Mean}  &amp;=&amp;  \mu + \gamma a ~\approx~ a \log(T/a) + 0.5772a,
\end{eqnarray*}
where $\gamma = 0.5772\cdots$ is the Euler-Mascheroni constant. 
The mean value of observed maximal intervals in Problem A will converge almost surely %\cite{gnedenko} 
to the mean $\mu + a\gamma$ of the Gumbel distribution, therefore:
$$
E(\mbox{max interval}) ~\approx~ \log_{1/P}(Tq) + \gamma a ~\approx~ a\log(T/a) + \gamma a   ~=~  a \log(T/a) + O(a). 
$$

\medskip\noindent
{\it Historical notes: }  
%E.~J.~Gumbel was not the original discoverer of his namesake distribution. 
In 1928 Fisher and Tippett \cite{ft} described three types of limiting extreme-value distributions 
and showed that the double exponential (Gumbel) distribution is the limiting extreme-value distribution 
for a certain wide class of random sequences. They also computed, among other parameters, 
the {\it mean-to-mode distance} in the double exponential distribution \cite[p.\,186]{ft}; 
it is this result that allows one to conclude that the mean is $\mu + 	\gamma a$ if the mode is $\mu$.
Gnedenko (1943) \cite{gnedenko} rigorously proved the necessary and sufficient conditions 
for an initial distribution to be in the domain of attraction of a given type of limiting distribution. 
%The three possible types of limiting distributions are the Gumbel, Fr\'echet, and Weibull distributions.

\medskip\noindent
{\bf (B) Geometric initial distribution. }
Surprisingly, in this case the limiting extreme-value distribution does not exist 
\cite[p.\,203]{schilling},\,\cite[p.\,280]{gsw}. 
For the longest run of heads $R_n$ in a series of $n$ tosses of a biased coin,
with the probability of heads $P$, we have 
$$
E(R_n)  =  \log_{1/P}(nq) + \frac{\gamma}{\log(1/P)} - {1\over2} + \mbox{smaller terms}  
\qquad\mbox{\cite[{\rm p.\,202}]{schilling}},
$$
where the first term is the same as in Problem A (up to a substitution $n = T$). 
The sum of the other terms is $O(a)$ when $P$ is close to 1; %(and is bounded when $n \to\infty$, $P=\mbox{const}$) 
so, again, we have
$$
    E(R_n)  =  a \log(n/a) + O(a). 
$$
 
\subsection{Standard deviation of extremes}
As above, the specific formula for standard deviation (SD) in distributions of 
maximal intervals between events depends on the nature of the problem 
(whether the initial distribution of intervals is exponential or geometric). 
Still, in both cases SD $\approx \pi a/\sqrt{6} = O(a)$.

\medskip\noindent
{\bf (A) Exponential initial distribution.}
Here the limiting distribution of maximal intervals is the Gumbel distribution with the scale $a = 1/\log(1/P)$, 
therefore the SD of maximal intervals must be very close to the SD of the Gumbel distribution:
$$
\mbox{SD}(\mbox{max interval}) \approx {\pi a \over \sqrt{6}} =O(a)
 \qquad\mbox{\cite[{\rm p.\,116,\,174}]{gumbel}}.
$$

\medskip\noindent
{\bf (B) Geometric initial distribution.}
For the longest run of heads $R_n$ in a series of $n$ tosses of a biased coin, the variance is
$$
\mbox{Var\,}R_n = {\pi^2\over 6\log^2(1/P)} + {1\over12} + \mbox{smaller terms} 
\qquad\mbox{\cite[{\rm p.\,202}]{schilling}},
$$
where the first term is $O(a^2)$, %when the heads probability $P \to 1$, 
while the sum of the other terms is much smaller than the first term. %when $P \to 1$, as well as when $n \to\infty$ with $P=\mbox{const}$. 
(Again, recall that for average intervals $a$ between rare events~--- in this case, 
between {\it tails}~--- we have $a \approx 1/\log(1/P)$.)
Therefore, the standard deviation is %(the square root of the variance)
$$
\mbox{SD}\,\,R_n  = \sqrt{\mbox{Var\,}R_n} = {\pi \over \sqrt{6} \log(1/P)} + \mbox{a small term} \approx {\pi a \over\sqrt{6}}=O(a).
$$

\subsection{A shortcut to the answer}
There is a simple way to ``guesstimate'' the answer $a\log(T/a) + O(a)$. 
If $a$ is the average interval between events, 
then the most probable maximal interval is about $a\log(T/a)$ (sect.~8.3). 
We can now simply use the fact that the width of the extreme value distribution is $O(a)$. 
(Imagine what happens if the rare event's probability $q$ is reduced by 50\%.
This change in $q$ would have about the same effect as if every interval became twice as large: 
then average and maximal intervals would also become twice as large, 
and the extreme value distribution would be twice as wide. 
This immediately implies that the extreme value distribution is $O(a)$ wide.) 
But then the true value of the expected maximal interval cannot be any farther 
than $O(a)$ from our estimate $a\log(T/a)$; so the expected maximal interval is $a\log(T/a) + O(a)$.

 
\subsection{Summary}
We have considered maximal intervals between random events in two common situations:
\begin{itemize}
\item rare events occurring at {\it exponentially distributed} intervals (Problem A);
\item discrete rare events at {\it geometrically distributed} intervals (Problem B).
\end{itemize}
These two situations are somewhat different:
in the former case maximal intervals have a limiting distribution (the Gumbel distribution), while
in the latter case no limiting distribution exists (here the Gumbel distribution is simply a decent approximation).
%
Nevertheless, in both cases the expected maximal interval between events is
$$
E(\mbox{max interval}) = a \log(T/a) + \gamma a + \mbox{lower-order terms } =  a \log(T/a) + O(a),    
$$
where $a$ is the average interval between events, $T$ is the total observation time or length,
and the lower-order terms depend on the initial distribution. 

\medskip\noindent
As we have seen in Sections 4--6, a remarkably similar {\it heuristic formula} $a\log(x/a)-ba$, 
with an empirical term $-ba$ replacing the ``theoretical'' $\gamma a$, satisfactorily describes the following:
\begin{itemize}
\item record gaps between primes below $x$ ($a = \log x$, $b \approx 3$; 
\seqnum{A005250})
\item record gaps between twin primes below $x$ ($a = 0.75739 \log^2 x$, $b\approx1$; \seqnum{A113274}) and, more generally,
\item record gaps between prime $k$-tuples ($a = C_k \log^k x$, $b \approx 2/k$, 
      where $C_k$ is reciprocal to the Hardy-Littlewood constant for the particular $k$-tuple).
\end{itemize}
%

\section{Acknowledgments}
The author is grateful to the anonymous referee and to
all authors, contributors, and editors of the websites 
{\it OEIS.org}, {\it PrimePuzzles.net} and {\it FermatQuotient.com}.
Many thanks also to Prof.~Marek Wolf for his interest in the initial version of this paper, 
followed by an email exchange that undoubtedly helped make this paper better.


\begin{thebibliography}{20}

\bibitem{bgt}
J.~Beirlant, Y.~Goegebeur, J.~Segers, and J.~Teugels, {\it Statistics of Extremes: Theory and Applications}, Wiley, 2004.

\bibitem{berman}
S.~M.~Berman, Limiting distributions of the maximum term in sequences of dependent random variables.
{\it Ann.\ Math.\ Statist.} {\bf 33} (1962), 894--908.

\bibitem{cohen}
H.~Cohen, High precision computation of Hardy-Littlewood constants,
preprint, 2012. Available at 
\url{http://www.math.u-bordeaux1.fr/~cohen/hardylw.dvi}.

\bibitem{cram}
H.~Cram\'er, On the order of magnitude of the difference between consecutive prime numbers. 
{\it Acta Arith.} {\bf 2} (1937), 23--46. 

\bibitem{fischer} 
R.~Fischer, Maximale L\"ucken (Intervallen) von Primzahlenzwillingen,
preprint, 2008.  Available at
\url{http://www.fermatquotient.com/PrimLuecken/ZwillingsRekordLuecken}.

\bibitem{fischer2} 
R.~Fischer, Maximale Intervalle von Primzahlenpaaren, preprint,
2006.  Available at 
\url{http://www.fermatquotient.com/PrimLuecken/Max_Intervalle}.

\bibitem{ft}
R.~A.~Fisher and L.\,H.\,C.~Tippett, Limiting forms of the frequency distribution of 
the largest and smallest member of a sample, {\it Math.\ Proc.\ Cambridge\ Philos.\ Soc.} {\bf 24} (1928), 180--190.

\bibitem{forbes}
A.~D.~Forbes, Prime $k$-tuplets. Section 21:~List of all possible patterns of prime $k\mbox{-}$tuplets.
The Hardy-Littlewood constants pertaining to the distribution of prime $k\mbox{-}$tuplets, preprint, 2012.  Available at  \newline
\url{http://anthony.d.forbes.googlepages.com/ktuplets.htm}.

\bibitem{galambos}
J.~Galambos, {\it The Asymptotic Theory of Extreme Order Statistics}, Krieger, 1987. 

\bibitem{gnedenko}
B.~V. Gnedenko, Sur la distribution limite du terme maximum d'une s\'erie al\'eatoire. {\it Ann. Math.} {\bf 44} (1943), 423--453.
English translation: On the limiting distribution of the maximum term in a random series, in 
{\it Breakthroughs in Statistics}, Volume 1: 
{\it Foundations and Basic Theory.} Springer, 1993, pp.\,185--225.

\bibitem{gsw}
L.~Gordon, M.~F.~Schilling, and M.~S.~Waterman, An extreme value theory for long head runs. 
{\it Probab.\ Theory Related Fields} {\bf 72} (1986), 279--297.

\bibitem{granville}
A. Granville. Harald Cram\'er and the distribution of prime numbers. 
{\it Scand.\ Actuar.\ J.} {\bf 1} (1995), 12--28.

\bibitem{gumbel}
E.~J.~Gumbel, {\it Statistics of Extremes}, Columbia University Press, 1958. Dover, 2004.

\bibitem{hl}
G.~H.~Hardy and J.~E.~Littlewood, Some problems of `Partitio Numerorum.' III. 
on the expression of a number as a sum of primes. {\it Acta Math.} {\bf 44} (1922), 1--70.

\bibitem{hw} G.~H.~Hardy and E.~M.~Wright, 
{\it An Introduction to the Theory of Numbers}, 6th ed. Oxford University Press, 2008. 

\bibitem{hays}
W.~L.~Hays, {\it Statistics}, Harcourt Brace College Publishers, 1994.

\bibitem{kpII}
P.~F.~Kelly and T.~Pilling,
Implications of a new characterisation of the distribution of twin primes, preprint, 2001.  Available at
\url{http://arxiv.org/abs/math/0104205}.

\bibitem{kpIII}
P.~F.~Kelly and T.~Pilling,
Physically inspired analysis of prime number constellations, preprint, 2001.
Available at
\url{http://arxiv.org/abs/hep-th/0108241}.

\bibitem{maier}
H.~Maier, Primes in short intervals, {\it Michigan Math. J.} {\bf 32} (1985), 221--225.

\bibitem{mp}
H.~Maier and C.~Pomerance, Unusually large gaps between consecutive primes. 
{\it Trans.\ Amer.\ Math.\ Soc.} {\bf 322} (1990), 201--237. 

\bibitem{easyfit}
MathWave Technologies, {\it EasyFit --- Distribution Fitting Software}, company web site, 2012.  Available at \newline
\url{http://www.mathwave.com/easyfit-distribution-fitting.html}.

\bibitem{exceltrendline}
Microsoft Corporation, {\it Excel:~Add a Trendline to a Chart}, 
company web site, 2012.  Available at 
\url{http://tinyurl.com/7fllepq}.

\bibitem{nicely}
T.~R.~Nicely, List of prime gaps, preprint, 2012.
Available at \newline \url{http://www.trnicely.net/gaps/gaplist.html}.

\bibitem{cvc}
J.~Pintz, Cram\'er vs Cram\'er: On Cram\'er's probabilistic model of primes.
{\it Funct.\ Approx.\ Comment.\ Math.} {\bf 37} (2007), 361--376.

\bibitem{riesel}
H.~Riesel, {\it Prime Numbers and Computer Methods for Factorization}, Birkh\"auser, 1994. 

\bibitem{rr} 
L. Rodriguez and C. Rivera,
Conjecture 66. Gaps between consecutive twin prime pairs, 2009.
Available at
\url{http://www.primepuzzles.net/conjectures/conj_066.htm}.

\bibitem{schilling}
M. F. Schilling, The longest run of heads. {\it College Math. J.} {\bf 21} (1990), 196--207. 

\bibitem{shanks}
D.~Shanks, On maximal gaps between successive primes. {\it Math.\ Comp.} {\bf 18} (1964), 646--651. 

\bibitem{oeis}
N.~J.~A.~Sloane, {\it On-Line Encyclopedia of Integer Sequences}, 2012.
Available at \url{http://oeis.org}.

\bibitem{watson}
G.~S.~Watson, Extreme values in samples from $m$-dependent stationary stochastic processes.
{\it Ann.\ Math.\ Statist.} {\bf 25} (1954), 798--800.

\bibitem{wolf} 
M.~Wolf, Some heuristics on the gaps between consecutive primes,
preprint, 2011.  Available at 
\url{http://arxiv.org/abs/1102.0481}.

\bibitem{wolf2} 
M.~Wolf, Maximal gaps between twin primes $G_2(x)$ 
can be expressed in terms of $\pi_2(x)$.  Personal communication, 2013.
%
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11N05; Secondary 60G70.

\noindent \emph{Keywords: } 
distribution of primes, prime $k$-tuple, Hardy-Littlewood conjecture,
extreme value statistics, Gumbel distribution,
prime gap, Cram\'er conjecture, 
prime constellation, twin prime conjecture, prime quadruplet, prime sextuplet.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A005250},
\seqnum{A091592},
\seqnum{A113274},
\seqnum{A113404},
\seqnum{A192870},
\seqnum{A200503},
\seqnum{A201051},
\seqnum{A201062},
\seqnum{A201073},
\seqnum{A201251},
\seqnum{A201596},
\seqnum{A201598},
\seqnum{A202281}, and
\seqnum{A202361}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  January 22 2013;
revised version received  May 1 2013.
Published in {\it Journal of Integer Sequences}, May 9 2013.

\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>