# hp41programs

simplex conjecture A Recreative Problem for the HP-41

Overview

1°)  What's the side of this Equilateral Triangle ?
2°)  Generalization to a Simplex
3°)  Demonstration

-I found this problem in a reference  with the answer without a proof
-Then, it was logical to ask a similar question for a tetrahedron and - why not - a simplex
-The generalized formula remains quite simple.

1°)  What's the side of this Equilateral Triangle ?

A
*
*      *                                               ABC  is an equilateral triangle AB = AC = BC = x
*              *
*       * M        *                                        AM = 57  BM =  65  CM = 73       A B C M  are in the same plane
*                            *
*                                   *                                 ->  Calculate x
*                                         *
B    *    *    *    *    *    *    *    *    *   C

-This problem may be solved in several ways:

a) Using the coordinates of the 4 points leads to a 3x3 non-linear system.
b) We can also write that the sum of the areas of the 3 triangles  MAB + MBC + MAC = the area of ABC ( with Heron's formula )
c) Or: the sum of the 3 angles  MAB + MBC + MAC = 360°  ( with the law of cosines )

-But there is a much simpler formula that is given in references  & 

-Let be  a = MA , b = MB , c = MC  we have  3 ( a4 + b4 + c4 + x4 ) = ( a2 + b2 + c2 + x2 )2

Data Registers: /
Flags: /
Subroutines: /

 01  LBL "WST2"  02  X^2  03  ENTER^  04  X^2               05  R^  06  X^2  07  ST+ Z 08  X^2               09  +  10  R^  11  X^2  12  ST+ Z  13  X^2  14  + 15  ST+ X            16  CHS  17  RCL Y  18  ENTER^  19  *  20  +  21  3 22  *  23  SQRT            24  ST+ Z  25  -  26  2  27  ST/ Z  28  / 29  SQRT            30  X<>Y  31  SQRT  32  END

( 47 bytes / SIZE 000 )

 STACK INPUTS OUTPUTS Z a / Y b x' X c x

Example:   With the problem above:

57  ENTER^
65  ENTER^
73  XEQ "WST"   >>>>   x  =  112
RDN   x'  =  16.09347694

-So,  x = 112

Note:

-The 2nd result corresponds to a point outside the triangle

2°)  Generalization to a Simplex

-The 1st generalization concerns a regular tetrahedron ABCD and a point M defined by the distances a = MA , b = MB , c = MC , d = MD
-What is the edge length x of the tetrahedron ?
-This may be solved in the same ways:

a) Using the coordinates of the 5 points leads to a 4x4 non-linear system.
b) We can also write that the sum of the volumes of the 4 tetrahedrons
MABC + MBCD + MACD + MABD = the volume of ABCD ( with Francesca's formula )
c) A 3rd approach is: Sum of the 4 trihedral angles   MABC + MBCD + MACD + MABD = 720°

-But the formula that was used in paragraph 1°) may be generalized to a regular tetrahedron:

4 ( a4 + b4 + c4 + d4 + x4 ) = ( a2 + b2 + c2 + c2 + x2 )2

-I first proved it with my HP-48 using a Cayley-Menger determinant

-Whence the conjecture:     If A1 A2 ... AN is a regular simplex ( edge length = x )   and  MA1 = a1 , MA2 = a2 , ........ , MAN = aN

N ( a14 + ........ + aN4 + x4 ) = ( a12 + ......... + aN2 + x2 )2       here  N = number of points

-A general proof is given in paragraph 3°)

Data Registers:           •  R00 = N = Nb of points                  ( Registers R00 thru RNN are to be initialized before executing "WST" )

•  R01 = a1         •  R02 = a2       .....................         •  RNN = aN
Flags: /
Subroutines: /

 01  LBL "WST"  02  RCL 00          03  0  04  ENTER^  05  LBL 01  06  RCL IND Z  07  X^2 08  ST+ Z  09  X^2  10  +  11  DSE Z  12  GTO 01  13  R^  14  RCL 00 15  -  16  *  17  X<>Y  18  X^2  19  +  20  RCL 00          21  * 22  SQRT  23  ST+ Z  24  -  25  RCL 00          26  1  27  -  28  ST/ Z 29  /  30  SQRT           31  X<>Y  32  SQRT  33  END

