- mathfun@mailman.xmission.com - mailman.xmission.com

Re: [math-fun] non-square products of squares?
by Dan Hoey 26 Sep '03

26 Sep '03

This really is fascinating. I've been trying to follow along with Gap, and I ran into a problem because it takes about five or ten minutes to find all the elements of Aut(2^4). I kept trying to figure out what was wrong, where if I waited I would have had it. So now I can calculate semidirect products 2^4:3[h], where h is a homomorphism from 3 to Aut(2^4), and there are the three you promised: The canonical 2^4:3, the direct product 2^4x3, and... well, one that's halfway in between. I don't know if it's worth giving it a special name. Anyway, I still haven't found any group with a greater proporition of (a,b,ab)=(square,square,nonsquare) than 1/6, except for the 5/24 we get from 2^4:3. In fact, the proportion seems to go down, so perhaps 2^4:3 is unique. I have no idea how one might prove it, though. Here's a poser that came up while I was writing the code to search for nonsquare products. Can it ever happen that (a,b,ab,ba)=(square,square,square,nonsquare)? I can prove it's impossible for finite groups, but what about infinite? Dan

2 1

[math-fun] math fun from politics
by John McCarthy 26 Sep '03

26 Sep '03

Texas University Shuts Down Bake Sale By Associated Press September 24, 2003, 11:17 PM EDT DALLAS -- Southern Methodist University shut down a bake sale Wednesday in which cookies were offered for sale at different prices, depending on the buyer's race or gender. The sale was organized by the Young Conservatives of Texas, who said it was intended as a protest of affirmative action. A sign said white males had to pay $1 for a cookie. The price was 75 cents for white women, 50 cents for Hispanics and 25 cents for blacks. . . . The group sold three cookies during its protest, raising $1.50. What are the possible distributions of buyers? Will this increase interest in politics among math students and increase interest in math among politically minded students.

5 4

[math-fun] 13 as a constant, With Moebius functions
by Ed Pegg Jr 25 Sep '03

25 Sep '03

I was recently intrigued by the fact that Sum[MoebiusMu[n]/n^s,{n,1,Infinity}] = 1/Zeta[s]. Since MoebiusMu[n] = -1, 0, or 1 ... and since there is a 1/Zeta[2] chance that it will be -1 or 1, I decided to look at how the numbers split up between -1 and 1. Define (for k from 1 to infinity), where Mu is the MoebiusMu function. My actual Mathematica code is at the bottom of the message. MuRatio[s] = Sum[If[Mu[k]=1,1,0]/k^s]/Sum[If[Mu[k]=-1,1,0]/k^s] MuRatio[2] = Sum[1/{k:Mu[k]==1}^2]/Sum[1/{k:Mu[k]==-1}^2] Then MuRatio[2] = 7/3 MuRatio[4] = 13 MuRatio[6] = 703/12 MuRatio[8] = 14527/59 MuRatio[10] = 524354/521 MuRatio[12] = 354333857/872492 MuRatio[14] = 6785975897/415603 Also Sum[Abs[Mu[k]]/k^2] = 15/Pi^2 Sum[1/{k:Mu[k]==1}^2] = 21/(2 Pi^2) Sum[1/{k:Mu[k]==1}^2] = 9/(2 Pi^2) --Ed Pegg Jr, www.mathpuzzle.com MuRatio[s_] := Total[Table[N[If[MoebiusMu[k]== 1,1,0]/k^s, 50], {k, 1, 1000000}]]/ Total[Table[N[If[MoebiusMu[k]==-1,1,0]/k^s, 50], {k, 1, 1000000}]]

1 0

Re: [math-fun] distinguishing groups
by Dan Hoey 25 Sep '03

25 Sep '03

