wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> close-to-regular perfect tetrahedra
        
(Message started by: JocK on Feb 20th, 2005, 2:45pm)
Title: close-to-regular perfect tetrahedra
Post by JocK on Feb 20th, 2005, 2:45pm
--- An 'open' problem ---

A perfect tetrahedron, is a tetrahedron whose sides, face areas, and volume are all integer numbers. There are infinitely many of such tetrahedra.

I am interested in perfect tetrahedra that are close to regular.

We define the closeness to regular as maximising R/r, the radius of the circumsphere divided by the radius of the insphere, such that the R/r value of a regular tetrahedron is approached.

Can you generate perfect polyhedra with R/r as large as possible? How close can you get to the theoretical limit?
Title: Re: close-to-regular perfect tetrahedra
Post by Barukh on Feb 22nd, 2005, 12:11am
Wow, what a problem!!!  ;D

It seems that even the calculation of the "regularity characteristics" R/r may be a problem in itself. So:

Does anybody know a good way to calculate the radii R, r given six lengths of tetrahedron edges?
Title: Re: close-to-regular perfect tetrahedra
Post by Icarus on Feb 23rd, 2005, 7:56pm
A partial answer to Barukh's question:

If the 4 planes of the tetrahedron are given by ni.x = di,  i = 1 .. 4, where the vectors ni are unit vectors pointing towards the center of the tetrahedron, and if c is the incenter and r is the inradius, and pi are the projections of c onto the 4 planes, then we have the two sets of equations:
ni . pi = di
r ni + pi = c


Solving the second set for pi and substituting into the first yields
ni . c - r = di,

a system of 4 equations in 4 unknowns.
Define N to be the 4x4 matrix

[  n11   n12   n13   -1  ]
[  n21   n22   n23   -1  ]
[  n31   n32   n33   -1  ]
[  n41   n42   n43   -1  ]

Let D = (d1, d2, d3, d4) and C = (c1, c2, c3, r), both considered as column vectors. Then N C = D, or C = N-1D.

Of course, this still leaves the tough part of finding the nij and di appropriate for a particular set of edge lengths. Since we can always put one vertex at the origin, we can take all but one of the di to be 0, also, one of the faces can be taken as the xy plane, so the corresponding ni = (0, 0, 1). By further assuming that one of the edges is along x axis, so for a second plane i, we have ni1 = 0. At this point though, the freedom of positioning the coordinate system with respect to the tetrahedron is exhausted, except for possible sign changes.
Title: Re: close-to-regular perfect tetrahedra
Post by Barukh on Feb 26th, 2005, 7:27am
The following is a compilation from different sources. The proofs are not supplied.

Let a, b, c, d, e, f be the lengths of the tetrahedron edges. The pairs of opposite edges (i.e. edges with no common point) are (a, d), (b, e), (c, f). Then, the four triangular faces are (abc), (aef), (bdf), (cde). I also denote S the surface area and V the volume of the tetrahedron.

1. The in-sphere radius is simple, once we know the V and S:

r = 3V/S.

2. The circum-sphere radius is more difficult. I’ve found the following formula:

R2 = s(s-ad)(s-be)(s-cf) / (36V2),
where s = (ad+be+cf)/2.

3. S is computed easily using Heron’s formula for every face.

4. There are several ways to compute V. Here’s one formula due to Euler that is relatively easy to use:

36V2 = det(M),
where M is 3x3 symmetric matrix with

M11  = a2,   M22  = b2,   M33  = c2,
M12  = (a2+ b2-f2)/2,
M13  = (a2+ c2-e2)/2,
M23  = (b2+ c2-d2)/2.


With this at hand, we can return to the original question. The theoretical minimum of the ratio R/r is 3 and corresponds to a regular tetrahedron (one of the 5 platonic solids).

Using some of the published regular tetrahedra, I’ve found a pair with ratios 3.0526… and 3.0828… Elaborations will follow in the next post.
Title: Re: close-to-regular perfect tetrahedra
Post by Icarus on Feb 26th, 2005, 3:05pm
Good. I was unable to find these formulas and trying to figure them out myself. But it was so messy, I didn't get very far.
Title: Re: close-to-regular perfect tetrahedra
Post by Barukh on Mar 6th, 2005, 5:22am
Do you think I forgot about this problem? No, I did not ;D! I just wanted to collect more data and make more analysis. But now I believe it’s time to share what I’ve done.

