ホモトピー不変量の計算機による計算

初等的なトポロジーへの計算機の応用としては, まず単体的複体の古典的なホモロジー群を計算機で計算することにより, 様々な情報を取り出す, というものがある。このことをまとめたのが, Kaczynski と Mischaikow と Mrozek の [KMM04] という本である。

Edelsbrunner と Zomorodian は [EZ03] で, linking number を計算するアルゴリズムを述べ, その応用として, 結び目, 特に DNA などの巨大な分子の構造を調べることが書いてある。 Link Floer homology の計算を計算機で行なうという試み [Dro] もある。

単体的複体のホモロジー, コホモロジー, 基本群などの, 基本的なホモトピー不変量を計算するためのアルゴリズムと計算の複雑性については, Joswig の survey [Jos] に簡潔にまとめられている。 そこには他の survey として Vegter の [Veg97] が挙げられている。Lewis と Zomorodian の [LZ] の §1.2 にも別の視点からの文献がまとめられている。

計算機にかけられるアルゴリズムを考えるためには, 良い代数的モデルが必要である。それについては, Rubio と Sergeraert の [RS05] を見るとよい。彼等自身のものと他の2種類のモデルを比較している。 彼等は [RS02] でそのような計算可能なモデルを作ることを constructive algebraic topology と呼んでいる。

• constructive algebraic topology

Segeraert による lecture note では, constructive algebraic topology の解として次の三つが挙げられている。

1. Schön の [Sch91]
2. Sergeraert らによるもの
3. operadic solution

最後のものは, この Sergeraert の lecture が行なわれた summer school で Kadeishvili [Kad] により紹介されている。

Sergeraert は, 実際に Dousson とともに Kenzo という software を開発している。 代数的トポロジーに関係した様々な計算を行なってくれるようである。 最新版では discrete Morse theory も使うようになったらしい。

ホモトピー群については, Kenzo でも計算できるようであるが, Adams spectral sequence に関連して, 計算機を用いる試みが古くからある。古いのは Tangora の [Tan85] であるが, Kochman の [Koc90] もある。

Adams spectral sequence を計算するためには, まずその \(E_{2}\)-term, つまり \(\mathrm{Ext}_{\cA }^{*,*}(\F _{p},\F _{p})\) を計算しなければならないが, それを計算機で行なう試みとして, Isaksen と Wang と Xu の [IWX] では, Bruner の [Bru89; Bru93; Bru], Nassau の website, Wang の program が挙げられている。 Bruner は, 最近では Rognes と共に計算した結果を [BR] として公開している。

スペクトル系列を計算するソフトとして, Ext Chart というものが登場した。Hopkins から Davis のメーリングリストに流れて知った。

別のアプローチもいくつかある。Matousek らの [Čad+] では, simplicial complex の間の homotopy 集合を計算する algorithm が考えられている。 またホモトピー群の計算可能性についてもまとめられている。 例えば, 基本群については, Soare の [Soa04] を見るように書いてある。 最近の [Cad+] では, 単連結な simplicial complex \(Y\) について, \(\pi _k(Y)\) を多項式時間で計算する algorithm について述べている。

Adiprasito, Benedetti, Lutz の [ABL] によると, 可縮かどうか, そして collapsible かどうかについては, Tancer の [Tan] に書かれている。

• 5次元の simplcial complex が 可縮かどうかは algorithmically undecidable
• 3次元の simplicial complex が collapsible かどうかは NP-complete な問題

最近, 有限群のコホモロジーの計算機による計算で, 大きな進歩があったようである。Jon Carlson の解説 [Car05] や 本 [Car+03] を見るとよい。

References

[ABL]

Karim A. Adiprasito, Bruno Benedetti, and Frank H. Lutz. Extremal examples of collapsible complexes and random discrete Morse theory. arXiv: 1404.4239.

[BR]

Robert R. Bruner and John Rognes. The cohomology of the mod 2 Steenrod algebra. arXiv: 2109.13117.

[Bru]

Robert R. Bruner. The Cohomology of the Mod \(2\) Steenrod Algebra: A Computer Calculation. url: http://www.rrb.wayne.edu/papers/cohom.pdf.

[Bru89]

Robert R. Bruner. “Calculation of large Ext modules”. In: Computers in geometry and topology (Chicago, IL, 1986). Vol. 114. Lecture Notes in Pure and Appl. Math. Dekker, New York, 1989, pp. 79–104.

