# Polynomial whose roots are very nearly integers

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.

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

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.

-
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? –  Antonio Vargas Jan 7 at 16:50
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_-$. –  LutzL Jan 7 at 17:18
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. –  LutzL Jan 7 at 17:27

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.

-
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 –  user44197 Jan 7 at 5:49
What do you know about known bounds ? –  Ewan Delanoy Jan 7 at 5:51
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 –  user44197 Jan 7 at 5:56
Thank you for the reference, I’ll definitely look into it as it has been quoted in a totally different question. –  Ewan Delanoy Jan 7 at 6:06