August 2013 - mathfun@mailman.xmission.com

[math-fun] solving and denesting
by Bill Gosper 26 Aug '13

26 Aug '13

Early in the sequence of solvable quintic trinomials comes In[105]:= Squint[5*x^5 + 6*x + 6]; whose only real root is In[107]:= FullSimplify /@ %105[[4]] Out[107]= -(1/5) 2^(3/5) 3^(1/5) - 1/5 2^(1/5) 3^(2/5) - 1/5 2^(4/5) 3^(3/5) + 1/5 2^(2/5) 3^(4/5) Raising this to consecutive powers, we find the third gives a binomial: In[108]:= Table[FullSimplify[%^k], {k, 3}] Out[108]= {Root[6 + 6 #1 + 5 #1^5 &, 1], Root[-36 + 36 #1 + 60 #1^3 + 25 #1^5 &, 1], 1/5 2^(3/5) 3^(1/5) (-3 + 2^(1/5) 3^(2/5))} thus rediscovering one of my favorite denestings: (-2^(1/5) + 3^(3/5))^(1/3) == (2^(2/5) + 3^(1/5) + 2^(3/5) 3^(2/5) - 2^(1/5) 3^(3/5))/5^(2/3) --rwg

3 3

Re: [math-fun] solving and denesting
by Henry Baker 26 Aug '13

26 Aug '13

"Euler's Lost Notebook" ?? Unfortunately, this particular journal only accepts papers in Latin... ;-) At 06:27 AM 8/26/2013, James Propp wrote: >Maybe we need an Electronic Journal of Unoriginal Research with a quick turn-around time. If Wikipedia rejects part of a submitted article as being Original Research, just publish it in EJUR and resubmit the Wikipedia article with the EJUR citation included. :-)

1 0

[math-fun] absolute value (branchless)
by Warren D Smith 26 Aug '13

26 Aug '13

suppose my computer wants |x| but it refuses to perform an "if" statement. What to do?

7 12

Re: [math-fun] Einstein thoughts (ignore previous garbled msg)
by Adam P. Goucher 25 Aug '13

25 Aug '13

Warren, > You wrote: > > --re your helix idea, seems simpler but think still works, to use > straight rods in straight holes, but tilted at angles so they do not > hit each other? Not that it really makes a difference, but screws > with my mind less. (Literally.) Correct, that works. > --I've actually had a lot of these thoughts for many years, but your > lego-ism stimulated me. Very well. > --It is more than CAs. See, with CAs, there is a unique successor > given the neighborhood state is known. With tiles we could > permit non-unique successors (i.e several allowed) or could permit > none (i.e. tiling fails if > that local configuration occurs). Agreed. > The tiles which correspond to CAs are interesting and could be > searched for by an easy add-on to my program I sent you (the > "interesting tile" condition is a uniqueness criterion) but the fact > 24 is not a perfect power seems a bit of an obstacle... 24=3*8 > and 8 is a power, though, so given 3-way identification you could do a > 3-neighborhood > 2-alphabet. > > --I'm confused about reversible CAs. Reversible cellular automata are more amenable to implementation in the Margolus neighbourhood, which is precisely the type of neighbourhood directly implemented by truncated octahedra where only the hexagonal faces are coloured. There's a LBA-complete two-state cellular automaton of this type, by Ed Fredkin and Tommaso Toffoli: https://en.wikipedia.org/wiki/Billiard-ball_computer Sincerely, Adam P. Goucher http://cp4space.wordpress.com

1 0

Re: [math-fun] Einstein thoughts (ignore previous garbled msg)
by Adam P. Goucher 25 Aug '13

25 Aug '13

