text:
\subsection{Proof of \Cref{theo:4:num_1}}

The main ingredient of the proof is to use a second sample $\cD_n^{\diamond}$ in order to deal with the data-dependent aspect. Thus, we first define a dummy estimator based on two samples $\cD_n$ and $\cD^{\diamond}_n$ which will be used below. The trees are grown as in Algorithm \ref{algo:3:QRF} using $\cD_n$, but we consider another sample $\cD_n^{\diamond}$ (independent of $\cD_n$ and $\Theta$) which is used to define a dummy estimator:

\begin{equation}\label{eq:5:CDF_estimate_diam}
F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx;\Theta_1,\ldots,\Theta_k, \cD_n^{\diamond}, \cD_n \right) = \sum_{j=1}^{n} w_{n,j}^{\diamond} \left( \bx; \Theta_1,\ldots,\Theta_k, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right) \ind_{ \{Y^{\diamond j} \leqslant y\}}
\end{equation}

where the weights are:

\[
w_{n,j}^{\diamond}\left( \bx; \Theta_1,\ldots,\Theta_k, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right) = \dfrac{1}{k} \sum_{\ell=1}^{k} \dfrac{\ind_{\left\lbrace \bX^{\diamond j} \in A_n \left( \bx;\Theta_\ell,\cD_n \right) \right\rbrace}}{N_n^{\diamond} \left( \bx;\Theta_\ell, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)},\ j=1,\ldots, n
\]

with $N_n^{\diamond} \left( \bx;\Theta_\ell, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)$, the number of elements of $\cD_n^{\diamond}$ that fall into $A_n \left( \bx;\Theta_\ell,\cD_n \right)$. Throughout this section, we shall use the convention $\frac00=0$ in case
$N_n^{\diamond} \left( \bx;\Theta_\ell, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)=0$ and thus $\ind_{\left\lbrace \bX^{\diamond j} \in A_n \left( \bx;\Theta_\ell,\cD_n \right) \right\rbrace}=0$ for $j=1\/,\ldots n$. \\
The weights $w_{n,j}^{\diamond}\left( \bx; \Theta_1,\ldots,\Theta_k, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)$ are nonnegative random variables, as function of $\Theta_1,\ldots,\Theta_k, \bX^{\diamond 1}, \ldots, \bX^{\diamond n},\cD_n$. To lighten the notation in the sequel, we will simply write $F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) = \sum\limits_{j=1}^{n} w_{j}^{\diamond} \left( \bx \right) \ind_{ \{Y^{\diamond j} \leqslant y\}}$ instead of \eqref{eq:5:CDF_estimate_diam}.

Let $\bx \in \cX$ and $y \in \RR$, we have:

\[
\left| F_{k,n}^b \left( \left. y \right| \bX=\bx \right) -  F \left( \left. y \right| \bX=\bx \right) \right| \leqslant \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) -  F \left( \left. y \right| \bX=\bx \right) \right| + \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) - F_{k,n}^b \left( \left. y \right| \bX=\bx \right) \right|
\]

The convergence of the two right-hand terms is handled separately into the following \Cref{prop:5:cv_diam_to_true} and \Cref{lem:5:cv_diam_to_bootstrap}.

\begin{prop}\label{prop:5:cv_diam_to_true}
Consider a random forest which satisfies \Cref{hyp:4:num_1,hyp:4:num_2}. Then,

\[
\forall \bx \in \cX, \forall y \in \RR, \quad F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} F \left( \left. y \right| \bX=\bx \right)
\]
\end{prop}

Hence, \Cref{prop:5:cv_diam_to_true} establishes the consistency for a random forest estimator based on a second sample $\cD_n^\diamond$ independent of $\cD_n$ and $\Theta$. \citet{wager2018estimation} proved that estimators built from honest forests are asymptotically Gaussian. Remark that in \citet{wager2018estimation}, it is also required to control the proportion of chosen observations at each split and in each direction. In our case, going through a kind of honest trees is just a theoretical tool. We go one step further with the following lemma by showing that the estimators built with honest and non-honest trees are close.

\begin{lem}\label{lem:5:cv_diam_to_bootstrap}
Consider a random forest which satisfies \Cref{hyp:4:num_2}. Then,

\[
\forall \bx \in \cX, \forall y \in \RR, \quad \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) -  F_{k,n}^b \left( \left. y \right| \bX=\bx \right) \right| \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0
\]
\end{lem}

Hence, according to \Cref{prop:5:cv_diam_to_true} and \Cref{lem:5:cv_diam_to_bootstrap}, we get

\begin{equation}\label{eq:5:theo1_cv_CDF_estimate_to_true_pointwise_ps}
\forall \bx \in \cX, \forall y \in \RR, \quad F_{k,n}^b \left( \left. y \right| \bX=\bx \right) \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} F \left( \left. y \right| \bX=\bx \right)
\end{equation}

Now, thanks to Dini's second theorem, let us sketch how to obtain the almost sure uniform convergence relative to $y$ of the estimator.

Note that $\left\lbrace Y^{j} \leqslant y \right\rbrace = \left\lbrace U_j \leqslant F_{Y|\bX=\bx} \left( y \right) \right\rbrace$ under \Cref{hyp:4:num_3} with $U_j = F_{Y|\bX=\bx} \left( Y^{j} \right), j=1,\ldots,n$ which are i.i.d random variables. Then, \eqref{eq:5:theo1_cv_CDF_estimate_to_true_pointwise_ps} is equivalent to:

\[
\forall \bx \in \cX, \forall s \in \left[ 0,1 \right],  \quad \sum_{j=1}^{n} w_j^b \left( \bx \right) \ind_{\left\lbrace U_j \leqslant s \right\rbrace} \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} s
\]

As in the proof of Glivenko–Cantelli's Theorem, using that $s \mapsto \sum\limits_{j=1}^{n} w_j^b \left( \bx \right) \ind_{\left\lbrace U_j \left( \omega \right) \leqslant s \right\rbrace}$ is increasing and Dini's second theorem, we get the uniform convergence almost everywhere, which concludes the proof of the theorem. \hfill\qedsymbol

We now turn to the proofs of \Cref{prop:5:cv_diam_to_true} and \Cref{lem:5:cv_diam_to_bootstrap}. To that aim, the following lemma, based on Vapnik-Chervonenkis classes \citep{vapnik71uniform} is a key tool.

\begin{lem}\label{lem:5:lemma_VC}
Consider $\cD_n$ and  $\cD_n^{\diamond}$, two independent datasets of independent $n$ samples of $(\bX,Y)$. Build a tree using $\cD_n$ with bootstrap and bagging procedure driven by $\Theta$. As before, $N^b \left( A_n \left( \Theta \right) \right) = N_n^b \left( \bx;\Theta, \cD_n \right)$ is the number of bootstrap observations of $\cD_n$ that fall into in $A_n \left( \Theta \right) = A_n \left( \bx;\Theta,\cD_n \right)$ and $N^{\diamond} \left( A_n \left( \Theta \right) \right) = N_n^{\diamond} \left( \bx;\Theta, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)$, the number of observations of $\cD_n^{\diamond}$ that fall into in $A_n \left( \Theta \right)$. Then:

\[
\forall \varepsilon > 0, \quad \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^{\diamond} \left( A_n \left( \Theta \right) \right) \right| > \varepsilon \right) \leqslant 24 (n+1)^{2d}e^{- \varepsilon^2/288n}
\]
\end{lem}

\begin{myproof}[Proof of \Cref{lem:5:lemma_VC}]
Let $\varepsilon > 0$ and $\bx \in \cX$, we have:

\begin{align*}
& \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^{\diamond} \left( A_n \left( \Theta \right) \right) \right| > \varepsilon \right) \\
&\leqslant \PP \left( \left| \dfrac{N^b \left( A_n \left( \Theta \right) \right)}{n} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A_n \left( \Theta \right) \right\rbrace} \right| > \dfrac{\varepsilon}{3n} \right) + \PP \left( \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A_n \left( \Theta \right) \right\rbrace} - \PP_{\bX} \left( \bX \in A_n \left( \Theta \right) \right) \right| > \dfrac{\varepsilon}{3n} \right) \\
& \quad + \PP \left( \left| \dfrac{N^{\diamond} \left( A_n \left( \Theta \right) \right)}{n} - \PP_{\bX} \left( \bX \in A_n \left( \Theta \right) \right) \right| > \dfrac{\varepsilon}{3n} \right) \\
&\leqslant \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n B_{j} \left( \Theta^1,\cD_n \right) \ind_{\left\lbrace \bX^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\varepsilon}{3n} \right) \\
& \quad + \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} - \PP_{\bX} \left( \bX \in A \right) \right| >  \dfrac{\varepsilon}{3n} \right) + \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^{\diamond j} \in A \right\rbrace} - \PP_{\bX} \left( \bX \in A \right) \right| >  \dfrac{\varepsilon}{3n} \right)
\end{align*}

with $\cB = \left\lbrace \prod\limits_{i=1}^d \left[ a_i, b_i \right] : a_i, b_i \in \overline{\RR} \right\rbrace$. The last two right-hand terms are handled thanks to a direct application of the Theorem of \citet{vapnik71uniform} over the class $\cB$ whose Vapnik-Chervonenkis dimension is $2d$. This class is nothing more than an extension of the class $\cR$ of rectangles in $\RR^d$. Following the lines of the proof of Theorem 13.8 in \citet{devroye2013probabilistic}, one sees that the classes $\cR$ and $\cB$ have the same Vapnik-Chervonenkis dimension.

A special attention should be given to the first right hand-term. The bootstrap component is represented with the random vector $\left( B_{j} \left( \Theta^1,\cD_n \right) \right)_{j=1, \ldots,n}$ referring to the number of times that the observation $\left( \bX^j, Y^j \right)$ has been chosen from the original dataset. Conditionally to $\cD_n$, this random vector has a multinomial distribution with parameters $ \cM\left( n; 1/n, \ldots, 1/n \right)$. As stated in \citet{arenal1996unconditional}, the bootstrap component can also be represented thanks to the variables selected with replacement from the set $\cD_n = \left\lbrace \left(\bX^1, Y^1 \right), \ldots, \left(\bX^n, Y^n \right) \right\rbrace$. Let $Z^1, \ldots, Z^n$ be these elements which are distributed as $Z = \left( Z_1, Z_2 \right)$ that has a discrete uniform distribution over $\cD_n$ conditionally to $\cD_n$. The first right hand-term is rewritten as:

\begin{align*}
& \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n B_{j} \left( \Theta^1,\cD_n \right) \ind_{\left\lbrace \bX^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\varepsilon}{3n} \right) \\
& = \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\varepsilon}{3n} \right) \\
& = \EE \left[ \PP \left( \left. \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\varepsilon}{3n} \right| \cD_n \right) \right] \\
& = \EE \left[ \PP \left( \left. \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \PP \left( \left. Z_1 \in A \right| \cD_n \right) \right| > \dfrac{\varepsilon}{3n} \right| \cD_n \right) \right]
\end{align*}

By applying Vapnik-Chervonenkis' Theorem under the conditional distribution given $\cD_n$, we get:

\[
\PP \left( \left. \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \PP \left( \left. Z_1 \in A \right| \cD_n \right) \right| > \dfrac{\varepsilon}{3n} \right| \cD_n \right) \leqslant 8 (n+1)^{2d}e^{- \varepsilon^2/288n}
\]

Therefore,

\[
\PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\varepsilon}{3n} \right) \leqslant 8 (n+1)^{2d}e^{- \varepsilon^2/288n}
\]

Finally, we get the overall upper bound:

\[
\PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^{\diamond} \left( A_n \left( \Theta \right) \right) \right| > \varepsilon \right) \leqslant 24 (n+1)^{2d}e^{- \varepsilon^2/288n}
\]
\end{myproof}

\Cref{lem:5:lemma_VC} is the main ingredient of the proof of \Cref{prop:5:cv_diam_to_true}.

\begin{myproof}[Proof of \Cref{prop:5:cv_diam_to_true}]
We aim to prove:

\[
\forall \bx \in \cX, \forall y \in \RR, \quad \PP \left( \omega \in \Omega:\  F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) \underset{n \rightarrow \infty}{\longrightarrow} F \left( \left. y \right| \bX=\bx \right) \right) = 1
\]

Let $\bx \in \cX$ and $y \in \RR$, we have:

\[
\left| F_{k,n}^{\diamond}  \left( \left. y \right| \bx \right) - F \left( \left. y \right| \bx \right) \right| \leqslant \left| \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) \left( \ind_{\{ Y^{\diamond j} \leqslant y \}} -  F \left( \left. y \right| \bX^{\diamond j} \right) \right) \right| + \left| \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) \left( F \left( \left. y \right| \bX^{\diamond j} \right) - F \left( \left. y \right| \bx \right) \right) \right|
\]

