April 2019 - mathfun@mailman.xmission.com

Re: [math-fun] Restaurant placemat mazes
by Keith F. Lynch 14 Apr '19

14 Apr '19

Cris Moore <moore(a)santafe.edu> wrote: > Site percolation on the square lattice isn?t self-dual since there > can be ?checkerboard? states where neither path is possible, I could be wrong, but I don't think that's what anyone is talking about. The square lattice, or maybe I should say grid, is like a fly screen, consisting entirely of lots of equally spaced horizontal and vertical lines. Some proportion of the segments of those horizontal lines between two consecutive vertical lines, and the same proportion of the segments of the vertical lines between two consecutive horizontal lines, are randomly removed, to create a random maze. "Checkerboard" implies that at least some of the small squares are filled in. They're all hollow. The dual of the maze consists of the remaining lines. Think of them as wires, which can conduct current from one side of the maze to the opposite side only if there's continuity, i.e. an unbroken wire path. To me it's obvious that either the empty spaces connect two opposite faces or the solid lines connect the other two faces. It's impossible for both to be true or for neither to be true. > and the threshold is 0.592746? > 1/2. Where does that number come from? Allan Wechsler <acwacw(a)gmail.com> wrote: > Keith's confusion, which I share, is raised by the wording in the > Bollobas & Riordan paper which he quotes upthread. It seems to > Keith and me that pH = 1/2 follows instantly from self-duality, but > Bollobas & Riordan say that the proof is deep and non-trivial. I > know Bollobas's name -- these are no lightweights. It follows that > Keith and I are missing some complication to the question. All I can think of is that maybe what I describe above as obvious is one of those things that's very difficult to formally prove. I certainly wouldn't know how to begin to do so. It's one of those things that would seem to not need a proof. I guess that means I'll never be a real mathematician. See https://xkcd.com/2042/

2 1

[math-fun] Three old "threequences" from Gosper
by Allan Wechsler 14 Apr '19

14 Apr '19

OEIS has three sequences, A019989, A019990, and A019991, entered by Neil Sloane in 1996 but credited to Bill Gosper. The wording is quite terse, but reasonably clear. There is little commentary, and only about 60 terms are given. Recently on Sequence Fanatics, Sean Irvine reported that he tried to reproduce the data from the given definitions and failed. I was skeptical, but then I tried the experiment myself and also failed. Obviously Sean and I are misunderstanding the wording in the same way, and I'd like to reconstruct what was meant. Below, I'm going to give my reconstruction, which must be wrong at some point! I hope somebody (hint, hint) can clear up my misunderstanding. The underlying structure is a set of six boolean sequences, named a, b, c, A, B, C. At n=0, they are initialized with a(0) true, and the rest false. For any future n, the values are calculated from one particular set of six old values, the ones for k = floor((n+1)/3). For example, the value at 117 are calculated from those at 39. The value of each of the sequences at n is derived from the values at k by OR-ing together three of the values at k. The rule is quite symmetrical: the new value for each sequence is derived from the old value of the same sequence, OR-ed together with the values of the two sequences that differ from the given one in both case and letter. For example, B(n) = B(k) OR a(k) OR c(k). The three sequences in OEIS are defined in terms of a(2n), b(2n), and c(2n). A number n is in the list A019989 if a(2n) is true, and the other two sequences are built from b and c respectively. The problem that Sean and I encountered is that, because OR is monotonic, all six sequences seem to be quickly driven to true, and stay there. My reconstruction is as follows: n=0: abc/ABC = TFF/FFF n=1: TFF/FTT n=2, 3, 4: TTT/FTT all n>=5: TTT/TTT Sean tried exclusive OR, and some other options, and it failed in different ways that he did not share. What was the intent here?

1 0

Re: [math-fun] Possibly unsolved problem about continuous functions f : [0,1]^3 —> R^2
by Dan Asimov 14 Apr '19

14 Apr '19

