Tiles

Mathematical Weirdness
You Can Hold In Your Hand




Paul Harrison @paulfharrison

Wang Invents Wang Tiles
And Makes A Wrong Conjecture

Wang (1961, section 4.1, A Generalized Game Of Dominos)

Given a set of squares with colored edges, can we tile the plane with copies of these squares so all the edge colors match?
(Rotations and reflections are not allowed.)


Wang's conjecture:
If we can tile the plane, we can do so with a repeating pattern.


Wang's student Berger (1966) showed this is wrong.
There are aperiodic tile-sets.

Aperiodic Wang Tile-sets

Berger's initial construction used 20,426 tiles.

The number of tiles needed has been whittled down over time.

Jeandel and Rao (2015) proved the minimum to be 11 tiles:

(Images from paper.)Berger's main application of this was to be able to construct, for any specified Turing machine, a tile-set that contains somewhere within it the Turing machine tape at any number of steps of evaluation. If the Turing machine halts, the tiles will not tile the plane. Since the halting problem is undecidable, knowing in all cases whether a tile-set will tile the plane is also undecidable.

Penrose Tiles

Penrose (1974, patented 1975) found a set of 6 tiles that is aperiodic, and later reduced this to 2 tiles. Roughly, Penrose tiles are obtained by trying to tile the regular pentagon, which does not work and needs further shapes to fill in gaps.

There are several versions of Penrose tiles with only 2 tiles. This variant has thin and fat rhombuses:

Penrose Tiles

Like many aperiodic tile-sets, the tile layout has a hierarchical construction. Starting with a layout covering a small area, enlarge it by the golden ratio (1+√5)/2=1.618... and replace each rhombus as shown. Repeat.


(Diagram from the Tilings Encyclopedia. Orange lines correspond to the smaller bumps and dents on my version of the tiles.)

Further rabbit holes: Other mathematical analyses of Penrose tiles include projections of cubes from higher dimensions, and decorations with "Ammann bars". The spacing of these bars is also aperiodic, following a "Beatty sequence" of the golden ratio.

The Impact Of Penrose Tiles

  • Penrose patented his tiles, and they were developed into a puzzle with chicken shaped pieces.

  • Used as an architectural motif, such as RMIT's Storey Hall.

  • Speculative link to Islamic architecture: Girih tiles.

  • Quasi-crystals with forbidden symmetries discovered.

    • Quasi-crystals

    Forbidden symmetries were found in real crystals, such as here a 10-fold symmetry.

    Initially created in labs. Natural examples have been found in meteorites.


    (Figures from Bindi et al (2015), with a BY CC 4.0 license)

    Aperiodicity With 1 Tile

    Socolar and Taylor (2011)
    Joan Taylor's website

  • Tile is not a connected shape.
  • Forms nesting triangles.


    • (Figures from paper.)

    Let's now allow forcing rules beyond edge matching.

    This will make it much easier to force aperiodic patterns,
    but it is interesting what is possible.

    My Favourite Tiles That I Found One Day

    Harrison (2005)

    Make a finite pattern, with each notch filled by a bump, and with exactly three corner tiles.

    My Favourite Tiles Explained

    Underlying hexagonal grid:

    Can be viewed as an XOR cellular automaton:

    Wolfram Looked At
    All The Elementary Cellular Automata

    Wolfram, 2002
    "... simple programs produce great complexity ..."


    Elementary Cellular Automata are a class of simple programs. There are only 256, so Wolfram examined them all.

  • Rule 90 is the XOR automaton.
  • Rule 30 produces high quality pseudo-random bits.
  • Rule 110 with suitably contrived input is Turing complete
    (Cook, 2004, proof first presented in 1998).


    • (This was my inspiration to try simple tiles.)

    Elementary Cellular Automata

  • Output is a grid of black and white squares.
  • Color each square based on squares to north-west, north, north-east.
  • Coloring need 8 choices of 2 colors → 256 automata.


    • Example: Rule 30, binary 00011110, north-west XOR (north OR north-east)

    Rule 30 As Tiles

    Trick: Tiles tell west and east neighbours the color of the north neighbour.

    Make an infinite pattern, with each notch filled by a bump, and with one big bang tile at the top.

    Comment: Berger used aperiodic Wang tiles to avoid the need for a big bang tile for a Turing machine. The same idea could also be applied here.

    Final Thought

    Maybe this is all perfectly normal.

    Resources

    Tilings Encyclopedia

    Grünbaum and Shephard (1987) Tilings and patterns

    Martin Gardner on Penrose Tiles

    Some Javascript apps I've written:
    Ghostsurn - Try to assemble square or hexagon-based tiles.
    Ghost Diagrams - Older version of the same idea.

    WaveFunctionCollapse - Maxim Gumin's pattern generator, uses local rules derived from an example pattern.

    Oh Gosh, I Didn't Even Mention

    The 3D Taylor tile. Kepler. Federation Square and Pinwheel tiling. The Robinson tiles. Schechtman's Nobel Prize. Quasi-crystal coated frying pans. The extensive contributions of Robert Ammann.