34
$\begingroup$

How close can $S(n) = \sum_{k=1}^n \sqrt{k}$ be to an integer? Is there some $f(n)$ such that, if $I(x)$ is the closest integer to $x$, then $|S(n)-I(S(n))|\ge f(n)$ (such as $1/n^2$, $e^{-n}$, ...).

This question was inspired by the recently proposed and answered question of "prove that $\sum_{k=1}^n \sqrt{k}$ is never an integer/". The question is here: Is $\sqrt1+\sqrt2+\dots+\sqrt n$ ever an integer?

The Euler-Maclaurin estimate for $S(n)$ might be useful. According to an answer here, (the link is "How to calculate the asymptotic expansion of $\sum \sqrt{k}$?") $$S(n) = \frac{2}{3} n^{3/2} + \frac{1}{2} n^{1/2} + C + \frac{1}{24} n^{-1/2} + O(n^{-3/2})$$ where $C=\zeta(-\frac 12)\approx-0.207886224977...$.

$\endgroup$
  • $\begingroup$ How I interpret the question is whether there is a nice closed form $f$ that we can prove works. We know that $f$ can be taken to be positive. We know from André's answer that $\liminf\limits_{n\to\infty}\dfrac{f(n)}{n^{1/4}}\lesssim 1$. (The part made explicit is that $\liminf\limits_{n\to\infty}f(n)=0$, but the method gives the stronger fact that $f(n)\lesssim \dfrac{1}{n^{1/4}}$ infinitely often.) But this doesn't answer the quesiton about what $f$ does work, in particular whether say $n^{-2}$ or $e^{-n}$ would work. Steven Stadnicki suggests that even $\dfrac{1}{\sqrt n}$ might work. $\endgroup$ – Jonas Meyer Jul 13 '13 at 6:30
  • $\begingroup$ I mention this partly because although I think that André's answer is a valuable contribution here, it doesn't show any $f$ that gives a lower bound for your sequence, so I didn't understand why it was accepted so quickly as answering the question. $\endgroup$ – Jonas Meyer Jul 13 '13 at 6:32
  • $\begingroup$ I meant $\dfrac{f(n)}{n^{-1/4}}$ (or $f(n)n^{1/4}$) where I wrote $\dfrac{f(n)}{n^{1/4}}$. $\endgroup$ – Jonas Meyer Jul 13 '13 at 6:52
  • $\begingroup$ I'm easy. I would rather accept too much than not accept correct answers, which really annoys me. $\endgroup$ – marty cohen Jul 13 '13 at 13:05
  • $\begingroup$ Thanks. I don't really understand, but what you accept on your question is your business. $\endgroup$ – Jonas Meyer Jul 13 '13 at 17:19
15
$\begingroup$

Thanks Marty for a fascinating question. We can get the entire asymptotic expansion quite easily using Mellin transforms.

Start with the telescoping sum $$ S(x) = \sum_{k\ge 1} \left(\sqrt{k}-\sqrt{x+k}\right)$$ which has the property that $$ S(n) = \sum_{q=1}^n \sqrt{q}$$ so that $S(n)$ is the value we are looking for.

Now re-write the inner term so that we can see the harmonics: $$ \sqrt{k}-\sqrt{x+k} = \sqrt{k}\left(1-\sqrt{x/k+1}\right).$$

Now recall that $$\mathfrak{M}\left(\sum_{k\ge 1} \lambda_k g(\mu_k x); s\right)= \left(\sum_{k\ge 1} \frac{\lambda_k}{\mu_k^s} \right)g^*(s)$$ where $g^*(s)$ is the Mellin transform of $g(x).$ In the present case we have $$\lambda_k = \sqrt{k}, \quad \mu_k = \frac{1}{k} \quad \text{and} \quad g(x) = 1-\sqrt{1+x}.$$

It follows that $$ \sum_{k\ge 1} \frac{\lambda_k}{\mu_k^s} = \sum_{k\ge 1} \sqrt{k} \times k^s =\zeta(-1/2-s).$$