That Andy! Always with the counterexamples! I had been reading about maps from R^n to R^q and talking about (n-q)-dimensional area, but tripped up on 3-2 = 1. Ah, the glories of old age. Anyhow by 2-dimensional area I meant 1-dimensional length. So: Given a continuous g : [0, 1]^3 —> R^2, the problem is: Prove there exists p in R^2 with the *length* of the inverse image g^(-1)(p) of p is >= 1. ( Or more generally, for any continuous map g : [0, 1]^n —> R^q show there exists a point p of R^q such that (the (n-q)-dimensional "area" of g^(-1)(p)) >= 1 ) —Dan ----- > > Say > > f : [0,1]^3 —> R^2 > > is a continuous map from the unit cube to the plane. > > Unsolved problem (I think): > > ----- > Prove there is some point p in R^2 whose inverse image f^(-1)(p) has area >= 1. Take f(x,y, z) = (x,y). The inverse image of any point is a line segment, which has area 0. Andy > ----- > > Here "area" means 2-dimensional Hausdorff measure.* > > This should properly be called a conjecture. It is related to an apparently > difficult — but proven — theorem in geometry, the "waist inequality" of Gromov: > > Let S^3 be the unit sphere in 4-space, and let > > g : S^3 —> R^2 > > be any continuous map, where D^3 is the closed unit ball in R^3. > > ----- > Then there exists some point p of R^2 whose inverse image g^(-1)(p) has area > at least the area of the equator of S^3. That is, >= 4π^2, since the equator > is a unit 2-sphere). > ----- > > —Dan > > ————— > * Hausdorff r-measure is an ingenious way to assign a reasonable meaning to > the notion of r-dimensional measure of a compact subset K of Euclidean space > R^N, for any positive real number r. When r is an integer it works like this: > > Let alph(N) > 0 be the constant for which the volume of an N-dimensional > ball D_R of radius R in R^n is equal to > > vol(D_R) = alpha(N) R^N. > > Now in R^N, let C be any covering of K by open balls of radii <= eps, > for some eps > 0. > > Define > > |C|_(r, eps) = alph(N) * (the sum of the r'th power of each radius of a ball in C). > > Finally, define > > |C|_r = inf |C|_(r, eps) > eps > 0 > > It's a bit complicated, but it's exactly the right definition. -----

1 0

[math-fun] Possibly unsolved problem about continuous functions f : [0,1]^3 —> R^2
by Dan Asimov 14 Apr '19

14 Apr '19

Say f : [0,1]^3 —> R^2 is a continuous map from the unit cube to the plane. Unsolved problem (I think): ----- Prove there is some point p in R^2 whose inverse image f^(-1)(p) has area >= 1. ----- Here "area" means 2-dimensional Hausdorff measure.* This should properly be called a conjecture. It is related to an apparently difficult — but proven — theorem in geometry, the "waist inequality" of Gromov: Let S^3 be the unit sphere in 4-space, and let g : S^3 —> R^2 be any continuous map, where D^3 is the closed unit ball in R^3. ----- Then there exists some point p of R^2 whose inverse image g^(-1)(p) has area at least the area of the equator of S^3. That is, >= 4π^2, since the equator is a unit 2-sphere). ----- —Dan ————— * Hausdorff r-measure is an ingenious way to assign a reasonable meaning to the notion of r-dimensional measure of a compact subset K of Euclidean space R^N, for any positive real number r. When r is an integer it works like this: Let alph(N) > 0 be the constant for which the volume of an N-dimensional ball D_R of radius R in R^n is equal to vol(D_R) = alpha(N) R^N. Now in R^N, let C be any covering of K by open balls of radii <= eps, for some eps > 0. Define |C|_(r, eps) = alph(N) * (the sum of the r'th power of each radius of a ball in C). Finally, define |C|_r = inf |C|_(r, eps) eps > 0 It's a bit complicated, but it's exactly the right definition.

2 1

Re: [math-fun] Restaurant placemat mazes
by Keith F. Lynch 13 Apr '19

13 Apr '19

Allan Wechsler <acwacw(a)gmail.com> wrote: > Just in case anybody doesn't know: questions like this have been > studied at least since the 1950s, under the rubric of "percolation > theory". The seminal work appears to be Broadbent & Hammersley > 1957. See the Wikipedia article on percolation theory for the > complete reference. Thanks. Wikipedia led me, indirectly, to https://arxiv.org/pdf/math/0410359.pdf which says: The problem of investigating pH in a variety of contexts was posed by Broadbent and Hammersley [7] in 1957. Hammersley [11, 12, 13] proved general results implying in particular that 0.35 < pH(Z2) < 0.65. The first major progress was due to Harris [14], who proved in 1960 that pH(Z2) >= 1/2. His proof makes use of the "self-duality" of Z^2, and is highly non-trivial. For many years it was believed that pH = 1/2 for bond percolation in Z^2; see, for example, Sykes and Essam [22]. However, it was only in 1980, twenty years after Harris proved that pH >= 1/2, that Kesten [16] proved this conjecture, following significant progress by Russo [20] and Seymour and Welsh [21]. I'm puzzled by this. I would think that knowing that it was self dual and that the odds of a solution were greater than or equal to one half would prove that the dual also has odds of a solution greater than or equal to one half. And since the dual obviously has a solution if and only if the original does not, it must follow that both are exactly equal to one half. What am I missing?

3 2

[math-fun] Draft of my April 17, 2019 essay
by James Propp 12 Apr '19

12 Apr '19

I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at http://mathenchant.org/047-draft1.pdf I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged. One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it. Thanks, Jim

7 12

Re: [math-fun] Interesting paper on calculus
by Dan Asimov 11 Apr '19

11 Apr '19

I find this paper to be extremely poorly written. He never defines his terms. The first sentence of the abstract is ungrammatical. For some reason he discusses trying to multiply (d^2 y / dx^2) by (dx^2 / dt^2) [sic!]. No, this is not an interesting paper. —Dan ----- FYI -- This paper discusses the solution of a differential equation (y in terms of x) as well as its inverse function (x in terms of y). The particular example shows x as a cubic polynomial in y, so the inverse is solvable in radicals. I'm curious to know if this particular way of looking at things would provide more insights into the solvability of quartic, quintic, etc., equations. http://online.watsci.org/abstract_pdf/2019v26/v26n3a-pdf/4.pdf ... ... -----

1 0

[math-fun] Interesting paper on calculus
by Henry Baker 11 Apr '19

11 Apr '19

FYI -- This paper discusses the solution of a differential equation (y in terms of x) as well as its inverse function (x in terms of y). The particular example shows x as a cubic polynomial in y, so the inverse is solvable in radicals. I'm curious to know if this particular way of looking at things would provide more insights into the solvability of quartic, quintic, etc., equations. http://online.watsci.org/abstract_pdf/2019v26/v26n3a-pdf/4.pdf EXTENDING THE ALGEBRAIC MANIPULABILITY OF DIFFERENTIALS Jonathan Bartlett 1 and Asatur Zh. Khurshudyan 2 1 The Blyth Institute jonathan.bartlett(a)blythinstitute.org Broken Arrow, OK, USA 2 Institute of Mechanics, NAS of Armenia Abstract. Treating differentials as independent algebraic units have a long history of use and abuse. It is generally considered problematic to treat the derivative as a fraction of differentials rather than as a holistic unit acting as a limit, though for practical reasons it is often done for the first derivative. However, using a revised notation for the second and higher derivatives will allow for the ability to treat differentials as independent units for a much larger number of cases.

1 0

Re: [math-fun] Restaurant placemat mazes
by Keith F. Lynch 11 Apr '19

11 Apr '19

"Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: > A better generalization to 3D should assume a one-dimensional > explorer, i.e. a two-dimensional path. Hold a piece of string in > your hands, and drag it through a 3D maze from north to south while > keeping one end of the string to the west of the maze and the other > end to the east of the maze. (You may need a helper with tweezers > to keep the string on the right path.) Again, either the maze has > such a solution between two opposite faces, or the maze's dual has > such a solution between two different opposite faces, never both and > never neither. That wasn't quite right. I apologize. Either there is a 2D path through the 3D maze, or there is a 1D path through the dual of the 3D maze (i.e. a support column), never both and never neither. Hence, symmetrically, there is either a 1D path through the 3D maze or there is a 2D path through the dual of the 3D maze (i.e. an airtight 2D wall). By "1D path" I mean one between two opposite faces, and by "2D path" I mean one through the other four faces. I now suspect that as 3D mazes become large without limit, there's always a 1D path between opposite faces unless p=0, and always a 1D path between opposite faces of the dual unless p=1.

1 0

Re: [math-fun] Restaurant placemat mazes
by Keith F. Lynch 11 Apr '19

11 Apr '19

Andy Latto <andy.latto(a)pobox.com> wrote: > While I think this is likely, I think more argument is needed to > actually prove it. The duality argument shows that if there is a > phase transition at probability p, there is also a phase transition > at 1-p. But how does it show there is a phase transition at p = .5? > Maybe there are two phase transitions, one at .37 and one at .63. > Maybe there are no phase transitions at all, and the chance that > most locations are accessible increases gradually with p, with no > sudden jumps. I'm sure it does increase gradually with p -- for small mazes. But as you repeatedly assemble four random mazes of a given size into a maze of twice the height and twice the width, it should become more and more unlikely that any p significantly less than 0.5 allows a solution or that any p significantly more than 0.5 doesn't allow a solution. By "solution," I'm thinking mostly about a west-to-east traversal of the maze. Consider two mazes in parallel, i.e. one north of the other. If p is such that the odds of a solution in each maze is 0.8, then the odds of a non-solution with them in parallel is 0.2^2 = 0.04. Actually, less, since there could be a solution partly through one maze and partly through the other. But call it 0.04. Now put two more mazes in parallel in series with the original two. Another 0.04. Since the two new ones are in series with the original two, we have to square 0.96 to get the odds of a solution. 0.9216. Actually, less, since it's possible that none of the solution exits from the first two line up with any solution entrances on the second two, but probably not much less. Of course by symmetry the odds are the same for a north-to-south traversal. Roughly speaking, if the maze size is infinite, if p exceeds 0.5 there will certainly be a single infinite connected set which most of the small squares are in, and will certainly not be any such set for the maze's dual. And if p is less than 0.5, it will be the other way around. I'm reminded of the Apollo Lunar Module ascent stage. It had to work, since otherwise the astronauts would be stranded on the moon. It used hypergolic fuel, so there were no worries about ignition. What was needed is a very reliable valve. It had to open when desired, and had to remain closed at all other times. (It would have been embarrassing had it spontaneously taken off while the astronauts weren't aboard.) Also, since the fuel was very corrosive, the engine couldn't be tested ahead of time. Every lunar module ascent engine was "tested" for the very first time only when it was taking off from the moon. So what they did was have four identical valves in series-parallel. That way any one valve could be open when it should have been closed, and any one valve could be closed when it should have been open, but the engine would still work perfectly. This amplified the odds both of the thing not taking off when it shouldn't and of the thing taking off when it should. Now imagine that the four valves themselves each consisted of four valves in series-parallel. And that each of those four valves consisted of four valves in series-parallel. *Those* valves could be very unreliable, with perhaps only a 2/3 probability of being open when they're supposed to be open, and only a 2/3 probability of being closed when they're supposed to be closed, and yet the overall system would still be highly reliable. That's how I envision these arbitrarily large random mazes. Large assemblages tend to have abrupt phase changes. A macroscopic amount of water (at reasonable pressures) is always either a gas, a liquid, or a solid, never a jelly. Similarly with all other simple substances. The sun has an sharp edge even though it's just a ball of gas. An avalanche on a large mountain always consists of a large amount of snow. You can hammer a rock hundreds of times and have no visible change. Then suddenly when a sufficient proportion of tiny internal cracks link up, the rock shatters into gravel in response to a hammer blow no larger than any of the previous hundred. Learning is often just as abrupt, when lots of small useless disconnected networks of related concepts, skills, facts, and therbligs in your mind link up and create a path between problem and solution. As for the possibility of there being two phase changes, what would the other one be? But there's no substitute for numerical simulation. I should actually construct connection matrices with the appropriate kinds of randomness, and measure the distribution of connected regions as a function of both p and the maze size. Of course this will require multiplication of large matrices, which is CPU intensive and memory intensive. It helps that I only care about zero and non-zero, so I can store 32 values in each 32-bit integer. Also, the matrix is symmetric, so I need only store half of it. Slightly less than half since the diagonal elements are always all non-zero. > Keith F. Lynch <kfl(a)keithlynch.net> wrote: >> I haven't yet figured out how to generalize my dual insight to >> three-dimensional graphs. I'm pretty sure that unless p is very close to 0 or very close to 1, both the 3D graph and the 3D graph's dual will almost certainly be well connected, letting you get from any face to any other face. That's because I'm thinking of a zero-dimensional explorer, i.e. a one-dimensional path. A better generalization to 3D should assume a one-dimensional explorer, i.e. a two-dimensional path. Hold a piece of string in your hands, and drag it through a 3D maze from north to south while keeping one end of the string to the west of the maze and the other end to the east of the maze. (You may need a helper with tweezers to keep the string on the right path.) Again, either the maze has such a solution between two opposite faces, or the maze's dual has such a solution between two different opposite faces, never both and never neither. One complication is that any such solvable maze would fall apart into two or more disconnected pieces. So would a placemat maze except that the lines are attached to the placemat. Clearly what's needed for a 3D maze is for all its parts to be firmly glued to a 3D block through a 4th dimension. I wonder if anyone has ever researched such paths. Or 3D paths through 4D mazes. (Drag a rubber sheet through a 4D maze.)

1 0