TITLE: $ F(x)= \int_{\sin x}^{\cos x} e^{t^2+xt}\,dt$. What is $F'(0)=$?
QUESTION [3 upvotes]: $$\begin{align*} F(x)&= \int_{\sin x}^{\cos x} e^{t^2+xt}\,\mathrm dt\\F'(0)&=\,?\end{align*}$$

I only know how to deal with the kind like $$F(x)=\int h(x)g(t)\,\mathrm dt $$ for which I can treat $h(x)$ as a constant relative to $t$ and move it out of the integral and differentiate. But in this problem I cannot separate $x$ from $t$.

REPLY [2 votes]: I apologize if this is just Dr. MV's idea, but I hope this is a simpler exposition.
Using $v=\cos(x)$, $u=\sin(x)$, and $y=t^2$, we have
$$
\begin{align}
&\frac{\mathrm{d}}{\mathrm{d}x}\int_{\sin(x)}^{\cos(x)}e^{t^2+xt}\mathrm{d}t\\[3pt]
&=\frac{\mathrm{d}v}{\mathrm{d}x}\frac{\partial}{\partial v}\int_u^ve^{t^2+xt}\mathrm{d}t
-\frac{\mathrm{d}u}{\mathrm{d}x}\frac{\partial}{\partial u}\int_u^ve^{t^2+xt}\mathrm{d}t
+\frac{\partial}{\partial x}\int_u^ve^{t^2+xt}\mathrm{d}t\\[3pt]
&=\frac{\mathrm{d}v}{\mathrm{d}x}e^{v^2+xv}
-\frac{\mathrm{d}u}{\mathrm{d}x}e^{u^2+xu}
+\int_u^vte^{t^2+xt}\mathrm{d}t\\
&=-\sin(x)e^{\cos^2(x)+x\cos(x)}
-\cos(x)e^{\sin^2(x)+x\sin(x)}
+\int_{\sin(x)}^{\cos(x)}te^{t^2+xt}\mathrm{d}t\\
&=-0-1+\int_0^1te^{t^2}\mathrm{d}t\\
&=-1+\frac12\int_0^1e^y\mathrm{d}y\\[3pt]
&=\frac12e-\frac32
\end{align}
$$


TITLE: What is the name of the 65537-gon?
QUESTION [3 upvotes]: I know the name of the heptadecagon (17 sides) and the diacosipentacontaheptagon (257 sides). But what is the name of the polygon with 65537 sides? I am unable to figure it.

REPLY [5 votes]: Following the portuguese nomenclature (I am from Brazil) and translating to english its results:
hexacontakaipentachiliakaipentahectakaitriacontakaiheptagon.
Best regards!!


TITLE: Proving $\sum_{k=0}^n \binom{n}{k} = 2^n$ combinatorially?
QUESTION [2 upvotes]: I am trying to prove the basic fact that
$$\sum_{k=0}^n \binom{n}{k} = 2^n$$
I can use the binomial theorem, simply setting $x = y = 1$, but how can I prove this combinatorially?
Thanks.

REPLY [3 votes]: Let $\mathcal P$ the set af all subsets of $E=\{1,2,...,n\}$ an $\mathcal P_k$ the set of all subsets of $E$ having $k$ elements. then $\{\mathcal P_0, \cdots,\mathcal P_n\}$ is a partition of $\mathcal P$.
Since $$\text{card}(\mathcal P)=2^n$$ and for all $k \in \{0,1,\cdots,n\}$:  $$\text{card}(\mathcal P_k)=\binom{n}{k}$$ and   $$\text{card}(\mathcal P)=\sum_{k=0}^n \text{card}(\mathcal P_k)$$ we get the formula to proof.


text:
\section{Main results}\label{KPCA-sec-Lp}

\subsection{Basic setup}

Consider the signal-plus-noise model
\begin{align}
\bx_i = \bar\bx_i + \bz_i \in \RR^d,\qquad i \in [n].
\label{Lp-eqn-signal-plus-noise-euc}
\end{align}
For simplicity, we assume that the signals $\{ \bar{\bx}_i \}_{i=1}^n$ are deterministic and the noises $\{ \bz_i \}_{i=1}^n$ are the only source of randomness. The results readily extend to the case where the signals are random but independent of the noises.

Define the \textit{hollowed} Gram matrix $\bG \in \RR^{n\times n}$ of samples $\{ \bx_i \}_{i=1}^n$ through $G_{ij} = \langle \bx_i , \bx_j \rangle \mathbf{1}_{ \{ i \neq j \} }$, and the Gram matrix $\bar\bG \in \RR^{n\times n}$ of signals $\{ \bar\bx_i \}_{i=1}^n$ through $\bar G_{ij} = \langle \bar\bx_i , \bar\bx_j \rangle$.
Denote the eigenvalues of $\bG$ by $\lambda_1 \geq \cdots \geq \lambda_n$ and their associated eigenvectors by $\{ \bu_j \}_{j=1}^n$. Similarly, we define the eigenvalues $\bar\lambda_1 \geq \cdots \geq \bar\lambda_n$ and eigenvectors $\{ \bar\bu_j \}_{j=1}^n$ of $\bar\bG$.
Since $\bar\bG = \bar\bX \bar\bX^{\top} \succeq 0$, we have $\bar\lambda_j \geq 0$ for all $j \in [n]$.
By convention, $\lambda_0 = \bar\lambda_0 = + \infty$ and $\lambda_{n+1} = \bar\lambda_{n+1} = - \infty$. Some groups of eigenvectors may only be defined up to orthonormal transforms as we allow for multiplicity of eigenvalues.

Let $s$ and $r$ be two integers in $[n]$ satisfying  $0 \leq s \leq n - r$. Define $\bU = (\bu_{s+1},\cdots,\bu_{s + r})$, $\bar\bU = (\bar\bu_{s+1},\cdots, \bar\bu_{s + r})$, $\bLambda = \diag (\lambda_{s+1},\cdots,\lambda_{s + r})$ and $\bar\bLambda = \diag ( \bar\lambda_{s+1},\cdots, \bar\lambda_{s + r})$. In order to study how $\bU$ relates to $\bar\bU$, we adopt the standard notion of eigen-gap \citep{DKa70}:
\begin{align}
\bar{\Delta} = \min\{  \bar\lambda_{s} - \bar\lambda_{s+1} , \bar\lambda_{s+r} - \bar\lambda_{s+r+1} \}.
\end{align}
This is the separation between the set of target eigenvalues $\{ \bar\lambda_{s + j} \}_{j=1}^r$ and the rest, reflecting the signal strength. Define $\kappa = \bar\lambda_1 / \bar\Delta$, which plays the role of condition number.
Most importantly, we use a parameter $\gamma$ to characterize the signal-to-noise ratio and impose the regularity assumptions below. It is worth mentioning that we consider the asymptotic setting $n\to\infty$ throughout the paper to make the results clean and easy to read. They can be easily translated to finite-sample versions similar to those in \cite{AFW17}, since our tools such as concentration inequalities and spectral perturbation bounds are non-asymptotic by nature.

\begin{assumption}[Incoherence]\label{KPCA-assumption-incoherence-euc}
As $n \to \infty$ we have
	\begin{align*}
	\kappa \mu \sqrt{\frac{r}{n} } \leq \gamma \ll \frac{1}{\kappa \mu}
	\qquad \text{where} \qquad
	\mu = \max \bigg\{ \frac{\| \bar\bX \|_{2, \infty}}{\| \bar\bX \|_{2}} \sqrt{\frac{n}{r}} , ~ 1  \bigg\}.
	\end{align*}
\end{assumption}
\begin{assumption}[Sub-Gaussianity]\label{KPCA-assumption-noise-euc}
	$\{ \bz_i \}_{i=1}^n$ are independent, zero-mean random vectors in $\RR^d$. There exists a constant $\alpha > 0$ and $\bSigma \succeq 0$ such that $\EE e^{\langle \bu,\bz_i \rangle} \leq e^{ \alpha^2 \langle \bSigma \bu, \bu \rangle / 2 }$ holds for all $\bu \in \RR^d$ and $i\in [n]$.
\end{assumption}
\begin{assumption}[Concentration]\label{KPCA-assumption-concentration-euc}
	$\sqrt{n} \max\{ (  \kappa \| \bSigma \|_{2} / \bar\Delta )^{1/2},~  \| \bSigma \|_{\mathrm{F}} / \bar\Delta \} \leq \gamma$.
\end{assumption}

