Inequality in "PRIMES is in P"

69 Views Asked by At

I'm having trouble verifying an inequality that is claimed in "PRIMES is in P" (Annals of Mathematics, 160 (2004), 781-793).

I'll state it in such a way that it can be understood without the paper, but for the curious it is in the middle of the proof of Lemma 4.3.

Assume that $n$ is an integer satisfying $n \geq 3$. Then it is claimed that $$n \cdot \prod_{i=1}^{\lfloor \log^2 n \rfloor} (n^i-1) < n^{\log^4 n}.$$ Here the log functions means the base-$2$ logarithm.

It is easy to verify a somewhat weaker inequality. Namely, each term in the product is at most $n^{\log^2 n}-1$, so we have $$n \cdot \prod_{i=1}^{\lfloor \log^2 n \rfloor} (n^i-1) \leq n \cdot (n^{\log^2 n}-1)^{\log^2 n} < n \cdot (n^{\log^2 n})^{\log^2 n} = n^{\log^4 n +1}.$$ However, try as I might I cannot seem to get rid of the $1$ in the exponent.