Krdytkyu

I would like to prove (rigorously, not intuitively) that
$$sum_{n=1}^N {nsqrt{2}}=frac{N}{2}+mathcal{O}(sqrt{N})$$
where ${}$ is the "fractional part" function. I understand intuitively why this is true, and that's how I came up with this claim - ${nsqrt{2}}$ behaves like a random variable uniformly distributed in $(0,1)$, and treating it as a random variable makes the sum analogous to a random walk, and the $mathcal{O}(sqrt{N})$ bound can be shown using expected values.

However, just saying that ${nsqrt{2}}$ behaves "like a random variable" is highly non-rigorous. Can someone show me how to justify this in a more airtight way (ideally without using any theorems that require specialized background knowledge)?

Thanks!

Let $f$ be the function defined for a positive integer $N$ as follows:
$$
f(N)
=
sum_{1le nle N}{nsqrt 2} .
$$
We need a control of $f(N)-N/2$.

Here, i try to give arguments for the idea extracted from the following experimental computation:

Experiment:
We approximate $sqrt 2$ by using continued fractions, for such a fixed approximation,
$P/Q$ say, we compute $f(Q)$ and $f(Q)-Q/2$. For the first few values of $Q$...

def f(N):

    return sum( [ RR(k*sqrt(2)).frac() for k in xrange(1, N+1) ] )



cf = continued_fraction( sqrt(2) )



# consider the first 15 "convergents" P/Q and compute f(Q) - Q/2 for them

for frac in cf.convergents()[:15]:

    P, Q = frac.numerator(), frac.denominator()

    print "sqrt(2) ~ %s :: Q = %s :: f(Q)-Q/2 ~ %s" % ( frac, Q, f(Q)-Q/2 )

Results:

sqrt(2) ~ 1 :: Q = 1 :: f(Q)-Q/2 ~ -0.0857864376269049

sqrt(2) ~ 3/2 :: Q = 2 :: f(Q)-Q/2 ~ 0.242640687119285

sqrt(2) ~ 7/5 :: Q = 5 :: f(Q)-Q/2 ~ -0.286796564403573

sqrt(2) ~ 17/12 :: Q = 12 :: f(Q)-Q/2 ~ 0.308657865101423

sqrt(2) ~ 41/29 :: Q = 29 :: f(Q)-Q/2 ~ -0.317100367703610

sqrt(2) ~ 99/70 :: Q = 70 :: f(Q)-Q/2 ~ 0.320702497141440

sqrt(2) ~ 239/169 :: Q = 169 :: f(Q)-Q/2 ~ -0.322176510488248

sqrt(2) ~ 577/408 :: Q = 408 :: f(Q)-Q/2 ~ 0.322790161566445

sqrt(2) ~ 1393/985 :: Q = 985 :: f(Q)-Q/2 ~ -0.323043813132131

sqrt(2) ~ 3363/2378 :: Q = 2378 :: f(Q)-Q/2 ~ 0.323148970494003

sqrt(2) ~ 8119/5741 :: Q = 5741 :: f(Q)-Q/2 ~ -0.323192510470562

sqrt(2) ~ 19601/13860 :: Q = 13860 :: f(Q)-Q/2 ~ 0.323210559656218

sqrt(2) ~ 47321/33461 :: Q = 33461 :: f(Q)-Q/2 ~ -0.323217967510573

sqrt(2) ~ 114243/80782 :: Q = 80782 :: f(Q)-Q/2 ~ 0.323221431812271

sqrt(2) ~ 275807/195025 :: Q = 195025 :: f(Q)-Q/2 ~ -0.323220559774200

So the difference is in these cases "surprisingly" in the interval $[-1,1]$.

The estimation:
Let us try to convert these observation into a proof.
Let $a$ be $sqrt 2-1$, so $ain(0,1/2)$.
(I need $a<1$ below.) We have ${nsqrt 2}={na}$.

