text:
\begin{document}
\begin{abstract}
We construct a ring homomorphism comparing the tautological ring, fixing a point, of a closed smooth manifold with that of its stabilisation by $S^{2a} \times S^{2b}$.
\end{abstract}
\maketitle

\section{Introduction and statement of result}

\subsection{Tautological rings}

For a connected closed oriented smooth $d$-manifold $N$, the universal smooth fibre bundle with fibre $N$ may be described in terms of classifying spaces as
$$N \overset{i}\lra B\Diff^+(N, \star) \overset{\pi}\lra B\Diff^+(N).$$
Here $\Diff^+(N)$ denotes the topological group of orientation-preserving diffeomorphisms of $N$, and $\Diff^+(N, \star)$ denotes the subgroup of those diffeomorphisms fixing a marked point $\star \in N$. Assigning to a diffeomorphism fixing $\star \in N$ its derivative at this point gives a map
$$D_{\star} : B\Diff^+(N, \star) \lra B\GL_{d}^+(\bR) \simeq B\SO(d).$$
Using this we may pull back any cohomology class $c \in H^*(B\SO(d);\bQ)$ to give a class on $B\Diff^+(N, \star)$, which we continue to denote by $c$. We may then define classes
$$\kappa_c := \int_\pi c \in H^{|c|-d}(B\Diff^+(N);\bQ)$$
by integration along the fibres of the map $\pi$. These are known as tautological classes, $\kappa$-classes, or generalised Miller--Morita--Mumford classes. If $|c|=d$ then the degree zero cohomology class $\kappa_c$ is simply a characteristic number of $N$; the higher degree $\kappa_c$'s may be considered as analogues of characteristic numbers for families of manifolds.

The \emph{tautological ring} $R^*(N) \subset H^{*}(B\Diff^+(N);\bQ)$ is the subring generated by the classes $\kappa_c$. We may pull the classes $\kappa_c$ back along $\pi$ and hence also consider them as cohomology classes on $B\Diff^+(N, \star)$, where we continue to denote them by $\kappa_c$. A variant of $R^*(N)$, the \emph{tautological ring fixing a point} $R^*(N, \star) \subset H^{*}(B\Diff^+(N, \star);\bQ)$ is the subring generated by the classes $\kappa_c$ as well as the classes $c$.

\vspace{1ex}

