2
$\begingroup$

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)?

2 Answers 2

1

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.

0

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.