Let us prove the second result by contradiction. Assume that there exists an estimator $\widehat{T}$ and a constant $c_s$ such that

\[
\sup_{\bA: \ \|\bA\|_{\infty}\leq 0.125(pq)^{1/4}}\E\left[\big|\widehat{T}- \|\bA\|_s\big|\right]\leq c_s \frac{q^{1/s}(pq)^{1/4}}{\log^{s}(q)\vee 1}
\]

Without loss of generality, we can also assume that $\widehat{T}\leq 0.125q^{1/s}(pq)^{1/4}$. Then, for any matrix $\bA$ with $\|\bA\|_{\infty}\leq 0.125(pq)^{1/4}$, we have

\[
\E\left[\big|\widehat{T}^{s}- \|\bA\|^{s}_s\big|\right]\leq s  [q^{1/s}(pq)^{1/4}]^{s-1}\E\left[\big|\widehat{T}- \|\bA\|_s\big|\right]\leq
c_s s \frac{q(pq)^{1/4}}{\log^s (q)}\ .
\]

Hence, if $c_s$ is take small enough, this contradicts the first result.

§.§ Proofs for Wasserstein estimation

We start with the key lemma in [21] that allows them to control the Wasserstein distance between the spectral measures.

Consider two probability measures  $\nu_1$ and $\nu_2$ supported on $[-1,1]$. Denote their first $k$ moments
$\alpha =(\alpha_1,\ldots, \alpha_k)$ and $\beta= (\beta_1,\ldots, \beta_k)$, respectively. Then,

\[
W_1(\nu_1,\nu_2)\leq \frac{c}{k}+ c'3^k |\alpha-\beta|_2\ ,
\]

where $c$ and $c'$ are numerical constant.

It turns out that we can extend the above approximation bound by only considering the sequence of even moments.

Consider two probability measures  $\nu_1$ and $\nu_2$ supported on $[0,1]$. Denote their first $k$ even moments
$\alpha =(\alpha_1,\ldots, \alpha_k)$ and $\beta= (\beta_1,\ldots, \beta_k)$, respectively. Then,

\[
W_1(\nu_1,\nu_2)\leq \frac{c}{2k}+ c'3^{2k} |\alpha-\beta|_2\ ,
\]

where $c$ and $c'$ are the same numerical constants as in Lemma <ref>.

We start from  Kantorovich-Rubinstein variational representation of the Wasserstein distance:
$ W_{1}(\nu_1,\nu_2)=\sup_{f: Lip(f)\leq 1}\int f(x) (\nu_1(dx) - \nu_2(dx))$, where $f$ is supported on $[0,1]$ and $Lip(f)\leq 1$ means that $f$ is a Lipschitz function with constant $1$. Let $\cP^{sym}_{k}$ denote the space of the symmetric polynomials of degree less or equal to $k$. As Kong and Valiant [21], we approximate
$\int f(x)(\nu_1(dx) - \nu_2(dx))dx$ by $\int P(x)(\nu_1(dx) - \nu_2(dx))dx$ where $P= \sum_{i=0}^{k} a_k x^{2k} \in \cP^{sym}_{k}$, the twist being that we now consider symmetric polynomials.
∫f(x)(ν_1(dx) - ν_2(dx))dx     =      ∫(f(x)-P(x))(ν_1(dx) - ν_2(dx))dx+ ∫P(x)(ν_1(dx) - ν_2(dx))dx

≤     2f-P_∞+ ∑_i=1^k|a_i||α_i-β_i| .
Coming back to the Wasserstein distance, we have

W_1(ν_1,ν_2)≤sup_f: Lip(f)≤1 inf_P∈^sym_k 2f-P_∞ + ∑_i=1^k|a_i||α_i-β_i| .
Fix any such Lipschitz function $f$ defined in $[0,1]$ and consider the symmetric function $\overline{f}$ on $[-1,1]$, such that $\overline{f}(x)=f(|x|)$. In the proof of Proposition 1 in [21], Kong and Valiant show that there exists a polynomial $Q_{2k}(x)= \sum_{i=0}^{2k} c_i x^{i}$
such that $\|Q-\overline{f}\|_{\infty}\leq c/(2k)$ ($c$ is the same universal contant as in Lemma <ref>) and $(\sum_{i=1}^k c_i^2)^{1/2}\leq 3^{2k}/2$. Since $\overline{f}$ is symmetric, the symmetric  polynomial $Q^{sym}= \sum_{i=0}^{k}c_{2i}x^{2i}$ satisfies
Q^sym_2k-f_∞   =     sup_x∈[-1,1]| Q_2k(x)+ Q_2k(-x)/2-f(x)|= sup_x∈[-1,1]| Q_2k(x)+ Q_2k(-x)-f(x)-f(-x)/2|

≤    Q- f_∞≤c/2k .
In particular, this implies that $\|Q- f\|_{\infty}\leq c/(2k)$. Coming back to (<ref>), we have proved that

\[
W_{1}(\nu_1,\nu_2)\leq \frac{c}{2k}+  \frac{3^{2k}}{2}|\alpha-\beta|_2 \enspace .
\]

The proof closely follows that of Theorem 2 in Kong and Valiant [21].  Define $\overline{m}$ the vector of size $K$ of even moments such that $\overline{m}_k= \frac{1}{q}\big[\frac{\|\bA\|_{2k}}{M(pq)^{1/4}}\big]^{2k}$, for $k=1,\ldots, K$. Since we assume that $\sigma_1(\bA)\leq M(pq)^{1/4}$, it follows from Proposition <ref> and Theorem <ref> that

\[
\E\left[|\overline{m}- \widehat{m}|_1\right] \leq \frac{1}{q} \sum_{k=1}^K c^{k}\left[\frac{1}{M^2}+ \left(\frac{q}{p}\right)^{1/4}\frac{1}{M}\right]\leq \frac{c^{K}}{q[M^2\wedge [(p/q)^{1/4}M]]}\ .
\]

Consider a rounding $\mu_0$ of the true measure $\mu_{\sigma(\bA)/[M(pq)^{1/4}]}$ that is supported on the grid. By definition, the $2k$-th moments of $\mu_0$ is at most $[1- (1-\zeta)^2k]$ far from that of $\mu_{\sigma(\bA)/[M(pq)^{1/4}]}$. As a consequence, this distribution $\mu_0$ is a feasible point of the linear program and its objective value is less or equal to $|\overline{m}-\widehat{m}|_1+ 2\zeta \sum_{k=1}^{K} k$.
As a consequence, the even moments vector $m^+$ of the  solution $p^+$ of the linear program satisfies in expectation
[|m^+-m |_2]   ≤   [|m^+-m|_1]+ [m- m|_1]

≤    c^K/q1/M^2∧[(p/q)^1/4M]+c ζK^2

≤    2c^K/q1/M^2∧[(p/q)^1/4M] ,
since $\zeta\leq 1/(M^2q)$. Denote $\mu^+$ the measure associated to the vector $p^+$ and  $\mu^+_{disc}$ the discrete distribution made of  $q$ Dirac which is derived from $p^+$ after step $2$ of the procedure. By triangular inequality, we have
$W(\mu^+_{disc}, \mu_{\sigma(\bA)})\leq W(\mu^+, \mu_{\sigma(\bA)})+ W(\mu^+_{disc}, \mu^+)$. Since $W(\mu^+_{disc}, \mu^+)\leq 1/q$, we deduce from Lemma <ref> that

