# Induced Monoidal structure from the functor

Neha Gupta
neha.gupta@snu.edu.in,pradip.kumar<EMAIL_ADDRESS>and
Pradip kumar  Department of Mathematics
Shiv Nadar University, Dadri
U.P. 201314, India

###### Abstract.

Let $\mathcal{B}$ be a subcategory of a given category $\mathcal{D}$. Let
$\mathcal{B}$ has monoidal structure. In this article, we discuss when can one
extend the monoidal structure of $\mathcal{B}$ to $\mathcal{D}$ such that
$\mathcal{B}$ becomes a sub monoidal category of monoidal category
$\mathcal{D}$. Examples are discussed, and in particular, in an example of
loop space, we elaborated all results discussed in this article.

###### Key words and phrases:

Monoidal structure, Dualizable object, loop space, tensor product

###### 2010 Mathematics Subject Classification:

18D10,19D23, 55P35

##  1\. Introduction

We start from a few examples of a category $\mathcal{B}$

  1. (1)

Let $\mathcal{B}$ be the category of one dimensional closed oriented manifolds
without boundary and arrows as the oriented cobordism classes. It has monoidal
structure given by disjoint union and empty set, see [3]. Let $\mathcal{D}$ be
the category whose objects are the oriented cobordism classes between objects
of $\mathcal{B}$ with arrows defined in a special way (details are discussed
in the example 3.3).

  2. (2)

Let $\mathcal{B}$ be the category of finite dimensional vector spaces over
$\mathbb{R}$ with usual tensor product of vector spaces. If $\mathcal{D}$ be
the category having objects as loop spaces and morphisms defined in a special
way (details are discussed in the section 5).

For both these setups, we ask a natural question, that from $\mathcal{B}$, can
we get a monoidal structure on the category $\mathcal{D}$. In this article we
discussed about this type of question. More precisely, in theorem 4.6, we
proved that under certain conditions, we can provide a monoidal structure on a
category $\mathcal{D}$ from a given monoidal structure on some category
$\mathcal{B}$

When $\mathcal{B}$ is a subcategory, the induced monoidal structure (as in
theorem 4.6) on $\mathcal{D}$ , from $\mathcal{B}$ is the extension of the
monoidal structure in the sense that $\mathcal{B}$ becomes the monoidal
subcategory of $\mathcal{D}$. This extension is not same as the graded
extension of the monoidal category discussed in [1]. In [4], Ponto Kate and
Shulman Michael have discussed the concept of a normal lax symmetric monoidal
functor between two monoidal categories; and using such a functor we have got
an induced monoidal structure on the category $\mathcal{D}$. Our article is
based on the discussion in [4].

In section 2, we revise the basics about the monoidal category, dual objects
and strong lax symmetric monoidal functor. Section 3 and 4 discuss the induced
tensor with its various properties and examples. In the last section 5, we did
explicit calculation for the case of loop space.

##  2\. Preliminaries

###  2.1. Monoidal category

We first set the terminology that we use throughout the article which can be
found in [6],[4],[2] etc. We begin with a few terms from category theory. A
monoidal category is a collection of data
$(\mathcal{C},\otimes,\mathbb{I},a,\lambda,\rho)$ where $\mathcal{C}$ is a
category, $\otimes$ is a functor from $\mathcal{C}\times\mathcal{C}$ to
$\mathcal{C}$ called the tensor product, an associator $a$ for $\otimes$ which
is a family of isomorphisms

(1) $a_{X,Y,Z}:(X\otimes Y)\otimes Z\to X\otimes(Y\otimes Z),$

an unit object $\mathbb{I}$ of $\mathcal{C}$, and a left unitor $\lambda$ and
a right unitor $\rho$ with respect to $\mathbb{I}$ which are also a family of
isomorphisms

(2) $\lambda_{X}:\mathbb{I}\otimes X\to X$ (3) $\rho_{X}:X\otimes\mathbb{I}\to
X$

such that these isomorphisms $(a,\lambda,\rho)$ satisfy certain coherence
conditions (for details we refer [2]). To name, these conditions are the
Pentagon identity and the Triangle identities. Note that the existence of the
associator ensures that the tensor product $\otimes$ is associative up to
isomorphism and the existence of the unitors ensure that $\mathbb{I}$ serves
as a unit for $\otimes$, up to isomorphism.

Let $X$ and $Y$ be objects in $\mathcal{C}$. We say $X$ has a left dual $Y$
(or $Y$ has a right dual $X$) if there is

  1. $\cdot$

a morphism $ev:Y\otimes X\to\mathbb{I}$ (called evaluation), and

  2. $\cdot$

a morphism $coev:\mathbb{I}\to X\otimes Y$ (called coevaluation)

such that the compositions

$\setcounter{MaxMatrixCols}{11}\begin{CD}X@>{\lambda^{-1}_{X}}>{}>\mathbb{I}\otimes
X@>{coev\otimes\text{Id}_{X}}>{}>(X\otimes Y)\otimes
X@>{a_{X,Y,X}}>{}>X\otimes(Y\otimes X)@>{\text{Id}_{X}\otimes
ev}>{}>X\otimes\mathbb{I}@>{\rho_{X}}>{}>X\end{CD}$

and

$\setcounter{MaxMatrixCols}{11}\begin{CD}Y@>{\rho^{-1}_{Y}}>{}>\mathbb{I}\otimes
Y@>{\text{Id}_{Y}\otimes coev}>{}>Y\otimes(X\otimes
Y)@>{a^{-1}_{Y,X,Y}}>{}>(Y\otimes X)\otimes
Y@>{ev\otimes\text{Id}_{Y}}>{}>\mathbb{I}\otimes
Y@>{\lambda_{Y}}>{}>Y\end{CD}$

are both identity. If $X$ has a left [right] dual, we say that $X$ is left
[right] dualizable, If the left and right duals are isomorphic in
$\mathcal{C}$, we say $X$ is dualizable, and in general the dual of $X$ is
denoted as $X^{*}$.

Let $\mathcal{C}$ and $\mathcal{D}$ be symmetric monoidal categories. There is
a special functor which takes dualizable object in $\mathcal{C}$ to dualizable
object in $\mathcal{D}$. Below we give the precise definition of such a
functor and recall required properties (for detail we refer to [4]).

######  Definition 2.1 (Lax Symmetric monoidal functor).

Lax symmetric monoidal functor between symmetric monoidal categories consists
of a functor $\mathcal{F}:\mathcal{C}\to\mathcal{D}$ and natural
transformations

$c:\mathcal{F}(M)\otimes\mathcal{F}(N)\to\mathcal{F}(M\otimes N)$
$i:\mathbb{I}_{\mathcal{D}}\to\mathcal{F}(\mathbb{I}_{\mathcal{C}})$

satisfying appropriate coherence axioms.

$\mathcal{F}$ is normal if $i$ is an isomorphism and $\mathcal{F}$ is strong
if both $c$ and $i$ are isomorphism.

######  Proposition 2.2 (Prop.6.1, [4]).

If $\mathcal{F}:\mathcal{C}\to\mathcal{D}$ be normal lax symmetric monoidal
functor, let $M\in Ob(\mathcal{C})$ be dualizable with dual $M^{*}$ and assume
that $c:\mathcal{F}(M)\otimes\mathcal{F}(M^{*})\to\mathcal{F}(M\otimes M^{*})$
is an isomorphism then $\mathcal{F}(M)$ is dualizable with dual
$\mathcal{F}(M^{*})$.

##  3\. Monoidal structure on Image of $\mathcal{F}$

Let $\mathcal{C}$ and $\mathcal{D}$ be two categories where $\mathcal{C}$ has
a monoidal structure given by $(\otimes,a,\lambda,\rho)$. Let
$\mathcal{F}:\mathcal{C}\to\mathcal{D}$ be a functor, then
$\text{Im}(\mathcal{F})$ which is the collection of the images of all objects
and morphisms in $\mathcal{C}$ under $\mathcal{F}$ becomes a subcategory of
$\mathcal{D}$. With this set up we wish to give a monoidal structure on
$\text{Im}(\mathcal{F})$. If $\mathcal{F}$ satisfies certain conditions, which
we discuss below, then the category $\text{Im}(\mathcal{F})$ has monoidal
structure induced from $\mathcal{C}$.

Let the functor $\mathcal{F}$ satifies following conditions: for any pair of
objects $a_{1}$, $a_{2}$ and $a_{3}$, $a_{4}$ in $\mathcal{C}$, such that
whenever we have

(4) $\mathcal{F}(a_{1})=\mathcal{F}(a_{2})\text{ and
}\mathcal{F}(a_{3})=\mathcal{F}(a_{4})$

then

$\mathcal{F}(a_{1}\otimes a_{3})=\mathcal{F}(a_{2}\otimes a_{4})$

We have similar conditions on morphisms also. For any pair $f,f^{\prime}$ and
$g,g^{\prime}$ of morphisms in $\mathcal{C}$, such that

(5) $\mathcal{F}(f)=\mathcal{F}(f^{\prime})\text{ and
}\mathcal{F}(g)=\mathcal{F}(g^{\prime})$

then, we have

$\mathcal{F}(f\otimes g)=\mathcal{F}(f^{\prime}\otimes g^{\prime})$

We use the notation $\mathcal{B}$ for $\text{Im}{(\mathcal{F})}$ and we define
the monoidal functor $\otimes_{\mathcal{F}}$ on $\mathcal{B}$ where,

$\otimes_{\mathcal{F}}:\mathcal{\mathcal{B}}\times\mathcal{\mathcal{B}}\to\mathcal{\mathcal{B}}$

as follows: on objects,

$\otimes_{\mathcal{F}}(b_{1},b_{2}):=\mathcal{F}(a_{1}\otimes a_{2})$

where $b_{1}=\mathcal{F}(a_{1})$ and $b_{2}=\mathcal{F}(a_{2})$. The condition
(4) on functor ensures that this is well defined on objects. On morphisms,

$\otimes_{\mathcal{F}}(f_{1},f_{2}):=\mathcal{F}(h_{1}\otimes h_{2})$

where $f_{1}=\mathcal{F}(h_{1})$ and $f_{2}=\mathcal{F}(h_{2})$. Condition (5)
will make sure that this is also well defined as a map. Compatibility of
$\otimes_{\mathcal{F}}$ with composition in $\mathcal{B}$ will be followed
from the compatibility of the tensor $\otimes$ with composition in
$\mathcal{C}$. Again, the compatibility of $\otimes_{\mathcal{F}}$ with
identity maps of $\mathcal{B}$ will require only the compatibility of the
tensor $\otimes$ with identity maps of $\mathcal{C}$. Explicitly, we want to
show that the equation $\text{Id}_{b_{1}\otimes
b_{2}}=\text{Id}_{b_{1}}\otimes_{\mathcal{F}}\text{Id}_{b_{2}}$ is true in
$\mathcal{B}$ where $b_{1}$ and $b_{2}$ are objects in $\mathcal{B}$, such
that $b_{\mathbb{I}}=\mathcal{F}(a_{1})$ and $b_{2}=\mathcal{F}(a_{2})$, for
some objects $a_{1}$ and $a_{2}$ in $\mathcal{C}$. Then
$b_{1}\otimes_{\mathcal{F}}b_{2}=\mathcal{F}(a_{1}\otimes a_{2})$ and the easy
calculations shown below gives the result.

$\displaystyle\text{Id}_{b_{1}}\otimes_{\mathcal{F}}\text{Id}_{b_{2}}$
$\displaystyle=$
$\displaystyle\text{Id}_{\mathcal{F}(a_{1}})\otimes_{\mathcal{F}}\text{Id}_{\mathcal{F}(a_{2})}$
$\displaystyle=$
$\displaystyle\mathcal{F}(\text{Id}_{a_{1}})\otimes_{\mathcal{F}}\mathcal{F}(\text{Id}_{a_{2}})$
$\displaystyle=$
$\displaystyle\mathcal{F}\big{(}\text{Id}_{a_{1}}\otimes\text{Id}_{a_{2}}\big{)}$
$\displaystyle=$ $\displaystyle\mathcal{F}\big{(}\text{Id}_{a_{1}\otimes
a_{2}}\big{)}$ $\displaystyle=$
$\displaystyle\text{Id}_{\mathcal{F}(a_{1}\otimes a_{2})}$ $\displaystyle=$
$\displaystyle\text{Id}_{b_{1}\otimes b_{2}}.$

This defines a tensor product $\otimes_{\mathcal{F}}$ on $\mathcal{B}$. For
$\mathcal{B}$ to have a monoidal structure we want the left and right unitors
as well as the associator in $\mathcal{B}$. These are nothing but
$\mathcal{F}(a)$, $\mathcal{F}(\lambda)$, $\mathcal{F}(\rho)$ where $a$,
$\lambda$ and $\rho$ are the respective left unitor, right unitor and
associator of $\mathcal{C}$ and they will satisfy the triangle and pentagon
axioms since they are true in $\mathcal{C}$. Thus we have proved the
following.

######  Theorem 3.1.

If $\mathcal{F}$ is a functor from a monoidal category $(\mathcal{C},\otimes)$
to a category $\mathcal{D}$ that satisfies the following conditions

  1. (1)

for any objects $a_{1},a_{2},a_{3},a_{4}$ in $\mathcal{C}$ such that
$\mathcal{F}(a_{1})=\mathcal{F}(a_{2})\;\;and\;\;\mathcal{F}(a_{3})=\mathcal{F}(a_{4})$,
then we have $\mathcal{F}(a_{1}\otimes a_{3})=\mathcal{F}(a_{2}\otimes
a_{4})$,

  2. (2)

for any morphisms $f,g,f^{\prime},g^{\prime}$ in $\mathcal{C}$ if
$\mathcal{F}(f)=\mathcal{F}(f^{\prime})=h;\;\;\mathcal{F}(g)=\mathcal{F}(g^{\prime})=k\text{
then, we have}$ $\mathcal{F}(f\otimes g)=\mathcal{F}(f^{\prime}\otimes
g^{\prime})$.

Then $\mathcal{F}$ induces a monoidal structure on $\text{Im}(\mathcal{F})$.

######  Example 3.2.

Let $\mathcal{D}$ be a monoidal category with tensor $\otimes_{D}$ and
$\mathcal{C}=\mathcal{D}\times\mathcal{D}$, then $\mathcal{C}$ is also a
monoidal category with obvious tensor, defined component-wise. Define a
functor $\mathcal{F}:\mathcal{C}\to\mathcal{D}$ such that it associates to
each object $(X,Y)$ in $\mathcal{C}$ to $X$ in $\mathcal{D}$ and to each
morphism $(f,g)\in Hom(X_{1},Y_{1}),(X_{2},Y_{2}))$ to $f\in
Hom(X_{1},Y_{1}).$

One can think of the functor $\mathcal{F}$ as a projection onto the first
component. Further, $\mathcal{F}$ also satisfies both the condition of theorem
3.1. Therefore we have a monoidal structure $\otimes_{\mathcal{F}}$ on
$\mathcal{D}$. Moreover, both monoidal structures $\otimes_{D}$ and
$\otimes_{\mathcal{F}}$ are same.

######  Example 3.3.

(See, [3]) Let $\mathcal{A}$ be the category having 1-dimensional compact
oriented manifold without boundary as objects along with the empty set.
Morphism between any two objects $X$ and $Y$ is the oriented cobordism class.
We write a representative of this class and also the class as $(W,X,Y)$ where
$W$ denotes a 2-dimensional oriented cobordism between $X$ and $Y$.
Composition of morphism is given by gluing the representatives of the two
cobordism classes. Kock in [3] has discussed that the result of this gluing
does not depend on the actual cobordisms chosen; rather only their class. The
class of cylinders is the identity for the composition. Monoidal structure on
$\mathcal{B}$ is the disjoint union of the objects and the of the cobordisms.
The Tensor between two morphisms $(W_{1},X_{1},Y_{1})$ and
$(W_{2},X_{2},Y_{2})$ is a cobordism class $(W_{1}\sqcup W_{2},X_{1}\sqcup
X_{2},Y_{1}\sqcup Y_{2})$. The unit object of $\mathcal{B}$ is the empty set.

Consider the product category $\mathcal{A}\times\mathcal{A}$ and call it as
$\mathcal{B}$. Use the tensor on $\mathcal{A}$ to give a monoidal structure on
$\mathcal{B}$. It is defined in the obvious way as component-wise. In
particular, the unit object here is $(\emptyset,\emptyset)$.

We now define a category $\mathcal{D}$ with objects as oriented 2-dimensional
cobordism classes, which have oriented cobordisms between the objects of
$\mathcal{A}$ but without holes only. As before, we write an object of
$\mathcal{D}$ as $(W,X,Y)$. A morphism between two objects
$(W_{1},X_{1},Y_{1})$ and $(W_{2},X_{2},Y_{2})$ in $\mathcal{D}$ is a pair of
morphisms in $\mathcal{A}$, one between $X_{1}$ and $X_{2}$ and the other
between $Y_{1}$ and $Y_{2}$. Since a morphism of $\mathcal{D}$ is a pair
$(W_{1},W_{2})$ so composition of morphism is the pair wise gluing of the
cobordism classes.

We define a functor $\mathcal{F}:\mathcal{B}\to\mathcal{D}$ such that any
object $(X,Y)$ in $\mathcal{B}$ is taken to the unique cobordism class of
oriented 2-dimensional cobordisms between $X$ to $Y$ (without holes).
$\mathcal{F}$ is identity on morphisms.

