So I was reading a book in analytic number theory and there was this claim $$\sum_{a\leq x} 1/a =\log x+O(1)$$ and since we kinda skipped these big $O$ notation problems at early uni days I got wondering how I can be sure in something like this?

I mean I can see how $\sum_{a\leq x} 1/a \leq \log x$ holds but how can I be sure that the rest is $O(1)$?

Also if I take $\sum_{a\leq x} O(1)$, $O(1)$ I can get out of the sum and the sum is something that is less than $x$ so $O(x)$ so that gives me $O(1)O(x)$ which is $O(x)$, am I correct?

  • 2
    $\begingroup$ $$ \log n = \int_1^n {\frac{{dx}}{x}} < \sum\limits_{k = 1}^n {\frac{1}{k}} < 1 + \int_1^n {\frac{{dx}}{x}} = 1 + \log n $$ $\endgroup$
    – Gary
    Jun 15 at 11:04
  • $\begingroup$ Can you explain first how the first inequality holds and how this answers my question? $\endgroup$
    – MotionMath
    Jun 15 at 11:11
  • $\begingroup$ Note that $$ \sum\limits_{k = 1}^n {\frac{1}{k}} = \sum\limits_{k = 1}^n {\int_k^{k + 1} {\frac{{dx}}{k}} } \ge \sum\limits_{k = 1}^n {\int_k^{k + 1} {\frac{{dx}}{x}} } = \int_1^{n + 1} {\frac{{dx}}{x}} = \log (n + 1) > \log n. $$ The inequalities show that $\sum\nolimits_{k = 1}^n {\frac{1}{k}} - \log n$ is bounded, i.e., $$ \sum\limits_{k = 1}^n {\frac{1}{k}} = \log n + \mathcal{O}(1). $$ $\endgroup$
    – Gary
    Jun 15 at 11:16
  • $\begingroup$ Does this help math.stackexchange.com/questions/4139408/…? $\endgroup$
    – zkutch
    Jun 15 at 13:57

To summarize the comments to this question and add one bit of extra info, the notation $$ f(x) = O(g(x)) $$ is defined to mean that $\left| f(x)\right| \leq C g(x)$, where $C$ is a constant independent of $x$. For your specific question, one needs to show that for some suitable constant $C$, we have $$ \left| \sum_{a \leq x} \frac{1}{a} - \log x\right| \leq C. $$ From the comments provided by Gary, we have precisely this inequality with $C = 1$. In fact, one can use partial summation to deduce that $$ \sum_{a \leq x} \frac{1}{a} = \log x + \gamma + O\left(\frac{1}{x}\right), $$ where $\gamma$ denotes the Euler-Mascheroni constant. In general, when dealing with the sums $$ \sum_{a\leq x} f(a) $$ where $f$ is differentiable (or, say, continuously differentiable $k$ times), you should expect the sum above to be comparable to the integral $$ \int_{1}^{x} f(t) dt. $$ Indeed, this is precisely the content of the Euler-Maclaurin summation formula.

By a more careful analysis, one can obtain an asymptotic expansion of the sum above with an arbitrarily small error term. For instance, if $\psi(x) = \left\{ x\right\} - \frac{1}{2}$, where $\left\{ x\right\}$ denotes the fractional part of $x$, then $$ \sum_{a \leq x} \frac{1}{a} = \log x + \gamma - \frac{\psi(x)}{x} + O\left(\frac{1}{x^2}\right). $$


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.