4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – John M Jun 5 '14 at 19:40
  • $\begingroup$ why not ?, what i have made wrong in my approximation $\endgroup$ – Jose Garcia Jun 6 '14 at 8:24
  • $\begingroup$ 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. $\endgroup$ – John M Jun 6 '14 at 12:51
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – robjohn Jun 6 '14 at 10:19

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.