TRIANGLES WITH VERTICES ON LATTICE POINTS

Michael J. Beeson Department of Mathematics and Computer Science San Jose State University San Jose, CA 95192 beeson@ucscc.ucsc.edu

Abstract^{1}

A triangle is called embeddable in Z^{n} if it is similar to a triangle whose vertices have integer coordinates in R^{n}. It was already known that a triangle is embeddable in Z^{2} if and only if all its angles have rational tangents. We show that a triangle is embeddable in some Z^{n} if and only if it is embeddable in Z^{5}, and if and only if all its angles have tangents with rational squares. We reduce the problem of embeddability to a certain Diophantine equation. We give a complete characterization of the triangles embeddable in Z^{n} for every n. In particular, there are triangles embeddable in Z^{5} but not Z^{4}, and in Z^{3} but not Z^{2}, but surprisingly, the same triangles are embeddable in Z^{3} as are embeddable in Z^{4}. A triangle is embeddable in Z^{3} if and only if the tangents of its angles are all rational multiples of \sqrt{k} for some integer k which is a sum of three squares. The proofs use only elementary number theory and quaternions.

These results can be equivalently formulated in terms of embeddable angles rather than embeddable triangles. An angle is embeddable in Z^{n} for n ≥ 5 iff its tangent is a rational multiple of \sqrt{k} for some k. It is embeddable in Z^{n} for n = 3 or n = 4 iff k is a sum of three squares. It is embeddable in Z^{2} iff k is a square, that is, the tangent is rational. The number k depends only on the plane of the angle, so all angles of a triangle have the same k.

Introduction

The simplest question concerning embeddability is this: is the equilateral triangle embeddable in Z^{2}? That is, are there lattice points in the plane forming the vertices of an equilateral triangle? As it turns out, there are not. Of course, the equilateral triangle is embeddable in Z^{3}, with vertices at the points one unit along each of the three axes. This illustrates that more triangles may be embeddable if more dimensions are allowed. The general problem addressed in this paper is to characterize the triangles embeddable in Z^{n} for each n. We give a complete solution of this problem, as described in the preceding abstract.

The problem solved in this paper has a surprisingly long history, and is connected to the work of several other authors. These points are discussed in a separate section near the end of the paper.

Dimension Two

The following proposition is included as an introduction to the subject. (In the proposition, infinity counts as a rational tangent.)

Proposition 1. (J. McCarthy) A triangle is embeddable in Z^{2} if and only if all its angles have rational tangents.

Proof. Let triangle ABC have its vertices on lattice points in Z^{2}. Assume for the moment that neither leg of angle A is parallel to the y-axis. Let AP be a line through vertex A parallel to the x-axis. Then angle A is the difference of the angles BAP and CAP. These two angles evidently have rational tangents. But now we may use the formula

Typeset by AMS-TEX

1It was John McCarthy who pointed out the result on embeddability in R^{2} and asked for a generalization to R^{n}. Thanks are due to R. Alperin, for pointing out Lemma 7.

2 MICHAEL J. BEESON DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE SAN JOSE STATE UNIVERSITY SAN JOSE, CA 95192 BEESON@UCSCC.UCSC.EDU

tan(α − β) = \frac{tan α − tan β}{1 + tan α tan β}

to conclude that angle A also has a rational tangent. In case one leg of angle A is parallel to the y-axis, we interchange the roles of the x-axis and y-axis in this argument. This will be possible unless angle A is a right angle, in which case the conclusion is immediate.

Conversely, suppose all the angles of triangle ABC have rational tangents. If one of the angles is a right angle, the embeddability is immediate, so we assume that none of the angles is a right angle. Drop an altitude AP from vertex A to side BC (possible extended), so that P is on line BC. Then the ratios AP/BP and AP/CP are rational, being the tangents of angles B and C respectively. Express these two fractions over a common denominator as AP/BP = u/N and AP/CP = v/N. Assume for the moment that P lies between B and C. Then triangle ABC is similar to triangle (0, uv), (−Nv, 0), (Nu, 0), since two corresponding angles have the same tangent. The cases where P lies to the left of A or the right of C are similar. □

Remark: The criterion in Proposition 1 does not extend to higher dimensions. For example, the equilateral triangle is embeddable in Z^{3} but not in Z^{2}.

Embeddability of Angles and Triangles Compared

