mathr / blog / #

Starting from this post I'll be using MathJax to display prettier equations. It does require Javascript, but it's much less awkward than the alternatives I've considered.

I was wondering about drawing rectangles on a regular triangular lattice. I found that the area is always a multiple of 4 cells.

Let $\mathbf{u},\mathbf{v}$ be the basis vectors of the triangular lattice, and $\mathbf{x},\mathbf{y}$ be the basis vectors of rectangular Cartesian coordinates. Specify a point on the lattice by $p,q \in \mathbb{Z}$, then:

$$p \mathbf{u} + q \mathbf{v} = (p + \frac{q}{2}) \mathbf{x} + \frac{\sqrt{3}}{2} q \mathbf{y}$$

with the squared Euclidean distance of the point from the origin being:

$$\left|\left| p \mathbf{u} + q \mathbf{v} \right|\right| ^ 2= p^2 + q^2 + pq$$

Now assume $\gcd(p,q) = 1$, to ensure that the line segment from the origin to the point passes through no other lattice points. A line $(P,Q)$ perpendicular to $(p,q)$ satisfies:

$$(p + \frac{q}{2}) \mathbf{x} + \frac{\sqrt{3}}{2} q \mathbf{y} = \lambda ( -\frac{\sqrt{3}}{2} Q \mathbf{x} + (P + \frac{Q}{2}) \mathbf{y} )$$

which reduces to

$$\frac{P}{Q} = - \frac{p + 2 q}{2 p + q}$$

Letting $K = \gcd(p + 2 q, 2 p + q)$, then $P = -\frac{p + 2 q}{K}$ and $Q = \frac{2 p + q}{K}$ and $\gcd(P,Q) = 1$.

The area of the rectangle can be found in terms of $p$ and $q$:

$$A^2 = (p^2 + q^2 + pq) (P^2 + Q^2 + PQ)$$

which reduces to

$$A = \sqrt{3} \frac{p^2 + q^2 + pq}{K}$$

Expressing this in terms of the smallest triangular cell on the lattice, which has area $\frac{\sqrt{3}}{4}$, gives a count of triangles:

$$N = 4 \frac{p^2 + q^2 + pq}{K}$$

Recall that $\gcd(p,q) = 1$ and $\gcd(p + 2 q, 2 p + q) = K$. This means that $K \mid p + 2 q$ and $K \mid 2 p + q$ which implies that $K \mid 3 (p + q)$. So $K \mid 3$ or $K \mid p + q$. When $K$ doesn't divide $p + q$ then $K \in \{1,3\}$. Suppose $K \mid p + q$, then $K \mid p + 2 q$ implies that $K \mid q$, and similarly $K \mid 2 p + q$ implies that $K \mid p$. But $\gcd(p,q) = 1$, therefore $K = 1$.

$K = 1$ implies that $4 \mid N$, so it remains to consider the other case when $K = 3$. Let $p = 3 a + b$ and $q = 3 c + d$ with $b,d \in \{0,1,2\}$. Now $K \mid b + 2 d$ and $K \mid 2 b + d$. Exhaustive case analysis shows that this holds only when $b = d$. Expanding

$$p^2 + q^2 + pq = 3(\ldots) + b^2 + d^2 + bd = 3(\ldots) + 3 b^2$$

shows that $3 \mid p^2 + q^2 + pq$. So $\frac{p^2 + q^2 + pq}{K}\ \in \mathbb{Z}$ and $4 \mid N$: the area of a rectangle on a triangular lattice is always a multiple of 4 cells.