A hardness of approximation result in metric geometry (Q785622)

Recent work of \textit{G. R. Chambers} et al. [J. Am. Math. Soc. 31, No. 4, 1165--1203 (2018; Zbl 1402.53035)] shows that for a contractible map \(S^n\to S^m\) of Lipschitz constant \(L\) one has a null-homotopy of Lipschitz constant \(C(m,n)(L+1)\). The paper under review uses these recent ideas to accurately estimate the Lipschitz constants Lip\((\alpha)\) of certain cohomology classes \(\alpha\in H^n(\Sigma;\mathbf{Z})\), that is, of the smallest Lipschitz constant of maps \(g\colon \Sigma\to S^n\) with \(g^*\left[S^n\right]=\alpha\). Let \(\Sigma\) be a triangulated manifold and define a metric on \(\Sigma\) by declaring all simplices to be regular of unit length. One may then ask for the optimal Lipschitz constant \(L_1(\Sigma)\) of a degree-1 map, respectively \(L_{\not=0}(\Sigma)\) for a map of non-zero degree, from \(\Sigma\) to the unit sphere of the same dimension. (The invariant \(L_{\not=0}(\Sigma)\) is the inverse of the hyperspherical radius defined by Gromov-Lawson.) For a triangulated 2-sphere \(\Sigma\), \textit{L. Guth} [Geom. Funct. Anal. 15, No. 5, 1052--1090 (2005; Zbl 1101.53021)] proved that the optimal Lipschitz constant of a degree-1 map is between \(\frac{1}{D}\) and \(\frac{12}{D}\), where \(D\) is the largest diameter of (some component of) a distance sphere. His proof yields a polynomial-time algorithm to compute \(L_{\not=0}(\Sigma)\) up to a constant factor. The paper under review shows that such a polynomial-time algorithm can not exist neither for surfaces of higher genus nor for spheres of higher dimension. It shows that in these cases, both \(L_{\not=0}(\Sigma)\) and \(L_1(\Sigma)\) are NP-hard to approximate within \(N^{\frac{c}{\log\log N}}\), where \(N=\operatorname{vol}(\Sigma)\) and \(c\) depends on \(\dim(\Sigma)\). An essential ingredient of the proof is the hardness of approximation result for the shortest vector problem in \(L^\infty\), due to \textit{I. Dinur} [Theor. Comput. Sci. 285, No. 1, 55--71 (2002; Zbl 1016.68041)]. From the proof of that result one has a basis \(u_0,u_1,\ldots,u_M\) of a lattice \(\Gamma\subset\mathbf{Z}^N\) with \(\Vert u_j\Vert_\infty\) polynomial in \(N\), such that it is NP-hard to distinguish the case that there is \(v=u_0+\sum_{j=1}^Ma_ju_j\) with \(a_j\in\left\{0,1\right\}\) and \(\Vert v\Vert_\infty=1\) from the case that there is no \(v\not=0\) with \(\Vert v\Vert_\infty\le N^{\frac{C}{\log\log N}}\). The idea of the proof for the main theorem is then to construct an \((n+1)\)-dimensional simplicial complex \(X\) with an isomorphism \(\Gamma\simeq H^n(X;\mathbf{Z})\), so that the \(l^\infty\)-norm on \(\Gamma\) is closely related to the simplicial comass norm on \(H^n(X;\mathbf{Z})\), and in which \(\Sigma\) sits such that it comes within distance \(\epsilon\) from every point of \(X\) and that distances in \(\Sigma\) are almost the same as distances in \(X\). This implies that maps \(f\colon\Sigma\to S^n\) extend to maps \(g\colon X\to S^n\) with only slightly larger Lipschitz constant. Thus \(L_{\not=0}(\Sigma)\) is approximately the infimum of \(\operatorname{Lip}(\alpha)\) over all homotopy classes \(\alpha\) of non-zero degree maps from \(X\) to \(S^n\). On the other hand, the authors show that \(\operatorname{Lip}(\alpha)\) can be estimated above and below in terms of the comass of \(\alpha^*\left[S^n\right]\in H^n(X;\mathbf{Z})\). But from Dinur's hardness of approximation result for shortest vectors in the lattice \(\Gamma\), the authors can conclude that it is NP-hard to estimate the comass within \(N^{\frac{c}{\log\log N}}\). This shows the hardness of approximation for \(L_{\not=0}(\Sigma)\), a similar argument works for \(L_1(\Sigma)\). The almost-isometric embedding of \(\Sigma\) in \(X\) is done by different constructions for surfaces and higher-dimensional spheres, the second case being more complicated and occupying almost six pages. In an appendix, the authors show that \(L_{\not=0}(\Sigma)\) and \(L_1(\Sigma)\) can be approximated up to a constant factor by an NP algorithm.