2013年12月29日日曜日

جَيْب (jayb)

From India the sine function was introduced to the Arab world in the 8th century, where the term jya was transliterated into jiba or jyb. Early Latin translations of Arabic mathematical treatises mistook jiba for the Arabic word jaib, which can mean the opening of a woman's garment at the neck. Accordingly, jaib was translated into the Latin sinus, which can mean "fold" (in a garment), "bosom," "bay," or even "curve." Hence our word "sine."

The birth of trigonometry

また新説が。 the opening of a woman's garment at the neck とは女性の服の首回りの開いたところぐらいの意味だろうか。

さて前回の結論としては、アラビア語を調べないと判らない、ということだったので今回はアラビア語。 今まで出てきたどの説もアラビア語は jaib としているが、それらしい単語はむしろ جَيْب (jayb) という形のようだ。 (もちろんアラビア語の transliteration の方式に依るのかもしれないが素直に読めば y に当たる字が入っている)

ここで脱線してアラビア文字について述べておこう(もちろん俄知識である)。 アラビア語の文字は右から左に(主に)子音だけ書くというスタイルで、しかも各文字に語頭、語中、語尾の形があるため、なかなか読みにくい。 今回の単語は ج (jīm) が語頭の形で右側の角張った部分と下の点(ここまでが文字そのもの)と上の´(アの音を表す記号)まで、 次の ي (yā) は語中の形で上に一回持ち上がった部分と下の二つの点(ここまでが文字そのもの)と上の○(母音が付かないことを表す記号)まで、 最後の ب (bā) は語尾の形で二回目に持ち上がった部分から最後まで、と分解される。

話を戻して、この単語の意味であるが、第一義は「胸」のようだ。 たとえば Quran Dictionary - ج ي ب では bosom しか出てこない。 アラビア語検索エンジン アラジン ver.1 では、「胸、胸部」が最初で「穴、くぼみ、空洞」「ポケット」と続き6番目の意味で「[数] サイン」が登場する。

ということで野﨑先生の御説が概ね正しいのだろうと結論づけておく。

2013年12月17日火曜日

sin の語源?

インドの言葉 "jya-ardha" (高さ)が似た発音のアラビア語 "jiba" になり、母音を省いて "jb" のように書く習慣から "jaib" (胸)と混同されてラテン語では "sinus" (胸)に化け、それが今のサイン "sin" のもとだそうです

野﨑昭弘「算数・数学24の真珠」日本評論社 2012

jyā は弦を意味する言葉であり、もともとは半弦を意味する jyā-ardha が使われていたがそれが省略されて jyā が使われるようになったと考えられている。用語 jyā はアラビア語訳されるときにそのまま発音を写して jiba と訳されたが、アラビア語では母音が記されないため jiba と jaib とは同じ綴りとなりいつのまにか「湾」を意味する jaib が使われるようになった。そのためアラビア語の著作がラテン語訳されるときに湾を意味する sinus が使われ、そこから今日の sine が誕生した

上野健爾「円周率が歩んだ道」岩波書店 2013

胸と湾が同じ単語?

sin·us,-ūs m indentation, curve, fold, hollow; fold of toga about the breast, pocket, purse; breast, bosom, lap; bay, gulf, lagoon; winding coast; valley, hollow; heart (e.g., of a city), interior; intimacy

John C. Traupman, Ph.D., The New College Latin and English Dictionary, third edition, Bantam books 2007
両方の意味がちゃんと載っていた。 アラビア語の jaib の意味を調べないとどちらの説が正しいのか(あるいはラテン語同様広い意味をカバーする言葉でどちらも正解か)不明である。

2013年12月15日日曜日

右から割り算

自然数 \(n\) と素数 \(p\) が与えられて、\(n\) が \(p\) で割り切れるかどうか判定したいとしよう。 ふつうは余りを求めて、それが \(0\) だったら割り切れる、それ以外なら割り切れない、と判断する。 しかし、暗算でそんな計算をするとき、思い返してみると右から桁を減らしていくことが多い。 たとえば \(211\) が \(13\) で割り切れないことを確かめようとする場合、1の位の \(1\) を打ち消すために \(91=7\times 13\) を引き、残りが \(120\) だから \(13\) では割り切れない、と思考を進めるわけである。

再帰的にこんな手続き \(f(n, p)\) を定義すればいい。

1. \(n=0\) ならば True を返す。
2. \(n\) が \(10\) で割り切れるならば \(f(n/10, p)\) を返す。
3. \(n\) の1の位と同じ1の位を持つ \(p\) の倍数(のうち最小のもの)を \(kp\) とするとき、\(n\ge kp\) ならば \(f(n - kp, p)\) を返し、\(n< kp\) ならば False を返す。

いくつか注意を述べると、まず \(p\) は \(10\) と互いに素の場合にだけ適用できる。 その \(10\) は \(d\)-進数の \(d\) だと思って良い(プログラムで実現するときは \(2\)-進数で考えることだろう)。 \(kp\) は事前にテーブルを用意しておいて辞書引きすれば良い(というか \(p\) の1の位で \(k\) は決まってしまう)。 特に\(2\)-進数ならば\(k\)は常に\(1\)なので話が簡単である。

他の人、あるいは既存のプログラムで、この方法で割り切れるかどうかの判定を行っている例があるのかどうか知りたいところである。

2013年9月8日日曜日

平方因子の存在

