Sage Days 39 in Japan

Sage Days in Japanが九大伊都キャンパスで開催されたので，参加・講演してきました．

Sageは，Mathematica, Maple, Magma, Matlabなどの商用数式処理システム，数値計算システムをフリーソフトで置き換えようという野心的なプロジェクトです．現在，Linux各種ディストリビューション，Apple MacOS X，Microsoft Windows上で動きます．また，iOSデバイス（iPadやiPhone），Androidデバイス上で動くものも開発が進められています．

Sage Daysというのは，Sageの開発，また利用普及をするための集まりで，Sageユーザたちが自発的に行っているものです．これまでの様々な催し（世界各地での）についてはWikiにまとめられています．

初日は，主催者の一人横山さんの基調講演「数式処理システム Sage への誘い / A brief tour of some of Sage's features」から開幕．Sageがどんなものでどんなことができるのか，開発プロジェクトを率いるSteinさんの横顔や，実際にSageを使ってどんな計算が出来るのか，のプレゼンテーションでした．

会場に居る人は殆ど皆，ノートパソコンを持参していたようです（主催者が呼びかけたわけではないのに）．午後は，それぞれのノートパソコンへSageをインストールするところから．

Macの人は，ほぼ苦労なく，ダウンロードしたものをインストールすることが出来たようでした．一方，Windowsの人は少し苦労があったようです．VirtualBoxという，無償で使える仮想化ソフトの上に，LinuxにSageをインストールしたものを導入するのですが，日本語キーボードや日本語フォントの未搭載など，解決すべき点があったようです．主催者の一人の沼田泰英さんが，相方の西山絢太さんとともに，それこそ残像が残るような機敏な動きで会場を走り回り，火消しに当たっておられました．

Windowsパソコンへの導入を回避する方法がもう一つあって，会場で配布されていたMathLibreを使う，と言うものです．こちらで使っていた方もおられました．MathLibreは，数学ソフトウェアをこれでもかというくらいにたくさん（もちろんSageも）導入した，Linuxディストリビューションです．DVD-ROMやUSBメモリに書き込み，それらからパソコンを起動することで，インストールせずに使うことが出来ます．

午後2コマ目は，実際にSageを試してみるというセッションで，主にSageを使うのに必要な，Pythonの実習でした．

Sageは実は，様々な数学ソフトウェアをPythonで束ねた統合ソフトウェアです．なので，使うには最小限のPythonの知識が必要です．

3コマ目は，福岡大学の濱田龍義先生（Knoppix/Math, MathLibreを作っている方）の，「Sage Days 韓国訪問記」でした．実は韓国で一足先に，Sage Daysが開かれていたのでした．また，Sageについての分厚い書籍（韓国語なので読めないですが，大体分かります）が出版されていたりもするそうです．

2日目は，私がSageを改造・改良するための一連の手順についてお話ししました．（プレゼンテーションスライドを下に貼っておきます．このほかに，実際にSageのソースコードを改変したり，改変したものを起動して計算したりのデモを行いました）：

さらに2日目午前の2コマ目は，福岡教育大の藤本光史先生による「タブレット端末上の数式処理システムの現状とその実装」というご講演でした．リナックスの走るザウルス上でのRisa/Asirの実演や，パソコン上での手書き数式認識，また最近のiPadやAndroid端末上での数式処理システムの実装についてのご報告で，実に目を奪われました．

プログラムにあったのは以上ですが，午後は有志で，今回の集まりの反省，今後の，国内で開催するSage Daysについての方針の話し合いなどがもたれました．

会期中・会期後にtwitterでhash tag #SDJ39 付きで呟かれたものは，togetterでまとめを作りました．講演のプレゼンテーションやSageワークシートなどは，全部ではありませんがSage Days in Japan 39のウェブページからたどれます．また，会期中幾つかの講演はUstreamにて中継され，オンラインで視聴しtwitterなどで参加された方も大勢いらっしゃいました．

Live stream videos at Ustream

残雪期の立山

久しぶりに山登り．

5月の連休の立山は，とにかく大変な人出である．地元にいるのだから，時期を外して登る．好天の予報だったので日曜を一日，山に費やす．

立山駅からケーブルカーで美女平へ，そこからバスで，標高2，500mの室堂まで1時間．外に出てみれば文句なしの青空に，まだ雪がたっぷりと残りまばゆい山々である．

慣れた道ながら（道はないのだが），体が重くペースが上がらない．ぜいぜいいいながら，一ノ越までスキーを履いて登る．スキーはそこで脱いで，アイゼンに履き替えてピッケルをつきつつ雄山に登る．

正午頃の山頂では皆くつろいでいる．東面に滑り込む人たち，山崎カールに滑り込む人たち．私もしばし休んで，また上ってきた道を降りた．

一ノ越からはよろよろとスキーで下る．

