$\displaystyle=\sum_{t=1}^{T-2}\left(u_{t+1}^{2}+2u_{t+1}\sum_{r=t+1}^{T-1}u_{r+1}\theta^{r-t}+\left(\sum_{r=t+1}^{T-1}u_{r+1}\theta^{r-t}\right)^{2}\right)+u_{T}^{2}$
$\displaystyle\leq
1+\sum_{t=1}^{T-2}\sum_{r=t+1}^{T-1}(u_{t+1}^{2}+u_{r+1}^{2})\theta^{r-t}+\theta^{2}\sum_{t=1}^{T-2}\left(\sum_{r=t}^{T-2}u_{r+2}\theta^{r-t}\right)^{2},$

where the third line follows from $\sum_{t=1}^{T}u_{t}^{2}\leq 1$ and an
elementary inequality $2ab\leq a^{2}+b^{2}$. Also, by the induction
hypothesis,

$\sum_{t=1}^{T-2}\left(\sum_{r=t}^{T-2}u_{r+2}\theta^{r-t}\right)^{2}\leq\frac{1}{(1-\theta)^{2}}.$

In addition,

$\sum_{t=1}^{T-2}\sum_{r=t+1}^{T-1}(u_{t+1}^{2}+u_{r+1}^{2})\theta^{r-t}\leq
2\sum_{l=1}^{T-2}\sum_{t=1}^{T}\theta^{l}u_{t}^{2}\leq\frac{2\theta}{1-\theta}.$

Hence,

$\sum_{t=1}^{T-1}\left(\sum_{r=t}^{T-1}u_{r+1}\theta^{r-t}\right)^{2}\leq
1+\frac{2\theta}{1-\theta}+\frac{\theta^{2}}{(1-\theta)^{2}}=\frac{1}{(1-\theta)^{2}},$

which completes the induction argument and thus gives the asserted claim for
all $T\geq 2$. $\blacksquare$

##  Appendix B Proofs for Remaining Results from Main Text

###### Proof of Theorem 3.4.

By Theorem 3.2, $\hat{\beta}=\hat{\beta}^{0}$ with probability $1-o(1)$ for
$\hat{\beta}^{0}$ appearing in (13). In turn, by the Frisch-Waugh-Lovell
theorem,

$\hat{\beta}^{0}=\left(\sum_{i=1}^{N}\sum_{t=1}^{T}\check{x}_{it}\check{x}_{it}^{\prime}\right)^{-1}\left(\sum_{i=1}^{N}\sum_{t=1}^{T}\check{x}_{it}y_{it}\right),$

and so

$\displaystyle\sqrt{NT}(\hat{\beta}^{0}-\beta)$
$\displaystyle=\left(\frac{1}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}\check{x}_{it}\check{x}_{it}^{\prime}\right)^{-1}\left(\frac{1}{\sqrt{NT}}\sum_{i=1}^{N}\sum_{t=1}^{T}\check{x}_{it}v_{it}\right)\to_{D}N(\check{\Sigma}^{-1}\Omega\check{\Sigma}^{-1})$

by Slutsky’s lemma and Assumption 3.9. The asserted claim follows.
$\blacksquare$

###### Proof of Theorem 4.1.

The asserted claim follows from the same arguments as those in the proofs of
Theorems 3.1–3.4 as long as we can show that there exists a constant $C>0$
such that $\|\mathring{\rho}_{im}\|\vee|\mathring{\alpha}_{\gamma t}^{m}|\leq
C$ for all $i=1,\dots,N$, $\gamma=1,\dots,G$, $t=1,\dots,T$, and
$m=1,\dots,2M$, which would correspond to Assumption 3.3 in the context of
dynamic model. To do so, observe that

$\displaystyle\max_{1\leq m\leq 2M}\|\mathring{\rho}_{im}\|$
$\displaystyle\leq\max_{1\leq m\leq M}(\|\rho_{im}\|+|\rho_{im}^{y}|)$
$\displaystyle\leq\max_{1\leq m\leq
M}(\|\rho_{im}\|+1+|\rho_{im}^{\prime}\beta|)\leq 1+C_{3}(1+\|\beta\|)$

for all $i=1,\dots,N$ by Assumption 4.5. Also,

$\max_{1\leq m\leq 2M}|\mathring{\alpha}_{\gamma t}^{m}|\leq\max_{1\leq m\leq
M}\left(|\alpha_{\gamma t}^{m}|+\left|\sum_{r=0}^{t-2}\theta^{r}\alpha_{\gamma
t-r-1}^{m}\right|\right)\leq C_{4}\left(1+\frac{1}{1-\theta}\right)$

by Assumption 4.6. Therefore, the asserted claim follows if we set

$C=1+C_{3}(1+\|\beta\|)+C_{4}\left(1+\frac{1}{1-\theta}\right).$

This completes the proof of the theorem. $\blacksquare$

###### Proof of Theorem 4.2.

We first prove (19). By construction of $\hat{\Sigma}$ and $\hat{S}$, it
suffices to show that

$\lambda^{b}_{1}+\dots+\lambda^{b}_{2GM+2}=b^{\prime}\Sigma
b+S^{\prime}b+L+O_{P}\left(\frac{1}{T\wedge N}+\sqrt{\frac{\log
d}{NT}}\right)$

uniformly over $b\in\overline{\mathcal{B}}=\\{0_{d}\\}\cup\\{e_{k}\colon
k=1,\dots,d\\}\cup\\{e_{k}+e_{l}\colon k,l=1,\dots,d\\}$. To do so, we proceed
by appropriately modifying the proof of Theorem 3.1. Throughout, we use the
same notations as in the proof of Theorem 3.1. We have

$\displaystyle\textrm{tr}(R)$
$\displaystyle=-\frac{2}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}\Big{\\{}(\beta-b)^{\prime}z_{it}z_{it}(\beta-b)+v_{it}^{2}+2v_{it}z_{it}^{\prime}(\beta-b)\Big{\\}}$
$\displaystyle=-\frac{2}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}\Big{\\{}(\beta-b)^{\prime}z_{it}z_{it}(\beta-b)+v_{it}^{2}\Big{\\}}+O_{P}\left(\sqrt{\frac{\log
d}{NT}}\right)$

uniformly over $b\in\overline{\mathcal{B}}$ since

$\left|\frac{1}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}v_{it}z_{it}^{\prime}(\beta-b)\right|\leq\left\|\frac{1}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}v_{it}z_{it}\right\|_{\infty}\|\beta-b\|_{1}\leq(C_{\beta}+2)O_{P}\left(\sqrt{\frac{\log
d}{NT}}\right)$

uniformly over $b\in\overline{\mathcal{B}}$. Thus,

$\displaystyle\textrm{tr}(A_{0})$
$\displaystyle=\frac{2}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}\Big{\\{}(\beta-b)^{\prime}z_{it}z_{it}(\beta-b)+v_{it}^{2}\Big{\\}}+O_{P}\left(\sqrt{\frac{\log
d}{NT}}\right)$ $\displaystyle=b^{\prime}\Sigma
b+S^{\prime}b+L+O_{P}\left(\sqrt{\frac{\log d}{NT}}\right)$

uniformly over $b\in\overline{\mathcal{B}}$ since

$\displaystyle\left|\frac{2}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}(\beta-b)^{\prime}z_{it}z_{it}^{\prime}(\beta-b)-(\beta-b)^{\prime}\Sigma(\beta-b)\right|$
$\displaystyle\qquad\leq\left\|\frac{1}{NT}\sum_{i=1}^{N}\sum_{t=1}^{T}z_{it}z_{it}^{\prime}-\Sigma\right\|_{\infty}\|\beta-b\|_{1}^{2}\leq(C_{\beta}+2)^{2}O_{P}\left(\sqrt{\frac{\log
d}{NT}}\right)$

uniformly over $b\in\overline{\mathcal{B}}$. Also,

$\left\|\frac{1}{NT}\sum_{t=1}^{T}V_{t}V_{t}^{\prime}\right\|=O_{P}\left(\frac{1}{T\wedge
N}\right)$

as in the proof of Theorem 3.1. Further, to prove that

$\left\|\frac{1}{NT}\sum_{t=1}^{T}Z_{bt}Z_{bt}^{\prime}\right\|=O_{P}\left(\frac{1}{T\wedge
N}\right)$ (55)

uniformly over $b\in\overline{\mathcal{B}}$, where we denoted
$Z_{bt}=(z_{1t}^{\prime}(\beta-b),\dots,z_{Nt}^{\prime}(\beta-b))^{\prime}$,
we have
$\|u^{\prime}z_{i}(\beta-b)\|_{\psi_{2}}\leq\|u^{\prime}z_{i}\beta\|_{\psi_{2}}+\|u^{\prime}z_{i}b\|_{\psi_{2}}\leq
C_{z}+2C_{2}$ uniformly over
$u=(u_{1},\dots,u_{T})^{\prime}\in\mathcal{S}^{T}$ and
$b\in\overline{\mathcal{B}}$ by our assumptions, where we denoted
$z_{i}=(z_{i1},\dots,z_{iT})^{\prime}$ for all $i=1,\dots,N$. Thus, denoting
$\mathcal{Z}_{b}=(z_{1}(\beta-b),\dots,z_{N}(\beta-b))^{\prime}$, we have

$\mathrm{P}\left(\max_{u\in\mathcal{N}}\left|u^{\prime}\left(\frac{\mathcal{Z}_{b}^{\prime}\mathcal{Z}_{b}}{N}-\mathbb{E}\left[\frac{\mathcal{Z}_{b}^{\prime}\mathcal{Z}_{b}}{N}\right]\right)u\right|\geq\epsilon\right)\leq
2\times 9^{T}\times\exp(-c(\epsilon\wedge\epsilon^{2})N)$

for all $b\in\overline{\mathcal{B}}$, where $\mathcal{N}$ is the same as in
the proof of Theorem 3.1 and $c$ is a constant depending only on $C_{z}$ and
$C_{2}$. Hence, by the union bound,

$\mathrm{P}\left(\max_{b\in\overline{\mathcal{B}}}\max_{u\in\mathcal{N}}\left|u^{\prime}\left(\frac{\mathcal{Z}_{b}^{\prime}\mathcal{Z}_{b}}{N}-\mathbb{E}\left[\frac{\mathcal{Z}_{b}^{\prime}\mathcal{Z}_{b}}{N}\right]\right)u\right|\geq\epsilon\right)\leq(1+d+d^{2})\times
2\times 9^{T}\times\exp(-c(\epsilon\wedge\epsilon^{2})N).$

Setting here $\epsilon=c^{-1}(\log 9)(T/N)+1$, we obtain

$\mathrm{P}\left(\max_{b\in\overline{\mathcal{B}}}\max_{u\in\mathcal{N}}\left|u^{\prime}\left(\frac{\mathcal{Z}_{b}^{\prime}\mathcal{Z}_{b}}{N}-\mathbb{E}\left[\frac{\mathcal{Z}_{b}^{\prime}\mathcal{Z}_{b}}{N}\right]\right)u\right|\geq
c^{-1}(\log 9)(T/N)+1\right)\\\ \leq 2(1+d+d^{2})\exp(-cN)\to 0$

because $\log d=o(N)$. We thus obtain (55) by the same arguments as those in
the proof of Theorem 3.1. Repeating the remaining arguments of the proof of
Theorem 3.1, we obtain (19).

Next, we prove that (20) and (21) imply (22). To do so, we assume for the rest
of the proof that both (20) and (21) are satisfied. Then, by the definition of
$\hat{\beta}_{\lambda}$,

$\hat{\beta}_{\lambda}^{\prime}\hat{\Sigma}\hat{\beta}_{\lambda}+\hat{S}^{\prime}\hat{\beta}_{\lambda}+\lambda\|\hat{\beta}_{\lambda}\|_{1}\leq\beta^{\prime}\hat{\Sigma}\beta+\hat{S}^{\prime}\beta+\lambda\|\beta\|_{1}.$

Also,

$(\hat{\beta}_{\lambda}-\beta)^{\prime}\hat{\Sigma}(\hat{\beta}_{\lambda}-\beta)=\hat{\beta}_{\lambda}^{\prime}\hat{\Sigma}\hat{\beta}_{\lambda}-\beta^{\prime}\hat{\Sigma}\beta+2(\beta-\hat{\beta}_{\lambda})^{\prime}\hat{\Sigma}\beta.$

Taking the sum of these two displays, we obtain

$\displaystyle(\hat{\beta}_{\lambda}-\beta)^{\prime}\hat{\Sigma}(\hat{\beta}_{\lambda}-\beta)$
$\displaystyle=(\hat{S}+2\hat{\Sigma}\beta)^{\prime}(\beta-\hat{\beta}_{\lambda})+\lambda\|\beta\|_{1}-\lambda\|\hat{\beta}_{\lambda}\|_{1}$
$\displaystyle\leq\|\hat{S}+2\hat{\Sigma}\beta\|_{\infty}\|\hat{\beta}_{\lambda}-\beta\|_{1}+\lambda\|\beta\|_{1}-\lambda\|\hat{\beta}_{\lambda}\|_{1}$
$\displaystyle\leq\Big{(}\|\hat{S}-S\|_{\infty}+2C_{\beta}\|\hat{\Sigma}-\Sigma\|_{\infty}\Big{)}\|\hat{\beta}_{\lambda}-\beta\|_{1}+\lambda\|\beta\|_{1}-\lambda\|\hat{\beta}_{\lambda}\|_{1},$

