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

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

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

単体的複体の ホモロジー, コホモロジー, 基本群などの, 基本的なホモトピー不変量を計算するためのアルゴリズムと計算の複雑性については, 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] により紹介されている。

最近では, [MR] のように Rubio と Sergeraert の手法は, effective homology method と呼ばれているようである。

• effective homology method

Sergeraert は, このアイデアを元に Dousson とともに Kenzo という software を開発している。

ホモトピー群については, 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+14b] では, simplicial complex の間の homotopy 集合を計算する algorithm が考えられている。 また ホモトピー群の計算可能性についてもまとめられている。 例えば, 基本群については, Soare の [Soa04] を見るように書いてある。 最近の [Čad+14a] では, 単連結な simplicial complex \(Y\) について, \(\pi _k(Y)\) を多項式時間で計算する algorithm について述べている。

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

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

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

References

[ABL17]

Karim A. Adiprasito, Bruno Benedetti, and Frank H. Lutz. “Extremal examples of collapsible complexes and random discrete Morse theory”. In: Discrete Comput. Geom. 57.4 (2017), pp. 824–853. arXiv: 1404.4239. url: https://doi.org/10.1007/s00454-017-9860-4.

[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.

[Čad+14a]

Martin Čadek, Marek Krčál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner. “Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension”. In: SIAM J. Comput. 43.5 (2014), pp. 1728–1780. arXiv: 1211.3093. url: https://doi.org/10.1137/120899029.

[Čad+14b]

Martin Čadek et al. “Computing all maps into a sphere”. In: J. ACM 61.3 (2014), Art. 17, 44. arXiv: 1105.6257. url: https://doi.org/10.1145/2597629.

[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.

[Dro08]

Jean-Marie Droz. “Effective computation of knot Floer homology”. In: Acta Math. Vietnam. 33.3 (2008), pp. 471–491. 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.

[MR]

Miguel Angel Marco-Buzunariz and Ana Romero. Computing the homology of universal covers via effective homology and discrete vector fields. arXiv: 2409.06357.

[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. url: https://doi.org/10.1090/memo/0451.

[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.