無限小を用いた記述を標準的な記述に還元することについて

これはMath Advent Calendar 2017の12/8の記事です: mathAdventCalendar2017 (←リンク先PDF)

改訂情報

  • 2017/12/09: 式(24), 式(26)の脱字と誤字を訂正しました.(@waidotto 様,ありがとうございました.)

 

広告

cos(x)+sin(x√2)の「周期っぽい長さ」を作る方法

{f(x) := \cos(x)+\sin(\sqrt{2}x)}とすると,これは明らかに周期関数ではないが,「周期っぽい長さ」が存在する.ある{l_\varepsilon}{f(x)}の「{\varepsilon}精度で周期っぽい長さ」であるということを次の条件で定義しよう:

\displaystyle{\sup_{x\in\Bbb{R}}\lvert f(x) - f(x+l_\varepsilon) \rvert < \varepsilon.}

このような「周期っぽい長さ」を機械的に作ってみよう.{\cos(x)}は周期{2\pi}で,{\sin(\sqrt{2}x)}は周期{\sqrt{2}\pi}なので
{\cos(x+l_\varepsilon) \fallingdotseq \cos(x),}
{\sin(\sqrt{2}x + \sqrt{2}l_\varepsilon) \fallingdotseq \sin(\sqrt{2}x).}
であればよい.よって
{l_\varepsilon \fallingdotseq 0\enskip(\mod 2\pi),\enskip l_\varepsilon \fallingdotseq 0\enskip(\mod \sqrt{2}\pi).}
そこである{a,b\in\Bbb{Z}}があって
{l_\varepsilon \fallingdotseq 2a\pi \fallingdotseq \sqrt{2}b\pi}
となっていれば良いことになる.

補足:近似({\fallingdotseq})による「アバウトな」議論がうまく行く事は,{\cos(x)}{\sin(\sqrt{2}x)}{\Bbb{R}}上一様連続であることを使えばうまく説明できる.

このような整数{a,b}を上手く見つけるために{\Bbb{Z}[\sqrt{2}]}が積について閉じていることに注目する.また,{0 < \sqrt{2}-1 < 1}という不等式にも注目する.よく知られているように,絶対値が{1}より小さい数のべき乗はゼロに収束する.そこで例えば
{(\sqrt{2}-1)^{2n} = b_n - \sqrt{2}a_n}
としてやれば,{2a_n \fallingdotseq \sqrt{2}b_n}となるような整数{a_n,\,b_n}を作り出すことができるはずである.{(\sqrt{2}-1)^{2n}}の二項展開を利用して具体形を求めれば

\displaystyle{a_n = \sum_{k=1}^n \binom{2n}{2k-1}2^{k-1},}

\displaystyle{b_n = \sum_{k=1}^n \binom{2n}{2k} 2^k.}

となる.

Maybeの(>=>)を使って問題を解く

■マーティン・ガードナーのパズル本を見ていたらこんな問題が載っていた:

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、1つ余ったので、彼はそれを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。やはりココナツは1つ余り、それは猿のものになった。こうして5人の男たちが順番に同じことをした。つまり1人ずつ目を覚ましては、ココナツの山を5つに分けて、残った1つを猿にあげて、自分の取り分を画した。朝になり、残ったココナツ全部を分けると、今度はきれいに5等分された。
(略) さて、最初にココナツはいくつあったのだろうか?

計算機で総当りしてももちろんこの問題は解ける。本には、これを少ない労力で解くためのトリックが紹介されていた。(「ガードナーの数学娯楽」/日本評論社)。そのトリックについてはこの記事では触れない。

この問題を見たとき、HaskellのMaybeモナドを使ったら素直に解けそうだと感じた。(そして実際に解けた)。ココナツの数をNとすると
N = 5A +1 ;  4A個の山を残す # 1人目の男
4A = 5B + 1 ; 4B個の山を残す # 2人目の男
4B = 5C + 1 ; 4C個の山を残す # 3人目の男
4C = 5D + 1 ; 4D個の山を残す # 4人目の男
4D = 5E +1 ; 4E個の山を残す # 5人目の男
4E = 5F ; きれいに5等分された
のようになる。「与えられた数から1を引いておけば5で割り切れる」という状況が続き、そうして得られた商の4倍だけ残すという操作が5回行われている。そこでこんな関数を考えてみよう:

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

こうすると、それぞれの男が行った操作は g 1 として表現できる:

g 1 :: Int -> Maybe Int

一般に、モナドMに対して X -> M Yの形の関数は、(>=>)で合成できるのだった。
(この記事では説明しないし、知っている必要もないが、この形の関数はこのモナドの与えるKleisli圏の射とみなす事ができ、(>=>)はこのタイプの射の「合成」とみなせるのだった)。

よって、5人の男がココナツに対して行った操作とその結果は

f :: Int -> Maybe Int
f = g 1 {- 1人目の男 -} >=> g 1{- 2人目の男 -} >=> g 1{- 3人目の男 -} >=> g 1{- 4人目の男 -} >=> g 1{- 5人目の男 -} >=> g 0

として表せる。もちろんこれはもっとコンパクトに

f = foldl1 (>=>) [g 1, g 1, g 1, g 1, g 1, g 0]