上の写真は，雄山山頂から見た剱岳．その他は下のスライドショーからどうぞ．

連休終了

連休後半は特に遠出することもなく，日々を消光致しおり候．

ある日は家人の家で7回忌．お寺さん（という言い方も私にはあまりなじみがないのだが）がいらして読経して下さる．いわゆるお経とは違って，読み下し文のようなものを唱和するのである．な～むあみだ～あぶつ～．

そして別の日には，子供の何かの（あまりよく分かっていない）節目で，神社に行きお祓いを受けるのである．お日柄も良く，光あふれる境内に善男善女が集まっており，かしこぎ～かしこぎ～もうしたてまぁつ～る～，という調子である．

無秩序に本をひっくり返す中，ファインマンさんは超天才 (岩波現代文庫)が面白かった．1995年刊行のものが，岩波現代文個で再発売されていたもの．ハンス・ベーテがマーク・カッツによるファインマン評を引いて曰く：

「普通の天才とは，われわれが今の何倍か頭が良ければ，だれでもなれるような人間のことだ．そういった天才なら，その頭脳の働きになんの神秘もありはしない．彼らが何をやったのかを理解さえしてしまえば，われわれにだってきっとできたはずだと確信できる．ところが魔術師の場合はまったく違う．あの連中は数学の言葉で言うなら，われわれのいる空間の直交補空間にいるのだ．……」（マーク・カッツ「偶然の謎」，1985，同書より孫引き）．

ファインマンさんは超天才 (岩波現代文庫)

posted with amazlet at 12.05.07

C.サイクス
岩波書店
売り上げランキング: 195462

Amazon.co.jp で詳細を見る

Cornacchia-Smithのアルゴリズム：mod 4で1の素数は2平方数の和

$4$で割って$1$余る素数$p$を2つの平方数の和と表す（$p=x^2+y^2$）ことの証明をこれまで幾つか見てきた．今回は，$p$が与えられたときに具体的に$x,\,y$を求めるアルゴリズムを紹介する．少し一般化して，奇素数$p$と，$p$で割り切れない正整数$d$が与えられたときに， \[ p = x^2 + dy^2 \] となる$x,\,y$が存在するかを判定し，存在すれば$x,\,y$を与える，Cornacchia-Smithのアルゴリズムを述べる：

入力：奇素数$p$, 正整数$d$で$p$で割り切れないもの．

出力：$p=x^2+dy^2$となる整数$x,\,y$が存在するか否か，存在すれば$x,\,y$を返す．

アルゴリズム：

1. もし$(-d/p) = -1$なら$x,\,y$は存在しない．終了．
2. $x_0\equiv \sqrt{-d}\pmod{p}$とし，$2x_0\lt p$なら$x_0 = p-x_0$と取り直す．
3. $(a, b) = (p, x_0)$, $c = \lfloor\sqrt{p}\rfloor$とする．
4. while $(b > c)$, $(a,b) = (b, a\pmod{b})$.
5. $t = p-b^2$とし，もし$t\not\equiv 0\pmod{p}$または$t/d$が平方でないなら，$x,\,y$は存在しない．終了．そうでないなら，$(\pm b, \pm \sqrt{t/d})$が求める解である．

例えば$p=37$, $d=1$で$37=x^2+y^2$を解いてみよう．$x_0 \equiv \sqrt{-1} \equiv \sqrt{36} = 6\pmod{37}$. $2\cdot 6 =12 < p = 37$より， $x_0=37-6=31$と取り直す．$c=\lfloor \sqrt{37}\rfloor = 6$. すると，4の互除法の過程は$(a,\,b) = (37,\,31) \to (31,\, 6)$となり，$b=6 \leq c = 6$よりこれで終わり．5のステップで，$t=p-b^2 = 37 - 6^2 = 1$. $t/d = 1$は平方であるから，$(\pm 6, \pm 1)$が解である．

2番目のステップで，法$p$で平方根を求める計算があり，これについてもスタンダードなアルゴリズムの他に，色々と工夫があるのだが，別の機会に譲る．

上のCornacchia-Smithのアルゴリズムは，例えばH. Cohen, A Course in Computational Algebraic Number Theory (Graduate Texts in Mathematics)のアルゴリズム1.5.2, またCrandall-Pomerance著, 和田秀男監訳， 素数全書―計算からのアプローチのアルゴリズム2.3.12がこれである．虚2次体の，判別式$D$の整環で，$(D/p)=1$なる素数の上にある素イデアルが単項イデアルかを判定し，そうならその生成元を与える，と定式化し直した（H. Lenstraによる）アルゴリズムが，R. Schoof, Counting points on elliptic curves over finite fields, JTNB, 7, 1995の定理4.1として述べられている．pari-gpではqfbsolve()という函数として実装されている．きわめて高速で，500桁の素数でも一瞬で答えが求まる．以前述べた，Jacobsthal和の計算では高々数十桁ぐらいまでしか計算できないのと対照的である．（後記：クランドール・ポメランスのリンクが間違っていたので訂正．23:20）

