Geodesic diameter of sets defined by few quadratic equations and inequalities (Q455654): Difference between revisions

From the authors' abstract and introduction: This work considers semialgebraic subsets \(X\) of the unit ball in \(\mathbb{R}^{n}\) given by \(k\) quadratic equalities or inequalities. The main result provides a bound of type \(n^{O(k)}\) (i.e. polynomial in \(n\)) for the geodesic diameter. (For semialgebraic sets of general degree the bound is known to be exponential in \(n\).) The proof borrows heavily from the idea of \textit{D. D'Acunto} and \textit{K. Kurdyka} [Bull. Lond. Math. Soc. 38, No. 6, 951--965 (2006; Zbl 1106.14046)] which consists in controlling the geodesic diameter by the length of trajectories of the gradient of a Morse function, which in turn are uniformly bounded by the length of the \textit{talweg} of this function. The main difficulty is to show that this talweg can be assumed of dimension \(1\), so that its length can be estimated via the Cauchy-Crofton formula, by counting intersection points with a hyperplane. This eventually leads to a system of equations containing a big (of size \(n\)) linear system in \(x\). This linearity comes from the fact that the gradients of quadratic functions are linear. A method introduced by \textit{A. I. Barvinok} [Math. Z. 225, No. 2, 231--244 (1997; Zbl 0919.14034)] is hereby adapted to solve the linear system in \(x\) (as function of the parameters and a few free variables among \(x\)) and carry this solution in the other equations. An additional difficulty appears from the nonlinear dependence on the parameters of the matrix of the system. The co-rank of the linear system, that is, the number of free variables, is eventually shown to remain small, controlled by \(k\), when the parameters vary, which gives a bound polynomial in \(n\) of degree \(O(k)\) on the number of solutions of the complete system.