###### Abstract

Many complex networks in the real world can be formulated as hypergraphs where
community detection has been widely used. However, the fundamental question of
whether communities exist or not in an observed hypergraph remains unclear.
The aim of the work is to tackle this important problem. Specifically, we
systematically study when a hypergraph with community structure can be
successfully distinguished from its Erdös-Rényi counterpart, and propose
concrete test statistics based on hypergraph cycles when the models are
distinguishable. For uniform hypergraphs, we show that the success of
hypergraph testing highly depends on the order of the average degree as well
as the signal to noise ratio. In addition, we obtain asymptotic distributions
of the proposed test statistics and analyze their power. Our results are
further extended to nonuniform hypergraphs in which a new test involving both
edge and hyperedge information is proposed. The novel aspect of our test is
that it is provably more powerful than the classic test involving only edge
information. Simulation and real data analysis support our theoretical
findings. The proofs rely on Janson’s contiguity theory ([32]) and a high-
moments driven asymptotic normality result by Gao and Wormald ([28]).

62G10,

05C80,

hypergraph, stochastic block model, hypothesis testing, contiguity,
$l$-cycle.,

###### keywords:

[class=AMS]

###### keywords:

Testing Community Structure for Hypergraphs

Mingao<EMAIL_ADDRESS>Ruiqi<EMAIL_ADDRESS>Yang<EMAIL_ADDRESS>Zuofeng Shang<EMAIL_ADDRESS>
t1Corresponding author. Supported by NSF CAREER Grant DMS-1554804.

t2Corresponding author. Supported by NSF DMS-1764280 and NSF DMS-1821157.

##  1 Introduction.

Community detection is a fundamental problem in network data analysis. For
instance, in social networks ([18, 30, 53]), protein to protein interactions
([14]), image segmentation ([49]), among others, many algorithms have been
developed for identifying community structure. Theoretical studies on
community detection have mostly been focusing on ordinary graph setting in
which each possible edge contains exactly two vertices (see [7, 3, 46, 53, 54,
27, 4]). One common assumption made in these references is the existence of
communities. Recently, a number of researchers have been devoted to testing
this assumption, e.g., [12, 34, 41, 10, 6, 25, 26, 51].

Real-world networks are usually more complex than ordinary graphs. Unlike
ordinary graphs where the data structure is typically unique, e.g., edges only
contain two vertices, _hypergraphs_ demonstrate a number of possibly
overlapping data structures. For instance, in coauthorship data ([17, 44, 47,
42]), the number of coauthors varies so that one cannot consider edges
consisting of two coauthors only. Instead, a new type of “edge,” called
_hyperedge_ , must be considered which allows the connectivity of arbitrarily
many coauthors. The complex structures of hypergraphs create new challenges in
both theoretical and methodological study. As far as we know, existing
hypergraph literature mostly focuses on community detection in algorithmic
aspects ([48, 13, 7, 46, 3, 22, 33, 35]). Only recently Ghoshdastidar and
Dukkipati [22, 23] provided a statistical study in which a spectral algorithm
based on adjacency tensor was proposed for identifying community structure and
asymptotic results were developed. Nonetheless, the important problem of
testing the existence of community structure in an observed hypergraph still
remains untreated.

In this paper, we aim to tackle the problem of testing community structure for
hypergraphs. We first consider the relatively simpler but widely useful
uniform hypergraphs in which each hyperedge consists of an equal number of
vertices. For instance, the (user, resource, annotation) structure in
folksonomy may be represented as a uniform hypergraph where each hyperedge
consists of three vertices ([29]); the (user, remote host, login time, logout
time) structure in the login-data can be modeled as a uniform hypergraph where
each hyperedge contains four vertices ([24]); the point-set matching problem
is usually formulated as identifying a strongly connected component in a
uniform hypergraph ([13]). We provide various theoretical or methodological
studies ranging from dense uniform hypergraphs to sparse ones and investigate
the possibility of a successful test in each scenario. Our testing results in
the dense case are then extended to the more general nonuniform hypergraph
setting, in which a new test statistic involving both edge and hyperedge is
proposed. One important finding is that our new test is more powerful than the
classic one involving edge information only, which is an advantage of using
hyperedge information to boost the testing performance.

###  1.1 Review of Hypergraph Model And Relevant Literature.

In this section, we review some basic notion in hypergraphs and recent
progress in literature. Let us first review the notion of the uniform
hypergraph. An $m$-uniform hypergraph
$\mathcal{H}_{m}=(\mathcal{V},\mathcal{E})$ consists of a vertex set
$\mathcal{V}$ and a hyperedge set $\mathcal{E}$, where each hyperedge in
$\mathcal{E}$ is a subset of $\mathcal{V}$ consisting of exactly $m$ vertices.
Two hyperedges are the same if they are equal as vertex sets. An $l$-cycle in
$\mathcal{H}_{m}$ is a cyclic ordering $\\{v_{1},v_{2},\ldots,v_{r}\\}$ of a
subset of the vertex set with hyperedges like
$\\{v_{i},v_{i+1},\ldots,v_{i+m-1}\\}$ and any two adjacent hyperedges have
exactly $l$ common vertices. An $l$-cycle is loose if $l=1$ and tight if
$l=m-1$. To better illustrate the notion, consider a $3$-uniform hypergraph
$\mathcal{H}_{3}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\\}$,
$\mathcal{E}=\\{(v_{i},v_{j},v_{l})|1\leq i<j<l\leq 7\\}$. Then
$(\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\},\\{(v_{1},v_{2},v_{3}),(v_{3},v_{4},v_{5}),(v_{5},v_{6},v_{1})\\})$
is a loose cycle and
$(\\{v_{1},v_{2},v_{3},v_{4}\\},\\{(v_{1},v_{2},v_{3}),(v_{2},v_{3},v_{4}),(v_{3},v_{4},v_{1}),(v_{4},v_{1},v_{2})\\})$
is a tight cycle (see Figure 1).

$v_{3}$$v_{4}$$v_{5}$$v_{2}$$v_{6}$$v_{1}$$E_{2}$$E_{1}$$E_{3}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$E_{1}$$E_{2}$$E_{3}$$E_{4}$

Figure 1: Left: a loose cycle of three edges $E_{1},E_{2},E_{3}$. Right: a
tight cycle of four edges $E_{1},E_{2},E_{3},E_{4}$. Both cycles are subgraphs
of the $3$-uniform hypergraph $\mathcal{H}_{3}(\mathcal{V},\mathcal{E})$.

Next, let us review uniform hypergraphs with a planted partitioning structure,
also known as stochastic block model (SBM). For any positive integers $n,m,k$
with $m,k\geq 2$, and positive sequences $0<q_{n}<p_{n}<1$ (possibly depending
on $n$), let $\mathcal{H}_{m}^{k}(n,p_{n},q_{n})$ denote a $m$-uniform
hypergraph of $n$ vertices and $k$ balanced communities, in which $p_{n}$
($q_{n}$) represents the hyperedge probability within (between) communities.
More explicitly, any vertex $i\in[n]\equiv\\{1,2,\dots,n\\}$ is assigned,
independently and uniformly at random, a label
$\sigma_{i}\in[k]\equiv\\{1,2,\dots,k\\}$, and then each possible hyperedge
$(i_{1},i_{2},\dots,i_{m})$ is included with probability $p_{n}$ if
$\sigma_{i_{1}}=\sigma_{i_{2}}=\dots=\sigma_{i_{m}}$ and with probability
$q_{n}$ otherwise. In particular, $\mathcal{H}_{2}^{2}(n,p_{n},q_{n})$ (with
$m=k=2$) reduces to the ordinary bisection stochastic block models considered
by [39, 51]. Let $A\in\\{0,1\\}^{\tiny\underbrace{n\times n\times\dots\times
n}_{m}}$ denote the symmetric adjacency tensor of order $m$ associated with
$\mathcal{H}_{m}^{k}(n,p_{n},q_{n})$. By symmetry we mean that
$A_{i_{1}i_{2}\dots i_{m}}=A_{\psi(i_{1})\psi(i_{2})\dots\psi(i_{m})}$ for any
permutation $\psi$ of $(i_{1},i_{2},\dots,i_{m})$. For convenience, assume
$A_{i_{1}i_{2}\dots i_{m}}=0$ if $i_{s}=i_{t}$ for some distinct
$s,t\in\\{1,2,\dots,m\\}$, i.e., the hypergraph has no self-loops. Conditional
on $\sigma_{1},\ldots,\sigma_{n}$, the $A_{i_{1}i_{2}\dots i_{m}}$’s, with
$i_{1},\ldots,i_{m}$ pairwise distinct, are assumed to be independent
following the distribution below:

$\mathbb{P}(A_{i_{1}i_{2}\dots i_{m}}=1|\sigma)=p_{i_{1}i_{2}\dots
i_{m}}(\sigma),\ \mathbb{P}(A_{i_{1}i_{2}\dots
i_{m}}=0|\sigma)=q_{i_{1}i_{2}\dots i_{m}}(\sigma),$ (1)

where $\sigma=(\sigma_{1},\ldots,\sigma_{n})$,

