PRIMES Is in P

• p. 9 References, [GK86]

  Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pages 316–329, 1986.

• p. 9 Reference list, [GK86]

  In Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pages 316–329, 1986.

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: 'Almost all primes can be quickly certified' was published in the Proceedings of the 18th ACM STOC (1986), pp. 316–329, not IEEE FOCS. The page 9 image shows the FOCS wording exactly as quoted, and it is the same wording as the [AB99] entry.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 2 Section 1, para 'The ultimate goal'

  the correctenss proofs of deterministic algorithms of [APR83, GK86, Atk86] are much more complex

• p. 1 Section 1, last paragraph

  Goldwasser and Kilian [GK86] proposed a randomized algorithm

• p. 2 Introduction, para 2

  correctenss proofs

• p. 2 Introduction, para 1

  the correctenss proofs of deterministic algorithms

Only the authors can say what is right here.

Judge's note: Compared the page 1 and page 2 images. Page 1 calls GK86 randomized (expected polynomial time) and calls Atk86 similar to it. Page 2 groups both with APR83 as 'deterministic algorithms'. The paper's own descriptions are inconsistent. The intended word (e.g. primality-proving) is for the authors to say. The misspelling 'correctenss' in the same sentence is handled separately as C004.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 2 Proof of Identity (1), first sentence

  For 0 < i < p, the coefficient

Only the authors can say what is right here.

Judge's note: Checked the crop of p.2. My working: (x−a)^p = Σ C(p,i) x^i (−a)^{p−i}, so the coefficient of x^i is (−1)^{p−i} C(p,i) a^{p−i}. Subtracting x^p − a changes only the x^p and x^0 terms. For odd p, (−1)^{p−i} = −(−1)^i. Counterexample: p=9, a=1, i=3 (a is coprime to p, and the proof covers composite p). The true coefficient is +84 and the printed formula gives −84. These also differ mod 9 (3 vs 6). The proof only uses whether coefficients are zero or nonzero mod p, and a sign does not change that, so the identity and the rest of the proof stand. This is a faulty step under a stated result that still holds, so S3.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 2 Section 2, proof of Identity

  the coefficient of x^i in ((x − a)^p − (x^p − a)) is (−1)^i

Only the authors can say what is right here.

Judge's note: Read on page 2 image. My working: (x−a)^p = sum_i C(p,i) x^i (−a)^{p−i}, so the coefficient of x^i is (−1)^{p−i} C(p,i) a^{p−i}. Check with p=3, i=1: (x−a)^3 = x^3 − 3a x^2 + 3a^2 x − a^3, so the coefficient of x is +3a^2, while the printed formula gives −3a^2. For odd p the two signs differ. The proof only uses whether the coefficient vanishes mod p, so the stated Identity stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Proof of Theorem 5.1

  The first step (gcd computation) takes poly(log log r) asymptotic time.

• p. 7 Theorem 5.1 proof

  takes poly(log log r) asymptotic time

• p. 7

  (gcd computation) takes poly(log log r) asymptotic time.

Only the authors can say what is right here.

Judge's note: Checked the crop of p.7. In step 4 of the algorithm, gcd(n,r) is computed afresh for each r (text p.3/4, line 211). In the bit-operation model used elsewhere in the proof, this needs at least reading n, which is Ω(log n). Even after reducing n mod r it costs about Õ(log n · log r). The bound poly(log log r) = poly(log log log n) is therefore too small. The other steps in the same paragraph are costed with log log n, which suggests a slip. Charging Õ(log n) per iteration over O(log^6 n) iterations gives Õ(log^7 n). That is still below the stated Õ(log^9 n) for the while loop, so Theorem 5.1 stands, hence S3. One reviewer's 'repeated log' flag is a text-rule artefact: 'log log' is intended notation, not a duplicated word.

Second check: another model agreed, code check

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 8 Section 6, paragraph after Conjecture

  the product of prime numbers less than x is at least e^x (see [Apo97])

• p. 8 Section 6, justification of the search interval [2, 4 log n]

  the product of prime numbers less than x is at least e^x

Only the authors can say what is right here.

Judge's note: Checked the full p.8 image; the sentence is printed as quoted. Products of small primes show the inequality is false: at x=10 the product is 2·3·5·7 = 210 < e^10 ≈ 22026. In general the product is e^{θ(x)}, with θ(x) < x across checked ranges. The argument needs only a Chebyshev-type bound, for example a product of primes ≤ 4 log n of at least 2^{4 log n} = n^4 > n^2 − 1 for large n. With that bound, an r in [2, 4 log n] not dividing n^2 − 1 still exists, and the conditional Õ(log^3 n) claim stands. The printed justification step is false, but the result it supports survives, so S3, author_query. Which bound Apostol actually states is outside the files and was not checked.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send