Wikipedia:Reference desk/Archives/Mathematics/2008 January 15

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 15

Game of Life

In Conway's game of life, what is the shortest-known period glider gun (psudo glider guns, made from filling gaps in a glider stream do not count)? Thanks, *Max* (talk) 02:28, 15 January 2008 (UTC).

According to this page, it's the period 22 gun I and Jason Summers found in 2000. —David Eppstein (talk) 02:39, 15 January 2008 (UTC)

I may have discovered a new period 20 diagonal rake. How do I verify whether it is known? *Max* (talk) 02:41, 15 January 2008 (UTC).

c/12 diagonal rakes based on Corderships have been known for some time.

The first c/4 diagonal puffer was found by Hartmut Holzwart in February 2004 and is period 28; it emits tubs and beehives but some other variations have since been found. In July 2005 David Bell used it as part of a breeder, by crashing the output of a c/2 rake into it to form a sequence of switch engines:

x = 155, y = 102
77boo$77bobo$77bo$80bo$80boo$80boo$79boo$75booboo$75bo4bo$75bob4o$79b
oo$79boo$79boo$81bob3o$77bobbo$76b5o6bo$76bobboo5bobo$74bobo10bo$73b3o
4bo$73bobboo$77b3o$77boo10bo$79bo8bobo3bo$77bobo8bobobbobo$70boo4boo
11bo4bo$69boo5boobo$71bo4booboobobboo$76b3obobobbobo$67boo3boobboo7bo
10bo$66boo3boo15bo6bobo3bo$68bobb3o14boo5bobobbobo$70b4o14boo6bo4bo$
69bobo15boo$68boo13booboo$68bobo12bo4bo$67bo15bob4o14bo$68boo17boo13bo
bo3bo$87boo13bobobbobo$87boo14bo4bo$89bo$85bobbo4bo$84b5o4bo$84bobboo
4bo16bo$82bobo12bo11bobo3bo$81b3o4bo7bobo10bobobbobo$81bobboo11bo12bo
4bo$85b3o$55bobo27boo$54bobbo29bo$53boo30bobo11bo17bo$52bo25boo4boo12b
obo3bo11bobo3bo$51b4o22boo5boobo10bobobbobo10bobobbobo$50bo4bo6bo16bo
4booboobo8bo4bo12bo4bo$50bobbo5boobo21b3obobo$50bobbo5bo15boo3boobboo$
51bo7bo14boo3boo$52b4obo6boo10bobb3o24bo17bo$53bo3bo4bo4bo10b4o23bobo
3bo11bobo3bo$54bo6bo15bobo25bobobbobo10bobobbobo$54b5obbo5bo8boo28bo4b
o12bo4bo$61b6o9bobo$54b5o16bo$54bo21boo$53bo3bobbo24boo26bo17bo$11bobo
12boo24b4obo25bo4bo23bobo3bo11bobo3bo$10bobbo10bo4bo21bo7boboo19bo29bo
bobbobo10bobobbobo$9boo7bo4bo26bobbo5bobbo6bo12bo5bo24bo4bo12bo4bo$8bo
6boobo4bo5bo20bobbo5bobbo4bobo12b6o9boo$7b6obbo7b6o21bo4bo4boo6boo5bo
20b4o$4boo7bo3b4o30b4o18bobo19booboo$3bo3b3obo4bo35bo21boo5bo14boo22bo
17bo$bbo3bo3boobobboobobbo30boo24bobo5bo31bobo3bo11bobo3bo$bbo5boo3bo
5bo6boo26bobbo22boo5bo31bobobbobo10bobobbobo$bb3o3b4obo7bobobb3o26bobo
27bobo32bo4bo12bo4bo$11bo9bo6bo57boo$bb3o6bobo7bo6bo5bo73boo$bo5bo5bo
8bo4bo4bobo3boobboobboobboobboobboobboobboobboobb3oboo27bobbo3b3o$o3b
oobo3boo11boo7boo3boobboobboobboobboobboobboobboobboobb4obbo27boo6bo
10bo17bo$o3bo6b3o62boboo35bo10bobo3bo11bobo3bo$o3boobo3boo11boo7boo3b
oobboobboobboobboobboobboobboobboobboo50bobobbobo10bobobbobo$bo5bo5bo
8bo4bo4bobo3boobboobboobboobboobboobboobboobboobboo34boo15bo4bo12bo4bo
$bb3o6bobo7bo6bo5bo75bobbo$11bo9bo6bo80boo$bb3o3b4obo7bobobb3o78bo$bbo
5boo3bo5bo6boo50boo27bo26bo17bo$bbo3bo3boobobboobobbo54booboo25bo4bo
20bobo3bo11bobo$3bo3b3obo4bo61b4o6boo19b3o21bobobbobo10bobo$4boo7bo3b
4o58boo6boob3o41bo4bo12bo$7b6obbo7b6o59b5o$8bo6boobo4bo5bo59b3o$9boo7b
o4bo95boo$10bobbo10bo4bo88boob4o16bo$11bobo12boo91b6o15bobo3bo$120b4o
16bobobbobo$141bo4bo4$148bo$147bobo3bo$147bobobbobo$148bo4bo!

