Approximation of N/2 with fractional parts

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Approximation of N/2 with fractional parts

G H J

Reveal topic tags

fractional part

L

G H BBookmark kLocked kLocked NReply

Source: KoMaL A. 421

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

470 posts

#1 h Apr 17, 2023, 5:20 PM

Y by

Find two positive constants $\alpha$ and $c$ such that
$\left|\sum_{k=1}^N \left\{\frac{k^2}{N}\right\}-\frac{N}2\right|<cN^{1-\alpha}$ holds for all positive integers $N$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

302 posts

R8kt

#6 h Apr 19, 2023, 8:25 AM

Y by

Is there an other source other than Kömal?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PhilippineMonkey

315 posts

PhilippineMonkey

#8 h Apr 20, 2023, 1:20 AM

Y by

For any $\alpha {}$ , $c{}$ .Choose $N=(m+1)^2$ .( $m{}$ large enough)Then $m\sim N^{1/2}$ .
Assume $S=\sum_{k=1}^{N}\left \{\frac{k^2}{N}\right \}$ .Then we have
$S=\sum_{k=1}^{N}\frac{k^2}N-\sum_{k=1}^{N}\lfloor \frac{k^2}{N}\rfloor =\frac 13N^2+\frac 12N+\frac 16-\sum_{k=1}^{N}\lfloor \frac{k^2}{N}\rfloor$ Notice that when $1\leqslant k\leqslant \lfloor \sqrt{N-1}\rfloor$ , $\lfloor \frac{k^2}N\rfloor =0$ .
And when $\lfloor \sqrt{iN-1}\rfloor < k \leqslant \lfloor \sqrt{(i+1)N-1}\rfloor$ , $\lfloor \frac{k^2}N\rfloor =i$ .So we have
$\begin{align*} \sum_{k=1}^{N}\lfloor \frac{k^2}{N}\rfloor & = \sum_{i=1}^{N-1}i\left(\lfloor \sqrt{(i+1)N-1}\rfloor-\lfloor \sqrt{iN-1}\rfloor\right)+N\\ & = (N-1)^2-\sum_{i=1}^{N-1}\lfloor \sqrt{iN-1}\rfloor +N\\ & = N^2-N+1-\sum_{i=1}^{N-1}\lfloor \sqrt{iN-1}\rfloor \end{align*}$ Hence
$\left |S-\frac N2\right |=\left | -\frac 23N^2+N-\frac 56+\sum_{i=1}^{N-1} \lfloor \sqrt{iN-1}\rfloor\right|$ $\sum_{i=1}^{N-1} \lfloor \sqrt{iN-1}\rfloor \geqslant \sum_{i=1}^{N-1}\sqrt {iN}-N+1$ Notice that
$\sum_{i=1}^{N-1}\sqrt {iN}=\sqrt N \sum_{i=1}^{N-1}\sqrt i\geqslant \sqrt N\sum_{t=1}^{m}t(2t+1)=\sqrt N\left(\frac 23m^3+\frac 32m^2+\frac 56m\right )\sim \frac 23N^2+\frac 32N^{3/2}+\frac 56N$ So
$\begin{align*} \left |S-\frac N2\right | & =\left | -\frac 23N^2+N-\frac 56+\sum_{i=1}^{N-1} \lfloor \sqrt{iN-1}\rfloor\right|\\ & \geqslant \frac 32N^{3/2}+\frac{11}6N-\frac 56\\ & > cN^{1-\alpha} \end{align*}$ We're done. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23501 posts

pco

#9 h Apr 20, 2023, 4:37 AM

Y by

PhilippineMonkey wrote:

$\begin{align*} \left |S-\frac N2\right | & =\left | -\frac 23N^2+N-\frac 56+\sum_{i=1}^{N-1} \lfloor \sqrt{iN-1}\rfloor\right|\\ & \geqslant \frac 32N^{3/2}+\frac{11}6N-\frac 56\\ & > cN^{1-\alpha} \end{align*}$ We're done. $\square$