For the record, we define an angle to be embeddable in Z^{n} if it is one of the angles of a triangle embeddable in Z^{n}.

Proposition 2. If an angle θ is embeddable in Z^{n} (for any n), then tan^{2} θ is rational.

Proof. Let triangle ABC lie in Z^{n} with its vertices on lattice points. Consider sides AB and AC as vectors, and take their dot product: AB · AC = |AB||AC| cos θ, where θ is the angle at vertex A. Hence

cos^{2} θ = \frac{(AB · AC)^{2}}{|AB|^{2}|AC|^{2}}

The expression on the right hand side is a rational function of the coordinates of A, B, and C. Since those coordinates are integers, it follows that cos^{2} θ is rational. Hence sin^{2} θ = 1 − cos^{2} θ is also rational, and hence tan^{2} θ = sin^{2} θ/ cos^{2} θ is rational too. □

The following lemma connects the embeddability of a triangle with the embeddability of its angles considered separately. (We count infinity as a rational tangent, and as a rational multiple of \sqrt{k}.)

Lemma 3. (i) If the square of the tangent of each angle of a triangle T is rational, then there exists a (square-free) positive integer k such that each tangent is a rational multiple of \sqrt{k}.

(ii) Moreover, k depends only on the plane of the triangle, i.e. any two triangles in the same plane have the same k.

(iii) Still more generally, any two lattice angles in the same plane have the same k.

Proof. Ad (i): Let the angles of the triangle be α, β, and γ. In case one of the angles is a right angle, say γ, then tan α is the reciprocal of tan β, so the conclusion is trivial. We may assume therefore that none of the angles is a right angle. In particular, 1 − tan α tan β is not zero. Then

tan γ = −\frac{tan α + tan β}{1 − tan α tan β}

Suppose tan α = a\sqrt{j} and tan β = b\sqrt{k} where k and j are square-free positive integers, and a and b are non-zero rationals. Then

tan γ = −\frac{a\sqrt{j} + b\sqrt{k}}{1 − ab\sqrt{jk}}

Rationalizing the denominator on the right, we have

tan γ = −\frac{(1 + a^{2}j)b\sqrt{k} + (1 + b^{2}k)a\sqrt{j}}{1 − a^{2}b^{2}jk}

Hence tan^{2} γ is a rational plus a rational multiple of \sqrt{jk}, which is irrational unless j = k. This completes the proof of part (i) of the Lemma.

Part (ii) evidently follows from part (iii), since the six different angles of two triangles are special cases of angles in the plane.

Now for part (iii). Let two non-right lattice angles α and β be given in the same plane. Unless there are parallel sides, upon extending the sides of the angles two triangles will be formed, with a common vertex P opposite angle α in one triangle and opposite angle β in the other triangle. (It may be necessary to replace one angle with its vertical angle or a supplemental angle, which won’t affect the square of the tangent.) Rescaling the figure if necessary, the intersection points of the sides, one of which is P, can be made lattice points. Assuming there are no parallel sides, it will be possible to choose the vertex P so that the angle at P is not a right angle. (Otherwise the figure must be a square with α and β diagonally opposite.) We apply part (i) of the lemma successively to the two triangles containing α and β to show that α and β have the same k.

The proof is not quite finished, because we still must consider the case in which no triangles are formed, i.e. two angles α and β in the same plane with one side of α parallel to one side of β. In this case we can translate the angles until they have a common vertex and a common side. Assume for definiteness that the common side is between the two angles. Then the sum α + β is embeddable. Therefore tan^{2}(α + β) is rational. Using the same argument as we used to prove part (i), i.e. the formula for the tangent of a sum, we can show that α and β must have the same k. Similarly, using the formula for tan(α − β), we can treat the case of parallel sides in which one angle lies inside the other. □

One of the referees pointed out that the integer k in Lemma 3 is related to the area of the lattice triangle. Putting the matter simply, \sqrt{k} is a rational multiple of the area. This observation yields another proof of part (i) of Lemma 3. The computation is a little simpler, but we can’t get part (iii) without the computation given above. Since the observation about the area is interesting in its own right, we give that computation too: Let a and b be lattice points defining two adjacent sides of a triangle with angle θ at origin. Then the perpendicular from a to b is given by

u = a − \frac{(a · b)b}{|b|^{2}}

