Counting Lattice Points

Draw the curve $y = n/x$ for some positive integer $n$. How many points with positive integer coordinates lie on or below it?

This is not a geometry problem dressed up as number theory. It is number theory — because the lattice points under $y = n/x$ are exactly the pairs $(a, b)$ with $ab \leq n$, which counts divisors.

---

What is a lattice point?

A lattice point is a point $(x, y)$ where both $x$ and $y$ are integers.

The integer lattice is the grid $\mathbb{Z}^2$ — all points with integer coordinates. Counting lattice points in a region is a fundamental technique in number theory.

---

Lattice points in a rectangle

The number of lattice points $(x, y)$ with $1 \leq x \leq a$ and $1 \leq y \leq b$ (positive integers) is simply $a \times b$.

For non-integer bounds: lattice points with $1 \leq x \leq X$ and $1 \leq y \leq Y$ number $\lfloor X \rfloor \times \lfloor Y \rfloor$.

---

Lattice points under $y = c/x$

Fix a positive integer $n$. Count lattice points $(x, y)$ with $x, y \geq 1$ and $xy \leq n$.

Approach 1 — Sum by column. For each fixed $x = 1, 2, \ldots, n$, the number of valid $y$ is $\lfloor n/x \rfloor$ (since $y \leq n/x$).

Total: $D(n) = \sum_{x=1}^{n} \left\lfloor \frac{n}{x} \right\rfloor$

What is this sum? For each pair $(x, y)$ with $xy \leq n$, we are counting 1. Equivalently, for each integer $k \leq n$, we count the number of ways to write $k = xy$ with $x, y \geq 1$ — which is the number of divisors $d(k)$.

Therefore: $D(n) = \sum_{x=1}^{n} \left\lfloor \frac{n}{x} \right\rfloor = \sum_{k=1}^{n} \tau(k)$

where $\tau(k)$ is the number of divisors of $k$.

This connection — lattice points under a hyperbola equal the sum of divisor counts — is the starting point of Dirichlet's Divisor Problem.

---

Symmetry across the diagonal

The hyperbola $xy = n$ is symmetric about the line $y = x$.

For lattice points $(x, y)$ with $xy \leq n$:

• Points with $x < y$ pair with points with $x > y$ (swap coordinates)
• Points with $x = y$ satisfy $x^2 \leq n$, so $x \leq \lfloor \sqrt{n} \rfloor$

This symmetry gives a smarter way to count.

Approach 2 — Use symmetry. Let $m = \lfloor \sqrt{n} \rfloor$.

Points with $x \leq m$ and $y \leq m$ (the "square" region): $m^2$.

Points with $x \leq m$ and $y > m$ — for each $x \leq m$, $y$ ranges from $m+1$ to $\lfloor n/x \rfloor$. Count: $\sum_{x=1}^{m} (\lfloor n/x \rfloor - m)$.

By symmetry, points with $x > m$ and $y \leq m$ give the same count.

Therefore: $D(n) = 2\sum_{x=1}^{m} \left\lfloor \frac{n}{x} \right\rfloor - m^2$

where $m = \lfloor \sqrt{n} \rfloor$.

This formula is much faster to compute than summing all $n$ terms.

---

Lattice points under $y = cx$ (linear case)

Count lattice points $(x, y)$ with $x \geq 1$, $y \geq 1$, $y \leq cx$ for rational $c = p/q$.

For each $x$: $y$ ranges from 1 to $\lfloor px/q \rfloor$. Total: $\sum_{x=1}^{n} \lfloor px/q \rfloor$.

This sum — called a Dedekind sum in its general form — appears in problems about counting integers with bounded ratios.

---

Lattice points in a triangle

Points $(x, y)$ with $x \geq 1$, $y \geq 1$, $x + y \leq n$:

For each $x = 1, \ldots, n-1$: $y$ ranges from 1 to $n - x - 1$, giving $n - x - 1$ points (if positive).

Total: $\sum_{x=1}^{n-1}(n-x-1) = \frac{(n-1)(n-2)}{2}$.

This is $\binom{n-1}{2}$ — the triangular number pattern.

---

Worked problems

Problem 1. Compute $\displaystyle\sum_{k=1}^{10} \tau(k)$ by counting lattice points.

$D(10) = \sum_{x=1}^{10} \lfloor 10/x \rfloor = 10+5+3+2+2+1+1+1+1+1 = 27$.

Check: $\tau(1)+\cdots+\tau(10) = 1+2+2+3+2+4+2+4+3+4 = 27$. ✓

Problem 2. Use the symmetry formula to compute $D(10)$.

$m = \lfloor \sqrt{10} \rfloor = 3$.

$\sum_{x=1}^{3} \lfloor 10/x \rfloor = 10 + 5 + 3 = 18$.

$D(10) = 2 \times 18 - 9 = 27$. ✓

Problem 3. How many pairs $(a, b)$ of positive integers satisfy $ab \leq 20$ and $a \leq b$?

These are lattice points with $xy \leq 20$ and $x \leq y$ — the points on or below the diagonal.

$m = \lfloor \sqrt{20} \rfloor = 4$. Using symmetry: $D(20) = 2\sum_{x=1}^{4}\lfloor 20/x\rfloor - 16 = 2(20+10+6+5) - 16 = 82 - 16 = 66$.

Points with $a \leq b$: $\frac{D(20) + \lfloor\sqrt{20}\rfloor}{2} = \frac{66+4}{2} = 35$.

(Add the diagonal points — those with $a=b$, i.e., $a^2 \leq 20$, giving $a \in \{1,2,3,4\}$ — then halve.)

Problem 4. Prove: $\displaystyle\sum_{d \mid n} 1 = \tau(n)$ by a lattice point argument.

The sum $\sum_{d \mid n} 1$ counts divisors of $n$. Each divisor $d$ corresponds to the lattice point $(d, n/d)$ on the hyperbola $xy = n$. So $\tau(n)$ is the number of lattice points on $xy = n$ with $x, y \geq 1$. $\blacksquare$

---

The deeper question: not just how many lattice points, but approximately how many — and how good the approximation is. That requires understanding the hyperbola's area, which is in Hyperbola Area Intuition.