と書いてもいいし、さらにこれは

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

と書いてもいい。こうして得られたfInt -> Maybe Int という型シグネチャを持つ。元のクイズの答をNとするとき、 f N Just ...という形をしているはずである。そこで、こんな関数を用意してみよう:

--  f の答がNothing ではない場合の引数を得るように変形する
getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

この関数を使えば、問題のNは map (getJustArg f) [1 ..] の最初の元から得られることがわかる。Data.List の

find :: (a -> Bool) -> [a] -> Maybe a

を使えば最初の元を取ってこられそうだ。findMaybeをかぶせて返してくるおかげで、
find isJust (map (getJustArg f) [1 ..])Maybe(Maybe Int) 値になる。そこで join してMaybe を一段に落としてやると、得られる答は Just n の形をしているので fromJustInt値を引っ張り出せる:

fromJust . join $ find isJust (map (getJustArg f) [1 ..])

以上をまとめると次のようなプログラムが得られる:

import Control.Monad
import Data.List
import Data.Maybe

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

main = do{
  print $ fromJust . join $ find isJust (map (getJustArg f) [1 ..])
  }

答は3121となる。

■まとめ
Maybeモナドに対するKleisli射の合成演算(>=>)を用いてクイズを解いてみた。

■おまけの問題

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、4つ余ったので、彼は余ったココナツを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。今度は3つ余ったので、彼はやはり余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
三番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は2つ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
四番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は1つだけ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
五番目の男も同じことを考えたが、彼だけは仲間を裏切ることを恥ずかしく思い、結局何もしなかった。
朝になり、残ったココナツ全部を分けると、きれいに5等分された。
さて、最初にココナツはいくつあったのだろうか?

最小の答は3089個になるはずである。

C90: 「簡約!? λカ娘 9」 が出ます

C90の三日目(2016/08/14(日))に、サークル「参照透明な海を守る会」から『簡約!? λカ娘 9』が出ます。場所は「西地区f32a」です。

<簡約!? λカ娘 9> 内容紹介
第 1 章 λカ娘探索ファイナル (@ark_golgo)
第 2 章 変態する昆虫の観察 (@master_q)
第 3 章 IST(Internal Set Theory) 入門 (前編) (@dif_engine)

第 3 章の『 IST(Internal Set Theory) 入門 (前編) 』が私の記事です。

以下、いくつかの記事について簡単な紹介をします。自分が書いた記事以外はどれも「ちゃんと理解できていない」ので、自分の理解の程度に応じた紹介となります。ご了承ください。

第1章 λカ娘探索ファイナル
AlphaGo が凄いということはみなさんもご存知かと思いますが、では一体どこがどのように凄いのでしょうか?この記事ではコンピュータ囲碁の研究をしている荒木さんによって、コンピュータ囲碁の歴史とAlphaGoの強さの本質、そして将来のコンピュータ囲碁の展望が語られています。

第2章 変態する昆虫の観察
組み込み系のChibiOS/RT というOSは独自の(非POSIXの)スレッド機構を持ち、グローバルロック状態に応じて呼び出せるシステムAPIが変わるのだそうです。間違ったシステムAPIの呼び出しは未定義の挙動を引き起こすのですが、このたぐいのコーディングミスは実行時ではなく、コンパイル時にわかってほしいものです。そのための方法の一つはプログラムの静的なチェックを強化することです。岡部さんの方針は、この静的なチェックのためにATSを使うというものです。(この場合、ATSは最終的にC言語のソースコードを生成します。)

第3章 IST(Internal Set Theory) 入門 (前編)
Edward Nelson によって創始された超準集合論であるInternal Set Theory (以下、IST)という理論があります。
「ふつうの」超準解析、例えば齋藤正彦やM・デービスや中村徹の超準解析の本では、通常の集合論宇宙の超積を使って超準宇宙を作ります。
これに対し、NelsonによるISTにおいては、通常の集合論宇宙が超準宇宙に該当します。この宇宙の中に、一種のミニチュア宇宙が存在し、そこには空集合からスタートして集合論公理を有限回使って到達できるもの全てが含まれています。ISTでは、その意味で超準化という手続きは「すでに終わっている」ので超準宇宙の構成の議論は必要ありません。また、ISTはZFCの保存拡張になっているため、ZFC集合論での全ての定理はISTの定理でもあります。
(超積による超準宇宙の構成では正則性公理(基礎の公理)が省かれることがあります。したがって、ZFC集合論における議論を修正しないとZFC宇宙における定理を超準宇宙に輸入できないことがあります。)

このように言うとISTには良いことしかないようですが、NelsonのIST論文は若干読みにくいところがあります。それは、(1)読者に数理論理学の基礎的教養を要求している (2)ZFCにおける有限性のやや深い理解を要求している ところから来ているのではないかと思います。

(1)に関して言えば、ISTの公理図式は、量化子を「St付き」に変更するような操作を要求しており、論理式をオブジェクトとみなす視点が必要です。(2)に関して言えば、”直観的には”無限集合にしかなり得ない巨大な集合が有限集合であることがISTでは示されたりします。そして、そのようなことがISTにおける議論において有効に利用されたりする場面があります。このため、ISTを学ぶ人は「有限性とはなんだったのか」と悩むことになるでしょう。ISTにおける「有限性」の奇妙さに関連して、Nelson自身は次のような言葉を残しています:

