December 2002 - mathfun@mailman.xmission.com

[math-fun] Reference book on voting systems, paradoxes, etc?
by Bernie Cosell 17 Dec '02

17 Dec '02

For some time now I've been putting off getting a book on Arrow's Theorem/paradox, Condorcet criteria, etc... and for no particularly good reason the topic has surfaced again for me and I thought I'd turn to you folks for recommendations for a good expository book on voting systems.. Thanks! /Bernie\ Bernie Cosell bernie(a)fantasyfarm.com

1 0

[math-fun] René Thom
by asimovd＠aol.com 14 Dec '02

14 Dec '02

I just learned that French mathematician René Thom died on Nov. 17. He was awarded the Fields medal in 1958 for his work on cobordism theory, and is also well-known for originating catastrophe theory in the late 1960's. In case anyone's interested, the simplest case of cobordism theory defines an equivalence relation on all (compact and boundaryless) manifolds of a fixed dimension: two n-manifolds M,N are equivalent when there is an (n+1)-manifold W such that the boundary of W is M u N. With union as the additive operation, and cartesian product as the multiplication, the set of equivalence classes form a "graded algebra" over Z_2. Manifolds that are themselves the boundary of another manifold represent the zeros in this algebra, and it's over Z_2 since M u M is always the boundary of M x [0,1]. Thom's astonishingly elegant result is that this graded algebra over Z_2 has just one generator in each dimension *not* of the form 2^k - 1, for k >= 1. Put another way, the algebra is all polynomials over Z_2 formed by 1=x0 (represented by the point), x_2, x_4, x_5, x_6, x_8, x_9, etc., where the degree of any monomial is the sum of the indices of its factors. (The monomials of a given degree correspond to the equivalence classes among connected manifolds of that dimension.) Hence, among connected manifolds there are just two "cobordism" classes {0, x_2} in dimension 2; just one {0} in dimensions 1 or 3 (i.e. every manifold of dimension 1 or 3 is the boundary of another manifold), and e.g. three in dimension 9: {0, x_4 * x_5, x_9}. --Dan

2 1

RE: [math-fun] Mathematical Presidents and the Pythagorean Theore m
by Andy Latto 13 Dec '02

13 Dec '02

> -----Original Message----- > From: John McCarthy [mailto:jmc@steam.Stanford.EDU] > Sent: Friday, December 13, 2002 3:10 PM > Subject: Re: [math-fun] Mathematical Presidents > > > I recall it as a proof by Garfield. It was in my high school > geometry > book. Spoilsports claim the proof is older. Of course, it's entirely possible that Garfield independently rediscovered an existing proof. I'll use this as an excuse to share my favorite proof of the Pythagorean Theorem with the list. It's very simple, and deserves to be better known. Consider a right triangle with legs A and B, and hypotenuse C, with lengths a, b, and c. The claim that a^2 + b^2 = c^2 is equivalent to the statement that the area of a square of side A, plus the area of a square of side B, is equal to the area of a square of side C. But that's not the only geometrical statement equivalent to this equation. The area of any similar plane figures is proportional to the lengths of corresponding sides, so we can use any set of similar figures we choose to prove the Pythagorean theorem. For example, if we could show that the area of a semicircle with diameter A, plus the area of a semicircle with diameter B, was equal to the area of a semicircle with diameter C, that would suffice to show that a^2 + b^2 = c^2. The similar figures I will use in the proof are triangles similar to ABC itself, with the hypotenuse the length of the given side. Proof; draw the altitude of ABC from the vertex opposite C. Observe that the two smaller triangles are similar to the original triangle, and sum to it in area. The hypotenuses of these three triangles are A, B, and C. QED This proof is so simple I was able to give it without a diagram. When I first saw this proof (in the mathematics exhibit in a museum), it was given with diagrams, but no words! There were 5 pictures. The first was the classical picture of a right triangle, with a square erected on each side. The second was the same right triangle, with a semicircle erected on each side. The third was the same right triangle, with irregular but similar figures erected on each side. The fourth was the same right triangle, with a similar right triangle erected on each side, in the orientation that would allow these to be "folded" into the original triangle. The fifth illustration was the same as the third, with the single line described in the proof added. If you understand that the areas of similar figures are proportional to the lengths of corresponding sides, you can't look at these diagrams without being immediately convinced of the Pythagorean Theorem, even if you have never seen it before. Most short or geometrical proofs of the theorem that I've seen make it seem amazing and magical. This one makes it seem obvious. Andy Latto andy.latto(a)pobox.com

