11
$\begingroup$

Just studying the paper PRIMES is in P, although I've tried great efforts, some proofs are still not so clear(or obvious) to me, especially the proof of Lemma 4.3. The problem is by choosing r the smallest number that does not divide the product $n^{\lfloor logB \rfloor}\prod_{i=1}^{\lfloor log^2n\rfloor}{(n^i-1)}$, why the fact $(r, n)$ cannot be divisible by all the prime divisors of r holds? And why if violated, r will divide $n^{\lfloor logB \rfloor}$? Any relation with the observation "the largest value of $k$ for any number of the form $m^k \leq B$ , for $m > 2$ is $\lfloor logB \rfloor$"? And finally, the conclude of this proof, I cannot find trivial relation between $r$ and $B$, any theorem or fact I miss?

Thanks and Best Regards!


EDIT:

Follow Will's advice below, I found the article linked above is a draft and referred to the published version. Much more clear indeed! However, there is still one point I'm not sure:

At nearly the end of proof to lemma 4.3, the authors say "If $(s,n)>1$, then since $s$ does not divide $n$ and $(s,n)\in {r_1,r_2,…,r_t }$" then "$r=\frac{s}{(s,n)}\not\in {r_1,r_2,…,r_t }$". Where $r_i$ is defined as numbers either $o_r(n)\leq \log^{2} n$(which is the bound we want to approach, I think) or $r_i$ divides $n$ and $s$ is a number $\leq \lceil \log^{5}n\rceil$ such that $s\neq r_i$(previous lemma shows we can always find such an $s$ under the hypothesis). Why there is no pobability $o_r(n)\leq \log^{2}n$? In which case, seems no assumptions are voilated.

Thank you!

  • 5
    Dear readers: In case you don't notice, there's a link to the PDF paper if you hover over ` PRIMES is in P`!2012-03-13
  • 0
    read terry taos blog on it, he makes it really simple2013-01-22

2 Answers 2