Warren, Some of these replies are in a different order to how you sent them: > this code finds all possible decorated trunc-octs. In three dimensions, a tile (probably a cube will suffice) can have helical protrusions from each face, like so: http://cp4space.files.wordpress.com/2013/08/helical.png If we have similar helical passageways cut into the cube, then they could pass through several cubes. The upshot of this is that we can turn any (possibly disconnected) decorated cube into a connected one, enabling non-adjacent matching rules. (This was how I made a hexagonal lego prism emulate the TS tile.) So, the only real issue is to find local matching rules capable of forcing a three-dimensional recursive pattern. We know (a la Taylor-Socolar) that this can be done in two dimensions, so surely we can get a non-trivial three-dimensional variant...? Indeed, can the modified Sierpinski triangle pattern of the T-S tile be generalised to a tetrahedral pattern? > You would probably immediately think of Conway "life" as a good > candidate, but I suspect not since it needs access to all 8 neighbors > of a square. Would be better to > find a 2D CA with, e.g, the lattice of square-centers alternating in time > with the lattice of square-corners (in 3D this is the BCC lattice, > whose Voronoi region is > the truncated octahedron, 24 possible rotations) where each state is > a function of its 4 predecessors. Larger alphabet than {0,1} perhaps. Okay, this is worryingly coincidental after I posted this (about five hours before your message): http://cp4space.wordpress.com/2013/08/25/block-cellular-automata/ My motivation for considering BCC automata was to create a replicator in CGoL, which emulates an arbitrary 16-state BCC automaton, which can in turn emulate CGoL itself. The hardware is much simpler for BCC automata than full Moore-neighbourhood cellular automata. Conway's Game of Life can be emulated by a BCC automaton with 16 states (by grouping the cells into 2x2 clusters) as a first estimate. I sent this e-mail to Andy Adamatzky in June 2010: > [beginquote] > > Recent advances in DNA nanotechnology have led to the ability to implement Wang > tiles (a tiling system with computational properties). Similar to Penrose tiles, > Wang tiles can enforce complex, aperiodic patterns. > > One of the more interesting patterns created automatically by DNA tilings is a > Sierpinski gasket, formed by emulating the XOR rule (the simplest non-trivial > cellular automaton, similar to Rule 90). > > This gave me an idea: can a tiling system simulate Conway's Life? > > An important stepping-stone to producing a set of Life-simulating tiles is a > 16-state cellular automaton by Paul Callahan. He originally used it to > accelerate his Life program. > > Each cell has 16 states, and corresponds to a 2x2 block of Life cells. Four of > these blocks in a square (4x4 Life cells) determine the state of the central 2x2 > block in the following generation. So, we effectively have a 16-state cellular > automaton, where each cell depends on four cells in the previous generation. > > An interesting thing to note is that the cells do not stay in one place: > alternate generations have cells offset by ½-units. In other words, the lattice > for generation 1 is the dual tiling of the lattice for generation 0. > > Plotting the cells in 3D space (two spatial, one temporal dimension) results in > the body-centred cubic (BCC) lattice. The Voronoi cells are truncated octahedra, > so these are what we use as the 'Wang tiles'. For convenience, we consider the > vertical dimension to be the temporal one, with each generation above the > previous one. > > It is clear to see that each truncated octahedron shares a hexagonal face with > each of the four cells below it (the four cells which affect the cell in > question). It also shares a hexagonal face with each of the four cells above it > (those which it directly affects). > > The square faces of the truncated octahedra can be indented or raised to enforce > the orientation of the cells. The eight hexagonal faces are more interesting, > and correspond to the generation rules for Life. There is one Wang tile for each > possible neighbourhood (65536 in total), and the lower four hexagons are unique > to that particular tile. The upper four hexagons correspond to the next state of > the cell. > > Each of the lower four hexagons have between zero and fifteen bumps; each of the > upper four hexagons have between zero and fifteen indentations. > > For example, the central 2x2 block of the neighbourhood: > > .o.o > .oo. > ..o. > .... > > becomes: > > o. > oo > > in the next generation. In the 16-state cellular automaton, this is equivalent > to the rule: > > 5|6 > ----> 11 > 0|8 > > (The numbers are the binary interpretations of the 2x2 blocks of Life cells.) > > So, the truncated octahedron corresponding to this particular neighbourhood will > have 5, 6, 8, and 0 bumps on the lower four hexagons, numbering in a clockwise > fashion, and 11 indentations on each of the upper four hexagons. There are > another 65535 truncated octahedra, one for each of the 4x4 Life neighbourhoods. > > By placing a single layer of these truncated octahedra on the bottom of a > container, and placing tiles according to the matching rules, this will simulate > Conway's Game of Life. The structure formed by the truncated octahedra is found > in some crystals, and was conjectured by Lord Kelvin (William Thomson) to be the > optimal foam of soap bubbles. It has the highest symmetry group of any > three-dimensional structure, and is the best lattice covering of spheres in > three dimensions. > > http://en.wikipedia.org/wiki/Bitruncated_cubic_honeycomb > > [endquote] By being only slightly cleverer, CGoL can be emulated as a 9-state BCC automaton. > > Yes. In the same way that the Taylor-Socolar tile is a decorated > > hexagon, I suspect that there is a decorated rhombic dodecahedron > or decorated truncated octahedron capable of tiling space strongly > > aperiodically. > > --great minds think alike again :). Furthermore, even a plain > decorated hypercube > likely works in high enough dimension. I can believe that. > And in 4D, the 24-cell is the obvious candidate for decoration and > I strongly suspect the 24-cell is good enough to do the job (if we > were smart enough to see precisely how). Hmm, yes. Let's see: it has an automorphism group of order 24*48, and its rotational subgroup would be half of this, so 576. This is rather promising. > An even cooler goal than mere "strong aperiodicity" (which is highly > related) is "Turing universality." Berger somehow proved 2D Wang > tiling undecidable. I'm not sure exactly how he did it. But vaguely > the idea is, let X=space and Y=time; then the history of a Turing > machine (head+tape), is the tiling in the XY plane: Tiles if and > only if Turing machine does not halt. But that idea runs into the > obstacles that (1) this would only be a quarterplane (or region of > similar ilk) being tiled not the full plane, (2) it would only prove > extensibility of some initial state (the tiles touching the X-axis) is > undecidable, not "tiling in any way at all." Berger somehow overcame > those obstacles. Yes, I've got a copy of Grünbaum and Shephard's `Tilings and Patterns', which gives details (I believe). > Incidentally the "does it tile periodically" problem > is decidable, noted by Hao Wang, and this result is easy. > > > Of course, a "K-1 dimensional Turing universal cellular automaton" seems > more natural starting point than "a Turing machine." Agreed. > Jarkko Kari in 1990 showed (related to the tiling problem by Wang > tile) that the "is your 2D or 3D CA reversible" problem is undecidable. > > Matthew Cook has the simplest 1D UTM, > http://en.wikipedia.org/wiki/Rule_110_cellular_automaton > I'm pretty sure the rule-110 automaton can be implemented in "2 and a > half" dimensions using 2 (or perhaps 3) kinds of tiles and max packing > density criterion not true tiling. > That is, the question "can a 3X1sidedinfinityX2sidedinfinity slab be > filled with these 2-3 tile types at packing density>0.99, given that > the tiles touching > the 2sidedinfinite face are specified (specification finite since > infinite repeating patterns plus finite stretch disagreeing with it)?" > is Turing undecidable. If grant me 1 extra kind of tile, I can fill > in the holes with it to make the true-tiling question > undecidable. You can probably figure out the details yourself of how > to do that. > > You know about all that sort of stuff. > > So somehow you'd have to computer search the finite space Infinite, by the helical decoration idea. :) > of trunc-oct decorations, to find one which yielded Turing universal > power. How the hell to do that? See below for ideas. > > Another issue with "life" and rule-110 is this. If you have only 1 > tile type, I think the only CAs you can implement are "reversible" CAs > (both life and 110 are not). Information-erasing many-to-1 irreversible > transitions seem impossible. I'm not completely convinced. We already know that CGoL can be emulated with ... hmm ... 9^4 = 6561 Wang truncated octahedra. So, presumably the issue is that you're only allowed one tile? However, is it not conceivable that a single monomer can be composed in different ways to yield multiple meta-tiles? > We can however consider CAs with certain forbidden transitions corresponding > to positions where no tile can be placed. That is a larger class than "CAs." > Something like that is unfortunately probably what is needed. > > Also note, a trunc-oct can actually "see thru" the 2D layer at time > t-1 to also access its immediate predecessor at time t-2, giving you a > bit more power than a plain CA. Indeed. This is rendered obsolete by the helical decoration idea, though. > If we refuse to decorate the 6 square faces and only decorate the 8 hex > faces, then it'd be a plain CA, the t-2 trick would be unused. Note with > this un-use, that every > initial state (2D layer) would be possible since neighboring truncocts > in a single t=const layer do not touch hexes, only touch square faces. > That's very nice, so I'd recommend the un-use strategy. > > I actually suspect that there is some decoration of tiles such > that, given an initial layer at t=0 the question "can the next layer at t=1 > exist?" is undecidable. Most probably. > The few surviving tile types -- the ones that actually implement 2D > CAs -- could then be > checked by Wolfram's type-classification for random initial data to > see which seemed to be candidates for Turing power. This too should > be largely automatable. You'd then have to stare at the results and > exercise the grey cells a lot to figure out what was what. Yes, you can depth-first search for periodic tilings, and for impossible tilings. If we dovetail this process over all candidate tiles, the boring ones (periodic or impossible) will be eliminated soon, and the ones that survive could be subjected to human analysis. > > As long as you don't allow both enantiomorphs of a tile, you can > > replace colour-matching rules with indentations and protrustions. > > --yes. > > So anyhow, above I have outlined ideas for a computer-aided search procedure > which has a decent shot at finding a 3D einstein with universal Turing > power and/or mere forced-aperiodicity (the latter should be easier to > prove). Yes. Again, it's easier to eliminate boring examples than to search specifically for interesting examples. > I think some such search should be tried. Think one could find > interesting results with it, > even if not solve einstein problem. Indeed. This might be conceivably applicable to self-assembling (nano?) technology. There's a thesis by Toth-Fejel about this sort of thing, possibly entitled `Kinematic Self-Replicating Machines'. Sincerely, Adam P. Goucher

