Metric Invariants of Tetrahedra via Polynomial Elimination

Petr Lison� ek^{∗}

Department of Mathematics and Statistics Simon Fraser University Burnaby, BC Canada V5A 1S6

lisonek@cecm.sfu.ca

Robert B. Israel

Department of Mathematics University of British Columbia Vancouver, BC Canada V6T 1Z2

israel@math.ubc.ca

ABSTRACT

We use Gröbner bases and the Pedersen-Roy-Szpirglas real solution counting method to analyze systems of algebraic equations satisfied by metric invariants of the tetrahedron. The transformation from the geometric to the algebraic setting is effected using the Cayley-Menger determinant formula for the volume of a simplex. We prove that, in general, the four face areas, circumradius and volume together do not uniquely determine a tetrahedron, and that there exist non-regular tetrahedra that are uniquely determined just by the four face areas and circumradius. This settles two open problems posed by the American Mathematical Monthly in 1999.

1. INTRODUCTION

Let ℝ^{n} denote the n-dimensional Euclidean space with the usual metric. The distance between points P and Q will be denoted by d(P, Q). Consider a general tetrahedron T in ℝ^{3} and let v_{i} (i = 1, 2, 3, 4) be the vertices of T. Clearly, T is determined uniquely (up to a rigid motion) if the lengths d(v_{i}, v_{j}) of its six edges are given. In this paper we address the question whether T can be determined uniquely by sets of metric invariants other than edge lengths. Specifically, we prove in Section 3 that, in general, the four face areas, circumradius and volume together do not uniquely determine a tetrahedron, while in Section 4 we prove that there exist non-regular tetrahedra that are uniquely determined just by the four face areas and circumradius. This answers two questions posed recently as open problems—see [3] for details.

The notation for the metric invariants of T is as follows: Let the squared edge lengths be

s_{i,j} = d(v_{i}, v_{j})^{2}.  (1)

∗Research supported by the Symbolic Analysis project of The Mathematics of Information Technology and Complex Systems (MITACS) Network of Centres of Excellence.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro�t or commercial advantage, and that copies bear this notice and the full citation on the �rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci�c permission and/or a fee. ISSAC 2000, St. Andrews, Scotland

\begin{matrix}c \\ ◯ \end{matrix}2000 ACM 1-58113-218-2/ 00/ 0008 $5.00

Let the volume be V and the circumradius (i.e. radius of the circumscribed sphere) R. Let the area of the face v_{i}v_{j}v_{k} be A_{l}, where {i, j, k} ∪ {l} = {1, 2, 3, 4}.

2. FORMULATION OF THE POLYNOMIAL SYSTEM

Let P_{i} (1 ≤ i ≤ n) be n points in ℝ^{n−1} and denote d_{i,j} = d(P_{i}, P_{j}). The Cayley-Menger determinant ([1], §40) associated with the points P_{i} (1 ≤ i ≤ n) is the determinant of the (n + 1) × (n + 1) matrix

D(P_{1}, …, P_{n}) = | \begin{matrix}0 & 1 & 1 & ⋯ & 1 \\ 1 & 0 & d_{1,2}^{2} & ⋯ & d_{1,n}^{2} \\ 1 & d_{2,1}^{2} & 0 & ⋯ & d_{2,n}^{2} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & d_{n,1}^{2} & d_{n,2}^{2} & ⋯ & 0 \end{matrix} | . (2)

The (n − 1)-dimensional volume Vol(P_{1}, …, P_{n}) of the convex hull of P_{1}, …, P_{n} satisfies the equality ([1], p. 98)

Vol(P_{1}, …, P_{n})^{2} = \frac{(−1)^{n}}{2^{n−1}((n − 1)!)^{2}} D(P_{1}, …, P_{n}). (3)

Hence, the face areas and the volume of the tetrahedron can be expressed as low degree polynomials in the squared edge lengths s_{i,j}. In the case of triangles, (3) is a disguise of the Heron formula.

Let C denote the center of the circumscribed sphere of our tetrahedron. The five points v_{1}, v_{2}, v_{3}, v_{4}, C lie in a threedimensional space (a hyperplane of ℝ^{4}) and therefore Vol(v_{1}, v_{2}, v_{3}, v_{4}, C) = 0. Hence, the algebraic equation for the circumradius R is

D(v_{1}, v_{2}, v_{3}, v_{4}, C) = 0  (4)

where d(v_{i}, C) = R for 1 ≤ i ≤ 4.

