Home » Lattice Points

Tag: Lattice Points

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

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.

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

  1. 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*}

  2. 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]. \]


        \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

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

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