RESULTS

The best results that I obtained so far are given in the following table:

   Edges                        Volume                   R/r       Published?
----------------------------------------------------------------------------------
1   42285769 45904320 42285769
   42285769 41406638 42285769   9141246007321716288000   3.021     No

2   404633  454784  404633
   404633  391950  404633       8060582065536000         3.045     No

3   2431  2296  2175              
   2431  2296  2175             1403038560               3.053     Yes


ANALYSIS

In my analysis I used of course the known results. Of great help was the nice article by R.H. Buchholz that is available here (http://www.geocities.com/teufel_pi/papers/perfectpyramids.pdf). By the way, I think there is an error in one of author’s results.

1.  It is clear that the regular tetrahedron cannot be perfect (why?)

2. The next case to consider would be the tetrahedron consisting of 4 congruent faces (such tetrahedron is called isosceles) each being an almost equilateral integer triangle (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1108913697). Buchholz proves that such a tetrahedron also cannot be perfect (in fact, he proves a stronger result). I tried to derive it myself, here’s where I get.

WLOG, we may consider a = c = d = f = 2n[pm]1, b = e = 2n for an integer n. In this configuration, the volume of the tetrahedron satisfies the simple formula 36V2 = b4(a2-b2/2) = (2n)4[(2n[pm]1)2 – 2n2]. That is, the tetrahedron will have an integral volume if the second term is a perfect square:

2n2 [pm] 4n + 1 = p2,                              (1)

and from the discussion of the almost equilateral triangles, we know that the following should be satisfied for faces:

3n2 [pm] 4n + 1 = q2.                              (2)

Therefore, the perfect tetrahedron of such configuration exists iff the system of Diophantine equations (1), (2) has a solution in n, p, q. The number of unknowns may be reduced as follows: subtracting (1) from (2), we get  q2 - p2 = n2, that is, p and n should be legs of the Pythagorean triangle, that is n = 2rs, p = r2-s2 for some integers r, s. Plugging this into (1), we obtain:
2(2rs[pm]1)2 – 1 = (r2 - s2)2.

I can’t prove this, but it follows from Buchholz’s paper that this quartic equation has no solutions in positive integers.

To be continued… (I need to go out).
Title: Re: close-to-regular perfect tetrahedra
Post by Barukh on Mar 10th, 2005, 4:00am
Hey, am I the only one interested in this problem?  ???

3. The available sources (one of which is Buchholz’s paper, another is Ivars Peterson’s article (http://www.sciencenews.org/articles/20030802/mathtrek.asp) in Science News) gave only one reasonable example – an isosceles tetrahedron with triangle edges 2431, 2296, 2175 – it has the ratio R/r = 3.0526… (#3 in the above table).

4. There is another example (in Guy’s book “Unsolved Problems in Number Theory”) of perfect tetrahedron with edges (1073, 990, 1073, 1073, 896, 1073) and R/r = 3.082… Note that this tetrahedron is not isosceles; it consists of 2 pairs of congruent isosceles triangles (acb, dfb) and (afe, dce). This type was mentioned in Buchholz’s paper, but not explored. So, I decided to take on from there.

This type has 3 different edge lengths, say a, b, e, and c = d = f = a. I called it abe-tetrahedron. In what follows, only primitive tetrahedrons  (i.e. edges do not have common factors) are considered.

As we already know, for the isosceles triangle to be Heronian, the base must be even and legs odd. So, let b = 2g, and using Heron's formula, we get for the area of the triangle abc:
A(abc)2 = (a+g)g2(a-g),

and this is perfect square iff (a+g)(a-g) = a2 - g2 is. Analogously, for the second pair of triangles, put e = 2h, and get that a2 – h2 must be a perfect square. Therefore, abe-tetrahedron has integer faces if its edges satisfy simultaneously the following equations:
a2 = (b/2)2 + r2 = (e/2)2 + s2                      (3)

for some integers r, s. In other words, a should be representable as a sum of two squares in at least two different ways. (why?)

As for volume, using the formula in my previous posts, one gets 144V2 = (be)2(4a2 - b2 - e2), which is a perfect square when 4a2-b2-e2 is. Combining this with formula (3), we get the following conditions for abe-tetrahedron to have an integer volume:
(b/2)2 + t2 = s2,    (e/2)2 + u2 = r2               (4)

for some integers t, u. In other words, b/2, e/2 should be legs of at least 2 Pythagorean triangles.

From here, there are several approaches to proceed. The best of course would be to get the parametric solution for the system of equations (3), (4), but I didn’t get that far :D. Instead, I generated numbers ‘a’ satisfying (3). Fortunately, there is an efficient algorithm to do that, based on the following result (remember we are looking only at primitive solutions):

An odd number is representable as a sum of two squares if its prime factors are all of the form 4k+1, and if there are n such factors, there are 2n-1 representations.

It follows immediately that the candidates must have at least 2 prime factors of the form 4k+1 (indeed, the example in Guy’s book has a = 1073 as a product of 29 and 37). The whole procedure is as follows:

a)  Generate primes of the form 4k+1.
b)  For every such prime find its representation as a two-squares-sum (how?)
c)  Take n numbers of that form and form 2n-1 two-square-sums of their product (how?). This will give one number ‘a’.
d)  Taking any 2 representations for a generated number, calculate numbers b, e, r, s (using Pythagorean triples) satisfying (3).
e)  Check that these numbers satisfy (4).
f)  If yes, we have a perfect abe-tetrahedron. Calculate its parameters and R/r ratio.

