over one representative per class. Such equivalence classes are organized by
the rank of the matrix $C$. The case that $\operatorname{rank}C=0$ is trivial,
as we can take $(C,D)=(0,\mathbb{1})$ as a representative, so in what follows
we will assume $\operatorname{rank}C=r$ with $0<r\leq n$. We would like to
identify a particular simple representative for each class in order to make
the sum involved in the Eisenstein series more concrete. Here we will briefly
review the construction of [76], where it is shown that for each rank $r$ we
can rephrase the sum over representatives as a sum over $r\times r$ matrices
$C^{(r)}$ and $D^{(r)}$ with $\det C^{(r)}\neq 0$, augmented by a sum over
primitive $n\times r$ matrices $Q^{(n,r)}$.

We start by seeking two unimodular $n\times n$ matrices $U_{1},U_{2}$ such
that [76]

$C=U_{1}^{-1}\begin{pmatrix}C_{1}&0\\\ 0&0\end{pmatrix}U_{2}^{T},$ (B.9)

where $C_{1}$ is an $r\times r$ matrix with $\det C_{1}\neq 0$, and

$D=U_{1}^{-1}\begin{pmatrix}D_{1}&D_{2}\\\
D_{3}&D_{4}\end{pmatrix}U_{2}^{-1},$ (B.10)

where $D_{1}$ is an $r\times r$ matrix. If $(C,D)$ is a symmetric pair, then
so is $U_{1}(C,D)$, and from the symmetry property (B.6) of $U_{1}(C,D)$ one
can show that $(C_{1},D_{1})$ also forms a symmetric pair and deduce that
$D_{3}=0$. By making the replacement

$U_{1}\to\begin{pmatrix}\mathbb{1}&D_{2}\\\ 0&D_{4}\end{pmatrix}U_{1},$ (B.11)

(B.9) and (B.10) simplify to

$\displaystyle U_{1}C$ $\displaystyle\to\begin{pmatrix}C_{1}&0\\\
0&0\end{pmatrix}U_{2}^{T}$ (B.12) $\displaystyle U_{1}D$
$\displaystyle\to\begin{pmatrix}D_{1}&0\\\
0&\mathbb{1}\end{pmatrix}U_{2}^{-1}$

It follows from this construction that the pair $(C_{1},D_{1})$ is also
necessarily coprime [76].

Furthermore, if one acts on $U_{2}$ from the right by a unimodular matrix that
only has a nontrivial upper-left $r\times r$ block, for example

$U_{2}\to U_{2}\begin{pmatrix}U_{3}&0\\\ 0&\mathbb{1}\end{pmatrix},$ (B.13)

where $U_{3}$ is an $r\times r$ unimodular matrix, then one can simply make
the replacement $(C_{1},D_{1})\to(C_{1}U_{3}^{T},D_{1}U_{3}^{-1})$ and nothing
is changed. To take account of this equivalence, let us introduce the $n\times
r$ matrix $Q^{(n,r)}$, formed by taking the first $r$ columns of $U_{2}$. We
are thus motivated to introduce the equivalence class $\\{Q^{(n,r)}\\}$

$Q^{(n,r)}\sim Q^{(n,r)}U_{3},~{}\text{for $U_{3}$ $r\times r$ unimodular}$
(B.14)

of primitive $n\times r$ matrices that can be completed to a unimodular
$n\times n$ matrix (that we refer to as $U_{2}$ above). Importantly, in the
maximal-rank case of $r=n$ we have only $Q^{(n,n)}=\mathbb{1}$.

Finally, by replacing

$U_{1}\to\begin{pmatrix}U_{4}&0\\\ 0&\mathbb{1}\end{pmatrix}U_{1}$ (B.15)

with $U_{4}$ an $r\times r$ unimodular matrix, we have $(C_{1},D_{1})\to
U_{4}(C_{1},D_{1})$ and so these pairs are also associated. Thus one is free
to choose $(C_{1},D_{1})$ as any representative of the class
$\\{C_{1},D_{1}\\}$.

The upshot of this construction is that one can associate to each equivalence
class $\\{C,D\\}$ where $\operatorname{rank}C=r$ the equivalence classes of
$r\times r$ matrices $\\{C^{(r)},D^{(r)}\\}$ with $\det C^{(r)}\neq 0$,
augmented by the equivalence class of primitive matrices $\\{Q^{(n,r)}\\}$,
such that

$\displaystyle C$ $\displaystyle=\begin{pmatrix}C^{(r)}&0\\\
0&0\end{pmatrix}U^{T}$ (B.16) $\displaystyle D$
$\displaystyle=\begin{pmatrix}D^{(r)}&0\\\ 0&\mathbb{1}\end{pmatrix}U^{-1}$
$\displaystyle U$ $\displaystyle=(Q^{(n,r)},*),$

where $U$ is the completion of $Q^{(n,r)}$ into a unimodular matrix. In [76]
it is shown that this association is in fact one-to-one. In fact, since
$C^{(r)}$ is invertible, one can further define the matrix
$R=(C^{(r)})^{-1}D^{(r)}$, and in [76] it is shown that the set of all
equivalence classes $\\{C^{(r)},D^{(r)}\\}$ with $\det C^{(r)}\neq 0$ is
precisely the set of all rational symmetric $r\times r$ matrices $R$, and the
map is one-to-one.

###  B.2 Fourier decomposition of the higher-degree Eisenstein series

To begin unpackaging the sum in the definition of the Eisenstein series,
recall from the previous subsection the one-to-one correspondence between the
equivalence class $\\{C,D\\}$ and that of $r\times r$ matrices
$\\{C^{(r)},D^{(r)}\\}$ where $r=\operatorname{rank}C$, $\det C^{(r)}\neq 0$
and $\\{Q^{(n,r)}\\}$ of primitive $n\times r$ matrices that can be completed
to a unimodular $n\times n$ matrix. Then, since in the case that
$\operatorname{rank}C=r$

$\det(C\Omega+D)=\pm\det(C^{(r)}\Omega[Q^{(n,r)}]+D^{(r)})$ (B.17)

we can rewrite (B.3) as

${E^{(n)}_{s}(\Omega)\over(\det\operatorname{Im}\Omega)^{s}}=1+\sum_{r=1}^{n}\sum_{\\{C^{(r)},D^{(r)}\\}}\sum_{\\{Q^{(n,r)}\\}}\det(C^{(r)})^{-2s}|\det(\Omega[Q^{(n,r)}]+(C^{(r)})^{-1}D^{(r)})|^{-2s}.$
(B.18)

Recall that the sum over $\\{C^{(r)},D^{(r)}\\}$ can be replaced by a sum over
symmetric rational $r\times r$ matrices $R=(C^{(r)})^{-1}D^{(r)}$. Then one
can find $r\times r$ unimodular matrices $U,V$ such that

$U^{-1}RV=\operatorname{diag}({p_{i}/q_{i}}),~{}\text{where $(p_{i},q_{i})=1$
and ${p_{i}/q_{i}}\geq 0$.}$ (B.19)

The ratios $p_{i}/q_{i}$ are called the elementary divisors of $R$. Then one
can write the determinant of $C^{(r)}$ in terms of the product of the
denominators of the elementary divisors of $R$ [76]

$\nu(R)\equiv\det C^{(r)}=\prod_{i=1}^{r}q_{i}.$ (B.20)

Finally, this allows us to rewrite the Eisenstein series in terms of a sum
over symmetric rational matrices

$\displaystyle{E^{(n)}_{s}(\Omega)\over(\det\operatorname{Im}\Omega)^{s}}$
$\displaystyle=1+\sum_{r=1}^{n}\sum_{\\{Q^{(n,r)}\\}}\sum_{\begin{subarray}{c}P=P^{T}\\\
\rm rational\end{subarray}}\nu(P)^{-2s}|\det(\Omega[Q^{(n,r)}]+P)|^{-2s}$
(B.21)
$\displaystyle=1+\sum_{r=1}^{n}\sum_{\\{Q^{(n,r)}\\}}\sum_{\begin{subarray}{c}R=R^{T}\\\
{\rm rational}\,{\rm mod}\,1\end{subarray}}\sum_{\begin{subarray}{c}N=N^{T}\\\
{\rm integral}\end{subarray}}\nu(R)^{-2s}|\det(\Omega[Q^{(n,r)}]+R+N)|^{-2s},$

where in the second line we wrote $P=R+N$ where $R$ is a symmetric matrix with
entries that are rational mod one, and $N$ is a symmetric integral matrix.

To proceed we define the function

$\psi_{s,r}(\Omega)=\sum_{\begin{subarray}{c}N=N^{T}\\\ {\rm
integral}\end{subarray}}|\det(\Omega+N)|^{-2s},$ (B.22)

where $\Omega$ and $N$ are understood to be $r\times r$ matrices. By
construction this function is invariant under integral shifts of the real part
of $\Omega\equiv X+iY$, $X\to X+N$ for $N$ symmetric and integral, and thus
admits a Fourier decomposition

$\psi_{s,r}(\Omega)=\sum_{\begin{subarray}{c}J=J^{T}\\\ {\rm semi-
integral}\end{subarray}}\widehat{\psi}_{s,r}(Y,J)e^{2\pi i\sigma(JX)},$ (B.23)

where, for symmetric $r\times r$ matrices $A,B$, $\sigma$ is defined by the
trace

$\sigma(AB)={\rm
tr\,}(AB)=\sum_{i=1}^{r}A_{ii}B_{ii}+\sum_{i<j}^{r}2A_{ij}B_{ij}.$ (B.24)

The condition that $J$ be symmetric and semi-integral requires

$\displaystyle J_{ii}$ $\displaystyle\in\mathbb{Z}$ (B.25) $\displaystyle
J_{ij}$ $\displaystyle=J_{ji}\in{1\over 2}\mathbb{Z},~{}i<j.$

The Fourier coefficients $\widehat{\psi}_{s,r}$ can be written in terms of an
integral over the unit $X$ cube $\mathcal{X}$

$\displaystyle\widehat{\psi}_{s,r}(Y,J)$
$\displaystyle=\int_{\mathcal{X}}[dX]\,\psi_{s,r}(\Omega)e^{-2\pi
i\sigma(JX)}$ (B.26)
$\displaystyle=\int_{-\infty}^{\infty}[dX]\,|\det\Omega|^{-2s}e^{-2\pi
i\sigma(JX)},$

where $[dX]=\prod_{i\leq j}dX_{ij}$ is the flat measure and in the second line
we used the explicit form of $\psi_{s}$ as a sum over integral shifts of
$\Omega$ and the invariance of the exponential factor under such shifts. After
some standard manipulations, one can show that [76]

$\widehat{\psi}_{s,r}(Y,J)={2^{r}\pi^{2rs}\over\Gamma_{r}(s)^{2}}h_{s,r}(Y,J),$
(B.27)

where

$\displaystyle h_{s,r}(Y,J)$ $\displaystyle=\int_{\Delta\pm
J>0}[d\Delta]\,e^{-2\pi\sigma(\Delta Y)}\det(\Delta+J)^{s-{1\over
2}(r+1)}\det(\Delta-J)^{s-{1\over 2}(r+1)}$ (B.28)
$\displaystyle\Gamma_{r}(s)$ $\displaystyle=\pi^{{1\over
4}r(r-1)}\prod_{j=0}^{r-1}\Gamma(s-j/2).$

The key to this rewriting is the following identity

$\int_{H>0}[dH]\,e^{i\sigma(H\Omega)}\det(H)^{s-{r+1\over
2}}=\Gamma_{r}(s)\det(-i\Omega)^{-s},$ (B.29)

where the integral is over symmetric positive-definite $r\times r$ matrices
$H$. The functions $h_{s,r}(Y,J)$ are sometimes known as confluent
hypergeometric functions on tube domains [83], and it is by studying
properties of these functions that the functional equation (B.33) satisfied by
the meromorphic continuation of the higher-degree Eisenstein series was
established.

Thus the Fourier decomposition of the degree $n$ Eisenstein series (B.21) can
be written as

$\displaystyle{E^{(n)}_{s}(\Omega)\over(\det\operatorname{Im}\Omega)^{s}}$
$\displaystyle=1+\sum_{r=1}^{n}\sum_{\begin{subarray}{c}J^{(r)}=(J^{(r)})^{T}\\\
{\rm semi-
integral}\end{subarray}}\sum_{\\{Q^{(n,r)}\\}}S_{s,r}(J)\widehat{\psi}_{s,r}(Y[Q],J)e^{2\pi
i\sigma(X[Q]J)}$ (B.30)
$\displaystyle=1+\sum_{r=1}^{n}\sum_{\begin{subarray}{c}J^{(r)}=(J^{(r)})^{T}\\\
{\rm semi-
integral}\end{subarray}}\sum_{\\{Q^{(n,r)}\\}}{2^{r}\pi^{2rs}\over\Gamma_{r}(s)^{2}}S_{s,r}(J)h_{s,r}(Y[Q],J)e^{2\pi
i\sigma(X[Q]J)},$

where $S_{s,r}(J)$ is Siegel’s “singular series”

$S_{s,r}(J)=\sum_{\begin{subarray}{c}R=R^{T}\\\ {\rm rational}\,{\rm
mod}\,1\end{subarray}}\nu(R)^{-2s}e^{2\pi i\sigma(JR)},$ (B.31)

and in the summand on the right-hand side we have omitted for the sake of
brevity the superscripts on the matrices $Q^{(n,r)}$ and $J^{(r)}$ denoting
their sizes. Some special values of the singular series are known explicitly,
for example in the case that $J$ is the zero matrix we have [76]

$S_{s,r}(0)={\zeta(2s-r)\over\zeta(2s)}\prod_{j=1}^{r}{\zeta(4s-r-j)\over\zeta(4s-2j)}.$
(B.32)

The sum (B.3) converges provided $\operatorname{Re}s>{n+1\over 2}$. Like the
genus-one Eisenstein series, it can be formally defined by analytic
continuation in the complex $s$ plane away from this domain, but the argument
relating it to a partition function of an averaged Narain lattice CFT
established in [59] only holds for half-integer $s>{n+1\over 2}$. The
meromorphic continuation of the Eisenstein series can be shown to satisfy the
functional equation [84, 83, 85, 75]

$\mathcal{E}_{s}^{(n)}(\Omega)=\mathcal{E}^{(n)}_{{n+1\over 2}-s}(\Omega)$
(B.33)

where

$\mathcal{E}^{(n)}_{s}(\Omega)=\Lambda(s)\left(\prod_{j=1}^{\lfloor{n\over
2}\rfloor}\Lambda(2s-j)\right)E^{(n)}_{s}(\Omega),\quad\Lambda(s)=\pi^{-s}\Gamma(s)\zeta(2s).$
(B.34)

The function $\mathcal{E}^{(n)}_{s}(\Omega)$ can be shown to have poles of
finite order at $s={k\over 4}$ for $k=0,1,\ldots,2n+2$, including a simple
pole at $s={n+1\over 2}$ with residue $\prod_{j=1}^{\lfloor{n\over
2}\rfloor}\Lambda\left(j+{1\over 2}\right)$ [75].