By construction, $\bar\bX = (\bar\bx_1,\cdots,\bar\bx_n)^{\top}$ and $\| \bar\bX \|_{2,\infty} = \max_{i\in[n]} \| \bar\bx_i \|_2$. Assumption \ref{KPCA-assumption-incoherence-euc} regulates the magnitudes of $\{ \| \bar\bx_i \|_2 \}_{i=1}^n$ in order to control the bias induced by the hollowing step. It naturally holds under various mixture models. The incoherence parameter $\mu$ is similar to the usual definition \citep{CRe09} except for the facts that $ \bar\bX $ does not have orthonormal columns and $r$ is not its rank. When $r = 1$, we have $\mu = \sqrt{n} \| \bar\bX \|_{2, \infty} / \| \bar\bX \|_{2} \geq 1 $.
Assumption \ref{KPCA-assumption-noise-euc}  is a standard one on sub-Gaussianity \citep{KLo14}. Here $\{ \bz_i \}_{i=1}^n$ are independent but may not have identical distributions, which allows for heteroscedasticity. Assumption \ref{KPCA-assumption-concentration-euc} governs the concentration of $\bG$ around its population version $\bar\bG$.
To gain some intuition, we define $\bZ = (\bz_1,\cdots,\bz_n)^{\top} \in \RR^{n \times d}$ and observe that
\begin{align*}
\bG
& = \cH [ (\bar\bX + \bZ)  (\bar\bX + \bZ)^{\top} ] = \cH ( \bar\bX \bar\bX^{\top} ) + \cH( \bar\bX\bZ^{\top} + \bZ \bar\bX^{\top} ) + \cH( \bZ\bZ^{\top} ) \notag \\
& = \bar\bX \bar\bX^{\top} + ( \bar\bX\bZ^{\top} + \bZ \bar\bX^{\top} ) + \cH( \bZ\bZ^{\top} )  - \bar\bD,
\end{align*}
where $\bar\bD$ is the diagonal part of $\bar\bX \bar\bX^{\top} + \bar\bX\bZ^{\top} + \bZ \bar\bX^{\top}$. Hence
\begin{align*}
\| \bG - \bar\bG \|_2 \leq  \| \bar\bX\bZ^{\top} + \bZ \bar\bX^{\top} \|_2 + \| \cH( \bZ\bZ^{\top} ) \|_2 + \max_{i \in [n]} | (\bar\bX \bar\bX^{\top} + \bar\bX\bZ^{\top} + \bZ \bar\bX^{\top})_{ii} |.
\end{align*}
The individual terms above are easy to work with. For instance, we may control $\| \cH( \bZ\bZ^{\top} ) \|_2$ using concentration bounds for random quadratic forms such as Hanson-Wright-type inequalities \citep{CYa18}. The spectral and Frobenius norms of $\bSigma$ collectively characterize the effective dimension of the noise distribution. That gives the reason why Assumption \ref{KPCA-assumption-concentration-euc} is formulated as it is. It turns out that Assumptions \ref{KPCA-assumption-incoherence-euc}, \ref{KPCA-assumption-noise-euc} and \ref{KPCA-assumption-concentration-euc} lead to a matrix concentration bound $\| \bG - \bar\bG \|_2 = O_{\PP} ( \gamma \bar\Delta;~ n)$, paving the way for eigenvector analysis. Hence $\gamma^{-1}$ measures the signal strength, similar to the quantity in \cite{AFW17}.

\subsection{$\ell_{2,p}$ analysis of eigenspaces}

Note that $\{ \bu_{s+j} \}_{j=1}^r$ and $\{ \bar\bu_{s+j} \}_{j=1}^r$ are only identifiable up to sign flips, and things become even more complicated if some eigenvalues are identical. To that end, we need to align $\bU$ with $\bar\bU$ using certain orthonormal transform.

Define $\bH = \bU^{\top} \bar\bU \in \RR^{r\times r}$ and let $\tilde\bU \tilde\bLambda  \tilde\bV^{\top}$ denote its singular value decomposition, where $\tilde\bU, \tilde\bV \in \cO_{r\times r}$ and $\tilde\bLambda \in \RR^{r\times r}$ is diagonal with nonnegative entries. The orthonormal matrix $\tilde\bU \tilde \bV^\top $, denoted by the matrix sign function $\sgn ( \bH )$ in the literature \citep{Gro11}, is the best rotation matrix that aligns $\bU$ with $\bar \bU$ and will play an important role throughout our analysis. In addition, define $\bZ = (\bz_1,\cdots,\bz_n)^{\top} \in \RR^{n\times d}$ as the noise matrix.   Recall that for $\bA \in \RR^{n\times r}$ with row vectors $\{ \bA_i \}_{i=1}^n $, the $\ell_{2,p}$ norm is
\begin{align*}
\| \bA \|_{2,p} = \bigg( \sum_{i=1}^n \| \bA_{i} \|_2^p \bigg)^{1/p}.
\end{align*}

\begin{theorem}\label{KPCA-corollary-main}
Suppose that Assumptions \ref{KPCA-assumption-incoherence-euc}, \ref{KPCA-assumption-noise-euc} and \ref{KPCA-assumption-concentration-euc} hold. As long as $2 \leq p \lesssim (\mu\gamma)^{-2}$, we have
\begin{align*}
	&	\| \bU \sgn(\bH) - \bG\bar\bU \bar\bLambda^{-1}  \|_{2,p} = o_{\PP} ( \| \bar\bU \|_{2,p};~p),\\
	& \| \bU \sgn(\bH) - [ \bar\bU + \cH ( \bZ \bX^{\top} ) \bar\bU \bar\bLambda^{-1} ] \|_{2,p} = o_{\PP} ( \| \bar\bU \|_{2,p};~p),\\
	&	\| \bU \sgn(\bH) \|_{2,p} = O_{\PP} ( \| \bar\bU \|_{2,p};~p).
	\end{align*}
In addition, if $\kappa^{3/2} \gamma \ll 1$, then
\begin{align*}
&	\| \bU \bLambda^{1/2} \sgn(\bH) - \bG\bar\bU \bar\bLambda^{-1/2}  \|_{2,p} = o_{\PP} ( \| \bar\bU \|_{2,p} \| \bar\bLambda^{1/2} \|_2 ;~p) ,\\
&	\| \bU \bLambda^{1/2} \sgn(\bH) - [ \bar\bU \bar\bLambda^{1/2} + \cH (\bZ \bX^{\top}) \bar{\bU} \bar\bLambda^{-1/2} ] \|_{2,p} = o_{\PP} ( \| \bar\bU \|_{2,p} \| \bar\bLambda^{1/2} \|_2 ;~p).
\end{align*}
\end{theorem}

The first equation in Theorem \ref{KPCA-corollary-main} asserts that although $\bU$ is a highly nonlinear function of $\bG$, it can be well-approximated by a linear form $\bG \bar\bU \bar\bLambda^{-1}$ up to an orthonormal transform. This can be understood from the hand-waving deduction:
\begin{align*}
\bU = \bG \bU \bLambda^{-1} \approx \bG \bar\bU \bar\bLambda^{-1}.
\end{align*}
The second equation in Theorem \ref{KPCA-corollary-main} talks about the difference between $\bU$ and its population version $\bar\bU$. Ignoring the orthonormal transform $\sgn(\bH)$, we have that for a large fraction of $m \in [n]$, the following entrywise approximation holds
\begin{align}
\bU_m \approx
[\bar\bU + \cH ( \bZ \bX^{\top} ) \bar\bU \bar\bLambda^{-1}]_m

= \bar\bU_{m} + \bigg\langle \bz_m,  \sum_{j \neq m} \bx_j  \bar\bU_{j} \bar\bLambda^{-1} \bigg\rangle .
\label{KPCA-eqn-entrywise}
\end{align}
If we keep $\{ \bx_j \}_{j \neq m}$ fixed,  then the spectral embedding $\bU_m$ for the $m$-th sample is roughly linear in $\bz_m$ or equivalently $\bx_m$ itself. This relation is crucial for our analysis of spectral clustering algorithms.
The third equation in Theorem \ref{KPCA-corollary-main} relates to the delocalization property of $\bU$ to that of $\bar\bU$, showing that the mass of $\bU$ is spread out across its rows as long as $\bar\bU$ behaves in a similar way.

Many spectral methods use the rows of $\bU \in \RR^{n\times r}$ to embed the samples $\{ \bx_i \}_{i=1}^n \subseteq \RR^d$ into $\RR^r$ \citep{SMa00, NJW02} and perform downstream tasks. By precisely characterizing the embedding, the first three equations in Theorem \ref{KPCA-corollary-main} facilitate their analysis  under statistical models.
In PCA, however, the embedding is defined by PC scores. Recall that the PCs are eigenvectors of the covariance matrix $\frac{1}{n} \bX^{\top} \bX \in \RR^{d \times d}$ and PC scores are derived by projecting the data onto them. Therefore, the PC scores in our setting correspond to the rows of $\bU \bLambda^{1/2}$ rather than $\bU$. The last two equations in Theorem \ref{KPCA-corollary-main} quantify their behavior.

Theorem \ref{KPCA-corollary-main} is written to be easily applicable. It forms the basis of our applications in Sections \ref{KPCA-sec-GMM} and \ref{KPCA-sec-CSBM}. General results under relaxed conditions are given by Theorem \ref{KPCA-theorem-main}.

