BudanFourierBound -- a bound for the number of real roots of a univariate polynomial with rational coefficients

Synopsis

• Usage:

  BudanFourierBound(f, a, b)

  BudanFourierBound(f)

• Inputs:
  • f, a ring element, a univariate polynomial with rational coefficients, where ring f is not necessarily univariate
  • a, a real number, (optional) the lower bound of the interval
  • a, an infinite number, (optional) the lower bound of the interval
  • b, a real number, (optional) the upper bound of the interval
  • b, an infinite number, (optional) the upper bound of the interval
• Outputs:
  • an integer, the bound for the number of real roots of a rational univariate polynomial f in the interval (a,b]

Description

This computes the bound from the Budan Fourier Theorem for the number of real roots of a rational univariate polynomial f in the interval(a,b], counted with multiplicity. If the interval is not specified, it computes such bound on $(-\infty, \infty)$. Moreover, ring f is allowed to be multivariate.

i1 : R = QQ[t]

o1 = R

o1 : PolynomialRing

i2 : f = 45 - 39*t - 34*t^2 + 38*t^3 - 11*t^4 + t^5

      5      4      3      2
o2 = t  - 11t  + 38t  - 34t  - 39t + 45

o2 : R

i3 : BudanFourierBound(f)

o3 = 5

i4 : g = (t + 5)*(t + 3)*(t + 1)*(t - 1)^2*(t - 4)*(t - 6)

      7     6      5      4       3       2
o4 = t  - 3t  - 40t  + 86t  + 357t  - 443t  - 318t + 360

o4 : R

i5 : BudanFourierBound(g,-6,infinity)

o5 = 7

i6 : BudanFourierBound(g,-1,5)

o6 = 3

We also provide examples when the interval includes $-\infty$ or $\infty$.

i7 : BudanFourierBound(g,-infinity,0)

o7 = 3

i8 : BudanFourierBound(g,3,infinity)

o8 = 2

i9 : BudanFourierBound(g,-infinity,infinity)

o9 = 7