From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Tetrahedral Inequality Date: 25 May 1998 20:22:32 GMT If you are given 3 line segments of length a, b, and c, you may form them into a triangle iff the triangle inequalities are met: each of a+b-c, b+c-a, c+a-b must be positive. Suppose you are given 6 line segments of lengths a,b,c,d,e, and f, and you wish to form them into a tetrahedron. There may be several ways to do this; let us assume you want the non-intersecting pairs of edges to be {a,f}, {b,e}, and {c,d}. (If you are at liberty to connect the edges as you see fit, then you would consider 15 permutations of this problem.). It is clear that there are relations on {a, ..., f} which must be satisfied if this tetrahedron is to be formed: at the very least, the four sets of triangle inequalities must be satisfied so that the faces {a,b,d}, {a,c,e}, {b,c,f}, {d,e,f} may be constructed. There is an additional inequality to be satisfied, however. You can see this easily if the lengths are a=b=c=d=e=1, f=7/4, say. Here, the triangles {a,b,d} and {a,c,e} are isosceles triangles joined at the edge a like a hinge. All the tetrahedra including these two faces may be formed by swinging one triangle around the common edge. Clearly the remaining edge -- the one joining the points of the hinge -- can have lengths only in the interval [0, sqrt(3)]. Thus this tetrahedron is impossible even though all 12 triangle inequalities are satisfied. (You can vary these dimensions and retain the construction of a 1-parameter family of tetrahedra with 5 given lengths to see that the sixth length must generally be in a narrower range than is dictated by the triangle inequalities for the other two faces.) The condition that the six lengths form a tetrahedron appears to be the negativity of AF(A+F) + BE(B+E) + CD(C+D) + (ABD + ACE + BCF + DEF) - AF(B+C+D+E) - BE(A+C+D+F) - CD(A+B+E+F) where I have set A=a^2, ..., F=f^2 for brevity. My questions are these: 1. Given that the triangle inequalities are satisfied, does this formula simplify? (i.e. is there a simpler polynomial in a, ..., f with the property that (a+b-e>=0, ...) => (P1 >=0 iff P2 >=0) ? It _is_ true that if you view the polynomial above as a quadratic in F (say), then its discriminant is not identically positive, but its positivity is forced by the triangle inequalities on the two faces including edge a . 2. Surely this is an ancient result. Can anyone supply an old reference? 3. Is there a fairly geometric derivation of this formula? I must confess I derived this condition by the heresy of introducing coordinates. 4. What about higher dimensional simplices? dave ============================================================================== To: rusin@vesuvius.math.niu.edu (Dave Rusin) From: trailler@aol.com (Trailler) Subject: Re: Tetrahedral Inequality (and Tetrahedral Volume!) Date: 26 May 1998 05:24:14 GMT Newsgroups: sci.math This same expression turned up when I was working a (96?) putnam problem ( to show that there is no tetrahedron all of whose edges have odd length with integral volume.) Moreover in the few cases I checked it seemed like if I call dave's expression K = AF(A+F) + BE(B+E) + CD(C+D) + (ABD + ACE + BCF + DEF) - AF(B+C+D+E) - BE(A+C+D+F) - CD(A+B+E+F) where A=a^2, ..., F=f^2, as defined in dave's original message, then the volume of the tetrahedron V = sqrt (-K)/12. Which would be consistent with dave's theorem, since obviously if the 6 edges form a tetrahedron the volume must be nonnegative, so K <= 0. (And which, if true, led to a trivial proof of the putnam problem, since if a,b,c,d,e,f are odd, A=B=...=F = 1 mod 4, so K = 2 mod 4 and hence can't be a perfect square.) This is a 3d analog of the formula for the area of a triangle given edges a,b,c in terms of the semiperimeter A = sqrt (s(s-a)(s-b)(s-c)) I didn't want to crank through the coordinate algebra necessary to prove this volume formula, so it remains a hypothesis. So I too second the questions: --is this an old result? --does it simplify? --is there a simple geometrical proof? in Message-id: <6kcju8$3cc$1@gannett.math.niu.edu> rusin@vesuvius.math.niu.edu (Dave Rusin) wrote: [original post slightly edited within this follow-up. -- djr] Gary Miller (millerg@adsnet.net) "The greatest obstacle to communication is the misconception that it has already occurred." ============================================================================== From: Robin Chapman Newsgroups: sci.math Subject: Re: Tetrahedral Inequality Date: Tue, 26 May 1998 07:21:26 GMT In article <6kcju8$3cc$1@gannett.math.niu.edu>, rusin@vesuvius.math.niu.edu (Dave Rusin) wrote: [original post was quoted -- djr] Let's try to construct a tetrahedron with faces {a,b,d}, {a,c,e}, {b,c,f} and {d,e,f} so that the pairs of opposite edges are {a,f}, {b,e}, {c,d}. Take the origin at the intersection of the edges a, b and c, and let p, q and r be the position vectors of the other three vertices (p, q, r correspond to edges a, b and c resp.). Then we can build the tetrahedron iff the Gram matrix of p, q and r is positive definite. Now p.p = a^2 = A (etc.); also 2 p.q = p.p + q.q - (p - q).(p - q) = A + B - D etc. So we get the condition that the matrix 1 ( 2A A + B - D A + C - E) M = - (A + B - D 2B B + C - F) 2 (A + C - E B + C - F 2C ) be positive definite. One well-known criterion for positive definiteness is that the determinants of square submatrices in the top left corner are all positive. Here this gives A > 0 (OK as a > 0) 4AB > (A + B - 2D)^2, which is equivalent to {a, b, d} forming a triangle and det(M) > 0. Now det(M) is up, to a constant factor, the square of the volume of the putative tetrahdron. This formula can be put into more symmetric form: see 97/herons.tetrahed So we see that we really do get a tetrahedron, if we can build one face, and the square of the putative volume is positive. Clearly this method is valid in any number of dimensions. Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Tetrahedral Inequality Date: 26 May 1998 13:56:07 GMT In an earlier article I wrote > The condition that the six lengths form a tetrahedron appears to be the > negativity of > AF(A+F) + BE(B+E) + CD(C+D) + (ABD + ACE + BCF + DEF) > - AF(B+C+D+E) - BE(A+C+D+F) - CD(A+B+E+F) > where I have set A=a^2, ..., F=f^2 for brevity. and asked for a nice proof. Many thanks to those who responded in mail or by posting. I am embarassed to admit I failed to notice the volume formula for a tetrahedron. Naturally, any formula which purports to give the square of a volume must be nonnegative for a realizable tetrahedron, but that argument is insufficient for me: it's not clear that positivity of the volume-squared formula is conversely enough to guarantee the realizability of the tetrahedron. (Indeed it's not -- the triangle inequalities must still be assumed on each face.) Chapman's solution is a natural one. To his reference >97/herons.tetrahed I can only respond "Touch\'e!" with a red face. I should have known some day it would come to this. An even more fitting file is 98/multidim.scal I really must work on that search engine... This argument for tetrahedra could not be more than 150 years old, yet I suspect the inequality itself could be much older; I am still interested in older citations (and more geometric proofs). dave ============================================================================== From: Dave Rusin [rusin@math.niu.edu] Date: Tuesday, May 26, 1998 4:48 PM To: ksbrown@seanet.com Subject: Re: Tetrahedral Inequality (and Tetrahedral Volume!) Thanks for responding to the thread I initiated. In article <356a5c51.51097800@news.seanet.com> you write: > 144 V^2 = AF(-A+B+C+D+E-F) + BE(A-B+C+D-E+F) + CD(A+B-C-D+E+F) > > - (A+F)(B+E)(C+D)/2 - (A-F)(B-E)(C-D)/2 > >Can the formula be broken down into fewer than 5 terms, where each >"term" is a product of three linear functions of the squared sides? I remember when you asked this question before; nothing came to mind then. But a possible method occurred to me today; you'd have to think about how important the question is to you because I don't think it's easy. You have an expression (=144V^2) in the degree-3 part of the graded polynomial ring Q[A,B,...,F]. You wish to know whether or not this element is the sum of four or fewer elements of the form L1 L2 L3 with L_i in the degree-1 part of the ring. What you need is some invariant of cubic forms which counts the "number of product summands". It may be possible to pursue the analogy with thie following question: given an expression in the _degree-2_ part of the same ring, you may ask for the minimum number of products L1 L2 which must be summed to equal the original expression. Now, this particular question is different because one has the language of quadratic forms, and I think the answer may be given in terms of the signature of the form; none of that generalizes well to cubic forms, however. On the other hand, any such sum of products reduces to another such sum of products mod p for any p not involved in the denominators of the L_i. In particular, one would in the "generic" case be able to write a quadratic polynomial as a sum of products in Z_2[A,B,...,F]. The minimal number of summands in such an expression can be computed, more or less, and this is an important tool in the cohomology of groups! The trick is to use the Steenrod algebra of all (mod-2) cohomology operations. If you're not familiar with that algebra, that's OK in this case, since the action of the Steenrod algebra on a simple polynomial ring is easily described: consider the ring homomorphism S : Z_2[A, B, ...] -> Z_2[A, B, ...] given by its action on the ring generators: S(A)=A+A^2, S(B)=B+B^2, etc. Since this is a ring of characteristic 2, we actually have S(L)=L+L^2 for all linear forms L. It is clear that this S is not degree-preserving, but that if f is a homogeneous polynomial of degree n in the ring, then S(f) = f + (something) + (something) + ... + f^2, where each summand here is supposed to be a homogeneous polynomial of degree n+1, n+2, ..., 2n. For example, S(A^2+B^2+AB) = (A^2+B^2+AB) + (AB(A+B)) + (A^2+B^2+AB)^2 We think of this as an infinite sum with all the trailing terms equal to zero. Thus, S(f) is, for any f, an "infinite" sum of homogeneous terms S(f) = S^0(f) + S^1(f) + S^2(f) + ... where S^0(f) = f and in general deg(S^i(f)) = def(f) + i. So we have now defined a collection of Z_2-linear endomorphisms S^i of the polynomial ring, each increasing the degrees by i. The Steenrod algebra is the subalgebra of the whole endomorphism algebra End( R ) of this infinite-dimensional vector space over Z_2. Like the whole endomorphism algebra of any vector space, this is an associative, non-commutative ring, actually itself an algebra over Z_2, graded by the amount of degree-increase. It's a very complicated algebra in toto; there are relations among these generating operators S^i -- for example S^1 S^2 = S^3 -- known as the Adem relations. I won't bore you with details since we need very little of them. Now suppose q is a quadratic form over Z_2. Form the polynomials q, S^1(q), S^2(S^1(q)), S^4(S^2(S^1(q))), ... of degrees 2, 3, 5, 9, ... It is a result of Serre that eventually these polynomials are all in the ideal generated by just a few of the initial ones. Indeed, the number of S's which may be applied in this way without landing back in the same ideal is a function of the number of products necessary for the writing of q as a sum of products! We don't need complete information here, now that we have this idea. Example: is q a simple product L1 L2 ? Compute S^1(q) and see if it's a multiple of q. If not, q is not a product, since S^1( L1 L2) = L1 L2 (L1+L2) Example: is q a sum of two products q = L1 L2 + L3 L4 ? If so, then S^2(S^1(q)) would have to lie in the ideal generated by q and S^1(q). For some q this provides an easy way to see q is not a sum of two products. These examples assume q is a form of degree _2_; of course one could perform similar calculations on a form of degree _3_. Perform the calculations on the putative expression (e.g. L1L2L3 + L4L5L6 + ...), note a pattern, then perform the calculations on q and see if that pattern indeed holds. If not, you've ruled out the form q would satisfy. The analysis is unsatisfying, particularly since the Steenrod algbera is very much a mod-p thing, and you are willing to entertain rational coefficients. But possibly this suggests some ways to analyze your particular polynomial q. If you decide to pursue this I would be very interested in hearing of any results you obtain. dave ============================================================================== From: ksbrown@seanet.com (Kevin Brown) Newsgroups: sci.math Subject: Re: Tetrahedral Inequality Date: Fri, 29 May 1998 03:32:38 GMT On 25 May 1998 rusin@vesuvius.math.niu.edu (Dave Rusin) wrote: >Suppose you are given 6 line segments of lengths a,b,c,d,e, >and f, and you wish to form them into a tetrahedron. There may >be several ways to do this; let us assume you want the non- >intersecting pairs of edges to be {a,f}, {b,e}, and {c,d}. >(If you are at liberty to connect the edges as you see fit, >then you would consider 15 permutations of this problem.). It occurs to me that there are actually 30 distinct tetrahedra, up to rotations and reflections, that can be formed from six given edges The factor of two arises because there are two distinct shapes for any given choice of "pairings", depending on how we choose to connect those pairs. To illustrate, for the non-intersecting pairs {a,f}, {b,e}, and {c,d} we have the following two distinct tetrahedral graphs _________a_________ _________f_________ \ / \ / \ \ / / \ \ / / \ \c d/ / \ \c d/ / \ \ / / \ \ / / \ \ / / \ \ / / e\ | /b e\ | /b \ | / \ | / \ |f / \ |a / \ | / \ | / \|/ \|/ The only change has been to transpose the edges a <-> f, but notice that in the left-hand figure the edge "a" meets the edges c,e at one end and b,d at the other, whereas in the right-hand figure it meets the edges b,e at one end and c,d at the other. These two distinct configurations are can be seen algebraically in the volume formulae. Recall that Dave Rusin and Gary Miller were discussing the (positive) quantity - AF(A+F) - BE(B+E) - CD(C+D) - (ABD + ACE + BCF + DEF) + AF(B+C+D+E) + BE(A+C+D+F) + CD(A+B+E+F) which was recognized to be 144 V^2 where V is the volume of the tetrahedron whose *squared* edges lengths are A,B,..,F. Then it was mentioned that this is essentially Piero's formula, which reads 144 V^2 = - ABC - ADE - BDF - CEF + ACD + BCD + ABE + BCE + BDE + CDE + ABF + ACF + ADF + CDF + AEF + BEF - CCD - CDD - BBE - BEE - AAF - AFF However, if you look closely, these two formulae are not exactly equivalent. Where Piero had - ABC - ADE - BDF - CEF the previous formula has - ABD - ACE - BCF - DEF Actually both formulas are correct, but they represent the two distinct tetrahedrons that can be constructed from six given edges with given pairings of non-intersecting edges (a,f), (b,e), (c,d). This appears most clearly if we re-write the volume formula as a sum of five "squared volume" terms as follows 144 V^2 = AF[-(A+F)+(B+E)+(C+D)] + BE[(A+F)-(B+E)+(C+D)] + CD[(A+F)+(B+E)-(C+D)] - (A+F)(B+E)(C+D)/2 -+ (A-F)(B-E)(C-D)/2 Notice that the first four terms are symmetrical in the non- intersecting pairs, but the fifth term is anti-symmetric, i.e., it reverses sign when we transpose any of the pairs. That's the reason I put a +- sign on that term. With the - sign it gives Piero's formula, whereas with the + sign it gives the formula discussed by Dave and Gary. So this formula represents the two possible tetrahedron volumes (and shapes) for a given pairing of the edges. _____________________________________________________________ | MathPages /*\ http://www.seanet.com/~ksbrown/ | | / \ | |___________/"But thou art all my art and dost advance _______| As high as learning my rude ignorance." ============================================================================== From: johnmitchell2100@my-deja.com Subject: Re: Achievable distances between points in 3-space Date: Thu, 10 Jun 1999 17:59:04 GMT Newsgroups: sci.math.research Keywords: [missing] [Note: My first post didn't seem to get through, so I'm reposting this.] As an historical reference, the solution given by Dave Rusin and Robert Israel appears in as Theorem 1 in: I.J. Schoenberg, "Remarks to Maurice Frechet's Article "Sur La Definition ...", Annals of Mathematics, Vol. 36, No. 3, July, 1935. Schoenberg states that K. Menger earlier proved the same result "by means of equations and inequalities involving certain determinants" (see Schoenberg's paper for the references). Schoenberg also extends the result to realizations in spheres and "indefinite" spaces. In a related paper ("On Certain Metric Spaces Arising From a Change of Metric and Their Imbedding in Hilbert Space", Annals of Math. Vol. 38, No. 4, October, 1937) Schoenberg says that "this elementary theorem is in substance identical with the well known correspondence between lattices of points and positive definite quadratic forms. See H. Minkowski, Gesammelte Abhandlungen, Vol. 1, pp. 243-254, where also references to Gauss and Dirichlet are found." The original question arises naturally in the investigation of which metric spaces may be isometrically imbedded in Hilbert spaces. Questions of this nature were addressed by Frechet, Jordan, von Neumann, Godel, and others. A minor point: your statement "if not positive definite, the distances are not realizable in Euclidean space" should be "if not positive semi-definite, ...". In article <3757043C.ACF5BF95@csr.csc.uvic.ca>, Frank Ruskey wrote: > Given 6 distances ab, ac, ad, bc, bd, cd is there a simple > efficiently testable (e.g., a determinental criteria) necessary > and sufficient condition for whether there exists 4 points a,b,c,d > in 3-space that have those distances between them? If it > helps, the points may be assumed to all lie on their mutual > convex hull. Extensions to more than 4 points? Please send me > e-mail as well as responding to this group. Thanks. > > -- > ---------------------- > Frank Ruskey e-mail: fruskey@csr.uvic.ca > Dept. of Computer Science fax: 250-721-7292 > University of Victoria office: 250-721-7232 > Victoria, B.C. V8W 3P6 CANADA WWW: http://csr.csc.uvic.ca/~fruskey > > Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't. ============================================================================== From: John_Mitchell@intuit.com Subject: Achievable distances between points in 3-space Date: Wed, 16 Jun 1999 12:30:09 -0700 Newsgroups: [missing] To: rusin@math.niu.edu I hope you don't mind the email, but I thought you might want to add the references I mentioned in my 6/10/99 sci.math.research posting to your web page 98/tetrahedral_ineq. In case you haven't seen it, my posting (with a name correction) is included below. Regards, John Mitchell San Diego, California [copy & HTML formatting of previous post deleted -- djr] ============================================================================== From: Ronald Bruck Subject: Re: Embedding of a metric space Date: Mon, 22 Jan 2001 11:12:30 -0800 Newsgroups: sci.math In article , billsilver223@iol.com (Bill Silver) wrote: :If X is a finite metric space with 3 points then it has isometric :embedding into R^2, but there are metric spaces with 4 points that :do not have isometric embedding into R^n for any n. : :So if X is a finite metric space what condition beside the triangle :inequality the metric should satisfie in order to have isometric :embedding from X to R^n for some n ? :(with the standard euclidean metric on R^n). As I recall from previous postings, put A = matrix of distances d(x_i, x_j). The condition is that exp(tA) be positive-definite for all t > 0. I may be misquoting this, but not by much. There's definitely an exponential in there. --Ron Bruck -- Due to University fiscal constraints, .sigs may not be exceed one line.