BudanFourierBound(RingElement,Number,Number)

Synopsis

• Function: BudanFourierBound

• Usage:

  BudanFourierBound(f, a, b)

• Inputs:
  • a ring element, f, a univariate polynomial
  • a number, a, a lower bound of the interval
  • a number, b, an upper bound of the interval
• Outputs:
  • an integer, a sharp upper bound for the number of real roots of a univariate polynomialf in the interval (a,b)

Description

This computes a sharp upper bound for the number of real roots of a univariate polynomial f from a to b. If interval is not specified, it computes a bound for the real roots of the function from negative infinity to infinity.

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-4)*(t-1)^2*(t+1)*(t+3)*(t+5)*(t-6)

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

o4 : R

i5 : a = -6

o5 = -6

i6 : BudanFourierBound(g,a,infinity)

o6 = 7

i7 : BudanFourierBound(g,-1,5)

o7 = 3