$p_{i_{1}i_{2}\dots
i_{m}}(\sigma)=\left\\{\begin{array}[]{cc}p_{n},&\sigma_{i_{1}}=\dots=\sigma_{i_{m}}\\\
q_{n},&\textrm{otherwise}\end{array}\right.,\ \ q_{i_{1}i_{2}\dots
i_{m}}(\sigma)=1-p_{i_{1}i_{2}\dots i_{m}}(\sigma).$

In other words, each possible hyperedge $(i_{1},\ldots,i_{m})$ is included
with probability $p_{n}$ if the vertices $i_{1},\ldots,i_{m}$ belong to the
same community, and with probability $q_{n}$ otherwise. Let
$\mathcal{H}_{m}(n,\frac{p_{n}+(k^{m-1}-1)q_{n}}{k^{m-1}})$ denote the
$m$-uniform hypergraph without community structure, i.e., an Erdös-Rényi model
in which each possible hyperedge is included with common probability
$\frac{p_{n}+(k^{m-1}-1)q_{n}}{k^{m-1}}$. We consider such a special choice of
hyperedge probability in order to make the model have the same average degree
as $\mathcal{H}_{m}^{k}(n,p_{n},q_{n})$. In particular,
$\mathcal{H}_{2}(n,\frac{p_{n}+(k-1)q_{n}}{k})$ with $m=2$ becomes the
traditional Erdös-Rényi model that has been well studied in ordinary graph
literature; see [8, 9, 20, 16, 50]. Nonuniform hypergraphs can be simply
viewed as a superposition of uniform ones; see Section 3.

Given an observed adjacency tensor $A$, does $A$ represent a hypergraph that
exhibits community structure? In the present setting, this problem can be
formulated as testing the following hypothesis:

$H_{0}:A\sim\mathcal{H}_{m}\Big{(}n,\frac{p_{n}+(k^{m-1}-1)q_{n}}{k^{m-1}}\Big{)}\
\ vs.\ \ H_{1}:A\sim\mathcal{H}_{m}^{k}\Big{(}n,p_{n},q_{n}\Big{)}.$ (2)

When $m=k=2$, problem (2) has been well studied in the literature.
Specifically, for extremely sparse scenario $p_{n}\asymp q_{n}\ll n^{-1}$,
[39] show that $H_{0}$ and $H_{1}$ are always indistinguishable; for bounded
degree case $p_{n}\asymp q_{n}\asymp n^{-1}$, the two models are
distinguishable if and only if the signal-to-noise ratio (SNR) is greater than
1 ([39, 40, 51]); for dense scenario $p_{n}\asymp q_{n}\gg n^{-1}$, $H_{0}$
and $H_{1}$ are always distinguishable and a number of algorithms have been
developed (see [34, 25, 26, 10, 2, 12]). When $m=2$ and $k\geq 3$, the above
statements remain true for extremely sparse and dense scenarios; but for
bounded degree scenario, SNR$>1$ is only a sufficient condition for
successfully distinguishing $H_{0}$ from $H_{1}$ while a necessary condition
remains an open problem (see [2, 11, 52]). Abbe ([1]) provides a comprehensive
review of the recent development in this field. From the best of our
knowledge, there is a lack of literature dealing with the testing problem (2)
for general $m$. The literature on hypergraph analysis mainly focused on
community detection (see [5, 22, 23, 48, 13, 21, 33, 35, 38]).

###  1.2 Our Contributions.

The aim of this paper is to provide a study on hypergraph testing under a
spectrum of hyperedge probability scenarios. Our results consist of four major
parts. Section 2.1 deals with the extremely sparse scenario $p_{n}\asymp
q_{n}\ll n^{-m+1}$, in which we show that $H_{0}$ and $H_{1}$ are always
indistinguishable in the sense of contiguity. Section 2.2 deals with bounded
degree case $p_{n}\asymp q_{n}\asymp n^{-m+1}$, in which we show that $H_{1}$
and $H_{0}$ are distinguishable if the SNR of uniform hypergraph is greater
than one, but indistinguishable if the SNR is below certain threshold. We also
construct a powerful test statistic in the former case based on counting the
“long loose cycles”. Section 2.3 deals with dense scenario $p_{n}\asymp
q_{n}\gg n^{-m+1}$. We propose a test based on counting the hyperedges,
$l$-hypervees, and $l$-hypertriangles with $l$ determined by the order of
$p_{n}$ (or $q_{n}$), and show that the power of the proposed test approaches
one as the number of vertices goes to infinity. In Section 3, we extend some
of the previous results to nonuniform hypergraph testing. We propose a new
test involving both edge and hyperedge information and show that it is
generally more powerful than the classic test using edge information only (see
Remark 3.1). The results of the present paper can be viewed as nontrivial
extensions of the ordinary graph testing results such as [39, 40, 25]. Section
4 provides numerical studies to support our theory. Possible extensions are
discussed in Section 5 and proof of the main results are collected in Section
6.

Figure 2 displays a phase transition phenomenon in the special 3-uniform
hypergraph, based on our results in Sections 2.1 and 2.3. We find that $H_{0}$
and $H_{1}$ are indistinguishable if the hyperedge probabilities satisfy
$p_{n},q_{n}=o(n^{-2})$ (see red zone), and are distinguishable if $n^{-2}\ll
p_{n},q_{n}\ll n^{-5/3}$ (see green shaded zone). The spectral algorithm
proposed by [23] is able to detect communities if $p_{n},q_{n}\gg
n^{-2}(\log{n})^{2}$, which is improved to $p_{n},q_{n}\gg n^{-2}\log{n}$ in
[35] (see orange shaded zone). The white zone indicates unknown results. There
is clearly a region covered by the green shaded zone but not by the orange
one, which indicates that a successful test is possible even when the spectral
detection algorithm may fail. This demonstrates a substantial distinction
between the two problems. Similar phenomenon hold for higher-order uniform
hypergraphs.

Figure 2: Phase transition for 3-uniform hypergraph.

##  2 Main Results.

In this section, we present our main results in three parts depending on the
sparsity of the network. The contiguity theory for the extremely sparse case
is summarized in Section 2.1, followed by the contiguity and orthogonality
result for the bounded degree case in Section 2.2. In Section 2.3, we
construct a powerful test by counting the hyperedges, $l$-hypervees, and
$l$-hypertriangles for the dense case.

###  2.1 A Contiguity Theory for Extremely Sparse Case.

In this section, we consider the testing problem (2) with $p_{n}\asymp
q_{n}\ll n^{-m+1}$, i.e., the hyperedge probability of the hypergraph is
extremely low. For technical convenience, we only consider
$p_{n}=\frac{a}{n^{\alpha}}$ and $q_{n}=\frac{b}{n^{\alpha}}$ with constants
$a>b>0$ and $\alpha>m-1$. The results in this section may be extended to
general orders of $p_{n}$ and $q_{n}$ with more cumbersome arguments. We will
show that no test can successfully distinguish $H_{0}$ from $H_{1}$ in such a
situation. The proof proceeds by showing that the probability measures
associated with $H_{0}$ and $H_{1}$ are contiguous (see Theorem 2.1). We
remark that contiguity has also been used to prove indistinguishability for
ordinary graphs (see [39, 40]).

Let $\mathbb{P}_{n}$ and $\mathbb{Q}_{n}$ be sequences of probability measures
on a common probability space $(\Omega_{n},\mathcal{F}_{n})$. We say that
$\mathbb{P}_{n}$ and $\mathbb{Q}_{n}$ are mutually contiguous if for every
sequence of measurable sets $A_{n}\subset\Omega_{n}$,
$\mathbb{P}_{n}(A_{n})\rightarrow 0$ if and only if
$\mathbb{Q}_{n}(A_{n})\rightarrow 0$ as $n\rightarrow\infty$. They are said to
be orthogonal if there exists a sequence of measurable sets $A_{n}$ such that
$\mathbb{P}_{n}(A_{n})\rightarrow 0$ and $\mathbb{Q}_{n}(A_{n})\rightarrow 1$
as $n\rightarrow\infty$. According to [39], two probability models are
indistinguishable if their associated probability measures are mutually
contiguous, and two probability models are distinguishable if their associated
probability measures are orthogonal. The following theorem shows that $H_{0}$
and $H_{1}$ are indistinguishable.

######  Theorem 2.1.

If $\alpha>m-1$ and $a>b>0$ are fixed constants, then the probability measures
associated with $H_{0}$ and $H_{1}$ are mutually contiguous.

The proof of Theorem 2.1 proceeds by showing that the ratio of the likelihood
function of $H_{1}$ over $H_{0}$ converges in distribution to 1 under $H_{0}$,
which implies the contiguity of $H_{1}$ and $H_{0}$ ([32]). Theorem 2.1 says
that the hypergraphs in $H_{0}$ and $H_{1}$ are indistinguishable, hence, no
test can successfully separate the two hypotheses. One intuitive explanation
is that when $\alpha>m-1$, the average degree of both hypergraph models
converges to zero. To see this, the average degree is

$\binom{n}{m-1}\frac{a+(k^{m-1}-1)b}{k^{m-1}n^{\alpha}},$ (3)

which goes to zero as $n\rightarrow\infty$ if $\alpha>m-1$. Therefore, the
signals in both models are not strong enough to support a successful test. It
is easy to see that the average degree becomes bounded when $\alpha=m-1$ which
will be investigated in the next section.

###  2.2 Bounded Degree Case.

In this section, we consider $p_{n}\asymp q_{n}\asymp n^{-m+1}$ which leads to
bounded average degrees for the models in $H_{0}$ and $H_{1}$; see (3). For
convenience, let us denote $p_{n}=\frac{a}{n^{m-1}}$ and
$q_{n}=\frac{b}{n^{m-1}}$ for fixed $a>b>0$. Define the signal to noise ratio
(SNR) as

$\kappa=\frac{(a-b)^{2}}{k^{m-1}(m-2)![a+(k^{m-1}-1)b]}.$ (4)

When $m=k=2$, it is easy to check that $\kappa=\frac{(a-b)^{2}}{2(a+b)}$ which
becomes the classic SNR of ordinary stochastic block models considered by
[39]. Hence, it is reasonable to view $\kappa$ defined in (4) as a
generalization of the classic SNR to the hypergraph model
$\mathcal{H}_{m}^{k}(n,\frac{a}{n^{m-1}},\frac{b}{n^{m-1}})$. Like the classic
SNR, the value of $\kappa$ characterizes the separability between communities.
Intuitively, when $\kappa$ is large which means that the communities are very
different, the testing problem (2) becomes simpler. The following result says
that when $\kappa>1$ successful testing becomes possible.

######  Theorem 2.2.

Suppose that $a>b>0$ are fixed constants, $m,k\geq 2$. If $\kappa>1$, then the
probability measures associated with $H_{0}$ and $H_{1}$ are orthogonal.

We prove Theorem 2.2 by constructing a sequence of events dependent on the
number of long loose cycles and showing that the probabilities of the events
converge to 1 (or 0) under $H_{0}$ (or $H_{1}$), based on the high moments
driven asymptotic normality theorem from Gao and Wormald ([28]). Theorem 2.2
says that it is possible to distinguish the hypotheses $H_{0}$ and $H_{1}$
provided that $\kappa>1$. Abbe and Sandon [2] obtained relevant results in the
ordinary graph setting, i.e., $m=2$ and $k\geq 2$ in our case; see Corollary
2.8 therein which states that community detection in polynomial time becomes
possible if SNR$>1$. Whereas Theorem 2.2 holds for arbitrary $m,k\geq 2$.
Hence our result can be viewed as an extension of [2] to hypergraph setting.

Let us now propose a test statistic based on “long loose cycles” that can
successfully distinguish $H_{0}$ and $H_{1}$ when $\kappa>1$. Let $k_{n}$ be a
sequence diverging along with $n$. Let $X_{k_{n}}$ be the number of loose
cycles each consisting of exactly $k_{n}$ edges. Define

$\mu_{n0}=\frac{\lambda_{m}^{k_{n}}}{2k_{n}},\,\,\,\,\mu_{n1}=\mu_{n0}+\frac{k-1}{2k_{n}}\Big{[}\frac{a-b}{k^{m-1}(m-2)!}\Big{]}^{k_{n}},$

where $\lambda_{m}=\frac{a+(k^{m-1}-1)b}{{k}^{m-1}(m-2)!}$ for any $m\geq 2$.
Note that when $m=2$, $\lambda_{m}=\frac{a+(k-1)b}{k}$ is the average degree
[11]. Let $\mathbb{P}_{H_{1}}$ denote the probability measure induced by $A$
under $H_{1}$. We have the following theorem about the asymptotic property of
$X_{k_{n}}$.

######  Theorem 2.3.

Suppose $\kappa>1$ and $1\ll
k_{n}\leq\delta_{0}\log_{\lambda_{m}}\log_{\gamma}n$, where $\gamma>1$ and
$0<\delta_{0}<2$ are constants. Then, under $H_{l}$ for $l=0,1$,
$\frac{X_{k_{n}}-\mu_{nl}}{\sqrt{\mu_{nl}}}\overset{d}{\to}N(0,1)$ as
$n\to\infty$. Furthermore, for any constant $C>0$,
$\mathbb{P}_{H_{1}}\left(\big{|}\frac{X_{k_{n}}-\mu_{n0}}{\sqrt{\mu_{n0}}}\big{|}>C\right)\rightarrow
1$ as $n\to\infty$.

The proof is based on the asymptotic normality theory developed by [28].
According to Theorem 2.3, we propose the following test statistic

$T_{k_{n}}=\frac{X_{k_{n}}-\mu_{n0}}{\sqrt{\mu_{n0}}}.$

We remark that computation of $T_{k_{n}}$ is typically in super-polynomial
time since it requires to find $X_{k_{n}}$ which has complexity
$n^{O(k_{n})}$. By Theorem 2.3, $T_{k_{n}}\overset{d}{\to}N(0,1)$ under
$H_{0}$. Hence, we construct the following testing rule at significance level
$\alpha\in(0,1)$:

$\textrm{reject $H_{0}$ if and only if $|T_{k_{n}}|>z_{\alpha/2}$},$

where $z_{\alpha/2}$ is the $(1-\alpha/2)$-quantile of $N(0,1)$. It follows by
Theorem 2.3 that $\mathbb{P}_{H_{1}}(|T_{k_{n}}|>z_{\alpha/2})\to 1$, i.e.,
the power of $T_{k_{n}}$ approaches one when $\kappa>1$.

Theorem 2.3 requires $k_{n}\to\infty$ and to grow slower than an iterative
logarithmic order. This is due to the use of [28] which requires $k_{n}$ to
diverge with $k_{n}\lambda_{m}^{k_{n}}=o(\log n)$. In practice, we suggest
choosing $k_{n}=\lfloor\delta_{0}\log_{\lambda_{m}}\log_{\gamma}n\rfloor$ with
$\gamma$ close to 1 and $\delta_{0}$ close to 2. Such $\gamma$ and
$\delta_{0}$ will make $k_{n}$ suitably large so that the test statistic
$T_{k_{n}}$ becomes valid. For instance, Table 1 demonstrates the values of
$k_{n}$ along with $n$ with $\delta_{0}=1.99$, $\gamma=1.01$,
$\lambda_{m}=10$. We can see that, for a moderate range of $n$, the values of
$k_{n}$ are sufficiently large to make the test valid.

Desirable $k_{n}$ | 3 | 4 | 5 | 6
---|---|---|---|---
Minimal $n$ | 2 | 3 | 25 | 29786
Table 1: Minimal $n$ to achieve a desirable value of $k_{n}$.

It should be mentioned that the calculation of $T_{k_{n}}$ requires known
values of $a$ and $b$. When $a$ and $b$ are unknown, motivated by the ordinary
graph ([39]), they can be estimated as follows. Define

$\widehat{\lambda}_{m}=\frac{n^{m-1}|\mathcal{E}|}{(m-2)!\binom{n}{m}},\ \
\widehat{f}=(2k_{n}X_{k_{n}}-\widehat{\lambda}_{m}^{k_{n}})^{\frac{1}{k_{n}}},$

where $|\mathcal{E}|$ is the number of observed hyperedges and $X_{k_{n}}$ is
the number of loose cycles of length $k_{n}$. Let
$\widehat{a}_{n}=(m-2)!\Big{[}\widehat{\lambda}_{m}+(k^{m-1}-1)(k-1)^{-\frac{1}{k_{n}}}\widehat{f}\Big{]}$
and
$\widehat{b}_{n}=(m-2)!\Big{[}\widehat{\lambda}_{m}-(k-1)^{-\frac{1}{k_{n}}}\widehat{f}\Big{]}$.
The following theorem says that $\widehat{a}_{n}$ and $\widehat{b}_{n}$ are
consistent estimators of $a$ and $b$, respectively.

######  Theorem 2.4.

Suppose $\kappa>1$ and $k_{n}$ satisfies the condition in Theorem 2.3. Then
$\widehat{a}_{n}\to a$ and $\widehat{b}_{n}\to b$ in probability.

Another interesting question is to investigate for what values of $\kappa$ a
successful test becomes impossible. When $m=k=2$, [39] showed that no test can
successfully distinguish $H_{0}$ from $H_{1}$ provided $\kappa<1$; and
successful test becomes possible provided $\kappa>1$. It is substantially
challenging to obtain such a sharp result when $k$ becomes larger. For
instance, in the ordinary graph setting, [43] obtained a (nonsharp) condition
in terms of SNR when $k\geq 3$ under which successful test becomes impossible.
In Theorem 2.5 below, we address a similar question in the hypergraph setting.
For any integers $m\geq 3,k\geq 2$, define
$\tau_{1}(m,k)=\binom{m}{2}^{-1}\sum_{i=1}^{\lceil\frac{m}{2}-1\rceil}\frac{1}{k^{2i-1}}\binom{m}{i+2}$
and
$\tau_{2}(m,k)=1+\binom{m}{2}^{-1}\sum_{i=1}^{m-2}\frac{1}{k^{2i}}\binom{m}{i+2}$.
The quantities $\tau_{1}(m,k)$ and $\tau_{2}(m,k)$ will jointly characterize a
spectrum of $(m,k,\kappa)$ such that successful test does not exist.

######  Theorem 2.5.

Suppose that $m\geq 3,k\geq 2$ are integers satisfying $\tau_{1}(m,k)\leq 1$,
$a>b>0$ are fixed constants and $\alpha=m-1$. If

$0<\kappa<\frac{1}{\tau_{2}(m,k)(k^{2}-1)},$ (5)

then the probability measures associated with $H_{0}$ and $H_{1}$ are mutually
contiguous.

The proof of Theorem 2.5 relies on Janson’s contiguity theory ([32]). Theorem
2.5 says that when $\tau_{1}(m,k)\leq 1$ and $\kappa$ falls in the range (5),
there is no test that can successfully distinguish the hypotheses $H_{0}$ and
$H_{1}$. It should be emphasized that the condition $\tau_{1}(m,k)\leq 1$
holds for a broad range of pairs $(m,k)$. For instance, such condition holds
for any $k\geq 2$ and $3\leq m\leq 6$. To see this, for any $k\geq 2$,
$\tau_{1}(3,k)=\frac{1}{3k}<1$, $\tau_{1}(4,k)=\frac{2}{3k}<1$,
$\tau_{1}(5,k)=\frac{1}{k}+\frac{1}{2k^{3}}<1$ and
$\tau_{1}(6,k)=\frac{4}{3k}+\frac{1}{k^{3}}<1$. Note that $m\leq 6$ covers
most of the practical cases (see [23]).

Combining Theorems 2.5 and 2.2, it is still unknown whether $H_{0}$ and
$H_{1}$ are distinguishable when
$\frac{1}{\tau_{2}(m,k)(k^{2}-1)}\leq\kappa\leq 1$. One way to tackle this
might be to enhance Janson’s contiguity theory to efficiently handle
hypergraph models. We intend to leave this as one future topic.

###  2.3 A Powerful Test for Dense Uniform Hypergraph.

In this section, we consider the problem of testing community structure in
dense $m$-uniform hypergraphs with $p_{n}\asymp q_{n}\gg n^{-m+1}$. Our
approach is based on counting the hyperedges, $l$-hypervees, and
$l$-hypertriangles in the observed hypergraph. To make our test successful,
$l$ needs to be correctly selected according to the hyperedge probability of
the model. Under such correct selection, we derive asymptotic normality for
the test as well as analyze its power. We also comment the effect of
misspecified $l$ in Remark 2.1. Our method can be viewed as a generalization
of [25, 26] from ordinary graph testing. The substantially different nature of
the hypergraph cycles makes our generalization nontrivial.

For convenience, let us denote $p_{n}=\frac{a_{n}}{n^{m-1}}$ and
$q_{n}=\frac{b_{n}}{n^{m-1}}$ with diverging $a_{n},b_{n}$. Therefore, (2)
becomes the following hypothesis testing problem:

$H_{0}^{\prime}:A\sim\mathcal{H}_{m}\Big{(}n,\frac{a_{n}+(k^{m-1}-1)b_{n}}{k^{m-1}n^{m-1}}\Big{)}\
\ vs.\ \
H_{1}^{\prime}:A\sim\mathcal{H}_{m}^{k}\Big{(}n,\frac{a_{n}}{n^{m-1}},\frac{b_{n}}{n^{m-1}}\Big{)}.$
(6)

Throughout this section, we assume that there exists an integer $1\leq
l\leq\frac{m}{2}$ such that $n^{l-1}\ll a_{n}\asymp b_{n}\ll
n^{l-\frac{2}{3}}$. Note that model (6) allows $1\ll a_{n}\asymp b_{n}\ll
n^{1/3}$ (with $l=1$), compared with spectral algorithm ([23]) which requires
$a_{n}\gg(\log{n})^{2}$ or $a_{n}\gg\log{n}$ in [35].

We consider the following degree-corrected SBM which is more general than (1).
Let $\\{W_{i},i=1,\dots,n\\}$ be i.i.d. random variables with
$\mathbb{E}(W_{1}^{2})=1$ and $\mathbb{E}(W_{1})\neq 0$. Let
$\\{\sigma_{i},i=1,\dots,n\\}$ be i.i.d. random variables from multinomial
distribution Mult$(k,1,1/k)$. Assume that $W_{i}$’s and $\sigma_{i}$’s are
independent. Given $W_{i}$’s and $\sigma_{i}$’s, the $A_{i_{1}i_{2}\ldots
i_{m}}$’s, with pairwise distinct $i_{1},\ldots,i_{m}$, are conditional
independent satisfying

$\displaystyle\mathbb{P}(A_{i_{1}i_{2}\dots i_{m}}=1|W,\sigma)$
$\displaystyle=$ $\displaystyle W_{i_{1}}\dots W_{i_{m}}p_{i_{1}i_{2}\dots
i_{m}}(\sigma),$ (7) $\displaystyle\mathbb{P}(A_{i_{1}i_{2}\dots
i_{m}}=0|W,\sigma)$ $\displaystyle=$ $\displaystyle 1-W_{i_{1}}\dots
W_{i_{m}}p_{i_{1}i_{2}\dots i_{m}}(\sigma),$

where $W=(W_{1},\ldots,W_{n})$,

$p_{i_{1}i_{2}\dots
i_{m}}(\sigma)=\left\\{\begin{array}[]{cc}\frac{a_{n}}{n^{m-1}},&\sigma_{i_{1}}=\dots=\sigma_{i_{m}}\\\
\frac{b_{n}}{n^{m-1}},&\mbox{otherwise}\end{array}\right..\ \ $

We call (7) the degree-corrected SBM in hypergraph setting. The degree-
correction weights $W_{i}$’s can capture the degree inhomogeneity exhibited in
many social networks. When $m=2$, (7) reduces to the classical degree-
corrected SBM for ordinary graphs (see [54, 37, 27, 25]). For ordinary graphs,
[25] proposed a test through counting small subgraphs to distinguish the
degree-corrected SBM from an Erdös-Rényi model. In what follows, we generalize
their results to hypergraphs through counting small sub-hypergraphs including
hyperedges, $l$-hypervee, and $l$-hypertriangles, with definitions given
below.

######  Definition 2.1.

An $l$-hypervee consists of two hyperedges with $l$ common vertices. An
$l$-hypertriangle is an $l$-cycle consisting of three hyperedges.

For example, in Figure 3, the hyperedge set
$\\{(v_{1},v_{2},v_{3},v_{4}),(v_{3},v_{4},v_{5},v_{6})\\}$ is a 2-hypervee,
and
$\\{(v_{1},v_{2},v_{3},v_{4}),(v_{3},v_{4},v_{5},v_{6}),(v_{5},v_{6},v_{1},v_{2})\\}$
is a 2-hypertriangle.

$v_{3}$$v_{4}$$v_{5}$$v_{2}$$v_{6}$$v_{1}$$E_{2}$$E_{1}$

$v_{3}$$v_{4}$$v_{5}$$v_{2}$$v_{6}$$v_{1}$$E_{2}$$E_{1}$$E_{3}$

Figure 3: An example of hypervee (left) and hypertriangle (right) with two
common vertices between consecutive hyperedges.

Consider the following probabilities of hyperedge, hypervee and hypertriangle
in
$\mathcal{H}_{m}^{k}\Big{(}n,\frac{a_{n}}{n^{m-1}},\frac{a_{n}}{n^{m-1}}\Big{)}$:

$\displaystyle E$ $\displaystyle=$ $\displaystyle\mathbb{P}(A_{i_{1}i_{2}\dots
i_{m}}=1),$ $\displaystyle V$ $\displaystyle=$
$\displaystyle\mathbb{P}(A_{i_{1}i_{2}\dots i_{m}}A_{i_{m-l+1}\dots
i_{2m-l}}=1),$ $\displaystyle T$ $\displaystyle=$
$\displaystyle\mathbb{P}(A_{i_{1}i_{2}\dots i_{m}}A_{i_{m-l+1}\dots
i_{2m-l}}A_{i_{2m-2l+1}\dots i_{3(m-l)}i_{1}\dots i_{l}}=1).$

It follows from direct calculations that

$\displaystyle E$ $\displaystyle=$
$\displaystyle(\mathbb{E}W_{1})^{m}\frac{a_{n}+(k^{m-1}-1)b_{n}}{n^{m-1}k^{m-1}},$
$\displaystyle V$ $\displaystyle=$
$\displaystyle(\mathbb{E}W_{1})^{2(m-l)}\Bigg{(}\frac{(a_{n}-b_{n})^{2}}{n^{2(m-1)}k^{2m-l-1}}+\frac{2(a_{n}-b_{n})b_{n}}{n^{2(m-1)}k^{m-1}}+\frac{b_{n}^{2}}{n^{2(m-1)}}\Bigg{)},$
$\displaystyle T$ $\displaystyle=$
$\displaystyle(\mathbb{E}W_{1})^{3(m-2l)}\Bigg{(}\frac{(a_{n}-b_{n})^{3}}{n^{3(m-1)}k^{3(m-l)-1}}+\frac{3(a_{n}-b_{n})^{2}b_{n}}{n^{3(m-1)}k^{2m-l-1}}+\frac{3(a_{n}-b_{n})b_{n}^{2}}{n^{3(m-1)}k^{m-1}}+\frac{b_{n}^{3}}{n^{3(m-1)}}\Bigg{)}.$

Define $\mathcal{T}=T-\Big{(}\frac{V}{E}\Big{)}^{3}$. The following result
demonstrates a strong relationship between $\mathcal{T}$ and
$H_{0}^{\prime},H_{1}^{\prime}$.

######  Proposition 2.6.

Under $H_{0}^{\prime}$, $\mathcal{T}=0$. Moreover, if $\mathbb{E}W_{1}\neq 0$,
then under $H_{1}^{\prime}$, $\mathcal{T}\neq 0$.

Proposition 2.6 says that, if $\mathbb{E}W_{1}\neq 0$, then $H_{0}^{\prime}$
holds if and only if $\mathcal{T}=0$. Hence, it is reasonable to use an
empirical version of $\mathcal{T}$, namely, $\widehat{\mathcal{T}}$, as a test
statistic for (6).

Prior to constructing $\widehat{\mathcal{T}}$, let us introduce some notation.
For convenience, we use $i_{1}:i_{m}$ to represent the ordering
$i_{1}i_{2}\dots i_{m}$. Also define $C_{2m-l}(A)$ and $C_{3(m-l)}(A)$ for any
adjacency tensor $A$ as follows.

$\displaystyle C_{2m-l}(A)$ $\displaystyle=$ $\displaystyle
A_{i_{1}:i_{m}}A_{i_{m-l+1}:i_{2m-l}}+A_{i_{2}:i_{m+1}}A_{i_{m-l+2}:i_{2m-l}i_{1}}+\dots+A_{i_{2m-l}i_{1}:i_{m-1}}A_{i_{m-l}:i_{2m-l-1}},$
$\displaystyle C_{3(m-l)}(A)$ $\displaystyle=$ $\displaystyle
A_{i_{1}:i_{m}}A_{i_{m-l+1}:i_{2m-l}}A_{i_{2m-2l+1}:i_{3(m-l)}i_{1}:i_{l}}+A_{i_{2}:i_{m+1}}A_{i_{m-l+2}:i_{2m-l+1}}A_{i_{2m-2l+2}:i_{3(m-l)}i_{1}:i_{l+1}}$
$\displaystyle+\dots+A_{i_{m-l}:i_{2m-l-1}}A_{i_{2(m-l)}:i_{3(m-l)}i_{1}:i_{l-1}}A_{i_{3(m-l)}i_{1}:i_{m-1}}.$

Note that $C_{2m-l}(A)$ is the number of hypervees in the given vertex
ordering $i_{1}i_{2}\dots i_{2m-l}$, while $C_{3(m-l)}(A)$ counts the number
of hypertriangles in the given vertex ordering $i_{1}i_{2}\dots i_{3(m-l)}$.
Define $\widehat{E}$, $\widehat{V}$, $\widehat{T}$ as the empirical versions
of $E,V,T$:

$\widehat{E}=\frac{1}{\binom{n}{m}}\sum_{i\in
c(m,n)}A_{i_{1}:i_{m}},\widehat{V}=\frac{1}{\binom{n}{2m-l}}\sum_{i\in
c(2m-l,n)}\frac{C_{2m-l}(A)}{2m-l},\widehat{T}=\frac{1}{\binom{n}{3(m-l)}}\sum_{i\in
c(3(m-l),n)}\frac{C_{3(m-l)}(A)}{m-1},$ (8)

where, for any positive integers $s,t$, $c(s,t)=\\{(i_{1},\dots,i_{s}):1\leq
i_{1}<\dots<i_{s}\leq t\\}$. We have the following asymptotic normality
result.

######  Theorem 2.7.

Suppose $\mathbb{E}W_{1}^{4}=O(1)$, $\mathbb{E}W_{1}\neq 0$ and $n^{l-1}\ll
a_{n}\asymp b_{n}\ll n^{l-\frac{2}{3}}$ for some integer $1\leq
l\leq\frac{m}{2}$. Moreover, let

$\delta:=\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}}{\sqrt{T}}\Bigg{[}T-\Big{(}\frac{V}{E}\Big{)}^{3}\Bigg{]}\in[0,\infty).$
(9)

Then we have, as $n\to\infty$,

$\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}\Big{[}\widehat{T}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{3}\Big{]}}{\sqrt{\widehat{T}}}-\delta\rightarrow
N(0,1),$ (10)
$2\sqrt{\binom{n}{3(m-l)}(m-l)}\Bigg{[}\sqrt{\widehat{T}}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{\frac{3}{2}}\Bigg{]}-\delta\rightarrow
N(0,1).$ (11)

When $l=1$ and $m=2$, Theorem 2.7 becomes Theorem 2.2 of [25].

Following (10) in Theorem 2.7, we can construct a test statistic for (6) as

$\widehat{\mathcal{T}}_{m}=\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}\Big{[}\widehat{T}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{3}\Big{]}}{\sqrt{\widehat{T}}}.$
(12)

In practice, $\widehat{T}$ might be close to zero which may cause
computational instability, an alternative test can be constructed based on
(11) as

$\widehat{\mathcal{T}}^{\prime}_{m}=2\sqrt{\binom{n}{3(m-l)}(m-l)}\Bigg{[}\sqrt{\widehat{T}}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{\frac{3}{2}}\Bigg{]}.$
(13)

We remark that computation of $\widehat{\mathcal{T}}_{m}$ and
$\widehat{\mathcal{T}}^{\prime}_{m}$ is in polynomial time since the
computations of $\widehat{T}$, $\widehat{V}$ and $\widehat{E}$ are all in
complexity $O(n^{3(m-l)})$. Theorem 2.7 proves asymptotic normality for
$\widehat{\mathcal{T}}_{m}$ and $\widehat{\mathcal{T}}^{\prime}_{m}$ under
both $H_{0}^{\prime}$ and $H_{1}^{\prime}$. Under $H_{0}^{\prime}$, i.e.,
$\delta=0$, both $\widehat{\mathcal{T}}_{m}$ and
$\widehat{\mathcal{T}}^{\prime}_{m}$ are asymptotically standard normal. Under
$H_{1}^{\prime}$, both $\widehat{\mathcal{T}}_{m}$ and
$\widehat{\mathcal{T}}^{\prime}_{m}$ are asymptotically normal with mean
$\delta>0$ and unit variance. When $\widehat{T}$ has a large magnitude, both
test statistics can be used to construct valid rejection regions.

The following Theorem 2.8 says that the power of our test tends to one if
$\delta$ goes to infinity.

######  Theorem 2.8.

Suppose $\mathbb{E}W_{1}^{4}=O(1)$, $\mathbb{E}W_{1}\neq 0$, $n^{l-1}\ll
a_{n}\asymp b_{n}\ll n^{l-\frac{2}{3}}$ for some integer $1\leq
l\leq\frac{m}{2}$. Under $H_{1}^{\prime}$, as $n,\delta\rightarrow\infty$,
$\mathbb{P}(|\widehat{\mathcal{T}}_{m}|>z_{\alpha/2})\rightarrow 1$. The same
result holds for $\widehat{\mathcal{T}}^{\prime}_{m}$.

######  Remark 2.1.

When there are multiple possible choices for $l$, Theorem 2.7 and Theorem 2.8
may fail if $l$ is misspecified. For example, if $m=4$ and the “correct” value
is $l_{0}=2$ (corresponding to the true hyperedge probability), but we count
$1$-cycle. Then under $H_{0}$, the test statistic in (10) or (11) is of order
$O_{p}(n^{\frac{3}{2}})$, i.e., the limiting distribution does not exist.
Whereas, if the correct value is $l_{0}=1$ but we count $2$-cycle, then the
test statistic in (10) or (11) have the same limiting distribution (if it
exists) under $H_{0}$ and $H_{1}$, i.e., the power of the test does not
approach one. In practice, it is recommended to use hyperedge proportion to
get a rough estimate for $l$.

##  3 Extentions to Non-uniform Hypergraph.

Non-uniform hypergraph can be considered as a superposition of a collection of
uniform hypergraphs, introduced by [23] in which the authors proposed a
spectral algorithm for community detection. In this section, we study the
problem of testing community structure over a nonuniform hypergraph.
Interestingly, our results in Section 2.3 can be extended here without much
difficulty.

Let $\mathcal{H}^{k}(n,M)$ be a nonuniform hypergraph over $n$ vertices, with
the vertices uniformly and independently partitioned into $k$ communities, and
$M\geq 2$ is an integer representing the maximum length of the hyperedges.
Following [23], we can write
$\mathcal{H}^{k}(n,M)=\cup_{m=2}^{M}\mathcal{H}_{m}^{k}\left(n,\frac{a_{mn}}{n^{m-1}},\frac{b_{mn}}{n^{m-1}}\right)$,
where
$\mathcal{H}_{m}^{k}\left(n,\frac{a_{mn}}{n^{m-1}},\frac{b_{mn}}{n^{m-1}}\right)$
are independent uniform hypergraphs with degree-corrected vertices introduced
in Section 2.3. Assume that, for $2\leq m\leq M$, $a_{mn},b_{mn}$ are proxies
of the hyperedge densities satisfying $n^{l_{m}-1}\ll a_{mn}\asymp b_{mn}\ll
n^{l_{m}-\frac{2}{3}}$, for some integer $1\leq l_{m}\leq\frac{m}{2}$.
Correspondingly, define
$\mathcal{H}(n,M)=\cup_{m=2}^{M}\mathcal{H}_{m}\Big{(}n,\frac{a_{mn}+(k^{m-1}-1)b_{mn}}{k^{m-1}n^{m-1}}\Big{)}$
as a superposition of Erdös-Rényi models. Clearly, each Erdös-Rényi model in
$\mathcal{H}(n,M)$ has the same average degree as its counterpart in
$\mathcal{H}^{k}(n,M)$, and $\mathcal{H}(n,M)$ has no community structure. Let
$A_{m}$ denote the adjacency tensor for $m$-uniform sub-hypergraph and
$A=\\{A_{m},m=2,\ldots,M\\}$ is a collection of $A_{m}$’s. We are interested
in the following hypotheses:

$\displaystyle H_{0}^{\prime\prime}:A\sim\mathcal{H}(n,M)\ vs.\
H_{1}^{\prime\prime}:A\sim\mathcal{H}^{k}(n,M).$ (14)

For any $2\leq m\leq M$, let $\widehat{\mathcal{T}}_{m}$ and $\delta_{m}$ be
defined as in (12) and (9), respectively, based on the $m$-uniform sub-
hypergraph. We define a test statistic for (14) as

$\widehat{\mathcal{T}}=\sum_{m=2}^{M}c_{m}\widehat{\mathcal{T}}_{m},$ (15)

where $c_{m}$ are constants with normalization $\sum_{m=2}^{M}c_{m}^{2}=1$. As
a simple consequence of Theorems 2.7 and 2.8, we get the asymptotic
distribution of $\widehat{\mathcal{T}}$ as follows.

######  Corollary 3.1.

Suppose that the degree-correction weights satisfy the same conditions as in
Theorem 2.7, and for any $2\leq m\leq M$, $n^{l_{m}-1}\ll a_{mn}\asymp
b_{mn}\ll n^{l_{m}-\frac{2}{3}}$, for some integer $1\leq
l_{m}\leq\frac{m}{2}$. Then, as $n\to\infty$,
$\widehat{\mathcal{T}}-\sum_{m=2}^{M}c_{m}\delta_{m}\overset{d}{\to}N(0,1)$.
Furthermore, for any constant $C>0$, under $H_{1}^{\prime\prime}$,
$\mathbb{P}(|\widehat{\mathcal{T}}|>C)\rightarrow 1$, provided that
$\sum_{m=2}^{M}c_{m}\delta_{m}\rightarrow\infty$ as $n\to\infty$.

Under $H_{0}^{\prime\prime}$, i.e., each $m$-uniform subhypergraph has no
community structure, we have $\delta_{m}=0$ by Proposition 2.6. Corollary 3.1
says that $\widehat{\mathcal{T}}$ is asymptotically standard normal. Hence, an
asymptotic testing rule at significance $\alpha$ would be

$\textrm{reject $H_{0}^{\prime\prime}$ if and only if
$|\widehat{\mathcal{T}}|>z_{\alpha/2}$}.$

The quantity $\sum_{m=2}^{M}c_{m}\delta_{m}$ may represent the degree of
separation between $H_{0}^{\prime\prime}$ and $H_{1}^{\prime\prime}$. By
Corollary 3.1, under $H_{1}^{\prime\prime}$, the test will achieve high power
when $\sum_{m=2}^{M}c_{m}\delta_{m}$ is large.

######  Remark 3.1.

According to Corollary 3.1, to make $\widehat{\mathcal{T}}$ having the largest
power, we need to maximize the value of $\sum_{m=2}^{M}c_{m}\delta_{m}$
subject to $\sum_{m=2}^{M}c_{m}^{2}=1$. The maximizer is
$c^{*}_{m}=\frac{\delta_{m}}{\sqrt{\sum_{m=2}^{M}\delta_{m}^{2}}}$,
$m=2,3,\dots,M$. The corresponding test
$\widehat{\mathcal{T}}^{*}=\sum_{m=2}^{M}c_{m}^{*}\widehat{\mathcal{T}}_{m}$
becomes asymptotically the most powerful among (15). In particular,
$\widehat{\mathcal{T}}^{*}$ is more powerful than $\widehat{\mathcal{T}}_{m}$
for a single $m$. This can be explained by the more hyperedge information
involved in the test. This intuition is further confirmed by numerical studies
in Section 4. Note that $\widehat{\mathcal{T}}_{2}$ (m=2) is the classic test
proposed by [25] in ordinary graph setting.

##  4 Numerical Studies.

In this section, we provide a simulation study in Section 4.1 and real data
analysis in Section 4.2 to assess the finite sample performance of our tests.

###  4.1 Simulation.

We generated a nonuniform hypergraph
$\mathcal{H}^{2}(n,3)=\mathcal{H}_{2}^{2}(n,a_{2},b_{2})\cup\mathcal{H}_{3}^{2}(n,a_{3},b_{3})$,
with $n=100$ under various choices of $\\{(a_{m},b_{m}),m=2,3\\}$. In each
scenario, we calculated $Z_{2}:=\widehat{\mathcal{T}}_{2}^{\prime}$ and
$Z_{3}:=\widehat{\mathcal{T}}_{3}^{\prime}$ by (13). Note that
$Z_{2}=\widehat{\mathcal{T}}_{2}^{\prime}$ is the test for ordinary graph
considered in [25]. For testing the community structure on the nonuniform
hypergraph, we calculated the statistic
$Z:=\widehat{\mathcal{T}}=(\widehat{\mathcal{T}}_{2}^{\prime}+\widehat{\mathcal{T}}_{3}^{\prime})/\sqrt{2}$.
We examined the size and power of the test by calculating the rejection
proportions based on 500 independent replications at $5\%$ significance level.
Let $\delta_{m}$ denote the quantity defined in (9) which is the main factor
that affects power.

Our study consists of two parts. In the first part, we investigated the power
change of the three testing procedures when $\delta_{2}=\delta_{3}=\delta$
increases from 0 to 10. Specifically, we set $b_{2}=10b_{3}$, where
$b_{3}=0.01,0.005,0.001$ represents the dense, moderately dense and sparse
network, respectively; $a_{m}=r_{m}b_{m}$ for $m=2,3$ with the values of
$r_{m}$ summarized in Table 2. It can be checked that such choice of
$(a_{m},b_{m})$ indeed makes $\delta$ range from $0$ to $10$. We also
considered both balanced and imbalanced networks with the probability
($\varsigma$) of the smaller community takes the value of 0.5 and 0.3,
respectively.

The rejection proportions under various settings are summarized in Figures 4
through 6. Several interesting findings should be emphasized. First, the
rejection proportions of all test statistics at $\delta=0$ are close to the
nominal level $0.05$ under different choices of $\varsigma$ and $b_{3}$, which
demonstrates that all test statistics are valid. Second, as expected, the
rejection proportions of the three methods all increase with $\delta$,
regardless of the choices of $b_{3}$ and $\varsigma$. Third, in most cases,
the testing procedure based on non-uniform hypergraph has larger power than
the one based only on the $3$-uniform hypergraph or the ordinary graph. This
agrees with our theoretical finding since more information has been used in
the combined test; see Remark 3.1 for a detailed explanation.

$b_{3}$ | $\delta$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---|---
0.01 | $r_{3}$ | 1 | 2.26 | 2.65 | 2.93 | 3.17 | 3.38 | 3.58 | 3.75 | 3.91 | 4.06 | 4.21
$r_{2}$ | 1 | 2.07 | 2.43 | 2.71 | 2.95 | 3.16 | 3.35 | 3.53 | 3.71 | 3.87 | 4.02
0.005 | $r_{3}$ | 1 | 2.89 | 3.51 | 3.98 | 4.39 | 4.75 | 5.08 | 5.38 | 5.67 | 5.94 | 6.20
$r_{2}$ | 1 | 2.66 | 3.29 | 3.79 | 4.22 | 4.61 | 4.97 | 5.31 | 5.64 | 5.94 | 6.24
0.001 | $r_{3}$ | 1 | 6.50 | 8.83 | 10.73 | 12.41 | 13.95 | 15.39 | 16.76 | 18.03 | 19.28 | 20.48
$r_{2}$ | 1 | 6.57 | 9.31 | 11.59 | 13.64 | 15.51 | 17.26 | 18.92 | 20.51 | 22.00 | 23.46

Table 2: Choices of $r_{2},r_{3},b_{3}$ for $\delta$ to range from 1 to 10.

Figure 4: Rejection proportions in dense case with $b_{3}=0.1\times
b_{2}=0.01$.

Figure 5: Rejection proportions in moderately dense case with $b_{3}=0.1\times
b_{2}=0.005$.

Figure 6: Rejection proportions in sparse case with $b_{3}=0.1\times
b_{2}=0.001$.

In the second part, we investigated the power change along with the hyperedge
probability. For convenience, we report the results based on the log-scale of
$b_{3}$ which ranges from $-8$ to $-6$. We chose $\delta=1$ and $3$,
$\varsigma=0.3$ and 0.5, $b_{2}=10b_{3}$. Similar to the first part, we set
$a_{m}=r_{m}b_{m}$ with $m=2$ and $3$ to guarantee that $\log b_{3}$ indeed
ranges from $-8$ to $-6$. The values of $r_{m}$ were summarized in Table 3.
Figures 7 and 8 report the rejection proportions for $\delta=1$ and $3$ under
various hyperedge densities. We note that a larger $b_{3}$ leads to higher
rejection proportion of $Z$. Moreover, $Z$ is more powerful than $Z_{2}$ and
$Z_{3}$ in the cases $\varsigma=0.3,0.5$ and $\delta=3$. For the remaining
scenarios, all procedures have satisfactory performance.

$\delta$ | $\log(b_{3})$ | -8 | -7 | -6
---|---|---|---|---
1 | $r_{3}$ | 14.18 | 6.88 | 3.93
$r_{2}$ | 15.78 | 7.03 | 3.72
3 | $r_{3}$ | 26.37 | 11.51 | 5.82
$r_{2}$ | 30.68 | 12.54 | 5.83

Table 3: Choices of $r_{2}$, $r_{3}$, and $\delta$ for $\log(b_{3})$ to range
from $-8$ to $-6$.

Figure 7: Rejection proportions when $\delta=1$ and $b_{2}=10b_{3}$.

Figure 8: Rejection proportions when $\delta=3$ and $b_{2}=10b_{3}$.

###  4.2 Analysis of Coauthorship Data.

In this section, we applied our testing procedure to study the community
structure of a coauthorship network dataset, available at
https://static.aminer.org/lab-datasets/soinf/. The dataset contains a 2-author
ordinary graph and a 3-author hypergraph. After removing vertices with degrees
less than 10 or larger than 20, we obtained a hypergraph (hereinafter referred
to as global network) with 58 nodes, 110 edges and 40 hyperedges. The vertex-
removal process aims to obtain a suitably sparse network so that our testing
procedure is applicable. We examined our procedures based on the global
network and subnetworks. To do this, we first performed the spectral algorithm
proposed by [23] to partition the global network into four subnetworks which
consist of 7, 13, 14, 24 vertices, respectively (see Figure 9). In Figure 10,
we plotted the incidence matrices of the 2- and 3-uniform hypergraphs, denoted
2-UH and 3-UH respectively, as well as their superposition (Non-UH). The black
dots represent vertices within the same communities. The red crosses represent
vertices between different communities. An edge or hyperedge is drawn between
the black dots or red crosses that are vertically aligned. It is observed that
the between-community (hyper)edges are sparser than the within-community ones,
indicating the validity of the partitioning.

We conducted testing procedures based on $Z_{2}$, $Z_{3}$, and $Z$ at
significance level 0.05 (similar to Section 4.1) to both global network and
subnetworks. The values of the test statistics are summarized in Table 4.
Observe that $Z_{2}$ and $Z$ yield very large test values for global network
indicating strong rejection of the null hypothesis. For subnetwork testing,
$Z_{2}$ rejects the null hypothesis for subnetwork 3; while $Z_{3}$ and $Z$ do
not reject the null hypotheses for any subnetworks. This demonstrates the
community detection results are reasonable in general, and the subnetworks may
no longer have finer community structures.

Figure 9: Global network and four subnetworks based on coauthorship data.
Figure 10: Incidence matrices based on coauthorship data. Left: 2-uniform
hypergraph; Middle: 3-uniform hypergraph; Right: nonuniform hypergraph.

| Global Network | SubNetwork 1 | SubNetwork 2 | SubNetwork 3 | SubNetwork 4
---|---|---|---|---|---
$n$ | 58 | 7 | 13 | 14 | 24
$Z_{2}$ | 8.360** | 0.161 | -0.030 | 2.667* | 1.661
$Z_{3}$ | 1.451 | -0.100 | -0.211 | -0.289 | -0.052
$Z$ | 6.938** | 0.043 | -0.171 | 1.682 | 1.137

Table 4: Values of test statistics based on global network and four
subnetworks. Symbols $**$ and $*$ indicate the strength of rejection, i.e.,
p-value$<0.001$ and p-value$<0.05$ respectively.

##  5 Discussion.

In the context of community testing for hypergraphs, we systematically
considered various scenarios in terms of hyperedge densities and investigated
distinguishability or indistinguishability of the hypotheses in each scenario.
Extensions of our results are possible.

First of all, it is interesting to extend the test statistic in Section 2.3 to
tackle the model selection problem for SBM in hypergraphs. In particular, one
possibility is to study the hypothesis testing problem of $H_{0}:k=k_{0}$ vs.
$H_{1}:k>k_{0}$ for $k_{0}=1,2,\cdots$ sequentially and stop when observing a
rejection.

In addition, the results in Section 2.3 require $n^{l-1}\ll a_{n}\asymp
b_{n}\ll n^{l-\frac{2}{3}}$ for $1\leq l\leq m/2$, which excludes the case
$n^{l-\frac{2}{3}}\ll a_{n}\asymp b_{n}\ll n^{l}$. This might be a limitation
of counting hypervees and hypertriangles. The range of $a_{n}$ and $b_{n}$
might be further relaxed by counting higher-order sub-hypergraphs such as
those consisting of more hyperedges.

Lastly, the present methods cannot handle extremely dense hypergraphs such as
the ones with constant density. One possible solution is to extend the
spectral method proposed by [12] to our setting. However, to derive the
corresponding asymptotic theory, random matrix theory needs to be extended to
handle adjacency tensor which is a valuable future topic.

##  6 Proof of Main Results.

In this section, we prove the main results of this paper. The proofs of Lemmas
6.3, 6.4, 6.5, 6.7, 6.8 and Proposition 2.6 are relegated to the supplement.

###  6.1 Proof of Theorem 2.1.

The proof is based on one result in Janson ([32]) as below.

######  Proposition 6.1 (Janson, 1995).

Suppose that $L_{n}=\frac{d\mathbb{Q}_{n}}{d\mathbb{P}_{n}}$, regarded as a
random variable on $(\Omega_{n},\mathcal{F}_{n},\mathbb{P}_{n})$, converges in
distribution to some random variable $L$ as $n\rightarrow\infty$. Then
$\mathbb{P}_{n}$ and $\mathbb{Q}_{n}$ are contiguous if and only if $L>0$ a.s.
and $\mathbb{E}L=1$.

We prove Theorem 2.1 for $k=2$. The general case can be proved similarly, but
with more tediousness. For convenience, we use $\sigma_{i}=+$ or $-$ (rather
than $\sigma_{i}=1$ or $2$) to represent the potential community label of $i$.
We use $i_{1}:i_{m}$ to represent the ordering $i_{1}i_{2}\dots i_{m}$, and
hence, $A_{i_{1}:i_{m}}=A_{i_{1}i_{2}\dots i_{m}}$. Define
$I[\sigma_{i_{1}}:\sigma_{i_{m}}]=I[\sigma_{i_{1}}=\sigma_{i_{2}}=\dots=\sigma_{i_{m}}]$.
Let $d=\frac{a+(2^{m-1}-1)b}{2^{m-1}}$, $p_{0}=\frac{d}{n^{\alpha}}$,
$q_{0}=1-p_{0}$. Therefore, the hyperedge probabilities $p_{i_{1}i_{2}\dots
i_{m}}(\sigma)$ and $q_{i_{1}i_{2}\dots i_{m}}(\sigma)$ are rewritten as

$p_{i_{1}:i_{m}}(\sigma)=\mathbb{P}(A_{i_{1}:i_{m}}=1|\sigma)=\Big{(}\frac{a}{n^{\alpha}}\Big{)}^{I[\sigma_{i_{1}}:\sigma_{i_{m}}]}\Big{(}\frac{b}{n^{\alpha}}\Big{)}^{1-I[\sigma_{i_{1}}:\sigma_{i_{m}}]},$

and $q_{i_{1}:i_{m}}(\sigma)=1-p_{i_{1}:i_{m}}(\sigma)$. Let
$Y_{n}=\mathbb{P}_{H_{1}}(A)/\mathbb{P}_{H_{0}}(A)$ be the likelihood ratio of
the adjacent tensor $A$, where $\mathbb{P}_{H_{0}}$ and $\mathbb{P}_{H_{1}}$
are the probability measures under $H_{0}$ and $H_{1}$ respectively. Then
$Y_{n}=2^{-n}\sum_{\sigma\in\\{\pm\\}^{n}}\prod_{i\in
c(m,n)}\Big{(}\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\Big{)}^{A_{i_{1}:i_{m}}}\Big{(}\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\Big{)}^{1-A_{i_{1}:i_{m}}}$
which leads to that

$Y_{n}^{2}=2^{-2n}\sum_{\sigma,\eta\in\\{\pm\\}^{n}}\prod_{i\in
c(m,n)}\Big{(}\frac{p_{i_{1}:i_{m}}(\sigma)p_{i_{1}:i_{m}}(\eta)}{p_{0}^{2}}\Big{)}^{A_{i_{1}:i_{m}}}\Big{(}\frac{q_{i_{1}:i_{m}}(\sigma)q_{i_{1}:i_{m}}(\eta)}{q_{0}^{2}}\Big{)}^{1-A_{i_{1}:i_{m}}}.$

The expectation of $Y_{n}^{2}$ under $H_{0}$ is

$\displaystyle\mathbb{E}_{0}Y_{n}^{2}$ $\displaystyle=$ $\displaystyle
2^{-2n}\sum_{\sigma,\eta\in\\{\pm\\}^{n}}\prod_{i\in
c(m,n)}\Big{(}\frac{p_{i_{1}:i_{m}}(\sigma)p_{i_{1}:i_{m}}(\eta)}{p_{0}}+\frac{q_{i_{1}:i_{m}}(\sigma)q_{i_{1}:i_{m}}(\eta)}{q_{0}}\Big{)}.$
(16)

For any $\sigma,\eta\in\\{\pm\\}^{n}$, define $s_{2}=\\#\\{1\leq
i_{1}<i_{2}<\dots<i_{m}\leq
n:I[\sigma_{i_{1}}:\sigma_{i_{m}}]+I[\eta_{i_{1}}:\eta_{i_{m}}]=2\\}$,
$s_{1}=\\#\\{1\leq i_{1}<i_{2}<\dots<i_{m}\leq
n:I[\sigma_{i_{1}}:\sigma_{i_{m}}]+I[\eta_{i_{1}}:\eta_{i_{m}}]=1\\}$ and
$s_{0}=\\#\\{1\leq i_{1}<i_{2}<\dots<i_{m}\leq
n:I[\sigma_{i_{1}}:\sigma_{i_{m}}]+I[\eta_{i_{1}}:\eta_{i_{m}}]=0\\}$. Note
that $s_{0}$, $s_{1}$, $s_{2}$ are bounded above by $n^{m}$. By direct
examinations, we have

$\displaystyle\frac{1}{p_{0}}\Big{(}\frac{a}{n^{\alpha}}\Big{)}^{2}+\frac{1}{q_{0}}\Big{(}1-\frac{a}{n^{\alpha}}\Big{)}^{2}$
$\displaystyle=$ $\displaystyle
1+\frac{(a-d)^{2}}{dn^{\alpha}}+\frac{(a-d)^{2}}{n^{2\alpha}}+O(\frac{1}{n^{3\alpha}}),$
$\displaystyle\frac{1}{p_{0}}\frac{a}{n^{\alpha}}\frac{b}{n^{\alpha}}+\frac{1}{q_{0}}\Big{(}1-\frac{a}{n^{\alpha}}\Big{)}\Big{(}1-\frac{b}{n^{\alpha}}\Big{)}$
$\displaystyle=$ $\displaystyle
1+\frac{(a-d)(b-d)}{dn^{\alpha}}+\frac{(a-d)(b-d)}{n^{2\alpha}}+O(\frac{1}{n^{3\alpha}}),$
$\displaystyle\frac{1}{p_{0}}\Big{(}\frac{b}{n^{\alpha}}\Big{)}^{2}+\frac{1}{q_{0}}\Big{(}1-\frac{b}{n^{\alpha}}\Big{)}^{2}$
$\displaystyle=$ $\displaystyle
1+\frac{(b-d)^{2}}{dn^{\alpha}}+\frac{(b-d)^{2}}{n^{2\alpha}}+O(\frac{1}{n^{3\alpha}}).$

Then for $\alpha>\frac{m}{2}$, we have by (16) that

$\displaystyle\mathbb{E}_{0}Y_{n}^{2}$ $\displaystyle=$
$\displaystyle(1+o(1))\mathbb{E}_{\sigma\eta}\Big{\\{}\Big{(}1+\frac{(a-d)^{2}}{dn^{\alpha}}\Big{)}^{s_{2}}\Big{(}1+\frac{(a-d)(b-d)}{dn^{\alpha}}\Big{)}^{s_{1}}\Big{(}1+\frac{(b-d)^{2}}{dn^{\alpha}}\Big{)}^{s_{0}}\Big{\\}}$
(17) $\displaystyle=$
$\displaystyle(1+o(1))\mathbb{E}_{\sigma\eta}\exp\Big{\\{}\frac{(a-d)^{2}}{dn^{\alpha}}s_{2}+\frac{(a-d)(b-d)}{dn^{\alpha}}s_{1}+\frac{(b-d)^{2}}{dn^{\alpha}}s_{0}\Big{\\}}.$

If $\alpha>m$, then $\frac{s_{j}}{n^{\alpha}}\rightarrow 0$ for $j=0,1,2$.
Hence $\mathbb{E}_{0}Y_{n}^{2}\rightarrow 1$. Since $\mathbb{E}_{0}Y_{n}=1$,
we have that $Y_{n}$ converges to 1 in distribution. By Proposition 6.1,
$H_{0}$ and $H_{1}$ are contiguous.

Next we consider $\alpha=m$. Note that

$\displaystyle s_{2}$ $\displaystyle=$ $\displaystyle\sum_{i\in
c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}],$
$\displaystyle s_{1}$ $\displaystyle=$ $\displaystyle\sum_{i\in
c(m,n)}\Big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}](1-I[\eta_{i_{1}}:\eta_{i_{m}}])+(1-I[\sigma_{i_{1}}:\sigma_{i_{m}}])I[\eta_{i_{1}}:\eta_{i_{m}}]\Big{)},$
$\displaystyle s_{0}$ $\displaystyle=$
$\displaystyle\sum_{c(i,m,n)}(1-I[\sigma_{i_{1}}:\sigma_{i_{m}}])(1-I[\eta_{i_{1}}:\eta_{i_{m}}]).$

Then the numerator of the exponent in (17) can be written as

