Introduction and main results
Let G = ( V , c ) G=(V,c) G = ( V , c ) be a connected undirected weighted graph on n n n vertices, with symmetric conductances c u v = c v u ≥ 0 c_{uv}=c_{vu}\ge0 c uv = c v u ≥ 0 , c u u = 0 c_{uu}=0 c uu = 0 , for all u , v ∈ V u,v\in V u , v ∈ V . We regard { u , v } \{u,v\} { u , v } as an edge exactly when c u v > 0 c_{uv}>0 c uv > 0 . Fix distinct terminals x , y ∈ V x,y\in V x , y ∈ V . The effective conductance between x x x and y y y is
c e f f ( x , y ) : = inf { ∑ { u , v } c u v [ ϕ ( u ) − ϕ ( v ) ] 2 | ϕ : V → R , ϕ ( x ) = 0 , ϕ ( y ) = 1 } . (1) c_{\mathrm{eff}}(x,y):=\inf\left\{\sum_{\{u,v\}}c_{uv}[\phi(u)-\phi(v)]^2\ \middle|\ \phi:V\to\mathbb{R},\ \phi(x)=0,\ \phi(y)=1\right\}. \tag*{(1)} c eff ( x , y ) := inf ⎩ ⎨ ⎧ { u , v } ∑ c uv [ ϕ ( u ) − ϕ ( v ) ] 2 ϕ : V → R , ϕ ( x ) = 0 , ϕ ( y ) = 1 ⎭ ⎬ ⎫ . (1)
The energy functional in (1) has a unique minimizer, which we denote by p p p and call the harmonic x x x –y y y voltage : it satisfies p ( x ) = 0 p(x)=0 p ( x ) = 0 , p ( y ) = 1 p(y)=1 p ( y ) = 1 , and the discrete Laplace’s equation
∑ v ∈ V ∖ { u } c u v [ p ( u ) − p ( v ) ] = 0 , u ∈ V ∖ { x , y } . (2) \sum_{v\in V\setminus\{u\}}c_{uv}[p(u)-p(v)]=0,\qquad u\in V\setminus\{x,y\}. \tag*{(2)} v ∈ V ∖ { u } ∑ c uv [ p ( u ) − p ( v )] = 0 , u ∈ V ∖ { x , y } . (2)
The discrete maximum principle gives 0 ≤ p ≤ 1 0 \le p \le1 0 ≤ p ≤ 1 on V V V . By the homogeneity of the variational characterization in (1) , every ϕ : V → R \phi: V \to\mathbb{R} ϕ : V → R satisfies
c e f f ( x , y ) [ ϕ ( x ) − ϕ ( y ) ] 2 ≤ ∑ { u , v } c u v [ ϕ ( u ) − ϕ ( v ) ] 2 . (3) c_{\mathrm{eff}}(x,y)[\phi(x)-\phi(y)]^2 \le\sum_{\{u,v\}} c_{uv}[\phi(u)-\phi(v)]^2. \tag*{(3)} c eff ( x , y ) [ ϕ ( x ) − ϕ ( y ) ] 2 ≤ { u , v } ∑ c uv [ ϕ ( u ) − ϕ ( v ) ] 2 . (3)
The moving particle lemma (or inequality) is the interacting particle analog of the inequality (3) : the scalar edge energy on the right-hand side is replaced by the Dirichlet form of the particle system, while the terminal difference on the left-hand side is replaced by the energy cost of exchanging the configuration at x x x and y y y .
The moving particle lemma has a long history in the interacting particle systems literature; see, for example, Kipnis and Landim [7, §5.5]. In the classical argument, one chooses a path joining the two sites, writes the distant exchange as a telescoping sequence of nearest-neighbor exchanges along that path, and applies Cauchy–Schwarz. The resulting constants are controlled by path lengths and congestion. Alternatively, one may replace this pathwise comparison by the electrical coefficient (1) .
Throughout this paper we work with the interchange process on G G G . Let S V \mathfrak{S}_V S V denote the symmetric group on V V V ; it acts by left multiplication in its regular representation on R [ S V ] \mathbb{R}[\mathfrak{S}_V] R [ S V ] . For distinct u , v ∈ V u,v \in V u , v ∈ V , denote their transposition by τ u v \tau_{uv} τ uv . We define the positive semidefinite interchange process generator as
L G I P : = ∑ { u , v } ⊂ V c u v ( I − τ u v ) . \mathcal{L}^{\mathrm{IP}}_G := \sum_{\{u,v\}\subset V} c_{uv}(I-\tau_{uv}). L G IP := { u , v } ⊂ V ∑ c uv ( I − τ uv ) .
In [5 ] , this author used the octopus inequality of Caputo, Liggett, and Richthammer [3 ] —the key ingredient towards resolving Aldous’ spectral gap conjecture—to prove the following operator inequality.
Proposition 1.1 (Moving particle lemma, cf. Lemma 3.2 in [5 ] ). On every finite connected weighted graph G = ( V , c ) G=(V,c) G = ( V , c ) , and distinct vertices x , y ∈ V x,y \in V x , y ∈ V ,
L G I P ≥ c e f f ( x , y ) ( I − τ x y ) (4) \mathcal{L}^{\mathrm{IP}}_G \ge c_{\mathrm{eff}}(x,y)(I-\tau_{xy}) \tag*{(4)} L G IP ≥ c eff ( x , y ) ( I − τ x y ) (4) as operators on the regular representation of S V \mathfrak{S}_V S V .
The proof of Proposition 1.1 proceeds via eliminating vertices successively while preserving the effective conductance between x x x and y y y , and applying the octopus inequality [3 Theorem 2.3] at each step of the elimination. The argument goes through in only a few lines, but hides the nontrivial nature of the octopus inequality, and does not utilize any algebraic aspect thereof. For a representation theory perspective of the octopus inequality, see e.g. Cesi [4 ] .
Alon and Kozma Alon and Kozma [1 ] later described [5 ] as the first application of the octopus inequality for a purpose beyond the proof of Aldous’ spectral gap conjecture. Of course there have been many more developments since then, thanks to our better understanding of the algebraic structure of the operators involved. The main focus of this work is to establish a full characterization of attaining equality in (4) .
In order to proceed, let us discuss how to transfer Proposition 1.1 to the symmetric exclusion process on G G G . For 0 ≤ r ≤ n 0 \le r \le n 0 ≤ r ≤ n , write Ω r = ( V r ) \Omega_r=\binom{V}{r} Ω r = ( r V ) for the space of r r r -subsets (or the r r r -particle sector in the exclusion process language), and equip R Ω r \mathbb{R}^{\Omega_r} R Ω r with the normalized inner product
⟨ f , g ⟩ r = ( n r ) − 1 ∑ ξ ∈ Ω r f ( ξ ) g ( ξ ) , ∥ f ∥ r 2 = ⟨ f , f ⟩ r . (5) \langle f,g\rangle_r=\binom{n}{r}^{-1}\sum_{\xi\in\Omega_r}f(\xi)g(\xi), \qquad\|f\|_r^2=\langle f,f\rangle_r. \tag*{(5)} ⟨ f , g ⟩ r = ( r n ) − 1 ξ ∈ Ω r ∑ f ( ξ ) g ( ξ ) , ∥ f ∥ r 2 = ⟨ f , f ⟩ r . (5)
The positive semidefinite exclusion process generator is
L G ( r ) = ∑ { u , v } ⊂ V c u v ( I − τ u v ) , (6) \mathcal{L}^{(r)}_G=\sum_{\{u,v\}\subset V}c_{uv}(I-\tau_{uv}), \tag*{(6)} L G ( r ) = { u , v } ⊂ V ∑ c uv ( I − τ uv ) , (6)
where the transposition τ u v \tau_{uv} τ uv acts on subsets by interchanging u u u and v v v , and on functions by pullback. Now apply Proposition 1.1 to the permutation representation on r r r -subsets to obtain
L G ( r ) ≥ c e f f ( x , y ) ( I − τ x y ) . (7) \mathcal{L}^{(r)}_G \ge c_{\mathrm{eff}}(x,y)(I-\tau_{xy}). \tag*{(7)} L G ( r ) ≥ c eff ( x , y ) ( I − τ x y ) . (7)
It is standard to express (7) as a quadratic form inequality under the inner product (5) ; in particular at r = 1 r=1 r = 1 one recovers (3) . There is also a related product Bernoulli formulation of this quadratic form inequality that is recorded as [5 Theorem 1.1] . For most of this paper, we focus on the equality analysis in each fixed r r r -particle sector.
This requires us to analyze how the operators act on the irreducible representations of G V \mathcal{G}_V G V , or the so-called Specht modules. For background and standard facts on Specht modules, Young diagrams, and the branching rule used below, we refer the reader to Sagan [9 ] . For a given partition λ = ( λ 1 , … , λ m ) \lambda=(\lambda_1,\ldots,\lambda_m) λ = ( λ 1 , … , λ m ) of n n n , write S λ S^\lambda S λ for the Specht module (over the field R \mathbb{R} R ) of G V \mathcal{G}_V G V indexed by λ \lambda λ . For r ≤ n 2 r\le\frac{n}{2} r ≤ 2 n , Young’s rule [9 §2.11] states that the r r r -subset permutation representation decomposes multiplicity-free as
R Ω r ≅ S ( n ) ⊕ S ( n − 1 , 1 ) ⊕ ⋯ ⊕ S ( n − r , r ) . (8) \mathbb{R}\Omega^r \cong S^{(n)} \oplus S^{(n-1,1)} \oplus\cdots\oplus S^{(n-r,r)}. \tag*{(8)} R Ω r ≅ S ( n ) ⊕ S ( n − 1 , 1 ) ⊕ ⋯ ⊕ S ( n − r , r ) . (8)
This decomposition agrees with the Hoeffding decomposition to be used from § 4 onwards: the constant sector is S ( n ) S^{(n)} S ( n ) , the linear sector is S ( n − 1 , 1 ) S^{(n-1,1)} S ( n − 1 , 1 ) , the quadratic sector is S ( n − 2 , 2 ) S^{(n-2,2)} S ( n − 2 , 2 ) , and, more generally, the degree-j j j Hoeffding layer is the copy of S ( n − j , j ) S^{(n-j,j)} S ( n − j , j ) . Thus symmetric exclusion realizes the interchange generator on the two-row irreducible representations in (8) , with exactly the same conductance coefficients.
In [5 ] this author conjectured that the coefficient c e f f ( x , y ) c_{\mathrm{eff}}(x,y) c eff ( x , y ) in (4) should be sharp. Recently Zhu [10 ] proved the said conjecture on every G G G by exhibiting a vector in the linear sector S ( n − 1 , 1 ) S^{(n-1,1)} S ( n − 1 , 1 ) that realizes equality in (4) ; see also Proposition 8.5 below. This naturally leads to the next question studied in this work: which vectors outside the sectors S ( n ) S^{(n)} S ( n ) and S ( n − 1 , 1 ) S^{(n-1,1)} S ( n − 1 , 1 ) attain equality in (4) ? We call any nonzero vector that attains equality in the relevant moving particle inequality an equality vector .
A related but distinct problem concerning the second eigenspace of the interchange process generator L G I P \mathcal{L}^{\mathrm{IP}}_G L G IP was studied by Belotserkovskiy and this author [2 ] ; see Remark 2.4 for the precise comparison.
Summary of the main results
The regular representation decomposes orthogonally as
R [ G V ] ≅ ⨁ λ ⊢ n S λ ⊗ R d λ , d λ : = dim S λ . (9) \mathbb{R}[\mathcal{G}_V] \cong\bigoplus_{\lambda\vdash n} S^\lambda\otimes\mathbb{R}^{d_\lambda}, \qquad d_\lambda:= \dim S^\lambda. \tag*{(9)} R [ G V ] ≅ λ ⊢ n ⨁ S λ ⊗ R d λ , d λ := dim S λ . (9)
where each Specht module S λ S^\lambda S λ occurs with multiplicity d λ d_\lambda d λ ; see [9 §1.10 and §2.3] . Because the operators on both sides of (4) are built from permutations, the equality problem can be studied on each irreducible summand. Theorem 2.3 shows that no nonzero equality vector can be supported on a partition with three or more rows. Consequently, all equality phenomena for the interchange process are already visible in the two-row representations realized by symmetric exclusion. We name this finding two-row rigidity .
By carrying out the analysis in each r r r -particle sector of symmetric exclusion, we obtain a complete graph-theoretic classification, stated formally in Theorem 7.5 . Put W : = V ∖ { x , y } W:=V\setminus\{x,y\} W := V ∖ { x , y } , let G [ W ] G[W] G [ W ] be the induced graph on W W W that retains the edges of positive conductance inside W W W , and let p p p be the harmonic x x x -y y y voltage from (2) . Then equality in the moving particle lemma outside the constant sector S ( n ) S^{(n)} S ( n ) and the linear sector S ( n − 1 , 1 ) S^{(n-1,1)} S ( n − 1 , 1 ) occurs if and only if one of the following alternatives holds:
(a) p ( u ) = 1 2 p(u)=\frac{1}{2} p ( u ) = 2 1 for every u ∈ W u\in W u ∈ W , and G [ W ] G[W] G [ W ] has at least two connected components;
(b) p p p is constant on every connected component of G [ W ] G[W] G [ W ] , and the component values are exactly a a a and 1 − a 1-a 1 − a for some 0 ≤ a < 1 2 0\le a<\frac{1}{2} 0 ≤ a < 2 1 , with both values occurring.
No other weighted graph and terminal pair supports equality beyond the constant and linear sectors. Theorems 8.4 and 8.6 determine the dimension and structure of every surviving equality space, first in each top Hoeffding degree and then in every particle sector. Finally, Theorem 8.8 assembles these spaces into the complete equality kernel for the interchange process.
The rest of the paper is organized as follows. The proof begins with the aforementioned two-row rigidity in § 2 , and the equality criterion in symmetric exclusion in § 3 . In § 4 we derive interface identities from an equality vector and give conditions for reconstructing one from interface data. We also show that a nonzero equality vector in a top Hoeffding space H k \mathcal{H}_k H k , with 3 ≤ k ≤ ⌊ n / 2 ⌋ 3\le k\le\lfloor n/2\rfloor 3 ≤ k ≤ ⌊ n /2 ⌋ , forces the nonterminal harmonic voltage to take at most two distinct values. We then classify the quadratic kernel in § 5 , and reduce higher-degree equality to it in § 6 . Finally, § 7 and § 8 transfer and reconstruct the kernels in all particle sectors, first for symmetric exclusion and then for the interchange process.
Interchange equality and two-row rigidity
Let λ ⊢ n \lambda\vdash n λ ⊢ n be a partition, let ℓ ( λ ) \ell(\lambda) ℓ ( λ ) denote the number of rows in its Young diagram, and let λ i \lambda_i λ i be the number of boxes in row i i i . Fix an G V \mathcal{G}_V G V -invariant inner product on S λ S^\lambda S λ , and write ρ λ \rho_\lambda ρ λ for the corresponding orthogonal representation. Set
Q u v λ : = Id S λ − ρ λ ( τ u v ) , L G λ : = ∑ { u , v } ⊂ V c u v Q u v λ , K G , x y λ : = L G λ − c e f f ( x , y ) Q x y λ . (10) Q_{uv}^\lambda:= \operatorname{Id}_{S^\lambda}-\rho_\lambda(\tau_{uv}), \qquad\mathcal{L}_G^\lambda:= \sum_{\{u,v\}\subset V} c_{uv}Q_{uv}^\lambda, \qquad\mathcal{K}_{G,xy}^\lambda:= \mathcal{L}_G^\lambda-c_{\mathrm{eff}}(x,y)Q_{xy}^\lambda. \tag*{(10)} Q uv λ := Id S λ − ρ λ ( τ uv ) , L G λ := { u , v } ⊂ V ∑ c uv Q uv λ , K G , x y λ := L G λ − c eff ( x , y ) Q x y λ . (10)
where x ≠ y ∈ V x \ne y \in V x = y ∈ V . Since the regular representation contains every Specht module, the moving particle lemma for the interchange process, Proposition 1.1 , implies K G , x y λ ≥ 0 K^\lambda_{G,xy} \ge0 K G , x y λ ≥ 0 .
One-vertex reduction
Fix a nonterminal vertex z ∈ V ∖ { x , y } z \in V \setminus\{x,y\} z ∈ V ∖ { x , y } , put V z : = V ∖ { z } V_z := V \setminus\{z\} V z := V ∖ { z } , and write S V z \mathfrak{S}_{V_z} S V z for the subgroup fixing z z z . Also write c i : = c i z c_i := c_{iz} c i := c i z and C z : = ∑ i ∈ V z c i > 0 C_z := \sum_{i \in V_z} c_i > 0 C z := ∑ i ∈ V z c i > 0 . When the underlying graph matters, we write c e f f ( x , y ) c_{\mathrm{eff}}(x,y) c eff ( x , y ) for the effective conductance between x x x and y y y in a weighted graph H H H ; the definition still follows from (1) .
Upon reducing the graph G G G at the vertex z z z , we obtain the Schur-reduced graph G / z G/z G / z on V z V_z V z , which is connected and has conductances
c i j ( z ) : = c i j + c i c j C z , i ≠ j ∈ V z . (11) c_{ij}^{(z)} := c_{ij} + \frac{c_i c_j}{C_z}, \qquad i \ne j \in V_z. \tag*{(11)} c ij ( z ) := c ij + C z c i c j , i = j ∈ V z . (11)
We claim that this reduction preserves the effective conductance between the terminals x x x and y y y . For a given voltage function ϕ : V z → R \phi: V_z \to\mathbb{R} ϕ : V z → R , put
ϕ ˉ z : = 1 C z ∑ i ∈ V z c i ϕ ( i ) . \bar{\phi}_z := \frac{1}{C_z} \sum_{i \in V_z} c_i \phi(i). ϕ ˉ z := C z 1 i ∈ V z ∑ c i ϕ ( i ) .
If t t t denotes the voltage value at z z z , then the Dirichlet energy contributed by edges connected to z z z equals
∑ i ∈ V z c i ( t − ϕ ( i ) ) 2 = C z ( t − ϕ ˉ z ) 2 + 1 C z ∑ { i , j } ⊆ V z c i c j [ ϕ ( i ) − ϕ ( j ) ] 2 . \sum_{i \in V_z} c_i(t-\phi(i))^2 = C_z(t-\bar{\phi}_z)^2 + \frac{1}{C_z}\sum_{\{i,j\}\subseteq V_z} c_i c_j[\phi(i)-\phi(j)]^2. i ∈ V z ∑ c i ( t − ϕ ( i ) ) 2 = C z ( t − ϕ ˉ z ) 2 + C z 1 { i , j } ⊆ V z ∑ c i c j [ ϕ ( i ) − ϕ ( j ) ] 2 .
From the right-hand side expression, we see that this energy attains the minimum at t = ϕ ˉ z t=\bar{\phi}_z t = ϕ ˉ z , with value exactly the second term. Adding the edges already contained in V z V_z V z therefore replaces c i j c_{ij} c ij by the reduced conductance c i j ( z ) c_{ij}^{(z)} c ij ( z ) in (11) . Since z z z is not a terminal, the constraints at x x x and y y y are unchanged, and a second minimization over the values on V z V_z V z gives
c e f f G / z ( x , y ) = c e f f G ( x , y ) . (12) c_{\mathrm{eff}}^{G/z}(x,y)=c_{\mathrm{eff}}^G(x,y). \tag*{(12)} c eff G / z ( x , y ) = c eff G ( x , y ) . (12)
We now analyze two positive semidefinite operators that are relevant to the problem. The operator K G , x y λ K^\lambda_{G,xy} K G , x y λ introduced in (10) is referred to as the moving-particle residual . The operator created by eliminating z z z and the edges attached to z z z is the one-vertex octopus remainder
Δ z λ : = ∑ i ∈ V z c i Q i z λ − 1 C z ∑ { i , j } ⊆ V z c i c j Q i j λ . (13) \Delta^\lambda_z := \sum_{i \in V_z} c_i Q^\lambda_{iz} - \frac{1}{C_z}\sum_{\{i,j\}\subseteq V_z} c_i c_j Q^\lambda_{ij}. \tag*{(13)} Δ z λ := i ∈ V z ∑ c i Q i z λ − C z 1 { i , j } ⊆ V z ∑ c i c j Q ij λ . (13)
To see how the two operators fit together, write the residual on G G G as
K G , x y λ = ∑ { i , j } ⊆ V z c i j Q i j λ + ∑ i ∈ V z c i Q i z λ − c e f f G ( x , y ) Q x y λ . (14) K^\lambda_{G,xy} = \sum_{\{i,j\}\subseteq V_z} c_{ij}Q^\lambda_{ij} + \sum_{i \in V_z} c_i Q^\lambda_{iz} - c_{\mathrm{eff}}^G(x,y)Q^\lambda_{xy}. \tag*{(14)} K G , x y λ = { i , j } ⊆ V z ∑ c ij Q ij λ + i ∈ V z ∑ c i Q i z λ − c eff G ( x , y ) Q x y λ . (14)
On the restricted S V z \mathfrak{S}_{V_z} S V z -representation S λ ↓ S V z S^\lambda\downarrow_{\mathfrak{S}_{V_z}} S λ ↓ S V z , define the reduced residual by
K G / z , x y λ ↓ V z : = ∑ { i , j } ⊆ V z ( c i j + c i c j C z ) Q i j λ − c e f f G / z ( x , y ) Q x y λ . (15) K^{\lambda\downarrow V_z}_{G/z,xy} := \sum_{\{i,j\}\subseteq V_z}\left(c_{ij}+\frac{c_i c_j}{C_z}\right)Q^\lambda_{ij} - c_{\mathrm{eff}}^{G/z}(x,y)Q^\lambda_{xy}. \tag*{(15)} K G / z , x y λ ↓ V z := { i , j } ⊆ V z ∑ ( c ij + C z c i c j ) Q ij λ − c eff G / z ( x , y ) Q x y λ . (15)
Subtracting (15) from (14) and using (12) leaves exactly (13) . Hence
K G , x y λ = Δ z λ + K G / z , x y λ ↓ V z . (16) K^\lambda_{G,xy} = \Delta^\lambda_z + K^{\lambda\downarrow V_z}_{G/z,xy}. \tag*{(16)} K G , x y λ = Δ z λ + K G / z , x y λ ↓ V z . (16)
According to the branching rule, cf. [9 §2.8] , the restriction of the Specht module S λ S^\lambda S λ to the subgroup S V z \mathfrak{S}_{V_z} S V z decomposes multiplicity-free as
S λ ↓ S V z ≅ ⨁ μ = λ − □ S μ , (17) S^\lambda\downarrow_{\mathfrak{S}_{V_z}} \cong\bigoplus_{\mu=\lambda-\square} S^\mu, \tag*{(17)} S λ ↓ S V z ≅ μ = λ − □ ⨁ S μ , (17)
where the sum runs over the removable boxes of λ \lambda λ .
Lemma 2.1 (Positivity inputs for one-vertex reduction). For every partition λ ⊢ n \lambda\vdash n λ ⊢ n ,
Δ z λ ≥ 0 and K G / z , x y λ ↓ V z ≥ 0 , \Delta^\lambda_z \ge0 \quad\text{and}\quad K^{\lambda\downarrow V_z}_{G/z,xy} \ge0, Δ z λ ≥ 0 and K G / z , x y λ ↓ V z ≥ 0 , where the first inequality acts on S λ S^\lambda S λ , and the second on the restricted S V z \mathfrak{S}_{V_z} S V z -representation S λ ↓ S V z S^\lambda\downarrow_{\mathfrak{S}_{V_z}} S λ ↓ S V z .
Proof. The first inequality is the octopus inequality of Caputo, Liggett, and Richthammer [3 Theorem 2.3] restricted to the representation S λ S^\lambda S λ . For the second inequality, apply Proposition 1.1 to the connected Schur-reduced graph G / z G/z G / z . By the branching decomposition (17) , the restricted representation S λ ↓ S V z S^\lambda\mathord{\downarrow}_{\mathfrak{S}_{V_z}} S λ ↓ S V z is the direct sum of the irreducible summands S μ S^\mu S μ obtained by removing one box from λ \lambda λ . The resulting operator inequality is nonnegative on each such summand, and hence on their direct sum. □
Let us make a simple but crucial observation. If ℓ ( λ ) ≥ 3 \ell(\lambda) \ge3 ℓ ( λ ) ≥ 3 , then every branch in (17) still has at least 3 rows except in exactly one scenario: λ = ( a , b , 1 ) \lambda=(a,b,1) λ = ( a , b , 1 ) with a ≥ b ≥ 1 a\ge b\ge1 a ≥ b ≥ 1 , and the box in row 3 is removed, producing μ = ( a , b ) \mu=(a,b) μ = ( a , b ) . We call this the exceptional branch .
To prepare for the next lemma, recall that if P P P is the orthogonal projection onto a branching summand, then P Δ z λ P P\Delta^\lambda_zP P Δ z λ P is the compression of Δ z λ \Delta^\lambda_z Δ z λ to that summand; equivalently, it is the operator governing the quadratic form of Δ z λ \Delta^\lambda_z Δ z λ on vectors in the range of P P P . We also use the standard Jucys–Murphy content rule for branching (see Murphy [8 ] ). In a Young diagram, the content of a box in row r r r and column c c c is ct ( r , c ) = c − r \operatorname{ct}(r,c)=c-r ct ( r , c ) = c − r . If a branch S μ ⊂ S λ ↓ S V z S^\mu\subset S^\lambda\mathord{\downarrow}_{\mathfrak{S}_{V_z}} S μ ⊂ S λ ↓ S V z is obtained by removing the box λ ∖ μ \lambda\setminus\mu λ ∖ μ , and P μ P_\mu P μ is the orthogonal projection onto that branch, then the Jucys–Murphy element ∑ i ∈ V z ρ λ ( τ i z ) \sum_{i\in V_z}\rho^\lambda(\tau_{iz}) ∑ i ∈ V z ρ λ ( τ i z ) acts as a scalar on P μ P_\mu P μ according to
( ∑ i ∈ V z ρ λ ( τ i z ) ) P μ = ct ( λ ∖ μ ) P μ . (18) \left(\sum_{i\in V_z}\rho^\lambda(\tau_{iz})\right)P_\mu=\operatorname{ct}(\lambda\setminus\mu)P_\mu. \tag*{(18)} ( i ∈ V z ∑ ρ λ ( τ i z ) ) P μ = ct ( λ ∖ μ ) P μ . (18)
The sum in (18) is the difference between the transposition class sums for S V \mathfrak{S}_V S V and S V z \mathfrak{S}_{V_z} S V z , and these act on S λ S^\lambda S λ and S μ S^\mu S μ by the respective sums of box contents.
For the said exceptional branch, fix λ = ( a , b , 1 ) \lambda=(a,b,1) λ = ( a , b , 1 ) with a ≥ b ≥ 1 a\ge b\ge1 a ≥ b ≥ 1 , let B z ≅ S ( a , b ) B_z\cong S^{(a,b)} B z ≅ S ( a , b ) be the branch obtained by removing the third-row box, and let P P P be the orthogonal projection onto B z B_z B z . In the next lemma, we write Q u v : = Q u v ( a , b , 1 ) Q_{uv}:=Q^{(a,b,1)}_{uv} Q uv := Q uv ( a , b , 1 ) ; restrictions of these operators to B z B_z B z are indicated explicitly.
Lemma 2.2 (Exceptional branch compression). With the notation above, the following hold:
(i) For every i ∈ V z i\in V_z i ∈ V z ,
( P Q i z P ) ∣ B z = Id B z + 1 b ( a + 1 ) ∑ j ∈ V z ∖ { i } Q i j ∣ B z . (PQ_{iz}P)\big|_{B_z}=\operatorname{Id}_{B_z}+\frac{1}{b(a+1)}\sum_{j\in V_z\setminus\{i\}}Q_{ij}\big|_{B_z}. ( P Q i z P ) B z = Id B z + b ( a + 1 ) 1 j ∈ V z ∖ { i } ∑ Q ij B z . (ii) The octopus remainder satisfies
P Δ z ( a , b , 1 ) P ≥ ∑ i ∈ V z c i 2 C z P , P\Delta^{(a,b,1)}_zP\ge\frac{\sum_{i\in V_z}c_i^2}{C_z}P, P Δ z ( a , b , 1 ) P ≥ C z ∑ i ∈ V z c i 2 P , and hence is strictly positive on B z B_z B z .
Proof. Write ρ : = ρ ( a , b , 1 ) \rho:=\rho^{(a,b,1)} ρ := ρ ( a , b , 1 ) and regard all compressed operators as acting on B z B_z B z . The removed box is ( 3 , 1 ) (3,1) ( 3 , 1 ) , whose content is − 2 -2 − 2 , so (18) gives
( ∑ j ∈ V z ρ ( τ j z ) ) ∣ B z = − 2 Id B z . \left(\sum_{j\in V_z}\rho(\tau_{jz})\right)\bigg|_{B_z}=-2\operatorname{Id}_{B_z}. j ∈ V z ∑ ρ ( τ j z ) B z = − 2 Id B z .
Fix i ∈ V z i\in V_z i ∈ V z . The group algebra identity
τ i z ∑ j ∈ V z τ j z = 1 + ( ∑ j ∈ V z ∖ { i } τ i j ) τ i z \tau_{iz}\sum_{j\in V_z}\tau_{jz}=1+\left(\sum_{j\in V_z\setminus\{i\}}\tau_{ij}\right)\tau_{iz} τ i z j ∈ V z ∑ τ j z = 1 + j ∈ V z ∖ { i } ∑ τ ij τ i z
may be compressed to B z B_z B z as follows. The projection P P P commutes with every ρ ( τ i j ) \rho(\tau_{ij}) ρ ( τ ij ) , i , j ∈ V z i,j\in V_z i , j ∈ V z , since B z B_z B z is an invariant summand of the orthogonal subgroup representation. Also, (18) gives ( ∑ j ∈ V z ρ ( τ j z ) ) P = − 2 P \left(\sum_{j\in V_z}\rho(\tau_{jz})\right)P=-2P ( ∑ j ∈ V z ρ ( τ j z ) ) P = − 2 P . Multiplying by P P P on both sides gives
( 2 Id B z + ∑ j ∈ V z ∖ { i } ρ ( τ i j ) ∣ B z ) ( P ρ ( τ i z ) P ) ∣ B z = − Id B z . \left(2\operatorname{Id}_{B_z}+\sum_{j\in V_z\setminus\{i\}}\rho(\tau_{ij})\big|_{B_z}\right)(P\rho(\tau_{iz})P)\big|_{B_z}=-\operatorname{Id}_{B_z}. 2 Id B z + j ∈ V z ∖ { i } ∑ ρ ( τ ij ) B z ( P ρ ( τ i z ) P ) B z = − Id B z .
After relabeling i i i as the last letter of V z V_z V z , the sum over j j j is the Jucys–Murphy element for restricting S ( a , b ) S^{(a,b)} S ( a , b ) to S V z ∖ { i } \mathfrak{S}_{V_z\setminus\{i\}} S V z ∖ { i } . Its possible eigenvalues are the contents of the removable boxes of ( a , b ) (a,b) ( a , b ) , hence lie in { a − 1 , b − 2 } \{a-1,b-2\} { a − 1 , b − 2 } . For either such eigenvalue t t t , ( 2 + t ) − 1 = a + b − 1 − t b ( a + 1 ) (2+t)^{-1}=\frac{a+b-1-t}{b(a+1)} ( 2 + t ) − 1 = b ( a + 1 ) a + b − 1 − t . Spectral calculus therefore gives
( 2 Id B z + ∑ j ∈ V z ∖ { i } ρ ( τ i j ) ∣ B z ) − 1 = 1 b ( a + 1 ) ∑ j ∈ V z ∖ { i } Q i j ∣ B z . \left(2\operatorname{Id}_{B_z}+\sum_{j\in V_z\setminus\{i\}}\rho(\tau_{ij})\big|_{B_z}\right)^{-1}=\frac{1}{b(a+1)}\sum_{j\in V_z\setminus\{i\}}Q_{ij}\big|_{B_z}. 2 Id B z + j ∈ V z ∖ { i } ∑ ρ ( τ ij ) B z − 1 = b ( a + 1 ) 1 j ∈ V z ∖ { i } ∑ Q ij B z .
which proves item (i).
For item (ii), substitute item (i) into (13) . This gives
( P Δ z P ) ∣ B z = C z Id B z + 1 b ( a + 1 ) ∑ i ∈ V z c i ∑ j ∈ V z ∖ { i } Q i j ∣ B z − 1 C z ∑ { i , j } ⊆ V z c i c j Q i j ∣ B z . (P\Delta_zP)\big|_{B_z}=C_z\operatorname{Id}_{B_z}+\frac{1}{b(a+1)}\sum_{i\in V_z}c_i\sum_{j\in V_z\setminus\{i\}}Q_{ij}\big|_{B_z}-\frac{1}{C_z}\sum_{\{i,j\}\subseteq V_z}c_ic_jQ_{ij}\big|_{B_z}. ( P Δ z P ) B z = C z Id B z + b ( a + 1 ) 1 i ∈ V z ∑ c i j ∈ V z ∖ { i } ∑ Q ij B z − C z 1 { i , j } ⊆ V z ∑ c i c j Q ij B z .
The double sum is positive semidefinite, and each transposition is a self-adjoint involution, so 0 ≤ Q i j ∣ B z ≤ 2 Id B z 0\leq Q_{ij}\big|_{B_z}\leq2\operatorname{Id}_{B_z} 0 ≤ Q ij B z ≤ 2 Id B z . Hence
( P Δ z P ) ∣ B z ≥ ( C z − 2 C z ∑ { i , j } ⊆ V z c i c j ) Id B z = ∑ i ∈ V z c i 2 C z Id B z , (P\Delta_zP)\big|_{B_z}\geq\left(C_z-\frac{2}{C_z}\sum_{\{i,j\}\subseteq V_z}c_ic_j\right)\operatorname{Id}_{B_z}=\frac{\sum_{i\in V_z}c_i^2}{C_z}\operatorname{Id}_{B_z}, ( P Δ z P ) B z ≥ C z − C z 2 { i , j } ⊆ V z ∑ c i c j Id B z = C z ∑ i ∈ V z c i 2 Id B z ,
using C z 2 = ∑ i c i 2 + 2 ∑ { i , j } ⊆ V z c i c j C_z^2=\sum_i c_i^2+2\sum_{\{i,j\}\subseteq V_z}c_ic_j C z 2 = ∑ i c i 2 + 2 ∑ { i , j } ⊆ V z c i c j . This proves item (ii).
No equality in representations with three or more rows
The next result says that equality in the moving particle lemma can occur only in irreducibles with at most two rows.
Theorem 2.3 (Two-row rigidity for interchange equality). Let G = ( V , c ) G=(V,c) G = ( V , c ) be a finite connected weighted graph, let x ≠ y ∈ V x\ne y\in V x = y ∈ V be terminals, and let λ ⊢ n = ∣ V ∣ \lambda\vdash n=|V| λ ⊢ n = ∣ V ∣ . If ℓ ( λ ) ≥ 3 \ell(\lambda)\geq3 ℓ ( λ ) ≥ 3 , then ker K G , x y λ = { 0 } \ker K^\lambda_{G,xy}=\{0\} ker K G , x y λ = { 0 } .
Proof. We argue by induction on n n n . The assertion is vacuous for n ≤ 2 n\leq2 n ≤ 2 . Assume it is known on every graph with n − 1 n-1 n − 1 vertices, and let ℓ ( λ ) ≥ 3 \ell(\lambda)\geq3 ℓ ( λ ) ≥ 3 . Choose z ∉ { x , y } z\notin\{x,y\} z ∈ / { x , y } and suppose that 0 ≠ f ∈ ker K G , x y λ 0\ne f\in\ker K^\lambda_{G,xy} 0 = f ∈ ker K G , x y λ . By (16) and Lemma 2.1 ,
Δ z λ f = 0 and K G / z , x y λ ↓ V z f = 0. (19) \Delta^\lambda_z f=0\qquad\text{and}\qquad K^{\lambda\downarrow V_z}_{G/z,xy}f=0. \tag*{(19)} Δ z λ f = 0 and K G / z , x y λ ↓ V z f = 0. (19)
Decompose f f f according to the branching rule (17) . The second operator in (2.10) belongs to the group algebra of S V z S_{V_z} S V z , so it preserves every branch; in particular on the branch S μ S^\mu S μ it is K G / z , x y μ K^\mu_{G/z,xy} K G / z , x y μ . By the induction hypothesis, its kernel is trivial whenever ℓ ( μ ) ≥ 3 \ell(\mu)\geq3 ℓ ( μ ) ≥ 3 .
If no removable box of λ \lambda λ produces a two-row partition, every branch component of f f f is therefore zero, a contradiction. The only remaining possibility is λ = ( a , b , 1 ) \lambda=(a,b,1) λ = ( a , b , 1 ) , and then the only two-row branch is the branch B z ≅ S ( a , b ) B_z\cong S^{(a,b)} B z ≅ S ( a , b ) of Lemma 2.2. Hence f ∈ B z f\in B_z f ∈ B z , so P f = f Pf=f P f = f . The first identity in (19) and Lemma 2.2(ii) give
0 = ⟨ f , Δ z λ f ⟩ = ⟨ f , P Δ z λ P f ⟩ ≥ ∑ i ∈ V z c i 2 C z ∥ f ∥ 2 > 0 , 0=\langle f,\Delta^\lambda_zf\rangle=\langle f,P\Delta^\lambda_zPf\rangle\geq\frac{\sum_{i\in V_z}c_i^2}{C_z}\lVert f\rVert^2>0, 0 = ⟨ f , Δ z λ f ⟩ = ⟨ f , P Δ z λ P f ⟩ ≥ C z ∑ i ∈ V z c i 2 ∥ f ∥ 2 > 0 ,
a contradiction. This completes the induction. □
Remark 2.4. The proof of Theorem 2.3 shares some representation theoretic ingredients with the proof strategy in [2 ] . Both works track the equality of operators through a one-vertex reduction, and use the branching rule to control the irreducible components that survive restriction to one fewer vertex. But the objects of study differ. In [2 ] the goal is to identify the 2nd eigenspace of L G I P L_G^{\mathrm{IP}} L G IP . In this work, we fix the terminals x , y x,y x , y , and study the kernel of the terminal-dependent operator K G , x y λ K^\lambda_{G,xy} K G , x y λ .
Equality criterion for symmetric exclusion
Having ruled out partitions with three or more rows, we now analyze the remaining two-row representations through symmetric exclusion in an arbitrary r r r -particle sector.
Retain the notation of § 1 . Since each τ u v \tau_{uv} τ uv is an orthogonal involution, the quadratic form of (6) is
⟨ f , L G ( r ) f ⟩ r = ∑ { u , v } c u v ⟨ f , ( I − τ u v ) f ⟩ r , f ∈ R Ω r . (20) \langle f,L_G^{(r)}f\rangle_r=\sum_{\{u,v\}}c_{uv}\langle f,(I-\tau_{uv})f\rangle_r,\qquad f\in\mathbb{R}^{\Omega_r}. \tag*{(20)} ⟨ f , L G ( r ) f ⟩ r = { u , v } ∑ c uv ⟨ f , ( I − τ uv ) f ⟩ r , f ∈ R Ω r . (20)
Recall from (2) that the minimizing voltage p p p is harmonic at every nonterminal vertex. In what follows we will often use the concatenation notation: if u ∉ T u\notin T u ∈ / T , then u T uT u T means T ∪ { u } T\cup\{u\} T ∪ { u } , and similarly for u v T uvT uv T .
Transposition metric and the equality criterion
Throughout this subsection 1 ≤ r ≤ n − 1 1 \le r \le n-1 1 ≤ r ≤ n − 1 ; the sectors r = 0 , n r=0,n r = 0 , n consist only of constants. The key geometric input is that transposition differences of a fixed observable f ∈ R Ω r f \in\mathbb{R}^{\Omega_r} f ∈ R Ω r define a pseudometric on the vertex set V V V .
Definition 3.1 (Transposition distance). For f ∈ R Ω r f \in\mathbb{R}^{\Omega_r} f ∈ R Ω r and distinct u , v ∈ V u,v \in V u , v ∈ V , define
δ f ( u , v ) 2 : = ⟨ f , ( I − τ u v ) f ⟩ r = 1 2 ∥ f − τ u v f ∥ r 2 . (21) \delta_f(u,v)^2 := \langle f,(I-\tau_{uv})f\rangle_r = \frac{1}{2}\lVert f-\tau_{uv}f\rVert_r^2. \tag*{(21)} δ f ( u , v ) 2 := ⟨ f , ( I − τ uv ) f ⟩ r = 2 1 ∥ f − τ uv f ∥ r 2 . (21)
Set δ f ( u , u ) : = 0 \delta_f(u,u):=0 δ f ( u , u ) := 0 for every u ∈ V u \in V u ∈ V . For distinct u , v ∈ V u,v \in V u , v ∈ V , the same quantity has the coordinate representation
δ f ( u , v ) 2 = ( n r ) − 1 ∑ T ∈ ( V ∖ { u , v } r − 1 ) [ f ( u T ) − f ( v T ) ] 2 . (22) \delta_f(u,v)^2 = \binom{n}{r}^{-1}\sum_{T\in\binom{V\setminus\{u,v\}}{r-1}}[f(uT)-f(vT)]^2. \tag*{(22)} δ f ( u , v ) 2 = ( r n ) − 1 T ∈ ( r − 1 V ∖ { u , v } ) ∑ [ f ( u T ) − f ( v T ) ] 2 . (22)
We write
d f u v : = ( f ( u T ) − f ( v T ) ) T ∈ ( V ∖ { u , v } r − 1 ) \mathbf{d}_f^{uv}:=(f(uT)-f(vT))_{T\in\binom{V\setminus\{u,v\}}{r-1}} d f uv := ( f ( u T ) − f ( v T ) ) T ∈ ( r − 1 V ∖ { u , v } )
for this coordinate difference vector. For distinct u , v , w ∈ V u,v,w\in V u , v , w ∈ V , define two further coordinate vectors indexed by the same sets T T T by
( a f , w u v ( T ) , b f , w u v ( T ) ) : = { ( f ( u T ) − f ( w T ) , f ( w T ) − f ( v T ) ) , w ∉ T , ( f ( u v T ′ ) − f ( v w T ′ ) , f ( u w T ′ ) − f ( u v T ′ ) ) , T = T ′ ⊔ { w } , (23) (a_{f,w}^{uv}(T),b_{f,w}^{uv}(T)) :=
\begin{cases}
(f(uT)-f(wT),f(wT)-f(vT)), & w\notin T,\\
(f(uvT')-f(vwT'),f(uwT')-f(uvT')), & T=T'\sqcup\{w\},
\end{cases} \tag*{(23)} ( a f , w uv ( T ) , b f , w uv ( T )) := { ( f ( u T ) − f ( w T ) , f ( w T ) − f ( v T )) , ( f ( uv T ′ ) − f ( v w T ′ ) , f ( u w T ′ ) − f ( uv T ′ )) , w ∈ / T , T = T ′ ⊔ { w } , (23)
and write a f , w u v : = ( a f , w u v ( T ) ) T ∈ ( V ∖ { u , v } r − 1 ) \mathbf{a}_{f,w}^{uv}:=(a_{f,w}^{uv}(T))_{T\in\binom{V\setminus\{u,v\}}{r-1}} a f , w uv := ( a f , w uv ( T ) ) T ∈ ( r − 1 V ∖ { u , v } ) and b f , w u v : = ( b f , w u v ( T ) ) T ∈ ( V ∖ { u , v } r − 1 ) \mathbf{b}_{f,w}^{uv}:=(b_{f,w}^{uv}(T))_{T\in\binom{V\setminus\{u,v\}}{r-1}} b f , w uv := ( b f , w uv ( T ) ) T ∈ ( r − 1 V ∖ { u , v } ) .
Lemma 3.2 (Transposition pseudometric and equality in the triangle inequality). For every f ∈ R Ω r f\in\mathbb{R}^{\Omega_r} f ∈ R Ω r , the following hold for distinct u , v , w ∈ V u,v,w\in V u , v , w ∈ V :
(i) The coordinate vectors split as d f u v = a f , w u v + b f , w u v \mathbf{d}_f^{uv}=\mathbf{a}_{f,w}^{uv}+\mathbf{b}_{f,w}^{uv} d f uv = a f , w uv + b f , w uv , and their Euclidean norms are
∥ d f u v ∥ 2 = ( n r ) 1 / 2 δ f ( u , v ) , ∥ a f , w u v ∥ 2 = ( n r ) 1 / 2 δ f ( u , w ) , ∥ b f , w u v ∥ 2 = ( n r ) 1 / 2 δ f ( w , v ) . \lVert\mathbf{d}_f^{uv}\rVert_2=\binom{n}{r}^{1/2}\delta_f(u,v),\qquad
\lVert\mathbf{a}_{f,w}^{uv}\rVert_2=\binom{n}{r}^{1/2}\delta_f(u,w),\qquad
\lVert\mathbf{b}_{f,w}^{uv}\rVert_2=\binom{n}{r}^{1/2}\delta_f(w,v). ∥ d f uv ∥ 2 = ( r n ) 1/2 δ f ( u , v ) , ∥ a f , w uv ∥ 2 = ( r n ) 1/2 δ f ( u , w ) , ∥ b f , w uv ∥ 2 = ( r n ) 1/2 δ f ( w , v ) . (ii) The triangle inequality δ f ( u , v ) ≤ δ f ( u , w ) + δ f ( w , v ) \delta_f(u,v)\le\delta_f(u,w)+\delta_f(w,v) δ f ( u , v ) ≤ δ f ( u , w ) + δ f ( w , v ) *holds. Hence δ f \delta_f δ f is a pseudometric on V V V .
(iii) If equality holds in item (ii) and δ f ( u , v ) > 0 \delta_f(u,v)>0 δ f ( u , v ) > 0 , then
a f , w u v = δ f ( u , w ) δ f ( u , v ) d f u v , b f , w u v = δ f ( w , v ) δ f ( u , v ) d f u v . \mathbf{a}_{f,w}^{uv}=\frac{\delta_f(u,w)}{\delta_f(u,v)}\mathbf{d}_f^{uv},\qquad
\mathbf{b}_{f,w}^{uv}=\frac{\delta_f(w,v)}{\delta_f(u,v)}\mathbf{d}_f^{uv}. a f , w uv = δ f ( u , v ) δ f ( u , w ) d f uv , b f , w uv = δ f ( u , v ) δ f ( w , v ) d f uv .
Proof. Item (i): The vector identity holds coordinatewise. When w ∉ T w\notin T w ∈ / T , a f , w u v ( T ) a_{f,w}^{uv}(T) a f , w uv ( T ) is a ( u , w ) (u,w) ( u , w ) -difference and b f , w u v ( T ) b_{f,w}^{uv}(T) b f , w uv ( T ) is a ( w , v ) (w,v) ( w , v ) -difference. When T = T ′ ⊔ { w } T=T'\sqcup\{w\} T = T ′ ⊔ { w } , the same is true after reindexing by v T ′ vT' v T ′ and u T ′ uT' u T ′ , respectively. The norm identities then follow from (3.3).
Item (ii): Symmetry follows from (3.2), and δ f ( u , u ) = 0 \delta_f(u,u)=0 δ f ( u , u ) = 0 by definition. Minkowski’s inequality applied to item (i) gives the triangle inequality.
Item (iii): Equality in item (ii) is equality in the Euclidean triangle inequality from item (i). Hence a f , w u v \mathbf{a}_{f,w}^{uv} a f , w uv and b f , w u v \mathbf{b}_{f,w}^{uv} b f , w uv are nonnegative scalar multiples of d f u v \mathbf{d}_f^{uv} d f uv . Comparing their norms in item (i) gives the stated factors. □
Proposition 3.3 (Moving particle lemma and equality criterion). For every 1 ≤ r ≤ n − 1 1\le r\le n-1 1 ≤ r ≤ n − 1 , every f ∈ R Ω r f\in\mathbb{R}^{\Omega_r} f ∈ R Ω r , and every x ≠ y x\ne y x = y ,
c e f f ( x , y ) δ f ( x , y ) 2 ≤ ⟨ f , L G ( r ) f ⟩ r . (24) c_{\mathrm{eff}}(x,y)\delta_f(x,y)^2\le\langle f,L_G^{(r)}f\rangle_r. \tag*{(24)} c eff ( x , y ) δ f ( x , y ) 2 ≤ ⟨ f , L G ( r ) f ⟩ r . (24) If δ f ( x , y ) > 0 \delta_f(x,y)>0 δ f ( x , y ) > 0 , equality holds in (3.5) if and only if the function ϕ f ( v ) : = δ f ( x , v ) / δ f ( x , y ) \phi_f(v):=\delta_f(x,v)/\delta_f(x,y) ϕ f ( v ) := δ f ( x , v ) / δ f ( x , y ) is the harmonic x x x –y y y voltage and every edge { u , v } \{u,v\} { u , v } of positive conductance satisfies
δ f ( u , v ) = δ f ( x , y ) ∣ ϕ f ( u ) − ϕ f ( v ) ∣ . (25) \delta_f(u,v)=\delta_f(x,y)|\phi_f(u)-\phi_f(v)|. \tag*{(25)} δ f ( u , v ) = δ f ( x , y ) ∣ ϕ f ( u ) − ϕ f ( v ) ∣. (25) If δ f ( x , y ) = 0 \delta_f(x,y)=0 δ f ( x , y ) = 0 , equality holds if and only if $f is constant on Ω r \Omega_r Ω r .
Proof. Assume first that δ f ( x , y ) > 0 \delta_f(x,y)>0 δ f ( x , y ) > 0 . The reverse triangle inequality for the pseudometric gives ∣ ϕ f ( u ) − ϕ f ( v ) ∣ ≤ δ f ( u , v ) / δ f ( x , y ) |\phi_f(u)-\phi_f(v)|\le\delta_f(u,v)/\delta_f(x,y) ∣ ϕ f ( u ) − ϕ f ( v ) ∣ ≤ δ f ( u , v ) / δ f ( x , y ) . Since ϕ f ( x ) = 0 \phi_f(x)=0 ϕ f ( x ) = 0 and ϕ f ( y ) = 1 \phi_f(y)=1 ϕ f ( y ) = 1 , the scalar Dirichlet principle (1) yields
c e f f ( x , y ) ≤ ∑ { u , v } c u v [ ϕ f ( u ) − ϕ f ( v ) ] 2 ≤ δ f ( x , y ) − 2 ∑ { u , v } c u v δ f ( u , v ) 2 . (26) c_{\mathrm{eff}}(x,y)\le\sum_{\{u,v\}}c_{uv}[\phi_f(u)-\phi_f(v)]^2\le\delta_f(x,y)^{-2}\sum_{\{u,v\}}c_{uv}\delta_f(u,v)^2. \tag*{(26)} c eff ( x , y ) ≤ { u , v } ∑ c uv [ ϕ f ( u ) − ϕ f ( v ) ] 2 ≤ δ f ( x , y ) − 2 { u , v } ∑ c uv δ f ( u , v ) 2 . (26)
By (20) , the sum over { u , v } \{u,v\} { u , v } in the last display is ⟨ f , L G ( r ) f ⟩ r \langle f,\mathcal{L}^{(r)}_Gf\rangle_r ⟨ f , L G ( r ) f ⟩ r , which then proves (24) .
Equality in (24) holds exactly when both inequalities in (26) are equalities. To attain equality in the first inequality, ϕ f \phi_f ϕ f must be the harmonic voltage per (1) –(1.2). In the second inequality, every edge contribution is nonnegative, so equality is equivalent to (3.6)` on every edge of positive conductance.
Now assume δ f ( x , y ) = 0 \delta_f(x,y)=0 δ f ( x , y ) = 0 . Equality in (24) means ⟨ f , L G ( r ) f ⟩ r = 0 \langle f,\mathcal{L}^{(r)}_Gf\rangle_r=0 ⟨ f , L G ( r ) f ⟩ r = 0 . Hence τ u v f = f \tau_{uv}f=f τ uv f = f on every edge of positive conductance. The edge transpositions of a connected graph generate the full symmetric group on V V V , so f f f is constant on the r r r -particle sector. The converse is immediate. □
From now on it is convenient to encode equality in the moving particle lemma by the residual operator
K x y ( r ) : = L G ( r ) − c e f f ( x , y ) ( I − τ x y ) . (27) \mathcal{K}^{(r)}_{xy}:=\mathcal{L}^{(r)}_G-c_{\mathrm{eff}}(x,y)(I-\tau_{xy}). \tag*{(27)} K x y ( r ) := L G ( r ) − c eff ( x , y ) ( I − τ x y ) . (27)
Corollary 3.4 (Residual kernel and equality vectors). For every r r r , K x y ( r ) ≥ 0 \mathcal{K}^{(r)}_{xy}\ge0 K x y ( r ) ≥ 0 . Also , for f ∈ R Ω r f\in\mathbb{R}^{\Omega_r} f ∈ R Ω r we have
K x y ( r ) f = 0 ⟺ ⟨ f , K x y ( r ) f ⟩ r = 0 ⟺ c e f f ( x , y ) δ f ( x , y ) 2 = ⟨ f , L G ( r ) f ⟩ r . \mathcal{K}^{(r)}_{xy}f=0\quad\Longleftrightarrow\quad\langle f,\mathcal{K}^{(r)}_{xy}f\rangle_r=0\quad\Longleftrightarrow\quad c_{\mathrm{eff}}(x,y)\delta_f(x,y)^2=\langle f,\mathcal{L}^{(r)}_Gf\rangle_r. K x y ( r ) f = 0 ⟺ ⟨ f , K x y ( r ) f ⟩ r = 0 ⟺ c eff ( x , y ) δ f ( x , y ) 2 = ⟨ f , L G ( r ) f ⟩ r . If any of these conditions holds for a nonconstant f f f , then δ f ( x , y ) > 0 \delta_f(x,y)>0 δ f ( x , y ) > 0 .
Proof. By Proposition 1.1 , applied in the r r r -subset permutation representation, L G ( r ) ≥ c e f f ( x , y ) ( I − τ x y ) \mathcal{L}^{(r)}_G\ge c_{\mathrm{eff}}(x,y)(I-\tau_{xy}) L G ( r ) ≥ c eff ( x , y ) ( I − τ x y ) , so (27) gives K x y ( r ) ≥ 0 \mathcal{K}^{(r)}_{xy}\ge0 K x y ( r ) ≥ 0 . For a positive semidefinite self-adjoint operator, vanishing of the quadratic form is equivalent to kernel membership. Expanding the quadratic form of (27) gives the third condition. Finally, Proposition 3.3 shows that equality with δ f ( x , y ) = 0 \delta_f(x,y)=0 δ f ( x , y ) = 0 forces f f f to be constant. □
Terminal geometry of equality vectors
Fix a nonconstant equality vector f f f . Write u ∼ f v u\sim_f v u ∼ f v when δ f ( u , v ) = 0 \delta_f(u,v)=0 δ f ( u , v ) = 0 . Since δ f \delta_f δ f is a pseudometric, ∼ f \sim_f ∼ f is an equivalence relation on V V V ; its equivalence classes are the zero-distance classes of f f f . Contracting these classes gives a quotient graph whose vertices are the zero-distance classes and whose positive edges are induced by edges of positive conductance in G G G .
The next lemma turns the equality criterion into terminal geodesicity, and then invokes Lemma 3.2 (iii) to obtain the coordinate proportionality used in § 4 .
Lemma 3.5 (Every vertex lies on a terminal geodesic). Suppose f f f is a nonconstant equality vector. Then for every z ∈ V z\in V z ∈ V ,
δ f ( x , y ) = δ f ( x , z ) + δ f ( z , y ) . (28) \delta_f(x,y)=\delta_f(x,z)+\delta_f(z,y). \tag*{(28)} δ f ( x , y ) = δ f ( x , z ) + δ f ( z , y ) . (28) Let p v : = p ( v ) = ϕ f ( v ) p_v:=p(v)=\phi_f(v) p v := p ( v ) = ϕ f ( v ) , where ϕ f \phi_f ϕ f is the harmonic x x x –y y y voltage from Proposition 3.3 . Then for every $z\in V\setminus{x,y} we have
a f , z x y = p z d f x y and b f , z x y = ( 1 − p z ) d f x y , (29) \mathbf{a}^{xy}_{f,z}=p_z\mathbf{d}^{xy}_f\quad\text{and}\quad\mathbf{b}^{xy}_{f,z}=(1-p_z)\mathbf{d}^{xy}_f, \tag*{(29)} a f , z x y = p z d f x y and b f , z x y = ( 1 − p z ) d f x y , (29) where a f , z x y \mathbf{a}^{xy}_{f,z} a f , z x y and b f , z x y \mathbf{b}^{xy}_{f,z} b f , z x y are the coordinate vectors from (23) in Definition 3.1 .
Proof. Throughout the proof we use the shorthand L f : = δ f ( x , y ) L_f:=\delta_f(x,y) L f := δ f ( x , y ) . By Corollary 3.4, L f > 0 L_f>0 L f > 0 . For z = x z=x z = x or z = y z=y z = y , (28) is immediate, so fix z ∈ V ∖ { x , y } z\in V\setminus\{x,y\} z ∈ V ∖ { x , y } . Pass to the quotient by the zero-distance relation ∼ f \sim_f ∼ f ; the pseudometric δ f \delta_f δ f descends to a metric on the quotient. Since p v = δ f ( x , v ) / L f p_v=\delta_f(x,v)/L_f p v = δ f ( x , v ) / L f , the reverse triangle inequality gives ∣ p u − p v ∣ ≤ δ f ( u , v ) / L f |p_u-p_v|\le\delta_f(u,v)/L_f ∣ p u − p v ∣ ≤ δ f ( u , v ) / L f . Thus p p p is constant on each zero-distance class. Moreover, if distinct quotient classes U , V U,V U , V are joined by an edge induced from an edge of positive conductance in G G G , then δ f ( U , V ) = L f ∣ p ( U ) − p ( V ) ∣ \delta_f(U,V)=L_f|p(U)-p(V)| δ f ( U , V ) = L f ∣ p ( U ) − p ( V ) ∣ . Thus adjacent quotient classes have different voltages, and along any quotient path on which the voltage is monotone, the δ f \delta_f δ f -length is L f L_f L f times the total voltage change.
If the zero-distance class of z z z contains x x x , then δ f ( x , z ) = 0 \delta_f(x,z)=0 δ f ( x , z ) = 0 , and the triangle inequality gives δ f ( z , y ) = δ f ( x , y ) \delta_f(z,y)=\delta_f(x,y) δ f ( z , y ) = δ f ( x , y ) ; the case in which it contains y y y is symmetric. Thus (28) already holds in these cases. We may then assume that the class Q Q Q of z z z contains neither terminal. Choose a vertex of Q Q Q incident to an edge leaving Q Q Q , which exists because the quotient graph is connected. If p ( Q ) = 0 p(Q)=0 p ( Q ) = 0 , every term in the harmonicity equation (2) at that vertex coming from outside Q Q Q is nonpositive, and at least one is strictly negative, a contradiction. The case p ( Q ) = 1 p(Q)=1 p ( Q ) = 1 is analogous. Thus 0 < p ( Q ) < 1 0<p(Q)<1 0 < p ( Q ) < 1 . The same harmonicity argument shows that Q Q Q has both a lower-voltage and a higher-voltage neighboring class. Because the quotient is finite, and voltage strictly decreases or increases at every such step, a path obtained by following lower- or higher-voltage neighbors must terminate. No class without a terminal can be an endpoint: it has neighbors of both voltage signs. The maximum principle gives 0 ≤ p ≤ 1 0 \le p \le1 0 ≤ p ≤ 1 , so the only possible endpoints are respectively the class containing x x x (voltage 0) and the class containing y y y (voltage 1).
Let Q 0 , … , Q m Q_0,\ldots,Q_m Q 0 , … , Q m be such a decreasing-voltage path from the z z z -class to the x x x -class. Then
∑ i = 0 m − 1 δ f ( Q i , Q i + 1 ) = L f ∑ i = 0 m − 1 ( p ( Q i ) − p ( Q i + 1 ) ) = p z L f . \sum_{i=0}^{m-1}\delta_f(Q_i,Q_{i+1})=L_f\sum_{i=0}^{m-1}\bigl(p(Q_i)-p(Q_{i+1})\bigr)=p_zL_f. i = 0 ∑ m − 1 δ f ( Q i , Q i + 1 ) = L f i = 0 ∑ m − 1 ( p ( Q i ) − p ( Q i + 1 ) ) = p z L f .
Similarly, an increasing-voltage path from the z z z -class to the y y y -class has δ f \delta_f δ f -length ( 1 − p z ) L f (1-p_z)L_f ( 1 − p z ) L f . Hence
δ f ( x , z ) ≤ p z L f , δ f ( z , y ) ≤ ( 1 − p z ) L f . \delta_f(x,z)\le p_zL_f,\qquad\delta_f(z,y)\le(1-p_z)L_f. δ f ( x , z ) ≤ p z L f , δ f ( z , y ) ≤ ( 1 − p z ) L f .
Together with the triangle inequality,
L f = δ f ( x , y ) ≤ δ f ( x , z ) + δ f ( z , y ) ≤ p z L f + ( 1 − p z ) L f = L f . L_f=\delta_f(x,y)\le\delta_f(x,z)+\delta_f(z,y)\le p_zL_f+(1-p_z)L_f=L_f. L f = δ f ( x , y ) ≤ δ f ( x , z ) + δ f ( z , y ) ≤ p z L f + ( 1 − p z ) L f = L f .
Equality therefore holds throughout. This proves (28) , and Lemma 3.2 (iii) applied to the triple ( u , w , v ) = ( x , z , y ) (u,w,v)=(x,z,y) ( u , w , v ) = ( x , z , y ) gives (29) . □
Interface identities and voltage rigidity
We introduce the down map on an arbitrary ground set. Given a finite E ⊆ V E\subseteq V E ⊆ V and 1 ≤ r ≤ ∣ E ∣ 1\le r\le|E| 1 ≤ r ≤ ∣ E ∣ , define
D r E : R ( E r ) ⟶ R ( E r − 1 ) , ( D r E g ) ( T ) : = ∑ z ∈ E ∖ T g ( T ∪ { z } ) . D_r^E:\mathbb{R}^{\binom{E}{r}}\longrightarrow\mathbb{R}^{\binom{E}{r-1}},\qquad(D_r^E g)(T):=\sum_{z\in E\setminus T}g(T\cup\{z\}). D r E : R ( r E ) ⟶ R ( r − 1 E ) , ( D r E g ) ( T ) := z ∈ E ∖ T ∑ g ( T ∪ { z }) .
When E = V E=V E = V , write D r : = D r V D_r:=D_r^V D r := D r V for short. Set
H 0 ( E ) : = R , H r ( E ) : = ker D r E , 1 ≤ r ≤ ⌊ ∣ E ∣ 2 ⌋ , \mathcal{H}_0(E):=\mathbb{R},\qquad\mathcal{H}_r(E):=\ker D_r^E,\qquad1\le r\le\left\lfloor\frac{|E|}{2}\right\rfloor, H 0 ( E ) := R , H r ( E ) := ker D r E , 1 ≤ r ≤ ⌊ 2 ∣ E ∣ ⌋ ,
and abbreviate H r : = H r ( V ) \mathcal{H}_r:=\mathcal{H}_r(V) H r := H r ( V ) . Thus g ∈ H r ( E ) g\in\mathcal{H}_r(E) g ∈ H r ( E ) if and only if D r E g = 0 D_r^E g=0 D r E g = 0 . The down map is equivariant under vertex permutations of E E E , so H r ( E ) \mathcal{H}_r(E) H r ( E ) is preserved by the full symmetric group S E S_E S E . In particular, the space H r \mathcal{H}_r H r is isomorphic to S ( n − r , r ) S^{(n-r,r)} S ( n − r , r ) as an S V S_V S V -representation, as in the Hoeffding–Specht correspondence of § 1 ; for background on this realization see [6 ] .
Interface identities and algebraic reconstruction
This subsection provides the algebraic basis for our main theorems. First, we derive in Lemma 4.2 identities for the terminal difference h h h and the both-terminal trace b b b of a nonzero equality vector in H k \mathcal{H}_k H k . Then, in the reverse direction, we prove in Lemma 4.4 that using compatible data ( p , h , b ) (p,h,b) ( p , h , b ) one may reconstruct a function in H k \mathcal{H}_k H k . This reconstructed function becomes an equality vector under the harmonic voltage and the remaining positive-edge conditions, as stated in Corollary 4.5 .
The six identities in Lemma 4.2 support several results to follow, such as the voltage rigidity result of § 4.1 , the degree lowering results in § 6 , and the classification of nonzero equality vectors in § 8 .
Assumption 4.1 (Higher-degree equality hypothesis). For the necessary interface identities below, the voltage-rigidity argument, and the degree-lowering argument in § 6 , assume
3 ≤ k ≤ ⌊ n 2 ⌋ , 0 ≠ f ∈ H k , κ x y ( k ) f = 0. 3\le k\le\left\lfloor\frac{n}{2}\right\rfloor,\qquad0\ne f\in\mathcal{H}_k,\qquad\kappa_{xy}^{(k)}f=0. 3 ≤ k ≤ ⌊ 2 n ⌋ , 0 = f ∈ H k , κ x y ( k ) f = 0. The function f f f is nonconstant, since no nonzero constant belongs to H k \mathcal{H}_k H k . By Proposition 3.3 and Corollary 3.4, δ f ( x , y ) > 0 \delta_f(x,y)>0 δ f ( x , y ) > 0 and ϕ f = p \phi_f=p ϕ f = p , where p p p is the unique harmonic x x x -y y y voltage of G G G (with p ( x ) = 0 p(x)=0 p ( x ) = 0 and p ( y ) = 1 p(y)=1 p ( y ) = 1 ). Set W : = V ∖ { x , y } W:=V\setminus\{x,y\} W := V ∖ { x , y } , N : = ∣ W ∣ = n − 2 N:=|W|=n-2 N := ∣ W ∣ = n − 2 , and p u : = p ( u ) p_u:=p(u) p u := p ( u ) for u ∈ W u\in W u ∈ W .
For any A ⊆ W A\subseteq W A ⊆ W , write S A : = ∑ w ∈ A p w S_A:=\sum_{w\in A}p_w S A := ∑ w ∈ A p w ; in particular, S W S_W S W is the total nonterminal voltage sum. For ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) and T ∈ ( W k − 2 ) T\in\binom{W}{k-2} T ∈ ( k − 2 W ) , define
(4.1) \qquad h ξ : = f ( x ξ ) − f ( y ξ ) , b T : = f ( x y T ) h_\xi:=f(x\xi)-f(y\xi),\qquad b_T:=f(xyT) h ξ := f ( x ξ ) − f ( y ξ ) , b T := f ( x y T ) .
Lemma 4.2 (Interpolation and interface identities). Under Assumption 4.1 , the interface functions h h h and b b b satisfy the following identities:
(i) (Down-map identities) D k − 1 W h = 0 D^{W}_{k-1}h=0 D k − 1 W h = 0 and D k − 2 W b = 0 D^{W}_{k-2}b=0 D k − 2 W b = 0 .
(ii) (Terminal interpolation formula) If T ∈ ( W k − 2 ) T\in\binom{W}{k-2} T ∈ ( k − 2 W ) and z ∈ W ∖ T z\in W\setminus T z ∈ W ∖ T , then f ( x z T ) = b T + ( 1 − p z ) h z T f(xzT)=b_T+(1-p_z)h_{zT} f ( x z T ) = b T + ( 1 − p z ) h z T and f ( y z T ) = b T − p z h z T f(yzT)=b_T-p_zh_{zT} f ( y z T ) = b T − p z h z T .
(iii) (Non-terminal interpolation formula) If ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) and z ∈ W ∖ ξ z\in W\setminus\xi z ∈ W ∖ ξ , then f ( z ξ ) = ( 1 − p z ) f ( x ξ ) + p z f ( y ξ ) f(z\xi)=(1-p_z)f(x\xi)+p_zf(y\xi) f ( z ξ ) = ( 1 − p z ) f ( x ξ ) + p z f ( y ξ ) .
(iv) (Symmetry) If R ∈ ( W k − 3 ) R\in\binom{W}{k-3} R ∈ ( k − 3 W ) and u , v ∈ W ∖ R u,v\in W\setminus R u , v ∈ W ∖ R are distinct, then b v R − b u R = ( p u − p v ) h u v R b_{vR}-b_{uR}=(p_u-p_v)h_{uvR} b v R − b u R = ( p u − p v ) h uv R .
(v) (Consistency) If T ∈ ( W k − 2 ) T\in\binom{W}{k-2} T ∈ ( k − 2 W ) and u , v ∈ W ∖ T u,v\in W\setminus T u , v ∈ W ∖ T are distinct, then ( 1 − p u − p v ) ( h u T − h v T ) = 0 (1-p_u-p_v)(h_{uT}-h_{vT})=0 ( 1 − p u − p v ) ( h u T − h v T ) = 0 .
(vi) (Master identity) Writing L : = N − k + 2 L:=N-k+2 L := N − k + 2 , for every T ∈ ( W k − 2 ) T\in\binom{W}{k-2} T ∈ ( k − 2 W ) and u ∈ W ∖ T u\in W\setminus T u ∈ W ∖ T one has
( L + 1 ) b T + ( L − S W − L p u + S T ) h u T = 0. (L+1)b_T+(L-S_W-Lp_u+S_T)h_{uT}=0. ( L + 1 ) b T + ( L − S W − L p u + S T ) h u T = 0.
Proof. Item (i): Let R ∈ ( W k − 2 ) R\in\binom{W}{k-2} R ∈ ( k − 2 W ) . Applying D k f = 0 D_kf=0 D k f = 0 to x R xR x R gives b R + ∑ z ∈ W ∖ R f ( x z R ) = 0 b_R+\sum_{z\in W\setminus R}f(xzR)=0 b R + ∑ z ∈ W ∖ R f ( x z R ) = 0 ; applying it to y R yR y R gives the same identity with x x x replaced by y y y . Subtraction proves D k − 1 W h = 0 D^{W}_{k-1}h=0 D k − 1 W h = 0 . Applying D k f = 0 D_kf=0 D k f = 0 to x y Q xyQ x y Q , with Q ∈ ( W k − 3 ) Q\in\binom{W}{k-3} Q ∈ ( k − 3 W ) , gives D k − 2 W b = 0 D^{W}_{k-2}b=0 D k − 2 W b = 0 .
Item (ii): Apply the proportionality condition (29) of Lemma 3.5 at the coordinate indexed by z T zT z T ; note that the a f , z x y a^{xy}_{f,z} a f , z x y -coordinate is b T − f ( y z T ) b_T-f(yzT) b T − f ( y z T ) , the b f , z x y b^{xy}_{f,z} b f , z x y -coordinate is f ( x z T ) − b T f(xzT)-b_T f ( x z T ) − b T , and the d f x y d^{xy}_f d f x y -coordinate is h z T h_{zT} h z T .
Item (iii): Apply the proportionality condition (29) once more, now to ξ \xi ξ .
Item (iv): Fix R ∈ ( W k − 3 ) R\in\binom{W}{k-3} R ∈ ( k − 3 W ) and distinct u , v ∈ W ∖ R u,v\in W\setminus R u , v ∈ W ∖ R . Apply item (ii) to f ( x u v R ) f(xuvR) f ( xuv R ) , first choosing z = u z=u z = u and T = v R T=vR T = v R , and then choosing z = v z=v z = v and T = u R T=uR T = u R . This gives
f ( x u v R ) = b v R + ( 1 − p u ) h u v R = b u R + ( 1 − p v ) h u v R . f(xuvR)=b_{vR}+(1-p_u)h_{uvR}=b_{uR}+(1-p_v)h_{uvR}. f ( xuv R ) = b v R + ( 1 − p u ) h uv R = b u R + ( 1 − p v ) h uv R .
Manipulating the last equality yields b v R − b u R = ( p u − p v ) h u v R b_{vR}-b_{uR}=(p_u-p_v)h_{uvR} b v R − b u R = ( p u − p v ) h uv R , as required.
Item (v): Fix T ∈ ( W k − 2 ) T\in\binom{W}{k-2} T ∈ ( k − 2 W ) and distinct u , v ∈ W ∖ T u,v\in W\setminus T u , v ∈ W ∖ T . Apply item (iii) to f ( u v T ) f(uvT) f ( uv T ) , taking z = u z=u z = u and ξ = v T \xi=vT ξ = v T . Substituting the two formulas from item (ii), we obtain
f ( u v T ) = ( 1 − p u ) f ( x v T ) + p u f ( y v T ) = ( 1 − p u ) [ b T + ( 1 − p v ) h v T ] + p u [ b T − p v h v T ] = b T + ( 1 − p u − p v ) h v T . \begin{aligned}
f(uvT)&=(1-p_u)f(xvT)+p_uf(yvT)\\
&=(1-p_u)\left[b_T+(1-p_v)h_{vT}\right]+p_u\left[b_T-p_vh_{vT}\right]\\
&=b_T+(1-p_u-p_v)h_{vT}.
\end{aligned} f ( uv T ) = ( 1 − p u ) f ( xv T ) + p u f ( y v T ) = ( 1 − p u ) [ b T + ( 1 − p v ) h v T ] + p u [ b T − p v h v T ] = b T + ( 1 − p u − p v ) h v T .
Interchanging u u u and v v v in the same calculation gives f ( u v T ) = b T + ( 1 − p u − p v ) h u T f(uvT)=b_T+(1-p_u-p_v)h_{uT} f ( uv T ) = b T + ( 1 − p u − p v ) h u T . Subtracting these two expressions gives ( 1 − p u − p v ) ( h u T − h v T ) = 0 (1-p_u-p_v)(h_{uT}-h_{vT})=0 ( 1 − p u − p v ) ( h u T − h v T ) = 0 .
Item (vi): Fix T ∈ ( W k − 2 ) T\in\binom{W}{k-2} T ∈ ( k − 2 W ) and u ∈ W ∖ T u\in W\setminus T u ∈ W ∖ T . The parameter L = N − k + 2 ≥ 2 L=N-k+2\ge2 L = N − k + 2 ≥ 2 is convenient because u T uT u T has k − 1 k-1 k − 1 elements, so ∣ W ∖ ( u T ) ∣ = N − k + 1 = L − 1 ≥ 1 |W\setminus(uT)|=N-k+1=L-1\ge1 ∣ W ∖ ( u T ) ∣ = N − k + 1 = L − 1 ≥ 1 . Thus D k f = 0 D_kf=0 D k f = 0 at u T uT u T consists of two terminal terms and L − 1 L-1 L − 1 nonterminal terms:
0 = f ( x u T ) + f ( y u T ) + ∑ z ∈ W ∖ ( u T ) f ( z u T ) . (30) 0=f(xuT)+f(yuT)+\sum_{z\in W\setminus(uT)}f(zuT). \tag*{(30)} 0 = f ( xu T ) + f ( y u T ) + z ∈ W ∖ ( u T ) ∑ f ( z u T ) . (30)
By item (ii), the first two terms sum to 2 b T + ( 1 − 2 p u ) h u T 2b_T+(1-2p_u)h_{uT} 2 b T + ( 1 − 2 p u ) h u T . For each z ∈ W ∖ ( u T ) z\in W\setminus(uT) z ∈ W ∖ ( u T ) , item (iii) followed by item (ii) gives
f ( z u T ) = ( 1 − p z ) f ( x u T ) + p z f ( y u T ) = ( 1 − p z ) [ b T + ( 1 − p u ) h u T ] + p z [ b T − p u h u T ] = b T + ( 1 − p u − p z ) h u T . \begin{aligned}
f(zuT)&=(1-p_z)f(xuT)+p_zf(yuT)\\
&=(1-p_z)\left[b_T+(1-p_u)h_{uT}\right]+p_z\left[b_T-p_uh_{uT}\right]\\
&=b_T+(1-p_u-p_z)h_{uT}.
\end{aligned} f ( z u T ) = ( 1 − p z ) f ( xu T ) + p z f ( y u T ) = ( 1 − p z ) [ b T + ( 1 − p u ) h u T ] + p z [ b T − p u h u T ] = b T + ( 1 − p u − p z ) h u T .
By the subset-sum convention, S W S_W S W is the total nonterminal voltage sum. The disjoint decomposition W = { u } ⊔ T ⊔ ( W ∖ ( u T ) ) W=\{u\}\sqcup T\sqcup(W\setminus(uT)) W = { u } ⊔ T ⊔ ( W ∖ ( u T )) therefore gives S W ∖ ( u T ) = S W − p u − S T S_{W\setminus(uT)}=S_W-p_u-S_T S W ∖ ( u T ) = S W − p u − S T . With these inputs (30) rewrites as
0 = ( L + 1 ) b T + ( 1 − 2 p u + ( L − 1 ) ( 1 − p u ) − S W ∖ ( u T ) ) h u T = ( L + 1 ) b T + ( L − ( L + 1 ) p u − S W ∖ ( u T ) ) h u T = ( L + 1 ) b T + ( L − S W − L p u + S T ) h u T . \begin{aligned}
0&=(L+1)b_T+\left(1-2p_u+(L-1)(1-p_u)-S_{W\setminus(uT)}\right)h_{uT}\\
&=(L+1)b_T+\left(L-(L+1)p_u-S_{W\setminus(uT)}\right)h_{uT}\\
&=(L+1)b_T+(L-S_W-Lp_u+S_T)h_{uT}.
\end{aligned} 0 = ( L + 1 ) b T + ( 1 − 2 p u + ( L − 1 ) ( 1 − p u ) − S W ∖ ( u T ) ) h u T = ( L + 1 ) b T + ( L − ( L + 1 ) p u − S W ∖ ( u T ) ) h u T = ( L + 1 ) b T + ( L − S W − L p u + S T ) h u T .
Corollary 4.3 (Nonvanishing terminal difference). Under Assumption 4.1 , h ≠ 0 h\ne0 h = 0 .
Proof. If h = 0 h=0 h = 0 , Lemma 4.2 (vi) gives ( L + 1 ) b T = 0 (L+1)b_T=0 ( L + 1 ) b T = 0 for every T T T , hence b = 0 b=0 b = 0 . The interpolation formulas of Lemma 4.2 (ii)–(iii) then give f = 0 f=0 f = 0 on every k k k -subset, a contradiction.
We now reverse the interface identities. The following reconstruction is purely algebraic: compatible data ( h , b , p ) (h,b,p) ( h , b , p ) uniquely determine a function in H k \mathcal{H}_k H k . The additional conditions for producing an equality vector are recorded in Corollary 4.5 .
Lemma 4.4 (Algebraic reconstruction from interface data). Fix 3 ≤ k ≤ ⌊ n 2 ⌋ 3 \le k \le\left\lfloor\frac{n}{2} \right\rfloor 3 ≤ k ≤ ⌊ 2 n ⌋ , put W = V ∖ { x , y } W = V \setminus\{x,y\} W = V ∖ { x , y } , N = ∣ W ∣ N = |W| N = ∣ W ∣ , and L = N − k + 2 L = N-k+2 L = N − k + 2 . Fix a function p : W → [ 0 , 1 ] p: W \to[0,1] p : W → [ 0 , 1 ] , and write p u : = p ( u ) p_u := p(u) p u := p ( u ) and S A : = ∑ u ∈ A p u S_A := \sum_{u\in A}p_u S A := ∑ u ∈ A p u . Suppose h : ( W k − 1 ) → R h: \binom{W}{k-1} \to\mathbb{R} h : ( k − 1 W ) → R and b : ( W k − 2 ) → R b: \binom{W}{k-2} \to\mathbb{R} b : ( k − 2 W ) → R satisfy Lemma 4.2 items (i) (the down-map identities), (iv) (symmetry), (v) (consistency), and (vi) (master identity).
For T ∈ ( W k − 2 ) T \in\binom{W}{k-2} T ∈ ( k − 2 W ) , ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) , u ∈ ξ u \in\xi u ∈ ξ , Q ∈ ( W k ) Q \in\binom{W}{k} Q ∈ ( k W ) , and z ∈ Q z \in Q z ∈ Q , define f : ( V k ) → R f: \binom{V}{k} \to\mathbb{R} f : ( k V ) → R by
f ( x y T ) = b T , (31) f(xyT)=b_T, \tag*{(31)} f ( x y T ) = b T , (31) f ( x ξ ) = b ξ ∖ { u } + ( 1 − p u ) h ξ , (32) f(x\xi)=b_{\xi\setminus\{u\}}+(1-p_u)h_\xi, \tag*{(32)} f ( x ξ ) = b ξ ∖ { u } + ( 1 − p u ) h ξ , (32) f ( y ξ ) = b ξ ∖ { u } − p u h ξ , (33) f(y\xi)=b_{\xi\setminus\{u\}}-p_u h_\xi, \tag*{(33)} f ( y ξ ) = b ξ ∖ { u } − p u h ξ , (33) f ( Q ) = ( 1 − p z ) f ( x ( Q ∖ { z } ) ) + p z f ( y ( Q ∖ { z } ) ) . (34) f(Q)=(1-p_z)f\bigl(x(Q\setminus\{z\})\bigr)+p_zf\bigl(y(Q\setminus\{z\})\bigr). \tag*{(34)} f ( Q ) = ( 1 − p z ) f ( x ( Q ∖ { z }) ) + p z f ( y ( Q ∖ { z }) ) . (34) Then:
(i) Equations (31) –(34) are independent of the choices of u u u and z z z , and uniquely define f f f .
(ii) The reconstructed function f f f belongs to H k \mathcal{H}_k H k .
(iii) The terminal norm of f f f satisfies
δ f ( x , y ) 2 = ( n k ) − 1 ∑ ξ ∈ ( W k − 1 ) h ξ 2 . \delta_f(x,y)^2=\binom{n}{k}^{-1}\sum_{\xi\in\binom{W}{k-1}}h_\xi^2. δ f ( x , y ) 2 = ( k n ) − 1 ξ ∈ ( k − 1 W ) ∑ h ξ 2 . (iv) For every z ∈ W z\in W z ∈ W , δ f ( x , z ) = p z δ f ( x , y ) \delta_f(x,z)=p_z\delta_f(x,y) δ f ( x , z ) = p z δ f ( x , y ) and δ f ( z , y ) = ( 1 − p z ) δ f ( x , y ) \delta_f(z,y)=(1-p_z)\delta_f(x,y) δ f ( z , y ) = ( 1 − p z ) δ f ( x , y ) .
Proof. Item (i): First let ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) and choose distinct u , v ∈ ξ u,v\in\xi u , v ∈ ξ . With R = ξ ∖ { u , v } R=\xi\setminus\{u,v\} R = ξ ∖ { u , v } , Lemma 4.2 (iv) gives b v R − b u R = ( p u − p v ) h ξ b_{vR}-b_{uR}=(p_u-p_v)h_\xi b v R − b u R = ( p u − p v ) h ξ . Consequently,
b v R + ( 1 − p u ) h ξ = b u R + ( 1 − p v ) h ξ , b_{vR}+(1-p_u)h_\xi=b_{uR}+(1-p_v)h_\xi, b v R + ( 1 − p u ) h ξ = b u R + ( 1 − p v ) h ξ ,
b v R − p u h ξ = b u R − p v h ξ . b_{vR}-p_u h_\xi=b_{uR}-p_vh_\xi. b v R − p u h ξ = b u R − p v h ξ .
Thus (32) and (33) are independent of the chosen vertex of ξ \xi ξ .
Next let Q ∈ ( W k ) Q\in\binom{W}{k} Q ∈ ( k W ) , choose distinct z , w ∈ Q z,w\in Q z , w ∈ Q , and put T = Q ∖ { z , w } T=Q\setminus\{z,w\} T = Q ∖ { z , w } . Evaluating (34) with z z z and then with w w w gives, respectively,
( 1 − p z ) f ( x w T ) + p z f ( y w T ) = ( 1 − p z ) [ b T + ( 1 − p w ) h w T ] + p z [ b T − p w h w T ] = b T + ( 1 − p z − p w ) h w T , \begin{aligned}
(1-p_z)f(xwT)+p_zf(ywT)
&=(1-p_z)\left[b_T+(1-p_w)h_{wT}\right]+p_z\left[b_T-p_wh_{wT}\right]\\
&=b_T+(1-p_z-p_w)h_{wT},
\end{aligned} ( 1 − p z ) f ( x w T ) + p z f ( y w T ) = ( 1 − p z ) [ b T + ( 1 − p w ) h w T ] + p z [ b T − p w h w T ] = b T + ( 1 − p z − p w ) h w T ,
( 1 − p w ) f ( x z T ) + p w f ( y z T ) = b T + ( 1 − p z − p w ) h z T . (1-p_w)f(xzT)+p_wf(yzT)=b_T+(1-p_z-p_w)h_{zT}. ( 1 − p w ) f ( x z T ) + p w f ( y z T ) = b T + ( 1 − p z − p w ) h z T .
Lemma 4.2 (v) says ( 1 − p z − p w ) ( h z T − h w T ) = 0 (1-p_z-p_w)(h_{zT}-h_{wT})=0 ( 1 − p z − p w ) ( h z T − h w T ) = 0 , so these evaluations agree. Every k k k -subset contains both terminals, exactly one terminal, or neither terminal. Therefore under the hypotheses on the interface data h h h and b b b , (31) –(34) defines f f f unambiguously and uniquely.
Item (ii): Fix T ∈ ( W k − 2 ) T\in\binom{W}{k-2} T ∈ ( k − 2 W ) . For each z ∈ W ∖ T z\in W\setminus T z ∈ W ∖ T , Lemma 4.2 (vi) is equivalent to
( S W − S T − L + L p z ) h z T = ( L + 1 ) b T . (35) (S_W-S_T-L+Lp_z)h_{zT}=(L+1)b_T. \tag*{(35)} ( S W − S T − L + L p z ) h z T = ( L + 1 ) b T . (35)
Evaluating the down-map identity D k − 1 W h = 0 D^W_{k-1}h=0 D k − 1 W h = 0 from Lemma 4.2 (i) at the ( k − 2 ) (k-2) ( k − 2 ) -subset T T T gives ∑ z ∈ W ∖ T h z T = 0 \sum_{z\in W\setminus T}h_{zT}=0 ∑ z ∈ W ∖ T h z T = 0 . Using this identity and the fact that ∣ W ∖ T ∣ = L |W\setminus T|=L ∣ W ∖ T ∣ = L , we sum the equation (35) over all z ∈ W ∖ T z\in W\setminus T z ∈ W ∖ T to obtain
∑ z ∈ W ∖ T p z h z T = ( L + 1 ) b T . \sum_{z\in W\setminus T}p_z h_{zT}=(L+1)b_T. z ∈ W ∖ T ∑ p z h z T = ( L + 1 ) b T .
Equations (31) –(33) now give, for the ( k − 1 ) (k-1) ( k − 1 ) -subsets x T xT x T and y T yT y T ,
( D k f ) ( x T ) = f ( x y T ) + ∑ z ∈ W ∖ T f ( x z T ) = ( L + 1 ) b T + ∑ z ∈ W ∖ T ( 1 − p z ) h z T = 0 , (D_kf)(xT)=f(xyT)+\sum_{z\in W\setminus T}f(xzT)=(L+1)b_T+\sum_{z\in W\setminus T}(1-p_z)h_{zT}=0, ( D k f ) ( x T ) = f ( x y T ) + z ∈ W ∖ T ∑ f ( x z T ) = ( L + 1 ) b T + z ∈ W ∖ T ∑ ( 1 − p z ) h z T = 0 ,
( D k f ) ( y T ) = f ( x y T ) + ∑ z ∈ W ∖ T f ( y z T ) = ( L + 1 ) b T − ∑ z ∈ W ∖ T p z h z T = 0. (D_kf)(yT)=f(xyT)+\sum_{z\in W\setminus T}f(yzT)=(L+1)b_T-\sum_{z\in W\setminus T}p_z h_{zT}=0. ( D k f ) ( y T ) = f ( x y T ) + z ∈ W ∖ T ∑ f ( y z T ) = ( L + 1 ) b T − z ∈ W ∖ T ∑ p z h z T = 0.
For R ∈ ( W k − 3 ) R \in\binom{W}{k-3} R ∈ ( k − 3 W ) , the remaining case containing both terminals follows from the other down-map identity D k − 2 W b = 0 D^{W}_{k-2}b=0 D k − 2 W b = 0 in Lemma 4.2 (i):
( D k f ) ( x y R ) = ∑ z ∈ W ∖ R b z R = ( D k − 2 W b ) ( R ) = 0. (D_kf)(xyR)=\sum_{z\in W\setminus R}b_{zR}=(D^{W}_{k-2}b)(R)=0. ( D k f ) ( x y R ) = z ∈ W ∖ R ∑ b z R = ( D k − 2 W b ) ( R ) = 0.
Finally, let ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) , choose u ∈ ξ u \in\xi u ∈ ξ , and put T = ξ ∖ { u } T=\xi\setminus\{u\} T = ξ ∖ { u } . For every z ∈ W ∖ ξ z\in W\setminus\xi z ∈ W ∖ ξ , (32) –(34) give f ( z ξ ) = b T + ( 1 − p u − p z ) h ξ f(z\xi)=b_T+(1-p_u-p_z)h_\xi f ( z ξ ) = b T + ( 1 − p u − p z ) h ξ . As ∣ W ∖ ξ ∣ = L − 1 \lvert W\setminus\xi\rvert=L-1 ∣ W ∖ ξ ∣ = L − 1 , it follows that
( D k f ) ( ξ ) = f ( x ξ ) + f ( y ξ ) + ∑ z ∈ W ∖ ξ f ( z ξ ) = ( L + 1 ) b T + ( L − S W − L p u + S T ) h ξ = 0. (D_kf)(\xi)=f(x\xi)+f(y\xi)+\sum_{z\in W\setminus\xi}f(z\xi)=(L+1)b_T+(L-S_W-Lp_u+S_T)h_\xi=0. ( D k f ) ( ξ ) = f ( x ξ ) + f ( y ξ ) + z ∈ W ∖ ξ ∑ f ( z ξ ) = ( L + 1 ) b T + ( L − S W − L p u + S T ) h ξ = 0.
where the final equality is exactly Lemma 4.2 (vi). These four types exhaust the ( k − 1 ) (k-1) ( k − 1 ) -subsets of V V V . Hence D k f = 0 D_kf=0 D k f = 0 , or f ∈ H k f\in\mathcal{H}_k f ∈ H k .
Item (iii): Subtracting (33) from (32) gives f ( x ξ ) − f ( y ξ ) = h ξ f(x\xi)-f(y\xi)=h_\xi f ( x ξ ) − f ( y ξ ) = h ξ . Applying the coordinate formula (22) to the pair x , y x,y x , y yields the claimed formula.
Item (iv): Fix z ∈ W z\in W z ∈ W . In (22) for the pair x , z x,z x , z , the indexing ( k − 1 ) (k-1) ( k − 1 ) -subsets of V ∖ { x , z } V\setminus\{x,z\} V ∖ { x , z } either avoid y y y or contain y y y . Writing them, respectively, as ξ ∈ ( W ∖ { z } k − 1 ) \xi\in\binom{W\setminus\{z\}}{k-1} ξ ∈ ( k − 1 W ∖ { z } ) and y R yR y R where R ∈ ( W ∖ { z } k − 2 ) R\in\binom{W\setminus\{z\}}{k-2} R ∈ ( k − 2 W ∖ { z } ) , gives
δ f ( x , z ) 2 = ( n k ) − 1 [ ∑ ξ ∈ ( W ∖ { z } k − 1 ) [ f ( x ξ ) − f ( z ξ ) ] 2 + ∑ R ∈ ( W ∖ { z } k − 2 ) [ f ( x y R ) − f ( z y R ) ] 2 ] . \delta_f(x,z)^2=\binom{n}{k}^{-1}\left[\sum_{\xi\in\binom{W\setminus\{z\}}{k-1}}[f(x\xi)-f(z\xi)]^2+\sum_{R\in\binom{W\setminus\{z\}}{k-2}}[f(xyR)-f(zyR)]^2\right]. δ f ( x , z ) 2 = ( k n ) − 1 ξ ∈ ( k − 1 W ∖ { z } ) ∑ [ f ( x ξ ) − f ( z ξ ) ] 2 + R ∈ ( k − 2 W ∖ { z } ) ∑ [ f ( x y R ) − f ( z y R ) ] 2 .
Equations (32) –(34) give
f ( x ξ ) − f ( z ξ ) = p z h ξ , f ( x y R ) − f ( z y R ) = p z h z R . f(x\xi)-f(z\xi)=p_z h_\xi,\qquad f(xyR)-f(zyR)=p_z h_{zR}. f ( x ξ ) − f ( z ξ ) = p z h ξ , f ( x y R ) − f ( z y R ) = p z h z R .
Consequently,
δ f ( x , z ) 2 = p z 2 ( n k ) − 1 [ ∑ ξ ∈ ( W ∖ { z } k − 1 ) h ξ 2 + ∑ R ∈ ( W ∖ { z } k − 2 ) h z R 2 ] = p z 2 δ f ( x , y ) 2 . \delta_f(x,z)^2=p_z^2\binom{n}{k}^{-1}\left[\sum_{\xi\in\binom{W\setminus\{z\}}{k-1}}h_\xi^2+\sum_{R\in\binom{W\setminus\{z\}}{k-2}}h_{zR}^2\right]=p_z^2\delta_f(x,y)^2. δ f ( x , z ) 2 = p z 2 ( k n ) − 1 ξ ∈ ( k − 1 W ∖ { z } ) ∑ h ξ 2 + R ∈ ( k − 2 W ∖ { z } ) ∑ h z R 2 = p z 2 δ f ( x , y ) 2 .
The second equality uses the partition of the ( k − 1 ) (k-1) ( k − 1 ) -subsets of W W W into those avoiding z z z and those containing z z z , together with item (iii).
For the pair z , y z,y z , y , split the indexing subsets in (22) according to whether they contain x x x . The corresponding differences are
f ( z ξ ) − f ( y ξ ) = ( 1 − p z ) h ξ , f ( z x R ) − f ( y x R ) = ( 1 − p z ) h z R . f(z\xi)-f(y\xi)=(1-p_z)h_\xi,\qquad f(zxR)-f(yxR)=(1-p_z)h_{zR}. f ( z ξ ) − f ( y ξ ) = ( 1 − p z ) h ξ , f ( z x R ) − f ( y x R ) = ( 1 − p z ) h z R .
The same partition of the ( k − 1 ) (k-1) ( k − 1 ) -subsets of W W W therefore gives δ f ( z , y ) 2 = ( 1 − p z ) 2 δ f ( x , y ) 2 \delta_f(z,y)^2=(1-p_z)^2\delta_f(x,y)^2 δ f ( z , y ) 2 = ( 1 − p z ) 2 δ f ( x , y ) 2 . Since 0 ≤ p z ≤ 1 0\leq p_z\leq1 0 ≤ p z ≤ 1 , taking square roots proves δ f ( x , z ) = p z δ f ( x , y ) \delta_f(x,z)=p_z\delta_f(x,y) δ f ( x , z ) = p z δ f ( x , y ) and δ f ( z , y ) = ( 1 − p z ) δ f ( x , y ) \delta_f(z,y)=(1-p_z)\delta_f(x,y) δ f ( z , y ) = ( 1 − p z ) δ f ( x , y ) . □
Corollary 4.5 (Equality criterion for reconstructed functions). Let f ∈ H k f\in\mathcal{H}_k f ∈ H k be reconstructed from compatible interface data ( h , b , p ) (h,b,p) ( h , b , p ) as in Lemma 4.4 . Then:
(i) f = 0 f=0 f = 0 if and only if h = 0 h=0 h = 0 .
(ii) Suppose h ≠ 0 h\neq0 h = 0 and p p p is the harmonic x x x –y y y voltage of G G G , restricted to W W W . Then
K x y ( k ) f = 0 ⟺ δ f ( u , v ) = δ f ( x , y ) ∣ p u − p v ∣ for every { u , v } ⊂ W with c u v > 0. \mathcal{K}^{(k)}_{xy}f=0\quad\Longleftrightarrow\quad\delta_f(u,v)=\delta_f(x,y)\lvert p_u-p_v\rvert\quad\text{for every }\{u,v\}\subset W\text{ with }c_{uv}>0. K x y ( k ) f = 0 ⟺ δ f ( u , v ) = δ f ( x , y ) ∣ p u − p v ∣ for every { u , v } ⊂ W with c uv > 0.
Proof. Item (i): If h = 0 h=0 h = 0 , the master identity Lemma 4.2 (vi) gives b = 0 b=0 b = 0 , and (31) –(34) then give f = 0 f=0 f = 0 . Conversely, (32) –(33) gives h ξ = f ( x ξ ) − f ( y ξ ) h_\xi=f(x\xi)-f(y\xi) h ξ = f ( x ξ ) − f ( y ξ ) , so f = 0 f=0 f = 0 implies h = 0 h=0 h = 0 .
Item (ii): Suppose h ≠ 0 h\neq0 h = 0 . By Lemma 4.4 (iii), δ f ( x , y ) > 0 \delta_f(x,y)>0 δ f ( x , y ) > 0 . The distance identities in Lemma 4.4 (iv) then give φ f = p \varphi_f=p φ f = p on V V V , with p ( x ) = 0 p(x)=0 p ( x ) = 0 and p ( y ) = 1 p(y)=1 p ( y ) = 1 . Since p p p is harmonic, Proposition 3.3 and Corollary 3.4 reduce residual-kernel membership to the positive-edge distance identities. Those identities already hold on the edges incident to either terminal by Lemma 4.4 (iv); and also on { x , y } \{x,y\} { x , y } if it is a positive edge. Therefore it remains to check them on the positive edges within W W W , which is exactly the right-hand side criterion in the two-way implication. □
Voltage rigidity
4.2. Voltage rigidity. We show that a nonzero equality vector in H k \mathcal{H}_k H k permits at most two nonterminal voltage values. For k = 3 k=3 k = 3 , eliminating the interface variables yields a determinant; for k ≥ 4 k\geq4 k ≥ 4 , comparing the master identity across four vertices produces a Vandermonde factor in three voltage variables. Retain L = N − k + 2 L=N-k+2 L = N − k + 2 from Lemma 4.2 (vi).
Degree three
When k = 3 k=3 k = 3 , the interface data (4.1) are h u v : = f ( x u v ) − f ( y u v ) h_{uv}:=f(x_{uv})-f(y_{uv}) h uv := f ( x uv ) − f ( y uv ) and b u : = f ( x y u ) b_u:=f(x_{yu}) b u := f ( x y u ) , where u , v ∈ W u,v\in W u , v ∈ W are distinct. Then L = N − 1 L=N-1 L = N − 1 , and Lemma 4.2 (vi) becomes
N b v + ( Θ + p v − ( N − 1 ) p u ) h u v = 0 , Θ : = N − 1 − S W . (36) Nb_v+\bigl(\Theta+p_v-(N-1)p_u\bigr)h_{uv}=0,\qquad\Theta:=N-1-S_W. \tag*{(36)} N b v + ( Θ + p v − ( N − 1 ) p u ) h uv = 0 , Θ := N − 1 − S W . (36)
By symmetry, N b u + ( Θ + p u − ( N − 1 ) p v ) h u v = 0 Nb_u+\bigl(\Theta+p_u-(N-1)p_v\bigr)h_{uv}=0 N b u + ( Θ + p u − ( N − 1 ) p v ) h uv = 0 . Hence b u b_u b u and b v b_v b v satisfy the proportionality relation
( Θ + p u − ( N − 1 ) p v ) b v = ( Θ + p v − ( N − 1 ) p u ) b u . (37) \bigl(\Theta+p_u-(N-1)p_v\bigr)b_v=\bigl(\Theta+p_v-(N-1)p_u\bigr)b_u. \tag*{(37)} ( Θ + p u − ( N − 1 ) p v ) b v = ( Θ + p v − ( N − 1 ) p u ) b u . (37)
Lemma 4.6 (Degree-3 determinant). For three distinct vertices u , v , w ∈ W u,v,w\in W u , v , w ∈ W , the determinant of the three pair relations (37) equals
− N ( N − 1 ) ( p u − p v ) ( p u − p w ) ( p v − p w ) . (38) -N(N-1)(p_u-p_v)(p_u-p_w)(p_v-p_w). \tag*{(38)} − N ( N − 1 ) ( p u − p v ) ( p u − p w ) ( p v − p w ) . (38)
Hence, if p u , p v , p w p_u,p_v,p_w p u , p v , p w are pairwise distinct, then b u = b v = b w = 0 b_u=b_v=b_w=0 b u = b v = b w = 0 .
Proof. Writing the relations for ( u , v ) (u,v) ( u , v ) , ( u , w ) (u,w) ( u , w ) , and ( v , w ) (v,w) ( v , w ) as a homogeneous system in ( b u , b v , b w ) (b_u,b_v,b_w) ( b u , b v , b w ) gives the coefficient matrix
M = ( − ( Θ + p v − ( N − 1 ) p u ) Θ + p u − ( N − 1 ) p v 0 − ( Θ + p w − ( N − 1 ) p u ) 0 Θ + p u − ( N − 1 ) p w 0 − ( Θ + p w − ( N − 1 ) p v ) Θ + p v − ( N − 1 ) p w ) . M=
\begin{pmatrix}
-\bigl(\Theta+p_v-(N-1)p_u\bigr) & \Theta+p_u-(N-1)p_v & 0\\
-\bigl(\Theta+p_w-(N-1)p_u\bigr) & 0 & \Theta+p_u-(N-1)p_w\\
0 & -\bigl(\Theta+p_w-(N-1)p_v\bigr) & \Theta+p_v-(N-1)p_w
\end{pmatrix}. M = − ( Θ + p v − ( N − 1 ) p u ) − ( Θ + p w − ( N − 1 ) p u ) 0 Θ + p u − ( N − 1 ) p v 0 − ( Θ + p w − ( N − 1 ) p v ) 0 Θ + p u − ( N − 1 ) p w Θ + p v − ( N − 1 ) p w .
Treat Θ \Theta Θ temporarily as an independent scalar and put q = N − 1 q=N-1 q = N − 1 . Expanding the determinant using, say, the cofactor formula gives
det M = ( Θ + p u − q p v ) ( Θ + p w − q p u ) ( Θ + p v − q p w ) − ( Θ + p v − q p u ) ( Θ + p u − q p w ) ( Θ + p w − q p v ) . \begin{aligned}
\det M={}&(\Theta+p_u-qp_v)(\Theta+p_w-qp_u)(\Theta+p_v-qp_w)\\
&-(\Theta+p_v-qp_u)(\Theta+p_u-qp_w)(\Theta+p_w-qp_v).
\end{aligned} det M = ( Θ + p u − q p v ) ( Θ + p w − q p u ) ( Θ + p v − q p w ) − ( Θ + p v − q p u ) ( Θ + p u − q p w ) ( Θ + p w − q p v ) .
Interchanging any two of p u , p v , p w p_u,p_v,p_w p u , p v , p w exchanges these products and hence changes the sign of det M \det M det M . Since det M \det M det M has total degree at most three in the three voltages, it is a constant multiple of ( p u − p v ) ( p u − p w ) ( p v − p w ) (p_u-p_v)(p_u-p_w)(p_v-p_w) ( p u − p v ) ( p u − p w ) ( p v − p w ) . The coefficient of p u 2 p v p_u^2p_v p u 2 p v is − q -q − q in the first product and q 2 q^2 q 2 in the second, so its coefficient in det M \det M det M is − q − q 2 = − N ( N − 1 ) -q-q^2=-N(N-1) − q − q 2 = − N ( N − 1 ) . This proves (38) for every Θ \Theta Θ , in particular for Θ = N − 1 − S W \Theta=N-1-S_W Θ = N − 1 − S W .
Degrees at least four
Lemma 4.7 (Four-point voltage identity). Assume k ≥ 4 k\ge4 k ≥ 4 . Let R ∈ ( W k − 4 ) R\in\binom{W}{k-4} R ∈ ( k − 4 W ) , and u , v , w , z u,v,w,z u , v , w , z be four distinct vertices of W ∖ R W\setminus R W ∖ R . Then L ( L + 1 ) ( p v − p w ) ( p v − p z ) ( p w − p z ) h u v w R = 0 L(L+1)(p_v-p_w)(p_v-p_z)(p_w-p_z)h_{uvwR}=0 L ( L + 1 ) ( p v − p w ) ( p v − p z ) ( p w − p z ) h uv w R = 0 .
Proof. For distinct a , b , c ∈ W ∖ R a,b,c\in W\setminus R a , b , c ∈ W ∖ R , set K a ( b , c ) : = L − S W + S R − L p a + p b + p c K_a(b,c):=L-S_W+S_R-Lp_a+p_b+p_c K a ( b , c ) := L − S W + S R − L p a + p b + p c . Apply Lemma 4.2 (vi) with T = u v R T=uvR T = uv R , first choosing the vertex w ∈ W ∖ T w\in W\setminus T w ∈ W ∖ T , and then z ∈ W ∖ T z\in W\setminus T z ∈ W ∖ T . The two equations contain the same term ( L + 1 ) b u v R (L+1)b_{uvR} ( L + 1 ) b uv R , which cancels upon subtraction and gives
K w ( u , v ) h u v w R = K z ( u , v ) h u v z R . K_w(u,v)h_{uvwR}=K_z(u,v)h_{uvzR}. K w ( u , v ) h uv w R = K z ( u , v ) h uv z R .
Likewise, taking T = u z R T=uzR T = u z R with the respective choices v , w ∈ W ∖ T v,w\in W\setminus T v , w ∈ W ∖ T , and then T = u w R T=uwR T = u w R with z , v ∈ W ∖ T z,v\in W\setminus T z , v ∈ W ∖ T , gives
K v ( u , z ) h u v z R = K w ( u , z ) h u w z R , K z ( u , w ) h u w z R = K v ( u , w ) h u v w R . \begin{aligned}
K_v(u,z)h_{uvzR}&=K_w(u,z)h_{uwzR},\\
K_z(u,w)h_{uwzR}&=K_v(u,w)h_{uvwR}.
\end{aligned} K v ( u , z ) h uv z R K z ( u , w ) h u w z R = K w ( u , z ) h u w z R , = K v ( u , w ) h uv w R .
Multiplying these identities so as to eliminate h u v z R h_{uvzR} h uv z R and h u w z R h_{uwzR} h u w z R , without dividing by any coefficient, yields
0 = [ K v ( u , z ) K w ( u , v ) K z ( u , w ) − K w ( u , z ) K v ( u , w ) K z ( u , v ) ] h u v w R . 0=\bigl[K_v(u,z)K_w(u,v)K_z(u,w)-K_w(u,z)K_v(u,w)K_z(u,v)\bigr]h_{uvwR}. 0 = [ K v ( u , z ) K w ( u , v ) K z ( u , w ) − K w ( u , z ) K v ( u , w ) K z ( u , v ) ] h uv w R .
The bracket is a polynomial of total degree at most three in p v , p w , p z p_v,p_w,p_z p v , p w , p z and changes sign when any two of these three voltages are exchanged. It therefore vanishes whenever two of them coincide and is a constant multiple of ( p v − p w ) ( p v − p z ) ( p w − p z ) (p_v-p_w)(p_v-p_z)(p_w-p_z) ( p v − p w ) ( p v − p z ) ( p w − p z ) . The coefficient of p v 2 p w p_v^2p_w p v 2 p w is − L ( L + 1 ) -L(L+1) − L ( L + 1 ) , so the bracket equals − L ( L + 1 ) ( p v − p w ) ( p v − p z ) ( p w − p z ) -L(L+1)(p_v-p_w)(p_v-p_z)(p_w-p_z) − L ( L + 1 ) ( p v − p w ) ( p v − p z ) ( p w − p z ) . This proves the lemma.
Proposition 4.8 (At most two nonterminal voltage values). Under Assumption 4.1 , the set { p u : u ∈ W } \{p_u:u\in W\} { p u : u ∈ W } has cardinality at most two.
Proof. Suppose, on the contrary, that { p u : u ∈ W } \{p_u : u \in W\} { p u : u ∈ W } contains at least three distinct voltage values. We discuss the two alternatives, k = 3 k=3 k = 3 and k ≥ 4 k \ge4 k ≥ 4 .
The case k = 3 k=3 k = 3 : Fix u ∈ W u \in W u ∈ W . Since at least three voltage values occur, we can choose v , w ∈ W v,w \in W v , w ∈ W such that p u , p v , p w p_u,p_v,p_w p u , p v , p w are pairwise distinct. Lemma 4.6 gives b u = b v = b w = 0 b_u=b_v=b_w=0 b u = b v = b w = 0 . As u u u was arbitrary, b u = 0 b_u=0 b u = 0 for every u ∈ W u \in W u ∈ W . Hence b = 0 b=0 b = 0 , and h ≠ 0 h \ne0 h = 0 by Corollary 4.3. By Lemma 4.2 (iv), ( p u − p v ) h u v = 0 (p_u-p_v)h_{uv}=0 ( p u − p v ) h uv = 0 for distinct u , v ∈ W u,v \in W u , v ∈ W . In particular, h u v = 0 h_{uv}=0 h uv = 0 whenever p u ≠ p v p_u \ne p_v p u = p v .
For distinct u , v u,v u , v with p u = p v = t p_u=p_v=t p u = p v = t , we use b v = 0 b_v=0 b v = 0 to reduce equation (36) to ( Θ − ( N − 2 ) t ) h u v = 0 (\Theta-(N-2)t)h_{uv}=0 ( Θ − ( N − 2 ) t ) h uv = 0 . The quantity Θ = N − 1 − S W \Theta=N-1-S_W Θ = N − 1 − S W is independent of u , v u,v u , v , and the standing bound k = 3 ≤ n 2 k=3 \le\frac{n}{2} k = 3 ≤ 2 n gives N = n − 2 ≥ 4 N=n-2 \ge4 N = n − 2 ≥ 4 . Hence N − 2 > 0 N-2>0 N − 2 > 0 , so h u v ≠ 0 h_{uv}\ne0 h uv = 0 for a pair with equal voltages is possible only at the common value t ∗ : = Θ N − 2 t_*:=\frac{\Theta}{N-2} t ∗ := N − 2 Θ . Thus h u v h_{uv} h uv can be nonzero only when p u = p v = t ∗ p_u=p_v=t_* p u = p v = t ∗ .
The case k ≥ 4 k \ge4 k ≥ 4 : We first show that h ξ = 0 h_\xi=0 h ξ = 0 whenever ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) contains vertices with different voltages. If exactly two voltage values occur on ξ \xi ξ , choose d ∈ W ∖ ξ d \in W\setminus\xi d ∈ W ∖ ξ at a third voltage value, and choose b , c ∈ ξ b,c \in\xi b , c ∈ ξ at different voltages. If at least three values occur on ξ \xi ξ , choose any d ∈ W ∖ ξ d \in W\setminus\xi d ∈ W ∖ ξ and then b , c ∈ ξ b,c \in\xi b , c ∈ ξ so that p b , p c , p d p_b,p_c,p_d p b , p c , p d are pairwise distinct. These choices are possible: in the first case the third value occurs outside ξ \xi ξ , and in the second case at least two values on ξ \xi ξ differ from p d p_d p d . Moreover, W ∖ ξ ≠ ∅ W\setminus\xi\ne\varnothing W ∖ ξ = ∅ because N ≥ 2 k − 2 > k − 1 N \ge2k-2>k-1 N ≥ 2 k − 2 > k − 1 . Choose a ∈ ξ ∖ { b , c } a \in\xi\setminus\{b,c\} a ∈ ξ ∖ { b , c } and put R = ξ ∖ { a , b , c } R=\xi\setminus\{a,b,c\} R = ξ ∖ { a , b , c } . Applying Lemma 4.7 with ( u , v , w , z ) = ( a , b , c , d ) (u,v,w,z)=(a,b,c,d) ( u , v , w , z ) = ( a , b , c , d ) gives
L ( L + 1 ) ( p b − p c ) ( p b − p d ) ( p c − p d ) h ξ = 0. L(L+1)(p_b-p_c)(p_b-p_d)(p_c-p_d)h_\xi=0. L ( L + 1 ) ( p b − p c ) ( p b − p d ) ( p c − p d ) h ξ = 0.
Since L = N − k + 2 ≥ k ≥ 4 L=N-k+2 \ge k \ge4 L = N − k + 2 ≥ k ≥ 4 and p b , p c , p d p_b,p_c,p_d p b , p c , p d are pairwise distinct, the scalar coefficient is nonzero. Thus h ξ = 0 h_\xi=0 h ξ = 0 , as claimed.
Next fix T ∈ ( W k − 2 ) T \in\binom{W}{k-2} T ∈ ( k − 2 W ) . Choose a ∈ W ∖ T a \in W\setminus T a ∈ W ∖ T so that p p p is not constant on a T aT a T : any a ∈ W ∖ T a \in W\setminus T a ∈ W ∖ T works if p p p is already nonconstant on T T T , while otherwise we choose a a a at a voltage different from the common value on T T T . The preceding paragraph gives h a T = 0 h_{aT}=0 h a T = 0 , and Lemma 4.2 (vi) gives ( L + 1 ) b T = 0 (L+1)b_T=0 ( L + 1 ) b T = 0 . Therefore b T = 0 b_T=0 b T = 0 for every T T T , or b = 0 b=0 b = 0 . Hence h ≠ 0 h\ne0 h = 0 by Corollary 4.3.
It remains to consider ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) on which p p p is constant with common voltage value t t t . Taking any u ∈ ξ u \in\xi u ∈ ξ and T = ξ ∖ { u } T=\xi\setminus\{u\} T = ξ ∖ { u } in Lemma 4.2 (vi) now yields ( L − S W + ( 2 k − N − 4 ) t ) h ξ = 0 (L-S_W+(2k-N-4)t)h_\xi=0 ( L − S W + ( 2 k − N − 4 ) t ) h ξ = 0 . Since N ≥ 2 k − 2 N\ge2k-2 N ≥ 2 k − 2 , we have N + 4 − 2 k ≥ 2 N+4-2k\ge2 N + 4 − 2 k ≥ 2 . Thus a nonzero h ξ h_\xi h ξ on such a set requires its common voltage to equal t ∗ : = L − S W N + 4 − 2 k t_*:=\frac{L-S_W}{N+4-2k} t ∗ := N + 4 − 2 k L − S W . Thus, also in this case, h ξ h_\xi h ξ can be nonzero only if p p p is constant with value t ∗ t_* t ∗ on ξ \xi ξ .
Common contradiction. In both cases we have established b = 0 b=0 b = 0 , h ≠ 0 h\ne0 h = 0 , and a scalar t ∗ t_* t ∗ (depending on the case) such that h ξ ≠ 0 h_\xi\ne0 h ξ = 0 only if every vertex of ξ \xi ξ has voltage t ∗ t_* t ∗ . Choose such a ξ \xi ξ with h ξ ≠ 0 h_\xi\ne0 h ξ = 0 , fix u ∈ ξ u \in\xi u ∈ ξ , and put T = ξ ∖ { u } T=\xi\setminus\{u\} T = ξ ∖ { u } . For any d ∈ W d \in W d ∈ W with p d ≠ t ∗ p_d\ne t_* p d = t ∗ , we have d ∉ ξ d\notin\xi d ∈ / ξ . The set d T dT d T contains vertices with two distinct voltage values, so the support restriction proved in both cases gives h d T = 0 h_{dT}=0 h d T = 0 . As b = 0 b=0 b = 0 , Lemma 4.2 (ii) gives
f ( x d T ) = f ( y d T ) = 0 , f ( x ξ ) = ( 1 − t ∗ ) h ξ , f ( y ξ ) = − t ∗ h ξ . f(xdT)=f(ydT)=0,\qquad f(x\xi)=(1-t_*)h_\xi,\qquad f(y\xi)=-t_*h_\xi. f ( x d T ) = f ( y d T ) = 0 , f ( x ξ ) = ( 1 − t ∗ ) h ξ , f ( y ξ ) = − t ∗ h ξ .
Applying Lemma 4.2 (iii) with distinguished vertex u u u and remaining set d T dT d T gives f ( d ξ ) = 0 f(d\xi)=0 f ( d ξ ) = 0 . Applying the same identity again with distinguished vertex d d d and remaining set ξ \xi ξ gives
0 = f ( d ξ ) = ( 1 − p d ) f ( x ξ ) + p d f ( y ξ ) = ( 1 − p d − t ∗ ) h ξ . 0=f(d\xi)=(1-p_d)f(x\xi)+p_df(y\xi)=(1-p_d-t_*)h_\xi. 0 = f ( d ξ ) = ( 1 − p d ) f ( x ξ ) + p d f ( y ξ ) = ( 1 − p d − t ∗ ) h ξ .
Since h ξ ≠ 0 h_\xi\ne0 h ξ = 0 , every voltage different from t ∗ t_* t ∗ must equal 1 − t ∗ 1-t_* 1 − t ∗ . This contradicts the assumption of at least three distinct nonterminal voltage values. □ \square □
Quadratic equality kernel
Proposition 4.8 established that a nonzero equality vector of Hoeffding degree k ≥ 3 k\ge3 k ≥ 3 permits at most two nonterminal voltage values. In this section we analyze nonzero equality vectors of Hoeffding degree k = 2 k=2 k = 2 . The analysis produces a sharper classification: either every nonterminal voltage equals 1 2 \frac{1}{2} 2 1 , or exactly two complementary values a a a and 1 − a 1-a 1 − a occur.
We use the following notation throughout this section. If n ≤ 3 n\le3 n ≤ 3 , then ⌊ n 2 ⌋ ≤ 1 \left\lfloor\frac{n}{2}\right\rfloor\le1 ⌊ 2 n ⌋ ≤ 1 , so there is no Hoeffding degree-two layer to classify. Hence throughout this section assume n = ∣ V ∣ ≥ 4 n=|V|\ge4 n = ∣ V ∣ ≥ 4 . As before, set W : = V ∖ { x , y } W:=V\setminus\{x,y\} W := V ∖ { x , y } and N : = ∣ W ∣ = n − 2 N:=|W|=n-2 N := ∣ W ∣ = n − 2 . Let G [ W ] G[W] G [ W ] be the graph on W W W obtained by retaining exactly the edges of positive conductance, and let W 1 , … , W q W_1,\ldots,W_q W 1 , … , W q be the connected components of G [ W ] G[W] G [ W ] .
Terminal balance and quadratic interface identities
Recall the harmonic voltage condition (2) . If the harmonic voltage is constant, say equal to ρ i \rho_i ρ i , on a component W i W_i W i , then the internal-edge contributions cancel in the harmonicity equation. Harmonicity at u ∈ W i u\in W_i u ∈ W i therefore reduces to ρ i c x u = ( 1 − ρ i ) c y u \rho_i c_{xu}=(1-\rho_i)c_{yu} ρ i c xu = ( 1 − ρ i ) c y u . This motivates the following definition.
Definition 5.1 (Terminal balance). A component W i W_i W i is terminal-balanced at voltage ρ i ∈ [ 0 , 1 ] \rho_i \in[0,1] ρ i ∈ [ 0 , 1 ] if
ρ i c x u = ( 1 − ρ i ) c y u for every u ∈ W i . (39) \rho_i c_{xu}=(1-\rho_i)c_{yu}\qquad\text{for every }u\in W_i. \tag*{(39)} ρ i c xu = ( 1 − ρ i ) c y u for every u ∈ W i . (39)
Because G G G is connected, every W i W_i W i has at least one vertex incident to x x x or y y y . Hence if (39) holds, ρ i \rho_i ρ i is unique. Equivalently, at every vertex with c x u + c y u > 0 c_{xu}+c_{yu}>0 c xu + c y u > 0 , ρ i = c y u / ( c x u + c y u ) \rho_i=c_{yu}/(c_{xu}+c_{yu}) ρ i = c y u / ( c xu + c y u ) , and this ratio is constant over all vertices of W i W_i W i adjacent to a terminal.
The following lemma records the identities satisfied by every quadratic equality vector. Let F ∈ H 2 ∖ { 0 } F\in\mathcal{H}_2\setminus\{0\} F ∈ H 2 ∖ { 0 } satisfy K x y ( 2 ) F = 0 K_{xy}^{(2)}F=0 K x y ( 2 ) F = 0 . Since a nonzero constant does not belong to H 2 \mathcal{H}_2 H 2 , Corollary 3.4 gives δ F ( x , y ) > 0 \delta_F(x,y)>0 δ F ( x , y ) > 0 . Let p u : = φ F ( u ) p_u:=\varphi_F(u) p u := φ F ( u ) be the harmonic voltage from Proposition 3.3 , and following the notation of § 4 , set S W : = ∑ u ∈ W p u S_W:=\sum_{u\in W}p_u S W := ∑ u ∈ W p u . The interface functions from (4.1) specialize to h u : = F ( x u ) − F ( y u ) h_u:=F(xu)-F(yu) h u := F ( xu ) − F ( y u ) and b : = F ( x y ) b:=F(xy) b := F ( x y ) .
Lemma 5.2 (Scalar quadratic interface). The following hold for distinct u , v ∈ W u,v\in W u , v ∈ W :
(i) The interpolation identities are F ( x u ) = b + ( 1 − p u ) h u F(xu)=b+(1-p_u)h_u F ( xu ) = b + ( 1 − p u ) h u , F ( y u ) = b − p u h u F(yu)=b-p_uh_u F ( y u ) = b − p u h u , and F ( u v ) = b + ( 1 − p u − p v ) h v = b + ( 1 − p u − p v ) h u F(uv)=b+(1-p_u-p_v)h_v=b+(1-p_u-p_v)h_u F ( uv ) = b + ( 1 − p u − p v ) h v = b + ( 1 − p u − p v ) h u .
(ii) The two-vertex consistency identity is ( 1 − p u − p v ) ( h u − h v ) = 0 (1-p_u-p_v)(h_u-h_v)=0 ( 1 − p u − p v ) ( h u − h v ) = 0 .
(iii) The interface vector has zero sum: ∑ u ∈ W h u = 0 \sum_{u\in W}h_u=0 ∑ u ∈ W h u = 0 .
(iv) The scalar master identity is ( N + 1 ) b + ( N − S W − N p u ) h u = 0 (N+1)b+(N-S_W-Np_u)h_u=0 ( N + 1 ) b + ( N − S W − N p u ) h u = 0 .
(v) The terminal norm squared is δ F ( x , y ) 2 = ( N 2 ) − 1 ∑ u ∈ W h u 2 \delta_F(x,y)^2=\binom{N}{2}^{-1}\sum_{u\in W}h_u^2 δ F ( x , y ) 2 = ( 2 N ) − 1 ∑ u ∈ W h u 2 . In particular h ≠ 0 h\ne0 h = 0 .
Proof. By Lemma 3.5, every u ∈ W u\in W u ∈ W satisfies δ F ( x , y ) = δ F ( x , u ) + δ F ( u , y ) \delta_F(x,y)=\delta_F(x,u)+\delta_F(u,y) δ F ( x , y ) = δ F ( x , u ) + δ F ( u , y ) . Applying (29) to the corresponding coordinates of d F d^F d F gives the first two formulas in item (i). Applying it to the coordinate indexed by v v v gives the first expression for F ( u v ) F(uv) F ( uv ) ; interchanging u u u and v v v gives the second. Their difference proves item (ii).
The relations D 2 F ( x ) = D 2 F ( y ) = 0 D_2F(x)=D_2F(y)=0 D 2 F ( x ) = D 2 F ( y ) = 0 say b + ∑ u ∈ W F ( x u ) = 0 b+\sum_{u\in W}F(xu)=0 b + ∑ u ∈ W F ( xu ) = 0 and b + ∑ u ∈ W F ( y u ) = 0 b+\sum_{u\in W}F(yu)=0 b + ∑ u ∈ W F ( y u ) = 0 ; subtracting and using item (i) gives ∑ u ∈ W h u = 0 \sum_{u\in W}h_u=0 ∑ u ∈ W h u = 0 . For fixed u ∈ W u\in W u ∈ W , the remaining down-map identity, together with the interpolation formulas, gives
0 = F ( x u ) + F ( y u ) + ∑ v ∈ W ∖ { u } F ( u v ) = ( N + 1 ) b + [ 1 − 2 p u + ∑ v ∈ W ∖ { u } ( 1 − p u − p v ) ] h u = ( N + 1 ) b + ( N − S W − N p u ) h u . \begin{aligned}
0=F(xu)+F(yu)+\sum_{v\in W\setminus\{u\}}F(uv) \\
&=(N+1)b+\left[1-2p_u+\sum_{v\in W\setminus\{u\}}(1-p_u-p_v)\right]h_u \\
&=(N+1)b+(N-S_W-Np_u)h_u.
\end{aligned} 0 = F ( xu ) + F ( y u ) + v ∈ W ∖ { u } ∑ F ( uv ) = ( N + 1 ) b + 1 − 2 p u + v ∈ W ∖ { u } ∑ ( 1 − p u − p v ) h u = ( N + 1 ) b + ( N − S W − N p u ) h u .
where the last step uses ∑ v ∈ W ∖ { u } p v = S W − p u \sum_{v\in W\setminus\{u\}}p_v=S_W-p_u ∑ v ∈ W ∖ { u } p v = S W − p u . This proves item (iv). Finally, item (v) follows from (22) for the pair x , y x,y x , y . Since F ∈ H 2 F\in\mathcal{H}_2 F ∈ H 2 is a nonzero equality vector, δ F ( x , y ) > 0 \delta_F(x,y)>0 δ F ( x , y ) > 0 by Corollary 3.4, so h ≠ 0 h\ne0 h = 0 .
We distinguish the midpoint case b = 0 b=0 b = 0 from the complementary case b ≠ 0 b\ne0 b = 0 . These names describe the harmonic voltage functions that will be proved below: the first case forces p ≡ 1 2 p\equiv\frac{1}{2} p ≡ 2 1 on W W W , while the second case forces exactly two values a a a and 1 − a 1-a 1 − a , with 0 ≤ a < 1 2 0\le a<\frac{1}{2} 0 ≤ a < 2 1 .
The midpoint case: b = 0 b=0 b = 0 .
Lemma 5.3 (Midpoint case). If b = 0 b=0 b = 0 , then p u = 1 2 p_u=\frac{1}{2} p u = 2 1 for every u ∈ W u\in W u ∈ W , and there is a function α : W → R \alpha:W\to\mathbb{R} α : W → R with ∑ u ∈ W α ( u ) = 0 \sum_{u\in W}\alpha(u)=0 ∑ u ∈ W α ( u ) = 0 such that for all u , v ∈ W u,v\in W u , v ∈ W with u ≠ v u\ne v u = v ,
F ( x u ) = α ( u ) , F ( y u ) = − α ( u ) , F ( x y ) = 0 , F ( u v ) = 0. (40) F(xu)=\alpha(u),\qquad F(yu)=-\alpha(u),\qquad F(xy)=0,\qquad F(uv)=0. \tag*{(40)} F ( xu ) = α ( u ) , F ( y u ) = − α ( u ) , F ( x y ) = 0 , F ( uv ) = 0. (40) Moreover, α \alpha α is constant on each component W i W_i W i .
Proof. When b = 0 b=0 b = 0 , Lemma 5.2 (iv) shows that h u ≠ 0 h_u\ne0 h u = 0 requires p u = 1 N ( N − S W ) = : t p_u=\frac{1}{N}(N-S_W)=:t p u = N 1 ( N − S W ) =: t . Since h ≠ 0 h\ne0 h = 0 and ∑ u ∈ W h u = 0 \sum_{u\in W}h_u=0 ∑ u ∈ W h u = 0 by Lemma 5.2 (iii), there are vertices u , v ∈ W u,v\in W u , v ∈ W with h u > 0 h_u>0 h u > 0 and h v < 0 h_v<0 h v < 0 , and therefore p u = p v = t p_u=p_v=t p u = p v = t . The consistency identity Lemma 5.2 (ii) then becomes ( 1 − 2 t ) ( h u − h v ) = 0 (1-2t)(h_u-h_v)=0 ( 1 − 2 t ) ( h u − h v ) = 0 . As h u − h v > 0 h_u-h_v>0 h u − h v > 0 , we obtain t = 1 2 t=\frac{1}{2} t = 2 1 . If h w = 0 h_w=0 h w = 0 , applying the same consistency identity to u , w u,w u , w gives ( 1 − p u − p w ) h u = 0 (1-p_u-p_w)h_u=0 ( 1 − p u − p w ) h u = 0 , so p w = 1 − p u = 1 2 p_w=1-p_u=\frac{1}{2} p w = 1 − p u = 2 1 as well. Set α ( u ) : = h u 2 \alpha(u) := \frac{h_u}{2} α ( u ) := 2 h u . Using Lemma 5.2 (i) gives (40) , and Lemma 5.2 (iii) gives ∑ u α ( u ) = 0 \sum_u \alpha(u) = 0 ∑ u α ( u ) = 0 . For u , v ∈ W u,v \in W u , v ∈ W , direct use of (22) gives
δ F ( u , v ) 2 = 2 ( n 2 ) − 1 ( α ( u ) − α ( v ) ) 2 . (41) \delta_F(u,v)^2 = 2\binom{n}{2}^{-1}\left(\alpha(u)-\alpha(v)\right)^2. \tag*{(41)} δ F ( u , v ) 2 = 2 ( 2 n ) − 1 ( α ( u ) − α ( v ) ) 2 . (41)
If c u v > 0 c_{uv} > 0 c uv > 0 , then (25) and p u = p v = 1 2 p_u = p_v = \frac{1}{2} p u = p v = 2 1 give δ F ( u , v ) = 0 \delta_F(u,v) = 0 δ F ( u , v ) = 0 . Hence α ( u ) = α ( v ) \alpha(u) = \alpha(v) α ( u ) = α ( v ) on every positive edge inside W W W , and therefore on every component W i W_i W i .
The complementary case: b ≠ 0 b \ne0 b = 0
We first construct a quadratic equality vector when the two nonempty voltage classes A A A and B B B carry values a a a and 1 − a 1-a 1 − a and no positive edge joins them. The construction assigns one value to each pair type determined by x x x , y y y , A A A , and B B B ; we then establish necessity and uniqueness up to a scalar multiple.
Lemma 5.4 (Quadratic construction in the complementary case). Suppose W = A ⊔ B W = A \sqcup B W = A ⊔ B with A A A , B B B nonempty, and let 0 ≤ a < 1 2 0 \le a < \frac{1}{2} 0 ≤ a < 2 1 . Assume that the harmonic x x x –y y y voltage takes value a a a on A A A and 1 − a 1-a 1 − a on B B B , and that no positive edge joins A A A to B B B . Then there exists a nonzero F ∈ H 2 F \in\mathcal{H}_2 F ∈ H 2 satisfying K x y R F = 0 K_{xy}^{\mathsf{R}}F = 0 K x y R F = 0 .
Proof. Fix a scalar Δ ≠ 0 \Delta\ne0 Δ = 0 and put R 0 : = ∣ A ∣ ( 2 a − 1 ) N + 1 Δ R_0 := \frac{|A|(2a-1)}{N+1}\Delta R 0 := N + 1 ∣ A ∣ ( 2 a − 1 ) Δ . Define F : ( V 2 ) → R F : \binom{V}{2} \to\mathbb{R} F : ( 2 V ) → R by the pair-value table (5.4) below. To explain the notation, F ( x A ) F(xA) F ( x A ) denotes the common value F ( x u ) F(xu) F ( xu ) for u ∈ A u \in A u ∈ A , and F ( A B ) F(AB) F ( A B ) denotes the common value F ( u v ) F(uv) F ( uv ) for u ∈ A u \in A u ∈ A , v ∈ B v \in B v ∈ B . The A A AA AA row is used only if ∣ A ∣ ≥ 2 |A| \ge2 ∣ A ∣ ≥ 2 , and the B B BB B B row only if ∣ B ∣ ≥ 2 |B| \ge2 ∣ B ∣ ≥ 2 .
Table 5.4.
The rest of the proof verifies that F F F is a nonzero quadratic equality vector. To verify D 2 F = 0 D_2F = 0 D 2 F = 0 , first compute the row indexed by x x x :
D 2 F ( x ) = F ( x y ) + ∣ A ∣ F ( x A ) + ∣ B ∣ F ( x B ) = ( N + 1 ) R 0 + ∣ A ∣ ( 1 − 2 a ) Δ = 0. D_2F(x) = F(xy) + |A|F(xA) + |B|F(xB) = (N+1)R_0 + |A|(1-2a)\Delta= 0. D 2 F ( x ) = F ( x y ) + ∣ A ∣ F ( x A ) + ∣ B ∣ F ( x B ) = ( N + 1 ) R 0 + ∣ A ∣ ( 1 − 2 a ) Δ = 0.
For u ∈ A u \in A u ∈ A , the ∣ A ∣ − 1 |A|-1 ∣ A ∣ − 1 other vertices of A A A and all ∣ B ∣ |B| ∣ B ∣ vertices of B B B contribute
D 2 F ( u ) = F ( x A ) + F ( y A ) + ∑ w ∈ A ∖ { u } F ( u w ) + ∣ B ∣ F ( A B ) = ( N + 1 ) R 0 + ∣ A ∣ ( 1 − 2 a ) Δ = 0. D_2F(u) = F(xA) + F(yA) + \sum_{w \in A \setminus\{u\}} F(uw) + |B|F(AB) = (N+1)R_0 + |A|(1-2a)\Delta= 0. D 2 F ( u ) = F ( x A ) + F ( y A ) + w ∈ A ∖ { u } ∑ F ( u w ) + ∣ B ∣ F ( A B ) = ( N + 1 ) R 0 + ∣ A ∣ ( 1 − 2 a ) Δ = 0.
The sum over A ∖ { u } A \setminus\{u\} A ∖ { u } is empty when ∣ A ∣ = 1 |A| = 1 ∣ A ∣ = 1 . For v ∈ B v \in B v ∈ B , the remaining two kinds of row sums have the forms
D 2 F ( y ) = F ( x y ) + ∣ A ∣ F ( y A ) + ∣ B ∣ F ( y B ) , D_2F(y) = F(xy) + |A|F(yA) + |B|F(yB), D 2 F ( y ) = F ( x y ) + ∣ A ∣ F ( y A ) + ∣ B ∣ F ( y B ) ,
D 2 F ( v ) = F ( x B ) + F ( y B ) + ∣ A ∣ F ( A B ) + ∑ w ∈ B ∖ { v } F ( v w ) . D_2F(v) = F(xB) + F(yB) + |A|F(AB) + \sum_{w \in B \setminus\{v\}} F(vw). D 2 F ( v ) = F ( x B ) + F ( y B ) + ∣ A ∣ F ( A B ) + w ∈ B ∖ { v } ∑ F ( v w ) .
Substituting the pair values from (5.4) in both rows gives
D 2 F ( y ) = D 2 F ( v ) = ( N + 1 ) R 0 + ∣ A ∣ ( 1 − 2 a ) Δ = 0. D_2F(y) = D_2F(v) = (N+1)R_0 + |A|(1-2a)\Delta= 0. D 2 F ( y ) = D 2 F ( v ) = ( N + 1 ) R 0 + ∣ A ∣ ( 1 − 2 a ) Δ = 0.
Hence D 2 F = 0 D_2F = 0 D 2 F = 0 .
Set Λ : = δ F ( x , y ) 2 \Lambda:= \delta_F(x,y)^2 Λ := δ F ( x , y ) 2 . The coordinates of the difference for ( x , y ) (x,y) ( x , y ) are indexed by W W W , so (22) gives
( n 2 ) Λ = ( ∣ A ∣ + ∣ A ∣ 2 ∣ B ∣ ) Δ 2 = N ∣ A ∣ ∣ B ∣ Δ 2 . \binom{n}{2}\Lambda= \left(|A| + \frac{|A|^2}{|B|}\right)\Delta^2 = \frac{N|A|}{|B|}\Delta^2. ( 2 n ) Λ = ( ∣ A ∣ + ∣ B ∣ ∣ A ∣ 2 ) Δ 2 = ∣ B ∣ N ∣ A ∣ Δ 2 .
For u ∈ A u \in A u ∈ A , the coordinates indexed by y y y and by A ∖ { u } A \setminus\{u\} A ∖ { u } contribute ∣ A ∣ |A| ∣ A ∣ differences of magnitude a ∣ Δ ∣ a|\Delta| a ∣Δ∣ , while those indexed by B B B contribute ∣ B ∣ |B| ∣ B ∣ differences of magnitude a ∣ A ∣ ∣ B ∣ ∣ Δ ∣ \frac{a|A|}{|B|}|\Delta| ∣ B ∣ a ∣ A ∣ ∣Δ∣ . For v ∈ B v \in B v ∈ B , the analogous differences for ( x , v ) (x,v) ( x , v ) have magnitudes ( 1 − a ) ∣ Δ ∣ (1-a)|\Delta| ( 1 − a ) ∣Δ∣ on A A A and ( 1 − a ) ∣ A ∣ ∣ B ∣ ∣ Δ ∣ \frac{(1-a)|A|}{|B|}|\Delta| ∣ B ∣ ( 1 − a ) ∣ A ∣ ∣Δ∣ on { y } ∪ ( B ∖ { v } ) \{y\} \cup(B \setminus\{v\}) { y } ∪ ( B ∖ { v }) . Consequently,
( n 2 ) δ F ( x , u ) 2 = a 2 ( ∣ A ∣ + ∣ A ∣ 2 ∣ B ∣ ) Δ 2 = a 2 ( n 2 ) Λ , \binom{n}{2}\delta_F(x,u)^2=a^2\left(|A|+\frac{|A|^2}{|B|}\right)\Delta^2=a^2\binom{n}{2}\Lambda, ( 2 n ) δ F ( x , u ) 2 = a 2 ( ∣ A ∣ + ∣ B ∣ ∣ A ∣ 2 ) Δ 2 = a 2 ( 2 n ) Λ ,
( n 2 ) δ F ( x , v ) 2 = ( 1 − a ) 2 ( ∣ A ∣ + ∣ A ∣ 2 ∣ B ∣ ) Δ 2 = ( 1 − a ) 2 ( n 2 ) Λ . \binom{n}{2}\delta_F(x,v)^2=(1-a)^2\left(|A|+\frac{|A|^2}{|B|}\right)\Delta^2=(1-a)^2\binom{n}{2}\Lambda. ( 2 n ) δ F ( x , v ) 2 = ( 1 − a ) 2 ( ∣ A ∣ + ∣ B ∣ ∣ A ∣ 2 ) Δ 2 = ( 1 − a ) 2 ( 2 n ) Λ.
The same calculation with y y y instead of x x x gives δ F ( y , u ) 2 = ( 1 − a ) 2 Λ \delta_F(y,u)^2=(1-a)^2\Lambda δ F ( y , u ) 2 = ( 1 − a ) 2 Λ and δ F ( y , v ) 2 = a 2 Λ \delta_F(y,v)^2=a^2\Lambda δ F ( y , v ) 2 = a 2 Λ . The distances within either class vanish because the corresponding coordinate differences are zero for every pair type.
For u ∈ A u \in A u ∈ A and v ∈ B v \in B v ∈ B , the coordinates indexed by x x x , y y y , the ∣ A ∣ − 1 |A|-1 ∣ A ∣ − 1 other vertices of A A A , and the ∣ B ∣ − 1 |B|-1 ∣ B ∣ − 1 other vertices of B B B give, respectively, the four squared differences below:
( n 2 ) δ F ( u , v ) 2 Δ 2 = ( 1 − a + a ∣ A ∣ ∣ B ∣ ) 2 + ( a + ( 1 − a ) ∣ A ∣ ∣ B ∣ ) 2 + ( ∣ A ∣ − 1 ) ( 1 − 2 a ) 2 + ( ∣ B ∣ − 1 ) ( ∣ A ∣ ∣ B ∣ ) 2 ( 1 − 2 a ) 2 = ( 1 − 2 a ) 2 N ∣ A ∣ ∣ B ∣ + 2 a ( 1 − a ) N 2 ∣ B ∣ 2 . \begin{aligned}
\binom{n}{2}\frac{\delta_F(u,v)^2}{\Delta^2}
=\left(1-a+a\frac{|A|}{|B|}\right)^2
+\left(a+(1-a)\frac{|A|}{|B|}\right)^2
+(|A|-1)(1-2a)^2
+(|B|-1)\left(\frac{|A|}{|B|}\right)^2(1-2a)^2 \\
&=(1-2a)^2\frac{N|A|}{|B|}+\frac{2a(1-a)N^2}{|B|^2}.
\end{aligned} ( 2 n ) Δ 2 δ F ( u , v ) 2 = ( 1 − a + a ∣ B ∣ ∣ A ∣ ) 2 + ( a + ( 1 − a ) ∣ B ∣ ∣ A ∣ ) 2 + ( ∣ A ∣ − 1 ) ( 1 − 2 a ) 2 + ( ∣ B ∣ − 1 ) ( ∣ B ∣ ∣ A ∣ ) 2 ( 1 − 2 a ) 2 = ( 1 − 2 a ) 2 ∣ B ∣ N ∣ A ∣ + ∣ B ∣ 2 2 a ( 1 − a ) N 2 .
Consequently,
(5.5)
δ F ( u , v ) 2 = ( 1 − 2 a ) 2 Λ + ( n 2 ) − 1 2 a ( 1 − a ) N 2 ∣ B ∣ 2 Δ 2 . (42) \delta_F(u,v)^2=(1-2a)^2\Lambda+\binom{n}{2}^{-1}\frac{2a(1-a)N^2}{|B|^2}\Delta^2. \tag*{(42)} δ F ( u , v ) 2 = ( 1 − 2 a ) 2 Λ + ( 2 n ) − 1 ∣ B ∣ 2 2 a ( 1 − a ) N 2 Δ 2 . (42)
By hypothesis no positive edge joins A A A to B B B . The displayed distances give (25) on every positive edge joining a terminal to W W W , and the zero within-block distances give it on internal positive edges. On { x , y } \{x,y\} { x , y } , if it is an edge, the equality is tautological. Moreover, the normalized distance from x x x agrees with the harmonic voltage p p p . For any u ∈ A u \in A u ∈ A , F ( x u ) − F ( y u ) = Δ ≠ 0 F(xu)-F(yu)=\Delta\ne0 F ( xu ) − F ( y u ) = Δ = 0 , so δ F ( x , y ) > 0 \delta_F(x,y)>0 δ F ( x , y ) > 0 . Since ϕ F = p \phi_F=p ϕ F = p and the positive-edge conditions have been verified, Proposition 3.3 and Corollary 3.4 give 0 ≠ F ∈ ker ( K x y ∣ H 2 ) 0 \ne F \in\ker(K_{xy}|_{\mathcal H_2}) 0 = F ∈ ker ( K x y ∣ H 2 ) . □
Lemma 5.5 (Complementary case). Suppose b ≠ 0 b \ne0 b = 0 . Then:
(i) There are exactly two nonterminal voltage values a a a and 1 − a 1-a 1 − a , where 0 ≤ a < 1 2 0 \le a < \frac{1}{2} 0 ≤ a < 2 1 .
(ii) Writing A : = { u ∈ W : p u = a } A:=\{u\in W:p_u=a\} A := { u ∈ W : p u = a } and B : = { u ∈ W : p u = 1 − a } B:=\{u\in W:p_u=1-a\} B := { u ∈ W : p u = 1 − a } , the space of quadratic equality vectors with this voltage partition is one-dimensional. More precisely, if Δ : = h u \Delta:=h_u Δ := h u on A A A , then h = − ∣ A ∣ ∣ B ∣ Δ h=-\frac{|A|}{|B|}\Delta h = − ∣ B ∣ ∣ A ∣ Δ on B B B , and F F F is exactly the function in (5.4) with R 0 = ∣ A ∣ ( 2 a − 1 ) N + 1 Δ R_0=\frac{|A|(2a-1)}{N+1}\Delta R 0 = N + 1 ∣ A ∣ ( 2 a − 1 ) Δ .
(iii) No positive edge inside W W W joins A A A to B B B .
Proof. Item (i): Since b ≠ 0 b \ne0 b = 0 , the scalar master identity Lemma 5.2 (iv) gives h u ≠ 0 h_u \ne0 h u = 0 and N − S W − N p u ≠ 0 N-S_W-Np_u \ne0 N − S W − N p u = 0 for every u ∈ W u \in W u ∈ W . For distinct u , v ∈ W u,v \in W u , v ∈ W , subtract the identity indexed by v v v from that indexed by u u u :
(5.6)
0 = ( N − S W − N p u ) h u − ( N − S W − N p v ) h v = ( N − S W ) ( h u − h v ) − N ( p u h u − p v h v ) . (43) 0=(N-S_W-Np_u)h_u-(N-S_W-Np_v)h_v=(N-S_W)(h_u-h_v)-N(p_uh_u-p_vh_v). \tag*{(43)} 0 = ( N − S W − N p u ) h u − ( N − S W − N p v ) h v = ( N − S W ) ( h u − h v ) − N ( p u h u − p v h v ) . (43)
If h u = h v h_u=h_v h u = h v , (43) reduces to N ( p u − p v ) h u = 0 N(p_u-p_v)h_u=0 N ( p u − p v ) h u = 0 , hence p u = p v p_u=p_v p u = p v . On the other hand, if p u = p v = t p_u=p_v=t p u = p v = t , (43) reduces to ( N − S W − N t ) ( h u − h v ) = 0 (N-S_W-Nt)(h_u-h_v)=0 ( N − S W − N t ) ( h u − h v ) = 0 ; and since N − S W − N t ≠ 0 N-S_W-Nt\ne0 N − S W − N t = 0 , we have h u = h v h_u=h_v h u = h v . Therefore
(5.7)
h u = h v ⟺ p u = p v . (44) h_u=h_v\Longleftrightarrow p_u=p_v. \tag*{(44)} h u = h v ⟺ p u = p v . (44)
When p u ≠ p v p_u\ne p_v p u = p v , we have h u ≠ h v h_u\ne h_v h u = h v , and the consistency identity Lemma 5.2 (ii) implies p u + p v = 1 p_u+p_v=1 p u + p v = 1 . Thus at most two complementary voltage values occur. They cannot all coincide: otherwise h h h would be constant by the equivalence above, and the zero sum identity Lemma 5.2 (iii) would give h = 0 h=0 h = 0 , contrary to Lemma 5.2 (iv) with b ≠ 0 b\ne0 b = 0 . Thus exactly two values occur, denoted by a a a and 1 − a 1-a 1 − a with 0 ≤ a < 1 2 0\le a<\frac12 0 ≤ a < 2 1 .
Item (ii): By the equivalence (44) , h h h is constant on each voltage class A , B A,B A , B ; write its values as h A , h B h_A,h_B h A , h B . Lemma 5.2 (iii) gives ∣ A ∣ h A + ∣ B ∣ h B = 0 |A|h_A+|B|h_B=0 ∣ A ∣ h A + ∣ B ∣ h B = 0 . Setting Δ : = h A ≠ 0 \Delta:=h_A\ne0 Δ := h A = 0 yields h B = − ∣ A ∣ ∣ B ∣ Δ h_B=-\frac{|A|}{|B|}\Delta h B = − ∣ B ∣ ∣ A ∣ Δ . Apply Lemma 5.2 (iv) at u ∈ A u\in A u ∈ A , where p u = a p_u=a p u = a and h u = Δ h_u=\Delta h u = Δ . Using S W = ∣ A ∣ a + ∣ B ∣ ( 1 − a ) S_W=|A|a+|B|(1-a) S W = ∣ A ∣ a + ∣ B ∣ ( 1 − a ) and N = ∣ A ∣ + ∣ B ∣ N=|A|+|B| N = ∣ A ∣ + ∣ B ∣ gives
( N + 1 ) b = ( S W + N a − N ) Δ = ∣ A ∣ ( 2 a − 1 ) Δ . (N+1)b=(S_W+Na-N)\Delta=|A|(2a-1)\Delta. ( N + 1 ) b = ( S W + N a − N ) Δ = ∣ A ∣ ( 2 a − 1 ) Δ.
Hence b = R 0 b=R_0 b = R 0 in (5.4). Substituting b = R 0 b=R_0 b = R 0 , h A = Δ h_A=\Delta h A = Δ , and h B = − Δ ∣ A ∣ ∣ B ∣ h_B=-\Delta\frac{|A|}{|B|} h B = − Δ ∣ B ∣ ∣ A ∣ into Lemma 5.2 (i) reproduces the x A xA x A , y A yA y A , x B xB x B , and y B yB y B rows of (5.4). Its formula for F ( u v ) F(uv) F ( uv ) likewise gives the A B AB A B , A A AA AA , and B B BB B B rows; the remaining x y xy x y entry equals b = R 0 b=R_0 b = R 0 . Thus every vector for this fixed voltage partition is determined by the single scalar Δ \Delta Δ .
Item (iii): The coordinate calculation leading to (42) uses only the pair-value table (5.4) and (22) , not the no-cross-edge assumption invoked later in the construction proof. By item (ii), the present F F F has those same pair values. Thus, if 0 < a < 1 2 0<a<\frac{1}{2} 0 < a < 2 1 , the formula gives, for u ∈ A u\in A u ∈ A and v ∈ B v\in B v ∈ B ,
δ F ( u , v ) 2 − ( p u − p v ) 2 δ F ( x , y ) 2 = ( n 2 ) − 1 2 a ( 1 − a ) N 2 ∣ B ∣ 2 Δ 2 > 0. \delta_F(u,v)^2-(p_u-p_v)^2\delta_F(x,y)^2=\binom{n}{2}^{-1}\frac{2a(1-a)N^2}{|B|^2}\Delta^2>0. δ F ( u , v ) 2 − ( p u − p v ) 2 δ F ( x , y ) 2 = ( 2 n ) − 1 ∣ B ∣ 2 2 a ( 1 − a ) N 2 Δ 2 > 0.
A positive A A A –B B B edge would instead require equality by (25) , which is impossible. If a = 0 a=0 a = 0 , harmonicity at u ∈ A u\in A u ∈ A , where p u = 0 p_u=0 p u = 0 , gives ∑ z ∈ V c u z p z = 0 \sum_{z\in V}c_{uz}p_z=0 ∑ z ∈ V c u z p z = 0 . Every summand is nonnegative, and a positive edge from u u u to v ∈ B v\in B v ∈ B , where p v = 1 p_v=1 p v = 1 , would make one strictly positive. So there is no positive A A A –B B B edge in this case either. □
Existence criteria and kernel dimensions.
Theorem 5.6 (Quadratic kernel classification). Let W 1 , … , W q W_1,\ldots,W_q W 1 , … , W q be the connected components of G [ W ] G[W] G [ W ] . Then
dim ker ( K x y ( 2 ) ∣ H 2 ) = { q − 1 , if every W i is terminal-balanced and every ρ i = 1 2 (the midpoint case), 1 , if every W i is terminal-balanced and { ρ 1 , … , ρ q } = { a , 1 − a } for some 0 ≤ a < 1 2 (the complementary case), 0 , otherwise. (45) \dim\ker\left(\mathcal{K}^{(2)}_{xy}\big|_{\mathcal{H}_2}\right)=
\begin{cases}
q-1, & \text{if every }W_i\text{ is terminal-balanced and every }\rho_i=\frac{1}{2}\text{ (the midpoint case),}\\
1, & \text{if every }W_i\text{ is terminal-balanced and }\{\rho_1,\ldots,\rho_q\}=\{a,1-a\}\\
& \text{for some }0\leq a<\frac{1}{2}\text{ (the complementary case),}\\
0, & \text{otherwise.}
\end{cases} \tag*{(45)} dim ker ( K x y ( 2 ) H 2 ) = ⎩ ⎨ ⎧ q − 1 , 1 , 0 , if every W i is terminal-balanced and every ρ i = 2 1 (the midpoint case), if every W i is terminal-balanced and { ρ 1 , … , ρ q } = { a , 1 − a } for some 0 ≤ a < 2 1 (the complementary case), otherwise. (45)
Proof. Necessity and dimension upper bounds. Suppose 0 ≠ F ∈ ker ( K x y ( 2 ) ∣ H 2 ) 0\ne F\in\ker(\mathcal{K}^{(2)}_{xy}|_{\mathcal{H}_2}) 0 = F ∈ ker ( K x y ( 2 ) ∣ H 2 ) , and let p p p be its harmonic voltage. The alternatives b = 0 b=0 b = 0 and b ≠ 0 b\ne0 b = 0 are covered by Lemmas 5.3 and 5.5.
If b = 0 b=0 b = 0 , Lemma 5.3 gives p ≡ 1 2 p\equiv\frac{1}{2} p ≡ 2 1 on W W W , so harmonicity implies c x u = c y u c_{xu}=c_{yu} c xu = c y u at each u ∈ W i u\in W_i u ∈ W i . Every W i W_i W i is therefore terminal-balanced at 1 2 \frac{1}{2} 2 1 . Writing the componentwise constants as α i \alpha_i α i , its zero-sum condition is ∑ i = 1 q ∣ W i ∣ α i = 0 \sum_{i=1}^q|W_i|\alpha_i=0 ∑ i = 1 q ∣ W i ∣ α i = 0 . Thus these vectors lie in a parameter space of dimension q − 1 q-1 q − 1 , proving the upper bound.
If b ≠ 0 b\ne0 b = 0 , Lemma 5.5 gives two distinct voltages a a a and 1 − a 1-a 1 − a , both attained, with 0 ≤ a < 1 2 0\leq a<\frac{1}{2} 0 ≤ a < 2 1 , and no positive edge between the corresponding classes. Each connected component W i W_i W i therefore lies in one class. Writing its voltage as ρ i \rho_i ρ i , harmonicity at u ∈ W i u\in W_i u ∈ W i reduces to ρ i c x u = ( 1 − ρ i ) c y u \rho_i c_{xu}=(1-\rho_i)c_{yu} ρ i c xu = ( 1 − ρ i ) c y u ; hence every component is terminal-balanced, with { ρ 1 , … , ρ q } = { a , 1 − a } \{\rho_1,\ldots,\rho_q\}=\{a,1-a\} { ρ 1 , … , ρ q } = { a , 1 − a } . The harmonic x x x –y y y voltage is uniquely determined by the graph and the terminals. Thus a a a and the voltage classes A = { u ∈ W : p u = a } A=\{u\in W:p_u=a\} A = { u ∈ W : p u = a } and B = { u ∈ W : p u = 1 − a } B=\{u\in W:p_u=1-a\} B = { u ∈ W : p u = 1 − a } are fixed, independently of F F F . By Lemma 5.5(ii), every such F F F is specified by one scalar, giving a dimension upper bound of one.
Sufficiency and attainment of the dimension bounds. Suppose first that every component is terminal-balanced at 1 2 \frac{1}{2} 2 1 . Define p ( x ) = 0 p(x)=0 p ( x ) = 0 , p ( y ) = 1 p(y)=1 p ( y ) = 1 , and p ≡ 1 2 p\equiv\frac{1}{2} p ≡ 2 1 on W W W . Equation (39) makes p p p harmonic. For any constants α i \alpha_i α i with ∑ i = 1 q ∣ W i ∣ α i = 0 \sum_{i=1}^q|W_i|\alpha_i=0 ∑ i = 1 q ∣ W i ∣ α i = 0 , let α = α i \alpha=\alpha_i α = α i on W i W_i W i and define F F F by (40) . Its down-map sums are D 2 F ( x ) = ∑ u ∈ W α ( u ) = 0 D_2F(x)=\sum_{u\in W}\alpha(u)=0 D 2 F ( x ) = ∑ u ∈ W α ( u ) = 0 , D 2 F ( y ) − ∑ u ∈ W α ( u ) = 0 D_2F(y)-\sum_{u\in W}\alpha(u)=0 D 2 F ( y ) − ∑ u ∈ W α ( u ) = 0 , and D 2 F ( u ) = α ( u ) − α ( u ) = 0 D_2F(u)=\alpha(u)-\alpha(u)=0 D 2 F ( u ) = α ( u ) − α ( u ) = 0 for u ∈ W u\in W u ∈ W ; thus F ∈ H 2 F\in\mathcal{H}_2 F ∈ H 2 . With Λ : = ( n 2 ) − 1 ∑ u ∈ W α ( u ) 2 \Lambda:=\binom{n}{2}^{-1}\sum_{u\in W}\alpha(u)^2 Λ := ( 2 n ) − 1 ∑ u ∈ W α ( u ) 2 , (22) yields
δ F ( x , y ) 2 = 4 Λ , δ F ( x , u ) 2 = δ F ( u , y ) 2 = Λ ( u ∈ W ) . \delta_F(x,y)^2=4\Lambda,\qquad\delta_F(x,u)^2=\delta_F(u,y)^2=\Lambda\quad(u\in W). δ F ( x , y ) 2 = 4Λ , δ F ( x , u ) 2 = δ F ( u , y ) 2 = Λ ( u ∈ W ) .
Because α \alpha α is constant on each W i W_i W i , (41) gives zero F F F -distance on every positive edge inside W W W . The displayed terminal distances therefore verify (25) on every positive edge; the x y xy x y edge, if present, is automatic. For nonzero α \alpha α , these distances also show that ϕ F = p \phi_F=p ϕ F = p , so Proposition 3.3 and Corollary 3.4 give K x y ( 2 ) F = 0 \mathcal{K}^{(2)}_{xy}F=0 K x y ( 2 ) F = 0 ; the zero vector is in the kernel as well.
Conversely, let F F F be a nonzero equality vector in the midpoint case. Since p = 1 2 p=\frac{1}{2} p = 2 1 on W W W , Lemma 5.5 excludes b ≠ 0 b\ne0 b = 0 . Thus Lemma 5.3 gives (40) , with α ∣ W i = α i \alpha|_{W_i}=\alpha_i α ∣ W i = α i and ∑ i = 1 q ∣ W i ∣ α i = 0 \sum_{i=1}^q|W_i|\alpha_i=0 ∑ i = 1 q ∣ W i ∣ α i = 0 . The parameters are unique, since α i = F ( x u ) \alpha_i=F(xu) α i = F ( xu ) for any u ∈ W i u\in W_i u ∈ W i . Together with the preceding construction, which also includes the zero vector, this identifies the kernel linearly with { ( α i ) i = 1 q ∈ R q : ∑ i = 1 q ∣ W i ∣ α i = 0 } \{(\alpha_i)_{i=1}^q\in\mathbb{R}^q:\sum_{i=1}^q|W_i|\alpha_i=0\} {( α i ) i = 1 q ∈ R q : ∑ i = 1 q ∣ W i ∣ α i = 0 } , which has dimension q − 1 q-1 q − 1 .
Finally, suppose the terminal-balance parameters take exactly the two values a a a and $1-a$, with 0 ≤ a < 1 2 0\leq a<\frac{1}{2} 0 ≤ a < 2 1 . Let A A A and B B B (both nonempty) be the unions of components with parameters a a a and 1 − a 1-a 1 − a , respectively. The function taking values 0 , a , 1 − a , 1 0,a,1-a,1 0 , a , 1 − a , 1 on, respectively, x , A , B , y x,A,B,y x , A , B , y is harmonic by (39) . No positive edge joins $A to B B B , since distinct components of G [ W ] G[W] G [ W ] have no such edge. Thus Lemma 5.4 supplies a nonzero quadratic kernel vector. This attains the dimension upper bound of 1 established above. □
Remark 5.7 (Terminal-balance obstruction). By Theorem 5.6, if a component of G [ W ] G[W] G [ W ] is not terminal-balanced at any voltage, the quadratic equality kernel is zero. In particular, a nonzero quadratic equality vector forces terminal balance on every nonterminal component.
Degree lowering via zero-distance classes
Throughout this section Assumption 4.1 is in force. We retain the shorthands W , N , p u W,N,p_u W , N , p u , the interface data h , b h,b h , b from (4.1), and L = N − k + 2 > 0 L=N-k+2>0 L = N − k + 2 > 0 . By Proposition 4.8, at most two nonterminal voltage values occur. We distinguish whether each voltage level is a single zero-distance class or one level splits into several such classes. These cases lead, respectively, to complementary and midpoint graph geometry, from which the quadratic classification supplies a degree-two equality vector.
Single-class voltage levels: the complementary case
We first consider the case in which each voltage value is a single zero-distance class. If there is only one nonterminal voltage, the single-class hypothesis gives δ f ( u , v ) = 0 \delta_f(u,v)=0 δ f ( u , v ) = 0 for all u , v ∈ W u,v\in W u , v ∈ W . By (21) , every transposition τ u v \tau_{uv} τ uv within W W W fixes f f f and hence h h h . These transpositions generate S W S_W S W , which acts transitively on ( k − 1 ) (k-1) ( k − 1 ) -subsets, so h ≡ c h\equiv c h ≡ c . Then D k − 1 W h = 0 D_{k-1}^{W}h=0 D k − 1 W h = 0 gives 0 = ( N − k + 2 ) c = L c 0=(N-k+2)c=Lc 0 = ( N − k + 2 ) c = L c . Since L > 0 L>0 L > 0 , this forces h = 0 h=0 h = 0 , contradicting δ f ( x , y ) > 0 \delta_f(x,y)>0 δ f ( x , y ) > 0 . Hence there are exactly two nonterminal voltage classes.
Let A , B A,B A , B be these classes, with respective voltages p A ≠ p B p_A\ne p_B p A = p B . By Corollary 4.3, h ≠ 0 h\ne0 h = 0 . Since vertices within each class have zero δ f \delta_f δ f -distance, their transpositions fix f f f . Consequently h h h and b b b are invariant under S A × S B S_A\times S_B S A × S B . For 0 ≤ j ≤ k − 1 0\le j\le k-1 0 ≤ j ≤ k − 1 , let h j h_j h j be the value of h h h on a ( k − 1 ) (k-1) ( k − 1 ) -set containing j j j vertices of B B B , whenever that orbit exists. Similarly, let b j b_j b j be the value of b b b on a ( k − 2 ) (k-2) ( k − 2 ) -set containing j j j vertices of B B B .
Lemma 6.1 (Minimum sizes of the voltage classes). If h ≠ 0 h\ne0 h = 0 , then ∣ A ∣ , ∣ B ∣ ≥ k − 1 |A|,|B|\ge k-1 ∣ A ∣ , ∣ B ∣ ≥ k − 1 .
Proof. The standing range k ≤ ⌊ n 2 ⌋ k\le\left\lfloor\frac{n}{2}\right\rfloor k ≤ ⌊ 2 n ⌋ gives N = ∣ A ∣ + ∣ B ∣ ≥ 2 ( k − 1 ) N=|A|+|B|\ge2(k-1) N = ∣ A ∣ + ∣ B ∣ ≥ 2 ( k − 1 ) . Suppose ∣ A ∣ < k − 1 |A|<k-1 ∣ A ∣ < k − 1 , and set j 0 = k − 1 − ∣ A ∣ ≥ 1 j_0=k-1-|A|\ge1 j 0 = k − 1 − ∣ A ∣ ≥ 1 . The feasible indices of h j h_j h j are then j 0 ≤ j ≤ k − 1 j_0\le j\le k-1 j 0 ≤ j ≤ k − 1 (in particular, ∣ B ∣ ≥ k − 1 |B|\ge k-1 ∣ B ∣ ≥ k − 1 ). Choose B ′ ⊆ B B'\subseteq B B ′ ⊆ B with ∣ B ′ ∣ = j 0 − 1 |B'|=j_0-1 ∣ B ′ ∣ = j 0 − 1 , and put Q = A ⊔ B ′ Q=A\sqcup B' Q = A ⊔ B ′ . Now ∣ Q ∣ = ∣ A ∣ + j 0 − 1 = k − 2 |Q|=|A|+j_0-1=k-2 ∣ Q ∣ = ∣ A ∣ + j 0 − 1 = k − 2 , so the down-map identity Lemma 4.2 (i) applies:
0 = ( D k − 1 W h ) ( Q ) = ∑ z ∈ W ∖ Q h Q z = ( ∣ B ∣ − j 0 + 1 ) h j 0 . 0=(D_{k-1}^{W}h)(Q)=\sum_{z\in W\setminus Q}h_{Qz}=(|B|-j_0+1)h_{j_0}. 0 = ( D k − 1 W h ) ( Q ) = z ∈ W ∖ Q ∑ h Q z = ( ∣ B ∣ − j 0 + 1 ) h j 0 .
Since ∣ B ∣ − j 0 + 1 > 0 |B|-j_0+1>0 ∣ B ∣ − j 0 + 1 > 0 , we have h j 0 = 0 h_{j_0}=0 h j 0 = 0 . For each j 0 ≤ j < k − 1 j_0\le j<k-1 j 0 ≤ j < k − 1 , choose a ( k − 2 ) (k-2) ( k − 2 ) -subset Q ′ ⊂ W Q'\subset W Q ′ ⊂ W containing j j j vertices of B B B . Such a subset exists, and applying the same down-map identity to Q ′ Q' Q ′ gives
0 = ( D k − 1 W h ) ( Q ′ ) = ( ∣ A ∣ − k + 2 + j ) h j + ( ∣ B ∣ − j ) h j + 1 . 0=(D_{k-1}^{W}h)(Q')=(|A|-k+2+j)h_j+(|B|-j)h_{j+1}. 0 = ( D k − 1 W h ) ( Q ′ ) = ( ∣ A ∣ − k + 2 + j ) h j + ( ∣ B ∣ − j ) h j + 1 .
The coefficient ∣ B ∣ − j |B|-j ∣ B ∣ − j is positive, so induction on j j j shows that every feasible h j h_j h j vanishes, contradicting h ≠ 0 h\ne0 h = 0 . Therefore ∣ A ∣ ≥ k − 1 |A|\ge k-1 ∣ A ∣ ≥ k − 1 . Interchanging A A A and B B B proves ∣ B ∣ ≥ k − 1 |B|\ge k-1 ∣ B ∣ ≥ k − 1 . □
By Lemma 6.1, all orbit values h j h_j h j for 0 ≤ j ≤ k − 1 0\le j\le k-1 0 ≤ j ≤ k − 1 and b j b_j b j for 0 ≤ j ≤ k − 2 0\le j\le k-2 0 ≤ j ≤ k − 2 are defined. Applying D k − 1 W h = 0 D_{k-1}^{W}h=0 D k − 1 W h = 0 to an arbitrary ( k − 2 ) (k-2) ( k − 2 ) -subset with j j j vertices of B B B now gives the full recurrence
( ∣ A ∣ − k + 2 + j ) h j + ( ∣ B ∣ − j ) h j + 1 = 0 , 0 ≤ j ≤ k − 2. (46) (|A|-k+2+j)h_j+(|B|-j)h_{j+1}=0,\qquad0\le j\le k-2. \tag*{(46)} ( ∣ A ∣ − k + 2 + j ) h j + ( ∣ B ∣ − j ) h j + 1 = 0 , 0 ≤ j ≤ k − 2. (46)
Similarly, D k − 2 W b = 0 D_{k-2}^{W}b=0 D k − 2 W b = 0 gives
( ∣ A ∣ − k + 3 + j ) b j + ( ∣ B ∣ − j ) b j + 1 = 0 , 0 ≤ j ≤ k − 3. (47) (|A|-k+3+j)b_j+(|B|-j)b_{j+1}=0,\qquad0\le j\le k-3. \tag*{(47)} ( ∣ A ∣ − k + 3 + j ) b j + ( ∣ B ∣ − j ) b j + 1 = 0 , 0 ≤ j ≤ k − 3. (47)
For 0 ≤ j ≤ k − 3 0\le j\le k-3 0 ≤ j ≤ k − 3 , Lemma 4.2 (iv) gives
b j + 1 − b j = ( p A − p B ) h j + 1 . (48) b_{j+1}-b_j=(p_A-p_B)h_{j+1}. \tag*{(48)} b j + 1 − b j = ( p A − p B ) h j + 1 . (48)
Lemma 6.2 (Complementary voltages). The two unequal nonterminal voltages p A , p B p_A,p_B p A , p B satisfy p A + p B = 1 p_A+p_B=1 p A + p B = 1 .
Proof. At j = 0 j=0 j = 0 , the recurrences (46) and (47) become ( ∣ A ∣ − k + 2 ) h 0 + ∣ B ∣ h 1 = 0 (|A|-k+2)h_0+|B|h_1=0 ( ∣ A ∣ − k + 2 ) h 0 + ∣ B ∣ h 1 = 0 and ( ∣ A ∣ − k + 3 ) b 0 + ∣ B ∣ b 1 = 0 (|A|-k+3)b_0+|B|b_1=0 ( ∣ A ∣ − k + 3 ) b 0 + ∣ B ∣ b 1 = 0 . Substituting b 1 = b 0 + ( p A − p B ) h 1 b_1=b_0+(p_A-p_B)h_1 b 1 = b 0 + ( p A − p B ) h 1 from (48) into the latter, and using L = N − k + 2 L=N-k+2 L = N − k + 2 , gives
h 0 = − ∣ B ∣ ∣ A ∣ − k + 2 h 1 , b 0 = − ∣ B ∣ ( p A − p B ) L + 1 h 1 . (49) h_0=-\frac{|B|}{|A|-k+2}h_1,\qquad b_0=-\frac{|B|(p_A-p_B)}{L+1}h_1. \tag*{(49)} h 0 = − ∣ A ∣ − k + 2 ∣ B ∣ h 1 , b 0 = − L + 1 ∣ B ∣ ( p A − p B ) h 1 . (49)
Since h ≠ 0 h\ne0 h = 0 , the recurrence (46) implies h 1 ≠ 0 h_1\ne0 h 1 = 0 .
Apply Lemma 4.2 (vi) to a set T T T consisting of k − 2 k-2 k − 2 vertices of A A A , and a distinguished vertex u ∈ A ∖ T u \in A \setminus T u ∈ A ∖ T . Then b T b_T b T and h u T h_{uT} h u T in Lemma 4.2 (vi) correspond respectively to b 0 b_0 b 0 and h 0 h_0 h 0 in the current setting. Substituting (49) gives
∣ B ∣ ∣ A ∣ k − 2 ( p A + p B − 1 ) h 1 = 0. \frac{|B|}{|A|^{k-2}}(p_A+p_B-1)h_1=0. ∣ A ∣ k − 2 ∣ B ∣ ( p A + p B − 1 ) h 1 = 0.
Since ∣ B ∣ > 0 |B|>0 ∣ B ∣ > 0 , L > 0 L>0 L > 0 , h 1 ≠ 0 h_1\ne0 h 1 = 0 , and ∣ A ∣ − k + 2 > 0 |A|-k+2>0 ∣ A ∣ − k + 2 > 0 by Lemma 6.1, deduce that p A + p B = 1 p_A+p_B=1 p A + p B = 1 . □ \square □
Relabel the two classes if necessary, and write p A = a p_A=a p A = a and p B = 1 − a p_B=1-a p B = 1 − a with 0 ≤ a < 1 2 0\le a<\frac{1}{2} 0 ≤ a < 2 1 .
Lemma 6.3 (No positive edges between voltage classes). If 0 ≤ a < 1 2 0\le a<\frac{1}{2} 0 ≤ a < 2 1 , then no positive edge joins A A A to B B B .
Proof. Suppose on the contrary that there exist u ∈ A u\in A u ∈ A and v ∈ B v\in B v ∈ B with c u v > 0 c_{uv}>0 c uv > 0 . First suppose a = 0 a=0 a = 0 , so that p A = 0 p_A=0 p A = 0 and p B = 1 p_B=1 p B = 1 . Then
∑ w ∈ V c u w [ p ( u ) − p ( w ) ] = c u v [ p ( u ) − p ( v ) ] + ∑ w ∈ V ∖ { v } c u w [ p ( u ) − p ( w ) ] ≤ − c u v < 0 \sum_{w\in V}c_{uw}[p(u)-p(w)]=c_{uv}[p(u)-p(v)]+\sum_{w\in V\setminus\{v\}}c_{uw}[p(u)-p(w)]\le-c_{uv}<0 w ∈ V ∑ c u w [ p ( u ) − p ( w )] = c uv [ p ( u ) − p ( v )] + w ∈ V ∖ { v } ∑ c u w [ p ( u ) − p ( w )] ≤ − c uv < 0
which contradicts the harmonicity (2) of the voltage p p p at u u u .
Now suppose 0 < a < 1 2 0<a<\frac{1}{2} 0 < a < 2 1 . By the definition of the voltage, δ f ( x , u ) = p u δ f ( x , y ) \delta_f(x,u)=p_u\delta_f(x,y) δ f ( x , u ) = p u δ f ( x , y ) and δ f ( x , v ) = p v δ f ( x , y ) \delta_f(x,v)=p_v\delta_f(x,y) δ f ( x , v ) = p v δ f ( x , y ) , while (25) gives δ f ( u , v ) = δ f ( x , y ) ( p v − p u ) \delta_f(u,v)=\delta_f(x,y)(p_v-p_u) δ f ( u , v ) = δ f ( x , y ) ( p v − p u ) . Hence δ f ( x , v ) = δ f ( x , u ) + δ f ( u , v ) \delta_f(x,v)=\delta_f(x,u)+\delta_f(u,v) δ f ( x , v ) = δ f ( x , u ) + δ f ( u , v ) . Apply Lemma 3.2 (iii) to the triple ( x , u , v ) (x,u,v) ( x , u , v ) and to the coordinate indexed by y R yR y R , where R ∈ ( W ∖ { u , v } k − 2 ) R\in\binom{W\setminus\{u,v\}}{k-2} R ∈ ( k − 2 W ∖ { u , v } ) . By Lemma 4.2 (ii), b R − f ( y u R ) = p u h u R b_R-f(yuR)=p_uh_{uR} b R − f ( y u R ) = p u h u R and b R − f ( y v R ) = p v h v R b_R-f(yvR)=p_vh_{vR} b R − f ( y v R ) = p v h v R . These are respectively the a f , u x v a^{xv}_{f,u} a f , u xv - and d f , u x v d^{xv}_{f,u} d f , u xv -coordinates in the equality criterion. Their proportionality factor is p u / p v p_u/p_v p u / p v , and p u > 0 p_u>0 p u > 0 ; thus p u h u R = ( p u / p v ) p v h v R p_uh_{uR}=(p_u/p_v)p_vh_{vR} p u h u R = ( p u / p v ) p v h v R , giving h u R = h v R h_{uR}=h_{vR} h u R = h v R . The transposition τ u v \tau_{uv} τ uv swaps u R uR u R and v R vR v R , and fixes the ( k − 1 ) (k-1) ( k − 1 ) -subsets which contain both or neither of u , v u,v u , v ; thus it fixes h h h . Together with S A × S B S_A\times S_B S A × S B , this cross-transposition generates S W S_W S W , so h h h is constant on ( k − 1 ) (k-1) ( k − 1 ) -subsets. Since D k − 1 W h = 0 D^W_{k-1}h=0 D k − 1 W h = 0 , that constant must be zero, contradicting h ≠ 0 h\ne0 h = 0 . □ \square □
Proposition 6.4 (Complementary-case graph geometry). If each nonterminal voltage value is a single δ f \delta_f δ f -class, then every connected component of G [ W ] G[W] G [ W ] is terminal-balanced, and its terminal-balance parameter belongs to { a , 1 − a } \{a,1-a\} { a , 1 − a } for some 0 ≤ a < 1 2 0\le a<\frac{1}{2} 0 ≤ a < 2 1 , with both values attained.
Proof. By Lemmas 6.2 and 6.3, the nonempty voltage classes A , B A,B A , B have respective values a , 1 − a a,1-a a , 1 − a and no positive edge joins them. Thus each component W i W_i W i of G [ W ] G[W] G [ W ] lies in one class, where p ≡ ρ i ∈ { a , 1 − a } p\equiv\rho_i\in\{a,1-a\} p ≡ ρ i ∈ { a , 1 − a } . Harmonicity at u ∈ W i u\in W_i u ∈ W i gives ρ i c x u = ( 1 − ρ i ) c y u \rho_i c_{xu}=(1-\rho_i)c_{yu} ρ i c xu = ( 1 − ρ i ) c y u , the terminal-balance relation. □ \square □
Split voltage levels: the midpoint case
We now suppose that two distinct zero-distance classes occur at the same nonterminal voltage. Choose u , v ∈ W u,v\in W u , v ∈ W with p u = p v = t p_u=p_v=t p u = p v = t and δ f ( u , v ) > 0 \delta_f(u,v)>0 δ f ( u , v ) > 0 . For R ∈ ( W ∖ { u , v } k − 2 ) R\in\binom{W\setminus\{u,v\}}{k-2} R ∈ ( k − 2 W ∖ { u , v } ) define J R : = h u R − h v R J_R:=h_{uR}-h_{vR} J R := h u R − h v R .
Lemma 6.5 (Same-voltage difference tensor). The tensor J J J satisfies:
(i) D k − 2 W ∖ { u , v } J = 0 D^{W\setminus\{u,v\}}_{k-2}J=0 D k − 2 W ∖ { u , v } J = 0 .
(ii) The distance identity δ f ( u , v ) 2 = ( n k ) − 1 [ t 2 + ( 1 − t ) 2 ] ∑ R ∈ ( W ∖ { u , v } k − 2 ) J R 2 \delta_f(u,v)^2=\binom{n}{k}^{-1}\left[t^2+(1-t)^2\right]\sum_{R\in\binom{W\setminus\{u,v\}}{k-2}}J_R^2 δ f ( u , v ) 2 = ( k n ) − 1 [ t 2 + ( 1 − t ) 2 ] ∑ R ∈ ( k − 2 W ∖ { u , v } ) J R 2 . In particular J ≠ 0 J\ne0 J = 0 .
(iii) For every R ∈ ( W ∖ { u , v } k − 2 ) R\in\binom{W\setminus\{u,v\}}{k-2} R ∈ ( k − 2 W ∖ { u , v } ) , ( 1 − 2 t ) J R = 0 (1-2t)J_R=0 ( 1 − 2 t ) J R = 0 ; hence t = 1 2 t=\frac{1}{2} t = 2 1 .
Proof. Item (i): Let Q ∈ ( W ∖ { u , v } k − 3 ) Q\in\binom{W\setminus\{u,v\}}{k-3} Q ∈ ( k − 3 W ∖ { u , v } ) . Applying Lemma 4.2 (i) to u Q uQ u Q and v Q vQ v Q gives h u v Q + ∑ z ≠ u , v Q h u z Q = 0 h_{uvQ}+\sum_{z\ne u,vQ}h_{uzQ}=0 h uv Q + ∑ z = u , v Q h u z Q = 0 and h u v Q + ∑ z ≠ u , v Q h v z Q = 0 h_{uvQ}+\sum_{z\ne u,vQ}h_{vzQ}=0 h uv Q + ∑ z = u , v Q h v z Q = 0 . Subtracting the two equations proves the claim.
Item (ii): Apply the coordinate formula (22) to the pair u , v u,v u , v , and separate the indexing sets T ∈ ( V ∖ { u , v } k − 1 ) T\in\binom{V\setminus\{u,v\}}{k-1} T ∈ ( k − 1 V ∖ { u , v } ) according to their intersection with { x , y } \{x,y\} { x , y } . If T T T contains neither terminal, then Lemma 4.2 (iii) gives
f ( u T ) − f ( v T ) = ( p v − p u ) ( f ( x T ) − f ( y T ) ) = 0 , f(uT)-f(vT)=(p_v-p_u)(f(xT)-f(yT))=0, f ( u T ) − f ( v T ) = ( p v − p u ) ( f ( x T ) − f ( y T )) = 0 , because p u = p v = t p_u=p_v=t p u = p v = t . If T = x y Q T=xyQ T = x y Q contains both terminals, then Lemma 4.2 (iv) gives f ( u T ) − f ( v T ) = b u Q − b v Q = 0 f(uT)-f(vT)=b_{uQ}-b_{vQ}=0 f ( u T ) − f ( v T ) = b u Q − b v Q = 0 for the same reason.
The remaining sets are T = x R T=xR T = x R or T = y R T=yR T = y R , with R ∈ ( W ∖ { u , v } k − 2 ) R\in\binom{W\setminus\{u,v\}}{k-2} R ∈ ( k − 2 W ∖ { u , v } ) . By Lemma 4.2 (ii), their differences are
f ( x u R ) − f ( x v R ) = ( 1 − t ) ( h u R − h v R ) = ( 1 − t ) J R , f(xuR)-f(xvR)=(1-t)(h_{uR}-h_{vR})=(1-t)J_R, f ( xu R ) − f ( xv R ) = ( 1 − t ) ( h u R − h v R ) = ( 1 − t ) J R , f ( y u R ) − f ( y v R ) = − t ( h u R − h v R ) = − t J R . f(yuR)-f(yvR)=-t(h_{uR}-h_{vR})=-tJ_R. f ( y u R ) − f ( y v R ) = − t ( h u R − h v R ) = − t J R . Each R R R occurs once in each of these two classes of T T T . Substituting all four classes of T T T into (22) proves the distance identity. Since δ f ( u , v ) > 0 \delta_f(u,v)>0 δ f ( u , v ) > 0 , it follows that $J\ne 0.
Item (iii): Fix R ∈ ( W ∖ { u , v } k − 2 ) R \in\binom{W\setminus\{u,v\}}{k-2} R ∈ ( k − 2 W ∖ { u , v } ) . Apply Lemma 4.2 (iii) to the same k k k -set u v R uvR uv R , first with the distinguished vertex u u u and then with v v v . Using Lemma 4.2 (ii) in each case, we obtain
f ( u v R ) = ( 1 − t ) f ( x v R ) + t f ( y v R ) = b R + ( 1 − 2 t ) h v R , f(uvR)=(1-t)f(xvR)+tf(yvR)=b_R+(1-2t)h_{vR}, f ( uv R ) = ( 1 − t ) f ( xv R ) + t f ( y v R ) = b R + ( 1 − 2 t ) h v R ,
f ( u v R ) = ( 1 − t ) f ( x u R ) + t f ( y u R ) = b R + ( 1 − 2 t ) h u R . f(uvR)=(1-t)f(xuR)+tf(yuR)=b_R+(1-2t)h_{uR}. f ( uv R ) = ( 1 − t ) f ( xu R ) + t f ( y u R ) = b R + ( 1 − 2 t ) h u R .
Subtracting the two equations gives ( 1 − 2 t ) J R = 0 (1-2t)J_R=0 ( 1 − 2 t ) J R = 0 for every R R R . Since J ≠ 0 J\ne0 J = 0 by item (ii), deduce that t = 1 2 t=\frac{1}{2} t = 2 1 .
Lemma 6.6 (No second voltage in the split-level case)
Lemma 6.6. If a nonterminal voltage level contains more than one zero-distance class, then p w = 1 2 p_w=\frac{1}{2} p w = 2 1 for every w ∈ W w\in W w ∈ W .
Proof. By Proposition 4.8, at most one other voltage value can occur. Suppose a second value s ≠ 1 2 s\ne\frac{1}{2} s = 2 1 occurs on exactly q s ≥ 1 q_s\ge1 q s ≥ 1 vertices. For R ∈ ( W ∖ { u , v } k − 2 ) R\in\binom{W\setminus\{u,v\}}{k-2} R ∈ ( k − 2 W ∖ { u , v } ) , let j ( R ) j(R) j ( R ) be the number of those q s q_s q s vertices contained in R R R . Apply Lemma 4.2 (vi) to T = R T=R T = R and a vertex u ∈ W ∖ R u\in W\setminus R u ∈ W ∖ R , and again to the same T T T and a different vertex v ∈ W ∖ R v\in W\setminus R v ∈ W ∖ R . This produces two separate equations. To simplify further, we note that p u = p v = 1 2 p_u=p_v=\frac{1}{2} p u = p v = 2 1 , so S W = N 2 + q s ( s − 1 2 ) S_W=\frac{N}{2}+q_s(s-\frac{1}{2}) S W = 2 N + q s ( s − 2 1 ) , S R = k − 2 2 + j ( R ) ( s − 1 2 ) S_R=\frac{k-2}{2}+j(R)(s-\frac{1}{2}) S R = 2 k − 2 + j ( R ) ( s − 2 1 ) , and
L − S W − L p u + S R = L − S W − L p v + S R = L 2 − S W + S R = ( q s − j ( R ) ) ( 1 2 − s ) , L-S_W-Lp_u+S_R=L-S_W-Lp_v+S_R=\frac{L}{2}-S_W+S_R=(q_s-j(R))\left(\frac{1}{2}-s\right), L − S W − L p u + S R = L − S W − L p v + S R = 2 L − S W + S R = ( q s − j ( R )) ( 2 1 − s ) ,
which is the common coefficient of h u R h_{uR} h u R and h v R h_{vR} h v R in the two equations. Subtracting these equations yields
( q s − j ( R ) ) ( 1 2 − s ) J R = 0 (50) (q_s-j(R))\left(\frac{1}{2}-s\right)J_R=0 \tag*{(50)} ( q s − j ( R )) ( 2 1 − s ) J R = 0 (50)
Thus J R ≠ 0 J_R\ne0 J R = 0 only if R R R contains all q s q_s q s vertices at voltage s s s .
If q s > k − 2 q_s>k-2 q s > k − 2 this is already impossible. Otherwise, choose R R R with J R ≠ 0 J_R\ne0 J R = 0 , remove one voltage-s s s vertex s 0 ∈ R s_0\in R s 0 ∈ R , and put Q = R ∖ { s 0 } Q=R\setminus\{s_0\} Q = R ∖ { s 0 } . Apply Lemma 6.5 (i) to the set Q Q Q :
( D k − 2 W ∖ { u , v } J ) ( Q ) = ∑ z ∈ ( W ∖ { u , v } ) ∖ Q J Q z = 0. \left(D_{k-2}^{W\setminus\{u,v\}}J\right)(Q)=\sum_{z\in(W\setminus\{u,v\})\setminus Q}J_{Qz}=0. ( D k − 2 W ∖ { u , v } J ) ( Q ) = z ∈ ( W ∖ { u , v }) ∖ Q ∑ J Q z = 0.
Only the term z = s 0 z=s_0 z = s 0 contains all q s q_s q s vertices at voltage s s s ; every other summand vanishes by (50) . Thus J R = 0 J_R=0 J R = 0 , a contradiction. □ \square □
Proposition 6.7 (Midpoint-case graph geometry)
Proposition 6.7. If a nonterminal voltage value contains more than one δ f \delta_f δ f -class, then G [ W ] G[W] G [ W ] has at least two connected components, and every component is terminal-balanced at 1 2 \frac{1}{2} 2 1 .
Proof. Choose two distinct zero-distance classes in the split voltage level. Lemma 6.6 implies that p w = 1 2 p_w=\frac{1}{2} p w = 2 1 for every w ∈ W w\in W w ∈ W . For distinct u , v ∈ W u,v\in W u , v ∈ W with c u v > 0 c_{uv}>0 c uv > 0 , (25) forces δ f ( u , v ) = 0 \delta_f(u,v)=0 δ f ( u , v ) = 0 . Hence a connected component of G [ W ] G[W] G [ W ] is contained in a single zero-distance class. In conjunction with the hypothesis, this implies that G [ W ] G[W] G [ W ] has q q q connected components with q ≥ 2 q\ge2 q ≥ 2 .
Since p ≡ 1 2 p\equiv\frac{1}{2} p ≡ 2 1 on W W W , harmonicity at each u ∈ W u\in W u ∈ W reduces to c x u = c y u c_{xu}=c_{yu} c xu = c y u . Thus every connected component is terminal-balanced at 1 2 \frac{1}{2} 2 1 , as claimed. □ \square □
Reduction to degree two
Theorem 6.8. (Reduction of higher-degree equality to degree two). Let G = ( V , c ) G=(V,c) G = ( V , c ) be a finite connected weighted graph, fix x ≠ y x\ne y x = y , and let 3 ≤ k ≤ ⌊ n 2 ⌋ 3\le k\le\left\lfloor\frac{n}{2}\right\rfloor 3 ≤ k ≤ ⌊ 2 n ⌋ . If there exists a nonzero f ∈ H k f\in\mathcal{H}_k f ∈ H k such that K x y ( k ) f = 0 K_{xy}^{(k)}f=0 K x y ( k ) f = 0 , then there exists a nonzero F ∈ H 2 F\in\mathcal{H}_2 F ∈ H 2 such that K x y ( 2 ) F = 0 K_{xy}^{(2)}F=0 K x y ( 2 ) F = 0 .
Proof. Let f ∈ H k ∖ { 0 } f\in\mathcal{H}_k\setminus\{0\} f ∈ H k ∖ { 0 } satisfy K x y ( k ) f = 0 K_{xy}^{(k)}f=0 K x y ( k ) f = 0 . Proposition 4.8 ensures at most two nonterminal voltage values. If some voltage level contains more than one δ f \delta_f δ f -class, Proposition 6.7 gives at least two connected components of G [ W ] G[W] G [ W ] , all terminal-balanced at 1 2 \frac{1}{2} 2 1 . Otherwise, Proposition 6.4 gives terminal-balanced components whose parameters are exactly { a , 1 − a } \{a,1-a\} { a , 1 − a } for some 0 ≤ a < 1 2 0\le a<\frac{1}{2} 0 ≤ a < 2 1 . Thus in either case the graph satisfies a nontrivial-kernel alternative of Theorem 5.6. That theorem supplies a nonzero F ∈ H 2 F\in\mathcal{H}_2 F ∈ H 2 satisfying K x y ( 2 ) F = 0 K_{xy}^{(2)}F=0 K x y ( 2 ) F = 0 . □ \square □
Transfer between particle sectors
To transfer the top-degree classification to an arbitrary particle sector, we record the up-map realization of Hoeffding degree and its compatibility with the exclusion residual K x y ( ℓ ) K_{xy}^{(\ell)} K x y ( ℓ ) .
For 0 ≤ r < n 0 \le r < n 0 ≤ r < n , define the one-step up operator
( U r g ) ( ξ ) : = ∑ z ∈ ξ g ( ξ ∖ { z } ) , ξ ∈ ( V r + 1 ) . (U_rg)(\xi) := \sum_{z \in\xi} g(\xi\setminus\{z\}), \qquad\xi\in\binom{V}{r+1}. ( U r g ) ( ξ ) := z ∈ ξ ∑ g ( ξ ∖ { z }) , ξ ∈ ( r + 1 V ) .
For 0 ≤ j < ℓ 0 \le j < \ell 0 ≤ j < ℓ , write U j → ℓ : = U ℓ − 1 ⋯ U j U_{j\to\ell} := U_{\ell-1}\cdots U_j U j → ℓ := U ℓ − 1 ⋯ U j , and set U ℓ → ℓ = I U_{\ell\to\ell}=I U ℓ → ℓ = I . For j ≤ min ( ℓ , n − ℓ ) j \le\min(\ell,n-\ell) j ≤ min ( ℓ , n − ℓ ) , the degree-j j j Hoeffding layer in the ℓ \ell ℓ -particle sector is U j → ℓ H j U_{j\to\ell}\mathcal H_j U j → ℓ H j .
Lemma 7.1 (Up-map intertwining). Let 1 ≤ j ≤ min ( ℓ , n − ℓ ) 1 \le j \le\min(\ell,n-\ell) 1 ≤ j ≤ min ( ℓ , n − ℓ ) . The map U j → ℓ U_{j\to\ell} U j → ℓ is injective on H j \mathcal H_j H j and intertwines the vertex-permutation actions on its domain and codomain. Consequently,
K x y ( ℓ ) U j → ℓ = U j → ℓ K x y ( j ) . (51) K_{xy}^{(\ell)}U_{j\to\ell}=U_{j\to\ell}K_{xy}^{(j)}. \tag*{(51)} K x y ( ℓ ) U j → ℓ = U j → ℓ K x y ( j ) . (51) Thus a vector in U j → ℓ H j U_{j\to\ell}\mathcal H_j U j → ℓ H j is an equality vector if and only if its unique preimage in H j \mathcal H_j H j is an equality vector.
Proof. Permutation equivariance is immediate from the definition of U r U_r U r , and therefore (51) holds. To prove injectivity, first note that for 1 ≤ r < n 1 \le r < n 1 ≤ r < n ,
D r + 1 U r − U r − 1 D r = ( n − 2 r ) I . (52) D_{r+1}U_r-U_{r-1}D_r=(n-2r)I. \tag*{(52)} D r + 1 U r − U r − 1 D r = ( n − 2 r ) I . (52)
Indeed, for an r r r -set T T T and a function g g g on r r r -sets,
( D r + 1 U r g ) ( T ) = ( n − r ) g ( T ) + ∑ w ∈ T ∑ z ∉ T g ( T ∖ { w } ∪ { z } ) , (D_{r+1}U_rg)(T)=(n-r)g(T)+\sum_{w\in T}\sum_{z\notin T}g\bigl(T\setminus\{w\}\cup\{z\}\bigr), ( D r + 1 U r g ) ( T ) = ( n − r ) g ( T ) + w ∈ T ∑ z ∈ / T ∑ g ( T ∖ { w } ∪ { z } ) ,
( U r − 1 D r g ) ( T ) = r g ( T ) + ∑ w ∈ T ∑ z ∉ T g ( T ∖ { w } ∪ { z } ) . (U_{r-1}D_rg)(T)=rg(T)+\sum_{w\in T}\sum_{z\notin T}g\bigl(T\setminus\{w\}\cup\{z\}\bigr). ( U r − 1 D r g ) ( T ) = r g ( T ) + w ∈ T ∑ z ∈ / T ∑ g ( T ∖ { w } ∪ { z } ) .
Subtracting the two equations gives (52) .
If g ∈ H j g \in\mathcal H_j g ∈ H j , set g 0 = g g_0=g g 0 = g and g s : = U j + s − 1 ⋯ U j g g_s:=U_{j+s-1}\cdots U_jg g s := U j + s − 1 ⋯ U j g for 1 ≤ s ≤ ℓ − j 1\le s\le\ell-j 1 ≤ s ≤ ℓ − j . Applying (52) inductively gives D j + s g s = s ( n − 2 j − s + 1 ) g s − 1 D_{j+s}g_s=s(n-2j-s+1)g_{s-1} D j + s g s = s ( n − 2 j − s + 1 ) g s − 1 . Note that the coefficient n − 2 j − s + 1 n-2j-s+1 n − 2 j − s + 1 is positive because ℓ ≤ n − j \ell\le n-j ℓ ≤ n − j . Hence g s = 0 g_s=0 g s = 0 implies g s − 1 = 0 g_{s-1}=0 g s − 1 = 0 , and inductively g = 0 g=0 g = 0 . In particular, U j → ℓ g = g ℓ − j = 0 U_{j\to\ell}g=g_{\ell-j}=0 U j → ℓ g = g ℓ − j = 0 implies g = 0 g=0 g = 0 , and thus U j → ℓ U_{j\to\ell} U j → ℓ is injective on H j \mathcal H_j H j .
If U j → ℓ g U_{j\to\ell}g U j → ℓ g lies in the kernel of K x y ( ℓ ) K_{xy}^{(\ell)} K x y ( ℓ ) , then (51) gives U j → ℓ ( K x y ( j ) g ) = 0 U_{j\to\ell}(K_{xy}^{(j)}g)=0 U j → ℓ ( K x y ( j ) g ) = 0 . The down map is equivariant under vertex permutations, as noted in the beginning of § 4 . Since K x y ( j ) K_{xy}^{(j)} K x y ( j ) is a linear combination of the identity and transpositions, this yields D j K x y ( j ) = K x y ( j − 1 ) D j D_jK_{xy}^{(j)}=K_{xy}^{(j-1)}D_j D j K x y ( j ) = K x y ( j − 1 ) D j . As D j g = 0 D_jg=0 D j g = 0 , we have D j K x y ( j ) g = 0 D_jK_{xy}^{(j)}g=0 D j K x y ( j ) g = 0 , hence K x y ( j ) g ∈ H j K_{xy}^{(j)}g\in\mathcal H_j K x y ( j ) g ∈ H j . The injectivity of U j → ℓ U_{j\to\ell} U j → ℓ on H j \mathcal H_j H j therefore gives K x y ( j ) g = 0 K_{xy}^{(j)}g=0 K x y ( j ) g = 0 . The reverse implication follows from (51) .
Lemma 7.2 (Down-map surjectivity). Let E ⊆ V E\subseteq V E ⊆ V be a finite set. For 1 ≤ r ≤ ∣ E ∣ 2 1\le r\le\frac{|E|}{2} 1 ≤ r ≤ 2 ∣ E ∣ , the down map D r E : R ( E r ) → R ( E r − 1 ) D_r^E:\mathbb R^{\binom{E}{r}}\to\mathbb R^{\binom{E}{r-1}} D r E : R ( r E ) → R ( r − 1 E ) is surjective.
Proof. For r = 1 r=1 r = 1 , D 1 E D_1^E D 1 E is the summation map onto functions on the unique 0 0 0 -subset, so it is surjective. Assume r ≥ 2 r\ge2 r ≥ 2 . Equip the subset-function spaces with the unnormalized counting inner products. For 0 ≤ s < ∣ E ∣ 0\le s<|E| 0 ≤ s < ∣ E ∣ , denote the one-step up map on E E E by U s E U_s^E U s E , where ( U s E g ) ( ξ ) = ∑ z ∈ ξ g ( ξ ∖ { z } ) (U_s^Eg)(\xi)=\sum_{z\in\xi}g(\xi\setminus\{z\}) ( U s E g ) ( ξ ) = ∑ z ∈ ξ g ( ξ ∖ { z }) for ξ ∈ ( E s + 1 ) \xi\in\binom{E}{s+1} ξ ∈ ( s + 1 E ) . Then D r E = ( U r − 1 E ) ∗ D_r^E=(U_{r-1}^E)^* D r E = ( U r − 1 E ) ∗ . The commutator calculation in (52) , with n n n replaced by ∣ E ∣ |E| ∣ E ∣ , gives
D r E U r − 1 E − U r − 2 E D r − 1 E = ( ∣ E ∣ − 2 r + 2 ) Id . D_r^EU_{r-1}^E-U_{r-2}^ED_{r-1}^E=(|E|-2r+2)\operatorname{Id}. D r E U r − 1 E − U r − 2 E D r − 1 E = ( ∣ E ∣ − 2 r + 2 ) Id .
If U r − 1 E g = 0 U_{r-1}^Eg=0 U r − 1 E g = 0 , taking the inner product with g g g yields
0 = ∥ D r − 1 E g ∥ c o u n t 2 + ( ∣ E ∣ − 2 r + 2 ) ∥ g ∥ c o u n t 2 . 0=\lVert D_{r-1}^Eg\rVert_{\mathrm{count}}^2+(|E|-2r+2)\lVert g\rVert_{\mathrm{count}}^2. 0 = ∥ D r − 1 E g ∥ count 2 + ( ∣ E ∣ − 2 r + 2 ) ∥ g ∥ count 2 .
The coefficient ∣ E ∣ − 2 r + 2 |E|-2r+2 ∣ E ∣ − 2 r + 2 is positive for r ≤ ∣ E ∣ 2 r\le\frac{|E|}{2} r ≤ 2 ∣ E ∣ , so g = 0 g=0 g = 0 . Thus U r − 1 E U_{r-1}^E U r − 1 E is injective, whence its adjoint D r E D_r^E D r E is surjective.
Lemma 7.3 (Hoeffding–Specht decomposition across particle sectors). For 0 ≤ j ≤ ⌊ n / 2 ⌋ 0\le j\le\lfloor n/2\rfloor 0 ≤ j ≤ ⌊ n /2 ⌋ , the top-degree space H j \mathcal H_j H j satisfies
H j ≅ S ( n − j , j ) (53) \mathcal H_j \cong\mathcal S^{(n-j,j)} \tag*{(53)} H j ≅ S ( n − j , j ) (53)
as an S V \mathbb{S}_V S V -representation. Moreover, for 1 ≤ ℓ ≤ n − 1 1 \le\ell\le n-1 1 ≤ ℓ ≤ n − 1 , put d : = min ( ℓ , n − ℓ ) d := \min(\ell,n-\ell) d := min ( ℓ , n − ℓ ) . Then the decomposition
R Ω ℓ = ⨁ j = 0 d U j → ℓ H j (54) \mathbb{R}^{\Omega^\ell} = \bigoplus_{j=0}^{d} U_{j\to\ell}\mathcal{H}_j \tag*{(54)} R Ω ℓ = j = 0 ⨁ d U j → ℓ H j (54)
is orthogonal.
Proof. Recall (8) . For j ≥ 1 j \ge1 j ≥ 1 , the down map D j D_j D j is S V \mathbb{S}_V S V -equivariant and surjective by Lemma 7.2 . The target contains exactly the summands with 0 ≤ i ≤ j − 1 0 \le i \le j-1 0 ≤ i ≤ j − 1 . Since each summand S ( n − i , i ) S^{(n-i,i)} S ( n − i , i ) occurs with multiplicity one, surjectivity forces D j D_j D j to be nonzero, hence an isomorphism, on each summand shared by the source and the target. Therefore ker D j \ker D_j ker D j is precisely the remaining summand S ( n − j , j ) S^{(n-j,j)} S ( n − j , j ) , proving (53) . The case j = 0 j=0 j = 0 is the constant representation.
For 1 ≤ j ≤ d 1 \le j \le d 1 ≤ j ≤ d , Lemma 7.1 shows that U j → ℓ H j U_{j\to\ell}\mathcal{H}_j U j → ℓ H j is a nonzero invariant copy of S ( n − j , j ) S^{(n-j,j)} S ( n − j , j ) ; for j = 0 j=0 j = 0 it is the constant line. Young’s rule for the ℓ \ell ℓ -subset module, together with the complement identification Ω ℓ ≅ Ω n − ℓ \Omega^\ell\cong\Omega^{n-\ell} Ω ℓ ≅ Ω n − ℓ when ℓ > n 2 \ell> \frac{n}{2} ℓ > 2 n , shows that R Ω ℓ \mathbb{R}^{\Omega^\ell} R Ω ℓ contains exactly one copy of each S ( n − j , j ) S^{(n-j,j)} S ( n − j , j ) , 0 ≤ j ≤ d 0 \le j \le d 0 ≤ j ≤ d , and no others. Hence the displayed sum is exhaustive. The permutation action is orthogonal, and inequivalent irreducible summands are orthogonal, which proves (54) . □
Corollary 7.4 (Equality above degree one if and only if quadratic equality). Fix G G G , x x x , y y y and an ℓ \ell ℓ -particle sector with d : = min ( ℓ , n − ℓ ) ≥ 2 d := \min(\ell,n-\ell) \ge2 d := min ( ℓ , n − ℓ ) ≥ 2 . Then
ker K x y ( ℓ ) ∩ ( ⨁ j = 2 d U j → ℓ H j ) ≠ { 0 } ⟺ ker K x y ( ℓ ) ∩ U 2 → ℓ H 2 ≠ { 0 } . \ker K_{xy}^{(\ell)} \cap\left(\bigoplus_{j=2}^{d} U_{j\to\ell}\mathcal{H}_j\right) \ne\{0\}
\quad\Longleftrightarrow\quad
\ker K_{xy}^{(\ell)} \cap U_{2\to\ell}\mathcal{H}_2 \ne\{0\}. ker K x y ( ℓ ) ∩ ( j = 2 ⨁ d U j → ℓ H j ) = { 0 } ⟺ ker K x y ( ℓ ) ∩ U 2 → ℓ H 2 = { 0 } . Proof. By Lemmas 7.1 and 7.3 , each U j → ℓ H j U_{j\to\ell}\mathcal{H}_j U j → ℓ H j is preserved by K x y ( ℓ ) K_{xy}^{(\ell)} K x y ( ℓ ) . Thus a nonzero vector in the intersection on the left has a nonzero component g ∈ ker K x y ( ℓ ) ∩ U j → ℓ H j g \in\ker K_{xy}^{(\ell)} \cap U_{j\to\ell}\mathcal{H}_j g ∈ ker K x y ( ℓ ) ∩ U j → ℓ H j for some 2 ≤ j ≤ d 2 \le j \le d 2 ≤ j ≤ d . If j = 2 j=2 j = 2 , the conclusion follows immediately. If j ≥ 3 j \ge3 j ≥ 3 , write g = U j → ℓ h g=U_{j\to\ell}h g = U j → ℓ h for the unique h ∈ H j h \in\mathcal{H}_j h ∈ H j . By Lemma 7.1 , h h h is a nonzero equality vector. Theorem 6.8 supplies a nonzero F ∈ H 2 F \in\mathcal{H}_2 F ∈ H 2 with K x y ( 2 ) F = 0 K_{xy}^{(2)}F=0 K x y ( 2 ) F = 0 , and Lemma 7.1 shows that U 2 → ℓ F U_{2\to\ell}F U 2 → ℓ F is a nonzero vector in the right-hand intersection. The reverse implication follows from the inclusion of the j = 2 j=2 j = 2 summand in the direct sum. □
Graph criterion for equality beyond degree one.
Theorem 7.5 (Equality beyond degree one). Fix G G G , x x x , y y y and an ℓ \ell ℓ -particle sector with d : = min ( ℓ , n − ℓ ) ≥ 2 d := \min(\ell,n-\ell) \ge2 d := min ( ℓ , n − ℓ ) ≥ 2 . Put W : = V ∖ { x , y } W := V \setminus\{x,y\} W := V ∖ { x , y } , and let W 1 , … , W q W_1,\ldots,W_q W 1 , … , W q be the connected components of G [ W ] G[W] G [ W ] . Then
ker K x y ( ℓ ) ∩ ( ⨁ j = 2 d U j → ℓ H j ) ≠ { 0 } (55) \ker K_{xy}^{(\ell)} \cap\left(\bigoplus_{j=2}^{d} U_{j\to\ell}\mathcal{H}_j\right) \ne\{0\} \tag*{(55)} ker K x y ( ℓ ) ∩ ( j = 2 ⨁ d U j → ℓ H j ) = { 0 } (55) if and only if either
(a) q ≥ 2 q \ge2 q ≥ 2 and every W i W_i W i is terminal-balanced at 1 2 \frac{1}{2} 2 1 ; or
(b) every W i W_i W i is terminal-balanced, and the terminal-balance parameters are exactly { a , 1 − a } \{a,1-a\} { a , 1 − a } for some 0 ≤ a < 1 2 0 \le a < \frac{1}{2} 0 ≤ a < 2 1 , with both values occurring.
Moreover, the quadratic component in this sector satisfies
dim ( ker K x y ( ℓ ) ∩ U 2 → ℓ H 2 ) = dim ker ( K x y ( 2 ) ∣ H 2 ) . \dim\left(\ker K_{xy}^{(\ell)} \cap U_{2\to\ell}\mathcal{H}_2\right)
=
\dim\ker\left(K_{xy}^{(2)}\big|_{\mathcal{H}_2}\right). dim ( ker K x y ( ℓ ) ∩ U 2 → ℓ H 2 ) = dim ker ( K x y ( 2 ) H 2 ) . The common dimension is given by Theorem 5.6.
Proof. By Lemma 7.1 , the restriction of U 2 → ℓ U_{2\to\ell} U 2 → ℓ to H 2 \mathcal{H}_2 H 2 is injective and intertwines the residuals. Consequently, ker K x y ( ℓ ) ∩ U 2 → ℓ H 2 = U 2 → ℓ ker ( K x y ( 2 ) ∣ H 2 ) \ker K_{xy}^{(\ell)} \cap U_{2\to\ell}\mathcal{H}_2 = U_{2\to\ell}\ker\left(K_{xy}^{(2)}\big|_{\mathcal{H}_2}\right) ker K x y ( ℓ ) ∩ U 2 → ℓ H 2 = U 2 → ℓ ker ( K x y ( 2 ) H 2 ) . By Corollary 7.4, the intersection in (55) is nonzero exactly when ker ( K x y ( 2 ) ∣ H 2 ) ≠ { 0 } \ker\left(K_{xy}^{(2)}\big|_{\mathcal{H}_2}\right) \ne\{0\} ker ( K x y ( 2 ) H 2 ) = { 0 } . The graph alternatives are precisely those in Theorem 5.6, which also supplies the asserted dimension. □
Examples: Weighted 4-cycles and complete bipartite graphs
The first examples with equality beyond degree one occur on four vertices. The next proposition records the complete weighted 4-cycle family with opposite terminals.
Proposition 7.6 (Weighted 4-cycles with opposite terminals). Let G G G be the 4-cycle x − u − y − v − x x-u-y-v-x x − u − y − v − x with positive conductances c x u = α c_{xu}=\alpha c xu = α , c u y = β c_{uy}=\beta c u y = β , c y v = γ c_{yv}=\gamma c y v = γ , and c v x = δ c_{vx}=\delta c v x = δ . Then G G G supports equality beyond degree one for the terminal pair x , y x,y x , y if and only if β γ = α δ \beta\gamma=\alpha\delta β γ = α δ , in which case the quadratic equality kernel is one-dimensional.
Proof. Here W = { u , v } W=\{u,v\} W = { u , v } and G [ W ] G[W] G [ W ] has the two singleton components { u } \{u\} { u } and { v } \{v\} { v } . Their harmonic voltages are p ( u ) = β / ( α + β ) p(u)=\beta/(\alpha+\beta) p ( u ) = β / ( α + β ) and p ( v ) = γ / ( γ + δ ) p(v)=\gamma/(\gamma+\delta) p ( v ) = γ / ( γ + δ ) . By Theorem 7.5, equality beyond degree one occurs exactly when these two terminal-balance parameters are complementary: p ( u ) + p ( v ) = 1 p(u)+p(v)=1 p ( u ) + p ( v ) = 1 ; in particular this subsumes the midpoint case. This constraint is equivalent to β γ = α δ \beta\gamma=\alpha\delta β γ = α δ . Since there are exactly two components, (45) gives a quadratic equality kernel of dimension 1. □
The uniformly weighted 4-cycle is just one possible member of the equality family. For a non-uniformly weighted example, consider ( α , β , γ , δ ) = ( 2 , 1 , 2 , 1 ) (\alpha,\beta,\gamma,\delta)=(2,1,2,1) ( α , β , γ , δ ) = ( 2 , 1 , 2 , 1 ) , which gives harmonic voltages p ( u ) = 1 3 p(u)=\frac{1}{3} p ( u ) = 3 1 and p ( v ) = 2 3 p(v)=\frac{2}{3} p ( v ) = 3 2 .
By contrast, if the terminals of a 4-cycle are adjacent, i.e., x − y − u − v − x x-y-u-v-x x − y − u − v − x , then G [ W ] G[W] G [ W ] is connected, so neither alternative in Theorem 7.5 can hold. The same observation shows that adding a positive edge between u u u and v v v to an equality 4-cycle with opposite terminals destroys equality beyond degree one.
Remark 7.7 (Connection to the second eigenspace of L G I P L_G^{\mathrm{IP}} L G IP ). Among all weighted 4-cycles, only the uniformly weighted cycle exhibits the exceptional second-eigenspace phenomenon described in Theorem 2.4 of [2 ] .
A useful larger family is the weighted complete bipartite graph K 2 , q K_{2,q} K 2 , q , where the terminals x , y x,y x , y lie in one side of the bipartition, and the nonterminal vertices u 1 , … , u q u_1,\ldots,u_q u 1 , … , u q lie in the opposite side. Write a i : = c x u i > 0 a_i:=c_{xu_i}>0 a i := c x u i > 0 , b i : = c y u i > 0 b_i:=c_{yu_i}>0 b i := c y u i > 0 , and ρ i : = b i / ( a i + b i ) \rho_i:=b_i/(a_i+b_i) ρ i := b i / ( a i + b i ) . Each { u i } \{u_i\} { u i } is a connected component of G [ W ] G[W] G [ W ] , with terminal-balance parameter ρ i \rho_i ρ i . Theorem 7.5 gives the complete alternative: equality beyond degree one occurs either when every a i = b i a_i=b_i a i = b i and q ≥ 2 q\ge2 q ≥ 2 , in which case the quadratic kernel has dimension q − 1 q-1 q − 1 ; or when the set of parameters ρ i \rho_i ρ i is exactly { a , 1 − a } \{a,1-a\} { a , 1 − a } for some 0 ≤ a < 1 2 0\le a<\frac{1}{2} 0 ≤ a < 2 1 , with both values occurring, in which case the quadratic kernel is one-dimensional. Of course, when q = 2 q=2 q = 2 we recover the weighted 4-cycles in Proposition 7.6.
Higher-degree kernels and sectorwise classification
We now determine the equality kernel in each Hoeffding degree. For 1 ≤ k ≤ ⌊ n 2 ⌋ 1\le k\le\left\lfloor\frac{n}{2}\right\rfloor 1 ≤ k ≤ ⌊ 2 n ⌋ set E k : = ker ( K x y ( k ) ∣ H k ) \mathcal{E}_k:=\ker\left(\mathcal{K}_{xy}^{(k)}\big|_{\mathcal{H}_k}\right) E k := ker ( K x y ( k ) H k ) . The k = 1 k=1 k = 1 case is treated in Proposition 8.5 below, while the k = 2 k=2 k = 2 case is settled by Theorem 5.6. For k ≥ 3 k\ge3 k ≥ 3 , if E k ≠ { 0 } \mathcal{E}_k\ne\{0\} E k = { 0 } , apply Theorem 7.5 in the k k k -particle sector: then ℓ = d = k \ell=d=k ℓ = d = k and U k → k = I U_{k\to k}=I U k → k = I , so the graph must satisfy one of the midpoint or complementary voltage alternatives. By Lemma 4.4 and Corollary 4.5, their higher-degree kernels can be constructed from compatible interface data, with equality reduced to the positive-edge conditions within W W W . In the midpoint case, these data form an invariant down-map kernel, while in the complementary case they obey an explicit orbit recurrence. The resulting kernels are assembled into the particle-sector and interchange-process classifications.
For a subgroup Γ ≤ S W \Gamma\le\mathfrak{S}_W Γ ≤ S W , where W = V ∖ { x , y } W=V\setminus\{x,y\} W = V ∖ { x , y } , and a linear space U \mathcal{U} U of functions on subsets of W W W , write
U Γ : = { g ∈ U : g ( γ ξ ) = g ( ξ ) for every γ ∈ Γ and every admissible ξ } \mathcal{U}^{\Gamma}:=\{g\in\mathcal{U}:g(\gamma\xi)=g(\xi)\text{ for every }\gamma\in\Gamma\text{ and every admissible }\xi\} U Γ := { g ∈ U : g ( γ ξ ) = g ( ξ ) for every γ ∈ Γ and every admissible ξ }
for the subspace of Γ \Gamma Γ -invariant functions.
Lemma 8.1 (Dimension of the invariant down-map kernel). Let Γ \Gamma Γ be a permutation group acting on W W W , and β s \beta_s β s denote the number of Γ \Gamma Γ -orbits on s s s -subsets of W W W . If 1 ≤ r ≤ N 2 1\le r\le\frac{N}{2} 1 ≤ r ≤ 2 N , then
dim ( ker D r W ) Γ = β r − β r − 1 . \dim\left(\ker D_r^W\right)^\Gamma=\beta_r-\beta_{r-1}. dim ( ker D r W ) Γ = β r − β r − 1 .
Proof. The space of Γ \Gamma Γ -invariant functions on s s s -subsets of W W W has dimension β s \beta_s β s , since such a function is determined by its values on the Γ \Gamma Γ -orbits. By Lemma 7.2, D r W D_r^W D r W is surjective for r ≤ N 2 r\le\frac{N}{2} r ≤ 2 N . Let v v v be Γ \Gamma Γ -invariant on ( r − 1 ) (r-1) ( r − 1 ) -subsets, and choose g g g on r r r -subsets with D r W g = v D_r^Wg=v D r W g = v . Its Γ \Gamma Γ -average g ‾ ( ξ ) : = 1 ∣ Γ ∣ ∑ γ ∈ Γ g ( γ − 1 ξ ) \overline{g}(\xi):=\frac{1}{|\Gamma|}\sum_{\gamma\in\Gamma}g(\gamma^{-1}\xi) g ( ξ ) := ∣Γ∣ 1 ∑ γ ∈ Γ g ( γ − 1 ξ ) is Γ \Gamma Γ -invariant, and permutation-equivariance gives D r W g ‾ = 1 ∣ Γ ∣ ∑ γ ∈ Γ ( D r W g ) ∘ γ − 1 = v D_r^W\overline{g}=\frac{1}{|\Gamma|}\sum_{\gamma\in\Gamma}(D_r^Wg)\circ\gamma^{-1}=v D r W g = ∣Γ∣ 1 ∑ γ ∈ Γ ( D r W g ) ∘ γ − 1 = v . Thus the down map D r W D_r^W D r W is surjective between the invariant function spaces, and its kernel there is ( ker D r W ) Γ (\ker D_r^W)^\Gamma ( ker D r W ) Γ . The rank-nullity theorem yields (8.1). □
Midpoint case
Let W 1 , … , W q W_1,\ldots,W_q W 1 , … , W q be the connected components of G [ W ] G[W] G [ W ] , and set Γ : = S W 1 × ⋯ × S W q \Gamma:= \mathfrak{S}_{W_1}\times\cdots\times\mathfrak{S}_{W_q} Γ := S W 1 × ⋯ × S W q . Let β s \beta_s β s count the Γ \Gamma Γ -orbits on s s s -subsets of W W W .
Theorem 8.2 (Higher-degree midpoint kernel). Assume the midpoint voltage configuration : the harmonic x x x –y y y voltage p p p equals 1 2 \frac{1}{2} 2 1 on W W W . For 3 ≤ k ≤ ⌊ n 2 ⌋ 3\leq k\leq\left\lfloor\frac{n}{2}\right\rfloor 3 ≤ k ≤ ⌊ 2 n ⌋ , the map
H k − 1 ( W ) Γ ∋ h ↦ f h ∈ R ( V k ) , f h ( ζ ) = { 1 2 h ξ , ζ = x ξ , ξ ∈ ( W k − 1 ) , − 1 2 h ξ , ζ = y ξ , ξ ∈ ( W k − 1 ) , 0 , otherwise , (56) \mathcal{H}_{k-1}(W)^\Gamma\ni h\mapsto f_h\in\mathbb{R}^{\binom{V}{k}},\qquad
f_h(\zeta)=
\begin{cases}
\frac{1}{2}h_\xi,&\zeta=x\xi,\ \xi\in\binom{W}{k-1},\\
-\frac{1}{2}h_\xi,&\zeta=y\xi,\ \xi\in\binom{W}{k-1},\\
0,&\text{otherwise},
\end{cases} \tag*{(56)} H k − 1 ( W ) Γ ∋ h ↦ f h ∈ R ( k V ) , f h ( ζ ) = ⎩ ⎨ ⎧ 2 1 h ξ , − 2 1 h ξ , 0 , ζ = x ξ , ξ ∈ ( k − 1 W ) , ζ = y ξ , ξ ∈ ( k − 1 W ) , otherwise , (56) defines a linear isomorphism H k − 1 ( W ) Γ ≅ E k \mathcal{H}_{k-1}(W)^\Gamma\cong\mathcal{E}_k H k − 1 ( W ) Γ ≅ E k . Consequently,
dim E k = β k − 1 − β k − 2 . (57) \dim\mathcal{E}_k=\beta_{k-1}-\beta_{k-2}. \tag*{(57)} dim E k = β k − 1 − β k − 2 . (57)
Proof. Let f ∈ E k f\in\mathcal{E}_k f ∈ E k be nonzero, and let h h h and b b b be its interface functions from (4.1). By the midpoint hypothesis, p ≡ 1 2 p\equiv\frac{1}{2} p ≡ 2 1 on W W W , so S W = N 2 S_W=\frac{N}{2} S W = 2 N and S T = k − 2 2 S_T=\frac{k-2}{2} S T = 2 k − 2 . With L = N − k + 2 L=N-k+2 L = N − k + 2 , the coefficient of h u T h_{uT} h u T in the master identity Lemma 4.2(vi) is 1 2 ( L − N + k − 2 ) = 0 \frac{1}{2}(L-N+k-2)=0 2 1 ( L − N + k − 2 ) = 0 . Therefore ( L + 1 ) b T = 0 (L+1)b_T=0 ( L + 1 ) b T = 0 for every T T T , hence b = 0 b=0 b = 0 . Using Lemma 4.2(ii)–(iii) now gives exactly (56) .
If c u v > 0 c_{uv}>0 c uv > 0 with u , v ∈ W u,v\in W u , v ∈ W , then (25) and p u = p v = 1 2 p_u=p_v=\frac{1}{2} p u = p v = 2 1 give δ f ( u , v ) = 0 \delta_f(u,v)=0 δ f ( u , v ) = 0 , hence τ u v f = f \tau_{uv}f=f τ uv f = f . Since τ u v \tau_{uv} τ uv fixes x x x and y y y , it also fixes the interface function:
h τ u v ξ = f ( x τ u v ξ ) − f ( y τ u v ξ ) = f ( x ξ ) − f ( y ξ ) = h ξ . h_{\tau_{uv}\xi}=f(x\tau_{uv}\xi)-f(y\tau_{uv}\xi)=f(x\xi)-f(y\xi)=h_\xi. h τ uv ξ = f ( x τ uv ξ ) − f ( y τ uv ξ ) = f ( x ξ ) − f ( y ξ ) = h ξ .
The positive-edge transpositions in each connected component W i W_i W i generate S W i \mathfrak{S}_{W_i} S W i , so h h h is Γ \Gamma Γ -invariant. The down-map identity D k − 1 W h = 0 D^W_{k-1}h=0 D k − 1 W h = 0 in Lemma 4.2(i) then gives h ∈ H k − 1 ( W ) Γ h\in\mathcal{H}_{k-1}(W)^\Gamma h ∈ H k − 1 ( W ) Γ . Thus every f ∈ E k f\in\mathcal{E}_k f ∈ E k has the prescribed form (56) for some h ∈ H k − 1 ( W ) Γ h\in\mathcal{H}_{k-1}(W)^\Gamma h ∈ H k − 1 ( W ) Γ .
Conversely, take h ∈ H k − 1 ( W ) Γ h\in\mathcal{H}_{k-1}(W)^\Gamma h ∈ H k − 1 ( W ) Γ and set b = 0 b=0 b = 0 , as required by the midpoint master identity (see the first paragraph of this proof). If h = 0 h=0 h = 0 , then f h = 0 f_h=0 f h = 0 , and the assertion is immediate. Hence assume h ≠ 0 h\ne0 h = 0 . With the harmonic voltage p ≡ 1 2 p\equiv\frac{1}{2} p ≡ 2 1 fixed by the hypothesis, we verify the compatibility conditions of Lemma 4.4. Lemma 4.2(i) holds because h ∈ H k − 1 ( W ) h\in\mathcal{H}_{k-1}(W) h ∈ H k − 1 ( W ) and b = 0 b=0 b = 0 . In Lemma 4.2(iv), both sides vanish because b = 0 b=0 b = 0 and all nonterminal voltages are equal. In Lemma 4.2(v), the factor 1 − p u − p v 1-p_u-p_v 1 − p u − p v vanishes. Lemma 4.2(vi) holds because its h u T h_{uT} h u T coefficient vanishes, as computed above. Thus Lemma 4.4 produces f h ∈ H k f_h\in\mathcal{H}_k f h ∈ H k with precisely the values in (56) . By Corollary 4.5, it remains only to check positive edges within W W W . On such an edge { u , v } \{u,v\} { u , v } inside W i W_i W i , Γ \Gamma Γ -invariance of h h h and the formula (56) for f h f_h f h give τ u v f h = f h \tau_{uv}f_h=f_h τ uv f h = f h . Hence δ f h ( u , v ) = 0 \delta_{f_h}(u,v)=0 δ f h ( u , v ) = 0 , matching p u = p v p_u=p_v p u = p v , and thus f h ∈ E k f_h\in\mathcal{E}_k f h ∈ E k . The map is therefore surjective; it is injective since f h = 0 f_h=0 f h = 0 implies h = 0 h=0 h = 0 by (56) .
The orbit count β s \beta_s β s is the number of tuples ( j 1 , … , j q ) (j_1,\ldots,j_q) ( j 1 , … , j q ) with 0 ≤ j i ≤ ∣ W i ∣ 0\leq j_i\leq|W_i| 0 ≤ j i ≤ ∣ W i ∣ and ∑ i j i = s \sum_i j_i=s ∑ i j i = s . Since k − 1 ≤ N 2 k-1\leq\frac{N}{2} k − 1 ≤ 2 N , Lemma 8.1 gives (57) . □
Complementary case
Theorem 8.3 (Higher-degree complementary kernel). Assume the complementary voltage configuration : the harmonic x x x –y y y voltage p p p is constant on each connected component of G [ W ] G[W] G [ W ] and takes exactly two values a a a and 1 − a 1-a 1 − a on W W W , for some 0 ≤ a < 1 2 0\leq a<\frac{1}{2} 0 ≤ a < 2 1 . Let A : = { u ∈ W : p u = a } A:=\{u\in W:p_u=a\} A := { u ∈ W : p u = a } and B : = { u ∈ W : p u = 1 − a } B:=\{u\in W:p_u=1-a\} B := { u ∈ W : p u = 1 − a } . For 3 ≤ k ≤ ⌊ n 2 ⌋ 3\leq k\leq\left\lfloor\frac{n}{2}\right\rfloor 3 ≤ k ≤ ⌊ 2 n ⌋ , we have
dim E k = { 1 , k − 1 ≤ min { ∣ A ∣ , ∣ B ∣ } , 0 , k − 1 > min { ∣ A ∣ , ∣ B ∣ } . \dim\mathcal{E}_k=
\begin{cases}
1,&k-1\leq\min\{|A|,|B|\},\\
0,&k-1>\min\{|A|,|B|\}.
\end{cases} dim E k = { 1 , 0 , k − 1 ≤ min { ∣ A ∣ , ∣ B ∣ } , k − 1 > min { ∣ A ∣ , ∣ B ∣ } . When dim E k = 1 \dim\mathcal{E}_k=1 dim E k = 1 , E k \mathcal{E}_k E k is spanned by the function f f f reconstructed from the S A × S B \mathfrak{S}_A\times\mathfrak{S}_B S A × S B -invariant interface data constructed in the proof .
Proof. Let f ∈ E k f\in\mathcal{E}_k f ∈ E k be nonzero. If two vertices in A A A had positive δ f \delta_f δ f -distance, then one voltage level would contain more than one zero-distance class, and Lemma 6.6 would force every nonterminal voltage to equal 1 2 \frac{1}{2} 2 1 , a contradiction. Thus δ f ( u , v ) = 0 \delta_f(u,v)=0 δ f ( u , v ) = 0 for every u , v ∈ A u,v\in A u , v ∈ A , and similarly for every u , v ∈ B u,v\in B u , v ∈ B . Since δ f ( u , v ) 2 = 1 2 ∥ f − τ u v f ∥ k 2 \delta_f(u,v)^2=\frac{1}{2}\lVert f-\tau_{uv}f\rVert_k^2 δ f ( u , v ) 2 = 2 1 ∥ f − τ uv f ∥ k 2 , every such transposition fixes f f f . Hence f f f , and its corresponding interface functions h h h and b b b defined in (4.1), are invariant under S A × S B \mathfrak{S}_A\times\mathfrak{S}_B S A × S B .
Applying Lemma 6.1 at degree k k k gives ∣ A ∣ , ∣ B ∣ ≥ k − 1 |A|,|B|\geq k-1 ∣ A ∣ , ∣ B ∣ ≥ k − 1 for every nonzero equality vector. Consequently, if k − 1 > min { ∣ A ∣ , ∣ B ∣ } k-1>\min\{|A|,|B|\} k − 1 > min { ∣ A ∣ , ∣ B ∣ } , the kernel is trivial. So assume from now on that ∣ A ∣ , ∣ B ∣ ≥ k − 1 |A|,|B|\geq k-1 ∣ A ∣ , ∣ B ∣ ≥ k − 1 . Write h j h_j h j for the value of h h h on a ( k − 1 ) (k-1) ( k − 1 ) -subset containing j j j points of B B B . The down-map identity D k − 1 W h = 0 D^W_{k-1}h=0 D k − 1 W h = 0 from Lemma 4.2(i) gives (46) . Both coefficients in (46) are positive for 0 ≤ j ≤ k − 2 0 \le j \le k-2 0 ≤ j ≤ k − 2 , so the orbit values of h h h are determined by h 0 h_0 h 0 . Let b j b_j b j be the corresponding orbit value of b b b . For a ( k − 2 ) (k-2) ( k − 2 ) -subset T T T with j j j points of B B B , choose u ∈ A ∖ T u \in A \setminus T u ∈ A ∖ T . The master identity Lemma 4.2 (vi) then determines b j b_j b j uniquely from h j h_j h j , since N − k + 3 > 0 N-k+3 > 0 N − k + 3 > 0 . Since p p p is fixed, the uniqueness in Lemma 4.4 (i) shows that h 0 h_0 h 0 determines f f f ; hence dim E k ≤ 1 \dim\mathcal{E}_k \le1 dim E k ≤ 1 . Moreover, f ≠ 0 f \ne0 f = 0 implies h ≠ 0 h \ne0 h = 0 by Corollary 4.3, hence h 0 ≠ 0 h_0 \ne0 h 0 = 0 . Taking T ⊂ A T \subset A T ⊂ A and u ∈ A ∖ T u \in A \setminus T u ∈ A ∖ T in Lemma 4.2 (vi) gives ( N − k + 3 ) b 0 = ( 2 a − 1 ) ( ∣ A ∣ − k + 2 ) h 0 ≠ 0 (N-k+3)b_0=(2a-1)(|A|-k+2)h_0 \ne0 ( N − k + 3 ) b 0 = ( 2 a − 1 ) ( ∣ A ∣ − k + 2 ) h 0 = 0 . Thus every nonzero equality vector has b ≠ 0 b \ne0 b = 0 .
It suffices to prove existence of a nonzero vector f ∈ E k f \in\mathcal{E}_k f ∈ E k . Put L : = N − k + 2 L := N-k+2 L := N − k + 2 , μ : = ∣ A ∣ − k + 2 \mu:= |A|-k+2 μ := ∣ A ∣ − k + 2 , and η : = 2 a − 1 \eta:= 2a-1 η := 2 a − 1 . Choose h 0 ≠ 0 h_0 \ne0 h 0 = 0 , and define h 1 , … , h k − 1 h_1,\ldots,h_{k-1} h 1 , … , h k − 1 recursively by
( μ + j ) h j + ( ∣ B ∣ − j ) h j + 1 = 0 , 0 ≤ j ≤ k − 2. (58) (\mu+j)h_j+(|B|-j)h_{j+1}=0,\qquad0\le j\le k-2. \tag*{(58)} ( μ + j ) h j + ( ∣ B ∣ − j ) h j + 1 = 0 , 0 ≤ j ≤ k − 2. (58)
Set h ξ = h j h_\xi=h_j h ξ = h j whenever ξ ∈ ( W k − 1 ) \xi\in\binom{W}{k-1} ξ ∈ ( k − 1 W ) contains j j j vertices of B B B . For T ∈ ( W k − 2 ) T \in\binom{W}{k-2} T ∈ ( k − 2 W ) containing j j j vertices of B B B , set
b T = b j , b j : = η ( μ + j ) L + 1 h j . (59) b_T=b_j,\qquad b_j:=\frac{\eta(\mu+j)}{L+1}h_j. \tag*{(59)} b T = b j , b j := L + 1 η ( μ + j ) h j . (59)
The recurrence (58) gives D k − 1 W h = 0 D^W_{k-1}h=0 D k − 1 W h = 0 . Moreover, for 0 ≤ j ≤ k − 3 0\le j\le k-3 0 ≤ j ≤ k − 3 ,
( μ + j + 1 ) b j + ( ∣ B ∣ − j ) b j + 1 = η ( μ + j + 1 ) L + 1 [ ( μ + j ) h j + ( ∣ B ∣ − j ) h j + 1 ] = 0 , (\mu+j+1)b_j+(|B|-j)b_{j+1}
=\frac{\eta(\mu+j+1)}{L+1}\left[(\mu+j)h_j+(|B|-j)h_{j+1}\right]=0, ( μ + j + 1 ) b j + ( ∣ B ∣ − j ) b j + 1 = L + 1 η ( μ + j + 1 ) [ ( μ + j ) h j + ( ∣ B ∣ − j ) h j + 1 ] = 0 ,
so D k − 2 W b = 0 D^W_{k-2}b=0 D k − 2 W b = 0 . We thus verified both down-map identities in Lemma 4.2 (i).
Now we verify the remaining hypotheses of Lemma 4.4 . Replacing a vertex by another vertex in A A A (resp. B B B ) does not change h h h or b b b . If one vertex lies in A A A and the other in B B B , then (58) and (59) give
b j + 1 − b j = η L + 1 [ ( μ + j + 1 ) h j + 1 − ( μ + j ) h j ] = η h j + 1 . b_{j+1}-b_j=\frac{\eta}{L+1}\left[(\mu+j+1)h_{j+1}-(\mu+j)h_j\right]=\eta h_{j+1}. b j + 1 − b j = L + 1 η [ ( μ + j + 1 ) h j + 1 − ( μ + j ) h j ] = η h j + 1 .
Thus b j + 1 − b j = η h j + 1 b_{j+1}-b_j=\eta h_{j+1} b j + 1 − b j = η h j + 1 for 0 ≤ j ≤ k − 3 0\le j\le k-3 0 ≤ j ≤ k − 3 , exactly as required by Lemma 4.2 (iv). The identity Lemma 4.2 (v) holds for T T T and distinct u , v ∈ W ∖ T u,v\in W\setminus T u , v ∈ W ∖ T : if u , v u,v u , v both belong to A A A (resp. B B B ), the two h h h -values agree; if one of { u , v } \{u,v\} { u , v } belongs to A A A and the other to B B B , their voltages sum to one. Finally, we verify the master identity Lemma 4.2 (vi). Let T T T contain j j j vertices of B B B . Since S T = ( k − 2 − j ) a + j ( 1 − a ) S_T=(k-2-j)a+j(1-a) S T = ( k − 2 − j ) a + j ( 1 − a ) and S W = ∣ A ∣ a + ∣ B ∣ ( 1 − a ) S_W=|A|a+|B|(1-a) S W = ∣ A ∣ a + ∣ B ∣ ( 1 − a ) , the coefficient L − S W − L p u + S T L-S_W-Lp_u+S_T L − S W − L p u + S T of h u T h_{uT} h u T equals − η ( μ + j ) -\eta(\mu+j) − η ( μ + j ) if u ∈ A ∖ T u\in A\setminus T u ∈ A ∖ T , and η ( ∣ B ∣ − j ) \eta(|B|-j) η ( ∣ B ∣ − j ) if u ∈ B ∖ T u\in B\setminus T u ∈ B ∖ T . In the two cases h u T = h j h_{uT}=h_j h u T = h j and h u T = h j + 1 h_{uT}=h_{j+1} h u T = h j + 1 , respectively, so Lemma 4.2 (vi) reads
( L + 1 ) b j − η ( μ + j ) h j = 0 , u ∈ A ∖ T , (60) (L+1)b_j-\eta(\mu+j)h_j=0,\qquad u\in A\setminus T, \tag*{(60)} ( L + 1 ) b j − η ( μ + j ) h j = 0 , u ∈ A ∖ T , (60)
( L + 1 ) b j + η ( ∣ B ∣ − j ) h j + 1 = 0 , u ∈ B ∖ T . (61) (L+1)b_j+\eta(|B|-j)h_{j+1}=0,\qquad u\in B\setminus T. \tag*{(61)} ( L + 1 ) b j + η ( ∣ B ∣ − j ) h j + 1 = 0 , u ∈ B ∖ T . (61)
Equation (60) is equivalent to (59) ; substituting (60) into (61) yields
η [ ( μ + j ) h j + ( ∣ B ∣ − j ) h j + 1 ] = 0 , \eta\left[(\mu+j)h_j+(|B|-j)h_{j+1}\right]=0, η [ ( μ + j ) h j + ( ∣ B ∣ − j ) h j + 1 ] = 0 ,
which holds by (58) . Thus all compatibility conditions have been verified, and Lemma 4.4 reconstructs f ∈ H k f\in\mathcal{H}_k f ∈ H k from ( h , b , p ) (h,b,p) ( h , b , p ) , with p p p the harmonic voltage prescribed by the hypothesis of this theorem.
Since h 0 ≠ 0 h_0\ne0 h 0 = 0 , Corollary 4.5 gives f ≠ 0 f\ne0 f = 0 and reduces the equality test to positive edges within W W W . The reconstruction formulas show that f f f is S A × S B \mathfrak{S}_A\times\mathfrak{S}_B S A × S B -invariant, since h h h , b b b , p p p are invariant under this group. Every positive edge within A A A or within B B B therefore has zero f f f -distance, matching its zero voltage drop; no positive edge joins A A A to B B B . By Corollary 4.5 , f ∈ E k f\in\mathcal{E}_k f ∈ E k , completing the existence proof. □ \square □
Top-degree and particle-sector kernels
Theorem 8.4 (Top-degree kernel classification). Let W 1 , … , W q W_1,\ldots,W_q W 1 , … , W q be the connected components of G [ W ] G[W] G [ W ] . For every 2 ≤ k ≤ ⌊ n 2 ⌋ 2\le k\le\left\lfloor\frac{n}{2}\right\rfloor 2 ≤ k ≤ ⌊ 2 n ⌋ , exactly the following alternatives occur:
(i) If every W i W_i W i is terminal-balanced at 1 2 \frac{1}{2} 2 1 , let Γ : = S W 1 × ⋯ × S W q \Gamma:=\mathfrak{S}_{W_1}\times\cdots\times\mathfrak{S}_{W_q} Γ := S W 1 × ⋯ × S W q and let β s \beta_s β s count the Γ \Gamma Γ -orbits on s s s -subsets of W W W . Then
dim E k = β k − 1 − β k − 2 . \dim\mathcal{E}_k=\beta_{k-1}-\beta_{k-2}. dim E k = β k − 1 − β k − 2 .
Moreover, E k \mathcal{E}_k E k is canonically identified with H k − 1 ( W ) Γ \mathcal{H}_{k-1}(W)^\Gamma H k − 1 ( W ) Γ by (56) , interpreted also at k = 2 k=2 k = 2 .
(ii) If every W i W_i W i is terminal-balanced, and the terminal-balance parameters are exactly { a , 1 − a } \{a,1-a\} { a , 1 − a } for some 0 ≤ a ≤ 1 2 0\le a\le\frac{1}{2} 0 ≤ a ≤ 2 1 , let A , B A,B A , B be the corresponding voltage classes. Then
dim E k = { 1 , k − 1 ≤ min { ∣ A ∣ , ∣ B ∣ } , 0 , k − 1 > min { ∣ A ∣ , ∣ B ∣ } . \dim\mathcal{E}_k=
\begin{cases}
1, & k-1\le\min\{|A|,|B|\},\\
0, & k-1>\min\{|A|,|B|\}.
\end{cases} dim E k = { 1 , 0 , k − 1 ≤ min { ∣ A ∣ , ∣ B ∣ } , k − 1 > min { ∣ A ∣ , ∣ B ∣ } .
In the case k ≥ 3 k \ge3 k ≥ 3 and dim E k = 1 \dim\mathcal{E}_k = 1 dim E k = 1 , the data in (58) –(59) together with Lemma 4.4 and Corollary 4.5 give a spanning vector for E k \mathcal{E}_k E k . In the case k = 2 k = 2 k = 2 , the vector in (5.4) spans E k \mathcal{E}_k E k .
(iii) In all other cases, E k = { 0 } \mathcal{E}_k = \{0\} E k = { 0 } .
Proof. For k = 2 k = 2 k = 2 , the dimension statement is Theorem 5.6. In the midpoint case, β 1 = q \beta_1 = q β 1 = q and β 0 = 1 \beta_0 = 1 β 0 = 1 , so β 1 − β 0 = q − 1 \beta_1 - \beta_0 = q - 1 β 1 − β 0 = q − 1 . The proof of Theorem 5.6 parametrizes this kernel by weighted-zero-sum component constants α \alpha α ; setting h = 2 α h = 2\alpha h = 2 α identifies their parameter space with H 1 ( W ) Γ \mathcal{H}_1(W)^{\Gamma} H 1 ( W ) Γ through the piecewise formula (56) , which is also valid at k = 2 k = 2 k = 2 . In the complementary case, both voltage classes are nonempty, so 1 ≤ min { ∣ A ∣ , ∣ B ∣ } 1 \le\min\{|A|, |B|\} 1 ≤ min { ∣ A ∣ , ∣ B ∣ } , dim E k = 1 \dim\mathcal{E}_k = 1 dim E k = 1 , and E k \mathcal{E}_k E k is spanned by the vector (5.4).
For k ≥ 3 k \ge3 k ≥ 3 , alternatives (i) and (ii) are Theorems 8.2 and 8.3 . If neither graph alternative holds, Theorem 7.5 with ℓ = k \ell= k ℓ = k gives ker K x y ℓ ∩ ( ⨁ j = 2 k U j → k H j ) = { 0 } \ker K_{xy}^{\ell} \cap\bigl(\bigoplus_{j=2}^{k} U_{j\to k}\mathcal{H}_j\bigr) = \{0\} ker K x y ℓ ∩ ( ⨁ j = 2 k U j → k H j ) = { 0 } . Since U k → k = I U_{k\to k} = I U k → k = I , this forces E k = { 0 } \mathcal{E}_k = \{0\} E k = { 0 } , proving the alternative (iii). □
To describe every particle sector, it remains to identify the degree-one equality space. Zhu [10 ] established a nontrivial degree-one equality vector (which he called a “linear observable”). The next result shows that this vector spans E 1 \mathcal{E}_1 E 1 .
Proposition 8.5 (Degree-one kernel). Let p p p be the harmonic x x x –y y y voltage and set p ˉ : = n − 1 ∑ v ∈ V p ( v ) \bar p := n^{-1}\sum_{v\in V}p(v) p ˉ := n − 1 ∑ v ∈ V p ( v ) . Then
E 1 = span { p − p ˉ } . (62) \mathcal{E}_1 = \operatorname{span}\{p-\bar p\}. \tag*{(62)} E 1 = span { p − p ˉ } . (62)
Proof. The function p − p ˉ p-\bar p p − p ˉ lies in H 1 \mathcal{H}_1 H 1 . Its transposition distances are a constant multiple of ∣ p ( u ) − p ( v ) ∣ |p(u)-p(v)| ∣ p ( u ) − p ( v ) ∣ , so Proposition 3.3 shows that it is an equality vector. Conversely, let g ∈ H 1 g \in\mathcal{H}_1 g ∈ H 1 be a nonzero equality vector. For r = 1 r = 1 r = 1 and v ∈ V ∖ { x , y } v \in V \setminus\{x,y\} v ∈ V ∖ { x , y } , apply (29) to g g g : the a g , v x y a^{xy}_{g,v} a g , v x y -coordinate is g ( x ) − g ( v ) g(x)-g(v) g ( x ) − g ( v ) , while the d g x y d^{xy}_g d g x y -coordinate is g ( x ) − g ( y ) g(x)-g(y) g ( x ) − g ( y ) . Hence g ( v ) = ( 1 − p ( v ) ) g ( x ) + p ( v ) g ( y ) g(v)=(1-p(v))g(x)+p(v)g(y) g ( v ) = ( 1 − p ( v )) g ( x ) + p ( v ) g ( y ) for every vertex v v v , terminal or nonterminal. Thus g g g is affine in p p p , and the zero-sum condition defining H 1 \mathcal{H}_1 H 1 leaves exactly the one-dimensional span in (62) . □
Theorem 8.6 (Kernel in each particle sector). Fix 1 ≤ ℓ ≤ n − 1 1 \le\ell\le n-1 1 ≤ ℓ ≤ n − 1 and put d = min ( ℓ , n − ℓ ) d=\min(\ell,n-\ell) d = min ( ℓ , n − ℓ ) . For 1 ≤ j ≤ ⌊ n / 2 ⌋ 1 \le j \le\lfloor n/2\rfloor 1 ≤ j ≤ ⌊ n /2 ⌋ , let E j \mathcal{E}_j E j be the kernels described in Theorem 8.4 and Proposition 8.5 . Then we have the orthogonal decomposition
ker K x y ( ℓ ) = span { 1 } ⊕ ⨁ j = 1 d U j → ℓ E j . (63) \ker\mathcal{K}_{xy}^{(\ell)}=\operatorname{span}\{1\}\oplus\bigoplus_{j=1}^{d}U_{j\to\ell}\mathcal{E}_j. \tag*{(63)} ker K x y ( ℓ ) = span { 1 } ⊕ j = 1 ⨁ d U j → ℓ E j . (63) where 1 1 1 denotes the constant-one function. Consequently, using the orbit counts β s \beta_s β s in the midpoint case, resp. the voltage classes A , B A,B A , B in the complementary case, as specified in Theorem 8.4 ,
dim ker K x y ( ℓ ) = { 1 + β d − 1 , in the midpoint case , 2 + min { d − 1 , ∣ A ∣ , ∣ B ∣ } , in the complementary case , 2 , in all other cases . (64) \dim\ker\mathcal{K}_{xy}^{(\ell)}=
\begin{cases}
1+\beta_{d-1}, & \text{in the midpoint case},\\
2+\min\{d-1,|A|,|B|\}, & \text{in the complementary case},\\
2, & \text{in all other cases}.
\end{cases} \tag*{(64)} dim ker K x y ( ℓ ) = ⎩ ⎨ ⎧ 1 + β d − 1 , 2 + min { d − 1 , ∣ A ∣ , ∣ B ∣ } , 2 , in the midpoint case , in the complementary case , in all other cases . (64)
Proof. By Lemmas 7.1 and 7.3 , the orthogonal summands in (54) are invariant under K x y ( ℓ ) \mathcal{K}_{xy}^{(\ell)} K x y ( ℓ ) . For 1 ≤ j ≤ d 1 \le j \le d 1 ≤ j ≤ d , its kernel on U j → ℓ H j U_{j\to\ell}\mathcal{H}_j U j → ℓ H j is exactly U j → ℓ E j U_{j\to\ell}\mathcal{E}_j U j → ℓ E j . In particular, the kernel intersection in Corollary 7.4 is the direct sum ⨁ j = 2 d U j → ℓ E j \bigoplus_{j=2}^{d}U_{j\to\ell}\mathcal{E}_j ⨁ j = 2 d U j → ℓ E j when d ≥ 2 d \ge2 d ≥ 2 . Degree zero is the constant line, while Proposition 8.5 identifies the degree-one contribution. This proves (63) .
In the midpoint case, Theorem 8.4 (i) and telescoping give the dimension 2 + ∑ j = 2 d ( β j − 1 − β j − 2 ) = 2 + β d − 1 − β 0 = 1 + β d − 1 2+\sum_{j=2}^{d}(\beta_{j-1}-\beta_{j-2})=2+\beta_{d-1}-\beta_0=1+\beta_{d-1} 2 + ∑ j = 2 d ( β j − 1 − β j − 2 ) = 2 + β d − 1 − β 0 = 1 + β d − 1 . In the complementary case, Theorem 8.4 (ii) states that exactly min { d − 1 , ∣ A ∣ , ∣ B ∣ } \min\{d-1,|A|,|B|\} min { d − 1 , ∣ A ∣ , ∣ B ∣ } of the degrees 2 , … , d 2,\ldots,d 2 , … , d contribute one dimension. In all other cases no Hoeffding degree j ≥ 2 j\ge2 j ≥ 2 contributes. This yields (64) . □
Remark 8.7. For ℓ ∈ { 0 , n } \ell\in\{0,n\} ℓ ∈ { 0 , n } , there is only one ℓ \ell ℓ -particle configuration. Hence the residual K x y ( ℓ ) \mathcal{K}_{xy}^{(\ell)} K x y ( ℓ ) vanishes, and its kernel is the constant line.
Equality kernel for the interchange process
The preceding Theorem 8.6 determines the equality kernel in all exclusion particle sectors, including its component in each Hoeffding layer. To pass to the interchange process, define the moving-particle residual on the group algebra R [ C V ] \mathbb{R}[\mathbb{C}_V] R [ C V ] by
K x y IP : = L G IP − c e f f ( x , y ) ( I − τ x y ) . \mathcal{K}_{xy}^{\operatorname{IP}}:=\mathcal{L}_G^{\operatorname{IP}}-c_{\mathrm{eff}}(x,y)(I-\tau_{xy}). K x y IP := L G IP − c eff ( x , y ) ( I − τ x y ) .
On S λ S^\lambda S λ , the corresponding residual is K G , x y λ K^\lambda_{G,xy} K G , x y λ from (10) . Recall the orthogonal regular representation decomposition (9) . On the λ \lambda λ -isotypic summand S λ ⊗ R d λ S^\lambda\otimes\mathbb{R}^{d_\lambda} S λ ⊗ R d λ , K x y I P K^{\mathrm{IP}}_{xy} K x y IP acts as K G , x y λ ⊗ I K^\lambda_{G,xy} \otimes I K G , x y λ ⊗ I .
Set E 0 : = R E_0 := \mathbb{R} E 0 := R for the constant representation.
Theorem 8.8 (Complete equality kernel for the interchange process). The interchange residual K x y I P K^{\mathrm{IP}}_{xy} K x y IP defined above has the orthogonal decomposition
ker K x y I P ≅ ⨁ j = 0 ⌊ n 2 ⌋ E j ⊗ R d ( n − j , j ) . (65) \ker K^{\mathrm{IP}}_{xy} \cong\bigoplus_{j=0}^{\left\lfloor\frac{n}{2} \right\rfloor} E_j \otimes\mathbb{R}^{d_{(n-j,j)}}. \tag*{(65)} ker K x y IP ≅ j = 0 ⨁ ⌊ 2 n ⌋ E j ⊗ R d ( n − j , j ) . (65) In particular,
dim ker K x y I P = n + ∑ j = 2 ⌊ n 2 ⌋ ( ( n j ) − ( n j − 1 ) ) dim E j , (66) \dim\ker K^{\mathrm{IP}}_{xy} = n + \sum_{j=2}^{\left\lfloor\frac{n}{2} \right\rfloor} \left(\binom{n}{j} - \binom{n}{j-1}\right)\dim E_j, \tag*{(66)} dim ker K x y IP = n + j = 2 ∑ ⌊ 2 n ⌋ ( ( j n ) − ( j − 1 n ) ) dim E j , (66) where dim E j \dim E_j dim E j for j ≥ 2 j \ge2 j ≥ 2 are given by Theorem 8.4 .
Proof. For 1 ≤ j ≤ ⌊ n 2 ⌋ 1 \le j \le\left\lfloor\frac{n}{2} \right\rfloor 1 ≤ j ≤ ⌊ 2 n ⌋ , apply Theorem 8.6 to the j j j -particle sector: its top Hoeffding-layer kernel is E j E_j E j . By (53) , this identifies ker K G , x y ( n − j , j ) \ker K^{(n-j,j)}_{G,xy} ker K G , x y ( n − j , j ) with E j E_j E j . By definition, E 0 = R E_0 = \mathbb{R} E 0 = R , and E 1 = span { p − p ˉ } E_1 = \operatorname{span}\{p-\bar p\} E 1 = span { p − p ˉ } by Proposition 8.5 . By Theorem 2.3 , all irreducible summands with at least three rows have trivial kernel. Applying (9) gives (65) . Since dim E 0 = dim E 1 = 1 \dim E_0 = \dim E_1 = 1 dim E 0 = dim E 1 = 1 , the j = 0 , 1 j=0,1 j = 0 , 1 summands contribute d ( n ) + d ( n − 1 , 1 ) = 1 + ( n − 1 ) = n d_{(n)} + d_{(n-1,1)} = 1 + (n-1) = n d ( n ) + d ( n − 1 , 1 ) = 1 + ( n − 1 ) = n dimensions. For j ≥ 2 j \ge2 j ≥ 2 , the hook-length formula gives d ( n − j , j ) = ( n j ) − ( n j − 1 ) d_{(n-j,j)} = \binom{n}{j} - \binom{n}{j-1} d ( n − j , j ) = ( j n ) − ( j − 1 n ) , yielding (66) . □
Statement of AI use
This author used ChatGPT 6–Sol to discover the two-row rigidity Theorem 2.3 , the interface identities Lemma 4.2 , the voltage rigidity Lemmas 4.6 and 4.7, and the quadratic equality vector (5.4) in Lemma 5.4 . In the writing process, multiple rounds of edit prompts were executed to ensure the correctness of the results, as well as their presentation. The author manually checked the paper line-by-line and made the necessary edits before finalizing it. He takes full responsibility for the contents of this paper.