Furthermore we have $$\mathfrak{M}(g(x); s) = \frac{1}{2\sqrt{\pi}} \Gamma(-1/2-s)\Gamma(s).$$

Now this transform has fundamental strip $\langle -1, -1/2 \rangle$ while the zeta function term has $-s-1/2 > 1$ or $s < -3/2.$ These two are disjoint. Therefore we need to modify $g(x)$ by canceling the next term in the power series of $-\sqrt{1+x},$ which gives $$g(x) = 1 + \frac{1}{2} x - \sqrt{x+1},$$ with fundamental strip $\langle -2, -1 \rangle,$ and the transform of $g(x)$ being the same. This strip is perfect as the half-plane of convergence of the zeta function term starts right in the middle of it, extending to the left.

It is important to note that we have now added $$\sum_{k\ge 1} \frac{1}{2}\sqrt{k} \frac{x}{k} = \frac{1}{2} x \sum_{k\ge 1} \frac{1}{\sqrt{k}} = \frac{1}{2} x \zeta(1/2)$$ to our sum, which we will have to subtract out at the end.

The conclusion is that the Mellin transform $T(s)$ of $S(x)$ is given by $$T(s) = \frac{1}{2\sqrt{\pi}} \Gamma(-1/2-s)\Gamma(s) \zeta(-1/2-s).$$

Now apply Mellin inversion, shifting the integral $$\frac{1}{2\pi i}\int_{-7/4-i\infty}^{-7/4+i\infty} T(s)/x^s ds$$ to the right to obtain an expansion at infinity.

We obtain that $$\operatorname{Res}(T(s)/x^s; s=-3/2) = -\frac{2}{3} x^{3/2},$$ $$\operatorname{Res}(T(s)/x^s; s=-1) = -\frac{1}{2} \zeta(1/2) x,$$ (this residue does not contribute being cancelled by the term that we introduced to shift the fundamental strip of $g(x)$) $$\operatorname{Res}(T(s)/x^s; s=-1/2) = -\frac{1}{2} x^{1/2},$$ $$\operatorname{Res}(T(s)/x^s; s=0) = -\zeta(-1/2),$$ $$\operatorname{Res}(T(s)/x^s; s=1/2) = -\frac{1}{24} x^{-1/2}.$$ The remaining residues have the form $$\operatorname{Res}(T(s)/x^s; s=2q+1/2) = \frac{1}{2\sqrt{\pi}}\Gamma(2q+1/2)\zeta(-2q-1)\frac{x^{-2q-1/2}}{(2q+1)!}.$$ Here we use $q\ge 1.$ The reader may wish to simplify these.

This yields the asymptotic expansion $$S(n) \sim 2/3\,{n}^{3/2}+1/2\,\sqrt {n}+\zeta \left( -1/2 \right) + 1/24\,{\frac {1}{\sqrt {n}}} -{\frac {1}{1920}}\,{n}^{-5/2}+{\frac {1}{9216}}\,{n}^{-9/2} +\cdots$$

This is as it ought to be and here Mellin transforms really shine. Mellin-Perron and Wiener-Ikehara only give the first few terms while Euler-MacLaurin fails to produce the constant. The following MSE link points to a calculation in a very similar spirit.

$\endgroup$
  • $\begingroup$ I just realized that I answered the question from the other post on the asymptotic expansion rather than this one. I put a link there that points here. $\endgroup$ – Marko Riedel Jul 17 '13 at 12:43
  • 1
    $\begingroup$ The formula for the residues in the right half plane is $$-1/2\,{\frac {{\it B} \left( 2\,q+2 \right) {4\,q+2\choose 2\,q}}{{16}^{q} \left( 4\,q+2 \right) \left( 4\,q+1 \right) }} x^{-2q-1/2} $$ where the $B(n)$ are the Bernoulli numbers. $\endgroup$ – Marko Riedel Jul 17 '13 at 13:19
  • 1
    $\begingroup$ Does the fact that the infinite sum for $S(x)$ doesn't converge cause a problem? The same issue appears in this answer. $\endgroup$ – robjohn Jun 16 '15 at 23:57
  • $\begingroup$ @robjohn One could probably apply a correction term to the definition of $S(x)$? $\endgroup$ – Simply Beautiful Art Sep 8 '17 at 23:22
