Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

GEOMETRY, ALGEBRA, CALCULUS

Up Next

ITEM 1 (Schroeppel):

(1/3)! and (2/3)! are interexpressible.
(1/4)! and (3/4)! are interexpressible.

Thus these two pairs are of dimensionality one.

(1/10)! and (2/10)! are sufficient to express (N/10)! for all N.
(1/12)! and (2/12)! are sufficient to express (N/12)! for all N.
(1/3)! and (1/4)! are sufficient to express (N/12)! for all N.

Thus the three cases above are of dimensionality two.

PROBLEM: Find some order to this dimensionality business.

The reflection and multiplication formulas: 

             pi Z
Z! (-Z)! = ---------
           sin(pi Z)


      (N-1)/2  -NZ-1/2
(2 pi)        N        (NZ)! = Z! (Z-1/N)! (Z-2/N)! ... (Z-(N-1)/N)!

ITEM 2 (Jan Kok):

Problem: Given a regular n-gon with all diagonals drawn, how many regions are there? In particular, how many triple (or N-tuple) concurrences of diagonals are there?

ITEM 3 (Schroeppel):

Regarding convergence of Newton's method for quadratic equations: Draw the perpendicular bisector of the line connecting the two roots. Points on either side converge to the closest root.

On the line:

  1. they do not converge
  2. there is a dense set of points which involve division by zero
  3. there is a dense set of points which loop, but roundoff error propagates so all loops are unstable
  4. being on the line is also unstable
    (if the roots are imaginary and you are on the real axis, you may be doing exact computation of the imaginary part (0), hence stay on the line. Example: X^2 + 1 = 0, X0 = random real floating point number.)

ITEM 4 (Schroeppel):

By Mathlab, the discriminant of 
 4      3      2
X  + F X  + G X  + H X + I  is (as the discriminant of

   2                 2
A X  + B X + C  is  B  - 4 A C):


           4           3      3  3      3  2    2  2  2
     - 27 H  + 18 F G H  - 4 F  H  - 4 G  H  + F  G  H

                   2      2  2         2         3           4      2  3
     + I * [144 G H  - 6 F  H  - 80 F G  H + 18 F  G H + 16 G  - 4 F  G ]

        2                     2        2         4
     + I  * [- 192 F H - 128 G  + 144 F  G - 27 F ]

            3
     - 256 I

ITEM 5:

In general, the discriminant of an n-th degree polynomial is 
 /===\
  ! !                 2
  ! !  (ROOT  - ROOT )   =  square of determinant whose i,j element is
  ! !       i       j
 i < j


    i-1
ROOT    .
    j
(The discriminant is the lowest degree symmetric function of the roots which is 0 when any two are equal.)

ITEM 6 (Schroeppel):

If A is the first symmetric function of N variables 
= X + Y + Z + ...
and B is the second symmetric function of N variables 
= X Y + X Z + ... + Y Z + ...
(B = sum of pairs), then 
 2    2    2          2
X  + Y  + Z  + ... = A  - 2 B.

 3    3    3          3
X  + Y  + Z  + ... = A  - 3 A B + 3 C.

 4    4    4          4      2        2
X  + Y  + Z  + ... = A  - 4 A  B + 2 B  + 4 A C - 4 D.

ITEM 7 (Gosper):

If f(I;X,Y,...) is the Ith symmetric function on N variables, 
               /   0                                if I > N
f(I;X,Y,...) = !   1                                if I = 0
               \   X*f(I-1;Y,Z...) + f(I;Y,Z,...)   (N-1 variables)
The generating function is simply 
        N
       ====
       \                    I
        >    F(I; X, Y, Z) S  = (1 + S X) (1 + S Y) (1 + S Z) ...
       /
       ====
       I=0

ITEM 8 (Schroeppel):

Solutions to 
        3        2
F(X) = X  - 3 B X  + C X + D = 0
are 
             ------------------------------
            /            ------------------
           / F(B)       / F(B) 2    F'(B) 3
B - K *  3/  ----  +   / [----]  + [-----]
         V    2       V    2          3


             ------------------------------
            /            ------------------
    2      / F(B)       / F(B) 2    F'(B) 3
 - K  *  3/  ----  -   / [----]  + [-----]
         V    2       V    2          3
where K is one of the three cuberoots of 1:

1, (-1+sqrt(-3))/2, (-1-sqrt(-3))/2.

ITEM 9 (Schroeppel & Salamin):

If 
 4      2    
X  + B X  + C X + D = 0,
then 2 X = sqrt(Z1) + sqrt(Z2) + sqrt(Z3), where Z1, Z2, Z3 are roots of 
 3        2     2             2
Z  + 2 B Z  + (B  - 4 D) Z - C  = 0.
The choices of square roots must satisfy

sqrt(Z1) sqrt(Z2) sqrt(Z3) = -C.

ITEM 10 (Salamin):

An easy solution of 
    3
-4 X  + 3 X - a = 0
is X = sin((arcsin a)/3).

In a similar manner, the general quintic can be solved exactly by use of the elliptic modular function and its inverse. See Davis: Intro. to Nonlinear Differential and Integral Equations (Dover), p. 172. Unfortunately, there exists >= 1 typo, since his eqs. (7) and (13) are inconsistent.

ITEM 11 (Salamin):

The following operations generate one-to-one conformal mappings of Euclidean N-space onto itself.
  1. Translate N-space.
  2. Expand N-space about one of its points.
  3. Stereographically project N-space onto an N-sphere, rotate the sphere, then project back onto N-space.
PROBLEMS:

Show that all such conformal maps are generated by these operations for any N. If the one-to-one and onto conditions are removed, then for N = 2, conformal maps can be obtained by analytic functions. Show that for N > 2, no new conformal maps exist.

Up Next