Clearly this functor is fully faithful. That is to say that
$\text{Im}(\mathcal{F})$ is whole of $\mathcal{D}$. Further, this functor
satisfies the two conditions of the above theorem 3.1. Hence we get an induced
tensor on $\mathcal{D}$. We discuss this induced functor explicitly later in
examples 4.3.

######  Corollary 3.4.

Let $\mathcal{F}:\mathcal{C}\to\text{Im}(\mathcal{F})$ be a functor as in
theorem 3.1. If $(\mathcal{C},\otimes)$ is symmetric then the category
$(\text{Im}(\mathcal{F}),\otimes_{\mathcal{F}})$ is symmetric as well.

###### Proof.

We need to give a symmetric structure in $\mathcal{D}$ and this will be simply
be the image of the symmetry of $\mathcal{C}$ under the functor $\mathcal{F}$.
Explicitly, if $D_{1},D_{2}\in Ob(Im(\mathcal{F}))$, then there are
$C_{1},C_{2}\in Ob(C)$ such that $\mathcal{F}(C_{1})=D_{1}$ and
$\mathcal{F}(C_{2})=D_{2}$. Since $\mathcal{C}$ is symmetric, therefore there
is a symmetric map, say $s_{C_{1},C_{2}}:C_{1}\otimes C_{2}\to C_{2}\otimes
C_{1}$ which is an isomorphism. Consider
$\mathcal{F}(s_{C_{1},C_{2}}):\mathcal{F}(C_{1}\otimes
C_{2})\to\mathcal{F}(C_{2}\otimes C_{1})$. As $\mathcal{F}$ is a functor
therefore $\mathcal{F}(s_{C_{1},C_{2}})$ is an isomorphism between
$D_{1}\otimes_{\mathcal{F}}D_{2}:=\mathcal{F}(C_{1}\otimes C_{2})$ and
$D_{2}\otimes_{\mathcal{F}}D_{1}:=\mathcal{F}(D_{1}\otimes D_{1})$. ∎

######  Corollary 3.5.

A functor $\mathcal{F}$ between a symmetric monoidal category $\mathcal{C}$ to
$\text{Im}(\mathcal{F})$ where $\text{Im}(\mathcal{F})$ has the induced
monoidal structure from $\mathcal{C}$ and which satisfies the conditions of
theorem (3.1) is a strong lax symmetric monoidal functor.

###### Proof.

This is direct from the definition of the induced monoidal structure on
$\text{Im}(\mathcal{F})$ described in the theorem 3.1, which is,
$D_{1}\otimes_{\mathcal{F}}D_{2}=\mathcal{F}(C_{1}\otimes C_{2})$. Thus by
definition itself we get

$\mathcal{F}(C_{1})\otimes_{\mathcal{F}}\mathcal{F}(C_{2})=\mathcal{F}(C_{1}\otimes
C_{2})$

And

$\mathbb{I}_{\text{Im}(\mathcal{F})}=\mathcal{F}(\mathbb{I}_{\mathcal{C}}).$

∎

######  Corollary 3.6.

If $A\in Ob(\mathcal{C})$ is dualizable in $(\mathcal{C},\otimes)$, then
$\mathcal{F}(A)$ is dualizable in
$(\text{Im}(\mathcal{F}),\otimes_{\mathcal{F}})$.

###### Proof.

Since $\mathcal{F}$ is a strong lax symmetric monoidal functor, then by
proposition 2.2, we have the result directly. ∎

##  4\. Producut category and Base

###  4.1. Product Category over Index set $\Lambda$

Let $\Lambda$ be an indexing set. Abusing the use of notation, we define an
indexing category, denoted by $\Lambda$, with objects as elements of the
indexing set $\Lambda$, and morphisms as

$\text{Hom}(\lambda_{1},\lambda_{2})=\begin{cases}\\{\text{Id}_{\lambda}\\}&\text{if
}\lambda_{1}=\lambda_{2}\\\ \emptyset&\text{otherwise}\end{cases}$

Composition is trivial, which will again be the identity map of the source
object. In particular, we will be considering finite sets as well as countably
infinite sets (like set of natural numbers) as a category wherever we talk of
a product category in the rest of the paper.

Let $\mathcal{B}$ be a monoidal category with a unit object $\mathbb{I}$. We
define the product $\Pi_{\Lambda}(\mathcal{B})$ of a category $\mathcal{B}$
over an indexing category $\Lambda$ as a collection of functors $\mathcal{F}$
from $\Lambda$ to $\mathcal{B}$ with $\mathcal{F}(\lambda)$ being an object in
$\mathcal{B}$, and
$\mathcal{F}(\text{Hom}(\lambda,\lambda))=\\{\text{Id}_{\mathcal{F}(\lambda)}\\}$.
The collection is non empty since $C$ (the constant functor) that maps every
object in $\Lambda$ to the identity $\mathbb{I}$ in $\mathcal{B}$ and
$\mathcal{C}(\text{Id}_{\lambda})$ is the identity map of the unit
$\mathbb{I}$ in $\mathcal{B}$ for $\lambda\in\Lambda$. The product category
$\mathcal{D}^{\prime}$ of $\mathcal{B}$ over an indexing set $\Lambda$ is
defined as follows:

  1. (1)

an object in $\mathcal{D}^{\prime}$ is a functor from $\Lambda\to\mathcal{B}$,

  2. (2)

a morphism between two objects $\mathcal{G},\mathcal{F}\in
Ob(\mathcal{D}^{\prime})$ is a natural transformation
$\eta:\mathcal{F}\to\mathcal{G}$ which gives a family of morphisms
$\eta_{\lambda}:\mathcal{F}(\lambda)\to\mathcal{G}(\lambda)$ in $\mathcal{B}$,

  3. (3)

composition of morphism is the vertical composition of two natural
transformations. That is, if $\eta\in Hom(\mathcal{F},\mathcal{G})$ and
$\zeta\in Hom(\mathcal{G},\mathcal{H})$ are two vertically composable natural
transformations, then the composition $\zeta\circ\eta$ is a natural
transformation between $\mathcal{F}$ and $\mathcal{H}$ given by
$\zeta\circ\eta(\lambda)=\zeta(\lambda)\circ\eta(\lambda)$ for every
$\lambda\in\Lambda.$

In particular, if the indexing set $\Lambda$ has only two elements, then as
expected, the product category $\mathcal{D}^{{}^{\prime}}$ of $\mathcal{B}$
over $\Lambda$ is isomorphic to $\mathcal{B}\times\mathcal{B}$.

######  Example 4.1.

Finite product. In case the indexing set is a finite set, then the product
category $\mathcal{D}^{{}^{\prime}}$ of any category $\mathcal{B}$ would be
finite copies of $\mathcal{B}$.

###  4.2. Base

Let $\mathcal{D}$ be a category. We define a base for $\mathcal{D}$ as the
data $(\mathcal{B},*,\mathcal{G})$, where $\mathcal{B}$ is a category, the
functor $*$ (we call as the pasting functor) from
$\mathcal{D}^{{}^{\prime}}\to\mathcal{D}$, and
$\mathcal{G}:\mathcal{D}\to\mathcal{D}^{{}^{\prime}}$, the decomposition
functor (here $\mathcal{D}^{{}^{\prime}}$ is the product category of
$\mathcal{B}$ over some indexing set, say $\Lambda$) such that
$*\mathcal{G}\cong\text{Id}_{\mathcal{D}}$. $\mathcal{B}$ in base, we call as
base category for $\mathcal{D}$. This is like asking for a representation of
every object of $\mathcal{D}$ in terms of objects in $\mathcal{B}$. Thus for
the same category $\mathcal{B}$ with different indexing sets in the product
category, might give different bases for $\mathcal{D}$.

######  Example 4.2.

Every category is a trivial base of itself. Simply take
$\mathcal{B}=\mathcal{D}$, $\Lambda=\\{1\\}$ with $\mathcal{G}$ and $*$ as
identity functors.

######  Example 4.3.

(continuation to example 3.3). Countable product of the category $\mathcal{A}$
of one dimensional compact oriented manifold without boundary over
$\Lambda=\\{1,2,\cdots\\}$ serves as a base for the category $\mathcal{D}$ of
oriented 2-dimensional cobordism classes, which have oriented cobordisms
between the objects of $\mathcal{A}$ but without holes only. As before, we
write an object of $\mathcal{D}$ as $(W,X,Y)$. The pasting functor
$*:\mathcal{D}^{{}^{\prime}}\to\mathcal{D}$ is defined such that
$*(\mathcal{H})$ is the cobordism between $\mathcal{H}(1)$ and
$\mathcal{H}(2)$ for any functor $\mathcal{H}$ in $\mathcal{D}^{{}^{\prime}}$.
The decomposition functor $\mathcal{G}$ picks an object in $\mathcal{D}$,
which is an oriented cobordism class , say $(W,X,Y)$ without holes, and maps
it to the functor : $1\mapsto X$, $2\mapsto Y$ and the rest of the elements of
the indexing category are mapped to the empty set. The combination of the two
functors is such that $*\mathcal{G}=\text{Id}_{\mathcal{D}}$. Note that the
pasting functor $*:\mathcal{D}^{{}^{\prime}}\to\mathcal{D}$ acts in a way that
its restriction onto two copies of $\mathcal{A}$ (that is, indexing category
with only two objects) becomes the same functor $\mathcal{F}$ as discussed in
example 3.3.

######  Proposition 4.4.

If the base $\mathcal{B}$ is a monoidal category then so is the product
category $\mathcal{D}^{\prime}=\Pi_{\Lambda}\mathcal{B}$.

###### Proof.

For defining a bifunctor (tensor product)
$\otimes^{\prime}:\mathcal{D}^{\prime}\times\mathcal{D}^{\prime}\to\mathcal{D}^{\prime}$
we have the following data: for any two objects (which are functors)
$\mathcal{F}$ and $\mathcal{G}$ in $\mathcal{D}^{{}^{\prime}}$,

  1. (1)

On level of objects: $\mathcal{F}\otimes^{\prime}\mathcal{G}$ is a functor
from $\Lambda\to\mathcal{B}$ defined as

    1. (a)

On object level

$\mathcal{F}\otimes^{\prime}\mathcal{G}(\lambda)=\mathcal{F}(\lambda)\otimes_{B}\mathcal{G}(\lambda)\quad\text{
for }\lambda\in\Lambda.$

    2. (b)

On the level of morphisms:

$\mathcal{F}\otimes^{\prime}\mathcal{G}(\text{Id}_{\lambda})=\mathcal{F}(\text{Id}_{\lambda})\otimes_{\mathcal{B}}\mathcal{G}(\text{Id}_{\lambda})=\text{Id}_{\mathcal{F}(\lambda)}\otimes_{\mathcal{B}}\text{Id}_{\mathcal{G}(\lambda)}=\text{Id}_{\mathcal{F}(\lambda)\otimes_{B}\mathcal{G}(\lambda)}$

  2. (2)

On the level of morphism: For $i=1,2$, if $\eta_{i}$ are two natural
transformations from $\mathcal{F}_{i}\to\mathcal{G}_{i}$, then
$\eta_{1}\otimes^{\prime}\eta_{2}:\mathcal{F}_{1}\otimes^{\prime}\mathcal{F}_{2}\to\mathcal{\mathcal{G}_{1}}\otimes^{\prime}\mathcal{\mathcal{G}_{2}}$
is a natural transformation which is given by the collection of morphisms

$\big{(}\eta_{1}\otimes^{\prime}\eta_{2}\big{)}_{\lambda}:\mathcal{F}_{1}(\lambda)\otimes_{B}\mathcal{F}_{2}(\lambda)\to\mathcal{G}_{1}(\lambda)\otimes_{B}\mathcal{G}_{2}(\lambda)$

where each of these morphisms are defined as
$(\eta_{1})_{\lambda}\otimes_{\mathcal{B}}(\eta_{2})_{\lambda}$ for each
$\lambda\in\Lambda$.

  3. (3)

Composition of morphisms: For two pair of composable transformations
$\begin{CD}\mathcal{F}_{1}@>{\eta_{1}}>{}>\mathcal{G}_{1}@>{\zeta_{1}}>{}>\mathcal{H}_{1}\end{CD}\text{
and
}\begin{CD}\mathcal{F}_{2}@>{\eta_{2}}>{}>\mathcal{G}_{2}@>{\zeta_{2}}>{}>\mathcal{H}_{2}\end{CD}$,
we want to show that their composition

$(\eta_{1}\otimes^{\prime}\eta_{2})\circ(\zeta_{1}\otimes^{\prime}\zeta_{2})=(\eta_{1}\circ\zeta_{1})\otimes^{\prime}(\eta_{2}\circ\zeta_{2})$

holds in $\mathcal{D}^{{}^{\prime}}$. This equation of natural transformation
is basically a collection of equations of morphisms in $\mathcal{B}$. Each
equation is true using the composition of morphisms in $\mathcal{B}$.

  4. (4)

Identity morphism:

$\text{Id}_{\mathcal{F}\otimes^{\prime}\mathcal{G}}=\text{Id}_{\mathcal{F}}\otimes^{\prime}Id_{\mathcal{G}}$

This is true using the monoidal structure of $\mathcal{B}$.

The associator $a^{{}^{\prime}}$, as well as the left and right unitors,
$\lambda^{{}^{\prime}}$ and $\rho^{{}^{\prime}}$, are all transformations with
the unit functor $I^{{}^{\prime}}$ in $\mathcal{D}^{{}^{\prime}}$, which on
objects is the collection $\\{\lambda\mapsto
I_{\mathcal{B}};\quad\forall\lambda\in\Lambda\\}$. They will satisfy the
triangle and pentagon axioms since they are true in $\mathcal{B}$. ∎

######  Remark 4.5.

We observe that $\mathcal{D}^{\prime}$ is symmetric if and only if
$\mathcal{B}$ is symmetric.

######  Theorem 4.6.

There exists a monoidal structure on a category $\mathcal{D}$ if it has a base
$(\mathcal{B},*,\mathcal{G})$ such that

  1. (1)

the base category $\mathcal{B}$ has monoidal structure and

  2. (2)

the pasting functor $*$ satisfies both the conditions of theorem 3.1.
Explicitly, for any pair of objects $\mathcal{H}_{1}$, $\mathcal{H}_{2}$ and
$\mathcal{H}_{3}$, $\mathcal{H}_{4}$ in $\mathcal{D}^{{}^{\prime}}$, such that
whenever we have

$*(\mathcal{H}_{1})=*(\mathcal{H}_{2})\text{ and
}*(\mathcal{H}_{3})=*(\mathcal{H}_{4})$

then

$*(\mathcal{H}_{1}\otimes\mathcal{H}_{3})=\mathcal{F}(\mathcal{H}_{2}\otimes\mathcal{H}_{4})$

And, a similar condition on morphisms. That is, for any pair
$\eta,\eta^{{}^{\prime}}$ and $\zeta,\zeta^{{}^{\prime}}$ of morphisms in
$\mathcal{D}^{{}^{\prime}}$, such that

$*(\eta)=*(\eta^{\prime})\text{ and }*(\zeta)=*(\zeta^{\prime})$

then, we must have

$*(\eta\otimes\zeta)=*(\eta^{{}^{\prime}}\otimes\zeta^{{}^{\prime}}).$

Moreover if $\mathcal{B}$ is symmetric then with induced monoidal structure
$\mathcal{D}$ will be symmetric.

###### Proof.

A monoidal structure on $\mathcal{D}$ consists of a tensor functor along with
an identity object, associativity and a pair of left and right unitors in
$\mathcal{D}$. We now give all these structures in $\mathcal{D}$ one by one.
The tensor functor $\otimes_{\mathcal{G}}$ on $\mathcal{D}$ is defined as the
composition of functors
$*\otimes^{{}^{\prime}}(\mathcal{G}\times\mathcal{G})$. Explicitly, on any
pair of objects $X$ and $Y$, and any pair of morphisms $f:X_{1}\to Y_{1}$ and
$g:X_{2}\to Y_{2}$ in $\mathcal{D}$, the tensor is defined as:

$X\otimes_{\mathcal{G}}Y=*\Big{(}\mathcal{G}(X)\otimes^{{}^{\prime}}\mathcal{G}(Y)\Big{)},\text{
and}$
$f\otimes_{\mathcal{G}}g=*\Big{(}\mathcal{G}(f)\otimes^{{}^{\prime}}\mathcal{G}(g)\Big{)}$

where $\otimes^{{}^{\prime}}$ is the tensor on $\mathcal{D}^{{}^{\prime}}$.
Since the tensor $\otimes_{\mathcal{G}}$ is dependent on the tensor of
$\mathcal{B}$ and hence on the tensor $\otimes^{{}^{\prime}}$ of
$\mathcal{D}^{{}^{\prime}}$, the associativity $(a_{\mathcal{G}})$, the unit
object (IG), the left unitor $(\lambda\mathcal{G})$ and the right unitor
$(\rho_{\mathcal{G}})$ are defined in the obvious way as $*(a^{{}^{\prime}})$,
*(I${}^{{}^{\prime}}$), $*(\lambda^{{}^{\prime}})$ and $*(\rho^{{}^{\prime}})$
respectively. These morphisms are isomorphisms as isomorphisms are preserved
under the action of functor $*$, and hence they will satisfy the pentagon and
triangle axioms.

If $\mathcal{B}$ is symmetric then $\mathcal{D}^{\prime}$ is symmetric, as we
have a functor $*\mathcal{D}^{\prime}\to\mathcal{D}$, therefore symmetric
structure of $\mathcal{D}^{\prime}$ is carried to $\mathcal{D}$ by the
functor. ∎