19
$\begingroup$

Suppose we are given a small $\epsilon\gt 0$. We show that we can choose $n$ such that $\sum_1^n\sqrt{k}$ is within $\epsilon$ of an integer. Relatively simple estimates are used.

For take $N\gt 1/\epsilon$. Then the numbers $$\sqrt{N^4+1},\quad \sqrt{N^4+2},\quad\text{and so on up to}\quad \sqrt{N^4+2N} $$ are greater than $N^2$ but within $\epsilon$ of $N^2$. Thus each of them is "nearly" an integer. To see this, note that $\left(N^2+\frac{1}{N}\right)^2 \gt N^4 +2N$.

Moreover, these numbers have fractional parts that add up to more than $1$. This is fairly straightforward, since the smallest fractional part is approximately $\frac{1}{2N}$.

So however far $\sum_1^{N^4} \sqrt{k}\,\,$ may be from an integer, one of the sums to $n=N^4+i$, where $1\le i\le 2N$, must come within $\epsilon$ of an integer.

Remark: It may be interesting to ask how much better one can do than $M\approx \frac{1}{\epsilon^4}$ to be sure that there is an $n\le M$ such that $\sum_1^n\sqrt{k}$ is within $\epsilon$ of an integer. Presumably much better! That is where more sophisticated ideas such as Euler-Maclaurin may be useful.

$\endgroup$
  • $\begingroup$ It seems given the examples in the question that OP knew or expected this result, namely that $f(n)\to 0$ for any solution $f$ to the lower bound question asked. This answer is useful for both making that explicit and proving it. I guess that OP is interested in going further and estimating how large $f(n)$ may be, or perhaps just finding any nice closed form strictly positive $f$ that we can prove works. $\endgroup$ – Jonas Meyer Jul 13 '13 at 3:49
  • $\begingroup$ Running these figures backwards, this seems to give $f(n)\approx n^{-1/4}$; it seems plausible that $f(n)\approx n^{-1/2}$ should be straightforwardly acheivable by careful massaging of the terms in the aforementioned Euler-Maclaurin expansion, but I haven't tried going down that route yet. $\endgroup$ – Steven Stadnicki Jul 13 '13 at 3:55
  • $\begingroup$ I gave a (probably) poor but explicit bound. One may be able to do substantially better by using integral estimates, but that will likely leave us very far from the truth. $\endgroup$ – André Nicolas Jul 13 '13 at 3:58
  • $\begingroup$ I think this shows that $f(n)$ must be at most (something close to) $n^{-1/4}$ sometimes. It doesn't show that something like $n^{-1/4}$ works as a lower bound for $|S(n)-I(S(n))|$. Maybe I misunderstand. $\endgroup$ – Jonas Meyer Jul 13 '13 at 3:58
  • $\begingroup$ (I was mistaken to say $f(n)\to 0$. Rather, $\liminf\limits_{n\to \infty}f(n)=0$, whereas $\limsup\limits_{n\to\infty}|I(n)-S(I(n))|=\frac12$.) $\endgroup$ – Jonas Meyer Jul 13 '13 at 6:56
10
$\begingroup$

The form for the asymptotic expansion suggests examining values of $n$ near $36m^2$, where $m\in\mathbb{Z}^+$. For $a\in\mathbb{Z}$ and $|a|\ll m^2$ we find $$\begin{equation*} S(36m^2+a) = 144m^3+(6a+3)m+\frac{a(a+1)}{24m}+\zeta(-1/2) + O(1/m).\tag{1} \end{equation*}$$ Thus, if $m$ is large and $$\begin{equation*} m = \left[-\frac{a(a+1)}{24\zeta(-1/2)}\right],\tag{2} \end{equation*}$$ where $[\;]$ is the nearest integer function, the sum itself should be near an integer. The expansion (1) is consistent, since for this choice of $m$ we must have $|a|\sim\sqrt{m}\ll m^2$.

