無作為実係数多項式の最大根は複素数より実数になりやすい
(mathoverflow.net)- 実係数が独立一様分布に従う無作為多項式では、実根の総数はおおよそ 2log n/π にとどまるが、実験では絶対値が最大/最小の根が 実数である確率 のほうが高く現れる
- 次数ごとの 10^5回モンテカルロシミュレーション では、この確率は n が大きくなるにつれて 1/2 付近へ下がり、正規分布係数を (-1,1) にスケーリングしても同様の観測が維持される
- ある回答では、有限次数の極端根の問題は無作為冪級数 P(x)=a₀+a₁x+a₂x²+… の最小根が実数かを問う問題へ収束するとみなしている
- 分布によって極限値は変わりうるため、一様分布 [-1,1] では約 51%、標準正規分布では約 52%、分散 1/k! の正規分布では 62%、±1 の離散分布では 40%台前半に見える
- 回答者は「1/2に収束する」という解釈に懐疑的で、次数 200 と 300 を比較した 4万件の実験 では最小根が実数かどうかがすべて維持され、極限が 50% を上回る可能性を強く見ている
問題設定: 実根は少ないが極端根は実数側に偏る
- 実係数をもつ無作為多項式では、全根のうち 実根の数 は複素根よりはるかに少ない
- 係数が独立に (-1,1) 一様分布に従うと、次数 n の多項式の実根数は漸近的に
2log n/π + o(1) - 複素根数はおおよそ
n - 2log n/π - 参照された論文によれば、他の係数分布でも似た漸近式が成り立つ
- 係数が独立に (-1,1) 一様分布に従うと、次数 n の多項式の実根数は漸近的に
- ここで「最大の根」と「最小の根」は、それぞれ 絶対値が最大の根 と 絶対値が最小の根 を意味する
- 実根がはるかに少ないなら極端根も複素数になりそうだが、質問者の実験データは逆の傾向を示している
モンテカルロ観測と未解決の問い
- 観測データの要点は3つある
- 最大の根または最小の根が 実数である確率 は、複素数である確率より大きい
- この確率は n が大きくなるにつれて 1/2 付近の値へ下がるように見える
- 各 n の値ごとに 10^5回のモンテカルロシミュレーション を行っている
- 係数を一様分布ではなく平均 0、標準偏差 1 の正規分布から取り、(-1,1) にスケーリングしても同じ観測と極限確率が維持されると書かれている
- 問いは次の2点に絞られる
- なぜ最大の根と最小の根が 実数側に偏るのか
- 次数 n におけるその確率が n→∞ のとき 1/2 付近の値に収束するのか
- 観測された偏りは条件付き確率として次のように表される
P(L|R)=P(S|R)≈π/(4log n)P(L|C)=P(S|C)≈π/(2nπ-4log n)
更新: 下限の証明と n=1000 の追加実験
- リンク先の Math StackExchange 投稿では、最大の根が実数である確率が少なくとも次の値以上であることが証明されている
(23-16√2)/6 ≈ 6.2%
- 2024年5月11日の更新では、次数 n=1000 の多項式に対するほぼ 60,000回の実験 結果が追加された
- n≤125 で観測されたグラフと整合的な結果になっている
- 試行回数が増えるほど最大の根が実数である確率は減少する傾向を示し、1/2 に収束する可能性があるとしている
回答: 無作為冪級数の最小根に結び付く
- Math StackExchange と Thurston, Selberg, and random polynomials Part II のブログ記事を根拠に、適切な係数分布では有限次数の極限が 無作為冪級数の最小根 の問題につながる
P(x)=a₀+a₁x+a₂x²+…- 有限次数で最小根が実数である確率の極限は、この無作為冪級数の最小根が実数である確率になる
- Rouché の定理を使えば、この確率が 0より大きく1より小さい ことは容易に示せるという
- 極限値は係数
aᵢの分布に依存しうるaᵢが [-1,1] 一様分布なら約 51%- 平均 0、分散 1 の Gaussian なら約 52%
- Gaussian だが分散が
1/k!なら約 62% 1と-1の離散分布なら 40%台前半に見える
- したがって、「合理的なすべての場合で 50% を超える」というより、モデルによって 50% を上回ることも下回ることもある とするのがより正確である
実根が少なくても極端根を占めうる理由
- 多くのモデルでは根は単位円板の周辺に集まり、角度分布は一様化する傾向があり、非常に局所的なスケールでは根の間に 反発(repulsion) が生じる
- 複素根は単位円板の周囲に広がれる一方で、実根同士の反発は実根をより小さく、あるいはより大きくするよう「強制」するとみなせる
- この観点では、全実根数が対数オーダーであっても、最小根や最大根を占めるには 十分な数の実根 がある可能性がある
- 残る課題は、モンテカルロで容易に計算できる値をどう 厳密な数値評価 にするかである
Rouché の定理で厳密な評価を作るアイデア
- 一様分布
aᵢ∈[-1,1]を仮定し、低次数多項式の係数空間を小さな箱に分割する方法が提案されている- 例として、次数 100 未満の多項式で各
aᵢを同じ長さの 1000 個の区間に分ける方法が挙げられている - 回答では、結果として
100^1000個の多項式になると書かれている
- 例として、次数 100 未満の多項式で各
- モンテカルロの観点では、ほとんどの多項式を次の2集合に分けられると期待される
- 最小根が実数で、かつ絶対値が 9/10 より小さい場合
- 最小の2根が複素共役対で、かつ絶対値が 9/10 より小さい場合
- どちらの場合も、その根だけを含む円板の境界で
|P| > (9/10)^100を示せれば、Rouché の定理 により最小根の性質が保たれることを保証できる - この方法に理論上の障害はないが、実際の計算量は大きすぎる可能性があり、次数 10 未満かつ
10^10個の多項式規模の計算、あるいはより効率的な分割が必要かもしれない
1/2 収束解釈への反論と追加計算
- 回答者は、質問者の「おそらく 1/2 に収束する」という解釈には説得力が乏しいと見ており、他の自然で対称的なモデルが 1/2 に収束しないことを反証材料に挙げている
- 次数 500 の無作為多項式 1000 個を生成して最小根の絶対値を確認したところ、すべての場合で絶対値は 0.91より小さい だった
- これを無作為冪級数に拡張すると、
|z|<0.91の円板内で関数の変化は10^-20規模かそれ以下だとしている - Rouché の定理が適用できないためには、最小根または複素共役対が次の根と絶対値の上で極端に近くなければならない
- これを無作為冪級数に拡張すると、
- より良い収束率推定のため、次の実験が提案されている
- 次数 500 の無作為多項式 50,000 個を計算する
- 同じ初項を維持したまま次数 1000 に拡張した多項式 50,000 個を計算する
- 両次数で最小根が実数かどうか、また次数を増やしたときその性質がどれだけの頻度で変わるかを確認する
- 回答者の直感では、次数 500 から 1000 に行くとき 変化するケースは非常にまれ である
- 両者がともに 51% 前後で、変化率が 1% を大きく下回るなら、極限が 50% より厳密に大きいことのシグナルとみなせる
実際の比較実験: 次数 200 と 300
- 高次数の計算に時間がかかるため、実際の比較は次数 200 と 300 で行われた
- 40,000 個の多項式を実行した結果:
- 次数 200 の多項式では 20,287個 で最小根が実数だった
- それらを次数 300 に拡張したとき、すべての場合で同じ性質が維持された
- この結果は、次数 200、300、1000 の期待値が無限次数の期待値にすでに非常に近い可能性を示唆している
- 計算値は 約 50.7% であり、質問者の計算も同様に 50.7% 程度だったため、極限が 1/2 を上回る側の根拠として提示されている
- 回答者は「極限は 50% より大きい」と確信しており、自分が誤りだと証明した人に 100 ドルを払うと付け加えている
切断冪級数の高速な安定化
- 追加の証拠として、無作為冪級数
P(x)=Σaᵢxᶦの切断多項式Pₖ(x)=Σᵢ₌₀ᵏaᵢxᶦについて、k=1 から 1000 まで最小根が実数か複素数かがいつ安定化するかを確認している - 200 個の無作為多項式では、安定化の開始点はほとんど非常に小さかった
- 多くは k=1 または k=2 ですでに安定化していた
- 列挙された値の最大は 22
- この結果も、有限次数の実験が無限次数極限へ素早く近づく可能性を支持している
1件のコメント
Hacker News のコメント
偶然の水準と 1/φ の間にあるというのは本当に不思議だ
リンク先の MSE の投稿では、最大の根が実数である確率が少なくとも 6.2% であることが今では証明されていて、しかも 1/φ の 1/10 以上でもある。素数と φ のつながりは自然だと思う。素数はよく誤解されるようにランダムなのではなく、以前の素数から再帰的に生じるもので、以前の素数の倍数が占められなかった「隙間」だからだ。だから e や φ のような何らかの自然な成長パターンが現れると期待してもよい。真理や美といった、非常に根本的な大きさのパターンだ
素数そのものの性質というよりは成長の性質であり、ランダムな数の集合ではよりよく当てはまる
すぐに思い浮かぶ疑問が二つある
この面白い記事をけなすつもりではない
ただし、問いの重要な部分は、実数上の任意の可能な分布についても問うことができる
これで数値実験をしてみたいなら、R にはこの用途の組み込みサポートがある
plot(polyroot(runif(101,-1,1)))こうすると 100 次多項式の根の可視化を見ることができる
「係数は独立で、(−1,1) から一様ランダムだと仮定する。そうでなければ各係数を絶対値が最大の係数で割って、各係数を (−1,1) にスケールできるからだ。」
直感が正しいか分からないが、このように割ってスケールすると、最大係数を除いた残りの係数の分布は非一様分布になるのではないか？
5 次以上の多項式には公式がないのに、実根と
実数 + epsilon*iをどう区別するのか？(r - ɛ, r + ɛ]の中に実根がちょうど 1 個あるか、またはちょうど 0 個であるかを認証できる推定値 r がある根から ɛ 以内にあれば、正確な値がなくても実根と複素根を区別できる。もちろん Budan の定理が答えを出せない場合もある。たとえばその区間内に根が 2 個以上ある場合が最も明白な失敗例だ
たとえば係数
a_iが独立同分布の Bernoulli 確率変数である多項式a_n x^n + ... + a_0を考えると、次数 n が大きくても（>4）、この種の多項式はx = 0に実根を持つ確率が 1/2 だと自信を持って言える。リンク先の質問でも、似ているがより洗練された論理が働く係数が実数なら、公式があっても役に立たない。ある数が 0 と等しいかを判定できないという同じ問題がある。たとえば二次方程式の解の公式で判別式が
-epsilonになり得るが、epsilon が 0 なら虚根はなく、0 でなければ虚根があるx+iyとx-iyが複素根で y が非常に小さいなら、x における導関数も小さくなければならない。y=0 なら重根なのでp'(x)=0になるしたがって
p'(x)が 0 から十分離れていれば、単純な実根だと見なせる。そしてランダム係数では重根は実質的に起こらないように思う公式について言えば、5 次以上に対する一般公式はない。一般公式が存在するのは 4 次以下の多項式だけだ
もちろん、特定の種類の高次多項式には特定の公式がある場合もある。しかし一般的な 5 次以上については存在せず、これは古典的にすでに証明されている
少し話題から外れるが、こういう数学の記事を読むのはいつも楽しい。
大学では数学が本当に好きで、専攻はコンピュータサイエンスだったが、先生たちの楽しそうな様子にいつも刺激を受けていた。もっと学んで、数学で問題を解くことに少し足を踏み入れてみたい。おそらく数値解析寄りになるかもしれない。
ただ、卒業してから2年経っていて、その間あまりやっていなかったので、かなり学び直す必要がありそう。どこから始めるとよいか、面白いテーマを見つけられる場所があるか知りたい。数値解析ではないが、学部時代にProject Eulerの問題をかなり解いた。似たものはほかにもあるだろうか？ どんなアイデアでも歓迎。
それとも、まず教科書の問題を全部解き直すべきだろうか？ ;-)
Proofs from THE BOOK (https://link.springer.com/book/10.1007/978-3-662-57265-8) も楽しく読めると思う。
こういう種類の数学を知らないからかもしれないが、よく分からない。
自分の頭の中では、「ランダムな」多項式を取り、最大の2つの根だけを見る。次に2種類の反射を考える。曲線の下側／上側を基準にした反射と、x軸を基準にした反射だ。その上位2つの根が退化していなければ、反射で得られる4つの曲線の組み合わせのうち、2つの曲線は最大実根を持ち、2つの曲線は最大虚根を持つように思える。退化していれば最大根は実数になる。
だから、(1) 最大根が実数である場合は虚数である場合より多く、(2) 退化していない最大根を持つ曲線は退化した場合より無限に多いので、その「優位」は消えるほど小さい、と結論づけそうになる。
用語をほとんど知らないことは伝わると思う。おそらく、ランダム係数の一様性が空間での一様分布につながるわけではない、という点を見落としているのだろう。あるいは、私の反射が条件の1つ、たとえば実係数条件を壊しているのかもしれない。もしくは単に間違っているだけかもしれない。
p(x)のグラフをx軸について反射するというのは、p(x)をp(-x)に変えることだ。「曲線の下側／上側を基準に反射」とはどういう意味か？ y軸についての反射か？ それならp(x)が-p(x)に変わるという意味になる。組み合わせというのは、おそらく
(多項式 + 反射された多項式)/2を取るという意味なのか？実数のほうが可能性が高そうだという点が、なぜ反直感的なのかよく分からない。
区間内の一様ランダムな実係数の代わりに、複素平面の原点中心の円板から一様にランダムな根を選んで多項式を作るなら、実係数多項式になる可能性はほとんどない。逆にランダムな根が実数なら、多項式は必ず実係数を持つ。したがって事前にはどちらの答えも驚くものではなく、実数のほうがもっともらしそうに見えるほうが、自分には少し直感的だ。もちろん必然ではない。
log(n)個が実根で、n - log(n)個が非実根になる。nが大きくなると
log(n)はnに比べて非常に小さいので、半分を超える場合で最大根がそのごく少数の実根の1つだというのは、とても驚くべきことだ。ここのリンクをたどっていたら、Boris Hanin の回答の1つが、しばらく抱いていた疑問を解決してくれたようだ。
ところで、ランダム多項式というのは実係数なのか、複素係数なのか気になる。
[-1, 1]の範囲のランダム係数を選び、ある種のスケールされた正規分布もテストしたように見える。