Hemm, I did not check your proof but is not the requested question $|S-\frac N2|\le cN^{1-\alpha}$ ? (the exact contrary of what you proved :maybe:

:maybe:

)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PhilippineMonkey

315 posts

PhilippineMonkey

#10 h Apr 20, 2023, 5:23 AM

Y by

@above,I mean there isn't any solution for ${\alpha}$ , $c{}$ at all.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9036 posts

#14 h Apr 21, 2023, 7:46 AM

Y by

PhilippineMonkey wrote:

So
$\begin{align*} \left |S-\frac N2\right | & =\left | -\frac 23N^2+N-\frac 56+\sum_{i=1}^{N-1} \lfloor \sqrt{iN-1}\rfloor\right|\\ & \geqslant \frac 32N^{3/2}+\frac{11}6N-\frac 56\\ & > cN^{1-\alpha} \end{align*}$ We're done. $\square$

Note that by definition we trivially have $\vert S\vert \le N$ . So your computation is obviously not correct...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1734 posts

oVlad

#15 h Apr 21, 2023, 7:58 AM

Y by

Tintarn wrote:

PhilippineMonkey wrote:

So
$\begin{align*} \left |S-\frac N2\right | & =\left | -\frac 23N^2+N-\frac 56+\sum_{i=1}^{N-1} \lfloor \sqrt{iN-1}\rfloor\right|\\ & \geqslant \frac 32N^{3/2}+\frac{11}6N-\frac 56\\ & > cN^{1-\alpha} \end{align*}$ We're done. $\square$

Note that by definition we trivially have $\vert S\vert \le N$ . So your computation is obviously not correct...

Adding to this, let me explain what precisely is incorrect. You proved that $\sum_{i=1}^{N-1} \lfloor \sqrt{iN-1}\rfloor\geqslant K\sim\frac 23N^2+\frac 32N^{3/2}+\frac 56N,$ but the fact that $K{}$ is asymptotical with $2N^2/3+3N^{3/2}/2+5N/6$ doesn't really give you much info regarding $K$ , except that it is of the form $2N^2/3+o(N^2)$ . For all you know, $K$ might be of the form $\frac{2}{3}N^2-10000N^{3/2},$ which is still asymptotical with $2N^2/3+3N^{3/2}/2+5N/6$ . This is not the case, but after some computations you'll see that $\sqrt N\left(\frac 23m^3+\frac 32m^2+\frac 56m\right )$ written in terms of $N$ is actually smaller than $2N^2/3$ .

This post has been edited 4 times. Last edited by oVlad, Aug 22, 2023, 4:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9036 posts

#18 h Apr 21, 2023, 10:43 AM • 5 Y

Y by oVlad, GHHardy911, Miquel-point, Joider, R8kt