2 1

Re: [Fwd: [math-fun] triangoops
by R. William Gosper 13 Dec '02

13 Dec '02

Nick, you chided >bill, >i don't think your claim is accurate. it seems you've found the smallest c such >that one edge goes through the origin. but i think one can always find a smaller > triangle. >by experimentation, i find that c is suspiciously close to sqrt(3), but i have n >o math to support this. [...] >"R. William Gosper" wrote: >> Nick Baxter points out that in answering >> >what is the smallest constant c so that the graph of the function >> >f(x) = x^3 - c x contains the vertices of an equilateral triangle? [...] >> Claim: The midpoint of one triangle side is the origin. Otherwise, centering >> some side and rotating its endpoints back onto the curve will intersect the ot >her >> two sides with the curve, indicating that c is non-minimal. NONSENSE! The derivatives at both endpoints are equal, so you can slide them slightly in the same direction so that the other two sides obviously cross the curve, which is impossible when c is minimal. Grinding out dc/dx1=0, dc/dx2=0, the x coordinates in the minimal case are the roots near -.54557 and .83587 of 6 4 2 27 x - 54 sqrt(3) x + 72 x - 8 sqrt(3). Trying for the univariate c polynomial led toward degree 588, but numerically the answer is just c = sqrt(3) ! Erich, is there some way to see this? --rwg

2 2

[math-fun] Mathematical Presidents
by Thane Plambeck 13 Dec '02

13 Dec '02

Who was the strongest mathematician to serve as US President? I just read in Ulysses's S Grant's Memoirs that war in Mexico stopped him from teaching math at West Point. Not too bad. I suppose Thomas Jefferson? He definitely had a few math books around http://www.loc.gov/catdir/toc/becites/main/jefferson/88607928_ch25.html. I wonder what "Emerson's Fluxion's" is about. Also "Sir Isaac Newton's tables for the Renewals of Leases" sounds promising from the Jefferson library. It would be nice if Thomas Jefferson weren't the best at everything, but if that's the way it is, we have to live with it. I remember Jimmy Carter frequently being described as a "nuclear engineer," but that was when it was popular to think that Ford was a bumbler. Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

4 5

Re: [math-fun] Re: Lacings continued
by Henry Baker 13 Dec '02

13 Dec '02

I recently had the occasion to attend a workshop on Japanese bookbinding, which utilizes a strong thread to 'sew' the back of the book together. This technique is very different from that used in Western books. There are an enormous number of variations on the 'lacing' pattern used to sew the book together, but most of them seem to have some reasonable degree of symmetry -- e.g., the pattern on the back of the book is the mirror image of that on the front. The rules are somewhat different from that used in shoes -- you can have multiple parallel rows of 'eyelets', and you can thread through an eyelet multiple times. What intrigued me was the possibility that there may be some relationship with Euler Circuits in undirected graphs and the K\"onigsberg bridge problem. I started my bookbinding by following the teacher's directions, but then speculated that a 'greedy algorithm' would work. When the teacher made a mistake and got stuck, the greedy speculation was proved false. But I was still struck by how hard it was to 'get stuck'. I suspect that some Japanese mathematician has already studied this problem, but I also suspect that the paper is published in Japanese. Here is the relevant theorem from graph theory: Theorem (Euler?). An undirected graph possesses an Euler circuit iff it is connected and its vertices are all of even degree.

1 0

[math-fun] Elkies on X^3-Y^2
by Richard Schroeppel 13 Dec '02

13 Dec '02

Date: Fri, 13 Dec 2002 10:57:06 -0500 Sender: Number Theory List <NMBRTHRY(a)LISTSERV.NODAK.EDU> From: Noam Elkies <elkies(a)math.harvard.edu> Subject: Re: Ten new "good examples of Hall's conjecture" Ismael Jimenez Calvo <ltqij04(a)pinar2.csic.es> writes: > Good Examples of Hall's Conjecture > ======================================== > # x r [=sqrt(x)/|x^3-y^2|] > ======================================== > 1 2 1.41 > 2 5234 4.26 GPZ > 3 8158 3.76 GPZ > 4 93844 1.03 GPZ [...] > 13 390620082 1.33 GPZ > 14 3790689201 2.20 GPZ > 15 65589428378 2.19 E > 16 952764389446 1.15 JHS > 17 12438517260105 1.27 E > 18 35495694227489 1.15 E > 19 53197086958290 1.66 E > 20 5853886516781223 46.60 E > 21 12813608766102806 1.30 E #16 was puzzling: how could I have missed it? In fact it turns out that this was in my files from six years ago: % ls -la h6.op -rw-r--r-- 1 elkies snr_fac 128167 Jun 10 1996 h6.op % grep e+00 h6.op -849, -687, -417: 3.773e+00 969, 826, 528: 3.156e+00 5309, 1870, 494: -4.871e+00 10525, 5761, 2365: -1.228e+00 19764, 4386, 730: -1.330e+00 19602, 4362, 728: -1.336e+00 -12423, -11660, -8208: 1.081e+00 -61569, -52560, -33652: 2.197e+00 256104, 169562, 84198: -2.188e+00 >>> -976097, -963963, -713985: -1.145e+00 <<< 3526828, 1518521, 490364: 1.274e+00 5957826, 3581213, 1614484: 1.148e+00 % The marked line yields x = 976097^2 - 963963 = 952764389446. I don't know how this xample got lost on the way to my tables at <http://www.math.harvard.edu/~elkies/hall.html>; at any rate, thank you for alerting me to the omission. > 22 23415546067124892 1.46 E > 23 38115991067861271 6.50 E > 24 322001299796379844 1.04 E > 25 471477085999389882 1.38 E > 26 810574762403977064 4.66 E > 27 9870884617163518770 1.90 JHS > 28 42532374580189966073 3.47 JHS > 29 51698891432429706382 1.75 JHS > 30 44648329463517920535 1.79 JHS > 31 231411667627225650649 3.71 JHS > 32 601724682280310364065 1.88 JHS > 33 4996798823245299750533 2.17 JHS > 34 14038790674256691230847 1.27 JHS > 35 372193377967238474960883 1.33 JHS That's impressive. How does the running time of your approach grow with the upper bound on x? For my algorithm it's sqrt(x)*log^A(x), which means that raising the bound from 10^18 to 10^24 would multiply the time by about 10^3. The hardware and software improvements over my computation, indicated by > The algorithm was programmed as a PARI script that was > translated to C and compiled with the utility GP2C. > The executable was run in a Pentium III at 1000 Mhz during 30 days. , are significant, but surely don't amount to three orders of magnitude. It is true that the new computation is not claimed to be exhaustive: > The algorithm is probabilistic in the sense that it seeks for > "good examples of Hall's conjecture" where they can be found > with higher probability. Nevertheless, the algorithm has found all > the items known and 10 more which are displayed in the table But these observations suggest that the algorithm in fact does catch all the "good examples" in its range, and perhaps it's possible to prove this. Unfortunately, the webpage <http://www.terra.es/personal9/ismaeljc/hall.html>, offered "for more information", does not include details on the algorithm beyond what's in the NMBRTHRY announcement; and the paper > [JS] Jimenez Calvo, I. and Saez Moreno, G.: > Approximate Power roots in Z_m. > pages 310-323 in ISC 2001; G.I. Davida and Y. Frankel, eds.; > Berlin: Springer, 2001; LNCS 2200. (which may or may not contain enough information to figure out the Jimenez-Herranz-Saez method) is not easy to find. Can you please post/e-mail/URL further details and/or that GP program? One correction: > A detailed theoretical and computational account on this subject > can be found in [Elkies] where he published a table with > the 25 items known. Actually (as explained in that paper) infinitely many examples are known, since Danilov exhibited an infinite family of solutions of 0 < sqrt(x) < |x^3-y^2|. The next example in his family has x = 10^30 approximately, well beyond even the range of the [JHS] computation. --Noam D. Elkies

1 0

Re: [math-fun] Re: five, six, and eight
by asimovd＠aol.com 13 Dec '02

13 Dec '02

Hi, Dylan. << Consider the triangulations of a pentagon. There a 5 triangulations, and if you connect two triangulations that share a triangle, you get a 5-cycle. >> I'm pretty sure you mean the triangulations that don't add a vertex, right? In other news, how are you? Any chance of my gettting to see you -- and possibly meet Ken -- when you're in town this month? Best regards, Dan

1 0

Re: [math-fun] Mathematical Presidents
by Henry Baker 13 Dec '02

13 Dec '02

>From the ASME (Mechanical Engineering???): "Carter began his career as a nuclear engineer after receiving a B.S. degree from the U.S. Naval Academy in 1946 and undertaking graduate work in nuclear physics at Union College. He served as a submariner and worked on the Navy's nuclear submarine program." To account for his recent activities, we can only presume that he received a bit too much radiation through his brain in those early days. At 11:42 PM 12/12/02 -0800, Thane Plambeck wrote: >I remember Jimmy Carter frequently being described as a "nuclear engineer," >but that was when it was popular to think that Ford was a bumbler.

1 0

[math-fun] Re: Lacings continued
by Pfoertner, Hugo 13 Dec '02

13 Dec '02

-----Original Message----- Von: Antti Karttunen [mailto:karttu@megabaud.fi] Gesendet am: 13 December, 2002 15:08 An: njas(a)research.att.com Cc: Pfoertner, Hugo; seqfan(a)ext.jussieu.fr; math-fun(a)mailman.xmission.com Betreff: Re: Lacings continued <sequence definition snipped> > >Dear Neil, > >Because you have counted 132546 as a solution in A078602, I reckon that your condition >"and cannot pass though three consecutive and adjacent eyelets that are in a line" >means that "cannot pass _in order_ three consecutive and adjacent eyelets on >the same side." If we want to count "real world" lacings things like the "132546" config should be excluded from being counted. I would like another condition that applies to all lacings I have seen: >From each eyelet there is at least one path to the opposite side. This condition should guarantee that there is a closing force on the eylet and not just a force in tangential direction as it is the case with eyelets 3 and 4 in the 1322546 config. >I think here it is a question of simply counting of permutations with some forbidden >subsequences. I.e. in the case a(3) = 21, we have permutations of [1..6], but >with the first and the last element fixed as 1 and 6, so actually counting the >permutations of [2,3,4,5], but discarding the cases where we would have a >either an increasing [i,i+1,i+2] or decreasing subsequence [i+2,i+1,i] >(where i+2 is either <= n or i > n) e.g. from 4! = 24 permutations of >[1,2,3,4,5,6] with 1 and 6 fixed we have to further discard the three cases >[1,2,3,4,5,6] (violates the condition on both sides), [1,2,3,5,4,6] (on the left side) >and [1,3,2,4,5,6] (on the right side), so we are left with 24-3 = 21 solutions. > >Reasoning on these lines should easily (?) lead to a formula for A078602. >At least it's now very easy to write a program in a declarative language >like Prolog or Haskell to count the solutions. > >Then regarding Hugo's point about whether the lace enters each hole >(Btw, some of his pictures resemble my son's attempts at this difficult art...) >from the outside or inside, doesn't this just add an extra factor >of 2^(2n) to the count? That would be the case, if all combinations were allowed. I want to exclude inside/outside changes if the lace connects two eyeholes on the same side. This complicates things. >Regarding which lace goes underneath or over which other, it seems more >complex. I don't know whether thinking in terms of braids actually clarifies >or confuses this issue: > >http://mathworld.wolfram.com/BraidGroup.html >and >http://www.brown.edu/Students/OHJC/topology/index.html >and >http://math.ucr.edu/home/baez/braids.html > >(at least one could borrow some notation from there?) I'll try to learn something from the links. > > >Terveempänä, > >Antti Karttunen Best Regards, Hugo Pfoertner

1 0