—Perhaps it is fair to say that “finite” does not mean what we have always thought it to mean. What have we always thought it to mean?
I used to think that I knew what I had always thought it to mean, but I no longer think so. In any case, intuition changes with experience.

(1)も(2)もそれぞれ数理論理学と公理的集合論の基本的な教科書を読めば済む話なのですが、なかなか大変です(大変でした)。この章を読みこなせばNelsonによるISTの論文を読むための最低限の知識が得られる、そんな線を狙って執筆しました。なお、この(1)(2)を丁寧に説明しすぎて、肝心のISTの解説には入ることができなかったので「前編」とさせて頂きました。(後編は来年の予定です)。

表紙
久しぶりに表紙絵を描きました。「このすば」のめぐみんの衣装を着たイカ娘です。

簡約!? λカ娘 9 表紙

簡約!? λカ娘 9 表紙

atan2の引数順序をすぐ思い出すための恒等式

二次元直交座標系から極座標系に変換する際に、あるいは「ほとんど同じ話」ですが{x+iy} という形式の複素数を極形式に変換する際に二つの与えられた実数からある角度を得たい場合があります。そのような場合に便利なのが atan2 であることはご存知と思います。私はこの関数の引数の順序を数年に一度はネットで調べてる気がします:こういうのは全く無駄な時間です。

そこで、少し落ち着いて考え、次の恒等式を覚えておけばもう迷わなくなりそうだと思ったのでメモしておきます:

{\theta=\mathrm{atan2}(\sin(\theta), \cos(\theta))\quad(\theta \in [0,2\pi)).}

C88: 「簡約!? λカ娘 8」 が出ます

C88の三日目(2015/08/16(日))に、サークル「パスティヤージュλカ研究学院」から『簡約!? λカ娘 8』が出ます。場所は「東地区 O-47a」です。サークル名(旧名:参照透明な海を守る会)は変わりましたがよろしくおねがいいたします。

<簡約!? λカ娘 8> 内容紹介
第1章 エルエフ島漂流記(@master_q)
第2章 二重否定と継続(@nushio)
第3章 真の名を~データ設計とAlloy~(@osiire)
第4章 Lagrangeの未定乗数法(@dif_engine)  ←私の記事です

第四章の『Lagrangeの未定乗数法』が私の記事です。もはや関数プログラミングとか関係なく、純粋に数学の話になってしまいました。表題の通りLagrangeの未定乗数法についての記事です。数学の応用の場面で未定乗数法は頻繁に使われるのですが、制約条件が増えた場合についての未定乗数法がどうしてうまくいくのかよくわからなかったので勉強して整理してみました。内容は高度なものではありませんが、多変数の微積分に関する話なのでそのへんの復習とか整理だとかそんな話を述べながらゆったりと説明しています。

以下、いくつかの記事について簡単な紹介をします。自分が書いた記事以外はどれも「ちゃんと理解できていない」ので、自分の理解の程度に応じた紹介となります。ご了承ください。

