# The Second Moment of a Sum of Floor Functions

The following well known identity, where $\tau(n)$ denotes the number of divisors of $n$ appears in many number theory texts $$\sum_{k=1}^n \tau(k) = \sum_{d=1}^n \lfloor n/d \rfloor,$$ and follows from the observation that "one out of d" integers in $\{1,2,\ldots,n\}$ are multiples of $d$ and then summing along rows $d$ as well as along columns $k$ the indicator function $1\{~ d~\mathrm{divides}~k~\}$.

Is there a good approximation, or are there any identities related to the following sum, preferably containing arithmetic functions? $$\sum_{d=1}^n \lfloor n/d \rfloor^2$$

-
The sequence isn't in OEIS if I computed it correctly. –  joro Apr 22 '12 at 9:51

Sums of this sort are well known to the experts - but since none of them have answered so far, let me try. Denoting the fractional part of a real $x$ by $\{x\}$, you can write your sum as $$S = n^2 \sum_{d=1}^n \frac1{d^2} - 2n \sum_{d=1}^n \frac1d\left\{\frac nd\right\} + \sum_{d=1}^n \left\{\frac nd\right\}^2 = \frac{\pi^2}{6}\, n^2 + O(n\log n).$$

If you need more precision, you have to find the main term of the sum $\sum_d d^{-1}\{d^{-1}n\}$. The standard technique here, I believe, would be to use the Fourier expansion of the fractional part function, but you'd better contact experts for details, to avoid re-inventing the wheel.

Here is a different kind of answer, depending on what you are after. Your sum counts the number of triples $d,x,y\in[1,n]$ with $xd,yd\le n$. Since there are $\sum_{k=1}^n \tau(k)$ such triples with $x=y$, splitting the sum into two part according to whether $x\ge y$ or $y\ge x$, we can write it as $$S = 2 \sum_{dx\le n} x - \sum_{k=1}^n \tau(k).$$
Letting $k=dx$, we get $$S = 2 \sum_{k=1}^n \sigma(k) - \sum_{k=1}^n \tau(k),$$ where $\sigma$ is the sum-of-divisors function. This gives you an identity containing arithmetic functions'', as you requested.

-
@Seva: Thank you that's very helpful, and I will look into the fourier expansion of the fractional part function –  kodlu Apr 22 '12 at 21:20
See my response for a supplement. –  GH from MO Apr 23 '12 at 0:58
Looks like you haven't escaped "{" in: Denoting the fractional part of a real $x$ by $x$. –  joro Apr 23 '12 at 5:18
@joro: have fixed it now, thanks. For some reason, I never get a math preview when editing an answer. –  Seva Apr 23 '12 at 7:37

This is a supplement to Seva's answer. The error term $O(n\log n)$ can be improved, but not considerably. $S$ is the summatory function of $2\sigma(k)-\tau(k)$ which exceeds $k\log\log k$ infinitely often, hence there is no continuous approximation to $S$ with an error less than $n\log\log n$. For $\sum_{k=1}^n\tau(k)$ the error can be improved to $(2\gamma-1)n+O(n^{7/22})$ or even better, but for $\sum_{k=1}^n\sigma(k)$ the best known error is $O(n(\log n)^{2/3})$, due to Walfisz (1963). See Chapter I.3 in Tenenbaum's Introduction to analytic and probabilistic number theory.

-
@GH: Thanks. How would the answers change if the upper limit of the sum was $v=v(n)$ for some positive, monotone function of $n$ satisfying $1< v(n) < n$? And what if the moment wasn't second but a higher moment? Perhaps $k=3,4$ and the sum was generalized to $$\sum_{d=1}^{v} \lfloor n/d \rfloor^k$$ And where can I find information, if any, on the fourier expansion of the fractional part function? –  kodlu Apr 23 '12 at 1:47
@kodlu: Smaller terms do not necessarily yield a better error term. For example, the error term in the summatory function of the Mobius function is extremely tricky, closely connected to the Riemann Hypothesis. Regarding your second question: each moment is a different story. You see, my response only supplements Seva's which describes your sum in more arithmetic terms. The Fourier expansion of the fractional function is classical, see e.g. en.wikipedia.org/wiki/… Of course the coefficients don't decay fast as the function is not continuous. –  GH from MO Apr 23 '12 at 4:05

On your comment concerning the sum $\sum_{d\leq n}\lfloor{n/d}\rfloor^k$ for various values of $k$

$$\sum_{n\leq x}[\frac{x}{n}]^k=\sum_{n\leq x}\sum_{m\leq \frac{x}{n}}m^{k}-(m-1)^k=\sum_{n\leq x}\sum_{d\mid n}d^k-(d-1)^k$$

And since, $$\sum_{d\mid n} d^k-(d-1)^k=\sum_{d\mid n}(d^k-\sum_{j=0}^k\binom{k}{j}d^{k-j}(-1)^j)=\sum_{d\mid n}\sum_{j=1}^k \binom{k}{j}d^{k-j}(-1)^{j-1}$$

We get that, $$\sum_{n\leq x}[\frac{x}{n}]^k=\sum_{j=1}^k\binom{k}{j}(-1)^{j-1}\sum_{n\leq x}\sigma_{k-j}(n)$$ For all $k\ge 1$

-