where the third line follows by recalling that $S+2\Sigma\beta=0$ and
$\|\beta\|_{1}\leq C_{\beta}$. Therefore, by (20), we have

$(\hat{\beta}_{\lambda}-\beta)^{\prime}\hat{\Sigma}(\hat{\beta}_{\lambda}-\beta)\leq(\lambda/c_{\lambda})\|\hat{\beta}_{\lambda}-\beta\|_{1}+\lambda\|\beta\|_{1}-\lambda\|\hat{\beta}_{\lambda}\|_{1}.$
(56)

Further, denote $\delta=\hat{\beta}_{\lambda}-\beta$,
$\mathcal{T}=\\{k=1,\dots,d\colon\beta_{k}\neq 0\\}$, and
$\mathcal{T}^{c}=\\{1,\dots,d\\}\setminus\mathcal{T}$. Also, let
$\delta_{\mathcal{T}}=(\delta_{\mathcal{T}1},\dots,\delta_{\mathcal{T}d})^{\prime}$
be a $d\times 1$ vector such that
$\delta_{\mathcal{T}k}=\delta_{k}1\\{k\in\mathcal{T}\\}$ and, similarly, let
$\delta_{\mathcal{T}^{c}}=(\delta_{\mathcal{T}^{c}1},\dots,\delta_{\mathcal{T}^{c}d})^{\prime}$
be a $d\times 1$ vector such that
$\delta_{\mathcal{T}^{c}k}=\delta_{k}1\\{k\in\mathcal{T}^{c}\\}$. Then, given
that
$(\hat{\beta}_{\lambda}-\beta)^{\prime}\hat{\Sigma}(\hat{\beta}_{\lambda}-\beta)\geq
0$, it follows from (56) that

$\displaystyle 0$
$\displaystyle\leq(1/c_{\lambda})\|\hat{\beta}_{\lambda}-\beta\|_{1}+\|\beta\|_{1}-\|\hat{\beta}_{\lambda}\|_{1}$
$\displaystyle\leq(1/c_{\lambda})(\|\delta_{\mathcal{T}}\|_{1}+\|\delta_{\mathcal{T}^{c}}\|_{1})+\|\delta_{\mathcal{T}}\|_{1}-\|\delta_{\mathcal{T}^{c}}\|_{1},$

where the second inequality follows from observing that
$\beta_{k}=\beta_{k}1\\{k\in\mathcal{T}\\}$ for all $k=1,\dots,d$. Therefore,
$(1-1/c_{\lambda})\|\delta_{\mathcal{T}^{c}}\|_{1}\leq(1+1/c_{\lambda})\|\delta_{\mathcal{T}}\|_{1},$
and so
$\|\delta_{\mathcal{T}^{c}}\|_{1}\leq\bar{c}_{\lambda}\|\delta_{\mathcal{T}}\|_{1}$.
Thus,

$\displaystyle\delta^{\prime}\hat{\Sigma}\delta$
$\displaystyle=\delta^{\prime}\Sigma\delta-\delta^{\prime}(\Sigma-\hat{\Sigma})\delta\geq
c_{\Sigma}\|\delta\|^{2}-\|\delta\|_{1}^{2}\|\hat{\Sigma}-\Sigma\|_{\infty}$
$\displaystyle\geq
c_{\Sigma}\|\delta\|^{2}-(1+\bar{c}_{\lambda})^{2}\|\delta_{\mathcal{T}}\|_{1}^{2}\|\hat{\Sigma}-\Sigma\|_{\infty}$
$\displaystyle\geq
c_{\Sigma}\|\delta\|^{2}-s(1+\bar{c}_{\lambda})^{2}\|\delta\|^{2}\|\hat{\Sigma}-\Sigma\|_{\infty}\geq
c_{\Sigma}\|\delta\|^{2}/2$

by (21). Substituting this bound into (56), we obtain

$c_{\Sigma}\|\delta\|^{2}/2\leq\lambda(1+1/c_{\lambda})\|\delta_{\mathcal{T}}\|_{1}\leq\sqrt{s}\lambda(1+1/c_{\lambda})\|\delta\|.$

Rearranging this bound gives gives the second inequality in (22). To obtain
the first inequality in (22), observe that

$\|\delta\|_{1}=\|\delta_{\mathcal{T}}\|_{1}+\|\delta_{\mathcal{T}^{c}}\|_{1}\leq(1+\bar{c}_{\lambda})\|\delta_{\mathcal{T}}\|_{1}\leq\sqrt{s}(1+\bar{c}_{\lambda})\|\delta\|.$

This completes the proof of the theorem. $\blacksquare$

###### Proof of Theorem 4.3.

The proof is closely related to that of Theorem 3.1, with the main difference
is that we now have

$f_{it}=(\kappa_{i}+\omega_{i}(\beta-b))^{\prime}\phi_{t},\quad\text{for all
}i=1,\dots,N,\ t=1,\dots,T.$

This difference in turn requires us to change the calculation of the bound on
the number of non-zero eigenvalues of the matrix $A_{0}$. Recalling that
$F_{t}=(f_{1t},\dots,f_{Nt})^{\prime}$ for all $t=1,\dots,T$, we now have

$\sum_{t=1}^{T}F_{t}(F_{t}+Z_{t}+V_{t})^{\prime}=\sum_{t=1}^{T}\mathcal{K}\phi_{t}(F_{t}+Z_{t}+V_{t})^{\prime}=\mathcal{K}\sum_{t=1}^{T}\phi_{t}(F_{t}+Z_{t}+V_{t})^{\prime},$

where
$\mathcal{K}=(\kappa_{1}+\omega_{1}(\beta-b),\dots,\kappa_{N}+\omega_{N}(\beta-b))^{\prime}$
and $Z_{t}$ and $V_{t}$ are the same as in the proof of Theorem 3.1. Thus,
given that $\mathcal{K}$ is an $N\times J$ matrix, it follows that the rank of
the matrix $\sum_{t=1}^{T}F_{t}(F_{t}+Z_{t}+V_{t})^{\prime}$ is at most $J$.
Similarly, the rank of the matrix $\sum_{t=1}^{T}(Z_{t}+V_{t})F_{t}^{\prime}$
is also at most $J$, as the column rank coincides with the row rank. We have
thus replaced $GM$ in the proof of Theorem 3.1 by $J$. The rest of the proof
is the same as that of Theorem 3.1. $\blacksquare$

##  Appendix C Randomized Algorithm for Calculating Eigenvalues of Large
Matrices

To calculate the spectral estimator $\tilde{\beta}$ in Section 2, we had to
calculate $2GM+2$ largest in absolute value eigenvalues of the $N\times N$
matrix $A^{b}$. When $N$ is large, calculating these eigenvalues exactly may
be difficult. Fortunately, there exists a class of randomized algorithms that
allow to calculate these eigenvalues approximately with minimal efforts. In
this section, we describe one such algorithm. Our discussion here mostly
follows [22], where an interested reader can find several other related
algorithms.

For brevity of notation, suppose that we have an $N\times N$ symmetric matrix
$A$ and we would like to calculate its $k$ largest in absolute value
eigenvalues, $\lambda_{(1)},\dots,\lambda_{(k)}$, ordered so that
$|\lambda_{(1)}|\geq\dots\geq|\lambda_{(k)}|$. Consider the following
algorithm:

Randomized Algorithm for Calculating Eigenvalues.

Step 1: choose an oversampling parameter $p>0$, e.g. $p=5$ or $10$;

Step 2: set a multiplication parameter $q=[\log N]$;

Step 3: draw an $N\times(k+p)$ random matrix
$\Omega=\\{\Omega_{ij}\\}_{i,j=1}^{N,k+p}\stackrel{{\scriptstyle
iid}}{{\sim}}N(0,1)$;

Step 4: compute the $N\times(k+p)$ matrix $Y=A^{q+1}\Omega$;

Step 5: compute QR decomposition $Y=QR$ with $Q$ having orthonormal columns;

Step 6: compute the $(k+p)\times N$ matrix $B=Q^{\prime}A$;

Step 7: compute eigenvectors $\tilde{s}_{1},\dots,\tilde{s}_{k+p}$ of the
$(k+p)\times(k+p)$ matrix $BB^{\prime}$;

Step 8: compute $N\times 1$ vectors $s_{j}=B^{\prime}\tilde{s}_{j}$ for
$j=1,\dots,k+p$;

Step 9: compute
$\hat{\lambda}_{j}=\textrm{sign}(s_{j}^{\prime}As_{j})(\|B^{\prime}Bs_{j}\|/\|s_{j}\|)^{1/2}$
for $j=1,\dots,k+p$;

Step 10: order values $\hat{\lambda}_{1},\dots,\hat{\lambda}_{k+p}$ into
$\hat{\lambda}_{(1)},\dots,\hat{\lambda}_{(k+p)}$ so that
$|\hat{\lambda}_{(1)}|\geq\dots\geq|\hat{\lambda}_{(k+p)}|$;

Step 11: return $\hat{\lambda}_{(1)},\dots,\hat{\lambda}_{(k)}$.

The result of this algorithm is $k$ values
$\hat{\lambda}_{(1)},\dots,\hat{\lambda}_{(k)}$. These are estimators of $k$
largest in absolute value eigenvalues $\lambda_{(1)},\dots,\lambda_{(k)}$ of
the matrix $A$. As follows from results in [22], these estimators are
consistent as $N\to\infty$ under conditions to be discussed below even though
they are based on a realization of the random matrix $\Omega$. Specifically,
Corollary 10.10 in [22] shows that

$\mathbb{E}[\|A-QQ^{\prime}A\|]\leq\left(1+\sqrt{\frac{k}{p-1}}+\frac{e\sqrt{N(k+p)}}{p}\right)^{\frac{1}{q+p+1}}|\lambda_{(k+1)}|,$

where $\lambda_{(k+1)}$ is the $(k+1)$th largest in absolute value eigenvalue
of $A$. Therefore, by Markov’s inequality,

$\|A-QQ^{\prime}A\|=O_{P}(|\lambda_{(k+1)}|).$ (57)

In turn, by the triangle inequality, the fact that $Q^{\prime}Q$ is the
identity matrix, and the definition $B=Q^{\prime}A$,

$\displaystyle\|A^{\prime}A-B^{\prime}B\|$
$\displaystyle=\|A^{\prime}A-A^{\prime}QQ^{\prime}QQ^{\prime}A\|$
$\displaystyle\leq\|A\|\|A-QQ^{\prime}A\|+\|QQ^{\prime}A\|\|A-QQ^{\prime}A\|\leq
2\|A\|\|A-QQ^{\prime}A\|$

Thus, given that $\hat{\lambda}_{(1)}^{2},\dots,\hat{\lambda}_{(k)}^{2}$ are
$k$ largest eigenvalues of the matrix $B^{\prime}B$ by construction (see Steps
8,9, and 10 in the algorithm above), it follows from Weyl’s inequality that
$\hat{\lambda}_{(1)}^{2},\dots,\hat{\lambda}_{(k)}^{2}$ are consistent
estimators of $\lambda_{(1)}^{2},\dots,\lambda_{(k)}^{2}$ as long as
$\|A\|=O_{P}(1)$ and $|\lambda_{(k+1)}|=o_{P}(1)$ as $N\to\infty$. Hence,
$\hat{\lambda}_{(j)}\to\lambda_{(j)}$ for all $j=1,\dots,k$ under the same
conditions by the Davis-Kahane theorem.

The described algorithm can be applied in Section 2 to calculate the spectral
estimator $\tilde{\beta}$ with $A=A^{b}$ and $k=2GM+2$. In this case, the
aforementioned conditions $\|A\|=O_{P}(1)$ and $|\lambda_{(k+1)}|=o_{P}(1)$
are satisfied under Assumptions 3.1 and 3.2 by the proof of Theorem 3.1.

##  Appendix D Relation between Assumptions 3.1–3.12 and Assumptions 4.1–4.12

In this section, we explain what conditions one has to impose on top of
Assumptions 3.1–3.12 to obtain Assumptions 4.1–4.12. To start with, note that
Assumptions 4.1 and 4.5–4.9 coincide with Assumptions 3.1 and 3.5–3.9. Also,
Assumption 4.11 follows immediately from Assumption 3.11 if we define
$\mathring{\mathcal{B}}=[-1,1]\times\mathcal{B}$, as proposed in the main
text. In addition, Assumptions 3.10 and 3.12 depend on $x_{it}$ but their
versions corresponding to the dynamic model, i.e. Assumptions 4.10 and 4.12,
are discussed in [11], where some interpretations as well as low-level
conditions are provided. We thus only need to discuss Assumptions 4.2, 4.3,
and 4.4.

To this end, suppose that Assumptions 3.1, 3.2, 3.3, and 3.4 are satisfied
and, in addition, suppose that the noise variables $v_{it}$ satisfy (16).
Moreover, suppose that there exists a constant $C_{y}>0$ such that
$\|y_{i0}\|_{\psi_{2}}\leq C_{y}$ for all $i=1,\dots,N$. Then for all
$u=(u_{1},\dots,u_{T})^{\prime}\in\mathcal{S}^{T}$, we have

$\left\|\sum_{t=1}^{T}u_{t}\sum_{r=0}^{t-2}\theta^{r}v_{it-r-1}\right\|_{\psi_{2}}=\left\|\sum_{t=1}^{T-1}v_{it}\sum_{r=t}^{T-1}u_{r+1}\theta^{r-t}\right\|_{\psi_{2}}\leq\frac{C_{1}}{1-\theta}$

