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 みたいなもの)の中って。

今回は何も解決しない。