From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Exposition of Budan's theorem ?
Date: 14 Dec 1997 10:28:53 GMT

In article <rbloomEL4BwH.49B@netcom.com>, Ron Bloom <rbloom@netcom.com> wrote:
>
>Can anyone find a concise exposition of Budan's theorem?
>In an old algebra text, dating from the 1930s, I find a 
>two and a half page argument, by the middle of which I 
>am about to doze off.

If this is the same as the "theorem of Budan-Fourier", try
M. Mignotte, Mathematics for Computer Algebra, Springer-Verlag
1992, p. 196.

Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Z2
==============================================================================
[Some MathSciNet matches for  (Budan and fourier) : --djr]

   93c:65068 65H05
   Huang, Nan Yang
   A generalization of the Budan-Fourier theorem and its application in
   solving equations. (Chinese. English summary)
   J. Numer. Methods Comput. Appl. 13 (1992), no. 1, 44--50.
   
   Summary: "In this paper, the changes of local values of a polynomial
   and its derivative functions are carefully studied and represented by
   a series of power functions. Based upon this, a generalization of the
   Budan-Fourier theorem is obtained, and a new method for solving
   equations, especially algebraic equations, is given."
     _________________________________________________________________
   
   92c:01043 01A70 (01A50 01A55 14-03 65-03)
   Borowczyk, Jacques(F-POIT)
   Sur la vie et l'\oe uvre de François Budan (1761--1840). (French.
   English, German summary) [On the life and works of Francois Budan
   (1761--1840)]
   Historia Math. 18 (1991), no. 2, 129--157.
   
   This paper is an account of the life and work of the French scientist
   Francois Budan (1761--1840). Budan was a mathematician who contributed
   also to law, medicine and poetry. The author presents the genealogy of
   Budan's aristocratic family and his biography. The main part of this
   paper is dedicated to the mathematical work of Budan. The author
   presents and discusses the ten mathematical publications of Budan. He
   emphasizes the algorithmic devices developed for the resolution of
   polynomial equations. There are many references to results of P.
   Ruffini, C. F. Sturm, J. Fourier, J.-L. Lagrange, F. N. W. Moigno and
   others. In this paper there are included two short algebraic papers of
   Budan, the list of his publications, many critical notes and a good
   bibliography.
   
   Reviewed by Doru Stefanescu
     _________________________________________________________________

   90g:41042 41A55 (41A15 65D32)
   Bojanov, B.(BG-SOFI); Huang, Da Ren(PRC-ZHJ)
   On the optimal quadrature formulas in $W\sp r\sb q$ of quasi-Hermitian
   type. 
   Approx. Theory Appl. 4 (1988), no. 4, 13--22.
   
   Quadrature formulas of quasi-Hermite type for the integral $\int\sp
   b\sb af(x)\, dx$ use multiple knots $a<x\sb 1<\cdots<x\sb n<b$, while
   the knots $x\sb 0=a$ and $x\sb {n+1}=b$ are of lacunary or Birkhoff
   type (the sequence of derivatives of $f$ used is not consecutive). If
   the formula is exact for polynomials of a certain degree we have---in
   turn---a Peano kernel. Minimizing the $L\sb p$-norm of this kernel
   with respect to a variation of weights and knots of the formula is the
   idea behind so-called optimal quadrature formulas.
   
   In this paper the authors extend their earlier work inasmuch as
   lacunary data at the endpoints are admitted; in particular the
   existence of $L\sb p$-optimal Peano kernels, $1\leq p<\infty$, is
   settled. The Budan-Fourier theorem used in the paper is proved using
   well-known techniques from Birkhoff interpolation theory. Concerning
   further background cf. chapter VIII of D. Braess' book Nonlinear
   approximation theory [Springer, Berlin, 1986; MR 88e:41002].
   
   Reviewed by K. Jetter
     _________________________________________________________________
   
   86k:41003 41A05 (26C10 42A15)
   Lorentz, G. G.(1-TX)
   Theorem of Budan-Fourier and Birkhoff interpolation. Studies in
   pure mathematics, 455--457,
   Birkhäuser, Basel-Boston, Mass., 1983.
   
   From the introduction: "We point out the close relation which exists
   between the theorem of Budan-Fourier and lacunary or Birkhoff
   interpolation---a subject to which P. Turan himself made important
   contributions. In this way we obtain a generalization of this theorem,
   which in its simplest form asserts that the number $Z\sb 0$ of zeros
   of a polynomial $P$ of degree $n$ in $(a,b)$ satisfies (1) $Z\sb 0\leq
   S\sp -\{P\sp {(k)}(a)\}-S\sp +\{P\sp {(k)}(b)\}.$ As usual, we denote
   by $S\sp -\{c\sb k\}\sp n\sb 0$ or $S\sp +\{c\sb k\}\sp n\sb 0$ the
   number of changes of sign in the sequence $c\sb k$, when zero terms
   are disregarded, or respectively assigned signs $±$ so as to maximize
   this number.
   
   "Let $f$ be an $n$ times continuously differentiable function on
   $[a,b]$. For $a<\alpha<b$, $\alpha$ is a zero of $f$ if and only if
   $f(\alpha)=0$, with usual multiplicity. On the other hand, $\alpha=a$
   is a zero of $f$ under the new definition, if either $f(a)=0$ or else
   $f(a)f\sp {(k)}(a)>0$, where $k$ is the smallest integer
   $k=1,\cdots,n$ with $f\sp {(k)}(a)\neq0$. Similarly, $b$ is a zero if
   $f(b)=0$ or if $f(b)(-1)\sp kf\sp {(k)}(b)>0$, with similarly defined
   $k$. We say that a matrix ${E}$ and the set of knots $X\:a=x\sb
   0<\cdots<x\sb m=b$ annihilate $f$, if for each pair $i$, $k$ with
   $e\sb {ik}=1$, $x\sb i$ is a zero of $f\sp {(k)}$ in the wide sense.
   
   "Theorem 1. If a conservative matrix ${E}$ and a set of knots
   $X\:a=x\sb 1<\cdots<x\sb m=b$ annihilate a polynomial $P$ of (exact)
   degree $n$, and if ${E}$ lists all zeros of $P$ in the wide sense at
   $a$ and $b$, then (2) $S\sp +\{(-1)\sp kP\sp {(k)}(a)\}+Z+S\sp +\{P\sp
   {(k)}(b)\}\leq n,$ where $Z$ is the number of zeros in $(a,b)$ of
   various derivatives of $P$, listed by ${E}$."
     _________________________________________________________________
   
   85k:41013 41A15 (41A05 65D07)
   Huang, Da Ren; Wang, Jian Zhong
   The Budan-Fourier theorem for ${\cal L}$-splines and its
   application. (Chinese)
   An English summary appears in Chinese Ann. Math. Ser. B {4} (1983),
   no. 2, 264.
   Chinese Ann. Math. Ser. A 4 (1983), no. 3, 349--360.
   
   Authors' summary: "Suppose that $t\sb j$ are real numbers
   $(j=0,\cdots,n), T=\{t\sb 0,\cdots,t\sb n\}, D=d/dx$. We consider the
   ${\scr L}$-spline related to the differential operator ${\scr L}\sb
   {n+1}=\prod\sb {j=0}\sp n(D-t\sb j)$, with simple knots. The
   Budan-Fourier theorem for ${\scr L}$-splines is proved. By use of it
   we also prove the existence and uniqueness of some ${\scr
   L}$-interpolation splines. If $T=-T$, $\Delta$ is a uniform mesh, then
   the approximation degree of ${\scr L}$-interpolation splines is $h\sp
   {n+1}$. Furthermore, when $n=2,3,4,5$, the optimal coefficients are
   obtained."
     _________________________________________________________________
   
   84m:01023 01A55
   Akritas, Alkiviadis
   Reflections on a pair of theorems by Budan and Fourier. 
   Math. Mag. 55 (1982), no. 5, 292--298.
   
   From the introduction: "In the early 19th century F. D. Budan and J.
   B. J. Fourier presented two different (but equivalent) theorems which
   enable us to determine the maximum possible number of real roots that
   an equation has within a given interval. In the discussion which
   follows we present separately, and without proofs, the classical
   theorems by Fourier and Budan and we indicate how they lead to the
   corresponding real root isolation methods. Some empirical results are
   also presented for comparison."
     _________________________________________________________________
   
   83e:41014 41A15
   Goodman, T. N. T.; Lee, S. L.
   The Budan\mhy Fourier theorem and Hermite\mhy Birkhoff spline
   interpolation. 
   Trans. Amer. Math. Soc. 271 (1982), no. 2, 451--467.
   
   The paper contains three main sections: one section concerning Budan -
   Fourier theorems for so-called Birkhoff splines (with compact
   support), a second one where a duality theorem and a regularity
   theorem for Birkhoff interpolation by Birkhoff splines are developed,
   and a third section dealing with cardinal interpolation of Birkhoff
   type. The results are interesting, while the proofs are rather
   challenging due to many highly technical details. The reader should be
   referred to another paper of the first author [Proc. Roy. Soc.
   Edinburgh Sect. A 88 (1981), no. 3-4, 195 - 201; MR 82g:41003] and to
   the paper by the reviewer, G. G. Lorentz and S. D. Riemenschneider
   ["Rolle theorem method in spline interpolation", Analysis, to appear].

   Reviewed by K. Jetter
     _________________________________________________________________
   
   58 #12097a 41A15
   Schoenberg, I. J.
   Cardinal interpolation and spline functions. VI. Semi-cardinal
   interpolation and quadrature formulae. 
   J. Analyse Math. 27 (1974), 159--204.
   
   58 #12097b 41A15
   Schoenberg, I. J.
   Cardinal interpolation and spline functions. VII. The behavior of
   cardinal spline interpolants as their degree tends to infinity. 
   J. Analyse Math. 27 (1974), 205--229.
   
   58 #12097c 41A15
   de Boor, Carl; Schoenberg, I. J.
   Cardinal interpolation and spline functions. VIII. The Budan-Fourier
   theorem for splines and applications. Spline functions (Proc.
   Internat. Sympos., Karlsruhe, 1975), pp. 1--79. Lecture Notes in
   Math., Vol. 501,
   Springer, Berlin, 1976.
   
   From the introduction to part VIII: "The paper is divided into four
   parts called A, B, C and D. We aim here at three or four different
   results. The unifying link between them is that they all involve the
   sign structure of what one might call a `Green spline', i.e., a
   function which consists of two null-splines pieced together at a
   certain point to satisfy at that point several homogeneous conditions
   and just one inhomogeneous condition, much as (any section of) a
   (univariate) Green function consists of two solutions to a homogeneous
   ordinary differential equation which are pieced together at a point in
   just that way. The different results are further linked by the fact
   that we use an extension of the Budan-Fourier theorem to splines in an
   essential way. In each of our applications of this theorem, the
   circumstances are such that the inequality furnished by the theorem
   becomes taut, i.e., must be an equality, and this provides an
   unexpected amount of precise information."
   
   © Copyright American Mathematical Society 1998