2008年、ダニエル・スピルマンは、イェール大学の同僚であるギル・カライに、ノード間の接続を減らしながら元のネットワークの本質的な機能を維持するようにネットワークを「スパース化」する方法に関する、彼が取り組んでいるコンピューター科学の問題について語った.
ネットワークのスパース化は、データ圧縮と効率的な計算に適用されますが、Spielman の特定の問題は、Kalai とは異なる何かを示唆していました。それは有名な Kadison-Singer 問題 (ほぼ 50 年間未解決のままだった量子物理学の基礎に関する問題) に関連しているように思われました.
何十年にもわたって、Kadison-Singer 問題は数十の遠い数学と工学の分野にまで入り込んできましたが、誰もそれを解読できなかったようです。 2014 年の調査記事で、この質問は「過去 50 年間で最も才能のある数学者の最善の努力に逆らった」と、コロンビアのミズーリ大学のピーター・カザッツァとジャネット・トレメインは書いています。
コンピューター科学者として、スピルマンは量子力学やカディソン・シンガー問題に関連する C* 代数と呼ばれる数学的分野についてほとんど知りませんでした。しかし、主な機関がエルサレムのヘブライ大学であるカライが問題の多くの同等の定式化の1つを説明したとき、スピールマンは彼自身がそれを解決するのに最適な立場にあるかもしれないことに気づきました。 「それはとても自然で、私が考えていることの中心にあるように思えました」と彼は言いました. 「私は、『それを証明できなければならない』と思いました。」彼は、問題が解決するまでに数週間かかるかもしれないと推測しました。
代わりに、彼は5年かかりました。 2013 年、ポスドクの Adam Marcus (現在はプリンストン大学) と大学院生の Nikhil Srivastava (現在はカリフォルニア大学バークレー校) と協力して、Spielman はついに成功を収めました。 C* 代数やその他の多くの分野における最も重要な問題の 1 つが、問題の中心にある分野についてほとんど知らなかったコンピューター科学者によって解決されたという噂が数学コミュニティに急速に広まりました。 /P>
これらの分野の数学者は、喜びと手ごわさの組み合わせでニュースを迎えました。カザザとトレメインが「私たちの時代の主要な成果」と呼んだ解決策は、問題がどのように解決されるかについての期待に反し、困惑するほど異質に見えました。過去 2 年間、Kadison-Singer 問題の専門家は、証明のアイデアを吸収するために懸命に努力しなければなりませんでした。 Spielman、Marcus、Srivastava は、「私たちの誰も聞いたことのない多くのツールをこの問題にもたらしました」と Casazz 氏は述べています。 「私たちの多くはこの問題が大好きで、それが解決されるのを待ち望んでいたのですが、彼らがどのように解決したのか理解するのに非常に苦労しました。」
「これらの方法が機能する理由について深い直感を持っている人々は、これらの問題に長い間取り組んできた人々ではありません」と、これらの開発を追跡してきたカリフォルニア大学ロサンゼルス校のテレンス・タオは述べています。数学者は、これらの異なる陣営を結び付けるためにいくつかのワークショップを開催しましたが、証明を消化するにはさらに数年かかる可能性があると Tao 氏は述べています。 「この魔道具の説明書はまだありません。」
しかし、コンピュータ サイエンティストは、新しい技術をすぐに活用してきました。たとえば昨年、2 人の研究者がこれらのツールを活用して、難しいことで有名な巡回セールスマンの問題を理解する上で大きな飛躍を遂げました。カディソン・シンガー問題に関連する分野で働いているプリンストン大学の数学者アサフ・ナオールは、そのような進歩がさらにあることは確かである. 「これは深遠すぎて、これ以上多くのアプリケーションを用意することはできません。」
よくある問題
1959 年に Richard Kadison と Isadore Singer が提起した質問は、特別なサブシステムでその状態に関する完全な情報を持っている場合、量子システムの「状態」についてどの程度知ることができるかを尋ねています。伝説的な物理学者ポール・ディラックによる非公式のコメントに触発された彼らの質問は、粒子の位置や運動量などの特定の属性のペアを任意の精度で同時に測定することはできないというヴェルナー・ハイゼンベルグの不確実性原理に基づいています。
Kadison と Singer は、互換性を持って同時に測定できるのと同じくらい多くの異なる属性 (または「観察対象」) を含むサブシステムについて疑問に思いました。そのようなサブシステムの状態を完全に把握している場合、システム全体の状態を推測できますか?
測定している系が実線に沿って移動できる粒子である場合、Kadison と Singer は答えがノーであることを示しました。同時に測定できるオブザーバブル。 「あたかも多くの異なる粒子が同時にまったく同じ位置にあるかのようです — ある意味で、それらは平行宇宙にあります」と Kadison は電子メールで書いたが、そのような状態が物理的に実現できるかどうかはまだ明らかではないと警告した.
Kadison と Singer の結果は、粒子が存在する空間が連続した線ではなく、代わりにその線のより途切れたバージョンである場合に何が起こるかを述べていませんでした — Kadison が言ったように、空間が「粒状」である場合.これは、Kadison-Singer 問題として知られるようになった問題です。
Kadison と Singer は、連続的な設定での作業に基づいて、この新しい設定でも答えはパラレル ユニバースが存在するということになると推測しました。しかし、彼らは自分たちの推測を推測として述べることまではしませんでした。 「気をつけていてよかったです」とカディソンは言いました。
現在ペンシルバニア大学とマサチューセッツ工科大学 (名誉) にいるカディソンとシンガーは、量子力学の哲学的基礎への関心がルネサンス期に入った瞬間に疑問を投げかけました。一部の物理学者はこの分野に対して「黙って計算する」アプローチを推進していましたが、他のより数学的に傾倒した物理学者は、カディソン・シンガー問題に飛びつきました。彼らは、カディソン・シンガー問題を C* 代数、代数特性を捉える抽象的な構造に関する問題として理解しました。量子システムだけでなく、確率論で使用される確率変数、行列と呼ばれる数のブロック、および正規数についても同様です。
C* 代数は難解な主題であり、カサザの言葉では「数学に存在する最も抽象的なナンセンス」です。 「この地域以外では、そのことをよく知っている人は誰もいません。」 Kadison-Singer 問題が存在してから最初の 20 年間、それはこの不可解な領域に閉じ込められたままでした。
その後、1979 年に、現在ペンシルベニア州立大学の名誉教授であるジョエル アンダーソンは、行列をより単純なチャンクに分解できるのはいつかという簡単に述べられる問題と同等であることを証明することによって、この問題を広めました。行列は線形代数の中核となるオブジェクトであり、線、平面、および高次元空間によって挙動を捉えることができる数学的現象を研究するために使用されます。突然、Kadison-Singer 問題がいたるところに広がりました。その後数十年にわたって、それは次々と分野で主要な問題として浮上しました。
これらの異なる分野間の相互作用はほとんどない傾向があるため、カサザが信号処理の彼自身の分野で最も重要な問題と同等であることに気付くまで、Kadison-Singer 問題がどれほど遍在するようになったかを誰も理解していませんでした。問題は、信号の処理をより小さく単純な部分に分解できるかどうかということでした。カサザはカディソン・シンガー問題に飛び込み、2005 年にトレメインと 2 人の共著者と共に、それが数学と工学の 12 の分野における最大の未解決問題と同等であることを示す論文を書きました。これらの問題のいずれか 1 つを解決することで、すべての問題が解決することを著者は示しました。
彼らが書いた多くの同等の定式化の 1 つは、セントルイスのワシントン大学の Nik Weaver によってほんの数年前に考案されたものでした。 Weaver のバージョンでは、ベクトルのコレクションを、それぞれが元のコレクションとほぼ同じ一連の方向を指す 2 つのグループに分割できるのはいつなのかという、自然に聞こえる質問に問題を絞り込みました。 Kadison-Singer の質問の中心にある「コアの組み合わせ問題をもたらした美しい問題です」と Weaver 氏は述べています。
そのため、カザザの調査での言及と、彼のアプローチに対する懐疑論を表明した別の 1 つの論文を除けば、ウィーバーは驚いた.彼は自分の論文に誰も気づいていないと思っていましたが、実際にはそれを解決するのに適切な人々の注目を集めていました.
電気特性
Spielman が 2008 年に Weaver の予想について知ったとき、彼はそれが彼の種類の問題であることを知っていました。ネットワークとベクトルの集合を切り替える自然な方法があり、Spielman はそれまでの数年間、ネットワークを物理的なオブジェクトとして見ることによってネットワークへの強力な新しいアプローチを構築してきました。たとえば、ネットワークが電気回路と考えられる場合、(代替ルートを見つけるのではなく) 特定のエッジを流れる電流の量は、ネットワークにおけるそのエッジの重要性を測定する自然な方法を提供します。
Spielman は、Kalai が Kadison-Singer 問題の別の形式を彼に紹介した後、Weaver の予想を発見し、それがネットワークに関する単純な質問とほとんど同じであることに気付きました。 、赤いエッジと青いエッジ — 結果として得られる赤と青のネットワークは、ネットワーク全体と同様の電気的特性を持つようになりますか?
これが常に可能であるとは限りません。たとえば、元のネットワークが 1 つのエッジによって相互にリンクされた 2 つの高度に接続されたクラスターで構成されている場合、そのエッジはネットワーク内で非常に重要です。したがって、そのクリティカル エッジが赤色の場合、青色のネットワークはネットワーク全体と同様の電気的特性を持つことはできません。実際、青いネットワークは接続すらされません。
ウィーバーの問題は、これがネットワークを似たような小さなネットワークに分割する唯一の障害であるかどうかを問うものです。言い換えれば、ネットワーク内を移動する方法が十分にある場合 (個々のエッジがそれほど重要でない場合)、ネットワークを同様の電気的特性を持つ 2 つのサブネットワークに分割できるでしょうか?
Spielman、Marcus、および Srivastava は、答えはイエスであると考えており、彼らの直感は、ネットワークのスパース化に関する以前の研究から生じたものではありませんでした。また、何百万ものシミュレーションを実行しましたが、反例は見つかりませんでした。 「私たちのものの多くは実験によって導かれました」とマーカスは言いました。 「20 年前、私たち 3 人が同じ部屋に座っていても、この問題は解決しなかったでしょう。」
問題が次々とつまずきをもたらしたとしても、シミュレーションは彼らが正しい道を進んでいると彼らに確信させました。そして、彼らは夢中になるのに十分な進歩を遂げ続けました。チームがこの問題に取り組んで 4 年目の終わりにマーカスのポスドク フェローシップが期限切れになったとき、彼は一時的に学界を離れ、ニューヘブンを離れるのではなく、クリスプリーと呼ばれる地元の新興企業に参加することを選択しました。 「私は会社で週に 4 日働き、その後は週に 1 回ほどエール大学に行きました」と彼は言いました。
ネットワークの電気特性は、ネットワークの「特性多項式」と呼ばれる特別な方程式によって管理されます。トリオがこれらの多項式でコンピューター実験を行ったとき、彼らは方程式が隠れた構造を持っているように見えることを発見しました:彼らの解は常に (複素数ではなく) 実数であり、驚くべきことに、これらの多項式を一緒に追加すると常に新しい同じ性質を持つ多項式。 「これらの多項式は、私たちが信用した以上のことをしていました」とマーカスは言いました。 「知識を伝達する方法としてそれらを使用しましたが、実際には多項式自体が知識を含んでいるように見えました。」
研究者たちは、この根底にある構造を捉えるために、いわゆる「インターレース多項式」を扱う新しい手法を少しずつ開発し、最終的に 2013 年 6 月 17 日、マーカスは、ワシントン大学の学部生の顧問だったウィーバーに電子メールを送りました。 10年前の大学。 「私のことを覚えていてほしい」とマーカスは書いている。 「私が書いている理由は、私たちが…あなたの予想を解決したと思うからです（あなたが示したものはKadison-Singerと同等でした）。」数日のうちに、チームの成果に関するニュースがブロゴスフィア全体に広まりました。
それ以来徹底的に精査された証拠は非常に独創的である、とナオールは述べた. 「私が気に入っているのは、まさにこの新鮮な感覚です」と彼は言いました。 「だからこそ、私たちは未解決の問題を解決したいと考えています。以前とはまったく異なる解決策を誰かが思いついたというまれな出来事のために、私たちの視点を完全に変えるだけです。」
コンピューター科学者は、この新しい視点を「非対称」巡回セールスマン問題にすでに適用しています。巡回セールスマン問題では、セールスマンは、移動距離の合計を最小限に抑えることを目標に、一連の都市を移動する必要があります。非対称バージョンには、A から B までの距離が B から A までの距離と異なる状況が含まれます (たとえば、ルートに一方通行が含まれる場合)。
非対称問題の近似解を見つけるための最も有名なアルゴリズムは 1970 年にさかのぼりますが、その近似がどれほど優れているかは誰も知りませんでした。カリフォルニア大学バークレー校の Nima Anari とシアトルのワシントン大学の Shayan Oveis Gharan は、Kadison-Singer 問題の証明からのアイデアを使用して、このアルゴリズムが人々が認識していたよりも指数関数的に優れていることを示しました。 .新しい結果は「大きな、大きな進歩」です、と Naor は言いました。
Kadison-Singer問題の証明は、1ダースの具現化におけるすべての構成が原則として実行できることを意味します.量子知識は完全な量子システムに拡張でき、ネットワークは電気的に類似したものに分解でき、行列は次のように分解できます.より単純なチャンク。この証明は、量子物理学者が行うことを変えるものではありませんが、信号のデジタル化に使用されるベクトルの集合をより高速に処理できる小さなフレームに分解できることを意味するため、信号処理に応用できる可能性があります。この定理は「いくつかの重要な工学的問題に影響を与える可能性があります」と Casazza 氏は述べています。
しかし、原則と実践の間には大きな隔たりがあります。証明は、これらのさまざまな構造が存在することを立証しますが、それらを実行する方法については述べていません。現時点では、Casazza 氏は、証明から有用なアルゴリズムを引き出す「可能性はまったくありません」と述べています。しかし、数学者はこの問題に肯定的な答えがあることを知ったので、彼は建設的な証明がすぐに出てくることを望んでいます — 彼の分野の数学者が実際に理解できる証明は言うまでもありません. 「私たちは皆、それが否定的な答えであると完全に確信していたので、実際にそれを証明しようとした人はいませんでした」と彼は言いました.
Kadison-Singer 問題が顕著であった分野の数学者は、3 人の部外者が参加して「彼らの」中心的な問題を解決したことを懐かしく思うかもしれませんが、それは実際に起こったことではない、と Marcus は言いました。 「私たちがそのような問題を解決しようとすることさえできた唯一の理由は、その分野の人々がC*代数で起こっていたすべての困難をすでに取り除いていたからです」と彼は言いました. 「残ったピースは 1 つだけでした。そのピースは、彼らが解決する技術を持っていた問題ではありませんでした。この問題が 50 年も続いた理由は、本当に 2 つの困難な部分があったからだと思います。」
Kadison-Singer 問題に取り組んでいた 5 年間を通して、Marcus は次のように述べています。彼、Srivastava と Spielman がそれを解くことができたという事実は、「私が望む数学の未来について何かを物語っています」と彼は言いました。数学者が分野を超えてアイデアを取り入れるとき、「知識の中でこれらの本当に興味深い飛躍が起こると私は思う」