\noindent\textbf{Context.} The rings $R^*(N)$ have been extensively studied in the case that $N$ is an oriented surface, as in this case $B\Diff^+(N)$ is a model for the moduli space of Riemann surfaces, cf.\ \cite{Mumford, Looijenga, Faber, Morita}. For manifolds of higher dimension they have recently been studied by Grigoriev, Galatius, and the author \cite{grigoriev-relations, galagriran-characteristic, RWPhenomena}, and in the case of 4-manifolds by Baraglia \cite{Baraglia}. In a different direction the \emph{vanishing} of tautological classes for various aspherical manifolds has been shown by Bustamante, Farrell, and Jiang \cite{BFJ}, and by Hebestreit, Land, L{\"u}ck, and the author \cite{HLLRW}. A variant of tautological rings for Poincar{\'e} complexes rather than manifolds has been studied by Prigge \cite{Prigge}.

\subsection{Main result}

The main result of this note concerns the case $d=2(a+b)$, and gives an explicit ring homomorphism $R^*(N \# S^{2a} \times S^{2b}, \star) \to R^*(N, \star)$. This is rather surprising because---as far as we can tell---there is no corresponding map $B\Diff^+(N, \star) \to B\Diff^+(N \# S^{2a} \times S^{2b}, \star)$, even at the level of rational cohomology groups.

In order to state our result we must first explain our conventions for describing the classes $c$. When $d=2n$ we have $H^*(B\SO(2n);\bQ) = \bQ[e, p_1, p_2, \ldots, p_{n-1}]$, the polynomial ring of the Euler class and Pontrjagin classes. There is a further Pontrjagin class, $p_n$, which agrees with $e^2$. Using this we may write any monomial in this ring as either $p_I$ or $e p_I$, with $I=(i_1, i_2, \ldots, i_r)$ having $1 \leq i_j \leq n$ and $p_I = p_{i_1} \cdots p_{i_r}$.

\begin{theorem}\label{thm:Stab}
Let $N$ be a $2(a+b)$-dimensional manifold. Then the formula
\begin{align*}
R^*(N \# S^{2a} \times S^{2b}, \star) &\lra R^*(N, \star)\\
\kappa_{p_I} & \longmapsto \kappa_{p_I}\\
\kappa_{ep_I} & \longmapsto \kappa_{ep_I} + 2 p_I\\
c &\longmapsto c
\end{align*}
gives a well-defined and surjective ring homomorphism.
\end{theorem}

\begin{remark}\
\begin{enumerate}[(i)]

\item The \emph{tautological ring fixing a disc} $R^*(N, D^d) \subset H^{*}(B\Diff^+(N, D^d);\bQ)$ is the subring generated by the classes $\kappa_c$. There are natural ring homomorphisms
$$R^*(N) \lra R^*(N,\star) \lra R^*(N, D^d)$$
sending $\kappa_c$ to $\kappa_c$, and the second map sending $c$ to 0. Considering $\Diff^+(N, D^d)$ as the group of diffeomorphisms of $N \setminus \mathrm{int}(D^d)$ fixing the boundary, there are natural maps $B\Diff^+(N, D^d) \to B\Diff^+(N \# M, D^d)$, and these induce ring homomorphisms
$$R^*(N \# M, D^d) \lra R^*(N, D^d),$$
sending $\kappa_c$ to $\kappa_c$. Theorem \ref{thm:Stab} may be viewed as a refinement of this map which does not require an entire disc to be fixed, but only a point.

\item Tautological rings can equally well be defined for homeomorphism groups of topological manifolds, but for our method smoothness is used in an essential way (we use that $\mathrm{Diff}^+(\bR^d)$ is homotopy equivalent to a compact Lie group).

\end{enumerate}
\end{remark}

Our method can more generally be used to compare tautological rings of $N$ and $N \# M$ when $M$ is a $2n$-manifold with an $n$-torus action satisfying certain cohomological hypotheses. In Section \ref{sec:General} we develop our construction in this generality, in Section \ref{sec:PfThm1} we verify the cohomological hypotheses in the case $M=S^{2a} \times S^{2b}$, thereby proving Theorem \ref{thm:Stab}, and in Section \ref{sec:CP2Ex} we explain the analogous result in the case $M=\mathbb{CP}^2$.

\begin{example}
Composing with the inclusion $i : N \to B\Diff^+(N,\star)$ of the fibre of the universal bundle gives a ring homomorphism
\begin{align*}
R^*(N \# S^{2k} \times S^{2k}, \star) &\lra H^*(N ; \bQ)\\
\kappa_{p_I} & \longmapsto 0\\
\kappa_{ep_I} & \longmapsto 2 p_I(TN)\\
c &\longmapsto c(TN).
\end{align*}
So if $p_I(TN) \neq 0 \in H^*(N;\bQ)$ then $\kappa_{ep_I} \neq 0 \in R^*(N \# S^{2k} \times S^{2k}, \star)$.
\end{example}

\begin{example}\label{ex:W}
Writing $W_g^{4k} = \#^g S^{2k} \times S^{2k}$, one consequence of Theorem \ref{thm:Stab} is that the sequence of Krull dimensions $\mathrm{Kdim} R^*(W_g^{4k}, \star)$ is non-decreasing with $g$. The morphism $R^*(W_g^{4k}) \to  R^*(W_g^{4k}, \star)$ is injective by the Becker--Gottlieb transfer \cite{beckegottl-transfer}: if $\pi : E \to B$ denotes the universal $W_g^{4k}$-bundle then the composition $\trf_\pi^* \circ \pi^*$ is multiplication by the Euler characteristic $\chi(W_g^{4k}) = 2+2g \neq 0$ and so $\pi^*$ is injective. By \cite[Theorem A (ii)]{RWPhenomena} the morphism $R^*(W_g^{4k}) \to  R^*(W_g^{4k}, \star)$ is in addition finite, so it follows that these rings have the same Krull dimensions and so the sequence $\mathrm{Kdim} R^*(W_g^{4k})$ is also non-decreasing with $g$.

This is in distinction with the manifolds $W_g^{4k+2} = \#^g S^{2k+1} \times S^{2k+1}$, as in \cite{galagriran-characteristic} it was shown that the sequence $\mathrm{Kdim} R^*(W_g^{4k+2})$ is $2k+1, 0, 2k, 2k, 2k,\ldots$ for $g=0,1,2,3,4,\ldots$.
\end{example}

\begin{example}
We have $R^*(S^{4k})= \bQ[\kappa_{ep_1}, \kappa_{ep_2}, \ldots, \kappa_{ep_{2k}}]$ (see \cite[Section 5.3]{galagriran-characteristic}), so by \cite[Theorem A (ii)]{RWPhenomena} the ring $R^*(S^{4k}, \star)$ also has Krull dimension $2k$. Thus $\mathrm{Kdim} R^*(W_g^{4k}) \geq 2k$ for all $g \geq 0$.
\end{example}

\begin{example}
In \cite[Corollary 4.18]{RWPhenomena} it was shown that $\mathrm{Kdim} R^*(S^2 \times S^2)$ is either 3 or 4, so it follows that $\mathrm{Kdim} R^*(W_g^{4}) \geq 3$ for all $g \geq 1$.
\end{example}

\begin{example}
In \cite[Proposition 1]{GKT} it was shown that for the $K3$ manifold $K$ one has $\kappa_{\cL_{i+1}} \neq 0 \in R^*(K)$ for $1 \leq i \leq 8$. As $\chi(K)=24 \neq 0$ the map $R^*(K) \to R^*(K, \star)$ is injective by the Becker--Gottlieb transfer as in Example \ref{ex:W}, so  $\kappa_{\cL_{i+1}} \neq 0 \in R^*(K, \star)$ and hence $\kappa_{\cL_{i+1}} \neq 0 \in R^*(K \# g S^2 \times S^2)$ for all $g \geq 0$ and $1 \leq i \leq 8$.
\end{example}

\subsection*{Acknowledgements}
The author was partially supported by the ERC under the European Union's Horizon 2020 research and innovation programme (grant agreement No.\ 756444), and by a Philip Leverhulme Prize from the Leverhulme Trust.

\section{The general construction}\label{sec:General}

\subsection{Parametrised connect-sum}

Let $(M, m_0)$ and $(N, n_0)$ be $d$-dimensional connected manifolds with marked points, and choose charts $\varphi_M : \bR^d \to M$ and  $\varphi_N : \bR^d \to N$ around these marked points.

\begin{definition}
Let $\Diff^+(M, \varphi_M)$ denote the group of diffeomorphisms $f :M \to M$ for which there exists an $A \in \SO(d)$ such that $f \circ \varphi_M = \varphi_M \circ A$, equipped with the $C^\infty$-topology. Define $\Diff^+(N, \varphi_N)$ in the same way.

More generally for a subset $X \subset M \setminus \varphi_M(\bR^d)$ let $\Diff^+(M, \varphi_M, X)$ denote the subgroup which fixes $X$ pointwise.
\end{definition}

These are just slightly unusual models for the group of diffeomorphisms fixing a point, as follows.

\begin{lemma}
The inclusion $\Diff^+(M, \varphi_M) \to \Diff^+(M, m_0)$ is a weak homotopy equivalence. Similarly for $\Diff^+(N, \varphi_N)$ and $\Diff^+(M, \varphi_M, X)$.
\end{lemma}
\begin{proof}[Proof sketch]
Combine the facts (i) that the inclusion $\SO(d) \to \GL^+_d(\bR)$ into the space of invertible matrices with positive determinant is an equivalence, and (ii) that the space of Riemannian metrics on $M$ is contractible.
\end{proof}

Taking the derivative at the marked point $m_0 = \varphi_M(0)$ gives a homomorphism
$$D_{m_0} : \Diff^+(M, \varphi_M, X) \lra \SO(d),$$
and similarly with $n_0 = \varphi_N(0)$ gives
$$D_{n_0} : \Diff^+(N, \varphi_N) \lra \SO(d).$$
Let $r : \SO(d) \to \SO(d)$ be given by conjugating by a reflection: the induced map $Br : B\SO(d) \to B\SO(d)$ corresponds to reversing orientation. For compactness we write $\overline{D}_{m_0} := r \circ D_{m_0}$. Using these maps we can form a homotopy pullback square
\begin{equation}\label{eq:MainSq}
\begin{tikzcd}
\mathcal{G} \arrow[rr, "f_M"] \arrow[d, "f_N"] &&  B\Diff^+(M, \varphi_M,  X) \arrow[d, "\overline{D}_{m_0}"]\\
B\Diff^+(N, \varphi_N) \arrow[rr, "D_{n_0}"] && B\SO(d).
\end{tikzcd}
\end{equation}
The space $\mathcal{G}$ (for ``glue") is equipped with the following data:
\begin{enumerate}[(i)]
\item an oriented orthogonal vector bundle $V \to \mathcal{G}$,
\item a smooth oriented $N$-bundle $\pi_N : E_N \to \mathcal{G}$ with an orientation-preserving embedding ${s}_N : V \to E_N$,
\item a smooth oriented $M$-bundle $\pi_M : E_M \to \mathcal{G}$ with an orientation-reversing embedding ${s}_M : V \to E_M$ and a disjoint embedding $\mathcal{G} \times X \to E_M$.
\end{enumerate}
Furthermore $\mathcal{G}$ is the universal example of a space equipped with this data. For a characteristic class
$$c \in  H^*(B\SO(d);\bQ)$$
we write $c = c(V) \in H^*(\mathcal{G};\bQ)$ for its pullback to $\mathcal{G}$. We also write $q : S(\bR \oplus V) \to \mathcal{G}$ for the associated $d$-dimensional sphere bundle.

\begin{proposition}\label{prop:Cobordism}\mbox{}
\begin{enumerate}[(i)]
\item\label{it:Cobordism:1} There is a smooth oriented ${M} \# N$-bundle $\pi_{{M} \# N} : E_{{M} \# N} \to \mathcal{G}$ which is equipped with an embedding $\mathcal{G} \times X \to E_{{M} \# N}$ over $\mathcal{G}$.

\item\label{it:Cobordism:2} There is a bundle of oriented cobordisms over $\mathcal{G}$
$$W : E_{{M}} \sqcup E_N \leadsto E_{{M} \# N} \sqcup S(\bR \oplus V),$$
 which is equipped with
\begin{enumerate}[(a)]
\item an embedding $\mathcal{G} \times [0,1] \times X  \to W$ over $\mathcal{G}$, extending the embeddings of $\mathcal{G} \times X$ into $E_M$ and $E_{M \# N}$,
\item a $d$-dimensional oriented vector bundle which restricts to the vertical tangent bundle over the boundary.
\end{enumerate}
\end{enumerate}
\end{proposition}

We write
$$f_{M\# N}: \mathcal{G} \lra B\Diff^+({M} \# N, X)$$
for the map which classifies the oriented $M \# N$-bundle given by Proposition \ref{prop:Cobordism} (\ref{it:Cobordism:1}).

\begin{proof}[Proof of Proposition \ref{prop:Cobordism}]
We form $E_{{M} \# N}$ by gluing together
$$E_{{M}} \setminus \mathrm{int}(D(V)),\quad D^1 \times S(V),\quad \text{ and }\quad E_{N} \setminus \mathrm{int}(D(V))$$
along the natural identifications
$$\partial (E_{{N}} \setminus \mathrm{int}(D(V))) \cong \{-1\} \times S(V)\quad \text{ and} \quad \partial (E_{{M}} \setminus \mathrm{int}(D(V))) \cong \{+1\} \times S(V),$$
 with smooth structure induced by the evident radial collar of $D(V) \subset V$. We have $\mathcal{G} \times X \subset E_{{M}} \setminus \mathrm{int}(D(V)) \subset E_{{M} \# N}$, and $E_{M \# N}$ admits a unique orientation compatible with those of $E_{{N}} \setminus \mathrm{int}(D(V))$ and $E_{{M}} \setminus \mathrm{int}(D(V))$. This establishes (\ref{it:Cobordism:1}).

To produce the cobordism data we first make a local construction. Let us write $U$ for the inner product space $\bR^d$ with an orientation $\det(U) \in \Lambda^d U$. Consider the elementary cobordism $W'_{\text{loc}}$ between $S^0 \times D(U)$ and $D^1 \times S(U)$,  realised $\SO(U)$-equivariantly by a codimension zero submanifold with corners
$$W'_{\text{loc}}  \subset \bR \times U$$
equipped with the Morse function $f(z, u) = |u|^2 - z^2$ and the orientation $\tfrac{\partial}{\partial z} \wedge \det(U)$. Remove the unit disc around $(0,0)$ from $W'_{\text{loc}}$ to obtain $W_{\text{loc}}$ as shown in Figure \ref{fig:Morse}, whose new boundary component is $S(U \oplus \bR)$. We consider $W_{\text{loc}}$ as a $\SO(U)$-equivariant oriented cobordism of manifolds with boundary
$$W_{\text{loc}} : S^0 \times D(U) \leadsto D^1 \times S(U) \sqcup S(\bR \oplus U).$$
As usual, we equip the boundary components of an oriented cobordism with the induced orientation on outgoing boundaries and the opposite of the induced orientation on incoming boundaries. (The induced orientation is that which agrees with prepending the outwards-pointing normal vector.) Thus in this case the orientation on $\{-1\} \times D(U)$ agrees with that inherited from $U$, that on $\{+1\} \times D(U)$ is the opposite of that inherited from $U$, and that on $S(\bR \oplus U)$ is the opposite of that induced from $D(\bR \oplus U)$.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=10cm]{Morse}
\caption{The cobordism $W_{\text{loc}}$.}\label{fig:Morse}
\end{center}
\end{figure}

The kernel of the differential $Df$ defines a $\SO(U)$-equivariant $d$-dimensional oriented subbundle $\tau$ of $TW'_{\text{loc}}$ on the complement of the point $(0,0)$, restricting to the oriented tangent bundles of $\{-1\} \times D(U)$ and $D^1 \times S(U)$, and the oppositely-oriented tangent bundle over $\{+1\} \times D(U)$, respectively, as these are level sets of $f$. The bundle $\tau$ restricts to an oriented vector bundle of the same name on $W_{\text{loc}}$, and hence to an oriented vector bundle on $S(U \oplus \bR)$, which we now identify.

At the point $(z, u) \in S(\bR \oplus U)$ the differential $D_{(z,u)} f : \bR \oplus U \to \bR$ is given by inner product with $2(-z,u)$, so its kernel is identified with the tangent space $T_{(-z,u)} S(\bR \oplus U)$ though with the opposite orientation. As $(z,u) \mapsto (-z,u)$ gives a (orientation-reversing) diffeomorphism of $S(\bR \oplus U)$ commuting with the $\SO(U)$-action, there is $\SO(U)$-equivariant identification of oriented vector bundles between $\tau\vert_{S(\bR \oplus U)}$ and $T S(\bR \oplus U)$.

We implant this local construction as follows. Applying the local construction fibrewise the oriented orthogonal vector bundle $V \to \mathcal{G}$ gives a bundle of cobordisms of manifolds with boundary
$$W_{\text{loc}}(V) : S^0 \times D(V) \leadsto D^1 \times S(V) \sqcup S(\bR \oplus V)$$
over $\mathcal{G}$, equipped with a vector bundle $\tau(V)$ which agrees with the tangent bundle over the incoming and outgoing boundaries. We then construct $W$ as
$$\left([0,1] \times (E_{{M}} \setminus \mathrm{int}(D(V)) \sqcup E_{N} \setminus \mathrm{int}(D(V))) \right) \cup_{[0,1] \times S^0 \times S(V)} W_{\text{loc}}(V).$$
This is a bundle of oriented cobordisms $E_{{M}} \sqcup E_N \leadsto E_{{M} \# N} \sqcup S(\bR \oplus V)$, and contains $\mathcal{G} \times [0,1] \times X \subset [0,1] \times E_{{M}} \setminus \mathrm{int}(D(V))$. The bundle $\tau(V)$ extends to a vector bundle on $W$ by taking the vertical tangent bundle of $E_{{M}} \setminus \mathrm{int}(D(V)) \sqcup E_{N} \setminus \mathrm{int}(D(V))$. This establishes (\ref{it:Cobordism:2}).
\end{proof}

From now on let us suppose that $d=2n$, so that the available characteristic classes are
$$H^*(B\SO(2n);\bQ) = \bQ[p_1, p_2, \ldots, p_{n-1}, e].$$
As mentioned in the introduction, we use that $e^2 = p_n$ to write monomials in this ring as either $p_I$ or $e p_I$, with $I=(i_1, i_2, \ldots, i_r)$ having $1 \leq i_j \leq n$.

\begin{lemma}\label{lem:SphereCalc}
Let $V \to B$ be a $2n$-dimensional oriented orthogonal vector bundle, and $q : S(\bR \oplus V) \to B$ be the associated oriented $S^{2n}$-bundle. Then
$$\kappa_{p_I}(q) = 0 \quad\quad \text{ and } \quad\quad \kappa_{ep_I}(q) = 2p_I(V).$$
\end{lemma}
\begin{proof}
We have $T_q S(\bR \oplus V) \oplus \bR \cong \bR \oplus q^*V$ and hence the cohomology classes $p_i(T_q S(\bR \oplus V)) = q^*p_i(V)$ are pulled back from the base. Then $\int_q p_I(T_q S(\bR \oplus V)) = \int_q q^*(p_I(V))=0$ by the projection formula (i.e.\ the fact that fibre integration is a map of modules over the cohomology of the base), and similarly
\begin{align*}
\int_q e(T_q S(\bR \oplus V))p_I(T_q S(\bR \oplus V)) &= \int_q e(T_q S(\bR \oplus V)) q^*(p_I(V))\\
&= \left(\int_q e(T_q S(\bR \oplus V))\right) p_I(V)\\
 &= \chi(S^{2n}) p_I(V) = 2 p_I(V).\qedhere
\end{align*}
\end{proof}

\begin{corollary}\label{cor:SumFormula}
There are identities
\begin{align*}
\kappa_{p_I}(\pi_{{M} \# N}) &= \kappa_{p_I}(\pi_M) + \kappa_{p_I}(\pi_N),\\
\kappa_{ep_I}(\pi_{{M} \# N}) &= \kappa_{ep_I}(\pi_M) + \kappa_{ep_I}(\pi_N) - 2p_I(V),
\end{align*}
in $H^*(\mathcal{G};\bQ)$.
\end{corollary}
\begin{proof}
Consider the bundle of cobordisms $W : E_{{M}} \sqcup E_N \leadsto E_{{M} \# N} \sqcup S(\bR \oplus V)$ constructed in Proposition \ref{prop:Cobordism} (\ref{it:Cobordism:2}), with its oriented $2n$-dimensional vector bundle which restricts to the vertical tangent bundles over the two ends. By Stokes' theorem, for any $c \in H^*(B\SO(2n);\bQ)$ we therefore have
$$\int_{\pi_{{M} \# N}} c(T_{\pi_{{M} \# N}} E_{{M} \# N}) + \int_q c(T_q S(\bR \oplus V))=  \int_{\pi_{{M}}} c(T_{\pi_{{M}}} E_{{M}}) + \int_{\pi_N} c(T_{\pi_N} E_N).$$
The result follows by using Lemma \ref{lem:SphereCalc}.
\end{proof}

\subsection{Torus actions}

If the $n$-torus $T$ acts on the $2n$-manifold $M$ fixing $m_0 \in M$ and $X = m_1 \in M$, then by choosing $\varphi_M$ to be an equivariant orthogonal chart around $m_0$ (obtained for example by exponentiating with respect to a $T$-invariant Riemannian metric) we have homomorphisms
$$T \overset{\phi}\lra \Diff^+(M, \varphi_M, m_1) \overset{\overline{D}_{m_0}}\lra \SO(2n).$$
We may then form the following commutative cube, in which the front face is \eqref{eq:MainSq}, the map $i^T : BT \to B\SO(2n)$ is $B(\overline{D}_{m_0} \circ \phi)$, and the remaining faces are developed by taking homotopy pullbacks.

\[
\begin{tikzcd}[row sep=2.5em, column sep = 0em]
\mathcal{G}_T \arrow[rr] \arrow[dr,swap, "i^\mathcal{G}"] \arrow[dd,swap] &&
  B\Diff^+_T(M, \varphi_M, m_1) \arrow[dd,swap, near start] \arrow[dr, "i^M"] \\
& \mathcal{G} \arrow[rr,crossing over, near start, "f_M"] &&
  B\Diff^+(M, \varphi_M, m_1) \arrow[dd, "\overline{D}_{m_0}"] \\
B\Diff^+_T(N, \varphi_N) \arrow[uu, dotted, bend left, "s^\phi"] \arrow[rr, near end, "D_{n_0}^T"] \arrow[dr,swap, "i^N"] && BT \arrow[dr,swap, "i^T"] \arrow[ur, "\phi", dotted] \arrow[uu, dotted, bend left] \\
& B\Diff^+(N, \varphi_N) \arrow[rr, "D_{n_0}"] \arrow[uu,<-,crossing over, near end, "f_N"]&& B\SO(2n)
\end{tikzcd}
\]

The lift $\phi$ determines a section $BT \to B\Diff^+_T(M, \varphi_M, m_1)$ and hence, by pullback, a section $s^\phi : B\Diff^+_T(N, \varphi_N) \to \mathcal{G}_T$. Furthermore, taking the derivative at $m_1$ gives a map
$$D_{m_1} : B\Diff^+(M, \varphi_M, m_1) \lra B\GL_{2n}^+(\bR) \simeq B\SO(2n).$$

\begin{lemma}\label{lem:CalcComp}
On tautological classes the composition
$$\varphi: B\Diff^+_T(N, \varphi_N) \overset{s^\phi}\lra \mathcal{G}_T \overset{i^\mathcal{G}}\lra \mathcal{G} \overset{f_{M \# N}}\lra B\Diff^+({M} \# N, m_1)$$
satisfies
\begin{align*}
\varphi^* \kappa_{p_I} &= (i^N)^*(\kappa_{p_I}) + (D_{n_0}^T)^*\phi^*(\kappa_{p_I})\\
\varphi^*\kappa_{ep_I} &= (i^N)^*(\kappa_{ep_I} - 2(D_{n_0})^*p_I) + (D_{n_0}^T)^*\phi^*(\kappa_{ep_I})\\
\varphi^* c &= (D_{n_0}^T)^*\phi^*(D_{m_1})^* c.
\end{align*}
\end{lemma}
\begin{proof}
By Corollary \ref{cor:SumFormula} we have
\begin{align*}
(f_{M \# N})^* \kappa_{p_I} &= \kappa_{p_I}(\pi_M) + \kappa_{p_I}(\pi_N)\\
(f_{M \# N})^*\kappa_{ep_I} &= \kappa_{ep_I}(\pi_M) + \kappa_{ep_I}(\pi_N) - 2p_I.
\end{align*}
When we pull this back to $B\Diff^+_T(N, \varphi_N)$ the classes $\kappa_c(\pi_N)$ can be written as $(i^N)^*\kappa_c$, and the classes $p_I$ can be written as $(i^N)^*(D_{n_0})^*p_I$. The classes $\kappa_c(\pi_M)$ pulled back to $B\Diff^+_T(N, \varphi_N)$ may be written as $(D^T_{n_0})^* \phi^* \kappa_c$.

Finally, Proposition \ref{prop:Cobordism} (\ref{it:Cobordism:2}) implies that
\[
\begin{tikzcd}
\mathcal{G} \arrow[r, "f_{M \# N}"] \arrow[d, "f_M"]& B\Diff^+({M} \# N, m_1) \arrow[d, "D_{m_1}"]\\
B\Diff^+(M, \varphi_M, m_1) \arrow[r, "D_{m_1}"] & B\SO(2n)
\end{tikzcd}
\]
commutes up to homotopy, which with the cube above shows that the composition
$$B\Diff^+_T(N, \varphi_N) \overset{s^\phi}\lra \mathcal{G}_T \overset{i^\mathcal{G}}\lra \mathcal{G} \overset{f_{M \# N}}\lra B\Diff^+({M} \# N, m_1) \overset{D_{m_1}}\lra B\GL_{2n}^+(\bR)$$
agrees with $B\Diff^+_T(N, \varphi_N) \overset{D^T_{n_0}}\to BT \overset{\phi}\to B\Diff^+(M, \varphi_M, m_1) \overset{D_{m_1}}\to B\GL_{2n}^+(\bR)$ up to homotopy.
\end{proof}

To proceed we require $\overline{D}_{m_0} \circ \phi : T \to\SO(2n)$ to be injective, in which case it is the inclusion of a maximal torus.

\begin{lemma}
The homomorphism $\overline{D}_{m_0} \circ \phi$ is injective if and only if $m_0 \in M$ is an isolated fixed point of this torus action.
\end{lemma}
\begin{proof}
If this homomorphism is not injective then its image is a torus of rank $\leq n-1$, which may therefore be conjugated into the maximal torus of $\SO(2n-1) \leq \SO(2n)$: in this case $T$ fixes a tangent vector at $m_0$, and since $T$ acts linearly in a chart around this point it follows that $m_0$ is not an isolated fixed point.

Conversely, if $m_0$ is not an isolated fixed point then this torus fixes a non-zero vector in $T_{m_0} M$, so lies in some $\SO(2n-1)$, and hence cannot be injective (by dimension of the maximal torus of $\SO(2n-1)$).
\end{proof}

Thus if $m_0$ is an isolated fixed point then the map $\overline{D}_{m_0} \circ \phi : T \to \SO(2n)$ is the inclusion of a maximal torus. We use this in the following way. The homotopy fibre of the map $i^N$ is then $\SO(2n)/T$ which has non-zero Euler characteristic (it is the order of the Weyl group of $\SO(2n)$), and therefore just as in Example \ref{ex:W} the Becker--Gottlieb
transfer shows that the ring homomorphism
$$(i^N)^* : H^*(B\Diff^+(N, \varphi_N);\bQ) \lra H^*(B\Diff^+_T(N, \varphi_N);\bQ)$$
is injective. Thus:
\begin{enumerate}[(i)]
\item If for each $c \in H^*(B\SO(2n);\bQ)$ we have $(D_{n_0}^T)^*\phi^*(\kappa_{c}) = (i^N)^* q_c$ for some (unique) $q_c \in R^*(N, \star)$, then the function
\begin{align*}
R^*({M} \# N) &\lra R^*(N, \star)\\
\kappa_{p_I} &\longmapsto \kappa_{p_I} + q_{p_I}\\
\kappa_{ep_I} &\longmapsto \kappa_{ep_I} + q_{e p_I} - 2p_I
\end{align*}
is a well-defined ring homomorphism.

\item If in addition for each $c \in H^*(B\SO(2n);\bQ)$ we have $(D_{n_0}^T)^*\phi^*(D_{m_1})^* c = (i^N)^* r_c$ for some (unique) $r_c \in R^*(N, \star)$, then the function
\begin{align*}
R^*({M} \# N, \star) &\lra R^*(N, \star)\\
\kappa_{p_I} &\longmapsto \kappa_{p_I} + q_{p_I}\\
\kappa_{ep_I} &\longmapsto \kappa_{ep_I} + q_{e p_I} - 2p_I\\
c &\longmapsto r_c
\end{align*}
is a well-defined ring homomorphism.
\end{enumerate}

For these to hold we must impose conditions on the torus action on $M$. We do not try to pursue this in its greatest generality, and instead treat two special cases.

\section{Proof of Theorem \ref{thm:Stab}: Stabilisation by $S^{2a} \times S^{2b}$}\label{sec:PfThm1}

We consider $S^{2k} = (\bR^{2k})^+$ with the usual $\SO(2k)$-action, and let the standard maximal torus $T = T^{a+b} = T^{a} \times T^{b} \leq \SO(2a) \times \SO(2b)$ act on $M = S^{2a} \times S^{2b}$. We write $\zeta$ for the corresponding oriented $2(a+b)$-dimensional representation of $T$, and $\bar{\zeta}$ for the same representation with opposite orientation.

\begin{lemma}\label{lem:FPData}
The $T$-action on $S^{2a} \times S^{2b}$ fixes $\{(0,0), (0,\infty), (\infty,0), (\infty,\infty)\}$. The $T$-representations at these points are all isomorphic to $\zeta$, but as oriented representations they are isomorphic to the $\zeta$ at $\{(0,0), (\infty,\infty)\}$ and to $\bar{\zeta}$ at $\{(0,\infty), (\infty,0)\}$.
\end{lemma}
\begin{proof}
The $T^k$-action on $S^{2k} = (\bR^{2k})^+$ fixes precisely 0 and $\infty$. The normal representation at 0 is the standard oriented representation $T^k \leq \SO(2k)$. The orientation-reversing reflection in the equator interchanges the fixed points $0$ and $\infty$ and commutes with the $T^k$-action, so the normal representation at $\infty$ is the opposite of the standard representation. Taking products gives the claimed description.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:Stab}]
For $m_0 = (0,0) \in S^{2a} \times S^{2b}$ with orthogonal chart given by the product of the two open upper hemispheres, and $X = m_1 = (0, \infty) \in S^{2a} \times S^{2b}$, there is a corresponding map
$$\phi : BT \lra B\Diff^+(S^{2a} \times S^{2b}, \varphi_{S^{2a} \times S^{2b}},  m_1).$$

\begin{lemma}
This satisfies $\phi^*\kappa_{p_I}=0$ and $\phi^* \kappa_{ep_I} =  (i^T)^*(4 p_I)$.
\end{lemma}
\begin{proof}
We will use the localisation theorem in $T$-equivariant rational cohomology $H^*_T(-)$, in the following special case; see \cite[p.\ 366]{AP} for an exposition.

Let $T$ act on an oriented $2n$-manifold $M$ with isolated fixed points $\{x_1, \ldots, x_r\}$, and let $e_j \in H^*_T = H^*_T(pt)$ denote the Euler class of the oriented $T$-representation on the tangent space $T_{x_j} M$. Let $S \subset H^*_T$ denote the multiplicative subset of non-zero elements. Then the $S$-localised fibre-integration map
$$\int_\pi : S^{-1} H^*_T(M) \lra S^{-1}H^{*-2n}_T$$
for the bundle $\pi : M \times_T ET \to \{*\} \times_T ET = BT$ may be expressed as
$$\int_\pi t = \sum_{j=1}^r \frac{t\vert_{x_j}}{e_j}.$$
As $H^*_T$ is an integral domain this determines the unlocalised fibre-integration map.

We apply this to the $T$-action on $S^{2a} \times S^{2b}$. By Lemma \ref{lem:FPData}, tangent representations at all fixed points are isomorphic to $\zeta$, so have Pontrjagin classes $p_i(\zeta)$, but taking orientation into account the Euler classes of the tangent representations at $(0,0)$ and $(\infty, \infty)$ are $e(\zeta)$ and at $(0,\infty)$ and $(\infty, 0)$ are $e(\bar{\zeta}) = - e(\zeta)$. Thus we have
$$\phi^*\kappa_{p_I} = \int_\pi p_I(T(S^{2a} \times S^{2b})) = \frac{p_I(\zeta)}{e(\zeta)}+ \frac{p_I(\zeta)}{e(\zeta)} + \frac{p_I(\zeta)}{-e(\zeta)} + \frac{p_I(\zeta)}{-e(\zeta)}=0$$
and similarly
\begin{align*}
\phi^*\kappa_{ep_I}  &= \frac{e(\zeta)p_I(\zeta)}{e(\zeta)}+ \frac{e(\zeta)p_I(\zeta)}{e(\zeta)} + \frac{-e(\zeta)p_I(\zeta)}{-e(\zeta)} + \frac{-e(\zeta)p_I(\zeta)}{-e(\zeta)}\\
&= 4 p_I(\zeta) = (i_T)^*(4 p_I).\qedhere
\end{align*}
\end{proof}

As the oriented tangent representation at $m_1 \in S^{2a} \times S^{2b}$ is isomorphic but with opposite orientation to that at $m_0 \in S^{2a} \times S^{2b}$, so that $D_{m_1} \simeq \overline{D}_{m_0}$, we have
\begin{align*}
(D_{n_0}^T)^*\phi^*(\kappa_{p_I}) &= 0\\
(D_{n_0}^T)^*\phi^*(\kappa_{ep_I}) &= (i^N)^*(D_{n_0})^*(4 p_I)\\
(D_{n_0}^T)^*\phi^*(D_{m_1})^* ({c}) &= (i^N)^*(D_{n_0})^*(c).
\end{align*}
By the discussion above the formula
\begin{align*}
R^*({S^{2a} \times S^{2b}} \# N, \star) &\lra R^*(N, \star)\\
\kappa_{p_I} & \longmapsto \kappa_{p_I}\\
\kappa_{ep_I} & \longmapsto \kappa_{ep_I} + 2 p_I\\
c & \longmapsto c
\end{align*}
is then a well-defined ring homomorphism, which is clearly surjective. This proves Theorem \ref{thm:Stab}.
\end{proof}

\begin{remark}
In this argument we could have chosen the fixed point $m_1 = (\infty, \infty)$, whose tangential $T$-representation is oriented isomorphic with that at $m_0$. This has the disconcerting effect that the formula
\begin{align*}
R^*({S^{2a} \times S^{2b}} \# N, \star) &\lra R^*(N, \star)\\
\kappa_{p_I} & \longmapsto \kappa_{p_I}\\
\kappa_{ep_I} & \longmapsto \kappa_{ep_I} + 2 p_I\\
c &\longmapsto \bar{c}
\end{align*}
also gives a well-defined ring homomorphism, where $c \mapsto \bar{c}$ is the automorphism of $H^*(B\SO(2n);\bQ)$ induced by conjugation by a reflection.
\end{remark}

\section{Stabilisation by $\mathbb{CP}^2$}\label{sec:CP2Ex}

As a further example of the method, consider $M = {\mathbb{CP}}^2$ with the 2-torus action
\begin{align*}
S^1 \times S^1 \times {\mathbb{CP}}^2 &\lra {\mathbb{CP}}^2\\
(\xi_1, \xi_2, [z_0 : z_1: z_2]) &\longmapsto [z_0 : \xi_1 z_1 : \xi_2 z_2].
\end{align*}
We let $m_0 = [1 : 0 : 0]$ and $m_1 = [0 : 1 : 0]$; the third fixed point is $[0:0:1]$. The torus action gives a map
$$\phi : BT \lra B\Diff^+({\mathbb{CP}}^2, \varphi_{{\mathbb{CP}}^2}, m_1).$$
The map $D_{m_0} \circ \phi$ is induced by the standard inclusion $T \to \SO(4)$ of a maximal torus. If we let $H^*(BT;\bQ)=\bQ[x_1, x_2]$ then the representation at $m_0$ has $e = x_1 x_2$ and $p_1 = x_1^2 + x_2^2$. At the other fixed points we have $e = x_1(x_1-x_2)$ and $p_1 = x_1^2 + (x_2 - x_1)^2$, and $e = x_2(x_2-x_1)$ and $p_1 = x_2^2 + (x_1 - x_2)^2$, so by localisation in equivariant cohomology we may calculate
\begin{align*}
\phi^* \kappa_{e^a p_1^b} &=  \frac{(x_1 x_2)^a (x_1^2 + x_2^2)^b}{x_1 x_2} + \frac{(x_1^2 - x_1x_2)^a (x_1^2 + (x_2 - x_1)^2)^b}{x_1^2 - x_1x_2}\\
& \quad\quad\quad\quad\quad\quad + \frac{(x_2^2 - x_1 x_2)^a (x_2^2 + (x_1 - x_2)^2)^b}{x_2^2 - x_1 x_2}.
\end{align*}
When expanded out this is a polynomial in the $x_i$, and in fact is an even symmetric polynomial in these variables and so can be written in terms of $e = x_1 x_2$ and $p_1 = x_1^2 + x_2^2$. Call the resulting polynomial $q_{a,b}(e, p_1)$. The first few are
$$q_{0,1} = 3;\quad q_{1,0} = 3; $$
$$q_{0,2} = 7p_1 - 7e; \quad q_{1,1} = 4p_1 - 4e;\quad q_{2,0} = p_1-e;$$
$$q_{0,3} = 13(p_1^2 + e^2 -2 e p_1);\quad q_{1,2} = 6(p_1^2 + e^2 -2e p_1);\quad q_{2,1} = 2(p_1^2 + e^2 - 2 e p_1);$$
and $q_{3,0} = p_1^2 + e^2 - 2 e p_1$.

It then follows from our general discussion that the formula
\begin{align*}
R^*(N^4 \# \mathbb{CP}^2) &\lra R^*(N^4, \star)\\
\kappa_{e^a p_1^b} & \longmapsto \kappa_{e^a p_1^b} + \begin{cases}
 q_{a,b}(e, p_1) - 2 e^{a-1} p_1^b & \text{if $a$ is odd}\\
 q_{a,b}(e, p_1)  & \text{if $a$ is even}
\end{cases}
\end{align*}
gives a well-defined ring homomorphism. (This cannot be promoted to a ring homomorphism from $R^*(N^4 \# \mathbb{CP}^2, \star)$, because the Euler and Pontrjagin classes of the normal $T$-representation at $[0 : 1 : 0]$ (or $[0:0:1]$) cannot be expressed in terms of those at $m_0$.)

\begin{remark}
Baraglia \cite{Baraglia} has recently determined the tautological rings of $\mathbb{CP}^2$ and $\mathbb{CP}^2 \# \mathbb{CP}^2$, and more generally given a gauge-theoretic technique for obtaining relations in tautological rings of definite 4-manifolds. Up to a change of variables the polynomials $q_{a,b}$ also arise there.
\end{remark}

\bibliographystyle{amsalpha}
\bibliography{biblio}

\end{document}


TITLE: Prove that $x^n(1−x)^n$ has its maximum at x=1/2.
QUESTION [0 upvotes]: I was trying to prove that $f_n(x)=x^n(1-x)^n$ converges uniformly on [0,1], and found this: Convergence of $f_n(x)=x^n(1-x)^n$
But I've got stuck on how to prove that $f_n(x)$ has a maximum on 1/2. Can you guys give me an idea?

REPLY [1 votes]: More generally,
if
$f(x) = x^a(1-x)^b
$
where
$a, b \ge 1$,
then
$\begin{array}\\
f'(x)
&=ax^{a-1}(1-x)^b-x^ab(1-x)^{b-1}\\
&=x^{a-1}(1-x)^{b-1}(a(1-x)-bx)\\
&=x^{a-1}(1-x)^{b-1}(a-x(a+b))\\
\end{array}
$
so
$f'(x) = 0$
at
$x = \dfrac{a}{a+b}
$
when
$\begin{array}\\
f(x)
&=(\dfrac{a}{a+b})^a(1-\dfrac{a}{a+b})^b\\
&=(\dfrac{a}{a+b})^a(\dfrac{b}{a+b})^b\\
&=\dfrac{a^ab^b}{(a+b)^{a+b}}\\
\end{array}
$
If $a=b$,
the max is at $\dfrac12$
and the value is
$\dfrac{a^{2a}}{(2a)^{2a}}
=\dfrac{1}{2^{2a}}
$.


TITLE: Is both $\{\}$ and $\{\{\}\}$ same element $?$
QUESTION [3 upvotes]: Let $P(S)$ denotes the power set of set $S$. Which of the following is always true$?$

$P(P(S)) = P(S)$
$P(S) ∩ P(P(S)) = \{ Ø \}$
$P(S) ∩ S = P(S)$
$S ∉ P(S)$

I try to explain $:$
If $S$ is the set $\{x, y, z \},$ then the subsets of S are:
${}$ (also denoted $\phi,$ the empty set)
$\{x\},
\{y\},
\{z\},
\{x, y \},
\{x, z \},
\{y, z \},
\{x, y, z \}$
and hence the power set of S is i.e.,
$P(S) =$ $\{\{\}, \{x\}, \{y\}, \{z\}, \{x, y\}, \{x, z\}, \{y, z\}, \{x, y, z\}\}$.
Similarly ,
$P(P(S))=\{\{\{\}\}, \{\{x\}\}, \{\{y\}\}, \{\{z\}\}, \{\{x, y\}\}, \{\{x, z\}\}, \{\{y, z\}\}, \{\{x, y, z\}\}\}.....\}$
therefore ,
$P(S) ∩ P(P(S)) = \{ Ø \}$
Note that $\{ Ø \}$ is always element of powerset of a set , and also $\{ Ø \}$ is the subset of a set , in other words all subset of a set is a powerset .

My question is $:$  both $\{\}$ and $\{\{\}\}$ same element ?

REPLY [5 votes]: No, $\{\}$ and $\{\{\}\}$ are two different sets. You can see that by noting that there's something that is an element of one but not of the other:
$$ \{\}\notin \{\} \qquad\text{but}\qquad \{\}\in\{\{\}\} $$
$\{\}$ is a set that has no elements. It is the same set that is also notated $\varnothing$.
$\{\{\}\}$ is a set which has exactly one element, namely $\{\}$. Since $\{\}$ is the same as $\varnothing$, a different name for $\{\{\}\}$ would be $\{\varnothing\}$.

REPLY [4 votes]: No, $\{\}$ is the empty set, and $\{ \{ \} \}$ is the set containing the empty set.  They aren't the same -- $\{\}$ has no elements, and $\{ \{ \} \}$ has one element.
By the way, in $P(P(S))$, you forgot to add the element $\{ \}$, since the empty set is a subset of every set.

REPLY [3 votes]: No, $\{\}$ and $\{\{\}\}$ are not the same. Think of sets as bags. $\{\}$ is an empty bag. $\{\{\}\}$ is a bag with an empty bag within it. Therefore the outermost bag is not empty: It has a bag inside it.

For the original question, you are wrong, lets consider all four possibilities.

No. By Cantor's theorem, we always have $|P(P(S))| > |P(S)|$. Hence they cannot be equal. Alternatively, let $S=\{\}$ and write out.

Consider $S=\{\{\}\}$. Then $P( S)=\{\{\},\{\{\}\}\}$ and $P(P(S))=\{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}  \}$, hence $P(S) \cap P(P(S)) = \{\{\},\{\{\}\}\}$.

No. Note that $A \cap B \subseteq B$ for all sets $A,B$. Hence  $S \cap P(S) \subseteq S$, hence $$|S \cap P(S)| \leq |S| < |P(S)|$$
hence they are not equal.

By definition $S \subseteq S$ and thus $S \in P(S)$.

Therefore, none of the statements is true.


TITLE: Express how many ways you can select a representative
QUESTION [2 upvotes]: Assume that a school has these three teams: Chess team with 10 members, Checkers team with 15 members, and College bowl team with 20 members.
In how many ways can we select representatives of the school if there should be:

exactly 1 representative from each team.
2 persons, and they should be from different teams.
1, 2, or 3 persons but no two from the same team.
2 persons, both from the same team.
2 persons from any team.

Answers

$20*15*10$ using the product rule
$10 \cdot 15 + 10 \cdot 20 + 15 \cdot 20$

REPLY [2 votes]: Hints:
These will rely on various applications of the multiplication principle, permutations, combinations, and the summation principle.
1: There will be one representative from each team.  Who is the representative from the checkers team?  Who is the representative from the chess team?  Who is the representative from the College bowl team?
2: Consider the set of all 2 person groups with no restriction on what team they come from (same answer as problem 5).  How many of those are "bad" selections such that they came from the same team (same as problem 4)?  Use inclusion-exclusion to find the number of "good" selections.
3: Split this into cases.  If 1 person, choose that one person.  If 2 people, with no two from same team, this is same answer as problem 2.  If 3 people, this is one from each team (same as problem 1).
4: Split this into cases.  If both are from the chess team, which two are they?  If both are from the checkers team, which two are they?  If both are from the college bowl team, which two are they?  Use combinations to answer those questions, and finish by using summation rule.
5: There are no restrictions whatsoever, so 2 people out of the total population.


TITLE: Is it possible to realize the Klein bottle as a linear group orbit?
QUESTION [10 upvotes]: Does there exists a Lie group $ G $, a finite dimensional representation $ \pi: G \to GL(V) $, and a vector $ v \in V $ such that the orbit
$$
\mathcal{O}_v=\{ \pi(g)v: g\in G  \}
$$
is diffeomorphic to the Klein bottle?
The Klein bottle, $ K $, is homogeneous for the special Euclidean group of the plane
$$
SE_2= \left \{ \
\begin{bmatrix}
a & b & x \\
-b & a & y \\
0 & 0 & 1
\end{bmatrix} : a^2+b^2=1 \right \}
$$
Because there is a one parameter group $ H $ of translations up each vertical line
$$
H= \left \{ \
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & y \\
0 & 0 & 1
\end{bmatrix} : y \in \mathbb{R} \right \}
$$
There is also an element that shifts horizontally by one unit
$$
b:=\begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
$$
If we mod out $ SE_2 $ by the group generated by $ \langle H,b \rangle \cong \mathbb{R} \times \mathbb{Z} $ we just get a torus. Now if we include the rotation by 180 degrees
$$
r:=\begin{bmatrix}
-1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1
\end{bmatrix}
$$
Then mod out $ SE_2 $ by the group generated by $ \langle H,r,b \rangle $ we get the Klein bottle $ K $. Since $ \mathbb{Z}=\pi_1(SE_2) $ and $ \pi_0(<H,r,b>) =<r,b> \cong \{ \pm 1 \} \rtimes \mathbb{Z} $  then we must have
$$
0 \to \mathbb{Z} \to \pi(K) \to  \mathbb{Z} \rtimes \{ \pm 1 \}  \to 0
$$
So we can conclude that $ \pi_1(K) \cong \mathbb{Z} \rtimes (\mathbb{Z} \rtimes \{ \pm 1 \}) $. It turns out that this particular semidirect product is isomorphic to the simpler semidirect product $ \mathbb{Z} \rtimes \mathbb{Z} $ with presentation $ <a,b:abab^{-1}> $ . Thus $ \pi_1(K) \cong \mathbb{Z} \rtimes \mathbb{Z} $ (this fact can be verified using the Seifert-Van Kampen theorem and the fact that a Klein bottle is a connected sum of two projective planes)
As Steve D pointed out below, since the klein bottle has orientable double cover the torus then by applying LES of homotopy to the $C_2$ principal bundle we have
$$
1 \to \mathbb{Z}^2 \to \pi_1(KB) \to C_2 \to 1
$$
So the fundamental group is virtually abelian.

REPLY [1 votes]: This is an extended comment on the question - apologies for posting as answer.
Firstly I find it really interesting that you have this transitive $SE_2$ action on the Klein bottle.  Naively one might think that as the Klein bottle inherits a locally Euclidean metric as a quotient of the plane by a subgroup $G\subset E_2$ (with $G\cong \pi_1(K)$), there would be such a transitive $SE_2$ action of isometries.  However $G$ is not central in $E_2$ so the action of $SE_2$ as isometries is not well defined.  Further if we consider pairs of geodesics parallel to the sides of a fundamental rectangle, meeting orthogonally at different points:

we see that the length of the vertical geodesic is doubled when the point does not lie in the middle vertical line.
This does not prove that $SE_2$ does not act transitively isometrically on the Klein bottle - but it is very unlikely as the points in the middle (and sides) seem to be genuinely different to the rest.
On the other hand, both here and in your comment you give beautiful transitive actions of $SE_2$ on the Klein bottle - which made me wonder what quadratic structure on the tangent bundle they might preserve.
Following the construction from your comment, parametrise the Klein bottle by $$K=\{(c,\theta)| c\in [0,1], \theta\in [0,\pi]\}/\sim,$$ with $k_1\sim k_2$ precisely when they result in the same set of lines in $\mathbb{R}^2$:$$\{(x,y\}|\,\,(\cos\theta) x+(\sin\theta) y\equiv c\mod 1\}.$$
As you said, the action of $SE_2$ on these sets of lines (induced from the natural action on $\mathbb{R}^2$), gives us an action on $K$.  A bilinear form on the tangent bundle is invariant under $SE_2$ precisely when it is induced by translations, from a bilinear map at a point, invariant under the stabiliser of the point.
The stabiliser of $(0,\pi)\in K$ is precisely translations by $(0,\lambda),\lambda\in \mathbb{R}$, translations by $(n,0),\, n\in\mathbb{Z}$ and rotations by $\pi$.  This is precisely your $\langle H,r,b\rangle$, so the two constructions you gave are the same (sorry - this is probably obvious to you, but I only just realised).
The action of $(0,\lambda)$ sends $(c,\theta)\mapsto (c+\lambda \cos\theta)$, so has derivative $$\left(\begin{array}{cc}1&\lambda\\0&1\end{array}\right).$$
The forms invariant under this are precisely the ones of the form: $$\left(\begin{array}{cc}0&a\\-a&b\end{array}\right).$$
So your action is not compatible with any metric.  Locally though we can define an area form: $$\left(\begin{array}{cc}0&1\\-1&0\end{array}\right).$$
However the derivative of rotation by $\pi$ is: $$\left(\begin{array}{cc}-1&0\\0&1\end{array}\right),$$ so area gets flipped when you cross the boundary that reverses orientation (as one would expect).
The only bilinear form that is globally invariant under $SE_2$ is then (up to scalar): $$\left(\begin{array}{cc}0&0\\0&1\end{array}\right).$$
We do not need to worry about translations by $(n,0)$ as these have derivative the identity.
Apologies for rambling, but I found this action you described (two different ways) very interesting.


text:
\begin{document}

\maketitle

\begin{abstract}
We describe how cross-kernel matrices, that is, kernel matrices between the data and a custom chosen set of `feature spanning points' can be used for learning. The main potential of cross-kernels lies in the fact that (a) only one side of the matrix scales with the number of data points, and (b) cross-kernels, as opposed to the usual kernel matrices, can be used to certify for the data manifold. Our theoretical framework, which is based on a duality involving the feature space and vanishing ideals, indicates that cross-kernels have the potential to be used for any kind of kernel learning. We present a novel algorithm, Ideal PCA (IPCA), which cross-kernelizes PCA. We demonstrate on real and synthetic data that IPCA allows to (a) obtain PCA-like features faster and (b) to extract novel and empirically validated features certifying for the data manifold.
\end{abstract}

\input{ipca_1_intro.tex}

\input{ipca_2_duality.tex}

\input{ipca_3_random.tex}

\input{ipca_4_ipca.tex}

\input{ipca_5_applications.tex}

\subsubsection*{Acknowledgments}

LT is supported by the European Research Council under the European Union's Seventh Framework
Programme (FP7/2007-2013) / ERC grant agreement no 247029-SDModels.  This research was conducted
while MK and LT were guests of FK at Mathematisches Forschungsinstitut Oberwolfach, supported
by FK's Oberwolfach Leibniz Fellowship.

\subsubsection*{References}

\small{

\begingroup
\let\oldsection\section
\renewcommand{\section}[2]{}

config: arxiv


TITLE: $A \subset C$ and $B \subset D$. Prove $A \times B \subset C \times D$
QUESTION [2 upvotes]: I understand that if all elements in A are contained in C and all elements in B are contained in D, then the Cartesian Product of C and D is a set that contains among its elements all the ordered pairs that can be formed with the elements of A and B. Therefore, $A \times B \subset C \times D$. This is an intuitive conclusion based on definitions and inspection. I would like a formal proof of this. Thanks in advance.

REPLY [3 votes]: First,
$$A \subset C \Longleftrightarrow  \{x \in A \Longrightarrow x \in C\}$$
Similarly,
$$B \subset D \Longleftrightarrow  \{x \in B \Longrightarrow x \in D\}$$
We want to show that
$$A \times B \subset C \times D.$$
That is, we want to prove the implication
$$(y,z) \in A \times B \Longrightarrow (y,z) \in C \times D.$$
Suppose that
$$(y,z) \in A \times B.$$
This implies that
$$\{y \in A\} \land \{z \in B\}.$$
Consequently,
$$\{y \in C\} \land \{z \in D\}$$
is also true, since $A \subset C$ and $B \subset D$.
Finally,
$$(y, z) \in C \times D.$$
Since $y$ and $z$ were arbitrary, we have proved that
$$A \times B \subset C \times D.$$

REPLY [1 votes]: Let a ∈ A. Then a ∈ C.
Let b ∈ B. Then b ∈ D.
Let (a,b) ∈ A×B.
Since A ⊆ C and B ⊆ D, a ∈ C and b ∈ D. Thus, (a,b) ∈ C×D.


TITLE: Determine line crossing corner of cuboid and POV of a camera faced towards it, based on the angles in the photo
QUESTION [0 upvotes]: Say you were to take a picture to a corner of a room with 90 degree angled walls and ceiling.
In that picture you'd see three radial lines (the edges of the walls) starting in the same point (the corner) forming 3 angles between each other: alpha, beta, gamma (alpha + beta + gamma = 360 degrees)
That set of angles seems to uniquely identify the line (L) that crosses the corner of the ceiling and passes through the point where the picture was taken.
So assuming that:
1. the corner of the ceiling is the reference point O (Ox, Oy, Oz),
2. the reference axes (x, y, z) coincide with the edges of the walls,
3. Vx, Vy, Vz are the unit vectors and that
4. P (Px, Py, Pz) is any point in the line L
-> How to determine the equations of Px, Py and Pz based on Ox, Oy, Oz, Vx, Vy, Vz, alpha, beta and gamma only?
I suppose it is a matter of determining (Mx, My, Mz) in the equation: (Px, Py, Pz) = (Ox,Oy,Oz) + (Mx, My, Mz) * (Vx, Vy, Vz) but I've been trying to solve this problem for a long time without success. I even introduced it to a few math teachers in my university but this seems to be out of their comfort zone.
So I ask: is there anyone who can help me figure it out?

REPLY [0 votes]: This question is equivalent to camera pose estimation in computer vision. Consider the object in 3D world is known and you have a 2D projection on image. This is a 2D to 3D pose estimation problem, which can also be concluded as a Perspective n Points Problem.
Here is a link about Perspective 3 Points problem:
http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MARBLE/high/pia/solving.htm
Basically, you need at least 3 recognized corners in 2D image and their corresponding coordinates in 3D world to figure out the pose of the camera.


TITLE: lowest degree of polynomial that removes the first digit of an integer in base p
QUESTION [11 upvotes]: Let $p$ be an odd prime and $n \geq 2$.
(1) Does there exist an integer-coefficient polynomial $f$ such that $f(x) = x - (x \bmod p)$ for all $x \in \mathbb{Z}/p^n \mathbb{Z}$? The polynomial effectively removes the first base-$p$ digit of $x$. For example, if $n = 2$, then the defining property is $f(a+bp) = bp$.
(2) If so, then how can we find such a polynomial with lowest possible degree? How does this lowest degree change with $n$?
UPDATE: I am super amazed. Because the reason I asked the question is because by trial and error I have an algorithm to construct polynomials of degree $(n-1)(p-1) + 1$ that works for small $n$, but can't quite finish the proof by induction to all $n$. This has been bugging me for past few days. Seeing the answers confirm with my heuristic is just thrilling!
SECOND UPDATE: Can we generalize this to functions that removes the lower $k$-digits, i.e., $f(x) = x - (x \mod p^k)$ for all $x \in \mathbb{Z}/p^n \mathbb{Z}$?
Thank you all for your nice answers!

REPLY [9 votes]: Yes, this can be done, and the bound for the degree given by Neil Strickland (that is, $(n-1)\cdot(p-1)+1$ holds.
Let $F_A(x)$ be the formal sum in binomial coefficients
$$ F_A(x):=\sum_{j=0}^\infty (-1)^j \begin{pmatrix}A-1+j\\j\end{pmatrix}\begin{pmatrix}x\\A+j\end{pmatrix}.$$
Then $F_A(x)$ converges on every integer, and for $M\in \mathbb Z$ we have
$$
F_A(M)=\begin{cases}1 & M\geq A\\ 0 & \text{otherwise.}\end{cases}
$$
The 'otherwise' part of the claim is easy. The rest follows by noticing that $F_A(M)$ is the same as coefficient of $X^{M-A}$ found by taking the product of the Taylor series of $(1+X)^{-A}$ and the polynomial $(1+X)^M$. The result is of course $1$.
Let $$G(x):= p\cdot \sum_{j=1}^\infty F_{j\cdot p}(x)=\sum_{m=0}^\infty a(m)\begin{pmatrix}x\\m\end{pmatrix},$$ where
$$a(m):= p\sum_{k=0}^\infty (-1)^{m-kp} \begin{pmatrix}m-1\\m-kp\end{pmatrix}.$$
Then for $M$ a positive integer, we have $0\leq M-G(M)<p$ and $M-G(M)\equiv M \pmod{p}.$
We then define $\tilde G(x)$ to be the same sum, truncated at $m=(n-1)(p-1)+1.$ I claim this polynomial has $p$-integral coefficients, and satisfies the desired properties, and so reduces to a polynomial with integer coefficients satisfying the properties.
Using the identity $$(-1)^k\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}k-n-1\\k\end{pmatrix},$$ we find that $a(m)$ is the coefficient of $X^m$ in the Taylor expansion of $$ p\sum_{k=0}^\infty \left(\frac{X}{1+X}\right)^{rp}=p\frac{(1+X)^p}{(1+X)^p-X^p}.$$ The denominator on the right can be written as $1+B(X)$ where $B(X)$ is divisible by $px$ and has degree $p-1.$ From here it is not hard to see that $a(m)\equiv 0 \pmod{p^n}$ when ever $m>(n-1)(p-1)+1$. Thus, truncating the sum as described above does not change the valuer, mod $p^n$.
We now just need to show that $\tilde G$ can be expanded in a polynomial with $p$-integral coefficients. Each binomial coefficient $\begin{pmatrix}x\\m\end{pmatrix}$ introduces a denominator of $m!$, which has $p$-adic valuation bounded by $$v_p(m!)<\frac{m}{p-1}$$. But as we already saw, $v_p(a(m))>\frac{m}{p-1}$ so the coefficient of $\tilde G(x)$ are indeed $p$-integral.


text:
\section{Introduction}
Optimal transport (OT) theory~\citep{Villani-2003-Topics, Villani-2008-Optimal} has become an important source of ideas and algorithmic tools in machine learning and related fields. Examples include contributions to generative modelling~\citep{Arjovsky-2017-Wasserstein, Salimans-2018-Improving, Genevay-2017-AutoDiff, Tolstikhin-2018-Wasserstein, Genevay-2018-Sinkhorn}, domain adaptation~\citep{Courty-2017-Optimal}, clustering~\citep{Srivastava-2015-WASP, Ho-2017-Multilevel}, dictionary learning~\citep{Rolet-2016-Fast, Schmitz-2018-Wasserstein}, text mining~\citep{Lin-2019-Sparsemax}, neuroimaging~\citep{Janati-2020-Multi} and single-cell genomics~\citep{Schiebinger-2019-Optimal, Yang-2020-Predicting}. The Wasserstein geometry has also provided a simple and useful analytical tool to study latent mixture models~\citep{Ho-2016-Convergence}, reinforcement learning~\citep{Bellemare-2017-Distributional}, sampling~\citep{Cheng-2018-Underdamped, Dalalyan-2019-User, Mou-2019-High, Bernton-2018-Langevin} and stochastic optimization~\citep{Nagaraj-2019-Sgd}. For an overview of OT theory and the relevant applications, we refer to the recent survey~\citep{Peyre-2019-Computational}.

\paragraph{Curse of Dimensionality in OT.} A significant barrier to the direct application of OT in machine learning lies in some inherent statistical limitations. It is well known that the sample complexity of approximating Wasserstein distances between densities using only samples can grow exponentially in dimension~\citep{Dudley-1969-Speed, Fournier-2015-Rate, Weed-2019-Sharp, Lei-2020-Convergence}. Practitioners have long been aware of this issue of the curse of dimensionality in applications of OT, and it can be argued that most of the efficient computational schemes that are known to improve computational complexity also carry out, implicitly through their simplifications, some form of statistical regularization. There have been many attempts to mitigate this curse when using OT, whether through entropic regularization~\citep{Cuturi-2013-Sinkhorn, Cuturi-2014-Barycenter, Genevay-2019-Sample, Mena-2019-Statistical}; other regularizations~\citep{Dessein-2018-Regularized, Blondel-2018-Smooth}; quantization~\citep{Canas-2012-Learning, Forrow-2019-Statistical}; simplification of the dual problem in the case of 1-Wasserstein distance~\citep{Shirdhonkar-2008-Approximate, Arjovsky-2017-Wasserstein} or by only using second-order moments of measures to fall back on the Bures-Wasserstein distance~\citep{Bhatia-2018-Bures, Muzellec-2018-Elliptical, Chen-2018-Optimal}.

\paragraph{Subspace projections: PRW and WPP.} We focus in this paper on another important approach to regularize the Wasserstein distance: Project input measures onto lower-dimensional subspaces and compute the Wasserstein distance between these reductions, instead of the original measures. The simplest and most representative example of this approach is the sliced Wasserstein distance~\citep{Rabin-2011-Wasserstein, Bonneel-2015-Sliced, Kolouri-2019-Generalized, Nguyen-2020-Distributional}, which is defined as the average Wasserstein distance obtained between random 1D projections. In an important extension,~\citet{Paty-2019-Subspace} and~\citet{Niles-2019-Estimation} proposed very recently to look for the $k$-dimensional subspace ($k>1$) that would maximize the Wasserstein distance between two measures after projection.~\citep{Paty-2019-Subspace} called that quantity the \textit{projection robust Wasserstein} (PRW) distance, while~\citet{Niles-2019-Estimation} named it \textit{Wasserstein Projection Pursuit} (WPP). PRW/WPP are conceptually simple, easy to interpret, and do solve the curse of dimensionality in the so called spiked model as proved in~\citet[Theorem 1]{Niles-2019-Estimation} by recovering an optimal $1/\sqrt{n}$ rate. Very recently,~\citet{Lin-2020-Projection} further provided several fundamental statistical bounds for PRW as well as asymptotic guarantees for learning generative models with PRW. Despite this appeal,~\citep{Paty-2019-Subspace} quickly rule out PRW for practical applications because it is non-convex, and fall back on a convex relaxation, called the \emph{subspace robust Wasserstein} (SRW) distance, which is shown to work better empirically than the usual Wasserstein distance. Similarly,~\citet{Niles-2019-Estimation} seem to lose hope that it can be computed, by stating \textit{``it is unclear how to implement WPP efficiently,''} and after having proved positive results on sample complexity, conclude their paper on a negative note, showing hardness results which apply for WPP when the ground cost is the Euclidean metric (the 1-Wasserstein case). Our contribution in this paper is to revisit the original motivation behind WPP/PRW, but take the hard route of showing that, despite its non-convexity and lack of nonsmoothness, and even despite some hardness results proved in~\cite{Niles-2019-Estimation} in a minimax sense, the original formulation for PRW/WPP \textit{can} be efficiently computed in practice using Riemannian optimization, yielding in relevant cases better behavior than SRW. For simplicity, we refer from now on to PRW/WPP as PRW.

\paragraph{Contribution:} In this paper, we study the computation of the PRW distance between two discrete probability measures of size $n$. We show that the resulting optimization problem has a special structure, allowing it to be solved in an efficient manner using Riemannian optimization~\citep{Absil-2009-Optimization, Boumal-2019-Global, Kasai-2019-Riemannian, Chen-2020-Proximal}. Our contributions can be summarized as follows.
\begin{enumerate}
\item We propose a max-min optimization model for computing the PRW distance. The maximization and minimization are performed over the Stiefel manifold and the transportation polytope, respectively. We prove the existence of the subdifferential (Lemma~\ref{lemma:bound-subdiff}), which allows us to properly define an \emph{$\epsilon$-approximate pair of optimal subspace projection and optimal transportation plan} (Definition~\ref{def:optimal-pair}) and carry out a finite-time analysis of the algorithm.

\item We define an entropic regularized PRW distance between two finite discrete probability measures, and show that it is possible to efficiently optimize this distance over the transportation polytope using the Sinkhorn iteration. This poses the problem of performing the maximization over the Stiefel manifold, which is not solvable by existing optimal transport algorithms~\citep{Cuturi-2013-Sinkhorn, Altschuler-2017-Near, Dvurechensky-2018-Computational, Lin-2019-Efficient, Lin-2019-Acceleration, Guminov-2019-Accelerated}. To this end, we propose two new algorithms, which we refer to as \textit{Riemannian gradient ascent with Sinkhorn} (RGAS) and \textit{Riemannian adaptive gradient ascent with Sinkhorn} (RAGAS), for computing the entropic regularized PRW distance. These two algorithms are guaranteed to return an \emph{$\epsilon$-approximate pair of optimal subspace projection and optimal transportation plan} with a complexity bound of $\bigOtil(n^2d\|C\|_\infty^4\epsilon^{-4} + n^2\|C\|_\infty^8\epsilon^{-8} + n^2\|C\|_\infty^{12}\epsilon^{-12})$. To the best of our knowledge, our algorithms are the first provably efficient algorithms for the computation of the PRW distance.

\item We provide comprehensive empirical studies to evaluate our algorithms on synthetic and real datasets. Experimental results confirm our conjecture that the PRW distance performs better than its convex relaxation counterpart, the SRW distance. Moreover, we show that the RGAS and RAGAS algorithms are faster than the Frank-Wolfe algorithm while the RAGAS algorithm is more robust than the RGAS algorithm.
\end{enumerate}

\paragraph{Organization.} The remainder of the paper is organized as follows. In Section~\ref{sec:background}, we present the nonconvex max-min optimization model for computing the PRW distance and its entropic regularized version. We also briefly summarize various concepts of geometry and optimization over the Stiefel manifold. In Section~\ref{sec:algorithm}, we propose and analyze the RGAS and RAGAS algorithms for computing the entropic regularized PRW distance and prove that both algorithms achieve the finite-time guarantee under stationarity measure. In Section~\ref{sec:experiment}, we conduct extensive experiments on both synthetic and real datasets, demonstrating that the PRW distance provides a computational advantage over the SRW distance in real application problems. In the supplementary material, we provide further background materials on Riemannian optimization, experiments with the algorithms, and proofs for key results. For the sake of completeness, we derive a near-optimality condition (Definition~\ref{def:near-stationarity} and~\ref{def:near-optimal-pair}) for the max-min optimization model and propose another \emph{Riemannian SuperGradient Ascent with Network simplex iteration} (RSGAN) algorithm for computing the PRW distance without regularization and prove the finite-time convergence under the near-optimality condition.

\paragraph{Notation.} We let $[n]$ be the set $\{1, 2, \ldots, n\}$ and $\br^n_+$ be the set of all vectors in $\br^n$ with nonnegative components. $\one_n$ and $\zero_n$ are the $n$-dimensional vectors of ones and zeros. $\Delta^n = \{u \in \br^n_+: \one_n^\top u = 1\}$ is the probability simplex. For a vector $x \in \br^n$, the Euclidean norm stands for $\|x\|$ and the Dirac delta function at $x$ stands for $\delta_x(\cdot)$. The notation $\Diag(x)$ denotes an $n \times n$ diagonal matrix with $x$ as the diagonal elements. For a matrix $X \in \br^{n \times n}$, the right and left marginals are denoted $r(X) = X\one_n$ and $c(X) = X^\top\one_n$, and $\|X\|_\infty = \max_{1 \leq i, j \leq n} |X_{ij}|$ and $\|X\|_1 = \sum_{1 \leq i, j \leq n} |X_{ij}|$. The notation $\diag(X)$ stands for an $n$-dimensional vector which corresponds to the diagonal elements of $X$. If $X$ is symmetric, $\lambda_{\max}(X)$ stands for largest eigenvalue. The notation $\St(d, k) \mydefn \{X \in \br^{d \times k}: X^\top X = I_k\}$ denotes the Stiefel manifold. For $X, Y \in \br^{n \times n}$, we denote $\langle X, Y\rangle = \trac(X^\top Y)$ as the Euclidean inner product and $\|X\|_F$ as the Frobenius norm of $X$. We let $P_\SCal$ be the orthogonal projection onto a closed set $\SCal$ and $\dist(X, \SCal) = \inf_{Y \in \SCal} \|X-Y\|_F$ denotes the distance between $X$ and $\SCal$. Lastly, $a = \bigO(b(n, d, \epsilon))$ stands for the upper bound $a \leq C \cdot b(n, d, \epsilon)$ where $C>0$ is independent of $n$ and $1/\epsilon$ and $a = \bigOtil(b(n, d, \epsilon))$ indicates the same inequality where $C$ depends on the logarithmic factors of $n$, $d$ and $1/\epsilon$.


TITLE: Integral formula involving Legendre polynomial
QUESTION [1 upvotes]: I would like a proof of the following equation below, where $(P_n)$ denotes Legendre polynomials. I guess this formula to hold; I checked the first several values.
\begin{equation}
\int_{-1}^{1}\sqrt{\frac{1-x}{2}} P_n(x) \text{d}{x}=\frac{-4}{(2n-1)(2n+1)(2n+3)}.
\end{equation}
This formula is motivated by research about the random walk on the sphere.

REPLY [5 votes]: Using the relation
$$ P_n(x)=\frac{1}{2n+1}\left(P'_{n+1}(x)-P'_{n-1}(x)\right)$$
and integration by parts, we get for your integral the expression
$$ \frac{1}{2n+1}\left(-\int_{-1}^1 \frac{P_{n+1}(x)}{2\sqrt{2-2x}}dx+\int_{-1}^1 \frac{P_{n-1}(x)}{2\sqrt{2-2x}}dx\right).$$
But
$$\int_{-1}^1 \frac{P_{n}(x)}{\sqrt{2-2x}}dx=\frac{2}{2n+1},$$
which can be proven by using the well known expansion $ \frac{1}{\sqrt{1-2xt+t^2}}=\sum_{n}P_n(x)t^n$ and the orthogonality relation.

REPLY [1 votes]: Not a derivation (yet), but at least a reduction to a more familiar form:
$$\int_{-1}^{1}\sqrt{\frac{1-x}{2}} P_n(x) \text{d}{x}=4\int_0^1 z^2\,P_n(1-2z^2)\,dz$$
which is a special case, $\mu=3/2$, of a formula from Gradshteyn & Ryzhik (7.233):
$$\int_0^1 x^{2\mu-1}P_n(1-2x^2)\,dx=\frac{(-1)^n\Gamma^2(\mu)}{2\Gamma(\mu+n+1)\Gamma(\mu-n)},\;\;{\rm Re}\,\mu>0.$$


text:
\begin{document}
\maketitle

\begin{abstract}
A graph is h-perfect if its stable set polytope can be completely described by non-negativity, clique and odd-hole constraints. It is  t-perfect if it furthermore has no clique of size 4.

For every graph $G$ and every $c\in\wght{G}$, the weighted chromatic number of $(G,c)$ is the minimum cardinality of a multi-set $\mathcal{F}$ of stable sets of $G$ such that every $v\in\vts{G}$ belongs to at least $c_v$ members of $\mathcal{F}$.

We prove that every h-perfect line-graph and every t-perfect claw-free graph $G$ has the integer round-up property for the chromatic number: for every non-negative integer weight $c$ on the vertices of $G$, the weighted chromatic number of $(G,c)$ can be obtained by rounding up its fractional relaxation. In other words, the stable set polytope of $G$ has the integer decomposition property.

Another occurrence of this property was recently obtained by Eisenbrand and Niemeier for fuzzy circular interval graphs (extending previous results of Niessen, Kind and Gijswijt). These graphs form another proper subclass of claw-free graphs.

Our results imply the existence of a polynomial-time algorithm which computes the weighted chromatic number of t-perfect claw-free graphs and h-perfect line-graphs. Finally, they yield a new case of a conjecture of Goldberg and Seymour on edge-colorings.

\end{abstract}

\section{Introduction}
\input{intro}

\section{Basic definitions and properties}
\input{part1}

\section{H-perfect line-graphs}
The purpose of this section is to prove theorem \ref{thm-ben-line-irp}.
In part 3.1, we state an edge-coloring result (theorem \ref{thm-ecol-form}) and show that it easily implies theorem \ref{thm-ben-line-irp} using a result of Cao and Nemhauser (which is a direct consequence of Edmonds' description of the matching polytope).

Part 3.2 is devoted to the proof of this edge-coloring statement. It relies on an auxiliary result (lemma \ref{thm-ben-crit}) whose proof is postponed to part 3.3.

\subsection{Reduction to an edge-coloring result}
\input{linegraphs}
\subsection{Proof of lemma \ref{thm-ben-crit}}
\input{proofline}

\section{T-perfect claw-free graphs}
Our purpose is to prove theorem \ref{thm-ben-cft-irp}. The first part gives an outline of the proof and hopefully clarifies that we have to take a new approach compared to the unweighted case. The proofs of the two main lemmas are postponed to sections 4.2 and 4.3.

\subsection{How the proof works ?}
\input{clawfree}

\subsection{Proof of lemma \ref{lem-reduc}}
\input{proofclawfree}

\subsection{Proof of lemma \ref{lem-small-diamond}}
\input{proofclawfree2}

\section{Minmax formulae and algorithmic remarks}
\input{explicitform}

\input{conclusion}

\bibliographystyle{alpha}
\bibliography{idpbib}

\end{document}


text:
\begin{document}
\maketitle
\abstract{ \normalsize
Motivated by understanding the limiting case of a certain systolic inequality we study compact Riemannian manifolds having all harmonic $1$-forms of constant
length. We give complete characterizations as far as K\"ahler and hyperbolic geometries are concerned. In the second part of the paper, we give algebraic and topological obstructions to the existence
of a geometrically $2$-formal K\"ahler metric, at the level of the second cohomology group. A strong interaction with almost K\"ahler geometry is to be noted. In complex dimension $3$, we list all the possible values of the second Betti number of a geometrically $2$-formal K\"ahler metric.
\large
\tableofcontents
\section{Introduction}
Let $(M^n,g)$ be a compact oriented Riemannian manifold. We denote by $\Lambda^{p}(M), 0 \le  p \le n$ the space of smooth, real valued, $p$-forms of
$M$. The standard deRham complex
$$ \ldots \rightarrow \Lambda^{p}(M) \stackrel{d}{\rightarrow}  \Lambda^{p+1}(M) \rightarrow \ldots $$
where $d$ stands for exterior derivative is then used to introduce the deRham cohomology groups, to be denoted by $H_{DR}^{p}(M)$. The topological
information contained in these cohomology groups may be understood geometrically, using Hodge theory, by means of the isomorphisms
\begin{nr} \hfill
$ H_{DR}^{p}(M) \equiv {\cal{H}}^p(M,g), \ 0 \le p \le n. \hfill $
\end{nr}
Here the space of {\it{harmonic}} $p$-forms of $(M^n,g)$ is defined by
$$ {\cal{H}}^p(M,g)=\{ \alpha \in \Lambda^p(M) : \Delta \alpha=0 \}. $$
The Laplacian on forms is given by $\Delta=dd^{\star}+d^{\star}d$ where $d^{\star}$ is the formal adjoint of $d$ with respect to the
given metric and orientation of $M$.\par
In this paper we investigate various notions of "constancy" related to harmonic forms. The first one is introduced by the following
\begin{defi}
Let $(M^n,g)$ be compact and oriented. It is said to satisfy the hypothesis $(CL_p)$ for some $1 \le p \le n-1$ iff
every harmonic $p$-form has pointwisely constant norm.
\end{defi}
Manifolds satisfying hypothesis $(CL_1)$ appear to be naturally related to a generalized systolic inequality. More precisely,
for a compact, orientable Riemannian manifold $(N^n,g)$ with
non-vanishing first Betti number one defines the stable $1$-systole $stsys_1(g)$ in terms of the stable norm (see \cite{Ban1,Ban2} for details). Let
$sys_{n-1}(g)$ be the infimum of the $(n-1)$-volumes of all nonseparating hypersurfaces in $N$. Then
the following systolic inequality, previously established in \cite{Hebda} in the case when the first Betti
number equals $1$ holds (see \cite{Ban1}) :
\begin{nr} \hfill \label{sys}
$ stsys_1(g)\cdot sys_{n-1}(g) \le \gamma^{\prime}_{b_1(N)}\cdot vol(g).\hfill $
\end{nr}
Here $\gamma^{\prime}_{b_1(N)}$ is the Berg\'e-Martinet constant for whose definition we send again the reader to \cite{Ban2}. The important point for
us is that it was shown in \cite{Ban2} that if equality in (1.2) occurs then $(N^n,g)$ satisfies the hypothesis $(CL_1)$. Note that the converse is false, as flat tori always satisfy
$(CL_1)$ but saturate (\ref{sys}) iff they are dual-critical.\par
Riemannian manifolds $(N^n,g)$ saturating (\ref{sys}) have strong geometric properties. It was proved in \cite{Ban2}, Thm. 1.2, that in this case $(N^n,g)$ is the total space of a Riemannian submersion with minimal fibers to a flat torus, whose projection is actually the Albanese map.
Therefore, in the special case when $b_1(N)=n-1$ it follows that the fibers of the Albanese map must be totally geodesic. Using Chern-Weil theory and an argument that reproduces in part that in section 6 of \cite{Ban2}, we showed in \cite{NV} that the only possible topologies of manifolds $N^n$ which admit a metric satisfying $(CL_1)$ and have $b_1(N)=n-1$ are those of $2$-step nilmanifolds with $1$-dimensional kernel. Equivalently, the above class of manifolds is parametrized by couples
$(T, \omega)$ where $T$ is a flat $(n-1)$-torus and $\omega$ is a non zero, integral cohomology class on $T$.

\par
For a compact oriented Riemannian manifold $(M,g)$ we now set
$$ H^{\star}_{DR}(M)=\bigoplus \limits_{p \ge 0}H_{DR}^p(M) \ \mbox{and} \ {\cal{H}}^{\star}(M,g)= \bigoplus \limits_{p \ge 0} {\cal{H}}^{p}(M,g)$$
Whilst $H^{\star}(M)$ is a graded algebra, in general ${\cal{H}}^{\star}(M,g)$ is not an algebra with respect to the
wedge product operation for there is no reason the isomorphism (1.1) descends to the level of harmonic forms. Our next definition
is related to this fact.
\begin{defi}
Let $(M^n,g)$ be compact and oriented. \\
(i) The metric $g$ is $p$-formal for some $1 \le p \le n-1$ iff the product of any
harmonic $p$-forms remains harmonic. \\
(ii) The metric $g$ is formal iff the product of any two harmonic  forms remains harmonic.
\end{defi}
Following \cite{Kot} we also set
\begin{defi} Let $M^n$ be compact and oriented. $M^n$ is geometrically formal iff it admits a formal Riemannian metric.
\end{defi}
From a topological viewpoint, geometric formality implies that the rational
homotopy type of the manifold is a formal consequence of the cohomology ring \cite{Sul}. Basic examples
are compact Riemannian symmetric spaces. In fact, in the recent \cite{Kot}, it was proved that in dimension
$3$ and $4$ every geometrically formal manifold has the real cohomology algebra of a compact Riemannian symmetric
space. In higher dimensions, there are very few
general facts known about geometrically formal manifolds; for instance
formal metrics satisfy hypothesis $(CL_p)$ for all $1 \le p \le n-1$ \cite{Kot}. Note that, by contrast, the class of
(non necessarily invariant) metrics on nilmanifolds studied in \cite{NV} satisfy hypothesis $(CL_p)$ whenever $1 \le p \le n-1$ but none of the $p$-formality hypothesis.
Moreover, it is known that certain classes of homogeneous spaces fail
to be geometrically formal for cohomological reasons \cite{Kot1}. \par
In this note we place ourselves in the context of K\"ahler manifolds and we investigate geometric consequences of the constant length hypothesis
and of (geometric) formality for low degree harmonic forms. Our paper is organized as follows. In section 2 we prove the following.
\begin{teo}
Let $(M^{2n},g,J)$ be a compact K\"ahler manifold. Then every harmonic $1$-form of pointwisely constant length is parallel with respect to the Levi-Civita connection
of $g$. In particular, if $g$ satisfies the hypothesis $(CL_1)$ then $(M^{2n},g,J)$ is locally the
Riemannian (and biholomorphic) product of a compact, simply connected K\"ahler manifold and of a flat torus.
\end{teo}
Note that the result of theorem 1.1 is no longer available if instead of having a K\"ahler structure we require only the presence of an almost K\"ahler
one (see section 2 for an example). It also follows that a compact K\"ahler manifold which is locally irreducible and not flat never
saturates the systolic inequality (1.2). Moreover in section 2 we remark that the length of a harmonic $1$-form on a compact hyperbolic manifold
cannot be constant; this is actually a consequence of a result in \cite{Kim} and holds in fact for compact locally symmetric spaces of negative curvature
\cite{Wal}. We propose a different, very simple proof. \par
\par
The rest of the paper is concerned with the study of obstructions to geometric $2$-formality. Note however that
every compact K\"ahler is {\it{topologically}} formal by results in \cite{Deligne}. In section 3, we show that harmonic $2$-forms of a
$2$- formal K\"ahler manifold have a global spectral decomposition and constant eigenvalues. This is enforcing the
opinion, already presented in \cite{Kot} that geometric formality is weakening the notion of Riemannian holonomy reduction. Based upon this we are able to prove the following.
\begin{teo}
Let $(M^{2n},g,J)$ be a compact K\"ahler manifold and assume that the metric $g$ is $2$-formal. Then : \\
(i) the space ${\cal{H}}^{1,1}$ of $J$-invariant harmonic forms is spanned by almost K\"ahler forms
compatible with the metric $g$. \\
(ii) the space ${\cal{H}}^2_{-}$ of $J$-anti-invariant harmonic two-forms consists only in parallel forms.
\end{teo}
By contrast, recall that simply connected, irreducible compact Hermitian symmetric space have second Betti number
equal to $1$.
As an application of theorems 1.1 and 1.2 we show in section 4 that
geometrically formal K\"ahler manifold having a maximal Betti number are flat.
Further consequences of theorem 1.2 are investigated under various curvature
assumptions in section 4. For example, we prove that locally irreducible
$8$-dimensional hyperk\"ahler manifolds cannot be geometrically formal. In
section 5 we study the case  of geometrically formal K\"ahler
manifolds of complex dimension $3$. We are able to give the possible values of
the second Betti number in this situation together with more precisions
concerning the algebraic structure of the second cohomology group. We prove :
\begin{teo} Let $(M^6,g,J)$ be a geometrically formal K\"ahler manifold. If the metric $g$ is
locally irreducible then $b_1(M)=b_2^{-}(M)=0$. Moreover one has $b_2(M) \le 3$ and ${\cal{H}}^{1,1}$ is
spanned by mutually commuting almost K\"ahler structures.
\end{teo}
As a final remark, we mention that finding further, first order obstructions
to geometric formality in the K\"ahler case relies on understanding

the algebraic structure of the space of harmonic $p$-forms, $p\ge 3$.

\section{The length of harmonic $1$-forms}
\input{oneforms.tex}

\section{Algebraic obstructions}
\input{alg.tex}
\section{More on Hodge numbers}
\input{hodgenr.tex}

\section{$6$-dimensions}

\input{sixdim1.tex}
{\bf{Acknowledgement}} : The author wishes to thank the referee for his helpful comments.
\normalsize


TITLE: How to show venn diagram?
QUESTION [0 upvotes]: How to show the following sets by Venn diagrams?
Case 1:
$$A=\{1,2,B\},B =\{3,4\}$$
Case 2:
$$A=\{1,2,3,4\}, B=\{3,4\}$$

REPLY [1 votes]: In case 1 the universe is $A=U_1=\{1,2,B\}$ and $B$ happens to be a set $\{3,4\}$. So, the "type" (whatever it means) of $B$ is the same as that of the "type" of $1$ and $2$. This means that $B\not \subset U_1$ but $B\in U_1$
In case 2 the universe is $A=U_2=\{1,2,3,4\}$. Now, the "type" of "B" is not the same as the type of $1,2,3,4$. Now, $B \subset U_2$ but $B \not \in U_2.$
The following figure is supposed to depict these two different situations:


TITLE: Can binary ring for homology make life easier?
QUESTION [1 upvotes]: Do you know of a proof which uses homology to demonstrate a property about a topological space which is made easier (or even possible) because they work over $\mathbb{Z}/2\mathbb{Z}$ instead of $\mathbb{Z}$?
I have found that certain computer calculations on a finite set of generators and a explicit boundary function are really easy if I work just over the $\mathbb{Z}/2\mathbb{Z}$. But I am wondering if there are any proofs that become easier? Such a proof could look something like

Topological space $X$ and $Y$ are hard to distinguish using point set topology.
They have different singular homology groups, but they are impossible to calculate.
But if you use the ring $\mathbb{Z}/2\mathbb{Z}$ instead of $\mathbb{Z}$, the proof is approachable and you can distinguish the spaces.

REPLY [3 votes]: The introduction to the book linked below (it is all about mod 2 (co)homology) gives a nice example of a result that was first proved with mod 2 homology.  It provided the tools to generalize Poincaré duality to all closed manifolds, regardless of orientibility. The author also mentions that they are used to develop the theory of spin structures and in some cobordism stuff.
https://www.unige.ch/math/folks/hausmann/hausmannBook.pdf


TITLE: Prove that $\int_{0}^{a}f(x)dx \geq af(a/2)$ if $f''(x) > 0$.
QUESTION [1 upvotes]: I'm trying to solve the problem below, but I'm running into some problems. I hope you can help me.

Solution Using the Integral Mean Value Theorem, we get:
$\exists \xi \in (0,a) : \int_{0}^{a}f(x)dx=f(\xi)a$
Using the fact that the function is convex, since $f''(x) > 0$, we get the following inequality:
$f(\frac{a}{2})\leq \frac{f(a)+f(0)}{2}$
How can I continue from here? I don't really know how to get rid of the 0, as I don't know whether the function maps to every set of real numbers.
Thank you for any tips.

REPLY [3 votes]: $f''(x) > 0$ means that the function is (strictly) convex, so that its graph lies above the tangent at the point $x=a/2$:
$$
 f(x) \ge f\left( \frac a2 \right) + f'\left( \frac a2 \right)\left(x-\frac a2 \right) \, .
$$
(You can also prove this with Taylor's theorem, if needed.)
Integrating this inequality over $[0, a]$ gives the wanted result
$$
 \int_0^a f(x) \, dx \ge a f\left( \frac a2 \right)
$$
since the integral over the second term is zero.


TITLE: Degree of $K(X^{1/p}, Y^{1/p})$ over $K(X, Y)$ in characteristic $p$
QUESTION [1 upvotes]: Let $K$ be a field of characteristic $p$ and $L=K(X,Y)$ where $X$ and $Y$ are variables (i.e. $L$ is the field of fractions of the polynomial ring $K[X,Y]$.
Let $\alpha,\beta\in\overline L$ such that $\alpha^p=X$ and $\beta^p=Y$. Let's consider the extension $L(\alpha,\beta)/L$. Clearly, $L(\alpha)/L$ and $L(\beta)/L$ are extensions of degree $p$. But what about the degree of $$L(\alpha,\beta)/L\text{ ?}$$
It seems natural that $T^p-X$ is still irreducible over $L(\beta)$, because we essentially don't add anything about $X$ when we go up to $L(\beta)$.
However, I haven't found an elegant/rigorous way to show that. What I actually did some time ago was writing $T^p-X$ as the product of two polynomials in $L(\beta)$ and observing that it led to something "strange", but it was quite messy and not totally rigorous.
Is there a nice way to prove that ?

REPLY [2 votes]: $T^p - Y$ is irreducible over $L(\alpha)$ by Eisenstein's Criterion, applied to the integral domain $K(\alpha)[Y]$ and the prime ideal $(Y)$.
Now my question is how you proved that $T^p - Y$ was irreducible over $L$ in the first place.


TITLE: Binomial Distribution: $\mathsf{Binom}(5, 1/4)$
QUESTION [0 upvotes]: 25%  of the workers will get cold in a factory. What will be the probability that at least 4 workers out of 5 will get cold?
I have tried this, can you please help me out if it is wrong or it can be solved easily by any other method.
$P(\text{worker gets cold}) = 25/100 = 1/4$
and $P(\text{worker doesn't get cold}) = 75/100 = 3/4.$
"At least four" means that it can be four or it can be five.
So,
$P(X=4) = {5 \choose 4} (1/4)^4 (3/4)^1 = 0.0147.$
$P(X=5) =  {5 \choose 5} (1/4)^5 (3/4)^0 = 0.000732.$
Then $P(X=4)+P(X=5) = 0.015432.$
is this answer right?
Thanks and help is appreciated.

REPLY [0 votes]: Your original statement is confusing.  What is the total number of workers in the factory?  I believe that the larger the total number of workers is then the chances of 80% or more get cold is smaller.


text:
\section{Approximate second-order points and smoothed analysis}\label{sec:smoothanal}

We state our main results formally in this section. As announced, following~\citep{bhojanapalli2018smoothed}, we resort to smoothed analysis~\citep{SmoothedAnalysis}. To this end, we consider perturbations of the cost matrix $C$ of~\eqref{eq:eq3} by a \textit{Gaussian Wigner matrix}. Intuitively, smoothed analysis tells us how large the variance of the perturbation should be in
order to obtain a new SDP which, with high probability, is sufficiently distant from any pathological case.

We start by formally defining the notion of Gaussian Wigner matrix, following~\citep{arous2011wigner}.

\begin{definition}[Gaussian Wigner matrix]\label{def:wigner}
	The random matrix $W = W^*$ in $\Sy^{n\times n}$ is a \emph{Gaussian Wigner matrix} with variance $\sigma_W^2$ if its entries on and above the diagonal are independent, zero-mean Gaussian variables (real or complex depending on context) with variance $\sigma_W^2$.

\end{definition}

Besides Assumption~\ref{ass:smoothmanifold}, another important assumption for our results is that the search space $\mathcal{C}$~\eqref{eq:C} of~\eqref{eq:eq3} is compact. In that scenario, there exists a finite constant $R$ such that
\begin{equation}\label{boundTrace}
\forall X\in\mathcal{C}, \quad \Tr{X}\leq R.
\end{equation}
Thus, for all $Y\in\mathcal{M}$, $\norm{Y}^2 = \Tr{YY^*} \leq R$. Another consequence of compactness of $\mathcal{C}$ is that the operator $\mathcal{A}^*\circ G^{\dagger}\circ\mathcal{A}$ is uniformly bounded, that is, there exists a finite constant $K$ such that
\begin{equation}\label{boundProof}
	 \forall Y\in\mathcal{M}, \quad \norm{\mathcal{A}^*\circ G^{\dagger}\circ\mathcal{A}}_{\mathrm{op}} \leq K,
\end{equation}
where $G^\dagger$ is a continuous function of $Y$ as in Lemma~\ref{lem:orthproj}. We give explicit expressions for the constants $R$ and $K$ for the case of phase retrieval in Section~\ref{sec:appli}.

We now state the main theorem, whose proof is in Appendix~\ref{sec:proofmain}.
\begin{theorem}\label{thm:main}
Let Assumption~\ref{ass:smoothmanifold} hold for~\eqref{eq:eq3} with cost matrix $C \in \Sy^{n\times n}$ and $m$ constraints.
 Assume $\mathcal{C}$~\eqref{eq:C} is compact, and let $R$ and $K$ be as in~\eqref{boundTrace} and~\eqref{boundProof}.
 Let $W$ be a Gaussian Wigner matrix with variance $\sigma_W^2$ and let $\delta \in (0, 1)$ be any tolerance.
 Define $\kappa$ as:
 \begin{align}
 	\kappa = \kappa(R, K, C, n, \sigma_{W}) & = R K \left(\norm{C}_{\mathrm{op}}+3\sigma_{W}\sqrt{n}\right).
 	\label{eq:kappa}
 \end{align}
 There exists a universal constant $c_0$ such that, if the rank $k$ for the low-rank problem~\eqref{eq:eq4} satisfies
 \begin{align}
 	k & \geq 3\left[ \log(n) + \sqrt{\log(1/\delta)} + \sqrt{m\cdot\log\left(1+\frac{6 \kappa\sqrt{c_0n}}{\sigma_W} \right)} \right],
 	\label{eq:rankcondition}
 \end{align}
 then, with probability at least $1-\delta - e^{-\frac{n}{2}}$ on the random matrix $W$, any $(\varepsilon_g,\varepsilon_H)$-SOSP $Y\in\K^{n\times k}$ of~\eqref{eq:eq4} with perturbed cost matrix $C+W$ has bounded optimality gap:
	\begin{align}
		0 \leq  g(Y) - f^{\star} \leq ({\varepsilon_H}+\varepsilon_g^2\eta)R + {\frac{\varepsilon_{g}}{2}}  \sqrt{R},
	\end{align}
	with $g$ the cost function of~\eqref{eq:eq4}, $f^{\star}$ the optimal value of~\eqref{eq:eq3} (both perturbed), and
	\begin{align}

		\eta & = \eta(R, K, C, n, m, \sigma_W) = \frac{c_0 n K(2+KR)^2 \left(\norm{C}_{\mathrm{op}} +  3\sigma_{W}\sqrt{n})\right)}{9m \sigma_W^2\log\left(1+\frac{6 \kappa\sqrt{c_0n}}{\sigma_W} \right)}.
		\label{eq:eta}
	\end{align}
\end{theorem}

This result indicates that, as long as the rank $k$ is on the order of $\sqrt{m}$ (up to logarithmic factors), the optimality gap in the \emph{perturbed} problem is small if a sufficiently good \emph{approximate} second-order point is computed. Since~\eqref{eq:eq3} may admit a unique solution of rank as large as $\Theta(\sqrt{m})$ (see for example~\citep[Thm.~3.1(ii)]{laurent1996facial} for the Max-Cut SDP), we conclude that the scaling of $k$ with respect to $m$ in Theorem~\ref{thm:main} is essentially optimal.

There is an incentive to pick $\sigma_W$ small, since the optimality gap is phrased in terms of the perturbed problem. As expected though, taking $\sigma_W$ small comes at a price. Specifically, the required rank $k$ scales with $\sqrt{\log(1/\sigma_W)}$, so that a smaller $\sigma_W$ may require $k$ to be a larger multiple of $\sqrt{m}$. Furthermore, the optimality gap is bounded in terms of $\eta$ with a dependence in $\varepsilon_g^2 / \sigma_W^2$; this may force us to compute more accurate approximate second-order points (smaller $\varepsilon_g$) for a similar guarantee when $\sigma_W$ is smaller: see also Corollary~\ref{cor::gap} below.

As announced, the theorem rests on two arguments which we now present---a probabilistic one, and a deterministic one:
\begin{enumerate}
 \item Probabilistic argument: In the smoothed analysis framework, we show, for $k$ large enough, that $\varepsilon_g$-FOSPs of~\eqref{eq:eq4}
 have their smallest singular value near zero, with high probability upon perturbation of $C$. This implies that such points are almost column-rank deficient.
 \item Deterministic argument: If $Y$ is an $(\varepsilon_g,\varepsilon_H)$-SOSP of~\eqref{eq:eq4} and it is almost column-rank deficient,
 then the matrix $S(Y)$ defined in equation~\eqref{eq:S} is almost positive semidefinite. From there,
 we can derive a bound on the optimality gap.
\end{enumerate}
Formal statements for both follow, building on the notation in Theorem~\ref{thm:main}. Proofs are in Appendices~\ref{sec:proofeigbd} and~\ref{sec:proofalmostpsd}, with supporting lemmas in Appendix~\ref{lem:LBSV}.
\begin{lemma}\label{lem:eigbd}
Let Assumption~\ref{ass:smoothmanifold} hold for~\eqref{eq:eq3}.
Assume $\mathcal{C}$~\eqref{eq:C} is compact.

Let $W$ be a Gaussian Wigner matrix with variance $\sigma_W^2$ and let $\delta \in (0, 1)$ be any tolerance.

There exists a universal constant $c_0$ such that, if the rank $k$ for the low-rank problem~\eqref{eq:eq4} is lower bounded as in~\eqref{eq:rankcondition}, then, with probability at least $1 - \delta - e^{-\frac{n}{2}}$ on the random matrix $W$, we have
\begin{align*}
	\norm{W}_{\mathrm{op}} & \leq 3\sigma_{W}\sqrt{n},
	\label{eq:boundnormWop}
\end{align*}
and furthermore: any $\varepsilon_g$-FOSP $Y\in\K^{n\times k}$ of~\eqref{eq:eq4} with perturbed cost matrix $C+W$ satisfies
\begin{align*}
	 \sigma_k(Y)\leq \frac{\varepsilon_g}{\sigma_W}\frac{\sqrt{c_0 n}}{k},
\end{align*}
where $\sigma_k(Y)$ is the $k$th singular value of the matrix $Y$.

\end{lemma}

\begin{lemma}\label{lem:almostpsd}
Let Assumption~\ref{ass:smoothmanifold} hold for~\eqref{eq:eq3} with cost matrix $C$.
Assume $\mathcal{C}$ is compact.

Let $Y\in \K^{n\times k}$ be an $(\varepsilon_g, \varepsilon_H)$-SOSP of~\eqref{eq:eq4} (for any $k$).

 Then, the smallest eigenvalue of $S = S(Y)$~\eqref{eq:S} is bounded below as
 \begin{align*}
 	\lambda_{\min}(S) & \geq -\varepsilon_H - \zeta  \norm{C}_{\mathrm{op}} \cdot \sigma_k^2(Y),
 \end{align*}

 where $\zeta = K(2+KR)^2$ with $R, K$ as in~\eqref{boundTrace} and~\eqref{boundProof}, and $\sigma_k(Y)$ is the $k$th singular value of $Y$ (it is zero if $k > n$). This holds deterministically for any cost matrix $C$.
\end{lemma}
Combining the two above lemmas, the key step in the proof of Theorem~\ref{thm:main} is to deduce a bound on the optimality gap from a bound on the smallest eigenvalue of $S$: see Appendix~\ref{sec:proofmain}.

We have shown in Theorem~\ref{thm:main} that a perturbed version of~\eqref{eq:eq4} can be approximately solved to global optimality, with high probability on the perturbation. In the corollary below, we further bound the optimality gap at the approximate solution of the perturbed problem with respect to the original, unperturbed problem. The proof is in Appendix~\ref{sec:proofcorollary}.

\begin{corollary}\label{cor::gap}
	Assume $\mathcal{C}$ is compact and let $R$ be as defined in~\eqref{boundTrace}. Let $X \in \mathcal{C}$ be an approximate solution for~\eqref{eq:eq3} with perturbed cost matrix $C+W$, so that the optimality gap in the perturbed problem is bounded by $\varepsilon_f$. Let $f^\star$ denote the optimal value of the unperturbed problem~\eqref{eq:eq3}, with cost matrix $C$. Then, the optimality gap for $X$ with respect to the unperturbed problem is bounded as:
	\begin{align*}
		0 \leq \dotprod{C, X} - f^\star \leq \varepsilon_f + 2\|W\|_{\mathrm{op}}R.
	\end{align*}
	Under the conditions of Theorem~\ref{thm:main}, with the prescribed probability, $\varepsilon_f$ and $\|W\|_{\mathrm{op}}$ can be bounded so that for an $(\varepsilon_g, \varepsilon_H)$-SOSP $Y$ of the perturbed problem~\eqref{eq:eq4} we have:
	\begin{align*}
		0 \leq \dotprod{CY, Y} - f^\star \leq ({\varepsilon_H}+\varepsilon_g^2\eta)R + {\frac{\varepsilon_{g}}{2}}  \sqrt{R} + 6\sigma_W\sqrt{n}R,
	\end{align*}
	where $\eta$ is as defined in~\eqref{eq:eta} and $\sigma_W^2$ is the variance of the Wigner perturbation $W$.

\end{corollary}


TITLE: Why is Graphene So Strong?
QUESTION [5 upvotes]: There has been a lot of news about Graphene since its discovery in 2004. And as we are all told it is a revolutionary material which is very strong, conductive and transparent.
But what is it about the structure of Graphene which makes it so strong?

REPLY [2 votes]: Graphene's strength mainly comes from the strong covalent bonds of the carbon atoms.
Graphite is made of layers of graphene but it is weaker because the layers making up graphite are bonded to each other through London forces hence why the layers can slide past each other and the material is soft. These weak inter-layer London forces provide a weak point in graphite's structure which doesn't exist in graphene.


TITLE: Real Life Rounding Phenomena When Solving for Variables
QUESTION [1 upvotes]: I have a question that I've been thinking a long time about without being able to come up with an answer and would appreciate some help:
I am attempting to subtract two distinct fees from a total transaction, depending on transaction price.
Fee #1 = 2.9% of transaction price
Fee #2 = 10% of transaction price
Let T = transaction price.  Therefore :
Let F = Total Fees
F = T(0.029) + T(0.1)
F = T(0.129)
F / 0.129 = T
This seems to look ok, HOWEVER, in the real world, each fee is rounded to the nearest cent.  So, for Fee #1, assuming a transaction price of 10.99, the fee would be 0.31871 and thus rounded to 0.32.  This would give a slightly different result from the algebraic result, given this rounding phenomenon.
My question is, in equations such as the one in the example, is there a way to account for  discrete rounding of terms before solving for a variable?

REPLY [0 votes]: How about multiplying by a factor $c$ first, then dividing the final answer by the same factor again?
For $f_1=$ fee #1, $f_2=$ fee #2, $c = 10$.
$$F\cdot c = T(f_1 \cdot c) + T(f_2 \cdot c) = T((f_1+f_2)\cdot c)$$
$$F = \frac{T((f_1+f_2)\cdot c)}{c}$$
Of course you solve the parentheses and numerator first. You can use bigger values of $c$ if you need more accuracy. e.g. $c=100, 1000, \ldots$.


TITLE: Simplifying a binomial sum
QUESTION [2 upvotes]: I came across the following expression
$$
-1+(1+a^5)x+4a^4bx^{h+1}+6a^3b^2x^{2h+1}+4a^2b^3x^{3h+1}+ab^4x^{4h+1}=0
$$
which I would like to simplify. I though of using a sum with the binomial coefficient, maybe something like
$$
1-x=\sum_{j=0}^4\binom{4}{j}a^{5-j}b^jx^{jh+1}
$$
but I'm not sure if I can simplify it further. Any ideas?

REPLY [4 votes]: If you expand $(a+bx^h)^4$ you get
$$a^4 + 4a^3bx^h + 6 a^2b^2x^{2h} + 4ab^3x^{3h} + b^4x^{4h}.$$
So your equation is
$$-1 + x+ ax(a+bx^h)^4 = 0.$$