# Asymptotic of a sum evaluation as $x \to \infty$

Let be the sum

$$\sum_{n\le x}[x/n]=g(x)$$

where $[x]$ means floor function.

My best try for asymptotic is $g(x) \sim x\log (x)+\gamma x +1$

where I have used the asymptotic $[x] \sim x$ and $\sum_{n\le x}1/n=\gamma +\log(x)+1/x$.

Is there a way to improve this result ? Thanks.

• Note that $\sum_{n \leq x} 1/n = \log x + \gamma + 1/(2x) + O(1/x^2)$ (not $1/x$). Thus $\sum_{n \leq x} x/n = x\log x + \gamma x + 1/2 + O(1/x)$, but, even though $[x] \sim x$, you can not simply conclude that $\sum_{n \leq x} [x/n] = x\log x + \gamma x + 1/2 + O(1/x)$. – John M Jun 5 '14 at 19:40
• why not ?, what i have made wrong in my approximation – Jose Garcia Jun 6 '14 at 8:24
• You shouldn't be using $X \sim Y$ notation in your intermediate steps. It can lead to logical fallacies, especially for any secondary terms. Instead use big O, e.g. $X = Y + O(error)$. For example, write $[x/n] = x/n + O(1)$ instead of $[x/n] \sim x/n$. Then you can see that when you put $[x/n]$ in the sum $\sum_{n < x} [x/n]$, the error accumulates to $O(x)$, invalidating the lower order terms $\gamma x + 1$ that you wrote in your asymptotic expansion. – John M Jun 6 '14 at 12:51

ADDED LATER: Everything I originally wrote below was correct. However there is a much better way to look at this that I neglected to mention.

The most important feature of this sum is that it is equal to divisor summatory function $M_\tau$, $$\sum_{n \leq x} \left[\frac{x}{n}\right] = \sum_{n \leq x} \sum_{d \leq x/n} 1 = \sum_{dn \leq x} 1 = \sum_{m \leq x} \sum_{d | m} 1 = \sum_{m \leq x} \tau(m) = M_\tau(x),$$ where $\tau(m) = \sum_{d|m}1$ is the number of divisors of $m$.

Using the hyperbola method, we can easily get the bound $$\sum_{n \leq x} \left[\frac{x}{n}\right] = M_\tau(x) = x \log x + (2\gamma-1)x + O(x^{1/2}).$$

Of course, the divisor summatory function has been most intensively studied and better bounds are available. The best bound to date is by Huxley, who proved $$M_\tau(x) = x \log x + (2\gamma-1)x + O(x^{131/416 + \epsilon}).$$

The smallest $\theta$ for which the error term $O(x^{\theta+\epsilon})$ holds true is known as the Dirichlet divisor problem. Thus we know $\theta \leq 131/416$. But also Hardy and Landau showed that $\theta \geq 1/4$, which tells us that we should abandon our hope of ever having a constant term in our asymptotic expansion; there is no possible constant for which such an asymptotic can be true.

ORIGINAL ANSWER: So what you write is not quite correct.

Let $\{x\} = x - [x]$ denote the fractional part of $x$. Then $\{x\}=O(1)$ and $[x]=x+O(1)$. So we have a crude estimate, $$\sum_{n \leq x} \left[\frac{x}{n}\right] = \sum_{n \leq x} \left( \frac{x}{n} - \left\{\frac{x}{n}\right\} \right) = x\sum_{n \leq x} \frac{1}{n} + O\left(\sum_{n \leq x} 1 \right) = x\left(\log x + \gamma + \frac{1}{2x} + O(x^{-2})\right) + O(x) = x\log x + O(x),$$ so we have the asymptotic,

$$\sum_{n \leq x} \left[\frac{x}{n}\right] \sim x \log x.$$

This is the most that you can conclude without a more precise estimate of the sums of the fractional parts $\sum_{n \leq x}\{x/n\}$.

To attempt to get a more precise estimate, one interesting question to ask is what is $$\lim_{x \rightarrow \infty} \frac{1}{x} \sum_{n \leq x} \left\{\frac{x}{n}\right\} = \; ?$$ If we were to assume that the fractional parts were uniformly distributed, we would conclude that that the limit would be $1/2$. But that would be wrong! Somewhat surprisingly, that sum is in fact a Riemann sum, and can be written as an integral, $$\lim_{x \rightarrow \infty} \frac{1}{x} \sum_{n \leq x} \left\{\frac{x}{n}\right\} = \int_0^1 \left\{\frac{1}{t}\right\} \, dt.$$ The integrand is piecewise continuous, and we can break the integral into pieces, $$\int_0^1 \left\{\frac{1}{t}\right\} \, dt = \sum_{k=1}^\infty \int_{1/(k+1)}^{1/k} \left(\frac{1}{t} - k\right) \, dt = \sum_{k=1}^\infty \left( \log(k+1) - \log(k) - \frac{1}{k+1}\right) = \lim_{K \rightarrow \infty} \left( \log(K+1) - \sum_{k=1}^K \frac{1}{k+1} \right) = 1 - \gamma.$$ We conclude that $$\sum_{n \leq x} \left\{\frac{x}{n}\right\} \sim (1 - \gamma)x.$$ We can use this to refine our earlier estimate, $$\sum_{n \leq x} \left[\frac{x}{n}\right] = \sum_{n \leq x} \frac{x}{n} - \sum_{n \leq x} \left\{\frac{x}{n}\right\} = x\left(\log x + \gamma + \frac{1}{2x} + O(x^{-2})\right) - \left(1-\gamma+o(1)\right)(x) \\ = x\log x + (2\gamma -1)x + o(x).$$ Thus, we now have a more precise asymptotic,

$$\sum_{n \leq x} \left[\frac{x}{n}\right] \sim x\log x + (2\gamma -1)x.$$

Note we haven't justified a particular constant term in our asymptotic expansion.

• Since the sum is always an integer, I doubt we can get much better than $O(1)$ as an error. In fact, here is a plot of the errors up to $x=100000$. – robjohn Jun 6 '14 at 10:19