September 2003 - mathfun@mailman.xmission.com

[math-fun] odometer word game
by Richard Schroeppel 03 Jun '04

03 Jun '04

zimb zinc chromatic chromatid Rich

2 1

[math-fun] nonobviously integer sequence
by R. William Gosper 09 Oct '03

09 Oct '03

Let a and c be integers. "Shew that" F := 1, F := a c - 1, F := 0 1 n 2 (2 n + a - 3) ((2 c - 1) (2 n + a - 4) (2 n + a - 2) + (a - 2) ) F n - 1 (----------------------------------------------------------------------- 2 - (n - 1) (n + a - 3) (2 n + a - 2) F )/(n (n + a - 2) (2 n + a - 4)) n - 2 (note cubic denominator) is an integer sequence. Distantly related: it appears that [ n + 4 n + 5 ] [ - n, -----, ----- | ] F [ 2 2 | -4] = 1,6,57,701,10147,164317,2888282,54047434, 3 2 [ | ] [ 3, 2 ] is an integer sequence. The smallest prime factors go {},2,3,701,73,37,2,2,7,2,3,3,5,2,23,37,65306671610636210891,2, 31,3,3,19,2,2,3,2,3,7,3,3,2,2,7,2,67,5,... . Likewise, [ n + 5 n + 6 ] [ - n, -----, ----- | ] 4 F [ 2 2 | -4] = 4,25,228,2620,35164,527663,8613004, 3 2 [ | ] [ 4, 2 ] [ n + 6 n + 7 ] [ - n, -----, ----- | ] 15 F [ 2 2 | -4] = 15,99,891,9825,125085,1772775,27303603, 3 2 [ | ] [ 5, 2 ] [ n + 7 n + 8 ] [ - n, -----, ----- | ] 5 F [ 2 2 | -4] = 5,29,230,2260,25921,334105,4717653, 3 2 [ | ] [ 5, 3 ] More generally, [ n + k + 1 n + k + 2 ] [ n + k + 2 n + k + 3 ] [-n,---------,---------| ] [-n,---------,---------| ] F [ 2 2 |-4] & F [ 2 2 |-4] 3 2[ | ] 3 2[ | ] [ k, 2 ] [ k, 3 ] appear to have bounded denominators. --rwg Does OEIS list sequences not proven integral?

4 5

Re: [math-fun] More on sphere packing
by Dan Hoey 29 Sep '03

29 Sep '03

John Conway <conway(a)math.princeton.edu> wrote: > I didn't read the piece I snipped, but presume that it is supposed > to guarantee to find (in particular) a 25-sphere configuration in 4D if > one exists. I can't really see how it can do that, while still being > approximate. Do you think it can? No, of course not. Why would you presume I attempt such a guarantee, when it is patently impossible? I claim that if there are no (25,4,1+2epsilon) configurations, the algorithm would say so. This is important, because if there are no (25,4,1) configurations, there must be an epsilon for which there are no (25,4,1+2epsilon) configurations. I also claim that every (25,4,1) configuration is represented in the output by an approximation that describes the coordinates of the centers to within epsilon. Each of these can be converted to a (25,4,1-2epsilon) configuration. Dan

2 1

Re: [math-fun] More on sphere packing
by Dan Hoey 29 Sep '03

29 Sep '03

I wrote: > Why would you presume I attempt such a guarantee, > when it is patently impossible? Possibly because about half of what I say has errors in it, including my latest attempt. What I meant to say was summed up correctly by Andy Latto. Dan

1 0

RE: [math-fun] More on sphere packing
by Andy Latto 29 Sep '03

29 Sep '03