Finally in October 2005 the first clean c/4 diagonal rake was constructed, by David Bell. It has period 4508 and occupies roughly a 4500 by 4000 bounding box. I think not much more than that is known about c/4 diagonal puffer and rake technology. So if you have a new period, and with a rake no less, I think it would be new and interesting. But you might want to check with Holzwart or Bell, or if you care to share your pattern here I could do so. —David Eppstein (talk) 03:37, 15 January 2008 (UTC)

What format is that code in? Algebraist 07:33, 15 January 2008 (UTC)

It's in rle (run-length-encoded) format [1] [2] [3] [4]. A "b" stands for a blank space, an "o" stands for a live cell, a "$" stands for the end of a row of cells, and a number prior to any of these three characters is a repetition count. You should be able to copy and past it into most life programs such as xlife, golly, etc. —David Eppstein (talk) 18:31, 15 January 2008 (UTC)

Thanks. *Max* (talk) 19:43, 15 January 2008 (UTC)

^That post (originally signed User:131.111.8.103) was from me signed out. Can you please not co-opt my posts, even if they are unedifying? Algebraist 06:36, 16 January 2008 (UTC)

Sorry, I thought it was from me signed out. I couldn't tell because my IP changes and I could have easily forgotten a one-word post. *Max* (talk) 01:05, 17 January 2008 (UTC).

File:Conway's Life Rake.jpg

Actually, it's period 60. It emitts 1 glider every 20 generations, but it destroys 2/3 of them. It's speed is c/2. *Max* (talk) 01:02, 16 January 2008 (UTC).

That's not a c/4 diagonal rake, it's a c/2 orthogonal rake. According to the "c/2 orthogonal spaceships, puffers, rakes" section of the Life status page I linked to above, a rake with that period is already known. —David Eppstein (talk) 02:32, 16 January 2008 (UTC)

Oops, I got it confused with a different rake. I didn't say it was c/4, but the diagonal part was an error. *Max* (talk) 01:05, 17 January 2008 (UTC).

I inferred the c/4 part from the fact that other speeds are not known for diagonal puffers compatible with a period of 20. Though, now that you say it's really period 60, it seems likely that period 60 c/12 diagonal Cordership rakes exist... —David Eppstein (talk) 01:12, 17 January 2008 (UTC)

Iterated automorphisms

Let Aut(G) be the automorphism group of the finite group G. Consider the directed graph whose vertices correspond to finite groups (up to isomorphism), such that there is an edge from G to H iff $\operatorname {Aut} (G)\cong H$. What is known about the structure of this graph? For example, are there any nontrivial cycles? Is the number of connected components finite or infinite? —Keenan Pepper 22:47, 15 January 2008 (UTC)

No answers, but another question: does this graph have any infinite (nonrepeating) paths? (btw, I assume by nontrivial you mean a cycle which is not a loop loop. Is that correct?) Algebraist 09:02, 16 January 2008 (UTC)

Ah, thanks for that link. Now I know it's called an automorphism tower, and that gets many more relevant hits than the keywords I was using before. And yes, that is what I meant by nontrivial cycle, except that 79.67.220.203 is correct that not every loop is a complete group. —Keenan Pepper 01:22, 17 January 2008 (UTC)

There are a number of loops, e.g. the dihedral group of order 8, that don't come from complete groups. I don't know any larger cycles though. 79.67.220.203 (talk) 11:45, 16 January 2008 (UTC)

<slaps head>Yes, of course. Algebraist 15:06, 17 January 2008 (UTC)

There are infinitely many complete groups (if I recall correctly, the automorphism group of a finite simple group is complete, and this is proven in (Rotman 1994, Ch. 7)). A directed path which encounters a complete group stabilizes there. Thus every complete group is a strongly connected component, and this may answer one of your questions, but in a silly way. Of course, multiple directed paths may stabilize at the same complete group, so there is the theoretical possibility that these directed paths fuse into finitely many weakly connected components. I would be very shocked if this were so, but I have not found a definitive answer for the weakly connected components.

Paths in this graph are called automorphism towers, especially when the starting group has a center of order 1 (so the group is "centerless"). When the center is not of order 1, then it is important to label the edges by the homomorphism taking G onto the subgroup Inn(G) of Aut(G).

