\section{Introduction \label{sec:intro}}

In the last 20 years experimentalists have provided precise data
for deuteron (d) breakup in the collision with a proton (p)
at energies up to pion production
threshold. Their motivation has been to look for regions of three-body
phase space where the results are sensitive to the nucleon-nucleon
(NN) interaction and the need to include a three-nucleon (3N)
force. Given that there are numerically exact 3N
calculations that include a wide variety of NN force models,
comparison between theoretical calculations and precise data sheds
light on the quality of the NN interactions that have been
proposed. Since all NN interactions are fitted to NN elastic
scattering data with equivalent $\chi^2$ precision, possible disagreements
may reside in the off-shell nature of the chosen NN interaction or the
need to add a 3N force. Unfortunately this quest has been, in a few
isolated cases such as the nucleon-deuteron analyzing power puzzle
\cite{kievsky:01a} or the space-star anomaly
\cite{strate:89,setze:05a,deltuva:05d},
overshadowed by persistent discrepancies between data
and theory that defy comprehension within the framework of
non-relativistic quantum mechanics applied to three interacting
nucleons alone.

Up to now very few breakup data exist involving four-nucleon
reactions,
though this system shows extra sensitivity to NN force
models as some calculations have already demonstrated
\cite{deltuva:07c,lazauskas:09a,viviani:13a}  for specific
spin observables and cross sections for elastic, charge exchange and
transfer reactions. Nevertheless  exact numerical four-nucleon
calculations for breakup amplitudes are still years away given the
dimensionality of the problem and the complex structure of
singularities above breakup. For elastic and transfer reactions driven
by all possible N+3N initial states as well as d+d,
 converged solutions for all two-body reactions up to 30 MeV beam
energy \cite{deltuva:14a,deltuva:15a,lazauskas:15a} are available.
 Going to higher energies is formally not an obstacle but
requires much more computer power to obtain fully converged results
in terms of number of partial waves and grid points.  On the other
hand, the existing d+d breakup measurement
 \cite{ramazani:phd,dd3bkvi,PhysRevC.83.024002}
performed at 130 MeV deuteron beam energy has provided fully
exclusive cross sections that are about three orders of magnitude smaller
than for the p+d breakup at comparable energies. This is
puzzling because one would expect a similar order of magnitude
for p+d and d+d  total breakup cross sections.
According to recent calculations, albeit at the much lower energy of 10 MeV
 \cite{deltuva:15a}, this is indeed the case.

Therefore, in order to provide the first estimate of d+d breakup cross
sections at higher energies, we present here an approximate calculation based on
the lowest-order term
in the Neumann series expansion of the Alt, Grassberger and Sandhas
(AGS) equations \cite{grassberger:67}
 for the breakup operator and called single-scattering approximation (SSA).
 The SSA contains the breakup of one of the deuterons followed by the
scattering of one nucleon from the other deuteron through the full 3N
operator that sums up all orders of NN rescattering involving the
corresponding three particles. This operator is obtained from the exact
solution of the AGS three-nucleon equations for the underlying
force model being used. As demonstrated before \cite{dd232}, the same kind of approximation
 may be used to calculate d+d elastic scattering at high energies.
In order to obtain a quantitative calibration of the d+d breakup cross sections,
we provide SSA results also for d+d elastic scattering observables.

SSA for three-cluster breakup calculations is expected
to be reasonable near quasi-free
scattering (QFS) kinematics at energies  above 100 MeV in the
center-of-mass (c.m.) system. This conjecture is supported
 by the results for the equivalent
approximation applied to p+d breakup where a comparison with the exact
results that include NN rescattering to all orders is possible.

In Section II we present the theory for the breakup amplitudes using
the first term in the Neumann series expansion of the AGS equations,
and study the equivalent approximation applied to
p+d breakup by comparing such results with those obtained from the
exact solution of
the corresponding 3N problem. In Section III we show the results for
d+d elastic scattering and three-cluster breakup near  the quasi-free scattering kinematics.
 Conclusions come in Section IV.

\section{Scattering amplitudes \label{sec:eq}}

We start with exact four-nucleon scattering equations  and
transition amplitudes, and then show how they are simplified
under the single scattering approximation.
Treating nucleons as identical fermions in the isospin formalism,
one has to consider only two two-cluster partitions, namely,
 $3+1$ and $2+2$ which in the notation for operators and wave-functions
  are abbreviated by 1 and 2, respectively.
In terms of four particles 1,2,3, and 4 they correspond to the clustering
(12,3)4 and (12)(34), respectively. The reactions initiated by
the collisions of two deuterons
are described by the four-nucleon transition operators
 $\mcu_{\beta 2}$ obeying the symmetrized AGS equations
\begin{subequations}  \label{eq:AGS}
\begin{align}
\mcu_{12}  = {}&  (G_0 \, t \, G_0)^{-1} -
P_{34} U_1 G_0 \, t \, G_0 \, \mcu_{12}
+ U_2   G_0 \, t \, G_0 \, \mcu_{22}, \label{eq:U11}  \\
\label{eq:U21}
\mcu_{22} = {}&  (1 - P_{34}) U_1 G_0 \, t \, G_0 \, \mcu_{12}.
\end{align}
\end{subequations}
The pair potential $v$ enters the AGS equations via the
pair (12) transition matrix
\begin{gather} \label{eq:t}
t = v + v G_0 t
\end{gather}
and via the  3+1 and 2+2 subsystem transition operators
\begin{gather} \label{eq:AGSsub}
U_\alpha =  P_\alpha G_0^{-1} + P_\alpha t\, G_0 \, U_\alpha.
\end{gather}
The dependence of all transition operators on the available energy $E$,
although not indicated in our notation, arises via the free resolvent
\begin{gather}\label{eq:G0}
G_0 = (E +i0 - H_0)^{-1}
\end{gather}
where  $H_0$ is the  free Hamiltonian.
In the considered case $E = p_2^2/2m_N + 2 \epsilon_d$, where
$p_2$ is the relative $d\text{-}d$ momentum, $m_N$ the average nucleon mass,
 and $\epsilon_d = -2.225$ MeV the energy of the deuteron bound state.
The full antisymmetry that a system of four identical fermions must obey is ensured by the
permutation operators $P_{ab}$ of nucleons $a$ and $b$ with
$P_1 =  P_{12}\, P_{23} + P_{13}\, P_{23}$ and $P_2 =  P_{13}\, P_{24}$.
Furthermore,
the basis states are antisymmetric under exchange of the two nucleons
(12) while in the $2+2$ partition they are antisymmetric
also  under exchange of the two nucleons (34).

The three-cluster breakup operator for the $2+2$ collision is derived in
Ref.~\cite{deltuva:12e} to be
\begin{equation} \label{eq:U3}
\mcu_{32} = (1- P_{34}) U_1 G_0 \, t \, G_0 \, \mcu_{12} +
U_2 G_0 \,  t \, G_0 \, \mcu_{22} .
\end{equation}

To get the reaction amplitudes the on-shell matrix elements of
the above transition operators have to be calculated between the appropriate
channel states. Considering
only the elastic $d\text{-}d$ scattering and three-cluster breakup,
the respective channel states are
 $| \Phi_{2}(\mbf{p}_2) \rangle = | \phi_{d}  \phi_{d}  \mbf{p}_2 \rangle =
(1+P_2)| \phi_{2}(\mbf{p}_2) \rangle$
with the Faddeev component
$|\phi_{2}(\mbf{p}_2) \rangle = G_0 v | \Phi_{2}(\mbf{p}_2) \rangle =
G_0 t P_2 |\phi_{2} (\mbf{p}_2) \rangle$,
and  $| \Phi_{3}(\mbf{k}_y,\mbf{k}_z) \rangle =
| \phi_{d} \mbf{k}_y  \mbf{k}_z \rangle$.
Here $ \phi_{d}$ denotes the deuteron wave function,
$\mbf{p}_2$ is the relative $d\text{-}d$ momentum, and
$\mbf{k}_y$ and $\mbf{k}_z$ are  momenta for the relative motion
in the three-cluster $d+p+n$ system, e.g.,
$\mbf{k}_y = (2\mbf{k}_p-\mbf{k}_d)/3$ and
$\mbf{k}_z= (3\mbf{k}_n-\mbf{k}_p-\mbf{k}_d)/4$
for the $(dp)n$ partition.
 The dependence on the
