On proof of AKS primality test algorithm

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!

• Dear readers: In case you don't notice, there's a link to the PDF paper if you hover over  PRIMES is in P! – user2468 Mar 13 '12 at 4:58
• read terry taos blog on it, he makes it really simple – user58512 Jan 22 '13 at 21:14

Actually, the first paper (version 6) you read is the more recent version; the annals of mathematics version was published first and contains an mistake in Lemma 4.3 (there's an acknowledgment in the version 6 paper noting the error). The problem is with the last line of the proof, which is exactly where you got stuck.

Mistake in Lemma 4.3 of AKS (Annals of Math version)

Given that $s \not \in \{r_1,\ r_2,\ ...,\ r_t\}$ and $(s,n) > 1$, it is not necessarily true that $\frac{s}{(s,n)} \not \in \{r_1,\ r_2,\ ...,\ r_t\}$. Consider the following:

Since $s \not \in \{r_1,\ r_2,\ ...,\ r_t\}$, we know that $s$ doesn't divide $n$, and either $o_s(n) > \log_2^2(n)$ or $o_s(n)$ doesn't exist. If $(s,n) > 1$, then $o_s(n)$ doesn't exist, but that doesn't imply that the order of $n$ modulo $\frac{s}{(s,n)}$ is greater than $\log_2^2(n)$.

Suppose $n = 8$. Then 6 is the first number we encounter that is not in $\{r_1,\ r_2,\ ...,\ r_t\}$, because $o_6(8)$ doesn't exist, and 6 doesn't divide 8. However, $\frac{6}{(6,8)} = \frac{6}{2} = 3$, and $3 \in \{r_1,\ r_2,\ ...,\ r_t\}$, because $o_3(8) = 2$, and $2 \leq \log_2^2(8) = 9$.

My proof of Lemma 4.3

It turns out that the $n^{\lfloor\log(B)\rfloor}$ introduced in the newer version of the paper is necessary to address this kind of counterexample. I also found the version 6 proof rather difficult to understand; a lot of steps were left out. So below is an expanded proof I wrote myself! Hopefully it is more clear; let me know if anything doesn't make sense :) It breaks the proof down into three steps: finding a small enough $r$, proving that $o_r(n)$ exists, and finally showing that $o_r(n) > \log^2{n}$.

Claim: There exists an $r \leq$ max$\{3,\lceil\log^5{n}\rceil\}$ such that $o_r(n) > \log^2{n}$.

Proof: We know $n>1$. If $n=2$, we can let $r=3$, and since $2^2 = 4 \equiv 1 \text{ mod } 3$, $o_3(2) = 2$, while $\log^2{2} = 1$, so the statement holds. From here on, assume $n>2$. Note that $\lceil \log^5 3 \rceil = 11$, and since the logarithm function is monotonically increasing, we know that $\lceil \log^5 n \rceil > 10$ for all $n>2$. Let $B = \lceil \log^5 n \rceil$. Applying lemma 3.1, we have that $LCM(B) \geq 2^{B}$. First we will prove that there exists a number $r\leq B$ that doesn't divide the product $$N=n^{\lfloor\log{B}\rfloor} \cdot \displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1)$$ Suppose, by contradiction, that for all $1\leq r \leq B$, $r$ divides $N$. Then clearly $LCM(B) \leq N$, because $N$ itself is a common multiple of all numbers less than or equal to $B$. Notice that \begin{align*} N&=n^{\lfloor\log{B}\rfloor} \cdot \displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1) \\ &< n^{\lfloor\log{B}\rfloor} \cdot \displaystyle\prod_{i=1}^{\log^2(n)}(n^i) \\ &= n^{\lfloor\log{B}\rfloor+1+2+...+\log^2(n)} \\ &= n^{\lfloor\log{B}\rfloor+\frac{1}{2}(\log^2(n)((\log^2(n)+1))} \\ &= n^{\lfloor\log{B}\rfloor+\frac{1}{2}(\log^4(n)+\log^2(n))} \\ &< n^{\log^4(n)} \\ &= (2^{\log(n)})^{\log^4(n)} \\ &= 2^{\log(n)\cdot \log^4(n)}\\ &= 2^{\log^5(n)}\\ &\leq 2^{B} \end{align*} Therefore $N < 2^{B}$. Recall that $LCM(B) \geq 2^{B}$, so we have $LCM(B) > N$. However, we saw above that $LCM(B) \leq N$; a contradiction. Therefore the set of numbers between 1 and $B$ that do not divide $N$ is non-empty; let $r$ be the smallest element of this set.

We've found an $r\leq B$; now we need to prove that $o_r(n)$ exists, and that $o_r(n) > \log^2{n}$. Recall that the order of $n$ modulo $r$ only exists if $(r,n) = 1$. We shall prove that this is the case. Write $r=ab$, where the prime factors of $a$ are precisely the prime factors of $r$ which divide $n$, and $b$ is made up of the remaining prime factors. Clearly $(b,n) = 1$, since $n$ and $b$ have no common prime factors. Notice that the highest power any prime could be raised to in the prime factorization of $a$ is $\lfloor \log{B}\rfloor$, since otherwise $a \leq r$ would be greater than $B$ (this is from the observation that "the largest value of $k$ for any number of the form $m^k \leq B$ , for $m\geq2$ is $\lfloor \log{B}\rfloor$" from the AKS paper). Therefore, every prime factor in $a$ is raised to a smaller exponent than the same factor in $n^{\lfloor\log{B}\rfloor}$, and since every prime factor of $a$ is present in $n$, it must be the case that $a$ divides $n^{\lfloor\log{B}\rfloor}$. It follows that $b$ does not divide $\displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1)$, because if it did, then $r = ab$ would divide $N$, and we chose $r$ such that this isn't the case. However, it is also true that $b$ does not divide $n^{\lfloor\log{B}\rfloor}$, since $(b,n) = 1$. Therefore $b$ doesn't divide $N$. But we know $r$ is the smallest number that doesn't divide $N$ and $b \leq r$, so it must be the case that $r = b$. So since $(b,n) = 1$, we have $(r,n) = 1$. Therefore, the order of $n$ modulo $r$ exists.

All that remains to be shown is that $o_r(n) > \log^2{n}$. This, fortunately, is almost trivial. Suppose by contradiction that $o_r(n) = d \leq \log^2{n}$. Then by definition, $n^d \equiv 1$ mod $r$, which implies $n^d -1 \equiv 0$ mod $r$, and so $r | (n^d -1)$, for a value of $d$ which is less than or equal to $\log^2{n}$. But then $r$ would divide one of the factors within the product of $N$, and we know that $r$ does not divide $N$. Therefore, $o_r(n) > \log^2{n}$.

I can't make any sense of that section, it appears if you assume $r < B$ then other things follow and then $r < B,$ so seemingly circular, but in any case clumsy.

Otherwise, Andrew Granville did the whole thing over, see GRANVILLE. On page 20, Lemma 4.4, he switches to prime $r$ such that $(\log n)^5 < r < 2 (\log n)^5,$ where $\log$ always means logarithm base $2.$ Note that the fact that there is at least one prime between those bounds is Bertrand's Postulate, first proved by Chebyshev and later, in elementary fashion, by Erdos.

• Thanks for your helpful hints and suggestion! – Summer_More_More_Tea Mar 13 '12 at 6:54
• I went over the published version. Quite clear indeed. However, still one thing that I can't figure out. At the nearly end of the proof of 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,\dots,r_t\}$" then "$r=\frac{s}{(s,n)}\not\in\{r_1,r_2,\dots,r_t\}". Why there is no pobability$o_r(n)\leq \lceil(\log n)^5\rceil$? In which case, seems no assumptions are voilated. Thanks! – Summer_More_More_Tea Mar 13 '12 at 13:23 • @Summer_More_More_Tea, I don't have the published version and won't today, it is a long drive to the Institute. Either you can scan the published article and edit a link to it in your question, or put an extended description in your question, defining everything and giving all the bounds, especially defining the$r_i$and everything about$s,\$ preferably word for word and typeset. Also, if you edit your question, it goes to the front of the "active" ordering of questions, so more people will see it. But many MSE users who could answer you will also lack the published paper. – Will Jagy Mar 13 '12 at 19:06