September 2003 - mathfun@mailman.xmission.com

[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

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

24 Sep '03

Dylan Thurston wrote: > On Tue, Sep 23, 2003 at 11:43:33AM -0700, Richard Schroeppel wrote: > > Similar questions exist for graphs & other math objects. > 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. No, it isn't (unless I've missed a very surprising very recent breakthrough). It's a long-standing open problem. Because the graph isomorphism algorithms of unproven polynomiality are so good, it's conjectured that graph isomorphism is strictly easier than NP-complete (by people who are willing to conjecture that NP > P). Some people even conjecture it's P (even without conjecturing NP = P). You may be thinking of subgraph isomorphism, which is NPC, but there the hard part is finding the subgraph, not the isomorphism. (In the usual proof, the test graph is a complete graph, for which isomorphism is easy. > Is there a way of stating a finite-group-isomorphism problem so that it > is decideable? Is it then NP-complete? If you're given the multiplication table, it's certainly decidable. I suspect it's more likely to be polynomially related to graph isomorphism than NP-complete (but I haven't really worked on it). Dan

1 0

RE: [math-fun] distinguishing groups
by Andy Latto 24 Sep '03

24 Sep '03

> 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. Are you sure of this? Eric Weisstein's World of Mathematics, at http://mathworld.wolfram.com/GraphIsomorphismComplete.html, says ______________________________________________________ Graph Isomorphism Complete There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. In fact, the problem of identifying isomorphic graphs seems to fall in a crack between P and NP-complete, if such a crack exists (Skiena 1990, p. 181), and as a result, the problem is sometimes assigned to a special graph isomorphism complete complexity class. References Skiena, S. "Graph Isomorphism." 5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 181-187, 1990. _______________________________________________________ Was there a recent result that didn't make it into World of Mathematics showing that Graph Isomorphism is NP complete? The fact that graph isomorphism "seems to" not be in P means that no-one has yet found a set of simple, easy-to-compute properties that will distinguish graphs. That doesn't mean that some clever person won't find such a set in the future, showing graph isomorphism to be in P in the process (and doing this won't show that P=NP). Andy Latto andy.latto(a)pobox.com

1 0

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

24 Sep '03

John Conway <conway(a)math.princeton.edu> wrote: > On Wed, 24 Sep 2003, Dan Hoey wrote: > > I looked at your classification of groups of order 16 and verified > > your translation of the smaller anonymous groups I found. In hopes of > > identifying this group, I found its derived subgroup 2^4 . > This must be a typo for 2^2 ? No. I'm trying to describe the 48-element group with order spectrum [1,15,32,0,...,0]. Gap claims its derived subgroup (which it defines as the subgroup generated by the commutators) is the 16-element group with order spectrum [1,15,0,0]--that's 2^4. Could GAP be mistaken, or am I just spreading confusion? Thanks for explaining this stuff. I'm really in the dark about being able to describe the group I'm talking about. Dan

2 1

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

24 Sep '03

While I've got the Groupies' attention, let me bring up another puzzle that's been bothering me for 40 years or so. Can two non-isomorphic groups always be distinguished by some extrinsic property? For any group, we can find a number of derived objects: The order, the collection of element orders, the center, the commutator subgroup, the diagonal subgroup (generated by squares), &c. This process can be carried quite a ways, defining some pretty fancy concepts. Bill Henneman once explained the Frattini subgroup to me as "the set of useless generators". If you write out a notion like this in primitives, you are soon knee- deep in quantifiers. My question can be restated as: If two groups have enough of these concepts matching, are they isomorphic? Can the matchings be used to compute an isomorphism? For finite groups, I can check isomorphism in time roughly N^(log2(N)). The extrinsic properties might give a faster check. Similar questions exist for graphs & other math objects. Rich

3 2

[math-fun] Steve Finch's new book
by David H Bailey 24 Sep '03

24 Sep '03

I just got a copy of Steve Finch's new book "Mathematical Constants". This is chock-full of info, much of which is new to me, on scores of interesting math constants, including constants that arise in analysis of continued fractions, prime numbers, approximation theory, Ising models, digital search trees, chaos theory, probability theory, and more. This is a very nice book. Thanks Steve for taking the time to produce this. David H Bailey david(a)dhbailey.com

1 0