回路代数とグラフ置換モナド

「絵図的手法： 中間整理」を書いた後で、つまり昨日、ダンクソ／ハラーチェバ／ロバーツォンの次の論文を見つけてザッと眺めてみました。

• [DHR20]
• Title: Circuit algebras are wheeled props
• Authors: Zsuzsanna Dancso, Iva Halacheva, Marcy Robertson
• Submitted: 21 Sep 2020
• Pages: 29p
• URL: https://arxiv.org/abs/2009.09738

この論文 [DHR20] は、トポロジー／結び目理論／数理物理学などへの応用を想定して、回路代数〈circuit algebra〉とグラフ置換モナド〈the monad of graph substitution〉を定義しています。車輪付きプロップ〈wheeled prop〉はグラフ置換モナドのアイレンベルク／ムーア代数のことです。

「絵図的手法： 中間整理」で紹介した絵図的手法は、データベースやソフトウェア・システムへの応用を想定しているのですが、使っている道具や発想は [DHR20] とかなり共通しています。おおよそ、次の対応があります。

[DHR20]	絵図的手法
ワイヤリング図	ワイヤリング図〈ワイヤリング複射〉
回路代数	実装、モデル
グラフ	システムスキーマ〈SS〉
グラフ置換モナド	SSモナド

[DHR20] を読みたい人がそうそういるとは思えませんが、僕自身が後でまた読むときのために、概要や注意事項や関連する事や思った事をメモしておきます。図式的手法の観点から語るので、そのバイアスは混じります。$`\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\cat}[1]{\mathcal{#1}}
%\newcommand{\twoto}{\Rightarrow }
\newcommand{\In}{\text{ in } }
%\newcommand{\Imp}{ \Rightarrow }
%\newcommand{\Iff}{\Leftrightarrow }
%\newcommand{\hyp}{\text{－} }
%\newcommand{\op}{\mathrm{op} }
\newcommand{\id}{\mathrm{id} }
%\newcommand{\pto}{ \supseteq\!\to }
%\newcommand{\u}[1]{\underline{#1}}
`$

内容：

スケマティック系とオペラッド

「スケマティック圏： お絵描きできる場所」にて：

スケマティック圏は、単なる（構造付きの）圏ではなく、圏と複圏〈オペラッド〉が一緒になった構造として定義します。よって、これを圏と呼んでいいかは疑問ですが、いちいち「圏類似構造」というのも鬱陶しいので、「圏」という言葉を使います。

スケマティック圏 $`(\cat{C}, \cat{W})`$ は実際“圏ではない”し、主役はワイヤリング・オペラッド $`\cat{W}`$ で、余デカルト圏 $`\cat{C}`$ はオペラッドを作る台〈underlying thing〉として存在します。さすがに「圏」と呼ぶのは不適切だったので、スケマティック系〈schematic system〉に改名します。

スケマティック系 $`\cat{S}`$ に対して、そのワイヤリング・オペラッド〈ワイヤリング複圏〉は $`\cat{W}^\cat{S}`$ と書きます。「オペラッド〈operad〉」と「複圏〈multicategory〉」は完全に同義語として使います。下の表の横方向は同義語です。

オペラッド	複圏
色	対象
色のプロファイル	ソース・プロファイル〈域プロファイル〉
オペレーション	複射
オペラッド結合	複射の結合
恒等オペレーション	恒等複射
	複ホムセット
オペラッドの準同型射	複関手
	複自然変換

オペラッドにおける「色のプロファイル〈profile of colors〉」とは色のリストのことです -- 例えば、ハックニー／ロバーツォン／ヤウ〈Philip Hackney, Marcy Robertson, Donald Yau〉の教科書の2.1.1節に記述があります。

複関手〈multifunctor〉は関手の複圏バージョンで、nLab項目 multifunctor の第二の用法です。複自然変換〈multi-natural transformation〉は自然変換の複圏バージョンです。複自然変換という言い方はみかけなくて、複関手の自然変換〈natural transformation of multifunctors〉と呼ぶようです。用語の統一性・一貫性がないので、検索・調査は大変です。