by Assumption 3.1(i) and Lemma A.4 and, similarly,

$\left\|\sum_{t=1}^{T}u_{t}\sum_{r=0}^{t-2}\theta^{r}z_{it-r-1}^{\prime}\beta\right\|_{\psi_{2}}=\left\|\sum_{t=1}^{T-1}z_{it}^{\prime}\beta\sum_{r=t}^{T-1}u_{r+1}\theta^{r-t}\right\|_{\psi_{2}}\leq\frac{d_{z}C_{2}\|\beta\|_{\infty}}{1-\theta}$

by Assumption 3.1(ii) and Lemma A.4, where $d_{z}$ is the dimension of
$z_{it}$. Also,

$\left\|\sum_{t=1}^{T}u_{t}\theta^{t-1}y_{i0}\right\|_{\psi_{2}}\leq\frac{\|y_{i0}\|_{\psi_{2}}}{1-\theta}\leq\frac{C_{y}}{1-\theta}.$

Hence, by the triangle inequality,

$\left\|\sum_{t=1}^{T}u_{t}z_{it}^{y}\right\|_{\psi_{2}}\leq\frac{C_{y}+C_{1}+d_{z}C_{2}\|\beta\|_{\infty}}{1-\theta},$

and so Assumption 4.2 is satisfied.

Next,

$\displaystyle\mathbb{E}\left[\left(\sum_{i=1}^{N}\sum_{t=1}^{T}v_{it}z_{it}^{y}\right)^{2}\right]$
$\displaystyle=\sum_{i=1}^{N}\sum_{t=1}^{T}\mathbb{E}\left[(v_{it}z_{it}^{y})^{2}\right]\leq\sum_{i=1}^{N}\sum_{t=1}^{T}\sqrt{\mathbb{E}[v_{it}^{4}]\mathbb{E}[(z_{it}^{y})^{4}]}\leq
CNT$

for some constant $C>0$ by (16), the triangle inequality, Assumption 3.1, the
fact that $\|y_{i0}\|_{\psi_{2}}\leq C_{y}$ for all $i=1,\dots,N$, and (2.15)
in [39]. Thus, Assumption 4.3 is satisfied as well. Finally, regarding
Assumption 4.4, observe that the convergence
$(NT)^{-1}\sum_{i=1}^{N}\sum_{t=1}^{T}\mathring{z}_{it}\mathring{z}_{it}^{\prime}=\mathring{\Sigma}+O_{P}(1/\sqrt{NT})$
holds by a law of large numbers as long as the dependence of
$(z_{it},v_{it})$’s across $t$ is not too strong. Also, by Assumption 3.4, the
matrix $\mathring{\Sigma}$ has at most one zero eigenvalue, whereas Assumption
4.4 requires that $\mathring{\Sigma}$ has no zero eigenvalues, so that
$\mathring{\Sigma}$ is invertible. Although it seems difficult to provide low-
level conditions implying invertibility of $\mathring{\Sigma}$, as it depends
on the auto-covariance structure of the random processes
$(z_{it}^{\prime},v_{it})^{\prime}$, $t=1,\dots,T$, we note that
$\mathring{\Sigma}$ can be consistently estimated (as it is done in the
process of constructing the spectral estimator), and so the invertibility
condition is testable.

##  Appendix E Motivating Example

To motivate equation (3), we provide a specific example in the context of
agricultural production and environmental economics. Suppose a production
process has an input that is potentially polluting, $x$, such as a pesticide.
In addition, suppose we want to assess the incidence of the use of this
substance in the environment’s pollution, such as water or soil. See, for
example, [30]. The incidence of polluting substances on the environment
depends on the intensity of use, but also on the characteristics of the
environment, such as soil permeability, rainfall, etc.

Suppose we have the following model to quantify the effect of the use of input
$x$ on some measure of pollution:

$\displaystyle y_{it}=x_{it}\beta+\alpha_{g_{i}t}+\varepsilon_{it}$

where $y_{it}$ is a measure of pollution, $x_{it}$ is the quantity of
pesticide, $\alpha_{g_{i}t}$ are unobserved characteristics of the region,
$g_{i}$, such as soil permeability, rain incidence, and other characteristics
that influence the presence of chemicals in the environment, and $\varepsilon$
is an unobserved shock. The farmer chooses to purchase pesticide in the local
market as to maximize expected profits:

$x_{it}=\arg\max_{x}\mathbb{E}\left[\pi_{i}(x,\alpha_{g_{i}t},z_{it},\nu_{it})|\alpha_{g_{i}1},\ldots\alpha_{g_{i}T},z_{i1},\ldots,z_{iT}\right]-C(x,p^{x}_{g_{i}t})/p_{g_{i}t}$
(58)

where $\pi_{i}(x,\alpha_{gt},z_{it},\varepsilon_{it})$ is the production
function of farmer $i$, and $C(x,p^{x}_{g_{i}t})$ is the cost associated to
purchase $x$ when the price of the input is $p^{x}_{g_{i}t}$, and $p_{g_{i}t}$
is the price of the produced good in the local market of farmer $i$. The
production process depends on the use of observable inputs, such as $x$, but
also soil and rain characteristics specific to the region, that affect both
the prevalence of pesticides in the environment but also the agricultural
process, and $z_{it}$, a variable that affects production, such as quality of
inputs, observed to the farmer but not to the econometrician, which does not
affect the environment. Finally $\nu$ is an idiosyncratic shock in the
production process, unforeseeable by both the farmer and the econometrician.

Assume
$\pi_{i}(x,\alpha_{g_{i}t},z_{it},\nu_{it})=\tilde{\pi}_{i}(x,\alpha_{g_{i}t},z_{it})+\nu_{it}$,
and
$\mathbb{E}\left[\nu_{it}|\alpha_{g_{i}1},\ldots\alpha_{g_{i}T},z_{i1},\ldots,z_{iT}\right]=0$.
In addition, let
$\tilde{\pi}_{i}^{\prime}(x,\alpha_{g_{i}t},z_{it})=\beta_{i}x+\alpha_{g_{i}t}+z_{it}$,
and $C^{\prime}(x,p^{x}_{g_{i}t})=p^{x}_{g_{i}t}$ be the partial derivative
with respect to the first argument, respectively for $\tilde{\pi}_{i}$ and
$C$. The F.O.C. in (58) implies that $x_{it}$ is defined as:

$\displaystyle\beta_{i}x_{it}+\alpha_{gt}+z_{it}-\frac{p^{x}_{gt}}{p_{gt}}=0,$

which implies:
$x_{it}=\frac{1}{\beta_{i}}\left(\frac{p^{x}_{gt}}{p_{gt}}-\alpha_{gt}\right)-\frac{1}{\beta_{i}}z_{it}$,
which takes the form of equation (3) with $M=2$.

Table 1.  Mean Absolute Error (MAE) and misclassification results: $\sigma^{2}=1$, $M=1$ |  |  |  |  | $G=2$ |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.035 | 0.018 | 0.059 | 0.151 | 0.016 | 0.034 | 0.014 | 0.009 | 0.058
200 |  | 0.024 | 0.009 | 0.019 | 0.150 | 0.009 | 0.009 | 0.008 | 0.002 | 0.003
400 |  | 0.016 | 0.007 | 0.010 | 0.151 | 0.007 | 0.008 | 0.006 | 0.003 | 0.006
50 | 100 |  | 0.024 | 0.007 | 0.012 | 0.149 | 0.007 | 0.007 | 0.007 | 0.000 | 0.000
200 |  | 0.015 | 0.006 | 0.008 | 0.150 | 0.006 | 0.006 | 0.006 | 0.000 | 0.000
400 |  | 0.010 | 0.004 | 0.006 | 0.149 | 0.004 | 0.004 | 0.004 | 0.000 | 0.000
100 | 100 |  | 0.014 | 0.006 | 0.010 | 0.153 | 0.006 | 0.006 | 0.006 | 0.000 | 0.000
200 |  | 0.008 | 0.004 | 0.006 | 0.151 | 0.004 | 0.004 | 0.004 | 0.000 | 0.000
400 |  | 0.004 | 0.002 | 0.004 | 0.152 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
|  |  |  |  | $G=7$ |  |  |  |  |  |
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.116 | 0.109 | 0.144 | 0.151 | 0.023 | 0.144 | 0.011 | 0.346 | 0.705
200 |  | 0.057 | 0.085 | 0.149 | 0.152 | 0.029 | 0.149 | 0.010 | 0.234 | 0.744
400 |  | 0.025 | 0.062 | 0.142 | 0.148 | 0.055 | 0.147 | 0.006 | 0.139 | 0.764
50 | 100 |  | 0.034 | 0.014 | 0.142 | 0.147 | 0.007 | 0.147 | 0.007 | 0.006 | 0.651
200 |  | 0.015 | 0.008 | 0.143 | 0.148 | 0.006 | 0.137 | 0.006 | 0.001 | 0.645
400 |  | 0.009 | 0.004 | 0.062 | 0.150 | 0.004 | 0.137 | 0.004 | 0.000 | 0.622
100 | 100 |  | 0.022 | 0.006 | 0.148 | 0.151 | 0.006 | 0.110 | 0.006 | 0.000 | 0.364
200 |  | 0.009 | 0.003 | 0.083 | 0.152 | 0.003 | 0.112 | 0.003 | 0.000 | 0.289
400 |  | 0.006 | 0.003 | 0.006 | 0.150 | 0.003 | 0.078 | 0.003 | 0.000 | 0.203

Table 2.  Mean Absolute Error (MAE) and misclassification results: $\sigma^{2}=4$, $M=1$ |  |  |  |  | $G=2$ |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.026 | 0.005 | 0.018 | 0.153 | 0.005 | 0.005 | 0.005 | 0.000 | 0.000
200 |  | 0.015 | 0.003 | 0.014 | 0.159 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
400 |  | 0.009 | 0.002 | 0.009 | 0.157 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
50 | 100 |  | 0.015 | 0.003 | 0.014 | 0.156 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
200 |  | 0.009 | 0.002 | 0.009 | 0.157 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
400 |  | 0.007 | 0.001 | 0.007 | 0.144 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000
100 | 100 |  | 0.010 | 0.002 | 0.007 | 0.140 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
200 |  | 0.007 | 0.001 | 0.006 | 0.063 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000
400 |  | 0.004 | 0.001 | 0.005 | 0.011 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000
|  |  |  |  | $G=7$ |  |  |  |  |  |
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.055 | 0.005 | 0.099 | 0.155 | 0.004 | 0.055 | 0.004 | 0.000 | 0.154
200 |  | 0.029 | 0.003 | 0.035 | 0.158 | 0.003 | 0.073 | 0.003 | 0.000 | 0.216
400 |  | 0.016 | 0.002 | 0.013 | 0.158 | 0.002 | 0.060 | 0.002 | 0.000 | 0.195
50 | 100 |  | 0.026 | 0.003 | 0.014 | 0.157 | 0.003 | 0.049 | 0.003 | 0.000 | 0.135
200 |  | 0.012 | 0.002 | 0.009 | 0.157 | 0.002 | 0.048 | 0.002 | 0.000 | 0.138
400 |  | 0.007 | 0.002 | 0.006 | 0.157 | 0.002 | 0.071 | 0.002 | 0.000 | 0.219
100 | 100 |  | 0.023 | 0.002 | 0.011 | 0.156 | 0.002 | 0.048 | 0.002 | 0.000 | 0.122
200 |  | 0.009 | 0.001 | 0.007 | 0.161 | 0.001 | 0.062 | 0.001 | 0.000 | 0.165
400 |  | 0.005 | 0.001 | 0.004 | 0.158 | 0.001 | 0.036 | 0.001 | 0.000 | 0.101

Table 3.  Mean Absolute Error (MAE) and misclassification results: $\sigma^{2}=1$, $M=2$ |  |  |  |  | $G=2$ |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.048 | 0.019 | 0.016 | 0.171 | 0.015 | 0.016 | 0.014 | 0.015 | 0.004
200 |  | 0.028 | 0.009 | 0.011 | 0.169 | 0.008 | 0.008 | 0.008 | 0.004 | 0.005
400 |  | 0.019 | 0.007 | 0.008 | 0.169 | 0.007 | 0.007 | 0.006 | 0.003 | 0.003
50 | 100 |  | 0.022 | 0.008 | 0.010 | 0.168 | 0.008 | 0.008 | 0.008 | 0.000 | 0.000
200 |  | 0.016 | 0.007 | 0.007 | 0.168 | 0.007 | 0.007 | 0.007 | 0.000 | 0.000
400 |  | 0.009 | 0.003 | 0.006 | 0.168 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
100 | 100 |  | 0.013 | 0.005 | 0.008 | 0.168 | 0.005 | 0.005 | 0.005 | 0.000 | 0.000
200 |  | 0.011 | 0.004 | 0.005 | 0.169 | 0.004 | 0.004 | 0.004 | 0.000 | 0.000
400 |  | 0.006 | 0.003 | 0.004 | 0.167 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
|  |  |  |  | $G=7$ |  |  |  |  |  |
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.104 | 0.069 | 0.146 | 0.167 | 0.015 | 0.166 | 0.012 | 0.169 | 0.639
200 |  | 0.075 | 0.057 | 0.108 | 0.169 | 0.012 | 0.159 | 0.009 | 0.144 | 0.641
400 |  | 0.038 | 0.046 | 0.040 | 0.170 | 0.014 | 0.153 | 0.006 | 0.103 | 0.608
50 | 100 |  | 0.050 | 0.013 | 0.094 | 0.169 | 0.009 | 0.081 | 0.009 | 0.004 | 0.204
200 |  | 0.024 | 0.006 | 0.011 | 0.168 | 0.005 | 0.014 | 0.005 | 0.002 | 0.019
400 |  | 0.014 | 0.004 | 0.006 | 0.167 | 0.004 | 0.004 | 0.004 | 0.000 | 0.000
100 | 100 |  | 0.025 | 0.006 | 0.011 | 0.166 | 0.006 | 0.017 | 0.006 | 0.000 | 0.019
200 |  | 0.012 | 0.004 | 0.006 | 0.168 | 0.004 | 0.004 | 0.004 | 0.000 | 0.000
400 |  | 0.007 | 0.003 | 0.003 | 0.168 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000

