April 2003 - mathfun@mailman.xmission.com

[math-fun] cellular automata soup experiments
by Richard Schroeppel 12 Apr '03

12 Apr '03

I'm reporting a couple of soup experiments in Conway's Life. Life is a two-dimensional, two-state, cellular automata. The succession rule is based on counting how many of a cell's 8 nearest neighbors are in the ON (or 1) state. If two neighbors are ON, the cell's state is preserved in the next time step. If three neighbors are ON, the cell is turned ON (or left ON) for the next time step. Otherwise, the cell is turned (or left) OFF. My soup experiments are run in either a 1024*1024 field, or an 8192*8192 field. The fields are initialized from a random number generator to be 50% ON. Cells beyond the edge of the field are treated as always 0. It's known from old experiments that a random field, after a long time, seems to settle down to a mostly stable pattern with about about 2.8% of the cells ON. The time to settle is thousands of time steps, perhaps tens of thousands. I have no information on longer term behavior, including whether or not all the active areas eventually stabilize, or if there's a permanent long term low level percolation. My first set of experiments was looking at what happens if there's a small mutation rate. I began with a random 1024*1024 field and ran it 3000 steps. The initial population was 523295, and by generation 3000 it had dropped to 34240 (3%). A small visual sample of the field appeared static, but there were probably a few active areas (based on past experience). I reran the experiment with the same starting position, but I changed the rule by adding mutation. After each time step, 1024 (.1%) of the cells were randomly flipped. After 3000 steps, the population was 74710 (7%), with large active areas. After 10000 steps, the population was 73545 (7%), still with large active areas. The stable areas had the usual Life objects. Then I changed the mutation rule. I started over with the same initial position (50%), and used the same sequence of mutated cells, 1024 (.1%) mutations after each time step. But the mutation rule was "force to ON". If a cell was already on, the mutation was a nop. After 10000 steps, the population was 90045 (9%) with large active areas. There were a few of the usual Life objects. My final mutation experiment repeated the starting setup and the mutation sequence, but the mutation rule was "force to OFF". After 10000 steps, the population was 8875 (.9%), and the only ON patterns were blocks. (A block is a Life pattern of 4 ON cells in a 2x2 square. It's the most common stable pattern in regular Life. If one cell is turned OFF, it regenerates on the next step.) It's possible that over the longer term, the blocks in this pattern would slowly evaporate from double hits. I then ran an experiment in information propagation. The main experiment was with a size 8192*8192 field. I made two random starting positions that matched on the left half but had different (random) right halves. I ran the positions for N generations and compared the results, determining how far the difference propagated into the left half of the field. I measured the position of the leftmost difference (from the midline) for the whole field, and the average position of the leftmost difference (averaged over all rows). The first number represents the maximum leftward penetration of the information from the differing right halves; the second number is the average leftward penetration. (My initial experiments were with 1024*1024 fields, but the 10K generation case reached the left edge of the field. So I bumped the field size to 8192^2.) 10 steps max 10 avg 4 20 20 9 50 46 21 100 78 36 200 125 57 500 200 106 1000 302 154 2000 432 219 5000 501 274 10000 566 288 20000 566 290 After 20K steps, the maximum leftward information flow is 566 columns, and the average is about half that. This might be interpreted as evidence that a random field blocks or dilutes information flow to only 566 columns; or that a random change to a random field usually has a finite effect. Or maybe I just haven't run enough steps to see the ultimate effect. One possible "practical" consequence is that big random Life patterns can be subdivided and run on many parallel machines, with an overlapping margin of perhaps 2000 cells, for many time steps, and only modest synchronization effort. Rich rcs(a)cs.arizona.edu

2 1

[math-fun] Math Awareness pays off: this week's Sunday New York Times crossword
by Thane Plambeck 11 Apr '03

11 Apr '03

