Commuting stabilizers and topological degeneracy

Since ${\mathrm{\partial }}_1{\mathrm{\partial }}_2=0$, the supports of $A_v$ and $B_f$ overlap in even parity, so they commute. Each is a self-adjoint involution; hence $(I-A_v)\mathrm{/}2$ and $(I-B_f)\mathrm{/}2$ are commuting orthogonal projections. Multiplication by the positive coefficients makes each summand positive semidefinite.

The product of all vertex operators is $I$, because each edge has two endpoint incidences counted modulo two. The product of all face operators is $I$, because the closed surface has two incident face sides at each edge. Therefore any simultaneous joint eigenvalue assignment has an even number of violated vertex constraints and an even number of violated face constraints.

The image of ${\mathrm{\partial }}_1$ is the even-parity subspace of ${\mathbb{F}}_2^V$: every edge boundary has even parity, while for a fixed vertex $v_0$, a path to each $v\mathrm{\ne }{v}_0$ has boundary $v+v_0$, and these vectors span that subspace. Thus $\mathrm{rank}{\mathrm{\partial }}_1=\mathrm{\mid }V\mathrm{\mid }-1$. A vertex coefficient vector lies in $\ker {\mathrm{\partial }}_1^T$ exactly when it is orthogonal to this even-parity subspace; this orthogonal complement consists of the constant vectors and has dimension one. Rank-nullity gives $\mathrm{rank}{\mathrm{\partial }}_1^T=\mathrm{\mid }V\mathrm{\mid }-1$, the number of independent vertex stabilizers. A face 2-chain is in $\ker {\mathrm{\partial }}_2$ exactly when its coefficients agree across adjacent faces; dual-graph connectedness makes this kernel the one-dimensional constant subspace, so $\mathrm{rank}{\mathrm{\partial }}_2=\mathrm{\mid }F\mathrm{\mid }-1$, the number of independent face stabilizers. Hence the combined stabilizer group has rank $r=\mathrm{\mid }V\mathrm{\mid }+\mathrm{\mid }F\mathrm{\mid }-2$.

Choose independent generators $S_1,\dots ,S_r$ from those commuting involutions and set $\mathrm{\Pi }=2^{-r}{\prod }_{j=1}^r(I+S_j)$. This is an orthogonal projection. Independence of the vertex and face support vectors implies that its $2^r$ Pauli terms are distinct and only the all-identity term is the identity matrix. Every other Pauli term has trace zero because at least one tensor factor is $X$, $Z$, or $XZ$, each of which has trace zero. Thus $\mathrm{Tr}\mathrm{\Pi }=2^{-r}{2}^{\mathrm{\mid }E\mathrm{\mid }}>0$, so the common $+1$ eigenspace is nonzero and has dimension $2^{\mathrm{\mid }E\mathrm{\mid }-r}$. Each penalty is an orthogonal projection by step 1.1, and for every $\psi$ the quadratic form is $⟨\psi ,H_K\psi ⟩={\sum }_{v\in V}{J}_v{\parallel \frac{I-A_v}{2}\psi \parallel }^2+{\sum }_{f\in F}{K}_f{\parallel \frac{I-B_f}{2}\psi \parallel }^2$. Positivity of every coupling makes this quantity zero exactly when every penalty annihilates $\psi$, equivalently when every stabilizer has eigenvalue $+1$. Thus $\ker H_K$ is the common $+1$ eigenspace, the Hamiltonian is frustration free, and its ground space has dimension $2^{\mathrm{\mid }E\mathrm{\mid }-r}$.

Put $m=\min (\{J_v\}\cup \{K_f\})$. The commuting self-adjoint penalty projections have a common orthonormal eigenbasis: diagonalize one projection and restrict the remaining commuting projections to each invariant eigenspace, iterating over the finite family. Thus every eigenvalue of $H_K$ occurs on a joint eigenvector. Outside the ground space, such a vector violates at least one constraint; by the two product identities of step 1.2, at least two constraints of that same type are violated. Each contributes at least $m$, so every excited eigenvalue is at least $2m$ above the ground energy zero. If the orthogonal complement of the ground space is zero, the stated $+\mathrm{\infty }$ convention applies.

The dimension found in step 2.1 is $2^{\mathrm{\mid }E\mathrm{\mid }-\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }F\mathrm{\mid }+2}$. By [F2], under [A1], $\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }E\mathrm{\mid }+\mathrm{\mid }F\mathrm{\mid }=2-2g$, so $\mathrm{\mid }E\mathrm{\mid }-\mathrm{\mid }V\mathrm{\mid }-\mathrm{\mid }F\mathrm{\mid }+2=2g$. Therefore the ground-space dimension is $2^{2g}$.

On the uniform square torus, applying $Z$ on one edge to any ground vector flips exactly the two distinct endpoint vertex eigenvalues and no face eigenvalue, giving an excited vector of energy $2J$. Applying $X$ on one edge flips exactly the two adjacent face eigenvalues and no vertex eigenvalue, giving an excited vector of energy $2K$. The lower bound of step 2.2 is $2\min (J,K)$, and one of these two constructions attains it. Thus the exact first-excitation cost is $2\min (J,K)$.