The area S is thus given by 4S^{2} = |u|^{2}|b|^{2} = |a|^{2}|b|^{2} − (a · b)^{2}. We have

tan θ = \frac{|u||b|}{a · b} = \frac{2S}{acdotb}

The formula shows that 4S^{2} is an integer. Write 4S^{2} = m^{2}k where k is square-free. Then tan θ is a rational multiple of \sqrt{k}.

The Triangle Equations

Definition. The triangle equations E(k, n) are

k(a_{1}^{2} + a_{2}^{2} + … + a_{n}^{2}) = u_{1}^{2} + u_{2}^{2} + … u_{n}^{2}
a_{1}u_{1} + a_{2}u_{2} + … a_{n}u_{n} = 0

Throughout the paper, we consider only non-trivial solutions in integers a_{i} and u_{i} of these equations.

Proposition 4. If a triangle with an angle with tangent λ\sqrt{k} is embeddable in Z^{n}, where λ is rational, then the triangle equations E(n, k) have a non-zero solution, in which the variables have no common factor.

Conversely, if E(n, k) has a non-zero solution, and if triangle ABC has all its tangents of the form λ\sqrt{k} for rational λ, then triangle ABC is embeddable in Z^{n}.

Remark: Of course there are many non-embeddable triangles with one tangent of the specified form, as you can fix two vertices and let the third move along one side of the triangle. Hence the second condition in the theorem is needed.

Proof. First suppose the triangle ABC has its vertices on lattice points in Z^{n}. As in the previous proof, we drop the altitude from vertex B to point P on side AC. As in that proof, P has rational coordinates, and enlarging the triangle if necessary, we may assume P has integer coordinates. Performing a translation, we may assume P is the origin. We now have vector A of magnitude AP, and vector B of magnitude BP, which are orthogonal. The ratio BP/AP = tan A = λ\sqrt{k} by hypothesis. We thus have

(tan^{2} A)|A|^{2} = k|(λA)|^{2} = |B|^{2}.

Thus (λA, B) solves the triangle equations E(n, k).

Conversely, suppose given a solution (a, u) of the triangle equations, and a triangle ABC such that tan A = λ\sqrt{k} with λ rational. As before drop an altitude BP from B to side AC. Consider first the case in which P lies between A and C. Then the triangle with two vertices at −λ^{−1}a, and u will have the correct tangent tan A at vertex a. By hypothesis, the tangent at vertex C has the form μ\sqrt{k} for some rational μ. Taking the third vertex to be μ^{−1}a yields the correct tangent tan B at this vertex. Therefore the triangle is similar to the given one. The cases in which P does not lie between A and C are treated similarly. □

Dimension Five or More

Lemma 5. If n ≥ 5 then the triangle equations have a non-zero solution for any k.

Proof. It suffices to consider n = 5, since we can always let the variables u_{i} and a_{i} for i > 5 be zero. Let k be given. Then k can be written as the sum of four squares (see e.g. Hardy and Wright, p. 302):

k = u_{1}^{2} + u_{2}^{2} + u_{3}^{2} + u_{4}^{2}

Let u_{5} = 0, and let a_{1} = 0 = a_{2} = a_{3} = a_{4}, and a_{5} = 1. □

Remark: Similarly, if k is a sum of n − 1 squares, then the triangle equations E(n, k) have a nontrivial solution.

Theorem 6. The following are all equivalent:

• Triangle T is embeddable in Z^{n} for some n.

• All the tangents of the angles of triangle T have rational squares.

• For some k, all the tangents of the angles of triangle T are of the form λ\sqrt{k} for rational λ.

• The triangle equations E(n, k) have a non-zero solution and all the tangents of the angles are of the form λ\sqrt{k} for rational λ.

• Triangle T is embeddable in Z^{5}.

Proof. We show that each claim in the theorem implies the next; since the last one is a special case of the first, that will suffice. Suppose triangle T is embeddable in Z^{n}. By Proposition 2, the tangents of all the angles of T have rational squares.

Now suppose all the tangents of angles of T have rational squares. By Lemma 3, there is a positive square-free integer k such that all the tangents of angles of T are rational multiples of \sqrt{k}.

Now suppose all the tangents are rational multiples of \sqrt{k}. By Proposition 4, the triangle equations E(n, k) are solvable.