1 0

[math-fun] Square-Split-Subtract
by Hans Havermann 25 Aug '13

25 Aug '13

There are *three* (base-ten) 38-digit squares that can be split (somewhere) so that (the difference of the two parts)^2 is the original number. One of them is 3636363636363636365^2: Square: 13223140495867768604958677685950413225 Split: 1322314049586776860'4958677685950413225 Subtract: abs(1322314049586776860-4958677685950413225) = 3636363636363636365 What are the other two solutions?

1 0

Re: [math-fun] Hybrid of Goucher lego and Taylor-Socolar tile
by Adam P. Goucher 25 Aug '13

25 Aug '13

> Warren wrote: > > but I didnt think the Taylor-Soc tile was really a tile. It used color matching > rules, not real tile rules based only on shape. No? There are three different variants: I: A connected two-dimensional tile with colour-matching rules; II: A disconnected tile where matching is forced geometrically; III: A complicated three-dimensional connected tile. Now, with access to the third dimension it is straightforward to implement II as a connected prismatic hexagonal tile (with lots of interlocking corkscrew-like protrusions). This can be embedded in the turnover version of the hexagonal Lego tile as described in the previous e-mail. > I thought of the checkerboard of indent+knobs idea too allowing > turnover too, great minds think alike :). What I'd really like to > solve is the einstein problem in 2D or 3D, though. The strongly aperiodic version (no infinite cylic group of symmetries), I guess you mean...? The weakly aperiodic (no translations) has of course already been solved by the Schmitt tile, SCD tile or Goucher lego (whichever you prefer). > You seem to be very smart and you know about the right stuff so > you might be able to. Thanks. > I think it is going to take conceptual clarifications aimed at > figuring out how to make a computer explore the possibilities > efficiently. Yes. In the same way that the Taylor-Socolar tile is a decorated hexagon, I suspect that there is a decorated rhombic dodecahedron or decorated truncated octahedron capable of tiling space strongly aperiodically. As long as you don't allow both enantiomorphs of a tile, you can replace colour-matching rules with indentations and protrustions. Sincerely, Adam P. Goucher

