text:
\begin{document}

\title{Jumping numbers of a unibranch curve on a smooth surface}
\author{Daniel Naie}

\begin{abstract}
A formula for the jumping numbers of a curve unibranch at a singular
point is established.  The jumping numbers are expressed in terms of
the Enriques diagram of the log resolution of the singularity, or
equivalently in terms of the canonical set of generators of the
semigroup of the curve at the singular point.
\end{abstract}

The jumping numbers of a curve on a smooth complex surface are a
sequence of positive rational numbers revealing information about the
singularities of the curve.  They extend in a natural way the
information given by the log-canonical threshold, the smallest jumping
number (see \cite{EiLa} for example).  They are periodic, completely
determined by the jumping numbers less than $1$, but otherwise
difficult to compute in general, even if a set of candidates is easy
to provide, \cf \cite[Lemma~9.3.16]{La}.

The aim of this paper is to give a formula for the jumping numbers of
a curve {\it unibranch} at a singular point.  A curve $C$ will be said
to be unibranch at a point $P$, if the analytic germ of $C$ at $P$ is
irreducible.  The formula is expressed in terms of the Enriques
diagram associated to the singularity, or equivalently (see
Theorem~\ref{th:main}) in terms of a minimal set of generators
$(\betabar_0,\betabar_1,\ldots,\betabar_g)$ of the
semigroup $S(C,P)$ of $C$ at $P$:
\begin{equation} \label{eq:main}
  \{\text{jumping numbers}<1\} =
  \bigcup_{j=1}^g \frac{1}{[m_j,\betabar_j]}\,
  R^{m_{j+1}}\bigg(\frac{m_j}{m_{j+1}},\frac{\betabar_j}{m_{j+1}}\bigg),
\end{equation}
where the $m_j$ are defined below.  Here
\[
  R^m(p,q) = \bigcup_{k=0}^{m-1}(kpq+R(p,q))
\]
and
\[
  R(p,q) = R^1(p,q) = \{ap+bq \mid a,b\in\NN^\ast,\, ap+bq<pq\}.
\]
The semigroup is defined by
$S(C)=\{\ord_P s\mid s\in\Oo_{C,P}\}$, the order of the local
section $s$ being computed using a normalization of $C$.  It is finitely
generated and a minimal set of generators
$(\betabar_0,\betabar_1,\ldots,\betabar_g)$ is constructed as follows
(see \cite[Theorem~4.3.5]{Wa}): $\betabar_0$ is the least element of
$S(C)$; set $m_1=\betabar_0$; $\betabar_j$ is the least element of
$S(C)$ not divisible by $m_j$ and $m_{j+1}=\gcd(m_j,\betabar_j)$.

To prove (\ref{eq:main}) we use the notion of {\it~relevant divisors}
of the minimal log resolution of $C$ at $P$, notion introduced in
\cite{SmTh}, and previously in \cite{FaJo} from the point of view of
valuations corresponding to Puiseux exponents: a relevant
divisor is an irreducible exceptional divisor that intersects at least
three other components of the total transform of $C$ through the
resolution.  When $C$ is unibranch at $P$, we show that the relevant
divisors account for all the jumping numbers.  This is the content of
Proposition~\ref{p:unibranch} and represents the key step of the
proof.  In general, if the curve is not unibranch, there are jumping
numbers that are not contributed by any relevant divisor (see
\cite[Example~2.2]{SmTh}).  Using Proposition~\ref{p:unibranch} and
the Enriques diagram associated to the minimal log resolution of $C$
at $P$, we compute the jumping numbers contributed by the relevant
divisors, and hence all the jumping numbers in
Theorem~\ref{th:mainEnriques}.  Finally, Theorem \ref{th:main} follows
as a consequence of Theorem \ref{th:mainEnriques} and of the
equivalence between the Enriques diagram and the semigroup $S(C)$.

The construction of the Enriques diagram as well as the definition of
the jumping numbers are recalled in \S\,\ref{s:one}.  The proof of
Theorem~\ref{th:mainEnriques} is given in \S\,\ref{s:three} together
with some necessary technical lemmas, whereas
Proposition~\ref{p:unibranch} is established in the last section.  The
explicit equivalence between the Puiseux characteristic, and hence the
semigroup, and the Enriques diagram of a unibranch curve is presented
in Theorem~\ref{th:enriques}.

In \cite{Ja}, Tarmo J\"arviletho obtained recently an explicit
description of the jumping numbers of a simple complete ideal $\ppp$
in a two dimensional regular local ring.  The jumping numbers are
expressed in terms of the Zariski exponents of the ideal.  Moreover
(see \cite[Proposition~9.2.8]{La} and also \cite[Theorem~9.4]{Ja}) the
jumping numbers $<1$ of the ideal $\ppp$ coincide to those of the
unibranch plane curve corresponding to a general element of $\ppp$,
and they amount to the jumping numbers given in (\ref{eq:main}).

If the unibranch curve is characterized by a single Puiseux exponent
$q/p$, with $\gcd(p,q)=1$, or equivalently if the semigroup is
generated by $p$ and $q$, the jumping numbers
\[
  \frac{ap+bq}{pq}<1,\quad a,b\in\NN^\ast,
\]
were computed by L.~Ein in \cite{Ei}, or by J.~A.~Howald in \cite{Ho}
as a particular case of his formula for the multiplier ideals of
monomial ideals.

It is a pleasure to acknowledge James Alexander's criticism on
questions of presentation and proportion after having read a
preliminary version of the paper, and also the friendly and useful
talks I have with him, with Michel Granger and Adam Parusinski.

\section{Preliminaries and notation}
\label{s:one}

In this section we recall the definition of the jumping numbers and
introduce the Enriques diagram associated to a minimal log resolution
of a curve at a singular point.  The diagram will be used to perform
the calculations of the jumping numbers.

\subsection{Log resolutions and Enriques diagrams}
\label{ss:enriquesDiagrams}
Let $C$ be a curve on a smooth surface with an isolated singularity at
$P$.  A minimal log resolution of $C$ at $P$ is the composition
$\mu:Y\to X$ of blowings up such that $\mu$ gives an isomorphism
$Y\smallsetminus\mu\inv(P)\to X\smallsetminus\{P\}$, the strict
transform $\Ctilde$ of $C$ is smooth, the support of the total
transform $\mu^\ast C$ has normal crossings and the number of blowings
up is minimal with these properties.

Let $Y=Y_{r+1}\to Y_r\to\cdots\to Y_1=X$ be a decomposition of
$\mu:Y\to X$ into successive blowings up with
$Y_{\alpha+1}=\Bl_{P_\alpha}Y_\alpha$.  Each point $P_\alpha$ is
infinitely near to $P=P_1$ and has an associated exceptional divisor
\footnote{The terms exceptional divisor and exceptional curve
will be used indifferently in the sequel.}
$E_\alpha$ on $Y_{\alpha+1}$.  Its strict
transform on $Y$ will also be denoted by $E_\alpha$ and its total
transform on $Y$ will be denoted by $W_\alpha$.
The strict transforms $E_\alpha$ and the the total transforms
$W_\alpha$ form two bases of the $\ZZ$-module
$\Lambda_C=\bigoplus_\alpha\ZZ E_\alpha\subset\Pic Y$.  In particular
\[
  \mu^\ast C = \Ctilde + D
  = \Ctilde + \sum_\alpha e_\alpha E_\alpha
  = \Ctilde + \sum_\alpha w_\alpha W_\alpha.
\]

\begin{rem}
  \label{r:theWeights}
The weight $w_\alpha$, the coefficient of the total transform
$W_\alpha$ in the divisor $\mu^\ast C-\Ctilde$, is the multiplicity of
the corresponding strict transform of $C$ at $P_\alpha$.
\end{rem}

If the curve $C$ is unibranch, then for any $\alpha$, the strict
transform of $C$ on $Y_\alpha$ has a unique singular point $P_\alpha$.
In particular there is a unique log resolution of the singular point
$C$.  In the general case the resolution is not unique; the ordering
of the exceptional divisors $E_\alpha$, or equivalently of the points
$P_\alpha$ might vary.  Nevertheless, the ordering of the points is
compatible with the partial order of the infinitely near points.  If
$\alpha<\beta$, then either $P_\beta$ is infinitely near to $P_\alpha$
or there is $\gamma<\alpha$ such that $P_\alpha$ and $P_\beta$ are
infinitely near to $P_\gamma$.

The combinatorics of the configuration of the exceptional curves
$E_\alpha$ on $Y$, or equivalently the geometric relation between the
infinitely near points $P_\alpha$, is encoded in the notion of {\it
proximity}: a point $P_\beta$ is said to be {\it proximate} to
$P_\alpha$ if $P_\beta$ lies on the strict transform of $E_\alpha$ on
$Y_\beta$.  A point that is infinitely near is always proximate to at
most two other points.  A point is said to be {\it free} if it is
proximate to exactly one other point and {\it satellite} if it is
proximate to two infinitely near points.

\begin{rem}
  \label{r:theOrder}
If $P_\beta$ is proximate to both $P_\alpha$ and $P_{\alpha'}$ and if
$\alpha<\alpha'$, then $P_{\alpha'}$ is infinitely near to $P_\alpha$.
Moreover, if the curve is unibranch, then $P_\beta$ is always
proximate to $P_{\beta-1}$.
\end{rem}

A convenient way to present the proximity relations is given by the
{\it proximity matrix} $\Pi=||p_{\alpha\beta}||$, where
$p_{\alpha\alpha}=1$ for any $\alpha$ and $p_{\alpha\beta}$ equals
$-1$ if $P_\beta$ is proximate to $P_\alpha$ and $0$ if not.  The
proximity matrix is upper unitriangular by the previous remark and
represents at the same time the decomposition matrix of the strict
transforms in terms of the total transforms on $Y$.  A simple but
useful consequence of this remark is the following lemma.

\begin{lem}
  \label{l:star}