$\displaystyle(a-d)^{2}s_{2}+(a-d)(b-d)s_{1}+(b-d)^{2}s_{0}$ (18)
$\displaystyle=$
$\displaystyle\binom{n}{m}(b-d)^{2}+(a-b)^{2}\sum_{c(i,m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]$
$\displaystyle+(a-b)(b-d)\Big{(}\sum_{i\in
c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]+\sum_{c(i,m,n)}I[\eta_{i_{1}}:\eta_{i_{m}}]\Big{)}.$

For $s,t=+1,-1$, let

$\displaystyle\rho_{st}=\sum_{i=1}^{n}I[\sigma_{i}=t]I[\eta_{i}=s],\ \
\rho_{t0}=\sum_{i=1}^{n}I[\sigma_{i}=t],\ \
\rho_{0s}=\sum_{i=1}^{n}I[\eta_{i}=s],$

and

$\displaystyle\tilde{\rho}_{st}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(I[\sigma_{i}=t]I[\eta_{i}=s]-\frac{1}{2^{2}}),\
\tilde{\rho}_{t0}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(I[\sigma_{i}=t]-\frac{1}{2}),\
\tilde{\rho}_{0s}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}(I[\eta_{i}=s]-\frac{1}{2}).$

It is easy to verify that $\sum_{s,t}\tilde{\rho}_{st}=0$,
$\sum_{s}\tilde{\rho}_{s0}=0$, $\sum_{t}\tilde{\rho}_{0t}=0$ and

$\sum_{1\leq i_{1},\dots,i_{m}\leq
n}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]=m!\sum_{i_{1}<i_{2}<\dots<i_{m}}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]+O(n^{m-1}).$

Then we have

$\displaystyle\sum_{i\in
c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]$
$\displaystyle=$ $\displaystyle\frac{1}{m!}\sum_{1\leq i_{1},\dots,i_{m}\leq
n}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]+O(n^{m-1})$
$\displaystyle=$ $\displaystyle\frac{1}{m!}\sum_{1\leq i_{1},\dots,i_{m}\leq
n}\sum_{s,t=-1,+1}\prod_{j=1}^{m}I[\sigma_{i_{j}}=s]I[\eta_{i_{j}}=t]+O(n^{m-1})$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{s,t=-1,+1}\rho_{st}^{m}+O(n^{m-1})$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{s,t=-1,+1}(\sqrt{n}\tilde{\rho}_{st}+\frac{n}{2^{2}})^{m}+O(n^{m-1})$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\frac{4n^{m}}{2^{2m}}+\frac{1}{m!}n^{m-1}\sum_{s,t}\tilde{\rho}_{st}^{2}\sum_{k=2}^{m}\binom{m}{k}\frac{1}{2^{2(m-k)}}\Big{(}\frac{\tilde{\rho}_{st}}{\sqrt{n}}\Big{)}^{k-2}+O(n^{m-1}),$
$\displaystyle\sum_{i\in c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]$
$\displaystyle=$ $\displaystyle\frac{1}{m!}\sum_{1\leq i_{1},\dots,i_{m}\leq
n}I[\sigma_{i_{1}}:\sigma_{i_{m}}]+O(n^{m-1})$ $\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{t=-1,+1}\rho_{t0}^{m}+O(n^{m-1})$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\frac{2n^{m}}{2^{m}}+\frac{n^{m-1}}{m!}\sum_{t}\tilde{\rho}_{t0}^{2}\sum_{k=2}^{m}\binom{m}{k}\frac{1}{2^{(m-k)}}\Big{(}\frac{\tilde{\rho}_{t0}}{\sqrt{n}}\Big{)}^{k-2}+O(n^{m-1}),$
$\displaystyle\sum_{i\in c(m,n)}I[\eta_{i_{1}}:\eta_{i_{m}}]$ $\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{1\leq i_{1},\dots,i_{m}\leq
n}I[\eta_{i_{1}}:\eta_{i_{m}}]+O(n^{m-1})$ (21) $\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{s=-1,+1}\rho_{0s}^{m}+O(n^{m-1})$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\frac{2n^{m}}{2^{m}}+\frac{n^{m-1}}{m!}\sum_{s}\tilde{\rho}_{0s}^{2}\sum_{k=2}^{m}\binom{m}{k}\frac{1}{2^{(m-k)}}\Big{(}\frac{\tilde{\rho}_{0s}}{\sqrt{n}}\Big{)}^{k-2}+O(n^{m-1}).$

If $\alpha=m$, by (18), (6.1), (6.1), (6.1), and law of large number, we have

$\displaystyle(a-d)^{2}\frac{s_{2}}{n^{m}}+(a-d)(b-d)\frac{s_{1}}{n^{m}}+(b-d)^{2}\frac{s_{0}}{n^{m}}$
$\displaystyle\rightarrow$
$\displaystyle(a-b)^{2}\frac{4}{2^{2m}}+(a-b)(b-d)\frac{4}{2^{m}}+(b-d)^{2}$
(23) $\displaystyle=$
$\displaystyle\Big{(}\frac{a-b}{2^{m-1}}+(b-d)\Big{)}^{2}=0.$

Combining (17) and (23), we get that $\mathbb{E}_{0}Y_{n}^{2}\rightarrow 1$,
which implies that $H_{0}$ and $H_{1}$ are contiguous by Proposition 6.1.

Let $\alpha=m-1+\delta$, for $0<\delta<1$. Note that
$|\frac{\tilde{\rho}_{st}}{\sqrt{n}}|$,
$|\frac{\tilde{\rho}_{s0}}{\sqrt{n}}|$, $|\frac{\tilde{\rho}_{0t}}{\sqrt{n}}|$
are all bounded by 1. Hence, there is a universal constant $C$ such that

$\displaystyle\frac{(a-b)^{2}}{dm!}\Big{|}\sum_{k=2}^{m}\binom{m}{k}\frac{1}{2^{2(m-k)}}\Big{(}\frac{\tilde{\rho}_{ts}}{\sqrt{n}}\Big{)}^{k-2}\Big{|}$
$\displaystyle\leq$ $\displaystyle C,$
$\displaystyle\frac{(a-b)(b-d)}{dm!}\Big{|}\sum_{k=2}^{m}\binom{m}{k}\frac{1}{2^{(m-k)}}\Big{(}\frac{\tilde{\rho}_{t0}}{\sqrt{n}}\Big{)}^{k-2}\Big{|}$
$\displaystyle\leq$ $\displaystyle C,$
$\displaystyle\frac{(a-b)(b-d)}{dm!}\Big{|}\sum_{k=2}^{m}\binom{m}{k}\frac{1}{2^{(m-k)}}\Big{(}\frac{\tilde{\rho}_{0s}}{\sqrt{n}}\Big{)}^{k-2}\Big{|}$
$\displaystyle\leq$ $\displaystyle C.$

Note that $(b-d)^{2}+\frac{4}{2^{2m}}(a-b)^{2}+\frac{4}{2^{m}}(a-b)(b-d)=0$.
Then by (17), (18), (6.1), (6.1), (6.1), we have

$\displaystyle\mathbb{E}_{0}Y_{n}^{2}$ $\displaystyle\leq$
$\displaystyle(1+o(1))\mathbb{E}_{\sigma\eta}\exp\Big{\\{}\sum_{s,t}\frac{C}{n^{\delta}}\tilde{\rho}_{st}^{2}+\sum_{t}\frac{C}{n^{\delta}}\tilde{\rho}_{t0}^{2}+\sum_{s}\frac{C}{n^{\delta}}\tilde{\rho}_{0s}^{2}+O(\frac{1}{n^{\delta}})\Big{\\}}.$
(24)

By central limit theorem and Slutsky’s theorem, $\tilde{\rho}_{st}^{2}$,
$\tilde{\rho}_{s0}^{2}$ and $\tilde{\rho}_{0t}^{2}$ converge to chi-square
distributions, which implies that $\frac{C}{n^{\delta}}\tilde{\rho}_{st}^{2}$,
$\frac{C}{n^{\delta}}\tilde{\rho}_{s0}^{2}$ and
$\frac{C}{n^{\delta}}\tilde{\rho}_{0t}^{2}$ converge to zero in probability.
For any $\gamma>0$ and $\beta>0$, by Hoeffding inequality, we have

$\displaystyle\mathbb{P}\Big{(}\exp\Big{\\{}\frac{C}{n^{\delta}}\tilde{\rho}_{st}^{2}\Big{\\}}>\gamma^{\beta}\Big{)}=\mathbb{P}\Big{(}\frac{|\tilde{\rho}_{ts}|}{\sqrt{n}}>\sqrt{\frac{n^{\delta}\log\gamma^{\beta}}{Cn}}\Big{)}\leq
2\exp\Big{\\{}-\frac{n^{\delta}\log\gamma^{\beta}}{Cn}\frac{n}{m}\Big{\\}}=2\gamma^{-\beta\frac{n^{\delta}}{C}}.$

Choose a $n_{0}>0$ such that $C<\beta n_{0}^{\delta}$. For any $n\geq n_{0}$
and $C_{1}>0$, we have

$\int_{C_{1}}^{\infty}\mathbb{P}\Big{(}\exp\Big{\\{}\frac{C}{n^{\delta}}\tilde{\rho}_{st}^{2}\Big{\\}}>\gamma^{\beta}\Big{)}d\gamma\leq\frac{2}{\frac{\beta
n_{0}^{\delta}}{C}-1}C_{1}^{1-\frac{\beta n_{0}^{\delta}}{C}}.$ (25)

Notice that there are totally eight items in the summation
$\sum_{s,t}+\sum_{s}+\sum_{t}$ where the sums range over $s,t=\pm$. Therefore,
we have

$\displaystyle\mathbb{P}\Big{(}\exp\Big{\\{}\sum_{s,t}\frac{C}{n^{\delta}}\tilde{\rho}_{st}^{2}+\sum_{t}\frac{C}{n^{\delta}}\tilde{\rho}_{t0}^{2}+\sum_{s}\frac{C}{n^{\delta}}\tilde{\rho}_{0s}^{2}\Big{\\}}>t\Big{)}$
$\displaystyle\leq$
$\displaystyle\sum_{s,t}\mathbb{P}\Big{(}\exp\Big{\\{}\frac{C}{n^{\delta}}\tilde{\rho}_{st}^{2}\Big{\\}}>t^{\frac{1}{8}}\Big{)}+\sum_{s}\mathbb{P}\Big{(}\exp\Big{\\{}\frac{C}{n^{\delta}}\tilde{\rho}_{t0}^{2}\Big{\\}}>t^{\frac{1}{8}}\Big{)}+\sum_{t}\mathbb{P}\Big{(}\exp\Big{\\{}\frac{C}{n^{\delta}}\tilde{\rho}_{0s}^{2}\Big{\\}}>t^{\frac{1}{8}}\Big{)}.$

Together with (25), the variable in the right side of (24) is uniform
integrable. By $\mathbb{E}_{0}Y_{n}^{2}\geq 1$, we conclude that
$\mathbb{E}_{0}Y_{n}^{2}\rightarrow 1$, hence $H_{0}$ and $H_{1}$ are
contiguous by Proposition 6.1.

For $k>2$, let $S=\\{1,2,\dots,k\\}$ and $\sigma_{i}\in S$. It can be checked
that

$Y_{n}=k^{-n}\sum_{\sigma\in S^{n}}\prod_{i\in
c(m,n)}\Big{(}\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\Big{)}^{A_{i_{1}:i_{m}}}\Big{(}\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\Big{)}^{1-A_{i_{1}:i_{m}}}.$

The rest of the proof follows by a line-by-line check of the $k=2$ case.

###  6.2 Proof of Theorem 2.2.

The key idea in proving Theorem 2.2 is to count the long loose cycles and use
Theorem 1 in Gao and Wormald ([28]). Here “long” means that the number of
hyperedges in the loose cycle diverges along with $n$. Recall Theorem 1 from
Gao and Wormald ([28]) below.

######  Theorem 6.2 (Gao and Wormald, 2004).

Let $s_{n}>-\frac{1}{\mu_{n}}$ and
$\sigma_{n}=\sqrt{\mu_{n}+\mu_{n}^{2}s_{n}}$, where $\mu_{n}>0$ satisfies
$\mu_{n}\rightarrow\infty$. Suppose that $\mu_{n}=o(\sigma_{n}^{3})$ and
$\\{X_{n}\\}$ is a sequence of nonnegative random variables satisfying

$\mathbb{E}[X_{n}]_{k}\sim\mu_{n}^{k}\exp\Big{(}\frac{k^{2}s_{n}}{2}\Big{)},$

uniformly for all integers $k$ in the range $c_{1}\mu_{n}/\sigma_{n}\leq k\leq
c_{2}\mu_{n}/\sigma_{n}$ for some constants $c_{2}>c_{1}>0$. Then
$(X_{n}-\mu_{n})/\sigma_{n}$ converges in distribution to the standard normal
variable as $n\rightarrow\infty$. Here $\alpha_{n}\sim\beta_{n}$ means
$\lim_{n\rightarrow\infty}\frac{\alpha_{n}}{\beta_{n}}=1$.

Let $X_{k_{n}}$ be the number of $k_{n}$-hyperedge loose cycles over the
observed hypergraph. We will compute the expectation of $[X_{k_{n}}]_{s}$
under $H_{1}$. Consider the $s$-tuple of $k_{n}$-hyperedge loose cycles
$(H_{k_{n}1},\dots,H_{k_{n}s})$ in which $H_{k_{n}j}$ are $k_{n}$-hyperedge
loose cycles. Let $B$ be the collection of such $s$-tuples with vertex
disjoint cycles and $\bar{B}$ be the collection of tuples in which two cycles
have common vertex. The expectation of $[X_{k_{n}}]_{s}$ under $H_{1}$ can be
expressed as

$\mathbb{E}_{1}[X_{k_{n}}]_{s}=\sum_{B}\mathbb{E}_{1}I_{\cup_{i=1}^{s}H_{k_{n}i}}+\sum_{\bar{B}}\mathbb{E}_{1}I_{\cup_{i=1}^{s}H_{k_{n}i}}.$

Let $\tau$ be a random label assignment. The first term in the right hand side
of the above equation is

$\displaystyle\mathbb{E}_{1}I_{\cup_{i=1}^{s}H_{k_{n}i}}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{1}\prod_{i=1}^{s}I_{H_{k_{n}i}}=\mathbb{E}_{\tau}\prod_{i=1}^{s}\mathbb{E}_{1}I_{H_{k_{n}i}}=\mathbb{E}_{\tau}\prod_{i=1}^{s}\prod_{\\{i_{1},\dots,i_{m}\\}\in\mathcal{E}(H_{k_{n}i})}\frac{M_{i_{1}i_{2}\dots
i_{m}}(\tau)}{n^{m-1}}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{s}\Big{(}\Big{[}\frac{a+(k^{m-1}-1)b}{(kn)^{m-1}}\Big{]}^{k_{n}}+(k-1)\Big{[}\frac{a-b}{(kn)^{m-1}}\Big{]}^{k_{n}}\Big{)}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{(m-1)k_{n}s}}\Big{(}\Big{[}\frac{a+(k^{m-1}-1)b}{{k}^{m-1}}\Big{]}^{k_{n}}+(k-1)\Big{[}\frac{a-b}{k^{m-1}}\Big{]}^{k_{n}}\Big{)}^{s},$

where $\mathcal{E}(H_{k_{n}i})$ is the hyperedge set of $H_{k_{n}i}$. Note
that
$\\#B=\frac{n!}{(n-M_{1})!}\Big{(}\frac{1}{2k_{n}(m-2)!^{k_{n}}}\Big{)}^{s}$,
where $M_{1}=(m-1)k_{n}s$. Then for $M_{1}=o(\sqrt{n})$,

$\displaystyle\sum_{B}\mathbb{E}_{1}I_{\cup_{i=1}^{s}H_{k_{n}i}}$
$\displaystyle=$
$\displaystyle\\#B\times\mathbb{E}_{1}I_{\cup_{i=1}^{s}H_{k_{n}i}}$
$\displaystyle=$
$\displaystyle\frac{n!}{(n-M_{1})!}n^{-M_{1}}\Big{(}\frac{1}{2k_{n}}\Big{[}\frac{a+(k^{m-1}-1)b}{{k}^{m-1}(m-2)!}\Big{]}^{k_{n}}+\frac{(k-1)}{2k_{n}}\Big{[}\frac{a-b}{k^{m-1}(m-2)!}\Big{]}^{k_{n}}\Big{)}^{s}$
$\displaystyle\sim$
$\displaystyle\Big{(}\frac{1}{2k_{n}}\Big{[}\frac{a+(k^{m-1}-1)b}{{k}^{m-1}(m-2)!}\Big{]}^{k_{n}}+\frac{(k-1)}{2k_{n}}\Big{[}\frac{a-b}{k^{m-1}(m-2)!}\Big{]}^{k_{n}}\Big{)}^{s}.$

The “$\sim$” is due to the trivial fact that
$\frac{n!}{(n-M_{1})!}n^{-M_{1}}\to 1$ as $M_{1}=o(\sqrt{n})$. Note that
$\\#\bar{B}\leq M_{1}^{2}n^{M_{1}-1}$ and
$\mathbb{E}_{1}[I_{\cup_{i=1}^{s}H_{k_{n}i}}|\tau]\leq\Big{(}\frac{a}{n^{m-1}}\Big{)}^{|\mathcal{E}(H)|}$,
then

$\displaystyle\sum_{\bar{B}}\mathbb{E}_{1}I_{\cup_{i=1}^{s}H_{k_{n}i}}\leq
M_{1}^{2}n^{M_{1}-1}\Big{(}\frac{a}{n^{m-1}}\Big{)}^{|\mathcal{E}(H)|}=M_{1}^{2}\frac{a^{M_{1}}}{n}\rightarrow
0,$

provided that $M_{1}\leq\delta_{1}\log_{a}n$ for a constant $0<\delta_{1}<1$.

Define
$\mu_{n1}=\frac{1}{2k_{n}}\Big{[}\frac{a+(k^{m-1}-1)b}{{k}^{m-1}(m-2)!}\Big{]}^{k_{n}}+\frac{(k-1)}{2k_{n}}\Big{[}\frac{a-b}{k^{m-1}(m-2)!}\Big{]}^{k_{n}}$
and
$\mu_{n0}=\frac{1}{2k_{n}}\Big{[}\frac{a+(k^{m-1}-1)b}{{k}^{m-1}(m-2)!}\Big{]}^{k_{n}}$.
If $M_{1}\leq\delta_{1}\log_{a}n$, then

$\mathbb{E}_{1}[X_{k_{n}}]_{s}\sim\mu_{n1}^{s},$ (26)
$\mathbb{E}_{0}[X_{k_{n}}]_{s}\sim\mu_{n0}^{s}.$ (27)

Note that $\kappa>1$ implies $\lambda_{m}>1$. To see this, let
$a=c+(k^{m-1}-1)d$ and $b=c-d$ for some constants $c>d>0$. Then it follows
from $\kappa>1$ that $c>(m-2)!$, which yields $\lambda_{m}>1$. Then
$\mu_{n1},\mu_{n0}\rightarrow\infty$ as $n\rightarrow\infty$. It is obvious
that

$\mu_{n1}\leq\frac{\Big{(}\log_{\gamma}n\Big{)}^{\delta_{0}}}{k_{n}},\ \
\mu_{n0}\leq\frac{\Big{(}\log_{\gamma}n\Big{)}^{\delta_{0}}}{k_{n}}.$

Let $\sigma_{n1}=\sqrt{\mu_{n1}}$, $\sigma_{n0}=\sqrt{\mu_{n0}}$. For any
constant $c_{2}>c_{1}>0$ and $s$ satisfying
$c_{1}\frac{\mu_{n1}}{\sigma_{n1}}\leq s\leq
c_{2}\frac{\mu_{n1}}{\sigma_{n1}}$ or $c_{1}\frac{\mu_{n0}}{\sigma_{n0}}\leq
s\leq c_{2}\frac{\mu_{n0}}{\sigma_{n0}}$, we have for large $n$

$M_{1}=(m-1)k_{n}s=(m-1)\sqrt{\Big{(}\log_{\gamma}n\Big{)}^{\delta_{0}}\log_{\lambda_{m}}\Big{(}\log_{\gamma}n\Big{)}^{\delta_{0}}}\leq\delta_{1}\log_{a}n,$

which implies (26) and (27) hold. By Theorem 6.2, we conclude that
$\frac{X_{k_{n}}-\mu_{n1}}{\sqrt{\mu_{n1}}}$ and
$\frac{X_{k_{n}}-\mu_{n0}}{\sqrt{\mu_{n0}}}$ converge in distribution to the
standard normal variables under $H_{1}$ and $H_{0}$, respectively.

Since $\kappa>1$, there exits a constant $\rho$ satisfying

$\sqrt{\frac{a+(k^{m-1}-1)b}{{k}^{m-1}(m-2)!}}<\rho<\frac{a-b}{k^{m-1}(m-2)!}.$

It is easy to verify that $\mu_{n1}=o(\rho^{2k_{n}})$,
$\mu_{n0}=o(\rho^{2k_{n}})$. Let
$A_{n}=\\{X_{k_{n}}\leq\mathbb{E}_{0}X_{k_{n}}+\rho^{k_{n}}\\}$. Then we have

$\displaystyle\mathbb{P}_{H_{0}}(A_{n})$ $\displaystyle=$
$\displaystyle\mathbb{P}_{H_{0}}\Big{(}\frac{X_{k_{n}}-\mu_{n0}}{\sqrt{\mu_{n0}}}\leq\frac{\rho^{k_{n}}}{\sqrt{\mu_{n0}}}\Big{)}\rightarrow\Phi(\infty)=1.$
(28)

Note that $\frac{\mu_{n1}-\mu_{n0}}{\rho^{k_{n}}}\rightarrow\infty$, then for
large $n$, we have $\mu_{n1}-\rho^{k_{n}}\geq\mu_{n0}+\rho^{k_{n}}$. Then it
yields

$\displaystyle\mathbb{P}_{H_{1}}(A_{n})\leq\mathbb{P}_{H_{1}}\Big{(}X_{k_{n}}\leq\mathbb{E}_{1}X_{k_{n}}-\rho^{k_{n}}\Big{)}=\mathbb{P}_{H_{1}}\Big{(}\frac{X_{k_{n}}-\mu_{n1}}{\sqrt{\mu_{n1}}}\leq-\frac{\rho^{k_{n}}}{\sqrt{\mu_{n1}}}\Big{)}\rightarrow\Phi(-\infty)=0.$
(29)

By definition, (28) and (29) shows that $H_{0}$ and $H_{1}$ are orthogonal.

###  6.3 Proof of Theorem 2.4.

Let $f=\frac{a-b}{k^{m-1}(m-2)!}$. By the proof of Theorem 2.2, it is easy to
show that for any $\epsilon>0$,