Let us now gain some intuition about the $\ell_{2,p}$ error metric. For large $p$,
$\| \bA \|_{2,p} $ is small if a vast majority of the rows have small $\ell_2$ norms, but there could be a few rows that are large. Roughly speaking, the number of those outliers is exponentially small in $p$. We illustrate this using a toy example with $r = 1$, i.e., $\bA = \bx \in \RR^n$ is a vector and $\| \cdot \|_{2,p} = \| \cdot \|_p$. If $\| \bx \|_{p} \leq \varepsilon \| \mathbf{1}_n \|_{p}$ for some $\varepsilon > 0$, then Markov's inequality yields
\begin{align*}
\frac{1}{n} |\{ i:~ |x_i| > t \varepsilon \}| \leq
\frac{ n^{-1} \| \bx \|_p^p }{(t \varepsilon)^p}
\leq \frac{ n^{-1} \varepsilon^p \| \mathbf{1}_n \|_p^p }{(t \varepsilon)^p} = t^{-p}, \qquad  \forall t > 0.
\end{align*}
Larger $p$ implies stronger bounds. In particular, the following fact states that when $p \gtrsim \log n$, an upper bound in $\ell_{2,p}$ yields one in $\ell_{2,\infty}$, controlling all the row-wise errors simultaneously.
\begin{fact}\label{KPCA-fact-p-log}
	$\| \bx \|_{\infty} \leq \| \bx \|_{c \log n} \leq e^{1/c} \| \bx \|_{\infty}$ for any $ n \in \ZZ_+$, $\bx \in \RR^n$, $c > 0$.
\end{fact}
Fact \ref{KPCA-fact-p-log} immediately follows from the relation
\[
\| \bx \|_{\infty} \leq \| \bx \|_p = \bigg(\sum_{i=1}^{n} |x_i|^p\bigg)^{1/p} \leq (n \| \bx \|_{\infty}^p)^{1/p} = n^{1/p} \| \bx \|_{\infty}, \qquad\forall p \geq 1.
\]
Recall that in \Cref{KPCA-corollary-main} we require $\mu \gamma \to 0$ (Assumption \ref{KPCA-assumption-incoherence-euc}) but the convergence rate can be arbitrarily slow. The largest $p$ is of order $(\mu\gamma)^{-2}$. Now we consider a stronger condition $\mu \gamma \lesssim 1 / \sqrt{\log n}$ so that we can take $p \asymp \log n$ and obtain $\ell_{2,\infty}$ approximation bounds.

\begin{corollary}\label{KPCA-corollary-main-inf}
	Suppose that Assumptions \ref{KPCA-assumption-incoherence-euc}, \ref{KPCA-assumption-noise-euc} and \ref{KPCA-assumption-concentration-euc} hold. As long as $\mu\gamma \lesssim 1 / \sqrt{\log n}$, we have
	\begin{align*}
	&	\| \bU \sgn(\bH) - \bG\bar\bU \bar\bLambda^{-1}  \|_{2,\infty} = o_{\PP} ( \| \bar\bU \|_{2,\infty};~\log n),\\
	& \| \bU \sgn(\bH) - [ \bar\bU + \cH ( \bZ \bX^{\top} ) \bar\bU \bar\bLambda^{-1} ] \|_{2,\infty} = o_{\PP} ( \| \bar\bU \|_{2,\infty};~\log n),\\
	&	\| \bU \sgn(\bH) \|_{2,\infty} = O_{\PP} ( \| \bar\bU \|_{2,\infty};~\infty).
	\end{align*}
	In addition, if $\kappa^{3/2} \gamma \ll 1$, then
	\begin{align*}
	&	\| \bU \bLambda^{1/2} \sgn(\bH) - \bG\bar\bU \bar\bLambda^{-1/2}  \|_{2,\infty} = o_{\PP} ( \| \bar\bU \|_{2,\infty} \| \bar\bLambda^{1/2} \|_2 ;~\log n) , \\
&	\| \bU \bLambda^{1/2} \sgn(\bH) - [ \bar\bU \bar\bLambda^{1/2} + \cH (\bZ \bX^{\top}) \bar{\bU} \bar\bLambda^{-1/2} ] \|_{2,\infty} = o_{\PP} ( \| \bar\bU \|_{2,\infty} \| \bar\bLambda^{1/2} \|_2 ;~\log n).
	\end{align*}
\end{corollary}

However, $p$ cannot be arbitrarily large in general. When the signal is weak, we can no longer obtain uniform error bounds as the above and should allow for exceptions. The quantity $(\mu\gamma)^{-2}$ in Theorem \ref{KPCA-corollary-main} measures the signal strength, putting a cap on the largest $p$ we can take. That makes the results adaptive and superior to the $\ell_{2,\infty}$ ones in \citep{AFW17}.

\subsection{Extension to Hilbert spaces}

Since $\bG \in \RR^{n\times n}$ is constructed purely based on pairwise inner products of samples, the whole procedure can be extended to kernel settings. Here we briefly discuss the kernel PCA \citep{SSM97}. Suppose that $\{ \bx_i \}_{i=1}^n $ are samples from some space $\cX$ and $K(\cdot,\cdot):~\cX \times \cX \to \RR$ is a symmetric and positive semi-definite kernel.

The kernel PCA is PCA based on a new Gram matrix $\bK \in \RR^{n\times n}$ with $K_{ij} = K(\bx_i , \bx_j)$. PCA is a special case of kernel PCA with $\cX = \RR^d$ and $K(\bx,\by) = \bx^{\top} \by$. Commonly-used nonlinear kernels include the Gaussian kernel $K(\bx,\by) = e^{- \eta \| \bx - \by \|_2^2 }$ with $\eta > 0$ and polynomial kernel. They offer flexible nonlinear embedding techniques which have achieved great success in machine learning \citep{CSh00}.

According to the Moore-Aronszajn Theorem \citep{Aro50}, there exists a reproducing kernel Hilbert space $\HH$ with inner product $\langle \cdot,\cdot \rangle $ and a function $\phi:~ \cX \to \HH$ such that $K(\bx, \by) =\langle \phi(\bx), \phi(\by) \rangle $ for any $\bx,\by \in \cX$. Hence, kernel PCA of $\{ \bx_i \}_{i=1}^n \subseteq \cX$ is de facto PCA of transformed data $\{ \phi(\bx_i) \}_{i=1}^n \subseteq \HH$.
The transform $\phi$ can be rather complicated since $\HH$ has infinite dimensions in general. Fortunately, the inner products $\{ \langle \phi(\bx_i) , \phi(\bx_j)  \rangle \}$ in $\HH$ can be conveniently computed in the original space $\cX$, which is $K_{ij}$.

Motivated by the kernel PCA, we extend the basic setup to Hilbert spaces. Let $\mathbb{H}$ be a real separable Hilbert space with inner product $\langle \cdot,\cdot \rangle $, norm $\| \cdot \|$, and orthonormal bases $\{ \bh_j \}$.
\begin{definition}[Basics of Hilbert spaces]
	A linear operator $\bA:\HH \to \HH$ is said to be bounded if its operator norm $\| \bA \|_{\mathrm{op}} = \sup_{ \| \bu \| = 1 } \| \bA \bu \|$ is finite.
	Define $\cL (\HH)$ as the collection of all bounded linear operators over $\mathbb{H}$. For any $\bA \in \cL (\HH)$, we use $\bA^*$ to refer to its adjoint operator and let $\Tr ( \bA ) = \sum_{j} \langle \bA \bh_j , \bh_j \rangle$.   Define
	\begin{align*}
	\cS_{+} (\HH) = \{ \bA \in \cL (\HH):~~\bA = \bA^*,~~\langle \bA \bx,\bx \rangle \geq 0,~\forall \bx \in \mathbb{H} \text{ and } \Tr ( \bA ) < \infty \}.
	\end{align*}
	Any $\bA \in \cS_{+}  (\HH)$ is said to be positive semi-definite. We use
	$\| \bA \|_{\mathrm{HS}} = \sqrt{ \Tr ( \bA^* \bA ) } = ( \sum_{j} \| \bA \bh_j \|^2 )^{1/2}$
	to refer to its Hilbert-Schmidt norm, and define $\bA^{1/2} \in \cT ( \mathbb{H} )$ as the unique operator such that $\bA^{1/2} \bA^{1/2} = \bA$.
\end{definition}

\begin{remark}
	When $\mathbb{H} = \RR^d$, we have $\cL(\cH) = \RR^{d\times d}$, $\Tr(\bA) = \sum_{i=1}^{d} A_{ii}$, $\| \cdot \|_{\mathrm{op}} = \| \cdot \|_2$ and $\| \cdot \|_{\mathrm{HS}} = \| \cdot \|_{\mathrm{F}}$. Further, $\cS_{+} (\HH)$ consists of all $d\times d$ positive semi-definite matrices.
\end{remark}