> -----Original Message----- > From: John Conway [mailto:conway@Math.Princeton.EDU] > Sent: Monday, September 29, 2003 3:34 PM > To: math-fun > Subject: Re: [math-fun] More on sphere packing > > > On Mon, 29 Sep 2003, Dan Hoey wrote: > I didn't read the piece I snipped, but presume that it is supposed > to guarantee to find (in particular) a 25-sphere > configuration in 4D if > one exists. I can't really see how it can do that, while still being > approximate. Do you think it can? I don't think that one of these epsilon-algorithms could be guaranteed to find a 25-sphere configuration if one exists, because if the algorithm required exact placement, it wouldn't be found, no matter how small epsilon was. But I can imagine an algorithm of this sort with the following property: If a 25-sphere configuration exists, then the algorithm will find 25-sphere configurations for spheres of size 1 - epsilon that all touch a central sphere of size 1, no matter how small epsilon is. Finding such configurations for small epsilon would lend credence to the theory that there is a 25-sphere configuration with spheres of size 1, and examination of the configuration of spheres of size epsilon may help guess the 25-spheres-of-size-1 configuration. Conversely, if there is no 25-sphere configuration, then compactness shows that there is no 25-sphere configuation for spheres of size 1 - epsilon for sufficiently small epsilon, so a program of this sort could provide a proof if epsilon is chosen correctly. Andy Latto andy.latto(a)pobox.com

1 0

Re: [math-fun] More on sphere packing
by Dan Hoey 29 Sep '03

29 Sep '03

