May 2012 - mathfun@mailman.xmission.com

[math-fun] Square lattice percolation
by Warren Smith 23 May '12

23 May '12

Your function of p, call it F(p), if I understand you aright is F(p) = sum[all orientations and positions of polyominos X which contain the origin] p^|X| * q^|neighborset(X)| where |S| denotes the cardinality of [number of grid squares in] set S and where q=1-p. (Special case: when X is the emptyset then neighborset(X) also is empty.) It likely is best to think about the double generating function F(p,q) i.e. not assuming q+p=1 until afterwards. It is claimed (wikipedia) that the threshhold for square lattice site percolation is pcrit=0.5927460 so that F(pcrit)=infinity. This would suggest that the asymptotic behavior of the coefficients of the Maclaurin series for F(p) grows exponentially like (1/pcrit)^N more precisely their logs ought to be asymptotic. If this asymptotic could be proven with error bounds, then the problem of proving your conjecture that all coeffs are positive, would be reduced to a finite number of cases, which you could then handle by computer enumeration. There is a book Harry Kesten: Percolation, I have not looked at for 10 years, but might be a good start.

1 0

Re: [math-fun] compressed bitmaps of the primes?
by Henry Baker 23 May '12

23 May '12

Very interesting! Thanks! I would imagine that the "zip"-type programs would do better with larger dictionaries -- especially on larger files -- so perhaps this would help to improve these numbers. Perhaps there is an additional argument to these programs to allow for larger dictionaries? (Many of these compression programs were developed in an earlier era of PC's having main memories in the megabyte range instead of the gigabyte range; so perhaps their idea of a "large" dictionary needs to be revised.)) I wonder if "zip"-type programs would do even as well as your 2-level scheme; i.e., could these programs notice the patterns of 0's when the number is divisible by 2, 3, 5 ? At 11:35 AM 5/22/2012, Tom Rokicki wrote: >Well, I do have a sieve program that outputs bitmaps, but these bitmaps >represent a sequence of 30 integers with a single byte (the eight values >mod 30 that are not divisible by 2, 3, or 5.) > >Running this to a 1GB data file (representing all primes less than >32,212,254,720) and compressing the resulting file, I see the following >sizes: > >1073741824 primes.dat >798639547 primes.dat.bz2 >761814389 primes.dat.gz >761814523 primes.zip > >I'm a bit surprised the compressors don't do better; just using >arithmetic coding and the probability of a zero or one >bit should give about a 0.639 compression ratio, but the best >we see above is 0.709. > >On Tue, May 22, 2012 at 11:00 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> Has anyone analyzed the expected size of bitmaps of the primes? >> >> Specifically, consider the set of primes less than some number N, and then represent those primes as "1" bits in a bit vector of length N. >> >> Then compress this bit vector using common techniques such as zip, gzip, 7zip, etc. >> >> What is the growth rate of such compressed bitmaps as a function of N? Are these schemes any better than a simple run-length encoding? >> >> Has anyone even performed any experiments? >> >> Thanks in advance for any info. >> >> P.S. Yes, I know, you can encode the entire infinite bitmap in a fixed/finite number of bits, where these bits encode a Turing Machine that spits out all of the primes. That's not what I'm asking here. > >-- >-- http://cube20.org/ -- http://golly.sf.net/ --

3 3

[math-fun] compressed bitmaps of the primes?
by Henry Baker 22 May '12

22 May '12

Has anyone analyzed the expected size of bitmaps of the primes? Specifically, consider the set of primes less than some number N, and then represent those primes as "1" bits in a bit vector of length N. Then compress this bit vector using common techniques such as zip, gzip, 7zip, etc. What is the growth rate of such compressed bitmaps as a function of N? Are these schemes any better than a simple run-length encoding? Has anyone even performed any experiments? Thanks in advance for any info. P.S. Yes, I know, you can encode the entire infinite bitmap in a fixed/finite number of bits, where these bits encode a Turing Machine that spits out all of the primes. That's not what I'm asking here.

5 4

Re: [math-fun] Gosper's variant (was: Re: Aaronson's puzzles)
by Bill Gosper 21 May '12

21 May '12

