May 2015 - mathfun@mailman.xmission.com

[math-fun] Overkilbert
by Bill Gosper 08 May '15

08 May '15

The Hilbert curve([0,1]) double-covers a dense, uncountable subset of [0,1]x[0,i]. E.g., In[55]:= Hilbert /@ {2661/3280, 2677/3280} Out[55]= {3/4 + (5 I)/11, 3/4 + (5 I)/11} It triple-covers a dense, countable set, e.g., In[57]:= Hilbert /@ {1/6, 1/2, 5/6} Out[57]= {1/2 + I/2, 1/2 + I/2, 1/2 + I/2} Less obviously, it quadruple covers a sparser, but presumably dense set, e.g., In[58]:= Hilbert /@ {5/48, 7/48, 41/48, 43/48} Out[58]= {1/2 + I/4, 1/2 + I/4, 1/2 + I/4, 1/2 + I/4} --rwg

1 0

[math-fun] replicator in ConwayLife
by Warren D Smith 08 May '15

08 May '15

probably old news to you all, but new to me.... First replicating creature spawned in life simulator 16 June 2010 by Jacob Aron New Scientist Magazine issue 2765. http://www.newscientist.com/article/mg20627653.800-first-replicating-creatu… "Gemini" is described here, it can be regarded as a spaceship with very general velocity vector: http://www.conwaylife.com/wiki/Gemini Number of cells 846278 Bounding box 4217807x4220191 Period 33699586 The new copy is offset by: (5120,1024) This as definitely an example of "intelligent design" :) The designer was Andrew J. Wade. Then the "geminoid replicator" was built, which creates an offset copy of itself, but the original copy is still there (unlike gemini, where the original is destroyed) and this was implemented in 14826990x14826908 box using 290096 live cells, and the replication takes 237228340 ticks. A gzip compressed description fits in 26.6 kbytes. Apparently the designer was Dave Green (?). Using this technology it is comparatively easy to build quadratic-growth patterns, etc etc, you could program it to create a spatial -- or space-time -- pattern which, viewed at a large enough scale of space and/or time, looks like anything that is algorithmically describable. Apparently, the geminoid replicator's core processor fits in only about a 600x600 box with about 16000 live cells; the rest is just "microcode." Even that 16000, however, is far more complexity than could have ever been expected to arise naturally in the observable physical universe. http://conwaylife.com/ links to an enormous amount of ConwayLife research, it is incredible how much they've done. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] How miraculous was the origin of life? Experiment suggested to answer this.
by Warren D Smith 08 May '15

08 May '15

Meeker's cite led to this summary: http://www2.asa3.org/archive/evolution/199705/0014.html SELF-REPLICATION: Even peptides do it By Stuart A. Kauffman Nature 382 (8 Aug 1996). Do not be too excited -- this "lifeform" is a 32-amino polypeptide which catalyes its formation from 15- and 17-long halves, assumed already present in environment. But we could regard it as meeting Allan Wechsler's notion of "semi-life" and conceive that many interacting systems of this nature could suffice to synthesize themselves from an amino-soup. C.Greathouse claimed he felt it unlikely even a single mutation would leave a lifeform viable. Wrong. Actually, proteins do usually still work if 1 amino is altered. It helps to avoid aminos in the small "active site" and to keep the amino in the same "class" meaning {hydrophobic, hydrophilic} but the latter is usually not necessary if it is only one amino changing. Thinking a bit about really stripping down a bacterium, all we really need are the DNA, transcription machinery, ribosome, and a DNA polymerase, if we optimistically assume aminos and nucleotide triphosphates were available in environment. In all that'd be about 100 genes fitting in about 10000 base pairs. If we claim the "true complexity" of N-amino proteins is not 20^N or 64^N but rather more like 2^N in view of the 2-class approximate view, and if we claim the 100 genes could be permuted in 100! ways and it'd still work, then we get this number of bits: log( 2^3333 / 100! ) / log(2) = 2808 bits. (This also would be about the complexity of 100 interacting peptide systems of the ilk at top.) Which is still far above from the complexity the abiotic universe could be expected to provide by luck. Which is what? If the entire Earth surface 10 meters deep is regarded as a laboratory performing 1 experiment per cubic angstrom per millisecond for 10^9 years, then I get this number of experiments: 2^217. (If there were also 10^20 planet earths out there, then increase this to 2^283.) So to get genesis of life on Earth, we need to reduce the bit count 2808 by a factor of at least 13, but probably reducing it by a factor 25 would be good enough.