discrete spin and isospin quantum numbers is suppressed in our notation.
The elastic and three-cluster breakup amplitudes are
\begin{subequations}  \label{eq:ampl}
\begin{align}
\langle \mbf{p}'_2 | \mct_{22} | \mbf{p}_2 \rangle
= {}& 2 \langle \phi_{2}(\mbf{p}'_2)| \mcu_{22} | \phi_{2}(\mbf{p}_2) \rangle, \\
\langle \mbf{k}_y\mbf{k}_z |\mct_{32} | \mbf{p}_2 \rangle
= {}& 2 \langle \Phi_{3}(\mbf{k}_y,\mbf{k}_z)|\mcu_{32}
| \phi_{2}(\mbf{p}_2) \rangle.
\end{align}
\end{subequations}
Factors of 2 result from the antisymmetrization
of the four-nucleon states \cite{deltuva:12e}; to account for the
identity of the two deuterons one has to use  symmetrized
$d\text{-}d$ channel states, leading to symmetrized amplitudes
obtained from \eqref{eq:ampl}   by replacing
$| \phi_{2}(\mbf{p}_2) \rangle$ with
$ | \phi_{2}^s(\mbf{p}_2) \rangle =
 \frac{1}{\sqrt{2}}(1+P_2) | \phi_{2}(\mbf{p}_2) \rangle
= \frac{1}{\sqrt{2}} [| \phi_{2}(\mbf{p}_2) \rangle + | \phi_{2}^x(-\mbf{p}_2) \rangle] $
where the superscript $x$ indicates that also the spin-isospin part
is exchanged. Note that in the partial-wave representation
both terms have equal contributions.

The absence of an inhomogeneous term in the equation \eqref{eq:U21} makes possible the
development of a simple approximation for d+d elastic scattering and
three-cluster breakup that may
work at higher energies under certain conditions. In the single-scattering
approximation  only the terms that are of
first order in the subsystem transition operators $U_\alpha$
are retained, resulting in the amplitudes
\begin{subequations}  \label{eq:ssa}
\begin{align}   \label{eq:ssa-a}
\langle \mbf{p}'_2 | \mct_{22}^{\rm SS} | \mbf{p}_2 \rangle
= {}& 2  \langle \phi_{2}^s(\mbf{p}'_2)| (1 - P_{34}) U_1
 | \phi_{2}^s(\mbf{p}_2) \rangle, \\ \label{eq:ssa-b}
\langle \mbf{k}_y\mbf{k}_z | \mct_{32}^{\rm SS} | \mbf{p}_2 \rangle
= {}& 2 \langle \Phi_{3}(\mbf{k}_y,\mbf{k}_z)| (1 - P_{34}) U_1
| \phi_{2}^s(\mbf{p}_2) \rangle.
\end{align}
\end{subequations}
Thus, only the calculation of the operator $U_1$ is required,
which is the standard three-nucleon AGS transition matrix.
However, it needs to be calculated at off-shell momenta
as we show below.
Given that
$|\phi_{2}(\mbf{p}_2) \rangle = G_0 v | \phi_{d}  \phi_{d}  \mbf{p}_2 \rangle $,
it is convenient to introduce the momentum-space matrix elements
\begin{equation} \label{eq:U1yz}
\langle  \phi_{d} \mbf{k}_y\mbf{k}_z | v G_0 U_1 G_0 v |
 \phi_{d} \mbf{k}'_y\mbf{k}'_z  \rangle =
\delta(\mbf{k}_z - \mbf{k}'_z) \baru(\mbf{k}_y,\mbf{k}'_y,{k}_z)
\end{equation}
and the deuteron wave function $\phi_{d}(\mbf{p}_y)= \langle \mbf{p}_y | \phi_{d} \rangle$;
they are  operators in the spin-isospin space.
With these definitions the first contribution to the symmetrized SSA elastic
amplitude \eqref{eq:ssa} is calculated as
\begin{gather}\label{eq:sse}
\begin{split}
\langle \phi_{2}(\mbf{p}'_2){}& | (1 -  P_{34}) U_1
 | \phi_{2}(\mbf{p}_2) \rangle \\ &
=  2 \int d^3 \mbf{k}_z \phi_{d}(\mbf{p}'_y) \baru(\mbf{k}_y,\mbf{k}'_y,{k}_z) \phi_{d}(\mbf{p}_y)
\end{split}
\end{gather}
with
\begin{subequations}  \label{eq:ssep}
\begin{align}
\mbf{p}'_y = {}& \frac12 \mbf{p}'_2 - \mbf{k}_z, \\
\mbf{p}_y = {}& \frac12 \mbf{p}_2 - \mbf{k}_z, \\
\mbf{k}'_y = {}& \mbf{p}_2 - \frac23 \mbf{k}_z, \\
\mbf{k}_y = {}& \mbf{p}'_2 - \frac23 \mbf{k}_z.
\end{align}
\end{subequations}
The remaining three contributions are calculated analogously.
In Eq.~\eqref{eq:sse} the energy available for the three-nucleon subsystem
$E- 2k_z^2/3m_N$ runs from $E$ to $-\infty$, obviously indicating
that $U_1$ is needed off-shell. On the other
hand, the final breakup channel state
$| \Phi_{3}(\mbf{k}_y,\mbf{k}_z) \rangle$
fulfills the on-shell condition $E = \epsilon_d + 3k_y^2/4m_N + 2k_z^2/3m_N$,
indicating that only half-shell elements of  $U_1$ are needed.
Thus,  the first term of the single-scattering breakup
amplitude \eqref{eq:ssa-b}  becomes
\begin{gather}\label{eq:ssb}
\langle \Phi_{3}(\mbf{k}_y,\mbf{k}_z)|  U_1
| \phi_{2}(\mbf{p}_2) \rangle=
 \baru(\mbf{k}_y,\mbf{k}'_y,{k}_z) \phi_{d}(\mbf{p}_y)
\end{gather}
with $\mbf{k}'_y$ and $\mbf{p}_y$ defined in Eqs.~\eqref{eq:ssep}.
The second term is calculated analogously, but with the final state
$P_{34}| \Phi_{3}(\mbf{k}_y,\mbf{k}_z) \rangle =
|\Phi^x_{3}(\frac13 \mbf{k}_y+ \frac89 \mbf{k}_z,\mbf{k}_y - \frac13 \mbf{k}_z) \rangle  $
where the superscript $x$ indicates that also the spin-isospin part
is exchanged.
These two contributions are graphically depicted in
Fig.~\ref{fig:u} for the $d+p+n$ final state.
Taking the left-side deuteron as the beam and the right-side deuteron
as the target, the diagram (a) corresponds to the target
deuteron breakup after the
full interaction between the impinging deuteron and the target proton
while no interaction occurs involving the target neutron.
Thus, the diagram (a) corresponds to proton-deuteron
quasi-free scattering (QFS).
Analogously, the diagram (b) corresponds to neutron-deuteron QFS.
Two more contributions
$\langle \Phi_{3}(\mbf{k}_y,\mbf{k}_z)| (1-P_{34}) U_1| \phi_{2}^x(-\mbf{p}_2) \rangle$,
not shown in Fig.~\ref{fig:u},
 arise due to the symmetrization of the initial
$d+d$ state; they correspond to the breakup of the impinging deuteron.

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.62]{u.eps}
\end{center}
\caption{ \label{fig:u} (Color online)
Two contributions to the single-scattering three-cluster
breakup amplitude. The three-nucleon transition operator $U_1$
is represented by a box while deuterons
are represented by filled arcs. }
\end{figure}

Under the assumption of the simplified SSA reaction
mechanism of Fig.~\ref{fig:u} (a),
the energy distribution of the final neutron is given by the
deuteron wave function, i.e., the differential cross section is sharply peaked at the neutron
energy $E_n = 0$. In a complete reaction picture the  cross section
 also gets contributions from the higher rescattering terms beyond the SSA; roughly,
their relative importance increases when the SSA contribution decreases, i.e.,
for larger $E_n$. Thus, the reliability of the SSA should decrease with
increasing energy of the final neutron.
 Another necessary condition for the non-interacting neutron, and thereby
also for the validity of the SSA,
is a high enough relative $n$-$d$ and $n$-$p$ energy, implying
also high enough energy for the initial beam and for the final deuteron and proton.
At  $E_n = 0$ only the contribution of Fig.~\ref{fig:u} (a)
is peaked; the remaining three SSA contributions are not as they
do not correspond to the deuteron-proton(target) QFS.
In the following we will call the results obtained with only
the contribution of Fig.~\ref{fig:u} (a) as SSA-1, while those
including all four contributions as SSA-4. An agreement between the
SSA-1 and  SSA-4 results indicates the dominance of the Fig.~\ref{fig:u} (a)
SSA reaction mechanism,  while  disagreement indicates a more complicate reaction
mechanism; a significant contribution of higher-order terms
is probable in the latter case although it cannot be ruled out also in the former case.

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.62]{ss3-95.eps}
\end{center}
\caption{ \label{fig:ss3-95} (Color online)
Differential cross section for the proton deuteron breakup
at 95  MeV proton beam energy as function of the arclength $S$
along the kinematical curve. The polar angles of the  two detected protons
$(\theta_1,\theta_2)$ are indicated in the plots.
Exact results based on the CD Bonn + $\Delta$ potential
and including the Coulomb interaction (solid curves) are compared
with SSA results (dashed-dotted curves) that neglect the Coulomb interaction.
The final neutron energy is given by dotted curves. }
\end{figure}

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.62]{ss3-200.eps}
\end{center}
\caption{ \label{fig:ss3-200} (Color online)
Same as Fig.~\ref{fig:ss3-95} but
at 200  MeV proton beam energy.}
\end{figure}

Finally we note that the corresponding SSA can be introduced also in the
nucleon-deuteron scattering, expanding the three-nucleon transition operators in terms
of two-nucleon transition operators $t$ and retaining first order terms in the Neumann series.
 In fact, this approach already has been used in a number
of early works, e.g. \cite{fukehara:79}.
The full nucleon-deuteron  breakup operator is
\begin{gather} \label{eq:U0}
U_0 =  (1+P_1) t\, G_0 \, U_1
\end{gather}
whereas its SSA reads
\begin{gather} \label{eq:U0ssa}
U_0^{\rm SS} =  (1+P_1) t\, P_1.
\end{gather}
The diagrammatic representation of the nucleon-deuteron SSA is
very similar to the one of Fig.~\ref{fig:u} except that the
left-side deuteron is replaced by a nucleon and the three-nucleon
transition operator $U_1$ is replaced by the two-nucleon operator $t$.

Comparing results based on Eqs.~\eqref{eq:U0} and \eqref{eq:U0ssa}
one can evaluate the reliability of the SSA in three-nucleon breakup.
This is done in Figs.~\ref{fig:ss3-95} and \ref{fig:ss3-200}
for proton-deuteron breakup at
95 and 200 MeV proton beam energy in several kinematical configurations.
The above energy values approximately correspond to the same c.m. energy as
130 and 270 MeV deuteron  energy in deuteron-deuteron collisions.
The fivefold differential cross section
$d^5\sigma/d\Omega_1 d\Omega_2 dS$ is shown as a function of the arclength $S$
along the kinematical curve
for fixed angles of the two detected protons $(\theta_1,\varphi_1=0^\circ)$
and $(\theta_2,\varphi_2=180^\circ)$. The energy of the neutron $E_n$ is plotted
as well. One can see that the SSA results deviate significantly
from the exact ones for larger $E_n$ values; for small $E_n$ well below 1 MeV
the agreement improves for higher  proton beam energy.

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.56]{dd232.eps}
\end{center}
\caption{ \label{fig:dd232} (Color online)
Differential cross section and deuteron analyzing powers
for the deuteron-deuteron elastic scattering
at 232  MeV deuteron beam energy.
SSA predictions based on the CD Bonn + $\Delta$ (solid curves),
CD Bonn (dashed-dotted curves), and AV18  (dotted curves)
potentials are compared with experimental data from
Ref.~\cite{dd232}. }
\end{figure}

Total p+d breakup cross sections calculated exactly and in the SSA are
69.1 and 109 mb at 95 MeV and 49.7 and 63.5 mb at 200 MeV, respectively.
Thus, SSA provides a correct order of the magnitude
for the p+d total  breakup cross section.

\section{Results \label{sec:res}}

\begin{figure*}[!]
\begin{center}
\includegraphics[scale=0.7]{dd130s.eps}
\end{center}
\caption{ \label{fig:dd130} (Color online)
Differential cross section for the three-cluster breakup
in deuteron-deuteron collision
at 130  MeV deuteron beam energy as function of the arclength $S$
along the kinematical curve. The polar angles of the detected deuteron and proton
$(\theta_d,\theta_p)$ are indicated in the plots, the azimuthal angles
are $(\varphi_d,\varphi_p) = (0^\circ,180^\circ)$.
SSA 4-term (solid curves) and 1-term (dashed-dotted curves)
results, both based on the CD Bonn + $\Delta$ potential, are compared.
Published experimental data from Ref.~\cite{dd3bkvi}
are only available for the configuration $(15^\circ,15^\circ)$;
in the plot the data points are multiplied by a factor of $10^3$.
The final neutron energy is given by  dotted curves. }
\end{figure*}

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.66]{dd130t11.eps}
\end{center}
\caption{ \label{fig:t11} (Color online)
Deuteron analyzing power $iT_{11}$ for the three-cluster breakup
in deuteron-deuteron collision at 130  MeV deuteron beam energy.
 The polar angles of the detected deuteron and proton
$(\theta_d,\theta_p)$ are indicated in the plots.
SSA 4-term (solid curves) and 1-term (dashed-dotted curves)
results, both based on the CD Bonn + $\Delta$ potential, are compared
with the experimental data from Refs.~\cite{PhysRevC.83.024002,ramazani:phd}.
 }
\end{figure}

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.66]{dd130t20.eps}
\end{center}
\caption{ \label{fig:t20} (Color online)
Deuteron tensor analyzing power $T_{20}$ for the three-cluster breakup
in deuteron-deuteron collision at 130  MeV deuteron beam energy.
Curves and experimental data are as in Fig.~\ref{fig:t11}.}
\end{figure}

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.66]{dd130t22.eps}
\end{center}
\caption{ \label{fig:t22} (Color online)
Deuteron tensor analyzing power $T_{22}$ for the three-cluster breakup
in deuteron-deuteron collision at 130  MeV deuteron beam energy.
Curves and experimental data are as in Fig.~\ref{fig:t11}.}
\end{figure}

\begin{figure}[!]
\begin{center}
\includegraphics[scale=0.6]{dd270v.eps}
\end{center}
\caption{ \label{fig:dd270v} (Color online)
Differential cross section for the three-cluster breakup
in deuteron-deuteron collision
at 270  MeV deuteron beam energy.  The polar angles of the detected deuteron and proton
$(\theta_d,\theta_p)$ are indicated in the plots.
SSA-4 based on the CD Bonn + $\Delta$ (solid curves),
CD Bonn (dashed-dotted curves), and AV18  (dotted curves)
potentials are compared with the  SSA-1 predictions
 based on the CD Bonn + $\Delta$ potential (thin solid curves).
The final neutron energy is given by dashed curves. }
\end{figure}

We use three models of  realistic high-precision
two-nucleon potentials, namely,
the Argonne 18-operator (AV18) potential  \cite{wiringa:95a},
the charge-dependent Bonn potential (CD Bonn)  \cite{machleidt:01a},
and its extension CD Bonn + $\Delta$ \cite{deltuva:03c}
allowing for an excitation of a nucleon to a $\Delta$ isobar
and thereby yielding an effective 3N force.

The three-nucleon AGS equation \eqref{eq:AGSsub} is solved in the
momentum-space partial-wave representation.
The states with two-nucleon angular momenta $j_x  \le 5$ and
 three-nucleon angular momenta $j_y  \le \frac{27}{2}$ are included.
The final four-nucleon results are well converged with these cutoffs.
The elastic amplitude \eqref{eq:ssa-a} is calculated in partial waves
including the states with 4N total angular momentum $J \le 25$ while
for the breakup amplitude
the obtained partial-wave half-shell matrix elements of $U_1$ are first transformed into
the plane-wave basis and then used in Eq.~\eqref{eq:ssa-b}.
The Coulomb interaction is neglected
when solving AGS equation \eqref{eq:AGSsub} for the 3N transition operator $U_1$.
However, the external Coulomb correction is added to the
elastic amplitude \eqref{eq:ssa-a}.

We first present results for d+d elastic observables at 232 MeV
beam energy where the experimental data \cite{dd232} for the differential cross section
and analyzing powers are available. The SSA results based on Eq.~\eqref{eq:ssa-a}
 are shown in Fig.~\ref{fig:dd232}  for CD Bonn + $\Delta$, CD Bonn and AV18
potentials. The sensitivity to the force model is visible for the tensor analyzing powers
$T_{20}$ and $T_{22}$. The observables are reasonably described at forward scattering angles
$\Theta_{\mathrm{c\!\:\!.m\!\:\!.}} \le 40^\circ$ in the c.m. frame.
At larger scattering angles multiple scattering effects are expected, thus,
the failure of SSA is not surprising.
For the vector analyzing
 power $iT_{11}$ a rough agreement between SSA results and experimental data
is seen also at larger angles. Since the
calculation of the d+d elastic amplitude involves the integration of
the N+d off-shell amplitude over the 3N subsystem energy range from $E$ to $-\infty$, it is
reasonable to assume that the SSA for the d+d breakup may have the correct
order of magnitude over a wide range of phase space. Therefore we
expect our SSA results to provide at least the
correct order of magnitude for the d+d three-cluster breakup cross sections.

The fivefold differential cross section for the three-cluster breakup in the laboratory frame
\begin{gather}\label{eq:d5S}
\begin{split}
   \frac{d^5 \sigma}{d\Omega_d d\Omega_p dS} = {}& (2 \pi)^{4}  \frac{ m_N }{p_2}
   \big | \langle \mbf{k}_y\mbf{k}_z | \mct_{32}^{\rm SS} | \mbf{p}_2 \rangle \big |^2  \,
   m_N^2  k_d^2  k_p^2   \\ & \times
    \Big \{ (k_d/2)^2 \big[ 2k_p  - \hv{k}_p \cdot (2\mbf{p}_2  \!-\! \mbf{k}_d) \big]^2 \\ & +
k_p^2 \big[ 3k_d/2  - \hv{k}_d \cdot (2\mbf{p}_2  \!-\! \mbf{k}_p) \big]^2   \Big \}^{-1/2}.
  \end{split}
\end{gather}
is calculated as a function of the arclength $S$
along the kinematical curve in the plane of final deuteron and proton energies
$E_d$ and $E_p$
for fixed polar and azimuthal angles of the deuteron  $(\theta_d,\varphi_d=0^\circ)$
and proton $(\theta_p,\varphi_d=180^\circ)$. The starting point $S=0$
 is chosen as  $E_p = 0$ with $dE_p/dE_d > 0$ and $S$ is measured counterclockwise
in the $(E_d,E_p)$ plane.

The spin-averaged differential cross section for
six angular configurations is shown in Fig.~\ref{fig:dd130}, together with the
energy $E_n$ of the final-state neutron; the CD Bonn + $\Delta$ model is used.
This observable in peaked at the minimum of $E_n$,
i.e., near/at deuteron-proton QFS kinematics. The SSA-1 and SSA-4 predictions
approach each other for small  $E_n$ and deviate at larger $E_n$.
The experimental data \cite{ramazani:phd}  taken at KVI are preliminary and cannot be shown
here except for the configuration  $(\theta_d,\theta_p) = (15^\circ,15^\circ)$ already
published in Ref.~\cite{dd3bkvi}. The disagreement between our predictions and data
exceeds a factor of 1000 which is striking. In fact,  when compared to the
data \cite{ramazani:phd}, a  similar discrepancy of three orders
of magnitude  exists for all remaining configurations in Fig.~\ref{fig:dd130}.
Such a difference is far too large even taking into account that
our predictions are approximate. On the other hand, using SSA we predict the same order of magnitude
for the differential cross section in nucleon-deuteron and deuteron-deuteron three-cluster breakup.
This applies also to the total three-cluster breakup cross section. Using
SSA-4 with the CD Bonn + $\Delta$ potential we obtain
 189 and 57 mb at 130 and 270 MeV, respectively, which are comparable to the ones