Puzzle Title: "PEOPLE WITH UNLISTED NUMBERS" Here's one Across clue: 20 Tori Spelling [11 letter answer needed] But the next Across clue, following 20, was seemingly missing in the clue list. Its answer had 9 letters. What to do? Note to our international readers: Tori Spelling happens to be a particularly bad actress who appears on US TV http://www.tori-spelling.com/ (You would be well-advised to not visit that URL). The answer(s) turned out to be DONUTSHAPES (Tori) CLASSWORK (Spelling) Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

[math-fun] a theta value denesting, anagrams elements <-> math
by R. William Gosper 11 Apr '03

11 Apr '03

Henry asks for "Moriarty's theorems". There are two in that Russian book Emma Lehmer partially translated (if I can only find it), apparently due to someone named Davis ("Dyeveesa", which I mistook for "device"). Henry also privately remarked >I thought that tatami's were 1:2, not 1:3... Usually, but for departure ceremonies they use an elongated version whose full name is tatatami. Apropos Henry's years-earlier question about algebraic valuations of infinite products of 1+e^-(a n pi), - 6 %pi theta (0, %e ) 3/4 1/4 4 3 + 3 - sqrt(2) -------------------- = --------------------- ~ 1.00016141206207, - 3 %pi 9/8 theta (0, %e ) 2 4 i.e., 3^(1/4) + 3^(3/4) ~ 2^(1/2) + 2^(9/8). Attn Ed Pegg: arsenic <--> arcsine, selenium <--> semilune(!) Are these amphoteric or metaphoric?

1 0

Re: [math-fun] The Unabomber's Mathematical Locutions
by Henry Baker 11 Apr '03

11 Apr '03

There's a mathematical metatheorem: All theorems are named after someone not their original discoverer. Your best hope is that someone else will find that your theorem is not original, so that your name will then be attached to it forever. At 03:57 PM 4/10/03 -0700, Steve Gray wrote: > Napoleon was probably not the originator of that theorem. I think the >earliest known mention was in 1825. Napoleon's theorem may rank as the most >generalized theorem in the history of geometry, culminating (so far) in an >article of mine in the March 2003 Monthly. But it can be taken even >farther, which I am now working on. > I do not (yet) have a criminal career, but will consider one if my >article continues to be totally ignored. Please help me avoid a life of >crime! :o)

2 1

Re: [math-fun] tic-tac-toe & qubic
by asimovd＠aol.com 11 Apr '03

11 Apr '03

Rich writes: << I've shown N^3 TicTacToe is drawn for N >= 7; N^4 is drawn for N >= 11; N^5 is drawn for N >= 14; ... N^D is drawn for N >= 3 D - (D mod 2) (and D>=3). >> This is fascinating, and (if it hasn't already been published) sounds well worthy of writing up as an article for the Math. Intelligencer or the American Mathematical Monthly. Rich, do you know for which N the first player is known to have a winning strategy? * * * I'll mention two torus games, the first of which I've already alluded to: 1. n^D toral-tic-tac-toe (T4). This just assumes the usual wraparound when a line gets to the edge of the board. The winning "lines" would actually be certain "finite circles" in the torus, since there'd be no distinguished start or end. E.g., in the 4^3 case, there'd be the same 3x16 = 48 axis-aligned wins as in cubical tic-tac-toe, but a total of 6x16 = 96 wins parallel to a face diagonal (compared to 24 in the cubical case) and a total of 4x16 = 64 wins parallel to a main diagonal (compared to 4). So the total number of winning "lines" is 13x16 = 208 (compared to 76). 2. n^D affine toral tic-tac-toe (AT4). This is easiest to describe mathematically: A win is any "affine line" (which again is a finite "circle"). Think of the board as the abelian group G = (Z_n)^D where Z_n = integers mod n. A win is any coset of any subgroup H isomorphic to Z_n, or in other words a subset L of the form g + H where g is any element of G. For the 4^3 game, each subgroup isomorphic to Z_4 has 64/4 = 16 cosets, so the number of winning "lines" is 16 x (the number of subgroups of (Z_4)^3 that are isomorphic to Z_4). If I'm not mistaken there are 28 distinct subgroups isomorphic to Z_4, and so 16x28 = 448 different wins. * * * Can the first player always win 4^3 AT4 ??? How about 4^4 AT4 ??? --Dan

