# Effective algebraicity for solutions of systems of functional equations with
one catalytic variable

Hadrien Notarantonio1, 2  Sergey Yurkevich1,3  1Inria Saclay, France
2Sorbonne Université, France
3University of Vienna, Austria

###### Abstract

We study systems of $n\geq 1$ discrete differential equations of order $k\geq
1$ in one catalytic variable and provide a constructive and elementary proof
of algebraicity of their solutions. This yields effective bounds and a
systematic method for computing the minimal polynomials. Our approach is a
generalization of the pioneering work by Bousquet-Mélou and Jehanne (2006).

###### keywords:

algebraic functional equations, combinatorics, algebraic algorithms,
algebraicity bounds, catalytic variables

##  1 Introduction

Numerous combinatorial enumeration problems reduce to the study of functional
equations which can be solved by a uniform method introduced by Bousquet-Mélou
and Jehanne in the seminal work [5]. These functional equations, usually
called discrete differential equations (DDEs) with one catalytic variable,
involve a bivariate generating function $F\in\mathbb{Q}[u][[t]]$ associated to
the enumeration problem, and are of the form

$F(t,u)=f(u)+t\cdot
Q(F(t,u),\Delta_{a}F(t,u),\dots,\Delta_{a}^{k}F(t,u),t,u),$ (1)

where $k\in\mathbb{N}$ (called the order of the DDE), $f$ and $Q$ are
polynomials, and (for some $a\in\mathbb{Q}$, usually $0$ or $1$)
$\Delta_{a}^{\ell}$ is the $\ell$th iteration of the operator
$\Delta_{a}:\mathbb{Q}[u][[t]]\to\mathbb{Q}[u][[t]]$ defined by

$\Delta_{a}F(t,u):=\frac{F(t,u)-F(t,a)}{u-a}.$

In their paper, Bousquet-Mélou and Jehanne designed a “non-linear kernel
method” which allows one to prove that the unique solution of (1) is always an
algebraic function over $\mathbb{Q}(t,u)$. Significantly in practice, this
approach yields an algorithm for finding the minimal polynomial of the
specialization $F(t,a)$ and of the bivariate series $F(t,u)$.

The main contribution of the present paper is a generalization of this method
to the case of _systems of discrete differential equations_. More precisely,
we shall prove the following theorem. Here and in the following, we let
$\mathbb{K}$ be a field of characteristic $0$.

######  Theorem 1.

Let $n,k\geq 1$ be integers and $f_{1},\ldots,f_{n}\in\mathbb{K}[u]$,
$Q_{1},\ldots,Q_{n}\in\mathbb{K}[y_{1},\ldots,y_{n(k+1)},t,u]$ be polynomials.
Set $\nabla^{k}F:=(F,\Delta_{a}F,\ldots,\Delta_{a}^{k}F)$. Then the system of
equations

$\begin{cases}\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{1}}}}}\textbf{{\text{):}}}\;\;\;F_{1}=f_{1}(u)+t\cdot
Q_{1}(\nabla^{k}F_{1},\ldots,\nabla^{k}F_{n},t,u),\\\
\indent\vdots\hfill\vdots\\\
\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{n}}}}}\textbf{{\text{):}}}\;\;F_{n}=f_{n}(u)+t\cdot
Q_{n}(\nabla^{k}F_{1},\ldots,\nabla^{k}F_{n},t,u)\end{cases}$ (2)

admits a unique vector of solutions
$(F_{1},\ldots,F_{n})\in\mathbb{K}[u][[t]]^{n}$, and all its components are
algebraic functions over $\mathbb{K}(t,u)$.

The key idea, analogous to the one in [5], for proving this theorem is to
define a deformation of (2) that ensures the applicability of a multi-
dimensional analog of the “non-linear kernel method”. Stated explicitly, we
show in 3 that after deforming the equations as in (6), the polynomial in $u$
defined by the determinant of the Jacobian matrix associated to the numerator
equations in (2) (considered with respect to the $F_{i}$) has exactly $nk$
solutions in an extension of the ring $\bigcup_{d\geq
1}\overline{\mathbb{K}}[[t^{1/d}]]$. Then, after a process of “duplication of
variables”, we construct a zero-dimensional and radical polynomial ideal, a
non-trivial element of which must be the desired annihilating polynomial. The
most difficult step consists in proving the invertibility of a certain
Jacobian matrix (5 and 6) in order to justify the zero-dimensionality. We
remark that an alternative, and possibly more practical, strategy is to reduce
the initial system to a single functional equation. Our 7 ensures that such a
reduction preserves the roots guaranteed in the deformation step, however, as
we will show in Section 4, this method is not guaranteed to produce a zero-
dimensional polynomial ideal in the end.

Similarly to the work by Bousquet-Mélou and Jehanne, our proof is effective,
in the sense that it produces an algorithm for finding the minimal polynomials
of the power series of interest. Moreover, we can deduce a bound on the
algebraicity degree of each $F_{i}$. When the field $\mathbb{K}$ is effective
(e.g. $\mathbb{K}=\mathbb{Q}$), we can also bound the arithmetic complexity of
our algorithm, that is the number of operations $(+,-,\times,\div)$ performed
in $\mathbb{K}$. Denoting by $\textsf{totdeg}(P)$ the total degree of a
multivariate polynomial $P$, we obtain the following:

######  Theorem 2.

In the setting of 1, let $(F_{1},\ldots,F_{n})\in\mathbb{K}[u][[t]]^{n}$ be
the vector of solutions and
$\delta:=\max(\deg(f_{1}),\dots,\deg(f_{n}),\textsf{totdeg}(Q_{1}),\dots,\textsf{totdeg}(Q_{n}))$.
Then the algebraicity degree of each $F_{i}(t,u)$ over $\mathbb{K}(t,u)$ is
bounded by $(2nk\delta)^{2n^{3}k^{2}+2n}/(nk)!^{nk}$. If $\mathbb{K}$ is
effective, there exists an algorithm computing the minimal polynomial of any
$F_{i}(t,a)$ in $(2nk\delta)^{O(n^{2}k)}$ operations in $\mathbb{K}$.

Discrete differential equations are ubiquitous in enumerative combinatorics
[6, 7, 12]. Systems of DDEs also appear in a variety of different contexts
throughout combinatorics, for instance for hard particles on planar maps [5,
§5.4], inhomogeneous lattice paths [8], or certain orientations with $n$ edges
[3, §5]. The usual strategy for solving these systems of equations is to try
to reduce a given system to a scalar equation and then apply the method of
Bousquet-Mélou and Jehanne. This approach is usually ad-hoc and needs to
exploit additional structure of the system. Moreover, since the reduced
equation is in general not of the form (1) anymore, the theory of [5] is not
guaranteed to work.

In the literature there exist two methods to overcome these theoretical
issues. First, a deep theorem in commutative algebra by Popescu [10], so-
called “nested Artin approximation”, guarantees that equations of the form (2)
always admit an algebraic solution (see also [3, Thm. 16] for a statement of
this theorem). Note that the nested condition is automatically satisfied in
this case and that the uniqueness of the solution is obvious. A drawback of
using Popescu’s theorem, however, is that its proof is highly non-constructive
and can only be applied as a “black box”, whereas in practice one is often
interested in the explicit minimal polynomials annihilating the solutions.
Secondly, the frequent case when all polynomials $Q_{1},\dots,Q_{n}$ in (2)
are linear functions was effectively solved in the recent FPSAC article [8] by
Buchacher and Kauers and independently by Asinowski, Bacher, Banderier and
Gittenberger [1]. From this viewpoint, it is safe to say that our contribution
is a common generalization of central results by Bousquet-Mélou and Jehanne
[5] and the “vectorial kernel method” of [1, 8], and at the same time an
effective and elementary proof of a special case of Popescu’s theorem [10].

We shall highlight the following two examples of systems of DDEs in more
detail.

######  Example 1.

The following system of DDEs for the generating function of certain planar
orientations was considered in [3, Eq.$(27)$] and solved in the same work:

$\begin{cases}\textbf{(E${}_{\textbf{F}_{1}}$):}\;\;F_{1}(t,u)=1+t\cdot\big{(}u+2uF_{1}(t,u)^{2}+2uF_{2}(t,1)+u\frac{F_{1}(t,u)-uF_{1}(t,1)}{u-1}\big{)},\\\
\textbf{(E${}_{\textbf{F}_{2}}$):}\;\;F_{2}(t,u)=t\cdot\big{(}2uF_{1}(t,u)F_{2}(t,u)+uF_{1}(t,u)+uF_{2}(t,1)+u\frac{F_{2}(t,u)-uF_{2}(t,1)}{u-1}\big{)}.\end{cases}$
(3)

From our perspective, (3) has the advantage that it does not require any
deformation and, as we will show in Section 2, it can be solved fast by a
direct application of our method. It is thus a good illustration of the
simplest non-trivial case of our approach.

######  Example 2.

This example of a system of DDEs modelling a particular case of hard particles
on planar maps was introduced and solved in [5, Section $11$]:

$\begin{cases}\textbf{(E${}_{\textbf{F}_{1}}$):}\;\;F_{1}(t,u)=F_{2}(t,u)+tu^{2}F_{1}(t,u)^{2}+tu\frac{uF_{1}(t,u)-F_{1}(t,1)}{u-1},\\\
\textbf{(E${}_{\textbf{F}_{2}}$):}\;\;F_{2}(t,u)=1+tsuF_{1}(t,u)F_{2}(t,u)+tsu\frac{F_{2}(t,u)-F_{2}(t,1)}{u-1}.\end{cases}$
(4)

To apply our method directly, a deformation step (6) is necessary (see Section
4).

The structure of the paper is as follows: In Section 2 we explain our method
in the case of two equations of order one under the genericity assumption that
no deformation is necessary. We summarize the method in an algorithm and
showcase it explicitly on 1. Section 3 is devoted to the proofs of 1 and 2. In
the last Section 4 we briefly explore an improvement to our approach which in
theory has a better algorithmic complexity but which requires a new genericity
assumption. We also discuss possible future works.

##  2 The case of two generic equations of first order

Before proving our main theorem in Section 3, we introduce our method in the
situation of two equations of order $1$ and under a genericity assumption on
the input system.

Starting with (2), we first multiply (E${}_{\textbf{F}_{1}}$) and
(E${}_{\textbf{F}_{2}}$) by $(u-a)^{m_{1}}$ and $(u-a)^{m_{2}}$ respectively
(for $m_{1},m_{2}\in~{}\mathbb{N}$) in order to obtain a system with
polynomial coefficients in $u$. By a slight abuse of notation, we shall still
write (E${}_{\textbf{F}_{1}}$) and (E${}_{\textbf{F}_{2}}$) for those
equations. Note that this system induces polynomials $E_{1},E_{2}$ in
$\mathbb{K}[x_{1},x_{2},z_{0},z_{1},t,u]$ whose specializations to
$x_{1}=F_{1}(t,u),x_{2}=F_{2}(t,u),z_{0}=F_{1}(t,a),z_{1}=F_{2}(t,a)$ are
zero.

######  Example 1 (cont.).

Multiplying (E${}_{\textbf{F}_{1}}$) and (E${}_{\textbf{F}_{2}}$) in 1 by
$u-1$ gives

$\begin{cases}E_{1}=(1-x_{1})\cdot(u-1)+t\cdot(2u^{2}x_{1}^{2}-u^{2}z_{0}+2u^{2}z_{1}-2ux_{1}^{2}+u^{2}+ux_{1}-2uz_{1}-u),\\\
E_{2}=x_{2}\cdot(1-u)+t\cdot(2u^{2}x_{1}x_{2}+u^{2}x_{1}-2ux_{1}x_{2}-ux_{1}+ux_{2}-uz_{1}).\end{cases}$

In the spirit of [5], we now take the derivative of both equations with
respect to $u$:

$\begin{pmatrix}\partial_{x_{1}}E_{1}&\partial_{x_{2}}E_{1}\\\
\partial_{x_{1}}E_{2}&\partial_{x_{2}}E_{2}\end{pmatrix}\cdot\begin{pmatrix}\partial_{u}F_{1}\\\
\partial_{u}F_{2}\end{pmatrix}+\begin{pmatrix}\partial_{u}E_{1}\\\
\partial_{u}E_{2}\end{pmatrix}=0.$ (5)

Define
$\operatorname{\mathsf{Det}}:=\partial_{x_{1}}E_{1}\cdot\partial_{x_{2}}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{x_{2}}E_{1}\in\mathbb{K}[x_{1},x_{2},z_{0},z_{1},t,u]$
to be the determinant of the square matrix above. One can show that
$\operatorname{\mathsf{Det}}(F_{1}(t,u),F_{2}(t,u),F_{1}(t,a),F_{2}(t,a),t,u)\in\mathbb{K}[[t]][[u]]$
admits either $0,1$ or $2$ distinct non-zero solutions
$u=U(t)\in\bigcup_{d\geq
1}\overline{\mathbb{K}}[[t^{1/d}]]=:\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$.
We assume now that there exist $2$ such solutions
$U_{1},U_{2}\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$; we prove in
Section 3 that it is always the case up to the deformation (6).

Exploiting the idea of [8], we now define
$v:=(\partial_{x_{1}}E_{2},\;\;-\partial_{x_{1}}E_{1})\in\mathbb{K}[x_{1},x_{2},z_{0},z_{1},t,u]^{2}$
and plug $U_{1}$ for $u$ into $v$ and (5). Note that $v$ is an element of the
left-kernel of the square matrix in (5) $\bmod$
$\operatorname{\mathsf{Det}}(x_{1},x_{2},z_{0},z_{1},t,u)$. After
multiplication of (5) by $v$ on the left, we find a new polynomial relation
between $F_{1}(t,U_{i}),F_{2}(t,U_{i}),F_{1}(t,a),F_{2}(t,a),t$ and $U_{i}$,
namely
$\partial_{x_{1}}E_{1}\cdot\partial_{u}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{u}E_{1}=0$
when evaluated at
$x_{1}=F_{1}(t,U_{i}),x_{2}=F_{2}(t,U_{i}),z_{0}=F_{1}(t,a),z_{1}=F_{2}(t,a),u=U_{i}$.
We denote this polynomial by $P\in\mathbb{K}[x_{1},x_{2},z_{0},z_{1},t,u]$.
Define the polynomial system
$\mathcal{S}:=(E_{1},E_{2},\operatorname{\mathsf{Det}},P)\in\mathbb{K}[t][x_{1},x_{2},z_{0},z_{1},u]^{4}$.
It admits the non-trivial solutions
$(F_{1}(t,U_{i}),F_{2}(t,U_{i}),F_{1}(t,a),F_{2}(t,a),U_{i})\in\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]^{5}$,
for $i\in\\{1,2\\}$.

