November 2011 - mathfun@mailman.xmission.com

[math-fun] Tiling puzzle
by Dan Asimov 12 Nov '11

12 Nov '11

PUZZLE: Can the real line be partitioned into two congruent sets that are each dense? --Dan Even though kleptomaniacs can't help themselves, they do.

2 1

Re: [math-fun] Exact N-body simulations?
by Warren Smith 12 Nov '11

12 Nov '11

Henry Baker (10 June 2011) wanted to know about rigorous N-body simulations. Answer: You lose: There is no algorithm for simulating the N-body problem with rigorous results, as was proven by me in 1993, see paper #21 http://rangevoting.org/WarrenSmithPages/homepage/works.html Warren D. Smith: "Church's Thesis Meets the N-body Problem" ------- I also have papers about the computational complexity of other theoretical physics, for example I proved in paper #49 that N body problem in "garden variety quantum mechanics" is simulable (quantum mechanics is "easier" than classical mechanics?!) and in paper #58 that hydrodynamics is unsimulable, except that in this result I had to "cheat" by showing either that or 2 other alternatives which also would be devastating. It would be nice to go further to address, e.g. general relativity, standard model, but I put a lot of time into those with nothing coming out.

1 0

[math-fun] Nice solution of "einstein" 1D tile problem
by Warren Smith 12 Nov '11

12 Nov '11