3 2

Re: [math-fun] Sizing permutation graphs
by Leo Broukhis 08 May '15

08 May '15

On Thu, 7 May 2015 07:55:23 -0400, Andy Latto <andy.latto(a)pobox.com> wrote: > > I think the diameter is N-1. Given two permutations X and Y, we can > find k transpositions T1, T2,...Tk such that > > XT1T2...Tk agrees with Y on k of the objects being permuted. But when > k = N-1, if n of the elements go to the right place, the last one > must, too; where else could it go? My understanding of the definition of graph diameter is that is is one greater than the max distance between nodes, so that the diameter of an empty graph is 0, and the diameter of a single node graph is 1. > (obviously, the distance between 2 >> single-cycle derangements will be N). That's a typo, the distance is N-1. > This seems completely wrong. > > 1->2->3->.....100->1, and 1->3->2->4->5....->100->1 are single cycle > derangements, and they are adjacent in the graph. I meant two derangements relative to one another, not to the "original" position. >> What if we allow combining disjoint same distance transpositions, e.g. >> >> 1234567890 <-> 3412765098 > > That reduces the diameter to ceiling(log_2(n)); we can find a > permutation of this form that sends half of the objects being permuted > to the right place, then multiply by another that fixes these and > sends half of the remainder to the right place, and so forth. The ceiling(log_2(n)) estimate seems intuitively right, as it takes at most that number of bit swaps to reverse a word, but the observation is wrong. When doing a reversal, all pairwise distances are different, therefore the first swap can send no more than 2 objects to the right place. We win only by incremental adjustments. And still, it is not obvious that an arbitrary permutation will be decomposable as easily as the reversal. Leo

2 1

[math-fun] How miraculous was the origin of life? Experiment suggested to answer this.
by Warren D Smith 08 May '15

08 May '15

If the simplest lifeform capable of independent existence had, say, 3000 base pair long DNA --actually I think the least the "minimal genome project" has been able to come up with is more like 100 times that -- then you might say "the chance of that is 4^(-3000) which is about 10^(-1806), which is so small that even if every atom in the observable universe were trying a new 3000-long DNA sequence every femtosecond, life almost certainly would still never have come into existence anywhere ever... therefore, life is a miracle and Earth is likely the only place in the universe that has any." However, that calculation was wrong because more than one of those 4^3000 sequences probably works to produce a viable lifeform. In fact the number that work is probably also enormous. If the number were N then the viability probability is more like P=N/4^3000, and it is that chance P that really needs to be used to assess the miraculousness. OK, that brings me to my point. We can do an experiment to approximately measure P. Start with some near-minimal bacterial genome which say has G base pairs in its genome. Randomly mutate K of its base pairs. There are binomial(G,K)*3^K possible mutated genomes obtainable in this way. We are taking a uniform random sample among them. When you do this, count how many of the resulting bacteria remain viable, versus how many are rendered unviable. The result of such an experiment is a function F(K) estimating the chance that mutating K of the base pairs, still yields a viable lifeform. We will know, to good accuracy, the values of F(1), F(2), F(3), etc for some set of K's. We then want to EXTRAPOLATE this function to determine the value of F(G-1), which is, essentially, equal to P, the life-viability chance we were seeking. To perform this extrapolation we need to obtain an empirical formula that fits the data F(1), F(2), F(3) etc that we have. I doubt this extrapolation will be very difficult. In fact I might a priori suspect that F(K) = K^Q * C^K for suitable fitting constants Q and C, will work decently. Thinking some more, it might be possible to do an even better job than that. We can do a different kind of experiment to attempt to estimate F(K+J)/F(K), by starting with a viable K-mutant, and generating J-mutants of it. We might be able to reach very large K values this way and thus build a long chain of such ratio-estimates.