[Bru93]

Robert R. Bruner. “\(\mathrm{Ext}\) in the nineties”. In: Algebraic topology (Oaxtepec, 1991). Vol. 146. Contemp. Math. Amer. Math. Soc., Providence, RI, 1993, pp. 71–90. url: https://doi.org/10.1090/conm/146/01216.

[Cad+]

Martin Cadek, Marek Krcal, Jiri Matousek, Lukas Vokrinek, and Uli Wagner. Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension. arXiv: 1211.3093.

[Čad+]

Martin Čadek et al. Computing all maps into a sphere. arXiv: 1105.6257.

[Car+03]

Jon F. Carlson, Lisa Townsley, Luis Valeri-Elizondo, and Mucheng Zhang. Cohomology rings of finite groups. Vol. 3. Algebra and Applications. With an appendix: Calculations of cohomology rings of groups of order dividing 64 by Carlson, Valeri-Elizondo and Zhang. Kluwer Academic Publishers, Dordrecht, 2003, pp. xvi+776. isbn: 1-4020-1525-9. url: https://doi.org/10.1007/978-94-017-0215-7.

[Car05]

Jon F. Carlson. “Cohomology, computations, and commutative algebra”. In: Notices Amer. Math. Soc. 52.4 (2005), pp. 426–434.

[Dro]

Jean-Marie Droz. Effective computation of knot Floer homology. arXiv: 0803.2379.

[EZ03]

Herbert Edelsbrunner and Afra Zomorodian. “Computing linking numbers of a filtration”. In: Homology Homotopy Appl. 5.2 (2003), 19–37 (electronic).

[IWX]

Daniel C. Isaksen, Guozhen Wang, and Zhouli Xu. Stable homotopy groups of spheres. arXiv: 2001.04247.

[Jos]

Michael Joswig. Computing Invariants of Simplicial Manifolds. arXiv: math/0401176.

[Kad]

Tornike Kadeishvili. Operadic Algebraic Topology. ICTP Map Summer School, 11-29 August 2008, Trieste. url: https://mapcommunity.github.io/ictp/lectures_files/Kadeishvili_L.pdf.

[KMM04]

Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek. Computational homology. Vol. 157. Applied Mathematical Sciences. Springer-Verlag, New York, 2004, pp. xviii+480. isbn: 0-387-40853-3. url: http://dx.doi.org/10.1007/b97315.

[Koc90]

Stanley O. Kochman. Stable homotopy groups of spheres. Vol. 1423. Lecture Notes in Mathematics. A computer-assisted approach. Berlin: Springer-Verlag, 1990, pp. viii+330. isbn: 3-540-52468-1.

[LZ]

Ryan H. Lewis and Afra Zomorodian. Multicore Homology via Mayer Vietoris. arXiv: 1407.2275.

[RS02]

Julio Rubio and Francis Sergeraert. “Constructive algebraic topology”. In: Bull. Sci. Math. 126.5 (2002), pp. 389–412. arXiv: math/0111243. url: http://dx.doi.org/10.1016/S0007-4497(02)01119-3.

[RS05]

Julio Rubio and Francis Sergeraert. “Algebraic models for homotopy types”. In: Homology Homotopy Appl. 7.2 (2005), pp. 139–160. arXiv: math/0311509. url: http://projecteuclid.org/euclid.hha/1139839379.

[Sch91]

Rolf Schön. “Effective algebraic topology”. In: Mem. Amer. Math. Soc. 92.451 (1991), pp. vi+63.

[Soa04]

Robert I. Soare. “Computability theory and differential geometry”. In: Bull. Symbolic Logic 10.4 (2004), pp. 457–486. url: http://dx.doi.org/10.2178/bsl/1102083758.

[Tan]

Martin Tancer. Recognition of collapsible complexes is NP-complete. arXiv: 1211.6254.

[Tan85]

Martin C. Tangora. “Computing the homology of the lambda algebra”. In: Mem. Amer. Math. Soc. 58.337 (1985), pp. v+163. url: http://dx.doi.org/10.1090/memo/0337.

[Veg97]

Gert Vegter. “Computational topology”. In: Handbook of discrete and computational geometry. CRC Press Ser. Discrete Math. Appl. CRC, Boca Raton, FL, 1997, pp. 517–536.