Tag: Lattice Points

Prove a formula for the sum of [(na)/b] where a,b are relatively prime integers

by RoRi

July 17, 2015

Let $a,b$ be relatively prime positive integers (i.e., they have no common factors other than 1). Then we have the formula

$\sum_{n=1}^{b-a} \left[ \frac{na}{b} \right] = \frac{(a-1)(b-1)}{2}.$

The sum is 0 when $b=1$ .

Prove this result by a geometric argument.
Prove this result by an analytic argument.

Proof. We know by the previous exercise (1.11, #6) that
$\sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \begin{array}{l} \text{\# of lattice points inside a right triangle}\\ \text{of base } b \text{ and height } a \ (\text{letting } f(x) = \frac{ax}{b}).\end{array}$

Further, from this exercise (1.7, #4), we know

$a(T) = I_T + \frac{1}{2} B_T - 1$

where $I_T =$ number of interior lattice points, and $B_T =$ number of boundary lattice points. We also know by the formula for the area of a right triangle that

$a(T) = \frac{1}{2} (ab).$

Thus, we have,

$I = \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \frac{1}{2} (ab) - \frac{1}{2}B_T + 1.$

Then, to calculate $B_T$ we note there are no boundary points on the hypotenuse of our right triangle (since $a$ and $b$ have no common factor). (This follows since if there were such a point then $\frac{na}{b} \in \mathbb{Z}$ for some $n < b$ , but then we would have $a$ divides $b$ , contradicting that they have no common factor.) Thus, $B_T = a + b + 1$ . So,

$\begin{align*} \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] &= \frac{1}{2} (ab) - \frac{1}{2} (a+b+1) +1 \\ &= \frac{1}{2} (ab - a - b + 1) \\ &= \frac{1}{2} (a-1)(b-1). \qquad \blacksquare \end{align*}$
Proof. To derive the result analytically, first, by counting in the other direction we have,
$\sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] = \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right].$

Then,

$\begin{align*} && \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right] &= \sum_{n=1}^{b-1} [a] - \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] - \sum_{n=1}^{b-1} 1 \\ \implies && 2 \sum_{n=1}^{b-1} \left[ \frac{a(b-n)}{b} \right] &= \sum_{n=1}^{b-1} [a] - \sum_{n=1}^{b-1} 1 = (b-1)a - (b-1)\\ \implies && \sum_{n=1}^{b-1} \left[ \frac{na}{b} \right] &= \frac{1}{2} (a-1)(b-1). \qquad \blacksquare \end{align*}$

Formula for counting lattice points in the ordinate set of a function

by RoRi

July 17, 2015

For a nonnegative function $f$ defined on an interval $[a,b]$ define the set

$S = \{ (x,y) \mid a \leq x \leq b, \ 0 < y \leq f(x) \}.$

(i.e., the region enclosed by the graph of the function and the $x$ -axis between the vertical lines at $x=a$ and $x=b$ ). Then prove

$\text{\# of lattice points in } S = \sum_{n=a}^b [f(n)],$

where $[f(n)]$ is the greatest integer less than or equal to $f(n)$ .

We can help ourselves by drawing a picture to get a good idea of what is going on, then turn that intuition into something more rigorous. The picture is as follows:

Rendered by QuickLaTeX.com

In the picture, we can see the number of lattice points in the ordinate set of $f(x)$ (not including the $x$ -axis since the question stipulates $S$ contains the points $0 < y \leq f(x)$ ). At each integer between $a$ and $b$ , we count the number of lattice points beneath $[f(x)]$ , the greatest integer less than or equal to $f(x)$ . Then we need to turn this intuition from the picture into a proof:

Proof. Let $n \in \mathbb{Z}$ with $a \leq n < b$ . We know such an $n$ exists since $a,b \in \mathbb{Z}$ with $a < b$ . Then, the number of lattice points in $S$ with first element $n$ is the number of integers $y$ such that $0 < y \leq f(n)$ . But, by definition, this is $[f(n)]$ (the greatest integer less than or equal to $f(n)$ ). Summing over all integers $n, \ a \leq n \leq b$ we have,

$\text{\# of lattice points in } S = \sum_{n=a}^b [ f(n) ]. \qquad \blacksquare$

Prove that no equilateral triangle can have all of vertices on lattice points

by RoRi

July 15, 2015

Prove that an equilateral triangle $T$ cannot have all of vertices on lattice points, i.e., points $(x,y)$ such that both $x,y$ are integers.

Proof. Suppose there exists such an equilateral triangle $T$ . Then,

$T = A \cup B$

for two disjoint, congruent right triangles $A, B$ . Since the vertices of $T$ are at lattice points, we know the altitude from the vertex to the base must pass through $h$ lattice points (where $h$ is the height of $T$ ). Therefore, denoting the lattice points on this altitude by $V_B = h+1$ , we have

$B_T = B_A + B_B -V_B + 2, \qquad I_T = I_A + I_B +V_B - 2.$

Since $T$ is a polygon with lattice point vertices we know by the previous exercise, that $a(T) = I_T + \frac{1}{2} B_T -1$ . Further, by Exercise #2 of this section, we know $a(T) = \frac{1}{2} bh$ . So,

$\begin{align*} &&I_T + \frac{1}{2}B_T - 1 &= (I_A + I_B + V_B - 2) + \frac{1}{2} (B_A + B_B - V_B+2) \\ \implies && I_T + \frac{1}{2}B_T - 1 &= 2I_A + B_A - 2 + \frac{1}{2} V_B &(B_A = B_B, I_A = I_B)\\ \implies && I_T + \frac{1}{2} B_T - 1 &= 2I_A + B_A - 2 + \frac{1}{2}(h+1) &(V_B = h+1) \\ \implies && I_T + \frac{1}{2} B_t - 1 &= 2(a(A)) + \frac{1}{2}(h+1) \end{align*}$

But, $\frac{1}{2} a(T) = a(A) = a(B)$ , so,

$I_T + \frac{1}{2} B_T - 1 &= a(T) + \frac{1}{2}(h+1) \qquad \implies \qquad a(T) = a(T) + \frac{1}{2}(h+1).$

But, $h > 0$ , so this is a contradiction. Therefore, $T$ cannot have its vertices at lattice points and be equilateral $. \qquad \blacksquare$