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.