Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a system of multivariate polynomial equations

$\vec{x}= f(\vec{x})$ with integer coefficients, $f$ is at most of degree 2.

Suppose $\vec{x}_1$ and $\vec{x}_2$ are two real roots of $f$, is there any bound on

$||\vec{x}_1-\vec{x}_2||$ (in terms of $\infty$-norm or $1$-norm)?

share|improve this question

2 Answers 2

I'm not sure if "$\infty$-norm or $1$-norm" refer to the vector $\vec{x}_1-\vec{x}_2$ or to the coefficients of polynomials. Anyway, to narrow down the possibilities I give an example where all coefficients are small but the distance between roots is large:

$$x_1^2-2x_1=0,\qquad x_{k+1}-x_{k}^2=0\quad \text{for } k=1,\dots,n-1$$

One root is $(0,0,\dots,0)$, the other is $(2,4,8,\dots, 2^n)$. So the maximum of coefficients is not enough to bound the distance.

share|improve this answer

Suppose that we have a system of $m$ polynomial equations of degree at most $d = 2$ in $x \in \mathbb{R}^n$

$$\begin{array}{rll} f_1 (x) &:= x^T Q_1 x + r_1^T x + s_1 &= 0\\ f_2 (x) &:= x^T Q_2 x + r_2^T x + s_2 &= 0\\ & \vdots & \\ f_m (x) &:= x^T Q_m x + r_m^T x + s_m &= 0\\ \end{array}$$

where $Q_i \in \mathbb{R}^{n \times n}$, $r_i \in \mathbb{R}^{n}$, and $s_i \in \mathbb{R}$. If $x_i, x_2 \in \mathbb{R}^n$ are solutions of the polynomial system of equations, then we have a total of $2 m$ quadratic equality constraints

$$\begin{array}{c}\displaystyle\bigwedge_{i=1}^m \left( x_1^T Q_i x_1 + r_i^T x_1 + s_i = 0 \right)\\ \displaystyle\bigwedge_{i=1}^m \left( x_2^T Q_i x_2 + r_i^T x_2 + s_i = 0 \right)\end{array}$$

and we would like to maximize $\|x_1-x_2\|$ in order to find an upper bound on the distance between any two solutions of the polynomial system. Maximizing $\|x_1-x_2\|_1$ or $\|x_1-x_2\|_{\infty}$ is not trivial, so one could maximize $\|x_1-x_2\|_2$ instead, as follows

$$\begin{array}{ll} \displaystyle\text{maximize} & \|x-x_2\|_2^2\\ \text{subject to} & \begin{array}{c}\displaystyle\bigwedge_{i=1}^m \left( x_1^T Q_i x_1 + r_i^T x_1 + s_i = 0 \right)\\ \displaystyle\bigwedge_{i=1}^m \left( x_2^T Q_i x_2 + r_i^T x_2 + s_i = 0 \right)\end{array}\end{array}$$

which is a quadratically-constrained quadratic program (QCQP). One could also use Lagrange multipliers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.