MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Let $g(n)$ be the maximal order of a permutation of n objects

RH Equivalence 3.3. The Riemann Hypothesis is equivalent to $\log{g(n)} < Li^{-1} (n)$ for n large enough.

$Li$ is strictly increasing for $n>1$ and $\log{g(n)} \sim \sqrt{n \log{n}}$.

$\log{g(n)} \ge \sqrt{n \log{n}}$ for $n \ge 906$ and $\log{g(n)} \gg 1$.

Some equivalences using the fact that $Li$ and squaring preserve inequalities (because they are strictly increasing in the relevant intervals, easy to show) are:

$$ \log{g(n)} < \sqrt{Li^{-1}(n)} \iff (\log{g(n))^2 < Li^{-1}(n) \iff Li( (\log{g(n)})^2}) < n \qquad (1) $$

for $n$ large enough.

In Effective Bounds for the Maximal Order of an Element in the Symmetric Group Theorem 2, p. 2 the following bound for $g(n)$ is given unconditionally for $n \ge 3$:

$$\log{g(n)} \le F(n) = \sqrt{n \log{n}} \left( 1 + \frac{\log{\log{n}} - 0.975}{2 \log{n}}\right) $$

$$\log{g(n)} \le F(n) \iff (\log{g(n)})^2 \le F(n)^2 \iff Li((\log{g(n)})^2) \le Li(F(n)^2) \qquad (1a)$$

From (1) and (1a) showing $ Li( (\log{g(n)) ^2}) \le Li(F(n)^2) < n $ (if true) will prove (1).

Let $$ G(n) = Li(F(n)^2) - n = $$

$$ -n + {Li}\left(\frac{1}{4} \, {\left(\frac{\log\left(\log\left(n\right)\right) - 0.975}{\log\left(n\right)} + 2\right)}^{2} n \log\left(n\right)\right) =$$

$$ -n + {\rm Ei}\left(\log\left(\frac{1}{4} \, {\left(\frac{\log\left(\log\left(n\right)\right) - 0.975}{\log\left(n\right)} + 2\right)}^{2} n \log\left(n\right)\right)\right) - {\rm Ei}\left(\log\left(2\right)\right) $$

We must show $$G(n)<0 \qquad (2)$$ (if true) for $n$ large enough.

According to both sage and maple (using the $\rm Ei$ expression) $\lim_{n \to \infty} G(n) = -\infty$ so (2) may fail at most finitely often ($n \in \mathbb{N}$).

The derivative of $G(n)$ is of elementary functions only.

What are the mistakes and logical errors in this?

share|cite|improve this question
up vote 8 down vote accepted

I suspect the mistake is in relying on Sage or Maple in the last step. Instead use the asymptotic expansion of li(x) ( ) $$\operatorname{li}(x)=\frac x {\log x}+\frac{x}{\log^2 x}+O \left(\frac x {\log^3 x} \right)$$ to obtain an asymptotic expression of $G(n)$. Letting $$x=\frac 1 4 \left(\frac {\log \log n-0.975}{\log n}+2 \right)^2 n \log n$$ we see that $$x = n \log n \left(1+\frac{\log \log n}{\log n}- \frac{0.975}{\log n} +O \left( \frac{\log \log n}{\log^2 n} \right) \right) $$ and that $$\log x=\log n+\log \log n+\frac{\log \log n}{\log n}-\frac{0.975}{\log n}+O \left(\frac {\log \log n}{\log^2 n} \right).$$ With some more calculation we get $$\frac x {\log x}=n-\frac{0.975 n}{\log n}+O \left(\frac {n \log \log n}{\log^2 n} \right) $$ By the first two terms in the asymtotic expansion of li(x) we get that $$ \operatorname{li} (x)=n+\frac{0.025n}{\log n}+O \left(\frac {n \log \log n}{\log^2 n} \right) $$ and thus $$G(n)=\frac{0.025 n}{\log n}+O \left(\frac {n \log \log n}{\log^2 n} \right) $$ and $G(n) \to \infty$ as $n\to \infty$.

share|cite|improve this answer
Thank you ${}{}{}$ – joro Jul 27 '12 at 8:52

Don't blame Maple (blame the user).


share|cite|improve this answer
Thank you! I confirm this on version 13. Can you try without "MultiSeries" and writing Li in terms of Ei (that is what worked for me). – joro Jul 27 '12 at 8:51
$$\tt{> G := -n+Ei(1/4*((log(log(n))-0.975)/log(n)+2)^2*n*log(n))-Ei(log(2)):}$$ $$\tt{> limit(G,n=infinity);}$$ $$\tt{Float(infinity)}$$ – Gerald Edgar Jul 27 '12 at 14:13
Thank you. The last result is certainly different in version 13. – joro Jul 27 '12 at 14:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.