The error introduced by (2) is $O(1/m)$. Thus, the sum for this choice of $n$ will be within $O(1/m)\sim O(1/n^{1/2})$ of an integer.

Below we give the distance to the nearest integer to the seventh decimal place for some values of $n$. $$\begin{array}{lll} a & n & |S(n)-[S(n)]| \\ \hline 2 & 38 & 0.0462347 \\ 4 & 580 & 0.0019127 \\ 8 & 7064 & 0.0068525 \\ 16 & 108916 & 0.0017046 \\ 32 & 1618016 & 0.0003070 \\ 64 & 25040080 & 0.0000443 \\ 128 & 394419728 & 0.0000292 \end{array}$$

$\endgroup$
  • 1
    $\begingroup$ Mind I ask what brought about this approach? $\endgroup$ – Simply Beautiful Art Sep 8 '17 at 23:23
  • $\begingroup$ @SimplyBeautifulArt: I could see from the asymptotic expansion for the sum that once I forced the first two terms to be integer that I could look for nearby integers such that their nonintegral contribution to the sum cancelled $C$. $\endgroup$ – user26872 Sep 9 '17 at 18:44
  • $\begingroup$ @SimplyBeautifulArt: I was also interested in the possibility of, in a generic way, finding specific $n$s that worked well. $\endgroup$ – user26872 Sep 10 '17 at 15:11
  • $\begingroup$ Sorry, your approach, while clever, is not a great way to find minimal distances from nearest integer, because you can gain something by allowing the leading terms to be slightly off-integer in a way that almost cancels the other terms. For example, while your $f(7064) = .00685$, for the lesser $n = 4070$, $f(4070) = .00113$. And $f(170) = .000390$ $\endgroup$ – Mark Fischler Jul 9 at 19:03
  • $\begingroup$ @MarkFischler: I do not claim to find all possible $n$s. I simply find an infinite family of such $n$s. Taking the term of order $1/n^{1/2}$ into account we should be able to find more such $n$s. (We could even go to higher order.) I would be interested if you were to carry this out, giving an explicit formula for the sequence of $n$s given in your answer. $\endgroup$ – user26872 Jul 10 at 17:10
1
$\begingroup$

To complete this calculation we need to show how to compute $$g^*(s) = \mathfrak{M}(\sqrt{x+1}; s).$$ This is $$\int_0^\infty \sqrt{x+1} x^{s-1} dx.$$ Now put $x+1 = 1/t$ to get $$ g^*(s) = \int_1^0 \frac{1}{\sqrt{t}} \frac{(1-t)^{s-1}}{t^{s-1}} \left(-\frac{1}{t^2}\right) dt \\ = \int_0^1 t^{-1/2-s+1-2} (1-t)^{s-1} dt = \int_0^1 t^{-s-3/2} (1-t)^{s-1} dt. $$ This last integral is a beta function term and equal to $$B(-s-1/2, s) = \frac{\Gamma(-s-1/2)\Gamma(s)}{\Gamma(-1/2)} = -\frac{\Gamma(-s-1/2)\Gamma(s)}{2\sqrt{\pi}}.$$ This was to be shown.

$\endgroup$
1
$\begingroup$

Contrary to the numbers obtained by the clever approach of @user26872, The sequence of "best values up to this point" for numbers $m$ such that $\sum_1^m\sqrt{n}$ is closer to an integer than it is for any smaller $n$, is

$$ \{ 3, 13, 22, 33, 38, 41, 54, 156, 761, 10869, 41085, 142625, 224015, 898612, 2750788 \ldots\} $$ For example, $\sum_1^{156}\sqrt{n} \approx 1305.000314$ and $\sum_1^{10869}\sqrt{n} \approx 755479.999989$ and $\sum_1^{2750788}\sqrt{n}$ is only $3.0776 \cdot 10^{-8}$ more than an integer.

Of these best values, only $38$ is on the list given in the other answer.

The observation is that you can get better approaches to an integer by allowing the leading terms to stray off of integer values, in clever ways that almost cancel the lower order terms.

$\endgroup$

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.