6 6

Re: [math-fun] Sizing permutation graphs
by Leo Broukhis 07 May '15

07 May '15

On Thu, 7 May 2015 16:32:09 -0400, Warren D Smith <warren.wds(a)gmail.com> wrote: > LB, something like your "bitswap" primitive move, > where, e.g. items x and y are swapped if the binary integers x and y > differ in only a single bit, we specify the single bit we have in mind, and > all such (x,y) pairs are independently decided about whether > that pair is swapped or not... all in a single whack... I don't see how you arrive from the above to the below. > that thing yields diameter of the whole set of N! permutations, of > diam=O(logN). > The reason: this set of primitives can be used to build a "Benes network" which > is a well known "non-blocking network" capable of "routing any permutation" of > "telephone calls" in O(logN) stages. Unlike bit swap, Benes stages are of a scatter-gather variety with O(log(N)) different distances each, therefore using bit swaps to implement a Benes network, one would expect O(log(N)^2) stages. Leo

1 0

Re: [math-fun] Similar permutations problem
by Dave Dyer 07 May '15

07 May '15

Here's a sample puzzle http://www.tantrix.nu/img/match/matchmain.gif The program that generated the puzzles verified that there's only one way to fit the remaining tiles into the frame, but no one ever verified that the lots of the available puzzles don't lead to the same or similar solution. Clearly, if you started with the solution and randomly removed tiles, there are many valid starting points that would lead to that solution. There definitely are may positions where you could pick up a block of 3 or more tiles and put them down (possibly rotated) in different positions, and have a new solution. That's what I want to look for, initially in the available set of 20,000 puzzles. Ultimately, I want to verify or refute the feeling of Deja Vu I have; that these puzzles are all the same after a while.

1 0

[math-fun] Sizing permutation graphs (Leo Broukhis)
by Warren D Smith 07 May '15

07 May '15

LB's question: The graph of permutations of N elements with edges corresponding to transpositions has diameter N (obviously, the distance between 2 single-cycle derangements will be N). What happens to the diameter if we add edges corresponding to 1-step rotations (considering both unidirectional, e.g. rotating only to the right, and bidirectional edges)? What if we allow arbitrary rotations? ... At what point the diameter will be O(sqrt(N)), O(log(N))? Less than O(log(N))? --ANSWER: SInce there are N! permutations, if we allow 1-step rotations (2 choices) the diameter necessarily is >=log2(N!) which is about N*lg(N). Actually diam=infinity since you can only access the cyclic subgroup, but I'm trying to illustrate a very simple bounding technique here. If we allow any-#step-rotations, there are N choices, hence diam>=log(N!)/log(N) which is about N. If we allow 2-element swaps, LB showed diam=N. If we allow swapping only a FIXED element (eg, the first) with an arbitrary one, there are N-1 choices, hence diam>=log(N!)/log(N-1) which is about N. This is in fact the correct order of magnitude since I can build one of LB's transpositions from a constant number of mine.

1 2

Re: [math-fun] Similar permutations problem
by Dave Dyer 07 May '15

07 May '15

> >Wouldn't that be 20000*19999/2 = 199990000 *pairwise* comparisons ? >Not a lot by today's standards. Solution 1 compared with each of 19,999 others Soluiion 2 compared with each of 19,998 others .... = 20,000! comparisons.

2 1

Re: [math-fun] Similar permutations problem
by Leo Broukhis 07 May '15

07 May '15

On Thu, 07 May 2015 10:41:34 -0700, Dave Dyer <ddyer(a)real-me.net> wrote: > Here's a real life problem. I have a lot of strings (~20,000) > which are permutations of 14 letter "words" starting with ABCDEFGHIJKLMN > > I suspect a lot of these words are similar, meaning they have a large > number of letters in the same position. Checking for identical words > is trivial - just sort and compare adjacents. Is there an approach > better than the brute force 20,000! pairwise comparisons to find similar > permutations? Wouldn't that be 20000*19999/2 = 199990000 *pairwise* comparisons ? Not a lot by today's standards. Leo

1 0