A hardness of approximation result in metric geometry. (English) Zbl 1462.53040

Brady, Zarathustra; Guth, Larry; Manin, Fedor

Sel. Math., New Ser. 26, No. 4, Paper No. 54, 20 p. (2020).

Recent work of 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\), 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 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.

Reviewer: Thilo Kuessner (Augsburg)

MSC:

53C23	Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces
57Q15	Triangulating manifolds
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

hardness of approximation; hyperspherical radius; Lipschitz constants; simplicial comass norm

Citations:

Zbl 1402.53035; Zbl 1101.53021; Zbl 1016.68041

References:

[1]	Berdnikov, A., Manin, F.: Scalable spaces. arXiv:1912.00590 (2019)
[2]	Berdnikov, A.: Lipschitz null-homotopy of mappings \(S^3 \rightarrow S^2\). arXiv:1811.02606 (2018)
[3]	Chambers, GR; Dotterrer, D.; Manin, F.; Weinberger, S., Quantitative null-cobordism, J. Am. Math. Soc., 31, 4, 1165-1203 (2018) · Zbl 1402.53035
[4]	Chambers, GR; Manin, F.; Weinberger, S., Quantitative nullhomotopy and rational homotopy type, Geom. Funct. Anal. (GAFA), 28, 3, 563-588 (2018) · Zbl 1408.57023
[5]	Dinur, I., Approximating \({\rm SVP}_{\infty }\) to within almost-polynomial factors is NP-hard, Theor. Comput. Sci., 285, 1, 55-71 (2002) · Zbl 1016.68041
[6]	Dranishnikov, AN; Ferry, SC; Weinberger, S., Large Riemannian manifolds which are flexible, Ann. Math. (2), 157, 3, 919-938 (2003) · Zbl 1051.53035
[7]	Dyer, R.; Vegter, G.; Wintraecken, M., Riemannian simplices and triangulations, Geom. Dedicata, 179, 91-138 (2015) · Zbl 1333.57036
[8]	Edelsbrunner, H.; Grayson, DR, Edgewise subdivision of a simplex, Discrete Comput. Geometry, 24, 4, 707-719 (2000) · Zbl 0968.51016
[9]	Ferry, S.; Okun, B., Approximating topological metrics by Riemannian metrics, Proc. Am. Math. Soc., 123, 6, 1865-1872 (1995) · Zbl 0828.53038
[10]	Filakovský, M.; Vokřínek, L., Are two given maps homotopic? An algorithmic viewpoint, Found. Comput. Math., 20, 2, 311-330 (2020) · Zbl 1436.55020
[11]	Gromov, M., Homotopical effects of dilatation, J. Differ. Geometry, 13, 3, 303-310 (1978) · Zbl 0427.58010
[12]	Gromov, M., Width and related invariants of Riemannian manifolds, Asterisque, 163-164, 6, 93-109 (1988) · Zbl 0684.53036
[13]	Gromov, M.; Lawson, HB Jr, Spin and scalar curvature in the presence of a fundamental group I, Ann. Math. (2), 111, 2, 209-230 (1980) · Zbl 0445.53025
[14]	Guth, L., Lipshitz maps from surfaces, Geom. Funct. Anal. (GAFA), 15, 5, 1052-1090 (2005) · Zbl 1101.53021
[15]	Guth, L., Minimax problems related to cup powers and Steenrod squares, Geomet. Funct. Anal. (GAFA), 18, 6, 1917-1987 (2009) · Zbl 1190.53038
[16]	Guth, L., Recent progress in quantitative topology, Surv. Differ. Geometry, 22, 191-216 (2017) · Zbl 1426.55013
[17]	Kolmogorov, AN; Barzdin, YM, On the realization of nets in 3-dimensional space, Probl. Cybern., 8, 261-268, 259-260 (1967)
[18]	Manin, F., Plato’s cave and differential forms, Geometry Topol., 23, 6, 3141-3202 (2019) · Zbl 1429.53058
[19]	Weinberger, S.: Computers, Rigidity, and Moduli, M. B. Porter Lectures. Princeton University Press, Princeton, NJ (2005)