Full marks! Extra credit: Product[(4*Cos[(2/3)^n*x] - Sec[(2/3)^n*x])/3, {n, ∞}] == Sinc[y] What is y? --rwg >> >> For anyone who wants a little puzzle to start the week: if I set z_0 >> = i, >> >> and z_(n+1) = 0.5 (z_n + |z_n|), what is the limit of z_n as n tends >> to >> >> infinity? >> >> >> >> Tougher: Suppose z_(n+1) = z_n + |z_n| - sqrt(z_n |z_n|). Why is >> z_∞ = >> >> 1/3? >> >> What is it for general z_0? Spoiler below. > > [ ... ] > >> >> Spoiler: (2Re(z0)+|z0|)/3. This HAD to be on a Putnam. >> >> >> >> Oops, this only holds for Re(z0)≥0 ! Re(z0)<0 is more interesting. >> >> Julian sez it's good out to |argz| ≤ 2π/3, past which the limit is >> (2 Re(sqrt(z0))-|sqrt(z0|)^2/3 . [...] MR> (I am having trouble identifying some of your characters, but I think I > know what it says ... ) > > Of course, it depends on the branch of sqrt(z) you are using. > Let me take Arg(z) to be in the half-open interval (-pi, pi] , > and w = sqrt(z) to be in the sector -pi/2 < Arg(w) <= pi/2 . > > Write z = r exp(i theta) , where theta = Arg(z) . From the rhombus > with vertices at 0 , z , |z| and z + |z| , it is clear that > the argument of z + |z| is half the argument of z . Moreover, > z + |z| = 2 r cos (theta / 2) exp(i theta / 2) . The branch of sqrt(z) > implies that sqrt(z |z|) also has argument theta / 2 . > Thus, z + |z| - sqrt(z |z|) also has argument theta / 2 ... > well, maybe . We have > z + |z| - sqrt(z |z|) = r (2 cos (theta / 2) - 1) exp(i theta / 2) , > so as long as the factor 2 cos (theta / 2) - 1 is non-negative, > the argument is theta / 2 ; otherwise add or subtract pi . > > This shows that one step of the recurrence multiplies z by > (2 cos (theta / 2) - 1) exp(-i theta / 2) , where theta = Arg(z) , > and if theta is in the interval [-2 pi / 3 , 2 pi / 3] , > the argument gets halved (and thus stays in that interval). > Thus, if the initial z_0 is in the sector [-2 pi / 3 , 2 pi / 3] , > we multiply by the infinite product > prod_{k = 1, infinity} (2 cos (theta / 2^k) - 1) exp(-i theta / 2^k) , > which is a telescoping product. Indeed, write the factor as > (exp(3 i theta / 2^(k+1)) + exp(-3 i theta / 2^(k+1))) / > ((exp(i theta / 2^(k+1)) + exp(-i theta / 2^(k+1))) exp(i theta / > 2^k)) > so that z_n = z_0 prod_{k = 1, n} ( expression above ) > = z_0 (exp(3i theta / 2) - exp(-3i theta / 2)) > (exp(i theta / 2^(n+1)) - exp(-i theta / 2^(n+1))) / > ((exp(i theta / 2) - exp(-i theta / 2)) > (exp(3i theta / 2^(n+1)) - exp(-3i theta / 2^(n+1))) > exp(i theta (1 - 2^(-n)))) > = r exp(i theta / 2^n) sin(3 theta / 2) sin(theta / 2^(n+1)) / > (sin (theta / 2) sin(3 theta / 2^(n+1)) > (hopefully no typos there!) Now the limit is easy to evaluate as > r sin(3 theta / 2) / (3 sin (theta / 2)) = r (2 cos theta + 1) / 3 = > (2 Re(z_0) + |z_0|) / 3 . > > If z_0 is outside the sector [-2 pi / 3 , 2 pi / 3] , then z_1 > is within the sector. For example, if 2 pi / 3 < Arg(z_0) <= pi , > then z_0 + |z_0| - sqrt(z_0 |z_0|) = > r (2 cos (theta / 2) - 1) exp(i theta / 2) , as before. But now > the factor 2 cos (theta / 2) - 1 is negative, so the argument is > (theta / 2) - pi . Thus z_1 is in the sector > -2 pi / 3 < Arg(z_1) <= -pi / 2 . In this case, the limit is > (2 Re(z_1) + |z_1|) / 3 . I leave it to those interested to express > it in terms of z_0 . > > By the way, I haven't seen this before, on the Putnam, or elsewhere, > but that doesn't mean it couldn't have been a Putnam problem. > > Michael Reid

