0$,
while those below $a\log(p/a)$ are mapped to $g_k^* < 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<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 > 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 > 0$, there is always a prime between $n^2$ and $(n+1)^2$. ({\em Legendre})
\item For each integer $n > 122$, there are twin primes between $n^2$ and $(n+1)^2$. (\seqnum{A091592})
\item For each integer $n > 3113$, there is a prime triplet between $n^2$ and $(n+1)^2$.
\item For each integer $n > 719377$, there is a prime quadruplet between $n^2$ and $(n+1)^2$.
\item For each integer $n > 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 > 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 > 0$, there are twin primes between $n^3$ and $(n+1)^3$.
\item For each integer $n > 0$, there is a prime triplet between $n^4$ and $(n+1)^4$.
\item For each integer $n > 0$, there is a prime quadruplet between $n^5$ and $(n+1)^5$.
\item For each integer $n > 0$, there is a prime quintuplet between $n^6$ and $(n+1)^6$.
\item For each integer $n > 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 > n_0(k, r)$,
where $n_0(k,r)$ is a function of $k\ge1$ and $r > 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)