## References

  * [1] A. Strominger and C. Vafa, Microscopic origin of the Bekenstein-Hawking entropy, Phys. Lett. B 379 (1996) 99–104, [hep-th/9601029].
  * [2] Y. Sekino and L. Susskind, Fast Scramblers, JHEP 10 (2008) 065, [arXiv:0808.2096].
  * [3] S. H. Shenker and D. Stanford, Black holes and the butterfly effect, JHEP 03 (2014) 067, [arXiv:1306.0622].
  * [4] J. Maldacena, S. H. Shenker, and D. Stanford, A bound on chaos, JHEP 08 (2016) 106, [arXiv:1503.01409].
  * [5] J. S. Cotler, G. Gur-Ari, M. Hanada, J. Polchinski, P. Saad, S. H. Shenker, D. Stanford, A. Streicher, and M. Tezuka, Black Holes and Random Matrices, JHEP 05 (2017) 118, [arXiv:1611.04650]. [Erratum: JHEP 09, 002 (2018)].
  * [6] J. L. Cardy, Operator Content of Two-Dimensional Conformally Invariant Theories, Nucl. Phys. B 270 (1986) 186–204.
  * [7] A. Strominger, Black hole entropy from near horizon microstates, JHEP 02 (1998) 009, [hep-th/9712251].
  * [8] J. Brown and M. Henneaux, Central Charges in the Canonical Realization of Asymptotic Symmetries: An Example from Three-Dimensional Gravity, Commun. Math. Phys. 104 (1986) 207–226.
  * [9] A. Castro, M. R. Gaberdiel, T. Hartman, A. Maloney, and R. Volpato, The Gravity Dual of the Ising Model, Phys. Rev. D 85 (2012) 024032, [arXiv:1111.1987].
  * [10] C.-M. Jian, A. W. Ludwig, Z.-X. Luo, H.-Y. Sun, and Z. Wang, Establishing strongly-coupled 3D AdS quantum gravity with Ising dual using all-genus partition functions, arXiv:1907.06656.
  * [11] M. R. Gaberdiel and R. Gopakumar, An AdS3 Dual for Minimal Model CFTs, Phys. Rev. D 83 (2011) 066007, [arXiv:1011.2986].
  * [12] S. Hellerman, A Universal Inequality for CFT and Quantum Gravity, JHEP 08 (2011) 130, [arXiv:0902.2790].
  * [13] D. Friedan and C. A. Keller, Constraints on 2d CFT partition functions, JHEP 10 (2013) 180, [arXiv:1307.6562].
  * [14] S. Collier, Y.-H. Lin, and X. Yin, Modular Bootstrap Revisited, JHEP 09 (2018) 061, [arXiv:1608.06241].
  * [15] N. Afkhami-Jeddi, T. Hartman, and A. Tajdini, Fast Conformal Bootstrap and Constraints on 3d Gravity, JHEP 05 (2019) 087, [arXiv:1903.06272].
  * [16] T. Hartman, D. Mazáč, and L. Rastelli, Sphere Packing and Quantum Gravity, JHEP 12 (2019) 048, [arXiv:1905.01319].
  * [17] Y. Kusuki, Light Cone Bootstrap in General 2D CFTs and Entanglement from Light Cone Singularity, JHEP 01 (2019) 025, [arXiv:1810.01335].
  * [18] S. Collier, Y. Gobeil, H. Maxfield, and E. Perlmutter, Quantum Regge Trajectories and the Virasoro Analytic Bootstrap, JHEP 05 (2019) 212, [arXiv:1811.05710].
  * [19] S. Collier, A. Maloney, H. Maxfield, and I. Tsiares, Universal dynamics of heavy operators in CFT2, JHEP 07 (2020) 074, [arXiv:1912.00222].
  * [20] A. Sen, Extremal black holes and elementary string states, Mod. Phys. Lett. A 10 (1995) 2081–2094, [hep-th/9504147].
  * [21] A. Dabholkar, Exact counting of black hole microstates, Phys. Rev. Lett. 94 (2005) 241301, [hep-th/0409148].
  * [22] A. Dabholkar, R. Kallosh, and A. Maloney, A Stringy cloak for a classical singularity, JHEP 12 (2004) 059, [hep-th/0410076].
  * [23] A. Sen, How does a fundamental string stretch its horizon?, JHEP 05 (2005) 059, [hep-th/0411255].
  * [24] V. Hubeny, A. Maloney, and M. Rangamani, String-corrected black holes, JHEP 05 (2005) 035, [hep-th/0411272].
  * [25] A. Dabholkar, F. Denef, G. W. Moore, and B. Pioline, Precision counting of small black holes, JHEP 10 (2005) 096, [hep-th/0507014].
  * [26] N. Benjamin, E. Dyer, A. L. Fitzpatrick, A. Maloney, and E. Perlmutter, Small Black Holes and Near-Extremal CFTs, JHEP 08 (2016) 023, [arXiv:1603.08524].
  * [27] K. Narain, New Heterotic String Theories in Uncompactified Dimensions $<$ 10, Phys. Lett. B 169 (1986) 41–46.
  * [28] K. Narain, M. Sarmadi, and E. Witten, A Note on Toroidal Compactification of Heterotic String Theory, Nucl. Phys. B 279 (1987) 369–379.
  * [29] M. Winer, S.-K. Jian, and B. Swingle, An exponential ramp in the quadratic Sachdev-Ye-Kitaev model, Phys. Rev. Lett. 125 (2020) 250602, [arXiv:2006.15152].
  * [30] S. Sachdev and J. Ye, Gapless spin fluid ground state in a random, quantum Heisenberg magnet, Phys. Rev. Lett. 70 (1993) 3339, [cond-mat/9212030].
  * [31] A. Kitaev, “A simple model of quantum holography.” May, 2015.
  * [32] J. Maldacena and D. Stanford, Remarks on the Sachdev-Ye-Kitaev model, Phys. Rev. D 94 (2016), no. 10 106002, [arXiv:1604.07818].
  * [33] R. Jackiw, Lower Dimensional Gravity, Nucl. Phys. B 252 (1985) 343–356.
  * [34] C. Teitelboim, Gravitation and Hamiltonian Structure in Two Space-Time Dimensions, Phys. Lett. B 126 (1983) 41–45.
  * [35] A. Almheiri and J. Polchinski, Models of AdS2 backreaction and holography, JHEP 11 (2015) 014, [arXiv:1402.6334].
  * [36] J. Maldacena, D. Stanford, and Z. Yang, Conformal symmetry and its breaking in two dimensional Nearly Anti-de-Sitter space, PTEP 2016 (2016), no. 12 12C104, [arXiv:1606.01857].
  * [37] P. Saad, S. H. Shenker, and D. Stanford, JT gravity as a matrix integral, arXiv:1903.11115.
  * [38] D. Stanford and E. Witten, JT Gravity and the Ensembles of Random Matrix Theory, arXiv:1907.03363.
  * [39] D. Kapec, R. Mahajan, and D. Stanford, Matrix ensembles with global symmetries and ’t Hooft anomalies from 2d gauge theory, JHEP 04 (2020) 186, [arXiv:1912.12285].
  * [40] A. Maloney and E. Witten, Quantum Gravity Partition Functions in Three Dimensions, JHEP 02 (2010) 029, [arXiv:0712.0155].
  * [41] C. A. Keller and A. Maloney, Poincare Series, 3D Gravity and CFT Spectroscopy, JHEP 02 (2015) 080, [arXiv:1407.6008].
  * [42] J. Cotler and K. Jensen, AdS3 gravity and random CFT, arXiv:2006.08648.
  * [43] J. Cotler and K. Jensen, AdS3 wormholes from a modular bootstrap, arXiv:2007.15653.
  * [44] H. Maxfield and G. J. Turiaci, The path integral of 3D gravity near extremality; or, JT gravity with defects as a matrix integral, arXiv:2006.11317.
  * [45] J. M. Maldacena and L. Maoz, Wormholes in AdS, JHEP 02 (2004) 053, [hep-th/0401024].
  * [46] N. Benjamin, H. Ooguri, S.-H. Shao, and Y. Wang, Light-cone modular bootstrap and pure gravity, Phys. Rev. D 100 (2019), no. 6 066029, [arXiv:1906.04184].
  * [47] L. F. Alday and J.-B. Bae, Rademacher Expansions and the Spectrum of 2d CFT, JHEP 11 (2020) 134, [arXiv:2001.00022].
  * [48] N. Benjamin, S. Collier, and A. Maloney, Pure Gravity and Conical Defects, JHEP 09 (2020) 034, [arXiv:2004.14428].
  * [49] L. F. Alday, J.-B. Bae, N. Benjamin, and C. Jorge-Diaz, On the Spectrum of Pure Higher Spin Gravity, JHEP 12 (2020) 001, [arXiv:2009.01830].
  * [50] P. Kraus and A. Maloney, A cardy formula for three-point coefficients or how the black hole got its spots, JHEP 05 (2017) 160, [arXiv:1608.03284].
  * [51] D. Das, S. Datta, and S. Pal, Universal asymptotics of three-point coefficients from elliptic representation of Virasoro blocks, Phys. Rev. D 98 (2018), no. 10 101901, [arXiv:1712.01842].
  * [52] E. M. Brehm, D. Das, and S. Datta, Probing thermality beyond the diagonal, Phys. Rev. D 98 (2018), no. 12 126015, [arXiv:1804.07924].
  * [53] A. Romero-Bermúdez, P. Sabella-Garnier, and K. Schalm, A Cardy formula for off-diagonal three-point coefficients; or, how the geometry behind the horizon gets disentangled, JHEP 09 (2018) 005, [arXiv:1804.08899].
  * [54] Y. Hikida, Y. Kusuki, and T. Takayanagi, Eigenstate thermalization hypothesis and modular invariance of two-dimensional conformal field theories, Phys. Rev. D 98 (2018), no. 2 026003, [arXiv:1804.09658].
  * [55] A. Belin and J. de Boer, Random Statistics of OPE Coefficients and Euclidean Wormholes, arXiv:2006.05499.
  * [56] C. L. Siegel, Indefinite quadratische formen und funktionentheorie i, Mathematische Annalen 124 (dec, 1951) 17–54.
  * [57] A. Weil, Sur certains groupes d'opérateurs unitaires, Acta Mathematica 111 (1964), no. 0 143–211.
  * [58] A. Weil, Sur la formule de siegel dans la théorie des groupes classiques, Acta Mathematica 113 (1965), no. 0 1–87.
  * [59] A. Maloney and E. Witten, Averaging Over Narain Moduli Space, arXiv:2006.04855.
  * [60] N. Afkhami-Jeddi, H. Cohn, T. Hartman, and A. Tajdini, Free partition functions and an averaged holographic duality, arXiv:2006.04839.
  * [61] A. Pérez and R. Troncoso, Gravitational dual of averaged free CFT’s over the Narain lattice, arXiv:2006.08216.
  * [62] A. Dymarsky and A. Shapere, Comments on the holographic description of Narain theories, arXiv:2012.15830.
  * [63] S. Datta, S. Duary, P. Kraus, P. Maity, and A. Maloney, Adding Flavor to the Narain Ensemble, arXiv:2102.12509.
  * [64] A. Dymarsky and A. Shapere, Quantum stabilizer codes, lattices, and CFTs, arXiv:2009.01244.
  * [65] V. Meruliya, S. Mukhi, and P. Singh, Poincaré Series, 3d Gravity and Averages of Rational CFT, JHEP 04 (2021) 267, [arXiv:2102.03136].
  * [66] N. Benjamin, C. A. Keller, H. Ooguri, and I. G. Zadeh, Narain to Narnia, arXiv:2103.15826.
  * [67] V. Meruliya and S. Mukhi, AdS3 Gravity and RCFT Ensembles with Multiple Invariants, arXiv:2104.10178.
  * [68] M. Ashwinkumar, M. Dodelson, A. Kidambi, J. M. Leedom, and M. Yamazaki, Chern-Simons Invariants from Ensemble Averages, arXiv:2104.14710.
  * [69] J. Dong, T. Hartman, and Y. Jiang, Averaging over moduli in deformed WZW models, arXiv:2105.12594.
  * [70] S. Giombi, A. Maloney, and X. Yin, One-loop Partition Functions of 3D Gravity, JHEP 08 (2008) 007, [arXiv:0804.1773].
  * [71] M. Porrati and C. Yu, Kac-Moody and Virasoro Characters from the Perturbative Chern-Simons Path Integral, JHEP 05 (2019) 083, [arXiv:1903.05100].
  * [72] J. M. Maldacena and A. Strominger, AdS(3) black holes and a stringy exclusion principle, JHEP 12 (1998) 005, [hep-th/9804085].
  * [73] H. Maxfield, Quantum corrections to the BTZ black hole extremality bound from the conformal bootstrap, JHEP 12 (2019) 003, [arXiv:1906.04416].
  * [74] X. Yin, On Non-handlebody Instantons in 3D Gravity, JHEP 09 (2008) 120, [arXiv:0711.2803].
  * [75] V. L. Kalinin, Eisenstein series on the symplectic group, Journal of Soviet Mathematics 10 (jul, 1978) 71–73.
  * [76] H. Maaß, Siegel's Modular Forms and Dirichlet Series.  Springer Berlin Heidelberg, 1971.
  * [77] T. Guhr, A. Muller-Groeling, and H. A. Weidenmuller, Random matrix theories in quantum physics: Common concepts, Phys. Rept. 299 (1998) 189–425, [cond-mat/9707301].
  * [78] G. Livan, M. Novaes, and P. Vivo, Introduction to Random Matrices.  Springer International Publishing, 2018.
  * [79] J. Cotler and K. Jensen, Gravitational Constrained Instantons, arXiv:2010.02241.
  * [80] D. Das and S. Datta, Higher spin wormholes from modular bootstrap, arXiv:2106.03889.
  * [81] J. M. Maldacena, Eternal black holes in anti-de Sitter, JHEP 04 (2003) 021, [hep-th/0106112].
  * [82] N. Engelhardt, S. Fischetti, and A. Maloney, Free Energy from Replica Wormholes, arXiv:2007.07444.
  * [83] G. Shimura, Confluent hypergeometric functions on tube domains, Mathematische Annalen 260 (sep, 1982) 269–302.
  * [84] G. Kaufhold, Dirichletsche reihe mit funktionalgleichung in der theorie der modulfunktion 2. grades, Mathematische Annalen 137 (oct, 1959) 454–476.
  * [85] S. ichiro Mizumoto, Eisenstein series for siegel modular groups, Mathematische Annalen 297 (sep, 1993) 581–625.


# Visual Gyroscope: Combination of Deep Learning Features and Direct Alignment
for Panoramic Stabilization

Bruno Berenguel-Baeta
Instituto de Investigacion en Ingenieria de Aragon
Department of Computer Science and Systems Engineering
University of Zaragoza
Zaragoza, Spain
<EMAIL_ADDRESS>
& Antoine N. Andre
CNRS-AIST JRL (Joint Robotics Laboratory)
IRL, Japan
<EMAIL_ADDRESS>
& Guillaume Caron
CNRS-AIST JRL (Joint Robotics Laboratory)
IRL, Japan
Universite de Picardie Jules Verne, MIS laboratory
Amiens, France
<EMAIL_ADDRESS>
& Jesus Bermudez-Cameo
Instituto de Investigacion en Ingenieria de Aragon
Department of Computer Science and Systems Engineering
University of Zaragoza
Zaragoza, Spain
<EMAIL_ADDRESS>
& Jose J. Guerrero
Instituto de Investigacion en Ingenieria de Aragon
Department of Computer Science and Systems Engineering
University of Zaragoza
Zaragoza, Spain
<EMAIL_ADDRESS>
Corresponding author.

