home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / SCIMATH2.FAQ < prev    next >
Text File  |  1996-08-02  |  35KB  |  819 lines

  1. SciMath FAQ
  2.  
  3.              Table of Contents
  4.              -----------------
  5.  1Q.- Fermat's Last Theorem, status of ..
  6.  2Q.- Values of Record Numbers
  7.  3Q.- Formula for prime numbers...
  8.  4Q.- Digits of Pi, computation and references
  9.  5Q.- Odd Perfect Number
  10.  6Q.- Computer Algebra Systems, application of ..
  11.  7Q.- Computer Algebra Systems, references to ..
  12.  8Q.- Fields Medal, general info ..
  13.  9Q.- Four Colour Theorem, proof of ..
  14. 10Q.- 0^0=1. A comprehensive approach
  15. 11Q.- 0.999... = 1. Properties of the real numbers ..
  16. 12Q.- There are three doors, The Monty Hall problem, Master Mind and
  17.       other games ..
  18. 13Q.- Surface and Volume of the n-ball
  19. 14Q.- f(x)^f(x)=x, name of the function ..
  20. 15Q.- Projective plane of order 10 ..
  21. 16Q.- How to compute day of week of a given date
  22. 17Q.- Axiom of Choice and/or Continuum Hypothesis?
  23. 18Q.- Cutting a sphere into pieces of larger volume
  24. 19Q.- Pointers to Quaternions
  25. 20Q.- Erdos Number
  26. 21Q.- Why is there no Nobel in mathematics?
  27. 22Q.- General References and textbooks...
  28. 23Q.- Interest Rate...
  29. 24Q.- Euler's formula e^(i Pi) = - 1 ...
  30.  
  31.  
  32.  
  33. 6Q:  I have this complicated symbolic problem (most likely
  34.     a symbolic integral or a DE system) that I can't solve.
  35.     What should I do?
  36.  
  37. A:  Find a friend with access to a computer algebra system
  38.     like MAPLE, MACSYMA or MATHEMATICA and ask her/him to solve it.
  39.     If packages cannot solve it, then (and only then) ask the net.
  40.  
  41.  
  42. 7Q:  Where can I get <Symbolic Computation Package>?
  43.  
  44.     THIS IS NOT A COMPREHENSIVE LIST. There are other Computer Algebra
  45.     packages available that may better suit your needs. There is also
  46.     a FAQ list in the group sci.math.symbolic. It includes a much larger
  47.     list of vendors and developers. (The FAQ list can be obtained from
  48.     math.berkeley.edu via anonymous ftp).
  49.  
  50.  
  51.  
  52. A: Maple
  53.         Purpose: Symbolic and numeric computation, mathematical
  54.         programming, and mathematical visualization.
  55.         Contact: Waterloo Maple Software,
  56.         450 Phillip Street
  57.         Waterloo, Ontario
  58.         N2L 5J2
  59.         Phone (519)747-2373
  60.         FAX   (519)747-5284
  61.         email:  info@maplesoft.on.ca
  62.  
  63.  
  64. A: DOE-Macsyma
  65.         Purpose: Symbolic and mathematical manipulations.
  66.         Contact: National Energy Software Center
  67.         Argonne National Laboratory 9700 South Cass Avenue
  68.         Argonne, Illinois 60439
  69.         Phone: (708) 972-7250
  70.  
  71.  
  72. A: Pari
  73.         Purpose: Number-theoretic computations and simple numerical
  74.         analysis.
  75.         Available for most 32-bit machines, including 386+387 and 486.
  76.         This is a copyrighted but free package, available by ftp from
  77.         math.ucla.edu (128.97.4.254) and ftp.inria.fr (128.93.1.26).
  78.         Contact: questions about pari can be sent to pari@ceremab.u-bordeaux.fr
  79.         and for the Macintosh versions to bernardi@mathp7.jussieu.fr
  80.  
  81.  
  82. A: Mathematica
  83.         Purpose: Mathematical computation and visualization,
  84.         symbolic programming.
  85.         Contact: Wolfram Research, Inc.
  86.         100 Trade Center Drive Champaign,
  87.         IL 61820-7237
  88.         Phone: 1-800-441-MATH
  89.         info@wri.com
  90.  
  91.  
  92. A: Macsyma
  93.         Purpose: Symbolic numerical and graphical mathematics.
  94.         Contact: Macsyma Inc.
  95.         20 Academy Street
  96.         Arlington, MA 02174
  97.         tel: 617-646-4550
  98.         fax: 617-646-3161
  99.         email: info-macsyma@macsyma.com
  100.  
  101.  
  102. A: Matlab
  103.         Purpose: `matrix laboratory' for tasks involving
  104.         matrices, graphics and general numerical computation.
  105.         Contact: The MathWorks, Inc.
  106.         21 Prime Park Way
  107.         Natick, MA 01760
  108.         508-653-1415
  109.         info@mathworks.com
  110.  
  111.  
  112. A: Cayley
  113.         Purpose: Computation in algebraic and combinatorial structures
  114.         such as groups, rings, fields, modules and graphs.
  115.         Available for: SUN 3, SUN 4, IBM running AIX or VM, DEC VMS, others
  116.         Contact: Computational Algebra Group
  117.         University of Sydney
  118.         NSW 2006
  119.         Australia
  120.         Phone:  (61) (02) 692 3338
  121.         Fax: (61) (02) 692 4534
  122.         cayley@maths.su.oz.au
  123.  
  124.  
  125. 8Q:  Let P be a property about the Fields Medal. Is P(x) true?
  126.  
  127. A:  Institution is meant to be the Institution to which the researcher
  128.     in question was associated to at the time the medal was awarded.
  129.  
  130.  
  131. Year Name               Birthplace              Age Institution
  132. ---- ----               ----------              --- -----------
  133. 1936 Ahlfors, Lars      Helsinki       Finland   29 Harvard U         USA
  134. 1936 Douglas, Jesse     New York NY    USA       39 MIT               USA
  135. 1950 Schwartz, Laurent  Paris          France    35 U of Nancy        France
  136. 1950 Selberg, Atle      Langesund      Norway    33 Adv.Std.Princeton USA
  137. 1954 Kodaira, Kunihiko  Tokyo          Japan     39 Princeton U       USA
  138. 1954 Serre, Jean-Pierre Bages          France    27 College de France France
  139. 1958 Roth, Klaus        Breslau        Germany   32 U of London       UK
  140. 1958 Thom, Rene         Montbeliard    France    35 U of Strasbourg   France
  141. 1962 Hormander, Lars    Mjallby        Sweden    31 U of Stockholm    Sweden
  142. 1962 Milnor, John       Orange NJ      USA       31 Princeton U       USA
  143. 1966 Atiyah, Michael    London         UK        37 Oxford U          UK
  144. 1966 Cohen, Paul        Long Branch NJ USA       32 Stanford U        USA
  145. 1966 Grothendieck, Alexander Berlin    Germany   38 U of Paris        France
  146. 1966 Smale, Stephen     Flint MI       USA       36 UC Berkeley       USA
  147. 1970 Baker, Alan        London         UK        31 Cambridge U       UK
  148. 1970 Hironaka, Heisuke  Yamaguchi-ken  Japan     39 Harvard U         USA
  149. 1970 Novikov, Serge     Gorki          USSR      32 Moscow U          USSR
  150. 1970 Thompson, John     Ottawa KA      USA       37 U of Chicago      USA
  151. 1974 Bombieri, Enrico   Milan          Italy     33 U of Pisa         Italy
  152. 1974 Mumford, David     Worth, Sussex  UK        37 Harvard U         USA
  153. 1978 Deligne, Pierre    Brussels       Belgium   33 IHES              France
  154. 1978 Fefferman, Charles Washington DC  USA       29 Princeton U       USA
  155. 1978 Margulis, Gregori  Moscow         USSR      32 InstPrblmInfTrans USSR
  156. 1978 Quillen, Daniel    Orange NJ      USA       38 MIT               USA
  157. 1982 Connes, Alain      Draguignan     France    35 IHES              France
  158. 1982 Thurston, William  Washington DC  USA       35 Princeton U       USA
  159. 1982 Yau, Shing-Tung    Kwuntung       China     33 IAS               USA
  160. 1986 Donaldson, Simon   Cambridge      UK        27 Oxford U          UK
  161. 1986 Faltings, Gerd     1954           Germany   32 Princeton U       USA
  162. 1986 Freedman, Michael  Los Angeles CA USA       35 UC San Diego      USA
  163. 1990 Drinfeld, Vladimir Kharkov        USSR      36 Phys.Inst.Kharkov USSR
  164. 1990 Jones, Vaughan     Gisborne       N Zealand 38 UC Berkeley       USA
  165. 1990 Mori, Shigefumi    Nagoya         Japan     39 U of Kyoto?       Japan
  166. 1990 Witten, Edward     Baltimore      USA       38 Princeton U/IAS   USA
  167.  
  168. References :
  169.  
  170. International Mathematical Congresses, An Illustrated History 1893-1986,
  171. Revised Edition, Including 1986, by Donald J.Alberts, G. L. Alexanderson
  172. and Constance Reid, Springer Verlag, 1987.
  173.  
  174. Tropp, Henry S., ``The origins and history of the Fields Medal,''
  175. Historia Mathematica, 3(1976), 167-181.
  176.  
  177.  
  178. 9Q:  Has the Four Colour Theorem been proved?
  179.  
  180.     Four Color Theorem:
  181.  
  182.     Every planar map with regions of simple borders can be coloured
  183.     with 4 colours in such a way that no two regions sharing a non-zero
  184.     length border have the same colour.
  185.  
  186. A:  This theorem was proved with the aid of a computer in 1976.
  187.     The proof shows that if aprox. 1,936  basic forms of maps
  188.     can be coloured with four colours, then any given map can be
  189.     coloured with four colours. A computer program coloured this
  190.     basic forms. So far nobody has been able to prove it without
  191.     using a computer. In principle it is possible to emulate the
  192.     computer proof by hand computations.
  193.  
  194.     References:
  195.  
  196.     K. Appel and W. Haken, Every planar map is four colourable,
  197.     Bulletin of the American Mathematical Society, vol. 82, 1976
  198.     pp.711-712.
  199.  
  200.     K. Appel and W. Haken, Every planar map is four colourable,
  201.     Illinois Journal of Mathematics, vol. 21, 1977, pp. 429-567.
  202.  
  203.     T. Saaty and Paul Kainen, The Four Colour Theorem: Assault and
  204.     Conquest, McGraw-Hill, 1977. Reprinted by Dover Publications 1986.
  205.  
  206.     K. Appel and W. Haken, Every Planar Map is Four Colourable,
  207.     Contemporary Mathematics, vol. 98, American Mathematical Society,
  208.     1989, pp.741.
  209.  
  210.     F. Bernhart, Math Reviews. 91m:05007, Dec. 1991. (Review of Appel
  211.     and Haken's book).
  212.  
  213.  
  214. 10Q:  What is 0^0 ?
  215.  
  216. A:  According to some Calculus textbooks, 0^0 is an "indeterminate
  217.     form". When evaluating a limit of the form 0^0, then you need
  218.     to know that limits of that form are called "indeterminate forms",
  219.     and that you need to use a special technique such as L'Hopital's
  220.     rule to evaluate them. Otherwise, 0^0=1 seems to be the most
  221.     useful choice for 0^0. This convention allows us to extend
  222.     definitions in different areas of mathematics that otherwise would
  223.     require treating 0 as a special case. Notice that 0^0 is a
  224.     discontinuity of the function x^y.
  225.  
  226.     Rotando & Korn show that if f and g are real functions that vanish
  227.     at the origin and are _analytic_ at 0 (infinitely differentiable is
  228.     not sufficient), then f(x)^g(x) approaches 1 as x approaches 0 from
  229.     the right.
  230.  
  231.     From Concrete Mathematics p.162 (R. Graham, D. Knuth, O. Patashnik):
  232.  
  233.     "Some textbooks leave the quantity 0^0 undefined, because the
  234.     functions x^0 and 0^x have different limiting values when x
  235.     decreases to 0. But this is a mistake. We must define
  236.  
  237.        x^0 = 1 for all x,
  238.  
  239.     if the binomial theorem is to be valid when x=0, y=0, and/or x=-y.
  240.     The theorem is too important to be arbitrarily restricted! By
  241.     contrast, the function 0^x is quite unimportant."
  242.    Published by Addison-Wesley, 2nd printing Dec, 1988.
  243.  
  244.     References:
  245.  
  246.     H. E. Vaughan, The expression '0^0', Mathematics Teacher 63 (1970),
  247.     pp.111-112.
  248.  
  249.     Louis M. Rotando & Henry Korn, "The Indeterminate Form 0^0",
  250.     Mathematics Magazine, Vol. 50, No. 1 (January 1977), pp. 41-42.
  251.  
  252.     L. J. Paige, A note on indeterminate forms, American Mathematical
  253.     Monthly, 61 (1954), 189-190; reprinted in the Mathematical
  254.     Association of America's 1969 volume, Selected Papers on Calculus,
  255.     pp. 210-211.
  256.  
  257.  
  258. 11Q:  Why is 0.9999... = 1?
  259.  
  260. A:  In modern mathematics, the string of symbols "0.9999..." is
  261.     understood to be a shorthand for "the infinite sum  9/10 + 9/100
  262.     + 9/1000 + ...." This in turn is shorthand for "the limit of the
  263.     sequence of real numbers 9/10, 9/10 + 9/100, 9/10 + 9/100 + 9/1000,
  264.     ..."  Using the well-known epsilon-delta definition of limit, one
  265.     can easily show that this limit is 1.  The statement that
  266.     0.9999...  = 1 is simply an abbreviation of this fact.
  267.  
  268.                     oo              m
  269.                    ---   9         ---   9
  270.         0.999... = >   ---- = lim  >   ----
  271.                    --- 10^n  m->oo --- 10^n
  272.                    n=1             n=1
  273.  
  274.  
  275.         Choose epsilon > 0. Suppose delta = 1/-log_10 epsilon, thus
  276.         epsilon = 10^(-1/delta). For every m>1/delta we have that
  277.  
  278.         |  m           |
  279.         | ---   9      |     1          1
  280.         | >   ---- - 1 | = ---- < ------------ = epsilon
  281.         | --- 10^n     |   10^m   10^(1/delta)
  282.         | n=1          |
  283.  
  284.         So by the (epsilon-delta) definition of the limit we have
  285.  
  286.                m
  287.               ---   9
  288.          lim  >   ---- = 1
  289.         m->oo --- 10^n
  290.               n=1
  291.  
  292.  
  293.     An *informal* argument could be given by noticing that the following
  294.     sequence of "natural" operations has as a consequence 1 = 0.9999....
  295.     Therefore it's "natural" to assume 1 = 0.9999.....
  296.  
  297.              x = 0.99999....
  298.            10x = 9.99999....
  299.        10x - x = 9
  300.             9x = 9
  301.              x = 1
  302.     Thus
  303.              1 = 0.99999....
  304.  
  305.     References:
  306.  
  307.     E. Hewitt & K. Stromberg, Real and Abstract Analysis,
  308.     Springer-Verlag, Berlin, 1965.
  309.  
  310.     W. Rudin, Principles of Mathematical Analysis, McGraw-Hill, 1976.
  311.  
  312.  
  313. 12Q:  There are three doors, and there is a car hidden behind one
  314.     of them, Master Mind and other games ..
  315.  
  316. A:  Read frequently asked questions from rec.puzzles, as well as
  317.     their ``archive file'' where the problem is solved and carefully 
  318.     explained. (The Monty Hall problem). 
  319.  
  320.     MANY OTHER MATHEMATICAL GAMES ARE EXPLAINED IN THE REC.PUZZLES 
  321.     FAQ AND ARCHIVES. READ IT BEFORE ASKING IN SCI.MATH.
  322.  
  323.     Your chance of winning is 2/3 if you switch and 1/3 if you don't.
  324.     For a full explanation from the rec.puzzles' archive, send to the
  325.     address archive-request@questrel.com an email message consisting 
  326.     of the text
  327.  
  328.                send monty.hall
  329.  
  330.  
  331.     Also any other FAQ list can be obtained through anonymous ftp from
  332.     rtfm.mit.edu.
  333.  
  334.     References
  335.  
  336.     American Mathematical Monthly, January 1992.
  337.  
  338.  
  339.     For the game of Master Mind it has been proven that no more than
  340.     five moves are required in the worst case. For references look at
  341.  
  342.     One such algorithm was published in the Journal of Recreational
  343.     Mathematics; in '70 or '71 (I think), which always solved the
  344.     4 peg problem in 5 moves. Knuth later published an algorithm which
  345.     solves the problem in a shorter # of moves - on average - but can
  346.     take six guesses on certain combinations.
  347.  
  348.  
  349.  
  350.     Donald E. Knuth, The Computer as Master Mind, J. Recreational Mathematics
  351.     9 (1976-77), 1-6.
  352.  
  353.  
  354. 13Q:  What is the formula for the "Surface Area" of a sphere in
  355.     Euclidean N-Space.  That is, of course, the volume of the N-1
  356.     solid which comprises the boundary of an N-Sphere.
  357.  
  358. A:  The volume of a ball is the easiest formula to remember:  It's r^N
  359.     times pi^(N/2)/(N/2)!.  The only hard part is taking the factorial
  360.     of a half-integer.  The real definition is that x! = Gamma(x+1), but
  361.     if you want a formula, it's:
  362.  
  363.     (1/2+n)! = sqrt(pi)*(2n+2)!/(n+1)!/4^(n+1)
  364.  
  365.     To get the surface area, you just differentiate to get
  366.     N*pi^(N/2)/(N/2)!*r^(N-1).
  367.  
  368.     There is a clever way to obtain this formula using Gaussian
  369.     integrals. First, we note that the integral over the line of
  370.     e^(-x^2) is sqrt(pi).  Therefore the integral over N-space of
  371.     e^(-x_1^2-x_2^2-...-x_N^2) is sqrt(pi)^n.  Now we change to
  372.     spherical coordinates.  We get the integral from 0 to infinity
  373.     of V*r^(N-1)*e^(-r^2), where V is the surface volume of a sphere.
  374.     Integrate by parts repeatedly to get the desired formula.
  375.  
  376.     It is possible to derive the volume of the sphere from ``first 
  377.     principles''.
  378.  
  379.  
  380. 14Q:  Does anyone know a name (or a closed form) for
  381.  
  382.       f(x)^f(x)=x
  383.  
  384.  
  385.     Solving for f one finds a "continued fraction"-like answer
  386.  
  387.  
  388.                f(x) = log x
  389.                       -----
  390.                       log (log x
  391.                           ------
  392.                               ...........
  393.  
  394. A:  This question has been repeated here from time to time over the
  395.     years, and no one seems to have heard of any published work on it,
  396.     nor a published name for it (D. Merrit proposes "lx" due to its
  397.     (very) faint resemblance to log). It's not an analytic function.
  398.  
  399.     The "continued fraction" form for its numeric solution is highly
  400.     unstable in the region of its minimum at 1/e (because the graph is
  401.     quite flat there yet logarithmic approximation oscillates wildly),
  402.     although it converges fairly quickly elsewhere. To compute its value
  403.     near 1/e, use the bisection method which gives good results. Bisection
  404.     in other regions converges much more slowly than the "logarithmic
  405.     continued fraction" form, so a hybrid of the two seems suitable.
  406.     Note that it's dual valued for the reals (and many valued complex
  407.     for negative reals).
  408.  
  409.     A similar function is a "built-in" function in MAPLE called W(x).
  410.     MAPLE considers a solution in terms of W(x) as a closed form (like
  411.     the erf function). W is defined as W(x)*exp(W(x))=x.
  412.  
  413.     An extensive treatise on the known facts of Lambert's W function
  414.     is available for anonymous ftp at daisy.uwaterloo.ca in the
  415.     /pub/maple/5.2/share/LambertW.ps.
  416.  
  417.  
  418.  
  419. 15Q: Does there exist a projective plane of order 10?
  420.  
  421.     More precisely:
  422.  
  423.     Is it possible to define 111 sets (lines) of 11 points each
  424.     such that:
  425.     
  426.       For any pair of points there is precisely one line containing them
  427.       both and for any pair of lines there is only one point common to
  428.       them both?
  429.  
  430.  
  431. A:  Analogous questions with n^2 + n + 1 and n + 1 instead of 111 and 11
  432.     have been positively answered only in case n is a prime power.
  433.     For n=6 it is not possible, more generally if n is congruent to 1
  434.     or 2 mod 4 and can not be written as a sum of two squares, then an
  435.     FPP of order n does not exist.  The n=10 case has been settled as not
  436.     possible either by Clement Lam. As the "proof" took several years of
  437.     computer search (the equivalent of 2000 hours on a Cray-1) it can be 
  438.     called the most time-intensive computer assisted single proof. The
  439.     final steps were ready in January 1989.
  440.  
  441.     References
  442.  
  443.     R. H. Bruck and H. J. Ryser, "The nonexistence of certain finite
  444.     projective planes," Canadian Journal of Mathematics, vol. 1 (1949),
  445.     pp 88-93.
  446.  
  447.     C. Lam, Amer.Math.Monthly 98 (1991), 305-318.
  448.  
  449.  
  450. 16Q:  Is there a formula to determine the day of the week, given
  451.     the month, day and year?
  452.  
  453. A:  First a brief explanation: In the Gregorian Calendar, over a period
  454.     of four hundred years, there are 97 leap years and 303 normal years.
  455.     Each normal year, the day of January 1 advances by one; for each leap
  456.     year it advances by two.
  457.  
  458.         303 + 97 + 97 = 497 = 7 * 71
  459.  
  460.     As a result, January 1 year N occurs on the same day of the week as
  461.     January 1 year N + 400.  Because the leap year pattern also recurs
  462.     with a four hundred year cycle, a simple table of four hundred
  463.     elements, and single modulus, suffices to determine the day of the
  464.     week (in the Gregorian Calendar), and does it much faster than all the
  465.     other algorithms proposed.  Also, each element takes (in principle)
  466.     only three bits; the entire table thus takes only 1200 bits, or 300
  467.     bytes; on many computers this will be less than the instructions to do
  468.     all the complicated calculations proposed for the other algorithms.
  469.  
  470.     Incidental note: Because 7 does not divide 400, January 1 occurs more
  471.     frequently on some days than others!  Trick your friends!  In a cycle
  472.     of 400 years, January 1 and March 1 occur on the following days with
  473.     the following frequencies:
  474.  
  475.            Sun      Mon     Tue     Wed     Thu     Fri     Sat
  476.     Jan 1: 58       56      58      57      57      58      56
  477.     Mar 1: 58       56      58      56      58      57      57
  478.  
  479.     Of interest is that (contrary to most initial guesses) the occurrence
  480.     is not maximally flat.
  481.  
  482.     The Gregorian calendar was introduced in 1582 in parts of Europe; it was
  483.     adopted in 1752 in Great Britain and its colonies, and on various dates
  484.     in other countries.  It replaced the Julian Calendar which has a four-year
  485.     cycle of leap years; after four years January 1 has advanced by five days.
  486.     Since 5 is relatively prime to 7, a table of 4 * 7 = 28 elements is
  487.     necessary for the Julian Calendar.
  488.  
  489.  
  490.     There is still a 3 day / 10,000 year error which the Gregorian calendar
  491.     does not take.  into account.  At some time such a correction will have
  492.     to be done but your software will probably not last that long :-)   !
  493.  
  494.     Here is a standard method suitable for mental computation:
  495.  
  496.         A. Take the last two digits of the year.
  497.         B. Divide by 4, discarding any fraction.
  498.         C. Add the day of the month.
  499.         D. Add the month's key value: JFM AMJ JAS OND
  500.                                       144 025 036 146
  501.         E. Subtract 1 for January or February of a leap year.
  502.         F. For a Gregorian date, add 0 for 1900's, 6 for 2000's, 4 for 1700's,
  503.            2 for 1800's; for other years, add or subtract multiples of 400.
  504.         G. For a Julian date, add 1 for 1700's, and 1 for every additional
  505.            century you go back.
  506.         H. Add the last two digits of the year.
  507.         I. Divide by 7 and take the remainder.
  508.  
  509.         Now 1 is Sunday, the first day of the week, 2 is Monday, and so on.
  510.  
  511.     The following formula, which is for the Gregorian calendar only, may be
  512.     more convenient for computer programming.  Note that in some programming
  513.     languages the remainder operation can yield a negative result if given
  514.     a negative operand, so "mod 7" may not translate to a simple remainder.
  515.  
  516.         W == (k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]) mod 7
  517.            where [] denotes the integer floor function (round down),
  518.            k is day (1 to 31)
  519.            m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
  520.                          Treat Jan & Feb as months of the preceding year
  521.            C is century (1987 has C = 19)
  522.            Y is year    (1987 has Y = 87 except Y = 86 for Jan & Feb)
  523.            W is week day (0 = Sunday, ..., 6 = Saturday)
  524.  
  525.     Here the century & 400 year corrections are built into the formula.
  526.     The [2.6m-0.2] term relates to the repetitive pattern that the 30-day
  527.     months show when March is taken as the first month.
  528.  
  529.  
  530.     References:
  531.  
  532.     Winning Ways  by Conway, Guy, Berlekamp is supposed to have it.
  533.  
  534.     Martin Gardner in "Mathematical Carnival".
  535.  
  536.     Michael Keith and Tom Craver, "The Ultimate Perpetual Calendar?",
  537.     Journal of Recreational Mathematics, 22:4, pp. 280-282, 19
  538.  
  539.     K. Rosen, "Elementary Number Theory",  p. 156.
  540.  
  541.  
  542.  
  543. 17Q:  What is the Axiom of Choice?  Why is it important? Why some articles
  544.     say "such and such is provable, if you accept the axiom of choice."?
  545.     What are the arguments for and against the axiom of choice?
  546.  
  547.  
  548. A:  There are several equivalent formulations:
  549.  
  550.     -The Cartesian product of nonempty sets is nonempty, even
  551.     if the product is of an infinite family of sets.
  552.  
  553.     -Given any set S of mutually disjoint nonempty sets, there is a set C
  554.     containing a single member from each element of S.  C can thus be
  555.     thought of as the result of "choosing" a representative from each
  556.     set in S. Hence the name.
  557.  
  558.     >Why is it important?
  559.  
  560.     All kinds of important theorems in analysis require it.  Tychonoff's
  561.     theorem and the Hahn-Banach theorem are examples. Indeed,
  562.     Tychonoff's theorem is equivalent to AC. Similarly, AC is equivalent
  563.     to the thesis that every set can be well-ordered.  Zermelo's first
  564.     proof of this in 1904 I believe was the first proof in which AC was
  565.     made explicit.  AC is especially handy for doing infinite cardinal
  566.     arithmetic, as without it the most you get is a *partial* ordering
  567.     on the cardinal numbers.  It also enables you to prove such
  568.     interesting general facts as that n^2 = n for all infinite cardinal
  569.     numbers.
  570.  
  571.     > What are the arguments for and against the axiom of choice?
  572.  
  573.     The axiom of choice is independent of the other axioms of set theory
  574.     and can be assumed or not as one chooses.
  575.  
  576.     (For) All ordinary mathematics uses it.
  577.  
  578.     There are a number of arguments for AC, ranging from a priori to
  579.     pragmatic.  The pragmatic argument (Zermelo's original approach) is
  580.     that it allows you to do a lot of interesting mathematics.  The more
  581.     conceptual argument derives from the "iterative" conception of set
  582.     according to which sets are "built up" in layers, each layer consisting
  583.     of all possible sets that can be constructed out of elements in the
  584.     previous layers.  (The building up is of course metaphorical, and is
  585.     suggested only by the idea of sets in some sense consisting of their
  586.     members; you can't have a set of things without the things it's a set
  587.     of).  If then we consider the first layer containing a given set S of
  588.     pairwise disjoint nonempty sets, the argument runs, all the elements
  589.     of all the sets in S must exist at previous levels "below" the level
  590.     of S.  But then since each new level contains *all* the sets that can
  591.     be formed from stuff in previous levels, it must be that at least by
  592.     S's level all possible choice sets have already been *formed*. This
  593.     is more in the spirit of Zermelo's later views (c. 1930).
  594.  
  595.     (Against) It has some supposedly counterintuitive consequences,
  596.     such as the Banach-Tarski paradox. (See next question)
  597.  
  598.     Arguments against AC typically target its nonconstructive character:
  599.     it is a cheat because it conjures up a set without providing any
  600.     sort of *procedure* for its construction--note that no *method* is
  601.     assumed for picking out the members of a choice set.  It is thus the
  602.     platonic axiom par excellence, boldly asserting that a given set
  603.     will always exist under certain circumstances in utter disregard of
  604.     our ability to conceive or construct it.  The axiom thus can be seen
  605.     as marking a divide between two opposing camps in the philosophy of
  606.     mathematics:  those for whom mathematics is essentially tied to our
  607.     conceptual capacities, and hence is something we in some sense
  608.     *create*, and those for whom mathematics is independent of any such
  609.     capacities and hence is something we *discover*.  AC is thus of
  610.     philosophical as well as mathematical significance.
  611.  
  612.  
  613.     It should be noted that some interesting mathematics has come out of an
  614.     incompatible axiom, the Axiom of Determinacy (AD).  AD asserts that
  615.     any two-person game without ties has a winning strategy for the first or
  616.     second player.  For finite games, this is an easy theorem; for infinite
  617.     games with duration less than \omega and move chosen from a countable set,
  618.     you can prove the existence of a counter-example using AC.  Jech's book
  619.     "The Axiom of Choice" has a discussion.
  620.  
  621.     An example of such a game goes as follows.
  622.  
  623.        Choose in advance a set of infinite sequences of integers; call it A.
  624.        Then I pick an integer, then you do, then I do, and so on forever
  625.        (i.e. length \omega).  When we're done, if the sequence of integers
  626.        we've chosen is in A, I win; otherwise you win.  AD says that one of
  627.        us must have a winning strategy.  Of course the strategy, and which
  628.        of us has it, will depend upon A.
  629.  
  630.  
  631.     From a philosophical/intuitive/pedagogical standpoint, I think Bertrand
  632.     Russell's shoe/sock analogy has a lot to recommend it.  Suppose you have an
  633.     infinite collection of pairs of shoes.  You want to form a set with one
  634.     shoe from each pair.  AC is not necessary, since you can define the set as
  635.     "the set of all left shoes". (Technically, we're using the axiom of
  636.     replacement, one of the basic axioms of Zermelo-Fraenkel (ZF) set theory.)
  637.     If instead you want to form a set containing one sock from each pair of an
  638.     infinite collection of pairs of socks, you now need AC.
  639.  
  640.  
  641.     References:
  642.  
  643.     Maddy, "Believing the Axioms, I", J. Symb. Logic, v. 53, no. 2, June 1988,
  644.     pp. 490-500, and "Believing the Axioms II" in v.53, no. 3.
  645.  
  646.     Gregory H. Moore, Zermelo's Axiom of Choice, New York, Springer-Verlag,
  647.     1982.
  648.  
  649.     H. Rubin and J. E. Rubin, Equivalents of the Axiom of Choice II,
  650.     North-Holland/Elsevier Science, 1985.
  651.  
  652.     A. Fraenkel, Y.  Bar-Hillel, and A. Levy, Foundations of Set Theory,
  653.     Amsterdam, North-Holland, 1984 (2nd edition, 2nd printing), pp. 53-86.
  654.  
  655.  
  656. 18Q:  Cutting a sphere into pieces of larger volume. Is it possible
  657.     to cut a sphere into a finite number of pieces and reassemble
  658.     into a solid of twice the volume?
  659.  
  660. A:  This question has many variants and it is best answered explicitly.
  661.     Given two polygons of the same area, is it always possible to
  662.     dissect one into a finite number of pieces which can be reassembled
  663.     into a replica of the other?
  664.  
  665.     Dissection theory is extensive.  In such questions one needs to
  666.     specify
  667.  
  668.      (A) what a "piece" is,  (polygon?  Topological disk?  Borel-set?
  669.          Lebesgue-measurable set?  Arbitrary?)
  670.  
  671.      (B) how many pieces are permitted (finitely many? countably? uncountably?)
  672.  
  673.      (C) what motions are allowed in "reassembling" (translations?
  674.          rotations?  orientation-reversing maps?  isometries?
  675.          affine maps?  homotheties?  arbitrary continuous images?  etc.)
  676.  
  677.      (D) how the pieces are permitted to be glued together.  The
  678.          simplest notion is that they must be disjoint.  If the pieces
  679.          are polygons [or any piece with a nice boundary] you can permit
  680.          them to be glued along their boundaries, ie the interiors of the
  681.          pieces disjoint, and their union is the desired figure.
  682.  
  683.  
  684.     Some dissection results
  685.  
  686.      1) We are permitted to cut into FINITELY MANY polygons, to TRANSLATE
  687.         and ROTATE the pieces, and to glue ALONG BOUNDARIES;
  688.         then Yes, any two equal-area polygons are equi-decomposable.
  689.  
  690.         This theorem was proven by Bolyai and Gerwien independently, and has
  691.         undoubtedly been independently rediscovered many times.  I would not
  692.         be surprised if the Greeks knew this.
  693.  
  694.         The Hadwiger-Glur theorem implies that any two equal-area polygons are
  695.         equi-decomposable using only TRANSLATIONS and ROTATIONS BY 180
  696.         DEGREES.
  697.  
  698.      2) THM (Hadwiger-Glur, 1951) Two equal-area polygons P,Q are
  699.         equi-decomposable by TRANSLATIONS only, iff we have equality of these
  700.         two functions:     PHI_P() = PHI_Q()
  701.         Here, for each direction v (ie, each vector on the unit circle in the
  702.         plane), let PHI_P(v) be the sum of the lengths of the edges of P which
  703.         are perpendicular to v, where for such an edge, its length is positive
  704.         if v is an outward normal to the edge and is negative if v is an
  705.         inward normal to the edge.
  706.  
  707.  
  708.      3) In dimension 3, the famous "Hilbert's third problem" is:
  709.  
  710.        "If P and Q are two polyhedra of equal volume, are they
  711.         equi-decomposable by means of translations and rotations, by
  712.         cutting into finitely many sub-polyhedra, and gluing along
  713.         boundaries?"
  714.  
  715.         The answer is "NO" and was proven by Dehn in 1900, just a few months
  716.         after the problem was posed. (Ueber raumgleiche polyeder, Goettinger
  717.         Nachrichten 1900, 345-354). It was the first of Hilbert's problems
  718.         to be solved. The proof is nontrivial but does *not* use the axiom
  719.         of choice.
  720.  
  721.         "Hilbert's Third Problem", by V.G.Boltianskii, Wiley 1978.
  722.  
  723.  
  724.      4) Using the axiom of choice on non-countable sets, you can prove
  725.         that a solid sphere can be dissected into a finite number of
  726.         pieces that can be reassembled to two solid spheres, each of
  727.         same volume of the original. No more than nine pieces are needed.
  728.  
  729.         The minimum possible number of pieces is FIVE.  (It's quite easy
  730.         to show that four will not suffice).  There is a particular
  731.         dissection in which one of the five pieces is the single center
  732.         point of the original sphere, and the other four pieces  A, A',
  733.         B, B'  are such that A is congruent to A' and B is congruent to B'.
  734.         [See Wagon's book].
  735.  
  736.         This construction is known as the "Banach-Tarski" paradox or the
  737.         "Banach-Tarski-Hausdorff" paradox (Hausdorff did an early version of
  738.         it).  The "pieces" here are non-measurable sets, and they are
  739.         assembled *disjointly* (they are not glued together along a boundary,
  740.         unlike the situation in Bolyai's thm.)
  741.          An excellent book on Banach-Tarski is:
  742.  
  743.         "The Banach-Tarski Paradox", by Stan Wagon, 1985, Cambridge
  744.         University Press.
  745.  
  746.         Robert M. French, The Banach-Tarski theorem, The Mathematical 
  747.         Intelligencer 10 (1988) 21-28.
  748.  
  749.  
  750.         The pieces are not (Lebesgue) measurable, since measure is preserved
  751.         by rigid motion. Since the pieces are non-measurable, they do not
  752.         have reasonable boundaries. For example, it is likely that each piece's
  753.         topological-boundary is the entire ball.
  754.  
  755.         The full Banach-Tarski paradox is stronger than just doubling the
  756.         ball.  It states:
  757.  
  758.      5) Any two bounded subsets (of 3-space) with non-empty interior, are
  759.         equi-decomposable by translations and rotations.
  760.  
  761.         This is usually illustrated by observing that a pea can be cut up
  762.         into finitely pieces and reassembled into the Earth.
  763.  
  764.         The easiest decomposition "paradox" was observed first by Hausdorff:
  765.  
  766.      6) The unit interval can be cut up into COUNTABLY many pieces which,
  767.         by *translation* only, can be reassembled into the interval of
  768.         length 2.
  769.  
  770.         This result is, nowadays, trivial, and is the standard example of a
  771.         non-measurable set, taught in a beginning graduate class on measure
  772.         theory.
  773.  
  774.  
  775.         References:
  776.  
  777.         In addition to Wagon's book above, Boltyanskii has written at least
  778.         two works on this subject.  An elementary one is:
  779.  
  780.           "Equivalent and equidecomposable figures"
  781.  
  782.         in Topics in Mathematics published by D.C. HEATH AND CO., Boston.  It
  783.         is a translation from the 1956 work in Russian.
  784.  
  785.           Also, the article "Scissor Congruence" by Dubins, Hirsch and ?,
  786.         which appeared about 20 years ago in the Math Monthly, has a pretty
  787.         theorem on decomposition by Jordan arcs.
  788.  
  789.  
  790.         ``Banach and Tarski had hoped that the physical absurdity of this
  791.         theorem would encourage mathematicians to discard AC. They were
  792.         dismayed when the response of the math community was `Isn't AC great?
  793.         How else could we get such counterintuitive results?' ''
  794.  
  795.  
  796.  
  797. Copyright Notice
  798.  
  799. Copyright (c) 1993   A. Lopez-Ortiz
  800.  
  801.   This FAQ is Copyright (C) 1994 by Alex Lopez-Ortiz. This text,
  802.   in whole or in part, may not be sold in any medium, including,
  803.   but not limited to electronic, CD-ROM, or published in print,
  804.   without the explicit, written permission of Alex Lopez-Ortiz.
  805.  
  806.  
  807.  
  808.  
  809. --------------------------------------------------------------------------
  810. Questions and Answers Edited and Compiled by:
  811.  
  812. Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
  813. Department of Computer Science                      University of Waterloo
  814. Waterloo, Ontario                                                   Canada
  815. -- 
  816. Alex Lopez-Ortiz                             alopez-o@neumann.UWaterloo.ca
  817. Department of Computer Science                      University of Waterloo
  818. Waterloo, Ontario                                                   Canada
  819.