1 0

[math-fun] Gosper's variant (was: Re: Aaronson's puzzles)
by Michael Reid 20 May '12

20 May '12

> >> For anyone who wants a little puzzle to start the week: if I set z_0 = i, > >> and z_(n+1) = 0.5 (z_n + |z_n|), what is the limit of z_n as n tends to > >> infinity? > >> > >> Tougher: Suppose z_(n+1) = z_n + |z_n| - sqrt(z_n |z_n|). Why is z_∞ = > >> 1/3? > >> What is it for general z_0? Spoiler below. [ ... ] > >> Spoiler: (2Re(z0)+|z0|)/3. This HAD to be on a Putnam. > >> > >> Oops, this only holds for Re(z0)≥0 ! Re(z0)<0 is more interesting. > > Julian sez it's good out to |argz| ≤ 2π/3, past which the limit is > (2 Re(sqrt(z0))-|sqrt(z0|)^2/3 . Check: (I am having trouble identifying some of your characters, but I think I know what it says ... ) Of course, it depends on the branch of sqrt(z) you are using. Let me take Arg(z) to be in the half-open interval (-pi, pi] , and w = sqrt(z) to be in the sector -pi/2 < Arg(w) <= pi/2 . Write z = r exp(i theta) , where theta = Arg(z) . From the rhombus with vertices at 0 , z , |z| and z + |z| , it is clear that the argument of z + |z| is half the argument of z . Moreover, z + |z| = 2 r cos (theta / 2) exp(i theta / 2) . The branch of sqrt(z) implies that sqrt(z |z|) also has argument theta / 2 . Thus, z + |z| - sqrt(z |z|) also has argument theta / 2 ... well, maybe . We have z + |z| - sqrt(z |z|) = r (2 cos (theta / 2) - 1) exp(i theta / 2) , so as long as the factor 2 cos (theta / 2) - 1 is non-negative, the argument is theta / 2 ; otherwise add or subtract pi . This shows that one step of the recurrence multiplies z by (2 cos (theta / 2) - 1) exp(-i theta / 2) , where theta = Arg(z) , and if theta is in the interval [-2 pi / 3 , 2 pi / 3] , the argument gets halved (and thus stays in that interval). Thus, if the initial z_0 is in the sector [-2 pi / 3 , 2 pi / 3] , we multiply by the infinite product prod_{k = 1, infinity} (2 cos (theta / 2^k) - 1) exp(-i theta / 2^k) , which is a telescoping product. Indeed, write the factor as (exp(3 i theta / 2^(k+1)) + exp(-3 i theta / 2^(k+1))) / ((exp(i theta / 2^(k+1)) + exp(-i theta / 2^(k+1))) exp(i theta / 2^k)) so that z_n = z_0 prod_{k = 1, n} ( expression above ) = z_0 (exp(3i theta / 2) - exp(-3i theta / 2)) (exp(i theta / 2^(n+1)) - exp(-i theta / 2^(n+1))) / ((exp(i theta / 2) - exp(-i theta / 2)) (exp(3i theta / 2^(n+1)) - exp(-3i theta / 2^(n+1))) exp(i theta (1 - 2^(-n)))) = r exp(i theta / 2^n) sin(3 theta / 2) sin(theta / 2^(n+1)) / (sin (theta / 2) sin(3 theta / 2^(n+1)) (hopefully no typos there!) Now the limit is easy to evaluate as r sin(3 theta / 2) / (3 sin (theta / 2)) = r (2 cos theta + 1) / 3 = (2 Re(z_0) + |z_0|) / 3 . If z_0 is outside the sector [-2 pi / 3 , 2 pi / 3] , then z_1 is within the sector. For example, if 2 pi / 3 < Arg(z_0) <= pi , then z_0 + |z_0| - sqrt(z_0 |z_0|) = r (2 cos (theta / 2) - 1) exp(i theta / 2) , as before. But now the factor 2 cos (theta / 2) - 1 is negative, so the argument is (theta / 2) - pi . Thus z_1 is in the sector -2 pi / 3 < Arg(z_1) <= -pi / 2 . In this case, the limit is (2 Re(z_1) + |z_1|) / 3 . I leave it to those interested to express it in terms of z_0 . By the way, I haven't seen this before, on the Putnam, or elsewhere, but that doesn't mean it couldn't have been a Putnam problem. Michael Reid