In particular, suppose $\mathcal{B}$ is a subcategory of a category
$\mathcal{D}$ such that we have the same setup as in above theorem. That is,
$\mathcal{B}$ has a monoidal structure $\otimes$ along with two functors $*$
and $\mathcal{G}$ as defined above, then $(\mathcal{B},\otimes)$ will be a
monoidal subcategory of $(\mathcal{D},\otimes_{\mathcal{G}})$.

######  Definition 4.7.

Let $(\mathcal{B},*,\mathcal{G})$ be a base for a category $\mathcal{D}$ such
that $\mathcal{B}$ has a monoidal structure. Then the monoidal structure on
$\mathcal{D}$ coming from the base satisfying the two conditions of above
theorem is denoted by $\otimes_{\mathcal{G}}$, and we call this monoidal
structure on $\mathcal{D}$ as induced tensor on $\mathcal{D}$ from the base
$\mathcal{B}$. In this case, we call base as monoidal base.

######  Example 4.8.

Let $\mathcal{B}$ be the category of finite dimensional vector spaces over
$\mathbb{R}$ with usual tensor product $\otimes_{\mathbb{R}}$ of vector spaces
(-ie- $\otimes_{\mathcal{B}}=\otimes_{\mathbb{R}}$). By example 4.3, taking
$\mathcal{D}=\mathcal{B}$ we can think of $\mathcal{B}$ as a base of itself
with $\Lambda=\\{1\\}$, and the functors $\mathcal{G}$ and $*$ as the identity
functor. We see that $\otimes_{\mathcal{G}}=\otimes_{\mathcal{B}}$.

######  Example 4.9.

(continuation to examples 3.3, 4.3) In example 4.3, we have shown that the
category $\mathcal{A}$ of one dimensional compact oriented manifold without
boundary together with indexing category $\Lambda=\\{1,2,\cdots\\}$ serves as
a base for the category $\mathcal{D}$ of oriented 2-dimensional cobordism
classes between objects of $\mathcal{A}$ (without holes). Now, in particular
let us choose the indexing category $\Lambda$ to be of two objects only (that
is, $\mathcal{D}^{{}^{\prime}}=\mathcal{A}\times\mathcal{A}).$

In example 3.3, we have discussed a monoidal structure on $\mathcal{A}$ and
also shown that the functor
$\mathcal{F}:\mathcal{A}\times\mathcal{A}\to\mathcal{D}$ satisfies the two
conditions asked in the theorem (4.8) above. Think of $\mathcal{F}$ playing
the role of the required $*$ functor for the monoidal base. Thus by the above
theorem, there is an induced tensor from the monoidal base $\mathcal{A}$ onto
$\mathcal{D}$. Explicitly, for any two objects $(W_{1},X_{1},Y_{1})$ and
$(W_{2},X_{2},Y_{2})$ in $\mathcal{D}$ we have

$(W_{1},X_{1},Y_{1})\otimes_{\mathcal{F}}(W_{2},X_{2},Y_{2})=(W,X_{1}\sqcup
X_{2},Y_{1}\sqcup Y_{2})$

where $W$ is a cobordism between $X_{1}\sqcup X_{2}$ and $Y_{1}\sqcup Y_{2}$
without any holes; For any two morphisms, say,
$\Big{(}(W_{1},X_{1},Y_{1}),(W_{2},X_{2},Y_{2})\Big{)}$ and
$\Big{(}(W_{3},X_{3},Y_{3}),(W_{4},X_{4},Y_{4})\Big{)}$ in $\mathcal{D}$ we
have

