论文标题
概括Davenport-Mahler-Mignotte绑定 - 加权案例
Generalizing The Davenport-Mahler-Mignotte Bound -- The Weighted Case
论文作者
论文摘要
根部分离范围在理解计算代数（例如根隔离算法）中的各种算法的行为方面起着重要的作用。单变量设置的经典结果是Davenport-Mahler-Mignotte（DMM）绑定。陈述界限的一种方法是考虑一个定向的无环图$（v，e）$，在\ Mathbb {c} [c} [z} [z] $中的根源的子集中，其中边缘从较小的绝对价值到较大的绝对值中的一个较小的绝对价值来指向所有较大的绝对值，以及所有degrees of degrees of degrees。然后，DMM结合是以下产品上的摊销下限：$ \ prod _ {（α，β）\在e} |α-β| $中。但是，下边界涉及多项式$ f $的判别，如果多项式不是平方的，则会变得微不足道。 Eigenwillig（2008）通过使用合适的亚歧义代替判别物来解决这一问题。 Escorcielo-Perrucci，2016年，通过使用有限差异理论，进一步删除了图表上的限制。 Emiris等人，2019年已经概括了其结果，以处理产品中$ |α-β| $的指数最多是任何一个根的多样性。在本文中，我们通过在图表的边缘上允许任意正整数的重量来概括这些结果，即，对于权重函数$ W：这样的产物发生在一些最新的根聚类算法的复杂性估计中（例如，Becker等，2016），其中权重通常是根的多样性的一定函数。由于其摊销的性质，我们的界限可以说是通过操纵现有结果以适应权重来获得的界限。
Root separation bounds play an important role as a complexity measure in understanding the behaviour of various algorithms in computational algebra, e.g., root isolation algorithms. A classic result in the univariate setting is the Davenport-Mahler-Mignotte (DMM) bound. One way to state the bound is to consider a directed acyclic graph $(V,E)$ on a subset of roots of a degree $d$ polynomial $f(z) \in \mathbb{C}[z]$, where the edges point from a root of smaller absolute value to one of larger absolute, and the in-degrees of all vertices is at most one. Then the DMM bound is an amortized lower bound on the following product: $\prod_{(α,β) \in E}|α-β|$. However, the lower bound involves the discriminant of the polynomial $f$, and becomes trivial if the polynomial is not square-free. This was resolved by Eigenwillig, (2008), by using a suitable subdiscriminant instead of the discriminant. Escorcielo-Perrucci, 2016, further dropped the in-degree constraint on the graph by using the theory of finite differences. Emiris et al., 2019, have generalized their result to handle the case where the exponent of the term $|α-β|$ in the product is at most the multiplicity of either of the roots. In this paper, we generalize these results by allowing arbitrary positive integer weights on the edges of the graph, i.e., for a weight function $w: E \rightarrow \mathbb{Z}_{>0}$, we derive an amortized lower bound on $\prod_{(α,β) \in E}|α-β|^{w(α,β)}$. Such a product occurs in the complexity estimates of some recent algorithms for root clustering (e.g., Becker et al., 2016), where the weights are usually some function of the multiplicity of the roots. Because of its amortized nature, our bound is arguably better than the bounds obtained by manipulating existing results to accommodate the weights.