1 0

[math-fun] mathematical criminals
by Thane Plambeck 10 Apr '03

10 Apr '03

If being a criminal means being put in jail, that casts a pretty wide net. Bertrand Russell jailed for opposing the First World War Andre Weil jailed in Finland as a spy, almost executed Galois jailed for threatening the King, (found 'not guilty' ) Fourier jailed in French Revolution Not too hard to come up with more examples... Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

Re: [math-fun] The Unabomber's Mathematical Locutions
by Henry Baker 10 Apr '03

10 Apr '03

Do we know any theorems of Moriarity? At 05:09 PM 4/10/03 -0700, Ed Pegg Jr wrote: >Professor Moriarity. > >Although this might technically be a fictional criminal who was also a >mathematician. > >--- Henry Baker <hbaker1(a)pipeline.com> wrote: >> Are there any other famous mathematicians who >> were also criminals?

1 0

[math-fun] tic-tac-toe & qubic
by Richard Schroeppel 10 Apr '03

10 Apr '03

I recall seeing both 3^3 and 4^3 TicTacToe c. 1955. The 4^3 game was played with circular tokens - skinny checkers - on a board with 4 transparent plastic levels, separated by spindly legs. It was called Qubic. The 3^3 game was played on a foldable wire frame, using colored wooden beads with holes, as for making a necklace. The 3^3 game had more complicated rules -- maybe you had to make two connected lines (?) -- probably you couldn't start in the center. There were three colors of beads for a three-person game. Of course plain 3^3 TTT is an easy first player win. For 4^3, around 1980, Oren Patashnik showed a first player win. It was based on a table of 2900 key positions, where he specified the winning move. Non-table positions have a forcing sequence to complete the win. He took a job as a PDP10 night shift operator, and used a year of background computer time to do the necessary searches. When his program got stuck, he would figure out a winning move and add the position to the table. His result wasn't widely known; as late as 1985, Qubic was one of the games played in a British computer games tournament, where programs competed against each other. In contrast to most computer games (which tend to be acquired tastes), Qubic is fun to play. It might even be appropriate for bright seven year olds. I've done some work on TicTacToe, exhibiting drawing strategies for various sizes of game (or proving existence). I've shown N^3 TicTacToe is drawn for N >= 7; N^4 is drawn for N >= 11; N^5 is drawn for N >= 14; ... N^D is drawn for N >= 3 D - (D mod 2) (and D>=3). Most of these are based on fancy weighting & counting arguments to show the existence of a simple pairing strategy draw: each possible winning line contains two paired cells, and if X plays in one cell, O takes the other. The 7^3 has too many lines (193) for this to work. Instead, I have an explicit ad hoc blocking strategy. The game group is special when either D=1 or N<=2. In the non-special case, the groups are the same for (2N)^D and (2N+1)^D. Proving the group is hard: Exhibiting and checking the generators is easy enough, but showing no other elements is tricky. Rich rcs(a)cs.arizona.edu

2 1

[math-fun] math & crime, and Neptune
by Richard Schroeppel 10 Apr '03

10 Apr '03

Apparently Cardan (of cubic equations) was a rather unsavory character. In the 1960s, I was told a story about a well-known mathematician who murdered someone. The name began with K, but this was before Kaczynski. -- Apparently a new chapter is about to be added to the Adams-Leverrier story about the discovery of Neptune. The new claim is that Airy took the criticism in order to promote Adams. Based on newly discovered letters. Rich rcs(a)cs.arizona.edu

1 0

Re: [math-fun] The Unabomber's Mathematical Locutions
by Henry Baker 10 Apr '03

10 Apr '03

Are there any other famous mathematicians who were also criminals? I seem to recall that Vieta was a lawyer, but I'm not aware of any greater crimes. Napolean has Napolean's theorem, but isn't normally considered a mathematician. Socrates was a criminal, but was he a mathematician? Logician?

4 4