Non-Uniform Root of Polynomial in Open Cube - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T22:07:16Z http://mathoverflow.net/feeds/question/102544 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102544/non-uniform-root-of-polynomial-in-open-cube Non-Uniform Root of Polynomial in Open Cube Derrick Stolee 2012-07-18T13:52:43Z 2012-07-18T17:44:47Z <p>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 &lt; 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?</p> <p>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}$.</p> http://mathoverflow.net/questions/102544/non-uniform-root-of-polynomial-in-open-cube/102551#102551 Answer by Will Sawin for Non-Uniform Root of Polynomial in Open Cube Will Sawin 2012-07-18T15:16:37Z 2012-07-18T15:16:37Z <p>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.</p> http://mathoverflow.net/questions/102544/non-uniform-root-of-polynomial-in-open-cube/102567#102567 Answer by Robert Israel for Non-Uniform Root of Polynomial in Open Cube Robert Israel 2012-07-18T17:44:47Z 2012-07-18T17:44:47Z <p>If you can find points $u, v \in [0,1]^n$ where $p(u) &lt; 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$.</p>