September 2003 - mathfun@mailman.xmission.com

Re: [math-fun] Kissing number (again).
by Dan Hoey 26 Sep '03

26 Sep '03

> My 4-D intuition is certainly no good, so I was wondering if what seems > would work in 3D would carry over to 4D (about whether or not it is > sufficiently general for a ball to touch the maximum number of other > balls). But let me ask this about the "continuum", and I'll use the 3D > analogy. > Suppose you've got a few balls touching the central one and you're > finding the places where you can add another one. The simplest > approach would be to find all of the places where it touches the > central ball and two others, but that isn't sufficiently general. No, it isn't. Your problem is not geometry, it's logic. You can't assume that the new ball will touch more than one of the previously placed balls (and you can't even assume _that_ just by saying so, you have to prove it--see below). > Consider the new ball touching the center ball and is in contact > with ball A. You can't assume that. It might be in touch with just one of the previously-placed balls, and you can't even guarantee which one. > Swing it one way (staying in contact with ball A and the central > ball) until it touches ball B. But your "swinging" it is not general, because it might interfere with the further placement of other balls. If you interfere with future placements, your solution is not general, even in two dimensions. The way you can guarantee that each ball touches at least two others, one of them previously placed, is this way: Hypothesize a complete kissing arrangement of N>2 spheres. I will prove there is a connected kissing arrangement in which every ball touches at least two others, by modifying the given arrangement: 1. If the arrangement is not connected, you can move one connected component as a unit until it touches another ball. 2. If ball A touches only ball B, then ball B must touch some ball C (otherwise case 1 would hold). You can swing ball A around B until A hits some other ball-- perhaps not C, but some ball. This modification increases the number of adjacencies by 1, so if you repeat it as long as there is a ball touching fewer than two others, it will terminate in at most (n-1)(n-2)/2 + 2 steps, because with that many adjacencies every ball must touch at least two others, QED. This _allows_ you to search for arrangements by placing each new ball so it touches one previous ball somewhere. If you further restrict your choice. you invalidate the entire effort, since you might not find an arrangement even if one exists. I looked at trying to modify this for four dimensions, and I find that you can prove that every ball must touch at least two others. Same in K dimensions: every ball must touch at least two others. You might have all N balls in a loop, so you have to guess each ball but the first, second, and last with K-1 degrees of freedom. You can't do better with "geometric intuition". John was right, of course. Dan

3 2

Re: [math-fun] Kissing number (again).
by Dan Hoey 26 Sep '03

26 Sep '03

Oops! I wrote: > Jud McCranie wrote: > > Consider the new ball touching the center ball and is in contact > > with ball A. > You can't assume that. It might be in touch with just one of the > previously-placed balls, and you can't even guarantee which one. I'm sorry, I misread "center ball" as one of the ones you placed. You can indeed choose the new ball so it is touching the kissed ball and one previously placed ball A. But to do even that, you have to prove at least part of the theorem from my last message. > > Swing it one way (staying in contact with ball A and the central > > ball) until it touches ball B. Swing it the other way until it > > touches ball C. Now would it be the case that only certain areas > > in that swing need to be considered? Would it be that, say, any > > position from 0 to 0.1x is essentially the same because it makes > > no essential difference in how the rest of the balls are placed, > > and 0.1x to 0.36x are essentially the same, etc? If so, that > > would be how it can be reduced to a finite number of cases. You really do have to consider the whole arc. There is a way to make the number of cases finite, and that is to say, "The new ball G is at some unspecified place on this epsilon-arc." You can't say that it makes "no essential difference" where it is, but you can say the difference it makes is no greater than the diameter of the set of places it could be. In the future, when you're "swinging a newer ball around G," you will have to take account of not really knowing where you placed G, so the space of possible tangencies to G has positive area, and you have to say "some unspecified place in this epsilon-patch" instead of "along this epsilon-arc". And at the end, you won't usually have a packing, because you have to overpack to take account of the uncertainties. All you can say is that, if you end up with a sufficiently great amount of overpacking, that there couldn't have been a packing of that many balls in the first place. Dan

2 1

Re: [math-fun] Kissing number (again).
by Jud McCranie 26 Sep '03

26 Sep '03