in nucleon-deuteron breakup. Since in the nucleon-deuteron breakup the SSA provides the right order
of magnitude for both differential and total cross sections, we believe that our
predictions for the deuteron-deuteron three-cluster breakup are reasonable as well and point out
to problems in the experimental data of Ref.~\cite{ramazani:phd}.
These conclusions are supported by very recent measurements of this reaction
at 160 MeV deuteron beam energy where our differential cross section predictions
near QFS kinematics are in qualitative
agreement with the preliminary experimental data  \cite{khatri:phd}.

Deuteron vector  analyzing power $iT_{11}$ and
tensor analyzing powers $T_{20}$ and $T_{22}$ are shown in Figs.~\ref{fig:t11} --- \ref{fig:t22}
for several kinematic $(\theta_d,\theta_p)$ configurations. The experimental data points for two of them,
$(15^\circ,15^\circ)$ and $(25^\circ,25^\circ)$,
are taken from Ref.~\cite{PhysRevC.83.024002}, others are still preliminary and
only available in Ref.~\cite{ramazani:phd}.
There is a rough qualitative agreement between the data and SSA-1 and SSA-4 predictions
for $(15^\circ,15^\circ)$ and $(25^\circ,20^\circ)$ configurations.
The data change very rapidly from $(25^\circ,20^\circ)$ to $(25^\circ,25^\circ)$, loosing the
agreement with SSA results. Comparing  SSA-1 and SSA-4 predictions one may conclude
that the level of agreement between SSA-1 and SSA-4 is not the same
 for the spin-averaged differential cross section and for spin observables.
The sensitivity of all these observables to the force model is minor and it is not shown.

Although no experimental data is available above 160 MeV, we present in Fig.~\ref{fig:dd270v} example
results at 270 MeV deuteron beam energy where the sensitivity to the force model becomes more visible.
Under suitable kinematic conditions, e.g., in the $(28^\circ,25^\circ)$ configuration,
this sensitivity even exceeds the  difference between SSA-1 and SSA-4.
Nevertheless it is plausible that this extra sensitiveness may change when exact calculations are performed.

\section{Summary \label{sec:sum}}

In the present work we have calculated the spin-averaged fivefold differential cross section
and deuteron analyzing powers for the three-cluster breakup in deuteron-deuteron
collisions at 130 and 270 MeV beam energy.
Although at this time we
could not perform an exact four-nucleon calculation of the corresponding
breakup amplitudes, we devised an approximation
based on the first term in the Neumann series expansion of the AGS
three-cluster breakup operator which is expected to be, qualitatively, a reasonable
approximation near proton-deuteron quasifree scattering kinematic conditions.

In order to validate the method, we calculated proton-deuteron breakup at similar
energies and compared with the results of an exact three-nucleon
calculation. Likewise we used the same single scattering approximation
to calculate deuteron-deuteron elastic scattering at 232 MeV where there is data for
the differential cross section and analyzing powers. These auxiliary studies have shown that the
SSA  reproduces, if nothing else, the correct magnitude
of the existing cross section data.

Although the deuteron beam energy of 130 MeV seems to be not high enough for
SSA to be reliable,  we compared
the SSA results for the three-cluster breakup
with the experimental data measured at KVI \cite{ramazani:phd,dd3bkvi,PhysRevC.83.024002}.
We found, at least in some configurations, a rough qualitative agreement
for deuteron analyzing powers, but a factor of 1000 difference for the cross section.
Since we have provided convincing arguments that SSA should yield at least correct order of
magnitude for total and differential cross sections, and that deuteron-deuteron and proton-deuteron
breakup cross sections should be of comparable size, our work raises some serious concern
on the correct normalization of the KVI data. On the contrary, new  Cracow
data \cite{khatri:phd} at 160 MeV seems to be in line with our SSA results.
Further investigation on these issues needs to be
pursued by both theory and experimental collaborations.

\vspace{3mm}

We thank A. Ramazani-Moghaddam-Arani and N. Kalantar-Nayestanaki for discussions and  providing
the experimental data.


\section{Introduction}