######  Example 1 (cont.).

Continuing 1, we find

$\begin{cases}\operatorname{\mathsf{Det}}=(4tu^{2}x_{1}-4tux_{1}+tu-u+1)(2tu^{2}x_{1}-2tux_{1}+tu-u+1),\\\
P=-2tx_{1}x_{2}-tx_{1}+tx_{2}-tz_{1}-x_{2}+P_{1}\cdot u+P_{2}\cdot
u^{2}+P_{3}\cdot u^{3},\end{cases}$

where $P_{1},P_{2},P_{3}$ are explicit (but relatively big) polynomials in
$\mathbb{Q}[x_{1},x_{2},z_{0},z_{1},t]$.

Now, generalizing naturally the steps of [5], we define for $i\in\\{0,1\\}$
the polynomial systems
$\mathcal{S}_{i}:=\mathcal{S}(x_{2i+1},\;x_{2i+2},\;z_{0},\;z_{1},\;t,\;u_{i+1})$
by “duplicating” variables. We call the situation “ _generic_ ” if the ideal
$\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle$ has
dimension $0$ over $\mathbb{K}(t)$. In this case, in order to find an
annihilating polynomial of $F_{1}(t,a)$, it is enough to compute a non-zero
element of
$\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle\cap\mathbb{K}[z_{0},t]$.

######  Example 1 (cont.).

Continuing Example 1, we compute111All computations in this paper have been
performed in Maple using msolve [2]. a generator of the polynomial ideal
$\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle\cap\mathbb{Q}[z_{0},t]$.
It has degree $13$ in $z_{0}$ and $14$ in $t$. In particular, it contains in
its factors the minimal polynomial of $F_{1}(t,1)$ given by
$64t^{3}z_{0}^{3}+(48t^{3}-72t^{2}+2t)z_{0}^{2}-(15t^{3}-9t^{2}-19t+1)z_{0}+t^{3}+27t^{2}-19t+1$.

We summarize the presented algorithm in a more compact form:

Input: A “generic” system of two DDEs (E${}_{\textbf{F}_{1}}$),
(E${}_{\textbf{F}_{2}}$) of order $1$.

Output: A non-zero $R\in\mathbb{K}[z_{0},t]$ annihilating $F_{1}(t,a)$.

1 Replace (E${}_{\textbf{F}_{1}}$) and (E${}_{\textbf{F}_{2}}$) by their
respective numerators and denote by $E_{1}$ and $E_{2}$ the associated
polynomials in $\mathbb{K}[x_{1},x_{2},z_{0},z_{1},t,u]$.

2 Compute
$\operatorname{\mathsf{Det}}:=\partial_{x_{1}}E_{1}\cdot\partial_{x_{2}}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{x_{2}}E_{1}$
and
$P:=\partial_{x_{1}}E_{1}\cdot\partial_{u}E_{2}-\partial_{x_{1}}E_{2}\cdot\partial_{u}E_{1}$.

3 Set
$\mathcal{S}:=(E_{1},E_{2},\operatorname{\mathsf{Det}},P)\subset\mathbb{K}[x_{1},x_{2},z_{0},z_{1},t,u]$.

4 For $0\leq i\leq 1$, define
$\mathcal{S}_{i}:=\mathcal{S}(x_{2i+1},\;x_{2i+2},\;z_{0},\;z_{1},\;t,\;u_{i+1})$.

Return a non-zero element of
$\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle\cap\mathbb{K}[z_{0},t]$.

Algorithm 1 Solving systems of two discrete differential equations of order
$1$.

As already stated, Section 3 ensures that for a non-generic input, after a
deformation, we can use an algorithm in spirit of Algorithm 1.

We remark that if the strategy above is applied in the case of a single
equation of first order $F_{1}=f(u)+t\cdot Q_{1}(F_{1},\Delta_{a}F_{1},t,u)$,
the presented method simplifies to the classical algorithm in [5] relying on
studying the ideal $\langle
E_{1},\partial_{x_{1}}E_{1},\partial_{u}E_{1}\rangle$. Stated explicitly,
$\partial_{x_{1}}E_{1}$ plays the role of $\operatorname{\mathsf{Det}}$ and
$\partial_{u}E_{1}$ plays the role of $P$ (as we can take here $v=1$).

##  3 Proofs of 1 and 2

We start by proving 1. As explained before, the statement and proof can be
seen as a generalization of [5, Theorem 3] and [8, Theorem 2], so several
steps are done analogously. Without loss of generality we assume that $a=0$
and set $\Delta:=\Delta_{0}$.

Denote by $m_{1},\ldots,m_{n}$ the least positive integers greater than or
equal to $k$ such that multiplying ($\textbf{E}_{\textbf{F}_{\textit{{i}}}}$)
in (2) by $u^{m_{i}}$ gives a polynomial equation in $u$. Set $\beta:=\lfloor
2M/k\rfloor$ and $\alpha:=n^{2}k\cdot(\beta+1)+nM$, where
$M:=m_{1}+\cdots+m_{n}$. Let $\epsilon$ be a new variable,
$\mathbb{L}:=\mathbb{K}(\epsilon)$, and let $(\gamma_{i,j})_{1\leq i,j\leq n}$
be defined by $\gamma_{i,i}=i^{k}$ and $\gamma_{i,j}=t^{\beta}$ for $i\neq j$.
Then consider the following system which is a deformation of (2):

$\begin{cases}\textbf{{\text{(E}}}_{\textbf{{\text{G}}}_{\textbf{{\text{1}}}}}\textbf{{\text{):}}}\;\;\;G_{1}=f_{1}(u)+t^{\alpha}\cdot
Q_{1}(\nabla^{k}G_{1},\nabla^{k}G_{2},\ldots,\nabla^{k}G_{n},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{1,i}\cdot\Delta^{k}G_{i},\\\
\qquad\qquad\;\;\;\vdots\hfill\vdots\\\
\textbf{{\text{(E}}}_{\textbf{{\text{G}}}_{\textbf{{\text{{n}}}}}}\textbf{{\text{):}}}\;\;\;G_{n}=f_{n}(u)+t^{\alpha}\cdot
Q_{n}(\nabla^{k}G_{1},\nabla^{k}G_{2},\ldots,\nabla^{k}G_{n},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{n,i}\cdot\Delta^{k}G_{i}.\end{cases}$
(6)

The fixed point nature of these equations still implies that there exists a
unique solution $(G_{1},\ldots,G_{n})\in\mathbb{L}[u][[t]]^{n}$. Remark that
the equalities $F_{i}(t^{\alpha},u)=G_{i}(t,u,0)$ relate the formal power
series solutions of (2) and of (6). Hence, showing that each $G_{i}$ is
algebraic over $\mathbb{L}(t,u)$ is enough to prove 1. Moreover, as we will
see later, the algebraicity of each $G_{i}$ follows from the algebraicity of
$G_{1}(0),\ldots,\partial_{u}^{k-1}G_{1}(0),\ldots,G_{n}(0),\ldots,\partial_{u}^{k-1}G_{n}(0)$.
Here, and in what follows, we shall use the short notation $G_{i}(u)\equiv
G_{i}(t,u,\epsilon)$, $\partial_{0}G_{i}(u)\equiv
G_{i}(u),G_{i}(0),\partial_{u}G_{i}(0),\ldots,\partial_{u}^{k-1}G_{i}(0)$ and
$A(u)\equiv A(\partial_{0}G_{1},\ldots,\partial_{0}G_{n},t,u)$ for any
polynomial $A\in\mathbb{L}[X_{1},\ldots,X_{n},t,u]$ with
$X_{j}:=x_{j},z_{k(j-1)},\ldots,z_{kj-1}$. In the case $n=1$, this notation
implies that for any $0\leq i\leq k-1$, the variable $z_{i}$ stands for
$\partial_{u}^{i}F_{1}(t,a)$.

Let us define $Y_{i,0}:=x_{i}$ and
$Y_{i,j}:=({x_{i}-z_{k(i-1)}-\cdots-\frac{u^{j-1}}{(j-1)!}z_{k(i-1)+j-1})/u^{j}}$
for $j\geq 1$. With these definitions, (6) is equivalent to the following
system of polynomial equations

$\begin{cases}E_{1}:=u^{m_{1}}\cdot(f_{1}(u)-x_{1}+t^{\alpha}\cdot
Q_{1}(Y_{1,0},\ldots,Y_{1,k},Y_{2,0},\ldots,Y_{n,k},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{1,i}\cdot
Y_{i,k})=0,\\\ \indent\vdots\hfill\vdots\\\
E_{n}:=u^{m_{n}}\cdot(f_{n}(u)-x_{n}+t^{\alpha}\cdot
Q_{n}(Y_{1,0},\ldots,Y_{1,k},Y_{2,0},\ldots,Y_{n,k},t^{\alpha},u)+t\cdot\epsilon^{k}\cdot\sum_{i=1}^{n}\gamma_{n,i}\cdot
Y_{i,k})=0.\end{cases}$ (7)

Like in (5), we take the derivative with respect to $u$ of these equations and
find

$\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n}}E_{1}\\\
\vdots&\ddots&\vdots\\\
\partial_{x_{1}}E_{n}&\dots&\partial_{x_{n}}E_{n}\end{pmatrix}\cdot\begin{pmatrix}\partial_{u}G_{1}\\\
\vdots\\\ \partial_{u}G_{n}\end{pmatrix}+\begin{pmatrix}\partial_{u}E_{1}\\\
\vdots\\\ \partial_{u}E_{n}\end{pmatrix}=0.$ (8)

Let $\operatorname{\mathsf{Det}}\in\mathbb{L}[X_{1},\dots,X_{n},t][u]$ be the
determinant of the square matrix $(\partial_{x_{j}}E_{i})_{1\leq i,j\leq n}$
above. The following lemma on the number of distinct solutions to
$\operatorname{\mathsf{Det}}(u)=0$ is the first main step in our proof.

######  Lemma 3.

$\operatorname{\mathsf{Det}}(u)=0$ admits exactly $nk$ distinct non-zero
solutions
$U_{1},\ldots,U_{nk}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]$.

###### Proof.

Note that we have

$\operatorname{\mathsf{Det}}(u)=\det\begin{pmatrix}-u^{m_{1}}+t\epsilon^{k}\gamma_{1,1}u^{m_{1}-k}&\cdots&t\epsilon^{k}\gamma_{1,n}u^{m_{1}-k}\\\
\vdots&\ddots&\vdots\\\
t\epsilon^{k}\gamma_{n,1}u^{m_{n}-k}&\cdots&-u^{m_{n}}+t\epsilon^{k}\gamma_{n,n}u^{m_{n}-k}\end{pmatrix}+O(t^{\alpha}u^{M-nk}).$

For every $i$ we first divide the $i^{\text{th}}$ row by $u^{m_{i}-k}$. Then,
using the definition of $\gamma_{i,j}$ and $\alpha,\beta\geq n$, we see that
the matrix above becomes diagonal mod $t^{n+1}$ and its determinant mod
$t^{n+1}$ simplifies to $\prod_{j=1}^{n}(-u^{k}+t\epsilon^{k}j^{k})\bmod
t^{n+1}$. Hence, computing the first terms of a solution in $u$ by using
Newton polygons, we find $nk$ distinct solutions $u=U_{1}(t),\ldots,U_{nk}(t)$
whose first terms are given by $\zeta^{\ell}\cdot
t^{\frac{1}{k}}\cdot\epsilon+O(t^{\frac{2}{k}}),\ldots,\zeta^{\ell}\cdot
n\cdot
t^{\frac{1}{k}}\cdot\epsilon+O(t^{\frac{2}{k}})\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]$,
for $\zeta$ a $k$-primitive root of unity and for all $1\leq\ell\leq k$.
Finally, note that the constant coefficient in $t$ of
$\prod_{j=1}^{n}(-u^{k}+t\epsilon^{k}j^{k})$ has degree $nk$ so by [5, Theorem
2] there cannot be more than $nk$ solutions to
$\operatorname{\mathsf{Det}}(u)=0$ in
$\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]$. ∎

Now, let $P$ be the determinant of the square matrix
$(\partial_{x_{j}}E_{i})_{1\leq i,j\leq n}$ where the last column
$(\partial_{x_{n}}E_{1},\dots,\partial_{x_{n}}E_{n})$ is replaced by
$(\partial_{u}E_{1},\dots,\partial_{u}E_{n})$. It is easy to see with standard
linear algebra arguments that if $\operatorname{\mathsf{Det}}=0$ then (8)
implies that $P=0$. Hence, we define the polynomial system
$\mathcal{S}:=(E_{1},\ldots,E_{n},\operatorname{\mathsf{Det}},P)$ in
$\mathbb{L}[t][X_{1},\ldots,X_{n},u]$. We see that $\mathcal{S}$ is a system
with exactly $n+2$ equations in the $nk+n+1$ variables
$z_{0},\ldots,z_{nk-1},x_{1},\ldots,x_{n},u$ (here $t$ and $\epsilon$ are
parameters). We wish to construct a zero-dimensional ideal, so we introduce
the _duplicated system_
$\operatorname{\mathcal{S}_{\mathsf{dup}}}:=(\mathcal{S}_{1},\ldots,\mathcal{S}_{nk})$,
defined in
$\mathbb{L}(t)[x_{1},\ldots,x_{n^{2}k},z_{0},\dots,z_{nk-1},u_{1},\ldots,u_{nk}]$.
This system is built from $nk(n+2)$ equations and $nk(n+2)$ variables.

The following lemma is proven in [4, Lemma 2.10] as a consequence of Hilbert’s
Nullstellensatz and [9, Theorem 16.19]:

######  Lemma 4.

Assume that the Jacobian matrix
$\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}$ of
$\operatorname{\mathcal{S}_{\mathsf{dup}}}$, considered with respect to the
variables
$x_{1},\ldots,x_{n},u_{1},\ldots,x_{n^{2}k-n},\ldots,x_{n^{2}k},u_{nk},$
$z_{0},\ldots,z_{nk-1}$, is invertible at the point