自然数が与えられたとき、その数が平方因子を持つかどうかの判定は、現在のところ、因数分解してみる以上に効率的な方法が知られていない。 べつに因子自身を知る必要が無いということを考えると、因数分解は手間が掛かりすぎという感覚があり、多分これは多くの(計算数論に多少なりとも興味のある)人に喉に刺さった小骨のような苛立ちをもたらしている。 以下に述べることは、問題の解決ではなく、こんなことを考えてみたけどうまくいかんなあ、という記録である。

整数の難しい問題は、一変数多項式に手がかりを求めると良いと言われる。 多項式が平方因子を持つかどうかの判定は簡単で、\((f, f')\) を計算すると平方因子が求まる。 (もちろん \(f'\) は \(f\) を微分したもの、\((,)\) は最小公倍数の記号、である)

例えば \(f(X) = X^3 + 7 X^2 + 8 X - 16\) とすると、 \(f'(X) = 3 X^2 + 14X + 8\) で、 \(f(X)\) と \(f'(X)\) の最小公倍数は \(X+4\)。 よって \(f(X)\) は \(X+4\) で2回割り切れる。

整数には微分が定義されていないので、そのまま使えるわけではないが、類似の現象を探すのが良さそうである。

次の関係に注目してみたい。 「\(n\) が平方因子を持つ正整数ならば、\((n, \varphi(n)) > 1\)」

注意点としては、逆が成り立たないし、\(\varphi(n)\) の計算の手間も因数分解と大体同等だと思われる、という二つがある。 逆が成り立たないことは、\(p_1 | p_2 - 1\) となる \(n\) の素因数の組 \(p_1, p_2\) がある場合にも \((n, \varphi(n)) > 1\) となることを見れば良い。 オイラー関数の計算の手間が因数分解と同等か正確なところは判らないが、RSA 暗号の安全性と関わってそういう議論があったはずだ。

オイラー関数を計算してはいけないという縛りの下に \((n, \varphi(n)) > 1\) の成立を確かめよう、というのが次のタスクになる。 そこでひねり出したのが次の条件である。 \[\exists a \text{ s.t. } a^{n-1}\not\equiv 1 \bmod n \wedge a^{n(n-1)}\equiv 1 \bmod n\] これが \((n, \varphi(n)) > 1\) と同値な条件になっている。 問題は、存在するという \(a\) はどのぐらいの数を調べると見つかるのか、ということである。 それは各素(冪)因子での条件の中国式剰余定理での組み合わせなので、まあだいたい平方になっている素因子ぐらいは最低でも見ないと見つからないはずだ。 結局、そんなに大量に探すなら因数分解した方が早くなってしまう。 少し考えれば \(1\) かどうかにこだわらず \(n-1\) 乗では異なり \(n(n-1)\) 乗では一致する組 \(a, b\) を見つければ良いと判るが、これでも計算量は平方根程度に(確率的に)落ちるだけなのでまだ指数の手間が掛かる。

いつか改善策を思いつけたらいいな、と思ったのが5年ぐらい前の話である。

2013年8月24日土曜日

円分擬素数 あるいは なぜオイラー関数の冪和記号が欲しかったのか

これは遠い昔、とある研究集会で発表したことのある話である。 概要ぐらいしか公に残されているものがないと思うので、昔のノートを参照しながら書いてみる。 (ちなみに最近このブログにポツポツ書いている数学系の記事は、だいたい昔のノートを読み返して抜き出したものだったりする。)

定義

まずは前段階として、擬素数について思い出しておく。 広義に擬素数とは素数ならば必ず満たす条件を満たしている必ずしも素数でない整数、ということだが、単に擬素数とだけ言えばフェルマーの小定理 「\(p\) が素数ならば \(a^{p-1}\equiv 1 \bmod p\)」の式「\(a^{n-1}\equiv 1 \bmod n\)」を満たす合成数 \(n\) のことである。 正確にはこのとき「\(n\) は基 \(a\) の擬素数である」という。 以降簡単のためにこれを「\(n\) が \(\mathrm{psp}(a)\) を満たす」と表現する(psp とは pseudo prime の略である)。

\(n\) は奇数で \(\mathrm{psp}(a)\) を満たすとしよう。 すると \(n-1\) は偶数であり、2 でちょうど \(s\) 回割り切れるとすると \(n - 1 = 2^s n^*\) と書くことができる。 もちろん \(n^*\) は奇数である。 さて \(n-1\) は偶数であるから(条件式の右辺を左辺に移項すると)平方の差の形なのでよく知られているように和と差の積に因数分解できる。 \[a^{n-1} - 1 = (a^{\frac{n-1}{2}} + 1)(a^{\frac{n-1}{2}} - 1)\] この形の因数分解を \(s\) 回繰り返す。 \[a^{n-1} - 1 = (a^{2^{s-1}n^*} + 1)(a^{2^{s-2}n^*} + 1) \cdots (a^{n^*} + 1)(a^{n^*} - 1)\] \(n\) が素数の場合、積を割り切ればその因子の一つを割り切る、という性質が成り立つので、右辺の因子の一つを割り切る。 一方 \(n\) が合成数の場合、そのような保証はないが、たまたま素数と同じように右辺の因子のただ一つを割り切るかもしれない。 そのような擬素数を強擬素数といい、「\(n\) が \(\mathrm{spsp}(a)\) を満たす」と表現する(spsp とは strong pseudo prime の略である)。

以上のことはよく知られた話だが、ここから拡張を試みる。

