An asymptotically tight bound on the number of connected components of realizable sign conditions
An asymptotically tight bound on the number of connected components of realizable sign conditions
复制标题
可实现符号条件的连通分量数量的渐近紧界
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Marie
中科院分区：
文献类型：
--
作者：
S. Basu;R. Pollack;Marie
本文证明了实多项式族的所有可实现符号条件的连通分支个数的渐近紧界(关于固定次数多项式的个数和变量个数的渐近)。更确切地说，我们证明了一族S多项式的所有可实现符号条件在R[X1，.。。，xk]，其次数至多为d，由(2d)k k！S+O(SK−1)。这改进了之前已知的最佳上界，即12(8d)kk！S+O(SK−1)。新的下界与得到的多项式族的下界渐近匹配，每个多项式族都是一次多项式的乘积。
In this paper we prove an asymptotically tight bound (asymptotic with respect to the number of polynomials for fixed degrees and number of variables) on the number of connected components of the realizations of all realizable sign conditions of a family of real polynomials. More precisely, we prove that the number of connected components of the realizations of all realizable sign conditions of a family of s polynomials in R[X1, . . . , Xk] whose degrees are at most d, is bounded by (2d)k k! s + O(sk−1). This improves the best upper bound known previously, which was 1 2 (8d)k k! s + O(sk−1). The new bound matches asymptotically the lower bound obtained for families of polynomials each of which is a product of generic polynomials of degree one.