\[
\E[W(\mu^+_{disc}, \mu_{\sigma(\bA)})] \leq  \frac{c}{K}+\frac{1}{q}+  \frac{c'^{K}}{q}\frac{1}{M^2\wedge [(p/q)^{1/4}M]} \ .
\]

From (<ref>), we conclude that

\[
\sum_{i=1}^q |\widehat{\sigma}_i-\sigma_i(\bA)|\leq qM(pq)^{1/4} \left[ \frac{c}{K}+\frac{1}{q}+  \frac{c'^{K}}{q}\frac{1}{M^2\wedge [(p/q)^{1/4}M]} \right]\ .
\]

Plugging the value $K = \lfloor c_1\log(q)\rfloor $ where $c_1$ is chosen small enough so that $c'^{K}\leq \sqrt{q}$ yields the desired result.

§.§ Proof of Propositions <ref> and <ref>

Recall that $\tr[\bY^T \bY- p\bI_q]= \|\bA\|_2^2+2 \tr[\bA^T \bE]+ (\tr[\bE^T\bE]-pq)$. The second expression follows a centered normal distribution with variance $4\|\bA\|_2^2$ whereas the last expression follows a $\chi^2$ distribution with $pq$ degrees of freedom.
From Lemma <ref>, we deduce that, with probability higher than $1-4e^{-t}$,

\[
\big|\tr[\bY^T \bY- p\bI_q]- \|\bA\|_2^2 \big| \leq 2\sqrt{pqt}+ 2t + 2\|\bA\|_2\sqrt{2t}\ .
\]

Regarding the operator norm, we start from (<ref>)

\[
\big|\sigma_1(\bY^T \bY -p \bI_q) - \|\bA^T\bA\|_{\infty}\big| \leq 2\|\bA^T\bE\|_{\infty}+ \|\bE^T\bE - p\bI_q\|_{\infty}\ .
\]

From Lemma <ref>, we deduce that, with probability higher than $1-e^{-t}$,  $\|\bE^T\bE - p\bI_q\|_{\infty}\leq q+ 2\sqrt{pq}+ 4\sqrt{2pt}+ 2t$. In the proof of Lemma <ref>, we have shown that $ \|\bA^T\bE\|_{\infty}/\|\bA\|_{\infty}$ is stochastically dominated by the operator norm of a $q\times q$ matrix with independent normal entries. Invoking again Lemma <ref>, we derive that $2\|\bA^T\bE\|_{\infty}\leq 2\sigma_1(\bA)(2\sqrt{q}+\sqrt{2t})$ with probability higher than $1-e^{-t}$. Putting everything together, this yields

\[
\frac{1 - [2\sqrt{pqt}+2t]/\|\bA\|_2^2- 2\sqrt{2t}/\|\bA\|_2 }{1 +2\frac{2\sqrt{q}+\sqrt{2t}}{\sigma_1(\bA)}+ \frac{3\sqrt{pq}+ 4\sqrt{2pt}+ 2t}{\sigma^2_1(\bA)} } \leq  \frac{\sigma^2_1(\bA)}{\|\bA\|_2^2}\widehat{\mathrm{ER}}_{2,\infty}(\bA)\leq
\frac{1 + [2\sqrt{pqt}+2t]/\|\bA\|_2^2+ 2\sqrt{2t}/\|\bA\|_2 }{1 -2\frac{2\sqrt{q}+\sqrt{2t}}{\sigma_1(\bA)}- \frac{3\sqrt{pq}+ 4\sqrt{2pt}+ 2t}{\sigma^2_1(\bA)} }\ ,
\]

which, assuming that both $\|\bA\|_2$  and  $\|\bA\|_{\infty}$ are  large enough, implies that

\[
\frac{\big|\widehat{\mathrm{ER}}_{2,\infty}(\bA)  - \mathrm{ER}_{2,\infty}(\bA)\big|}{\mathrm{ER}_{2,\infty}(\bA)}\lesssim  \frac{\sqrt{pqt}}{\|\bA\|_2^2}+ \frac{\sqrt{pt}+ \sqrt{pq}}{\|\bA\|^2_{\infty}}+ \frac{\sqrt{q}+\sqrt{t}}{\|\bA\|_{\infty}}\enspace .
\]

The first bound is a straightforward consequence of (<ref>), so we focus on the minimax lower bound.
Consider any $r\geq (pq)^{1/4}$. We shall first prove that

inf_Rsup_: σ_1()≥r [|R -ER_2,∞()|/ER_2,∞()≥c √(pq)/r^2 ] ≥0.2 .
Define the  matrices $\bE_{i,j}$  by $(\bE_{ij})_{kl}=\1_{i=k}\1_{j=l}$. Fix $s \in (0, (pq)^{1/4})$.    We consider the matrix $\bA_0= r \bE_{11}$  and
the class $\mathcal{C}_{s}$ of matrices of the form $\bA= \bA_0 + s \bB$, where $\bB$ is a rank-one matrix whose only non-zero singular is equal to one and whose  first row and first column are zero. Obviously, the effective rank of $\bA_0$ is $1$, whereas that of $\bA$ in $\mathcal{C}_{s}$ is $1+ s^2/r^2$. This allows us to reducing the problem of estimating the effective rank to that of testing whether $\bA=\bA_0$ versus $\bA\in \mathcal{C}_{s}$.
inf_Rsup_: σ_1()≥r [|R -ER_2,∞()|/ER_2,∞()≥s^2/4r^2]    ≥    inf_T∈{0,1}[max(__0[T=1], max_∈𝒞_s_[T=0])] .
Since the first row and the first column of $\bY$ are uninformative for this test, this reduces to the problem of testing whether a $(p-1)\times (q-1)$ matrix $\bA$ is null versus $\bA$ is a rank-one matrix with non-zero singular value $s$. We rely again on Le Cam's method of fuzzy hypotheses [37]. Considering again the same mixture distribution $\mu$ as in the proof of Proposition <ref>, we deduce that
inf_Rsup_: σ_1()≥r [|R -ER_2,∞()|/ER_2,∞()≥s^2/4r^2]    ≥    1- √(χ^2(ℙ_0, 𝐏))/2.
By Lemma <ref>, the latter expression is larger than $0.2$ if we take $s= [0.25(p-1)(q-1)]^{1/4}$. We proved (<ref>).

Let us now prove that

inf_Rsup_: σ_1()≥r [|R -ER_2,∞()|/ER_2,∞()≥c √(q)/r ] ≥0.2 .
Without loss of generality, we restrict ourselves to square matrices of dimension $q$. Introduce $\bA_1= r \bI_q$ and, for $s>0$, $\mathcal{C}'_s$ the collection of matrices of the form $\bA= \bA_1 + s uu^T$ where $u$ is a unit vector. The effective rank of $\bA_1$ is $q$, whereas that of matrices $\bA$ in $\mathcal{S}'$ equals $q - (q-1)\frac{s^2 + 2sr}{(r+ s)^2}$. As long as $r\geq 2s$ and $q\geq 2$, the relative difference between these effective ranks is at least $\tfrac{4s}{9r}$. Arguing as above, we deduce that
inf_Rsup_: σ_1()≥r [|R -ER_2,∞()|/ER_2,∞()≥2s/9r]    ≥    inf_T∈{0,1}[max(__1[T=0], max_∈𝒞'_s_[T=0])] ,
the latter quantity being equivalent to the optimal error of the test of the hypotheses “$\bA=0$” versus “$\bA= s uu^T$ for some unit vector $u$”.
Introduce the uniform distribution $\nu$ on the hypercube $\{-1,1\}^q$ and define $\mu$ the corresponding distribution of $\bA= s/q v v^T$ when $v$ is sampled according to $\nu$. Writing $\mathbf{P}'$ the marginal distribution of $Y$ when $\bA$ is sampled according to $\mu$, we deduce that
inf_Rsup_: σ_1()≥r [|R -ER_2,∞()|/ER_2,∞()≥2s/9r]    ≥    1- √(χ^2(ℙ_0, 𝐏'))/2.
We claim that, for $s=\sqrt{q/16}$, we we have $\chi^2(\mathbb{P}_0, \mathbf{P}')\leq 1/3$. Before showing this claim, let us finish this proof. Since $r\geq (pq)^{1/4}\geq \sqrt{q}$, we have $r\geq 2s$ and (<ref>) follows from the previous inequality.

It remains to prove the claim. Recall that $\chi^2(\mathbb{P}_0, \mathbf{P}')=\E_{0}[L^2]-1$, where $L$ is the likelihood ratio.
Arguing as in the beginning of the proof of Lemma <ref>, we deduce that

\[
\E_0[L^2]= \E\left[\exp\left(\frac{s^2Z^2}{q^2}\right)\right]= \E\left[\exp\left(\frac{Z^2}{16q}\right)\right]\ ,
\]

where $Z$ is distributed as a sum of $q$ independent Rademacher random variables. By Hoeffding's inequality $\P[|Z|\geq u]\leq 2e^{-u^2/(2q)}$. Hence,

\[
\E_0[L^2]-1\leq \int_{1}^{\infty}\P\left[\exp\left(\frac{Z^2}{16q}\right)\geq t\right]dt\leq 2\int_{1}^{\infty}\frac{1}{t^8}dt= \frac{2}{9}\leq \frac{1}{3} \ .
\]

The result follows.

§ PROOFS FOR SUB-GAUSSIAN NOISE

§.§ Proof of Theorem <ref>

Recall that our estimator $U_k$ is defined as

\[
U_k = \sum_{i=i_1,\ldots, i_k}\sum_{j=j_1,\ldots, j_k}\prod_{r,s}H_{N_{rs}(ij)}(\bY_{rs})\enspace ,
\]

so that its square risk satisfies

[(U_k - _2k^2k)^2]= ∑_i,j,i'j'= T_iji'j'[(∏_r,sH_N_rs(ij)(_rs)-  ∏_rs_rs^N_rs(ij))(∏_r,sH_N_rs(i'j')(_rs)-  ∏_rs_rs^N_rs(i'j'))]  .
The random variables $Y_{rs}$ are independent. Besides, we have  $\E[H_1(Y_{rs})]= \bA_{rs}$  and $\E[H_2(Y_{rs})]= \bA_{rs}^2$ since  $\var{E_{rs}}=1$. As a consequence, $T_{iji'j'}$ is equal to zero if

\[
\max_{rs}N_{rs}(ij) N_{rs}(i'j')=0\quad  \text{ and }\quad  [\max_{rs}N_{rs}(ij)]\wedge [\max_{rs}N_{rs}(i'j')]\leq 2\enspace .
\]

Indeed, the first condition ensures that $T_{iji'j'}$ is the expectation of a product of two independent random variables $Z_1$ and $Z_2$ whereas the second condition ensures that either $\E[Z_1]=0$ or $\E[Z_2]=0$ so that $T_{iji'j'}=0$. In order to work out the expression of the non-zero $T_{iji'j'}$, we shall rely on the following lemma which control that expectation of $H_{k}(Y)$ and of the products $H_{k}(Y)H_{l}(Y)$ when $Y$ is not normally distributed.

Let $Y=\theta + E$ where $E$ is a mean-zero random variable satisfying $\var{E}=1$. There exists a universal constant $c>0$, such that the following holds. For any integer $k\geq 3$, we have

\[
\E[H_k(Y)]= \theta^k+ P_{k}(\theta) \ ,
\]

where $P_{k}$ is a polynomial of degree at most $k-3$ and whose coefficients are, in absolute value, uniformly bounded by $(c\|E\|_{\psi_2})^k k^{k+1}$.
Let $k$ and $l$ be two non-negative integers satisfying  $k+l \geq 2$. Then,

\[
\E[H_kH_l(Y)]= \theta^{k+l}+ Q_{k,l}(\theta)
\]

where the degree of $Q_{k,l}$ is at most $k+l-2$ and whose coefficients are, in absolute value, uniformly bounded by $(c\|E\|_{\psi_2})^{k+l} (k+l)^{k+l+2}$.  Besides, if $k+l=2= k\vee l$, then  $Q_{k,l}=0$.

Given a partition $\cP=\{\cP_1,\ldots, \cP_l\}$ of $[4k]$ with $l$ groups, we consider the function  $F_{\cP}$ defined by

\begin{eqnarray}
F_{\cP}[x_1,\ldots, x_l]&=& \prod_{r=1}^{l} \mathbb{E}\left[H_{|\cP_r\cap [2k]|}(y_r)H_{|\cP_r\cap [2k+1:4k]|}(y_r)\right] - \prod_{r=1}^{l} x_r^{|\cP_r\cap [2k]|}\E\left[H_{|\cP_r\cap [2k+1:4k]|}(y_r)\right]\nonumber \\  & &- \prod_{r=1}^{l} x_r^{|\cP_r\cap [2k+1:4k]|}\E\left[H_{|\cP_r\cap [2k]|}(y_r)\right]+  \prod_{r=1}^{l} x_r^{|\cP_r|}\ , \nonumber
\end{eqnarray}

where, for $r=1,\ldots, l$,  $y_r=x_r+ \epsilon_r$ and the $\epsilon_r$'s are independent and identically distributed.
By Lemma <ref> above, $F_{\cP}$ is a polynomial of $l$ variables.

\begin{eqnarray}\nonumber
F_{\cP}[x_1,\ldots, x_l]&=& \prod_{r:\ |\cP_r|=1} x_r \left[\prod_{r:\ |\cP_r|\geq 2}  x_r^{|\cP_r|} + \prod_{r:\ |\cP_r|\geq 2} \left[ x_r^{|\cP_r|} + Q_{|\cP_r\cap [2k]|,|\cP_r\cap [2k+1:4k]|}(x_k)\right]  \right.\\
&&  \quad \quad - \prod_{r:\ |\cP_r|\geq 2}\left[  x_r^{|\cP_r|}+ x_r^{|\cP_r\cap [2k]|}P_{|\cP_r\cap [2k+1:4k]|}(x_r) \right] \nonumber \\ & &  \quad \quad  \left. -   \prod_{r:\ |\cP_r|\geq 2}\left[  x_r^{|\cP_r|}+ x_r^{|\cP_r\cap [2k+1:4k]|}P_{|\cP_r\cap [2k]|}(x_r) \right]  \right]\ .\label{eq:definition_F_P}
\end{eqnarray}

Given $m=(i,j,i',j')$, we define the following sequence $\underline{m}$  of $2$-tuples of size $4k$

\begin{eqnarray}\label{eq:definition_u_m}
\underline{m}&= &((i_1,j_1), (i_1,j_2),\ldots, (i_{k},j_1), (i'_1,j'_1),\ldots, (i'_k,j'_1)) \ .
\end{eqnarray}

Then, we define $\cP[m]$ as the partition of $[4k]$ that groups identical 2-tuples in $\underline{m}$.
Besides, we consider the two sequences $\underline{m}^{ev}$ and $\underline{m}^{od}$ defined by

\begin{eqnarray}\label{eq:definition_u_m_ev}
\underline{m}^{ev}= (i_1,i_1,i_2,i_2,\ldots, i_k,i_k, i'_1,i'_1,\ldots,i'_k,i'_k)\ ;\,\,\,
\underline{m}^{od}= (j_1,j_2,j_2,\ldots, j_k,j_1, j'_1,j'_2,\ldots,j'_k,j'_1)\ .\nonumber
\end{eqnarray}

Given a partition $\cP$ of $[4k]$ into $l$ groups, we pick representatives $s_1, \ldots, s_l$ for each group. Then,
for all $m$ satisfying $\cP[m]=\cP$, we have

\[
T_m= F_{\cP}[\bA_{\underline{m}_{s_1}}, \ldots, \bA_{\underline{m}_{s_l}}]\ .
\]

For short, we write henceforth $F_{\cP}[m]$ for $F_{\cP}[\bA_{\underline{m}_{s_1}}, \ldots, \bA_{\underline{m}_{s_l}}]$.
Write $\boldsymbol{\cP}_k$ for the collection of all  partitions $\cP$ of $[4k]$. Equipped with this notation, we group the expressions $T_m$ according to their partition $\cP[m]$.

\begin{equation}\label{eq:upper_0_risk_GP}
\E\left[\left(U_k - \|\bA\|_{2k}^{2k}\right)^2\right]= \sum_{\cP\in \boldsymbol{\cP}_k} \quad\sum_{m: \ \cP[m]=\cP }F_{\cP}(m)\ .
\end{equation}

Unfortunately, it is not simple to enumerate the sequences such that $\cP[m]=\cP$ and these sums $\sum_{m: \ \cP[m]=\cP }F_{\cP}(m)$ do not simplify much. For this reason, we prefer to reformulate the expressions using sums over sequences $m$ such that $\cP[m]$ is coarser than $\cP$
For two partitions $\cP'$ and $\cP$, we write $ \cP' \trianglelefteq \cP$ if $\cP'$ is finer or equal to $\cP$. First, we extend the definition of $F_{\cP}(m)$ to any sequence $m$ whose partition $\cP[m]$ is coarser than $\cP$, that is $\cP\trianglelefteq \cP[m]$. Then, we  define a new functional $G_{\cP}$ for $\cP\in \boldsymbol{\cP}_k$ by recursion.
If $\cP$ is the finest partition (with $4k$ groups), we fix $G_{\cP}=F_{\cP}=0$. Otherwise, we define

\[
G_{\cP}(m) = F_{\cP}(m)- \sum_{\cP'\in \boldsymbol{\cP}_k: \ \cP'\triangleleft \cP}G_{\cP'}(m)\ ,
\]

where $F_{\cP}(m)$ is defined in (<ref>).
One then easily deduce from this definition that

[(U_k - _2k^2k)^2]= ∑_∈_kW_   where   W_=∑_m:  ⊴[m]G_(m) .
In the remainder of the proof, we shall carefully control $W_{\cP}$. To do this, we need to evaluate the functional $G_{\cP}$, which is done using
Möbius inversion formula for posets (see the proof of the next lemma). Equipped with this formula, we first establish some structural properties of $G_{\cP}$.

$G_{\cP}$ can be represented as a polynomial in $|\cP|$ variables that satisfies the two following properties:

(a) if $\cP$ contains at least one group, say $\cP_1$, of size $2$ such that either $\cP_1\subset [2k]$ or $\cP_1\subset [2k+1:4k]$, then $G_{\cP}=0$.

(b) For any $l=1,\ldots, |\cP|$ such that $|\cP_l|\geq 2$, the degree of $\cP$ in $x_l$ is at most $|\cP_l|-3$ if $\cP_l\subset[2k]$ or  $\cP_l\subset[2k+1:4k]$  and at most $|\cP_l|-2$ otherwise.

Writing  $\kappa$ the number of groups of $\cP$ of size higher than one, we order the groups of the partition $\cP$ in such a way that the $\kappa$ first groups are of size at least $2$.
We define
the collection $\mathrm{deg}(\cP)$ of non-negative integer-valued vectors $D$ of size $\kappa$ satisfying the two following properties  for all $1\leq r\leq \kappa$,

(a) $D_r\leq |\cP_r|-2$ if $|\cP_r|\geq 2$ ;

(b) $D_r\leq |\cP_r|-3$ if $|\cP_r|\geq 3$ and $\cP_r\subset [2k]$ or  $\cP_r\subset  [2k+1:4k]$ .

Define the monomial,  $G_{\cP,D}[x_1,\ldots, x_{|\cP|}]= \prod_{l=\kappa+1}^{|\cP|}x_l \prod_{l=1}^{\kappa}x_l^{D_l}$ for any $D\in \mathrm{deg}(\cP)$. By Lemma <ref>, we deduce that there exists a collection of numbers $\alpha_{D,\cP}$ for $D\in \mathrm{deg}(\cP)$ such that

\[
G_{\cP}[x_1,\ldots, x_{|\cP|}]= \sum_{D\in \mathrm{deg}(\cP)}\alpha_{D,\cP} G_{\cP,D}[x_1,\ldots, x_{|\cP|}] \ .
\]

The next lemma provides an uniform bound for the coefficients $\alpha_{D,\cP}$. It is based on Möbius inversion formula (as the previous lemma) together with Lemma <ref>.

For any partition $\cP$, we have

\[
\sum_{D\in \mathrm{deg}(\cP)}|\alpha_{D,\cP} |\leq (c'\|E\|_{\psi_2})^{4k}k^{12k+2}
\]

where $c'$ is a numerical constant.

Now define the associated sums

W_,D=  ∑_m:  ⊴[m]  G_,D[(_m_s_1,…, _m_s_l )]   ,
where we recall that $(s_1,\ldots, s_l)$ are representatives of the partition $\cP$.
In light of the last lemma, we deduce from (<ref>)

\begin{eqnarray}
\E\left[\left(U_k - \|\bA\|_{2k}^{2k}\right)^2\right]&\leq &  \sum_{\cP}\sum_{D\in \mathrm{Deg}(\cP)}|\alpha_{D,\cP}||W_{\cP,D}| \nonumber \\
&\leq & (c''\|E\|_{\psi_2})^{4k}k^{16k+2}  \max_{\cP,\ D}|W_{\cP,D}|  \enspace . \label{eq:upper_max}
\end{eqnarray}

Hence, it remains to upper bound $W_{\cP,D}$ defined in (<ref>) to conclude.

Consider any partition $\cP$ and any $D\in \mathrm{deg}(P)$ such that $W_{\cP,D}\neq 0$. In particular,  $\cP$ contains a least a group of size larger than one and $\cP$ does not contain any group of size $2$ which is either included in $[2k]$ or in $[2k+1,4k]$ –see Lemma <ref>.

Define  $\cP_{ev}$  as the finest partition of $[4k]$ that is coarser than $\cP$ and coarser than $\{\{1,2\},\{3,4\}, \ldots, \{4k-1,4k\}\}$.
Similarly, we define  $\cP_{od}$ the as the finest partition of $[4k]$ that is coarser than $\cP$ and coarser than $\{\{2k,1\},\{2,3\}, \ldots, \{2k-2,2k-1\}, \{4k,2k+1\},\{2k+2,2k+1\},\ldots,  \{4k-2,4k-1\}\}$. Denote $l_1$ the number of groups of $\cP_{ev}$ and $l_2$ the number of groups of $\cP_{od}$. Equipped with this notation, we deduce that there are $p^{l_1}q^{l_2}$ sequences $m=(i,j,i',j')$ satisfying $\cP \trianglelefteq \cP[m]$.

We denote $\cP_{\geq 2}$ the subcollection of $\cP$ made of groups of size at least $2$. By definition of $\kappa$ above, we have $\kappa=|\cP_{\geq 2}|$.
Finally, we define $\cP_{\geq 2,ev}\subset \cP_{ev}$ the subcollection of $\cP_{ev}$ made of groups that intersect at least one group of $\cP_{\geq 2}$. We denote $\kappa_1\leq \kappa$ the number of groups of $\cP_{\geq 2,ev}$. Analogously, we define $\cP_{\geq 2,od}$ and we denote $\kappa_2\leq \kappa$ the corresponding number of groups. In order to evaluate $W_{\cP,D}$, we first fix the values of $\underline{m}_{ev}$, $\underline{m}_{od}$ on $\cP_{\geq 2,ev}$ and $\cP_{\geq 2,od}$ respectively –recall the definitions of $\underline{m}_{ev}$ and $\underline{m}_{od}$ in (<ref>).
Consider any  $s=(s_1,\ldots, s_{\kappa_1})\in [p]^{\kappa_1}$ and $t=(t_1,\ldots, t_{\kappa_2})\in [q]^{\kappa_2}$, where $s_r$ (resp. $t_r$) corresponds to the value of $(i_{ev},i'_{ev})$ (resp. $(j_{od},j'_{od})$) in the $r$-th group of $\cP_{\geq 2,ev}$ (resp. $\cP_{\geq 2,od})$.  Besides denote $\lambda_1$ (resp. $\lambda_2$) the number of groups of $\cP_{1,ev}=\cP_{ev}\setminus \cP_{\geq 2,ev}$ (resp. $\cP_{1,od}=\cP_{od}\setminus \cP_{\geq 2,od}$).

By Definition (<ref>) of $W_{\cP; D}$, there exist sequences $(h_r)_{r=1,\ldots,\kappa}$ in $[\kappa_1]^{\kappa}$ and  $(h'_r)_{r=1,\ldots,\kappa}$ in $[\kappa_2]^{\kappa}$,  $(h_r)_{r=\kappa+1,\ldots,l}$ in $[\kappa_1+\lambda_1]^{l-\kappa}$  and $(h'_{r})_{r=\kappa+ 1,\ldots, \lambda}$ in $[\kappa_2+\lambda_2]^{l-\kappa}$ such that

W_; D= ∑_s_1,…, s_κ_1=1^p ∑_t_1,…, t_κ_2=1^q[∏_r=1^κ _s_h_r,t_h'_r^D_r] ∑_s_κ_1+1, …, s_κ_1+λ_1=1^p   ∑_t_κ_2+1, …, t_κ_2+λ_2=1^q  ∏_r=κ+1^l  _s_h_r,t_h'_r .
Besides, the sequence $(h_r)_{r=\kappa+1,\ldots,l}$ contains exactly twice the value $u$ for all $u\in  [\kappa_1+1, \kappa_1+\lambda_1]$. Similarly, the sequence  $(h'_r)_{r=\kappa+1,\ldots,l}$ contains exactly twice the value $u$ for all $u \in [\kappa_2+1, \kappa_2+\lambda_2]$. The sequence $(h_r)_{r=1,\ldots, \kappa}$ contains at least once each value in $[\kappa_1]$  and the sequence $(h'_r)_{r=1,\ldots, \kappa}$ contains at least once each value in $[\kappa_2]$. Since the indices $s_{\kappa_1+1},\ldots,s_{\kappa_1+\lambda_1}$ and $t_{\kappa_2+1}, \ldots, t_{\kappa_2+\lambda_2}$ occur exactly twice in the sum (<ref>), we can express the corresponding sums in (<ref>) as products of matrices $\bA$ and $\bA^T$. This leads us to the following expression for $W_{\cP; D}$ (the proof is omitted).

There exists a positive integer $z_{\cP}$ only depending on the partition $\cP$ such that

W_; D =  ∑_s_1,…, s_κ_1=1^p ∑_t_1,…, t_κ_2=1^q[∏_r=1^κ _s_h_r,t_h'_r^D_r]∏_r=1^z_ ^(r)_f_r,f'_r
where $\bB^{(r)}=\bA^{\omega_r}(\bA^{T}\bA)^{\omega'_r}(\bA^{T})^{\omega''_r}$ with $\omega_r$ and $\omega''_r$ in $\{0,1\}$ and $\omega'_r$ is a non-negative integer. If $\omega_r= 1$, we have $f_r= s_{v_r}$ for some $1\leq v_r\leq \kappa_1$, otherwise we have $f_r= t_{v_r}$ for some $1\leq v_r\leq \kappa_2$. If $\omega''_r= 1$, we have $h'_r= s_{v'_r}$ for some $1\leq v'_r\leq l$, otherwise we have $h_r= t_{v'_r}$ for some $1\leq v_r\leq l'$.

Now that we have expressed $W_{\cP; D}$ as a sum indexed by the group in $\cP_{\geq 2,ev}$ and $\cP_{\geq 2,od}$ in (<ref>), we cannot simply express $W_{\cP; D}$ as the trace of a matrix or even the product matrix traces. Indeed, the indices $s_{i}$ or $t_{j}$ may occur more than two times in (<ref>). The next bound is the crux of the proof.

Upon denoting $a = \sum_{r=1}^{\kappa}(|\cP_r|-D_r)$, we have

\[
\big|W_{\cP; D}\big|\leq\left\{
\begin{array}{cc}
\|\bA\|_{\infty}^{4k-a} p^{\lfloor a/4\rfloor}q^{\lceil a/4\rceil} & \text{ if $a$ is even}\\
\|\bA\|_{\infty}^{4k-a} p^{ (a-1)/4}q^{(a-1)/4} & \text{ if $a$ is odd}
\end{array}
\right.
\]

We first show how to conclude the proof from this bound before establishing Proposition <ref>.
Recall that $a = \sum_{r=1}^{\kappa}(|\cP_r|-D_r)$ lies in $[2,4k]$. If $a\equiv 3[4]$, then Young's inequality yields

\begin{eqnarray*}
\|\bA\|_{\infty}^{4k-a} p^{(a-1)/4}q^{(a-1)/4}&\leq& \frac{1}{2}\|\bA\|_{\infty}^{4k-a-1}p^{ (a-3)/4}q^{ (a-3)/4}\left[\|\bA\|_{\infty}^{2} +  qp  \right]\\
&\leq & \frac{1}{2}\|\bA\|_{\infty}^{4k-a-1}p^{\lfloor (a+1)/4\rfloor}q^{\lceil (a+1)/4\rceil}+ \frac{1}{2}\|\bA\|_{\infty}^{4k-a+1}p^{\lfloor (a-1)/4\rfloor}q^{\lceil (a-1)/4\rceil} \ .
\end{eqnarray*}

If $a\equiv 1[4]$, then Young's inequality yields

\begin{eqnarray*}
\|\bA\|_{\infty}^{4k-a} p^{(a-1)/4}q^{(a-1)/4}&\leq& \frac{1}{2}\|\bA\|_{\infty}^{4k-a-1}p^{ (a-1)/4}q^{ (a-1)/4}\left[\|\bA\|_{\infty}^{2} +  1 \right]\\
&\leq & \frac{1}{2}\|\bA\|_{\infty}^{4k-a-1}p^{\lfloor (a+1)/4\rfloor}q^{\lceil (a+1)/4\rceil}+ \frac{1}{2}\|\bA\|_{\infty}^{4k-a+1}p^{\lfloor (a-1)/4\rfloor}q^{\lceil (a-1)/4\rceil} \ .
\end{eqnarray*}

This allows us to derive

\[
\big| W_{\cP; D}|\leq \max_{s= 1}^{2k}  \|\bA\|_{\infty}^{4k-2s}p^{\lfloor s/2\rfloor}q^{\lceil s/2\rceil}\leq \max\left[\|\bA\|_{\infty}^{4k-2}q,\|\bA\|_{\infty}^{4k-4}pq,(pq)^{k} \right]
\]

Then, together with (<ref>), we conclude that

\[
\E\left[\left(U_k - \|\bA\|_{2k}^{2k}\right)^2\right]\leq  (c''\|E\|_{\psi_2})^{4k}k^{16k+2} \max\left[\|\bA\|_{\infty}^{4k-2}q,\|\bA\|_{\infty}^{4k-4}pq,(pq)^{k} \right]\ .
\]

The result follows.

§.§ Proof of Proposition <ref>

First, we factorize the expression  the operator norm of $\bA$ in order to consider matrices with operator norm at most one.

W_; D= _∞^4k-∑_r=1^κ(|_r|-D_r)∑_s_1,…, s_κ_1=1^p ∑_t_1,…, t_κ_2=1^q∏_r=1^κ _s_h_r,t_h'_r^D_r ∑_r=1^z_ ^(r)_f_r,f'_r,
where $\overline{\bA}= \bA/\|\bA\|_{\infty}$ and $\overline{\bB}^{(r)}= \bB^{(r)}/ \|\bA\|_{\infty}^{\omega_r+\omega'_r+\omega''_r}$. In order to bound the latter expression, we shall introduce a multigraph $G$ and bound $W_{\cP,D}$ relying on the topology of $G$.

Before explaining how we translate $(\cP,d)$ into a multigraph, we introduce some notation for a multigraph $G=(V,E)$. Since there are possibly multiple edges between the same two vertices, the edges $e\in E$ are defined as a $3$-tuple $(i,j,a)$ where $i$ and $j$ are two  vertices and $a$ is a positive integer corresponding to the index of $e$ among all the edges between $i$ and $j$. Besides, we respectively denote $e_1=i$ and $e_2=j$ the vertices incident to $e$. Although the edges are directed, we shall most often ignore their direction and the degree of vertex $i$ henceforth corresponds to the number of edges that are incident to $i$. Finally, each vertex of $G$ is either labelled as type '$r$' (for row) or as type '$c$' (for column). We write $R\subset V$ for the collection of vertices of type '$r$' and $C=V\setminus R$ for collection of vertices of type '$c$'.  We write  $E_{\mathrm{lo}}\subset E$ for the collection of self-loops, that is edges satisfying $e_1=e_2$ and $E_0= E\setminus E_{\mathrm{lo}}$ for the collection of remaining edges.
In the sequel, the external degree $d_i$ of a vertex $i\in V$ is the number of edges $e\in E_0$ that are incident to $i$. We also $d_{i,\mathrm{lo}}$ for the number of self-loops of $i$.

A matrix $\bC$ is said to satisfy Condition $(\cB_0)$ if its operator norm is at most one and if its rank is at most $q$. A real vector $b$ is said to satisfy Condition $(\cB_{\mathrm{lo}})$ if $|b|_{\infty}\leq 1$ and $|b|_1\leq q$. Finally, a real vector $b$ is said to satisfy the slightly weaker condition  $(\cB^{-}_{\mathrm{lo}})$ if $|b|_{\infty}\leq 1$ and $|b|_2\leq \sqrt{q}$

For a multigraph $G=(V,E)$, we consider a collection $\bB= (\bB^{(e)})_{e\in E_0}$ of matrices and a collection $\beta= (\beta^{(e)})_{e\in E_{\mathrm{lo}}}$ of vectors. The matrix $\bB^{(e)}$ has $p$ (resp. $q$) rows  if $e_1\in R$ (resp. $e_1\in C$).  Similarly, $\bB^{(e)}$ has $p$ (resp. $q$) columns  if $e_2\in R$ (resp. $e_2\in C$). The size of $\beta^{(e)}$ is $p$ (resp. $q$) if $e_1=e_2\in R$ (resp. $\in C$). Finally, $(G,\bB,\beta)$ is said to satisfy Property $(\cA_0)$ if:

(i) all matrices $\bB^{(e)}$ with $e\in E_0$ satisfy Condition $(\cB_0)$.

(ii) all vectors $\beta^{(e)}$ with $e\in E_{\mathrm{lo}}$ satisfy Condition $(\cB^{-}_{\mathrm{lo}})$.

(iii) all vectors $\beta^{(e)}$ with $e\in E_{\mathrm{lo}}$ where the self-loop $e$ is incident to a vertex $i$ such that $d_i\leq 1$ satisfy Condition $(\cB_{\mathrm{lo}})$.

Given a multigraph $G$, a collection $\bB$ of matrices and a collection $\beta$ of vectors, we define the quantity $W_{G,\bB,\beta}$ by

\begin{equation}\label{eq:definition_W}
W_{G,\bB,\beta} := \sum_{(\omega_i)_{i\in V}}\prod_{e\in E_0} \bB^{(e)}_{\omega_{e_1},\omega_{e_2}}\prod_{e\in E_{\mathrm{lo}}}\beta^{(e)}_{\omega_{e_1}}\ ,
\end{equation}

where the sum runs over $\omega_i$ runs from $1$ to $p$ if $i\in R$ and from $1$ to $q$ is $i\in C$.

Denote $V_{r,0,0}$ the subset of isolated vertices $i$ in $G$ that have a label $r$ and satisfy $d_i=d_{i,\mathrm{lo}}=0$. Similarly,
$V_{*,0,*}$ stands for the collection of vertices $i$ satisfying $d_i=0$, whereas  $V_{r,1,*}$ is the collection of vertices of type '$r$' that satisfy $d_i=1$. Finally,
$V_{r,\geq 2,*}$ is the collection of vertices of type '$r$' with $d_i\geq 2$.

If $(G,\bB,\beta)$ satisfies  Property $(\cA_0)$, then

\[
\big|W_{G,\bB,\beta} \big|\leq  p^{|V_{r,0,0}|+|V_{r,1,0}|/2}q^{ |V_{*,0,*}|- |V_{r,0,0}|+ [|V|- |V_{r,1,0}|/2-|V_{*,0,*}|  ]/2]}\left(\frac{p}{q}\right)^{(|V_{r,\geq 2,*}|-1)_+/2} \enspace .
\]

Let us now apply explicit how we can apply this result to the expression (<ref>) of $W_{\cP; D}$. We build a multigraph with $\kappa_1$ vertices of type 'r' and $\kappa_2$ vertices of type 'c'. For $r=1,\ldots, \kappa$, we add $D_r$ edges between the vertex $h_r$ of type 'r' and the vertex $h'_r$ of type 'c' and we associate the matrix  $\overline{\bA}$ to this edge. Obviously, we have $\|\overline{\bA}\|_{\infty}\leq 1$ and $\mathrm{Rank}(\bA)\leq q$ so that $\overline{\bA}$  satisfies $\mathcal{B}_0$. For $r=1,\ldots, z_{\cP}$, we also add an edge between the vertices $v_r$ and $v'_r$ where $v_r$ and $v'_r$ are defined in Lemma <ref>. If $v_r\neq v'_r$, we associate the matrix $\overline{\bB}^{(r)}$ which satisfies also $\cB_0$. If $v_r=v'_r$, then we associate the vector $(\bB^{(r)}_{a,a})$ to this self-loop. Since $\|\bB^{(r)}\|_{\infty}\leq 1$ and its rank is at most $q$, one readily checks that it satisfies $\cB_{\mathrm{lo}}$. We are therefore in position to apply Proposition <ref> to $W_{\cP,D}$.

\[
|W_{\cP,D}|\leq \|\bA\|_{\infty}^{4k- a}p^{|V_{r,0,0}|+|V_{r,1,0}|/2}q^{ |V_{*,0,*}|- |V_{r,0,0}|+ [|V|- |V_{r,1,1}|-|V_{*,0,*}|  ]/2]}\left(\frac{p}{q}\right)^{(|V_{r,\geq 2,*}|-1)_+/2} \enspace ,
\]

where we recall that $a= \sum_{r=1}^{\kappa}(|\cP_r|-D_r)$. For $r=1,\ldots, \kappa$, define $a_r = |\cP_r|-D_r$ so that $a= \sum_{r=1}^{\kappa} a_r$. From Lemma <ref>, we know that $a_r\geq 2$ and that $a_r\geq 3$ if $|\cP_r|\subset[2r]$ or $|\cP_r|\subset[2r+1:4r]$.

Let us consider any vertex $i$ of the $\kappa_2$ vertices of type '$c$'. The vertex $i$ corresponds to a group $\cP_{i,od}$ of $\cP_{\geq 2,od}$ and we write $s_i$ for the number of groups of $\cP_{\geq 2}$ whose intersection with this group of  $\cP_{\geq 2,ev}$ is non-empty. By definition of $\cP_{\geq 2,ev}$, we have $s_i\geq 1$ and $\sum_{i=1}^{\kappa_2} s_i = \kappa$. If $s_i=1$, we denote $r_i$ for the unique group $\cP_{r_i}$ which is included in $\cP_{i,ev}$.

Any node $i$ of type '$c$' such that $s_i=1$ and $a_{r_i}\leq 3$ has an external degree $d_i$ satisfying $d_i\geq 1$.

Similarly, we define for any vertex $i=1,\ldots, \kappa_1$ of type '$r$' the group $\cP_{i,ev}$, the number $s'_i$ of groups of $\cP_{\geq 2}$ that are included in $\cP_{i,ev}$ and, if $s'_i=1$, the index $r'_i$ such that $\cP_{r'_i}\subset \cP_{i,ev}$.

Any node $i$ of type '$r$' such that $s'_i=1$ and $a_{r'_i}\leq 3$ has an external degree $d_i$ satisfying $d_i\geq 1$. Besides,  if $s'_i=1$ and $a_{r'_i}=2$, then $d_i\geq 2$.

Since $p\geq q$, we deduce that

\[
|W_{\cP,D}|\leq \|\bA\|_{\infty}^{4k- a}p^{T_1 -T_3}q^{T_2+T_3}\ ,
\]

\[T_1= \sum_{i=1}^{\kappa_1}\left[\1_{s'_i>1}+ \1_{s'_i=1}\1_{a_{r'_i}\geq 4} + \frac{1}{2} \1_{s'_i=1}\1_{a_{r'_i}\in [2,3]}\right] \enspace ;
\]

\[
T_2= \sum_{i=1}^{\kappa_2}\left[\1_{s_i>1}+ \1_{s_i=1}\1_{a_{r_i}\geq 4} + \frac{1}{2} \1_{s_i=1}\1_{a_{r_i}\in [2,3]}\right]\ ,
\]

and $T_3= \tfrac{1}{2} \1_{\sum_{i=1}^{\kappa_1}\1_{s'_i=1}\1_{a_{r'_i}=2}>0}$. Since $\sum_{r=1}^\kappa a_r =a$ and $a_r\geq 2$, we derive that

\[
T_2\leq \frac{1}{4} a - \sum_{i=1}^{\kappa_2}\frac{1}{2}(s_i-2)_+ - \frac{1}{4}\sum_{r=1}^{\kappa}(a_r-2)_+ +\frac{1}{2}\sum_{i=1}^{\kappa_2}\1_{s_i=1}\1_{a_{r_i}\geq 4}
\]

and similarly that

T_1 ≤1/4 a - ∑_i=1^κ_11/2(s'_i-2)_+ - 1/4∑_r=1^κ(a_r-2)_+ +1/2∑_i=1^κ_1_s'_i=1_a_r'_i≥4 .
To finish, we consider four different cases depending on the value of $a$. If $a\equiv 0[4]$, then one readily checks that $T_1\leq a/4$ and $T_2\leq a/4$ which leads to
$|W_{\cP,D}|\leq \|\bA\|_{\infty}^{4k- a}p^{a/4}q^{a/4}$.  If $a\equiv 1[2]$, then at least one $a_{r}$ is odd and we deduce that $T_1\leq (a-1)/4$ and $T_2\leq (a-1)/4$ so that
$|W_{\cP,D}|\leq \|\bA\|_{\infty}^{4k- a}p^{(a-1)/4}q^{(a-1)/4}$. It remains to consider the case $a\equiv 2[4]$. We observe again that $T_2\leq a/4$ so that $T_2+T_3\leq \lceil a/4\rceil$. If $T_3=1/2$, we can use the simple bound $T_1\leq a/4$ so that $T_1-T_3\leq \lfloor a/4\rfloor$. If $T_3=0$, this implies that no index $i$ satisfies  $s'_i=1$ and $a_{r'_i}=2$, and we claim that $T_1\leq \lfloor a/4\rfloor = (a-2)/4$ which implies that $|W_{\cP,D}|\leq \|\bA\|_{\infty}^{4k- a}p^{\lfloor a/4\rfloor}q^{\lceil a/4\rceil}$.

It remains to establish the claim.
Since we know that $T_1\leq a/4$, and that 4 times the rhs of (<ref>) is an integer, it suffices to prove that the rhs of  (<ref>) is neither equal to $a/4$ nor to $(a-1)/4$. First, this expression cannot be equal to $(a-1)/4$ because this would imply that

\[
2\sum_{i=1}^{\kappa_1}\frac{1}{2}(s'_i-2)_+ -\sum_{r=1}^{\kappa}(a_r-2)_+  + 2\sum_{i=1}^{\kappa_1}\1_{s'_i=1}\1_{a_{r'_i}\geq 4}= 1\ ,
\]

which in turn would imply that $\sum_{r=1}^{\kappa}(a_r-2)_+ $ is odd  which contradicts that the fact that $a=\sum_{r=1}^{\kappa} a_r$ is even (recall that $a_r\geq 2$). Next, the only way of having the rhs of (<ref>) equal to $a/4$ is that (i)  all $s'_i$ are either equal to $1$ or $2$, (ii) that, for all $i$ such that $s'_i=1$, we have $a_{r'_i}=4$, and (iii) that all the remaining values of $a_{r}$ are equal to $2$.
This implies that $a\equiv 0[4]$ which contradicts the hypothesis $a\equiv 2[4]$.

In order to have $d_i=0$, we need that $a_{r_i}=|\cP_{r_i}|$, otherwise the graph contains at least $D_{r_i}= |\cP_{r_i}|-a_{r_i}$ external edges incident to $i$ (see (<ref>)). If $a_{r_i}=|\cP_{r_i}|=2$, then this implies that $|\cP_{r_i}\cap [2k]|=1$ and $|\cP_{r_i}\cap [2k+1:4k]|=1$, otherwise $W_{\cP,d}=0$ (Lemma <ref>). Hence, we have  $|\cP_{i,od}|=4$ with $|\cP_{i,od}\cap[2k]|=2$ and $|\cP_{i,od}\cap[2k+1;4k]|=2$. From the construction of the graph $G$, we deduce that $d_i=2$ (see (<ref>)).

Now assume that  $a_{r_i}=|\cP_{r_i}|=3$.Since $|\cP_{i,od}|$ is an even integer, and since the number of half edges incident to $i$ in the graph is $|\cP_{i,od}|- a_{r_i}$, it follows that the number of half edges is odd and at least one of these half edges is connected to a distinct vertex. Hence, we have $d_i\geq 1$.

The first claim is proved analogously to Lemma <ref>. We focus on the second claim.
Also, we have already shown in the previous proof that $d_i=2$ if $|a_{r'_i}|=|\cP_{r'_i}|=2$. If $|\cP_{r'_i}|\geq 4$ and $a_{r'_i}=2$, then there are $D_{r_i}= |\cP_{r_i}|-a_{r_i}\geq 2$ external edges incident to $i$ (see (<ref>)). It remains to consider the case where  $|\cP_{r'_i}|=3$ and $a_{r'_i}=2$. Then, $D_{r_i}=|\cP_{r_i}|-a_{r_i}=1$ and there is one external edge which is associated to $D_{r_i}$ (see (<ref>)). Besides, $|\cP_{i,ev}|-|\cP_{r'_i}|$ is odd and is the number of half-edges corresponding to the right-hand side term in (see (<ref>)). Since this number of half-edges is odd, at least one them corresponds to an external edge. Hence, we have proved that $d_i\geq 2$.

§.§ Proof of Proposition <ref>

The proof is based on an induction-like approach. We shall first iteratively prune the graph $G$ by removing small external degree vertices and we will show that the functional $\big|W_{G,\bB,\beta}\big|$ is not much larger than that of the pruned graph. We start with the following lemma that summarizes the pruning operations that we are able to consider.

Let $(G,\bB,\beta)$ satisfying $(\cA_0)$ and let $i\in V$ be a vertex  satisfying $d_i\leq 2$. If $d_i\leq 1$, we define $G^{(-i)}$ as the subgraph induced by $V\setminus\{i\}$. If  $d_i=2$ and $i$ has two distinct neighbors, then  $G^{(-i)}$ is defined as the subgraph induced by $V\setminus\{i\}$ where we add an edge $e$ connecting the two neighbors of $i$. If $d_i=2$ and $i$ is connected twice to the same neighbor, say $j$,  then  $G^{(-i)}$  is defined as the subgraph induced by $V\setminus\{i\}$ such that $j$ is incident to a single self-loop.
Then, the following holds:

(a) If $d_i=0$, then, for some $\bB'$, $\beta'$ such that ($G^{(-i)},\bB',\beta'$) satisfies $(\cA_0)$, we have

\[
\big|W_{G,\bB,\beta}\big|\leq  \big|W_{G^{(-i)},\bB',\beta')}\big| [q+ (p-q)\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0}]\ .
\]

(b) If $d_i=2$, then, for some $\bB'$, $\beta'$ such that ($G^{(-i)},\bB',\beta'$) satisfies $(\cA_0)$, we have

\[
W_{G,\bB,\beta}= W_{G^{(-i)},\bB',\beta'}\ .
\]

(c) If $d_i=1$ and the unique neighbor of $j$ satisfies $d_j\geq 3$, then, for some $\bB'$, $\beta'$ such that ($G^{(-i)},\bB',\beta'$) satisfies $(\cA_0)$, we have

\[
|W_{G,\bB,\beta}| \leq    \left|W_{G^{(-i)},\bB',\beta'} \right|\left[\sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0}\right]\enspace .
\]

(d) If $d_i=1$ and the unique neighbor of $j$ satisfies $d_j=1$, then, for some $\bB'$, $\beta'$ such that ($G^{(-i,-j)},\bB',\beta'$) satisfies $(\cA_0)$, we have

\[
\left|W_{G,\bB,\beta}\right| \leq   \left|W_{G^{(-i,-j)},\bB',\beta'}\right|\left[(\sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0})(\sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0})\right]\enspace .
\]

In view of this lemma, we iteratively prune the graph $G$ by  removing   vertex with external degree $0$  (case (a) above), or a vertex with external degree 2 (case (b) above) if no vertex with external degree 0 is left, or a vertex with external degree 1(cases (c) and (d) above) if no vertices with external  degrees $0$ or $2$ vertices are left. Then, the pruning process stops when the resulting graph $G'=(V',E')$ is  either  empty or when all its vertices have an external degree higher or equal to $3$. Below, we use the convention that $W_{G',\bB',\beta'}=1$ if $G'$ is empty

Denote $V_{r,0,0}\subset R$ the subset of vertices $i$ in $G$ that have a label $r$ and satisfy $d_i=d_{i,\mathrm{lo}}=0$. Define $V_{*,0,*}\subset V$ the subset of vertices $i$ in $G$ satisfying $d_i=0$.
Denote $V_{r,1,0}\subset R$ the subset of vertices $i$ in $G$ that have a label $r$ and satisfy $d_i=1$ and $d_{i,\mathrm{lo}}=0$.  Denote $R'= R\cap V'$ and $C'=C\cap V'$ the vertices of $G'$ of type $r$ and $c$ respectively. The following lemma is an application of Lemma <ref> above and controls $|W_{G,\bB,\beta}|$ in terms of $|W_{G',\bB',\beta'}|$.

We have $V'\subset V\setminus  (V_{*,0,*}\cup V_{r,1,0})$ and

\begin{equation}\label{eq:upper_WGBbeta}
|W_{G,\bB,\beta}|\leq |W_{G',\bB',\beta'}|p^{|V_{r,0,0}|+ |V_{r,1,0}|/2}q^{|V_{*,0,*}|-|V_{r,0,0}||+ [|V|-|V'|-|V_{*,0,*}|- |V_{r,1,0}|]/2]}\enspace ,
\end{equation}

where  $(G',\bB',\beta')$ satisfy $(\cA_0)$.

It remains to control quantities of the form $|W_{G',\bB',\beta'}|$ for graphs $G'$ whose vertices have all an external degree at least $3$. This is slightly more tricky than the previous arguments. See the proof of the following dedicated result.

Consider any multi-graph $G'=(V',E')$ whose vertices have an external degree at least $3$. Let $(\bB', \beta')$ be any matrices and vectors  such that $(G',\bB',\beta')$ satisfies Property $(\cA_0)$. Then, we have

W_G',',β'≤q^|V'|/2(p/q)^(|R'|-1)_+/2 ,
where we recall that $[x]_+= \max(x,0)$ and $R'\subset V'$ is the subset of vertices of type '$r$'.

Gathering the two previous lemmas leads to

\[
|W_{G,\bB,\beta}|\leq p^{|V_{r,0,0}|+ |V_{r,1,0}|/2}q^{|V_{*,0,*}|-|V_{r,0,0}||+ [|V|-|V_{*,0,*}|- |V_{r,1,0}|]/2]}\left(\frac{p}{q}\right)^{(|R'|-1)_+/2} \enspace .
\]

To conclude, we need to upper bound $|R'|$. Since all vertices of with external  degree $0$ or $1$ have been pruned in the above iterative algorithm, the vertex set $V'$ is only made of vertices of degree at least $2$. Hence, $R'\subset V_{r,2,*}$, the collection of vertices of type '$r$' with external degree at least $2$. The result follows.

§.§ Proof of  Lemmas <ref> and <ref>

Let us explain how we obtain (<ref>). As we first prune all vertices with external degree $0$ , it follows from Cases (a) and (b) in Lemma <ref> that

\begin{equation}\label{eq:upper_WGBbeta0}
|W_{G,\bB,\beta}|\leq |W_{G'',\bB'',\beta''}|p^{|V_{r,0,0}|}q^{|V_{*,0,*}|-|V_{r,0,0}|}\enspace ,
\end{equation}

where $G''$ is subgraph of $G$ induced by $V\setminus V_{*,0,*}$ and $(G'',\bB'',\beta'')$ satisfies $(\cA_0)$. Then, we observe that no pruning step in Lemma <ref> increases the external degree of any vertex. Therefore, at some point, the procedure prunes all the vertices $i$ satisfying $d_i=1$ in the original graph $G$.

If, at some point of the pruning procedure, we have decreased the degree $d_j$ of a vertex to $0$, then this implies that, in the previous step, we have pruned its unique neighbor, which was therefore an external degree $2$ vertex (case (b) in Lemma <ref>), so that the vertex $j$ must have now a self-loop. When we prune this vertex $j$ with external degree $0$, we pay a total price of $q$ for having pruned two vertices (cases (a) and (b) in Lemma <ref>).

If, at some point of the pruning procedure, we have decreased the degree $d_j$ of a vertex to $1$, then this vertex must now contain a self-loop. Indeed, the external degree of $j$ was at least $2$ in the previous step. It is not possible that it was equal to $2$, because this would imply that we have pruned an external degree one vertex before an external degree 2 vertex. Similarly, it is not possible that the external degree of $j$ was larger than $3$, otherwise its pruned neighbor would have been of external degree at least $3$. Finally, if the external degree of $j$ was equal to $3$, than its pruned neighbor $i$ was satisfying $d_i=2$ and pruning $i$ creates a self-loop in $j$ (see case (b) in Lemma <ref>). Since $j$ has a self-loop, it follows from  cases (c) and (d) in Lemma <ref>), we pay a price $\sqrt{q}$ when we prune $j$.

In summary, in the pruning process, all vertices with external degree at most $2$ have been pruned. We pay a price $p$ only when pruning vertices $i\in R$ with $d_i=d_{i,lo}=0$ in the original graph $G$. We pay a price $\sqrt{p}$ only when pruning vertices $i\in R$ with $d_i=1$ and $d_{i,lo}=0$ in the original graph $G$. We pay a price $q$ only for vertices satisfying $d_i=0$ and  $i\in C$ or $d_{i,lo}>0$ in the original graph $G$. Otherwise, we pay a $\sqrt{q}$ price for all the other pruned vertices. The result follows.

We start with a straightforward property that will be used several times through the manuscript.

If a matrix   $\bB$ satisfies $(\cB_{0})$, then  $\|\bB\|_{2}\leq \sqrt{q}$.

Indeed, $\|\bB\|^2_{2}=\sum_{i} \sigma_i^2(\bB)\leq \sigma_1^2(\bB)q = q$ because $\|\bB\|_{\infty}=1$ and the rank of $\bB$ is at most $q$.

If $(G,\bB,\beta)$ satisfies $(\cA_0)$ and if $G$ contains a vertex $i$ with external degree $d_i=0$. Then, we consider $G^{(-i)}$ as the graph induced by $V\setminus\{i\}$, $\bB^{(-i)}= \bB$, and $\beta^{(-i)}$ as the restriction of $\beta$ to self-loops that not incident to $i$.
We start from the decomposition

\[
W_{G,\bB,\beta}= W_{G^{(-i)},\bB^{(-i)},\beta^{(-i)}} \sum_{\omega_i}\prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega_i}\ ,
\]

where $E_{lo,i}$ is the subset of self-loops that are incident to $i$ and where we use the convention $\prod_{e\in \emptyset}\beta^{(e)}_{\omega_i} =1$. Assume first that $E_{lo,i}=\emptyset$, then the above sum over $\omega_i$ equals $p$ if $i\in R$ and $q$ if $i\in C$.  If $E_{lo,i}\neq\emptyset$, then one deduces from Condition ($\cA_0$) that the vector  $\gamma=(\prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega_i})$ satisfies $|\gamma|_1\leq q$, which yields

|W_G,,β|≤|W_G^(-i),^(-i),β^(-i)| [q+ (p-q)_i∈R_d_i,lo=0] .
If $G$ contains a vertex $i$ with external degree $d_i=2$, then we define
$G^{(-i)}$ as the subgraph $G$ induced by $V\setminus\{i\}$ where we have added a new edge $e'$ between the neighbors of $i$. If these neighbors, say $j$ and $k$, are distinct, then the new matrix $\bB^{(e')}$ is defined by

\[
\bB^{(e')}_{\omega,\omega'}= \sum_{\omega_i} \bB^{(j,i,1)}_{\omega,\omega_i}\bB^{(k,i,1)}_{\omega_i,\omega'} \prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega_i}\ .
\]

This matrix $\bB^{(e')}$ satisfies $(\cB_0)$.  Indeed, $\bB^{(e')}$ is a product of the matrices $\bB^{(j,i,1)}$ and  $\bB^{(k,i,1)}$ and of $|E_{lo,i}|$ diagonal matrices with diagonal entries given by the $\beta^{(e)}$. By Conditions $(\cB_0)$ and $(\cB_{\mathrm{lo}}^{-})$, the operator norm of all these matrices is smaller or equal to one, whereas the rank of the two first matrices in the product is smaller or equal to $q$. Hence, $\bB^{(e')}$ satisfies $(\cB_0)$. We have
$W_{G,\bB,\beta}=  W_{G^{(-i)},\bB^{(-i)},\beta^{(-i)}}$, where $\bB^{(-i)}$ is the collection $\bB$ of matrices  where we have removed $\bB^{(j,i,1)}$ and $\bB^{(k,i,1)}$ and added $\bB^{(e')}$ and where $\beta^{(-i)}$ is the collection $\beta$ of vectors  where we have removed all vectors corresponding to self-loops incident to $i$. Since the external degrees of the vertices $j$ and $k$ are left unchanged, this implies that $(G^{(-i)},\bB^{(-i)},\beta^{(-i)})$ satisfies ($\cA_0$).

If $i$ has a unique neighbor, say $j$, then the new edge $e'$ is a self-loop incident to $j$. The  new vector $\beta^{(e')}$ is defined by

\[
\beta^{(e')}_{\omega}=   \sum_{\omega_i} \bB^{(j,i,1)}_{\omega,\omega_i}\bB^{(j,i,2)}_{\omega,\omega_i} \prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega_i}\ .
\]

Applying Young's inequality and relying on the fact that the Frobenius norms of $\bB^{(j,i,1)}$ and $\bB^{(j,i,2)}$ are at most $\sqrt{q}$ (Lemma <ref>), we derive that $|\beta^{(e')}|_1\leq q$. Besides, $|\beta^{(e')}|_{\infty}\leq \|\bB^{(j,i,1)}\|_{\infty}\|\bB^{(j,i,2)}\|_{\infty}\leq 1$. As a consequence, $\beta^{(e')}$ satisfies $(\cB_{\mathrm{lo}})$. If the vertex $j$ had no previous self-loop, we consider $\bB^{(-i)}$ as the collection  $\bB$ of matrices where we have removed $\bB^{(j,i,1)}$ and $\bB^{(j,i,2)}$. Besides, we consider  $\beta^{(-i)}$ as the collection $\beta$ of vectors  where we have removed all vectors corresponding to self-loops incident to $i$ and we have added $\beta^{(e')}$. Hence, $(G^{(-i)},\bB^{(-i)},\beta^{(-i)})$ satisfies ($\cA_0$) and we have $W_{G,\bB,\beta}=  W_{G^{(-i)},\bB^{(-i)},\beta^{(-i)}}$. It remains to consider the case where $j$ had already at least one self-loop. We cannot simply use $(G^{(-i)},\bB^{(-i)},\beta^{(-i)})$ as before because the external degree of $j$ is possibly smaller than one while some of the vectors  $\beta^{(e)}$ associated to self-loops incident to $j$ do not necessarily satisfy ($\mathcal{B}_{\mathrm{lo}}$). To resolve this small issue, we merge all the self-loops of $j$ together and replace them  by a single self-loop, say $e''$ whose associated vector $\beta^{(e'')}$ is the coordinate-wise product of the vectors, i.e. $\beta^{(e'')}_{\omega}=\beta^{(e')}_{\omega}\prod_{e\in E_{l_0,j}}\beta^{(e)}_{\omega}$. One easily checks that $\beta^{(e'')}$ satisfied ($\cB_{\mathrm{lo}}$). The result follows.

Finally, we consider the case where  $G$ contains a vertex $i$ with external degree $d_i=1$ and we denote $j$ its unique neighbor.

* If $d_j=1$. Then, we have

\[
|W_{G,\bB,\beta}|\leq   \left|W_{G^{(-i,-j)},\bB^{(-i,-j)},\beta^{(-i,-j)}}\right|\left[(\sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0})(\sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0})\right]\enspace ,
\]

where $G^{(-i,-j)}$ is the subgraph induced by $V\setminus \{i,j\}$.
Indeed, denoting $e'$ the unique edges between $i$ and $j$, we have the decomposition

\[
W_{G,\bB,\beta} =   W_{G^{(-i,-j)},\bB^{(-i,-j)},\beta^{(-i,-j)}} \sum_{\omega,\omega'}\bB^{(e')}_{\omega,\omega'} \prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega}\prod_{e\in E_{lo,j}}\beta^{(e)}_{\omega'}\ ,
\]

and we only have to bound this sum over $\omega$ and $\omega'$. Since $\|\bB^{(e')}\|_{\infty}\leq 1$, we have

\[
\left|\sum_{\omega,\omega'}\bB^{(e')}_{\omega,\omega'} \prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega}\prod_{e\in E_{lo,j}}\beta^{(e)}_{\omega'} \right| \leq \Bigg[\underset{=A}{\underbrace{\sum_{\omega}\left(\prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega}\right)^2}}\Bigg]^{1/2} \Bigg[\sum_{\omega'}\left(\prod_{e\in E_{lo,j}}\beta^{(e)}_{\omega'}\right)^2\Bigg]^{1/2}\ .
\]

