WARP rendering of Kari tiling.
WARP rendering of Culik tiling.
The Kari and Culik tiles are examples of aperiodic Wang tile sets. Aperiodic tile sets are tiles that can tile the infinite plane, but any such infinite tiling cannot be periodic.
In 1996 Kari [3] published a paper describing an aperiodic set of 14 Wang tiles, the smallest set of aperiodic Wang tiles known at the time. Kari’s discovery was followed very quickly by Culik [1] who, using Kalik’s basic method, found a set of 13 aperiodic Wang tiles. The two papers were published in the same volume of Discrete Mathematics. Culik’s tiles remained the smallest known set of aperiodic Wang tiles until a set of 12 was found by Jeandel and Rao [2] in 2021.
Using my WARP program I have rendered the Kari and Culik tile sets to illustrate the logic behind the tile matching rules from which the proof of aperiodicity is derived.
The proofs of non periodicity depend on the concept of a Beatty sequence.
Table of Contents
Beatty Sequences
A Beatty sequence is a series of the two integers that bracketthe value. The average value of a subsequence of a Beatty sequence converges to the required value as its length approaches infinity. For instance:
1 is 1,1,1,1…
1/3 is 0,0,1,0,0,1,0,0,1…
3/2 is 1,2,1,2,1,2…
The Kari Prototiles
The top edge value is regarded as “input” and the bottom value as “output”. Each tile has an associated multiplier, 2/3 or 2. The left and right edges represent “carries” and are all multiples of 1/3. The four edge values are related by the equation
input x q + left = output + right
The Kari tiles are divided into two subsets T2 and T2/3 according to the multiplier for each tile. Each row is made up of tiles with the same multiplier, the two subsets of tiles are confined to separate rows because the left and right values are unique across the subsets. An exception is zero, which is required in both subsets. In one subset zero is represented by 0’, which does not match 0, but arithmetically is treated as 0.
So the input of one row of tiles is the input of the previous row multipled by the appropriate value, 2 or 2/3. As no product of powers of 2 and 2/3 can equate to 1, with infinite row lengths no row can be exactly repeated. This means that an infinite tiling cannot be periodic.
The Culik Prototiles
The Culik tiles work in a similar way, but the multipliers are 3 and 1/2. All the carry values are multiples of 1/2.
My WARP Representation of the Tiles
The top and bottom values are rendered as rectangles. The sequence of rectangles in each row can therefore be read as a Beatty sequence. Each colour is an integer – purple is 1, green is 2, pale blue is 0.
The multiplier for a tile is represented by the two (Culik) or three (Kari) horizontal dots representing a finite Beatty sequence. The left and right edges “carries” are similarly represented by a vertical sequence of dots.
The Culik tiles with multiplier 3, T3, can be further divided into 3 overlapping subsets. Every tile in a T3 row must be in the same subset. I have marked these subsets with shallow sine curves, so every row that containing T3 tiles should have at least one unbroken sine curve. Note that these sine curves do not all have to match at tile edges, but at least one will.
The staggered vertical lines in each column of tiles represent, via the horizontal position, the input and output values, and the intermediate values input x q and input x q + left.
Artistic Licence
The colours of the vertical lines have no mathematical significance. They have been chosen for purely aesthetic reasons and the colour is changed according to the column the tile is in.
In the bottom of both tilings some of the tiles have been replaced with the traditional Wang tile rendering.
Interpreting the Kari Tiling
The top row here is made up entirely of tile number 1. This is because I have run my WARP program in a mode that selects tiles to try matching in the order they have been defined and so tries to start a tiling with the first tile in the set. The top of the Kari tiling here shows a row of purple rectangles – representing a row of 1‘s i.e. the Beatty Sequence for 1. The top row of tiles have 3 horizontal green dots. This green represents 2, so the multiplier is 2. All the top row tiles have the same values on the left and right edges so in each top row tile the left and right carries cancel out. The second row of triangles are all green, so the second row represents 2, correct for 2 times the first input row. The second row tiles have multiplier 2/3 represented by one blue dot (0) and two purple dots(1). The third row of rectangles has a repeated sequence of two purple rectangles followed by a single green tile, if you ignore the first column. (2 * 1 + 2)/3 gives 4/3, which is correct for 2/3 times 2.
An inifinite tiling would enable the Beatty sequences in the rows to be infinitely precise. In this finite tiling, errors are particularly likely to occur at edges, where the tile has not been constrained by a tile on one side. With only a finite set of tiles precision cannot be maintained so in a finite width tiling rows can be repeated. However, in an infinite tiling and hence infinite precision, no product of powers of 2 and 2/3 can yield 1, so no row can be repeated. The non-periodicity requirement for an aperiodic tile set only applies to infinite tilings.
References
[1] Culik, K. (1996) An aperiodic set of 13 Wang tiles, Discrete mathematics,
160(1), pp. 245–251. Available at:
https://doi.org/10.1016/S0012-365X(96)00118-5.
[2] Jeandel, E. and Rao, M. (2021) An aperiodic set of 11 Wang tiles, Advances
in Combinatorics (Online) [Preprint]. Available at:
https://doi.org/10.19086/aic.18614.
[3] Kari, J. (1996) A small aperiodic set of Wang tiles, Discrete mathematics,
160(1), pp. 259–264. Available at:
https://doi.org/10.1016/0012-365X(95)00120-L.