さて、上では \(n-1\) を \(2\) で何回割り切れるかだけを問題にしたが、実際のところ \(X^m - 1\) という多項式の因数分解は次のようになることが知られている。 \[X^m - 1 = \prod_{d|m} \Phi_d(X)\] ここで \(\Phi_d(X)\) は \(d\) 次の円分多項式、すなわち \(1\) の原始 \(d\) 乗根を、それだけを根に持つ多項式である。 したがって、\(a^{n-1} - 1\) もこの形で因数分解されて、 \[a^{n-1} - 1 = \prod_{d|n-1} \Phi_d(a)\] となる。 先程と同様に、\(n\) が素数ならば \(n\) は右辺の因子の内ただ一つを割り切る。 一方、\(n\) が合成数のときは(たとえ強擬素数であったとしても)そのような保証はない。 が、たまたま素数と同じように \(n\) が右辺の因子の内ただ一つを割り切るかもしれない。 そのような強擬素数を円分擬素数といい、「\(n\) が \(\mathrm{cpsp}(a)\) を満たす」と表現する(cpsp とは cyclotomic pseudo prime の略である)ことにする。

強擬素数と円分擬素数の違いを簡単に述べると、 強擬素数は各素冪因子について基 \(a\) の位数の \(2\) 冪が一致するという条件である一方、 円分擬素数は各素冪因子について基 \(a\) の位数が完全に一致するという条件である。

基の個数

ここからは \(n\) を固定したとき、\(n\) が基 \(a\) の円分擬素数となるような \(a\) は \(n\) を法として何個あるかを計算していく。 そのために \(n\) の素因数分解を \(p_1^{e_1}\cdots p_r^{e_r}\) とする。 もちろん \(p_i\) は素数である。 先程述べたように、円分擬素数の条件は \(a\) の位数が各素冪因子について一致するということだが、その位数が \(n-1\) の約数としても登場しなければならない。 つまり、その位数は次の \(G\) の約数でなければならない。 \[G = \gcd(\{n-1\}\cup\{\varphi(p_i^{e_i}) | i = 1,\ldots,r\})\] ここでオイラー関数 \(\varphi(p_i^{e_i}) = (p_i - 1)p_i^{e_i - 1}\) だが、\(p_i\) は \(n\) の約数だから \(n-1\) とは互いに素である。よって \[G = \gcd(\{n-1\}\cup\{p_i - 1 | i = 1,\ldots,r\})\] と考えれば良い。

\(d\) を \(G\) の約数とすると、\(n\) の各素冪因子 \(p_i^{e_i}\) について位数 \(d\) の元は \((\mathbb{Z}/p_i^{e_i}\mathbb{Z})^{\times}\) に \(\phi(d)\) 個ずつ存在する。 そのうち一つを \(b_i\) と書くことにすると、孫子の剰余定理によって \(x\equiv b_i \bmod p_i^{e_i}\) であるような元 \(x\) が \(\mathbb{Z}/n\mathbb{Z}\) に一つ取れる。 いま \(b_i\) の決め方は任意だったから全ての素冪因子について位数 \(d\) である元はそれらの任意の組み合わせに対し一つずつ取れる。 つまり、全ての素冪因子について位数 \(d\) である元は \(\varphi(d)^r\) 個存在する。 \(G\) の約数全てについて和を取れば円分擬素数の基の個数が求められ、\(\sum_{d|G}\varphi(d)^r\) 個、 オイラー関数の冪和で示唆した記号を使うと \(n_r(G)\) 個である。

強擬素数の場合と比べてみると、強擬素数の基の個数は Monier により \[\left(1+\frac{2^{kr} - 1}{2^r -1}\right)\prod_{i=1}^{r}\gcd(n^*, p_i^*)\] と示されている。 ただし、\(k=v_2(G)\) である。 この2冪の等比数列の和のような部分が \(n_r(2^k)\) に該当しており、円分擬素数とは残りの奇因子の部分に違いが出てきていることが見て取れる。

2013年8月12日月曜日

オイラー関数の冪和

オイラー(totient)関数 \(\varphi(n)\) は \(1\) 以上 \(n\) 以下の \(n\) と互いに素な整数の個数を表す関数である。 言い方を変えると \((\mathbb{Z}/n\mathbb{Z})^\times\) の位数を表す関数である。 \(n\) 次円分多項式の次数という捉え方もある。 この関数が乗法的関数であることはよく知られている。 すなわち \(a\) と \(b\) が互いに素なとき \(\varphi(ab) = \varphi(a)\varphi(b)\) を満たす。

さて一般に、二つの乗法的関数 \(f\), \(g\) があったとき、次のように積の和をとったもの \(f\cdot g (n) = \sum_{d|n}f(d)g(d)\) も乗法的関数である。 よってたとえばオイラー関数の2乗和 \(\sum_{d|n}\varphi(d)^2\) は乗法的関数である。

こういったオイラー関数の2乗和や、より高次のオイラー関数の冪和について何かよく使われる記号がないものか、と昔から知りたく思っている。 ちなみに単なる因子の冪和については \(\sigma_k(n)\) という記号がある。 \(\sigma(n) = \sigma_1(n) = \sum_{d|n}d\) を一般化したものである。 その考え方を踏襲すると \(\sum_{d|n}\varphi(d) = n\) なので、\(n_k(n)\) になると考えるといいのかもしれない。

試しに OEIS を引くと、A029939 Sum phi(d)^2; d|n. は出てくるが、3乗の冪和である数列 1,2,9,10,65 が出てこない。 そのぐらい需要がない。 その需要のないものをどうして気にするか、ということはまた改めて書く。

2013年8月5日月曜日

Wilson の定理

Wilson の定理とは、素数 \(p\) に対し \((p-1)! \equiv -1 \bmod p\) が成り立つという初等整数論の定理である。 これが重要な定理ということは特にないと思うのだが、大体の教科書に載っている。 証明にはフェルマーの小定理を使ったり原始根を使ったりすることが多い。 しかし、そんな道具立ては解り易くないと思うのだ。