$\displaystyle\mathcal{P}=(G_{1}$
$\displaystyle(U_{1}),\ldots,G_{n}(U_{1}),U_{1},\ldots,G_{1}(U_{nk}),\ldots,G_{n}(U_{nk}),U_{nk},{G}_{1}(0),\ldots,\partial_{u}^{k-1}{G}_{1}(0),\ldots,$
$\displaystyle{G}_{n}(0),\ldots,\partial_{u}^{k-1}{G}_{n}(0))\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{nk(n+1)}\times\mathbb{L}[[t]]^{nk}.$

Then the saturated ideal
$\langle\operatorname{\mathcal{S}_{\mathsf{dup}}}\rangle:\det(\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}})^{\infty}$
is zero-dimensional and radical over $\mathbb{L}(t)$. Moreover, $\mathcal{P}$
lies in the zero set of
$\langle\operatorname{\mathcal{S}_{\mathsf{dup}}}\rangle:\det(\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}})^{\infty}$.

Therefore, in order to conclude the algebraicity of
$G_{i}(0),\ldots,\partial_{u}^{k-1}G_{i}(0)$ over $\mathbb{L}(t)$ for all
$1\leq i\leq n$, it is enough to justify that
$\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}$ is
invertible at $\mathcal{P}$. Then, by 4, it will follow that it is possible to
apply effective techniques from polynomial elimination theory and find
annihilating polynomials for the power series of interest.

The idea for proving that
$\det(\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}})(\mathcal{P})\neq
0$, analogous to the proof in [5], is to show first that
$\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}(\mathcal{P})$
can be rewritten as a block triangular matrix. We will then show that each
such block is invertible by carefully analyzing its lowest valuation in $t$.

If $A\in\mathbb{L}[t][X_{1},\ldots,X_{n},u]$, we shall define its
“$i^{\text{th}}$ duplicated polynomial” as
$A^{(i)}:=A(X_{ni+1},\ldots,X_{n(i+1)},u_{i})$ . Then the Jacobian matrix
$\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}(\mathcal{P})$
has the shape

$\displaystyle\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}(\mathcal{P})=\begin{pmatrix}A_{1}&&0&B_{1}\\\
&\ddots&&\vdots\\\ 0&&A_{nk}&B_{nk}\\\
\end{pmatrix}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{nk(n+2)\times
nk(n+2)},$

where the matrices
$A_{i}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{(n+2)\times(n+1)}$ and
$B_{i}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{(n+2)\times nk}$ are
given by:

$\displaystyle\footnotesize
A_{i}:=\begin{pmatrix}\partial_{x_{1}}E_{1}^{(i)}(U_{i})&\dots&\partial_{x_{n}}E_{1}^{(i)}(U_{i})&\partial_{u_{i}}E_{1}^{(i)}(U_{i})\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}^{(i)}(U_{i})&\dots&\partial_{x_{n}}E_{n}^{(i)}(U_{i})&\partial_{u_{i}}E_{n}^{(i)}(U_{i})\\\
\partial_{x_{1}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})&\dots&\partial_{x_{n}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})&\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\\\
\partial_{x_{1}}P^{(i)}(U_{i})&\dots&\partial_{x_{n}}P^{(i)}(U_{i})&\partial_{u_{i}}P^{(i)}(U_{i})\end{pmatrix},B_{i}:=\begin{pmatrix}\partial_{z_{0}}E_{1}^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}E_{1}^{(i)}(U_{i})\\\
\vdots&\ddots&\vdots\\\
\partial_{z_{0}}E_{n}^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}E_{n}^{(i)}(U_{i})\\\
\partial_{z_{0}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\\\
\partial_{z_{0}}P^{(i)}(U_{i})&\dots&\partial_{z_{nk-1}}P^{(i)}(U_{i})\end{pmatrix}.$

Using $\operatorname{\mathsf{Det}}(U_{i})=0$ and (8), we see that the first
$n\times(n+1)$ submatrix of each $A_{i}$ has rank at most $n-1$. Hence, after
performing operations on the first $n$ rows, we can transform the
$n^{\text{th}}$ row of $A_{i}$ into the zero vector. It follows that after the
suitable transformation and a permutation of rows,
$\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}(\mathcal{P})$
can be rewritten as a block triangular matrix. To give the precise form of the
determinant of
$\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}}(\mathcal{P})$,
we first define

$\small
R:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}^{(i)}(U_{i})&\dots&\partial_{x_{n-1}}E_{1}^{(i)}(U_{i})&y_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}^{(i)}(U_{i})&\dots&\partial_{x_{n-1}}E_{n}^{(i)}(U_{i})&y_{n}\end{pmatrix}\in\mathbb{K}[\\{\partial_{x_{\ell}}E_{j}^{(i)}(U_{i})\\}_{1\leq\ell,j\leq
n}][y_{1},\ldots,y_{n}].$ (9)

Then it follows that
$\det(\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}})(\mathcal{P})=\pm\big{(}\prod\limits_{i=1}^{nk}\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))\big{)}\cdot\det(\Lambda)$,
where

$\small\operatorname{\mathsf{Jac}}_{i}(u):=\begin{pmatrix}\partial_{x_{1}}E_{1}^{(i)}(u)&\dots&\partial_{x_{n}}E_{1}^{(i)}(u)&\partial_{u_{i}}E_{1}^{(i)}(u)\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n-1}^{(i)}(u)&\dots&\partial_{x_{n}}E_{n-1}^{(i)}(u)&\partial_{u_{i}}E_{n-1}^{(i)}(u)\\\
\partial_{x_{1}}\operatorname{\mathsf{Det}}^{(i)}(u)&\dots&\partial_{x_{n}}\operatorname{\mathsf{Det}}^{(i)}(u)&\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(u)\\\
\partial_{x_{1}}P^{(i)}(u)&\dots&\partial_{x_{n}}P^{(i)}(u)&\partial_{u_{i}}P^{(i)}(u)\end{pmatrix}\in\mathbb{L}[u][[t]]^{(n+1)\times(n+1)},\text{
\normalsize{and}}$
$\small\Lambda:=\big{(}R(\partial_{z_{j}}E_{1}^{(i)}(U_{i}),\ldots,\partial_{z_{j}}E_{n}^{(i)}(U_{i}))\big{)}_{1\leq
i,j+1\leq nk}\in\overline{\mathbb{L}}[[t^{\frac{1}{\star}}]]^{nk\times nk}.$
(10)

The proof that this product is non-zero is the content of 5 and 6.

######  Lemma 5.

For each $i=1,\dots,nk$, the determinant of
$\operatorname{\mathsf{Jac}}_{i}(U_{i})$ is non-zero.

###### Proof sketch.

To prove that $\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))\neq 0$ we will
show that
$\textsf{val}_{t}(\det(\operatorname{\mathsf{Jac}}_{i}(U_{i})))<\infty$, where
$\textsf{val}_{t}$ denotes the valuation in $t$. The main idea here is to
expand $\det(\operatorname{\mathsf{Jac}}_{i}(U_{i}))$ with respect to the last
column and show that the least valuation comes from the product of
$\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})$ by its associated
submatrix, which we denote by $\mathcal{M}$.

Since
$\partial_{x_{j}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})=O(t^{\alpha})$, it
is clear that for $1\leq j\leq n$ the minors associated to
$\partial_{u_{i}}E_{j-1}^{(i)}(U_{i})$ and $\partial_{u_{i}}P^{(i)}(U_{i})$
are in $O(t^{\alpha})$. It remains to show that the product of
$\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})$ by
$\det(\mathcal{M})$ is of valuation in $t$ strictly lower than $\alpha$. For
$j=1,\dots,n-1$ and $\ell=1,\dots,n$ one computes that
$\textsf{val}_{t}(\mathcal{M})_{j,\ell}=\partial_{x_{j}}E_{\ell}^{(i)}(U_{i})=\beta+\frac{m_{j}}{k}$
if $j\neq\ell$ and $\frac{m_{j}}{k}$ if $j=\ell$. Moreover, it follows from
the definition of $P$ and expansion along the last row of the matrix which
defines $P$ that the term with lowest $t$-valuation in
$\partial_{x_{n}}P^{(i)}$ is given by the product of
$\partial_{x_{n},u_{i}}E_{n}^{(i)}$ by the determinant of the associated sub-
matrix of $\partial_{u_{i}}E_{n}^{(i)}$. Computing this valuation while using
that $\alpha,\beta$ are chosen sufficiently large, we find that
$\textsf{val}_{t}(\partial_{x_{n}}P^{(i)})=(\sum_{i=1}^{n}{\frac{m_{i}}{k}})-\frac{1}{k}=(M-1)/k$.
It follows that the only monomial in the determinant of $\mathcal{M}$ that has
no dependency on $\beta$ comes from the product of diagonal elements of
$\mathcal{M}$. Using the definition $\alpha=n^{2}k\cdot(\lfloor
2M/k\rfloor+1)+nM$ and $\beta=\lfloor 2{M}/{k}\rfloor$, we conclude that
$\textsf{val}_{t}(\partial_{u_{i}}\operatorname{\mathsf{Det}}^{(i)}(U_{i})\cdot\det(\mathcal{M}))<\alpha$.
∎

######  Lemma 6.

The determinant of $\Lambda$ is non-zero.

###### Proof sketch.

Proving $\det(\Lambda)\neq 0$ is again done by analyzing the first terms of
$\det(\Lambda)$. We prove that mod $t^{\alpha}$ the determinant factors as a
product of $U_{i}$, the Vandermonde determinant $\prod_{i<j}(U_{i}-U_{j})$,
and a non-zero polynomial $H(t)$. The actual computation is somewhat
technical, since $\det(\Lambda)$ is defined as the determinant of the
$nk\times nk$ matrix
$R(\partial_{z_{j}}E_{1}^{(i)}(U_{i}),\ldots,\partial_{z_{j}}E_{n}^{(i)}(U_{i}))_{i,j}$
whose entries are themselves determinants of the $n\times n$ matrices (9). We
shall give an exposition of the proof, omitting technical details.

We denote
$R_{j}(u):=R(\partial_{z_{j}}E_{1}^{(i)}(u),\ldots,\partial_{z_{j}}E_{n}^{(i)}(u))$
and compute $R_{j}(u_{i})\bmod t^{\alpha}$ for variables
$u_{1},\ldots,u_{nk}$. Note that the latter is a non-zero polynomial in
$\mathbb{L}[u_{1},\dots,u_{nk},t]$ which is independent of the polynomials
$Q_{1},\dots,Q_{n}$. Let $\tilde{\Lambda}=(R_{j}(u_{i}))_{1\leq i,j+1\leq nk}$
be the matrix $\Lambda$ with the $U_{i}$ replaced by the variables $u_{i}$.
With tedious but explicit computations it is possible to show that each
element in the $i^{\text{th}}$ row of $\tilde{\Lambda}\bmod t^{\alpha}$ is a
polynomial in $u_{i}$ of degree $\leq M-1$ and valuation $\geq M-nk$.
Moreover, all entries of $\tilde{\Lambda}\bmod t^{\alpha}$ have degree in $t$
bounded by $t^{n(\beta+1)}$. The choice for $\alpha$ and $\beta$ ensures that
$\det(\tilde{\Lambda}\bmod t^{\alpha})=\det(\tilde{\Lambda})\bmod t^{\alpha}$.

As we have $M\geq nk$, it is possible to factor out $u_{i}^{M-nk}$ from the
$i^{\text{th}}$ row of $\tilde{\Lambda}\bmod t^{\alpha}$ when computing its
determinant. This yields polynomials of degree at most $nk-1$ in $u_{i}$ on
the $i^{\text{th}}$ row. Moreover, it is obvious that if $u_{i}=u_{j}$ for
some $i\neq j$, the determinant of $\tilde{\Lambda}$ vanishes. Hence, we can
also factor out the Vandermonde determinant $\prod_{i<j}{(u_{i}-u_{j})}$. As
this latter product is of degree $nk-1$ in $u_{i}$, we conclude that

$\det(\tilde{\Lambda})\equiv\prod_{i=1}^{nk}{u_{i}^{M-nk}}\cdot\prod_{i<j}{(u_{i}-u_{j})}\cdot
H(t)\mod t^{\alpha},$ (11)

for some non-zero polynomial $H\in\mathbb{L}[t]$ whose degree only depends on
$\beta$. Recall that $\tilde{\Lambda}(U_{1},\dots,U_{nk})=\Lambda$, and all
$U_{i}$ are distinct with valuation in $t$ of $1/k$ by 3. Using this, equation
(11) and $\alpha>(M-nk)n+n+n^{2}k(\beta+1)$, we conclude that
$\det(\Lambda)\neq 0$. ∎

Having now proved that
$\det(\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}})\neq
0$ at $\mathcal{P}$, we can apply 4 and obtain that the specialized series
$G_{i}(0),\ldots,\partial_{u}^{k-1}G_{i}(0)$ are all algebraic over
$\mathbb{K}(t,\epsilon)$. The algebraicity of the complete formal power series
$G_{1},\ldots,G_{n}$ over $\mathbb{K}(t,u,\epsilon)$ then follows again by [4,
Lemma 2.10] from the invertibility of the Jacobian matrix of
$E_{1},\ldots,E_{n}$ considered with respect to the variables
$x_{1},\ldots,x_{n}$ (with $t,u,z_{0},\ldots,z_{nk-1}$ viewed as parameters).
The equalities $F_{i}(t^{\alpha},u)=G_{i}(t,u,0)$ finally imply that
$F_{1},\ldots,F_{n}$ are also algebraic over $\mathbb{K}(t,u)$.

As already mentioned, a strength of the presented method is that it is
effective. Recall that 2 summarizes a bound on the algebraicity degree of all
$F_{i}(t,u)$ and estimates the arithmetic complexity of the algorithm which
computes $F_{i}(t,a)$.

###### Proof sketch of 2.

Using the definition of $\alpha$ and $\beta$ in the proof of 1, the result is
proven along the same lines as the results in [4, Section $3$]. The
algebraicity bound of the shape
${n^{2n^{2}k^{2}}(k+1)^{n^{2}k^{2}(n+2)+n}\delta^{n^{2}k^{2}(n+2)+n}}/{(nk)!^{nk}}$
is a consequence of Bézout’s theorem applied to the saturated ideal defined in
4, while the announced complexity is a consequence of [11, Theorem $2$]. Note
that the factor $(nk)!^{nk}$ comes from exploiting the structure of the
duplicated system by prescribing an action of the symmetric group
$\mathfrak{S}_{nk}$ on it. ∎

##  4 Summary and future work

We can summarize the strategy presented in Section 3 as follows:

  1. 1.

Set up the deformed system (6) and the polynomials
$\operatorname{\mathsf{Det}},P\in\mathbb{L}[X_{1},\dots,X_{n},t,u]$:

$\displaystyle\small\operatorname{\mathsf{Det}}:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n}}E_{1}\\\
\vdots&\ddots&\vdots\\\ \partial_{x_{1}}E_{n}&\dots&\partial_{x_{n}}E_{n}\\\
\end{pmatrix}\quad\text{ \normalsize{and} }\quad
P:=\det\begin{pmatrix}\partial_{x_{1}}E_{1}&\dots&\partial_{x_{n-1}}E_{1}&\partial_{u}E_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
\partial_{x_{1}}E_{n}&\dots&\partial_{x_{n-1}}E_{n}&\partial_{u}E_{n}\\\
\end{pmatrix}.$

  2. 2.

Set up the duplicated polynomial system
$\operatorname{\mathcal{S}_{\mathsf{dup}}}$, consisting of the duplications of
the polynomials $E_{i},\operatorname{\mathsf{Det}},P$. It has $nk(n+2)$
variables and equations.

  3. 3.

Compute a non-trivial element of the saturated ideal
$\langle\operatorname{\mathcal{S}_{\mathsf{dup}}}\rangle:\det(\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}})^{\infty}$.

As illustrated in 1, the deformation step is not always needed. In fact, it is
clear that for a generic system the equation
$\operatorname{\mathsf{Det}}(u)=0$ will have $nk$ distinct non-zero solutions
in $\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$. Moreover, generically, a
non-trivial element of both
$\langle\operatorname{\mathcal{S}_{\mathsf{dup}}}\rangle:\det(\operatorname{\mathsf{Jac}}_{\operatorname{\mathcal{S}_{\mathsf{dup}}}})^{\infty}$
and $\langle\operatorname{\mathcal{S}_{\mathsf{dup}}}\rangle:(\prod_{i\neq
j}{(u_{i}-u_{j})})^{\infty}$ contains the sought annihilating polynomial. In
general, however, the deformation is important, as the following example
shows:

######  Example 2 (cont.).

For $s$ randomly chosen in $\mathbb{Q}$ in (4), one cannot apply Algorithm 1
because the ideal
$\langle\mathcal{S}_{0},\mathcal{S}_{1},m\cdot(u_{1}-u_{2})-1\rangle$ is not
$0$-dimensional, despite the fact $\operatorname{\mathsf{Det}}(u)=0$ has $2$
distinct solutions. However, as predicted by the theory, after the deformation
(6) the system indeed becomes zero-dimensional and can be solved
systematically, even though the actual computation becomes quite heavy.

Our strategy produces a polynomial system with $nk(n+2)+1$ variables and
equations (the additional variable and equation come from the saturation).
Since, already for small values of $n,k$, solving such systems are often out
of reach, we wish to briefly introduce an approach that has a better
algorithmic complexity. The idea is to reduce (by eliminating
$F_{2},\ldots,F_{n}$) the initial system to a single functional equation
$R=0$, and then to use Bousquet-Mélou and Jehanne’s method [5]. This reduces
to solving a polynomial system with just $3nk$ variables and equations. In
order to make this approach work, there are two necessary conditions: the
equation $\partial_{x_{1}}R=0$ should contain enough (that is $nk$) roots in
$\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$ and the corresponding ideal
should be zero-dimensional. Note that $R$ is not a DDE anymore in general, so
these conditions are not guaranteed. The following proposition ensures that
our deformation takes care of the first part, and the example right after
shows that the second condition can still fail in practice.

######  Proposition 7.

Let
$\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{1}}}}}\textbf{{\text{)}}},\dots,\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{n}}}}}\textbf{{\text{)}}}$
be as in 1 and let $E_{1},\ldots,E_{n}$ be the polynomials obtained after
deforming
$\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{1}}}}}\textbf{{\text{)}}},\dots,\textbf{{\text{(E}}}_{\textbf{{\text{F}}}_{\textbf{{\text{n}}}}}\textbf{{\text{)}}}$
as in (7). Let
$U_{1},\ldots,U_{nk}\in\overline{\mathbb{K}(\epsilon)}[[t^{\frac{1}{\star}}]]$
be the distinct non-zero series solutions in $u$ of the equation
$\operatorname{\mathsf{Det}}(u)=0$ and let $R\in(\langle
E_{1},\ldots,E_{n}\rangle:\operatorname{\mathsf{Det}}^{\infty})\cap\mathbb{L}[x_{1},z_{0},\ldots,z_{nk-1},t,u]$.
Then $U_{1},\ldots,U_{nk}$ are also solutions of $\partial_{x_{1}}R(u)=0$.

###### Proof.

Since $R\in\langle E_{1},\dots,E_{n}\rangle$, there exist
$V_{1},\dots,V_{n}\in\mathbb{L}[x_{1},\dots,x_{n},z_{0},\ldots,z_{nk-1},t,u]$
such that $R(U_{\ell})=\sum_{i=1}^{n}E_{i}(U_{\ell})V_{i}(U_{\ell})$ for any
$\ell=1,\dots,nk$. Differentiating with respect to $x_{j}$ for $j=1,\dots,n$
and using that $E_{i}(U_{\ell})=0$ and that $R$ does not depend on $x_{j}$ for
$j\geq 2$, we find

$\small\begin{pmatrix}\partial_{x_{1}}R(U_{\ell})\\\ 0\\\ \vdots\\\
0\end{pmatrix}=\begin{pmatrix}\partial_{x_{1}}E_{1}(U_{\ell})&\dots&\partial_{x_{1}}E_{n}(U_{\ell})\\\
\vdots&\ddots&\vdots\\\
\partial_{x_{n}}E_{1}(U_{\ell})&\dots&\partial_{x_{n}}E_{n}(U_{\ell})\end{pmatrix}\begin{pmatrix}V_{1}(U_{\ell})\\\
\vdots\\\ V_{n}(U_{\ell})\end{pmatrix}.$ (12)

By definition of $U_{\ell}$, the matrix
$(\partial_{x_{j}}E_{i}(U_{\ell}))_{i,j}$ is singular and 3 implies that each
of its $(n-1)\times(n-1)$ minors is non-zero. It follows that we can express
the first row of the matrix as a linear combination of the other rows, then
(12) implies that $\partial_{x_{1}}R(U_{\ell})=0$. ∎

######  Example 2 (cont.).

For $s$ randomly chosen in $\mathbb{Q}$, reducing to a single equation $R$ (by
taking the resultant with respect to $x_{2}$), we indeed find that
$\partial_{x_{1}}R(u)=0$ has two distinct roots in
$\overline{\mathbb{K}}[[t^{\frac{1}{\star}}]]$. However, the computation of a
Gröbner basis reveals that the corresponding ideal has positive dimension.

### Future work.

The present work proves constructively and elementarily the algebraicity of
solutions of systems of DDEs with one catalytic variable. Practical
experiments (which are also based on further algorithmic tools under
development) make us believe that our method has good potential for practical
unresolved combinatorial examples as well. Moreover, there are three most
natural directions for further work. They will deal with complexity
improvements for practical computations and theoretical generalizations:

  1. 1.

Exploit the strategy _hybrid guess-and-prove_ , which was used in [4, Section
$2.2.2$] to tackle first order scalar DDEs efficiently, and which turns out to
be useful when dealing with huge polynomial systems.

  2. 2.

7 ensures that the deformation (6) guarantees $nk$ distinct roots of
$\partial_{x_{1}}R(u)=0$, however, as demonstrated above, the corresponding
ideal might still have positive dimension. Investigate whether it is possible
to overcome this issue.

  3. 3.

Extend the results to a higher number of “nested” catalytic variables, where
the algebraicity is still guaranteed by Popescu’s theorem, but with no
effective version.

### Acknowledgments.

We would like to thank Mohab Safey El Din for interesting discussions and Alin
Bostan for his great support and many valuable comments on the manuscript. We
are also grateful to Mireille Bousquet-Mélou for exciting and enlightening
discussions. We thank the anonymous referees for their helpful comments.

Both authors were supported by the ANR-19-CE40-0018 De Rerum Natura project;
the second author was funded by the DOC fellowship P-26101 of the ÖAW and the
WTZ collaboration project FR-09/2021.

## References

  * [1] Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger  “Analytic Combinatorics of Lattice Paths with Forbidden Patterns, the Vectorial Kernel Method, and Generating Functions for Pushdown Automata”  In _Algorithmica_ 82.3, 2020, pp. 386–428  DOI: 10.1007/s00453-019-00623-3
  * [2] Jérémy Berthomieu, Christian Eder and Mohab Safey El Din  “msolve: A Library for Solving Polynomial Systems”  In _2021 International Symposium on Symbolic and Algebraic Computation_ , ISSAC ’21  Saint Petersburg, Russia: ACM, 2021, pp. 51–58  DOI: 10.1145/3452143.3465545
  * [3] Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec and Claire Pennarun  “On the number of planar Eulerian orientations”  In _European J. Combin._ 65, 2017, pp. 59–91  DOI: 10.1016/j.ejc.2017.04.009
  * [4] Alin Bostan, Frédéric Chyzak, Hadrien Notarantonio and Mohab Safey El Din  “Algorithms for Discrete Differential Equations of Order 1”  In _Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation_ , ISSAC ’22  Villeneuve-d’Ascq, France: ACM, 2022, pp. 101–110  DOI: 10.1145/3476446.3535471
  * [5] Mireille Bousquet-Mélou and Arnaud Jehanne  “Polynomial equations with one catalytic variable, algebraic series and map enumeration”  In _Journal of Combinatorial Theory, Series B_ 96.5, 2006, pp. 623–672  DOI: 10.1016/j.jctb.2005.12.003
  * [6] W. G. Brown and W. T. Tutte  “On the Enumeration of Rooted Non-Separable Planar Maps”  In _Canadian J. of Mathematics_ 16 Cambridge University Press, 1964, pp. 572–577  DOI: 10.4153/CJM-1964-058-7
  * [7] William G. Brown  “Enumeration of Quadrangular Dissections of the Disk”  In _Canadian J. Math._ 17, 1965, pp. 302–317  DOI: 10.4153/CJM-1965-030-1
  * [8] Manfred Buchacher and Manuel Kauers  “Inhomogeneous Restricted Lattice Walks”  In _Sém. Lothar. Combin._ 82B, 2020, pp. Art. 75, 12
  * [9] David Eisenbud  “Commutative Algebra” with a View Toward Algebraic Geometry 150, Graduate Texts in Mathematics  Springer-Verlag, New York, 1995, pp. xvi+785
  * [10] Dorin Popescu  “General Néron Desingularization and Approximation”  In _Nagoya Math. J._ 104, 1986, pp. 85–115  DOI: 10.1017/S0027763000022698
  * [11] Éric Schost  “Computing Parametric Geometric Resolutions”  In _Appl. Algebra Engrg. Comm. Comput._ 13.5, 2003, pp. 349–393  DOI: 10.1007/s00200-002-0109-x
  * [12] W. T. Tutte  “A Census of Planar Triangulations”  In _Canadian J. Math._ 14 Cambridge University Press, 1962, pp. 21–38  DOI: 10.4153/CJM-1962-002-9


###  B.3 Medium regime: proof of Theorem 4

###### Proof.

With the aforementioned analytical framework, we find the constraint
$\textup{srank}(\mathbf{B}^{\natural})\gg\log^{2}n$ to be inevitable. In this
subsection, we relax it to $\textup{srank}(\mathbf{B}^{\natural})\gg\log n$ by
considering a different relaxation event. First, we transform the solution of
(3) to that of the following optimization problem

$\displaystyle\bm{\Pi}^{\textup{opt}}=\textup{argmin}_{\bm{\Pi}}~{}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{Y}-\bm{\Pi}\mathbf{X}\widehat{\mathbf{B}}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}.\vspace{1mm}$

This is due to the energy preserving property of $\bm{\Pi}$, i.e.,
${|\kern-1.72218pt|\kern-1.72218pt|\bm{\Pi}\mathbf{M}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}={|\kern-1.72218pt|\kern-1.72218pt|\mathbf{M}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}$
for an arbitrary matrix $\mathbf{M}\in\mathbb{R}^{n\times(\cdot)}$. Then, we
define the relaxation event ${\cal F}_{\textup{err-
relax}}^{(\textup{multi},2)}$ as

