home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / answers / sci-math / faq / part1 next >
Text File  |  1993-10-06  |  63KB  |  1,484 lines
  1. Newsgroups: sci.math,news.answers,sci.answers
  2. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!usc!cs.utexas.edu!utnut!torn!watserv2.uwaterloo.ca!watdragon.uwaterloo.ca!alopez-o
  3. From: alopez-o@maytag.uwaterloo.ca (Alex Lopez-Ortiz)
  4. Subject: sci.math: Frequently Asked Questions
  5. Message-ID: <CEH8Cx.F0G@watdragon.uwaterloo.ca>
  6. Followup-To: sci.math
  7. Summary: (version 4.5)
  8. Originator: alopez-o@maytag.uwaterloo.ca
  9. Sender: alopez-o@maytag.uwaterloo.ca
  10. Reply-To: alopez-o@maytag.uwaterloo.ca
  11. Organization: University of Waterloo
  12. Date: Wed, 6 Oct 1993 13:05:21 GMT
  13. Approved: news-answers-request@MIT.Edu
  14. Lines: 1467
  15. Xref: senator-bedfellow.mit.edu sci.math:54194 news.answers:13305 sci.answers:535
  16.  
  17. Archive-Name: sci-math-faq
  18. Version: $Id: sci-math-faq,v 4.5 93/07/19 15:55:00 $
  19.  
  20.  This is, hopefully, the last posting of the FAQ list in its old style.
  21. A new version will be posted on october 21st.
  22.  
  23. It will be split in several parts, with a short introduction being posted
  24. weekly and the full version being posted monthly (instead of posting 
  25. 70K biweekly).
  26.  
  27. If there's a topic you think should be included send e-mail to
  28. alopez-o@maytag.uwaterloo.ca
  29.  
  30. Topics to be included: Questions 22, 24 and 25.
  31.  
  32.  
  33.  
  34. This is a list of Frequently Asked Questions for sci.math (version 4.5).
  35. Any contributions/suggestions/corrections are most welcome. Please use
  36. * e-mail * on any comment concerning the FAQ list.
  37.  
  38. Changes and additions are marked with a # on the table of contents.
  39. This FAQ list (and most others, for that matter) is available via anonymous
  40. ftp at rtfm.mit.edu (18.70.0.224).
  41.  
  42. The list of contributors to this FAQ list is too large to include here;
  43. but thanks are due to all of them (you know who you are folks!).
  44.  
  45.              Table of Contents
  46.              -----------------
  47.  
  48.  1Q.- Fermat's Last Theorem, status of .. #
  49.  2Q.- Four Colour Theorem, proof of ..
  50.  3Q.- Values of Record Numbers      
  51.  4Q.- General Netiquette
  52.  5Q.- Computer Algebra Systems, application of ..
  53.  6Q.- Computer Algebra Systems, references to ..
  54.  7Q.- Fields Medal, general info ..
  55.  8Q.- 0^0=1. A comprehensive approach 
  56.  9Q.- 0.999... = 1. Properties of the real numbers ..
  57. 10Q.- Digits of Pi, computation and references 
  58. 11Q.- There are three doors, The Monty Hall problem, Master Mind and
  59.       other games .. 
  60. 12Q.- Surface and Volume of the n-ball  
  61. 13Q.- f(x)^f(x)=x, name of the function ..
  62. 14Q.- Projective plane of order 10 ..   
  63. 15Q.- How to compute day of week of a given date 
  64. 16Q.- Axiom of Choice and/or Continuum Hypothesis? 
  65. 17Q.- Cutting a sphere into pieces of larger volume  
  66. 18Q.- Pointers to Quaternions
  67. 19Q.- Erdos Number 
  68. 20Q.- Odd Perfect Number 
  69. 21Q.- Why is there no Nobel in mathematics? 
  70. 22Q.- General References and textbooks... 
  71. 23Q.- Formula for prime numbers... #
  72. 24Q.- Interest Rate...
  73. 25Q.- Euler's formula e^(i Pi) = - 1 ...
  74.  
  75. 1Q:  What is the current status of Fermat's last theorem?
  76.     (There are no positive integers x,y,z, and n > 2 such that 
  77.     x^n + y^n = z^n)  
  78.     I heard that <insert name here> claimed to have proved it but later
  79.     on the proof was found to be wrong. ...
  80.     (wlog we assume x,y,z to be relatively prime)
  81.  
  82. A:  The status of FLT has remained remarkably constant.  Every few
  83.     years, someone claims to have a proof ... but oh, wait, not quite.
  84.  
  85.     UPDATE.... UPDATE
  86.  
  87.     Andrew Wiles, a researcher at Princeton claims to have found
  88.     a proof. 
  89.  
  90.     The proof was presented in Cambridge, UK during a three day seminar 
  91.     to an audience including some of the leading experts in the field.
  92.  
  93.     The proof is long and cumbersome, but here are some of the first
  94.     few details:
  95.  
  96.     *From Ken Ribet:
  97.  
  98. Here is a brief summary of what Wiles said in his three lectures.
  99.  
  100. The method of Wiles borrows results and techniques from lots and lots
  101. of people.  To mention a few: Mazur, Hida, Flach, Kolyvagin, yours
  102. truly, Wiles himself (older papers by Wiles), Rubin...  The way he does
  103. it is roughly as follows.  Start with a mod p representation of the
  104. Galois group of Q which is known to be modular.  You want to prove that
  105. all its lifts with a certain property are modular.  This means that the
  106. canonical map from Mazur's universal deformation ring to its "maximal
  107. Hecke algebra" quotient is an isomorphism.  To prove a map like this is
  108. an isomorphism, you can give some sufficient conditions based on
  109. commutative algebra.  Most notably, you have to bound the order of a
  110. cohomology group which looks like a Selmer group for Sym^2 of the
  111. representation attached to a modular form.  The techniques for doing
  112. this come from Flach; you also have to use Euler systems a la
  113. Kolyvagin, except in some new geometric guise.
  114.  
  115. If you take an elliptic curve over Q, you can look at the
  116. representation of Gal on the 3-division points of the curve.  If you're
  117. lucky, this will be known to be modular, because of results of Jerry
  118. Tunnell (on base change).  Thus, if you're lucky, the problem I
  119. described above can be solved (there are most definitely some
  120. hypotheses to check), and then the curve is modular.  Basically, being
  121. lucky means that the image of the representation of Galois on
  122. 3-division points is GL(2,Z/3Z).
  123.  
  124. Suppose that you are unlucky, i.e., that your curve E has a rational
  125. subgroup of order 3.  Basically by inspection, you can prove that if it
  126. has a rational subgroup of order 5 as well, then it can't be
  127. semistable.  (You look at the four non-cuspidal rational points of
  128. X_0(15).)  So you can assume that E[5] is "nice." Then the idea is to
  129. find an E' with the same 5-division structure, for which E'[3] is
  130. modular.  (Then E' is modular, so E'[5] = E[5] is modular.)  You
  131. consider the modular curve X which parametrizes elliptic curves whose
  132. 5-division points look like E[5].  This is a "twist" of X(5).  It's
  133. therefore of genus 0, and it has a rational point (namely, E), so it's
  134. a projective line.  Over that you look at the irreducible covering
  135. which corresponds to some desired 3-division structure.  You use
  136. Hilbert irreducibility and the Cebotarev density theorem (in some way
  137. that hasn't yet sunk in) to produce a non-cuspidal rational point of X
  138. over which the covering remains irreducible.  You take E' to be the
  139. curve corresponding to this chosen rational point of X.
  140.  
  141.  
  142.     *From the previous version of the FAQ:
  143.  
  144.     (b) conjectures arising from the study of elliptic curves and
  145.     modular forms. -- The Taniyama-Weil-Shmimura conjecture.
  146.  
  147.     There is a very important and well known conjecture known as the
  148.     Taniyama-Weil-Shimura conjecture that concerns elliptic curves.
  149.     This conjecture has been shown by the work of Frey, Serre, Ribet,
  150.     et. al. to imply FLT uniformly, not just asymptotically as with the
  151.     ABC conj.
  152.     
  153.     The conjecture basically states that all elliptic curves can be
  154.     parameterized in terms of modular forms. 
  155.  
  156.     There is new work on the arithmetic of elliptic curves. Sha, the
  157.     Tate-Shafarevich group on elliptic curves of rank 0 or 1. By the way
  158.     an interesting aspect of this work is that there is a close 
  159.     connection between Sha, and some of the classical work on FLT. For
  160.     example, there is a classical proof that uses infinite descent to
  161.     prove FLT for n = 4. It can be shown that there is an elliptic curve
  162.     associated with FLT and that for n=4, Sha is trivial. It can also be
  163.     shown that in the cases where Sha is non-trivial, that 
  164.     infinite-descent arguments do not work; that in some sense 'Sha
  165.     blocks the descent'. Somewhat more technically, Sha is an
  166.     obstruction to the local-global principle [e.g. the Hasse-Minkowski
  167.     theorem].
  168.  
  169.     *From Karl Rubin:
  170.  
  171. Theorem.  If E is a semistable elliptic curve defined over Q,
  172.   then E is modular.
  173.  
  174. It has been known for some time, by work of Frey and Ribet, that
  175. Fermat follows from this.  If u^q + v^q + w^q = 0, then Frey had
  176. the idea of looking at the (semistable) elliptic curve
  177. y^2 = x(x-a^q)(x+b^q).  If this elliptic curve comes from a modular
  178. form, then the work of Ribet on Serre's conjecture shows that there
  179. would have to exist a modular form of weight 2 on Gamma_0(2).  But
  180. there are no such forms.
  181.  
  182. To prove the Theorem, start with an elliptic curve E, a prime p and let
  183.  
  184.      rho_p : Gal(Q^bar/Q) -> GL_2(Z/pZ)
  185.  
  186. be the representation giving the action of Galois on the p-torsion
  187. E[p].  We wish to show that a _certain_ lift of this representation
  188. to GL_2(Z_p) (namely, the p-adic representation on the Tate module
  189. T_p(E)) is attached to a modular form.  We will do this by using
  190. Mazur's theory of deformations, to show that _every_ lifting which
  191. 'looks modular' in a certain precise sense is attached to a modular form.
  192.  
  193. Fix certain 'lifting data', such as the allowed ramification,
  194. specified local behavior at p, etc. for the lift. This defines a
  195. lifting problem, and Mazur proves that there is a universal
  196. lift, i.e. a local ring R and a representation into GL_2(R) such
  197. that every lift of the appropriate type factors through this one.
  198.  
  199. Now suppose that rho_p is modular, i.e. there is _some_ lift
  200. of rho_p which is attached to a modular form.  Then there is
  201. also a hecke ring T, which is the maximal quotient of R with the
  202. property that all _modular_ lifts factor through T.  It is a
  203. conjecture of Mazur that R = T, and it would follow from this
  204. that _every_ lift of rho_p which 'looks modular' (in particular the
  205. one we are interested in) is attached to a modular form.
  206.  
  207. Thus we need to know 2 things:
  208.   (a)  rho_p is modular
  209.   (b)  R = T.
  210.  
  211. It was proved by Tunnell that rho_3 is modular for every elliptic
  212. curve.  This is because PGL_2(Z/3Z) = S_4.  So (a) will be satisfied
  213. if we take p=3.  This is crucial.
  214.  
  215. Wiles uses (a) to prove (b) under some restrictions on rho_p.  Using
  216. (a) and some commutative algebra (using the fact that T is Gorenstein,
  217. 'basically due to Mazur')  Wiles reduces the statement T = R to
  218. checking an inequality between the sizes of 2 groups.  One of these
  219. is related to the Selmer group of the symmetric sqaure of the given
  220. modular lifting of rho_p, and the other is related (by work of Hida)
  221. to an L-value.  The required inequality, which everyone presumes is
  222. an instance of the Bloch-Kato conjecture, is what Wiles needs to verify.
  223.  
  224. He does this using a Kolyvagin-type Euler system argument.  This is
  225. the most technically difficult part of the proof, and is responsible
  226. for most of the length of the manuscript.  He uses modular
  227. units to construct what he calls a 'geometric Euler system' of
  228. cohomology classes.  The inspiration for his construction comes
  229. from work of Flach, who came up with what is essentially the
  230. 'bottom level' of this Euler system.  But Wiles needed to go much
  231. farther than Flach did.  In the end, _under_certain_hypotheses_ on rho_p
  232. he gets a workable Euler system and proves the desired inequality.
  233. Among other things, it is necessary that rho_p is irreducible.
  234.  
  235. Suppose now that E is semistable.
  236.  
  237. Case 1.  rho_3 is irreducible.
  238. Take p=3.  By Tunnell's theorem (a) above is true.  Under these
  239. hypotheses the argument above works for rho_3, so we conclude
  240. that E is modular.
  241.  
  242. Case 2.  rho_3 is reducible.
  243. Take p=5.  In this case rho_5 must be irreducible, or else E
  244. would correspond to a rational point on X_0(15).  But X_0(15)
  245. has only 4 noncuspidal rational points, and these correspond to
  246. non-semistable curves.  _If_ we knew that rho_5 were modular,
  247. then the computation above would apply and E would be modular.
  248.  
  249. We will find a new semistable elliptic curve E' such that
  250. rho_{E,5} = rho_{E',5} and rho_{E',3} is irreducible.  Then
  251. by Case I, E' is modular.  Therefore rho_{E,5} = rho_{E',5}
  252. does have a modular lifting and we will be done.
  253.  
  254. We need to construct such an E'.  Let X denote the modular
  255. curve whose points correspond to pairs (A, C) where A is an
  256. elliptic curve and C is a subgroup of A isomorphic to the group
  257. scheme E[5].  (All such curves will have mod-5 representation
  258. equal to rho_E.)  This X is genus 0, and has one rational point
  259. corresponding to E, so it has infinitely many.  Now Wiles uses a
  260. Hilbert Irreducibility argument to show that not all rational
  261. points can be images of rational points on modular curves
  262. covering X, corresponding to degenerate level 3 structure
  263. (i.e. im(rho_3) not GL_2(Z/3)).  In other words, an E' of the
  264. type we need exists.  (To make sure E' is semistable, choose
  265. it 5-adically close to E.  Then it is semistable at 5, and at
  266. other primes because rho_{E',5} = rho_{E,5}.)
  267.     
  268.  
  269.  
  270. 2Q: Has the Four Colour Theorem been solved?
  271.     (Every planar map with regions of simple borders can be coloured 
  272.     with 4 colours in such a way that no two regions sharing a non-zero
  273.     length border have the same colour.)
  274.  
  275. A:  This theorem was proved with the aid of a computer in 1976.
  276.     The proof shows that if aprox. 1,936  basic forms of maps
  277.     can be coloured with four colours, then any given map can be
  278.     coloured with four colours. A computer program coloured this 
  279.     basic forms. So far nobody has been able to prove it without 
  280.     using a computer. In principle it is possible to emulate the 
  281.     computer proof by hand computations.
  282.  
  283.     References:
  284.  
  285.     K. Appel and W. Haken, Every planar map is four colourable,
  286.     Bulletin of the American Mathematical Society, vol. 82, 1976 
  287.     pp.711-712.
  288.  
  289.     K. Appel and W. Haken, Every planar map is four colourable,
  290.     Illinois Journal of Mathematics, vol. 21, 1977, pp. 429-567.
  291.  
  292.     T. Saaty and Paul Kainen, The Four Colour Theorem: Assault and
  293.     Conquest, McGraw-Hill, 1977. Reprinted by Dover Publications 1986. 
  294.  
  295.     K. Appel and W. Haken, Every Planar Map is Four Colourable,
  296.     Contemporary Mathematics, vol. 98, American Mathematical Society,
  297.     1989, pp.741.
  298.  
  299.     F. Bernhart, Math Reviews. 91m:05007, Dec. 1991. (Review of Appel
  300.     and Haken's book).
  301.  
  302.  
  303.  
  304.  
  305. 3Q:  What are the values of:
  306.  
  307. largest known Mersenne prime?
  308.  
  309. A:  It is 2^756839-1. It was discovered by a Cray-2 in England in 1992.
  310.     It has 227,832 digits.
  311.  
  312.     
  313. largest known prime?
  314.  
  315. A:  The largest known prime is the Mersenne prime described above.
  316.     The previous record holder, and the largest known non-Mersenne prime,
  317.     is 391581*2^216193-1. See Brown, Noll, Parady, Smith, Smith, and
  318.     Zarantonello, Letter to the editor, American Mathematical Monthly,
  319.     vol. 97, 1990, p. 214. Throughout history, the largest known prime
  320.     has almost always been a Mersenne prime; the period between Brown
  321.     et al's discovery in Aug 1989 and Slowinski & Gage's in March 1992
  322.     is one of the few exceptions.
  323.  
  324.     
  325. largest known twin primes?
  326.     
  327. A:  The largest known twin primes are 4650828 * 1001 * 10^3429  +/- 1.
  328.     They were found by H. Dubner
  329.  
  330.     For an article by the previous record holders see:
  331.  
  332.     B. K. Parady and J. F. Smith and S. E. Zarantonello,
  333.     Smith, Noll and Brown.
  334.     Largest known twin primes, Mathematics of Computation,
  335.     vol.55, 1990, pp. 381-382. 
  336.  
  337.  
  338. largest Fermat number with known factorization?
  339.  
  340. A:  F_11 = (2^(2^11)) + 1 which was  factored by Brent & Morain in
  341.     1988. F9 = (2^(2^9)) + 1 = 2^512 + 1 was factored by 
  342.     A.K. Lenstra, H.W. Lenstra Jr., M.S. Manasse & J.M. Pollard
  343.     in 1990. The factorization for F10 is NOT known.
  344.  
  345.  
  346. Are there good algorithms to factor a given integer?
  347.  
  348. A:  There are several that have subexponential estimated 
  349.     running time, to mention just a few:
  350.  
  351.         Continued fraction algorithm,
  352.         Class group method,
  353.         Quadratic sieve algorithm,
  354.         Elliptic curve algorithm,
  355.         Number field sieve,
  356.         Dixon's random squares algorithm,
  357.         Valle's two-thirds algorithm,
  358.         Seysen's class group algorithm,
  359.  
  360.     A.K. Lenstra, H.W. Lenstra Jr., "Algorithms in Number Theory",
  361.     in: J. van Leeuwen (ed.), Handbook of Theoretical Computer 
  362.     Science, Volume A: Algorithms and Complexity, Elsevier, pp. 
  363.     673-715, 1990.
  364.  
  365.  
  366. List of record numbers?
  367.  
  368. A:  Chris Caldwell maintains "THE LARGEST KNOWN PRIMES (ALL KNOWN
  369.     PRIMES WITH 2000 OR MORE DIGITS)"-list. Send him mail to  
  370.     bf04@UTMartn.bitnet (preferred) or kvax@utkvx.UTK.edu, on any new 
  371.     gigantic primes (greater than 10,000 digits), titanic primes
  372.     (greater than 1000 digits).
  373.  
  374.  
  375. What is the current status on Mersenne primes?
  376.  
  377. A:  Mersenne primes are primes of the form 2^p-1. For 2^p-1 to be prime 
  378.     we must have that p is prime. The following Mersenne primes are
  379.     known.
  380.  
  381.     nr            p                                 year  by
  382.     -----------------------------------------------------------------
  383.      1-5   2,3,5,7,13                    in or before the middle ages
  384.      6-7       17,19                     1588  Cataldi
  385.      8          31                       1750  Euler
  386.      9          61                       1883  Pervouchine
  387.     10          89                       1911  Powers
  388.     11          107                      1914  Powers
  389.     12          127                      1876  Lucas
  390.     13-14       521,607                  1952  Robinson
  391.     15-17       1279,2203,2281           1952  Lehmer
  392.     18          3217                     1957  Riesel
  393.     19-20       4253,4423                1961  Hurwitz & Selfridge
  394.     21-23       9689,9941,11213          1963  Gillies
  395.     24          19937                    1971  Tuckerman
  396.     25          21701                    1978  Noll & Nickel
  397.     26          23209                    1979  Noll
  398.     27          44497                    1979  Slowinski & Nelson
  399.     28          86243                    1982  Slowinski
  400.     29          110503                   1988  Colquitt & Welsh jr.
  401.     30          132049                   1983  Slowinski
  402.     31          216091                   1985  Slowinski
  403.     32?         756839                   1992  Slowinski & Gage
  404.  
  405.     The way to determine if 2^p-1 is prime is to use the Lucas-Lehmer 
  406.     test:
  407.       Lucas_Lehmer_Test(p):
  408.          u := 4
  409.          for i from 3 to p do
  410.             u := u^2-2 mod 2^p-1
  411.          od
  412.          if u == 0 then
  413.             2^p-1 is prime
  414.          else
  415.             2^p-1 is composite
  416.          fi
  417.  
  418.    The following ranges have been checked completely:
  419.     2 - 355K and  430K - 520K
  420.  
  421.    More on Mersenne primes and the Lucas-Lehmer test can be found in:
  422.       G.H. Hardy, E.M. Wright, An introduction to the theory of numbers,
  423.       fifth edition, 1979, pp. 16, 223-225.
  424.  
  425.  
  426. (Please send updates to alopez-o@maytag.UWaterloo.ca)
  427.  
  428.  
  429.  
  430.  
  431. 4Q:  I think I proved <insert big conjecture>.    OR
  432.     I think I have a bright new idea.
  433.  
  434.     What should I do?
  435.  
  436. A:  Are you an expert in the area? If not, please ask first local
  437.     gurus for pointers to related work (the "distribution" field
  438.     may serve well for this purposes). If after reading them you still
  439.     think your *proof is correct*/*idea is new* then send it to the net.
  440.  
  441.  
  442. 5Q:  I have this complicated symbolic problem (most likely
  443.     a symbolic integral or a DE system) that I can't solve.
  444.     What should I do?
  445.  
  446. A:  Find a friend with access to a computer algebra system
  447.     like MAPLE, MACSYMA or MATHEMATICA and ask her/him to solve it.
  448.     If packages cannot solve it, then (and only then) ask the net. 
  449.  
  450.  
  451. 6Q:  Where can I get <Symbolic Computation Package>?
  452.     This is not a comprehensive list. There are other Computer Algebra
  453.     packages available that may better suit your needs. There is also
  454.     a FAQ list in the group sci.math.symbolic. It includes a much larger
  455.     list of vendors and developers. (The FAQ list can be obtained from
  456.     math.berkeley.edu via anonymous ftp).
  457.  
  458. A: Maple 
  459.         Purpose: Symbolic and numeric computation, mathematical
  460.         programming, and mathematical visualization. 
  461.         Contact: Waterloo Maple Software,
  462.         160 Columbia Street West,
  463.         Waterloo, Ontario, Canada     N2L 3L3
  464.         Phone: (519) 747-2373 
  465.         wmsi@daisy.uwaterloo.ca wmsi@daisy.waterloo.edu
  466.  
  467. A: DOE-Macsyma  
  468.         Purpose: Symbolic and mathematical manipulations.
  469.         Contact: National Energy Software Center
  470.         Argonne National Laboratory 9700 South Cass Avenue
  471.         Argonne, Illinois 60439 
  472.         Phone: (708) 972-7250
  473.  
  474. A: Pari            
  475.  
  476.         Purpose: Number-theoretic computations and simple numerical
  477.         analysis.
  478.         Available for most 32-bit machines, including 386+387 and 486.
  479.         This is a copyrighted but free package, available by ftp from
  480.         math.ucla.edu (128.97.4.254) and ftp.inria.fr (128.93.1.26).
  481.         Contact: questions about pari can be sent to pari@ceremab.u-bordeaux.fr
  482.         and for the Macintosh versions to bernardi@mathp7.jussieu.fr
  483.  
  484.  
  485. A: Mathematica
  486.         Purpose: Mathematical computation and visualization,
  487.         symbolic programming. 
  488.         Contact: Wolfram Research, Inc. 
  489.         100 Trade Center Drive Champaign,
  490.         IL 61820-7237
  491.         Phone: 1-800-441-MATH
  492.         info@wri.com
  493.  
  494.  
  495. A: Macsyma
  496.         Purpose: Symbolic numerical and graphical mathematics.
  497.     Contact: Macsyma Inc.
  498.         20 Academy Street
  499.         Arlington, MA 02174
  500.         tel: 617-646-4550
  501.         fax: 617-646-3161
  502.         email: info-macsyma@macsyma.com
  503.  
  504.  
  505. A: Matlab
  506.         Purpose: `matrix laboratory' for tasks involving 
  507.     matrices, graphics and general numerical computation.
  508.     Contact: The MathWorks, Inc.
  509.          21 Prime Park Way
  510.          Natick, MA 01760
  511.          508-653-1415
  512.          info@mathworks.com
  513.  
  514. A: Cayley
  515.         Purpose: Computation in algebraic and combinatorial structures
  516.         such as groups, rings, fields, modules and graphs.
  517.         Available for: SUN 3, SUN 4, IBM running AIX or VM, DEC VMS, others
  518.         Contact: Computational Algebra Group
  519.         University of Sydney
  520.         NSW 2006
  521.         Australia
  522.         Phone:  (61) (02) 692 3338
  523.         Fax: (61) (02) 692 4534
  524.         cayley@maths.su.oz.au
  525.  
  526.  
  527.  
  528. 7Q:  Let P be a property about the Fields Medal. Is P(x) true?
  529.  
  530. A:  There are a few gaps in the list. If you know any of the
  531.     missing information (or if you notice any mistakes), 
  532.     please send me e-mail.
  533.  
  534. Year Name               Birthplace              Age Institution
  535. ---- ----               ----------              --- -----------
  536. 1936 Ahlfors, Lars      Helsinki       Finland   29 Harvard U         USA
  537. 1936 Douglas, Jesse     New York NY    USA       39 MIT               USA
  538. 1950 Schwartz, Laurent  Paris          France    35 U of Nancy        France
  539. 1950 Selberg, Atle      Langesund      Norway    33 Adv.Std.Princeton USA 
  540. 1954 Kodaira, Kunihiko  Tokyo          Japan     39 Princeton U       USA
  541. 1954 Serre, Jean-Pierre Bages          France    27 College de France France
  542. 1958 Roth, Klaus        Breslau        Germany   32 U of London       UK
  543. 1958 Thom, Rene         Montbeliard    France    35 U of Strasbourg   France
  544. 1962 Hormander, Lars    Mjallby        Sweden    31 U of Stockholm    Sweden
  545. 1962 Milnor, John       Orange NJ      USA       31 Princeton U       USA
  546. 1966 Atiyah, Michael    London         UK        37 Oxford U          UK
  547. 1966 Cohen, Paul        Long Branch NJ USA       32 Stanford U        USA
  548. 1966 Grothendieck, Alexander Berlin    Germany   38 U of Paris        France
  549. 1966 Smale, Stephen     Flint MI       USA       36 UC Berkeley       USA
  550. 1970 Baker, Alan        London         UK        31 Cambridge U       UK
  551. 1970 Hironaka, Heisuke  Yamaguchi-ken  Japan     39 Harvard U         USA
  552. 1970 Novikov, Serge     Gorki          USSR      32 Moscow U          USSR
  553. 1970 Thompson, John     Ottawa KA      USA       37 U of Chicago      USA
  554. 1974 Bombieri, Enrico   Milan          Italy     33 U of Pisa         Italy
  555. 1974 Mumford, David     Worth, Sussex  UK        37 Harvard U         USA
  556. 1978 Deligne, Pierre    Brussels       Belgium   33 IHES              France
  557. 1978 Fefferman, Charles Washington DC  USA       29 Princeton U       USA
  558. 1978 Margulis, Gregori  Moscow         USSR      32 InstPrblmInfTrans USSR
  559. 1978 Quillen, Daniel    Orange NJ      USA       38 MIT               USA
  560. 1982 Connes, Alain      Draguignan     France    35 IHES              France
  561. 1982 Thurston, William  Washington DC  USA       35 Princeton U       USA
  562. 1982 Yau, Shing-Tung    Kwuntung       China     33 IAS               USA
  563. 1986 Donaldson, Simon   Cambridge      UK        27 Oxford U          UK
  564. 1986 Faltings, Gerd     1954           Germany   32 Princeton U       USA
  565. 1986 Freedman, Michael  Los Angeles CA USA       35 UC San Diego      USA
  566. 1990 Drinfeld, Vladimir Kharkov        USSR      36 Phys.Inst.Kharkov USSR
  567. 1990 Jones, Vaughan     Gisborne       N Zealand 38 UC Berkeley       USA
  568. 1990 Mori, Shigefumi    Nagoya         Japan     39 U of Kyoto?       Japan
  569. 1990 Witten, Edward     Baltimore      USA       38 Princeton U/IAS   USA
  570.  
  571. References :
  572.  
  573. International Mathematical Congresses, An Illustrated History 1893-1986,
  574. Revised Edition, Including 1986, by Donald J.Alberts, G. L. Alexanderson 
  575. and Constance Reid, Springer Verlag, 1987.
  576.  
  577. Tropp, Henry S., ``The origins and history of the Fields Medal,''
  578. Historia Mathematica, 3(1976), 167-181.  
  579.  
  580.  
  581. 8Q:  What is 0^0 ?
  582.  
  583. A:  According to some Calculus textbooks, 0^0 is an "indeterminate
  584.     form". When evaluating a limit of the form 0^0, then you need
  585.     to know that limits of that form are called "indeterminate forms",
  586.     and that you need to use a special technique such as L'Hopital's
  587.     rule to evaluate them. Otherwise, 0^0=1 seems to be the most
  588.     useful choice for 0^0. This convention allows us to extend 
  589.     definitions in different areas of mathematics that otherwise would
  590.     require treating 0 as a special case. Notice that 0^0 is a
  591.     discontinuity of the function x^y. 
  592.    
  593.     Rotando & Korn show that if f and g are real functions that vanish
  594.     at the origin and are _analytic_ at 0 (infinitely differentiable is
  595.     not sufficient), then f(x)^g(x) approaches 1 as x approaches 0 from
  596.     the right.
  597.  
  598.     From Concrete Mathematics p.162 (R. Graham, D. Knuth, O. Patashnik):
  599.  
  600.     "Some textbooks leave the quantity 0^0 undefined, because the
  601.     functions x^0 and 0^x have different limiting values when x 
  602.     decreases to 0. But this is a mistake. We must define
  603.  
  604.        x^0 = 1 for all x,
  605.  
  606.     if the binomial theorem is to be valid when x=0, y=0, and/or x=-y.
  607.     The theorem is too important to be arbitrarily restricted! By
  608.     contrast, the function 0^x is quite unimportant." 
  609.  
  610.     Published by Addison-Wesley, 2nd printing Dec, 1988.
  611.  
  612.     References:
  613.  
  614.     H. E. Vaughan, The expression '0^0', Mathematics Teacher 63 (1970),
  615.     pp.111-112.
  616.  
  617.     Louis M. Rotando & Henry Korn, "The Indeterminate Form 0^0",
  618.     Mathematics Magazine, Vol. 50, No. 1 (January 1977), pp. 41-42.
  619.  
  620.     L. J. Paige, A note on indeterminate forms, American Mathematical 
  621.     Monthly, 61 (1954), 189-190; reprinted in the Mathematical 
  622.     Association of America's 1969 volume, Selected Papers on Calculus,
  623.     pp. 210-211.
  624.  
  625.  
  626.  
  627. 9Q:  Why is 0.9999... = 1?
  628.  
  629. A:  In modern mathematics, the string of symbols "0.9999..." is
  630.     understood to be a shorthand for "the infinite sum  9/10 + 9/100
  631.     + 9/1000 + ...." This in turn is shorthand for "the limit of the
  632.     sequence of real numbers 9/10, 9/10 + 9/100, 9/10 + 9/100 + 9/1000,
  633.     ..."  Using the well-known epsilon-delta definition of limit, one
  634.     can easily show that this limit is 1.  The statement that 
  635.     0.9999...  = 1 is simply an abbreviation of this fact.
  636.  
  637.                     oo              m
  638.                    ---   9         ---   9
  639.         0.999... = >   ---- = lim  >   ----
  640.                    --- 10^n  m->oo --- 10^n
  641.                    n=1             n=1
  642.         Choose epsilon > 0. Suppose delta = 1/-log_10 epsilon, thus
  643.         epsilon = 10^(-1/delta). For every m>1/delta we have that
  644.  
  645.         |  m           |
  646.         | ---   9      |     1          1
  647.         | >   ---- - 1 | = ---- < ------------ = epsilon
  648.         | --- 10^n     |   10^m   10^(1/delta)
  649.         | n=1          |
  650.  
  651.         So by the (epsilon-delta) definition of the limit we have
  652.                m
  653.               ---   9
  654.          lim  >   ---- = 1
  655.         m->oo --- 10^n
  656.               n=1
  657.  
  658.  
  659.     An *informal* argument could be given by noticing that the following
  660.     sequence of "natural" operations has as a consequence 1 = 0.9999....
  661.     Therefore it's "natural" to assume 1 = 0.9999.....
  662.  
  663.              x = 0.99999....
  664.            10x = 9.99999....
  665.        10x - x = 9 
  666.             9x = 9                
  667.              x = 1
  668.     Thus
  669.              1 = 0.99999....
  670.  
  671.     References:
  672.  
  673.     E. Hewitt & K. Stromberg, Real and Abstract Analysis, 
  674.     Springer-Verlag, Berlin, 1965.
  675.  
  676.     W. Rudin, Principles of Mathematical Analysis, McGraw-Hill, 1976.
  677.  
  678.  
  679.  
  680. 10Q:  Where I can get pi up to a few hundred thousand digits of pi? 
  681.     Does anyone have an algorithm to compute pi to those zillion 
  682.     decimal places?
  683.  
  684.  
  685. A:  MAPLE or MATHEMATICA can give you 10,000 digits of Pi in a blink,
  686.     and they can compute another 20,000-500,000 overnight (range depends
  687.     on hardware platform).
  688.  
  689.     It is possible to retrieve 1.25+ million digits of pi via anonymous
  690.     ftp from the site wuarchive.wustl.edu, in the files pi.doc.Z and
  691.     pi.dat.Z which reside in subdirectory doc/misc/pi.
  692.  
  693.     New York's Chudnovsky brothers have computed 2 billion digits of pi
  694.     on a homebrew computer.
  695.  
  696.     References :
  697.     (This is a short version for a more comprehensive list contact
  698.     Juhana Kouhia at jk87377@cc.tut.fi)
  699.  
  700.     J. M. Borwein, P. B. Borwein, and D. H. Bailey, "Ramanujan,
  701.     Modular Equations, and Approximations to Pi", American Mathematical
  702.     Monthly, vol. 96, no. 3 (March 1989), p. 201 - 220.
  703.  
  704.     P. Beckman
  705.     A history of pi
  706.     Golem Press, CO, 1971 (fourth edition 1977)
  707.  
  708.     J.M. Borwein and P.B. Borwein
  709.     The arithmetic-geometric mean and fast computation of elementary
  710.     functions
  711.     SIAM Review, Vol. 26, 1984, pp. 351-366
  712.  
  713.     J.M. Borwein and P.B. Borwein
  714.     More quadratically converging algorithms for pi
  715.     Mathematics of Computation, Vol. 46, 1986, pp. 247-253
  716.  
  717.     J.M. Borwein and P.B. Borwein
  718.     Pi and the AGM - a study in analytic number theory and
  719.     computational complexity
  720.     Wiley, New York, 1987
  721.  
  722.     Shlomo Breuer and Gideon Zwas
  723.     Mathematical-educational aspects of the computation of pi
  724.     Int. J. Math. Educ. Sci. Technol., Vol. 15, No. 2, 1984,
  725.     pp. 231-244
  726.  
  727.     Y. Kanada and Y. Tamura
  728.     Calculation of pi to 10,013,395 decimal places based on the
  729.     Gauss-Legendre algorithm and Gauss arctangent relation
  730.     Computer Centre, University of Tokyo, 1983
  731.  
  732.     Morris Newman and Daniel Shanks
  733.     On a sequence arising in series for pi
  734.     Mathematics of computation, Vol. 42, No. 165, Jan 1984,
  735.     pp. 199-217
  736.  
  737.     E. Salamin
  738.     Computation of pi using arithmetic-geometric mean
  739.     Mathematics of Computation, Vol. 30, 1976, pp. 565-570
  740.  
  741.     D. Shanks and J.W. Wrench, Jr.
  742.     Calculation of pi to 100,000 decimals
  743.     Mathematics of Computation, Vol. 16, 1962, pp. 76-99
  744.  
  745.     Daniel Shanks
  746.     Dihedral quartic approximations and series for pi
  747.     J. Number Theory, Vol. 14, 1982, pp.397-423
  748.  
  749.     David Singmaster
  750.     The legal values of pi
  751.     The Mathematical Intelligencer, Vol. 7, No. 2, 1985
  752.  
  753.     Stan Wagon
  754.     Is pi normal?
  755.     The Mathematical Intelligencer, Vol. 7, No. 3, 1985
  756.  
  757.     J.W. Wrench, Jr.
  758.     The evolution of extended decimal approximations to pi
  759.     The Mathematics Teacher, Vol. 53, 1960, pp. 644-650
  760.  
  761.  
  762.  
  763.  
  764. 11Q:  There are three doors, and there is a car hidden behind one
  765.     of them, Master Mind and other games ..
  766.  
  767. A:  Read frequently asked questions from rec.puzzles, where the
  768.     problem is solved and carefully explained. (The Monty
  769.     Hall problem). MANY OTHER "MATHEMATICAL" GAMES ARE EXPLAINED
  770.     IN THE REC.PUZZLES FAQ. READ IT BEFORE ASKING IN SCI.MATH.
  771.  
  772.     Your chance of winning is 2/3 if you switch and 1/3 if you don't.
  773.     For a full explanation from the frequently asked questions list
  774.     for rec.puzzles, send to the address archive-request@questrel.com
  775.     an email message consisting of the text
  776.  
  777.                send switch
  778.  
  779.  
  780.     Also any other FAQ list can be obtained through anonymous ftp from
  781.     rtfm.mit.edu.
  782.  
  783.     References
  784.     
  785.     American Mathematical Monthly, January 1992.
  786.  
  787.  
  788.     For the game of Master Mind it has been proven that no more than
  789.     five moves are required in the worst case. For references look at
  790.  
  791.     One such algorithm was published in the Journal of Recreational
  792.     Mathematics; in '70 or '71 (I think), which always solved the
  793.     4 peg problem in 5 moves. Knuth later published an algorithm which
  794.     solves the problem in a shorter # of moves - on average - but can
  795.     take six guesses on certain combinations.
  796.  
  797.  
  798.  
  799.     Donald E. Knuth, The Computer as Master Mind, J. Recreational Mathematics
  800.     9 (1976-77), 1-6.
  801.  
  802.  
  803.  
  804. 12Q:  What is the formula for the "Surface Area" of a sphere in
  805.     Euclidean N-Space.  That is, of course, the volume of the N-1
  806.     solid which comprises the boundary of an N-Sphere.  
  807.  
  808. A:  The volume of a ball is the easiest formula to remember:  It's r^N
  809.     times pi^(N/2)/(N/2)!.  The only hard part is taking the factorial
  810.     of a half-integer.  The real definition is that x! = Gamma(x+1), but
  811.     if you want a formula, it's:
  812.  
  813.     (1/2+n)! = sqrt(pi)*(2n+2)!/(n+1)!/4^(n+1)
  814.  
  815.     To get the surface area, you just differentiate to get
  816.     N*pi^(N/2)/(N/2)!*r^(N-1).
  817.  
  818.     There is a clever way to obtain this formula using Gaussian
  819.     integrals. First, we note that the integral over the line of
  820.     e^(-x^2) is sqrt(pi).  Therefore the integral over N-space of
  821.     e^(-x_1^2-x_2^2-...-x_N^2) is sqrt(pi)^n.  Now we change to
  822.     spherical coordinates.  We get the integral from 0 to infinity 
  823.     of V*r^(N-1)*e^(-r^2), where V is the surface volume of a sphere.
  824.     Integrate by parts repeatedly to get the desired formula.
  825.  
  826. 13Q:  Does anyone know a name (or a closed form) for
  827.   
  828.       f(x)^f(x)=x
  829.  
  830.  
  831.     Solving for f one finds a "continued fraction"-like answer
  832.  
  833.  
  834.                f(x) = log x
  835.                       -----
  836.                       log (log x
  837.                           ------
  838.                               ...........
  839.  
  840. A:  This question has been repeated here from time to time over the 
  841.     years, and no one seems to have heard of any published work on it,
  842.     nor a published name for it (D. Merrit proposes "lx" due to its
  843.     (very) faint resemblance to log). It's not an analytic function.
  844.  
  845.     The "continued fraction" form for its numeric solution is highly 
  846.     unstable in the region of its minimum at 1/e (because the graph is
  847.     quite flat there yet logarithmic approximation oscillates wildly),
  848.     although it converges fairly quickly elsewhere. To compute its value
  849.     near 1/e, use the bisection method which gives good results. Bisection
  850.     in other regions converges much more slowly than the "logarithmic 
  851.     continued fraction" form, so a hybrid of the two seems suitable.
  852.     Note that it's dual valued for the reals (and many valued complex
  853.     for negative reals).
  854.  
  855.     A similar function is a "built-in" function in MAPLE called W(x).
  856.     MAPLE considers a solution in terms of W(x) as a closed form (like
  857.     the erf function). W is defined as W(x)*exp(W(x))=x.
  858.  
  859.     An extensive treatise on the known facts of Lambert's W function 
  860.     is available for anonymous ftp at daisy.uwaterloo.ca in the 
  861.     maple/5.2/doc/LambertW.ps.
  862.  
  863. 14Q:  The existence of a projective plane of order 10 has long been
  864.     an outstanding problem in discrete mathematics and finite geometry.
  865.  
  866. A:  More precisely, the question is: is it possible to define 111 sets
  867.     (lines) of 11 points each such that:
  868.     for any pair of points there is precisely one line containing them
  869.     both and for any pair of lines there is only one point common to
  870.     them both.
  871.     Analogous questions with n^2 + n + 1 and n + 1 instead of 111 and 11
  872.     have been positively answered only in case n is a prime power.
  873.     For n=6 it is not possible, more generally if n is congruent to 1
  874.     or 2 mod 4 and can not be written as a sum of two squares, then an
  875.     FPP of order n does not exist.  The n=10 case has been settled as
  876.     not possible either by Clement Lam. See Am. Math. Monthly,
  877.     recent issue. As the "proof" took several years of computer search
  878.     (the equivalent of 2000 hours on a Cray-1) it can be called the most
  879.     time-intensive computer assisted single proof.
  880.     The final steps were ready in January 1989.
  881.  
  882.     References
  883.  
  884.     R. H. Bruck and H. J. Ryser, "The nonexistence of certain finite
  885.     projective planes," Canadian Journal of Mathematics, vol. 1 (1949),
  886.     pp 88-93.
  887.  
  888.  
  889.  
  890. 15Q:  Is there a formula to determine the day of the week, given
  891.     the month, day and year? 
  892.  
  893. A:  Here is the standard method.
  894.  
  895.      A. Take the last two digits of the year.
  896.      B. Divide by 4, discarding any fraction.
  897.      C. Add the day of the month.
  898.      D. Add the month's key value: JFM AMJ JAS OND
  899.                                    144 025 036 146
  900.      E. Subtract 1 for January or February of a leap year.
  901.      F. For a Gregorian date, add 0 for 1900's, 6 for 2000's, 4 for 1700's, 2
  902.            for 1800's; for other years, add or subtract multiples of 400.
  903.      G. For a Julian date, add 1 for 1700's, and 1 for every additional
  904.       century you go back.
  905.      H. Add the last two digits of the year.
  906.  
  907.     Now take the remainder when you divide by 7; 1 is Sunday, the first day
  908.     of the week, 2 is Monday, and so on.
  909.  
  910.     Another formula is:
  911.  
  912.     W == k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]     mod 7
  913.        where [] denotes the integer floor function (round down),
  914.        k is day (1 to 31)
  915.        m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
  916.                      Treat Jan & Feb as months of the preceding year
  917.        C is century ( 1987 has C = 19)
  918.        Y is year    ( 1987 has Y = 87 except Y = 86 for jan & feb)
  919.        W is week day (0 = Sunday, ..., 6 = Saturday)
  920.  
  921.     This formula is good for the Gregorian calendar
  922.     (introduced 1582 in parts of Europe, adopted in 1752 in Great Britain
  923.     and its colonies, and on various dates in other countries).
  924.  
  925.     It handles century & 400 year corrections, but there is still a 
  926.     3 day / 10,000 year error which the Gregorian calendar does not take.
  927.     into account.  At some time such a correction will have to be 
  928.     done but your software will probably not last that long :-)   !
  929.  
  930.  
  931.     References:
  932.  
  933.     Winning Ways  by Conway, Guy, Berlekamp is supposed to have it.
  934.  
  935.     Martin Gardner in "Mathematical Carnival".
  936.  
  937.     Michael Keith and Tom Craver, "The Ultimate Perpetual Calendar?",
  938.     Journal of Recreational Mathematics, 22:4, pp. 280-282, 1990.
  939.     
  940.     K. Rosen, "Elementary Number Theory",  p. 156.
  941.  
  942.  
  943.  
  944. 16Q:  What is the Axiom of Choice?  Why is it important? Why some articles
  945.     say "such and such is provable, if you accept the axiom of choice."?
  946.     What are the arguments for and against the axiom of choice?  
  947.  
  948.  
  949. A:  There are several equivalent formulations:
  950.  
  951.     -The Cartesian product of nonempty sets is nonempty, even
  952.     if the product is of an infinite family of sets.
  953.  
  954.     -Given any set S of mutually disjoint nonempty sets, there is a set C
  955.     containing a single member from each element of S.  C can thus be
  956.     thought of as the result of "choosing" a representative from each
  957.     set in S. Hence the name. 
  958.  
  959.     >Why is it important? 
  960.  
  961.     All kinds of important theorems in analysis require it.  Tychonoff's
  962.     theorem and the Hahn-Banach theorem are examples. Indeed,
  963.     Tychonoff's theorem is equivalent to AC. Similarly, AC is equivalent
  964.     to the thesis that every set can be well-ordered.  Zermelo's first
  965.     proof of this in 1904 I believe was the first proof in which AC was
  966.     made explicit.  AC is especially handy for doing infinite cardinal
  967.     arithmetic, as without it the most you get is a *partial* ordering
  968.     on the cardinal numbers.  It also enables you to prove such 
  969.     interesting general facts as that n^2 = n for all infinite cardinal 
  970.     numbers.
  971.  
  972.     > What are the arguments for and against the axiom of choice?
  973.  
  974.     The axiom of choice is independent of the other axioms of set theory
  975.     and can be assumed or not as one chooses.
  976.  
  977.     (For) All ordinary mathematics uses it.
  978.  
  979.     There are a number of arguments for AC, ranging from a priori to 
  980.     pragmatic.  The pragmatic argument (Zermelo's original approach) is
  981.     that it allows you to do a lot of interesting mathematics.  The more
  982.     conceptual argument derives from the "iterative" conception of set
  983.     according to which sets are "built up" in layers, each layer consisting
  984.     of all possible sets that can be constructed out of elements in the
  985.     previous layers.  (The building up is of course metaphorical, and is
  986.     suggested only by the idea of sets in some sense consisting of their 
  987.     members; you can't have a set of things without the things it's a set
  988.     of).  If then we consider the first layer containing a given set S of
  989.     pairwise disjoint nonempty sets, the argument runs, all the elements 
  990.     of all the sets in S must exist at previous levels "below" the level
  991.     of S.  But then since each new level contains *all* the sets that can
  992.     be formed from stuff in previous levels, it must be that at least by
  993.     S's level all possible choice sets have already been *formed*. This
  994.     is more in the spirit of Zermelo's later views (c. 1930). 
  995.  
  996.     (Against) It has some supposedly counterintuitive consequences,
  997.     such as the Banach-Tarski paradox. (See next question)
  998.  
  999.     Arguments against AC typically target its nonconstructive character:
  1000.     it is a cheat because it conjures up a set without providing any
  1001.     sort of *procedure* for its construction--note that no *method* is
  1002.     assumed for picking out the members of a choice set.  It is thus the
  1003.     platonic axiom par excellence, boldly asserting that a given set
  1004.     will always exist under certain circumstances in utter disregard of
  1005.     our ability to conceive or construct it.  The axiom thus can be seen
  1006.     as marking a divide between two opposing camps in the philosophy of
  1007.     mathematics:  those for whom mathematics is essentially tied to our
  1008.     conceptual capacities, and hence is something we in some sense
  1009.     *create*, and those for whom mathematics is independent of any such
  1010.     capacities and hence is something we *discover*.  AC is thus of 
  1011.     philosophical as well as mathematical significance.
  1012.  
  1013.  
  1014.     It should be noted that some interesting mathematics has come out of an
  1015.     incompatible axiom, the Axiom of Determinacy (AD).  AD asserts that
  1016.     any two-person game without ties has a winning strategy for the first or
  1017.     second player.  For finite games, this is an easy theorem; for infinite
  1018.     games with duration less than \omega and move chosen from a countable set,
  1019.     you can prove the existence of a counter-example using AC.  Jech's book
  1020.     "The Axiom of Choice" has a discussion.  
  1021.  
  1022.     An example of such a game goes as follows.  
  1023.  
  1024.        Choose in advance a set of infinite sequences of integers; call it A.
  1025.        Then I pick an integer, then you do, then I do, and so on forever 
  1026.        (i.e. length \omega).  When we're done, if the sequence of integers
  1027.        we've chosen is in A, I win; otherwise you win.  AD says that one of
  1028.        us must have a winning strategy.  Of course the strategy, and which
  1029.        of us has it, will depend upon A.
  1030.  
  1031.  
  1032.     From a philosophical/intuitive/pedagogical standpoint, I think Bertrand
  1033.     Russell's shoe/sock analogy has a lot to recommend it.  Suppose you have an
  1034.     infinite collection of pairs of shoes.  You want to form a set with one
  1035.     shoe from each pair.  AC is not necessary, since you can define the set as
  1036.     "the set of all left shoes". (Technically, we're using the axiom of
  1037.     replacement, one of the basic axioms of Zermelo-Fraenkel (ZF) set theory.)
  1038.     If instead you want to form a set containing one sock from each pair of an
  1039.     infinite collection of pairs of socks, you now need AC.
  1040.  
  1041.  
  1042.     References:
  1043.  
  1044.     Maddy, "Believing the Axioms, I", J. Symb. Logic, v. 53, no. 2, June 1988,
  1045.     pp. 490-500, and "Believing the Axioms II" in v.53, no. 3.  
  1046.  
  1047.     Gregory H. Moore, Zermelo's Axiom of Choice, New York, Springer-Verlag,
  1048.     1982.
  1049.  
  1050.     H. Rubin and J. E. Rubin, Equivalents of the Axiom of Choice II,
  1051.     North-Holland/Elsevier Science, 1985.
  1052.  
  1053.     A. Fraenkel, Y.  Bar-Hillel, and A. Levy, Foundations of Set Theory, 
  1054.     Amsterdam, North-Holland, 1984 (2nd edition, 2nd printing), pp. 53-86.
  1055.  
  1056.  
  1057.  
  1058. 17Q:  Cutting a sphere into pieces of larger volume. Is it possible
  1059.     to cut a sphere into a finite number of pieces and reassemble 
  1060.     into a solid of twice the volume?
  1061.  
  1062. A:  This question has many variants and it is best answered explicitly.
  1063.     Given two polygons of the same area, is it always possible to
  1064.     dissect one into a finite number of pieces which can be reassembled
  1065.     into a replica of the other?
  1066.  
  1067.     Dissection theory is extensive.  In such questions one needs to
  1068.     specify
  1069.  
  1070.      (A) what a "piece" is,  (polygon?  Topological disk?  Borel-set? 
  1071.          Lebesgue-measurable set?  Arbitrary?)
  1072.  
  1073.      (B) how many pieces are permitted (finitely many? countably? uncountably?)
  1074.  
  1075.      (C) what motions are allowed in "reassembling" (translations?
  1076.          rotations?  orientation-reversing maps?  isometries?  
  1077.          affine maps?  homotheties?  arbitrary continuous images?  etc.)
  1078.  
  1079.      (D) how the pieces are permitted to be glued together.  The
  1080.          simplest notion is that they must be disjoint.  If the pieces
  1081.          are polygons [or any piece with a nice boundary] you can permit
  1082.          them to be glued along their boundaries, ie the interiors of the
  1083.          pieces disjoint, and their union is the desired figure.
  1084.  
  1085.  
  1086.     Some dissection results
  1087.  
  1088.      1) We are permitted to cut into FINITELY MANY polygons, to TRANSLATE
  1089.         and ROTATE the pieces, and to glue ALONG BOUNDARIES;
  1090.         then Yes, any two equal-area polygons are equi-decomposable.
  1091.  
  1092.         This theorem was proven by Bolyai and Gerwien independently, and has
  1093.         undoubtedly been independently rediscovered many times.  I would not
  1094.         be surprised if the Greeks knew this.
  1095.  
  1096.         The Hadwiger-Glur theorem implies that any two equal-area polygons are
  1097.         equi-decomposable using only TRANSLATIONS and ROTATIONS BY 180
  1098.         DEGREES. 
  1099.  
  1100.      2) THM (Hadwiger-Glur, 1951) Two equal-area polygons P,Q are
  1101.         equi-decomposable by TRANSLATIONS only, iff we have equality of these
  1102.         two functions:     PHI_P() = PHI_Q()
  1103.         Here, for each direction v (ie, each vector on the unit circle in the
  1104.         plane), let PHI_P(v) be the sum of the lengths of the edges of P which
  1105.         are perpendicular to v, where for such an edge, its length is positive
  1106.         if v is an outward normal to the edge and is negative if v is an 
  1107.         inward normal to the edge.
  1108.  
  1109.  
  1110.      3) In dimension 3, the famous "Hilbert's third problem" is:
  1111.      
  1112.        "If P and Q are two polyhedra of equal volume, are they
  1113.         equi-decomposable by means of translations and rotations, by
  1114.         cutting into finitely many sub-polyhedra, and gluing along
  1115.         boundaries?" 
  1116.  
  1117.         The answer is "NO" and was proven by Dehn in 1900, just a few months
  1118.         after the problem was posed. (Ueber raumgleiche polyeder, Goettinger 
  1119.         Nachrichten 1900, 345-354). It was the first of Hilbert's problems
  1120.         to be solved. The proof is nontrivial but does *not* use the axiom 
  1121.         of choice.
  1122.  
  1123.         "Hilbert's Third Problem", by V.G.Boltianskii, Wiley 1978.
  1124.  
  1125.  
  1126.      4) Using the axiom of choice on non-countable sets, you can prove
  1127.         that a solid sphere can be dissected into a finite number of
  1128.         pieces that can be reassembled to two solid spheres, each of
  1129.         same volume of the original. No more than nine pieces are needed.
  1130.  
  1131.         The minimum possible number of pieces is FIVE.  (It's quite easy 
  1132.         to show that four will not suffice).  There is a particular
  1133.         dissection in which one of the five pieces is the single center 
  1134.         point of the original sphere, and the other four pieces  A, A',
  1135.         B, B'  are such that A is congruent to A' and B is congruent to B'.
  1136.         [See Wagon's book].
  1137.  
  1138.         This construction is known as the "Banach-Tarski" paradox or the 
  1139.         "Banach-Tarski-Hausdorff" paradox (Hausdorff did an early version of
  1140.         it).  The "pieces" here are non-measurable sets, and they are
  1141.         assembled *disjointly* (they are not glued together along a boundary,
  1142.         unlike the situation in Bolyai's thm.)
  1143.          An excellent book on Banach-Tarski is:
  1144.  
  1145.         "The Banach-Tarski Paradox", by Stan Wagon, 1985, Cambridge
  1146.         University Press.
  1147.  
  1148.          Also read in the Mathematical Intelligencer an article on
  1149.         the Banach-Tarski Paradox.
  1150.  
  1151.         The pieces are not (Lebesgue) measurable, since measure is preserved
  1152.         by rigid motion. Since the pieces are non-measurable, they do not
  1153.         have reasonable boundaries. For example, it is likely that each piece's
  1154.         topological-boundary is the entire ball.
  1155.  
  1156.         The full Banach-Tarski paradox is stronger than just doubling the
  1157.         ball.  It states:
  1158.  
  1159.      5) Any two bounded subsets (of 3-space) with non-empty interior, are
  1160.         equi-decomposable by translations and rotations.
  1161.  
  1162.         This is usually illustrated by observing that a pea can be cut up
  1163.         into finitely pieces and reassembled into the Earth.
  1164.  
  1165.         The easiest decomposition "paradox" was observed first by Hausdorff:
  1166.  
  1167.      6) The unit interval can be cut up into COUNTABLY many pieces which,
  1168.         by *translation* only, can be reassembled into the interval of
  1169.         length 2.
  1170.  
  1171.         This result is, nowadays, trivial, and is the standard example of a
  1172.         non-measurable set, taught in a beginning graduate class on measure
  1173.         theory.
  1174.  
  1175.  
  1176.         References:
  1177.  
  1178.         In addition to Wagon's book above, Boltyanskii has written at least
  1179.         two works on this subject.  An elementary one is:
  1180.  
  1181.           "Equivalent and equidecomposable figures"
  1182.  
  1183.         in Topics in Mathematics published by D.C. HEATH AND CO., Boston.  It
  1184.         is a translation from the 1956 work in Russian.   
  1185.  
  1186.           Also, the article "Scissor Congruence" by Dubins, Hirsch and ?,
  1187.         which appeared about 20 years ago in the Math Monthly, has a pretty
  1188.         theorem on decomposition by Jordan arcs.
  1189.  
  1190.  
  1191.         ``Banach and Tarski had hoped that the physical absurdity of this
  1192.         theorem would encourage mathematicians to discard AC. They were 
  1193.         dismayed when the response of the math community was `Isn't AC great?
  1194.         How else could we get such counterintuitive results?' ''
  1195.  
  1196.  
  1197. 18Q:   Is there a theory of quaternionic analytic functions, that is, a four-
  1198.      dimensional analog to the theory of complex analytic functions?
  1199.     
  1200. A.   Yes.   This was developed in the 1930s by the mathematician
  1201.      Fueter.   It is based on a generalization of the Cauchy-Riemann
  1202.      equations, since the possible alternatives of power series expansions
  1203.      or quaternion differentiability do not produce useful theories.
  1204.      A number of useful integral theorems follow from the theory.
  1205.      Sudbery provides an excellent review.  Deavours covers some of the same
  1206.      material less thoroughly.   Brackx discusses a further generalization
  1207.      to arbitrary Clifford algebras.
  1208.  
  1209.  
  1210.       Anthony Sudbery, Quaternionic Analysis, Proc. Camb. Phil. Soc.,
  1211.       vol. 85, pp 199-225, 1979.
  1212.  
  1213.       Cipher A. Deavours, The Quaternion Calculus, Am. Math. Monthly,
  1214.       vol. 80, pp 995-1008, 1973.
  1215.  
  1216.       F. Brackx and R. Delanghe and F. Sommen, Clifford analysis,
  1217.       Pitman, 1983.
  1218.  
  1219.  
  1220. 19Q:  What is the Erdos Number?
  1221.  
  1222.      Form an undirected graph where the vertices are academics, and an
  1223.      edge connects academic X to academic Y if X has written a paper
  1224.      with Y.  The Erdos number of X is the length of the shortest path
  1225.      in this graph connecting X with Erdos.
  1226.  
  1227.      What is the Erdos Number of X ? for a few selected X in {Math,physics}
  1228.  
  1229.      Erdos has Erdos number 0.  Co-authors of Erdos have Erdos number 1.
  1230.      Einstein has Erdos number 2, since he wrote a paper with Ernst Straus,
  1231.      and Straus wrote many papers with Erdos.
  1232.  
  1233.      Why people care about it?
  1234.  
  1235.      Nobody seems to have a reasonable answer...
  1236.  
  1237.      Who is Paul Erdos? 
  1238.  
  1239.      Paul Erdos is an Hungarian mathematician, he obtained his PhD
  1240.      from the University of Manchester and has spent most of his 
  1241.      efforts tackling "small" problems and conjectures related to
  1242.      graph theory, combinatorics, geometry and number theory.
  1243.  
  1244.      He is one of the most prolific publishers of papers; and is
  1245.      also and indefatigable traveller.
  1246.  
  1247.  
  1248.      References:
  1249.  
  1250.       Caspar Goffman, And what is your Erdos number?, American Mathematical
  1251.       Monthly v. 76 (1969), p. 791.
  1252.  
  1253.  
  1254. 20Q:  Does there exist a number that is perfect and odd?
  1255.  
  1256.      A given number is perfect if it is equal to the sum of all its proper 
  1257.      divisors. This question was first posed by Euclid in ancient Greece.
  1258.      This question is still open.  Euler proved that if  N  is an odd
  1259.      perfect number, then in the prime power decomposition of N, exactly 
  1260.      one exponent is congruent to 1 mod 4 and all the other exponents are
  1261.      even. Furthermore, the prime occurring to an odd power must itself be
  1262.      congruent to 1 mod 4.  A sketch of the proof appears in Exercise 87,
  1263.      page 203 of Underwood Dudley's Elementary Number Theory, 2nd ed.  
  1264.      It has been shown that there are no odd perfect numbers < 10^300.
  1265.  
  1266.  
  1267.  
  1268. 21Q.- Why is there no Nobel in mathematics? #
  1269.  
  1270.      Nobel prizes were created by the will of Alfred Nobel, a notable
  1271.      swedish chemist.
  1272.  
  1273.      One of the most common --and unfounded-- reasons as to why Nobel
  1274.      decided against a Nobel prize in math is that [a woman he proposed
  1275.      to/his wife/his mistress] [rejected him beacuse of/cheated him
  1276.      with] a famous mathematician. Gosta Mittag-Leffler is often claimed
  1277.      to be the guilty party.
  1278.      
  1279.      There is no historical evidence to support the story.
  1280.  
  1281.      For one, Mr. Nobel was never married.
  1282.  
  1283.      There are more credible reasons as to why there is no Nobel prize
  1284.      in math. Chiefly among them is simply the fact he didn't care much
  1285.      for mathematics, and that it was not considered a practical 
  1286.      science from which humanity could benefit (a chief purpose
  1287.      for creating the Nobel Foundation).
  1288.  
  1289.  
  1290.      Here are some relevant facts:
  1291.  
  1292.      1. Nobel never married, hence no ``wife''. (He did have a mistress,
  1293.      a Viennese woman named Sophie Hess.)
  1294.  
  1295.      2. Gosta Mittag-Leffler was an important mathematician in Sweden
  1296.      in the late 19th-early 20th century.  He was the founder of the
  1297.      journal Acta Mathematica, played an important role in helping the
  1298.      career of Sonya Kovalevskaya, and was eventually head of the
  1299.      Stockholm Hogskola, the precursor to Stockholms Universitet.
  1300.      However, it seems highly unlikely that he would have been a
  1301.      leading candidate for an early Nobel Prize in mathematics, had 
  1302.      there been one -- there were guys like Poincare and Hilbert around,
  1303.      after all.
  1304.  
  1305.      3.  There is no evidence that Mittag-Leffler had much contact with
  1306.      Alfred Nobel (who resided in Paris during the latter part of his
  1307.      life), still less that there was animosity between them for whatever
  1308.      reason.  To the contrary, towards the end of Nobel's life 
  1309.      Mittag-Leffler was engaged in ``diplomatic'' negotiations to try to
  1310.      persuade Nobel to designate a substantial part of his fortune to the
  1311.      Hogskola. It seems hardly likely that he would have undertaken this
  1312.      if there was prior bad blood between them.  Although initially Nobel
  1313.      seems to have intended to do this, eventually he came up with the
  1314.      Nobel Prize idea -- much to the disappointment of the Hogskola,
  1315.      not to mention Nobel's relatives and Fraulein Hess.
  1316.  
  1317.      According to the very interesting study by Elisabeth Crawford,
  1318.      ``The Beginnings of the Nobel Institution'', Cambridge Univ. Press,
  1319.      1984, pages 52-53:
  1320.  
  1321.      ``Although it is not known how those in responsible positions
  1322.      at the Hogskola came to believe that a *large* bequest was
  1323.      forthcoming, this indeed was the expectation, and the
  1324.      disappointment was keen when it was announced early in 1897 that
  1325.      the Hogskola had been left out of Nobel's final will in 1895.
  1326.      Recriminations followed, with both Pettersson and Arrhenius 
  1327.      [academic rivals of Mittag-Leffler in the administration of the
  1328.      Hogskola] letting it be known that Nobel's dislike for 
  1329.      Mittag-Leffler had brought about what Pettersson termed the
  1330.      `Nobel Flop'.  This is only of interest because it may have
  1331.      contributed to the myth that Nobel had planned to institute a prize
  1332.      in mathematics but had refrained because of his antipathy to
  1333.      Mittag-Leffler or --in another version of the same story-- because
  1334.      of their rivalry for the affections of a woman...."
  1335.  
  1336.      4.  A final speculation concerning the psychological element.
  1337.      Would Nobel, sitting down to draw up his testament, presumably
  1338.      in a mood of great benevolence to mankind, have allowed a mere
  1339.      personal grudge to distort his idealistic plans for the monument
  1340.      he would leave behind?
  1341.      Nobel, an inventor and industrialist, did not create a prize in
  1342.      mathematics simply because he was not particularly interested
  1343.      in mathematics or theoretical science.  His will speaks of
  1344.      prizes for those ``inventions or discoveries'' of greatest
  1345.      practical benefit to mankind.  (Probably as a result of this 
  1346.      language, the physics prize has been awarded for experimental work
  1347.      much more often than for advances in theory.)
  1348.  
  1349.      However, the story of some rivalry over a woman is obviously
  1350.      much more amusing, and that's why it will probably continue to
  1351.      be repeated.
  1352.  
  1353.    
  1354.      References:
  1355.  
  1356.      Mathematical Intelligencer, vol. 7 (3), 1985, p. 74.
  1357.  
  1358.      Elisabeth Crawford, ``The Beginnings of the Nobel Institution'', 
  1359.      Cambridge Univ. Press, 1984.
  1360.  
  1361.  
  1362. 22Q.- General References and textbooks... #
  1363.  
  1364.      [a list of general references and most commonly used textbooks]
  1365.      [                                                             ]
  1366.       
  1367.  
  1368. 23Q.- Formula for prime numbers...
  1369.  
  1370.  
  1371.       Is there a polynomial which gives all the prime numbers?
  1372.  
  1373.       No, there is not. This is a simple exercise to prove.
  1374.  
  1375.       Is there a non-constant polynomial that only takes on prime values?
  1376.  
  1377.       It has been proved that no such polynomial exists.
  1378.  
  1379.       The proof is simple enough that an high school student could probably
  1380.       discover it.  See, for example, Ribenboim's book _The Book of Prime
  1381.       Number Records_.
  1382.  
  1383.       Note, however, by the work of Jones, Sato, Wada, and Wiens, there *is* a
  1384.       polynomial in 26 variables such that the set of primes coincides with
  1385.       the set of *positive* values taken by this polynomial.  See Ribenboim,
  1386.       pp. 147-150.
  1387.  
  1388.       But most people would object to the term "formula" restricted to mean
  1389.       polynomial.  Can we not use summation signs, factorial, and the floor
  1390.       function in our "formula"?  If so, then indeed, there *are* formulas
  1391.       for the prime numbers.  Some of them are listed below.
  1392.       
  1393.       If we can't, then exactly what operations do you allow and why?
  1394.       
  1395.       Indeed, as I have previously argued, a reasonable interpretation of
  1396.       the word "formula" is simply "Turing machine that halts on all inputs".
  1397.       Under this interpretation, there certainly are halting Turing machines
  1398.       which compute the n'th prime number.  However, nobody knows how to
  1399.       compute the n'th prime in time polynomial in log n.  That's still
  1400.       an open question.
  1401.       
  1402.       Herb Wilf has addressed the question, "What is a formula?" in his
  1403.       delightful article, "What is an answer?" which appeared in the
  1404.       American Mathematical Monthly, 89 (1982), 289-292.  He draws the
  1405.       distinction between "formula" and "good formula".  Anyone who claims
  1406.       "there is no formula for the prime numbers" should read this article.
  1407.       
  1408.       Here are just a few articles that discuss "formulas" for primes.  Almost
  1409.       all of these do *not* require computation of the primes "ahead of time".
  1410.       Most of them rely on standard mathematical functions such as summation,
  1411.       factorial, greatest integer function, etc.
  1412.  
  1413.  
  1414.             C. Isenkrahe, Math. Annalen  53 (1900), 42-44.
  1415.  
  1416.             W. H. Mills, Bull. Amer. Math. Soc. 53 (1947), 604.
  1417.  
  1418.             L. Moser, Math. Mag. 23 (1950), 163-164.
  1419.  
  1420.             E. M. Wright, Amer. Math. Monthly 58 (1951), 616-618.  (Correction,
  1421.       59 (1952), 99.)
  1422.  
  1423.             E. M. Wright, J. Lond. Math. Soc. 29 (1954), 63-71.
  1424.  
  1425.             B. R. Srinivasan, J. Indian Math. Soc. 25 (1961), 33-39.
  1426.  
  1427.             C. P. Willans, Math. Gazette 48 (1964), 413-415.
  1428.  
  1429.             V. C. Harris, Nordisk Mat. Tidskr. 17 (1969), 82.
  1430.  
  1431.             U. Dudley, Amer. Math. Monthly 76 (1969), 23-28.
  1432.             
  1433.             C. Vanden Eynden, Amer. Math. Monthly 79 (1972), 625.
  1434.  
  1435.             S. W. Golomb, Amer. Math. Monthly 81 (1974), 752-754.
  1436.  
  1437.  
  1438.             For more references see 
  1439.  
  1440.       J.O. Shallit, E. Bach, _Algorithmic Number Theory_ (to be published, 
  1441.       MIT Press).
  1442.  
  1443. 24Q.- Interest Rate...
  1444.  
  1445. >Below is the standard equation for calculating monthly payments (m)
  1446. >given the periodic interest rate (i), the principal (p), and the number
  1447. >of payments (n).  I need to rearrange the equation to solve for the
  1448. >periodic interest rate, given the other variables, but my math is sadly
  1449. >no longer up to it.
  1450. >
  1451. >If someone would be so kind as to solve for (i), or look up the
  1452. >equation, or whatever, and respond by email, I would be eternally
  1453. >grateful (well, a long time, anyway).  I ask for email since this site
  1454. >does not receive sci.math.  Thanks in advance.
  1455. >
  1456. >             i
  1457. >m = p * ------------
  1458. >                   -n
  1459. >        1 - (i + 1)
  1460. >
  1461. >
  1462.  
  1463.  
  1464. 25Q.- Euler's formula e^(i Pi) = - 1 ...
  1465.  
  1466. -1  = e^(ip)
  1467.  
  1468.  where i = sqrt(-1), p = pi ...
  1469.  
  1470.  
  1471.  
  1472. Copyright (C) 1993  A. Lopez-Ortiz
  1473.  
  1474. --------------------------------------------------------------------------
  1475. Questions and Answers _Compiled_ by:
  1476.  
  1477. Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
  1478. Department of Computer Science                      University of Waterloo
  1479. Waterloo, Ontario                                                   Canada
  1480. -- 
  1481. Alex Lopez-Ortiz                             alopez-o@neumann.UWaterloo.ca
  1482. Department of Computer Science                      University of Waterloo
  1483. Waterloo, Ontario                                                   Canada
  1484.