Consider seven positive real numbers a_{1,2}, a_{1,3}, …, a_{3,4}, W. It is now clear that the statement “The volume of the tetrahedron with edge lengths \sqrt{a_{1,2}}, \sqrt{a_{1,3}}, …, \sqrt{a_{3,4}} is W ” implies the statement “The point (a_{1,2}, a_{1,3}, …, a_{3,4}, W) is a zero of the polynomial f_{1}(s_{1,2}, s_{1,3}, …, s_{3,4}, V),” where the explicit form of f_{1} can be easily extracted from (1–3). In a similar fashion, the analogous statements about the other metric invariants of the tetrahedron (circumradius, four face areas) imply statements about zeros of certain five other polynomials f_{2}, …, f_{6} with rational coefficients.

Since we are turning a geometric problem into an algebraic one, we should make sure that we are not merely working with abstract algebraic objects that do not have meaning (interpretation) back in the original geometric setting. The essential question to be raised here is, for which sextuples (s_{1,2}, s_{1,3}, …, s_{3,4}) ∈ (ℝ^{+})^{6} there exists a tetrahedron whose squared edge lengths take up the values s_{i,j}. It is shown in [1], §40 that this is the case exactly when all squared volumes (3) evaluate non-negative, which therefore is not only necessary but also sufficient condition for the existence of the tetrahedron. The important consequence is that whenever there exists a solution (a_{1,2}, a_{1,3}, …, a_{3,4}) ∈ (ℝ^{+})^{6} to a system f_{1}^{∗} = 0, …, f_{6}^{∗} = 0, where f_{i}^{∗} is f_{i} with V, R, A_{1}, …, A_{4} substituted by positive real constants, then this solution has a geometric interpretation (corresponds to a tetrahedron in ℝ^{3}, whose edge lengths are \sqrt{a_{i,j}}).

Since scaling does not influence the nature of our problem in any way, we can typically allow ourselves to assign a positive constant value to one of the variables, for example R.

3. A SEXTUPLE OF METRIC INVARIANTS

The question whether a tetrahedron is uniquely determined by its volume, circumradius and face areas was posed as an open problem in [3]. In this section we answer this question negatively. We follow the constructive approach, that is, establishing two (or more) tetrahedra that share the same volume, circumradius and face areas.

Consider a tetrahedron T given by squared edge lengths. Equations for the volume, circumradius and face areas of T can be obtained by substituting the values of s_{i,j} into the polynomials f_{1}, …, f_{6} introduced earlier. Conversely, by substituting the numerical values of V, R, A_{1}, …, A_{4} into the f_{i}’s we set up a polynomial system in the squared edge lengths as unknowns—let us call this system F^{∗} = {f_{1}^{∗}, …, f_{6}^{∗}}. Following the discussion at the end of Section 2, we are interested in the distinct positive solutions to F^{∗}. To determine these solutions we first find G, a grevlex Gröbner basis for F^{∗}. (Remark: In all numerical examples that we tried, we found that ⟨F^{∗}⟩ was a zero-dimensional ideal.) Then we use the method of Pedersen, Roy and Szpirglas to count all real solutions of F^{∗}. (We refer to the presentation of this method in Chapter 2 of [2], in particular we will use the terminology and notation introduced therein.) Let p_{i,j} be the generators for the univariate elimination ideals, that is, ⟨p_{i,j}⟩ = ℂ[s_{i,j}] ∩ ⟨F^{∗}⟩. Using the theory in Chapter 2, Section 2 of [2] we can find the p_{i,j}’s from the grevlex Gröbner basis G by working in the algebra A = ℂ[s_{1,2}, s_{1,3}, …, s_{3,4}] / ⟨G⟩. Then we use interval arithmetic (together with the knowledge of the total number of real solutions) to isolate the real solutions of F^{∗} and eventually we select the positive solutions. It is easy to come up with examples in which there will be several different tetrahedra sharing the same volume, circumradius and face areas, as is illustrated in the following example.

3.1 A Numerical Example

We will now demonstrate our approach on a numerical example. We skip some intermediate expressions because of their large size. A Maple worksheet (and its exported HTML version) containing all computational details is available at the URL

                                                         http://www.cecm.sfu.ca/~lisonek/tetrahedron.html

The entire computation takes about five minutes on an SGI workstation.

Consider the tetrahedron defined by

(s_{1,2}, s_{1,3}, s_{1,4}, s_{2,3}, s_{2,4}, s_{3,4}) = (1, 1, 2, 2, 1, 2).