$\Big{(}(W_{1},X_{1},Y_{1}),(W_{2},X_{2},Y_{2})\Big{)}\otimes_{\mathcal{F}}\Big{(}(W_{3},X_{3},Y_{3}),(W_{4},X_{4},Y_{4})\Big{)}=$
$\Big{(}(W_{1}\sqcup W_{3},X_{1}\sqcup X_{3},Y_{1}\sqcup Y_{3}),(W_{2}\sqcup
W_{4},X_{2}\sqcup X_{4},Y_{2}\sqcup Y_{4}\Big{)}.$

Note that the unit object under the induced tensor will be the oriented
2-dimensional class of a sphere (cobordism between empty set to itself without
holes!)

######  Proposition 4.10.

$\mathcal{B}$ is dualizable if and only if $\mathcal{D}^{\prime}$ is
dualizable.

###### Proof.

Firstly, let us assume that $\mathcal{B}$ is dualizable. That means every
object has a dual in $\mathcal{B}$. Let $\mathcal{F}:\Lambda\to\mathcal{B}$ be
an object in $\mathcal{D}^{\prime}$. We define a functor
$\mathcal{F}^{*}:\Lambda\to\mathcal{B}$ such that

  1. (1)

For any $\lambda\in\Lambda$, we have
$\mathcal{F}^{*}(\lambda):=\mathcal{F}(\lambda)^{*}$, here
$\mathcal{F}(\lambda)^{*}$ is the dual of $\mathcal{F}(\lambda)$ in
$\mathcal{B}$.

  2. (2)

$\mathcal{F}(\text{Id}_{\lambda})=\text{Id}_{\mathcal{F}(\lambda)^{*}}$

Clearly $\mathcal{F}^{*}\in Ob(\mathcal{D}^{\prime})$. We claim that
$\mathcal{F}^{*}$ is the dual of $\mathcal{F}$ in the category
$\mathcal{D}^{\prime}$ with monoidal structure as in proposition 4.4.

We have natrual transformations
$ev:\mathcal{F}\otimes^{\prime}\mathcal{F}^{*}\to\mathbb{I}_{\mathcal{D}}^{\prime}$,
defined by

$ev_{\lambda}:\mathcal{F}(\lambda)\otimes_{\mathcal{B}}\mathcal{F}(\lambda)^{*}\to\mathbb{I}_{\mathcal{B}}.$

Here $ev_{\lambda}$ is the evaluation map in the monoidal category
$\mathcal{B}$ for $\mathcal{F}(\lambda)$ and $\mathcal{F}(\lambda)^{*}$.

Similiary, we have coevaluation map in the category $\mathcal{D}^{\prime}$,
given by natural transformation,
$coev:\mathbb{I}_{\mathcal{D}}\to\mathcal{F}\otimes^{\prime}\mathcal{F}^{*}$,
it is defined by coevaluation map $coev_{\lambda}$ in the monoidal category
$\mathcal{B}$ for $\mathcal{F}(\lambda)$ and $\mathcal{F}^{*}(\lambda)$.

$coev_{\lambda}:\mathbb{I}_{B}\to\mathcal{F}(\lambda)\otimes_{B}\mathcal{F}^{*}(\lambda).$

As for each $\lambda$, $\mathcal{F}(\lambda)$ is dual of
$\mathcal{F}^{*}(\lambda)$, we have

$\begin{CD}\mathcal{F}(\lambda)@>{l^{-1}_{\mathcal{F}(\lambda)}}>{}>\mathbb{I}_{\mathcal{B}}\otimes_{\mathcal{B}}\mathcal{F}(\lambda)@>{coev_{\lambda}\otimes_{\mathcal{B}}\text{Id}_{\mathcal{F}}(\lambda)}>{}>(\mathcal{F}(\lambda)\otimes_{\mathcal{B}}\mathcal{F}^{*}(\lambda))\otimes_{\mathcal{B}}\mathcal{F}(\lambda)@>{a_{\mathcal{F}(\lambda),\mathcal{F}^{*}(\lambda),\mathcal{F}(\lambda)}}>{}>\end{CD}$
$\begin{CD}\mathcal{F}(\lambda)\otimes_{\mathcal{B}}(\mathcal{F}^{*}(\lambda)\otimes_{\mathcal{B}}\mathcal{F}(\lambda))@>{\text{Id}_{\mathcal{F}}(\lambda)\otimes_{\mathcal{B}}ev_{\lambda}}>{}>\mathcal{F}(\lambda)\otimes_{\mathcal{B}}\mathbb{I}_{\mathcal{B}}@>{r_{\mathcal{F}}(\lambda)}>{}>\mathcal{F}(\lambda)\end{CD}$

here $r$ and $l$ are right and left unitors in $\mathcal{B}$ and

$\begin{CD}\mathcal{F}^{*}(\lambda)@>{r^{-1}_{\mathcal{F}^{*}(\lambda)}}>{}>\mathbb{I}_{\mathcal{B}}\otimes_{\mathcal{B}}\mathcal{F}^{*}(\lambda)@>{\text{Id}_{\mathcal{F}^{*}(\lambda)}\otimes_{\mathcal{B}}coev_{\lambda}}>{}>\mathcal{F}^{*}(\lambda)\otimes_{\mathcal{B}}(\mathcal{F}(\lambda)\otimes\mathcal{F}^{*}(\lambda))@>{a^{-1}_{\mathcal{F}^{*}(\lambda),\mathcal{F}(\lambda),\mathcal{F}^{*}(\lambda)}}>{}>\end{CD}$

$\begin{CD}(\mathcal{F}^{*}(\lambda)\otimes_{\mathcal{B}}\mathcal{F}(\lambda))\otimes_{\mathcal{B}}\mathcal{F}^{*}(\lambda)@>{ev_{\lambda}\otimes_{\mathcal{B}}\text{Id}_{\mathcal{F}^{*}(\lambda)}}>{}>\mathbb{I}_{\mathcal{B}}\otimes\mathcal{F}^{*}(\lambda)@>{l_{\mathcal{F}^{*}(\lambda)}}>{}>\mathcal{F}^{*}(\lambda)\end{CD}$

are both identity, since $\mathcal{F}(\lambda)$ has left dual
$\mathcal{F}^{*}(\lambda)$. Similiary we can see that $\mathcal{F}(\lambda)$
has same right dual. This proves that we have $\mathcal{F}^{*}$ is the dual of
$\mathcal{F}$ in $(\mathcal{D}^{\prime},\otimes^{\prime})$.

Conversely, for a fix $\lambda\in\Lambda$, we define a functor
$EV_{\lambda}:\mathcal{D}^{\prime}\to\mathcal{B}$, such that for each object
$\mathcal{F}\in\mathcal{D}^{\prime}$, it associates to $\mathcal{F}(\lambda)$
in $\mathcal{B}$ and For each morphism $\eta:\mathcal{F}\to\mathcal{G}$, it
associates to $\eta_{\lambda}:\mathcal{F}(\lambda)\to\mathcal{G}(\lambda)$.
$EV_{\lambda}$ is a functor such that $\mathcal{B}=Im(EV_{\lambda})$, and by
the definition of monoidal structur on $\mathcal{D}^{\prime}$, we see that

$EV_{\lambda}(\mathcal{F})\otimes_{B}EV_{\lambda}(\mathcal{G})=EV_{\lambda}(\mathcal{F}\otimes^{\prime}\mathcal{G}).$

Therefore $EV_{\lambda}$ is strong lax symmetric monoidal functor. As a result
every object in $\mathcal{B}$ is dualizable, if $\mathcal{D}^{\prime}$ is
dualiable.

∎

######  Proposition 4.11.

$\mathcal{D}$ is dualizable if $\mathcal{D}^{\prime}$ is dualizable.

###### Proof.

Since the functor $*:\mathcal{D}^{\prime}\to\mathcal{D}$ is a strong lax
symmetric monoidal functor and $\mathcal{D}=*(\mathcal{D}^{\prime})$, it
proves the result. ∎

##  5\. example: Loop space

###  5.1. Loop space and lifting of maps

Let $V$ be a finite dimensional vector space over $\mathbb{R}$. By loop space
we mean set of all maps from $S^{1}$ to $V$, we denote this set by $LV$. With
usual function addition and scalar multiplication this is a vector space over
$\mathbb{R}$.

If $T:V_{1}\to V_{2}$ is a linear map from vector space $V_{1}$ to $V_{2}$, we
define a map

$\widetilde{T}:LV_{1}\to LV_{2}\quad\text{as:}$

(6) $\widetilde{T}(\gamma)(t):=T(\gamma(t)).$

We call $\widetilde{T}$ is the lifting of $T$. $\widetilde{T}$ is a linear map
from $LV_{1}\to LV_{2}$.

###  5.2. Categories $\mathcal{B}$ and $\mathcal{D}$

Category $\mathcal{B}$ is the category of finite dimensional vector spaces
over $\mathbb{R}$ and linear maps as morphisms. Category $\mathcal{D}$ is
defined by the following:

  1. (1)

Objects are $LV$ for all finite dimensional vector spaces $V$ over
$\mathbb{R}$.

  2. (2)

Morphisms $Hom(LV_{1},LV_{2}):=LHom(V_{1},V_{2})$. For $f:LV_{1}\to LV_{2}$
there is a unique linear map $T_{f}:V_{1}\to V_{2}$ such that

(7) $f(\gamma)(t):=\widetilde{T_{f}}(\gamma(t)).$

For $f\in Hom(LV_{1},LV_{2})$ and $g\in Hom(LV_{2},LV_{3})$ there exits
$T_{f}$ and $T_{g}$ and we have

$\widetilde{T_{g}}\circ\widetilde{T_{f}}=\widetilde{T_{g\circ f}}$

This means that $g\circ f\in Hom(LV_{1},LV_{3})$.

###  5.3. Monoidal structure on $\mathcal{D}$ from the theorem above

From the construction of categories, we have a natural choice of functor
$L:\mathcal{B}\to\mathcal{D}$ defined as:

$V\to LV;\;\;f\to\widetilde{f}$

where $\widetilde{f}$ is given by equation (6). Let
$\mathcal{G}:\mathcal{D}\to\mathcal{B}$ be a functor which associates each
object $LV$ to $\\{\gamma\in LV:\gamma\text{ is a constant loop}\\}$ and any
morphism $f:LV_{1}\to LV_{2}$ to $T_{f}:V_{1}\to V_{2}$ given by equation (7).

Taking $\Lambda=\\{1\\}$ so that the product category of $\mathcal{B}$ over
$\Lambda$ is $\mathcal{B}$ itself, then the data $(\mathcal{B},\mathcal{G},L)$
becomes a base for $\mathcal{D}$. Here $L$ works as $*$ functor in the
definition.

######  Proposition 5.1.

There is a monoidal structure on $\mathcal{D}$ induced from its base
$\mathcal{B}$.

###### Proof.

First we see that for vector spaces $V_{1},V_{2}$ such that $LV_{1}=LV_{2}$
and $W_{1},W_{2}$ such that $LW_{1}=LW_{2}$, we have

$L(V_{1}\otimes_{\mathcal{B}}W_{1})=L(V_{2}\otimes_{\mathcal{B}}W_{2}).$

Also for any morphisms $\eta,\eta^{\prime},\zeta,\zeta^{\prime}$, if
$L(\eta)=L(\eta^{\prime})$ and $L(\zeta)=L(\zeta^{\prime})$, we have

$L(\eta\otimes_{\mathcal{B}}\zeta)=L(\eta^{\prime}\otimes_{\mathcal{B}}\zeta^{\prime})$

Therefore $(\mathcal{B},\mathcal{G},L)$ satisfies all the condition of theorem
4.6. Thus, we have monoidal structure on $\mathcal{D}$ defined as

$LV_{1}\otimes_{\mathcal{G}}LV_{2}:=L(V_{1}\otimes V_{2})$
$\eta\otimes_{\mathcal{G}}\zeta:=\widetilde{T_{\eta}\otimes_{\mathcal{B}}T_{\zeta}}$

∎

With this induced monoidal structure on $LV$, it is obvious to see that the
functor $L$ and $\mathcal{G}$ are strong lax symmetric monoidal functors. And
as a result of above remark, every object in the category $\mathcal{D}$ of
loop space is dualizable. Explicit calculation of the above observations is
given in the following subsection.

###  5.4. Explicit calculation for above results in the case of loop space.

$L\mathbb{R}\otimes LV=L(\mathbb{R}\otimes V)\simeq L(V).$

Therefore $L\mathbb{R}$ is the identity element in this monoidal category
$\mathcal{D}$. If $V$ is of $n$ dimensional vector space over $\mathbb{R}$ and
if $V^{*}$ is the dual of $V$ in original sense, then we have a map

$ev:V\otimes V^{*}\to\mathbb{R}$

defined by

$ev\left(\sum_{i=1,j=1}^{n}a_{ij}e_{i}\otimes
e_{j}^{*}\right)=\sum_{i=1}^{n}a_{ii}$

We also have the coevaluation map.

$coev:\mathbb{R}\to V\otimes V^{*}$ $coev(1)=\sum_{i=1}^{n}e_{i}\otimes
e_{i}^{*}$

Let $\widetilde{ev}$ and $\widetilde{coev}$ be the lifting of $ev$ and $coev$
respectively, then we have

$\widetilde{ev}:LV\otimes LV^{*}(=L(V\times V^{*})\to L\mathbb{R}$

by

$\left(t\to\gamma(t)=\sum_{i=1,j=1}^{n}a_{ij}(t)e_{i}\otimes
e_{j}^{*}\right)\to\left(t\to\sum_{i=1}^{n}a_{ii}(t)\right)$

and

$\widetilde{coev}:L\mathbb{R}\to LV\otimes LV^{*}:=L(V\times V^{*})$

by

$\left(t\to\gamma(t)\right)\to\left(t\to\gamma(t)\sum e_{i}\otimes
e_{i}^{*}\right)$

Now we will write left and right unitor.

$\widetilde{\lambda_{V}}:L\mathbb{R}\otimes LV:=L(\mathbb{R}\otimes V)\to LV$
$\widetilde{\lambda_{V}}\left(t\to\sum a_{i}(t)e_{i}\right)=\left(t\to\sum
a_{i}(t)e_{i}\right)$

Also we have

$\widetilde{\lambda_{V}}^{-1}:LV\to L\mathbb{R}\otimes LV$

by

$\widetilde{\lambda_{V}}^{-1}\left(t\to\sum
a_{i}(t)e_{i}\right)=\left(t\to\sum 1\otimes a_{i}(t)e_{i}\right)$

The map $\widetilde{\lambda_{V}}$ and inverse are the lift of the map
$\lambda_{V}:\mathbb{R}\otimes V\to V$ and
$\lambda_{V}^{-1}:V\to\mathbb{R}\otimes V$.

Similar way we have maps

$\rho_{V}:V\otimes\mathbb{R}\to V$ $\rho_{V}(\sum a_{i}e_{i}\otimes v)=\sum
ba_{i}e_{i}$

If we lift this map to the loop space, we have corresponding map.

$\widetilde{\rho}_{V}:=LV\otimes L\mathbb{R}:=L(V\otimes\mathbb{R})\to LV$

given by

$\widetilde{\rho_{V}}\left(t\to\gamma(t)=\sum a_{i}(t)e_{i}\otimes
b(t)\right):=\left(t\to\sum b(t)a_{i}(t)e_{i}\right)$

Also if we lift $\rho_{V}^{-1}$ we have

$\widetilde{\rho_{V}}^{-1}\left(t\to\sum a_{i}(t)e_{i}\right):=\left(t\to\sum
a_{i}(t)e_{i}\otimes 1\right)$

Now we will calculate the map

$\widetilde{coev}\otimes\text{Id}_{LV}:L\mathbb{R}\otimes LV\to L(V\otimes
V^{*})\otimes LV$

Let $\gamma\in L\mathbb{R}\otimes LV:=L(\mathbb{R}\otimes V)$, we can write

$\gamma(t)=\gamma_{1}(t)\otimes\gamma_{2}(t)=b(t)\otimes\sum a_{i}(t)e_{i}$

In general, for each $\gamma\in L\mathbb{R}\otimes LV$, there exists
$\gamma_{1}$ and $\gamma_{2}$ such that
$\gamma(t)=\gamma_{1}(t)\otimes\gamma_{2}(t)$. Obviously, $\gamma_{1}\in
L\mathbb{R}$ and $\gamma_{2}\in LV$.

We denote
$\gamma_{1}\otimes\gamma_{2}:=\left(t\to\gamma_{1}(t)\otimes\gamma_{2}(t)\right)$

With this notation we have a symmetric structure $\widetilde{s}$ in
$\mathcal{D}$ given as

$\widetilde{s}:LV_{1}\otimes LV_{2}\to LV_{2}\otimes LV_{1}$
$\widetilde{s}(\gamma_{1}\otimes\gamma_{2})=\gamma_{2}\otimes\gamma_{1}$

####  5.4.1. Braiding and Trace

A braiding for a monoidal category consists of a family of isomorphisms

$C_{X,Y}:X\otimes Y\to Y\otimes X,\text{ for }X,Y\text{ in }\mathcal{C}$

natural in $X$ and $Y$, such that the two Hexadonal identities are satisfied.
A monoidal category together with a braiding is called a braided monoidal
category.

Let $X$ be a dualizable object in a braided monoidal category $\mathcal{C}$,
and that $f:X\to X$ is an endomorphism of $X$. The $\textit{trace}tr_{X}(f)\in
End(\mathbb{I})$ is the composite

$\begin{CD}\mathbb{I}@>{coev_{X}}>{}>X\otimes
X^{*}@>{C_{X,X^{*}}}>{}>X^{*}\otimes X@>{\text{Id}_{X^{*}}\otimes
f}>{}>X^{*}\otimes X@>{ev_{X}}>{}>\mathbb{I}\end{CD}$

We know that category of finite dimensional vector spaces over $\mathbb{R}$
with usual tensor product is a braided monoidal category. From the braiding
(family of isomorphism) if we lift all the isomorphism to the loop space level
(by tilde map discussed in section 5.1), we can easily see that $\mathcal{D}$
with induced monoidal structure is braided. So we have the following.

######  Proposition 5.2.

Category $(\mathcal{B},\otimes_{\mathcal{B}})$ and $(\mathcal{D},\otimes_{G})$
are braided monoidal category.

Lets see the map

$L\mathbb{R}\xrightarrow{\widetilde{coev}}LV\otimes
LV^{*}\xrightarrow{Id\otimes Id}LV\otimes
LV^{*}\xrightarrow{\widetilde{s}}LV^{*}\otimes
LV\xrightarrow{\widetilde{ev}}L\mathbb{R}$

$\left(t\to\gamma(t)\sum e_{i}\otimes
e_{i}^{*}\right)=\left(t\to\sum\gamma(t)e_{i}\otimes e_{i}^{*}\right)$
$\to\left(t\to\gamma(t).n\right)=n\gamma$

This proves that $tr_{LV}(\text{Id})=n=\text{ dimensional of vector space}$.
For each object in the category we get a unique number that is the dimensional
of vector space. This is because of the way we define the monoidal structure
on $\mathcal{D}$.

## References

  * [1] A.M. Cegarra, A.R. Garz̀on, J.A. Ortega, Graded extensions of monoidal categories, J. Algebra 241 (2001), no. 2, 620–657.
  * [2] Christian Kassel, Quantum Groups, Graduate texts in mathematics; vol I. 155, DOI 10.1007/978–1–4612–0783–2.
  * [3] Joachim Kock, Frobenius Algebras and 2D Topological Quantum Field Theories, Cambridge University Press 2003, ISBN 978–O–521–54031–O.
  * [4] Ponto Kate, Shulman Michael, Traces in symmetric monoidal categories, Expo. Math. 32 (2014), no. 3, 248–273.
  * [5] Brian Day, Craig Pastro, Note on Frobenius monoidal functors, New York J. Math. 14 (2008) 733–742. MR2465800 (2009k:18001).
  * [6] Mac Lane, Saunders (1998), Categories for the Working Mathematician (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978–0–387–98403–2, p. 123, section V.7.
  * [7] Imrich, Wilfried, Klavzar, Sandi, Product Graphs: Structure and Recognition, Wiley (2000), ISBN 0–471–37039–8.


then $Z_{1},\dotsc,Z_{t}$ are independent and identically distributed random
vectors with mean $(\mu_{1}-\mu_{2})/\sqrt{2}$ and covariance matrix $I_{p}$
and satisfy
$\mathbb{E}\bigl{|}Z_{i}(j)-\frac{\mu_{1}(j)-\mu_{2}(j)}{\sqrt{2}}\bigr{|}^{\alpha}\leq
2^{\alpha/2}K$ for $i\in[t],j\in[p]$. Recall that
$\tilde{t}\|\mu_{1}-\mu_{2}\|^{2}_{2}\geq\rho^{2}/2$. Hence, when
$\rho^{2}\geq
24C_{2}\bigl{(}s\log(ep/s)+\log(16\log(2n)/\varepsilon)\bigr{)}$, we have by 1
that

$\displaystyle\mathbb{E}_{\theta}(1-\phi_{\mathcal{P},\mathrm{sparse}}^{\mathrm{RSM}})=\mathbb{P}_{\theta}(A^{\mathrm{RSM}}_{\tilde{t},a}\leq
r^{\mathrm{RSM}}_{\tilde{t}})=\mathbb{P}_{\theta}\Bigl{(}\tilde{t}\bigl{\|}\hat{\mu}_{\tilde{t},s,\eta_{\tilde{t}}}^{\mathrm{RSM}}\bigr{\|}^{2}_{2}\leq
2C_{2}\bigl{(}s\log(ep/s)+\log(1/\eta_{\tilde{t}})\bigr{)}\Bigr{)}$
$\displaystyle\leq\mathbb{P}_{\theta}\biggl{(}\sqrt{\tilde{t}}\biggl{|}\Bigl{\|}\frac{\mu_{1}-\mu_{2}}{\sqrt{2}}\Bigr{\|}_{2}-\Bigl{\|}\hat{\mu}_{\tilde{t},s,\eta_{\tilde{t}}}^{\mathrm{RSM}}-\frac{\mu_{1}-\mu_{2}}{\sqrt{2}}\Bigr{\|}_{2}\biggr{|}\leq\sqrt{2C_{2}}\bigl{(}\sqrt{s\log(ep/s)}+\sqrt{\log(1/\eta_{\tilde{t}})}\bigr{)}\biggr{)}$
$\displaystyle\leq\mathbb{P}_{\theta}\biggl{(}\sqrt{\tilde{t}}\Bigl{\|}\hat{\mu}_{\tilde{t},s,\eta_{\tilde{t}}}^{\mathrm{RSM}}-\frac{\mu_{1}-\mu_{2}}{\sqrt{2}}\Bigr{\|}_{2}>\sqrt{C_{2}}\bigl{(}\sqrt{s\log(ep/s)}+\sqrt{\log(1/\eta_{\tilde{t}})}\bigr{)}\biggr{)}\leq\eta_{\tilde{t}}$
$\displaystyle\leq\exp\biggl{\\{}s\log(ep/s)-\frac{\min(t,\tilde{\Delta}_{2})}{C_{1}}\biggr{\\}}\leq\frac{\varepsilon}{16},$

as desired.

####  A.1.6 Proof of Theorem 9

We first consider the statistical property of
$\phi_{\mathcal{P},\mathrm{sparse}}$. By comparing the two rates
$v^{\mathrm{U,MoM}}_{\mathcal{P},\mathrm{sparse}}$ and
$v^{\mathrm{U}}_{\mathcal{P},\mathrm{sparse}}$, we note that the improvement
offered by $\phi_{\mathcal{P},\mathrm{sparse}}^{\mathrm{RSM}}$ over
$\phi_{\mathcal{P},\mathrm{sparse}}^{\mathrm{MoM}}$ only exists when

$(p/s)^{2/\alpha}\leq\log\log(8n),$

since otherwise
$v^{\mathrm{U,MoM}}_{\mathcal{P},\mathrm{sparse}}=v^{\mathrm{U}}_{\mathcal{P},\mathrm{sparse}}$.
Combining this with the fact that we are in the sparse regime $s\leq
p^{(\alpha-4)/(2\alpha-4)}$, we deduce that $p\leq\log^{\alpha-2}(\log(8n))$.
The desired result is then an immediate consequence of 7 and 8.

Now onto the computational complexity claim. For each $t\in\mathcal{T}$,
computing the statistics $A^{\mathrm{MoM}}_{t,a}$ and $A_{t,a}$ in
$\phi_{\mathcal{P},\mathrm{sparse}}^{\mathrm{MoM}}$ and
$\phi_{\mathcal{P},\mathrm{sparse}}^{\mathrm{RSM}}$ take time polynomial in
$n$ and $p$ since they only involve performing basic operations and finding
the median of $G_{t}\leq 8\log\log(8n)$ quantities. The computationally
demanding part lies in computing $A^{\mathrm{RSM}}_{t}$, or equivalently the
robust sparse mean estimator $\hat{\mu}^{\mathrm{RSM}}_{t,s,\eta_{t}}$. Note
that we are using this only when $p\leq\log^{\alpha-2}(\log(8n))$. For each
fixed $t$, we claim that the computation/approximation of
$\hat{\mu}^{\mathrm{RSM}}_{t,s,\eta_{t}}$ can be performed in time that is
polynomial in $n$. We now show this by arguing that each component below has
time complexity that is polynomial in $n$. In the rest of the proof, we omit
the subscripts and adopt the notation $\hat{\mu}^{\mathrm{RSM}}$ for clarity.

  1. 1.

Each evaluation of the function $\mathrm{1DRobust}(\cdot)$ (c.f. Prasad et
al., 2019, Algorithm 2) of $t$ data point requires time of order $t\log t\leq
n\log n$ (in order to find the shortest interval).

  2. 2.

The total number of projection $|\mathcal{N}^{1/2}_{2s}(\mathcal{S}^{p-1})|$
can be bounded by
$|\mathcal{N}^{1/2}_{2s}(\mathcal{S}^{p-1})|\leq(6ep/s)^{s}\leq(6ep)^{p}\leq\exp(6ep^{2})\leq\exp(C_{\alpha}\log(n))=n^{C_{\alpha}}$
for some constant $C_{\alpha}>0$, depending only on $\alpha$. Denote

$g(\mu):=\max_{u\in\mathcal{N}^{1/2}_{2s}(\mathcal{S}^{p-1})}|u^{\top}\mu-\mathrm{1DRobust}(\\{u^{\top}Z_{i}\\}_{i=1}^{t},\eta_{t}/(6ep/s)^{s})|.$

Thus for a fixed $\mu\in\mathbb{R}^{p}$, the computational complexity of
evaluating $g(\mu)$ is polynomial in $n$.

  3. 3.

The optimisation problem defining $\hat{\mu}^{\mathrm{RSM}}$ can be written as

$\min_{\mu\in\mathcal{L}_{s}}g(\mu).$

We solve this by first considering each possible $s$-sparsity coordinate
pattern individually before working out the minimum among these
$\binom{p}{s}\leq n^{C_{\alpha}}$ minima.

  4. 4.

Fix $\mathcal{U}\subseteq\mathbb{R}^{p}$ with $|\mathcal{U}|=s$. We solve the
optimisation problem

$\min_{\mu\in\mathbb{R}:\mu(j)=0\,\forall j\in\mathcal{U}^{c}}g(\mu)$

by subgradient descent. Denote the optimal value to be $g_{*,\mathcal{U}}$ and
the $k$-th iterate to be $\mu_{\mathcal{U}}^{(k)}$. Note that $g(\mu)$ is
$1$-Lipschitz and $\partial g(\mu)\subseteq\bigl{\\{}\pm
u:u\in\mathcal{N}^{1/2}_{2s}(\mathcal{S}^{p-1})\bigr{\\}}$. Standard result on
the convergence of subgradient descent (e.g. Nesterov, 2003, Theorem 3.2.2)
shows that
$\bigl{(}\min_{k\in[K]}g\bigl{(}\mu_{\mathcal{U}}^{(k)}\bigr{)}\bigr{)}-g_{*,\mathcal{U}}\leq\epsilon$
in $K\asymp 1/\epsilon^{2}$ steps, where we choose
$\epsilon=\sqrt{s\log(ep/s)t^{-1}}$. The computational complexity is again at
most polynomial in $n$. Denote $\tilde{\mu}^{\mathrm{RSM}}_{\mathcal{U}}$ to
be the update that attains the best objective value in $K$ iterations.

Write

$\tilde{\mu}^{\mathrm{RSM}}:=\operatorname*{argmin}_{\mu\in\bigl{\\{}\tilde{\mu}^{\mathrm{RSM}}_{\mathcal{U}}:\,|\mathcal{U}|=s\bigr{\\}}}g(\mu),$

as our final estimator (an approximation of $\hat{\mu}^{\mathrm{RSM}}$). We
have now shown that $\tilde{\mu}^{\mathrm{RSM}}$ can be obtained in time that
is polynomial in $n$. Finally, we prove that $\tilde{\mu}^{\mathrm{RSM}}$
still satisfies Condition 1. Indeed, following the proof of Lemma 4 and
Corollary 12 in Prasad et al. (2019), we have

$\displaystyle\|\tilde{\mu}^{\mathrm{RSM}}-\mu_{Z}\|_{2}$
$\displaystyle\leq\|\tilde{\mu}^{\mathrm{RSM}}-\hat{\mu}^{\mathrm{RSM}}\|_{2}+\|\hat{\mu}^{\mathrm{RSM}}-\mu_{Z}\|_{2}\leq
g\bigl{(}\tilde{\mu}^{\mathrm{RSM}}\bigr{)}+g\bigl{(}\hat{\mu}^{\mathrm{RSM}}\bigr{)}+g\bigl{(}\hat{\mu}^{\mathrm{RSM}}\bigr{)}+g(\mu_{Z})$
$\displaystyle\leq
g\bigl{(}\hat{\mu}^{\mathrm{RSM}}\bigr{)}+\epsilon+2g\bigl{(}\hat{\mu}^{\mathrm{RSM}}\bigr{)}+g(\mu_{Z})\leq\varepsilon+4g(\mu_{Z})$
$\displaystyle\leq\sqrt{C}\biggl{(}\sqrt{\frac{s\log(ep/s)}{t}}+\sqrt{\frac{\log(1/\eta_{t})}{t}}\biggr{)},$

for some $C\geq 1$, where $\mu_{Z}=\mathbb{E}Z_{1}$.

###  A.2 Proof of the adaptation result in Section 4

###### Proof of Theorem 11.

This proof is based on the proofs of Theorem 5, Propositions 7, 8. For
brevity, we only highlight the main steps and differences.

Null term. By a union bound, (55) and (A.1.5), we have

$\displaystyle\mathbb{E}_{\theta}\phi_{\mathcal{P},\mathrm{adaptive}}$
$\displaystyle\leq\mathbb{E}_{\theta}\phi_{\mathcal{P},\mathrm{dense}}+\mathbb{E}_{\theta}\biggl{[}\max_{s\in\mathcal{K}}\phi_{\mathcal{P},\mathrm{sparse},s}^{\mathrm{MoM}}\biggr{]}\mathbbm{1}_{\\{p>\log^{\alpha-2}(\log(8n))\\}}+\mathbb{E}_{\theta}\biggl{[}\max_{s\in\mathcal{K}}\phi_{\mathcal{P},\mathrm{sparse},s}^{\mathrm{RSM}}\biggr{]}\mathbbm{1}_{\\{p\leq\log^{\alpha-2}(\log(8n))\\}}$
$\displaystyle\leq\mathbb{E}_{\theta}\phi_{\mathcal{P},\mathrm{dense}}+\Biggl{(}\mathbb{P}_{\theta}\biggl{(}\max_{s\in\mathcal{K}}\frac{A_{1,a_{s},s}}{r_{1,s}}>1\biggr{)}+\sum_{s\in\mathcal{K}}\sum_{t\in\mathcal{T}\backslash\\{1\\}}\mathbb{P}_{\theta}\bigl{(}A_{t,a_{s},s}^{\mathrm{MoM}}>r_{t,s}\bigr{)}\Biggr{)}\mathbbm{1}_{\\{p>\log^{\alpha-2}(\log(8n))\\}}$
$\displaystyle\quad+\Biggl{(}\mathbb{P}_{\theta}\biggl{(}\max_{s\in\mathcal{K}}\frac{A_{1,a_{s},s}}{\tilde{r}_{1,s}}>1\biggr{)}+\sum_{s\in\mathcal{K}}\sum_{t\in\tilde{\mathcal{T}}_{1,s}\backslash\\{1\\}}\mathbb{P}_{\theta}(A_{t,a_{s},s}>\tilde{r}_{t,s})$
$\displaystyle\qquad\qquad+\sum_{s\in\mathcal{K}}\sum_{t\in\tilde{\mathcal{T}}_{2,s}}\mathbb{P}_{\theta}(A^{\mathrm{RSM}}_{t,s}>r^{\mathrm{RSM}}_{t,s})+\sum_{s\in\mathcal{K}}\sum_{t\in\tilde{\mathcal{T}}_{3,s}}\mathbb{P}_{\theta}(A^{\mathrm{RSM}}_{t,s}>r^{\mathrm{RSM}}_{t,s})\Biggr{)}\mathbbm{1}_{\\{p\leq\log^{\alpha-2}(\log(8n))\\}}$
$\displaystyle\leq\mathbb{E}_{\theta}\phi_{\mathcal{P},\mathrm{dense}}+\mathbb{P}_{\theta}\biggl{(}\max_{s\in\mathcal{K}}\frac{A_{1,a_{s},s}}{r_{1,s}\wedge\tilde{r}_{1,s}}>1\biggr{)}+\sum_{s\in\mathcal{K}}\sum_{t\in\mathcal{T}\backslash\\{1\\}}\mathbb{P}_{\theta}\bigl{(}A_{t,a_{s},s}^{\mathrm{MoM}}>r_{t,s}\bigr{)}$
$\displaystyle\quad+\sum_{s\in\mathcal{K}}\sum_{t\in\tilde{\mathcal{T}}_{1,s}\backslash\\{1\\}}\mathbb{P}_{\theta}(A_{t,a_{s},s}>\tilde{r}_{t,s})+\sum_{s\in\mathcal{K}}\Biggl{(}\sum_{t\in\tilde{\mathcal{T}}_{2,s}}\mathbb{P}_{\theta}(A^{\mathrm{RSM}}_{t,s}>r^{\mathrm{RSM}}_{t,s})+\sum_{t\in\tilde{\mathcal{T}}_{3,s}}\mathbb{P}_{\theta}(A^{\mathrm{RSM}}_{t,s}>r^{\mathrm{RSM}}_{t,s})\Biggr{)},$
(64)

where we denote
$\tilde{\mathcal{T}}_{1,s}:=\\{t\in\mathcal{T}:t\leq\tilde{\Delta}_{1,s}\\}$,
$\tilde{\mathcal{T}}_{2,s}:=\\{t\in\mathcal{T}:\tilde{\Delta}_{1,s}<t\leq\tilde{\Delta}_{2,s}\\}$
and $\tilde{\mathcal{T}}_{3,s}:=\\{t\in\mathcal{T}:t>\tilde{\Delta}_{2,s}\\}$.
In the following, we bound each of the five terms in (A.2) by
$\varepsilon/10$.
Term 1. By closely following the null term part of the proof of Theorem 5,
with a sufficiently large constant $C_{1}$, we deduce, similar to (A.1.3),
that

$\displaystyle\mathbb{E}_{\theta}\phi_{\mathcal{P},\mathrm{dense}}$
$\displaystyle\leq\varepsilon/180+\frac{(32/\varepsilon)^{-1}}{1-(32/\varepsilon)^{-1}}+\log_{2}(n/2)(32/\varepsilon)^{-\Delta/2}\leq\varepsilon/180+\varepsilon/31+\varepsilon/31<\varepsilon/10.$

Term 2. By having $C_{3}$ and $C_{5}$ sufficiently large, by Proposition
17(c), we can control this term at level $\varepsilon/10$.
Term 3. For this, we follow the null term part of the proof of 7. The key step
in that proof was to bound both terms in (56). The first term can be
controlled via (58). A careful inspection reveals that the condition on $a$
(same as $a_{s}$ here) given in (59) with a possibly larger value of the
leading constant can guarantee the control of both terms in (58) at
$\varepsilon/(160s^{1/2})$. Bounding the second term in (56) required the
argument from (A.1.3) to (A.1.3), within which the dimension $p$ was replaced
by $s$. Our new choice of $r_{t,s}=C_{3}s^{3/4}G_{t}$ for $t>1$ with a
sufficiently large $C_{3}$ allows us to have $\varepsilon/(1100s^{1/2})$ as
the RHS bound in (A.1.3) (dimension being $s$). Correspondingly, the RHS of
(A.1.3) now becomes

$\displaystyle\exp\biggl{\\{}-\frac{\varepsilon
G_{t}}{1100\sqrt{s}}\biggl{(}\frac{550\sqrt{s}}{\varepsilon}\log\Bigl{(}\frac{550\sqrt{s}}{\varepsilon}\Bigr{)}-\frac{550\sqrt{s}}{\varepsilon}+1\biggr{)}\biggr{\\}}\leq\exp\biggl{\\{}-\frac{G_{t}}{2}\log\bigl{(}200\sqrt{s}/\varepsilon\bigr{)}\biggr{\\}}.$

Thus, The second term in (56) can now be bounded instead by

$\displaystyle\frac{\varepsilon}{1100\sqrt{s}}+\frac{(200\sqrt{s}/\varepsilon)^{-1}}{1-(200\sqrt{s}/\varepsilon)^{-1}}+\log_{2}(n/2)(200\sqrt{s}/\varepsilon)^{-\Delta/4}\leq\frac{\varepsilon}{1100\sqrt{s}}+\frac{\varepsilon}{199\sqrt{s}}+\frac{\varepsilon}{199\sqrt{s}}<\frac{\varepsilon}{80\sqrt{s}}.$

Putting everything together, we conclude that

$\sum_{s\in\mathcal{K}}\sum_{t\in\mathcal{T}\backslash\\{1\\}}\mathbb{P}_{\theta}\bigl{(}A_{t,a_{s},s}^{\mathrm{MoM}}>r_{t,s}\bigr{)}\leq\sum_{s\in\mathcal{K}}\frac{\varepsilon}{40\sqrt{s}}<\frac{\varepsilon}{10}.$

Term 4. We follow the null term part of the proof of 8. More specifically,
this term can be split into two terms according to (62). Similar to the
argument made for the second term above, with $C_{4}$ sufficiently large, the
first term in (62) can be guaranteed to be at most $\varepsilon/(80s^{1/2})$.
The second term, with the new choice of $\tilde{r}_{t,s}$ and its leading
constant $C_{5}$ being sufficiently large, can also be bounded above by

$\frac{\varepsilon|\tilde{\mathcal{T}}_{1,s}\backslash\\{1\\}|}{80\sqrt{s}\log_{2}(\tilde{\Delta}_{1,s})}\leq\varepsilon/(80s^{1/2}).$

Therefore, we can again control the fourth term at level $\varepsilon/10$.
Term 5. We again follow the null term part of the proof of 8. By Condition 1
and similar to (A.1.5), we can now bound

$\displaystyle\sum_{s\in\mathcal{K}}\Biggl{(}\sum_{t\in\tilde{\mathcal{T}}_{2,s}}\mathbb{P}_{\theta}(A^{\mathrm{RSM}}_{t,s}>r^{\mathrm{RSM}}_{t,s})+\sum_{t\in\tilde{\mathcal{T}}_{3,s}}\mathbb{P}_{\theta}(A^{\mathrm{RSM}}_{t,s}>r^{\mathrm{RSM}}_{t,s})\Biggr{)}$
$\displaystyle\leq\sum_{s\in\mathcal{K}}\Biggl{(}\sum_{t\in\tilde{\mathcal{T}}_{2,s}}\exp\biggl{\\{}s\log(ep/s)-\frac{t}{C_{6}}\biggr{\\}}+\sum_{t\in\tilde{\mathcal{T}}_{3,s}}\exp\biggl{\\{}s\log(ep/s)-\frac{\tilde{\Delta}_{2,s}}{C_{6}}\biggr{\\}}\Biggr{)}$
$\displaystyle\leq\sum_{s\in\mathcal{K}}\Biggl{(}2\exp\biggl{\\{}s\log(ep/s)-\frac{\tilde{\Delta}_{1,s}}{C_{6}}\biggr{\\}}+\log_{2}(n/2)\frac{\varepsilon}{80s\log
n}\Biggr{)}<\sum_{s\in\mathcal{K}}\frac{\varepsilon}{20s}\leq\frac{\varepsilon}{10},$

as desired.

Alternative term. First, let $s_{1}$ satisfy
$s_{1}(p/s_{1})^{2/\alpha}+\log\log(8n)=\sqrt{p}\log\log(8n)$ and $s_{2}$
satisfy
$s_{2}\bigl{(}(p/s_{2})^{2/\alpha}+\log\log(8n)\bigr{)}=\sqrt{p}\log\log(8n)$.
Note that $s_{1}\geq s_{2}$. For $\theta\in\Theta(p,n,s,\rho)$, we consider
all four possible $(p,s)$ regimes below.
(1) $p>\log^{\alpha-2}(\log(8n))$ and $s\geq s_{2}/2$. We have
$\mathbb{E}_{\theta}(1-\phi_{\mathcal{P},\mathrm{adaptive}})\leq\mathbb{E}_{\theta}(1-{\phi}_{\mathcal{P},\mathrm{dense}})$.
By the alternative term part of the proof of Theorem 5, we can bound the above
quantity by $\varepsilon/2$ as long as $\rho^{2}\geq
C^{\prime}\sqrt{p}\log\log(8n)$ with a sufficiently large $C^{\prime}$. We
also note that when $s_{2}/2\leq s<s_{2}$, we have

$\frac{1}{2}\sqrt{p}\log\log(8n)\leq
s\bigl{(}(p/s)^{2/\alpha}+\log\log(8n)\bigr{)}\leq\sqrt{p}\log\log(8n).$

(2) $p>\log^{\alpha-2}(\log(8n))$ and $s<s_{2}/2$. By the definition of
$\mathcal{K}$, there exists an $\tilde{s}\in\mathcal{K}$ such that
$s\leq\tilde{s}<2s$. We have
$\mathbb{E}_{\theta}(1-\phi_{\mathcal{P},\mathrm{adaptive}})\leq\mathbb{E}_{\theta}(1-{\phi}_{\mathcal{P},\mathrm{sparse},\tilde{s}}^{\mathrm{MoM}})$.
Now, by carefully inspecting the alternative term part of the proof of 7, we
can still deduce
$\mathbb{E}_{\theta}(1-{\phi}_{\mathcal{P},\mathrm{sparse},\tilde{s}}^{\mathrm{MoM}})\leq\varepsilon/2$
as long as $\rho$ satisfies

$\displaystyle\rho^{2}$ $\displaystyle\geq
C^{\prime}\Bigl{(}s\bigl{(}(p/s)^{2/\alpha}+\log\log(8n)\bigr{)}\Bigr{)}\geq\frac{C^{\prime}}{2}\Bigl{(}\tilde{s}\bigl{(}(p/\tilde{s})^{2/\alpha}+\log\log(8n)\bigr{)}\Bigr{)}$
$\displaystyle\geq
C^{\prime\prime}\max\Bigl{\\{}\log^{2}(8/\varepsilon)\max_{t\in\mathcal{T}\backslash\\{1\\}}(r_{t,\tilde{s}}+2\tilde{s}G_{t}),(r_{1,\tilde{s}}+2\tilde{s})\log^{2}(8/\varepsilon),a^{2}_{\tilde{s}}\tilde{s}\Bigr{\\}},$
(65)

for sufficiently large $C^{\prime}$ and $C^{\prime\prime}$, where the final
inequality in (A.2) remains true with our modified choice of $r_{t,s}$.
(3) $p\leq\log^{\alpha-2}(\log(8n))$ and $s\geq s_{1}/2$. We use the same
argument as in (1) to obtain the same condition $\rho^{2}\geq
C^{\prime}\sqrt{p}\log\log(8n)$. Similarly, we also note that when
$s_{1}/2\leq s<s_{1}$, we have

$\frac{1}{2}\sqrt{p}\log\log(8n)\leq
s(p/s)^{2/\alpha}+\log\log(8n)\leq\sqrt{p}\log\log(8n).$

(4) $p\leq\log^{\alpha-2}(\log(8n))$ and $s<s_{1}/2$. Similar to (2), we have
$\mathbb{E}_{\theta}(1-\phi_{\mathcal{P},\mathrm{adaptive}})\leq\mathbb{E}_{\theta}(1-{\phi}_{\mathcal{P},\mathrm{sparse},\tilde{s}}^{\mathrm{RSM}})$.
By carefully examining the alternative term part of the proof of 8, we can
obtain
$\mathbb{E}_{\theta}(1-{\phi}_{\mathcal{P},\mathrm{sparse},\tilde{s}}^{\mathrm{RSM}})\leq\varepsilon/2$
as long as

$\displaystyle\rho^{2}$ $\displaystyle\geq
C^{\prime}\bigl{(}s(p/s)^{2/\alpha}+\log\log(8n)\bigr{)}\geq\frac{C^{\prime}}{2}\bigl{(}\tilde{s}(p/\tilde{s})^{2/\alpha}+\log\log(8n)\bigr{)}$
$\displaystyle\geq C^{\prime\prime}\max\bigl{\\{}(\tilde{r}_{t\neq
1,\tilde{s}}+2\tilde{s})\log^{2}(8/\varepsilon),(\tilde{r}_{1,\tilde{s}}+2\tilde{s})\log^{2}(8/\varepsilon),a^{2}_{\tilde{s}}\tilde{s},\tilde{s}\log(ep/\tilde{s})+\log\log(8n)\bigr{\\}},$
(66)

for sufficiently large $C^{\prime}$ and $C^{\prime\prime}$, where the final
inequality in (A.2) remains true with our new choices of $a_{s}$ and
$\tilde{r}_{t,s}$.

The desired result then follows from Theorem 9 and the first part of its
proof. ∎

###  A.3 Proofs of lower bound results

In this section, we prove all lower bound results presented in the paper,
namely Propositions 2, 4, 6 and 10. Throughout the proof, we use
$P_{\theta,\Xi}$ to denote the probability distribution of
$X\in\mathbb{R}^{p\times n}$ that satisfies $X-\theta\sim\Xi$, and
$E_{\theta,\Xi}$ the corresponding expectation under this distribution. It
suffices to prove the five claims below, as they immediately imply all the
lower bound results in the paper.

  1. (i).

$\log\log(8n)$, for $\mathcal{G}_{\alpha,K}^{\otimes}$ with $0<\alpha\leq 2$
and $K\geq 2^{1+2/\alpha}$ and for $\mathcal{P}_{\alpha,K}^{\otimes}$ with
$\alpha>2$ and $K\geq\sqrt{\alpha+1}$ or $\alpha=2$ and $K\geq 1$;

  2. (ii).

$\sqrt{p\log\log(8n)}$ when $s\geq\sqrt{p\log\log(8n)}$, for
$\mathcal{G}_{\alpha,K}^{\otimes}$ with $0<\alpha\leq 2$ and $K\geq
2^{1+2/\alpha}$ and for $\mathcal{P}_{\alpha,K}^{\otimes}$ with $\alpha>2$ and
$K\geq\sqrt{\alpha+1}$ or $\alpha=2$ and $K\geq 1$;

  3. (iii).

$p^{2/\alpha}$ when $s\geq 30$, for $\mathcal{P}_{\alpha,K}^{\otimes}$ with
$\alpha>2$ and $K\geq\sqrt{2}$ or $\alpha=2$ and $K\geq 1$;

  4. (iv).

$s(p/s)^{2/\alpha}$ when $30\leq s\leq p^{\frac{\alpha-4}{2\alpha-4}}$, for
$\mathcal{P}_{\alpha,K}^{\otimes}$ with $\alpha\geq 4$ and $K\geq\sqrt{2}$;

  5. (v).

$s\log^{2/\alpha}(ep/s)$ when $30\leq s\leq\sqrt{p}\log^{-2/\alpha}(ep)$, for
$\mathcal{G}_{\alpha,K}^{\otimes}$ with $0<\alpha\leq 2$ and $K\geq
2^{1+2/\alpha}$.

(i). We first consider that each entry of the noise matrix $E$ follows an
independent standard normal distribution. Then for $0<\alpha\leq 2$,
$i\in[n]$, $j\in[p]$ and $x\geq 2^{1+2/\alpha}$, we have

$\displaystyle\mathbb{E}\Biggl{[}\exp\biggl{\\{}\biggl{(}\frac{|E_{i}(j)|}{x}\biggr{)}^{\alpha}\biggr{\\}}\Biggr{]}$
$\displaystyle=\mathbb{E}\Biggl{[}\exp\biggl{\\{}\biggl{(}\frac{|E_{i}(j)|}{x}\biggr{)}^{\alpha}\biggr{\\}}\mathbbm{1}_{\\{|E_{i}(j)|\geq
2\\}}\Biggr{]}+\mathbb{E}\Biggl{[}\exp\biggl{\\{}\biggl{(}\frac{|E_{i}(j)|}{x}\biggr{)}^{\alpha}\biggr{\\}}\mathbbm{1}_{\\{|E_{i}(j)|<2\\}}\Biggr{]}$
$\displaystyle\leq\mathbb{E}\Biggl{[}\exp\biggl{\\{}\biggl{(}\frac{|E_{i}(j)|}{2}\biggr{)}^{2}\biggr{\\}}\mathbbm{1}_{\\{|E_{i}(j)|\geq
2\\}}\Biggr{]}+\exp\bigl{\\{}(2/x)^{\alpha}\bigr{\\}}$
$\displaystyle=\sqrt{2}-\mathbb{E}\Biggl{[}\exp\biggl{\\{}\biggl{(}\frac{|E_{i}(j)|}{2}\biggr{)}^{2}\biggr{\\}}\mathbbm{1}_{\\{|E_{i}(j)|<2\\}}\Biggr{]}+\exp\bigl{\\{}(2/x)^{\alpha}\bigr{\\}}$
$\displaystyle\leq\sqrt{2}-\bigl{(}1-\exp(-2)\bigr{)}+\exp\bigl{\\{}(2/x)^{\alpha}\bigr{\\}}<2,$

where the penultimate inequality follows from the standard Gaussian tail
bound. Thus, for any $K\geq 2^{1+2/\alpha}$, we have
$\|E_{i}(j)\|_{\psi_{\alpha}}\leq K$. Furthermore, by Jensen’s inequality, we
obtain for $\alpha>2$

$\mathbb{E}|E_{i}(j)|^{\alpha}\leq\biggl{\\{}\mathbb{E}|E_{i}(j)|^{2\lceil\alpha/2\rceil}\biggr{\\}}^{\frac{\alpha/2}{\lceil\alpha/2\rceil}}=\biggl{\\{}\prod_{i=1}^{\lceil\alpha/2\rceil}(2i-1)\biggr{\\}}^{\frac{\alpha/2}{\lceil\alpha/2\rceil}}\leq\bigl{(}2\lceil\alpha/2\rceil-1\bigr{)}^{\alpha/2}\leq(\alpha+1)^{\alpha/2}.$

Therefore $P_{e}\in\mathcal{G}_{\alpha,K}^{\otimes}$ for all $0<\alpha\leq 2$
and $K\geq 2^{1+\alpha/2}$ and $P_{e}\in\mathcal{P}_{\alpha,K}^{\otimes}$ for
all $\alpha\geq 2$ and $K\geq\sqrt{\alpha+1}$ or $\alpha=2$ and $K\geq 1$. For
the mean vectors $\mu_{1}$ and $\mu_{2}$ in the definition of
$\Theta^{(t_{0})}(p,n,s,\rho)$, we restrict them to be equal in all
coordinates except perhaps the first. Then under this setting, the lower bound
$\log\log(8n)$ of the detection rate is established in Gao et al. (2020,
Proposition 4.2). Note that this lower bound holds for all $1\leq s\leq p$.

(ii). When $s\geq\sqrt{p\log\log(8n)}$, we again consider the independent
standard normal noise structure. The lower bound $\sqrt{p\log\log(8n)}$ is
shown in Liu et al. (2021, Proposition 3).

We now use a unified approach to establish the three remaining rates. Let
$\xi$ and $\tilde{\xi}$ be two independent random variables on $\mathbb{R}$,
whose distributions are to be specified later; let $\tilde{\mathcal{\omega}}$
be an discrete random variable (independent of $\xi,\tilde{\xi}$), taking
values

$\tilde{\omega}=\begin{cases}+1&\text{ w.p.
}\frac{s}{4p}\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}\\\ -1&\text{ w.p.
}\frac{s}{4p}\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}\\\ 0&\text{
otherwise,}\end{cases}$ (67)

where $\gamma>0$ is also to be specified later; let
$\tilde{\pi}:=\tilde{\xi}+\gamma\tilde{\omega}$. We remark that
$\tilde{\omega}$ can be viewed as a Rademacher random variable being
multiplied by a Bernoulli random variable. Denote
$\underline{\xi}:=(\xi(1),\dotsc,\xi(p))^{\top}\in\mathbb{R}^{p}$, where the
coordinates are i.i.d. copies of $\xi$ and we use similar notations
$\underline{\tilde{\xi}},\underline{\tilde{\omega}},\underline{\tilde{\pi}}$.
Let $\nu$ denote the distribution of
$\gamma\tilde{\underline{\omega}}\in\mathbb{R}^{p}$, and $\bar{\nu}$ the
distribution restricted to
$\mathcal{V}_{s}:=\\{v\in\mathbb{R}^{p}:s/6\leq\|v\|_{0}\leq s\\}$, i.e.
$\bar{\nu}(A)=\frac{\nu(A\cap\mathcal{V}_{s})}{\nu(\mathcal{V}_{s})}$ for any
Borel set $A\subseteq\mathbb{R}^{p}$. Consequently, the support of this
restricted measure satisfies

$\mathrm{supp}(\bar{\nu})\subseteq\bigl{\\{}v\in\mathbb{R}^{p}:\|v\|_{0}\leq
s,\|v\|^{2}_{2}\geq s\gamma^{2}/6\bigr{\\}}.$ (68)

We also have

$-\nu(\mathcal{V}_{s}^{c})=-\Bigl{(}\frac{1}{\nu(\mathcal{V}_{s})}-1\Bigr{)}\nu(\mathcal{V}_{s})\leq\nu(A)-\bar{\nu}(A)=\nu(A\cap\mathcal{V}_{s}^{c})-\Bigl{(}\frac{1}{\nu(\mathcal{V}_{s})}-1\Bigr{)}\nu(A\cap\mathcal{V}_{s})\leq\nu(\mathcal{V}_{s}^{c}).$
(69)

for any Borel set $A$. Denote $\Xi^{*}$ to be the distribution of
$(\underline{\xi},R_{2},\dotsc,R_{n})\in\mathbb{R}^{p\times n}$,
$\tilde{\Xi}^{*}$ the distribution of
$(\tilde{\underline{\xi}},R_{2},\dotsc,R_{n})$, and $\tilde{\Pi}$ the
distribution of $(\tilde{\underline{\pi}},R_{2},\dotsc,R_{n})$, where
$(R_{i}(j))_{i\in\\{2,\dotsc,n\\},j\in[p]}$ are i.i.d. Rademacher random
variables, independent of
$\underline{\xi},\tilde{\underline{\xi}},\tilde{\underline{\pi}}$. Now we
consider the following mixture measures:

$\bar{\mathbf{P}}^{*}:=\int
P_{\theta^{(1)},{\Xi}^{*}}\,\bar{\nu}(d\theta_{1}),\quad\mathbf{P}^{*}:=\int
P_{\theta^{(1)},{\Xi}^{*}}\,\nu(d\theta_{1}),\quad\text{and}\quad\tilde{\mathbf{P}}^{*}:=\int
P_{\theta^{(1)},\tilde{\Xi}^{*}}\,\nu(d\theta_{1}),$

where $\theta^{(1)}:=(\theta_{1},0,\dotsc,0)\in\mathbb{R}^{p\times n}$.
Observe that $\tilde{\mathbf{P}}^{*}=P_{0,\tilde{\Pi}}$, as both sides
represent the distribution of $(\tilde{\underline{\pi}},R_{2},\dotsc,R_{n})$.
We first provide an upper bound on the total variation distance between
${\mathbf{P}}^{*}$ and $\bar{\mathbf{P}}^{*}$. By (69), we have

$\mathrm{TV}({\mathbf{P}}^{*},\bar{\mathbf{P}}^{*})\leq\mathrm{TV}(\nu,\bar{\nu})=\sup_{A}|\nu(A)-\bar{\nu}(A)|\leq\nu(\mathcal{V}_{s}^{c})=\mathbb{P}\bigl{(}\|\underline{\tilde{\omega}}\|_{0}>s\bigr{)}+\mathbb{P}\bigl{(}\|\underline{\tilde{\omega}}\|_{0}<s/6\bigr{)}.$
(70)

Suppose $\gamma$ is chosen to satisfy $\gamma\leq\sqrt{p/s}$. Then from (67),
we deduce $\frac{s}{3p}\leq\mathbb{P}(\tilde{\omega}(1)\neq 0)<\frac{s}{2p}$.
By Chernoff bounds, we have

$\displaystyle\mathbb{P}\bigl{(}\|\underline{\tilde{\omega}}\|_{0}>s\bigr{)}$
$\displaystyle\leq\frac{\mathbb{E}\bigl{[}e^{\|\underline{\tilde{\omega}}\|_{0}\log
2}\bigr{]}}{e^{s\log 2}}\leq\frac{\bigl{(}1+s/(2p)\bigr{)}^{p}}{e^{s\log
2}}\leq e^{-s/6},$
$\displaystyle\mathbb{P}\bigl{(}\|\underline{\tilde{\omega}}\|_{0}<s/6\bigr{)}$
$\displaystyle\leq\frac{\mathbb{E}\bigl{[}e^{-\|\underline{\tilde{\omega}}\|_{0}\log
2}\bigr{]}}{e^{-(s\log
2)/6}}\leq\frac{\bigl{(}1-s/(6p)\bigr{)}^{p}}{e^{-(s\log 2)/6}}\leq
e^{-s/20}.$ (71)

The key step of the proof is to carefully construct two random variables $\xi$
and $\tilde{\xi}$ such that the following three conditions are satisfied:

$\displaystyle\Xi^{*}\in\mathcal{G}_{\alpha,K}\ $ $\displaystyle(\text{resp.
}\mathcal{P}_{\alpha,K}),$ (72)
$\displaystyle\tilde{\Pi}\in\mathcal{G}_{\alpha,K}\ $
$\displaystyle(\text{resp. }\mathcal{P}_{\alpha,K}),$ (73) $\displaystyle
H^{2}(P_{\xi},P_{\tilde{\xi}})$ $\displaystyle\leq\frac{1}{16p},$ (74)

where, in a slight abuse of notation, we denote $P_{\xi}$ and
$P_{\tilde{\xi}}$ to be the distribution of $\xi$ and $\tilde{\xi}$
respectively. Then, by data processing inequality as well as some basic
properties of the total variation distance and the Hellinger distance, we
obtain

$\displaystyle\mathrm{TV}(\tilde{\mathbf{P}}^{*},{\mathbf{P}}^{*})$
$\displaystyle\leq\mathrm{TV}(P_{0,\tilde{\Xi}^{*}},P_{0,{\Xi}^{*}})\leq\mathrm{TV}\bigl{(}P_{\tilde{\underline{\xi}}},P_{\underline{\xi}}\bigr{)}\leq
H\bigl{(}P_{\tilde{\underline{\xi}}},P_{\underline{\xi}}\bigr{)}=\sqrt{2\bigl{(}1-(1-H^{2}(P_{\tilde{\xi}},P_{\xi})/2)^{p}\bigr{)}}$
$\displaystyle\leq\sqrt{pH^{2}(P_{\xi},P_{\tilde{\xi}})}\leq 1/4,$ (75)

where the penultimate inequality follows from the fact that $(1-x)^{p}\geq
1-px$ for all $0\leq x\leq 1$ and $p\geq 1$. Combining (68), (70), (71), and
(75), when $s\geq 30$, for all $\rho^{2}\leq s\gamma^{2}/12$, we have

$\displaystyle\mathcal{R}_{\mathcal{Q}}(\rho)$
$\displaystyle=\inf_{\phi\in\Phi}\biggl{\\{}\sup_{P_{e}\in\mathcal{Q}}\sup_{\theta\in\Theta_{0}(p,n)}\mathbb{E}_{\theta,P_{e}}\phi+\sup_{P_{e}\in\mathcal{Q}}\sup_{\theta\in\Theta(p,n,s,\rho)}\mathbb{E}_{\theta,P_{e}}(1-\phi)\biggr{\\}}$
$\displaystyle\geq
1-\mathrm{TV}(P_{0,\tilde{\Pi}},\bar{\mathbf{P}}^{*})=1-\mathrm{TV}(\tilde{\mathbf{P}}^{*},\bar{\mathbf{P}}^{*})\geq
1-\mathrm{TV}(\tilde{\mathbf{P}}^{*},{\mathbf{P}}^{*})-\mathrm{TV}({\mathbf{P}}^{*},\bar{\mathbf{P}}^{*})$
$\displaystyle\geq 3/4-e^{-s/6}-e^{-s/20}\geq 1/2,$

where the class $\mathcal{Q}$ is either $\mathcal{G}_{\alpha,K}^{\otimes}$ or
$\mathcal{P}_{\alpha,K}^{\otimes}$. Below, we give three constructions of
$\xi$ and $\tilde{\xi}$ that satisfy conditions (72), (73) and (74), and
specify the corresponding choices of $\gamma$. Each construction corresponds
to a rate given at the beginning of the proof.
(iii). We work within the noise distribution class
$\mathcal{P}_{\alpha,K}^{\otimes}$ with $\alpha>2$ and $K\geq\sqrt{2}$ or
$\alpha=2$ and $K\geq 1$ and we only consider $s=30$ (a constant) in this
construction. Let $\xi$ and $\tilde{\xi}$ be two independent discrete random
variables such that

$\tilde{\xi}=\begin{cases}\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1/2}&\text{
w.p. }1/2\\\ -\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1/2}&\text{ w.p.
}1/2\end{cases}\qquad\text{and}\qquad\xi=\begin{cases}\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1/2}&\text{
w.p.
}\frac{t_{0}^{2}-1}{2\Bigl{(}t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}\Bigr{)}}\\\
-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1/2}&\text{ w.p.
}\frac{t_{0}^{2}-1}{2\Bigl{(}t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}\Bigr{)}}\\\
t_{0}&\text{ w.p.
}\frac{1-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}{2\Bigl{(}t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}\Bigr{)}}\\\
-t_{0}&\text{ w.p.
}\frac{1-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}{2\Bigl{(}t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}\Bigr{)}}.\end{cases}$