Define $\displaystyle W_n =  \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) \left( \ind_{\{ Y^{\diamond j} \leqslant y \}} -  F \left( \left. y \right| \bX^{\diamond j} \right) \right) = \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) Z_j^{\diamond} $ with $Z_j^{\diamond} = \ind_{\{ Y^{\diamond j} \leqslant y \}} -  F \left( \left. y \right| \bX^{\diamond j} \right)$, $n$ i.i.d random variables and $\displaystyle V_n = \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) \left( F \left( \left. y \right| \bX^{\diamond j} \right) - F \left( \left. y \right| \bx \right) \right)$. Remark that $\EE \left[ \left. Z_j^{\diamond} \right| \bX^{\diamond j} \right] = 0$.

\begin{enumerate}[label=\protect\circled{\textbf{\arabic*}},leftmargin=*,noitemsep,parsep=0cm, itemsep=0cm,topsep=0cm,partopsep=0cm,labelsep=*,nolistsep]
\item We first show that $\left( W_{n} \right)_{n \geqslant 1}$ goes to $0$ a.s. in the case of \Cref{hyp:4:num_2} item 2. This is achieved by adapting Hoeffding inequality's proof to our random weighted  sum context.
\end{enumerate}

For any $\varepsilon >0$, $t \in \RR_{+}^*$, we have

\[
\PP \left( W_n > \varepsilon \right) \leq \EE \left[ e^{t W_n} \right] \cdot e^{-t\varepsilon}.
\]

We shall make use of the folklore lemma below.

\begin{lem*}
Let $X$ be a centred random variable, a.s. bounded by $1$. Then, for any $t \in \RR$, $\EE \left[ e^{tX} \right] \leqslant e^{\frac{t^2}{2}}$.
\end{lem*}

Let $t>0$, we have:

\begin{eqnarray*}
\EE \left[ e^{tW_n} \right] &=& \EE \left[ \prod_{j=1}^n e^{t  w_j^{\diamond}(\bx) Z_j^{\diamond}}\right] = \EE \left[ \EE \left[ \left. \prod_{j=1}^n e^{t  w_j^{\diamond}(\bx) Z_j^{\diamond}} \right| \cD_n, \Theta_1, \ldots, \Theta_k, \bX^{\diamond 1}, \ldots,\bX^{\diamond n} \right] \right] \\
\lefteqn{\mbox{conditionally to }  \cD_n, \Theta_1, \ldots, \Theta_k, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \ \mbox{the $w_j^\diamond$ are constant and the $Z_j^\diamond$ are centred,}} \\
\lefteqn{\mbox{independent and bounded by $1$. Thus, using the folklore lemma,} } \\
\EE \left[ e^{tW_n} \right] & =&  \EE \left[ \prod_{j=1}^n \EE \left[ \left. e^{t  w_j^{\diamond}(\bx) Z_j^{\diamond}} \right| \cD_n, \Theta_1, \ldots, \Theta_k, \bX^{\diamond 1}, \ldots, \bX^{\diamond n} \right] \right] \leqslant \EE \left[ \prod_{j=1}^n e^{t^2 w_j^{\diamond}(\bx)^2 /2} \right].
\end{eqnarray*}

Let $K>0$ be such that for all $\ell=1\/, \ldots \/, k$, $N_n^b \left( A_n ( \ell ) \right) = N_n^b \left( \bx;\Theta_\ell,\cD_n \right) \geqslant K \sqrt{n} \left( \ln \left( n \right) \right)^\beta$ a.s. by using \Cref{hyp:4:num_2} item 2. Denote $\Gamma(\ell)$ the event $\left\lbrace N_n^\diamond(A_n(\ell)) < \frac{K \sqrt{n} \left( \ln (n) \right)^\beta}{2} \right\rbrace$. Remark that $\Gamma(\ell)\subset \left\lbrace \left| N_n^\diamond(A_n(\ell)) - N_n^b \left( A_n(\ell) \right) \right| >\frac{K \sqrt{n} \left( \ln (n) \right)^\beta}{2}\right\rbrace$. Thus, using \Cref{lem:5:lemma_VC}, we have that $\PP \left( \Gamma(\ell) \right) \leq 24 \left( n+1 \right)^{2d} \exp \left[ -\frac{K^2 \left( \ln (n) \right)^{2\beta}}{1152} \right]$.

We have

\begin{align*}
\sum_{j=1}^n  w_j^{\diamond}(\bx)^2 &= \sum_{j=1}^n \frac{w_j^{\diamond}(\bx)}{k} \left( \sum_{\ell=1}^k \frac{\ind_{\left\lbrace \bX^{\diamond j} \in A_n(\ell) \right\rbrace}}{N_n^\diamond(A_n(\ell))}
\left( \ind_{\left\lbrace \Gamma(\ell)^c \right\rbrace} + \ind_{\left\lbrace \Gamma(\ell) \right\rbrace} \right) \right) \\
&\leq \sum_{j=1}^n w_j^{\diamond}(\bx)\left( \frac{2}{K \sqrt{n}(\ln n)^\beta} + \frac1k \sum_{\ell=1}^k \ind_{\left\lbrace \bX^{\diamond j} \in A_n(\ell) \right\rbrace} \ind_{\left\lbrace \Gamma(\ell) \right\rbrace} \right)
\end{align*}

So that,

\begin{align*}
\EE \left[ \prod_{j=1}^n e^{t^2 w_j^{\diamond}(\bx)^2 /2} \right] &\leqslant \exp \left[ t^2 / \left( K \sqrt{n} \left( \ln (n) \right)^\beta \right) \right] \times \EE \left[ \exp{\left( \frac{t^2}{2} \cdot \ind_{\left\lbrace \bigcup_{\ell=1}^k \Gamma(\ell) \right\rbrace} \right)} \right] \\
&\leqslant \exp \left[ t^2 / \left( K \sqrt{n} \left( \ln (n) \right)^\beta \right) \right] \times \left( 1 + e^{t^2/2} \sum_{\ell=1}^k \PP \left( \Gamma(\ell) \right) \right) \\
&\leqslant \exp \left[ t^2 / \left( K \sqrt{n} \left( \ln (n) \right)^\beta \right) \right] \times \left( 1 + 24 k \left( n+1 \right)^{2d} \exp \left[\frac{t^2}{2} -\frac{K^2 \left( \ln (n) \right)^{2\beta}}{1152} \right] \right)
\end{align*}

Taking $t^2 = \frac{K^2 \left( \ln (n) \right)^{2\beta}}{576}$ leads to

\[
\PP \left( W_n > \varepsilon \right) \leqslant \left( 1 + 24 k \left( n+1 \right)^{2d} \right) \exp \left[\frac{K \left( \ln (n) \right)^{\beta}}{576 \sqrt{n}} -\frac{\varepsilon K \left( \ln (n) \right)^{\beta}}{24} \right]
\]

The same upper bound is obtained for $\PP \left( W_n < -\varepsilon \right)$ by using that $\PP \left( W_n < -\varepsilon \right) = \PP \left( -W_n > \varepsilon \right)$.

Thus, by using \Cref{hyp:4:num_2}, item 1., $k=O(n^\alpha)$ so that the right hand side is summable,  we conclude that $W_n$ goes to $0$ almost surely.

\begin{enumerate}[label=\protect\circled{\textbf{\arabic*}},leftmargin=*,noitemsep,parsep=0cm, itemsep=0cm,topsep=0cm,partopsep=0cm,labelsep=*,nolistsep,resume]
\item Let us now show that $\left( W_{n} \right)_{n \geqslant 1}$  goes to $0$ a.s. in the case where \Cref{hyp:4:num_2} item 3 is satisfied.
\\
$\textcolor{Scor_color}{\bigstar}$ Let us first show that $\left( W_{n^2} \right)_{n \geqslant 1}$ goes to 0 a.s.
\end{enumerate}

\begin{align*}
\EE \left[ \left( W_n \right)^2 \right] &= \EE \left[ \left( \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) Z_j^{\diamond} \right)^2 \right] \\
&= \sum_{j=1}^{n} \sum_{m=1}^{n} \EE \left[ w_j^{\diamond} \left( \bx \right) w_m^{\diamond} \left( \bx \right) Z_j^{\diamond} Z_m^{\diamond} \right] \\
&= \sum_{j=1}^{n} \EE \left[ w_j^{\diamond^2} \left( \bx \right) Z_j^{\diamond^2} \right] + \sum\limits_{\substack{1 \leqslant j,m \leqslant n \\ j \neq m}} \EE \left[ w_j^{\diamond} \left( \bx \right) w_m^{\diamond} \left( \bx \right) Z_j^{\diamond} Z_m^{\diamond} \right] \\
&\overset{\textnormal{def}}{=} I_n + J_n
\end{align*}

\begin{align*}
I_n &= \EE \left[ \sum_{j=1}^{n} w_j^{\diamond^2} \left( \bx \right) Z_j^{\diamond^2} \right] \\
&\leqslant \EE \left[ \sum_{j=1}^{n} w_j^{\diamond^2} \left( \bx \right) \right] \\
&\leqslant \EE \left[ \dfrac{1}{\displaystyle \min_{\ell=1,\ldots,k} N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \right] ( \textnormal{recall that } \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) = 1 ) \\
&\leqslant \EE \left[ \dfrac{1}{\displaystyle \min_{\ell=1,\ldots,k} N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \ind_{\displaystyle \left\lbrace \exists \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) \right| > \lambda \right\rbrace} \right] \\
&\quad + \EE \left[ \dfrac{1}{\displaystyle \min_{\ell=1,\ldots,k} N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \ind_{\displaystyle \left\lbrace \forall \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) \right| \leqslant \lambda \right\rbrace} \right] \\
\intertext{ where  $\lambda = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{4}$.}
I_n &\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^{\diamond} \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) + \EE \left[ \dfrac{1}{N^b \left( A_n \left( \Theta \right) \right) - \lambda} \right]
\end{align*}

We have:

\[
\EE \left[ \dfrac{1}{N^b \left( A_n \left( \Theta \right) \right) - \lambda} \right] \leqslant \dfrac{4}{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]} + \PP \left( N^b \left( A_n \left( \Theta \right) \right) - \lambda \leqslant \lambda \right)
\]

Using Bienaymé-Tchebychev's inequality, we get:

\begin{align*}
\PP \left( N^b \left( A_n \left( \Theta \right) \right) \leqslant 2 \lambda \right) &\leqslant 4 \dfrac{\var \left( N^b \left( A_n \left( \Theta \right) \right) \right)}{\left( \EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right] \right)^2} \\
&\leqslant 4 \left( \CV \left( N^b \left( A_n \left( \Theta \right) \right) \right) \right)^2
\end{align*}

Finally, thanks to \Cref{lem:5:lemma_VC} and \Cref{hyp:4:num_2} items 1. and 3., there exist $C, K$ and $M$ positive constants such that:

\begin{align*}
I_n &\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^{\diamond} \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) + \dfrac{4}{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]} + 4 \left( \CV \left( N^b \left( A_n \left( \Theta \right) \right) \right) \right)^2 \\
&\leqslant 24 C n^\alpha (n+1)^{2d} \exp \left[- \dfrac{K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{4608} \right] +\dfrac{4}{K \sqrt{n} \left( \ln \left( n \right) \right)^\beta} + \dfrac{4 M^2}{n  \left( \ln \left( n \right) \right)^\gamma}
\end{align*}

The trick of using a second sample $\cD_n^{\diamond}$ independent of the first-one and the random variable $\Theta$ is really important to handle the $J_n$ term. Indeed, we have $J_n = 0$ while the equivalent term encountered in the proof of the Theorem 2 developed by \citet{scornet2015consistency} is handled using a conjecture regarding the correlation behavior of the CART algorithm that is difficult to verify (cf. assumption (H2) of \citet{scornet2015consistency}). Indeed:

\begin{align*}
J_n &= \sum\limits_{\substack{1 \leqslant j,m \leqslant n \\ j \neq m}} \EE \left[ w_j^{\diamond} \left( \bx \right) w_m^{\diamond} \left( \bx \right) Z_j^{\diamond} Z_m^{\diamond} \right] \\
&= \sum\limits_{\substack{1 \leqslant j,m \leqslant n \\ j \neq m}} \EE \left[ \EE \left[ \left. w_j^{\diamond} \left( \bx \right) w_m^{\diamond} \left( \bx \right) Z_j^{\diamond} Z_m^{\diamond} \right| \Theta_1,\ldots,\Theta_k, \cD_n, \bX^{\diamond 1}, \ldots, \bX^{\diamond n}, Y^{\diamond j} \right] \right] \\
&= \sum\limits_{\substack{1 \leqslant j,m \leqslant n \\ j \neq m}} \EE \left[ w_j^{\diamond} \left( \bx \right) w_m^{\diamond} \left( \bx \right) Z_j^{\diamond} \EE \left[ \left. Z_m^{\diamond} \right| \bX^{\diamond m} \right] \right] \textnormal{using that } w_j^{\diamond} \left( \bx \right), w_m^{\diamond} \left( \bx \right) \textnormal{ and } \\
& Z_j^{\diamond} \textnormal{ are } \Theta_1,\ldots, \Theta_k, \cD_n, \left( \bX^{\diamond j} \right)_{j=1,\ldots,n}, Y^{\diamond j} \textnormal{ measurable.} \\
&= 0 \text{ because } \EE \left[ \left. Z_m^{\diamond} \right| \bX^{\diamond m} \right] = 0
\end{align*}

Finally:

\[
\forall \varepsilon > 0, \quad \PP \left( \left| W_n \right| \geqslant \varepsilon \right) \leqslant \dfrac{\EE \left[ \left( W_n \right)^2 \right]}{\varepsilon^2} = \dfrac{I_n}{\varepsilon^2}
\]

Hence, since $\displaystyle\sum_{n\geq 1} I_{n^2}<\infty$, Borel–Cantelli Lemma gives:

\[
\forall \varepsilon > 0, \quad \PP \left( \limsup\limits_{n \rightarrow \infty} \left\lbrace \left| W_{n^2} \right| \geqslant \varepsilon \right\rbrace \right) = 0
\]

which implies that $\displaystyle W_{n^2} \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0$.

$\textcolor{Scor_color}{\bigstar}$ Let us now show that $\left( W_{n} \right)_{n \geqslant 1}$ converges almost surely to 0.

Let $p=p \left( n \right) = \left\lfloor \sqrt{n} \right\rfloor$, we have $\displaystyle W_n - W_{p^2} = \sum_{j=p^2+1}^{n} w_j^{\diamond} \left(\bx \right) Z_j^{\diamond}$. Fix $\varepsilon > 0$ and consider again $\lambda = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{4}$,

\begin{align*}
& \PP \left( \left| W_n - W_{p^2} \right| \geqslant \varepsilon \right) \\
&\leqslant \PP \left( \sum_{j=p^2+1}^{n} w_j^{\diamond} \left(\bx \right) \left| Z_j^{\diamond} \right| \geqslant \varepsilon \right) \\
&\leqslant \PP \left( \dfrac{2 \sqrt{n}}{\displaystyle \min_{\ell=1,\ldots,k} N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \geqslant \varepsilon \right)  \\
&\leqslant \PP \left( \dfrac{2 \sqrt{n}}{\displaystyle \min_{\ell=1,\ldots,k} N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \geqslant \varepsilon, \exists \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) \right| > \lambda \right) \\
&\quad + \PP \left( \dfrac{2 \sqrt{n}}{\displaystyle \min_{\ell=1,\ldots,k} N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \geqslant \varepsilon, \forall \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) \right| \leqslant \lambda \right) \\
&\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^{\diamond} \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) + \PP \left( \dfrac{2 \sqrt{n}}{N^b \left( A_n \left( \Theta \right) \right) - \lambda} \geqslant \varepsilon \right)
\end{align*}

Using Bienaymé-Tchebychev's inequality and that $\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right] \geqslant \dfrac{8\sqrt{n}}{\varepsilon}$ for $n$ large enough, thanks to \Cref{hyp:4:num_2} item 3., we have:

\begin{align*}
\PP \left( N^b \left( A_n \left( \Theta \right) \right) \leqslant \lambda + \dfrac{2\sqrt{n}}{\varepsilon} \right) &\leqslant 4 \dfrac{\var \left( N^b \left( A_n \left( \Theta \right) \right) \right)}{\left( \EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right] \right)^2} \\
&\leqslant 4 \left( \CV \left( N^b \left( A_n \left( \Theta \right) \right) \right) \right)^2
\end{align*}

Finally, thanks to \Cref{lem:5:lemma_VC} and \Cref{hyp:4:num_2} items 1. and 3., we have for $n$ large enough:

\begin{align*}
\PP \left( \left| W_n - W_{p^2} \right| \geqslant \varepsilon \right) &\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^{\diamond} \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) + 4 \left( \CV \left( N^b \left( A_n \left( \Theta \right) \right) \right) \right)^2 \\
&\leqslant 24 C n^\alpha (n+1)^{2d} \exp \left[- \dfrac{K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{4608} \right] + \dfrac{4 M^2}{n \left( \ln \left( n \right) \right)^\gamma}
\end{align*}

Hence, using Borel–Cantelli Lemma:

\[
\forall \varepsilon > 0, \quad \PP \left( \limsup\limits_{n \rightarrow \infty} \left\lbrace \left| W_{n} - W_{p^2} \right| \geqslant \varepsilon \right\rbrace \right) = 0
\]

which implies that the random variable $\displaystyle W_{n} - W_{p^2} \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0$.

From this, we deduce that $\left( W_n \right)_{n \geqslant 1}$ goes to 0 a.s.

\begin{enumerate}[label=\protect\circled{\textbf{\arabic*}},leftmargin=*,noitemsep,parsep=0cm, itemsep=0cm,topsep=0cm,partopsep=0cm,labelsep=*,nolistsep,resume]
\item Finally, we show that $\left( V_{n} \right)_{n \geqslant 1}$ goes to 0 a.s.
\end{enumerate}

\begin{align*}
& \left| V_n \right| =  \left| \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) \left( F \left( \left. y \right| \bX^{\diamond j} \right) - F \left( \left. y \right| \bx \right) \right) \right| \\
&\leqslant \dfrac{1}{k} \sum_{\ell=1}^k \left( \sum_{j=1}^{n} \dfrac{\ind_{\left\lbrace \bX^{\diamond j} \in A_n \left( \bx;\Theta_\ell,\cD_n \right) \right\rbrace}}{N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \left| F \left( \left. y \right| \bX^{\diamond j} \right) - F \left( \left. y \right| \bx \right) \right| \right) \\
&\leqslant \dfrac{1}{k} \sum_{\ell=1}^k \left( \sum_{j=1}^{n} \dfrac{\ind_{\left\lbrace \bX^{\diamond j} \in A_n \left( \bx;\Theta_\ell,\cD_n \right) \right\rbrace}}{N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} \sup_{\bz \in A_n \left( \bx;\Theta_\ell, \cD_n \right)} \left| F \left( \left. y \right| \bz \right) - F \left( \left. y \right| \bx \right) \right| \right) \\
&\leqslant \dfrac{1}{k} \sum_{\ell=1}^k \sup_{\bz \in A_n \left( \bx;\Theta_\ell, \cD_n \right)} \left| F \left( \left. y \right| \bz \right) - F \left( \left. y \right| \bx \right) \right|
\end{align*}

Hence, by using \Cref{hyp:4:num_1}, we have:
\[
\left| \sum_{j=1}^{n} w_j^{\diamond} \left( \bx \right) \left( F \left( \left. y \right| \bX^{\diamond j} \right) - F \left( \left. y \right| \bx \right) \right) \right| \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0
\]

This allows us to conclude that

\[
\forall \bx \in \cX, \forall y \in \RR, \quad F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} F \left( \left. y \right| \bX=\bx \right)
\]
\end{myproof}

Let us now turn to the proof of \Cref{lem:5:cv_diam_to_bootstrap} which shows that the dummy estimator $F_{k,n}^{\diamond}$ is close to the interesting one $F_{k,n}^b$.

\begin{myproof}[Proof of \Cref{lem:5:cv_diam_to_bootstrap}]
Let $\bx \in \cX$ and $y \in \RR$, we have that:

\begin{align*}
& \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) - F_{k,n}^b \left( \left. y \right| \bX=\bx \right) \right| \\
&= \left| \dfrac{1}{k} \sum_{\ell=1}^k \left( \sum_{j=1}^{n} \dfrac{\ind_{\left\lbrace \bX^{\diamond j} \in A_n \left( \bx;\Theta_\ell,\cD_n \right) \right\rbrace} \ind_{\left\lbrace Y^{\diamond j} \leqslant y \right\rbrace}}{N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)} - \sum_{j=1}^{n} \dfrac{B_{j} \left( \Theta_\ell^1,\cD_n \right) \ind_{\left\lbrace \bX^j \in A_n \left( \bx;\Theta_\ell,\cD_n \right) \right\rbrace} \ind_{\left\lbrace Y^{j} \leqslant y \right\rbrace}}{N_n^b \left( \bx; \Theta_\ell, \cD_n \right)} \right) \right| \\
&= \left| \dfrac{1}{k} \sum_{\ell=1}^k \left( \dfrac{\# \left\lbrace j \leqslant J^{\diamond} \ / \ \bX^{\diamond (j)} \in A_n \left( \Theta_\ell \right) \right\rbrace}{N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)} - \dfrac{\sum\limits_{j \in \cS} B_{j} \left( \Theta_\ell^1,\cD_n \right)}{N^b \left( A_n \left( \Theta_\ell \right) \right)} \right) \right| \textnormal{ with } \cS = \left\lbrace j \leqslant J \ / \ \bX^{(j)} \in A_n \left( \Theta_\ell \right) \right\rbrace
\end{align*}

where we denote $A_n \left( \Theta_\ell \right) = A_n \left( \bx;\Theta_\ell,\cD_n \right), N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) = N_n^{\diamond} \left( \bx; \Theta_\ell,\bX^{\diamond 1}, \ldots, \bX^{\diamond n}, \cD_n \right)$ and $N^b \left( A_n \left( \Theta_\ell \right) \right) = N_n^b \left( \bx; \Theta_\ell, \cD_n \right)$. $J, J^\diamond$ are such that $Y^{\diamond \left( J^\diamond \right)} \leqslant y < Y^{\diamond \left( J^{\diamond}+1 \right)}$ and $Y^{\left( J \right)} \leqslant y < Y^{\left( J+1 \right)}$, with $Y^{\diamond (j)}$ (resp. $Y^{(j)}$) the order statistics of $(Y^{\diamond 1}, \ldots, Y^{\diamond n})$ (resp. $(Y^1, \ldots, Y^n)$) and the $\bX^{\diamond (j)}$  (resp. $\bX^{(j)}$) the corresponding $\bX^{\diamond p}$'s (resp. $\bX^p$'s).

Let us consider for some $\ell \in \llbracket 1,k \rrbracket$,

\[
G = \dfrac{\# \left\lbrace j \leqslant J^{\diamond} \ / \ \bX^{\diamond (j)} \in A_n \left( \Theta_\ell \right) \right\rbrace}{N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)} - \dfrac{\sum\limits_{j \in \cS} B_{j} \left( \Theta_\ell^1,\cD_n \right)}{N^b \left( A_n \left( \Theta_\ell \right) \right)} \overset{\textnormal{def}}{=} \dfrac{N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)}{N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)} - \dfrac{N_J \left( A_n \left( \Theta_\ell \right) \right)}{N^b \left( A_n \left( \Theta_\ell \right) \right)}.
\]

We have,

\begin{align*}
\left| G \right| &\leqslant \dfrac{\left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^b \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^b \left( A_n \left( \Theta_\ell \right) \right)} + \dfrac{\left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^b \left( A_n \left( \Theta_\ell \right) \right)} \\
&\overset{\textnormal{def}}{=} \left| G_1 \right| + \left| G_2 \right|
\end{align*}

We continue the proof below in the case where \Cref{hyp:4:num_2} item 3. is satisfied. The case where item 2. is verified is done easier following the same lines. Let $\varepsilon >0$.

\begin{enumerate}[label=\protect\circled{\textbf{\arabic*}},leftmargin=*,noitemsep,parsep=0cm, itemsep=0cm,topsep=0cm,partopsep=0cm,labelsep=*,nolistsep]
\item We are now going to show the almost everywhere convergence to 0 for each term $G_1$ and $G_2$. Let us start with $G_1$.
\end{enumerate}

\begin{align*}
\PP \left( \left| G_1 \right| > \varepsilon \right) &= \PP \left( \dfrac{\left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^b \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^b \left( A_n \left( \Theta_\ell \right) \right)} > \varepsilon \right) \\
&= \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^b \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N^b \left( A_n \left( \Theta_\ell \right) \right), N^b \left( A_n \left( \Theta_\ell \right) \right) > \lambda \right) \\
&\quad + \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^b \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N^b \left( A_n \left( \Theta_\ell \right) \right), N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \lambda \right) \\ \intertext{ where $\lambda = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{2}$}
&\leqslant \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^b \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) + \PP \left( N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \lambda \right)
\end{align*}