1 0

[math-fun] Aaronson's puzzles
by Bill Gosper 20 May '12

20 May '12

JA> For anyone who wants a little puzzle to start the week: if I set z_0 = i, and z_(n+1) = 0.5 (z_n + |z_n|), what is the limit of z_n as n tends to infinity? -- James Tougher: Suppose z_(n+1) = z_n + |z_n| - sqrt(z_n |z_n|). Why is z_∞ = 1/3? What is it for general z_0? Spoiler below. JA> Suppose we have a uniform spherical planet, of density p and radius R, and we drill a straight hole from one point to its antipode (neglecting any changes in the gravitational force that this will entail). Then, we drop a point mass from one of the ends, and it will travel through the hole. It is simple enough to show that the particle will oscillate with SHM, and the half-period of this motion will be sqrt(3pi/4Gp). Has anyone pointed out that this is the ground-level orbital period, so a zero-altitude satellite in polar orbit will synchronize latitudes with the point mass? --rwg Spoiler: (2Re(z)+|z|)/3. This HAD to be on a Putnam.

1 2

[math-fun] Life survives 34 days on pseudo-Mars
by Warren Smith 19 May '12

19 May '12

http://www.dlr.de/dlr/en/desktopdefault.aspx/tabid-10212/332_read-3409/year… "Lichens from inhospitable parts of Earth have demonstrated their ability to survive even under the conditions on Mars – organisms that live at altitudes of up to 3500 metres, collected in Switzerland, and cyanobacteria and lichens from the Antarctic. "We observed these samples in a Martian climate for over a month in our Mars simulation chamber," says de Vera. The researchers recreated the Martian surface with various mineral constituents, using knowledge obtained from missions such as the NASA Mars rovers 'Opportunity' and 'Spirit'. In the chamber itself, they replicated the Martian atmosphere, which consists of 95 percent carbon dioxide, four percent nitrogen and trace gases such as argon and oxygen. A vacuum pump system then ensured six millibars of air pressure, which enabled the planetary researchers to simulate the Red Planet’s tenuous atmosphere. Special radiation sources ranging from the ultraviolet to the infrared replicated solar radiation on the surface of Mars. Finally, the organisms had to cope with temperatures that fluctuated between minus 50 degrees Celsius to plus 23 degrees Celsius." "We know that lichens and bacteria could survive and remain active on Mars for 34 days. But could the organisms continue to live in these conditions beyond this period, for years or even centuries? Unfortunately, this question will remain unanswered, as such lengths of time would exceed the scope of this experiment."

1 0

Re: [math-fun] geometry puzzle
by Michael Reid 19 May '12

19 May '12

> Hmm -- you're quite right that I meant the sphere, and also that the space > of uninteresting dissections is larger than I was thinking. Perhaps the > good question again is to ask for one with not all pieces touching the > center? Nah, ... the right question is to ask for a classification of congruent dissections. I'll do this for the 2d case of a unit disc, but of course it only encompasses *known* congruent dissections. And, to be explicit, I'm only considering pieces that have connected interior. First, there are the obvious, uninteresting dissections: use n equally spaced segments (possibly curved) from the center to the boundary. In this case, I think it's OK to describe the "uninteresting" cases as fundamental regions of a finite subgroup of SO(2) ; we don't even need all of O(2) . Second, start by dissecting into six congruent pieces with arcs of unit circles. These pieces have mirror symmetry, so can be bisected with straight line segments. This is the figure in UPIG, and the first that Michael sent last month. Third, start with the same six-piece dissection as before. Now further dissect each into n congruent pieces using arcs of unit circles from the center. Since n of these make a shape with reflective symmetry, patches of n can be reflected (they need not have started in the same piece of the six-piece dissection). The n = 2 case, with all six pairs of pieces flipped is the second figure that Michael sent earlier; perhaps he had intended this more general situation. If this list is not complete, I'd be very interested in seeing more! On the other hand, if the list is complete, then it solves questions such as "can the center be in the interior of one of the pieces?" and "can the diameter of the pieces be less than 1 ?". Michael Reid