$\displaystyle{\cal F}_{\textup{err-relax}}^{(\textup{multi},2)}\triangleq\
\left\\{\big{\|}\mathbf{Y}_{i,:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\geq\big{\|}\mathbf{Y}_{i,:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{j,:}\big{\|}_{2}^{2},~{}~{}\exists~{}1\leq
j\neq\pi^{\natural}(i)\leq n\right\\}.\vspace{1mm}$

Step I. We would like to show $\overline{{\cal F}}_{\textup{err-
relax}}^{(\textup{multi},2)}\subseteq\\{\bm{\Pi}^{\textup{opt}}=\bm{\Pi}^{\natural}\\}$.
Its proof comes as follows. Conditional on $\overline{{\cal F}}_{\textup{err-
relax}}^{(\textup{multi},2)}$, we have

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{Y}-\bm{\Pi}^{\natural}\mathbf{X}\widehat{\mathbf{B}}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2}=\sum_{i=1}^{n}\big{\|}\mathbf{Y}_{i,:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}<\sum_{i=1}^{n}\big{\|}\mathbf{Y}_{i,:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{\pi(i),:}\big{\|}_{2}^{2}=\
{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{Y}-\bm{\Pi}\mathbf{X}\widehat{\mathbf{B}}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2},\vspace{1mm}$

which implies $\bm{\Pi}^{\textup{opt}}=\bm{\Pi}^{\natural}$ and further leads
to $\\{\bm{\Pi}^{\textup{opt}}\neq\bm{\Pi}^{\natural}\\}\subseteq{\cal
F}_{\textup{err-relax}}^{(\textup{multi},2)}$. Hence, we can upper-bound the
error probability by $\mathbb{P}({\cal F}_{\textup{err-
relax}}^{(\textup{multi},2)})$.

Step II. We decompose the task of upper-bounding $\mathbb{P}({\cal
F}_{\textup{err-relax}}^{(\textup{multi},2)})$ into a series of sub-tasks that
are amenable to analysis. First, we verify that
$\big{\|}\mathbf{Y}_{i,:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\geq\big{\|}\mathbf{Y}_{i,:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{j,:}\big{\|}_{2}^{2}$
is equivalent to

$\displaystyle\underbrace{2\left\langle\mathbf{W}_{i,:},~{}\widehat{\mathbf{B}}^{\top}\left(\mathbf{X}_{j,:}-\mathbf{X}_{\pi^{\natural}(i),:}\right)\right\rangle}_{\textup{LHS}}\
\geq~{}$
$\displaystyle\underbrace{\big{\|}\mathbf{B}^{\natural\top}\mathbf{X}_{\pi^{\natural}(i),:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{j,:}\big{\|}_{2}^{2}-\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}}_{\textup{RHS}}.\vspace{1mm}$

With the union bound, we conclude

$\displaystyle\mathbb{P}({\cal F}_{\textup{err-
relax}}^{(\textup{multi},2)})\leq~{}$
$\displaystyle\mathbb{P}\left(\textup{LHS}\gtrsim\Delta_{(\textup{multi,
2})},~{}\exists~{}1\leq\pi^{\natural}(i)\neq j\leq
n\right)+\mathbb{P}\left(\textup{RHS}\lesssim\Delta_{(\textup{multi,
2})},~{}\exists~{}1\leq\pi^{\natural}(i)\neq j\leq n\right)$
$\displaystyle\leq~{}$ $\displaystyle
n^{2}\cdot\left[\mathbb{P}\left(\textup{LHS}\gtrsim\Delta_{(\textup{multi,
2})}\right)+\mathbb{P}\left(\textup{RHS}\lesssim\Delta_{(\textup{multi,
2})}\right)\right],\vspace{1mm}$

where $\Delta_{(\textup{multi, 2})}$ is defined as $\Delta_{2}+\Delta_{3}$,
whose definitions are referred to (19) and (20).

Then we complete the proof by separately bounding
$\mathbb{P}\left(\textup{LHS}\gtrsim\Delta_{(\textup{multi, 2})}\right)$ and
$\mathbb{P}\left(\textup{RHS}\lesssim\Delta_{(\textup{multi, 2})}\right)$. To
upper-bound $\mathbb{P}\left(\textup{LHS}\gtrsim\Delta_{(\textup{multi,
2})}\right)$, we first perform the following decomposition

$\displaystyle\textup{LHS}=2\langle\mathbf{W}_{i,:},~{}\widetilde{\mathbf{B}}^{\top}(\mathbf{X}_{j,:}-\mathbf{X}_{\pi^{\natural}(i),:})\rangle+2(n-h)^{-1}\langle\mathbf{W}\mathbf{W}_{i,:},~{}\mathbf{X}(\mathbf{X}_{j,:}-\mathbf{X}_{\pi^{\natural}(i),:})\rangle.\vspace{1mm}$

Recalling the definitions of $\mathsf{Term}_{2}$ and $\mathsf{Term}_{3}$ in
(24) and (25), we invoke Lemma 7 and Lemma 8 and obtain
$\mathbb{P}\left(\textup{LHS}\gtrsim\Delta_{(\textup{multi, 2})}\right)\leq
c_{0}n^{-c_{1}}$. For
$\mathbb{P}\left(\textup{RHS}\lesssim\Delta_{(\textup{multi, 2})}\right)$, we
put its analysis in Lemma 9 and then complete the whole proof. ∎

######  Lemma 9.

Consider the sensing matrix $\mathbf{X}$ with its entries $\mathbf{X}_{i,j}$
being sub-gaussian RV with zero mean and unit variance $(1\leq i\leq n,1\leq
j\leq p)$. Assume that $(i)$ $n\gg p\log^{3}n\cdot\log^{2}(n^{2}p^{3})$,
$(ii)$ $\textup{srank}(\mathbf{B}^{\natural})\gg\log n$, $(iii)$ $h\leq c\cdot
n$, $(iv)$ conditional on ${\cal F}_{8}$, and $(v)$
$\log\mathsf{SNR}\gtrsim\log\log n$, we conclude

$\displaystyle\mathbb{P}\left(\big{\|}\mathbf{B}^{\natural\top}\mathbf{X}_{\pi^{\natural}(i),:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{j,:}\big{\|}_{2}^{2}-\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\gtrsim\Delta_{(\textup{multi,
2})}\right)\geq 1-c_{0}n^{-c_{1}},\vspace{1mm}$

where $\Delta_{(\textup{multi, 2})}=\Delta_{2}+\Delta_{3}$, which are defined
in (19) and (20), respectively.

###### Proof.

We begin the proof as

$\displaystyle\mathbb{P}\left(\big{\|}\mathbf{B}^{\natural\top}\mathbf{X}_{\pi^{\natural}(i),:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{j,:}\big{\|}_{2}^{2}-\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\leq\Delta_{(\textup{multi,
2})},~{}\exists~{}i,j\right)$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\big{(}\big{\|}\mathbf{B}^{\natural\top}\big{(}\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:}\big{)}\big{\|}_{2}^{2}-2\big{\|}\mathbf{B}^{\natural\top}\left(\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:}\right)\big{\|}_{2}\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{j,:}\big{\|}_{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\leq\Delta_{(\textup{multi,
2})},~{}\exists~{}i,j\big{)}$ $\displaystyle\leq~{}$
$\displaystyle\underbrace{\mathbb{P}\big{(}\big{\|}\mathbf{B}^{\natural\top}\left(\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:}\right)\big{\|}_{2}\leq\delta,~{}\exists~{}i,j\big{)}}_{\triangleq~{}\zeta_{1}}$
$\displaystyle+~{}$
$\displaystyle\underbrace{\mathbb{P}\left(\frac{\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}}{\delta^{2}}+\frac{2\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{j,:}\big{\|}_{2}}{\delta}+\frac{\Delta_{(\textup{multi,
2})}}{\delta^{2}}\geq
1,~{}\exists~{}i,j\right)}_{\triangleq~{}\zeta_{2}}.\vspace{1mm}$

The following context separately discusses $\zeta_{1}$ and $\zeta_{2}$.
Setting $\delta$ as
$\nicefrac{{{\left|\kern-1.20552pt\left|\kern-1.20552pt\left|\mathbf{B}^{\natural}\right|\kern-1.20552pt\right|\kern-1.20552pt\right|}_{\textup{F}}}}{{4}}$,
we will show $\zeta_{1}\lesssim n^{-c}$ and $\zeta_{2}\lesssim n^{-c}$ under
the assumptions in Lemma 9 and ${\cal F}_{8}$.

Analysis of $\zeta_{1}$. We set $\delta$ as
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}/4$
and can upper bound $\zeta_{1}$ as

$\displaystyle\zeta_{1}\leq~{}$
$\displaystyle\sum_{i=1}^{n}\sum_{j\neq\pi^{\natural}(i)}\
\mathbb{P}\left(\big{\|}\mathbf{B}^{\natural\top}(\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:})\big{\|}_{2}\leq\delta\right)\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}\
\sum_{i=1}^{n}\sum_{j\neq\pi^{\natural}(i)}e^{-c_{0}\cdot\textup{srank}(\mathbf{B}^{\natural})}$
$\displaystyle\leq~{}$ $\displaystyle n^{2}\cdot
e^{-c_{0}\cdot\textup{srank}(\mathbf{B}^{\natural})},$ (43)

where \raisebox{-.8pt}{1}⃝ comes from the _small ball_ probability as restated
in Lemma 22. Due to the assumption such that
$\textup{srank}(\mathbf{B}^{\natural})\gg\log n$, we have $\zeta_{1}\lesssim
n^{-c}$. When $\mathbf{X}_{ij}$ is with log-concave property, we can pick a
smaller $\delta$ and remove this assumption. A detailed explanation is
deferred to Lemma 11.

Analysis of $\zeta_{2}$. We prove that $\zeta_{2}$ to be less than $c_{0}\cdot
n^{-c_{1}}$ under the assumptions in Lemma 9. Conditional on ${\cal F}_{8}$
and invoke Lemma 10 (attached as follows), with probability $1-c_{0}\cdot
n^{-c_{1}}$ we have

$\displaystyle\frac{\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}^{2}_{2}}{\delta^{2}}\leq~{}$
$\displaystyle\frac{2\big{\|}(\widetilde{\mathbf{B}}-\mathbf{B}^{\natural})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}^{2}_{2}}{\delta^{2}}+\frac{2\big{\|}\mathbf{W}^{\top}\mathbf{X}\mathbf{X}_{i,:}\big{\|}^{2}_{2}}{(n-h)^{2}\delta^{2}}$
$\displaystyle\lesssim~{}$
$\displaystyle\frac{p\log^{3}n\cdot\log^{2}(n^{2}p^{3})}{n}+\frac{\log^{2}n}{\mathsf{SNR}}.$
(44)

Recalling the assumptions $\mathsf{SNR}\gtrsim\log^{c}n$ and $n\gg
p\cdot(\log^{3}n)\cdot\log^{2}(n^{2}p^{3})$, we have
$\nicefrac{{\|(\widehat{\mathbf{B}}-\mathbf{B}^{\natural})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\|_{2}}}{{\delta}}$
approach zero as $n$ goes to infinity. Following the same logic, we conclude
$\nicefrac{{\|(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{j,:}\|_{2}}}{{\delta}}\rightarrow
0$ as $n\rightarrow\infty$. Then we turn to
$\nicefrac{{\Delta_{(\textup{multi, 2})}}}{{\delta^{2}}}$ and obtain

$\displaystyle\frac{\Delta_{(\textup{multi, 2})}}{\delta^{2}}\lesssim~{}$
$\displaystyle\
\frac{\log^{2}n}{\sqrt{m\cdot\mathsf{SNR}}}+\frac{\log^{2}n}{\mathsf{SNR}}\sqrt{\frac{p}{nm}}+\frac{p\cdot\log^{2}n}{n\cdot\mathsf{SNR}}.$
(45)

Following similar procedures as above, we can prove
$\nicefrac{{\Delta_{(\textup{multi, 2})}}}{{\delta^{2}}}$ to be a small
positive constant. Combing (44) and (45) together, we conclude

$\displaystyle\frac{\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}}{\delta^{2}}+\frac{2\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{j,:}\big{\|}_{2}}{\delta}+\frac{\Delta_{(\textup{multi,
2})}}{\delta^{2}}<1,\vspace{1mm}$

conditional on ${\cal F}_{8}$ and
${\left\|\mathbf{W}^{\top}\mathbf{X}\mathbf{X}_{i,:}\right\|}_{2}\lesssim\
(n\log n)\sqrt{m\sigma^{2}}$. Hence, we obtain

$\displaystyle\zeta_{2}\leq\mathbb{P}\left({\left\|\mathbf{W}^{\top}\mathbf{X}\mathbf{X}_{i,:}\right\|}_{2}\gtrsim\
(n\log n)\sqrt{m\sigma^{2}},~{}\exists~{}1\leq i\leq
n\right)\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{2}⃝}}}}{{\leq}}c_{0}\cdot
n^{-c_{1}}$ (46)

where \raisebox{-.8pt}{2}⃝ is due to Lemma 10. Combining with (B.3) then
completes the proof. ∎

######  Lemma 10.

Conditioning on ${\cal F}_{2}$, we have

$\displaystyle\mathbb{P}\left({\left\|\mathbf{W}^{\top}\mathbf{X}\mathbf{X}_{i,:}\right\|}_{2}\leq\
c(n\log n)\sqrt{m\sigma^{2}},~{}\exists~{}1\leq i\leq n\right)\geq
1-c_{0}n^{-c_{1}}.\vspace{1mm}$

###### Proof.

First, we consider a fixed index $i$. Adopting the _leave-one-out_ technique,
we construct a perturbed matrix $\mathbf{X}_{\setminus(i)}$ by replicating
matrix $\mathbf{X}$ except its $i$th row $\mathbf{X}_{i,:}$, which is replaced
with an i.i.d. sample $\mathbf{X}^{{}^{\prime}}_{i,:}$. Then we obtain

$\displaystyle\mathbb{P}\left({\left\|\mathbf{X}_{i,:}\mathbf{X}^{\top}\mathbf{W}\right\|}_{2}\geq
c(n\log n)\sqrt{m\sigma^{2}}\right)$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\left(\big{\|}\mathbf{X}_{i,:}\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}\big{\|}_{2}+\big{\|}\mathbf{X}_{i,:}(\mathbf{X}-\mathbf{X}_{\setminus(i)})^{\top}\mathbf{W}\big{\|}_{2}\geq
c(n\log n)\sqrt{m\sigma^{2}}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}~{}$
$\displaystyle\underbrace{\mathbb{P}\left(\big{\|}\mathbf{X}_{i,:}\big{(}\mathbf{X}-\mathbf{X}_{\setminus(i)}\big{)}^{\top}\mathbf{W}\big{\|}_{2}\geq
c_{0}(n\log
n)\sqrt{m\sigma^{2}}\right)}_{\triangleq~{}\zeta_{1}}+\underbrace{\mathbb{P}\left(\big{\|}\mathbf{X}_{i,:}\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}\big{\|}_{2}\geq
c_{1}(n\log
n)\sqrt{m\sigma^{2}}\right)}_{\triangleq~{}\zeta_{2}},\vspace{1mm}$

where \raisebox{-.8pt}{1}⃝ is due to the union bound.

Analysis of $\zeta_{1}$. One noticeable property of
$\mathbf{X}_{\setminus(i)}-\mathbf{X}$ is that only its $i$th row is non-zero.
Hence we obtain the relation

$\displaystyle\big{\|}\mathbf{X}_{i,:}(\mathbf{X}-\mathbf{X}_{\setminus(i)})^{\top}\mathbf{W}\big{\|}_{2}\
\leq{\left\|\mathbf{X}_{i,:}\right\|}_{2}\cdot{|\kern-1.72218pt|\kern-1.72218pt|(\mathbf{X}-\mathbf{X}_{\setminus(i)})^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}={\left\|\mathbf{X}_{i,:}\right\|}_{2}\cdot\big{\|}\mathbf{X}_{i,:}-\mathbf{X}^{{}^{\prime}}_{i,:}\big{\|}_{2}{\left\|\mathbf{W}_{i,:}\right\|}_{2}.\vspace{1mm}$

Recalling the definition of ${\cal F}_{2}$, $n\gg p\log^{6}n$, and
${\left\|\mathbf{W}_{i,:}\right\|}_{2}\leq 2\sqrt{m\sigma^{2}}$ holds with
probability exceeding $1-c_{0}\cdot n^{-c_{1}}$, we have $\zeta_{1}\lesssim
n^{-c_{1}}$ conditioning on ${\cal F}_{2}$.

