Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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$.

share|improve this answer
    
Thanks! This solution was easy to implement and worked for my project. –  Derrick Stolee Jul 18 '12 at 20:40

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.

share|improve this answer
    
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$. –  Noam D. Elkies Jul 18 '12 at 15:47

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.