Bounds on Distance to Variety in Terms of Coefficients of Bivariate Polynomials

Theorem 1. For a point $\mathbf{p} \in \mathbb{C}^2$ that is not a zero of f $$\max_{i=0,\dots,k} \left| \frac{f_{i,k-i}(\mathbf{p})}{f(\mathbf{p})} \right|^{1/k} < \frac{2D}{\operatorname{sep}(\mathbf{p}, V(f))}.$$ (14) The bound above can also be interpreted as an upper bound on the separation of a point $\mathbf{p}$ from the variety V(f) in terms of the coefficients of the polynomial. Can a converse bound be given, i.e., a lower bound on the separation in terms of the coefficients. We next derive such a bound. Suppose $f(0) \neq 0$ , then we want to derive a lower bound on sep(0, V(f)) in terms of the coefficients. Clearly, any $\mathbf{x} = (x, y)$ for which $$|a_{0,0}| > \sum_{k>1} \sum_{i=0}^{k} |a_{i,k-i}| |x|^{i} |y|^{k-i}$$ (15) cannot be on the variety of f. Define $$\gamma := \max_{1 \le k \le D} \max_{0 \le i \le k} \left( \frac{k!}{\binom{k}{i}} \left| \frac{a_{i,k-i}}{a_0} \right| \right)^{1/k},$$ where D is the total degree. Then it follows that (15) is equivalent to $$1 > \sum_{k > 1} \frac{\gamma}{k!} \sum_{i=0}^{k} {k \choose i} |x|^{i} |y|^{k-i} = \sum_{k > 1} \frac{\gamma}{k!} (|x| + |y|)^{k} > \exp(\gamma ||\mathbf{x}||_{1}) - 1.$$ Therefore, if $\mathbf{x}$ is such that $\|\mathbf{x}\|_{1}\gamma < \ln 2$ then $|f(\mathbf{x})| > 0$ . In general, for any point $\mathbf{p} \in \mathbb{C}^{2}$ we can apply the argument above to the shifted polynomial to obtain the following: if $$\gamma_f(\mathbf{p}) := \max_{1 \le k \le D} \max_{0 \le i \le k} \left| \frac{f_{i,k-i}(\mathbf{p})}{f(\mathbf{p})} \right|^{1/k}, \tag{16}$$ then $$sep(\mathbf{p}, V(f)) \ge \frac{\ln 2}{\sqrt{2}\gamma(\mathbf{p})} \ge \frac{1}{3\gamma(\mathbf{p})}.$$ (17) Besides their intrinsic interest, such bounds are useful in analyzing the complexity of certain algorithms. For instance, the bound given in (3) has been useful in bounding the running time of certain root isolation algorithms using the continuous amortization framework [Bur16, SB15]. We expect the generalization given above to be useful in deriving similar bounds on the running time of generalizations of corresponding algorithms that generally use subdivision (e.g., [PV04]). Acknowledgement: The author is grateful to Chee Yap and Bernard Mourrain for their feedback on earlier drafts of the results presented here.