July 2004 - mathfun@mailman.xmission.com

[math-fun] More innumeracy in high places
by David Gale 08 Aug '04

08 Aug '04

The quote below appeared in a column in the International Herald Tribune by Michael Johnson described as "a former correspondent for Business Week and The Associated Press." The column head was "2,3,5,7,1,13,,19,23 What comes next?" The article was about the search for a ten million digit prime. About halfway down we find, "It was Euclid who started it all by identifying the smaller primes 2,300 years ago and predicting that the number of primes would turn out to be infinite [my italics] ." I don't know, wouldn't you think even the man or woman on the street should be able to digest Euclid's proof? I'm tempted to go out on the street and try to find out. "Look, Mary, suppose there were only a zillion of them. Well then, multiply them all together and add 1and you see . . . " What do you all think? David G

5 4

[math-fun] Distance matrix for symmetric group S_n
by Daniel Asimov 30 Jul '04

30 Jul '04

Let the (usual) distance on the symmetric group S_n be given by d(p,q) = the least # of transpositions that will change p into q. Just did some little calculations with the symmetric group S_4 and found the # of perms at distance = d from 1234 to be these: dist: 0 1 2 3 4 5 6 #: 1 3 5 6 5 3 1 a) I'm wondering if there's a simple formula that will give this table for any S_n, including which perms are at what distance. I can do this by hand, but wonder if there's a faster algorithm than winging it -- and of course would want to use a computer for large n (even pretty small n are large in this question). b) Even better, is there a simple formula to determine the distance between any two permutations p, q in S_n ? (I guess it boils down to the distance from p(q^-1) to the identity, which would come from the answer to a). But still it would be nice to quickly calculate all n!*(n!-1)/2 distances for tractable n.) Dan

4 4

Re: [math-fun] Distance matrix for symmetric group S_n
by Daniel Asimov 30 Jul '04

30 Jul '04

Thane wrote: << I'm confused. Shouldn't there be 4 \choose 2 = 6 permutations at distance one? Daniel Asimov wrote: Let the (usual) distance on the symmetric group S_n be given by d(p,q) = the least # of transpositions that will change p into q. Just did some little calculations with the symmetric group S_4 and found the # of perms at distance = d from 1234 to be these: dist: 0 1 2 3 4 5 6 nmbr: 1 3 5 6 5 3 1 >> Maybe I didn't express the definition of distance clearly, and/or maybe I'm using confusing notation. But there are only 3 transpositions one can apply to 1234: (12),(23), or (34). The 3 perms. at distance = 1 from 1234 [Note: 1234 doesn't mean the cycle (1234); it's the identity perm., the result of applying the identity to the initial position of 4 things, which I'm calling 1234] are the following: 2134, 1324, or 1243. (By the same token, *any* element of S_4 should also have exactly 3 perms. at distance = 1 from it.) Hope this clarifies things. --Dan

1 0

[math-fun] Four Colours Suffice ...
by Guy Haworth 27 Jul '04

27 Jul '04

Apologies if this noddy q has been covered before. What are the most recent, and 'best', accepted proofs of the 4C Theorem? The proof by Robertson, Sanders, Seymour and Thomas (1996) has been published in a reputable journal, seems to be leaner and make more use of formal proofs than Appel/Haken/Koch (1977), and presumably is accepted. I see references to a proof by Ashay Dharwadker (2000). Has this been accepted or refuted? Guy

1 0

[math-fun] median5
by Richard Schroeppel 26 Jul '04

26 Jul '04