###### Abstract

In this article we present a visual gyroscope based on equirectangular
panoramas. We propose a new pipeline where we take advantage of combining
three different methods to obtain a robust and accurate estimation of the
attitude of the camera. We quantitatively and qualitatively validate our
method on two image sequences taken with a $360^{\circ}$ dual-fisheye camera
mounted on different aerial vehicles.

A final version of this article can be found at
https://doi.org/10.1109/CVPRW59228.2023.00685

_Keywords_ Omnidirectional Vision $\cdot$ 3D Vision $\cdot$ Non-central
Cameras $\cdot$ Layout recovery $\cdot$ Scene understanding

##  1 Introduction

Autonomous navigation of Unmanned Aerial Vehicles (UAV) require the knowledge
of pose and orientation. Among the different sensors we can use, cameras
provide information of the surroundings of the UAV which can be used for
several applications, such as object detection Jiang et al. (2022), while
being a lightweight sensor. One of these applications is the use of the camera
as a Visual Gyroscope (VG), estimating the 3D orientation of the camera for a
given image with respect to a reference.

VG algorithms consider two kinds of information, direct or indirect. Indirect
VG (IVG) leverage image features, either handcrafted, as patches around image
points Hadj-Abdelkader et al. (2018), or learned, e.g. estimating first the
optical flow and then the 3D orientation of the camera Kim et al. (2021).
Instead, Direct VG (DVG) consider pixel brightness of the whole image as input
of a 3D rotation optimization method André and Caron (2022). Usually, this
pixel information is transformed into different domains before estimating the
orientation, such as spherical Fourier transform Makadia and Daniilidis (2006)
or Mixture of photometric potentials Caron and Morbidi (2018).

Previous methods present high accuracy on 3D orientation estimation on narrow
domains André and Caron (2022), or the possibility of a wide estimation domain
but with lower accuracy Makadia and Daniilidis (2006). In this paper, we
propose a hybrid pipeline combining three different methods to obtain a robust
VG within a very large estimation domain and with high orientation accuracy.
We leverage the strong points of each method, overcoming the weak points and
limitations of each of them. In the next section we present the different
methods that form our pipeline while in Sec. 3 we evaluate and compare our
pipeline against state-of-the-art methods on two 360 equirectangular panoramas
data-sets taken from UAV.

##  2 Visual Gyroscope

Figure 1: Overview of our proposed pipeline. The input equirectangular
panorama first goes through HoLiNet, obtaining a first approximation of Roll-
Pitch angles with respect to the horizontal plane. The output is feed to the
MPP, obtaining an approximation of the Yaw angle with respect to a reference
image. Finally, the PVG refines the three angles such that the rotation
compensated image is closer to the reference one.

Our proposed pipeline111Code is available in
https://github.com/Sbrunoberenguel/HoLiNet is composed by three different
methods that act sequentially to obtain the Roll-Pitch-Yaw angles of the
camera in outdoor environments (see Fig. 1). The first block is a IVG composed
by a convolutional neural network called HoLiNet (Horizon Line Network) where
we obtain a first approximation of Roll-Pitch angles. The second block is a
DVG algorithm that uses MPP (Mixture of Photometric Potentials) Caron and
Morbidi (2018) to retrieve the Yaw angle taking as initial solution the
orientation from HoLiNet. The third and final block is second DVG algorithm
defined as PVG (Photometric Visual Gyroscope) where we refine the previous
solutions.

###  2.1 HoLiNet

Our proposed HoLiNet follows an encoder-decoder structure taking as input
information an equirectangular panorama in any orientation and providing two
heat-maps, one for the horizon line and another for the vertical vanishing
points (see Fig. 1).

For the encoder and feature extractor we use the convolutional part of
ResNet-50 He et al. (2016). We use the available pre-trained weights,
leveraging the performance of this network for feature extraction. In the
decoder we propose a set of convolutional layers followed by up-scaling layers
and skip connections from the encoder part. The output of the decoder is a
two-channel heat-map with the horizon line and vanishing points prediction. To
adapt the neural network to the distortion, we use in all the convolutional
layers convolutions adapted to the equirectangular projection. These
convolutions, EquiConvs, were first presented in Fernandez-Labrador et al.
(2020) and, in this work, are re-implemented pre-computing the kernel’s
distortion for a faster inference time (i.e. the original implementation runs
at 0.2fps while ours can run at 10fps).

The network is trained in a collection of gravity-oriented equirectangular
panoramas from indoor and outdoor environments Fraguas Bordonaba and Bermúdez
Cameo (2020). We apply rotations to these panoramas and generate the ground
truth labelling according to these rotations. We also perform several data
augmentations such as: horizontal flip, color permutation, color jitter and
random cropping. At training, we obtain intermediate representations at
different resolutions from the decoder of the network. These intermediate
representations allow to evaluate the network on early stages, making the
intermediate features of the network aim for the final task, improving the
overall performance of the network.

From the output information of the network, we compute the most probable
horizon plane, obtaining a first approximation of the camera’s Roll-Pitch
angles. To compute the horizon plane, we use the information of both outputs
of the network. First, we use the vanishing point heat-map to make a rough
estimation of the vertical direction. We project the vanishing points heat-map
in the unit sphere and compute the average vertical direction. This is a rough
estimation since the output is really sparse and can be noisy. Then, we
project the horizon line heat-map into the unit sphere. Using a random sample
consensus algorithm, we compute the 3D plane that better fits the horizon line
heat-map in the unit sphere. Assuming that both network’s outputs are coherent
with each other, the first estimation of the vertical direction and the normal
vector of the horizon plane should be close. So, to maintain this coherence,
in the iterative process we discard any possible solution which differs from
the first estimation more than a threshold angle (i.e. we assume a threshold
of $\pm 30^{\circ}$).

Once obtained the plane that better fits the output of the network, we can
compute the Roll and Pitch angles of the camera (Yaw is the rotation around
the plane’s normal vector, which cannot be computed with this method). The
main advantage of this method is that we can obtain 2 angles from a
$360^{\circ}$ domain. The main limitation is the angle precision, which is
limited by the uncertainty of the output of the network, and the impossibility
to obtain the Yaw angle with the proposed representation.

###  2.2 MPP-based visual gyroscope

The MPP is a full spherical image representation of image brightness as a
mixture of Gaussians. The MPP is structured as an icosahedron subdivided
$n\in\mathbb{N}$ times, of which each vertex is the center of a Gaussian
function, weighted by the normalized intensity of the pixel where it projects
in the captured image. Thus, there are as many Gaussians as vertices of the
sphere but all Gaussians of the MPP share the same variance
$\lambda_{g}\in\\{\mathbb{R}>0\\}$ that acts as a smoothing parameter. In the
seminal work introducing the MPP-based visual gyroscope Caron and Morbidi
(2018), captured dual-fisheye images are first transformed as MPPs: $G^{*}$
for a reference image, $G$ for a request image. Thus, $\lambda_{g}$ acts as a
smoothing parameter of the cost function, that is the sum of squared
differences between $G$ and $G^{*}$, to be minimized by optimizing the three
angles of the 3D rotation that aligns the best both MPPs with a Newton-like
algorithm.

In this work, the differences w.r.t. Caron and Morbidi (2018) are motivated by
the HoLiNet-MPP-PVG pipeline we propose (Fig. 1):

  * •

input images are equirectangular instead of dual-fisheye for both the sake of
uniformity with respect to HoLiNet and more generality since the
equirectangular format is much more common than dual-fisheye.

  * •

the single Yaw angle is estimated since not only HoLiNet already outputs
estimates of Roll and Pitch angles that can serve as good initial guesses for
PVG (see Sec. 2.3) but it reduces a little the computation load.

The main advantage of the MPP-based visual gyroscope is its very large
convergence domain, observed as being both globally convergent indoor for a
single pure rotation angle and almost as large for 3D rotations, even in the
presence of translations, in Caron and Morbidi (2018). However, its main
drawback is the required trade-off between processing time and estimation
accuracy: to reach a processing rate of 3 images per second, the icosahedron
maximum subdivision level is $n=3$ and the average estimation error was
reported about 3 degrees with $\lambda_{g}=0.325$. Thus, PVG is required as a
final step to improve the accuracy of estimations.

###  2.3 Photometric Visual Gyroscope (PVG)

To improve both the processing time and the accuracy with respect to the MPP-
based visual gyroscope, the PVG André and Caron (2022) uses a spherical image
representation directly from image brightness without a transformation to a
MPP. The PVG is built on the same principle as the MPP-based visual gyroscope
and also relies on the intensities of the image mapped to a subdivided
icosahedron. However, instead of computing a MPP, the direct pixel brightness
are assigned to each vertices of the icosahedron, allowing a much faster
computation of the Jacobians in the Newton-like optimization of the
orientations. When mapping full resolution images (typically $1280\times 720$)
to the subdivided icosahedron, a higher precision in the orientation
estimation can be obtained. The spherical gradient is computed in the image
plane (as highlighted in the PVG thumbnail of Fig. 1) and not with neighbors
vertices as in the MPP-based gyroscope.

The main difference of this work with respect to the source work André and
Caron (2022) is that equirectangular input images are used, instead of dual-
fisheye images, allowing a consistency of input images all along the
orientation estimation pipeline.

PVG has shown estimation errors below $0.1^{\circ}$ in the single axis
rotation case, both pure and with translations André and Caron (2022). To
reach such a precision, the icosahedron is subdivided $n=5$ times and the
captured image at full resolution is used for a computation time $2\%$the one
of the MPP-based gyroscope. But inversely to the MPP-based gyroscope, the low
processing load and the high accuracy come at the price of a narrow
convergence domain that was observed at $\pm 12.5^{\circ}$ for the single
rotation angle case. Hence, PVG needs good initial guesses that HoLiNet (Roll,
Pitch) and the MPP-based visual gyroscope (Yaw) bring.

##  3 Experiments

###  3.1 Experimental setup

We evaluate our pipeline with two datasets. The first is the Sequence 8 of
PanoraMIS Benseddik et al. (2020) that was taken with a Ricoh Theta S mounted
on a Parrot Disco fixed-wing drone. Since this sequence is captured as raw
dual-fisheye, we first transform the images to the equirectangular format
using the software shared with the
dataset222http://github.com/PerceptionRobotique/dualfisheye2equi. With this
sequence of 12000+ images, we make a qualitative evaluation by compensating
the estimated rotations with respect to image 8890 in order to compare the
success rate with Caron and Morbidi (2018).

To allow the quantitative evaluation, we introduce a new dataset of 2700+
equirectangular images,
SVMIS+333http://mis.u-picardie.fr/~g-caron/pub/data/SVMISplus_er_pano.zip.
SVMIS+ is acquired with a Ricoh Theta S too but embedded on a Matrice 600 Pro
hexarotor manually flown in a countryside area during $4^{\prime}36"$. The use
of the hexarotor has two interests over the Disco drone. First, it allows to
embed an extra computer connected to the onboard electronics in order to save
the orientation information of the drone’s Inertial Measurement Unit
synchronously with the image capture. Second, the different type of motion of
a hexarotor compared to a fixed-wing drone provides an additional variety in
the evaluation, together with different meteorological conditions (sunny
versus cloudy). With this dataset, in addition to the quantitative evaluation,
we also perform a qualitative evaluation by compensating the estimated
rotations of all the images with respect to a selected frame. Frame 1074 is
selected such that the image is roughly at the center of the flown area, with
attitude angles near zero (horizon line near straight and horizontal in the
image).

###  3.2 Results

With PanoraMIS’ Sequence 8, we evaluate qualitatively the success rate of the
computed orientations by studying the misalignment of stabilized images with
respect to the reference image. Over the 12000+ images, 564 were misaligned.
This represents a success rate of $95.3\%$, thus out-performing previously
shown results of $88\%$ Caron and Morbidi (2018). The stabilization results
with the whole first dataset are shared as a
video444http://mis.u-picardie.fr/~g-caron/videos/2023OmniCV_svmis.mp4
highlighting each intermediate result of our pipeline for orientation
estimation.

With the synchronized and reliable ground truth provided with SVMIS+, a
quantitative evaluation of the pipeline is put in practice. HoLiNet is only
evaluated over 2 angles. To avoid ambiguities in the evaluation of the two
angles, we compute the predicted normal vector, $n$, of the horizon plane and
compare with the ground truth measure, $\hat{n}$, computing the angle between
both vectors as: $\arccos\left(n\cdot\hat{n}\right)$. The quantitative results
are shown in Fig. 2, obtaining a mean error of $3.04^{\circ}$.

Figure 2: Quantitative results of HoLiNet for 2 angles. Dashed lines show mean
error.

(a)

(b)

Figure 3: a) Quantitative results of HoLiNet+MPP and HoLiNet+MPP+PVG in the
SVMIS+ dataset. b) (Zoom) Quantitative results of MPP and PVG around the
reference image. Vertical green line defines the reference image and
horizontal dashed lines show mean error of each method.

The evaluation for the 3 angles is made computing the angle difference between
the angle-axis rotation of ground truth with respect to the reference image,
$R_{gt}$, and our estimation, $R_{pred}$, as:
$\arccos\left((trace(R_{gt}\cdot{R_{pred}}^{T})-1)/2\right)$. The results are
presented in Fig. 3, obtaining a mean error of $17.6^{\circ}$ for HoLiNet +
MPP, $16.7^{\circ}$ for the whole pipeline over the whole sequence, and
$4.6^{\circ}$ for 900 images (33% of SVMIS+) around the reference image
(Fig.3b), corresponding to a difference of altitude with respect to the
reference image lower than 10 m. We also present a
video555http://mis.u-picardie.fr/~g-caron/videos/2023OmniCV_svmis_p.mp4 of
qualitative results with SVMIS+.

##  4 Conclusions

We have presented a novel pipeline that leverages the strong points of three
methods, HoLiNet using neural networks and two using direct alignment, for
panoramic image rotation compensation in outdoor environments. The
quantitative results on two datasets of airborne panoramic images show HoLiNet
is robust to any translation and improves the visual alignment success rate.
But since the direct alignment methods following HoLiNet in the pipeline
assume pure rotation between the reference and current images, the presence of
a large translation decreases the rotation estimation accuracy, as shown with
the newly introduced public dataset SVMIS+. However, the rotation estimation
appears accurate within a reasonable translation to the reference image that
further study with SVMIS+ will allow to quantify during future works.

