1
$\begingroup$

Within the paper PRIMES is in P the following inequality can be found (on page 4, in the proof of Lemma 4.3) $$ n^{\lfloor \log(B) \rfloor} \prod_{i=1}^{\lfloor \log^2(n) \rfloor} (n^i - 1) \hspace{2mm} < \hspace{2mm} n^{\lfloor \log(B) \rfloor + \frac{1}{2} \log^2(n) (\log^2(n) - 1)} $$

This implies that $$ \prod_{i=1}^{\lfloor \log^2(n) \rfloor} (n^i - 1) \hspace{2mm} < \hspace{2mm} n^{\frac{1}{2} \log^2(n) (\log^2(n) - 1)} $$ However, I would have expected this inequality to be

$$ \prod_{i=1}^{\lfloor \log^2(n) \rfloor} (n^i - 1) \hspace{2mm} < \hspace{2mm} n^{\frac{1}{2} \log^2(n) (\log^2(n) + 1)} $$ (plus 1 at the end, rather than minus 1) due to the summation rule $$ \sum_{i=1}^n i = \frac{1}{2} n(n+1) \hspace{5mm} \Rightarrow \hspace{5mm} \prod_{i=1}^n n^i = n^{\frac{1}{2} n(n+1)} $$

Assuming I am wrong about this, how was the inequality formed?

$\endgroup$
4
  • $\begingroup$ You are right. When $\log n = \ell$ is an integer (below, I assume wlog $\log$ is in base 2), it is easy to find a counterexample. $n=4$, $\log n = 2$, $$\prod_{i=1}^4 (4^i-1) = 722925 > 4^{\frac{1}{2}\cdot 4\cdot 3} = 4096$$ $\endgroup$
    – Clement C.
    Commented Mar 7, 2018 at 20:40
  • $\begingroup$ @user328442 For big $n$, this is irrelevant: $$\prod_{i=1}^\ell (n^i -1) = e^{\sum_{i=1}^\ell \ln(n^i - 1)} = n^{\frac{\ell(\ell+1)}{2}}e^{\sum_{i=1}^\ell \ln(1 - 1/n^i)} = n^{\frac{\ell(\ell+1)}{2}} e^{O(1)}$$ compared to the $n^{\log^2 n}$ factor difference obtained by switching the sign of $\pm$ in the exponent. $\endgroup$
    – Clement C.
    Commented Mar 7, 2018 at 20:44
  • $\begingroup$ Also, note: the Annals of Mathematics version only states $$n \prod_{i=1}^{\lfloor\log^2 n\rfloor} (n^i -1) < n^{\log^4 n} \leq 2^{\log^5 n}$$ $\endgroup$
    – Clement C.
    Commented Mar 7, 2018 at 20:48
  • $\begingroup$ I found Granville much easier to read ams.org/journals/bull/2005-42-01/S0273-0979-04-01037-7/… $\endgroup$
    – Will Jagy
    Commented Mar 7, 2018 at 21:22

0

You must log in to answer this question.

Browse other questions tagged .