We find that V = \sqrt{1/48}, R = \sqrt{7/12}, A_{1} = A_{2} = \sqrt{7/16} and A_{3} = A_{4} = 1/2. By substituting these six values in the polynomials f_{1}, …, f_{6} we obtain the set F^{∗} = {f_{1}^{∗}, …, f_{6}^{∗}}. Next we compute G, the Gröbner basis for F^{∗} with respect to the grevlex ordering induced by s_{1,2} > s_{1,3} > … > s_{3,4}, and the basis for the algebra A = ℂ[s_{1,2}, s_{1,3}, …, s_{3,4}] / ⟨F^{∗}⟩. It turns out that that the dimension of A is 8, and a basis of A consisting of representatives of monomials is B = (1, s_{1,2}, s_{2,3}, s_{2,4}, s_{2,4}^{2}, s_{1,2}s_{2,4}, s_{3,4}, s_{2,4}s_{3,4}). We then let h to be the constant function 1 and construct the symmetric bilinear form S_{1} as described on p. 65 in [2]. Next we compute the characteristic polynomial of M_{1}, the matrix of S_{1} with respect to B. It turns out that there are six sign variations in the coefficient list of this characteristic polynomial, whence by the Descartes Rule of Signs the signature of S_{1} is four and there are four distinct real solutions to the system F^{∗} by Theorem 5.2 on p. 65 in [2]. Using Maple’s procedure Groebner[univpoly] (which implements the Faugère-Gianni-Lazard-Mora basis conversion method) we use G to find the generators p_{i,j} for the univariate elimination ideals ⟨p_{i,j}⟩ = ℂ[s_{i,j}] ∩ ⟨F^{∗}⟩. They turn out to be the following polynomials:

p_{1,2}(x) = (x − 1)a(x)
p_{1,3}(x) = p_{1,4}(x) = p_{2,3}(x) = p_{2,4}(x)
= (x − 1)(x − 2)b(x)
p_{3,4}(x) = (x − 2)c(x)

where

a(x) = 9x^{3} − 123x^{2} + 491x − 249
b(x) = 81x^{6} − 1485x^{5} + 10215x^{4} − 25803x^{3} + 22865x^{2}
− 3303x + 162
c(x) = 9x^{3} − 150x^{2} + 1028x − 960.

Using Sturm’s Theorem (Maple’s procedure realroot) we find the isolating intervals for all real roots of a, b and c; it turns out that a and c have one real root each, namely α_{1} ∈ [75/128, 19/32] and γ_{1} ∈ [35/32, 141/128], respectively, while b has two real roots β_{1} ∈ [219/128, 55/32] and β_{2} ∈ [267/128, 67/32]. It also turns out that these isolating intervals are narrow enough to prove (using interval arithmetic) that only four boxes in ℝ^{6} (obtained as Cartesian products of the isolating intervals) can possibly contain a solution of F^{∗}; since we know from earlier developments that there exactly four real solutions, we have isolated all solutions of F^{∗}. Their values (s_{1,2}, s_{1,3}, s_{1,4}, s_{2,3}, s_{2,4}, s_{3,4}) are (1, 2, 1, 1, 2, 2), (1, 1, 2, 2, 1, 2), (α_{1}, β_{1}, β_{2}, β_{2}, β_{1}, γ_{1}) and (α_{1}, β_{2}, β_{1}, β_{1}, β_{2}, γ_{1}). Since all s_{i,j} values are positive in all four solutions, it follows (cf. the discussion at the end of Section 2) that we have constructed four different tetrahedra that all share the same volume, circumradius and face areas. By inspecting the four solutions we see that the four tetrahedra pair up into two pairs, with the elements of each pair related by interchanging the labels of the vertices v_{1} and v_{2}; yet we have obtained two essentially different tetrahedra.

Summarizing the developments of this section, we have:

Proposition 1. There are tetrahedra which are not uniquely determined by the four face areas, circumradius and volume.

4. A QUINTUPLE OF INVARIANTS

It is noted in part (b) of [3] that the quintuple of values (A_{1}, A_{2}, A_{3}, A_{4}, R) uniquely determines any regular tetrahedron, in which case of course A_{1} = A_{2} = A_{3} = A_{4} = \sqrt{4/3}R^{2}. The question whether there exist non-regular tetrahedra determined uniquely by (A_{1}, A_{2}, A_{3}, A_{4}, R) is posed as an open problem in [3].

Proposition 2. There exist non-regular tetrahedra determined uniquely by the four face areas and the circumradius.

Again, our proof is constructive:

Proposition 3. Every non-degenerate tetrahedron, whose one face is an equilateral triangle inscribed in a great circle of the circumscribed sphere, is determined uniquely by its four face areas and circumradius.

Proof. We can assume without loss of generality that R = 1. It is easy to see that 3\sqrt{3}/4 is the maximum area among all triangles inscribed in a unit sphere, and it is attained only by equilateral triangles inscribed in a great circle of the sphere. Therefore we have already determined the shape of one of the faces of the tetrahedron by requiring its area to be equal to 3\sqrt{3}/4. Let us assume that this face is v_{1}v_{2}v_{3}. We have R = 1, s_{1,2} = s_{1,3} = s_{2,3} = 3 and A_{4} = 3\sqrt{3}/4. Let F′ be the set of polynomials f_{2}, …, f_{6} from Section 2 with the values from the previous sentence substituted. It takes only a few seconds to compute the Gröbner basis for the ideal generated by F′ for the lexicographic ordering induced by s_{3,4} > s_{2,4} > A_{1} > A_{3} > A_{2} > s_{1,4}. This basis contains (among others) the polynomials f^{2} and g^{2}, where

