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.
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).[reply]
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)[reply]
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).[reply]
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:
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)[reply]
What format is that code in? Algebraist 07:33, 15 January 2008 (UTC)[reply]
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)[reply]
Thanks. *Max* (talk) 19:43, 15 January 2008 (UTC)[reply]
^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)[reply]
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).[reply]
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).[reply]
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)[reply]
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).[reply]
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)[reply]
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 . 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)[reply]
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)[reply]
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)[reply]
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)[reply]
<slaps head>Yes, of course. Algebraist 15:06, 17 January 2008 (UTC)[reply]
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, ISSN0002-9939, JSTOR119135, MR1487370
Wielandt, Helmut (1939), "Eine Verallgemeinerung der invarianten Untergruppen", Mathematische Zeitschrift, 45 (1): 209–244, ISSN0025-5874, JFM65.0061.02, MR1545814
Sorry not to answer it more specifically. JackSchmidt (talk) 05:46, 19 January 2008 (UTC)[reply]
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)[reply]
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)[reply]
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)[reply]
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)[reply]
Possibly it is related to Nylonathatep, the Laddering Horror. Algebraist 07:01, 16 January 2008 (UTC)[reply]
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)[reply]
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)[reply]
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)[reply]
Sorry, forgot to sign - and I should, this had to provide some laughs. :-) Somebody or his brother (talk) 03:45, 17 January 2008 (UTC)[reply]