Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
depends on $f$; e.g., if $f(x)=x^d$ then the shortest distance is zero. –  Luis H Gallardo Feb 19 '11 at 18:55
    
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 ? –  Luis H Gallardo Feb 23 '11 at 0:54
add comment

3 Answers

up vote 7 down vote accepted

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

share|improve this answer
    
The results similar to the mentioned conjecture of Collins were obtained recently in the following papers: worldscinet.com/ijnt/06/0603/S1793042110003083.html blms.oxfordjournals.org/content/43/6/1239 –  duje Feb 19 '12 at 20:48
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.