1
$\begingroup$

I'm looking to find a root $(x_1,\dots,x_n)$ of a polynomial $p \in {\mathbb R}[x_1,\dots,x_n]$ such that $0 \leq x_i < 1$ for all $i$. Further, I know in advance that setting $x_1 = \cdots = x_n$ is a root of $p$, but wish to avoid this root. How can I find at least one of these roots, preferably using a computer?

In more detail, $p$ is formed by taking two homogeneous polynomials $q_1, q_2$ (of degrees $d_1$ and $d_2$) where every coefficient is either zero or one, letting $D$ be the least common multiple of $d_1$ and $d_2$, and setting $p = q_1^{D/d_1} - q_2^{D/d_2}$. This is encoding the simultaneous solution to the equations $$q_1(x) = y^{d_1}, \quad q_2(x) = y^{d_2}$$ over $(x_1,\dots,x_n, y) \in [0,1)^{n+1}$.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

If you can find points $u, v \in [0,1]^n$ where $p(u) < 0$ and $p(v) > 0$, there will be a solution of the form $tu + (1-t) v$ for some $t \in [0,1]$, and that can be found by solving a polynomial in one variable. If $n > 2$, generically the line $tu+(1-t)v$ will not intersect the diagonal. With a bit of luck, you might find $u$ and $v$ by random search and/or local optimization. Of course, this won't work if $p$ is always $\ge 0$ or always $\le 0$.

$\endgroup$
1
  • $\begingroup$ Thanks! This solution was easy to implement and worked for my project. $\endgroup$ Jul 18, 2012 at 20:40
1
$\begingroup$

You want to look at the derivative of the polynomial at the root you know. If this is nonzero in one coordinate, say $x_1$, then locally the polynomial forms a surface. If the original root is $(x,...,x)$ then the equation $p(x_1,...,x_n)=0$, $x_2=x+\epsilon$, $x_3=x$, $x_4=x$, ... $x_n=x$ will have a root for sufficiently small $\epsilon$. So take a small $\epsilon$ and look for a root of that.

$\endgroup$
1
  • $\begingroup$ True, though there are natural examples where none of the partial derivatives vanish, such as $n=3$ and $p(x) = x_1^2+x_2^2+x_3^2 - (x_2 x_3 + x_3 x_1 + x_1 x_2)$, or more generally $\sum_{1\leq i < j \leq n} (x_i-x_j)^2$. $\endgroup$ Jul 18, 2012 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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