## References

  * Jiang et al. [2022] Peiyuan Jiang, Daji Ergu, Fangyao Liu, Ying Cai, and Bo Ma.  A review of yolo algorithm developments.  _Procedia Computer Science_ , 199:1066–1073, 2022.
  * Hadj-Abdelkader et al. [2018] Hicham Hadj-Abdelkader, Omar Tahri, and Houssem-Eddine Benseddik.  Closed form solution for rotation estimation using photometric spherical moments.  In _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 627–634. IEEE, 2018.
  * Kim et al. [2021] Dabae Kim, Sarthak Pathak, Alessandro Moro, Atsushi Yamashita, and Hajime Asama.  Self-supervised optical flow derotation network for rotation estimation of a spherical camera.  _Advanced Robotics_ , 35(2):118–128, 2021.
  * André and Caron [2022] Antoine N André and Guillaume Caron.  Photometric visual gyroscope for full-view spherical camera.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5232–5235, 2022.
  * Makadia and Daniilidis [2006] Ameesh Makadia and Kostas Daniilidis.  Rotation recovery from spherical images without correspondences.  _IEEE transactions on pattern analysis and machine intelligence_ , 28(7):1170–1175, 2006.
  * Caron and Morbidi [2018] Guillaume Caron and Fabio Morbidi.  Spherical visual gyroscope for autonomous robots using the mixture of photometric potentials.  In _International Conference on Robotics and Automation_ , pages 820–827. IEEE, 2018.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Fernandez-Labrador et al. [2020] Clara Fernandez-Labrador, Jose M Facil, Alejandro Perez-Yus, Cedric Demonceaux, Javier Civera, and Jose J Guerrero.  Corners for layout: End-to-end layout recovery from 360 images.  _IEEE Robotics and Automation Letters_ , 5(2):1255–1262, 2020.
  * Fraguas Bordonaba and Bermúdez Cameo [2020] Eduardo Fraguas Bordonaba and Jesus Bermúdez Cameo.  Estimación de línea del horizonte en imágenes de 360 grados con aprendizaje automático profundo.  _Master thesis_ , 2020.
  * Benseddik et al. [2020] H. Benseddik, F. Morbidi, and G. Caron.  Panoramis: An ultra-wide field of view image dataset for vision-based robot-motion estimation.  _The International Journal of Robotics Research_ , 39(9):1037–1051, 2020.

## ACKNOWLEDGMENT

This work was supported by PID2021-125209OB-I00 and TED2021-129410B-I00
(MCIN/AEI/10.13039/501100011033 and FEDER/UE and NextGenerationEU/PRTR)


# Quadratic dispersion relations in gapless frustration-free systems

Rintaro Masaoka  Department of Applied Physics, The University of Tokyo, Tokyo
113-8656, Japan  Tomohiro Soejima  Department of Physics, Harvard University,
Cambridge, MA 02138, USA  Haruki Watanabe<EMAIL_ADDRESS>Department of Applied Physics, The University of Tokyo, Tokyo 113-8656, Japan

###### Abstract

Recent case-by-case studies revealed that the dispersion of low energy
excitations in gapless frustration-free Hamiltonians is often quadratic or
softer. In this work, we argue that this is actually a general property of
such systems. By combining a previous study by Bravyi and Gosset and the min-
max principle, we prove this hypothesis for models with local Hilbert spaces
of dimension two that contains only nearest-neighbor interactions on cubic
lattice. This may be understood as a no-go theorem realizing gapless phases
with linearly dispersive excitations in frustration-free Hamiltonians. We also
provide examples of frustration-free Hamiltonians in which the plane-wave
state of a single spin flip does not constitute low energy excitations.

##  I Introduction

Accurately investigating the ground states and excited states of quantum many-
body systems is often challenging. It is hence common practice to analyze the
system of interest using the simplest possible model that belongs to the same
phase. Frustration-free systems, in particular, are relatively easy to handle,
and their exact ground states and excited states are sometimes accessible. For
these reasons, frustration-free systems have been widely used as
representative models of various phases of matter. Therefore, elucidating the
general properties of frustration-free systems and understanding the limits of
the phases that can be realized by frustration-free Hamiltonians hold
significant importance.

Numerous frustration-free systems posses an excitation gap. Notable examples
include the Majumdar–Ghosh (MG) model, known as a toy model realizing
spontaneous breaking of discrete translational symmetry, the
Affleck–Kennedy–Lieb–Tasaki (AKLT) model, representing a symmetry-protected
topological phase, and the Kitaev Toric code model, serving as the canonical
model for topologically ordered phases Auerbach (2012); Tasaki (2020). The
parent Hamiltonians of Matrix Product States (MPS) also feature an excitation
gap Fannes  _et al._ (1992).

There are also frustration-free Hamiltonians with gapless excitations. For
example, the uncle Hamiltonian of MPS Fernández-González  _et al._ (2015),
various models at critical points, and models related to spontaneously broken
continuous symmetries Ogunnaike  _et al._ (2023); Watanabe  _et al._ (2023)
are gapless. Through recent investigation of these models, the general
properties of frustration-free systems have gradually become clearer.

In this paper, we discuss two conjectures regarding frustration-free systems.
The first is about the finite-size gap between degenerate ground states.
Generally, even if the ground states are degenerate in the thermodynamic
limit, their energy eigenvalues in a finite-size system do not precisely match
due to the finite-size gap. However, in frustration-free systems, the ground
states are exactly degenerate even before taking the thermodynamic limit. In
other words, we can judge whether a frusration-free system is gapped or not by
looking at the limiting behavior of the difference between the ground state
energy and the second lowest energy level.

The second conjecture concerns the dispersion relation of low-energy
excitations in frustration-free systems. Although gapless modes typically have
a linear dispersion, it is known that the ferromagnetic Heisenberg model,
which is a representative frustration-free Hamiltonian, have a spin wave
excitation with a quadratic dispersion Auerbach (2012). In fact, our second
conjecture asserts that gapless frustration-free systems generally have a
quadratic or softer dispersion relation. Although there are several arguments
supporting this statement in literature (for example, see Refs. Palle and
Benton, 2021; Ogunnaike  _et al._ , 2023; Watanabe  _et al._ , 2023; Ren  _et
al._ , 2024), they are applicable only to the case where the low-energy
excitations are obtained by applying a sum of local operators to a ground
state. We provide a general proof for spin-1/2 models with nearest-neighbor
interaction on cubic lattice based on the result of Bravyi and Gosset Bravyi
and Gosset (2015). We also discuss examples with longer-range interactions and
show that gapless excitations with quadratic dispersion may not be obtained by
a sum of local operators.

##  II Overview

####  II.0.1 Setting and definitions

In this work, we consider Hamiltonians defined on a finite $d$-dimensional
lattice $\Lambda$:

$\displaystyle\hat{H}=\sum_{\bm{r}\in\Lambda}\hat{H}_{\bm{r}}.$ (1)

The local Hilbert space on each lattice site $\bm{r}\in\Lambda$ is assumed to
be finite dimensional, which is denoted by $D_{0}$. Let $|\Lambda|$ be the
number of lattice sites in $\Lambda$. Then the dimension of the total Hilbert
space is $D=D_{0}^{|\Lambda|}$. We assume that the Hamiltonian is local in the
sense that $\hat{H}_{\bm{r}}$ acts nontrivially on the sites within a finite
distance $R$ from $\bm{r}$.

Let us write eigenvalues of $\hat{H}$ as

$\displaystyle E_{1}\leq E_{2}\leq\cdots\leq E_{D}.$ (2)

The thermodynamic limit $|\Lambda|\to\infty$ is taken by a sequence of
increasing system size.

The system is said to be _gapped_ if there exists an integer
$N_{\mathrm{deg}}$ ($1\leq N_{\mathrm{deg}}<D$), which may depend on the
system size, such that

$\displaystyle\lim_{|\Lambda|\to\infty}\big{(}E_{N_{\mathrm{deg}}}-E_{1}\big{)}=0,$
(3)
$\displaystyle\Delta\coloneqq\lim_{|\Lambda|\to\infty}\big{(}E_{N_{\mathrm{deg}}+1}-E_{N_{\mathrm{deg}}}\big{)}\neq
0.$ (4)

Otherwise the system is _gapless_. The limit in Eq. (3) defines the excitation
gap $\Delta$. When $N_{\mathrm{deg}}\geq 2$, the quantity
$E_{N_{\mathrm{deg}}}-E_{1}$ is referred to as _the finite-size gap among
degenerate ground states_. When the degeneracy originates from spontaneous
breaking of a discrete symmetry or formation of a topological order, it
generically decays exponentially with the system size. Even when
$N_{\mathrm{deg}}$ converges to a finite number in the large $|\Lambda|$
limit, its value for a finite system may be ambiguous due to the possible
system-size dependence.

The Hamiltonian is _translation invariant_ if there exists an operator
$\hat{T}_{\bm{a}}$ for each lattice vector $\bm{a}$ such that
$\hat{T}_{\bm{a}}\hat{H}_{\bm{r}}=\hat{H}_{\bm{r}+\bm{a}}\hat{T}_{\bm{a}}$ for
all $\bm{r}\in\Lambda$. This is possible only when the periodic boundary
condition (PBC) is imposed.

The Hamiltonian is _frustration-free_ if a ground state $|{\Phi_{0}}\rangle$
of $\hat{H}$ is a simultaneous ground state of every local Hamiltonian
$\hat{H}_{\bm{r}}$ Tasaki (2020). In this case, without loss of generality and
without modifying the ground states and low-energy excitations of the system,
one may assume that each $\hat{H}_{\bm{r}}$ is a projector, i.e.,
$\hat{Q}_{\bm{r}}^{2}=\hat{Q}_{\bm{r}}$ and
$\hat{Q}_{\bm{r}}|{\Phi_{0}}\rangle=0$ for all $\bm{r}\in\Lambda$. Under this
choice, the ground state energy becomes $E_{1}=0$.

####  II.0.2 Conjectures on frustration-free Hamiltonian

Let us state our conjectures one by one. The first conjecture is that, when
the Hamiltonian is frustration-free and gapped, the finite-size gap among
ground states precisely vanishes before taking the thermodynamic limit:

$\displaystyle E_{N_{\mathrm{deg}}}=E_{1}.$ (5)

For example, in the AKLT model for spin $s=1$ chain under OBC, the four-fold
ground state degeneracy due to the edge modes is exact. The four-fold
topological degeneracy in the Kitaev toric code under PBC is also exact.

This implies the following criterion for the excitation gap in frustration-
free systems. Let $\tilde{N}_{\mathrm{deg}}$
($1\leq\tilde{N}_{\mathrm{deg}}<D$) be the number of exact zero energy states,
i.e.,

$\displaystyle E_{\tilde{N}_{\mathrm{deg}}}=E_{1},\quad
E_{\tilde{N}_{\mathrm{deg}}+1}\neq E_{1},$ (6)

which may also depend on the system size (see, for example, Eq. (45) below).
The Hamiltonian is gapped if and only if

$\displaystyle\lim_{|\Lambda|\to\infty}\big{(}E_{\tilde{N}_{\mathrm{deg}}+1}-E_{1}\big{)}>0.$
(7)

Namely, one can set $N_{\mathrm{deg}}=\tilde{N}_{\mathrm{deg}}$. Actually this
criterion has been used as the definition of the excitation gap in previous
studies (for example, see Refs. Bravyi and Gosset, 2015; Gosset and Mozgunov,
2016; Gosset and Huang, 2016). Note that $\tilde{N}_{\mathrm{deg}}$ is well-
defined even for gapless systems unlike $N_{\mathrm{deg}}$.

The second conjecture is that, when the Hamiltonian is translation-invariant,
frustration-free, and gapless, there exists a family of variational states
$|\Psi_{\bm{k}}\rangle$ that are orthogonal to all the ground states and
satisfy

$\displaystyle\hat{T}_{\bm{a}}|\Psi_{\bm{k}}\rangle=e^{-i\bm{k}\cdot\bm{a}}|\Psi_{\bm{k}}\rangle,$
(8)
$\displaystyle\langle\Psi_{\bm{k}}|\hat{H}|\Psi_{\bm{k}}\rangle=O\big{(}|\bm{k}-\bm{k}_{0}|^{2},L^{-2}\big{)}$
(9)

for some $\bm{k}_{0}$. Namely, the low energy excitation of the system is not
linearly dispersive about the gapless point at $\bm{k}=\bm{k}_{0}$.

For systems under OBC, the result of Refs. Knabe, 1988; Anshu, 2020; Gosset
and Mozgunov, 2016 gives us the bound
$E_{\tilde{N}_{\mathrm{deg}}+1}-E_{1}\leq O(L^{-2})$. Although this is
consistent with our conjecture, it is not directly applicable to the PBC case
Watanabe  _et al._ (2023).

####  II.0.3 Min-max principle

Next, let us review the min-max principle, which supports our conjectures. We
compare two Hamiltonians $\hat{H}$ and $\hat{H}^{\prime}$ acting on a
$D$-dimensional Hilbert space. The eigenvalues of $\hat{H}$ and
$\hat{H}^{\prime}$ are, respectively, denoted by $E_{j}$ and $E_{j}^{\prime}$
($j=1,2,\cdots,D$) in the increasing order. Suppose that
$\hat{V}\coloneqq\hat{H}^{\prime}-\hat{H}$ is positive semi-definite:

$\displaystyle\hat{V}\geq 0.$ (10)

That is, $\langle\Phi|\hat{V}|\Phi\rangle\geq 0$ for any state $|\Phi\rangle$.
In other words, all the eigenvalues of $\hat{V}$ are nonnegative. In this
setting, the min-max principle states that

$\displaystyle E_{j}^{\prime}\geq E_{j}$ (11)

for every $j=1,2,\cdots,D$ (see Theorem A.7 of Ref. Tasaki (2020)). This
statement is trivial when the two Hamiltonians can be diagonalized by a common
unitary operator, but it holds more generally. Since the proof is elementary,
we review it in Appendix A.

Two corollaries follow immediately from the min-max principle. Let us consider
two frustration free Hamiltonians
$\hat{H}=\sum_{\bm{r}\in\Lambda}\hat{Q}_{\bm{r}}$ and
$\hat{H}^{\prime}=\sum_{\bm{r}\in\Lambda}\hat{Q}_{\bm{r}}^{\prime}$. Suppose
that $\hat{V}=\hat{H}^{\prime}-\hat{H}$ is positive-semidefinite. Then the
inequality in (11) implies that the number of zero-energy states of $\hat{H}$
cannot be smaller than that of $\hat{H}^{\prime}$:

$\displaystyle\tilde{N}_{\mathrm{deg}}\geq\tilde{N}_{\mathrm{deg}}^{\prime}.$
(12)

Furthermore,

$\displaystyle\lim_{|\Lambda|\to\infty}E_{j}^{\prime}=0\quad\Rightarrow\quad\lim_{|\Lambda|\to\infty}E_{j}=0.$
(13)

This relation suggests that if (i) $\hat{H}$ is gapped and (ii)
$\tilde{N}_{\mathrm{deg}}$ is bounded by a system-size independent constant,
then $\hat{H}^{\prime}$ is also gapped. This relation was previously used for
interacting Kitaev chains in Refs. Katsura  _et al._ , 2015; Wouters  _et al._
, 2018.

##  III 1D Examples with nearest-neighbor interactions

In this section, we discuss a chain of $L$ qubits with open boundary condition
(OBC) and PBC following Ref. Bravyi and Gosset (2015). The Hilbert space on
each qubit is spanned by $|0\rangle$ and $|1\rangle$, which may be interpreted
as $|{\uparrow}\rangle$ and $|{\downarrow}\rangle$ for an $s=1/2$ spin. Let us
consider the translation-invariant Hamiltonian with nearest-neighbor
interactions:

$\displaystyle\hat{H}^{\mathrm{pbc}}\coloneqq\sum_{x=1}^{L}\hat{Q}_{x,x+1},\quad\hat{H}^{\mathrm{obc}}\coloneqq\sum_{x=1}^{L-1}\hat{Q}_{x,x+1}.$
(14)

