I'm working on understanding Nagura's analysis of the upper bound for $\psi(x)$ which is done in Lemma 2. I am unclear on one step of his reasoning.

With Lemma 1, he establishes for $x \ge 2000$:

$$\log\Gamma(\lfloor{x}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{2}}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{3}}\rfloor+1)- \log\Gamma(\lfloor{\frac{x}{7}}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{43}}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{1806}}\rfloor+1) < 1.0851x$$

With Lemma 2, he shows that for $x > 0$:

$$\log\Gamma(\lfloor{x}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{2}}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{3}}\rfloor+1)- \log\Gamma(\lfloor{\frac{x}{7}}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{43}}\rfloor+1) - \log\Gamma(\lfloor{\frac{x}{1806}}\rfloor+1) \ge \psi(x) -\psi(\frac{x}{1806})$$

Now, it's the next step that confuses me. Based on these two steps, Nagura makes the following argument:

$$\psi(x) < 1.0851(x + \frac{x}{1806} + \frac{x}{1806^2} + \frac{x}{1806^3} + \ldots ) < 1.086x$$

I am having trouble understanding this step.

Does it follow since he has established this step:

$$\psi(x) < 1.0851x + \psi(\frac{x}{1806})$$

And is trying to generalize to a statement of the form:

$$\psi(x) < Kx$$




A second application of the inequality $$\psi(x) <1.0851x+\psi\left(\frac{x}{1806}\right)$$ gives $$\psi(x) < 1.0851x\left(1+\frac{1}{1806}\right)+\psi\left(\frac{x}{1806^2}\right)$$ In general, induction gives $$\psi(x) < 1.0851x \left(1+\frac{1}{1806} + \frac{1}{1806^2} + \ldots + \frac{1}{1806^k}\right)+\psi \left( \frac{x}{1806^{k+1}}\right).$$ For $k$ sufficiently large, we have $1806^{k+1} > x$, at which point the $\psi$-term is $0$, which gives the bound $$\psi(x) < 1.0851x\sum_{j=0}^\infty \frac{1}{1806^j}.$$

Historical note: this technique was first used by Chebyshev, who showed $$0.9212x< \psi(x) < 1.1056x$$ for large $x$ to prove Bertrand's postulate (as well as give the correct growth order of $\pi(x)$). Nagura uses a different approximation function of $\log \mathrm{lcm}(1,\ldots,n)$, and thus achieves different constants. I wrote an article that includes general constructions of this form, as well as historical notes; it can be found here.

  • $\begingroup$ Thanks so much for the link to the article. This is exactly the information that I was looking for. Cheers. :-) $\endgroup$ – Larry Freeman May 2 '13 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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