Certifying numerical estimates of spectral gaps (Q1647864)

Kazhdan constants of discrete groups are hard to compute and are known only for several classes of groups. By solving a semidefinite programming problem by a computer, the authors obtain a lower bound of the Kazhdan constant of a discrete group. Let \(G = \langle S \mid R\rangle\) be a finitely presented group with a finite generating set \(S\) with a finite set of relations \(R\), \((\pi, \mathcal H)\) be an orthogonal representation and \(\mathcal H^\pi= \{ v \in \mathcal H: \pi(g)v= v, \forall g \in G\}\). If one denotes by \[ \mathcal K(G, S, \pi) = \inf\{\sup_{ g\in S} \|\pi(g) \xi - \xi\| : \xi \in (\mathcal H^\pi)^\perp,\| \xi \| = 1\}, \] the Kazhdan constant \(\mathcal K(G, S)\) is defined as the infimum of \(\mathcal K(G, S, \pi)\) over all orthogonal representations \(\pi\) of \(G\). We say that \(G\) has the Kazhdan property (T) if and only if there exists a finite generating set \(S\) such that \(\mathcal K(G, S) > 0\). It is known that property (T) is equivalent to the positivity of the operator \( \Delta^2 -\lambda \Delta\) in the maximal group \(C^*\)-algebra, for some positive \(\lambda \). If the set S is assumed symmetric, i.e. \(S^{-1} = S\), the unnormalized Laplace operator \(\Delta _S \in \mathbb{R}[G]\), associated to \(S\), is defined by: \(\Delta_S= \frac{1}{2}\sum_{g\in S} (1-g)^*(1-g)\), where \(~*\) is the involution on \(\mathbb R[G]\). Analogously to \(\mathcal K(G, S)\), the authors define \(\lambda (G, S, \pi)\) as the spectral gap of \(\pi(\Delta_S)\), i.e. its first non-zero eigenvalue, and \(\lambda(G, S)\) as the infimum of the \(\lambda's\) over all representations \(\pi\) without non-zero invariant vector. The spectral gap is related to the Kazhdan constant by the inequality: \[ \sqrt{\frac{2\lambda (G, S)}{| S|} } \leq \mathcal K(G, S). \] For a discrete group \(G\) the Kazhdan property (T) is equivalent to the existence a constant \(\lambda > 0\) and \(\xi_1, \dots , \xi_k \in \mathbb R[G]\) such that \( \Delta^2_S-\lambda \Delta_S= \sum_{i=1}^k \xi_i^*\xi_i\), and that \(\lambda \) is a lower bound for \(\lambda(G, S)\). A sum-of-squares decomposition in a subspace \( V \) of \(\mathbb R[G]\) is then equivalent to the existence of a semi-positive definite matrix \(P\) satisfying: \(\Delta_S ^2- \lambda \Delta_S= x^*Px \), where \(x\in V\). The optimisation problem for the sum-of-squares decomposition can be described as a semidefinite programming SDP: minimise \( -\lambda\), subject to \(x^* P x = \Delta^2_S-\lambda \Delta_S, \lambda \geq 0\), where \(P\) denotes semi-positive definiteness. The authors use a specialised algebraic modeling language to specify SDP problems and software which to obtain approximate values \(\lambda_0\) and \(P_0\) with surprising efficiency. The two key problems here are the following: The choice of a subspace V turning the approximate solution \((\lambda_0, P_0)\) into an exact one, i.e. dealing with the residual of the numerical solution \( r = \Delta^2 - \lambda_0\Delta - x^* P_0 x \simeq 0 .\)