$\mathbb{P}_{H_{1}}\Big{(}\frac{2k_{n}X_{k_{n}}-\lambda_{m}^{k_{n}}-(k-1)f^{k_{n}}}{(k-1)f^{k_{n}}}>\epsilon\Big{)}=\mathbb{P}_{H_{1}}\Big{(}\frac{X_{k_{n}}-\mu_{n1}}{\sqrt{\mu_{n1}}}>\frac{(k-1)f^{k_{n}}\epsilon}{2k_{n}\sqrt{\mu_{n1}}}\Big{)}=1-\Phi\Big{(}\frac{(k-1)f^{k_{n}}\epsilon}{2k_{n}\sqrt{\mu_{n1}}}\Big{)}\rightarrow
0,$

and
$\mathbb{P}_{H_{1}}\Big{(}\frac{2k_{n}X_{k_{n}}-\lambda_{m}^{k_{n}}-(k-1)f^{k_{n}}}{(k-1)f^{k_{n}}}<-\epsilon\Big{)}\rightarrow
0$. Then it follows that
$2k_{n}X_{k_{n}}-\lambda_{m}^{k_{n}}=(1+o_{p}(1))(k-1)f^{k_{n}}$.

Next, we show that
$\widehat{\lambda}_{m}^{k_{n}}-\lambda_{m}^{k_{n}}=o_{p}(1)$. For simplicity,
we only show $\widehat{\lambda}_{3}^{k_{n}}-\lambda_{3}^{k_{n}}=o_{p}(1)$, the
general case follows similarly. Let
$\eta_{ijt}=\frac{(a-b)I[\sigma_{i}=\sigma_{j}=\sigma_{t}]+b}{n^{2}}$. By
Taylor expansion, we have

$\widehat{\lambda}_{3}^{k_{n}}-\lambda_{3}^{k_{n}}=\sum_{i=1}^{k_{n}}\frac{k_{n}(k_{n}-1)\dots(k_{n}-i+1)}{i!}\lambda_{3}^{k_{n}-i}(\widehat{\lambda}_{3}-\lambda_{3})^{i},$

from which it follows that

$\mathbb{E}(\widehat{\lambda}_{3}^{k_{n}}-\lambda_{3}^{k_{n}})^{2}=\sum_{i,j=1}^{k_{n}}C_{ij}\lambda_{3}^{2k_{n}-i-j}\mathbb{E}(\widehat{\lambda}_{3}-\lambda_{3})^{i+j},$
(30)

where
$C_{ij}=\frac{k_{n}(k_{n}-1)\dots(k_{n}-i+1)}{i!}\frac{k_{n}(k_{n}-1)\dots(k_{n}-j+1)}{j!}\leq
k_{n}^{2k_{n}}$. For any integer $s$ with $2\leq s\leq 2k_{n}$, we calculate
$\mathbb{E}(\widehat{\lambda}_{3}-\lambda_{3})^{s}$ as follows:

