3
$\begingroup$

Suppose $f$ is uni-variate degree d polynomial have integer coefficient.

What will be shortest distance between any two real root of polynomial.

Can we compute this exact if not then upper and lower bound for the same.

Correction :Here I am assuming all roots are distinct

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ depends on $f$; e.g., if $f(x)=x^d$ then the shortest distance is zero. $\endgroup$
    – Luis H Gallardo
    Commented Feb 19, 2011 at 18:55
  • $\begingroup$ Since the OP asks for distance between real roots we require that the polynomial has real roots (so forbidden say $f(x)=x^{2^d}+1$ etc. ). Assume then that the polynomial $f(x)$ has at least $2$ real roots : The bounds in the literature may be better or worst under the reality condition ? $\endgroup$
    – Luis H Gallardo
    Commented Feb 23, 2011 at 0:54
  • $\begingroup$ Using [iteration][1] we can using additionaly Newton's method approximate the non zero real roots of the polynomial.A bound can be found for the smallest root in the link. [1]: math.stackexchange.com/questions/4738155/… $\endgroup$
    – DesmosTutu
    Commented Nov 25, 2023 at 15:19

3 Answers 3

Reset to default
8
$\begingroup$

There is considerable literature on this question, much of which can be revealed by doing a google search on "root separation". In particular, Wolfram MathWorld's "root separation" article is brief but to the point, and also see:

Polynomial Minimum Root Separation George E. Collins Department of Computer and Information Sciences, University of Delaware, Newark, DE 19716, U.S.A. Received 21 June 2001; accepted 7 July 2001. Available online 28 February 2002. Abstract There is a well-known lower bound, due to Mignotte, for the minimum root separation of a squarefree integral polynomial, but no evidence for the sharpness of this bound. This paper provides massive computational evidence for a conjectured much larger bound, one that is approximately the square root of Mignotte’s bound. References

(this is journal of symbolic computation).

Improve this answer
$\endgroup$
2
8
$\begingroup$

As you've seen from the examples that others have given, you need to know something about the degree and size of coefficients. Suppose that $f$ has distinct roots, degree $n$ and integer coefficients of absolute value at most $H$. So the roots have absolute value at most $nH$, so $2nH$ is an upper bound for the distance between two roots. To get a lower bound, use that the discriminant is at least one and the previous bounds, to get the lower bound $(2nH)^{-n(n-1)}$. I am sure this can be improved.

Improve this answer
$\endgroup$
5
$\begingroup$

Consider the polynomial $n\cdot m\cdot (x-1/n)(x-1/m).$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .