Intereting Posts

approximating a maximum function by a differentiable function
Is there such thing as an unnormed vector space?
Perfect set without rationals
Linear Algebra, add these two matrices
Estimate number of solutions in the Roth's theorem
Indefinite integral of product of CDF and PDF of standard normal distribution
Is every entire function is a sum of an entire function bounded on every horizontal strip and an entire function bounded on every vertical strip?
Understanding Vacuously True (Truth Table)
Is there a $k$ for which $k\cdot n\ln n$ takes only prime values?
Construct a metric for the topology of compact convergence on $Y^{X}$ so that $Y^{X}$ is complete when $(Y,d)$ is complete and $X$ is $\sigma$-compact
Finding sine of an angle in degrees without $\pi$
Are projective modules “graded projective”?
Prove that the field F is a vector space over itself.
Inequality with monotone functions on power set
Wolfram Alpha can't solve this integral analytically

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)<f(x), $$ where $\psi(x)$ is second Chebyshev function (the summatory function for the von Mangoldt function)?

- Prime factorization knowing n and Euler's function
- writing $pq$ as a sum of squares for primes $p,q$
- Show that a Sophie Germain prime $p$ is of the form $6k - 1$ for $p > 3$
- Prove nth root of n! is less than n+1 th root of ((n+1) !): $\sqrt{n!}\lt \sqrt{(n+1)!}$?
- Quadratic Gauss Sum
- Proof without induction of the inequalities related to product $\prod\limits_{k=1}^n \frac{2k-1}{2k}$
- a new continued fraction for $\sqrt{2}$
- Can a Mersenne number be a power (with exponent > 1) of a prime?
- $A,B$ be Hermitian.Is this true that $tr\le tr(A^2B^2)$?
- Show that for any integer $n\ge 6$, the inequality $2^n>7n$ holds.

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.

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$.

- Is there a nodeless graph?
- Why are $L^p$-spaces so ubiquitous?
- How to evaluate $\int\int_SF.dS$ where $F=(xz,yz,x^2+y^2)$?
- A function that is $L^p$ for all $p$ but is not $L^\infty$?
- Closed set in $\ell^1$
- Product of one minus the tenth roots of unity
- Correct notation for “for all positive real $c$”
- (dis)prove:$\sup_{F \in 2^{(L^1(S,\mathbb{R}))}}\limsup\sup_{f\in F}|\int f dP_n-\int fdP|=\limsup\sup_{f\in L^1(S,\mathbb{R})}|\int fdP_n-\int fdP|$
- Trying to generalize an inequality from Jitsuro Nagura: Does this work?
- Evaluate $\int_0^1 \frac{\log \left( 1+x^{2+\sqrt{3}}\right)}{1+x}\mathrm dx$
- Research in differential geometry
- Difference between elementary submodel and elementary substructure
- On an informal explanation of the tangent space to a manifold
- Showing $\sum_{i = 1}^n\frac1{i(i+1)} = 1-\frac1{n+1}$ without induction?
- The king comes from a family of 2 children. What is the probability that the other child is his sister?