Table 4.  Mean Absolute Error (MAE) and misclassification results: $\sigma^{2}=4$, $M=2$ |  |  |  |  | $G=2$ |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.036 | 0.005 | 0.006 | 0.167 | 0.005 | 0.005 | 0.005 | 0.000 | 0.000
200 |  | 0.017 | 0.003 | 0.004 | 0.169 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
400 |  | 0.012 | 0.003 | 0.004 | 0.167 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
50 | 100 |  | 0.016 | 0.003 | 0.004 | 0.122 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
200 |  | 0.012 | 0.002 | 0.003 | 0.087 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
400 |  | 0.006 | 0.001 | 0.002 | 0.038 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000
100 | 100 |  | 0.009 | 0.002 | 0.003 | 0.030 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
200 |  | 0.007 | 0.002 | 0.002 | 0.009 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
400 |  | 0.005 | 0.001 | 0.001 | 0.001 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000
|  |  |  |  | $G=7$ |  |  |  |  |  |
$\ \ T\ \ $ | $\ \ N\ \ $ |  | Mean Absolute Error | Misclassification
|  S |  P-S | LS | Pen NN |  I-GFE |  GFE |  Oracle |  S |  GFE
20 | 100 |  | 0.103 | 0.006 | 0.007 | 0.164 | 0.004 | 0.004 | 0.004 | 0.003 | 0.000
200 |  | 0.063 | 0.003 | 0.005 | 0.169 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
400 |  | 0.028 | 0.002 | 0.004 | 0.169 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
50 | 100 |  | 0.036 | 0.003 | 0.005 | 0.171 | 0.003 | 0.003 | 0.003 | 0.000 | 0.000
200 |  | 0.015 | 0.002 | 0.003 | 0.169 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
400 |  | 0.011 | 0.001 | 0.002 | 0.168 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000
100 | 100 |  | 0.021 | 0.002 | 0.003 | 0.173 | 0.002 | 0.002 | 0.002 | 0.000 | 0.000
200 |  | 0.010 | 0.001 | 0.002 | 0.167 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000
400 |  | 0.005 | 0.001 | 0.001 | 0.166 | 0.001 | 0.001 | 0.001 | 0.000 | 0.000


# Comparing zeros of
distinct Dirichlet $L$-functions

William Banks  Department of Mathematics, University of Missouri, Columbia MO
65211, USA<EMAIL_ADDRESS>
###### Abstract.

Let $\chi_{1}$ and $\chi_{2}$ be distinct primitive Dirichlet characters whose
moduli are $q_{1}$ and $q_{2}$, respectively, and put
$q\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}={\rm
lcm}[q_{1},q_{2}]\geqslant 3$. We show that for some absolute constants
$C_{1},C_{2}>0$, the $L$-functions $L(s,\chi_{1})$ and $L(s,\chi_{2})$ do not
have the same zeros (counted with multiplicity) in the region

$\big{\\{}s=\sigma+it\in\mathbb{C}:0<\sigma<1,~{}T<\gamma<T+C_{1}q^{2}\log
T\big{\\}}$

for any real number $T\geqslant C_{2}\,q^{2}\log q$.

MSC Primary: 11M06; Secondary: 11M26.

Keywords: Dirichlet $L$-function, Dirichlet character, nontrivial zeros.

##  1\. Introduction

For a given Dirichlet character $\chi$ modulo $q\geqslant 1$, the $L$-function
$L(s,\chi)$ is defined in the half-plane $\sigma>1$ via the equivalent
definitions

$L(s,\chi)\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=\sum_{n\geqslant
1}\chi(n)n^{-s}=\prod_{p\text{~{}prime}}(1-\chi(p)p^{-s})^{-1}.$

If $\chi$ is nonprincipal, then $L(s,\chi)$ extends to an entire function on
the complex plane, and if $\chi$ is primitive, then $L(s,\chi)$ satisfies a
simple functional equation relating its values at $s$ and $1-s$. In this note,
we prove the following:

######  Theorem 1.1.

There exist absolute constants $C_{1},C_{2}>0$ such that the following
property holds. Let $\chi_{1}$ and $\chi_{2}$ be distinct primitive Dirichlet
characters whose moduli are $q_{1}$ and $q_{2}$, respectively, and put
$q\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}={\rm
lcm}[q_{1},q_{2}]\geqslant 3$. If $T\geqslant C_{2}\,q^{2}\log q$, then
$L(s,\chi_{1})$ and $L(s,\chi_{2})$ do not have the same zeros $($counted with
multiplicity$)$ in the region

$\mathcal{R}(q,T)\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=\big{\\{}s=\sigma+it\in\mathbb{C}:0<\sigma<1,~{}T<\gamma<T+C_{1}q^{2}\log
T\big{\\}}.$

In other words, the function

$\frac{L(s,\chi_{1})}{L(s,\chi_{2})}+\frac{L(s,\chi_{2})}{L(s,\chi_{1})}$
(1.1)

has at least one pole in $\mathcal{R}(q,T)$.

Some related results have been previously found. Fujii [3, Thm. $1^{\prime}$]
showed that if $\chi_{1}$ and $\chi_{2}$ are distinct primitive characters to
the same modulus, then a positive proportion of the nontrivial zeros of
$L(s,\chi_{1})L(s,\chi_{2})$ are poles of the function (1.1). Using a variant
of Hamburger’s theorem, Ragunathan [12, Thm. 3] showed that for any pair of
distinct primitive characters $\chi_{1}$ and $\chi_{2}$, both functions

$\frac{L(s,\chi_{1})}{L(s,\chi_{2})}\qquad\mbox{and}\qquad\frac{L(s,\chi_{2})}{L(s,\chi_{1})}$

have infinitely many (non-integer) poles.

Our proof of Theorem 1.1 is based on a generalization of a striking formula
due to Landau [7, Satz 1], which asserts that for any fixed $x>1$ one has

$\sum_{\begin{subarray}{c}\rho=\beta+i\gamma\\\ 1<\gamma\leqslant
T\end{subarray}}x^{\rho}=-\frac{T}{2\pi}\Lambda(x)+O(\log T),$ (1.2)

where the sum runs over the multiset of nontrivial zeros $\rho=\beta+i\gamma$
of the Riemann zeta function $\zeta(s)$ with $1<\gamma\leqslant T$, and
$\Lambda$ is defined as follows: $\Lambda(x)\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=\log p$ if $x$ is a positive integral power of a prime
$p$, and $\Lambda(x)\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=0$ for all other real values of $x$. Gonek [6, Thm. 1]
gave a uniform version of Landau’s result (1.2) with an error expressed in
terms of both variables $x$ and $T$. Some stronger versions of the Gonek-
Landau theorem are known; see [1, 4, 5].

The following result extends [6, Thm. 1] (and is proved using Gonek’s methods)
to cover the case of an $L$-function attached to a primitive Dirichlet
character.

######  Theorem 1.2.

Let $\chi$ be a primitive Dirichlet character modulo $q\geqslant 1$. Then,
uniformly for $x>1$ and $T_{2}>T_{1}>1$, we have

$\sum_{\begin{subarray}{c}\rho=\beta+i\gamma\\\
T_{1}<\gamma<T_{2}\end{subarray}}x^{\rho}=-\frac{T_{2}-T_{1}}{2\pi}\Lambda(x)\chi(x)+O(E),$
(1.3)

where the sum runs over the nontrivial zeros $\rho=\beta+i\gamma$ of
$L(s,\chi)$ for which $T_{1}<\gamma<T_{2}$ $($each zero being summed according
to its multiplicity$)$,

$E\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}=x\log 2x\log\log
3x+x\log 2x\cdot\min\Big{\\{}\frac{T_{2}}{x},\frac{1}{\langle
x\rangle}\Big{\\}}+x\log 2qT_{2}\log\log 3x,$

and $\langle x\rangle$ is the distance from $x$ to the nearest prime power
other than $x$ itself. The implied constant in (1.3) is absolute.

We remark that stronger results have been achieved covering all functions in
the Selberg class (including the Dirichlet $L$-functions considered here); see
[2, 9, 10]. For our purposes, however, the error term provided by Theorem 1.2
is more convenient as the dependence on the quantity $\langle x\rangle$ is
explicit.

##  2\. Preliminaries

######  Lemma 2.1.

For $x,T>1$ and $c\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=1+\tfrac{1}{\log 3x}$ we have

$\sum_{\begin{subarray}{c}n\geqslant 2\\\ n\neq
x\end{subarray}}\frac{\Lambda(n)}{n^{c}}\min\Big{\\{}T,\frac{1}{|\log(x/n)|}\Big{\\}}\ll\log
2x\log\log 3x+\log 2x\cdot\min\Big{\\{}\frac{T}{x},\frac{1}{\langle
x\rangle}\Big{\\}},$

where $\langle x\rangle$ is the distance from $x$ to the nearest prime power
other than $x$ itself.

###### Proof.

See Gonek [6, Lem. 2]. ∎

######  Lemma 2.2.

Let $\chi$ be a primitive character modulo $q\geqslant 1$. Then the estimate

$\frac{L^{\prime}}{L}(s,\chi)=\sum_{\begin{subarray}{c}\rho\\\
|\gamma-t|<1\end{subarray}}\frac{1}{s-\rho}+O\big{(}\log 2q|t|\big{)}$

holds uniformly for $-1\leqslant\sigma\leqslant 2$ and $|t|\geqslant 1$.

###### Proof.

See Montgomery and Vaughan [8, Lems. 12.1 and 12.6]. ∎

##  3\. Proof of Theorem 1.2

Our proof closely parallels that of Gonek [6, Thm. 1].

We can assume without loss of generality that neither $T_{1}$ nor $T_{2}$ is
the ordinate of a zero of $L(s,\chi)$. Let $\mathcal{C}$ be the rectangle in
the complex plane:

$c+iT_{1}~{}~{}\longrightarrow~{}~{}c+iT_{2}~{}~{}\longrightarrow~{}~{}1-c+iT_{2}~{}~{}\longrightarrow~{}~{}1-c+iT_{1}~{}~{}\longrightarrow~{}~{}c+iT_{1}.$

By Cauchy’s theorem we have

$\displaystyle\sum_{\begin{subarray}{c}\rho=\beta+i\gamma\\\
T_{1}<\gamma<T_{2}\end{subarray}}x^{\rho}$ $\displaystyle=\frac{1}{2\pi
i}\bigg{(}\nolimits{}_{c+iT_{1}}^{c+iT_{2}}+\nolimits{}_{c+iT_{2}}^{1-c+iT_{2}}+\nolimits{}_{1-c+iT_{2}}^{1-c+iT_{1}}+\nolimits{}_{1-c+iT_{1}}^{c+iT_{1}}\bigg{)}\frac{L^{\prime}}{L}(s,\chi)\,x^{s}\,ds$
$\displaystyle=I_{1}+I_{2}+I_{3}+I_{4}\quad\text{(say)}.$

We estimate the four integrals separately.

In the half-plane $\sigma>1$ we have

$\frac{L^{\prime}}{L}(s,\chi)=-\sum_{n\geqslant
2}\frac{\Lambda(n)\chi(n)}{n^{s}},$ (3.1)

and therefore

$\displaystyle I_{1}$
$\displaystyle=\frac{1}{2\pi}\nolimits{}_{T_{1}}^{T_{2}}\frac{L^{\prime}}{L}(c+it,\chi)\,x^{c+it}\,dt=-\frac{x^{c}}{2\pi}\sum_{n\geqslant
2}\frac{\Lambda(n)\chi(n)}{n^{c}}\nolimits{}_{T_{1}}^{T_{2}}\Big{(}\frac{x}{n}\Big{)}^{it}\,dt$
$\displaystyle=-\frac{T_{2}-T_{1}}{2\pi}\Lambda(x)\chi(x)+O\bigg{(}x^{c}\sum_{\begin{subarray}{c}n\geqslant
2\\\ n\neq
x\end{subarray}}\frac{\Lambda(n)}{n^{c}}\min\Big{\\{}T_{2},\frac{1}{|\log(x/n)|}\Big{\\}}\bigg{)}.$

Applying Lemma 2.1 and taking into account that $x^{c}\ll x$, we deduce that

$I_{1}=-\frac{T_{2}-T_{1}}{2\pi}\Lambda(x)\chi(x)+O\bigg{(}x\log
2x\bigg{(}\log\log 3x+\min\Big{\\{}\frac{T_{2}}{x},\frac{1}{\langle
x\rangle}\Big{\\}}\bigg{)}\bigg{)}.$ (3.2)