Here, $\hat{Q}_{x,x+1}=\hat{Q}_{x,x+1}^{2}$ is a projector nontrivially acting
on the spins at $x$ and $x+1$. The interaction range of this Hamiltonian is 1.
The number of $+1$ eigenvalues of a projector is called the rank. The
Hamiltonian $\hat{H}^{\mathrm{pbc}}$ has the translation symmetry $\hat{T}$
which satisfies $\hat{T}\hat{Q}_{x-1,x}=\hat{Q}_{x,x+1}\hat{T}$.

The seminal work by Bravyi and Gosset Bravyi and Gosset (2015) showed that
$\hat{H}^{\mathrm{obc}}$ can be gapless only when the projector
$\hat{Q}_{x,x+1}$ is unitary equivalent to Eqs. (19), (20) for the rank 1 case
and Eq. (38) for the rank 2 case. Then the min-max principle implies the same
for $\hat{H}^{\mathrm{pbc}}$ at least when $\tilde{N}_{\mathrm{deg}}$ under
OBC is finite, since
$\hat{H}^{\mathrm{pbc}}-\hat{H}^{\mathrm{obc}}=\hat{Q}_{L,1}\geq 0$ is
positive semi-definite. We will see that the fully polarized state

$\displaystyle|{\Phi_{0}}\rangle\coloneqq\bigotimes_{x=1}^{L}|0\rangle_{x}=|0\cdots
0\rangle$ (15)

is a common ground state of these Hamiltonians. Furthermore, the plane-wave
state of a single spin flip

$\displaystyle|{\Psi_{k}}\rangle\coloneqq\frac{1}{\sqrt{L}}\sum_{x=1}^{L}e^{ikx}|x\rangle,$
(16)
$\displaystyle|x\rangle\coloneqq\hat{s}_{x}^{-}|{\Phi_{0}}\rangle=|\underbrace{0\cdots
0}_{x-1}1\underbrace{0\cdots 0}_{L-x}\rangle$ (17)

with $k\coloneqq 2\pi m/L$ ($m=1,2,\cdots L$) is a common variational state
among these examples and has a quadratic dispersion relation. That is,

$\displaystyle E(k)$
$\displaystyle=\langle\Psi_{k}|\hat{H}^{\mathrm{pbc}}|{\Psi_{k}}\rangle=\sum_{x=1}^{L}\big{\|}\hat{Q}_{x,x+1}|{\Psi_{k}}\rangle\big{\|}^{2}$
$\displaystyle=\frac{1}{L}\sum_{x,x^{\prime}=1}^{L}e^{ik(x-x^{\prime})}\langle
x^{\prime}|\hat{H}^{\mathrm{pbc}}|x\rangle=O\big{(}(k-k_{0})^{2}\big{)}$ (18)

for some $k_{0}$.

###  III.1 Rank 1 case

Let us start with the rank 1 case. We write

$\displaystyle\hat{Q}_{x,x+1}\coloneqq|\psi\rangle_{x,x+1}\langle\psi|_{x,x+1},$
(19)

where $|\psi\rangle_{x,x+1}$ is a normalized state for two spins at $x$ and
$x+1$. Without loss of generality one can assume the form

$\displaystyle|\psi\rangle=(\alpha+i\beta)|01\rangle+(\alpha+i\gamma)|10\rangle+\delta|11\rangle,$
(20) $\displaystyle\alpha,\beta,\gamma,\delta\in\mathbb{R},\quad
2\alpha^{2}+\beta^{2}+\gamma^{2}+\delta^{2}=1$ (21)

by performing a local unitary transformation (see Appendix B for the
derivation) Bravyi and Gosset (2015). The model has U(1) spin rotation
symmetry about the $z$ axis if and only if $\delta=0$.

Since the matrix elements are known, the Hamiltonian in Eq. (19) can be
expressed in terms of spin operators $\hat{s}_{x}^{a}$ and $\hat{s}_{x+1}^{a}$
($a=x,y,z$). For example, when
$(\alpha,\beta,\gamma,\delta)=\pm(0,1/\sqrt{2},-1/\sqrt{2},0)$,
$\hat{Q}_{x,x+1}$ becomes the projector onto the spin-singlet state
$(|01\rangle-|10\rangle)/\sqrt{2}$:

$\displaystyle\hat{Q}_{x,x+1}$ $\displaystyle=\hat{\Pi}_{x,x+1}^{s=0},$ (22)
$\displaystyle\hat{\Pi}_{x,x+1}^{s=0}$
$\displaystyle\coloneqq\hat{\mathbbm{1}}-\frac{1}{2}(\hat{\bm{s}}_{x}+\hat{\bm{s}}_{x+1})^{2}=\frac{1}{4}\hat{\mathbbm{1}}-\hat{\bm{s}}_{x}\cdot\hat{\bm{s}}_{x+1}.$
(23)

The corresponding Hamiltonian is the ferromagnetic Heisenberg model. Any state
that is invariant under permutations of any two qubits (e.g., the fully-
polarized state and the W state) is a ground state of this model. As a basis
of such states, we can choose

$\displaystyle\hat{\mathcal{S}}|\underbrace{0\cdots
0}_{L-n}\underbrace{1\cdots 1}_{n}\rangle\quad(n=0,1,\cdots L),$ (24)

where $\hat{\mathcal{S}}$ is the symmetrization operator, uniformly averaging
over the $\binom{L}{n}=\frac{L!}{(L-n)!n!}$ states. This model is known to be
gapless due to the presence of a spin-wave excitation $E(k)=2\sin^{2}(k/2)$
under PBC.

To analyze more general cases, let us introduce a matrix

$\displaystyle
m_{\psi}\coloneqq\begin{pmatrix}\langle\psi|01\rangle&\langle\psi|11\rangle\\\
-\langle\psi|00\rangle&-\langle\psi|10\rangle\end{pmatrix}=\begin{pmatrix}\alpha-i\beta&\delta\\\
0&-\alpha+i\gamma\end{pmatrix}.$ (25)

The model defined by Eqs. (14), (19), and (20) can be gapless only when $\det
m_{\psi}=(\alpha-i\beta)(-\alpha+i\gamma)\neq 0$, i.e., $|\psi\rangle$ is
entangled Bravyi and Gosset (2015). In this case, we introduce an invertible
operator $\hat{M}$ composed of nonuniform powers of the matrix $m_{\psi}$:

$\displaystyle\hat{M}\coloneqq\mathbbm{1}\otimes\hat{m}_{\psi}\otimes\hat{m}_{\psi}^{2}\otimes\cdots\otimes\hat{m}_{\psi}^{L-1},$
(26) $\displaystyle\hat{m}_{\psi}\coloneqq(\alpha-i\beta)|0\rangle\langle
0|-(\alpha-i\gamma)|1\rangle\langle 1|+\delta|0\rangle\langle 1|.$ (27)

This operator maps $|\psi\rangle$ to the singlet state:

$\displaystyle\hat{M}^{\dagger}|\psi\rangle_{x,x+1}=(\det{m_{\psi}}^{*})^{j}(|01\rangle_{x,x+1}-|10\rangle_{x,x+1}),$
(28)

It follows that $\hat{Q}_{x,x+1}$ for the state in Eq. (20) can be connected
to $\hat{\Pi}_{x,x+1}^{s=0}$ as

$\displaystyle\hat{Q}_{x,x+1}=4|{\det{m}_{\psi}}|^{2}(\hat{M}\hat{\Pi}_{x,x+1}^{s=0}\hat{M}^{-1})^{\dagger}(\hat{M}\hat{\Pi}_{x,x+1}^{s=0}\hat{M}^{-1}).$
(29)

This type of non-unitary transformation is known as Witten’s conjugation
Witten (1982); Wouters  _et al._ (2021). As a consequence, ground states of
$\hat{H}^{\mathrm{obc}}$ takes the form Bravyi and Gosset (2015)

$\displaystyle\hat{M}\hat{\mathcal{S}}|\underbrace{0\cdots
0}_{L-n}\underbrace{1\cdots 1}_{n}\rangle\quad(n=0,1,\cdots L).$ (30)

The Hamiltonian under PBC has an additional term $\hat{Q}_{L,1}$. Every ground
state of $\hat{H}^{\mathrm{obc}}$ remains a ground state of
$\hat{H}^{\mathrm{pbc}}$ if $m_{\psi}^{L}$ is proportional to the identity
matrix $\mathbbm{1}$. However, except when
$(\alpha,\beta,\gamma,\delta)=\frac{\pm 1}{\sqrt{2}}(0,1,-1,0)$ discussed
above, $m_{\psi}^{L}$ is not proportional to $\mathbbm{1}$ for some $L$. In
such a case, the ground state of $\hat{H}^{\mathrm{pbc}}$ is restricted to the
product state of the eigenstates of $\hat{m}_{\psi}$; that is,
$|{\Phi_{0}}\rangle=|00\cdots 0\rangle$ and $|uu\cdots u\rangle$, where

$\displaystyle|u\rangle\coloneqq\frac{[2\alpha-i(\beta+\gamma)]|1\rangle-\delta|0\rangle}{\sqrt{4\alpha^{2}+(\beta+\gamma)^{2}+\delta^{2}}}.$
(31)

One can easily check that $\langle\psi|00\rangle=\langle\psi|uu\rangle=0$.
Therefore, the exact ground state degeneracy of this model can be summarized
as Bravyi and Gosset (2015)

$\displaystyle\tilde{N}_{\mathrm{deg}}=\begin{cases}L+1&\text{if
}m_{\psi}^{L}\propto\mathbbm{1},\\\ 2&\text{otherwise}.\\\ \end{cases}$ (32)

The variational state $|{\Psi_{k}}\rangle$ in Eq. (16) with $k\neq 0$ is
orthogonal to the ground states at least when $m_{\psi}^{L}$ is not
proportional to $\mathbbm{1}$, since their translation eigenvalues are
different. The energy expectation value in Eq. (18) can be computed as

$\displaystyle E(k)$
$\displaystyle=\sum_{x=1}^{L}\big{|}\langle\psi|_{x,x+1}|{\Psi_{k}}\rangle\big{|}^{2}=\big{|}\langle\psi|10\rangle+e^{ik}\langle\psi|01\rangle\big{|}^{2}$
$\displaystyle=\big{|}(\alpha-i\gamma)+(\alpha-i\beta)e^{ik}\big{|}^{2}$
$\displaystyle=(1-\delta^{2})+2(\alpha^{2}+\beta\gamma)\cos
k+2\alpha(\beta-\gamma)\sin k$
$\displaystyle=(1-\delta^{2})-\sqrt{(1-\delta^{2})^{2}-(\beta^{2}-\gamma^{2})^{2}}\cos(k-k_{0}).$
(33)

In going to the last line, we defined

$\displaystyle\cos
k_{0}\coloneqq-\frac{\alpha^{2}+\gamma\beta}{\sqrt{(\alpha^{2}+\gamma\beta)^{2}+\alpha^{2}(\beta-\gamma)^{2}}},$
(34) $\displaystyle\sin
k_{0}\coloneqq-\frac{\alpha(\beta-\gamma)}{\sqrt{(\alpha^{2}+\gamma\beta)^{2}+\alpha^{2}(\beta-\gamma)^{2}}}.$
(35)

It follows that $E(k)$ can be bounded below as

$\displaystyle
E(k)\geq(1-\delta^{2})-\sqrt{(1-\delta^{2})^{2}-(\beta^{2}-\gamma^{2})^{2}}.$
(36)

The right-hand side vanishes when $\beta^{2}=\gamma^{2}$, implying the
existence of gapless excitations when $\gamma=\pm\beta$. In this case $E(k)$
can be rewritten as

$\displaystyle E(k)=2(1-\delta^{2})\sin^{2}((k-k_{0})/2),$ (37)

which confirms our conjecture in the rank 1 case. When $\gamma=\beta$, $k_{0}$
is precisely $\pi$, but it takes more general value when $\gamma=-\beta$. This
result is consistent with Ref. Bravyi and Gosset (2015) which mathematically
proved that $\hat{H}^{\mathrm{obc}}$ is gapped if and only if
$\beta^{2}\neq\gamma^{2}$.

###  III.2 Rank 2 case

Next let us discuss the rank 2 case. In this case the Hamiltonian in Eq. (14)
can be gapless only when $\hat{Q}_{x,x+1}$ is unitary equivalent to the XY
model with an external magnetic field:

$\displaystyle\hat{Q}_{x,x+1}\coloneqq\frac{1}{2}\hat{\mathbbm{1}}-\frac{\zeta\hat{s}_{x}^{+}\hat{s}_{x+1}^{-}+\zeta^{*}\hat{s}_{x}^{-}\hat{s}_{x+1}^{+}}{1+|\zeta|^{2}}-\frac{|\zeta|^{2}\hat{s}_{x}^{z}+\hat{s}_{x+1}^{z}}{{1+|\zeta|^{2}}}.$
(38)

with $\zeta\in\mathbb{C}$ Bravyi and Gosset (2015). One may express this
Hamiltonian as

$\displaystyle\mathrm{ker}\,\hat{Q}_{x,x+1}=\mathrm{span}\big{\\{}|00\rangle,|10\rangle+\zeta|01\rangle\big{\\}}.$
(39)

When $\zeta=1$, ground states of $\hat{Q}_{x,x+1}^{\zeta=1}$ are the fully-
polarized state $|{\Phi_{0}}\rangle$ and the zero momentum state of single
spin flip $|\Psi_{0}\rangle$, regardless of the boundary condition. We find
that $\hat{Q}_{x,x+1}$ with $\zeta\neq 1$ can be obtained from
$\hat{Q}_{x,x+1}^{\zeta=1}$ by Witten’s conjugation as

$\displaystyle\hat{Q}_{x,x+1}=(\hat{M}\hat{Q}_{x,x+1}^{\zeta=1}\hat{M}^{-1})^{\dagger}\hat{C}_{x,x+1}(\hat{M}\hat{Q}_{x,x+1}^{\zeta=1}\hat{M}^{-1}),$
(40)

where

$\displaystyle\hat{M}\coloneqq\hat{\mathbbm{1}}\otimes\hat{m}_{\zeta}\otimes\hat{m}_{\zeta}^{2}\otimes\cdots\otimes\hat{m}_{\zeta}^{L-1},$
(41) $\displaystyle\hat{m}_{\zeta}\coloneqq|0\rangle\langle
0|+\zeta|1\rangle\langle 1|,$ (42)
$\displaystyle\hat{C}\coloneqq\hat{\mathbbm{1}}+\frac{(1-|\zeta|^{2})^{2}}{2\mathrm{Re}\zeta(1+|\zeta|^{2})}(|10\rangle\langle
01|+|01\rangle\langle 10|).$ (43)

Hence, the ground states of $\hat{H}^{\mathrm{obc}}$ with $\zeta\neq 1$ are
given by $\hat{M}|{\Phi_{0}}\rangle=|{\Phi_{0}}\rangle$ and
$\hat{M}|\Psi_{0}\rangle\propto\sum_{x=1}^{L}\zeta^{x-1}|x\rangle.$ The latter
remains a ground state of $\hat{H}^{\mathrm{pbc}}$ if and only if
$\zeta^{L}=1$.

Because of the U(1) symmetry of the Hamiltonian in Eq. (38), the plane-wave
state $|{\Psi_{k}}\rangle$ in Eq. (16) is actually an exact eigenstate of
$\hat{H}^{\mathrm{pbc}}$. The eigen energy is given by