回路代数

[DHR20] の回路代数〈circuit algebra〉は、とある対称オペラッド〈対称複圏〉の線形表現です。ここでの「線形表現」は「群の線形表現」と言うときの「線形表現」と同じことで、対象にベクトル空間を、オペレーション〈複射〉に線形写像を対応させます。

“とある対称オペラッド”は、スケマティック系 $`{\bf LOA}`$ のワイヤリング・オペラッド $`\cat{W}^{\bf LOA}`$ として書けます。ここで、スケマティック系 $`{\bf LOA}`$ は次のようなものです。

• ワイヤリング図のすべてのポートにラベル〈名前 | インデックス〉が付いている -- Labeled
• ワイヤリング図のすべてのワイヤーに向き〈orientation〉が付いている -- Oriented
• ワイヤリング図のすべてのボックスごとに、ポートに全順序が付いている。-- Anchored

注意事項：

• ここでのラベル付けは、一般的なラベリング（任意の関数）のことではなくて、識別用の名前を付けることです。
• ワイヤーの orientation と direction は同義語です（詳細は後述）。
• ボックスごとにポートに全順序を与えることをアンカリング〈anchoring〉といいました（「テンソルの可視化のための半グラフ」参照）。

対称オペラッド〈対称複圏〉の“表現”は、必ずしも“線形”である必要はありません。対称モノイド圏 $`\cat{M}`$ があると、$`\cat{M}`$ をターゲットとした表現が可能です。オペラッドの表現を「オペラッドの代数〈algebra〉」とも呼びます。一般に、対称オペラッド $`\cat{O}`$ の対称モノイド圏 $`\cat{M}`$ への“表現＝代数”の圏を、

$`\quad \mrm{Alg}_\cat{M}(\cat{O})`$

と書くことにします。代数の圏は、実はとある2-圏のホム圏〈hom category〉のことです。このことを以下に説明します。

[追記]2つのパラメータを構文的にどう配置するかなんてどうでもいいことですが、後の記法との兼ね合いで言うと、次のように書いたほうが良かったかも知れません。

$`\quad \mrm{Alg}_\cat{O}(\cat{M})`$
[/追記]

$`{\bf SymMultiCAT}`$ を次のような2-圏だとします。

• 対象は、大きい（小さくないかも知れない）対称複圏〈対称オペラッド〉
• 射は、対称複圏のあいだの対称複関手〈対称オペラッドの準同型射〉
• 2-射は、対称複関手のあいだの対称複自然変換〈対称複関手のあいだの自然変換〉

$`{\bf SymMultiCAT}`$ は2-圏なので、2つの対象〈対称複圏 | 対称オペラッド〉 $`\cat{O}, \cat{P}`$ に対して、ホムシング〈hom thing〉は圏になります。

$`\quad {\bf SymMultiCAT}(\cat{O}, \cat{P}) \;\in |{\bf CAT}|`$

ところで、対称モノイド圏 $`\cat{M}`$ は、それ自体は対称複圏ではありません。しかし、$`\cat{M}`$ から容易に対称複圏 $`\mrm{Multi}(\cat{M})`$ を作れます。作り方の要点を書けば：

• $`\mrm{Obj}(\mrm{Multi}(\cat{M}) ) := \mrm{Obj}(\cat{M})`$
• $`(\mrm{Multi}(\cat{M}) )( (A_1, \cdots, A_n), B) := \cat{M}( A_1 \otimes \cdots\otimes A_n , B)`$
• $`(\id_A \In \mrm{Multi}(\cat{M})) := (\id_A \In \cat{M})`$

以上の準備のもとで、[DHR20] の回路代数の圏〈category of circuit algebras〉 $`{\bf CircAlg}`$ は次のように書けます。

$`\quad {\bf CircAlg} := {\bf SymMultiCAT}( \cat{W}^\mrm{LOA}, \mrm{Multi}({\bf Vect}_{\mathbb{k}} ) ) \;\in |{\bf CAT}|`$