one-sentence-proof: mod 4で1の素数は2平方数の和

$4$で割って$1$余る素数$p$を2つの平方数の和と表す問題の証明のうち，おそらくもっとも有名ではないかと思われるのが，D. Zagierによるone-sentence proofである：

「$S = \{(x,y,z)\in\mathbf{N}^3\,|\, x^2+4yz = p\}$とするとき，$S$上のinvolution \[ (x,\,y,\,z) \mapsto \begin{cases} (x+2z, z, y-x-y),\quad \text{ if }x < y-z,\\ (2y-x, y, x-y+z), \quad \text{ if } y-z < x < 2y,\\ (x-2y, x-y+z, y), \quad \text{ if } x > 2y, \end{cases} \] はただ一つの固定点を持ち，よって$S$は奇数個の元からなるが，一方でinvolution \[ (x, y, z) \mapsto (x, z, y) \] も固定点を持つ．」 問題は，何故これで証明されたのかが直ちには了解しづらい点である．

この元になったのが，Heath-Brownによる証明である．まず行列$M$を \[ M = \begin{pmatrix} 0 & 2 & 0\\ 2 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix} \] と定義する．$M$を使って$\mathbf{Z}^3$内の部分集合を， \[ S = \{\mathbf{v} = (x,y,z)^t \in\mathbf{Z}^3\,|\, \mathbf{v}^{t}M\mathbf{v} = p\} \] と定義する．$\mathbf{v}^{t}M\mathbf{v}= 4xy + z^2 = p$である（${}^t$は転置の記号とする）．行列をもう3つ，$A$, $B$, $C$を次のように定義する： \[ A = \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & -1 \end{pmatrix},\quad B = \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix},\quad C = \begin{pmatrix} 1 & -1 & 1\\ 0 & 1 & 0\\ 0 & 2 & -1 \end{pmatrix}. \] $A$, $B$, $C$はいずれも可逆行列で，$A^2 = B^2 = C^2 = I$, さらに$A^tMA = B^tMB = C^tMC = M$. また，$S$の部分集合$T$, $U$を次のように定義する： \[ T = \{(x,y,z)\in S\,|\, z > 0\},\quad U = \{(x,y,z)\in S\,|\, x+z>y\}. \] すると，以下の各主張が成立する：

主張1: $A\colon S\to S$, $B\colon T\to T$, $C\colon U\to U$.

主張2: $S = T \sqcup AT = U \sqcup AU$.

（証明は原論文を）．よって$\# T = \# AT$, $\# U = \# AU$から$\# S = 2\# T = 2\# U$となり，$\# T = \# U$.

主張3: $\# U$は奇数．

証明：$C^2=I$より，$C$の$U$への作用でのそれぞれの軌道は，$1$つ，もしくは$2$つの元しか含まない．軌道が$1$つの元と言うことは，固定点と言うことである．$C(x,y,z)^t = (x,y,z)^t$から，$y=z$が出るが，すると$p=y(4x+y)$となり，よって$y=1$, $x=(p-1)/4$. 従って, $C$の作用での$U$の固定点は唯一で，他の軌道はすべて$2$元からなる．よって$\# U$は奇数である．

すると，$\# T = \# U$も奇数であり，$B$の$T$への作用において奇数個の固定点が存在する．特に$B$の作用での固定点が$T$に存在するが，この固定点は（$B$が$x$と$y$を入れ替えるので）$x=y$. すると \[ p = 4xy + z^2 = 4x^2 + z^2 = (2x)^2+ z^2. \] これが求める結果であった．

参考文献は，上掲のZagier, Heath-Brownの論文の他，Aigner, Ziegler, Proofs from THE BOOKの4章がこの証明（の他に，A. Thueによる別の証明）を詳細に解説している．

モジュラー形式・テータ級数(2)：mod 4で1の素数は2平方数の和

昨日の記事では，$4$で割って$1$余る素数を2つの平方数の和と表す問題から，CM楕円曲線を経由してモジュラー形式に至った．今日はより直接的にモジュラー形式と関連するお話．