Next, using Lemma 2.2 we have

$I_{2}=\frac{1}{2\pi i}\sum_{\begin{subarray}{c}\rho\\\ |\gamma-
T_{2}|<1\end{subarray}}\nolimits{}_{c+iT_{2}}^{1-c+iT_{2}}\frac{x^{s}\,ds}{s-\rho}+O\bigg{(}\log
2qT_{2}\cdot\nolimits{}_{1-c}^{c}x^{\sigma}\,d\sigma\bigg{)},$

where the sum runs over the zeros $\rho=\beta+i\gamma$ of $L(s,\chi)$ for
which $|\gamma-T_{2}|<1$, each zero being summed according to its
multiplicity. Since $x^{c}\ll x$, the error term is $O(x\log 2qT_{2}/\log x)$,
and arguing as in [6, p. 402] we have for each zero $\rho$ in the sum:

$\nolimits{}_{c+iT_{2}}^{1-c+iT_{2}}\frac{x^{s}\,ds}{s-\rho}\ll x\log\log 3x.$

Since there are at most $O(\log 2qT_{2})$ such zeros, we obtain that

$I_{2}\ll x\log 2qT_{2}\log\log 3x.$ (3.3)

Similarly, we have

$I_{4}\ll x\log 2qT_{1}\log\log 3x.$ (3.4)

Finally, we come to

$I_{3}=-\frac{1}{2\pi}\nolimits{}_{T_{1}}^{T_{2}}\frac{L^{\prime}}{L}(1-c+it,\chi)\,x^{1-c+it}\,dt.$
(3.5)

Recall the functional equation (cf. [8, Cor. 10.9])

$L(s,\chi)=\varepsilon(\chi)L(1-s,\overline{\chi})2^{s}\pi^{s-1}q^{1/2-s}\Gamma(1-s)\sin\tfrac{\pi}{2}(s+\kappa),$
(3.6)

where

$\kappa=\kappa(\chi)\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=\begin{cases}0&\quad\text{if $\chi(-1)=1$},\\\
1&\quad\text{if $\chi(-1)=-1$},\\\ \end{cases}$

and

$\varepsilon(\chi)\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=\frac{\tau(\chi)}{i^{\kappa}\sqrt{q}}\qquad\text{with}\quad\tau(\chi)\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}=\sum_{a\bmod q}\chi(a)\mathrm{e}^{2\pi ia/q}.$

Taking the logarithmic derivative of (3.6) and setting
$s\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}=1-c+it$ for some
$t\in(T_{1},T_{2})$, we get that

$\displaystyle-\frac{L^{\prime}}{L}(1-c+it,\chi)$
$\displaystyle=\frac{L^{\prime}}{L}(c-it,\overline{\chi})+\log\frac{q}{2\pi}+\frac{\Gamma^{\prime}}{\Gamma}(c-it)-\tfrac{\pi}{2}\cot\tfrac{\pi}{2}(1-c+\kappa+it)$
$\displaystyle=\frac{L^{\prime}}{L}(c-it,\overline{\chi})+\log\frac{q\,t}{2\pi}+O(t^{-1}),$

where the implied constant is absolute. Inserting this estimate into (3.5),
and taking into account that $x^{1-c}\ll 1$, it follows that

$I_{3}=\frac{x^{1-c}}{2\pi}\nolimits{}_{T_{1}}^{T_{2}}\frac{L^{\prime}}{L}(c-it,\overline{\chi})\,x^{it}\,dt+O\left(\frac{\log
2qT_{2}}{\log x}+\log T_{2}\right)$

Using (3.1), the first term is

$-\frac{x^{1-c}}{2\pi}\sum_{n\geqslant
2}\frac{\Lambda(n)\chi(n)}{n^{c}}\nolimits{}_{T_{1}}^{T_{2}}(nx)^{it}\,dt\ll\sum_{n\geqslant
2}\frac{\Lambda(n)\chi(n)}{n^{c}\log
nx}\ll-\frac{\zeta^{\prime}}{\zeta}(c)\ll\frac{1}{c-1}=\log 3x.$

Therefore,

$I_{3}\ll\log 2qT_{2}+\log 2x.$ (3.7)

Combining (3.2), (3.3), (3.4), and (3.7), the theorem follows.

##  4\. Proof of Theorem 1.1

First, we claim that there is a prime $p_{0}$ such that

$\chi_{1}(p_{0})\neq\chi_{2}(p_{0}),\qquad p_{0}\ll
q,\qquad|\chi_{1}(p_{0})-\chi_{2}(p_{0})|\gg q^{-1}.$ (4.1)

To prove this, let $\chi$ be the Dirichlet character
$\chi_{1}\overline{\chi}_{2}$ modulo $q\mathrel{\vbox{\hbox{\scriptsize.}
\hbox{\scriptsize.}}}={\rm lcm}[q_{1},q_{2}]\geqslant 3$.

If $\chi$ is the principal character modulo $q$, then
$\chi_{1}(p)=\chi_{2}(p)$ for every prime $p\nmid q$. Therefore, since
$\chi_{1}\neq\chi_{2}$, we must have $\chi_{1}(p)\neq\chi_{2}(p)$ for some
prime $p\mid q$; let $p_{0}$ be any such prime. Then $p_{0}\leqslant q$, and
we also have $|\chi_{1}(p_{0})-\chi_{2}(p_{0})|=1$ since one of the numbers
$\chi_{j}(p_{0})$ is a root of unity while the other is zero. This proves
(4.1) in this case.

If $\chi$ is not the principal character modulo $q$, then by Norton [11,
(1.22)] the least character non-residue $n_{\chi}$ (i.e., the least positive
integer $n$ such that $\chi(n)\neq 0$ and $\chi(n)\neq 1$) satisfies
$n_{\chi}\ll_{\varepsilon}q^{1/4\sqrt{\mathrm{e}}+\varepsilon}$ for any
$\varepsilon>0$. Since $n_{\chi}$ is a prime number, we can take
$p_{0}\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}=n_{\chi}$, so
that $\chi_{1}(p_{0})\neq\chi_{2}(p_{0})$ and $p_{0}\ll q^{0.16}$. The lower
bound $|\chi_{1}(p_{0})-\chi_{2}(p_{0})|\gg q^{-1}$ follows from the fact that
$\chi_{1}(p_{0})$ and $\chi_{2}(p_{0})$ are distinct $\phi(q)$-th roots of
unity, where $\phi$ is the Euler function. Thus, (4.1) holds in this case as
well.

Let $\Delta$ be a real number such that $0<\Delta<T$; our choice of $\Delta$
is specified below. For $j=1$ or $2$, let $\mathcal{S}_{j}(T)$ be the multiset
of zeros $\rho=\beta+i\gamma$ of $L(s,\chi_{j})$ with $T<\gamma<T+\Delta$,
where the number of times each zero occurs in $\mathcal{S}_{j}(T)$ is the same
as its multiplicity. Applying Theorem 1.2 with
$x\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}=p_{0}$,
$T_{1}\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}=T$, and
$T_{2}\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}=T+\Delta$, we
have

$\sum_{\begin{subarray}{c}\rho\in\mathcal{S}_{j}(T)\end{subarray}}p_{0}^{\rho}=-\frac{\Delta\log
p_{0}}{2\pi}\chi_{j}(p_{0})+O(p_{0}\log qT\log\log
2p_{0})\qquad(j=1\text{~{}or~{}}2).$

(Here we used the fact that $\langle p_{0}\rangle\geqslant 1$). If the zero
sets $\mathcal{S}_{1}(T)$ and $\mathcal{S}_{2}(T)$ are the same, then on
subtracting the above estimates we get that

$\frac{\Delta\log p_{0}}{2\pi}\big{(}\chi_{1}(p_{0})-\chi_{2}(p_{0})\big{)}\ll
p_{0}\log qT\log\log 2p_{0}.$

Using the bounds in (4.1) we see that the inequality

$\Delta\leqslant Cq^{2}\log qT$

holds with some absolute constant $C>0$. Taking
$\Delta\mathrel{\vbox{\hbox{\scriptsize.} \hbox{\scriptsize.}}}=2Cq^{2}\log
qT$, we obtain a contradiction provided that $\Delta<T$, and thus we deduce
that the zero sets $\mathcal{S}_{1}(T)$ and $\mathcal{S}_{2}(T)$ cannot be
equal. Since $\Delta<T$ holds if $T\geqslant C_{2}q^{2}\log q$ with some
suitable absolute constant $C_{2}>0$, and $\log qT\ll\log T$ for such $T$, the
theorem is proved.

###  4.1. Acknowledgments

The author would like to thank Steve Gonek and Alexandru Zaharescu for helpful
comments and for pointing out some relevant literature.

## References

  * [1] K. Ford and A. Zaharescu, On the distribution of imaginary parts of zeros of the Riemann zeta function. _J. Reine Angew. Math._ 579 (2005), 145–158.
  * [2] K. Ford, K. Soundararajan and A. Zaharescu, On the distribution of imaginary parts of zeros of the Riemann zeta function. II. _Math. Ann._ 343 (2009), no. 3, 487–505.
  * [3] A. Fujii, On the zeros of Dirichlet $L$-functions (V). _Acta Arith._ 28 (1975/76), no. 4, 395–403.
  * [4] A. Fujii, On a theorem of Landau. _Proc. Japan Acad. Ser. A Math. Sci._ 65 (1989), no. 2, 51–54.
  * [5] A. Fujii, On a theorem of Landau. II. _Proc. Japan Acad. Ser. A Math. Sci._ 66 (1990), no. 9, 291–296.
  * [6] S. M. Gonek, An explicit formula of Landau and its applications to the theory of the zeta-function, in _A tribute to Emil Grosswald: number theory and related analysis_ , 395–413, Contemp. Math., 143, Amer. Math. Soc., Providence, RI, 1993.
  * [7] E. Landau, Über die Nullstellen der Zetafunktion. _Math. Ann._ 71 (1912), no. 4, 548–564.
  * [8] H. L. Montgomery and R. C. Vaughan, _Multiplicative number theory. I. Classical theory._ Cambridge Studies in Advanced Mathematics, 97. Cambridge University Press, Cambridge, 2007.
  * [9] M. R. Murty and A. Perelli, The pair correlation of zeros of functions in the Selberg class. _Internat. Math. Res. Notices_ (1999), no. 10, 531–545.
  * [10] M. R. Murty and A. Zaharescu, Explicit formulas for the pair correlation of zeros of functions in the Selberg class. _Forum Math._ 14 (2002), no. 1, 65–83.
  * [11] K. K. Norton, A character-sum estimate and applications. _Acta Arith._ 85 (1998), no. 1, 51–78.
  * [12] R. Raghunathan, A comparison of zeros of $L$-functions. _Math. Res. Lett._ 6 (1999), no. 2, 155–167.


Therefore, one can see that the error analysis in Theorem 30 is sensitive to
the condition number provided by the given sketch function. In the case of
large condition number, one might actually obtain a better result from
truncating $r_{e}$.Error analysis for TTNS-Sketch with truncation is out of
the scope for this paper, but one can see that the perturbative sketch
function actually performs quite well without any truncation.

###  8.3. Numerical case study: tree graphical model with large variable
dimension

In this subsection, we will test the performance of TTNS-Sketch in the setting
of large $d$. We consider tree-based graphical models of the form (70) with
$\beta=1/2$, $f_{i,j}(x_{i},x_{j})=-x_{i}x_{j}$, and $x_{i}\in\\{-1,1\\}$,
which is the case of Ising model. As a remark, cases under more general
$\\{f_{i,j}\\}_{(i,j)\in E}$ leads to the same conclusion, and so they are
excluded for the sake of brevity. For the candidate graph $T$, we consider a
path graph with $d=100$ nodes and the 3-fractal dendrimer graph with $d=94$
nodes, see Figure 12.

(a) Path Graph (segment)

(b) Dendrimer Graph with $d=94$

Figure 11. Plot of graphs considered in Section 8.3

(c) Path graph $d=100$

(d) Dendrimer graph with $d=94$

Figure 12. Error comparison for path graph with $d=100$ and dendrimer graph
with $d=94$. The model $\hat{p}_{\mathrm{CL}}$ stands for the result of direct
graphical modeling with the true Tree structure $T$. One can see that all
methods converge to the true model. Among TTNS-Sketch based models, TTNS-
Sketch with perturbative sketch function has the best performance. In Figure
11(c), $\hat{p}_{\mathrm{TS}}$ with perturbative sketching has an error that
is quite close to the benchmark $\hat{p}_{\mathrm{CL}}$.

For samples generated from the underlying model, direct graphical modeling
with the underlying tree model $T$ provides the best tree-based graphical
model in the sense of MLE, and hence we put it as the benchmark. We compare
the following sketch functions: (i) Markov sketch function, (ii) perturbative
sketching function with $\epsilon=0.05$. The result can be seen in Figure 12.
One can see that perturbative sketching significantly outperforms (i). In the
path case, perturbative sketching even has an almost equivalent performance to
direct graphical modeling. Due to the $N=O(d^{2})$ scaling in Theorem 30 and
the $O(d)$ computational scaling, one can likewise perform the same procedure
up to very large $d$.

###  8.4. Numerical case study: spin system with long range interactions

(a) Ring model with $d=16$

(b) Linear path model with $d=16$