Not exactly elegant, but no worse than best-so-far, and one fewer kind of operator: median(a,b,c,d,e) = min( max(abc),max(abd),max(abe),max(acd),max(ace), max(ade),max(bcd),max(bce),max(bde),max(cde) ) Another puzzle: It turns out that median-of-5 (Med5) can be constructed from the median-of-3 (Med3) function. One way is Med5(A,B,C,D,E) = Med3( A, Med3(B,C,D), Med3(B,E, Med3(A,C,D)) ). [All median-of-odd functions can be built out of any single one. In fact, any non-trival, 0-1 symmetric, monotone-nondecreasing, boolean function can be built from Med3, and vice versa. This includes weighted medians, and many others.] The expression above for Med5 in terms of Med3 is minimal. But it's far from obvious that the expression is right, and it sure doesn't look symmetrical. Even though Med5 is symmetrical in all permutations of the arguments, the expression has only the C:D swap symmetry. The puzzle is to come up with a better expression. Ideally it would exhibit full symmetry and be obviously correct. But even just having some additional symmetry would be an improvement. [My proof of the formula above is by cases in the boolean environment: The cases are C/=D, and C=D=0. Plus the lifting principle, that boolean -> also true for total ordering. Also less than elegant.] Rich rcs(a)cs.arizona.edu

2 1

[math-fun] median of five
by Marc LeBrun 26 Jul '04

26 Jul '04

For distinct a,b,c you can express their median using min, max and arithmetic operators by a + b + c - min(a,b,c) - max(a,b,c) Can you construct something elegant for a,b,c,d,e?

3 2

[math-fun] two more denestings
by Bill Gosper 25 Jul '04

25 Jul '04

[Sorry for the missing "Fractal coordinates" subject line. And so is Stan Isaacs for our stage-whispered puzzle business.] (c1) (fancy_display:false,showtime:true,sqrt(4^(3/7)-1),%%=subst([7=s,s=7],denest_radicals(%%))) Time= 22913 msecs 6/7 5/7 3/7 1/7 3/7 - 2 + 2 + 2 + 2 2 - 1 (d1) sqrt(4 - 1) = --------------------------------- sqrt(7) (c2) (sqrt(5^(6/7)-132*5^(1/7)+164),%%=denest_radicals(%%)) Time= 420 msecs 6/7 1/7 (d2) sqrt(5 - 132 5 + 164) = 6/7 5/7 3/7 2/7 1/7 - 2 5 + 2 5 - 5 + 6 5 - 2 5 - 2, the latter is the positive square root yet has four of its six terms negative. Still no luck with sqrt(binomial) = (>=hex)anomial. --rwg senatorial rationales

1 0

[math-fun] is math a sport?
by Thane Plambeck 24 Jul '04

24 Jul '04

http://slate.msn.com/id/2103903/ Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.plambeck.org

1 0

[math-fun] Fractal coordinates
by Mike Stay 23 Jul '04

23 Jul '04

To specify a point in a two-dimensional space, we use two coordinates. I can't find any reference on how to specify a point in a fractional-dimensional space. Do any funsters know? http://www.cut-the-knot.org/do_you_know/dimension.shtml gives an example of a fractal with rational Hausdorff dimension, 3/2. Apparently, one can specify three points on the curve with two coordinates. I've no idea how one would approach the Koch curve. -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

4 3

[math-fun] (no subject)
by Bill Gosper 23 Jul '04

23 Jul '04

ES> The Koch curve is homeomorphic >to a circle, and can be represented as a Fourier series. > z(t) = x(t)+ i y(t) = sum(a[n] exp(i n t),n=-inf..inf). >A point on the curve is specified by the single coordinate t. The >representation is not unique, because you are free to choose the "speed >s(t)" at which the curve is traced. Bill Gosper has found explicit >expressions for the Fourier coefficients. Even including a "dimension" parameter D, which spacefills when D=2. So, as shown by Peano, you can specify a 2D point with 1 coordinate. Infinitely often, there are three ways to do it. Of course, if you've a high tolerance for disconinuity, just interlace the digits of x and y to make a single number t. --rwg PS, one can find exact values of z(rational) using hashcoding to detect cycles in the recursive (e.g. Koch) definition of the "curve". Equating these to the Fourier series produced two of the recondite identities in www.tweedledum.com/rwg/idents.htm vaticinate <-> inactivate

1 0