TITLE: $f^{-1}(\{w_{0}\})$ is a linear subspace of $V$ iff $w_0 = 0$
QUESTION [0 upvotes]: We have two $K$-Vectorspaces $V, W$ and $f \in L(V,W)$
Let $w_0 \in Image(f)$ such that $f^{-1}(\{w_{0}\}) := \{v \in V \ | \ f(v) = w_0\}$
First I have proved that $f^{-1}(\{w_{0}\})$ is an affine subspace of $V$ by showing that for $v_0 \in f^{-1}(\{w_{0}\})$
$U := f^{-1}(\{w_{0}\}) - v_0$ is a linear subspace of $V$
Now I would like to prove: $f^{-1}(\{w_{0}\})$ is a linear subspace of $V$ iff $w_0 = 0$
On one direction, if $w_0 = 0$ then is $Kern(f)$ a subspace of $V$.
How would I go about the other direction? and why should this statement be true?

REPLY [2 votes]: Hint : If $f^{-1}(\{w_0\})$ is a vector subspace of $V$, it must contain $0$.


text:
\clearpage
\appendix

\section{Proof of Theorem 4.1}\label{app:proof}
\begin{proof}
We show that both of the two terms in \cref{eq:wreath_prod_w} are equivariant to $\Kg \wr \Hg$-action as expressed by the
permutation matrix of \cref{eq:wreath_perm_matrix}.
\paragraph{Part 1.} We show that ${\Gm\ly{\gg}}$ commutes with the first term in \cref{eq:wreath_prod_w} for any $\gg \in \Kg \wr \Hg$:
\begin{align}
    \left (\Wm_\Hg \otimes (\vec{1}_Q \vec{1}^\top_Q) \right) {\Gm\ly{\gg}} &= \left (\Wm_\Hg \otimes (\vec{1}_Q \vec{1}^\top_Q) \right)
     \left (\sum_{p=1}^P \mat{1}_{p,\hg \cdot p} \otimes \Gm\ly{\kg_p}\right) \label{eq:p1} \\
    &= \sum_{p=1}^P \left ( \Wm_\Hg \mat{1}_{p,\hg \cdot p} \right ) \otimes
    \overbrace{\left ( (\vec{1}_Q \vec{1}^\top_Q)  \Gm\ly{\kg_p} \right )}^{= (\vec{1}_Q \vec{1}^\top_Q)} \label{eq:p2} \\
    & = \Wm_\Hg \left (\sum_{p=1}^P \mat{1}_{p,\hg \cdot p} \right ) \otimes (\vec{1}_Q \vec{1}^\top_Q) \label{eq:p3} \\
    &= (\Wm_\Hg \Gm\ly{\hg}) \otimes  (\vec{1}_Q \vec{1}^\top_Q)  = ( \Gm\ly{\hg} \Wm_\Hg) \otimes (\vec{1}_Q \vec{1}^\top_Q) \label{eq:p4}\\
    &= \sum_{p=1}^P \left ( \mat{1}_{p,\hg \cdot p} \Wm_\Hg \right) \otimes \left ( (\vec{1}_Q \vec{1}^\top_Q)  \Gm\ly{\kg_p} \right ) \\
    &= \sum_{p=1}^P  \left (\mat{1}_{p,\hg \cdot p} \otimes \Gm\ly{\kg_p}\right)
     \left (\Wm_\Hg \otimes (\vec{1}_Q \vec{1}^\top_Q) \right) \label{eq:p5} \\
    & = \left (\sum_{p=1}^P \mat{1}_{p,\hg \cdot p} \otimes \Gm\ly{\kg_p}\right)
     \left (\Wm_\Hg \otimes (\vec{1}_Q \vec{1}^\top_Q) \right) = {\Gm\ly{\gg}} \left (\Wm_\Hg \otimes (\vec{1}_Q \vec{1}^\top_Q) \right). \label{eq:p6}
\end{align}
In \cref{eq:p1} we substitute from \cref{eq:wreath_perm_matrix}. In \cref{eq:p2} we pulled the summation out, and then used the mixed product property of Kronecker product. We also note that a permutation of the uniformly constant matrix $\vec{1}_Q \vec{1}^\top_Q$ is constant. In \cref{eq:p3}, since the summation can be restricted to the first term we pull out $\Wm_\Hg$. In \cref{eq:p4} we use the fact that the summation of the previous line is the permutation matrix
$\Gm\ly{\hg}$ and apply the key assumption that $\Wm_\Hg$ and $\Wm_\Kg$ are equivariant to $\Hg$ and $\Kg$-action respectively. The following lines repeat the procedure so far in reverse order to commute ${\Gm\ly{\gg}}$ and
$\left (\Wm_\Hg \otimes (\vec{1}_Q \vec{1}^\top_Q) \right)$.

\paragraph{Part 2.} For the second term, again we use the mixed-product property and
equivariance of the input maps
\begin{align}
    \left ( \mat{I}_P \otimes \Wm_\Kg \right) {\Gm\ly{\gg}} &= \left ( \mat{I}_P \otimes \Wm_\Kg\right)
     \left (\sum_{p=1}^P \mat{1}_{p,\hg \cdot p} \otimes \Gm\ly{\kg_p}\right) \label{eq:p10} \\
     &=  \sum_{p=1}^P \left (\mat{I}_P \mat{1}_{p,\hg \cdot p} \right ) \otimes
     \left ( \Wm_\Kg \Gm\ly{\kg_p}\right) \label{eq:p11} \\
     &= \sum_{p=1}^P \left (\mat{1}_{p,\hg \cdot p} \mat{I}_P  \right ) \otimes
     \left ( \Gm\ly{\kg_p} \Wm_\Kg \right) \label{eq:p12} \\
     &= \sum_{p=1}^P \left ( \mat{1}_{p,\hg \cdot p} \otimes \Gm\ly{\kg_p}\right)
     \left ( \mat{I}_P \otimes \Wm_\Kg\right) = {\Gm\ly{\gg}}  \left ( \mat{I}_P \otimes \Wm_\Kg \right) \label{eq:p13}
     \end{align}
     where in \cref{eq:p12} we used the fact that the identity matrix commutes with any matrix, as well as the equivariance of
$\Gm\ly{\kg_p}$. \cref{eq:p11,eq:p13} simply use the mixed product property.
Putting the two parts together shows the equivariance of the first and second term in \cref{eq:wreath_prod_w}, completing the proof.
\end{proof}

\subsection{Proof of Maximality}
Previously we proved that the linear maps of \cref{eq:wreath_prod_w} is
equivariant to imprimitive action of wreath product $\Kg \wr \Hg$ given by
\cref{eq:wreath_perm_matrix}. Here, we prove that any $\Kg \wr \Hg$
equivariant linear map has this form.

\begin{claim}
Assuming that any $\Kg$-equivariant ($\Hg$-equivariant) linear map $\Wm_\Kg$ ($\Wm_\Hg$) can be written as a linear combination of $K$ ($H$) independent linear operators, then any $W_{\Kg \wr \Hg}$ as defined in \cref{eq:wreath_prod_w} is a linear combination of $K+H-1$ independent linear bases.
 \end{claim}
 \begin{proof}
Consider the two terms
(I) $\Wm_\Hg \otimes (\vec{1}_Q \vec{1}^\top_Q)$ and (II) $\mat{I}_P \otimes \Wm_\Kg$ in \cref{eq:wreath_prod_w}, where (I) has $H$ independent bases and (II) has $K$ independent bases. If they had independent bases, their summation would have $K+H$ linear bases. However, (I) and (II) have exactly one shared basis: $\Wm_\Hg = \mathbf{I}_P$ is $\Hg$-equivariant, and $\Wm_\Kg = \vec{1}_Q \vec{1}^\top_Q$ is $\Kg$-equivariant. Therefore,  $\mathbf{I}_P \otimes (\vec{1}_Q \vec{1}^\top_Q)$ is a basis for both (I) and (II).
 \end{proof}

Next, we show that any $\Kg \wr \Hg$-equivariant linear map
 can be written using as a weighted sum of $K+H-1$ independent linear operators. Together with proof of equivariance of $\Wm_{\Kg \wr \Hg}$ these two facts prove that any $\Kg \wr \Hg$
equivariant linear map has the form of \cref{eq:wreath_prod_w}.

