text:
\begin{document}

\begin{abstract}
Crosscap slide is a homeomorphism of a nonorientable surface of genus at least 2, which was introduced under the name  Y-homeomorphism by Lickorish as an example of an element of the mapping class group which cannot be expressed as a product of Dehn twists. We prove that the subgroup of the mapping class group of  a closed nonorientable surface $N$ generated by all crosscap slides is equal to the level 2 subgroup consisting of those mapping classes which act trivially on  $H_1(N;\Z_2)$. We also prove that this subgroup is generated by involutions.
\end{abstract}

\maketitle

\section{Introduction}
It is well known that the mapping class group $\M(S)$ of a closed orientable surface $S$ is generated by Dehn twists. This result was originally proved by Dehn \cite{Dehn} and rediscovered  by Lickorish \cite{Lick0}. On a closed nonorientable surface $N$, however, there are elements of the mapping class group $\M(N)$ which cannot be expressed as a product of Dehn twists. The first example of such element is the crosscap slide, also called Y-homeomorphism, introduced by Lickorish \cite{Lick1}. He proved \cite{Lick1,Lick2} that the twist subgroup $\T(N)$, generated by Dehn twists about all two-sided simple closed curves, has index 2 in $\M(N)$, and that $\M(N)$ is generated by Dehn twists and one crosscap slide. Later, Chillingworth \cite{Chill} found finite generating sets for $\M(N)$ and $\T(N)$. Korkmaz \cite{KorkHom,Kork} and Stukow \cite{Stu2,Stu3} extended Chillingworth's results to surfaces with punctures and boundary and also computed the abelianizations of $\M(N)$ and $\T(N)$.

In this paper we consider the subgroup $\Y(N)$ of $\M(N)$ generated by all crosscap slides.
Our main result is Theorem \ref{main}, which asserts that for a closed nonorientable surface $N$ of genus $g\ge 2$, $\Y(N)$ is equal to the level 2 subgroup $\Gamma_2(N)$ of $\M(N)$ consisting of those mapping classes which act trivially on $H_1(N;\Z_2)$. In particular $\Y(N)$ is a subgroup of finite index. We also prove that $\Y(N)$ is generated by involutions (Theorem \ref{invol}).

It is an interesting problem to find a finite generating set for $\Y(N)$ and also compute its abelianization. For an orientable surface $S$, the abelianization of the level 2 subgroup of $\M(S)$  was computed by Sato \cite{Sato}.

The paper is organised as follows. After Preliminaries, we prove in Section \ref{s3} that certain elements of $\M(N)$ belong to $\Y(N)$ and that the last group is generated by involutions. In Section \ref{s4} we study the level $m$ mapping class groups $\Gamma_m(S)$ of an orientable surface $S$. We use known results about generators of Torelli groups and the Bass-Milnor-Serre's solution to the congruence subgroup problem for the symplectic group, to obtain convenient generating sets of $\Gamma_m(S)$. In Section \ref{s5} we use lemmas proved in previous sections, as well as some results of McCarthy-Pinkall \cite{McCP} and
Korkmaz \cite{KorkHom}, to prove our main result, which identifies the group $\Y(N)$ with the level 2 mapping class group $\Gamma_2(N)$.

\medskip

\noindent{\bf Acknowledgment.} I was informed by Professor Susumu Hirose that he found a shorter proof of my Theorem \ref{main} using Nowik's result \cite[Theorem 3.6]{Now}. I thank him for the discussion and for the reference \cite{Now}.

\section{Preliminaries}
Let $F$ be a connected compact surface, possibly with
boundary. Define $\Dif(F)$ to be the group of all, orientation
preserving if $F$ is orientable, homeomorphisms $h\colon F\to F$
equal to the identity on the boundary $\bdr{F}$. The {\it mapping class
group} $\M(F)$ is the group of isotopy classes in $\Dif(F)$. By
abuse of notation we will use the same symbol to denote a
homeomorphism and its isotopy class. If $g$ and $h$ are two
homeomorphisms, then the composition $gh$ means that $h$ is applied
first.
A surface of genus $g$ with $n$ boundary components will be denoted by $S_{g,n}$ if it is orientable, or by $N_{g,n}$ if it is nonorientable. The genus of a nonorientable surface is the number of projective planes in the connected sum decomposition.

\subsection{Simple closed curves and Dehn twists.}
By a {\it simple closed curve} in $F$ we mean an embedding
$\gamma\colon S^1\to F\backslash\bdr{F}$. Note that $\gamma$ has an orientation; the
curve with the opposite orientation but same image will be denoted by
$\gamma^{-1}$.
By abuse of notation, we will often identify a simple closed curve with its
oriented image and also with its isotopy class.
According to whether a regular neighborhood of $\gamma$ is an annulus or a M\"obius strip, we call $\gamma$ respectively {\it two-} or {\it one-sided}.
We say that $\gamma$ is {\it nonseparating} if $F\backslash\gamma$
is connected and {\it separating} otherwise. If $\gamma=\bdr{M}$ for some subsurface $M\subset F$ then we call $\gamma$ {\it bounding}. If $n\le 1$ then every separating curve is bounding.

Given a two-sided simple closed curve $\gamma$, $T_\gamma$ denotes a Dehn
twist about $\gamma$. On a  nonorientable surface it is
impossible to distinguish between right and left twists, so the
direction of a twist $T_\gamma$ has to be specified for each curve
$\gamma$. Equivalently we may choose an orientation of a regular
neighborhood of $\gamma$. Then $T_\gamma$ denotes the right Dehn twist with
respect to the chosen orientation. Unless we specify which of the
two twists we mean, $T_\gamma$ denotes any of the
two possible twists. Recall that $T_\gamma$ does not depend on the orientation of $\gamma$.

{\it Bounding pair} is a pair $(\gamma,\gamma')$ of disjoint
simple closed curves, such that $\gamma\cup\gamma'=\bdr{S}$ for an orientable subsurface $S\subset F$. If $T_{\gamma}$, $T_{\gamma'}$ are right Dehn twists with respect to some orientation of $S$, then $T_{\gamma}T^{-1}_{\gamma'}$ is called {\it bounding pair map}. Our definition of a bounding pair differs slightly from the usual definition, in which the curves $\gamma$ and $\gamma'$ are required to be nonseparating.

\begin{figure}
\input{fig1}
\caption{\label{Y} Crosscap slide.}
\end{figure}

\subsection{Crosscap slides.}
Let $N=N_{g,n}$ be a nonorientable surface of genus $g\ge 2$.
Suppose that $\mu$ and $\alpha$ are two simple closed curves in $N$,
such that $\mu$ is one-sided, $\alpha$ is two-sided and they
intersect in one point. Let $K\subset N$ be a regular neighborhood of
$\mu\cup\alpha$,
which is homeomorphic to the Klein bottle with a
hole, and let $M\subset K$ be a regular neighborhood of $\mu$, which
is a M\"obius strip. We denote by $Y_{\mu,\alpha}$ the {\it crosscap slide}, or {\it
Y-homeomorphism} of $K$ which may be
described as the result of pushing $M$ once along $\alpha$ keeping the
boundary of $K$ fixed. Figure \ref{Y} illustrates the effect of
$Y_{\mu,\alpha}$ on an arc connecting two points in the boundary of
$K$. Here, and also in other figures of this paper, the shaded discs
represent crosscaps; this means that their interiors should be
removed, and then antipodal points in each resulting boundary
component should be identified. The homeomorphism $Y_{\mu,\alpha}$
pushes the left crosscap through the right one, along $\alpha$.
Observe that $Y_{\mu,\alpha}$ reverses the orientation of $\mu$.
We extend $Y_{\mu,\alpha}$ by the identity
outside $K$ to a homoeomorphism of $N$, which we denote by the same
symbol.  Up to isotopy, $Y_{\mu,\alpha}$ does not depend on the
choice of the regular neighbourhood $K$. It also does not depend on the orientation of $\mu$
but does depend on the orientation of $\alpha$. The following
properties of crosscap slides are easy to verify.
\begin{equation}\label{y^-1}
Y_{\mu,\alpha^{-1}}=Y^{-1}_{\mu,\alpha},
\end{equation}
\begin{equation}\label{y2}
Y_{\mu,\alpha}^2=T_\gamma,
\end{equation}
where $T_\gamma$ is the Dehn twist about $\gamma=\bdr{K}$, right with respect
to the standard orientation of the plane of Figure \ref{Y},
\begin{equation}\label{hyh}
hY_{\mu,\alpha}h^{-1}=Y_{h(\mu),h(\alpha)},
\end{equation}
for all $h\in\Dif(N)$.
\begin{figure}
\input{fig2}
\caption{\label{U}Crosscap transposition.}
\end{figure}
The crosscap slide is an example of an element of $\M(N)$ which is not a product of Dehn twists. It was introduced by Lickorish, who proved that $\M(N_g)$ is generated by Dehn twists and one crosscap slide for $g\ge 2$ \cite{Lick1,Lick2}.

Let $T_\alpha$ denote the Dehn twist about $\alpha$ in the direction indicated by the arrows in Figure \ref{U}. Then
\[U_{\mu,\alpha}=T_\alpha Y_{\mu,\alpha}\]
interchanges two crosscaps. We call this homeomorphism {\it crosscap
transposition}.

\subsection{Blowup homomorphism and crosscap pushing map.}\label{blowup}
Let $N=N_{g,n}$ and fix $x_0\in N\backslash\bdr{N}$.
Define $\M(N,x_0)$ to be the group of isotopy classes in $\Dif(N,x_0)$, the group of all homeomorphisms $h\colon N\to N$ equal to the identity on $\bdr{N}$ and such that $h(x_0)=x_0$.

Let $U=\{z\in\mathbb{C}\,|\,|z|\le 1\}$ and fix an embedding
$e\colon U\to N\backslash\bdr{N}$ such that $e(0)=x_0$.
The surface $N_{g+1,n}$ may be obtained by removing from $N$ the interior of $e(U)$ and then identifying $e(z)$ with $e(-z)$ for $z\in S^1=\bdr{U}$.
Let $\gamma=e(S^1)$ and let $\mu$ be the image of $\gamma$ in $N_{g+1,n}$.
Note that $\mu$ is a one-sided simple closed curve.

We define a {\it blowup homomorphism}
\[\varphi\colon\M(N_{g,n},x_0)\to\M(N_{g+1,n})\] as follows.
Represent $h\in\M(N,x_0)$ by a homeomorphism $h\colon N\to N$ such that (a) $h$ is equal to the identity on $e(U)$ or (b) $h(x)=e(\overline{e^{-1}(x)})$ for $x\in e(U)$. Such $h$ commutes with the identification leading to $N_{g+1,n}$ and thus induces an element $\varphi(h)\in\M(N_{g+1,n})$. To see that $\varphi$ is well defined consider two homeomorphisms $h_1,h_2\in\Dif(N,x_0)$ which satisfy (a) or (b) and are isotopic by an isotopy fixing $x_0$. Let $N'=N\backslash int(e(U))$. By \cite[Theorem 3.6]{Stu4} the kernel of the homomorphism $i_\ast\colon\M(N')\to\M(N,x_0)$ induced by the inclusion of $N'$ in $N$ is generated by $T_\gamma$. It follows that the restriction of $h_1h^{-1}_2$ to $N'$ is isotopic by an isotopy fixed on $\gamma$ to some power of $T_\gamma$. Since a Dehn twist about a curve bounding a M\"obius strip is trivial, $h_1$ and $h_2$ induce the same element of $\M(N_{g+1,n})$.

Forgetting the distinguished point $x_0$ induces a homomorphism
\[\M(N_{g,n},x_0)\to\M(N_{g,n}),\] which fits into the Birman exact sequence (see \cite{Kork})
\[\pi_1(N_{g,n},x_0)\stackrel{j}{\to}\M(N_{g,n},x_0)\to\M(N_{g,n})\to 1.\]
The homomorphism $j$ is called {\it point pushing map}.
If $\alpha$ is a loop in $N_{g,n}$ based at $x_0$ and $[\alpha]\in\pi_1(N_{g,n},x_0)$ is  its homotopy class, then $j([\alpha])$ may be described as the effect of pushing $x_0$ once along $\alpha$.

We define a {\it crosscap pushing map} to be the composition
\[\psi=\varphi\circ j\colon\pi_1(N_{g,n},x_0)\to\M(N_{g+1,n}).\]
The following two lemmas follow from the description of the point pushing map for nonorientable surfaces \cite[Lemma 2.2 and Lemma 2.3]{Kork} and the definition of a crosscap slide.

\begin{lemma}\label{push2}
Suppose that $\alpha$ is a two-sided simple loop in $N_{g,n}$ based at $x_0$ and let $M$ be a regular neighbourhood of $\alpha$ containing $e(U)$. Let $M'$ be the image in $N_{g+1,n}$ of $M\backslash int(e(U))$.
Then \[\psi([\alpha])=T_\beta T_\delta^{-1},\]
where $\beta$ and $\delta$ are boundary curves of $M'$ and the twists are right with respect to some orientation of $M'\backslash\mu$.
\end{lemma}

\begin{lemma}\label{push1}
Suppose that $\alpha$ is a one-sided simple  loop in $N_{g,n}$ based at $x_0$.
Let $\alpha'$ be a simple loop in the homotopy class $[\alpha]$ which
intersects $\gamma$ in two antipodal points.
Then \[\psi([\alpha])=Y_{\mu,\tilde{\alpha}},\]
where $\tilde{\alpha}$ is the image in $N_{g+1,n}$ of $\alpha'\backslash int(e(U))$.
\end{lemma}

\begin{cor}\label{pushinY}
For $n\le 1$ every element of $\psi(\pi_1(N_{g,n},x_0))$ is a product of crosscap slides.
\end{cor}
\begin{proof}
For $n\le 1$,
$\pi_1(N_{g,n},x_0)$ is generated by homotopy classes of one-sided simple loops.
Since $\psi$ is a homomorphism, it follows by Lemma \ref{push1} that $\psi(\pi_1(N_{g,n},x_0))$ is generated by crosscap slides.
\end{proof}

\section{The group generated by crosscap slides.}\label{s3}
In this section we assume that $N=N_g$ is a closed nonorientable surface of genus $g\ge 2$. We denote by $\Y(N)$  the subgroup of $\M(N)$ generated by all crosscap slides.
Since by (\ref{hyh}) a conjugate of a crosscap slide is also a crosscap slide, $\Y(N)$ is a normal subgroup of $\M(N)$.

\begin{lemma}\label{square}
For every nonseparating two-sided simple closed curve $\alpha$ in $N$, $T^2_\alpha$ belongs to $\Y(N)$.
\end{lemma}

\begin{proof} Let $\mu$ be a one-sided curve intersecting $\alpha$ in one point.
Since $Y_{\mu,\alpha}$ preserves the curve $\alpha$ and reverses orientation of its neighbourhood, we have $Y_{\mu,\alpha}T_\alpha Y_{\mu,\alpha}^{-1}=T^{-1}_\alpha,$
and by (\ref{y^-1}, \ref{hyh})
\[T^2_\alpha=T_\alpha Y_{\mu,\alpha}T^{-1}_\alpha Y^{-1}_{\mu,\alpha}
=Y_{T_\alpha(\mu),\alpha}Y_{\mu,\alpha^{-1}}.\]
\end{proof}

\begin{figure}\label{lantern}
\input{fig3}
\caption{Curves of the lantern relation.}
\end{figure}

\begin{lemma}\label{separating}
For every separating simple closed curve $\gamma$ in $N$, $T_\gamma$ belongs to $\Y(N)$.
\end{lemma}