$\displaystyle\mathbb{E}(\widehat{\lambda}_{3}-\lambda_{3})^{s}$ (31)
$\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}\frac{n^{2}}{\binom{n}{3}}\sum_{i<j<t}\Big{(}A_{ijt}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{]}^{s}$
$\displaystyle=$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,s}\mathbb{E}\Big{[}\Big{(}A_{i_{1}j_{1}t_{1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}A_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{]}$
$\displaystyle=$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,s}\mathbb{E}\Big{[}\Big{(}A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}}+\eta_{i_{1}j_{1}t_{1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\times\dots$
$\displaystyle\times\Big{(}A_{i_{s}j_{s}t_{s}}-\eta_{i_{s}j_{s}t_{s}}+\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{]}$
$\displaystyle=$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,s}\mathbb{E}\Big{[}\Big{(}A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}}\Big{)}\dots\Big{(}A_{i_{s}j_{s}t_{s}}-\eta_{i_{s}j_{s}t_{s}}\Big{)}+\dots$
$\displaystyle+\Big{(}\eta_{i_{1}j_{1}t_{1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{]}.$

There are $\binom{n}{3}^{s}$ index triples $(i_{r},j_{r},t_{r})$ for $1\leq
r\leq s$ in total. Among them,
$\binom{n}{3}\binom{n-3}{3}\dots\binom{n-3(s-1)}{3}$ ones are disjoint, that
is, $(i_{r},j_{r},t_{r})$ and $(i_{u},j_{u},t_{u})$ are disjoint for any
$1\leq r<u\leq s$. In the disjoint case, the independence between
$\eta_{i_{r}j_{r}t_{r}}(1\leq r\leq s)$ yields

$\mathbb{E}\Big{[}\Big{(}\eta_{i_{1}j_{1}t_{1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{]}=0.$

Let $C_{1}>1$ be a constant such that $|\eta_{ijt}|\leq\frac{C_{1}}{n^{2}}$
and $|\eta_{ijt}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}|\leq\frac{C_{1}}{n^{2}}$. Let
$C_{2}=18C_{1}>1$, we have

$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,s}\Big{|}\mathbb{E}\Big{[}\Big{(}\eta_{i_{1}j_{1}t_{1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{]}\Big{|}$
$\displaystyle\leq$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\Big{[}\binom{n}{3}^{s}-\binom{n}{3}\binom{n-3}{3}\dots\binom{n-3(s-1)}{3}\Big{]}\frac{C_{1}^{s}}{n^{2s}}\leq\frac{3^{s-1}(s-1)!n^{2s+1}C_{1}^{s}}{\binom{n}{3}^{s}}\leq\frac{C_{2}^{s}(2k_{n})^{2k_{n}}}{n}.$

Consider the terms in (31) consisting of $v$ items $(A_{ijt}-\eta_{ijt})$ for
$1\leq v\leq s$. Typically they have the following fashion:

$\mathbb{E}\left[(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})\dots(A_{i_{v}j_{v}t_{v}}-\eta_{i_{v}j_{v}t_{v}})\Big{(}\eta_{i_{v+1}j_{v+1}t_{v+1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\right].$
(32)

The above term vanishes when $v=1$ since
$\mathbb{E}[(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})|\sigma]=0$. When
$v=2$, if $(i_{1},j_{1},t_{1})\neq(i_{2},j_{2},t_{2})$, then

$\mathbb{E}\big{[}(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})(A_{i_{2}j_{2}t_{2}}-\eta_{i_{2}j_{2}t_{2}})\big{|}\sigma\big{]}=\mathbb{E}\big{[}(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})\big{|}\sigma\big{]}\mathbb{E}\big{[}(A_{i_{2}j_{2}t_{2}}-\eta_{i_{2}j_{2}t_{2}})\big{|}\sigma\big{]}=0,$

since $A_{ijt}$ are independent conditional on $\sigma$. This implies that
(32) vanishes. Hence, (32) is nonzero if and only if
$(i_{1},j_{1},t_{1})=(i_{2},j_{2},t_{2})$. In this case, we have

$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,s}\Big{|}\mathbb{E}(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})\dots(A_{i_{v}j_{v}t_{v}}-\eta_{i_{v}j_{v}t_{v}})$
$\displaystyle\times\Big{(}\eta_{i_{v+1}j_{v+1}t_{v+1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{|}$
$\displaystyle=$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=2,\dots,s}\Big{|}\mathbb{E}(A_{i_{2}j_{2}t_{2}}-\eta_{i_{2}j_{2}t_{2}})^{2}\Big{(}\eta_{i_{3}j_{3}t_{3}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{|}$
$\displaystyle=$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=2,\dots,s}\Big{|}\mathbb{E}\eta_{i_{2}j_{2}t_{2}}(1-\eta_{i_{2}j_{2}t_{2}})\Big{(}\eta_{i_{3}j_{3}t_{3}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{|}$
$\displaystyle\leq$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\Big{[}\binom{n}{3}^{s-1}\frac{C_{1}}{n^{2}}\frac{C_{1}^{s-2}}{n^{2(s-2)}}\Big{]}=\frac{n^{2}C_{1}^{s-1}}{\binom{n}{3}}\leq\frac{C_{2}^{s}(2k_{n})^{2k_{n}}}{n}.$

When $3\leq v\leq s$, for each $r$ with $1\leq r\leq v$, there exists
$r_{0}\neq r$ such that $(i_{r_{0}},j_{r_{0}},t_{r_{0}})=(i_{r},j_{r},t_{r})$.
Otherwise the expectation in (32) will vanish. For example, if $v=4$ and
$(i_{1},j_{1},t_{1})\neq(i_{2},j_{2},t_{2})=(i_{3},j_{3},t_{3})=(i_{4},j_{4},t_{4})$,
then

$\displaystyle\mathbb{E}\big{[}(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})(A_{i_{2}j_{2}t_{2}}-\eta_{i_{2}j_{2}t_{2}})^{3}\big{|}\sigma\big{]}=\mathbb{E}\big{[}(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})\big{|}\sigma\big{]}\mathbb{E}\big{[}(A_{i_{2}j_{2}t_{2}}-\eta_{i_{2}j_{2}t_{2}})^{3}\big{|}\sigma\big{]}=0,$

which implies that either
$(i_{1},j_{1},t_{1})=(i_{2},j_{2},t_{2})=(i_{3},j_{3},t_{3})=(i_{4},j_{4},t_{4})$
or $(i_{r_{1}},j_{r_{1}},t_{r_{1}})=(i_{r_{2}},j_{r_{2}},t_{r_{2}})$ and
$(i_{r_{3}},j_{r_{3}},t_{r_{3}})=(i_{r_{4}},j_{r_{4}},t_{r_{4}})$ for distinct
$r_{1},r_{2},r_{3},r_{4}\in\\{1,2,3,4\\}$. In the general case, suppose for
some $q$ with $1\leq q<v$ and $p_{r}\geq 2$ for $1\leq r\leq q$ that

$(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})\dots(A_{i_{v}j_{v}t_{v}}-\eta_{i_{v}j_{v}t_{v}})=(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})^{p_{1}}\dots(A_{i_{q}j_{q}t_{q}}-\eta_{i_{q}j_{q}t_{q}})^{p_{q}}.$

Then, after relabeling the indexes, one has

$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,s}\Big{|}\mathbb{E}(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})\dots(A_{i_{v}j_{v}t_{v}}-\eta_{i_{v}j_{v}t_{v}})$
$\displaystyle\times\Big{(}\eta_{i_{v+1}j_{v+1}t_{v+1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s}j_{s}t_{s}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{|}$
$\displaystyle=$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,{s-v+q}}\Big{|}\mathbb{E}(A_{i_{1}j_{1}t_{1}}-\eta_{i_{1}j_{1}t_{1}})^{p_{1}}\dots(A_{i_{q}j_{q}t_{q}}-\eta_{i_{q}j_{q}t_{q}})^{p_{q}}$
$\displaystyle\times\Big{(}\eta_{i_{q+1}j_{q+1}t_{q+1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\dots\Big{(}\eta_{i_{s-v+q}j_{s-v+q}t_{s-v+q}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{|}$
$\displaystyle=$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\sum_{i_{r}<j_{r}<t_{r},r=1,\dots,{s-v+q}}\Big{|}\mathbb{E}\eta_{i_{1}j_{1}t_{1}}\dots\eta_{i_{q}j_{q}t_{q}}\Big{(}\eta_{i_{q+1}j_{q+1}t_{q+1}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\times$
$\displaystyle\dots\times\Big{(}\eta_{i_{s-v+q}j_{s-v+q}t_{s-v+q}}-\frac{a+(k^{2}-1)b}{n^{2}k^{2}}\Big{)}\Big{|}$
$\displaystyle\leq$
$\displaystyle\frac{n^{2s}}{\binom{n}{3}^{s}}\Big{[}\binom{n}{3}^{s-v+q}\frac{C_{1}^{q}}{n^{2q}}\frac{C_{1}^{s-v}}{n^{2(s-v)}}\Big{]}=\frac{(3!)^{v-q}C_{1}^{s-v+q}}{n^{v-q}}\leq\frac{C_{2}^{s}(2k_{n})^{2k_{n}}}{n}.$

Hence, by (30) and (31) and for some large constant $C_{3}>1$, we conclude
that $\mathbb{E}(\widehat{\lambda}_{3}-\lambda_{3})^{s}\leq
2^{s}\frac{C_{2}^{s}(2k_{n})^{2k_{n}}}{n}$ and

$\displaystyle\mathbb{E}(\widehat{\lambda}_{3}^{k_{n}}-\lambda_{3}^{k_{n}})^{2}$
$\displaystyle\leq$ $\displaystyle
k_{n}^{2}k_{n}^{2k_{n}}\lambda_{3}^{2k_{n}}2^{k_{n}}\frac{C_{2}^{k_{n}}(2k_{n})^{2k_{n}}}{n}\leq\frac{(C_{3}k_{n})^{C_{3}k_{n}}}{n}.$

Let $N_{n}=C_{3}k_{n}\rightarrow\infty$, then
$n=\gamma^{\lambda_{3}^{\frac{N_{n}}{\delta_{0}C_{3}}}}$. For large $N_{n}$,
it holds that $\lambda_{3}^{\frac{N_{n}}{\delta_{0}C_{3}}}\geq C_{4}N_{n}^{2}$
for some constant $C_{4}>0$, which implies that

$\mathbb{E}(\widehat{\lambda}_{3}^{k_{n}}-\lambda_{3}^{k_{n}})^{2}\leq\frac{(C_{3}k_{n})^{C_{3}k_{n}}}{n}=\frac{N_{n}^{N_{n}}}{\gamma^{\lambda_{3}^{\frac{N_{n}}{\delta_{0}C_{3}}}}}\leq\Big{(}\frac{N_{n}}{\gamma^{C_{4}N_{n}}}\Big{)}^{N_{n}}\rightarrow
0,$

leading to $\widehat{\lambda}_{3}^{k_{n}}-\lambda_{3}^{k_{n}}=o_{p}(1)$.

Now we conclude
$2k_{n}X_{k_{n}}-\widehat{\lambda}_{m}^{k_{n}}=(1+o_{p}(1))(k-1)f^{k_{n}}$,
which implies that $\widehat{f}=f+o_{p}(1)$. Since $\widehat{\lambda}_{m}$ and
$\widehat{f}$ are consistent estimators of $\lambda_{m}$ and $f$, then
$\widehat{a}_{n}$ and $\widehat{b}_{n}$ are consistent estimators of $a$ and
$b$, respectively.

###  6.4 Proof of Theorem 2.5.

Before proving Theorem 2.5, we need several preliminary results, i.e., Lemmas
6.3, 6.4, 6.5, 6.7 and Proposition 6.6.

######  Lemma 6.3.

Let $M_{0}$ be the following $k\times k$ matrix

$M_{0}=\begin{bmatrix}a+(k^{m-2}-1)b&k^{m-2}b&\dots&k^{m-2}b\\\
k^{m-2}b&a+(k^{m-2}-1)b&\dots&k^{m-2}b\\\ \vdots&\vdots&\dots&\vdots\\\
k^{m-2}b&k^{m-2}b&\dots&a+(k^{m-2}-1)b\end{bmatrix}.$

Then the trace of $M_{0}^{j}$ is

$Tr(M_{0}^{j})=(a+(k^{m-2}-1)b)^{j}+(k-1)(a-b)^{j},$

for any positive integer $j$.

######  Lemma 6.4.

For any $1\leq i_{1},\ldots,i_{m}\leq k$, let $M_{i_{1}i_{2}\dots
i_{m}}=(a-b)I[i_{1}=i_{2}=\dots=i_{m}]+b$. If $j\geq 1$ and $1\leq
i_{1},\dots,i_{jm-j}\leq k$, then we have

$\sum_{i_{1},\dots,i_{jm-j}=1}^{k}M_{i_{1}i_{2}\dots i_{m}}M_{i_{m}\dots
i_{2m-1}}M_{i_{2m-1}\dots i_{3m-2}}\dots M_{i_{(j-1)m-(j-2)}\dots
i_{jm-j}i_{1}}=Tr(M_{0}^{j}),$

where $M_{0}$ is the same as in Lemma 6.3.

######  Lemma 6.5.

For any $h\geq 2$, let $X_{hn}$ be the number of $h$-hyperedge loose cycles in
$\mathcal{H}_{m}(n,\frac{d}{n^{m-1}})$, where
$d=\frac{a+(k^{m-1}-1)b}{k^{m-1}}$. Then for any integer $s\geq 2$,
$\\{X_{hn}\\}_{h=2}^{s}$ jointly converge to independent Poisson variables
with means $\lambda_{h}=\frac{d^{h}}{2h[(m-2)!]^{h}}$.

The following proposition is useful to prove Theorem 2.5. For any non-negative
integer $x$, let $[x]_{j}$ denote the product $x(x-1)\cdots(x-j+1)$.

######  Proposition 6.6 (Janson, 1995).

Let $\lambda_{i}>0$, $i=1,2,\ldots$, be constants and suppose that for each
$n$ there are random variables $X_{in}$, $i=1,2,\ldots$, and $Y_{n}$ (defined
on the same probability space) such that $X_{in}$ is non-negative integer
valued and $\mathbb{E}\\{Y_{n}\\}\neq 0$ (at least for large $n$), and
furthermore the following conditions are satisfied:

  * (A1)

$X_{in}\overset{d}{\to}Z_{i}$ as $n\to\infty$, jointly for all $i$, where
$Z_{i}\sim\textrm{Poisson}(\lambda_{i})$ are independent Poisson random
variables;

  * (A2)

$\mathbb{E}\\{Y_{n}[X_{1n}]_{j_{1}}\cdots[X_{kn}]_{j_{k}}\\}/\mathbb{E}\\{Y_{n}\\}\to\prod_{i=1}^{k}\mu_{i}^{j_{i}}$,
as $n\to\infty$, for some $\mu_{i}\geq 0$ and every finite sequence
$j_{1},\ldots,j_{k}$ of non-negative integers;

  * (A3)

$\sum_{i=1}^{\infty}\lambda_{i}\delta_{i}^{2}<\infty$, where
$\delta_{i}=\mu_{i}/\lambda_{i}-1$;

  * (A4)

$\mathbb{E}\\{Y_{n}^{2}\\}/(\mathbb{E}\\{Y_{n}\\})^{2}\to\exp\left(\sum_{i=1}^{\infty}\lambda_{i}\delta_{i}^{2}\right)$.

Then

$\frac{Y_{n}}{\mathbb{E}\\{Y_{n}\\}}\overset{d}{\to}W\equiv\prod_{i=1}^{\infty}(1+\delta_{i})^{Z_{i}}\exp(-\lambda_{i}\delta_{i}),\,\,\,\,\textrm{as
$n\to\infty$},$

and $\mathbb{E}W=1$.

For $u=1,\ldots,n$, let
$\widetilde{\sigma}_{u}=(1_{[\sigma_{u}=1]},\dots,1_{[\sigma_{u}=k]})^{T}$,
$\widetilde{\tau}_{u}=(1_{[\tau_{u}=1]},\dots,1_{[\tau_{u}=k]})^{T}$. Clearly,
$\widetilde{\sigma}_{u},\widetilde{\tau}_{u}\sim Multinomial(1,k,p)$ with
$p=\frac{1}{k}$. Let $C$ be a $(k^{2}+2k)\times(k^{2}+2k)$ diagonal matrix,
with the first $2k$ diagonal elements $c_{1}$, the last $k^{2}$ diagonal
elements $c_{2}$. Let

$\tilde{\rho}=(\tilde{\rho}_{10},\dots,\tilde{\rho}_{s0},\tilde{\rho}_{01},\dots,\tilde{\rho}_{0s},\tilde{\rho}_{11},\tilde{\rho}_{12},\dots,\tilde{\rho}_{ss})^{T}.$

Then $Z_{n}=\tilde{\rho}C\tilde{\rho}^{T}$. By central limit theorem,
$\tilde{\rho}$ converges to $N(0,\Sigma)$, where $\Sigma$ is the covariance
matrix of
$(\widetilde{\sigma}_{u}^{T},\widetilde{\tau}_{u}^{T},\widetilde{\sigma}_{u}^{T}\otimes\widetilde{\tau}_{u}^{T})^{T}$.

######  Lemma 6.7.

The covariance matrix of
$(\widetilde{\sigma}_{u}^{T},\widetilde{\tau}_{u}^{T},\widetilde{\sigma}_{u}^{T}\otimes\widetilde{\tau}_{u}^{T})^{T}$
has the following expression:

$\Sigma=\begin{bmatrix}V&0&V\otimes{\bf p}^{T}\\\ 0&V&{\bf p}^{T}\otimes V\\\
V\otimes{\bf p}&{\bf p}\otimes V&V_{2}\end{bmatrix},$

where $V=Var(\widetilde{\sigma}_{u})=pI_{k}-p^{2}J_{k}$, ${\bf
p}=E(\widetilde{\sigma}_{u})$, $V_{2}=p^{2}I_{k^{2}}-p^{4}J_{k^{2}}$,
$J_{k^{2}}$ is an $k^{2}\times k^{2}$ order matrix with all elements 1.
Besides, $V^{2}=pV$, $V_{2}^{2}=p^{2}V_{2}$. Let

$R=\begin{bmatrix}I_{k}&0&-I_{k}\otimes{\bf p}^{T}\\\ 0&I_{k}&-{\bf
p}^{T}\otimes I_{k}\\\ 0&0&I_{k^{2}}\end{bmatrix},\
\Lambda=\begin{bmatrix}V&0&0\\\ 0&V&0\\\ 0&0&\Omega_{2}\end{bmatrix},\
\Lambda_{1}=\begin{bmatrix}\frac{1}{\sqrt{p}}V&0&0\\\
0&\frac{1}{\sqrt{p}}V&0\\\
0&0&\frac{1}{p}\Omega_{2}\end{bmatrix},A=\begin{bmatrix}c_{1}I_{k}&0&0\\\
0&c_{1}I_{k}&0\\\ 0&0&c_{2}I_{k^{2}}\end{bmatrix}$

where $\Omega_{2}=V_{2}-p^{2}V\otimes J_{k}-p^{2}J_{k}\otimes V$ with
$\Omega_{2}^{2}=p^{2}\Omega_{2}$. Then $R^{T}\Sigma R=\Lambda$ and

$R^{-1}=\begin{bmatrix}I_{k}&0&I_{k}\otimes{\bf p}^{T}\\\ 0&I_{k}&{\bf
p}^{T}\otimes I_{k}\\\ 0&0&I_{k^{2}}\end{bmatrix},\ \
\Lambda_{1}R^{-1}A(R^{-1})^{T}\Lambda_{1}=\begin{bmatrix}0&0&0\\\ 0&0&0\\\
0&0&c_{2}\Omega_{2}\end{bmatrix}.$

Hence, $Z_{n}\rightarrow c_{2}p^{2}\chi^{2}_{(k-1)^{2}}$. Furthermore,
$\\{\exp(Z_{n})\\}_{n=1}^{\infty}$ is uniformly integrable if
$\kappa(k-1)^{2}<1$.

###### Proof of Theorem 2.5.

We check the conditions of Proposition 6.6. Let
$\lambda_{h}=\frac{1}{2h}\Big{(}\frac{a+(k^{m-1}-1)b}{k^{m-1}(m-2)!}\Big{)}^{h}$
and $\delta_{h}=(k-1)\Big{(}\frac{a-b}{a+(k^{m-1}-1)b}\Big{)}^{h}$. Condition
(A1) follows from Lemma 6.5.

Next, we check condition (A2). Let $S=\\{1,2,\dots,k\\}$ and
$H=(H_{hi})_{2\leq h\leq s,1\leq i\leq j_{s}}$ be a $sj_{s}$-tuple of $h$-edge
loose cycle $H_{hi}$ for any integers $s(\geq 2)$ and $j_{s}(\geq 1)$. Define
$X_{hn}$ as the number of $h$-edge loose cycles in the hypergraph and
$[x]_{j}=x(x-1)\dots(x-j+1)$. Note that for any sequence of positive integers
$j_{2}$,$\dots$, $j_{s}$, we have

$\mathbb{E}_{0}Y_{n}[X_{2n}]_{j_{2}}\dots[X_{sn}]_{j_{s}}=\sum_{H\in
B}\mathbb{E}_{0}Y_{n}1_{H}+\sum_{H\in\overline{B}}\mathbb{E}_{0}Y_{n}1_{H},$
(33)

where $B$ is the collection of disjoint tuples $H$ and $\overline{B}$ is the
complement, that is, any two tuples $H_{1}$ and $H_{2}$ in $\overline{B}$ have
at least one vertex in common. Direct computation yields

$\displaystyle\mathbb{E}_{0}Y_{n}1_{H}$ $\displaystyle=$
$\displaystyle\frac{1}{k^{n}}\sum_{\sigma\in
S^{n}}\mathbb{E}_{0}1_{H}\prod_{i\in
c(m,n)}\left(\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\right)^{A_{i_{1}:i_{m}}}\left(\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\right)^{1-A_{i_{1}:i_{m}}}$
$\displaystyle=$ $\displaystyle\frac{1}{k^{n}}\sum_{\sigma\in
S^{n}}\mathbb{E}_{0}1_{H}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\left(\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\right)^{A_{i_{1}:i_{m}}}\left(\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\right)^{1-A_{i_{1}:i_{m}}}$
$\displaystyle\times\mathbb{E}_{0}1_{H}\prod_{(i_{1},\dots,i_{m})\not\in\mathcal{E}(H)}\left(\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\right)^{A_{i_{1}:i_{m}}}\left(\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\right)^{1-A_{i_{1}:i_{m}}}$
$\displaystyle=$ $\displaystyle\frac{1}{k^{n}}\sum_{\sigma\in
S^{n}}\mathbb{E}_{0}1_{H}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\left(\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\right)^{A_{i_{1}:i_{m}}}\left(\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\right)^{1-A_{i_{1}:i_{m}}},$

where the second equality follows by the independence of $A_{i_{1}:i_{m}}$.
Define $\sigma^{1hi}$ and $\sigma^{2hi}$ to be the restrictions of $\sigma$ on
$\mathcal{V}(H_{hi})$ and $[n]\backslash\mathcal{V}(H_{hi})$. Similarly,
$\sigma^{1}$ and $\sigma^{2}$ are the restrictions of $\sigma$ on
$\mathcal{V}(H)$ and $[n]\backslash\mathcal{V}(H)$. Then by the above
equation, we have

$\displaystyle\mathbb{E}_{0}Y_{n}1_{H}$ $\displaystyle=$
$\displaystyle\frac{1}{k^{n}}\sum_{\sigma^{1}\in
S^{|\mathcal{V}(H)|}}\sum_{\sigma^{2}\in
S^{[n]/|\mathcal{V}(H)|}}\mathbb{E}_{0}1_{H}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\left(\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\right)^{A_{i_{1}:i_{m}}}\left(\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\right)^{1-A_{i_{1}:i_{m}}}$
$\displaystyle=$ $\displaystyle k^{-|\mathcal{V}(H)|}\sum_{\sigma^{1}\in
S^{|\mathcal{V}(H)|}}\mathbb{E}_{0}1_{H}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\left(\frac{p_{i_{1}:i_{m}}(\sigma^{1})}{p_{0}}\right)^{A_{i_{1}:i_{m}}}\left(\frac{q_{i_{1}:i_{m}}(\sigma^{1})}{q_{0}}\right)^{1-A_{i_{1}:i_{m}}}.$

Since $A_{i_{1}:i_{m}}=1$ for $(i_{1},\ldots,i_{m})\in\mathcal{E}(H)$, the
above equals

$\displaystyle k^{-M_{1}}p_{0}^{M_{1}}\sum_{\sigma^{1}\in
S^{|\mathcal{V}(H)|}}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\frac{p_{i_{1}:i_{m}}(\sigma^{1})}{p_{0}}=\mathbb{E}_{\sigma^{1}}\prod_{(u,v)\in\mathcal{E}(H)}p_{i_{1}:i_{m}}(\sigma^{1})$
$\displaystyle=$
$\displaystyle\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}\mathbb{E}_{\sigma^{1hi}}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H^{hi})}p_{i_{1}:i_{m}}(\sigma^{1hi})=\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}\mathbb{E}_{\sigma^{1hi}}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H^{hi})}\frac{M_{\sigma^{1hi}_{i_{1}},\dots,\sigma^{1hi}_{i_{m}}}}{n}$
$\displaystyle=$
$\displaystyle\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}E_{\tau_{hi}}\frac{M_{\tau_{i_{1}}^{hi}\dots\tau_{i_{m}}^{hi}}M_{\tau_{i_{m}}^{hi}\dots\tau_{2m-1}^{hi}}\dots
M_{\tau_{i_{(h-1)(m-1)}}^{hi}\dots\tau_{i_{1}}^{hi}}}{n^{h(m-1)}}$
$\displaystyle=$
$\displaystyle\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}\frac{Tr(M_{0}^{h})}{k^{h(m-1)}n^{h(m-1)}},$

where we used Lemma 6.4 for the last equality. Note
$\\#B=\frac{n!}{(n-M_{1})}\prod_{h=2}^{k}(\frac{1}{2h(m-2)!^{h}})^{j_{h}}$,
where $M_{1}=(m-1)\sum_{h=2}^{s}hj_{h}$. Hence, by Lemma 6.3, the first term
in (33) is

$\displaystyle\\#B\times\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}\frac{Tr(M_{0}^{h})}{k^{h(m-1)}n^{h(m-1)}}$
$\displaystyle=$
$\displaystyle\frac{n!}{(n-M_{1})!n^{M_{1}}}\prod_{h=2}^{s}\left[\frac{1}{2h(m-2)!^{h}}\left(d^{h}+\frac{(k-1)(a-b)^{h}}{k^{m-1}}\right)\right]^{j_{h}}$
$\displaystyle=$
$\displaystyle\frac{n!}{(n-M_{1})!n^{M_{1}}}\prod_{h=2}^{s}\left[\lambda_{h}(1+\delta_{h})\right]^{j_{h}}\rightarrow\prod_{h=2}^{s}\left[\lambda_{h}(1+\delta_{h})\right]^{j_{h}}.$

For $H\in\overline{B}$, one has

$\displaystyle\mathbb{E}_{0}Y_{n}1_{H}$ $\displaystyle=$ $\displaystyle
k^{-n}\sum_{\sigma\in
S^{n}}\mathbb{E}_{0}1_{H}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\left(\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\right)^{A_{i_{1}:i_{m}}}\left(\frac{q_{i_{1}:i_{m}}(\sigma)}{q_{0}}\right)^{1-A_{i_{1}:i_{m}}}$
$\displaystyle=$ $\displaystyle k^{-n}\sum_{\sigma\in
S^{n}}\left(\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\frac{p_{i_{1}:i_{m}}(\sigma)}{p_{0}}\right)P_{0}(H)$
$\displaystyle\leq$ $\displaystyle
k^{-n}p_{0}^{|\mathcal{V}(H)|}\sum_{\sigma\in
S^{n}}p_{0}^{-|\mathcal{V}(H)|}\left(\frac{a}{n^{m-1}}\right)^{|\mathcal{V}(H)|}=\left(\frac{a}{n^{m-1}}\right)^{|\mathcal{V}(H)|}.$

Then it follows that

$\sum_{\text{ $H^{\prime}$ isomorphic to
$H$}}\mathbb{E}_{0}Y_{n}1_{H}\leq\left(\frac{a}{n^{m-1}}\right)^{|\mathcal{V}(H)|}\binom{n}{|\mathcal{V}(H)|}|\mathcal{V}(H)|!\rightarrow
0,$

and $\sum_{H\in\overline{B}}\mathbb{E}_{0}Y_{n}1_{H}\rightarrow 0$. Hence,
$\mathbb{E}_{0}Y_{n}[X_{2n}]_{j_{2}}\dots[X_{sn}]_{j_{s}}\rightarrow\prod_{h=2}^{s}[\lambda_{h}(1+\delta_{h})]^{j_{h}}$.

Then we check condition (A3). By (A1) and (A2), we have
$\frac{\mu_{h}}{\lambda_{h}}-1=\frac{\lambda_{h}(1+\delta_{h})}{\lambda_{h}}-1=\delta_{h}$.
Besides,
$\lambda_{h}\delta_{h}^{2}=\frac{1}{2h}\Big{(}\frac{(a-b)^{2}}{k^{m-1}(m-2)!(a+(k^{m-1}-1)b)}\Big{)}^{h}=\frac{\kappa^{h}}{2h}$.
If $\kappa<1$, then $\sum_{h=2}^{\infty}\lambda_{h}\delta_{h}^{2}<\infty$.

Lastly, we check condition (A4). Note that

$\displaystyle\mathbb{E}_{0}Y_{n}^{2}$ $\displaystyle=$
$\displaystyle(1+o(1))\exp\Big{\\{}\frac{1}{n^{m-1}d}\Big{(}\binom{n}{m}(b-d)^{2}+(a-b)^{2}\sum_{i\in
c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]$
$\displaystyle+(a-b)(b-d)(\sum_{i\in
c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]+\sum_{i\in
c(m,n)}I[\eta_{i_{1}}:\eta_{i_{m}}])\Big{)}\Big{\\}}.$

Let $C=\\{(i_{1},\dots,i_{m})|\exists
i_{s},i_{t}:i_{s}=i_{t},i_{s^{\prime}}\neq i_{t^{\prime}}\ if\
s^{\prime},t^{\prime}\notin\\{s,t\\}\\}$. Then

$\sum_{i_{1},i_{2},\dots,i_{m}}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]=m!\sum_{i\in
c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]+\sum_{C}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]+O(n^{m-2}).$

Direct computation yields

$\displaystyle\sum_{i\in
c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{i_{1},i_{2},\dots,i_{m}}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]-\frac{1}{m!}\sum_{C}I[\sigma_{i_{1}}:\sigma_{i_{m}}]I[\eta_{i_{1}}:\eta_{i_{m}}]+O(n^{m-2})$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\sum_{s,t=1}^{k}(\sqrt{n}\tilde{\rho}_{st}+\frac{n}{k^{2}})^{m}-\frac{1}{m!}\binom{m}{2}\sum_{s,t=1}^{k}(\sqrt{n}\tilde{\rho}_{st}+\frac{n}{k^{2}})^{m-1}+O(n^{m-2})$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\frac{n^{m}}{k^{2m-2}}+\frac{1}{m!}\frac{\binom{m}{2}n^{m-1}}{k^{2(m-2)}}\sum_{s,t=1}^{k}\tilde{\rho}_{st}^{2}\Big{[}1+\sum_{i=1}^{m-2}\frac{1}{k^{2i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{st}}{\sqrt{n}}\Big{)}^{i}\Big{]}$
$\displaystyle-\frac{\binom{m}{2}}{m!}\frac{k^{2}n^{m-1}}{k^{2(m-1)}}-\frac{\binom{m}{2}n^{m-1}}{m!}\sum_{s,t=1}^{k}\sum_{i=1}^{m-1}\binom{m-1}{i}\frac{1}{k^{2(m-1-i)}}\Big{(}\frac{\tilde{\rho}_{st}}{\sqrt{n}}\Big{)}^{i}+O(n^{m-2}).$

Similarly, one gets

$\displaystyle\sum_{i\in c(m,n)}I[\sigma_{i_{1}}:\sigma_{i_{m}}]$
$\displaystyle=$
$\displaystyle\frac{1}{m!}\frac{n^{m}}{k^{m-1}}+\frac{1}{m!}\frac{\binom{m}{2}n^{m-1}}{k^{(m-2)}}\sum_{s=1}^{k}\tilde{\rho}_{s0}^{2}\Big{[}1+\sum_{i=1}^{m-2}\frac{1}{k^{i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{s0}}{\sqrt{n}}\Big{)}^{i}\Big{]}$
$\displaystyle-\frac{\binom{m}{2}}{m!}\frac{kn^{m-1}}{k^{(m-1)}}-\frac{\binom{m}{2}n^{m-1}}{m!}\sum_{s=1}^{k}\sum_{i=1}^{m-1}\binom{m-1}{i}\frac{1}{k^{(m-1-i)}}\Big{(}\frac{\tilde{\rho}_{s0}}{\sqrt{n}}\Big{)}^{i}+O(n^{m-2})$

and

$\displaystyle\sum_{i\in c(m,n)}I[\eta_{i_{1}}:\eta_{i_{m}}]$ $\displaystyle=$
$\displaystyle\frac{1}{m!}\frac{n^{m}}{k^{m-1}}+\frac{1}{m!}\frac{\binom{m}{2}n^{m-1}}{k^{(m-2)}}\sum_{t=1}^{k}\tilde{\rho}_{0t}^{2}\Big{[}1+\sum_{i=1}^{m-2}\frac{1}{k^{i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{0t}}{\sqrt{n}}\Big{)}^{i}\Big{]}$
$\displaystyle-\frac{\binom{m}{2}}{m!}\frac{kn^{m-1}}{k^{(m-1)}}-\frac{\binom{m}{2}n^{m-1}}{m!}\sum_{t=1}^{k}\sum_{i=1}^{m-1}\binom{m-1}{i}\frac{1}{k^{(m-1-i)}}\Big{(}\frac{\tilde{\rho}_{0t}}{\sqrt{n}}\Big{)}^{i}+O(n^{m-2}).$

Note that
$\binom{n}{m}=\frac{n^{m}}{m!}-\frac{\binom{m}{2}}{m!}n^{m-1}+O(n^{m-2})$ and

$\frac{n^{m}}{m!}\Big{(}\frac{(a-b)^{2}}{k^{2(m-2)}}+\frac{2(a-b)(b-d)}{k^{m-1}}+(b-d)^{2}\Big{)}=\frac{n^{m}}{m!}\Big{(}\frac{a-b}{k^{m-1}}+(b-d)\Big{)}^{2}=0,$

$\frac{\binom{m}{2}n^{m-1}}{m!}\Big{(}\frac{k^{2}(a-b)^{2}}{k^{2(m-1)}}+\frac{2k(a-b)(b-d)}{k^{m-1}}+(b-d)^{2}\Big{)}=\frac{\binom{m}{2}n^{m-1}}{m!}\frac{(k-1)^{2}(a-b)^{2}}{k^{2(m-1)}}.$

Let $c_{1}=\frac{\binom{m}{2}}{m!d}\frac{(a-b)(b-d)}{k^{m-2}}$ and
$c_{2}=\frac{\binom{m}{2}}{m!d}\frac{(a-b)^{2}}{k^{2(m-2)}}$. Since
$|\frac{\tilde{\rho}_{st}}{\sqrt{n}}|\leq 1$,
$|\frac{\tilde{\rho}_{0t}}{\sqrt{n}}|\leq 1$,
$|\frac{\tilde{\rho}_{t0}}{\sqrt{n}}|\leq 1$ and
$|\frac{\tilde{\rho}_{st}}{\sqrt{n}}|\rightarrow 0$,
$|\frac{\tilde{\rho}_{0t}}{\sqrt{n}}|\rightarrow 0$,
$|\frac{\tilde{\rho}_{t0}}{\sqrt{n}}|\rightarrow 0$ in probability. Hence,

$\displaystyle\tilde{Z}_{n}$ $\displaystyle=$ $\displaystyle
c_{2}\sum_{s,t=1}^{k}\tilde{\rho}_{st}^{2}\Big{[}1+\sum_{i=1}^{m-2}\frac{1}{k^{2i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{st}}{\sqrt{n}}\Big{)}^{i}\Big{]}$
$\displaystyle+c_{1}\Big{(}\sum_{t=1}^{k}\tilde{\rho}_{0t}^{2}\Big{[}1+\sum_{i=1}^{m-2}\frac{1}{k^{i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{0t}}{\sqrt{n}}\Big{)}^{i}\Big{]}+\sum_{s=1}^{k}\tilde{\rho}_{s0}^{2}\Big{[}1+\sum_{i=1}^{m-2}\frac{1}{k^{i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{s0}}{\sqrt{n}}\Big{)}^{i}\Big{]}\Big{)}$

and
$Z_{n}=c_{2}\sum_{s,t=1}^{k}\tilde{\rho}_{st}^{2}+c_{1}\Big{(}\sum_{t=1}^{k}\tilde{\rho}_{0t}^{2}+\sum_{s=1}^{k}\tilde{\rho}_{s0}^{2}\Big{)}$
are asymptotically equivalent.

If $\tau_{1}(m,k)\leq 1$, then
$1+\sum_{i=1}^{m-2}\frac{1}{k^{i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{s0}}{\sqrt{n}}\Big{)}^{i}\geq
0$, hence

$\tilde{Z}_{n}\leq
c_{2}\sum_{s,t=1}^{k}\tilde{\rho}_{st}^{2}\Big{[}1+\sum_{i=1}^{m-2}\frac{1}{k^{2i}}\frac{\binom{m}{i+2}}{\binom{m}{2}}\Big{(}\frac{\tilde{\rho}_{st}}{\sqrt{n}}\Big{)}^{i}\Big{]}\leq
c_{2}\tau_{2}(m)\sum_{s,t=1}^{k}\tilde{\rho}_{st}^{2}.$

Let
$f_{j}=\frac{1}{\sqrt{n}}\sum_{u=1}^{j}\Big{(}\left(1_{[\sigma_{u}=1]}1_{[\eta_{u}=1]}-\frac{1}{k^{2}}\right),\dots,\left(1_{[\sigma_{u}=k]}1_{[\eta_{u}=k]}-\frac{1}{k^{2}}\right)\Big{)}^{T}$
and $d_{j}=f_{j}-f_{j-1}$. Then
$\|d_{j}\|^{2}=\frac{1}{n}\frac{k^{2}-1}{k^{2}}$ and
$b_{*}^{2}=\sum_{j=1}^{n}\|d_{j}\|^{2}=\frac{k^{2}-1}{k^{2}}$. By Theorem 3.5
in Pinelis ([45]), for any $t>0$,

$\displaystyle
P\Bigg{(}\exp\left\\{c_{2}\tau_{2}(m)\|f_{n}\|^{2}\right\\}>t\Bigg{)}$
$\displaystyle=$ $\displaystyle
P\Bigg{(}c_{2}\tau_{2}(m)\|f_{n}\|^{2}>\log(t)\Bigg{)}=P\left(\|f_{n}\|>\sqrt{\frac{\log(t)}{c_{2}\tau_{2}(m)}}\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{\log(t)}{\kappa(k^{2}-1)\tau_{2}(m)}\right)=2t^{-\frac{1}{\kappa(k^{2}-1)\tau_{2}(m)}}.$

Hence, the condition $\kappa(k^{2}-1)\tau_{2}(m,k)<1$ implies that
$\\{\exp(\tilde{Z}_{n})\\}_{n=1}^{\infty}$ is uniformly integrable.

By Lemma 6.7, we conclude that $Z_{n}$ converges to
$\frac{c_{2}}{k^{2}}\chi^{2}_{(k-1)^{2}}$. Since
$\kappa(k^{2}-1)\tau_{2}(m,k)<1$ implies $\kappa(k-1)^{2}<1$ and
$\frac{c_{2}}{k^{2}}<\frac{1}{2}$, then it follows that

$\displaystyle\mathbb{E}_{0}Y_{n}^{2}$ $\displaystyle\rightarrow$
$\displaystyle\exp\Big{\\{}-\frac{\binom{m}{2}}{m!d}\frac{(k-1)^{2}(a-b)^{2}}{k^{2(m-1)}}\Big{\\}}\mathbb{E}\exp\Big{\\{}\frac{c_{2}}{k^{2}}\chi^{2}_{(k-1)^{2}}\Big{\\}}$
$\displaystyle=$
$\displaystyle\exp\Big{\\{}-\frac{\binom{m}{2}}{m!d}\frac{(k-1)^{2}(a-b)^{2}}{k^{2(m-1)}}\Big{\\}}\exp\Big{\\{}-\frac{(k-1)^{2}}{2}\log\Big{(}1-2\frac{c_{2}}{k^{2}}\Big{)}\Big{\\}}=\exp\Big{\\{}\sum_{h=2}^{\infty}\lambda_{h}\delta_{h}^{2}\Big{\\}},$

where we used the fact that

$\frac{(k-1)^{2}}{2}\Big{(}\frac{2c_{2}}{k^{2}}\Big{)}^{h}\frac{1}{h}=\frac{(k-1)^{2}}{2h}\Big{(}\frac{a+(k^{m-1}-1)b}{k^{m-1}(m-2)!}\Big{)}^{h}\Big{(}\frac{(a-b)^{2}}{(a+(k^{m-1}-1)b)^{2}}\Big{)}^{h}=\lambda_{h}\delta_{h}^{2}.$

Obviously, $\mathbb{E}_{0}Y_{n}=1$. Hence, $H_{0}$ and $H_{1}$ are contiguous.
∎

###  6.5 Proof of Theorem 2.7 and Theorem 2.8.

The proof relies on the following lemma.

######  Lemma 6.8.

Under the condition of Theorem 2.7, we have

$\mathbb{E}(\widehat{E}-E)^{2}=O\Big{(}\frac{a_{1}^{2}}{n}\Big{)},$ (34)
$\mathbb{E}(\widehat{V}-V)^{2}=O\Big{(}\frac{a_{1}^{4}}{n}\Big{)},$ (35)
$\mathbb{E}(\widehat{T}-T)^{2}=O\Big{(}\frac{a_{1}^{3}}{n^{3(m-l)}}\Big{)},$
(36)
$\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}(\widehat{T}-T)}{\sqrt{T}}\stackrel{{\scriptstyle
d}}{{\rightarrow}}N(0,1).$ (37)

###### Proof of Theorem 2.7.

It is easy to check the following expansion