Again, thanks to the Bienaymé-Tchebychev's inequality:

\begin{align}
\PP \left( N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \lambda \right) &\leqslant 4 \dfrac{\var \left( N^b \left( A_n \left( \Theta_\ell \right) \right) \right)}{\left( \EE \left[ N^b \left( A_n \left( \Theta_\ell \right) \right) \right] \right)^2} \nonumber \\
&\leqslant 4 \left( \CV \left( N^b \left( A_n \left( \Theta \right) \right) \right) \right)^2 \label{eq:5:upper_bound_with_CV}
\end{align}

Now, using \Cref{lem:5:lemma_VC} and \Cref{hyp:4:num_2}, we get:

\begin{align*}
\PP \left( \left| G_1 \right| > \varepsilon \right) &\leqslant \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^b \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) + 4 \left( \CV \left( N^b \left( A_n \left( \Theta \right) \right) \right) \right)^2 \\
&\leqslant 24(n+1)^{2d} \exp \left[- \dfrac{\varepsilon^2 K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{1152} \right] + \dfrac{4M^2}{n  \left( \ln \left( n \right) \right)^\gamma}
\end{align*}

Then, thanks to Borel–Cantelli Lemma:

\[
\forall \varepsilon > 0, \quad \PP \left( \limsup\limits_{n \rightarrow \infty} \left\lbrace \left| G_1 \right| > \varepsilon \right\rbrace \right) = 0
\]

which implies $\displaystyle G_1 \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0$.

\begin{enumerate}[label=\protect\circled{\textbf{\arabic*}},leftmargin=*,noitemsep,parsep=0cm, itemsep=0cm,topsep=0cm,partopsep=0cm,labelsep=*,nolistsep,resume]
\item Now, consider the $G_2$ term:
\end{enumerate}

\begin{align*}
\PP \left( \left| G_2 \right| > \varepsilon \right) &= \PP \left( \dfrac{\left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^b \left( A_n \left( \Theta_\ell \right) \right)} > \varepsilon \right) \\
&= \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N \left( A_n \left( \Theta_\ell \right) \right), N^b \left( A_n \left( \Theta_\ell \right) \right) > \lambda \right) \\
&\quad + \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N^b \left( A_n \left( \Theta_\ell \right) \right), N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \lambda \right) \\
\intertext{ where  $\lambda = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{2}$}
&\leqslant \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) + \PP \left( N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \lambda \right) \\
\end{align*}

We are going to bound the first term by using again the Vapnik-Chervonenkis theory. By considering the class $\cB = \left\lbrace \prod\limits_{i=1}^{d} \left[ a_i, b_i \right] \times \left] -\infty, y \right] : a_i, b_i \in \overline{\RR} \right\rbrace$, we have:

\begin{align}\label{eq:class_B}
&\PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) \nonumber \\
&= \PP \left( \dfrac{\left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right|}{n} > \dfrac{\varepsilon \lambda}{n} \right) \nonumber \\
&\leqslant \PP \left( \left| \dfrac{N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)}{n} - \PP_{\bX,Y}\left( \left( \bX, Y \right) \in A_n \left( \Theta_\ell \right) \times \left] -\infty, y \right] \right) \right| > \dfrac{\varepsilon \lambda}{3n} \right) \nonumber \\
& \quad + \PP \left( \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \left( \bX^j, Y^j \right) \in A_n \left( \Theta_\ell \right) \times \left] -\infty, y \right] \right\rbrace} - \PP_{\bX,Y}\left( \left( \bX, Y \right) \in A_n \left( \Theta_\ell \right) \times \left] -\infty, y \right] \right) \right| > \dfrac{\varepsilon \lambda}{3n} \right)\nonumber \\
& \quad + \PP \left( \left| \dfrac{N_J \left( A_n \left( \Theta_\ell \right) \right)}{n} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \left( \bX^j, Y^j \right) \in A_n \left( \Theta_\ell \right) \times \left] -\infty, y \right] \right\rbrace} \right| > \dfrac{\varepsilon \lambda}{3n} \right) \nonumber \\
&\leqslant \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \left( \bX^{\diamond j}, Y^{\diamond j} \right) \in A \right\rbrace} - \PP_{\bX,Y} \left( \left(\bX, Y \right) \in A \right)\right| > \dfrac{\varepsilon \lambda}{3n} \right) \\
&\quad + \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \left( \bX^j, Y^j \right) \in A \right\rbrace} - \PP_{\bX,Y} \left( \left(\bX, Y \right) \in A \right)\right| > \dfrac{\varepsilon \lambda}{3n} \right) \nonumber \\
& \quad + \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n B_{j} \left( \Theta_\ell^1,\cD_n \right) \ind_{\left\lbrace \left( \bX^j, Y^j \right) \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \left( \bX^j, Y^j \right) \in A \right\rbrace} \right| > \dfrac{\varepsilon \lambda}{3n} \right) \nonumber
\end{align}

Let us make some comments on Vapnik-Chervonenkis dimension of the class $\cB$. If we had the class $\left\lbrace \prod\limits_{i=1}^{d} \left[ a_i, b_i \right] \times \left] -\infty, c \right] : a_i, b_i \in \overline{\RR}, c \in \RR \right\rbrace$, it could be shown by calculations similar to those from Theorem 13.8 in \citet{devroye2013probabilistic} that the Vapnik-Chervonenkis dimension is $2d+1$. But in our case, the element $c$ is fixed as $y$, then all the possibilities to break the points are related to the elements $a_i, b_i$, which thus gives us a Vapnik-Chervonenkis dimension equals to $2d$. Therefore, the first two right-hand terms are handled thanks to a direct application of the Theorem of \citet{vapnik71uniform} over the class $\cB$. The latter deserves special attention.

The third term is treated as in the proof of \Cref{lem:5:lemma_VC}. We use as before, the representation of the bootstrap component with the random variables $Z_\ell^1, \ldots, Z_\ell^n$.
We apply Vapnik-Chervonenkis' Theorem under the conditional distribution given $\cD_n$ and get:

\[
\PP \left( \left. \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_\ell^j \in A \right\rbrace} - \PP \left( \left. Z \in A \right| \cD_n \right) \right| > \dfrac{\varepsilon \lambda}{3n} \right| \cD_n \right) \leqslant 8 (n+1)^{2d}e^{- \varepsilon^2 \lambda^2/288n}
\]

Therefore,

\[
\PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_\ell^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \left( \bX^j, Y^j \right) \in A \right\rbrace} \right| > \dfrac{\varepsilon \lambda}{3n} \right) \leqslant 8 (n+1)^{2d}e^{- \varepsilon^2 \lambda^2/288n}
\]

Hence, at last

\[
\PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) \leqslant 24 (n+1)^{2d}e^{- \varepsilon^2 \lambda^2/288n}
\]

As a consequence, Equation \eqref{eq:5:upper_bound_with_CV} and \Cref{hyp:4:num_2} lead to:

\begin{align*}
\PP \left( \left| G_2 \right| > \varepsilon \right)  &\leqslant \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) + 4 \left( \CV \left( N \left( A_n \left( \Theta \right) \right) \right) \right)^2 \\
&\leqslant 24(n+1)^{2d} \exp \left[- \dfrac{\varepsilon^2 K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{1152} \right] + \dfrac{4M^2}{n  \left( \ln \left( n \right) \right)^\gamma}
\end{align*}

Thanks to Borel–Cantelli Lemma, we get:

\[
\forall \varepsilon > 0, \quad \PP \left( \limsup\limits_{n \rightarrow \infty} \left\lbrace \left| G_2 \right| > \varepsilon \right\rbrace \right) = 0
\]

which implies that $\displaystyle G_2 \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0$.

We conclude that $G$ goes to $0$ for all $\ell$, thus

\[
\forall \bx \in \cX, \forall y \in \RR, \quad \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) -  F_{k,n}^b \left( \left. y \right| \bX=\bx \right) \right| \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0
\]

In the case where \Cref{hyp:4:num_2} item 2. is verified, it exists $K>0$ such that

\[
N^b \left( A_n \left( \Theta_\ell \right) \right) \geqslant K \sqrt{n} \left( \ln \left( n \right) \right)^\beta \ a.s.
\]

So that $\PP(|G_1|>\varepsilon)$ and $\PP(|G_2|>\varepsilon)$ are bounded above respectively by

\begin{itemize}
\item $ \PP \left( \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon K \sqrt{n} \left( \ln \left( n \right) \right)^\beta \right)$
\item and $\PP \left( \left|  N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon K \sqrt{n} \left( \ln \left( n \right) \right)^\beta \right)$.
\end{itemize}

A simple application of \Cref{lem:5:lemma_VC} and an adaptation of it to $N_J \left( A_n \left( \Theta_\ell \right) \right)$ show that $G_1$ and $G_2$ go to $0$ a.s.
\end{myproof}

This conclude the proof of \Cref{theo:4:num_1}, we now sketch the proof of \Cref{theo:4:num_2} which is a bit simpler.


TITLE: The birational positivity of a Line Bundle
QUESTION [0 upvotes]: I have a question about F. Bastianelli's article: Measure of irrationality for hypersurfaces of large degree
We have the Definition 1.1.

A line bundle $L$ on $X$ satisfies property $(BVA)_p$ if there exists a proper Zariski-closed subset $Z = Z(L) \subset X$ depending on L such that
  $$ H^0(X,L) \to H^0(X, L \otimes \mathcal{O}_{\xi}) $$
  surjects for every finite subscheme $\xi \subset X$ of length $p+1$ whose support is disjoint from $Z$.