1 0

[math-fun] Hybrid of Goucher lego and Taylor-Socolar tile
by Adam P. Goucher 25 Aug '13

25 Aug '13

> Warren Smith wrote: > > The hex-lego has no "slide the strips" freedom unlike the square-lego -- its > layers thus are unique. > It might be that some combinations of upper & lower twists eliminate the > latter freedom though. The square `Goucher lego' doesn't have `slide the strips' freedom, either, since the knobbles only line up to form a square lattice if the tiles themselves form a square lattice. Animation: http://cp4space.files.wordpress.com/2013/08/noslide.gif Anyway, I've made a hexagonal monotile based on your suggestion: http://cp4space.files.wordpress.com/2013/08/hex-monotiles.png The indentations in the bottom are rotated by the same angle as the knobbles on the top (but in opposite directions). It's possible to replace both the indentations and knobbles with a _self-complementary_ ring of alternate indentations and knobbles. The advantage is that the tile is now invariant under being flipped over. This means that we can embed a 2D hexagonal tile in the equator of the lego, where both enantiomers of the 2D tile are allowed to appear in a layer (since we can flip the 3D tile over). In particular, choose the Taylor-Socolar tile, forcing an aperiodic tiling in each layer. The result is a 3D tile with the following pair of properties: (a) Imitates the Taylor-Socolar pattern in each layer; (b) Has no translational symmetry (being instead screw-symmetric). This is, in a sense, the most aperiodic 3D tile discovered thus far. Sincerely, Adam P. Goucher