At 08:11 AM 9/26/2003, John Conway wrote: > In fact, they were quite valid, except that I think I mistakenly >described the number of cases for each sphere (after the first few) >as "a 3-dimensional continuum", when it's really only 2-dimensional. >Jud's method is indeed fallacious. > > In 3 dimensions, it would probably get the correct kissing number >of 12, and so maybe leave the fallacy undetected, but almost certainly >the fallacy would be made manifest in the 4-dimensional case by the >fact that it would "prove" the kissing number to be < 24. My 4-D intuition is certainly no good, so I was wondering if what seems would work in 3D would carry over to 4D (about whether or not it is sufficiently general for a ball to touch the maximum number of other balls). But let me ask this about the "continuum", and I'll use the 3D analogy. Suppose you've got a few balls touching the central one and you're finding the places where you can add another one. The simplest approach would be to find all of the places where it touches the central ball and two others, but that isn't sufficiently general. Consider the new ball touching the center ball and is in contact with ball A. Swing it one way (staying in contact with ball A and the central ball) until it touches ball B. Swing it the other way until it touches ball C. Now would it be the case that only certain areas in that swing need to be considered? That is, suppose that the new ball swings through x degrees going from B to C. Would it be that, say, any position from 0 to 0.1x is essentially the same because it makes no essential difference in how the rest of the balls are placed, and 0.1x to 0.36x are essentially the same, etc? If so, that would be how it can be reduced to a finite number of cases. Like I said, I have no 4D intuition, so maybe higher than 3D is to unconstrained for that to work.

2 1

Re; [math-fun] Kissing number (again).
by Dan Hoey 26 Sep '03

26 Sep '03

John Conway <conway(a)math.princeton.edu> wrote: > The feeling that I'd expressed too strongly my criticisms of Jud > McCranie's proposed attack on the kissing number problem somehow > convinced me that they were wrong, and led me to apologise.... You know, I had been about to do something like that, too. I think it was all the "wolg'ing that was so irritating. A little "wolg" goes a long way, and after two "wolg"s and an "etc" I was about to "wolg" all over my keyboard. But looking closer, I think there's something correct in Jud's idea, perhaps new or perhaps not. It might even be possible to use it to (correctly) prove bounds on the r-kissing number (how many radius-r balls can kiss a unit ball in k dimensions) for which I'm sure there are plenty of open cases. First, let's try it without using symmetry or requiring any adjacencies of the balls (except, of course, to the central one). Quantitize the space of ball centers into small pieces p1,p2,...,pm. This could be done as coordinate-wise, so that each pi is the intersection of a dimension-k box with the (1+r)-sphere, or perhaps there is a better way of chopping up the space. A pair of pieces (pi,pj) is admissible if they contain respective points (xi,xj) at a distance of at least 2r. If that's too hard to test, admissiblity standards can be loosened. For instance, we could call (pi,pj) admissible if the underlying boxes contain an appropriate pair of points. We then exhaustively search for a set of n pieces that are pairwise admissible. If there is no such set, then the (r,k) kissing number is less than n. Of course, this doesn't prove the converse. But I think that if the kissing number is less than n, then there is a minimum overlap epsilon that will occur in any configuration of n spheres. If we require the pieces (or their boxes, in the loosened regime) to have dimension at most 2 epsilon, then the search for a pairwise adminssible subset will fail. This can be improved for efficiency. If n >= k I think that we can require each ball to kiss k-1 others in addition to the central one. If that's incorrect, we can at least require some adjacencies. This will allow us to require that adjacent balls be mapped to pieces that contain respective points (xi,xj) at a distance of exactly 2r. Other reductions of the search space are possible from symmetry. I imagine this method will be intractible in the interesting cases, but at least it's correct. Dan P.S. Thanks Hartmut and JHC for reminding me that conjugacy induces a homomorphism! --D[o]H

5 7

Antwort: Re: [math-fun] non-square products of squares?
by hartmut.holzwart＠allianz.de 26 Sep '03

26 Sep '03

ab=x°2 => ba = b(ab)b°-1 = (bxb°-1)(bxb°-1)=y°2 Cheers, Hartmut Dan Hoey <Hoey(a)aic.nrl.navy.mil>@mailman.xmission.com on 26.09.2003 11:39:12 Bitte antworten an math-fun <math-fun(a)mailman.xmission.com> Gesendet von: math-fun-bounces(a)mailman.xmission.com An: John Conway <conway(a)math.princeton.edu> Kopie: math-fun <math-fun(a)mailman.xmission.com> Thema: Re: [math-fun] non-square products of squares? 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 _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

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