The automorphism tower of a centerless finite group stabilizes in finitely many steps (Wielandt 1939), but there are some tall towers starting from small groups. Some silly examples can be constructed for carefully chosen cyclic groups. For instance the cyclic group of order 47 has a cyclic group of automorphisms of order 46, which has a cyclic group of automorphisms of order 22, which has a cyclic group of automorphisms of order 10, which has a cyclic group of automorphisms of order 4, which has a cyclic group of automorphisms of order 2, which has the trivial group as its automorphism group. Just choose primes p_n such that p_n = 2*p_{n-1} + 1 with p_{n-1} also prime. Some larger such primes are p=163, p=487, p=1459, and p=39367.

The groups in a tower can both increase and decrease in size, and they certainly don't have to stabilize at the trivial group. The cyclic group of order 67 has a reasonably tall tower stabilizing at the complete group S3 x S4. I don't think there is a loop starting at a group of order 200 or smaller, though I have not proven this. Certainly there is no loop only involving groups of order 200 or smaller.

When the group is not centerless, then an isomorphism G ≅ Aut(G) is somewhat strange, as it cannot be the natural map G → Inn(G) ≤ Aut(G). For this reason, some authors simply do not count such an isomorphism. Using the language of direct limits, they show that the automorphism tower of the dihedral group of order 8 (which is only strangely isomorphic to its automorphism group) has length ω+1, where ω is the first infinite ordinal (Hamkins 1998).

• Hamkins, Joel David (1998), "Every group has a terminating transfinite automorphism tower", Proceedings of the American Mathematical Society, 126 (11): 3223–3226, ISSN 0002-9939, JSTOR 119135, MR 1487370
• Rotman, Joseph (1994), An introduction to the theory of groups, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94285-8
• Wielandt, Helmut (1939), "Eine Verallgemeinerung der invarianten Untergruppen", Mathematische Zeitschrift, 45 (1): 209–244, ISSN 0025-5874, JFM 65.0061.02, MR 1545814

Sorry not to answer it more specifically. JackSchmidt (talk) 05:46, 19 January 2008 (UTC)

Here is one complete answer: There are infinitely many weakly connected components too.

An undirected path is just a zig-zag of correctly directed paths and reverse directed paths. When one changes from forward to reverse, there is no problem as this just says two groups may have the same automorphism group. However, when one changes from reverse to forward, there is a problem as a group cannot have two automorphism groups. In particular, the weakly connected component of a complete group contains precisely those groups whose automorphism tower stabilizes at the complete group at some finite stage. Therefore, the weakly connected components of non-isomorphic complete groups are distinct. JackSchmidt (talk) 16:27, 19 January 2008 (UTC)

Yes, I was about to say exactly the same thing. Infinity of complete groups implies infinity of connected components, because this is a special kind of directed graph in which there is exactly one directed edge leaving each vertex. So, there are two remaining questions, which I believe are open: "Are there any cycles other than self-loops?" and "Does every path eventually lead to a cycle?". —Keenan Pepper 02:37, 20 January 2008 (UTC)

A Second Opinon

Sorry,If I spelled the word opinon wrong,basicilly I`m not the guy whose been posting those Physics Magazine Questions. But,I`m doing that same thing. And I`m someone,whose not doing it for the prize money just for fun.You see I`m doing The Embriodery One,what I need to know is specific examples which I wrote that show that The Embriodery One,would be sucessful.I got my own theroy,basicilly I just want a second opionon. Also,there`s some Math in this but I think I can figure that part out. —Preceding unsigned comment added by 68.161.128.203 (talk) 23:22, 15 January 2008 (UTC)

Are you attempting to say this was not posted by you, but by someone with the same IP address? For the rest, sorry, but I have got no clue what you are talking about. The Embroidery One? One of the Old Ones? Is it a relative of the Flying Spaghetti Monster?  --Lambiam 23:32, 15 January 2008 (UTC)

Possibly it is related to Nylonathatep, the Laddering Horror. Algebraist 07:01, 16 January 2008 (UTC)

Fresh from getting laughed off of the science desk for trying to conscript us to solve a problem so he could make $50, this guy comes here and tries to pass off the idea that he's a different guy with the same IP, spelling, and question as the last guy. Buddy, if you think we're that stupid, how are we supposed to help you solve the problem? --24.147.69.31 (talk) 00:00, 16 January 2008 (UTC)

Thanks for that, it's one of the best things to come out of these questions :-P Nil Einne (talk) 17:40, 16 January 2008 (UTC)

Oh, yeah, the Embroidery One, I know that, the key was to take the dihydrogen oxide and transpose the intersecting diodes till the bunsen burner reached an altitude of 2 feet, after which you have to to iodize the elixir till it becomes an emulsion, and only *then* to you add phosphates to the beakers that you had previously filled with 1% (not 2%, it will become a gooey mess) milk and 1 tablespoon of an acidic juice such as lemon juice.

If this helped...why? —Preceding unsigned comment added by 63.3.19.129 (talk) 03:42, 17 January 2008 (UTC)

Sorry, forgot to sign - and I should, this had to provide some laughs. :-) Somebody or his brother (talk) 03:45, 17 January 2008 (UTC)