Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can someone find a function f(n) satisfieing these bounds? Can you also prove that it does? $$ \sum\limits_{k=1}^n \Lambda(k) [1-\text{Frac}(\frac{n}{k})][1-\frac{k}{n}\text{Frac}(\frac{n}{k})]=\frac{1}{2}\sum\limits_{k=1}^n \Lambda(k){}\text{}+O(f(n)),\text{ Such that:}\lim_{n\to\infty}f(n)/n=0$$

Where $\displaystyle \text{Frac}(\frac{n}{k})$ is the fractional part of $\displaystyle \frac{n}{k}$, and where $\Lambda(k)$ is the Von-Mangoldt function. I know that a function does exist, I just cant prove that it does. I would Greatly appreiciate any help though, and if someone could even give me an elementary proof I would be willing to do somthing for them in return.

share|cite|improve this question

I doubt there is a reasonable elementary proof. Note that the left-hand sum equals $$ \sum_{F=1}^n \sum_{n/(F+1)<k\le n/F} \Lambda(k)[1-(\tfrac nk-F)][1-\tfrac kn(\tfrac nk-F)] = \frac1n \sum_{F=1}^n F \sum_{n/(F+1)<k\le n/F} \Lambda(k)[(F+1)k-n]. $$ If we let $\psi(x) = \sum_{1\le n\le x} \Lambda(n)$, then the inner sum can be written as a Riemann-Stieltjes integral $$ \sum_{n/(F+1)<k\le n/F} \Lambda(k)[(F+1)k-n] = \int_{n/(F+1)}^{n/F} [(F+1)x-n] \, d\psi(x), $$ which after integration by parts equals \begin{align*} \sum_{n/(F+1)<k\le n/F} \Lambda(k)[(F+1)k-n] &= [(F+1)x-n]\psi(x) \bigg|_{n/(F+1)}^{n/F} - \int_{n/(F+1)}^{n/F} \psi(x) \tfrac d{dx}[(F+1)x-n] \,dx \\ &= \psi(\tfrac nF) - (F+1) \int_{n/(F+1)}^{n/F} \psi(x) \,dx. \end{align*} (And this formula, once suspected, can be proved in an elementary fashion without needing to use Riemann-Stieltjes integrals.) In summary, your left-hand sum equals $$ \frac1n \sum_{F=1}^n F \bigg( \psi(\tfrac nF) - (F+1) \int_{n/(F+1)}^{n/F} \psi(x) \,dx \bigg). $$ So far this is all elementary; and if you define $E(x) = \psi(x) - x$, then this becomes \begin{multline*} \frac1n \sum_{F=1}^n F \bigg( \tfrac nF - (F+1) \int_{n/(F+1)}^{n/F} x \,dx \bigg) + \frac1n \sum_{F=1}^n F \bigg( E(\tfrac nF) - (F+1) \int_{n/(F+1)}^{n/F} E(x) \,dx \bigg) \\ = \frac12 + \frac1n \sum_{F=1}^n F \bigg( E(\tfrac nF) - (F+1) \int_{n/(F+1)}^{n/F} E(x) \,dx \bigg) \end{multline*} after some easy evaluation.

However, I don't know how to proceed further without plugging in the Prime Number Theorem, say in the form $|E(x)| \le C(A) x/(\log x)^A$ for any $A>0$ and some constant $C(A)$ depending on $A$.

share|cite|improve this answer
If I could reduce the prime number theorem to this problem, do you think it would be worth pursuing? Also are Riemann-Stieltjes integrals considered elementary? – boby Oct 26 '12 at 9:55
Personally, I think this problem is slightly harder than the prime number theorem (where the summand is simply $\Lambda(k)$). So reducing PNT to this problem isn't likely to be fruitful in my opinion. Riemann-Stieltjes integrals are more or less as elementary as regular Riemann integrals - they're just less common. The good news is, the formula I derived using R-S integrals can be verified using nothing more than first-year calculus. (Also, "elementary" isn't a firm label, so deciding whether a method is or isn't elementary isn't that mathematically significant.) – Greg Martin Oct 26 '12 at 21:29
What is meant by the letter F? does that denote the fractional part of n/k? or what? – user47704 Oct 31 '12 at 18:49
$F$ is simply an index of summation (see the $\sum_{F=1}^n$?). In the first step, it equals the integer part of $n/k$; thereafter, it's simply an integer parameter. – Greg Martin Nov 3 '12 at 5:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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