Now suppose E(n, k) is solvable and the angles of a triangle have tangents which are rational multiples of \sqrt{k}. By Lemma 5, the equations are solvable already when n = 5. By the second half of Proposition 4, the triangle is embeddable in Z^{5}. □

Quaternions and Orthogonal Transformations of R^{4}

Background information on quaternions can be found in Hardy and Wright, p. 303. We assume the reader knows the basic properties of quaternions. A four-vector (x_{1}, x_{2}, x_{3}, x_{4}) can be regarded as a quaternion x_{1} + x_{2}i + x_{3}j + x_{4}k. To fix some notation: If x = x_{1} + x_{2}i + x_{3}j + x_{4}k, then the conjugate x∗ is defined by x∗ = x_{1} − x_{2}i − x_{3}j − x_{4}k, the norm is defined by |x|^{2} = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2}. We have xx∗ = |x|^{2} + 0i + 0j + 0k which we shall identify with the scalar |x|^{2}. The multiplicative inverse of x is x^{−1} = x ∗ /|x|^{2}.

Lemma 7. Given a fixed quaternion α, an orthogonal transformation T_{α} on R^{4} is defined by T_{α}x = xα, where on the right we mean quaternion multiplication. That is, T_{α} preserves orthogonality and multiplies lengths by a constant factor.

Proof. A simple calculation. Let x = x_{1}+x_{2}i+x_{3}j+x_{4}k, y = y_{1}+y_{2}i+y_{3}j+y_{4}k, and α = α_{1}+α_{2}i+α_{3}j+α_{4}k. Note that the dot product of two vectors x·y is the real part of the quaternion product xy∗. Hence (xα)·(yα) is the real part of (xα)(yα)∗ = xαα∗y∗ = x|α|^{2}y∗ = |α|^{2}xy∗, whose real part is |α|^{2}x·y. Hence orthogonality is preserved. Taking x = y we see that lengths are multiplied by |α|^{2}. □

Dimension 4

We first characterized the triangles embeddable in Z^{4} by using a computer to show that certain triangles are not embeddable in Z^{4}. This proof showed by direct search that the triangle equations E(4, k) have no solutions mod 32 in which the variables have no common factor, when k = 7, 15, 23, 31. It is possible to prove Theorem 8 below from this result. The program we used, written in the C language, ran for several hours on an IBM PC/AT. Later we found the more insightful proof given here.

Theorem 8. The triangle equations E(4, k) are solvable iff k is a sum of three squares. Geometrically stated: A triangle is embeddable in Z^{4} if and only if all of its tangents are rational multiples of \sqrt{k}, where k is a sum of three squares.

Proof. If a triangle is embeddable in Z^{n}, for any n, then there is a k such that the tangents of its angles all lie in Q(\sqrt{k}), as has been proved above. Hence the main claim of the theorem follows from the equivalence of the first two propositions.

If k is a sum of three squares, then E(4, k) is automatically solvable, as remarked after Lemma 5. Thus it will suffice to show that if E(4, k) is solvable, then k is a sum of three squares. Suppose that a and u are four-vectors solving E(4, k), that is k|a|^{2} = |u|^{2} and a · u = 0. Consider the four-vectors as quaternions. Let b = aa∗ (considered as a four-vector or quaternion, not as a scalar), and let v = ua∗, where we mean quaternion multiplication on the right. Since quaternion multiplication preserves orthogonality, we have b · v = 0. We have

k|b|^{2} = k|a|^{4}
= |a|^{2}k|a|^{2}
= |a|^{2}|u|^{2}
= |a|^{2}uu∗
= uaa ∗ u∗
= ua(ua)∗
= vv∗
= |v|^{2}

Hence b and v are a new solution to the triangle equations E(4, k). But b = aa∗ has only its first component non-zero. Since v is orthogonal to b by Lemma 7, v lies in the three-dimensional subspace of vectors with zero first component. Hence we have k|b|^{2} = v_{2}^{2} + v_{2}^{2} + v_{3}^{2}. Hence k|b|^{2} is a sum of three squares.

Note that since b = aa∗, we have |b|^{2} = |a|^{4}, so |b| = |a|^{2} is an integer. It is well-known (see e.g. LeVeque p. 187) that a number fails to be a sum of three squares if and only if it is a power of 4 times a number congruent to 7 mod 8. If k were of this form, then k|b|^{2} would also be of this form, since every odd square is congruent to 1 mod 8. Hence it follows from the facts that k|b|^{2} is a sum of three squares and |b| is an integer that k is also a sum of three squares. □

