2
$\begingroup$

Let $n\geq 6$ be an integer ; consider the polynomial

$$ P_n=\big((x-1)(x-2)\ldots (x-n)\big)^2+(n+1) $$

Let $\varepsilon=\frac{n^4}{173\big((\lfloor \frac{n}{2} \rfloor)!\big)^2}$. I have checked with a computer that up to $n=50$, the following holds : for every $k$ such that $1\leq k\leq \frac{n}{2}$, there is a root $z_k=x_k+iy_k$ of $P_n$ where $x_k$ and $y_k$ are real, and

$$ k-\varepsilon \leq x_k \leq k, \ 0 \leq y_k \leq \varepsilon \tag{1} $$

Notice the symmetry $P_n((n+1)-x)=P_n(x)$, so that the other roots of $P_n$ are the $(n+1)-z_k$. Thus if (1) holds, we can enumerate all the roots of $P$ as $z_1,\ldots ,z_{2n}$ with $|z_k-k|\leq \sqrt{2}\varepsilon$ for every $k$.

Does anyone know how to show (1) (or find a counterexample ?)

I was led to this by working on this recent MSE question.

$\endgroup$
2
  • $\begingroup$ $$P_n(x)=\left[{x\choose n+1}\cdot\frac{(n+1)!}x\right]^2+(n+1)$$ $\endgroup$
    – Lucian
    Jan 7, 2014 at 6:14
  • 1
    $\begingroup$ @Lucian flashy rewriting, but not sure it’s helpful. $\endgroup$ Jan 7, 2014 at 6:30

2 Answers 2

2
$\begingroup$

The theory of the Durand-Kerner method provides bounds on roots, based on the Gershgorin circle theorem and more refined bounds based on more complicated methods.

If $z_1,\dots,z_n$ are distinct approximations of the roots, and

$$w_i=-\frac{p(z_i)}{\prod_{k\ne i}(z_k-z_i)},$$

then the roots can be found in the union of the disks $D(z_i+w_i,(n-1)|w_i|)\subset D(z_i,n|w_i|)$. See the literature cited in the wikipedia article for closer bounds and conditions on root disk separation.


Here for the reduced polynomials $p_\pm(z)=(z-1)...(z-n)\pm i\sqrt{n+1}$, $z_k=k$ and $p_\pm(z_k)=\pm i\sqrt{n+1}$, so that $P_n(z)=p_+(z)p_-(z)$, the Weierstrass increments for each factor $p_\pm(z)$ separately can be bounded by

$$|w_i|\le\frac{\sqrt{n+1}}{\lfloor\tfrac n2\rfloor!\,\lceil\tfrac n2\rceil!}$$

which results in a bound

$$|z_{\pm,k}^*-k|\le \frac{n\sqrt{n+1}}{\lfloor\tfrac n2\rfloor!\,\lceil\tfrac n2\rceil!}$$

for the roots $z_{\pm,k}^*$ of $P_n$ independent of the factor in which they occur. This bound is perhaps not as nice for small $n$ as the bound in the conjecture, but in a similar structure and should be better for large $n$ due to the smaller power in the numerator.


If one uses these root bounds, one gets for $n\ge6$ clearly separated roots of $p_\pm$, that is, the claim of the Gershgorin theorem (and earlier Weierstrass) of exactly one root per disk holds.

This is usually demonstrated with a homotopy argument for $p_\pm(t,z)=(z-1)...(z-n)\pm it\sqrt{n-1}$ in that for $t=0$, the integers are the exact roots, and for growing $t$ there is exactly one root path starting from each integer per the implicit function theorem. As long as the root bounding disks, that also grow with factor $t$, stay separate until $t=1$, no root path can change disks.

$\endgroup$
3
  • $\begingroup$ What is the resulting bound for the roots of $P_n$? Also, could you clarify your last statement? There are complex roots, so how does the fact that their paths don't cross imply that they won't leave a neighborhood of the real axis? $\endgroup$ Jan 7, 2014 at 16:50
  • $\begingroup$ By the binomial theorem $a^2-b^2=(a+b)(a-p)$, any root of $P_n$ is either a root of $p_+$ or of $p_-$, so the same bounds apply. I'll add something about the real roots. I think that any complex part is an artefact of the computation that can be avoided by just computing with $p_+$ and $p_-$. $\endgroup$ Jan 7, 2014 at 17:18
  • $\begingroup$ I'm sorry, partial blindness hits again. Your polynomial is square plus the positive $(n+1)$, so of course all solutions will have an imaginary part. $\endgroup$ Jan 7, 2014 at 17:27
1
$\begingroup$

That the roots have to have that structure is well known in the control community. Look up any graduate level discussion on "root locus". What you have is $$ P(x) = Q(x) + R $$ and $Q(x)$ has double real roots and for real $x$, $Q(x)\ge 0$ and $R>0$. Hence all roots have to be complex conjugate pairs.

How much the roots of $P$ drift from that of $Q$ is your question and that can be estimated by the perturbation results. I don't have the reference handy here.

$\endgroup$
4
  • $\begingroup$ I did some additional work. It is not hard to show the perturbation has to be small. But getting the bound you seek may be non-trivial $\endgroup$
    – user44197
    Jan 7, 2014 at 5:49
  • $\begingroup$ What do you know about known bounds ? $\endgroup$ Jan 7, 2014 at 5:51
  • $\begingroup$ To get bounds, you convert the polynomial roots to eigenvalues of a matrix. So if you write the matrices as $P=Q+\Delta$, then you want to bound the eigenvalues of $P$. These are the inclusion theorems. The "best" book that covers this very succinctly is "A Survey of Matrix Theory and Matrix Inequalities" (my go to book!) store.doverpublications.com/048667102x.html $\endgroup$
    – user44197
    Jan 7, 2014 at 5:56
  • $\begingroup$ Thank you for the reference, I’ll definitely look into it as it has been quoted in a totally different question. $\endgroup$ Jan 7, 2014 at 6:06

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.