To be continued…
Title: Re: close-to-regular perfect tetrahedra
Post by THUDandBLUNDER on Mar 10th, 2005, 7:37am

Quote:
Hey, am I the only one interested in this problem?

Excellent research, Barukh.
For myself, I am a little too busy these days to spend much time on it.


Quote:
For every such prime find its representation as a two-squares-sum (how?)

There is an O(log2p) algorithm here (http://mcraefamily.com/MathHelp/BasicNumberSquareSums.htm).
Title: Re: close-to-regular perfect tetrahedra
Post by Barukh on Mar 22nd, 2005, 7:35am
4. Update on abe-tetrahedrons. Since my last posting, I was able to find better examples using the algorithm described there. The following table presents the best three.


N  ABE-edges         Volume           R/r         n
------------------------------------------------
1  10524850673      1.3935e+29       3.0046       3
  10429574430
  10949232896

2  690396541        4.0079e+25       3.0080       2
  708428182
  722746440

3  7346712977       4.7398e+28       3.0103       3
  7179271904
  7768190430

Notes:

1. Volume is presented approximately, although computed exactly.
2. ‘n’ is the number of generating primes of the form 4k+1, as described in step c) of the algorithm.

MATTERS COMPUTATIONAL

Because the parametric solution is missing, it is necessary to run exhaustive search… I use two input parameters: the maximal prime number to consider P, and the number of generating primes, n. From the complexity point of view, the first parameter has quadratic dependence, and the second – exponential. The results achieved so far are from the two runs (P, n) = (1000000, 2) and (100000, 3) (the second was not completed).

At such a scale of experiment, the size of machine word is not enough; so I used the long long C-type to represent the edges. To check for the 'perfectness' of the tetrahedron, I used tricks from Check for Perfect Square (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1110540607) thread to avoid overflow and gain speed. Volume and area computation were performed by using the GMP library (multiple precision arithmetic) which is nowadays pretty standard on different Unix/Linux systems. They have a rich C interface and a nice C++ interface, although I am not satisfied with the efficiency (don’t know if it may be improved, though…)

Suggestions for efficiency improvements are welcome...  ;)

For the end: the biggest perfect tetrahedron computed by my program has a volume 1.43265695e+37 and R/r = 3.5665; its smallest edge equals 4898641148041 (~1140 times 232).
Title: Re: close-to-regular perfect tetrahedra
Post by JocK on Jun 13th, 2005, 2:13pm
Well done Barukh, chapeau!

An R/r value only 0.0046 above the theoretical lower bound of 3 is an excellent result.  

Considering Barukh's impressive solo race, I consider it unlikely that anyone will beat this record and get any closer to 3...


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board