ブダンの定理

数学において、ブダンの定理（ブダンのていり、英語: Budan's theorem）は、ある区間における多項式の実根の数の上限と、その数の偶奇性を決定する定理である。 1807年にフランソワ・ブダン・ド・ボワローラン（François Budan de Boislaurent）（英語版）によって発表された。

同様の定理は、1820年にジョゼフ・フーリエによって独立に発表された。これらの定理はそれぞれが他方の定理の帰結となっている。フーリエの命題は19世紀の文献でより頻繁に見られ、フーリエの定理、ブダン・フーリエの定理、フーリエ・ブダンの定理、さらにはブダンの定理とも呼ばれてきた。

ブダンの元の形式は、現代の高速な多項式の実根分離アルゴリズムで使用されている。

符号変化

${\displaystyle c_{0},c_{1},c_{2},\ldots c_{k}}$ は実数の有限列とする。この数列における符号変化（sign variation または sign change）とは、以下の条件を満たす添え字のペア i < j である。

• ${\displaystyle c_{i}c_{j}<0}$
• かつ、以下のいずれかが成り立つ；
  • j = i + 1
  • または、i < k < j であるすべての k について ${\displaystyle c_{k}=0}$

つまり符号変化は、数列のゼロは無視して、符号が変わる各箇所で発生する。

何かしらの数列の符号変化の数を用いて、多項式の実根を調べることができる。ブダンの定理では、係数の列を用いる。フーリエの定理では、ある点において連続する導関数値の列を用いる。スツルムの定理では、ある点におけるスツルム列を用いる。

デカルトの符号法則

→詳細は「デカルトの符号法則」を参照

ここで説明されているすべての結果は、デカルトの符号法則に基づいている。

p(x) が実係数を持つ一変数多項式であるとする。その正の実根を、重複度を考慮して数えた数を #₊(p) とし^[1]、 その係数列における符号変化の数を v(p) とする。 すると、デカルトの符号法則により、

v(p) – #₊(p) は非負の偶数である。

特に、v(p) ≤ 1 の場合、#₊(p) = v(p) となる。

ブダンの命題

実係数を持つ一変数多項式 p(x) について、半開区間 (ℓ, r]（ℓ < r は実数）における、p の実根の数（重複度を含む^[1]）を #_(ℓ,r](p) で表す。 また、多項式 p_h(x) = p(x + h) の係数列の符号変化の数を v_h(p) で表す。 前節の表記法では v(p) = v₀(p) となる。

ブダンの定理は次の通り。

${\displaystyle v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}}$ は、非負の偶数である。