John Conway <conway(a)math.princeton.edu> wrote: > My feeling is that the methods we used could be converted into > a formal proof that one could distinguish between any two given > candidate groups of orders < N in a time bounded by some power > of log N. [Note that that's weaker than saying "find which group of order > < N you have".] But it's the former problem that Rich is taking N^O(logN) to solve! I suspect you're at least going to have to multiply that log N by the sum of the orders of the generators, in case someone gave you generators of two huge cyclic groups and asked you to test eqality with the black box multiplier. But even doing it in provably O(N^c) would be an advance. I suspect that's going to run into the same sort of problem graph isomorphism has. There are methods that work well on a lot of graphs, and combining them _seems_ to work well on all graphs, but we can't prove there isn't an exception. Dan

3 3

Re: [math-fun] Kissing number in 4 dimensions claimed to be 24
by Jud McCranie 25 Sep '03

25 Sep '03

At 04:01 PM 9/25/2003, John Conway wrote: > Yes, of course. The same argument applies to solving the game >of Chess. If next week someone claims to have done that, I won't >believe them for the same reason, namely that the problem is so >big that their argument is more likely to be wrong than right. I think a computer search could succeed with the 4-D kissing number problem. I was contemplating it several years ago. Consider for a moment the 3-D version. Take a sphere to be the center sphere. WOLG, place a sphere touching it. WOLG, place the next sphere touching the center sphere and the first one, etc. Use standard backtracking/depth first search. I don't think there are too many possibilities to consider for the 4-D kissing number - far fewer than chess.

2 4

[math-fun] Kissing number in 4 dimensions claimed to be 24
by asimovd＠aol.com 25 Sep '03

25 Sep '03

I've just heard that Oleg Musin is circulating a paper in which he purports to prove that the kissing number in 4D is 24. ( For those unfamiliar with this problem: The kissing number K(n) in n-space is the maximum number of unit n-balls that can be simultaneously tangent to ("kissing") a given unit n-ball in n-space, such that when any two of these K(n) balls intersect, they are merely tangent to each other. Clearly K(2) = 6, and K(3) was a matter of much debate between Newton and Gregory (Gregory said it was 13, and Newton was right that K(3) = 12). It's amazing that this wasn't proved, however, until about 1875. It has been known for some time that K(4) must be 24 or 25. An arrangement for 24 has been known for a long time. The most symmetrical such arrangment of 24 4-balls all touching a 25th is described by assuming the 25th 4-ball to be centered at the origin, and the 24 "kissing" 4-balls to be centered at the 24 points having [2 coordinates = ±sqrt(1/2) and the other 2 coordinates = 0]. ) --Dan

3 3

[math-fun] 24 kissing, Riemann Hypothesis, 3N+1
by Richard Schroeppel 25 Sep '03

25 Sep '03

Dan writes ... > It has been known for some time that K(4) must be 24 or 25. An arrangement for 24 has been known for a long time. The most symmetrical such arrangment of 24 4-balls all touching a 25th is described by assuming the 25th 4-ball to be centered at the origin, and the 24 "kissing" 4-balls to be centered at the 24 points having [2 coordinates = +-sqrt(1/2) and the other 2 coordinates = 0]. This is a rotation of the 24 unit Hurwitz quaternions: The 8 usual +-{1,i,j,k} and the sixteen (+-1 +-i +-j +-k)/2. JHC remarks that he wouldn't trust a numerical geometric proof. I'll ask: Why not? It's a packing problem, and computer calculations might well provide a proof. I assume even John accepts computer searches for error correcting codes and similar packing problems as valid. --- I recently read the "popular" book Prime Obsession. It's an attempt to explain the Riemann Hypothesis to a layman. I've called it "popular" since I found it prominently displayed at Borders. I enjoyed it, particularly the historical chapters. (The author alternates history chapters with math chapters.) I haven't seen a serious attempt to explain complex variables to a non-mathematical audience in forever. I'm not in a position to say how well the explanation works, but it seems to be a good try. The graphs are good. There are a couple of typos. Only a few proof sketches. I recommend the book for the historical background. It will also serve as a very gentle introduction to RH for the interested funster, although many will find the math a bit thin. --- Jeff Lagarias has recently released a 50-page annotated bibliography for the 3N+1 probem. http://arXiv.org/abs/math/0309224 I was amazed that so much has been written about it. The conjecture has been checked to 2.5 x 10^17 by an ongoing distributed computing project at http://personal.computrain.nl/eric/wondrous. The lower bound for the size of a hypothetical new loop is now 630 million. Rich rcs(a)cs.arizona.edu

2 1

[math-fun] Primitive graph operations
by Tom Knight 24 Sep '03

24 Sep '03

I've been thinking a bit recently about representation and manipulation of graphical structure in computers, and specifically have a somewhat open ended question which some of you may have thought about. For matrix like operations, APL and Matlab provides a set of primitive ops (we can argue or not about how good they are...). What are the similarly "primitive" operations needed to flexibly create, modify, search, or otherwise manipulate graph structures? How do things change between directed and undirected graphs? Inquiring minds want to know.

2 1

[math-fun] distinguishing groups
by Richard Schroeppel 24 Sep '03

24 Sep '03

RCS> For finite groups, I can check isomorphism in time roughly N^(log2(N)). MLB> How's that? If you're given the groups in some reasonable form how can it take more than the N^2 required to completely compare them element-wise? Perhaps this time includes making the inputs presentable? I should speak more precisely: Given two finite groups, I can decide if they are isomorphic in time roughly N^(log2(N)). Actually, N^(2+log2(N)). The hard part is finding the isomorphism. Checking a candidate isomorphism is, indeed, O(N^2), maybe less. I'm assuming the groups are given as lists of the elements, perhaps named G0, G1, ... and H0, H1, ..., and that there are black boxes G*, G/, H*, and H/ that provide products and reciprocals in time 1. I'm also assuming that the objects are indeed groups, although that could be checked in O(N^3) (or maybe less?). To search for the isomorphism I, you begin by developing a list of generators for G. First, scan the elements of G to locate the identity Gi so you can ignore it. We maintain of list of elements of G that we've already generated, and their formulas. This list starts with {Gi}. Then build a list of generators one at a time. Take the first element of G that isn't in the already-generated list, and call it a new generator. Expand the generated list with the new generator, closing under G*. (Don't need to bother with G/, it's a finite group.) Each new generator at least doubles the size of the generated set, so the total number of generators is <= log2(N). In the case of the group (Z2)^K, the formula is exact. Now that we have a list Ga,Gb,... of generators for G, we start searching for an isomorphism with H. We guess I(Ga) = Hx, and calculate the portion of I generated by Ga->Hx. For those that are consistent, we continue with a guess for Gb->Hy, and so on. I guess this comes out to N ^ (2 + log2(N)) if we include the time to check each candidate I. If we were actually making a list of all automorphisms of (Z2)^K, it's nearly N^(log2(N)). The separate puzzles, How much work to check a group given as a table is really a group? and How much work to check an isomorphism given as a table between two known-to-be groups given as tables? are also interesting. Obvious upper bounds are N^3 and N^2, but maybe we can do better. Rich rcs(a)cs.arizona.edu

3 2

[math-fun] distinguishing groups - graph isomorphism
by Richard Schroeppel 24 Sep '03

24 Sep '03

On Tue, Sep 23, 2003 at 11:43:33AM -0700, Richard Schroeppel wrote: > Similar questions exist for graphs & other math objects. DPT>The graph isomorphism problem is known to be NP-complete, so any sort of properties that distinguish graphs is likely to be hard to compute. Is there a way of stating a finite-group-isomorphism problem so that it is decideable? Is it then NP-complete? I think you're referring to Subgraph Isomorphism, Is the graph G isomorphic to any subgraph of H? which was one of the original bunch of NP-complete problems. AFAIK, the NP-completeness of the Graph Isomorphism Problem remains an open question. I think the approach I outlined for checking group isomorphism can be adapted to graphs, but some work is needed. When a vertex Gv is conjecturally mapped to Hv, it implies a "distance from Gv" stratification of G, which must match a similar stratification of H. In the ordinary case, choosing maps for log2(N) points from G to H will define the full isomorphism by intersecting stratifications. But there may be extraordinary graphs to consider. In my comments about finite groups, I assume the group was given as a table or some equivalent, which sidesteps the undecidable question, Is this particular set of generators and relations a finite group? "My" group isomorphism problem is clearly within NP (guess a map, check it in time N^2), but may NOT be NP-complete. Similarly, the group non-isomorphism problem seems to be of unknown hardness: We'd like to say G/=H implies there's some checkable property or feature of G and H that distinguishes them. But John has indicated we're out of luck for the time being. Rich rcs(a)cs.arizona.edu

1 0