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 [1] 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 [1] & [2]

-Let be  a = MA , b = MB , c = MC  we have  3 ( a4 + b4 + c4 + x4 ) = ( a2 + b2 + c2 + x2 )2
-This leads to a quadratic equation that is solved by "WST"
 

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.
-Skip to the next paragraph otherwise.
 

-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:

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