We now generalize model (\ref{Lp-eqn-signal-plus-noise-euc}) to the following one in $\HH$:
\begin{align}
\bx_i = \bar\bx_i + \bz_i \in \HH,\qquad i \in [n].
\label{Lp-eqn-signal-plus-noise}
\end{align}
When $\HH = \RR^d$, the data matrix $\bX = (\bx_1,\cdots,\bx_n)^{\top} \in \RR^{n \times d}$ corresponds to a linear transform from $\RR^d$ to $\RR^n$. For any general $\HH$, we can always define $\bX$ as a bounded linear operator from $\HH$ to $\RR^n$ through its action $\bh \mapsto (\langle \bx_1, \bh \rangle, \cdots, \langle \bx_n, \bh \rangle)$.
With slight abuse of notation, we formally write $\bX = (\bx_1,\cdots,\bx_n)^{\top}$, use $\| \bX \|_{\mathrm{op}}$ to refer to its norm, let $\| \bX \|_{2,\infty} = \max_{i\in[n]} \| \bx_i \|$, and do the same for $\bar\bX$ and $\bZ$. We generalize Assumptions \ref{KPCA-assumption-incoherence-euc}, \ref{KPCA-assumption-noise-euc} and \ref{KPCA-assumption-concentration-euc} accordingly.
\begin{assumption}[Incoherence]\label{KPCA-assumption-incoherence}
	As $n \to \infty$ we have
	\begin{align*}
	\kappa \mu \sqrt{\frac{r}{n} } \leq \gamma \ll \frac{1}{\kappa \mu}
	\qquad \text{where} \qquad
	\mu = \max \bigg\{ \frac{\| \bar\bX \|_{2, \infty}}{\| \bar\bX \|_{\mathrm{op}}} \sqrt{\frac{n}{r}} , ~ 1  \bigg\}.
	\end{align*}
\end{assumption}

\begin{assumption}[Sub-Gaussianity]
	\label{KPCA-assumption-noise}
	$\{ \bz_i \}_{i=1}^n$ are independent, zero-mean random vectors in $\mathbb{H}$. There exists a constant $\alpha > 0$ and an operator $\bSigma \in \cT  (\HH)$ such that $\EE e^{\langle \bu,\bz_i \rangle} \leq e^{ \alpha^2 \langle \bSigma \bu, \bu \rangle / 2 }$ holds for all $\bu \in \mathbb{H}$ and $i\in [n]$.
\end{assumption}

\begin{assumption}[Concentration]\label{KPCA-assumption-concentration}
	$\sqrt{n} \max\{ (  \kappa \| \bSigma \|_{\mathrm{op}} / \bar\Delta )^{1/2},~  \| \bSigma \|_{\mathrm{HS}} / \bar\Delta \} \leq \gamma$.
\end{assumption}

Again, Assumption \ref{KPCA-assumption-incoherence} on incoherence holds for various mixture models. Assumption \ref{KPCA-assumption-noise} appears frequently in the study of sub-Gaussianity in Hilbert spaces \citep{KLo14}. For kernel PCA, Assumption \ref{KPCA-assumption-noise} automatically holds when the kernel is bounded, i.e. $K(\bx,\bx) \leq C$ for some constant $C$. Assumption \ref{KPCA-assumption-concentration} naturally arises in the study of Gram matrices and quadratic forms in Hilbert spaces \citep{CYa18}.
The same results in Theorem \ref{KPCA-corollary-main} continue to hold under the Assumptions \ref{KPCA-assumption-incoherence}, \ref{KPCA-assumption-noise} and \ref{KPCA-assumption-concentration}.
The proof is in Appendix \ref{KPCA-corollary-main-proof}.

config: arxiv


text:
\begin{document}
 \maketitle

\section*{Statement of the result}

Bogomolov and Pantev~\cite{Bog-Pant} have recently discovered a rather
elegant geometric proof of the weak Hironaka theorem on resolution of
singularities:
 \begin{thm} \label{main}
   Let $X$ be a projective variety and $Z$ a proper Zariski closed
   subscheme of $X$. There is a projective birational map
   $\ep\colon\wave{X}\to X$ such that $\wave X$ is smooth, the scheme
   theoretic inverse image $\ep\1(Z)$ is a Cartier divisor, the
   exceptional locus of $\ep$ is a divisor and the union of these two
   divisors is a divisor with simple normal crossings.
 \end{thm}
Before the work cited above, and that of Abramovich and de Jong
\cite{Ab-Jong} (appearing at roughly the same time) the only proof of
this theorem was as a corollary of the famous result of Hironaka
\cite{Hironaka}. These new proofs were inspired by the recent work of
de Jong \cite{Jong}, which Bogomolov and Pantev combine with a
beautiful idea of Belyi \cite{Belyi} ``simplifying'' the ramification
locus of a covering of $\proj^1$ by successively folding up the
$\proj^1$ onto itself, over a fixed base. This latter step
unfortunately only works in characteristic zero, limiting the scope
of the argument (Abramovich and de Jong's paper gives some results
even in characteristic $p$). Hence, we work over the field of complex
numbers; the argument also works (with suitable modifications about
rationality) over any field of characteristic zero.

The outline of the argument we follow is the same as that of the paper
of Bogomolov and Pantev; however we offer different (and we hope
simpler) proofs of the corresponding lemmas. To begin with, their
argument using Grassmannians is replaced by an application of Noether
normalisation in Section~\ref{bundle}. Belyi's argument to reduce the
degree of individual components of the ramification locus is presented in
purely algebraic form in Section~\ref{bundle}, Lemmas~\ref{belyi1}
and~\ref{belyi2}. The presentation of Bogomolov and Pantev refers to
``semi-stable families of pointed curves of genus 0''; the precise
result required from that theory is proved here by means of blowups in
Section~\ref{fibrations}. Finally we also give a summary (in
Section~\ref{toric}) of the desingularisation of toroidal embeddings
which is used by both the papers \cite{Bog-Pant,Ab-Jong}. To summarise,
the aim of this account is to give all the details of the argument, so
that it should be accessible to anyone with a basic knowledge of
algebraic geometry (as contained for example in Mumford's book
\cite{Redbook}).

\subsection*{Acknowledgements} The last statement above was the
``challenge'' posed by Miles Ried who has contributed to this paper in
numerous ways. Discussions with Lawrence Ein and D.~S.~Nagaraj have
greatly helped me in understanding this proof better. V.~S.~Sunder
patiently heard out my ramblings on ``convex'' barycentric
subdivisions. Madhav Nori pointed out a flaw in an earlier argument in
the section on genus 0 fibrations. Rob Lazarsfeld suggested that the
statement of the main result be strengthened---this did not require a
change in the proof! I thank the referee for reading the paper very
carefully and providing a number of suggestions. Of course, many
thanks to Fedor Bogomolov and Tony Pantev for their beautiful proof!

\section*{Some reductions}
For completeness, we define the notion of {\em exceptional locus} that
we use. For a proper birational morphism $\ep:Y\to X$ of varieties,
the {\em exceptional locus} is defined as the complement of the
largest $\ep$-saturated open subset of $Y$ on which $\ep$ is an
isomorphism. We note that the exceptional locus of the composite
$f\circ g$ is the union of the inverse image under $g$ of the
exceptional locus for $f$ and the exceptional locus for $g$.