@above: Please don't spam this thread by bumping every minutes and quoting whole (long) posts.
Here is a solution which shows that any $\alpha>\frac{1}{2}$ works if $c$ is chosen sufficiently large (and I am pretty sure that this is sharp).
Indeed, let us show that
$\sum_{k=1}^N \left\{\frac{k^2}{N}\right\}=\frac{N}{2}+\mathcal{O}\left(N^{\frac{1}{2}+\varepsilon}\right)$ which is clearly sufficient.
The key is the fact that we can expand the sawtooth function $\{x\}-\frac{1}{2}$ into a Fourier Series $\sum_{m \in \mathbb{Z}, m \ne 0} \frac{e^{2\pi i mx}}{2\pi im}$ . More precisely, since this is not absolutely convergent, we require the truncated version
$\{x\}-\frac{1}{2}=\sum_{1 \le \vert m\vert \le M} \frac{e^{2\pi i mx}}{2\pi im}+\mathcal{O}\left(\frac{1}{M\|x\|}\right)$ where $\|x\|$ is the distance to the nearest integer (so this identity only makes sense for $x \not \in \mathbb{Z}$ ).
Hence we obtain
$\sum_{k=1}^N \left\{\frac{k^2}{N}\right\}=\frac{N}{2}+\mathcal{O}\left(\sum_{1 \le m \le M} \frac{1}{m}\left\vert \sum_{k=1}^N e^{2\pi i \frac{mk^2}{N}}\right\vert+\#\{k: N \mid k^2\}+\sum_{k: N \nmid k^2} \frac{1}{M\left\|\frac{k^2}{N}\right\|}\right).$ Now the inner sum is a Gauß sum which is $\sqrt{N}$ in absolute value when $m$ is coprime to $N$ and so in general is bounded by $(N;m) \cdot \sqrt{N}$ and so the whole first error term is bounded by $\sqrt{N} \cdot \log(M) \cdot \tau(N)$ which is $\mathcal{O}\left(N^{1/2+\varepsilon}\right)$ as long as $M \le N$ (say).
For the second error term it is easy to see that $\{k: N \mid k^2\}$ is also $\mathcal{O}(\sqrt{N})$ .
Finally, the third term is bounded by
$\frac{N}{M} \sum_{1 \le a \le \frac{N}{2}} \frac{1}{a} \cdot \#\{k: k^2 \equiv \pm a \pmod{N}\} \ll \frac{N^{1+\varepsilon}}{M}\sum_{1 \le a \le \frac{N}{2}} \frac{(a;N)}{a} \ll \frac{N^{1+\varepsilon}}{M}$ as before. Choosing e.g. $M=\sqrt{N}$ or $M=N$ now yields the desired result.

This post has been edited 1 time. Last edited by Tintarn, Apr 21, 2023, 11:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1734 posts

oVlad

#19 h Apr 21, 2023, 11:02 AM • 1 Y

Y by GHHardy911

Very nice, Tintarn! I tried this problem and (heuristically) I reached the same order of magnitude as you, but didn't manage to finish. I mostly followed the same idea as #8. Once I reached $\left|\sum_{i=1}^N\left\{\frac{i^2}{N}\right\}-\frac{N}{2}\right|=\left|\frac{2}{3}N^2-\frac{1}{6}-\sum_{i=1}^N\lfloor\sqrt{iN-1}\rfloor\right|,$ I tried to approximate the sum of floors with $\sqrt{N}(\sqrt{1}+\cdots+\sqrt{N})$ and use the Euler-Maclaurin summation to get $\sum_{i=1}^N\sqrt{i}=\frac{2}{3}N^{3/2}+\frac{1}{2}N^{1/2}+\zeta\left(\frac{1}{2}\right)+O\left(N^{-1/2}\right),$ which is very close, but I am short of an $N/2$ . Do you think this idea works?

Edit: Yeah, that's exactly it. Thanks for the opinion.

This post has been edited 2 times. Last edited by oVlad, Nov 22, 2023, 10:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9036 posts

#21 h Apr 21, 2023, 11:19 AM • 2 Y

Y by GHHardy911, oVlad

oVlad wrote:

I tried to approximate the sum of floors with $\sqrt{N}(\sqrt{1}+\cdots+\sqrt{N})$ and use the Euler-Maclaurin summation to get $\sum_{i=1}^N\sqrt{i}=\frac{2}{3}N^{3/2}+\frac{1}{2}N^{1/2}+\zeta\left(\frac{1}{2}\right)+O\left(N^{-1/2}\right),$ which is very close, but I am short of an $N/2$ . Do you think this idea works?

I am not sure this can work... I guess the $\frac{N}{2}$ that you are off comes from the fact that you are ignoring the floors, right? Because on average you expect that you lose $\frac{1}{2}$ from each floor.
In general, I am not sure approximations like Euler-McLaurin are useful to approximate these irregular floor functions, at least on such a fine scale.
This is really what the Fourier Series I wrote down is doing: It approximates uniformly the floor function (or equivalently the sawtooth function).

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a