Direct calculations show that both $\xi$ and
$\tilde{\xi}+\gamma\tilde{\omega}$ have mean 0 and variance 1. Choose

$\gamma=\max\biggl{\\{}-1+\frac{\bigl{\\{}(K^{\alpha}-1)p/s\bigr{\\}}^{1/\alpha}}{\max\\{32,K\\}},\frac{\sqrt{2}}{32}\biggr{\\}}\quad\text{and}\quad
t_{0}=32\gamma\geq\sqrt{2}.$

Note that we have $\gamma\leq\sqrt{p/s}$. Now, to check (72) and (73), it
suffices to only verify that $\mathbb{E}|\xi|^{\alpha}\leq K^{\alpha}$ and
that $\mathbb{E}\bigl{|}\tilde{\xi}+\gamma\tilde{\omega}\bigr{|}^{\alpha}\leq
K^{\alpha}$ respectively. Indeed, as $\alpha>2$ and $K\geq\sqrt{2}$, we have

$\displaystyle\mathbb{E}|\xi|^{\alpha}$ $\displaystyle\leq
1+t_{0}^{\alpha}\frac{1-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}{t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}\leq
1+t_{0}^{\alpha}\frac{\gamma^{2}s/(2p)}{t_{0}^{2}-1}=1+\frac{\gamma^{2}st_{0}^{\alpha-2}}{p}\leq
1+\frac{32^{\alpha-2}\gamma^{\alpha}s}{p}$ $\displaystyle\leq
1+\max\biggl{\\{}K^{\alpha}-1,2^{\alpha/2-10}\biggr{\\}}\leq K^{\alpha},$

