Non-Uniform Root of Polynomial in Open Cube - MathOverflow

Non-Uniform Root of Polynomial in Open Cube

2012-07-18T13:52:43Z

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

Answer by Will Sawin for Non-Uniform Root of Polynomial in Open Cube

2012-07-18T15:16:37Z

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.

Answer by Robert Israel for Non-Uniform Root of Polynomial in Open Cube

2012-07-18T17:44:47Z

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