1 0

[math-fun] absolute value (branchless)
by Warren D Smith 24 Aug '13

24 Aug '13

Grossman's solution only works on 2-complement machines with sign-propagating right-shift (for signed integers) but if you are willing to accept those restrictions is better than the solution in Joerg Arndt's ftxbook 1.11 (I haven't figured out what his restrictions are). Yes, I said "your computer" which admittedly might already have a single "absolute value" machine instruction, for example... but basically, I'm satisfied. I guess there really ought to be various versions of all Arndt's libraries, one for 2s complement machines, one for 1s complement machines etc etc, which one being detected by #IF statements that at compile time detect your machine type. But, it gets a bit silly at some point. I mean. we'd be better off getting rid of the C language and replacing it with a better language.

2 1

[math-fun] Two tiling theorems with somewhat sketchy proofs provided
by Warren D Smith 24 Aug '13

24 Aug '13

Some results on tilings and the "Einstein problem" (actually more Hilbert's 18th problem) ====Warren D. Smith===Augist 2013======================================================== THEOREM 1: There exists a polyhedral "tile" in 26 dimensions -- i.e. a compact subset of R^26 with simply connected interior and if desired can be taken as polyhedral and arbitrarily close in shape to a 1x2x1x2x...x1x2 hyper-rectangle -- such that if these tiles are positioned (via rotations & translations) interior disjointly in such a way that they completely cover the 2D plane x3=x4=x5=...=x26=0, then this positioning must be aperiodic. And there exists such a covering. THEOREM 2: Suppose a K-dimensional tile (we can wlog demand it be polyhedral with simply-connected interior and all numbers involved in description being rational) is described to you. [And we can even demand it be within epsilon of being a 1x2x1x2...x1x2 hyperbrick for some arbitarily small rational epsilon>0. That is, each point of its surface is within distance epsilon of a surface point for the hyperbrick, and vice versa.] You also are given a rational number F, 0<F<1. [And we can demand the specific formula like F=(1+epsilon)^(2-K).] Suppose you are asked "is it possible to cover a fraction>=F of D-space with these tiles (rotated & translated, interior-disjoint)?" Then: this question is Turing-undecidable. I'll prove these below, but must admit my proofs are somewhat sketchy. If we agree theorem 2 is established then the questions become A. "what is the least dimension K in which undecidability happens?" I have no idea what is the answer, aside from knowing K>=2. B. What if we demand F=1 (true tiling, 100% of K-space covered). I suspect this also is undecidable for the same kind of reason, but making the proof methods I have now, work to show that, would require a hell of a lot of computing or you're going to have to be smarter... you'd have to get heavily into the details of Turing-like machines. PROOF SKETCH FOR THEOREM 1: The tiles are going to be unit hyperbricks with slightly indented/raised patterns on their faces. They thus obviously nearly-tile 26-space, i.e. cover it at density around (1+epsilon)^)^(-26). Now there are many possible rotations of each tile, namely 26! * 2^25 if it were based on a 1x1x...x1 hypercube, but only 12!^2 * 2^25 since we actually use a 1x2x1x2x...x1x2 hyperbrick, which preserve it to within epsilon. If we restrict to the 13 possible rotations in which (x1,x2) or (x3,x4) or (x5,x6) ... or (x25,x26) are rotated into (x1,x2), then we get a 2D tiling problem, which is in fact "Wang tiles" and there is a set of 13 Wang tiles published by Karel Culik II in 1996 [picture in http://en.wikipedia.org/wiki/Wang_tile, cite "An aperiodic set of 13 Wang tiles", Discrete Mathematics 160 (1996) 245-251] which tile but only aperiodically. Actually each of the 13 will really be a set of many rotations, since we have ignored what is happening with the other 24 coordinates, but that will not matter for our 2D-restricted covering problem. Now, why are we permitted to restrict to only these 13 rotations? Why, not, for example, rotate (x5,x14) to (x1,x2)? Or why not negate (-x1,-x2)? By placing "spines" on the "positive faces" and ""boreholes" on the "negative faces" we can prevent negations. In the 2D tiling problem with "Wang-rectangle" tiles, the rectangle edges each really are 25-dimensional surfaces arising from hyperbrick faces. The original hyperbrick has 26*2=52 faces. By patterning each such surface in a designed way we can prevent all the "wrong rotations" and only 13 rotations can possibly matter since the other rotations cannot intermesh with our 13. Each one viewed 2 dimensionally yields a 2x1 rectangle whose 4 edges correspond to a set of 4 of the original 52 faces, and these 13 4-element subsets of the 52 faces all are disjoint. So then it is plain that a 2D plane is coverable if and only if the 13 "Wang rectangle tiles" can cover said plane. QED. PROOF SKETCH FOR THEOREM 2: Same approach as in theorem 1, using fact that (shown by Robert Berger in 1966 following up on initial investigation by Hao Wang 1961) that Wang tiling in the plane is undecidable for a large-enough finite set of Wang tiles (so for us, a large enough finite dimension K). Robert Berger: "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66 (1966). This shows it is undecidable whether a single K-dimensional near-hyperbrick tile, can cover a 2-dimensional plane within K-space. Now if we have such a covering then we can view it as a 2X1X2X1X...2X1XinfinityXinfinity hyperbrick to within epsilon, hence cover K-space with them with packing density (1+epsilon)^(2-K). Now we can design the patterns on the faces so that if covering 2D plane is not possible, then the best possible packing density is strictly below (1+epsilon)^(2-K). QED. --end.

1 0