Analysis of $\zeta_{2}$. Due to the construction of
$\mathbf{X}_{\setminus(i)}$, we have $\mathbf{X}_{i,:}$ to be independent of
$\mathbf{X}_{\setminus(i)}$. Hence, we condition on
$\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}$ and obtain

$\displaystyle\zeta_{2}\leq~{}$
$\displaystyle\mathbb{P}\left(\big{\|}\mathbf{X}_{i,:}\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}\big{\|}_{2}\geq
c_{1}n(\log
n)\sqrt{m\sigma^{2}},~{}{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\lesssim
n\sqrt{m\sigma^{2}}\right)+\mathbb{P}\left({|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\gtrsim
n\sqrt{m\sigma^{2}}\right)$ $\displaystyle\leq~{}$ $\displaystyle\
\underbrace{\mathbb{E}_{\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}}\mathbbm{1}\left(\big{\|}\mathbf{X}_{i,:}\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}\big{\|}_{2}\geq
c_{2}(\log
n){|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\right)}_{\triangleq~{}\zeta_{2,1}}+\
\underbrace{\mathbb{P}\left({|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\gtrsim
n\sqrt{m\sigma^{2}}\right)}_{\triangleq~{}\zeta_{2,2}}.\vspace{1mm}$

For $\zeta_{2,1}$, we define
$Z=\big{\|}\mathbf{X}_{i,:}\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}\big{\|}_{2}^{2}$
and have

$\displaystyle\zeta_{2,1}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{2}⃝}}}}{{\leq}}~{}$
$\displaystyle\mathbb{E}_{\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}}\mathbbm{1}\left(\left\lvert
Z-\mathbb{E}Z\right\rvert\geq
c_{3}(\log^{2}n){|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{3}⃝}}}}{{\leq}}~{}$
$\displaystyle\mathbb{E}_{\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}}\exp\left(-\left(\frac{(\log^{4}n){|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{4}}{{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}\mathbf{W}^{\top}\mathbf{X}_{\setminus(i)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}}\wedge\
\frac{\left(\log^{2}n\right){|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}}{{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}\mathbf{W}^{\top}\mathbf{X}_{\setminus(i)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}}\right)\right)\
\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{4}⃝}}}}{{\leq}}n^{-c},$

where \raisebox{-.8pt}{2}⃝ is due to
$\mathbb{E}_{\mathbf{X}_{i,:}}Z={|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}$,
\raisebox{-.8pt}{3}⃝ is because of the Hanson-Wright inequality (Theorem
$6.2.1$ in Vershynin (2018)), and \raisebox{-.8pt}{4}⃝ is due to the stable
rank $\textup{srank}(\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W})\geq 1$. Then
we move to $\zeta_{2,2}$ and have

$\displaystyle\mathbb{P}\left({|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}^{\top}\mathbf{W}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\gtrsim
n\sqrt{m\sigma^{2}}\right)\leq\
\mathbb{P}\left({|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{W}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\gtrsim
n\sqrt{m\sigma^{2}}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{5}⃝}}}}{{\leq}}~{}$
$\displaystyle\mathbb{P}\left({|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}\gtrsim\sqrt{n}+\sqrt{p}\right)+\
\mathbb{P}\left({\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{W}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\gtrsim\frac{n\sqrt{m\sigma^{2}}}{\sqrt{n}+\sqrt{p}},~{}\
{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}\lesssim\sqrt{n}+\sqrt{p}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{6}⃝}}}}{{\leq}}~{}$
$\displaystyle\mathbb{P}\left({|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(i)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}\gtrsim\sqrt{n}+\sqrt{p}\right)+\
\mathbb{P}\left({\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{W}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\geq\sqrt{2nm}\sigma\right)\
\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{7}⃝}}}}{{\leq}}e^{-c_{0}n}+e^{-c_{1}nm},$

where \raisebox{-.8pt}{5}⃝ is because of the union bound, in
\raisebox{-.8pt}{6}⃝ we use $p\leq n$, and in \raisebox{-.8pt}{7}⃝ we use
${|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}\gtrsim\sqrt{n}+\sqrt{p}$
with probability less than $e^{-c_{0}n}$ (c.f. Theorem $4.6.1$ in Vershynin
(2018)) and the fact
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{W}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2}/\sigma^{2}$
is a $\chi^{2}$-RV with $nm$ freedom, and Lemma 20.

Ultimately, we complete the proof by iterating the above proof procedures to
all indices and invoking the union bound. ∎

###  B.4 Hard regime: proof of Theorem 5

This subsection aims to strength Theorem 4, which reduces the requirement on
$\textup{srank}(\mathbf{B}^{\natural})$ from $\Omega(\log n)$ to $\Omega(1)$.
As compensation, we need to put an extra assumption on $\mathbf{X}_{ij}$’s
distribution, namely, $\mathbf{X}_{ij}$ follows a log-concave sub-gaussian
distribution.

######  Lemma 11.

Consider the sensing matrix $\mathbf{X}$ with its entries $\mathbf{X}_{i,j}$
being log-concave sub-gaussian RV with zero mean and unit variance $(1\leq
i\leq n,1\leq j\leq p)$. Assume that $(i)$ $n\gg
p^{1+\varepsilon}\log^{3(1+\varepsilon)}n\cdot\log^{2(1+\varepsilon)}(n^{2}p^{3})$,
$(ii)$ $\textup{srank}(\mathbf{B}^{\natural})\geq c(\varepsilon)$, $(iii)$
$h\leq c\cdot n$, $(iv)$ conditional on ${\cal F}_{8}$, and

$\displaystyle\textup{(}v)~{}~{}\log\mathsf{SNR}\gtrsim\frac{\log
n}{\textup{srank}(\mathbf{B}^{\natural})}+\log\log n,$ (47)

we conclude

$\displaystyle\mathbb{P}\left(\big{\|}\mathbf{B}^{\natural\top}\mathbf{X}_{\pi^{\natural}(i),:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{j,:}\big{\|}_{2}^{2}-\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\gtrsim\Delta_{(\textup{multi,
2})}\right)\geq 1-c_{0}n^{-c_{1}},\vspace{1mm}$

where $\varepsilon>0$ is an arbitrary positive constant; $c(\varepsilon)$ is
some positive constant depending only on $\varepsilon$; and
$\Delta_{(\textup{multi, 2})}=\Delta_{2}+\Delta_{3}$, whose definitions can be
found in (19) and (20), respectively.

###### Proof.

Same as the procedure in Lemma 9, we begin the proof with the union bound

$\displaystyle\mathbb{P}\left(\big{\|}\mathbf{B}^{\natural\top}\mathbf{X}_{\pi^{\natural}(i),:}-\widehat{\mathbf{B}}^{\top}\mathbf{X}_{j,:}\big{\|}_{2}^{2}-\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\leq\Delta_{(\textup{multi,
2})},~{}\exists~{}i,j\right)$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\big{(}\big{\|}\mathbf{B}^{\natural\top}\big{(}\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:}\big{)}\big{\|}_{2}^{2}-2\big{\|}\mathbf{B}^{\natural\top}\left(\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:}\right)\big{\|}_{2}\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{j,:}\big{\|}_{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}\leq\Delta_{(\textup{multi,
2})},~{}\exists~{}i,j\big{)}$ $\displaystyle\leq~{}$
$\displaystyle\underbrace{\mathbb{P}\big{(}\big{\|}\mathbf{B}^{\natural\top}\left(\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:}\right)\big{\|}_{2}\leq\delta,~{}\exists~{}i,j\big{)}}_{\triangleq~{}\zeta_{1}}$
$\displaystyle+~{}$
$\displaystyle\underbrace{\mathbb{P}\left(\frac{\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}_{2}^{2}}{\delta^{2}}+\frac{2\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{j,:}\big{\|}_{2}}{\delta}+\frac{\Delta_{(\textup{multi,
2})}}{\delta^{2}}\geq
1,~{}\exists~{}i,j\right)}_{\triangleq~{}\zeta_{2}}.\vspace{1mm}$

Due to the log-concave assumption on $\mathbf{X}_{ij}$’s distributions, we are
able to pick a smaller $\delta$. Here we set $\delta$ as
${|\kern-1.72218pt|\kern-1.72218pt|\mathbf{B}^{\natural}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\cdot
n^{-\nicefrac{{c_{0}}}{{\textup{srank}(\mathbf{B}^{\natural})}}}$. We would
like to show $\zeta_{1}\leq c_{0}n^{-c_{1}}$ and $\zeta_{2}\leq
c_{0}n^{-c_{1}}$ under the assumptions in Lemma 11.

Analysis of $\zeta_{1}$. According to the _small ball_ probability in Theorem
$1.3$ (Paouris, 2012), which is also stated as Lemma 23, we have

$\displaystyle\zeta_{1}\leq\sum_{i=1}^{n}\sum_{j\neq\pi^{\natural}(i)}\
\mathbb{P}\left({\left\|\left(\mathbf{X}_{\pi^{\natural}(i),:}-\mathbf{X}_{j,:}\right)\mathbf{B}^{\natural}\right\|}_{2}\leq\delta\right)\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}\
\sum_{i=1}^{n}\sum_{j\neq\pi^{\natural}(i)}n^{-c_{0}}\lesssim n^{-c_{1}}.$
(48)

Note that the requirement $\textup{srank}(\mathbf{B}^{\natural})\gg\log n$ is
no longer needed here.

Analysis of $\zeta_{2}$. Then we move on to the analysis of $\zeta_{2}$. Same
as Lemma 11, we have

$\displaystyle\frac{\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}^{2}_{2}}{\delta^{2}}\leq~{}$
$\displaystyle\frac{2\big{\|}(\widetilde{\mathbf{B}}-\mathbf{B}^{\natural})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}^{2}_{2}}{\delta^{2}}+\frac{2\big{\|}\mathbf{W}^{\top}\mathbf{X}\mathbf{X}_{i,:}\big{\|}^{2}_{2}}{(n-h)^{2}\delta^{2}}$
$\displaystyle\lesssim~{}$
$\displaystyle\frac{p\log^{3}n\cdot\log^{2}(n^{2}p^{3})}{n^{1-\nicefrac{{c}}{{\textup{srank}(\mathbf{B}^{\natural})}}}}+\frac{\log^{2}n\cdot
n^{\nicefrac{{c}}{{\textup{srank}(\mathbf{B}^{\natural})}}}}{\mathsf{SNR}}$
(49)

hold with probability $1-c_{0}n^{-c_{1}}$ when conditional on ${\cal F}_{8}$.
When
$\textup{srank}(\mathbf{B}^{\natural})\geq\nicefrac{{c(1+\varepsilon)}}{{\varepsilon}}$
and $\log\mathsf{SNR}\gtrsim\frac{\log
n}{\textup{srank}(\mathbf{B}^{\natural})}+\log\log n$, we have
$\nicefrac{{\big{\|}(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{\pi^{\natural}(i),:}\big{\|}^{2}_{2}}}{{\delta^{2}}}$
approach to zero when $n$ goes to infinity. Following the same logic, we have
$\nicefrac{{\|(\mathbf{B}^{\natural}-\widehat{\mathbf{B}})^{\top}\mathbf{X}_{j,:}\|_{2}}}{{\delta}}$
be arbitrarily small provided $n$ is sufficiently large. Afterwards, we
consider $\frac{\Delta_{(\textup{multi, 2})}}{\delta^{2}}$ and expand it as

$\displaystyle\frac{\Delta_{(\textup{multi, 2})}}{\delta^{2}}\lesssim\
n^{\nicefrac{{c}}{{\textup{srank}(\mathbf{B}^{\natural})}}}\left(\frac{\log^{2}n}{\sqrt{m\cdot\mathsf{SNR}}}+\frac{\log^{2}n}{\mathsf{SNR}}\sqrt{\frac{p}{nm}}+\frac{p\cdot\log^{2}n}{n\cdot\mathsf{SNR}}\right).$
(50)

Following similar procedures as above, we can prove
$\frac{\Delta_{(\textup{multi, 2})}}{\delta^{2}}$ to be a small positive
constant given (47), which enables us to bound $\zeta_{2}$ in the same way as
(46). Combing (48), (49), and (50) hence completes the proof. ∎

###  B.5 Supporting lemmas

######  Lemma 12.

For an arbitrary row $\mathbf{X}_{i,:}$, we have

$\displaystyle{\left\|\mathbf{M}^{\top}\mathbf{X}_{i,:}\right\|}_{2}\lesssim\sqrt{\log
n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}},\vspace{1mm}$

with probability exceeding $1-n^{-c}$.

###### Proof.

This lemma is a direct consequence of the Hanson-Wright inequality (Theorem
$6.2.1$ in Vershynin (2018)). Easily we can verify
$\mathbb{E}{\left\|\mathbf{M}^{\top}\mathbf{X}_{i,:}\right\|}_{2}^{2}={|\kern-1.72218pt|\kern-1.72218pt|\mathbf{M}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}$
and hence

