text:
\begin{document}
\title{Quantum monotone metrics induced from trace non-increasing maps and additive noise}
\author{
	Koichi Yamagata
	\thanks{koichi.yamagata@uec.ac.jp}\\
	{The University of Electro-Communications Department of Informatics,}\\
		{1-5-1, Chofugaoka, Chofu, Tokyo 182-8585, Japan}
}

\date{}

\maketitle

\begin{abstract}
Quantum monotone metric was introduced by Petz, and it was proved
that quantum monotone metrics on the set of quantum states with trace
one were characterized by operator monotone functions. Later, these
were extended to monotone metrics on the set of positive operators
whose traces are not always one based on completely positive, trace
preserving (CPTP) maps.
It was shown that these extended monotone metrics were characterized by operator monotone functions continuously
parameterized by traces of

positive operators,

and did not have some ideal properties
such as monotonicity and convexity with respect to
the positive operators.

In this paper, we introduce another extension of quantum monotone metrics
which have monotonicity under completely positive, trace non-increasing
(CPTNI) maps and additive noise. We prove that our extended monotone
metrics can be characterized only by static operator monotone functions
from few assumptions without assuming continuities of metrics.
We show that our monotone metrics have some natural properties such as
additivity of direct sum, convexity and monotonicity with respect
to

positive operators.

\end{abstract}

\maketitle

\if 0
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{plain}
\newtheorem{cor}[thm]{Corollary}
\fi

\if 0
\theoremstyle{defn}

\newtheorem{defn}{Definition}
\fi

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\newcommand{\argmin}{\mathop{\rm arg~min}\limits}

\global\long\def\E{\mathcal{E}}
\global\long\def\S{\mathcal{S}}
\global\long\def\R{\mathbb{R}}
\global\long\def\C{\mathbb{C}}
\global\long\def\N{\mathbb{N}}
\global\long\def\D{\mathcal{D}}
\global\long\def\M{\mathcal{M}}
\global\long\def\X{\mathcal{X}}
\global\long\def\F{\mathcal{F}}
\global\long\def\B{\mathcal{B}}
\global\long\def\T{\mathcal{T}}
\global\long\def\para{\xi}
\global\long\def\P{\mathcal{P}}
\global\long\def\Para{\Xi}
\global\long\def\H{\mathcal{H}}
\global\long\def\Tr{{\rm Tr}\,}
\global\long\def\Ch{\mathcal{C}}
\global\long\def\bR{\mathbf{R}}
\global\long\def\bL{\mathbf{L}}
\global\long\def\ket#1{\left|#1\right\rangle }
\global\long\def\bra#1{\left\langle #1\right|}
\global\long\def\braket#1#2{\left\langle #1\mid#2\right\rangle }

\if 0
\begin{quotation}
The ``lead paragraph'' is encapsulated with the \LaTeX\
\verb+quotation+ environment and is formatted as a single paragraph before the first section heading.
(The \verb+quotation+ environment reverts to its usual meaning after the first sectioning command.)
Note that numbered references are allowed in the lead paragraph.

The lead paragraph will only be found in an article being prepared for the journal \textit{Chaos}.
\end{quotation}
\fi

\section{Introduction}

In classical statistics, Cencov \cite{cencov} proved that the Fisher
information metric is the only Riemannian metric on families of probabilities
up to rescaling that has monotonicity under Markov maps. Petz extended
Cencov's theorem to families of quantum states, and it was revealed
that there is a one-to-one correspondence between quantum monotone
metrics and operator monotone functions \cite{petz}. To introduce
Petz's characterization of monotone metrics,
let us define some notations.

Let $\B(\C^{n})$ be the set of all linear operators on $\C^{n}$, and let
$\S^{++}(\C^{n})=\left\{ \rho\in\B(\C^{n})\mid\Tr\rho=1,\,\rho>0\right\} $
be the set of all strictly positive quantum states on $\C^{n}$. The
quantum analog of Markov map can be expressed as completely positive,
trace preserving map (CPTP map) $T:\B(\C^{n})\rightarrow\B(\C^{m})$,
and it can be represented by operator sum representation
\[
T(X)=\sum_{i=1}^{k}A_{i}XA_{i}^{*}
\]
with linear maps $A_{1},\dots,A_{k}$ from $\C^{n}$ to $\C^{m}$
such that
\[
\sum_{i=1}^{k}A_{i}^{*}A_{i}=I.
\]
We denote by $\Ch(\C^{n},\C^{m})$ the set of all CPTP maps from $\B(\C^{n})$
to $\B(\C^{m})$. Let $\bL_{\rho}$ and $\bR_{\rho}$ be super operators
on $\B(\C^{n})$ defined by
\begin{align*}
\bL_{\rho}(X) & =\rho X,\\
\bR_{\rho}(X) & =X\rho,
\end{align*}
with a strictly positive operator $\rho$.

Petz defined quantum monotone metric as follows.
\begin{defn}
	\label{def:petz}
	A family of functions $\{ K_{\centerdot}^{(n)}(\cdot,\cdot) \}_{n\in\N^+}$
	from $\S^{++}(\C^n) \times \B(\C^n) \times \B(\C^n)$ to $\C$
	is a family of monotone metrics, if

	 the following conditions hold:

	\begin{description}
		\item [{(a)}] For every $n\in\N^{+}$ and $\rho\in\S^{++}(\C^n)$ the map
		\[
		K^{(n)}_{\rho}: \B(\C^n)\times\B(\C^n) \to \C
		\qquad (X,Y)\mapsto K^{(n)}_{\rho}(X,Y)
		\]
		is an inner product.
		\item [{(b)}]
		For every $n,m\in\N^+$,
		$X\in\B(\C^{n})$,
		CPTP map $T\in\Ch(\C^{n},\C^{m})$,
		$\rho\in\S^{++}(\C^{n})$
		such that $T(\rho)\in\S^{++}(\C^{m})$,
		the inequality
		\[
		K^{(m)}_{T(\rho)}\left(T(X),T(X)\right)\leq K^{(n)}_{\rho}\left(X,X\right)
		\]
		holds.

		\item [{(c)}]
		For every  $n\in\N^+$ and $X\in\B(\C^{n})$,
		the map $\rho\mapsto K^{(n)}_{\rho}\left(X,X\right)$ is continuous.
	\end{description}
\end{defn}

Any monotone metric can be characterized by operator monotone functions
as follows. (See Appendix \ref{sec:ope_monotone} for a brief account of operator monotone functions.
See \cite{Bhatia} for more details.)
\begin{thm}[Petz\cite{petz}]

	$\{ K_{\centerdot}^{(n)}(\cdot,\cdot) \}_{n\in\N^+} $
	is
	a family of monotone metrics if and only if there
	exists an operator monotone function $f:(0,\infty)\rightarrow(0,\infty)$
	and a non-negative constant $c\in\R$ such that
	\begin{equation}
	K^{(n)}_{\rho}(X,Y)=\Tr X^{*}[(\bR_{\rho}f(\bL_{\rho}\bR_{\rho}^{-1}))^{-1}Y]+c(\Tr X)^{*}(\Tr Y) \label{eq:petz}
	\end{equation}
	for $n\in\N^+$, $\rho\in \S^{++}(\C^n)$, and $X,Y\in\B(\C^n)$.
\end{thm}

Note that the second term in (\ref{eq:petz}) does not appear when
$X$ and $Y$ are derivatives of parameterized density operators whose
traces are fixed to one, and $\Tr X=\Tr Y=0$.  However, if we consider
a extended parametric family containing states whose traces are not
fixed to one, the traces of derivatives are not always zero.

In a previous study, monotone metrics on the quantum state family
$\S^{++}(\C^{n})$ are extended to strictly positive operators $\B^{++}(\C^{n})$
in Ref. \cite{kumagai}.
In their study,

a family of functions
$\{ K^{(n)}_{\centerdot}(\cdot,\cdot) \}_{n\in\N^+}$
from $\B^{++}(\C^n) \times \B(\C^n) \times \B(\C^n)$ to $\C$

is a family of monotone metrics if following conditions hold:
\begin{description}
	\item [{(a)}] For every $n\in\N^{+}$ and $\rho\in\B^{++}(\C^n)$ the map
	\[
	K^{(n)}_{\rho}: \B(\C^n)\times\B(\C^n) \to \C
	\qquad (X,Y)\mapsto K^{(n)}_{\rho}(X,Y)
	\]
	is an inner product.
	\item [{(b)}]
	For every $n,m\in\N^+$,
	$X\in\B(\C^{n})$,
	CPTP map $T\in\Ch(\C^{n},\C^{m})$,
	$\rho\in\B^{++}(\C^{n})$
	such that $T(\rho)\in\B^{++}(\C^{m})$,
	the inequality
	\[
	K^{(m)}_{T(\rho)}\left(T(X),T(X)\right)\leq K^{(n)}_{\rho}\left(X,X\right)
	\]
	holds.

	\item [{(c)}]
	For every  $n\in\N^+$ and $X\in\B(\C^{n})$,
	the map $\rho\mapsto K^{(n)}_{\rho}\left(X,X\right)$ is continuous.

\end{description}
These conditions are same as Definition \ref{def:petz} except that
$\S^{++}(\C^{n})$ is replaced by $\B^{++}(\C^{n})$. They proved
that $\{ K^{(n)}_{\centerdot}(\cdot,\cdot) \}_{n\in\N^+}$ is a family of monotone metrics if and only if
there exist a continuous function $b:\R^{++}\rightarrow\R$ and a
continuous family of operator monotone functions $\{f_{t}:\R^{++}\rightarrow\R^{++}\}_{t\in\R^{++}}$
such that
\begin{equation}
K^{(n)}_{\rho}(X,Y)=\Tr X^{*}[(\bR_{\rho}f_{\Tr\rho}(\bL_{\rho}\bR_{\rho}^{-1}))^{-1}Y]+b(\Tr\rho)(\Tr X)^{*}(\Tr Y)\label{eq:kuma}
\end{equation}
with $f_{t}(1)^{-1}+t\,b(t)>0$,
for $n\in\N^+$, $\rho\in\B^{++}(\C^n)$, and $X,Y\in\B(\C^n)$.
To distinguish this metric from
ours defined later, we call it CPTP monotone metric. It can be seen
that this CPTP monotone  metric does not have some desirable properties.
For example, $K^{(n)}_{\rho}(X,X)$ is not convex with respect to $\rho$
in general. Further, it does not have the additivity with respect
to direct sum:
\[
K^{(n_1+n_2)}_{\rho_{1}\oplus\rho_{2}}
\left(X_{1}\oplus X_{2},X_{1}\oplus X_{2}\right)
=K^{(n_1)}_{\rho_{1}} \left(X_{1},X_{1}\right)
+K^{(n_2)}_{\rho_{2}} \left(X_{2},X_{2}\right).

\]
This means that the inner product structures are different between
whole and part.

In this study, we introduce another extension of quantum monotone
metrics which have monotonicity under completely positive, trace non-increasing
maps. We prove that our extended monotone metrics can be characterized
by fixed operator monotone functions from few assumptions without
assuming continuities of metrics. We show that our monotone metrics
have some natural properties such as additivity of direct sum, convexity
and monotonicity with respect to unnormalized states.

\section{Quantum monotone metrics induced from CPTNI maps and additive noise}

In quantum mechanics, a quantum operation $T$ is used to describe
transformations of quantum states, and it must satisfy $0\leq\Tr T(\rho)\leq1$
for any quantum state $\rho$ to be physical\cite{nielsen,caves}.
A quantum operations
can be expressed as a completely positive, trace non-increasing (CPTNI)
maps $T:\B(\C^{n})\rightarrow\B(\C^{m})$, and it can be represented
by operator sum representation
\[
T(X)=\sum_{i=1}^{k}A_{i}XA_{i}^{*}
\]
with linear maps $A_{1},\dots,A_{k}$ from $\C^{n}$ to $\C^{m}$
such that
\[
\sum_{i=1}^{k}A_{i}^{*}A_{i}\leq I.
\]

If there is a state $\rho$ such that $\Tr [T(\rho)] < 1$, then the quantum operation $T$

does not provide a complete description of processes that may occur in a system, and

$\Tr[T(\rho)]$ is equal to the probability

that $T$ occurs\cite{nielsen}.
In this sense, unnormalized states having traces less than one
can be interpreted  as
results of incomplete quantum operations.
We denote by $\overline{\Ch}(\C^{n},\C^{m})$ the set of all CPTNI maps
from $\B(\C^{n})$ to $\B(\C^{m})$. We denote by
$\overline{\S}^{++}(\C^{n}):=\left\{ \rho\in\B(\C^n)\mid\Tr\rho\leq1,\,\rho>0\right\} $
and $\overline{\S}(\C^{n}):=\left\{ \rho\in\B(\C^n)\mid\Tr\rho\leq1,\,\rho\geq0\right\} $
the set of all strictly and non-strictly positive operators with traces
less than one. To extend monotone metric, it is natural to consider
a condition $K_{T(\rho)}\left(T(X),T(X)\right)\leq K_{\rho}\left(X,X\right)$
for every CPTNI map $T$.

When the trace of  an unnormalized quantum state $\rho$ is less than one, $\rho+\sigma$
may also physical with $\sigma\geq0$ such that $\Tr(\rho+\sigma)\leq1$.
In this case, $\sigma$ is considered to be noise for $\rho$. Therefore
a metric on $\overline{\S}^{++}(\C^{n})$ which has monotonicity under
noise should satisfy $K_{\rho+\sigma}\left(X,X\right)\leq K_{\rho}\left(X,X\right)$.
In this inequality, $X$ does not need to be changed under this kind
of noise because the derivative of $\rho+tX+\sigma$ with respect
to $t$ is $X$. Note that this kind of noise is not necessary to
be considered when only normalized states and CPTP maps are treated
because $\rho\mapsto T(\rho)+(\Tr\rho-\Tr T(\rho))\sigma$ is a CPTP
map for $\sigma\in\S^{++}(\C^{m})$ and $T\in\overline{\Ch}(\C^{n},\C^{m})$,
in fact, it has an operator sum representation
\[
\sum_{i=1}^{k}A_{i}\rho A_{i}^{*}+\sum_{st}B_{st}\rho B_{st}^{*}
\]
where
\[
B_{st}=\sqrt{\lambda_{s}}\text{\ensuremath{\ket{e_{s}}\bra{e_{t}}}}\sqrt{I-\sum_{i=1}^{k}A_{i}^{*}A_{i}},
\]
with the spectral decomposition $\sigma=\sum_{s}\lambda_{s}\ket{e_{s}}\bra{e_{s}}$
and the operator sum representation $T(X)=\sum_{i=1}^{k}A_{i}XA_{i}^{*}$.

Based on the above considerations, we define quantum monotone metrics
which have monotonicity under CPTNI maps as follows.
\begin{defn}
\label{def:monotone_cptni}