( 47 bytes / SIZE NNN+1 )

 STACK INPUTS OUTPUTS Y / x' X / x

Example1:    Regular Tetrahedron with edge length = x ; a = 56 , b = 59 , c = 69 , d = 79  ;  calculate  x

4  STO 00    56  STO 01    59  STO 02    69  STO 03   79  STO 04

XEQ "WST"  >>>>   x = 105
RDN   x' =  26.85144316

Example2:    Regular 4-Simplex with edge length = x   ( N = 5 )

a1 = 138  ,   a2 = 142  ,   a3 = 158  ,   a4 = 160  ,   a5 = 178

5  STO 00    138  STO 01    142  STO 02    158  STO 03    160  STO 04   178  STO 05

XEQ "WST"  >>>>    x = 242
RDN   x' =  46.51881340

Notes:

-Of course, "WST" may also be used to solve the triangle problem, with N = 3
-Here, N is the number of points, not the dimension of the space: for a n-simplex,  N = n+1

-The example 2 was found by Gerson W. Barbosa:
-He wrote a program in turbo pascal3 to find - a lot of - integer solutions of the problem
-If you choose the ai at random, x & x' will probably be not integers !

3°)  Demonstration for a n-simplex

a)  Case n = 3

-This case is just given because the proof is easier to follow.

-Let be ABCD a regular tetrahedron with all edge lengths = 1   and   M(x,y,z)   in the basis  DA = i  , DB = j ,  DC = k

-The dot products  i.i = j.j = k.k = 1  and  i.j = i.k = j.k = cos 60° = 1/2

-We have, for the coordinates of these 4 vectors   DM(x,y,z)  AM(x-1,y,z)  BM(x,y-1,z)  CM(x,y,z-1)  whence:

d2 = (x.i + y.j + z.k)2 =  x2 + y2 + z2 + x y + x z + y z                and likewise

a2 =  (x-1)2 + y2 + z2 + (x-1) y + (x-1) z + y z
b2 =  x2 + (y-1)2 + z2 + x (y-1) + x z + (y-1) z                          which may be re-written:
c2 =  x2 + y2 + (z-1)2 + x y + x (z-1) + y (z-1)

a2 =  d2 - 2 x + 1 - y - z = d2 - x - s + 1
b2 =  d2 - 2 y + 1 - x - z = d2 - y - s + 1                                    with   s = x + y + z
c2 =  d2 - 2 z + 1 - x - y = d2 - z - s + 1

-Adding these 3 relations + d2 + 1  on both sides yields:

a2 + b2 + c2 + d2 + 1 = 4 d2 + 4 - 4 s = 4 ( d2 + 1 - s )   and squaring gives

( a2 + b2 + c2 + d2 + 1 )2 =  16 ( d2 + 1 - s )2 =  16 ( d4 + 1 + s2 + 2 d2 - 2 d2 s - 2 s )

( a2 + b2 + c2 + d2 + 1 )2 =  16 ( d4 + 1 + s2 + 2 d2 - 2 d2 s - 2 s )

-Squaring the same 3 relations above:

a4 = ( d2 - x - s + 1 )2 =  d4 + x2 + s2 + 1 + 2 d2 ( 1 - x - s ) + 2 x s - 2 x - 2 s
b4 = ( d2 - y - s + 1 )2 =  d4 + y2 + s2 + 1 + 2 d2 ( 1 - y - s ) + 2 y s - 2 y - 2 s
c4 = ( d2 - z - s + 1 )2 =  d4 + x2 + s2 + 1 + 2 d2 ( 1 - z - s ) + 2 z s - 2 z - 2 s

-Adding these equalities + d4 + 1  on both sides:

a4 + b4 + c4 + d4 + 1 = 4 d4 + 4 + ( x2 + y2 + z2 ) + 3 s2 + 2 d2 ( 3 - 4 s ) + 2 s ( x + y + z ) - 8 s
a4 + b4 + c4 + d4 + 1 = 4 d4 + 4 + ( x2 + y2 + z2 ) + 3 s2 + 2 d2 ( 3 - 4 s ) + 2 s2 - 8 s

-But  s2 = x2 + y2 + z2 + 2 x y + 2 x z + 2 y z   so,   ( x2 + y2 + z2 ) = 2 d2 - s2   whence:

a4 + b4 + c4 + d4 + 1 = 4 d4 + 4 + 2 d2 - s2  + 3 s2 + 2 d2 ( 3 - 4 s ) + 2 s2 - 8 s
= 4 d4 + 4 + 2 d2 + 4 s2 + 2 d2 ( 3 - 4 s ) - 8 s
= 4 d4 + 4 + 8 d2 + 4 s2 - 8 d2 s  - 8 s
= 4 ( d4 + 1 + 2 d2 + s2 - 2 d2 s  - 2 s )

-Finally,   4 ( a4 + b4 + c4 + d4 + 1 ) = 16 ( d4 + 1 + 2 d2 + s2 - 2 d2 s  - 2 s )            and

( a2 + b2 + c2 + d2 + 1 )2 =  4 ( a4 + b4 + c4 + d4 + 1 )

b)  General Case

* An
L   *        .....
*                ....
A0*   *    *    *   *A2
*
*A1

-Without loss of generality, we can suppose that the edge lengths of the regular tetrahedron   A0A1 ................ An  equal 1 ;    L=1
( In other words, divide the equality by  L4 )

-We choose the basis as  ( e1 , ............. , en ) =  ( A0A1 , ............... , A0An )
-The norms of these n vectors = 1 , but the dot product  ei. ej = cos ( A0Ai , A0Aj ) = cos 60° = 1/2  if  i # j
-Let a point M ( x1 , .............. , xn )  and

a0 = A0M , a1 = A1M , ...................... , an = AnM    we have:

a02 =  Sum xi2 + Sumi<j  xi xj
a12 =  ( x1 - 1 )2 + Sumi#1 xi2 +  ( x1 - 1 ) ( x2 + ....  + xn )  + Sum1<i<j  xi xj

...................................................................................................................

an2 =  Sumi#n xi2 +  ( xn - 1 )2 + Sumi<j<n  xi xj +  ( x1 + ....  + xn-1 ) ( xn - 1 )

-In other words:

a12 =  a02 - 2 x1 - x2 - .................... - xn + 1 =  a02 -  x1 - s + 1        (1)
a22 =  a02 -  x1 - 2 x2 - .................... - xn + 1 =  a02 -  x2 - s + 1       (2)

.................................................................................................                             with  s = x1 + ....  + xn

an2 =  a02 - x1  ................. - xn-1 - 2 xn + 1 =  a02 -  xn - s + 1          (n)

•   Adding these n equalities and adding  a02 + 1  on both sides yields:

a02 + a12 + .....  + an2 + 1 =   ( n + 1 ) a02 + ( n + 1 ) - ( n + 1 ) s

-Dividing by ( n + 1 )  gives  [ a02 + a12 + .....  + an2 + 1 ] / ( n + 1 ) =  a02 + 1 - s   and   squaring this equality produces:

{ [ a02 + a12 + .....  + an2 + 1 ] / ( n + 1 ) }2  = ( a02 + 1 - s )2 =  a04 + 2 a02 - 2 s a02 + 1 - 2 s + s2

•  Squaring the same n equalities (1) (2) ..... (n)  yields:

a14 = ( a02 -  x1 - s + 1 )2  = a04 + x12 + s2 + 1 + 2 a02 ( 1 - s - x1 ) + 2 s x1 - 2 x1 - 2 s
a24 = ( a02 -  x2 - s + 1 )2  = a04 + x22 + s2 + 1 + 2 a02 ( 1 - s - x2 ) + 2 s x2 - 2 x2 - 2 s

