Author |
Topic: close-to-regular perfect tetrahedra (Read 1942 times) |
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
close-to-regular perfect tetrahedra
« on: Feb 20th, 2005, 2:45pm » |
Quote Modify
|
--- 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?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: close-to-regular perfect tetrahedra
« Reply #1 on: Feb 22nd, 2005, 12:11am » |
Quote Modify
|
Wow, what a problem!!! 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?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: close-to-regular perfect tetrahedra
« Reply #2 on: Feb 23rd, 2005, 7:56pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: close-to-regular perfect tetrahedra
« Reply #3 on: Feb 26th, 2005, 7:27am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: close-to-regular perfect tetrahedra
« Reply #4 on: Feb 26th, 2005, 3:05pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: close-to-regular perfect tetrahedra
« Reply #5 on: Mar 6th, 2005, 5:22am » |
Quote Modify
|
Do you think I forgot about this problem? No, I did not ! 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. 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. 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).
|
« Last Edit: Mar 10th, 2005, 12:44am by Barukh » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: close-to-regular perfect tetrahedra
« Reply #6 on: Mar 10th, 2005, 4:00am » |
Quote Modify
|
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 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 . 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…
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: close-to-regular perfect tetrahedra
« Reply #7 on: Mar 10th, 2005, 7:37am » |
Quote Modify
|
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.
|
« Last Edit: Mar 10th, 2005, 9:35am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: close-to-regular perfect tetrahedra
« Reply #8 on: Mar 22nd, 2005, 7:35am » |
Quote Modify
|
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 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).
|
« Last Edit: Mar 22nd, 2005, 7:37am by Barukh » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: close-to-regular perfect tetrahedra
« Reply #9 on: Jun 13th, 2005, 2:13pm » |
Quote Modify
|
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...
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
|