Let $f:X_1\to X$ be the blowup of $X$ along the scheme $Z$; we thus
ensure that $f^{-1}(Z)$ supports a Cartier divisor. Now let $g:X_2\to
X_1$ be the blowup along the reduced scheme supported on the
exceptional locus $E(f)$ of $f$. Finally, let $h:X_3\to X_2$ be the
blowup along the reduced scheme supported on the singular locus of
$X_2$. Let $Z'$ denote the union of the supports of inverse images of
$Z$, $E(f)$ and $(X_2)_{\rm sing}$ in $X_3$.
\begin{lemma}
  With notation as above, let $\ep_1:\tilde{X}\to X_3$ be a projective
  birational morphism with $\tilde{X}$ smooth such that $\ep_1\1(Z')$
  is contained in a divisor with simple normal crossings. The composite
  morphism $\ep=f\circ g\circ h\circ\ep_1$ then satisfies the conclusion
  of Theorem~\ref{main}.
\end{lemma}
\begin{proof}
  Since any sub-divisor of a divisor with simple normal crossings (see
  Section~\ref{fibrations} for the definition) is again a divisor with
  simple normal crossings it is enough to show that each of $\ep^{-1}(Z)$
  and the exceptional locus $E(\ep)$ are divisors.

  First of all, $f^{-1}(Z)$ supports a Cartier divisor, thus so does
  $\ep^{-1}(Z)$. It follows that the latter is a divisor.

  If $D$ is any divisorial component of $(X_2)_{\rm sing}$, then $X_2$
  is not normal along $D$. It follows that $X_3\to X_2$ is {\em not}
  an isomorphism along $D$ and thus $h^{-1}(D)$ is contained in the
  exceptional locus for $h$. The inverse image of any codimension 2
  component of $(X_2)_{\rm sing}$ is clearly contained in the
  exceptional locus of $h$. Thus, the exceptional locus for $h$ is
  precisely $h^{-1}((X_2)_{\rm sing})$. The exceptional locus of
  $f\circ g:X_2\to X$ is $g^{-1}(E(f))$ which supports a Cartier
  divisor by construction of $g$. It follows that the exceptional
  locus of $f\circ g\circ h:X_3\to X$ supports a Cartier divisor.
  Moreover, the complement $U$ of this divisor in $X_3$ is smooth and
  is mapped isomorphically to an open subset of $X$ by $f\circ g\circ
  h$. Let $V=\ep_1^{-1}(U)$. The morphism $\ep_1:V\to U$ is a proper
  birational morphism of smooth varieties and thus its exceptional
  locus is a divisor $D$ in $V$. It thus follows that the exceptional
  locus of $\ep$ is a divisor.
\end{proof}
As a corollary we see that the main result Theorem~\ref{main} is
equivalent to the apparently weaker result:
\begin{thm}\label{weaker}
  Let $X$ be a projective variety and $Z$ a proper Zariski closed
  subset of $X$. There is a projective birational map
  $\ep\colon\wave{X}\to X$ such that $\wave X$ is smooth. Moreover,
  the set theoretic inverse image $\ep\1(Z)$ and the exceptional locus
  of $\ep$ are contained in a divisor with simple normal crossings.
\end{thm}
We will now prove the two equivalent theorems, by proving
Theorem~\ref{weaker}. We can make the following trivial reductions:
 \begin{enumerate}
 \item We may assume that $X$ is normal by replacing $X$ with its
  normalisation and replacing $Z$ by the union of its inverse image
  with the exceptional locus of the normalisation.
\item Any normal curve is smooth and any proper closed subset of a
  smooth curve is a simple normal crossing divisor~(!). Hence the
  result is true in dimension 1.
\item We prove the theorem by induction on the dimension of $X$. Thus
  we may assume that $n=\dim X>1$ and that Theorem~\ref{main}
  holds for all varieties of smaller dimension than $X$.
\item In order to prove Theorem~\ref{weaker} for a given $Z$ it is enough to
  prove it for a larger $Z'\supset Z$, as long as $Z'$ is a proper
  subset of $X$. Thus, we can expand $Z$ at any stage in our
  construction of the resolution. In particular, whenever we blow up
  $X$ we will expand $Z$ to include the exceptional locus of the blow
  up.
 \end{enumerate}

\section{$\proj^1$-bundles}\label{bundle}
We will prove the following:
 \begin{claim}\label{claim1}
   After replacing $X$ by $X'$, where the latter is the blow up of $X$
   at a finite set of smooth points, and replacing $Z$ by the union of
   its inverse image in $X'$ and the exceptional divisor of the blow
   up, we have:
 \begin{enumerate}
 \item There is a finite surjective map $f\colon X\to\proj_Y(F)$,
   where $Y$ is smooth and $F$ is a rank $2$ vector bundle on $Y$.
 \item The morphism $f$ is finite and \'etale outside a divisor
   $B=\bigcup_{i=1}^n s_i(Y)$ which is the union of a finite number of
   sections $s_i\colon Y\to\proj_Y(F)$ of the $\proj^1$-bundle
   $\proj_Y(F)$.
 \item The image $f(Z)$ of $Z$ under $f$ contained in $B$.
 \end{enumerate}
 \end{claim}

 \begin{lemma}\label{noether}
After replacing $X$ by its blowup at a suitable finite set of smooth
points, we have the following situation. There is a smooth variety $Y$, a
line bundle $L$ and a finite surjective map $g\colon X\to Q=
\proj_Y(\Oh\oplus L)$ such that if $E$ denotes the section corresponding
to the quotient homomorphism $\Oh\oplus L\to\Oh$, then there is a divisor
$B\subset Q$ disjoint from $E$ and containing $g(Z)$ and the branch locus
of $g$. Moreover, $E$ is the image of the exceptional locus of the
blowup of $X$ at the finite set of smooth points.
 \end{lemma}

 \begin{proof}
This is essentially just Noether normalisation. Let $X\into\proj^N$ be a
projective embedding of $X$ and $L=\proj^{N-n-1}$ a linear subspace in
$\proj^N$ that does not meet $X$, where $n=\dim X$. The projection from
$L$ gives a finite map $X\to\proj^n$. Let $B$ be a hypersurface in
$\proj^n$ that contains the image of $Z$ and the branch locus of
the map. Let $p$ be a point of $\proj^n$ not on $B$. Replace $X$ by its
blowup at the points lying over $p$ (which are all smooth) and let
$Y=\proj^{n-1}$ with $L=\Oh(1)$. The blowup of $\proj^n$ at $p$ is
naturally isomorphic to $\proj_Y(\Oh\oplus L)$ and the resulting
morphism from $X$ to this $\proj^1$-bundle has the required form.
 \end{proof}

Now $B$ is a divisor in the $\proj^1$-bundle $Q\to Y$ that does not meet
a section $E$. Thus the projection $B\to Y$ is finite and flat. In fact
we have:

\begin{lemma}\label{belyi1}
In the above situation, if $\Oh_Q(1)$ denotes the universal quotient
bundle, then $\Oh_Q(B)=\Oh_Q(b)$ where $b$ is the degree of the map
$B\to Y$.
\end{lemma}

\begin{proof}
Consider the line bundle $\Oh_Q(B)\otimes\Oh_Q(-b)$. Since this line
bundle is trivial on the fibres of $Q\to Y$, it is the pullback of a line
bundle from $Y$. But it restricts to the trivial bundle on $E$, which is
a section of $Q\to Y$. Hence it is the trivial line bundle.
\end{proof}
Set $Q=\proj_Y(\Oh\oplus L)$, and let $B$ be a divisor in $Q$ which is
finite over $Y$; assume moreover that $B=B_1\cup\bigcup_{i=1}^r s_i(Y)$,
where $s_i$ are sections, and $B_1$ does not meet $E$. Now let $d(B)$
denote the maximum degree over $Y$ of any irreducible component of $B_1$
and $m(B)$ the number of components of this degree. We wish to construct
a new map $X\to Q'=\proj_Y(\Oh\oplus L^N)$ for which $B_1$ is empty.
Thus we may assume that $d(B)>1$ and $m(B)>0$. The following lemma
shows that we can arrange for at least one of these numbers to drop, and
that completes the required inductive step.

\begin{lemma}\label{belyi2}
There is a map $h\colon Q\to Q'=\proj_Y(\Oh\oplus L^d)$ such that if $B'$
is the union of $h(B)$ and the branch locus of $h$ then
$(d(B),m(B))>(d(B'),m(B'))$ in the lexicographic ordering. Moreover,
under this map the image of the divisor $E$ in $Q$ is the
corresponding divisor $E'$ in $Q'$.
 \end{lemma}

\begin{proof}
Let $A$ be an irreducible component of $B_1$ of degree $d=d(B)$ and
consider the two maps $\Oh_Q\to\Oh_Q(d)$ and $L_Q^d\to\Oh_Q(d)$ given by
$A$ and $d\cdot E$. Since these two divisors do not meet, the direct sum
$\Oh_Q\oplus L_Q^d\to\Oh_Q(d)$ is surjective. Thus, by the universal
property of $Q'$ we obtain a morphism $Q\to Q'$ which on every fibre is
a map $\proj^1\to\proj^1$ of degree $d$. Its ramification divisor $R$
has the form $R=(d-1)E + R'$ for some divisor $R'$ that does not meet
$E$. Moreover, the Hurwitz formula on the general fibre $\proj^1$
(equivalently, computing the canonical divisors) gives
$\Oh_Q(R')=\Oh_Q(d-1)$. Thus we have the required result.
\end{proof}
We compose the morphism obtained from Lemma~\ref{noether} with a
succession of morphisms obtained from Lemma~\ref{belyi2}. By the
latter lemma the pair $(d(B),m(B))$ can be reduced until eventually
$B_1$ becomes empty and thus the composite morphism $f$ is as stated
in Claim~\ref{claim1}.

\section{Genus 0 fibrations}\label{fibrations}

We will prove the following:
\begin{claim}\label{claim2}
  We can replace $X$ by a blow up $X'$ and $Z$ by the union of its
  inverse image in $X'$ with the exceptional locus of the blow up, so
  that:
 \begin{enumerate}
 \item There is a finite map $f\colon X\to W$ with $W$ smooth.
 \item The union of the image $f(Z)$ of $Z$, the exceptional locus $E$
   and the branch locus of $f$ is contained in a divisor $D$ with
   simple normal crossings (or strict normal crossings).
 \end{enumerate}
 \end{claim}
For completeness, we recall the definition of a simple normal crossing
divisor $D$ in a smooth projective variety. If $D=\bigcup_{i=1}^n D_i$
is the decomposition of the divisor into irreducible components, then
for each $I\subset\{1,\ldots,n\}$ the scheme theoretic intersection
$D_I=\bigcap_{i\in I} D_i$ is reduced and smooth of codimension equal
to the cardinality $\#I$ of the set $I$.

Write $g\colon X\to P=\proj_Y(F)$ for the map constructed in
Section~\ref{bundle} and let $\{s_i\}_{i=1}^m$ be sections of $P\to Y$
such that the union $\bigcup_{i=1}^m s_i(Y)$ contains $g(Z)$, the
branch locus of $g$ and the image of the exceptional locus of the
blowups already performed. Let
 \[
 Z_1 = \bigcup_{1\le i < j\le m} p_Y(s_i(Y)\cap s_j(Y))
 \]
be the divisor in $Y$ obtained as the image of the pairwise
intersections of the sections. We apply the induction hypothesis 0.3
to obtain a map $\ep_Y\colon\wave Y\to Y$ such that the inverse image
$\ep_Y\1(Z)$ is a divisor with simple normal crossings in $\wave
Y$. Moreover, note that $Y$ as constructed in the previous section is
$\proj^{n-1}$ and thus normal. Thus, we can also assume (by induction)
that the exceptional locus $E_Y$ of $\ep_Y$ is a divisor, such that
the union $Z_1=E_Y\cup\ep_Y\1(Z)$ is also a divisor with simple normal
crossings.

Replacing $Y$ by $\wave Y$ and $P$ by its pullback, we obtain a
configuration with the following properties (A):

 \begin{enumerate}
 \renewcommand{\labelenumi}{(\arabic{enumi})}

\item $p\colon P\to Y$ is a flat morphism of smooth varieties whose
reduced fibres are trees of projective lines $\proj^1$ (in other words,
$p$ is a {\em genus $0$ fibration});

\item we have a finite collection $\{s_i\}_{i=1}^m$ of sections of $p$
such that
 \[
 \bigcup_{1\le i < j\le m} p_Y(s_i(Y) \cap s_j(Y)) \subset Z_1
 \]
where $Z_1$ is a divisor with simple normal crossings in $Y$;

\item the morphism $p$ is smooth outside $p\1(Z_1)$ and the latter
 is a divisor with simple normal crossings.
\end{enumerate}
We wish to perform a succession of blowups resulting in a configuration
still having the same properties, but with the sections disjoint.

For each component $C$ of $Z_1$ and each section $s_i$, the image
$C'=s_i(C)\subset P$ is a codimension $2$ subvariety. Write $n(C')$ for
the number of $j$ such that $s_j(C)=C'$, and $n_P$ for the maximum of
such $n(C')$.

\begin{lemma}
 Let $C'$ be so chosen that $n(C')=n_P$. Then for any $j$, either
$s_j(C)=C'$ or $s_j(Y)\cap C'=\emptyset$.
\end{lemma}

\begin{proof}
Suppose $j$ is such that $s_j(Y)\cap C'$ is a proper nonempty subset of
$C'$, and let $C''$ be an irreducible component of this intersection.
Choose $i$ so that $s_i(C)=C'$, let $D'$ be a component of $s_i(Y)\cap
s_j(Y)$ containing $C''$, and denote by $D$ the image $p(D')$. On the one
hand we have
 \[
 s_j(C)\cap C' \subset s_j(Y)\cap C' \subsetneq C' = s_i(C),
 \]
while $D'=s_i(D)=s_j(D)$. Thus we see that $D$ and $C$ are different
components of $Z_1$ containing $p(C'')$. But $C''\subset C'$ has
codimension 3 in $P$, and $p$ restricts to an isomorphism from $C'$ to
$C$. Thus $p(C'')$ is of codimension 2 in $Y$; hence it is an irreducible
component of $D\cap C$. Since $Z_1$ is a simple normal crossing divisor
we see that $D$ and $C$ are the {\em only} components of $Z_1$ that
contain $p(C'')$.

Take any $k$ such that $s_k(C)=C'$; then $s_k(Y)\cap s_j(Y)$ contains a
component $E'$ which contains $C''$. Then by the above reasoning we must
have $D=p(E')$, and thus
 \[
 D' = s_j(D) = s_j(p(E')) = E' = s_k(p(E')) = s_k(D)
 \]
