4
$\begingroup$

How can I get inequalities that bound the prime counting function if I have the following inequalities for some functions $f(x)$ and $g(x)$: $ g(x)<\psi(x) where $\psi(x)$ is second Chebyshev function (the summatory function for the von Mangoldt function)?

  • 0
    Certainly calculus, to the point of comfort, even though there are few explicit integrals. There are no actual Fourier series, although that is one part of number theory. The kind of sums you find interesting require that much knowledge in any case.2012-11-23

2 Answers 2

3

Chapter 5 of this book contains a pretty nice walkthrough of Chebyshev's theorem (and the whole prime number theorem) that uses nothing but elementary number theory and combinatorics techniques to achieve such bounds.

  • 0
    I don't need bounds, I want to know how to take bounds and convert them into bounds for the prime counting function2012-11-25
7

Define: $\psi(x) = \sum_{n \le x} \Lambda(n) = \sum_{p^k \le x} \ln p$ $\theta(x) = \sum_{p \le x} \ln p$ $\pi(x) = \sum_{p \le x} 1$

We'll compare $\psi$ to $\theta$ and $\theta$ to $\pi$.

  • $\psi(x) - \theta(x) = \sum_{p^k \le x, k\ge 2} \ln p$. So in the sum we care only about primes that are at most $\sqrt{x}$. Each such prime $p$ appears in the sum $\lfloor \frac{\ln x}{\ln p} \rfloor -1$ times, so we can write it as follows: $\psi(x) -\theta(x) = \sum_{p \le \sqrt{x}} \ln p (\lfloor \frac{\ln x}{\ln p} \rfloor -1)$

Now there are a few options:

i. We can bound each term from above by $\ln x$, so $0 \le \psi(x) - \theta(x) \le \pi(\sqrt{x}) \ln x$ And then use the trivial bound $\pi(\sqrt{x}) \le \sqrt{x}$ bound, to find $\psi(x) - \theta(x) \le \sqrt{x}\ln x$.

ii. Similar to i, but use the Chebyshev bound $\pi(\sqrt{x}) = O(\frac{\sqrt{x}}{\ln x})$ to prove $\psi(x) - \theta(x) = O(\sqrt{x})$ (with constant around 2).

iii. A more involved argument shows that the real constant is around 1: Bound each term by $\ln x - \ln p$, so the difference becomes $\ln x \pi(\sqrt{x}) - \theta(\sqrt{x})$, which behaves like $\ln x \frac{\sqrt{x}}{\ln \sqrt{x}} - \sqrt{x} \sim \sqrt{x}$.

  • To understand the relation between $\pi$ and $\theta$ we need Abel Summation applied to $a_n = 1_{n \text{ is prime}}, b_n = \log n$. As $\theta(x) = \sum_{n \le x} a_n b_n$, we find: $\theta(m) = (\sum_{n \le m} a_n) b_{m} - \sum_{n < m} (b_{n+1}-b_{n}) (\sum_{i \le n} a_n) =$ $\pi(m) \ln m - \sum_{n < m} \ln(1 + \frac{1}{n}) \pi(n)$ (I worked with $m$ integer but it is true in general, up to some tiny error term.)

To bound the last sum, note that $0 \le \ln(1+\frac{1}{n}) \le \frac{1}{n}$ (it's pretty tight for large $n$), so $0 \le \sum_{n < m} \ln(1 + \frac{1}{n}) \pi(n) \le \sum_{n < m} \frac{\pi(n)}{n}$.

i. The trivial bound is $m$, which follows form $\pi(x) \le x$.

ii. A more complex one is $O(\sum_{n < m} \frac{1}{\ln n}) = O(\frac{m}{\ln m})$ (constant around 1), based on $\pi(x) = O(\frac{x}{\ln x})$, which is based of Chebyshev's estimates.

All in all, $\psi(x) = \pi(x) \ln x + O(\frac{x}{\ln x})$, so $g(x) < \psi(x) < f(x) \implies \frac{g(x)+O(\frac{x}{\ln x})}{\ln x} < \pi(x) < \frac{f(x)+O(\frac{x}{\ln x})}{\ln x}$. Precise error terms depend on what you're assumeing, but I believe the constant of the $O()$ is around $1$.