Let $a$ be a positive proper fraction and $n$ is any integer then evaluate the following sum, $$\sum_{i=1}^{\left \lfloor na \right \rfloor\atop} \left \lfloor ia \right \rfloor $$

I think that probably some counting argument will give us a solution of the problem but I can't find it. Any help is appreciated.

Actually the question aroused due to my efforts in trying to find out a simple formula for calculating the Legendre Symbol. Following is my approach to finding a closed form for the sum $$\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor $$ where $\operatorname{gcd}(a,p)=1$ and $a$ is odd.

My Try

I have tried to approach the above problem in the following manner. Consider a rectangle in the Cartesian Plane with coordinates of the vertices $A(0,0)$, $B(\dfrac{p}{2},0)$, $C(\dfrac{p}{2},\dfrac{a}{2})$ and $D(0,\dfrac{a}{2})$.

Now draw the two diagonals $AC$ and $BD$. Let them intersect at $O$. Denote the number of lattice points in region $R$ with no lattice point (if any) on the boundaries is counted by $\Lambda(R)$.

Then using this notation we have, $$\Lambda(\triangle AOB)+\Lambda(\triangle BOC)+\Lambda(\triangle COD)+\Lambda(\triangle DOA)=\Lambda(\square ABCD)$$

But since $\triangle AOB \equiv \triangle COD$ and $\triangle BOC \equiv \triangle DOA$, we get $\Lambda(\triangle AOB)=\Lambda(\triangle COD)$ and $\Lambda(\triangle BOC)=\Lambda(\triangle DOA)$

Therefor our expression reduces to, $$2(\Lambda(\triangle AOB)+\Lambda(\triangle BOC)=\Lambda(\square ABCD) \implies 2\Lambda(\triangle ABC)=\Lambda(\square ABCD)$$

But, $$\Lambda(\triangle ABC)=\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor $$ and $$\Lambda(\square ABCD)=\left(\dfrac{p-1}{2} \right)\left \lfloor \dfrac{a}{2} \right \rfloor$$ hence we have, $$2\sum_{i=1}^{\frac{p-1}{2}} \left \lfloor \dfrac{ia}{p} \right \rfloor=\left(\dfrac{p-1}{2} \right)\left(\dfrac{a-1}{2} \right )$$

But from this I can't interpret the given sum. What is the mistake? There must be a mistake because the parity of both side of the inequality doesn't hold if $p \equiv a \equiv 3$ $(\operatorname{mod}4)$. Can anyone help me in this respect?


Let $a = \displaystyle\frac{p}{q}$ where $(p,q) = 1$ and $p < q$. Then:

$$\sum_{i=1}^{\lfloor na\rfloor} \lfloor ia \rfloor = \sum_{i=1}^{\lfloor na\rfloor} ia - \sum_{i=1}^{\lfloor na\rfloor} \lbrace ia \rbrace $$

Where $\lbrace x\rbrace$ is the fractional part of $x$.

Note that:

$$\sum_{i=1}^{\lfloor na\rfloor} \lbrace ia \rbrace = \frac{1}{q}\sum_{i=1}^{\lfloor na\rfloor} ip\text{ mod }q $$

We can get some interesting results from that depending on $n \text{ mod }q$.

  • $\begingroup$ Could you elaborate on how you got to the second summation involving mod q. $\endgroup$ – KBusc Aug 19 '14 at 20:00
  • $\begingroup$ @KBusc Using integer division we have $ip = cq + r$ where $0 \leq r < q$ (in fact, $r = ip \mod q$ and $c = \lfloor ia\rfloor$) so $\frac{ip}{q} = c + \frac{r}{q} = \lfloor ai\rfloor + \frac{ip\mod q}{q}$ $\endgroup$ – Darth Geek Aug 19 '14 at 20:23
  • $\begingroup$ Ahh thank you very much, that makes sense. $\endgroup$ – KBusc Aug 20 '14 at 12:10
  • $\begingroup$ Can't there be obtained any closed form of the sum? $\endgroup$ – user 170039 Aug 20 '14 at 12:37
  • $\begingroup$ @user170039 that depends on the divisibility of $n$ by $q$ and on wether $q$ is prime or not. $\endgroup$ – Darth Geek Aug 20 '14 at 12:39

Not quite an answer but I couln't get this to look correct as comment. But I think $$ 0 <\sum_{i=1}^{\left \lfloor na \right \rfloor} \left \lfloor ia \right \rfloor < a\cdot {\left \lfloor na \right \rfloor}\frac{{\left \lfloor na \right \rfloor} + 1}{2} $$

Should be true.

  • $\begingroup$ Sorry for the terrible syntax but I am not sure how to do the fraction correctly $\endgroup$ – KBusc Aug 19 '14 at 18:02
  • $\begingroup$ Try \frac{ numerator } { denominator } or just { numerator \over denominator } $\endgroup$ – Winther Aug 19 '14 at 18:02
  • 1
    $\begingroup$ You are missing a factor of $a$. Since $\lfloor ia \rfloor \leq ia$ we have $\sum \lfloor ia \rfloor \leq a \cdot \frac{\lfloor na \rfloor(\lfloor na \rfloor + 1)}{2}$. $\endgroup$ – Winther Aug 19 '14 at 18:06

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.