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

  • 1
    $\begingroup$ What about $c_n=1,c_1=c_2...c_{n-1}=0$? Or $c_n=1$ and the rest of the sum vanishing? $\endgroup$ – joro Sep 17 '15 at 12:02
  • $\begingroup$ @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. $\endgroup$ – Pablo Sep 17 '15 at 12:16
  • 6
    $\begingroup$ 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$. $\endgroup$ – David E Speyer Sep 17 '15 at 12:49
  • 1
    $\begingroup$ What happens if we use (perhaps scaled) Chebyshev's polynomials? $\endgroup$ – Ilya Bogdanov Sep 17 '15 at 12:52
  • 1
    $\begingroup$ @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. $\endgroup$ – Igor Rivin Sep 17 '15 at 13:06

This question (with copious references, summarizing the progress to date, with best constants) is dealt with in this 2013 paper by D. Bazzanella.

| cite | improve this answer | |
  • 1
    $\begingroup$ What about giving short summary related to the question? $\endgroup$ – joro Sep 17 '15 at 13:21
  • 1
    $\begingroup$ @joro why? The paper is short, the relevant summary is somewhere in the first page, and all you have to do is click on the link. $\endgroup$ – Igor Rivin Sep 17 '15 at 13:23
  • 7
    $\begingroup$ My suggestion would make your answer more self contained. $\endgroup$ – joro Sep 17 '15 at 13:24
  • 4
    $\begingroup$ 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"... $\endgroup$ – David E Speyer Sep 17 '15 at 13:50

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.