まず，指標付きのEisenstein級数$G_{k,\,\chi}(z)$を定義する．$\chi$を法$N$に対するDirichlet指標（群準同型$\chi\colon (\mathbf{Z}/N\mathbf{Z})^\times\to \mathbf{C}^{\times}$を，$(n,N)\neq 1$なら$\chi(n)=0$として$\chi\colon\mathbf{Z}\to\mathbf{C}$へ伸ばしたもの）とする．正整数$k$と$N$, 法$N$のDirichlet指標に対して \[ G_{k,\,\chi}(z) = c_k(\chi) + \sum_{n=1}^{\infty}\left(\sum_{d\mid n}\chi(d)d^{k-1} \right)q^n \] と定義する．但し$\chi(-1)=(-1)^k$を仮定し，また \[ c_k(\chi) = \frac{1}{2}L(1-k,\chi) \] は，Dirichlet指標$\chi$に対するDirichlet $L$函数の$1-k$での値の半分で，これは代数的数になる．すると，$G_{k,\,\chi}(z)$は，重み$k$, レベル$N$, 指標$\chi$を持つモジュラー形式になる．

一方，テータ級数$\theta(z)$を \[ \theta(z) = \sum_{n\in\mathbf{Z}} q^{n^2} = 1 + 2\sum_{n\geq 1}q^{n^2} \] とする．その$2$乗$\theta(z)^2$は，重みが$1$, レベル$4$, 指標$\chi_{-4}(\cdot)=(-4/\cdot)$をもつモジュラー形式になり，整数を二平方数の和に書き表す書き方 \[ r_2(n) = \# \{(x,y)|\, x^2+y^2=n,\, x,\, y\in\mathbf{Z}\} \] と次のような関係があることが分かる： \[ \theta(z)^2 = \left(\sum_{n\in\mathbf{Z}} q^{n^2}\right)\left(\sum_{m\in\mathbf{Z}} q^{m^2}\right) = \sum_{n\geq 0}r_2(n)q^n. \]

さて，重みが$1$, レベル$4$, 指標$\chi_{-4}$をもつモジュラー形式で$q$展開が$0$でない定数項を持つものの全体は複素$1$次元なので，$G_{1, \chi_{-4}}(z)$と$\theta(z)^2$は定数倍で一致する．この定数は$L(0,\chi_{-4})=1/2$から$4$であること（$4G_{1, \chi_{-4}}(z) = \theta(z)^2$）が分かる．よって，$p\equiv1\pmod{4}$なる素数については， \[ r_2(p) = 4(\chi_{-4}(1) + \chi_{-4}(p)) = 8. \] 特にそのような素数は，二平方数の和である事（更に，二平方数和としての表し方が順番と負号の付け方を除いて一意である事）が分かる．

参考文献は，Zagierの1-2-3の論説の§3.1.

モジュラー形式・テータ級数：mod 4で1の素数は2平方数の和

$E\colon y^2=x^3-Dx$のHasse-Weil $L$函数が，Hecke $L$函数に一致すること（Deuring-Weil）を見た．今回は更に，これらがあるモジュラー形式の$L$函数である事を見る．

特に$D=1$, つまり$E\colon y^2=x^3-x$の場合を考えると，対応するHecke指標は，$P$が$2$の上にある素イデアルなら$\chi(P)=0$, それ以外の場合は$\chi(P)=\pi$, $P=(\pi)$, $\pi\equiv 1\pmod{2+2\sqrt{-1}}$, となる．このとき$E$に対応するモジュラー形式は，重み$2$, レベル$32$のテータ級数（CMモジュラー形式） \[ f_E(z) = -\sum_{\mathfrak{a}\subset\mathbf{Z}[\sqrt{-1}]}\chi(\mathfrak{a}) q^{N(\mathfrak{a})} = -\sum_{a,\,b}a q^{a^2+b^2}, \] 但し$q=\exp(2\pi\sqrt{-1}z)$, $\mathfrak{a}$は$\mathbf{Z}[\sqrt{-1}]$の$0$でないイデアルを走り，また$a$, $b$は$a\equiv1\pmod{4}$, $b\equiv0\pmod{2}$を走る．

更に，このモジュラー形式は，$\eta$函数 \[ \eta(z) = q^{1/24}\prod_{n=1}^{\infty}(1-q^n), \] により， \[ f_E(z) = \eta(4z)^2\eta(8z)^2 \] と表示される．（重み2, レベル32のカスプ形式の空間が1次元である事から）．

すると，考えている楕円曲線$E$の$a_p$（$p$は素数）は，$f_E(z))$の$q^p$の係数に等しかったので，最終的に上の式の右辺を$q$展開した係数に等しいことがわかる．Jacobsthal和が，そして$x^2+y^2=p$の解が，上のような無限積の係数と関係付くのは大変ふしぎなことである．

参考文献は，D. Zagier, Elliptic Modular Forms and Their Appliation, in The 1-2-3 of Modular Forms, The 1-2-3 of Modular Forms: Lectures at a Summer School in Nordfjordeid, Norway (Universitext) §6.4, 並びに，橋本喜一朗先生の連載記事「数のジャングル・数論の迷宮」第15回「森の広場（スクエア）：素数たちの饗宴（2）」，数学セミナー 2010年 09月号 [雑誌] ，である．