\begin{claim}
Any linear map that is equivariant to the imprimitive action of $\Kg \wr \Hg$
can  a linear combination of $K+H-1$ equivariant linear bases.
\end{claim}
\begin{proof}
Let $\Wm \in \Reals^{N \times N}$ be the matrix representing this equivariant map, satisfying
$\Wm \Gm^{\gg} = \Gm^{\gg}  \Wm \quad \forall \gg \in \Kg \wr \Hg$. Since $\Gm^{{\gg}^\top} \Wm \Gm^{\gg} =  \Wm \quad \forall \gg \in \Kg \wr \Hg$, all elements of the matrix $\Wm$ that are in the same orbit are tied together. This constraint means that the number of unique values in $\Wm$ are equal to the number of orbits in this simultaneous action on rows and columns of $\Wm$. Using a property of Kronecker product, we can also write the equation above as $\operatorname{vec}(\Gm^{\gg} \Wm \Gm^{{\gg}^\top}) = (\Gm^{\gg} \otimes  \Gm^{\gg}) \operatorname{vec}(\Wm)$. Therefore, the diagonal group action is given by $\Gm^{\gg} \otimes  \Gm^{\gg}$.
Using \emph{Burnside's lemma} we get the number of orbits $L$ in this action to be
\begin{align}\label{eq:burnside}
    L = \frac{1}{|\Gg|} \sum_{\gg \in \Kg \wr \Hg} \Tr(\Gm^{(\gg)} \otimes  \Gm^{(\gg)}) = \sum_{\gg \in \Kg \wr \Hg} \Tr(\Gm^{(\gg)})^2
\end{align}
Our objective is to show that $L = H+K-1$. Our strategy is to replace the definition of $\Gm^\gg$ from \cref{eq:wreath_perm_matrix} into \cref{eq:burnside} and simplify. This simplification involves numerous steps.
\begin{align}
    L & = \frac{1}{|\Hg| |\Kg|^P} \sum_{\hg \in \Hg, \kg_{1}, \ldots, \kg_{P} \in \Kg} \Tr \left (\sum_{p=1}^P \mathbf{1}_{p, \hg \cdot p} \otimes \Gm^{(\kg_p)} \right)^2 \label{pr:1}\\
     & = \frac{1}{|\Hg| |\Kg|^P} \sum_{\hg \in \Hg, \kg_{1}, \ldots, \kg_{P} \in \Kg}  \Tr \left(\sum_{p=1}^P \Gm^{(\hg)}_{p,p} \Gm^{(\kg_p)} \right)^2 \label{pr:2} \\
     & = \frac{1}{|\Hg| |\Kg|^P}  \sum_{\hg \in \Hg, \kg_{1}, \ldots, \kg_{P} \in \Kg}
     \left ( \sum_{p=1}^P \Gm^{(\hg)}_{p,p} \Tr \left ( \Gm^{(\kg_p)} \right )    \right)
     \left ( \sum_{p'=1}^P \Gm^{(\hg)}_{p',p'} \Tr \left ( \Gm^{(\kg_{p'})} \right )    \right) \label{pr:3} \\
     & = \frac{1}{|\Hg| |\Kg|^P} \sum_{\hg \in \Hg, \kg_{1}, \ldots, \kg_{P} \in \Kg}
     \left (\sum_{p=1}^P \Gm^{(\hg)}_{p,p} \Tr \left ( \Gm^{(\kg_p)} \right )^2 \right) + \notag \\
     & \left ( \sum_{p=1}^P \sum_{p'\neq p, p'=1}^P  \Gm^{(\hg)}_{p,p}  \Gm^{(\hg)}_{p',p'}
     \Tr \left ( \Gm^{(\kg_p)} \right ) \Tr \left ( \Gm^{(\kg_{p'})} \right ) \right ) \label{pr:4}
\end{align}
where in \cref{pr:2} we observed that the contribution from $\Gm^{(\kg_p)}$ to the trace of $\Gg^{(\gg)}$ is non-zero only if $\Gm^{(\hg)}_{p,p} = 1$. Note that all the $\Gm$ matrices are permutation matrices and in the following we will continue to use this fact without elaborating. In \cref{pr:3} we used linearity of trace, and in \cref{pr:4} we divided the product of the previous line into $p=p'$ and $p \neq p'$. As we show below, the first term simplifies to $K$ and the second terms simpliefies to $H-1$, showing that $L = K +H -1$.
We start by simplifying the first term of \cref{pr:4} below:
\begin{align}
    & \frac{1}{|\Hg| |\Kg|^P} \sum_{\hg \in \Hg, \kg_{1}, \ldots, \kg_{P} \in \Kg}
     \left (\sum_{p=1}^P \Gm^{(\hg)}_{p,p} \Tr \left ( \Gm^{(\kg_p)} \right )^2 \right) \\
     = & \frac{1}{|\Hg| |\Kg|^P} \sum_{p=1}^P \left (\sum_{\hg \in \Hg} \Gm^{(\hg)}_{p,p} \right) \left( \sum_{\kg_{1}, \ldots, \kg_{P} \in \Kg} \Tr(\Gm^{(\kg_p)})^2 \right) \\
     = & \frac{1}{|\Hg| |\Kg|^P} \left (\sum_{\hg \in \Hg}  \sum_{p=1}^P \Gm^{(\hg)}_{p,p} \right) \left (|\Kg|^{P-1} \sum_{\kg \in \Kg} \Tr(\Gm^{(\kg)})^2 \right) \\
     = & \frac{1}{|\Hg| |\Kg|^P} \left (\sum_{\hg \in \Hg}  \Tr(\Gm^{(\hg)}) \right)
     \left (|\Kg|^{P-1} |\Kg| K \right) \label{pr:5} \\
     = & \frac{1}{|\Hg| |\Kg|^P} |\Hg| |\Kg|^P K = K \label{pr:6}
\end{align}
where beside simple algebra, in \cref{pr:5}, we used the Burnside lemma on $\Wm_{\Kg}$, which gives us the number of unique parameters (orbits) as $K = \frac{1}{|\Kg|} \sum_{\kg \in \Kg} \Tr(\Gm^{(\kg)})^2$.
Similarly for $\Hg$-action we get $\frac{1}{|\Hg|} \sum_{\hg \in \Hg} \Tr( \Gm^{(\hg)})^2 = H$.
In \cref{pr:6} we used the fact that $\Hg$ action on $\set{P}$ is transitive (\ie it has a single orbit), to get
$ |\Hg| = \sum_{\hg \in \Hg} \Tr(\Gm^{(\hg)})$. Similarly, due to transitivity of $\Kg$-action on $\set{Q}$
we have $ |\Kg| = \sum_{\kg \in \Kg} \Tr(\Gm^{(\kg)})$.
Next, we use these same equalities to simplify the second term of \cref{pr:4}:
\begin{align}
    & \frac{1}{|\Hg| |\Kg|^P}  \sum_{\hg \in \Hg, \kg_{1}, \ldots, \kg_{P} \in \Kg} \sum_{p=1}^P \sum_{p'\neq p, p'=1}^P  \Gm^{(\hg)}_{p,p}  \Gm^{(\hg)}_{p',p'}
     \Tr \left ( \Gm^{(\kg_p)} \right ) \Tr \left ( \Gm^{(\kg_{p'})} \right ) \\
     = & \frac{1}{|\Hg| |\Kg|^P} \sum_{p=1}^P \sum_{p'\neq p, p'=1}^P \left ( \sum_{\hg \in \Hg} \Gm^{(\hg)}_{p,p}  \Gm^{(\hg)}_{p',p'}  \right )
     \left ( |\Kg |^{P-2} \left (\sum_{\kg \in \Kg} \Tr(\Gm^{(\kg_{p'})} \right )^2 \right) \\
     = &  \frac{1}{|\Hg| |\Kg|^P} \left ( \sum_{\hg \in \Hg}
     \left (  \sum_{p=1}^P \sum_{p'=1}^P \Gm^{(\hg)}_{p,p}  \Gm^{(\hg)}_{p',p'} \right) - \left (  \sum_{p=1}^P  \Gm_{p,p}^{{(\hg)}^2} \right )
     \right ) \left (
     |\Kg|^{P-2} |\Kg|^2
     \right ) \\
     & = \frac{1}{|\Hg|} \sum_{\hg \in \Hg} \left ( \sum_{p=1}^P  \Gm^{(\hg)}_{p,p}  \right ) \left ( \sum_{p'=1}^P  \Gm^{(\hg)}_{p',p'}  \right ) -  \left (  \sum_{p=1}^P  \Gm^{(\hg)}_{p,p} \right ) \\
     & = \frac{1}{|\Hg|} \sum_{\hg \in \Hg} \Tr( \Gm^{(\hg)})^2 -  \Tr( \Gm^{(\hg)})
      = H - 1 \label{pr:7}.
\end{align}
\cref{pr:6,pr:7} together with \cref{eq:burnside} show that $L = H + K -1$, that any linear map $\Wm_{\Gg}$ equivariant to imprimitive action of
$\Kg \wr \Hg$, can be written using $H+K-1$ independent linear bases. Considering this proof together with our proof for the first part (that the equivariant map of \cref{eq:wreath_prod_w} has $H+K-1$ independent linear bases) completes the proof that any $\Kg \wr \Hg$-equivariant linear map is of the form \cref{eq:wreath_prod_w}.
\end{proof}

\section{Adaptive Pooling and Attention}\label{app:attention}
While the layer of \cref{eq:conv} performs competitively, to improve its performance we add a novel attention mechanism.  To this end we complement the pool-and-broadcast scheme of \cref{eq:conv} with an adaptive pooling mechanism using a learned $\tilde{\Pi}: \Reals^{N} \to \Delta_{L}$ in \cref{eq:conv}, where $\Delta_L$ is the $L$-dimensional probability simplex. Here, one may interpret $L$ as the number of \emph{latent classes}, analogous to $D^3$ voxels.
The pooling matrix $\tilde{\Pi}$, is a function of input through a linear map $\W_3\ly{\ell} \in \Reals^{C \times L}$ followed by $\mathrm{Softmax}:\Reals^{L} \to (0,1)^{L}$, so that the probability of each point belonging to different classes sums to one -- that is
\begin{align}
    \tilde{\Pi}_{n} = \mathrm{Softmax}\left( (\Xm \Wm_{3})_{n} \right ) \forall n \in [N].
\end{align}

We then use a linear function that models the interaction between latent classes, for each pair of channels. This is done using a rank four tensor $\W_{4} \in \Reals^{L \times L \times C \times C}$. As before the result is broadcasted back using $\tilde{\Pi}_n^\top$, giving us the adaptive pooling layer, in which the output for channel $c$ is given by
\begin{align}\label{eq:attn}
    \phi(\Xm)_c = \sum_{c' = 1}^{C'}{\tilde{\Pi}^\top} \W_{4,c,c'} \tilde{\Pi} \X_c.
\end{align}
Intuitively this layer can decide which subset of nodes to pool, and therefore acts like an equivariant attention mechanism.
In experiments, we see further improvement in results when adding this nonlinear layer to the linear layer of \cref{eq:conv}.

\section{Details on Experiments}\label{app:experiments}

 \subsection{Architecture and Data Processing}
 Our results are produced using minor architectural variations and limited hyperparameter search. Concretely, our best-performing models on \kw{Semantic3D} and \kw{S3DIS} involve 56 residual-style blocks, where each block comprises of 2 equivariant linear maps of \cref{eq:conv}. Each map involves a single 3D convolution operator with periodic padding and a $3 \times 3 \times 3$ kernel. We use an identity map to facilitate skip connections within these blocks. The number channels is fixed 64, except the final block, which maps to the number of segmentation classes (8 for \kw{Semantic3D} and 13 for \kw{S3DIS}). When incorporating adaptive pooling, we utilize 5, 10, 15, 25 and 50 latent classes $L$ for blocks 1-19, 19-29, 30-39, 40-49 and 50-56, respectively and inclusively. Our best-performing model on \kw{vKITTI} uses 22 such residual-style blocks with identical architectural hyperparameters. For adaptive pooling, we then use 5, 10, 15, and 20 latent classes for blocks 1-9, 10-14, 15-19, and 20-22, respectively and inclusively.

Additionally, while previous works rely on stochastic point cloud subsampling during pre-processing and reprojection during post-processing, we simply split large point clouds into subsets of 1 million points each to ameliorate memory issues. We then compute a $9 \times 9 \times 9$ voxelization over each sample, and train on mini-batches of 4 such samples. To generate predictions, we stitch predictions on these smaller samples together.

\subsection{Datasets: Training, Validation and Test}
\paragraph{Outdoor Scene Segmentation -  \kw{semantic3d}
\kw{Semantic3D} \cite{hackel2017semantic3d}}   We hold out 4 of the available 15 training point clouds to use as a validation set, as in \cite{landrieu2018large}.

\begin{figure*}[ht!]
\begin{center}
\includegraphics[width=\columnwidth]{figures/sem8_seg_results_zoomed_sota}
\caption{(\textbf{top left}) RGB scan of a point cloud with 280 994 028 points from the  \kw{semantic3d} dataset;
(\textbf{middle left}) segmentation results from our method;
(\textbf{bottom left}) ground truth segmentation;
(\textbf{top right}) RGB scan of a point cloud with 19 767 991 points from the  \kw{semantic3d} dataset.
(\textbf{middle right}) segmentation results from our method;
(\textbf{bottom right}) ground truth segmentation;}
\label{sem8-sota}
\end{center}
\vskip -0.05 in
\end{figure*}

\cref{tab:semantic3d} reports the overall accuracy (OA), and mean intersection over union (mIoU) for our method and the competition. We achieve both the best overall accuracy as well as the best mean intersectio over union.

\begin{table*}[ht]
\centering
\footnotesize
\scalebox{.67}{
\begin{tabulary}{0.4\linewidth}{l|cc|c|c|c|c|c|c|c|cr}
\toprule
Method & \textbf{OA} & \textbf{mIoU} & \makecell{Man-Made \\ Terrain}  & \makecell{Natural \\ Vegetation} &  \makecell{High \\ Vegetation} & \makecell{Low \\ Vegetation} & Buildings & Hardscape & \makecell{Scanning \\ Artifacts} & Cars \\
\midrule
\kw{DeepSets}\cite{zaheer2017deep} & 89.3 & 60.5 & 90.8 & 76.3 & 41.9 & 22.1 & 94.0 & 46.5 & 26.8 & 85.4 \\
\kw{PointNet}\cite{qi2017pointnet} & 85.7 & 63.1 & 81.9 & 78.1 & 64.3 & 51.7 & 75.9 & 36.4 & 43.7 & 72.6 \\
\kw{SnapNet}\cite{boulch2018snapnet} & 91.0 & 67.4 & 89.6 & 79.5 & 74.8 & 56.1 & 90.9 & 36.5 & 34.3 & 77.2 \\
\kw{SPG}\cite{landrieu2018large} & 92.9 & 76.2 & 91.5 & 75.6 & \textbf{78.3} & 71.7 & 94.4 & \textbf{56.8} & 52.9 & 88.4 \\
\kw{ConvPoint}\cite{boulch2019generalizing} & 93.4 & 76.5 & 92.1 & 80.6 & 76.0 & \textbf{71.9} & 95.6 & 47.3 & \textbf{61.1} & 87.7 \\
\midrule
\vox & 93.9 & 75.4 & 93.4 & 84.0 & 76.4 & 68.2 & 96.8 & 45.6 & 47.4 & 91.9 \\
\comb & \textbf{94.6} & \textbf{77.1} & \textbf{95.2} & \textbf{87.1} & 75.3 & 67.1 & \textbf{96.1} & 51.3 & 51.0 & \textbf{93.4} \\
\bottomrule
\end{tabulary}
}
\caption{Performance of various models on the \emph{full}  \kw{semantic3d} dataset (semantic-8). Higher is better, bolded is best. mIoU is unweighted mean intersection over union metric. OA is overall accuracy. Per class splits show mIoU.}
\label{tab:semantic3d}
\end{table*}

\paragraph{Indoor Scene Segmentation - Stanford Large-Scale 3D Indoor Spaces (\kw{S3DIS})}
The  \kw{s3dis} dataset \cite{armeni20163d} consists of various 3D RGB point cloud scans from an assortment of room types on six different floor in three buildings on the Stanford campus, totaling almost 600 million points. Following previous works by \cite{qi2017pointnet, qi2017pointnet++, engelmann2017exploring, tchapmi2017segcloud, landrieu2018large}, we perform 6-fold cross validation with micro-averaging, computing all metrics once over the merged predictions of all test folds.

Here, we achieve the best overall accuracy as well as mean intersection over union.
This is in spite of the fact that our competition use extensive data-augmentation also for this dataset.
In particular, both \kw{KPConv} and \kw{ConvPoint} use random jittering and subsampling.

\begin{table*}[ht!]
\scalebox{.55}{
\begin{tabulary}{0.4\textwidth}{l|cc|c|c|c|c|c|c|c|c|c|c|c|c|cr}
\toprule
Method & \textbf{OA} & \textbf{mIoU} & Ceiling & Floor & Wall & Beam & Column & Window & Door & Chair & Table & Bookcase & Sofa & Board & Clutter \\
\midrule
\kw{DeepSets}\cite{zaheer2017deep} & 67.3 & 42.7 & 81.1 & 72.4 & 67.2 & 16.9 & 25.8 & 44.2 & 48.5 & 51.0 & 49.8 & 21.7 & 24.4 & 17.2 & 34.6  \\
\kw{PointNet}\cite{qi2017pointnet} & 78.5& 47.6 &88.0 & 88.7 & 69.3 & 42.4 & 23.1 & 47.5 & 51.6 & 42.0 & 54.1 & 38.2 & 9.6 & 29.4 & 35.2 \\
\kw{RSNet}\cite{huang2018recurrent} & N/A & 56.5 & 92.5 & 92.8 & 78.6 & 32.8 & 34.4 & 51.6 & 68.1 & 60.1 & 59.7 & 50.2 & 16.4 & 44.9 & 52.0 \\
\kw{PCCN}\cite{wang2018deep} & N/A & 58.3 & 92.3 & 96.2 & 75.9 & 0.27 & 6.0 & 69.5 & 63.5 & 65.6 & 66.9 & 68.9 & 47.3 & 59.1 & 46.2 \\
\kw{SPG}\cite{landrieu2018large} & 85.5 & 62.1 & 89.9 & 95.1 & 76.4 & 62.8 & 47.1 & 55.3 & 68.4 & 73.5 & 69.2 & 63.2 & 45.9 & 8.7 & 52.9 \\
\kw{ConvPoint}\cite{boulch2019generalizing} & 88.8 & 68.2 & 95.0 & \textbf{97.3} & 81.7 & 47.1 & 34.6 & 63.2 & 73.2 & \textbf{75.3} & \textbf{71.8} & 64.9 & 59.2 & 57.6 & 65.0 \\
\kw{KP-FCNN}\cite{thomas2019kpconv} & N/A & 70.6 & 93.6 & 92.4 & 83.1 & 63.9 & 54.3 & 66.1 & 76.6 & 57.8 & 64.0 & 69.3 & \textbf{74.9} & 61.3 & 60.3  \\
\midrule
\vox & 90.6 & 71.2 & 94.3 & 96.7 & 80.6 & 65.0 & 76.2 & 62.1 & 71.9 & 64.3 & 62.7 & 60.2 & 68.8 & 63.5 & 59.9 \\
\comb & \textbf{95.8} & \textbf{80.1} & \textbf{97.2} & \textbf{97.8} & \textbf{88.6} & \textbf{72.3} & \textbf{82.0} & \textbf{73.6} & \textbf{78.6} & \textbf{75.1} & \textbf{72.0} & \textbf{73.1} & 71.4 & \textbf{82.1} & \textbf{77.2} \\
\bottomrule
\end{tabulary}
}
\caption{Performance of various models on the \kw{s3dis} dataset (micro-averaged over all 6 folds). Higher is better, bolded is best. mIoU is unweighted mean intersection over union metric. OA is overall accuracy. Per class splits show mIoU.}
\label{tab:s3dis}
\end{table*}

\subsection{Virtual Scene Segmentation - Virtual KITTI}
The \kw{vKITTI} dataset \cite{gaidon2016virtual} contains 35 monocular photo-realistic synthetic videos with fully annotated pixel-level labels for each frame and 13 semantic classes in total. Following \cite{engelmann2017exploring}, we project the 2D depth information within these synthetic frames into 3D space, thereby obtaining semantically annotated 3D point clouds. Similar to the training and evaluation scheme in \cite{landrieu2019point, engelmann2017exploring}, we separate the original set of sequences into 6 non-overlapping subsequences and use a 6 fold cross-validation protocol (with micro-averaging similar to the methodology on \kw{S3DIS}).

\begin{table*}[ht]
\centering
\scalebox{.7}{
\begin{tabulary}{0.4\textwidth}{l|c|c|cr}
\toprule
Method & OA & mIoU & mAcc \\
\midrule
\kw{DeepSets}\cite{zaheer2017deep} & 74.2 & 42.9 & 36.8 \\
\kw{PointNet}\cite{qi2017pointnet} & 79.7 & 34.4 & 47.0 \\
\kw{Engelmann et al. 2018}\cite{engelmann2018know} & 79.7 & 57.6 & 35.6 \\
\kw{Engelmann et al. 2017}\cite{engelmann2017exploring} & 80.6 & 54.1 & 36.2 \\
\kw{3P-RNN}\cite{ye20183d} & 87.8 & 54.1 & 41.6 \\
\kw{SPG}\cite{landrieu2019point} & 84.3 & 67.3 & 52.0 \\
\midrule
\vox & 88.4 & 68.9 & 58.6 \\
\comb & \textbf{90.7} & \textbf{69.5} & \textbf{59.2} \\
\bottomrule
\end{tabulary}
}
\vskip 0.1 in
\caption{Performance of various models on the \kw{vKITTI} dataset (micro-averaged over all 6 folds). Higher is better, best results are in bold. mIoU is unweighted mean intersection over union metric. OA is overall accuracy. mAcc is mean accuracy.}
\label{tab:vkitti}
\end{table*}

Note that \kw{vKITTI} is significantly smaller than either \kw{Semantic3D} or \kw{S3DIS}, containing only 15 millions points in total. We hypothesize that these smaller, and sparser point clouds provide little geometric signal outside vegetation and road structure. This partially explains our only incremental improvement over the state of the art (see Table \ref{tab:vkitti}). However, we expect future simulations of point cloud scenes to become increasingly dense, in line with increasingly powerful LiDAR scanners for real world applications \cite{fang2018simulating, sadakuni2019construction}, where our simple baselines can potentially produce significant gain both in accuracy and computation.

config: arxiv


TITLE: Circular cylinder $S=\{ (x,y,z) : x^2+y^2=1 \}$ can be covered with a single surface patch.
QUESTION [3 upvotes]: I somewhere found that we can take $U$ an annulus instead of a disc
where
$U=\{ (u,v): 0 < u^2+v^2 < π \}$. Can anyone please explain me that how a cylinder can be covered with a single surface patch from $U$?

REPLY [0 votes]: Parametrization
EDIT1:
For Cylinder
$$ a=1 ; $$
$$ (a \cos u, a \sin u, v),(u,0, 2 \pi),(v,v1,v2) $$
where z coordinate is depth or height of cylinder between two limits.
For Annulus
$$ a=1 ; $$
$$ (a v  \cos u, a v  \sin u, 0 ),(u,0, 2 \pi),(v,v1,v2) $$


TITLE: confused about logical meaning of direction of a space
QUESTION [0 upvotes]: Here are the description about how PCA (Principal component analysis) is calculated (referred from this book). Confused about this statement -- "We can define the direction of this space using a D-dimensional vector u1", I think a vector can represent a direction and length, how could it represent a space? And when talking about PCA, it is projection into a space or projection into a vector (i.e. dot product)?

REPLY [1 votes]: If $u_1$ is any vector not orthogonal to the line, then we may decree that the projection of $u_1$ onto the line yields the positive direction. So any non-orthogonal vector yields an orientation of the line.


TITLE: Norm of a basis vector
QUESTION [0 upvotes]: Let $e_i=(0,\ldots,0,1,0,\ldots)$. Does $\|e_i\|=1$ for every norm $\|\cdot\|$?
If not, does anyone has a counter-example?

REPLY [1 votes]: The norm $$\|(x_1, x_2,\dots, x_n)\| = 2\cdot \sqrt{x_1^2 + x_2^2+\cdots +x_n^2}$$ is one such example.


text:
\begin{document}

\maketitle

\begin{abstract}
Let $X$ be a scheme and let $\M$ be a quasi-coherent sheaf on $X$. Then $\M$ can be viewed as a cogroup object in the category of schemes under $X$. We show that the category of first order thickenings of $X$ by $\M$ is equivalent to the category of $\M$-cotorsors.
\end{abstract}

\section{Introduction}

\begin{conv}
We always use the word \textit{ring} to refer to a commutative ring with identity, and we always use the phrase \textit{ring homomorphism} to refer to an identity-preserving ring homomorphism. We write $\Rings$ for the category of rings and ring homomorphisms. We fix a ring $A$ and an $A$-module $M$. We write $\Rings/A$ for the category of rings over $A$.
\end{conv}

According to Beck~\cite{Beck}, we can view $M$ as a group object in $\Rings/A$ via the trivial square-zero extension $A\oplus M\to A$. Using this idea, the Andre-Quillen cohomology theory for rings~\cite{Quillen} was developed. The first Andre-Quillen cohomology group $H^1(A, M)$ can be identified with the set of isomorphism classes of square-zero extensions of $A$ by $M$. This cohomology theory is equivalent to a sheaf cohomology theory, and it is well-known that the first sheaf cohomology group can be interpreted as a set of isomorphism classes of sheaf-theoretic torsors. However, it would be more satisfying to interpret $H^1(A, M)$ in terms of torsors directly in the category $\Rings/A$ rather than in terms of sheaf-theoretic torsors. Given that $M$ can be viewed as a group object in $\Rings/A$, there should be a well-defined notion of $M$-torsors in $\Rings/A$. In section~\ref{sqandtors}, we define $M$-torsors and prove that the category of $M$-torsors is equivalent to the category of square-zero extensions of $A$ by $M$. This achieves our goal of interpreting $H^1(A, M)$ in terms of torsors directly in the category $\Rings/A$.

\begin{conv}
We write $\Sch$ for the category of schemes. We fix a scheme $X$ and a quasi-coherent sheaf $\M$ on $X$. We write $\XSch$ for the category of schemes under $X$.
\end{conv}

Given that $X$ can be viewed as a generalized ring and $\M$ can be viewed as a generalized module, it is reasonable to suspect that the above discussion can be generalized to the scheme-theoretic setting. Indeed, there is a scheme-theoretic analogue~\cite{Stacks} of Andre-Quillen cohomology which we will refer to as scheme-theoretic Andre-Quillen \textit{homology} because the morphisms in $\Sch$ are in the opposite direction of the morphisms in $\Rings$. The first scheme-theoretic Andre-Quillen homology group $H_1(X, \M)$ can be identified with the set of isomorphism classes of first order thickenings of $X$ by $\M$. One may wonder whether it is possible to interpret $H_1(X, \M)$ in terms of torsors. However, since $H_1(X,\M)$ is a homology group rather than a cohomology group, it is more reasonable to expect an interpretation in terms of \textit{cotorsors}. As shown in~\cite{Remy}, $\M$ can be viewed as a cogroup object in $\XSch$. Therefore, there should be a well-defined notion of $\M$-cotorsors in $\XSch$. In section~\ref{thickandcos}, we define $\M$-cotorsors and prove that the category of $\M$-cotorsors is equivalent to the category of first order thickenings of $X$ by $\M$. This achieves our goal of interpreting $H_1(X, \M)$ in terms of cotorsors.

\section{Square-zero extensions and torsors}\label{sqandtors}

The purpose of this section is to develop the commutative algebra which is necessary to give efficient descriptions of first order thickenings and cotorsors. A first order thickening is, roughly speaking, a morphism of schemes which gives rise to a square-zero extension in each stalk. Therefore, it is natural to start by discussing square-zero extensions. Throughout this section, we will only ever consider square-zero extensions of $A$ by $M$ and thus we will simply call these square-zero extensions.
\begin{dfn}
Let $f: B\to A$ be an object of $\Rings/A$. We write $f_\ast M$ for the $B$-module defined as follows. The underlying abelian group of $f_\ast M$ is the same as the underlying abelian group of $M$. The $B$-scalar multiplication on $f_\ast M$ is such that, for all $b\in B$ and $m\in f_\ast M$, $b\cdot m$ = $f(b)m$.
\end{dfn}
\begin{dfn}\label{defsquarezext}
A \textit{square-zero extension} is an object $f: B\to A$ of $\Rings/A$ such that $f$ is surjective and $(\ker(f))^2 = 0$, together with an isomorphism $\alpha_f: f_\ast M\to \ker(f)$ of $B$-modules.
\end{dfn}
Let $f: B\to A$ be a square-zero extension. Then we have an associated isomorphism $\alpha_f: f_\ast M\to \ker(f)$ of $B$-modules. Alternatively, we can define square-zero extensions in such a way that $\alpha_f$ is viewed as an isomorphism of $A$-modules rather than as an isomorphism of $B$-modules. In order to do this, we need to define an $A$-module structure on $\ker(f)$. Let $a\in A$ and let $b\in \ker(f)$. Since $f$ is surjective, choose $b'\in B$ such that $f(b') = a$. Then define the $A$-scalar multiplication on $\ker(f)$ such that $a\cdot b = b' b$. We need to check that this $A$-scalar multiplication is well-defined. Let $b''\in B$ be such that $f(b'') = a$. Then $b' - b''\in \ker(f)$. Since $(\ker(f))^2 = 0$, we have that
\[
\begin{split}
b'' b &= b''b + (b' - b'')b \\
&= b'b.
\end{split}
\]
Given this $A$-module structure on $\ker(f)$, it is straightforward to verify that $\alpha_f: M\to \ker(f)$ is an isomorphism of $A$-modules if and only if $\alpha_f: f_\ast M\to \ker(f)$ is an isomorphism of $B$-modules (recall that $M$ and $f_\ast M$ have the same underlying abelian group). In the literature on square-zero extensions, somehow $\alpha_f$ is unanimously viewed as an isomorphism of $A$-modules rather than as an isomorphism of $B$-modules. However, in this paper we always view $\alpha_f$ as an isomorphism of $B$-modules. This perspective becomes especially convenient in Section~\ref{thickandcos}.
\begin{dfn}\label{defmorphismsquarezero}
Let $f: B\to A$ and $g: C\to A$ be square-zero extensions. A \textit{morphism of square-zero extensions} from $f$ to $g$ is a morphism $h: f\to g$ in $\Rings/A$ such that, for each $m\in M$, $h(\alpha_f(m)) = \alpha_g(m)$. We write $\Exal(A, M)$ for the category of square-zero extensions and morphisms of square-zero extensions.
\end{dfn}
\begin{dfn}
We write $A\oplus M$ for the ring whose underlying abelian group is the direct sum of the abelian groups $A$ and $M$ and whose multiplication is such that, for all $(a_1, m_1), (a_2, m_2)\in A\oplus M$,
\[
(a_1, m_1)(a_2, m_2) = (a_1a_2, a_1m_2 + a_2m_1).
\]
The canonical projection $\pi_A: A\oplus M\to A$ is an object of $\Rings/A$ such that $\pi_A$ is surjective and $(\ker(\pi_A))^2 = 0$. We write $\alpha_{\pi_A}: (\pi_A)_\ast M\to \ker(\pi_A)$ for the isomorphism of $(A\oplus M)$-modules such that, for each $m\in M$, $\alpha_{\pi_A}(m) = (0, m)$. Then $\pi_A$ together with $\alpha_{\pi_A}$ is a square-zero extension.
\end{dfn}
We now want to equip $\pi_A: A\oplus M\to A$ with the structure of a group object in $\Rings/A$. In order to do this, we need a notion of products and a terminal object. Note that the identity $\id_A: A \to A$ is a terminal object in $\Rings/A$. Let $f: B\to A$ and $g: C\to A$ be objects of $\Rings/A$. We write $B\times_A C$ for the subring of $B\times C$ such that
\[
B\times_A C = \{(b, c)\in B\times C\,|\, f(b) = g(c)\}.
\]
We write $f\times g: B\times_A C\to A$ for the ring homomorphism such that, for each $(b, c)\in B\times_A C$, $(f\times g)(b, c) = f(b) = g(c)$.
\begin{dfn}
We equip $\pi_A: A\oplus M\to A$ with the structure of a group object in $\Rings/A$ as follows. We define $e_M: \id_A\to \pi_A$ such that, for each $a\in A$,
\[
e_M(a) = (a, 0).
\]
We define $+_M: \pi_A\times\pi_A\to\pi_A$ such that, for each $((a, m_1), (a, m_2))\in (A\oplus M)\times_A (A\oplus M)$,
\[
(a, m_1) +_M (a, m_2) = (a, m_1 + m_2).
\]
We define $\inv_M: \pi_A\to \pi_A$ such that, for each $(a, m)\in A\oplus M$,
\[
\inv_M(a, m) = (a, -m).
\]
\end{dfn}
It is straightforward to verify that $\pi_A$ together with the three morphisms $e_M$, $+_M$, and $\inv_M$ in $\Rings/A$ define a group object (in fact an abelian group object) in $\Rings/A$. Therefore, we can define $\pi_A$-torsors in $\Rings/A$. We will call these torsors $M$-torsors rather than $\pi_A$-torsors for convenience of notation.
\begin{dfn}
An \textit{$M$-torsor} is an object $f: B\to A$ of $\Rings/A$ such that $f$ is surjective, together with a morphism $\tau_f: \pi_A\times f\to f$ in $\Rings/A$ such that
\begin{enumerate}
\item \textbf{Convention}: For each $((a, m), b)\in (A\oplus M)\times_A B$, we will usually write $\tau_f(m, b)$ instead of $\tau_f((a, m), b)$. This should not cause confusion beacuse $((a, m), b)\in (A\oplus M)\times_A B$ implies that $a = f(b)$, and hence the $a$ is redundant in the notation.
\item For each $b\in B$, $\tau_f(0, b) = b$.
\item For each $(b_1, b_2)\in B\times_A B$, there exists a unique $m\in M$ such that
\[
\tau_f(m, b_2) = b_1.
\]
\end{enumerate}
\end{dfn}
One may suspect that we also need to require an associativity axiom. However, associativity is implied by our definition of $M$-torsor. We prove this associativity now, together with a preliminary lemma.
\begin{lem}
Let $f: B\to A$ be an $M$-torsor. If $m\in M$ and $b\in B$, then
\[
\tau_f(m, b) = \tau_f(m, 0) + b.
\]
\end{lem}
\begin{proof}
Let $m\in M$ and let $b\in B$. Then
\[
\begin{split}
\tau_f(m, b) &= \tau_f((f(b), m), b) \\
&= \tau_f((0, m) + (f(b), 0), b) \\
&= \tau_f(((0, m), 0) + ((f(b), 0), b)) \\
&= \tau_f((0, m), 0) + \tau_f((f(b), 0), b) \\
&= \tau_f(m, 0) + \tau_f(0, b) \\
&= \tau_f(m, 0) + b.
\end{split}
\]
\end{proof}
\begin{lem}
Let $f: B\to A$ be an $M$-torsor. If $m_1, m_2\in M$ and $b\in B$, then
\[
\tau_f(m_1 + m_2, b) = \tau_f(m_1, \tau_f(m_2, b)).
\]
\end{lem}
\begin{proof}
Let $m_1, m_2\in M$ and let $b\in B$. Then
\[
\begin{split}
\tau_f(m_1 + m_2, b) &= \tau_f(m_1 + m_2, 0) + b \\
&= \tau_f((0, m_1 + m_2), 0) + b \\
&= \tau_f((0, m_1) + (0, m_2), 0) + b \\
&= \tau_f(((0, m_1), 0) + ((0, m_2), 0)) + b \\
&= \tau_f((0, m_1), 0) + \tau_f((0, m_2), 0) + b \\
&= \tau_f(m_1, 0) + \tau_f(m_2, 0) + b \\
&= \tau_f(m_1, 0) + \tau_f(m_2, b) \\
&= \tau_f(m_1, \tau_f(m_2, b)).
\end{split}
\]
\end{proof}
\begin{dfn}
Let $f: B\to A$ and $g: C\to A$ be $M$-torsors. A \textit{morphism of $M$-torsors} from $f$ to $g$ is a morphism $h: f\to g$ in $\Rings/A$ such that, for all $m\in M$ and $b\in B$,
\[
h(\tau_f (m, b)) = \tau_g(m, h(b)).
\]
We write $\MTors$ for the category of $M$-torsors and morphisms of $M$-torsors.
\end{dfn}
\begin{dfn}\label{torstructonsqze}
Let $f: B\to A$ be a square-zero extension. We write $\tau_f: (A\oplus M)\times_A B\to B$ for the function such that, for all $m\in M$ and $b\in B$,
\[
\tau_f(m, b) = \alpha_f(m) + b.
\]
\end{dfn}
\begin{lem}\label{torstructonsqzelemma}
If $f: B\to A$ is a square-zero extension, then $\tau_f: (A\oplus M)\times_A B\to B$ gives $f$ the structure of an $M$-torsor.
\end{lem}
\begin{proof}
Let $f: B\to A$ be a square-zero extension. We first need to verify that $\tau_f: \pi_A\times f\to f$ is a morphism in $\Rings/A$. Let $((f(b_1), m_1), b_1), ((f(b_2), m_2), b_2)\in (A\oplus M)\times_A B$. Recall that $\alpha_f: f_\ast M\to \ker(f)$ is an isomorphism of $B$-modules, and recall that $(\ker(f))^2 = 0$. Then
\[
\begin{split}
\tau_f(((f(b_1), m_1), b_1)((f(b_2), m_2), b_2)) &= \tau_f((f(b_1), m_1)(f(b_2), m_2), b_1b_2)) \\
&= \tau_f((f(b_1)f(b_2), f(b_1)m_2 + f(b_2)m_1), b_1 b_2) \\
&= \tau_f(f(b_1)m_2 + f(b_2)m_1, b_1 b_2) \\
&= \alpha_f(f(b_1)m_2 + f(b_2)m_1) + b_1 b_2 \\
&= \alpha_f(b_1\cdot m_2 + b_2\cdot m_1) + b_1 b_2 \\
&= b_1 \alpha_f(m_2) + b_2 \alpha_f(m_1) + b_1 b_2 \\
&= \alpha_f(m_1) \alpha_f(m_2) + b_1 \alpha_f(m_2) + b_2 \alpha_f(m_1) + b_1 b_2 \\
&= (\alpha_f(m_1) + b_1)(\alpha_f(m_2) + b_2) \\
&= \tau_f(m_1, b_1)\tau_f(m_2, b_2) \\
&= \tau_f((f(b_1), m_1), b_1)\tau_f((f(b_2), m_2), b_2)
\end{split}
\]
and thus $\tau_f$ preserves multiplication. It is straightforward to show that $\tau_f$ preserves addition and preserves the identity, so $\tau_f$ is a ring homomorphism. Furthermore, $\tau_f$ is a morphism in $\Rings/A$ since, for all $m\in M$ and $b\in B$,
\[
\begin{split}
f(\tau_f(m, b)) &= f(\alpha_f(m) + b) \\
&= f(\alpha_f(m)) + f(b) \\
&= f(b) \\
&= (\pi_A\times f)(m, b). \\
\end{split}
\]
It remains to show that the morphism $\tau_f$ in $\Rings/A$ indeed satisfies the properties of an $M$-torsor. Note that, for each $b\in B$,
\[
\begin{split}
\tau_f(0, b) &= \alpha_f(0) + b\\
&= b.
\end{split}
\]
Now let $(b_1, b_2)\in B\times_A B$. Then $b_1 - b_2\in \ker(f)$. Since $\alpha_f: f_\ast M\to \ker(f)$ is bijective, there exists a unique $m\in M$ such that $\alpha_f(m) = b_1 - b_2$. Equivalently, there exists a unique $m\in M$ such that $\tau_f(m, b_2) = \alpha_f(m) + b_2 = b_1$.
\end{proof}
We now show that the assignment $\Psi: \Exal(A, M)\to \MTors$ which maps each square-zero extension to its corresponding $M$-torsor can be extended to a functor. In particular, we show that each morphism of square-zero extensions induces a corresponding morphism of $M$-torsors.
\begin{lem}\label{morphisquarezeroextimptormorph}
Let $f: B\to A$ and $g: C\to A$ be square-zero extensions. If $h: f\to g$ is a morphism of square-zero extensions, then $h$ is a morphism of $M$-torsors.
\end{lem}
\begin{proof}
Let $h: f\to g$ be a morphism of square-zero extensions. Let $m\in M$ and let $b\in B$. Then
\[
\begin{split}
h(\tau_f(m, b)) &= h(\alpha_f(m) + b) \\
&= h(\alpha_f(m)) + h(b) \\
&= \alpha_g(m) + h(b) \\
&= \tau_g(m, h(b)).
\end{split}
\]
\end{proof}
\begin{dfn}
We write $\Psi: \Exal(A, M)\to \MTors$ for the functor which maps each square-zero extension to its corresponding $M$-torsor and which maps each morphism of square-zero extensions to its corresponding morphism of $M$-torsors.
\end{dfn}
\begin{thm}\label{ringtorstheorem}
The functor $\Psi: \Exal(A, M)\to \MTors$ is an equivalence of categories.
\end{thm}
\begin{proof}
We will show that $\Psi$ is fully faithful and essentially surjective. Note that $\Psi$ is faithful since $\Psi$ maps each morphism of square-zero extensions to itself.

We now show that $\Psi$ is full. Let $f: B\to A$ and $g: C\to A$ be square-zero extensions and let $h: f\to g$ be a morphism of $M$-torsors. We want to show that $h$ is a morphism of square-zero extensions. Let $m\in M$. Then
\[
\begin{split}
h(\alpha_f(m)) &= h(\tau_f(m, 0)) \\
&= \tau_g(m, h(0)) \\
&= \tau_g(m, 0) \\
&= \alpha_g(m) + 0 \\
&= \alpha_g(m)
\end{split}
\]
and thus $h$ is a morphism of square-zero extensions.

Finally, we show that $\Psi$ is essentially surjective. Let $f: B\to A$ be an $M$-torsor. We want to show that $f$ can be given the structure of a square-zero extension in such a way that the $M$-torsor structure associated with the square-zero extension $f$ is the same as the original $M$-torsor structure on $f$.

First we show that $f: B\to A$ is such that $(\ker(f))^2 = 0$. Let $b_1, b_2\in \ker(f)$. Then $(0, b_1), (0, b_2)\in B\times_A B$, so there exist unique $m_1, m_2\in M$ such that $\tau_f(m_1, b_1) = 0$ and  $\tau_f(m_2, b_2) = 0$. Since $\tau_f: (A\oplus M)\times_A B\to B$ is a ring homomorphism, we have that
\[
\begin{split}
0 &= 0\cdot 0 \\
&= \tau_f(m_1, b_1)\tau_f(m_2, b_2) \\
&= \tau_f((0, m_1), b_1)\tau_f((0, m_2), b_2) \\
&= \tau_f(((0, m_1), b_1)((0, m_2), b_2)) \\
&= \tau_f((0, m_1)(0, m_2), b_1b_2) \\
&= \tau_f((0, 0), b_1b_2) \\
&= \tau_f(0, b_1b_2) \\
&= b_1b_2
\end{split}
\]
and thus $(\ker(f))^2 = 0$.

Note that, for each $m\in M$,
\[
\begin{split}
f(\tau_f(m, 0)) &= (f\circ\tau_f)((0, m), 0) \\
&= (\pi_A\times f)((0, m), 0) \\
&= 0
\end{split}
\]
and thus $\tau_f(m, 0)\in \ker(f)$. We define a function $\alpha_f: f_\ast M\to \ker(f)$ such that, for each $m\in M$, $\alpha_f(m) = \tau_f(m, 0)$. Then $\alpha_f$ is bijective since, for each $b\in \ker(f)$, $(b, 0)\in B\times_A B$ and thus there exists a unique $m\in M$ such that $\alpha_f(m) = \tau_f(m, 0) = b$. We now show that $\alpha_f: f_\ast M\to \ker(f)$ is an isomorphism of $B$-modules. Let $m_1, m_2\in M$. Then
\[
\begin{split}
\alpha_f(m_1 + m_2) &= \tau_f(m_1 + m_2, 0) \\
&= \tau_f(m_1, \tau_f(m_2,0)) \\
&= \tau_f(m_1, 0) + \tau_f(m_2, 0) \\
&= \alpha_f(m_1) + \alpha_f(m_2)
\end{split}
\]
and thus $\alpha_f$ is a group homomorphism. Let $b\in B$ and let $m\in M$. Then
\[
\begin{split}
\alpha_f(b\cdot m) &= \alpha_f(f(b)m) \\
&= \tau_f(f(b)m, 0) \\
&= \tau_f((0, f(b)m), 0) \\
&= \tau_f((f(b), 0)(0, m), 0) \\
&= \tau_f(((f(b), 0), b)((0, m), 0)) \\
&= \tau_f((f(b), 0), b)\tau_f((0, m), 0) \\
&= \tau_f(0, b)\tau_f(m, 0) \\
&= b\,\alpha_f(m)
\end{split}
\]
and thus $\alpha_f$ preserves $B$-scalar multiplication. Therefore, $\alpha_f: f_\ast M\to \ker(f)$ is an isomorphism of $B$-modules and hence $f$ together with $\alpha_f$ is a square-zero extension.

It remains to be shown that the $M$-torsor structure associated with the square-zero extension $f$ is the same as the original $M$-torsor structure on $f$. Let $m\in M$ and let $b\in B$. Then
\[
\begin{split}
\tau_f(m, b) &= \tau_f(m, 0) + b \\
&= \alpha_f(m) + b.
\end{split}
\]
Therefore, the functor $\Psi: \Exal(A, M)\to \MTors$ is an equivalence of categories.
\end{proof}

\section{First order thickenings and cotorsors}\label{thickandcos}

In effort to make this section easier to read, an attempt has been made to follow the organization of section~\ref{sqandtors} as closely as possible. In the previous section, we studied square-zero extensions. We will now describe the scheme-theoretic analogue of a square-zero extension, which is called a first order thickening. Since we will only ever consider first order thickenings of $X$ by $\M$, we will simply call these first order thickenings.
\begin{dfn}
Let $f: X\to Y$ be an object of $\XSch$ such that $f$ is a closed immersion. We write
\[
\I_f = \ker(f^\#: \O_Y\to f_\ast\O_X).
\]
\end{dfn}
Let $f: X\to Y$ be an object of $\XSch$ such that $f$ is a closed immersion and let $\alpha_f: f_\ast\M\to \I_f$ be an isomorphism of $\O_Y$-modules. Let $x\in X$. Then the canonical ring homomorphism $(f_\ast \O_X)_{f(x)}\to \O_{X, x}$ is an isomorphism and the canonical group homomorphism $(f_\ast \M)_{f(x)}\to \M_x$ is an isomorphism. Thus we obtain an object $f^\#_x: \O_{Y, f(x)}\to \O_{X, x}$ of $\Rings/\O_{X, x}$ such that $f^\#_x$ is surjective and an isomorphism $\alpha_{f, x}: (f^\#_x)_\ast \M_x\to \I_{f, f(x)}$ of $\O_{Y, f(x)}$-modules.
\begin{dfn}
See Definition~\ref{defsquarezext}. A \textit{first order thickening} is an object $f: X\to Y$ of $\XSch$ such that $f$ is a surjective closed immersion, together with an isomorphism $\alpha_f: f_\ast\M\to \I_f$ of $\O_Y$-modules such that, for each $x\in X$, the object $f^\#_x: \O_{Y, f(x)}\to \O_{X, x}$ of $\Rings/\O_{X, x}$ together with the isomorphism $\alpha_{f, x}: (f^\#_x)_\ast \M_x\to \I_{f, f(x)}$ of $\O_{Y, f(x)}$-modules is a square-zero extension of $\O_{X, x}$ by $\M_x$.
\end{dfn}
Let $f: X\to Y$ and $g: X\to Z$ be first order thickenings. Let $x\in X$. Then we obtain square-zero extensions $f^\#_x$ and $g^\#_x$ of $\O_{X, x}$ by $\M_x$. Let $h: f\to g$ be a morphism in $\XSch$. Then, for each $x\in X$, we obtain a morphism
\[
h^\#_x: \O_{Z, g(x)}\to \O_{Y, f(x)}
\]
in $\Rings/\O_{X, x}$.
\begin{dfn}
See Definition~\ref{defmorphismsquarezero}. Let $f: X\to Y$ and $g: X\to Z$ be first order thickenings. A \textit{morphism of first order thickenings} from $f$ to $g$ is a morphism $h: f\to g$ in $\XSch$ such that, for each $x\in X$,
\[
h^\#_x: \O_{Z, g(x)}\to \O_{Y, f(x)}
\]
is a morphism of square-zero extensions of $\O_{X, x}$ by $\M_x$. We write $\ThSch(X, \M)$ for the category of first order thickenings and morphisms of first order thickenings.
\end{dfn}
\begin{dfn}
We write $X\oplus \M$ for the scheme whose underlying topological space is $X$ and whose structure sheaf is $\O_{X\oplus \M} = \O_X\oplus \M$ where, for each open subset $U$ of $X$, $(\O_X\oplus\M)(U)$ is the ring $\O_X(U)\oplus \M(U)$. We write $i_X: X\to X\oplus \M$ for the morphism of schemes which is the identity on topological spaces and $i_X^\#: \O_X\oplus \M\to\O_X$ is the canonical projection of $\O_X\oplus \M$ onto $\O_X$. Then $i_X$ is a surjective closed immersion. Note that $(i_X)_\ast \M = \M$. We write $\alpha_{i_X}: \M\to \I_{i_X}$ for the isomorphism of $\O_{X\oplus M}$-modules such that, for all open subsets $U$ of $X$ and $m\in \M(U)$, $\alpha_{i_X}(U)(m) = (0, m)\in\O_X(U)\oplus \M(U)$. Then $i_X$ together with $\alpha_{i_X}$ is a first order thickening.
\end{dfn}
We now want to equip $i_X: X \to X\oplus \M$ with the structure of a cogroup object in $\XSch$. In order to do this, we need a notion of coproducts and an initial object. Note that the identity $\id_X: X \to X$ is an initial object in $\XSch$. Let $f: X\to Y$ and $g: X\to Z$ be objects of $\XSch$ such that $f$ and $g$ are closed immersions. First consider $f: X\to Y$ and $g:X\to Z$ as continuous maps of topological spaces. We can form the pushout
\[
\begin{tikzcd}
X \arrow{r}{g} \arrow[swap]{d}{f} & Z \arrow{d}{j_Z} \\
Y \arrow{r}{j_Y} & Y\amalg_X Z
\end{tikzcd}
\]
in the category of topological spaces. Then the topological space $Y\amalg_X Z$, together with the sheaf of rings
\[
\O_{Y\amalg_X Z} = (j_Y)_\ast\O_Y\times_{(j_Y\circ f)_\ast\O_X} (j_Z)_\ast\O_Z = (j_Y)_\ast\O_Y\times_{(j_Z\circ g)_\ast\O_X} (j_Z)_\ast\O_Z
\]
is a scheme and we write $f\amalg g: X\to Y\amalg_X Z$ for the associated object of $\XSch$. The object $f\amalg g$ of $\XSch$ is a coproduct of $f$ and $g$ since the scheme $Y\amalg_X Z$ is a pushout in the category of schemes~\cite{StacksPushout}. Thus we have a well-defined notion of cogroup object in $\XSch$, so long as the underlying ordinary object is a closed immersion.
\begin{dfn}
We equip $i_X: X\to X\oplus \M$ with the structure of a cogroup object in $\XSch$ as follows. We define $e_\M: i_X \to \id_X$ such that $e_\M$ is the identity on topological spaces and $e_\M^\#: \O_X\to \O_X\oplus \M$ is the canonical inclusion of $\O_X$ into $\O_X\oplus \M$. Note that, since $i_X$ is the identity on topological spaces, the coproduct $i_X\amalg i_X: X\to (X\oplus \M)\amalg_X (X\oplus\M)$ is also the identity on topological spaces. The structure sheaf of the scheme $(X\oplus \M)\amalg_X (X\oplus\M)$ is $(\O_X\oplus \M)\times_{\O_X} (\O_X\oplus\M)$. We define $+_\M: i_X\to i_X\amalg i_X$ such that $+_\M$ is the identity on topological spaces and $+_\M^\#: (\O_X\oplus \M)\times_{\O_X} (\O_X\oplus\M) \to \O_X\oplus \M$ is such that, for all open subsets $U$ of $X$ and $((a, m_1), (a, m_2))\in (\O_X(U)\oplus \M(U))\times_{\O_X(U)} (\O_X(U)\oplus\M(U))$,
\[
(a, m_1) +_{\M(U)}^\# (a, m_2) = (a, m_1 + m_2).
\]
We define $\inv_\M: i_X\to i_X$ such that $\inv_\M$ is the identity on topological spaces and $\inv_\M^\#: \O_X\oplus \M\to \O_X\oplus \M$ is such that, for all open subsets $U$ of $X$ and $(a, m)\in \O_X(U)\oplus \M(U)$,
\[
\inv_{\M(U)}^\#(a, m) = (a, -m).
\]
\end{dfn}

It is straightforward to verify that $i_X$ together with the three morphisms $e_\M$, $+_\M$, and $\inv_\M$ in $\XSch$ define a cogroup object (in fact an abelian cogroup object) in $\XSch$. Therefore, we can define $i_X$-cotorsors in $\XSch$. We will call these cotorsors $\M$-cotorsors rather than $i_X$-cotorsors for convenience of notation. Before stating the definition of $\M$-cotorsor, we need to make some preliminary remarks.

Let $f: X\to Y$ be an object of $\XSch$ such that $f$ is a closed immersion. Using the universal property of the coproduct $i_X\amalg f$, we obtain a morphism $\theta: (X\oplus\M)\amalg_X Y\to Y$ fitting into the pushout diagram
\[
\begin{tikzcd}
X \arrow[swap]{d}{i_X} \arrow{r}{f} &
Y \arrow{d}{j_Y} \arrow[ddr,bend left,"\id_Y"] \\
X\oplus \M \arrow{r}{j_{X\oplus\M}} \arrow[drr,bend right,"f\circ e_\M"'] &
(X\oplus\M)\amalg_X Y \arrow[dr,dashed,"\theta"] \\
&& Y
\end{tikzcd}
\]
Since $i_X$ is a cogroup object in $\XSch$, there should be a well-defined notion of a cogroup action of $i_X$ on $f$. A candidate for a cogroup action is a morphism $\tau_f: f\to i_X\amalg f$ in $\XSch$. For an ordinary group action on a space, we have an axiom which states that the identity element of the group acts trivially on all elements of the space. The analogue of that axiom in the cogroup setting states that $\theta\circ\tau_f = \id_Y$. Note that since the underlying topological space of the scheme $X\oplus \M$ is the topological space $X$, the topological space $Y$ is the underlying topological space of the scheme $(X\oplus \M)\amalg_X Y$. Therefore, at the level of topological spaces, the above pushout diagram becomes
\[
\begin{tikzcd}
X \arrow[swap]{d}{\id_X} \arrow{r}{f} &
Y \arrow{d}{\id_Y} \arrow[ddr,bend left,"\id_Y"] \\
X \arrow{r}{f} \arrow[drr,bend right,"f"'] &
Y \arrow[dr,dashed,"\theta"] \\
&& Y
\end{tikzcd}
\]
and we see that $\theta: Y\to Y$ must be the identity on topological spaces. Therefore, if $\tau_f: f\to i_X\amalg f$ is to be thought of as a cogroup action, we must have that $\theta\circ\tau_f = \id_Y$ and hence as functions on topological spaces we must have that $\tau_f = \theta = \id_Y$.

See Lemma~\ref{cotorimpsurj} and Remark~\ref{twodefscotors} in regards to the following definition.
\begin{dfn}
An \textit{$\M$-cotorsor} is an object $f: X\to Y$ of $\XSch$ such that $f$ is a closed immersion, together with a morphism $\tau_f: f\to i_X\amalg f$ in $\XSch$ such that
\begin{enumerate}
\item $\tau_f$ is the identity on topological spaces.
\item For each $y\in Y$, the object $f^\#_y: \O_{Y, y}\to (f_\ast \O_X)_y$ of $\Rings/(f_\ast \O_X)_y$ together with the morphism
\[
\tau^\#_{f,y}: ((f_\ast\O_X)_y\oplus (f_\ast \M)_y)\times_{(f_\ast \O_X)_y} \O_{Y, y}\to \O_{Y, y}
\]
in $\Rings/(f_\ast \O_X)_y$ is an $(f_\ast \M)_y$-torsor.
\end{enumerate}
\end{dfn}
A few comments need to be made about this definition of $\M$-cotorsor. Recall from the above discussion that the underlying topological space of $(X\oplus\M)\amalg_X Y$ is $Y$, and that $\tau_f$ must be the identity on topological spaces in order for $\tau_f$ to be thought of as a cogroup action. The structure sheaf of $(X\oplus\M)\amalg_X Y$ is $(f_\ast\O_X\oplus f_\ast\M)\times_{f_\ast \O_X} \O_Y$, and thus we have that $\tau_f^\#: (f_\ast\O_X\oplus f_\ast\M)\times_{f_\ast \O_X} \O_Y\to \O_Y$. Let $y\in Y$. Then we have a morphism
\[
\tau^\#_{f,y}: ((f_\ast\O_X)_y\oplus (f_\ast \M)_y)\times_{(f_\ast \O_X)_y} \O_{Y, y}\to \O_{Y, y}
\]
in $\Rings/(f_\ast \O_X)_y$. Since $f$ is a closed immersion, $f^\#_y: \O_{Y, y}\to (f_\ast \O_X)_y$ is surjective and thus it makes sense to test whether or not the object $f^\#_y$ of $\Rings/(f_\ast \O_X)_y$ together with $\tau^\#_{f, y}$ is an $(f_\ast \M)_y$-torsor.

Note that we do not require $f$ to be surjective in the definition of $\M$-cotorsor. However, the axioms for an $\M$-cotorsor imply that $f$ is surjective.
\begin{lem}\label{cotorimpsurj}
If $f: X\to Y$ is an $\M$-cotorsor, then $f$ is surjective.
\end{lem}
\begin{proof}
Let $f: X\to Y$ be an $\M$-cotorsor. Let $y\in Y$. Since $f$ is an $\M$-cotorsor, the object $f^\#_y: \O_{Y, y}\to (f_\ast \O_X)_y$ of $\Rings/(f_\ast \O_X)_y$ together with the morphism
\[
\tau^\#_{f,y}: ((f_\ast\O_X)_y\oplus (f_\ast \M)_y)\times_{(f_\ast \O_X)_y} \O_{Y, y}\to \O_{Y, y}
\]
in $\Rings/(f_\ast \O_X)_y$ is an $(f_\ast \M)_y$-torsor. Since every $(f_\ast \M)_y$-torsor has a square-zero kernel, we conclude that $(\ker(f^\#_y))^2 = 0$. Therefore, we must have that $\ker(f^\#_y)$ is a subset of the unique maximal ideal $\m_y\sub\O_{Y, y}$. Thus $\O_{Y, y}/\ker(f^\#_y)\isom (f_\ast \O_X)_y$ is nonzero and, since the image of $f$ is a closed subset of $Y$, we conclude that $y$ must be contained in the image of $f$.
\end{proof}
\begin{rem}\label{twodefscotors}
Given that the underlying object of $\XSch$ of any $\M$-cotorsor is automatically surjective, we obtain the following alternative definition of $\M$-cotorsor. Let $f: X\to Y$ be an object of $\XSch$ such that $f$ is a closed immersion and let $\tau_f: f\to i_X\amalg f$ be a morphism in $\XSch$. Then $f$ together with $\tau_f$ is an $\M$-cotorsor if and only if
\begin{enumerate}
\item $\tau_f$ is the identity on topological spaces.
\item $f$ is surjective.
\item For each $x\in X$, the object $f^\#_x: \O_{Y, f(x)}\to \O_{X, x}$ of $\Rings/\O_{X, x}$ together with the morphism
\[
\tau^\#_{f, x}: (\O_{X, x}\oplus \M_x)\times_{\O_{X, x}} \O_{Y, f(x)}\to \O_{Y, f(x)}
\]
in $\Rings/\O_{X, x}$ is an $\M_x$-torsor.
\end{enumerate}
This definition of $\M$-cotorsor is easier to work with than our original definition because its form is more closely related to first order thickenings. However, it seems to me that requiring $f$ to be surjective in the definition of $\M$-cotorsor is too strong of a condition.
\end{rem}
Let $f: X\to Y$ and $g: X\to Z$ be $\M$-cotorsors. Let $x\in X$. Then the objects $f^\#_x: \O_{Y, f(x)}\to \O_{X, x}$ and $g^\#_x: \O_{Z, g(x)}\to \O_{X, x}$ of $\Rings/\O_{X, x}$ together with the morphisms
\[
\tau^\#_{f, x}: (\O_{X, x}\oplus \M_x)\times_{\O_{X, x}} \O_{Y, f(x)}\to \O_{Y, f(x)}
\]
and
\[
\tau^\#_{g, x}: (\O_{X, x}\oplus \M_x)\times_{\O_{X, x}} \O_{Z, g(x)}\to \O_{Z, g(x)}
\]
in $\Rings/\O_{X, x}$ are $\M_x$-torsors.
\begin{dfn}
Let $f: X\to Y$ and $g: X\to Z$ be $\M$-cotorsors. A \textit{morphism of $\M$-cotorsors} from $f$ to $g$ is a morphism $h: f\to g$ in $\XSch$ such that, for each $x\in X$,
\[
h^\#_x: \O_{Z, g(x)}\to \O_{Y, f(x)}
\]
is a morphism of $\M_x$-torsors. We write $\McoTors$ for the category of $\M$-cotorsors and morphisms of $\M$-cotorsors.
\end{dfn}
\begin{dfn}
See Definition~\ref{torstructonsqze}, Lemma~\ref{torstructonsqzelemma}, and Remark~\ref{twodefscotors}. Let $f: X\to Y$ be a first order thickening. Then we define an $\M$-cotorsor structure on $f$ as follows. We write $\tau_f: f\to i_X\amalg f$ for the morphism in $\XSch$ such that $\tau_f$ is the identity on topological spaces and, for each $x\in X$,
\[
\tau^\#_{f, x}: (\O_{X, x}\oplus \M_x)\times_{\O_{X, x}} \O_{Y, f(x)}\to \O_{Y, f(x)}
\]
is the $\M_x$-torsor structure associated with the square-zero extension $f^\#_x: \O_{Y, f(x)}\to \O_{X, x}$ of $\O_{X, x}$ by $\M_x$.
\end{dfn}
In the above definition, it is straightforward to verify that the torsor structures specified on the stalks indeed give rise to a well-defined morphism $\tau_f: f\to i_X\amalg f$. We now show that the assignment $\Phi: \ThSch(X, \M)\to \McoTors$ which maps each first order thickening to its corresponding $\M$-cotorsor can be extended to a functor. In particular, we show that each morphism of first order thickenings induces a corresponding morphism of $\M$-cotorsors.
\begin{lem}
Let $f: X\to Y$ and $g: X\to Z$ be first order thickenings. If $h: f\to g$ is a morphism of first order thickenings, then $h$ is a morphism of $\M$-cotorsors.
\end{lem}
\begin{proof}
Let $h: f\to g$ be a morphism of first order thickenings and let $x\in X$. Then $h^\#_x: f^\#_x\to g^\#_x$ is a morphism of square-zero extensions of $\O_{X, x}$ by $\M_x$. Since $\tau^\#_{f, x}$ and $\tau^\#_{g, x}$ are the $\M_x$-torsor structures associated with the square-zero extensions $f^\#_x$ and $g^\#_x$ of $\O_{X, x}$ by $\M_x$, we know from Lemma~\ref{morphisquarezeroextimptormorph} that $h^\#_x$ is a morphism of $\M_x$-torsors.
\end{proof}
\begin{dfn}
We write $\Phi: \ThSch(X, \M)\to \McoTors$ for the functor which maps each first order thickening to its corresponding $\M$-cotorsor and which maps each morphism of first order thickenings to its corresponding morphism of $\M$-cotorsors.
\end{dfn}
\begin{thm}\label{mainthm}
The functor $\Phi: \ThSch(X, \M)\to \McoTors$ is an equivalence of categories.
\end{thm}
\begin{proof}
Now that we have set up all of the formalism for working with $\M$-cotorsors, this theorem follows straightforwardly from Theorem~\ref{ringtorstheorem}.
\end{proof}

\section*{Conclusion}

In this paper, we have shown that the first scheme-theoretic Andre-Quillen homology group (recall the discussion from the introduction) can be interpreted as a set of isomorphism classes of cotorsors. On a technical level, this result was proved by showing that first order thickenings of schemes can be identified with cotorsors for the cogroups associated with quasi-coherent sheaves. We have thus given a concrete geometric and categorical interpretation of an otherwise abstract homology group. Since the literature on cogroups and cotorsors in algebraic geometry is still in its infancy, this result marks an important turning point on the quest for a deeper understanding of homology theories in general.

We now make a few comments on how this research could be continued in the future. One project would be to take a fresh look at etale morphisms through the lens of cotorsors. The notion of a first order thickening is fundamentally related to etale morphisms of schemes, so it is reasonable to suspect that one may gain deeper insights into etale morphisms by replacing first order thickenings by their incarnation as cotorsors.

The next line of inquiry would be to study which other homology theories have convenient descriptions in terms of cotorsors, and also see which new homology theories can be developed from the cotorsor perspective. Finally, the cotorsor picture of the first scheme-theoretic Andre-Quillen homology group begs for a higher-categorical analogue. It is reasonable to suspect that a good theory of $\infty$-cotorsors should allow one to reproduce the full scheme-theoretic Andre-Quillen homology theory. Furthermore, there is nothing about this paper which is so special to schemes. There does not seem to be any barrier to proving similar results (perhaps with minor modifications) for algebraic spaces and stacks, as well as their derived analogues.

\section*{Acknowledgements}

In section 7.4.1 of Jacob Lurie's book \textit{Higher Algebra}~\cite{Lurie}, a comment is made about viewing square-zero extensions as torsors. That comment was the original source of motivation for this paper.

To the best of my knowledge, the only other reference to cogroups and cotorsors in the context of schemes is in the paper \textit{Combinatorial Differential Forms}~\cite{BreenMessing} by Lawrence Breen and William Messing. Some of what has been stated in the present paper can be found in section 1.11 of Breen and Messing's paper, but it does not appear that they carried out their inquiry all the way to the point of Theorem~\ref{mainthm}.

I would like to thank Sam Spiro for some helpful comments on the formatting of this paper.


TITLE: Why are we not allowed to write Big-O notation in terms of fractions? Ex: O(n/2)
QUESTION [1 upvotes]: For example, the average case for linear sort is described as O(n). But why is it not described as O(n/2), wouldn't it be this way because the average is the average times the program runs?

REPLY [3 votes]: This is exactly the same statement because we have :
$$O(n) = O\left(\frac{n}{2}\right)$$
Saying that a function $f$ is $O(n)$ means that there is an $N$ and some $K>0$ such that :
$$ \forall n > N, |f(n)| \leq Kn$$
So in particular we have .
$$\forall n > N, |f(n)| \leq (2K)\frac{n}{2}$$
We prefer to say $O(n)$ for simplicity.
Hence note that in general we have :
$$O(n) = O(Kn), \text{ for some } K > 0$$


TITLE: Nowhere $0$ form on the sphere?
QUESTION [2 upvotes]: Consider the differential form on $\mathbb R^3$ given by $ x dy \wedge dz + y dz \wedge dx + z dx \wedge dy$. I converted this to spherical coordinates using a laborious calculation, and when I'm done, by some miracle (which would be cool if someone could explain exactly how that works), I get something really compact and elegant: $\rho^3 \sin \phi d\phi \wedge d\theta$.
If we call this form $\Omega$, my task is to compute $i^*\Omega,$ where $i$ represents the inclusion from $\mathbb S^2 \rightarrow \mathbb R^3$, which seems to be pretty easy also - on the unit sphere we just have $\rho = 1$.
Now why is this nowhere $0$ on the sphere? It looks like it's $0$ along the half plane where $\phi = 0$!

REPLY [4 votes]: Let me remark that there is no need to convert to spherical coordinates. The coordinates $x,y,z$ are well defined smooth functions on $S^2$, so their exterior derivatives are well defined one-forms on $S^2$. Naturality of the exterior derivative and the operations on differential forms shows that the pullback of your form to $S^2$ is still given by $xdy\wedge dz+ydz\wedge dx+zdx\wedge dy$. To show that this is nowhere vanishing, observe that on $S^2$, one has $x^2+y^2+z^2=1$, so applying the exterior derivative (and dividing by 2) we get $0=xdx+ydy+zdz$. Now on the open subset $\{x\neq 0\}$ you can use this equation to rewrite your form as $\frac1x(x^2+y^2+z^2)dy\wedge dz$. At the same time, on this open subset you can use $y$ and $z$ as local coordinates, which shows that $dy\wedge dz$ and hence your form is nowhere vanishing on $\{x\neq 0\}$. Similar arguments apply to the sets $\{y\neq 0\}$ and $\{z\neq 0\}$, and together the three sets cover $S^2$.


TITLE: Minimizing a strictly convex quadratic function over 2 norm ball
QUESTION [2 upvotes]: Let $x, b\in \mathbb{R}^n$ and let $P$ be a $n \times n$ positive definite symmetrix matrix. $r$ is a positive number. What is the minimum of this problem?
$$\begin{array}{ll} \text{minimize} & x^T P x+2 b^Tx\,\\ \text{subject to} & x^T x \leq r\end{array}$$
It seems this problem has an explicit solution, I am surprised that I couldn’t find it on the internet since it is just a special case of the trust region subproblem.

REPLY [0 votes]: I think I have one answer though. Look at this paper
http://users.clas.ufl.edu/hager/papers/Regular/sphere.pdf


TITLE: second derivative of the composition of two multivariable functions
QUESTION [1 upvotes]: Let $U \subset \mathbb{R}^n$ be open, and let $\gamma: \mathbb{R} \to U$ and $f: U \to \mathbb{R}$ be to functions that are differentiable at least twice.
I want to show that $\frac{d^2}{dt^2}(f \circ \gamma)(t)$ is then given by:
$$\frac{d^2}{dt^2}(f \circ \gamma)(t) = \dot{\gamma}(t)^t H f(\gamma(t))\dot{\gamma}(t)+ d f(\gamma(t))\dot{\dot{\gamma}}(t)$$
(where $H f(x)$ is the Hesse matrix of $f$ at $x \in U$).
I must admit that I don't really know how to get started. It looks like one could utilise the multivariable chain rule?

REPLY [1 votes]: For the first derivation we get:
$d/dt f(\gamma(t)) = <\nabla f(\gamma_1(t),...,\gamma_n(t)), \dot\gamma_1(t),...\dot\gamma_n(t) > = \sum\limits_{i=1}^n \partial_if(\gamma(t))\dot\gamma_i(t) $
For the second one we get:
$d^2/dt^2 f(\gamma(t)) = \sum\limits_{i=1}^n<(\partial_{i1}f(\gamma(t)),...,\partial_{in}f(\gamma(t)),\dot\gamma_1(t),...\dot\gamma_n(t)>\dot\gamma_i(t) + \partial_if(\gamma(t))\dot{\dot\gamma_i}(t) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n \partial_{ij}f(\gamma(t))\dot\gamma_i(t)\dot\gamma_j(t) + \sum\limits_{i=1}^n \partial_if(\gamma(t))\dot{\dot\gamma_i}(t) = \dot{\gamma}(t)^t H f(\gamma(t))\dot{\gamma}(t)+ <d/dt f(\gamma(t)),\dot{\dot{\gamma}}(t)> $
Where $< . , . >$ denotes the standard scalar product.


TITLE: Reference for the converse of Cartan's Theorem B
QUESTION [4 upvotes]: Cartan's theorem B states that every coherent analytic sheaf on a Stein manifold is acyclic.  Hartshorne claims that the converse to this theorem also holds, but doesn't supply a reference.  Does anyone where to find a proof of this fact?
Thank you kindly.

REPLY [9 votes]: Actually a more general result is true:
If $X$ is a complex space (maybe not smooth) and if $H^1(X,\mathcal I)$ is zero for all coherent sheaves of ideals $\mathcal I\subset \mathcal O_X$, then $X$ is a Stein space.
This is Proposition 52.6 In L.Kaup-B.Kaup's Holomorphic Functions of Several Variables.
It is also proved in Taylor's book: Proposition 11.4.5
An amusing variant is that an open subset $U\subset \mathbb C^n$ is Stein iff  $H^i(U,\mathcal O)$ for all $1\leq i\leq n-1$.
This is proved as Theorem 2, §5, Chapter V, page 159 of Grauert-Remmert's Theory of Stein Spaces.


TITLE: Turkey TST 2014 Day 3 Problem 9 Worms that are allowed to move one way
QUESTION [5 upvotes]: Turkey TST 2014 Day 3 Problem 9( I've read the official answer, and I find the official answer incorrect）

At the bottom-left corner of a $2014\times 2014$ chessboard, there are some green worms and at the top-left corner of the same chessboard, there are some brown worms. Green worms can move only to right and up, and brown worms can move only to right and down. After a while, the worms make some moves and all of the unit squares of the chessboard become occupied at least once throughout this process. Find the minimum total number of the worms.

There in AOPS Some of these discussions, however, are just as problematic as the official answers：I found this somewrong:

In the final calculation of the green and Brown crawler through the grid, according to the inclusive-exclusive principle to subtract duplicate. The answer is that the repeated squares do not overlap by default when calculating repetitions. For example, the Green Reptilian AB has crossed C, and the Brown Reptilian D has crossed C, twice, in the manner of the answer, but actually it should have been once

The following is an official translation of the Chinese version

REPLY [1 votes]: The key to understanding why it takes less than $n$ worms to cover an nxn area is considering the case $n=3$.
let's display the best 3x3 solution by denoting each worm a number and labelling each cell with the worm(s) that visited it:
$$
    \begin{matrix}
    1 &  &  \\
    1 & 1 & 1 \\
     &  & 1 \\
    \end{matrix}
$$
$$
    \begin{matrix}
    1 & 2 & 2 \\
    1 & 12 & 1 \\
    2 & 2 & 1 \\
    \end{matrix}
$$
Let's try to make sense of what conclusions we can draw from the above and in general:

We want to minimise the overlap of worms (or numbers in each matrix cell) both for same-color worms but also for different-color worms.
We want each worm to visit as many cells as possible, and for as many of these as possible to be unvisited.
Worm $i$ can visit $2n-i$ cells in the optimal solution, since it visits $2n-1$ cells and must cross the path of at least $i-1$ worms. (as a sidenote, clearly the chinese textbook uses this fact to sum the overlapped squares in its proof - and then factorises n^2 ).

Clearly overlap is unavoidable in the two right corners, and must occur between the green and brown worms, but should never do so between same-coloured worms outside of corners. The 9x9 solution illustrates this:
$$
    \begin{matrix}
    123 & 23 & 3 & 4 & 4 & 4 & 4 & 4 & 456 \\
    1 & 2 & 3 & 4 & 5 & 5 & 5 & 5 & 56 \\
    1 & 2 & 3 & 4 & 5 & 6 & 6 & 6 & 6 \\
    1 & 2 & 3 & 34 & 35 & 36 & 3 & 3 & 3 \\
    1 & 2 & 2 & 24 & 25 & 26 & 2 & 2 & 3 \\
    1 & 1 & 1 & 14 & 15 & 16 & 1 & 2 & 3 \\
    4 & 4 & 4 & 4 & 5 & 6 & 1 & 2 & 3 \\
    45 & 5 & 5 & 5 & 5 & 6 & 1 & 2 & 3 \\
    456 & 6 & 6 & 6 & 6 & 6 & 1 & 12 & 123 \\
    \end{matrix}
$$
A pattern that extends from this center-overlap strategy is that the central n/3-2n/3 squares only need require 2 numbers. i.e. The only need be brown-green worm overlaps. That is, $n^2/9$ squares will have 2 worms go through them. Noting that n/3 worms can certainly cover each other section as shown, we can conclude that we need 2*n/3 worms altogether.
In the case where n mod 3 is not 1, 1 extra worm can trace the outside to reduce the problem to a mod 3 = 0 case. If n mod 3 is 2, then we simply solve the board for the next integer case and have overlap in n/3 squares. That is, for instance n=11 and n=12 would have the same number of worms required (8).
for 2014, the remainder is 1 and the first worm reduces the board to a 2013x2013 board as described, which is then traversed by 2 sets of 2013/3 worms - or 671 worms. In total that is 671*2+1 which is 1343.
A full proof to this problem would probably require discussing the analogy of perpendicular sets of parallel lines to the different-coloured worms. Clearly, each line must cross all of the perpendicular ones(here, each green worm must cross paths with each brown worm). Then discussing how (and why) if only one corner was originally occupied, it must take $n$ worms to traverse it with the same rules. This is important to justify how the two right corners (top and bottom third - so $n/3$ squares) can be traversed by $n/3$ worms. Justifying how n/3 worms can continue across to another n/3 set of squares on the centers of the board is a direct extension of this.
Alternatively, as is done in the textbook, a proof to show why 2n/3 is the best possible outcome via factorising and then demonstrating how 2n/3 can be achieved may be enough for Olympiad marking.


TITLE: Can I use angular diameter to determine the apparent size of an object at a given distance?
QUESTION [1 upvotes]: I believe this question uses Angular Diameter to determine the answer but I'm not sure how to use it.
Question: If a widget is 10 meters wide and it is positioned 1,000 meters from the observer how wide will it appear?  How wide will it appear at 2,000 meters?  Is Angular Diameter used for this?
Using this online calculator I inputted 10 meters for Linear Size and 1000 meters for Distance to Object.  It returned an Angular Diameter of 0.572953020554149.  But how does this help me determine the apparent size of an object at a given distance?  Or alternately am I using the wrong formula?
Backstory:
I can find many references to Angular Diameter on both Google and this forum.  But I can't find one that explains how to use this simple concept to determine on object's apparent size.

REPLY [1 votes]: You need to add Ratio to your equations. If you know how big something is than add the ratio of that to the equation and do the math there... P.s. I'm horrible at math. It's just a thought.


text:
\section{Addition Rule for Gaussian Binomial Coefficients/Formulation 2}
Tags: Addition Rule for Gaussian Binomial Coefficients

\begin{theorem}
:$\dbinom n m_q = \dbinom {n - 1} m_q q^m + \dbinom {n - 1} {m - 1}_q$
\end{theorem}

\begin{proof}
By definition of [[Definition:Gaussian Binomial Coefficient|Gaussian binomial coefficient]]:
{{begin-eqn}}
{{eqn | l = \binom n m_q
      | o = :=
      | r = \prod_{j \mathop = 0}^{m - 1} \dfrac {1 - q^{n - j} } {1 - q^{j + 1} }
      | c =
}}
{{eqn | r = \dfrac {\paren {1 - q^n} \paren {1 - q^{n - 1} } \dotsm \paren {1 - q^{n - m + 1} } } {\paren {1 - q^m} \paren {1 - q^{m - 1} } \dotsm \paren {1 - q^1} }
      | c =
}}
{{end-eqn}}
Thus:
{{begin-eqn}}
{{eqn | l = \dbinom {n - 1} m_q q^m + \dbinom {n - 1} {m - 1}_q
      | r = q^m \prod_{j \mathop = 0}^{m - 1} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } + \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} }
      | c = {{Defof|Gaussian Binomial Coefficient}}
}}
{{eqn | r = \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {q^m \dfrac {1 - q^{n - 1 - \paren {m - 1} } } {1 - q^{\paren {m - 1} + 1} } + 1}
      | c = extracting $\displaystyle \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} }$ as a factor
}}
{{eqn | r = \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {q^m \dfrac {1 - q^{n - m} } {1 - q^m} + 1}
      | c = simplifying
}}
{{eqn | r = \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {q^m \paren {1 - q^{n - m} } + \paren {1 - q^m} } {1 - q^m} }
      | c = placing over a common [[Definition:Denominator|denominator]]
}}
{{eqn | r = \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {q^m - q^n + 1 - q^m} {1 - q^m} }
      | c =
}}
{{eqn | r = \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {1 - q^n} {1 - q^m} }
      | c =
}}
{{eqn | r = \prod_{j \mathop = 0}^{m - 1} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} }
      | c =
}}
{{eqn | r = \binom n m_q
      | c = {{Defof|Gaussian Binomial Coefficient}}
}}
{{end-eqn}}
{{qed}}
\end{proof}

config: wiki


TITLE: Do linearly independent polynomials over number fields have linearly independent coordinates over the rationals?
QUESTION [3 upvotes]: Let $K$ be a number field with ring of integers $\mathcal{O}_K$.
Suppose $\{1, p_1, \dots, p_k\} \subseteq K[x]$ is a linearly independent family (over $K$).
Let $\{b_1, b_2, \dots, b_d\}$ be an integral basis in $\mathcal{O}_K$.
For each $i=1, \dots, k$, let $p_{i,1}, \dots, p_{i,d} \in \mathbb{Q}[x_1, \dots, x_d]$ be the coordinate polynomials of $p_i$, i.e.
\begin{align}
 p_i \left( \sum_{j=1}^d{x_jb_j} \right) = \sum_{j=1}^d{p_{i,j}(x_1, \dots, x_d)b_j}
\end{align}
for $x_1, \dots, x_d \in \mathbb{Q}$.
Is the family $\{1\} \cup \{p_{i,j} : 1 \le i \le k, 1 \le j \le d\} \subseteq \mathbb{Q}[x_1, \dots, x_d]$ linearly independent over $\mathbb{Q}$?
Example
A simple example, for which the answer is "yes", is $K = \mathbb{Q}(i)$ with the polynomials $p_1(x) = x$ and $p_2(x) = x^2$.
In the integral basis $\{1, i\}$, we can expand
\begin{align}
p_1(x_1 + ix_2) & = x_1 + ix_2 \\
p_2(x_1 + ix_2) & = (x_1^2 - x_2^2) + i(2x_1x_2),
\end{align}
so $p_{1,1}(x_1,x_2) = x_1$, $p_{1,2}(x_1,x_2) = x_2$, $p_{2,1}(x_1,x_2) = x_1^2 - x_2^2$, and $p_{2,2}(x_1,x_2) = 2x_1x_2$.
For this example, the set $\{1, p_{1,1}, p_{1,2}, p_{2,1}, p_{2,2}\} = \{1, x_1, x_2, x_1^2 - x_2^2, 2x_1x_2\}$ is linearly independent over $\mathbb{Q}$.

REPLY [1 votes]: I think you’ve made things difficult for yourself by stressing the ring structure of $K[x]$. Let me rather look at your question and your example in a different light, purely as a question in linear algebra.
Your choice of polynomials, $x$ and $x^2$, makes up a linearly independent set over $K$, in the $K$-vector space $K[x]$. You ask whether $(1x, ix, 1x^2, ix^2)$, as an ordered quadruple, forms a $\Bbb Q$-linearly independent set in the $\Bbb Q$-vector space $K[x]$. Looked at in this way, I think you say, “Of course”, since if $\lambda_1\cdot1x+\lambda_2ix+\lambda_3\cdot1x^2+\lambda_4ix^2=0$, then we have a statement of complex linear dependence $(\lambda_1+i\lambda_2)x+(\lambda_3+i\lambda_4)x^2=0$.
I was going to go into greater detail, looking at $K[x]$ as a tensor product
$K[x]\cong K\otimes_{\Bbb Q}\Bbb Q[x]$, but I don’t have time. If you’d like to see this, say so in a comment and I’ll get to it later.