2018-09-25

最短距離と自由豊穣圏

距離空間は豊穣圏であるという Lawvere の論文(http://www.tac.mta.ca/tac/reprints/articles/1/tr1abs.html)がありますが，それに似た感じで重みつきグラフから自由に生成された豊穣圏を考えると hom-object が最短経路になるらしいことに気付いて面白いと思ったので書いてみます．（よく見たら Lawvere の論文にも書いてありましたが，まあいいでしょう．）

R の monoidal structure

R は非負実数の集合に∞を追加した集合とする．これに普通と逆の順序を入れて圏とみなす．実数の普通の足し算はこの圏でのモノイド積になる（0が単位元）．また，この圏における直和は inf で与えられる．特に始対象は∞である．モノイド積はすべての直和に対して分配律を満たす．

V-graph と重みつきグラフ

V を可算直和をもつモノイド圏で，分配律 $A \otimes \coprod_i B_i \simeq \coprod_i (A \otimes B_i)$ と $\left(\coprod_i A_i\right) \otimes B \simeq \coprod_i (A_i \otimes B)$ が成り立つものとする（Lawvere の論文には詳しい条件が書かれていないけど，後でこれくらい必要になる気がするので最初から仮定しておく）．

V-グラフ $\mathcal A$ は，集合 $\mathcal A_0$ と，各 $u, v \in \mathcal A_0$ に対する対象の割り当て $\mathcal A(u, v) \in V$ からなる．

特に V = R のときを考えると，V-グラフとは非負の重みつき単純有向グラフのことである．逆に非負の重みつき単純有向グラフ G が与えられたとき，辺がないところには重み ∞ の辺があると考えることで G を R-グラフとみなせる．

free V-category と最短距離

V-グラフ $\mathcal A$ に対して，V-category $\widetilde{\mathcal A}$ を対象が $\mathcal A_0$ の要素全体で，hom-objectが $\widetilde{\mathcal A}(u, v) = \coprod_{n \ge 0} \mathcal A^n(u, v)$ となるようなものとする（0は始対象，1はモノイド積の単位元）．ただし
$\mathcal A^0(u, v) = \begin{cases} 0 & u \ne v \\ 1 & u = v, \end{cases} \quad \mathcal A^{n+1}(u, v) = \coprod_{w \in \mathcal A_0} (\mathcal A^n(w, v)\otimes \mathcal A(u, w))$
とする．これは V-category になる（たぶん）．Lawvere によると，この構成は V-Cat から V-graph への忘却関手の左随伴になっているそうだ（いかにもなってそうである）．

重みつきグラフ G を R グラフとみなして上記の構成を行うと， $\widetilde G(u, v)$ は u から v への最短距離になる（ $\otimes$ が足し算で $\coprod$ がinfであることを思い出せばわかる）．

2018-09-23

Z/nZ の分解周りのメモ

$n = q_1 \dots q_k, q_i = p_i^{e_i}$ と書いたとき中国剰余定理として知られる同型 $\mathbb Z / p^n\mathbb Z \simeq \prod_i \mathbb Z / q_i \mathbb Z$ の具体的な与え方が毎回思い出せないのでどこかに書いておきたいと思ってメモ。ついでに単数群の生成元も。

同型

$\mathbb Z / n \mathbb Z \to \prod_i \mathbb Z / q_i \mathbb Z$ は単純にそれぞれの成分に射影すればよい。逆が少しややこしくて，
$\prod_i \mathbb Z / q_i \mathbb Z \ni (x_1, \dots, x_k) \mapsto \sum_i \left(\frac{n}{q_i} \mod q_i\right)^{-1} \cdot \frac{nx_i}{q_i} \mod n \in \mathbb Z / n \mathbb Z$
となる。mod q_i での逆元は互除法を使うか $\phi(q_i) - 1$ 乗すると求まる。

単数群

p が奇素数のときは $(\mathbb Z / p^n \mathbb Z)^{\times}$ は巡回群で，r を mod p での原始根とすると $(p+1)r$ で生成される。他にも生成元はたくさんある。

p = 2 のときは n > 2 なら巡回群ではなく， $(\mathbb Z / 2^n \mathbb Z)^{\times} \simeq \mathbb Z / 2 \mathbb Z \times \mathbb Z / 2^{n-2} \mathbb Z$ となる。右から左への同型は $(x \mod 2, y \mod 2^{n-2}) \mapsto (-1)^x \cdot 3^y$ で与えられる（左辺は乗法群，右辺は加法群なので混乱しないよう注意）。他の同型もたぶんたくさんある。

2018-07-10

Graphillion で半順序の個数を数えてみた話

Graphillion で遊んでみた。

やったこと

有限集合上の半順序の個数を数えてみた(cf. OEIS A001035)。これを効率的に求めるのは未解決問題らしい。ちなみに有限集合上の位相の個数を数える問題とだいたい同じ。

要素数 n を固定して，Graphillion を使って [1..n] 上の半順序をわりと愚直に列挙した。

実行時間は n=6 で 0.3s, n=7 で 8.6s くらい。n=8 になると三時間ぐらい走らせても終わらなかったのでやめた。ちなみに OEIS を見る限り少なくとも n=18 までは既知らしいので，こういうアプローチで新しい値を見つけるのは無理がありそう。

やりかた

a <= b だったら a から b へ辺を伸ばすことにすると，半順序は有向グラフとみなせる。そこで n 点からなる完全グラフの部分グラフで，半順序になっているようなものを列挙すればよい。Graphillion は基本的な集合演算をサポートしているので，基本的には順序の条件をそのまま書くだけでよい。

ただし，Graphillion は無向グラフを扱うライブラリなのに対して，ここでは有向グラフを扱いたい。そこで，source と target を別の点にして有向グラフをむりやり無向グラフで表すことにした。

一応ちゃんと書くと以下のとおり。有向グラフ $(G, E)$ に対して無向グラフ $(G+G', E')$ を $(a, b') \in E' \iff (a, b) \in E$ となるように作る。ただし $G'$ は $G$ のコピーで， $(-)'\colon G \to G'$ が全単射とする。

実際のコードでは，G の点を正の整数，G' の点を負の整数で表した。あと半順序は反射的反対称的推移的関係だけど，対角線部分はあっても情報が増えないので，非対称的推移的関係（strict order; 日本語だと強順序？）にした。こっちのほうが辺の数が減って少し効率がよくなるようだ。

from graphillion import GraphSet

def posets(n):
    univ = [(i, j) for i in range(1, n+1) for j in range(-n, 0)]
    GraphSet.set_universe(univ)
    x = GraphSet({})

    # asymmetry
    for i in range(1, n+1):
        x = x.excluding((i, -i))

    # transitivity
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i != j:
                for k in range(1, n+1):
                    if j != k:
                        y = x.including([(i, -j), (j, -k)]).excluding((i, -k))
                        x = x - y

    return x

import sys
print(len(posets(int(sys.argv[1]))))

実行してみた。

$ time python3 posets.py 6
130023

real	0m0.328s
user	0m0.293s
sys	0m0.028s

$ time python3 posets.py 7
6129859

real	0m8.648s
user	0m8.251s
sys	0m0.324s

出てきた数字は合ってる。

感想とか

ZDD を使うとコンパクトに表現できるかと思ったが，期待したほどコンパクトにはならなかったようだ。ZDD で効率的に表現できるのは基本的には疎な組合せ集合（正確にはちょっと違うと思う）なのだけど，考えてみれば順序全体ってそれほど疎ではないかもしれない。

強引に無向グラフにしてるところにちょっと無駄がある感じはして，Graphillion を使わないで ZDD を自分で操作すればもうちょっと効率よく列挙できそうには思う。

あとは，順序の表現を単に strict order にしたけど，推移律から推論できる辺を除くなどすればもっと辺の数を節約することはできるかもしれない。あるいは，実は BDD のほうがいいとか，(Z)SDD を使うといいとかはあるかもしれない。

2017-12-13

Emacs 上でカーソル位置にある文字の T-Code での入力方法を勝手に表示する

Emacs で日本語を入力するときに T-Code を少し使ってるのですが，ある文字の打ち方を知りたいときにわざわざ 55 って打つのがめんどくさいのでカーソルを合わせたら勝手に表示されるようにしたいとずっと前から定期的に思っていて，今日も思ったので40分くらい調べたらできました。

(defun mylib-show-tc-stroke ()
  (if (and (eq major-mode 'text-mode)
           (not (eq last-command 'skk-insert)))
      (let ((c (char-after)))
        (if (and (integerp c) (< 128 c))
            (tcode-query-stroke (point))))))

(setq mylib-show-tc-stroke-timer
      (run-with-idle-timer 0.2 0.2 'mylib-show-tc-stroke))

関数の中でいろいろ条件つけてるのは適当に書いたのでそんなによくないかも。

あとこれだと勝手にウィンドウが分割されて画面の半分が Help 用のバッファになったりするのであまりスマートでなくて，もうちょっといい感じになったらいいのにと思います。

2017-10-20

関数のオーダーの上の順序と足し算

https://twitter.com/yoshihiro503/status/920979507053412353 から始まってなんか議論になっている感じだったのを見て，ちょっと考えてみた話．要するに，関数のオーダー全体の集合は自然な順序が入って join-semilattice になる．あと足し算もできる（実は join と一致する）．

以下詳細．

$\mathbb{R}_+$ は正の実数全体の集合として， $f: \mathbb{N} \to \mathbb{R}_+$ に対してそのオーダーを
$O(f) = \{g : \mathbb{N} \to \mathbb{R}_+ \mid \exists n_0, \exists c > 0, \forall n \ge n_0, g(n) \le cf(n)\}$
とする．オーダー全体の集合を $\mathbb{O}$ と書くことにする．この集合には包含関係で半順序が入る．

$\mathbb{O}$ は全順序ではない*1が，任意の二元は最小上界をもち，それは $O(f) \vee O(g) = O(\max(f, g)) = O(f+g)$ で与えられる（ $\max(f, g)$ は各点ごとのmax）．

証明: $O(f), O(g) \subseteq O(\max(f,g))$ は明らか．もし $O(f), O(g) \subseteq O(h)$ とすると， $f \le ch$ , $g \le ch$ *2となる $c$ がとれる（この $c$ は共通にとれる）．このとき $\max(f,g) \le ch$ であるから $\max(f,g) \in O(h)$ すなわち $O(\max(f,g)) \subseteq O(h)$ である． $O(\max(f,g)) = O(f+g)$ であることは $\max(f,g) \le f+g \le 2\max(f,g)$ だから明らか．

オーダーの和を $O(f) + O(g) = \{ h \mid \exists h_1 \in O(f), \exists h_2 \in O(g), h = f + g\}$ と定義すると， $O(f) + O(g) = O(f+g)$ が成り立つ．

証明: 左から右への包含関係は明らか．逆にもし $h \in O(f+g)$ ならば，ある $c$ が存在して $h \le c(f+g)$ となる．このとき $h = \frac{f}{f+g}h + \frac{g}{f+g}h$ と分解してやればそれぞれ $\frac{f}{f+g}h \le cf$ , $\frac{g}{f+g}h \le cg$ となるので $h \in O(f) + O(g)$ である．

*1:証明は簡単な演習問題

*2:正確には，有限個を除いてすべて点でこの不等式が成り立つ．以下の不等号も同様．

2017-04-22

真空中を音が伝わる速さ

「真空中を音が伝わる速さはおよそ 340m/s である」という主張は正しいか正しくないかということを，ちょっと前に道を歩いていたらふと気になって考え始めたことがあって，そのことを今日思い出したので記録。

まず大前提として，真空中を音が伝わることはない，という事実があります。これを踏まえたうえでこの文の真偽をあえて考えるとどうなるか，という話です。したがってこの文は，有名な「現在のフランス国王は禿である」と同じタイプの主張を述べたものである，と考えられそうです。*1

大雑把に考えて次の二つの解釈があるでしょう。

(1) 「もし真空中を音が伝わるならば，その速さはおよそ 340m/s である」
(2) 「真空中を音が伝わり，かつその速さはおよそ 340m/s である」

「真空中を音が伝わる速さ」という名詞句の指示対象が存在することを，仮定と読むか主張の一部と読むかの違いです。それぞれの場合の真偽はどうなるかというと，普通に（直観主義論理で）考えて，(1) と読めば真，(2) と読めば偽になるでしょう。

ここに書いたことだけだとフランス国王の場合と何も変わらない気がしますが，まったく同じ構造というわけではないような気もするので，もうちょっと議論の余地があるのかもしれません。

*1:と書いたところで，じゃあこれ以上新しく解説することはないのではと思いましたが，せっかくなのでちょっと書きます

2016-12-31

数学は可能な限り一般的であるべきか

ある論文を読んでいて，「集合 X の部分集合族 K が与えられたとする。このとき〜」と書いてあって，その後には K を用いた概念が定義されているのだけど，その部分を最後まで読んでも何を意図しているかよくわからなかった。もっと先を読んでみると，どうやら定義された概念が論文中で使われるのは X が位相空間で K は X の開基になっている場合だけのようだった。そして，K は開基なのだと思ってもう一度定義を読めば，「何だ，そういうことか」という内容だった。

ということがあって，一般的にできることは常に一般的な形で書くことがよいことなのだろうか，ということを考えた。不要な条件はなんとなく書きたくない，という気持ちになることはよくある。だから，そういう書き方をしたくなるのもわかる。でも，可読性を考えれば不必要な一般性は排除したほうがいいように思う。上の場合だったら，最初から X は位相空間で K はその開基とする，と書いてしまったほうがいい。論理的には必要でなくても，適当な条件が文脈として提供されていれば理解の助けになるというケースはよくある。それだったら，はじめからその条件のもとで議論したほうが，読み手にとってはわかりやすい。