ratio - rational - irrational

あ、PRIMES is in PのAugust 2005 ver.が出てる。私がゼミで読んだのは3rdだから、あれから結構改訂したのね。

大枠は変わっていない（そらそうだ。変わってたらもっと話題になってる）ものの、ざっと見た感じでも記法が整理されたほかに、いくつか変更点がある。

* rの上界が[log^5 n]からmax{3, [log^5 n]}に変わった。

Step 4の不等式が意味をなす範囲が少し限定される。私らが実験値から推測したのと大体大きさは合ってる。私らの実験値のほうがいくらか大きかったのは、オイラー関数あたりの実装がかなり甘かったからだろう。

* LenstraによるAgrawal予想の否定。

古い版ではFuture Workとしてオーダーを大幅に下げる予想を提示してあったけれども、それは2003年3月にLenstraが偽であると証明した。そのことに言及している。でも、「それでも何かこの命題の変形で真になるものがあるかもしれない」と食い下がっている。

そう言えば、先生は冗談交じりに「Agrawal予想を証明できたら即、修士号あげるよ」と言ってたけれど、それからすぐにLenstraの論文が出てしまったのだった。