.....................................................................................................................................

an4 = ( a02 -  xn - s + 1 )2  = a04 + xn2 + s2 + 1 + 2 a02 ( 1 - s - xn ) + 2 s xn - 2 xn - 2 s

•   Adding these n equalities and adding  a04 + 1  on both sides yields:

a04 + a14 + .....  + an4 + 1 = ( n + 1 ) a04 + ( x12 + ........... + xn2 ) + n  s2 + ( n + 1 ) + 2 a02 n - 2 a02 ( n + 1 ) s  + 2 s2 - 2 ( n + 1 ) s

but   x12 + ........... + xn2  =  2 a02 - s2

so,   a04 + a14 + .....  + an4 + 1 = ( n + 1 ) a04 + 2 a02 - s2 + n  s2 + ( n + 1 ) + 2 a02 n - 2 a02 ( n + 1 ) s  + 2 s2 - 2 ( n + 1 ) s
= ( n + 1 ) a04 + 2 a02 ( 1 + n ) - 2 a02 ( n + 1 ) s + ( n + 1 ) s2 - 2 ( n + 1 ) s + ( n + 1 )

-Dividing by ( n + 1 )  gives

[ a04 + a14 + .....  + an4 + 1 ] / ( n + 1 ) = a04 + 2 a02 - 2 s a02 + 1 - 2 s + s2

-So,  [ a04 + a14 + .....  + an4 + 1 ] / ( n + 1 ) = { [ a02 + a12 + .....  + an2 + 1 ] / ( n + 1 ) }2

-Multiplying on both sides by ( n + 1 )2  proves the formula.                         Q.E.D.

Converse proposition

-Assuming that the relation  ( n + 1 ) ( a04 + a14 + .....  + an4 + x4 ) = ( a02 + a12 + .....  + an2 + x2 )2  is satisfied
and that it does define a point, we have to check that this point M is not outside the n-dimensional space of the n-simplex

-Let be H the orthogonal projection of M on the n-dimensional space of the simplex and  let be h = HM, we have:

( n + 1 ) ( a04 + a14 + .....  + an4 + x4 ) = ( a02 + a12 + .....  + an2 + x2 )2    whence

( n + 1 ) [ ( a'02+h2 )2 + ( a'12+h2 )2 + .....  + ( a'n2+h2 )2 + x4 ] = ( a'02+h2 + a'12+h2  + .....  + a'n2+h2  + x2 )2    ( Pythagoras )

where  a'0 = A0H , a'1 = A1H , .......... , a'n = AnH

-Expanding this equality yields:

( n+1) [ a'04 + a'14 + .....  + a'n4 + x4 + ( n+1 ) h4 + 2 h2 ( a'02 + a'12 + .....  + a'n2 ) ] = [ a'02 + a'12  + .....  + a'n2+ ( n+1 ) h2  + x2 ]2

( n+1) [ a'04 + a'14 + .....  + a'n4 + x4 + ( n+1 ) h4 + 2 h2 ( a'02 + a'12 + .....  + a'n2 ) ]
= [ a'02 + a'12  + .....  + a'n2 + x2 ]2 + 2 ( n + 1 ) h2 ( a'02 + a'12  + .....  + a'n2 + x2 )

-Since H belong to the n-dimensional space of the simplex, we can apply the 1st part of the demonstration to H

-So, ( n+1) [ a'04 + a'14 + .....  + a'n4 + x4 ]  = [ a'02 + a'12  + .....  + a'n2 + x2 ]2

and the remaining equation is the form   C  h4 + D h2 = 0  which has a unique solution:  h = 0

-In other words,  H = M  and  M belong to the n-dimensional space of the simplex.    Q.E.D.

References:

  "The King of Nought" - Diffusion Belin - ISBN 2-909737-06-3 ( in French and English )
  http://mathafou.free.fr/pbg/sol113.html