# 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 univariate polynomial with rational coefficients, where ring f is not necessarily univariate
• a, , (optional) the lower bound of the interval
• a, , (optional) the lower bound of the interval
• b, , (optional) the upper bound of the interval
• b, , (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

## Ways to use BudanFourierBound :

• "BudanFourierBound(RingElement)"
• "BudanFourierBound(RingElement,InfiniteNumber,InfiniteNumber)"
• "BudanFourierBound(RingElement,InfiniteNumber,QQ)"
• "BudanFourierBound(RingElement,InfiniteNumber,RR)"
• "BudanFourierBound(RingElement,InfiniteNumber,ZZ)"
• "BudanFourierBound(RingElement,QQ,InfiniteNumber)"
• "BudanFourierBound(RingElement,QQ,QQ)"
• "BudanFourierBound(RingElement,QQ,RR)"
• "BudanFourierBound(RingElement,QQ,ZZ)"
• "BudanFourierBound(RingElement,RR,InfiniteNumber)"
• "BudanFourierBound(RingElement,RR,QQ)"
• "BudanFourierBound(RingElement,RR,RR)"
• "BudanFourierBound(RingElement,RR,ZZ)"
• "BudanFourierBound(RingElement,ZZ,InfiniteNumber)"
• "BudanFourierBound(RingElement,ZZ,QQ)"
• "BudanFourierBound(RingElement,ZZ,RR)"
• "BudanFourierBound(RingElement,ZZ,ZZ)"

## For the programmer

The object BudanFourierBound is .