ブダンの定理とは？わかりやすく解説

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

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

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

符号変化

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

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

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

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

デカルトの符号法則

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

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

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

v (p) - # + (p)

は非負の偶数である。

特に、 $v (p) \leq 1$ の場合、 $# + (p) = v (p)$ となる。

ブダンの命題

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

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

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

は、非負の偶数である。

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

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

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

例

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

{\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}}

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

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

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

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

フーリエの命題

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

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

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

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

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

証明

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

証明：

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

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

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

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

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

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

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

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

歴史

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

1807年、フランソワ・ブダン・ド・ボワローラン（英語版）は、デカルトの符号法則が適用できる区間が $(0, +\infty)$ であるのを、任意の区間に拡張する方法を発見した^[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年にアレクサンドル・ジョセフ・イドゥルフ・ヴィンセントによって解決された^[8]。大まかに言えば、ヴィンセントの定理（英語版）は、ブダンの変数の線形変換を、連分数を用いてメビウス変換に置き換えることで構成されている。

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

脚注

^ ^a ^b これは、重複度 $m$ の根は、 $m$ 個の根として数えられることを意味する。
^ Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier
^ Fourier, Jean Baptiste Joseph (1820). “Sur l'usage du théorème de Descartes dans la recherche des limites des racines”. Bulletin des Sciences, par la Société Philomatique de Paris: 156–165.
^ ^a ^b Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation), p. 383
^ Akritas, Alkiviadis G. (1981). “On the Budan–Fourier Controversy”. ACM SIGSAM Bulletin 15 (1): 8–10. doi:10.1145/1089242.1089243.
^ Akritas, Alkiviadis G. (1982). “Reflections on a Pair of Theorems by Budan and Fourier”. Mathematics Magazine 55 (5): 292–298. doi:10.2307/2690097. JSTOR 2690097.
^ Benis-Sinaceur, Hourya (1988). “Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm”. Revue d'Histoire des Sciences 41 (2): 99–132 (p. 108). doi:10.3406/rhs.1988.4093.
^ Vincent, Alexandre Joseph Hidulph (1834). “Mémoire sur la résolution des équations numériques”. Mémoires de la Société Royale des Sciences, de l' Agriculture et des Arts, de Lille: 1–34.
^ Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. pp. 363–368
^ Collins, G. E.; Akritas, A. G. (1976). Polynomial real root isolation using Descarte's rule of signs. Proceedings of the 1976 ACM symposium on Symbolic and Algebraic Computation. pp. 272–275. doi:10.1145/800205.806346.

外部リンク

O'Connor, John J.; Robertson, Edmund F., “Budan de Boislaurent”, MacTutor History of Mathematics archive, University of St Andrews .

[mult-1] これは、重複度 $m$ の根は、 $m$ 個の根として数えられることを意味する。

[nmethode-2] Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier

[Fourier-3] Fourier, Jean Baptiste Joseph (1820). “Sur l'usage du théorème de Descartes dans la recherche des limites des racines”. Bulletin des Sciences, par la Société Philomatique de Paris: 156–165.

[arago-4] Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation), p. 383

[BF-5] Akritas, Alkiviadis G. (1981). “On the Budan–Fourier Controversy”. ACM SIGSAM Bulletin 15 (1): 8–10. doi:10.1145/1089242.1089243.

[Reflections-6] Akritas, Alkiviadis G. (1982). “Reflections on a Pair of Theorems by Budan and Fourier”. Mathematics Magazine 55 (5): 292–298. doi:10.2307/2690097. JSTOR 2690097.

[Sturm-7] Benis-Sinaceur, Hourya (1988). “Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm”. Revue d'Histoire des Sciences 41 (2): 99–132 (p. 108). doi:10.3406/rhs.1988.4093.

[paper_1834-8] Vincent, Alexandre Joseph Hidulph (1834). “Mémoire sur la résolution des équations numériques”. Mémoires de la Société Royale des Sciences, de l' Agriculture et des Arts, de Lille: 1–34.

[Serret-9] Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. pp. 363–368

[10] Collins, G. E.; Akritas, A. G. (1976). Polynomial real root isolation using Descarte's rule of signs. Proceedings of the 1976 ACM symposium on Symbolic and Algebraic Computation. pp. 272–275. doi:10.1145/800205.806346.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

ブダンの定理とは？わかりやすく解説