Let $D=\sum_\alpha e_\alpha E_\alpha=\sum_\alpha w_\alpha W_\alpha$ be
the divisor associated to a log resolution of $C$ at $P$.
If $P_\beta$ is a satellite point
proximate to $P_{\alpha'}$ and $P_{\alpha''}$, then
\[
  e_\beta = e_{\alpha'}+e_{\alpha''}+w_\beta.
\]
\end{lem}

\proof
Use the relation
$E_\alpha=\sum_\beta p_{\alpha\beta}W_\beta=
W_\alpha-\sum_{P_\beta \text{ proximate to }P_\alpha}W_\beta$
to express the coefficients $w_\beta$ in terms of the coefficients
$e_\alpha$.
\qed

The resolution data of a curve $C$ at a singular point $P$ has been
encoded by Enriques in an appropriate weighted tree diagram now called
the {\it Enriques diagram} (see \cite{EnCh, SeKn, Ca, Ev}).  The tree
graphically represents the proximity relations of the infinitely near
points.

\begin{definition*}
An {\it Enriques tree} is a couple $(T,\epsilon_T)$, where
$T=T(\VVV,\EEE)$ is an oriented tree (a graph without loops) with a
single {\it root}, with $\VVV$ the set of vertices and $\EEE$ the set
of edges, and where $\epsilon_T$ is a map
\[
  \epsilon_T:
  \EEE \to \{\text{`slant'}, \text{`horizontal'},\text{`vertical'}\}.
\]
fixing the graphical representation of the edges.
An {\it Enriques diagram} is a weighted or labeled Enriques tree.
\end{definition*}

\begin{definition*}
Let $T$ be an Enriques tree.  A horizontal (respectively vertical)
{\it $L$-shape branch} of $T$ is a path of length $\geq1$ such that
all edges but the first, are horizontal (respectively vertical)
through $\epsilon_T$.  An $L$-shape branch is proper if it contains at
least two edges.  A {\it maximal $L$-shape branch} is an $L$-shape
branch that cannot be continued to a longer one.
\end{definition*}

The construction of the Enriques tree associated to a log resolution
of $C$ at $P$ is as follows.  The set of vertices is
$\VVV=\{P_1,\ldots,P_r\}$, \ie the set of infinitely near points; the
root of the tree is the proper point $P$.  There is an edge starting
at $P_\alpha$ and ending at $P_\beta$ if and only if $P_\beta$ is
proximate to $P_\alpha$ and, either $P_\beta$ is free, or $P_\beta$ is
satellite, proximate to $P_\alpha$ and $P_{\alpha'}$ and
$\alpha>\alpha'$.  There is an $L$-shape branch that starts at
$P_\alpha$ and ends at $P_\beta$ if and only if $P_\beta$ is proximate
to $P_\alpha$; there is either a horizontal or a vertical edge that
ends at $P_\alpha$ if and only if $P_\alpha$ is satellite.  To
normalize the shape of the tree it is assumed that an edge that starts
at a free point and ends at a satellite point is horizontal.  The
weights $w_\alpha$ are given by the coefficients of the total
transforms in $\mu^\ast C=\Ctilde+\sum_\alpha w_\alpha W_\alpha$.

It is to be noticed that $E_\alpha$ and $E_\beta$ intersect on $Y$ if
and only if there is a maximal $L$-shape branch that starts at
$P_\alpha$ and ends at $P_\beta$.

\begin{exa}[Definition of $T_{p,q}$]
  \label{ex:tpq}
Let $p<q$ be relatively prime positive integers and let $C$ be defined
locally at $P$ by $x^p-y^q=0$.  The Enriques tree $T_{p,q}$ associated
to the minimal log resolution of $C$ at $P$ is defined as follows.
Consider the Euclidean algorithm: $r_0=a_1r_1+r_2$, \ldots,
$r_{m-2}=a_{m-1}r_{m-1}+r_{m}$ and $r_{m-1}=a_mr_m$, with $r_0=q$ and
$r_1=p$.  Set
\[
  \VVV=\{P_\alpha \mid 1\leq\alpha\leq a_1+\cdots+a_m=r\}
\]
and
\[
  \EEE=\{[P_\alpha P_{\alpha+1}] \mid
  1\leq\alpha\leq a_1+\cdots+a_m-1\}.
\]
The map $\epsilon$ is locally constant on the $a_j$ edges
$[P_\alpha P_{\alpha+1}]$ with
$a_1+\cdots+a_{j-1}+1\leq\alpha\leq a_1+\cdots+a_j$.  The first
constant value of $\epsilon$---on the first $a_1$ edges---is `slant'.
The other constant values are alternatively either `horizontal' or
`vertical', starting with `horizontal'.  The Enriques trees $T_{5,7}$
is
\begin{center}
\begin{pspicture}(0,0)(10,2.25)
  \psset{arrows=->,radius=.1,unit=5ex}
  \rput(5,1){
    \Cnode(-.71,-.71){1}
    \Cnode(0,0){2}
    \Cnode(1,0){3}
    \Cnode(2,0){4}
    \Cnode(2,1){5}
    \ncline{1}{2}
    \ncline{2}{3}
    \ncline{3}{4}
    \ncline{4}{5}
    \uput{\labelsep}[l](-.71,-.71){$P_1$}
    \uput{\labelsep}[u](0,0){$P_2$}
    \uput{\labelsep}[u](1,0){$P_3$}
    \uput{\labelsep}[r](2,0){$P_4$}
    \uput{\labelsep}[r](2,1){$P_5$}}
\end{pspicture}
\end{center}
and together with the weights $5,2,2,1,1$, it becomes the Enriques
diagram $\tT_{5,7}$ of the minimal log resolution of $x^5-y^7=0$.  In
general, the Enriques diagram $\tT_{p,q}$ that encodes the minimal log
resolution of the curve $x^p-y^q=0$ consists of the Enriques tree
$T_{p,q}$ together with the corresponding remainders of the Euclidean
algorithm as weights.
\end{exa}

\begin{cor}
  \label{c:star}
Let $D=\sum_\alpha e_\alpha E_\alpha$ be the divisor associated to the
Enriques diagram $\tT_{p,q}$.  If $P_\beta$ is a satellite point
proximate to $P_{\alpha'}$ and $P_{\alpha''}$, then
\[
  e_\beta = e_{\alpha'}+e_{\alpha''}+r_\beta.
\]
\end{cor}

\proof
By Lemma \ref{l:star} and the interpretation of the weights of
$T_{p,q}$.
\qed

\subsection{Multiplier ideals and jumping numbers}
\label{ss:multiplierIdeals}
We briefly recall the notions of multiplier ideals and jumping
numbers.  We refer the reader to \cite{La} for the results cited
below.  In the context of curves on surfaces, we define the relevant
divisors following \cite{SmTh}.

If $X$ is a smooth variety, $D\subset X$ an effective $\QQ$-divisor
and $\mu\colon Y\to X$ a {\it log resolution} for $D$, then
$\Jj(D)=\mu_\ast\Oo_Y(K_\mu-\floor{\mu^\ast D})$ is an ideal sheaf on
$X$
\footnote{The integral part or round-down $\floor{D}$ of $D$ is the
integral divisor $\floor{D} = \sum_\alpha\floor{c_\alpha}D_\alpha$,
where for $c\in\QQ$, $\floor{x}$ denotes the greatest integer
$\leq c$.}.
The divisor $K_\mu$ is the relative canonical divisor of the map
$\mu$.  The ideal sheaf $\Jj(D)$ is independent of the choice of the
resolution and is called the multiplier ideal of $D$.  When $\mu$ is
the resolution of $D$ at a singular point $P$, the multiplier ideal
may be denoted by $\Jj(D)_P$.  The sheaf
$\Oo_Y(K_\mu-\floor{\mu^\ast D})$ computing the multiplier ideal
satisfies, for any $i>0$, the local vanishing result
\[
  R^i\mu_\ast\Oo_Y(K_\mu-\floor{\mu^\ast D})=0.
\]

\begin{likethm}[Definition-Lemma]\rm (see \cite{EiLa})
Let $D\subset X$ be an effective divisor and $P\in D$ be a fixed
point.  Then there is an increasing discrete sequence of rational
numbers $\xi_i=\xi(D,P)$,
\[
  0 = \xi_0 < \xi_1 < \cdots
\]
such that $\Jj(\xi D)_P = \Jj(\xi_i D)_P$ for every
$\xi\in[\xi_i,\xi_{i+1})$, and
$\Jj(\xi_{i+1}D)_P\varsubsetneq\Jj(\xi_i D)_P$.  The rational numbers
$\xi_i$ are called {\it the jumping numbers} of $D$ at $P$.
\end{likethm}

The jumping numbers of $D$ at $P$ are periodic (see
\cite[Theorem~9.3.24]{La}) and that they are completely determined by
the ones that are less than $1$.  Therefore, in the sequel, we will
talk about the jumping numbers $<1$.

We have anticipated in the introduction that a set of candidates for
the jumping numbers is easy to provide in case $C$ is a curve singular
at $P$ on the smooth surface $X$.  Indeed, let $\mu:Y\to X$ be a log
resolution of $C$ with $\mu\inv(P)=\cup_{\alpha=1}^rE_r$.  Then
$K_\mu=\sum_{\alpha=1}^r W_\alpha=\sum_{\alpha=1}^rk_\alpha E_\alpha$,
with $k_\alpha>0$.  Writing
$\mu^\ast C=\Ctilde+\sum_{\alpha=1}^r e_\alpha E_\alpha$, form the
proof of the above lemma it follows that the set of jumping numbers
must be contained in the set of the rational numbers
$(k_\alpha+n)/e_\alpha$, where $1\leq\alpha\leq r$ and $n$ is a
positive integer.

\begin{definition}[see \cite{SmTh}]
Let $\xi=(k_\alpha+n)/e_\alpha$ be a jumping number of $C$ at $P$.
The exceptional divisor $E_\alpha$ is said to contribute the jumping
number $\xi$ if
\[
  \Jj(\xi\cdot C) \varsubsetneq
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E_\alpha).
\]
\end{definition}

If the above inclusion is satisfied for $\xi=(k_\alpha+n)/e_\alpha$,
then $\xi$ is a jumping number, since for any sufficiently small
$\epsilon>0$,
\[
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E_\alpha)
  \subset \mu_\ast\Oo_Y(K_\mu-\floor{(\xi-\epsilon)\mu^\ast C})
  = \Jj((\xi-\epsilon)\cdot C).
\]
In \cite{SmTh}, on the one hand, Theorem 3.1 shows that a divisor
$E_\alpha$ contributes to the sequence of jumping numbers if and only
if $E_\alpha$ has non-trivial intersection with at least three of the
other components of the total transform $\mu^\ast C$
\footnote{The same characterization was established in
\cite[Lemma~2.11]{FaJo} in an analytical context.}.
On the other hand, it is also shown that not all jumping numbers are
contributed by exceptional divisors.  For example no $E_\alpha$
contributes the log-canonical threshold $1/2$ of the curve defined by
$(x^2-y^3)(x^3-y^2)=0$.  It is to be noticed that this curve is not
unibranch at the origin.  The essential step in the computation of the
jumping numbers of a unibranch curve is that each jumping number is
contributed by an exceptional divisor $E_\alpha$.  This is the content
of the forthcoming Proposition~\ref{p:unibranch}.

\begin{exa*}
In \cite{Ho} it is shown that if the
Puiseux exponent of $C$ at $P$ is $p/q$, with $\gcd(p,q)=1$, then the
jumping numbers less than $1$ of $C$ are $a/p+b/q<1$ with $a$ and $b$
positive integers.  There is only one divisor that contributes all
these jumping numbers, namely the last exceptional divisor.
\end{exa*}

\begin{definition}
An exceptional divisor $E_\rho$ is said to be a {\it relevant
divisor}, or $\rho$ is said to be a {\it relevant position} of $C$ at
$P$, if $E_\rho\cdot E_\rho^0\geq3$, where
$E_\rho^0=(\mu^\ast C)_{red}-E_\rho$.  The set of relevant positions
of $C$ at $P$ will be denoted by $\RRR_P$.
\end{definition}

\begin{rem}
  \label{r:branchBasis}
A relevant position $\rho$ is easy to identify on the Enriques tree.
Either it corresponds to a satellite point from which a 'slant'
edge starts, or it corresponds to a non-zero coefficient in the
expression of $\mu^\ast C-\Ctilde$ in the {\it branch basis}.  To
define this basis,
let $\Pi$ be the proximity matrix.  The
intersection matrix of the curves $W_\alpha$ is minus the
identity.  It follows that there exists effective
\footnote{$||B_1\ldots B_s||= ^t\!\!\Pi\inv ||W_1\ldots W_s||$ and the
matrix $\Pi\inv$ has non negative entries since it decomposes the
$W_\alpha$ in terms of the $E_\alpha$.}
divisors $B_\alpha$ that form the dual basis to $(-E_\alpha)$ with
respect to the intersection form for the lattice
$\Lambda_C=\bigoplus_\alpha \ZZ E_\alpha$.  This basis is the
{\it branch basis}
\footnote{The divisor $\mu^\ast C-\Ctilde$ may be expressed in three ways.  Its
expression in the branch basis reflects the branches of
$\Ctilde$---the analytically irreducible components of $\Ctilde$ above
$P$.  Its expression in the basis of total transforms $(W_\alpha)$
reflects the multiplicities of $C$ and the multiplicities of its
strict transforms along the resolution process, as it has been noticed
in Remark~\ref{r:theWeights}.  Finally, its expression in the basis
$(E_\alpha)$, the basis of strict transforms, gives the coefficients
necessary to compute the multiplier ideals associated to $C$.}.

Going back to the relevant position $\rho$ corresponding to a non-zero
coefficient in the branch basis, we notice that this position
might be represented on the tree using arrowhead vertices, the number
of arrows being given by the coefficient $b_\rho$ in $\mu^\ast
C-\Ctilde=\sum_\alpha b_\alpha B_\alpha$.  We would obtain in
this way an augmented Enriques tree, equivalent to the Enriques
diagram $\tT$.
\end{rem}

\section{Jumping numbers of a unibranch curve}
\label{s:three}

The aim of this section is to prove Theorem~\ref{th:mainEnriques}.  To
formulate it we need to make some considerations about the {\it
unibranch trees}.  A unibranch tree is an Enriques tree having
out-valence $1$ for any of its vertices.  The trees $T_{p,q}$
introduced in Example~\ref{ex:tpq} are unibranch and represent the
simplest such trees in the sens that there is no slant edge starting
at a satellite point.  If a curve is unibranch at $P$, then the
Enriques diagram is given by a unibranch Enriques tree with the last
element in the branch basis $(B_\alpha)$ as the associated divisor.
The next definition allows us to see a unibranch tree as
being constructed from $T_{p,q}$ trees.

\begin{definition}
Let $T$ and $T'$ be unibranch Enriques trees with
$\VVV(T)=\{P_1,\ldots,P_r\}$ and $\VVV(T')=\{P'_1,\ldots,P'_{r'}\}$.
The {\it connected sum} of $T$ and $T'$ is the Enriques tree $T\#T'$
with the set of vertices
$\VVV(T\#T')=\VVV(T)\cup\VVV(T')/\{P_r=P'_1\}$, the set of edges
$\EEE(T\#T')=\EEE(T)\cup\EEE(T')$ and the map $\epsilon_{T\#T'}$
defined by $\epsilon_T$ and $\epsilon_{T'}$ through the natural
restrictions.
\end{definition}

\begin{exa}
  \label{ex:asUsual}
The minimal log resolution of $(x^3-y^2)^2-4x^5y-x^7=0$ needs five blowings
up with the following Enriques diagram.
\begin{center}
\begin{pspicture}(0,0)(3,2.25)
  \psset{arrows=->,radius=.1,unit=5ex}
  \rput(1,1){
    \Cnode(-.71,-.71){1}
    \Cnode(0,0){2}
    \Cnode(1,0){3}
    \ncline{1}{2}
    \ncline{2}{3}
    \uput{\labelsep}[l](-.71,-.71){$4$}
    \uput{\labelsep}[u](0,0){$2$}
    \uput{\labelsep}[u](1,0){$2$}}
  \rput(2.71,1.71){
    \Cnode(-.71,-.71){1}
    \Cnode(0,0){2}
    \Cnode(1,0){3}
    \ncline{1}{2}
    \ncline{2}{3}
    \uput{\labelsep}[u](0,0){$1$}
    \uput{\labelsep}[u](1,0){$1$}}
\end{pspicture}
\end{center}
The Enriques tree is the connected sum $T_{2,3}\#T_{2,3}$.
\end{exa}

\begin{thm}
  \label{th:mainEnriques}
Let $C$ be a curve unibranch at $P$ with the Enriques tree of the
minimal log resolution $S=T_{p_1,q_1}\#\cdots\#T_{p_g,q_g}$.  Set
$\qbar_1=q_1$ and
\[
  \qbar_j = \frac{m_{j-1}}{m_{j+1}}\,\qbar_{j-1}-p_j+q_j
\]
for any $2\leq j\leq g$, where $m_j = p_j\cdots p_g$ for any
$1\leq j\leq g$, and $m_{g+1}=1$.  Then the jumping numbers less
that $1$ of $C$ at $P$ are given by
\[
  \bigcup_{j=1}^g \frac{1}{m_j \qbar_j}\,
  R^{m_{j+1}}(p_j,\qbar_j),
\]
where
\[
  R^{m_{j+1}}(p_j,\qbar_j)
  = \bigcup_{k=0}^{m_{j+1}-1}
  \big( kp_j\qbar_j+\{ap_j+b\qbar_j \mid a,b\in\NN^\ast,\,
  ap_j+b\qbar_j<p_j\qbar_j\} \big).
\]
\end{thm}

We begin by describing the sets $R^m(p,q)$ as they will appear in the
proof of Theorem~\ref{th:mainEnriques}.  For the purposes of this
section we denote by $\ceil{x}$ the round-up of $x$, \ie the least
integer $\geq x$, and by $\fpart{x}=x-\floor{x}$ the fractional part of
$x$.

Let $2\leq p<q$ be relatively prime integers and let $m$ be a positive
integer.  Setting $q'$ to be the positive integer that satisfies
$q'<p$ and $qq'=-1\mod p$, we define $R^m(p,q)$ as the set of integers
$k$, $1\leq k<mpq$, such that
\[
  \fpart{\frac{k}{pq}} + \fpart{\frac{q'k}{p}} > 1.
\]
If $m=1$ we shall denote the set $R^1(p,q)$ by $R(p,q)$.
Clearly
\begin{equation} \label{eq:rInGeneral}
  R^m(p,q) = \bigcup_{j=0}^{m-1}(jpq+R(p,q))
\end{equation}
and $R(p,q)$ is computed in the following Proposition.

\begin{pro}
  \label{p:theSetR}
\[
  R(p,q) = \{ap+bq \mid a,b\in\NN^\ast,\, ap+bq<pq\}
\]
\end{pro}

\proof
If $k_0\in R(p,q)$ then
\[
  \frac{k_0+p}{pq} + \fpart{\frac{q'(k_0+p)}{p}}
  = \frac{k_0}{pq}+\frac{1}{q} + \fpart{\frac{q'k_0}{p}}
  > 1,
\]
hence $k_0+p\in R(p,q)$.  It follows that to determine $R(p,q)$ it is
sufficient to determine the first element belonging to $R(p,q)$ in
each equivalence class mod $p$.  Clearly the multiples of $p$ do not
belong to $R(p,q)$.  So such an element is of the form $jq+Np$, with
$j\in\{1,\ldots,p-1\}$ and $N$ a positive integer.  Using the
hypothesis $qq'=-1\mod p$,
\[
  \frac{jq+Np}{pq}+\fpart{\frac{q'(jq+Np)}{p}}
  = \frac{j}{p}+\frac{N}{q}+1-\frac{j}{p}
  = 1+\frac{N}{q}.
\]
So the minimal element in each equivalence class different from zero
is $jq+p$.  The result follows.
\qed

As we have anticipated in \S\,\ref{s:one}, the computation of the
jumping numbers depends on the fact that each one of them is
contributed by an irreducible exceptional divisor.  More precisely we
have the following proposition whose proof will be given in
the last section.

\begin{pro}
  \label{p:unibranch}
Let $C$ be a unibranch curve at $P$ and let $\mu$ be a log resolution
such that $\mu^\ast C=\Ctilde+\sum_{\alpha\in\VVV}e_\alpha E_\alpha$.
If $\xi$ is a jumping number of $C$ at $P$, then there exists $\beta$
a relevant position such that $\floor{\xi e_\beta}=\xi e_\beta$ and
such that $E_\beta$ contributes $\xi$.
\end{pro}

\likeproof[Proof of Theorem~\ref{th:mainEnriques}]
By Proposition~\ref{p:unibranch} each jumping number is contributed by
a relevant divisor and it is sufficient to compute the jumping numbers
contributed by each relevant divisor.  Remember that a relevant
divisor is an exceptional divisor that satisfies
$E_\rho\cdot E_\rho^0\geq3$.

If $\rho$ is a relevant position, then tensoring the exact sequence
\[
  0 \lra
  \Oo_Y \lra
  \Oo_Y(E_\rho) \lra
  \Oo_{E_\rho}(E_\rho|_{E_\rho}) \lra
  0
\]
with $\Oo_Y(K_\mu-\floor{\xi\mu^\ast C})$ and
pushing it down to $X$ give
\begin{multline*}
 0 \lra
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}) \lra
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E_\rho) \\
  \lra \mu_\ast\Oo_{E_\rho}(K_{E_\rho}-\floor{\xi\mu^\ast C}|_{E_\rho})
  \lra 0
\end{multline*}
thanks to the local vanishing.  Since $E_\rho$ is a projective line,
$\xi$ is a jumping number contributed by $E_\rho$ if and only if
$\xi e_\rho$ is an integer and
\begin{equation}
  \label{eq:mainInequality}
  -\floor{\xi\mu^\ast C} \cdot E_\rho \geq 2.
\end{equation}
Assume that $\xi e_\rho$ is an integer.  Let $r_j$ be the number of
vertices of the Enriques tree $T_{p_j,q_j}$ and set
$s=r_1+\cdots+r_g-(g-1)$, the number of vertices of $S$.  There are
two cases to be considered: either $\rho=s$, \ie $\rho$ is the highest
point of the Enriques tree, or $\rho$ is a relevant position different
from $s$.  Whatever the case, the study of the numbers
$\floor{\xi\mu^\ast C} \cdot E_\rho$ depends on the control of the
coefficients $e_\alpha$ in
$\mu^\ast C=\Ctilde+\sum_{\alpha=1}^s e_\alpha E_\alpha$.  The
following technical lemmas \ref{l:eCoeff}, \ref{l:eCoeffBefore_r},
\ref{l:eRelevantCoeff} and \ref{l:eCoeffAfter_r}
give explicit formulae for these
coefficients and also, some other useful numerical relations.

Some notation is in order.  Let $T$ be an Enriques tree.  Denote by
$E_\alpha^T$ the elements of the basis of strict transforms, by
$W_\alpha^T$ the elements of the basis of total transforms and by
$B_\alpha^T$ the elements of the branch basis that has been introduced
in Remark~\ref{r:branchBasis}.  If
$\Lambda=\bigoplus_\alpha E_\alpha^T$, then $(e_\alpha^T)$ will denote
the basis for $\Lambda^\ast$, dual to $(E_\alpha^T)$.  Similarly,
$(w_\alpha^T)$ will denote the dual basis to the basis of total
transforms and $(b_\alpha^T)$ the dual basis to the branch basis.

Let $p<q$ be two relatively prime positive integers.  Consider the
Euclidean algorithm $r_0=a_1r_1+r_2$,
\ldots, $r_{m-2}=a_{m-1}r_{m-1}+r_{m}$ and $r_{m-1}=a_mr_m$, with
$r_0=q$ and $r_1=p$.  Define as in \cite[Lemma~A.8]{Na} two finite
sequences
 $(f_j)_{-1\leq j\leq m}$ and
$(\delta_j)_{1\leq j\leq m+1}$ by
\begin{equation}
  \label{eq:sequences}
\begin{aligned}
  f_j &= f_{j-2}+a_j\delta_j, \quad\text{for any } 1\leq j\leq m, \\
  \delta_j &= \delta_{j-2}+a_{j-1}\,f_{j-2},
  \quad\text{for any } 2\leq j\leq m+1, \quad
\end{aligned}
\end{equation}
such that $f_{-1}=f_0=0$ and $\delta_0=\delta_1=1$.  It is easy to show
that the remainder $r_j$ in the Euclidean algorithm is given by
$-f_{j-1}q+\delta_jp$ if $j$ is odd and by $\delta_jq-f_{j-1}p$ if $j$
is even.  Furthermore, if $m$ is odd, then $f_m=q$ and
$\delta_{m+1}=p$, and if $m$ is even, then $f_m=p$ and
$\delta_{m+1}=q$.  We have the following lemma that computes various
coefficients for the Enriques tree $T_{p,q}$.

\begin{lem}
  \label{l:eCoeff}
Let $T=T_{p,q}$.  Then for any $0\leq j\leq m-1$ and any
$1\leq k\leq a_{j+1}$,
\[
  e_{a_1+\cdots+a_j+k}^T(B_r^T) =
  \begin{cases}
    (f_{j-1}+k\delta_{j+1})\,p & \textql{if $j$ is even}\\
    (f_{j-1}+k\delta_{j+1})\,q & \textql{if $j$ is odd}
  \end{cases}
\]
and
\[
  e_{a_1+\cdots+a_j+k}^T(W_1^T) =
  \begin{cases}
    \delta_j+kf_j & \textql{if $j$ is even}\\
    f_{j-1}+k\delta_{j+1} & \textql{if $j$ is odd}.
  \end{cases}
\]
\end{lem}

\proof
We proceed by
induction using Corollary~\ref{c:star}, the relations
(\ref{eq:sequences}) and the relations quoted after them.  For the
computation of $e_{a_1+\cdots+a_j+k}^T(B_r^T)$, we suppose
that $j$ is even, the case $j$ odd being similar.  If $k=1$, then
\[
\begin{split}
  e_{a_1+\cdots+a_j+1}^T(B_r^T)
  &= e_{a_1+\cdots+a_{j-1}}^T(B_r^T) + e_{a_1+\cdots+a_j}^T(B_r^T)
  + r_{j+1} \\
  &= f_{j-1}p+f_jq+(-f_jq+\delta_{j+1}p) \\
  &= (f_{j-1}+\delta_{j+1})\,p.
\end{split}
\]
Now, if $1<k\leq a_{j+1}$, then
\[
\begin{split}
  e_{a_1+\cdots+a_j+k}^T(B_r^T)
  &= e_{a_1+\cdots+a_{j}}^T(B_r^T) + e_{a_1+\cdots+a_j+k-1}^T(B_r^T)
  + r_{j+1} \\
  &= f_{j}q + (f_{j-1}+(k-1)\delta_{j+1})\,p + (-f_jq+\delta_{j+1}p) \\
  &= (f_{j-1}+k\delta_{j+1})\,p.
\end{split}
\]
As for the second equality, if we suppose again that $j$ is even,
we get
\[
  e_{a_1+\cdots+a_j+1}^T(W_1^T)
  = e_{a_1+\cdots+a_{j-1}}^T(W_1^T) + e_{a_1+\cdots+a_j}^T(W_1^T)
  = \delta_j+f_j
\]
for $k=1$, and
\[
  e_{a_1+\cdots+a_j+k}^T(W_1^T)
  = e_{a_1+\cdots+a_{j}}^T(W_1^T) + e_{a_1+\cdots+a_j+k-1}^T(W_1^T)
  = f_j+(\delta_j+(k-1)f_j)
\]
for $1<k\leq a_{j+1}$.
\qed

The remaining lemmas will allow us to compute the $e_\alpha$
coefficients for $\mu^\ast C-\Ctilde$ for a unibranch curve.

\begin{lem}
  \label{l:eCoeffBefore_r}
Let $S=T\# T'$ be a unibranch Enriques tree.  If $r$ is the number of
vertices of $T$ and $s$ is the number of vertices of $S$, then
\[
  e_{\alpha}^S(B_{s}^S) =
  w_r^S(B_s^S)\,e_\alpha^T(B_r^T)
\]
for any $1\leq \alpha\leq r$.
\end{lem}

\proof
Write $B_{s}^S=\sum_\beta w_\beta^S(B_{s}^S)\,W_\beta^S$ using the
basis of total transforms.  Since the proximity matrix in upper
unitriangular, if $1\leq \alpha\leq r$, then only the divisors
$W_\beta$ with $\beta\leq r$ count when computing
$e_{\alpha}^S(B_{s}^S)$.  For $\beta\leq r$, we have
\[
  w_\beta^S(B_{s}^S) = w_\beta^S( w_r^S(B_{s}^{S})\,B_r^S)
  = w_r^S(B_s^S)\,w_\beta^S(B_r^S) = w_r^S(B_s^S)\,w_\beta^T(B_r^T).
\]
So
\[
\begin{split}
  e_\alpha^S(B_s^S)
  &= w_r^S(B_s^S)\sum_{\beta\leq
    r}w_\beta^T(B_r^T)e_\alpha^S(W_\beta^S)\\
  &= w_r^S(B_s^S)\,e_\alpha^T\big(
  \sum_{\beta\leq r}w_\beta^T(B_r^T)W_\beta^T\big),
\end{split}
\]
since $e_\alpha^S(W_\beta^S)=e_\alpha^T(W_\beta^T)$, and the result
follows.
\qed

\begin{lem}
  \label{l:eRelevantCoeff}
Let
\[
  S = T_{p_1,q_1} \# T_{p_2,q_2} \#\cdots\# T_{p_g,q_g}
\]
with $r_j$ the number of vertices of the tree $T_{p_j,q_j}$, and let
$s=r_1+\cdots+r_g-(g-1)$ be the number of vertices of $S$.
If $\qbar_1=q_1$ and
\[
  \qbar_j = p_{j-1}p_j\qbar_{j-1}-p_j+q_j
\]
for any $2\leq j\leq g$, then
\[
\begin{aligned}
  w_{r_1+\cdots+r_j-(j-1)}^S(B_s^S) &= p_j\cdots p_g\\
  e_{r_1+\cdots+r_j-(j-1)}^S(B_s^S) &= p_j\cdots p_g\qbar_j
\end{aligned}
\]
for any $1\leq j\leq g$.
\end{lem}

\proof
Set $T_j=T_{p_j,q_j}$ for any $j$.  The first identity is clear by
induction since using the proximity relations,
\[
  w_{r_1+\cdots+r_j-(j-1)}^S(B_s^S) =
  w_1^{T_{j+1}\#\cdots\# T_g}
  (B_{r_{j+1}+\cdots+r_g-(g-j-1)}^{T_{j+1}\#\cdots\# T_g}).
\]
As for the second, by Lemma~\ref{l:eCoeffBefore_r},
\[
\begin{split}
  e_{r_1+\cdots+r_j-(j-1)}^S(B_s^S)
  &= w_{r_1+\cdots+r_j-(j-1)}^S(B_s^S)\,
  e_{r_1+\cdots+r_j-(j-1)}^{T_1\#\cdots\# T_j}
    (B_{r_1+\cdots+r_j-(j-1)}^{T_1\#\cdots\# T_j}) \\
  &= p_{j+1}\cdots p_gp_j\qbar_j.
\end{split}
\]
\qed

\begin{lem}
  \label{l:eCoeffAfter_r}
Let $S=T'\# T$ be a unibranch Enriques tree with $T=T_{p,q}$.  Let
$r'$ be the number of vertices of $T'$ and $r$ the number of vertices
of $T$.  Then
\[
  e_{r'-1+\alpha}^S(B_{r'-1+r}^S)
  = \big( e_{r'}^{T'}(B_{r'}^{T'})-1\big)\,
  e_\alpha^T(W_1^T)\, p + e_\alpha^T(B_r^T)
\]
for any $1\leq \alpha\leq r$.
\end{lem}

\proof
Set $s=r'+r-1$, the number of vertices of $S$.
Using that
\[
  w_{r'-1+\beta}^{S}(B_{s}^{S})=w_{\beta}^T(B_r^T)
\]
for any $2\leq\beta\leq r$ and discarding the exponent $S$, we have
\[
\begin{split}
  e_{r'-1+\alpha}(B_{s}) &=
  e_{r'-1+\alpha}\bigg(\sum_{\gamma=1}^{r'}w_\gamma(B_{s})\,W_\gamma
  + \sum_{\beta=2}^rw_{r'-1+\beta}(B_{s})\,W_{r'-1+\beta}
  \bigg)\\
  &= e_{r'-1+\alpha}\bigg(
  w_{r'}(B_{s})\,B_{r'} - w_{r'}(B_{s})\,W_{r'}
  + \sum_{\beta=1}^rw_{r'-1+\beta}(B_{s})\,W_{r'-1+\beta}
  \bigg)\\
  &= e_{r'-1+\alpha}
  \big( w_1^T(B_r^T)\,B_{r'} - w_1^T(B_r^T)\,W_{r'} \big)
  + e_\alpha^T\bigg(
  \sum_{\beta=1}^rw_\beta^T(B_r^T)\,W_\beta^T
  \bigg)\\
  &=  w_1^T(B_r^T)\,
  e_{r'-1+\alpha}\big(e_{r'}^{T'}(B_{r'}^{T'})W_{r'}-W_{r'}\big)
  + e_\alpha^T(B_r^T),
\end{split}
\]
and hence the result, since
$e_{r'-1+\alpha}(W_{r'})= e_\alpha^T(W_1^T)$ and $w_1^T(B_r^T)=p$.
\qed

\likeproof[End of the proof of Theorem~\ref{th:mainEnriques}]
We need to study $\floor{\xi\mu^\ast C} \cdot E_\rho$ when $\rho$ is a
relevant position and $\xi e_\rho$ is an integer.  We have already
noticed that there are two cases to be considered: either $\rho=s$ or
$\rho\neq s$, where $s$ is the number of vertices of
$S=T_{p_1,q_1}\#\cdots\#T_{p_g,q_g}$.

In the former case, set $T=T_{p_g,q_g}$.  Then
\[
  \floor{\xi\mu^\ast C} \cdot E_{s}^S
  = \Big(
  \floor{\xi e_{s-a_m}}E_{r_g-a_m}^{T}+
  \floor{\xi e_{s-1}}E_{r_g-1}^{T}+
  \xi e_{s}E_{r_g}^{T}
  \Big) \cdot E_{r_g}^{T},
\]
where $a_m$ is the last quotient in the Euclidean algorithm for $q_g$
and $p_g$. By Corollary~\ref{c:star}, $e_{s}=e_{s-a_m}+e_{s-1}+1$.
By Lemma~\ref{l:eRelevantCoeff}, $e_{s}=p_g\qbar_g$ with
$p_g<\qbar_g$, relatively prime integers.
Then, by Lemma~\ref{l:eCoeffAfter_r}
\[
  e_{s-\alpha}
  = (p_{g-1}\qbar_{g-1}-1)\, p_g\, e_{r_g-\alpha}^T(W_1^T)
  + e_{r_g-\alpha}^T(B_{r_g}^T)
\]
for any $1\leq\alpha<r_g$.  One of the two positions $r_g-m$ and
$r_g-1$ must belong to a proper horizontal $L$-shape branch.  We
suppose that $r_g-1$ satisfies this, the argument being similar in the
other case.  By Lemma~\ref{l:eCoeff},
$e_{r_g-1}^T(B_{r_g}^T) = e_{r_g-1}^T(W_1^T)\, q_g$, \ie
\[
  e_{s-1} = (p_{g-1}\qbar_{g-1}-1)\, p_g\, e_{r_g-1}^T(W_1^T)
  + e_{r_g-1}^T(B_{r_g}^T)
  = e_{r_g-1}^T(W_1^T)\, \qbar_g,
\]
and $p_g$ divides $e_{s-m}$.  Set $M=e_{r_g-1}^T(W_1^T)$.  From
$p_g\qbar_g = e_{s-m}+M\qbar_g+1$
it follows that
\[
  M\qbar_g = -1 \mod p_g.
\]
Set $x=\xi e_{s}=\xi p_g\qbar_g$.  It is an integer
satisfying $1\leq x<p_g\qbar_g$.  Then putting everything together,
\[
\begin{split}
  -\floor{\xi\mu^\ast C} \cdot E_{s}
  &=
  -\floor{\frac{x}{p_g\qbar_g}(p_g\qbar_g-M\qbar_g-1)}
  -\floor{\frac{x}{p_g\qbar_g}\,M\qbar_g}+x\\
  &=\ceil{\frac{Mx}{p_g}+\frac{x}{p_g\qbar_g}}-\floor{\frac{Mx}{p_g}}.
\end{split}
\]
Hence the inequality (\ref{eq:mainInequality}) is satisfied, \ie
$-\floor{\xi\mu^\ast C} \cdot E_\rho \geq 2$, if and only if
\[
  \fpart{\frac{Mx}{p_g}}+\frac{x}{p_g\qbar_g}>1
\]
By Proposition~\ref{p:theSetR} this is equivalent to
$x\in R(p_g,\qbar_g)$.

In the second case, if $\rho=r_1+\cdots+r_j-(j-1)$ is a relevant
position different from $s$, the highest one, set $r=r_{j}$,
$T=T_{p_{j},q_{j}}$ and $S=T'\# T\# T''$.  When computing
$\floor{\xi\mu^\ast C}\cdot E_\rho$ we distinguish two situations
according to whether $a''_1=1$ or not, where $a''_1,a''_2\ldots$ are
the quotients in the Euclidean algorithm for $q_{j+1}$ and $p_{j+1}$.
In case $a''_1\neq1$,
\[
\begin{split}
  \floor{\xi\mu^\ast C} \cdot E_\rho
  &= \Big(
  \floor{\xi e_{\rho-a_m}}E_{\rho-a_m}+
  \floor{\xi e_{\rho-1}}E_{\rho-1}+
  \xi e_\rho E_\rho+
  \floor{\xi e_{\rho+1}}E_{\rho+1}
  \Big) \cdot E_\rho \\
  &= \floor{\xi e_{\rho-a_m}}+\floor{\xi e_{\rho-1}}-2\xi e_\rho
  +\floor{\xi e_{\rho+1}},
\end{split}
\]
whereas in case $a''_1=1$,
\[
  \floor{\xi\mu^\ast C} \cdot E_\rho=
  \floor{\xi e_{\rho-a_m}}+\floor{\xi e_{\rho-1}}-(2+a''_2)\xi e_\rho
  +\floor{\xi e_{\rho+a''_2+1}}.
\]
By Lemma~\ref{l:star}, $e_\rho=e_{\rho-a_m}+e_{\rho-1}+m_{j+1}$, and
by Lemma~\ref{l:eRelevantCoeff}, $e_\rho=p_j\qbar_jm_{j+1}$.  As
before, either $m$ is odd and $e_{\rho-a_m}=M\qbar_jm_{j+1}$, or $m$
is even and $e_{\rho-1}=M\qbar_jm_{j+1}$ with
$M\qbar_j = -1 \mod p_j$.  Set $x=\xi e_\rho$.  The integer $x$
satisfies $1\leq x<e_\rho=p_j\qbar_jm_{j+1}$.  We claim that
independently of $a''_1$,
\begin{equation} \label{eq:claimStep1}
  -\floor{\xi\mu^\ast C} \cdot E_\rho =
  \ceil{\frac{Mx}{p_j}+\frac{x}{p_j\qbar_j}}
  -\floor{\frac{Mx}{p_j}}-\floor{\frac{x}{p_j\qbar_j}}.
\end{equation}
The justification is more complicated if $a''_1=1$.  The Enriques tree
is shown below in case $a''_1=1$ and $m$ even---the last proper
$L$-shape branch of $T_{p_j,q_j}$ is horizontal.
\begin{center}
  \begin{pspicture}(0,0)(12,3.8)
    \rput(5.5,2.3){

      \uput{\labelsep}[u](1.5,0){$\substack{a'_2\text{ vertices}
          \\ \overbrace{\hspace{30mm}}}$}
      \psset{arrows=->,radius=.1}
      \Cnode(-3.71,-1.71){13}
      \Cnode(-3.71,-.71){12}
      \Cnode(-1.71,-.71){11}
      \Cnode(-.71,-.71){1}
      \ncline{13}{12}
      \ncline{11}{1}
      \Cnode(0,0){2}
      \Cnode(1,0){3}
      \Cnode(3,0){4}
      \Cnode(4,0){5}
      \Cnode(4,1){6}
      \ncline{1}{2}
      \ncline{2}{3}
      \ncline{4}{5}
      \ncline{5}{6}
      \uput{\labelsep}[l](-3.71,-1.71){$P_{\rho-a_m}$}
      \uput{\labelsep}[u](-1.71,-.71){$P_{\rho-1}$}
      \uput{\labelsep}[l](0,-1){$P_\rho$}
      \uput{\labelsep}[d](3,0){$P_{\rho+a'_2}$}
      \uput{\labelsep}[r](4,0){$P_{\rho+a'_2+1}$}
      \psset{arrows=-}
      \psline(-3.61,-.71)(-3.21,-.71)
      \psline[linestyle=dotted](-2.21,-.71)(-1.81,-.71)
      \psline[linestyle=dotted](1.1,0)(1.5,0)
      \psline[linestyle=dotted](2.5,0)(2.9,0)}
  \end{pspicture}
\end{center}
By Lemma~\ref{l:eCoeff},
\[
  e_{\rho+a''_2+1} = (a''_2+1)e_\rho + a''_2r''_2m_{j+2} + r''_3m_{j+2}
  = (a'_2+1)p_j\qbar_jm_{j+1}+m_{j+1},
\]
hence $-\floor{\xi\mu^\ast C}\cdot E_\rho$ is given by
\begin{multline*}
  -\floor{\frac{x}{p_j\qbar_jm_{j+1}}(p_j\qbar_jm_{j+1}
    -M\qbar_jm_{j+1}-m_{j+1})}
  -\floor{\frac{x}{p_j\qbar_jm_{j+1}}\,M\qbar_jm_{j+1}} \\
  +(2+a'_2)x
  -\floor{\frac{x}{p_j\qbar_jm_{j+1}}((a'_2+1)p_j\qbar_jm_{j+1}
    +m_{j+1})}
\end{multline*}
and the equality follows establishing the equality
(\ref{eq:claimStep1}).  Finally,
$-\floor{\xi\mu^\ast C} \cdot E_\rho \geq 2$ is equivalent to
\[
  \fpart{\frac{Mx}{p_j}}+\fpart{\frac{x}{p_j\qbar_j}}>1
\]
with $x=\xi e_\rho<p_j\qbar_jm_{j+1}$, \ie to
$x\in R^{m_{j+1}}(p_j,\qbar_j)$, again by Proposition~\ref{p:theSetR}.
\qed

\begin{exa*}
A jumping number might be contributed by more than one relevant
divisor.  For example if the Enriques diagram associated to the
minimal log resolution of $C$ is given by
$T = T_{2,3}\# T_{5,11}$---a tree with nine vertices---and
$\mu^\ast C = \Ctilde+B_9^T$, then $\xi=11/30$ is a jumping number
contributed by either $E_3$ or $E_9$.
\end{exa*}

The first jumping numbers of a unibranch curve can be obtained by
inspecting the jumping numbers of the term ideal associated to $C$ in
a suitable coordinate system.

\begin{cor}
Let $C$ be a curve unibranch at $P$ with the Enriques tree of the
mi\-ni\-mal log resolution $T_{p_1,q_1}\#\cdots\#T_{p_g,q_g}$.  Fixing
$\Pp$ an allowable system of local parameters, let $\aaa_{C,\Pp}$
be the term ideal of an equation of $C$ in $\Pp$.  Then the first
$\card(R(p_1,q_1))$ jumping numbers of $C$ at $P$ coincide with the first
jumping numbers of $\aaa_{C,\Pp}$.
\end{cor}

\proof
Set $\pi=p_2\cdots p_g$.  If $\tT$ is the Enriques diagram defined by
the tree $T_{p_1,q_1}$ and the wights corresponding to the last
$B_\alpha$ considered with multiplicity $\pi$, then
\[
  \overline{\aaa}_{C,\Pp} = \mu^\ast\Oo_Y(-D_\tT).
\]
Notice that $\overline{\aaa}_{C,\Pp}$ is the smallest integrally
closed monomial ideal containing an equation of $C$.  The jumping
numbers of $\aaa_{C,\Pp}$, or equivalently the jumping numbers of
$\overline{\aaa}_{C,\Pp}$, less than $1$ are given by
\[
  \frac{ap_1+bq_1}{p_1q_1\pi} < 1,
\]
with $a,b$ positive integers.  Then the first $\card(R(p_1,q_1))$ of
them, \ie those for which $ap_1+bq_1<p_1q_1$ are among the jumping
numbers of $C$, in the subset $R^\pi(p_1,q_1)$, by
Theorem~\ref{th:main}.  It is sufficient to show that these jumping
numbers are also the first ones of $C$.  But they all satisfy
\[
  \frac{ap_1+bq_1}{p_1q_1\pi} < \frac{1}{\pi}
\]
and $1/\pi$ is bigger that any element of any set
$1/m_j\qbar_jR^{m_{j+1}}(p_j,\qbar_j)$, with $j\geq 2$.
\qed

\section{Reformulation of Theorem~\ref{th:mainEnriques} in terms of \\the
  semigroup of the singularity}
\label{s:two}

Let $S(C)$ be the semigroup of the curve $C$ unibranch at $P$.  It is
defined by
\[
  S(C) = \{\ord_P s \mid s\in\Oo_{C,P}\}
\]
where the order of the local section $s$ is computed using a
normalization $\Ctilde\to C$.  If the Puiseux characteristic of $C$ at
$P$ is $(m;\beta_1,\ldots,\beta_g)$, the first part of Theorem~4.3.5
in \cite{Wa} states that the integers $\betabar_0$,
$\betabar_1,\ldots,\betabar_g$ generate $S(C)$, where $\betabar_j$ are
defined by $\betabar_0=m=m_1$, $\betabar_1=\beta_1$ and then
inductively by
\begin{equation}
  \label{eq:betabar}
  \betabar_{j+1} = \frac{m_j}{m_{j+1}}\,\betabar_j+\beta_{j+1}
  - \beta_j,
\end{equation}
for any $1\leq j<g$, and where $m_{j+1}=\gcd(m_j,\beta_j)$ for any
$1\leq j\leq g$.  The second part shows how to recover the generators
$\betabar_j$ once the semigroup $S(C)$ given: $\betabar_0=m_1$ is
the least non-zero element of $S(C)$, and inductively $\betabar_{j}$
is the least element non divisible by $m_j$, and
$m_{j+1}=\gcd(m_j,\betabar_j)$.  We can state the main result of the
paper.

\begin{thm}
  \label{th:main}
Let $C$ be a curve unibranch at $P$ and let
$(\betabar_0,\betabar_1,\ldots,\betabar_g)$ be the canonical minimal
set of generators of the semigroup $S(C)$.  Then the jumping numbers
of $C$ at $P$ less that $1$ are given by
\[
  \bigcup_{j=1}^g \frac{1}{[m_j,\betabar_j]}\,
  R^{m_{j+1}}\bigg(\frac{m_j}{m_{j+1}},\frac{\betabar_j}{m_{j+1}}\bigg),
\]
where $m_1=\betabar_0$ and $m_{j+1}=\gcd(m_j,\betabar_j)$ for any
$j\geq1$, and where $[m_j,\betabar_j]$ denotes the least common
multiple of the two integers.
\end{thm}

For the proof we will use Theorem~\ref{th:mainEnriques} and need
Enriques' equivalence between the Puiseux characteristic of $C$ at
$P$ and the Enriques diagram associated to the minimal log resolution
of $C$ at $P$, equivalence that we present next.

Let $(x,y)$, be a system of local parameters.  If $x=0$ is not tangent
to $C$ at $P$, there exists a good parametrization
(see~\cite[Chapter~2]{Wa}) of $C$, $x=t^m$ and
$y=\sum_{k=m}^\infty c_kt^k$.  The {\it Puiseux characteristic} of $C$
is the sequence of integers $(m;\beta_1,\ldots,\beta_g)$ defined as
follows: $\beta_1$ is the exponent of the first term in the power
series which is not a power of $t^m$.  Set $m_1=m$ and
$m_2=\gcd(m_1,\beta_1)$.  Inductively, $\beta_j$ is the exponent of
the first term which is not a power of $m_j$ and
$m_{j+1}=\gcd(m_j,\beta_j)$.  The construction stops when $m_{g+1}=1$
is reached.  The integers $\beta_j$ are also called the Puiseux
characteristic exponents and the {\it Puiseux exponents} are just the
rationals $\beta_1/m, \beta_2/m,\ldots,\beta_g/m$.  Note that
\[
  \frac{\beta_1}{m} < \frac{\beta_2}{m} < \cdots <
  \frac{\beta_g}{m}.
\]

\begin{pro}[see \cite{Wa}, Theorem 3.5.5]
  \label{p:puiseuxDropping}
Let $C\subset X$ be a unibranch curve at $P$ on the smooth surface
$X$.  If the Puiseux characteristic of $C$ at $P$ is
$(m;\beta_1,\ldots,\beta_g)$, then the Puiseux characteristic of the
curve obtained by blowing up $X$ at $P$ is given by
\[
\begin{split}
  (m;\beta_1-m,\ldots,\beta_g-m) &\textq{if} \beta_1>2m\\
  (\beta_1-m;m,\beta_2-\beta_1+m,\ldots,\beta_g-\beta_1+m)
  &\textq{if} \beta_1<2m, \, (\beta_1-m)\!\!\not|m\\
  (\beta_1-m;\beta_2-\beta_1+m,\ldots,\beta_g-\beta_1+m)
  &\textq{if} (\beta_1-m)|m.
\end{split}
\]
\end{pro}

\begin{cor}
  \label{c:puiseuxEnriques}
Let $C$ be a curve unibranch at $P$ whose Puiseux characteristic is\linebreak
$(m;\beta_1,\ldots,\beta_g)$.  Consider the sequence of the strict
transforms of $C$ constructed by the successive blowings up that
desingularize $C$.  The first Puiseux characteristic in this sequence
with exactly $g-j+1$ characteristic exponents is
$(m_j;\beta_j^{(j-1)},\ldots,\beta_g^{(j-1)})$, where
$m_j= \gcd(m_{j-1},\beta_{j-1})$ as before, and for any $k\geq j$,
\[
  \beta_k^{(j-1)} = \beta_k-\beta_{j-1}+a_{j-1}m_j
\]
with $a_{j-1}$ the last quotient in the Euclidean
algorithm for $m_{j-1}$ and $\beta_{j-1}$.
\end{cor}

\proof
Considering the Euclidean algorithm for $\beta_1$ and $m_1=m$ and
using the previous proposition, it is easy to see that the first
element in the second Puiseux characteristic is
$m_2=\gcd(m_1,\beta_1)$.  Computing $\beta_j-\beta'_j$ we get that
that $\beta'_j=\beta_j-\beta_1+a_1m_2$, for any $j\geq2$.  Notice that
\[
  \gcd(m_2,\beta_2) = \gcd(m_2,\beta'_2)
\]
and that furthermore, the last quotients in the Euclidean algorithms
for $\beta_2$ and $m_2$, and $\beta'_2$ and $m_2$ coincide.
The result follows by induction on $j$.
\qed

Enriques established the equivalence between the Puiseux
characteristic and the Enriques diagram associated to a curve
unibranch and singular at $P$.  We refer the reader to \cite{EnCh},
\cite{Ca} and especially \cite{SeKn} Theorem XI~\S~6.1.3 for further
details.  What we want to state now is just a more concise way to
present this equivalence.

\begin{thm}[Enriques]
  \label{th:enriques}
Let $(m;\beta_1,\ldots,\beta_g)$ be the Puiseux characteristic of $C$
at $P$.  Set
\[
  p_j = \frac{m_j}{m_{j+1}}
  \textq{and}
  q_j = \frac{\beta_j-\beta_{j-1}+m_j}{m_{j+1}}
\]
for any $1\leq j\leq g$, with $\beta_0=m_1$.  Then, the corresponding
Enriques diagram $\tT$ is given by the Enriques tree
\[
  T = T_{p_1,q_1} \# T_{p_2,q_2} \#\cdots\# T_{p_g,q_g}.
\]
\end{thm}

\likeproof[Sketch of proof]\!\!\!
We will use the notation from Corollary~\ref{c:puiseuxEnriques}.  The
first part of the Enriques tree associated to $C$ coincides with the
Enriques tree associated to a curve having the Puiseux characteristic
$(m_1;\beta_1)$.  Such a curve is desingularized by the blowings up
corresponding to the whole Enriques tree
$T_{p_1,\beta_1/m_2}=T_{p_1,q_1}$ except for the last stretch.  It is
noteworthy that the length of this stretch equals the last quotient in
the Euclidean algorithm for $\beta_1/m_2$ and $p_1$, \ie $a_1$, and
that the blowings up of this last stretch are needed to obtain a
log-resolution for such a curve.  Now, if $C_2$ denotes the strict
transform of $C$ before the blowings up of the last stretch of
$T_{p_1,\beta_1/m_2}$, then $C_2$ is the first strict transform among
the strict transforms of $C$ given by the log resolution, having
exactly $g-1$ Puiseux exponents.  The Puiseux characteristic is
$(m_2;\beta'_2,\ldots,\beta'_g)$.  What we have previously said for
$C$ is true for $C_2$.  So the Enriques tree associated to $C_2$
starts with $T_{p_2,n_2}$, where
\[
  n_2 = \beta'_2/m_3.
\]
It follows that the part of the Enriques tree associated to $C$ and
corresponding to the first two Puiseux exponents is
\[
  T_{p_1,q_1} \# T_{p_2,n_2-(a_1-1)p_2}.
\]
But
\[
  n_2-(a_1-1)p_2 = \frac{\beta'_2}{m_3}-(a_1-1)\frac{m_2}{m_3}
  = \frac{\beta_2-\beta_1+a_1m_2}{m_3}-(a_1-1)\frac{m_2}{m_3}
  = q_2.
\]
The proof is finished by induction on the number of Puiseux exponents.
\qed

\begin{exa*}
The curve given in Example~\ref{ex:asUsual} has the good
parametrization $t\mapsto (t^4,t^6+t^7)$.  It follows that the Puiseux
characteristic is $(4;6,7)$, with $3/2$ the first Puiseux exponent,
and after one blow-up, the strict transform has the unique Puiseux
exponent $5/2$.  We recover the fact that the Enriques tree of the
minimal log resolution is $T_{2,3}\# T_{2,3}$.
\end{exa*}

\begin{cor}
  \label{c:wCoeff}
Let $C$ be a curve unibranch at $P$.  In the notation of
Theorem~\ref{th:enriques}, if $w_\alpha$ are the weights of the
Enriques diagram associated to the minimal log resolution of $C$ at
$P$, and if $r_j$ is the number of vertices of the tree $T_{p_j,q_j}$
for any $1\leq j\leq g$, then $w_1=m_1$ and
\[
  w_{r_1+\cdots+r_j-(j-1)} = m_{j+1}
  = p_{j+1}p_{j+2}\cdots p_{g}
\]
for any $1\leq j\leq g$.
\end{cor}

\proof
Follows from Theorem~\ref{th:enriques},
Proposition~\ref{p:puiseuxDropping}, Corollary~\ref{c:puiseuxEnriques}
and Remark~\ref{r:theWeights}.
\qed

\likeproof[Proof of Theorem~\ref{th:main}]
By Theorem~\ref{th:mainEnriques}, the jumping numbers are given by
\[
  \bigcup_{j=1}^g \frac{1}{m_j \qbar_j}\,
  R^{m_{j+1}}(p_j,\qbar_j).
\]
where the Enriques tree of the minimal log resolution is
$T_{p_1,q_1}\#\cdots\# T_{p_g,q_g}$.  Furthermore
$m_j = p_j\cdots p_g$ and
\[
  \qbar_j = \frac{m_{j-1}}{m_{j+1}}\,\qbar_{j-1}-p_j+q_j
\]
for any $1\leq j\leq g$, with $m_{g+1}=1$ and $\qbar_1=q_1$.
Clearly
$p_j=m_j/m_{j+1}$.
As for $\qbar_j$, using
Theorem~\ref{th:enriques} and the identity (\ref{eq:betabar}), we have
\[
\begin{split}
  \frac{m_{j-1}}{m_{j+1}}\,\qbar_{j-1}-p_j+q_j
  &= \frac{m_{j-1}}{m_{j+1}}\frac{\betabar_{j-1}}{m_j}
  -\frac{m_j}{m_{j+1}}+\frac{\beta_j-\beta_{j-1}+m_j}{m_{j+1}}\\
  &= \frac{1}{m_{j+1}}
  \bigg(
  \frac{m_{j-1}}{m_j}\,\betabar_{j-1}+\beta_j-\beta_{j-1}
  \bigg)\\
  &= \frac{\betabar_j}{m_{j+1}}.
\end{split}
\]
The result follows.
\qed

\section{The proof of Proposition~\ref{p:unibranch}}
\label{s:four}

Let $\xi$ be a jumping number and set $E=\sum_{\beta\in\BBB}E_\beta$
with $\BBB\subset\VVV$ the subset of all vertices such that
$\floor{\xi e_\beta}=\xi e_\beta$.
Then
\begin{equation} \label{eq:inclusion}
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C})
  \varsubsetneq  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E).
\end{equation}
We will show that the right hand side ideal can be computed using only
$\RRR$-chains contained in $E$.  A chain $\Gamma$ of exceptional
divisors $E_\beta$ in the dual graph of the log resolution is called
an $\RRR$-chain if its both extremities are relevant divisors.  A
relevant divisor will be considered as an improper $\RRR$-chain.

\paragraph{Claim}
\begin{equation} \label{eq:equality}
    \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E)
  = \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+\sum \Gamma).
\end{equation}
where $\Gamma$ runs through all the maximal $\RRR$-chains contained in
$E$.

Indeed, suppose that $E$ is a connected subgraph of the dual graph
that contains at least two irreducible components.  Let $E_0$ be an
irreducible component which is not a relevant divisor and which is an
extremity for $E$.

The intersection of $E_0$ with
$E'=E-E_0$ consists of exactly one point $P$ that will be seen as a
divisor of $E_0$.  Notice that
\begin{equation} \label{eq:degrees}
  \deg (\Ctilde-E)|_{E_0} \leq 1.
\end{equation}
Since $(K_\mu+E)|_{E_0}\sim K_{E_0}+(E-E_0)|_{E_0}=K_{E_0}+P$, we have
the commutative diagram
\[
\begin{CD}
  &&&& 0 && 0\\
  &&&&  @VVV  @VVV \\
  0 @>>> \Oo_Y(\Delta) @>>> \Oo_Y(\Delta+E') @>>>
  \Oo_{E'}(K_{E'}-\floor{\xi\mu^\ast C}|_{E'})@>>> 0 \\
  && @|  @VVV  @VVV \\
  0 @>>> \Oo_Y(\Delta) @>>> \Oo_Y(\Delta+E) @>>>
  \Oo_E(K_E-\floor{\xi\mu^\ast C}|_E)@>>> 0  \\
  &&&&  @VVV  @VVV \\
  &&&& \Oo_{E_0}(\Delta_0+P) @=
  \Oo_{E_0}(\Delta_0+P) \\
  &&&&  @VVV  @VVV \\
  &&&& 0 && 0\\
\end{CD}
\]
where $\Delta=K_\mu-\floor{\xi\mu^\ast C}$ and
$\Delta_0=K_{E_0}-\floor{\xi\mu^\ast C}|_{E_0}$.  The last entry in
the middle vertical short exact sequence is given by the snake lemma.
Pushing down to $X$ this exact sequence and using the local vanishing,
we get that
\[
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E)
  = \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E')
\]
if and only if $h^0(E_0,K_{E_0}+P-\floor{\xi\mu^\ast C}|_{E_0})=0$.
But this is true since $E_0$ is an extremity of $E$ and
\[
\begin{split}
  \floor{\xi\mu^\ast C} \cdot E_0
  &= \sum_{\beta\in\BBB}\xi e_\beta E_\beta\cdot E_0
  + \sum_{\alpha\not\in\BBB} \floor{\xi e_\alpha}E_\alpha\cdot E_0\\
  &> \sum_{\beta\in\BBB}\xi e_\beta E_\beta\cdot E_0
  + \sum_{\alpha\not\in\BBB}(\xi e_\alpha-1)E_\alpha\cdot E_0
  + (\xi-1)\Ctilde\cdot E_0\\
  &= \xi\mu^\ast C \cdot E_0 -
  \big( \Ctilde+\sum_{\alpha\not\in\BBB}E_\alpha \big) \cdot E_0 \\
  &= -(\Ctilde-E) \cdot E_0,
\end{split}
\]
and with (\ref{eq:degrees}) yield
\[
  \deg P-\floor{\xi\mu^\ast C} \cdot E_0
  < 1 + (\Ctilde-E)\cdot E_0 \leq 2.
\]
Hence
\[
  \deg(K_{E_0}+P-\floor{\xi\mu^\ast C}|_{E_0}) \leq -1.
\]
Repeated use of this argument shows that we can eliminate from $E$ one
component at a time replacing $E$ by $E'$ as long as $E_0$ is not
a relevant divisor.  Hence if $E$ is
connected, only its maximal $\RRR$-chain counts in
computing the ideal $\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+E)$.
The above argument, applied to each connected part of $E$, justifies the
claim.

\medskip

To end the proof of the proposition it is sufficient to show that
the proper $\RRR$-chains can be discarded in the equality
(\ref{eq:equality}).  This is done next.

\paragraph{Claim}
If $\Gamma$ is a proper $\RRR$-chain, then
$h^0(\Gamma,K_\Gamma-\floor{\xi\mu^\ast C}|_\Gamma)=0$.

Indeed, let us suppose that the $\RRR$-chain $\Gamma$ connects
$E_\rho$ and $E_{\rho'}$, with $\rho'>\rho$.  The first
$E_\gamma\neq E_\rho$ belonging to $\Gamma$ that $E_\rho$ intersects
is either $E_{\rho+1}$ if $a'_1\geq 2$, or $E_{\rho+a'_2+1}$ if not.
In the former case $e_{\rho+1}=e_\rho+\pi$ and in the latter we have
$e_{\rho+a'_2+1}=(a'_2+1)e_\rho+\pi$.  Here $\pi$ equals a certain
$m_j$, depending on $\rho$.  Since $\xi e_\gamma$ is an integer for
any $E_\gamma\subset\Gamma$, these equalities imply that $\xi\pi$ is
an integer.  Then
\[
  \floor{\xi\mu^\ast C} \cdot E_\rho
  = \xi\mu^\ast C \cdot E_\rho - \fpart{\xi\mu^\ast C} \cdot E_\rho
  = -\big(\!
  \fpart{\xi e_{\rho-a_m}}E_{\rho-a_m}+\fpart{\xi e_{\rho-1}}E_{\rho-1}
  \big) \cdot E_\rho = 0
\]
as $\pi$ divides both $e_{\rho-a_m}$ and $e_{\rho-1}$ by
Lemma~\ref{l:eCoeffBefore_r}.  Now, if $\Gamma'=\Gamma-E_\rho$ and $P$ is
the intersection point of $E_\rho$ with $\Gamma'$, from the short exact
sequence
\[
  0 \lra
  \Oo_{\Gamma'}(K_{\Gamma'}-\floor{\xi\mu^\ast C}|_{\Gamma'}) \lra
  \Oo_\Gamma(K_\Gamma-\floor{\xi\mu^\ast C}|_\Gamma) \lra
  \Oo_{E_\rho}(K_{E_\rho}+P-\floor{\xi\mu^\ast C}|_{E_\rho}) \lra
  0
\]
we obtain that
\[
  h^0(\Gamma,K_\Gamma-\floor{\xi\mu^\ast C}|_\Gamma)
  = h^0(\Gamma',K_{\Gamma'}-\floor{\xi\mu^\ast C}|_{\Gamma'}).
\]
Inductively we cut off from the new chain the lowest extremity
$E_\gamma$ and keep denoting the resulting chain by $\Gamma'$.  We
eventually arrive at
\begin{multline*}
  0 \lra
  \Oo_{E_{\rho'}}(K_{E_{\rho'}}-\floor{\xi\mu^\ast C}|_{E_{\rho'}}) \lra
  \Oo_{\Gamma'}(K_{\Gamma'}-\floor{\xi\mu^\ast C}|_{\Gamma'}) \\ \lra
  \Oo_{E_{\gamma}}(K_{E_{\gamma}}+P-
  \floor{\xi\mu^\ast C}|_{E_{\gamma}}) \lra
  0,
\end{multline*}
where $\gamma$ equals either $\rho'-1$ or $\rho'-a_{m'}$, \ie
$E_\gamma$ is the last exceptional divisor in $\Gamma$ different from
$E_{\rho'}$ and $P$ is the intersection point between $E_\gamma$ and
$E_{\rho'}$.  Arguing as before
$\deg\floor{\xi\mu^\ast C}|_{E_{\gamma}}=0$.  As for the computation
of $\deg\floor{\xi\mu^\ast C}|_{E_{\rho'}}$, we have
\[
  \floor{\xi\mu^\ast C} \cdot E_{\rho'}
  = -\Big(\!
  \fpart{\xi e_{\rho'-a'_{m'}}}E_{\rho'-a'_{m'}}
  +\fpart{\xi e_{\rho'-1}}E_{\rho'-1}
  +\fpart{\xi e_{\rho'+\alpha}}E_{\rho'+\alpha}
  \Big) \cdot E_{\rho'}.
\]
Since, as it has been said, $\gamma$ equals either $\rho'-1$ or
$\rho'-a_{m'}$, and since
$e_{\rho'} = e_{\rho'-a_{m'}}+e_{\rho'-1}+\pi'$ with $\pi'|\pi$,
\[
  \floor{\xi\mu^\ast C} \cdot E_{\rho'}
  = \fpart{\xi e_{\rho'+\alpha}} = 0.
\]
Hence $h^0(\Gamma',K_{\Gamma'}-\floor{\xi\mu^\ast C}|_{\Gamma'})=0$
and finally,
$h^0(\Gamma,K_\Gamma-\floor{\xi\mu^\ast C}|_{\Gamma})=0$
for the proper $\RRR$-chain $\Gamma$, justifying the claim.

\medskip

Now, the short exact sequence
\begin{multline*}
  0 \lra
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}) \lra
  \mu_\ast\Oo_Y(K_\mu-\floor{\xi\mu^\ast C}+\sum_{\beta\in\BBB}E_\beta)
  \\ \lra
  \bigoplus_{\rho\in(\BBB\cap\RRR)'}
  H^0(E_\rho,K_{E_\rho}-\floor{\xi\mu^\ast C}|_{E_\rho}) \lra
  0
\end{multline*}
shows that $\xi$ must be contributed by a relevant divisor.  The
set $(\BBB\cap\RRR)'$ is the set of relevant positions in $\BBB$ that
do not define proper $\RRR$-chains contained in $\BBB$.


TITLE: A problem on probability involving binomial distribution
QUESTION [0 upvotes]: I'm trying to figure out the method required to solve this problem, so I stripped out the actual values to keep from getting a direct answer.

A random sample of $n$ people who walk to work are chosen, what is the probability that at least $r$ of them are injured, given that the probability of being injured while walking to work is $p$.

I don't know where to go.  It feels like a binomial probability problem, but it covers a range of trials and not just one value exactly.  My guess was to calculate 1-BinomCDF(n, p, r - 1).  Does this seem accurate?  For example, if $n = 15$, $r = 7$, $p = 0.5$.
I would have 1-BinomCDF(15, 0.5, 6)
or $$1-\sum_{i=1}^6 {15\choose i}0.5^i(1-0.5)^{15-i}.$$

REPLY [3 votes]: You are right, this does use the binomial distribution.$$Pr(X=r)={n\choose r}p^r(1-p)^{n-r}$$
That simply gives the probability that "r" events are true from a total of "n" possible events, with the probability of the event happening being "p"
So using your values:$$\sum_{i=7}^n Pr(X=i)$$
$$=\sum_{i=7}^n{15\choose i}0.5^i(1-0.5)^{15-i}$$


text:
\section{Introduction}

The group testing problem was originally studied in the context of testing blood samples for rare diseases \cite{Dor43}, with the key idea being to reduce the required number of tests via pooling.

Group testing has since found applications in communications \cite{Ant11}, information retrieval \cite{Cor05}, compressed sensing \cite{Gil08}, and most recently, COVID-19 testing \cite{Yel20}.

The problem is formally defined as follows: There are $n$ items $[n]=\sett{1,2,\ldots,n}$, a subset $S\subseteq [n]$ of which is defective, with $|S|=k$.  A number of tests are performed, each taking as input a subset of items, and returning positive if and only if the subset contains at least one defective item.  A group testing algorithm specifies the number of tests $T$, the items included in each test, and a decoder that returns an estimate $\hat{S}$ of the defective set given the test outcomes.   We are interested in the required number of tests to attain asymptotically vanishing error probability, i.e., $\lim_{n \to \infty} \PP[\hat{S}\ne S] = 0$.

We focus on the non-adaptive setting, in which all tests must be specified prior to observing any outcomes; this is often highly desirable in applications, since it permits the tests to be implemented in parallel.  In this setting, the tests can be represented as a test matrix $\bb{X} \in \{0,1\}^{T \times n}$, where the $(i,j)$-th entry is 1 if and only if the $i$-th test contains the $j$-th item.  The test outcomes are then given by the element-wise ``OR'' of the $k$ columns corresponding to the defective items.  Mathematically, the $i$-th outcome is given by
\begin{align}
    Y^{(i)}=\bigvee_{j\in S}X_j^{(i)}, \label{eq:test_outcome_formula}
\end{align}
where $X_j^{(i)}$ is the $(i,j)$-th entry of $\bb{X}$.

We place a random model on the defective set $S$.  Throughout the majority of the paper, we assume that each item is included in $S$ (i.e., is defective) independently with some probability $p$ (possibly depending on $n$), referred to as the {\em prevalence}.  We also consider a closely-related model in which $k$ is fixed, and $S$ is a uniformly random subset of $[n]$ of cardinality $k$.  We refer to these models as the {\em i.i.d.~prior} and {\em combinatorial prior} respectively.  The two are closely related, since under the i.i.d.~model we have $k = np(1+o(1))$ with probability approaching one as long as $np = \omega(1)$.  See \cite[Sec.~1.A]{Ald19} for a more detailed summary of the connections between these models.

Throughout the paper, we make the mild assumption that $p \le \frac{1}{2}$ (i.i.d.~prior) or $k \le \frac{n}{2}$ (combinatorial prior).  Otherwise, the problem fails to be sparse, and it is already well-established that individual (one-by-one) testing is optimal even when adaptivity is allowed \cite{ungar1960,riccio2000sharper,aldridge2019rates}.  In addition, our analysis applies essentially unchanged when this factor of $\frac{1}{2}$ is replaced by any fixed constant less than one.

\section{Existing Results and Contributions} \label{sec:related}

Here we state the most relevant existing results on probabilistic non-adaptive group testing, and state our own main results in the context of these existing ones.  For consistency with the vast majority of existing works, we express the previously-known results in terms of $k$ and $n$, corresponding to the combinatorial prior.  However, the same results apply under the i.i.d.~prior when $k$ is replaced by $\kbar := np$ throughout, under the mild assumption that $\kbar \to \infty$ as $n \to \infty$.

\subsection{Main Existing and New Results}

A simple counting-based (or entropy-based) argument reveals that the number of tests for the high-probability recovery of $S$ must satisfy $T \ge (1-o(1)) \log_2 {n \choose k}$, or more simply $T = \Omega\big(k \log \frac{n}{k}\big)$ \cite{Mal78,Cha11,Ati12,Bal13}.  Moreover, this scaling is order-optimal in the following widely-considered regimes:
\begin{itemize}
    \item If $k \le n^{1-\Omega(1)}$, then we have $k \log \frac{n}{k} = \Theta(k \log n)$, and thus, the lower bound matches the ubiquitous $O(k \log n)$ upper bound obtained via random testing \cite{Fre75,Mal78,Cha11,Ald14a} or certain explicit designs \cite{Ina19}.
    \item If $k = \Theta(n)$, then we have $k \log \frac{n}{k} = \Theta(n)$, and thus, the lower bound matches the trivial $O(n)$ upper bound corresponding to testing each item individually.
\end{itemize}
While these observations cover the majority of scaling regimes, there remain ``mildly sublinear'' regimes in which the existing upper and lower bounds do not match, namely, $k = \Theta\big( \frac{n}{f(n)} \big)$ for any $f(n)$ satisfying $f(n) = \omega(1)$ and $f(n) = o(n^c)$ for all $c > 0$.  A notable example of such a regime is $k = \frac{n}{ {\rm poly}(\log n) }$.  Our first main result, stated below, closes this gap by showing that the correct scaling is always $\Theta( \min\{ k \log n, n\} )$.

Before stating the result, we introduce the following threshold:
\begin{equation}
    T^*(n,k) = \max\Big\{ k \log_2\frac{n}{k}, \frac{k \log_2 k}{\ln 2}\Big\}. \label{eq:T*}
\end{equation}
While the above discussion focuses on scaling laws, recent refined analyses \cite{Joh16,Ald18,Coj19,Coj19a} have nailed down the precise constants in the above-mentioned scaling regimes:
\begin{itemize}
    \item When $k \le n^{1-\Omega(1)}$, the optimal threshold for non-adaptive group testing is $T^*$ \cite{Coj19a}.  Specifically, there exists a strategy using $T \le (1+\epsilon)T^*$ tests that succeeds with probability approaching one and has decoding time polynomial in $n$, whereas any algorithm requires $T \ge (1-\epsilon)T^*$ to have a success probability bounded away from zero.
    \item When $k = \Theta(n)$, the optimal threshold for non-adaptive group testing is $n$ \cite{Ald18}.  Specifically, with $T = n$ one can trivially use one-by-one testing, whereas any strategy attaining success probability arbitrarily close to one must have $T \ge n-1$.\footnote{The subtraction of one is merely due to the fact that under the combinatorial prior, knowing the status of $n-1$ items also implies knowing the status of the remaining item.}
\end{itemize}
Based on these results, a reasonable guess is that the optimal threshold for group testing in general scaling regimes is $\min\{T^*(n,k),n\}$ (which scales as $\Theta( \min\{ k \log n, n\} )$, consistent with the above discussion).  Our main result, stated as follows, reveals that this is indeed the case.

\begin{thm} \label{thm:main1}
    In the non-adaptive group testing problem with $n$ items and prevalence $p$ (possibly depending on $n$) under the i.i.d.~prior with $p = \omega\big(\frac{1}{n}\big)$ and $p \le \frac{1}{2}$,\footnote{The assumption $p = \omega\big(\frac{1}{n}\big)$ ensures that $\kbar = np = \omega(1)$, and hence the number of defectives concentrates around $\kbar$.  The theorem cannot be true as stated when $p \le O\big(\frac{1}{n}\big)$; for example, even the trivial strategy of declaring every item non-defective has $\Omega(1)$ probability of succeeding, in contrast to the second part of the theorem.  In addition, our main novel contribution is handling the significantly denser regime $\kbar = n^{1-o(1)}$.  } we have the following for any $\epsilon > 0$:
    \begin{itemize}
        \item There exists a test design and polynomial-time decoding algorithm using $T \le \min\{ (1+\epsilon)T^*(n,np), n\}$ tests and having a success probability approaching one as $n \to \infty$.
        \item Any group testing strategy having success probability bounded away from zero as $n \to \infty$ must use at least $T \ge (1-\epsilon)\min\{ T^*(n,np), n \}$ tests.
    \end{itemize}
\end{thm}

While we find it most convenient to establish this result for the i.i.d.~prior, we can use known connections between the two priors to establish the following analog for the combinatorial prior.

\begin{cor} \label{cor:main1}
    In the non-adaptive group testing problem with $n$ items and $k \le \frac{n}{2}$ defectives under the combinatorial prior, we have the following for any $\epsilon > 0$:
    \begin{itemize}
        \item There exists a test design and polynomial-time decoding algorithm using $T \le \min\{ (1+\epsilon)T^*(n,k), n\}$ tests and having a success probability approaching one as $n \to \infty$.
        \item Any group testing strategy having success probability bounded away from zero as $n \to \infty$ must use at least $T \ge (1-\epsilon)\min\{ T^*(n,k), n \}$ tests.
    \end{itemize}
\end{cor}

These results not only show that optimal non-adaptive group testing requires $T = \Theta(\min\{k \log n,n\})$ tests in general sparsity regimes, but also provide the precise underlying constants.

The algorithmic upper bounds in Theorem \ref{thm:main1} and Corollary \ref{cor:main1} are already known in the regime $k \le n^{1-\Omega(1)}$ \cite{Joh16,Coj19a}, and follow trivially from one-by-one testing when $\min\{ (1+\epsilon)T^*, n\} = n$.  Hence, it suffices to establish success using $(1+\epsilon)T^*$ tests in the regime $k = n^{1-o(1)}$.  Fortunately, although the analysis of the Definite Defectives (DD) algorithm in \cite{Joh16} was formally only stated for $k \le n^{1-\Omega(1)}$, the analysis can be adapted to the regime $k = n^{1-o(1)}$ with only minor modifications.  We detail the required changes in Appendix \ref{app:dd}.

As for the algorithm-independent lower bounds, with the regime $k \le n^{1-\Omega(1)}$ having been solved in \cite{Coj19a}, we can again focus on the regime $k = n^{1-o(1)}$ (including $k = \Theta(n)$).  In this case, we were unable to directly infer the desired result from \cite{Coj19a}, and we thus provide a detailed proof in Section \ref{sec:proofs}, though we still naturally re-use the main tools and ideas proposed in \cite{Coj19a}.

{\bf Specialization to dense regimes.} As hinted above, when the $\min\{T^*,n\}$ term is attained by $n$, our results indicate that one-by-one testing is asymptotically optimal.  This is consistent with the above-mentioned result of \cite{Ald18}, but also strengthens it in two ways:
\begin{itemize}
    \item Individual testing is not only asymptotically optimal when the goal is to succeed with probability approaching one, but also when the goal is attaining {\em any} strictly positive target success probability.
    \item Individual testing is not only asymptotically optimal when $k = \Theta(n)$, but also when $k = \omega\big( \frac{n}{\log n} \big)$, or even more generally, when $k > \frac{n \ln 2}{\log_2 n}$.
\end{itemize}
On the other hand, it is worth noting that our result only indicates failure when $T < (1-\epsilon)n$, whereas that of \cite{Ald18} handles the more general scenario $T < n-1$.  This distinction is necessary when establishing high-probability failure and/or handling the regime $k = o(n)$, since otherwise one could consider a strategy that (e.g.) tests the first $n-2$ items one-by-one and then guesses the remaining two to be non-defective.

{\bf Note on partially concurrent work.} In the initial version of our work, we focused only on the lower bound, and provided a weaker result with an unspecified coefficient to the $k \log n$ term in the $\min\{ k \log n, n \}$ scaling.  After releasing the initial version, the important case of $k = \Theta\big( \frac{n}{\log n}\big)$ was studied in more detail in \cite{Flo21}, giving upper and lower bounds with explicit constants.  The updated version of our work was developed in parallel with \cite{Flo21}, and establishes the precise constants.  Our upper bound in fact matches that of \cite{Flo21} (and is proved similarly), whereas a refinement of the main proof technique is needed to obtain our tight lower bound (see the stopping condition of Step 4(a), Procedure \ref{alg:fullalg}).

\subsection{Further Existing Results}

Before proceeding, we provide a brief summary of some further existing works.  Since these are less directly related to our work, we omit the details, and refer the reader to \cite{Du93,Ald19} for more detailed surveys.

For certain variants of group testing, the optimal number of tests is $\Theta\big( k \log \frac{n}{k}\big)$, as opposed to $\Theta(\min\{k \log n,n\})$ under the setup we consider.  Specifically, two notable cases with scaling $\Theta\big( k \log \frac{n}{k}\big)$ are (i) the adaptive setting, in which each test can be designed based on previous outcomes \cite{Hwa72,aldridge2019rates,aldridge2020conservative}, and (ii) the approximate recovery criterion, in which $\Theta(k)$ false positives and $\Theta(k)$ false negatives are allowed in the reconstruction \cite{Sca15b,Sca17}.

In contrast to the noiseless setting that we consider in this paper, in the {\em noisy} setting, the number of tests is at least $\Omega(k \log n)$ even if $k \log n \gg n$, and even if adaptivity is allowed \cite{Sca18}.

Finally, while the focus of our work is on high-probability recovery, extensive results have been established for the stronger guarantee of {\em uniform recovery}, i.e., a single test matrix that uniquely recovers any defective set of cardinality at most $k$, without allowing any error probability (e.g., see \cite{Kau64,Dya82,Du93,Che13a} and the references therein).  This stronger guarantee comes at the price of requiring significantly more tests, with a quadratic dependence on $k$ instead of a linear dependence.  In addition, the associated proof techniques are very different.

\begin{comment}
For adaptive testing in the linear regime, \citep{ungar1960} proved that in the probabilistic setting, individual testing is optimal for $p>\frac{3-\sqrt{5}}{2}\approx 0.382$, and \citep{riccio2000sharper} proved that in the combinatorial setting, individual testing is optimal for $p>1-\log_3 2\approx 0.369$. Outside these ranges, an algorithm by \citep{aldridge2019rates} achieves $T<1.05H_2(p)n$ in the former case and $T<1.11H_2(p)n$ in the latter, which is rather close to the trivial information-theoretic lower bound of $H_2(p)n$, where $H_2(p)=-p\log_2 p-(1-p)\log_2(1-p)$ refers to the binary entropy. The below figure from \citep{aldridge2019rates} illustrates the near-optimality of these algorithms:
\begin{Figure}
\centering
\includegraphics[width=220pt]{ald.png}
\end{Figure}
\end{comment}

\section{Proofs of Algorithm-Independent Lower Bounds} \label{sec:proofs}

We first consider Theorem \ref{thm:main1} regarding the i.i.d.~prior, and then turn to Corollary \ref{cor:main1} regarding the combinatorial prior.

\subsection{Proof of the Lower Bound for Theorem \ref{thm:main1}} \label{sec:pf_thm}

Our analysis builds on the ideas of \cite{Ald18,Coj19a}, both of which identify {\em totally disguised} items (see Definition \ref{def:disguised} below) whose defectivity status can be flipped without changing the test outcomes.  In \cite{Ald18}, one such item suffices for attaining the weak converse (i.e., $\PP[\hat{S} \ne S] \not\to 0$) in the linear regime.  To obtain a stronger statement of the form $\PP[\hat{S} \ne S] \to 1$ and also handle sublinear sparsity regimes, we follow the idea from \cite{Coj19a} of identifying {\em many} such items.

Specifically, we follow the high-level steps of \cite{Coj19a} and utilize certain auxiliary results therein, but modify the details in order to handle the regime $k = n^{1-o(1)}$ instead of $k \le n^{1-\Omega(1)}$.  The key idea is to identify many items that are disguised {\em independently of one another}.  We then apply an auxiliary result of \cite{Ald18} (see Lemma \ref{lem:Aldridge} below) along with some ``clean-up'' steps to ensure that its assumptions remain valid each time it is invoked.

In the following, we let $q=1-p$ for convenience.  The following useful definition was introduced in \cite{Ald18}.

\begin{defn} \label{def:disguised}
    \cite{Ald18}

    We say that an item $i$ is \textit{disguised} in test $t$ if at least one of the other items in the test is defective. We say that an item is \textit{totally disguised} if it is disguised in every test it is included in. Let $D_i$ denote the event that item $i$ is totally disguised.
\end{defn}

It is noted in \cite{Ald18} that if an item is totally disguised, then it remains totally disguised even if it is changed from defective to non-defective or vice versa.  Thus, under the i.i.d.~prior, the tests do not reveal any information about that item's defectivity status, and we have the following.

\begin{lem} \label{lem:cond_disguised}
    {\em (Implicit in \cite{Ald18} and \cite[Sec.~3]{Coj19a})}
    For any given test matrix $\Xv$, and a defective set $S$ generated according to the i.i.d.~prior, we have the following: Conditioned on a given item $i$ being totally disguised, that item is defective with conditional probability $p$ (i.e., the same as the prior defectivity probability).
\end{lem}

It follows that for any totally disguised item, the best the algorithm can do is choose the more likely outcome, and succeed with probability $\max\sett{p,1-p} = 1-p$ (recalling that we focus on the case that $p \le \frac{1}{2}$).

The following result from \cite{Ald18} is crucial for characterizing the probability of items being totally disguised.

\begin{lem} \label{lem:Aldridge}
    {\em \cite[Eq.~(1)]{Ald18}}
    Define $\mathcal{L}(p)=\min_{x=2,3,\ldots,n}x\ln(1-q^{x-1})$, where $q = 1-p$. If the test design $\bb{X}$ has no tests with 0 or 1 items, then
    \begin{align}
        \frac{1}{n}\sum_{i=1}^n\ln \pr[D_i]\geq\frac{T}{n}\cdot \mathcal{L}(p) \label{eq:AldBound}
    \end{align}
    Hence, there exists an item $i$ with $\ln \pr[D_i]\geq\frac{T}{n}\cdot \mathcal{L}(p)$.
\end{lem}

At a high level, this lemma is proved by directly calculating $\pr[D_i]$ in terms of the $i$-th test size (which $x$ plays the role of in the definition of $\mathcal{L}(p)$), then averaging over the resulting log-values and applying some simple lower bounding techniques.

In the linear regime (i.e., $k = \Theta(n)$), one has $\mathcal{L}(p) = \Theta(1)$, and consequently, Lemma \ref{lem:Aldridge} directly implies that the success probability is bounded away from one, after removing all tests with 0 or 1 items \cite{Ald18}.
More generally, it is natural to ask whether there are, in fact, {\em many} items $i$ with $\ln \pr[D_i]$ close to the the right-hand side of \eqref{eq:AldBound} \cite{Coj19a}. If we can find a ``large'' set $W$ of such items such that these items are totally disguised independently from each other, then we may apply standard binomial distribution concentration bounds to conclude that many totally disguised items exist, with high probability.

Following \cite{Coj19a}, we interpret the testing strategy as a bipartite graph $G_{\bb{X}}$ in which there is a vertex $v_i$ for each item $i$ and a vertex $v_t$ for each test $t$, with an edge between $v_i$ and $v_t$ if item $i$ is placed in test $t$.

Before constructing the desired set (denoted by $W$), we present two simple lemmas (which are analogous to \cite[Lemmas 3.7 and 3.8]{Coj19a}) and two subroutines that will be useful.

\begin{lem}
    \label{nobigtests}
    Let $z=\frac{2}{\ln\frac{1}{q}}$, and suppose that $T \le n$. Then, the probability that there exists a negative test containing more than $z\ln n$ items is at most $\frac{1}{n}$.
\end{lem}

\begin{proof}
    Recalling that $q = 1-p$, a given test containing at least $z\ln n$ items is negative with probability at most
    \begin{align}
        q^{z\ln n}=e^{z\ln q\ln n}=\frac{1}{n^2}
    \end{align}
    by the definition of $z$.  Since $T \le n$, a union bound yields the desired result.
\end{proof}

We henceforth assume that no test contains more than $z\ln n$ items, since Lemma \ref{nobigtests} implies that the decoder may declare all such tests to be positive without increasing the error probability by more than $\frac{1}{n}\to0$.

\begin{lem}
    \label{fewbigitems}
    Fix $\xi > 0$, and define an item to be {\em very-present} if it appears in more than $n^{\xi}$ tests. If $T \le n$ and no test contains more than $z\ln n$ items, then there are no more than $zn^{1-\xi}\ln n$ very-present items.
\end{lem}

\begin{proof}
    We count the number $P$ of pairs $(i,t)$ such that item $i$ is in test $t$. By assumption, $P \leq Tz\ln n \le nz\ln n$. Letting $n_{\mathrm{vp}}$ be the number of very-present items, it follows that $n_{\mathrm{vp}}n^{\xi}\leq P< nz\ln n$, and rearranging yields the desired result.
\end{proof}

\begin{algorithm}[t]
    \caption*{ \manuallabel{sub}{3.1} \textbf{Subroutine 3.1:} $\texttt{Clean}(\bb{X})$. \label{alg:clean} }

    \begin{enumerate}
        \item[1.] Identify the set of tests $T_{\leq1}$ containing 0 or 1 items, and the set of items $I$ contained in at least one test in $T_{\leq1}$.
        \item[2.] Return $\bb{X}_{\geq2}$, defined to be $\bb{X}$ with the rows and columns indexed by $T_{\leq1}$ and $I$ removed.
    \end{enumerate}
\end{algorithm}

\begin{algorithm}[t]
    \caption*{ \manuallabel{subr}{3.2} \textbf{Subroutine 3.2:} $\texttt{Extract}(\bb{X},W)$. \label{alg:extract} }

    \begin{enumerate}
        \item[1.] Let $\widetilde{D}_i$ be the event that $i$ is totally disguised with respect to $\bb{X}$. Let the item with the highest $\pr[\widetilde{D}_i]$ be denoted by $i_0$, and set $W_{\rm next} = W \cup \{i_0\}$.
        \item[2.] Let $T_{\textrm{close}}$ and $I_{\textrm{close}}$ denote the sets of tests and items within distance at most 4 from $i_0$ in $G_{\bb{X}}$.
        \item[3.] Set $\bb{X}_{\rm pruned}$ to be $\bb{X}$ with the rows and columns indexed by $T_{\textrm{close}}$ and $I_{\rm close}$ removed.
        \item[4.] Return $(\bb{X}_{\textrm{pruned}},W_{\rm next})$
    \end{enumerate}
\end{algorithm}

We are now in a position to describe the construction of the desired set $W$, namely, a set of items that are disguised independently of one another.  To establish a hardness result, we would like to ensure that the size of $W$ and the probability of each $i \in W$ being disguised are both large enough, so that the resulting error probability is high.

Towards achieving this goal, we introduce Subroutines \ref{alg:clean} and \ref{alg:extract}.  \texttt{Clean} removes all tests with 0 or 1 items, allowing us to apply Lemma \ref{lem:Aldridge}, and \texttt{Extract} adds an item to $W$.  Both will be called multiple times in the construction of $W$, and their calls will reduce the effective $T$ and/or $n$.

\begin{algorithm}[t]
    \caption*{ \manuallabel{algo}{3.1} \textbf{Procedure 3.1:} $\texttt{ConstructSet}(\bb{X})$. \label{alg:fullalg} }

    \begin{enumerate}
        \item[1.] Let $G_0=G_{\bb{X}}$, and let $(n,T)$ be the number of items and tests in $\bb{X}$. Remove all very-present items from $G_0$ to obtain $G_1$. Let $G=G_1$.
        \item[2.] Initialize $W_0=\emptyset$, $i=1$.
        \item[3.] Set $\bb{X}_i\leftarrow$ test design represented by $G_i$. Set $\bb{X}_{\mathrm{tmp},i}\leftarrow\texttt{Clean}(\bb{X}_i)$, and let $(n_i,T_i)$ be the corresponding number of items and tests in $\bb{X}_{\mathrm{tmp},i}$.
        \item[4.] Perform the following:
        \begin{itemize}[leftmargin=3ex]
            \item[(a)] If $n_i > 0$ and $\frac{T_i}{n_i} \le (1+\xi) \frac{T}{n}$, then set $(\bb{X}_{i+1},W_{i}) \leftarrow\texttt{Extract}(\bb{X}_{\mathrm{tmp},i},W_{i-1})$, $G_{i+1}\leftarrow G_{\bb{X}_{i+1}}$, and $i\leftarrow i+1$, and return to Step 3.
            \item[(b)] Otherwise, terminate the procedure and return $W = W_{i-1}$.
        \end{itemize}
    \end{enumerate}
\end{algorithm}

The full procedure for constructing $W$ is described in Procedure \ref{alg:fullalg}, which depends on a generic constant $\xi > 0$; although its use in step 4(a) is not directly related to its used in Lemma \ref{fewbigitems}, we find it sufficient to use the same constant in both cases.

To justify step 1, we momentarily imagine that there exists a ``genie'' that tells the decoder the identity of the very-present items. Let the test results for $G_0$ and $G_1$ be $\bb{y}_0$ and $\bb{y}_1$ respectively; then, knowing $\bb{X}$, we see that $\bb{y}_0$ can be derived from $\bb{y}_1$ and the genie information. If we can prove that the error probability tends to one even with the help of the genie (and knowing $\bb{y}_1$), then it certainly tends to one without it, so step 1 is justified. After step 1, each item is contained in at most $n^{\xi}$ tests.

Let $w_i$ denote the $i$-th item placed in $W$. Let $D_{w_i}$ be the event that $w_i$ is totally disguised with respect to $\bb{X}_1$, and let $\widetilde{D}_{w_i}$ be the event that $w_i$ is totally disguised with respect to $\bb{X}_{{\rm tmp},i}$ (see Procedure \ref{alg:fullalg} for the definitions of  $\bb{X}_1$ and $\bb{X}_{{\rm tmp},i}$).

Since the totally disguised event $D_{w_i}$ only depends on the 2-neighborhood of $w_i$ in $G_1$, and the 2-neighborhoods of items in $W$ are pairwise disjoint by construction (due to the $\texttt{Extract}$ subroutine), the events $\sett{D_{w}:w\in W}$ are independent (this independence property for nodes having distance greater than $4$ was also used in \cite{Coj19a}).

Next, we state the following simple lemma relating the events $D_{w_i}$ and $\widetilde{D}_{w_i}$, both of which represent events of being totally disguised, but with  respect to different test matrices.

\begin{lem} \label{lem:EtoD}
    Under the preceding setup, we have $\pr[D_{w_i}] \geq \pr[\widetilde{D}_{w_i}]$.
\end{lem}
\begin{proof}
    In each \texttt{Clean}/\texttt{Extract} step, whenever we remove a test, we remove all of its items. It follows that $w_i$ is contained in $\textit{the same tests}$ in $\bb{X}_1$ and $\bb{X}_{\mathrm{tmp},i}$, except that each such test in $\bb{X}_{\mathrm{tmp},i}$ has \textit{fewer items}.  Since a disguised item always remains disguised when further items are added to its tests, it follows that $\widetilde{D}_{w_i}$ implies $D_{w_i}$.
\end{proof}

In addition, we have the following lower bound on $|W|$, the total number of extracted items.  Here and subsequently, we recall that to prove Theorem \ref{thm:main1}, it suffices to consider the regime $p = n^{-o(1)}$, since for any smaller $p$ (i.e. $p = n^{-\Omega(1)}$), Theorem \ref{thm:main1} was already established in \cite{Coj19a}.

\begin{lem} \label{lem:num_extracted}
    Under the preceding setup, if $p = n^{-o(1)}$ and $T \le (1-\epsilon)n$, then the size of the set $W$ returned by Procedure \ref{alg:fullalg} satisfies the following:
    \begin{equation}
        |W|\, \ge n^{1-3\xi}. \label{eq:W_asymp}
    \end{equation}
\end{lem}
\begin{proof}
    We first count the number of removed items as follows:
    \begin{itemize}
        \item No more than $T$ items alone in some test are removed by \texttt{Clean}.
        \item Lemma \ref{fewbigitems} implies that we removed at most $zn^{1-\xi}\ln n$ very-present items, and this scales as $o(n)$ due to the fact that $z = \frac{2}{\ln\frac{1}{1-p}} = \Theta\big(\frac{1}{p}\big) = n^{o(1)}$ (by the assumption $p = n^{-o(1)}$).
        \item By the assumption stated following Lemma \ref{nobigtests} and the removal of very-present items, each call to \texttt{Extract} removes at most $z^2n^{2\xi}\ln^2 n$ items.
    \end{itemize}
    We now argue by contradiction that \eqref{eq:W_asymp} must hold.  Suppose to the contrary that Procedure \ref{alg:fullalg} terminates at some iteration $i^* \le n^{1-3\xi}$.  Then, the above calculations imply that
    \begin{align}
        n_{i^*} &\ge n - T - zn^{1-\xi}\ln n- n^{1-3\xi} \cdot  z^2n^{2\xi}\ln^2n \label{eq:n_i_0} \\
        &\ge \epsilon n - o(n), \label{eq:n_i}
    \end{align}
    where we used the fact that $T \le (1-\epsilon)n$ and $z = n^{o(1)}$.  This means that the stopping condition met in step 4(a) cannot have been $n_i$ reaching zero, so it must have been $\frac{T_{i^*}}{n_{i^*}}$ exceeding $(1+\xi) \frac{T}{n}$.

    While \eqref{eq:n_i} indicates that the majority of items could eventually be removed in principle, this is only due to the subtraction of $T$ in \eqref{eq:n_i_0}; the other two terms behave as $o(n)$, and we conclude that the removal of very-present items and the calls to \texttt{Extract} collectively only remove $o(n)$ items.  Any further removal of items can only be due to the tests containing one item in \texttt{Clean}; removing these causes $T_i$ and $n_i$ to be reduced by the {\em same amount}.  However, as long as $\frac{T_i}{n_i} < 1$ (which holds by assumption for $i=0$, and subsequently for all $i \le i^*$ due to the stopping condition), reducing $T_i$ and $n_i$ by the same amount can {\em only make the ratio smaller} (i.e., $\frac{T_i - c}{n_i - c} \le \frac{T_i}{n_i}$ for any $c \in [0,T_i]$).

    More formally, suppose that up to index $i^*$, a total of $c$ items and tests are removed due to tests containing a single item, and a total of $c'$ items are removed for the other reasons mentioned above.  Then, we have
    \begin{equation}
        \frac{T_{i^*}}{n_{i^*}} \le \frac{ T - c }{ n - c - c' }. \label{eq:ratio}
    \end{equation}
    As established above, we have $0 \le c \le T \le n(1-\epsilon)$ and $c' = o(n)$.  However, since $\frac{T}{n} < 1$ by assumption, substituting these findings into \eqref{eq:ratio} reveals that $\frac{T_{i^*}}{n_{i^*}} \le \frac{T}{n}(1+o(1))$, which gives the desired contradiction to the stopping condition $\frac{T_{i^*}}{n_{i^*}} > (1+\xi) \frac{T}{n}$.

\end{proof}

Recall that all of the extracted items have independent totally disguised events, each with probability lower bounded according to Lemma \ref{lem:Aldridge}.
We need to consider applying this lemma with possibly smaller choices of $T$ and $n$ than the original values (namely, $T_i$ and $n_i$), but the stopping condition in step 4(a) of Procedure \ref{alg:fullalg} ensures that $\frac{T_i}{n_i} \le (1+\xi) \frac{T}{n}$.

As a result, Lemmas \ref{lem:Aldridge} and \ref{lem:EtoD} guarantee for any extracted item $i$ that
\begin{align}
    \pr[D_i]\geq\exp\bigg( \frac{T(1+\xi)}{n}\cdot \mathcal{L}(p) \bigg), \label{eq:Di_bound1}
\end{align}
where we recall that $\mathcal{L}(p)=\min_{x=2,3,\ldots,n}x\ln(1-q^{x-1})$ with $q = 1-p$.  Note that $x\ln(1-q^{x-1}) < 0$, so this minimum is to be interpreted as ``most negative''. This minimum is characterized in the following lemma, which is similar to \cite[Claim 3.12]{Coj19a}.

\begin{lem} \label{lem:x_opt}
    For any $p \le \frac{1}{2}$ satisfying $p = n^{-o(1)}$, we have the following: (i) If $p = o(1)$, then $-\mathcal{L}(p) = \frac{(\ln 2)^2}{p} (1+o(1))$; (ii) If $p = \Theta(1)$, then  $-\mathcal{L}(p) = \Theta(1)$.
\end{lem}
\begin{proof}
    We provide a simple generalization of the argument from \cite[Claim 3.12]{Coj19a}, which focuses on the regime $k \le n^{1-\Omega(1)}$.
    We first write
    \begin{equation}
        -\mathcal{L}(p)=\max_{x=2,3,\ldots,n}x\ln\frac{1}{1-q^{x-1}}.
    \end{equation}
    This quantity is lower bounded by the argument corresponding to $x = \lceil \frac{1}{p}\rceil + 1$, which readily yields $\ln\frac{1}{1-q^{x-1}} = \Theta(1)$ and hence an $\Omega\big(\frac{1}{p}\big)$ lower bound on $-\mathcal{L}(p)$.

    For the upper bound, we note that for $x = o\big( \frac{1}{p} \big)$ we have $q^{x-1} = (1-p)^{x-1} = 1-\Theta(px)$, so the objective function behaves as $O(x \ln \frac{1}{px})$, which is  $o\big(\frac{1}{p}\big)$ (since $px \ln \frac{1}{px} \to 0$ as $px \to 0$).  On the other hand, if $x = \omega\big(\frac{1}{p}\big)$, then $q^{x-1} = (1-p)^{x-1} \to 0$, so the objective behaves as $O(x (1-p)^{x-1}) = O(x e^{-px})$, which is $o\big(\frac{1}{p}\big)$  (since $px e^{-\Theta(px)} \to 0$ as $px \to \infty$).  Hence, the optimal choice of $x$ must scale as $\Theta\big(\frac{1}{p}\big)$, and in this case, we have $\ln\frac{1}{1-q^{x-1}} = \Theta(1)$, yielding an $O\big(\frac{1}{p}\big)$ upper bound on $-\mathcal{L}(p)$.

    The second part of the lemma follows immediately, whereas for the first part, a refined analysis is needed.  For $p = o(1)$ and $x = \Theta\big( \frac{1}{p} \big)$, we have
    \begin{align}
        x\ln\frac{1}{1-(1-p)^{x-1}}
        &= x\ln\frac{1}{1-e^{-px}(1+O(p))} \\
        &= -x\ln(1-e^{-px}) + O(px)
    \end{align}
    by standard Taylor expansions.  Since $O(px) = O(1)$ is asymptotically negligible compared to the $\Theta\big( \frac{1}{p} \big)$ scaling derived above, it suffices to consider maximizing the first term.  As noted in \cite{Coj19a}, we can define $d = px$ and write this term as $\frac{1}{p}\big( - d \ln(1-e^{-d}) \big)$, and it is a simple differentiation exercise to verify that $-d \ln(1-e^{-d})$ is maximized at $d = \ln 2$, with maximum value $(\ln 2)^2$.  While the corresponding choice $x = \frac{d}{p}$ may not be integer-valued, the effect of rounding is asymptotically negligible for $p = o(1)$ by the continuity of the function $-d \ln(1-e^{-d})$.
\end{proof}

Combining Lemma \ref{lem:x_opt} with \eqref{eq:Di_bound1}, we obtain for some $c_p = \Theta(1)$ that
\begin{align}
    \pr[D_i]\geq\exp\bigg( - \frac{(1+\xi) c_p T}{n p} \bigg), \label{eq:Di_bound2}
\end{align}
and moreover, when $p = o(1)$ we specifically have $c_p = (\ln 2)^2 (1+o(1))$.

Since the events $\{D_i\}_{i \in W}$ are mutually independent by construction, and $|W| \ge n^{1-3\xi}$ according to Lemma \ref{lem:num_extracted}, we deduce that the number of totally disguised items is stochastically dominated by ${\rm Binomial}( n^{1-3\xi}, e^{-\frac{(1+\xi) c_p T}{ np }} )$.  In particular, the average number of totally disguised items is
\begin{equation}
    n^{1-3\xi} e^{-\frac{(1+\xi) c_p T}{ np }},
\end{equation}
and by simple re-arrangements, this is lower bounded by $n^{\xi}$ whenever
\begin{equation}
    T \le \frac{np(1-4\xi)}{(1+\xi) c_p } \ln n. \label{eq:T_bound2}
\end{equation}
Thus, by the multiplicative form of the Chernoff bound, the actual number is at least $N_{\min} := \frac{1}{2} n^{\xi}$ with probability approaching one when \eqref{eq:T_bound2} holds.

By Lemma \ref{lem:cond_disguised} and the assumption $p \le \frac{1}{2}$, for any item that is disguised, the optimal algorithm can do no better than declare it to be non-defective, and the resulting probability of being correct is at most
\begin{equation}
    (1-p)^{N_{\min}} \le e^{-p N_{\min}} = e^{-\frac{p}{2} n^{\xi} } = o(1),
\end{equation}
where the last step follows from the assumption $p =  n^{-o(1)}$.  Thus, we have proved that $\PP[\hat{S} = S] = o(1)$ whenever $T \le (1-\epsilon) n$ and \eqref{eq:T_bound2} holds.

When $p = \Theta(1)$ (or more generally $p = \omega\big( \frac{1}{\log n}\big)$), the stricter of these two conditions is $T \le (1-\epsilon) n$, and the constant $c_p$ in \eqref{eq:T_bound2} is inconsequential.  On the other hand, when $p = o(1)$, we have established that $c_p = (\ln 2)^2 (1+o(1))$.  Since $\xi$ can be arbitrarily small, it follows that \eqref{eq:T_bound2} reduces to $T \le (1-\epsilon') \frac{np}{ (\ln 2)^2 } \ln n$ for arbitrarily small $\epsilon' > 0$.  Finally, since $\frac{\ln n}{\ln 2} = \log_2 n$, and the assumption $p = n^{-o(1)}$ implies that $\log_2 n = (\log_2 k)(1+o(1))$, we obtain the desired threshold corresponding to the second term of $T^*$ in \eqref{eq:T*}.

\subsection{Proof of the Lower Bound for Corollary \ref{cor:main1}} \label{sec:pf_cor}

We utilize an approach from \cite[Lemma 3.6]{Coj19a} for transferring the key auxiliary results on the number of disguised items from the i.i.d.~prior to the combinatorial prior.  Despite the high level of similarity, we provide the main details for completeness.

The idea is to show that with too few tests, the number of totally disguised defectives and totally disguised non-defectives both grow unbounded with high probability.  When this occurs, interchanging the statuses among these items would not impact the test results, and hence, there exist an unbounded number of candidate defective sets of cardinality $k$ consistent with the test outcomes.  The decoder cannot do any better than guess one of these at random, failing with high probability. This intuition is easily made precise \cite{Coj19a}, giving the following.

\begin{lem} \label{lem:cond_error}
    {\em \cite[Facts 3.1 and 3.3]{Coj19a}}
    Under the combinatorial prior, the conditional error probability of any group testing strategy given that there are $\tilde{n}_0$ totally disguised non-defectives and $\tilde{n}_1$ totally disguised defectives is at least $1 - \frac{1}{\tilde{n}_0 \tilde{n}_1}$.   In particular, if $\tilde{n}_0 = \omega(1)$ and $\tilde{n}_1 = \omega(1)$, then the conditional error probability is $1-o(1)$.
\end{lem}

Consider the combinatorial prior with $n^{1-o(1)} \le k \le \frac{n}{2}$, where the condition $k \ge n^{1-o(1)}$ is safe to assume since Corollary \ref{cor:main1} is already well-known when $k \le n^{1-\Omega(1)}$ (see Section \ref{sec:related}).  We consider generating $S$ according to the following procedure:
\begin{enumerate}
    \item Let $S_{0} \subseteq [n]$ include each item independently with probability $p_0 = \frac{k - \sqrt{k} \ln n}{n}$.  That is, $S_0$ follows the i.i.d.~prior with parameter $p_0$.
    \item Form $S$ by adding $\max\{k - |S_0|, 0\}$ elements of $[n] \setminus S_0$ to $S_0$, chosen uniformly at random.
\end{enumerate}
By the symmetry of this construction, conditioned on the event $|S_0| \le k$, the resulting set $S$ is indeed distributed according to the combinatorial prior.  While $|S_0| >  k$ has a non-zero probability, for the purposes of proving a converse, we can simply assume that this event always leads to successful recovery.  Since we assume that $k \ge n^{1-o(1)}$, a simple concentration argument (e.g., the Chernoff bound or central limit theorem) gives with probability $1-o(1)$ that
\begin{equation}
    k - 2\sqrt{k} \ln n \le |S_0| \le k, \label{eq:conc}
\end{equation}
so the resulting contribution to the success probability is asymptotically negligible.

We now introduce the terminology that an item $i$ is {\em totally disguised in the first step} if the defectives from $S_0$ alone are enough to disguise $i$ in every test it is included in.  Clearly, being totally disguised in the first step is sufficient for being totally disguised after the second step, since the second step only involves marking more items as defective.

Hence, trivially, the number of totally disguised defective items only increases (or stays the same) after the second step.  The number of totally disguised non-defectives may in principle decrease due to non-defectives being changed to defective, but conditioned on \eqref{eq:conc}, any given non-defective is only changed with probability $O\big( \frac{\sqrt{k} \ln n}{n} \big) = o(1)$.  As a result, if there are $\omega(1)$ totally disguised non-defectives, the same still remains true with probability $1-o(1)$ after the second step.

Hence, in accordance with Lemma \ref{lem:cond_error}, it suffices to show that under the i.i.d.~prior with parameter $p_0 = \frac{k - \sqrt{k} \ln n}{n}$, the number of totally disguised defectives and totally disguised non-defectives both behave as $\omega(1)$ with probability $1-o(1)$.   Note that the assumption $n^{1-o(1)} \le k \le \frac{n}{2}$ ensures that $n^{-o(1)} \le p_0 \le \frac{1}{2}$, as was assumed in the later parts of Section \ref{sec:pf_thm}.

We already argued that when \eqref{eq:T_bound2} holds, the average number of totally disguised items is at least $n^{\xi}$.  Since $n^{-o(1)} \le p_0 \le \frac{1}{2}$, it follows that the average number of totally disguised defectives and totally disguised non-defectives are both at least $n^{\xi-o(1)}$ on average.  Again, the multiplicative form of the Chernoff bound implies the same with high probability, and we have the desired $\omega(1)$ scaling.  This establishes that the condition on $T$ from Theorem \ref{thm:main1} with $p_0$ in place of $p$ is necessary for attaining a success probability bounded away from zero, and since $np_0 = k(1+o(1))$ by definition, Corollary \ref{cor:main1} follows.

\section{Conclusion} \label{sec:conclusion}

We have proved that the optimal number of tests for probabilistic noiseless non-adaptive group testing is $\Theta(\min\{k \ln n,n\})$, as well as establishing the precise underlying constant factors.  This closes gaps exhibited by existing bounds in the in the case that $k$ is ``mildly'' sublinear in $n$, so that the optimal thresholds are now known for arbitrary scaling regimes.  Perhaps the main challenge remaining in this setting is to understand how the number of tests increases when the target error probability decreases to zero at a given rate depending on $n$.

config: arxiv


TITLE: What is measure of angle $CED.$
QUESTION [0 upvotes]: In the figure, $ABCD$ is a rhombus with area $48\sqrt 3 cm^2,$ $|DE|=10cm, |BE|=2cm.$ What is the measure of the angle $\angle CED?$ Please help me. Thanks.

REPLY [0 votes]: Let $\alpha$ be the angle $\angle CED$. We can get $AC$ by means the area formula:
$${AC\cdot BD\over 2}=48\sqrt3$$
$$AC={2\cdot48\sqrt3\over12}=8\sqrt3$$
If $M$ is the center of the rhombus $CM=4\sqrt3$; $ME=MB-BE=6-2=4$ so:
$$\tan\alpha={CM\over ME}=\sqrt3$$
hence $\alpha=60$.