f = 81s_{1,4}^{4} − 432s_{1,4}^{3} + 288(A_{2}^{2} + A_{3}^{2})s_{1,4}^{2}

+256A_{2}^{4} + 256A_{3}^{4} − 512A_{2}^{2}A_{3}^{2}

g = 9s_{1,4}^{2} − 54s_{1,4} − 16A_{1}^{2} + 32A_{2}^{2} + 32A_{3}^{2} + 27.

Further we have

f = Q · g + S  (5)

where

Q = 9s_{1,4}^{2} + 6s_{1,4} + 16A_{1}^{2} + 9
S = (960A_{1}^{2} − 192A_{2}^{2} − 192A_{3}^{2} + 324)s_{1,4}

+256(A_{1}^{4} + A_{2}^{4} + A_{3}^{4}) − 512(A_{1}^{2}A_{2}^{2} + A_{1}^{2}A_{3}^{2} + A_{2}^{2}A_{3}^{2}) −288(A_{1}^{2} + A_{2}^{2} + A_{3}^{2}) − 243.

If both f and g vanish, then S must vanish by (5). The equation S = 0 determines s_{1,4} uniquely if L, the coefficient at s_{1,4} in S, is non-zero. The discriminant of g as a quadratic polynomial in s_{1,4} is

Z = 576A_{1}^{2} − 1152A_{2}^{2} − 1152A_{3}^{2} + 1944,

and we observe that 6 · L = 5184A_{1}^{2} + Z. If there exists a tetrahedron with face areas A_{1}, A_{2}, A_{3}, 3\sqrt{3}/4 and circumradius 1, then g must have a real (positive) root, hence Z ≥ 0 and consequently L > 0 by non-degeneracy, in particular L ≠ 0. Therefore s_{1,4} is determined uniquely by S = 0. By applying analogous arguments to s_{2,4} and s_{3,4} we prove that all s_{j,4} are determined uniquely (1 ≤ j ≤ 3). Since also s_{1,2} = s_{1,3} = s_{2,3} = 3 are determined uniquely by A_{4} = 3\sqrt{3}/4, we have established that the tetrahedron is determined uniquely.

5. OPEN QUESTIONS

An intriguing question related to the result of Section 3 is whether, for any positive real constants V, R, A_{1}, …, A_{4}, there are finitely many tetrahedra, all having these values as their respective metric invariants.

If the answer is affirmative, what is then the maximal number of such tetrahedra? For example, the values (s_{1,2}, s_{1,3}, s_{1,4}, s_{2,3}, s_{2,4}, s_{3,4}) = (16, 25, 9, 9, 33, 54) yield a family of six such tetrahedra, but we do not know whether this is maximal in terms of the number of different tetrahedra.

The bounds obtained by applying general theorems in algebraic geometry seem quite high compared to the empirical results that we have obtained by running our algorithm on a number of different examples. In cases when the number of (projective) solutions to the system F^{∗} is finite we can apply Bézout’s Theorem and get 3·4·2^{4} = 192 as the bound on the number of solutions. We are indebted to one of the referees for pointing out that a theorem of Milnor [4] gives 9375 as an upper bound on the number of real solutions of F^{∗} that are isolated points.

6. CONCLUSION

We combine classical distance geometry with modern algorithmic methods in polynomial elimination to solve interesting and apparently open problems in three-dimensional Euclidean geometry. The advantage of using the Cayley-Menger determinant is that it allows a coordinate-free approach in which all metric invariants are readily available in terms of the distances between vertices, while at the same time it is faithful to the original geometric setting (one does not introduce spurious algebraic solutions that would not admit geometric interpretation). It is interesting to note that while the number of free variables is relative high (six), the Gröbner basis computations are easily manageable, and it can be expected that a variety of similar geometric problems can be solved in an analogous fashion.

7. REFERENCES

[1] L.M. Blumenthal, Distance Geometry. Chelsea, New York, 1970.

[2] D. Cox, J. Little, D. O’Shea, Using Algebraic Geometry. Springer, 1998.

[3] Problem 10717 (proposed by M. Mazur). Amer. Math. Monthly 106 (February 1999), 167.

[4] J. Milnor, On the Betti numbers of real algebraic varieties. Proc. Amer. Math. Soc. 15 (1964) 275–280.