Another proof of Theorem 8: J. McCarthy has pointed out that the fact that the tangents are rational multiples of \sqrt{k} where k is a sum of three squares can be proved without use of the triangle equations, as follows: by Lemma 3, it suffices to consider only one angle θ, with vertex at origin and sides given by vectors x and y. We have

tan^{2} θ = sec^{2} θ − 1

= \frac{|x|^{2}|y|^{2}}{(x · y)^{2}} − 1

= \frac{|x|^{2}|y|^{2} − (x · y)^{2}}{(x · y)^{2}}

Therefore tan θ is a rational multiple of

k = |x|^{2}|y|^{2} − (x · y)^{2}
= (Σx_{i}^{2})(Σy_{i}^{2}) − (Σx_{i}y_{i})^{2}

The proof will be completed by observing an identity which expresses the last expression as a sum of three squares:

(Σx_{i}^{2})(Σy_{i}^{2}) − (Σx_{i}y_{i})^{2}
=(x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2})(y_{1}^{2} + y_{2}^{2} + y_{3}^{2} + y_{4}^{2}) − (x_{1}y_{1} + x_{2}y_{2} + x_{3}y_{3} + x_{4}y_{4})^{2}
=(x_{1}y_{2} − x_{2}y_{1} + x_{3}y_{4} − x_{4}y_{3})^{2}
+ (x_{1}y_{3} − x_{3}y_{1} − x_{2}y_{4} + x_{4}y_{2})^{2}
+ (x_{1}y_{4} − x_{4}y_{1} + x_{2}y_{3} − x_{3}y_{2})^{2}

McCarthy found this identity by generalizing the corresponding three-dimensional identity

|x|^{2}|y|^{2} = (x · y)^{2} + |x × y|^{2}

It is really just the identity expressing the multiplicativity of the quaternion norm, applied to the two quaternions x and y∗.

This alternate proof is interesting because it shows a uniformity in the derivation of the necessary condition on k for different dimensions; the two-dimensional case of this identity is

\frac{tan^{2} θ}{(x · y)^{2}} =(x_{1}^{2} + x_{2}^{2})(y_{1}^{2} + y_{2})^{2} − (x_{1}y_{1} + x_{2}y_{2})^{2}
=(x_{1}y_{2} − x_{2}y_{1})^{2}

which explains why the tangent is rational in two dimensions.

Corollary 9. There are triangles embeddable in Z^{5} but not Z^{4}. For example, the isosceles triangle of base 2 and height \sqrt{7}.

Dimension 3

The following very short proof took a long time to find; see the Postscript.

Theorem 10. If k is a sum of three squares, then E(3, k) is solvable in integers. Hence the same triangles are embeddable in Z^{4} as in Z^{3}, and E(3, k) is solvable if and only if k is a sum of three squares.

Proof. By our results on embeddability in Z^{4}, it suffices to prove the first claim. Suppose k = x^{2} + y^{2} + z^{2}. Define

a = (z, z, −y − x)

.

u = (y^{2} + xy + z^{2}, x^{2} + xy + z^{2}, xz − yz)

One can easily check that a and u (regarded as quaternions with zero real part) are obtained by multiplying the known solution (1, 0, 0, 0) and (0, x, y, z) of E(4, k) on the right by the quaternion 0+zi+zj+(−y −x)k. Hence, by Lemma 7, the transformed vectors are still orthogonal and have the same ratio \sqrt{k} of length, so a and u solve the triangle equations E(3, k). □

Remark: One can produce a and u deus ex machina and verify by a simple direct computation that they do solve the triangle equations, without ever mentioning quaternions. For example, type the three equations for k, a, and u into Mathematica and then ask Simplify[a.u] and Simplify[k(a.a) - u.u].

Embeddability of regular polygons in plane lattices

We show that an old result is a corollary of our main theorem. The original proofs (there are two independent ones in the literature) are much easier than the proof of our main theorem, so the fact that it is a corollary of our theorem is only of interest for the connection, and not for the result itself. The original proofs are discussed in the next section.

