オイラー標数を使って数える話

この記事は 日曜数学 Advent Calendar 2015 の 15 日目の記事です。
(14日目： matsumoring さんによる ring数学店 今年の日曜数学活動 )

---

#追記#
頭に追記します。というか謝罪です。日曜数学 Advent Calendar 2015の序文、tsujimotter 氏の

面白さを読者が共感できるように「自分はなぜそのトピックを面白いと思ったのか」を熱く書いてもらえると嬉しいです。

という目標がで達成できなかった私の後悔が以下です。

今日の反省： 紙面(?)の都合上、簡単な(結論も大して面白くない)事しか書けなかったのが悔しいので、ちょこまか続編を書いていくことにしよう persistent やら sheaf やら morse 理論と絡んでこそなんですよ。euler integral は！！！！ と言いたい

— 有向ホモティッピー (@simizut22) 2015, 12月 15

#問題設定#
まずは非常に簡単な問題から始めます

平面上の各点にセンサーが設置されているとします。各センサーは自分が観測できる位置に何個のものがあるか、という事実だけを認識できたとします。各センサー x にたいし、x が把握する object の数を h(x) で表すことにします。さて、全センサーが認識している範囲には一体何個のものがあるのでしょうか。それを計算するプロトコルはあるのでしょうか??

もしも、各センサーが捉えられる領域が半径 R の円の内部の場合には、

\frac{1}{M} \int_{ \mathbb{R}^2 }h(x)dx

ここで、M は半径 R の円の面積を表します
で与えられることが計算してみるとわかります。計算してみましょう。
観測 object 全体を $\left\{U_{\alpha}\right\}_{\alpha}$とすると、

h = \sum_{\alpha} \boldsymbol{1}_{U_{\alpha}}

が、object の側から考えることで成立します。従って、

\begin{align}
\int_{ \mathbb{R}^2 }h(x) dx &= \int_{ \mathbb{R}^2} \sum_{ \alpha } { 1_{U_{ \alpha } } }dx \\
&= \sum_{ \alpha } \int_{ U_{ \alpha } } dx \\
 &= M \#{\alpha}
\end{align}

例えば、もしもあるセンサーの周りに壁があった場合、上の計算は成り立ちません。この簡単な場合のアイデアを一般化するのには位相的な情報を使います。オイラー標数を用いて積分をしていくことをこれから考えます。

#オイラー標数とは#

オイラー標数という言葉を聞いたことがあるでしょうか。簡単に定義してしまいましょう。
単体複体 $X$ に対して、オイラー標数 $\chi(X)$ を以下で定めます。

\begin{align}
\chi \left(X \right) &= \sum_{\sigma} (-1)^{dim \sigma}  \\
&= \sum_{k=0}^{\infty} \left\{(-1)^k \# \left\{k-単体\right\} \right\}
\end{align}

ちょっと、何言ってるかわからないですね。例を見てみることにします。

X がそれぞれ次の時、オイラー標数は次のようになる：

1. 有限集合 ⇒ $\chi \left( X \right)= \#X$
2. 1点に連続的につぶせる(可縮) ⇒ $\chi \left( X \right) = 1$
3. 有限グラフ(1次元単体複体) ⇒ $\chi \left( X \right) = \#V - \#E$
4. 2 次元単体複体 ⇒ $\chi \left( X \right) = \#V - \#E + \#F$
5. genus g の閉 Riemann 面 ⇒ $\chi \left( X \right) = 2 - 2g$
6. $\mathbb{R}^2 - \left\{Npts\right\} \Rightarrow \chi \left( X \right) = 1 - N$

3, 4 の式は見たことある人も多いのではないでしょうか。

ここで定まったオイラー標数ですが、以下のような大事な性質があります。

$\underline{Prop1}$

\chi \left( A \cup B \right) = \chi \left(A \right) + \chi \left( B \right) - \chi \left( A \cap B \right) 

べん図と言うわけではないですが、面積っぽいと思いませんか??

#euler測度とeuler積分#
Prop1 はオイラー標数が単体複体に対して有限加法的測度になる、ということを表しています。測度に関しての記述は 参考書 [1] などを参考にしてください。
さて、測度があるので、積分できるクラスと言うものを定めます。

$\underline{def}$

CF(X) = \mathbb{Z} \langle \left\{ 1_{\sigma} | \sigma: 単体 \right\} \rangle

すなわち、各単体上でのみ 1 を持つ関数全体で生成されるアーベル群を $CF(X)$ とおきます。この可測関数のクラスを用いてオイラー積分とは
$\underline{def}$

\begin{align}
\int_X d \chi : CF(X) \to \mathbb{Z} \\
\int_X d \chi ( 1_{\sigma} ) =  \chi (\sigma) = (-1)^{dim\sigma}
\end{align}

なる汎関数として定めます。

#元の問題に戻って#
ざっくりしか述べていなかった問題をしっかり定式化して述べましょう。そのうえで、最初のアナロジーがオイラー積分を用いて成立することを示します。

###Setting###

W : target が存在する空間
X: Sensor がある空間
$\left\{ O_{\alpha} \right\}_{\alpha}$ : 観測物の(有限)集合

たとえば、
$W = \mathbb{I}^3$
$X=\mathbb{I}^2 \times \left\{ 1 \right\}$
などを考える
各 target $O_{\alpha}$ の support $U_{\alpha}$ を以下で与える

$U_{\alpha} = \{ x \in X |$ x にあるセンサーが $O_{\alpha}$ を見つける $\}$

$\underline{Problem}$

h : X \to \mathbb{N} : given \\
h(x) = \# \left\{ \alpha \,| \,x \in U_{\alpha} \right\} 

この時、target の個数を h のみから復元できるか？？

$\underline{Theorem}$
もしも $ U_{\alpha}$ : compact かつ $\chi \left( U_{\alpha} \right) = \exists N \left(\forall \alpha \right)$
このとき

\#\alpha = \frac{1}{N} \int_Xh d\chi

$\underline{Proof}$
前と同様。

\begin{align}
\int_Xhd\chi &= \int_X \left( \sum_{\alpha} { 1_{U_{\alpha}}} \right) d\chi \\
&= \sum_{\alpha} \int_{U_{\alpha}} d\chi \\
&=  N \# \alpha
\end{align}

ここで、先ほどと、異なりサポートが同じ形からオイラー標数が等しければよい、という位相的な条件に変わっている。

#今後の発展#

長文になってしまったが、同種の問題で例えば、(条件はあるが)動いている target を euler 積分を用いて数えることも可能であるし、また、$\mathbb{N}-value$ だった counting function を区分線系的にかくちょうすることで、センサーが network の構造を持っているときも target を求めることが可能である。
正直、触りの触りしか述べていないので、何が楽しいかわかりずにくいと思うが、この子はいろいろな数学的対象と絡みあって、愉快なことになる。という注釈を入れておきたい。私の能力不足だ。無念...

#reference#
基本的なリファレンスは以下である

1. Curry, Justin, Robert Ghrist, and Michael Robinson. "Euler calculus with applications to signals and sensing." Proceedings of Symposia in Applied Mathematics. Vol. 70. 2012.
2. Baryshnikov, Yuliy, and Robert Ghrist. "Target enumeration via Euler characteristic integrals." SIAM Journal on Applied Mathematics 70.3 (2009): 825-844.

---

(16日目： KinebuchiTomo さんによる 京大特色入試, コインの問題を解く (その2) )