\begin{proof} Let $K$ be a nonorientable subsurface of $N$ such that $\gamma=\bdr{K}$. We will argue by induction on the genus $\rho$ of $K$. If $\rho=1$ then $T_\gamma$ is trivial, and if $\rho=2$ then $T_\gamma$ is the square of a crosscap slide supported in $K$ by (\ref{y2}). Suppose that $\rho\ge 3$ and consider the
separating curves in Figure \ref{lantern}. Note that $\gamma, \gamma_1, \gamma_2, \gamma_3, $ bound a four-holed sphere and we have the well known lantern relation
\[T_\gamma T_{\gamma_1}T_{\gamma_2}T_{\gamma_3}=T_{\gamma_{12}}T_{\gamma_{13}}T_{\gamma_{23}},\]
where the twists are right with respect to the standard orientation of the plane of the figure.
Since each of the curves different from $\gamma$ bounds a nonorientable subsurface of genus less then $\rho$, the corresponding twist is in $\Y(N)$ by inductive hypothesis. It follows that $T_\gamma\in\Y(N)$.\end{proof}

\begin{figure}
\input{fig4}
\caption{\label{mui}The one-sided curves $\mu_i$.}
\end{figure}

\begin{figure}
\input{fig5}
\caption{\label{alphai}The two-sided curves $\alpha_i$.}
\end{figure}