and

$\displaystyle\mathbb{E}\bigl{|}\tilde{\xi}+\gamma\tilde{\omega}\bigr{|}^{\alpha}$
$\displaystyle\leq 1+(1+\gamma)^{\alpha}\cdot\mathbb{P}(\tilde{\omega}\neq
0)\leq 1+\frac{(1+\gamma)^{\alpha}s}{2p}\leq
1+\max\biggl{\\{}K^{\alpha}-1,\frac{(17/16)^{\alpha}}{2}\biggr{\\}}\leq
K^{\alpha}.$

We also verify (74):

$\displaystyle H^{2}(P_{\xi},P_{\tilde{\xi}})$
$\displaystyle=\Biggl{(}1-\sqrt{\frac{t_{0}^{2}-1}{t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}}\Biggr{)}^{2}+\frac{1-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}{t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}\leq\frac{2\Bigl{(}1-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}\bigr{)}}{t_{0}^{2}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1}}$
$\displaystyle\leq\frac{2\gamma^{2}s}{pt_{0}^{2}}=\frac{60\gamma^{2}}{(32\gamma)^{2}p}\leq\frac{1}{16p}.$

We thus conclude that under the noise distribution class
$\mathcal{P}_{\alpha,K}^{\otimes}$ with $\alpha>2$ and $K\geq\sqrt{2}$,
whenever $s\geq 30$ and