Figure 13. Graph representations of the true model in Section 8.4 and the path
model learned by path-based graphical modeling.

Figure 14. Negative Log Likelihood (NLL) level comparison for the ring graph
with $d=16$ in Figure 13(a). Here, $N=2^{15}=32,768$. The model
$\hat{p}_{\mathrm{CL}}$ stands for the result of direct graphical modeling
with the path structure in Figure 13(b). The model $\hat{p}_{\mathrm{BM}}$
stands for the result of Born Machine with $r_{\mathrm{max}=4}$. The model
$\hat{p}_{\mathrm{TS}}$ stands for the result of TTNS-Sketch with the special
high-order Markov sketch function in (73). One can see that the output of
TTNS-Sketch is close to the NLL level of the true model, while the output of
BM is close to the NLL level of the path-based graphical model
$\hat{p}_{\mathrm{CL}}$.

Figure 15. Mutual Information (MI) level comparison for the ring graph with
$d=16$ in Figure 13(a), with experiment setting described in the caption of
Figure 15. The MI level of a distribution $p$ refers to $I(X_{1},X_{d})$ where
$X\sim p$. In other words, the MI level is the mutual information between the
last and first entry of the multivariate distribution according to $p$. One
can see that the mutual information level of BM is close to the zero
throughout training, which is a further evidence that BM effectively learns a
path graphical model.

Quite importantly, in this numerical experiment, we introduce another
important benchmark called Born Machine (BM). As BM is a method over the
tensor train format, we restrict TTNS-Sketch to the path graph
$T_{\mathrm{path}}$ to ensure fair comparison.

There are two important differences between BM and TTNS-Sketch. First, BM
assures positivity of the trained model. Second, BM is based on Negative Log
Likelihood (NLL) training, which is a more conventional error metric for
statistical modeling. While TTNS-Sketch does not ensure the trained model is
positive, the $\|\cdot\|_{\infty}$ norm error bound obtained in Section 7
ensures that positivity is not a major issue if the correct tree structure and
sketch function are provided.

During numerical experiment with BM, we have discovered a significant failure
mode of BM, which is that it fails to converge to the true model for periodic
spin systems. Similar observation has been independently made in
[gomez2021born]. To show the failure mode in the simplest possible setting, we
discuss the case of a Markov random field with a ring graph $G$ with $d=16$
nodes, and its graphical model representation of (72) is illustrated in Figure
13(a):

(72) $p^{\star}(x_{1},\ldots,x_{d})=\exp{\left(-\sum_{i-j=0\mod
d}f_{i,j}(x_{i},x_{j})\right)}$

For TTNS-Sketch, we pick a special high order Markov sketch function, with the
following neighborhood of interest:

(73) $\mathcal{S}_{k}=\\{k-1,k,k+1\\}\cup\\{1,d\\},$

which is chosen to ensure convergence in the limit of sample size.
Importantly, we include direct graphical modeling over the path graph
$T_{\mathrm{path}}$ as a benchmark.

We now discuss the numerical specification for the BM modeling. We pick the
sample size $N=2^{15}=32,768,$ which is sufficiently large so that the
generalization error should be small. For the BM method, there is a parameter
$r_{\mathrm{max}}$, which is the largest allowed internal bond dimension, i.e.
$\max_{e\in E}r_{e}\leq r_{\mathrm{max}}$. Importantly, $p^{\star}$ admits a
tensor train ansatz with $\max_{e\in E}r_{e}\leq 4$, and so we pick
$r_{\mathrm{max}}=4$ to ensure that the BM method in this instance has no
approximation error. The only training parameter is the learning rate and is
picked according to cross-validation.

In Figure 15, we plot the result of the comparison between BM, TTNS-Sketch,
and direct graphical modeling. Quite surprisingly, TTNS-Sketch can converge,
while the NLL level of BM stays at a sub-optimal level. Interestingly, the NLL
level of the BM model $\hat{p}_{\mathrm{BM}}$ converges to that of the
graphical model $\hat{p}_{\mathrm{CL}}$. Moreover, one can also show that the
KL-divergence between $\hat{p}_{\mathrm{BM}}$ and $\hat{p}_{\mathrm{CL}}$ is
quite small. In the converged model plotted in Figure 15, one has
$D_{\mathrm{KL}}\left(\hat{p}_{\mathrm{BM}}\parallel p^{\star}\right)\approx
0.4357$, while
$D_{\mathrm{KL}}\left(\hat{p}_{\mathrm{BM}}\parallel\hat{p}_{\mathrm{CL}}\right)\approx
0.0266$.

Numerically, we can then conclude that the BM training implicitly leads to a
sub-optimal model, and the gap to true model can be explained by the sub-
optimal model’s closeness to the path-based graphical model
$\hat{p}_{\mathrm{CL}}$, see Figure 13 for illustration. As an additional
evidence, during in the training dynamics, the learned model fails to capture
the correlation between node $1$ and node $d$. In Figure 15, the mutual
information level between node $1$ and node $d$ is plotted throughout
training, and one can see the level is consistently close to zero, despite the
strong correlation in $p^{\star}$.

In practice, when $d=16$, this phenomenon of BM training failure persists up
to $r_{\mathrm{max}}=7$ , and is resolved by setting $r_{\mathrm{max}}\geq 8$.
However, if $d$ is increased, we have observed that the smallest
$r_{\mathrm{max}}$ for successful BM training also increases. This coupling of
maximal bond dimension with $d$ is problematic, as one could no longer expect
a linear dependency between parameter size and the dimension $d$.

On the other hand, for TTNS-Sketch under (73), one is theoretically guaranteed
convergence to true model with $r_{e}\leq 4$, the proof of which can be
obtained by adapting the proof for Lemma 11. Moreover, for TTNS-Sketch with
sketch function in 73, increasing $d$ does not affect performance beyond the
sample complexity scaling in $d$ as discussed in Section 7.

##  9\. Conclusion

We describe an algorithm TTNS-Sketch, which obtains a Tree Tensor Network
States representation of a probability density from a collection of its
samples. This is done by formulating a sequence of equations, one for each
core, which can be solved independently. This is a general framework which
allows for arbitrary tree structures to be used. We have also compared this
algorithm with similar training-based regimes in the tensor train format, in
which we have shown much better performance from TTNS-Sketch even in a simple
case of periodic spin systems. For models which have interaction beyond
immediate neighbors, we have shown that TTNS-Sketch with perturbative
sketching greatly outperforms Chow-Liu. Theoretically, we have provided
condition for TTNS-Sketch to be a consistent estimator, as well as a
reasonable sample complexity upper bound.

While TTNS-Sketch might not necessarily be superior at approximating to an
arbitrary density, the numerical and theoretical evidence gathered point to
the conclusion that it is good at the inverse problem of solving for the
tensor component of a density with a TTNS ansatz. In other words, a
deterministic linear algebraic subroutine is sufficient to approximate a
$p^{\star}$ with a low-rank TTNS format. While this point has been made for
tensor completion problems, it is quite remarkable that statistical inference
of models with a TTNS ansatz can be shown to reduce to a linear algebraic
problem.

## References

##  Appendix A Proof of Theorem 7

###### Proof.

(Of Theorem 7) For simplicity, for the remainder of the proof, we fix a
structure for all of the high-order tensors we use. For $\Phi_{w\to k}$, one
reshapes it to the unfolding matrix $\Phi_{w\to k}(x_{\mathcal{L}(w)\cup
w};\alpha_{(w,k)})$. For $\Psi_{w\to k}$, one reshapes it to the unfolding
matrix $\Psi_{w\to k}(\alpha_{(w,k)};x_{\mathcal{R}(w)})$. For
$\Phi_{\mathcal{C}(k)\to k}$, one reshapes it to the unfolding matrix
$\Phi_{\mathcal{C}(k)\to k}(x_{\mathcal{L}(k)};\alpha_{(k,\mathcal{C}(k))})$.
For $G_{k}$, one reshapes it to the unfolding matrix
$G_{k}(\alpha_{(k,\mathcal{C}(k))};x_{k},\alpha_{(k,\mathcal{P}(k))})$. For
$p$, we will explicitly write out the unfolding matrix structure to avoid
ambiguity.

According to Condition 1, for any edge $w\to k$, one has

(74) $p(x_{\mathcal{L}(w)\cup w};x_{\mathcal{R}(w)})=\Phi_{w\to k}\Psi_{w\to
k}.$

Then, define $\Phi_{w\to
k}^{\dagger}\colon[r_{(w,k)}]\times\left[\prod_{i\in\mathcal{L}(w)\cup
w}n_{i}\right]\to\mathbb{R}$ and $\Psi_{w\to
k}^{\dagger}\colon\left[\prod_{i\in\mathcal{R}(w)}n_{i}\right]\times[r_{(w,k)}]\to\mathbb{R}$
so that $\Phi_{w\to k}^{\dagger}(\alpha_{(w,k)};x_{\mathcal{L}(w)\cup w})$
denotes the pseudoinverse of $\Phi_{w\to k}$, and $\Psi_{w\to
k}^{\dagger}(x_{\mathcal{R}(w)};\alpha_{(w,k)})$ denotes the pseudoinverse of
$\Psi_{w\to k}(\alpha_{(w,k)};x_{\mathcal{R}(w)})$. Then,

$\Phi_{w\to k}^{\dagger}\Phi_{w\to k}=\Psi_{w\to k}\Psi_{w\to
k}^{\dagger}=\mathbb{I}_{r_{(w,k)}}$

First, we prove uniqueness of each equation of (5) in the sense of least
squares. Note that an exact solution is guaranteed when $k$ is leaf, and so
one only needs to consider when $k$ is non-leaf. By assumption, $\Phi_{w\to
k}$ has full column rank of $r_{w\to k}$. In particular, the Kronecker product
structure ensures that $\Phi_{\mathcal{C}(k)\to k}$ has full column rank of
$\prod_{w\in\mathcal{C}(k)}r_{w\to k}$. Therefore, a unique of solution to (5)
exists in the sense of least squares.

Moreover, when $k$ is non-leaf and non-root, the pseudoinverse
$\Phi_{\mathcal{C}(k)\to
k}^{\dagger}(\alpha_{(k,\mathcal{C}(k))};x_{\mathcal{L}(k)})$ leads to the
following explicit construction of $G_{k}$:

(75) $G_{k}=\Phi_{\mathcal{C}(k)\to k}^{\dagger}\Phi_{k\to\mathcal{P}(k)},$

and likewise when $k$ is root, one has

(76) $G_{k}=\Phi_{\mathcal{C}(k)\to k}^{\dagger}p(x_{\mathcal{L}(k)};x_{k}).$

To verify that (5) holds exactly for the construction of $G_{k}$ in (75), one
can argue it suffices to check that

(77) $\Phi_{\mathcal{C}(k)\to k}\Phi_{\mathcal{C}(k)\to
k}^{\dagger}p(x_{\mathcal{L}(k)};x_{k\cup\mathcal{R}(k)})=p(x_{\mathcal{L}(k)};x_{k\cup\mathcal{R}(k)}),$

for which we give a brief explanation. When $k$ is root, (76) implies that
(77) coincides with (5) for when $k$ is root. When $k$ is non-root and non-
leaf, one can multiply both sides of (77) by
$\Psi_{k\to\mathcal{P}(k)}^{\dagger}$ and sum over $x_{\mathcal{R}(k)}$.
According to (75), the obtained equation coincides with (5) for when $k$ is
non-root and non-leaf.

It remains to show that (77) holds. For an edge $w\to k\in E$, define an
intermediate term $Q_{w\to k}$ as follows

$Q_{w\to k}(x_{\mathcal{L}(w)\cup w};y_{\mathcal{L}(w)\cup
w}):=\sum_{\alpha_{(w,k)}}\Phi_{w\to k}(x_{\mathcal{L}(w)\cup
w};\alpha_{(w,k)})\Phi_{w\to k}^{\dagger}(\alpha_{(w,k)};y_{\mathcal{L}(w)\cup
w}).$

Then, for a generic tensor
$f\colon[n_{1}]\times\ldots\times[n_{d}]\to\mathbb{R}$, one can define a
projection operator $P_{w\to k}$ as follows

$(P_{w\to k}f)(x_{1},\ldots,x_{d})=\sum_{y_{\mathcal{L}(w)\cup w}}Q_{w\to
k}(x_{\mathcal{L}(w)\cup w},y_{\mathcal{L}(w)\cup w})f(y_{\mathcal{L}(w)\cup
w},x_{\mathcal{R}(w)}).$

By commutativity of the sum operations involved, one has

$\displaystyle\Phi_{\mathcal{C}(k)\to k}\Phi_{\mathcal{C}(k)\to k}^{\dagger}f$
$\displaystyle=\sum_{y_{\mathcal{L}(k)}}\left(\prod_{w\in\mathcal{C}(k)}{Q_{w\to
k}(x_{\mathcal{L}(w)\cup w};y_{\mathcal{L}(w)\cup
w})}\right)f(x_{1},\ldots,x_{d})$
$\displaystyle=\sum_{\begin{subarray}{c}y_{\mathcal{L}(w)\cup w}\\\
w\in\mathcal{C}(k)\end{subarray}}\left(\prod_{w\in\mathcal{C}(k)}{Q_{w\to
k}(x_{\mathcal{L}(w)\cup w};y_{\mathcal{L}(w)\cup
w})}\right)f(x_{1},\ldots,x_{d})$
$\displaystyle=\left(\prod_{w\in\mathcal{C}(k)}P_{w\to k}\right)f$

