あ、PRIMES is in Pの August 2005 ver. が出てる。私がゼミで読んだのは3rdだから、あれから結構改訂したのね。
大枠は変わっていない(そらそうだ。変わってたらもっと話題になってる)ものの、ざっと見た感じでも記法が整理されたほかに、いくつか変更点がある。
- rの上界が[log5 n]からmax{3, [log5 n]}に変わった。
Step 4の不等式が意味をなす範囲が少し限定される。私らが実験値から推測したのと大体大きさは合ってる。私らの実験値のほうがいくらか大きかったのは、オイラー関数あたりの実装がかなり甘かったからだろう。
- LenstraによるAgrawal予想の否定。
古い版ではFuture Workとしてオーダーを大幅に下げる予想を提示してあったけれども、それは2003年3月にLenstraが偽であると証明した。そのことに言及している。でも、「それでも何かこの命題の変形で真になるものがあるかもしれない」と食い下がっている。
そう言えば、先生は冗談交じりに「Agrawal予想を証明できたら即、修士号あげるよ」と言ってたけれど、それからすぐにLenstraの論文が出てしまったのだった。