$\rho^{2}\leq\frac{30}{12}\Biggl{(}\max\biggl{\\{}-1+\frac{\bigl{\\{}(K^{\alpha}-1)p/30\bigr{\\}}^{1/\alpha}}{\max\\{32,K\\}},\frac{\sqrt{2}}{32}\biggr{\\}}\Biggr{)}^{2}\leq
c\cdot p^{2/\alpha},$

for some $c>0$ depending only on $\alpha$ and $K$, we have
$\mathcal{R}_{\mathcal{P}}(\rho)\geq 1/2$. When $\alpha=2$, we can simply set
$\gamma=\sqrt{p/s}$ and $t_{0}=32\gamma$ and reach the same conclusion.

(iv). We work within the noise distribution class
$\mathcal{P}_{\alpha,K}^{\otimes}$ with $\alpha\geq 4$ and $K\geq\sqrt{2}$. We
first define an auxiliary random variable $\xi_{\mathrm{aux}}$ and with the
following density elsewhere:

$f_{\xi_{\mathrm{aux}}}(x)=\begin{cases}1000(x-\mathrm{sgn}(x)\cdot
0.9)^{2}&\qquad 0.9\leq|x|<0.95\\\ 5-1000(x-\mathrm{sgn}(x))^{2}&\qquad
0.95\leq|x|\leq 1.05\\\ 1000(x-\mathrm{sgn}(x)\cdot 1.1)^{2}&\qquad
1.05<|x|\leq 1.1\\\ 0&\qquad\mathrm{otherwise}.\end{cases}$

Observe that $\mathbb{E}\xi_{\mathrm{aux}}=0$ and
$\sigma_{\mathrm{aux}}^{2}:=\mathbb{E}\xi_{\mathrm{aux}}^{2}\in(1,1.01)$. Now
let $\xi$ and $\tilde{\xi}$ be independent random variables such that
$\xi\stackrel{{\scriptstyle
d}}{{=}}\sigma_{\mathrm{aux}}^{-1}\xi_{\mathrm{aux}}$ and
$\tilde{\xi}\stackrel{{\scriptstyle
d}}{{=}}\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1/2}\sigma_{\mathrm{aux}}^{-1}\xi_{\mathrm{aux}}$.
Again, direct calculations show that both $\xi$ and
$\tilde{\xi}+\gamma\tilde{\omega}$ have mean 0 and variance 1. For condition
(72), since $|\xi|<1.1$ holds with probability one, we have
$\Xi^{*}\in\mathcal{P}_{\alpha,K}$ for all $\alpha\geq 4$ and $K\geq\sqrt{2}$.
We choose

$\gamma=\frac{1}{12}(p/s)^{1/\alpha}.$

Note that $\gamma\leq\sqrt{p/s}$. We verify (73) as follows:

$\displaystyle\mathbb{E}\bigl{|}\tilde{\xi}+\gamma\tilde{\omega}\bigr{|}^{\alpha}$
$\displaystyle\leq
1.1^{\alpha}+(1.1+\gamma)^{\alpha}\cdot\mathbb{P}(\tilde{\omega}\neq 0)\leq
1.1^{\alpha}+\frac{(1.1+\gamma)^{\alpha}s}{2p}\leq
1.1^{\alpha}+\frac{\max\\{1.2,12\gamma\\}^{\alpha}s}{2p}$
$\displaystyle\leq\max\biggl{\\{}1.1^{\alpha}+\frac{1.2^{\alpha}}{2},1.1^{\alpha}+\frac{1}{2}\biggr{\\}}\leq
2^{\alpha/2}\leq K^{\alpha}.$ (76)

Finally, by Ibragimov and Has’ Minskii (2013, Theorem 7.6), we have when
$s\leq p^{\frac{\alpha-4}{2\alpha-4}}$

$\displaystyle H^{2}(P_{\xi},P_{\tilde{\xi}})$
$\displaystyle\leq\frac{\Bigl{(}\sigma_{\mathrm{aux}}^{-1}-\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1/2}\sigma_{\mathrm{aux}}^{-1}\Bigr{)}^{2}}{4}\sup_{u\in\bigl{[}\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{-1/2}\sigma_{\mathrm{aux}}^{-1},\sigma_{\mathrm{aux}}^{-1}\bigr{]}}\frac{\int_{\mathrm{supp}(\xi_{\mathrm{aux}})}\bigl{(}f^{\prime}_{\xi_{\mathrm{aux}}}(x)\bigr{)}^{2}/f_{\xi_{\mathrm{aux}}}(x)\,dx}{u^{2}}$
$\displaystyle\leq\frac{\Bigl{(}\bigl{(}1+\frac{\gamma^{2}s}{2p}\bigr{)}^{1/2}-1\Bigr{)}^{2}}{4}\int_{\mathrm{supp}(\xi_{\mathrm{aux}})}\bigl{(}f^{\prime}_{\xi_{\mathrm{aux}}}(x)\bigr{)}^{2}/f_{\xi_{\mathrm{aux}}}(x)\,dx$
$\displaystyle\leq\frac{\gamma^{4}s^{2}}{64p^{2}}\cdot
4\biggl{(}\int_{0}^{0.05}\frac{(-2000x)^{2}}{5-1000x^{2}}\,dx+\int_{0.05}^{0.1}\frac{(2000(x-0.1))^{2}}{1000(x-0.1)^{2}}\,dx\biggr{)}\leq\frac{25\gamma^{4}s^{2}}{p^{2}}\leq\frac{1}{16p},$
(77)

and this verifies (74). Therefore, under the noise distribution class
$\mathcal{P}_{\alpha,K}^{\otimes}$ with $\alpha\geq 4$ and $K\geq\sqrt{2}$,
whenever $30\leq s\leq p^{\frac{\alpha-4}{2\alpha-4}}$ and $\rho^{2}\leq
s(p/s)^{2/\alpha}/1728$, we have $\mathcal{R}_{\mathcal{P}}(\rho)\geq 1/2$.

(v). We work within the noise distribution class
$\mathcal{G}_{\alpha,K}^{\otimes}$ with $0<\alpha\leq 2$ and $K\geq
2^{1+2/\alpha}$. We use the same construction as in (iv), but now choose
instead

$\gamma=\frac{1}{3\cdot(8/\alpha)^{1/\alpha}}\log^{1/\alpha}(ep/s).$

Since $\log x\leq\frac{2}{e\alpha}x^{\alpha/2}$ for all $x\geq e$, we can
verify that $\gamma\leq\sqrt{p/s}$. Again, for condition (72), since
$|\xi|<1.1$ holds with probability one, we have
$\Xi^{*}\in\mathcal{G}_{\alpha,K}$ for all $\alpha\geq 4$ and $K\geq
2^{1+2/\alpha}$, as $\exp\\{(1.1/K)^{\alpha}\\}\leq e^{1/4}<2$. We now verify
(73) using the technique in (A.3):

$\displaystyle\mathbb{E}\Biggl{[}\exp\biggl{\\{}\biggl{(}\frac{|\tilde{\xi}+\gamma\tilde{\omega}|}{K}\biggr{)}^{\alpha}\biggr{\\}}\Biggr{]}$
$\displaystyle\leq\exp\biggl{\\{}\biggl{(}\frac{1.1}{K}\biggr{)}^{\alpha}\biggr{\\}}+\frac{s}{2p}\exp\biggl{\\{}\biggl{(}\frac{\max\\{2,3\gamma\\}}{K}\biggr{)}^{\alpha}\biggr{\\}}$
$\displaystyle\leq
e^{1/4}+\max\Biggl{\\{}e^{1/4}\frac{s}{2p},\Bigl{(}\frac{s}{2p}\Bigr{)}^{1-\frac{2\alpha}{8K^{\alpha}}}\Biggr{\\}}$
$\displaystyle\leq e^{1/4}+\max\bigl{\\{}e^{1/4}/2,\sqrt{1/2}\bigr{\\}}<2.$

We then follow (A.3) to verify (74) as well:

$H^{2}(P_{\xi},P_{\tilde{\xi}})\leq\frac{25\gamma^{4}s^{2}}{p^{2}}\leq\frac{1}{16p},$

when $s\leq\sqrt{p}\log^{-2/\alpha}(ep)$. Therefore, under the noise
distribution class $\mathcal{G}_{\alpha,K}^{\otimes}$ with $\alpha\leq 2$ and
$K\geq 2^{1+2/\alpha}$, whenever $30\leq s\leq\sqrt{p}\log^{-2/\alpha}(ep)$
and $\rho^{2}\leq\frac{s\log^{2/\alpha}(ep/s)}{36\cdot(8/\alpha)^{1/\alpha}}$,
we have $\mathcal{R}_{\mathcal{G}}(\rho)\geq 1/2$.

##  Appendix B Auxiliary results

We first present the definition and some basic properties of sub-Weibull
random variables. For a more in-depth introduction and discussion, we refer to
Vladimirova et al. (2020) and Kuchibhotla and Chakrabortty (2022, Section 2).

######  Definition 4 (Orlicz norms).

Let $f:[0,\infty)\rightarrow[0,\infty)$ be a non-decreasing function with
$f(0)=0$. The $f$-Orlicz norm of a real-valued random variable $X$ is

$\|X\|_{f}:=\inf\\{t>0:\mathbb{E}f(|X|/t)\leq 1\\}.$

######  Definition 5 (sub-Weibull random variables).

A random variable $X$ is sub-Weibull of order $\alpha>0$, denoted sub-
Weibull($\alpha$), if it has mean zero and

$\|X\|_{\psi_{\alpha}}<\infty,$

with the function $\psi_{\alpha}$ defined by
$\psi_{\alpha}(x):=\exp(x^{\alpha})-1$ for $x\geq 0$.

######  Proposition 12 (Vladimirova et al., 2020, Theorem 2.1).

Let $X$ be a sub-Weibull($\alpha$) random variable with $0<\alpha\leq 2$ and
$\|X\|_{\psi_{\alpha}}=K<\infty$. Then, we have the following properties:
(a) the tails of $X$ satisfy

$\mathbb{P}(|X|\geq x)\leq 2\exp\\{-(x/K)^{\alpha}\\}\qquad\text{for all
}x\geq 0;$

(b) Let $\|X\|_{k}:=\mathbb{E}(|X|^{k})^{1/k},k\geq 1$, then

$\|X\|_{k}\leq K^{\prime}k^{1/\alpha}$

for some absolute constant $K^{\prime}>0$.
(c) Conversely, if a random variable $X$ has mean zero and satisfies
$\mathbb{P}(|X|\geq x)\leq 2\exp\\{-(x/K)^{\alpha}\\}$ for all $x\geq 0$, then
there exists $K^{\prime\prime}>0$, depending only on $\alpha$ and $K$, such
that

$\mathbb{E}\exp\bigl{\\{}(|X|/K^{\prime\prime})^{\alpha}\bigr{\\}}\leq 2.$

In other words, $X$ is a sub-Weibull($\alpha$) random variable with
$\|X\|_{\psi_{\alpha}}\leq K^{\prime\prime}<\infty$.

######  Proposition 13 (Vladimirova et al., 2020, Proposition 2.1).

Let $\alpha>\alpha^{\prime}>0$ and $X$ be a sub-Weibull($\alpha$) random
variable with $\|X\|_{\psi_{\alpha}}=K<\infty$. Then there exists
$K^{\prime}>0$, depending only on $\alpha^{\prime}$ and $K$, such that $X$ is
a sub-Weibull($\alpha^{\prime}$) random variable with
$\|X\|_{\psi_{\alpha^{\prime}}}\leq K^{\prime}<\infty$.

We now provide two tail bound results from literature for sums and quadratic
forms of independent sub-Weibull random variables respectively. 15 below can
be viewed as an extension of the Hanson–Wright inequality (Hanson and Wright,
1971).

######  Proposition 14 (Kuchibhotla and Chakrabortty, 2022, Theorem 3.1).

Let $\alpha>0$ and $n\in\mathbb{N}$. Let $X_{1},\dotsc,X_{n}$ be independent
mean zero sub-Weibull random variables of order $\alpha$, with
$\|X_{i}\|_{\psi_{\alpha}}\leq K$ for all $i\in\mathbb{N}$ and for some $K>0$.
Then, there exists a constant $C>0$, depending only on $\alpha$ and $K$, such
that for any vector $u=(u_{1},\dotsc,u_{n})^{\top}\in\mathbb{R}^{n}$ and
$x\geq 0$, we have

$\mathbb{P}\Bigl{(}\Bigl{|}\sum_{i=1}^{n}u_{i}X_{i}\Bigr{|}\geq
x\Bigr{)}\leq\exp\biggl{\\{}1-\min\biggl{\\{}\biggl{(}\frac{x}{C\|u\|_{2}}\biggr{)}^{2},\biggl{(}\frac{x}{C\|u\|_{\beta(\alpha)}}\biggr{)}^{\alpha}\biggr{\\}}\biggr{\\}},$

where $\beta(\alpha)=\infty$ when $\alpha\leq 1$ and
$\beta(\alpha)=\alpha/(\alpha-1)$ when $\alpha>1$.

######  Proposition 15 (Götze et al., 2021, Proposition 1.5).

Let $\alpha\in(0,1]\cup\\{2\\}$, $A=(a_{ij})\in\mathbb{R}^{n\times n}$ be a
symmetric matrix and $X_{1},\dotsc,X_{n}$ be independent mean zero sub-Weibull
random variables of order $\alpha$, with $\mathbb{E}X_{i}^{2}=\sigma_{i}^{2}$
and $\|X_{i}\|_{\psi_{\alpha}}\leq K$ for all $i\in\mathbb{N}$ and for some
$K>0$. Then, there exists a constant $C>0$, depending only on $\alpha$ and
$K$, such that for any $x\geq 0$, we have

$\mathbb{P}\biggl{(}\Bigl{|}\sum_{1\leq i,j\leq
n}a_{ij}X_{i}X_{j}-\sum_{i=1}^{n}a_{ii}\sigma_{i}^{2}\Bigr{|}\geq
x\biggr{)}\leq\exp\bigl{(}1-\eta_{\alpha}(x/C;A)\bigr{)},$

where

$\eta_{\alpha}(x;A):=\min\Biggl{\\{}\biggl{(}\frac{x}{\|A\|_{\mathrm{F}}}\biggr{)}^{2},\frac{x}{\|A\|_{2}},\biggl{(}\frac{x}{\|A\|_{2\rightarrow\infty}}\biggr{)}^{\frac{2\alpha}{2+\alpha}},\biggl{(}\frac{x}{\|A\|_{\max}}\biggr{)}^{\frac{\alpha}{2}}\Biggr{\\}}.$

The following proposition presents a concentration inequality for sums of
independent random variables with only finite certain number of moments. We
use the form of the Fuk–Nagaev type inequalities appeared in Rio (2017).

######  Proposition 16 (Fuk, 1973; Nagaev, 1979).

Let $X_{1},\dotsc,X_{n}$ be independent random variables, each having mean $0$
and variance $\sigma^{2}$. Assume further that for some $q\geq 2$ and
$C_{q}>0$, we have for all $i\in[n]$

$\mathbb{E}[\\{\max(X_{i},0)\\}^{q}]\leq C_{q}.$

Then for any $x>0$, we have

$\mathbb{P}\biggl{(}\sum_{i=1}^{n}X_{i}\geq
x\biggr{)}\leq\Biggl{(}\frac{(q+2)(nC_{q})^{1/q}}{qx}\Biggr{)}^{q}+\exp\Biggl{\\{}-\frac{2x^{2}}{n(q+2)^{2}e^{q}\sigma^{2}}\Biggr{\\}}.$

######  Proposition 17.

Let $X_{1},\dotsc,X_{p}$ be independent random variables, each with mean zero
and unit variance. Let $a\geq 0$ and
$Z:=\sum_{i=1}^{p}(X_{i}^{2}-1)\mathbbm{1}_{\\{|X_{i}|\geq a\\}}$.
(a) Let $\alpha>0$, $K>0$, $0<\varepsilon\leq 1$ and $1\leq s\leq\sqrt{p}$.
Assume that $X_{1},\dotsc,X_{p}$ are independent sub-Weibull random variables
of order $\alpha$, with $\|X_{i}\|_{\psi_{\alpha}}\leq K$ for all $i\in[p]$.
By setting

$a\geq K\log^{1/\alpha}\Bigl{(}\frac{4ep}{\varepsilon
s}\Bigr{)}\qquad\text{and}\qquad
r=2^{2/\alpha}K^{2}s\log^{2/\alpha}\Bigl{(}\frac{4p}{\sqrt{\varepsilon}s}\Bigr{)},$

we have $\mathbb{P}(Z>r)\leq\varepsilon$.
(b) Let $\alpha\geq 2$, $K>0$, $0<\varepsilon\leq 1$ and $1\leq s\leq p$.
Assume that $\mathbb{E}|X_{i}/K|^{\alpha}\leq 1$ for all $i\in[p]$. By setting

$a\geq K\Bigl{(}\frac{2ep}{\varepsilon
s}\Bigr{)}^{1/\alpha}\qquad\text{and}\qquad
r=\frac{\alpha-2}{\alpha}K^{2}s\Bigl{(}\frac{2ep}{\varepsilon
s}\Bigr{)}^{2/\alpha},$

we have $\mathbb{P}(Z>r)\leq\varepsilon$.
(c) Assume the same conditions as in (b). Write
$Z_{s}:=\sum_{i=1}^{p}(X_{i}^{2}-1)\mathbbm{1}_{\\{|X_{i}|\geq a_{s}\\}}$ to
make the dependence on $s$ explicit. By choosing the same $a_{s}$ and $r_{s}$
as in (b), we have