Thus, (77) holds if one can show that $P_{w\to k}p=p$ for any
$w\in\mathcal{C}(k)$, but this fact is straightforward:

$P_{w\to k}p=\Phi_{w\to k}\Phi_{w\to k}^{\dagger}p(x_{\mathcal{L}(w)\cup
w};x_{\mathcal{R}(w)})=\Phi_{w\to k}\Phi_{w\to k}^{\dagger}\Phi_{w\to
k}\Psi_{w\to k}=\Phi_{w\to k}\Psi_{w\to k}=p,$

and thus (5) exactly holds for the constructed $\\{G_{i}\\}_{i=1}^{d}$.

Lastly, we prove that the solution $\\{G_{i}\\}_{i=1}^{d}$ forms a TTNS tensor
core of $p$. To show this result, it will be much more convenient to use the
notion of subgraph TTNS function in Definition 10. We remark that the
construction in Definition 10 is only arithmetic and has no dependency on this
theorem. For every node $k\in[d]$, define a subset
$\mathcal{S}_{k}:=\mathcal{L}(k)\cup\\{k\\}$. Then, for non-root $k$, we prove
that $\Phi_{k\to\mathcal{P}(k)}$ is the subgraph TTNS function over
$\\{G_{i}\\}_{i=1}^{d}$ and $T_{\mathcal{S}_{k}}$, i.e. one wishes to show

(78) $\Phi_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k},\alpha_{k\to\mathcal{P}(k)})=\sum_{\begin{subarray}{c}\alpha_{e}\\\
e\not=(k,\mathcal{P}(k))\end{subarray}}\prod_{i\in\mathcal{L}(k)\cup
k}G_{i}\left(x_{i},\alpha_{(i,\mathcal{N}(i))}\right).$

We prove (78) by mathematical induction. Notice that (5) proves (78) when $k$
is leaf node. Then, suppose that $k$ is non-leaf and suppose by mathematical
induction that $\Phi_{w\to k}$ satisfies (78) for all $w\in\mathcal{C}(k)$.
Then, one can rewrite (5) by plugging in $\Phi_{\mathcal{C}(k)\to k}$ by the
form of each $\Phi_{w\to k}$ according to (78), and the obtained equation is
exactly (78) for $\Phi_{k\to\mathcal{P}(k)}$. By induction over nodes by
topological order, (78) then holds for every non-root $k$.

By the same logic, now consider (5) when $k$ is root, and one plugs in
$\Phi_{\mathcal{C}(k)\to k}$ by the form of each $\Phi_{w\to k}$ according to
(78), whereby the obtained equation is exactly (3) in Definition 5, and thus
$\\{G_{i}\\}_{i=1}^{d}$ does form a TTNS tensor core of $p$. ∎

##  Appendix B Proof of Theorem 9

###### Proof.

(of Theorem 9) For any non-root $k$, note that $Z^{\star}_{k}$ is assumed to
be of rank $r_{(k,\mathcal{P}(k))}$ by (ii) in Condition 3. Let
$Q^{\star}_{k}$ be as in (16). In other words,
$Q^{\star}_{k}(\gamma_{(k,\mathcal{P}(k))};\alpha_{(k,\mathcal{P}(k))})$ is
formed by the rank-$r_{(k,\mathcal{P}(k))}$ SVD decomposition of
$Z^{\star}_{k}$ in the SystemForming step of Algorithm 1. Thus
$Q^{\star}_{k}(\gamma_{(k,\mathcal{P}(k))};\alpha_{(k,\mathcal{P}(k))})$ is of
rank $r_{(k,\mathcal{P}(k))}$, which means it has full column rank. We define

(79) $\Phi^{\star}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k},\alpha_{(k,\mathcal{P}(k))}):=\sum_{\gamma_{(k,\mathcal{P}(k))}}\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)\cup
k},\gamma_{(k,\mathcal{P}(k))})Q^{\star}_{k}(\gamma_{(k,\mathcal{P}(k))},\alpha_{(k,\mathcal{P}(k))}).$

Due to (i) in Condition 4 and $Q_{k}$ having full rank, one can conclude that
$\Phi^{\star}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k};\alpha_{(k,\mathcal{P}(k))})$ and
$\Phi^{\Delta}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)\cup
k};\alpha_{(k,\mathcal{P}(k))})$ have the same column space. Thus, there
exists $\Psi^{\star}_{(w,k)}$’s such that
$\\{\Phi^{\star}_{(w,k)},\Psi^{\star}_{(w,k)}\\}_{(w,k)\in E}$ forms a
collection of the low-rank decomposition of $p^{\star}$ in the sense of
Condition 1. We make the following claim, which also justifies $\star$ upper-
index in (79):

Claim: $\\{\Phi^{\star}_{(w,k)}\\}_{(w,k)\in E}$ as defined in (79) satisfies
Condition 2

The proof of the claim is somewhat technical and we will defer the proof after
stating how it proves this theorem.

Assume the claim is correct and $\\{\Phi^{\star}_{(w,k)}\\}_{(w,k)\in E}$
satisfies Condition 2. As a consequence, if one defines
$\\{A^{\star}_{i},B^{\star}_{i}\\}$ by

$\\{A^{\star}_{i},B^{\star}_{i}\\}_{i=1}^{d}\leftarrow\textsc{SystemForming}(\\{Z^{\star}_{w\to
k}\\}_{w\to k\in E},\\{Z^{\star}_{i}\\}_{i=1}^{d}),$

then one can alternatively define
$\\{A^{\star}_{i},B^{\star}_{i}\\}_{i=1}^{d}$ by (22) with

$\\{\Phi_{(w,k)}^{\Delta}\\}_{(w,k)\in
E}\leftarrow\\{\Phi_{(w,k)}^{\star}\\}_{(w,k)\in E}.$

Thus, with the alternative definition in (22), it follows that (23) is a
(possibly over-determined) linear system formed by a linear projection of the
linear system in (5), where chosen gauge is
$\\{\Phi^{\star}_{(w,k)}\\}_{(w,k)\in E}$.

Due to Theorem 7, (5) is an over-determined linear system with a unique and
exact solution. Theorem 7 guarantees an exact solution
$\\{G^{\star}_{i}\\}_{i=1}^{d}$ to (5), which is then necessarily an exact
solution to (23). If (23) satisfies uniqueness of solution, then the solution
to (23) is a solution to (5), which by Theorem 7 forms a TTNS tensor core of
$p^{\star}$. Therefore, it suffices to check uniqueness. Uniqueness of
solution to (23) when $k$ is leaf is trivial. When $k$ is non-leaf, note that
one can apply (iii) in Condition 3 with $\\{\Phi_{(w,k)}^{\star}\\}_{(w,k)\in
E}$ as the chosen gauge, which guarantees that
$A^{\star}_{k}(\beta_{(k,\mathcal{C}(k))},\alpha_{(k,\mathcal{C}(k))})$ has
the full column rank for every non-leaf $k$. In other words, one is guaranteed
uniqueness of the solution to (23), as desired. For the assertion on the
consistency of $\hat{G}_{k}$, note that
$\lim_{N\to\infty}\hat{G}_{k}=G^{\star}_{k}$ follows from the fact that
$\lim_{N\to\infty}\hat{A}_{k}=A^{\star}_{k}$ and
$\lim_{N\to\infty}\hat{B}_{k}=B^{\star}_{k}$.

We now prove that $\\{\Phi^{\star}_{(w,k)}\\}_{(w,k)\in E}$ satisfies
Condition 2. For a clear exposition, we adopt the unfolding 3-tensor structure
developed in Section 7.1-7.2. We remark that the 3-tensor construction is only
arithmetic and does not depend on validity of this theorem.

For $Z^{\star}_{k}$, we reshape it as
$Z^{\star}_{k}(\beta_{(k,\mathcal{C}(k))};x_{k};\gamma_{(k,\mathcal{P}(k))})$.
For $U^{\star}_{k}$, we reshape it as
$U^{\star}_{k}(\beta_{(k,\mathcal{C}(k))};x_{k};\alpha_{(k,\mathcal{P}(k))})$.
For $Q^{\star}_{k}$, we reshape it as
$Q^{\star}_{k}(\gamma_{(w,k)};1;\alpha_{(w,k)})$. For $S_{k},T_{k}$, we
reshape as $S_{k}(\beta_{(k,\mathcal{C}(k))};1;x_{\mathcal{L}(k)})$ and
$T_{k}(x_{\mathcal{R}(k)};1;\gamma_{(k,\mathcal{P}(k))})$. For
$\Phi^{\star}_{k\to\mathcal{P}(k)}$, we reshape it as
$\Phi^{\star}_{k\to\mathcal{P}(k)}(x_{\mathcal{L}(k)};x_{k};\alpha_{(k,\mathcal{P}(k))})$.
For $\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)\cup
k},\gamma_{(k,\mathcal{P}(k))})$, we reshape it as
$\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)};x_{k};\gamma_{(k,\mathcal{P}(k))})$.
For $p^{\star}$, we reshape it as
$p^{\star}(x_{\mathcal{L}(k)};x_{k};x_{\mathcal{R}(k)})$.

Then, by the construction of $Q^{\star}_{k}$ in the SystemForming step of
Algorithm 1, one has $U_{k}^{\star}=Z_{k}^{\star}\circ Q^{\star}_{k}$. By
(79), it follows
$\Phi^{\star}_{k\to\mathcal{P}(k)}:=\bar{\Phi}^{\star}_{k}\circ
Q^{\star}_{k}$. Condition 2 is satisfied if
$U_{k}^{\star}=S_{k}\circ\Phi^{\star}_{k\to\mathcal{P}(k)}.$ With such a
choice of unfolding 3-tensor, one obtains a simple proof as follows

$U_{k}^{\star}=Z_{k}^{\star}\circ Q^{\star}_{k}=S_{k}\circ p^{\star}\circ
T_{k}\circ Q^{\star}_{k}=S_{k}\circ\bar{\Phi}^{\star}_{k}\circ
Q^{\star}_{k}=S_{k}\circ\Phi^{\star}_{k\to\mathcal{P}(k)},$

where the first equality comes from $Z_{k}^{\star}=S_{k}\circ p^{\star}\circ
T_{k}$, the second equality comes from $\bar{\Phi}^{\star}_{k}=p^{\star}\circ
T_{k}$, and the third equality comes from
$\Phi^{\star}_{k\to\mathcal{P}(k)}=\bar{\Phi}^{\star}_{k}\circ Q^{\star}_{k}$.
Thus the claim holds and we are done.

∎

##  Appendix C Proof of Lemma 11

######  Lemma 32.

Suppose $p$ satisfies the Markov property given a rooted tree $([d],E)$. For
any subsets $\mathcal{S}_{1}\subset\mathcal{L}(k)\cup k$ and
$\mathcal{S}_{2}\subset\mathcal{R}(k)$,

  * (i)

$\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}p(x_{\mathcal{S}_{1}};x_{\mathcal{S}_{2}})$
and
$\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{P}(k)}p(x_{\mathcal{S}_{1}};x_{\mathcal{P}(k)})$
have the same column space if $\mathcal{P}(k)\in\mathcal{S}_{2}$,

  * (ii)

$\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}p(x_{\mathcal{S}_{1}};x_{\mathcal{S}_{2}})$
and $\mathcal{M}_{k\cup\mathcal{S}_{2}}p(x_{k};x_{\mathcal{S}_{2}})$ have the
same row space if $k\in\mathcal{S}_{1}$.

###### Proof.

Define a conditional probability tensor as follows:

$\mathcal{M}_{\mathcal{S}_{1}|\mathcal{S}_{2}}p(x_{\mathcal{S}_{1}},x_{\mathcal{S}_{2}}):=\mathbb{P}_{X\sim
p}\left[X_{\mathcal{S}_{1}}=x_{\mathcal{S}_{1}}|X_{\mathcal{S}_{2}}=x_{\mathcal{S}_{2}}\right].$

Due to the conditional independence property for graphical models, one can
write

$\displaystyle\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}p(x_{\mathcal{S}_{1}},x_{\mathcal{S}_{2}})$
$\displaystyle=\mathcal{M}_{\mathcal{S}_{1}|\mathcal{P}(k)}p(x_{\mathcal{S}_{1}},x_{\mathcal{P}(k)})\mathcal{M}_{\mathcal{P}(k)}p(x_{\mathcal{P}(k)})\mathcal{M}_{\mathcal{S}_{2}|\mathcal{P}(k)}p(x_{\mathcal{S}_{2}\backslash\mathcal{P}(k)},x_{\mathcal{P}(k)})$
$\displaystyle=\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{P}(k)}p(x_{\mathcal{S}_{1}},x_{\mathcal{P}(k)})\mathcal{M}_{\mathcal{S}_{2}|\mathcal{P}(k)}p(x_{\mathcal{S}_{2}\backslash\mathcal{P}(k)},x_{\mathcal{P}(k)})$

Thus, the column space of
$\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}p(x_{\mathcal{S}_{1}};x_{\mathcal{S}_{2}})$
depends solely on
$\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{P}(k)}(x_{\mathcal{S}_{1}};x_{\mathcal{P}(k)})$.
Therefore, (i) holds.

Similarly,