第1章 エルエフ島漂流記
ATS/LFという、ATSのサブシステムがあります。これについての入門記事です。(ATSについてはhttp://jats-ug.metasepi.org/ を御覧ください。)

第2章 二重否定と継続
継続という、わかりづらいことで有名な概念があります。この継続がカリー・ハワード対応を通して二重否定と結びついているという話です。

第3章 真の名を~データ設計とAlloy~
現実世界を模倣したシステムを作るとき、大抵は大幅に単純化・抽象化を行います。そのようにして導入した抽象化が適切か?というのは重要です。多重度、依存性、一意性、など考慮すべき制約条件をきちんと記述できたかどうかを検証するツールとして Alloy Analyzer を使う方法が解説されています。

第4章 Lagrangeの未定乗数法
魔理沙がパチュリーに未定乗数法を教わります。線形代数の復習を行い、陰関数の定理を利用してLagrangeの未定乗数法の証明を追います。最後に、陰関数定理の証明を眺めます。

表紙
前回(簡約λカ娘~巻の七~)に引き続いてうさ叉吉様に絵をお願いいたしました。

行列式を行列のべき乗のトレースたちの多項式として表すこと

物理の本を読んでいたら、{3\times 3} 行列についての次のような公式が出てきた:
{3!|A| = (\mathrm{tr}A)^3 - 3\mathrm{tr}(A^2)\mathrm{tr}(A) + 2\mathrm{tr}(A^3).  }
気になってネットで調べると,{2\times 2} 行列のとき、次の関係式が成り立つのだそうだ:
{2!|A| = (\mathrm{tr}A)^2 - \mathrm{tr}(A^2).}
一般の{n} の場合はどうなるのか気になって考えた.

一般に,{n} 次正方行列 {A} は(適当に取った)ユニタリ行列 {U} によって,対角成分が {A} の固有値であるような上三角行列に変換できる:
{U^*AU = \left[      \begin{array}{ccc}        \lambda_1 & {} & * \\        {} & \ddots & {} \\       0 & {} & \lambda_n      \end{array}    \right].}
ユニタリ行列の性質から,任意の自然数 {k} に対して
{U^*A^kU = \left[      \begin{array}{ccc}        \lambda_1^k & {} & * \\        {} & \ddots & {} \\       0 & {} & \lambda_n^k      \end{array}    \right].}
固有多項式はユニタリ変換で不変なので,その {n-1} 次の項を比較することで次を得る:
{\mathrm{tr}(A^k) = \mathrm{tr}(U^*A^kU) = \lambda_1^k + \cdots+ \lambda_n^k.}
よって,行列のべき乗のトレースが固有値のニュートン多項式になっていることがわかる.ここで, {n} 変数の {k} 次ニュートン多項式 {S_k(x_1,...,x_n) := x_1^k + ... + x_n^k.}

さて, {n} 変数の {k} 次基本対称式 {B_k(x_1,...,x_n)} は次のように定義されるのだった:
{B_k(x_1,...,x_n) :=\sum_{1 \le j_1 < ...< j_k \le n} x_{j_1}\cdot ... \cdot x_{j_k}.}

特に,{B_n(\lambda_1, ..., \lambda_n) = |A|} となることに注意する.行列式もトレースも,ユニタリ変換で上三角化した行列の対角成分だけで決まる.このことから「行列式を行列のべき乗のトレースたちの関数として表す問題」は「{B_n}{S_1, ..., S_n} たちの関数として表す問題」に帰着できることがわかる.

基本対称式とニュートン多項式の間には次のような関係式が成り立つ:
{B_{k+1} = \frac{1}{k+1} \left\{  \left( \sum_{0\le s < k} B_{k-s} S_{s+1} \right) + (-1)^k S_{k+1} \right\}.} ただし {k=0, ..., n-1.}

順番に具体的な式を幾つか書いてみると:
{B_1=S_1.}

{B_2=\frac{1}{2}(B_1S_1 - S_2).}

{B_3 = \frac{1}{3}(B_2S_1 - B_1S_2 + S_3).}

最初の式を2番目の式に,最初と2番目の式を三番目に代入すると次のような式を得る:

{B_2=\frac{1}{2!}(S_1^2 - S_2).}

{B_3 = \frac{1}{3!}(S_1^3 - 3S_1S_2 + 2S_3 ).}

これらの式は最初に紹介した式と強く結びついていることがわかる.これ以上手計算でやるのは面倒なのでMaximaに続きをやらせることにしたいが,Maximaで関数の定義を書くのが面倒になったので次のようなHaskellの使い捨てコードを書いてみた:

(++#) :: String -> String -> String
(++#) a [] = a
(++#) a b = a ++ "," ++ b

sn :: Int -> String
sn n = "(" ++ foldr (++#) "" [ "S"++show k | k <- [1 .. n]] ++ ")"

f :: Int -> IO ()
f k =
	let out = 
		"B" ++ (show (k+1)) ++ sn(k+1) 
		++ ":=(1/" ++ (show (k+1)) ++ ")*("
		++ foldr (++) "" [ "(-1)^" ++ show t 
		++ "*B" ++ show(k-t) ++ sn(k-t) 
		++ "*S" ++ show(t+1) ++ "+" | t <- [0 .. k-1]]
		++ "(-1)^" ++ show k ++ "*S" ++ show(k+1) ++ ");"
	in putStrLn out
$ ghci
Prelude>:l a.hs
[1 of 1] Compiling Main             ( a.hs, interpreted )
Ok, modules loaded: Main.
*Main>  mapM_ f [0 .. 10]
B1(S1):=(1/1)*((-1)^0*S1);
B2(S1,S2):=(1/2)*((-1)^0*B1(S1)*S1+(-1)^1*S2);
B3(S1,S2,S3):=(1/3)*((-1)^0*B2(S1,S2)*S1+(-1)^1*B1(S1)*S2+(-1)^2*S3);
B4(S1,S2,S3,S4):=(1/4)*((-1)^0*B3(S1,S2,S3)*S1+(-1)^1*B2(S1,S2)*S2+(-1)^2*B1(S1)*S3+(-1)^3*S4);
B5(S1,S2,S3,S4,S5):=(1/5)*((-1)^0*B4(S1,S2,S3,S4)*S1+(-1)^1*B3(S1,S2,S3)*S2+(-1)^2*B2(S1,S2)*S3+(-1)^3*B1(S1)*S4+(-1)^4*S5);
B6(S1,S2,S3,S4,S5,S6):=(1/6)*((-1)^0*B5(S1,S2,S3,S4,S5)*S1+(-1)^1*B4(S1,S2,S3,S4)*S2+(-1)^2*B3(S1,S2,S3)*S3+(-1)^3*B2(S1,S2)*S4+(-1)^4*B1(S1)*S5+(-1)^5*S6);
B7(S1,S2,S3,S4,S5,S6,S7):=(1/7)*((-1)^0*B6(S1,S2,S3,S4,S5,S6)*S1+(-1)^1*B5(S1,S2,S3,S4,S5)*S2+(-1)^2*B4(S1,S2,S3,S4)*S3+(-1)^3*B3(S1,S2,S3)*S4+(-1)^4*B2(S1,S2)*S5+(-1)^5*B1(S1)*S6+(-1)^6*S7);
B8(S1,S2,S3,S4,S5,S6,S7,S8):=(1/8)*((-1)^0*B7(S1,S2,S3,S4,S5,S6,S7)*S1+(-1)^1*B6(S1,S2,S3,S4,S5,S6)*S2+(-1)^2*B5(S1,S2,S3,S4,S5)*S3+(-1)^3*B4(S1,S2,S3,S4)*S4+(-1)^4*B3(S1,S2,S3)*S5+(-1)^5*B2(S1,S2)*S6+(-1)^6*B1(S1)*S7+(-1)^7*S8);
B9(S1,S2,S3,S4,S5,S6,S7,S8,S9):=(1/9)*((-1)^0*B8(S1,S2,S3,S4,S5,S6,S7,S8)*S1+(-1)^1*B7(S1,S2,S3,S4,S5,S6,S7)*S2+(-1)^2*B6(S1,S2,S3,S4,S5,S6)*S3+(-1)^3*B5(S1,S2,S3,S4,S5)*S4+(-1)^4*B4(S1,S2,S3,S4)*S5+(-1)^5*B3(S1,S2,S3)*S6+(-1)^6*B2(S1,S2)*S7+(-1)^7*B1(S1)*S8+(-1)^8*S9);
B10(S1,S2,S3,S4,S5,S6,S7,S8,S9,S10):=(1/10)*((-1)^0*B9(S1,S2,S3,S4,S5,S6,S7,S8,S9)*S1+(-1)^1*B8(S1,S2,S3,S4,S5,S6,S7,S8)*S2+(-1)^2*B7(S1,S2,S3,S4,S5,S6,S7)*S3+(-1)^3*B6(S1,S2,S3,S4,S5,S6)*S4+(-1)^4*B5(S1,S2,S3,S4,S5)*S5+(-1)^5*B4(S1,S2,S3,S4)*S6+(-1)^6*B3(S1,S2,S3)*S7+(-1)^7*B2(S1,S2)*S8+(-1)^8*B1(S1)*S9+(-1)^9*S10);
B11(S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11):=(1/11)*((-1)^0*B10(S1,S2,S3,S4,S5,S6,S7,S8,S9,S10)*S1+(-1)^1*B9(S1,S2,S3,S4,S5,S6,S7,S8,S9)*S2+(-1)^2*B8(S1,S2,S3,S4,S5,S6,S7,S8)*S3+(-1)^3*B7(S1,S2,S3,S4,S5,S6,S7)*S4+(-1)^4*B6(S1,S2,S3,S4,S5,S6)*S5+(-1)^5*B5(S1,S2,S3,S4,S5)*S6+(-1)^6*B4(S1,S2,S3,S4)*S7+(-1)^7*B3(S1,S2,S3)*S8+(-1)^8*B2(S1,S2)*S9+(-1)^9*B1(S1)*S10+(-1)^10*S11);

これらの式をMaximaにコピペしてやってから例えば

expand(ratsimp( 3! * B3(S1, S2, S3)));

としてやると {2\,S3-3\,S1\,S2+{S1}^{3}} が出てくるので,どうやらうまく行っている様子だ.
同様にして計算すれば,{n} 次正方行列についての {n!\, |A|} は次のように求まる:

{4!\, |A| = -6\,\mathrm{tr}(A^4)+8\,\mathrm{tr}(A)\,\mathrm{tr}(A^3)+3\,{\mathrm{tr}(A^2)}^{2}-6\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^2)+{\mathrm{tr}(A)}^{4}.}

{5!\,|A| = 24\,\mathrm{tr}(A^5)-30\,\mathrm{tr}(A)\,\mathrm{tr}(A^4)-20\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^3)}
{ +20\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^3)+15\,\mathrm{tr}(A)\,{\mathrm{tr}(A^2)}^{2}-10\,{\mathrm{tr}(A)}^{3}\,\mathrm{tr}(A^2)}
{   +{\mathrm{tr}(A)}^{5}.}

{6!\,|A| = -120\,\mathrm{tr}(A^6)+144\,\mathrm{tr}(A)\,\mathrm{tr}(A^5)+90\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^4)}
{    -90\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^4)+40\,{\mathrm{tr}(A^3)}^{2}-120\,\mathrm{tr}(A)\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^3)}
{    +40\,{\mathrm{tr}(A)}^{3}\,\mathrm{tr}(A^3)-15\,{\mathrm{tr}(A^2)}^{3}+45\,{\mathrm{tr}(A)}^{2}\,{\mathrm{tr}(A^2)}^{2}-15\,{\mathrm{tr}(A)}^{4}\,\mathrm{tr}(A^2)+{\mathrm{tr}(A)}^{6}.}