Thus $(BVA)_0$ is equivalent to requiring that $L$ be effective, and $(BVA)_1$ is what is often called "birationally very ample".
My question
I wanted to show that if $L$ is a line bundle on $X$ satisfying $(BVA)_p$ and $E$ is an effective divisor on $X$, then $\mathcal{O}_X(L+E)$ satisfies $(BVA)_p$.
What I did so far
By applying the definition above, since $L$ satisfies $(BVA)_p$ then there exist a Zariski-closed subset $Z$ such as for every finite subscheme $\xi \subset X$ of length $p+1$ whose support is disjoint from $Z$, the map
$$ H^0(X,L) \to H^0(X, L \otimes \mathcal{O}_{\xi}) $$
is surjective.
On the other hand, since $E$ is effective, then it verifies $(BVA)_0$ (i.e. there exist a Zariski-closed subset $Z'$ such as for every finite subscheme $\xi' \subset X$ of length $1$ whose support is disjoint from $Z'$, the map
$$ H^0(X,E) \to H^0(X, E \otimes \mathcal{O}_{\xi'}) $$
is surjective.)
Where I'm stuck
To show that $\mathcal{O}_X(L+E)$ satisfies $(BVA)_p$, which Zariski-closed subset that we'll take? My suggestion is $Z \cup Z'$, am I right? and if the answer is yes, can I take any subscheme $\Xi \subset X \backslash (Z \cup Z')$ for the finite subscheme of length $p+1$ whose support is disjoint from $Z \cup Z'$ ?
Thanks in advance for any hint or enlightement?
K. Y.

REPLY [1 votes]: The answer is yes.
It is enough to see that since $E$ is effective, then $L + E_{|X \ Supp E} = L \otimes \mathcal{O}_X = L$.


TITLE: diagonalizability, normal matrices
QUESTION [1 upvotes]: Problem:
I want to prove that if $A^3$ is unitary, then $A$ is diagonalizable. Definitely, since $A^3$ is unitary, then it is normal, and we know that every normal matrix is diagonalizable. So, there exists $U$ unitary such that: $U^{*}A^{3}U=D=\begin{bmatrix}
 \lambda_{1}^{3}&0  &0  &0 \\
 0&\lambda_{2}^{3}  &0  &0 \\
0 & 0 &  \lambda_{3}^{3}&0 \\
 0& 0 &0  & \lambda_{n}^{3}
\end{bmatrix}$
Where $\lambda_{i}$ are eigenvalues of $A$. I am thinking to prove that $A$ is also normal, which implies that $A$ is diagonalizable, but I have no idea how to approach it.

REPLY [1 votes]: Another approach is the following:
Lemma. Matrix $A$ is diagonalizable if and only if the minimal polynomial of $A$ can be factorized into different linear factors, i.e. $m_A(x) = \Pi (x - \lambda_i)$ with distinct $\lambda_i$ 's.
Now from the assumptions we know that $A^3$ possesses the property above, therefore $m_{A^3}(x) = \Pi (x - \lambda_i)$. Note that $\lambda_i$ are distinct and nonzero (since A is invertible, from the fact that $A^3$ is unitary and invertible.)
Also $\Pi (A^3 - \lambda_i I) = 0$. Thus the polynomial $p(x) = \Pi(x^3-\lambda_i)$ is an annihilator of the matrix $A$.
Now factor the polynomial $p(x)$ into linear factors over $\mathbb{C}[x]$ using 3rd roots of unity. Note that the resulting polynomial is a product of distinct linear factors $x-z_i$ (Again using the properties: $\lambda_i$ are nonzero and distinct.) Thus using the lemma at the top of the article, one can conclude that the minimal polynomial of $A$ which divides $p(x)$, satisfies the desiring property and we are done.
strong text


text:
section \<open>Interpreted Transition Systems and Traces\<close>

theory Transition_System_Interpreted_Traces
imports
  Transition_System_Traces
  "Basics/Stuttering"
begin

  locale transition_system_interpreted_traces =
    transition_system_interpreted ex en int +
    transition_system_traces ex en ind
    for ex :: "'action \<Rightarrow> 'state \<Rightarrow> 'state"
    and en :: "'action \<Rightarrow> 'state \<Rightarrow> bool"
    and int :: "'state \<Rightarrow> 'interpretation"
    and ind :: "'action \<Rightarrow> 'action \<Rightarrow> bool"
    +
    assumes independence_invisible: "a \<in> visible \<Longrightarrow> b \<in> visible \<Longrightarrow> \<not> ind a b"
  begin

    lemma eq_swap_lproject_visible:
      assumes "u =\<^sub>S v"
      shows "lproject visible (llist_of u) = lproject visible (llist_of v)"
      using assms independence_invisible by (induct, auto)
    lemma eq_fin_lproject_visible:
      assumes "u =\<^sub>F v"
      shows "lproject visible (llist_of u) = lproject visible (llist_of v)"
      using assms eq_swap_lproject_visible by (induct, auto)
    lemma le_fin_lproject_visible:
      assumes "u \<preceq>\<^sub>F v"
      shows "lproject visible (llist_of u) \<le> lproject visible (llist_of v)"
    proof -
      obtain w where 1: "u @ w =\<^sub>F v" using assms by rule
      have "lproject visible (llist_of u) \<le>
        lproject visible (llist_of u) $ lproject visible (llist_of w)" by auto
      also have "\<dots> = lproject visible (llist_of (u @ w))" using lappend_llist_of_llist_of by auto
      also have "\<dots> = lproject visible (llist_of v)" using eq_fin_lproject_visible 1 by this
      finally show ?thesis by this
    qed
    lemma le_fininf_lproject_visible:
      assumes "u \<preceq>\<^sub>F\<^sub>I v"
      shows "lproject visible (llist_of u) \<le> lproject visible (llist_of_stream v)"
    proof -
      obtain w where 1: "w \<le>\<^sub>F\<^sub>I v" "u \<preceq>\<^sub>F w" using assms by rule
      have "lproject visible (llist_of u) \<le> lproject visible (llist_of w)"
        using le_fin_lproject_visible 1(2) by this
      also have "\<dots> \<le> lproject visible (llist_of_stream v)" using 1(1) by blast
      finally show ?thesis by this
    qed
    lemma le_inf_lproject_visible:
      assumes "u \<preceq>\<^sub>I v"
      shows "lproject visible (llist_of_stream u) \<le> lproject visible (llist_of_stream v)"
    proof (rule lproject_prefix_limit)
      fix w
      assume 1: "w \<le> llist_of_stream u" "lfinite w"
      have 2: "list_of w \<le>\<^sub>F\<^sub>I stream_of_llist (llist_of_stream u)" using 1 by blast
      have 3: "list_of w \<preceq>\<^sub>F\<^sub>I v" using assms 2 by auto
      have "lproject visible w = lproject visible (llist_of (list_of w))" using 1(2) by simp
      also have "\<dots> \<le> lproject visible (llist_of_stream v)" using le_fininf_lproject_visible 3 by this
      finally show "lproject visible w \<le> lproject visible (llist_of_stream v)" by this
    qed
    lemma eq_inf_lproject_visible:
      assumes "u =\<^sub>I v"
      shows "lproject visible (llist_of_stream u) = lproject visible (llist_of_stream v)"
      using le_inf_lproject_visible assms by (metis antisym eq_infE)

    lemma stutter_selection_lproject_visible:
      assumes "run u p"
      shows "stutter_selection (lift (liset visible (llist_of_stream u)))
        (llist_of_stream (smap int (p ## trace u p)))"
    proof
      show "0 \<in> lift (liset visible (llist_of_stream u))" by auto
    next
      fix k i
      assume 3: "enat (Suc k) < esize (lift (liset visible (llist_of_stream u)))"
      assume 4: "nth_least (lift (liset visible (llist_of_stream u))) k < i"
      assume 5: "i < nth_least (lift (liset visible (llist_of_stream u))) (Suc k)"
      have 6: "int ((p ## trace u p) !! nth_least (lift (liset visible (llist_of_stream u))) k) =
        int ((p ## trace u p) !! i)"
      proof (rule execute_inf_word_invisible)
        show "run u p" using assms by this
        show "nth_least (lift (liset visible (llist_of_stream u))) k \<le> i" using 4 by auto
      next
        fix j
        assume 6: "nth_least (lift (liset visible (llist_of_stream u))) k \<le> j"
        assume 7: "j < i"
        have 8: "Suc j \<notin> lift (liset visible (llist_of_stream u))"
        proof (rule nth_least_not_contains)
          show "enat (Suc k) < esize (lift (liset visible (llist_of_stream u)))" using 3 by this
          show "nth_least (lift (liset visible (llist_of_stream u))) k < Suc j" using 6 by auto
          show "Suc j < nth_least (lift (liset visible (llist_of_stream u))) (Suc k)" using 5 7 by simp
        qed
        have 9: "j \<notin> liset visible (llist_of_stream u)" using 8 by auto
        show "u !! j \<notin> visible" using 9 by auto
      qed
      show "llist_of_stream (smap int (p ## trace u p)) ?! i = llist_of_stream (smap int (p ## trace u p)) ?!
        nth_least (lift (liset visible (llist_of_stream u))) k"
        using 6 by (metis lnth_list_of_stream snth_smap)
    next
      fix i
      assume 1: "finite (lift (liset visible (llist_of_stream u)))"
      assume 3: "Max (lift (liset visible (llist_of_stream u))) < i"
      have 4: "int ((p ## trace u p) !! Max (lift (liset visible (llist_of_stream u)))) =
        int ((p ## trace u p) !! i)"
      proof (rule execute_inf_word_invisible)
        show "run u p" using assms by this
        show "Max (lift (liset visible (llist_of_stream u))) \<le> i" using 3 by auto
      next
        fix j
        assume 6: "Max (lift (liset visible (llist_of_stream u))) \<le> j"
        assume 7: "j < i"
        have 8: "Suc j \<notin> lift (liset visible (llist_of_stream u))"
        proof (rule ccontr)
          assume 9: "\<not> Suc j \<notin> lift (liset visible (llist_of_stream u))"
          have 10: "Suc j \<in> lift (liset visible (llist_of_stream u))" using 9 by simp
          have 11: "Suc j \<le> Max (lift (liset visible (llist_of_stream u)))" using Max_ge 1 10 by this
          show "False" using 6 11 by auto
        qed
        have 9: "j \<notin> liset visible (llist_of_stream u)" using 8 by auto
        show "u !! j \<notin> visible" using 9 by auto
      qed
      show "llist_of_stream (smap int (p ## trace u p)) ?! i = llist_of_stream (smap int (p ## trace u p)) ?!
        Max (lift (liset visible (llist_of_stream u)))" using 4 by (metis lnth_list_of_stream snth_smap)
    qed

    lemma execute_fin_visible:
      assumes "path u q" "path v q" "u \<preceq>\<^sub>F\<^sub>I w" "v \<preceq>\<^sub>F\<^sub>I w"
      assumes "project visible u = project visible v"
      shows "int (target u q) = int (target v q)"
    proof -
      obtain w' where 1: "u \<preceq>\<^sub>F w'" "v \<preceq>\<^sub>F w'" using subsume_fin assms(3, 4) by this
      obtain u' v' where 2: "u @ u' =\<^sub>F w'" "v @ v' =\<^sub>F w'" using 1 by blast
      have "u @ u' =\<^sub>F w'" using 2(1) by this
      also have "\<dots> =\<^sub>F v @ v'" using 2(2) by blast
      finally have 3: "u @ u' =\<^sub>F v @ v'" by this
      obtain s\<^sub>1 s\<^sub>2 s\<^sub>3 where 4: "u =\<^sub>F s\<^sub>1 @ s\<^sub>2" "v =\<^sub>F s\<^sub>1 @ s\<^sub>3" "Ind (set s\<^sub>2) (set s\<^sub>3)"
        using levi_lemma 3 by this
      have 5: "project visible (s\<^sub>1 @ s\<^sub>2) = project visible (s\<^sub>1 @ s\<^sub>3)"
        using eq_fin_lproject_visible assms(5) 4(1, 2) by auto
      have 6: "project visible s\<^sub>2 = project visible s\<^sub>3" using 5 by simp
      have 7: "set (project visible s\<^sub>2) = set (project visible s\<^sub>3)" using 6 by simp
      have 8: "set s\<^sub>2 \<inter> visible = set s\<^sub>3 \<inter> visible" using 7 by auto
      have 9: "set s\<^sub>2 \<subseteq> invisible \<or> set s\<^sub>3 \<subseteq> invisible" using independence_invisible 4(3) by auto
      have 10: "set s\<^sub>2 \<subseteq> invisible" "set s\<^sub>3 \<subseteq> invisible" using 8 9 by auto
      have 11: "path s\<^sub>2 (target s\<^sub>1 q)" using eq_fin_word 4(1) assms(1) by auto
      have 12: "path s\<^sub>3 (target s\<^sub>1 q)" using eq_fin_word 4(2) assms(2) by auto
      have "int (fold ex u q) = int (fold ex (s\<^sub>1 @ s\<^sub>2) q)" using eq_fin_execute assms(1) 4(1) by simp
      also have "\<dots> = int (fold ex s\<^sub>1 q)" using execute_fin_word_invisible 11 10(1) by simp
      also have "\<dots> = int (fold ex (s\<^sub>1 @ s\<^sub>3) q)" using execute_fin_word_invisible 12 10(2) by simp
      also have "\<dots> = int (fold ex v q)" using eq_fin_execute assms(2) 4(2) by simp
      finally show ?thesis by this
    qed
    lemma execute_inf_visible:
      assumes "run u q" "run v q" "u \<preceq>\<^sub>I w" "v \<preceq>\<^sub>I w"
      assumes "lproject visible (llist_of_stream u) = lproject visible (llist_of_stream v)"
      shows "snth (smap int (q ## trace u q)) \<approx> snth (smap int (q ## trace v q))"
    proof -
      have 1: "lnth (llist_of_stream (smap int (q ## trace u q))) \<approx>
        lnth (llist_of_stream (smap int (q ## trace v q)))"
      proof
        show "linfinite (llist_of_stream (smap int (q ## trace u q)))" by simp
        show "linfinite (llist_of_stream (smap int (q ## trace v q)))" by simp
        show "stutter_selection (lift (liset visible (llist_of_stream u))) (llist_of_stream (smap int (q ## trace u q)))"
          using stutter_selection_lproject_visible assms(1) by this
        show "stutter_selection (lift (liset visible (llist_of_stream v))) (llist_of_stream (smap int (q ## trace v q)))"
          using stutter_selection_lproject_visible assms(2) by this
        show "lselect (lift (liset visible (llist_of_stream u))) (llist_of_stream (smap int (q ## trace u q))) =
          lselect (lift (liset visible (llist_of_stream v))) (llist_of_stream (smap int (q ## trace v q)))"
        proof
          have "llength (lselect (lift (liset visible (llist_of_stream u)))
            (llist_of_stream (smap int (q ## trace u q)))) = eSuc (llength (lproject visible (llist_of_stream u)))"
            by (simp add: lselect_llength)
          also have "\<dots> = eSuc (llength (lproject visible (llist_of_stream v)))"
            unfolding assms(5) by rule
          also have "\<dots> = llength (lselect (lift (liset visible (llist_of_stream v)))
            (llist_of_stream (smap int (q ## trace v q))))" by (simp add: lselect_llength)
          finally show "llength (lselect (lift (liset visible (llist_of_stream u)))
            (llist_of_stream (smap int (q ## trace u q)))) = llength (lselect (lift (liset visible (llist_of_stream v)))
            (llist_of_stream (smap int (q ## trace v q))))" by this
        next
          fix i
          assume 1:
            "enat i < llength (lselect (lift (liset visible (llist_of_stream u)))
              (llist_of_stream (smap int (q ## trace u q))))"
            "enat i < llength (lselect (lift (liset visible (llist_of_stream v)))
              (llist_of_stream (smap int (q ## trace v q))))"
          have 2:
            "enat i \<le> llength (lproject visible (llist_of_stream u))"
            "enat i \<le> llength (lproject visible (llist_of_stream v))"
            using 1 by (simp add: lselect_llength)+
          define k where "k \<equiv> nth_least (lift (liset visible (llist_of_stream u))) i"
          define l where "l \<equiv> nth_least (lift (liset visible (llist_of_stream v))) i"
          have "lselect (lift (liset visible (llist_of_stream u))) (llist_of_stream (smap int (q ## trace u q))) ?! i =
            int ((q ## trace u q) !! nth_least (lift (liset visible (llist_of_stream u))) i)"
            by (metis 1(1) lnth_list_of_stream lselect_lnth snth_smap)
          also have "\<dots> = int ((q ## trace u q) !! k)" unfolding k_def by rule
          also have "\<dots> = int ((q ## trace v q) !! l)"
          unfolding sscan_scons_snth
          proof (rule execute_fin_visible)
            show "path (stake k u) q" using assms(1) by (metis run_shift_elim stake_sdrop)
            show "path (stake l v) q" using assms(2) by (metis run_shift_elim stake_sdrop)
            show "stake k u \<preceq>\<^sub>F\<^sub>I w" "stake l v \<preceq>\<^sub>F\<^sub>I w" using assms(3, 4) by auto
            have "project visible (stake k u) =
              list_of (lproject visible (llist_of (stake k u)))" by simp
            also have "\<dots> = list_of (lproject visible (ltake (enat k) (llist_of_stream u)))"
              by (metis length_stake llength_llist_of llist_of_inf_llist_prefix lprefix_ltake prefix_fininf_prefix)
            also have "\<dots> = list_of (ltake (enat i) (lproject visible (llist_of_stream u)))"
              unfolding k_def lproject_ltake[OF 2(1)] by rule
            also have "\<dots> = list_of (ltake (enat i) (lproject visible (llist_of_stream v)))"
              unfolding assms(5) by rule
            also have "\<dots> = list_of (lproject visible (ltake (enat l) (llist_of_stream v)))"
              unfolding l_def lproject_ltake[OF 2(2)] by rule
            also have "\<dots> = project visible (stake l v)"
              by (metis length_stake lfilter_llist_of list_of_llist_of llength_llist_of
                llist_of_inf_llist_prefix lprefix_ltake prefix_fininf_prefix)
            finally show "project visible (stake k u) = project visible (stake l v)" by this
          qed
          also have "\<dots> = int ((q ## trace v q) !! nth_least (lift (liset visible (llist_of_stream v))) i)"
            unfolding l_def by simp
          also have "\<dots> = lselect (lift (liset visible (llist_of_stream v)))
            (llist_of_stream (smap int (q ## trace v q))) ?! i"
            using 1 by (metis lnth_list_of_stream lselect_lnth snth_smap)
          finally show "lselect (lift (liset visible (llist_of_stream u)))
            (llist_of_stream (smap int (q ## trace u q))) ?! i = lselect (lift (liset visible (llist_of_stream v)))
            (llist_of_stream (smap int (q ## trace v q))) ?! i" by this
        qed
      qed
      show ?thesis using 1 by simp
    qed

  end

end

subset_name: curated


TITLE: Why don't any of the gas giants have moons of Earth's mass (or greater) that orbit them? Is this generalizable to exoplanet gas giants?
QUESTION [15 upvotes]: Now, we know that the composition of the outer planets tend to contain a much higher ratio of ice over rock. [1] So the lack of Earth-like moons around the outer planets that this could be an artifact of the fact that in our solar system, all the gas giants are beyond the "ice line".
But could other factors be involved too? If Jupiter was at the distance of the Earth (probably by migrating in), then is it unlikely for it to have a moon of Earth's mass or greater?
[1] This is probably because the amount of rocky material falls off with distance from the Sun, but this is not true for icy material because icy material will volatilize if it's too close to the Sun.

REPLY [0 votes]: I think it is possible if you look at Ganymede it is bigger than Mercury but however if you know about other planetary systems there are gas giants much bigger than Jupiter. It is very possible for a gas giant to have a moon similar in size of earth however not in terms of mass. We can speculate that if the gas giant is a brown dwarf than it may be possible because there may be two stars forming in the so and so star system (as an example) so the so the brown dwarf have a lot of matter around it and it can accrete to form similar size to that of earth not in mass terms because there is heavy molten iron & nickel inside the earth's core which makes it more massive and the densest planet in the solar system. I think even higher density per cubic meter than the sun.


TITLE: Increments of discrete i.i.d. random variables
QUESTION [1 upvotes]: We are given a sequence of discrete i.i.d. random variables $X_0, X_1, \ldots$. Let $Y_i = X_{i+1} - X_i$. Are the $Y_i$ independent? I was trying to show
\begin{equation}
P(Y_{1} = k_1, \ldots, Y_{n} = k_n) \,=\, P(Y_{1} = k_1) \cdot \ldots \cdot P(Y_{n} = k_n)
\end{equation}
but failed to do it even for $Y_0$ and $Y_1$. What happens if $X_i$ are uncorrelated instead of independent?

REPLY [2 votes]: Let's consider the following example. Let $X_i=1$ and $X_i=2$ with probabilities $\frac14$ and $\frac34$, respectively; for all $i$.
Compute first
$$P(Y_{i}=0\ \cap \ Y_{i-1}=0)=P(X_{i+1}-X_i=0\ \cap \ X_i-X_{i-1}=0)$$
then compute
$$P(Y_{i}=0)=P(Y_{i-1}=0)=P(X_{i+1}-X_i=0).$$
So,
$$P(Y_{i}=0\ \cap \ Y_{i-1}=0)=P(X_{i+1}-X_i=0\ \cap \ X_i-X_{i-1}=0)=$$
$$=P(X_{i+1}-1=0\ \cap \ 1-X_{i-1}=0\mid X_i=1)\frac14+$$
$$+P(X_{i+1}-2=0\ \cap \ 2-X_{i-1}=0\mid X_i=2)\frac34=$$
$$=P(X_{i+1}-1=0)P(1-X_{i-1}=0)\frac14+P(X_{i+1}-2=0)P(2-X_{i-1}=0)\frac34=$$
$$=\frac1{64}+\frac{27}{64}=\frac{28}{64}$$
and
$$P(X_{i+1}-X_i=0)=\frac1{16}+\frac9{16}=\frac58$$
that is
$$P(Y_{i}=0)P(Y_{i-1}=0)=\frac{25}{64}.$$
Finally, since
$$P(Y_{i}=0\ \cap \ Y_{i-1}=0)\not =P(Y_{i}=0)P(Y_{i-1}=0)$$
we can tell that the $Y_i$s are not independent in general.


TITLE: $\varepsilon$-$\delta$ proof of limit (Spivak)
QUESTION [0 upvotes]: Could you please help me with this proof?
$$
f(x)=x^4 + \frac1x
$$
Prove using $\varepsilon$-$\delta$ that
$$
\lim_{x \to 1} f(x)=2
$$
This problem is from Spivak's book Chapter 5 problem $3-iii.$

REPLY [1 votes]: Others have posted solutions that provide excellent ways forward.  Here, we develop a "brute force" approach.
To that end, we first restrict $0<\delta<1/2$ so that for $|x-1|< \delta$, $\frac12<x<\frac32$.
Next, we see that for $|x-1|<1/2$
$$\begin{align}
\left|x^4+\frac1x-2\right|&=\left|\frac{x^5-2x+1}{x}\right|\\\\
&=\left|\frac{x^4+x^3+x^2+x-1}{x}\right|\,|x-1|\\\\
&\le\left(\frac{(3/2)^4+(3/2)^3+(3/2)^2+(3/2)+1}{1/2}\right)\,|x-1|\\\\
&=\frac{211}{8}|x-1|\tag 1
\end{align}$$
Now, note that given any number $\epsilon>0$, we can make the right-hand side of $(1)$ less than $\epsilon$ simply by ensuring that $|x-1|<\frac{\epsilon}{211/8}$.
Finally, choosing $\delta=\min \left(\frac12,\frac{8}{211}\epsilon\right)$, we have that given any $\epsilon >0$
$$\begin{align}
\left|x^4+\frac1x-2\right|&=\left|\frac{x^5-2x+1}{x}\right|<\epsilon
\end{align}$$
whenever $|x-1|<\delta$.


TITLE: State of the art for integral models of PEL type Shimura varieties with deep level structure
QUESTION [7 upvotes]: The theory of PEL type Shimura varieties is nowadays well developed, but it is not easy to be updated with the latest results. Here I am particularly interested in integrals models. Let me describe what I understand.
Let $B$ be a (semi)simple algebra over $\mathbb Q$, of finite dimension. We suppose that $B$ is endowed with a positive involution $\ast$. Let $\mathcal O_B$ be an order of $B$, preserved by $\ast$. Let $(V,\Psi)$ be a finitely generated symplectic left $(B, \ast)$-module. Let $h \colon \mathbb C \to End_{B_{\mathbb R}}(V_{\mathbb R})$ be an $\mathbb R$-algebras homomorphism that gives an Hode strucure of type $(1,0),(0,1)$ on $V_{\mathbb R}$. We can now define a Shimura datum $(G,X)$ in the usual way. We obtain in particular a family of complex varieties $S_K$ parametrized by compact open subgroup $K \subseteq G(\mathbb A_f)$. We will assume that $K$ is 'small enough', in particular these varieties are moduli spaces of abelian varieties with additional (PEL) structure. It turns out that there is a number field $E$, called the reflex field, such that $S_K$ admits a canonical model defined over $E$.
In arithmetic it is very interesting to consider integral model of $S_K$. We fix a rational prime $p$. We assume that there is a lattice $\Lambda \subseteq V_{\mathbb Q_p}$ that is self-dual for $\Psi$ and we fix a compact open, small enough, subgroup $K^p \subseteq G(\mathbb A_f^p)$. Assuming that $B$ splits over an unramified extension of $\mathbb Q_p$, we have that $G(\mathbb Q_p)$ admits an hyperspecial subgroup, that we denote $K_{0,p}$. We assume that $B$ is of type A or C (another question is what can be done in the case D). It is well known that $S_{K^pK_{0,p}}$ admits a canonical integral model over $\mathcal O_E$, that is smooth over $\mathcal O_E \otimes Z_p$ and solves a very reasonable moduli problem. This goes back to Kottwitz.
Question 1 What can be done without the unramifiedness assumption? Of course in this case we do not have an hyperspcial subroup of $G(\mathbb Q_p)$, so we need a level strucure also at $p$. Rapoport and Zink have defined some integral models that satisfy a moduli problem, but it seems that their models are not even flat over the base.
Let me go back to the unramified case. For different reasons, it is interesting to consider level structures at $p$ (for example of type $\Gamma_1(Np^m)$ or $\Gamma_1(N) \cap \Gamma_0(p^m)$ in the case of modular curves). Now there is no hope for a smooth model, but of course one wants a good integral models. I am in particular interested in Iwahoric (or, more generally, parahoric) level structure. In the Siegel case, for example, we have good integral models.
Question 2 Under which assumptions we have good (flat and with a moduli interpretation) model of Shimura varieties with Iwahoric level structure at $p$? We have the models of Rapoport and Zink, but I do not if they are flat in general. Some cases are studied by Görtz (http://arxiv.org/abs/math/9912064 and http://arxiv.org/abs/math/0011202), but it seems that the general case is open (here I am always assuming that $G$ is quasi-split).
In general, I am interested in various condition 'at $p$' one have to put in order to obtain good integral models of PEL type Shimura varieties.
Thank you!

REPLY [7 votes]: Here are some remarks:
Rapoport's Guide paper which you mention in your comment certainly is a good starting point. There is also a survey paper by Pappas, Rapoport and Smithling with many more recent results; it focusses on the "local model side", but the understanding of the local model more or less is enough to understand the Shimura variety side.
Generally speaking, when the group splits over an unramified extension of $\mathbb Q_p$, the original Rapoport-Zink model is flat (types $A$ and $C$). (Re your comment: The general case can be reduced to the case $B=F$ by a Morita equivalence argument.)
If the group does not split over an unramified extension, the original (now called: naive) local model is typically not flat. Pappas and Rapoport have studied this case in a series of papers. (Of course one can pass to the flat closure in order to obtain a flat model; then the question becomes giving a moduli description of the flat closure, and maybe describe its geometry.)
For type $D$ less is known, but see the papers of Smithling for some results.
For level structures deeper than Iwahori, much less is known in general: In special cases (such as the case considered by Harris and Taylor, or, of course, for modular curves) one can obtain a nice model with a good geometric description. Haines and Rapoport have a paper on the $\Gamma_1(p)$ case. Sometimes it is also enough to work with some "abstractly defined" models (e.g. Drinfeld level structures and flat closure as in Mantovan, On the cohomology of certain PEL type Shimura varieties, Duke Math. J. 129 (2005), no. 3, 573--610).


text:
\chapter{Representation Theory} \label{reptheory}

In this chapter we give a review of the necessary elements of
representation theory that are needed to read this paper, and lay out
the terminology and notation we shall use.  An excellent introduction
to the subject is \cite{james}.  For readers already acquainted with
representation theory, the first chapter of \cite{sagan} has a good
concise review.  \cite{dummit} is a very complete reference for any
unfamiliar concepts from group theory.

\section{Group representations} \label{groupreps}

Representation theory is, in essence, the idea of expressing abstract
algebra in terms of linear algebra.  Operations in a group are
transformed into operations in a vector space.

Let $G$ be a finite group.

\begin{definition}
  A \term{$G$-module} or \term{representation} of $G$ is a
  finite-dimensional complex vector space $V$ on which $G$ acts
  linearly.  That is, for any $g,h \in G$, $\vec{v},\vec{w} \in V$,
  and $\alpha, \beta \in \C$, we have:
  \begin{enumerate}
    \item $g\vec{v}$ is some element of $V$;
    \item If $e$ is the identity of $G$, then $e \vec{v} = \vec{v}$;
    \item $g(h\vec{v}) = (gh)\vec{v}$ (1, 2, and 3 together define an
    action of $G$ on $V$);
    \item $g(\alpha \vec{v} + \beta \vec{w}) = \alpha(g\vec{v}) +
    \beta(g \vec{w})$ (the action respects the linear structure of $V$).
  \end{enumerate}
\end{definition}

What we have, then, is that each $g \in G$ becomes a linear
transformation of $V$, and these transformations compose in the same
way that elements of $G$ multiply.  Since elements of $G$ have
inverses, so do these transformations.  So we can also think of this
correspondence as a homomorphism $\phi$ from $G$ to $GL(V)$, the set
of invertible linear transformations of $V$.  (Many authors use the
word ``representation'' to refer to this homomorphism instead of the
corresponding module.)

Once a basis for $V$ is fixed, each $\phi(g)$ can be represented as an
$n \times n$ matrix, where $n = \dim V$.  By taking the traces of
these matrices, we obtain the \term{character} $\chi$ corresponding to
$\phi$, defined by $\chi(g) = \tr \phi(g)$.  Since similar matrices
have the same trace (that is, $\tr ABA^{-1} = \tr B$), we see that the
character is independent of the basis chosen for $V$.  In fact, two
representations have the same character if and only if they are
isomorphic.  Also, $\chi(ghg^{-1}) = \tr[\phi(g)\phi(h)\phi(g)^{-1}] =
\tr \phi(h) = \chi(h)$, so that $\chi$ takes the same value on
conjugate elements of $G$.  A function $f : G \to \C$ with this
property is called a \term{class function}, since it can be considered
a function on the set of conjugacy classes of $G$.

We now consider how modules decompose.

\begin{definition}
  Let $V$ be a $G$-module.  A subspace $U \subset V$ is a
  \term{submodule} of $V$ if for each $g \in G$, $\vec{u} \in U$, we
  have $g\vec{u} \in U$ (that is, $U$ is closed under the action of
  $G$).  We say $V$ is \term{irreducible} if it has no submodules
  other than the trivial one $\{\vec{0}\}$ and itself.
\end{definition}

Irreducible modules are the most fundamental modules, as is shown by
the following central theorem.

\begin{theorem}[Maschke's Theorem]
  If $V$ is a nontrivial $G$-module, then we can write
  \begin{equation*}
    V = W_1 \oplus \dots \oplus W_k
  \end{equation*}
  where $W_1, \dots, W_k$ are irreducible $G$-modules.
\end{theorem}

In other words, every $G$-module can be decomposed into irreducible
modules.  See \cite{sagan} for a proof.

Using characters, we can say more about this decomposition.

\begin{definition}
  Let $\chi$ and $\psi$ be characters associated to representations of
  $G$.  Define the \term{inner product} $\langle \chi, \phi \rangle$
  by
  \begin{equation}
    \langle \chi, \psi \rangle = \frac{1}{\abs{G}} \sum_{g \in G}
    \chi(g) \overline{\psi(g)}.
  \end{equation}
\end{definition}

\begin{theorem} \label{character-inner}
  Let $V$ be a representation of $G$, with associated character
  $\chi$, which decomposes into irreducible submodules as
  \begin{equation*}
    V = m_1 W_1 \oplus m_2 W_2 \oplus \dots \oplus m_k W_k
  \end{equation*}
  where $m_i W_i$ denotes the direct sum of $m_i$ copies of $W_i$, and
  the $W_i$ are pairwise nonisomorphic.  If $\chi_i$ is the character
  associated with $W_i$, then
  \begin{equation}
    \langle \chi, \chi_i \rangle = m_i.
  \end{equation}
\end{theorem}

It also can be shown that irreducible characters are orthonormal with
respect to this inner product.  Using this fact, it is possible to
show that the set of irreducible characters forms a basis for the
space of all class functions on $G$.  As the dimension of this space
is equal to the number of conjugacy classes of $G$, we have the
following theorem:

\begin{theorem} \label{rep-class}
  The number of irreducible representations of $G$ is equal to the
  number of conjugacy classes of $G$.
\end{theorem}

Now, when decomposing a representation into irreducible submodules, it
may happen that some of these submodules are isomorphic to each other.
In this case, the decomposition is not unique; in fact, there are
infinitely many ways to write such a decomposition.  To remedy this
defect, we introduce the notion of an \term{isotypic} submodule, which
is simply the direct sum of one isomorphism class of irreducible
submodules of $V$.  In other words, given one irreducible submodule,
we collect together all the irreducible submodules isomorphic to it
into one larger subspace.  When this is done, the decomposition is in
fact unique.

\begin{theorem}
  If $V$ is a nontrivial $G$-module, then there is a decomposition
  \begin{equation*}
    V = W_1 \oplus \dots \oplus W_k
  \end{equation*}
  where $W_1, \dots, W_k$ are isotypic $G$-modules.  Furthermore, this
  decomposition is unique up to ordering.
\end{theorem}

\section{Examples} \label{repexamples}

Now let us see some examples of representations.

\begin{example}[The permutation representation]
  Suppose $G$ acts on a finite set $S$ with $n$ elements.  Let $\C S$
  be the set of all formal linear combinations $\sum_{i=1}^n a_i s_i$,
  where $a_i \in \C$, $s_i \in S$.  With componentwise addition and
  scalar multiplication, $\C S$ becomes a vector space.  Then we can
  make $\C S$ into a $G$-module by defining
  \begin{equation*}
    g \sum_{i=1}^n a_i s_i = \sum_{i=1}^n a_i (g s_i).
  \end{equation*}
  This is called the \term{permutation representation} of $G$
  corresponding to its action on $S$.
\end{example}

\begin{example}[The regular representation]
  If, in the previous example, we consider $G$ acting on itself by
  left multiplication, we obtain the \term{regular representation} $\C
  G$.

  Now an element of $G$ becomes a linear transformation on $\C G$.
  Then each element of $\C G$ is just a linear combination of linear
  transformations, which is again a linear transformation.  Hence each
  element of $\C G$ is itself a linear transformation of $\C G$, as
  follows:
  \begin{equation*}
    \left( \sum_i a_i g_i \right) \left(\sum_j b_j h_j \right) =
    \sum_i \sum_j a_i b_j g_i h_j.
  \end{equation*}
  It's easy to show that this puts a multiplicative structure on $\C
  G$, and for this reason $\C G$ is also called the \term{group
  algebra} or \term{group ring} of $G$.
\end{example}

The same extension works for any $G$-module $V$.  Since each element
of $G$ is a linear transformation of $V$, so is any element of $\C G$,
since a linear combination of linear transformations is again a linear
transformation:
\begin{equation*}
  \left( \sum_i a_i g_i \right) \vec{v} = \sum_i a_i (g_i \vec{v}).
\end{equation*}
For this reason, many authors prefer to think of $V$ as actually being
acted on by $\C G$ (since this action also respects the ring structure
of $\C G$), and call it instead a $\C G$-module.

The regular representation $\C G$ has the important property that it
contains \emph{every} irreducible representation.  In fact, if $\C G$
is written as a direct sum of irreducible submodules, then each
irreducible representation $W$ appears $\dim W$ times.  This yields
the identity
\begin{equation} \label{dimsum}
 \abs{G} = \dim \C G = \sum (\dim W)^2
\end{equation}
where the sum is taken over all non-isomorphic irreducible
representations $W$.

The regular representation can also be viewed as the set of all
functions $f : G \to \C$, with pointwise addition and scalar
multiplication, and the group action $(gf)(a) = f(g^{-1}a)$ for $g, a
\in G$.  This can be a useful formulation for signal processing, where
we may think of an element of $\C G$ as a signal on $\abs{G}$ points.

\section{Tensor products of representations} \label{tensor}

The tensor product allows us to construct representations of direct
products of groups.  We describe it in terms of matrices, but as we
saw in Section \ref{groupreps}, we could also describe it in terms of
$G$-modules; the two formulations are completely equivalent.  This
material comes directly from \cite{sagan} and is included here mainly
for later reference.

\begin{definition}
  Let $A = (a_{ij})$ and $B$ be matrices.  Their \term{tensor product}
  is the block matrix
  \begin{equation}
    A \tensor B = (a_{ij}B) =
    \begin{pmatrix}
      a_{11}B & a_{12}B & \cdots \\
      a_{21}B & a_{22}B & \cdots \\
      \vdots & \vdots & \ddots
    \end{pmatrix}.
  \end{equation}
\end{definition}

Now let $G$ and $H$ be groups, with representations $\rho : G \to
GL(\C^n)$ and $\phi : H \to GL(\C^m)$ respectively.  Then their tensor
product $\rho \tensor \phi : G \times H \to \C^{nm}$, where we define
$(\rho \tensor \phi)(g,h) = \rho(g) \tensor \phi(h)$, is a
representation of $G \times H$.  It can be shown \cite{sagan} that if
$\rho$ and $\phi$ are irreducible, then so is $\rho \tensor \phi$.
Thus the representations of a direct product of two groups are
completely determined by the representations of the factors.

\section{Induced and restricted representations} \label{induce-restrict}

It is natural to ask how the subgroup structure of a group influences
its representations.  In fact, if we have $H \subgroup G$, we can
construct representations of $G$ from those of $H$, and vice versa.
We again use the matrix formulation of a representation.  This
material also comes from \cite{sagan}.

\begin{definition}
  Suppose $H \subgroup G$, and $\rho : H \to GL(\C^n)$ is a
  representation of $H$.  Let $t_1, \dots, t_k$ be a set of
  representatives for the cosets of $H$ in $G$ (where
  $k=\abs{G}/\abs{H}$).  Then the \term{induced representation} $\rho
  \uparrow_H^G : G \to GL(\C^{nk})$ maps each $g \in G$ to the block
  matrix
  \begin{equation}
    \rho \uparrow_H^G (g) =
    \begin{pmatrix}
      \rho(t_1^{-1} g t_1) & \rho(t_1^{-1} g t_2) & \cdots &
      \rho(t_1^{-1} g t_k) \\

      \rho(t_2^{-1} g t_1) & \rho(t_2^{-1} g t_2) & \cdots &
      \rho(t_2^{-1} g t_k) \\

      \vdots & \vdots & \ddots & \vdots \\

      \rho(t_k^{-1} g t_1) & \rho(t_k^{-1} g t_2) & \cdots &
      \rho(t_k^{-1} g t_k) \\

    \end{pmatrix}
  \end{equation}
  where $\rho(x)=0$ for $x \notin H$.
\end{definition}

It is shown in \cite{sagan} that this actually yields a representation
of $G$, and that any two choices of coset representatives yield
isomorphic representations, so that the induced representation is
well-defined.

The other direction is much simpler: given a representation $\rho$ for
$G$, we can produce the \term{restricted representation} $\rho
\downarrow^G_H$ of $H$ simply by taking the restriction of the map
$\rho$ to $H$.  It is obvious that this remains a representation.

We should note that the induced or restricted representations of an
irreducible representation are \emph{not} necessarily themselves
irreducible.  See \cite{clifford} for more details on when this is
true.

\section{Representation theory and the Fourier transform} \label{fourier}

Consider the case where $G = Z_n$ is the cyclic group of order $n$.
Then $\C G$ consists of $n$-dimensional complex vectors, and the
action of $G$ cyclically permutes the components.  Its irreducible
submodules are all one-dimensional (this always happens for abelian
groups \cite{dummit}), so they will be spaces of vectors which are
only scaled when their components are cyclically permuted. One such
submodule is that in which all components are equal.  Others are given
by vectors whose components vary in some sense periodically.  In fact,
each irreducible submodule is spanned by a vector of the form
\begin{equation} \label{fourier-basis}
  v_k = (1, e^{2 \pi i k / n}, e^{4 \pi i k / n}, \dots, e^{2(n-1)\pi
  i k / n})
\end{equation}
Also, since these submodules are non-isomorphic, they are in fact the
isotypic submodules of $\C G$.

So by decomposing a vector into components lying in these subspaces,
we break it into parts that look like complex exponentials.  If we
think of vectors in $\C G$ as functions $f : G \to \C$ (where the $n$
elements of $G$ can be thought of as $n$ discrete points in time),
then this looks very much like a discrete Fourier transform.  In fact,
expressing a vector in the basis $\{v_k\}_{k=1}^n$ yields the
coefficients of the classical discrete Fourier transform on $n$
points.

If we consider the group algebra as functions on the $n$ elements of
$Z_n$, then isotypic submodules will consist of functions whose values
change only by a (complex) scalar when their domains are cycled.

This notion extends to arbitrary groups $G$ (\cite{clausen},
\cite{maslen:cooley-tukey}).  Although for nonabelian groups the
isotypics will not all be $1$-dimensional, projections onto isotypic
subspaces of $\C G$ (or another $G$-module) can still yield important
information about the original vector.  To give just one example, the
case $G = S_n$ has been exploited to analyze ranked data
\cite{diaconis:rank}, such as survey results and voter preferences, in
much the same way as the case $G = Z_n$ is used to analyze time-series
data.  One particularly interesting application uses these techniques
to analyze approval voting, detecting coalitions in judicial and
legislative bodies \cite{dave:thesis}.

The problem then becomes: how should we compute isotypic projections?
Obviously, since projection onto a subspace is a linear
transformation, it has a matrix representation, so we could just
compute the projection directly.  However, the cost of doing this is
that of multiplying an $n \times n$ matrix by a vector, which in
general requires $O(n^2)$ operations, since there is no reason why
this matrix should be particularly ``nice.''

A better approach comes from an algorithm described in \cite{summer}
and \cite{orrison:thesis}.  If we can find diagonalizable linear
operators whose eigenspaces correspond well with the isotypic
submodules we seek, then we can compute isotypic projections via
eigenspace projections.  The next chapter describes how we go about
this search.

config: arxiv


text:
\section{Framework and some results from Part~1}\label{main-one}

\subsection*{The spherically symmetric Einstein-Maxwell-scalar field system with a cosmological constant}

Consider a spherically symmetric spacetime with metric
$$g=-\Omega^2(u,v)\,dudv+r^2(u,v)\,\sigma_{\mathbb{S}^2},$$
where $\sigma_{\mathbb{S}^2}$ is the round metric on the 2-sphere.
The Einstein-Maxwell-scalar field system with a cosmological constant $\Lambda$ and total electric charge $4\pi e$ reduces to the following system of equations:
the wave equation for $r$,
\begin{equation}\label{wave_r}
\partial_u\partial_vr=\frac{\Omega^2}{2}\frac{1}{r^2}\left(\vlinha\right),
\end{equation}
the wave equation for $\phi$,
\begin{equation}\label{wave_phi}
\partial_u\partial_v\phi=-\,\frac{\partial_ur\,\partial_v\phi+\partial_vr\,\partial_u\phi}{r},
\end{equation}
the Raychaudhuri equation in the $u$ direction,
\begin{equation}\label{r_uu}
\partial_u\left(\frac{\partial_ur}{\Omega^2}\right)=-r\frac{(\partial_u\phi)^2}{\Omega^2},
\end{equation}
the Raychaudhuri equation in the $v$ direction,
\begin{equation}\label{r_vv}
\partial_v\left(\frac{\partial_vr}{\Omega^2}\right)=-r\frac{(\partial_v\phi)^2}{\Omega^2},
\end{equation}
and the wave equation for $\ln\Omega$,
 \begin{equation}\label{wave_Omega}
\partial_v\partial_u\ln\Omega=-\partial_u\phi\,\partial_v\phi-\,\frac{\Omega^2e^2}{2r^4}+\frac{\Omega^2}{4r^2}+\frac{\partial_ur\,\partial_vr}{r^2}.
\end{equation}

\subsection*{The first order system}

Given $r$, $\phi$ and $\Omega$, solutions of the Einstein equations,
let
\begin{equation}\label{nu_0}
\nu:=\partial_u r
\end{equation}
\begin{equation}\label{lambda_0}
\lambda:=\partial_v r,
\end{equation}
\begin{equation}\label{bar_rafaeli}
\omega:=\frac{e^2}{2r}+\frac{r}{2}-\frac{\Lambda}{6}r^3+\frac{2r}{\Omega^2}\nu\lambda,
\end{equation}
\begin{equation}\label{mu_0}
\mu:=\truemu,
\end{equation}
\begin{equation}\label{theta}
\theta:=r\partial_v\phi,
\end{equation}
\begin{equation}\label{zeta}
\zeta:=r\partial_u\phi
\end{equation}
and
\begin{equation}\label{kappa_0}
 \kappa:=\frac{\lambda}{1-\mu}.
\end{equation}
Notice that we may rewrite~\eqref{bar_rafaeli} as
\begin{equation}\label{omega_sq}
\Omega^2=-\,\frac{4\nu\lambda}{1-\mu}=-4\nu\kappa.
\end{equation}
The Einstein equations imply the first order system for $(r,\nu,\lambda,\varpi,\theta,\zeta,\kappa)$
\begin{eqnarray}
 \partial_ur&=&\nu\label{r_u},\\
 \partial_vr&=&\lambda\label{r_v},\\
 \partial_u\lambda&=&\nu\kappa\partial_r(1-\mu)\label{lambda_u},\\
 \partial_v\nu&=&\nu\kappa\partial_r(1-\mu),\label{nu_v}\\
 \partial_u\omega&=&\frac 12(1-\mu)\left(\frac\zeta\nu\right)^2\nu,\label{omega_u}\\
 \partial_v\omega&=&\frac 12\frac{\theta^2}{\kappa},\label{omega_v}\\
 \partial_u\theta&=&-\,\frac{\zeta\lambda}{r},\label{theta_u}\\
 \partial_v\zeta&=&-\,\frac{\theta\nu}{r},\label{zeta_v}\\
 \partial_u\kappa&=&\kappa\nu\frac 1r\left(\frac{\zeta}{\nu}\right)^2,\label{kappa_u}
\end{eqnarray}
with the restriction
\begin{equation}\label{kappa_at_u}
\lambda=\kappa(1-\mu).
\end{equation}
Under appropriate regularity conditions for the initial data, the system of first order PDE~\eqref{r_u}$-$\eqref{kappa_at_u} also implies the Einstein equations \eqref{wave_r}$-$\eqref{wave_Omega}.

\subsection*{Initial data}
In Part~1 we study well posedness of the first order system for general initial data. In this paper
we take the initial data on the outgoing null direction $v$ to be the data on the event horizon of a subextremal Reissner-Nordstr\"{o}m solution
with mass $M$. The initial data on the ingoing null direction $u$ is free.
More precisely, we choose
\begin{equation}\label{iu}
\left\{
\begin{array}{lclcl}
 r(u,0)&=&r_0(u)&=&r_+-u,\\
 \nu(u,0)&=&\nu_0(u)&=&-1,\\
 \zeta(u,0)&=&\zeta_0(u),&&
\end{array}
\right.\qquad{\rm for}\ u\in[0,U],
\end{equation}
\begin{equation}\label{iv}
\left\{
\begin{array}{lclcl}
 \lambda(0,v)&=&\lambda_0(v)&=&0,\\
 \omega(0,v)&=&\omega_0(v)&=&M,\\
 \theta(0,v)&=&\theta_0(v)&=&0,\\
 \kappa(0,v)&=&\kappa_0(v)&=&1,
\end{array}
\right.\qquad{\rm for}\ v\in[0,\infty[.
\end{equation}
Here $r_+>0$ is the radius of the event horizon. We assume $\zeta_0$ is continuous and $\zeta_0(0)=0$.

\subsection*{Well posedness of the first order system}

Theorem 4.4 of Part~1, for the initial data above, reads:

\begin{Thm}\label{maximal} The characteristic initial value problem\/~\eqref{r_u}$-$\eqref{kappa_at_u}, with initial
conditions\/~\eqref{iu} and\/~\eqref{iv}, where $\zeta_0$ is continuous and $\zeta_0(0)=0$,
has a unique solution defined on a maximal past set $\mysigma$ containing a neighborhood of $[0,\myumax]\times\{0\}\cup\{0\}\times[0,\infty[$.\end{Thm}

\begin{Rmk}
Notice that the initial data\/~\eqref{iu} and\/~\eqref{iv} satisfies the regularity condition $\rm(h4)$ in\/ {\rm Part~1} (that is, $\nu_0$, $\lambda_0$ and $\kappa_0$ are $C^1$). Therefore the solution of the characteristic initial value problem\/~\eqref{r_u}$-$\eqref{kappa_at_u} corresponds to a classical solution of the Einstein equations \eqref{wave_r}$-$\eqref{wave_Omega}.
\end{Rmk}

\subsection*{Breakdown criterion}

Theorem 5.4 of Part~1, for the initial data above, reads:

\begin{Thm}\label{bdown}
Suppose that $(r,\nu,\lambda,\omega,\theta,\zeta,\kappa)$ is the maximal solution of the characteristic initial value problem\/~\eqref{r_u}$-$\eqref{kappa_at_u}, with initial
conditions\/~\eqref{iu} and\/~\eqref{iv}.
If $(\myU,V')$ is a point on the boundary of $\mysigma$ with $0<\myU<\myumax$ and $V'>0$, then
for all sequences $(u_n,v_n)$ in $\mysigma$ converging to $(\myU,V')$, we have
$$
r(u_n,v_n)\to 0\quad {\rm and}\quad \omega(u_n,v_n)\to\infty.
$$
\end{Thm}

\subsection*{Reissner-Nordstr\"om solution}

For comparison purposes, we notice that the Reissner-Nordstr\"om solution (with a cosmological constant), obtained from the initial data $\zeta_0(u)=0$, corresponds to
\begin{align}
& \lambda = 1 - \mu, \label{primeira}\\
& \nu = - \, \frac{1 - \mu}{(1 - \mu)(\,\cdot\,,0)}, \label{segunda}\\
& \varpi = \varpi_0, \\
& \kappa = 1, \\
& \zeta = \theta = 0.\label{ultima}
\end{align}


TITLE: Calculate the determinant of $A$
QUESTION [0 upvotes]: I f
$$A_{(n+1)\times(n+1)}= \begin{pmatrix}x_{1}^{n}& x_{1}^{n-1} &\ldots& x_{1}& 1 \\
x_{2}^{n}& x_{2}^{n-1} &\ldots& x_{2}& 1\\
\vdots & \vdots & &\vdots &\vdots \\
x_{n}^{n}& x_{n}^{n-1} &\ldots& x_{n}& 1 \\
1&1&\ldots&1&1\end{pmatrix}$$
be a matrix, i like to calculate the $det (A)$. I think that this matrix is rather than like vandrmonde matrix, what is your idea?

REPLY [0 votes]: $\det(A)$ will be a degree ${n+1}\choose 2$ polynomial in $x_1,\dots,x_n$.  (Why?)
Now observe that for $i\ne j$, if $x_i=x_j$ then $\det(A)=0$ by properties of the determinant.  Therefore, $(x_i-x_j)$ is a factor of that polynomial for each $i\ne j$.
Furthermore, if $x_i=1$ for any $i$ then $\det(A)=0$.  So $(x_i-1)$ is a factor of $\det(A)$ for each $i$.
Putting all this together, we see that $\prod_{i=1}^n(x_i-1)\prod_{j<i}(x_i-x_j)$ is a factor of $\det(A)$.  But what is the degree of that polynomial?  And what does that tell us?


TITLE: What is the value of $0 \choose 0$?
QUESTION [4 upvotes]: It can be 0 according to $0 \choose n$ and 1 according to $n \choose 0$.

REPLY [3 votes]: Since $\binom n k$ is the number of $k$-element subsets of an $n$-element set, you're asking about the number of empty subsets of the empty set.  There's exactly one, so $\binom00=1$.