$\displaystyle\mathbb{P}\left({\left\|\mathbf{M}^{\top}\mathbf{X}_{i,:}\right\|}_{2}^{2}\gtrsim\log
n{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{M}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2}\right){\leq}~{}$
$\displaystyle\mathbb{P}\left(\left\lvert{\left\|\mathbf{M}^{\top}\mathbf{X}_{i,:}\right\|}_{2}^{2}-{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{M}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}\right\rvert\gtrsim(\log
n){|\kern-1.72218pt|\kern-1.72218pt|\mathbf{M}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}\right)$
$\displaystyle\leq~{}$ $\displaystyle\exp\left(-c_{0}\left(\frac{\log
n{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{M}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}}{{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{M}^{\top}\mathbf{M}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{OP}}}\wedge\frac{(\log^{2}n){|\kern-1.72218pt|\kern-1.72218pt|\mathbf{M}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{4}}{{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{M}^{\top}\mathbf{M}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2}}\right)\right)\leq
n^{-1-c}.\vspace{1mm}$

Adopting the union bound, we have

$\displaystyle\mathbb{P}\left({\left\|\mathbf{M}^{\top}\mathbf{X}_{i,:}\right\|}_{2}^{2}\gtrsim\log
n{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{M}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2},~{}\forall~{}i\right)\leq
n\cdot n^{-1-c}=n^{-c}.\vspace{1mm}$

Following the same procedure, we can obtain the same conclusions for
$\big{\|}\mathbf{M}^{\top}\mathbf{X}_{i,:}^{{}^{\prime}}\big{\|}_{2}$. ∎

######  Lemma 13.

For an arbitrary row $\mathbf{X}_{i,:}$ (or $\mathbf{X}_{i,:}^{{}^{\prime}}$),
we have

$\displaystyle\langle\mathbf{X}_{i,:},\mathbf{X}_{j,:}^{{}^{\prime}}\rangle~{}$
$\displaystyle\lesssim(\log n)\sqrt{p},~{}~{}1\leq i,j\leq n;$
$\displaystyle\langle\mathbf{X}_{i,:},\mathbf{X}_{j,:}\rangle~{}$
$\displaystyle\lesssim(\log n)\sqrt{p},~{}~{}1\leq i\neq j\leq n;$
$\displaystyle\langle\mathbf{X}^{{}^{\prime}}_{i,:},\mathbf{X}^{{}^{\prime}}_{j,:}\rangle~{}$
$\displaystyle\lesssim(\log n)\sqrt{p},~{}~{}1\leq i\neq j\leq n,\vspace{1mm}$

hold with probability $1-n^{-c}$.

###### Proof.

Denote $\bm{z}_{1},\bm{z}_{2}\in\mathbb{R}^{p}$ are two i.i.d isotropic sub-
gaussian RVs with ${\left\|\bm{z}_{i}\right\|}_{\psi_{2}}\leq K$ $(i=1,2)$,
where definition of ${\left\|\cdot\right\|}_{\psi_{2}}$ is referred to
Vershynin (2018) (Definition $3.2.1$). Exploiting the independence between
$\bm{z}_{1}$ and $\bm{z}_{2}$, we conclude

$\displaystyle\mathbb{P}\left(\left\langle\bm{z}_{1},\bm{z}_{2}\right\rangle\gtrsim\sqrt{p\log
n}\right)\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}~{}$
$\displaystyle\mathbb{P}\left(\left\langle\bm{z}_{1},\bm{z}_{2}\right\rangle\gtrsim(\log
n)\sqrt{p},{\left\|\bm{z}_{2}\right\|}_{2}\leq\sqrt{p\log
n}\right)+\mathbb{P}\left({\left\|\bm{z}_{2}\right\|}_{2}\gtrsim\sqrt{p\log
n}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{2}⃝}}}}{{\leq}}~{}$
$\displaystyle 2\exp\left(-\frac{c_{0}\cdot p\log^{2}n}{2p\log
n}\right)+\mathbb{P}\left(\left\lvert{\left\|\bm{z}_{2}\right\|}_{2}^{2}-p\right\rvert\geq
p\log
n\right)\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{3}⃝}}}}{{\leq}}n^{-c},\vspace{1mm}$

where \raisebox{-.8pt}{1}⃝ and \raisebox{-.8pt}{2}⃝ are due to the union
bound, and \raisebox{-.8pt}{3}⃝ is because of Hanson-Wright inequality.
Following the same procedure, we can prove the claims in Lemma 13 by invoking
the union bound. ∎

######  Lemma 14.

We conclude $\mathbb{P}\left({\cal F}_{4}\right)\geq 1-ne^{-cnp}$.

This lemma is a direct consequence of Lemma 20 and hence its proof is omitted.

######  Lemma 15.

Conditional on the intersection of events ${\cal F}_{3}\bigcap{\cal F}_{4}$,
we have $\mathbb{P}\left({\cal F}_{5}\right)\geq 1-n^{-c}$.

###### Proof.

For a fixed row index $s$ ($1\leq s\leq n$), we have

$\displaystyle\mathbb{P}\left({\left\|\mathbf{X}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim(\log
n)\sqrt{np}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}~{}$
$\displaystyle\mathbb{P}\left({\left\|\left(\mathbf{X}-\mathbf{X}_{\setminus(s)}\right)\mathbf{X}_{s,:}\right\|}_{2}\gtrsim
p\log
n\right)+\mathbb{P}\left({\left\|\mathbf{X}_{\setminus(s)}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim(\log
n)\sqrt{np}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{2}⃝}}}}{{\leq}}~{}$
$\displaystyle\underbrace{\mathbb{P}\left(\left({\left\|\mathbf{X}_{s,:}\right\|}_{2}+\|\mathbf{X}_{s,:}^{{}^{\prime}}\|_{2}\right){\left\|\mathbf{X}_{s,:}\right\|}_{2}\gtrsim
p\log
n\right)}_{\triangleq\zeta_{1}}+\underbrace{\mathbb{P}\left({\left\|\mathbf{X}_{\setminus(s)}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim(\log
n)\sqrt{np}\right)}_{\triangleq\zeta_{2}},\vspace{1mm}$

where in \raisebox{-.8pt}{1}⃝ we use the union bound and the fact $n\geq p$;
and in \raisebox{-.8pt}{2}⃝ we use the definition of
$\mathbf{X}_{\setminus(s)}$ such that the difference
$\mathbf{X}-\mathbf{X}_{\setminus(s)}$ only have non-zero elements in the
$s$th column. Conditional on the intersection of events ${\cal
F}_{2}\bigcap{\cal F}_{3}\bigcap{\cal F}_{4}$, we conclude that probability
$\zeta_{1}$ is zero and probability $\zeta_{2}$ is upper-bounded as

$\displaystyle\mathbb{P}\left({\left\|\mathbf{X}_{\setminus(s)}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim(\log
n)\sqrt{np}\right)\leq~{}$
$\displaystyle\mathbb{P}\left(\left\lvert{\left\|\mathbf{X}_{\setminus(s)}\mathbf{X}_{s,:}\right\|}_{2}^{2}-{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{X}_{\setminus(s)}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2}\right\rvert\gtrsim(\log^{2}n)np\right)$
$\displaystyle\leq~{}$
$\displaystyle\exp\left(-c_{0}\left(\frac{(\log^{2}n)np}{{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(s)}^{\top}\mathbf{X}_{\setminus(s)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}}\wedge\frac{(\log
n)^{4}n^{2}p^{2}}{{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{X}_{\setminus(s)}^{\top}\mathbf{X}_{\setminus(s)}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}^{2}}\right)\right)\leq
n^{-c}.\vspace{1mm}$

Thus the proof is completed by invoking the union bound since

$\displaystyle\mathbb{P}\left({\left\|\mathbf{X}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim(\log
n)\sqrt{np},~{}\exists~{}s\right)\leq
n\cdot\mathbb{P}\left({\left\|\mathbf{X}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim(\log
n)\sqrt{np}\right)\ \leq n\left(\zeta_{1}+\zeta_{2}\right)\leq
n^{1-c}=n^{-c^{{}^{\prime}}}.\vspace{1mm}$

∎

######  Lemma 16.

Conditional on ${\cal F}_{4}$, we have $\mathbb{P}({\cal F}_{6})\geq
1-cp^{-2}$.

###### Proof.

We assume that the first $h$ rows of $\mathbf{X}$ are permuted w.l.o.g. Due to
the i.i.d. distribution of $\\{\mathbf{X}_{i,:}\\}_{i=1}^{n}$ and
$\\{\mathbf{X}^{{}^{\prime}}_{i,:}\\}_{i=1}^{n}$, we conclude

$\displaystyle\mathbb{P}({\cal F}_{6})\leq
n^{2}\cdot\mathbb{P}\left(\big{\|}\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}\big{\|}_{2}\gtrsim\
\frac{(\log n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right).$
(51)

First, we expand $\mathbf{X}^{\top}\bm{\Pi}^{\natural}\mathbf{X}$ as

$\displaystyle\mathbf{X}^{\top}\bm{\Pi}^{\natural}\mathbf{X}=\sum_{i=1}^{h}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}+\
\sum_{i=h+1}^{n}\mathbf{X}_{i,:}\mathbf{X}_{i,:}^{\top},\vspace{1mm}$

and obtain

$\displaystyle\mathbb{P}\left(\big{\|}\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}\big{\|}_{2}\gtrsim\
\frac{(\log n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)$
$\displaystyle\leq~{}$ $\displaystyle\
\mathbb{P}\left(\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i=1}^{h}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}+\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i=h+1}^{n}\left(\mathbf{X}_{i,:}\mathbf{X}^{\top}_{i,:}-\mathbf{I}\right)\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\gtrsim\frac{(\log
n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}~{}$
$\displaystyle\
\underbrace{\mathbb{P}\left(\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i=1}^{h}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}^{\top}_{i,:}\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\gtrsim\frac{(\log
n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)}_{\triangleq~{}\zeta_{1}}$
$\displaystyle+~{}$ $\displaystyle\
\underbrace{\mathbb{P}\left(\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i=h+1}^{n}\left(\mathbf{X}_{i,:}\mathbf{X}_{i,:}^{\top}-\mathbf{I}\right)\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\gtrsim\frac{(\log
n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)}_{\triangleq~{}\zeta_{2}},$
(52)

where \raisebox{-.8pt}{1}⃝ is because of the union bound. The proof is
complete by proving $\zeta_{1}\leq 6n^{-2}p^{-2}$ and $\zeta_{2}\leq
4n^{-2}p^{-2}$. The technical details come as follows.

Analysis of $\zeta_{1}$. According to Lemma $8$ in Pananjady et al. (2018)
(restated as Lemma 21), we can decompose the set
$\left\\{i:\pi^{\natural}(i)\neq i\right\\}$ into three disjoint sets ${\cal
I}_{\ell}$ $(1\leq\ell\leq 3)$, such that $i$ and $\pi^{\natural}(i)$ does not
reside within the same set. And the cardinality $h_{\ell}$ of set ${\cal
I}_{\ell}$ satisfies $h_{\ell}\geq\lfloor h/5\rfloor$. Adopting the union
bound, we can upper-bound $\zeta_{1}$ as

$\displaystyle\zeta_{1}\leq~{}$
$\displaystyle\sum_{\ell=1}^{3}\mathbb{P}\left(\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i\in{\cal
I}_{\ell}}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\gtrsim\frac{(\log
n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)$
$\displaystyle\leq~{}$
$\displaystyle\sum_{\ell=1}^{3}\mathbb{P}\left(\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i\in{\cal
I}_{\ell}}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{OP}}\gtrsim\frac{(\log
n)(\log n^{2}p^{3})\sqrt{p}}{\sqrt{n}}\right).$ (53)

Defining $\mathbf{Z}_{\ell}$ as $\mathbf{Z}_{\ell}=\sum_{i\in{\cal
I}_{\ell}}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}^{\top}_{i,:}$, we would
bound the above probability by invoking the matrix Bernstein inequality
(Theorem $7.3.1$ in Tropp (2015)). First, we have

$\displaystyle\mathbb{E}\left(\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}^{\top}_{i,:}\right)=\left(\mathbb{E}\mathbf{X}_{\pi^{\natural}(i),:}\right)\left(\mathbb{E}\mathbf{X}_{i,:}\right)^{\top}=\bm{0},$

due to the independence between $\mathbf{X}_{\pi^{\natural}(i),:}$ and
$\mathbf{X}_{i,:}$. Then we upper bound
${\left\|\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\right\|}_{2}$
as

$\displaystyle{\left\|\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\right\|}_{2}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{2}⃝}}}}{{=}}\
{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{3}⃝}}}}{{=}}\
{\left\|\mathbf{X}_{\pi^{\natural}(i),:}\right\|}_{2}{\left\|\mathbf{X}_{i,:}\right\|}_{2}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{4}⃝}}}}{{\lesssim}}p\log
n,$

where \raisebox{-.8pt}{2}⃝ is because
$\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}$ is rank-$1$,
\raisebox{-.8pt}{3}⃝ is due to the fact
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bm{u}\bm{v}^{\top}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}^{2}=\operatorname{Tr}\left(\bm{u}\bm{v}^{\top}\bm{v}\bm{u}^{\top}\right)={\left\|\bm{u}\right\|}_{2}^{2}{\left\|\bm{v}\right\|}_{2}^{2}$
for arbitrary vector $\bm{u},\bm{v}\in\mathbb{R}^{p}$, and
\raisebox{-.8pt}{4}⃝ is because of event ${\cal F}_{3}$.

In the end, we calculate
$\mathbb{E}\left(\mathbf{Z}_{\ell}\mathbf{Z}_{\ell}^{\top}\right)$ and
$\mathbb{E}\left(\mathbf{Z}_{\ell}^{\top}\mathbf{Z}_{\ell}\right)$ as

$\displaystyle\mathbb{E}\left(\mathbf{Z}_{\ell}\mathbf{Z}_{\ell}^{\top}\right)=~{}$
$\displaystyle\mathbb{E}\bigg{(}\sum_{i_{1},i_{2}\in{\cal
I}_{\ell}}\mathbf{X}_{\pi^{\natural}(i_{1}),:}\mathbf{X}^{\top}_{i_{1},:}\mathbf{X}_{i_{2},:}\mathbf{X}^{\top}_{\pi^{\natural}(i_{2}),:}\bigg{)}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{5}⃝}}}}{{=}}\
\mathbb{E}\bigg{(}\sum_{i\in{\cal
I}_{\ell}}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\mathbf{X}_{i,:}\mathbf{X}^{\top}_{\pi^{\natural}(i),:}\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{6}⃝}}}}{{=}}~{}$
$\displaystyle\ \mathbb{E}\bigg{(}\sum_{i\in{\cal
I}_{\ell}}\mathbf{X}_{\pi^{\natural}(i),:}\mathbb{E}\left(\mathbf{X}^{\top}_{i,:}\mathbf{X}_{i,:}\right)\mathbf{X}^{\top}_{\pi^{\natural}(i),:}\bigg{)}=p\bigg{(}\sum_{i\in{\cal
I}_{\ell}}\mathbb{E}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}^{\top}_{\pi^{\natural}(i),:}\bigg{)}=ph_{i}\mathbf{I}_{p\times
p}=\mathbb{E}\left(\mathbf{Z}_{\ell}^{\top}\mathbf{Z}_{\ell}\right),\vspace{1mm}$

where \raisebox{-.8pt}{5}⃝ and \raisebox{-.8pt}{6}⃝ is because of the fact
such that $i$ and $\pi^{\natural}(i)$ are not within the set ${\cal I}_{\ell}$
simultaneously. To sum up, we invoke the matrix Bernstein inequality (Theorem
$7.3.1$ in Tropp (2015)) and have

