Introduction
Spectral gaps connect expansion, functional inequalities, and the convergence of random walks. On graphs, they quantify connectivity and control the rate at which a walk approaches equilibrium. Through Poincaré inequalities, they also bound the variance of functions in terms of their local variation, providing a connection to correlations and fluctuations. These perspectives have made spectral estimates useful throughout combinatorics, probability, and statistical physics, with applications to sampling and approximate counting, the dynamics of spin systems, and high-dimensional expansion. A recurring difficulty is that the relevant state spaces can be enormous or even continuous, even when their defining interactions are simple. This motivates a local-to-global approach: obtain spectral information about a complicated system by analyzing smaller, more tractable pieces. Trickle-down theorems in high-dimensional expansion provide one realization of this local-to-global approach (see [47 ] and its extensions [3 , 2 , 42 ] ). The local structure of a simplicial complex is described by its links, which record the ways a fixed face can be extended to larger faces. When a finite spin system is encoded as a simplicial complex, passing to a link corresponds to conditioning on the spins at specified sites. Under suitable connectivity assumptions, spectral expansion of low-dimensional links propagates to higher-dimensional links, leading to spectral bounds for random walks on the complex.
The Bochner method. In very recent times, many spectral-gap arguments like those utilized in trickle-down theorems now admit substantially simpler proofs via the Bochner method. The technique is similar, local expansion implies global expansion, but the main difference is in the simplicity and uniformity of its proof. This method has been utilized in a huge number of new results (see for instance [28 , 32 Wan26, 18 , 16 , 12 , 33 , 44 ] and also several recent papers by OpenAI). We note that the new explosion of results is mainly driven by AI, and even the general power of the technique itself within the context of trickle-down theorems was not fully realized until it was suggested by AI.
The Bochner method is not a new technique (it is called “Bochner” after all). The name derives from [13 , 41 ] , where a similar analysis is used to prove spectral gaps for the Laplacian of a Riemannian manifold (see also [10 ] ). Various papers since then have made connections to graphs, expansion, spectral gaps, and beyond [9 , 10 ] . The general idea is to represent an eigenvalue gap by a matrix inequality, for example L 2 − λ L ⪰ 0 L^2-\lambda L \succeq0 L 2 − λ L ⪰ 0 L L L L L L ( 0 , λ ) (0,\lambda) ( 0 , λ ) 0 0 0 L 2 − λ L L^2-\lambda L L 2 − λ L ∑ i L i 2 − λ i L i \sum_i L_i^2-\lambda_iL_i ∑ i L i 2 − λ i L i L i L_i L i [17 ] for further details.
Beyond the Bochner method. In the context of spin systems (which we define below), the usual Bochner argument yields a spectral gap for the whole system from conditional estimates on pairs of sites. In this paper, we extend this method to handle a much wider range of conclusions, allowing for arbitrary marginalization and groupings of sites, all following from the same local information. Moreover, our new spectral gap bounds are tight: for each admissible matrix of local bounds, a single Gaussian system attains all of these bounds simultaneously.
Our applications include spectral gap bounds and sampling algorithms for the O ( N ) O(N) O ( N ) § 1.3 ), applications to swap walks and local spectral expansion (§ 1.4 ), and improved negative correlation bounds for pairs of edges of uniformly random forests in a graph (§ 1.5 ).
To achieve our results, we abstract the content of the Bochner method. We prove a purely linear algebraic statement, which when applied to local Laplacians of a given graph, immediately recovers the spectral gap conclusions of both the Bochner method and our new results. Our hope for this formulation is that we are getting closer to some core underlying mathematical framework that might bring together the various local-to-global results spread across the math and TCS literature. This is an important goal in itself in the AI age, where specific theorems may become cheaper than the techniques used to conceptually simplify and unify them.
We now discuss these results and applications in more detail. We first describe the setup in terms of spin systems, and then give our main results and applications. After that, we will describe the purely linear algebraic formulation of our technical results, and how it yields our applications.
Spin systems and Glauber dynamics
A spin system is a graph G = ( V , E ) G=(V,E) G = ( V , E ) sites V V V spins S v S_v S v v ∈ V v \in V v ∈ V configuration of the spin system is then a valid choice of spin s v ∈ S v s_v \in S_v s v ∈ S v v ∈ V v \in V v ∈ V
We describe two basic examples. Given any graph, let S v S_v S v v ∈ V v \in V v ∈ V S v = { 0 , 1 } S_v=\{0,1\} S v = { 0 , 1 } v ∈ V v \in V v ∈ V [37 , 45 ] . Other important examples of spin systems (like the O ( N ) O(N) O ( N )
A spin system is also equipped with a measure μ \mu μ Glauber dynamics of a given spin system, which is a natural random walk on its configurations. This is how it works: Given a configuration, choose a uniformly random vertex and forget its spin. Then, sample a new spin for that vertex according to the μ \mu μ μ \mu μ
Let P G l a u b P_{\mathrm{Glaub}} P Glaub σ , τ \sigma,\tau σ , τ P G l a u b ( σ , τ ) P_{\mathrm{Glaub}}(\sigma,\tau) P Glaub ( σ , τ ) σ \sigma σ τ \tau τ mixing time of Glauber dynamics is defined to be
inf { t ∈ Z ≥ 0 : sup σ ∈ S ∥ P G l a u b t ( σ , ⋅ ) − μ ∥ T V ≤ 1 4 } . \inf\left\{t \in\mathbb{Z}_{\ge0}:\sup_{\sigma\in\mathcal{S}}\left\lVert P_{\mathrm{Glaub}}^t(\sigma,\cdot)-\mu\right\rVert_{\mathrm{TV}}\le\frac{1}{4}\right\}. inf { t ∈ Z ≥ 0 : σ ∈ S sup P Glaub t ( σ , ⋅ ) − μ TV ≤ 4 1 } . When the set of spins S v S_v S v v ∈ V v \in V v ∈ V λ 2 ( I − P G l a u b ) \lambda_2(I-P_{\mathrm{Glaub}}) λ 2 ( I − P Glaub )
However, when considering infinite spaces of spins (e.g. when S v S_v S v R m \mathbb{R}^m R m L G l a u b = I − P G l a u b L_{\mathrm{Glaub}}=I-P_{\mathrm{Glaub}} L Glaub = I − P Glaub spectral gap is defined to be the maximal λ ≥ 0 \lambda\ge0 λ ≥ 0 L G l a u b 2 − λ L G l a u b ≥ 0 L_{\mathrm{Glaub}}^2-\lambda L_{\mathrm{Glaub}}\ge0 L Glaub 2 − λ L Glaub ≥ 0 λ = 0 \lambda=0 λ = 0 dim ( ker ( L G l a u b ) ) ≥ 2 \dim(\ker(L_{\mathrm{Glaub}}))\ge2 dim ( ker ( L Glaub )) ≥ 2 L G l a u b L_{\mathrm{Glaub}} L Glaub P G l a u b P_{\mathrm{Glaub}} P Glaub λ 2 ( L G l a u b ) = λ \lambda_2(L_{\mathrm{Glaub}})=\lambda λ 2 ( L Glaub ) = λ
Using the Bochner method. The Bochner method then gives a simple method for proving spectral gaps in the case of general spin systems (with not necessarily finite sets of spins). In this section we give the main result in this direction and refer the reader to [32 ] for the original statement, or [17 ] for the clean and direct proof of this fact.
First we need a bit of extra notation. A pinning of a spin system is a fixing of some of the spins. Note that a pinning is a spin system on the unpinned vertices, with distribution μ \mu μ P G l a u b τ P_{\mathrm{Glaub}}^\tau P Glaub τ L G l a u b τ L_{\mathrm{Glaub}}^\tau L Glaub τ τ \tau τ
Theorem 1 ([32 , 17 ] , see also [43 ] ). Fix a spin system on G = ( V , E ) G=(V,E) G = ( V , E ) μ \mu μ ker ( L G l a u b ) \ker(L_{\mathrm{Glaub}}) ker ( L Glaub ) V × V V \times V V × V A A A λ max ( A ) < 1 \lambda_{\max}(A)<1 λ m a x ( A ) < 1 u ≠ v u \ne v u = v V V V τ \tau τ V ∖ { u , v } V \setminus\{u,v\} V ∖ { u , v }
λ 2 ( L G l a u b τ ) ≥ 1 − a u v 2 , \lambda_{2}(L_{\mathrm{Glaub}}^{\tau}) \ge\frac{1-a_{uv}}{2}, λ 2 ( L Glaub τ ) ≥ 2 1 − a uv , then
λ 2 ( L G l a u b ) ≥ 1 − λ max ( A ) ∣ V ∣ . \lambda_{2}(L_{\mathrm{Glaub}}) \ge\frac{1-\lambda_{\max}(A)}{|V|}. λ 2 ( L Glaub ) ≥ ∣ V ∣ 1 − λ m a x ( A ) . Note that, under the appropriate connectedness assumption, the conclusion of Theorem 1 extends to any intermediate pinning by considering the appropriate principal submatrix of $A. This is true also for our main result in Theorem 3.
Remark 2. We write the condition on pinnings in Theorem 1 (and in Theorem 3 below) in terms of the spectral gap of the two-site Glauber dynamics, but one can also write it in terms of the associated bipartite random walk operator; see Corollary 6. The equivalent bound on the second eigenvalue in this case becomes an upper bound by a u v a_{uv} a uv spectral influence between u u u v v v a u v a_{uv} a uv [43 ] to obtain trickle-down theorems for finite spins systems. This quantity was also used in [32 ] in the form of maximal correlations (see Remark 2 of that paper). We discuss the connections between these and other quantities further in § 2.3 .
Main result: Spectral gaps for block Glauber dynamics
Our main technical result is then an extension of Theorem 1 to bounds on spectral gaps of marginal distributions on disjoint sets of sites. To state this result, we need some new notation. Let T 1 , … , T m T_1,\ldots,T_m T 1 , … , T m T = T 1 ⊔ ⋯ ⊔ T m T=T_1\sqcup\cdots\sqcup T_m T = T 1 ⊔ ⋯ ⊔ T m i ∈ [ m ] i\in[m] i ∈ [ m ] Y i = X T i Y_i=X_{T_i} Y i = X T i T i T_i T i S i = ∏ v ∈ T i S v S_i=\prod_{v\in T_i}S_v S i = ∏ v ∈ T i S v
Consider the joint law of ( Y 1 , … , Y m ) (Y_1,\ldots,Y_m) ( Y 1 , … , Y m ) S 1 × ⋯ × S m S_1\times\cdots\times S_m S 1 × ⋯ × S m μ \mu μ T T T m m m i i i S i S_i S i P G l a u b T 1 , … , T m P_{\mathrm{Glaub}}^{T_1,\ldots,T_m} P Glaub T 1 , … , T m L G l a u b T 1 , … , T m L_{\mathrm{Glaub}}^{T_1,\ldots,T_m} L Glaub T 1 , … , T m T 1 , … , T m T_1,\ldots,T_m T 1 , … , T m V V V
Theorem 3. Fix a spin system on G = ( V , E ) G=(V,E) G = ( V , E ) μ \mu μ ker ( L G l a u b ) \ker(L_{\mathrm{Glaub}}) ker ( L Glaub ) V × V V\times V V × V A A A λ max ( A ) < 1 \lambda_{\max}(A)<1 λ m a x ( A ) < 1 M = I − A M=I-A M = I − A T 1 , … , T m ⊂ V T_1,\ldots,T_m\subset V T 1 , … , T m ⊂ V T = ⨆ i T i T=\bigsqcup_iT_i T = ⨆ i T i
C = ( ( M − 1 ) T ) − 1 , D = blockdiag ( C T 1 , … , C T m ) , H = I − D − 1 / 2 C D − 1 / 2 , C=((M^{-1})_T)^{-1}, \quad D=\operatorname{blockdiag}(C_{T_1},\ldots,C_{T_m}), \quad H=I-D^{-1/2}CD^{-1/2}, C = (( M − 1 ) T ) − 1 , D = blockdiag ( C T 1 , … , C T m ) , H = I − D − 1/2 C D − 1/2 , where M α M_\alpha M α M M M α \alpha α u ≠ v u\ne v u = v V V V τ \tau τ V ∖ { u , v } V\setminus\{u,v\} V ∖ { u , v }
λ 2 ( L G l a u b τ ) ≥ 1 − a u v 2 , \lambda_2(L_{\mathrm{Glaub}}^\tau)\ge\frac{1-a_{uv}}{2}, λ 2 ( L Glaub τ ) ≥ 2 1 − a uv , then
λ 2 ( L G l a u b T 1 , … , T m ) ≥ 1 − λ max ( H ) m . \lambda_{2}\left(L_{\mathrm{Glaub}}^{T_{1},\ldots,T_{m}}\right) \ge\frac{1-\lambda_{\max}(H)}{m}. λ 2 ( L Glaub T 1 , … , T m ) ≥ m 1 − λ m a x ( H ) . To see how this relates to Theorem 1 , let T 1 , … , T n T_{1},\ldots,T_{n} T 1 , … , T n L G l a u b T 1 , … , T n = L G l a u b L_{\mathrm{Glaub}}^{T_{1},\ldots,T_{n}}=L_{\mathrm{Glaub}} L Glaub T 1 , … , T n = L Glaub C = I − A C=I-A C = I − A D = I D=I D = I H = A H=A H = A Theorem 3 recovers Theorem 1 .
The dependence on the full matrix A A A λ \lambda λ § 1.4 .
Remark 4. We note that Theorem 3 is tight for every admissible matrix A A A Theorem 3 , let ( X 1 , … , X n ) = X ∼ N ( 0 , M − 1 ) (X_{1},\ldots,X_{n})=X\sim N(0,M^{-1}) ( X 1 , … , X n ) = X ∼ N ( 0 , M − 1 ) 1 , 2 , … , n 1,2,\ldots,n 1 , 2 , … , n R \mathbb{R} R X X X Theorem 3 are satisfied with equality, and so are the conclusions for any choice of disjoint T 1 , … , T m T_{1},\ldots,T_{m} T 1 , … , T m
Application: The O ( N ) O(N) O ( N )
We can now give our first application, on a global spectral gap and sampling of the O ( N ) O(N) O ( N )
We first describe the O ( N ) O(N) O ( N ) G = ( V , E ) G=(V,E) G = ( V , E ) n = ∣ V ∣ n=|V| n = ∣ V ∣ x ∈ V x\in V x ∈ V σ x ∈ S N − 1 ⊂ R N \sigma_{x}\in S^{N-1}\subset\mathbb{R}^{N} σ x ∈ S N − 1 ⊂ R N J = ( J x y ) x , y ∈ V J=(J_{xy})_{x,y\in V} J = ( J x y ) x , y ∈ V J x x = 0 J_{xx}=0 J xx = 0 J x y = 0 J_{xy}=0 J x y = 0 x ∼ y x\sim y x ∼ y h x ∈ R N h_{x}\in\mathbb{R}^{N} h x ∈ R N O ( N ) O(N) O ( N )
μ J , h ( d σ ) ∝ exp ( 1 2 ∑ x , y ∈ V J x y σ x ⋅ σ y + ∑ x ∈ V h x ⋅ σ x ) ∏ x ∈ V d ω ( σ x ) , (1) \mu_{J,h}(d\sigma)\propto\exp\left(\frac{1}{2}\sum_{x,y\in V}J_{xy}\sigma_{x}\cdot\sigma_{y}+\sum_{x\in V}h_{x}\cdot\sigma_{x}\right)\prod_{x\in V}d\omega(\sigma_{x}), \tag*{(1)} μ J , h ( d σ ) ∝ exp 2 1 x , y ∈ V ∑ J x y σ x ⋅ σ y + x ∈ V ∑ h x ⋅ σ x x ∈ V ∏ d ω ( σ x ) , (1) where ω \omega ω S N − 1 S^{N-1} S N − 1
J a b s = ( ∣ J x y ∣ ) x , y ∈ V and R = max x ∈ V ∑ y ≠ x ∣ J x y ∣ . J_{\mathrm{abs}}=(|J_{xy}|)_{x,y\in V}\quad\text{and}\quad R=\max_{x\in V}\sum_{y\ne x}|J_{xy}|. J abs = ( ∣ J x y ∣ ) x , y ∈ V and R = x ∈ V max y = x ∑ ∣ J x y ∣. For this model, some spectral gap bounds are known when the interactions between sites are bounded above in a suitable sense. The Brascamp–Lieb argument of Dyson, Lieb, and Simon [25 Appendix D] gives a bound on the covariance matrix of ( σ x ) x ∈ V (\sigma_{x})_{x\in V} ( σ x ) x ∈ V λ max ( J ) − λ min ( J ) < N \lambda_{\max}(J)-\lambda_{\min}(J)<N λ m a x ( J ) − λ m i n ( J ) < N R < N / 2 R<N/2 R < N /2 [8 ] strengthened this to a logarithmic Sobolev inequality for Langevin dynamics under the same spectral condition. More recently, Anari, Koehler, and Vuong [2 Theorems 5 and 8, Section 1.3] proved a logarithmic Sobolev inequality for Langevin dynamics and O ( n log n ) O(n\log n) O ( n log n ) R < ( 4 1 / 3 − 1 ) N ≈ 0.5874 N R<(4^{1/3}-1)N\approx0.5874N R < ( 4 1/3 − 1 ) N ≈ 0.5874 N
We now give our first main result, which establishes a spectral gap of order 1 / n 1/n 1/ n O ( n 2 ) O(n^{2}) O ( n 2 ) R < N R<N R < N ∥ J a b s ∥ o p < N \lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}}<N ∥ J abs ∥ op < N ∥ J a b s ∥ o p ≤ R \lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}}\le R ∥ J abs ∥ op ≤ R N N N 1 / n 1/n 1/ n [39 ] .
Theorem 5. Let N ≥ 2 N \ge2 N ≥ 2 μ \mu μ O ( N ) O(N) O ( N )
1 − ∥ J a b s ∥ o p N n . \frac{1-\frac{\lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}}}{N}}{n}. n 1 − N ∥ J abs ∥ op . Consequently, for every ε 0 ∈ ( 0 , 1 ) \varepsilon_0 \in(0,1) ε 0 ∈ ( 0 , 1 ) ∥ J a b s ∥ o p ≤ ( 1 − ε 0 ) N \lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}} \le(1-\varepsilon_0)N ∥ J abs ∥ op ≤ ( 1 − ε 0 ) N O N , ε 0 ( n 2 ) O_{N,\varepsilon_0}(n^2) O N , ε 0 ( n 2 )
Using established tools, we can improve this mixing-time bound to the optimal O ( n log n ) O(n\log n) O ( n log n )
Applications in high-dimensional expanders
Theorem 3 has a number of connections and applications to spectral bounds studied in the field of high-dimensional expanders (HDX). In the context of HDX, spin systems are referred to as partite simplicial complexes: the sites specify vertices of different types, configurations are facets which contain one vertex of each type, and pinnings correspond to passing to links. Bounding the spectral gap of the Glauber dynamics on various choices of block of sites (as allowed by Theorem 3) is then equivalent to different notions of expansion of the given simplicial complex.
λ \lambda λ λ \lambda λ [29 ] and studied later in [24 , 34 ] . A distribution μ \mu μ λ \lambda λ ρ max \rho_{\max} ρ m a x λ \lambda λ ρ max = ρ μ \rho_{\max} = \rho_\mu ρ m a x = ρ μ § 2.3 .) This condition then controls correlations (and hence also the Glauber spectral gap) between groups of coordinates: for disjoint sets T 1 , T 2 T_1,T_2 T 1 , T 2 [29 ] gives
ρ max ( X T 1 , X T 2 ) ≤ λ ∣ T 1 ∣ ∣ T 2 ∣ . \rho_{\max}(X_{T_1},X_{T_2}) \le\lambda\sqrt{\lvert T_1\rvert\lvert T_2\rvert}. ρ m a x ( X T 1 , X T 2 ) ≤ λ ∣ T 1 ∣ ∣ T 2 ∣ . where X ∼ μ X \sim\mu X ∼ μ ρ max \rho_{\max} ρ m a x swap walk , which is the bipartite random walk on the spins of the groupings T 1 T_1 T 1 T 2 T_2 T 2 [21 , 1 ] and later in [22 , 6 ] .
By the two-site equivalence in Lemma 13, the two-block case of Theorem 3 gives
ρ max ( X T 1 , X T 2 ) ≤ λ max ( H ) = ∥ C T 1 − 1 / 2 C T 1 , T 2 C T 2 − 1 / 2 ∥ o p . \rho_{\max}(X_{T_1},X_{T_2}) \le\lambda_{\max}(H) = \left\lVert C_{T_1}^{-1/2}C_{T_1,T_2}C_{T_2}^{-1/2}\right\rVert_{\mathrm{op}}. ρ m a x ( X T 1 , X T 2 ) ≤ λ m a x ( H ) = C T 1 − 1/2 C T 1 , T 2 C T 2 − 1/2 op . This estimate retains the locations and strengths of the conditional interactions recorded in A A A λ max ( H ) ≤ λ max ( A ) \lambda_{\max}(H) \le\lambda_{\max}(A) λ m a x ( H ) ≤ λ m a x ( A ) T 1 T_1 T 1 T 2 T_2 T 2
Path complexes and flags of subspaces. For the path complexes studied in [42 ] , we can take A = 1 2 Adj ( P n ) A = \frac{1}{2}\operatorname{Adj}(P_n) A = 2 1 Adj ( P n ) P n P_n P n n n n ( I − A ) − 1 (I-A)^{-1} ( I − A ) − 1
ρ max ( X i , X j ) ≤ λ max ( H ) = i ( n + 1 − j ) j ( n + 1 − i ) , i < j . (2) \rho_{\max}(X_i,X_j) \le\lambda_{\max}(H) = \sqrt{\frac{i(n+1-j)}{j(n+1-i)}}, \qquad i<j. \tag*{(2)} ρ m a x ( X i , X j ) ≤ λ m a x ( H ) = j ( n + 1 − i ) i ( n + 1 − j ) , i < j . (2) This recovers Theorem 7.2 of [42 ] , while Theorem 3 also applies to arbitrary disjoint groups of sites.
A related example regards chains/flags of subspaces in a finite vector space. Consider a uniformly random complete flag 0 ⊂ V 1 ⊂ ⋯ ⊂ V d − 1 ⊂ F q d 0 \subset V_1 \subset\cdots\subset V_{d-1} \subset\mathbb{F}_q^d 0 ⊂ V 1 ⊂ ⋯ ⊂ V d − 1 ⊂ F q d F q 3 \mathbb{F}_q^3 F q 3
A = q q + 1 Adj ( P d − 1 ) , for which λ max ( A ) < 2 q q + 1 . A = \frac{\sqrt{q}}{q+1}\operatorname{Adj}(P_{d-1}), \qquad\text{for which} \qquad\lambda_{\max}(A) < \frac{2\sqrt{q}}{q+1}. A = q + 1 q Adj ( P d − 1 ) , for which λ m a x ( A ) < q + 1 2 q . For singleton sites/rank sets, applying Theorem 3 implies
ρ max ( V i , V j ) ≤ q − ∣ i − j ∣ / 2 , \rho_{\max}(V_i,V_j) \le q^{-\lvert i-j\rvert/2}, ρ m a x ( V i , V j ) ≤ q − ∣ i − j ∣ /2 , and the same holds for all pinnings. This recovers the q − 1 / 2 q^{-1/2} q − 1/2 [35 ] for flags of subspaces.
Theorem 3 also allows for larger groups of ranks/sites, and the upper bound described above implies
ρ max ( ( V i ) i ∈ T 1 , ( V j ) j ∈ T 2 ) ≤ λ max ( H ) < 2 q q + 1 , \rho_{\max}\bigl((V_i)_{i\in T_1},(V_j)_{j\in T_2}\bigr) \le\lambda_{\max}(H) < \frac{2\sqrt{q}}{q+1}, ρ m a x ( ( V i ) i ∈ T 1 , ( V j ) j ∈ T 2 ) ≤ λ m a x ( H ) < q + 1 2 q , a bound that also holds for the corresponding swap walk. We note that the general λ \lambda λ r + 1 q \frac{r+1}{\sqrt{q}} q r + 1 r + 1 r+1 r + 1 r r r
Local spectral expansion. As a further application within HDX, we state a corollary of Theorem 3 for local spectral expansion on simplicial complexes. The proof is essentially immediate once the various equivalent spectral gap notions are unwound, see § 2.3 .
Corollary 6. Assume the notation and assumptions of Theorem 3. Assume additionally that Glauber dynamics is connected after every admissible pinning. Let X X X m m m a a a T a T_a T a Y = ( X T 1 , … , X T m ) Y=(X_{T_1},\ldots,X_{T_m}) Y = ( X T 1 , … , X T m ) X X X λ max ( H ) \lambda_{\max}(H) λ m a x ( H )
More precisely, let τ \tau τ I ⊆ [ m ] I\subseteq[m] I ⊆ [ m ] ∣ I ∣ ≥ 2 \lvert I\rvert\ge2 ∣ I ∣ ≥ 2 U = ⋃ a ∈ I T a U=\bigcup_{a\in I}T_a U = ⋃ a ∈ I T a W τ W_\tau W τ X τ X_\tau X τ
λ 2 ( W τ ) ≤ λ max ( H U ) ≤ λ max ( H ) < 1 \lambda_2(W_\tau) \le\lambda_{\max}(H_U) \le\lambda_{\max}(H) < 1 λ 2 ( W τ ) ≤ λ m a x ( H U ) ≤ λ m a x ( H ) < 1 where H U H_U H U U U U
Applying Corollary 6 to flags of subspaces gives a consequence for the colored faces complexes studied by Hopkins and Ray [35 ] . Fix a set of ranks/sites S ⊆ [ d − 1 ] S\subseteq[d-1] S ⊆ [ d − 1 ] T 1 , … , T m ⊆ S T_1,\ldots,T_m\subseteq S T 1 , … , T m ⊆ S r + 1 r+1 r + 1 T a T_a T a a a a [35 ] gives the local spectral expansion bound
2 ( r + 1 ) q − 1 − 2 ( ∣ S ∣ − r ) \frac{2(r+1)}{\sqrt{q}-1-2(\lvert S\rvert-r)} q − 1 − 2 (∣ S ∣ − r ) 2 ( r + 1 ) in the parameter range where this bound is nontrivial. Corollary 6 applies to the same complexes and gives
λ 2 ( W τ ) ≤ λ max ( H ) < 2 q q + 1 \lambda_2(W_\tau) \le\lambda_{\max}(H) < \frac{2\sqrt{q}}{q+1} λ 2 ( W τ ) ≤ λ m a x ( H ) < q + 1 2 q for every link with at least two remaining parts. Thus, we obtain a one-sided local spectral expansion bound that depends only on q q q q q q
Application: Negative correlations
The Bochner framework also yields covariance identities, which we use to study pairwise inclusion probabilities for random forests and matroid independent sets. Concretely let G = ( V , E ) G=(V,E) G = ( V , E ) μ \mu μ E E E G G G μ \mu μ e ≠ f ∈ E e \ne f \in E e = f ∈ E
c ⋅ Pr F ∼ μ [ e ∈ F ] Pr F ∼ μ [ f ∈ F ] ≥ Pr F ∼ μ [ e , f ∈ F ] ⟺ c ⋅ Pr F ∼ μ [ f ∈ F ] ≥ Pr F ∼ μ [ f ∈ F ∣ e ∈ F ] (3) c \cdot\Pr_{F\sim\mu}[e\in F]\Pr_{F\sim\mu}[f\in F] \ge\Pr_{F\sim\mu}[e,f\in F]
\quad\Longleftrightarrow\quad
c \cdot\Pr_{F\sim\mu}[f\in F] \ge\Pr_{F\sim\mu}[f\in F\mid e\in F] \tag*{(3)} c ⋅ F ∼ μ Pr [ e ∈ F ] F ∼ μ Pr [ f ∈ F ] ≥ F ∼ μ Pr [ e , f ∈ F ] ⟺ c ⋅ F ∼ μ Pr [ f ∈ F ] ≥ F ∼ μ Pr [ f ∈ F ∣ e ∈ F ] (3) for c = 1 c=1 c = 1
Another very related question asks something similar for independent sets and elements of a matroid. A matroid M M M E E E I \mathcal{I} I E E E A , B ∈ I A,B\in\mathcal{I} A , B ∈ I ∣ A ∣ < ∣ B ∣ |A|<|B| ∣ A ∣ < ∣ B ∣ e ∈ B ∖ A e\in B\setminus A e ∈ B ∖ A A ∪ { e } ∈ I A\cup\{e\}\in\mathcal{I} A ∪ { e } ∈ I μ \mu μ I \mathcal{I} I c c c [11 , 4 ] imply the bound c = 2 c=2 c = 2
For matroids, prior work shows that c ≥ 4 3 c\ge\frac{4}{3} c ≥ 3 4 [27 ] or [36 ] for a bound of 8 7 \frac{8}{7} 7 8 c = 1 c=1 c = 1 [30 ] , series-parallel graphs [26 ] , and for weighted forests in certain large-fugacity regimes [ÇR26].
Matroids capture a notion of independence which generalizes linear independence (E E E I \mathcal{I} I E E E E E E I \mathcal{I} I E E E E E E e ∈ E e\in E e ∈ E
We now show that c = 4 3 c=\frac{4}{3} c = 3 4
Theorem 7. If μ \mu μ c = 4 3 c=\frac{4}{3} c = 3 4
The covariance identity underlying our argument also gives a proof of the factor 2 bound for matroid independent sets, including under arbitrary external fields. For forests, an auxiliary real-stable polynomial gives finer control of the same covariance entries and yields the improvement to 4 3 \frac{4}{3} 3 4 § 5.3 .
Technical Overview
We now give a brief overview of the structure and proofs of our results. We first describe the discrete spins case, which is easier to think about. Later we will discuss how things change to generalize to continuous spins, which for example is needed to handle the O ( N ) O(N) O ( N ) P G l a u b P_{\mathrm{Glaub}} P Glaub f : { configurations } → R f:\{\text{configurations}\}\to\mathbb{R} f : { configurations } → R P G l a u b P_{\mathrm{Glaub}} P Glaub
Bochner and Poincaré inequalities. The first basic observation is that, for a given site v ∈ V v\in V v ∈ V v v v v v v X = ( X v ) v ∈ V X=(X_v)_{v\in V} X = ( X v ) v ∈ V μ \mu μ E v f = E μ [ f ∣ X − v ] E_vf=E_\mu[f\mid X_{-v}] E v f = E μ [ f ∣ X − v ] X − v X_{-v} X − v X u X_u X u f f f u ≠ v u\ne v u = v P G l a u b = 1 ∣ V ∣ ∑ v ∈ V E v P_{\mathrm{Glaub}}=\frac{1}{|V|}\sum_{v\in V}E_v P Glaub = ∣ V ∣ 1 ∑ v ∈ V E v
Now let us look at the local Laplacians, given by L v = I − E v L_v=I-E_v L v = I − E v L G l a u b = I − P G l a u b = 1 ∣ V ∣ ∑ v ∈ V L v L_{\mathrm{Glaub}}=I-P_{\mathrm{Glaub}}=\frac{1}{|V|}\sum_{v\in V}L_v L Glaub = I − P Glaub = ∣ V ∣ 1 ∑ v ∈ V L v P G l a u b P_{\mathrm{Glaub}} P Glaub 1 1 1 L G l a u b 2 ⪰ ϵ ∣ V ∣ L G l a u b L_{\mathrm{Glaub}}^2\succeq\frac{\epsilon}{|V|}L_{\mathrm{Glaub}} L Glaub 2 ⪰ ∣ V ∣ ϵ L Glaub ϵ / ∣ V ∣ > 0 \epsilon/|V|>0 ϵ /∣ V ∣ > 0 P G l a u b P_{\mathrm{Glaub}} P Glaub L G l a u b L_{\mathrm{Glaub}} L Glaub 0 0 0 L G l a u b L_{\mathrm{Glaub}} L Glaub L G l a u b 2 L_{\mathrm{Glaub}}^2 L Glaub 2 L G l a u b = 1 ∣ V ∣ ∑ v ∈ V L v L_{\mathrm{Glaub}}=\frac{1}{|V|}\sum_{v\in V}L_v L Glaub = ∣ V ∣ 1 ∑ v ∈ V L v
∥ L G l a u b f ∥ 2 = ∥ 1 ∣ V ∣ ∑ v ∈ V L v f ∥ 2 ≥ ϵ ∣ V ∣ 2 ∑ v ∈ V ∥ L v f ∥ 2 = ϵ ∣ V ∣ ⟨ f , L G l a u b f ⟩ (4) \left\|L_{\mathrm{Glaub}}f\right\|^2=\left\|\frac{1}{|V|}\sum_{v\in V}L_vf\right\|^2\ge\frac{\epsilon}{|V|^2}\sum_{v\in V}\left\|L_vf\right\|^2=\frac{\epsilon}{|V|}\langle f,L_{\mathrm{Glaub}}f\rangle \tag*{(4)} ∥ L Glaub f ∥ 2 = ∣ V ∣ 1 v ∈ V ∑ L v f 2 ≥ ∣ V ∣ 2 ϵ v ∈ V ∑ ∥ L v f ∥ 2 = ∣ V ∣ ϵ ⟨ f , L Glaub f ⟩ (4) for all functions f f f
A further equivalent formulation is via a Poincaré inequality, which compares the total variance of a given function f f f ∥ L v f ∥ 2 2 = E μ [ Var ( f ∣ X − v ) ] \left\|L_vf\right\|^2_2=E_\mu[\operatorname{Var}(f\mid X_{-v})] ∥ L v f ∥ 2 2 = E μ [ Var ( f ∣ X − v )] v ∈ V v\in V v ∈ V Var μ ( f ) = ∥ ( I − E μ ) f ∥ 2 \operatorname{Var}_\mu(f)=\left\|(I-E_\mu)f\right\|^2 Var μ ( f ) = ∥ ( I − E μ ) f ∥ 2 E μ E_\mu E μ
Var μ ( f ) = ∥ ( I − E μ ) f ∥ 2 ≤ ϵ − 1 ∑ v ∈ V ∥ L v f ∥ 2 2 = ϵ − 1 ∑ v ∈ V E μ [ Var ( f ∣ X − v ) ] (5) \operatorname{Var}_\mu(f)=\left\|(I-E_\mu)f\right\|^2\le\epsilon^{-1}\sum_{v\in V}\left\|L_vf\right\|^2_2=\epsilon^{-1}\sum_{v\in V}E_\mu[\operatorname{Var}(f\mid X_{-v})] \tag*{(5)} Var μ ( f ) = ∥ ( I − E μ ) f ∥ 2 ≤ ϵ − 1 v ∈ V ∑ ∥ L v f ∥ 2 2 = ϵ − 1 v ∈ V ∑ E μ [ Var ( f ∣ X − v )] (5) for all functions f f f
The inequalities via linear algebra. The inequalities (3) and (4) can be generalized to purely linear algebraic statements about orthogonal projections. We let H = L 2 ( μ ) \mathcal{H}=L^2(\mu) H = L 2 ( μ ) ⟨ f , g ⟩ = ∑ σ μ ( σ ) f ( σ ) g ( σ ) \langle f,g\rangle=\sum_\sigma\mu(\sigma)f(\sigma)g(\sigma) ⟨ f , g ⟩ = ∑ σ μ ( σ ) f ( σ ) g ( σ ) L v L_v L v v ∈ V v\in V v ∈ V I − E μ I-E_\mu I − E μ I − E μ I-E_\mu I − E μ ∑ v ∈ V ran ( L v ) \sum_{v\in V}\operatorname{ran}(L_v) ∑ v ∈ V ran ( L v )
( ∑ v ∈ V ran ( L v ) ) ⊥ = ⋂ v ∈ V ker L v = span { 1 } . \left(\sum_{v\in V}\operatorname{ran}(L_v)\right)^\perp=\bigcap_{v\in V}\ker L_v=\operatorname{span}\{1\}. ( v ∈ V ∑ ran ( L v ) ) ⊥ = v ∈ V ⋂ ker L v = span { 1 } . We first state the abstract inequalities that give the global bound. For spin systems, this corresponds to Theorem 1 , or the case of Theorem 3 where the blocks are singleton sets covering all sites.
Proposition 8 (Bochner and Poincaré inequalities). Let P i P_i P i H \mathcal{H} H W i W_i W i i ∈ [ n ] i \in[n] i ∈ [ n ] S S S n × n n \times n n × n 1 − ϵ 1-\epsilon 1 − ϵ ϵ > 0 \epsilon> 0 ϵ > 0 P i j P_{ij} P ij P P P W i ∩ W j W_i \cap W_j W i ∩ W j ⨁ i = 1 n W i \bigoplus_{i=1}^{n} W_i ⨁ i = 1 n W i ∥ P i P j − P i j ∥ ≤ s i j \lVert P_iP_j-P_{ij}\rVert\le s_{ij} ∥ P i P j − P ij ∥ ≤ s ij i ≠ j i \ne j i = j
∥ ∑ i = 1 n P i f ∥ 2 ≥ ϵ ∑ i = 1 n ∥ P i f ∥ 2 and ∥ P f ∥ 2 ≤ ϵ − 1 ∑ i = 1 n ∥ P i f ∥ 2 \left\lVert\sum_{i=1}^{n} P_i f \right\rVert^2 \ge\epsilon\sum_{i=1}^{n} \lVert P_i f\rVert^2
\qquad\text{and}\qquad
\lVert P f\rVert^2 \le\epsilon^{-1} \sum_{i=1}^{n} \lVert P_i f\rVert^2 i = 1 ∑ n P i f 2 ≥ ϵ i = 1 ∑ n ∥ P i f ∥ 2 and ∥ P f ∥ 2 ≤ ϵ − 1 i = 1 ∑ n ∥ P i f ∥ 2 for all f ∈ H f \in\mathcal{H} f ∈ H
One interpretation of the condition ∥ P i P j − P i j ∥ ≤ s i j \lVert P_iP_j-P_{ij}\rVert\le s_{ij} ∥ P i P j − P ij ∥ ≤ s ij W i W_i W i W j W_j W j Lemma 11 . More importantly for spin systems, this condition follows from a two-site Glauber spectral-gap bound of ( 1 − s i j ) / 2 (1-s_{ij})/2 ( 1 − s ij ) /2 Theorem 1 and Theorem 3 enter the argument.
We now give the main ideas of the proof. We consider the following sequence of maps between Hilbert spaces:
H 0 → d 0 H 1 → d 1 H 2 , \mathcal{H}_0 \xrightarrow{d_0} \mathcal{H}_1 \xrightarrow{d_1} \mathcal{H}_2, H 0 d 0 H 1 d 1 H 2 , where
H 0 = H , H 1 = ⨁ i W i , H 2 = ⨁ i < j W i j , \mathcal{H}_0=\mathcal{H},\qquad
\mathcal{H}_1=\bigoplus_i W_i,\qquad
\mathcal{H}_2=\bigoplus_{i<j} W_{ij}, H 0 = H , H 1 = i ⨁ W i , H 2 = i < j ⨁ W ij , with the direct-sum inner products inherited from H \mathcal{H} H
d 0 : f ↦ ( P i f ) i and d 1 : ( f i ) i ↦ ( P i j ( f i − f j ) ) i < j . d_0:f\mapsto(P_i f)_i
\qquad\text{and}\qquad
d_1:(f_i)_i\mapsto\bigl(P_{ij}(f_i-f_j)\bigr)_{i<j}. d 0 : f ↦ ( P i f ) i and d 1 : ( f i ) i ↦ ( P ij ( f i − f j ) ) i < j . The proof of Proposition 8 then follows from analyzing a single operator B : H 1 → H 1 B:\mathcal{H}_1\to\mathcal{H}_1 B : H 1 → H 1 B = d 0 d 0 ∗ + d 1 ∗ d 1 B=d_0d_0^*+d_1^*d_1 B = d 0 d 0 ∗ + d 1 ∗ d 1 Bochner operator . One of the key facts about this operator is that its off-diagonal W j → W i W_j \to W_i W j → W i P i P j − P i j P_iP_j-P_{ij} P i P j − P ij
To see how the inequalities follow, we first observe that
d 0 ∗ : ( f i ) i ↦ ∑ i f i ⟹ d 0 ∗ d 0 = ∑ i P i . d_0^*:(f_i)_i\mapsto\sum_i f_i
\qquad\Longrightarrow\qquad
d_0^*d_0=\sum_i P_i. d 0 ∗ : ( f i ) i ↦ i ∑ f i ⟹ d 0 ∗ d 0 = i ∑ P i . Our choice of d 1 d_1 d 1 d 1 d 0 = 0 d_1d_0=0 d 1 d 0 = 0 B B B B − 1 B^{-1} B − 1 ∑ i P i \sum_i P_i ∑ i P i P P P
( ∑ i P i ) 2 = d 0 ∗ B d 0 and P = d 0 ∗ B − 1 d 0 . \left(\sum_i P_i\right)^2=d_0^*Bd_0
\qquad\text{and}\qquad
P=d_0^*B^{-1}d_0. ( i ∑ P i ) 2 = d 0 ∗ B d 0 and P = d 0 ∗ B − 1 d 0 . These are the identities underlying Lemma 20 . We are therefore left with proving B ⪰ ϵ I B \succeq\epsilon I B ⪰ ϵ I B i i ⪰ I B_{ii} \succeq I B ii ⪰ I ∥ B i j ∥ ≤ s i j \lVert B_{ij}\rVert\le s_{ij} ∥ B ij ∥ ≤ s ij λ max ( S ) ≤ 1 − ϵ \lambda_{\max}(S) \le1 - \epsilon λ m a x ( S ) ≤ 1 − ϵ B ⪰ ϵ I B \succeq\epsilon I B ⪰ ϵ I B − 1 ⪯ ϵ − 1 I B^{-1} \preceq\epsilon^{-1} I B − 1 ⪯ ϵ − 1 I
( ∑ i P i ) 2 ⪰ ϵ ∑ i P i and P ⪯ ϵ − 1 ∑ i P i . \left(\sum_i P_i\right)^2 \succeq\epsilon\sum_i P_i \quad\text{and}\quad P \preceq\epsilon^{-1}\sum_i P_i. ( i ∑ P i ) 2 ⪰ ϵ i ∑ P i and P ⪯ ϵ − 1 i ∑ P i . Taking quadratic forms and using the projection identities P i 2 = P i P_i^2 = P_i P i 2 = P i P 2 = P P^2 = P P 2 = P § 3.3 .
Finishing the proof of Theorem 3. The above argument handles Theorem 1, but how does it extend to capture all of Theorem 3?
We give a brief overview here, leaving the full proof to § 3.3 .
Recall for the general result Theorem 3, we want to analyze a collection of disjoint subsets of sites T 1 , … , T m T_1,\ldots,T_m T 1 , … , T m T = T 1 ⊔ ⋯ ⊔ T m T=T_1\sqcup\cdots\sqcup T_m T = T 1 ⊔ ⋯ ⊔ T m T a T_a T a i ∈ [ n ] i\in[n] i ∈ [ n ] H 1 = H 1 T ⊕ H 1 R \mathcal{H}_1=\mathcal{H}_1^T\oplus\mathcal{H}_1^R H 1 = H 1 T ⊕ H 1 R
H 1 T = ⨁ i ∈ T W i . \mathcal{H}_1^T=\bigoplus_{i\in T}W_i. H 1 T = i ∈ T ⨁ W i . For a function f f f T T T d 0 f d_0f d 0 f T T T P = d 0 ∗ B − 1 d 0 P=d_0^*B^{-1}d_0 P = d 0 ∗ B − 1 d 0 ∥ P f ∥ 2 \lVert Pf\rVert^2 ∥ P f ∥ 2 ( B − 1 ) T T (B^{-1})_{TT} ( B − 1 ) T T
B ~ = ( ( B − 1 ) T T ) − 1 . \widetilde{B}=\left((B^{-1})_{TT}\right)^{-1}. B = ( ( B − 1 ) T T ) − 1 . This is the Schur complement of B B B C C C M M M
Once we take Schur complement, we now have this “reduced” Bochner operator B ~ : H 1 T → H 1 T \widetilde{B}:\mathcal{H}_1^T\to\mathcal{H}_1^T B : H 1 T → H 1 T ϵ I ⪯ B ~ \epsilon I\preceq\widetilde{B} ϵ I ⪯ B T 1 , … , T m T_1,\ldots,T_m T 1 , … , T m
B ~ ⪰ α D ~ where D ~ = blockdiag ( B ~ T 1 T 1 , … , B ~ T m T m ) , \widetilde{B}\succeq\alpha\widetilde{D}\quad\text{where}\quad\widetilde{D}=\operatorname{blockdiag}(\widetilde{B}_{T_1T_1},\ldots,\widetilde{B}_{T_mT_m}), B ⪰ α D where D = blockdiag ( B T 1 T 1 , … , B T m T m ) , and where α = λ min ( D − 1 / 2 C D − 1 / 2 ) \alpha=\lambda_{\min}(D^{-1/2}CD^{-1/2}) α = λ m i n ( D − 1/2 C D − 1/2 ) D = blockdiag ( C T 1 T 1 , … , C T m T m ) D=\operatorname{blockdiag}(C_{T_1T_1},\ldots,C_{T_mT_m}) D = blockdiag ( C T 1 T 1 , … , C T m T m )
We then bring everything back to a statement about orthogonal projections. We consider projections Q ~ a \widetilde{Q}_a Q a H \mathcal{H} H T T T i ∈ T a i\in T_a i ∈ T a a ∈ [ m ] a\in[m] a ∈ [ m ] P ~ \widetilde{P} P P P P W W W
∑ a = 1 m ∥ Q ~ a f ∥ 2 ≥ α ∥ P ~ f ∥ 2 . \sum_{a=1}^{m}\lVert\widetilde{Q}_af\rVert^2\ge\alpha\lVert\widetilde{P}f\rVert^2. a = 1 ∑ m ∥ Q a f ∥ 2 ≥ α ∥ P f ∥ 2 . This is the correct analogue of Proposition 8 in this more general context which leads to the conclusion of Theorem 3. See § 3.4 for the final details which make the connection back to the Glauber dynamics.
We finally comment that the full proofs of all these results require working on a possibly infinite dimensional Hilbert space in order to be able to handle infinite spin spaces for spin systems.
Everything we discussed above immediately generalizes to this case, with the right (but standard) care taken.
The remainder of this overview is spent discussing our main applications.
The O ( N ) O(N) O ( N ) As we have already observed, the Bochner identity reduces the spectral-gap bound to controlling the cross terms ⟨ L x f , L y f ⟩ \langle L_xf,L_yf\rangle ⟨ L x f , L y f ⟩ ν ( d u , d v ) ∝ e a ⋅ u + b ⋅ v + κ u ⋅ v d ω ( u ) d ω ( v ) \nu(du,dv) \propto e^{a\cdot u+b\cdot v+\kappa u\cdot v}d\omega(u)d\omega(v) ν ( d u , d v ) ∝ e a ⋅ u + b ⋅ v + κ u ⋅ v d ω ( u ) d ω ( v ) Theorem 3 , it suffices to show that, in every codimension-2 link, the maximal correlation between U U U V V V ∣ κ ∣ / N |\kappa|/N ∣ κ ∣/ N a a a b b b § 2.3 ), this can be proved by showing that for every Lipschitz φ \varphi φ ( T φ ) ( u ) = E [ φ ( V ) ∣ U = u ] (T\varphi)(u)=\mathbb{E}[\varphi(V)\mid U=u] ( T φ ) ( u ) = E [ φ ( V ) ∣ U = u ] ∣ T φ ( u ) − T φ ( u ′ ) ∣ ≤ ∣ κ ∣ N ℓ ∥ u − u ′ ∥ |T\varphi(u)-T\varphi(u')|\leq\frac{|\kappa|}{N}\ell\|u-u'\| ∣ T φ ( u ) − T φ ( u ′ ) ∣ ≤ N ∣ κ ∣ ℓ ∥ u − u ′ ∥ Lemma 23 in § 4.2 ).
Since changing u u u V V V φ ( V ) \varphi(V) φ ( V )
d d s E ν h + s c φ ( U ) = Cov ν h + s c ( φ ( U ) , c ⋅ U ) \frac{d}{ds}\mathbb{E}_{\nu_{h+sc}}\varphi(U)=\operatorname{Cov}_{\nu_{h+sc}}(\varphi(U),c\cdot U) d s d E ν h + sc φ ( U ) = Cov ν h + sc ( φ ( U ) , c ⋅ U ) and so we are reduced to upper-bounding this covariance quantity by ∥ c ∥ Lip ( φ ) / N \|c\|\operatorname{Lip}(\varphi)/N ∥ c ∥ Lip ( φ ) / N
The case of h = 0 h=0 h = 0 Since E ν 0 U = 0 \mathbb{E}_{\nu_0}U=0 E ν 0 U = 0
∣ Cov ν 0 ( φ ( U ) , c ⋅ U ) ∣ = ∣ E ω [ φ ( U ) c ⋅ U ] ∣ = 1 N ∣ E Z ∼ Unif ( B N ) [ c ⋅ ∇ F ( Z ) ] ∣ ≤ ∥ c ∥ N Lip ( φ ) . |\operatorname{Cov}_{\nu_0}(\varphi(U),c\cdot U)|=|\mathbb{E}_{\omega}[\varphi(U)c\cdot U]|=\frac{1}{N}|\mathbb{E}_{Z\sim\operatorname{Unif}(B^N)}[c\cdot\nabla F(Z)]|\leq\frac{\|c\|}{N}\operatorname{Lip}(\varphi). ∣ Cov ν 0 ( φ ( U ) , c ⋅ U ) ∣ = ∣ E ω [ φ ( U ) c ⋅ U ] ∣ = N 1 ∣ E Z ∼ Unif ( B N ) [ c ⋅ ∇ F ( Z )] ∣ ≤ N ∥ c ∥ Lip ( φ ) . Here c ∈ R N c\in\mathbb{R}^N c ∈ R N F F F φ \varphi φ
General h h h By rotational invariance we may assume that h = t e h=te h = t e e e e h = 0 h=0 h = 0 V c V_c V c
∇ ⋅ V c = 0 and V c ( u ) ⋅ u = w ( u ) c ⋅ ( u − m t e ) where w ( z ) = e t e ⋅ z E ω [ e t e ⋅ U ] . \nabla\cdot V_c=0 \qquad\text{and}\qquad V_c(u)\cdot u=w(u)c\cdot(u-m_te) \qquad\text{where}\qquad w(z)=\frac{e^{te\cdot z}}{\mathbb{E}_{\omega}[e^{te\cdot U}]}. ∇ ⋅ V c = 0 and V c ( u ) ⋅ u = w ( u ) c ⋅ ( u − m t e ) where w ( z ) = E ω [ e t e ⋅ U ] e t e ⋅ z . Integrating by parts (or precisely, the divergence theorem) would give the following analogous expression to the above
Cov ν h ( φ ( U ) , c ⋅ U ) = 1 N E Z ∼ Unif ( B N ) [ ∇ F ( Z ) ⋅ V c ( Z ) ] . \operatorname{Cov}_{\nu_h}(\varphi(U),c\cdot U)=\frac{1}{N}\mathbb{E}_{Z\sim\operatorname{Unif}(B^N)}[\nabla F(Z)\cdot V_c(Z)]. Cov ν h ( φ ( U ) , c ⋅ U ) = N 1 E Z ∼ Unif ( B N ) [ ∇ F ( Z ) ⋅ V c ( Z )] . To that end, we split c c c e e e c = v ⊥ e c=v\perp e c = v ⊥ e h = 0 h=0 h = 0 V v = w v V_v=wv V v = w v c = e c=e c = e V V V w ( u ) ( e ⋅ u − m t ) w(u)(e\cdot u-m_t) w ( u ) ( e ⋅ u − m t ) ∇ ⋅ ( w e ) = t w \nabla\cdot(we)=tw ∇ ⋅ ( w e ) = tw
Δ A = t 2 A in B N , A = 1 on S N − 1 . \Delta A=t^2A\quad\text{in }B^N,\qquad A=1\quad\text{on }S^{N-1}. Δ A = t 2 A in B N , A = 1 on S N − 1 . The idea is that w w w Δ w = t 2 w \Delta w=t^2w Δ w = t 2 w A A A V e = A ∇ w − w ∇ A t V_e=\frac{A\nabla w-w\nabla A}{t} V e = t A ∇ w − w ∇ A S N − 1 S^{N-1} S N − 1
Negative correlations in matroids. We next consider the problem of showing negative correlations for random independent sets from a matroid. Here, it is useful to think about what L i L j − L i j L_iL_j-L_{ij} L i L j − L ij L i L j − L i j L_iL_j-L_{ij} L i L j − L ij B − 1 B^{-1} B − 1 Lemma 20 and its proof for the precise formulation.
Having this, to recover the bound p i j ≤ 2 p i p j p_{ij} \le2p_ip_j p ij ≤ 2 p i p j p i p_i p i i i i p i j p_{ij} p ij i , j i,j i , j B − 1 B^{-1} B − 1
For this application, we use the weighted inner products introduced in § 5.1 . The Bochner operator still has the form B = d 0 d 0 ∗ + d 1 ∗ d 1 B=d_0d_0^*+d_1^*d_1 B = d 0 d 0 ∗ + d 1 ∗ d 1 B ⪰ I B \succeq I B ⪰ I B − 1 ⪯ I B^{-1} \preceq I B − 1 ⪯ I
Assuming this, we use Lemma 20 which shows that Σ ⪯ diag ( p ) \Sigma\preceq\operatorname{diag}(p) Σ ⪯ diag ( p ) Σ \Sigma Σ Δ = diag ( p ) − Σ ⪰ 0 \Delta=\operatorname{diag}(p)-\Sigma\succeq0 Δ = diag ( p ) − Σ ⪰ 0 Δ i i = p i 2 \Delta_{ii}=p_i^2 Δ ii = p i 2 i ≠ j i\ne j i = j 2 × 2 2\times2 2 × 2
p i j = p i p j − Δ i j ≤ p i p j + Δ i i Δ j j = 2 p i p j . (6) p_{ij}=p_ip_j-\Delta_{ij}\le p_ip_j+\sqrt{\Delta_{ii}\Delta_{jj}}=2p_ip_j. \tag*{(6)} p ij = p i p j − Δ ij ≤ p i p j + Δ ii Δ j j = 2 p i p j . (6) It remains to justify why B ⪰ I B \succeq I B ⪰ I i , j i,j i , j S ∪ { i , j } S\cup\{i,j\} S ∪ { i , j } S S S i , j i,j i , j M / S M/S M / S (26) , shows that within each class these cross terms combine with the corresponding diagonal terms into a nonnegative square. Summing these up then gives the desired B ⪰ I B\succeq I B ⪰ I
Graphic matroids. We next consider forests, where we can improve the factor 2 to 4/3 in (5). To that end, we need a more careful analysis that uses the graphic matroid structure. As a starting point, we recall that for spanning trees, one way to prove negative correlation is from the Rayleigh inequalities after showing real stability of the spanning-tree polynomial. We can imitate such an approach in the case of forests as well.
To obtain a related polynomial construction for forests, we add an auxiliary vertex and connect it to each vertex v v v x v x_v x v G ′ G' G ′ G ′ G' G ′ z e z_e z e e e e λ e ( 1 + z e ) \lambda_e(1+z_e) λ e ( 1 + z e )
The idea is that differentiating in z e z_e z e e e e Φ \Phi Φ (30) and the proof of Proposition 31 ).
The main fact we use, proved in Proposition 31 , is that Φ \Phi Φ Φ \Phi Φ 3 p i j ≤ ( 2 p i ) ( 2 p j ) 3p_{ij}\le(2p_i)(2p_j) 3 p ij ≤ ( 2 p i ) ( 2 p j ) (22) ), we can view this as a more precise estimate on the pairings involving B − 1 B^{-1} B − 1 Φ \Phi Φ
Acknowledgments
We would like to thank Shayan Oveis Gharan for important discussions and ideas in the first stages of this paper, when the application to the O ( N ) O(N) O ( N )
AL is supported by the Computer Science & Engineering Educators’ Endowed Fellowship and the Jonathan Hsieh and Kathleen Ting Endowed Fund. JL acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2023-03726]. Cette recherche a été partiellement financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2023-03726].
The development of this framework and its applications involved substantive assistance from OpenAI’s ChatGPT. This included assistance with the Hilbert-space formulation and the proof of the general block theorem, the real-stability approach to the forest correlation bound, and the radial construction used in the covariance inequality for tilted spherical measures. We describe these contributions and our use of the tool in more detail in the AI methodology statement at the end of the paper.
Preliminaries
We collect here some standard facts that will be used later.
Linear algebra and Hilbert spaces
Throughout, we let H \mathcal{H} H ∥ A ∥ o p \lVert A\rVert_{\mathrm{op}} ∥ A ∥ op A A A A ⪯ B A \preceq B A ⪯ B ⟨ f , A f ⟩ ≤ ⟨ f , B f ⟩ \langle f,Af\rangle\le\langle f,Bf\rangle ⟨ f , A f ⟩ ≤ ⟨ f , B f ⟩ f ∈ H f \in\mathcal{H} f ∈ H U ⊆ H U \subseteq\mathcal{H} U ⊆ H P U P_U P U U U U compression of A A A U U U A U U = P U A ∣ U A_{UU}=P_UA|_U A U U = P U A ∣ U A A A
We collect the following standard facts about compressions and Schur complements of uniformly positive bounded operators; see [7 ] and [19 Section 4] .
Lemma 9 (Compression and Schur complements ). Let H = U ⊕ V \mathcal{H}=U\oplus V H = U ⊕ V orthogonal decomposition into closed subspaces , and let A A A 0 < a I ⪯ A ⪯ b I 0<aI\preceq A\preceq bI 0 < a I ⪯ A ⪯ b I
A = ( A U U A U V A V U A V V ) . A=\begin{pmatrix} A_{UU} & A_{UV} \\ A_{VU} & A_{VV} \end{pmatrix}. A = ( A U U A V U A U V A V V ) . Then the following hold.
The compressions A U U A_{UU} A U U ( A − 1 ) U U (A^{-1})_{UU} ( A − 1 ) U U
a I U ⪯ A U U ⪯ b I U , b − 1 I U ⪯ ( A − 1 ) U U ⪯ a − 1 I U . aI_U\preceq A_{UU}\preceq bI_U,\qquad b^{-1}I_U\preceq(A^{-1})_{UU}\preceq a^{-1}I_U. a I U ⪯ A U U ⪯ b I U , b − 1 I U ⪯ ( A − 1 ) U U ⪯ a − 1 I U . The operator K U = ( ( A − 1 ) U U ) − 1 K_U=((A^{-1})_{UU})^{-1} K U = (( A − 1 ) U U ) − 1
K U = A U U − A U V A V V − 1 A V U , a I U ⪯ K U ⪯ A U U ⪯ b I U . K_U=A_{UU}-A_{UV}A_{VV}^{-1}A_{VU},\qquad aI_U\preceq K_U\preceq A_{UU}\preceq bI_U. K U = A U U − A U V A V V − 1 A V U , a I U ⪯ K U ⪯ A U U ⪯ b I U . If V = { 0 } V=\{0\} V = { 0 }
For every x ∈ U x \in U x ∈ U
min P U z = x , z ∈ H ⟨ z , A − 1 z ⟩ = ⟨ x , A U U − 1 x ⟩ . \min_{P_U z=x,\ z\in\mathcal{H}} \langle z,A^{-1}z\rangle=\langle x,A_{UU}^{-1}x\rangle. P U z = x , z ∈ H min ⟨ z , A − 1 z ⟩ = ⟨ x , A U U − 1 x ⟩ . In particular, ⟨ z , A − 1 z ⟩ ≥ ⟨ P U z , A U U − 1 P U z ⟩ \langle z,A^{-1}z\rangle\ge\langle P_U z,A_{UU}^{-1}P_U z\rangle ⟨ z , A − 1 z ⟩ ≥ ⟨ P U z , A U U − 1 P U z ⟩ z ∈ H z \in\mathcal{H} z ∈ H
Moreover, compression preserves operator order, while inversion reverses operator order for bounded, uniformly positive self-adjoint operators.
We next record a standard fact about nonnegative self-adjoint operators that allows us to deduce spectral-gap bounds from the Laplacian bounds in the Bochner method.
Fact 10. Let L L L H \mathcal{H} H Π \Pi Π ( ker L ) ⊥ (\ker L)^\perp ( ker L ) ⊥ γ > 0 \gamma> 0 γ > 0
σ ( L ) ⊆ { 0 } ∪ [ γ , ∞ ) , \sigma(L) \subseteq\{0\} \cup[\gamma,\infty), σ ( L ) ⊆ { 0 } ∪ [ γ , ∞ ) , γ ∥ Π f ∥ 2 ≤ ⟨ f , L f ⟩ , γ ⟨ f , L f ⟩ ≤ ∥ L f ∥ 2 , \gamma\|\Pi f\|^2 \le\langle f,Lf\rangle,\qquad\gamma\langle f,Lf\rangle\le\|Lf\|^2, γ ∥Π f ∥ 2 ≤ ⟨ f , L f ⟩ , γ ⟨ f , L f ⟩ ≤ ∥ L f ∥ 2 , where both inequalities hold for every f ∈ H f \in\mathcal{H} f ∈ H
Proof. For g = L 1 / 2 f g=L^{1/2}f g = L 1/2 f ⟨ g , L g ⟩ = ∥ L f ∥ 2 \langle g,Lg\rangle=\|Lf\|^2 ⟨ g , Lg ⟩ = ∥ L f ∥ 2 ∥ g ∥ 2 = ⟨ f , L f ⟩ \|g\|^2=\langle f,Lf\rangle ∥ g ∥ 2 = ⟨ f , L f ⟩ γ ∥ g ∥ 2 ≤ ⟨ g , L g ⟩ \gamma\|g\|^2\le\langle g,Lg\rangle γ ∥ g ∥ 2 ≤ ⟨ g , Lg ⟩ ran L 1 / 2 \operatorname{ran}L^{1/2} ran L 1/2 ran L 1 / 2 = ( ker L ) ⊥ \operatorname{ran}L^{1/2}=(\ker L)^\perp ran L 1/2 = ( ker L ) ⊥ L L L ( ker L ) ⊥ (\ker L)^\perp ( ker L ) ⊥ ⟨ f , L f ⟩ = ⟨ Π f , L Π f ⟩ \langle f,Lf\rangle=\langle\Pi f,L\Pi f\rangle ⟨ f , L f ⟩ = ⟨ Π f , L Π f ⟩
Subspace angles
Given two non-zero vectors in a Hilbert space H \mathcal{H} H f , g ∈ H f,g \in\mathcal{H} f , g ∈ H
cos ( f , g ) : = ⟨ f , g ⟩ ∥ f ∥ ∥ g ∥ . \cos(f,g):=\frac{\langle f,g\rangle}{\|f\|\|g\|}. cos ( f , g ) := ∥ f ∥∥ g ∥ ⟨ f , g ⟩ . this comes from the usual dot product identity. This can then be generalized to (closed) subspaces in a natural way:
cos ( U , W ) = sup u ∈ U , w ∈ W u , w ⊥ U ∩ W ⟨ u , w ⟩ ∥ u ∥ ∥ w ∥ , \cos(U,W)=\sup_{\substack{u\in U,w\in W\\u,w\perp U\cap W}}\frac{\langle u,w\rangle}{\|u\|\|w\|}, cos ( U , W ) = u ∈ U , w ∈ W u , w ⊥ U ∩ W sup ∥ u ∥∥ w ∥ ⟨ u , w ⟩ , where the sup is over non-zero vectors u , w u,w u , w U U U W W W u = w u=w u = w U ∩ W U\cap W U ∩ W cos ( U , W ) \cos(U,W) cos ( U , W ) [23 ] .
We now state a standard result about how this angle can be interpreted as the norm of a natural operator associated to U U U W W W
Lemma 11 (Angle-norm equivalence). Let P i P_i P i P j P_j P j P i j P_{ij} P ij W i W_i W i W j W_j W j W i ∩ W j W_i\cap W_j W i ∩ W j
cos ( W i , W j ) = ∥ P i P j − P i j ∥ o p . \cos(W_i,W_j)=\|P_iP_j-P_{ij}\|_{\mathrm{op}}. cos ( W i , W j ) = ∥ P i P j − P ij ∥ op . Proof. Note first that
( P i − P i j ) ( P j − P i j ) = P i P j − P i j − P i j + P i j = P i P j − P i j . (P_i-P_{ij})(P_j-P_{ij})=P_iP_j-P_{ij}-P_{ij}+P_{ij}=P_iP_j-P_{ij}. ( P i − P ij ) ( P j − P ij ) = P i P j − P ij − P ij + P ij = P i P j − P ij . Since orthogonal projections are self-adjoint, we have
⟨ ( P i − P i j ) f , ( P j − P i j ) g ⟩ = ⟨ f , ( P i P j − P i j ) g ⟩ \langle(P_i-P_{ij})f,(P_j-P_{ij})g\rangle=\langle f,(P_iP_j-P_{ij})g\rangle ⟨( P i − P ij ) f , ( P j − P ij ) g ⟩ = ⟨ f , ( P i P j − P ij ) g ⟩ for all f , g ∈ H f,g\in\mathcal{H} f , g ∈ H P i − P i j P_i-P_{ij} P i − P ij P j − P i j P_j-P_{ij} P j − P ij W i W_i W i W j W_j W j W i j W_{ij} W ij
cos ( W i , W j ) = sup f , g ∈ H f , g ≠ 0 ⟨ ( P i − P i j ) f , ( P j − P i j ) g ⟩ ∥ f ∥ ∥ g ∥ = sup f , g ∈ H f , g ≠ 0 ⟨ f , ( P i P j − P i j ) g ⟩ ∥ f ∥ ∥ g ∥ = ∥ P i P j − P i j ∥ , \cos(W_i,W_j)=\sup_{\substack{f,g\in\mathcal{H}\\f,g\ne0}}\frac{\langle(P_i-P_{ij})f,(P_j-P_{ij})g\rangle}{\lVert f\rVert\lVert g\rVert}=\sup_{\substack{f,g\in\mathcal{H}\\f,g\ne0}}\frac{\langle f,(P_iP_j-P_{ij})g\rangle}{\lVert f\rVert\lVert g\rVert}=\lVert P_iP_j-P_{ij}\rVert, cos ( W i , W j ) = f , g ∈ H f , g = 0 sup ∥ f ∥ ∥ g ∥ ⟨( P i − P ij ) f , ( P j − P ij ) g ⟩ = f , g ∈ H f , g = 0 sup ∥ f ∥ ∥ g ∥ ⟨ f , ( P i P j − P ij ) g ⟩ = ∥ P i P j − P ij ∥ , as desired. Note for the first equality that we can put ∥ f ∥ ∥ g ∥ \lVert f\rVert\lVert g\rVert ∥ f ∥ ∥ g ∥ ∥ ( P i − P i j ) f ∥ ∥ ( P j − P i j ) g ∥ \lVert(P_i-P_{ij})f\rVert\lVert(P_j-P_{ij})g\rVert ∥( P i − P ij ) f ∥ ∥( P j − P ij ) g ∥ f f f g g g P i − P i j P_i-P_{ij} P i − P ij P j − P i j P_j-P_{ij} P j − P ij
Another natural property of the angle (or cosine) of two subspaces is that it should be preserved under taking orthogonal complements. Consider the simplest case, of two linear subspaces L u , L w ∈ R 2 L_u,L_w\in\mathbb{R}^2 L u , L w ∈ R 2 L u L_u L u L w L_w L w L u ⊥ L_u^\perp L u ⊥ L w ⊥ L_w^\perp L w ⊥
Lemma 12 (Orthogonal complements preserve angles [38 ] ). For closed subspaces U , W ⊆ H U,W\subseteq\mathcal{H} U , W ⊆ H
cos ( U , W ) = cos ( U ⊥ , W ⊥ ) . \cos(U,W)=\cos(U^\perp,W^\perp). cos ( U , W ) = cos ( U ⊥ , W ⊥ ) . Equivalent forms of spectral gaps
We note that we do not actually use much of this section in the rest of the paper, but we keep it here to demonstrate the connections between the various spectral-gap-like quantities that appear here and in the surrounding literature.
Let μ \mu μ Ω = ∏ i ∈ V Ω i \Omega=\prod_{i\in V}\Omega_i Ω = ∏ i ∈ V Ω i V V V Ω i \Omega_i Ω i i i i X = ( X i ) i ∈ V X=(X_i)_{i\in V} X = ( X i ) i ∈ V μ \mu μ k k k V V V R ⊆ V R\subseteq V R ⊆ V ∣ R ∣ = k \lvert R\rvert=k ∣ R ∣ = k μ τ \mu_\tau μ τ X R X_R X R X V ∖ R = τ X_{V\setminus R}=\tau X V ∖ R = τ k k k
In this section we give several equivalent interpretations of the spectral gaps of k k k
Glauber dynamics on a link. Fix ν = μ τ \nu=\mu_\tau ν = μ τ R R R
P i ν f = E ν [ f ∣ X R ∖ { i } ] and L i ν = I − P i ν . P_i^\nu f=\mathbb{E}_\nu[f\mid X_{R\setminus\{i\}}]\quad\text{and}\quad L_i^\nu=I-P_i^\nu. P i ν f = E ν [ f ∣ X R ∖ { i } ] and L i ν = I − P i ν . Both are orthogonal projections on L 2 ( ν ) L^2(\nu) L 2 ( ν )
P G l a u b , ν = 1 k ∑ i ∈ R P i ν and L G l a u b , ν = I − P G l a u b , ν = 1 k ∑ i ∈ R L i ν . P_{\mathrm{Glaub},\nu}=\frac{1}{k}\sum_{i\in R}P_i^\nu\quad\text{and}\quad L_{\mathrm{Glaub},\nu}=I-P_{\mathrm{Glaub},\nu}=\frac{1}{k}\sum_{i\in R}L_i^\nu. P Glaub , ν = k 1 i ∈ R ∑ P i ν and L Glaub , ν = I − P Glaub , ν = k 1 i ∈ R ∑ L i ν . The link is connected if ker L G l a u b , ν = ⋂ i ∈ R ker L i ν \ker L_{\mathrm{Glaub},\nu}=\bigcap_{i\in R}\ker L_i^\nu ker L Glaub , ν = ⋂ i ∈ R ker L i ν L 0 2 ( ν ) L_0^2(\nu) L 0 2 ( ν ) ν \nu ν
λ 2 ( P G l a u b , ν ) : = sup σ ( P G l a u b , ν | L 0 2 ( ν ) ) , \lambda_2(P_{\mathrm{Glaub},\nu}) := \sup\sigma\left(P_{\mathrm{Glaub},\nu}\middle|_{L_0^2(\nu)}\right), λ 2 ( P Glaub , ν ) := sup σ ( P Glaub , ν L 0 2 ( ν ) ) , λ 2 ( L G l a u b , ν ) : = inf σ ( L G l a u b , ν | L 0 2 ( ν ) ) = 1 − λ 2 ( P G l a u b , ν ) . \lambda_2(L_{\mathrm{Glaub},\nu}) := \inf\sigma\left(L_{\mathrm{Glaub},\nu}\middle|_{L_0^2(\nu)}\right)=1-\lambda_2(P_{\mathrm{Glaub},\nu}). λ 2 ( L Glaub , ν ) := inf σ ( L Glaub , ν L 0 2 ( ν ) ) = 1 − λ 2 ( P Glaub , ν ) . Because we are working over an infinite spin space, these spectral values may not actually be eigenvalues.
Maximal correlation. Given a probability measure ν \nu ν X , Y X,Y X , Y μ \mu μ Hirschfeld-Gebelein-Rényi (HGR) maximal correlation to be
ρ ν ( X , Y ) = sup f , g ∣ Cov ν ( f ( X ) , g ( Y ) ) ∣ Var ν ( f ( X ) ) Var ν ( g ( Y ) ) , (7) \rho_\nu(X,Y)=\sup_{f,g}\frac{\left|\operatorname{Cov}_\nu(f(X),g(Y))\right|}{\sqrt{\operatorname{Var}_\nu(f(X))\operatorname{Var}_\nu(g(Y))}}, \tag*{(7)} ρ ν ( X , Y ) = f , g sup Var ν ( f ( X )) Var ν ( g ( Y )) ∣ Cov ν ( f ( X ) , g ( Y )) ∣ , (7) where the supremum is over square-integrable f ∈ L 2 ( ν X ) f\in L^2(\nu_X) f ∈ L 2 ( ν X ) g ∈ L 2 ( ν Y ) g\in L^2(\nu_Y) g ∈ L 2 ( ν Y ) ν X , ν Y \nu_X,\nu_Y ν X , ν Y ρ ν ( X , Y ) \rho_\nu(X,Y) ρ ν ( X , Y )
Let U i ν U_i^\nu U i ν L 2 ( ν ) L^2(\nu) L 2 ( ν ) R ∖ { i } R\setminus\{i\} R ∖ { i } ν \nu ν i ∈ R i\in R i ∈ R
U i ν = ran P i ν ∩ L 0 2 ( ν ) . U_i^\nu=\operatorname{ran}P_i^\nu\cap L_0^2(\nu). U i ν = ran P i ν ∩ L 0 2 ( ν ) . We now extend the HGR maximal correlation to the k k k [40 , 31 ] :
c ν : = sup g i ∈ U i ν ( i ∈ R ) ∑ i ∈ R ∥ g i ∥ 2 2 > 0 ∑ i , j ∈ R i ≠ j ⟨ g i , g j ⟩ ν ( k − 1 ) ∑ i ∈ R ∥ g i ∥ 2 2 . c_\nu:=\sup_{\substack{g_i\in U_i^\nu\ (i\in R)\\ \sum_{i\in R}\lVert g_i\rVert_2^2>0}}
\frac{\sum_{\substack{i,j\in R\\i\ne j}}\langle g_i,g_j\rangle_\nu}
{(k-1)\sum_{i\in R}\lVert g_i\rVert_2^2}. c ν := g i ∈ U i ν ( i ∈ R ) ∑ i ∈ R ∥ g i ∥ 2 2 > 0 sup ( k − 1 ) ∑ i ∈ R ∥ g i ∥ 2 2 ∑ i , j ∈ R i = j ⟨ g i , g j ⟩ ν . Connection to a walk on partial configurations. We define a random walk as follows: start from a configuration on R ∖ { i } R\setminus\{i\} R ∖ { i } i i i j ∈ R ∖ { i } j\in R\setminus\{i\} j ∈ R ∖ { i } j j j S ν , 0 : ⨁ i ∈ R U i ν ⟶ ⨁ i ∈ R U i ν S_{\nu,0}:\bigoplus_{i\in R}U_i^\nu\longrightarrow\bigoplus_{i\in R}U_i^\nu S ν , 0 : ⨁ i ∈ R U i ν ⟶ ⨁ i ∈ R U i ν
( S ν , 0 g ) i = 1 k − 1 ∑ j ≠ i P i ν g j . (S_{\nu,0}g)_i=\frac{1}{k-1}\sum_{j\ne i}P_i^\nu g_j. ( S ν , 0 g ) i = k − 1 1 j = i ∑ P i ν g j . For g , h ∈ ⨁ i ∈ R U i ν g,h\in\bigoplus_{i\in R}U_i^\nu g , h ∈ ⨁ i ∈ R U i ν
⟨ g , h ⟩ ⊕ : = ∑ i ∈ R ⟨ g i , h i ⟩ ν . \langle g,h\rangle_\oplus:=\sum_{i\in R}\langle g_i,h_i\rangle_\nu. ⟨ g , h ⟩ ⊕ := i ∈ R ∑ ⟨ g i , h i ⟩ ν . Since g i , h i ∈ U i ν g_i,h_i\in U_i^\nu g i , h i ∈ U i ν P i ν g i = g i P_i^\nu g_i=g_i P i ν g i = g i P i ν h i = h i P_i^\nu h_i=h_i P i ν h i = h i P i ν P_i^\nu P i ν i , j i,j i , j
⟨ g , S ν , 0 h ⟩ ⊕ = 1 k − 1 ∑ i ≠ j ⟨ g i , P i ν h j ⟩ ν = 1 k − 1 ∑ i ≠ j ⟨ g i , h j ⟩ ν = 1 k − 1 ∑ i ≠ j ⟨ P i ν g j , h i ⟩ ν = ⟨ S ν , 0 g , h ⟩ ⊕ . \langle g,S_{\nu,0}h\rangle_\oplus
=\frac{1}{k-1}\sum_{i\ne j}\langle g_i,P_i^\nu h_j\rangle_\nu
=\frac{1}{k-1}\sum_{i\ne j}\langle g_i,h_j\rangle_\nu
=\frac{1}{k-1}\sum_{i\ne j}\langle P_i^\nu g_j,h_i\rangle_\nu
=\langle S_{\nu,0}g,h\rangle_\oplus. ⟨ g , S ν , 0 h ⟩ ⊕ = k − 1 1 i = j ∑ ⟨ g i , P i ν h j ⟩ ν = k − 1 1 i = j ∑ ⟨ g i , h j ⟩ ν = k − 1 1 i = j ∑ ⟨ P i ν g j , h i ⟩ ν = ⟨ S ν , 0 g , h ⟩ ⊕ . showing that S ν , 0 S_{\nu,0} S ν , 0
sup σ ( S ν , 0 ) = c ν . (8) \sup\sigma(S_{\nu,0}) = c_\nu. \tag*{(8)} sup σ ( S ν , 0 ) = c ν . (8) For two sites, this is the bipartite walk that alternates between sampling Y Y Y X X X X X X Y Y Y ν \nu ν T ν : L 0 2 ( ν Y ) ⟶ L 0 2 ( ν X ) T_\nu: L_0^2(\nu_Y) \longrightarrow L_0^2(\nu_X) T ν : L 0 2 ( ν Y ) ⟶ L 0 2 ( ν X ) ( T ν g ) ( x ) = E ν [ g ( Y ) ∣ X = x ] (T_\nu g)(x) = \mathbb{E}_\nu[g(Y) \mid X=x] ( T ν g ) ( x ) = E ν [ g ( Y ) ∣ X = x ] ρ ν ( X , Y ) = ∥ T ν ∥ o p \rho_\nu(X,Y) = \lVert T_\nu\rVert_{\mathrm{op}} ρ ν ( X , Y ) = ∥ T ν ∥ op g ∈ L 0 2 ( ν X ) g \in L_0^2(\nu_X) g ∈ L 0 2 ( ν X ) h ∈ L 0 2 ( ν Y ) h \in L_0^2(\nu_Y) h ∈ L 0 2 ( ν Y )
( g h ) ⟼ ( E ν [ h ( Y ) ∣ X ] E ν [ g ( X ) ∣ Y ] ) = ( 0 T ν T ν ∗ 0 ) ( g h ) . \begin{pmatrix} g \\ h \end{pmatrix}
\longmapsto
\begin{pmatrix} \mathbb{E}_\nu[h(Y)\mid X] \\ \mathbb{E}_\nu[g(X)\mid Y] \end{pmatrix}
=
\begin{pmatrix} 0 & T_\nu\\ T_\nu^* & 0 \end{pmatrix}
\begin{pmatrix} g \\ h \end{pmatrix}. ( g h ) ⟼ ( E ν [ h ( Y ) ∣ X ] E ν [ g ( X ) ∣ Y ] ) = ( 0 T ν ∗ T ν 0 ) ( g h ) . Its spectrum is symmetric about zero, so its largest spectral value is ∥ T ν ∥ o p = ρ ν ( X , Y ) \lVert T_\nu\rVert_{\mathrm{op}} = \rho_\nu(X,Y) ∥ T ν ∥ op = ρ ν ( X , Y ) c ν = ρ ν ( X , Y ) c_\nu= \rho_\nu(X,Y) c ν = ρ ν ( X , Y ) k = 2 k=2 k = 2
Conditional-expectation and Laplacian angles. Finally, on ⨁ i ∈ R L 0 2 ( ν ) \bigoplus_{i\in R} L_0^2(\nu) ⨁ i ∈ R L 0 2 ( ν )
P ν = diag ( P i ν ) i ∈ R , and L ν = diag ( L i ν ) i ∈ R = I − P ν . P_\nu= \operatorname{diag}(P_i^\nu)_{i\in R}, \qquad\text{and} \qquad L_\nu= \operatorname{diag}(L_i^\nu)_{i\in R} = I-P_\nu. P ν = diag ( P i ν ) i ∈ R , and L ν = diag ( L i ν ) i ∈ R = I − P ν . Let Π Δ ν \Pi_{\Delta_\nu} Π Δ ν Δ ν = { ( f , … , f ) : f ∈ L 0 2 ( ν ) } \Delta_\nu= \{(f,\ldots,f): f\in L_0^2(\nu)\} Δ ν = {( f , … , f ) : f ∈ L 0 2 ( ν )}
Π Δ ν ( g i ) i ∈ R = ( 1 k ∑ i g i , … , 1 k ∑ i g i ) . \Pi_{\Delta_\nu}(g_i)_{i\in R} =
\left(\frac{1}{k}\sum_i g_i,\ldots,\frac{1}{k}\sum_i g_i\right). Π Δ ν ( g i ) i ∈ R = ( k 1 i ∑ g i , … , k 1 i ∑ g i ) . We let Π N ν \Pi_{N_\nu} Π N ν
N ν = { ( g i ) i ∈ R : g i ∈ ran L i ν , ∑ i g i = 0 } . N_\nu= \left\{(g_i)_{i\in R}: g_i\in\operatorname{ran}L_i^\nu,\ \sum_i g_i=0\right\}. N ν = { ( g i ) i ∈ R : g i ∈ ran L i ν , i ∑ g i = 0 } . For i ≠ j i\ne j i = j P i j ν P_{ij}^\nu P ij ν L i j ν L_{ij}^\nu L ij ν ran P i ν ∩ ran P j ν \operatorname{ran}P_i^\nu\cap\operatorname{ran}P_j^\nu ran P i ν ∩ ran P j ν ran L i ν ∩ ran L j ν \operatorname{ran}L_i^\nu\cap\operatorname{ran}L_j^\nu ran L i ν ∩ ran L j ν
We are now ready to state the equivalent forms of the spectral gap on a k k k
Lemma 13 (Equivalent forms of link spectral gaps). Let ν = μ τ \nu=\mu_\tau ν = μ τ k k k k ≥ 2 k\ge2 k ≥ 2 0 ≤ γ < 1 0\le\gamma<1 0 ≤ γ < 1
Glauber dynamics spectral gap: λ 2 ( L G l a u b , ν ) ≥ ( 1 − γ ) / k \lambda_2(L_{\mathrm{Glaub},\nu})\ge(1-\gamma)/k λ 2 ( L Glaub , ν ) ≥ ( 1 − γ ) / k λ 2 ( P G l a u b , ν ) ≤ 1 − ( 1 − γ ) / k \lambda_2(P_{\mathrm{Glaub},\nu})\le1-(1-\gamma)/k λ 2 ( P Glaub , ν ) ≤ 1 − ( 1 − γ ) / k
Generalized correlation:
c ν ≤ k − 2 + γ k − 1 ; c_\nu\le\frac{k-2+\gamma}{k-1}; c ν ≤ k − 1 k − 2 + γ ; Partial-configuration walk:
sup σ ( S ν , 0 ) ≤ k − 2 + γ k − 1 ; \sup\sigma(S_{\nu,0}) \le\frac{k-2+\gamma}{k-1}; sup σ ( S ν , 0 ) ≤ k − 1 k − 2 + γ ; Conditional-expectation:
∥ P ν Π Δ ν ∥ o p 2 ≤ 1 − 1 − γ k ; \lVert P_\nu\Pi_{\Delta_\nu}\rVert_{\mathrm{op}}^2 \le1-\frac{1-\gamma}{k}; ∥ P ν Π Δ ν ∥ op 2 ≤ 1 − k 1 − γ ; 5. Laplacian:
∥ L ν ( I − Π Δ ν ) − Π N ν ∥ o p 2 ≤ 1 − 1 − γ k . \lVert L_\nu(I-\Pi_{\Delta_\nu})-\Pi_{N_\nu}\rVert_{\mathrm{op}}^2 \le1-\frac{1-\gamma}{k}. ∥ L ν ( I − Π Δ ν ) − Π N ν ∥ op 2 ≤ 1 − k 1 − γ . As an example, when k = 2 k=2 k = 2 R = { i , j } R=\{i,j\} R = { i , j } (7) , and
c ν = ρ ν ( X i , X j ) = ∥ P i ν P j ν − P i j ν ∥ o p = ∥ L i ν L j ν − L i j ν ∥ o p . c_\nu=\rho_\nu(X_i,X_j)=\lVert P_i^\nu P_j^\nu-P_{ij}^\nu\rVert_{\mathrm{op}}=\lVert L_i^\nu L_j^\nu-L_{ij}^\nu\rVert_{\mathrm{op}}. c ν = ρ ν ( X i , X j ) = ∥ P i ν P j ν − P ij ν ∥ op = ∥ L i ν L j ν − L ij ν ∥ op . Proof. Define A : L 0 2 ( ν ) ⟶ ⨁ i ∈ R U i ν A:L_0^2(\nu)\longrightarrow\bigoplus_{i\in R}U^ \nu_i A : L 0 2 ( ν ) ⟶ ⨁ i ∈ R U i ν A f = ( P i ν f ) i ∈ R Af=(P_i^\nu f)_{i\in R} A f = ( P i ν f ) i ∈ R A ∗ ( g i ) = ∑ i g i A^*(g_i)=\sum_i g_i A ∗ ( g i ) = ∑ i g i
A ∗ A = k P G l a u b , ν , A A ∗ = I + ( k − 1 ) S ν , 0 . A^*A=kP_{\mathrm{Glaub},\nu},\qquad AA^*=I+(k-1)S_{\nu,0}. A ∗ A = k P Glaub , ν , A A ∗ = I + ( k − 1 ) S ν , 0 . Since A ∗ A A^*A A ∗ A A A ∗ AA^* A A ∗ (8) implies that
k λ 2 ( P G l a u b , ν ) = 1 + ( k − 1 ) c ν and λ 2 ( L G l a u b , ν ) = k − 1 k ( 1 − c ν ) . k\lambda_2(P_{\mathrm{Glaub},\nu})=1+(k-1)c_\nu\qquad\text{and}\qquad\lambda_2(L_{\mathrm{Glaub},\nu})=\frac{k-1}{k}(1-c_\nu). k λ 2 ( P Glaub , ν ) = 1 + ( k − 1 ) c ν and λ 2 ( L Glaub , ν ) = k k − 1 ( 1 − c ν ) . This proves the equivalence of the first three conditions.
To relate these to the other two properties, we define the isometry J : L 0 2 ( ν ) ⟶ ⨁ i ∈ R L 0 2 ( ν ) J:L_0^2(\nu)\longrightarrow\bigoplus_{i\in R}L_0^2(\nu) J : L 0 2 ( ν ) ⟶ ⨁ i ∈ R L 0 2 ( ν ) J f = 1 k ( f , … , f ) Jf=\frac{1}{\sqrt{k}}(f,\ldots,f) J f = k 1 ( f , … , f ) Π Δ ν = J J ∗ \Pi_{\Delta_\nu}=JJ^* Π Δ ν = J J ∗ f ∈ L 0 2 ( ν ) f\in L_0^2(\nu) f ∈ L 0 2 ( ν )
( J ∗ P ν J ) f = 1 k ∑ i P i ν f = P G l a u b , ν f . (J^*P_\nu J)f=\frac{1}{k}\sum_i P_i^\nu f=P_{\mathrm{Glaub},\nu}f. ( J ∗ P ν J ) f = k 1 i ∑ P i ν f = P Glaub , ν f . Having this, we write
∥ P ν Π Δ ν ∥ o p = ∥ Π Δ ν P ν Π Δ ν ∥ o p = ∥ J ∗ P ν J ∥ o p = λ 2 ( P G l a u b , ν ) . \lVert P_\nu\Pi_{\Delta_\nu}\rVert_{\mathrm{op}}=\lVert\Pi_{\Delta_\nu}P_\nu\Pi_{\Delta_\nu}\rVert_{\mathrm{op}}=\lVert J^*P_\nu J\rVert_{\mathrm{op}}=\lambda_2(P_{\mathrm{Glaub},\nu}). ∥ P ν Π Δ ν ∥ op = ∥ Π Δ ν P ν Π Δ ν ∥ op = ∥ J ∗ P ν J ∥ op = λ 2 ( P Glaub , ν ) . Note that the preceding computations did not use the connectedness of the link. That condition is precisely that ⋂ i ∈ R ran P i ν = span { 1 } \bigcap_{i\in R}\operatorname{ran}P_i^\nu=\operatorname{span}\{1\} ⋂ i ∈ R ran P i ν = span { 1 } ran P ν ∩ ran Π Δ ν = { 0 } \operatorname{ran}P_\nu\cap\operatorname{ran}\Pi_{\Delta_\nu}=\{0\} ran P ν ∩ ran Π Δ ν = { 0 } ran Π Δ ν \operatorname{ran}\Pi_{\Delta_\nu} ran Π Δ ν ( f , … , f ) (f,\ldots,f) ( f , … , f ) f ∈ L 0 2 ( ν ) f\in L_0^2(\nu) f ∈ L 0 2 ( ν ) ran P ν \operatorname{ran}P_\nu ran P ν i ∈ R i\in R i ∈ R P i ν f = f P_i^\nu f=f P i ν f = f f f f f f f f ≡ 0 f\equiv0 f ≡ 0
Now, since N ν = ran L ν ∩ ran ( I − Π Δ ν ) N_\nu=\operatorname{ran}L_\nu\cap\operatorname{ran}(I-\Pi_{\Delta_\nu}) N ν = ran L ν ∩ ran ( I − Π Δ ν )
∥ P ν Π Δ ν ∥ o p = cos ( ran P ν , ran Π Δ ν ) = cos ( ( ran P ν ) ⊥ , ( ran Π Δ ν ) ⊥ ) = cos ( ran L ν , ran ( I − Π Δ ν ) ) = ∥ L ν ( I − Π Δ ν ) − Π N ν ∥ o p . \begin{aligned}
\lVert P_\nu\Pi_{\Delta_\nu}\rVert_{\mathrm{op}}
&=\cos(\operatorname{ran}P_\nu,\operatorname{ran}\Pi_{\Delta_\nu}) \\
&=\cos((\operatorname{ran}P_\nu)^\perp,(\operatorname{ran}\Pi_{\Delta_\nu})^\perp) \\
&=\cos(\operatorname{ran}L_\nu,\operatorname{ran}(I-\Pi_{\Delta_\nu})) \\
&=\lVert L_\nu(I-\Pi_{\Delta_\nu})-\Pi_{N_\nu}\rVert_{\mathrm{op}}.
\end{aligned} ∥ P ν Π Δ ν ∥ op = cos ( ran P ν , ran Π Δ ν ) = cos (( ran P ν ) ⊥ , ( ran Π Δ ν ) ⊥ ) = cos ( ran L ν , ran ( I − Π Δ ν )) = ∥ L ν ( I − Π Δ ν ) − Π N ν ∥ op . This proves the remaining equivalences and completes the proof.
Connection to local spectral expansion
Here we show the connection back to local spectral expansion and spectral gaps for the base graphs of links of high-dimensional expanders. The following lemma is the crucial connection of the above notions which yields the proof of Corollary 6.
Lemma 14 (Multipartite comparison; see Proposition 30 of [35 ] ). Fix k ≥ 2 k\ge2 k ≥ 2 ( Y 1 , … , Y k ) (Y_1,\ldots,Y_k) ( Y 1 , … , Y k ) μ \mu μ W W W k k k
λ 2 ( W ) ≤ max a ≠ b ρ μ ( Y a , Y b ) . \lambda_2(W)\le\max_{a\ne b}\rho_\mu(Y_a,Y_b). λ 2 ( W ) ≤ a = b max ρ μ ( Y a , Y b ) . This follows from the multipartite comparison in Proposition 30 of [35 ] , since the graph K K K λ 2 ( W τ ) \lambda_2(W_\tau) λ 2 ( W τ ) τ \tau τ H U H_U H U ( 1 − λ max ( H U ) ) / 2 (1-\lambda_{\max}(H_U))/2 ( 1 − λ m a x ( H U )) /2
λ 2 ( W τ ) ≤ λ max ( H U ) ≤ λ max ( H ) , \lambda_2(W_\tau) \le\lambda_{\max}(H_U) \le\lambda_{\max}(H), λ 2 ( W τ ) ≤ λ m a x ( H U ) ≤ λ m a x ( H ) , as required.
Vector calculus
We write ∇ \nabla ∇ div \operatorname{div} div Δ \Delta Δ B N \mathbb{B}^N B N R N \mathbb{R}^N R N ω \omega ω S N − 1 \mathbb{S}^{N-1} S N − 1 ω N \omega_N ω N B N \mathbb{B}^N B N
We next recall the divergence theorem. We will apply the divergence theorem to Lipschitz functions which are initially defined only on the sphere. To that end, we first extend such functions to the whole unit ball without increasing the Lipschitz constant.
Proposition 15 (McShane-Whitney extension theorem). Let f : S N − 1 → R f:\mathbb{S}^{N-1}\to\mathbb{R} f : S N − 1 → R ℓ \ell ℓ f f f ℓ \ell ℓ R N \mathbb{R}^N R N
F ( x ) = inf u ∈ S N − 1 ( f ( u ) + ℓ ∥ x − u ∥ ) . F(x)=\inf_{u\in\mathbb{S}^{N-1}}\left(f(u)+\ell\lVert x-u\rVert\right). F ( x ) = u ∈ S N − 1 inf ( f ( u ) + ℓ ∥ x − u ∥ ) . In particular, F ∣ S N − 1 = f F|_{\mathbb{S}^{N-1}}=f F ∣ S N − 1 = f F F F ∥ ∇ F ∥ ≤ ℓ \lVert\nabla F\rVert\le\ell ∥ ∇ F ∥ ≤ ℓ
Using this extension, we can state the divergence theorem for Lipschitz functions on R N \mathbb{R}^N R N
Proposition 16 (Divergence theorem). Let F : R N → R F:\mathbb{R}^N\to\mathbb{R} F : R N → R V ∈ C 1 ( B N ‾ ; R N ) V\in C^1(\overline{\mathbb{B}^N};\mathbb{R}^N) V ∈ C 1 ( B N ; R N )
∫ S N − 1 F ( u ) V ( u ) ⋅ u d ω ( u ) = 1 N ω N ∫ B N ( ∇ F ⋅ V + F div V ) d x . \int_{\mathbb{S}^{N-1}} F(u)V(u)\cdot u\,d\omega(u)
=
\frac{1}{N\omega_N}\int_{\mathbb{B}^N}\left(\nabla F\cdot V+F\operatorname{div}V\right)\,dx. ∫ S N − 1 F ( u ) V ( u ) ⋅ u d ω ( u ) = N ω N 1 ∫ B N ( ∇ F ⋅ V + F div V ) d x . Consequently, if div V = 0 \operatorname{div}V=0 div V = 0 B N \mathbb{B}^N B N g ( u ) = V ( u ) ⋅ u g(u)=V(u)\cdot u g ( u ) = V ( u ) ⋅ u S N − 1 \mathbb{S}^{N-1} S N − 1 ℓ \ell ℓ f : S N − 1 → R f:\mathbb{S}^{N-1}\to\mathbb{R} f : S N − 1 → R
∣ ∫ S N − 1 f g d ω ∣ ≤ ℓ N ω N ∫ B N ∥ V ( x ) ∥ d x . \left|\int_{\mathbb{S}^{N-1}}fg\,d\omega\right|
\le
\frac{\ell}{N\omega_N}\int_{\mathbb{B}^N}\lVert V(x)\rVert\,dx. ∫ S N − 1 f g d ω ≤ N ω N ℓ ∫ B N ∥ V ( x )∥ d x . Proof. For smooth F F F F V FV F V F F F ∣ ∇ F ⋅ V ∣ ≤ ℓ ∥ V ∥ |\nabla F\cdot V|\le\ell\lVert V\rVert ∣∇ F ⋅ V ∣ ≤ ℓ ∥ V ∥
Real stable polynomials
A polynomial f ∈ R [ z 1 , … , z d ] f \in\mathbb{R}[z_1,\ldots,z_d] f ∈ R [ z 1 , … , z d ] real stable if f ( z 1 , … , z d ) ≠ 0 f(z_1,\ldots,z_d) \ne0 f ( z 1 , … , z d ) = 0 Im z i > 0 \operatorname{Im} z_i > 0 Im z i > 0 i i i multiaffine if it has degree at most one in each variable. Real stability is preserved by products, partial differentiation, and specialization of variables to real constants [46 Section 6] .
We will use the following inequalities, usually called the Rayleigh inequalities (see for example [Brä07]).
Fact 17 (Rayleigh inequalities). If f ∈ R [ z 1 , … , z d ] f \in\mathbb{R}[z_1,\ldots,z_d] f ∈ R [ z 1 , … , z d ]
( ∂ i f ) ( x ) ( ∂ j f ) ( x ) ≥ f ( x ) ( ∂ i ∂ j f ) ( x ) ( x ∈ R d , i ≠ j ) . (\partial_i f)(x)(\partial_j f)(x) \ge f(x)(\partial_i\partial_j f)(x) \qquad(x \in\mathbb{R}^d,\ i \ne j). ( ∂ i f ) ( x ) ( ∂ j f ) ( x ) ≥ f ( x ) ( ∂ i ∂ j f ) ( x ) ( x ∈ R d , i = j ) . At points where f ( x ) > 0 f(x) > 0 f ( x ) > 0 ∂ i ∂ j log f ( x ) ≤ 0 \partial_i\partial_j \log f(x) \le0 ∂ i ∂ j log f ( x ) ≤ 0
We also record the following consequence of the Lieb-Sokal differential rule which tells about one operation that preserves real stability (see for example [46 ] ).
Fact 18. Suppose that f f f x u , x v x_u,x_v x u , x v u ≠ v u \ne v u = v c ≥ 0 c \ge0 c ≥ 0 ( 1 − c ∂ x u ∂ x v ) f (1-c\,\partial_{x_u}\partial_{x_v})f ( 1 − c ∂ x u ∂ x v ) f
We will also use the following log-concavity consequence of real stability for polynomials with nonnegative coefficients (for a proof see for example [5 ] ).
Fact 19 (Log-concavity). Let f ∈ R [ z 1 , … , z d ] f \in\mathbb{R}[z_1,\ldots,z_d] f ∈ R [ z 1 , … , z d ] log f \log f log f R > 0 d \mathbb{R}^d_{>0} R > 0 d x ∈ R > 0 d x \in\mathbb{R}^d_{>0} x ∈ R > 0 d ∇ 2 log f ( x ) ⪯ 0 \nabla^2 \log f(x) \preceq0 ∇ 2 log f ( x ) ⪯ 0 x ∈ R ≥ 0 d x \in\mathbb{R}^d_{\ge0} x ∈ R ≥ 0 d f ( x ) > 0 f(x)>0 f ( x ) > 0
Orthogonal Projections and the Proofs of Theorems 1 and 3
In this section, we prove our main technical results, which give local-to-global type results for orthogonal projections on Hilbert spaces. These general results then imply our main result Theorem 3 and also Theorem 1 along the way. We start with a warm-up result in Section 3.1, and then state and prove the main technical result Theorem 21. Finally in Section 3.4 we use this to prove Theorem 3.
Before moving on, we note that some of the bounds developed below can be obtained from Kassabov’s results on angles between subspaces (Theorem 5.1 and Section 5.2 of [38 ] ), applied to the kernels of the orthogonal projections we study. In particular, his subspace-angle estimates imply the global Poincaré bound and, through successive intersections, the projection norm bounds in Theorem 21 for singleton sets T i T_i T i M M M
A warm-up result
We first prove very general bounds on the Bochner operator discussed in Section 1.6 above, along with a few nice identities which we will make use of in proving the full result in Theorem 21.
Lemma 20 (Bochner operator lemma). Let ( H i , ⟨ ⋅ , ⋅ ⟩ i ) (\mathcal{H}_i,\langle\cdot,\cdot\rangle_i) ( H i , ⟨ ⋅ , ⋅ ⟩ i ) i ∈ { 0 , 1 , 2 } i \in\{0,1,2\} i ∈ { 0 , 1 , 2 } d 0 : H 0 → H 1 d_0:\mathcal{H}_0\to\mathcal{H}_1 d 0 : H 0 → H 1 d 1 : H 1 → H 2 d_1:\mathcal{H}_1\to\mathcal{H}_2 d 1 : H 1 → H 2 d 1 d 0 = 0 d_1d_0=0 d 1 d 0 = 0 Q : H 0 → H 0 Q:\mathcal{H}_0\to\mathcal{H}_0 Q : H 0 → H 0 B : H 1 → H 1 B:\mathcal{H}_1\to\mathcal{H}_1 B : H 1 → H 1
Q = d 0 ∗ d 0 and B = d 0 d 0 ∗ + d 1 ∗ d 1 . Q=d_0^{*}d_0 \qquad\text{and}\qquad B=d_0d_0^{*}+d_1^{*}d_1. Q = d 0 ∗ d 0 and B = d 0 d 0 ∗ + d 1 ∗ d 1 . If B ⪰ α I B\succeq\alpha I B ⪰ α I α > 0 \alpha>0 α > 0 B B B
Q 2 = d 0 ∗ B d 0 ⪰ α Q and P = d 0 ∗ B − 1 d 0 ⪯ α − 1 Q . Q^2=d_0^{*}Bd_0\succeq\alpha Q \qquad\text{and}\qquad P=d_0^{*}B^{-1}d_0\preceq\alpha^{-1}Q. Q 2 = d 0 ∗ B d 0 ⪰ α Q and P = d 0 ∗ B − 1 d 0 ⪯ α − 1 Q . where P P P ( ker d 0 ) ⊥ (\ker d_0)^\perp ( ker d 0 ) ⊥
Proof. Since B B B B ⪰ α I B\succeq\alpha I B ⪰ α I α > 0 \alpha>0 α > 0 B − 1 ⪯ α − 1 I B^{-1}\preceq\alpha^{-1}I B − 1 ⪯ α − 1 I
We first compute some operator identities. We have
B d 0 = d 0 d 0 ∗ d 0 + d 1 ∗ d 1 d 0 = d 0 Q . Bd_0=d_0d_0^{*}d_0+d_1^{*}d_1d_0=d_0Q. B d 0 = d 0 d 0 ∗ d 0 + d 1 ∗ d 1 d 0 = d 0 Q . which implies Q 2 = d 0 ∗ B d 0 Q^2=d_0^{*}Bd_0 Q 2 = d 0 ∗ B d 0
d 0 ∗ B − 1 d 0 Q = d 0 ∗ B − 1 B d 0 = d 0 ∗ d 0 = Q . d_0^{*}B^{-1}d_0Q=d_0^{*}B^{-1}Bd_0=d_0^{*}d_0=Q. d 0 ∗ B − 1 d 0 Q = d 0 ∗ B − 1 B d 0 = d 0 ∗ d 0 = Q . Thus d 0 ∗ B − 1 d 0 d_0^{*}B^{-1}d_0 d 0 ∗ B − 1 d 0 ran ( Q ) \operatorname{ran}(Q) ran ( Q ) d 0 ∗ B − 1 d 0 d_0^{*}B^{-1}d_0 d 0 ∗ B − 1 d 0 ker d 0 \ker d_0 ker d 0 Q Q Q ( ker d 0 ) ⊥ = ( ker Q ) ⊥ = ran ( Q ) (\ker d_0)^\perp=(\ker Q)^\perp=\operatorname{ran}(Q) ( ker d 0 ) ⊥ = ( ker Q ) ⊥ = ran ( Q ) P = d 0 ∗ B − 1 d 0 P=d_0^{*}B^{-1}d_0 P = d 0 ∗ B − 1 d 0 d 0 ∗ B − 1 d 0 d_0^{*}B^{-1}d_0 d 0 ∗ B − 1 d 0
With these identities, we now prove the desired operator inequalities. We have
Q 2 = d 0 ∗ B d 0 ⪰ α d 0 ∗ d 0 = α Q and P = d 0 ∗ B − 1 d 0 ⪯ α − 1 d 0 ∗ d 0 = α − 1 Q Q^2=d_0^{*}Bd_0\succeq\alpha d_0^{*}d_0=\alpha Q
\qquad\text{and}\qquad
P=d_0^{*}B^{-1}d_0\preceq\alpha^{-1}d_0^{*}d_0=\alpha^{-1}Q Q 2 = d 0 ∗ B d 0 ⪰ α d 0 ∗ d 0 = α Q and P = d 0 ∗ B − 1 d 0 ⪯ α − 1 d 0 ∗ d 0 = α − 1 Q as desired.
General result
We now prove our main technical result on Hilbert space projections, which leads to our main result Theorem 3. We first need a bit of setup.
Let H \mathcal{H} H W 1 , … , W n ⊆ H W_1,\ldots,W_n\subseteq\mathcal{H} W 1 , … , W n ⊆ H P 1 , … , P n P_1,\ldots,P_n P 1 , … , P n W 1 , … , W n W_1,\ldots,W_n W 1 , … , W n P i j P_{ij} P ij W i j = W i ∩ W j W_{ij}=W_i\cap W_j W ij = W i ∩ W j i ≠ j i\ne j i = j W = ∑ i = 1 n W i W=\sum_{i=1}^{n}W_i W = ∑ i = 1 n W i P P P W W W
Additionally, we fix disjoint nonempty subsets T 1 , … , T m ⊂ [ n ] T_1,\ldots,T_m\subset[n] T 1 , … , T m ⊂ [ n ] T = T 1 ⊔ ⋯ ⊔ T m T=T_1\sqcup\cdots\sqcup T_m T = T 1 ⊔ ⋯ ⊔ T m H T = ⋂ i ∉ T W i ⊥ \mathcal{H}^{T}=\bigcap_{i\notin T}W_i^\perp H T = ⋂ i ∈ / T W i ⊥
W ~ i = H T ∩ ( H T ∩ W i ⊥ ) ⊥ , \widetilde{W}_i=\mathcal{H}^{T}\cap(\mathcal{H}^{T}\cap W_i^\perp)^\perp, W i = H T ∩ ( H T ∩ W i ⊥ ) ⊥ , and define P ~ i : H T → H T \widetilde{P}_i:\mathcal{H}^{T}\to\mathcal{H}^{T} P i : H T → H T W ~ i \widetilde{W}_i W i i ∈ [ n ] i\in[n] i ∈ [ n ] Q ~ a : H T → H T \widetilde{Q}_a:\mathcal{H}^{T}\to\mathcal{H}^{T} Q a : H T → H T ∑ i ∈ T a W ~ i \sum_{i\in T_a}\widetilde{W}_i ∑ i ∈ T a W i a ∈ [ m ] a\in[m] a ∈ [ m ] P ~ : H T → H T \widetilde{P}:\mathcal{H}^{T}\to\mathcal{H}^{T} P : H T → H T ∑ i ∈ T W ~ i \sum_{i\in T}\widetilde{W}_i ∑ i ∈ T W i
Theorem 21. Let notation be as above, and suppose that ∥ P i P j − P i j ∥ ≤ s i j \lVert P_iP_j-P_{ij}\rVert\le s_{ij} ∥ P i P j − P ij ∥ ≤ s ij i ≠ j i\ne j i = j S S S
M = I − S , C = ( ( M − 1 ) T ) − 1 , D = blockdiag ( C T 1 , … , C T m ) M=I-S,\qquad C=((M^{-1})^{\mathsf T})^{-1},\qquad D=\operatorname{blockdiag}(C_{T_1},\ldots,C_{T_m}) M = I − S , C = (( M − 1 ) T ) − 1 , D = blockdiag ( C T 1 , … , C T m ) and
α = λ min ( D − 1 / 2 C D − 1 / 2 ) . \alpha=\lambda_{\min}(D^{-1/2}CD^{-1/2}). α = λ m i n ( D − 1/2 C D − 1/2 ) . Then
∥ P ~ f ∥ 2 ≤ α − 1 ∑ a = 1 m ∥ Q ~ a f ∥ 2 \lVert\widetilde{P}f\rVert^2\le\alpha^{-1}\sum_{a=1}^{m}\lVert\widetilde{Q}_af\rVert^2 ∥ P f ∥ 2 ≤ α − 1 a = 1 ∑ m ∥ Q a f ∥ 2 for all f ∈ H T f\in\mathcal{H}^{T} f ∈ H T
The assumption of ∥ P i P j − P i j ∥ ≤ s i j \lVert P_iP_j-P_{ij}\rVert\le s_{ij} ∥ P i P j − P ij ∥ ≤ s ij P i P_i P i P j P_j P j W i W_i W i W j W_j W j W i W_i W i W j W_j W j W i ∩ W j W_i\cap W_j W i ∩ W j § 2.3 .
Proof of Theorem 21
Hilbert spaces and maps between them. Define
H 0 = H , H 1 = ⨁ i W i , H 2 = ⨁ i < j W i j \mathcal{H}_0=\mathcal{H},\qquad\mathcal{H}_1=\bigoplus_i W_i,\qquad\mathcal{H}_2=\bigoplus_{i<j}W_{ij} H 0 = H , H 1 = i ⨁ W i , H 2 = i < j ⨁ W ij with inner products given by
⟨ f , g ⟩ 0 = ⟨ f , g ⟩ H , ⟨ ( f i ) i , ( g i ) i ⟩ 1 = ∑ i ⟨ f i , g i ⟩ H , ⟨ ( f i j ) i < j , ( g i j ) i < j ⟩ 2 = ∑ i < j ⟨ f i j , g i j ⟩ H . \langle f,g\rangle_0=\langle f,g\rangle_{\mathcal{H}},\qquad\langle(f_i)_i,(g_i)_i\rangle_1=\sum_i\langle f_i,g_i\rangle_{\mathcal{H}},\qquad\langle(f_{ij})_{i<j},(g_{ij})_{i<j}\rangle_2=\sum_{i<j}\langle f_{ij},g_{ij}\rangle_{\mathcal{H}}. ⟨ f , g ⟩ 0 = ⟨ f , g ⟩ H , ⟨( f i ) i , ( g i ) i ⟩ 1 = i ∑ ⟨ f i , g i ⟩ H , ⟨( f ij ) i < j , ( g ij ) i < j ⟩ 2 = i < j ∑ ⟨ f ij , g ij ⟩ H . Further define
d 0 : H 0 → H 1 via d 0 ( f ) i = P i f for all i d_0:\mathcal{H}_0\to\mathcal{H}_1\quad\text{via}\quad d_0(f)_i=P_if\quad\text{for all }i d 0 : H 0 → H 1 via d 0 ( f ) i = P i f for all i and
d 1 : H 1 → H 2 via d 1 ( ( f i ) i ) i j = P i j ( f i − f j ) for all i < j . d_1:\mathcal{H}_1\to\mathcal{H}_2\quad\text{via}\quad d_1((f_i)_i)_{ij}=P_{ij}(f_i-f_j)\quad\text{for all }i<j. d 1 : H 1 → H 2 via d 1 (( f i ) i ) ij = P ij ( f i − f j ) for all i < j . These maps are both bounded. Note that d 1 d 0 = 0 d_1d_0=0 d 1 d 0 = 0 P i j P i = P i j P j = P i j P_{ij}P_i=P_{ij}P_j=P_{ij} P ij P i = P ij P j = P ij
d 0 ∗ ( ( f i ) i ) = ∑ i f i d_0^*((f_i)_i)=\sum_i f_i d 0 ∗ (( f i ) i ) = ∑ i f i
d 1 ∗ ( ( f i j ) i , j ) i = ∑ j > i f i j − ∑ j < i f j i d_1^*((f_{ij})_{i,j})_i=\sum_{j>i}f_{ij}-\sum_{j<i}f_{ji} d 1 ∗ (( f ij ) i , j ) i = ∑ j > i f ij − ∑ j < i f j i
d 0 ∗ d 0 = ∑ i P i d_0^*d_0=\sum_iP_i d 0 ∗ d 0 = ∑ i P i
( ker d 0 ) ⊥ = W (\ker d_0)^\perp=W ( ker d 0 ) ⊥ = W
Bochner operator. Now define B : H 1 → H 1 B:\mathcal{H}_1\to\mathcal{H}_1 B : H 1 → H 1 B = d 0 d 0 ∗ + d 1 ∗ d 1 B=d_0d_0^*+d_1^*d_1 B = d 0 d 0 ∗ + d 1 ∗ d 1
B ( f ) i = P i ( ∑ j f j ) + ∑ j ≠ i P i j ( f i − f j ) , B(f)_i=P_i\left(\sum_j f_j\right)+\sum_{j\ne i}P_{ij}(f_i-f_j), B ( f ) i = P i ( j ∑ f j ) + j = i ∑ P ij ( f i − f j ) , or equivalently on blocks B i j : W j → W i B_{ij}:W_j\to W_i B ij : W j → W i
B i j = { I + ∑ k ≠ i P i k , i = j P i P j − P i j , i ≠ j . B_{ij}=
\begin{cases}
I+\sum_{k\ne i}P_{ik}, & i=j\\
P_iP_j-P_{ij}, & i\ne j.
\end{cases} B ij = { I + ∑ k = i P ik , P i P j − P ij , i = j i = j . Coercivity of the Bochner operator. From our expression for B B B B i i ⪰ I B_{ii}\succeq I B ii ⪰ I ∥ B i j ∥ ≤ s i j \lVert B_{ij}\rVert\le s_{ij} ∥ B ij ∥ ≤ s ij i ≠ j i\ne j i = j ( f i ) i ∈ H 1 (f_i)_i\in\mathcal{H}_1 ( f i ) i ∈ H 1 a i = ∥ f i ∥ a_i=\lVert f_i\rVert a i = ∥ f i ∥ i i i
⟨ f , B f ⟩ 1 = ∑ i ⟨ f i , B i i f i ⟩ 0 + ∑ i ≠ j ⟨ f i , B i j f j ⟩ 0 ≥ ∑ i a i 2 − ∑ i ≠ j s i j a i a j = a ⊤ ( I − S ) a ≥ λ min ( M ) ∑ i a i 2 , \langle f,Bf\rangle_1=\sum_i\langle f_i,B_{ii}f_i\rangle_0+\sum_{i\ne j}\langle f_i,B_{ij}f_j\rangle_0\ge\sum_i a_i^2-\sum_{i\ne j}s_{ij}a_ia_j=a^\top(I-S)a\ge\lambda_{\min}(M)\sum_i a_i^2, ⟨ f , B f ⟩ 1 = i ∑ ⟨ f i , B ii f i ⟩ 0 + i = j ∑ ⟨ f i , B ij f j ⟩ 0 ≥ i ∑ a i 2 − i = j ∑ s ij a i a j = a ⊤ ( I − S ) a ≥ λ m i n ( M ) i ∑ a i 2 , and thus B ⪰ λ min ( M ) I B\succeq\lambda_{\min}(M)I B ⪰ λ m i n ( M ) I B B B B − 1 ⪯ λ min ( M ) − 1 I B^{-1}\preceq\lambda_{\min}(M)^{-1}I B − 1 ⪯ λ m i n ( M ) − 1 I Lemma 20 and ( ker d 0 ) ⊥ = W (\ker d_0)^\perp=W ( ker d 0 ) ⊥ = W P = d 0 ∗ B − 1 d 0 P=d_0^*B^{-1}d_0 P = d 0 ∗ B − 1 d 0 Lemma 20 with α = λ min ( M ) ≥ ϵ \alpha=\lambda_{\min}(M)\ge\epsilon α = λ m i n ( M ) ≥ ϵ § 3.4 .
Restricting to T T T Let R = [ n ] ∖ T R=[n]\setminus T R = [ n ] ∖ T
H 0 T = H T = ⋂ i ∉ T W i ⊥ , H 1 T = ⨁ i ∈ T W i , \mathcal{H}_0^T=\mathcal{H}^T=\bigcap_{i\notin T}W_i^\perp,\qquad\mathcal{H}_1^T=\bigoplus_{i\in T}W_i, H 0 T = H T = i ∈ / T ⋂ W i ⊥ , H 1 T = i ∈ T ⨁ W i , and define
d 0 T : H 0 T → H 1 T , d 0 T f = ( P i f ) i ∈ T . d_0^T:\mathcal{H}_0^T\to\mathcal{H}_1^T,\qquad d_0^Tf=(P_if)_{i\in T}. d 0 T : H 0 T → H 1 T , d 0 T f = ( P i f ) i ∈ T . We use the decomposition H 1 = H 1 T ⊕ ⨁ i ∈ R W i \mathcal{H}_1=\mathcal{H}_1^T\oplus\bigoplus_{i\in R}W_i H 1 = H 1 T ⊕ ⨁ i ∈ R W i
Now define B ~ : H 1 T → H 1 T \widetilde{B}:\mathcal{H}_1^T\to\mathcal{H}_1^T B : H 1 T → H 1 T
B ~ = ( ( B − 1 ) T T ) − 1 = B T T − B T R B R R − 1 B R T . \widetilde{B}=\left((B^{-1})_{TT}\right)^{-1}=B_{TT}-B_{TR}B_{RR}^{-1}B_{RT}. B = ( ( B − 1 ) T T ) − 1 = B T T − B T R B R R − 1 B R T . Similarly, note that
C = M T T − M T R M R R − 1 M R T . C=M_{TT}-M_{TR}M_{RR}^{-1}M_{RT}. C = M T T − M T R M R R − 1 M R T . When R = ∅ R=\varnothing R = ∅ Lemma 9 gives
λ min ( M ) I ⪯ B ~ ⪯ ∥ B ∥ I \lambda_{\min}(M)I\preceq\widetilde{B}\preceq\lVert B\rVert I λ m i n ( M ) I ⪯ B ⪯ ∥ B ∥ I Applying Lemma 9 to M M M C C C C C C D D D
Outer block bound on B − 1 B^{-1} B − 1 Here we prove that
∥ ( B R R − 1 ) k ℓ ∥ ≤ ( M R R − 1 ) k ℓ (9) \lVert(B_{RR}^{-1})_{k\ell}\rVert\leq(M_{RR}^{-1})_{k\ell} \tag*{(9)} ∥( B R R − 1 ) k ℓ ∥ ≤ ( M R R − 1 ) k ℓ (9) for all blocks k , ℓ ∈ R k,\ell\in R k , ℓ ∈ R y , z y,z y , z B R R y = z B_{RR}y=z B R R y = z z k = B k k y k + ∑ ℓ ∈ R , ℓ ≠ k B k ℓ y ℓ z_k=B_{kk}y_k+\sum_{\ell\in R,\ell\ne k}B_{k\ell}y_\ell z k = B k k y k + ∑ ℓ ∈ R , ℓ = k B k ℓ y ℓ B k k ⪰ I B_{kk}\succeq I B k k ⪰ I
∥ z k ∥ ≥ ∥ B k k y k ∥ − ∑ ℓ ∈ R , ℓ ≠ k ∥ B k ℓ y ℓ ∥ ≥ ∥ y k ∥ − ∑ ℓ ∈ R , ℓ ≠ k s k ℓ ∥ y ℓ ∥ . \lVert z_k\rVert\geq\lVert B_{kk}y_k\rVert-\sum_{\ell\in R,\ell\ne k}\lVert B_{k\ell}y_\ell\rVert\geq\lVert y_k\rVert-\sum_{\ell\in R,\ell\ne k}s_{k\ell}\lVert y_\ell\rVert. ∥ z k ∥ ≥ ∥ B k k y k ∥ − ℓ ∈ R , ℓ = k ∑ ∥ B k ℓ y ℓ ∥ ≥ ∥ y k ∥ − ℓ ∈ R , ℓ = k ∑ s k ℓ ∥ y ℓ ∥ . That is, letting a i = ∥ y i ∥ a_i=\lVert y_i\rVert a i = ∥ y i ∥ b i = ∥ z i ∥ b_i=\lVert z_i\rVert b i = ∥ z i ∥ i ∈ R i\in R i ∈ R
( I − S R R ) a ≤ b (I-S_{RR})a\leq b ( I − S R R ) a ≤ b entry-wise. Since M R R − 1 = ( I − S R R ) − 1 = ∑ t = 0 ∞ S R R t M_{RR}^{-1}=(I-S_{RR})^{-1}=\sum_{t=0}^{\infty}S_{RR}^{t} M R R − 1 = ( I − S R R ) − 1 = ∑ t = 0 ∞ S R R t
a ≤ M R R − 1 b a\leq M_{RR}^{-1}b a ≤ M R R − 1 b entry-wise.
Fix ℓ ∈ R \ell\in R ℓ ∈ R z ℓ ∈ W ℓ z_\ell\in W_\ell z ℓ ∈ W ℓ z t = 0 z_t=0 z t = 0 t ≠ ℓ t\ne\ell t = ℓ y = B R R − 1 z y=B_{RR}^{-1}z y = B R R − 1 z
∥ ( B R R − 1 ) k ℓ z ℓ ∥ = ∥ ( B R R − 1 z ) k ∥ = a k ≤ ( M R R − 1 b ) k = ( M R R − 1 ) k ℓ ∥ z ℓ ∥ , \lVert(B_{RR}^{-1})_{k\ell}z_\ell\rVert=\lVert(B_{RR}^{-1}z)_k\rVert=a_k\leq(M_{RR}^{-1}b)_k=(M_{RR}^{-1})_{k\ell}\lVert z_\ell\rVert, ∥( B R R − 1 ) k ℓ z ℓ ∥ = ∥( B R R − 1 z ) k ∥ = a k ≤ ( M R R − 1 b ) k = ( M R R − 1 ) k ℓ ∥ z ℓ ∥ , which implies ∥ ( B R R − 1 ) k ℓ ∥ ≤ ( M R R − 1 ) k ℓ \lVert(B_{RR}^{-1})_{k\ell}\rVert\leq(M_{RR}^{-1})_{k\ell} ∥( B R R − 1 ) k ℓ ∥ ≤ ( M R R − 1 ) k ℓ
Block-wise bounds on B ~ \widetilde{B} B Now for all i , j ∈ T i,j\in T i , j ∈ T
∥ ( B T R B R R − 1 B R T ) i j ∥ ≤ ∑ k , ℓ ∈ R ∥ B i k ∥ ∥ ( B R R − 1 ) k ℓ ∥ ∥ B ℓ j ∥ ≤ ∑ k , ℓ ∈ R s i k ( M R R − 1 ) k ℓ s ℓ j = ( S T R M R R − 1 S R T ) i j . \lVert(B_{TR}B_{RR}^{-1}B_{RT})_{ij}\rVert\leq\sum_{k,\ell\in R}\lVert B_{ik}\rVert\lVert(B_{RR}^{-1})_{k\ell}\rVert\lVert B_{\ell j}\rVert\leq\sum_{k,\ell\in R}s_{ik}(M_{RR}^{-1})_{k\ell}s_{\ell j}=(S_{TR}M_{RR}^{-1}S_{RT})_{ij}. ∥( B T R B R R − 1 B R T ) ij ∥ ≤ k , ℓ ∈ R ∑ ∥ B ik ∥ ∥( B R R − 1 ) k ℓ ∥ ∥ B ℓ j ∥ ≤ k , ℓ ∈ R ∑ s ik ( M R R − 1 ) k ℓ s ℓ j = ( S T R M R R − 1 S R T ) ij . Thus for all i ∈ T i\in T i ∈ T B i i ⪰ I B_{ii}\succeq I B ii ⪰ I
B ~ i i = B i i − B i R B R R − 1 B R i ⪰ ( 1 − ( S T R M R R − 1 S R T ) i i ) I . \widetilde{B}_{ii}=B_{ii}-B_{iR}B_{RR}^{-1}B_{Ri}\succeq\left(1-(S_{TR}M_{RR}^{-1}S_{RT})_{ii}\right)I. B ii = B ii − B i R B R R − 1 B R i ⪰ ( 1 − ( S T R M R R − 1 S R T ) ii ) I . And for all i ≠ j i\ne j i = j T T T
∥ B ~ i j ∥ = ∥ B i j − B i R B R R − 1 B R j ∥ ≤ ∥ B i j ∥ + ∥ ( B T R B R R − 1 B R T ) i j ∥ ≤ s i j + ( S T R M R R − 1 S R T ) i j . \lVert\widetilde{B}_{ij}\rVert=\lVert B_{ij}-B_{iR}B_{RR}^{-1}B_{Rj}\rVert\leq\lVert B_{ij}\rVert+\lVert(B_{TR}B_{RR}^{-1}B_{RT})_{ij}\rVert\leq s_{ij}+(S_{TR}M_{RR}^{-1}S_{RT})_{ij}. ∥ B ij ∥ = ∥ B ij − B i R B R R − 1 B R j ∥ ≤ ∥ B ij ∥ + ∥( B T R B R R − 1 B R T ) ij ∥ ≤ s ij + ( S T R M R R − 1 S R T ) ij . Since T , R T,R T , R S R T = − M R T S_{RT}=-M_{RT} S R T = − M R T S T R = − M T R S_{TR}=-M_{TR} S T R = − M T R i ∈ T i\in T i ∈ T
B ~ i i ⪰ ( 1 − ( M T R M R R − 1 M R T ) i i ) I = c i i I \widetilde{B}_{ii}\succeq\left(1-(M_{TR}M_{RR}^{-1}M_{RT})_{ii}\right)I=c_{ii}I B ii ⪰ ( 1 − ( M T R M R R − 1 M R T ) ii ) I = c ii I and for all i ≠ j i\ne j i = j T T T
∥ B ~ i j ∥ ≤ − m i j + ( M T R M R R − 1 M R T ) i j = − c i j . \lVert\widetilde{B}_{ij}\rVert\leq-m_{ij}+(M_{TR}M_{RR}^{-1}M_{RT})_{ij}=-c_{ij}. ∥ B ij ∥ ≤ − m ij + ( M T R M R R − 1 M R T ) ij = − c ij . Note that these inequalities imply for all f = ( f i ) i ∈ T ∈ H 1 T f=(f_i)_{i\in T}\in\mathcal{H}_1^T f = ( f i ) i ∈ T ∈ H 1 T i , j ∈ T i,j\in T i , j ∈ T
⟨ f i , B ~ i j f j ⟩ 0 ≥ c i j ∥ f i ∥ ∥ f j ∥ . (10) \langle f_i,\widetilde{B}_{ij}f_j\rangle_0\geq c_{ij}\lVert f_i\rVert\lVert f_j\rVert. \tag*{(10)} ⟨ f i , B ij f j ⟩ 0 ≥ c ij ∥ f i ∥ ∥ f j ∥ . (10) Coercivity-type inequality for B ~ \widetilde{B} B Now, we define D ~ = blockdiag ( B ~ T 1 T 1 , … , B ~ T m T m ) \widetilde{D}=\operatorname{blockdiag}(\widetilde{B}_{T_1T_1},\ldots,\widetilde{B}_{T_mT_m}) D = blockdiag ( B T 1 T 1 , … , B T m T m )
B ~ T a T a ⪰ λ min ( M ) I . \widetilde{B}_{T_aT_a}\succeq\lambda_{\min}(M)I. B T a T a ⪰ λ m i n ( M ) I . Thus, it follows that D ~ \widetilde{D} D
B ~ ⪰ α D ~ . (11) \widetilde{B}\succeq\alpha\widetilde{D}. \tag*{(11)} B ⪰ α D . (11) Note that by definition of α = λ min ( D − 1 / 2 C D − 1 / 2 ) \alpha=\lambda_{\min}(D^{-1/2}CD^{-1/2}) α = λ m i n ( D − 1/2 C D − 1/2 ) C ⪰ α D C\succeq\alpha D C ⪰ α D 0 < α ≤ 1 0<\alpha\leq1 0 < α ≤ 1 C C C D − 1 / 2 C D − 1 / 2 D^{-1/2}CD^{-1/2} D − 1/2 C D − 1/2 f = ( f i ) i ∈ T ∈ H 1 T f=(f_i)_{i\in T}\in\mathcal{H}_1^T f = ( f i ) i ∈ T ∈ H 1 T a i = ∥ f i ∥ a_i=\lVert f_i\rVert a i = ∥ f i ∥ i i i
⟨ f , ( B ~ − α D ~ ) f ⟩ 1 = ( 1 − α ) ∑ a ∑ i , j ∈ T a ⟨ f i , B ~ i j f j ⟩ 0 + ∑ a ≠ b ∑ i ∈ T a , j ∈ T b ⟨ f i , B ~ i j f j ⟩ 0 ≥ ( 1 − α ) ∑ a ∑ i , j ∈ T a c i j a i a j + ∑ a ≠ b ∑ i ∈ T a , j ∈ T b c i j a i a j = a T ( C − α D ) a ≥ 0 \begin{aligned}
\langle f,(\widetilde{B}-\alpha\widetilde{D})f\rangle_1
&=(1-\alpha)\sum_a\sum_{i,j\in T_a}\langle f_i,\widetilde{B}_{ij}f_j\rangle_0
+\sum_{a\ne b}\sum_{i\in T_a,j\in T_b}\langle f_i,\widetilde{B}_{ij}f_j\rangle_0\\
&\geq(1-\alpha)\sum_a\sum_{i,j\in T_a}c_{ij}a_i a_j
+\sum_{a\ne b}\sum_{i\in T_a,j\in T_b}c_{ij}a_i a_j\\
&=a^\mathsf{T}(C-\alpha D)a\\
&\geq0
\end{aligned} ⟨ f , ( B − α D ) f ⟩ 1 = ( 1 − α ) a ∑ i , j ∈ T a ∑ ⟨ f i , B ij f j ⟩ 0 + a = b ∑ i ∈ T a , j ∈ T b ∑ ⟨ f i , B ij f j ⟩ 0 ≥ ( 1 − α ) a ∑ i , j ∈ T a ∑ c ij a i a j + a = b ∑ i ∈ T a , j ∈ T b ∑ c ij a i a j = a T ( C − α D ) a ≥ 0 Therefore, we have B ~ ⪰ α D ~ \widetilde{B}\succeq\alpha\widetilde{D} B ⪰ α D D ~ − 1 ⪰ α B ~ − 1 \widetilde{D}^{-1}\succeq\alpha\widetilde{B}^{-1} D − 1 ⪰ α B − 1
Back to the projections. The definitions give the following kernels on H 0 T \mathcal{H}_0^T H 0 T
ker P ~ = W ⊥ and ker Q ~ a = H 0 T ∩ ⋂ i ∈ T a W i ⊥ . \ker\widetilde{P}=W^\perp
\qquad\text{and}\qquad
\ker\widetilde{Q}_a=\mathcal{H}_0^T\cap\bigcap_{i\in T_a}W_i^\perp. ker P = W ⊥ and ker Q a = H 0 T ∩ i ∈ T a ⋂ W i ⊥ . Since W ⊥ ⊆ H 0 T W^\perp\subseteq\mathcal{H}_0^T W ⊥ ⊆ H 0 T
ran P ~ = H 0 T ∩ W and P ~ f = P f , ∀ f ∈ H 0 T . \operatorname{ran}\widetilde{P}=\mathcal{H}_0^T\cap W
\qquad\text{and}\qquad
\widetilde{P}f=Pf,\ \forall f\in\mathcal{H}_0^T. ran P = H 0 T ∩ W and P f = P f , ∀ f ∈ H 0 T . We also have ran Q ~ a ⊆ ran P ~ \operatorname{ran}\widetilde{Q}_a\subseteq\operatorname{ran}\widetilde{P} ran Q a ⊆ ran P
Now fix f ∈ H 0 T f\in\mathcal{H}_0^T f ∈ H 0 T g i = P i f g_i=P_i f g i = P i f i ∈ T i\in T i ∈ T g = d 0 T f g=d_0^T f g = d 0 T f P i f = 0 P_i f=0 P i f = 0 i ∉ T i\notin T i ∈ / T
∥ P ~ f ∥ 2 = ∥ P f ∥ 2 = ⟨ d 0 f , B − 1 d 0 f ⟩ 1 = ⟨ g , ( B − 1 ) T T g ⟩ 1 = ⟨ g , B ~ − 1 g ⟩ 1 . (12) \lVert\widetilde{P}f\rVert^2=\lVert Pf\rVert^2=\langle d_0f,B^{-1}d_0f\rangle_1=\langle g,(B^{-1})_{TT}g\rangle_1=\langle g,\widetilde{B}^{-1}g\rangle_1. \tag*{(12)} ∥ P f ∥ 2 = ∥ P f ∥ 2 = ⟨ d 0 f , B − 1 d 0 f ⟩ 1 = ⟨ g , ( B − 1 ) T T g ⟩ 1 = ⟨ g , B − 1 g ⟩ 1 . (12) where here we used P = d 0 ∗ B − 1 d 0 P=d_0^*B^{-1}d_0 P = d 0 ∗ B − 1 d 0 d 0 f = ( g , 0 ) d_0f=(g,0) d 0 f = ( g , 0 )
Now for each a ∈ [ m ] a\in[m] a ∈ [ m ] h a = Q ~ a f h_a=\widetilde{Q}_a f h a = Q a f g ( a ) = d 0 T h a = ( P i h a ) i ∈ T g^{(a)}=d_0^T h_a=(P_i h_a)_{i\in T} g ( a ) = d 0 T h a = ( P i h a ) i ∈ T h a ∈ ran P ~ h_a\in\operatorname{ran}\widetilde{P} h a ∈ ran P P h a = h a Ph_a=h_a P h a = h a
f − h a ∈ ker Q ~ a = H 0 T ∩ ⋂ i ∈ T a W i ⊥ , f-h_a\in\ker\widetilde{Q}_a=\mathcal{H}_0^T\cap\bigcap_{i\in T_a}W_i^\perp, f − h a ∈ ker Q a = H 0 T ∩ i ∈ T a ⋂ W i ⊥ , and thus P i ( f − h a ) = 0 P_i(f-h_a)=0 P i ( f − h a ) = 0 i ∈ T a i\in T_a i ∈ T a g T a ( a ) = g T a g_{T_a}^{(a)}=g_{T_a} g T a ( a ) = g T a h a h_a h a
∥ Q ~ a f ∥ 2 = ⟨ g ( a ) , B ~ − 1 g ( a ) ⟩ 1 ≥ ⟨ g T a , ( B ~ T a T a ) − 1 g T a ⟩ 1 . (13) \lVert\widetilde{Q}_a f\rVert^2=\langle g^{(a)},\widetilde{B}^{-1}g^{(a)}\rangle_1\geq\langle g_{T_a},(\widetilde{B}_{T_aT_a})^{-1}g_{T_a}\rangle_1. \tag*{(13)} ∥ Q a f ∥ 2 = ⟨ g ( a ) , B − 1 g ( a ) ⟩ 1 ≥ ⟨ g T a , ( B T a T a ) − 1 g T a ⟩ 1 . (13) where the inequality is part 3 of Lemma 9 applied to B ~ \widetilde{B} B
∑ a = 1 m ∥ Q ~ a f ∥ 2 ≥ ∑ a = 1 m ⟨ g T a , ( B ~ T a T a ) − 1 g T a ⟩ = ⟨ g , D ~ − 1 g ⟩ ≥ α ⟨ g , B ~ − 1 g ⟩ = α ∥ P ~ f ∥ 2 (14) \sum_{a=1}^{m}\|\widetilde{Q}_a f\|^2 \ge\sum_{a=1}^{m}\langle g_{T_a},(\widetilde{B}_{T_aT_a})^{-1}g_{T_a}\rangle= \langle g,\widetilde{D}^{-1}g\rangle\ge\alpha\langle g,\widetilde{B}^{-1}g\rangle= \alpha\|\widetilde{P}f\|^2 \tag*{(14)} a = 1 ∑ m ∥ Q a f ∥ 2 ≥ a = 1 ∑ m ⟨ g T a , ( B T a T a ) − 1 g T a ⟩ = ⟨ g , D − 1 g ⟩ ≥ α ⟨ g , B − 1 g ⟩ = α ∥ P f ∥ 2 (14) which is precisely the desired conclusion.
Proof of Theorem 3
In this section, we put together the tools developed above to prove our main result, Theorem 3.
Proof of Theorem 3. First, note that interpreting the local assumption on links using Lemma 13 and averaging, we have
∥ L i L j − L i j ∥ o p ≤ a i j , \|L_iL_j-L_{ij}\|_{\mathrm{op}}\le a_{ij}, ∥ L i L j − L ij ∥ op ≤ a ij , This shows that the hypotheses of Theorem 21 hold for H = L 2 ( μ ) \mathcal{H}=L^2(\mu) H = L 2 ( μ ) W i = ran L i W_i=\operatorname{ran}L_i W i = ran L i S S S S i j = a i j S_{ij}=a_{ij} S ij = a ij
Now let f = f ( X T ) ∈ L 2 ( μ ) f=f(X_T)\in L^2(\mu) f = f ( X T ) ∈ L 2 ( μ ) f ∈ H T f\in\mathcal{H}_T f ∈ H T L i f = 0 L_if=0 L i f = 0 i ∉ T i\notin T i ∈ / T
ker P ~ = ⋂ i ∈ V ker L i = span { 1 } and ker Q ~ a = H T ∩ ⋂ i ∈ T a ker L i . \ker\widetilde{P}=\bigcap_{i\in V}\ker L_i=\operatorname{span}\{1\}
\qquad\text{and}\qquad
\ker\widetilde{Q}_a=\mathcal{H}_T\cap\bigcap_{i\in T_a}\ker L_i. ker P = i ∈ V ⋂ ker L i = span { 1 } and ker Q a = H T ∩ i ∈ T a ⋂ ker L i . Consequently, P ~ f = f − E μ f \widetilde{P}f=f-\mathbb{E}_{\mu}f P f = f − E μ f
Having this, we write
α Var μ ( f ) = α ∥ f − E μ f ∥ 2 = α ∥ P ~ f ∥ 2 ≤ ∑ a = 1 m ∥ Q ~ a f ∥ 2 = ∑ a = 1 m ∥ Q ~ a ( f − E μ [ f ∣ X T ∖ T a ] ) ∥ 2 2 ≤ ∑ a = 1 m ∥ f − E μ [ f ∣ X T ∖ T a ] ∥ 2 2 = m ⟨ f , L G l a u b T 1 , … , T m f ⟩ μ , \begin{aligned}
\alpha\operatorname{Var}_{\mu}(f)=\alpha\|f-\mathbb{E}_{\mu}f\|^2=\alpha\|\widetilde{P}f\|^2
\le\sum_{a=1}^{m}\|\widetilde{Q}_a f\|^2
=\sum_{a=1}^{m}\left\|\widetilde{Q}_a\left(f-\mathbb{E}_{\mu}[f\mid X_{T\setminus T_a}]\right)\right\|_2^2 \\
&\le\sum_{a=1}^{m}\left\|f-\mathbb{E}_{\mu}[f\mid X_{T\setminus T_a}]\right\|_2^2
= m\left\langle f,L_{\mathrm{Glaub}}^{T_1,\ldots,T_m}f\right\rangle_{\mu},
\end{aligned} α Var μ ( f ) = α ∥ f − E μ f ∥ 2 = α ∥ P f ∥ 2 ≤ a = 1 ∑ m ∥ Q a f ∥ 2 = a = 1 ∑ m Q a ( f − E μ [ f ∣ X T ∖ T a ] ) 2 2 ≤ a = 1 ∑ m f − E μ [ f ∣ X T ∖ T a ] 2 2 = m ⟨ f , L Glaub T 1 , … , T m f ⟩ μ , where the first equality follows from the fact that every function of X T ∖ T a X_{T\setminus T_a} X T ∖ T a ker Q ~ a \ker\widetilde{Q}_a ker Q a
Since α = λ min ( D − 1 / 2 C D − 1 / 2 ) = 1 − λ max ( H ) \alpha=\lambda_{\min}(D^{-1/2}CD^{-1/2})=1-\lambda_{\max}(H) α = λ m i n ( D − 1/2 C D − 1/2 ) = 1 − λ m a x ( H )
λ 2 ( L G l a u b T 1 , … , T m ) ≥ 1 − λ max ( H ) m , \lambda_2\left(L_{\mathrm{Glaub}}^{T_1,\ldots,T_m}\right)\ge\frac{1-\lambda_{\max}(H)}{m}, λ 2 ( L Glaub T 1 , … , T m ) ≥ m 1 − λ m a x ( H ) , as desired. □
Application: Mixing time of O ( N ) O(N) O ( N )
In this section, we prove the following theorem about the spectral gap of Glauber dynamics in the O ( N ) O(N) O ( N )
Theorem 5. Let N ≥ 2 N\ge2 N ≥ 2 μ \mu μ O ( N ) O(N) O ( N )
1 − ∥ J a b s ∥ o p N n . \frac{1-\frac{\|J_{\mathrm{abs}}\|_{\mathrm{op}}}{N}}{n}. n 1 − N ∥ J abs ∥ op . Consequently, for every ε 0 ∈ ( 0 , 1 ) \varepsilon_0 \in(0,1) ε 0 ∈ ( 0 , 1 ) ∥ J a b s ∥ o p ≤ ( 1 − ε 0 ) N \lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}} \le(1-\varepsilon_0)N ∥ J abs ∥ op ≤ ( 1 − ε 0 ) N O N , ε 0 ( n 2 ) O_{N,\varepsilon_0}(n^2) O N , ε 0 ( n 2 )
Remark 22. We can also use Theorem 3 to bound correlations and analyze block dynamics for the O ( N ) O(N) O ( N ) x , y x,y x , y ∣ J x y ∣ / N \lvert J_{xy}\rvert/N ∣ J x y ∣ / N Lemma 23 ). Having this, we can apply Theorem 3 with S = J a b s / N S=J_{\mathrm{abs}}/N S = J abs / N θ : = ∥ S ∥ o p < 1 \theta:=\lVert S\rVert_{\mathrm{op}}<1 θ := ∥ S ∥ op < 1
First, taking T 1 = { x } T_1=\{x\} T 1 = { x } T 2 = { y } T_2=\{y\} T 2 = { y } x , y x,y x , y f = f ( σ x ) f=f(\sigma_x) f = f ( σ x ) g = g ( σ y ) g=g(\sigma_y) g = g ( σ y )
∣ Cov μ ( f , g ) ∣ ≤ min { θ , θ dist G ( x , y ) 1 − θ } Var μ ( f ) Var μ ( g ) . \lvert\operatorname{Cov}_{\mu}(f,g)\rvert\le\min\left\{\theta,\frac{\theta^{\operatorname{dist}_{G}(x,y)}}{1-\theta}\right\}\sqrt{\operatorname{Var}_{\mu}(f)\operatorname{Var}_{\mu}(g)}. ∣ Cov μ ( f , g )∣ ≤ min { θ , 1 − θ θ dist G ( x , y ) } Var μ ( f ) Var μ ( g ) . In general, for any partition V = T 1 ⊔ ⋯ ⊔ T m V=T_1\sqcup\cdots\sqcup T_m V = T 1 ⊔ ⋯ ⊔ T m Theorem 3 gives a spectral gap of at least ( 1 − λ max ( H ) ) / m (1-\lambda_{\max}(H))/m ( 1 − λ m a x ( H )) / m
Proof of Theorem 5
Lemma 23. Let a , b ∈ R N a,b\in\mathbb{R}^{N} a , b ∈ R N κ ∈ R \kappa\in\mathbb{R} κ ∈ R
ν ( d u , d v ) = 1 Z exp ( a ⋅ u + b ⋅ v + κ u ⋅ v ) d ω ( u ) d ω ( v ) . \nu(du,dv)=\frac{1}{Z}\exp(a\cdot u+b\cdot v+\kappa u\cdot v)\,d\omega(u)\,d\omega(v). ν ( d u , d v ) = Z 1 exp ( a ⋅ u + b ⋅ v + κ u ⋅ v ) d ω ( u ) d ω ( v ) . Then ρ ν ( U , V ) ≤ min { 1 , ∣ κ ∣ / N } \rho_{\nu}(U,V)\le\min\{1,\lvert\kappa\rvert/N\} ρ ν ( U , V ) ≤ min { 1 , ∣ κ ∣ / N }
Assuming Lemma 23 , we prove Theorem 5.
Proof of Theorem 5. If ∥ J a b s ∥ o p > N \lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}}>N ∥ J abs ∥ op > N L G l a u b L_{\mathrm{Glaub}} L Glaub ϵ : = 1 − ∥ J a b s ∥ o p / N > 0 \epsilon:=1-\lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}}/N>0 ϵ := 1 − ∥ J abs ∥ op / N > 0 J a b s = ( ∣ J x y ∣ ) x , y ∈ V J_{\mathrm{abs}}=(\lvert J_{xy}\rvert)_{x,y\in V} J abs = (∣ J x y ∣ ) x , y ∈ V
Fix distinct x , y ∈ V x,y\in V x , y ∈ V σ V ∖ { x , y } = τ \sigma_{V\setminus\{x,y\}}=\tau σ V ∖ { x , y } = τ ( σ x , σ y ) (\sigma_x,\sigma_y) ( σ x , σ y )
∝ exp [ J x y σ x ⋅ σ y + ( h x + ∑ z ≠ x , y J x z τ z ) ⋅ σ x + ( h y + ∑ z ≠ x , y J y z τ z ) ⋅ σ y ] d ω ( σ x ) d ω ( σ y ) . \propto\exp\left[J_{xy}\sigma_x\cdot\sigma_y+\left(h_x+\sum_{z\ne x,y}J_{xz}\tau_z\right)\cdot\sigma_x+\left(h_y+\sum_{z\ne x,y}J_{yz}\tau_z\right)\cdot\sigma_y\right]\,d\omega(\sigma_x)\,d\omega(\sigma_y). ∝ exp J x y σ x ⋅ σ y + h x + z = x , y ∑ J x z τ z ⋅ σ x + h y + z = x , y ∑ J y z τ z ⋅ σ y d ω ( σ x ) d ω ( σ y ) . By Lemma 23 , its maximal correlation is at most ∣ J x y ∣ / N \lvert J_{xy}\rvert/N ∣ J x y ∣ / N τ \tau τ μ \mu μ Lemma 13 to verify the local hypothesis, we apply Theorem 3 with A = J a b s / N A=J_{\mathrm{abs}}/N A = J abs / N
λ 2 ( L G l a u b ) ≥ 1 − ρ ( S ) n = ϵ n and λ 2 ( P G l a u b ) ≤ 1 − ϵ n . \lambda_2(L_{\mathrm{Glaub}})\ge\frac{1-\rho(S)}{n}=\frac{\epsilon}{n}
\quad\text{and}\quad
\lambda_2(P_{\mathrm{Glaub}})\le1-\frac{\epsilon}{n}. λ 2 ( L Glaub ) ≥ n 1 − ρ ( S ) = n ϵ and λ 2 ( P Glaub ) ≤ 1 − n ϵ . This proves the spectral-gap bound.
Finally, we prove the mixing time consequence. After s s s n e − s / n ne^{-s/n} n e − s / n λ \lambda λ
d λ d μ = d λ d μ 0 , h d μ 0 , h d μ ≤ ( ∏ x e 2 ∑ y ∣ J x y ∣ ) e ∑ x , y ∣ J x y ∣ = e 3 ∑ x , y ∣ J x y ∣ . (15) \frac{d\lambda}{d\mu}=\frac{d\lambda}{d\mu_{0,h}}\frac{d\mu_{0,h}}{d\mu}\le\left(\prod_x e^{2\sum_y\lvert J_{xy}\rvert}\right)e^{\sum_{x,y}\lvert J_{xy}\rvert}=e^{3\sum_{x,y}\lvert J_{xy}\rvert}. \tag*{(15)} d μ d λ = d μ 0 , h d λ d μ d μ 0 , h ≤ ( x ∏ e 2 ∑ y ∣ J x y ∣ ) e ∑ x , y ∣ J x y ∣ = e 3 ∑ x , y ∣ J x y ∣ . (15) Consequently, we have
∥ L ( σ s + t ) − μ ∥ T V ≤ n e − s / n + 1 2 exp ( 3 ∑ x , y ∣ J x y ∣ 2 − ϵ t n ) . \lVert\mathcal{L}(\sigma_{s+t})-\mu\rVert_{\mathrm{TV}} \le n e^{-s/n}+\frac{1}{2}\exp\left(\frac{3\sum_{x,y}|J_{xy}|}{2}-\frac{\epsilon t}{n}\right). ∥ L ( σ s + t ) − μ ∥ TV ≤ n e − s / n + 2 1 exp ( 2 3 ∑ x , y ∣ J x y ∣ − n ϵ t ) . It follows that the mixing time of Glauber dynamics is therefore O ( n log n + n ( ∑ x , y ∣ J x y ∣ + 1 ) ϵ ) = O N , ϵ ( n 2 ) O\left(n\log n+\frac{n(\sum_{x,y}|J_{xy}|+1)}{\epsilon}\right)=O_{N,\epsilon}(n^2) O ( n log n + ϵ n ( ∑ x , y ∣ J x y ∣ + 1 ) ) = O N , ϵ ( n 2 ) ∑ x , y ∣ J x y ∣ ≤ n ∥ J a b s ∥ o p < n N \sum_{x,y}|J_{xy}|\le n\lVert J_{\mathrm{abs}}\rVert_{\mathrm{op}}<nN ∑ x , y ∣ J x y ∣ ≤ n ∥ J abs ∥ op < n N
Proof of the local inequality
For h ∈ R N h\in\mathbb{R}^{N} h ∈ R N ν h ( d u ) = Z h − 1 e h ⋅ u d ω ( u ) \nu_h(du)=Z_h^{-1}e^{h\cdot u}d\omega(u) ν h ( d u ) = Z h − 1 e h ⋅ u d ω ( u ) S N − 1 S^{N-1} S N − 1 Z h = ∫ S N − 1 e h ⋅ u d ω ( u ) Z_h=\int_{S^{N-1}}e^{h\cdot u}d\omega(u) Z h = ∫ S N − 1 e h ⋅ u d ω ( u )
Lemma 25. For every h , c ∈ R N h,c\in\mathbb{R}^{N} h , c ∈ R N f : S N − 1 → R f:S^{N-1}\to\mathbb{R} f : S N − 1 → R
∣ Cov ν h ( f ( U ) , c ⋅ U ) ∣ ≤ ∥ c ∥ N Lip ( f ) . \left|\operatorname{Cov}_{\nu_h}(f(U),c\cdot U)\right|\le\frac{\lVert c\rVert}{N}\operatorname{Lip}(f). ∣ Cov ν h ( f ( U ) , c ⋅ U ) ∣ ≤ N ∥ c ∥ Lip ( f ) . Assuming Lemma 25 , we prove Lemma 23 .
Proof of Lemma 23. Let ν U , ν V \nu_U,\nu_V ν U , ν V T : L 2 ( ν V ) → L 2 ( ν U ) T:L^2(\nu_V)\to L^2(\nu_U) T : L 2 ( ν V ) → L 2 ( ν U ) ( T g ) ( u ) = E ν [ g ( V ) ∣ U = u ] (Tg)(u)=\mathbb{E}_{\nu}[g(V)\mid U=u] ( T g ) ( u ) = E ν [ g ( V ) ∣ U = u ] ( T ∗ f ) ( v ) = E ν [ f ( U ) ∣ V = v ] (T^*f)(v)=\mathbb{E}_{\nu}[f(U)\mid V=v] ( T ∗ f ) ( v ) = E ν [ f ( U ) ∣ V = v ] ∥ T ∥ o p ≤ 1 \lVert T\rVert_{\mathrm{op}}\le1 ∥ T ∥ op ≤ 1 ρ ν ( U , V ) ≤ ∣ κ ∣ / N \rho_\nu(U,V)\le|\kappa|/N ρ ν ( U , V ) ≤ ∣ κ ∣/ N
We write
d d s E ν h + s c g ( U ) = d d s ( ∫ S N − 1 g ( u ) e ( h + s c ) ⋅ u d ω ( u ) Z h + s c ) = ∫ S N − 1 g ( u ) ( c ⋅ u ) e ( h + s c ) ⋅ u d ω ( u ) Z h + s c − ∫ S N − 1 g ( u ) e ( h + s c ) ⋅ u d ω ( u ) Z h + s c ∫ S N − 1 ( c ⋅ u ) e ( h + s c ) ⋅ u d ω ( u ) Z h + s c = E ν h + s c [ g ( U ) ( c ⋅ U ) ] − E ν h + s c [ g ( U ) ] E ν h + s c [ c ⋅ U ] = Cov ν h + s c ( g ( U ) , c ⋅ U ) . \begin{aligned}
\frac{d}{ds}\mathbb{E}_{\nu_{h+sc}}g(U)=\frac{d}{ds}\left(\frac{\int_{S^{N-1}}g(u)e^{(h+sc)\cdot u}d\omega(u)}{Z_{h+sc}}\right) \\
&=\frac{\int_{S^{N-1}}g(u)(c\cdot u)e^{(h+sc)\cdot u}d\omega(u)}{Z_{h+sc}}
-\frac{\int_{S^{N-1}}g(u)e^{(h+sc)\cdot u}d\omega(u)}{Z_{h+sc}}\frac{\int_{S^{N-1}}(c\cdot u)e^{(h+sc)\cdot u}d\omega(u)}{Z_{h+sc}} \\
&=\mathbb{E}_{\nu_{h+sc}}[g(U)(c\cdot U)]-\mathbb{E}_{\nu_{h+sc}}[g(U)]\mathbb{E}_{\nu_{h+sc}}[c\cdot U] \\
&=\operatorname{Cov}_{\nu_{h+sc}}(g(U),c\cdot U).
\end{aligned} d s d E ν h + sc g ( U ) = d s d ( Z h + sc ∫ S N − 1 g ( u ) e ( h + sc ) ⋅ u d ω ( u ) ) = Z h + sc ∫ S N − 1 g ( u ) ( c ⋅ u ) e ( h + sc ) ⋅ u d ω ( u ) − Z h + sc ∫ S N − 1 g ( u ) e ( h + sc ) ⋅ u d ω ( u ) Z h + sc ∫ S N − 1 ( c ⋅ u ) e ( h + sc ) ⋅ u d ω ( u ) = E ν h + sc [ g ( U ) ( c ⋅ U )] − E ν h + sc [ g ( U )] E ν h + sc [ c ⋅ U ] = Cov ν h + sc ( g ( U ) , c ⋅ U ) . Since ( T g ) ( u ) = E ν b + κ u g ( V ) (Tg)(u)=\mathbb{E}_{\nu_{b+\kappa u}}g(V) ( T g ) ( u ) = E ν b + κ u g ( V ) Lemma 25 along the segment between b + κ u b+\kappa u b + κ u b + κ u ′ b+\kappa u' b + κ u ′
Lip ( T g ) ≤ ∣ κ ∣ N Lip ( g ) , Lip ( T ∗ f ) ≤ ∣ κ ∣ N Lip ( f ) . (16) \operatorname{Lip}(Tg)\le\frac{|\kappa|}{N}\operatorname{Lip}(g),\qquad\operatorname{Lip}(T^*f)\le\frac{|\kappa|}{N}\operatorname{Lip}(f). \tag*{(16)} Lip ( T g ) ≤ N ∣ κ ∣ Lip ( g ) , Lip ( T ∗ f ) ≤ N ∣ κ ∣ Lip ( f ) . (16) We can write
( T g ) ( u ) = ∫ k ( u , v ) g ( v ) d ν V ( v ) . (Tg)(u)=\int k(u,v)g(v)\,d\nu_V(v). ( T g ) ( u ) = ∫ k ( u , v ) g ( v ) d ν V ( v ) . where
k ( u , v ) = p ( u , v ) p U ( u ) p V ( v ) = d ν d ( ν U ⊗ ν V ) ( u , v ) , k(u,v)=\frac{p(u,v)}{p_U(u)p_V(v)}=\frac{d\nu}{d(\nu_U\otimes\nu_V)}(u,v), k ( u , v ) = p U ( u ) p V ( v ) p ( u , v ) = d ( ν U ⊗ ν V ) d ν ( u , v ) , which is smooth and bounded since the density of ν \nu ν T T T T , T ∗ T,T^* T , T ∗ L 2 L^2 L 2 ρ : = ρ ν ( U , V ) > 0 \rho:=\rho_\nu(U,V)>0 ρ := ρ ν ( U , V ) > 0 f , g f,g f , g T g = ρ f Tg=\rho f T g = ρ f T ∗ f = ρ g T^*f=\rho g T ∗ f = ρ g
ρ 2 Lip ( f ) Lip ( g ) ≤ κ 2 N 2 Lip ( f ) Lip ( g ) . \rho^2\operatorname{Lip}(f)\operatorname{Lip}(g)\le\frac{\kappa^2}{N^2}\operatorname{Lip}(f)\operatorname{Lip}(g). ρ 2 Lip ( f ) Lip ( g ) ≤ N 2 κ 2 Lip ( f ) Lip ( g ) . Consequently, ρ ≤ ∣ κ ∣ / N \rho\le|\kappa|/N ρ ≤ ∣ κ ∣/ N
Finally, we prove the estimate in Lemma 25 .
Proof of Lemma 25. Without loss of generality by scaling it suffices to consider Lip ( f ) ≤ 1 \operatorname{Lip}(f)\le1 Lip ( f ) ≤ 1 μ \mu μ S N − 1 \mathbb{S}^{N-1} S N − 1
g ( x ) = e ⟨ h , x ⟩ Z h ( ⟨ c , x ⟩ − E ν h ⟨ c , X ⟩ ) g(x)=\frac{e^{\langle h,x\rangle}}{Z_h}\left(\langle c,x\rangle-\mathbb{E}_{\nu_h}\langle c,X\rangle\right) g ( x ) = Z h e ⟨ h , x ⟩ ( ⟨ c , x ⟩ − E ν h ⟨ c , X ⟩ ) so that
Cov ν h ( f ( X ) , ⟨ c , X ⟩ ) = ∫ S N − 1 f ( x ) g ( x ) μ ( d x ) . \operatorname{Cov}_{\nu_h}(f(X),\langle c,X\rangle)=\int_{\mathbb{S}^{N-1}}f(x)g(x)\,\mu(dx). Cov ν h ( f ( X ) , ⟨ c , X ⟩) = ∫ S N − 1 f ( x ) g ( x ) μ ( d x ) . We seek a vector field V V V B N \mathbb{B}^N B N
div V = 0 in B N , V ( x ) ⋅ x = g ( x ) on S N − 1 . \operatorname{div}V=0\quad\text{in }\mathbb{B}^N,\qquad V(x)\cdot x=g(x)\quad\text{on }\mathbb{S}^{N-1}. div V = 0 in B N , V ( x ) ⋅ x = g ( x ) on S N − 1 . With this vector field in hand, we can then “transfer” the derivative onto f f f ∫ S N − 1 g ( x ) μ ( d x ) = 0 \int_{\mathbb{S}^{N-1}}g(x)\,\mu(dx)=0 ∫ S N − 1 g ( x ) μ ( d x ) = 0
We begin by writing h = t e h=te h = t e t = ∥ h ∥ t=\lVert h\rVert t = ∥ h ∥ ∥ e ∥ = 1 \lVert e\rVert=1 ∥ e ∥ = 1 t = 0 t=0 t = 0 e e e c = α e + v c=\alpha e+v c = α e + v v ⊥ e v\perp e v ⊥ e
Z ( s ) = ∫ S N − 1 e s e ⋅ u d ω ( u ) , m ( s ) = Z ′ ( s ) Z ( s ) . \mathcal{Z}(s)=\int_{\mathbb{S}^{N-1}}e^{se\cdot u}\,d\omega(u),\qquad m(s)=\frac{\mathcal{Z}'(s)}{\mathcal{Z}(s)}. Z ( s ) = ∫ S N − 1 e se ⋅ u d ω ( u ) , m ( s ) = Z ( s ) Z ′ ( s ) . We observe that rotational invariance of the sphere gives Z h = Z ( t ) Z_h=\mathcal{Z}(t) Z h = Z ( t ) E ν s e U = m ( s ) e \mathbb{E}_{\nu_{se}}U=m(s)e E ν se U = m ( s ) e y ↦ ∫ e y ⋅ u d ω ( u ) = Z ( ∥ y ∥ ) y\mapsto\int e^{y\cdot u}\,d\omega(u)=\mathcal{Z}(\lVert y\rVert) y ↦ ∫ e y ⋅ u d ω ( u ) = Z (∥ y ∥) Δ y Z ( ∥ y ∥ ) = Z ( ∥ y ∥ ) \Delta_y\mathcal{Z}(\lVert y\rVert)=\mathcal{Z}(\lVert y\rVert) Δ y Z (∥ y ∥) = Z (∥ y ∥) s > 0 s>0 s > 0
Z ′ ′ ( s ) + N − 1 s Z ′ ( s ) = Z ( s ) and Z ( 0 ) = 1 , Z ′ ( 0 ) = 0 , Z ′ ′ ( 0 ) = 1 N . (17) \mathcal{Z}''(s)+\frac{N-1}{s}\mathcal{Z}'(s)=\mathcal{Z}(s)\quad\text{and}\quad\mathcal{Z}(0)=1,\quad\mathcal{Z}'(0)=0,\quad\mathcal{Z}''(0)=\frac{1}{N}. \tag*{(17)} Z ′′ ( s ) + s N − 1 Z ′ ( s ) = Z ( s ) and Z ( 0 ) = 1 , Z ′ ( 0 ) = 0 , Z ′′ ( 0 ) = N 1 . (17) For 0 ≤ r ≤ 1 0\le r\le1 0 ≤ r ≤ 1
a ( r ) = Z ( t r ) Z ( t ) , b ( r ) = Z ′ ( t r ) r Z ( t ) and b ( 0 ) = t N Z ( t ) . a(r)=\frac{\mathcal{Z}(tr)}{\mathcal{Z}(t)},\qquad b(r)=\frac{\mathcal{Z}'(tr)}{r\mathcal{Z}(t)}\quad\text{and}\quad b(0)=\frac{t}{N\mathcal{Z}(t)}. a ( r ) = Z ( t ) Z ( t r ) , b ( r ) = r Z ( t ) Z ′ ( t r ) and b ( 0 ) = N Z ( t ) t . These functions extend smoothly as radial functions at the origin, since Z \mathcal{Z} Z (17) , we have a ′ ( r ) = t r b ( r ) a'(r)=trb(r) a ′ ( r ) = t r b ( r ) r b ′ ( r ) + N b ( r ) = t a ( r ) rb'(r)+Nb(r)=ta(r) r b ′ ( r ) + N b ( r ) = t a ( r ) R N \mathbb{R}^{N} R N
V ( z ) = e h ⋅ z Z ( t ) [ v + α ( a ( ∥ z ∥ ) e − b ( ∥ z ∥ ) z ) ] . V(z)=\frac{e^{h\cdot z}}{\mathcal{Z}(t)}\left[v+\alpha\left(a(\lVert z\rVert)e-b(\lVert z\rVert)z\right)\right]. V ( z ) = Z ( t ) e h ⋅ z [ v + α ( a (∥ z ∥) e − b (∥ z ∥) z ) ] . For r = ∥ z ∥ > 0 r=\lVert z\rVert>0 r = ∥ z ∥ > 0
div V ( z ) = α e h ⋅ z Z ( t ) [ t a ( r ) − r b ′ ( r ) − N b ( r ) + ( e ⋅ z ) ( a ′ ( r ) r − t b ( r ) ) ] = 0. \operatorname{div}V(z)=\frac{\alpha e^{h\cdot z}}{\mathcal{Z}(t)}\left[ta(r)-rb'(r)-Nb(r)+(e\cdot z)\left(\frac{a'(r)}{r}-tb(r)\right)\right]=0. div V ( z ) = Z ( t ) α e h ⋅ z [ t a ( r ) − r b ′ ( r ) − N b ( r ) + ( e ⋅ z ) ( r a ′ ( r ) − t b ( r ) ) ] = 0. We can extend this to the origin by smoothness. Since a ( 1 ) = 1 a(1)=1 a ( 1 ) = 1 b ( 1 ) = m ( t ) b(1)=m(t) b ( 1 ) = m ( t )
V ( u ) ⋅ u = e h ⋅ u Z h ( c ⋅ u − E ν h [ c ⋅ U ] ) ( u ∈ S N − 1 ) . (18) V(u)\cdot u=\frac{e^{h\cdot u}}{\mathcal{Z}_h}\left(c\cdot u-\mathbb{E}_{\nu_h}[c\cdot U]\right)\qquad(u\in S^{N-1}). \tag*{(18)} V ( u ) ⋅ u = Z h e h ⋅ u ( c ⋅ u − E ν h [ c ⋅ U ] ) ( u ∈ S N − 1 ) . (18) We next bound the integral of ∥ V ∥ \lVert V\rVert ∥ V ∥ r ∈ [ 0 , 1 ] r\in[0,1] r ∈ [ 0 , 1 ] s = t r s=tr s = t r r b ( r ) = a ( r ) m ( s ) rb(r)=a(r)m(s) r b ( r ) = a ( r ) m ( s )
∫ S N − 1 ∥ V ( r u ) ∥ d ω ( u ) = a ( r ) E ν s e ∥ v + α a ( r ) ( e − m ( s ) U ) ∥ ≤ a ( r ) ( ∥ v ∥ 2 + α 2 a ( r ) 2 ( 1 − m ( s ) 2 ) ) 1 / 2 Cauchy-Schwarz E ν s e U = m ( s ) e , v ⊥ e ≤ ∥ c ∥ . ∣ m ( s ) ∣ ≤ 1 , 0 < a ( r ) ≤ 1 \begin{aligned}
\int_{S^{N-1}}\lVert V(ru)\rVert\,d\omega(u)=a(r)\mathbb{E}_{\nu_s e}\left\lVert v+\alpha a(r)(e-m(s)U)\right\rVert\\
&\le a(r)\left(\lVert v\rVert^2+\alpha^2a(r)^2(1-m(s)^2)\right)^{1/2}
\qquad\substack{\text{Cauchy-Schwarz}\\ \mathbb{E}_{\nu_s e}U=m(s)e,\ v\perp e} \\
&\le\lVert c\rVert.
\qquad\substack{|m(s)|\le1,\ 0<a(r)\le1}
\end{aligned} ∫ S N − 1 ∥ V ( r u )∥ d ω ( u ) = a ( r ) E ν s e ∥ v + α a ( r ) ( e − m ( s ) U ) ∥ ≤ a ( r ) ( ∥ v ∥ 2 + α 2 a ( r ) 2 ( 1 − m ( s ) 2 ) ) 1/2 Cauchy-Schwarz E ν s e U = m ( s ) e , v ⊥ e ≤ ∥ c ∥ . ∣ m ( s ) ∣ ≤ 1 , 0 < a ( r ) ≤ 1 where 0 < a ( r ) ≤ 1 0<a(r)\le1 0 < a ( r ) ≤ 1 Z ( s ) = ∫ cosh ( s e ⋅ u ) d ω ( u ) \mathcal{Z}(s)=\int\cosh(se\cdot u)\,d\omega(u) Z ( s ) = ∫ cosh ( se ⋅ u ) d ω ( u ) s ≥ 0 s\ge0 s ≥ 0
∫ B N ∥ V ( z ) ∥ d z = ∣ S N − 1 ∣ ∫ 0 1 r N − 1 ( ∫ S N − 1 ∥ V ( r u ) ∥ d ω ( u ) ) d r ≤ ∣ S N − 1 ∣ ∥ c ∥ ∫ 0 1 r N − 1 d r = ∣ B N ∣ ∥ c ∥ . (19) \int_{\mathbb{B}^{N}}\lVert V(z)\rVert\,dz=|S^{N-1}|\int_{0}^{1}r^{N-1}\left(\int_{S^{N-1}}\lVert V(ru)\rVert\,d\omega(u)\right)\,dr\le|S^{N-1}|\lVert c\rVert\int_{0}^{1}r^{N-1}\,dr=|\mathbb{B}^{N}|\lVert c\rVert. \tag*{(19)} ∫ B N ∥ V ( z )∥ d z = ∣ S N − 1 ∣ ∫ 0 1 r N − 1 ( ∫ S N − 1 ∥ V ( r u )∥ d ω ( u ) ) d r ≤ ∣ S N − 1 ∣ ∥ c ∥ ∫ 0 1 r N − 1 d r = ∣ B N ∣ ∥ c ∥ . (19) Let f ~ \widetilde{f} f f f f R N \mathbb{R}^{N} R N
∣ Cov ν h ( f ( U ) , c ⋅ U ) ∣ = (15) ∣ ∫ S N − 1 f ~ ( u ) V ( u ) ⋅ u d ω ( u ) ∣ ≤ Proposition 16, (16) ∣ B N ∣ N ω N ∥ c ∥ = ∥ c ∥ N . \left|\operatorname{Cov}_{\nu_h}(f(U),c\cdot U)\right|
\underset{\text{(15)}}{=}\left|\int_{S^{N-1}}\widetilde{f}(u)V(u)\cdot u\,d\omega(u)\right|
\underset{\text{Proposition 16, (16)}}{\le}\frac{|\mathbb{B}^{N}|}{N\omega_N}\lVert c\rVert=\frac{\lVert c\rVert}{N}. ∣ Cov ν h ( f ( U ) , c ⋅ U ) ∣ (15) = ∫ S N − 1 f ( u ) V ( u ) ⋅ u d ω ( u ) Proposition 16, (16) ≤ N ω N ∣ B N ∣ ∥ c ∥ = N ∥ c ∥ . Application: Negative correlation in matroids
Let M = ( E , I ) M=(E,\mathcal{I}) M = ( E , I ) λ ∈ ( 0 , ∞ ) E \lambda\in(0,\infty)^E λ ∈ ( 0 , ∞ ) E I \mathcal{I} I
μ ( S ) = 1 Z ∏ e ∈ S λ e where Z = ∑ S ∈ I ∏ e ∈ S λ e . \mu(S)=\frac{1}{Z}\prod_{e\in S}\lambda_e\quad\text{where}\quad Z=\sum_{S\in\mathcal{I}}\prod_{e\in S}\lambda_e. μ ( S ) = Z 1 e ∈ S ∏ λ e where Z = S ∈ I ∑ e ∈ S ∏ λ e . When λ e = 1 \lambda_e=1 λ e = 1 e ∈ E e\in E e ∈ E
For X ∼ μ X\sim\mu X ∼ μ X e = 1 { e ∈ X } X_e=\mathbf{1}_{\{e\in X\}} X e = 1 { e ∈ X } p e = E μ X e p_e=\mathbb{E}_{\mu}X_e p e = E μ X e p e f = E μ [ X e X f ] p_{ef}=\mathbb{E}_{\mu}[X_eX_f] p e f = E μ [ X e X f ] p = ( p e ) e ∈ E p=(p_e)_{e\in E} p = ( p e ) e ∈ E Σ = ( Cov μ ( X e , X f ) ) e , f ∈ E \Sigma=(\operatorname{Cov}_{\mu}(X_e,X_f))_{e,f\in E} Σ = ( Cov μ ( X e , X f ) ) e , f ∈ E
We will first recover the following known covariance bound for matroid independent sets using the abstract machinery relating to B − 1 B^{-1} B − 1
Theorem 26. We have Σ ⪯ diag ( p ) \Sigma\preceq\operatorname{diag}(p) Σ ⪯ diag ( p ) e e e f ∈ E f \in E f ∈ E
p e f ≤ 2 p e p f . p_{ef} \le2p_ep_f. p e f ≤ 2 p e p f . For graphic matroids, whose independent sets are forests, we obtain the following stronger bound. As above, the fugacities may be arbitrary positive numbers.
Theorem 27. If M M M e e e f ∈ E f \in E f ∈ E
p e f ≤ 4 3 p e p f . p_{ef} \le\frac{4}{3}p_ep_f. p e f ≤ 3 4 p e p f . Notation
We now adapt our Hilbert space set-up to the above measure on independent sets of a matroid. First, we let H 0 = L 2 ( μ ) \mathcal{H}^{0}=L^{2}(\mu) H 0 = L 2 ( μ )
W e = ran L e , W e f = W e ∩ W f , H 1 = ⨁ e W e and H 2 = ⨁ e < f W e f . W_e=\operatorname{ran}L_e,\qquad W_{ef}=W_e\cap W_f,\qquad\mathcal{H}^{1}=\bigoplus_e W_e\qquad\text{and}\qquad\mathcal{H}^{2}=\bigoplus_{e<f}W_{ef}. W e = ran L e , W e f = W e ∩ W f , H 1 = e ⨁ W e and H 2 = e < f ⨁ W e f . As before, let W = ∑ e W e W=\sum_e W_e W = ∑ e W e P P P W W W
For this application, we define the weights c e = 1 + λ e c_e=1+\lambda_e c e = 1 + λ e
⟨ u , v ⟩ 1 = ∑ e c e ⟨ u e , v e ⟩ 0 , and ⟨ a , b ⟩ 2 = ∑ e < f c e c f ⟨ a e f , b e f ⟩ 0 . \langle u,v\rangle_1=\sum_e c_e\langle u_e,v_e\rangle_0,\qquad\text{and}\qquad\langle a,b\rangle_2=\sum_{e<f}c_ec_f\langle a_{ef},b_{ef}\rangle_0. ⟨ u , v ⟩ 1 = e ∑ c e ⟨ u e , v e ⟩ 0 , and ⟨ a , b ⟩ 2 = e < f ∑ c e c f ⟨ a e f , b e f ⟩ 0 . where we recall that ⟨ h , g ⟩ 0 = E μ [ h g ] \langle h,g\rangle_0=\mathbb{E}_{\mu}[hg] ⟨ h , g ⟩ 0 = E μ [ h g ]
As before we have d 0 : H 0 → H 1 d_0:\mathcal{H}^{0}\to\mathcal{H}^{1} d 0 : H 0 → H 1 d 1 : H 1 → H 2 d_1:\mathcal{H}^{1}\to\mathcal{H}^{2} d 1 : H 1 → H 2 ( d 0 h ) e = L e h (d_0h)_e=L_eh ( d 0 h ) e = L e h ( d 1 u ) e f = L e f ( u e − u f ) (d_1u)_{ef}=L_{ef}(u_e-u_f) ( d 1 u ) e f = L e f ( u e − u f ) L e f L_{ef} L e f W e f W_{ef} W e f L e = I − P e L_e=I-P_e L e = I − P e d 1 d 0 = 0 d_1d_0=0 d 1 d 0 = 0
d 0 ∗ u = ∑ e c e u e , Q = d 0 ∗ d 0 = ∑ e c e L e . d_0^*u=\sum_e c_eu_e,\qquad Q=d_0^*d_0=\sum_e c_eL_e. d 0 ∗ u = e ∑ c e u e , Q = d 0 ∗ d 0 = e ∑ c e L e . For S ∈ I S\in\mathcal{I} S ∈ I A ( S ) = { e ∉ S : S ∪ { e } ∈ I } A(S)=\{e\notin S:S\cup\{e\}\in\mathcal{I}\} A ( S ) = { e ∈ / S : S ∪ { e } ∈ I } S S S
( Q h ) ( S ) = ∑ e ∈ S ( h ( S ) − h ( S − e ) ) + ∑ e ∈ A ( S ) λ e ( h ( S ) − h ( S ∪ { e } ) ) . (Qh)(S)=\sum_{e\in S}\bigl(h(S)-h(S-e)\bigr)+\sum_{e\in A(S)}\lambda_e\bigl(h(S)-h(S\cup\{e\})\bigr). ( Q h ) ( S ) = e ∈ S ∑ ( h ( S ) − h ( S − e ) ) + e ∈ A ( S ) ∑ λ e ( h ( S ) − h ( S ∪ { e }) ) . Since μ ( S ) λ e = μ ( S ∪ { e } ) \mu(S)\lambda_e=\mu(S\cup\{e\}) μ ( S ) λ e = μ ( S ∪ { e }) e ∈ A ( S ) e\in A(S) e ∈ A ( S )
⟨ h , Q g ⟩ 0 = ⟨ d 0 h , d 0 g ⟩ 1 = ∑ S ∈ I μ ( S ) ∑ e ∈ A ( S ) λ e ( h ( S ∪ { e } ) − h ( S ) ) ( g ( S ∪ { e } ) − g ( S ) ) . (20) \langle h,Qg\rangle_0=\langle d_0h,d_0g\rangle_1=\sum_{S\in\mathcal{I}}\mu(S)\sum_{e\in A(S)}\lambda_e\bigl(h(S\cup\{e\})-h(S)\bigr)\bigl(g(S\cup\{e\})-g(S)\bigr). \tag*{(20)} ⟨ h , Q g ⟩ 0 = ⟨ d 0 h , d 0 g ⟩ 1 = S ∈ I ∑ μ ( S ) e ∈ A ( S ) ∑ λ e ( h ( S ∪ { e }) − h ( S ) ) ( g ( S ∪ { e }) − g ( S ) ) . (20) Since all fugacities are positive, (17) shows that ker Q \ker Q ker Q W ⊥ = ⋂ e ker L e = ker Q W^\perp=\bigcap_e\ker L_e=\ker Q W ⊥ = ⋂ e ker L e = ker Q W = L 0 2 ( μ ) W=L_0^2(\mu) W = L 0 2 ( μ ) P h = h − E μ h Ph=h-\mathbb{E}_{\mu}h P h = h − E μ h
Bochner operator. As in Lemma 20, we define B : H 1 → H 1 B:\mathcal{H}^{1}\to\mathcal{H}^{1} B : H 1 → H 1 B = d 0 d 0 ∗ + d 1 ∗ d 1 B=d_{0}d_{0}^{*}+d_{1}^{*}d_{1} B = d 0 d 0 ∗ + d 1 ∗ d 1 ( B u ) e = L e ( ∑ f c f u f ) + ∑ f ≠ e c f L e f ( u e − u f ) (Bu)_{e}=L_{e}\left(\sum_{f}c_{f}u_{f}\right)+\sum_{f\ne e}c_{f}L_{ef}(u_{e}-u_{f}) ( B u ) e = L e ( ∑ f c f u f ) + ∑ f = e c f L e f ( u e − u f ) B e f : W f → W e B_{ef}:W_{f}\to W_{e} B e f : W f → W e
B e f = { c e I + ∑ k ≠ e c k L e k , e = f , c f ( L e L f − L e f ) , e ≠ f . (21) B_{ef}=
\begin{cases}
c_{e}I+\sum_{k\ne e}c_{k}L_{ek}, & e=f,\\
c_{f}(L_{e}L_{f}-L_{ef}), & e\ne f.
\end{cases} \tag*{(21)} B e f = { c e I + ∑ k = e c k L e k , c f ( L e L f − L e f ) , e = f , e = f . (21) Indeed, whenever B B B P = d 0 ∗ B − 1 d 0 P=d_{0}^{*}B^{-1}d_{0} P = d 0 ∗ B − 1 d 0
Cov μ ( h , g ) ∣ P h = h − E μ h = ⟨ P h , P g ⟩ 0 = ⟨ d 0 h , B − 1 d 0 g ⟩ 1 . (22) \operatorname{Cov}_{\mu}(h,g)\Big|_{Ph=h-\mathbb{E}_{\mu}h}=\langle Ph,Pg\rangle_{0}=\langle d_{0}h,B^{-1}d_{0}g\rangle_{1}. \tag*{(22)} Cov μ ( h , g ) P h = h − E μ h = ⟨ P h , P g ⟩ 0 = ⟨ d 0 h , B − 1 d 0 g ⟩ 1 . (22) Matroids: Proof of Theorem 26
In this section, we expand on the intuition that the off-diagonal blocks B e f = c f ( L e L f − L e f ) B_{ef}=c_{f}(L_{e}L_{f}-L_{ef}) B e f = c f ( L e L f − L e f ) p e f ≤ 2 p e p f p_{ef}\le2p_{e}p_{f} p e f ≤ 2 p e p f
Proposition 28. We have B ⪰ I B\succeq I B ⪰ I B B B B − 1 ⪯ I B^{-1}\preceq I B − 1 ⪯ I
Assuming Proposition 28, we prove Theorem 26.
Proof of Theorem 26. Fix a ∈ R E a\in\mathbb{R}^{E} a ∈ R E h ( S ) = ∑ e ∈ S a e h(S)=\sum_{e\in S}a_{e} h ( S ) = ∑ e ∈ S a e α = 1 \alpha=1 α = 1
a T Σ a = Var μ ( h ) ≤ ⟨ h , Q h ⟩ 0 = ∑ S ∈ I μ ( S ) ∑ e ∈ A ( S ) λ e a e 2 = ∑ e a e 2 ∑ T ∈ I e ∈ T μ ( T ) = ∑ e p e a e 2 . (23) a^{\mathsf{T}}\Sigma a=\operatorname{Var}_{\mu}(h)\leq\langle h,Qh\rangle_{0}=\sum_{S\in\mathcal{I}}\mu(S)\sum_{e\in A(S)}\lambda_{e}a_{e}^{2}=\sum_{e}a_{e}^{2}\sum_{\substack{T\in\mathcal{I}\\e\in T}}\mu(T)=\sum_{e}p_{e}a_{e}^{2}. \tag*{(23)} a T Σ a = Var μ ( h ) ≤ ⟨ h , Q h ⟩ 0 = S ∈ I ∑ μ ( S ) e ∈ A ( S ) ∑ λ e a e 2 = e ∑ a e 2 T ∈ I e ∈ T ∑ μ ( T ) = e ∑ p e a e 2 . (23) Consequently, we have Σ ⪯ diag ( p ) \Sigma\preceq\operatorname{diag}(p) Σ ⪯ diag ( p )
Define Δ = diag ( p ) − Σ ⪰ 0 \Delta=\operatorname{diag}(p)-\Sigma\succeq0 Δ = diag ( p ) − Σ ⪰ 0 Δ e e = p e − Var μ ( X e ) = p e 2 \Delta_{ee}=p_{e}-\operatorname{Var}_{\mu}(X_{e})=p_{e}^{2} Δ ee = p e − Var μ ( X e ) = p e 2
p e f = p e p f − Δ e f ≤ p e p f + Δ e e Δ f f = 2 p e p f . p_{ef}=p_{e}p_{f}-\Delta_{ef}\leq p_{e}p_{f}+\sqrt{\Delta_{ee}\Delta_{ff}}=2p_{e}p_{f}. p e f = p e p f − Δ e f ≤ p e p f + Δ ee Δ f f = 2 p e p f . This completes the proof.
Finally, we prove Proposition 28.
Proof of Proposition 28. For each S ∈ I S\in\mathcal{I} S ∈ I P ( S ) \mathcal{P}(S) P ( S ) A ( S ) A(S) A ( S ) M / S M/S M / S
For u e ∈ W e u_{e}\in W_{e} u e ∈ W e u e ( S ) = − λ e u e ( S ∪ { e } ) u_{e}(S)=-\lambda_{e}u_{e}(S\cup\{e\}) u e ( S ) = − λ e u e ( S ∪ { e }) e ∈ A ( S ) e\in A(S) e ∈ A ( S ) u e ( S ) = 0 u_{e}(S)=0 u e ( S ) = 0 e ∉ S ∪ A ( S ) e\notin S\cup A(S) e ∈ / S ∪ A ( S )
∑ S ∈ I e ∈ A ( S ) μ ( S ) u e ( S ) 2 = λ e c e ∥ u e ∥ 0 2 . (24) \sum_{\substack{S\in\mathcal{I}\\e\in A(S)}}\mu(S)u_{e}(S)^{2}=\frac{\lambda_{e}}{c_{e}}\lVert u_{e}\rVert_{0}^{2}. \tag*{(24)} S ∈ I e ∈ A ( S ) ∑ μ ( S ) u e ( S ) 2 = c e λ e ∥ u e ∥ 0 2 . (24) Next, we condition on all coordinates except e , f e,f e , f S ∪ { e , f } S\cup\{e,f\} S ∪ { e , f } L e L f = L e f L_{e}L_{f}=L_{ef} L e L f = L e f S S S { e } \{e\} { e } { f } \{f\} { f } e , f e,f e , f M / S M/S M / S
( L e f u f ) ( S ) = − λ e ( L e f u f ) ( S ∪ { e } ) = − λ e [ ( I − P f ) L e f u f ] ( S ∪ { e } ) = − λ e ( ( L e f u f ) ( S ∪ { e } ) − ( L e f u f ) ( S ∪ { e } ) ) = 0. (25) \begin{aligned}
(L_{ef}u_f)(S)=-\lambda_e(L_{ef}u_f)(S\cup\{e\})=-\lambda_e[(I-P_f)L_{ef}u_f](S\cup\{e\}) \\
&=-\lambda_e\big((L_{ef}u_f)(S\cup\{e\})-(L_{ef}u_f)(S\cup\{e\})\big)=0. \tag*{(25)}
\end{aligned} ( L e f u f ) ( S ) = − λ e ( L e f u f ) ( S ∪ { e }) = − λ e [( I − P f ) L e f u f ] ( S ∪ { e }) = − λ e ( ( L e f u f ) ( S ∪ { e }) − ( L e f u f ) ( S ∪ { e }) ) = 0. (25) It follows that the term in ⟨ u , ( B − I ) u ⟩ 1 \langle u,(B-I)u\rangle_1 ⟨ u , ( B − I ) u ⟩ 1 S S S S ∪ { e } S\cup\{e\} S ∪ { e } S ∪ { f } S\cup\{f\} S ∪ { f }
c e ∑ T ∈ { S , S ∪ { e } , S ∪ { f } } μ ( T ) u e ( T ) ( B e f u f ) ( T ) = c e c f ∑ T ∈ { S , S ∪ { e } , S ∪ { f } } μ ( T ) u e ( T ) u f ( T ) c_e\sum_{T\in\{S,S\cup\{e\},S\cup\{f\}\}}\mu(T)u_e(T)(B_{ef}u_f)(T)
=
c_ec_f\sum_{T\in\{S,S\cup\{e\},S\cup\{f\}\}}\mu(T)u_e(T)u_f(T) c e T ∈ { S , S ∪ { e } , S ∪ { f }} ∑ μ ( T ) u e ( T ) ( B e f u f ) ( T ) = c e c f T ∈ { S , S ∪ { e } , S ∪ { f }} ∑ μ ( T ) u e ( T ) u f ( T ) where L e u e = u e L_eu_e=u_e L e u e = u e L f u f = u f L_fu_f=u_f L f u f = u f u e ( S ∪ { f } ) = u f ( S ∪ { e } ) = 0 u_e(S\cup\{f\})=u_f(S\cup\{e\})=0 u e ( S ∪ { f }) = u f ( S ∪ { e }) = 0
= c e c f μ ( S ) u e ( S ) u f ( S ) . =c_ec_f\mu(S)u_e(S)u_f(S). = c e c f μ ( S ) u e ( S ) u f ( S ) . Consequently, summing up the above over all S S S e , f e,f e , f u = ( u e ) e ∈ E ∈ H 1 u=(u_e)_{e\in E}\in\mathcal{H}^1 u = ( u e ) e ∈ E ∈ H 1
⟨ u , ( B − I ) u ⟩ 1 ≥ ∑ e c e λ e ∥ u e ∥ 0 2 + ∑ S ∈ I μ ( S ) ∑ C ∈ P ( S ) ∑ e , f ∈ C e ≠ f c e c f u e ( S ) u f ( S ) = ∑ S ∈ I μ ( S ) ∑ C ∈ P ( S ) ( ∑ e ∈ C c e u e ( S ) ) 2 ≥ 0. (26) \begin{aligned}
\langle u,(B-I)u\rangle_1\geq\sum_e c_e\lambda_e\lVert u_e\rVert_0^2+\sum_{S\in\mathcal{I}}\mu(S)\sum_{C\in\mathcal{P}(S)}\sum_{\substack{e,f\in C\\e\ne f}}c_ec_fu_e(S)u_f(S) \\
&=\sum_{S\in\mathcal{I}}\mu(S)\sum_{C\in\mathcal{P}(S)}\left(\sum_{e\in C}c_eu_e(S)\right)^2\geq0. \tag*{(26)}
\end{aligned} ⟨ u , ( B − I ) u ⟩ 1 ≥ e ∑ c e λ e ∥ u e ∥ 0 2 + S ∈ I ∑ μ ( S ) C ∈ P ( S ) ∑ e , f ∈ C e = f ∑ c e c f u e ( S ) u f ( S ) = S ∈ I ∑ μ ( S ) C ∈ P ( S ) ∑ ( e ∈ C ∑ c e u e ( S ) ) 2 ≥ 0. (26) This shows that B ⪰ I B\succeq I B ⪰ I B B B B − 1 ⪯ I B^{-1}\preceq I B − 1 ⪯ I
Forests: Proof of Theorem 29
We now turn from the general matroid set-up to the setting of forests, where the additional structure in graphic matroids allows us to sharpen the correlation bound. For spanning trees, we recall that negative correlation can be proven via the determinantal representation and real stability of the spanning-tree polynomial. As described in the technical overview, our strategy is to extend this determinantal representation to the setting of forests.
While showing log-concavity of this auxiliary polynomial is the driving force of this proof, one way to compare this with the analysis of § 5.2 is that here this real stability provides a more fine-grained bound of quadratic forms of B − 1 B^{-1} B − 1 im ( d 0 ) \operatorname{im}(d_0) im ( d 0 )
In the following, we define
s e f = Pr μ ( e , f are edges of the same tree component of F ) and S = ( s e f ) e , f ∈ E . s_{ef}=\Pr_{\mu}(e,f\text{ are edges of the same tree component of }F)
\quad\text{and}\quad S=(s_{ef})_{e,f\in E}. s e f = μ Pr ( e , f are edges of the same tree component of F ) and S = ( s e f ) e , f ∈ E . Particularly, s e e = p e s_{ee}=p_e s ee = p e s e f ≤ p e f s_{ef}\leq p_{ef} s e f ≤ p e f
Theorem 29. We have
Σ ⪰ 3 4 diag ( p ) + 1 4 S . (27) \Sigma\succeq\frac{3}{4}\operatorname{diag}(p)+\frac{1}{4}S. \tag*{(27)} Σ ⪰ 4 3 diag ( p ) + 4 1 S . (27) Moreover, for all distinct e , f ∈ E e,f\in E e , f ∈ E
4 ( p e f − p e p f ) ≤ s e f ≤ p e f . 4(p_{ef}-p_ep_f)\leq s_{ef}\leq p_{ef}. 4 ( p e f − p e p f ) ≤ s e f ≤ p e f . Consequently,
p e f ≤ 4 3 p e p f . p_{ef}\leq\frac{4}{3}p_ep_f. p e f ≤ 3 4 p e p f . The following result gives the bounds on ⟨ d 0 X e , B − 1 d 0 X f ⟩ \langle d_0X_e,B^{-1}d_0X_f\rangle ⟨ d 0 X e , B − 1 d 0 X f ⟩ H 1 \mathcal{H}^1 H 1
Proposition 30. For every a ∈ R E \mathbf{a}\in\mathbb{R}^E a ∈ R E h = ∑ e a e X e \mathbf{h}=\sum_e a_eX_e h = ∑ e a e X e
4 ⟨ d 0 h , B − 1 d 0 h ⟩ 1 ≤ a T ( 3 diag ( p ) + S ) a . (28) 4\langle d_0\mathbf{h},B^{-1}d_0\mathbf{h}\rangle_1\leq\mathbf{a}^{\mathsf{T}}(3\operatorname{diag}(\mathbf{p})+S)\mathbf{a}. \tag*{(28)} 4 ⟨ d 0 h , B − 1 d 0 h ⟩ 1 ≤ a T ( 3 diag ( p ) + S ) a . (28) Moreover, for all distinct e , f ∈ E e,f\in E e , f ∈ E
4 c e ⟨ L e X e , ( B − 1 ) e f L f X f ⟩ 0 ≤ s e f . (29) 4c_e\langle L_eX_e,(B^{-1})_{ef}L_fX_f\rangle_0\leq s_{ef}. \tag*{(29)} 4 c e ⟨ L e X e , ( B − 1 ) e f L f X f ⟩ 0 ≤ s e f . (29) Assuming Proposition 30, we prove Theorem 29.
Proof of Theorem 29. Fix a ∈ R E \mathbf{a}\in\mathbb{R}^E a ∈ R E h = ∑ e ∈ E a e X e \mathbf{h}=\sum_{e\in E}a_eX_e h = ∑ e ∈ E a e X e
a T Σ a = ⟨ d 0 h , B − 1 d 0 h ⟩ 1 ≤ 1 4 a T ( 3 diag ( p ) + S ) a . \mathbf{a}^{\mathsf{T}}\Sigma\mathbf{a}=\langle d_0\mathbf{h},B^{-1}d_0\mathbf{h}\rangle_1\leq\frac{1}{4}\mathbf{a}^{\mathsf{T}}(3\operatorname{diag}(\mathbf{p})+S)\mathbf{a}. a T Σ a = ⟨ d 0 h , B − 1 d 0 h ⟩ 1 ≤ 4 1 a T ( 3 diag ( p ) + S ) a . Since the choice of a \mathbf{a} a
For distinct e , f e,f e , f d 0 X e d_0X_e d 0 X e e e e
4 ( p e f − p e p f ) = 4 c e ⟨ L e X e , ( B − 1 ) e f L f X f ⟩ 0 ≤ s e f ≤ p e f . 4(p_{ef}-p_ep_f)=4c_e\langle L_eX_e,(B^{-1})_{ef}L_fX_f\rangle_0\leq s_{ef}\leq p_{ef}. 4 ( p e f − p e p f ) = 4 c e ⟨ L e X e , ( B − 1 ) e f L f X f ⟩ 0 ≤ s e f ≤ p e f . Rearranging gives the desired inequality p e f ≤ 4 3 p e p f p_{ef}\leq\frac{4}{3}p_ep_f p e f ≤ 3 4 p e p f
The main step is to study a polynomial that in some sense generalizes the determinant construction used to prove negative correlation for spanning trees; we define
A F = diag ( X ) + ∑ T ∈ Comp ( F ) 1 E ( T ) 1 E ( T ) T and Φ ( z ) = E μ det ( I + diag ( z ) A F ) . (30) A_F=\operatorname{diag}(X)+\sum_{T\in\operatorname{Comp}(F)}\mathbf{1}_{E(T)}\mathbf{1}_{E(T)}^{\mathsf{T}}
\quad\text{and}\quad
\Phi(\mathbf{z})=\mathbb{E}_{\mu}\det(I+\operatorname{diag}(\mathbf{z})A_F). \tag*{(30)} A F = diag ( X ) + T ∈ Comp ( F ) ∑ 1 E ( T ) 1 E ( T ) T and Φ ( z ) = E μ det ( I + diag ( z ) A F ) . (30) Proposition 31. The polynomial Φ \Phi Φ
Assuming Proposition 31, we prove Proposition 30.
Proof of Proposition 30. We claim that
∇ 2 log Φ ( 0 ) = 4 ( c e ⟨ L e X e , ( B − 1 ) e f L f X f ⟩ 0 ) e , f ∈ E − 3 diag ( p ) − S . (31) \nabla^2\log\Phi(0)=4\left(c_e\langle L_eX_e,(B^{-1})_{ef}L_fX_f\rangle_0\right)_{e,f\in E}-3\operatorname{diag}(\mathbf{p})-S. \tag*{(31)} ∇ 2 log Φ ( 0 ) = 4 ( c e ⟨ L e X e , ( B − 1 ) e f L f X f ⟩ 0 ) e , f ∈ E − 3 diag ( p ) − S . (31) the proof of which we defer to the end. For now we use this identity and the real stability of Φ \Phi Φ B − 1 B^{-1} B − 1
Since A F ⪰ 0 A_F\succeq0 A F ⪰ 0 Φ \Phi Φ Φ ( 0 ) = 1 \Phi(0)=1 Φ ( 0 ) = 1 e ≠ f e\ne f e = f
∇ 2 log Φ ( 0 ) ⪯ Fact 19 0 and ∂ e ∂ f log Φ ( 0 ) ≤ Fact 17 0. (32) \nabla^2\log\Phi(0)\underset{\text{Fact 19}}{\preceq}0
\quad\text{and}\quad
\partial_e\partial_f\log\Phi(0)\underset{\text{Fact 17}}{\leq}0. \tag*{(32)} ∇ 2 log Φ ( 0 ) Fact 19 ⪯ 0 and ∂ e ∂ f log Φ ( 0 ) Fact 17 ≤ 0. (32) We let a ∈ R E \mathbf{a}\in\mathbb{R}^E a ∈ R E h = ∑ e a e X e \mathbf{h}=\sum_e a_eX_e h = ∑ e a e X e e e e d 0 X e d_0X_e d 0 X e
4 ⟨ d 0 h , B − 1 d 0 h ⟩ 1 = a T ( ∇ 2 log Φ ( 0 ) + 3 diag ( p ) + S ) a ≤ a T ( 3 diag ( p ) + S ) a . (33) 4\langle d_0\mathbf{h},B^{-1}d_0\mathbf{h}\rangle_1
=\mathbf{a}^{\mathsf{T}}\left(\nabla^2\log\Phi(0)+3\operatorname{diag}(\mathbf{p})+S\right)\mathbf{a}
\leq\mathbf{a}^{\mathsf{T}}(3\operatorname{diag}(\mathbf{p})+S)\mathbf{a}. \tag*{(33)} 4 ⟨ d 0 h , B − 1 d 0 h ⟩ 1 = a T ( ∇ 2 log Φ ( 0 ) + 3 diag ( p ) + S ) a ≤ a T ( 3 diag ( p ) + S ) a . (33) This proves (28) . For distinct e e e f f f
4 c e ⟨ L e e e , ( B − 1 ) e f L f x f ⟩ 0 = ∂ e ∂ f log Φ ( 0 ) + s e f (34) 4c_e\langle L_e\mathbf{e}_e,(B^{-1})_{ef}L_f\mathbf{x}_f\rangle_0=\partial_e\partial_f\log\Phi(0)+s_{ef} \tag*{(34)} 4 c e ⟨ L e e e , ( B − 1 ) e f L f x f ⟩ 0 = ∂ e ∂ f log Φ ( 0 ) + s e f (34) ≤ s e f (35) \le s_{ef} \tag*{(35)} ≤ s e f (35) which proves (29) .
It remains to prove (27). For z z z
H ( z , F ) = log det ( I + diag ( z ) A F ) , Φ ( z ) = E μ e H ( z , F ) . H(z,F)=\log\det(I+\operatorname{diag}(z)A_F),\qquad\Phi(z)=\mathbb{E}_{\mu}e^{H(z,F)}. H ( z , F ) = log det ( I + diag ( z ) A F ) , Φ ( z ) = E μ e H ( z , F ) . Since H ( 0 , F ) = 0 H(0,F)=0 H ( 0 , F ) = 0
∇ 2 log Φ ( 0 ) = E μ ∇ 2 H ( 0 , F ) + Cov μ ( ∇ H ( 0 , F ) ) . \nabla^2\log\Phi(0)=\mathbb{E}_{\mu}\nabla^2H(0,F)+\operatorname{Cov}_{\mu}\bigl(\nabla H(0,F)\bigr). ∇ 2 log Φ ( 0 ) = E μ ∇ 2 H ( 0 , F ) + Cov μ ( ∇ H ( 0 , F ) ) . Since ∂ e H ( 0 , F ) = ( A F ) e e = 2 X e \partial_eH(0,F)=(A_F)_{ee}=2X_e ∂ e H ( 0 , F ) = ( A F ) ee = 2 X e ∂ e ∂ f H ( 0 , F ) = − ( A F ) e f 2 \partial_e\partial_fH(0,F)=-(A_F)^2_{ef} ∂ e ∂ f H ( 0 , F ) = − ( A F ) e f 2
E μ ∂ e ∂ f H ( 0 , F ) = { − 4 p e , e = f , − s e f , e ≠ f . \mathbb{E}_{\mu}\partial_e\partial_fH(0,F)=
\begin{cases}
-4p_e, & e=f,\\
-s_{ef}, & e\ne f.
\end{cases} E μ ∂ e ∂ f H ( 0 , F ) = { − 4 p e , − s e f , e = f , e = f . Since s e e = p e s_{ee}=p_e s ee = p e E μ ∇ 2 H ( 0 , F ) = − 3 diag ( p ) − S \mathbb{E}_{\mu}\nabla^2H(0,F)=-3\operatorname{diag}(p)-S E μ ∇ 2 H ( 0 , F ) = − 3 diag ( p ) − S ∇ 2 log Φ ( 0 ) = − 3 diag ( p ) − S + 4 Cov μ ( X ) \nabla^2\log\Phi(0)=-3\operatorname{diag}(p)-S+4\operatorname{Cov}_{\mu}(X) ∇ 2 log Φ ( 0 ) = − 3 diag ( p ) − S + 4 Cov μ ( X ) (22) to each entry of Cov μ ( X ) \operatorname{Cov}_{\mu}(X) Cov μ ( X )
Proof of Proposition 31. For an edge e = u v e=uv e = uv b e = e u − e v \mathbf{b}_e=\mathbf{e}_u-\mathbf{e}_v b e = e u − e v x = ( x v ) v ∈ V \mathbf{x}=(x_v)_{v\in V} x = ( x v ) v ∈ V
R ( x , z ) = det ( diag ( x ) + ∑ e ∈ E λ e ( 1 + z e ) b e b e T ) , T = ∏ e = u v ∈ E ( 1 − λ e ∂ x u ∂ x v ) . R(\mathbf{x},z)=\det\left(\operatorname{diag}(\mathbf{x})+\sum_{e\in E}\lambda_e(1+z_e)\mathbf{b}_e\mathbf{b}_e^{\mathsf T}\right),\qquad
\mathcal{T}=\prod_{e=uv\in E}(1-\lambda_e\partial_{x_u}\partial_{x_v}). R ( x , z ) = det ( diag ( x ) + e ∈ E ∑ λ e ( 1 + z e ) b e b e T ) , T = e = uv ∈ E ∏ ( 1 − λ e ∂ x u ∂ x v ) . The key identity is
Z Φ ( z ) = T R ( x , z ) ∣ x = 1 . (36) Z\Phi(z)=\left.\mathcal{T}R(\mathbf{x},z)\right|_{\mathbf{x}=\mathbf{1}}. \tag*{(36)} Z Φ ( z ) = T R ( x , z ) ∣ x = 1 . (36) Assuming this identity, we prove the real stability of Φ \Phi Φ R R R x , z \mathbf{x},z x , z R R R
diag ( Im x ) + ∑ e ∈ E λ e Im ( z e ) b e b e T ≻ 0 , \operatorname{diag}(\operatorname{Im}\mathbf{x})+\sum_{e\in E}\lambda_e\operatorname{Im}(z_e)\mathbf{b}_e\mathbf{b}_e^{\mathsf T}\succ0, diag ( Im x ) + e ∈ E ∑ λ e Im ( z e ) b e b e T ≻ 0 , and is therefore nonsingular.
Moreover, R R R x , z \mathbf{x},z x , z T \mathcal{T} T Fact 18 . The resulting polynomial is still multiaffine, and its Rayleigh inequalities remain valid after setting x = 1 \mathbf{x}=\mathbf{1} x = 1 Fact 17 and (36) therefore show that Φ \Phi Φ
Finally, we prove (36) . To that end, we first apply the rooted-forest form of the weighted matrix-tree theorem to write
R ( x , z ) = ∑ H ∈ F ( G ) ∏ e ∈ H λ e ( 1 + z e ) ∏ C ∈ Comp ( H ) ( ∑ v ∈ V ( C ) x v ) . R(\mathbf{x},z)=\sum_{H\in\mathcal{F}(G)}\prod_{e\in H}\lambda_e(1+z_e)\prod_{C\in\operatorname{Comp}(H)}\left(\sum_{v\in V(C)}x_v\right). R ( x , z ) = H ∈ F ( G ) ∑ e ∈ H ∏ λ e ( 1 + z e ) C ∈ Comp ( H ) ∏ v ∈ V ( C ) ∑ x v . When we expand the final product, we correspondingly choose a root for each connected component of $H. concat? In the expansion of T \mathcal{T} T − λ e ∂ x u ∂ x v -\lambda_e\partial_{x_u}\partial_{x_v} − λ e ∂ x u ∂ x v u u u v v v e = u v e=uv e = uv − λ e -\lambda_e − λ e
After setting x = 1 x=1 x = 1 T T T
(We did not add any edge to join two components.) The original component was T T T ∣ V ( T ) ∣ |V(T)| ∣ V ( T ) ∣ ∣ V ( T ) ∣ ∏ f ∈ E ( T ) λ f ( 1 + z f ) |V(T)|\prod_{f\in E(T)}\lambda_f(1+z_f) ∣ V ( T ) ∣ ∏ f ∈ E ( T ) λ f ( 1 + z f )
(We added an edge e = u v e=uv e = uv e e e T T T u u u v v v e ∈ E ( T ) e\in E(T) e ∈ E ( T )
− λ e ∏ f ∈ E ( T ) ∖ { e } λ f ( 1 + z f ) . -\lambda_e\prod_{f\in E(T)\setminus\{e\}}\lambda_f(1+z_f). − λ e f ∈ E ( T ) ∖ { e } ∏ λ f ( 1 + z f ) . Summing these possibilities, the contribution of T T T
λ E ( T ) [ ∣ V ( T ) ∣ ∏ e ∈ E ( T ) ( 1 + z e ) − ∑ e ∈ E ( T ) ∏ f ∈ E ( T ) ∖ { e } ( 1 + z f ) ] . (37) \lambda^{E(T)}\left[|V(T)|\prod_{e\in E(T)}(1+z_e)-\sum_{e\in E(T)}\prod_{f\in E(T)\setminus\{e\}}(1+z_f)\right]. \tag*{(37)} λ E ( T ) ∣ V ( T ) ∣ e ∈ E ( T ) ∏ ( 1 + z e ) − e ∈ E ( T ) ∑ f ∈ E ( T ) ∖ { e } ∏ ( 1 + z f ) . (37) The choices in distinct connected components are independent, so their contributions multiply. For S ⊆ E ( T ) S\subseteq E(T) S ⊆ E ( T ) z S z^S z S ∣ V ( T ) ∣ − ∣ E ( T ) ∖ S ∣ = 1 + ∣ S ∣ |V(T)|-|E(T)\setminus S|=1+|S| ∣ V ( T ) ∣ − ∣ E ( T ) ∖ S ∣ = 1 + ∣ S ∣
On the other hand, the block of A F A_F A F E ( T ) E(T) E ( T ) I + 11 T I+\mathbf{1}\mathbf{1}^{\mathsf{T}} I + 1 1 T S S S det ( I ∣ S ∣ + 11 T ) = 1 + ∣ S ∣ \det(I_{|S|}+\mathbf{1}\mathbf{1}^{\mathsf{T}})=1+|S| det ( I ∣ S ∣ + 1 1 T ) = 1 + ∣ S ∣
From a principal-minor expansion, for every S ⊆ F S\subseteq F S ⊆ F z S z^S z S det ( I + diag ( z ) A F ) \det(I+\operatorname{diag}(z)A_F) det ( I + diag ( z ) A F ) ∏ T ∈ Comp ( F ) ( 1 + ∣ S ∩ E ( T ) ∣ ) \prod_{T\in\operatorname{Comp}(F)}(1+|S\cap E(T)|) ∏ T ∈ Comp ( F ) ( 1 + ∣ S ∩ E ( T ) ∣ ) A F A_F A F z S z^S z S
AI Declaration
We used OpenAI’s ChatGPT extensively in the mathematical development and preparation of this paper. Our use included proposing and refining mathematical formulations, exploring proof strategies, developing and checking candidate arguments, working through calculations and examples, identifying relevant literature, and drafting and revising exposition and notation. Some of these exchanges produced substantial derivations and proposed complete proofs that influenced the statements and arguments presented in the paper. The use of ChatGPT was iterative and interwoven with the authors’ research and writing, as described below.
Hilbert-space framework and general results. ChatGPT assisted in developing the general formulation in terms of closed subspaces and orthogonal projections on a possibly infinite-dimensional Hilbert space, and in extending the relevant finite-spin results to this setting. This included developing and explaining the maps d 0 d_0 d 0 d 1 d_1 d 1 B = d 0 d 0 ∗ + d 1 ∗ d 1 B=d_0d_0^*+d_1^*d_1 B = d 0 d 0 ∗ + d 1 ∗ d 1 B − 1 B^{-1} B − 1
The assistance also extended to the formulation and proof of the general block result. Following our questions about passing from individual coordinates to disjoint groups of coordinates, ChatGPT proposed and developed restriction and compression arguments, Schur-complement comparisons, and estimates for the resulting operator blocks. It supplied substantial candidate proof material for the general projection theorem and its application to the spectral gaps of marginal distributions grouped into blocks. We examined and revised this material as the generalization was incorporated into the main results of the paper. ChatGPT also helped develop the Gaussian interpretation of the comparison matrix and the examples showing sharpness of the bounds. The research questions and earlier results supplied by the authors guided these exchanges; the resulting assistance affected both the statements and the proofs of the generalization.
Negative correlations in matroids and forests. ChatGPT assisted substantially with the mathematical development of Section 5. This included calculations and proof arguments involving the weighted Bochner operator, covariance identities involving its inverse, and the recovery of the factor 2 bound on pairwise inclusion probabilities for random matroid independent sets. In particular, in response to our request to generalize the determinantal proof of negative correlation for spanning trees using the Bochner framework, ChatGPT suggested the approach based on real stability that yields the 4 3 \frac{4}{3} 3 4
The O ( N ) O(N) O ( N ) In Section 4, ChatGPT assisted in developing the radial ansatz and coefficient functions for the divergence-free vector field used to prove the covariance bound for tilted spherical measures. This is a substantive ingredient of the local inequality underlying the O ( N ) O(N) O ( N )
Related literature, interpretations, and further consequences. We used ChatGPT to identify and examine relevant literature and to compare the hypotheses, normalizations, and conclusions of related results. This included comparisons with existing Bochner and trickle-down arguments, covariance representations, and results on angles between subspaces, including those of Kassabov. ChatGPT also assisted in deriving and presenting consequences and comparisons involving λ \lambda λ
Writing, review, and author responsibility. We used ChatGPT to review successive manuscript drafts, suggest corrections and missing explanations, and help revise the abstract, introduction, technical overview, proofs, notation, and LaTeX. Earlier drafts also included AI-assisted transcriptions of author-supplied mathematical notes. The assistance included generating draft passages, proposing alternative organizations and explanations, and shortening or expanding arguments during revision. We also used the tool to explore alternative proof approaches and broader connections, including directions that were not retained in the paper.
Throughout this process, the authors supplied questions, existing results, draft statements, arguments, and manuscript versions; examined the responses; and developed, corrected, or discarded suggestions. Some AI-generated proposals contained errors, overlooked hypotheses, or did not lead to complete arguments. The authors selected and revised the material included in the paper and take full responsibility for its accuracy, originality, and integrity, including its mathematical statements, proofs, and references and all material developed with AI assistance. ChatGPT also assisted in preparing this declaration.
