Subject: sci.math: Frequently Asked Questions
From: [email-masked] (Alex Lopez-Ortiz)
Date: Thu, 21 Jan 1993 14:05:10 GMT
Newsgroups: sci.math,news.answers

Archive-Name: sci-math-faq
Version: $Id: sci-math-faq,v 3.8 92/12/26 18:45:00 $

This is a list of Frequently Asked Questions for sci.math (version 3.8).
Any contributions/suggestions/corrections are most welcome. Please use
* e-mail * on any comment concerning the FAQ list.

Changes and additions are marked with a # on the table of contents.
This FAQ list (and most others, for that matter) is available via anonymous
ftp at rtfm.mit.edu (18.172.1.27).

The list of contributors to this FAQ list is too large to include here;
but thanks are due to all of them (you know who you are folks).

             Table of Contents
             -----------------

 1Q.- Fermat's Last Theorem, status of .. #
 2Q.- Four Colour Theorem, proof of ..
 3Q.- Values of Record Numbers      
 4Q.- General Netiquette
 5Q.- Computer Algebra Systems, application of ..
 6Q.- Computer Algebra Systems, references to ..
 7Q.- Fields Medal, general info ..
 8Q.- 0^0=1. A comprehensive approach 
 9Q.- 0.999... = 1. Properties of the real numbers ..
10Q.- Digits of Pi, computation and references 
11Q.- There are three doors, The Monty Hall problem, Master Mind and
      other games .. #
12Q.- Surface and Volume of the n-ball  
13Q.- f(x)^f(x)=x, name of the function ..
14Q.- Projective plane of order 10 ..   
15Q.- How to compute day of week of a given date 
16Q.- Axiom of Choice and/or Continuum Hypothesis? 
17Q.- Cutting a sphere into pieces of larger volume  
18Q.- Pointers to Quaternions
19Q.- Erdos Number # 
20Q.- Odd Perfect Number #
21Q.- Why is there no Nobel in mathematics? #
22Q.- General References and textbooks... #

1Q:  What is the current status of Fermat's last theorem?
    (There are no positive integers x,y,z, and n > 2 such that 
    x^n + y^n = z^n)  
    I heard that <insert name here> claimed to have proved it but later
    on the proof was found to be wrong. ...
    (wlog we assume x,y,z to be relatively prime)

A:  The status of FLT has remained remarkably constant.  Every few
    years, someone claims to have a proof ... but oh, wait, not quite.
    Meanwhile, it is proved true for ever greater values of the exponent
    (but not all of them), and ties are shown between it and other
    conjectures (if only we could prove one of them), and ... so it has
    been for quite some time.  It has been proved that for each 
    exponent, there are at most a finite number of counter-examples to
    FLT.

    Here is a brief survey of the status of FLT. It is not intended to
    be 'deep', but it is rather for non-specialists.

    The theorem is broken into 2 cases. The first case assumes 
    (abc,n) = 1. The second case is the general case.

    What has been PROVED
    --------------------

    First Case.

    It has been proven true up to 7.568x10^17 by the work of Wagstaff &
    Tanner, Granville&Monagan, and Coppersmith. They all used extensions
    of the Wiefrich criteria and improved upon work performed by 
    Gunderson and Shanks&Williams.
 
    The first case has been proven to be true for an infinite number of 
    exponents by Adelman, Frey, et. al. using a generalization of the
    Sophie Germain criterion

    Second Case:

    It has been proven true up to n = 150,000 by Tanner & Wagstaff. The
    work used new techniques for computing Bernoulli numbers mod p and 
    improved upon work of Vandiver. The work involved computing the
    irregular primes up to 150,000. FLT is true for all regular primes 
    by a theorem of Kummer. In the case of irregular primes, some
    additional computations are needed.
 
    UPDATE : 

    Fermat's Last Theorem has been proved true up to exponent 4,000,000
    in the general case. The method used was essentially that of Wagstaff:
    enumerating and eliminating irregular primes by Bernoulli number
    computations. The computations were performed on a set of NeXT
    computers by Richard Crandall et al.

    Since the genus of the curve a^n + b^n = 1, is greater than or equal
    to 2 for n > 3, it follows from Mordell's theorem [proved by
    Faltings], that for any given n, there are at most a finite number
    of solutions.

    Conjectures
    -----------

    There are many open conjectures that imply FLT. These conjectures
    come from different directions, but can be basically broken into
    several classes: (and there are interrelationships between the 
    classes)
    
    (a) conjectures arising from Diophantine approximation theory such 
    as the ABC conjecture, the Szpiro conjecture, the Hall conjecture,
    etc.

    For an excellent survey article on these subjects see the article
    by Serge Lang in the Bulletin of the AMS, July 1990 entitled
    "Old and new conjectured diophantine inequalities".

    Masser and Osterle formulated the following known as the ABC 
    conjecture:

    Given epsilon > 0, there exists a number C(epsilon) such that for
    any set of non-zero, relatively prime integers a,b,c such that 
    a+b = c we have

    max( |a|, |b|, |c|) <= C(epsilon) N(abc)^(1 + epsilon)

    where N(x) is the product of the distinct primes dividing x.

    It is easy to see that it implies FLT asymptotically. The conjecture
    was motivated by a theorem, due to Mason that essentially says the
    ABC conjecture IS true for polynomials.

    The ABC conjecture also implies Szpiro's conjecture [and vice-versa]
    and Hall's conjecture. These results are all generally believed to
    be true. 

    There is a generalization of the ABC conjecture [by Vojta] which is
    too technical to discuss but involves heights of points on
    non-singular algebraic varieties . Vojta's conjecture also implies
    Mordell's theorem [already known to be true]. There are also a
    number of inter-twined conjectures involving heights on elliptic
    curves that are related to much of this stuff. For a more complete 
    discussion, see Lang's article.
    
    (b) conjectures arising from the study of elliptic curves and
    modular forms. -- The Taniyama-Weil-Shmimura conjecture.
 
    There is a very important and well known conjecture known as the
    Taniyama-Weil-Shimura conjecture that concerns elliptic curves.
    This conjecture has been shown by the work of Frey, Serre, Ribet,
    et. al. to imply FLT uniformly, not just asymptotically as with the
    ABC conj.
    
    The conjecture basically states that all elliptic curves can be
    parameterized in terms of modular forms. 

    There is new work on the arithmetic of elliptic curves. Sha, the
    Tate-Shafarevich group on elliptic curves of rank 0 or 1. By the way
    an interesting aspect of this work is that there is a close 
    connection between Sha, and some of the classical work on FLT. For
    example, there is a classical proof that uses infinite descent to
    prove FLT for n = 4. It can be shown that there is an elliptic curve
    associated with FLT and that for n=4, Sha is trivial. It can also be
    shown that in the cases where Sha is non-trivial, that 
    infinite-descent arguments do not work; that in some sense 'Sha
    blocks the descent'. Somewhat more technically, Sha is an
    obstruction to the local-global principle [e.g. the Hasse-Minkowski
    theorem].

    (c) Conjectures arising from some conjectured inequalities involving
    Chern classes and some other deep results/conjectures in arithmetic
    algebraic geometry. 

    I can't describe these results since I don't know the math. Contact
    Barry Mazur [or Serre, or Faltings, or Ribet, or ...]. Actually the
    set of people who DO understand this stuff is fairly small.

    The diophantine and elliptic curve conjectures all involve deep 
    properties of integers. Until these conjecture were tied to FLT,
    FLT had been regarded by most mathematicians as an isolated problem;
    a curiosity. Now it can be seen that it follows from some deep and
    fundamental properties of the integers. [not yet proven but
    generally believed].

    This synopsis is quite brief. A full survey would run to many pages.

    References:

    [1] J.P.Butler, R.E.Crandall, & R.W.Sompolski
    "Irregular Primes to One Million"
     Math. Comp. 59 (October 1992) pp. 717-722

    H.M. Edwards, Fermat's Last Theorem, A Genetic Introduction to
    Algebraic Number Theory, Springer Verlag, New York, 1977

    P. Ribenboim, Thirteen Lectures on Fermat's Last Theorem, 
    Springer Verlag, New York, 1979

    Number Theory Related to Fermat's Last Theorem, Neal Koblitz, editor,
    Birkh\"auser Boston, Inc., 1982, ISBN 3-7643-3104-6