By symmetry, we only need to consider the sum over $\omega$. If $d_{i,\mathrm{lo}}=0$, then we see that $A=q$ if $i\in C$ and $A=p$ if $i\in R$.  If $d_{i,\mathrm{lo}}>0$, then, we
deduce from Condition $(\cB_{\mathrm{lo}})$ that

\[
A\leq \sum_{\omega } \left|\prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega}\right|\leq q\enspace ,
\]

which concludes the proof.

* If $d_j\geq 3$ then we consider the subgraph $G^{(-i)}$ induced by $V\setminus \{i\}$ where we have added a self-loop $e'$ incident to $j$. We have

\[
W_{G,\bB,\beta}= \sum_{(\omega_l)_l\in V\setminus\{i,j\}}\sum_{\omega_j}\prod_{e\in E_0^{(-i)}}\bB^{(e)}_{\omega_{e_1}, \omega_{e_2}}\prod_{e\in E_{\mathrm{lo}}^{(-i)}}\beta^{e}_{\omega_{e_1}}\left[
\sum_{\omega_i}\bB^{(j,i,1)}_{\omega_j,\omega_i} \prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega_j}\right]\ ,
\]

where $E_{\mathrm{lo}}^{(-i)}$ is the set of self-loops that are not incident to $i$ and $E_0^{(-i)}$ is the subset of edges not incident to $i$.
Define the vector $\beta^{e'}$ by

\[
\beta^{e'}_{\omega}= \left[\sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0}\right]^{-1} \sum_{\omega_i}\bB^{(j,i,1)}_{\omega,\omega_i} \prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega_j}\ .
\]

Obviously we have

\[
|W_{G,\bB,\beta}| \leq    \left|W_{G^{(-i)},\bB^{(-i)},\beta^{(-i)}}\right|\left[\sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0}\right]\enspace ,
\]

Since the external degree of $j$ is still larger or equal to $2$ after the pruning step, we only have to prove that  $\beta^{(e')}$ satisfies $(\cB^{-}_{\mathrm{lo}})$.
Indeed, define the vectors $\gamma$ and $\delta$ by

\[
\gamma_{\omega}= \sum_{\omega_i}\bB^{(j,i,1)}_{\omega,\omega_i} \prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega_i} \ ; \quad \delta_{\omega}=\prod_{e\in E_{lo,i}}\beta^{(e)}_{\omega} .
\]

Since the  $\beta^{(e)}$'s satisfy $\cB_{\mathrm{lo}}$ (as $d_i=1$), we have $|\delta|_{\infty}=1$ and $|\delta|_1= \sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0}$. Since $\bB^{(i,j,1)}$ satisfies ($\cB_0$), it follows that the vector $\gamma$ satisfies

\[
|\gamma|_{2}=  |\bB^{(i,j,1)}\delta|_2\leq \| \bB^{(i,j,1)}\|_{\infty}|\delta|_2\leq \sqrt{q}+ [\sqrt{p}-\sqrt{q}]\1_{i\in R}\1_{d_{i,\mathrm{lo}}=0}\ .
\]

This implies that the  $|\beta^{(e')}|_2\leq 1$ and $\beta^{(e')}$ therefore satisfies $(\cB^{-}_{\mathrm{lo}})$.

§.§ Proof of Proposition <ref>

We shall establish the desired bound under different conditions and then show how to transform $(G', \bB', \beta')$ to satisfy these new conditions. A multigraph $G = (V, E)$ is said to satisfy Property $(\cG^*)$ if:

(a) $G$ does not contain any self-loop.

(b) Any pair of vertices is connected by at most 2 edges.

(c) The minimum degree is larger or equal to $2$.

(d) If the degree of a vertex is $2$, the this vertex has only one neighbor. In other words, this vertex shares two edges with another vertex.

A matrix  $\bC$ is said to satisfy Condition $(\cB^*)$ if (a) the entries of $\bC$ are non-negative,  if (b) the $l_2$ norm of each row and each column of $\bC$ is at most one, and if  (c) the Frobenius norm of $\bC$ is at most $\sqrt{q}$.

Finally, we say that $(\bG, \bB)$ where $\bB= (\bB^{(e)})$ is a collection of matrices indexed by the edges of $G$ satisfies Property $(\cA^*)$ is $G$ satisfies $(\cG^*)$ and all matrices $\bB^{(e)}$ satisfy $(\cB^*)$.

For any $(G,\bB)$ satisfying Condition ($\cA^*$), we have

W_G,≤q^|V|/2(p/q)^(|R|-1)_+/2 ,
where we recall that $[x]_+= \max(x,0)$ and $R\subset V$ is the subset of vertices of type '$r$'.

Let us show how to apply this result to $W_{G',\bB',\beta'}$. First, we transform $G'$ into a multigraph $G^{\uparrow}$ by erasing the self-loops of $G'$. Recall that the external degree of each vertex in $G'$ is at least $3$. For  any vertex $i\in V$, we pick an external edge $e=(k,i,a)$ incident to $i$ and we modify the corresponding matrix $(\bB')^{(e)}$ into $(\bB^{\uparrow})^{(e)}$ by setting $(\bB^{\uparrow})^{(e)}_{\omega, \omega'}= (\bB')^{(e)}_{\omega, \omega'}\prod_{e\in E_{l_0,i}}\beta^{(e)}_{\omega}$. One checks that the resulting matrix  $(\bB^{\uparrow})^{(e)}$ still satisfies $(\cB_{0})$. For all the other external edges $e$, we set
$(\bB^{\uparrow})^{(e)}= \bB^{(e)}$.
As a consequence,  the resulting  multigraph $G^{\uparrow}= (V, E^{\uparrow})$ is such that $(G^{\uparrow}, \bB^{\uparrow})$ satisfies $(\cA_0)$ and
$W_{G^{\uparrow}, \bB^{\uparrow}}=   W_{G',\bB',\beta'}$. Next, we modify $G^{\uparrow}$ by erasing some edges in such a way that any pair of vertices is connected by at most twice edges. We call $G^{\ddagger}$ the resulting multigraph. Since the degree of any vertex in
$G^{\uparrow}$ is larger or equal to $3$, one easily checks that $G^{\ddagger}$ satisfies Condition ($\cG^*$). Then, we define the collection of matrix $\bB^{\ddagger}$ as follows. For any pair of vertices that are connected by at most 2 edges, we simply define $(\bB^{\ddagger})^{(e)}$ by
$(\bB^{\ddagger})^{(e)}_{\omega,\omega'}= \big|(\bB^{\uparrow})^{(e)}_{\omega,\omega'}\big|$ for the corresponding edges. If there are more than $2$ edges, then the first matrix $(\bB^{\ddagger})^{(e)}$ is defined as above, whereas the second matrix $(\bB^{\ddagger})^{(e)}$ corresponding to the second edge
is defined by the product of the absolute values of the entries of the remaining matrices $(\bB^{\uparrow})^{(e')}$. Equipped with these notation, we straightforwardly have

|W_G', ',β'|=  |W_G^↑, ^↑|≤W_G^, ^ .
It remains to show that the matrices $(\bB^{\ddagger})^{e}$ all satisfy Condition $(\cB^*)$. Since the maximum entry (in absolute value value) of all matrices $(\bB^{\uparrow})^{e}$ is at most one because $\|(\bB^{\uparrow})^{e}\|_{\infty}\leq 1$, it suffices to establish the following claim: if a matrix $\bC$ satisfies Condition $(\cB_0)$, then the matrix $\overline{\bC}$ defined by  $\overline{\bC}_{\omega,\omega'}= |\bC_{\omega,\omega'}|$ satisfies $(\cB^*)$. Indeed, it follows from Lemma <ref> that $\|\overline{\bC}\|_2=\|\bC\|_2\leq \sqrt{q}$. Besides, the $l_2$ norm of each row and each column of $\overline{\bC}$ is upper bounded by the operator norm of $\bC$ and is therefore smaller than one. The claim follows. Since $(G^{\ddagger}, \bB^{\ddagger})$ satisfies $(\cA^*)$, we are in position to apply Proposition <ref> and the result follows from (<ref>).

Before turning to the proof  Proposition <ref>, we state a simple result that will be used several times.

Let $\bC_1$ and $\bC_2$ be any two $r\times s$ and $s\times t$ matrices that satisfy Property $(\cB^*)$. Then the product matrix $q^{-1/2}\bC_1\bC_2$ also satisfies Property $(\cB^*)$.

We prove this result by induction on the number $|V|$ of vertices. We start by considering any pair $(G, \bB)$ with $|V|= 2$ vertices that satisfies $(\mathcal{A}^*)$.  Since the two vertices are connected by exactly two edges, we  derive from Young's inequality that

\begin{eqnarray*}
W_{G,\bB} &= &\sum_{\omega_1,\omega_2=1}^{p}\prod_{e\in E} \bB^{(e)}_{\omega_1,\omega_2}\leq \frac{1}{2}\sum_{e\in E}\sum_{\omega_1,\omega_2=1}^{p} (\bB^{(e)}_{\omega_1,\omega_2})^2
\leq q\leq q^{|V|/2}\left(\frac{p}{q}\right)^{(|R|-1)_+/2}\ ,
\end{eqnarray*}

where we used that  the Frobenius norms of the matrices $\bB^{(e)}$ is at most $\sqrt{q}$ by Condition ($\mathcal{B}$).

[Case 1.a]  [Case 1.b.i]  [Case 1.b.ii]  [Case 3]
Examples of pruned graphs in the proof of Proposition <ref>.
Vertices and edges in red are removed, whereas edges in dotted green are inserted.

Let us now consider any $(G,\bB)$ satisfying $(\cA^*)$ with $|V|\geq 3$.
If the graph $G$ is not connected, we write $G_1=(V_1,E_1)$, $G_2=(V_2,E_2)$,…, $G_K=(V_K,E_K)$ its decomposition into connected components and $\bB_1$, …, $\bB_K$ the corresponding collection of matrices. Obviously, each $(G_j,\bB_j)$ satisfies the property $(\cA^*)$. Besides, we have  $W_{G,\bB} = \prod_{j=1}^K   W_{G_j,\bB_j}$. By induction, we conclude that  $W_{G,\bB} \leq q^{|V|/2}\left(\frac{p}{q}\right)^{(|R|-1)_+/2}$. We focus henceforth on the situation where $G$ is connected. Since $|V|\geq 3$, this implies that at least one vertex has a degree larger or equal to $3$. The analysis is divided into three cases.

CASE (1): there exists a least one vertex whose degree is exactly $3$. Then, we pick any degree $3$ vertex $i$ of type $r$  if there exists one and otherwise we pick any degree $3$ vertex $i$ of type $c$. There are two sub-cases depending on the number of distinct neighbors of $i$.

CASE (1.a): the vertex $i$ has three distinct neighbors $j$, $k$, and $l$ in $G$ –see Figure <ref>. Since $W_{G,\bB}$ is decreasing with the number of edges, we start by removing the edge between $i$ and $l$ from $E$ and the corresponding matrix $\bB^{(i,l,1)}$ from $\bB$. We write $G^p$ the corresponding pruned graph and $\bB^p$ the corresponding collection of matrices. Focusing on the sum over $w_i$ in $W_{G,\bB}$, we have

\begin{eqnarray*}
W_{G,\bB} \leq   W_{G^{p},\bB^{p}} = \sum_{\omega_t,\ t\in V\setminus\{i\}}\prod_{e\in E^{(-i)}} \bB^{(e)}_{\omega_{e_1},\omega_{e_2}} \sum_{\omega_i}\prod_{e\in E^{p}_{i}}\bB^{(e)}_{\omega_{e_1},\omega_{e_2}}\ ,
\end{eqnarray*}

where $E^{p}_{i}$ is the set of edges incident to $i$.
We denote $e'=(i,j,1)$ and $e''=(i,k,1)$ the two edges incident to $i$ in $G^p$. Then, we introduce the matrix $\bC$ defined by
$ \bC_{\omega,\omega'}=\sum_{\omega_i} \bB^{(e')}_{\omega_i,\omega}\bB^{(e'')}_{\omega_i,\omega'}$,
where the sum over $\omega_i$ runs over $[p]$ if $i$ is of type '$r$' and over $[q]$ if $j$ is of type '$c$'. From Lemma <ref>, we deduce that
$\bC/\sqrt{q}$ satisfies Condition $(\cB^*)$, so that

\[
W_{G^p,\bB}\leq \sum_{\omega_t,\ t\in V\setminus\{i\}}\prod_{e\in E^{(-i)}} \bB^{(e)}_{\omega_{e_1},\omega_{e_2}} \bC_{\omega_{j},\omega_{k}}\ .
\]

We now consider the modification $\overline{G}$ and $\overline{\bB}$ of $G^p$ and $\bB^p$ by removing the vertex $i$ and, if there are at most one edge between $i$ and $k$, we insert a new edge $\overline{e}$ between $j$ and $k$ and associate the matrix $\overline{\bB}^{(\overline{e})}= \bC/\sqrt{q}$. All the other matrices $\bB^{(e)}$ are left unchanged. Then, we have

\[
W_{G,\bB}\leq \sqrt{q}W_{\overline{G},\overline{\bB}}\ .
\]

Among the remaining vertices in $\overline{G}$, only the vertex $l$ possibly does not meet the conditions in $(\cG^*)$. If $l$ satisfies those condition, then ($\overline{G},\overline{\bB}$) satisfies $(\cA^*)$, and by induction, we conclude that

\[
W_{G,\bB}\leq \sqrt{q}q^{|\overline{V}|/2}\left(\frac{p}{q}\right)^{(|\overline{R}|-1)_+/2}\leq q^{|V|/2}\left(\frac{p}{q}\right)^{(|R|-1)_+/2}\ ,
\]

where we denote $\overline{R}$ the collection of vertices of type '$r$' in $\overline{G}$. If $l$ does not satisfy the degree condition in $(\cG^*)$, then this implies that the degree of $l$ in $G^p$ is $2$ and that $l$ is connected to two distinct vertices, say $m$ and $n$. Denoting  $e'=(l,m,1)$ and $e''=(l,n,1)$ these two edges, we consider as above the matrix $\bC'$ defined by  $\bC'_{a,b}=\sum_{\omega_l} \bB^{(e')}_{\omega_l,a}\bB^{(e'')}_{\omega_l,b}$.
Again, the matrix $\bC'/\sqrt{q}$ satisfies $(\cB^*)$ by Lemma <ref>. Then,

\[
W_{\overline{G},\overline{\bB}}\leq \sum_{\omega_s,\ s\in V\setminus \{i,l\}}\prod_{e\in \overline{E}^{-l}} \overline{\bB}^{(e)}_{e_1,e_2} \bC_{\omega_{m},\omega_{n}}\ .
\]

Finally, we consider the transformations $(\overline{G}',\overline{\bB}')$  of $(\overline{G},\overline{\bB})$ where we remove the vertex $l$ and, if the number of edges between $m$ and $n$ is at most one, we insert an edge $\tilde{e}$ between $m$ and $n$ and introduce the corresponding matrix $\overline{\bB}'^{(\tilde{e})}= \bC/\sqrt{q}$. Then, $(\overline{G}',\overline{\bB}')$ satisfies Condition ($\cA^*$) and  we conclude  by induction that

\[
W_{G,\bB}\leq qq^{|\overline{V}'|/2}\left(\frac{p}{q}\right)^{(|\overline{R}'|-1)_+/2}\leq q^{|V|/2}\left(\frac{p}{q}\right)^{(|R|-1)_+/2}\ .
\]

CASE (1.b): the vertex $i$ has only two neighbors $j$ and  $k$ in $G$. Without loss of generality, we can assume that there are two edges between $i$ and $j$ and only one between $i$ and $k$. Since $W_{G,\bB}$ is non-decreasing with the number of edges, we start by removing the edge between $i$ and $k$ and call $G^p$ the corresponding pruned graph. We consider again two sub-cases depending on whether the vertex $k$ satisfies the degree condition of  $(\cG^*)$ in  the pruned graph $G^p$.
CASE (1.b.i) The vertex $k$ does not satisfy the degree condition of $(\cG^*)$ in the pruned graph $G^p$  –see Figure <ref>. Then, this implies that, in $G^p$, $d_k=2$ and that $k$   is connected to two distinct vertices, say $l$ and $m$.  argue as in Case 1.a by introducing the matrix $\bC$ defined by

\[
\bC_{\omega,\omega'}=\sum_{\omega_k} \bB^{(e)}_{\omega_k,\omega}\bB^{(e')}_{\omega_k,\omega'}\ .
\]

where $e$ and $e'$ respectively stand for the edges $e= (k,l,1)$ and $e'=(k,m,1)$. The matrix $\bC/\sqrt{q}$ satisfies Condition $(\cB^*)$ by Lemma <ref>. Then,  we consider the transformation $(\overline{G},\overline{\bB})$ of $(G^p,\bB^p)$, where we remove the vertex $k$ and, if the number of edges between $l$ and $m$ is at most one, we insert an edge $\overline{e}$ between $l$ and $m$  with the matrix $\overline{\bB}^{(\overline{e})}= \bC/\sqrt{q}$. Then, $(\overline{G},\overline{\bB})$ satisfies Condition $(\cA^*)$ and $W_{G,\bB}\leq \sqrt{q}W_{\overline{G},\overline{\bB}}$.  By induction, we conclude that

\[
W_{G,\bB}\leq \sqrt{q}W_{\overline{G},\overline{\bB}}\leq  q^{|V|/2}\left(\frac{p}{q}\right)^{(|R|-1)_+/2}\ .
\]

CASE (1.b.ii) In the pruned graph $G^p$, the vertex $k$ satisfies the conditions of $(\cG^*)$. Hence, $(G^{P},\bB^{P})$ satisfy Condition $(\mathcal{A}^*)$. We now focus on the vertices $i$ and $j$ –recall that they are connected by two edges. If the degree of $j$ is equal to $2$, then $i$ and $j$ form a connected component of size $2$ in $G^p$. Decomposing $G^p$ into an union of at least two connected components, we conclude by induction  as in the beginning of the proof that

\[
W_{G,\bB}\leq  W_{G^p,\bB^P}\leq    q^{|V|/2}\left(\frac{p}{q}\right)^{(|R|-1)_+/2} \ .
\]

We now assume that the degree of $j$ is at most $3$ in $G^p$  –see Figure <ref>. Let us denote $e=(i,j,1)$ and $e'=(i,j,2)$ the two edges between $i$ and $j$. We derive from Condition $(\cB^*)$ and Young's inequality that, for any $\omega_j$,

\[
\sum_{\omega_i} \bB^{(e)}_{\omega_i,\omega_j}\bB^{(e')}_{\omega_i,\omega_j}\leq \frac{1}{2}\sum_{\omega_i} \left(\bB^{(e)}_{\omega_i,\omega_j}\right)^2+ \left(\bB^{(e')}_{\omega_i,\omega_j}\right)^2\leq 1\ .
\]

As a consequence, the new pruned graph $G^{(-i)}$ where we have removed the vertex $i$  and all edges incident to $i$ satisfies

\[
W_{G,\bB}\leq  W_{G^{(-i)},\bB^{(-i)}}\ .
\]

If, in $G^{(-i)}$, the vertex $j$ satisfies the degree conditions of $(\cG^*)$, then $(G^{(-i)},\bB^{(-i)})$ satisfies $(\cA^*)$ and we conclude by induction. If the vertex $j$ does not satisfy the degree conditions $(\cG^*)$, then either $d_j=1$ or $d_j=2$ and $j$ has two distinct neighbors. In the latter case, we have already explained (e.g. in Case (1.b.i)) how to factorize the sum  with respect to $\omega_j$ in $ W_{G^{(-i)},\bB^{(-i)}}$  to build a multi-graph $\overline{G}$ with vertex set $V\setminus\{i,j\}$  and a collection  of matrices $\overline{\bB}$ satisfying Condition $(\cA^*)$ and such that

\[
W_{G^{(-i)},\bB^{(-i)}}\leq \sqrt{q}W_{\overline{G},\overline{\bB}}\ .
\]

Then, we conclude by induction. It remains to consider the case where $j$ has exactly one neighbor in $G^{(-i)}$. Let us denote $l$ this neighbor and $e=(j,l,1)$ the corresponding edge. In $W_{G^{(-i)},\bB^{(-i)}}$ we focus on the sum

\[
\sum_{\omega_j}\bB^{(e)}_{\omega_j,\omega_l} \ .
\]

By Cauchy-Schwarz inequality and Condition $(\cB^*)$, this sum is bounded by $\sqrt{q}$ if $j$ is of type '$c$' and by $\sqrt{p}$ if $j$ is of type '$r$'. Since the degree of $j$ in $G^{(-i)}$ is 1, this entails that the degree of $j$ in $G$ is equal to 3. Hence, if $j$ is of type '$r$', then this implies that $i$ is of type '$r$' because we have picked $i$ as one of the degree 3 vertices of type '$r$' if there exists at least one. Hence, considering the new pruned graph $(G^{(-i,-j)},\bB^{(-i,-j)})$ where we have also removed the vertex $j$, we arrive at

\[
W_{G,\bB}\leq \sqrt{q}\sqrt{\frac{p}{q}}^{\1_{i,j\in R}} W_{G^{(-i,-j)},\bB^{(-i,-j)}}\ .
\]

In $G^{(-i,-j)}$, only the vertex $l$ possibly does not satisfy the degree condition in  $(\cG^*)$. Hence, if $l$ satisfies the degree conditions in $(\cG^*)$, then $(G^{(-i,-j)},\bB^{(-i,-j)})$ satisfies $(\cA^*)$ and we conclude by induction. Otherwise, the vertex $l$ has two distinct neighbors say $m$ and $n$  in $G^{(-i,-j)}$ with corresponding edges $e$ and $e'$. As already  argued several times, we focus the sum over $\omega_l$  of $\bB^{(e)}_{\omega_l,\omega_m} \bB^{(e')}_{\omega_l,\omega_{n}}$. This allows us to build a graph $\overline{G}$ with vertex set $V\setminus \{i,j,l\}$ and a collection   $\overline{\bB}$ of matrices that satisfy Condition $(\cA^*)$ and such that

\[
W_{G^{(-i,-j)},\bB^{(-i,-j)}}\leq \sqrt{q}W_{\overline{G},\overline{\bB}}\ .
\]

Then, we conclude by induction.

CASE $(2)$: The degree of all vertices in $G$ is at least $4$. Since the sum $W_{G,\bB}$ does not decrease when we remove edges in $G$, we can iteratively prune the graph by removing some edges until one vertex has a degree $3$. If the pruned graph $G^p$ is not connected, we conclude as in the beginning of the proof. If the pruned graph is connected, then we come back to Case $1$.

CASE $(3)$: No vertex has a degree $3$ and there exists at least one vertex with degree $2$. We pick one of the degree $2$ vertices, say $i$. Denoting $j$ the neighbor of $i$ in $G$, we observe that the degree of $j$ in $G$ is at least $4$ since $G$ is connected and since $d_j\neq 3$. Arguing exactly as in Case 1.ii.b, we observe that  $(G^{(-i)},\bB^{(-i)})$ where we have removed the vertex $i$ and the two edges incident to $i$ satisfies

\[
W_{G,\bB}\leq  W_{G^{(-i)},\bB^{(-i)}}\ .
\]

If, in $G^{(-i)}$, $j$ satisfies the degree conditions of $(\cG^*)$, then $(G^{(-i)},\bB^{(-i)})$ satisfies Condition $(\cA^*)$ and we conclude by induction. If $j$ does not satisfy the  degree conditions of $\cG$ in $G^{(-i)}$, then $d_j=2$ and $j$ has two distinct neighbors, say $k$ and $l$ –see Figure <ref>. As argued several times, we prune the vertex $j$ and possibly create an edge between $k$ and $l$ to build $(\overline{G},\overline{\bB})$ satisfying $(\cA^*)$ and such that

\[
W_{G^{(-i)},\bB^{(-i)}}\leq \sqrt{q}W_{\overline{G},\overline{\bB}}\ .
\]

Then, we conclude by induction.

Let us denote $\bD= \bC_1\bC_2$. We only have to prove that $\|\bD\|_2\leq q$ and that the $l_2$ norms of each row and column is smaller or equal to $\sqrt{q}$. Since the Frobenius norm is sub-multiplicative (as long as all Schatten norms), we deduce that

\[
\|\bD\|_2\leq \|\bC_1\|_2\|\bC_2\|_2  \leq q \ ,
\]

since both $\bC_1$ and $\bC_2$ satisfy $(\cB^*)$. Consider that $a$-th row of $\bD$. Then,
∑_b=1^t ^2_ab   =    ∑_b=1^t [∑_c=1^s (_1)_a,c(_2)_c,b ]^2 ≤∑_b=1^t [∑_c=1^s(_1)^2_a,c][∑_c'=1^s(_2)^2_c',b]

≤     ∑_b=1^t ∑_c'=1^s(_2)^2_c',b≤q ,
where we used in the second line that the $l_2$ norm of the $a$-th row of $\bC_1$ is at most one and  that the Frobenius norm of $\bC_2$ is at most $q$.

§.§ Proof of Technical Lemmas

Given a positive integer $k$, we write $a_{l,k}$ for the coefficients of the decomposition of the $k$-th Hermite polynomial in the canonical basis, that is $H_k(x)= \sum_{l=0}^{k} a_{l,k}x^{l}$.  First, we consider the case where $k$ is even. Since $H_{k}$ is a symmetric polynomial, we derive that

\begin{eqnarray*}
\E[H_k(Y)] &=&\sum_{l=0}^{k/2} \E[a_{2l,k} (\theta+E)^{2l}] =  \sum_{s=0}^{k} \theta^{s} \sum_{l=\lceil s/2 \rceil }^{k/2}  a_{2l,k} \binom{2l}{2l-s}\E[E^{2l-s}]\\
& = &a_{k,k} \theta^{k}+ a_{k,k} \theta^{k-1} k\E[E] +  \theta^{k-2}\left[a_{k,k}\frac{k(k-1)}{2}\E[E^2]+ a_{k-2,k}  \right]\\ & &+ \sum_{s=0}^{k-3} \theta^{s} \sum_{l=\lceil s/2 \rceil }^{k/2}  a_{2l,k} \binom{2l}{2l-s}\E[E^{2l-s}] \\
& =& \theta^{k} + \sum_{s=0}^{k-3} \theta^{s} \sum_{l=\lceil s/2 \rceil }^{k/2}  a_{2l,k} \binom{2l}{2l-s}\E[E^{2l-s}] \ ,
\end{eqnarray*}

because $\E[E]=0$, $\E[E^2]=1$, $a_{k,k}=1$ and $a_{k,k}\frac{k(k-1)}{2}+a_{k-2,k}=0$. The two latter identities are a consequence of the equality $\E[H_{k}(\theta+ Z)]=\theta^k$ when $Z\sim \cN(0,1)$. Similarly, if $k$ is odd, we derive that

\[
\E[H_k(Y)] = \theta^{k} + \sum_{s=0}^{k-3} \theta^{s} \sum_{l=\lceil (s-1)/2 \rceil }^{(k-1)/2}  a_{2l+1,k} \binom{2l+1}{2l+1-s}\E[E^{2l+1-s}] \ .
\]

Next, we upper bound the coefficients of the polynomial $P_{k}$. For $l\equiv k [2]$, it is well known that the coefficient $a_{l,k}$ of the Hermite polynomial satisfies

\[
a_{l,k}=  \frac{k!}{2^k l! [(k-l)/2]!}(-1)^{(k-l)/2} \ ,
\]

so that

|a_l,k|≤1/2^kkl(k-l)^(k-l)/2≤(k-l)^(k-l)/2≤k^k/2 .
Besides, we know (e.g. [39]) that  $|\E[E^k]|\leq (c\|E\|_{\psi_2}\sqrt{k})^k$ for some positive numerical constant $c$.
Writing $P_{k}(x)= \sum_{l=0}^{k-3}b_{l,k}x^k$, we derive that $|b_{l,k}|\leq c^k\|E\|_{\psi_2}^k k^{k+1}2^{k}$.
Let us turn to $\E[H_kH_l(Y)]$.

\begin{eqnarray*}
\E[H_kH_l(Y)]&= & \sum_{s=0}^{k+l} \sum_{t=(s-l)\vee 0}^{s\wedge k} a_{t,k}a_{s-t,l}\E[(\theta+E)^{s}]\\
& = & \sum_{r=0}^{k+l}\theta^{r}  \left[ \sum_{s=r}^{k+l} \sum_{t=(s-l)\vee 0}^{s\wedge k} a_{t,k}a_{s-t,l}  \binom{s}{r}\E[E^{s-r}]\right]\\
& =& \theta^{k+l}+ \sum_{r=0}^{k+l-2}\theta^{r}  \left[ \sum_{s=r}^{k+l} \sum_{t=(s-l)\vee 0}^{s\wedge k} a_{t,k}a_{s-t,l}  \binom{s}{r}\E[E^{s-r}]\right]\ ,
\end{eqnarray*}

because $a_{k,k}=a_{l,l}=1$ and $a_{k-1,k}=a_{l-1,l}=0$. The rhs in the above identity corresponds to a polynomial of degree at most $k+l-2$. Arguing as above, we derive that its coefficients are uniformly bounded (in absolute value) by $(c\|E\|_{\psi_2})^{(k+l)}(k+l)^{2+(k+l)}$.

Finally, we consider the case where
$k+l=2=k\vee l$. Then, we observe that $\E[H_k(Y)H_{l}(Y)]= \E[H_2(Y)]= \E[(\theta+E)^2-1]= \theta^2$ so that $Q_{k,l}=0$.

We prove the first result by induction on the size of   $v_{\cP}= \sum_{r}|\cP_r|\1_{|\cP_r|>1}$. If $v_{\cP}=0$, then $G_{\cP}=0$ by definition. Consider any partition $\cP$ such that $v_{\cP}>0$, $\cP$ contains a group, say $\cP_1$, of size $2$ satisfying $\cP_1\subset [2k]$ or $\cP_1\subset[2k+1,4k]$. We build the finer collection $\cP^{(-1)}\triangleleft \cP$ by breaking $\cP_1$ into two singletons. Then,

\begin{eqnarray*}
G_{\cP}(m)&= &F_{\cP}(m) - G_{\cP^{(-1)}}(m)  - \sum_{\cP'\triangleleft \cP,\  \cP'\ntrianglelefteq \cP^{(-1)} }G_{\cP'}(m) - \sum_{ \cP'\triangleleft \cP^{(-1)} }G_{\cP'}(m) \\
& = & F_{\cP}(m) - G_{\cP^{(-1)}}(m) - \sum_{ \cP'\triangleleft \cP^{(-1)} }G_{\cP'}(m) \\
& =& F_{\cP}(m) -F_{\cP^{(-1)}}(m) \  ,
\end{eqnarray*}

where  we used the definition of $G_{\cP}(m)$ and that, by induction,  $G_{P'}(m)=0$ for $P'$ such $P'\triangleleft \cP$ and   $P'\ntrianglelefteq \cP^{(-1)}$. Finally, since $Q_{2,0}=Q_{0,2}=P_{2}=P_0=0$, we deduce from (<ref>) that $F_{\cP}(m)= F_{\cP^{(-1)}}(m)$ so that $G_{\cP}(m)=0$.

We now turn to the second result. Let us apply the generalized Möbius inversion formula for posets <cit.> to obtain an explicit expression for $G_{\cP}(m)$:

G_(m)= ∑_'⊴ (-1)^||-|'| F_'(m)μ(,')  ,
where $\mu$ is the Möbius function for partitions. More precisely, for $\cP'\trianglelefteq \cP$ where $\cP$ has $t$ groups which respectively split into $s_1$,…, $s_t$ block in $\cP'$, we have $\mu(\cP,\cP')= (-1)^{|\cP|-|\cP'|}\prod_{r=1}^{t}(s_r-1)!$ .

We denote $\kappa$ the number of groups of $\cP$ of size larger to one and, without loss of generality, we denote these groups $\cP_1,\ldots, \cP_\kappa$. Writing $\cG_{\cP}$ as a polynomial of $|\cP|$ variables, we then deduce from (<ref>) that

\begin{eqnarray}
\lefteqn{G_{\cP}[x_1,\ldots, x_{|\cP|}]}&& \nonumber \\ \nonumber
&=&  \left(\prod_{l=\kappa+1}^{|\cP|} x_l
\right)\sum_{\underline{\cP'_1} \trianglelefteq \cP_1}
\sum_{\underline{\cP'_2}\trianglelefteq \cP_2}
\ldots \sum_{\underline{\cP'_\kappa}\trianglelefteq \cP_\kappa}
(-1)^{t-\sum_{l=1}^{\kappa}|\underline{\cP'_l|}}\prod_{l=1}^{\kappa} (\underline{|\cP'_l|}-1)!\\
&& \cdot \left[\prod_{l=1}^\kappa  x_l^{|\cP_l|} + \prod_{l=1}^{\kappa}\prod_{\cQ \in \underline{\cP'_l}} \left[ x_l^{|\cQ|} + Q_{|\cQ\cap [2k]|,|\cQ\cap [2k+1:4k]|}(x_l)\right]  \right.\nonumber \\
&-& \left.  \prod_{l=1}^{\kappa}\prod_{\cQ \in \underline{\cP'_l}} \left[  x_l^{|\cQ|}+ x_l^{|\cQ\cap [2k]|}P_{|\cQ\cap [2k+1:4k]|}(x_l) \right]
-   \prod_{l=1}^{\kappa}\prod_{\cQ \in \underline{\cP'_l}} \left[  (x_l^{|\cQ|}+ x_l^{|\cQ\cap [2k+1:4k]|}P_{|\cQ\cap [2k]|}(x_l) \right]  \right]\ . \nonumber \\ \label{eq:expression_G_P}
\end{eqnarray}

where we consider any finer partition $\cP'\trianglelefteq \cP$ as a combination of $t$ partitions of the groups $\cP_1,\ldots, \cP_t$. We now prove that, for
$r=1,\ldots, t$, the maximum degree of $x_l$ in  $G_{\cP}$ is at most $|\cP_r|-2$ and is at most $|\cP_r|-3$ when $\cP_l\subset [2k]$ or $\cP_r\subset [2k+1,4k]$. Without loss of generality, we fix $r=1$. We only have to consider monomials with degree $|\cP_1|$ in $x_1$ as there is no monomial of degree $|\cP_1|-1$ in $x_1$ and no monomial of degree $|\cP_1|-2$ in $x_1$ when  $\cP_1\subset [2k]$ or $\cP_1\subset [2k+1,4k]$. Gathering all the monomials in $G_{\cP}$ of degree $|\cP_1|$ in $x_1$,  we arrive at
x_1^|_1|[∑_'_1 ⊴_1 (-1)^1-|'_1| (|'_1|-1)! ] [∏_l=κ+1^|| x_l] Z  ;

Z   :=    ∑_'_2 ⊴_2 …∑_'_κ ⊴_κ∏_l=2^κ (-1)^1-|'_l|(|'_l|-1)!  [∏_l=2^κx_l^|_l| + ∏_l=1^κ∏_∈'_l [ x_l^|| + Q_|∩[2k]|,|∩[2k+1:4k]|(x_l)]  .

- ∏_l=2^κ∏_∈'_l [  x_l^||+ x_l^|∩[2k]|P_|∩[2k+1:4k]|(x_l) ]
-   .  ∏_l=2^κ∏_∈'_l [  (x_l^||+ x_l^|∩[2k+1:4k]|P_|∩[2k]|(x_l) ]  ] .
Finally, we need to compute  $M_{\cP_1}:= \sum_{\underline{\cP'_1} \trianglelefteq \cP_1} (-1)^{1-|\underline{\cP'_1}|} (|\underline{\cP'_1}|-1)!$. Applying again the generalized inverse Möbius inverse formula for posets with the constant functional $A_{\cP'}=1$ for any partition $\cP'$ of $\cP_1$, we conclude that $M_{\cP_1}=0$. As a consequence, the degree of $G_P$ in $x_1$ is at most $|\cP_1|-2$ and is at most $\cP_1-3$ if $\cP_1\subset [2k]$ or $\cP_1\subset [2k+1,4k]$.

It follows from (<ref>) that $G_{\cP}$ decomposes into a sum of at most $(4k)^{4k}$ – upper bound for the number of sub-partitions– sum of four polynomials (see the two last lines in (<ref>)). Each of these four polynomial decomposes into at most $2^{2k}$ monomials. Finally, it follows from Lemma <ref> that the coefficient associated to each of these monomials is smaller or equal $(4k-1)!(c\|E\|_{\psi_2})^{4k}(4k)^{4k+2}$.

\[
\sum_{D\in \mathrm{Deg}(\cP)} |\alpha_{D,\cP}| \leq 4\cdot 2^{2k} (4k)^{12k+2} (c\|E\|_{\psi_2})^{4k}\leq (c'\|E\|_{\psi_2})^{4k}k^{12k+2}\enspace .
\]

§.§ Proof of Corollary <ref>

The proof follows the same steps as for Corollary <ref>. First we observe that $\|\bA\|_{\infty}\leq \|\bA\|_{2k}$ so that

\[
\E\left[\left(U_k - \|\bA\|_{2k}^{2k}\right)^2\right]\leq   (c\|E\|_{\psi_2}k)^{c'k} \left[   (pq)^{k} +  pq \|\bA\|_{2k}^{4k-4}+ q\|\bA\|_{2k}^{4k-2}\right]
\]

We consider two cases depending on $\|\bA\|_{2k}$. If  $\|\bA\|_{2k} \leq  (pq)^{1/4}$, then the above risk bound simplifies in
$\E\left[|(U_k-\|\bA\|_{2k}^{2k})^2\right]\leq   3(c\|E\|_{\psi_2}k)^{c'k}(pq)^k$. Then, together with the inequality $|x^{1/(2k)}-y^{1/(2k)}|\leq |x-y|^{1/(2k)}$ and Hölder's inequality, we arrive at

\[ \E\left[|(U_k)_+^{1/(2k)}- \|\bA\|_{2k}|\right]\leq \E\left[|U_k- \|\bA\|^{2k}_{2k}|\right]^{1/2k}\leq c''(\|E\|_{\psi_2}k)^{c_3} (pq)^{1/4}\enspace .
\]

Turning to the case where  $\|\bA\|_{2k} \geq  (pq)^{1/4}$,
we use   $|(1+x)^{1/(2k)}-1|\leq  2|x|$ for any $x\geq - 1/2$, we have

\begin{eqnarray*}
\E\left[|(U_k)_+^{1/(2k)}- \|\bA\|_{2k}|\right]&=&\E\left[ \|\bA\|_{2k} \big|[U_k/\|\bA\|^{2k}_{2k}]^{\frac{1}{2k}} - 1\big|\right] \nonumber\\
&\leq & \|\bA\|_{2k}\P\left[U_k\leq \|\bA\|_{2k}^{2k}/2\right]+ 2\|\bA\|^{1-2k}_{2k}\E\left[|U_k- \|\bA\|_{2k}^{2k}|\right] \nonumber \\
&\leq & \|\bA\|_{2k}\left[4\frac{\E\left[(U_k- \|\bA\|_{2k}^{2k})^2\right]}{\|\bA\|^{4k}_{2k}}+ 2\frac{\E\left[(U_k- \|\bA\|_{2k}^{2k})^2\right]^{1/2}}{\|\bA\|^{2k}_{2k}} \right]\nonumber \\
&\lesssim &  (c\|E\|_{\psi_2}k)^{c'k} \left[\frac{(pq)^k}{\|\bA\|^{4k-1}_{2k}}+ \frac{(pq)^{k/2}}{\|\bA\|^{2k-1}_{2k}}+ \frac{pq+\sqrt{pq}\|\bA\|_{2k}}{\|\bA\|_{2k}^{2}}+  \frac{q}{\|\bA\|_{2k}}+\sqrt{q} \right] \nonumber
\\
&\lesssim & (c\|E\|_{\psi_2}k)^{c'k} (pq) ^{1/4}
\ .
\end{eqnarray*}

The result follows.

§.§ Proofs of Propositions <ref> and <ref>

As in proof of  Proposition <ref>, we start from (<ref>)

\[
\big|\|\bY^T\bY\|_{\infty} - p - \|\bA^T\bA\|_{\infty}\big|\leq   2\|\bA^T\bE\|_{\infty}+ \|\bE^T\bE - p\bI\|_{\infty} \leq   2\|\bA\|_{\infty}\|\bPi_{I(\bA)}\bE\|_{\infty}+ \|\bE^T\bE - p\bI\|_{\infty} \enspace .
\]

We control $\|\bE^T\bE - p\bI\|_{\infty}$ using (<ref>) and $\|\bPi_{I(\bA)}\bE\|_{\infty}$ as in Lemma <ref>. The remainder of the proof is as in the proof of Proposition <ref> and we obtain

\[
\mathbb{E}\cro{|(\|\bY^T \bY\|_{\infty}-p)_+^{1/2} - \|\bA\|_{\infty}|} \leq c_{\|E\|_{\psi_2}}(pq)^{1/4}\ .
\]

We argue as in the proof of Proposition <ref>. Starting from (<ref>), we have
|T^s_s - ^s_s|
≤    2^s/2s ∑_i=1^q[Π_I()^2_∞+ ^T- p _q_∞+ 2 σ_i()Π_I()_∞]σ^s-2_i()
+ 3^s/2-1[Π_I()^s_∞+ ^T- p _q^s/2_∞+ 2^s/2 σ^s/2_i()Π_I()^s/2_∞] ,
and we only have to control moments of $\|\Pi_{I(\bA)}\bE\|_{\infty}$ and $\|\bE^T\bE- p \bI_q\|_{\infty}$.

There exists a numerical constant $c>0$, such that for any $t>0$, we have

[Π_I()_∞ ≤cE_ψ_2 [√(q)+ √(t)]]≥1- e^-t .

Next, we turn to the control of $\|\bE^T\bE -p \bI_q\|_{\infty}$ which is a straightforward application of Theorem 9 in [20]. There exists a constant $c_{\|E\|_{\psi_2}}$ that only depends on $\|E\|_{\psi_2}$ such that for any $t$,

[^T-p _q_∞≤c_E_ψ_2[√(pq)+ q + √(pt)+ t]]≥1-e^-t .
Integrating the deviation bounds of (<ref>) and (<ref>), we arrive as in (<ref>) and (<ref>)

\[
\E\left[|T^s_s - \|\bA\|^s_s|\right]\leq c^s_{\|E\|_{\psi_2}} \left[q[(p\vee s)(q\vee s)]^{s/4}+ \sqrt{q}\|\bA\|^{s-1}_{s-1}+ \1_{s\geq 2}\sqrt{pq}\|\bA\|_{s-2}^{s-2}\right]\ .
\]

Then, the remainder of the proof is exactly as in the proof of Proposition <ref>.

We provide a simple but pedestrian proof based on $\epsilon$-nets. We start from

Π_I()_∞ = sup_u∈I(), |u|≤1  sup_v∈ℝ^q: |v|_2≤1 u^T v
Consider an $1/4$-net $\mathcal{N}_1$ of the unit ball of $I(\bA)$ and a $1/4$-net $\mathcal{N}_2$ of the unit ball of $\mathbb{R}^q$.
Let $u^*$ and $v^*$ be any maximizer of the supremum in (<ref>) and let $u'$ and $v'$ denote the corresponding closest points in $\mathcal{N}_1$ and $\mathcal{N}_2$.  Then, we have

Π_I()_∞     =    (u^*)^T v^* = (u')^T v'+ (u^*- u')^Tv' + (u^*)^T (v^*-v')
≤    sup_u∈_1sup_v∈_2u^T v  + 1/2Π_I()_∞
so that

\[
\|\Pi_{I(\bA)}\bE\|_{\infty}\leq 2 \sup_{u\in \cN_1}\sup_{v\in \cN_2}u^T \bE v
\]

Since the mean zero random variable $u^T \bE v$ is sub-Gaussian with sub-Gaussian norm $\|E\|_{\psi_2}$, we deduce that, with probability higher than $1- e^{-t}$, one has

\[
\|\Pi_{I(\bA)}\bE\|_{\infty}\leq c\|E\|_{\psi_2}\left[\sqrt{t}+ \sqrt{\log(|\cN_1|)+\log(|\cN_2|) }\right]\ ,
\]

Finally, we conclude by observing that $\log(|\cN_2|)+\log(|\cN_1|)\leq c'q$ since the $\epsilon$-covering number of a $d$-dimensional unit ball is at most $d\log(3/\epsilon)$.

§ TECHNICAL INEQUALITIES

For bounding the singular values of $\bE$, we shall rely on the following results (taken e.g. from  [11]).

Let  $\bE$ be a $p \times q$ matrix  whose entries are independent standard Gaussian random variables. Then,

\[ \mathbb{E}\cro{|\sigma_1(\bE)|}\leq \pa{\sqrt{p} + \sqrt{q}}\enspace . \]

Let  $\bE$ be a $p \times q$ matrix  whose entries are independent standard Gaussian random variables. Then,  for any $t > 0$, we have

\begin{equation}
\max\ac{\mathbb{P}\pa{\sigma_1\pa{\boldsymbol{\bE}}\geq \sqrt{p} + \sqrt{q} + \sqrt{2t}},\mathbb{P}\pa{\sigma_q \pa{\bE}\leq\sqrt{p} - \sqrt{q} - \sqrt{2t} }} \leq e^{-t}\ .
\end{equation}

The following lemma is taken from [23]

Let $Z$ be distributed as $\chi^2(p)$ random variable. For any $t>0$, we have

\[
\P[Z\geq p + 2\sqrt{pt}+ 2t ]\leq e^{-t}\ .
\]

[1]
Greg W Anderson, Alice Guionnet, and Ofer Zeitouni.
An introduction to random matrices, volume 118.
Cambridge university press, 2010.

[2]
Maria-Florina Balcan, Yi Li, David P Woodruff, and Hongyang Zhang.
Testing matrix rank, optimally.
In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 727–746. Society for Industrial and Applied
Mathematics, 2019.

[3]
Serge Bernstein.
Sur la valeur asymptotique de la meilleure approximation des
fonctions analytiques.
Communications de la Société mathématique de
Kharkow, 13(6):263–273, 1913.

[4]
Serge Bernstein.
Sur la meilleure approximation de $|x|^{p}$ par des polynômes de
degrés très élevés.
Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya,
2(2):169–190, 1938.

[5]
Rajendra Bhatia.
Matrix analysis, volume 169.
Springer Science & Business Media, 2013.

[6]
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.
Concentration inequalities.
Oxford University Press, Oxford, 2013.
A nonasymptotic theory of independence, With a foreword by Michel

[7]
T. Tony Cai and Mark G. Low.
Testing composite hypotheses, Hermite polynomials and optimal
estimation of a nonsmooth functional.
Ann. Statist., 39(2):1012–1041, 2011.

[8]
Sourav Chatterjee.
Matrix estimation by universal singular value thresholding.
The Annals of Statistics, 43(1):177–214, 2015.

[9]
Olivier Collier, Laëtitia Comminges, and Alexandre B Tsybakov.
Minimax estimation of linear and quadratic functionals on sparsity
The Annals of Statistics, 45(3):923–958, 2017.

[10]
Romain Couillet and Merouane Debbah.
Random matrix methods for wireless communications.
Cambridge University Press, 2011.

[11]
K. R. Davidson and S. J. Szarek.
Local operator theory, random matrices and Banach spaces.
In Handbook of the geometry of Banach spaces, Vol. I, pages
317–366. North-Holland, Amsterdam, 2001.

[12]
David Donoho and Matan Gavish.
Minimax risk of matrix denoising by singular value thresholding.
The Annals of Statistics, 42(6):2413–2440, 2014.

[13]
David L Donoho and Michael Nussbaum.
Minimax quadratic estimation of a quadratic functional.
Journal of Complexity, 6(3):290–323, 1990.

[14]
Matan Gavish and David L Donoho.
The optimal hard threshold for singular values is 4/$\sqrt{3}$.
IEEE Transactions on Information Theory, 60(8):5040–5053,

[15]
Yanjun Han, Jiantao Jiao, and Rajarshi Mukherjee.
On estimation of $l_{r}$-norms in gaussian white noise models.
Probability Theory and Related Fields, 177(3):1243–1294, 2020.

[16]
Yanjun Han, Jiantao Jiao, and Tsachy Weissman.
Local moment matching: A unified methodology for symmetric functional
estimation and distribution estimation under wasserstein distance.
In Conference On Learning Theory, pages 3189–3221. PMLR, 2018.

[17]
Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman.
Minimax estimation of functionals of discrete distributions.
IEEE Transactions on Information Theory, 61(5):2835–2885,

[18]
Lou Jost.
Entropy and diversity.
Oikos, 113(2):363–375, 2006.

[19]
Ashish Khetan and Sewoong Oh.
Spectrum estimation from a few entries.
The Journal of Machine Learning Research, 20(1):718–772, 2019.

[20]
Vladimir Koltchinskii and Karim Lounici.
Concentration inequalities and moment bounds for sample covariance
Bernoulli, 23(1):110–133, 2017.

[21]
Weihao Kong and Gregory Valiant.
Spectrum estimation from samples.
The Annals of Statistics, 45(5):2218–2247, 2017.

[22]
Serge Lang.
Graduate Texts in Mathematics: Algebra.
Springer, 2002.

[23]
B. Laurent and P. Massart.
Adaptive estimation of a quadratic functional by model selection.
Annals of Statistics, 28(5):1302–1338, 2000.

[24]
Oleg Lepski, Arkady Nemirovski, and Vladimir Spokoiny.
On estimation of the L r norm of a regression function.
Probability theory and related fields, 113(2):221–253, 1999.

[25]
Gérard Letac and Hélène Massam.
All invariant moments of the Wishart distribution.
Scandinavian Journal of Statistics, 31(2):295–318, 2004.

[26]
Yi Li, Huy L Nguyen, and David P Woodruff.
On sketching matrix norms and the top singular vector.
In Proceedings of the twenty-fifth annual ACM-SIAM symposium on
Discrete algorithms, pages 1562–1581. Society for Industrial and Applied
Mathematics, 2014.

[27]
Raj Rao Nadakuditi.
Optshrink: An algorithm for improved low-rank signal matrix
denoising by optimal, data-driven singular value shrinkage.
IEEE Transactions on Information Theory, 60(5):3002–3018,

[28]
Ricardo Pachón and Lloyd N Trefethen.
Barycentric-remez algorithms for best polynomial approximation in the
chebfun system.
BIT Numerical Mathematics, 49(4):721, 2009.

[29]
Yury Polyanskiy and Yihong Wu.
Dualizing le cam's method for functional estimation, with
applications to estimating the unseens.
arXiv preprint arXiv:1902.05616, 2019.

[30]
MA Qazi and QI Rahman.
Some coefficient estimates for polynomials on the unit interval.
Serdica Mathematical Journal, 33(4):449p–474p, 2007.

[31]
Eugene Y Remez.
Sur la détermination des polynômes d’approximation de
degré donnée.
Comm. Soc. Math. Kharkov, 10(196):41–63, 1934.

[32]
Theodore Rivlin.
Chebyshev polynomials. from approximation theory to algebra and
number theory. 1990.
Pure Appl. Math.(NY), 1990.

[33]
Olivier Roy and Martin Vetterli.
The effective rank: A measure of effective dimensionality.
In 2007 15th European Signal Processing Conference, pages
606–610. IEEE, 2007.

[34]
Andrey A Shabalin and Andrew B Nobel.
Reconstruction of a low-rank matrix in the presence of Gaussian
Journal of Multivariate Analysis, 118:67–76, 2013.

[35]
Richard P Stanley.
Enumerative combinatorics volume 1 second edition.
Cambridge studies in advanced mathematics, 2011.

[36]
Aleksandr Filippovich Timan.
Theory of approximation of functions of a real variable,
volume 34.
Elsevier, 2014.

[37]
Alexandre B. Tsybakov.
Introduction to nonparametric estimation.
Springer Series in Statistics. Springer, New York, 2009.
Revised and extended from the 2004 French original, Translated by
Vladimir Zaiats.

[38]
Pascal Vallet, Philippe Loubaton, and Xavier Mestre.
Improved subspace estimation for multivariate observations of high
dimension: the deterministic signals case.
IEEE Transactions on Information Theory, 58(2):1043–1068,

[39]
Roman Vershynin.
High-dimensional probability: An introduction with applications
in data science, volume 47.
Cambridge university press, 2018.

[40]
Yihong Wu and Pengkun Yang.
Minimax rates of entropy estimation on large alphabets via best
polynomial approximation.
IEEE Transactions on Information Theory, 62(6):3702–3720,

[41]
Yihong Wu and Pengkun Yang.
Polynomial methods in statistical inference: theory and practice.
arXiv preprint arXiv:2104.07317, 2021.