But then we get $s_k(D)=D'$ for all $k$ such that $s_k(C)=C'$, and in
addition, $s_j(D)=D'$ so that $n(D')=n(C')+1$. This contradicts the
maximality of $n(C')$.

\end{proof}

Together with the preceding lemma, the following result shows that
blowing up $C'$ with $n(C')=n_P$ again leads to a configuration of type
(A).

\begin{lemma}
Let $p\colon P\to Y$ be a genus $0$ fibration which is smooth outside
$Z_1$ so that the inverse image $p\1(Z_1)$ of $Z_1$ is a simple normal
crossing divisor in $P$. For $s\colon Y\to P$ a section and $C$ a
component of $Z_1$, consider the blowup $P'\to P$ along $s(C)$.

Then $p'\colon P'\to Y$ is again a genus $0$ fibration which is smooth
outside $Z_1$ so that the inverse image ${p'}\1(Z_1)$ of $Z_1$ is a
simple normal crossing divisor, and the birational transform (or strict
transform) of $s(Y)$ gives a section of $P'$ over $Y$. Moreover, if $t$
is a section of $p$ which is disjoint from $s(C)$ then the birational
transform of $t(Y)$ continues to be a section of $p'$.
\end{lemma}

\begin{proof}
The first two statements and the final statement about $P'$ are obvious.
The union of $s(Y)$ with $p\1(Z_1)$ is a simple normal crossing divisor
since $s$ is a section. Moreover, $s(C)$ is the locus of intersection of
$s(Y)$ and one of the components of $p\1(C)$. Thus the blowup
preserves the property of being a simple normal crossing divisor.
\end{proof}

Suppose that $n_P>1$ and let $N_P$ be the number of $C'$ attaining
this maximum. For each such $C'$ and each pair $i$, $j$ such that
$s_i(C)=s_j(C)=C'$ let $m(i,j,C')$ denote the multiplicity of
intersection of $s_i(Y)$ and $s_j(Y)$ along $C'$. We are in the
situation of the following lemma

\begin{lemma}
Let $P$ be a smooth variety, $D_1$ and $D_2$ smooth divisors meeting
along a smooth codimension $2$ locus $B$ with multiplicity $m>0$. Let
$P'$ be the blowup of $P$ along $B$, and let $D_1'$ and $D_2'$ be the
birational transforms of $D_1$ and $D_2$ respectively. Then the
multiplicity of intersection of $D_1'$ and $D_2'$ is $m-1$ along a
codimension two locus $B'$ lying over $B$.
\end{lemma}

\begin{proof}
In a neighbourhood of the generic point of $B$, the given condition can
be written as follows
 \[
 \Oh_P(D_1)\tensor\Oh_{D_2} = \Oh_{D_2}(m\cdot B)
 \]
Let $E$ denote the exceptional divisor of the blowup $\ep\colon P'\to P$
and let $B'$ be the intersection $D_2'\cap E$; this is a section of the
$\proj^1$-bundle $E\to B$. Now the birational transform of $D_1$
represents the divisor class $\ep^*(D_1)-E$ and thus we see that
 \[
 \Oh_{P'}(D_1')\tensor\Oh_{D_2'} =
 (\Oh_P(D_1)\tensor\Oh_{D_2'}) \tensor \Oh_{D_2'}(-B')
 = \Oh_{D_2'}((m-1)\cdot B'),
 \]
which proves the result.
\end{proof}

 From this lemma, we see that the multiplicity of intersection of the
birational transforms of $s_i(Y)$ and $s_j(Y)$ is $m(i,j,C')-1$. If this
becomes zero then $n(C')$ drops, hence either $N_P$ decreases or $n_P$
does so. This completes the argument by induction since all these
numbers are positive and we wish to obtain the situation where $n_P=1$.

Now, we replace $X$ by the normalisation of the fibre product
$X\times_{\proj_Y(F)} P$ where $P\to Y$ is the configuration of type
(A) with $n_P=1$ obtained above. We then have a finite morphism
$h\colon X\to P$. The image $h(Z)$ of $Z$ and the branch locus of $h$
are contained in the simple normal crossing divisor consisting of the
finitely many disjoint sections of the configuration (A) and
$p\1(Z_1)$. This proves the Claim~\ref{claim2}.

\section{Toric singularities}\label{toric}
As a last step we must prove the result in the following situation.
There is a finite map $f\colon X\to W$ with $W$ smooth and $X$ normal and
$D=\bigcup_{i=1}^n D_i$ a divisor with simple normal crossings so that
$f$ is \'etale outside $D$; moreover $Z$ is a union of (some of) the
components of $f\1(D)$. So we need to construct a birational
morphism $\ep\colon \wave X \to X$ so that $\wave X $ is smooth and
$\ep\1f\1(D)$ is a divisor with simple normal crossings in
$\wave X$.

We will show (see Lemma~\ref{strictness} below) that the inclusion
of $X\setminus f\1(D)$ in $X$ is a strict toroidal embedding in the
sense of \cite{Kempf-etal}, where the desingularisation problem for
such embeddings has been studied and solved. For the sake of
completeness we also give a brief summary of their method. Many
statements below are given without detailed proofs---readers
are invited to complete the arguments on their own or look for proofs in
one of the books on toric geometry such as Oda~\cite{Oda} or
Fulton~\cite{Fulton}.

\subsection{Affine toric singularities}\label{affine}
Let us first consider the simple situation where $W=\A^n$ and $D$ is a
union of coordinate hyperplanes. In this case $W\setminus D$ is
isomorphic to $\G_m^r\times \A^{n-r}$ where $r$ is the number of
components of $D$. Hence (because we are working over the complex
numbers $\C$) its fundamental group is a product of infinite cyclic
groups and the finite cover $X\setminus f\1(D)$ is also isomorphic to
$\G_m^r\times \A^{n-r}$. In fact, the homomorphism $f^*$ on rings has
the form
\begin{eqnarray}
\nonumber
\C[z_1,z_1\1,\dots,z_r,z_r\1,z_{r+1},\dots,z_n] & \to &
  \C[t_1,t_1\1,\dots,t_r,t_r\1,t_{r+1},\dots,t_n] \\
\label{gentor}
 z_i & \mapsto &
 \begin{cases}
 m_i & \text{~for $i\le r$}\\
 t_i & \text{~for $i>r$}
 \end{cases}
 \end{eqnarray}
where the $m_i$ are certain monomials (with negative powers allowed) in
$t_1,\dots,t_r$. The natural action of the torus $\G_m^n$ on $X\setminus
f\1(D)$ then descends to an action via $f$ making this map equivariant.
Moreover, since $X$ is the normalisation of $W$ in $X\setminus f\1(D)$,
the action extends to $X$. Since the map $f$ is equivariant there are
only finitely many orbits for the torus action on $X$; in other words,
$X$ is an (affine) {\em toric variety}.

An explicit description of $X$ can be given as follows. Let $M$ be the
free Abelian group of all monomials in the variables $t_1,\dots,t_r$. Let
$M^+$ be the {\em saturated} submonoid of $M$ generated by the $m_i$. Then
$X=\Spec \C[M^+]\times\A^{n-r}$. For future reference, we note that there
is a unique closed orbit in $X$ which maps isomorphically to the closed
orbit $0\times \A^{n-r}$ in $W$. Moreover, $M$ is the group of Cartier
divisors supported on $f\1(D)$ and $M^+$ is the submonoid of effective
Cartier divisors.

Let $N$ be the dual Abelian group to $M$ and
 \[
 N^+=\bigl\{ n \,\bigm|\, \text{$n(m)\ge0$ for all $m\in M^+$}\bigr\}
 \]
the ``dual'' monoid to $M^+$. Then $N^+$ is a finitely generated
saturated monoid in $N$ (like $M^+$ in $M$). Let $\si$ be any finitely
generated submonoid of $N^+$ and
 \[
 M^{\si}=\bigl\{ m \,\bigm|\,
 \text{$n(m)\ge0$ for all $n\in N^+$}\bigr\}
 \]
the dual monoid in $M$ (which contains $M^+$). Then
$X(\si)=\Spec\C[M^{\si}]\times\A^{n-r}$ is an affine toric variety and
the natural morphism $X(\si)\to X$ is birational and equivariant for the
torus action. Moreover, we see that $X(\si)$ is non\-singular and the
pullback to $X(\si)$ of $D$ is a simple normal crossing divisor if and
only if the monoid $\si$ is generated over nonnegative integers by a
(sub-)basis of $N$; such a monoid is called {\em simplicial}.

Let $\Si=\{\si_i\}_{i=1}^n$ be a collection of finitely generated
saturated submonoids of $N^+$ which give a subdivision of $N^+$; i.e.,
$N^+$ is the union of all the $\si_i$ and for any pair $\si_i$, $\si_j$
their intersection is a $\si_k$ for some $k$. We then obtain a collection
of equivariant birational morphisms $X_i=X(\si_i)\to X$ so that if
$\si_j\subset\si_i$ then $X_j\subset X_i$ in a natural way. Thus we can
patch together the $X_i$ to obtain $X_{\Si}\to X$ which is birational and
equivariant (but $X_{\Si}$ need not be affine any more). Moreover, the
condition that the $\si_i$ cover $N^+$ implies that
$X_{\Si}\to X$ is proper.

Thus to obtain a desingularisation of $X$ it is enough to find a
subdivision of $N^+$ consisting entirely of simplicial monoids; an easy
enough combinatorial problem solved by barycentric subdivision. The
intrepid reader is warned that proving that the resulting morphism is
projective is a little intricate since an arbitrary simplicial
subdivision {\em need not} result in a projective morphism; however, the
barycentric subdivision does yield a projective morphism.

\subsection{Local toric singularities}\label{local}
Now we examine the general case locally. Let $x\in X$ be any point such
that $w=f(x)$ lies in $D$. There is an analytic neighbourhood $U$ of $w$
in $W$ and coordinates on $U$ so that $D\cap U$ is given by the
vanishing of a product of coordinate functions; by further shrinking
$U$ we can assume that $U$ is a polydisk in these coordinates. Let $V$
be the component of $f\1(U)$ which contains $x$. The normality of $X$
implies the normality of the analytic space $V$. Hence, the open subset
$V\setminus f\1(D)$ is connected. So it is a topological cover of
$U\setminus D$. The coordinate functions give an inclusion $U\into
W'=\A^n$ so that $D\cap U$ is the restriction to $U$ of a union of
coordinate hyperplanes in $W'$. The resulting inclusion $U\setminus
D\into \G_m^r\times\A^{n-r}$ induces an isomorphism of fundamental
groups. Thus there is a Cartesian square in which the horizontal maps are
inclusions:
 \[
\renewcommand{\arraystretch}{1.5}
\begin{matrix}
V\setminus f\1(D) & \longrightarrow & \G_m^r\times \A^{n-r} \\
f \downarrow \hphantom{f} &&  \hphantom{f'} \downarrow  f' \\
U\setminus D  & \longrightarrow & \G_m^r\times \A^{n-r}
\end{matrix}
 \]
and $f'$ is a covering of the form \eqref{gentor} above. Let $X'$
denote the normalisation of $W'$ in the cover $f'$. By the normality
of $X$ (and hence the normality of $V$ as an analytic space) it
follows that we obtain a commutative diagram
 \[
\renewcommand{\arraystretch}{1.5}
\begin{matrix}
V & \longrightarrow & X'\\
f \downarrow \hphantom{f} &&  \hphantom{f'} \downarrow  f' \\
U & \longrightarrow & W'
\end{matrix}
 \]
so that $V$ is isomorphic to an analytic open neighbourhood of a point
in the toric variety $X'$. By means of the two diagrams above we can
carry over the desingularisation of \ref{affine} to the local analytic
space $V$.

\subsection{General toroidal embeddings}
The local description \ref{local} can be repeated in a suitable
neighbourhood of any point $x\in X$. This shows that the inclusion of
$X\setminus f\1(D)$ in $X$ is a {\em toroidal embedding}. The
desingularisations obtained locally need to be constructed in a coherent
manner so that they ``patch up''.

Let us stratify $W$ by connected components of intersections of the form
\begin{equation}\label{intn}
 (D_{i_1}\cap\dots\cap D_{i_r})\setminus \bigcup_{j\neq i_s} D_j.
\end{equation}
If $U$ and $V$ are as in \ref{local}, then there is a unique stratum
$S$ of $W$ so that $S\cap U$ is closed. Under the inclusions of $U$ in
$W'$ and $V$ in $X'$ of \ref{local} the strata correspond to the
orbits of the torus action. As we have noted in \ref{affine} the
unique closed strata in $U$ and $V$ then become isomorphic. Thus, if
$T=f\1(S)$ then $T\cap V$ is closed in $V$ and the morphism $T\cap V\to
S\cap U$ is an isomorphism; indeed $T\cap V$ and $S\cap U$ are the
restrictions of the closed orbits in $X'$ and $W'$ respectively. Thus we
see that if $S$ is {\em any} stratum in $W$ and $T$ a connected component
of $f\1(S)$ then $T\to S$ is \'etale and proper. We thus stratify $X$ by
connected components of the inverse images of strata in $W$ under $f$.
Let $\{T_a\}_{a\in A}$ denote this stratification; by abuse of notation
we define $S_a=f(T_a)$.

Let $E=\bigcup_{j=1}^m E_j$ be the decomposition into irreducible
components of the inverse image $f\1(D)$ of $D$. Then there is a
function $i\colon \{1,\dots,m\}\to\{1,\dots,n\}$ so that
$f(E_j)=D_{i(j)}$ for all $j$. For any stratum $T_a$ let $X^a$ denote
the complement in $X$ of all those $E_j$ that do not meet $T_a$.
Similarly, we denote by $W^a$ the complement in $W$ of all $D_i$ that do
not meet $S_a$. The morphism $f$ clearly maps $X^a$ to $W^a$.

\begin{lemma}\label{strictness}
Let $M_a$ be the Abelian group of all Cartier divisors in $X^a$ with
support in $E\cap X^a$; let $M^+_a$ be the submonoid consisting of
effective Cartier divisors. Then $M_a$ has rank $r_a=\codim_X T_a$. The
distinct analytic components of $E$ in a neighbourhood of any point $x$
of $X$ are precisely the algebraic components; i.e., $X\setminus E\into
X$ is a {\em strict} toroidal embedding.
\end{lemma}

\begin{proof}
Let $M_a'$ be the group of Cartier divisors on $W^a$ with support on
$D\cap W^a$. Clearly, this is the free Abelian group on those $D_i$ which
contain $S_a$. Since $S_a$ is a connected component of an intersection
of the type \eqref{intn}, there are exactly $r_a=\codim_W S_a$ of such
$D_i$. The pullback homomorphism makes $M'_a$ a subgroup of $M_a$. On the
other hand, consider an analytic neighbourhood $V=f\1(U)$ of some point
$x\in T_a$ as in \ref{local}. If $M_x''$ denotes the group of all
Cartier divisors on $V$ supported on $E\cap V$; then we have noted in
\ref{affine} that $M_x''$ is a free Abelian group of rank $r_a$.
Moreover, $M_a$ is included as a subgroup of $M_x''$ under the
restriction from $X_a$ to $V$.

It follows that the homomorphism $M_a\to M_x''$ has finite cokernel; but
then the normality of $X$ means that it is surjective. In particular, we
see that the distinct analytic components of $E\cap V$ correspond to
distinct algebraic components of $E$. This concludes the proof.
\end{proof}

Let $M_a^+$ denote the monoid of effective divisors in $M_a$; under the
isomorphism $M_a\to M_x''=M$ this maps isomorphically onto the submonoid
$M^+$ considered in \ref{affine}. Thus $X_a$ is smooth (and the
divisor $E$ is a simple normal crossing divisor) if and only if $M_a^+$
is simplicial. If $T_b$ lies in the closure of $T_a$ then $X_a$ is an
open subset of $X_b$. This induces by restriction a (surjective)
homomorphism $M_b\to M_a$ which further restricts to a surjection
$M_b^+\to M_a^+$. Thus we have a (finite) projective system of monoids.

Let $N_a$ and $N_a^+$ be the dual objects as defined in \ref{affine}.
These form a finite injective system of monoids. By a compatible family
$\sS$ of subdivisions we mean a subdivision $\Si_a$ of $N_a^+$ for each
$a$ so that the subdivision $\Si_b$ restricts to the subdivision $\Si_a$
on the submonoid $N_a^+$ of $N_b^+$. We then obtain a proper birational
morphism $X_{\Si_b}\to X_b$ for each $b$ which restricts to $X_{\Si_a}\to
X_a$ on the open subset $X_a$ of $X_b$. Thus, we see that any such
compatible family leads to a proper birational morphism $X_{\sS}\to X$.

Thus, in order to desingularise, we have to find a compatible family of
subdivisions so that each of the new monoids is simplicial. This is
achieved by the barycentric subdivision. As seen earlier, this ensures
that the morphism $X_{\sS}\to X$ is locally projective. Since $X$ is
projective, this morphism is indeed projective.

\nocite{Hironaka}


TITLE: A name for a claw-graph with paths attached to it
QUESTION [4 upvotes]: I wanted to know if the following family of graphs has a name in graph theory: A claw with  paths of any length attached to the three free vertices of the claw. More formally, a connected   acyclic graph, with 1 vertex of degree 3 and the rest of degree 2 or less.
They're interesting because they arise in the study of graph minors. (In particular, if a graph of this type is a minor of another graph G, then it is also a subgraph of G.)

REPLY [2 votes]: See also the question A name for star-graph with long “laces”.


TITLE: Norm of a linear map, rational numbers, continuous functions
QUESTION [2 upvotes]: Let $\{ x_n \}$ be an injective sequence of all rational numbers in $[0,1]$. Let $\mathcal{C} ([0,1])$ with complex values be equipped with the norm:
$$||f|| = \sqrt{\sum_{n=0}^{\infty} 2^{-n} |f(x_n)|^2}, \ \ f \in \mathcal{C} ([0,1])$$
Prove that for every $x \in [0,1]$, $\varphi_x : \mathcal{C} ([0,1]) \ni f  \rightarrow f(x) \in \mathbb{C}$ is a well defined linear map.
Find all $x \in [0,1]$ for which $\varphi _x$ is continuous and find its norm.
I think that the map is continuous for $x \in \mathbb{Q}$, because $|| \varphi_x (f)|| = |f(x)| = |f(x_n)|$ for a certain $n$.
By Holder inequality, $\sum_{n=0}^{\infty} 2^{-n} |f(x_n)|^2 \le \sqrt{\sum_{n=0}^{\infty} 4^{-n} } \sqrt{\sum_{n=0}^{\infty}  |f(x_n)|^4} = \frac{4}{3} \sqrt{\sum_{n=0}^{\infty}  |f(x_n)|^4}$.
But also $\sum_{n=0}^{\infty} 2^{-n} |f(x_n)| \le \sqrt{\sum_{n=0}^{\infty} \sqrt{2}^{-2n} } \sqrt{\sum_{n=0}^{\infty} \sqrt{2}^{-2n} |f(x_n)|^2} = \sqrt{2} \sqrt{\sum_{n=0}^{\infty} 2^{-n} |f(x_n)|^2}$
This works better, doesn't it?
I also don't know how to find a counterexample for $\varphi _x$ continuity when $x$ is not rational. I know that I would need to contruct a continuous function for which $f(x)|$ is not bounded by a positive number times the series by which the norm is defined.
Could you help?

REPLY [1 votes]: Let $x \in \mathbb{R}\setminus\mathbb{Q}$ be fixed. For the construction of a counterexample, the following fact is useful:
For every $k \in \mathbb{N}$, there exists $\varepsilon > 0$ : $x_n \not\in (x-\varepsilon, x+\varepsilon)$ for $n \le k$.
Now, construct a function $f$ with the following properties:

$0 \le f \le 1$,
$f(x) = 1$,
$f(x_n) = 0$, $n \le k$.

Use these properties to compute the norm of $f$ and conclude.


TITLE: Probability of Consecutive Cards
QUESTION [2 upvotes]: I've got a deck of 36 cards... 6 are labeled with #1, 6 with #2, and so on up to 6 with #6. I'm drawing 3 cards from the deck & wondering what the probability is that I will end up with 2 or more consecutive cards (including wrap-arounds--meaning a #6 can wrap-around to a #1 and visa-versa).
I know that it's 66.7% WITH replacement as I actually drew the whole thing out on a spreadsheet with every possible outcome (and got 24/36), but I know that the number will increase WITHOUT replacement, and I'm just not sure how to come up with the formula to figure it out.
I came up with this formula... 12/35 + (24/35 x 12/34)+(16/35 x 12/34) = 74.6%, but that seems way too high as I can't see an 8% jump just because I didn't replace 2 cards.
Is there anybody out there who can help me?

REPLY [0 votes]: Jacobi invert always invert. I am going to find the probability of not finding any consecutive cards then I will do 1-p.
1st draw. it doesn't matter, for practical purpouses let's say you draw a 1
2nd draw. you have to draw either a 1, 3, 4 or 5 (q=23/35).
3rd draw.
if 2nd was 1 -> you have to draw either a 1, 3, 4 or 5 (r=22/34) => $22/34*5/35$
if 2nd was 3 -> you have to draw either a 1, 3 or 5 (r=16/34) => $16/34*6/35$
if 2nd was 4 -> you have to draw either a 1 or 4 (r=10/34) => $10/34*6/35$
if 2nd was 5 -> you have to draw either a 1, 3 or 5 (r=16/34) => $16/34*6/35$
Then your probability is $1-22/34*5/35-16/34*6/35-10/34*6/35-16/34*6/35=414/595$


TITLE: Detective game - Expected number of solutions
QUESTION [0 upvotes]: The detective game involves 6 suspects, 6 weapons and 9 rooms. An item of each set is selected at random and the objective of the game is to find out which of those were choose.
In a version of this game, the itens are selected and then each player recieves, at random, 3 of the remainder cards.
Let $S,R,W$ denote the number of suspects, rooms and weapons recieved by an especified player and $X$ is the number of possible soluctions after the player observes his cards.
a) Write $X$ in function of $S, W, R$
b) Find $E(X)$
My attempt
a) Using the fundamental principle of counting, $X=(6-S)(6-W)(9-R)$, right?
b) Unfortunatelly, I think $S,R,W$ are not independent so I couldnt find a good way to use the last item to calculate this one. I noted that each are hipergeometric variables.
I appreciate some help.
Thanks!

REPLY [2 votes]: You look right about part a.  To find part b you can just create a probability mass function for X and use the familiar $\sum xp_X(x)$ to find its expected value.
Finding the probability function isn't really as bad as it might seem since there's some symmetry with $S$ and $R.$  In fact you only have 6 possible values of $X$:
$$X=(6-S)(6-W)(9-R)=\cases{ 162 & for (6-3)(6-0)(9-0) and (6-0)(6-3)(9-0) \\ 180 & for (6-2)(6-1)(9-0) and (6-1)(6-2)(9-0) \\ 192 & for (6-2)(6-0)(9-1) and (6-0)(6-2)(9-1)\\ 200 & for (6-1)(6-1)(9-1) \\210 & for (6-1)(6-0)(9-2) and (6-0)(6-1)(9-2)\\216 & for (6-0)(6-0)(9-3)}$$
And for any $S$, $W$, and $R$, the probability of drawing $s$ $S$ cards, $w$ $W$ cards, and r $R$ cards is
$${5\choose s}{5\choose w}{8\choose r}\over{18\choose 3}$$
so that
$$p_X(x)=\cases{ 0.02451 &x=162 \\ 0.1225 &x=180 \\ 0.1961&x=192\\ 0.2451 &x=200 \\0.3431&x=210\\0.06863&x=216}$$
So $E[X]=(162)(0.02451)+(180)(0.1225)+(192)(0.1961)+(200)(0.2451)+(210)(0.3431)+(216)(0.06863)\approx199.6$