$\displaystyle\widehat{T}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{3}$
$\displaystyle=$ $\displaystyle
T-\Big{(}\frac{V}{E}\Big{)}^{3}+(\widehat{T}-T)$ (38)
$\displaystyle+\Big{(}\frac{V}{E}-\frac{\widehat{V}}{\widehat{E}}\Big{)}^{3}-3\frac{V}{E}\Big{(}\frac{V}{E}-\frac{\widehat{V}}{\widehat{E}}\Big{)}^{2}+3\Big{(}\frac{V}{E}\Big{)}^{2}\frac{V-\widehat{V}}{E}$
$\displaystyle-3\Big{(}\frac{V}{E}\Big{)}^{2}\Big{(}\frac{1}{\widehat{E}}-\frac{1}{E}\Big{)}V-3\Big{(}\frac{V}{E}\Big{)}^{2}\Big{(}\frac{1}{\widehat{E}}-\frac{1}{E}\Big{)}(\widehat{V}-V).$

By Lemma 6.8, the first two terms in (38) are the leading terms and hence we
have

$\displaystyle\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}\Big{(}\widehat{T}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{3}\Big{)}}{\sqrt{T}}-\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}\Big{(}T-\Big{(}\frac{V}{E}\Big{)}^{3}\Big{)}}{\sqrt{T}}$
$\displaystyle=$
$\displaystyle\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}\Big{(}\widehat{T}-T\Big{)}}{\sqrt{T}}\stackrel{{\scriptstyle
d}}{{\rightarrow}}N(0,1).$

Since $\widehat{T}=T+o_{P}(1)$, we have

$\frac{\sqrt{\binom{n}{3(m-l)}(m-l)}\Big{(}\widehat{T}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{3}\Big{)}}{\sqrt{\widehat{T}}}-\delta\stackrel{{\scriptstyle
d}}{{\rightarrow}}N(0,1),$

which completes the proof. ∎

###### Proof of Theorem 2.8.

We rewrite the statistic as

$\displaystyle
2\sqrt{\binom{n}{3(m-l)}(m-l)}\Bigg{(}\sqrt{\widehat{T}}-\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{\frac{3}{2}}\Bigg{)}$
$\displaystyle=$ $\displaystyle
2\sqrt{\binom{n}{3(m-l)}(m-l)}\frac{T-\Big{(}\frac{V}{E}\Big{)}^{3}}{\sqrt{\widehat{T}}+\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{\frac{3}{2}}}+2\sqrt{\binom{n}{3(m-l)}(m-l)}\frac{\widehat{T}-T}{\sqrt{\widehat{T}}+\Big{(}\frac{\widehat{V}}{\widehat{E}}\Big{)}^{\frac{3}{2}}}+o_{P}(1).$

The first term is of the same order as $\delta$, while the second term is
bounded in probability. Hence, we get the desired result. ∎

## References

  * [1] Abbe, E. (2017). Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18, 1-86.
  * [2] Abbe, E. and Sandon, C. (2017). Proof of the achievability conjectures for the general stochastic block model. Communications on Pure and Applied Mathematics, 71(7), 1334-1406.
  * [3] Agarwal, S., Branson, K. and Belongie, S. (2006). Higher order learning with graphs. Proceedings of the International Conference on Machine Learning, 17-24.
  * [4] Amini, A., Chen, A. and Bickel, P. (2013). Pseudo-likelihood methods for community detection in large sparse networks. Annals of Statistics, 41(4), 2097-2122.
  * [5] Angelini, M., Caltagirone,F., Krzakala, F. and Zdeborova, L. (2015). Spectral detection on sparse hypergraphs. Allerton Conference on Communication, Control, and Computing, 66–73.
  * [6] Banerjee, D. (2018). Contiguity and non-reconstruction results for planted partition models: the dense case. Electronic Journal of Probability, 23, 1-28.
  * [7] Bolla, M. (1993). Spectra, euclidean representations and clusterings of hypergraphs. Discrete Mathematics, 117(1), 19-39.
  * [8] Bollobás, B. (2001). Random Graphs. Cambridge University Press, second edition.
  * [9] Bollobás, B. and Erdös, P. (1976). Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 80, 419-427.
  * [10] Banerjee, D. and Ma, Z. (2017). Optimal hypothesis testing for stochastic block models with growing degrees. https://arxiv.org/pdf/1705.05305.pdf.
  * [11] Bankds, J., Moore, C., Neeman, J. and Netrapalli, P. (2016). Information-theoretic thresholds for community detection in sparse networks. JMLR: Workshop and Conference Proceedings 49, 1-34.
  * [12] Bickel, P. J. and Sarkar, P. (2016). Hypothesis testing for automated community detection in networks. Journal of Royal Statistical Society, Series B, 78, 253-273.
  * [13] Chertok, M. and Keller, Y. (2010). Efficient high order matching. IEEE Trans. on Pattern Analysis and Machine Intelligence, 32(12), 2205-2215.
  * [14] Chen, J. and Yuan,B. (2006). Detecting functional modules in the yeast proteinprotein interaction network. Bioinformatics, 22(18), 2283-2290.
  * [15] Decelle, A., Krzakala, F., Moore, C., and Zdeborová, F. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physics Review E, 84, 066-106.
  * [16] Erdös, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. , 5, 17-61.
  * [17] Estrada, E. and Rodriguez-velasquez, J. (2005). Complex networks as hypergraphs. https://arxiv.org/ftp/physics/papers/0505/0505137.pdf
  * [18] Fortunato,S. (2010). Community detection in graphs. Physics Reports, 486 (3-5), 75-174.
  * [19] Fosdick, B. K. and Hoff, P. D. (2015). Testing and modeling dependencies between a network and nodal attributes. Journal of the American Statistical Association, 110, 1047-1056.
  * [20] Frieze, A. and Karonski, M. (2015). Introduction to random graphs. Cambridge University Press.
  * [21] Govindu, V. M. (2005). A tensor decomposition for geometric grouping and segmentation.  IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 1150-1157.
  * [22] Ghoshdastidar, D. and Dukkipati, A. (2014). Consistency of spectral partitioning of uniform hypergraphs under planted partition model.  Advances in Neural Information Processing Systems (NIPS), 397-405.
  * [23] Ghoshdastidar, D. and Dukkipati A. (2017). Consistency of spectral hypergraph partitioning under planted partition model. The Annals of Statistics, 45(1), 289-315.
  * [24] Gibson, D., Kleinberg, J. and Raghavan, P. (2000). Clustering categorical data: An approach based on dynamical systems. VLDB Journal, 8, 222-236.
  * [25] Gao, C. and Lafferty, J. (2017a). Testing for global network structure using small subgraph statistics. https://arxiv.org/pdf/1710.00862.pdf
  * [26] Gao, C. and Lafferty, J. (2017b). Testing network structure using relations between small subgraph probabilities. https://arxiv.org/pdf/1704.06742.pdf
  * [27] Gao, C., Ma, Z., Zhang, A.Y. and Zhou, H. H. (2016). Community detection in degree-corrected block models. https://arxiv.org/pdf/1607.06993.pdf.
  * [28] Gao, Z. and Wormald, N. (2004). Asymptotic normality determined by high moments, and submap counts of random maps. Probab. Theory Relat. Fields, 130(3), 368–376.
  * [29] Ghoshal, G., Zlatic, V., Caldarelli, G. and Newman, M. E. J. (2009). Random hypergraphs and their applications. Physical Review E 79.
  * [30] Goldenberg, A., Zheng, A. X. S., Fienberg, E., and Airoldi, E. M. (2010). A survey of statistical network models. Foundations and Trends in Machine Learning 2, 2, 129-233.
  * [31] Hall, P. and Heyde, C. C. (2014). Martingale limit theory and its application. Academic press.
  * [32] Janson, S. (1995). Random regular graphs: asymptotic distributions and contiguity. Combinatorics, Probability and Computing, 4, 369–405.
  * [33] Kim, C., Bandeira,A. and Goemans, M. (2017). Community detection in hypergraphs, spiked tensor models, and sum-of-squares. 2017 International Conference on Sampling Theory and Applications (SampTA), 124-128.
  * [34] Lei, J. (2016). A goodness-of-fit test for stochastic block models. Annals of Statistics, 44, 401-424.
  * [35] Lin, C., Chien, I. and Wang, I. (2017). On the fundamental statistical limit of community detection in random hypergraphs.  Information Theory (ISIT), 2017 IEEE International Symposium , 2178-2182.
  * [36] Leskovec, J., Lang, K. L., Dasgupta, A. and Mahoney, M. W. (2008). Statistical properties of community structure in large social and information networks. Proceeding of the 17th international conference on World Wide Web, 695-704. ACM.
  * [37] Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1), 215-237.
  * [38] Michoel, T. and Nachtergaele, B. (2012). Alignment and integration of complex networks by hypergraph-based spectral clustering. Physical Review E 86.
  * [39] Mossel, E., Neeman, J. and Sly, A. (2015). Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162, 431-461.
  * [40] Mossel, E., Neeman, J. and Sly, A. (2017). A proof of the block model threshold conjecture. Combinatorica, 1-44.
  * [41] Montanari, A. and Sen, S. (2016). Semidefinite programs on sparse random graphs and their application to community detection. STOC ’16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 814-827.
  * [42] Newman, M. (2001). Scientific collaboration networks. I. Network construction and fundamental results. Physical Review E, 64, 016-131.
  * [43] Neeman, J. and Netrapalli, P. (2014). Non-reconstructability in the stochastic block model. https://arxiv.org/abs/1404.6304
  * [44] Ouvrard, X., Goff, J. and Marchand-Maillet, S. (2017). Networks of Collaborations: hypergraph modeling and visualisation, https://arxiv.org/pdf/1707.00115.pdf.
  * [45] Pinelis, I. (1994). Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probability, 22(4), 1679-1706.
  * [46] Rodriguez, J. A. (2009). Laplacian eigenvalues and partition problems in hypergraphs. Applied Mathematics Letters, 22(6), 916-921.
  * [47] Ramasco, J., Dorogovtsev, S. N. and Pastor-Satorras, R. (2004). Self-organization of collaboration networks, Phys. Rev. E 70, 036-106.
  * [48] Rota Bulo, S. and Pelillo, M. (2013). A game-theoretic approach to hypergraph clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(6), 1312-1327.
  * [49] Shi, J. and Malik, J. (1997). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888-905.
  * [50] Wormald, N. C. (1999). Models of random regular graphs. London Mathematical Society Lecture Note Series, 239-298. Cambridge University Press.
  * [51] Yuan, M., Feng, Y. and Shang, Z. (2018a). A likelihood-ratio type test for stochastic block models with bounded degrees. https://arxiv.org/pdf/1807.04426.pdf
  * [52] Yuan, M., Feng, Y. and Shang, Z. (2018b). Inference on multi-community stochastic block models with bounded degree. Manuscript.
  * [53] Zhao, Y., Levina, E. and Zhu., J.(2011). Community extraction for social networks. Proc. Natn. Acad. Sci. USA, 108, 7321-7326.
  * [54] Zhao, Y., Levina, E. and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. Annals of Statistics, 40, 2266-2292.

Supplement to

Testing Community Structure for Hypergraphs

This supplement contains the proofs of Lemmas 6.3, 6.4, 6.5, 6.7, 6.8 and
Proposition 2.6.

###### Proof of Lemma 6.3.

Note that $M_{0}=(a-b)I+k^{m-2}bJ$, where $I$ is $k\times k$ identity matrix
and $J$ is $k\times k$ matrix with every entry 1. For any real number
$\lambda$, we have

$\displaystyle M_{0}-\lambda
I=(a-b-\lambda)I+k^{m-2}bJ=k^{m-2}b\Big{(}J-\frac{\lambda-a+b}{k^{m-2}b}I\Big{)}.$

Then $det(M_{0}-\lambda I)=0$ implies that
$det(J-\frac{\lambda-a+b}{k^{m-2}b}I)=0$. The eigenvalue of $J$ are $k$ and 0
with multiplicity $k-1$, which implies $\lambda=a-b$, $a+(k^{m-2}-1)b$ and the
desired result follows. ∎

###### Proof of Lemma 6.4.

Let $I_{j}=(i_{(j-1)m-j+3},\dots,i_{jm-j})$. Then we have

$\displaystyle\sum_{i_{1},\dots,i_{jm-j}\in\\{1,\dots,k\\}}M_{i_{1}i_{2}\dots
i_{m}}M_{i_{m}\dots i_{2m-1}}M_{i_{2m-1}\dots i_{3m-2}}\dots
M_{i_{(j-1)m-(j-2)}\dots i_{jm-j}i_{1}}$ $\displaystyle=$
$\displaystyle\sum_{I_{1},I_{2},\dots,I_{j}}\sum_{i_{1},i_{m},i_{2m-1},\dots,i_{(j-1)m-(j-2)}\in\\{1,2,\dots,k\\}}M_{i_{1}I_{1}i_{m}}M_{i_{m}I_{2}i_{2m-1}}\dots
M_{i_{(j-1)m-(j-2)}I_{j}i_{1}}$ $\displaystyle=$
$\displaystyle\sum_{I_{1},I_{2},\dots,I_{j}}Tr\Big{(}M(I_{1})M(I_{2})\dots
M(I_{j})\Big{)},$

where $M(I_{t})=(M_{iI_{t}s})_{i,s=1}^{k}$ is a $k\times k$ matrix. By the
definition of $M_{i_{1}i_{2}\dots i_{m}}$, it follows that

$\displaystyle M(I_{t})$ $\displaystyle=$
$\displaystyle\begin{bmatrix}a&b&\dots&b\\\ b&b&\dots&b\\\
\vdots&\vdots&\dots&\vdots\\\
b&b&\dots&b\end{bmatrix}+\begin{bmatrix}b&b&\dots&b\\\ b&a&\dots&b\\\
\vdots&\vdots&\dots&\vdots\\\
b&b&\dots&b\end{bmatrix}+\dots+\begin{bmatrix}b&b&\dots&b\\\ b&b&\dots&b\\\
\vdots&\vdots&\dots&\vdots\\\ b&b&\dots&a\end{bmatrix}+\sum_{I_{t}:\
\mbox{elements are different}}M(I_{t})$ $\displaystyle=$
$\displaystyle\begin{bmatrix}a+(k-1)b&kb&\dots&kb\\\ kb&a+(k-1)b&\dots&kb\\\
\vdots&\vdots&\dots&\vdots\\\
kb&kb&\dots&a+(k-1)b\end{bmatrix}+(k^{m-2}-k)\begin{bmatrix}b&b&\dots&b\\\
b&b&\dots&b\\\ \vdots&\vdots&\dots&\vdots\\\ b&b&\dots&b\end{bmatrix}=M_{0},$

which completes the proof. ∎

###### Proof of Lemma 6.5.

Let $H$ be a graph on a subset of $[n]$ with vertex set $\mathcal{V}(H)$ and
edge set $\mathcal{E}(H)$. For any sequence of positive integers $j_{2}$,
$j_{3}$, $\dots$, $j_{s}$, we have

$\prod_{h=2}^{s}[X_{hn}]_{j_{h}}=\sum_{(H_{hi})}\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}1_{H_{hi}}.$

Then

$\displaystyle\mathbb{E}_{0}\prod_{h=2}^{s}[X_{hn}]_{j_{h}}=\sum_{(H_{hi})}\mathbb{E}_{0}\prod_{h=2}^{s}\prod_{i=1}^{j_{s}}1_{H_{si}}=\sum_{(H_{si})\in
B}\mathbb{E}_{0}\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}1_{H_{hi}}+\sum_{(H_{hi})\in\overline{B}}\mathbb{E}_{0}\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}1_{H_{hi}}.$
(39)

The summand in the first term of (39) can be calculated as below

$\displaystyle\mathbb{E}_{0}\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}1_{H_{hi}}=\mathbb{E}_{\tau}\mathbb{E}_{0}\left[\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}1_{H_{hi}}\Big{|}\tau\right]=\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}E_{\tau_{hi}}\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H_{hi})}\frac{d}{n^{m-1}}=\prod_{h=2}^{k}\prod_{i=1}^{j_{h}}\frac{d^{h}}{n^{h(m-1)}}.$

Note that
$\\#B=\frac{n!}{(n-M_{1})}\prod_{h=2}^{k}(\frac{1}{2h(m-2)!^{h}})^{j_{h}}$,
$M_{1}=(m-1)\sum_{h=2}^{s}hj_{h}$. Hence the first term in the right hand side
of (39) by Lemma 6.3 is

$\\#B\times\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}\frac{d^{h}}{k^{h(m-1)}n^{h(m-1)}}=\frac{n!}{(n-M_{1})!n^{M_{1}}}\prod_{h=2}^{s}\left[\frac{d^{h}}{2h(m-2)!^{h}}\right]^{j_{h}}\rightarrow\prod_{h=2}^{s}\lambda_{h}^{j_{h}}.$

For $(H_{hi})\in\overline{B}$, $H=\cup H_{hi}$ has at most $M_{1}-1$ vertices
and $\sum_{h=2}^{s}hj_{h}$ hyperedges, and hence
$|\mathcal{V}(H)|<|\mathcal{E}(H)|(m-1)$, and

$\mathbb{E}_{0}\prod_{h=2}^{s}\prod_{i=1}^{j_{h}}1_{H_{hi}}=\prod_{(i_{1},\dots,i_{m})\in\mathcal{E}(H)}\left(\frac{a}{n^{m-1}}\right)^{1_{[\tau_{u}=\tau_{v}]}}\left(\frac{b}{n^{m-1}}\right)^{1_{[\tau_{u}\neq\tau_{v}]}}\leq\left(\frac{a}{n^{m-1}}\right)^{|\mathcal{E}(H)|}.$

There are $\binom{n}{|\mathcal{V}(H)|}|\mathcal{V}(H)|!$ graphs isomorphic to
$H$. Then

$\sum_{\text{$H^{\prime}$ isomorphic to
$H$}}E_{1}[1_{H^{\prime}}|\tau]\leq\left(\frac{a}{n^{m-1}}\right)^{|\mathcal{E}(H)|}\binom{n}{|\mathcal{V}(H)|}|\mathcal{V}(H)|!\rightarrow
0.$

Since the number of isomorphism classes is bounded, the second term in the
right hand side of (39) goes to zero. Hence,
$\mathbb{E}_{0}\prod_{h=2}^{s}[X_{hn}]_{j_{h}}\rightarrow\prod_{h=2}^{s}\lambda_{h}^{j_{h}}$,
which completes the proof by Lemma 2.8 in Wormald ([50]). ∎

###### Proof of Lemma 6.7.

We only need to find
$Cov(\widetilde{\sigma}_{u},\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u})$,
$Cov(\widetilde{\tau}_{u},\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u})$
and $Var(\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u})$.

$\displaystyle
Cov(\widetilde{\sigma}_{u},\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u})=E[(\widetilde{\sigma}_{u}-{\bf
p})\widetilde{\sigma}_{u}^{T}\otimes\widetilde{\tau}_{u}^{T}]$
$\displaystyle=$ $\displaystyle
E\begin{bmatrix}(1[\sigma_{u}=1]-p)1[\sigma_{u}=1]\widetilde{\tau}_{u}^{T}&(1[\sigma_{u}=1]-p)1[\sigma_{u}=2]\widetilde{\tau}_{u}^{T}&\dots&(1[\sigma_{u}=1]-p)1[\sigma_{u}=k]\widetilde{\tau}_{u}^{T}\\\
(1[\sigma_{u}=2]-p)1[\sigma_{u}=1]\widetilde{\tau}_{u}^{T}&(1[\sigma_{u}=2]-p)1[\sigma_{u}=2]\widetilde{\tau}_{u}^{T}&\dots&(1[\sigma_{u}=2]-p)1[\sigma_{u}=k]\widetilde{\tau}_{u}^{T}\\\
\vdots&\vdots&\vdots&\vdots\\\
(1[\sigma_{u}=k]-p)1[\sigma_{u}=1]\widetilde{\tau}_{u}^{T}&(1[\sigma_{u}=k]-p)1[\sigma_{u}=2]\tau_{u}^{T}&\dots&(1[\sigma_{u}=k]-p)1[\sigma_{u}=k]\tau_{u}^{T}\\\
\end{bmatrix}$ $\displaystyle=$ $\displaystyle\begin{bmatrix}(p-p^{2}){\bf
p}^{T}&-p^{2}{\bf p}^{T}&\dots&-p^{2}{\bf p}^{T}\\\ -p^{2}{\bf
p}^{T}&-(p-p^{2}){\bf p}^{T}&\dots&-p^{2}{\bf p}^{T}\\\
\vdots&\vdots&\vdots&\vdots\\\ -p^{2}{\bf p}^{T}&-p^{2}{\bf
p}^{T}&\dots&-(p-p^{2}){\bf p}^{T}\\\ \end{bmatrix}=V\otimes{\bf p}^{T}.$

Similarly one can get
$Cov(\widetilde{\tau}_{u},\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u})={\bf
p}^{T}\otimes V$. The variance of
$\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u}$ can be calculated as

$\displaystyle
Cov(\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u},\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u})$
$\displaystyle=$ $\displaystyle
E[(\widetilde{\sigma}_{u}\otimes\widetilde{\tau}_{u}-{\bf p}\otimes{\bf
p})\widetilde{\sigma}_{u}^{T}\otimes\widetilde{\tau}_{u}^{T}]$
$\displaystyle=$ $\displaystyle
E\begin{bmatrix}(1[\sigma_{u}=1]\widetilde{\tau}_{u}-p{\bf
p})1[\sigma_{u}=1]\widetilde{\tau}_{u}^{T}&\dots&(1[\sigma_{u}=1]\widetilde{\tau}_{u}-p{\bf
p})1[\sigma_{u}=k]\widetilde{\tau}_{u}^{T}\\\
(1[\sigma_{u}=2]\widetilde{\tau}_{u}-p{\bf
p})1[\sigma_{u}=1]\widetilde{\tau}_{u}^{T}&\dots&(1[\sigma_{u}=2]\widetilde{\tau}_{u}-p{\bf
p})1[\sigma_{u}=k]\widetilde{\tau}_{u}^{T}\\\ \vdots&\vdots&\vdots\\\
(1[\sigma_{u}=k]\widetilde{\tau}_{u}-p{\bf
p})1[\sigma_{u}=1]\widetilde{\tau}_{u}^{T}&\dots&(1[\sigma_{u}=k]\widetilde{\tau}_{u}-p{\bf
p})1[\sigma_{u}=k]\tau_{u}^{T}\\\ \end{bmatrix}$ $\displaystyle=$
$\displaystyle\begin{bmatrix}p^{2}I_{k}-p^{4}J_{k}&-p^{4}J_{k}&\dots&-p^{4}J_{k}\\\
-p^{4}J_{k}&p^{2}I_{k}-p^{4}J_{k}&\dots&-p^{4}J_{k}\\\
\vdots&\vdots&\vdots&\vdots\\\
-p^{4}J_{k}&-p^{4}J_{k}&\dots&p^{2}I_{k}-p^{4}J_{k}\\\
\end{bmatrix}=p^{2}I_{k^{2}}-p^{4}J_{k^{2}}.$

