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
http://www.math.niu.edu/~rusin/known-math/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
>http://www.math.niu.edu/~rusin/known-math/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
http://www.math.niu.edu/~rusin/known-math/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 http://www.math.niu.edu/~rusin/known-math/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.