dimers.md

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<n) base^l i_l, sum_(l<n) base^l j_l) : (i_l, j_l) in F}, the n-th Kronecker power of the mask, inside the side x side grid with side = base^n; it has fill^n cells. A cell is (r, c), row r, column c.
• D_n is fill copies of D_(n-1) placed at base^(n-1) F, the big blocks, and also fill^(n-1) copies of F placed at base D_(n-1), the small blocks.
• The cell graph joins two cells that share a side. A domino tiling of level n is a perfect matching of its cell graph, and T(n) counts them. A cell is black when r + c is even.
• The signed count of the code is s = sum_((i,j) in F) (-1)^(i+j).
• The carpet's tile is bang dim 2, base 3, code 495, the ring of 8 cells, with T(1) = 2. Its sibling bang dim 2, base 3, code 255 drops a corner instead of the centre. The control is bang dim 2, code 15, whose level n is the full 2^n x 2^n square.

The colour imbalance

• Proved. The black-minus-white count of level n is s^n at odd base and fill^(n-1) s at even base. A cell of D_n is (x, y) with x = sum base^l i_l and y = sum base^l j_l. At odd base every base^l is odd, so x + y = sum_l (i_l + j_l) mod 2; the sign (-1)^(x+y) is the product of the digit signs and the sum over D_n = F^n factors as s^n. At even base base^l is even for 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, 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, section 3.4, Theorem 2; Kuperberg 1998, 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

• 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, 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, 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, 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); the per-cell constant G/pi and the sign lemma used above are read here in Kenyon 2009, sections 3.3, 3.4 and 4.1, and the flat-weighting theorem in Kuperberg 1998, 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, Theorem III.2); self-similar graphs glued at two or three vertices are counted by explicit recursions (Teufl and Wagner 2009), and close-packed dimers on finitely ramified square-lattice fractals have their entropies computed numerically from exact recursions (Marcetic, Elezovic-Hadzic and Zivic 2020).
• 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.