What is the full asymptotic expansion of $\sum\limits_{a = 1}^{p - 1} \lfloor{\frac{N + a}{p}}\rfloor$ as $N \rightarrow \infty$

Question

I have an answer from dropping the floor function is summing to be $\left({1 - \frac{1}{p}}\right) N + 2 \left({p - 1}\right)$. Not certain if the order of part should be $\mathcal{O} \left({1}\right)$. Also $N \ge p$ and $N$ and $p$ are positive integers.

Answer 1

Edit After the comment by reuns, I added details for the closed-form after the asymptotic bounds. We will first show that $$ \boxed{\sum_{a=1}^{p-1} \left\lfloor \frac{N+a}{p}\right\rfloor = \left(\,1-\frac{1}{p}\,\right)N + O(1)}$$ and then, with the implications of the comment, we will show explicitly that $$ \boxed{\sum_{a=1}^{p-1} \left\lfloor \frac{N+a}{p}\right\rfloor = N - \left\lfloor \frac{N}{p}\right\rfloor}$$

Original There is a slight mistake in your upperbound, but I'll address it. We may obtain bounds: $$ \sum_{a=1}^{p-1} \left(\, \frac{N+a}{p} - 1 \,\right) \leq \sum_{a=1}^{p-1}\left\lfloor\frac{N+a}{p}\right\rfloor \leq \sum_{a=1}^{p-1} \frac{N+a}{p} $$ where the left hand side becomes: $$(p-1)\frac{N}{p} + \frac{\tfrac12 p(p-1)}{p} - (p-1) = \left(1-\frac1p\right)N - \frac{p-1}{2} $$ and the right hand side: $$(p-1)\frac{N}{p} + \frac{\tfrac12 p(p-1)}{p} = \left(1-\frac1p\right)N + \frac{p-1}{2} $$

This gives: $$\left(1-\frac1p\right)N - \frac{p-1}{2} \leq\sum_{a=1}^{p-1}\left\lfloor\frac{N+a}{p}\right\rfloor \leq \left(1-\frac1p\right)N + \frac{p-1}{2}$$

so this simple approximation gives that $$\sum_{a=1}^{p-1}\left\lfloor\frac{N+a}{p}\right\rfloor \sim \left(1-\frac1p\right)N + O(1)$$ in particular, $$ \sup_N \left|\, \sum_{a=1}^{p-1}\left\lfloor\frac{N+a}{p}\right\rfloor - \left(1-\frac1p\right)N\,\right| \leq \frac{p-1}{2}$$

Added I haven't seen the result given by reuns in the comment section, so I'll give a quick proof that I came up with, but it was sufficiently obvious that I suspect this is a standard approach. $f(x)= x-\lfloor x\rfloor$ is a sawtoothed periodic wave, with a Fourier series given by $$\frac12 -\frac{1}{\pi} \sum_{n=1}^{\infty} \frac{1}{n}\sin (2n\pi x)$$ which converges to $f$ except at the integers, where $f$ has a jump discontinuity. Fourier series converge to the middle of a jump: there is a jump from $1$ to $0$ at each integer, so the series converges to $\frac12$.

If we let $a$ go over $1,\dotsc, p$ instead, then $\frac{N+a}{p}$ is an integer exactly once, so we may adjust for the $\frac12$ and sum over the Fourier series:

\begin{align} &\sum_{a=1}^p \left(\,\frac{N+a}{p} - \left\lfloor \frac{N+a}{p}\right\rfloor\,\right)\\ &= \sum_{a=1}^p\left(\, \frac12 -\frac{1}{\pi} \sum_{n=1}^{\infty} \frac{1}{n}\sin \left(2n\pi \frac{N+a}{p}\right)\,\right) - \frac12\\ &= \frac{p-1}{2} - \frac{1}{\pi} \sum_{n=1}^{\infty} \sum_{a=1}^p \frac{1}{n}\sin \left(\, \frac{2n\pi N}{p} + \frac{2n\pi a}{p}\,\right)\\ &= \frac{p-1}{2} - \frac{1}{\pi} \sum_{n=1}^{\infty} \sum_{a=1}^p \frac{1}{n}\sin\frac{2n\pi N}{p} \cos \frac{2n\pi a}{p} - \frac{1}{\pi} \sum_{n=1}^{\infty} \sum_{a=1}^p \frac{1}{n}\sin\frac{2n\pi a}{p} \cos \frac{2n\pi N}{p}\\ &= \frac{p-1}{2} - \frac{1}{\pi} \sum_{n=1}^{\infty} \frac{1}{n}\sin\frac{2n\pi N}{p} \underbrace{\sum_{a=1}^p \cos \frac{2n\pi a}{p}}_{=\; 0} - \frac{1}{\pi} \sum_{n=1}^{\infty} \frac{1}{n} \cos \frac{2n\pi N}{p} \underbrace{\sum_{a=1}^p \sin\frac{2n\pi a}{p}}_{=\; 0} \end{align} where the latter step may be easily seen by considering the real and imaginary parts of the geometric series expansion of $$0 = \frac{1 - \left(e^{i\tfrac{2\pi n}{p}}\right)^p}{1-e^{i\tfrac{2\pi n}{p}}}$$

Now, applying this to the original bounds: \begin{align} \sum_{a=1}^{p-1} \left(\,\frac{N+a}{p} - \left\lfloor \frac{N+a}{p}\right\rfloor\,\right) &= \frac{p-1}{2} - \left(\,\frac{N+p}{p} - \left\lfloor \frac{N+p}{p}\right\rfloor \,\right)\\ &= \frac{p-1}{2} - \left(\,\frac{N}{p} - \left\lfloor \frac{N}{p}\right\rfloor \,\right) \end{align} Finally allowing us to compute: \begin{align} \sum_{a=1}^{p-1} \left\lfloor \frac{N+a}{p}\right\rfloor &= \sum_{a=1}^{p-1} \frac{N+a}{p} - \frac{p-1}{2} + \frac{N}{p} - \left\lfloor \frac{N}{p}\right\rfloor\\ &= \left(\,1-\frac1p\,\right) N + \frac{p-1}{2} - \frac{p-1}{2} + \frac{N}{p} - \left\lfloor \frac{N}{p}\right\rfloor\\ &= N - \left\lfloor \frac{N}{p}\right\rfloor \end{align}