In his study about the existence of clines in genetics, Nagylaki \cite{nagy} considered
a partial differential equation in space and time satisfied by the gene frequency in a
monoecious population distributed continuously over an arbitrary habitat. Nagylaki \cite{nagy}
showed that this partial differential equation reduces to the simplest multidimensional
generalization of the classical Fisher-Haldane
cline model, and he investigated the efficacy of migration and selection in maintaining genetic
variability at equilibrium in this model by deducing conditions
for the existence of clines under various circumstances. The boundary value problem
considered by Nagylaki reads as follows
\begin{equation}\label{eqnagy}
\Delta p+\lambda^2g(r)p=0,
\end{equation}
where $p'(0)=0$ and $p(\infty)<\infty,$ $\Delta p$ is the $n$-dimensional Laplacian,
$r$ is the distance from the origin of an $n$-dimensional vector $x,$ and
$$g(r)=\left\{\begin{array}{ll}1,& r\in[0,1]\\-\alpha^2,& r>1\end{array}\right. .$$
Nagylaki \cite{nagy} conjectured that for each $\alpha>0$ fixed the smallest positive eigenvalues
of the above boundary value problem increase with the dimension. Motivated by Nagylaki's investigation,
Ismail and Muldoon \cite{ismail} considered the radial part of the boundary value problem \eqref{eqnagy}, that is,
\begin{equation}\label{eqism}
-(ry'(r))'+\nu^2r^{-1}y(r)=\lambda^2rg(r)y(r),
\end{equation}
where $p'(0)=0,$ $p(\infty)<\infty,$ $y(r)=r^{\nu}p(r)$ and $\nu={n}/{2}-1,$ and they showed that the positive eigenvalues of \eqref{eqism}
are the positive zeros of fixed rank of the cross-product $$J_{\nu+1}(r)K_{\nu}(\alpha r)-\alpha K_{\nu+1}(\alpha r)J_{\nu}(r),$$ where $J_{\nu}$
is the Bessel function of the first kind, while $K_{\nu}$ stands for the modified Bessel function of the second kind. Moreover, motivated by Askey's claim, Ismail and Muldoon \cite{ismail} proved that the positive zeros of the cross-product $$J_{\nu+\beta}(r)K_{\nu}(\alpha r)-\alpha^{\beta} K_{\nu+\beta}(\alpha r)J_{\nu}(r)$$
are increasing with respect to $\nu$ on $[-\beta/2,\infty),$ where $\beta\in(0,1].$ Thus, it is clear that Nagylaki's conjecture follows from the case $\beta=1$ of the above result. In \cite{ismail} the authors actually stated more: they showed that the expression $\alpha r$ in the above affirmation can be changed to any strictly increasing differentiable function on $(0,\infty)$ and instead of $\alpha^{\beta}$ it can be taken an arbitrary positive constant. Motivated by the importance of the boundary value problem \eqref{eqnagy} and its radial part \eqref{eqism} in the existence of clines, and by following the suggestion of Ismail, in this note our aim is to show that Nagylaki's claim on the positive eigenvalues will be also true if we consider a more general setting, that is, if we change the Bessel function of the first kind to the regular Coulomb wave function, and the modified Bessel function of the second kind to Tricomi hypergeometric function of the second kind. This is actually a generalization of the problem considered by Nagylaki. For more details on the special functions appearing in this paper we refer to \cite{nist}.

\section{The eigenvalue problem related to Coulomb and Tricomi functions}
\setcounter{equation}{0}

In order to extend Nagylaki's problem we consider the next boundary value problem
\begin{equation}\label{eqnew}
\Delta p+\varphi_{\lambda}(r)r^{-2}p=0,
\end{equation}
where $p'(0)=0$ and $p(\infty)<\infty,$
$$\varphi_{\lambda}(r)=L(L-1)+\lambda^2r^2g(r)-2\eta\lambda rh(r),$$
$L=(n-1)/2,$ $\eta$ is a real parameter, and
$$h(r)=\left\{\begin{array}{ll}1,& r\in[0,1]\\\alpha,& r>1\end{array}\right. .$$
It can be shown that the radial part of the above boundary value problem \eqref{eqnew} is
\begin{equation}\label{radnew}
r^2y''(r)+\left(\lambda^2r^2g(r)-2\eta\lambda rh(r)-L(L+1)\right)y(r)=0,
\end{equation}
where $p'(0)=0,$ $p(\infty)<\infty$ and $y(r)=r^{L}p(r).$ Now, if we suppose that $r\in(0,1],$ then we arrive at
$$r^2y''(r)+\left(\lambda^2r^2-2\eta\lambda r-L(L+1)\right)y(r)=0.$$ By using the change of variable $u=\lambda r$ (and taking $y(r)=z(u)$), the above equation becomes the Coulomb wave equation
$$u^2z''(u)+\left(u^2-2\eta u-L(L+1)\right)z(u)=0.$$
Moreover, when $r>1$ the equation \eqref{radnew} becomes
$$r^2y''(r)-\left(\alpha^2\lambda^2r^2+2\eta\alpha\lambda r-L(L+1)\right)y(r)=0,$$
which after the change of variable $v=\alpha\lambda r$ (and taking $y(r)=q(v)$) becomes a transformation of the Kummer confluent hypergeometric
differential equation
$$v^2q''(v)-\left(v^2+2\eta v+L(L+1)\right)q(v)=0.$$
Thus, when $r\in(0,1]$ the differential equation \eqref{radnew} has as particular solution the regular Coulomb wave function $$y(r)=A\cdot F_{L}(\eta,u),$$ where $A$ is a real constant, while for $r>1$ the equation \eqref{radnew} has the particular solution a transformation of the Tricomi hypergeometric function $$y(r)=B\cdot v^{L+1}e^{-v}\psi(L+\eta+1,2L+2,2v),$$ where $B$ is a real constant. It is important to mention here that when $\eta=0$ the above particular solutions reduce to $$y(r)=A\cdot \sqrt{\frac{\pi}{2u}}J_{L+\frac{1}{2}}(u)\ \ \mbox{and}\ \  y(r)=B\cdot 2^{-L}\sqrt{\frac{2v}{\pi}}K_{L+\frac{1}{2}}(v),$$ which show that the boundary value problem \eqref{eqnew} is a natural extension of \eqref{eqnagy}, while \eqref{radnew} is a natural extension of \eqref{eqism}.

Now, we are ready to state the main result of this paper.

\begin{theorem}\label{the1}
The following assertions are valid:
\begin{enumerate}

\item[\bf a.] The boundary value problem \eqref{radnew} has for its eigenvalues the zeros of the cross-product of regular Coulomb wave and Tricomi hypergeometric functions $$F_{L}'(\eta,r)Q_{L}(\eta,\alpha r)-\alpha Q_{L}'(\eta,\alpha r)F_{L}(\eta,r)$$ and corresponding eigenfunctions
$$r\mapsto \Theta_{L}(\eta,r)=\left\{\begin{array}{ll}Q_{L}(\eta,\alpha\lambda)\cdot F_{L}(\eta,\lambda r),& r\in(0,1]\\
F_{L}(\eta,\lambda)\cdot Q_L(\eta,\alpha\lambda r),& r>1\end{array}\right. ,$$
where $$Q_{L}(\eta,r)=r^{L+1}e^{-r}\psi(L+\eta+1,2L+2,2r).$$

\item[\bf b.] For fixed $\alpha>0,$ $\eta\in\mathbb{R}$ such that $L+\eta>0,$ and $L>-3/2,$ $L\neq-1$ if $\eta\neq0$ and $L>-3/2$ if $\eta=0,$ the equation
\begin{equation}\label{eqtrans}
F_{L}'(\eta,r)/F_{L}(\eta,r)=\alpha Q_{L}'(\eta,\alpha r)/Q_{L}(\eta,\alpha r)
\end{equation}
has infinitely many positive roots, which we denote in increasing order by $\lambda_{L,\eta,\alpha,n},$ $n\in\mathbb{N}.$ These zeros satisfy $$x_{L,\eta,n-1}<\lambda_{L,\eta,\alpha,n}<x_{L,\eta,n},$$ $n\in\{2,3,\dots\},$ where $x_{L,\eta,n}$ stands for the
$n$th positive zero of the Coulomb wave function $\rho\mapsto F_{L}(\eta,\rho).$ Moreover, if $\alpha>0,$ $\eta\in\mathbb{R}$ and $L>-1/2,$ then we have $\lambda_{L,\eta,\alpha,1}<x_{L,\eta,1}.$

\item[\bf c.] For fixed $\alpha>0,$ $\eta\geq0$ and $n\in\mathbb{N}$ the zeros $\lambda_{L,\eta,\alpha,n}$ increase with $L$ on $[0,\infty).$

\end{enumerate}
\end{theorem}

We note that since the boundary value problem \eqref{eqnew} is an extension of \eqref{eqnagy}, while \eqref{radnew} is an extension of \eqref{eqism},
if we take $\eta=0$ in the above theorem, then we obtain some of the main results from \cite{ismail} for the case $\beta=1.$ In the proof of our main result we followed the approach considered in \cite{ismail}, namely, the Sturmian-type arguments and the approach of the Hellman-Feynman theorem of quantum chemistry. Moreover, we used some recent results on regular Coulomb wave and Tricomi hypergeometric functions: the so-called Mittag-Leffler expansion of regular Coulomb wave function (obtained from the infinite product representation, see \cite{coulomb,stampach,wimp} for more details), and a Tur\'an type inequality for Tricomi hypergeometric functions, recently obtained and written in terms of a monotonicity result (see \cite[Remark 3]{baricz}).

\begin{proof}[Proof of Theorem \ref{the1}]
{\bf a.} Subject to the stated boundary condition the differential equation in \eqref{radnew} has solution
$$y(r)=\left\{\begin{array}{ll}A\cdot F_{L}(\eta,\lambda r),& r\in(0,1]\\B\cdot Q_L(\eta,\alpha\lambda r),& r>1\end{array}\right..$$
Since $y$ and $y'$ are to be continuous at $r=1$ we must have $$A\cdot F_{L}(\eta,\lambda)=B\cdot Q_L(\eta,\alpha\lambda)$$ and $$A\cdot \lambda F_{L}'(\eta,\lambda)=B\cdot \alpha\lambda Q_L'(\eta,\alpha\lambda),$$ and there will be a notrivial solution of this system if and only if $$F_{L}'(\eta,\lambda)Q_{L}(\eta,\alpha \lambda)=\alpha Q_{L}'(\eta,\alpha\lambda)F_{L}(\eta,\lambda).$$ In this case we may take $A=Q_L(\eta,\alpha\lambda)$ and $B=F_L(\eta,\lambda).$ Thus, indeed the boundary value problem \eqref{radnew} has for its eigenvalues the zeros of the cross-product of the regular Coulomb wave and Tricomi hypergeometric functions, that is, $$F_{L}'(\eta,r)Q_{L}(\eta,\alpha r)-\alpha Q_{L}'(\eta,\alpha r)F_{L}(\eta,r)$$ and corresponding eigenfunctions
$r\mapsto\Theta_{L}(\eta,r).$

{\bf b.} The equation \eqref{eqtrans} is equivalent to
\begin{equation}\label{eqtrans2}\frac{F_{L}'(\eta,r)}{F_{L}(\eta,r)}-\frac{L+1}{r}=\alpha+\frac{2\alpha\,\psi'(L+\eta+1,2l+2,2\alpha r)}{\psi(L+\eta+1,2L+2,2\alpha r)}.\end{equation}
Since for $L>-3/2,$ $L\neq-1$ if $\eta\neq0$ and $L>-3/2$ if $\eta=0$ we have (see \cite[Lemma 1]{coulomb} for more details) $$\frac{F_{L}'(\eta,r)}{F_{L}(\eta,r)}-\frac{L+1}{r}=\frac{\eta}{L+1}-\sum_{n\geq1}\left(\frac{r}{x_{L,\eta,n}(x_{L,\eta,n}-r)}+
\frac{r}{y_{L,\eta,n}(y_{L,\eta,n}-r)}\right),$$
the left-hand side of the equation \eqref{eqtrans2} is decreasing on $(0,x_{L,\eta,1})$ and also on each interval $(x_{L,\eta,n},x_{L,\eta,n+1}),$ $n\in\mathbb{N}.$ Here $y_{L,\eta,n}$ stands for the $n$th negative zero of the regular Coulomb wave function $r\mapsto F_{L}(\eta,r).$ When $r\searrow0$ the left-hand side of \eqref{eqtrans2} tends to $\eta/(L+1),$ when $r\nearrow x_{L,\eta,n},$ $n\in\mathbb{N}$ it tends
to $-\infty$ and when $r\searrow x_{L,\eta,n},$ $n\in\mathbb{N}$ it tends
to $+\infty.$ On the other hand, according to \cite[Remark 3]{baricz} we know that for $a>1$ and $c\in\mathbb{R}$ the function $r\mapsto \psi'(a,c,r)/\psi(a,c,r)$ is increasing on $(0,\infty).$ Moreover, by using the recurrence relation
$$\psi'(a,c,r)=-a\psi(a+1,c+1,r),$$
the fact that $\psi(a,c,r)$ is positive for $a,c,r\in\mathbb{R},$ and the asymptotic expansion
$$\psi(a,c,r)=r^{-a}(1+\mathcal{O}(r^{-1}))\ \ \mbox{as}\ \  r\to\infty,$$ it follows that $r\mapsto \psi'(a,c,r)/\psi(a,c,r)$ maps $(0,\infty)$ into
$(-\infty,0).$ Thus, the right-hand side of \eqref{eqtrans2} is increasing on $(0,\infty)$ for $\alpha>0$ and $L+\eta>0$ and maps the interval $(0,\infty)$ into $(-\infty,\alpha).$ These show that the equation \eqref{eqtrans2} has indeed infinitely many positive roots, and starting from the second positive root they are certainly located between the positive zeros of the regular Coulomb wave function. Now, by using the asymptotic relation $$\psi(a,c,r)\sim\Gamma(c-1)r^{1-c}/\Gamma(a)\ \ \mbox{as}\ \ r\to0\ \ \mbox{and}\ \ \ c>1,$$ it follows that $\psi'(a,c,r)/\psi(a,c,r)\sim(1-c)/r$ as $r\to0$ and $c>1,$ and thus the right-hand side of \eqref{eqtrans2} tends to $-\infty$ as $r\to0$ and $L>-1/2.$ This shows that indeed if $\alpha>0,$ $\eta\in\mathbb{R}$ and $L>-1/2,$ then we have $\lambda_{L,\eta,\alpha,1}<x_{L,\eta,1}.$

{\bf c.} Since $r\mapsto\Theta_L(\eta,r)$ are eigenfunctions of the boundary value problem \eqref{radnew}, we have
$$-\Theta_L''(\eta,r)\Theta_L(\eta,r)+2\eta\lambda \frac{1}{r}h(r)\Theta_L^2(\eta,r)+L(L+1)\frac{1}{r^2}\Theta_L^2(\eta,r)=\lambda^2g(r)\Theta_L^2(\eta,r).$$
Integrating from zero to infinity we get
\begin{align*}\int_0^{\infty}&\left(\lambda^2g(r)-2\eta\lambda \frac{1}{r}h(r)\right)\Theta_L^2(\eta,r)dr\\&=L(L+1)\int_0^{\infty}\frac{1}{r^2}\Theta_L^2(\eta,r)dr+
\int_0^{\infty}\left(\Theta_L'(\eta,r)\right)^2dr,\end{align*}
where we used integration by parts in the last integral. Since the right-hand side of the above relation is positive for $L\geq0,$ it follows that
\begin{equation}\label{ineqlambda}\lambda^2\int_0^{\infty}g(r)\Theta_L^2(\eta,r)dr\geq \lambda\int_0^{\infty}2\eta\frac{1}{r}h(r)\Theta_L^2(\eta,r)dr.\end{equation}
Now, writing $\lambda_L$ instead of $\lambda_{L,\eta,\alpha,n},$ multiplying the equations
$$-\Theta_L''(\eta,r)+2\eta\lambda_L \frac{1}{r}h(r)\Theta_L(\eta,r)+L(L+1)\frac{1}{r^2}\Theta_L(\eta,r)=\lambda_{L}^2g(r)\Theta_L(\eta,r),$$
$$-\Theta_M''(\eta,r)+2\eta\lambda_M \frac{1}{r}h(r)\Theta_M(\eta,r)+M(M+1)\frac{1}{r^2}\Theta_M(\eta,r)=\lambda_{M}^2g(r)\Theta_M(\eta,r)$$
by $\Theta_M(\eta,r),$ $\Theta_L(\eta,r)$ respectively, subtracting and integrating between $0$ and $\infty$ we get
\begin{align*}&\left(\Theta_M'(\eta,r)\Theta_L(\eta,r)-\Theta_L'(\eta,r)\Theta_M(\eta,r)\right)\Big|_0^{\infty}\\
&+(\lambda_L-\lambda_M)\int_0^{\infty}2\eta\frac{1}{r}h(r)\Theta_L(\eta,r)\Theta_M(\eta,r)dr\\
&+\left[L(L+1)-M(M+1))\right]\int_0^{\infty}\frac{1}{r^2}\Theta_L(\eta,r)\Theta_M(\eta,r)dr\\
&=(\lambda_L^2-\lambda_M^2)\int_0^{\infty}g(r)\Theta_L(\eta,r)\Theta_M(\eta,r)dr.\end{align*}
Note that the integrated term vanishes at $0$ and $\infty$ for $L,M>0,$ and consequently dividing both parts of the above equation by
$L-M$ and taking the limit $M\to L$ we obtain
$$\frac{d\lambda_L}{dL}\int_0^{\infty}2\eta\frac{1}{r}h(r)\Theta_L^2(\eta,r)dr+(2L+1)\int_0^{\infty}\frac{1}{r^2}\Theta_L^2(\eta,r)dr$$
$$=\frac{d\lambda_L^2}{dL}\int_0^{\infty}g(r)\Theta_L^2(\eta,r)dr$$
or equivalently
$$\frac{d\lambda_L}{dL}\int_0^{\infty}2\eta\frac{1}{r}h(r)\Theta_L^2(\eta,r)dr+(2L+1)\int_0^{\infty}\frac{1}{r^2}\Theta_L^2(\eta,r)dr$$
$$=2\lambda_L\frac{d\lambda_L}{dL}\int_0^{\infty}g(r)\Theta_L^2(\eta,r)dr.$$
This implies that
$$\frac{d\lambda_L}{dL}\left(2\lambda_L\int_0^{\infty}g(r)\Theta_L^2(\eta,r)dr-\int_0^{\infty}2\eta\frac{1}{r}h(r)\Theta_L^2(\eta,r)dr\right)$$
$$=(2L+1)\int_0^{\infty}\frac{1}{r^2}\Theta_L^2(\eta,r)dr>0,$$
which in view of \eqref{ineqlambda} and the fact that $\lambda_L$ is positive according to part {\bf b}, yields that $d\lambda_L/dL>0,$ that is, indeed for fixed $\alpha>0$ and $\eta\geq0$ the zero $\lambda_{L}$ is increasing with respect to $L$ on $[0,\infty).$
\end{proof}


\section{Introduction}
In the inverse scattering problem \cite{Kirsch2011AnIntroToInverse, colton2013integralEqMethods, Colton2018lookingback, colton2019inverse}, the scattering object is an obstacle with given boundary conditions and data, and the goal is to determine the obstacle from a set of measurements of the scattered field $u^s$. In this paper, we consider the sound-hard acoustic scattering problem (see Fig.~\ref{fig:helmholtzSetup}) whose forward model is given by the Helmholtz equation:
\begin{equation}
    \label{eq:pde}
    \begin{aligned}
        (\Delta + k^2)u &= 0 ~\mathrm{in}~ \mathbb{R}^d \setminus \bar \Omega, \\
        \frac{\partial u}{\partial n} &= 0 ~\text{on}~ \partial \Omega,
    \end{aligned}
\end{equation}
where  $\Delta$ is the Laplacian operator, $k$ is the wave number, $\Omega$ is the obstacle domain with boundary $\partial \Omega$, $n$ is the outward unit normal to the boundary, and ${u=u^i+u^s}$ for $u^i$ is an incident wave field.
A method to solve the direct obstacle scattering problem is the integral equation method \cite{colton2013integralEqMethods, Kress1991, katsikadelis2002boundaryElements, folland2020introductionpde}. By formulating the problem in terms of boundary integral equations, the method reduces the dimensionality of the problem and avoids the application of absorbing boundary conditions \cite{colton2013integralEqMethods}.

To solve the inverse scattering problem, we are interested in those methods that easily handle topological changes of the boundary. One such method is the implicit boundary integral method (IBIM) \cite{kublik2013implicit, chen2017implicit, izzo2021correctedImplicit} which approximates the boundary integral via volume integral whose domain is implicitly represented by the signed distance function (SDF). Such a representation is advantageous in that it handles complicated shapes and their moving boundaries easily without the need for costly frequent remeshing, making the inverse problem more tractable \cite{santosa_1996, Osher_2003, BURGER_2005}. Additionally, no a priori assumptions on the topology or the nature of the shape need to be made, e.g., the shape could be made of several disconnected subregions.
\begin{figure}[t]
    \centering
    \includegraphics[width=0.452\columnwidth]{images/helmholtzSetup_tub.eps}
    \caption{\textbf{Inverse scattering setup.} $u^i$ is the incident wave, $u^s$ is the wave scattered by the obstacle (solid line). The sensors record the scattered waves at locations surrounding the obstacle. $n(y)$ is the normal vector at the point $y$. Dashed blue lines denote a thin tubular neighborhood around the boundary.}
    \vspace{-1em}
    \label{fig:helmholtzSetup}
\end{figure}

However, the grid-based representation of an SDF, especially in 3D space, is memory-inefficient. Recently, \textit{implicit neural representations} of shapes \cite{Park_2019_CVPR, chen2018implicit_decoder, mescheder_2019, atzmon2019controlling, icml2020_2086}, where a multilayer perceptron (MLP) ${\eta_{\theta}: \mathbb{R}^d \rightarrow \mathbb{R}}$ approximates the SDF, have shown remarkable results in data compression. Instead of being related to the fixed discretization of the ambient 3D space, the parameters $\theta$ of the MLP are directly related to the shape, whose watertight surface is implicitly represented by the isosurface of ${\eta_{\theta}(x)=0}$. Among others, SIREN \cite{sitzmann2019siren}, which is an MLP architecture with periodic activation functions, fits SDFs of complicated shapes robustly.

In this paper, we propose using an implicit neural representation of an obstacle shape in the inverse scattering problem. It allows us to represent various shapes with the number of parameters smaller than the number of grid points of interest. Contrary to the deep learning shape optimization frameworks, such as \cite{remelli2020meshsdf, deepMesh2021}, where the Marching Cubes algorithm \cite{Lorensen_1987, Sethian1999fmm} extracts the surface from the neural SDF on some predefined grid prior to solving the PDE, we use the closest point formulation proposed in \cite{kublik2013implicit} and \cite{chen2017implicit} for computing boundary integrals directly in the level set framework.
The loss functional is composed of a data-fidelity term and penalty terms on the SDF to regularize the ill-posedness of the inverse obstacle scattering problem. We implement the proposed framework in PyTorch, making it differentiable throughout via automatic differentiation (AD). This allows for convenient gradient-based optimization of the parameters $\theta$. While level-set methods are not new in the inverse scattering problems \cite{Dorn_2006, Guo_2013, Albuquerque_2021}, to the best of our knowledge, implicit neural representations of shapes were not yet taken advantage of in such problems. Besides decreasing the number of parameters to optimize, a continuous parameterization with a SIREN offers additional benefits over grid-based representations such as analytical computation of gradients and higher-order derivatives that are independent of conventional grid resolutions. Finally, our differentiable programming framework is user friendly in that it avoids manual derivation of shape derivatives, it easily handles complicated shapes and their perturbations, and achieves good reconstruction results even in noise-corrupted setups.

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.75\textwidth]{images/Scheme.eps}
    \caption{\textbf{Shape reconstruction pipeline.} The MLP is first trained to represent an initial shape before being employed in the inverse problem. By using the neural SDF, we solve the direct problem to obtain the predicted scattered field. Minimization of the loss function updates network parameters, i.e., the shape.}
    \vspace{-1em}
    \label{fig:proposedFramework}
\end{figure*}

\section{Direct and Inverse Obstacle Scattering}
The solution of \eqref{eq:pde} can be represented by the single layer potential \cite{folland2020introductionpde}
\begin{eqnarray}
    \label{eq:singleLayerPotential}
    u^s(x) = \mathcal{S}[\alpha](x) = \int_{\partial \Omega} \alpha(y) \Phi (x,y) ds(y) ~\mathrm{in}~ \mathbb{R}^d {\setminus} \partial \Omega,
\end{eqnarray}
where $\alpha$ is the density to match the boundary condition and $\Phi$ is the Green's function for the Helmholtz equation. The density ${\alpha \in C(\partial \Omega)}$ satisfies a boundary integral equation
\begin{eqnarray}
\label{eq:bie}
    \int_{\partial \Omega} \alpha(y) \dfrac{\partial \Phi (x,y)}{\partial n(x)} ds(y) - \dfrac{1}{2} \alpha(x) = -\frac{\partial u^i}{\partial n}(x) ~\text{on}~ \partial \Omega.
\end{eqnarray}
Finding a solution involves two steps: \textit{i)} solving the linear system in \eqref{eq:bie} for $\alpha(x)$ and \textit{ii)} evaluating \eqref{eq:singleLayerPotential}. A key challenge is to accurately evaluate the boundary integral in \eqref{eq:bie} where $\partial \Omega$ is represented implicitly as the zero-level set of the SDF. This problem has been addressed in \cite{kublik2013implicit} and \cite{chen2017implicit} where an effective solution involves a volume integration over the tubular neighborhood ${T_{\varepsilon}=\{ x \in \mathbb{R}^d: \vert \eta_{\theta}(x) \vert \leq \varepsilon ~\text{and}~ \varepsilon > 0 \}}$, and a projection of the grid points in $T_{\varepsilon}$ onto the boundary:
\begin{equation}
    \label{eq:projection}
    P_{\partial \Omega}(x) = x - \eta_{\theta}(x)\nabla \eta_{\theta}(x), ~x \in T_\varepsilon,
\end{equation}
since  $\vert \nabla \eta_{\theta}(x) \vert = 1$ for all $ x \in T_\varepsilon$  if $\partial \Omega$ is sufficiently smooth, and  $n(x) = - \nabla \eta_{\theta}(x)$ for $\{x\in \mathbb{R}^d : \eta_{\theta}(x)=0 \}.$ That way we avoid the need of extracting the surface by using grid-based techniques and/or the process of frequent remeshing.

The inverse obstacle scattering pipeline is depicted in Fig~\ref{fig:proposedFramework}. Given $M$ measurements $\hat{u}(x_m)$ for ${x_m \in \mathbb{R}^d {\setminus} \Omega}$, we minimize
\begin{equation}
    J(\eta_\theta, u) = \frac{1}{M} \sum_{m=1}^{M} \vert u(x_m) - \hat{u}(x_m) \vert^2 + \mathcal{R}(\eta_\theta),
\end{equation}
where the regularizer is
\begin{equation}
    \label{eq:reg}
    \mathcal{R}(\eta_\theta) = \lambda_1 \sum_{n=1}^{N} \vert \vert \nabla \eta_\theta(x_n) \vert - 1 \vert^2 + \lambda_2 \sum_{n=1}^{N} \vert \Delta \eta_\theta(x_n) \vert^2,
\end{equation}
for $\{x_n\}$ are points in a region of interest (ROI). The ROI is selected to cover the obstacle and sampled so that we regularize the shape representation. The first term in \eqref{eq:reg} ensures that $\eta_\theta$ is an SDF and the second term imposes smoothness on the shape.

\section{Numerical Experiments}
We present results of numerical simulations for inverse obstacle scattering in 2D. The ROI was set as a square ${[-1.1, 1.1]^2}$ and sampled uniformly at ${256 \times 256}$ locations. We initialized the SIREN with $2$ hidden layers and $128$ hidden features, making it $33.5$k parameters in total, and we trained the network using PyTorch \cite{pytorch2019} and Adam \cite{KingmaB14adam}. We measured the scattered field at $M$ angular locations generated by scattering of multiple incident plane waves ${u^i_l(x)=e^{jk\mathbf{x d}_l}}$ and multiple wave numbers $k$. We added a white Gaussian noise to some of the measurements and express the quality of the measurement data in terms of the signal-to-noise ratio (SNR). We show some of the reconstruction results for objects from \cite{leibe2003analyzing} in Fig. \ref{fig:rec_cup2} and \ref{fig:rec_car1}. Reconstruction quality was assessed in terms of Chamfer distance between the ground truth point set $S_{GT}$ and the reconstruction point set $S_{R,k}$ for different $k$s as:
\begin{multline}
    \label{eq:chamferDist}
    d_{C,k}(S_{GT}, S_{R,k}) = \frac{1}{2} \left( \sum_{x \in S_{GT}} \min_{y \in S_{R,k}}\Vert x-y \Vert^2 \right. \\
    \left. + \sum_{y \in S_{R,k}} \min_{x \in S_{GT}}\Vert y-x \Vert^2 \right).
\end{multline}
The results demonstrate the ability of the framework to achieve high-quality reconstructions and its robustness in the noise-corrupted and limited field-of-view (FOV) setups.

\begin{figure}[t]
	\centering
		\subfloat[${d_{C,7}{=}0.189}$, ${d_{C,14}{=}0.033}$]{%
        	\includegraphics[width=0.235\textwidth]{images/cup2_fullview_noiseless_new.eps}%
        }
        \hspace{0.5ex}
		\subfloat[${d_{C,7}{=}0.422}$, ${d_{C,14}{=}0.061}$]{%
			\includegraphics[width=0.235\textwidth]{images/cup2_fullview_noise_new.eps}%
        }
        \vspace{-0.5ex}

		\subfloat[${d_{C,7}{=}1.528}$, ${d_{C,14}{=}0.145}$]{%
			\includegraphics[width=0.235\textwidth]{images/cup2_narrowview_noiseless_new.eps}%
        }
        \hspace{0.5ex}
		\subfloat[${d_{C,7}{=}0.630}$, ${d_{C,14}{=}0.260}$]{%
			\includegraphics[width=0.235\textwidth]{images/cup2_narrowview_noise_new.eps}%
        }
	\caption{\textbf{Reconstruction of a 2D cup obstacle.} (a) Full FOV noiseless measurements; (b) Full FOV noisy measurements (${\text{SNR}=20}$ dB); (c) Limited FOV noiseless; (d) Limited FOV noisy measurements (${\text{SNR}=25}$ dB). $96$ sensors were uniformly displaced on a circle of radius $4.5$ and the number of incident plane waves was $5$. In limited FOV setups, sensors were uniformly placed in angular locations for intervals $[30^{\circ}, 150^{\circ}]$ and $[210^{\circ}, 330^{\circ}]$.}
	\vspace{-1em}
	\label{fig:rec_cup2}
\end{figure}
\begin{figure}[b]
    \vspace{-1em}
	\centering
		\subfloat[${d_{C,8}{=}0.254}$, ${d_{C,15}{=}0.063}$]{%
        	\includegraphics[width=0.235\textwidth]{images/car1_fullview_noiseless_new.eps}%
        }
        \hspace{0.5ex}
		\subfloat[${d_{C,8}{=}0.754}$, ${d_{C,15}{=}0.107}$]{%
			\includegraphics[width=0.235\textwidth]{images/car1_fullview_noise_new.eps}%
        }
        \vspace{-0.5ex}

		\subfloat[${d_{C,8}{=}0.959}$, ${d_{C,15}{=}0.126}$]{%
			\includegraphics[width=0.235\textwidth]{images/car1_narrowview_noiseless_new.eps}%
        }
        \hspace{0.5ex}
		\subfloat[${d_{C,8}{=}0.882}$, ${d_{C,15}{=}0.376}$]{%
			\includegraphics[width=0.235\textwidth]{images/car1_narrowview_noise_new.eps}%
        }
	\caption{\textbf{Reconstruction of a 2D car obstacle.} (a) Full FOV noiseless measurements; (b) Full FOV noisy measurements (${\text{SNR}=25}$ dB); (c) Limited FOV noiseless; (d) Limited FOV noisy measurements (${\text{SNR}=30}$ dB). $96$ sensors were uniformly displaced on a circle of radius $4.5$ and the number of incident plane waves was $5$. In limited FOV setups, sensors were uniformly displaced in angular locations for intervals $[-60^{\circ}, 60^{\circ}]$ and $[120^{\circ}, 240^{\circ}]$.}
	\label{fig:rec_car1}
\end{figure}

\balance

\bibliographystyle{myIEEEtran}


\section{Introduction}

How much of a distribution is revealed by a finite number of independent
observations? In a continuous environment data are informative on their
neighborhoods, and the question can be made precise in the setting of a
metric probability space $\left( \mathcal{X},d,\mu \right) $.

Let $\mathbf{X}=\left( X_{1},...,X_{n}\right) \sim \mu ^{n}$ be an iid
sample from $\mu $. For $r>0$ the \textit{conditional missing mass} is the
random variabl
\begin{equation*}
\hat{M}\left( \mathbf{X},r\right) =1-\Pr \bigcup_{i=1}^{n}B\left(
X_{i},r\right) ,
\end{equation*
where $B\left( x,r\right) $ is the closed ball of radius $r$ about $x$. The
conditional missing mass is the probability of finding a point at distance
more than $r$ from the given sample. The \textit{expected missing mass} is
its expectation $M\left( \mu ,n,r\right) =E\left[ \hat{M}\left( \mathbf{X
,r\right) \right] $. The \textit{Good-Turing estimator} is the random
variabl
\begin{equation*}
G\left( \mathbf{X},r\right) =\frac{1}{n}\sum_{l=1}^{n}\mathbf{1}\left\{
X_{l}\notin \bigcup_{i\neq l}B\left( X_{i},r\right) \right\} ,
\end{equation*
the relative number of sample points more than $r$ from the rest of the
sample. The expected missing mass is a scale-dependent property of the
distribution $\mu $, the conditional missing mass is a scale-dependent
property both of the distribution and the sample, and the Good-Turing
estimator is a function of the sample, used to estimate both the expected
and the conditional missing mass.

If $r<1$ and the metric space is discrete, in the sense that $\mathcal{X}$
is at most countable and $d\left( x,y\right) =1$ for $x\neq y$, then
estimation of the conditional missing mass has been considered in (\cit
{good1953population}, \cite{mcallester2000convergence}, \cit
{mcallester2003concentration}, \cite{berend2013concentration}, \cit
{ben2017concentration}). Exponential concentration of $\hat{M}$ have been
established in this setting, and $G$ is an accurate estimator of $\hat{M}$
in absolute loss, although it has been shown that no good estimator exists
in relative loss (\cite{mossel2019impossibility}). The conditional missing
mass in the discrete setting plays an important role in ecology and
computational linguistics.

In this paper we study the estimation problem in the extended setting of
metric spaces, which may be finite- or infinite dimensional Banach spaces or
more general geometric objects, thus opening the way to other
applications.\bigskip

The principal findings are the following.

\begin{itemize}
	\item Estimation is difficult within the class of all distributions in a
	high dimensional space. For any sample-size $n$ and $\epsilon >0$ there is a
	distribution such that the variance of the conditional missing mass is at
	least $\left( 1-\epsilon \right) /4$, with similar failure guarantees for
	any estimator of the expected missing mass (Proposition \ref{Proposition
		Negative} below).

	\item Such pathologies do not exist, when the distribution is well-behaved
	in the sense that the expected number of sample points in any ball of radius
	$r$, but mutually separated by at least $r$, is small. The corresponding
	random variable $h\left( \mathbf{X},r\right) $ resembles an empirical
	packing number. It is a configuration function (see Talagrand \cit
	{talagrand1995concentration}) and sharply concentrated on its expectation,
	which may be accurately estimated from the sample with high probability (see
	Theorem \ref{Theorem SelfBound} and Corollary \ref{Lemma bound EH by sample}
	below). Specifically, for $t>0$
	\begin{equation}
	\Pr \left\{ \sqrt{E\left[ h\left( \mathbf{X},r\right) \right] }\leq \sqrt
		h\left( \mathbf{X},r\right) }+\sqrt{2t}\right\} \geq 1-e^{-t}.
	\label{First EH estimate}
	\end{equation}

	\item The Good-Turing estimator has bias $O\left( 1/n\right) $ (Proposition
	\ref{Proposition bias} below). Its estimation error and the estimation error
	of the conditional missing mass are controlled by $E\left[ h\left( \mathbf{X
	,r\right) \right] $ as described in the following theorem.\bigskip
\end{itemize}

\begin{theorem}
	\label{Theorem Main
	\begin{eqnarray*}
		Var\left[ G\left( \mathbf{X},r\right) \right]  &\leq &\frac{2 \left( 1+E\left[ h\left( \mathbf{X},r\right) \right] \right) }
			n} \\
		Var\left[ \hat{M}\left( \mathbf{X},r\right) \right]  &\leq &\frac{2E\left[
			h\left( \mathbf{X},r\right) \right] +4\left( e-2\right) \left( \ln
			n+1\right) }{n-1}.
	\end{eqnarray*
	There are absolute constants $C,c,C^{\prime },c^{\prime }<\infty $ such that
	for $t>0
	\begin{eqnarray*}
		\Pr \left\{ \left\vert G\left( \mathbf{X},r\right) -E\left[ G\left( \mathbf{
		},r\right) \right] \right\vert >t\right\}  &\leq &C\exp \left( \frac{-nt^{2
	}{c\left( E\left[ h\left( \mathbf{X},r\right) \right] +\sqrt{n+1}t\right)
	\right)  \\
	\Pr \left\{ \left\vert \hat{M}\left( \mathbf{X},r\right) -E\left[ \hat{M
	\left( \mathbf{X},r\right) \right] \right\vert >t\right\}  &\leq &C^{\prime
	}n\exp \left( \frac{-\left( n-1\right) t^{2}}{c^{\prime }\left( E\left[
	h\left( \mathbf{X},r\right) \right] +\sqrt{\left( n-1\right) }t\right)
\right) .
\end{eqnarray*
These inequalities remain valid if the metric $d$ is replaced by any
measurable distortion measure $d$ such that the relation $d\left( x,y\right)
<r$ is reflexive and symmetric.
\end{theorem}

Definitive values of constants are given in (\ref{Bound G}) and (\ref{Bound
	Mhat}) below. Since there are a priori bounds for $h\left( \mathbf{x}\right)
$ in euclidean spaces of finite dimension (the $1$-packing number of the
unit sphere), the theorem establishes convergence of the Good-Turing
estimator and the conditional missing mass in $\mathbb{R}^{d}$, thus
extending the classical results of the discrete setting, although sample
sizes exponential in the dimension may be needed for the bounds to become
nontrivial.

In general combining the two exponential bounds with (\ref{First EH estimate
) in a union bound gives, for another absolute constant $C^{\prime \prime }$
and $\delta >0$, the purely empirical boun
\begin{equation}
\Pr \left\{ \left\vert \hat{M}\left( \mathbf{X},r\right) -G\left( \mathbf{X
,r\right) \right\vert > C^{\prime \prime }\left( \sqrt{\frac{h\left(
		\mathbf{X},r\right) \ln \left( n/\delta \right) }{n-1}}+\frac{\ln \left(
	n/\delta \right) }{\sqrt{n-1}}\right) \right\} \leq \delta .
\label{Empirical bound}
\end{equation}

In summary we have the following situation: even though estimation of the
expected and conditional missing mass is not possible in general, it is so
in the fortuitous case of a benign distribution, and this case could in
principle be determined from the available sample $\mathbf{X}$ of
observations, \textit{for an unknown distribution independent of the
	dimension of the ambient space}.

There is a caveat here, because as yet we have no efficient algorithm to
compute the function $h\left( \mathbf{x},r\right) $ from a given sample
\mathbf{x}$, and most likely no polynomial time algorithm exists. Finding
useful heuristics or efficient algorithms to compute reasonable upper bounds
of $h\left( \mathbf{x},r\right) $ remains an open problem.

When can we expect $h\left( \mathbf{X},r\right) $ to be small? A generic
example of a benign distribution would be concentrated on a low dimensional
(albeit unknown) sub-manifold. This is frequently the case in practice,
since the generative processes underlying real-world distributions often
have far fewer degrees of freedom than the dimension of the ambient space
where data is presented, an observation which has given rise to the manifold
hypothesis (\cite{ma2012manifold}, \cite{fefferman2016testing}, \cit
{berenfeld2021density}). Such manifolds need not have a pleasant structure.
In Proposition \ref{Proposition example} we provide an example of a
distribution $\mu $ in $L_{2}\left[ 0,\infty\right) $ whose support is not
totally bounded, nowhere smooth, not contained in any finite dimensional
subspace of $L_{2}\left[ 0,\infty\right) $, and yet $h\left( \mathbf{X},r\right)
\leq 5$ a.s., for any $r$ and any sample drawn from $\mu $.

The only reference which we know to address the missing mass in metric
spaces is \cite{berend2012missing}, where Section 4 gives a bound on
M\left( \mu ,n,r\right) $ for totally bounded ambient spaces. Most of the
following will be concerned with the estimation problem. Section \re
{Section applications} discusses some applications.

\subsection{Notation}

For $m\in \mathbb{N}$ we use the abbreviation $\left[ m\right] =\left\{
1,...,m\right\} $. The indicator of a set $A$ is denoted $\mathbf{1}A$, its
complement by $A^{c}$. Both cardinality of sets and absolute value of reals
are denote by bars $\left\vert \cdot \right\vert $. In a metric space
B\left( x,r\right) $ denotes the closed ball of radius $r$ about $x$, with $r
$ omitted when there is no ambiguity. Vectors are written in bold letters.
If $\mathbf{x}=\left( x_{1},...,x_{n}\right) \in \mathcal{X}^{n}$, $k\in
\left\{ 1,...,n\right\} $ and $y\in \mathcal{X}$ then the substitution
S_{y}^{k}\left( \mathbf{x}\right) \in \mathcal{X}^{n}$ is defined b
\begin{equation*}
S_{y}^{k}\left( \mathbf{x}\right) =\left(
x_{1},...,x_{k-1},y,x_{k+1},...,x_{n}\right) .
\end{equation*
Random variables are written in upper case letters. If $\mathbf{X}$ is a
random vector then $\mathbf{X}^{\prime }$ is always an independent copy of
\mathbf{X}$. The unit mass at a point $x$ will be denoted with $\delta _{x}$.

If $Y$ is a random variable with values in $\left[ 0,1\right] $ the we write
the complementary variable $Y^{\perp }=1-Y$.

We will use the letter $d$ both for a dimension and the metric of $\left(
\mathcal{X},d\right) $, but there should be no ambiguity. On $\mathbb{R}^{d}$
the letter $\lambda $ is used for the Lebesgue measure and
e_{1},e_{2},...,e_{d}$ for the canonical basis vectors.

\section{Estimation\label{Section estimation}}

We begin with a general negative result. Then we study estimation of the
condensation-separation property, the Good-Turing estimator and conclude
with an outline of the proof of Theorem \ref{Theorem Main}.

\subsection{A negative result\label{Section negative results}}

In general there is no good estimator for the expected missing mass, and the
conditional missing mass does not concentrate.

\begin{proposition}
	\label{Proposition Negative}Let $1<r<\sqrt{2}$. For every $\epsilon >0$ and
	n\in \mathbb{N}$ there exists $d\in \mathbb{N}$ and

	(i) $\mu $ on $\mathbb{R}^{d}$ such that for $\mathbf{X}\sim \mu ^{n}$, Var
	\left( \hat{M}\left( \mathbf{X},r\right) \right) \geq \left( 1-\epsilon
	\right) ^{2}/4$,

	(ii) and for every $f:\mathcal{X}^{n}\rightarrow \mathbb{R}$ there exists
	\mu $ on $\mathbb{R}^{d}$ such that for $\mathbf{X}\sim \mu ^{n}$, we have
	\begin{equation*}
	E\left[ \left( f\left( \mathbf{X}\right) -M\left( \mu ,n,r\right) \right)
	^{2}\right] \geq \left( 1-\epsilon \right) ^{2}/16.
	\end{equation*}
\end{proposition}

\begin{proof}
	Let $d\geq n/\epsilon $ and choose $\ r$ with $1<r<\sqrt{2}$. Let $\mu
	_{1}=\left( 1/d\right) \sum_{i=1}^{d}\delta _{e_{i}}$ be uniform on $d$
	basis vectors. By the choice of $r$ any $n$-sample $\mathbf{X}$ drawn from
	\mu _{1}$ must miss $d-n$ basis vectors, since all basis vectors are more
	than $r$ apart. Thus $\hat{M}\left( \mathbf{X},r\right) \geq \left(
	d-n\right) /d\geq 1-\epsilon $ and $M\left( \mu _{1},n,r\right) =E\left[
	\hat{M}\left( \mathbf{X},r\right) \right] \geq 1-\epsilon $.

	Now let $\mu _{2}=\left( 1/2\right) ^{1/n}\mu _{1}+\left( 1-\left(
	1/2\right) ^{1/n}\right) \delta _{0}$ and let $\mathbf{Y}$ be an $n$-sample
	drawn from $\mu _{2}$. Let $A$ be the event that $0$ occurs in $\mathbf{Y}$.
	Then $\Pr A=1/2$ by definition of $\mu _{2}$, since $\Pr A^{c}=\left(
	1-\left( 1-\left( 1/2\right) ^{1/n}\right) \right) ^{n}=1/2$. If $A$ occurs
	then $\hat{M}\left( \mathbf{Y},r\right) =0$, because all basis vectors are
	within $r$ from $0$. Under $A^{c}$ however $\hat{M}\left( \mathbf{Y
	,r\right) \geq 1-\epsilon $. Thus $Var\left( \left[ \hat{M}\left( \mathbf{Y
	,r\right) \right] \right) \geq \left( 1-\epsilon \right) ^{2}/4$ which is
	(i) with $\mu =\mu _{2}$.

	It also follows that $M\left( \mu _{2},n,r\right) =E\left[ \hat{M}\left(
	\mathbf{Y},r\right) |A\right] \Pr A+E\left[ \hat{M}\left( \mathbf{Y
	,r\right) |A^{c}\right] \Pr A^{c}=M\left( \mu _{1},n,r\right) /2$ and
	M\left( \mu _{1},n,r\right) -M\left( \mu _{2},n,r\right) \geq \left(
	1-\epsilon \right) /2$. But conditional on $A^{c}$ the samples $\mathbf{X}$
	and $\mathbf{Y}$ are identically distributed, s
	\begin{align*}
	& E\left[ \left( f\left( \mathbf{X}\right) -M\left( \mu _{1},n,r\right)
	\right) ^{2}+\left( f\left( \mathbf{Y}\right) -M\left( \mu _{2},n,r\right)
	\right) ^{2}\right]  \\
	& \geq E\left[ \left( f\left( \mathbf{X}\right) -M\left( \mu _{1},n,r\right)
	\right) ^{2}+\left( f\left( \mathbf{X}\right) -M\left( \mu _{2},n,r\right)
	\right) ^{2}|A^{c}\right] \Pr \left( A^{c}\right)  \\
	& \geq \frac{\left( M\left( \mu _{1},n,r\right) -M\left( \mu _{2},n,r\right)
		\right) ^{2}}{2}\geq \frac{\left( 1-\epsilon \right) ^{2}}{8},
	\end{align*
	which gives (ii) with either with $\mu =\mu _{1}$ or $\mu =\mu _{2}$. In the
	second inequality we used calculus to minimize $\left( x-M\left( \mu
	_{1},n,r\right) \right) ^{2}+\left( x-M\left( \mu _{2},n,r\right) \right)
	^{2}$.\bigskip
\end{proof}

\subsection{Condensation and separation\label{Section Condensation
		separation}}

It follows from Proposition \ref{Proposition Negative} that estimators of
the expected missing mass will only work if we can preclude a construction
as in the previous section. We can either rule it out a priori by some
constraint on the dimension, or, if we insist on dimension independence, at
least rule it out with high probability with the use of an auxiliary
statistic.

For $r>0$ and $k\in \mathbb{N}$ we say a sequence $S=\left(
x_{1},...,x_{k}\right) \in \mathcal{X}^{k}$ has the \textit
	condensation-separation} property, denoted $\Pi _{r}\left( S\right) $, if

\begin{itemize}
	\item There exists $y\in \mathcal{X}$ such that $\forall i\in \left[ k\right]
	,$ $d\left( x_{i},y\right) \leq r$ (condensation)

	\item For all $1\leq i<j\leq k$ we have $d\left( x_{i},x_{j}\right) >r$
	(separation)
\end{itemize}

Define the function $h:\mathcal{X}^{n}\rightarrow \mathbb{R}$ by
\begin{equation*}
h\left( \mathbf{x},r\right) =\max \left\{ \left\vert S\right\vert
:S\subseteq \left( x_{1},...,x_{n}\right) \text{ such that }\Pi _{r}\left(
S\right) \right\} .
\end{equation*
$h\left( \mathbf{x}\right) $ is the largest cardinality of a subsample
separated by more than $r$ but contained in some closed ball of radius $r$.
Notice that in the setting of Proposition \ref{Proposition Negative} we will
have $h\left( \mathbf{X}\right) =O\left( n\right) $ with high probability
for $\mathbf{X}\sim \mu _{2}^{n}$.

In the discrete case, when $d\left( x,y\right) =1$ $\iff $ $x\neq y$,
h\left( \mathbf{x}\right) $ is either always zero if $r>1$, or$\ 1$ if
r\leq 1$. In one dimension $h\left( \mathbf{x}\right) $ is at most $2$, in $2
$ dimensions it is at most $5$. In general, in $D$ dimensions with euclidean
metric, we can bound $h\left( \mathbf{x}\right) $ by the $1$-packing number
of the unit spher
\begin{equation*}
h\left( \mathbf{x},r\right) \leq \max \left\{ \left\vert S\right\vert
:S\subset \mathcal{S}^{D-1},\forall x,y\in S,x\neq y\implies d\left(
x,y\right) >1\right\} ,
\end{equation*
so that convergence of $G$ and $\hat{M}$ is guaranteed by Theorem \re
{Theorem Main}. These are worst-case bounds depending only on (and growing
rapidly with) the dimension of the ambient space.

But the random variable $h\left( \mathbf{X},r\right) $ depends on the
underlying distribution and not on the dimension of the ambient space. In
the simplest case $\mu $ is supported on a low-dimensional linear subspace,
and the corresponding packing numbers can be substituted for $h\left(
\mathbf{X},r\right) $. But linearity is not necessary for $h\left( \mathbf{X
,r\right) $ to be small, nor is differentiability.

\begin{proposition}
	\label{Proposition example}For $p\in \left( 1,\infty \right) $ there exists
	a distribution $\mu $ in $L_{p}\left[ 0,\infty \right) $ whose support is
	not totally bounded, nowhere smooth and not contained in any finite
	dimensional subspace, but $h\left( \mathbf{X},r\right) \leq 2^{p}+1$ for any
	$r>0$ and $\mathbf{X}\sim \mu $.
\end{proposition}

\begin{proof}
	Let $\mu $ be the distribution of the random variable $1_{\left[ 0,X\right] }
	$ in $L_{p}\left[ 0,\infty \right) $ with $X$ any real random variable whose
	distribution has full support on $\left[ 0,\infty \right) $ (the exponential
	distribution would do). It is easy to see that the support of $\mu $ has the
	required properties. Then note that $\left\Vert 1_{\left[ 0,a\right] }-1_
		\left[ 0,b\right] }\right\Vert _{p}=\left\vert a-b\right\vert ^{1/p}$, so if
	$h\left( \mathbf{X},r\right) \geq k$ then $\exists f\in L_{p}\left[ 0,\infty
	\right) $ and $x_{1},...,x_{k}\in \left[ 0,1\right] $ with $x_{i-1}<x_{i}$,
	\left\Vert 1_{\left[ 0,x_{i}\right] }-1_{\left[ 0,x_{i-1}\right]
	}\right\Vert _{p}>r$ and $\left\Vert 1_{\left[ 0,x_{i}\right] }-f\right\Vert
	_{p}\leq r$. Then $2r\geq \left\Vert 1_{\left[ 0,x_{1}\right] }-1_{\left[
		0,x_{k}\right] }\right\Vert _{p}=\left\vert x_{k}-x_{1}\right\vert
	^{1/p}=\left( \sum_{i=2}^{k}\left( x_{i}-x_{i-1}\right) \right)
	^{1/p}>\left( k-1\right) ^{1/p}r$, so $k-1<2^{p}$. \bigskip
\end{proof}

Clearly the condensation-separation property is \textit{hereditary} in the
sense that $\Pi _{r}\left( S\right) $ implies $\Pi _{r}\left( S^{\prime
}\right) $ for any subsequence $S^{\prime }\subseteq S$. The function $h$,
which maps $\mathbf{x}$ to the length of the longest subsequence having
property $\Pi _{r}$, is therefore a \textit{configuration function} as
defined in (\cite{Boucheron13}, Section 3.3, see also \cit
{talagrand1995concentration}, \cite{McDiarmid98} or \cite{boucheron2000sharp
). Configuration functions are strongly self-bounding and possess special
concentration properties (see Corollary 3.8 and Theorem 6.12 in \cit
{Boucheron13}), which, when applied to $h$, yield the following theorem.

\begin{theorem}
	\label{Theorem SelfBound} If $\mathbf{X}=\left( X_{1},...,X_{n}\right) $ is
	a vector of independent variables in $\mathcal{X}$ and $h:\mathcal{X
	^{n}\rightarrow \mathbb{R}$ is the configuration function defined above then

	(i) for every $t>0
	\begin{equation*}
	\Pr \left\{ h\left( \mathbf{X},r\right) -E\left[ h\left( \mathbf{X},r\right)
	\right] >t\right\} \leq \exp \left( \frac{-t^{2}}{2E\left[ h\left( \mathbf{X
		,r\right) \right] +2t/3}\right) ,
	\end{equation*}

	(ii) and for every $0<t\leq E\left[ h\left( \mathbf{X},r\right) \right]
	\begin{equation*}
	\Pr \left\{ E\left[ h\left( \mathbf{X},r\right) \right] -h\left( \mathbf{X
	,r\right) >t\right\} \leq \exp \left( \frac{-t^{2}}{2E\left[ h\left( \mathbf
			X},r\right) \right] }\right)
	\end{equation*}
\end{theorem}

For our purpose the most important conclusions are summarized in the
following.

\begin{corollary}
	\label{Lemma bound EH by sample}For $t>0$

	(i) $\Pr \left\{ \sqrt{E\left[ h\left( \mathbf{X},r\right) \right] }\leq
	\sqrt{h\left( \mathbf{X},r\right) }+\sqrt{2t}\right\} \geq 1-e^{-t}$

	(ii) $\Pr \left\{ h\left( \mathbf{X},r\right) -2E\left[ h\left( \mathbf{X
	,r\right) \right] >t\right\} \leq e^{-6t/7}.$
\end{corollary}

Part (i) means that, if we are able to compute $h\left( \mathbf{X}\right) $,
then $E\left[ h\left( \mathbf{X}\right) \right] $ can be estimated with high
probability from the sample. Consequently the bounds in Theorem \ref{Theorem
	Main} can be independent of assumptions on the distribution $\mu $ and
determined with high probability by the observed data $\mathbf{X}$ as in
\ref{Empirical bound}).

Part (ii) gives a subexponential bound in the other direction, which will be
important in the proof of Theorem \ref{Theorem Main}.

\begin{proof}
	Equating the r.h.s. of Theorem \ref{Theorem SelfBound} (ii) to $\delta $ and
	solving for $t$ gives for $\delta >0$ with probability at least $1-\delta $
	that $E\left[ h\left( \mathbf{X}\right) \right] -h\left( \mathbf{X}\right)
	\leq \sqrt{2E\left[ h\left( \mathbf{X}\right) \right] \ln \left( 1/\delta
		\right) }$. Bringing the r.h.s. to the left, completing the square and
	taking the square root gives (i) with $\delta =e^{-t}$. Similarly we get
	from Theorem \ref{Theorem SelfBound} (i) with probability at least $1-\delta
	$ tha
	\begin{equation*}
	h\left( \mathbf{X}\right) -E\left[ h\left( \mathbf{X}\right) \right] \leq
	\sqrt{2E\left[ h\left( \mathbf{X}\right) \right] \ln \left( 1/\delta \right)
	}+\frac{2\ln \left( 1/\delta \right) }{3}.
	\end{equation*
	Then use $\sqrt{2E\left[ h\left( \mathbf{X}\right) \right] \ln \left(
		1/\delta \right) }\leq E\left[ h\left( \mathbf{X}\right) \right] +\ln \left(
	1/\delta \right) /2$ and set $\delta =e^{-t}$ to get the second conclusion.
\end{proof}

At this point we have no efficient algorithm to compute $h\left( \mathbf{x
,r\right) $. For our bounds it will be sufficient to test if $h\left(
\mathbf{x},r\right) \geq H$ for some fixed value $H$. To this end one could
execute an algorithm for the minimum enclosing ball problem \cit
{yildirim2008two} on candidate subsequences of size $H$, which would take
polynomial execution time. The generation of candidate subsequences could be
further accelerated as they have to satisfy $r<d\left( x_{i},x_{j}\right)
\leq 2r$. In any case the computation of $h\left( \mathbf{x},r\right) $, or
a good upper bound thereof, remains an interesting problem for further
research.

\subsection{The Good-Turing estimator}

For the remainder of this section we take the radius $r$ as fixed and omit
it from all expressions unless explicitly specified otherwise. We will not
make use of the fact that $d$ is a metric, but only that $\left\{ d\left(
x,y\right) \leq r\right\} $ is a reflexive, symmetric relation.

The indicator of the event, that a sample point $X_{k}$ is not in the union
of the balls about the other sample points, is a crude leave-one-out
estimate for the expected missing mass. To reduce variance we average this
estimate over all $x_{k}$, which leads to the function $G:\mathcal{X
^{n}\rightarrow \left[ 0,1\right] $, defined b
\begin{equation*}
G\left( \mathbf{x}\right) =\frac{1}{n}\sum_{k=1}^{n}\mathbf{1}\left\{
x_{k}\notin \bigcup_{i:i\neq k}B\left( x_{i}\right) \right\} ,
\end{equation*
The random variable $G\left( \mathbf{X}\right) $ is conveniently called the
Good-Turing estimator, because this is what it reduces to in the discrete
case. It is the relative number of sample points, which are further than $r$
from all other sample points. If $d$ is indeed a metric, then the
computation of the Good-Turing estimator requires $n\left( n-1\right) /2$
evaluations of the distance function (e.g. evaluations of a kernel matrix),
and $n\left( n-1\right) $ comparisons.

Just as in the discrete case, where it was first shown in \cit
{good1953population}, the Good-Turing estimator has small bias.

\begin{proposition}
	\label{Proposition bias} $M\left( \mu ,n\right) \leq \mathbb{E}\left[
	G\left( \mathbf{X}\right) \right] \leq M\left( \mu ,n\right) +1/n$.
\end{proposition}

\begin{proof}
	We work with the complements, $M^{\perp }\left( \mu ,n\right) =1-M\left( \mu
	,n\right) $, $G^{\perp }\left( \mathbf{X}\right) =1-G\left( \mathbf{X
	\right) $
	\begin{eqnarray*}
		M^{\perp }\left( \mu ,n\right)  &=&E\left[ \Pr \bigcup_{i=1}^{n}B\left(
		X_{i}\right) \right]  \\
		&=&\frac{1}{n}\sum_{k=1}^{n}E\left[ \Pr \bigcup_{i:i\neq k}B\left(
		X_{i}\right) \cup \left( B\left( X_{k}\right) \backslash \bigcup_{i:i\neq
			k}B\left( X_{i}\right) \right) \right]  \\
		&=&\frac{1}{n}\sum_{k=1}^{n}E\left[ \Pr \bigcup_{i:i\neq k}B\left(
		X_{i}\right) \right] +\frac{1}{n}\sum_{k=1}^{n}E\left[ \Pr B\left(
		X_{k}\right) \backslash \bigcup_{i:i\neq k}B\left( X_{i}\right) \right]  \\
		&=&E\left[ \frac{1}{n}\sum_{k=1}^{n}\mathbf{1}\left\{ X_{k}\in
		\bigcup_{i:i\neq k}B\left( X_{i}\right) \right\} \right] +\frac{1}{n}E\left[
		\Pr \bigcup_{k=1}^{n}\left( B\left( X_{k}\right) \backslash \bigcup_{i:i\neq
			k}B\left( X_{i}\right) \right) \right]  \\
		&=&E\left[ G^{\perp }\left( \mathbf{X}\right) \right] +\frac{1}{n}E\left[
		\Pr \bigcup_{k=1}^{n}\left( B\left( X_{k}\right) \backslash \bigcup_{i:i\neq
			k}B\left( X_{i}\right) \right) \right] .
	\end{eqnarray*
	But the last term is larger than zero and smaller than $1/n$.
\end{proof}

\subsection{Concentration of $G$ and $\hat{M}$}

We outline the proof of Theorem \ref{Theorem Main}. A detailed proof is
given in the appendix. Define a nonlinear operator $Q$ acting on bounded
functions $f:\mathcal{X}^{n}\rightarrow \mathbb{R}$ b
\begin{equation*}
Qf\left( \mathbf{x}\right) =f\left( \mathbf{x}\right) -\min_{k}\inf_{y\in
	\mathcal{X}}~f\left( S_{y}^{k}\left( \mathbf{x}\right) \right)
=\max_{k}\sup_{y\in \mathcal{X}}f\left( \mathbf{x}\right) -f\left(
S_{y}^{k}\left( \mathbf{x}\right) \right) .
\end{equation*}

We will use the following auxiliary result, which may be of independent
interest.

\begin{proposition}
	\label{Mytheorem}Let $\mathbf{X}=\left( X_{1},...,X_{n}\right) $ be a vector
	of independent random variables with values in $\mathcal{X}$ and \thinspace
	f:\mathcal{X}^{n}\rightarrow \left[ 0,1\right] $ be measurable and strongly
	\left( a,0\right) $-self-bounded in the sense tha
	\begin{equation*}
	\forall \mathbf{x}\in \mathcal{X}^{n}\text{, }\sum_{k=1}^{n}f\left( \mathbf{
	}\right) -\inf_{y\in \mathcal{X}}f\left( S_{y}^{k}\mathbf{x}\right) \leq
	af\left( \mathbf{x}\right)
	\end{equation*
	with $a\geq 1$. Then $Var\left[ f\left( \mathbf{X}\right) \right] \leq a
	\left[ Q\left( \mathbf{X}\right) \right] $. Suppose also that for some
	b\geq 1$ and $w,\lambda >0$ and for all $t>0
	\begin{equation*}
	\Pr \left\{ Qf\left( \mathbf{X}\right) >w+t\right\} \leq be^{-\lambda t
	\text{.}
	\end{equation*
	Then with $C\approx 4.16$ we have for every $\delta \in \left( 0,1\right)
	\begin{equation*}
	\Pr \left\{ \left\vert f\left( \mathbf{X}\right) -E\left[ f\left( \mathbf{X
	\right) \right] \right\vert >\sqrt{Cae^{2}w\ln \left( b+2e^{2}/\delta
		\right) }+e^{2}\sqrt{\frac{Ca}{\lambda }}\ln \left( b+2e^{2}/\delta \right)
	\right\} \leq \delta .
	\end{equation*
	and for $t>0
	\begin{equation*}
	\Pr \left\{ \left\vert f\left( \mathbf{X}\right) -E\left[ f\left( \mathbf{X
	\right) \right] \right\vert >t\right\} \leq 2\left( b+e^{2}\right) \exp
	\left( \frac{-t^{2}}{e^{2}\left( Caw+2\sqrt{Ca\lambda ^{-1}}t\right)
	\right) .
	\end{equation*
	If $b=1$ then $b$ can be deleted from these inequalities.
\end{proposition}

The proof of this proposition is somewhat involved and provided in the
appendix. It first converts the exponential tail-bound on $Qf\left( \mathbf{
}\right) $ into moment bounds, then uses the moment inequalities from (\cit
{boucheron2005moment}, Theorems 2 and 4) to bound the moments of positive
and negative deviations of $f\left( \mathbf{X}\right) -E\left[ f\left(
\mathbf{X}\right) \right] $ and then re-converts the latter moment bounds
into tail-bounds.\bigskip

With Proposition \ref{Mytheorem} at hand we work with the complements
G^{\perp }=1-G$ and $\hat{M}^{\perp }=1-\hat{M}$. We have to show that these
functions are strongly $\left( a,0\right) $-self-bounded and find a
manageable bound for the function $Qf$. Then we need to identify the values
of $b,w$ and $\lambda $.

The first bit is easy for the conditional missing mass: define for $k\in
\left[ n\right] $ the functions $W_{k}$ and $W:\mathcal{X}^{n}\rightarrow
\mathbb{R}
\begin{equation*}
W_{k}\left( \mathbf{x}\right) :=\Pr B\left( x_{k}\right) \backslash
\bigcup_{i:i\neq k}B\left( x_{i}\right) \text{ and }W\left( \mathbf{x
\right) :=\max_{k}W_{k}\left( \mathbf{x}\right) .
\end{equation*}

\begin{lemma}
	\label{Lemma Bound DL}$\hat{M}^{\perp }$ is $\left( 1,0\right)
	-self-bounded and $Q\hat{M}^{\perp }\leq W$.
\end{lemma}

\begin{proof}
	With reference to any $k\in \left\{ 1,...,n\right\}
	\begin{equation*}
	\hat{M}^{\perp }\left( \mathbf{x}\right) =\Pr \bigcup_{i}B\left(
	x_{i}\right) =\Pr \bigcup_{i:i\neq k}B\left( x_{i}\right) +W_{k}\left(
	\mathbf{x}\right) .
	\end{equation*
	It follows that $\hat{M}^{\perp }\left( \mathbf{x}\right) -\inf_{y}\hat{M
	^{\perp }\left( S_{y}^{k}\mathbf{x}\right) \leq W_{k}\left( \mathbf{x
	\right) $ and thus $Q\hat{M}^{\perp }\leq W$. Also note tha
	\begin{equation*}
	\sum_{k}W_{k}\left( \mathbf{x}\right) =\sum_{k}\Pr B\left( x_{k}\right)
	\backslash \bigcup_{i\neq k}B\left( x_{i}\right) =\Pr \bigcup_{k}\left(
	B\left( x_{k}\right) \backslash \bigcup_{i\neq k}B\left( x_{i}\right)
	\right) \leq \hat{M}^{\perp }\left( \mathbf{x}\right) ,
	\end{equation*
	since the events in the second sum are disjoint.\bigskip
\end{proof}

A similar argument establishes that $G^{\perp }$ is $\left( 2,0\right)
-self-bounded and $QG^{\perp }\left( \mathbf{X}\right) \leq \left( 1+h\left(
\mathbf{X}\right) \right) /n$. From Corollary \ref{Lemma bound EH by sample}
we then find
\begin{equation*}
\Pr \left\{ QG^{\perp }\left( \mathbf{X}\right) \geq \frac{1+2E\left[
	h\left( \mathbf{X}\right) \right] }{n}+t\right\} \leq e^{-6nt/7}.
\end{equation*
We then use Proposition \ref{Mytheorem} on $G^{\perp }$ with $a=2$, $b=1$,
w=\left( 1+2E\left[ h\left( \mathbf{X}\right) \right] \right) /n$ and
\lambda =6n/7$. Also $E\left[ QG^{\perp }\left( \mathbf{X}\right) \right]
\leq \left( 1+E\left[ h\left( \mathbf{X}\right) \right] \right) /n$, which
gives the necessary bound for the variance and completes the proof for the
Good-Turing estimator, for which we obtain the exponential inequalit
\begin{multline}
\Pr \left\{ \left\vert G\left( \mathbf{X}\right) -E\left[ G\left( \mathbf{X
\right) \right] \right\vert >t\right\}   \label{Bound G} \\
\leq 2e^{2}\exp \left( \frac{-nt^{2}}{e^{2}\left( 2C\left( 1+2E\left[
	h\left( \mathbf{X}\right) \right] \right) +\sqrt{\frac{28}{3}C}t\right)
\right) .
\end{multline}

The situation for the conditional missing mass is more complicated. We hav
\begin{equation*}
W_{k}\left( \mathbf{X}\right) \leq \frac{1}{n-1}\sum_{j:j\neq k}E\left[
\mathbf{1}\left\{ X_{j}\in B\left( X_{k}\right) \backslash \bigcup_{i:i\neq
	k,i<j}B\left( X_{i}\right)\right\} |X_{k},X_{1},...,X_{j-1} \right]
:=F_{k}\left( \mathbf{X}\right) .
\end{equation*
On the other hand consider the random variable
\begin{equation*}
V_{k}\left( \mathbf{X}\right) =\frac{1}{n-1}\sum_{j:j\neq k}\mathbf{1
\left\{ X_{j}\in B\left( X_{k}\right) \backslash \bigcup_{i:i\neq
	k,i<j}B\left( X_{i}\right) \right\} .
\end{equation*
The sequence of the $X_{j}$ which contributes to this sum has the
condensation-separation property, since they all must be contained in the
ball about $X_{k}$, but may not be contained in the balls about any of the
other contributing $X_{i}$. Therefore $V_{k}\left( \mathbf{X}\right) \leq
h\left( \mathbf{X}\right) $. But the terms in $F_{k}$ are just the
conditional expectations of the terms in $V_{k}$. A Martingale argument
shows that
\begin{equation*}
\Pr \left\{ F_{k}\left( \mathbf{X}\right) >2V_{k}\left( \mathbf{X}\right)
+t\right\} \leq \exp \left( \frac{-\left( n-1\right) t}{4\left( e-2\right)
\right) .
\end{equation*
Since $W_{k}\leq F_{k}$ and $V_{k}\leq h$, a union bound and $Q\hat{M
^{\perp }\leq \max_{k}W_{k}$ (by Lemma \ref{Lemma Bound DL}) giv
\begin{equation}
\Pr \left\{ Q\hat{M}^{\perp }\left( \mathbf{X}\right) >2h\left( \mathbf{X
\right) +t\right\} \leq n\exp \left( \frac{-\left( n-1\right) t}{4\left(
	e-2\right) }\right) .  \label{First W-bound}
\end{equation
With integration by parts we then obtain the bound
\begin{equation*}
E\left[ Q\hat{M}^{\perp }\left( \mathbf{X}\right) \right] \leq \frac{2E\left[
	h\left( \mathbf{X}\right) \right] +4\left( e-2\right) \left( \ln n+1\right)
}{n-1},
\end{equation*
as needed for the variance part of Proposition \ref{Mytheorem}. Combining
\ref{First W-bound}) with Corollary \ref{Lemma bound EH by sample} finally
yields
\begin{equation*}
\Pr \left\{ Qf\left( \mathbf{X}\right) -\frac{4E\left[ h\left( \mathbf{X
	\right) \right] }{n-1}>t\right\} \leq \left( n+1\right) \exp \left( \frac
	-\left( n-1\right) t}{8\left( e-2\right) }\right) .
\end{equation*
Thus we have again collected all the ingredients for Proposition \re
{Mytheorem}, this time for $\hat{M}^{\perp }$, with $a=1$, $b=n+1$, $\lambda
=\left( n-1\right) /\left( 8\left( e-2\right) \right) $ and $w=4E\left[
h\left( \mathbf{X}\right) \right] /\left( n-1\right) $. Substitution give
\begin{multline}
\Pr \left\{ \left\vert \hat{M}\left( \mathbf{X}\right) -E\left[ \hat{M
\left( \mathbf{X}\right) \right] \right\vert >t\right\}   \label{Bound Mhat}
\\
\leq 2\left( n+1+e^{2}\right) \exp \left( \frac{-\left( n-1\right) t^{2}}
	e^{2}\left( 4CE\left[ h\left( \mathbf{X}\right) \right] +\sqrt{32C\left(
		e-2\right) \left( n-1\right) }t\right) }\right) .
\end{multline}

\section{Applications\label{Section applications}}

Since $h\left( \mathbf{x}\right) =1$ in the discrete case, all the
applications of the discrete case are covered by Theorem \ref{Theorem Main},
albeit with larger constants. With little imagination one can think of
similar applications which are not covered by the previous results. For
example let the members of a population be described by vectors such as gene
sequences. Then Theorem \ref{Theorem Main} can be applied and the
Good-Turing estimator can be used to estimate the relative proportion of the
population which is different from the sample in more than a prescribed
number of components, provided that $h\left( \mathbf{X}\right) $ is found to
be small. In the sequel we describe a different application of the extended
missing mass to machine learning.

\subsection{Generalization bounds for Lipschitz- or $\protect\beta $-smooth
	loss-classes}

We give two very easy learning bounds for very large hypothesis classes,
where the conditional missing mass controls generalization as a data
dependent complexity measure. They show how learning is still possible for
"easy" data, even if standard complexity measures on the hypothesis class
fail.

Let $\mathcal{F}$ be a loss-class on $\left( \mathcal{X},d\right) $. By this
we mean that $\mathcal{F}$ is the set of functions obtained from composing
the hypothesis functions (which the learner choses) with a fixed,
non-negative loss function. Draw a training sample $\mathbf{X\sim }\mu ^{n}$
and let $\mathcal{F}_{\mathbf{X}}$ be the class of loss functions which have
zero empirical error, that i
\begin{equation*}
\mathcal{F}_{\mathbf{X}}=\left\{ f\in \mathcal{F}:\forall i\in \left[
\right] ,f\left( X_{i}\right) =0\right\} .
\end{equation*
Given a test variable $X\sim \mu $, which is independent of $\mathbf{X}$ and
a tolerance parameter $s$ we define the risk a
\begin{equation*}
\mathcal{R}\left( \mathbf{X,}s\right) =\Pr \left\{ \exists f\in \mathcal{F}_
	\mathbf{X}},\text{ }f\left( X\right) >s|~\mathbf{X}\right\} .
\end{equation*
As it stands the loss may be arbitrarily large on the bad event, whose
probability we want to bound, but on the good event it is uniformly bounded.
This is different from conventional risk bounds, which would involve the
expectation \thinspace $\mathbb{E}\left[ f\left( X\right) \right] $. If the
loss functions were uniformly bounded, we could convert a bound on $\mathcal
	R}\left( \mathbf{X,}s\right) $ into a risk bound of the for
\begin{equation*}
\forall f\in \mathcal{F}_{\mathbf{X}},\mathbb{E}\left[ f\left( X\right)
\right] \leq s+\mathcal{R}\left( \mathbf{X,}s\right) \sup_{f\in \mathcal{F
}\left\Vert f\right\Vert _{\infty }.
\end{equation*
We first assume that the functions in $\mathcal{F}$ have Lipschitz constant
at most $L$. The
\begin{eqnarray*}
	\mathcal{R}\left( \mathbf{X,}s\right)  &\leq &\Pr \left\{ \exists f\in
	\mathcal{F}:\forall i\in \left[ n\right] ,\text{ }f\left( X\right) -f\left(
	X_{i}\right) >s~|\mathbf{X}\right\}  \\
	&\leq &\Pr \left\{ \forall i\in \left[ n\right] ,~d\left( X,X_{i}\right)
	\frac{s}{L},|~\mathbf{X}\right\}  \\
	&=&\hat{M}\left( \mathbf{X},\frac{s}{L}\right) .
\end{eqnarray*
This bound is elementary, and probably unrealistic, but it is not trivial.
It is not hard to see that the Lipschitz condition and a hard margin
together still are no guarantee of generalization. Consider classification
with the input distribution concentrated and uniform on the set of basis
vectors of $\mathbb{R}^{D}$ with $D\gg n$. Then every labeling can be
realized by a function with Lipschitz constant $\sqrt{2}$. But the labeling
of the $D-n$ inputs not in the sample can only be at random, so the error
can be arbitrarily close to 1/2 by making $D$ large enough.

If the underlying metric is euclidean, the Lipschitz constants of modern
function classes are very hard to estimate, and even if they can be
estimated realistically (\cite{li2019preventing}) they are still so large as
to make the above bound useless for all but the most trivial learning
situations.

But now take $\left( \mathcal{X},d\right) $ to be a Hilbert-space and
replace the Lipschitz condition on the functions in the loss class with
Lipschitz conditions on their derivatives. The simplest case is $\beta
-smoothness of the functions in $\mathcal{F}$, which means that their
gradients $f^{\prime }$ are $\beta $-Lipschitz. Such conditions are not
unusual in theoretical discussions (\cite{Hardt15}). For such functions the
fundamental theorem of calculus implies the inequalit
\begin{equation*}
f\left( x\right) -f\left( y\right) \leq \left\langle f^{\prime }\left(
y\right) ,x-y\right\rangle +\frac{\beta }{2}\left\Vert x-y\right\Vert ^{2}.
\end{equation*
Now if $f\in \mathcal{F}_{\mathbf{X}}$ then $f^{\prime }\left( X_{i}\right)
=f\left( X_{i}\right) =0$, since $f$ is non-negative, differentiable and
vanishes at $X_{i}$. The risk bound therefore become
\begin{eqnarray*}
	\mathcal{R}\left( \mathbf{X,}s\right)  &\leq &\Pr \left\{ \exists f\in
	\mathcal{F}:\forall i\in \left[ n\right] ,\text{ }f\left( X\right) -f\left(
	X_{i}\right) >s~|\mathbf{X}\right\}  \\
	&\leq &\Pr \left\{ \forall i\in \left[ n\right] ,~\frac{\beta }{2}\left\Vert
	X-X_{i}\right\Vert ^{2}>s|~\mathbf{X}\right\} =\hat{M}\left( \mathbf{X}
	\sqrt{\frac{2s}{\beta }}\right) .
\end{eqnarray*
If $\beta $ and $L$ are of the same order and $s\ll \beta $ this is is a
great improvement over the previous bound, since $\sqrt{r}\gg r$ for $r\ll 1
.

\section{Open problems and limitations}

The principal problem left wide open by this paper is the efficient
computation of the function $h\left( \mathbf{X}\right) $, or a reasonable
upper bound thereof, from a given sample $\mathbf{X}$. Given such an
algorithm the bounds in the paper would also have a greater practical value,
if the constants were more moderate.

Another open question concerns the applications. Can the role of the missing
mass in supervised learning go much beyond the simple bounds sketched above?

\newpage

\bibliographystyle{plain}