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

Suppose I have either of the following expressions:

$$\newcommand{\rd}{\mathrm{d}} \int\nolimits_1^n\int\nolimits_1^\frac{n}{x} \,\rd y\, \rd x - \sum_{x=2}^n\sum_{y=2}^\frac{n}{x}1 $$

$$ \int\nolimits_1^n\int\nolimits_1^\frac{n}{x} \log y \,\rd y\, \rd x - \sum_{x=2}^n\sum_{y=2}^\frac{n}{x}\log y $$

Are there any simpler forms I could convert either of these into? Or any other ways of expressing these that might yield insight or let me work with them in other interesting ways?

I already know there are several different ways of rewriting just the integrals on the left in isolation ($ n \log n - n + 1 $ at the simplest for the first one, for example), but I'm really looking for expressions that capture the difference between the continuous and the discrete here, kind of the way Euler-Maclaurin summation does.

share|cite|improve this question
up vote 5 down vote accepted

The double sum $S_n$ in your first expression is $$ S_n=\sum\limits_{i=2}^n\sum\limits_k\left[2\leqslant k\leqslant\left\lfloor n/i\right\rfloor\right]=\sum\limits_{i=2}^n\int\left[1\leqslant y\leqslant\lfloor n/i\rfloor\right]\mathrm dy, $$ hence $$ S_n=\int_1^n\int_1^{u_n(x)}\mathrm dy\mathrm dx,\qquad u_n(x)=\left\lfloor n/\lceil x\rceil\right\rfloor. $$ The difference between the integral $I_n$ and the sum $S_n$ is $$ I_n-S_n=\int_1^n\int_{u_n(x)}^{n/x}\mathrm dy\mathrm dx=\int_1^n((n/x)-u_n(x))\mathrm dx. $$ Since $u_n(x)\leqslant n/x$ for every $x$ in $(1,n)$, a consequence of this formula is that $I_n-S_n\geqslant0$. Another consequence is that $I_n-S_n=nJ+o(n)$ when $n\to\infty$, with $$ J=\int_0^1((1/x)-\lfloor 1/x\rfloor )\mathrm dx=\int_1^{+\infty}(x-\lfloor x\rfloor )\frac{\mathrm dx}{x^2}. $$ As noted by @Andrew, writing $J$ as a sum of integrals from $n$ to $n+1$ and then as a series gives $$ J=\lim\limits_{n\to\infty}\left(\log(n)-\sum\limits_{k=2}^n\frac1k\right)=1-\gamma, $$ where $\gamma$ is Euler's constant hence $\gamma=0.577\ldots$ and $J=0.423\ldots$

share|cite|improve this answer
Something must be amiss here, because empirically $I_n - S_n >= 0$ for all values I've checked. In fact, the integral was intended to be the curve bounding all lattice squares of the two sums and no other lattice squares. You can see the two compared here: . I think maybe the leading minus sign is out of place. Otherwise, this expression makes sense, although I'm not sure I'll have much better luck working with it. – Nathan McKenzie Oct 20 '11 at 3:25
Right. Corrected. Thanks. A practical consequence is the equivalent $nJ+o(n)$. – Did Oct 20 '11 at 5:00
Writing $J$ as sum of integrals from $n$ to $n+1$ and then as series gives $J= \sum _{n=1}^{\infty } \left(\log \left(\frac{1}{n}+1\right)-\frac{1}{n+1}\right)=1-\gamma\ \ $. A bit more tinkering gives $I_n-S_n=(1-\gamma) n-\frac{1}{2}+o(1)\ $. – Andrew Oct 20 '11 at 7:09
@Andrew, thanks, I appended your remarks to the post. – Did Oct 20 '11 at 8:08
I think that that $o(1)$ has to be too small (though I wish it weren't). $S_n$ is related to the Dirichlet divisor problem - $S_n = \sum_{i=1}^n d(i) - 2 n + 1$, and I think the error term is known to be no smaller than $o(n^\frac{1}{4})$ . Ultimately, I want to use either expression I wrote as parts of larger sums (consisting of related expressions with deeper and deeper sum / integral nesting), so error terms in isolation matter less to me than having new possible ways to manipulate them, if that makes sense. – Nathan McKenzie Oct 20 '11 at 9:46

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.