On a generalization of Stickelberger's theorem (Q607067)

This paper is about computational aspects of the number of connected components of varieties defined over the complex numbers. Its main result is the following: Theorem. Let \(f_1,\dots, f_r\in k[X_1,\dots, X_n]\) of degree \(\leq d\) defining an algebraic variety \(V\subset{\mathbb A}^n(K)\) (with \(K\) an algebraically closed field containing \(k\)), one can compute \((p_1,g_1),\dots, (p_t,g_t)\) with \(p_j\in k[T]\) and \(g_j\in k[T, X_1,\dots, X_n]\), with the following properties: 1) The \(p_1,\dots, p_t\) are squarefree and pairwise coprime, 2) the family of sets \(Z(f_1,\dots,f_r,g_j(\tau)),\) with \(1\leq j\leq t\) and \(\tau\in K\) being a root of \(p_j\), runs exactly once through all connected components of \(V\). The algorithm has parallel (sequential) time complexity \((n\log d)^{{\mathcal O}(1)}\,\big(d^{{\mathcal O}(n^4}\big)\). An analogous statement holds with respect to the irreducible instead of the connected components. Here, the terms ``irreducible'' and ``connected'' are taken with respect to the Zariski topology of \({\mathbb A}^n(K)\), and the model of computation is that of \textit{algebraic circuits} as in [\textit{J. von zur Gathen}, SIAM J. Comput. 13, 802--824 (1984; Zbl 0553.68032); \textit{P. Bürgisser} and \textit{F. Cucker}, Quaderni di Matematica 13, 73--151 (2004; Zbl 1076.68033)]. The ingredients to describe the components are two generalized versions of Stickelberger's theorem on the eigenvalues of certain linear transformations induced by multiplication in the residue classes of a zero-dimensional ideal (not to be confused with the number theory result of the same name, see for instance [\textit{F. Rouillier}, Appl. Algebra Eng. Commun. Comput. 9, No. 5, 433--461 (1999; Zbl 0932.12008)] for varieties of positive dimension. If \(V\) is a hypersurface and hence given by one polynomial \(f\), the irreducible decomposition of \(V\) corresponds to the absolutely irreducible factorization of \(f\), and the connected components are given by some coarser factorization. The algorithm applied to this case shows that one can compute both factorizations in parallel time \({\mathcal O}(n^2\log^2d)\) and sequential time \(d^{{\mathcal O}(n)}\).