少し一般的な次のことを証明する (Gauss の一般化と呼ばれているようだ): \(n\) を \(3\) 以上の整数とするとき、\(\prod_{i \in \mathbb{Z}/n\mathbb{Z}^\times} i \equiv (-1)^k \bmod n\) が成り立つ。 ただし、\(k\) は \(1\) の平方根の個数の半分。

(証明) \(\mathbb{Z}/n\mathbb{Z}^\times\) は群なので、各元に逆元が存在する。 自分自身が逆元である元以外は、\(a\) と \(a^{-1}\) が別々に存在して \(a\cdot a^{-1} \equiv 1 \bmod n\) だから積に寄与しない。 自分自身が逆元である元とは \(a^2 \equiv 1 \bmod n\) ということなので、\(1\) の平方根である。 このような元 \(a\) に対し、\(-a\) も同様に \((-a)^2 \equiv a^2 \equiv 1 \bmod n\) を満たす。 \(n\) は \(3\) 以上と仮定したので、 \(a\) と \(-a\) は等しくない。 この二つの元の積を考えると、\(a\cdot(-a) \equiv -a^2 \equiv -1 \bmod n\) である。 \(1\) の平方根を \(2\) 個ずつ組にしたので、\(k\) を \(1\) の平方根の個数の半分として \(\prod_{i \in \mathbb{Z}/n\mathbb{Z}^\times} i \equiv (-1)^k \bmod n\) が成り立つ。 (証明終わり)

元の形の Wilson の定理は、奇素数 \(p\) に関しては \(n=p\) として上の命題を適用すれば \(\mathbb{Z}/p\mathbb{Z}\) が体だから \(a^2 \equiv 1 \bmod p\) の解は \(\pm 1\) 以外にないことから従い、\(p=2\) の場合は \(1 \equiv -1 \bmod 2\) なので成り立つことが判る。

さて残りは \(1\) の平方根の個数を確定すれば話が完結するが、これは \(\mathbb{Z}/n\mathbb{Z}^\times\) を巡回群の直積で書いたときの直積因子の個数を \(m\) とおくと、\(2^m\) となる。 したがって、素数以外には \(n = 4, p^e, 2 p^e\) の時だけ右辺が \(-1\) になる。 ちなみにこの右辺の値の数列がA103131としてOEISに登録されている、といった情報がMathWorldに書いてあった。

2013年7月13日土曜日

abc予想と円分多項式の素冪値

前回 (abc予想と昔考えたこと)は、素数次円分多項式はその素数が7以上ならばabc予想の仮定の下で平方以上の素冪の値を高々有限回しか取らないということを示した。 素数次以外も同様のことが証明できる、というのはまあ読者の練習問題でもいいのだが、せっかくなので書いてみることにする。

\(m\) を合成数とし、\(\varphi(m)\) が \(6\) 以上(つまり \(m = 4,6,8,10,12\) 以外)と仮定しよう。 \(m\)次円分多項式 \(\Phi_m(X)\) が、\(x\) で素冪の値 \(p^n\) を取ると仮定する。ここでもちろん \(n \ge 2\) である。 円分多項式はよく知られているように \(X^m - 1 = \prod_{d | m}\Phi_d(X)\) を満たすので、 \[x^m - 1 = p^n \prod \Phi_d(x)\] と書ける。ただし、右辺の積は \(d=m\) 以外の \(m\) の約数に亘る。 \(x\) と右辺の各因子は互いに素なのでabc予想が使える。

abc予想:
任意の \(\epsilon > 0\) に対して, ある正の定数 \(K(\epsilon)\ge 1\) が存在して, 次を満たす:
\(a\), \(b\), \(c\) が互いに素な整数で \(a + b = c\) を満たすならば, 不等式 \[\max \{|a|, |b|, |c|\} < K(\epsilon) \{\text{rad}(abc)\}^{1+\epsilon}\] が成立する.

少し余談を挟むと、前回もそうだったのだが、左辺は \(\max\) を取るのが大事なのではなく、「\(|a| <\) 右辺」かつ「\(|c| <\) 右辺」と二つの式を両立できる、と考えるのが使い方のコツである。

ではまず \(|a|\) から使おう。 \[x^m < K(\epsilon) \left(p\cdot x\cdot \prod \Phi_d(x)\right)^{1+\epsilon}\] ここで円分多項式の積の部分は \(m - \varphi(m)\) 次の多項式なので、適当な定数 \(C\) を取れば \(Cx^{m-\varphi(m)}\) で上から抑えられる。 \[x^m < K(\epsilon) (p\cdot Cx^{1 + m-\varphi(m)})^{1+\epsilon}\] さらに \(x\) について左辺にまとめてしまおう。 \[x^{m-(m-\varphi(m)+1)(1+\epsilon)} < K(\epsilon)C^{1+\epsilon}p^{1+\epsilon}.\]

次は \(|c|\) を使う。 \[p^n\prod \Phi_d(x) < K(\epsilon) \left(p\cdot x\cdot \prod \Phi_d(x)\right)^{1+\epsilon}\] そして今度は \(p\) を左辺に、\(x\) を右辺にまとめる。 \[p^{n-1-\epsilon} < K(\epsilon) x^{1+\epsilon} \left(\prod \Phi_d(x)\right)^{\epsilon}\] 先程と同様円分多項式の積の部分は上からの評価に代えて \[p^{n-1-\epsilon} < K(\epsilon) C^{\epsilon} x^{\epsilon m - \epsilon \varphi(m) + 1 + \epsilon}\] を得る。