{7!\,|A| = 720\,\mathrm{tr}(A^7)-840\,\mathrm{tr}(A)\,\mathrm{tr}(A^6)-504\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^5)}
{+504\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^5)-420\,\mathrm{tr}(A^3)\,\mathrm{tr}(A^4)+630\,\mathrm{tr}(A)\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^4)}
{-210\,{\mathrm{tr}(A)}^{3}\,\mathrm{tr}(A^4)+280\,\mathrm{tr}(A)\,{\mathrm{tr}(A^3)}^{2}+210\,{\mathrm{tr}(A^2)}^{2}\,\mathrm{tr}(A^3)}
{-420\,{\mathrm{tr}(A)}^{2}\,\mathrm{tr}(A^2)\,\mathrm{tr}(A^3)+70\,{\mathrm{tr}(A)}^{4}\,\mathrm{tr}(A^3)}
{-105\,\mathrm{tr}(A)\,{\mathrm{tr}(A^2)}^{3}+105\,{\mathrm{tr}(A)}^{3}\,{\mathrm{tr}(A^2)}^{2}-21\,{\mathrm{tr}(A)}^{5}\,\mathrm{tr}(A^2)}
{+{\mathrm{tr}(A)}^{7}.}

こうして眺めていても規則性がわからなかったが,WikipediaのExpressing elementary symmetric polynomials in terms of power sumsを見ると,一般項がどのような形になるか書いてある.興味が出てきたら考えてみることにする.