I'm quite sorry that I do seem to have gotten the signs on my epsilons backwards. The relevant paragraph should have read: > At any rate, I would like to mention a modification to the approach I > outlined on Friday. In this approach we place points in k-cells of > side epsilon that intersect the given k-1-sphere. I will assign a > point a "nominal location" of the center of its cell. However, since > the point may differ from that location by epsilon.sqrt(k)/2, we > must enforce a separation of points by r - epsilon.sqrt(k). In > addition, since we require that each point be at the minimum distance > to at least two neighbors, we count those points within > r + epsilon.sqrt(k) of the given point toward the count of required > near neighbors. The output of the program would be: 1. If there is an (n,k,r) configuration, to find (n,k,r-eps.sqrt(k)) configurations for arbitrarily small eps, and 2. I there is no (n,k,r) configuration, to prove it by running out of cases when eps < (r-maxr(n,k))/sqrt(k) . Here maxr(n,k) is the maximum r' for which an (n,k,r') configuration exists. Perhaps case 1 would usually be faster with Gosset, but as I understand it Gosset might fail to find a configuration even when one exists. Dan

2 1

Re: [math-fun] A use for Jud's method
by Jud McCranie 29 Sep '03

29 Sep '03

At 12:57 PM 9/29/2003, John Conway wrote: > There doesn't seem to be any difference to me. Think of them >as unit vectors, whose inner products may not exceed such-&-such. I'm very rusty on that, having not used it in about 25 years. That's the kind of thing for which I might need help. At first I was thinking of using Cartesian coordinates on the spheres then I thought that using spherical coordinates on the caps would probably be better, but I haven't worked out any details. Most of the time used by the program will be in calculating the coordinates of a sphere/cap that touches the required number of others. This is where the method used will matter. It doesn't have to be optimal (as far as calculation speed) but it does need to be good.

1 0

Re: [math-fun] More on sphere packing
by Dan Hoey 29 Sep '03

29 Sep '03

"Allan C. Wechsler" <acw(a)alum.mit.edu> wrote (of Jud McCranie's conceptual program in four dimensions): > The central problem is the size of the configuration space that must > be explored: 24 or 25 spheres jostling around, each contributing 3 > degrees of freedom to the configuration space. JM proposed, if I > read him right, to prune this space by considering only > configurations of a certain special kind, in which the configuration > may be built by adding each new sphere in the 'socket' formed by > three previously-placed spheres. (This is hard to visualize, but in > four-space, you need three other spheres to form a well-defined > socket with no degrees of freedom.) Enumerating such configurations > would be much easier than searching an enormous 75-dimensional > configuration space. It may be that Jud made such a proposal, but I am sure he no longer believes it to be proved correct. In fact, I suspect he may have proposed a somewhat less dubious proposal that was misunderstood. The problem arises from confusion over whether we are counting the original unit 3-sphere (in which case we would say four hyperspheres are required to form a socket in R^4) and over whether we are talking about packing in R^3 (using ordinary 2-spheres) or in R^4 (with 3-spheres). (In addition, I think there is some confusion about this nomenclature--I understand the surface of a ball in R^4 to be called a "3-sphere", but Allan calls them 4-spheres, so we can be sure confusion abounds.) I know that some of my respnoses were based on confusion over whether a given description includes the original unit sphere. At any rate, I believe we will do better to pack _points_ on the unit k-1-sphere (in R^k) with a prescribed lower bound r on the distance between points. This translates directly into the packing of kissing k-1-spheres of radius r/(2-r), if I've done my algebra correctly. At any rate, I would like to mention a modification to the approach I outlined on Friday. In this approach we place points in k-cells of side epsilon that intersect the given k-1-sphere. I will assign a point a "nominal location" of the center of its cell. However, since the point may differ from that location by epsilon.sqrt(k)/2, we must enforce a separation of points by r + epsilon.sqrt(k). In addition, since we require that each point be at the minimum distance to at least two neighbors, we count those points within r - epsilon.sqrt(k) of the given point toward the count of required near neighbors. Now, searching for these points with approximately n(k-1)-k(k-1)/2 degrees of freedom may be fairly intractible, but we may get some relief from the minimum and maximum spacings where the packing is tight. I was concerned that this relief might happen too far down the search tree to be helpful, and I would like to share an idea that might help make the relief more generally available. The idea is basically to start with a large epsilon, and to go to epsilon/2 by cutting all the cells in 2^k pieces. Most of the pieces go away (because they no longer intersect the k-1-sphere), and the reduced epsilon should also prune the cases. As epsilon is reduced, the configuration becomes more and more constrained, and we may be able to identify places where the constraints are loose. I imagine the looser spheres might in fact not need to have their cells cut as much after a certain point. This leads to a sort of quad-tree approach to the search space. I'm curious about how this approach might work (or how it may have worked already, since it's a fairly standard approach to geometrical searching). I remark that it not could not only tell us which (n,k,r) are not feasible, but it could provide witnesses for which (n,k,r-epsilon.sqrt(k)) are feasible. Dan

2 2

Re: [math-fun] A use for Jud's method
by Jud McCranie 29 Sep '03

29 Sep '03

At 05:59 PM 9/28/2003, John Conway wrote: > I'm sure the program would also find a few unforeseen things that >would amply justify the trouble of writing it. How about it, Jud? I think I will try it, if I can appeal to this group for some help on geometric details if I need to. I never claimed that the method would work, I just thought it might. But we can see how far it can go. I plan three phases: 1. 3D, unit spheres if that works, then: 2. 3D, general radius and then maybe: 3. 4D case. I think it will be easier to work with the equivalent spherical caps instead of spheres. Figure on giving me about a month, I have plans for next Saturday and all of the next two weekends after that. (And I've been half sick since last Tuesday. My wife asked "which half?". I said the top half.)

2 1

[math-fun] packings on the surface of a sphere
by Richard Schroeppel 29 Sep '03

29 Sep '03

Neil Sloane's web page has tables of packings. http://www.research.att.com/~njas/packings/index.html#I surface of sphere http://www.research.att.com/~njas/packings/dim3/ coordinates The first URL has (among many other things) his best results for the maximum minimum angle for K points on the surface of an ordinary sphere. The second URL points to numerical coordinates of the points. They seem to have been obtained numerically -- 20 digit floating point values, including some numbers that should probably be 0 but instead are small values like 10^-20. I didn't see any formulas, so these coordinates are good candidates for algebraic number recognition. More digits will be needed, but this shouldn't be a big problem. The tables don't mention proofs, although there are lots of references in other parts of the web page. One curiosity: There are two instances where K and K+1 points have the same angle, indicating that removing a point from the K+1 packing doesn't make room to expand the remaining K points. These are 5,6 and 11,12. I didn't see any more cases up to 130 points, the table limit. The higher dmensions had some longer runs, where K...K+5 all had the same minimal angle. Is there a general "packings" web page? I had no idea Neil's tables existed -- they're pretty well hidden under the code phrase "spherical codes". Rich rcs(a)cs.arizona.edu

2 1