${\displaystyle \#_{(\ell ,r]}}$ が非負の場合、${\displaystyle v_{\ell }(p)\geq v_{r}(p)}$ が導かれる。

これはデカルトの符号法則の一般化であり、r を十分に大きくとれば p のすべての実根よりも大きくなり、${\displaystyle p_{r}(x)}$ のすべての実係数は正になる、つまり ${\displaystyle v_{r}(p)=0}$ になる。 したがって ${\displaystyle v_{0}(p)=v_{0}(p)-v_{r}(p)}$ かつ ${\displaystyle \#_{+}=\#_{(0,r)}}$ であり、デカルトの符号法則はブダンの定理の特別なケースである。

デカルトの符号法則によれば、${\displaystyle v_{\ell }(p)-v_{r}(p)\leq 1}$ であれば ${\displaystyle \#_{(\ell ,r]}=v_{\ell }(p)-v_{r}(p)}$ である。 これにより、${\displaystyle v_{\ell }(p)-v_{r}(p)\leq 1}$ であれば、『ゼロ根検定』および『単一根検定』ができることになる。

例

1. 多項式 ${\displaystyle p(x)=x^{3}-7x+7}$ は、開区間 ${\displaystyle (0,2)}$ について；

${\displaystyle {\begin{aligned}p(x+0)&=p(x)=x^{3}-7x+7\\p(x+2)&=(x+2)^{3}-7(x+2)+7=x^{3}+6x^{2}+5x+1\end{aligned}}}$

したがって、${\displaystyle v_{0}(p)-v_{2}(p)=2-0=2}$ であり、ブダンの定理より、多項式 ${\displaystyle p(x)}$ は、開区間 ${\displaystyle (0,2)}$ に2個または0個の実根を持つことがわかる。

2. 同じ多項式 ${\displaystyle p(x)=x^{3}-7x+7}$ について；

${\displaystyle p(x+1)=(x+1)^{3}-7(x+1)+7=x^{3}+3x^{2}-4x+1}$

したがって、${\displaystyle v_{0}(p)-v_{1}(p)=2-2=0}$ であり、ブダンの定理より、多項式 ${\displaystyle p(x)}$ は、開区間 ${\displaystyle (0,1)}$ に実根がないことがわかる。これは、ブダンの定理をゼロ根検定に用いる例である。

フーリエの命題

多項式の実根に関するフーリエの定理は、フーリエ・ブダンの定理またはブダン・フーリエの定理（あるいは単にブダンの定理）とも呼ばれ、 h = l および r に対して、p(x + h) の係数列が、h における p の導関数列に置き換えられることを除いて、ブダンの定理とまったく同じである。

それぞれの定理は、他方の定理の帰結である。 これは h における多項式 p のテイラー展開；

${\displaystyle p(x)=\sum _{i=0}^{\deg p}{\frac {p^{(i)}(h)}{i!}}(x-h)^{i}}$

から得られる。 これは、p(x + h) における xⁱ の係数が、${\displaystyle p^{(i)}(h)}$ を i! で割った正の数であることを意味する。 したがって、フーリエの定理とブダンの定理で考慮される数列には、同じ数の符号変化がある。

これら2つの定理の強い関連性は、19世紀に起こった優先順位論争や、同じ定理に複数の名称が使われた理由を説明するものと考えられる。 ブダンの定理よりフーリエの定理の方が、階乗の因数の影響で係数がはるかに大きくなるため、現代のコンピュータ計算においては、一般にブダンの定理の方が好まれる。

証明

それぞれの定理は他方の系であり、フーリエの定理を証明すれば十分である。

証明：

${\displaystyle n}$ を ${\displaystyle f}$ の次数とすると、${\displaystyle f,f',...,f^{(n-1)}}$ は非定数多項式、${\displaystyle f^{(n)}}$ はゼロでない定数、${\displaystyle f^{(n+1)},...}$ はすべて恒等的にゼロになる。

${\displaystyle t}$ の関数としての符号変化 ${\displaystyle v_{t}(f)}$ は、${\displaystyle f,f',...,f^{(n-1)}}$ の1つ以上についての根でのみ変化し得る。

${\displaystyle v_{t}(f)}$ が ${\displaystyle t=r}$ で変化する場合、ある ${\displaystyle k}$ に対して ${\displaystyle f^{(k)}(x)}$ は ${\displaystyle t}$ で根を持つが、${\displaystyle f,f',...,f^{(k-1)}}$ のそれぞれは ${\displaystyle t}$ で根を持たない。

${\displaystyle k=0}$ のとき、${\displaystyle s\geq 1}$ と、${\displaystyle p(0)\neq 0}$ を満たす多項式 ${\displaystyle p}$ に対して ${\displaystyle f(x)=(x-r)^{s}p(x-r)}$ である。 小さな ${\displaystyle \epsilon }$ に対して、${\displaystyle r}$ と ${\displaystyle r-\epsilon }$ における ${\displaystyle f,f',...,f^{(n)}}$ を明示的に計算すると、${\displaystyle v_{r}(f)=v_{r-\epsilon }(f)-s-2s',\quad \exists s'\geq 0}$ が成り立つ。

この式において、項『 ${\displaystyle -s}$ 』は、${\displaystyle f,f',...,f^{(s)}}$ の符号が ${\displaystyle (-1)^{s}\operatorname {sign} (p(0)),(-1)^{s-1}\operatorname {sign} (p(0)),...,-\operatorname {sign} (p(0)),\operatorname {sign} (p(0))}$ から ${\displaystyle 0,0,...,0,\operatorname {sign} (p(0))}$ に変化することに起因する。 項『 ${\displaystyle -2s',\quad \exists s'\geq 0}$ 』は、より高次の導関数の符号がゼロになる可能性があることに起因する。

${\displaystyle k\geq 1}$ の場合、一部の導関数は ${\displaystyle r}$ でゼロになるが、${\displaystyle f^{(k-1)}(x)}$ と ${\displaystyle f^{(n)}(x)}$ は両方ともゼロではないため、符号変化の回数の減少は偶数である：

$${\displaystyle v_{r}(f)=v_{r-\epsilon }(f)-2s',\quad \exists s'\geq 0}$$

${\displaystyle v_{t}(f)}$ が ${\displaystyle t=l}$ で変化する場合は、同様に議論すると、どちらの場合についても、${\displaystyle v_{l+\epsilon }(f)=v_{l}(f)}$ となるような小さな ${\displaystyle \epsilon }$ を取ることができることがわかる。

歴史

多項式の実根を数えて見つける問題は、19世紀初頭になってようやく体系的に研究され始めた。

1807年、フランソワ・ブダン・ド・ボワローラン（英語版）は、デカルトの符号法則が適用できる区間が (0, +∞) であるのを、任意の区間に拡張する方法を発見した^[2]。

ジョゼフ・フーリエは、1820年に同様の定理を発表し^[3]、20年以上その定理について研究した^[4]。

2つの定理は互いに類似しているため、独立に発見された^[4]にもかかわらず、優先順位をめぐる論争があった^[5][6]。 19世紀の方程式論（英語版）の教科書では、一般にフーリエの定式化と証明が使われていた。

19世紀における利用

ブダンの定理とフーリエの定理は、多項式の区間内の実根の数を数える問題を完全には解決しなかったものの、すぐに非常に重要なものと見なされるようになった。この問題は1827年にジャック・シャルル・フランソワ・スツルムによって完全に解決された。

スツルムの定理はデカルトの符号法則に基づいていないが、スツルムの定理とフーリエの定理は、数列の符号変化の数を使用するという点だけでなく、問題へのアプローチが似ているという点でも関連している。スツルム自身もフーリエの方法に触発されたことを認めている^[7]： « C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses démonstrations, que j'ai trouvé les nouveaux théorèmes que je vais énoncer. » これは 『私がこれから述べる新しい定理は、彼が確立した原理に依拠し、彼の証明を模倣することによって発見されたものである。』 と翻訳される。

このため、19世紀には方程式理論に関するほぼすべての書籍に、フーリエの定理とスツルムの定理が一緒に登場した。

フーリエとブダンは結局、根を求める区間の大きさを符号変化の数の差が最大1になるように縮小し、最終的な区間がそれぞれ最大1つの根を含むことを証明するという問題を未解決のまま残した。この問題は1834年にアレクサンドル・ジョゼフ・イドゥルフ・ヴァンサン（フランス語: Alexandre Joseph Hidulphe Vincent）によって解決された^[8]。 大まかに言えば、ヴァンサンの定理は、ブダンの変数の線形変換を、連分数を用いてメビウス変換に置き換えることで構成されている。

ブダン、フーリエ、そしてヴァンサンの定理は19世紀末に忘れ去られた。 20世紀後半以前にこれらの定理に言及した最後の著者は、ジョセフ・アルフレッド・セレット（英語版）である^[9]。 これらの定理は1976年にコリンズとアクリタスによって再び導入され、計算機代数において、コンピュータ上で実根分離を行う効率的なアルゴリズムを提供した^[10]。

関連項目

• 多項式の根
• 求根アルゴリズム
• スツルムの定理
• ヴァンサンの定理
• 実根分離