正五角形に付随する角度と黄金比の関係

前回の記事『正角錐の二面角の公式』では、「初等幾何と2次方程式を駆使して、正五角形にまつわる諸量が黄金比 {\phi=\frac{1+\sqrt{5}}{2}} と関連付けられる事」について触れないで話を進める予定だったがそもそも星形大正十二面体まで話が及ばなかったので取り消し線を入れておいた。

この辺の話題は既知として星形大正十二面体の話に進んでも良いのだが、どうやって{\mathrm{cos}(36^\circ)=\mathrm{cos}(\pi/5)}を正確な値として出すかというあたりもそれなりに面白い。この記事ではそのへんのことを丁寧に説明することにする。

さて、多角形の対角線(diagonal)とは、任意の異なる二頂点を結ぶ線分だが、この二頂点が隣接していると辺に一致してしまうので一般には「隣接しない異なる二頂点を結ぶ線分」という風に定義する。対角線と辺をキチンと分けておきたいというのは素朴な気持ちなのだろうが「二頂点が隣接していても良い」としたほうが議論は楽になる場合が多いように思う。必要に応じて、議論の後で対角線と辺が一致する場合を排除すればよい。用語の定義を巡る混乱を避けるためには「広義の(辺を含む)対角線」「狭義の(辺を含まない)対角線」と呼び分ければよいだろう。以下では正五角形の対角線やその長さについて議論をするが、どうしても必要な場合を除いて広義か狭義かは断らない。図と文脈からどちらの意味かわかるはずだからである。

さて、正五角形の内部に対角線を引くと、呪術的な図形としても知られる五芒星が得られる(図1)。図1では、36°の箇所に「・」を、72°の箇所に「・・」を描きいれてある。36°である箇所について納得がいけば、三角形についての基本的な性質(外角定理)から、72°である箇所にも納得が行く。残る問題は、どうやったら図1の「・」の箇所がすべて36°であることを確認できるか、である。

図1:正五角形の対角線が形成する五芒星。関連する角度も図示している。

図1:正五角形の対角線が形成する五芒星。関連する角度も図示している。

やや問題があるが簡単な確認方法は円周角定理を使うものである。図2は、図1における「・」の箇所が36°であることを円周角定理で説明するためのものである。赤い円は正五角形の外接円である。正五角形の辺を弦とする弧は全て同じ長さであり、それらの円周角は等しい。正五角形の内角は108°であることが(簡単な計算で)わかるから、それぞれの角度は(108/3)°=36°であることがわかる。

図2:円周角の定理を使って五芒星内部の角度を説明するための図(その1)。

図2:円周角の定理を使って五芒星内部の角度を説明するための図。

上で「やや問題がある」と書いた。そう書いた理由は、図1における「・」の角度が36°であることを示すのにまるで円周角の定理が必要であるかのような印象を与えかねないからである。これらの角度が36°になることは、図3、図4を使って考えれば理解できる。

図3:図中に黄緑色で示した二等辺三角形の頂角が36°であることを証明するための補助線。

図3:黄緑色の二等辺三角形の頂角が36°であることを証明するための補助線。

図4:図中に黄緑色で示した二等辺三角形の底角が36°であることを証明するための補助線。

図4:黄緑色の二等辺三角形の底角が36°であることを証明するための補助線。

さて、図3のなかに黄緑色に塗った二等辺三角形の各辺の長さの比を求めてみよう。正五角形の一辺の長さを{1}とし、対角線の長さを{\phi}とする。すると、先ほど求めた五芒星の中の角度の情報から、この二等辺三角形と相似な三角形が、今度は長辺を寝かせて横たわっていることがわかる(図5)。「横になった」方の三角形の短辺の長さは{\phi-1}と計算できるが、相似性から{1/\phi}であることもわかる。したがって次の方程式が立つ:

{1/\phi = \phi - 1.}

両辺に{\phi}をかけて2次方程式にすると、解の公式から簡単に{\phi = \frac{1\pm \sqrt{5}}{2}}と求まるが、もちろん正の解{\frac{1+ \sqrt{5}}{2}}が我々の求めるものである。

図5:正五角形の内部に現れる黄金比を計算するための相似三角形の例。