A family of functions $\{ K_{\centerdot}^{(n)}(\cdot,\cdot) \}_{n\in\N^+}$
from $\overline{\S}^{++}(\C^n) \times \B(\C^n) \times \B(\C^n)$ to $\C$
is a family of monotone metrics, if
the following conditions hold:
\begin{description}
	\item [{(a)}] For every $n\in\N^{+}$ and $\rho\in\overline{\S}^{++}(\C^n)$ the map
	\[
	K^{(n)}_{\rho}: \B(\C^n)\times\B(\C^n) \to \C
	\qquad (X,Y)\mapsto K^{(n)}_{\rho}(X,Y)
	\]
	is an inner product.
	\item [{(b)}]
	For every $n,m\in\N^+$,  CPTNI map $T\in\overline{\Ch}(\C^{n},\C^{m})$, $X\in\B(\C^{n})$,
	$\rho\in\overline{\S}^{++}(\C^{n})$, and $\sigma\in\overline{\S}(\C^{m})$
	such that $T(\rho)+\sigma\in\overline{\S}^{++}(\C^{m})$,

	the inequality
	\begin{equation}\label{eq:cptni_mono}

	K^{(m)}_{T(\rho)+\sigma}\left(T(X),T(X)\right)\leq K^{(n)}_{\rho}\left(X,X\right)
	\end{equation}
	holds.
\end{description}
\end{defn}

We call these metrics CPTNI monotone metrics to distinguish them from
metrics based on CPTP maps (\ref{eq:kuma}). We prove the following
Theorem.
\begin{thm}
$\{ K^{(n)}_{\centerdot}(\cdot,\cdot)\}_{n\in\N^+}$ is a family of CPTNI monotone metrics

if and only if there exists an operator monotone function $f:(0,\infty)\rightarrow(0,\infty)$
such that
\begin{equation}
K^{(n)}_{\rho}(X,Y)=\Tr X^{*}[(\bR_{\rho}f(\bL_{\rho}\bR_{\rho}^{-1}))^{-1}Y]\label{eq:petz2}
\end{equation}
for $n\in\N^+$, $\rho\in\overline{\S}^{++}(\C^n)$, and $X,Y\in\B(\C^n)$.
\end{thm}

Note that the continuous condition is not necessary to characterize
CPTNI monotone metrics unlike Definition \ref{def:petz}. Further,
the second term in RHS of (\ref{eq:petz}) does not appear in this
theorem, and the operator monotone $f$ does not depend on $\Tr\rho$
unlike CPTP monotone metrics (\ref{eq:kuma}).
\begin{proof}[The proof of ``only if'' part]
The inequality \eqref{eq:cptni_mono} implies the unitary covariance
\[
K^{(n)}_{\rho}(X,X)=K^{(n)}_{U\rho U^{*}}(UXU^{*},UXU^{*})
\]
 for any unitary operator $U$ because $U$ is an invertible CPTNI map, and
 \[
 K^{(n)}_{\rho}(X,Y)=K^{(n)}_{U\rho U^{*}}(UXU^{*},UYU^{*})
 \]
 due to the polarization identity of the inner product.

So we can assume $\rho={\rm Diag}(p_{1},\dots,p_{n})$ is diagonal,
 since we can freely choose such basis for further computations which consists of the
 eigenvectors

 of $\rho$.
 We denote by $E_{ij}^{(n)}$ the matrix
unit in $\B(\C^{n})$.
We characterize all elements $K^{(n)}_{\rho}(E_{ij}^{(n)},E_{kl}^{(n)})$
of $K^{(n)}_{\rho}$ for $i,j,k,l\in\{1,\dots,n\}$ by characterizing the
following four types of elements:
\begin{description}
\item [{(i)}] $K^{(n)}_{\rho}(E_{12}^{(n)},E_{kl}^{(n)})$ ($k\not=1$)
\item [{(ii)}] $K^{(n)}_{\rho}(E_{11}^{(n)},E_{22}^{(n)})$
\item [{(iii)}] $K^{(n)}_{\rho}(E_{12}^{(n)},E_{12}^{(n)})$
\item [{(iv)}] $K^{(n)}_{\rho}(E_{11}^{(n)},E_{11}^{(n)})$
\end{description}
Other elements of $K^{(n)}_{\rho}$ can be obtained by replacing bases of
the Hilbert space $\C^{n}$.

(i) Let $U={\rm Diag(c,1,\dots,1)}\in\B(\C^{n})$ be an unitary operator
with $|c|=1$. When $k\not=1$, we have
\[
K^{(n)}_{U\rho U^{*}}(UE_{12}^{(n)}U^{*},UE_{kl}^{(n)}U^{*})=\begin{cases}
\bar{c}^{2}K^{(n)}_{\rho}(E_{12}^{(n)},E_{kl}^{(n)}) & \text{if }l=1,\\
\bar{c}K^{(n)}_{\rho}(E_{12}^{(n)},E_{kl}^{(n)}) & \text{if }l\not=1.
\end{cases}
\]
Therefore $K^{(n)}_{\rho}(E_{12}^{(n)},E_{kl}^{(n)})=0$.

(ii) Let $T\in\overline{\Ch}(\C^{n},\C^{n})$ be a CPTNI map defined
by
\[
T(E_{ij}^{(n)})=\begin{cases}
E_{11}^{(n)} & \text{if }(i,j)=(1,1),\\
0 & \text{if }(i,j)\not=(1,1),
\end{cases}
\]
and let $\sigma={\rm Diag}(0,\lambda_{2},\dots,\lambda_{n})\in\overline{\S}(\C^{n})$.
By the definition of CPTNI monotone metrics, for any $\lambda\in\R$,
\begin{align*}
K^{(n)}_{\rho}(E_{11}^{(n)}+\lambda E_{22}^{(n)},E_{11}^{(n)}+\lambda E_{22}^{(n)}) & \geq K^{(n)}_{T(\rho)+\sigma}(T(E_{11}^{(n)}+\lambda E_{22}^{(n)}),T(E_{11}^{(n)}+\lambda E_{22}^{(n)}))\\
 & =K^{(n)}_{\rho}(E^{(n)}_{11},E^{(n)}_{11}).
\end{align*}
This means $E_{11}^{(n)}$ and $E_{22}^{(n)}$ are orthogonal with
respect to the inner product $K^{(n)}_{\rho}$, that is,
\[
K^{(n)}_{\rho}(E_{11}^{(n)},E_{22}^{(n)})=0.
\]
Note that the second terms of RHSs of (\ref{eq:petz}) and (\ref{eq:kuma})
are vanished here by using CPTNI maps and additive noise.

(iii) By using a CPTNI map $T_{1}\in\overline{\Ch}(\C^{n},\C^{2})$ defined
by
\[
T_{1}(E_{ij}^{(n)})=\begin{cases}
E_{ij}^{(2)} & \text{if }i,j\leq2,\\
O & \text{otherwise},
\end{cases}
\]
we have
\[
K^{(n)}_{\rho}(E_{12}^{(n)},E_{12}^{(n)})\ge K^{(n)}_{T_{1}(\rho)}(T_{1}(E_{12}^{(n)}),T_{1}(E_{12}^{(n)}))=K^{(2)}_{{\rm {\rm Diag}}\left(p_{1},p_{2}\right)}(E_{12}^{(2)},E_{12}^{(2)}).
\]
By using a CPTNI map $T_{2}\in\overline{\Ch}(\C^{2},\C^{n})$ defined
by
\[
T_{2}(E_{ij}^{(2)})=E_{ij}^{(n)}
\]
 and $\sigma={\rm Diag}(0,0,\lambda_{3},\dots,\lambda_{n})\in\overline{\S}(\C^{n})$,
we have
\[
K^{(2)}_{{\rm {\rm Diag}}\left(p_{1},p_{2}\right)}(E_{12}^{(2)},E_{12}^{(2)})\ge K^{(2)}_{T_{2}({\rm {\rm Diag}}\left(p_{1},p_{2}\right))+\sigma}(T_{2}(E_{12}^{(2)}),T_{2}(E_{12}^{(2)}))=K^{(n)}_{\rho}(E_{12}^{(n)},E_{12}^{(n)}).
\]
Therefore
\[
K^{(n)}_{\rho}(E_{12}^{(n)},E_{12}^{(n)})=K^{(2)}_{{\rm {\rm Diag}}\left(p_{1},p_{2}\right)}(E_{12}^{(2)},E_{12}^{(2)})=:g(p_{1},p_{2})
\]
depends only on $p_{1},p_{2}$. Note that this fact is different from
CPTP monotone metrics (\ref{eq:kuma}) which depends on a trace of
$\rho$.

Let $S_{1}\in\overline{\Ch}(\C^{2},\C^{2}\otimes\C^{m})$ be a CPTNI
map defined by
\begin{equation}
S_{1}(E^{(2)})=E^{(2)}\otimes I^{(m)}/m\label{eq:S1}
\end{equation}
for any $E^{(2)}\in\B(\C^{2})$ with an identity operator $I^{(m)}\in\B(\C^{m})$,
and let $S_{2}\in\overline{\Ch}(\C^{2}\otimes\C^{m},\C^{2})$ be a CPTNI
map defined by
\begin{equation}
S_{2}(E^{(2m)})={\rm Tr}_{2}E^{(2m)}\label{eq:S2}
\end{equation}
for any $E^{(2m)}\in\B(\C^{2}\otimes\C^{m})$ where ${\rm Tr}_{2}$
is a partial trace with respect to $\C^{m}$. Because $S_{2}(S_{1}(E^{(2)}))=E^{(2)}$,
we have
\begin{align*}
g(p_{1},p_{2}) & =K^{(2)}_{{\rm {\rm Diag}}\left(p_{1},p_{2}\right)}(E_{12}^{(2)},E_{12}^{(2)})=K^{(2 m)}_{{\rm {\rm Diag}}\left(p_{1},p_{2}\right)\otimes I^{(m)}/m}(E_{12}^{(2)}\otimes I^{(m)}/m,E_{12}^{(2)}\otimes I^{(m)}/m)\\
 & =\frac{1}{m}g\left(\frac{p_{1}}{m},\frac{p_{2}}{m}\right),
\end{align*}
for any $m\in\mathbb{N}$. From this, we have, for any rational number
$q=\frac{m_{1}}{m_{2}}$ with $m_{1},m_{2}\in\N^+$ such that $0<qp_{1}+qp_{2}\leq1$,
\[
g(qp_{1},qp_{2})=g(\frac{m_{1}}{m_{2}}p_{1},\frac{m_{1}}{m_{2}}p_{2})=\frac{1}{m_{1}}g(\frac{1}{m_{2}}p_{1},\frac{1}{m_{2}}p_{2})=\frac{m_{2}}{m_{1}}g(p_{1},p_{2})=\frac{1}{q}g(p_{1},p_{2}).
\]
Because a function $q\mapsto g(qp_{1},qp_{2})$ monotonously decreases
due to the definition \ref{def:monotone_cptni}, we have
\begin{equation}
g(qp_{1},qp_{2})=\frac{1}{q}g(p_{1},p_{2})\label{eq:rational_g}
\end{equation}
 for any real number $q\in(0,\frac{1}{p_{1}+p_{2}}]$. Note that we
don't require the continuity of $K^{(n)}_{\rho}$ to obtain (\ref{eq:rational_g}).