Nice solution of "einstein" 1D tile problem Warren D. Smith Nov 2011 Rich Schroeppel stimulated my brain rather like LSD, and overnight I found a solution! Plan of this post: 1. re-state the problem 2. re-state Schroeppel's impossibility proof plus some souped-up versions of it 3. Construct the sought-for 1D einstein tile (which indeed is "fractal" in nature) and prove it tiles but only in an aperiodic manner. 1. THE PROBLEM Does there exist a 1D einstein tile, i.e. a subset T of the real line with positive measure, such that (a) it tiles the whole line (b) it does so only in an aperiodic manner? "Tiles" for us shall mean there is a countably-infinite set S of translates of T [and we optionally could also permit mirror(T)] which are interior-disjoint and which cover the whole line. A sufficient condition for "aperiodic" is that the set S of translations cannot include any arithmetic progression. 2. IMPOSSIBILITY THEOREMS THM 1 (R.C.Schroeppel): If your single 1D tile can be reduced to a finite set of nonnegative integers, including 0 for definiteness, then any tiling can be converted to a periodic one. PROOF: Suppose the integers are covered by some tiling. For each K, consider the set of integers >K which are covered by some tile that begins at a value <=K. This set is of bounded width, not exceeding the width of the tile. So there are at most 2^width possible shapes for the set. BY pigeonhole principle, somewhere in the first 2^width+1 integers, there will be a K' and K'' with congruent sets (i.e., shifted by K''-K'). The supertile defined by the shift, i.e. tiles covering up to K'' but not entirely <=K', has a set of holes on the left that matches the covered squares on the right. So this supertile makes a periodic covering of the integers. QED. THM 2: Any tile consisting of a finite number of connected components, if it tiles at all, can also be tiled in a periodic manner. PROOF: Assume tile T has width=W, #connected components=C, and measure=A, all positive, C finite. It is easy to see neither W nor A can be infinite: if W were, A would be; if A is then at most 2 tiles could be interior-disjoint, but our defn of "tiling" demands infinite set of tiles. [There do exist tilings of the real line by 2 infinite tiles, of course. They are boring.] Consider the tiles which lie entirely within the right half-line, ordered by leftmost point. After some finite start, each has location given by the first gap in the set composed of the tiles to its left. Hence all locations are specified for us (after some finite start). The tiling is a set of intervals on the real line each labeled with its tile# and tile-orientation {0,1}. Within each segment of length W on the line sufficiently far to the right there can be at most 3*W/A tiles involved and the number of intervals involved is <=3*C*W/A and the number of possible patterns within said segment is thus <=(6*C*W/A)^(3*C*W/A). So now within a segment of length W*[(6*C*W/A)^(3*C*W/A) + 1] chopped into (6*C*W/A)^(3*C*W/A)+1 subsegments of length W we must by pigeonhole principle have at least two subsegments containing identical patterns... hence can tile periodically. QED. THM 3: Any tile of finite width W>0, if it tiles at all, can also be tiled in a periodic manner. PROOF SKETCH: Let tile T have measure=A, width=W, all these positive, W finite. It has C connected components. By THM 2 we may assume wlog that C=infinity. Hence there must be at least one accumulation point within T. The accumulation points cannot be everywhere dense within T otherwise T would be unmeasurable. So there must be some isolated accumulation points. Now if two tiles's minimum containing intervals overlap, then the accumulation points of one, must either lie within an empty subinterval of the other, or must coincide with an accumulation point of the other. Every accumulation point within a tile, must coincide with at least one accumulation point within some other tile of the tiling. Argue similarly to last proof but note the pattern after some point can be described by a binary string like 01100110101010101001... which means "walk rightward; each time you encounter a real not within a previous tile, add a new tile that starts there and is oriented according to the next bit." The number of possible binary patterns within a region of width W is <=2^(3*W/A) since at most 3*W/A tiles can be involved. Now the accumulation-point matchup requirements among these <=3*W/A tiles force each tile to contain at most a FINITE set of accumulation points, say at most F. Call two tiles "AP-adjacent" if one of the firsts's accumulation points coincides with one of the second's. Consider the subset of our tiling got by starting at tile #1 and then finding all tiles AP-adjacent to it, and all tiles AP-adjacent to any of them, and so on forever. This subtiling has finite density lower bounded by a positive constant. Now we can pigeonhole argue like before that it must contain a repeating pattern and hence must be periodic. There can be at most some finite number G of these subtilings (i.e. there are at most G different AP-connected components in the tiling). Hence we can now do a larger pigeonhole argument that shows we get a repeating pattern on the whole shebang which therefore must be periodic-ifiable. QED. 3. CONSTRUCTION of 1D EINSTEIN TILE THM 4: The following subset of the integers, will tile the nonnegative integers by translation only (no mirroring needed) but will only do so aperiodically: T = {nonnegative integers whose digits all are even}. PROOF: A suitable set S of translations is S = {nonnegative integers whose digits all are either 0 or 1}. Then every integer>=0 is covered, and every such integer is covered exactly once. Now to prove no periodic tiling is possible, note that S+T=Znonneg where "+" denotes Minkowski sum of sets, i.e the set of all s+t wwhere s in S and t in T. Because tiling, these s+t all are DISJOINT. Now the key thing is S+T=T+S whenever we have such disjointness. Therefore, we can also "dually" regard the tiling by tiles T via translations S, as a tiling of S by translations T. Note T is infinite but has density=0. (Also our recommended S is infintie and with density=0.) But if any other S worked and that S contained an arithmetic progresion, then this S would have density>0. Hnece it would be impossible to tile an infinite number of disjoint copies of S. Hence by duality it is impossible to tile T by any set S of translations, where S contains an arithmetic progression. QED. FRACTALITY: Note that our set T is "fractal" in that the number of integers x in T with 0<=x<X, behaves for large X like X^(ln5/ln10) = X^0.69897000433601880... And our recommended set S also is fractal in that the number of integers x in S with 0<=x<X, behaves for large X like X^(ln2/ln10) = X^0.301029995663981195... --end.

2 3

[math-fun] Giant planet was ejected from the solar system ?
by Henry Baker 12 Nov '11

12 Nov '11

FYI -- So the solar system didn't relax after 150 million years after all. 600 million years is 4x the previous estimates & I suspect that it took another 100-150 million years to relax after this ejection event. Still no solution for the k-T Boundary problem 65 million years ago, tho... http://swri.org/9what/releases/2011/giant-planet.htm Southwest Research Institute (SwRI) News Giant planet ejected from the solar system For immediate release Boulder, Colo. Â Nov. 10, 2011 Â Just as an expert chess player sacrifices a piece to protect the queen, the solar system may have given up a giant planet and spared the Earth, according to an article recently published in The Astrophysical Journal Letters. "We have all sorts of clues about the early evolution of the solar system," says author Dr. David Nesvorny of the Southwest Research Institute. "They come from the analysis of the trans-Neptunian population of small bodies known as the Kuiper Belt, and from the lunar cratering record." These clues suggest that the orbits of giant planets were affected by a dynamical instability when the solar system was only about 600 million years old. As a result, the giant planets and smaller bodies scattered away from each other. Some small bodies moved into the Kuiper Belt and others traveled inward, producing impacts on the terrestrial planets and the Moon. The giant planets moved as well. Jupiter, for example, scattered most small bodies outward and moved inward. This scenario presents a problem, however. Slow changes in Jupiter's orbit, such as the ones expected from interaction with small bodies, would have conveyed too much momentum to the orbits of the terrestrial planets, stirring up or disrupting the inner solar system and possibly causing the Earth to collide with Mars or Venus. "Colleagues suggested a clever way around this problem," says Nesvorny. "They proposed that Jupiter's orbit quickly changed when Jupiter scattered off of Uranus or Neptune during the dynamical instability in the outer solar system." The "jumping-Jupiter" theory, as it is known, is less harmful to the inner solar system, because the orbital coupling between the terrestrial planets and Jupiter is weak if Jupiter jumps. Nesvorny conducted thousands of computer simulations of the early solar system to test the jumping-Jupiter theory. He found that, as hoped for, Jupiter did in fact jump by scattering from Uranus or Neptune. When it jumped, however, Uranus or Neptune was knocked out of the solar system. "Something was clearly wrong," he says. Motivated by these results, Nesvorny wondered whether the early solar system could have had five giant planets instead of four. By running the simulations with an additional giant planet with mass similar to that of Uranus or Neptune, things suddenly fell in place. One planet was ejected from the solar system by Jupiter, leaving four giant planets behind, and Jupiter jumped, leaving the terrestrial planets undisturbed. "The possibility that the solar system had more than four giant planets initially, and ejected some, appears to be conceivable in view of the recent discovery of a large number of free-floating planets in interstellar space, indicating the planet ejection process could be a common occurrence," says Nesvorny. This research was funded by the National Lunar Science Institute and the National Science Foundation. The paper, "Young Solar Systemâs Fifth Giant Planet?" by Dr. David Nesvorny was published online by The Astrophysical Journal Letters. Editors: An image and animation to accompany this release are available at http://swri.org/press/2011/giant-planet.htm. For more information, contact Maria Martinez, (210) 522-3305, Communications Department, Southwest Research Institute, PO Drawer 28510, San Antonio, TX 78228-0510.

1 0

[math-fun] fractal optimizer?
by Warren Smith 11 Nov '11

11 Nov '11

A few months back on this list (I'm looking back thru the archives) somebody wanted to know if fractals were optimal solutions to something [of real-world interest]. Other than maximizing the amount of bullshit. :) Let me suggest two interesting candidates. 1. One problem I've long been interested in is this: the strongest beam with a given length and given mass of material (or: given the strength & length, minimize the mass). "Strong" means against buckling instability, as first examined by Euler. The optimum convex shape is known. However, much stronger beams are nonconvex and I believe probably fractal. See, you get more stiffness by making the beam wider, make a truss out of lots of triangles for example. This is way stiffer (=more stable against buckling) than any long thin beam of the same mass which is convex. But then, each strut in the truss, presumably also wants to be an optimum beam, I.e. also a truss viewed magnified. And so on recursively. Fractal. --- Another problem I'm interested in is this. You've all heard of the Penrose tiling (set of two tiles which only tile aperiodically). It is a famous open problem ("Einstein" problem) whether a single 2D tile exists which only tiles aperiodically. I would like to pose the same problem in 1D where now I do not demand that the tile be a connected set. I mean: 1D tiling? Now THAT'S simple. But... I do not know the answer, even in 1D. I feel quite embarrassed about it. I mean, you have to be an idiot not to be able to solve 1D tiling. If there is such a tile, it probably has a fractal-esque nature. For a (not quite) example Cantor's "exclude middle third" set is tiled by two copies of itself and is fractal in nature, so you could say it is a solution of this optimization problem: "minimize area subject to requirement two copies tile itself and it contains >=2 points."

2 1

Re: [math-fun] Welcome to the "math-fun" mailing list (Digest mode)
by Warren Smith 11 Nov '11

11 Nov '11

>Asimov: Warren, I don't seem to have received the original message, at least not recently. Can you please state what is is you are responding to? -- http://mailman.xmission.com/cgi-bin/mailman/private/math-fun/2011-September… "Ruminations on negative genus" posted by David Wilson --Asimov also pointed out "It is not correct that 2 - 2g is the number of handles. Rather, g is the number of handles (added to a sphere to get a surface of genus g)." Right, sorry, I mis-spoke re handles (which doesn't matter)

1 0

Re: [math-fun] Ruminations on negative genus
by Dan Asimov 11 Nov '11

11 Nov '11

Warren, I don't seem to have received the original message, at least not recently. Can you please state what is is you are responding to? Thanks, Dan << just use Euler characteristic x=V-E+F for polyhedra with V vertices E edges F faces. For genus g x=2-2g=#handles. For polyhedra of type "sphere" x=2. (example cube: V=8, E=12, F=6). For polyhedra of type "torus" x=0. For polyhedra of type "K spheres" we have x=2K. For polyhedra of type "sets of surfaces" the Euler characteristics obviously sum. So this whole problem becomes totally trivial if you view in terms of Euler. The end. >> Even though kleptomaniacs can't help themselves, they do.

1 0

Re: [math-fun] Ruminations on negative genus
by Warren Smith 11 Nov '11

11 Nov '11

just use Euler characteristic x=V-E+F for polyhedra with V vertices E edges F faces. For genus g x=2-2g=#handles. For polyhedra of type "sphere" x=2. (example cube: V=8, E=12, F=6). For polyhedra of type "torus" x=0. For polyhedra of type "K spheres" we have x=2K. For polyhedra of type "sets of surfaces" the Euler characteristics obviously sum. So this whole problem becomes totally trivial if you view in terms of Euler. The end.

1 0

[math-fun] A problem about approximation
by Warren Smith 11 Nov '11

11 Nov '11

Here's my first problem for you all... Recursively define the class of "ASU functions" of x: 1. f(x)=x is ASU. 2. If f(x) is an ASU function and c is a (complex) constant, then c+f(x), c-f(x), c*f(x), c/f(x) all are ASU functions. 3. If m is a positive integer constant and f(x) is an ASU function then f(x)^m is an ASU function. Prove or disprove: The "Weierstrass approximation theorem" for ASU functions. That is, is it true that an arbitrary continuous function of x on [0,1] can be approximated to within epsilon by an ASU function (for any epsilon>0)? The usual Weierstrassian proof techniques cannot handle this problem; they depend on the function class being closed under linear combinations. ASU class is not. I proved the following partial result. Given any finite subset of [0,1] and any set of real data on that set.... that is, given any finite set of 2-tuples (x1,y1), (x2,y2), ... (xN,yN) with the xj distinct... there exists an ASU function which fits the data with |additive error|<epsilon. However, that does not settle the problem for infinite datasets. Possible way to disprove: just find a function which cannot be approximated... e.g. the fact the real ASU functions are monotone except for rule 3, seems rather restrictive... Possible way to prove: I suspect that there is some sense in which you can keep on using the recursive definition randomly each time (for some very carefully chosen notion of "random"!) for N iterations. Then you can argue that in the limit N-->infinity, the resulting function will be "locally universal." That is, with probability-->1, if you zoom in with your microscope to look at its graph-picture, and set the (N-dependent) horizontal and vertical magnifications right (and high enough), then you will see any desired curve, accurate to epsilon, on your screen if the place you zoom in on was chosen right and if N(epsilon) was large enough. I think it would be quite interesting to prove or disprove this.

1 2

Re: [math-fun] A problem about approximation
by Bill Gosper 11 Nov '11

11 Nov '11

Aren't the Bernstein polynomials ASU? --rwg Warren Smith> Here's my first problem for you all... Recursively define the class of "ASU functions" of x: 1. f(x)=x is ASU. 2. If f(x) is an ASU function and c is a (complex) constant, then c+f(x), c-f(x), c*f(x), c/f(x) all are ASU functions. 3. If m is a positive integer constant and f(x) is an ASU function then f(x)^m is an ASU function. Prove or disprove: The "Weierstrass approximation theorem" for ASU functions. That is, is it true that an arbitrary continuous function of x on [0,1] can be approximated to within epsilon by an ASU function (for any epsilon>0)? The usual Weierstrassian proof techniques cannot handle this problem; they depend on the function class being closed under linear combinations. ASU class is not. I proved the following partial result. Given any finite subset of [0,1] and any set of real data on that set.... that is, given any finite set of 2-tuples (x1,y1), (x2,y2), ... (xN,yN) with the xj distinct... there exists an ASU function which fits the data with |additive error|<epsilon. However, that does not settle the problem for infinite datasets. Possible way to disprove: just find a function which cannot be approximated... e.g. the fact the real ASU functions are monotone except for rule 3, seems rather restrictive... Possible way to prove: I suspect that there is some sense in which you can keep on using the recursive definition randomly each time (for some very carefully chosen notion of "random"!) for N iterations. Then you can argue that in the limit N-->infinity, the resulting function will be "locally universal." That is, with probability-->1, if you zoom in with your microscope to look at its graph-picture, and set the (N-dependent) horizontal and vertical magnifications right (and high enough), then you will see any desired curve, accurate to epsilon, on your screen if the place you zoom in on was chosen right and if N(epsilon) was large enough. I think it would be quite interesting to prove or disprove this.

1 0