$\mathbb{P}\bigl{(}\max_{s\in[p]}Z_{s}/r_{s}>1\bigr{)}\leq 2\varepsilon.$

###### Proof.

We denote the order statistics of $|X_{1}|,\dotsc,|X_{p}|$ as
$|X|_{(1)}\leq\dotsc\leq|X|_{(p)}$. For $x\geq 0$, we write
$q_{x}:=\min_{i\in[p]}\mathbb{P}(|X_{i}|\geq x)$ and
$\mathcal{J}_{x}:=\\{i\in[p]:|X_{i}|\geq x\\}$.
(a) Note that $q_{x}\leq 2\exp\\{-(x/K)^{\alpha}\\}$ by Proposition 12(a).
Since $s\leq\sqrt{p}$, we observe that

$\sum_{j=1}^{s}K^{2}\log^{2/\alpha}\Bigl{(}\frac{4ep}{\varepsilon
j}\Bigr{)}\leq\sum_{j=1}^{s}K^{2}\log^{2/\alpha}\Bigl{(}\frac{4ep^{2}}{\varepsilon
s^{2}}\Bigr{)}\leq
2^{2/\alpha}K^{2}s\log^{2/\alpha}\Bigl{(}\frac{4p}{\sqrt{\varepsilon}s}\Bigr{)}=r.$

Then, by a union bound and a binomial tail bound, we have

$\displaystyle\mathbb{P}(Z>r)$
$\displaystyle\leq\mathbb{P}(|\mathcal{J}_{a}|>s)+\mathbb{P}\Biggl{(}\sum_{j=1}^{s}\bigl{(}|X|_{(p-j+1)}^{2}-1\bigr{)}>r\Biggr{)}$
$\displaystyle\leq\mathbb{P}(|\mathcal{J}_{a}|>s)+\sum_{j=1}^{s}\mathbb{P}\biggl{(}|X|_{(p-j+1)}>K\log^{1/\alpha}\Bigl{(}\frac{4ep}{\varepsilon
j}\Bigr{)}\biggr{)}$
$\displaystyle\leq\Bigl{(}\frac{ep}{s}\Bigr{)}^{s}\Biggl{\\{}2\exp\biggl{\\{}-\Bigl{(}\frac{a}{K}\Bigr{)}^{\alpha}\biggr{\\}}\Biggr{\\}}^{s}+\sum_{j=1}^{s}\Bigl{(}\frac{ep}{j}\Bigr{)}^{j}\Biggl{\\{}2\exp\biggl{\\{}-\biggl{(}\frac{K\log^{1/\alpha}\bigl{(}\frac{4ep}{\varepsilon
j}\bigr{)}}{K}\biggr{)}^{\alpha}\biggr{\\}}\Biggr{\\}}^{j}$
$\displaystyle\leq(\varepsilon/2)^{s}+\sum_{j=1}^{s}(\varepsilon/2)^{j}\leq\varepsilon.$

(b) Note that $q_{x}\leq(K/a)^{\alpha}$ by Chebyshev’s inequality. We now
observe that

$\sum_{j=1}^{s}K^{2}\Bigl{(}\frac{2ep}{\varepsilon j}\Bigr{)}^{2/\alpha}\leq
K^{2}\Bigl{(}\frac{2ep}{\varepsilon}\Bigr{)}^{2/\alpha}\biggl{\\{}1+\int_{1}^{s}x^{-2/\alpha}\,dx\biggr{\\}}\leq\frac{\alpha-2}{\alpha}K^{2}s\Bigl{(}\frac{2ep}{\varepsilon
s}\Bigr{)}^{2/\alpha}=r$

The rest then follows from the proof for part (a).
(c) By a union bound and the proof for the previous parts, we have

$\displaystyle\mathbb{P}\bigl{(}\max_{s\in[p]}Z_{s}/r_{s}>1\bigr{)}$
$\displaystyle\leq\Biggl{(}\sum_{s=1}^{p}\mathbb{P}(|\mathcal{J}_{a(s)}|>s)\Biggr{)}+\mathbb{P}\Biggl{(}\max_{s\in[p]}\frac{\sum_{j=1}^{s}\bigl{(}|X|_{(p-j+1)}^{2}-1\bigr{)}}{r_{s}}>1\Biggr{)}$
$\displaystyle\leq\sum_{s=1}^{p}(\varepsilon/2)^{s}+\sum_{j=1}^{p}\mathbb{P}\biggl{(}|X|_{(p-j+1)}>K\Bigl{(}\frac{2ep}{\varepsilon
j}\Bigr{)}^{2/\alpha}\biggr{)}$
$\displaystyle\leq\sum_{s=1}^{p}(\varepsilon/2)^{s}+\sum_{j=1}^{p}(\varepsilon/2)^{j}\leq
2\varepsilon.$

∎

######  Lemma 18.

Let $\gamma>0$. Then, for all $x\geq(2^{\gamma}-1)^{-1/\gamma}$ we have

$\sum_{i=0}^{\infty}\exp\bigl{\\{}-(x2^{i})^{\gamma}\bigr{\\}}\leq
2\exp(-x^{\gamma}).$

###### Proof.

By the convexity of $y\mapsto 2^{\gamma y}$, we have that
$2^{(i+1)\gamma}-2^{i\gamma}\geq 2^{i\gamma}-2^{(i-1)\gamma}$ and thus

$2^{i\gamma}=1+\sum_{j=1}^{i}(2^{j\gamma}-2^{(j-1)\gamma})\geq
1+i(2^{\gamma}-1).$

for all $i\in\mathbb{N}$. Denote $\tilde{x}:=\exp(x^{\gamma})$. We hence
deduce that when $\tilde{x}>2^{\frac{1}{2^{\gamma}-1}}$,

$\sum_{i=0}^{\infty}\exp\bigl{\\{}-(x2^{i})^{\gamma}\bigr{\\}}=\sum_{i=0}^{\infty}\tilde{x}^{-2^{i\gamma}}\leq\sum_{i=0}^{\infty}\tilde{x}^{-1-i(2^{\gamma}-1)}=\frac{1}{\tilde{x}\bigl{(}1-\tilde{x}^{-(2^{\gamma}-1)}\bigr{)}}\leq
2\tilde{x}^{-1}.$

∎

######  Lemma 19.

Let $Z_{1},\dotsc,Z_{n}$ be independent mean zero random variables.
(a) Assume that there exists $C>0$ such that $\mathbb{E}Z_{i}^{4}\leq C$ for
all $i\in[n]$. Then for any $v=(v_{1},\dotsc,v_{n})^{\top}\in\mathbb{R}^{n}$,
we have

$\mathbb{E}\biggl{[}\Bigl{(}\sum_{i=1}^{n}v_{i}Z_{i}\Bigr{)}^{4}\biggr{]}\leq
3C\|v\|_{2}^{4}.$

(b) Assume that there exists $C>0$ such that
$\mathbb{E}\bigl{(}|Z_{i}|^{2k}\bigr{)}\leq C$ for some $k\geq 1$. Then, there
exists a constant $C_{k}>0$, depending only on $k$ and $C$ such that

$\mathbb{E}\biggl{[}\Big{|}\sum_{i=1}^{n}Z_{i}/n\Big{|}^{2k}\biggr{]}\leq
C_{k}n^{-k}.$

###### Proof.

(a) Since $\mathbb{E}Z_{i}^{0}=1$ and $\mathbb{E}Z_{i}^{1}=0$ for all
$i\in[n]$, we have

$\displaystyle\mathbb{E}\biggl{[}\Bigl{(}\sum_{i=1}^{n}v_{i}Z_{i}\Bigr{)}^{4}\biggr{]}$
$\displaystyle=\sum_{i=1}^{n}v_{i}^{4}\mathbb{E}Z_{i}^{4}+\sum_{1\leq i<j\leq
n}6v_{i}^{2}v_{j}^{2}\mathbb{E}(Z_{i}^{2}Z_{j}^{2})\leq
C\Bigl{(}\sum_{i=1}^{n}v_{i}^{4}+\sum_{1\leq i<j\leq
n}6v_{i}^{2}v_{j}^{2}\Bigr{)}$ $\displaystyle\leq
3C\Bigl{(}\sum_{i=1}^{n}v_{i}^{2}\Bigr{)}^{2},$

where the first inequality follows from Jensen’s inequality.
(b) Note that $S_{j}:=\sum_{i=1}^{j}Z_{i}$ is a martingale (adapted to the
natural filtration) and $[S]_{j}:=\sum_{i=1}^{j}Z_{i}^{2}$ can be viewed as
the quadratic variation of this martingale. By Burkholder–Davis–Gundy
inequality (e.g. Beiglböck and Siorpaes, 2015, Theorem 1.1), we have for any
$k\geq 1$,

$\mathbb{E}\bigl{[}|S_{n}|^{2k}\bigr{]}\leq\mathbb{E}\biggl{[}\Bigl{(}\max_{j\leq
n}|S_{j}|\Bigr{)}^{2k}\biggr{]}\leq
C_{k,1}\mathbb{E}\Bigl{[}\bigl{(}[S]_{n}\bigr{)}^{k}\Bigr{]},$

for some constant $C_{k,1}>0$, depending only on $k$. Thus, we have

$\mathbb{E}\biggl{[}\Big{|}\sum_{i=1}^{n}Z_{i}/n\Big{|}^{2k}\biggr{]}\leq\frac{C_{k,1}}{n^{2k}}\mathbb{E}\biggl{[}\Big{(}\sum_{i=1}^{n}Z_{i}^{2}\Big{)}^{k}\biggr{]}\leq\frac{C_{k,1}}{n^{k}}\mathbb{E}\bigg{[}\frac{\sum_{i=1}^{n}|Z_{i}|^{2k}}{n}\bigg{]}\leq\frac{CC_{k,1}}{n^{k}},$

where we have used Jensen’s inequality in the second inequality. ∎

######  Lemma 20.

Let $k\geq 1$ and $V_{1},\dotsc,V_{L}$ be independent random vectors in
$\mathbb{R}^{p}$, each having zero mean and independent coordinates. Assume
that there exists $C>0$ such that
$\mathbb{E}\bigl{[}|V_{i}(j)|^{2k}\bigr{]}\leq C$ for all $i\in[L]$ and
$j\in[p]$. Denote $\overline{V}:=\sum_{i=1}^{L}V_{i}/L$. Then for any
$\delta\in(0,1)$, we have

$\mathbb{P}\Bigg{(}\bigg{|}\sum_{j=1}^{p}L\bigl{(}\overline{V}^{2}(j)-1/L\bigr{)}\bigg{|}>C_{k}\frac{p^{\frac{1}{2}\vee\frac{1}{k}}}{\delta^{1/k}}\Bigg{)}\leq\delta$

for some constant $C_{k}>0$, depending only on $C$ and $k$.

###### Proof.

We first prove the result for $1\leq k\leq 2$. Note that for any $\eta>0$

$\mathbb{P}\bigg{(}\bigg{|}\sum_{j=1}^{p}L\bigl{(}\overline{V}^{2}(j)-1/L\bigr{)}\bigg{|}>\eta\bigg{)}\leq
p\mathbb{P}\Bigl{(}\bigl{|}L\bigl{(}\overline{V}^{2}(1)-1/L\bigr{)}\bigr{|}>\eta\Bigr{)}\\\
+\mathbb{P}\bigg{(}\bigg{|}\sum_{j=1}^{p}L\bigl{(}\overline{V}^{2}(j)-1/L\bigr{)}\mathds{1}\Bigl{\\{}\bigl{|}L\bigl{(}\overline{V}^{2}(j)-1/L\bigr{)}\bigr{|}\leq\eta\Bigr{\\}}\bigg{|}>\eta\bigg{)}.$
(78)

We control the two terms separately. For the first term, we have

$\mathbb{P}\Bigl{(}\bigl{|}L\bigl{(}\overline{V}^{2}(1)-1/L\bigr{)}\bigr{|}>\eta\Bigr{)}\leq\frac{\mathbb{E}\Bigl{[}\bigl{|}L\overline{V}^{2}(1)-1\bigr{|}^{k}\Bigr{]}}{\eta^{k}}\leq\frac{2^{k-1}\Bigl{(}\mathbb{E}\bigl{|}L\overline{V}^{2}(1)\bigr{|}^{k}+1\Bigr{)}}{\eta^{k}}\leq\frac{2^{k-1}(C_{0,k}+1)}{\eta^{k}},$
(79)

where the three inequalities follow, respectively, from Markov’s inequality,
Jensen’s inequality and Lemma 19(b), with $C_{0,k}$ being the constant that
depends only on $C$ and $k$ in that lemma. For convenience, we denote
$C_{1,k}:=2^{k-1}(C_{0,k}+1)$ hereafter. For the second term in (78), we have

$\displaystyle\mathbb{P}\bigg{(}\bigg{|}\sum_{j=1}^{p}L\bigl{(}\overline{V}^{2}(j)-1/L\bigr{)}\mathds{1}\Big{\\{}\bigl{|}L(\overline{V}^{2}(j)-1/L)\bigr{|}\leq\eta\Big{\\}}\bigg{|}>\eta\bigg{)}$
$\displaystyle\leq\frac{1}{\eta^{2}}\Bigg{\\{}p\mathbb{E}\bigg{[}\bigl{(}L\overline{V}^{2}(1)-1\bigr{)}^{2}\mathds{1}\Big{\\{}\bigl{|}L(\overline{V}^{2}(1)-1/L)\bigr{|}\leq\eta\Big{\\}}\bigg{]}$
$\displaystyle\qquad\quad+p^{2}\bigg{(}\mathbb{E}\bigg{[}L\bigl{(}\overline{V}^{2}(1)-1/L\bigr{)}\mathds{1}\Big{\\{}\bigl{|}L(\overline{V}^{2}(1)-1/L)\bigr{|}>\eta\Big{\\}}\bigg{]}\bigg{)}^{2}\Bigg{\\}}$
$\displaystyle\leq\frac{p}{\eta^{2}}\mathbb{E}\Big{[}\bigr{|}L\overline{V}^{2}(1)-1\bigr{|}^{k}\eta^{2-k}\Big{]}+\frac{p^{2}}{\eta^{2}}\bigg{\\{}\mathbb{E}\Big{[}\bigl{|}L\overline{V}^{2}(1)-1\bigr{|}^{k}\Big{]}\bigg{\\}}^{2/k}\bigg{\\{}\mathbb{P}\Big{(}\bigl{|}L\bigl{(}\overline{V}^{2}(1)-1/L\bigr{)}\bigr{|}>\eta\Big{)}\bigg{\\}}^{2(k-1)/k}$
$\displaystyle\leq\frac{C_{1,k}p}{\eta^{k}}+\frac{C_{1,k}^{2/k}p^{2}}{\eta^{2}}\bigg{(}\frac{C_{1,k}}{\eta^{k}}\bigg{)}^{2(k-1)/k},$
(80)

where we have used Markov’s inequality for the first inequality, Hölder’s
inequality for the second one and (79) for the last one. Combining (78), (79)
and (B), we have

$\mathbb{P}\bigg{(}\bigg{|}\sum_{j=1}^{p}L\bigl{(}\overline{V}^{2}(j)-1/L\bigr{)}\bigg{|}>\eta\bigg{)}\leq\frac{2C_{1,k}p}{\eta^{k}}+\frac{C_{1,k}^{2}p^{2}}{\eta^{2k}}.$

Note that if $C_{1,k}p/\eta^{k}>1$, the bound above holds trivially. Therefore
we obtain

$\mathbb{P}\bigg{(}\sum_{j=1}^{p}L(\overline{V}^{2}(j)-1/L)>\eta\bigg{)}\leq\frac{3C_{1,k}p}{\eta^{k}},$

for any $\eta>0$, which is equivalent to the claimed bound.

For $k>2$, by Markov’s inequality, (79) and Lemma 19(b), there exists a
constant $C_{2,k}>0$, depending only on $k$ and $C$ such that

$\mathbb{P}\Bigl{(}\bigl{|}L\bigl{(}\overline{V}^{2}(1)-1/L\bigr{)}\bigr{|}>\eta\Bigr{)}\leq\frac{\mathbb{E}\bigg{[}\Big{|}\sum_{j=1}^{p}L\bigl{(}\overline{V}^{2}(j)-1/L\bigr{)}\Big{|}^{k}\bigg{]}}{\eta^{k}}\leq\frac{C_{2,k}p^{k/2}}{\eta^{k}},$

which proves the desired result.

∎

######  Lemma 21.

Let $n\in\mathbb{N}$ and $c\in\mathbb{R}$. Let
$a_{1},\dotsc,a_{n},b_{1},\dotsc,b_{n}$ be $2n$ real numbers. Suppose that
$a_{i}-b_{i}\leq c$ for all $i\in[n]$. Then

$\mathrm{median}(a_{1},\dotsc,a_{n})-\mathrm{median}(b_{1},\dotsc,b_{n})\leq
c.$

###### Proof.

We sort the two arrays respectively and obtain $a_{(1)}\leq\dotsc\leq a_{(n)}$
and $b_{(1)}\leq\dotsc\leq b_{(n)}$. We show that $a_{(i)}-b_{(i)}\leq c$ for
all $i\in[n]$. Indeed, there exists a set $\mathcal{I}_{i}\subseteq[n]$ with
$|\mathcal{I}_{i}|\geq i$ such that

$b_{(i)}=\max\\{b_{j}:j\in\mathcal{I}_{i}\\}\geq\max\\{a_{j}-c:j\in\mathcal{I}_{i}\\}\geq
a_{(i)}-c.$

The desired results follows by observing that the median is a convex
combination of the order statistics. ∎