Bounds for polynomials on algebraic numbers and application to curve topology (Q2118214): Difference between revisions

A polynomial in \(\mathbb{Z}[X,Y]\) or \(\mathbb Z[X]\) is said to be of magnitude bounded by \((d,\tau)\) if its total degree is less than or equal to \(d\) and its coefficients are of bitsize less than \(\tau\) (i.e. their absolute values are \(<2^\tau\) ). Write \(\tilde O(f(d,\tau))\) (used for estimating e.g. complexities) as as an abbreviation for that there exists positive constant \(c\) such that \( O((\log d \log \tau)^c f(d,\tau)).\) Let now \(P\in \mathbb{Z}[X,Y]\) be a square-free polynomial of magnitude bounded by \((d,\tau)\) describing a real algebraic curve \(V_{\mathbb R}(P)=\{(x,y)\in \mathbb R^2: P(x,y)=0\}.\) A new, fast, algorithm of bit complexity \(\tilde O(d^5\tau+d^6)\) is presented for determining the topology of \(V_{\mathbb R}(P)\) via an output which is a straight line planar graph \(\mathcal G.\) Essential features of the algorithm are i. its complexity matches that of the best other algorithms known for the task; ii. no coordinate changes are done avoiding this way for example a loss of sparsity and iii. the graph \(\mathcal G\) contains essential information for the cylindrical algebraic decomposition of the algebraic curve. Perhaps equally important are many new results for the complexity of algorithms that compute root isolation, root multiplicities, determination of common roots of various polynomials; in particular a new efficient algorithm for solving bivariate systems of form \( R(X)=0, F(X,Y)=0 \) is presented. The work has four sections. Sections 2, 3 give complexities of algorithms computing quantities associated to univariate and bivariate polynomials as well as bitsizes of their outputs. Section 4 explains how to obtain the topology of \(V_{\mathbb R}(P)\) within the announced complexity bounds. As a general source for many of the concepts used see [\textit{S. Basu} et al., Algorithms in real algebraic geometry. 2nd ed. Berlin: Springer (2006; Zbl 1102.14041)]. Section 2 titled Univariate Results is divided into three subsections. Subsection 2.1 presents quantitative results for the geometry of the roots associated to polynomials in \(\mathbb C[X]\) and \(\mathbb Z[X].\) The results are expressed in terms of the length, the norm, the Mahler measure (Mea) of \(f\) (see Basu et. al. [loc. cit]) and logarithmic quantities associated to these numbers; but also using the concept of the separation of \(f\) at a root \(x\) given by \(\mbox{Sep}(x,f)=\min_{y\in V_{\mathbb C}(f)\setminus\{x\}} |y-x|, \) and an apparently new concept which authors call the generalized discriminant. It plays a key role in the statement of several quantitative results and is defined as follows. Given \(f\in \mathbb C[X]\) define \(f^{[i]}:= f^{(i)}/i! .\) Then if \(f\in \mathbb Z[X],\) say, so will be any \(f^{[i]}\) and we may consider the polynomial \(h(X,U)= \sum_{k=1}^n U^{k-1} f^{[k]}.\) Then the resultant of \(f\) and \(h\) with respect to \(X,\) \(g(U):=\text{Res}_X(f,h(X,U)) \) is a polynomial in \(U\) with coefficients in \(\mathbb Z.\) By definition the generalized discriminant \(\text{GDisc}(f)\) is the coefficient of the nonzero term of lowest degree of \(g\) divided by the leading coefficient of \(f.\) One defines \(\text{lGDisc}(f)= \sum_{x\in V_{\mathbb C}(f)} \text{mul}(x,f)\cdot |\log|f^{[\text{mul}(x,f)]}(x) | |\) (which is essentially the logarithm of an expression for \(\text{GDisc}\) found earlier). Let \(\text{mul}(x,f)\) denote the multiplicity of a root \(x\in V_{\mathbb C}(f)\) and put \( \text{lSep}(f):= \sum_{x\in V_{\mathbb C}(f)} \text{mul}(x,f) |\log(\text{Sep}(x,f)|. \) With these definitions in place an interesting proof is given for that if \(f\in \mathbb C[X]\) has leading coefficient \(|\text{lc}(f)|\geq 1\) and degree \(n,\) then \(\text{lSep}(f) \in O(n(n+\text{lMea}(f))+\text{lGDisc}(f)).\) ( Here \(\text{lMea}(f)=\text{log(Mea}(f)).\)) Subection 2.2 gives quantitative results for polynomials in \(\mathbb Z[X].\) In particular it is deduced from the previous result that \(\text{lSep}(f) \in \tilde O(n\tau+n^2).\) This was known earlier by \textit{K. Mehlhorn} et al. [J. Symb. Comput. 66, 34--69 (2015; Zbl 1357.68305)] but has now a simpler proof. Then a number of further results concerning bitsizes or bitcomplexities of computing divisors, greatest common divisors, evaluation of polynomials on rationals are mentioned. At the beginning of subection 2.3 on root isolation technical definitions for the concepts of well isolating intervals of real roots and well isolating disks for compex roots of an \(f\in \mathbb C[X]\) are given guaranteeing that these are small compared with \(\text{Sep}(x,f).\) Some results from the just cited paper and other literature are recorded which give complexity results for computing for all \(x\in V_{\mathbb C}(f)\) the multiplicities \(\text{mul}(x,f)\) as well as well isolating disks \(\mathcal D_{r(x)}(m(x))\) of dyadic centers \(m(x)\) and radii \(r(x)\) and also estimates for the bitsizes of computing all \(m(x)\) and \(r(x).\) As a new result the authors present Proposition 2.24 which is important for one of their main results: Let a family of polynomials \(f,g_1, . . ., g_m\in \mathbb Z[X]\) of respective magnitudes bounded by \((d,\tau),(d_1,\tau_1), . . ., (d_m, \tau_m)\) be given and assume the sum of these pairs bounded by \((N,\Lambda).\) Then no more than \(\tilde O(N^2\Lambda+ N^3)\) bitoperations are needed to isolate all the roots of all the mentioned polynomials; to identify possible common roots of each pair \((f,g_i)\) and, finally, to determine the sign of the \(g_i\) at the real zeroes of \(f.\) Section 3, titled Bivariate Results has three subsections. Consider pairs of polynomials \(R\in \mathbb Z[X], \) of magnitude bounded by \((N,\Lambda) \) and \(F\in \mathbb Z [X,Y]\) of magnitude bounded by \((n,\tau)\) and suppose \(V_{\mathbb C}(R,F)\) is finite. For \(x\in \mathbb C\) define \(\mu(x):=\text{mul}(x,R),\) \(n(x):=\deg_Y (F(x,Y))\) and \(\nu(y):= \text{mul}(y, F(x,Y)).\) Write \(F(X,Y)=f_0(X)+f_1(X)Y + \cdots + f_{n_y}(X) Y^{n_y}\in \mathbb C[X,Y].\) The algebraic variety \(V_{\mathbb C}(F)\) contains no vertical line iff the polynomials \(f_i(X)\) do not share a common nontrivial factor. In this case \(\text{Crit}_X(V_{\mathbb C}(F))=\{(x,y)\in \mathbb{C}^2: F(x,y)=\partial_Y F(x,y)=0 \}\) is called the set of \(X\)-critical points of \(F.\) Note that for any \(x,\) we have \(F(x,Y)=F_{n(x)}(x,Y),\) where \(F_\ell(x,Y)= \sum_{l=0}^{\ell} f_l(X)Y^l .\) Subsection 3.1 titled Amortized bounds for Bivariate systems, provides in Propositions 3.2 and 3.4 estimates for the quantities \(\sum_{x\in V_{\mathbb C}(R)} \mu(x) \text{lLen} (F(x,Y))\) and analogous ones obtained by replacing \(\text{lLen}\) by \(\text{lMae}\) \(\text{lGDisc}\) and \(\text{lSep}\) in terms of \(n, N,\tau,\Lambda.\) In subsection 3.2 degrees and the number of distinct roots in the fibers are determined. Propositions 3.5 and 3.7 estimate, respectively given \(x\) the quantity \(\sum_{y:(x,y)\in \text{Crit}_X(V_{\mathbb C}(F)) } (\text{mul }(y, F_{n(x)}(x,Y)-1)\) and given \(y\) the quantity \(\sum_{x:(x,y)\in \text{Crit}_X(V_{\mathbb C}(F)) } (\text{mul }(y, F_{n(x)}(x,Y)-1)\) in the cases that \(F\in \mathbb C[X,Y]\) and \(F\in \mathbb Z[X,Y]\) by \(\text{mul}(x, \text{Disc}_Y(F_{n(x)}) \) and \(\text{mul}(y, R_Y), \) respectively where \(R_Y\in \mathbb Z[Y]\) is of magnitude \((O(n^2), O(n\tau+n^2)).\) \(R_Y\) sometimes can be chosen to be \(\text{Res}_X(F,\partial_YF).\) This and several other lemmas are then used to determine the bit complexity of computing \(n(x)\) and \(k(x)=\deg(\gcd(F(x,Y), \partial_Y(F(x,Y)))\) for every root \(x\) of polynomial \(R.\) Subsection 3.3 is dedicated to present results on bivariate Root Isolation: the complexity of computing the roots of all polynomials \(F(x,Y)\) where \(x\) runs over all roots of \(R\) is given. The upshot is that there results the following theorem mentioned in the introduction of the paper. Theorem 1.2. With \(R, F, V_{\mathbb C}(R,F)\) as before, using a total number of bit operations bounded by \(\tilde O(N^2\Lambda+ N^3+n^5\tau+ n^6+ n\cdot \max(n^2,N)(N\tau + n\Lambda+Nn))\) one can compute:\\ a. for all complex roots \(x\) of \(R\) the degree of \(F(x,Y)\) as well as of \(\gcd(F(x,Y), \partial_Y F(x,Y)), \) \\ b. for all complex roots \(x\) of \(R\) isolating disks \(\mathcal D_{x,y}\subset \mathbb C\) for all complex roots \(y\) of all polynomials \(F(x,Y)\) and the corresponding multiplicities \(\text{mul}(y, F(x,Y)).\)\\ b' . for a given subset \(V' \) of \(V_{\mathbb C}(R,F)\) and positive integer \(L\) one can further refine all isolating disks to a size less than \(2^{-L}\) in an additional number of bit operations \(\tilde O(N^2\Lambda + N^3+ n\max(n^2,N)\cdot (N\tau+ n\Lambda+Nn)+L(N\mu + n^2\sum_{x\in \pi_X(V)}\mu_x ))\) where \(\mu_x= \max_{(x,y)\in V} \text{mul}(y,F(x,Y)), \) and \(\mu=\max_{x\in \pi_X(V)}\mu_x.\) \(\pi_X(V)\) is the projection onto the \(X\)-axis. Section 4 gives in its last part 4.6 a combinatorial description of the topology of the curve as a list of lists in the following form: Let \(Q(X,Y)\) be the polynomial born from \(P=P(X,Y)\) which describes the variety defined by \(P\) except perhaps existing vertical lines. Let \(\alpha_1<\alpha_2< . . . <\alpha_N\) be the \(X\)-coordinates of the points that are \(X\)-critical or for which \(\deg(Q(\alpha,Y))<\deg_Y(Q)\) (such \(\alpha\)s correspond to asymptotes of \(V_{\mathbb R}(Q)\)). For each \(i=1, . . ., N\) let \(\beta_{i,1}< \beta_{i,2}<\cdots <\beta_{i,m_i},\) be the real zeros of \(Q(\alpha_i, Y).\) Let \(m_i' \) be the number of roots of \(Q(x,Y)\) for \(x\in ]\alpha_i, \alpha_{i+1}[,\) with the understanding that \(m_0' \) corresponds to \(x\in ]-\infty,\alpha_1[\) and \(m_N' \) to \(x\in ]\alpha_N,\infty[.\) Let \(\text{Left}_{i,j}\) be the number of curve segments of \(V_{\mathbb R}(Q)\) ending in \((\alpha_i, \beta_{ij})\) that lie to the left of this point and define \(\text{Right}_{i,j}\) similarly. Also define \(\text{Left}_{i,0}\) as the number of curve segments coming from the left that have \(x=\alpha_i\) as asymptotes tending to \(-\infty\), and \(\text{Left}_{i,1+m_i}\) as the number of curve pieces that come from the left that have \(x=\alpha_i\) as asymptotes tending to \(+\infty.\) Define analogous quantities for curve pieces coming from the right. Then \(\tilde{\mathcal L}(Q)\) is a list of lists of the form \(\{m_0', L_1,m_1', L_2, . . . , L_N, m_N' \},\) where \(L_i =[m_i, [\text{Left}_{i,0}, \text{Right}_{i,0} ], [\text{Left}_{i,1}, \text{Right}_{i,1} ], . . . , [\text{Left}_{i,1+m_i}, \text{Right}_{i,1+m_i} ] ].\) The list \(\tilde{\mathcal L}(Q)\) contains then sufficient information to construct in a simple manner the graph \(\mathcal G\) that is homeomorphic to \(V(Q).\) An extended example of this is shown. Finally it is still explained how to add rapidly the vertical lines that may make part of the real variety \(V_{\mathbb R}(P)\) and define modified lists \(\mathcal L(P).\) The subsections preceding 4.6 describe in detail how to find the quantities here referred and complexity estimates for this task. The lion's share of the explanations is taken up by dealing with singular points. For comparison, the potential reader can study in chapter 11 of Basu et. al. [loc. cit] another algorithm for finding the topology of an algebraic curve. The present article has some typos and copy-paste errors some of which are mathematically relevant but for the alert reader will be irrelevant.