Appendix B — Prerequisites

Open source document →

1. #1

   Fact B.1 (Bi-invariant metric). Every compact Lie group admits an -invariant inner product on its Lie algebra . The corresponding left-invariant Riemannian metric on is automatically bi-invariant. The geodesic distance satisfies:

   $$d_G(kg{k}^{\prime },kh{k}^{\prime })=d_G(g,h)\forall g,h,k,k^{\prime }\in G.$$
2. #2

   Fact B.3 (Discrete Cheeger inequality). For the Cheeger constant :

   $$\frac{{\lambda }_2}{2}\le h\le \sqrt{2{\lambda }_2}.$$
3. #3

   Definition. For :

   $$\varphi (S)=\frac{\mathrm{cut}(S,\bar{S})}{\min \{\mathrm{vol}(S),\mathrm{vol}(\bar{S})\}}.$$
4. #4

   Fact B.5 (Conductance and mixing time). For the lazy random walk , the mixing time satisfies:

   $$t_{\mathrm{mix}}(ϵ)\ge \frac{1}{2\varphi }\ln \frac{1}{2ϵ}$$
5. #5

   Fact B.6 (Sinclair--Jerrum conductance bound). For a reversible Markov chain with conductance , the spectral gap satisfies:

   $$\frac{{\Phi }^2}{2}\le \gamma \le 2\Phi .$$
6. #6

   Fact B.8 (Lojasiewicz inequality, finite-dimensional). Let be a real-analytic function on a compact Riemannian manifold . For every critical value of , there exist and such that in a neighbourhood of :

   $$\Vert \mathrm{grad}f(x)\Vert \ge C|f(x)-c{|}^{\alpha }.$$
7. #7

   Fact B.8 (Lojasiewicz inequality, finite-dimensional). Let be a real-analytic function on a compact Riemannian manifold . For every critical value of , there exist and such that in a neighbourhood of : Consequence.

   $${\int }_0^{\infty }\Vert \dot{x}(t)\Vert dt<\infty .$$