3 2

Re: [math-fun] geometry puzzle
by Michael Reid 19 May '12

19 May '12

> What's the story for the sphere instead of the circle? That is, what ways > are there, if any, to dissect a sphere into a finite number of congruent > pieces, other than the pieces just being fundamental domains of some finite > subgroup of O(3)? I suppose it is possible that you intended "unit ball", i.e. solid sphere, rather than sphere. However, it doesn't really matter for now, as all congruent dissections I know of the ball are formed from congruent dissections of the sphere, and then "conifying". I will work with the (hollow) sphere below, but dissections of the solid sphere follow. Independently of that, I think you probably want to phrase it differently. As asked, the dissection into twenty spherical triangles corresponding to a "spherical icosahedron" would be such a dissection. That is, there's no group of order 20 for which the spherical triangles are fundamental domains. Instead, let me suggest an alternative: Dissections whose symmetry groups act transitively on the pieces are "uninteresting" for this discussion. If I have missed your intent, or overlooked some other issue, feel free modify it further. Even with this modification, there are still plenty of other dissections. For example, first dissect into twelve spherical pentagons, corresponding to a "spherical dodecahedron". Each pentagon has bilateral symmetry, so can be bisected, and each has five ways to do it. There are then many ways to bisect all twelve pentagons, and in most, the symmetry group of the dissection does not act transitively on the pieces. Likewise, there are many such dissections starting from spherical tetrahedra, hexahedra, octahedra, and further subdividing. There are also dissections formed by joining pieces. Indeed, the spherical icosahedron dissection is formed by joining sets of three fundamental regions for the action of the icosahedral group. Here's a different type of example, perhaps closer in spirit to what was requested. First split the sphere into two hemispheres, and then dissect each into n congruent spherical triangles using great circles emanating from the poles. If n = 4m , then m of these spherical triangles form an equiangular spherical triangle, which has three-fold rotational symmetry, so that group can be rotated in place to give different dissections. If n = 2k is even, then k of them form a quarter of a sphere, which can also be rotated in place. (Hmmm, this gives me some ideas for rotational puzzles!) Michael Reid

2 1

Re: [math-fun] geometry puzzle
by Michael Reid 18 May '12

18 May '12

> > What a great problem! I was still working through the first few minutes > > of "but... how... isn't..." when Jessica said "Okay, how about this?..." > > and solved it. > > > > But is there more than one solution? I know about the answer depicted in > > http://i.imgur.com/iOfRI.png, but is that unique? > > > > Ah: it's not unique, in that there are solutions like > http://i.imgur.com/bxtbB.png as well. > > Are there any solutions that aren't a refinement of the basic dissection > you get by gluing together pairs of pieces from either of the images above, > though? That seems like it might be provable. There are also dissections into 6n pieces, of which 6 border on the center, and the others do not. By the way, this has been around for a while. I first(?) saw it in Croft, Falconer and Guy's "Unsolved Problems in Geometry". It's on page 89 of my 1991 edition, well, the first solution Michael gave. The generalization (to his second solution) I mention above is more or less "obvious". Your mileage may vary. Michael Reid > > --Michael > > > > > > On Wed, Apr 18, 2012 at 10:50 PM, Bill Gosper <billgosper(a)gmail.com>wrote: > > > >> Colin Wright (e.g., > >> *Colin Wright*: The Mathematics of *Juggling* on > >> Vimeo<http://vimeo.com/27998521> > >> ) > >> > >> posed this at G4GX (and G9?): Dissect a disk into congruent parts > >> > >> at least one of which avoids the center by a positive distance. Neil > >> > >> just beat me to a solution. Grr. > >> > >> --rwg

2 1