2Q: Has the Four Colour Theorem been solved?
    (Every planar map with regions of simple borders can be coloured 
    with 4 colours in such a way that no two regions sharing a non-zero
    length border have the same colour.)

A:  This theorem was proved with the aid of a computer in 1976.
    The proof shows that if aprox. 1,936  basic forms of maps
    can be coloured with four colours, then any given map can be
    coloured with four colours. A computer program coloured this 
    basic forms. So far nobody has been able to prove it without 
    using a computer. In principle it is possible to emulate the 
    computer proof by hand computations.

    References:

    K. Appel and W. Haken, Every planar map is four colourable,
    Bulletin of the American Mathematical Society, vol. 82, 1976 
    pp.711-712.

    K. Appel and W. Haken, Every planar map is four colourable,
    Illinois Journal of Mathematics, vol. 21, 1977, pp. 429-567.

    T. Saaty and Paul Kainen, The Four Colour Theorem: Assault and
    Conquest, McGraw-Hill, 1977. Reprinted by Dover Publications 1986. 

    K. Appel and W. Haken, Every Planar Map is Four Colorable,
    Contemporary Mathematics, vol. 98, American Mathematical Society,
    1989, pp.741.

    F. Bernhart, Math Reviews. 91m:05007, Dec. 1991. (Review of Appel
    and Haken's book).

3Q:  What are the values of:

largest known Mersenne prime?

A:  It is 2^756839-1. It was discovered by a Cray-2 in England in 1992.
    It has 227,832 digits.

largest known prime?

A:  The largest known prime is the Mersenne prime described above.
    The previous record holder, and the largest known non-Mersenne prime,
    is 391581*2^216193-1. See Brown, Noll, Parady, Smith, Smith, and
    Zarantonello, Letter to the editor, American Mathematical Monthly,
    vol. 97, 1990, p. 214. Throughout history, the largest known prime
    has almost always been a Mersenne prime; the period between Brown
    et al's discovery in Aug 1989 and Slowinski & Gage's in March 1992
    is one of the few exceptions.

largest known twin primes?
	
A:  The largest known twin primes are 1706595*2^11235 +- 1.
    See B. K. Parady and J. F. Smith and S. E. Zarantonello,
    Smith, Noll and Brown.
    Largest known twin primes, Mathematics of Computation,
    vol.55, 1990, pp. 381-382. 

largest Fermat number with known factorization?

A:  F_11 = (2^(2^11)) + 1 which was  factored by Brent & Morain in
    1988. F9 = (2^(2^9)) + 1 = 2^512 + 1 was factored by 
    A.K. Lenstra, H.W. Lenstra Jr., M.S. Manasse & J.M. Pollard
    in 1990. The factorization for F10 is NOT known.

Are there good algorithms to factor a given integer?

A:  There are several that have subexponential estimated 
    running time, to mention just a few:

        Continued fraction algorithm,
        Class group method,
        Quadratic sieve algorithm,
        Elliptic curve algorithm,
        Number field sieve,
        Dixon's random squares algorithm,
        Valle's two-thirds algorithm,
        Seysen's class group algorithm,

    A.K. Lenstra, H.W. Lenstra Jr., "Algorithms in Number Theory",
    in: J. van Leeuwen (ed.), Handbook of Theoretical Computer 
    Science, Volume A: Algorithms and Complexity, Elsevier, pp. 
    673-715, 1990.

List of record numbers?

A:  Chris Caldwell maintains "THE LARGEST KNOWN PRIMES (ALL KNOWN
    PRIMES WITH 2000 OR MORE DIGITS)"-list. Send him mail to  
    [email-masked] (preferred) or [email-masked], on any new 
    gigantic primes (greater than 10,000 digits), titanic primes
    (greater than 1000 digits).