図5:正五角形の内部に現れる黄金比を計算するための相似三角形の例。

この{\frac{1+ \sqrt{5}}{2}}黄金比と呼ばれている。なにか神秘的な性質を持つ数字だと期待する人たちもいるらしい。実際、フィボナッチ数列に関連してこの黄金比が登場するし、数学の色々なところにひょっこりと顔を出すことが知られているので、まったくつまらない数字というわけでもないのだが。

さて、ここまでの議論で正五角形に関連して、36°の頂角を持つ二等辺三角形が得られた。余弦定理を使えばこの頂角の余弦を、黄金比を用いて表すことができる。すなわち、{\mathrm{cos}(\pi/5)}を黄金比の有理式で表せる。もちろん、三角関数の加法公式を用いれば{\pi/5}の整数倍の角に対する余弦を求めるのは容易である。

『殺物語』 正誤表

サークル「参照透明な海を守る会」の同人誌「簡約!? λカ娘 Go!」に掲載した私の記事「殺物語」にいつくかの誤記がありました。お詫び申し上げます。

このブログでは表組みが出来ないため、正誤表を画像の形で貼らせて頂きます。

 

『殺物語』正誤表

参照透明な海を守る会「簡約!? λカ娘 Go!」の記事『殺物語』の正誤表


 

簡約!? λカ娘 Go! (C84)

C84の三日目(2013/08/12(月))に、サークル「参照透明な海を守る会」から『簡約!? λカ娘 Go!』が出ます。C82の『簡約!? λカ娘(算)』に引き続き、この本にも記事を書かせて頂きました。元々はこの一つ前のC83(2012年冬)のために用意していた記事ですが、諸事情により期限までに書くことができませんでした。今回の記事は去年の冬のために用意していた原稿に大幅に書き足して完成させたものです。

<簡約!? λカ娘 Go!> 内容紹介
第1章 めたせぴ☆ふぁうんでーしょん
第2章 jhcコピペ
第3章 侵略者と転校生とアイドルとイカが再帰を学ぶそうですよ!
第4章 殺物語  ←私の記事です
第5章 λカ娘探索?
第6章 ロマンティック・パージング
第7章 HaskEll Shaddai

第四章の『殺物語』が私の記事です。ストーリー部分は『簡約!? λカ娘(算)』に書いた『蓮物語』の続編になっていますが、数学やプログラミングの話題に関する部分は、『蓮物語』を読んでいなくても問題なく読めるように書いてあります。

『殺物語』 内容紹介
Haskellや圏論についてある程度理解している「私」が、モナドについて質問しにきた下級生に説明する話です。内容をもう少し具体的に要約すると、圏を導入し、Haskellの圏Haskを導入し、その上でKleisli圏に関連付けてモナドを説明しています。圏論は自然変換のあたりまで説明しています。こう要約すると短い記事になりそうなものだと思えてくるのですが、会話形式で書いたためか予想外にページが増えました(約50ページ)。圏Haskを圏論の議論の動機付けや理由付けとしてとりあげ、圏論を学ぶ際の「例が簡単すぎるか(数学的な前提知識が)高度すぎるかのどちらかになりがち」というハードルをいくらかでも緩和しようと試みています。

想定した読者
C82の『簡約!? λカ娘(算)』に私が書いた『蓮物語』は、数学科の平均的な大学二年生に期待されている程度の理解力を持つ「僕」が、はじめてHaskellと圏論に触れ、Haskellのアプリカティブファンクターの振る舞いを理解しようとする話でした。これはこれで一貫した姿勢で書いたものであり、自分では気に入っています。しかし、わかりにくいという読者も多かったようです。プログラミングという話題そのものが特殊ですから、誰にもわかる、というのはそもそも望むべきではないかもしれませんが、もう少し多くの人に理解してもらえる記事を書きたくなりました。反省してみると『数学科の平均的な大学二年生に期待されている程度の理解力を持つ「僕」』のあたりがハードルを高くしていたらしいので、今回は読者に要求する数学のレベルをやや下げました。そのかわりにHaskellの入門書(具体的には『すごいHaskellたのしく学ぼう!』ぐらいの本)を一冊はなんとなく読んだ、というぐらいのレベルの理解を前提としました。

なんでタイトルがモナドと関係無さそうな『殺物語』なの?
数学やプログラミングとは関係ない理由です。前回の『蓮物語』は、西尾維新の『化物語』の二次創作という体裁になっていました。『化物語』の主人公である阿良々木暦は原作でも数学が得意だという設定なので、『数学ガール』の「僕」の役割を果たすのに丁度良かったのです。タイトルはHaskellから取って『蓮物語』に決めていましたが、Haskellだから蓮、という以外に何か欲しくなり、記事を書いたときに大流行していた(そしてまだ流行している)近未来を舞台にしたサイバーパンクニンジャ活劇小説『ニンジャスレイヤー』の主役を改変した「ハスケルスレイヤー」を登場させました。本家の主人公・ニンジャスレイヤーのメンポ(面頬)に「忍」「殺」と刻まれているのが印象的だったので、ハスケルスレイヤーのメンポには「蓮」「殺」と刻まれていることにしました。『蓮物語』では構成上、いきなり出てきていきなり倒されるキャラクターだということもあり、『ニンジャスレイヤー』の主人公そのものを登場させたくはなかったというのも改変キャラにした理由です。というわけで、『蓮物語』の続編であることから、ハスケルスレイヤーのメンポの二文字目「殺」をタイトルに入れました。