式変形を簡単にするために \(\epsilon = \frac{1}{m}\) とおく。 \(x\) の評価式の冪は次のようになる。 \[m-(m-\varphi(m)+1)(1+\frac{1}{m}) = \varphi(m) -2 + \frac{\varphi(m) - 1}{m}\] 一方 \(p\) の評価式の右辺の \(x\) の冪は \[\epsilon m - \epsilon \varphi(m) + 1 + \epsilon = 2 - \frac{\varphi(m) - 1}{m}\] となる。 ここで両者に共通する \( 2 - \frac{\varphi(m) - 1}{m}\) を \(1\) と \(2\) の間という気持ちを込めて \(1 + \delta\) と書くことにする。

それでは二つの式をまとめていこう。 \[x^{\varphi(m) - (1 + \delta)} < K(\frac{1}{m})C^{1+\frac{1}{m}}p^{1+\frac{1}{m}}\] ここで \(p\) の評価を第2式で置き換えたいのだが、冪 \(n\) がちょうど \(2\) のとき、そのままでは \(n - 1 - \frac{1}{m} < 1 + \frac{1}{m}\) なので、\(2\)乗する(仮定した条件から\(2\)乗すれば良いことは容易に判る)。 \[ < K(\frac{1}{m})C^{1+\frac{1}{m}}p^{2(n - 1 - \frac{1}{m})}\] \[< K(\frac{1}{m})C^{1+\frac{1}{m}} K(\frac{1}{m})^2 C^{\frac{2}{m}} x^{2(1+\delta)}\] ここで \(x\) を左辺に移項すると、 \[x^{\varphi(m)-3(1+\delta)} < K(\frac{1}{m})^3 C^{1+\frac{3}{m}}\] という評価を得る。 ここで最初に仮定したように \(\varphi(m) \ge 6\) なので左辺の \(x\) の冪は正であり、右辺は定数であるから、可能な \(x\) の整数値は有限個である。

まとめると次のことが証明できた。 \(m\) を \(\varphi(m)\ge 6\) を満たす合成数とすると、abc予想が成り立つならば、円分多項式 \(\Phi_m(X)\) が平方以上の素冪の値をとるのはどの \(m\) についても高々有限回に限る。

2013年7月9日火曜日

eselect-1.3.6

gentoo と python と eselect と, dev-lang/python と /usr/lib/portage/pym, 0xF 0xB 0x31 0xFF と続いてきたシリーズも今回でひとまず終わり。

前回 libSystem.B.dylib で死ぬところまで見たが、 Gentoo Bugs #475284 では回避策の議論が進んだ。 eselect のコードでどこがこのバグを踏む原因になっているのかというと、 エラー出力のファイル記述子を置き換える辺りらしい。 決め打ちではエラーが起こるが、自動で振る機能は bash-4.1 以降の機能、というのが回避するコードを書く際の悩みどころだったようだ。

ともかく、対策済みのバージョンが eselect-1.3.6 としてリリースされた。 一件落着だ。

とはいえ、根本原因が塞がれたわけではないのでバグはまだオープンで、 バグタイトルが "app-shells/bash-4.2_p39-r1: "exec 3>&2" causes illegal instruction (seen with app-admin/eselect-1.3.5)" と大幅に変わって bash チームに投げられている状態である。

2013年7月4日木曜日

0xF 0xB 0x31 0xFF

app-admin/eselect-1.3.5 問題の続き。

一応復習しておこう。 PORTAGE_ELOG_COMMAND で呼び出された gentwoo が eselect を呼び出したところで死ぬ。 環境変数を gentwoo に引き渡しておけば死なない。

Gentoo Bugs #475284 に報告してみて得た情報なども加味しながらもう少し情報を補足しよう。 環境変数が空っぽだと死ぬので env -i /path/to/eselect とすればいつでも再現できる、と主張したのだが、 これで現象が再現できるのは(少なくとも今のところは)私の Gentoo Prefix on OS X でだけである。 そもそも、eselect は bash スクリプトで、死んでいるのは具体的にどこなのか、と聞かれて core を吐かせることにする。 ulimit -c unlimited としておく(と core ファイルは /cores に core.PID という名前で残される)。

死んでいるのは bash の中だ。

bash 自体が死ぬような現象には遭遇した経験が無かったので、どうにもデバッグの糸口が摑めなかった。 とりあえず eselect の中に echo コマンドをいくつか挟んでみた。 どうも死ぬ場所は一定していないらしい(埋め込んだ echo が実行される前に死んだり、実行してから死んだりまちまち)。 とすると、むしろメモリーのゴミを踏んでしまっているか?

メモリーエラーには valgrind。 ここでも環境変数を渡さないように env -i /path/to/valgrind /path/to/bash /path/to/eselect。 すると次のような出力を得る