Theorem. (Schoenberg [1937], Scherrer [1946]) Suppose a regular n-gon is embeddable in Z^{k} for some k. Then n = 3,4, or 6.

Proof. If we have an embedded n-gon, then there is an embedded isosceles triangle with one angle of 2π/n. The other two angles are each π/2 − π/n. Their tangents are thus cot π/n. The non-embeddability of an n-gon in any Z^{k} will then follow from our theorem when cot^{2}(π/n) is irrational. Since

cot^{2} θ = \frac{1 + cos 2θ}{1 − cos 2θ}

we have

cos 2θ = \frac{cot^{2} θ − 1}{cot^{2} θ + 1}

so cos 2θ is rational if and only if cot^{2}θ is rational. Hence an embedded n-gon is possible if and only if cos(2π/n) is rational. To complete the proof, we have to show that cos(2π/n) is rational exactly when n = 3, 4, or 6.

Let ζ = e^{2πi/n}. Then the minimal polynomial of ζ has degree ϕ(n), where ϕ is the Euler ϕ-function. (See for example Borevich and Shafarevich [1966], p. 326.) Since 2 cos(2π/n) = ζ + 1/ζ, we have f(ζ) = 0 for a quadratic polynomial f with coefficients in Q(cos(2π/n)). Hence the degree of the field extension [Q(ζ) : Q(cos(2π/n)] is at most 2. On the other hand it is at least 2, since cos(2π/n) is real. Hence the degree of cos(2pi/n) over the rationals is ϕ(n)/2. This can be one if and only ϕ(n) = 2, that is, n = 3, 4, or 6. □

History and Related Work

The first proof that the equilateral triangle is not embeddable in Z^{2} was given (so far as I know) by E. Lucas [1878]. Lucas’ proof is perhaps more accessible in Pólya and Szegö [1954], page 376 (problem 238). Since it is only a few lines, and not published elsewhere in English, it seems worth reprinting:

Put one corner of the hypothetical equilateral triangle at origin, the other corners at (a, b) and (x, y), and supposing that x, y, a, b have no common factor. Then we have

x^{2} + y^{2} = a^{2} + b^{2} = (x − a)^{2} + (y − b)^{2}

and hence

2(xa + by) = x^{2} + y^{2} = a^{2} + b^{2}
x^{2} + y^{2} + x^{2} + b^{2} = 4(xa + yb) ≅ 0 mod 4

Since we have excluded the case of x, y, a, b all divisible by 2, they must all be odd. In that case, however, the equation

x^{2} + y^{2} = (x − a)^{2} + (y − b)^{2} mod 4

is impossible, completing the proof.

So far as I can determine, John McCarthy was the first to state and prove (although he did not publish) the generalization of Lucas’ theorem to planar polygons (Proposition 1 of this paper). One of the referees suggested that this theorem was part of the “folklore” of the subject, and should not be credited to McCarthy; but Lucas’ proof is very special, and when Pólya and Szegö give it, as recently as 1954, there is no hint of a generalization, nor is this generalization mentioned in any of the other related papers discussed below, and these are all the papers I could find on the subject.

Rather than ask about arbitrary planar triangles, people seemed to have generalized Lucas’ theorem in another direction, asking about arbitrary regular polygons.

Schoenberg [1937] proved that a regular n-gon with n different from 3,4, and 6, is not embeddable in Z^{k}, or indeed any (possibly oblique) rational lattice in k-space for any k. Although it refers to k dimensions instead of a plane, it actually suffices to consider only planar lattices, since if a polygon were embeddable in Z^{k}, then the intersection of the plane of the polygon with Z^{k} would be a planar lattice. Schoenberg’s proof is short: Let A,B,and C be three consecutive vertices of a regular lattice n-gon with center at origin. Let P = A + C. Then |P | = 2|B| cos(2π/n), so cos^{2}(2π/n) is rational. Then we can finish the proof as in the previous section, except that the cases n = 8 and n = 12 still need attention. (Schoenberg [1937], p. 50, jumps too quickly for me to follow to the conclusion that cos(2π/n) is rational.)

Scherrer [1946], apparently unaware of Schoenberg [1937], gave another proof of this theorem. His proof is a gem: Suppose we had an embedded n-gon (for n > 6). Consider the lattice vectors formed by the sides. Translate them, putting their tails all at origin. Then their heads form a smaller lattice n-gon, in fact smaller by at least a certain factor, namely 2 sin(π/n). Iterating this construction leads to arbitrarily small lattice n-gons, a contradiction. This proof works even for non-square lattices, which we have not considered in this paper. Scherrer also showed the case n = 5 is impossible, by a similar construction: Number the sides of a pentagon, considered as vectors, by 1,2,3,4,5. Then taking them in the order 1,3,5,2,4, place the tail of each at the head of the previous one. You will get a five-pointed star. Connecting the points, you get a smaller lattice pentagon than you started with. For square lattices, Scherrer could have ruled out n = 3 and n = 6 by Lucas’ theorem.

The main point of Schoenberg [1937] is not polygons, but rather necessary and sufficient conditions for the embeddability of a regular n-simplex in Z^{n} (it is always embeddable in Z^{n+1}, for example taking all the points with one coordinate 1 and the rest 0). Although the equilateral triangle is not embeddable in Z^{2}, the tetrahedron is embeddable in the unit cube, for example at (1, 0, 0), (0, 1, 0), (0, 0, 1), and (1, 1, 1). Schoenberg showed that, for n even, the embedding is possible if and only if n + 1 is a perfect square; for n ≅ 3 mod 4, it is always possible and for n ≅ 1 mod 4, if and only if n + 1 is a sum of two squares.

The fact that the 4-simplex is not embeddable in Z^{4} refutes the idea that perhaps a polyhedron is embeddable if all of its triangles are embeddable.

Nobody seems to have considered the question of the embeddability of arbitrary triangles until the 1980’s. Landau and Cremona [1987] consider the following question: given that a triangle is embeddable in Z^{n}, what is the smallest embedding? That is, find the smallest triangle similar to the given one which has its vertices on lattice points in n-space. They answer the question in dimensions 3 and 4 using the greatest-common-divisor algorithm in the quaternions. Since now we know that triangles embeddable in Z^{4} are also embeddable in Z^{3}, we might wonder if a smallest embedding can always be found in Z^{3}. The answer (according to a letter from Landau) is no: although a lattice triangle in Z^{4} can always be rotated and dilated into Z^{3}, sometimes a dilation is really required.

Postscript on the Disappearing Computer

All the proofs above use only elementary number theory. This is interesting, considering that a computer was involved throughout this research. First I used it to discover that the isosceles triangle of height \sqrt{7} and base 2 is not embeddable in Z^{3}; then that the same triangle is not embeddable in Z^{4}; then to settle the question of non-solvability of E(4, k) if k is not a sum of four squares. At first I expected to use it to find an example of a triangle embeddable in Z^{4} but not in Z^{3}. Only after using it to find actual solutions of E(3, k) for k a sum of three squares up to 128 did I give up my preconceptions and try to prove that the same triangles are embeddable in three-space as in four-space. When I learned how to use quaternions to describe orthogonal transformations of four-space, all my programs were displaced by the concise elegance of “real mathematics”.

TRIANGLES WITH VERTICES ON LATTICE POINTS 9

References

Borevich, Z. I., and Shafarevich, I. R., Number Theory, Academic Press, New York–London (1966). Erdös, P., Gruber, P. M., and Hammer, J., Lattice Points, Wiley, New York (1989). Hardy, G. H. and Wright, E. M., The Theory of Numbers, Clarendon Press, Oxford (1968). Landau, S., and Cremona, J., Shrinking Lattice Polyhedra, Technical Report 87-05, Wesleyan University

Department of Mathematics, Middletown, CT 06457 (1987). LeVeque, W. J. The Elementary Theory of Numbers, Addison-Wesley, Reading, Massachusetts (1962). Lucas, E. Théorème sur la Géométrie des Quinconces, Bull Soc. Math. France 6 (1878) 9-10. Patruno, G. N., The lattice polytope problem, Elemente der Mathematik 38 (1983) 69-71. Pólya, G., and Szegö, G., Aufgaben und Lehrsätze aus der Analysis, Band II, Springer-Verlag, Berlin-

Göttingen-Heidelberg (1954).

Scherrer, W., Die Einlagerung eines regulären Vielecks in ein Gitter, Elemente der Mathematik 1 (1946) 97-98.

Schoenberg, I. J., Regular simplices and quadratic forms, J. London Math. Soc. 12 (1937) 48-55.