$\displaystyle\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i\in{\cal
I}_{\ell}}\mathbf{X}_{\pi^{\natural}(i),:}\mathbf{X}_{i,:}^{\top}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{OP}}\leq~{}$
$\displaystyle\frac{p(\log
n)\log(n^{2}p^{3})}{3(n-h)}+\frac{\sqrt{p^{2}(\log^{2}n)\log^{2}\left(n^{2}p^{3}\right)+18ph_{i}\log\left(n^{2}p^{3}\right)}}{n-h}$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{7}⃝}}}}{{\lesssim}}~{}$
$\displaystyle\frac{p(\log n)\log(n^{2}p^{3})}{n}+\
\frac{p}{n}\sqrt{(\log^{2}n)\log^{2}\left(n^{2}p^{3}\right)+\frac{n}{p}(\log
n^{2}p^{3})}$
$\displaystyle\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{8}⃝}}}}{{\lesssim}}~{}$
$\displaystyle\frac{p(\log n)\log(n^{2}p^{3})}{n}+\frac{(\log n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{9}⃝}}}}{{\lesssim}}\frac{(\log
n)(\log n^{2}p^{3})\sqrt{p}}{\sqrt{n}}$

holds with probability $1-2(np)^{-2}$, where in \raisebox{-.8pt}{7}⃝,
\raisebox{-.8pt}{8}⃝, and \raisebox{-.8pt}{9}⃝ we use the fact that $h\lesssim
n$, $h_{i}\leq h$, and $n\gtrsim p$. Hence we can show $\zeta_{1}$ in (53) to
be less than $6n^{-2}p^{-2}$.

Analysis of $\zeta_{2}$. We upper bound $\zeta_{2}$ as

$\displaystyle\zeta_{2}\leq~{}$ $\displaystyle\
\mathbb{P}\left(\frac{1}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i=h+1}^{n}\left(\mathbf{X}_{i,:}\mathbf{X}_{i,:}^{\top}-\mathbf{I}\right)\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\gtrsim\frac{(\log
n)(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\left({\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{i=h+1}^{n}\left(\mathbf{X}_{i,:}\mathbf{X}_{i,:}^{\top}-\mathbf{I}\right)\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{OP}}\gtrsim(\log
n)(\log n^{2}p^{3})\sqrt{np}\right).$

Similar to above, we define
$\widetilde{\mathbf{Z}}_{i}=\mathbf{X}_{i,:}\mathbf{X}_{i,:}^{\top}-\mathbf{I}$.
First, we verify that $\mathbb{E}\widetilde{\mathbf{Z}}_{i}=\bm{0}$ and
$\widetilde{\mathbf{Z}}_{i}$ are independent with each other. Then we bound
${|\kern-1.72218pt|\kern-1.72218pt|\widetilde{\mathbf{Z}}_{i}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}$
as

$\displaystyle{|\kern-1.72218pt|\kern-1.72218pt|\widetilde{\mathbf{Z}}_{i}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}\leq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{X}_{i,:}\mathbf{X}^{\top}_{i,:}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{OP}}+{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{I}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{OP}}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{A}⃝}}}}{{=}}\
{\left\|\mathbf{X}_{i,:}\right\|}_{2}^{2}+1\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{B}⃝}}}}{{\lesssim}}p\log
n+1\lesssim p\log n,\vspace{1mm}$

where in \raisebox{-.8pt}{A}⃝ we use
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bm{u}\bm{u}^{\top}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{OP}}={\left\|\bm{u}\right\|}_{2}^{2}$
for arbitrary vector $\bm{u}$, in \raisebox{-.8pt}{B}⃝ we condition on event
${\cal F}_{4}$. In the end, we compute
$\mathbb{E}(\widetilde{\mathbf{Z}}_{i}\widetilde{\mathbf{Z}}_{i}^{\top})$ as

$\displaystyle\mathbb{E}(\widetilde{\mathbf{Z}}_{i}\widetilde{\mathbf{Z}}_{i}^{\top})=\mathbb{E}\left({\left\|\mathbf{X}_{i,:}\right\|}_{2}^{2}\mathbf{X}_{i,:}\mathbf{X}^{\top}_{i,:}\right)-\mathbf{I}\preceq
p\log
n\cdot\mathbb{E}\left(\mathbf{X}_{i,:}\mathbf{X}^{\top}_{i,:}\right)-\mathbf{I}\preceq(p\log
n)\mathbf{I}.\vspace{1mm}$

Invoking the matrix Bernstein inequality (Theorem $7.3.1$ in Tropp (2015)), we
conclude

$\displaystyle\zeta_{2}\leq 4p\cdot\exp\left(-\frac{3n(\log
n)\log^{2}\left(n^{2}p^{3}\right)}{\sqrt{np}(\log
n)\log\left(n^{2}p^{3}\right)+6}\right)\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{C}⃝}}}}{{\leq}}4n^{-2}p^{-2},\vspace{1mm}$

where in \raisebox{-.8pt}{C}⃝ we use the fact $n\gtrsim p$. Combining it with
(51) and (B.5) then completes the proof. ∎

######  Lemma 17.

Conditional on the intersection of events ${\cal
F}_{1}(\mathbf{B}^{\natural})\bigcap{\cal F}_{2}$, we conclude

$\displaystyle\big{\|}\big{(}\widetilde{\mathbf{B}}-\widetilde{\mathbf{B}}_{\setminus(s)}\big{)}^{\top}\mathbf{X}_{s,:}\big{\|}_{2}\lesssim\frac{p\log^{\nicefrac{{3}}{{2}}}n}{n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}.\vspace{1mm}$

###### Proof.

Here we focus on the case when $\pi^{\natural}(s)=s$. The proof of the case
when $\pi^{\natural}(s)\neq s$ can be completed effortless with a similar
strategy. First, we notice

$\displaystyle\big{\|}\big{(}\widetilde{\mathbf{B}}-\widetilde{\mathbf{B}}_{\setminus(s)}\big{)}^{\top}\mathbf{X}_{s,:}\big{\|}_{2}=~{}$
$\displaystyle\left(n-h\right)^{-1}{\left\|\mathbf{B}^{\natural\top}(\widetilde{\mathbf{X}}_{s,:}\widetilde{\mathbf{X}}^{\top}_{s,:}-\mathbf{X}_{s,:}\mathbf{X}^{\top}_{s,:})\mathbf{X}_{s,:}\right\|}_{2}$
$\displaystyle\leq~{}$
$\displaystyle\left(n-h\right)^{-1}\left(|\langle\mathbf{X}_{s,:},\widetilde{\mathbf{X}}_{s,:}\rangle|\
\|\mathbf{B}^{\natural\top}\widetilde{\mathbf{X}}_{s,:}\|_{2}+{\left\|\mathbf{X}_{s,:}\right\|}_{2}^{2}\cdot\|\mathbf{B}^{\natural\top}\mathbf{X}_{s,:}\|_{2}\right).\vspace{1mm}$

Conditional on the intersection of events ${\cal
F}_{1}(\mathbf{B}^{\natural})\bigcap{\cal F}_{2}$, we conclude

$\displaystyle\big{\|}\big{(}\widetilde{\mathbf{B}}-\widetilde{\mathbf{B}}_{\setminus(s)}\big{)}^{\top}\mathbf{X}_{s,:}\big{\|}_{2}\lesssim\frac{p\log^{\nicefrac{{3}}{{2}}}n}{n-h}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\stackrel{{\scriptstyle}}{{\asymp}}\frac{p\log^{\nicefrac{{3}}{{2}}}n}{n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}.\vspace{1mm}$

∎

Following the same strategy, we can prove that

######  Lemma 18.

Conditional on the intersection of events ${\cal
F}_{1}(\mathbf{B}^{\natural})\bigcap{\cal F}_{2}$, we conclude

$\displaystyle{\left\|(\widetilde{\mathbf{B}}-\widetilde{\mathbf{B}}_{\setminus(s,t)})^{\top}\mathbf{X}_{s,:}\right\|}_{2}\lesssim\frac{p\log^{\nicefrac{{3}}{{2}}}n}{n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}.\vspace{1mm}$

######  Lemma 19.

Conditional on the intersection of events ${\cal F}_{6}\bigcap{\cal F}_{7}$,
we conclude $\mathbb{P}({\cal F}_{8})\geq 1-c_{0}\cdot n^{-c_{1}}$.

###### Proof.

We adopt the leave-one-out trick and construct the matrix
$\widetilde{\mathbf{B}}_{\setminus(s)}$ as

$\displaystyle\widetilde{\mathbf{B}}_{\setminus(s)}=(n-h)^{-1}\bigg{(}\sum_{\begin{subarray}{c}k\neq
s\\\ \pi^{\natural}(k)\neq
s\end{subarray}}\mathbf{X}_{\pi^{\natural}(k),:}\mathbf{X}_{k,:}^{\top}+\sum_{\begin{subarray}{c}k=s\textup{
or}\\\
\pi^{\natural}(k)=s\end{subarray}}\mathbf{X}^{{}^{\prime}}_{\pi^{\natural}(k),:}\mathbf{X}^{{}^{\prime}\top}_{k,:}\bigg{)}\mathbf{B}^{\natural},\vspace{1mm}$

where $\mathbf{X}^{{}^{\prime}}_{s,:}$ are the independent copy of
$\mathbf{X}_{s,:}$. Adopting the union bound, we conclude

$\displaystyle\mathbb{P}\left({\left\|(\widetilde{\mathbf{B}}-\mathbf{B}^{\natural})^{\top}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim\frac{(\log
n)^{\nicefrac{{3}}{{2}}}(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\left({\left\|(\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}_{\setminus(s)})^{\top}\mathbf{X}_{s,:}\right\|}_{2}+{\left\|(\widetilde{\mathbf{B}}_{\setminus(s)}-\widetilde{\mathbf{B}})^{\top}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim\frac{(\log
n)^{\nicefrac{{3}}{{2}}}(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)$
$\displaystyle\leq~{}$
$\displaystyle\underbrace{\mathbb{P}\left({\left\|(\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}_{\setminus(s)})^{\top}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim\frac{(\log
n)^{\nicefrac{{3}}{{2}}}(\log
n^{2}p^{3})\sqrt{p}}{\sqrt{n}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)}_{\triangleq\zeta_{1}}$
$\displaystyle+~{}$
$\displaystyle\underbrace{\mathbb{P}\left({\left\|(\widetilde{\mathbf{B}}_{\setminus(s)}-\widetilde{\mathbf{B}})^{\top}\mathbf{X}_{s,:}\right\|}_{2}\gtrsim\frac{p\log^{\nicefrac{{3}}{{2}}}n}{n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)}_{\triangleq\zeta_{2}}.\vspace{1mm}$

First, we study the probability $\zeta_{1}$. Due to the construction of
$\widetilde{\mathbf{B}}_{\setminus(s)}$, we have $\mathbf{X}_{s,:}$ to be
independent of $\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}_{\setminus(s)}$.
Conditional on $\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}_{\setminus(s)}$,
we conclude

$\displaystyle\zeta_{1}\stackrel{{\scriptstyle\small{\raisebox{0.6pt}{\raisebox{-.8pt}{1}⃝}}}}{{\leq}}\mathbb{P}\left({\left\|(\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}_{\setminus(s)})^{\top}\mathbf{X}_{s,:}\right\|}_{2}\geq\sqrt{\log
n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}_{\setminus(s)}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\right)\leq
n^{-c},\vspace{1mm}$

where in \raisebox{-.8pt}{1}⃝ we condition on event ${\cal F}_{6}$ such that
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}-\widetilde{\mathbf{B}}_{\setminus(s)}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}\lesssim(\log
n)(\log
n^{2}p^{3})\sqrt{\nicefrac{{p}}{{n}}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\mathbf{B}^{\natural}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}_{\textup{F}}$.
As for probability $\zeta_{2}$, we have it to be zero conditional on ${\cal
F}_{7}$. The proof is thus completed. ∎

##  Appendix C Useful Facts

This section lists some useful facts for the sake of self-containing.

######  Lemma 20.

For a $\chi^{2}$-RV $Z$ with $\ell$ freedom, we have

$\displaystyle\mathbb{P}\left(Z\leq
t\right)\leq\exp\left(\frac{\ell}{2}\left(\log\frac{t}{\ell}-\frac{t}{\ell}+1\right)\right),~{}~{}t<\ell;$
$\displaystyle\mathbb{P}\left(Z\geq
t\right)\leq\exp\left(\frac{\ell}{2}\left(\log\frac{t}{\ell}-\frac{t}{\ell}+1\right)\right),~{}~{}t>\ell.$

######  Lemma 21 (Lemma $8$ in Pananjady et al. (2018)).

Consider an arbitrary permutation map $\pi$ with Hamming distance $h$ from the
identity map, i.e., $\mathsf{d_{H}}\left(\mathbf{I},\mathbf{H}\right)=h$. We
define the index set $\left\\{i:~{}i\neq\pi(i)\right\\}$ and can decompose it
into $3$ independent sets ${\cal I}_{\ell}$ $(1\leq\ell\leq 3)$ such that the
cardinality of each set satisfies $|{\cal
I}_{\ell}|\geq\lfloor\nicefrac{{h}}{{3}}\rfloor\geq\nicefrac{{h}}{{5}}$.

######  Lemma 22 (Latala et al. (2007)).

Let $\bm{g}\in\mathbb{R}^{n}$ be a random vector with each entry to be
independent sub-gaussian RV with $\textup{Var}(g_{i})\geq 1$ and sub-gaussian
constants bounded by $K$, and $\mathbf{A}$ is a non-zero $n\times n$ matrix.
For any $\bm{y}\in\mathbb{R}^{n}$ and $\varepsilon\in(0,c_{1})$, one has

$\displaystyle\mathbb{P}\left({\left\|\bm{y}-\mathbf{A}\bm{g}\right\|}_{2}\leq\nicefrac{{1}}{{2}}{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{A}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\right)\leq
2\exp\left(-\frac{c_{0}}{K^{4}}\textup{srank}(\mathbf{A})\right).$

######  Lemma 23 (Theorem $1.3$ in Paouris (2012)).

Let $\bm{g}\in\mathbb{R}^{n}$ be an isotropic log-concave random vector with
sub-gaussian constant $K$, and $\mathbf{A}$ is a non-zero $n\times n$ matrix.
For any $\bm{y}\in\mathbb{R}^{n}$ and $\varepsilon\in(0,c_{1})$, one has

$\displaystyle\mathbb{P}\left({\left\|\bm{y}-\mathbf{A}\bm{g}\right\|}_{2}\leq\varepsilon{|\kern-1.72218pt|\kern-1.72218pt|\mathbf{A}|\kern-1.72218pt|\kern-1.72218pt|}_{\textup{F}}\right)\leq\exp\left(\kappa(K)\textup{srank}(\mathbf{A})\log\varepsilon\right),$

where $\kappa=c_{1}/K^{2}$.