vex x86->IR: unhandled instruction bytes: 0xF 0xB 0x31 0xFF
==64989== valgrind: Unrecognised instruction at address 0x2a5ce9.
==64989==    at 0x2A5CE9: _dispatch_mgr_invoke (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A4F58: _dispatch_queue_invoke (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A4CFD: _dispatch_worker_thread2 (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A4780: _pthread_wqthread (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A45C5: start_wqthread (in /usr/lib/libSystem.B.dylib)
==64989== Your program just tried to execute an instruction that Valgrind
==64989== did not recognise.  There are two possible reasons for this.
==64989== 1. Your program has a bug and erroneously jumped to a non-code
==64989==    location.  If you are running Memcheck and you just saw a
==64989==    warning about a bad jump, it's probably your program's fault.
==64989== 2. The instruction is legitimate but Valgrind doesn't handle it,
==64989==    i.e. it's Valgrind's fault.  If you think this is the case or
==64989==    you are not sure, please let us know and we'll try to fix it.
==64989== Either way, Valgrind will now raise a SIGILL signal which will
==64989== probably kill your program.
==64989==
==64989== Process terminating with default action of signal 4 (SIGILL)
==64989==  Illegal opcode at address 0x2A5CE9
==64989==    at 0x2A5CE9: _dispatch_mgr_invoke (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A4F58: _dispatch_queue_invoke (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A4CFD: _dispatch_worker_thread2 (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A4780: _pthread_wqthread (in /usr/lib/libSystem.B.dylib)
==64989==    by 0x2A45C5: start_wqthread (in /usr/lib/libSystem.B.dylib)
==64989== 

何度か実行してみたが、毎回同じ結果のようだ。 0xF 0xB 0x31 0xFF って何? しかも libSystem.B.dylib (OS X おける libc みたいなもの)の中って。

今回は何も解決しない。

2013年6月30日日曜日

dev-lang/python と /usr/lib/portage/pym

昨日の投稿で、gentwoo が上手く動かないのは python と eselect のせい、と書いた。 dev-lang/python は 2.7.3-r3 から 2.7.4 の間に何が変わったのか、ということを調べてみた。

昨日書いたように、portage.util の ImportError が第一の原因なので、それを見てみる。 python-2.7.3-r3 では sys.path に ${EPREFIX}/usr/lib/portage/pym が含まれているが、python-2.7.4 では含まれない。 では、python-2.7.3-r3 ではどこでこのパスを設定しているのか。 それは site.py の中である。 site.py にそれを書き加えているのはパッチ tar ボールの中の 03_all_add_portage_search_path.patch である。 python-2.7.4 ではこのパッチが消えている。 おお、これだ。

だがちょっと待て。 だとすると、普通に Gentoo Linux を使っている人も同じ症状になってしまわないか?

ということで、VirtualBox に Gentoo Linux 環境をお手軽に用意するために liveDVD イメージをダウンロードして、起動。 最新の liveDVD とはいえ昨年末のなので、python のバージョンは 2.7.3 である。 当然、emerge --sync して emerge -1 =python-2.7.5 で 2.7.5 に上げる。 python2.7 を立ち上げて、import sys; print sys.path。 うん、なぜか /usr/lib/portage/pym がちゃんと含まれている。

パッチは消えたのだから、site.py には設定されていない。 環境変数? python -E で環境変数を無視して立ち上げると確かに pym のパスは消える。

$ env | grep pym
PYTHONPATH="/usr/lib/portage/pym"

そう、環境変数 PYTHONPATH で設定しているんだ。 環境変数自体は /etc/env.d/05portage で定義されていた。

翻って Prefix 環境で調べてみると、確かに ${EPREFIX}/etc/env.d/05portage が存在した。 このファイルが有効に働くタイミングは、特に何もしなければログインするたびだ。 つまり、ログインし直していればちゃんと PYTHONPATH が反映されて gentwoo も普通に動作していたはず、と。 ログインしっぱなしだもんなあ。

2013年6月29日土曜日

gentwoo と python と eselect と

Gentoo の portage の機能として、make.conf で PORTAGE_ELOG_COMMAND にログ出力用の任意のコマンドを指定して実行させる仕組みがある。 gentwoo はそれを利用したログ収集のサイトで、そこにログを送るために betagarden overlay の app-portage/gentwoo をインストールして

PORTAGE_ELOG_SYSTEM="custom:* save"
PORTAGE_ELOG_COMMAND="gentwoo '${PACKAGE}' '${LOGFILE}'"

といった行を make.conf に書き加えてある。

最近、といってももう3週間ぐらい、この gentwoo の呼び出しでエラーが発生するのである。

二種類のパターンがある。 一つめは gentwoo-2.7 という(Python 2.7 で実行される)スクリプト本体で発生するエラー。

Traceback (most recent call last):
  File "/Users/tetsushi/Gentoo/usr/bin/gentwoo-2.7", line 11, in 
    from portage.util import getconfig
ImportError: No module named portage.util
!!! PORTAGE_ELOG_COMMAND failed with exitcode 1

二つめは gentwoo というラッパーシェルスクリプトで発生するエラー。

/Users/tetsushi/Gentoo/usr/bin/gentwoo: Execution of 'eselect python show --python2' failed
!!! PORTAGE_ELOG_COMMAND failed with exitcode 1

どちらのエラーも portage がインストールする ${EPREFIX}/usr/lib/portage/pym/portage/elog/mod_custom.py で spawn_bash の引数に env=os.environ を追加すれば回避できるようだが、このファイルは数年書き変えられていないので挙動が変わってしまった真の原因ではない。

portage と eselect のバージョンによるエラーのパターンは以下の表の通り。 portage のバージョンは現在 prefix ツリーにある最古と最新。 eselect のバージョンは最近エラーが変わる前後のバージョン。

portage-2.2.01.219382.2.01.22013
eselect-1.3.4パターン1パターン1
1.3.5パターン2パターン2

eselect は予想通りの結果だったけど、portage はエラーが起こり始めたと思った時点よりも前の 2.2.01.21938 でも再現されてしまって意外な感じ。 gentwoo のバージョンも関係ないし、原因が判らない。

と書いたところで思い出した。 そういえば最初にエラーが出た6月10日前後、python のアップデートもあった。 現在使っているのは dev-lang/python-2.7.5 だ。 ebuild の更新が6月のバージョンを避けて python-2.7.3-r2 を emerge すると、パターン1は再現しなくなった。 6月に更新されているけど 2.7.3-r3 も OK。 しかし 2.7.4 は再びエラーだ。

結論。パターン1は python 側の何らかの変更が原因。 パターン2は eselect の何らかの変更が原因。 さて、どこにどう報告すればいい?

2013年6月7日金曜日

人間ドック

初人間ドック。

バリウム飲んでぐるぐる回されると話には聞いていたが、なるほどぐるぐる回らされた。 バリウムが飲みにくいとか言われたが、ラッシーと変わらないぐらいじゃないの。

今日は身長が169センチ台の半ばだった。 いつもは168センチ台後半ぐらいなので、微妙に高めに出ている。

眼底検査の時に「睫毛が長くて邪魔」とか言われたが、ごめんなさい生えてる向きがわりと下向きなだけだと思います。

裸眼視力は相変わらず1.5あった。

腹囲を測るときに「ズボンのウエストサイズより太めに出るかもしれません」とか医者が言ったが、(私にとっては)逆です、先生。 いわゆる"メタボ"体型を念頭に置いて検査が出来上がっているんだな、と。

そんなこんなで検査が終わって、バリウムを排出するために下剤を飲んで下さい、という指示に素直に従った。 そして、飯を食って会社に向かう電車の中で腹痛が始まった。 何が印象に残ったって、もう何よりもこの腹痛による消耗した気分だった。

2013年5月8日水曜日

abc予想と昔考えたこと

その昔、円分多項式に整数を代入したとき素冪が出てくることがあるのか、というようなことを考えたことがある。 その時は、円分多項式 \(\Phi_m(X)\) に対し素数 \(p\) と原始 \(m\) 乗根 \(x\) を固定して、 \(x\) から始まる \(p\) 進 \(m\) 乗根の展開に \(0\) が沢山続くと…。 詳細は忘れたが、まあ不都合が発生するということになっていたはずである。 というようなわけで、\(p\) 進展開を計算させてみた記憶がある。

最近 ABC予想入門 という新書を読んだので、それをこの素冪の問題に応用してみようと思う。

abc予想:
任意の \(\epsilon > 0\) に対して, ある正の定数 \(K(\epsilon)\ge 1\) が存在して, 次を満たす:
\(a\), \(b\), \(c\) が互いに素な整数で \(a + b = c\) を満たすならば, 不等式 \[\max \{|a|, |b|, |c|\} < K(\epsilon) \{\text{rad}(abc)\}^{1+\epsilon}\] が成立する.

\(p\), \(q\) を素数として、\(\Phi_q(x) = p^n\) だったとする。 式を書き直すと \(x^q - 1 = (x-1)p^n\) となるので、\(a = x^q\), \(b = -1\), \(c = (x - 1) p^n\) として、 予想の前提を満たす。 よって、予想を仮定すれば \[\max \{x^q, 1, (x-1)p^n\} < K(\epsilon) \{\text{rad}(x^q \cdot 1 \cdot (x-1)p^n)\}^{1+\epsilon}\] となるが、左辺は \(x^q\)、右辺は \(K(\epsilon) (x(x-1)p)^{1+\epsilon}\) である。 すなわち \[x^q < K(\epsilon) (x(x-1)p)^{1+\epsilon}\] で、右辺の \(x-1\) を \(x\) に置き換えて \[x^{q-2-2\epsilon} < K(\epsilon)p^{1+\epsilon}\] を得る。

一方左辺をより小さくして \((x-1)p^n\) として評価すると、 \[p^{n -1 -\epsilon} < K(\epsilon)x^{1+\epsilon}(x-1)^{\epsilon}\] なので、\(x-1\) は \(x\) で置き換えて \[p^{n -1 -\epsilon} < K(\epsilon)x^{1+2\epsilon}\] となる。

今 \(\epsilon = 1/4\)、\(K=K(1/4)\) とすると、 \[x^{q-5/2} < K p^{5/4}\] \[p^{n-5/4} < K x^{3/2}\] なので \(n \ge 2\) のとき \[x^{q-5/2} < K p^{5/4} < K p^{2n-5/2} < K^3 x^3.\] この式は \(q > 11/2\) ならば \(x\) が十分大きいときに成り立たなくなる。

つまり、abc 予想が成り立てば、各素数 \(q \ge 7\) に対し \(\Phi_q(x)\) が2次以上の素冪になるような \(x\) は有限個しかない。 またその上限は \(q\) と abc 予想の定数 \(K(1/4)\) で決まる。

実に強力な予想である。

2013年4月22日月曜日

日記の書き写し

ブログ移転予定 なのでその作業の一環として Floating Log の内容を抜き出して 痕跡 に置いた。 ブログサイトとしての構造は全然保っていないので、まさに書き写された日記というだけの代物。

読み返すと、一文だけの日とかもあって、そういうのは今はツイッターで済ませてしまっているのだということに時代の変化を感じる。

2013年4月15日月曜日

棚卸し (GitHub編)

引き続いて GitHub、とは言ってもそんなに使っていないのだった。

Arithmetica
その昔、20世紀の終わり頃、awk がメインのプログラム言語だった頃、多倍長整数の計算がしたくなって awk で実装したもの。 素数判定とか因数分解とかなんかも、メモリーの制約が厳しい環境で動くアルゴリズムを実装してある。 「awk でも多倍長整数が使いたい」という人向け(まあ滅多にいない)。

他は gentoo の翻訳プロジェクトが github を使っているので、そこに参加しているぐらい。

棚卸し (BitBucket編)

引き続いて BitBucket 編。 BitBucket は(最近は Git も扱えるけど) Mercurial のレポジトリ置き場。

その1: mft_experimental
現在自分の普段使いの OS は Mac OS X なのだが、パッケージマネージャーには Gentoo Prefix を使っている。 それの自分用オーバーレイ。 一時期よりは管理している(独自にパッチを当てたりしている)パッケージが減ってきた。

その2: csggraphenum
どちらもグラフ列挙用のプログラム。 csg は阪大にいたときに間に合わせで作った Python プログラム。9頂点が限界。 graphenum は NII 時代に宇野先生と考えたアルゴリズムの実装で、Python 実装と C 実装があるが、メインは C 実装。 11 頂点まではいけることを確認している。 もう少し速くなると良かったんだけど。

その3: nxbimatch
2部グラフのマッチングを列挙するプログラム。 最大マッチングと完全マッチングの列挙ができる。 グラフ自体は NetworkX という Python のグラフライブラリのものを使っている。 マッチングを一つ探すようなプログラムは良くあるが、列挙するものは見掛けないので自分で実装した。

その4: hcp
これは GAE編 その2 の Hilbert class polynomials の実装を公開しているもの。 Google App Engine を公開データベースとして使うサンプル、ぐらいの気持ち。

ニッチなプログラムばかりだ。

棚卸し (GAE編)

技術者スキルシートとかいうものを埋めていたのだが、 どちらかというと趣味で動かしているプロジェクトはどうするのだ。 と、思って結局そこには書かなかったのだが、どこかに書きたくなったのでここに書く。

まずは Google App Engine 上で動かしているものについて。 (この後、BitBucket や GitHub に放り込んであるものなども書くつもり)

その1: みんなで正誤表
昔から本の誤植が気になる方だったので @nifty のホームページ(まだある)とかでも手書き HTML で正誤表を地味に作っていたのだが、「これウェブアプリにすればいいんじゃない?」と思って GAE で作ったもの。 Python 系の書籍などでごく少数ながら公式っぽく扱ってもらったりして、まあ一番使われていると言って良いだろう。

一時期、SDK のバージョンと Python のバージョンとデータストアの種類と利用するフレームワーク(Kay)とアップデートしなければいけない状態になって、更新に二の足を踏んでいた。 が、最近少し時間があるので、一気に更新と懸案の検索機能追加などを済ませた。 ツイッターの @public_errata で更新情報をつぶやくようにしたが、 これを自動化するのが次に暇になったときの目標。

その2: Hilbert class polynomials
NZMATH の機能の一部。 判別式ごとに Hilbert 類多項式の係数を返す、ただそれだけのもの。 データストアの更新前、Master/Slave 方式の時は free quota にぎりぎり収まっていたのに、HRD に代えたらぎりぎりインデックスが収まりきらない状態になってしまった。 無駄にインデックスが張られているフィールドをインデックス無しに変更して様子見。

その3: NZMATH / JSON
NZMATH は Python で書いてあるんだし、そのまま GAE に載るよね。 というノリで作られた試作品。 結果が JSON で返るので、この名前になっている。 データストアは一切使っていなかったが、更新しろと言われたので更新した。 放置して旧式の M/S が使えなくなったときにどうなるか見るのもいいかと思っていたが、その2の Hilbert class polynomials が中国式剰余定理をこっちでまかなうという、変な作りになっているので安全側に。 Sage のノートブックとかと比べてはいけません。

その4: ギョエテくん
Göthe をギョエテと読んだ人がいた時代があった。 今でも読み方の一定しない外国人の名前ってあるよね。 ということで、そんな情報を収集しようとしてみたもの。 インターフェイスもでたらめだし、もうメンテする気はなくなっている。 これこそ M/S 方式のまま放置して滅びる様を観察する対象、と自分では思っている。 もし万が一、引き継いでみたいという人がいれば、喜んで権限をお譲りします。

以上4つ。

2013年3月31日日曜日

転職

転職します。 ポスドクからプログラマーになります。

やり残したこととか:

  1. グラフの列挙: とにかく連結単純グラフを(頂点数を指定して)全部列挙する、という課題。 一応、ここ1年半ぐらいこのプログラムを書いていたりしたんですが、 世界最速には追いつけなかったのが心残り。
    graphenum
  2. \(L(m,n)\) の対称鎖分解: ここ半年ぐらい戯れていた未解決の予想。 任意の \(m,n\) について \(m \times n\) の長方形に入るヤング図形に包含関係で順序を入れた半順序集合は ランクに関して対称な鎖に分解できるだろうという、1980年頃出された予想です。 \(L(3,n)\) と \(L(4,n)\) は分解できることが知られているので、 その先をどうにかするのが問題で、今もプログラムとか書いて遊んでいます。
  3. Waring 問題的なもの: Waring 問題は、 自然数の \(k\) 乗を \(g(k)\) 個足したら自然数全部表せるような \(g(k)\) が存在する、 というのが元々の設定で、 \(G(k)\) 個あれば有限個の例外を除いて表せるような \(G(k)\) を求めよう、 というのが本質的な問題。 それを係数付きに拡張して考えると…という問題を、 これもコンピュータで計算してみたらと手を出してみたけど、 最近はMさんどうしているのでしょう。
  4. NZMATH: 数論向けのソフトウェアを Python で作ろうというプロジェクト。 これを始めて、それで博士の学位ももらったんですが、 今は後輩がリーダーとして動いています。動いて…。まあ、うん。 Python3 に移行しないといけない、とか、やることはいろいろあるはず。
    NZMATH home
    NZMATH @ sf.net