$\displaystyle E(k)$
$\displaystyle=\frac{|e^{ik}-\zeta|^{2}}{1+|\zeta|^{2}}=\frac{\big{|}e^{i(k-k_{0})}-|\zeta|\big{|}^{2}}{1+|\zeta|^{2}}$
$\displaystyle=\frac{1-|\zeta|^{2}}{1+|\zeta|^{2}}+\frac{4|\zeta|}{1+|\zeta|^{2}}\sin^{2}((k-k_{0})/2),$
(44)

where $k_{0}$ is defined by $\zeta=|\zeta|e^{ik_{0}}$. Hence, the model is
gapless and the conjecture holds when $|\zeta|=1$, regardless of $\zeta^{L}=1$
or not.

###  III.3 Degeneracy in gapped cases

Although our main focus is on gapless models, let us discuss the ground state
degeneracy of gapped cases for the model in Eq. (14). This result will be used
in our discussion for higher dimensional models in Sec. IV.

Let us start with the rank 1 model. In the $\gamma^{2}\neq\beta^{2}$ case, the
formula Eq. (32) implies that $N_{\mathrm{deg}}=2$, because $m_{\psi}^{L}$
cannot be proportional to $\mathbbm{1}$ when the absolute values of the
diagonal elements $\alpha-i\beta$ and $-\alpha+i\gamma$ do not agree. The
$\alpha=\beta=\gamma=0$ case is exceptional. In this case
$|\psi\rangle=\pm|11\rangle$ is a symmetric product state and any product
state with no consecutive $1$’s is a ground state. Hence, the ground state
degeneracy under PBC with $L\geq 3$ is given by the Lucas number Wikipedia
article

$\displaystyle
N_{\mathrm{deg}}=\sum_{n=0}^{\lfloor\frac{L+1}{2}\rfloor}\binom{L-n+1}{n}-\sum_{n=2}^{\lfloor\frac{L+1}{2}\rfloor}\binom{L-n-1}{n-2},$
(45)

which increases exponentially with the system size $L$. Here $\lfloor
x\rfloor$ represents the greatest integer less than or equal to
$x\in\mathbb{R}$. We append the derivation in Appendix C.

Next, let us discuss the rank 2 case. When $|\zeta|\neq 1$, the ground state
of $\hat{H}^{\mathrm{pbc}}$ composed of the projector in Eq. (38) is unique
($N_{\mathrm{deg}}=1$) because $\zeta^{L}$ cannot be 1. According to Ref.
Bravyi and Gosset (2015), $N_{\mathrm{deg}}\leq 2$ holds even for other rank 2
models under OBC. The min-max principle in Eq. (12) implies the same under
PBC.

In summary, for translation-invariant $s=1/2$ chains with nearest neighbor
interactions, the ground state degeneracy in the gapped cases is bounded as

$\displaystyle N_{\mathrm{deg}}\leq 2,$ (46)

except for the rank 1 model with $\alpha=\beta=\gamma=0$.

Figure 1: The illustration of the 2D model in Eq. (47) and its decomposition
into 1D models.

##  IV 2D models with nearest-neighbor interactions

In this section, we generalize the results in the previous section to two and
three dimensional models using the min-max principle.

We consider a square lattice of $s=1/2$ spins and assume the Hamiltonian of
the form:

$\displaystyle\hat{H}^{\mathrm{2D}}\coloneqq\sum_{x,y=1}^{L}\big{(}\hat{Q}_{(x,y),(x+1,y)}+\hat{Q}_{(x,y),(x,y+1)}\big{)},$
(47)

where $\hat{Q}_{(x,y),(x^{\prime},y^{\prime})}$ is a projector acting on two
spins at $(x,y)$ and $(x^{\prime},y^{\prime})$ [Fig. 1 (a)]. We impose PBC and
assume the translation invariance in both $x$ and $y$ directions. Our goal is
to show that when $\hat{H}^{\mathrm{2D}}$ is frustration free and gapless,
there exists a variational state with properties in Eqs. (8) and (9).

Let us decompose the 2D Hamiltonian into 1D chains in two different ways.

$\displaystyle\hat{H}^{\mathrm{2D}}=\hat{H}^{(1)}+\hat{H}^{(2)}=\hat{H}^{\prime}{}^{(1)}+\hat{H}^{\prime}{}^{(2)}.$
(48)

The first choice is the simple one, decomposing the system into decoupled
chains as illustrated in Fig. 1 (b) and (c):

$\displaystyle\hat{H}^{(1)}\coloneqq\sum_{y=1}^{L}\hat{H}_{y}^{\mathrm{1D}},\quad\hat{H}_{y}^{\mathrm{1D}}\coloneqq\sum_{x=1}^{L}\hat{Q}_{(x,y),(x+1,y)},$
(49)
$\displaystyle\hat{H}^{(2)}\coloneqq\sum_{x=1}^{L}\hat{H}_{x}^{\mathrm{1D}},\quad\hat{H}_{x}^{\mathrm{1D}}\coloneqq\sum_{y=1}^{L}\hat{Q}_{(x,y),(x,y+1)}.$
(50)

For each $y$, $\hat{H}_{y}^{\mathrm{1D}}$ describes the Hamiltonian for the
chain along the $x$ axis; similarly, for each $x$, $\hat{H}_{x}^{\mathrm{1D}}$
describes the Hamiltonian for the chain along the $y$ axis. The second choice
is illustrated in Fig. 1 (d) and (e), in which the chains are connected into
one piece.

Even when these 1D Hamiltonians are frustration-free, whether the total
Hamiltonian
$\hat{H}^{\mathrm{2D}}=\hat{H}^{(1)}+\hat{H}^{(2)}=\hat{H}^{\prime}{}^{(1)}+\hat{H}^{\prime}{}^{(2)}$
remains frustration-free or not is, in general, nontrivial. However, this
issue can be easily gone around in our case. When either
$\hat{H}^{\prime}{}^{(1)}$ or $\hat{H}^{\prime}{}^{(2)}$ is gapped with a
finite ground state degeneracy, the min-max principle suggests that
$\hat{H}^{\mathrm{2D}}$ is also gapped, because
$\hat{H}^{\prime}{}^{(2)}=\hat{H}^{\mathrm{2D}}-\hat{H}^{\prime}{}^{(1)}$ and
$\hat{H}^{\prime}{}^{(1)}=\hat{H}^{\mathrm{2D}}-\hat{H}^{\prime}{}^{(2)}$ are
positive semi-definite 111This argument cannot be directly applied to the
simpler decomposition $\hat{H}^{(1)}+\hat{H}^{(2)}$, because if
$N_{\mathrm{deg}}\geq 2$ for each $\hat{H}_{y}^{\mathrm{1D}}$, then the ground
state degeneracy of $\hat{H}^{(1)}$ becomes $N_{\mathrm{deg}}^{L}$, which
grows exponentially with the system size and the min-max principle becomes
silent. For the same reason, the case of $\alpha=\beta=\gamma=0$ in the rank 1
model should be treated separately, but this case is trivially gapped in any
spatial dimension. . Hence, we can restrict ourselves to the case where both
$\hat{H}^{\prime}{}^{(1)}$ and $\hat{H}^{\prime}{}^{(2)}$ are gapless,
implying that $\hat{H}^{(1)}$ and $\hat{H}^{(2)}$ are also gapless.
Furthermore, as we have seen in Sec. III, when the Hamiltonian for an $s=1/2$
spin chain with nearest-neighbor interaction is gapless, the fully polarized
state $|{\Phi_{0}}\rangle$ in Eq. (15) is a common zero-energy ground state
among all models. Hence, the 2D version of the fully polarized state

$\displaystyle|{\Phi_{0}}\rangle\coloneqq\bigotimes_{x,y=1}^{L}|0\rangle_{(x,y)}$
(51)

is a simultaneous ground state of all terms in $\hat{H}^{\mathrm{2D}}$,
implying that $\hat{H}^{\mathrm{2D}}$ is frustration-free.

To construct a variational state for low-energy excitations, let us define the
plane-wave state of a single spin flip by

$\displaystyle|\Phi_{(k_{x},k_{y})}\rangle\coloneqq\frac{1}{L}\sum_{x,y=1}^{L}e^{i(k_{x}x+k_{y}y)}\hat{s}_{(x,y)}^{-}|{\Phi_{0}}\rangle.$
(52)

The variational energy is given by

$\displaystyle E(k_{x},k_{y})$
$\displaystyle\coloneqq\langle\Phi_{(k_{x},k_{y})}|\hat{H}^{\mathrm{2D}}|\Phi_{(k_{x},k_{y})}\rangle$
$\displaystyle=\sum_{y=1}^{L}\langle\Phi_{(k_{x},k_{y})}|\hat{H}_{y}^{\mathrm{1D}}|\Phi_{(k_{x},k_{y})}\rangle$
$\displaystyle\quad+\sum_{x=1}^{L}\langle\Phi_{(k_{x},k_{y})}|\hat{H}_{x}^{\mathrm{1D}}|\Phi_{(k_{x},k_{y})}\rangle$
$\displaystyle=E(k_{x})+E(k_{y}),$ (53)

where we used the relation

$\displaystyle
E(k_{x})=\frac{1}{L}\sum_{x,x^{\prime}=1}^{L}e^{ik_{x}(x-x^{\prime})}\langle
x^{\prime},y|\hat{H}_{y}^{\mathrm{1D}}|x,y\rangle,$ (54) $\displaystyle
E(k_{y})=\frac{1}{L}\sum_{y,y^{\prime}=1}^{L}e^{ik_{y}(y-y^{\prime})}\langle
x,y^{\prime}|\hat{H}_{x}^{\mathrm{1D}}|x,y\rangle.$ (55)

Therefore,

$\displaystyle
E(k_{x},k_{y})=O\big{(}(k_{x}-k_{0})^{2},(k_{y}-k_{0})^{2}\big{)}$ (56)

The discussion above can be readily extended to the cubic lattice in three
dimensions. The variational energy of the plane-wave state
$|\Phi_{(k_{x},k_{y},k_{z})}\rangle\coloneqq
L^{-3/2}\sum_{x,y,z=1}^{L}e^{i(k_{x}x+k_{y}y+k_{z}z)}\hat{s}_{(x,y,z)}^{-}|{\Phi_{0}}\rangle$
is simply given by $E(k_{x})+E(k_{y})+E(k_{z})$.

Finally, let us discuss whether this analysis can be generalized to other form
of lattices. For example, the nearest-neighbor interaction on the triangular
lattice contains a diagonal interaction

$\displaystyle\sum_{x,y=1}^{L}\hat{Q}_{(x,y),(x+1,y-1)}.$ (57)

More generally, when an interaction $\hat{Q}_{(x,y),(x+d_{x},y+d_{y})}$ among
the spins at $(x,y)$ and $(x+d_{x},y+d_{y})$ is added, the variational energy
obtains a term

$\displaystyle E(k_{x}d_{x}+k_{y}d_{y})$
$\displaystyle=\sum_{x,y=1}^{L}\langle\Phi_{(k_{x},k_{y})}|\hat{Q}_{(x,y),(x+d_{x},y+d_{y})}|\Phi_{(k_{x},k_{y})}\rangle.$
(58)

Hence, the variational state generically becomes gapped unless
$E(k_{0}(d_{x}+d_{y}))=0$. When $k_{0}=0$ (for example, in the ferromagnetic
Heisenberg model), this condition can be easily satisfied, but otherwise some
fine-tuning is required.

##  V 1D examples with next nearest-neighbor interactions

In Sec. III, we showed that frustration-free Hamiltonians for $s=1/2$ spin
chains with nearest-neighbor interactions have a common ground state and a
low-energy variational state. This observation was the key in demonstrating
the softness of the dispersion relation in higher dimensional models in Sec.
IV.

Table 1: Comparison of gapless frustration-free Hamiltonians for $s=1/2$ chain. $|{\Phi_{0}}\rangle$ [(15)] is the fully polarized state and $|{\Psi_{k}}\rangle$ [Eq. (16)] is the plane-wave state of single spin flip.  Interaction type | Range |  $|{\Phi_{0}}\rangle$ is a GS |  $|{\Psi_{k}}\rangle$ is gapless | Variational energy
---|---|---|---|---
Nearest neighbor models with rank 1: (19), (20) with $\gamma=\pm\beta$ | 1 | ✓ | ✓ | $O\big{(}(k-k_{0})^{2}\big{)}$
Nearest neighbor models with rank 2: (38) with $|\zeta|=1$ | 1 | ✓ | ✓ | $O\big{(}(k-k_{0})^{2}\big{)}$
Fredkin spin chain: (63) | 2 | ✓ | ✓ | $O\big{(}k^{2}\big{)}$
GHZ uncle Hamiltonian: (67) | 2 | ✓ | – | $O\big{(}k^{2},L^{-2}\big{)}$
XYZ MG model: (78), (82) with $\theta\neq 0$ | 2 | – | – | $O\big{(}k^{2})$

In this section, we discuss $s=1/2$ spin chains with longer-range
interactions. We assume that the Hamiltonian has the following form

$\displaystyle\hat{H}^{\mathrm{pbc}}\coloneqq\sum_{x=1}^{L}\hat{Q}_{x,x+1,x+2},\quad\hat{H}^{\mathrm{obc}}\coloneqq\sum_{x=1}^{L-2}\hat{Q}_{x,x+1,x+2}.$
(59)

Here, $\hat{Q}_{x,x+1,x+2}$ is a projector acting on the three spins at $x$,
$x+1$, and $x+2$. The interaction range of the Hamiltonian is 2. Unlike the
only nearest-neighbor interaction case in the previous section, our discussion
here is based on examples and hence is not comprehensive. However, these
examples clearly demonstrate difficulties in the direct extension of our
results to more general cases. Namely, the fully polarized state
$|{\Phi_{0}}\rangle$ may not be a ground state and the plane-wave state
$|\Psi_{k}\rangle$ may not be a low-energy state. We instead construct a low-
energy variational state which does not take the form
$\sum_{x}e^{ikx}\hat{O}_{x}|\Phi_{0}\rangle$. We summarize our results in
Table 1.

###  V.1 W state

Let us start with the uncle Hamiltonian constructed by the fully polarized
state and the W state
$|W\rangle\coloneqq(|100\rangle+|010\rangle+|001\rangle)/\sqrt{3}$ Fernández-
González  _et al._ (2015). The kernel of the Hamiltonian is

$\displaystyle\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}=\mathrm{span}\big{\\{}|000\rangle,|W\rangle\big{\\}}.$
(60)

The spin representation of the Hamiltonian is found to be

$\displaystyle\hat{Q}_{x,x+1,x+2}$
$\displaystyle\coloneqq\frac{3}{4}\hat{\mathbbm{1}}-\frac{\hat{s}_{x}^{z}+\hat{s}_{x+1}^{z}+\hat{s}_{x+2}^{z}}{3}+2\hat{s}_{x}^{z}\hat{s}_{x+1}^{z}\hat{s}_{x+2}^{z}$
$\displaystyle\quad-\frac{2}{3}\Big{(}\frac{1}{2}\hat{\mathbbm{1}}+\hat{s}_{x}^{z}\Big{)}\hat{\bm{s}}_{x+1}\cdot\hat{\bm{s}}_{x+2}$
$\displaystyle\quad-\frac{2}{3}\Big{(}\frac{1}{2}\hat{\mathbbm{1}}+\hat{s}_{x+1}^{z}\Big{)}\hat{\bm{s}}_{x+2}\cdot\hat{\bm{s}}_{x}$
$\displaystyle\quad-\frac{2}{3}\Big{(}\frac{1}{2}\hat{\mathbbm{1}}+\hat{s}_{x+2}^{z}\Big{)}\hat{\bm{s}}_{x}\cdot\hat{\bm{s}}_{x+1}.$
(61)