What is the current status on Mersenne primes?

A:  Mersenne primes are primes of the form 2^p-1. For 2^p-1 to be prime 
    we must have that p is prime. The following Mersenne primes are
    known.

    nr            p                                 year  by
    -----------------------------------------------------------------
     1-5   2,3,5,7,13                    in or before the middle ages
     6-7       17,19                     1588  Cataldi
     8          31                       1750  Euler
     9          61                       1883  Pervouchine
    10          89                       1911  Powers
    11          107                      1914  Powers
    12          127                      1876  Lucas
    13-14       521,607                  1952  Robinson
    15-17       1279,2203,2281           1952  Lehmer
    18          3217                     1957  Riesel
    19-20       4253,4423                1961  Hurwitz & Selfridge
    21-23       9689,9941,11213          1963  Gillies
    24          19937                    1971  Tuckerman
    25          21701                    1978  Noll & Nickel
    26          23209                    1979  Noll
    27          44497                    1979  Slowinski & Nelson
    28          86243                    1982  Slowinski
    29          110503                   1988  Colquitt & Welsh jr.
    30          132049                   1983  Slowinski
    31          216091                   1985  Slowinski
    32?         756839                   1992  Slowinski & Gage

    The way to determine if 2^p-1 is prime is to use the Lucas-Lehmer 
    test:
      Lucas_Lehmer_Test(p):
         u := 4
         for i from 3 to p do
            u := u^2-2 mod 2^p-1
         od
         if u == 0 then
            2^p-1 is prime
         else
            2^p-1 is composite
         fi

   The following ranges have been checked completely:
    2 - 355K and  430K - 520K

   More on Mersenne primes and the Lucas-Lehmer test can be found in:
      G.H. Hardy, E.M. Wright, An introduction to the theory of numbers,
      fifth edition, 1979, pp. 16, 223-225.

(Please send updates to [email-masked])

4Q:  I think I proved <insert big conjecture>.    OR
    I think I have a bright new idea.

    What should I do?

