May 2014 - mathfun@mailman.xmission.com

[math-fun] 3D Mandelbrot set with "3-Haussdorf-dimensional" boundary?
by Warren D Smith 31 May '14

31 May '14

Just rotate the 2D Mandelbrot set to get a body of revolution with a 3D boundary given that the 2D set has 2D boundary.

5 6

Re: [math-fun] Fractal nomenclature question
by Bill Gosper 31 May '14

31 May '14

On 2014-05-30 18:23, Dan Asimov wrote: > Is there a standard name for the fractal G that's the *boundary* of > Bill Gosper's Flowsnake? > > I've been calling it "the map-of-France". Not sure where that > originated, Straight from Mandelbrot's (previous?) book. > but it's kind of apt, since the actual map of France is > hexagonalish and has a fractalish boundary. > > Omitting technical details: > > One way to define it is to start with the 2D regular hexagon H_0 in > the complex plane C. > > > Inductively, define H_(n+1) as > > a) First taking the union of 6 translated copies of the previous stage > H_n, along with H_n itself, so that the center of one of them lies at > 2+tau, where tau := exp(2pi*i/6) so they all fit snugly together. To > complete this step, and then > > b) shrink this union of 7 copies of H_n by the effect of the function > z |-> z/(2+tau). At this and each successive stage, we have the option of complex-conjugating the figure before recursing, providing a continuum of variations. . > The result is H_(n+1). > > Then we define > > H_oo := lim H_n > n->oo > > It's not too hard to show this actually converges in the Hausdorff > metric on compact subsets of the plane. > > Finally, define the fractal G := bd(H_oo), the boundary of H_oo. > > It has the lovely property that a rosette of 7 translated copies of it > fitting snugly together forms a magnified and rotate copy of H_oo, as > the regular hexagon doesn't quite do. > > It's easy to see the Hausdorff measure d of G is the solution to > sqrt(7)^d = 3, so > > d = log_7(9) = 1.1291500681.... Reminder: http://gosper.org/wikifrac.gif > QUESTION: Does G have an official name? > > --Dan I'm satisfied (≠ thrilled) with Franceflake. --rwg

3 2

[math-fun] Triangulations of planar point sets
by Michael Kleber 31 May '14

31 May '14

Okay, funsters, I'm sure this is really obvious, but I'm not figuring it out. Take a set of points P in the plane (let's say no three collinear, just to keep it simple). A "triangulation of P" is just what you expect: a way of writing the convex hull of P as a union of triangles with disjoint interiors, such that the points of P are exactly the vertices of the triangles in the the triangulation. Theorem, evidently: Every triangulation of P has the same number of triangles. In particular it has 2n-2-k triangles, where n = |P| and k = the number of points of P that are on the boundary of the convex hull. (Of course this means the triangulations all have the same number of edges too -- 3n-3-k of them -- thanks to Euler.) Why is this true? I've waved my hands in the direction of some argument involving the space being connected by moves which swap diagonals of a quadrilateral, with some justification based on thinking of a triangulation as a bird's-eye view of a convex surface that's a tent with poles sitting on the points of P. But this is sounding pretty baroque and it seems like there must be something clear and simple, and I'm just not seeing it. --Michael -- Forewarned is worth an octopus in the bush.

3 4

[math-fun] 3D Mandelbrot set with "3-Haussdorf-dimensional" boundary?
by Warren D Smith 31 May '14

31 May '14

>Warren's argument (which might or might not be valid -- it sounds good to me but I don't work in that area) reminds me of something I was told (but never understood) 30 years ago: that the fractal dimension of the Cartesian product of two sets need not be equal to the sum of the fractal dimensions of the two sets. >Can anyone explain this to me? >Jim --ok, first of all, (A) I am not taking the cartesian product of arbitrary sets -- one of my sets is a line segment orthogonal to the other (2D) set. For that kind of Cartesian product I claim the Haussdorf dimension DOES sum. (B) Second, Jim Propp says that more generally, it need not sum. And why is that? Well, what IS "Haussdorf dimension"? It is this. Let your set S be "grown" to set S(r) which is all points within distance r away from S. Consider the measure of S(r) as a function of r>0. If S(r) is proportional to r^P in the limit r-->0+ (or merely bounded between c1*r^P and c2*r^P for some constants 0<c1<c2) then we'll say S has Haussdorf codimension=P i.e. H = HaussdorfDim(S) = D-P, where the universe we work within is D dimensional. By the way, note that Haussdorf dimension need not exist. So if S is a point (of finite collection of points) then P=D so H=0, that worked. If S is a line segment (or finite collection of curve segments) H=1, worked again. Etc. It works in the usual cases, but can be applied to goofy fractals as well. Good. Now it should be obvious to you (or you should be able to prove easily) that (A) was true. Actually whenever at least one of the two sets is a "well behaved" set (hence with integer dimension) then I claim the sum rule holds. Now: can we construct two fractals whose Cartesian product does NOT have summed Haussdorf dimension? This paper discusses... Kaoru HATANO: Notes on Hausdorff Dimensions of Cartesian Product Sets, HIROSHIMA MATH. J. 1 (1971) 17-25 http://projecteuclid.org/download/pdf_1/euclid.hmj/1206138139 I don't understand this paper, but it cites others, and it at start claims that (i) HaussdorfDim(A)+HaussdorfDim(B) <= HaussdorfDim(AxB) and also that (ii) max{ HaussdorfCoDim(A), HaussdorfCoDim(B) } <= HaussdorfCoDim(AxB). I think the basic intuition for why (i) is not an equality in general, is that the product set exhibits DIFFERENT power law scaling laws in different directions. Further the power can be different in different places -- Haussdorf sort of only takes something like an average or max whenever you've got a fractal like that, yielding only one number (assuming it succeeds in producing a number at all). If you always had the same power no matter which direction, then things would be easy, but no. Indeed, it is not obvious to me that the Haussdorf dimension of a Cartesian product set even necessarily exists at all, even when it does for both the two original sets. Hatano seems to take it for granted it does exist... which hopefully is because somebody had proved that earlier... but he does not cite a proof of that, nor even explicitly state that he is assuming this (but he is).