The fully-polarized state $|{\Phi_{0}}\rangle$ and the zero momentum state of
a single spin flip $|\Psi_{0}\rangle$ are the two ground states of this model
regardless of the boundary condition. The state $|{\Psi_{k}}\rangle$ in Eq.
(16) is an exact eigenstate of $\hat{H}^{\mathrm{pbc}}$ as expected by the
U(1) symmetry. The eigen energy is given by

$\displaystyle E(k)$
$\displaystyle=\big{|}\hat{Q}_{1,2,3}(|100\rangle+e^{ik}|010\rangle+e^{2ik}|001\rangle)\big{|}^{2}$
$\displaystyle=\big{|}\hat{Q}_{1,2,3}((e^{ik}-1)|010\rangle+(e^{2ik}-1)|001\rangle)\big{|}^{2}$
$\displaystyle=2(1-\cos
k)\big{|}\hat{Q}_{1,2,3}(|010\rangle+(e^{ik}+1)|001\rangle)\big{|}^{2}$
$\displaystyle=\frac{8}{3}(2+\cos k)\sin^{2}(k/2).$ (62)

As a related model, let us discuss the bulk Hamiltonian for the Fredkin spin
chain Salberger and Korepin (2017):

$\displaystyle\hat{Q}_{x,x+1,x+2}^{\prime}$
$\displaystyle\coloneqq\Big{(}\frac{1}{2}\hat{\mathbbm{1}}+\hat{s}_{x}^{z}\Big{)}\Big{(}\frac{1}{4}\hat{\mathbbm{1}}-\hat{\bm{s}}_{x+1}\cdot\hat{\bm{s}}_{x+2}\Big{)}$
$\displaystyle\quad+\Big{(}\frac{1}{4}\hat{\mathbbm{1}}-\hat{\bm{s}}_{x}\cdot\hat{\bm{s}}_{x+1}\Big{)}\Big{(}\frac{1}{2}\hat{\mathbbm{1}}-\hat{s}_{x+2}^{z}\Big{)}.$
(63)

The kernel of this Hamiltonian is

$\displaystyle\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}^{\prime}$
$\displaystyle=\mathrm{span}\Big{\\{}|000\rangle,|100\rangle,|001\rangle+|010\rangle,$
$\displaystyle\quad\quad\quad|110\rangle,|111\rangle,|011\rangle+|101\rangle\Big{\\}}.$
(64)

Since
$\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}^{\prime}\supset\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}$,
the min-max principle implies that the Fredkin spin chain is gapless with
dispersion equal to or softer than the one implied by Eq. (62). Indeed,
$|{\Psi_{k}}\rangle$ is an exact eigenstate with eigenenergy

$\displaystyle E^{\prime}(k)$ $\displaystyle=1-\cos k=2\sin^{2}(k/2).$ (65)

In these two examples, the fully polarized state $|{\Phi_{0}}\rangle$ is one
of the ground states and the plane-wave state $|\Psi_{k}\rangle$ is a low-
energy state with the dispersion $E(k)=O(k^{2})$.

###  V.2 Greenberger–Horne–Zeilinger uncle Hamiltonian

Next, we discuss the uncle Hamiltonian for the Greenberger–Horne–Zeilinger
(GHZ) state Fernández-González  _et al._ (2015). The kernel of the Hamiltonian
is

$\displaystyle\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}$
$\displaystyle=\mathrm{span}\Big{\\{}|000\rangle,|111\rangle,|100\rangle+|110\rangle,|001\rangle+|011\rangle\Big{\\}}.$
(66)

The spin representation the Hamiltonian is

$\displaystyle\hat{Q}_{x,x+1,x+2}$
$\displaystyle\coloneqq\frac{1}{2}\hat{\mathbbm{1}}-\hat{s}_{x+1}^{z}(\hat{s}_{x}^{z}+\hat{s}_{x+2}^{z})$
$\displaystyle\quad-2\hat{s}_{x+1}^{x}\Big{(}\frac{1}{4}-\hat{s}_{x}^{z}\hat{s}_{x+2}^{z}\Big{)}.$
(67)

To write down ground states and low-energy excitations of this model, let us
define

$\displaystyle|n\rangle\coloneqq|\underbrace{0\cdots
0}_{L-n}\underbrace{1\cdots
1}_{n}\rangle,\quad|\bar{n}\rangle\coloneqq|\underbrace{1\cdots
1}_{L-n}\underbrace{0\cdots 0}_{n}\rangle.$ (68)

for $n=1,2,\cdots,L-1$. For example, $|n\rangle$ satisfies

$\displaystyle\hat{H}^{\mathrm{pbc}}|n\rangle-2|n\rangle$
$\displaystyle=-\frac{1}{2}(|n+1\rangle+|n-1\rangle+\hat{T}|n+1\rangle+\hat{T}^{-1}|n-1\rangle)$
(69)

for $n=2,3,\cdots,L-2$, and

$\displaystyle\hat{H}^{\mathrm{pbc}}|n\rangle-2|n\rangle$
$\displaystyle=\begin{cases}-\frac{1}{2}(|2\rangle+\hat{T}|2\rangle)&(n=1),\\\
-\frac{1}{2}(|L-2\rangle+\hat{T}^{-1}|L-2\rangle)&(n=L-1)\end{cases}$ (70)

for $n=1$ and $L-1$. Based on these expressions, the ground states of
$\hat{H}^{\mathrm{obc}}$ are found to be

$\displaystyle|0\cdots 0\rangle\,(=|\Phi_{0}\rangle),|1\cdots
1\rangle,\sum_{n=1}^{L-1}|n\rangle,\sum_{n=1}^{L-1}|\bar{n}\rangle.$ (71)

The latter two are not consistent with the PBC and are hence not ground states
of $\hat{H}^{\mathrm{pbc}}$.

Although the fully-polarized state $|{\Phi_{0}}\rangle$ is one of the ground
states, the simple variational state $|{\Psi_{k}}\rangle$ is not a low-energy
state:

$\displaystyle\langle\Psi_{k}|\hat{H}^{\mathrm{pbc}}|{\Psi_{k}}\rangle=2.$
(72)

We instead consider a plane-wave state of two domain walls:

$\displaystyle|\Psi_{k,\ell}\rangle\coloneqq\frac{\sqrt{2}}{L}\sum_{n=1}^{L-1}\sum_{m=0}^{L-1}e^{ikm}e^{-ikn/2}\sin(\tfrac{\pi
n\ell}{L})\hat{T}^{m}|n\rangle$ (73)

for $\ell=1,2,\cdots,L-1$. Using
$\hat{T}|\Psi_{k,\ell}\rangle=e^{-ik}|\Psi_{k,\ell}\rangle$ and
$[\hat{T},\hat{H}^{\mathrm{pbc}}]=0$, one can readily show that
$|\Psi_{k,\ell}\rangle$ is an exact eigenstate of $\hat{H}^{\mathrm{pbc}}$
with the eigenvalue

$\displaystyle E_{\ell}(k)$
$\displaystyle=2[1-\cos(k/2)\cos(\tfrac{\pi\ell}{L})]$
$\displaystyle=4\sin^{2}(\tfrac{\pi\ell}{2L})+4\cos(\tfrac{\pi\ell}{L})\sin^{2}(k/4).$
(74)

The first term in the last expression is $O(L^{-2})$, which vanishes in the
thermodynamic limit. The second term is $O(k^{2})$.

Despite the presence of gapless excitations, in this model, the correlation
function of the form

$\displaystyle\langle\Phi_{0}|\hat{\mathcal{O}}_{\bm{x}}^{\dagger}(\hat{\mathbbm{1}}-\hat{G})\hat{\mathcal{O}}^{\prime}_{\bm{y}}|\Phi_{0}\rangle$
(75)

decays exponentially with the system size for any choice of local operators
$\hat{\mathcal{O}}_{\bm{x}}$ and $\hat{\mathcal{O}}^{\prime}_{\bm{y}}$. Here
$\hat{G}$ is the projector onto the ground states of $\hat{H}^{\mathrm{pbc}}$.
This is because both of the two ground states of $\hat{H}^{\mathrm{pbc}}$ (the
first two states in Eq. (71)) are product states.

###  V.3 XYZ MG model

As our last example, let us discuss variations of the MG model. The local
Hamiltonian of the original model is given by

$\displaystyle\hat{Q}_{x,x+1,x+2}$
$\displaystyle\coloneqq\frac{1}{2}\hat{\mathbbm{1}}+\frac{2}{3}(\hat{\bm{s}}_{x}\cdot\hat{\bm{s}}_{x+1}+\hat{\bm{s}}_{x+1}\cdot\hat{\bm{s}}_{x+2}+\hat{\bm{s}}_{x}\cdot\hat{\bm{s}}_{x+2}).$
(76)

Any singlet state $|s\rangle_{x,x+1}\coloneqq(|01\rangle-|10\rangle)/\sqrt{2}$
belongs to the kernel of this Hamiltonian.

$\displaystyle\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}$
$\displaystyle=\mathrm{span}\Big{\\{}|010\rangle-|001\rangle,|100\rangle-|010\rangle,$
$\displaystyle\quad\quad\quad\quad\quad|110\rangle-|101\rangle,|101\rangle-|011\rangle\Big{\\}}.$
(77)

The extension of this model to the XYZ coupling

$\displaystyle\hat{Q}_{x,x+1,x+2}^{\prime}$ $\displaystyle\coloneqq
J_{0}\hat{\mathbbm{1}}+\sum_{a=x,y,z}J_{a}(\hat{s}_{x}^{a}\hat{s}_{x+1}^{a}+\hat{s}_{x+1}^{a}\hat{s}_{x+2}^{a}+\hat{s}_{x}^{a}\hat{s}_{x+2}^{a})$
(78)

is still frustration free for some ranges of $J_{x}$, $J_{y}$, $J_{z}$ Sriram
Shastry and Sutherland (1981); Shastry and Sutherland (1981); Gerhardt  _et
al._ (1998); Xu  _et al._ (2021); Palle and Benton (2021). In particular, when

$\displaystyle J_{x}J_{y}+J_{y}J_{z}+J_{z}J_{x}=0,$ (79)

the model exhibits additional ground state degeneracy. Following Ref. Palle
and Benton (2021), we set $J_{0}=\frac{1}{4}$ and

$\displaystyle J_{x}$
$\displaystyle=\frac{1}{3}-\frac{2}{3}\cos\Big{(}2\theta-\frac{2\pi}{3}\Big{)},$
(80) $\displaystyle J_{y}$
$\displaystyle=\frac{1}{3}-\frac{2}{3}\cos\Big{(}2\theta+\frac{2\pi}{3}\Big{)},$
(81) $\displaystyle J_{z}$ $\displaystyle=\frac{1}{3}-\frac{2}{3}\cos 2\theta$
(82)

with $-\pi/2\leq\theta\leq\pi/2$ so that the condition in Eq. (79) is
satisfied and $\hat{Q}_{x,x+1,x+2}^{\prime}$ becomes a projector. The kernel
of $\hat{Q}_{x,x+1,x+2}^{\prime}$ is given by

$\displaystyle\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}^{\prime}=\mathrm{ker}\,\hat{Q}_{x,x+1,x+2}\oplus\mathrm{span}\big{\\{}|\phi\rangle,|\bar{\phi}\rangle\big{\\}},$
(83)

where 222The presence of $|\bar{\phi}\rangle$ in the kernel is not relevant.
Hence, the rank of $\hat{Q}_{x,x+1,x+2}$ can be three rather than two.

$\displaystyle|\phi\rangle=\cos\theta\,|000\rangle+\frac{\sin\theta}{\sqrt{3}}(|011\rangle+|101\rangle+|110\rangle),$
(84)
$\displaystyle|\bar{\phi}\rangle=\cos\theta\,|111\rangle+\frac{\sin\theta}{\sqrt{3}}(|100\rangle+|010\rangle+|001\rangle).$
(85)

Unless $\theta=0$, the fully polarized state $|{\Phi_{0}}\rangle$ is not a
ground state of the system. The $\theta=\pm\pi/4$ cases are unitary equivalent
to the model discussed in Ref. Saito and Hotta (2024). The plane-wave state
$|{\Psi_{k}}\rangle$ in Eq. (16) is not a low-energy state unless $\theta=0$;
indeed, we find

$\displaystyle\langle\Psi_{k}|\hat{H}^{\mathrm{pbc}}|{\Psi_{k}}\rangle=\frac{\cos^{2}\theta}{3}(1+2\cos
k)^{2}+(L-3)\sin^{2}\theta.$ (86)

To construct a low-energy excitation, we assume $L$ is an odd integer greater
than three. We introduce a plane-wave state of the domain wall state

$\displaystyle|\tilde{\Psi}_{k}\rangle=\frac{1}{\sqrt{Ln_{k}}}\sum_{m=0}^{L-1}e^{ikm}\hat{T}^{m}|D\rangle,$
(87)
$\displaystyle|D\rangle\coloneqq|\phi\rangle_{1,2,3}|s\rangle_{4,5}|s\rangle_{6,7}\cdots|s\rangle_{L-1,L},$
(88)

where $n_{k}\coloneqq 1-(-2)^{-\frac{L-5}{2}}\cos k$ is the normalization
factor that converges to $1$ in the large $L$ limit. Using the translation
symmetry of $\hat{H}$, we find

$\displaystyle\langle\tilde{\Psi}_{k}|\hat{H}|\tilde{\Psi}_{k}\rangle$
$\displaystyle=\frac{\big{\|}\hat{Q}_{2,3,4}(|D\rangle+\hat{T}^{2}|D\rangle)\big{\|}^{2}}{n_{k}}=\frac{2\sin^{2}k}{3n_{k}}.$
(89)

This is $O(k^{2})$, which is consistent with the result of Ref. Palle and
Benton (2021) on Kagome lattice. Hence, our conjecture still holds in this
example as well, despite the fact that $|{\Phi_{0}}\rangle$ is not a ground
state and $|{\Psi_{k}}\rangle$ is not gapless.

##  VI Conclusion

In this paper, we proposed two conjectures regarding frustration-free systems.
The first conjecture posited that no finite-size gap opens between the
degenerate ground states of frustration-free systems. While this has been
implicitly assumed in previous studies Bravyi and Gosset (2015); Gosset and
Mozgunov (2016); Gosset and Huang (2016), we pointed out the necessity of
being cautious as it is actually a non-trivial assumption.