A:  Are you an expert in the area? If not, please ask first local
    gurus for pointers to related work (the "distribution" field
    may serve well for this purposes). If after reading them you still
    think your *proof is correct*/*idea is new* then send it to the net.

5Q:  I have this complicated symbolic problem (most likely
    a symbolic integral or a DE system) that I can't solve.
    What should I do?

A:  Find a friend with access to a computer algebra system
    like MAPLE, MACSYMA or MATHEMATICA and ask her/him to solve it.
    If packages cannot solve it, then (and only then) ask the net. 

6Q:  Where can I get <Symbolic Computation Package>?
    This is not a comprehensive list. There are other Computer Algebra
    packages available that may better suit your needs. There is also
    a FAQ list in the group sci.math.symbolics. It includes a much larger
    list of vendors and developers. (The FAQ list can be obtained from
    rtfm.mit.edu via anonymous ftp).

A: Maple 
        Purpose: Symbolic and numeric computation, mathematical
        programming, and mathematical visualization. 
        Contact: Waterloo Maple Software,
        160 Columbia Street West,
        Waterloo, Ontario, Canada     N2L 3L3
        Phone: (519) 747-2373 
        [email-masked] [email-masked]

A: DOE-Macsyma  
        Purpose: Symbolic and mathematical manipulations.
        Contact: National Energy Software Center
        Argonne National Laboratory 9700 South Cass Avenue
        Argonne, Illinois 60439 
        Phone: (708) 972-7250

A: Pari    
        Purpose: Number-theoretic computations and simple numerical
        analysis.
        Available for Sun 3, Sun 4, generic 32-bit Unix, and
        Macintosh II. This is a free package, available by ftp from
        math.ucla.edu (128.97.64.16).
        Contact: questions about pari can be sent to [email-masked]

A: Mathematica
        Purpose: Mathematical computation and visualization,
        symbolic programming. 
        Contact: Wolfram Research, Inc. 
        100 Trade Center Drive Champaign,
        IL 61820-7237
        Phone: 1-800-441-MATH

A: Macsyma
        Purpose: Symbolic and mathematical manipulations.
	Contact: Symbolics, Inc.
	8 New England Executive Park East
	Burlington, Massachusetts 01803
	United States of America
	(617) 221-1250
	[email-masked]

A: Matlab
        Purpose: `matrix laboratory' for tasks involving 
	matrices, graphics and general numerical computation.
	Contact: The MathWorks, Inc.
     	21 Eliot Street
     	South Natick, MA 01760
     	508-653-1415
     	[email-masked]

A: Cayley
        Purpose: Computation in algebraic and combinatorial structures
        such as groups, rings, fields, modules and graphs.
        Available for: SUN 3, SUN 4, IBM running AIX or VM, DEC VMS, others
        Contact: Computational Algebra Group
        University of Sydney
        NSW 2006
        Australia
        Phone:  (61) (02) 692 3338
        Fax: (61) (02) 692 4534
        [email-masked]

7Q:  Let P be a property about the Fields Medal. Is P(x) true?

A:  There are a few gaps in the list. If you know any of the
    missing information (or if you notice any mistakes), 
    please send me e-mail.

Year Name               Birthplace              Age Institution
---- ----               ----------              --- -----------
1936 Ahlfors, Lars      Helsinki       Finland   29 Harvard U         USA
1936 Douglas, Jesse     New York NY    USA       39 MIT               USA
1950 Schwartz, Laurent  Paris          France    35 U of Nancy        France
1950 Selberg, Atle      Langesund      Norway    33 Adv.Std.Princeton USA 
1954 Kodaira, Kunihiko  Tokyo          Japan     39 Princeton U       USA
1954 Serre, Jean-Pierre Bages          France    27 College de France France
1958 Roth, Klaus        Breslau        Germany   32 U of London       UK
1958 Thom, Rene         Montbeliard    France    35 U of Strasbourg   France
1962 Hormander, Lars    Mjallby        Sweden    31 U of Stockholm    Sweden
1962 Milnor, John       Orange NJ      USA       31 Princeton U       USA
1966 Atiyah, Michael    London         UK        37 Oxford U          UK
1966 Cohen, Paul        Long Branch NJ USA       32 Stanford U        USA
1966 Grothendieck, Alexander Berlin    Germany   38 U of Paris        France
1966 Smale, Stephen     Flint MI       USA       36 UC Berkeley       USA
1970 Baker, Alan        London         UK        31 Cambridge U       UK
1970 Hironaka, Heisuke  Yamaguchi-ken  Japan     39 Harvard U         USA
1970 Novikov, Serge     Gorki          USSR      32 Moscow U          USSR
1970 Thompson, John     Ottawa KA      USA       37 U of Chicago      USA
1974 Bombieri, Enrico   Milan          Italy     33 U of Pisa         Italy
1974 Mumford, David     Worth, Sussex  UK        37 Harvard U         USA
1978 Deligne, Pierre    Brussels       Belgium   33 IHES              France
1978 Fefferman, Charles Washington DC  USA       29 Princeton U       USA
1978 Margulis, Gregori  Moscow         USSR      32 InstPrblmInfTrans USSR
1978 Quillen, Daniel    Orange NJ      USA       38 MIT               USA
1982 Connes, Alain      Draguignan     France    35 IHES              France
1982 Thurston, William  Washington DC  USA       35 Princeton U       USA
1982 Yau, Shing-Tung    Kwuntung       China     33 IAS               USA
1986 Donaldson, Simon   Cambridge      UK        27 Oxford U          UK
1986 Faltings, Gerd     1954           Germany   32 Princeton U       USA
1986 Freedman, Michael  Los Angeles CA USA       35 UC San Diego      USA
1990 Drinfeld, Vladimir Kharkov        USSR      36 Phys.Inst.Kharkov USSR
1990 Jones, Vaughan     Gisbourne      N Zealand 38 UC Berkeley       USA
1990 Mori, Shigefumi    Nagoya         Japan     39 U of Kyoto?       Japan
1990 Witten, Edward     Baltimore      USA       38 Princeton U/IAS   USA

References :

International Mathematical Congresses, An Illustrated History 1893-1986,
Revised Edition, Including 1986, by Donald J.Alberts, G. L. Alexanderson 
and Constance Reid, Springer Verlag, 1987.

Tropp, Henry S., ``The origins and history of the Fields Medal,''
Historia Mathematica, 3(1976), 167-181.  

8Q:  What is 0^0 ?

A:  According to some Calculus textbooks, 0^0 is an "indeterminate
    form". When evaluating a limit of the form 0^0, then you need
    to know that limits of that form are called "indeterminate forms",
    and that you need to use a special technique such as L'Hopital's
    rule to evaluate them. Otherwise, 0^0=1 seems to be the most
    useful choice for 0^0. This convention allows us to extend 
    definitions in different areas of mathematics that otherwise would
    require treating 0 as a special case. Notice that 0^0 is a
    discontinuity of the function x^y. 
   
    Rotando & Korn show that if f and g are real functions that vanish
    at the origin and are _analytic_ at 0 (infinitely differentiable is
    not sufficient), then f(x)^g(x) approaches 1 as x approaches 0 from
    the right.

    From Concrete Mathematics p.162 (R. Graham, D. Knuth, O. Patashnik):

    "Some textbooks leave the quantity 0^0 undefined, because the
    functions x^0 and 0^x have different limiting values when x 
    decreases to 0. But this is a mistake. We must define

       x^0 = 1 for all x,

    if the binomial theorem is to be valid when x=0, y=0, and/or x=-y.
    The theorem is too important to be arbitrarily restricted! By
    contrast, the function 0^x is quite unimportant." 

    Published by Addison-Wesley, 2nd printing Dec, 1988.

    References:
 
    H. E. Vaughan, The expression '0^0', Mathematics Teacher 63 (1970),
    pp.111-112.

    Louis M. Rotando & Henry Korn, "The Indeterminate Form 0^0",
    Mathematics Magazine, Vol. 50, No. 1 (January 1977), pp. 41-42.

    L. J. Paige, A note on indeterminate forms, American Mathematical 
    Monthly, 61 (1954), 189-190; reprinted in the Mathematical 
    Association of America's 1969 volume, Selected Papers on Calculus,
    pp. 210-211.

9Q:  Why is 0.9999... = 1?

A:  In modern mathematics, the string of symbols "0.9999..." is
    understood to be a shorthand for "the infinite sum  9/10 + 9/100
    + 9/1000 + ...." This in turn is shorthand for "the limit of the
    sequence of real numbers 9/10, 9/10 + 9/100, 9/10 + 9/100 + 9/1000,
    ..."  Using the well-known epsilon-delta definition of limit, one
    can easily show that this limit is 1.  The statement that 
    0.9999...  = 1 is simply an abbreviation of this fact.

                    oo              m
                   ---   9         ---   9
        0.999... = >   ---- = lim  >   ----
                   --- 10^n  m->oo --- 10^n
                   n=1             n=1
        Choose epsilon > 0. Suppose delta = 1/-log_10 epsilon, thus
        epsilon = 10^(-1/delta). For every m>1/delta we have that

        |  m           |
        | ---   9      |     1          1
        | >   ---- - 1 | = ---- < ------------ = epsilon
        | --- 10^n     |   10^m   10^(1/delta)
        | n=1          |

        So by the (epsilon-delta) definition of the limit we have
               m
              ---   9
         lim  >   ---- = 1
        m->oo --- 10^n
              n=1

    An *informal* argument could be given by noticing that the following
    sequence of "natural" operations has as a consequence 1 = 0.9999....
    Therefore it's "natural" to assume 1 = 0.9999.....

             x = 0.99999....
           10x = 9.99999....
       10x - x = 9 
            9x = 9                
             x = 1
    Thus
             1 = 0.99999....

    References:

    E. Hewitt & K. Stromberg, Real and Abstract Analysis, 
    Springer-Verlag, Berlin, 1965.

    W. Rudin, Principles of Mathematical Analysis, McGraw-Hill, 1976.

10Q:  Where I can get pi up to a few hundred thousand digits of pi? 
    Does anyone have an algorithm to compute pi to those zillion 
    decimal places?

A:  MAPLE or MATHEMATICA can give you 10,000 digits of Pi in a blink,
    and they can compute another 20,000-500,000 overnight (range depends
    on hardware platform).
 
    It is possible to retrieve 1.25+ million digits of pi via anonymous
    ftp from the site wuarchive.wustl.edu, in the files pi.doc.Z and
    pi.dat.Z which reside in subdirectory doc/misc/pi.

    References :
    (This is a short version for a more comprhensive list contact
    Juhana Kouhia at [email-masked])

    J. M. Borwein, P. B. Borwein, and D. H. Bailey, "Ramanujan,
    Modular Equations, and Approximations to Pi", American Mathematical
    Monthly, vol. 96, no. 3 (March 1989), p. 201 - 220.

    P. Beckman
    A history of pi
    Golem Press, CO, 1971 (fourth edition 1977)

    J.M. Borwein and P.B. Borwein
    The arithmetic-geometric mean and fast computation of elementary
    functions
    SIAM Review, Vol. 26, 1984, pp. 351-366

    J.M. Borwein and P.B. Borwein
    More quadratically converging algorithms for pi
    Mathematics of Computation, Vol. 46, 1986, pp. 247-253
 
    J.M. Borwein and P.B. Borwein
    Pi and the AGM - a study in analytic number theory and
    computational complexity
    Wiley, New York, 1987

    Shlomo Breuer and Gideon Zwas
    Mathematical-educational aspects of the computation of pi
    Int. J. Math. Educ. Sci. Technol., Vol. 15, No. 2, 1984,
    pp. 231-244
 
    Y. Kanada and Y. Tamura
    Calculation of pi to 10,013,395 decimal places based on the
    Gauss-Legendre algorithm and Gauss arctangent relation
    Computer Centre, University of Tokyo, 1983
 
    Morris Newman and Daniel Shanks
    On a sequence arising in series for pi
    Mathematics of computation, Vol. 42, No. 165, Jan 1984,
    pp. 199-217

    E. Salamin
    Computation of pi using arithmetic-geometric mean
    Mathematics of Computation, Vol. 30, 1976, pp. 565-570
 
    D. Shanks and J.W. Wrench, Jr.
    Calculation of pi to 100,000 decimals
    Mathematics of Computation, Vol. 16, 1962, pp. 76-99
 
    Daniel Shanks
    Dihedral quartic approximations and series for pi
    J. Number Theory, Vol. 14, 1982, pp.397-423
 
    David Singmaster
    The legal values of pi
    The Mathematical Intelligencer, Vol. 7, No. 2, 1985
 
    Stan Wagon
    Is pi normal?
    The Mathematical Intelligencer, Vol. 7, No. 3, 1985

    J.W. Wrench, Jr.
    The evolution of extended decimal approximations to pi
    The Mathematics Teacher, Vol. 53, 1960, pp. 644-650

11Q:  There are three doors, and there is a car hidden behind one
    of them, Master Mind and other games ..

A:  Read frequently asked questions from rec.puzzles, where the
    problem is solved and carefully explained. (The Monty
    Hall problem). MANY OTHER "MATHEMATICAL" GAMES ARE EXPLAINED
    IN THE REC.PUZZLES FAQ. READ IT BEFORE ASKING IN SCI.MATH.

    Your chance of winning is 2/3 if you switch and 1/3 if you don't.
    For a full explanation from the frequently asked questions list
    for rec.puzzles, send to the address [email-masked]
    an email message consisting of the text

               send switch

    Also any other FAQ list can be obtained through anonymous ftp from
    rtfm.mit.edu.

    References
    
    American Mathematical Monthly, January 1992.

    For the game of Master Mind it has been proven that no more than
    five moves are required in the worst case. For references look at

    One such algorithm was published in the Journal of Recreational
    Mathematics; in '70 or '71 (I think), which always solved the
    4 peg problem in 5 moves. Knuth later published an algorithm which
    solves the problem in a shorter # of moves - on average - but can
    take six guesses on certain combinations.

    Donald E. Knuth, The Computer as Master Mind, J. Recreational Mathematics
    9 (1976-77), 1-6.

12Q:  What is the formula for the "Surface Area" of a sphere in
    Euclidean N-Space.  That is, of course, the volume of the N-1
    solid which comprises the boundary of an N-Sphere.  

A:  The volume of a ball is the easiest formula to remember:  It's r^N
    times pi^(N/2)/(N/2)!.  The only hard part is taking the factorial
    of a half-integer.  The real definition is that x! = Gamma(x+1), but
    if you want a formula, it's:

    (1/2+n)! = sqrt(pi)*(2n+2)!/(n+1)!/4^(n+1)

    To get the surface area, you just differentiate to get
    N*pi^(N/2)/(N/2)!*r^(N-1).

    There is a clever way to obtain this formula using Gaussian
    integrals. First, we note that the integral over the line of
    e^(-x^2) is sqrt(pi).  Therefore the integral over N-space of
    e^(-x_1^2-x_2^2-...-x_N^2) is sqrt(pi)^n.  Now we change to
    spherical coordinates.  We get the integral from 0 to infinity 
    of V*r^(N-1)*e^(-r^2), where V is the surface volume of a sphere.
    Integrate by parts repeatedly to get the desired formula.

13Q:  Anyone knows a name (or a closed form) for
  
      f(x)^f(x)=x

    Solving for f one finds a "continued fraction"-like answer

               f(x) = log x
                      -----
                      log (log x
                          ------
                              ...........

A:  This question has been repeated here from time to time over the 
    years, and no one seems to have heard of any published work on it,
    nor a published name for it (D. Merrit proposes "lx" due to its
    (very) faint resemblence to log). It's not an analytic function.

    The "continued fraction" form for its numeric solution is highly 
    unstable in the region of its minimum at 1/e (because the graph is
    quite flat there yet logarithmic approximation oscillates wildly),
    although it converges fairly quickly elsewhere. To compute its value
    near 1/e, I used the bisection method with good results. Bisection
    in other regions converges much more slowly than the "logarithmic 
    continued fraction" form, so a hybrid of the two seems suitable.
    Note that it's dual valued for the reals (and many valued complex
    for negative reals).

    A similar function is a "built-in" function in MAPLE called W(x).
    MAPLE considers a solution in terms of W(x) as a closed form (like
    the erf function). W is defined as W(x)*exp(W(x))=x.

    If anyone ever runs across something published on the subject,
    please post.

14Q:  The existence of a projective plane of order 10 has long been
    an outstanding problem in discrete mathematics and finite geometry.

A:  More precisely, the question is: is it possible to define 111 sets
    (lines) of 11 points each such that:
    for any pair of points there is precisely one line containing them
    both and for any pair of lines there is only one point common to
    them both.
    Analogous questions with n^2 + n + 1 and n + 1 instead of 111 and 11
    have been positively answered only in case n is a prime power.
    For n=6 it is not possible.  The n=10 case has been settled as
    not possible either by Clement Lam. See Am. Math. Monthly,
    recent issue. As the "proof" took several years of computer search
    (the equivalent of 2000 hours on a Cray-1) it can be called the most
    time-intensive computer assisted single proof.
    The final steps were ready in January 1989.

15Q:  Is there a formula to determine the day of the week, given
    the month, day and year? 
 
A:  Here is the standard method.
 
     A. Take the last two digits of the year.
     B. Divide by 4, discarding any fraction.
     C. Add the day of the month.
     D. Add the month's key value: JFM AMJ JAS OND
                                   144 025 036 146
     E. Subtract 1 for January or February of a non-leap year.
     F. For a Gregorian date, add 0 for 1900's, 6 for 2000's, 4 for 1700's, 2
           for 1800's; for other years, add or subtract multiples of 400.
     G. For a Julian date, add 1 for 1700's, and 1 for every additional
      century you go back.
     H. Add the year.

    Now take the remainder when you divide by 7; 0 is Sunday, the first day
    of the week, 1 is Monday, and so on.
 
    Another formula is:
 
    W == k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]     mod 7
       where [] denotes the integer floor function (round down),
       k is day (1 to 31)
       m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
                     Treat Jan & Feb as months of the preceding year
       C is century ( 1987 has C = 19)
       Y is year    ( 1987 has Y = 87 except Y = 86 for jan & feb)
       W is week day (0 = Sunday, ..., 6 = Saturday)

    This formula is good for the Gregorian calendar
    (introduced 1582 in parts of Europe, adopted in 1752 in Great Britain
    and its colonies, and on various dates in other countries).

    It handles century & 400 year corrections, but there is still a 
    3 day / 10,000 year error which the Gregorian calendar does not take.
    into account.  At some time such a correction will have to be 
    done but your software will probably not last that long :-)   !

    References:
 
    Winning Ways  by Conway, Guy, Berlekamp is supposed to have it.

    Martin Gardner in "Mathematical Carnaval".

    Michael Keith and Tom Craver, "The Ultimate Perpetual Calendar?",
    Journal of Recreational Mathematics, 22:4, pp. 280-282, 1990.
	
    K. Rosen, "Elementary Number Theory",  p. 156.

16Q:  What is the Axiom of Choice?  Why is it important? Why some articles
    say "such and such is provable, if you accept the axiom of choice."?
    What are the arguments for and against the axiom of choice?  

A:  There are several equivalent formulations:

    -The Cartesian product of nonempty sets is nonempty, even
    if the product is of an infinite family of sets.

    -Given any set S of mutually disjoint nonempty sets, there is a set C
    containing a single member from each element of S.  C can thus be
    thought of as the result of "choosing" a representative from each
    set in S. Hence the name. 

    >Why is it important? 

    All kinds of important theorems in analysis require it.  Tychonoff's
    theorem and the Hahn-Banach theorem are examples. AC is equivalent
    to the thesis that every set can be well-ordered.  Zermelo's first
    proof of this in 1904 I believe was the first proof in which AC was
    made explicit.  AC is especially handy for doing infinite cardinal
    arithmetic, as without it the most you get is a *partial* ordering
    on the cardinal numbers.  It also enables you to prove such 
    interesting general facts as that n^2 = n for all infinite cardinal 
    numbers.

    > What are the arguments for and against the axiom of choice?

    The axiom of choice is independent of the other axioms of set theory
    and can be assumed or not as one chooses.

    (For) All ordinary mathematics uses it.

    There are a number of arguments for AC, ranging from a priori to 
    pragmatic.  The pragmatic argument (Zermelo's original approach) is
    that it allows you to do a lot of interesting mathematics.  The more
    conceptual argument derives from the "iterative" conception of set
    according to which sets are "built up" in layers, each layer consisting
    of all possible sets that can be constructed out of elements in the
    previous layers.  (The building up is of course metaphorical, and is
    suggested only by the idea of sets in some sense consisting of their 
    members; you can't have a set of things without the things it's a set
    of).  If then we consider the first layer containing a given set S of
    pairwise disjoint nonempty sets, the argument runs, all the elements 
    of all the sets in S must exist at previous levels "below" the level
    of S.  But then since each new level contains *all* the sets that can
    be formed from stuff in previous levels, it must be that at least by
    S's level all possible choice sets have already been *formed*. This
    is more in the spirit of Zermelo's later views (c. 1930). 

    (Against) It has some supposedly counterintuitive consequences,
    such as the Banach-Tarski paradox. (See next question)

    Arguments against AC typically target its nonconstructive character:
    it is a cheat because it conjures up a set without providing any
    sort of *procedure* for its construction--note that no *method* is
    assumed for picking out the members of a choice set.  It is thus the
    platonic axiom par excellence, boldly asserting that a given set
    will always exist under certain circumstances in utter disregard of
    our ability to conceive or construct it.  The axiom thus can be seen
    as marking a divide between two opposing camps in the philosophy of
    mathematics:  those for whom mathematics is essentially tied to our
    conceptual capacities, and hence is something we in some sense
    *create*, and those for whom mathematics is independent of any such
    capacities and hence is something we *discover*.  AC is thus of 
    philosophical as well as mathematical significance.

    It should be noted that some interesting mathematics has come out of an
    incompatible axiom, the Axiom of Determinacy (AD).  AD asserts that
    any two-person game without ties has a winning strategy for the first or
    second player.  For finite games, this is an easy theorem; for infinite
    games with duration less than \omega and move chosen from a countable set,
    you can prove the existence of a counter-example using AC.  Jech's book
    "The Axiom of Choice" has a discussion.  

    An example of such a game goes as follows.  

       Choose in advance a set of infinite sequences of integers; call it A.
       Then I pick an integer, then you do, then I do, and so on forever 
       (i.e. length \omega).  When we're done, if the sequence of integers
       we've chosen is in A, I win; otherwise you win.  AD says that one of
       us must have a winning strategy.  Of course the strategy, and which
       of us has it, will depend upon A.

    From a philosophical/intuitive/pedagogical standpoint, I think Bertrand
    Russell's shoe/sock analogy has a lot to recommend it.  Suppose you have an
    infinite collection of pairs of shoes.  You want to form a set with one
    shoe from each pair.  AC is not necessary, since you can define the set as
    "the set of all left shoes". (Technically, we're using the axiom of
    replacement, one of the basic axioms of Zermelo-Fraenkel (ZF) set theory.)
    If instead you want to form a set containing one sock from each pair of an
    infinite collection of pairs of socks, you now need AC.

    References:

    Maddy, "Believing the Axioms, I", J. Symb. Logic, v. 53, no. 2, June 1988,
    pp. 490-500, and "Believing the Axioms II" in v.53, no. 3.  

    Gregory H. Moore, Zermelo's Axiom of Choice, New York, Springer-Verlag,
    1982.

    H. Rubin and J. E. Rubin, Equivalents of the Axiom of Choice, Amsterdam,
     North-Holland, 1963.

    A. Fraenkel, Y.  Bar-Hillel, and A. Levy, Foundations of Set Theory, 
    Amsterdam, North-Holland, 1984 (2nd edition, 2nd printing), pp. 53-86.

17Q:  Cutting a sphere into pieces of larger volume. Is it possible
    to cut a sphere into a finite number of pieces and reassemble 
    into a solid of twice the volume?

A:  This question has many variants and it is best answered explicitly.
    Given two polygons of the same area, is it always possible to
    dissect one into a finite number of pieces which can be reassembled
    into a replica of the other?

    Dissection theory is extensive.  In such questions one needs to
    specify

     (A) what a "piece" is,  (polygon?  Topological disk?  Borel-set? 
         Lebesgue-measurable set?  Arbitrary?)

     (B) how many pieces are permitted (finitely many? countably? uncountably?)

     (C) what motions are allowed in "reassembling" (translations?
         rotations?  orientation-reversing maps?  isometries?  
         affine maps?  homotheties?  arbitrary continuous images?  etc.)

     (D) how the pieces are permitted to be glued together.  The
         simplest notion is that they must be disjoint.  If the pieces
         are polygons [or any piece with a nice boundary] you can permit
         them to be glued along their boundaries, ie the interiors of the
         pieces disjoint, and their union is the desired figure.

    Some dissection results

     1) We are permitted to cut into FINITELY MANY polygons, to TRANSLATE
        and ROTATE the pieces, and to glue ALONG BOUNDARIES;
        then Yes, any two equal-area polygons are equi-decomposable.

        This theorem was proven by Bolyai and Gerwien independently, and has
        undoubtedly been independently rediscovered many times.  I would not
        be surprised if the Greeks knew this.

        The Hadwiger-Glur theorem implies that any two equal-area polygons are
        equi-decomposable using only TRANSLATIONS and ROTATIONS BY 180
        DEGREES. 

     2) THM (Hadwiger-Glur, 1951) Two equal-area polygons P,Q are
        equi-decomposable by TRANSLATIONS only, iff we have equality of these
        two functions:     PHI_P() = PHI_Q()
        Here, for each direction v (ie, each vector on the unit circle in the
        plane), let PHI_P(v) be the sum of the lengths of the edges of P which
        are perpendicular to v, where for such an edge, its length is positive
        if v is an outward normal to the edge and is negative if v is an 
        inward normal to the edge.

     3) In dimension 3, the famous "Hilbert's third problem" is:
     
       "If P and Q are two polyhedra of equal volume, are they
        equi-decomposable by means of translations and rotations, by
        cutting into finitely many sub-polyhedra, and gluing along
        boundaries?" 

        The answer is "NO" and was proven by Dehn in 1900, just a few months
        after the problem was posed. (Ueber raumgleiche polyeder, Goettinger 
        Nachrichten 1900, 345-354). It was the first of Hilbert's problems
        to be solved. The proof is nontrivial but does *not* use the axiom 
        of choice.

        "Hilbert's Third Problem", by V.G.Boltianskii, Wiley 1978.

     4) Using the axiom of choice on non-countable sets, you can prove
        that a solid sphere can be dissected into a finite number of
        pieces that can be reassembled to two solid spheres, each of
        same volume of the original. No more than nine pieces are needed.

        This construction is known as the "Banach-Tarski" paradox or the 
        "Banach-Tarski-Hausdorff" paradox (Hausdorff did an early version of
        it).  The "pieces" here are non-measurable sets, and they are
        assembled *disjointly* (they are not glued together along a boundary,
        unlike the situation in Bolyai's thm.)
         An excellent book on Banach-Tarski is:

        "The Banach-Tarski Paradox", by Stan Wagon, 1985, Cambridge
        University Press.

         Also read in the Mathematical Intelligencier an article on
        the Banach-Tarski Paradox.

        The pieces are not (Lebesgue) measurable, since measure is preserved
        by rigid motion. Since the pieces are non-measurable, they do not
        have reasonable boundaries. For example, it is likely that each piece's
        topological-boundary is the entire ball.

        The full Banach-Tarski paradox is stronger than just doubling the
        ball.  It states:

     5) Any two bounded subsets (of 3-space) with non-empty interior, are
        equi-decomposable by translations and rotations.

        This is usually illustrated by observing that a pea can be cut up
        into finitely pieces and reassembled into the Earth.

        The easiest decomposition "paradox" was observed first by Hausdorff:

     6) The unit interval can be cut up into COUNTABLY many pieces which,
        by *translation* only, can be reassembled into the interval of
        length 2.

        This result is, nowadays, trivial, and is the standard example of a
        non-measurable set, taught in a beginning graduate class on measure
        theory.

        References:

        In addition to Wagon's book above, Boltyanskii has written at least
        two works on this subject.  An elementary one is:

          "Equivalent and equidecomposable figures"

        in Topics in Mathematics published by D.C. HEATH AND CO., Boston.  It
        is a translation from the 1956 work in Russian.   

          Also, the article "Scissor Congruence" by Dubins, Hirsch and ?,
        which appeared about 20 years ago in the Math Monthly, has a pretty
        theorem on decomposition by Jordan arcs.

        ``Banach and Tarski had hoped that the physical absurdity of this
        theorem would encourage mathematicians to discard AC. They were 
        dismayed when the response of the math community was `Isn't AC great?
        How else could we get such unintuitive results?' ''

18Q:   Is there a theory of quaternionic analytic functions, that is, a four-
     dimensional analog to the theory of complex analytic functions?
    
A.   Yes.   This was developed in the 1930s by the mathematician
     Fueter.   It is based on a generalization of the Cauchy-Riemann
     equations, since the possible alternatives of power series expansions
     or quaternion differentiability do not produce useful theories.
     A number of useful integral theorems follow from the theory.
     Sudbery provides an excellent review.  Deavours covers some of the same
     material less thoroughly.   Brackx discusses a further generalization
     to arbitrary Clifford algebras.

      Anthony Sudbery, Quaternionic Analysis, Proc. Camb. Phil. Soc.,
      vol. 85, pp 199-225, 1979.

      Cipher A. Deavours, The Quaternion Calculus, Am. Math. Monthly,
      vol. 80, pp 995-1008, 1973.

      F. Brackx and R. Delanghe and F. Sommen, Clifford analysis,
      Pitman, 1983.

19Q:  What is the Erdos Number?

     Form an undirected graph where the vertices are academics, and an
     edge connects academic X to academic Y if X has written a paper
     with Y.  The Erdos number of X is the length of the shortest path
     in this graph connecting X with Erdos.

     What is the Erdos Number of X ? for a few selected X in {Math,physics}

     Erdos has Erdos number 0.  Co-authors of Erdos have Erdos number 1.
     Einstein has Erdos number 2, since he wrote a paper with Ernst Straus,
     and Straus wrote many papers with Erdos.

     Why people care about it?

     Nobody seems to have a reasonable answer...

     Who is Paul Erdos? [small biography in peparation]

      Caspar Goffman, And what is your Erdos number?, American Mathematical
      Monthly v. 76 (1969), p. 791.

20Q:  Does there exist a number that is perfect and odd?

     A given number is perfect if it is equal to the sum of all its proper 
     divisors. This question was first posed by Euclid in ancient Greece.
     This question is still open.  Euler proved that if  N  is an odd
     perfect number, then in the prime power decomposition of N, exactly 
     one exponent is congruent to 1 mod 4 and all the other exponents are
     even. Furthermore, the prime occuring to an odd power must itself be
     congruent to 1 mod 4.  A sketch of the proof appears in Exercise 87,
     page 203 of Underwood Dudley's Elementary Number Theory, 2nd ed.  

21Q.- Why is there no Nobel in mathematics? #

     [answer is forecoming]

22Q.- General References and textbooks... #

     [a list of general references and most commonly used textbooks]
     [                                                             ]

--------------------------------------------------------------------------
Questions and Answers _Compiled_ by:

Alex Lopez-Ortiz                              [email-masked]
Deparment of Computer Science                       University of Waterloo
Waterloo, Ontario                                                   Canada