# An elementary lower bound on the number of primes

Recall the second Chebyshev function: $$\psi(x) = \sum_{p \leq x} \lfloor \log_p x \rfloor \log p$$ where $x$ is a positive integer, and $p$ runs over all primes $\leq x$.

In a hunt for an "elementary" lower bound on the number of primes up to some $x \in \mathbb{N}$, it is sufficient to find a lower bound for $\psi(x)$ in view of its connection with the prime counting function $\pi(x)$. We can work instead with $$e^{\psi(n)} = \mathrm{lcm} (1, \dots, n)$$ for $n \in \mathbb{N}$, and try to bound it from below. This can be done by observing that for any $c_1, \dots, c_n \in \mathbb{Z}$ we have $$e^{\psi(n)}\sum_{i=1}^{n}\frac{c_i}{i} = \mathrm{lcm} (1, \dots, n)\sum_{i=1}^{n}\frac{c_i}{i} \in \mathbb{Z}$$ from which we conclude, in case that the sum does not vanish, that $$e^{\psi(n)} \geq \frac{1}{|\sum_{i=1}^{n}\frac{c_i}{i}|}$$.

Therefore, my question is:

Given $n \in \mathbb{N}$, how small can we make $|\sum_{i=1}^{n}\frac{c_i}{i}|$ (as a function of $n$) using $c_1, \dots, c_n \in \mathbb{Z}$ without making it zero?

I want to see choices of $\{c_i\}_{i=1}^n$ which are not necessarily explicit, but preferably elementary. I understand that bounds on this sum can be obtained using the prime number theorem, but this is not what I am looking for. Note also that $$\sum_{i=1}^{n}\frac{c_i}{i} = \int_{0}^1 \sum_{i=1}^{n}c_ix^{i-1}$$ so in some sense we are minimizing nonvanishing integrals of integral polynomials of degree at most $n$. Here is an example:

Take some $m \in \mathbb{N}$ and set $n = 2m+1$. Note that $$0 < \int_{0}^1 x^m(1-x)^m \leq \frac{1}{4^m} = \frac{1}{4^{\frac{n-1}{2}}}$$ so indeed one way to tackle this is by working with positive valued polynomials. The latter (simple) bound already shows that $\pi(x) \geq \frac{x}{3 \log x}$.

• What about $c_n=1,c_1=c_2...c_{n-1}=0$? Or $c_n=1$ and the rest of the sum vanishing? – joro Sep 17 '15 at 12:02
• @joro this is a pretty weak lower bound. Even the example I have given in the question attains a better one. I meant that the sum should be small as a function of $n$ - I have edited now. Thanks for your remark. – Pablo Sep 17 '15 at 12:16
• Here is something dumb which confused me: there do exist some $c_i$ such that $\sum_{i=1}^n c_i/i = 1/LCM(1, \ldots, n)$, which can be computed by the Chinese remainder theorem. The point of the question is not this sort of vacuous answer, but rather to find simple explicit $c_i$. – David E Speyer Sep 17 '15 at 12:49
• What happens if we use (perhaps scaled) Chebyshev's polynomials? – Ilya Bogdanov Sep 17 '15 at 12:52
• @IlyaBogdanov... but Mathematica tells me that the integral of $T_n(x)$ is $\frac{n \sin \left(\frac{\pi n}{2}\right)-1}{n^2-1},$ so too big. – Igor Rivin Sep 17 '15 at 13:06

• If we bound $\int_0^1 f(x) dx \leq \max_{x \in [0,1]} |f(x)|$, then the best possible value for the latter is $\exp(-(C+o(1)) n)$ for some $C \in (0.85991,0.86441)$. See page 3 of the paper for many references. The OP achieves $C = \log 2 \approx 0.693$; proving PNT requires $C=1$. It seems hard to me to think about what happens if you don't make those initial simplifications. This comment isn't a criticism of Igor. Rather, I was going to write "why don't YOU summarize the paper" and then I thought "wait a minute"... – David E Speyer Sep 17 '15 at 13:50