1 0

[math-fun] Diversion relating to curves ad dimensionality
by Dave Makin 30 May '14

30 May '14

Hi all, From Wolfram Mathworld: "Shishikura (1994) proved that the boundary of the Mandelbrot set is a fractal with Hausdorff dimension 2" One would therefore assert that a correct 3D counterpart of the complex Mandelbrot would have a surface with Hausdorff dimension 3. So far the best candidate for this is the "Mandelbulb" though it's not "perfect" in particular since it only looks like what one would hope/expect when the exponent p in z^p+c is around 7 or more, usually quoted as 8. The details of the Mandelbulb can be found here: http://en.wikipedia.org/wiki/Mandelbulb My suggested diversion/challenge is to find the actual Hausdorff dimension for either the z^7+c or z^8+c Mandelbulb surface.....(not the box-counting version). bye Dave The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.

1 0

[math-fun] curves in regions
by Warren D Smith 30 May '14

30 May '14

Lunnon: Given a plane curve C defined by f = 0 with f(x, y) polynomial, and a region R of the plane (possibly extending to infinity), I assert that C avoids R provided C avoids the boundary of R ; and C has no critical points within R . There must be a well-known theorem to this effect (unless, of course, it's actually false... WDS: a counterexample: C=unit circle, R = thickened version of unit circle (annulus).

5 7

[math-fun] Reliable transfer of quantum information achieved
by Henry Baker 30 May '14

30 May '14

FYI -- http://www.nytimes.com/2014/05/30/science/scientists-report-finding-reliabl… Scientists Report Finding Reliable Way to Teleport Data By JOHN MARKOFFMAY 29, 2014 Scientists in the Netherlands have moved a step closer to overriding one of Albert EinsteinÂs most famous objections to the implications of quantum mechanics, which he described as Âspooky action at a distance.Â In a paper published on Thursday in the journal Science, physicists at the Kavli Institute of Nanoscience at the Delft University of Technology reported that they were able to reliably teleport information between two quantum bits separated by three meters, or about 10 feet. [https://www.sciencemag.org/content/early/2014/05/28/science.1253512 "Realizing robust quantum information transfer between long-lived qubit registers is a key challenge for quantum information science and technology. Here, we demonstrate unconditional teleportation of arbitrary quantum states between diamond spin qubits separated by 3 m. We prepare the teleporter through photon-mediated heralded entanglement between two distant electron spins and subsequently encode the source qubit in a single nuclear spin. By realizing a fully deterministic Bell-state measurement combined with real-time feed-forward quantum teleportation is achieved upon each attempt with an average state fidelity exceeding the classical limit. These results establish diamond spin qubits as a prime candidate for the realization of quantum networks for quantum communication and network-based quantum computing."] Quantum teleportation is not the ÂStar TrekÂ-style movement of people or things; rather, it involves transferring so-called quantum information Â in this case what is known as the spin state of an electron Â from one place to another without moving the physical matter to which the information is attached. Classical bits, the basic units of information in computing, can have only one of two values Â either 0 or 1. But quantum bits, or qubits, can simultaneously describe many values. They hold out both the possibility of a new generation of faster computing systems and the ability to create completely secure communication networks. Moreover, the scientists are now closer to definitively proving Einstein wrong in his early disbelief in the notion of entanglement, in which particles separated by light-years can still appear to remain connected, with the state of one particle instantaneously affecting the state of another. They report that they have achieved perfectly accurate teleportation of quantum information over short distances. They are now seeking to repeat their experiment over the distance of more than a kilometer. If they are able to repeatedly show that entanglement works at this distance, it will be a definitive demonstration of the entanglement phenomenon and quantum mechanical theory. Succeeding at greater distances will offer an affirmative solution to a thought experiment known as BellÂs theorem, proposed in 1964 by the Irish physicist John Stewart Bell as a method for determining whether particles connected via quantum entanglement communicate information faster than the speed of light. ÂThere is a big race going on between five or six groups to prove Einstein wrong,Â said Ronald Hanson, a physicist who leads the group at Delft. ÂThere is one very big fish.Â In the past, scientists have made halting gains in teleporting quantum information, a feat that is achieved by forcing physically separated quantum bits into an entangled state. But reliability of quantum teleportation has been elusive. For example, in 2009, University of Maryland physicists demonstrated the transfer of quantum information, but only one of every 100 million attempts succeeded, meaning that transferring a single bit of quantum information required roughly 10 minutes. In contrast, the scientists at Delft have achieved the ability Âdeterministically,Â meaning they can now teleport the quantum state of two entangled electrons accurately 100 percent of the time. They did so by producing qubits using electrons trapped in diamonds at extremely low temperatures. According to Dr. Hanson, the diamonds effectively create ÂminiprisonsÂ in which the electrons were held. The researchers were able to establish a spin, or value, for electrons, and then read the value reliably. In addition to the possibility of an impregnable quantum Internet, the research holds out the possibility of networks of quantum computers. To date, practical quantum computers, which could solve certain classes of problems far more quickly than even the most powerful computers now in use, remain a distant goal. A functional quantum computer would need to entangle a large number of qubits and maintain that entangled state for relatively long periods, something that has so far not been achieved. A distributed quantum network might also offer new forms of privacy, Dr. Hanson suggested. Such a network would make it possible for a remote user to perform a quantum calculation on a server, while at the same time making it impossible for the operator of the server to determine the nature of the calculation. A version of this article appears in print on May 30, 2014, on page B3 of the New York edition with the headline: A Step Toward Winning a Dispute With Einstein.

1 0

[math-fun] counter mod N
by Warren D Smith 30 May '14

30 May '14

Suppose your computer wants to count 5,4,3,2,1,0,N-1,N-2,... forever (counting down modulo N). What to do? int J,K; forever( K=K-1; J=K mod N; } forever{ K=K-1; if(K<0){ K=K+N; } } both work, but one involves slow division, other slow if statement. Actually the first one fails when K overflows. forever{ K=K-1; K = K + ((K>>31)&N) ; } (here assuming 32-bit wordsize), has neither flaw. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Generalized gray code (answer)
by Warren D Smith 29 May '14

29 May '14

On 5/29/14, Warren D Smith <warren.wds(a)gmail.com> wrote: >> The "Gray code" is a fast way to produce the integers 0,1,2,..2^p-1 >> in an order such that each differs from predecessor in exactly 1 bit. >> >> Q1 (easy). Find an anti-Gray code where each differs from >> predecessor in exactly p-1 bits. >> >> Q2 (not so easy). Find a "mid-gray" code where >> each differs from predecessor in exactly p/2 bits (p>1 even). >> Note this is impossible if p is a multiple of 4. --actually, here is a solution. Maybe not a very nice solution, but it seems to work. A1. Just use gray code except bitwise-complement every other number. A2(i). If p is multiple of 4, then each word differs from previous in an even number of positions, causing parity to be preserved, meaning you lose because one parity is never accessed. A2(ii). Let p=2*q with q odd. Use A1 with a circular (Hamiltonian tour) Gray code to fidoodle the least-significant q+1 bits. When you get done [2^(q+1) steps], then do a single gray code step on the remaining (i.e. upper) q-1 bits while at the same time altering the lower q+1 bits in q-1 places (it does not matter what alteration). Then do it again. Keeping going in this way, we ultimately generate every p-bit word exactly once, with successors differing in exactly p/2 positions. Note also this answer is readily generalizable to allow generating all p-bit words in a manner such that each differs from preceding in exactly k bits. Works for any p>k>0 with k odd you want. And it is same algorithmic efficiency as the Gray code is, up to constant additive and multiplicative factors.

1 0

[math-fun] opposite of Gray code
by Warren D Smith 29 May '14

29 May '14

> The "Gray code" is a fast way to produce the integers 0,1,2,..2^p-1 > in an order such that each differs from predecessor in exactly 1 bit. > > Q1 (easy). Find an anti-Gray code where each differs from > predecessor in exactly p-1 bits. > > Q2 (not so easy). Find a "mid-gray" code where > each differs from predecessor in exactly p/2 bits (p>1 even). > Note this is impossible if p is a multiple of 4. > Not so easy to do exactly---but you get a decent approximation by > simply running a p-bit block cipher in counter mode. --you can also get an "approximate solution" much more simply by just repeatedly x = x + C (mod 2^p) where C is an appropriately chosen magic odd constant -- C in binary is ...100010001000100010001 This (and the cipher ploy) both are pretty piss-poor approximations, however. I think my method will have difference-bit-counts in the range p/4 to 3p/4 (?), and the Cipher ploy will usually do worse with some difference-bit-counts as small as O(1) and as large as p-O(1). The good news is, 100%-o(1) fraction of the time, the difference-bit-count will be within p/2 +- O(sqrt(p)*log(p)).

1 0