Let $P/Q$ be a rational approximation of $a$, an irreducible fraction, namely one provided by the
continued fraction convergents of $a$, which form an "alternated sequence around $a$" $dots P/Q, P'/Q', P''/Q'',dots$,
and the difference between two consecutive convergents $P/Q$ and $P'/Q'$ is $pm 1/(QQ')$.
In particular, $Q,Q'$ are relatively prime.
We will also use in the following the "next convergent" $P'/Q'$.

Fix some natural $n$ with $0<n<Q$. So $nP/Q<n$ is not an integer. (If $Q|(nP)$, then $Q|n$.)

Assume now there is an integer between $na$ and $nP/Q$.
Then the same integer is in the bigger interval between $nP'/Q'$ and $nP/Q$, which is of length
$1/(QQ')<1/Q$. But from $nPQnotinBbb N$ to the next integer is a distance of at least $1/Q$.
Contradiction.
Our assumption is false.

So $na$ and $nP/Q$ have the same floor.
Then
$$
left{naright}
=
left{nfrac PQ+nleft(a-frac PQright)right}
$$
lies between the numbers
$$
left{nfrac PQright}pm underbrace{left{nleft(a-frac PQright)right}}_{<n/(QQ')} .
$$
Now let $n$ run in a set $S=S(Q)$ of $Q$ consecutive elements. Then
$$
begin{aligned}
sum_{substack{nin S(Q)\Qnot|n}} {na}
text{ lies between }
&sum_{substack{nin S(Q)\Qnot|n}} left{nfrac PQright}
pm sum_{substack{nin S(Q)\Qnot|n}}left{nleft(a-frac PQright)right}
\
text{ thus between }
&sum_{0<n<Q} frac nQ
pm frac 1{QQ'}sum_{nin S(Q)}{color{red}{n}}
\
=
&frac 12(Q-1)
pm frac 1{QQ'}sum_{nin S(Q)}{color{red}{n}}
.
end{aligned}
$$
(Later edit in red.)
This can now be converted to a proof for the stated result as follows.
I try to explain my feeling of a procedure using an example, $N=100000$ say.

Recall the following denominators "$Q$" of the convergents of $a=sqrt 2-1$:
$1$, $2$, $5$, $12$, $29$, $70$, $169$, $408$, $985$, $2378$, $5741$, $13860$, $33461$, $80782$, $195025$.
Using $Q=80782$ and $S(Q)=(N-Q,N]capBbb Z$ we obtain a deviation from $frac 12|S(Q)|$ which is less than (one plus)
$frac {N(N+1)/2}{QQ'}<frac{Q'Q'/2}{QQ'}<2$. (Here, $Q'/Qapprox sqrt 2+1$, which is the limit of the ration of two
consecutive convergents.)

Then for the "new N", which is $N-Q=19281$ we use the "new Q" $13860$. And so on.

Using this we get a deviation of $f(N)$ from $N/2$ which is of the shape $2log_{sqrt 2+1} N$.

(Have to submit, hope that the idea is clear, this was more important for me than to write things rigurous,
and possibly deflect from the idea.)

Writing
begin{align}
&quad sum_{n=1}^N left( nsqrt{2} - lfloor nsqrt{2} rfloor right) \
&=int_1^N left( nsqrt{2} - lfloor nsqrt{2} rfloor right) {rm d}n + {cal O}(1) tag{1} \
&=frac{1}{sqrt{2}} int_sqrt{2}^{sqrt{2}N} left(x- lfloor x rfloor right) {rm d}x + {cal O}(1) \
&=frac{1}{sqrt{2}} Bigg( N^2 - 1 - Bigg[ frac{sqrt{2}N left(sqrt{2}N-1right)}{2} + frac{left{sqrt{2}Nright} left(1-left{sqrt{2}Nright}right)}{2} \
&quad - frac{sqrt{2} left(sqrt{2}-1right)}{2} - frac{left{sqrt{2}right} left(1-left{sqrt{2}right}right)}{2} Bigg] Bigg) + {cal O}(1) \
&=frac{N}{2} + {cal O}(1)
end{align}
where we used
$$
int_0^x lfloor t rfloor , {rm d}t = frac{x(x-1)}{2} + frac{left{xright}left(1-left{xright}right)}{2} , .
$$
The order follows from the fact that
$$
frac{left( sqrt{2}N - lfloor sqrt{2}N rfloor right) + left( sqrt{2} - lfloor sqrt{2} rfloor right)}{2} = {cal O}(1) tag{2}
$$
and
$$int_1^{N} left( nsqrt{2} - lfloor nsqrt{2} rfloor right)'' {rm d}n tag{3} \
= left( sqrt{2}n - lfloor sqrt{2}n rfloor right)'big|_{n=N} - left( sqrt{2}n - lfloor sqrt{2}n rfloor right)'big|_{n=1} \
=sqrt{2} sum_{k=-infty}^{infty}left[ deltaleft( sqrt{2} - k right) - deltaleft( sqrt{2}N - k right) right]
$$
but this requires Euler-Maclaurin.

Due to the harsh critic about my somewhat heuristic argument I want to correct my approach as far as possible.

Set $$f(x)=x-lfloor x rfloor$$ and $$f_n(x)=frac{1}{2} - frac{1}{pi} sum_{k=1}^n frac{sin(2pi k x)}{k} , ,$$such that
$$
lim_{nrightarrow infty} f_n(x) = f(x) , .
$$
Since $f_n$ is differentiable we can use Euler-Maclaurin to calculate the sum
$$
sum_{k=1}^N f_n(ak)
$$
with some $a$. The integral in (1) does not create much of an issue in the limit $n rightarrow infty$, since the limit is piecewise continuous and the integral can be splitted accordingly and then integrated. Also the limit of (2) is of ${cal O}(1)$. So the problematic term which needs to be examined is the remainder $R_2$ ((3) was very heuristic) which can be written as
$$
R_2=int_1^N B_2left(t-lfloor t rfloorright) frac{rm d}{{rm d}t} f_n'(at) , {rm d}t
$$
neglecting unnecessary constants and $B_2$ is the second Bernoulli polynomial. We can express
begin{align}
f_n'(at) &= 1-sum_{k=-n}^{n} {rm e}^{i2pi k at} = 1 - frac{sinleft((2n+1)pi atright)}{sinleft(pi atright)} \
B_2left(t-lfloor t rfloorright) &= left(t-lfloor t rfloorright)(left(t-lfloor t rfloor - 1right) + frac{1}{6} = lim_{M rightarrow infty} sum_{k=1}^M frac{cos(2pi kt)}{pi^2 k^2}
end{align}
and integrate by parts
$$
R_2=-B_2left(t-lfloor t rfloorright) frac{sinleft((2n+1)pi atright)}{sinleft(pi atright)} Bigg|_{1}^{N} - 2 sum_{k=1}^{M} int_1^N frac{sin(2pi kt)}{pi k} frac{sinleft((2n+1)pi atright)}{sinleft(pi atright)} , {rm d}t tag{4} , .
$$
For $a$ not an integer, the first term is bounded and ${cal O}(1)$ as $n rightarrow infty$. The integral can be viewed as a functional for $n rightarrow infty$ in which case the Dirichlet kernel acts as a periodic delta-distribution $sum_{m=-infty}^{infty} delta(at-m)$
$$
lim_{n rightarrow infty} int_1^N frac{sin(2pi kt)}{pi k} frac{sinleft((2n+1)pi atright)}{sinleft(pi atright)} , {rm d}t = sum_{m=lceil a rceil}^{lfloor Na rfloor} frac{sinleft(frac{2pi km}{a}right)}{pi k a} , .
$$

Evaluating
$$
sum_{m=lceil a rceil}^{lfloor Na rfloor} lim_{Mrightarrowinfty} -2sum_{k=1}^{M} frac{sinleft(frac{2pi km}{a}right)}{pi k a} = sum_{m=lceil a rceil}^{lfloor Na rfloor} frac{2{m/a}-1}{a} tag{5}
$$

and using $sum_{n=1}^{N}{an} = frac{N}{2} + {cal O}(?)$
this becomes ${cal o}(N)$. So it is actually true ${cal O}(1)$ does not follow.

We continue with the integral in (4) for $N$ integer
begin{align}
&quad -2sum_{k=1}^infty int_1^N frac{sin(2pi kt)}{pi k} frac{sinleft((2n+1)pi atright)}{sinleft(pi atright)} , {rm d}t \
&=-4sum_{m=1}^n sum_{k=1}^infty int_1^N frac{sin(2pi kt)cos(2pi m a t)}{pi k} , {rm d}t \
&=frac{4}{pi^2} sum_{m=1}^n sum_{k=1}^infty frac{cos^2(Npi m a)-cos^2(pi ma)}{k^2-m^2 a^2} \
&=2sum_{m=1}^n left[ frac{cos^2(Npi m a)-cos^2(pi ma)}{pi^2 m^2 a^2} - frac{cot(pi ma)left(cos^2(Npi ma) - cos^2(pi ma)right)}{pi ma} right]
end{align}
where $a$ must be an irrational number now. The first term is ${cal O}(1)$ for $nrightarrow infty$.

Any idea for the second?

It can be rewritten as
begin{align}
&quad , , sum_{m=1}^n frac{cot(pi ma)left(cos^2(Npi m a) - cos^2(pi ma)right)}{pi ma} \
&= sum_{m=1}^n frac{cot(pi ma)left(cos(N2pi ma) - cos(2pi ma)right)}{2pi ma} \
&= - sum_{m=1}^{n}cos(mpi a) , frac{sinleft((N+1)mpi aright)}{mpi a} , frac{sinleft((N-1)mpi aright)}{sin(mpi a)} \
&= - sum_{m=1}^{n} frac{sinleft((N+2)mpi aright)}{mpi a} , frac{sinleft((N-1)mpi aright)}{sin(mpi a)} + sum_{m=1}^n frac{ sinleft(N2pi maright) - sinleft(2pi maright) }{2pi ma}
end{align}
so the second sum is bounded again $forall N$ and $n rightarrow infty$.

Not sure if it helps, but I have the following two identities for the sines
$$
frac{sinleft((N-1)nxright)}{sin(nx)} = sum_{l=2}^N cosleft((N-l)nxright) cos^{l-2}(nx)
$$
and
$$
frac{sinleft((N-1)nxright)}{sin(nx)} = 1+2sum_{l=1}^{frac{N}{2}-1} cosleft(l2nxright) , ,
$$
but evaluating this feels as if I'm running in circles.

I added a Figure of the RHS of (5) up to $N=10^6$ which doesn't look anything like $log$, so either the numbers are just too small or I dont why it has to be $log$.

This is along the same line as another problem and my answer there: Determine whether $sum_{n=1}^infty frac {(-1)^n|sin(n)|}{n}$ converges

We need Koksma's inequality p. 143, Theorem 5.1 of 'Uniform Distribution of Sequences' by Kuipers and Niederreiter.

Theorem [Koksma]

Let $f$ be a function on $I=[0,1]$ of bounded variation $V(f)$, and suppose we are given $N$ points $x_1, ldots , x_N$ in $I$ with discrepancy
$$
D_N:=sup_{0leq aleq bleq 1} left|frac1N #{1leq nleq N: x_n in (a,b) } -(b-a)right|.
$$
Then
$$
left|frac1N sum_{nleq N} f(x_n) - int_I f(x)dx right|leq V(f)D_N.
$$

To control the discrepancy, We apply the following theorem, for the sequence $x_n = nalpha - lfloor n alpha rfloor$. Note that with $alpha = sqrt 2$, it has a bounded partial quotients in its continued fraction.

Theorem 3.4 of p125 in the Kuipers and Niederreiter's book, states that

If an irrational real $alpha$ has a bounded partial quotients, then the discrepancy $D_N$ satisfies
$$
N D_Nll log N.
$$

Then applying these to your problem with $f(x)=x$, we obtain
$$
biggvertfrac1N sum_{nleq N} { nsqrt 2} - int_0^1 x dxbiggvert ll frac{log N}N.
$$

Therefore, we have an estimate of
$$
sum_{nleq N} {nsqrt 2}=frac N2 + O(log N).
$$

To obtain a more precise estimate, we have $V(f)=1$ for $f(x)=x$. Also, p.143 Theorem 5.1 describes how $O(log N)$ term behaves. Using those, we have
$$
Biggvert sum_{nleq N} {nsqrt 2}-frac N2 Biggvert leq 3+left(frac1{log xi}+frac{2}{log 3}right)log N.
$$
Here we use $xi=frac{1+sqrt 5}2$ and the continued fraction partial quotients are bounded by $2$ (It is in fact $[1;2,2,2,ldots]$).