☆追記(2013/08/24) 若干の誤記がありました。お詫びと訂正→『殺物語』 正誤表

他の記事について
『簡約!? λカ娘 Go!』は全部で168ページもあります。あまり薄い本じゃない感じですね。執筆者による自記事紹介がすでにいくつかあります:

“簡約!? λカ娘 Go!”の紹介とAjhcプロジェクト近況
簡約!? λカ娘 Go!に「きつねさんでも分かるLR構文解析」書きました

以下、いくつかの記事について簡単な紹介をします。自分が書いた記事以外はどれも「ちゃんと理解できていない」ので、自分の理解の程度に応じた紹介となります。ご了承ください。

第1章 めたせぴ☆ふぁうんでーしょん
あまり有名ではありませんが、jhcというHaskellコンパイラが存在します。著者の @master_q さんはこのコンパイラに非常に強い関心を持ち、UnixライクなフリーOSをHaskellで実装するという野心的なプロジェクトを立ち上げています。野心的、というのは少々の工夫で片付くレベルではないからです。しかしながら、まったく無謀な試みというわけでもないことが、今回の @master_q さんの記事を読めばわかるかもしれません。記事の著者の @master_q さんは組み込み系の仕事をなさっていた方で、デバイスドライバのようなものを書くために必要な kernel ドメインでのプログラミングに強く型付けされた言語を使えないかと数年間考え(過去に @master_q さんが『λカ娘』に書いた記事の全てにこのような問題意識が関わっています)、スナッチ設計というアプローチにたどり着きました。このスナッチ設計が上手く行けば、漸進的にUnixライクなOSをHaskellでリライトでき、めでたく kernel ドメインのプログラミングに強く型付けされた言語を使えるはずです。この記事の議論の詳細を理解するためには低レイヤの部分で何が起こっているかをよく知っている必要があると思います。(というわけで、私には議論の細部を理解することができませんでした。)

タイトルに含まれる「ふぁうんでーしょん」は『銀河帝国興亡史』という通称で親しまれているアイザック・アシモフの有名な未来史のSFシリーズに由来します。『銀河帝国興亡史』は、統計力学と心理学を合わせたような「歴史心理学」を発展させた数学者ハリ・セルダンが銀河帝国の崩壊を予見し、帝国の崩壊後の文明再生の核となる組織「ファウンデーション」を作るところから話が始まります。(型付けが弱い)C言語を基礎としたUnix帝国の崩壊後の、kernelレベルプログラミング再生のための礎を築こうという意気込みが反映されたタイトルです。

第3章 侵略者と転校生とアイドルとイカが再帰を学ぶそうですよ!
リストのように、型そのものが再帰的な構成によって定義される事があります。このような構成を一般化したものとして、再帰スキームというものがあるのだそうです。このような再帰スキームが、たとえば foldr のような再帰関数の高レベルな一般化であることや、再帰スキームを利用して型を定義したときにテストをする方法などが紹介されています。

第4章 殺物語
「——それで翼さん、Haskell のモナドって何でそんなにすごいんですか?」
突然の訪問者は、忍野扇だった。圏論とモナドの解説のあと、忍者が出て殺す!

第5章 λカ娘探索?
囲碁というゲームがありますね。見かけはよく似ている(?)オセロなどと違い、囲碁をコンピュータで解析するのは難しいのだそうです。この記事では囲碁を解析するためになされてきたいくつかの工夫が解説されています。

第6章 ロマンティック・パージング
コンパイラの教科書には LL だとか LR だとか LALR のような術語が登場します。そんなわけで、コンパイラの授業を受けた人はこれらの用語やオートマトンについてよく知っていることが期待されるわけです。現実には、これらの話はなかなか面倒で、ただ本を眺めているだけでは身につきません。(身につきませんでした。)この記事では二人(二匹?)のきつねさんが会話しながらLR構文解析について勉強します。きつねでもわかるのだから人間である自分にもわかるはずだ、そんな希望と期待を抱かせてくれる記事です。

第7章 HaskEll Shaddai
オブジェクト指向プログラミングでは、しばしば個々のオブジェクトの属性を setter/getter 関数で読み書きします。このようなプログラミングスタイルは、オブジェクトが状態を持つ事を前提としています。したがって、参照透明性を基礎とするHaskellで setter/getter のようなものを書くには工夫が必要です。Lensはそのような工夫の一つです。この記事の著者である@fumieval さんのブログ記事『Freeモナドでゲームを作ろう!第2回: 本当に動かす 』でもこのLensについての概観が与えられていますが、『HaskEll Shaddai』ではもう少し深く掘り下げて機能が説明されており、Webスクレイピングのサンプルなどが与えられています。

表紙
今回は、表紙の絵も書かせて頂きました:
pixiv: λカ娘c84表紙絵  簡約!? λカ娘 Go!
表紙絵は裏表ひとつづきになっています。