Note that $(I_{k}\otimes{\bf p})V=V\otimes{\bf p}$, $V(I_{k}\otimes{\bf
p}^{T})=V\otimes{\bf p}^{T}$, $({\bf p}\otimes I_{k})V={\bf p}\otimes V$,
$V({\bf p}^{T}\otimes I_{k})={\bf p}^{T}\otimes V$. Direct computation yields
$R^{T}\Sigma R=\Lambda$ and

$\displaystyle\Lambda_{1}R^{-1}A(R^{-1})^{T}\Lambda_{1}$ $\displaystyle=$
$\displaystyle\Lambda_{1}\begin{bmatrix}I_{k}&0&I_{k}\otimes{\bf p}^{T}\\\
0&I_{k}&{\bf p}^{T}\otimes I_{k}\\\
0&0&I_{k^{2}}\end{bmatrix}\begin{bmatrix}c_{1}I_{k}&0&0\\\ 0&c_{1}I_{k}&0\\\
0&0&c_{2}I_{k^{2}}\end{bmatrix}\begin{bmatrix}I_{k}&0&0\\\ 0&I_{k}&0\\\
I_{k}\otimes{\bf p}&{\bf p}\otimes I_{k}&I_{k^{2}}\end{bmatrix}\Lambda_{1}$
$\displaystyle=$
$\displaystyle\Lambda_{1}\begin{bmatrix}c_{1}I_{k}&0&c_{2}I_{k}\otimes{\bf
p}^{T}\\\ 0&c_{1}I_{k}&c_{2}{\bf p}^{T}\otimes I_{k}\\\
0&0&c_{2}I_{k^{2}}\end{bmatrix}\begin{bmatrix}I_{k}&0&0\\\ 0&I_{k}&0\\\
I_{k}\otimes{\bf p}&{\bf p}\otimes I_{k}&I_{k^{2}}\end{bmatrix}\Lambda_{1}$
$\displaystyle=$
$\displaystyle\Lambda_{1}\begin{bmatrix}(c_{1}+c_{2}p)I_{k}&c_{2}p^{2}J_{k}&c_{2}I_{k}\otimes{\bf
p}^{T}\\\ c_{2}p^{2}J_{k}&(c_{1}+c_{2}p)I_{k}&c_{2}{\bf p}^{T}\otimes I_{k}\\\
c_{2}I_{k}\otimes{\bf p}&c_{2}{\bf p}\otimes
I_{k}&c_{2}I_{k^{2}}\end{bmatrix}\Lambda_{1}$ $\displaystyle=$
$\displaystyle\begin{bmatrix}\frac{I_{k}}{\sqrt{p}}&0&0\\\
0&\frac{I_{k}}{\sqrt{p}}&0\\\
0&0&\frac{I_{k}}{p}\end{bmatrix}\begin{bmatrix}(c_{1}+c_{2}p)V^{2}&c_{2}p^{2}VJ_{k}V&c_{2}V(I_{k}\otimes{\bf
p}^{T})\Omega_{2}\\\ c_{2}p^{2}VJ_{k}V&(c_{1}+c_{2}p)V^{2}&c_{2}V({\bf
p}^{T}\otimes I_{k})\Omega_{2}\\\ c_{2}\Omega_{2}(I_{k}\otimes{\bf
p})V&c_{2}\Omega_{2}({\bf p}\otimes
I_{k})V&c_{2}\Omega_{2}^{2}\end{bmatrix}\begin{bmatrix}\frac{I_{k}}{\sqrt{p}}&0&0\\\
0&\frac{I_{k}}{\sqrt{p}}&0\\\ 0&0&\frac{I_{k}}{p}\end{bmatrix}.$

Note that $VJ_{k}=J_{k}V=0$,

$c_{1}+c_{2}p=\frac{\binom{m}{2}}{m!d}\frac{(b-d)(a-b)}{k^{m-2}}+\frac{\binom{m}{2}}{m!d}\frac{(a-b)^{2}}{k^{2(m-2)}}\frac{1}{k}=0,$
$\displaystyle\Omega_{2}(I_{k}\otimes{\bf p})V$ $\displaystyle=$
$\displaystyle(V_{2}-p^{2}V\otimes J_{k}-p^{2}J_{k}\otimes V)(I_{k}\otimes{\bf
p})V$ $\displaystyle=$ $\displaystyle V_{2}(I_{k}\otimes{\bf
p})V-p(V\otimes{\bf p})V=p^{2}(V\otimes{\bf p})-p(V\otimes{\bf
p})(pI_{k}-p^{2}J_{k})=0,$

and $V({\bf p}^{T}\otimes I_{k})\Omega_{2}=V(I_{k}\otimes{\bf
p}^{T})\Omega_{2}=\Omega_{2}({\bf p}\otimes I_{k})V=0$, which yields the
desired result.

Let $Q=(\Lambda_{1}R^{-1})^{T}$ and $Z\sim N(0,I_{k^{2}})$. Then the
covariance matrix $\Sigma$ can be decomposed as

$\Sigma=(R^{-1})^{T}\Lambda
R^{-1}=(\Lambda_{1}R^{-1})^{T}(\Lambda_{1}R^{-1})=QQ^{T}.$

Hence

$\tilde{\rho}A\tilde{\rho}^{T}\rightarrow
Z^{T}Q^{T}AQZ=Z^{T}\Lambda_{1}R^{-1}A(R^{-1})^{T}\Lambda_{1}Z=c_{2}Z^{T}\Omega_{2}Z.$

Note $\Omega_{2}^{2}=p^{2}\Omega_{2}$ implies the eigenvalues of $\Omega_{2}$
are either 0 or $p^{2}$ and

$\displaystyle Tr(\Omega_{2})$ $\displaystyle=$ $\displaystyle
Tr\left(V_{2}-p^{2}V\otimes J_{k}-p^{2}J_{k}\otimes V\right)$ $\displaystyle=$
$\displaystyle Tr\left(p^{2}I_{k^{2}}-p^{3}I_{k}\otimes
J_{k}-p^{3}J_{k}\otimes I_{k}+p^{4}J_{k^{2}}\right)$ $\displaystyle=$
$\displaystyle
k^{2}p^{2}-p^{3}k^{2}-p^{3}k^{2}+p^{4}k^{2}=\frac{(k-1)^{2}}{k^{2}}.$

Hence $\Omega_{2}$ has $(k-1)^{2}$ eigenvalues $p^{2}$ with other eigenvalues
0. Then $c_{2}Z^{T}\Omega_{2}Z\sim c_{2}p^{2}\chi^{2}_{(k-1)^{2}}$.

Note that we can rewrite $Z_{n}$ as

$\displaystyle Z_{n}$ $\displaystyle=$
$\displaystyle\frac{\binom{m}{2}}{m!d}\frac{(a-b)^{2}}{k^{2(m-2)}}\Big{(}\sum_{s,t}^{k}\tilde{\rho}_{st}^{2}-\frac{1}{k}\Big{[}\sum_{s=1}^{k}\tilde{\rho}_{s0}^{2}+\sum_{t=1}^{k}\tilde{\rho}_{0t}^{2}\Big{]}\Big{)}$
$\displaystyle=$
$\displaystyle\frac{1}{2(m-2)!d}\frac{(a-b)^{2}}{k^{2(m-2)}}\sum_{s,t=1}^{k}\Big{(}\frac{1}{\sqrt{n}}\sum_{u=1}^{n}(I[\sigma_{u}=s]-\frac{1}{k})(I[\eta_{u}=t]-\frac{1}{k})\Big{)}^{2}.$

Let
$f_{j}=\frac{1}{\sqrt{n}}\sum_{u=1}^{j}\Big{(}\left(1_{[\sigma_{u}=1]}-\frac{1}{k}\right)\left(1_{[\eta_{u}=1]}-\frac{1}{k}\right),\dots,\left(1_{[\sigma_{u}=k]}-\frac{1}{k}\right)\left(1_{[\eta_{u}=k]}-\frac{1}{k}\right)\Big{)}^{T}$
and $d_{j}=f_{j}-f_{j-1}$. Then
$\|d_{j}\|^{2}=\frac{1}{n}\frac{(k-1)^{2}}{k^{2}}$ and
$b_{*}^{2}=\sum_{j=1}^{n}\|d_{j}\|^{2}=\frac{(k-1)^{2}}{k^{2}}$. By Theorem
3.5 in [45], we have for any $t>0$,

$\displaystyle
P\Bigg{(}\exp\left\\{\frac{1}{2(m-2)!d}\frac{(a-b)^{2}}{k^{2(m-2)}}\|f_{n}\|^{2}\right\\}>t\Bigg{)}$
$\displaystyle=$ $\displaystyle
P\Bigg{(}\frac{1}{2(m-2)!d}\frac{(a-b)^{2}}{k^{2(m-2)}}\|f_{n}\|^{2}>\log(t)\Bigg{)}$
$\displaystyle=$ $\displaystyle
P\left(\|f_{n}\|>\sqrt{\frac{\log(t)}{\frac{1}{2(m-2)!d}\frac{(a-b)^{2}}{k^{2(m-2)}}}}\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{\log(t)}{\kappa(k-1)^{2}}\right)=2t^{-\frac{1}{\kappa(k-1)^{2}}}.$

Hence, if $\kappa(k-1)^{2}<1$, $\\{\exp(Z_{n})\\}_{n=1}^{\infty}$ is uniformly
integrable. ∎

###### Proof of Proposition 2.6..

For convenience, we denote $a_{1}=\frac{a_{n}}{n^{m-1}}$ and
$b_{1}=\frac{b_{n}}{n^{m-1}}$. Under $H_{0}$, we have $a_{1}=b_{1}$, and then

$\mathcal{T}=(\mathbb{E}W_{1})^{3(m-2l)}\Big{[}b_{1}^{3}-\Big{(}\frac{b_{1}^{2}}{b_{1}}\Big{)}^{3}\Big{]}=0.$

Under $H_{1}$, $k\geq 2$ and $a_{1}>b_{1}$. For $l=1$, direct computation
yields

$\mathcal{T}=(\mathbb{E}W_{1})^{3(m-2)}\frac{(k-1)(a_{1}-b_{1})^{3}}{k^{3(m-1)}}\neq
0.$

Next we assume $l\geq 2$, let $E_{1}=(\mathbb{E}W_{1})^{-m}E$,
$V_{1}=(\mathbb{E}W_{1})^{-2(m-l)}V$ and
$T_{1}=(\mathbb{E}W_{1})^{-3(m-2l)}T$. Then

$\mathcal{T}=(\mathbb{E}W_{1})^{3(m-2l)}\Big{[}T_{1}-\Big{(}\frac{V_{1}}{E_{1}}\Big{)}^{3}\Big{]}.$

We calculate $T_{1}E_{1}^{3}-V_{1}^{3}$ to get the following

$\displaystyle T_{1}E_{1}^{3}-V_{1}^{3}$ $\displaystyle=$
$\displaystyle(a_{1}-b_{1})^{6}\frac{1-k^{-1}}{k^{6m-3l-4}}+3(a_{1}-b_{1})^{5}b_{1}\Big{(}\frac{k^{l}-2}{k^{5m-2l-3}}+\frac{1}{k^{5m-l-4}}\Big{)}$
(40)
$\displaystyle+3(a_{1}-b_{1})^{4}b_{1}^{2}\Big{(}\frac{k^{l}-1-k^{-2l+1}}{k^{4m-3l-2}}+\frac{1}{k^{4(m-1)}}\Big{)}$
$\displaystyle+(a_{1}-b_{1})^{3}b_{1}^{3}\Big{(}\frac{1-3k^{-2l+1}}{k^{3m-3l-1}}+\frac{2}{k^{3m-3}}\Big{)}.$

Clearly, if $k\geq 2$, $a_{1}>b_{1}>0$ and $l\geq 2$, each term in the right
hand side of (40) is positive, which implies that $T_{1}E_{1}^{3}-V_{1}^{3}>0$
and hence $\mathcal{T}\neq 0$. ∎

Before proving Lemma 6.8, we introduce some notation and preliminary. For any
tensors $A,B,C$, define

$\displaystyle C_{2m-l}(A,B)$ $\displaystyle=$ $\displaystyle
A_{i_{1}:i_{m}}B_{i_{m-l+1}:i_{2m-l}}+A_{i_{2}:i_{m+1}}B_{i_{m-l+2}:i_{2m-l}i_{1}}+\dots+A_{i_{2m-l}i_{1}:i_{m-1}}B_{i_{m-l}:i_{2m-l-1}},$
$\displaystyle C_{3(m-l)}(A,B,C)$ $\displaystyle=$ $\displaystyle
A_{i_{1}:i_{m}}B_{i_{m-l+1}:i_{2m-l}}C_{i_{2m-2l+1}:i_{3(m-l)}i_{1}:i_{l}}+A_{i_{2}:i_{m+1}}B_{i_{m-l+2}:i_{2m-l+1}}C_{i_{2m-2l+2}:i_{3(m-l)}i_{1}:i_{l+1}}$
$\displaystyle+\dots+A_{i_{m-l}:i_{2m-l-1}}B_{i_{2(m-l)}:i_{3(m-l)}i_{1}:i_{l-1}}C_{i_{3(m-l)}i_{1}:i_{m-1}}.$

The proof of Lemma 6.8 relies on the following high-moments driven asymptotic
result due to Hall and Heyde ([31]).

######  Theorem 6.9 (Hall and Heyde, 2014).

Suppose that for every $n\in\mathbb{N}$ and $k_{n}\rightarrow\infty$ the
random variables $X_{n,1},\dots,X_{n,k_{n}}$ are a martingale difference
sequence relative to an arbitrary filtration
$\mathcal{F}_{n,1}\subset\mathcal{F}_{n,2}$ $\subset$ $\dots$
$\mathcal{F}_{n,k_{n}}$. If (1)
$\sum_{i=1}^{k_{n}}\mathbb{E}(X_{n,i}^{2}|\mathcal{F}_{n,i-1})\rightarrow 1$
in probability, (2)
$\sum_{i=1}^{k_{n}}\mathbb{E}(X_{n,i}^{2}I[|X_{n,i}|>\epsilon]|\mathcal{F}_{n,i-1})\rightarrow
0$ in probability for every $\epsilon>0$, then
$\sum_{i=1}^{k_{n}}X_{n,i}\rightarrow N(0,1)$ in distribution.

###### Proof of Lemma 6.8.

Let $W_{i_{1}:i_{m}}=W_{i_{1}}W_{i_{2}}\dots W_{i_{m}}$,
$\eta_{i_{1}:i_{m}}=(a_{1}-b_{1})I[\sigma_{i_{1}}=\sigma_{i_{2}}=\dots=\sigma_{i_{m}}]+b_{1}$
and $\theta_{i_{1}:i_{m}}=\eta_{i_{1}:i_{m}}W_{i_{1}:i_{m}}$. Clearly
$\mathbb{E}(A_{i_{1}:i_{m}}|W,\sigma)=\theta_{i_{1}:i_{m}}$.

Firstly, we show equation (34). Write $\widehat{E}-E$ as

$\widehat{E}-E=\Big{(}\widehat{E}-\mathbb{E}(\widehat{E}|W,\sigma)\Big{)}+\Big{(}\mathbb{E}(\widehat{E}|W,\sigma)-\mathbb{E}(\widehat{E}|\sigma)\Big{)}+\Big{(}\mathbb{E}(\widehat{E}|\sigma)-E\Big{)}.$

Note that the three terms in the right hand side are mutually uncorrelated.
Hence

$\mathbb{E}(\widehat{E}-E)^{2}=\mathbb{E}\Big{(}\widehat{E}-\mathbb{E}(\widehat{E}|W,\sigma)\Big{)}^{2}+\mathbb{E}\Big{(}\mathbb{E}(\widehat{E}|W,\sigma)-\mathbb{E}(\widehat{E}|\sigma)\Big{)}^{2}+\mathbb{E}\Big{(}\mathbb{E}(\widehat{E}|\sigma)-E\Big{)}^{2}.$
(41)

It’s easy to check that $A_{i_{1}:i_{m}}$ and $A_{j_{1}:j_{m}}$ are
conditionally independent if $i_{1}:i_{m}\neq j_{1}:j_{m}$. For the first
term, we have

$\displaystyle\mathbb{E}\Big{(}\widehat{E}-\mathbb{E}(\widehat{E}|W,\sigma)\Big{)}^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}\Bigg{(}\frac{1}{\binom{n}{m}}\sum_{i\in
c(m,n)}(A_{i_{1}:i_{m}}-\theta_{i_{1}:i_{m}})\Bigg{)}^{2}$ (42)
$\displaystyle=$ $\displaystyle\frac{1}{\binom{n}{m}^{2}}\sum_{i\in
c(m,n),j\in
c(m,n)}\mathbb{E}(A_{i_{1}:i_{m}}-\theta_{i_{1}:i_{m}})(A_{j_{1}:j_{m}}-\theta_{j_{1}:j_{m}})$
$\displaystyle=$ $\displaystyle\frac{1}{\binom{n}{m}^{2}}\sum_{i\in
c(m,n)}\mathbb{E}(A_{i_{1}:i_{m}}-\theta_{i_{1}:i_{m}})^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{m}^{2}}\sum_{i\in
c(m,n)}\mathbb{E}\theta_{i_{1}:i_{m}}(1-\theta_{i_{1}:i_{m}})$
$\displaystyle\leq$ $\displaystyle\frac{1}{\binom{n}{m}^{2}}\sum_{i\in
c(m,n)}\mathbb{E}\theta_{i_{1}:i_{m}}$ $\displaystyle=$
$\displaystyle\frac{1}{\binom{n}{m}^{2}}\sum_{i\in(m,n)}(\mathbb{E}W_{1})^{m}\Big{(}\frac{a_{1}+(k^{m-1}-1)b_{1}}{k^{m-1}}\Big{)}$
$\displaystyle=$
$\displaystyle\frac{(\mathbb{E}W_{1})^{m}}{\binom{n}{m}}\Big{(}\frac{a_{1}+(k^{m-1}-1)b_{1}}{k^{m-1}}\Big{)}=O\Big{(}\frac{a_{1}}{n^{m}}\Big{)}.$

For the third term in (41), one has

$\displaystyle\mathbb{E}\Big{(}\mathbb{E}(\widehat{E}|\sigma)-E\Big{)}^{2}$
(43) $\displaystyle=$
$\displaystyle\mathbb{E}\Big{(}\frac{1}{\binom{n}{m}}\sum_{i\in
c(m,n)}(\mathbb{E}W_{1})^{m}(\eta_{i_{1}:i_{m}}-\mathbb{E}\eta_{i_{1}:i_{m}})\Big{)}^{2}$
$\displaystyle=$
$\displaystyle(\mathbb{E}W_{1})^{2m}\mathbb{E}\Big{(}\frac{1}{\binom{n}{m}}\sum_{i\in
c(m,n)}(a_{1}-b_{1})\big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}]-\mathbb{P}[\sigma_{i_{1}}:\sigma_{i_{m}}]\big{)}\Big{)}^{2}$
$\displaystyle\leq$
$\displaystyle(\mathbb{E}W_{1})^{2m}2(a_{1}^{2}+b_{1}^{2})\mathbb{E}\Big{(}\frac{1}{\binom{n}{m}}\sum_{i\in
c(m,n)}\big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}]-\mathbb{P}[\sigma_{i_{1}}:\sigma_{i_{m}}]\big{)}\Big{)}^{2}.$

Note that

$\displaystyle\mathbb{E}\Big{(}\frac{1}{\binom{n}{m}}\sum_{i\in
c(m,n)}\big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}]-\mathbb{P}[\sigma_{i_{1}}:\sigma_{i_{m}}]\big{)}^{2}\Big{)}$
(44) $\displaystyle=$ $\displaystyle\frac{1}{\binom{n}{m}^{2}}\sum_{i\in
c(m,n),j\in
c(m,n)}\mathbb{E}\big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}]-\mathbb{P}[\sigma_{i_{1}}:\sigma_{i_{m}}]\big{)}\big{(}I[\sigma_{j_{1}}:\sigma_{j_{m}}]-\mathbb{P}[\sigma_{j_{1}}:\sigma_{j_{m}}]\big{)}$

If there is no repeated index in $i_{1}:i_{m}$ and $j_{1}:j_{m}$, then

$\mathbb{E}\big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}]-\mathbb{P}[\sigma_{i_{1}}:\sigma_{i_{m}}]\big{)}\big{(}I[\sigma_{j_{1}}:\sigma_{j_{m}}]-\mathbb{P}[\sigma_{j_{1}}:\sigma_{j_{m}}]\big{)}=0.$

If there is only one repeated index in $i_{1}:i_{m}$ and $j_{1}:j_{m}$, say,
$i_{1}=j_{1}$ and other indices are different, then

$\displaystyle\mathbb{E}\big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}]-\mathbb{P}[\sigma_{i_{1}}:\sigma_{i_{m}}]\big{)}\big{(}I[\sigma_{j_{1}}:\sigma_{j_{m}}]-\mathbb{P}[\sigma_{j_{1}}:\sigma_{j_{m}}]\big{)}=\frac{k}{k^{2m-1}}-2\frac{k}{k^{m}}\frac{1}{k^{m-1}}+\frac{1}{k^{2(m-1)}}=0.$

If there are two or more indices in $i_{1}:i_{m}$ and $j_{1}:j_{m}$ are the
same, it is easy to verify that

$0<\mathbb{E}\big{(}I[\sigma_{i_{1}}:\sigma_{i_{m}}]-\mathbb{P}[\sigma_{i_{1}}:\sigma_{i_{m}}]\big{)}\big{(}I[\sigma_{j_{1}}:\sigma_{j_{m}}]-\mathbb{P}[\sigma_{j_{1}}:\sigma_{j_{m}}]\big{)}\leq
1.$

Hence, by (43) and (44), we have

$\displaystyle\mathbb{E}\Big{(}\mathbb{E}(\widehat{E}|\sigma)-E\Big{)}^{2}=O\Big{(}(a_{1}^{2}+b_{1}^{2})\frac{1}{\binom{n}{m}^{2}}\binom{n}{m}\binom{n}{m-2}\Big{)}=O\Big{(}\frac{a_{1}^{2}}{n^{2}}\Big{)}.$
(45)

For the second term in (41), we have

$\displaystyle\mathbb{E}\Big{(}\mathbb{E}(\widehat{E}|W,\sigma)-\mathbb{E}(\widehat{E}|\sigma)\Big{)}^{2}=\mathbb{E}\Big{(}\frac{1}{\binom{n}{m}}\sum_{i\in
c(m,n)}\eta_{i_{1}:i_{m}}(W_{i_{1}:i_{m}}-\mathbb{E}W_{i_{1}:i_{m}})\Big{)}^{2}.$
(46)

Note that for some constants $c_{s_{1}}$, $c_{s_{1}s_{2}}$, $\dots$,
$c_{s_{1}:s_{m-1}}$ dependent on $\mathbb{E}W_{1}$, $1\leq
s_{1},\dots,s_{m-1}\leq m$, one has