--- title: Dimers on a design lead: Domino tilings of a plane design: the colour imbalance read off the code, tilings that never switch off, codes that tile late, and the carpet's growth constant bracketed. figure: research-dimers slug: dimers --- Tile a design with dominoes: every filled cell covered once, every domino on two cells that share a side. The count is exact through Kasteleyn's determinant once the holes are signed, the obstruction is read off the code, and the Kronecker product splits every tiling into the part inside the blocks and the part that crosses. The generator is `lab/py/design-dimers`; every number below is printed by one of its verbs. ## The object - Fix a base `base >= 2` and a plane code, and let `F` be the digits of the code: the cells `(i, j)` of the `base x base` grid whose bit `base*i + j` is set. The code is read at its own base, so level 1 is the mask itself. - Level `n` is `D_n = {(sum_(l= 1`, so `x + y = i_0 + j_0 mod 2`; the sign reads the lowest digit alone, and each lowest digit carries `fill^(n-1)` cells. The verb `imbalance` checks both laws against the coordinate count at every code of base 2 through level 6 and of base 3 through level 4, wrong 0 times. - **Proved.** A code with `s != 0` tiles no level. A domino covers one black and one white cell, so a tiling forces a zero imbalance, and both laws vanish only at `s = 0`. An odd fill makes `s` odd, so such a code never tiles. - The codes with `s = 0` are those with as many black as white digits, `C(base^2, floor(base^2/2)) - 1` of the nonempty ones by Vandermonde's identity: 5 of 15 at base 2 and 125 of 511 at base 3 (`imbalance`). ## Tileability climbs the levels - **Proved.** `T(n) >= T(n-1)^fill` and `T(n) >= T(1)^(fill^(n-1))`. A copy of `D_(n-1)` inside `D_n` keeps every edge it has on its own, so tiling each big block on its own tiles `D_n`, and the same holds for the small blocks. The levels a code tiles therefore form a ray `n >= n0` or are none; `n0` is the first tileable level. - **Proved.** When `n0` is finite the growth constant `theta = lim log T(n) / fill^n` exists and equals `sup_n log T(n) / fill^n`. Dividing the first inequality by `fill^n` gives `log T(n) / fill^n >= log T(n-1) / fill^(n-1)`, so the sequence is nondecreasing from `n0` on, and it is bounded by `log(4)/2` because a tiling is fixed by the partner each black cell picks among at most 4 neighbours. Every computed level is a lower bound on `theta`. - So the question splits in two: which codes tile at all, decided by `n0`, and how fast the count grows, decided by what crosses the block boundaries. ## The census of tileable codes - A component of the cell graph of `F` is sealed when none of its cells can meet a cell of a neighbouring small block: no cell `(i, base-1)` with `(i, 0)` in `F` and no cell `(i, 0)` with `(i, base-1)` in `F`, these two checked only when `F` has two cells side by side in a row, and the same for columns when `F` has two cells one above the other. - **Proved.** A sealed component with nonzero signed count makes every level untileable. The cell across the right edge of the small block at `X` from `base X + (i, base-1)` is `base (X + (0,1)) + (i, 0)`, present only when `X + (0,1)` is in `D_(n-1)` and `(i, 0)` is in `F`. `D_(n-1)` has two cells side by side only if `F` does: such a pair lies in one small block, a pair of `F`, or across two, a pair of `D_(n-2)`, and induction ends at `D_1 = F`. So each copy of a sealed component is a whole component of `D_n`, its signed count `+-` that of the component, and a component with nonzero signed count has no perfect matching. - **Proved**, by the census. At base 2 the 5 codes with `s = 0` (3, 5, 10, 12, 15) tile level 1. At base 3 the 125 codes with `s = 0` split into 97 that tile level 1, hence every level, and 28 in 5 orbits of the square's symmetries that tile no level, each by a sealed unbalanced component: `12, 33, 66, 96, 99, 102, 105, 114, 129, 132, 135, 141, 156, 165, 177, 204, 225, 258, 264, 267, 270, 282, 300, 330, 354, 396, 417, 450`. So at bases 2 and 3 a code tiles some level exactly when `s = 0` and it tiles level 1 (`census`). - **Proved.** The lemma holds for any code, so for `D_m` read as a code at base `base^m`, whose level `k` is `D_(km)`. A sealed unbalanced component of `D_m` makes every level `km` untileable, and since the tileable levels form a ray, every level. - **Proved**, by the census. At base 4, of the 12869 codes with `s = 0`, 5699 tile level 1 and 7170 in 945 orbits tile none of levels 1, 2 and 3; of these 7030 tile no level, 2253 by a sealed unbalanced component of `F`, 4709 more by one of `D_2` and 68 more by one of `D_3` (`census`). - **Proved.** A run certificate. Suppose the small blocks never meet vertically: `F` has no two cells one above the other, or no column `j` with `(0, j)` and `(base-1, j)` both in `F`. Then every component of every level lies in a horizontal run of `k` side-by-side small blocks, glued along the rows `i` with `(i, 0)` and `(i, base-1)` in `F`. Write `A -> B` when `F` minus the cells `(i, 0)`, `i` in `A`, and `(i, base-1)`, `i` in `B`, tiles, for sets `A, B` of such rows. A run of `k` blocks tiles exactly when a walk of length `k` leads from the empty set back to the empty set, the set at each step being the rows crossed between consecutive blocks. If no walk of positive length returns to the empty set, no level tiles. The same holds with rows and columns exchanged. - **Proved**, by the census. Of the other 140 base-4 codes, 72 in 10 orbits, among them `756` with rows `..#.`, `####`, `.#..`, `....`, meet in one direction only and have no walk back, so they tile no level; as a check, the 2803 codes that meet in one direction only and tile level 1 all have one. At base 4, 7102 codes with `s = 0` therefore tile no level (`census`). - **Verified.** The last 68 base-4 codes, in 9 orbits, `9914, 9970, 11234, 11243, 11246, 12111, 12142, 12235, 14841` up to symmetry, tile none of levels 1 to 4 and carry no sealed unbalanced component through level 4 (`census`). - **Refuted**, the law that level 1 decides: a code can tile late. `bang dim 2, base 5, code 19920882` has rows `.#..#`, `#####`, `#.###`, `#####`, `.#..#` and `s = 0`. Level 1 has no tiling: the pendants `(0,1), (0,4), (4,1), (4,4)` force their dominoes onto `(1,1), (1,4), (3,1), (3,4)`, then `(1,0)` must take `(2,0)`, and `(3,0)` is left with no free neighbour. At level 2 the bottom pendant `(4, j)` of a small block meets the top pendant `(0, j)` of the block below, and `T(2) = 252236412223488`, by Kasteleyn's determinant and by the brute-force transfer count alike (`census`). - **Verified.** `census` prints nine late codes, each untileable at level 1, unsealed, and tileable at level 2: base 5 codes `15571455, 19627890, 19757811, 19920882, 32709486, 32715747, 32715771, 32912238` in 7 orbits, with `T(2)` from `8208000` to `252236412223488`, each matched by the brute-force count, and base 7 code `136308971855667`, fill 32, with `T(2) = 141562531209631520359886210546943393792`. - **Verified**, a seeded sample. `search` draws dense codes from a fixed seed, each cell filled with probability `0.7`, keeps the distinct ones, and tries at level 3 the codes untileable at levels 1 and 2 with `fill^3 <= 16000` whose level-2 deficiency falls below `fill` times the level-1 deficiency. At base 5, 1500000 draws give 173638 distinct codes with `s = 0`, 83744 untileable at level 1, 62111 of those without a sealed component at level 1, 27 that tile first at level 2 in 13 orbits, and none that tiles first at level 3 among the 37957 tried. Every code within Hamming distance 4 of the 15 late base-5 orbits, the 13 found and 2 more from the codes above, gives 100824 orbits, 16 of them late, and none of the 14914 orbits tried at level 3 under the same size cap tiles there. At base 6, 300000 draws give 20668 distinct untileable codes without a sealed component at level 1, no late one, and none of the 10287 tried at level 3 tiles there; at base 7, 100000 draws give 6420 such codes and 2 late codes in 2 orbits. - **Conjecture.** No code tiles first at level 3 or later: `n0` is 1, 2 or infinite. - **Conjecture.** At even base level 1 decides: no code tiles first at level 2 or later. At base 4 it is proved for all but the 68 open codes, which are untileable through level 4, and it holds on the base-6 sample. - So the codes that tile no level include those with `s != 0` and those with a sealed unbalanced component at some level; at bases 2 and 3 these are all of them, at base 4 they and the run certificate settle all but at most the 68 open codes, and from base 5 on level 1 does not settle the question. ## Kasteleyn on a design - The weighting: a vertical edge `(r, c)(r+1, c)` gets the sign `(-1)^c`, and a horizontal edge `(r, c)(r, c+1)` gets `(-1)^h` with `h` the number of empty cells `(r', c)` of the `side x side` grid below it, `r' > r`; any box holding the set gives the same sign products, since changing the box flips every horizontal edge between one pair of columns and a cycle crosses each pair of columns an even number of times. `K` is the black-by-white matrix of these signs, zero off the edges. - **Proved.** For every set of cells of the square grid with as many black as white cells, `T = abs(det K)`. The column signs alone are Kasteleyn's alternate-column weighting of the full grid, under which a cycle of length `2k` enclosing `l` grid points has sign product `(-1)^(1+k+l)` ([Kenyon 2009](../REFS.md), section 3.3, Lemma 1). The path that leaves an empty cell `(r0, c)` half a step to the right and then runs straight up between columns `c` and `c+1` crosses exactly the horizontal edges `(r, c)(r, c+1)` with `r < r0`, and a cycle crosses it an odd number of times exactly when it encloses that cell; so the extra signs multiply a cycle's product by `(-1)` to the number of empty cells inside, and the product becomes `(-1)^(1+k+m)` with `m` the filled cells inside. In the superposition of two tilings the cells inside each cycle are tiled among themselves, so `m` is even, every cycle has product `(-1)^(1+k)`, and every term of `det K` carries the same sign ([Kenyon 2009](../REFS.md), section 3.4, Theorem 2; [Kuperberg 1998](../REFS.md), Theorem 3). - The correction is load-bearing: holes of odd area break the column signs alone, and every carpet hole has odd area `9^m`. The column signs alone give `abs(det K) = 0` on the carpet at levels 1 and 2. On 300 random cell sets of side 2 to 7, each cell filled with probability `0.8`, 64 of which tile, the corrected determinant and the matching test agree with a brute-force transfer count at all 300, the column signs alone at 291 (`count`, its control line). - Determinants are exact integers from PARI's `matdet`; a level of 4096 cells, a `2048 x 2048` matrix, takes about 15 s. ## The counts | level | cells | carpet, code 495 | sibling, code 255 | |---|---|---|---| | 1 | 8 | `2` | `4` | | 2 | 64 | `6724` | `1291616` | | 3 | 512 | `3862920381083436011392889139781518336` | `1565113733863335194512818740595861896518010511818752` | | 4 | 4096 | `10247586265502482333...42029316805289312256`, 316 digits | `98391239678669891170...03660377644046745600`, 414 digits | - **Verified.** The table is printed by `count`, Kasteleyn's determinant at every level and the brute-force transfer count at levels 1 and 2. Level 5, 32768 cells and a `16384 x 16384` determinant, is not computed. - **Verified.** The control `bang dim 2, code 15` gives `2, 36, 12988816, 2444888770250892795802079170816` at levels 1 to 4, the `2^n x 2^n` terms of [A004003](https://oeis.org/A004003), and at levels 5 and 6, 126 and 511 digits, it matches Kasteleyn's product `prod_(j,k <= side/2) (4 cos^2(pi j/(side+1)) + 4 cos^2(pi k/(side+1)))` ([Kenyon 2009](../REFS.md), section 4.1, which prints the full product over `j, k <= side`; restated here over the half) rounded from PARI at a precision past the digit count (`count`). - **Proved.** `bang dim 2, base 3, code 63`, the top two rows, has `T(n) = F(3^n + 1)^(2^(n-1))` with `F` the Fibonacci numbers. Its rows are the integers with base-3 digits in `{0, 1}`, which come in `2^(n-1)` pairs `3m, 3m+1` separated by an empty row, and its columns are all `3^n`; so level `n` is `2^(n-1)` disjoint `2 x 3^n` strips, and a `2 x N` strip has `F(N+1)` tilings. So `log T(n) / 6^n = 2^(n-1) log F(3^n + 1) / 6^n`, and `log F(N+1) / N -> log(phi)` with `phi` the golden ratio gives the growth constant `theta = log(phi)/2`. `count` matches the formula at levels 1 to 4. - **Conjecture.** The odd part of the carpet's count is a square at every level: `T(n) = 2^a q^2` with `a = 1, 2, 10, 128` and `q = 1, 41, 61419729604189833` and a 139-digit `q` at level 4 (`count`). The sibling's odd part is not a square at levels 2, 3 and 4, and the control's is, `2^(2^(n-1))` times an odd square. ## What crosses - A tiling of `D_n` does not factor over the big blocks: some dominoes cross from one copy of `D_(n-1)` to the next. Weight each edge between two big blocks by `x` and write `P_n(x) = sum_k N_k x^k` for the weighted determinant, so `N_k` counts the tilings with exactly `k` crossing dominoes, `N_0 = T(n-1)^fill` counts those that respect the blocks and `P_n(1) = T(n)`. The sign argument runs tiling by tiling, so `det K(x)` is the common sign times `sum_M x^(k(M))` as a polynomial, `k(M)` the crossing dominoes of the tiling `M`; `cross` evaluates `det K` at `x = 0, 1, ..., E`, `E` the number of crossing edges, and interpolates in PARI. - **Proved.** At level `n >= 2` of a code that tiles some level, the number of dominoes crossing between big blocks is even. Some `fill^m` is even, so `fill` is, and each big block has `fill^(n-1)` cells, an even number; the cells of a block left by the crossing dominoes are tiled inside it, so each block holds an even number of crossing ends. Side-by-side blocks sit at digits `a` of opposite parity, so each crossing domino has exactly one end in a block whose digit has even parity, and the count is a sum of even numbers. At level 1 the blocks are single cells and the count is the number of dominoes. `cross` finds `N_k = 0` at every odd `k` and `N_k > 0` at every even `k` up to the maximum, for the carpet and its sibling at levels 2 and 3 and for the control at levels 2, 3 and 4. - **Verified.** On the carpet at level 2, `P_2(x) = ((x^2 + 2)^4 + x^8)^2`: `N_k = 256, 1024, 1792, 1792, 1152, 512, 160, 32, 4` at `k = 0, 2, ..., 16`, out of 24 crossing edges, and `T(2) = (3^4 + 1)^2 = 82^2`. At level 3, `P_3(x)` is `2^10` times the square of an integer polynomial, with up to 64 of the 72 crossing edges used (`cross`). - **Verified.** The tilings that respect the blocks are a vanishing share. On the carpet, `T(n)/N_0 = 26.265625` at level 2 and `924472.759617` at level 3, rounded; a tiling crosses on average `5.463415` of 24 edges at level 2 and `20.830336` of 72 at level 3, a share of the crossing edges rising from `0.227642` to `0.289310`. On the sibling, with 20 and 40 crossing edges, the ratios are `19.708496` and `202.059174` and the shares `0.239655` and `0.222924`, and `P_n` is not a constant times a square (`cross`). - Respecting the small blocks as well leaves `T(1)^(fill^(n-1))` tilings, `2^64` against `T(3) = 3862920381083436011392889139781518336` on the carpet. ## The growth constant - **Proved.** `theta <= lim_n (1/(4 fill^n)) sum_v log d_v`, the sum over the cells of level `n` and `d_v` the degree. Hadamard's inequality bounds `abs(det K)` by the product of the row norms, `prod_(black) sqrt(d)`, and by the product of the column norms, `prod_(white) sqrt(d)`, and the two bounds multiply to `T(n)^2 <= prod_v sqrt(d_v)`. The degree of a cell is 4 less its exposed sides. A side of a cell `base X + a` is exposed when it faces an empty cell inside the mask, or, when `a` sits on that edge of the mask, when `X` is exposed on the same side or the cell on the opposite edge, same row or column, is empty; `growth` runs that 16-state recursion, and the bound converges: each digit acts on the exposure as `E -> (E and m) or c` for masks `m, c` fixed by the digit, an idempotent map, so every state reached has a self-loop, the 16-state chain is aperiodic and its distribution, hence the bound, converges. The printed limits agree to 13 digits at levels 60 and 400. - **Verified.** The brackets, lower end the level-4 value of `log T(n) / fill^n` rounded down and upper end the Hadamard limit rounded up: carpet `0.177084 <= theta <= 0.286093`, sibling `0.232728 <= theta <= 0.296173` (`growth`). - **Proved.** Two exact constants. A code whose small blocks never meet, because `F` has no two cells side by side in a row or no row `i` with `(i, 0)` and `(i, base-1)` both in `F`, and the same for columns, has `T(n) = T(1)^(fill^(n-1))` and `theta = log T(1) / fill`; `bang dim 2, base 3, code 27`, a `2 x 2` square in the corner, gives `log(2)/4 = 0.173286...` (`growth` checks `T(n) = 2^(4^(n-1))` through level 3). Code 63 gives `theta = log(phi)/2 = 0.240605...` from its strips, `phi` the golden ratio. The control's constant is Kasteleyn's `G/pi = 0.291560...`, `G` Catalan's constant ([Kenyon 2009](../REFS.md), section 4.1), which its printed levels approach from below. - **Conjecture.** The increment `log T(n)/fill^n - log T(n-1)/fill^(n-1)` decays at a ratio tending to `c/fill`, `c` the most cells two side-by-side blocks share along an edge of the mask: 3 of 8 on the carpet, 2 of 8 on the sibling, 2 of 4 on the control, 2 of 6 on code 63. The printed ratios are `0.5254, 0.4676` on the carpet, `0.2226, 0.2405` on the sibling, `0.6306, 0.5443, 0.5183, 0.5085` on the control and `0.3032, 0.3332` on code 63 (`growth`). - **Conjecture.** The carpet's constant lies between its two geometric-tail closures, `0.184611` at ratio `3/8` and `0.188101` at the last printed ratio. Closing the series the same way from the last level puts the control at `0.291510` and `0.291669` around `G/pi = 0.2915609...` and code 63 at `0.240606` and `0.240605` against `log(phi)/2 = 0.2406059...`; the sibling closes at `0.233559` and `0.233518` (`growth`). ## Known elsewhere - Kasteleyn counts the dimer coverings of the rectangle by Pfaffians ([Kasteleyn 1961](../REFS.md)); the per-cell constant `G/pi` and the sign lemma used above are read here in [Kenyon 2009](../REFS.md), sections 3.3, 3.4 and 4.1, and the flat-weighting theorem in [Kuperberg 1998](../REFS.md), Theorem 3. - On the Sierpinski gasket, whose copies meet at three outmost vertices, four counts indexed by which outmost vertices are covered close under a recursion, and the entropy is exactly `ln(2)/3` per site ([Chang and Chen 2008](../REFS.md), Theorem III.2); self-similar graphs glued at two or three vertices are counted by explicit recursions ([Teufl and Wagner 2009](../REFS.md)), and close-packed dimers on finitely ramified square-lattice fractals have their entropies computed numerically from exact recursions ([Marcetic, Elezovic-Hadzic and Zivic 2020](../REFS.md)). - The carpet is infinitely ramified: two big blocks of level `n` meet along `3^(n-1)` edges where the gasket's copies meet at one vertex, so the gasket's recursion on a few boundary counts has no direct analogue, and the sources read here count no domino tiling of it. ## Open - A code that tiles first at level 3, or a proof that `n0` is 1, 2 or infinite. - A proof that level 1 decides at even base. - A decision procedure for `n0` read off the code, past the sealed and run certificates; at base 4 the 68 open codes are its first test. - The carpet's constant: an upper bound that closes on `0.177084`, a transfer operator on the `3^(n-1)` crossing edges, or level 5 in exact arithmetic. - Why the carpet's odd part is a square, and the closed form behind `P_2(x) = ((x^2 + 2)^4 + x^8)^2`.