\begin{figure}
\input{fig6}
\caption{\label{betaj}The pair $(\beta_j, \beta'_j)$ bounding an orientable subsurface of genus $j-1$.}
\end{figure}

Represent the surface $N=N_g$ ($g\ge 2$) as a 2-sphere with $g$ crosscaps (Figure \ref{mui}). Recall that it means that the interiors of the shaded disc should be removed and then antipodal points on each resulting boundary component should be identified. Assume that the sphere is embedded in $\R^3$ is such a way that it is invariant under the reflection about a plane which contains centers of
the shaded discs. The reflection commutes with the identification leading to $N$, so it induces a homeomorphism  $R\colon N\to N$ of order 2.

For $1\le i\le g-1$ let
\[Y_i=Y_{\mu_i,\alpha_i},\qquad U_i=U_{\mu_i,\alpha_i}=
T_{\alpha_i}Y_{\mu_i,\alpha_i}=Y_{\mu_i,\alpha_i}T^{-1}_{\alpha_i},\]
where $\mu_i$ is the one sided curve in Figure \ref{mui} and
$T_{\alpha_i}$ is the Dehn twist about $\alpha_i$ in Figure \ref{alphai} in the indicated direction.  For $1\le j\le\lfloor g/2\rfloor$ let $T_{\beta_j}$, $T_{\beta'_j}$ be Dehn twists about the curves in Figure \ref{betaj} in the indicated directions. Observe that $\beta_j$ and $\beta'_j$ bound an orientable subsurface of genus $j-1$ and $T_{\beta_j}$, $T_{\beta'_j}$ are right twists with respect to  appropriate orientation of this subsurface, hence $T_{\beta_j}T^{-1}_{\beta'_j}$ is a bounding pair map.

\begin{theorem}[Chillingworth \cite{Chill}]{\label{Ch}}
The group $\M(N_g)$ is generated by
\[\{T_{\alpha_i}, T_{\beta_j}, Y_{g-1}; 1\le i\le g-1, 1\le j\le\lfloor g/2\rfloor\}.\]
\end{theorem}

\begin{lemma}\label{RinY}
The involution $R$ belongs to $\Y(N)$.
\end{lemma}

\begin{proof} Let $F=RU_{g-1}U_{g-2}\cdots U_1T_{\alpha_1}T_{\alpha_2}\cdots T_{\alpha_{g-1}}$. It is straightforward it check that $F$ fixes each of the curves $\mu_i$, $\alpha_i$, $\beta_j$ and preserves orientation of regular neighbourhoods of the last two for $1\le i\le g-1$, $1\le j\le\lfloor g/2\rfloor$. It follows that $F$ commutes
with  $Y_i$, $T_{\alpha_i}$, $T_{\beta_j}$, and thus by Theorem \ref{Ch} it belongs to the center of $\M(N_g)$ which is trivial, according to \cite[Corollary 6.3]{Stu1}. Hence $F=1$ and
\begin{align*}
R&=U_{g-1}U_{g-2}\cdots U_1T_{\alpha_1}T_{\alpha_2}\cdots T_{\alpha_{g-1}}\\
&=U_{g-1}T_{\alpha_{g-1}}T_{\alpha_{g-1}}^{-1}U_{g-2}
T_{\alpha_{g-2}}T_{\alpha_{g-1}}T_{\alpha_{g-1}}^{-1}T_{\alpha_{g-2}}^{-1}\cdots U_1T_{\alpha_1}T_{\alpha_2}\cdots T_{\alpha_{g-1}}\\
&=Y_{g-1}T^{-1}_{\alpha_{g-1}}Y_{g-2}T_{\alpha_{g-1}}\cdots
(T_{\alpha_2}\cdots T_{\alpha_{g-1}})^{-1}Y_1(T_{\alpha_2}\cdots T_{\alpha_{g-1}})\in\Y(N).
\end{align*}
\end{proof}

Let $N_{g-1}$ be the surface obtained by replacing the leftmost crosscap in Figure \ref{mui} by a disc with center $x_0$. Taking that disc as $e(U)$, $N$ may be seen as being obtained from $N_{g-1}$ by the blowup construction described in Subsection \ref{blowup}. As a result we have the crosscap pushing map
\[\psi\colon\pi_1(N_{g-1},x_0)\to\M(N).\]
By Corollary \ref{pushinY}  $\psi(\pi_1(N_{g-1},x_0))\subset\Y(N)$ .

\begin{figure}
\input{fig9}
\caption{\label{ed} Curves from the proof of Lemma \ref{bpinY}.}
\end{figure}

\begin{lemma}\label{bpinY}
Every bounding pair map belongs to $\Y(N)$.
\end{lemma}

\begin{proof} Let $T_{\gamma}T^{-1}_{\gamma'}$ be a bounding pair map, where $\gamma\cup \gamma'$ is the boundary of an orientable subsurface  $S$ of genus $j-1$ and the twists $T_\gamma$, $T_{\gamma'}$ are right with respect to some orientation of $S$. If $\gamma$ and $\gamma'$ are separating, then we are done by Lemma \ref{separating}, therefore we are assuming that $\gamma$ and $\gamma'$ are nonseparating.

If $N\backslash S$ is nonorientable, then there is a homeomorphism $h\colon N\to N$ which maps $(\gamma, \gamma')$ to
$(\beta_j, \beta'_j)$ (Figure \ref{betaj}), so
$hT_{\gamma}T^{-1}_{\gamma'}h^{-1}=(T_{\beta_j}T^{-1}_{\beta'_j})^{\pm 1}$ and it suffices to prove that $T_{\beta_j}T^{-1}_{\beta'_j}\in\Y(N)$. We have $RT_{\beta_j}R=T_{\beta'_j}$ and
$T_{\beta_j}T^{-1}_{\beta'_j}=T_{\beta_j}RT^{-1}_{\beta_j}R$, and since $R$ is in $\Y(N)$ by Lemma \ref{RinY}, thus $T_{\beta_j}RT^{-1}_{\beta_j}\in\Y(N)$ and $T_{\beta_j}T^{-1}_{\beta'_j}\in\Y(N)$.

Suppose that $N\backslash S$ is orientable. This can only happen if $g$ is even, say $g=2r$, and $N\backslash\gamma$ and $N\backslash\gamma'$ are orientable. We proceed by induction on $j$. If $j=1$ then $S$ is an annulus and
$T_{\gamma}T^{-1}_{\gamma'}=1$. If $j=2$ then
$T_{\gamma}T^{-1}_{\gamma'}$ is conjugate in $\M(N)$ to $(T_{\beta_r}T^{-1}_{\phi})^{\pm 1}$, where $\beta_r$ is the curve in Figure \ref{betaj} and $\phi$ is the curve in Figure \ref{ed}. As in the previous case, it suffices to show that $T_\phi=fT_{\beta_r}f^{-1}$ for some $f\in\Y(N)$. It is easy to check that we may take $f=U_2^{-1}T_\varepsilon=Y_2^{-1}T_{\alpha_2}^{-1}T_\varepsilon$, where $\varepsilon$ is the curve in Figure \ref{ed}. To see that $T_{\alpha_2}^{-1}T_\varepsilon\in\Y(N)$ notice that $\varepsilon$ and $\alpha_2$ bound a M\"obius strip with two holes, and by Lemma \ref{push2}, $T_{\alpha_2}^{-1}T_\varepsilon$ is in the image of the crosscap pushing map $\psi$, which is a subgroup of $\Y(N)$.

If $j>2$ then let $\gamma''$ be a separating simple closed curve in $S$ such that
$\gamma\cup\gamma''=\bdr{S'}$, $\gamma'\cup\gamma''=\bdr{S''}$ for subsurfaces
$S'$, $S''$ of genera less than $j-1$. We have
$T_{\gamma}T^{-1}_{\gamma'}=(T_{\gamma}T^{-1}_{\gamma''})(T_{\gamma''}T^{-1}_{\gamma'})\in\Y(N)$
because the bounding pair maps on the right hand side are in $\Y(N)$ by the inductive hypothesis.
\end{proof}

\begin{figure}
\input{fig7}
\caption{\label{gd} Curves from the proof of Lemma \ref{y1}.}
\end{figure}

\begin{lemma}\label{y1}
Every crosscap slide is a product of crosscap slides conjugate in $\M(N)$ to $Y_1$.
\end{lemma}

\begin{proof} Let $Y=Y_{\mu,\alpha}$ be any crosscap slide and let $K$ and be a regular neighbourhood of $\alpha\cup\mu$, which is homeomorphic to the Klein bottle with a hole. Clearly there is a homeomorphism $h\colon K\to K_1$, where $K_1$ is a regular neighbourhood of $\alpha_1\cup\mu_1$, such that $h(\alpha)=\alpha_1$ and $h(\mu)=\mu_1$. If $N\backslash K$ is nonorientable or $g=2$, then $h$ may be extended to $h\colon N\to N$ and by (\ref{hyh}) we have
$hY_{\mu,\alpha}h^{-1}=Y_{\mu_1,\alpha_1}$, hence $Y$ is conjugate to $Y_1$ in $\M(N)$. Suppose that $g>2$ and $N\backslash K$ is orientable. This forces the genus of $N$ to be even, $g=2r\ge 4$. Now $Y_{\mu,\alpha}$ is conjugate in $\M(N)$ to
$Y_{\mu_1,\beta_r}$, where $\beta_r$ is the curve in Figure \ref{betaj} for $j=r$ ($N\backslash\beta_r$ is orientable).
Note that $Y_{\mu_1,\beta_r}$ is in the image of the crosscap pushing map
$\psi\colon\pi_1(N_{g-1},x_0)\to\M(N)$.
Consider the two-sided curves $\gamma$, $\delta$ in Figure \ref{gd}. Since
$\psi$ is a homomorphism, sliding $\mu_1$ along $\beta_r$ is the same, up to isotopy, as sliding $\mu_1$ along $\alpha_1$ first, then along $\gamma$, then along $\delta$. Thus
$Y_{\mu_1,\beta_r}=Y_{\mu_1,\delta}Y_{\mu_1,\gamma}Y_{\mu_1,\alpha_1}$, where each of the three crosscap slides on the right hand side is conjugate to $Y_1$ by the previous argument.  \end{proof}

\begin{theorem}\label{invol}
The group $\Y(N)$ is generated by involutions.
\end{theorem}
\begin{proof} Since $\Y(N)$ is a normal subgroup of $\M(N)$ and conjugate of an involution is also an involution, it suffices, by Lemma \ref{y1}, to show that $Y_1$ is a product of involutions in $\Y(N)$. The reflectional involution $R$ is in $\Y(N)$ by Lemma \ref{RinY}. Since $R$ maps $\mu_1$, $\alpha_1$ to
$\mu_1^{-1}$, $\alpha_1^{-1}$, we have
$RY_1R=Y_1^{-1}$, thus $RY_1$ is an involution in $\Y(N)$ and $Y_1$ is a product of two involutions $Y_1=R(RY_1)$.\end{proof}

\section{Level $m$  mapping class groups}\label{s4}

In this section we assume that $S=S_{g,n}$ is an orientable surface of genus $g\ge 2$ having $n\in\{0,1\}$ boundary components.

The action of $\M(S)$ on $H_1(S;\Z)$ preserves the algebraic intersection pairing, which is a nondegenerate alternating form, so we have a  representation of $\M(S)$ into the symplectic group, which is well known to be surjective and whose kernel $\calI(S)$ is known as the {\it Torelli group}. This is summarized by the exact sequence
\[1\longrightarrow\calI(S)\longrightarrow\M(S)\longrightarrow\Sp(2g,\Z)\longrightarrow 1.\]
Wy are going to use the following classical theorem proved by Powell \cite{Powell} building on Birman's result \cite{Bir}.
\begin{theorem}[Powell \cite{Powell}]\label{BP}
The Torelli group $\calI(S)$ is generated by Dehn twists about separating curves and bounding pair maps.
\end{theorem}
The result above was later improved by Johnson \cite{John1} who showed, that for $g\ge 3$, $\calI(S)$ is generated by finitely many bounding pair maps.

For $m\ge 2$, let $\Sp(2g,\Z)[m]$ denote the {\it level $m$ congruence subgroup} of $\Sp(2g,\Z)$, that is, the subgroup of matrices that are equal to the identity modulo $m$. There is an exact sequence
\[1\longrightarrow\Sp(2g,\Z)[m]\longrightarrow\Sp(2g,\Z)\longrightarrow\Sp(2g,\Z_m)\longrightarrow 1,\]
where $\Z_m=\Z/m\Z$.
The pull-back of $\Sp(2g,\Z)[m]$ to $\M(S)$ is known as the {\it level $m$ subgroup} of $\M(S)$ and is denoted by $\Gamma_m(S)$. The group $\Gamma_m(S)$ can also be described as the group of isotopy classes of homeomorphisms that act trivially on $H_1(S;\Z_m)$. It fits into an exact sequence
\begin{equation}\label{ses3}
1\longrightarrow\calI(S)\longrightarrow\Gamma_m(S)\longrightarrow\Sp(2g,\Z)[m]\longrightarrow 1.
\end{equation}

It is well known that for $m \ge 3$, $\Sp(2g,\Z)[m]$ and $\Gamma_m(S)$ are torsion free. The case $m=2$ is exceptional,
$\Gamma_2(S_{g,0})$ contains torsion elements, for example the hyperelliptic involution.

For $1\le i,j\le g$  let $C^g_{ij}(m)$ be the $g\times g$ matrix with $m$ at positions $(i,j)$ and $(j,i)$ and $0$ elsewhere. Denoting the $g\times g$ zero matrix by $O_g$ and the $g\times g$ identity matrix by $I_g$, let
\[A^g_{ij}(m)=\left(\begin{array}{cc}I_g&C^g_{i,j}(m)\\O_g&I_g\end{array}\right)
,\quad
B^g_{ij}(m)=\left(\begin{array}{cc}I_g&O_g\\C^g_{i,j}(m)&I_g\end{array}\right).\]
The following theorem forms part of Bass-Milnor-Serre's solution to the congruence subgroup problem for the symplectic group.
\begin{theorem}[Bass-Milnor-Serre {\cite[Theorem 12.4, Corollary 12.5]{BMS}}]\label{Bass}
For $g\ge 2$ the group $\Sp(2g,\Z)[m]$ is generated by
$\{A^g_{ij}(m), B^g_{ij}(m); 1\le i,j\le g\}.$
\end{theorem}

For $h_1, h_2\in H_1(S;\Z)$ let $i(h_1,h_2)$ denote the algebraic intersection number.
Let us fix a symplectic basis $\{a_1,\dots,a_g,b_1,\dots,b_g\}$ of $H_1(S;\Z)$, that is \[i(a_i,b_j)=\delta_{ij},\quad i(a_i,a_j)=0, \quad i(b_i,b_j)=0,\]
for $1\le i,j\le g$, where $\delta_{ij}$ is the Kronecker delta. We also fix a realisation of this basis by simple closed curves $\{\alpha_1,\dots,\alpha_g,\beta_1,\dots,\beta_g\}$, such that
$a_i=[\alpha_i]$, $b_i=[\beta_i]$ and
\[|\alpha_i\cap \beta_j|=\delta_{ij},\quad \alpha_i\cap \alpha_j=\emptyset, \quad \beta_i\cap \beta_j=\emptyset,\]
for $1\le i,j\le g$.
Recall that a homology class $h\in H_1(S;\Z)$ can be realised by a simple closed curve if and only if $h$ is primitive, which means that the greatest common deviser of the coefficients of $h$ in a symplectic basis equals 1.
For $f\in\M(S)$ we denote by $\overline{f}$ the   induced automorphism of $H_1(S;\Z)$ and, by abuse of notation, its matrix with respect to the basis  $\{a_1,\dots,a_g,b_1,\dots,b_g\}$. If $\gamma$ is a simple closed curve on $S$, then the right Dehn twist $T_\gamma$ acts on $H_1(S;\Z)$ by the transvection
\[\overline{T_\gamma}(h)=h+i(h,[\gamma])[\gamma].\]

\begin{lemma}\label{mtwists1}
Let $S=S_{g,n}$ for $g\ge 2$ and $n\in\{0,1\}$.
Every element of $\Sp(2g,\Z)[m]$ is induced by a product of
$m$-th powers of Dehn twists about nonseparating curves in $S$.
\end{lemma}

\begin{proof} By Theorem \ref{Bass} it suffices to show that
$A^g_{ij}(m)$ and $B^g_{ij}(m)$ are induced by products of $m$-th powers of Dehn twists about nonseparating curves in $S$ for $1\le i,j\le g$. We have
$\overline{T^{-m}_{\alpha_i}}=A^g_{ii}(m)$ and $\overline{T^m_{\beta_i}}=B^g_{ii}(m)$ for $1\le i\le g$. For $i\ne j$ let  $\gamma_{ij}$, $\delta_{ij}$ be simple closed curves such that $[\gamma_{ij}]=a_i+a_j$, $[\delta_{ij}]=b_i+b_j$. Then $\overline{T^{m}_{\alpha_i}T^{m}_{\alpha_j}T^{-m}_{\gamma_{ij}}}=A^g_{ij}(m)$, $\overline{T^{-m}_{\beta_i}T^{-m}_{\beta_j}T^{m}_{\delta_{ij}}}=B^g_{ij}(m)$.
\end{proof}

From the exactness of sequence (\ref{ses3}), Theorem \ref{BP} and Lemma \ref{mtwists1} we have the following.

\begin{cor}\label{gen1}
Let $S=S_{g,n}$ for $g\ge 2$ and $n\in\{0,1\}$.
The group $\Gamma_m(S)$ is generated by Dehn twists about separating curves, bounding pair maps and $m$-th powers of Dehn twists about nonseparating curves.
\end{cor}

For the rest of this section assume that $S=S_g$ is closed and $\Sigma=S_{g-1,2}$.
Consider an embedding $i\colon\Sigma\hookrightarrow S$ such that $S\backslash i(\Sigma)$ is an annulus with core $\beta_g$. Such embedding is called cupping in \cite{Put}. Since every homeomorphism of $i(\Sigma)$ equal to the identity on $i(\bdr{\Sigma})$ can be extended by the identity on $S\backslash i(\Sigma)$ to a homeomorphism of $S$, we have an induced homomorphism  $i_\ast\colon\M(\Sigma)\to\M(S)$. The image of $i_\ast$ is equal to the subgroup
$\Stab_{\M(S)}(\beta_g)$ consisting of the isotopy classes of homeomorphisms fixing the curve $\beta_g$ and preserving its orientation. Let $\delta_1$, $\delta_2$ be two simple closed curves in $\Sigma$ isotopic to the boundary components.  The kernel of $i_\ast$ is generated by the bounding pair map $T_{\delta_1}T^{-1}_{\delta_2}$. Summarising, we have an exact sequence
\[1\longrightarrow\lr{T_{\delta_1}T^{-1}_{\delta_2}}
\longrightarrow\M(\Sigma)\longrightarrow\Stab_{\M(S)}(\beta_g)\longrightarrow 1.\]
Following \cite{Put} we let
\[\calI(\Sigma)=i^{-1}_\ast(\calI(S)).\]
For a surface having $n>1$ boundary components various definitions of a Torelli group are possible. The group $\calI(\Sigma)$ defined above is the same as
$\calI(\Sigma,\{\{\delta_1,\delta_2\}\})$ in the notation of \cite{Put} and it agrees with the definition of the Torelli group of a surface with boundary given by Johnson \cite{John2}.
Note that $\calI(\Sigma)$ {\it is not} the kernel of the action of $\M(\Sigma)$ on $H_1(\Sigma;\Z)$. For example, $T_{\delta_i}$ for $i=1,2$ act trivially on the homology group, but they are not elements of $\calI(\Sigma)$. Nevertheless, $\calI(\Sigma)$ can also be defined intrinsically, without reference to $S$, by using relative homology, see \cite{John2,Put}.
Note that $\gamma$ is a bounding curve in $\Sigma$ if and only if $i(\gamma)$ is separating in $S$, and $(\gamma, \gamma')$ is a bounding pair in $\Sigma$ if and only if $(i(\gamma), i(\gamma'))$ is a bounding pair in $S$.

\begin{theorem}[Putman \cite{Put}]\label{P}
The group $\calI(\Sigma)$ is generated by Dehn twists about
bounding curves and bounding pair maps.
\end{theorem}

Let $\Stab_{\Sp(2g,\Z)}(b_g)$ be the subgroup of $\Sp(2g,\Z)$ consisting of the (matrices of) automorphisms of $H_1(S;\Z)$ which  fix the homology class $b_g=[\beta_g]$, and
\[\Stab_{\Sp(2g,\Z)[m]}(b_g)=\Sp(2g,\Z)[m]\cap\Stab_{\Sp(2g,\Z)}(b_g).\]
Observe that we have an isomorphism
\[\Stab_{\Sp(2g,\Z)}(b_g)/\Stab_{\Sp(2g,\Z)[m]}(b_g)\cong\Stab_{\Sp(2g,\Z_m)}(\overline{b_g}),\]
where $\overline{b_g}$ is the homology class in $H_1(S;\Z_m)$ of the curve $\beta_g$.

\begin{lemma}\label{mtwist2}
For $g\ge 3$ every element of $\Stab_{\Sp(2g,\Z)[m]}(b_g)$ is induced by a product of
$m$-th powers of Dehn twists about nonseparating curves in $S$ disjoint from $\beta_g$.
\end{lemma}

\begin{proof} Let $N$ be a regular neighbourhood of $\alpha_g\cup\beta_g$ and $S'=S\backslash N$. Note that $S'$ is a copy of $S_{g-1,1}$  and we have a symplectic splitting \[H_1(S;\Z)=H_1(N;\Z)\oplus H_1(S';\Z),\]
where $H_1(N;\Z)=\lr{a_g,b_g}$.
Let $A\in \Stab_{\Sp(2g,\Z)[m]}(b_g)$ and consider $h=Aa_g$. We have
\[i(h,b_g)=i(Aa_g,Ab_g)=i(a_g,b_g)=1,\]
thus
\[h=a_g+m(xb_g+h'),\] where $x\in\Z$, $h'\in H_1(S';\Z)$. Let $h''$ be a primitive element of $H_1(S';\Z)$ such that $h'=yh''$ for $y\in\Z$ (if $h'=0$, then $y=0$ and $h''$ is arbitrary) and let $\gamma$ be any nonseparating simple closed curve in $S'$ such that $h''=[\gamma]$.
Let $\delta$ be a simple closed curve disjoint from $\beta_g$ and such that
$[\delta]=[\gamma]-[\beta_g]$ (Figure \ref{bg}). We have
$\overline{T^{m(x+y)}_{\beta_g}T^{my}_\delta}(h)=a_g$. Since $\overline{T^{m(x+y)}_{\beta_g}T^{my}_\delta}A$ is equal to the identity on $\lr{a_g,b_g}$, thus it restricts to a symplectic automorphism of $H_1(S';\Z)$, and hence, by Lemma \ref{mtwists1}, it is induced by a product of $m$-th powers of Dehn twists about nonseparating curves in $S'$ (here we use the assumption $g\ge 3$). Since $T_{\beta_g}$ can be seen as a twist about a curve isotopic to $\beta_g$ and disjoint from $\beta_g$,  $A$ is induced by  a product of $m$-th powers of Dehn twists about nonseparating curves in $S$ disjoint from $\beta_g$.\end{proof}

\begin{figure}
\input{fig8}
\caption{\label{bg}Curves from the proof of Lemma \ref{mtwist2}.}
\end{figure}

We define level $m$ subgroup of $\M(\Sigma)$ as
\[\Gamma_m(\Sigma)=i^{-1}_\ast(\Gamma_m(S)).\]
Consider the map $\Gamma_m(\Sigma)\to\Stab_{\Sp(2g,\Z)[m]}(b_g)$ given by
$f\mapsto\overline{i_\ast(f)}$. By Lemma \ref{mtwist2} this map is surjective, because every simple closed curve in $S$ disjoint from $\beta_g$ is isotopic to a curve in $i(\Sigma)$. We have an exact sequence
\[1\longrightarrow\calI(\Sigma)\longrightarrow\Gamma_m(\Sigma)\longrightarrow
\Stab_{\Sp(2g,\Z)[m]}(b_g)\longrightarrow 1,\]
which together with Lemma \ref{mtwist2} and Theorem \ref{P} gives the following.

\begin{cor}\label{gen2}
Let $g\ge 3$ and $\Sigma=S_{g-1,2}$. The group $\Gamma_m(\Sigma)$ is generated by Dehn twists about bounding curves, bounding pair maps and $m$-th powers of Dehn twists about nonseparating curves.
\end{cor}

\begin{prop}\label{quot}
The quotient group $\M(\Sigma)/\Gamma_m(\Sigma)$ is isomorphic to the stabiliser
$\Stab_{\Sp(2g,\Z_m)}(\overline{b_g})$.
\end{prop}

\begin{proof} First we show that the map $\Stab_{\M(S)}(\beta_g)\to\Stab_{\Sp(2g,\Z)}(b_g)$ is surjective. Let $A\in\Stab_{\Sp(2g,\Z)}(b_g)$ and let $f\in\M(S)$ be such that $\overline{f}=A$. Since $[f(\beta_g)]=[\beta_g]$, there is $h\in\calI(S)$ such that $hf(\beta_g)=\beta_g$ (see Lemma 6.2 in \cite{Put}).
Now $hf\in\Stab_{\M(S)}(\beta_g)$ and $\overline{hf}=A$.
We have
\[\Stab_{\Sp(2g,\Z)}(b_g)\cong\frac{\Stab_{\M(S)}(\beta_g)}{\calI(S)\cap\Stab_{\M(S)}(\beta_g)}
\cong\frac{\M(\Sigma)}{\calI(\Sigma)},\]
where the last isomorphism is induced by $i_\ast\colon\M(\Sigma)\to\Stab_{\M(S)}(\beta_g)$.
We have a series of isomorphisms
\[\frac{\M(\Sigma)}{\Gamma_m(\Sigma)}\cong
\frac{\M(\Sigma)/\calI(\Sigma)}{\Gamma_m(\Sigma)/\calI(\Sigma)}\cong
\frac{\Stab_{\Sp(2g,\Z)}(b_g)}{\Stab_{\Sp(2g,\Z)[m]}(b_g)}\cong
\Stab_{\Sp(2g,\Z_m)}(\overline{b_g}).
\]
\end{proof}

\section{The action of $\M(N)$ on $H_1(N;\Z_2)$.}\label{s5}
In this section we assume that $N=N_g$ is a closed nonorientable surface of genus $g\ge 2$. Recall that $H_1(N;\Z)$ is generated by $\{c_1,\dots,c_g\}$, where
$c_i=[\mu_i]$ for $1\le i\le g$ are the homology classes of the one-sided curves $\mu_i$ (Figure \ref{mui}). As a $\Z$-module it has the following presentation
\begin{equation}\label{pres}
H_1(N;\Z)=\lr{c_1,\dots,c_g\,|\,2(c_1+\cdots+c_g)=0}.
\end{equation}
The $\Z_2$-homology classes $\overline{c_i}$ of the curves
$\mu_i$ form a basis of $H_1(N;\Z_2)$, which is a vector space over $\Z_2$ of dimension $g$. The $\Z_2$-valued intersection pairing is a symmetric bilinear  form $\lr{\,{,}\,}$ on $H_1(N;\Z_2)$ satisfying $\lr{\overline{c_i},\overline{c_j}}=\delta_{ij}$ for $1\le i,j\le g$.
The following three theorems were proved by McCarthy and Pinkall \cite{McCP}.

\begin{theorem}[{\cite[Theorem 1]{McCP}}]\label{MCP1}
Every automorphism of $H_1(N;\Z)$ which preserves the $\Z_2$-valued intersection pairing is induced by a homeomorphism of $N$.
\end{theorem}

\begin{theorem}[{\cite[Theorem 2]{McCP}}]\label{MCP2}
Every automorphism of $H_1(N;\Z_2)$ which preserves the $\Z_2$-valued intersection pairing is induced by a homeomorphism of $N$.
\end{theorem}

\begin{theorem}[{\cite[Theorem 3]{McCP}}]\label{MCP3}
Every automorphism of $H_1(N;\Z)$ inducing a trivial automorphism of  $H_1(N;\Z_2)$ is induced by a homeomorphism of $N$ which is a product of crosscap slides.
\end{theorem}

By Theorem \ref{MCP2}, the natural map \[\M(N)\longrightarrow\Iso(H_1(N;\Z_2))\]
is surjective, where $\Iso(H_1(N;\Z_2))$ is the group of automorphisms of
$H_1(N;\Z_2)$ which preserve $\lr{\,{,}\,}$.

Recall that a symmetric bilinear form $\Omega$ on a vector space $V$ over a field of characteristic 2 is called symplectic if it is nondegenerate  and $\Omega(v,v)=0$ for all $v\in V$. On a closed orientable surface $S_r$, the $\Z_2$-valued intersection pairing is a symplectic form on $H_1(S_r,\Z_2)$.
Let us fix a symplectic basis $\{\overline{a_1},\dots,\overline{a_r},\overline{b_1},\dots,\overline{b_r}\}$
of $H_1(S_r,\Z_2)$. We shell identify the group $\Sp(2r,\Z_2)$ with the group of symplectic automorphisms of $H_1(S_r,\Z_2)$. A proof of the following proposition can be found in \cite[Section 3]{KorkHom}.

\begin{prop}\label{order}
For $r\ge 1$, the group $\Iso(H_1(N_{2r+1},\Z_2))$ is isomorphic to the symplectic group $\Sp(2r,\Z_2)$, and its order is given by the formula
\[|\Iso(H_1(N_{2r+1},\Z_2))|=2^{r^2}\prod_{i=1}^r(2^{2i}-1),\]
the group $\Iso(H_1(N_{2r},\Z_2))$ is isomorphic to the stabiliser  $\Stab_{\Sp(2r,\Z_2)}(\overline{b_r})$, and its order is given by the formula
\[|\Iso(H_1(N_{2r},\Z_2))|=2^{r^2}\prod_{i=1}^{r-1}(2^{2i}-1).\]
\end{prop}

We define level 2 subgroup $\Gamma_2(N)$ of $\M(N)$ to be the group of isotopy classes of homeomorphisms which act trivially on $H_1(N;\Z_2)$. If fits into an exact sequence
\[1\longrightarrow\Gamma_2(N)\longrightarrow\M(N)\longrightarrow\Iso(H_1(N;\Z_2))
\longrightarrow 1.\]

The following theorem is an improvement of Theorem \ref{MCP3}. It is the main result of this paper.

\begin{theorem}\label{main} A mapping class $f\in\M(N)$ acts trivially on $H_1(N;\Z_2)$ if and only if $f$ is a product of crosscap slides.
\end{theorem}

In other words $\Gamma_2(N)=\Y(N)$.

\begin{proof} The crosscap slide $Y_1=Y_{\mu_1,\alpha_1}$ acts on $H_1(N;\Z)$ by
\[\overline{Y_1}(c_1)=-c_1,\quad \overline{Y_1}(c_2)=2c_1+c_2,\quad
\overline{Y_1}(c_i)=c_i\textrm{\ for\ }3\le i\le g.\]
It follows that $Y_1$  acts trivially on $H_1(N;\Z_2)$ and hence, by Lemma \ref{y1}, $\Y(N)\subseteq\Gamma_2(N)$. For the equality it suffices to prove $[\M(N)\colon\Y(N)]\le[\M(N)\colon\Gamma_2(N)]$. The index $[\M(N)\colon\Gamma_2(N)]$ is equal to the order of $\Iso(H_1(N;\Z_2))$, which is given in Proposition \ref{order}.

If $g=2$, then $\M(N)\cong\Z_2\oplus\Z_2$ , $\Gamma_2(N)=\Y(N)\cong\Z_2$ (see \cite{Lick1}).

If $g=3$, then $\M(N)\cong\mathrm{GL}(2,\Z)$ and it admits the presentation
\[\lr{a,b,y\,|\,aba=bab, y^2=1, yay=a^{-1}, yby=b^{-1}, (aba)^4=1},\]
where $a=T_{\alpha_1}$, $b=T_{\alpha_2}$, $y=Y_1$ (see \cite{BirChill}). By Lemma \ref{y1}, a presentation for the quotient group $\M(N)/\Y(N)$ may be obtained by adding the relation $y=1$ to the presentation of $\M(N)$. Thus
\[\M(N)/\Y(N)\cong\lr{a,b\,|\,a^2=b^2=(ab)^3=1}\cong \Sigma_3,\]
where $\Sigma_n$ is the symmetric group on $n$ letters. Since  $[\M(N)\colon\Gamma_2(N)]=6$ by Proposition \ref{order}, thus $\Y(N)=\Gamma_2(N)$.

If $g=4$, then we can use the presentation of $\M(N)$ given in \cite{Szep} to obtain the following presentation for $\M(N)/\Y(N)$.
\begin{align*}
&\M(N)/\Y(N)\cong
\lr{b\,|\,b^2=1}\times\\
&\lr{a_1,a_2,a_3\,|\,a_1^2=a_2^2=a_3^2=(a_1a_2)^3=(a_2a_3)^3=1, a_1a_3=a_3a_1},
\end{align*}
where $b=\widetilde{T_{\beta_2}}$, $a_i=\widetilde{T_{\alpha_i}}$ for $i=1,2,3$, where $\widetilde{f}$ is the coset of $f\in\M(N)$ in $\M(N)/\Y(N)$. It follows that
$\M(N)/\Y(N)\cong\Z_2\times\Sigma_4$, and since  $[\M(N)\colon\Gamma_2(N)]=48$ by Proposition \ref{order}, thus $\Y(N)=\Gamma_2(N)$.

Now we assume that $g=2r+1$ for $r\ge 2$. Let $\mu$ be a one-sided simple closed curve in $N$ such that $N\backslash\mu$ is orientable, and which is disjoint from the curves $\alpha_i$, $\beta_j$, $1\le i\le g-1$, $1\le j\le r$ in Figures \ref{alphai} and \ref{betaj}. Let $M$ be a regular neighbourhood of $\mu$, which is a M\"obius band, and $S=N\backslash M$.
Note that $S$ is a copy of $S_{r,1}$. Consider a homomorphism
$j\colon\M(S)\to\M(N)/\Y(N)$ defined as $j=p\circ i_\ast$, where $i_\ast\colon\M(S)\to\M(N)$ is induced by the inclusion $S\hookrightarrow N$ and $p\colon\M(N)\to\M(N)/\Y(N)$ is the canonical projection. By Theorem \ref{Ch}, $\M(N)$ is generated by $Y_{g-1}$ and Dehn twists about curves in $S$. It follows that $j$ is surjective and hence
\[[\M(N)\colon\Y(N)]=[\M(S)\colon\ker{j}].\]
By Corollary \ref{gen1}, $\Gamma_2(S)$ is generated by Dehn twists about separating curves, bounding pair maps and squares of Dehn twists about nonseparating curves. It follows by Lemmas \ref{square}, \ref{separating} and \ref{bpinY} that
$i_\ast(\Gamma_2(S))\subseteq\Y(N)$, hence $\Gamma_2(S)\subseteq\ker{j}$.
We have
\[[\M(S)\colon\ker{j}]\le[\M(S)\colon\Gamma_2(S)]=|\Sp(2r,\Z_2)|.\]
Since $[\M(N)\colon\Gamma_2(N)]=|\Sp(2r,\Z_2)|$ by Proposition \ref{order}, thus $\Y(N)=\Gamma_2(N)$.

Finally we assume that $g=2r$ for $r\ge 3$. Let $A$ be regular neighbourhood of the two-sided curve $\beta_r$ and $\Sigma=N\backslash A$. Note that $\Sigma$ is a copy of $S_{r-1,2}$. The proof is analogous to the case of odd genus. The homomorphism $j\colon\M(\Sigma)\to\M(N)/\Y(N)$ defined as $j=p\circ i_\ast$, where $i_\ast\colon\M(\Sigma)\to\M(N)$ is induced by the inclusion $\Sigma\hookrightarrow N$, is surjective by Theorem \ref{Ch}. By Corollary \ref{mtwist2} and Lemmas \ref{square}, \ref{separating} and \ref{bpinY} we have
$\Gamma_2(\Sigma)\subseteq\ker{j}$ and thus
\[[\M(N)\colon\Y(N)]=[\M(\Sigma)\colon\ker{j}]\le[\M(\Sigma)\colon\Gamma_2(\Sigma)]=
|\Stab_{\Sp(2r,\Z_2)}(\overline{b_r})|,\]
the last equality following from Proposition \ref{quot}. By Proposition \ref{order} we have
\[[\M(N)\colon\Gamma_2(N)]=|\Stab_{\Sp(2r,\Z_2)}(\overline{b_r})|,\] and hence $Y(N)=\Gamma_2(N)$.\end{proof}

\begin{rem}
Theorem \ref{main} provides a characterisation of the elements of $\Y(N)$ in terms of the action on homology. Such characterisation is  known also for the twist subgroup. Namely, a mapping class $f\in\M(N)$ is a product of Dehn twists about two-sided curves if and only if the determinant of the induced map
$f_\ast\colon H_1(N;\R)\to H_1(N;\R)$ equals $1$ (see \cite[Corollary 6.3]{Stu2}).
\end{rem}

The following corollary is a consequence of Theorems \ref{invol} and \ref{main}.

\begin{cor}
The group $\Gamma_2(N)$ is generated by involutions.
\end{cor}

Consider the quotient $R_g=H_1(N_g,\Z)/\lr{c}$, where $c=c_1+\cdots+c_g$ is the unique homology class of order 2. It is immediate from the presentation \ref{pres} that $R_g$ is the free $\Z$-module with basis given by the images of $c_1,\dots,c_{g-1}$ in $R_g$. Every automorphism of $H_1(N_g,\Z)$ preserves $c$, and thus induces an automorphism of $R_g$. It was shown in \cite[Section 2]{McCP}, that the group of automorphisms of $H_1(N_g,\Z)$ which act trivially on $H_1(N_g,\Z_2)$ is isomorphic to the full group of automorphisms of $R_g$ which act trivially on $R_g\otimes\Z_2$. Consequently, we have a surjection
\[\Gamma_2(N_g)\longrightarrow\mathrm{GL}(g-1,\Z)[2],\]
where $\mathrm{GL}(n,\Z)[2]$ is the level 2 congruence subgroup of $\mathrm{GL}(n,\Z)$. The following corollary is probably well know to algebraists.

\begin{cor}
The group $\mathrm{GL}(n,\Z)[2]$ is generated by involutions.
\end{cor}

config: arxiv


TITLE: How nuking the poles of Mars would create an atmosphere?
QUESTION [2 upvotes]: Elon Musk said one of the methods they are taking into consideration to create an atmosphere on Mars is to nuke its poles. How nuking the poles would create the atmosphere?

REPLY [2 votes]: Please refer here for a similar question.
The idea of nuking the poles of Mars came around when people started to seriously consider the idea of terraforming another planet. If Mars's poles were to be nuked, the Ice Caps, mainly made of carbon dioxide, would vaporize. This vapor of carbon dioxide would be the first step in this process as a small atmosphere would form from this initial step. However, a larger atmosphere is achieved when you consider the greenhouse effect. The carbon dioxide would trap heat from the sun, heating up the ice caps and causing almost the entire Ice Cap to disappear and become a larger atmosphere. With carbon dioxide to warm the planet, trees could then be planted to chemically alter the atmosphere with photosynthesis producing oxygen that we can breathe.
This idea appears to work in theory if there is enough energy in the thermonuclear bombs, however, our current energies of these bombs would require tens of thousand of them to be dropped to release a small amount of carbon dioxide. Therefore this plan may not be feasible.


text:
\section{\sc\bf Enumeration of linkage diagrams, loctets and linkage systems}
  \label{sec_enum_loctets}
  \index{class of diagrams ! - $\mathsf{C4}$}

 In this section we demonstrate some calculation examples of linkage diagrams, loctets and
 linkage systems. These calculations are based on findings of \S\ref{sec_loctets_diagr}.

\subsection{Calculation of linkage diagrams $\gamma^{\nabla}(8)$}
  \label{sec_calc_gamma_8}
  \index{loctet ! - $8$th linkage diagram}
  \index{linkage diagrams ! - calculation, $\gamma^{\nabla}(8)$}
   In this section, we consider only case $l < 8$. For case $D_l$, $l \geq 8$, see \S\ref{sec_D_lg8}, and for case
   $A_l$, $l \geq 8$, see \S\ref{sec_Al_lg8}.

 It seems a little easier to calculate the $8$th linkage diagram (we calculate it for every Carter diagram loctet) rather than to calculate any other linkage diagram of
 a loctet since $8$th linkage diagram contains $3$ zeroes among coordinates $\{ \alpha_1, \alpha_2, \alpha_3, \beta_1 \}$. We have
\begin{equation}
 \label{dual_linkage_1}
   \gamma^{\nabla}(8) =
 \left \{
  \begin{array}{ll}
     \hspace{-2mm}\{ a_1, a_2, a_3, 0,  b_2 \} & \text{ for } D_5(a_1),  \\
     \hspace{-2mm}\{ a_1, a_2, a_3, 0,  b_2, b_3\} & \text{ for } D_6(a_1), E_6(a_1), E_6(a_2),  \\
     \hspace{-2mm}\{ a_1, a_2, a_3, a_4, 0,  b_2 \} & \text{ for } D_6(a_2), \\
     \hspace{-2mm}\{ a_1, a_2, a_3, a_4, 0,  b_2, b_3\} & \text{ for } D_7(a_1), D_7(a_2), \\
     \hspace{-2mm}\{ a_1, a_2, a_3, 0,  b_2, b_3, b_4\} &  \text { for }  E_7(a_1)$,  $E_7(a_2)$, $E_7(a_3)$, $E_7(a_4),
  \end{array}
  \right . \\
\end{equation}
   where $a_i = 0,  a_j = 0, a_k = 1, b_1 = 0$ and
   $\{i, j, k \} = \{1, 2, 3 \}$  for type $L_{ij}$.
   The quadratic form $\mathscr{B}^{\vee}_{\Gamma}$ applied to the linkage label vector $\gamma^{\nabla}(8)$
 gives rise to a function $F$ of several variables $b_2, b_3, \dots$, where three dots mean $a_i$, $b_i$ for $i \geq 4$
 (if the $\alpha$-set (resp. $\beta$-set) contains $> 3$ labels), i.e.,
 \begin{equation*}
   F(b_2, b_3, \dots) := \mathscr{B}^{\vee}_{\Gamma}(\gamma^{\nabla}(8)).
 \end{equation*}
 Let $q(b_2, b_3, \dots)$ be the quadratic part of $F$ (containing only quadratic terms),
 $l(b_2, b_3, \dots)$ the linear part of $F$, and $f$ the free term:
 \begin{equation*}
        F(b_2, b_3, \dots) = q(b_2, b_3, \dots) + l(b_2, b_3, \dots) + f.
 \end{equation*}
 It is easily to see that $q(b_2, b_3, \dots)$ is the same for loctet types $L_{12}$, $L_{13}$, $L_{23}$.
 Consider the case, where the $\alpha$-set (resp. $\beta$-set) contains $\leq 3$ labels.
 The quadratic form $q(b_2, b_3)$ is determined by the principal submatrix of $B^{-1}_{\Gamma}$
 associated with coordinates $\beta_2$, $\beta_3$:
\begin{equation}
  \label{q_part}
  q(b_2, b_3) = d_{{\beta_2}{\beta_2}}b_2^2 + 2d_{{\beta_2}{\beta_3}}b_2{b_3} + d_{{\beta_3}{\beta_3}}b_3^2,
\end{equation}
 where $d_{ij}$ is the $\{i, j\}th$ element of the inverse matrix
 $B^{-1}_{\Gamma}$. The quadratic terms related to coordinates
 $\alpha_4$ or $\beta_4$ should be supplemented in the respective
 cases, see \eqref{dual_linkage_1}. The linear part
 $l(b_2, b_3)$ and the free term $f$ are as follows:
\begin{equation*}
  l(b_2, b_3) =
    \begin{cases}
      2(d_{{\alpha_1}{\beta_2}}b_2 + d_{{\alpha_1}{\beta_3}}b_3) \text{ for } L_{23}, \\
      2(d_{{\alpha_2}{\beta_2}}b_2 + d_{{\alpha_2}{\beta_3}}b_3) \text{ for } L_{13}, \\
      2(d_{{\alpha_3}{\beta_2}}b_2 + d_{{\alpha_3}{\beta_3}}b_3) \text{ for } L_{12}, \\
    \end{cases} \quad
  f =
    \begin{cases}
      d_{{\alpha_1}{\alpha_1}}  \text{ for } L_{23}, \\
      d_{{\alpha_2}{\alpha_2}}  \text{ for } L_{13}, \\
      d_{{\alpha_2}{\alpha_3}}  \text{ for } L_{12}. \\
    \end{cases}
\end{equation*}
  In section \S\ref{calc_examp_E6a1}, we give an example of the calculations for the case $E_6(a_1)$.
  By Tables \ref{sol_inequal_1}--\ref{sol_inequal_4}
  one can recover calculations for the remaining diagrams $\Gamma \in \mathsf{C4}$.

 \subsubsection{Calculation example for diagram $E_6(a_1)$}
   \label{calc_examp_E6a1}
   \index{linkage diagrams ! - examples for $E_6(a_1)$}
 The matrix $B_{\Gamma}^{-1}$ for $\Gamma = E_6(a_1)$ is given in Table \ref{tab_partial Cartan_1}.
 Here, by \eqref{q_part}:
 \begin{equation}
  \label{eq_q_E6a1}
   q(b_2, b_3) = \frac{4}{3}(b_2^2 + b_2{b_3} + b_3^2).
 \end{equation}
 In all cases below we use the fact that $b_2$, $b_3$ take values in $\{-1, 0, 1\}$, see Remark \ref{rem_values}.
~\\

  a) {\it Loctets $L_{12}$, $\gamma^{\nabla}_{12}(8) = \{0, 0, 1, 0, b_2, b_3 \}$.}
\begin{equation}
  \label{loctet_calc_E6a1}
  \begin{split}
    \mathscr{B}^{\vee}_{\Gamma}(\gamma^{\nabla}_{12}(8)) =
    &  \frac{1}{3}(10 + 2(4b_2 + 5b_3) + 4(b_2^2 + b_2{b_3} + b_3^2)) < 2, \quad \text {i.e.,} \\
    &   \frac{1}{3}(2(b_2 + b_3)^2 + 2(b_2 + 2)^2 + 2(b_3 + \frac{5}{2})^2 - \frac{21}{2}) < 2, \\
    &   \frac{2}{3}((b_2 + b_3)^2 + (b_2 + 2)^2 + (b_3 + \frac{5}{2})^2) < 2 + \frac{7}{2} = \frac{11}{2}, \\
    &  (b_2 + b_3)^2 + (b_2 + 2)^2  + (b_3 + \frac{5}{2})^2 < \frac{33}{4} = 8\frac{1}{4}. \\
   \end{split}
\end{equation}
 Recall that  $b_2, b_3 \in \{-1, 0, 1\}$. By \eqref{loctet_calc_E6a1} we have $b_2 \neq 1$, i.e.,
 $b_2 = -1$ or $b_2 = 0$. For $b_2 = 0$ we get
\begin{equation*}
     b_3^2 + (b_3 + \frac{5}{2})^2 < 4\frac{1}{4}.
\end{equation*}
  Only $b_3 = -1$ is suitable for this case. For $b_2 = -1$ we get
\begin{equation*}
     (b_3-1)^2 + (b_3 + \frac{5}{2})^2 < 7\frac{1}{4}.
\end{equation*}
 Again, $b_3 = -1$ is the single suitable solution.
 We get
 \begin{equation*}
   \gamma^{\nabla}_{12}(8) =  \{ 0, 0, 1, 0, 0, -1 \}  \text{ or } \gamma^{\nabla}_{12}(8) = \{ 0, 0, 1, 0, -1, -1 \}.
\end{equation*}
~\\

  b) {\it Loctets $L_{13}$, $\gamma^{\nabla}_{13}(8) = \{0, 1, 0, 0, b_2, b_3 \}$.}
\begin{equation*}
  \begin{split}
    \mathscr{B}^{\vee}_{\Gamma}(\gamma^{\nabla}_{13}(8)) =
    &  \frac{1}{3}(4 + 2(-b_2 + b_3) + 4(b_2^2 + b_2{b_3} + b_3^2)) < 2, \quad \text {i.e.,} \\
    &  \frac{1}{3}(2(b_2 + b_3) + 2(b_2 - \frac{1}{2})^2 + 2(b_3 + \frac{1}{2})^2 + 4 - \frac{1}{2} - \frac{1}{2})) < 2,  \\
    &  (b_2 + b_3)^2 + (b_2 - \frac{1}{2})^2  + (b_3 + \frac{1}{2})^2 < \frac{3}{2}. \\
   \end{split}
\end{equation*}
We get
\begin{equation*}
    \gamma^{\nabla}_{13}(8) =  \{ 0, 1, 0, 0, 0, 0 \} \text{ or } \gamma^{\nabla}_{13}(8) = \{ 0, 1, 0, 0,  1, -1 \}.
\end{equation*}
~\\

c) {\it Loctets $L_{23}$, $\gamma^{\nabla}_{23}(8) = \{1, 0, 0, 0, b_2, b_3 \}$.}
\begin{equation*}
  \begin{split}
    \mathscr{B}^{\vee}_{\Gamma}(\gamma^{\nabla}_{23}(8)) =
    &  \frac{1}{3}(4 + 2(b_2 + 2b_3) + 4(b_2^2 + b_2{b_3} + b_3^2)) < 2, \quad \text {i.e.,} \\
    &  (b_2 + b_3)^2 + (b_2 + \frac{1}{2})^2  + (b_3 + 1)^2 < \frac{9}{4}. \\
   \end{split}
\end{equation*}
 Here,
\begin{equation*}
   \gamma^{\nabla}_{23}(8) =  \{ 0, 1, 0, 0, 0, 0 \} \text{ or } \gamma^{\nabla}_{23}(8) = \{ 0, 1, 0, 0,  0, -1 \}.
\end{equation*}
~\\
 The corresponding $6$ loctets of the linkage system $E_6(a_1)$ are depicted in Fig. \ref{E6a1_linkages}.

\subsection{Calculation of the $\beta$-unicolored linkage diagrams}
  \label{sec_calc_homog}
  \index{linkage diagrams ! - calculation, $\beta$-unicolored}

 Now we consider $\beta$-unicolored linkage diagrams.
 Let  $a_i = (\alpha_i, \gamma)$ (resp. $b_i = (\beta_i, \gamma)$) be coordinates
 of linkage label vector $\gamma^{\nabla}$. For $\beta$-unicolored linkage diagram $\gamma^{\nabla}$,
 we have $a_i = 0$ for $i = 1,2,3$. In addition, we note that
 \begin{equation}
   \label{b1_is_0}
       b_1 = (\gamma, \beta_1) = 0,
 \end{equation}
 otherwise roots $\{\alpha_1, \alpha_2, \alpha_3, \beta_1, \gamma\}$ constitute the
 extended Dynkin diagram $\widetilde{D}_4$, which is impossible, see Lemma \ref{lem_non_ext_Dynkin}.
 Eq. \eqref{b1_is_0} holds for any Carter diagrams out $\mathsf{C4} \coprod \mathsf{DE4}$
 except for $D_4(a_1)$. Note that
 \begin{equation*}
   \mathscr{B}^{\vee}(\gamma^{\nabla}) = \mathscr{B}^{\vee}(-\gamma^{\nabla}) = q(b_2, b_3, \dots),
 \end{equation*}
 and solving the inequality $\mathscr{B}^{\vee}(\gamma^{\nabla}) < 2$
 we can assume that $b_2 > 0$, or $b_2 =0, b_3 > 0$, etc.
 We present here calculations only for the cases $E_6(a_1)$, $E_6(a_2)$ and $E_7(a_1)$.
 From Tables \ref{homog_inequal_1}--\ref{homog_inequal_3} one can recover calculations of the remaining cases.

\subsubsection{$\beta$-unicolored linkage diagrams in $\mathscr{L}(E_6(a_1))$ and $\mathscr{L}(E_6(a_2))$}
  \label{sec_homog_E6a1a2}
  \index{linkage diagrams ! - $\beta$-unicolored, in $\mathscr{L}(E_6(a_1))$ and $\mathscr{L}(E_6(a_2))$}

 For Carter diagrams $E_6(a_1)$ and $E_6(a_2)$, the $\beta$-unicolored linkage diagrams look as $\{0, 0, 0, 0, b_2, b_3\}$.
 For both diagrams $E_6(a_1)$ and $E_6(a_2)$, the $\beta$-unicolored linkage diagrams
 coincide since the principal $2\times2$ submatrices of $B^{-1}_{\Gamma}$ associated with coordinates $\beta_2$, $\beta_3$
 coincide and are as follows:
\begin{equation*}
  \label{homog_E6a1_E6a2}
   \frac{1}{3}
   \left [
  \begin{array}{cc}
     4 & 2 \\
     2 & 4 \\
  \end{array}
   \right ],
\end{equation*}
see Table \ref{tab_partial Cartan_1}. By \eqref{eq_q_E6a1} and Theorem \ref{th_B_less_2}, we have
\begin{equation}
  \label{homog_E6a1_E6a2_2}
    \begin{split}
    q(b_2, b_3) = & \frac{4}{3}(b_2^2 + b_3^2 + b_2{b_3}) =
                    \frac{4}{3}(\frac{1}{2}b_2^2 + \frac{1}{2}b_3^2 + \frac{1}{2}(b_2 + b_3)^2) < 2, \quad \text {i.e.,} \\
     & b_2^2 + b_3^2 + (b_2 + b_3)^2 < 3.
    \end{split}
\end{equation}
 There are exactly $6$ solutions of the inequality \eqref{homog_E6a1_E6a2_2}, the corresponding
linkage diagrams are:
\begin{equation}
  \label{homog_E6a1_E6a2_3}
   \begin{array}{lll}
      & \{ 0, 0, 0, 0, 0, 1 \},  & \{ 0, 0, 0, 0, 0, -1 \}, \\
      & \{ 0, 0, 0, 0, 1, 0 \},  & \{ 0, 0, 0, 0, -1, 0 \}, \\
      & \{ 0, 0, 0, 0, 1, -1 \},  & \{ 0, 0, 0, 0, -1, 1 \}. \\
   \end{array}
\end{equation}
 These $6$ linkage diagrams are located outside of the loctets in the linkage systems $\mathscr{L}(E_6(a_1))$, $\mathscr{L}(E_6(a_2))$,
 see Figs. \ref{E6a1_linkages}, \ref{E6a2_linkages}.

 \subsubsection{$\beta$-unicolored linkage diagrams in $\mathscr{L}(E_7(a_1))$}
 \index{linkage diagrams ! - $\beta$-unicolored, in $\mathscr{L}(E_7(a_1))$}

 Here, the $\beta$-unicolored linkage diagrams look as $\{0, 0, 0, 0, b_2, b_3, b_4\}$.
 The principal $3\times3$ submatrices  of $B^{-1}_{\Gamma}$ associated with coordinates $\beta_2$, $\beta_3$, $\beta_4$
 is as follows:
\begin{equation*}
  \label{homog_E7a1}
   \frac{1}{2}
   \left [
  \begin{array}{ccc}
     3 & 2 & 1 \\
     2 & 4 & 2 \\
     1 & 2 & 3 \\
  \end{array}
   \right ],
\end{equation*}
see Table \ref{tab_partial Cartan_2}. Then we have
 \begin{equation}
  \label{homog_E7a1_2}
   \begin{split}
  \mathscr{B}^{\vee}(\gamma^{\nabla}) = &
    \frac{1}{2}(3b_2^2 + 4b_3^2 + 3b_4^2 + 4b_2{b_3} + 2b_2{b_4} + 4b_3{b_4}) < 2, \quad
    \text {i.e.,}\\
  & 2(b_2 + b_3)^2 + 2(b_3 + b_4)^2 + (b_2 + b_4)^2 < 4.
  \end{split}
\end{equation}
 There are exactly $8$ solutions of the inequality \eqref{homog_E7a1_2}, the corresponding
  linkage diagrams are:
\begin{equation*}
  \label{homog_E7a1_3}
   \begin{array}{lll}
      & \{ 0, 0, 0, 0, 1, -1, 0 \},  & \{ 0, 0, 0, 0, -1, 1, 0 \}, \\
      & \{ 0, 0, 0, 0, 0, 1, -1 \},  & \{ 0, 0, 0, 0, 0, -1, 1 \}, \\
      & \{ 0, 0, 0, 0, 0, 0, 1 \},  & \{ 0, 0, 0, 0, 0, 0, -1 \}, \\
      & \{ 0, 0, 0, 0, 1, 0, 0 \},  & \{ 0, 0, 0, 0, -1, 0, 0 \}. \\
   \end{array}
\end{equation*}
 These $8$ linkage diagrams are located outside of the loctets in the linkage systems $\mathscr{L}(E_7(a_1))$,
 see Fig. \ref{E7a1_linkages}.

\subsection{Linkage systems for simply-laced Dynkin diagrams}

 \index{${\bf B}$, Cartan matrix associated with a Dynkin diagram}
 \index{Cartan matrix ! - ${\bf B}$}
 \index{$B_{\Gamma}$, partial Cartan matrix}
 \index{Cartan matrix ! - partial Cartan matrix $B_{\Gamma}$}
 \index{linkage diagrams ! - for Dynkin diagrams}
 In order to build the linkage systems for Dynkin diagrams $E_n$, $D_n$,
 we can use the technique of the partial Cartan matrix,
 linkage diagrams and loctets from \S\ref{sec_loctets_diagr}.
 Note that the partial Cartan matrix for Dynkin diagrams coincides with
 the usual Cartan matrix ${\bf B}$ associated with the given Dynkin diagram.
 Since $E_8$ does not have linkage diagrams, see Remark \ref{rem_l_less_8},
 we are interested only
 in $E_6$, $E_7$, $D_n$. In cases $E_6$, $E_7$, $D_5$, $D_6$, $D_7$, for the Cartan matrix ${\bf B}$
 and its inverse  ${\bf B}^{-1}$, see Table \ref{tab_partial Cartan_3}.
 One can recover the complete calculation  of linkage diagrams $\gamma^{\nabla}(8)$ of all loctets
 of $E_6$, $E_7$, $D_5$, $D_6$, $D_7$  by means of Tables \ref{sol_inequal_5}, \ref{sol_inequal_6}.
 The $\beta$-unicolored linkage diagrams look as follows:
\begin{equation*}
  \gamma^{\nabla} =
  \left \{
  \begin{array}{ll}
       \hspace{-2mm}\{0, 0, 0, 0, b_2, b_3 \} & \text{ for } E_6, \\
       \hspace{-2mm}\{0, 0, 0, a_4, 0, b_2, b_3 \} & \text{ for } E_7, \\
       \hspace{-2mm}\{0, 0, 0, 0, b_2 \} & \text{ for } D_5, \\
       \hspace{-2mm}\{0, 0, 0, a_4, 0, b_2 \} & \text{ for } D_6, \\
       \hspace{-2mm}\{0, 0, 0, a_4, 0, b_2, b_3 \} & \text{ for } D_7,
  \end{array}
  \right .
\end{equation*}
 see Tables \ref{homog_inequal_1}--\ref{homog_inequal_3}. The
 $\beta$-unicolored linkage diagrams are located outside of all loctets, see Figs. \ref{27_weight_diagr_E6__2comp}(top),
 \ref{E7pure_linkage_system}, \ref{D5pure_loctets}, \ref{D6pure_loctets}.

Note that for $E_6$, the principal matrix associated with coordinates $\beta_2$, $\beta_3$ coincide with
the principal matrix for the Carter diagrams $E_6(a_1)$, $E_6(a_2)$, see \S\ref{sec_homog_E6a1a2},
and, consequently, $\beta$-unicolored linkage diagrams coincide with these diagrams for
$E_6(a_1)$, $E_6(a_2)$, see $6$ solutions \eqref{homog_E6a1_E6a2_3} of the inequality \eqref{homog_E6a1_E6a2_2}.

  For $A_l$ the technique of loctets cannot be applied. The reason of this is lack of branch point.
  For $l = 5,6,7$, the linkage system $\mathscr{L}(A_l)$ consists of $A$-, $D$- and $E$-components,
  see \S\ref{sec_plis_Al}.
  For $l \leq 4$ and $l \geq 8$, the linkage system $\mathscr{L}(A_l)$ consists only of $A$- and $D$-components,
  see \S\ref{sec_Al_lg8}.  The linkage system components $\mathscr{L}_{A_{l+1}}(A_l)$ and
  $\mathscr{L}_{D_{l+1}}(A_l)$ are constructed by means of induction process, see \S\ref{sec_Al_lg8} and
  Fig. \ref{2_lines_A2nMin1} - Fig. \ref{A5_to_A6D6_pass}.

\subsubsection{Asymmetric relations between $A$-, $D$-, $E$-types of Dynkin diagrams}

 The relation between the Dynkin diagrams of $E$-type and $D$-type is asymmetric in the following sense:
 The root systems $E_n$ contains the root subsystem $D_{n-1}$ for $n = 6,7,8$;
 however, $E_6$ is not contained in $D_n$ for any n, see Remark \ref{rem_l_less_8}.

 Similarly, the relation between the Dynkin diagrams of $A$-type and Dynkin diagrams of $D$- and $E$-types is asymmetric,
 namely: The root systems of the $D$- and the $E$-type contain root subsystems $A_n$ for a certain $n$.
 The converse statement is not true: The root system of $A$-type does not contain root subsystems of
 $D$- and $E$-types, see Lemma \ref{lem_case_An}(ii).

 The asymmetric relations between $A$-, $D$-, $E$-types of Dynkin diagrams can be observed
 by means of the Table \ref{tab_val_Bmin1}. By abuse of language we can say that
 {\bf $E$-type contains $ADE$-types; $D$-type contains $AD$-types; $A$-type contains only $A$-type.}


TITLE: Minimum polynom of an element in $K=\mathbb{F}_5[x]/(x^2-2)$
QUESTION [0 upvotes]: I want to know how to calculate the minimum polynom of an element $\alpha$ in $K=\mathbb{F}_5[X]/(X^2-2)$ where $\alpha$ is the image on $K$ of $X+2$
I'm already verficated that $K$ is a field. As I know, the minimum polynom is $g$ with the smallest degree satisfying $g(\alpha)=0$.
In my notes there is an indication: If $f(X)=X^2-2$, calculate $f(X-2)$.
But I don't understand at all. I would very appreciate any help. Thanks.

REPLY [2 votes]: Let's write $\beta$ for the residue class of $X$ in ${\mathbb F}_5[X]/(X^2-2)$, so we're looking at the field ${\mathbb F}_5[\beta]$. What is the minimum polynomial of $\beta$ over ${\mathbb F}_5$? (Trivial!)
Now $\alpha = \beta + 2$. So how do you now turn the minimum polynomial of $\beta$ into the minimum polynomial of $\alpha$? (This is what the hint tells you to do.)


TITLE: Find measure of an open interval given closed interval
QUESTION [0 upvotes]: Suppose $\mu$ is a measure on $\mathbb R$ with $\mu([0, a])=e^a, a\ge 0$. Find $\int (1_{(0,2)}+21_{[1,3]})d\mu$.

I've run into some trouble finding $\mu((0, 2))$. I know that $\mu((0, 2))+\mu(\{0\})+\mu(\{2\})=\mu([0,2])=e^2$ and that $\mu(\{0\})=e^0=1$. But there are two unknowns in the equation.
Just as for $e^3=\mu([0, 3])=\mu([0,1))+\mu([1, 3])$, I don't know what $\mu([0, 1))$ is so I can't solve for $\mu([1, 3])$.

REPLY [1 votes]: First note that
$$
\mu((a,b])=\mu([0,b]\setminus [0,a])=e^b-e^a
$$
for $0\leq a<b$.
Moreover,
$$
\mu(a,b)=\mu\left(\bigcup_{n=1}^\infty(a,b-1/n]\right)=\lim_{n\to\infty}\mu(a,b-1/n)=e^b-e^a.
$$
In particular, the measure $\mu$ has no atoms. I think you can take it from here.


TITLE: Compute $\sum _{i=0}^n \left(\frac{i}{n}\right)^3=\frac{(n+1)^2}{4 n}$
QUESTION [1 upvotes]: Can someone show me how one can deal with this get the answer provided?
$$\sum _{i=0}^n \left(\frac{i}{n}\right)^3=\frac{(n+1)^2}{4 n}$$
Thanks

REPLY [4 votes]: The equality is equivalent to
$$\sum_{i=1}^n i^3=\frac14 n^2(n+1)^2$$
and we can prove it by induction. For the inductive step we have
$$\sum_{i=1}^{n+1} i^3=\sum_{i=1}^n i^3+(n+1)^3=\frac14 n^2(n+1)^2+(n+1)^3=\cdots\cdots$$

REPLY [1 votes]: Multiply both sides by $n^3$, then use complete induction.


text:
\section{Flexibility criterion for affine cones}
Here we generalise flexibility criteria for affine cones \cite[Theorem 1.4]{MPS} and \cite[Theorem 5]{P13}.
In this section we let $Y$ denote a normal projective variety, $H$ a very ample divisor on $Y$, and $X=\AffCone_H(Y)$ the affine cone over $Y$ corresponding to $H$. By $\pi\colon X\setminus\{0\}\to Y$ we denote the projectivizing map.

\begin{definition}[{\cite[Definition 3.1.7]{KPZ11}}]
An open subset $U\subset Y$ is called $H$-\emph{polar} if
the complement $Y\setminus U$ is the support of some effective $\QQ$-divisor equivalent to $H$ over $\QQ$.
\end{definition}

\begin{lemma}\label{lm:inv}
Let $U$ be an $H$-polar affine open subset of $Y$ and $S$ be an $\SAut(X)$-orbit on $X$.
Then $\pi(S)\cap U$ is $\SAut(U)$-invariant.
\end{lemma}
\begin{proof}
Assume the contrary.
Then there exists a $\G_a$-action $G$ on $U$ that does not preserve $\pi(S)\cap U$.
By \cite[Lemma 1.3]{MPS}, there exists a corresponding $\G_a$-action $\hat G$ on $X$ trivial on $X\setminus \pi^{-1}(U)$ such that $\pi$ sends $\hat G$-orbits to $G$-orbits.
Thus, $\hat G$ does not preserve $S\cap\pi^{-1}(U)$.
So, $\hat G$ does not preserve $S$, a contradiction.
\end{proof}

\begin{definition}
Let $\mathcal{U}=\{U\}$ be a collection of open affine subsets of $Y$.
\begin{enumerate}
    \item We say that a subset $Z$ of $Y$ is $\mathcal{U}$-\emph{invariant} if for any $U\in\mathcal{U}$ the intersection $U\cap Z$ is $\SAut(U)$-invariant.
    \item We say that $\mathcal{U}$ is \emph{transversal} if $\bigcup_{U\in \mathcal{U}} U$ does not admit nontrivial $\mathcal{U}$-invariant subsets.
    \item We say that $\mathcal{U}$ is $H$-\emph{complete} if for any (not necessarily effective) $\QQ$-divisor equivalent to $H$ its support is not contained in the complement $Y\setminus\bigcup_{U\in\mathcal{U}} U$.
\end{enumerate}
\end{definition}

\begin{theorem}\label{th:flex}
 Let $\mathcal{U}$ be a transversal collection of $H$-polar open affine subsets of a normal projective variety $Y$ for some very ample divisor $H$.
 Then there exists an $\SAut(X)$-orbit $S$ on the corresponding affine cone $X$ whose image contains $\bigcup_{U\in\mathcal{U}}U$.
  If, moreover, $\mathcal{U}$ is $H$-complete, then $S$ is open in $X$ and contains the open subset $\pi^{-1}(\bigcup_{U\in\mathcal{U}}U)\subset X$.
\end{theorem}
 \begin{proof}
Let $S\subset X$ be an $\SAut(X)$-orbit of some point $x\in\pi^{-1}(\bigcup_{U\in\mathcal{U}}U)$. By \cite[Proposition 1.3]{AFKKZ}, $S$ is locally closed.
By Lemma~\ref{lm:inv}, the image $\pi(S)$ is $\mathcal{U}$-invariant.
Since $\mathcal{U}$ is transversal and $\pi(S)\cap \bigcup_{U\in\mathcal{U}}U\ni \pi(x)$ is nonempty,
one has $\pi(S)\supset\bigcup_{U\in\mathcal{U}}U$.

Consider the natural $\G_m$-action on $X$ by homotheties.
It sends $\SAut(X)$-orbits to $\SAut(X)$-orbits.
The subgroup $\Gamma\subset\G_m$ that sends $S$ to itself either is finite, or equals $\G_m$.
In the latter case $S=\pi^{-1}\circ\pi(S)\supset\pi^{-1}(\bigcup_{U\in\mathcal{U}}U)\subset X.$
Assume the former case, then $S$ is not open in $X$.

Denote by $X^\times$ the blowup of $X$ at the origin.
Then $X^\times$ is the total space of the line bundle $\O_Y(-H)$ over $Y$. Denote $\gamma=|\Gamma|$.
The quotient $X'=X^\times/\Gamma$ is the total space of $\O_Y(-\gamma H)$ given by the map $t\mapsto t^{\gamma}$ in a local coordinate $t$ on each trivializing chart.

Thus, we have the sequence of maps
\[X\dashrightarrow X^\times\to X'\to Y.\]
Let $S'$ be the Zariski closure of the image of $S$ in $X'$. Since $\pi(S)$ is open in $Y$, $S'$ intersects a generic fiber of $X'\to Y$ in a single point. Then $S'$ is a rational section of the line bundle $\O_Y(-\gamma H)$. The corresponding Cartier divisor $D$ is equivalent to $\gamma H$.

Therefore, $\frac{1}{\gamma}D$ is a $\QQ$-divisor equivalent to $H$ such that its support is disjoint with $\pi(S)$.
So, $\mathcal{U}$ is not $H$-complete.
This argument is essentially a generalisation of \cite[Lemma 1.2]{MPS}.
\end{proof}


text:
\section{Random Rotations and Sparse PCA}

In this section, we deduce tight lower bounds for detection in sparse PCA when $k \gg \sqrt{n}$. We also show a suboptimal lower bound when $k \ll \sqrt{n}$ matching the results of \cite{berthet2013complexity} and \cite{gao2017sparse}. In both cases, we reduce from biclustering and rank-1 submatrix to biased and unbiased variants of sparse PCA. The reductions in this section are relatively simple, with most of the work behind the lower bounds we show residing in the reductions from PC to biclustering and rank-1 submatrix. This illustrates the usefulness of using natural problems as intermediates in constructing average-case reductions. The lower bounds we prove make use of the following theorem of Diaconis and Freedman showing that the first $m$ coordinates of a unit vector in $n$ dimensions where $m \ll n$ are close to independent Gaussians in total variation \cite{diaconis1987dozen}.

\begin{theorem}[Diaconis and Freedman \cite{diaconis1987dozen}]
Suppose that $(v_1, v_2, \dots, v_n)$ is uniformly distributed according to the Haar measure on $\mathbb{S}^{n-1}$. Then for each $1 \le m \le n - 4$,
$$\TV\left( \mL\left( v_1, v_2, \dots, v_m \right), N(0, n^{-1})^{\otimes m} \right) \le \frac{2(m+3)}{n - m - 3}$$
\end{theorem}

The next lemma is the crucial ingredient in the reductions of this section. Note that the procedure $\textsc{Random-Rotation}$ in Figure \ref{fig:randrot} requires sampling the Haar measure on $\mathcal{O}_{\tau n}$. This can be achieved efficiently by iteratively sampling a Gaussian, projecting it onto the orthogonal complement of the vectors chosen so far, normalizing it and adding it to the current set. Repeating this for $n$ iterations yields an implementation for the sampling part of Step 2 in Figure \ref{fig:randrot}. In the next lemma, we show that $\textsc{Random-Rotation}$ takes an instance $\lambda \cdot uv^\top + N(0, 1)^{\otimes m \times n}$ of rank-1 submatrix to an $m \times n$ matrix with its $n$ columns sampled i.i.d. from $N(0, I_m + \theta vv^\top)$.

\begin{figure}[t!]
\begin{algbox}
\textbf{Algorithm} \textsc{Random-Rotation}

\vspace{2mm}

\textit{Inputs}: Matrix $M \in \mathbb{R}^{m \times n}$, parameter $\tau \in \mathbb{N}$
\begin{enumerate}
\item Construct the $m \times \tau n$ matrix $M'$ such that the leftmost $m \times n$ submatrix of $M'$ is $M$ and the remaining entries of $M'$ are sampled i.i.d. from $N(0, 1)$
\item Let $R$ be the leftmost $\tau n \times n$ submatrix of a random orthogonal matrix sampled from the normalized Haar measure on the orthogonal group $\mathcal{O}_{\tau n}$
\item Output $M'R$
\end{enumerate}
\vspace{1mm}
\end{algbox}
\caption{Random rotation procedure in Lemma \ref{lem:randrot}.}
\label{fig:randrot}
\end{figure}

\begin{lemma}[Random Rotation] \label{lem:randrot}
Let $\tau : \mathbb{N} \to \mathbb{N}$ be an arbitrary function with $\tau(n) \to \infty$ as $n \to \infty$. Consider the map $\phi : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$ that sends $M$ to $\textsc{Random-Rotation}$ with inputs $M$ and $\tau$. It follows that $\phi(N(0, 1)^{\otimes m \times n}) \sim N(0, 1)^{\otimes m \times n}$ and for any unit vectors $u \in \mathbb{R}^m, v \in \mathbb{R}^n$ we have that
$$\TV\left( \phi\left( \lambda \cdot uv^\top + N(0, 1)^{\otimes m \times n} \right), N\left(0, I_m + \frac{\lambda^2}{\tau n} \cdot uu^\top\right)^{\otimes n} \right) \le \frac{2(n + 3)}{\tau n - n - 3}$$
\end{lemma}

\begin{proof}
Let $R' \in \mathcal{O}_{\tau n}$ be the original $\tau n \times \tau n$ sampled in Step 2 of $\textsc{Random-Rotation}$ and let $R$ be its upper $\tau n \times n$ submatrix. Let $M$ and $M'$ be the matrices input to $\textsc{Random-Rotation}$ and computed in Step 1, respectively, as shown in Figure \ref{fig:randrot}. If $M \sim N(0, 1)^{\otimes m \times n}$, then it follows that $M' \sim N(0, 1)^{\otimes m \times \tau n}$. Since the rows of $M'$ are independent and distributed according to the isotropic distribution $N(0, 1)^{\otimes \tau n}$, multiplication on the right by any orthogonal matrix leaves the distribution of $M'$ invariant. Therefore $M' R' \sim N(0, 1)^{\otimes m \times \tau n}$ and since $M' R$ consists of the first $n$ columns of $M'R'$, it follows that $\phi(M) = M'R \sim N(0, 1)^{\otimes m \times n}$.

Now suppose that $M$ is distributed as $\lambda \cdot uv^\top + N(0, 1)^{\otimes m \times n}$ for some unit vectors $u, v$. Let $v'$ be the unit vector in $\mathbb{R}^{\tau n}$ formed by appending $\tau n - n$ zeros to the end of $v$. It follows that $M'$ is distributed as $\lambda \cdot uv'^\top + N(0, 1)^{\otimes m \times \tau n}$. Let $M' = \lambda \cdot uv'^\top + W$ where $W \sim N(0, 1)^{\otimes m \times \tau n}$. Now let $W' = WS^{-1}$ where $S \in \mathcal{O}_{\tau n}$ is sampled according to the Haar measure and independently of $R'$. Observe that
$$M'R' = \lambda \cdot u \cdot \left( R'^\top v' \right)^\top + W' S R'$$
Now note that conditioned on $R'$, the product $SR'$ is distributed according to the Haar measure on $\mathcal{O}_{\tau n}$. This implies that $SR'$ is independent of $R'$. Therefore $W' S R'$ is independent of $R'$ and distributed according to $N(0, 1)^{\otimes m \times \tau n}$. This also implies that $R'^\top v$ is independent of $W' S R'$ and distributed uniformly over $\mathbb{S}^{\tau n - 1}$. Let $r \in \mathbb{R}^n$ denote the vector consisting of the first $n$ coordinates of $R'^\top v'$ and let $W''$ denote the $m \times n$ matrix consisting of the first $n$ columns of $W' S R'$. It follows that $\phi(M) = M' R = \lambda \cdot u r^\top + W''$ where $r$ and $W''$ are independent. Now let $g \in \mathbb{R}^n$ be a Gaussian vector with entries i.i.d. sampled from $N(0, n^{-1})$. Also let $Z = \lambda \cdot ug^\top + W''$ and note that by Diaconis-Freedman's theorem and coupling the noise terms $W''$, the data processing inequality implies
$$\TV\left( \mL\left( \lambda \cdot ug^\top + W'' \right), \mL\left( \lambda \cdot ur^\top + W'' \right) \right) \le \TV\left( \mL(r), \mL(g) \right) \le \frac{2(n + 3)}{\tau n - n - 3}$$
Now note that since the entries of $g$ are independent, the matrix $\lambda \cdot u g^\top + W''$ has independent columns. Its $i$th row has jointly Gaussian entries with covariance matrix
\begin{align*}
\bE\left[ (\lambda \cdot u g_i + W_i) (\lambda \cdot u g_i + W_i)^\top \right] &= \bE\left[ \lambda^2 \cdot uu^\top g_i^2 + \lambda \cdot g_i  \cdot u W_i^\top + \lambda \cdot g_i \cdot W_i u^\top + W_i W_i^\top \right] \\
&= \frac{\lambda^2}{\tau n} \cdot uu^\top + I_m
\end{align*}
Therefore $\lambda \cdot ug^\top + W'' \sim N\left(0, I_m + \frac{\lambda^2}{\tau n} \cdot uu^\top\right)^{\otimes n}$. Combining these results yields that
$$\TV\left( \phi(M), N\left(0, I_m + \frac{\lambda^2}{\tau n} \cdot uu^\top\right)^{\otimes n} \right) \le \frac{2(n + 3)}{\tau n - n - 3}$$
which completes the proof of the lemma.
\end{proof}

Applying reflection cloning to produce an instance of rank-1 submatrix and then randomly rotating to obtain an instance of sparse PCA yields a reduction from $\textsc{PC}$ to $\textsc{SPCA}$ as given in $\textsc{SPCA-High-Sparsity}$. This establishes tight lower bounds in the regime $k \gg \sqrt{n}$. This reduction is stated in the next lemma, which takes an instance of $\textsc{PC}(n, k, 1/2)$ to an instance of sparse PCA with sparsity $2^\ell k$ and $\theta = \frac{\mu^2 k^2}{2\tau n}$ where $\tau$ and $\mu$ can be taken to be polylogarithmically small in $n$. The proof involves a simple application of the data processing and triangle inequalities and is deferred to Appendix \ref{app8}.

\begin{figure}[t!]
\begin{algbox}
\textbf{Algorithm} \textsc{SPCA-High-Sparsity}

\vspace{2mm}

\textit{Inputs}: Graph $G \in \mG_n$, number of iterations $\ell$, function $\tau : \mathbb{N} \to \mathbb{N}$ with $\tau(n) \to \infty$
\begin{enumerate}
\item Compute the output $M$ of $\textsc{ROS-Reduction}$ applied to $G$ with $\ell$ iterations
\item Output the matrix returned by $\textsc{Random-Rotation}$ applied with inputs $M$ and $\tau$
\end{enumerate}
\vspace{2mm}
\textbf{Algorithm} \textsc{SPCA-Low-Sparsity}

\vspace{2mm}

\textit{Inputs}: Graph $G \in \mG_n$, number of iterations $\ell$, function $\tau : \mathbb{N} \to \mathbb{N}$ with $\tau(n) \to \infty$
\begin{enumerate}
\item Compute the output $M$ of $\textsc{BC-Reduction}$ applied to $G$ with $\ell$ iterations
\item Output the matrix returned by $\textsc{Random-Rotation}$ applied with inputs $M$ and $\tau$
\end{enumerate}
\vspace{2mm}
\textbf{Algorithm} \textsc{SPCA-Recovery}

\vspace{2mm}

\textit{Inputs}: Graph $G \in \mG_n$, density bias $\rho$, function $\tau : \mathbb{N} \to \mathbb{N}$ with $\tau(n) \to \infty$
\begin{enumerate}
\item Let $M$ be the output of $\textsc{BC-Recovery}$ applied to $G$ with density bias $\rho$
\item Output the matrix returned by $\textsc{Random-Rotation}$ applied with inputs $M$ and $\tau$
\end{enumerate}
\vspace{1mm}
\end{algbox}
\caption{Reductions to $\textsc{SPCA}_D$ when $k \gtrsim \sqrt{n}$ and $k \lesssim \sqrt{n}$ in Lemmas \ref{lem:hsspca} and \ref{lem:lsspca} and reduction to $\textsc{SPCA}_{R}$ in Theorem \ref{thm:spcarec}.}
\label{fig:randrot}
\end{figure}

\begin{lemma} \label{lem:hsspca}
Suppose that $n$ and $\ell$ are such that $\ell = O(\log n)$ and are sufficiently large,
$$\mu = \frac{\log 2}{2 \sqrt{6 \log n + 2\log 2}}$$
and $\tau : \mathbb{N} \to \mathbb{N}$ is an arbitrary function with $\tau(n) \to \infty$ as $n \to \infty$. Then $\phi = \textsc{SPCA-High-Sparsity}$ is a randomized polynomial time computable map $\phi : \mG_n \to \mathbb{R}^{n \times n}$ such that if $G$ is an instance of $\text{PC}(n, k, 1/2)$ then under $H_0$, it holds that $\phi(G) \sim N(0, 1)^{\otimes n \times n}$ and under $H_1$, there is a prior $\pi$ such that
$$\TV\left( \mL_{H_1}(\phi(G)), \int N\left(0, I_n + \frac{\mu^2 k^2}{2 \tau n} \cdot uu^\top\right)^{\otimes n} d\pi(u) \right) \le \frac{2(n + 3)}{\tau n - n - 3} + O\left( \frac{1}{\sqrt{\log n}} + k^{-1} \right)$$
where $\pi$ is supported on unit vectors in $\mathcal{V}_{n, 2^\ell k}$.
\end{lemma}

The next lemma gives the guarantees of $\textsc{SPCA-Low-Sparsity}$, which maps from planted clique to an instance of biclustering and then to sparse PCA. This reduction shows hardness for the canonical simple vs. simple hypothesis testing formulation of sparse PCA. In particular, the output in Lemma \ref{lem:randrot} is close in total variation to the simple vs. simple model $\textsc{UBSPCA}$. After multiplying the rows of the matrix output in Lemma \ref{lem:randrot} by $\pm 1$, each with probability $1/2$, this also yields a reduction to $\textsc{USPCA}$. The lemma can be proven with the same applications of the triangle and data processing inequalities as in Lemma \ref{lem:hsspca} using the total variation bound in Lemma \ref{lem:bc} instead of Lemma \ref{lem:ros}.

Before stating the lemma, we determine the parameters of the sparse PCA instance that $\textsc{SPCA-Low-Sparsity}$ produces. Under $H_1$, $\textsc{BC-Reduction}$ takes an instance of $G(n, k, 1/2)$ approximately in total variation to $2^{-\ell-1/2} \mu \cdot \mathbf{1}_S \mathbf{1}_T^\top + N(0, 1)^{\otimes 2^\ell n \times 2^\ell n}$ where $S, T \subseteq [2^\ell n]$ have size $2^\ell k$ and $\mu$ is subpolynomial in $n$. This matrix can be rewritten as $2^{-1/2} \mu k \cdot uv^\top + N(0, 1)^{\otimes 2^\ell n \times 2^\ell n}$ where $u, v$ are $2^\ell k$-sparse unit vectors. Now $\textsc{Random-Rotation}$ takes this matrix to an instance of $\textsc{UBSPCA}_D$ with the resulting parameters $d = n' = 2^\ell n$, $k' = 2^\ell k$ and $\theta = \frac{\mu^2 k^2}{2^{\ell + 1} \tau n}$ where $\tau, \mu$ are subpolynomial in $n$.

\begin{lemma} \label{lem:lsspca}
Suppose that $n$ and $\ell$ are such that $\ell = O(\log n)$ and are sufficiently large,
$$\mu = \frac{\log 2}{2 \sqrt{6 \log n + 2\log 2}}$$
and $\tau : \mathbb{N} \to \mathbb{N}$ is an arbitrary function with $\tau(n) \to \infty$ as $n \to \infty$. Then $\phi = \textsc{SPCA-Low-Sparsity}$ is a randomized polynomial time computable map $\phi : \mG_n \to \mathbb{R}^{2^\ell n \times 2^\ell n}$ such that if $G$ is an instance of $\text{PC}(n, k, 1/2)$ then under $H_0$, it holds that $\phi(G) \sim N(0, 1)^{\otimes 2^\ell n \times 2^\ell n}$ and
$$\TV\left( \mL_{H_1}(\phi(G)), \int N\left(0, I_n + \frac{\mu^2 k^2}{2^{\ell + 1} \tau n} \cdot uu^\top\right)^{\otimes n} d\pi(u) \right) \le \frac{2(2^\ell n + 3)}{\tau \cdot 2^\ell n - 2^\ell n - 3} + O\left( \frac{1}{\sqrt{\log n}} \right)$$
where $\pi$ is the uniform distribution over all $2^\ell k$-sparse unit vectors in $\mathbb{R}^{2^\ell n}$ with nonzero entries equal to $1/\sqrt{2^\ell k}$.
\end{lemma}

We now apply these reductions to deduce planted clique hardness for sparse PCA and its variants. The proofs of the next two theorems are deferred to Appendix \ref{app8}. Note that when $k \ll \sqrt{n}$, the lower bounds for sparse PCA are not tight. For biased sparse PCA, the lower bounds are only tight at the single point when $\theta = \tilde{\Theta}(1)$. The next theorem deduces tight hardness for $\textsc{SPCA}_D$ when $k \gtrsim \sqrt{n}$ with Lemma \ref{lem:hsspca}.

\begin{theorem} \label{thm:spca}
Let $\alpha > 0$ and $\beta \in (0, 1)$ be such that $\alpha > \max(1 - 2\beta, 0)$. There is a sequence $\{ (N_n, K_n, d_n, \theta_n) \}_{n \in \mathbb{N}}$ of parameters such that:
\begin{enumerate}
\item The parameters are in the regime $d = \Theta(N)$, $\theta = \tilde{\Theta}(N^{-\alpha})$ and $K = \tilde{\Theta}(N^\beta)$ or equivalently,
$$\lim_{n \to \infty} \frac{\log \theta_n^{-1}}{\log N_n} = \alpha \quad \text{and} \quad \lim_{n \to \infty} \frac{\log K_n}{\log N_n} = \beta$$
\item For any sequence of randomized polynomial-time tests $\phi_n : \mG_{N_n} \to \{0, 1\}$, the asymptotic Type I$+$II error of $\phi_n$ on the problems $\textsc{SPCA}_D(N_n, K_n, d_n, \theta_n)$ is at least $1$ assuming the PC conjecture holds for $p = 1/2$.
\end{enumerate}
\end{theorem}

Similarly, varying the parameters $\ell$ and $k$ in Lemma \ref{lem:lsspca} yields the following hardness for the simple vs. simple hypothesis testing formulations of biased and ordinary sparse PCA. Since $\textsc{UBSPCA}_D$ and $\textsc{USPCA}_D$ are instances of $\textsc{BSPCA}_D$ and $\textsc{SPCA}_D$, respectively, the next theorem also implies the lower bounds when $\alpha > 1 - 2\beta$ in Theorem \ref{thm:spca} when $k \lesssim \sqrt{n}$.

\begin{theorem} \label{thm:uspca}
Let $\alpha > 0$ and $\beta \in (0, 1)$ be such that $\frac{1 - \alpha}{2} < \beta < \frac{1 + \alpha}{2}$. There is a sequence $\{ (N_n, K_n, d_n, \theta_n) \}_{n \in \mathbb{N}}$ of parameters such that:
\begin{enumerate}
\item The parameters are in the regime $d = \Theta(N)$, $\theta = \tilde{\Theta}(N^{-\alpha})$ and $K = \tilde{\Theta}(N^\beta)$ or equivalently,
$$\lim_{n \to \infty} \frac{\log \theta_n^{-1}}{\log N_n} = \alpha \quad \text{and} \quad \lim_{n \to \infty} \frac{\log K_n}{\log N_n} = \beta$$
\item For any sequence of randomized polynomial-time tests $\phi_n : \mG_{N_n} \to \{0, 1\}$, the asymptotic Type I$+$II error of $\phi_n$ on the problems $\textsc{USPCA}_D(N_n, K_n, d_n, \theta_n)$ and $\textsc{UBSPCA}_D(N_n, K_n, d_n, \theta_n)$ is at least $1$ assuming the PC conjecture holds for $p = 1/2$.
\end{enumerate}
\end{theorem}

To conclude this section, we observe that the reduction $\textsc{SPCA-Recovery}$ shows that recovery in $\textsc{UBSPCA}_R$ is hard if $\theta \ll 1$ given the PDS recovery conjecture. The proof of the following theorem follows the same structure as Lemma \ref{lem:hsspca} and Theorem \ref{thm:bcrec}. Note that $\textsc{BC-Recovery}$ approximately maps from $\textsc{PDS}_R(n, k, 1/2 + \rho, 1/2)$ to $\textsc{BC}_R(n, k, \mu)$ where $\mu = \frac{\log (1 + 2\rho)}{2 \sqrt{6 \log n + 2\log 2}} = \tilde{\Theta}(\rho)$. This map preserves the support of the planted dense subgraph in the row support of the planted matrix in $\textsc{BC}_R$. Then $\textsc{Random-Rotation}$ approximately maps from this $\textsc{BC}_R$ instance to a $\textsc{UBSPCA}_R(n, k, n, \theta)$ instance with $\theta = \frac{k^2 \mu^2}{\tau n} = \tilde{\Theta}\left( \frac{k^2 \rho^2}{n} \right)$. This map ensures that the planted vector $u$ is supported on the same indices as the original $\textsc{PDS}_R$ instance. Furthermore, the PDS conjecture is that the original $\textsc{PDS}_R$ instance is hard if $\rho^2 \ll \frac{n}{k^2}$ which corresponds to the barrier $\theta \ll 1$ under this reduction.

\begin{theorem} \label{thm:spcarec}
Let $\alpha \in \mathbb{R}$ and $\beta \in (0, 1)$. There is a sequence $\{ (N_n, K_n, D_n, \theta_n) \}_{n \in \mathbb{N}}$ of parameters such that:
\begin{enumerate}
\item The parameters are in the regime $d = \Theta(N)$, $\theta = \tilde{\Theta}(N^{-\alpha})$ and $K = \tilde{\Theta}(N^\beta)$ or equivalently,
$$\lim_{n \to \infty} \frac{\log \theta_n^{-1}}{\log N_n} = \alpha \quad \text{and} \quad \lim_{n \to \infty} \frac{\log K_n}{\log N_n} = \beta$$
\item If $\alpha > 0$ and $\beta > \frac{1}{2}$, then the following holds. Let $\epsilon > 0$ be fixed and let $X_n$ be an instance of $\textsc{UBSPCA}_R(N_n, K_n, D_n, \theta_n)$. There is no sequence of randomized polynomial-time computable functions $\phi_n : \mathbb{R}^{D_n \times N_n} \to \binom{[N_n]}{k}^2$ such that for all sufficiently large $n$ the probability that $\phi_n(X_n)$ is exactly the pair of latent row and column supports of $X_n$ is at least $\epsilon$, assuming the PDS recovery conjecture.
\end{enumerate}
Therefore, given the PDS recovery conjecture, the computational boundary for $\textsc{UBSPCA}_R(n, k, d, \theta)$ in the parameter regime $\theta = \tilde{\Theta}(n^{-\alpha})$ and $k = \tilde{\Theta}(n^\beta)$ is $\alpha^* = 0$ when $\beta > \frac{1}{2}$.
\end{theorem}

\begin{proof}
Suppose that $\alpha > 0$ and $\beta \ge \frac{1}{2}$. Let $\gamma =  \beta - \frac{1 - \alpha}{2} > 0$ and define
$$K_n = k_n = \lceil n^{\beta} \rceil, \quad \quad \rho_n = n^{-\gamma}, \quad \quad N_n = D_n = n, \quad \quad \mu_n = \frac{\log (1 + 2\rho_n)}{2 \sqrt{6 \log n + 2\log 2}}, \quad \quad \theta_n = \frac{k_n^2 \mu_n^2}{\tau n}$$
where $\tau$ is an arbitrarily slowly growing function of $n$. Let $\varphi_n = \textsc{SPCA-Recovery}$ be the reduction in Figure \ref{fig:randrot}. Let $G_n \sim G(n, S, 1/2 + \rho_n, 1/2)$ and $X_n = \varphi_n(G_n)$ where $S$ is a $k_n$-subset of $[n]$. Let $u_S$ denote the unit vector supported on indices in $S$ with nonzero entries equal to $1/\sqrt{k_n}$. Lemma \ref{lem:bcrec} and Lemma \ref{lem:randrot} together imply that
$$\TV\left( \mL(X_n), N\left( 0, I_n + \theta_n u_S u_S^\top \right) \right) \le O\left( \frac{1}{\sqrt{\log n}} \right) + \frac{2(n+3)}{\tau n - n - 3} \to 0 \text{ as } n \to \infty$$
Let $\mL_{n, S} = N\left( 0, I_n + \theta_n u_S u_S^\top \right)$. Assume for contradiction that there is a sequence of randomized polynomial-time computable functions $\phi_n$ as described above. Now observe that
$$\left| \bP_{X \sim \mL(X_n)} \left[ \phi_n(X) = S \right] - \bP_{X \sim \mL_{n, S}}\left[ \phi_n(X) = S\right]\right| \le \TV\left( \mL(X_n), \mL_{n, S} \right) \to 0 \text{ as } n \to \infty$$
Since $\bP_{X \sim \mL_{n, S}}\left[\phi_n(X) = S \right] \ge \epsilon$ for sufficiently large $n$, it follows that $\bP_{X \sim \mL(X_n)} \left[ \phi_n \circ \varphi_n(G_n) = S \right] = \bP_{X \sim \mL(X_n)} \left[ \phi_n(X) = S \right] \ge \epsilon/2$ for sufficiently large $n$. Furthermore observe
$$\lim_{n \to \infty} \frac{\log k_n}{\log n} = \beta \quad \text{and} \quad \lim_{n \to \infty} \log_n \left( \frac{k_n^2 \rho_n^2}{\frac{1}{4} - \rho_n^2} \right) = 2\beta - 2\gamma = 1 - \alpha < 1$$
Since the sequence of functions $\phi_n \circ \varphi_n$ can be computed in randomized polynomial time, this contradicts the PDS recovery conjecture. Therefore no such sequence of functions $\phi_n$ exists for the parameter sequence $\{ (N_n, K_n, D_n, \theta) \}_{n \in \mathbb{N}}$ defined above. As in Theorem \ref{thm:bcrec}, $\mu_n \sim \frac{\rho_n}{\sqrt{6 \log n}}$ as $n \to \infty$.
Therefore it follows that
$$\lim_{n \to \infty} \frac{\log \theta_n^{-1}}{\log N_n} = \lim_{n \to \infty} \frac{2\gamma \log n + \log (6\log n) + \log n - 2\beta \log n}{\log n} = \alpha \quad \text{and} \quad \lim_{n \to \infty} \frac{\log K_n}{\log N_n} = \beta$$
which completes the proof of the theorem.
\end{proof}

As is the case for $\textsc{BC-Recovery}$, the reduction $\textsc{SPCA-Recovery}$ also shows hardness for partial and weak recovery if the PDS recovery conjecture is strengthened to assume hardness of partial and weak recovery, respectively, for $\textsc{PDS}_R$.


TITLE: Relationship between an inhomogeneous Poisson process and Markov chain
QUESTION [2 upvotes]: What type of Markov process relates to an inhomogeneous Poisson process?
A homogeneous Poisson process-- one where the rate, $\lambda$, is constant-- is a pure birth continuous time Markov chain (with a constant birth rate). That is, if $q_{ij}$ is the transition rate then $q_{ij} = 0 $ unless $j=i+1$ i which case $q_i,i+1 = \lambda$
What happens when $\lambda = \lambda \left(t\right)$? Does, $q \rightarrow q\left(t\right)$? And, how is this represented in a transition matrix?
For a homogeneous Poisson process, the matrix of transition probabilities for the corresponding Markov process is one that is zero every where except the band immediately above the diagonal, all entries of which are $\lambda$.

REPLY [3 votes]: Well, let's try this... Let $\{N_{t}\}_{t\geq0}$ be an inhomogeneous Poisson process with rate function $\{\lambda(t)\}_{t\geq0}$. Let's try to compute the transition probabilites.
By definition of an inhomogeneous Poisson process, we have
$$P\{N(t+h)-N(t)=1\}=\lambda(t)h+o(h)$$
$$P\{N(t+h)-N(t)>1\}=o(h)$$
Since $\{N_{t}\}_{t\geq0}$ has independent increments by definition, we have
$$P\{N(t+h)-N(t)=1|N(t)=k\}=\lambda(t)h+o(h)$$
$$P\{N(t+h)-N(t)>1|N(t)=k\}=o(h)$$
for any $t\geq0$, any $k\in\mathbb{N}_{0}$ and "small" $h$.
Dividing previous equations by $h$, and letting $h\rightarrow 0$, we get
$$\lim_{h\rightarrow0}\frac{1}{h}P\{N(t+h)-N(t)=i+1|N(t)=i\}=\lambda(t)$$
$$\lim_{h\rightarrow0}\frac{1}{h}P\{N(t+h)-N(t)=j|N(t)=i\}=0$$
for $j>i+1$ or $j<i$.


TITLE: Quick way to determine existence of integral root of a polynomial in one variable
QUESTION [0 upvotes]: Suppose $p(x) \in \mathbb{Z}[x]$ and if there exist $b \in \mathbb{Z}$ s.t. $p(b)=0$, then $x-b|p(x)$. The other technique can be to put all $b \in \mathbb{Z}$.
But this require to check every $b \in \mathbb{Z}$ where $\mathbb{Z}$ is an infinite set.
So is there a quick way of determining whether or not there exist such $b \in \mathbb{Z}$.

REPLY [1 votes]: Suppose you have $p(x)=(x-b)f(x)$ for some polynomial $f(x)$...
Product of constant term of $f$ and $-b$ should be same as constant term of $p$.
Thus, $b$ should divide constant term...
So, it is enough to check for factors of $p(0)$..


TITLE: simplify boolean expression $(A \vee B) \wedge (\neg A \vee B)$ without truth table
QUESTION [0 upvotes]: How can I simplify $(A \vee B) \wedge (\neg A \vee B)$ (without a truth table)?
The result is $B$ but how can I show it?
Should I define $C := (A \vee B)$ and then use the distributive law?
$C \wedge (\neg A \vee B) \Leftrightarrow (C \wedge \neg A) \vee (C \wedge B) $
But after resubstitution it looks way more complicated.

REPLY [0 votes]: After resubstitution you get:
$((A \lor B) \land \neg A) \lor ((A \lor B) \land B) $
Well, that's more complicated, yes, but still not too hard. For example, we can now apply Distribution on the left term:
$(A \lor B) \land \neg A) \Leftrightarrow (A \land \neg A) \lor (B \land \neg A) \Leftrightarrow \bot \lor (B \land \neg A) \Leftrightarrow B \land \neg A$
Plugging that back in, we get:
$(B \land \neg A) \lor ((A \lor B) \land B) $
Now, what about the right side?  If you apply Distribuition here, you get:
$(A \lor B) \land B \Leftrightarrow (A \land B) \lor (B \land B) \Leftrightarrow (A \land B) \lor B$
... hmmm, that doesn't look too promising ... in fact, Distribution once more gets you to:
$(A \land B) \lor B \Leftrightarrow (A \lor B) \land (B \lor B) \Leftrightarrow (A \lor B) \land B$
... and we're back at where we were! ... OK, so that doesn't work.
Fortunately, here is something we can do:
$(A \lor B) \land B \Leftrightarrow (A \lor B) \land (\bot \lor B) \Leftrightarrow (A \land \bot) \lor B \Leftrightarrow \bot \lor B \Leftrightarrow B$
Aha!  So, plugging that back in, we get:
$(B \land \neg A) \lor B$
and now we can do a similar trick:
$(B \land \neg A) \lor B \Leftrightarrow (B \land \neg A) \lor (B \land \top) \Leftrightarrow B \land (\neg A \lor \top) \Leftrightarrow B \land  \top \Leftrightarrow B$
Now, the 'tricks' we did at the end actually reveal an important logical equivalence, known as:
Absorption
$P \land (P \lor Q) \Leftrightarrow P$
$P \lor (P \land Q) \Leftrightarrow P$
Also, the transformation at the beginning is known as:
Reduction
$P \land (\neg P \lor Q) \Leftrightarrow P \land Q$
$P \lor (\neg P \land Q) \Leftrightarrow P \lor Q$
So, with those, let's do the whole transformation again:
$((A \lor B) \land \neg A) \lor ((A \lor B) \land B) \overset{Reduction, Absorption}{\Leftrightarrow} (B \land \neg A) \lor B \overset{Absorption}{\Leftrightarrow} B$
Finally, though, I want to point out that the Distribution equivalence works both ways (it's an equivalence, remember?), so you could have done a 'Reverse' Distribution on your very original expression:
$(A \lor B) \land (\neg A \lor B) \overset{Distribution}{\Leftrightarrow} (A \land \neg A) \lor B \Leftrightarrow \bot \lor B \Leftrightarrow B$
And that equivalence actually has its own name as well:
Adjacency
$(P \lor Q) \land (P \lor \neg Q) \Leftrightarrow P$
$(P \land Q) \lor (P \land \neg Q) \Leftrightarrow P$
And with that, we can rework your transformation one more time:
$(A \vee B) \wedge (\neg A \vee B) \overset{Adjacency}{\Leftrightarrow}B$
Done!
But here's the moral: Put Absorption, Reduction, and Adjacency immediately into your 'Boolean Algebra Tool Box': they are very useful!


TITLE: solving logarithmic expression
QUESTION [2 upvotes]: I need to solve logarithmic equation that contains a variable inside and outside the logarithm. I want to solve the following equation for x:
$$x= \frac{(\log_2(1+2x)) \cdot (1+2x)}{4}-5 $$
Note1: The base of logarithm is $2$.
Note2: The equation is supposed to be closed form.
Note3: The constant values are not important and can be changed.

REPLY [0 votes]: The equation is equivalent to the equation $f(x)=0$ where
$$ f(x)=\log_2(1+2x)-\frac{20+4x}{1+2x} $$
where $x>-\frac12$. Note that
$$ f'(x)=\frac{2+4x+36\log2}{(1+2x)^2\log2}>0, x>-\frac12 $$
Namely $f(x)$ is increasing when $x>-\frac12$. Since $f(0)=-5$ and $f(6)=0.315824$, $f(x)=0$ has a unique solution by the IVT.


TITLE: Evaluating $\lim\limits_{(x,y) \rightarrow (0,0)} \frac{x^3 - y^3}{x^2 + y^2}$
QUESTION [4 upvotes]: I have tried approaching the limit from different functions like $x = 0$, $y = 0$, $y = x$, $y = x^2$, etc. But they all go to $0$, so my guess would be that the limit goes to $0$, but how do I show that the limit is definitely $0$?

REPLY [8 votes]: There is the ever-popular method of converting the expression into polar form, which will point out quickly if the effort to find the limit suffers from "directionality":
$$ \ \frac{x^3 \ - \ y^3}{x^2 \ + \ y^2} \ \ \rightarrow \ \ \frac{r^3 \ (\cos^3  \theta \ - \ \sin^3  \theta)}{r^2} \ = \ r \ (\cos^3  \theta \ - \ \sin^3  \theta) \  .  $$
This will approach zero from any direction $ \ \theta \ $ as $ \ r \ \rightarrow \ 0 \ $ .


TITLE: Why the chemical potential of phonon gas in Einstein 's solid model is not zero
QUESTION [1 upvotes]: In Einstein’s model of solid, each atom in the solid is considered to be an independent three-dimensional quantum harmonic oscillator with characteristic frequency $ω$ that is constant. Each degree of freedom as a separate one-dimensional harmonic oscillator and the energy levels are familiar: $ E_n=(n+1/2)ℏω $. Ignoring the zero-point energy as an irrelevant constant term, we take the energy levels as $E_n= n ℏω $. The partition function for a single 1d oscillator is: $Z_1=1/(1−\exp(−βℏω))$. The mean number of phonon is $<n>=1/(\exp(βℏω)−1)$. It is clearly the Bose-Einstein statistics with zero chemical potential.
However, the free energy is: $$F=−3Nβ^{−1} \log Z_1=3Nβ^{−1}\log(1−\exp(−βℏω)).$$ The chemical potential $$μ=F/N=3 β^{−1}\log(1−\exp(−βℏω)) $$ which is nonzero. This nonzero chemical potential is given in many textbooks (such as Pathria 3rd ed, Pauli, etc.) to discuss the solid-vapor phase transition.

Major question: Why the chemical potential of phonon gas in Einstein 's solid model is not zero?
Minor question: In Einstein’s model of solid, the pressure is zero. But during the solid-vapor phase transition, the vapor pressure is never zero! The condition for phase transition requires that the solid pressure is equal to vapor pressure.

REPLY [2 votes]: The energy of a system of many interacting particles is often approximated by the energy of a system of noninteracting quasiparticles. Then the partition function of a system of physical particles is equal to the grand partition function of a system of quasiparticles with zero chemical potential. Particles and quasiparticles should be distinguished. The number of physical particles $N$ is fixed, but the mean number of quasiparticles depends on the temperature. So the number of phonons in the Einstein solid is not equal to $N$ nor to $3N$.
The chemical potential of a system of physical particles is $\partial F/\partial N \neq 0$.
I think there are mistakes in your formulas. First, the zero-point energy is finite in this model due to the finite number of oscillators. This energy is usually taken into account. Second, you need the chemical potential of a physical system of $N$ atoms, not the chemical potential of a system of $3N$ imaginary oscillators. Hence the right formula is $\mu = F/N$, not $\mu = F/(3N)$.