We can define a function $f:(0,\infty)\rightarrow(0,\infty)$ such
that
\[
g(p_{1},p_{2})=\frac{1}{p_{2}f(p_{1}/p_{2})}
\]
because $p_{2}g(p_{1},p_{2})$ depends only on $p_{1}/p_{2}$ due
to (\ref{eq:rational_g}). We prove $f$ is an operator monotone function.
Let
\[
\bar{X}=\begin{pmatrix}0 & 0\\
X & 0
\end{pmatrix}\in\B(\C^{2m})
\]
and
\[
\bar{\rho}=\begin{pmatrix}\epsilon I^{(m)} & 0\\
0 & \rho
\end{pmatrix}\in\overline{\S}^{++}(\C^{2m})
\]
are an observable and an unnormalized state represented by block matrices with a
positive real number $\epsilon$. It follows that
\[
K^{(2 m)}_{\bar{\rho}}\left(\bar{X},\bar{X}\right)=\Tr X^{*}\left[\epsilon f(\frac{\rho}{\epsilon})\right]^{-1}X.
\]
Because of definition \ref{def:monotone_cptni}, $\rho\leq\rho'$
implies $f(\frac{\rho}{\epsilon})\leq f(\frac{\rho'}{\epsilon})$.
Therefore $f$ is an operator monotone function. Note that every operator
monotone function on $(0,\infty)$ is continuous and operator concave.
(See Appendix \ref{sec:ope_monotone}).

(iv) By a similar discussion as (iii), $K^{(n)}_{\rho}(E_{11}^{(n)},E_{11}^{(n)})=:g(p_{1})$
depends only on $p_{1}$. It follows that
\[
g(p_{1})=K^{(2)}_{\frac{1}{2}p_{1}I^{(2)}}(\frac{1}{2}I^{(2)},\frac{1}{2}I^{(2)})=K^{(2)}_{\frac{1}{2}p_{1}I^{(2)}}(\frac{1}{2}X,\frac{1}{2}X)=\frac{1}{p_{1}f(1)},
\]
with $X=\begin{pmatrix}0 & 1\\
1 & 0
\end{pmatrix}$, because eigenvalues of $X$ are $\pm1$.
\end{proof}
Note that the above proof derives continuity of the metric $K^{(n)}_{\rho}(X,X)$
with respect to $\rho$ from only a few assumptions. Also note that,
unlike (\ref{eq:kuma}), the variety of CPTNI monotone metrics depends
only on an operator monotone function $f$.

\begin{proof}[The proof of ``if'' part]
When $f(x)=1$, we prove a metric defined by
\begin{equation}
K^{(n)}_{\rho}(X,X)=\Tr X^{*}\left[\bR_{\rho}^{-1}X\right]=\Tr X\rho^{-1}X^{*}\label{eq:RLD}
\end{equation}
is a CPTNI monotone metric. Because
\[
\begin{pmatrix}\rho & X^{*}\\
X & X\rho^{-1}X^{*}
\end{pmatrix}\geq0,
\]
it follows
\[
\begin{pmatrix}T(\rho)+\sigma & T(X^{*})\\
T(X) & T(X\rho^{-1}X^{*})
\end{pmatrix}\geq\begin{pmatrix}T(\rho) & T(X^{*})\\
T(X) & T(X\rho^{-1}X^{*})
\end{pmatrix}\geq0
\]
for any CPTNI map $T\in\overline{\Ch}(\C^{n},\C^{m})$ and a positive operator $\sigma$. Then it
follows
\[
T(X)\left(T(\rho)+\sigma\right)^{-1}T(X^{*})\leq T(X\rho^{-1}X^{*})
\]
by considering the Schur complement of the block matrix. Because $T$
is trace non-increasing,
\begin{align*}
K^{(m)}_{T(\rho)+\sigma}(T(X),T(X)) & =\Tr T(X)\left(T(\rho)+\sigma\right)^{-1}T(X^{*})\\
 & \leq\Tr T(X\rho^{-1}X^{*})\leq\Tr X\rho^{-1}X^{*}\\
 & =K^{(n)}_{\rho}(X,X).
\end{align*}
Therefore $(K^{(n)}_{\centerdot}(\cdot,\cdot))_{n\in\N^+}$ is a family of CPTNI monotone metrics. Similarly, when
$f(x)=x$,
\begin{equation}
K^{(n)}_{\rho}(X,X)=\Tr X^{*}\left[\bL_{\rho}^{-1}X\right]=\Tr X^{*}\rho^{-1}X\label{eq:LLD}
\end{equation}
is also CPTNI operator metric.

When $f:(0,\infty)\rightarrow(0,\infty)$ is any operator monotone
function, $h(x)=\frac{x}{f(x)}$ is also operator monotone (See Appendix
\ref{sec:ope_monotone}), and $K^{(n)}_{\rho}(X,X)$ can be rewritten to
\begin{equation}
K^{(n)}_{\rho}(X,X)=\Tr X^{*}\left[(\bL_{\rho}^{-1}m_{h}\bR_{\rho}^{-1})X\right],\label{eq:ope_mean}
\end{equation}
where
\[
A\,m_{h}B=A^{1/2}\,h(A^{-1/2}BA^{-1/2})A^{1/2}
\]
is operator mean  of strictly positive operators
$A,B$ on a Hilbert space \cite{kubo_ando}. Operator mean of non-negative operators
$A$ and $B$ is $A\,m_{h}B=\lim_{\epsilon\ssearrow0}(A+\epsilon I)\,m_{h}(B+\epsilon I)$.
It is known that operator means fulfill inequalities
\[
A\,m_{h}B\leq A'\,m_{h}B'
\]
if $A\leq A'$ and $B\leq B'$, and
\[
C(A\,m_{h}B)C^{*}\leq(CAC^{*})\,m_{h}(CBC^{*})
\]
for any operator $C$. (See Appendix \ref{sec:ope_mean} for a brief
account of operator means.) By using them, we have
\begin{align*}
K^{(m)}_{T(\rho)+\sigma}(T(X),T(X)) & =\Tr T(X^{*})\left[(\bL_{T(\rho)+\sigma}^{-1}m_{h}\bR_{T(\rho)+\sigma}^{-1})T(X)\right]\\
 & =\Tr X^{*}\left[T^{*}(\bL_{T(\rho)+\sigma}^{-1}m_{h}\bR_{T(\rho)+\sigma}^{-1})T\right]X\\
 & \leq\Tr X^{*}\left[\left(T^{*}\bL_{T(\rho)+\sigma}^{-1}T\right)m_{h}\left(T^{*}\bR_{T(\rho)+\sigma}^{-1}T\right)\right]X\\
 & \leq\Tr X^{*}\left[\bL_{\rho}^{-1}m_{h}\bR_{\rho}^{-1}\right]X=K^{(n)}_{\rho}(X,X),
\end{align*}
where CPTNI monotonicity of (\ref{eq:RLD}) and (\ref{eq:LLD}) are
used in the last inequality.
This proves $(K^{(n)}_{\centerdot}(\cdot,\cdot))_{n\in\N^+}$

is a family of CPTNI monotone
metrics for any operator monotone function $f$.
\end{proof}
\begin{cor}
\label{cor:direct_sum}For any CPTNI monotone metric,
\[
K^{(n_1+n_2)}_{\rho_{1}\oplus\rho_{2}}\left(X_{1}\oplus X_{2},Y_{1}\oplus Y_{2}\right)
=K^{(n_1)}_{\rho_{1}}\left(X_{1},Y_{1}\right)+K^{(n_2)}_{\rho_{2}}\left(X_{2},Y_{2}\right)
\]
with $\rho_{i}\in\overline{\S}^{++}(\C^{n_{i}})$ and $X_{i},Y_{i},\in\B(\C^{n_{i}})$
for $i=1,2$.
\end{cor}

This is a natural property meaning that the inner product structure
of the whole and part is the same, while CPTP monotone metrics (\ref{eq:kuma})
do not have this property. The following two corollaries about monotonicity
and convexity are also natural consequences which CPTP monotone metrics
do not have.
\begin{cor}
\label{cor:convexity}For any CPTNI monotone metric,
\[
K^{(n)}_{\frac{\rho_{1}+\rho_{2}}{2}}\left(\frac{X_{1}+X_{2}}{2},\frac{X_{1}+X_{2}}{2}\right)\leq\frac{1}{2}\left\{ K^{(n)}_{\rho_{1}}\left(X_{1},X_{1}\right)+K^{(n)}_{\rho_{2}}\left(X_{2},X_{2}\right)\right\} .
\]
\end{cor}

\begin{proof}
By using the above corollary and a partial trace, for $\rho_{1},\rho_{2}\in\overline{\S}^{++}(\C^{n})$
and $X_{1},X_{2}\in\B(\C^{n})$,
\begin{align*}
\frac{1}{2}\left\{ K^{(n)}_{\rho_{1}}\left(X_{1},X_{1}\right)+K^{(n)}_{\rho_{2}}\left(X_{2},X_{2}\right)\right\}  & =K^{(n)}_{\frac{\rho_{1}}{2}}\left(\frac{X_{1}}{2},\frac{X_{1}}{2}\right)+K^{(n)}_{\frac{\rho_{2}}{2}}\left(\frac{X_{2}}{2},\frac{X_{2}}{2}\right)\\
 & =K^{(n)}_{\frac{\rho_{1}\oplus\rho_{2}}{2}}\left(\frac{X_{1}\oplus X_{2}}{2},\frac{X_{1}\oplus X_{2}}{2}\right)\\
 & \geq K^{(n)}_{\frac{\rho_{1}+\rho_{2}}{2}}\left(\frac{X_{1}+X_{2}}{2},\frac{X_{1}+X_{2}}{2}\right).
\end{align*}
\end{proof}
\begin{cor}
\label{cor:monotonicity}For any CPTNI monotone metric $K^{(n)}_{\rho}$,
a function $\rho\mapsto K^{(n)}_{\rho}(X,X)$ is monotonically decreasing
and convex with respect to $\rho\in\overline{\S}(\C^{n})$.
\end{cor}

\begin{proof}
The monotonicity is obvious from the definition of CPTNI monotone
metric. The convexity is also obvious form the above corollary.
\end{proof}
In this section, we consider CPTNI monotone metric $K^{(n)}_{\rho}$ for
physical unnormalized state $\rho$ which is restricted to $\overline{\S}^{++}(\C^{n})=\left\{ \rho\in\B(\H)\mid\Tr\rho\leq1,\,\rho>0\right\} $.
However, it is easy to generalize $\overline{\S}^{++}(\C^{n})$ to $\overline{\overline{\S}}^{++}(\C^{n}):=\left\{ \rho\in\B(\H)\mid\rho>0\right\} $.
In fact, $\overline{\S}^{++}(\C^{n})$ can be replaced by $\overline{\overline{\S}}^{++}(\C^{n})$
in this section without any restrictions.

\section{Conclusion}

In the present paper, we introduced CPTNI monotone metrics which have
monotonicity under CPTNI maps and additive noise. It is a natural
generalization of quantum monotone metrics introduced by Petz which
have monotonicity under CPTP maps. We prove the CPTNI monotone metrics
can be characterized only by operator monotone functions from few
assumptions without assuming continuities of metrics. It was shown
that CPTNI monotone metrics have some natural properties such as additivity
of direct sum (Corollary \ref{cor:direct_sum}), convexity (Corollary
\ref{cor:convexity}), monotonicity with respect to unnormalized state (Corollary
\ref{cor:monotonicity}). These properties did not appear in monotone
metrics based on CPTP maps.

\appendix

\section{Operator monotone and operator concave functions\label{sec:ope_monotone}}

A function $f:(0,\infty)\rightarrow(0,\infty)$ is said to be operator
monotone if for all positive operators $A$ and $B$, $0<A\leq B$
implies $0<f(A)\leq f(B)$.
\begin{thm}
For a function $f:(0,\infty)\rightarrow(0,\infty)$, the following
statements are equivalent:
\begin{description}
\item [{(i)}] $f$ is operator monotone.
\item [{(ii)}]
$\bar{f}(C^{*}AC)\geq C^{*}\bar{f}(A)C$ for any

positive
operator $A$, and any operator $C$ such that $\left\Vert C\right\Vert \leq1$,
where $\bar{f}:[0,\infty) \to [0,\infty)$ is a function such that $\bar{f}(x)=f(x)$ for $x>0$ and $\bar{f}(0)=\limsup_{\epsilon \searrow 0}f(\epsilon)$.
\item [{(iii)}] $f$ is operator concave, i.e., $f(pA+(1-p)B)\geq pf(A)+(1-p)f(B)$
for any strictly positive Hermitian operators $A,B$ and any real
number $0\leq p\leq1$.
\end{description}
\end{thm}

\begin{proof}
(ii)$\Rightarrow$(iii): Consider operators $X=\begin{pmatrix}A & 0\\
0 & B
\end{pmatrix}$, $U=\begin{pmatrix}\sqrt{p}I & \sqrt{1-p}I\\
\sqrt{1-p}I & -\sqrt{p}I
\end{pmatrix}$, $P=\begin{pmatrix}I & 0\\
0 & 0
\end{pmatrix}$. Because $\left\Vert UP \right\Vert \leq1$,
\[
\begin{pmatrix}\bar{f}\left(pA+(1-p)B\right) & 0\\
0 & \bar{f}(0)
\end{pmatrix}=\bar{f}(PUXUP)\geq PU\bar{f}(X)UP=\begin{pmatrix}p\bar{f}(A)+(1-p)\bar{f}(B) & 0\\
0 & 0
\end{pmatrix}.
\]

This proves $\bar{f}$ and $f$ are operator concave.

(iii)$\Rightarrow$(i): For operators $A$ and $B$ such that $0<A\leq A+B$,
\begin{align*}
f(A+B) & =f(p\frac{1}{p}A+(1-p)\frac{1}{1-p}B)\geq pf\left(\frac{1}{p}A\right)+(1-p)f\left(\frac{1}{1-p}B\right)\\
 & \geq pf\left(\frac{1}{p}A\right).
\end{align*}
Because every concave function is continuous, $\lim_{p\to1}pf\left(\frac{1}{p}A\right)=f(A)$.
This proves $f(A+B)\geq f(A)$.

(i)$\Rightarrow$(ii): Without loss of generality, we can assume $0\leq C\leq I$
because any operator $C$ such that $\left\Vert C\right\Vert \leq1$
has a singular value decomposition $C=SW$ with $0\leq S\leq I$ and
an unitary operator $W$. Let $U=\begin{pmatrix}C & D\\
D & -C
\end{pmatrix}$ be an unitary operator with $D=\sqrt{I-C^{2}}$. For any real number
$\epsilon>0$, there exists $\mu>0$ such that
\[
\begin{pmatrix}CAC+2\epsilon I & 0\\
0 & \mu I
\end{pmatrix}\ge\begin{pmatrix}CAC+\epsilon I & CAD\\
DAC & DAD+\epsilon I
\end{pmatrix}=U\begin{pmatrix}A+\epsilon I & 0\\
0 & \epsilon I
\end{pmatrix}U.
\]
Then
\begin{align*}
\begin{pmatrix}f(CAC+2\epsilon I) & 0\\
0 & f(\mu I)
\end{pmatrix} & \ge U\begin{pmatrix}f(A+\epsilon I) & 0\\
0 & f(\epsilon I)
\end{pmatrix}U\ge U\begin{pmatrix}f(A+\epsilon I) & 0\\
0 & 0
\end{pmatrix}U\\
& =\begin{pmatrix}Cf(A+\epsilon I)C & Cf(A+\epsilon I)D\\
Df(A+\epsilon I)C & Df(A+\epsilon I)D
\end{pmatrix}.
\end{align*}
Therefore
\[
f^{+}(CAC)\geq Cf^{+}(A)C,
\]
where $f^{+}(x)=\limsup_{\epsilon \searrow 0} f(x+\epsilon)$ for $x \in [0,\infty)$.
Due to the proof of  (ii)$\Rightarrow$(iii), $f^+$ is operator concave and continuous at every $x>0$.
Hence, $f^{+}(x)=f(x)$ for $x>0$.
\begin{comment}
{\color{red}
Due to this inequality, for any real numbers $x \in (0,\infty)$  and $\epsilon \in (0,x)$,
\[
f^{+}(x)\geq f(x-\epsilon/2) \geq f^{+}(x-\epsilon) = f^{+}(\frac{x-\epsilon}{x} x) \geq \frac{x-\epsilon}{x} f^{+}(x).
\]
This means $f$ is continuous because $\lim_{\epsilon \searrow 0} f(x-\epsilon/2)=f^{+}(x)$.
}
\end{comment}
\end{proof}
\begin{thm}
If a function $f:(0,\infty)\rightarrow(0,\infty)$ is operator monotone,
\[
f^{\perp}(x)=x/f(x)
\]
 and
\[
f'(x)=xf(1/x)
\]
 are also operator monotone.
\end{thm}

\begin{proof}
Let $A,B$ be positive operators such that $0<A\leq B$. Because a
operator $C=B^{-\frac{1}{2}}A^{\frac{1}{2}}$ satisfies $\left\Vert C\right\Vert \leq1$,
\[
f(A)=f(C^{*}BC)\geq C^{*}f(B)C=A^{\frac{1}{2}}B^{-\frac{1}{2}}f(B)B^{-\frac{1}{2}}A^{\frac{1}{2}}
\]
due to the above theorem. Therefore
\[
B^{\frac{1}{2}}f(B)^{-1}B^{\frac{1}{2}}\geq A^{\frac{1}{2}}f(A)^{-1}A^{\frac{1}{2}}.
\]
This proves $f^{\perp}$ is operator monotone. Further, $f'$ is also
operator monotone because $f'(x)=1/f^{\perp}(1/x)$.
\end{proof}

\section{Operator means\label{sec:ope_mean}}

Operator mean of strictly positive operators $A$ and $B$ with respect
to an operator monotone function is defined by
\[
Am_{f}B=A^{1/2}f\left(A^{-1/2}BA^{-1/2}\right)A^{1/2}.
\]
Later, this is extended to non-negative operators.
\begin{thm}
For strictly positive operators $A,B$ on a Hilbert space $\C^{n},$
$A\,m_{f}B=B\,m_{f'}A$.
\end{thm}

\begin{proof}
By using a singular value decomposition $A^{1/2}B^{-1/2}=S^{1/2}W$
with $0 < S$ and an unitary operator $W$,
\begin{align*}
Am_{f}B & =A^{1/2}f\left(A^{-1/2}BA^{-1/2}\right)A^{1/2}\\
 & =B^{1/2}W^{*}S^{1/2}f\left(S^{-1}\right)S^{1/2}WB^{1/2}\\
 & =B^{1/2}W^{*}f'(S)WB^{1/2}\\
 & =B^{1/2}f'(B^{-1/2}AB^{-1/2})B^{1/2}.
\end{align*}
\end{proof}
\begin{thm}
For strictly positive operators $A_{1},A_{2},B_{1},B_{2}$ on a Hilbert
space $\C^{n}$ such that $0<A_{1}\leq A_{2}$ and $0<B_{1}\leq B_{2}$,
\[
A_{1}m_{f}B_{1}\leq A_{2}m_{f}B_{2}.
\]
\end{thm}

\begin{proof}
Because $f$ and $f'$ are operator monotone,
\begin{align*}
A_{1}m_{f}B_{1} & =A_{1}^{1/2}f\left(A_{1}^{-1/2}B_{1}A_{1}^{-1/2}\right)A_{1}^{1/2}\\
 & \leq A_{1}^{1/2}f\left(A_{1}^{-1/2}B_{2}A_{1}^{-1/2}\right)A_{1}^{1/2}\\
 & =B_{2}^{1/2}f'\left(B_{2}^{-1/2}A_{1}B{}_{2}^{-1/2}\right)B_{2}^{1/2}\\
 & \leq B_{2}^{1/2}f'\left(B_{2}^{-1/2}A_{2}B{}_{2}^{-1/2}\right)B_{2}^{1/2}=B_{2}m_{f'}A_{2}.
\end{align*}
\end{proof}
Due to this theorem, operator mean of non-negative operators $A$
and $B$ can be defined by
\[
Am_{f}B=\lim_{\epsilon\ssearrow0}(A+\epsilon I)m_{f}(B+\epsilon I)
\]
because this monotonically decreases, as $\epsilon\ssearrow0$, and
the limit exists.
\begin{thm}
For non-negative operators $A$ and $B$ on $\C^{n}$ and a linear
map $C$ from $\C^{n}$ to $\C^{m}$,
\[
C(A\,m_{f}B)C^{*}\leq(CAC^{*})\,m_{f}(CBC^{*}).
\]
\end{thm}

\begin{proof}
When $A>0$, $B>0$, and $C$ is invertible, by using a singular value
decomposition $CA^{1/2}=WS^{1/2}$ with $S>0$ and an unitary operator
$W$,
\begin{align*}
(CAC^{*})\,m_{f}(CBC^{*}) & =(WSW^{*})\,m_{f}(CBC^{*})\\
 & =WS^{1/2}W^{*}f(WS^{-1/2}W^{*}CBC^{*}WS^{-1/2}W^{*})WS^{1/2}W^{*}\\
 & =WS^{1/2}f(S^{-1/2}W^{*}CBC^{*}WS^{-1/2})S^{1/2}W^{*}\\
 & =CA^{1/2}f(A^{-1/2}C^{-1}CBC^{*}C^{*^{-1}}A^{-1/2})A^{1/2}C^{*}\\
 & =CA^{1/2}f(A^{-1/2}BA^{-1/2})A^{1/2}C^{*}=C(A\,m_{f}B)C^{*}.
\end{align*}

When $A\geq0$, $B\geq0$, and $C$ is any linear map, $A,B,C$ can
be embedded to $\B(\C^{l})$ with $l=\max(n,m)$. Therefore we can
assume $A,B,C\in\B(\C^{l})$ without loss of generality. For any $\epsilon>0$,
by using a singular value decomposition $C=W_{C}S_{C}$ with $S_{C}\geq0$
and an unitary operator $W_{C}$,
\begin{align*}
C(A\,m_{f}B)C^{*} & =\lim_{\epsilon\ssearrow0}W_{C}\left(S_{C}+\epsilon I\right)\left((A+\epsilon I)m_{f}(B+\epsilon I)\right)\left(S_{C}+\epsilon I\right)W_{C}^{*}\\
 & =\lim_{\epsilon\ssearrow0}W_{C}\left(\left\{ \left(S_{C}+\epsilon I\right)(A+\epsilon I)\left(S_{C}+\epsilon I\right)\right\} m_{f}\left\{ \left(S_{C}+\epsilon I\right)(B+\epsilon I)\left(S_{C}+\epsilon I\right)\right\} \right)W_{C}^{*}.
\end{align*}
Here,
\begin{align*}
\left(S_{C}+\epsilon I\right)(A+\epsilon I)\left(S_{C}+\epsilon I\right) & \leq S_{C}AS_{C}+\delta_{A}(\epsilon)I
\end{align*}
with $\delta_{A}(\epsilon)=\left\Vert \left(S_{C}+\epsilon I\right)(A+\epsilon I)\left(S_{C}+\epsilon I\right)-S_{C}AS_{C}\right\Vert $.
Similarly, $\left(S_{C}+\epsilon I\right)(B+\epsilon I)\left(S_{C}+\epsilon I\right)\leq\delta_{B}(\epsilon)I$.
Let $\delta(\epsilon)=\max\{\delta_{A}(\epsilon),\delta_{B}(\epsilon)\}$.
Then
\begin{align*}
C(A\,m_{f}B)C^{*} & \leq\lim_{\epsilon\ssearrow0}W_{C}\left(\left\{ S_{C}AS_{C}+\delta(\epsilon)I\right\} m_{f}\left\{ S_{C}BS_{C}+\delta(\epsilon)I\right\} \right)W_{C}^{*}\\
 & =\lim_{\epsilon\ssearrow0}\left(\left\{ CAC^{*}+\delta(\epsilon)I\right\} m_{f}\left\{ CBC^{*}+\delta(\epsilon)I\right\} \right)=\left(CAC^{*}\right)\,m_{f}\left(CBC^{*}\right).
\end{align*}
\end{proof}


TITLE: Prooving that T(n)=2∗T(⌊n/2⌋+17)+n is O(nlg(n))
QUESTION [1 upvotes]: I want to solve this exercice : (lg(n) is the logarithm in base 2 in all the text)
"Show that the solution of $T(n) = 2*T(⌊n/2⌋+17)+n$ is $O(nlg(n))$"
I tried everything I know but nothing worked. Here is what I did. First of all, I tried the substitution classical method. So I wrote $T(n) <= 2*c*(⌊n/2⌋+17)*lg(⌊n/2⌋+17)+n$ then I wanted to show that we had $T(n) <= c*n*lg(n)$. I wrote  $T(n) <= (cn+34c)*lg(⌊n/2⌋+17)+n$ and then I am completely lost, it seems so difficult to show that this is <= to cnlg(n) I absolutely have no idea of what to do. I tried all kind of algrebic manipulation but absolutely nothing worked so I thought that maybe the method was not good and I had to switch to the others method I knew.
The second method I know is to try to add constants to your function, so I tried this $c*n*lg(n)-d$, the result was even worse, I got this :
$T(n) <= 2*(c*(⌊n/2⌋+17)*lg(⌊n/2⌋+17)-d)+n <= (c*n+34c)*lg(⌊n/2⌋+17)-2d+n$ and I am supposed to show that this is $<= c*n*lg(n)-d$ ??? It is equivalent to  $(c∗n∗lg(n)−d-((c∗n+34c)∗lg(⌊n/2⌋+17)−2d+n) >= 0)$ Honestly it is so complicated, I am just desperated, I clearly see that it is completely dumb and impossible to do it like that but I'm 100% stuck everytime and can't do a single exercise...
After this disappointment I decided to tried the third technique I knew, change of variables. So I proposed the change m = ⌊n/2⌋+17 so maybe we get rid of the ⌊n/2⌋ (honestly I just have no idea, I just try everything I know and every idea that I have, I am just completely unable to figure out what method I should use and to find a path to the solution )
I wrote $T(2*(m-17)) = 2*T(m)+(m-17)$. Let's write $S(m) = T(2*(m-17))$, we have $S(m) = 2*T(m)+(m-17)$ and then I recognized that we could maybe use the adding a constant ( second method ) technique to get rid of the 17 to the end ?
So I wrote  : $S(m) <= 2*(c*m*lg(m)-d)+(m-17) <= 2*c*m*lg(m)-2d+m-17$ As we want to prove that $S(m) <= c*m*lg(m)$ I want to try to prove : $2*c*m*lg(m)-2d+m-17 <= c*m*lg(m) ≡ c*m*lg(m)-(2*c*m*lg(m)-2d+m-17) >= 0 ≡ c*m*lg(m)-2c*m*lg(m)+2d-m+17 >= 0 ≡ c*m*lg(m)[1-2c]+2d+m-17 >= 0 $ And then I am completely blocked, it start to become so much complicated, so long and I know I am totally in the wrong direction
Can someone help me please ? I don't understand what I need to do, which method I need to choose and why all my results are always so much complicated and so clearly wrong and stupids. Please help me. Thank you by advance. Thank you a lot.
Edit : After reading again the third technique application I did, I remark a problem in my variable change, I did m = ⌊n/2⌋+17 and concluded that we had n = (m-17)*2 but this is not true if n is odd... So I think my "proof start" try was even more wrong than I thought...

REPLY [0 votes]: You have T(34) = 2T(34) + 34, therefore T(34) = -34. You can directly calculate T(k) for k = 33, 32, 31, … 3, 2, 1, 0 in that order.
Let S(n) = T(n+34), then S(n) = T (n + 34) = 2 T(n/2 + 34/2 + 17) + n + 34 = 2T(n div 2 + 34) + n+34 = 2 S(n div 2) + n + 34, and S(0) = -34. So you have
S(n) = 2 S(n div 2) + n + 34, S(0) = -34.
Calculate a few values of S(n) to see it becomes positive, then you can find and prove an upper bound for S(n), and that will give you an upper bound for T(n) for large n. Small n don’t matter since you are looking for big-O.


TITLE: $k=2^n + 1$ is prime $\rightarrow n=2^m$
QUESTION [4 upvotes]: I am struggling with this proof. I want to prove the contrapositive, $n=2^ab \rightarrow 2^n + 1$ is composite.
My professor gave me a hint,
$n=2^ab$, $b=2r+1 \ge 3$  $\rightarrow$  $2^{2^a}+1 | 2^n+1$.  I truly don't know what I am doing and need lots of explanation.

REPLY [7 votes]: Recall that if $b$ is odd, then
$$(x+1) \vert x^{b}+1$$
This can be seen immediately from the remainder theorem, since $(-1)^b + 1 = -1 + 1 = 0$. Equivalently, for odd $b$, we have
$$x^b+1 = (x+1)(1-x+x^2-x^3 \pm \cdots - x^{b-2} + x^{b-1})$$
Hence, if we write $n = 2^a \cdot b$, such that $2^a \Vert n$ i.e. $b$ is odd, we have $x^n+1 = x^{2^a \cdot b} + 1 = \left(x^{2^a}\right)^b + 1$ is divisible by $x^{2^a}+1$. Hence, for $x^n+1$ to be a prime, we need $n = 2^a$ i.e. $n$ is a power of $2$.


TITLE: Why is angular momentum conserved in this case?
QUESTION [0 upvotes]: I was doing the following problem:
A solid cube of wood of side $2a$ and mass $M$ is resting on a horizontal surface. The cube is constrained to rotate about an axis $AB$. A bullet of mass $m$ and speed $v$ is shot at the face opposite $ABCD$ at a height of $4a/3$. The bullet becomes embedded in the cube. Find the minimum value of $v$ required to tip the cube so that it falls on face $ABCD$. Assume $m \ll M$.

I wasn't sure how to do this problem, so I checked this website for hints: https://www.physicsforums.com/threads/conservation-of-angular-momentum-help-needed.53833/
Here's the method they suggested (I'm consolidating the solution into one place for simplicity):
First, we need to determine the minimum angular velocity for which the cube will fall on face $ABCD$. For that, it needs enough angular velocity to rotate an angle of 45 degrees, after which gravity will help it down. So, we get the equation (by applying Conservation of Mechanical Energy):
$$Mga\big( \sqrt{2} - 1\big) = \dfrac{1}{2}\left(\dfrac{8Ma^2}{3}\right)\omega_{\text{min}}^2$$
This implies that
$$\omega_{\text{min}} = \sqrt{\dfrac{3g\big( \sqrt{2} - 1\big)}{4a}}$$
Now, we apply Conservation of Angular Momentum to relate the minimum velocity to the minimum angular velocity:
$$mv_{\text{min}}\left(\dfrac{4a}{3}\right) = \left(\dfrac{8Ma^2}{3}\right)\omega_{\text{min}}$$
(we are justified in neglecting the MOI of the bullet because it is given that $m \ll M$.)
After rearranging, we get that $v_{\text{min}}$ is equal to
$$v_{\text{min}} = \left(\dfrac{M}{m}\right)\sqrt{3ga\big(\sqrt{2} - 1\big)}$$
This answer checks out with the one given in the back of the textbook, so I know that the answer (and therefore the method too, most likely) is correct.

What I don't get is, why is angular momentum conserved in this case? Our system is the cube + bullet, and gravity, which acts through the COM of the cube, is exerting an external torque on the system.

REPLY [1 votes]: Before the bullet hits, the torque on the block is $0$. The reaction force of the horizontal surface is uniformly spread over the bottom of the block.
As the block rotates, the reaction force shifts to the edge of the block. This creates a torque opposing that of the bullet. The assumption is that the bullet comes to rest very quickly. The change in angular momentum from the reaction force during the collision is $\Delta L_r = \tau_r \Delta t$, where $\tau_r$ is the torque from the reaction force. $\tau_r << \tau_b$, the torque from the bullet. (No wood is crushed by the horizontal surface.) So during the collision, $\Delta L_r << \Delta L_b$, and can be ignored. This allows you to calculate the initial angular momentum of the block + bullet.
After the collision, angular momentum is not conserved. The $\tau_r$ slows the block. If $v = v_{min}$, the block comes to a stop balanced on its edge.
Not that you need it, but this old answer of mine shows pictures of the reaction force and how it relates to torque.


TITLE: Finitely generated module over Noetherian ring
QUESTION [1 upvotes]: I read that these two proposition are equivalent:

$R$ is a noetherian ring;
Every submodule of a finitely generated $R-$module is finitely generated.

While I was thinking about it I made the reasoning below, that leads me to an incorrect conclusion, so I must be wrong somewhere. I hope someone can explain me, thank you in advance.
Calling $M$ the $R-$module, we have $M\simeq R/\mathfrak{i_1}\oplus \dots \oplus R/\mathfrak{i_n}$, so it's clear that if $R$ is noetherian, so is $M$; however if $R/\mathfrak{i_1}\oplus \dots \oplus R/\mathfrak{i_n}$ is noetherian for some ideals $\mathfrak{i_1},\dots , \mathfrak{i_n}$, then $R$ is not necessarily noetherian. That means that the fact that $M$ is noetherian doesn't imply that $R$ is noetherian too.
For example, I let the ring of polynomials $\Bbb R[T_1,T_2,\dots ]$ act on the group $\Bbb R^2$, with $T_im=0\; \forall i,\forall \;m\in \Bbb R^2$. I obtain a module which is isomorphic to $\Bbb R[T_1,T_2,\dots ]/(T_1,T_2,\dots)\oplus \Bbb R[T_1,T_2,\dots ]/(T_1,T_2,\dots)$, which is in fact $\Bbb R^2$. This module is noetherian since every sumbodule is a subspace of dimension $1$ but clearly $\Bbb R[T_1,T_2,\dots ]$ is not.

REPLY [0 votes]: $R$ is an $R-$ module with respect itself so if it has unity then it will be finitely generated then by hypothesis you have that each sub module of $R$ is finitely generated.
You can observe that each ideal $I$ of $R$ is an $R-$ submodule of $R$ so it will be finitely generated, then there exists a finite number of elements $a_1,\dots, a_n$ such that
$I=(a_1,\dots , a_n)$
So $R$ is a noetherian ring.
Now we suppose that $R$ is a noetherian ring. If $f_1,\dots, f_n$ are generators of $M$ then you can define
$\psi: R\times \dots \times R\to M$ such that for each $(r_1,\dots r_n)$ you have that
$\psi(r_1,\dots , r_n):=r_1 f_1+\dots +\dots r_nf_n$
The map is surjective so by first homomorphism theorem you have that
$M\cong (R\times \dots \times R)/ ker(\psi)$
It is easily prove that if $R$ is a noetherian ring then $R\times \dots \times R$ is such that each its submodule is finitely generated.
Each submodule of $(R\times \dots \times R)/ K$ is finetly generated where $K$ is submodule of $R\times \dots \times R$ so you have finished.


TITLE: Intuition behind the paradox of instantaneous heat propagation
QUESTION [16 upvotes]: On this MIT lecture, the difference between the heat equation and the wave equation includes signal travelling infinitely fast in the heat equation, while it has finite speed in the wave equation:

I guess I don't get the idea of "signal" because in the heat equation there is a partial derivative with respect to time of the function that assigns a temperature to each point in space at each time, and this partial derivative with respect to time, which is not infinite, would seem to be the speed.
So what is it exactly that travels infinitely fast. After a Google search it seems as though this is the "paradox of instantaneous heat propagation" and it gets into other equations, and even has a relativistic counterpart. In other words, I couldn't find any entry-level explanations.

REPLY [11 votes]: One option is to recognize that the heat equation (or Fourier's law of heat conduction) is an approximation of a dissipative wave phenomenon. Consider the hyperbolic heat equation
$$
\epsilon\theta_{tt}+\theta_t = \theta_{xx}
$$
where $\epsilon \geq 0$ is a small parameter. For $\epsilon=0$ we get the (parabolic) heat equation, $\theta_t = \theta_{xx}$; otherwise, for $\epsilon>0$ we get the telegraph equation, a.k.a. the damped wave equation. Note that the absolute speed of sound equals ${\epsilon}^{-1/2}$, which becomes infinite as $\epsilon\to 0$.


TITLE: How do I solve this to represent the complex number in Cartesian coordinate
QUESTION [1 upvotes]: How do I solve this to represent the complex number in Cartesian coordinate
$$z=\frac{e^{\frac{\pi}{3}i}}{e^{\frac{2}{3}\pi i}\cdot 2e^{\frac{\pi}{6}i}}$$
So I got this question as a homework and I am not able to solve it correctly. Any leads on how to solve this would help.

REPLY [1 votes]: Hint: For any $x\in\mathbb R$, you have
$$e^{ix}=\cos(x)+i\sin(x)$$
also known as Euler's formula.

So, e.g. considering $e^{\frac{\pi}{3}i}$, as $\pi/3\in\mathbb R$, we have
$$e^{\frac{\pi}{3}i}=\cos(\pi/3)+i\sin(\pi/3)=\frac{1}{2}+i\frac{\sqrt{3}}{2}$$
You can proceed to use this conversion of polar to cartesian representations to convert the other expressions. Then, you may proceed to do arithmetic on those cartesian-represented numbers as usual.


TITLE: The interior of $S^2 \setminus \{N\}$ is itself.
QUESTION [0 upvotes]: I am hoping to confirm that if the interior of $S^2 \setminus \{N\}$ is itself? This question is in order to satisfy Excision Theorem condition in the exercise $(D^2) \cap (S^2 \setminus \{N\}) = D^2 \setminus \{0\}$.

REPLY [1 votes]: $\{N\}$ is a closed set, so $S^2 \backslash \{N\}$ is open by definition...


text:
\begin{document}
\maketitle
\begin{abstract}
A two-step model for generating random polytopes is considered. For parameters $m$, $d$, and $p$, the first step is to generate a simple polytope $P$ whose facets are given by $m$ uniform random hyperplanes tangent to the unit sphere in $\R^d$, and the second step is to sample each vertex of $P$ independently with probability $p$ and let $Q$ be the convex hull of the sampled vertices. We establish results on how well $Q$ approximates the unit sphere in terms of $m$ and $p$ as well as asymptotics on the combinatorial complexity of $Q$ for certain regimes of $p$.
\end{abstract}
\section{Introduction}
A standard family of models for random polytope comes from the convex hull of points chosen randomly from the interior or the boundary of some fixed convex body $K$. There is quite extensive literature on this model from a variety of perspectives for example \cite{BMT, Borgwardt, BeneathBeyond, Raynaud, Barany89, SW2003, SW20032, BFV, GiftWrapping, ReitznerBoundary}. On the other hand there are random 0/1 polytopes studied by \cite{Ziegler2000, Kaibel2004, Furedi1986, BaranyPor2001, KKS1995}. Here we examine a model first posed by Michael Joswig that is in some sense a combination of these two perspectives.

For parameters $d, m$ positive integers, with $m$ sufficiently larger than $d$, and $p \in [0, 1]$ we will sample a random polytope $Q$ from our model $P_2(d, m, p)$ via the following series of steps.  First generate a polytope $P$ as the convex hull of $m$ random points on the boundary of the the unit sphere in $\R^d$, then take its dual $P^{\circ}$. Next generate $Q$ from $P^{\circ}$ by taking the convex hull a random collection of the vertices of $P^{\circ}$ obtained by including each vertex of $P^{\circ}$ in the collection independently with probability $p$. This is naturally a composition of two models for random polytope and it will be helpful to have notation for each one. The first model we will denote by $P_1(d, m)$ which generates a polytope via the convex hull of $m$ random points on the unit sphere in $\R^d$. The second model we will denote $\B(P, p)$ for $P$ a polytope and $p \in [0, 1]$ which will generate a random polytope via the convex hull of a binomial random sample of the vertices of $P$ including each vertex of $P$ in the sample independently with probability $p$. Thus $Q \sim P_2(d, m, p)$ is $Q \sim \B(P^{\circ}, p)$ where $P \sim P_1(d, m)$.

An important result on $P_1(d, m)$ that we make extensive use of when studying $P_2(d, m, p)$ is the following result of Buchta, M\"{u}ller, and Tichy.
\begin{theorem}[\hspace{1sp}\cite{BMT}]\label{BMTtheorem}
Fix $d \geq 2$, $f_{d - 1}(P)$ for $P \sim P_1(d, m)$ satisfies
$$\lim_{m \rightarrow \infty} \frac{\E(f_{d - 1}(P))}{m} = \frac{2}{d} \gamma_{(d - 1)^2} \gamma_{d - 1}^{-(d - 1)}$$
with $\left\{\gamma_k\right\}_{k = 0}^{\infty}$ given by the recurrence $\gamma_0 = \frac{1}{2}$ and $\gamma_{k + 1} = \frac{1}{2 \pi (k + 1) \gamma_k}$.
\end{theorem}
We denote by $F(d)$ the constant of proportionality in Theorem \ref{BMTtheorem}.  Clearly $F(2) = 1$ and $F(3) = 2$; the first few nontrivial values are
\begin{eqnarray*}
F(4) &=& \frac{24 \pi^2}{35} \approx 6.77 \\
F(5) &=& \frac{286}{9} \approx 31.78 \\
F(6) &=& \frac{1296000 \pi^4}{676039} \approx 186.74
\end{eqnarray*}
Now $F(d)$ grows very quickly, from the recurrence of Theorem \ref{BMTtheorem} one can show that it grows like $\exp(\Theta(d \log d))$, but nonetheless in fixed dimension $P \sim P_1(d, m)$ has complexity which is $O(m)$. Recall that the \emph{complexity} of a polytope is the sum of the entries of its $f$-vector. McMullen's upper bound theorem tell us that the complexity of a $d$-dimensional polytope on $n$ vertices is $O(n^{\lfloor d/2 \rfloor})$. Moreover \emph{cyclic polytopes} realize this upper bound on the complexity, see for example \cite{Ziegler1995} for more background about extremal complexity of polytopes.

The low complexity of polytopes in $P \sim P_1(d, m)$ is a motivation to study the two-step model. From a computational perspective, one has hope of being able to compute the double description of a polytope in a reasonable amount of time only if the polytope has low complexity. For $P \sim P_1(d, m)$, for example, a special case of the main result of Borgwardt in \cite{BeneathBeyond} is that for $d$ fixed computing the double description of $P \sim P_1(d, m)$ has expected algorithmic complexity of order $O(m^2)$. On the other hand, $P \sim P_1(d, m)$ will be a simplicial polytope with probability 1. By establishing low complexity results on $Q \sim P_2(d, m , p)$ we can establish classes of low complexity polytopes that are \emph{neither simple nor simplicial}. This allows for ways to generate polytopes with new combinatorial types, either theoretical though the study of $Q \sim P_2(d, m, p)$, or, when low complexity holds, explicit computation of the $f$-vector of instances of $Q \sim P_2(d, m, p)$.

A particular application for this doubly random model comes from work of Joswig, Kaluba, and Ruff \cite{JKR}. The authors of \cite{JKR} have applied random techniques for polytopes in the context of machine learning, approximating the shape of data via randomized constructions and using the resulting polytope as a classifier.  In this case it is critical to have a rich class of polytopes of low complexity. For such polytopes it is reasonable to expect that computing a double description is feasible in practice. Toward this goal they define the following.
\begin{definition}[\hspace{1sp}\cite{JKR}]
  Let $P_1,P_2,\dots$ be a family $d$-dimensional polytopes in $\R^d$ such that $\lim_{i\to\infty} f_0(P_i)=+\infty$.
  That family is \emph{slender} if there are constants, $c,c'>0$, only depending on $d$, such that $c\cdot f_0(P_i)\leq f_{d-1}(P_i) \leq c'\cdot f_0(P_i)$ for all $i$.
\end{definition}
Now $P \sim P_1(d, m)$, $m \rightarrow \infty$ form a slender family of polytopes with $c' = F(d) + \epsilon$ and $c = F(d) - \epsilon$ for any $\epsilon > 0$ and $m$ large enough. By establishing low complexity results on $P_2(d, m, p)$ one may probabilistically establish families of slender polytopes which will in general be neither simple nor simplicial.

We show here that for $p$ sufficiently close to 1, this will depend on $d$ but not on $m$, $Q \sim P_2(d, m, p)$, $m \rightarrow \infty$ form a slender family of polytopes with explicit $c$ and $c'$, thus one should expect it to be feasible to compute a double description for $Q$ in this two-step model and $p$ close to 1. We also establish results about how close $Q \sim P_2(d, m, p)$ is to the unit sphere in $\R^d$; this has direct applications to \cite{JKR} which we outline in the appendix.

\section{Results}
We are primarily interested in number of facets for $Q \sim P_2(d, m, p)$ in the situation where $d$ and $p$ are fixed and $m$ tends to infinity. The main result in this direction is the following upper bound on the expected number of facets.

\begin{theorem}\label{upperbound}
For each $d \geq 2$ there exists a constant $C_d$ so that for $p >1 -  1/(8(d - 1))$ the expected number of facets of $Q \sim P_2(m, d, p)$ is asymptotically at most
\[\left(1 + F(d)p^dq \left(1 + \frac{C_d q}{1 - 8(d - 1)q} \right) \right) m \]
where $q = 1- p$.
\end{theorem}
The restriction that $p$ be close to 1 seems to be an artifact of the proof rather than a natural phenomenon of $P_2(d, m, p)$, we include some remarks about other regimes of $p$ at the end of the article.

We also provide a general lower bound on the expected number of facets together with a concentration inequality that is useful for constructing slender families of polytopes with some control over $c$ and $c'$. The lower bound holds for all values of $p$, but in particular as $p$ approaches 1 the ratio between the upper bound in Theorem \ref{upperbound} and the lower bound approaches 1. The lower bound we show is the following
\begin{theorem}\label{lowerbound}
For $Q \sim P_2(d, m, p)$ with $d$ fixed and $p \in [0, 1]$, for any $\delta > 0$ with high probability the number of facets of $Q$ is at least
\[(1 - \delta)(p^{d } + F(d) p^d q)m \]
where $q = 1 - p$
\end{theorem}
Here and throughout we use ``with high probability" to mean that a property holds with probability converging to 1 as $m$ tends to infinity.

Lastly we consider the question of how well $Q \sim P_2(d, m, p)$ approximates the unit sphere via the Hausdorff distance. Observe that $P \sim P_1(d, m)$ is a polytope inscribed in the unit sphere and $P^{\circ}$ is circumscribed around the unit sphere. However, once we sample $Q$ as the convex hull of a sample of vertices of $P^{\circ}$, we no longer have a guarantee that $Q$ is circumscribed around the unit sphere anymore. Thus to understand how close $Q$ is to the sphere we have to establish how close the vertices of $Q$, which are outside the unit sphere, are to the sphere and how far we ``cut into" the sphere when we remove the vertices of $P^{\circ}$ that do not belong to the sampled vertices for $Q$. By considering both of these questions, we establish the following for $d$ fixed, $m$ tending to infinity, and $p$ either fixed or depending on $m$.
\begin{theorem}\label{Hausdorffdistance}
For $d \geq 2$ fixed and $pm^{1/(d - 1)}$ tending to infinity as $m$ tends to infinity, with high probability the Hausdorff distance between $Q \sim P_2(d, m, p)$ and the unit sphere is at most
\[O \left(\frac{ \log^2(pm) (\log m)^{2/(d - 1)}}{p^2m^{2/(d - 1)}} + \left(\frac{\log(pm^d)}{m} \right)^{2/(d - 1)} \right) \]
\end{theorem}
The proof of Theorem \ref{Hausdorffdistance} proceeds by showing a lower bound on the largest ball contained in $Q$ and an upper bound on the smallest ball containing $Q$. As a corollary to this method of proof we therefore also obtain upper and lower estimates on the volume of $Q \sim P_2(d, m, p)$.

\section{Complexity in the dense regime}\label{sec:complexity}
In this section we describe the expected number of facets of $P \sim P_2(d, m, p)$ when $p$ is close to 1. The upper and lower bounds on the expected number of faces will be nontrivial for $p > 1 - \delta_d$ where $\delta_d$ is a constant depending only on $d$. Moreover the expected number of faces in this regime will be bounded between $c(d, p) m$ and $C(d, p) m$ where $C(d, p)$ and $c(d, p)$ approach the same value as $p$ tends to one. However, the results do not require that $p$ tends to one with $m$ in order to be able to give useful upper and lower bounds.

The bounds that are established apply to a more general class of random polytope. In some sense the bounds more heavily depend on the second step of the two-step model than on the first. The upper bound for the dense regime follows from an general upper bound that we prove for simple polytopes $P$ in the model $\B(P, p)$ that holds provided that all subsets of $d + 2$ vertices that do not lie on a facet of $P$ do not lie in the same hyperplane. For simple polytopes, this condition is referred to a \emph{(primal) nondegeneracy} from the point of view of linear programming. Moreover, it is a reasonable assumption for us; $P \sim P_1(d, m)$ will have all of its vertices in general position with probability 1, so $P^{\circ}$ will be nondegenerate.

To study the facets of $Q \sim \B(P, p)$ for $P$ a simple polytope we observe that the set of facets naturally partition into \emph{old facets}, those facets that arise as the restriction of the binomial model to a facet of $P$, and \emph{new facets}, those facets that are not contained in any single facet of $P$. Another way to define these notions is by examining the number of vertices of $P$ ``above" a facet of $Q$. To make this precise, one may assume that $P$ contains the origin in its interior and for a facet $\sigma$ of $Q$, we let $\mathcal{C}(\sigma)$ denote the set of vertices of $P$ on or above the hyperplane defined by $\sigma$. If $Q$ still contains the origin in its interior, which holds with high probability as long as $mp$ doesn't tend to zero, then the old facets of $Q$ are all those facets $\sigma$ with $\mathcal{C}(\sigma) = \sigma$ and the rest are the new facets. A first observation toward enumerating the new facets is the following claim:

\begin{claim}\label{uniquecaps}
If $\sigma$ is a new facet of $Q \sim \B(P, p)$, then the set of vertices on or above above the hyperplane determined by $\sigma$ in $P$ induce a connected subgraph of the 1-skeleton of $P$, whose vertices we will denote by $\spcap(\sigma)$.
\end{claim}
\begin{proof}
Let $\sigma$ be a new facet of $Q \sim \B(P, p)$. At any vertex $v$ in $\spcap(\sigma)$ the value of the linear functional given by the normal vector to the hyperplane determined by $\sigma$ is nonnegative. Moreover, the simplex method starting at $v$ will find a path from $v$ to an optimal vertex $w$ with respect to this functional and in doing so the path will always stay inside $\spcap(\sigma)$.
\end{proof}

Ultimately we want to upper bound the number of new facets of $Q \sim P_2(d, m, p)$ by enumeration of choices of $\spcap(\sigma)$. By Claim \ref{uniquecaps} we see that every $\spcap(\sigma)$ is connected so it becomes important to have an enumeration formula for the number of connected subgraphs of the 1-skeleton of $P^{\circ}$ for $P \sim P_1(d, m)$. Indeed we have the following which holds for any $d$-regular graph. A result of this type also appears in a different context in \cite{NP}.
\begin{claim}\label{connectedgraphs}
If $G$ is a $d$-regular graph on $n$ vertices then for each $t \geq 2$, the number of connected induced subgraphs of $G$ on $t$ vertices is at most \[4^{t - 2} d (d - 1)^{t - 2} n\]
\end{claim}
\begin{proof}
If $G$ is $d$-regular and $v$ is a vertex of $G$, then there exists a connected induced subgraph on $t$ vertices containing $v$ if and only if there is an injective graph homomorphism from some rooted tree $T$ on $t$ vertices into $G$ mapping the root to $v$. Now if we let $\mathcal{T}(t)$ denote the number of rooted trees on $t$ vertices then the number of connected induced subgraphs of $G$ containing $v$ is at most
\[\mathcal{T}(t) d (d - 1)^{t - 2}. \]
Indeed once we have picked the tree to map, the choice for mapping the root is fixed, we have $d$ choices for the neighbor of the root and then at most $(d - 1)$ choices for each vertex after that. We only now have to bound $\mathcal{T}(t)$.

The question of the number of rooted trees has been extensively studied and $|\mathcal{T}(t)|$ is known to grow exponentially in $\mathcal{T}$; see for example \cite{Otter} who shows that for $t$ large enough there is a constant $\alpha \approx 2.95$ so that $|\mathcal{T}(t)| \approx \alpha^t$. In the interest of giving a self-contained proof here and having a bound for all $t$, we show that for $t \geq 2$, $|\mathcal{T}(t)| \leq 4^{t - 2}$.

Observe that every rooted tree of size $t$ may be encoded uniquely by a sequence of $(t - 1)$ nonnegative integers. Given a lexicographic labeling of $T \in \mathcal{T}(t)$, that is the root is labeled with 0, its $k$ neighbors are labeled $1, 2 ..., k$, then the neighbors of vertex 1 labeled consecutively starting at $k + 1$ and so on, we can encode $T$ with a $(t - 1)$-sequence of nonnegative integers $(a_1, ..., a_{t - 1})$ where $a_i$ denotes the number of children of vertex $i - 1$.  Moreover we have $1 + a_1 + \cdots + a_{t - 1} = t$ and since $t \geq 2$, $a_1 > 0$. Thus we bound the number of such sequences.

By the requirement that the sum of all the entries of our sequence is $t - 1$, we may obtain all sequences via a procedure that takes $t - 1$ vertices arranged in a line, vertical bars at the beginning and the end, and inserts $t - 2$ additional bars anywhere in between two vertices or a vertex and a bar, except that the sequence cannot begin with two consecutive vertical bars. The sequence may be read off by counting the number of points between consecutive bars. Note that some bars may have no vertices between them. The number of outcomes to such a procedure is
\[\left( \! \binom{t - 1}{t - 2} \! \right) = \binom{t - 1 + t - 2 - 1}{t - 2} < 2^{2t - 4} = 4^{t - 2},\]
where $\left( \! \displaystyle \binom{N}{r} \! \right)$ is multiset coefficient notation, the number of ways to choose a multiset of size $r$ from a set of $N$ elements.
\end{proof}
\begin{theorem}\label{upperbounddeterministic}
For each $d \geq 2$ there exists a constant $C_d$ so that if $P$ is a nondegenerate simple $d$-polytope with $m$ facets and $n$ vertices, then for $p > 1 - 1/(8(d - 1))$ the expected number of facets of $Q \sim \B(P, p)$ is at most
\[m + nqp^d \left(1 + \frac{C_d q}{1 - 8(d-1)q} \right) \]
where $q = 1 - p$.
\end{theorem}
\begin{proof}
For each $t \geq (d + 1)$, we may upper bound the expected number of new  hyperplanes $\sigma$ so that $\mathcal{C}(\sigma)$ has exactly $t$ vertices. For $t = (d + 1)$, the number of choices is simply $n$; we choose a vertex and the vertices of its link must define the new facets with that vertex above it. For $t \geq (d + 2)$ fixed, an overestimate for the number of hyperplanes is given by first counting the number of choices of $t$ vertices of the graph of $P$ so that the graph induced by those vertices is connected. Next, since the convex hull of $\mathcal{C}(\sigma)$ is a polytope on $t$ vertices with $\sigma$ as a face, from each choice of $t$ vertices inducing a connected graph we have at most $2^t$ choices for a facet $\sigma$. Once we have chosen the set of $t$ vertices and the facet, which is necessarily a simplicial facet by the nondegeneracy assumption on $P$, we have a probability of at most $q^{t - d}p^d$ that the chosen facet is a new facet of $Q$ with the remaining $t - d$ vertices above it.

By Claim \ref{connectedgraphs} we have that the expected number of new facets is at most
\begin{eqnarray*}
&& n \left( qp^d + \sum_{t = d + 2}^{\infty} 4^{t - 2} d(d - 1)^{t - 2} 2^t q^{t - d}p^d  \right) \\
 &&\leq n \left(qp^d + \frac{dp^d}{16q^d(d - 1)^2} \sum_{t = d + 2}^{\infty} \left(8(d - 1)q\right)^t \right) \\
 &&\leq n \left(qp^d + 4(8)^d(d - 1)^dq^2 dp^d \sum_{t = 0}^{\infty} \left(8(d - 1)q\right)^t \right) \\
 &&\leq n \left(qp^d + \frac{4(8)^d(d - 1)^dq^2 dp^d }{1 - 8(d - 1)q} \right) \\
\end{eqnarray*}
This gives the upper bound on the number of new facets and trivially $m$ is an upper bound on the number of old facets
\end{proof}

Now as $m \rightarrow \infty$ the number of vertices in $P \sim P_1(d, m)$ tends to $F(d)m$. Therefore we have that the expected number of facets of $Q \sim P_2(d, m, p)$ satisfies the bound in Theorem \ref{upperbound} as a corollary.

We now turn our attention to a lower bound on the expectation. We first give a general lower bound valid for all $p$, and concentration inequality on the expected number of new facets.
\begin{theorem}\label{shallowcuts}
If $P$ is a simple $d$-polytope with $m$ facets and at least $n$ vertices then for every $p \in [0, 1]$, the expected number of facets of $Q \sim \B(P, p)$ is at least
\[p^{d}m + nqp^d\]
where $q = 1 - p$. And moreover for any $\epsilon > 0$ the probability that the number of facets is at least $(1 - \epsilon)(p^{d }m + nqp^d)$ is at least
\[1 - e^{-2 (\epsilon qp^d/d)^2 n} - e^{-(m p^{d} \epsilon^2)/2}\]
\end{theorem}
\begin{proof}
Since $P$ is a simple polytope, the link of every vertex in the 1-skeleton is a collection of $d$ vertices. For a fixed vertex $v$, and $\{w_1, ..., w_d\}$ its neighbors, the facet given by the convex hull of $\{w_1, ..., w_d\}$ will be included in $Q$ if every vertex $w_1, ... , w_d$ is included in the sample and $v$ is excluded from the sample. Call such a facet a shallow cut. The expected number of shallow cuts in $Q$ is clearly at least $nqp^d$, and this is a lower bound for the number of new facets in $Q$.

For the concentration of measure statement we apply McDiarmid's inequality from \cite{McDiarmid}
\begin{theorem}[\hspace{1sp}\cite{McDiarmid}]
Let $X_1, ..., X_n$ be random $\{0, 1\}$-valued random variables. If $f$ is a real-valued function on $X_1, ..., X_n$ so that for every $i$ there exists $c_i$ so that for all $(X_1, .., X_n)$
\[|f(X_1, ..., X_i, ..., X_n) - f(X_1, ..., 1 - X_i, ..., X_n)| \leq c_i.\]
Then for every $t > 0$
\[\Pr(\E(f(X_1, ..., X_n)) - f(X_1, ..., X_n) \geq t) \leq \exp\left(-2t^2/\sum_{i = 1}^n c_i^2\right) .\]
\end{theorem}
In our case the $X_i$'s are the indicator random variables for the vertices of $P$ sampled for $Q$, and $f(X_1, ... ,X_n)$ counts the number of shallow cuts. Thus we have that for any $i$,
\[|f(X_1, ..., X_i, ... X_n)  - f(X_1, ...., 1 - X_i, ..., X_n)| \leq d\]
Indeed swapping a vertex into or out of the sample only affects the shallow cuts involving adjacent vertices. Thus for $\epsilon > 0$ fixed the probability that the number of facets is at most $(1 - \epsilon) nqp^d$ is at most the probability that the number of shallow cuts is at most $(1 - \epsilon) n q p^d$ which is bounded above by
\[\Pr(\E(f(X_1, ..., X_n)) - f(X_1, ..., X_n)  \geq \epsilon n qp^d) \]
By McDiarmid's inequality this is at most
\[\exp\left(-2 \epsilon^2 q^2 p^{2d} n / d^2\right), \]
so this is an upper bound on the probability there are fewer than $(1 - \epsilon)p^dqn$ new facets.

Next find a lower bound on the number of old facets. If $P$ is a simple polytope with $m$ facets and we sample $Q \sim \B(P, p)$, then each facet of $P$ has at least $d$ vertices and so it contributes an old facet to $Q$ with probability at least $p^{d}$. So the expected number of old facets is at least $p^{d}m$. Moreover, if we select $d$ vertices from each facet of $P$ ahead of taking the sample, then we have that the number of old facets in $Q$ stochastically dominates the binomial random variable $\Bin(m, p^{d})$, so we have that for any $\epsilon > 0$ the probability that $Q$ has fewer than $(1 - \epsilon) m p^{d}$ facets is at most
\[\exp( - (mp^{d} \epsilon^2)/2). \]
The concentration inequality on the total number of facets now follows.
\end{proof}

To prove Theorem \ref{lowerbound}, we also need a concentration inequality on the number of facets of $P \sim P_1(d, m)$. There are already concentration inequalities on $f$-vector entries for random polytopes sampled as the convex hull of points in the \emph{interior} of a fixed convex body \cite{Reitzner2005}, however the concentration inequality we prove here for points sampled from the boundary of a ball is apparently new.  Our concentration inequality is obtained via the \emph{Efron--Stein jackknife inequality} first described in \cite{EfronStein}. The Efron--Stein inequality is applied by Reitzner \cite{Reitzner2003} to study concentration of volumes for polytopes obtained by taking the convex hull of points from the interior or from the boundary of some fixed convex body $K$. In the context of random polytopes one has that if $K$ is a convex body and one builds a sequence of polytopes $K_1, K_2, ...., K_m$ where $K_1$ is a single point sampled according to some distribution $\mu$ on $K$ and $K_i$ is sampled by taking the convex hull of $K_{i  - 1}$ and a new point sampled by $\mu$, then for a functional $f$ of the random polytope process the Efron--Stein jackknife inequality is that
\[\Var f(K_m) \leq (m + 1) \E(f(K_{m+1}) - f(K_m))^2\]
Thus one can bound the variance by understanding how the polytope changes when a single point is added. A result of Reitzner that is used in \cite{Reitzner2003} to study the volume of a random polytope is well suited here to prove the concentration inequality we will need.
\begin{theorem}[Special case of Theorem 10 of \cite{Reitzner2003}]\label{ReitznerLemma}
Let $X_1, ..., X_m, X$ be points chosen uniformly on the unit sphere in $\R^d$, and let $S_m(X)$ be the random variable counting the number of facets of the convex hull of $X_1, ..., X_m$ which are no longer facets in the convex hull of $X_1, .., X_m, X$.
 Then there exists a constants $C_d$ and $c_d$ so that
\[\lim_{m \rightarrow \infty} \E(S_m(X)) = C_d.\]
and
\[\lim_{m \rightarrow \infty} \E(S_m(X)^2) = c_d \]
\end{theorem}
With the result we will prove the following about the concentration of the number of facets of $P \sim P_1(d, m)$.
\begin{theorem}\label{vertexconcentration}
For $\epsilon > 0$ fixed the probability that the number of facets $f_{d - 1}(P)$ for $P \sim P_1(d, m)$ satisfies $|f_{d - 1}(P) - F(d)m| \geq \epsilon F(d) m$ is $O \left(1/m\right)$
\end{theorem}
\begin{proof}
Consider a sequence of polytopes $K_1, ..., K_m, ...$ where $K_1$ is a single point selected uniformly at random from the unit sphere in $\R^d$ and $K_i$ is obtained as the convex hull of $K_{i - 1}$ and a new point selected uniformly at random from the unit sphere in $\R^d$. By the Efron--Stein inequality we have that
\[\Var f_{d - 1}(K_m) \leq (m + 1) \E(f_{d - 1}(K_{m+1}) - f_{d - 1}(K_m))^2.\]
Now $f_{d - 1}(K_{m + 1}) - f_{d - 1}(K_m)$ is at most $S_m(X)(d + 1)$. This can be seen because if $K_m$ is already constructed then the number of facets erased by sampling a new point is exactly $S_m(X)$ by definition, however sampling a new point will also create new facets. But the number of new facets is controlled by $S_m(X)$ as well. Every new facet will come from the cone of a face of dimension $(d - 2)$ of some facet of $S_m(X)$ and cone point given by the new vertex. As every polytope $K_1, ..., K_m, ...$ will be simplicial with probability $1$ there are at most $dS_m(X)$ new facets added. Thus
\[\E(f_{d - 1}(K_{m+1}) - f_{d - 1}(K_m))^2 \leq \E((d + 1)S_m(X))^2 \]
and this tends to $(d + 1)^2 c_d$ by Theorem \ref{ReitznerLemma}. It follows that in the limit
\[ \Var f_{d - 1}(K_m) \leq (d + 1)^2(m + 1) c_d .\]
Now as $\E(f_{d - 1}(K_m)) \rightarrow F(d) m$ we have by Chebyshev's inequality that
\[ \Pr(|f_{d - 1}(K_m) - F(d) m| \geq \epsilon F(d)m ) \leq \frac{\Var(f_{d - 1}(K_m))}{\epsilon^2 (\E(f_{d - 1}(K_m)))^2} \rightarrow  \frac{(d + 1)^2(m + 1) c_d}{\epsilon^2 F(d)^2 m^2} = O \left(\frac{1}{m}\right) \]
\end{proof}

\begin{proof}[Proof of Theorem \ref{lowerbound}]
Let $\delta > 0$ be given and suppose $P \sim P_1(d, m)$. By Theorem \ref{vertexconcentration}, the probability that $P$ has fewer than $(1 - \delta)F(d)m$ facets as $m$ tends to infinity is $O(1/m)$. If $P$ has at least $(1 - \delta)F(d)m$ facets then $P^{\circ}$ has at least $(1 - \delta)F(d)m$ vertices and $m$ facets so we are in the situation to apply Theorem \ref{shallowcuts} with $n = (1 - \delta)F(d)m$ and in this case with probability $\exp(-\Omega(m))$ $Q \sim \B(P^{\circ}, p)$ has fewer than
\[\left(p^{d} + (1 - \delta) qp^d F(d) \right)m \]
facets. So for $Q \sim P_2(d, m, p)$ the probability that $Q$ has fewer than $\left(p^{d } + (1 - \delta)qp^d F(d)\right) m$ facets is $O(1/m) + \exp(-\Omega(m)) = o(1)$.
\end{proof}

\begin{remark}
The concentration statements for the lower bounds are convenient to have for the purpose of constructing slender families of polytopes. If we take $q < 1/(8(d - 1))$, then Theorem \ref{upperbound} gives us a constant $C = C(d, p)$ with $p = 1 - q$ so that asymptotically in $m$ the expected number of facets of $Q \sim P_2(d, m, p)$ is at most $C(d, p) m$, so by Markov's inequality there is a positive probability that such a random polytope has fewer than $(1 + \delta)C(d, p)m$ facets for any fixed $\delta > 0$. On the other hand Theorem \ref{lowerbound} gives us a constant $c = c(d, p)$ \emph{and} a concentration inequality so that we can say that with high probability $Q \sim P_2(d, m, p)$ has at least $(1 - \delta)c(d, p)m$. The number of vertices of $Q \sim P_2(d, m, p)$ is concentrated around $p F(d) m$ by Theorem \ref{vertexconcentration} and so for $\delta > 0$, one may use $P_2(d, m, p)$ with $m$ starting large enough and tending to infinity to probabilistically establish a slender family of polytopes $Q_1, Q_2, ...$ so that $f_0(Q_i) \rightarrow \infty$ and for all $i$,
\[\frac{(1- \delta) c(d, p)}{F(d)} f_0(Q_i) \leq f_{d - 1}(Q_i) \leq \frac{(1 + \delta) C(d, p)}{F(d)} f_0(Q_i).\]

\end{remark}

\section{Approximation of the sphere}

Here we estimate the Hausdorff distance between $Q \sim P_2(d, m, p)$ and the unit sphere. We will bound the Hausdorff distance to the unit sphere $S^{d - 1}$ by showing that the boundary of $Q$ lives outside a sphere centered at the origin of radius $1 - \epsilon$ and inside a sphere centered at the origin of radius $1 + \epsilon$, where we will have $\epsilon$ depend on $m$ and $p$ and keep the assumption that $d$ is fixed. For $P \sim P_1(d, m)$ it is known that the Hausdorff distance from $P$ to $S^{d - 1}$ is $\Theta\left(\left(\frac{\log m}{m} \right)^{2/(d - 1)}\right)$ by a result of \cite{Barany89}. The first step toward bounding the Hausdorff distance for $Q$ is to bound how far away the vertices of $Q$ are from the origin.
\begin{lemma}\label{HausdorffOutside}
For $1 > \epsilon > 0$ and $Q \sim P_2(d, m, p)$ with probability at least
\[1 - p\binom{m}{d} \left(1 - \frac{\sqrt{2 \epsilon}^{d - 1}v_{d - 1}}{dv_d} \right)^{m - d}\]
 every vertex of $Q$ is at distance at most $(1 + \epsilon)$ from the origin where $v_k$ denotes the Lebesgue measure of the unit ball in $\R^k$.
\end{lemma}
\begin{proof}
Let $P \sim P_1(d, m)$ and $Q \sim \B(P^{\circ}, p)$. Let $X_Q$ be the random variable counting the number of vertices of $Q$ at distance at least $(1 + \epsilon)$ from the origin. Since the sample of vertices of $P^{\circ}$ selected to define $Q$ are chosen uniformly and independently of the distance of those points from the origin, $\E(X_Q) = p\E(X_{P^{\circ}})$ where $X_{P^{\circ}}$ is the number of vertices of $P^{\circ}$ at distance at least $1 + \epsilon$ from the origin. Each vertex of $P^{\circ}$ at distance at least $(1 + \epsilon)$ from the origin is dual to a hyperplane of $P$ at distance at most $\frac{1}{1 + \epsilon}$ from the origin which induces a facet. The hyperplane defining such a facet therefore cuts off a cap of height at least $1 - \frac{1}{1 + \epsilon} = \frac{\epsilon}{1 + \epsilon}$. Moreover this cap can contain no vertices of $P$.

The probability a uniform random point of the unit sphere in $\R^d$ lives on some fixed cap of height $h$, with $h < 1$, is at least
\[\frac{\sqrt{2h}^{d - 1} v_{d - 1}}{dv_d}\]
Thus the expected number of facets of $P$ whose defining hyperplane is at distance at most $\frac{1}{1 + \epsilon}$ from the origin is by linearity of expectation at most
\[\binom{m}{d} \left(1 - \frac{\sqrt{2 \epsilon}^{d - 1}v_{d - 1}}{dv_d} \right)^{m - d}.\]
And from this estimate and Markov's inequality the bound on the probability follows.
\end{proof}
The second piece of the argument is to establish how close to the origin the facets of $Q$ may be. The argument for this part proceeds in essentially two steps, the first is to show that $P^{\circ}$ for $P \sim P_1(d, m)$ has that all its facets have metric diameter $O((\log m/m)^{1/(d - 1)})$. Then we show that for $P^{\circ}$ on $n$ vertices and $Q \sim \B(P^{\circ}, p)$ every new facet has $O(\log m)$ vertices of $P^{\circ}$ above it. Now the distance from any point of the unit sphere above a hyperplane determining a new facet must be at most the length of the longest path from a point of $P^{\circ}$ above the hyperplane to a vertex of the new facets. Since every edge has length $O((\log m/m)^{1/(d - 1)})$ and any such path has length $O(\log m)$, the distance from the origin to the new facet may not be smaller than $1 - O([(\log m) (\log m/m)^{1/(d - 1)}]^2)$. This argument is made precise by the following series of claims.

In the first claim we deal with the diameter of a facet. For polytope diameter has a few different meanings, here we mean the metric diameter; i.e. For a polytope $P$ we use ``diameter" to mean the supremum distance under the Euclidean metric between any two points of $P$.

\begin{claim}\label{triangle}
If $P$ is a polytope circumscribed around the unit sphere in $\R^d$ with every vertex of $P$ at distance at most $(1 + \epsilon)$ from the origin for $\epsilon > 0$, then the diameter of every facet of $P$ is at most $\sqrt{12 \epsilon + 6 \epsilon^2}$.
\end{claim}
\begin{proof}
Let $u$ and $v$ be points in some facet $\sigma$ of $P$ and let $\Delta$ denote the triangle on vertices $0$, $u$, and $v$. Then we have
\[\dist(u, v)^2 = ||u||^2 + ||v||^2 - 2||u||||v|| \cos\theta\]
where $\theta$ is the angle between $||u||$ and $||v||$. Now as $||u||$ and $||v||$ are both between $1$ and $(1 + \epsilon)$ and the entire segment from $u$ to $v$ lives outside of the unit sphere we have that the altitude from the origin to the segment from $u$ to $v$ has length at least 1. From this it follows that
\[\cos \frac{\theta}{2} \geq \frac{1}{1 + \epsilon} \]
and so
\begin{eqnarray*}
\dist(u, v)^2 &\leq& 2(1 + \epsilon)^2 - 2 \left(2\frac{1}{(1 + \epsilon)^2} - 1\right) \\
&=& 4 + 4\epsilon + 2 \epsilon^2 - \frac{4}{(1 + \epsilon)^2}  \\
&=& \frac{8 \epsilon + 4 \epsilon^2}{(1 + \epsilon)^2} + 4 \epsilon + 2 \epsilon^2 \\
&<& 12 \epsilon + 6 \epsilon^2
\end{eqnarray*}
\end{proof}
We point out that what we've proved here implies that under the assumptions of Claim \ref{triangle} every edge of $P$ has length at most $\sqrt{12 \epsilon + 6 \epsilon^2}$, but the claim is quite a bit stronger; this will be convenient later.
\begin{claim}\label{shortedges}
For $\epsilon > 0$ and $P \sim P_1(d, m)$ with probability at least \[1 - \binom{m}{d} \left(1 - \frac{\sqrt{2 \epsilon}^{d - 1}v_{d - 1}}{dv_d} \right)^{m - d}\] every facet of $P^{\circ}$ has diameter at most $\sqrt{12 \epsilon + 6 \epsilon^2}$. Thus with high probability every facet of $P^{\circ}$ has diameter $O((\log m/m)^{1/(d - 1)})$ where the implied constant depends only on $d$.
\end{claim}
\begin{proof}
This is immediate from Lemma \ref{HausdorffOutside} and Claim \ref{triangle}.
\end{proof}
Now that we have that all of the edges of $P^{\circ}$ will be short we turn our attention to the number of vertices above new facets in $Q$. This argument will be similar to the argument from Lemma \ref{HausdorffOutside}.
\begin{claim}\label{DiscreteCaps}
If $P$ is a nondegenerate simple $d$-polytope on at most $n$ vertices and $Q \sim \B(P, p)$ with $p \in [0, 1]$ then for any $t$ the probability that $Q$ has a new facet with at least $t$ vertices above it is at most
\[\binom{n}{d} p^d (1 - p)^t\]
\end{claim}
\begin{proof}
Let $\sigma$ be a facet determined by $d$ vertices of $P$ which are not on any facet of $P$ with $t$ vertices above the hyperplane of $\sigma$. Then $\sigma$ is a facet of $Q$ only if every vertex of $\sigma$ belongs to $Q$ and the vertices above it do not belong to $Q$. Thus the probability that $\sigma$ is a facet of $Q$ is therefore at most $p^d (1 - p)^t$. As there are at most $\binom{n}{d}$ choices for $\sigma$ we have that the expected number of new facets with exactly $t$ vertices above each of them is at most
\[\binom{n}{d} p^d (1 - p)^t.\]
The claim now follows by Markov's inequality.
\end{proof}

Now we have all the pieces in place to bound from below how close to the origin the facets of $Q$ may be.
\begin{lemma}\label{insideprob}
If $d$ is fixed and $p$ and $m$ are such that $pm^{1/(d - 1)}$ tends to infinity as $m$ tends to infinity then with high probability every facet of $Q \sim P_2(d, m, p)$ is at distance at least
\[1 - \Omega\left(\frac{ \log^2(mp) (\log m)^{2/(d - 1)}}{p^2m^{2/(d - 1)}}\right) \]
from the origin.
\end{lemma}
\begin{proof}
By Theorem \ref{vertexconcentration} there exists a constant $c_1$ so that with high probability $P^{\circ}$ for $P \sim P_1(d, m)$ has at most $c_1 m$ vertices. In this case we may apply Claim \ref{DiscreteCaps} with $n = c_1 m$ and we have that there is $c_2 > 1$ so that with high probability every new facet of $Q \sim \B(P^{\circ}, p)$ has at most  $c_2 (\log (pm))/p$ vertices above it.  Moreover by Claim \ref{shortedges} exists $c_3$ so that with high probability every facet of $P^{\circ}$ has diameter at most $c_3((\log m/m)^{1/(d - 1)})$. In the likely case that all of these conditions hold we have that for any hyperplane $\sigma$ determining a new facet of $Q$ there is a path of length at most
\[\frac{c_2c_3 \log(pm) (\log m)^{1/(d - 1)}}{pm^{1/(d - 1)}}\]
from the point of $P^{\circ}$ where the orthogonal vector to $\sigma$ crosses $P^{\circ}$ to a vertex of $P^{\circ}$ defining $\sigma$. This holds because this point of intersection, $w$ belongs to some facet of $P^{\circ}$ so it is within distance at most $c_3((\log m/m))^{1/(d - 1)}$ of some vertex of $P^{\circ}$ and from here we may follow a path in the graph induced by $\mathcal{C}(\sigma)$ back to some vertex of $\sigma$. As we have bounded the number of vertices above $\sigma$, the number of edges of this path is at most $c_2 (\log (pm))/p  - 1$ and each edge has length at most $c_3((\log m/m))^{1/(d - 1)}$ by the diameter assumption. However as every vertex defining $\sigma$ and $w$ are all at distance at least 1 from the origin, the distance from the origin to $\sigma$ is at least
\[1 - \frac{1}{2}\left(\frac{c_2c_3 \log(pm) (\log m)^{1/(d - 1)}}{pm^{1/(d - 1)}}\right)^2.\]
To see this, consider the triangle determined by $w$, the origin, and $v$ an arbitrary vertex of $P^{\circ}$ on $\sigma$. We have that $\dist(w, v) \leq \frac{c_2c_3 \log(pm) (\log m)^{1/(d - 1)}}{pm^{1/(d - 1)}}$, $||w|| \geq 1$, and $||v|| \geq 1$. Now the distance from the origin to the hyperplane $\sigma$ is given by the length of the projection of $v$ onto $w$, as $w$ is a normal vector to $\sigma$. It follows that
\[\dist(0, \sigma) = \frac{||w||^2 + ||v||^2 - \dist(w, v)^2}{2||w||},\]
by the law of cosines.
Now as both $||w||$ and $||v||$ are at least one we have that $||w||^2 + ||v||^2 \geq 2||w||$ and
\[\dist(0, \sigma) \geq 1 - \frac{\dist(w, v)^2}{2}.\]
\end{proof}

\begin{proof}[Proof of Theorem \ref{Hausdorffdistance}]
There exists a constant $\gamma$ depending on $d$ so that with high probability the boundary of $Q \sim P_2(d, m, p)$ lives outside the sphere of radius
\[1 - \frac{ \gamma \log^2(mp) (\log m)^{2/(d - 1)}}{p^2m^{2/(d - 1)}}\]
centered at the origin by Lemma \ref{insideprob}. Moreover the exists $\Gamma$ depending on $d$ so that with high probability $Q$ is contained entirely in the sphere of radius
\[1+\left( \frac{\Gamma \log (pm^d)}{m} \right)^{2/(d - 1)} \]
centered at the origin by Lemma \ref{HausdorffOutside}.
\end{proof}
As a corollary to the proof of Theorem \ref{Hausdorffdistance} we have the following result about the volume of $Q \sim P_2(d, m, p)$.

\begin{corollary}
With high probability the volume of $Q \sim P_2(d, m, p)$ is between
\[v_d \left(1 - \frac{ \gamma \log^2(mp) (\log m)^{2/(d - 1)}}{p^2m^{2/(d - 1)}}\right)^{d}\]
and
\[v_d \left(1+\left(\frac{\Gamma\log (pm^d)}{m} \right)^{2/(d - 1)}\right)^d\]
where $\gamma$ and $\Gamma$ are constants depending only on $d$.
\end{corollary}

\section{Concluding remarks}
Figure \ref{fig:examples} shows results of an experiment examining $P_2(d, m, p)$. Using \polymake \cite{polymake:2000} three random simple polytopes were generated: one in dimension 3, one in dimension 4, and one in dimension 5 as $P^{\circ}$ for $P \sim P_1(d, m)$.  For each $d = 3, 4, 5$, $m$ was chosen so that the resulting circumscribed, simple polytope would have about 500 vertices. Next a stochastic process version of the model $\B(P, p)$ was implemented, in this case taking each polytope and at each step deleting a random subset of the remaining vertices of size about 5 percent of the \emph{total} number of vertices. The results in Figure \ref{fig:examples} show $q = 1 - p$ on the $x$-axis against the number of facets of the random polytope normalized by the number of vertices at the start. The result of the \polymake experiment alone suggest that it would be interesting to understand the behavior of $P_2(d, m, p)$ as $p$ ranges from $0$ to $1$, for instance to establish $p_0 \in [0, 1]$ which maximizes the asymptotic complexity.
\begin{figure}[h]
\centering
\includegraphics[scale = 1]{DoublyRandomImage.pdf}
\caption{Density of deleted vertices $q$ against the normalized number of facets for a random 3-polytope (red), 4-polytope (blue), and 5-polytope (orange)}\label{fig:examples}
\end{figure}

 To this point we can only say something about the complexity for small values of $q$. However, the restriction to small values of $q$ in the proof of Theorem \ref{upperbound} likely has more to do with the method of proof than anything about the random model; it seems completely reasonable to expect that linear complexity will hold for all fixed values of $q \in [0, 1]$. Essentially the argument to prove Theorem \ref{upperbounddeterministic} studies the combinatorial structure of $Q \sim \B(P, p)$ by studying the graph structure of the graph induced on the vertices of $P$ not included in the random sample. This approach is also implicit in the proof of Lemma \ref{insideprob}, a key lemma for the proof of Theorem \ref{Hausdorffdistance}.

Underlying the proof of Theorem \ref{upperbounddeterministic} is a question about percolation for a random induced subgraph of the 1-skeleton of $P$ where each vertex is sampled independently with probability $q$. If $q$ is small, something implicit in our theorem is that every component of the resulting graph will be small, of order $O(\log n)$. Connected subgraphs of $Q$ in turn tell us something about the number of facets of $P$. As $q$ grows larger there should come a point where the induced graph contains a \emph{giant component} as occurs in the Erd\H{o}s--R\'{e}nyi model and so the argument would need to be changed.

One could push the upper bound to work for larger values of $q$ by first using Lemma \ref{DiscreteCaps} to find some reasonable $t_0$ so there is a very small probability that $Q \sim \B(P, p)$ has a new facet $\sigma$ so that $\mathcal{C}(\sigma) \geq t_0$, and then the infinite sum in the proof of Theorem \ref{upperbounddeterministic} can be replaced with a finite sum up to $t_0$. However in the case of $Q \sim P_2(d, m, p)$, $p, d$ fixed and $m$ tending to infinity, this $t_0$ would be of order $\log(m)$ so the $4^{t_0}$ in the upper bound of Theorem \ref{upperbounddeterministic} could give an upper bound which exceeds McMullen's upper bound theorem.

\section*{Acknowledgments}
The author is grateful to Michael Joswig and to Matthias Reitzner for several helpful comments on an earlier draft.

\section*{Appendix: An application of the doubly-random model}

This appendix is motivated by an application of random polytopes considered in \cite{JKR}.  In \cite{JKR}, Joswig, Kaluba, and Ruff consider randomized methods for approximating the convex hull of a finite set for outlier detection in machine learning. Given a finite set $X$, arising from a real data set, the authors  use a \emph{dual bounding body} construction to approximate $X$; the goal is then to use the dual bounding body to decide whether a new point is close to $X$. This dual bounding body construction of \cite{JKR} is based on the dual $P^{\circ}$ of $P \sim P_1(d, m)$, and an important step to determine the average of the vertices of this dual bounding body. Unfortunately, the dual bounding body may have very many vertices and so precisely determining the center may not be computationally feasible. To this end, the question become how well can a sample of the vertices from the dual bounding body approximate the center. Because the dual bounding body is a modified version of the dual of $P \sim P_1(d, m)$ taking a sample of its vertices is closely tied to $Q \sim P_2(d, m, p)$. For the purposes of applying what's been established here to the dual bounding body construction of \cite{JKR} we are interested in the following question.

\begin{question}\label{approximationquestion}
For $m > d \geq 2$, $\pi \in [0, 1]$ and $\epsilon > 0$, how large should be $N = N(m, d, \pi, \epsilon)$ so that with probability at least $1 - \pi$ the center of a random sample of $N$ vertices from $P^{\circ}$, $P \sim P_1(d, m)$ is within distance $\epsilon$ of the origin?
\end{question}

Here we do have to be a bit careful about the random sample is selected.  The vertices of $P_2(d, m, p)$ are sampled independently with probability $p$, thus the probability that a single vertex is included is the same for all vertices of the initial random polytope. In practice though to sample in this way one would need to know all the vertices of $P^{\circ}$. Instead one may take a sample of $N$ vertices of $P^{\circ}$ via optimizing uniform random linear objective functions on the unit sphere. This does not assign equal probability to the vertices of $P^{\circ}$ but for $N$ fixed and $m \rightarrow \infty$, in practice this likely does not make much of a difference so we ignore the technicalities between these two ways of randomly choosing a set of vertices.

One key step toward answering Question \ref{approximationquestion} is the result about the Hausdorff distance of $Q \sim P_2(d, m, p)$ to the unit sphere, especially Lemma \ref{HausdorffOutside}. A second step is the following lemma about how close the average value of points on a sphere of radius $R$ in $\R^d$ is to the origin.
\begin{lemma}\label{spherecenter}
Fix $d$ a positive integer and $R, \pi, \epsilon > 0$ then for $N \geq \frac{2R^2}{\epsilon^2}\left(1 + \frac{2}{d} \log \left(\frac{1}{\pi}\right) \right)$ points $v_1, ..., v_N$ chosen uniformly at random from the boundary of the $d$-dimensional ball of radius $R$ centered at the origin in $\R^d$ one has that with probability at least $1 - \pi$,
\[\frac{1}{N}||v_1 + \cdots + v_N|| \leq \epsilon.\]
\end{lemma}
In the case that $d = 1$ this lemma gives a concentration inequality for summing up $N$ random number each of which is uniformly selected from $\{-1, 1\}$. This is a problem that has been considered in the past, see for example Appendix A of \cite{AS}, but it seems that a result like Lemma \ref{spherecenter} as precise as we need here and for $d > 1$ does not appear in the literature.
\begin{proof}[Proof of Lemma \ref{spherecenter}]
Let $d$, $R$, $\pi$, and $\epsilon$ be given as in the statement. Let $X_i$ denote the random variable given by projection of a random point on the sphere of radius $R$ centered at the origin in $\R^d$ onto the $i$th coordinate. By symmetry $\E(X_i) = 0$ and for any pair $1 \leq i \leq j \leq n$, $X_i$ and $X_j$ have the same distribution. Moreover we always have
\[\sum_{i = 1}^d (X_i)^2 = R\]
Thus $\E(X_i^2) = R^2/d$, hence $\Var(X_i) = \E(X_i^2) - [E(X_i)]^2 = R^2/d$. If we sample $v_1, ..., v_N$, uniformly at random from the sphere of radius $R$ in $\R^d$, then by the central limit theorem the average of the $i$th coordinate of $v_1, ..., v_N$ will be asymptotically in $N$ distributed as a Gaussian with mean $0$ and variance $R^2/(dN)$.

Now if the coordinate averages were independent from one another we could approximate
\[\frac{||v_1 + \cdots + v_{N}||^2}{N^2}\]
 by the sum of $d$ independent copies of $[\mathcal{N}(0, R^2/(dN))]^2$. Such a sum is distributed as
\[\frac{R^2}{dN} \chi^2(d) \]
Where $\chi^2(d)$ denotes the chi-squared distribution with $d$ degrees of freedom.

The coordinate averages of course are not independent from one another, however it does hold that
\[\Pr\left(\frac{||v_1 + \cdots + v_N||^2}{N^2} \geq \epsilon^2\right) \leq \Pr\left(\frac{R^2}{dN}\chi^2(d) \geq \epsilon^2\right). \]
That is, sampling each coordinate average independently from a normal distribution with mean zero and variance $R^2/(d N)$ could only increase the probability that the square of the sum of the averages exceeds $\epsilon^2N^2$. Next by Chernoff bound we have that
\[\Pr \left(\frac{R^2}{dN}\chi^2(d) \geq \epsilon^2\right) \leq \left(\frac{\epsilon^2 N}{R^2} \exp(1 - \epsilon^2 N/R^2) \right)^{d/2}\]
Now we see that by setting
\[N \geq \frac{2R^2}{\epsilon^2}\left(1 + \frac{2}{d} \log \left(\frac{1}{\pi}\right) \right) \]
we have that the right hand side is at most $\pi$. Indeed

\begin{eqnarray*}
&&\left[2 \left(1 - \frac{2}{d} \log \pi \right) \exp\left(1 - \left(2\left(1 + \frac{2}{d} \log\left(\frac{1}{\pi}\right) \right)\right)\right)\right]^{d/2}\\
&& \leq 2^{d/2} \pi^{-1} \exp \left(-d/2 + 2\log(\pi)\right) \\
&& \leq \pi
\end{eqnarray*}
\end{proof}

We close by describing how one could use Lemma \ref{HausdorffOutside} and Lemma \ref{spherecenter} to answer Question \ref{approximationquestion}. As we are already ignoring the discrepancy in two methods of choosing the vertices anyway, we omit some details here and don't make a precise statement, but sketch the idea.

Given $d$, $m$, $\epsilon$ and $\pi$, one can apply Lemma \ref{HausdorffOutside} to find $p$ so that every vertex of $Q \sim P_2(d, m, p)$ is within distance $1 + \epsilon$ of the origin. This $p$ correspond to $N_1 = p(F(d)m)$. Next we take $R$ of Lemma \ref{spherecenter} to be $1 + \epsilon$ and we take $N_2$ as in Lemma \ref{spherecenter}, if $N_2 < N_1$ then $N = N_2$ gives an answers to Question \ref{approximationquestion} for some easily computable scalar multiples of $\epsilon$ and $\pi$.  Some values of $\epsilon$ and $\pi$ are too small relative to $m$ and $d$ for $N_2$ to be smaller than $N_1$, and in this case we wouldn't get an answer, but this is less of a concern as $m$ grows.

\bibliography{ResearchBibliography}
\bibliographystyle{amsplain}
\end{document}

config: arxiv


TITLE: List of structure theorems for vector valued Siegel modular forms (esp. of genus 2)
QUESTION [1 upvotes]: What are Siegel modular forms?
We start with defining their common domains $\mathbb{H}_g$ as the set of symmetric $g \times g$ matrices with positive definite imaginary parts.
The symplectic group $Sp(g,\mathbb{Z})$ is the subgroup of $SL(2g,\mathbb{Z})$ such that all elements satisfy $M=J_g^t M J_g$ with $J_g$ being the canonical almost complex structure. $J_g$ is also known as involution.
$Sp(g,\mathbb{Z})$ acts on $\mathbb{H}_g$ by $M(Z)=(AZ+B)(CZ+D)^{-1}$ where A,B,C and D are the block matrix entries of M.
Let $\rho : GL(g,\mathbb{C}) \to GL(V)$ be a rational representation on a finite dimensional $\mathbb{C}$-vector space then the associated modular forms are the holomorphic functions $f : \mathbb{H}_g \to V$ satisfying $f(M(Z))=\rho(CZ+D)f(Z)$ for all $M \in \Gamma < Sp(g,\mathbb{Z})$.
Since the determinant is also a representation scalar valued modular forms are included in this definition. If $V$'s dimension is 2 or higher then we speak of a vector valued Siegel modular form.
We can spice this definition up by allowing square roots of the determinant $\sqrt{det(CZ+D)}$. Here, we have to solve the ambiguity by a multiplier system $v$. Then we have
$$f(M(Z))=v(M) \cdot \left(\sqrt{det(CZ+D)}\right)^r \cdot \rho(CZ+D)f(Z).$$
Structure theorems
If we fix a representation $\rho_0$ and a subgroup $\Gamma$ but allow arbitrary powers of $\left(\sqrt{det(CZ+D)}\right)^r$ or $det(CZ+D)^k $ , resp., then all functions satisfying
$$ f(M(Z))=v(M) \cdot \left(\sqrt{det(CZ+D)}\right)^r \cdot \rho_0(CZ+D)f(Z)\quad \forall M \in \Gamma $$
form a module over (a subring of) the ring of scalar modular forms of $\Gamma$ (to the multiplier system $v$).
This module is always finitely generated. But it seems hard to find such a finite set of generators and even more all the relations between them. Without these relations it is possible to miss out a nicer description of elements in the module.
For me a structure theorems is a theorem that returns for a group and a representation such a finite set and the relations.
The actual question
Which structure theorems of vector valued Siegel modular forms are known? I'm personally most interested in genus 2.
I would make the question community because I don't expect a uniform theorem but couldn't find the button.
I already got some answers but I'm not sure how to post : all in one answer, one group $\Gamma$ (and one representation $\rho_0$) per answer, one paper per answer ???
Comments on this issue are very welcome. Afterwards I'm very happy to type this half of a dozen papers.
p.s. I hope the post is not too chaotic.

REPLY [0 votes]: In the preprint "Explicit computations of Siegel modular forms of degree two", which you can find here on arXiv, Raum, Ryan, Skoruppa and Tornaria recall quite a few structural results about Siegel modular forms in general, in degree two in particular, and with quite a few references ; it should cover this question quite nicely.