Complexity of computing the local dimension of a semialgebraic set (Q1300630)

The author exhibits some new and some improved complexity bounds for the task of computing the global dimension \(\dim(V)\) of a semialgebraic set \(V\) given by polynomial inequalities, the local dimension \(\dim_x(V)\) of \(V\) at a given point \(x\in V\) and the dimension of the Zariski tangent space \(T_x(V)\) of \(V\) at \(x\). The paper starts with a description of the author's strictly personal view of the recent advances in the field: complexity theory in algorithmic algebraic and semialgebraic geometry (where the author's own contributions are seminal). Let \(V\subset{\mathbb R}^n\) be a semialgebraic set defined by \(K\) inequalities of \(n\)-variate polynomials with integer coefficients. Suppose that the degrees and logarithmic heights of these polynomials are bounded positive integers \(d\) and \(M\) respectively. Then \(\dim(V)\) can be determined using \(M^{O(1)}(Kd)^{O(\dim(V)\text{codim}(V))}=M^{O(1)}(Kd)^{O(n^2)}\) bit operations. In case that \(V\) is defined only by equations this bound can be improved to \(M^{O(1)}Kd^{O(\dim(V)\text{codim}(V))}=M^{O(1)}Kd^{O(n^2)}\) bit operations. Moreover, in this case, it is possible to find using \(M^{O(1)}Kd^{O(n^2)}\) bit operations a quantifier free formula in the language of ordered fields which defines the singular locus of the real variety \(V\). This formula contains \(d^{O(n^2)}\) polynomials of degree \(d^{O(n)}\) and logarithmic height \((log(K) M)^{O(1)}d^{O(n)}\) (theorems 3.1 and 5.1). Let \(x\in V\) be a point with real algebraic coordinates which is definable by a quantifier free formula involving \(n\) univariate polynomials of degree and logarithmic height at most \(d_1\) and \(M_1\), respectively. Suppose that \(V\) is a real variety definable by equations only. Then the dimension of the Zariski tangent space \(T_x(V)\) of \(V\) at \(x\) can be determined using \(M_1^{O(1)}M^{O(1)}Kd_1^{O(1)}d^{O(n)}\) bit operations (theorem 4.1). Suppose that \(V\) is a semialgebraic set and that the system of polynomial inequalities describes a smooth (e.g. Whitney) stratification of \(V\). With respect to this stratification the point \(x\) has a well defined depth \(0\leq\ell\leq \dim_x(V)\). Then it is possible to determine the local dimension \(\dim_x(V)\) of \(V\) at \(x\) using \(M_1^{O(1)}M^{O(1)}d_1^{O(\ell)}(K(\ell+1)d)^{O(\ell^2n)}\) bit operations. In case that \(V\) is defined only by equations, this bound can be improved to \(M_1^{O(1)}M^{O(1)}d_1^{O(\ell)}Kd^{O(\ell^2n)}\) bit operations.