$\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}p(x_{\mathcal{S}_{1}},x_{\mathcal{S}_{2}})=\mathcal{M}_{\mathcal{S}_{1}|k}p(x_{\mathcal{S}_{1}\backslash
k},x_{k})\mathcal{M}_{k\cup\mathcal{S}_{2}}p(x_{k},x_{\mathcal{S}_{2}}),$

which shows that the row space of
$\mathcal{M}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}p(x_{\mathcal{S}_{1}};x_{\mathcal{S}_{2}})$
depends solely on
$\mathcal{M}_{k\cup\mathcal{S}_{2}}p(x_{k};x_{\mathcal{S}_{2}})$. Therefore,
(ii) holds. ∎

###### Proof.

(of Lemma 11) We will verify that Condition 3 holds. The Markov sketch
function is quite special, and we often refer to a concept of natural
identification. To make this concept rigorous, if two matrices $A(x;y)$ and
$A^{\prime}(z;w)$ are said to have a _natural identification_ , it then means
that $A(x;y)=A^{\prime}(z;w)$ entry-wise as matrices. In particular, if one
has a natural identification $A(x;y)=A^{\prime}(z;w)$, then $A$ and
$A^{\prime}$ share column space, row space, and rank.

By the property of right sketch function in Markov sketch function, one has
the natural identification $\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)\cup
k};\gamma_{(k,\mathcal{P}(k))})=\mathcal{M}_{\mathcal{L}(k)\cup
k\cup\mathcal{P}(k)}p^{\star}(x_{\mathcal{L}(k)\cup k};x_{\mathcal{P}(k)})$.
Lemma 32 then shows that the column space of
$\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)\cup k};\gamma_{(k,\mathcal{P}(k))})$
equals to that of $p^{\star}(x_{\mathcal{L}(k)\cup k};x_{\mathcal{R}(k)})$. By
Condition 1, the column space of $p^{\star}(x_{\mathcal{L}(k)\cup
k};x_{\mathcal{R}(k)})$ equals to that of any
$\Phi^{\Delta}_{(w,k)}(x_{\mathcal{L}(k)\cup k};\alpha_{(k,\mathcal{P}(k))})$,
and so (i) holds.

Similarly, due to Markov sketch function, one has the natural identification

$Z_{k}^{\star}(\beta_{(k,\mathcal{C}(k))},x_{k};\gamma_{(k,\mathcal{P}(k))})=\mathcal{M}_{\mathcal{C}(k)\cup
k\cup\mathcal{P}(k)}p(x_{\mathcal{C}(k)\cup k};x_{\mathcal{P}(k)}).$

By Lemma 32 and the natural identification of $Z_{k}^{\star}$, for any every
non-leaf and non-root $k$, it follows that $Z_{k}^{\star}$ has the same row
space as that of

$\bar{\Phi}^{\star}_{k}(x_{\mathcal{L}(k)\cup
k};\gamma_{(k,\mathcal{P}(k))})=\mathcal{M}_{\mathcal{L}(k)\cup
k\cup\mathcal{P}(k)}p^{\star}(x_{\mathcal{L}(k)\cup k};x_{\mathcal{P}(k)}).$

Hence, the rank of $Z_{k}^{\star}$ equals to the rank of
$\bar{\Phi}^{\star}_{k}$. By Lemma 32, the column space of
$\bar{\Phi}^{\star}_{k}$ equals to the column space of
$p^{\star}(x_{\mathcal{L}(k)\cup k};x_{\mathcal{R}(k)})$. Thus, the rank of
$Z_{k}^{\star}$ equals to $r_{(k,\mathcal{P}(k))}$ and (ii) holds.

Because (i) and (ii) hold, the proof of Theorem 9 actually shows that there
exists a gauge $\\{\Phi^{\star}_{(w,k)}\\}_{(w,k)\in E}$ which satisfies
Condition 2. To verify (iii), it suffices to check (iii) for the gauge
$\\{\Phi^{\star}_{(w,k)}\\}_{(w,k)\in E}$, because $A^{\star}_{k}$ having full
column rank leads to any $A^{\Delta}_{k}$ having full column rank.

Moreover, it suffices to show that each $A^{\star}_{w\to
k}(\beta_{(w,k)};\alpha_{(w,k)})$ has full column rank of $r_{w\to k}$. If
this holds, then it follows that
$A^{\star}_{k}=\bigotimes_{w\in\mathcal{C}(k)}A^{\star}_{w\to k}$ has full
column rank of $\prod_{w\in\mathcal{C}(k)}r_{w\to k}$. By the SVD step in
SystemForming, recall that the column space of
$Q_{w}^{\star}(\gamma_{(w,k)};\alpha_{(w,k)})$ is the same as the column space
of
$\left(Z^{\star}_{w}\right)^{\top}(\gamma_{(w,k)};\beta_{(w,\mathcal{C}(w))},x_{w})$.
By the natural identification of

$\left(Z^{\star}_{w}\right)^{\top}(\gamma_{(w,k)};x_{w},\beta_{(w,\mathcal{C}(w))})=\mathcal{M}_{k\cup
w\cup\mathcal{C}(w)}p(x_{k};x_{w\cup\mathcal{C}(w)}),$

we know that the column space of
$Q_{w}^{\star}(\gamma_{(w,k)};\alpha_{(w,k)})$ is the same as that of
$\mathcal{M}_{k\cup w\cup\mathcal{C}(w)}p(x_{k};x_{w\cup\mathcal{C}(w)})$. By
Lemma 32, it then follows that the column space of
$Q_{w}^{\star}(\gamma_{(w,k)};\alpha_{(w,k)})$ coincides with that of
$\mathcal{M}_{k\cup w}p(x_{k};x_{w})$.

Moreover, $Z^{\star}_{w\to k}$ has the natural identification $Z^{\star}_{w\to
k}(\beta_{(w,k)};\gamma_{(w,k)})=\mathcal{M}_{w\cup k}p(x_{w};x_{k})$, and so
the column space of $Z^{\star}_{w\to k}(\beta_{(w,k)};\gamma_{(w,k)})$
coincides with that of $\mathcal{M}_{w\cup k}p(x_{w};x_{k})$.

By (17), one has

$A^{\star}_{w\to k}(\beta_{(w,k)};\alpha_{(w,k)})=Z^{\star}_{w\to
k}(\beta_{(w,k)};\gamma_{(w,k)})Q^{\star}_{w}(\gamma_{(w,k)};\alpha_{(w,k)}),$

and so the column space of $A^{\star}_{w\to k}$ coincides with that of

$\mathcal{M}_{w\cup k}p(x_{w};x_{k})\mathcal{M}_{k\cup
w}p(x_{k};x_{w})=\mathcal{M}_{w\cup k}p(x_{w};x_{k})\left(\mathcal{M}_{w\cup
k}p(x_{w};x_{k})\right)^{\top}.$

Thus, the rank of $A^{\star}_{w\to k}$ coincides with that of
$\mathcal{M}_{w\cup k}p(x_{w};x_{k})\left(\mathcal{M}_{w\cup
k}p(x_{w};x_{k})\right)^{\top}$, which in turn coincides with the rank of
$\mathcal{M}_{w\cup k}p(x_{w};x_{k})$. By applying Lemma 32, the rank of
$\mathcal{M}_{w\cup k}p(x_{w};x_{k})$ equals to $r_{(w,k)}$, and so (iii)
holds.

∎

##  Appendix D Proof of Theorem 12

After applying the left and right sketching, one has the following form on
$Z^{\star}_{k}$:

(80)
$Z^{\star}_{k}(x_{k},\beta_{(k,\mathcal{N}(k))})=\sum_{\begin{subarray}{c}\beta_{e}\\\
k\not\in e\end{subarray}}\sum_{\begin{subarray}{c}x_{i}\\\
i\not=k\end{subarray}}p^{\star}(x_{1},\ldots,x_{d})\prod_{i\not=k}s_{i}(x_{i},\beta_{(i,\mathcal{N}(i))}).$

Let $\mathcal{S}_{k}:=[d]-\\{k\\}$, and let $T_{\mathcal{S}_{k}}$ be the
subgraph of $T$ with vertex set being $\mathcal{S}_{k}$. Using the definition
of subgraph TTNS function in Definition 10, define a tensor

$H_{k}\colon\prod_{i\in[d],i\not=k}[n_{i}]\times\prod_{w\in\mathcal{N}(k)}[\beta_{(w,k)}]\to\mathbb{R}$

as the subgraph TTNS function over $\\{s_{i}\\}_{i\not=k}$ and
$T_{\mathcal{S}_{k}}$, i.e.

(81)
$H_{k}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))})=\sum_{\begin{subarray}{c}\alpha_{e}\\\
k\not\in
e\end{subarray}}\prod_{i\not=k}s_{i}\left(x_{i},\beta_{(i,\mathcal{N}(i))}\right).$

Then (80) is equivalent to the following equation:

(82)
$Z^{\star}_{k}(x_{k},\beta_{(k,\mathcal{N}(k))})=\sum_{\begin{subarray}{c}x_{w}\\\
w\not=k\end{subarray}}p^{\star}(x_{1},\ldots,x_{d})H_{k}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))}).$

From (81), one sees that $H_{k}$ is multi-linear in $\\{s_{i}\\}_{i\not=k}$.
We thus can apply the binomial theorem to derive a structural form on $H_{k}$
as a sum of secondary terms. To do so, let $\mathcal{S}$ be an arbitrary
subset of $\mathcal{S}_{k}$, and define a tensor

$H_{k;\mathcal{S}}\colon\prod_{i\in[d],i\not=k}[n_{i}]\times\prod_{w\in\mathcal{N}(k)}[\beta_{(w,k)}]\to\mathbb{R}$

as the subgraph TTNS function over $T_{\mathcal{S}_{k}}$ and
$\\{\Delta_{i}\\}_{i\in\mathcal{S}_{k}}\cup\\{O_{j}\\}_{j\in\mathcal{S}_{k}-\mathcal{S}}$,
i.e.

$H_{k;\mathcal{S}}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))})=\sum_{\begin{subarray}{c}\alpha_{e}\\\
k\not\in
e\end{subarray}}\prod_{i\in\mathcal{S}}\Delta_{i}\left(x_{i},\beta_{(i,\mathcal{N}(i))}\right)\prod_{j\in\mathcal{S}_{k}-\mathcal{S}}O_{j}\left(x_{j},\beta_{(j,\mathcal{N}(j))}\right).$

We now use the fact that
$O_{j}\left(x_{j},\beta_{(j,\mathcal{N}(j))}\right)=1$ in Condition 6, and so

(83)
$H_{k;\mathcal{S}}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))})=\sum_{\begin{subarray}{c}\alpha_{e}\\\
k\not\in
e\end{subarray}}\prod_{i\in\mathcal{S}}\Delta_{i}\left(x_{i},\beta_{(i,\mathcal{N}(i))}\right)=\sum_{\beta_{e},k\not\in
e}\Delta_{\mathcal{S}}(x_{\mathcal{S}},\beta_{\partial\mathcal{S}}),$

where the second equality follows from the Definition of
$\Delta_{\mathcal{S}}$ in (37).

By applying the binomial theorem over the fact that
$s_{i}=\epsilon\Delta_{i}+O_{i}$, one sees that $H_{k}$ is a sum of $2^{d-1}$
terms, each of which formed by corresponding to one $H_{k;\mathcal{S}}$, i.e.

(84)
$H_{k}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))})=\sum_{l=0}^{d-1}\epsilon^{l}\sum_{\mathcal{S}\subset[d]-\\{k\\},|\mathcal{S}|=l}H_{k;\mathcal{S}}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))}).$

Define $Z^{\star}_{k;\mathcal{S}}$ as the following tensor:

(85)
$Z^{\star}_{k}(x_{k},\beta_{(k,\mathcal{N}(k))}):=\sum_{\begin{subarray}{c}x_{w}\\\
w\not=k\end{subarray}}p^{\star}(x_{1},\ldots,x_{d})H_{k;\mathcal{S}}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))}).$

The proof that $Z^{\star}_{k;\mathcal{S}}$ satisfies (39) is a simple result
of exchanging summation order:

$\displaystyle\sum_{\begin{subarray}{c}x_{w}\\\
w\not=k\end{subarray}}p^{\star}(x_{1},\ldots,x_{d})H_{k;\mathcal{S}}(x_{[d]-\\{k\\}},\beta_{(k,\mathcal{N}(k))})$
$\displaystyle=$ $\displaystyle\sum_{\begin{subarray}{c}x_{w}\\\
w\in\mathcal{S}\end{subarray}}\left(\sum_{\begin{subarray}{c}x_{w}\\\
w\in\mathcal{S}_{k}-\mathcal{S}\end{subarray}}p^{\star}(x_{1},\ldots,x_{d})\right)\left(\sum_{\beta_{e},k\not\in
e}\Delta_{\mathcal{S}}(x_{\mathcal{S}},\beta_{\partial\mathcal{S}})\right)$
$\displaystyle=$ $\displaystyle\sum_{\beta_{e},k\not\in
e}\left(\sum_{x_{\mathcal{S}}}\mathcal{M}_{\mathcal{S}\cup\\{k\\}}p^{\star}(x_{k},x_{\mathcal{S}})\Delta_{\mathcal{S}}(x_{\mathcal{S}},\beta_{\partial\mathcal{S}})\right).$

Due to the linear relationship between $H_{k}$ and $Z^{\star}_{k}$ in (82), it
follows that the structural form of $H_{k}$ in (84) leads to the structural
form for $Z^{\star}_{k}$ in (38), as desired.