$`\cat{W}^\mrm{LOA}`$ は先に述べた Labeled-Oriented-Anchored なスケマティック系のワイヤリング・オペラッドです。$`\mathbb{k}`$ はスカラー体で、$`{\bf Vect}_{\mathbb{k}}`$ はベクトル空間の圏です。ベクトル空間の圏は、テンソル積により対称モノイド圏と考えています。場合により、有限次元ベクトル空間の圏 $`{\bf FdVect}_\mathbb{k}`$ に取り替えたほうがいいかも知れません。

回路代数を様々な状況で考えたいなら、スケマティック系と対称モノイド圏をパラメータにした定義がいいでしょう。

$`\quad {\bf CircAlg}_\cat{S}(\cat{M}) := {\bf SymMultiCAT}( \cat{W}^\cat{S}, \mrm{Multi}(\cat{M} ) ) \;\in |{\bf CAT}|`$

例えば、同じワイヤリング・オペラッドを使うとして、線形構造は考えずに集合圏をターゲットにした回路代数（集合圏内の回路代数）ならば、$`{\bf CircAlg}_{\bf LOA}({\bf Set})`$ と書けます。集合圏は直積で対称モノイド圏だと考えます。

グラフ置換モナド

グラフ置換モナド〈graph substitution monad〉については、全体を簡略にはまとめられないので、幾つかのポイントと印象をピックアップして述べます。

[DHR20] では、グラフ置換モナドを定義するために、「グラフ」と呼ぶ組み合わせ構造を使います。[DHR20] のグラフ〈graph〉は有向半グラフ（「テンソルの可視化のための半グラフ」参照）です。[DHR20] のワイヤリング図も有向半グラフなので、ワイヤリング図と（[DHR20] の意味の）グラフは実質的に同じものです。

実質的に同じモノを、わざと異なった呼び名と異なった定義で導入しています。そうしないと、グラフ置換モナドの議論が非常に分かりにくいものになるからです。ここは「そうそう、そうだよね」という気分で読んでました。僕も、ワイヤリング図とほとんど同じ概念を「システムスキーマ」と名付けて別物として扱っています。冒頭でも言いましたが、おおよそ次の対応があります。

ワイヤリング図	ワイヤリング図〈ワイヤリング複射〉
グラフ	システムスキーマ〈SS〉
グラフ置換モナド	SSモナド
車輪付きプロップ	SS代数

車輪付きプロップ〈wheeled prop〉とはグラフ置換モナドのアイレンベルク／ムーア代数です。いったんモナドを作ってしまえば、モナド論のマシナリーにより、アイレンベルク／ムーア圏もクライスリ圏も自動的に作れるわけですが、[DHR20] では次のことを示しています。

• モナドとは無関係に定義される車輪付きプロップは、グラフ置換モナドのアイレンベルク／ムーア代数とみなせる。
• グラフ置換モナドのアイレンベルク／ムーア圏は、回路代数の圏と圏同値である。

“モナドとは無関係に定義される車輪付きプロップ”については、[DHR20] 第6節 "Wheeled props as tensor categories" で述べています。公理的な定義は "6.1. Axiomatic definition" にあります。公理的車輪付きプロップは、キッシンジャーの抽象テンソル系〈abstract tensor system〉と類似性を感じます。

• [Kis13]
• Title: Abstract Tensor Systems as Monoidal Categories
• Author: Aleks Kissinger
• Submitted: 16 Aug 2013
• Pages: 19p
• URL: https://arxiv.org/abs/1308.3586

抽象テンソル系を構文的システムだと考えて、車輪付きプロップが意味論を与えるのかも知れません。

前節の回路代数の定義を見ると、回路代数は関手意味論〈functorial semantics〉／関手モデル〈functorial model〉により定義されています。その回路代数は一方で、モナドのアイレンベルク／ムーア代数としても定義できます。この構図は、ローヴェアの代数セオリー論〈theory of algebraic theories〉を思い起こさせます。