The second conjecture stated that in a gapless frustration-free system with
translational symmetry, the dispersion relation of low-energy excitations near
a certain wave number $\bm{k}_{0}$ can be bounded above by a quadratic
dispersion, i.e., $O\big{(}|\bm{k}-\bm{k}_{0}|^{2},L^{-2}\big{)}$. We proved
this conjecture for the case of an $s=1/2$ spin chain with nearest-neighbor
interactions by combining the result of a seminal work by Bravyi and Gosset
Bravyi and Gosset (2015) and the min-max theorem. Furthermore, we extended
these results to two- and three-dimensional models on the cubic lattice.
However, it became clear that this method could not be directly extended to
cases where three or more neighboring spins interact simultaneously. Extending
our results to cases where the Hilbert space dimension at each site is larger
than two or to models with longer-range interactions constitutes important
future work.

Finally, there is a related, more general conjecture that the finite-size gap
$\epsilon=E_{\tilde{N}_{\mathrm{deg}}+1}$ for a gapless frustration-free
Hamiltonian can be bounded above by $O(L^{-2})$ regardless of the presence or
absence of translational symmetry or the details of the boundary conditions.
In fact, in the accompanying paper Masaoka  _et al._ (2024), we prove this
statement for critical frustration-free systems in which a ground-state
correlation function shows a power-law behavior. However, such an argument is
not applicable, for example, to the uncle Hamiltonian for the GHZ state since
all correlation functions decays exponentially as discussed in Sec. V.2.

###### Acknowledgements.

We thank Hosho Katsura for useful discussions. The work of H.W. is supported
by JSPS KAKENHI Grant No. JP24K00541. This research is funded in part by the
Gordon and Betty Moore Foundation’s EPiQS Initiative, Grant GBMF8683 to T.S.

## References

  * Auerbach (2012) A. Auerbach,  _Interacting electrons and quantum magnetism_ (Springer Science & Business Media, 2012).
  * Tasaki (2020) H. Tasaki,  _Physics and Mathematics of Quantum Many-Body Systems_ (Springer, 2020).
  * Fannes  _et al._ (1992) M. Fannes, B. Nachtergaele, and R. F. Werner, Communications in Mathematical Physics 144, 443 (1992).
  * Fernández-González  _et al._ (2015) C. Fernández-González, N. Schuch, M. M. Wolf, J. I. Cirac, and D. Pérez-García, Communications in Mathematical Physics 333, 299 (2015).
  * Ogunnaike  _et al._ (2023) O. Ogunnaike, J. Feldmeier, and J. Y. Lee, Phys. Rev. Lett. 131, 220403 (2023).
  * Watanabe  _et al._ (2023) H. Watanabe, H. Katsura, and J. Y. Lee, “Spontaneous breaking of u(1) symmetry at zero temperature in one dimension,” (2023), arXiv:2310.16881 .
  * Palle and Benton (2021) G. Palle and O. Benton, Phys. Rev. B 103, 214428 (2021).
  * Ren  _et al._ (2024) J. Ren, Y.-P. Wang, and C. Fang, “Quasi-nambu-goldstone modes in many-body scar models,” (2024), arXiv:2405.00785 .
  * Bravyi and Gosset (2015) S. Bravyi and D. Gosset, J. Math. Phys. 56, 061902 (2015).
  * Gosset and Mozgunov (2016) D. Gosset and E. Mozgunov, Journal of Mathematical Physics 57, 091901 (2016).
  * Gosset and Huang (2016) D. Gosset and Y. Huang, Phys. Rev. Lett. 116, 097202 (2016).
  * Knabe (1988) S. Knabe, J. Stat. Phys. 52, 627 (1988).
  * Anshu (2020) A. Anshu, Phys. Rev. B 101, 165104 (2020).
  * Katsura  _et al._ (2015) H. Katsura, D. Schuricht, and M. Takahashi, Phys. Rev. B 92, 115137 (2015).
  * Wouters  _et al._ (2018) J. Wouters, H. Katsura, and D. Schuricht, Phys. Rev. B 98, 155119 (2018).
  * Witten (1982) E. Witten, Nuclear Physics B 202, 253 (1982).
  * Wouters  _et al._ (2021) J. Wouters, H. Katsura, and D. Schuricht, SciPost Phys. Core 4, 027 (2021).
  * (18) Wikipedia article, “Lucas number,” .
  * Note (1) This argument cannot be directly applied to the simpler decomposition $\hat{H}^{(1)}+\hat{H}^{(2)}$, because if $N_{\mathrm{deg}}\geq 2$ for each $\hat{H}_{y}^{\mathrm{1D}}$, then the ground state degeneracy of $\hat{H}^{(1)}$ becomes $N_{\mathrm{deg}}^{L}$, which grows exponentially with the system size and the min-max principle becomes silent. For the same reason, the case of $\alpha=\beta=\gamma=0$ in the rank 1 model should be treated separately, but this case is trivially gapped in any spatial dimension.
  * Salberger and Korepin (2017) O. Salberger and V. Korepin, Reviews in Mathematical Physics 29, 1750031 (2017).
  * Sriram Shastry and Sutherland (1981) B. Sriram Shastry and B. Sutherland, Physica B+C 108, 1069 (1981).
  * Shastry and Sutherland (1981) B. S. Shastry and B. Sutherland, Phys. Rev. Lett. 47, 964 (1981).
  * Gerhardt  _et al._ (1998) C. Gerhardt, K.-H. Mütter, and H. Kröger, Phys. Rev. B 57, 11504 (1998).
  * Xu  _et al._ (2021) H.-Z. Xu, S.-Y. Zhang, G.-C. Guo, and M. Gong, Scientific Reports 11, 6462 (2021).
  * Note (2) The presence of $|\bar{\phi}\rangle$ in the kernel is not relevant. Hence, the rank of $\hat{Q}_{x,x+1,x+2}$ can be three rather than two.
  * Saito and Hotta (2024) H. Saito and C. Hotta, Phys. Rev. Lett. 132, 166701 (2024).
  * Masaoka  _et al._ (2024) R. Masaoka, T. Soejima, and H. Watanabe, in progress (2024).

##  Appendix A Proof of the inequality (11)

Let $\mathcal{M}_{j}$ be an arbitrary $j$ dimensional subspace of the entire
Hilbert space $\mathcal{H}_{D}$. We _maximize_ the energy expectation value
$\langle\Phi|\hat{H}|\Phi\rangle$ by varying the normalized state
$|\Phi\rangle$ belonging to $\mathcal{M}_{j}$. We then _minimize_ the maximum
value $\max_{|\Phi\rangle\in\mathcal{M}_{j}}\langle\Phi|\hat{H}|\Phi\rangle$
by varying the subspace $\mathcal{M}_{j}$ of $\mathcal{H}_{D}$. By definition,
the minimum value $E_{j}$ is achieved when $\mathcal{M}_{j}$ is spanned by the
$j$ eigenvectors corresponding to the eigenvalues $E_{1},E_{2},\cdots,E_{j}$.
Hence, we obtain an expression

$\displaystyle
E_{j}=\min_{\mathcal{M}_{j}\subset\mathcal{H}_{D}}\Big{(}\max_{|\Phi\rangle\in\mathcal{M}_{j}}\langle\Phi|\hat{H}|\Phi\rangle\Big{)}.$
(90)

The same argument leads to

$\displaystyle
E_{j}^{\prime}=\min_{\mathcal{M}_{j}\subset\mathcal{H}_{D}}\Big{(}\max_{|\Phi\rangle\in\mathcal{M}_{j}}\langle\Phi|\hat{H}^{\prime}|\Phi\rangle\Big{)}.$
(91)

Finally, by the definition of $\hat{V}=\hat{H}^{\prime}-\hat{H}\geq 0$, we
have

$\displaystyle\langle\Phi|\hat{H}^{\prime}|\Phi\rangle\geq\langle\Phi|\hat{H}|\Phi\rangle$
(92)

for any state $|\Phi\rangle$ in $\mathcal{H}_{D}$. In particular, if
$\langle\Phi|\hat{H}|\Phi\rangle$ and
$\langle\Phi|\hat{H}^{\prime}|\Phi\rangle$ are maximized by
$|\Phi\rangle_{*}\in\mathcal{M}_{j}$ and
$|\Phi\rangle_{*}^{\prime}\in\mathcal{M}_{j}$, respectively, we have

$\displaystyle\max_{|\Phi\rangle\in\mathcal{M}_{j}}\langle\Phi|\hat{H}^{\prime}|\Phi\rangle$
$\displaystyle=\langle\Phi_{*}^{\prime}|\hat{H}^{\prime}|\Phi_{*}^{\prime}\rangle$
$\displaystyle\geq\langle\Phi_{*}|\hat{H}^{\prime}|\Phi_{*}\rangle$
$\displaystyle\geq\langle\Phi_{*}|\hat{H}|\Phi_{*}\rangle=\max_{|\Phi\rangle\in\mathcal{M}_{j}}\langle\Phi|\hat{H}|\Phi\rangle.$
(93)

This relation holds for any $\mathcal{M}_{j}\subset\mathcal{H}_{D}$. Hence, we
arrive at the inequality (11).

##  Appendix B Derivation of Eq. (20)

Let us consider a local unitary that maps $|\psi\rangle$ to
$|\psi^{\prime}\rangle=\hat{U}\otimes\hat{U}|\psi\rangle$. In general,
$\hat{U}$ can be parametrized by $u_{1},u_{2}\in\mathbb{C}$
($|u_{1}|^{2}+|u_{2}|^{2}=1$) and $\theta\in[0,2\pi)$ as

$\displaystyle\hat{U}|0\rangle=e^{i\theta}(u_{1}|0\rangle+u_{2}|1\rangle),$
(94)
$\displaystyle\hat{U}|1\rangle=e^{i\theta}(-u_{2}^{*}|0\rangle+u_{1}^{*}|1\rangle),$
(95)

The inverse of $\hat{U}$ reads

$\displaystyle\hat{U}^{\dagger}|0\rangle=e^{-i\theta}(u_{1}^{*}|0\rangle-
u_{2}|1\rangle),$ (96)
$\displaystyle\hat{U}^{\dagger}|1\rangle=e^{-i\theta}(u_{2}^{*}|0\rangle+u_{1}|1\rangle).$
(97)

Hence

$\displaystyle m_{\psi^{\prime}}$
$\displaystyle=\begin{pmatrix}\langle\psi|\hat{U}^{\dagger}\otimes\hat{U}^{\dagger}|01\rangle&\langle\psi|\hat{U}^{\dagger}\otimes\hat{U}^{\dagger}|11\rangle\\\
-\langle\psi|\hat{U}^{\dagger}\otimes\hat{U}^{\dagger}|00\rangle&-\langle\psi|\hat{U}^{\dagger}\otimes\hat{U}^{\dagger}|10\rangle\end{pmatrix}$
$\displaystyle=e^{-2i\theta}\begin{pmatrix}\langle\psi|(u_{1}^{*}|0\rangle-
u_{2}|1\rangle)(u_{2}^{*}|0\rangle+u_{1}|1\rangle)&\langle\psi|(u_{2}^{*}|0\rangle+u_{1}|1\rangle)(u_{2}^{*}|0\rangle+u_{1}|1\rangle)\\\
-\langle\psi|(u_{1}^{*}|0\rangle-u_{2}|1\rangle)(u_{1}^{*}|0\rangle-
u_{2}|1\rangle)&-\langle\psi|(u_{2}^{*}|0\rangle+u_{1}|1\rangle)(u_{1}^{*}|0\rangle-
u_{2}|1\rangle)\end{pmatrix}$
$\displaystyle=e^{-2i\theta}\begin{pmatrix}u_{1}&-u_{2}^{*}\\\
u_{2}&u_{1}^{*}\end{pmatrix}\begin{pmatrix}\langle\psi|(u_{1}^{*}|0\rangle-
u_{2}|1\rangle)|1\rangle&\langle\psi|(u_{2}^{*}|0\rangle+u_{1}|1\rangle)|1\rangle\\\
-\langle\psi|(u_{1}^{*}|0\rangle-
u_{2}|1\rangle)|0\rangle&-\langle\psi|(u_{2}^{*}|0\rangle+u_{1}|1\rangle)|0\rangle\end{pmatrix}$
$\displaystyle=e^{-2i\theta}\begin{pmatrix}u_{1}&-u_{2}^{*}\\\
u_{2}&u_{1}^{*}\end{pmatrix}\begin{pmatrix}\langle\psi|01\rangle&\langle\psi|11\rangle\\\
-\langle\psi|00\rangle&-\langle\psi|10\rangle\end{pmatrix}\begin{pmatrix}u_{1}^{*}&u_{2}^{*}\\\
-u_{2}&u_{1}\end{pmatrix}$ $\displaystyle=e^{-2i\theta}Um_{\psi}U^{\dagger}.$
(98)

Therefore, by choosing $U=\begin{pmatrix}u_{1}&-u_{2}^{*}\\\
u_{2}&u_{1}^{*}\end{pmatrix}$ and $\theta$ properly, one gets the form in Eq.
(25), which is equivalent to the parametrization in Eq. (20).

##  Appendix C The case of $\det m_{\psi}=0$.

Here we discuss the case $\alpha=\beta=0$ in the rank 1 model. (The
$\alpha=\gamma=0$ case can be treated in the same way.) In this case,
$|\psi\rangle$ is not entangled because it can be written as a product state

$\displaystyle|\psi\rangle=|1\rangle\otimes|v^{\perp}\rangle,$ (99)

where $|v^{\perp}\rangle=i\gamma|0\rangle+\delta|1\rangle$ with
$\gamma^{2}+\delta^{2}=1$. According to Ref. Bravyi and Gosset (2015),
excitations under OBC are gapped in this case, which implies that excitations
under PBC are also gapped.

When $\gamma\neq 0$, orthogonal ground states under OBC are product states
with a single domain-wall:

$\displaystyle|\underbrace{0\cdots 0}_{n-1}v^{\perp}\underbrace{v\cdots
v}_{L-n}\rangle\quad(n=1,\cdots L),$ (100)

where $|v\rangle=\delta|0\rangle+i\gamma|1\rangle$ is orthogonal to
$|v^{\perp}\rangle$. Translation-invariant product states $|v\cdots v\rangle$
and $|0\cdots 0\rangle$ are also ground states but only the former is
orthogonal to the domain-wall states and the latter is not linearly
independent. In contrast, under PBC, domain wall states violate the boundary
term and the two translation-invariant product states give the ground states.
Thus the formula in Eq. (32) is applicable to this case.

On the other hand, the $\alpha=\beta=\gamma=0$ case is exceptional. In this
case $|\psi\rangle=\pm|11\rangle$ is a symmetric product state and any product
state with no consecutive $1$’s is a ground state of $\hat{H}^{\mathrm{obc}}$
and $\hat{H}^{\mathrm{pbc}}$. Hence,

$\displaystyle
N_{\mathrm{deg}}^{\mathrm{obc}}=\sum_{n=0}^{\lfloor\frac{L+1}{2}\rfloor}\binom{L-n+1}{n},$
(101) $\displaystyle
N_{\mathrm{deg}}^{\mathrm{pbc}}=N_{\mathrm{deg}}^{\mathrm{obc}}-\sum_{n=2}^{\lfloor\frac{L+1}{2}\rfloor}\binom{L-n-1}{n-2},$
(102)

where $\lfloor x\rfloor$ represents the greatest integer less than or equal to
$x\in\mathbb{R}$. The second term in $N_{\mathrm{deg}}^{\mathrm{pbc}}$
represents the number of valid product states under OBC which start with
$|1\rangle_{x=1}$ and end with $|1\rangle_{x=L}$. The excitation gap is
exactly 1.