ニューツ〈Nuyts〉のKEML図式〈KEML diagram | ケムル図式〉により、回路代数とグラフ置換モナドの周辺を整理できるかも知れません。

• [Nuy22]
• Title: Understanding Universal Algebra Using Kleisli-Eilenberg-Moore-Lawvere Diagrams (v0.2)
• Author: Andreas Nuyts
• Date: February 21, 2022
• Pages: 35p
• URL: https://anuyts.github.io/files/keml-diagrams.pdf

もうひとつ思い起こすことは、様々な多圏達（あるいは圏類似構造達）の定義方法です。車輪付きプロップがグラフ置換モナドのアイレンベルク／ムーア代数として現れたように、別な圏類似構造が別なモナドのアイレンベルク／ムーア代数として現れる可能性があります。それらの圏類似構造達は、スケマティック系でパラメトライズできる気がします。このテのことは、以下の過去記事とガーナー／フーショウィッツの論文で扱われています。

• 述語論理： 様々な多圏達の分類整理

ガーナー／フーショウィッツの論文：

• [GH15]
• Title: Shapely monads and analytic functors
• Authors: Richard Garner, Tom Hirschowitz
• Submitted: 18 Dec 2015 (v1), 10 Oct 2017 (v3)
• Pages: 52p
• URL: https://arxiv.org/abs/1512.05980

細かいこと

向き

[DHR20] では、ワイヤーの向きを orientation と言っています。direction も少し使われています。これは、ワイヤーを1次元多様体と考えて、それに向き〈orientation〉を考えているからです。1次元の図形では、orientation と direction を区別する必要はありません。

しかし、2次元以上の図形では、その図形〈多様体〉の向き〈orientation〉と、その図形内の曲線やベクトルの向き〈direction〉は異なる概念です。日本語だと、orientation も direction も「向き」なので、どうでもいい話になりますけど。（[追記]いやっ、どうでもよくないことかも。[/追記]）

サークル vs. ループ

[DHR20] では、半グラフの無頂点ループの意味での「サークル〈circle〉」も少数使われていますが、円板〈disc〉の境界である円周〈circle〉と紛らわしいので、次の言い方で無頂点ループを指しています。

• loop with no vertices
• {{free}? {floating}?}! loop

二番目は正規表現ですが、「!」は空語を排除します。展開すれば：

1. free loop
2. floating loop
3. free floating loop

オペラッドの図示に大円板〈big disc〉／小円板〈little disc〉を使うときは、確かに「サークル」は紛らわしい。「無頂点ループ」がいいですかね*1。

幾何的 vs. 組み合わせ的

[DHR20] のワイヤリング図は、完全に組み合わせ的構造だと強調しています。これは、ジョーンズ〈Vaughan F. R. Jones〉の平面タングル〈planar tangle〉と比較してです。平面タングルについては以下の記事で触れています。

• 単純平面タングルとカウフマン図のキャンバス・基準点について
• 平面タングル、空間タングル、ブレイドなんかが“もつれた”話
• モノイド圏上のテンプレート・オペラッド：具体例とソフトウェア的解釈

概念的には完全に組み合わせ的構造であるワイヤリング図ですが、その定義には、一部幾何的・位相的手段を使っています。ハイブリッド方式ですね。その理由は、ワイヤリング図のオペラッド結合を純組み合わせ的に定義するのが頭痛のタネ〈a headache〉だからだそうです。これも「そうそう、そうだよね」。

「不動点なし対合のオペラッド結合」において、ワイヤリング図のオペラッド結合の純組み合わせ的定義を示しましたが、これは無頂点ループを無視しています。無頂点ループが入ると、頭痛がひどくなりそうです。とはいえ、コンピュータで実行可能なアルゴリズムとしてオペラッド結合を書きたいなら、頭痛を我慢して頑張るしかありません。

*1:別などこかで「閉サイクル〈closed cycle〉」を見ましたが、これも混乱を招きそう。