betaFeedback

WorksComputer Science

Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete

Abstract

An important question in counting complexity is whether exact counting can remain hard under restrictions that make feasibility easy. Tilings of squares by a fixed family of polyominoes provide a stringent test of this question, since tileability is polynomial-time decidable and the only varying input is a binary-encoded side length. We prove that there exists a fixed finite family of connected polyominoes for which counting translation-only square tilings is #EXP-complete under polynomial-time metric reductions, while the counting function belongs to #E. The resulting separation reveals that solution multiplicities can retain computational information that feasibility alone cannot capture. The proof develops a two-stage numerical isolation technique that combines a boundary-amplified Wang system with a rigid geometric compiler to recover accepting-computation counts while controlling all noncanonical tilings.

Introduction

Feasibility and exact counting can have sharply different computational complexity. This difference is particularly revealing for problems whose inputs leave little freedom to encode computation. Polyomino tilings provide a classical geometric setting for investigating this issue, since the choice of permitted pieces and the shape of the region offer two distinct sources of variation. Restricting these sources in turn brings into focus how much computational information can remain in the number of tilings even when feasibility is easy to determine.

Classical results illustrate how the representation of a tiling instance affects its complexity. Domino tilings admit efficient counting algorithms based on Pfaffian methods [8], while more general tiling problems exhibit substantial computational hardness [12]. Pak and Yang [16] proved that counting tilings of simply connected regions by a fixed finite family of rectangles is #P-complete. Thus, fixing the pieces still leaves the boundary of the input region available to encode computation. A stronger restriction is to require every region to be an ordinary square, leaving its side length as the only varying parameter.

For a fixed finite family TT of polyominoes, let gT(n)g_T(n) be the number of tilings of the n×nn \times n square using translations of pieces in TT. With nn given in binary, O(log⁡n)O(\log n) bits can describe a square containing n2n^2 cells. The central question is whether this restricted input can still yield a #EXP-complete counting function. This fixed-family square-counting problem was formulated by Pak [14 Conjecture 1.7]. Moreover, the tileability of an m×nm \times n rectangle can be decided in O(log⁡m+log⁡n)O(\log m + \log n) time for every fixed family of tiles [14 Theorem 1.9]. The setting therefore offers a stringent test of whether solution counts can retain computational information beyond what feasibility reveals.

Our main theorem answers this question affirmatively. Here #EXP\#\mathrm{EXP} counts accepting paths of nondeterministic machines running in time 2poly⁡(ℓ)2^{\operatorname{poly}(\ell)} on inputs of length ℓ\ell, and #E\#\mathrm{E} denotes the subclass with time bound 2O(ℓ)2^{O(\ell)}. Hardness is understood under polynomial-time metric reductions [10], which recover the source count by polynomial-time postprocessing of a target count given in binary.

Theorem 1.1 (Main theorem). There exists a fixed finite family T⋆\mathcal{T}^{\star} of nonempty connected polyominoes such that counting translation-only tilings of the n×nn \times n square, with nn given in binary, is #EXP\#\mathrm{EXP}-complete under polynomial-time metric reductions. The counting function belongs to #E\#\mathrm{E}.

The #E\#\mathrm{E} upper bound follows by canonically encoding a tiling and checking it in time exponential in the bit length of nn. The central challenge is hardness. The count for an unmodified square includes every tiling admitted by its fixed pieces, not just configurations representing an encoded computation. Recovering the desired accepting-path count therefore requires control over the aggregate contribution of all these configurations. The proof achieves this by numerical isolation, arranging for the intended computation histories to contribute a common multiplicative factor while the entire remaining contribution is smaller than that factor. Integer division then recovers the target count exactly. This principle is implemented at two successive levels.

The first level uses a fixed Wang-tile system to encode accepting computations. Local edge-matching rules have long been used to simulate computation [20, 4, 17], and fixed translationally invariant systems with binary-encoded dimensions provide related examples of computational hardness [6, 1]. A fixed-Wang-square counting result was also reported by Mennen and Pak [15]. In the present construction, a scanner reconstructs a machine’s initial configuration from the binary side length, and a Wang tableau records its accepting branches. A boundary amplifier gives the intended full-frame histories a dominant multiplicity, while a bound on all other boundary modes allows their contribution to be separated arithmetically. Crucially, the same construction bounds the number of open Wang tilings of any rectangle exponentially in its perimeter, providing the control needed by the geometric stage.

The second level realizes the Wang system using a fixed family of connected polyominoes. Geometric encodings of local matching rules provide a starting point [5, 13]; here the central issue is preserving exact counts over all geometric tilings. Each Wang tile is represented by a carrier whose interior cavity records its identity and whose interfaces encode matching data. Local rigidity aligns the carriers on a common macrogrid, and the open-interface structure partitions the grid into rectangles. This gives an exact decomposition of the polyomino tiling count into contributions from rectangular dissections. The single-block configuration carries the Wang count, whereas every nontrivial dissection loses interface-label multiplicity along its seams. Bounds on seam length, the number of dissections, and the Wang counts within their blocks together make the total noncanonical contribution strictly smaller than one unit after normalization. A second integer division therefore extracts the Wang count.

Composing the two numerical readouts gives the required polynomial-time metric reduction. More broadly, numerical isolation combines a dominant term encoding accepting computations with global combinatorial bounds on the remaining configurations. Together with rigid geometric compilation, this provides a route to exact counting hardness in other succinctly specified systems with fixed local rules.

Preliminaries

The tiling conventions, counting complexity classes, metric reductions, and machine notation are specified below.

All regions are subsets of Z2\mathbb{Z}^{2}; a finite set is 4-connected if its grid-adjacency graph is connected.

Let bin⁡(n)\operatorname{bin}(n) denote the canonical binary representation of nn, with bin⁡(0)=0\operatorname{bin}(0)=0. For n≥0n \ge0, write Squaren={0,…,n−1}2\mathrm{Square}_{n}=\{0,\ldots,n-1\}^{2}, with Square0=∅\mathrm{Square}_{0}=\varnothing. Rectangles of positive width ww and height hh are denoted by Rectw,h={0,…,w−1}×{0,…,h−1}\mathrm{Rect}_{w,h}=\{0,\ldots,w-1\}\times\{0,\ldots,h-1\}.

If T={τ1,…,τk}T=\{\tau_{1},\ldots,\tau_{k}\}, a TT-tiling of a finite region Ω\Omega is a finite set of placements (t,v)∈{1,…,k}×Z2(t,v)\in\{1,\ldots,k\}\times\mathbb{Z}^{2} whose translates τt+v\tau_{t}+v are pairwise disjoint and have union Ω\Omega. Only translations are allowed. The empty region has one empty tiling.

A Wang system is a finite set of labelled tile types, each carrying north, east, south, and west colours. Distinct tile types are allowed to carry the same four colours. An open Wang tiling of a finite rectangle assigns a tile type to each cell, matches colours on internal edges, and imposes no condition on colours exposed along the geometric boundary. This type-level convention is important in § 7, where the geometric compiler preserves tile identity even when four edge colours coincide.

The class #EXP\#\mathrm{EXP} is used in its standard complexity-theoretic sense: it consists of total functions f:{0,1}∗→Nf:\{0,1\}^{*}\to\mathbb{N} equal to the number of accepting paths of a nondeterministic Turing machine that halts within 2p(∣x∣)2^{p(|x|)} steps for some polynomial pp. Likewise, NEXP\mathrm{NEXP} denotes nondeterministic time 2poly⁡(∣x∣)2^{\operatorname{poly}(|x|)}. The linear-exponential counting subclass is denoted by #E:=#NTIME(2O(∣x∣))\#\mathrm{E}:=\#\mathrm{NTIME}(2^{O(|x|)}). All counting functions in this paper are total: malformed or noncanonical binary strings receive value zero.

Proposition 2.1 (Fixed-family square counts lie in #E\#\mathrm{E}). For every fixed finite family TT of finite polyominoes, the function GTG_T belongs to #E\#\mathrm{E}.

Proof. Let ℓ=∣bin⁡(n)∣\ell=|\operatorname{bin}(n)|. A tiling of Squaren\mathrm{Square}_{n} has at most n2n^{2} placements. Encode the placements in a canonical lexicographic order, recording for each one its fixed tile type and its anchor coordinates. Because TT is fixed, the resulting witness has O(n2ℓ)O(n^{2}\ell) bits, which is 2O(ℓ)2^{O(\ell)}. A deterministic verifier checks containment, pairwise consistency, and exact coverage in time polynomial in this witness length. The canonical ordering gives one accepting witness per tiling. Since n<2ℓn<2^{\ell}, both witness generation and verification take 2O(ℓ)2^{O(\ell)} time.

A polynomial-time metric reduction from f:{0,1}∗→Nf:\{0,1\}^{*}\to\mathbb{N} to g:{0,1}∗→Ng:\{0,1\}^{*}\to\mathbb{N} is a pair of polynomial-time functions rr and hh satisfying f(x)=h(x,g(r(x)))f(x)=h(x,g(r(x))) for every xx, where the integer argument of hh is given in binary. Thus the running time of h(x,y)h(x,y) is measured in ∣x∣+∣bin⁡(y)∣|x|+|\operatorname{bin}(y)|. This is Krentel’s metric-reduction model [10]. For a counting function ff, write supp⁡(f)={x:f(x)>0}\operatorname{supp}(f)=\{x:f(x)>0\} for its support language.

For a one-tape machine with tape alphabet Γ\Gamma, state set QQ, and sentinel symbol #s\#_{\mathrm{s}}, a cell is either plain⁡(a)\operatorname{plain}(a) or hd⁡(q,a)\operatorname{hd}(q,a). A legal extended configuration of height H≥3H\ge3 is a word on indices −1,0,…,H-1,0,\ldots,H with sentinel cells plain⁡(#s)\operatorname{plain}(\#_{\mathrm{s}}) at −1,0,H−1,H-1,0,H-1,H, exactly one head cell at an index in {1,…,H−2}\{1,\ldots,H-2\}, and plain cells elsewhere. A labelled arrow is a tuple α=(q,a,q′,b,D)\alpha=(q,a,q',b,D), with D∈{L,S,R}D\in\{L,S,R\}; an arrow is inapplicable if its requested move would enter a sentinel. Distinct labelled arrows count as distinct computation branches even when they induce the same tape update.

Proof strategy

The hardness proof proceeds through two numerical readouts. The first uses a fixed nondeterministic machine whose accepting-path count CU(x)C_U(x) is #EXP\#\mathrm{EXP}-complete. A polynomial-time map encodes $x as a positive binary side length n=Eside(x)n = E_{\mathrm{side}}(x). The Wang construction of § 4–§ 5 has a total open-square tiling count aprod(n)a_{\mathrm{prod}}(n). For all sufficiently large encoded side lengths, its full boundary class contributes a fixed multiple of 1+CU(x)1 + C_U(x), while the other boundary classes contribute a remainder JW(n)J_W(n) satisfying

aprod(n)=Q4n−4(1+CU(x))+JW(n),0≤JW(n)<Q4n−4.(1)a_{\mathrm{prod}}(n) = Q^{4n-4}(1 + C_U(x)) + J_W(n), \qquad0 \le J_W(n) < Q^{4n-4}. \tag*{(1)}

The full boundary frame has 4n−44n - 4 independently labelled sites. Every proper boundary mode has fewer such sites, and the number of compatible tableaux can be controlled by a perimeter-scale bound. Division by Q4n−4Q^{4n-4} therefore retrieves the accepting-path count, with the finitely many exceptional inputs handled by a fixed table.

The second readout is geometric. § 7 represents the fixed Wang system by connected polyominoes with a constant macrocell pitch PsP_s and samps_{\mathrm{amp}} possible labels on each open interface. The total number En=2n(n−1)E_n = 2n(n - 1) of macrogrid adjacencies gives the canonical one-block contribution sampEnaprod(n)s_{\mathrm{amp}}^{E_n}a_{\mathrm{prod}}(n). All other geometric tilings are classified by rectangular partitions, whose seams reduce the number of available labels. Denoting their aggregate contribution by JP(n)J_P(n), the geometric counting identity yields

gT⋆(Psn)=sampEnaprod(n)+JP(n),0≤JP(n)<sampEn.(2)g_{T^\star}(P_s n) = s_{\mathrm{amp}}^{E_n}a_{\mathrm{prod}}(n) + J_P(n), \qquad0 \le J_P(n) < s_{\mathrm{amp}}^{E_n}. \tag*{(2)}

This second inequality follows from a lower bound on seam length, an exponential bound on the number of rectangular partitions, and the perimeter bound for open Wang rectangles. The exact geometric interfaces are defined in § 7, where Figure 2 and Figure 3 accompany their respective counting arguments.

Figure 2. A connected carrier and the geometry of a matching interface. The interior cavity records the identity of the simulated Wang tile. A fixed and a variable dent–bump pair encode the state of an open interface. Matching addresses force agreement of the adjacent local data.

Figure 3. One-block and nontrivial rectangular decompositions of the macrogrid. Each closed adjacency on an internal seam removes one independent interface-label choice. The canonical one-block term therefore has the maximum interface multiplicity, while other decompositions are bounded by their seam length.

Together, these identities describe how the accepting-path count is encoded first in the open Wang-square count and then in the translation-only polyomino-square count. The first numerical readout separates the intended computation histories from other Wang boundary modes, while the second separates the canonical one-block contribution from all other polyomino tilings. Applied in reverse order, the two floor divisions recover the original accepting-path count. § 8 and § 9 establish the bit-complexity bounds required for the resulting metric reductions.

Encoding an Exponential-Time Counting Computation

The hardness reduction begins with a fixed counting machine whose initial configuration can be reconstructed from the square’s side length. Parsimonious simulation and polynomial padding provide a universal accepting-path counter. A self-delimiting encoding then places its input in the binary side length; the final bounds ensure that the encoded computation can be recovered and completed within the available tableau.

Theorem 3.1 (Computation encoded by the side length). There are a fixed one-head nondeterministic Turing machine M⋆M_\star, a counting function CU∈#EC_U \in\#\mathrm{E} that is #EXP\#\mathrm{EXP}-complete under parsimonious reductions, and a polynomial-time injective map Eside:{0,1}∗→NE_{\mathrm{side}} : \{0,1\}^\ast\to\mathbb{N} with the following property. Let Acc⁡⋆(n)\operatorname{Acc}_\star(n) be the number of accepting length-nn branches of M⋆M_\star from the initial configuration determined by the binary digits of nn. Then, for every n≥5n \ge5,

Acc⁡⋆(n)={1+CU(x),n=Eside(x),1,n∉Eside({0,1}∗).\operatorname{Acc}_\star(n) = \begin{cases} 1 + C_U(x), & n = E_{\mathrm{side}}(x),\\ 1, & n \notin E_{\mathrm{side}}(\{0,1\}^\ast). \end{cases}

On encoded side lengths n=Eside(x)n = E_{\mathrm{side}}(x), the parser, input preparation, and simulation reach an accepting or rejecting stay-sink within n−1n - 1 steps. Both stay-sinks have unique continuations.

Proof. We first normalize an arbitrary #EXP counting machine without changing its path count. Let the source machine be fixed and suppose that, on inputs of length ss, every branch halts within T(s)=2p(s)T(s)=2^{p(s)} steps for a polynomial pp. Enlarging pp if necessary, assume p(s)≥s+1p(s)\ge s+1. A finite transition list is encoded self-delimitingly by unary indices for states and letters and fixed unary codes for the three head movements. The decoding procedure is deterministic and polynomial in the code length.

For later use, suppose a source pair has at most dmax⁡d_{\max} outgoing arrows. Its choice can be replaced by a complete binary tree of depth

ktree={1,dmax⁡≤1,min⁡{k:2k≥dmax⁡},dmax⁡≥2.k_{\mathrm{tree}} = \begin{cases} 1, & d_{\max} \le1,\\ \min\{k:2^k \ge d_{\max}\}, & d_{\max} \ge2. \end{cases}

Leaves representing unused choices enter a rejecting sink. Accepting and rejecting sinks each have one stay-arrow on every tape letter. A selected original arrow determines one tree path, so the conversion is bijective on labelled computation paths.

For a machine with tt tapes, store all tapes in one contiguous block, recording a letter and a head bit for each simulated tape. After uu steps the block length is at most t(s+u+1)t(s+u+1). A scan, rewrite, and head-bit update costs at most 2t(s+u+1)+162t(s+u+1)+16. Summation for 0≤u<T(s)0\le u<T(s) gives

T(s)(2t(s+T(s)+1)+16)≤22p(s)+ct.T(s)\bigl(2t(s+T(s)+1)+16\bigr)\le2^{2p(s)+c_t}.

for a constant ctc_t depending only on the fixed source machine, after enlarging it to cover finitely many small inputs. Applying the binary-tree replacement above to each nondeterministic choice has constant depth, so the fully converted one-tape binary machine halts within 2q(s)2^{q(s)} steps for some polynomial qq depending only on the source machine. All work inserted between nondeterministic choices is deterministic, so the path count is unchanged.

The fixed machine Ulog⁡U_{\log} parses strings of the form

1k0 codeM 1p0z,∣codeM∣=k,1^k0\,\mathrm{code}_M\,1^p0z,\qquad|\mathrm{code}_M|=k,

where the unary block 1p1^p is padding. It converts the decoded transition list once and simulates the resulting binary machine on zz for exactly 2m2^m simulated steps, where mm is the total input length. Missing transitions have already been redirected to the rejecting sink, and after the simulated-step budget any branch that has not reached a stay-sink is sent deterministically to the rejecting stay-sink. A simulated tape block has length at most 2m+2m+42^m+2m+4, so one simulated step costs at most 22m+22^{2m+2} for m≥1m\ge1. Including parsing, the running time is at most m2+4m+32+23m+2+2m≤28(m+1)m^2+4m+32+2^{3m+2}+2^m\le2^{8(m+1)}. The inequality is checked directly for m=0,1m=0,1; for m≥2m\ge2, m2+4m+32≤23mm^2+4m+32\le2^{3m}. Set pU(m)=8(m+1)p_U(m)=8(m+1). Thus Ulog⁡U_{\log} reaches a stay-sink within 2pU(m)2^{p_U(m)} steps.

Let CU(x)C_U(x) count the paths in the accepting sink at that time. A binary clock of pU(m)+1p_U(m)+1 bits makes a genuinely halting simulator. Its tape length is at most m+2pU(m)+4m+2^{p_U(m)}+4; hence its running time is at most

2pU(m)(m+2pU(m)+pU(m)+8)2≤23pU(m)+2≤226(m+1).2^{p_U(m)}\bigl(m+2^{p_U(m)}+p_U(m)+8\bigr)^2\le2^{3p_U(m)+2}\le2^{26(m+1)}.

For hardness, let f∈#EXPf\in\#\mathrm{EXP} and apply the preceding conversions to a fixed machine computing ff. Let codef\mathrm{code}_f be its transition code before the binary-tree conversion, and let qf(s)q_f(s) be a polynomial such that the converted machine halts within 2qf(s)2^{q_f(s)} steps on every input of length ss. Choose a fixed constant cfc_f large enough to cover the delimiters and code, and define the parsimonious source map

rf(z)=1∣codef∣0 codef 1qf(∣z∣)+cf0z.r_f(z)=1^{|\mathrm{code}_f|}0\,\mathrm{code}_f\,1^{q_f(|z|)+c_f}0z.

Its output length mm is polynomial in ∣z∣|z| and satisfies m≥qf(∣z∣)m \ge q_f(|z|). Hence the 2m2^m-step universal simulation outlasts every converted computation. Once the simulated machine reaches an accepting or rejecting stay-sink, the continuation is unique, so accepting paths are preserved bijectively. Thus CU(rf(z))=f(z)C_U(r_f(z)) = f(z) for every zz, and CUC_U is #EXP-complete under parsimonious polynomial-time reductions. Notice that CUC_U itself is computable by a nondeterministic machine in linear-exponential time; the polynomial padding in rfr_f is what allows hardness for the full standard #EXP class.

Moreover, if L∈NEXPL \in\mathrm{NEXP}, the function counting accepting paths of a nondeterministic 2poly⁡(∣z∣)2^{\operatorname{poly}(|z|)}-time machine deciding LL belongs to #EXP and has support exactly LL. Parsimonious completeness therefore implies that the support language supp⁡(CU)\operatorname{supp}(C_U) is NEXP-hard.

For m=∣x∣m = |x|, define the self-delimiting word and its numerical value by

β(x)=1x1 0m1 072m+72,Eside(x)=val⁡2(β(x)).\beta(x) = 1x1\,0^m1\,0^{72m+72}, \qquad E_{\mathrm{side}}(x) = \operatorname{val}_2(\beta(x)).

Its length is Lenc(x)=74m+75=8pU(m)+10m+11L_{\mathrm{enc}}(x) = 74m + 75 = 8p_U(m) + 10m + 11. Reading from the least significant end, count the terminal zero run, cross its following separator 1, and count the next zero run of length mm. The next separator 1 is then checked and skipped before reading the preceding mm bits as xx; the remaining leading bit must be 1, with no further bits. Checking that the first run has length 72m+7272m+72 recovers xx uniquely. The procedure scans only polynomially many bits and proves injectivity and polynomial-time decodability.

Since Eside(x)≥2Lenc(x)−1E_{\mathrm{side}}(x) \ge2^{L_{\mathrm{enc}}(x)-1},

Lenc(x)−14=2pU(m)+5m2+52≥2pU(m)+2.\frac{L_{\mathrm{enc}}(x)-1}{4} = 2p_U(m) + \frac{5m}{2} + \frac{5}{2} \ge2p_U(m) + 2.

Writing t=2pU(m)t = 2^{p_U(m)}, we have 4t2≥t+14t^2 \ge t + 1, and therefore

2pU(m)+1≤2(Lenc(x)−1)/4≤Eside(x)1/4.2^{p_U(m)} + 1 \le2^{(L_{\mathrm{enc}}(x)-1)/4} \le E_{\mathrm{side}}(x)^{1/4}.

Also Lenc(x)≥75L_{\mathrm{enc}}(x) \ge75, giving Eside(x)≥274E_{\mathrm{side}}(x) \ge2^{74}. Binary branching further gives 1+CU(x)≤2Eside(x)1/41 + C_U(x) \le2^{E_{\mathrm{side}}(x)^{1/4}}.

We next define M⋆M_\star. Its alphabet contains that of Ulog⁡U_{\log}, the sentinel #s, delimiters markL, markR, and finitely many parser letters. At its start pair it has exactly two arrows. The null arrow enters the accepting stay-sink. The real arrow enters a deterministic parser.

Write Cfg⁡⋆\operatorname{Cfg}_\star for the initial configuration specified by the binary digits of nn. On Cfg⁡⋆\operatorname{Cfg}_\star, the sentinels occupy −1,0,n−1,n-1, 0, n-1, n. The head is at index 1, on the least significant bit. For 1≤y≤n−31 \le y \le n-3, index y+1y+1 stores oneb_b if the yy-th bit of nn is one, zerob_b if it is zero below the leading bit, and workb_b above the leading bit. The inequalities n<2n−2n < 2^{n-2} (for n≥5n \ge5) and ⌊log⁡2n⌋≤n−3\lfloor\log_2 n \rfloor\le n-3 show that the two omitted high bits are zero and that the leading bit remains inside the sentinel interval. At n=4n=4, the omitted bit at position 2 is one.

The parser reads terminal zeros, the two separators, and the candidate xx, and checks Rpad(m)=72m+72R_{\mathrm{pad}}(m) = 72m+72. It then inspects the cell immediately north of the recovered leading one. A workb_b accepts the high-zero continuation; a bit letter or sentinel rejects. Thus a successful parse occurs exactly when n=Eside(x)n = E_{\mathrm{side}}(x).

After a successful parse, the machine writes markL, then 2pU(m)+12^{p_U(m)}+1 blanks, a copy of xx, another 2pU(m)+12^{p_U(m)}+1 blanks, and markR. It restores parser scratch and starts Ulog⁡U_{\log} on the copied bit letters. The head cannot reach either mark during 2pU(m)2^{p_U(m)} steps. The copy remains between the sentinels because

2pU(m)+1+Lenc(x)+m+6≤2pU(m)+3≤8Eside(x)1/4<Eside(x)−2.2^{p_U(m)+1} + L_{\mathrm{enc}}(x) + m + 6 \le2^{p_U(m)+3} \le8E_{\mathrm{side}}(x)^{1/4} < E_{\mathrm{side}}(x) - 2.

The parser takes at most (Lenc(x)+4)4(L_{\mathrm{enc}}(x)+4)^4 steps, the copy at most m22pU(m)+6m2^{2p_U(m)+6}, and the simulation at most 2pU(m)2^{p_U(m)}. For n=Eside(x)≥274n = E_{\mathrm{side}}(x) \ge2^{74}, the first term is at most n/4n/4, the second at most 64n5/8≤n/464n^{5/8} \le n/4, and the third at most n1/4≤n/4n^{1/4} \le n/4. Hence the real computation enters a sink by time n−1n-1. No transition enters a sentinel, and the remaining steps are uniquely supplied by the appropriate stay-sink.

The null branch contributes one accepting path for every n≥5n \ge5. On a coded side, real accepting branches are in bijection with accepting paths of Ulog⁡U_{\log}; off-code, the parser enters the rejecting sink. This proves the branch-count formula and all remaining assertions.

Counting Paths with Wang Tile Tableaux

Each step of the size-encoded machine is represented by one column of Wang tiles. The local rules record the unique head and its labelled transition, yielding a bijection between accepting branches and tableaux with prescribed boundaries. A separate count of successor columns under arbitrary boundary data provides the perimeter estimate needed in the geometric construction.

Let MM be a finite one-tape machine with state set QstQ_{\mathrm{st}}, tape alphabet Γtp\Gamma_{\mathrm{tp}}, accepting state qaccq_{\mathrm{acc}}, sentinel #s\#_{\mathrm{s}}, and labelled-arrow set Δarr\Delta_{\mathrm{arr}}. Put

Σcell={plain⁡(a):a∈Γtp}⊔{hd⁡(q,a):q∈Qst, a∈Γtp},scell=∣Γtp∣(1+∣Qst∣).\Sigma_{\mathrm{cell}} = \{\operatorname{plain}(a) : a \in\Gamma_{\mathrm{tp}}\} \sqcup\{\operatorname{hd}(q,a) : q \in Q_{\mathrm{st}},\ a \in\Gamma_{\mathrm{tp}}\}, \qquad s_{\mathrm{cell}} = |\Gamma_{\mathrm{tp}}|(1 + |Q_{\mathrm{st}}|).

Theorem 4.1 (Wang tableau for counting computation paths). For every fixed one-head Turing machine MM, there exists a finite Wang system WtabW_{\mathrm{tab}} with the following properties. For any legal initial configuration of height HH and any time horizon TT, accepting labelled-arrow branches of length TT correspond bijectively to WtabW_{\mathrm{tab}}-tilings of a TT-by-HH rectangle with prescribed initial, accepting, and sentinel boundary data. Distinct labelled arrows yield distinct tableaux.

Furthermore, writing scells_{\mathrm{cell}} for the number of possible tape-cell symbols and darrd_{\mathrm{arr}} for the number of labelled arrows, a prescribed east-boundary colour word of height nn has at most Kcol=4scell4(darr+1)4K_{\mathrm{col}} = 4s_{\mathrm{cell}}^{4}(d_{\mathrm{arr}}+1)^{4} vertically matching successor columns. The number of open nn-square tableaux therefore satisfies

atab(n)≤Rtabn,Rtab=4scell7(darr+1)4.a_{\mathrm{tab}}(n) \le R_{\mathrm{tab}}^{n}, \qquad R_{\mathrm{tab}} = 4s_{\mathrm{cell}}^{7}(d_{\mathrm{arr}}+1)^{4}.

Proof. For an old radius-one word X=(x−,x0,x+)X = (x_{-}, x_{0}, x_{+}), define its local update under an applicable arrow α=(q,a,q′,b,D)\alpha= (q,a,q',b,D) when x0=hd⁡(q,a)x_{0} = \operatorname{hd}(q,a), the two neighbours are tape cells, and a left or right movement does not enter a sentinel. The updated triple is

Θα(X)={(hd⁡(q′,ℓ),plain⁡(b),plain⁡(r)),D=L,(plain⁡(ℓ),hd⁡(q′,b),plain⁡(r)),D=S,(plain⁡(ℓ),plain⁡(b),hd⁡(q′,r)),D=R,\Theta_{\alpha}(X) = \begin{cases} (\operatorname{hd}(q',\ell),\operatorname{plain}(b),\operatorname{plain}(r)), & D = L,\\ (\operatorname{plain}(\ell),\operatorname{hd}(q',b),\operatorname{plain}(r)), & D = S,\\ (\operatorname{plain}(\ell),\operatorname{plain}(b),\operatorname{hd}(q',r)), & D = R, \end{cases}

where x−=plain⁡(ℓ)x_{-} = \operatorname{plain}(\ell) and x+=plain⁡(r)x_{+} = \operatorname{plain}(r). For a window whose head is immediately south or north of its centre, let ρα\rho_{\alpha} and λα\lambda_{\alpha} perform the corresponding incoming-head update at the centre.

Horizontal colours are symbols hcol⁡(X)\operatorname{hcol}(X) for X∈Σcell3X \in\Sigma_{\mathrm{cell}}^{3}. A candidate tile carries two order-bit chains, one for the old word and one for the new word. Write their south/north values as (oS,oN)(o_{\mathrm{S}},o_{\mathrm{N}}) and (nS,nN)(n_{\mathrm{S}},n_{\mathrm{N}}), both in {0,1}2\{0,1\}^{2}. For the old chain we require oN=oSo_{\mathrm{N}}=o_{\mathrm{S}} when the old centre is not a head and (oS,oN)=(0,1)(o_{\mathrm{S}},o_{\mathrm{N}})=(0,1) when it is a head; the new chain satisfies the analogous rule with the new centre. Thus each chain is nondecreasing and can jump only once, at its unique head. Vertical colours have the form vcol⁡(Pold,Pnew,o,n,μ)\operatorname{vcol}(P_{\mathrm{old}},P_{\mathrm{new}},o,n,\mu), where both PP's are pairs of cell symbols, o,n∈{0,1}o,n \in\{0,1\} are the old- and new-chain values on that horizontal boundary, and μ∈Δarr⊔{⊥}\mu\in\Delta_{\mathrm{arr}} \sqcup\{\bot\}. The south colour stores (oS,nS)(o_{\mathrm{S}},n_{\mathrm{S}}), and the north colour stores (oN,nN)(o_{\mathrm{N}},n_{\mathrm{N}}).

A candidate tile contains old and new triples X,YX,Y, these four order bits, and south and north tokens. It is admitted in exactly one of four cases. H. The old centre is a head. The south token is ⊥\perp, the north token is an applicable arrow α\alpha, and Y=Θα(X)Y = \Theta_{\alpha}(X).

A. The old south neighbour is the head. The south token is α\alpha, the north token is ⊥\perp, and the new centre is ρα(x0)\rho_{\alpha}(x_0).

B. The old north neighbour is the head. Both tokens are ⊥\perp, and the new centre equals λα(x0)\lambda_{\alpha}(x_0) for at least one arrow α\alpha having the source displayed by that head. This is an existence condition on the tile datum: if several labelled arrows witness the same resulting datum (X,Y,oS,oN,nS,nN)(X, Y, o_S, o_N, n_S, n_N), they do not create duplicate tile types in Case B.

Q. The old triple has no head. Both tokens are ⊥\perp, and the new centre equals the old centre.

Both triples are required to contain at most one head. The east and west colours are hcol⁡(X)\operatorname{hcol}(X) and hcol⁡(Y)\operatorname{hcol}(Y). The south vertical colour stores the two southern old and new symbols, the lower order bits, and the south token; the north colour stores the two northern symbols, the upper bits, and the north token. The inventory is finite and has the asserted cardinality. For the conditioned tableau used in the bijection, choose the south sentinel colour with both reconstructed symbol pairs equal to sentinels, both order-chain values equal to zero, and empty token; choose the north sentinel colour analogously with both order-chain values equal to one and empty token.

Vertical matching overlaps consecutive symbol pairs and identifies the corresponding boundary bits. Hence a matching column reconstructs unique extended old and new words on indices −1,…,H-1,\ldots,H, together with one old order chain and one new order chain. Each chain is constant except for a possible 0-to-1 jump at a head centre, so it certifies at most one head. When its prescribed south boundary value is zero and north boundary value is one, it certifies exactly one head. Sentinel vertical colours additionally force the two bottom and two top symbols to be plain(#s), so every certified head lies strictly between them.

At the unique old head, Case H chooses one arrow and places its label on the north edge. Vertical matching passes that token to the Case A tile. The overlap with Y=Θα(X)Y = \Theta_{\alpha}(X) simultaneously fixes the Case B centre for the same arrow. Every window at distance at least two is Case Q and preserves its centre. Thus the old word and the one arrow determine the entire visible new word. This proves that the neighbouring windows make no independent choice. Because the token is the labelled arrow itself, two same-effect arrows give different vertical colours.

Time runs from east to west. Fixing the east boundary to the radius-one windows of Cfg⁡0\operatorname{Cfg}_0 determines the first old word. Horizontal matching identifies each column’s new word with the next column’s old word. The sentinel colours make every word a legal configuration, and the accepting west-colour set requires the final unique head to have state qaccq_{\mathrm{acc}}. Conversely, a branch determines all triples, bits, and tokens and hence one tiling. These constructions are inverse.

For the open-column bound, fix its old-word triples. A column is encoded injectively by the two south-boundary order bits (one for each chain), the four new endpoint and ghost symbols, and four token slots containing the exterior tokens and the possible visible-head token. The old word together with its chosen south-boundary bit fixes the old order chain. Cases H–Q, the new south-boundary bit, and the recorded endpoint data recover the new word, its order chain, and every token. Therefore the number of columns is at most 2 scell4(darr+1)4=Kcol2\,s_{\mathrm{cell}}^4(d_{\mathrm{arr}}+1)^4 = K_{\mathrm{col}}. The east boundary of an open nn-square has at most (scell3)n(s_{\mathrm{cell}}^3)^n words. Scanning nn columns westward gives

atab(n)≤(scell3)nKcoln=Rtabn.a_{\mathrm{tab}}(n) \leq(s_{\mathrm{cell}}^3)^n K_{\mathrm{col}}^n = R_{\mathrm{tab}}^n.

Lemma 4.2 records the complete boundary-data reconstruction behind this estimate. The identity condition in Case Q is essential for the perimeter bound: without equality of old and new centres, a zero-head column would have exponentially many successor words, and iteration would give an area-exponential rather than perimeter-exponential bound. Finally, Θα\Theta_\alpha is undefined for a move onto a sentinel, which proves sentinel consistency.

Lemma 4.2 (Reconstruction of open successor columns). Fix the east-colour word of a vertically matching column in the Wang tableau constructed above. Such a column is uniquely determined by at most two initial order bits, four new endpoint or ghost symbols, and four arrow-token slots. In particular, its number of possible completions is at most 4scell4(darr+1)4=Kcol4s_{\mathrm{cell}}^{4}(d_{\mathrm{arr}}+1)^{4}=K_{\mathrm{col}}, independently of the column height.

Proof. The east colours determine all old radius-one windows. Their overlaps fix the old symbols throughout the column and the old endpoint data that they expose. Each vertically matched order-bit chain is nondecreasing, and its only permitted change is the transition from 0 to 1 at a head centre. Hence the old chain is fixed by its south bit and its old symbols. The new chain is similarly fixed once its south bit and the new symbols have been recovered.

The reconstruction of the new centres is local except at the old head, whose uniqueness follows from the old order chain. All possible arrangements are covered by the following cases. If an old head is strictly inside the visible column, Case H fixes its outgoing labelled arrow by the recorded head token; the neighbouring Case A and Case B rules implement the unique resulting update, while Case Q leaves all more distant centres unchanged. If a head touches the first or last visible radius-one window, its possible influence is confined to the boundary row and is recorded in the endpoint or ghost symbols and exterior token slots. If no old head is visible, Case Q fixes every centre whose old window is free of a head; only those bounded boundary windows that may involve an exterior head require the recorded boundary symbols. In every case, there is no independent choice at each additional interior row.

The overlap constraints then recover the new radius-one windows, the vertical colour data, and the order chains. The arrow token at a visible head records the actual labelled transition, so distinct same-effect arrows are counted separately. Conversely, in Case B, different arrow witnesses giving an identical local tile datum are identified as a single tile type. Thus two completing columns with the same prescribed east word and the same bounded boundary data coincide tile by tile. There are at most 222^{2} choices for the two initial order bits, scell4s_{\mathrm{cell}}^{4} choices for the four endpoint and ghost symbols, and (darr+1)4(d_{\mathrm{arr}}+1)^{4} choices for the token slots, proving the bound.

Counting Open-Square Wang Tilings

The tableau correspondence in the preceding section uses prescribed boundary data, while the target counting problem has open boundaries. A side-activity amplifier assigns a dominant multiplicity to the intended boundary class. Coupling it to a ripple counter and an edge scanner recovers the initial configuration from the side length, and the same construction supplies a uniform bound for all remaining boundary classes. The resulting perimeter estimate for arbitrary rectangles will be used in the geometric compiler.

Theorem 5.1 (Boundary amplification). For every integer Q≥1Q \ge1, there is a fixed Wang system with four side-activity tracks such that, on an open nn-square for n≥2n \ge2, the all-active boundary class has exactly Q4n−4Q^{4n-4} tilings and each proper side-activity class has at most Q3n−2Q^{3n-2} tilings. A private-colour dummy tile can be adjoined, contributing exactly one additional tiling.

Proof. Choose pairwise distinct atomic labels

gW,gE,gS,gN, aS,aN, gWc,gEc,gSv,gNv,aW,aEg_W, g_E, g_S, g_N,\ a_S, a_N,\ g_{Wc}, g_{Ec}, g_{Sv}, g_{Nv}, a_W, a_E

and dqWd^{W}_{q}, dqEd^{E}_{q}, dqSd^{S}_{q}, dqNd^{N}_{q} for 1≤q≤Q1 \le q \le Q. Horizontal colours are distinct symbols H(α,β,γ,δ)H(\alpha,\beta,\gamma,\delta); vertical colours are distinct symbols V(α,β,γ,δ)V(\alpha,\beta,\gamma,\delta).

A tile carries booleans W,E,S,NW,E,S,N and indices qW,qE,qS,qNq_W,q_E,q_S,q_N. Adjacent active sides on the same tile must use one common qq. Its colours are

Wcol=H(wW,gE,sc,nc),Ecol=H(gW,eE,sc,nc),W_{\mathrm{col}} = H(w_W,g_E,s_c,n_c), \qquad E_{\mathrm{col}} = H(g_W,e_E,s_c,n_c),
Scol=V(wc,ec,sS,gNv),Ncol=V(wc,ec,gSv,nN).S_{\mathrm{col}} = V(w_c,e_c,s_S,g_{N_v}), \qquad N_{\mathrm{col}} = V(w_c,e_c,g_{S_v},n_N).

where

wW=dqWW if W,wW=gW otherwise,wc=aW if W,wc=gWc otherwise,eE=dqEE if E,eE=gE otherwise,ec=aE if E,ec=gEc otherwise,sS=dqSS if S,sS=gSv otherwise,sc=aS if S,sc=gS otherwise,nN=dqNN if N,nN=gNv otherwise,nc=aN if N,nc=gN otherwise.\begin{aligned} w_W &= d^{W}_{q_W}\text{ if }W, & w_W &= g_W\text{ otherwise}, & w_c &= a_W\text{ if }W, & w_c &= g_{W_c}\text{ otherwise},\\ e_E &= d^{E}_{q_E}\text{ if }E, & e_E &= g_E\text{ otherwise}, & e_c &= a_E\text{ if }E, & e_c &= g_{E_c}\text{ otherwise},\\ s_S &= d^{S}_{q_S}\text{ if }S, & s_S &= g_{S_v}\text{ otherwise}, & s_c &= a_S\text{ if }S, & s_c &= g_S\text{ otherwise},\\ n_N &= d^{N}_{q_N}\text{ if }N, & n_N &= g_{N_v}\text{ otherwise}, & n_c &= a_N\text{ if }N, & n_c &= g_N\text{ otherwise}. \end{aligned}

Inactive indices do not occur in any colour and are normalized to 1.

No east colour contains dqWWd^{W}_{q_W} in its first coordinate. Hence a WW-active tile can occur only on the geometric west side. The three symmetric assertions follow for E,S,NE,S,N. Along the west side, the north and south colours carry either aWa_W or gWcg_{W_c}; since these differ, activity is constant down the whole side. The other three chain coordinates give the same all-or-none conclusion.

For n≥2n \ge2, let S⊆{W,E,S,N}S \subseteq\{W,E,S,N\} be the active-side set and write its indicator bits as w,e,s,tw,e,s,t. The number of distinct active sites is Sites⁡(n,S)=wn+en+s(n−w−e)+t(n−w−e)\operatorname{Sites}(n,S)=wn+en+s(n-w-e)+t(n-w-e). According to the active sides, this takes one of the six values 00, nn, 2n−12n-1, 2n2n, 3n−23n-2, and 4n−44n-4. A choice of one qq at each such site determines a unique tiling. Horizontal matching follows because an internal left tile is not EE-active, an internal right tile is not WW-active, and the north and south chain coordinates agree along their rows. Vertical matching is symmetric. Conversely, dead colours expose every qq. Hence the side class has exactly QSites⁡(n,S)Q^{\operatorname{Sites}(n,S)} tilings. Summation over the sixteen subsets gives the displayed formula.

When n=1n=1, the single tile lies on all four sides. The activity inventories contribute 11, 4Q4Q, 4Q4Q, 2Q22Q^2, 4Q4Q, and QQ for zero sides, one side, adjacent pairs, opposite pairs, triples, and all four sides, respectively. Their sum is 1+13Q+2Q21+13Q+2Q^2.

The west-only set contains the inactive tile and the QQ purely west-active tiles. It has one constant inactive tiling and QnQ^n active-west tilings. Finally, a private-colour tile cannot meet an amplifier tile. Connectedness of the square grid therefore makes its mode constant and adds exactly one tiling.

A raw product of four independent wires would give Q4nQ^{4n} full frames. The shared-qq rule removes one duplicate index at each corner and gives the required Q4n−4Q^{4n-4}.

We use a four-tile ripple counter. Its tile indexed by input bit bb and carry cc has west colour BbB_b, south colour CcC_c, east colour Bb⊕cB_{b\oplus c}, and north colour CbcC_{bc}. West and south boundary words determine a unique tiling. With west bits zero and south carries one, column xx represents xx, the east boundary represents the side length, and the top carries are zero.

Theorem 5.2 (Fixed open-square Wang counter). There are a fixed unweighted Wang tile set WprodW_{\mathrm{prod}} and positive constants R0=4Rtab5772R_0=4R_{\mathrm{tab}}577^2 and Q=2R0+1Q=2R_0+1 such that, for every n≥5n\ge5, the total number aprod(n)a_{\mathrm{prod}}(n) of open WprodW_{\mathrm{prod}}-tilings of the nn-square has the decomposition

aprod(n)=Q4n−4Acc∗(n)+Junk⁡(n),a_{\mathrm{prod}}(n)=Q^{4n-4}A_{\mathrm{cc}*}(n)+\operatorname{Junk}(n),

where the residual count satisfies

0≤Junk⁡(n)≤1+15R0nQ3n−2.0\le\operatorname{Junk}(n)\le1+15R_0^nQ^{3n-2}.

Proof. Apply Theorem 4.1 to M⋆M_\star. Its tableau track contributes at most RtabnR_{\mathrm{tab}}^n open nn-square patterns. The ripple track contributes 4n4^n.

We define the scanner in full. Let

Buf={plain⁡(#s),plain⁡(zerob),plain⁡(oneb),plain⁡(workb),hd⁡(qstart,zerob),hd⁡(qstart,oneb)}.\mathrm{Buf}=\{\operatorname{plain}(\#_{\mathrm{s}}),\operatorname{plain}(\mathrm{zero}_{\mathrm{b}}),\operatorname{plain}(\mathrm{one}_{\mathrm{b}}),\operatorname{plain}(\mathrm{work}_{\mathrm{b}}), \operatorname{hd}(q_{\mathrm{start}},\mathrm{zero}_{\mathrm{b}}),\operatorname{hd}(q_{\mathrm{start}},\mathrm{one}_{\mathrm{b}})\}.

Its vertical colours are

Sscan={bot,mid,top,cap}×Buf2×{lh0,lh1}×{modeHigh,modeBin},S_{\mathrm{scan}}=\{\mathrm{bot},\mathrm{mid},\mathrm{top},\mathrm{cap}\}\times\mathrm{Buf}^{2}\times\{\mathrm{lh0},\mathrm{lh1}\}\times\{\mathrm{modeHigh},\mathrm{modeBin}\},

so ∣Sscan∣=576\lvert S_{\mathrm{scan}}\rvert=576. There is one idle tile with private colour scanIdle on every side. For every s,t∈Sscans,t\in S_{\mathrm{scan}}, there is a marked tile with west colour scanIdle, east colour scanDead, south colour ss, and north colour tt. No west colour equals scanDead. Thus marked tiles occur only in the east column. Vertical colours prevent a marked tile from meeting an idle tile vertically, so either the scanner is entirely idle or its east column is entirely marked. Its open count satisfies 1+576n+1≤5772n1+576^{n+1}\leq577^{2n}. The uncoupled counter, tableau, and scanner product therefore has at most R0nR_0^n open tilings.

For b∈{0,1}b\in\{0,1\} and a mode mm, define

NewMid⁡(1,m)=plain⁡(oneb),NewMid⁡(0,modeHigh)=plain⁡(workb),NewMid⁡(0,modeBin)=plain⁡(zerob),ModeOut⁡(0,modeHigh)=modeHigh,ModeOut⁡(1,modeHigh)=modeBin,ModeOut⁡(b,modeBin)=modeBin.\begin{aligned} \operatorname{NewMid}(1,m)&=\operatorname{plain}(\mathrm{one}_{\mathrm{b}}),& \operatorname{NewMid}(0,\mathrm{modeHigh})&=\operatorname{plain}(\mathrm{work}_{\mathrm{b}}),\\ \operatorname{NewMid}(0,\mathrm{modeBin})&=\operatorname{plain}(\mathrm{zero}_{\mathrm{b}}),& \operatorname{ModeOut}(0,\mathrm{modeHigh})&=\mathrm{modeHigh},\\ \operatorname{ModeOut}(1,\mathrm{modeHigh})&=\mathrm{modeBin},& \operatorname{ModeOut}(b,\mathrm{modeBin})&=\mathrm{modeBin}. \end{aligned}

Write s=(ϕ,u,v,λ,m)s=(\phi,u,v,\lambda,m) and t=(ϕ′,u′,v′,λ′,m′)t=(\phi',u',v',\lambda',m'). The relation LegalScan⁡(s,t,b)\operatorname{LegalScan}(s,t,b) first requires u′=vu'=v, and then exactly one of the following clauses.

Bot.

ϕ=bot,λ=lh0,u=v=plain⁡(#s),ϕ′=mid,λ′=lh0,m=modeBin,\phi=\mathrm{bot},\quad\lambda=\mathrm{lh0},\quad u=v=\operatorname{plain}(\#_{\mathrm{s}}),\quad\phi'=\mathrm{mid},\quad\lambda'=\mathrm{lh0},\quad m=\mathrm{modeBin},
v′=hd⁡(qstart,zerob) if b=0,v′=hd⁡(qstart,oneb) if b=1.v'=\operatorname{hd}(q_{\mathrm{start}},\mathrm{zero}_{\mathrm{b}})\ \text{if }b=0,\qquad v'=\operatorname{hd}(q_{\mathrm{start}},\mathrm{one}_{\mathrm{b}})\ \text{if }b=1.

Mid.

ϕ=ϕ′=mid,λ=λ′=lh0,v′=NewMid⁡(b,m′),m=ModeOut⁡(b,m′).\phi=\phi'=\mathrm{mid},\quad\lambda=\lambda'=\mathrm{lh0},\quad v'=\operatorname{NewMid}(b,m'),\quad m=\operatorname{ModeOut}(b,m').

PreTop.

ϕ=mid,ϕ′=top,λ=lh0,λ′=lh1,\phi=\mathrm{mid},\quad\phi'=\mathrm{top},\quad\lambda=\mathrm{lh0},\quad\lambda'=\mathrm{lh1},
v′=plain⁡(#s),m=m′=modeHigh,b=0.v'=\operatorname{plain}(\#_{\mathrm{s}}),\quad m=m'=\mathrm{modeHigh},\quad b=0.

Top.

ϕ=top,ϕ′=cap,λ=lh1,λ′=lh0,\phi=\mathrm{top},\quad\phi'=\mathrm{cap},\quad\lambda=\mathrm{lh1},\quad\lambda'=\mathrm{lh0},
m=m′=modeHigh,v=v′=u′=plain⁡(#s).m=m'=\mathrm{modeHigh},\quad v=v'=u'=\operatorname{plain}(\#_{\mathrm{s}}).

No clause has south phase cap, and no clause has north phase bot. Define Emit⁡(s,t,b)=(u,v,v′)\operatorname{Emit}(s,t,b)=(u,v,v'). The lookahead and mode are scanner-colour coordinates, not amplifier activity bits.

Take the product of the amplifier at QQ, the ripple counter, the tableau, and the scanner. Retain a product tile only when the following cell-local couplings hold.

  1. A west-active amplifier cell has ripple west colour B0B_0, an accepting tableau west colour, and an idle scanner.

  1. An east-active cell has a marked scanner tile, reads its ripple east bit bb, satisfies LegalScan⁡(s,t,b)\operatorname{LegalScan}(s,t,b), and has tableau east colour hcol⁡(Emit⁡(s,t,b))\operatorname{hcol}(\operatorname{Emit}(s,t,b)).

  1. A south-active cell has ripple south colour C1C_1 and tableau south sentinel colour. At the southeast corner its scanner south colour is (bot,plain⁡(#s),plain⁡(#s),lh0,modeBin)(\mathrm{bot},\operatorname{plain}(\#_{\mathrm{s}}),\operatorname{plain}(\#_{\mathrm{s}}),\mathrm{lh0},\mathrm{modeBin}).

  1. A north-active cell has ripple north colour C0_0 and tableau north sentinel colour. At the northeast corner its scanner south colour has phase top, centre plain(#s), lookahead lh1, and mode modeHigh.

  1. Every non-east-active cell uses the idle scanner.

Adjoin a single all-private-colour dummy tile. Figure 1 summarizes the boundary data in the full-frame class and the role of the unique marked scanner column.

Figure 1. Full-frame boundary coupling and east-edge scanning at the Wang level. In panel (a), the west, south, and north sides carry the fixed ripple/tableau data B0B_0, HaccH_{\mathrm{acc}}, C1C_1, S#S_{\#}, and C0C_0, N#N_{\#}, respectively. The dots mark the shared-corner amplifier qq-sites, and the shaded east column receives the ripple bits by=bit⁡n(y)b_y = \operatorname{bit}_n(y). Time in the one-head tableau runs from east to west. Panel (b) isolates one scanner step: adjacent scanner states IyI_y, Iy+1I_{y+1}, together with byb_y, satisfy LegalScan and determine Emit(Iy,Iy+1,by)(I_y,I_{y+1},b_y), which is exported as the tableau east colour. Over the full marked column, these emitted colours are exactly the radius-one windows of Cfg⁡n⋆\operatorname{Cfg}^{\star}_n.

In a full frame, the amplifier forces all four active sides. The ripple boundary conditions give the unique incrementing counter and put the bits of nn on the east edge. The scanner diode confines marked tiles to that edge. The bottom constraint forces Bot at row zero. The top constraint forces Top at row n−1n-1; since no legal tile has south phase cap, no earlier Top is possible. Row n−2n-2 is therefore PreTop. Its required bit is zero because the omitted bit n−2n-2 vanishes for n≥5n \ge5. All intervening rows are Mid.

For j≥0j \ge0, the jj-th binary digit of nn is bit⁡n(j)=⌊n/2j⌋ mod 2\operatorname{bit}_n(j) = \lfloor n/2^j \rfloor\bmod2, with the least significant digit at j=0j=0. The mode is now unique by downward recursion. At height yy,

m(y)=modeHigh⟺bit⁡n(j)=0 for every y≤j≤n−3.m(y) = \text{modeHigh} \Longleftrightarrow\operatorname{bit}_n(j) = 0 \text{ for every } y \le j \le n-3.

This follows directly from ModeOut, starting with the high mode at the top. Therefore a zero above the leading one is emitted as workb, a lower zero as zerob, and a one as oneb. Bot installs the start head at index 1, while PreTop and Top install the two sentinels. PreTop explicitly checks the omitted bit n−2n-2; the ripple word already supplies the second omitted bit n−1=0n-1=0, so Top does not read it. The overlap equation u′=vu' = v gives

Emit⁡y=(Cfg⁡n∗(y−1),Cfg⁡n∗(y),Cfg⁡n∗(y+1)).\operatorname{Emit}_y = \left(\operatorname{Cfg}_n^*(y-1), \operatorname{Cfg}_n^*(y), \operatorname{Cfg}_n^*(y+1)\right).

The tableau bijection of Theorem 4.1 then identifies its tilings with accepting branches of M⋆M_\star. Independently, the amplifier supplies one qq per one of its 4n−44n-4 boundary sites. This proves the full-frame bijection.

For a proper side set, Theorem 5.1 gives at most Q3n−2Q^{3n-2} amplifier tilings. Dropping every coupling permits at most R0nR_0^n computational-track tilings, including every open scanner, counter, and tableau defect. Thus each proper class has at most R0nQ3n−2R_0^n Q^{3n-2} tilings. The private dummy colour cannot meet a product colour on the connected square grid, so it contributes one isolated tiling. Summing the fifteen proper classes proves the junk estimate.

Theorem 5.3 (Perimeter bound on arbitrary rectangles). Let arect(w,h)a_{\mathrm{rect}}(w,h) count open WprodW_{\mathrm{prod}}-tilings of Rectw,h\mathrm{Rect}_{w,h}. There is a fixed integer Rrect≥2R_{\mathrm{rect}} \ge2 such that

arect(w,h)≤Rrectw+h(w,h≥1).a_{\mathrm{rect}}(w,h) \le R_{\mathrm{rect}}^{w+h} \qquad(w,h \ge1).

One may take

Rrect=1+16Q2⋅2Rtab(∣Sscan∣+1)2.R_{\mathrm{rect}} = 1 + 16Q^2 \cdot2R_{\mathrm{tab}}(|S_{\mathrm{scan}}|+1)^2.

The bound also applies when w=1w=1 or h=1h=1.

Proof. The dummy colour again gives one isolated constant tiling. Dropping all couplings bounds every other tiling by the product of four independent track counts.

The ripple track is determined by hh west bits and ww south carries, so it has exactly 2w+h2^{w+h} tilings. For the tableau track, there are (scell3)h(s_{\mathrm{cell}}^3)^h east words and at most KcolwK_{\mathrm{col}}^w westward column extensions. Since Rtab=scell3KcolR_{\mathrm{tab}} = s_{\mathrm{cell}}^3 K_{\mathrm{col}},

atab(w,h)≤Rtabw+h.a_{\mathrm{tab}}(w,h) \le R_{\mathrm{tab}}^{w+h}.

The scanner is either idle or has one marked east column, giving ascan(w,h)=1+576h+1≤5772(w+h)a_{\mathrm{scan}}(w,h)=1+576^{h+1}\leq577^{2(w+h)}. For the amplifier, dead colours and chain colours still force an all-or-none subset of the four geometric sides. Charge one independent qq for every active side cell before imposing shared-corner equalities. A chosen side set therefore has at most Q2w+2hQ^{2w+2h} tilings, and summing sixteen sets gives 16Q2(w+h)16Q^{2(w+h)}. This charging remains valid when opposite sides occupy the same physical row or column. In particular, for w=1w=1, west and east indices may remain independent; for w=h=1w=h=1, the exact inventory 1+13Q+2Q21+13Q+2Q^2 is below 16Q416Q^4.

Multiplying the four bounds and absorbing the factor 16 into the exponent yields

arect(w,h)≤1+(16Q2⋅2Rtab⋅5772)w+h≤Rrectw+h.a_{\mathrm{rect}}(w,h)\leq1+\left(16Q^2\cdot2R_{\mathrm{tab}}\cdot577^2\right)^{w+h}\leq R_{\mathrm{rect}}^{w+h}.

Rectangular Decompositions of the Macrogrid

Closed interfaces in the geometric realization may divide the macrogrid into several components. The analysis requires two combinatorial facts: every nontrivial rectangular dissection has a sufficiently long seam and a controlled number of possible seam configurations, and the saturation condition enforced by the carrier interfaces makes each connected component a filled rectangle. Together, these facts classify the resulting tilings and control the multiplicity of nontrivial decompositions.

Theorem 6.1 (Rectangular-dissection bound). Let a rectangular dissection of Square⁡n\operatorname{Square}_n be a partition into at least two nonempty discrete rectangles. A seam pair is a pair of adjacent cells in different blocks, and its seam segment is their common unit side. Form the seam graph whose vertices are

seam segments and whose edges join segments sharing an endpoint. If II is the number of seam pairs, then:

  1. I≥nI \ge n;

  2. every connected component of the seam graph contains at least nn segments;

  3. for fixed I≥1I \ge1, the number of rectangular dissections with II seam pairs is at most 256I256^I.

Proof. Every internal side of a rectangular block consists of seam segments, and every seam segment lies on an internal side of both adjacent blocks.

Let f(x)f(x) be the number of blocks meeting column xx, and g(y)g(y) the number meeting row yy. Each column is partitioned into f(x)f(x) intervals, while each row is partitioned into g(y)g(y) intervals. Hence

I=∑x=0n−1(f(x)−1)+∑y=0n−1(g(y)−1).I = \sum_{x=0}^{n-1}(f(x)-1) + \sum_{y=0}^{n-1}(g(y)-1).

If every f(x)≥2f(x) \ge2, the first sum is at least nn. Otherwise some block contains a whole column. Such a rectangular block has height nn; unless it is the entire square, one of its vertical sides is internal and contributes nn seams. The entire-square case is excluded by nontriviality. This proves I≥nI \ge n.

Consider the internal sides of one block in cyclic order. Adjacent internal sides share a corner and therefore belong to the same seam component. If its internal sides do not all lie in one component, then it has either one internal side or two opposite internal sides. In either case every such side has length nn. Thus each block satisfies the dichotomy:

every internal side has length nn, or all its internal sides lie in one seam component.

Suppose a seam component CC has fewer than nn segments. Any block incident with CC must satisfy the second alternative and hence has all internal sides in CC. A neighbouring block is incident along one of these sides and has the same property. The adjacency graph of blocks is connected, since a row-then-column cell path between two blocks crosses a sequence of neighbouring blocks. Therefore every block is incident with CC, and every seam belongs to CC. This would give ∣C∣=I≥n|C| = I \ge n, a contradiction.

A dissection is determined by its seam set: delete the seam adjacencies from the cell grid, and the connected components are precisely its rectangular blocks. It remains to count possible seam sets.

Let CmC_m be the connected sets of mm unit grid segments with endpoints in {0,…,n}2\{0,\ldots,n\}^2. Double every edge of such a set. The resulting connected even-degree multigraph has an Euler tour of length 2m2m. An initial endpoint and the sequence of four possible unit steps determine the segment set, giving ∣Cm∣≤(n+1)242m=(n+1)216m|C_m| \le(n+1)^2 4^{2m} = (n+1)^2 16^m. The elementary inequality (n+1)2≤4n(n+1)^2 \le4^n holds for all n≥1n \ge1.

An admissible seam set with II segments is a disjoint union of rr connected components of sizes m1,…,mrm_1,\ldots,m_r, where each mj≥nm_j \ge n and ∑mj=I\sum m_j = I. Thus r≤I/nr \le I/n. For each ordered size tuple, ∏j∣Cmj∣≤(n+1)2r16I≤4I16I\prod_j |C_{m_j}| \le(n+1)^{2r}16^I \le4^I16^I. The number of ordered positive compositions, allowing every 1≤r≤I1 \le r \le I, is at most 4I4^I: for fixed rr, partial sums give at most 2I2^I choices, and there are at most I≤2II \le2^I choices of rr. Consequently, there are at most 4I⋅4I⋅16I=28I=256I4^I \cdot4^I \cdot16^I = 2^{8I} = 256^I admissible seam sets, and hence at most this many dissections.

We next isolate the local graph principle used by the geometric compiler. Fix Pmac≥1P_{\mathrm{mac}} \ge1 and ccol≥0c_{\mathrm{col}} \ge0, and write Lmac(n)=Pmacn+2ccolL_{\mathrm{mac}}(n) = P_{\mathrm{mac}}n + 2c_{\mathrm{col}}. Define

x0=0,xn=Lmac(n),xi=ccol+Pmaci(1≤i<n).x_0 = 0,\qquad x_n = L_{\mathrm{mac}}(n),\qquad x_i = c_{\mathrm{col}} + P_{\mathrm{mac}}i \quad(1 \le i < n).

Let

Macp,q={xp,…,xp+1−1}×{xq,…,xq+1−1}.\mathrm{Mac}_{p,q}=\{x_p,\ldots,x_{p+1}-1\}\times\{x_q,\ldots,x_{q+1}-1\}.

For a tiling Π\Pi, open the macro-edge between two adjacent macrocells when one placement contains adjacent physical cells on its two sides. This gives a spanning subgraph Gmac(Π)G_{\mathrm{mac}}(\Pi) of the nn-square index grid.

A grid subgraph is saturated when, in every 2-by-2 index square, two consecutive present edges force all four edges.

Theorem 6.2 (Saturation and rectangular macroblocks). The following assertions hold.

  1. Every connected component of a saturated index graph is a filled combinatorial rectangle: all internal horizontal and vertical index adjacencies of the rectangle are present.

  1. The macrocells Macp,q\mathrm{Mac}_{p,q} are nonempty, pairwise disjoint, and partition SquareLmac(n)\mathrm{Square}_{L_{\mathrm{mac}}}(n).

  1. If every prototile is 4-connected, then the macrocells met by one placement lie in a single component of Gmac(Π)G_{\mathrm{mac}}(\Pi).

  1. If Gmac(Π)G_{\mathrm{mac}}(\Pi) is saturated, its components induce a partition of the physical square into nonempty discrete rectangles. If there is more than one component, this is a rectangular dissection. No closed macro-adjacency lies inside one component.

  1. Let dTd_T be the maximum ℓ∞\ell_\infty-diameter of a prototile. If saturation fails in a 2-by-2 macro-window QwinQ_{\mathrm{win}}, every placement meeting the window is contained in its ℓ∞\ell_\infty-neighbourhood QextQ_{\mathrm{ext}} of radius dTd_T. Those placements determine the four offending edge bits, and QextQ_{\mathrm{ext}} has width and height at most

2(Pmac+2ccol)+2dT.2(P_{\mathrm{mac}}+2c_{\mathrm{col}})+2d_T.

Proof. Let CC be a connected component of a saturated index graph. Choose a filled combinatorial rectangle

R={a,…,a′}×{b,…,b′}⊆CR=\{a,\ldots,a'\}\times\{b,\ldots,b'\}\subseteq C

of maximum cardinality. Suppose an edge of CC leaves its north side at (x0,b′)(x_0,b'). Let SS be the set of xx for which the vertical edge from (x,b′)(x,b') to (x,b′+1)(x,b'+1) is present. If x∈Sx\in S and x<a′x<a', the vertical edge at xx and the filled horizontal edge below it are consecutive sides of a 2-by-2 square. Saturation supplies the upper horizontal edge and the vertical edge at x+1x+1. The symmetric argument propagates left. Hence S={a,…,a′}S=\{a,\ldots,a'\}, and the full added row is filled. This contradicts maximality. Coordinate swaps and reflections treat the other three sides. Therefore R=CR=C.

The sequence x0,…,xnx_0,\ldots,x_n is strictly increasing. Its endpoint increments are Pmac+ccolP_{\mathrm{mac}}+c_{\mathrm{col}}, its interior increments are PmacP_{\mathrm{mac}}, and when n=1n=1 its sole increment is Pmac+2ccolP_{\mathrm{mac}}+2c_{\mathrm{col}}. The induced coordinate intervals therefore partition {0,…,Lmac(n)−1}\{0,\ldots,L_{\mathrm{mac}}(n)-1\}, proving the macrocell assertion.

Let a 4-connected placement meet two macrocells. A cell path inside the placement crosses between either the same macrocell or two adjacent macrocells. Every genuine crossing witnesses an open macro-edge. The visited index cells thus form a walk in Gmac(Π)G_{\mathrm{mac}}(\Pi), proving containment in one component.

Under saturation, each component is a filled index rectangle. The union of its consecutive coordinate intervals is {xa,…,xa′+1−1}×{xb,…,xb′+1−1}\{x_a,\ldots,x_{a'+1}-1\}\times\{x_b,\ldots,x_{b'+1}-1\}, a nonempty discrete rectangle. Components partition the index grid, so these unions partition the physical square. Filledness says every internal adjacency is open; conversely a closed adjacency separates components.

Finally, if a placement meets QwinQ_{\mathrm{win}}, every one of its cells lies within ℓ∞\ell_\infty-distance dTd_T of the meeting cell. It is therefore contained in QextQ_{\mathrm{ext}}. A macrocell side length is at most Pmac+2ccolP_{\mathrm{mac}}+2c_{\mathrm{col}}, so the two-by-two window has width and height at most twice that quantity; thickening adds 2dT2d_T. The placements meeting the window contain every possible witness for its four open bits, so they determine the saturation failure.

The Polyomino Construction

The fixed Wang system is realized geometrically by a family of connected polyominoes. Each carrier stores the Wang tile identity in an interior cavity and encodes its edge colours and opening data in boundary registers. The proof establishes unique macrogrid anchoring and an exact correspondence between tilings and rectangular Wang-tiled blocks. The dissection estimates then isolate the contribution of the single-block configuration.

Let W=WprodW = W_{\mathrm{prod}}, MW=∣W∣M_W = \lvert W\rvert, and for u∈Wu \in W write W(u),E(u),S(u),N(u)W(u), E(u), S(u), N(u) for its west, east, south, and north colours. Let ColH,ColV\mathrm{Col}_H,\mathrm{Col}_V be its horizontal and vertical colour sets, of cardinalities HcolH_{\mathrm{col}} and VcolV_{\mathrm{col}}. Fix bijections

ȷ:W→{0,…,MW−1},ιH:ColH→{0,…,Hcol−1},ιV:ColV→{0,…,Vcol−1}.\jmath: W \to\{0,\ldots,M_W-1\},\quad\iota_H: \mathrm{Col}_H \to\{0,\ldots,H_{\mathrm{col}}-1\},\quad\iota_V: \mathrm{Col}_V \to\{0,\ldots,V_{\mathrm{col}}-1\}.

Define

samp=1024Rrect3,s_{\mathrm{amp}} = 1024R_{\mathrm{rect}}^3,
Ks=4sampmax⁡(Hcol,Vcol),K_s = 4s_{\mathrm{amp}}\max(H_{\mathrm{col}},V_{\mathrm{col}}),
Ps=Ks+4MW+64,b⋆=Ps−8.P_s = K_s + 4M_W + 64,\qquad b_{\star} = P_s - 8.

For a,b∈{0,1}a,b \in\{0,1\}, a horizontal colour χ\chi, and 0≤ℓ<samp0 \le\ell< s_{\mathrm{amp}}, put

AH(a,b,χ,ℓ)=8+4(sampιH(χ)+ℓ)+2a+b,A_H(a,b,\chi,\ell) = 8 + 4(s_{\mathrm{amp}}\iota_H(\chi)+\ell)+2a+b,

and define AVA_V analogously using ιV\iota_V. Every code lies in {8,…,Ks+7}\{8,\ldots,K_s+7\}, strictly below b⋆b_{\star}, and the four arguments are recovered from it.

Let

Lplug={(0,1),(1,0),(1,1)},qu=(16+4ȷ(u),16),Cavu=qu+Lplug.L_{\mathrm{plug}} = \{(0,1),(1,0),(1,1)\},\qquad q_u = (16+4\jmath(u),16),\qquad\mathrm{Cav}_u = q_u+L_{\mathrm{plug}}.

For an opening vector η=(ηW,ηE,ηS,ηN)∈{0,1}4\eta=(\eta_W,\eta_E,\eta_S,\eta_N)\in\{0,1\}^4, let ℓD=0\ell_D=0 whenever ηD=0\eta_D=0. Starting with Bs={0,…,Ps−1}2B_s=\{0,\ldots,P_s-1\}^2, delete Cavu\mathrm{Cav}_u. On each open side also perform the following dent-and-bump operation:

sidedentbump
WW(0,AH(ηS,ηN,W(u),ℓW))(0,A_H(\eta_S,\eta_N,W(u),\ell_W))(−1,b⋆)(-1,b_{\star})
EE(Ps−1,b⋆)(P_s-1,b_{\star})(Ps,AH(ηS,ηN,E(u),ℓE))(P_s,A_H(\eta_S,\eta_N,E(u),\ell_E))
SS(AV(ηW,ηE,S(u),ℓS),0)(A_V(\eta_W,\eta_E,S(u),\ell_S),0)(b⋆,−1)(b_{\star},-1)
NN(b⋆,Ps−1)(b_{\star},P_s-1)(AV(ηW,ηE,N(u),ℓN),Ps)(A_V(\eta_W,\eta_E,N(u),\ell_N),P_s)

Table 1.

Denote the resulting support by Car⁡(η,u,ℓ)\operatorname{Car}(\eta,u,\ell), and let T⋆\mathcal{T}^{\star} consist of LplugL_{\mathrm{plug}} and every such carrier. Figure 2 shows the tile-specific cavity and the reciprocal interface registers.

Lemma 7.1 (Local geometric rigidity). Every carrier Car⁡(η,u,ℓ)\operatorname{Car}(\eta,u,\ell) satisfies the following two properties.

  1. In any relative row or column of the body square BsB_s, no three consecutive body cells are all absent from the carrier.

  2. Relative rows and columns 1 and 2, and each three-by-three corner of BsB_s, are intact.

Proof. The interior cavity is contained in a two-by-two box and removes at most two consecutive cells from any row or column. Every side dent removes a single boundary cell. On any fixed body row, boundary dents can occur only at the two extreme columns; on any fixed body column, they can occur only at the two extreme rows. The variable dent coordinates lie in {8,…,Ks+7}\{8,\ldots,K_s+7\}, the fixed coordinate is b⋆=Ps−8b_\star=P_s-8, and the cavity lies in the strip {16,…,4MW+13}×{16,17}\{16,\ldots,4M_W+13\}\times\{16,17\}. If a boundary dent shares a row or column with the cavity, at least fifteen occupied body cells separate them. Hence neither the cavity nor any combination of boundary dents creates three consecutive missing body cells. The same coordinate separations place every cavity and dent away from relative rows and columns 1, 2 and away from all three-by-three body corners.

For n≥1n\ge1, let Part⁡n\operatorname{Part}_n denote the set of rectangular partitions of the index square {0,…,n−1}2\{0,\ldots,n-1\}^2, including the one-block partition. For D∈Part⁡nD\in\operatorname{Part}_n, let I(D)I(D) be its number of seam adjacencies, and for a block B∈DB\in D let wB,hBw_B,h_B denote its width and height.

Theorem 7.2 (Geometric compilation and counting identity). The fixed translation-only family T⋆T^\star has the following properties.

  1. Every carrier is 4-connected, has area Ps2−3P_s^2-3, lies in {−1,…,Ps2}\{-1,\ldots,P_s^2\}, and the map (η,u,ℓ)↦Car⁡(η,u,ℓ)(\eta,u,\ell)\mapsto\operatorname{Car}(\eta,u,\ell) is injective on unlabelled supports. The plug is 4-connected of area 3.

  1. For every n≥1n\ge1, every T⋆T^\star-tiling of Square⁡Psn\operatorname{Square}_{P_s n} has exactly one carrier anchored at each (iPs,jPs)(iP_s,jP_s), 0≤i,j<n0\le i,j<n.

  1. Adjacent anchored carriers are disjoint exactly when their reciprocal opening bits agree and, whenever the common opening bit is one, the corresponding perpendicular opening bits, Wang colours, and amplifier labels also agree. Diagonal carriers are disjoint, and outer opening bits vanish.

  1. For every n≥1n\ge1, after the anchored carriers are placed, the residual set is the disjoint union of the n2n^2 translated cavities. Each cavity has one plug placement, and no additional carrier fits.

  1. For every n≥1n\ge1, tilings of Square⁡Psn\operatorname{Square}_{P_s n} are in bijection with a partition D∈Part⁡nD\in\operatorname{Part}_n, an open WW-tiling of every block, and one label in {0,…,samp−1}\{0,\ldots,s_{\mathrm{amp}}-1\} on every open macro-edge.

  1. Let En=2n(n−1)E_n=2n(n-1). Then

gT⋆(Psn)=∑D∈Part⁡nsampEn−I(D)∏B∈Darect(wB,hB).g_{T^\star}(P_s n)=\sum_{D\in\operatorname{Part}_n}s_{\mathrm{amp}}^{E_n-I(D)}\prod_{B\in D}a_{\mathrm{rect}}(w_B,h_B).

For n=1n=1 this equals arect(1,1)a_{\mathrm{rect}}(1,1). For n≥2n \ge2, the nontrivial-partition contribution J(n)J(n) satisfies

0≤J(n)sampEn≤434−n<1,0 \le\frac{J(n)}{s_{\mathrm{amp}}^{E_n}} \le\frac{4}{3}4^{-n} < 1,

and consequently

⌊gT⋆(Psn)sampEn⌋=arect(n,n).\left\lfloor\frac{g_{T^\star}(P_s^n)}{s_{\mathrm{amp}}^{E_n}} \right\rfloor= a_{\mathrm{rect}}(n,n).

Proof. The coding maps AH,AVA_H,A_V are injective because their residues modulo four recover the two perpendicular bits, while quotient and remainder by samps_{\mathrm{amp}} recover the colour and label. The cavity lies in the interior strip {16,…,4MW+13}×{16,17}\{16,\ldots,4M_W+13\}\times\{16,17\}, far from every edge feature. Each open side deletes one cell and adds one cell, so a carrier has area Ps2−3P_s^2-3.

First delete the entire two-by-two box containing the cavity from the inner rectangle {1,…,Ps−2}2\{1,\ldots,P_s-2\}^2; the remainder is 4-connected. Reinsert the southwest cell of that box, which is the unique cell of the box not removed by the L-shaped cavity. It is adjacent to the surrounding remainder and therefore preserves 4-connectivity. Every undeleted boundary cell attaches inward. Each bump attaches to an undeleted boundary cell because all variable code positions lie below b⋆b_\star. Hence every carrier is 4-connected.

The cell (0,0)(0,0) uniquely minimizes x+yx+y in every carrier. Equality up to translation therefore forces equal origins. The presence or absence of the four side features recovers η\eta, the interior cavity recovers uu, and on every open side the variable address—carried by the dent on the west and south sides and by the bump on the east and north sides—recovers its label. This proves injectivity. It also proves the identity test for equal-colour Wang tiles.

We establish anchoring by row-major induction, increasing jj first and, within a fixed macro-row jj, increasing ii. The repeated rigidity input is Lemma 7.1: an anchored carrier cannot expose three consecutive body cells in one row or column, and the first two body rows and columns and all three-by-three body corners are intact.

Let z=(iPs,jPs)z=(iP_s,jP_s) be the next macro-corner. A translate of LplugL_{\mathrm{plug}} covering zz has origin (iPs,jPs−1)(iP_s,jP_s-1), (iPs−1,jPs)(iP_s-1,jP_s), or (iPs−1,jPs−1)(iP_s-1,jP_s-1). At the outer boundary one of its cells leaves the square. Otherwise it overlaps the intact cell (1,Ps−1)(1,P_s-1) of the lower carrier, the intact cell (Ps−1,1)(P_s-1,1) of the left carrier, or an intact corner cell. Hence the placement covering zz is a carrier.

Write its origin as (a,b)(a,b). The intact body corners and containment in SquarePsn\mathrm{Square}_{P_s^n} imply 0≤a,b≤Psn−Ps0\le a,b\le P_sn-P_s. Because the carrier covers zz and its relative support is contained in {−1,…,Ps}2\{-1,\ldots,P_s\}^2, its origin satisfies

iPs−Ps≤a≤iPs+1,jPs−Ps≤b≤jPs+1.iP_s-P_s\le a\le iP_s+1,\qquad jP_s-P_s\le b\le jP_s+1.

If b≤jPs−2b\le jP_s-2, then j≥1j\ge1 and the new carrier’s intact relative row 11 lies inside the already anchored macro-row j−1j-1. By the horizontal-origin bounds, its length-PsP_s body interval meets at least one anchored macrocell of that row in three consecutive positions. Those three positions are occupied by the new carrier, while the no-three-gap property prevents the anchored carrier from omitting all three; hence the two placements overlap. If b=jPs−1b=jP_s-1, again j≥1j\ge1. The intact cells with relative coordinates (0,0),(1,0),(2,0)(0,0),(1,0),(2,0) of the new carrier lie on the top row of the carrier directly below. On that top row the only possible boundary omission is the single north dent, and the corner cells are intact, so at least one of these three cells is already occupied. Both cases are impossible.

If b=jPs+1b=jP_s+1, the corner zz must be the south bump, so a=iPs−b⋆=(i−1)Ps+8a=iP_s-b_\star=(i-1)P_s+8. For i=0i=0, the body leaves the square. For i≥1i\ge1, its body overlaps the left carrier throughout

{(i−1)Ps+8,…,iPs−1}×{jPs+1,…,jPs+Ps−1}.\{(i-1)P_s+8,\ldots,iP_s-1\}\times\{jP_s+1,\ldots,jP_s+P_s-1\}.

In particular, ((i−1)Ps+9,jPs+2)((i-1)P_s+9,jP_s+2) belongs to both carriers: it is outside both cavities and all possible dents. Thus b=jPsb=jP_s. With b=jPsb=jP_s fixed, if a≤iPs−2a\leq iP_s-2 then necessarily i≥1i\geq1, and the new carrier’s intact relative column 1 meets the already anchored carrier immediately to the left in at least three consecutive vertical body positions. The no-three-gap property forces an overlap. If a=iPs−1a=iP_s-1, the new carrier’s intact southwest corner overlaps the left carrier’s intact southeast corner. Finally, if a=iPs+1a=iP_s+1, covering zz would require a relative cell with first coordinate −1-1 at height zero, whereas the only such cell is the west bump at height b⋆b_\star. Hence a=iPsa=iP_s, and therefore (a,b)=(iPs,jPs)(a,b)=(iP_s,jP_s). Induction anchors exactly one carrier at every macro-origin. Table 1 records the exhaustive alternatives and their overlap certificates.

Placement covering zzExclusion or surviving case
Plug at z+(0,−1)z+(0,-1)Crosses the lower boundary or overlaps the intact lower carrier.
Plug at z+(−1,0)z+(-1,0)Crosses the left boundary or overlaps the intact left carrier.
Plug at z+(−1,−1)z+(-1,-1)Crosses the boundary or overlaps an intact previously occupied corner.
Carrier with b≤jPs−2b\leq jP_s-2Its intact body row 1 forces three consecutive occupied cells in the preceding macro-row, contradicting the no-three-gap property.
Carrier with b=jPs−1b=jP_s-1Three intact south body cells meet the occupied top row below, where at most one north dent is absent.
Carrier with b=jPs+1b=jP_s+1This requires the south bump at zz. It crosses the boundary if i=0i=0; otherwise it overlaps at ((i−1)Ps+9,jPs+2)((i-1)P_s+9,jP_s+2).
Carrier with b=jPsb=jP_s, a≤iPs−2a\leq iP_s-2Its intact body column 1 overlaps the anchored macro-column to the left in three consecutive cells.
Carrier with b=jPsb=jP_s, a=iPs−1a=iP_s-1The new southwest corner overlaps the left carrier’s intact southeast corner.
Carrier with b=jPsb=jP_s, a=iPs+1a=iP_s+1Covering zz would require a cell at relative coordinate (−1,0)(-1,0), whereas the only west bump is at height b⋆b_\star.
Carrier at (a,b)=z(a,b)=zThe unique surviving anchored position.

Table 1 (PDF p. 19). Exhaustive alternatives at the next row-major macro-corner z=(iPs,jPs)z=(iP_s,jP_s). Here (a,b)(a,b) denotes the origin of a carrier that covers zz. Each rejected placement either crosses the physical boundary or overlaps a previously anchored carrier.

Consider two horizontal neighbours. If the left east bit and right west bit differ, the existing bump overlaps an undeleted body cell of the neighbour. Hence they agree. If both are open, the left east bump can avoid overlap only by occupying the right west dent, so

AH(ηS,ηN,E(u),ℓE)=AH(ηS′,ηN′,W(u′),ℓW′).A_H(\eta_S,\eta_N,E(u),\ell_E)=A_H(\eta'_S,\eta'_N,W(u'),\ell'_W).

Injectivity yields equality of the perpendicular bits, Wang colours, and labels. The fixed bump at height b⋆b_\star reciprocally fills the left east dent. If both sides are closed, the adjacent body columns are disjoint. The vertical argument is identical with AVA_V.

An open outer side would place a bump outside the square, so outer bits vanish. Diagonal support boxes meet in four cells around a macro-corner. The lower-left carrier occupies only its northeast body corner among those four; the upper-right carrier occupies only its southwest body corner. The other two cells cannot be bumps because variable coordinates are at most Ks+7<Ps−8K_s+7<P_s-8, while the fixed bump coordinate is b⋆≠0b_\star\ne0. Thus diagonal carriers are disjoint. Boxes separated by two macro-pitches are disjoint.

All exchanged dents are filled by reciprocal bumps, and closed interfaces leave no holes. The uncovered cells are therefore precisely the translated cavities. They are mutually separated, 4-connected, and have area three. Any remaining placement lies in one residual component. A carrier is too large, while a plug fitting a three-cell component must equal it. The translation is uniquely the cavity origin.

Set Pmac=PsP_{\mathrm{mac}} = P_s and ccol=0c_{\mathrm{col}} = 0. A macro-edge is open exactly when the reciprocal carrier bits on that interface are one; plugs lie strictly inside one macrocell. We verify saturation on one orientation, the others following by symmetry. Suppose the bottom horizontal edge and the left vertical edge of a 2-by-2 macro-square are open. The open bottom edge equates the north bits of its two incident carriers. Since the bottom-left north bit is one (the left vertical interface is open), the bottom-right north bit is also one; reciprocal-bit equality then makes the right vertical interface open. That open right interface equates the west bits of its two incident carriers. The bottom-right west bit is one (the bottom interface is open), so the top-right west bit is one; reciprocal-bit equality then makes the top horizontal interface open. Thus two consecutive open edges force all four.

Theorem Theorem 6.2 makes the opening components filled rectangles. The carrier identities on an open edge give Wang-colour matching inside each component, and the common label supplies one element of {0,…,samp−1}\{0,\ldots,s_{\mathrm{amp}}-1\}. Conversely, a rectangular partition, an open Wang tiling on every block, and edge labels determine all carrier records. The interface rules give disjointness, the diagonal check handles corner contacts, and the unique plugs fill the cavities. These maps are inverse: a physical tiling determines the partition, the Wang tile identities and the interface labels, and conversely these data prescribe all carrier placements and the unique cavity plugs. An all-closed singleton still has one distinct carrier for every u∈Wu \in W, because uu is recorded by its cavity.

There are En=2n(n−1)E_n = 2n(n-1) index-grid edges. A partition with I(D)I(D) seam edges has En−I(D)E_n-I(D) open edges, proving the exact sum.

For every rectangular partition, ∑B∈D(wB+hB)=2n+I(D)\sum_{B\in D}(w_B+h_B)=2n+I(D), because block perimeters count the outer boundary once and each seam twice. Figure 3 contrasts the canonical one-block term with a representative nontrivial rectangular partition and identifies the seam parameter I(D)I(D) that drives the suppression estimate below.

The bijection in Theorem 7.2 assigns every geometric tiling to exactly one partition D∈Part⁡nD \in\operatorname{Part}_n.

The unique one-block partition is the canonical term; every other tiling appears in exactly one nontrivial partition. For a fixed DD, the exact sum above already includes all open Wang tilings inside every block and all amplifier-label choices on every open macro-edge. Grouping the remaining partitions by their seam count I(D)I(D) therefore accounts for every noncanonical tiling exactly once. The two estimates below then bound, respectively, how many such partitions have a given II and how large the complete internal Wang contribution of each partition can be.

For a nontrivial partition, Theorem 6.1 gives I(D)≥nI(D) \ge n and at most 256I256^{I} dissections with II seams. By Theorem 5.3 and the block-perimeter identity,

∏B∈Darect(wB,hB)≤Rrect2n+I(D).\prod_{B\in D} a_{\mathrm{rect}}(w_B,h_B)\le R_{\mathrm{rect}}^{2n+I(D)}.

Writing J(n)J(n) for the sum of the nontrivial-partition terms, the exhaustive partition bijection now yields

J(n)sampEn≤∑I=nEn256Isamp−IRrect2n+I≤∑I=n∞(256Rrect3samp)I=434−n<1.\begin{aligned} \frac{J(n)}{s_{\mathrm{amp}}^{E_n}}\le\sum_{I=n}^{E_n}256^I s_{\mathrm{amp}}^{-I}R_{\mathrm{rect}}^{2n+I} \\ &\le\sum_{I=n}^{\infty}\left(\frac{256R_{\mathrm{rect}}^3}{s_{\mathrm{amp}}}\right)^I=\frac{4}{3}4^{-n}<1. \end{aligned}

where the second inequality uses 2n+I≤3I2n+I\le3I and samp=1024Rrect3s_{\mathrm{amp}}=1024R_{\mathrm{rect}}^3. This sum includes every noncanonical tiling through its unique rectangular partition. For n≥2n\ge2 this is at most 1/121/12. The one-block term is sampEnarect(n,n)s_{\mathrm{amp}}^{E_n}a_{\mathrm{rect}}(n,n), so the normalized error is strictly below one and the floor identity follows. For n=1n=1, there is only the singleton partition and E1=0E_1=0.

In particular, the identity cavity distinguishes Wang tile types even when their four edge colours coincide. For consecutive register values, the cavity positions are respectively

{(16,17),(17,16),(17,17)},{(20,17),(21,16),(21,17)}.\{(16,17),(17,16),(17,17)\},\qquad\{(20,17),(21,16),(21,17)\}.

Recovering the Wang Count

The boundary-amplified Wang system separates the desired computation histories from the other open-boundary configurations by counting multiplicity. A bound on the remaining configurations makes the accepting-path count recoverable by integer division. The section also verifies the bit complexity of this readout, establishing metric completeness for the fixed Wang counter.

Define the total Wang-counting function by Gprod(bin⁡(n))=aprod(n)G_{\mathrm{prod}}(\operatorname{bin}(n))=a_{\mathrm{prod}}(n) for n≥1n\ge1, and set it to zero on all other strings.

Theorem 8.1 (Metric completeness of the Wang count). The function GprodG_{\mathrm{prod}} has the following properties.

  1. Gprod∈#EXPG_{\mathrm{prod}}\in\#\mathrm{EXP}.

  1. For n=Eside(x)n=E_{\mathrm{side}}(x),

    aprod(n)=Q4n−4(1+CU(x))+Junk⁡(n)a_{\mathrm{prod}}(n)=Q^{4n-4}(1+C_U(x))+\operatorname{Junk}(n).

  1. Let n1n_1 be the least integer at least two satisfying 2n1−1>15Q22^{n_1-1}>15Q^2, and let nthr=max⁡(5,n1)n_{\mathrm{thr}}=\max(5,n_1). Then

    0≤Junk⁡(n)<Q4n−4(n≥nthr)0\le\operatorname{Junk}(n)<Q^{4n-4}\qquad(n\ge n_{\mathrm{thr}}).

  1. The exceptional set Xexc={x:Eside(x)<nthr}X_{\mathrm{exc}}=\{x:E_{\mathrm{side}}(x)<n_{\mathrm{thr}}\} is finite. There is a polynomial-time finite-table function HexcH_{\mathrm{exc}} agreeing with CUC_U on this set.

  1. The instance map rmet(x)=bin⁡(Eside(x))r_{\mathrm{met}}(x)=\operatorname{bin}(E_{\mathrm{side}}(x)) and the postprocessor

h⋆(x,y)={Hexc(x),Eside(x)<nthr,max⁡(0,⌊yQ4Eside(x)−4⌋−1),Eside(x)≥nthr,h_{\star}(x,y)= \begin{cases} H_{\mathrm{exc}}(x), & E_{\mathrm{side}}(x)<n_{\mathrm{thr}},\\ \max\left(0,\left\lfloor\frac{y}{Q^{4E_{\mathrm{side}}(x)-4}}\right\rfloor-1\right), & E_{\mathrm{side}}(x)\ge n_{\mathrm{thr}}, \end{cases}

form a polynomial-time one-query metric reduction from CUC_U to GprodG_{\mathrm{prod}}. The exponentiation is stopped once its value exceeds yy. On exceptional inputs the postprocessor ignores yy.

  1. GprodG_{\mathrm{prod}} is #EXP\#\mathrm{EXP}-complete under polynomial-time metric reductions.

Proof. An open WprodW_{\mathrm{prod}}-tiling of an nn-square has a unique encoding by O(n2)O(n^2) fixed-length tile labels. A deterministic verifier checks all horizontal and vertical adjacencies in O(n2)O(n^2) time. On a binary input of length ℓ\ell, n<2ℓn<2^\ell, so guessing the labels and checking them takes 2O(ℓ)2^{O(\ell)} time. Malformed strings and zero are rejected deterministically. This proves membership.

For n=Eside(x)n=E_{\mathrm{side}}(x), Theorem 3.1 gives AC⋆(n)=1+CU(x)A_{C_\star}(n)=1+C_U(x), and Theorem 5.2 gives

aprod(n)=Q4n−4AC⋆(n)+Junk⁡(n).a_{\mathrm{prod}}(n)=Q^{4n-4}A_{C_\star}(n)+\operatorname{Junk}(n).

This proves substitution.

Since Q=2R0+1Q=2R_0+1, 0<R0/Q<1/20<R_0/Q<1/2. For n≥5n\ge5,

Junk⁡(n)Q4n−4≤Q−(4n−4)+15Q2(R0Q)n<Q−(4n−4)+15Q22−n.\frac{\operatorname{Junk}(n)}{Q^{4n-4}} \le Q^{-(4n-4)}+15Q^2\left(\frac{R_0}{Q}\right)^n <Q^{-(4n-4)}+15Q^2 2^{-n}.

When n≥nthrn\ge n_{\mathrm{thr}}, both terms are below 1/21/2, proving the strict threshold estimate.

The lower bound Eside(x)≥274∣x∣+74E_{\mathrm{side}}(x)\ge2^{74|x|+74} tends to infinity with ∣x∣|x|, so only finitely many strings lie below the fixed threshold. Their values CU(x)C_U(x) define a finite hard-coded table HexcH_{\mathrm{exc}}. A lookup in a fixed table is polynomial-time. This existence claim does not require the threshold to be below 2742^{74}.

For a nonexceptional input, put n=Eside(x)n=E_{\mathrm{side}}(x) and B=Q4n−4B=Q^{4n-4}. The substitution and threshold estimates give

aprod(n)=B(1+CU(x))+Junk⁡(n),0≤Junk⁡(n)<B.a_{\mathrm{prod}}(n)=B(1+C_U(x))+\operatorname{Junk}(n),\qquad0\le\operatorname{Junk}(n)<B.

Therefore

⌊aprod(n)B⌋−1=CU(x).\left\lfloor\frac{a_{\mathrm{prod}}(n)}{B}\right\rfloor-1=C_U(x).

The exceptional branch is correct by the table.

It remains to justify the running time of the postprocessor. If y=0y=0, the second branch of h⋆h_\star returns zero immediately. Assume henceforth that y≥1y\ge1, let A=4n−4A=4n-4, and let ℓy=∣bin⁡(y)∣\ell_y=|\operatorname{bin}(y)|. Fix sQs_Q with 2sQ≤Q<2sQ+12^{s_Q}\le Q<2^{s_Q+1}. If AsQ≥ℓy+1As_Q\ge\ell_y+1, then QA>yQ^A>y, and the quotient is zero. Otherwise A≤ℓyA\le\ell_y, and exponentiation by squaring computes QAQ^A using integers of at most A(sQ+1)≤2ℓyA(s_Q+1)\le2\ell_y bits. Division is polynomial in ∣x∣+ℓy|x|+\ell_y. No loop iterates nn in unary.

Thus (rmet,h⋆)(r_{\mathrm{met}},h_\star) is a polynomial-time metric reduction. The function CUC_U is parsimoniously #EXP\#\mathrm{EXP}-complete by Theorem 3.1; composing its parsimonious reductions with this metric reduction proves hardness of GprodG_{\mathrm{prod}}.

For any sufficiently long xx, the nonexceptional postprocessor sends y=1y=1 to zero because B≥2B\ge2. Hence positivity of its second argument is not preserved.

Completeness of the Square-Tiling Count

The main theorem follows by composing the Wang-level readout with the geometric counting identity. The geometric postprocessor outputs an integer no larger than its input, so the two reductions compose in polynomial bit time. The general membership bound supplies the matching upper bound.

Proof of Theorem 1.1. Every member of T⋆T^\star is a nonempty finite 4-connected set by Theorem 7.2. Proposition 2.1 applies to this fixed family and gives the stronger membership GT⋆∈#E⊆#EXPG_{T^\star} \in\#\mathrm{E} \subseteq\#\mathrm{EXP}. On the canonical input bin⁡(0)\operatorname{bin}(0), this count includes the unique empty tiling of Square0\mathrm{Square}_0, while malformed strings receive value zero by definition.

For n≥1n \ge1, the sets Squaren\mathrm{Square}_n and Rectn,n\mathrm{Rect}_{n,n} coincide, as do their open Wang matching rules; hence aprod(n)=arect(n,n)a_{\mathrm{prod}}(n) = a_{\mathrm{rect}}(n,n). Theorem 7.2 gives

⌊gT⋆(Psn)samp2n(n−1)⌋=aprod(n)\left\lfloor\frac{g_{T^\star}(P_s n)}{s_{\mathrm{amp}}^{2n(n-1)}} \right\rfloor= a_{\mathrm{prod}}(n)

for every n≥1n \ge1, including n=1n = 1 under samp0=1s_{\mathrm{amp}}^{0} = 1.

Define the instance map by

rgeom(z)={bin⁡(Psn),z=bin⁡(n), n≥1,bin⁡(0),otherwise.r_{\mathrm{geom}}(z) = \begin{cases} \operatorname{bin}(P_s n), & z = \operatorname{bin}(n),\ n \ge1,\\ \operatorname{bin}(0), & \text{otherwise}. \end{cases}

It checks canonical binary syntax and, on a valid positive input, multiplies by the fixed constant PsP_s, so it is polynomial-time. Define hgeom(z,y)=0h_{\mathrm{geom}}(z,y) = 0 when zz is malformed or equals bin⁡(0)\operatorname{bin}(0). For z=bin⁡(n)z = \operatorname{bin}(n) with n≥1n \ge1, let A=2n(n−1)A = 2n(n - 1) and choose the fixed integer sss_s satisfying 2ss≤samp<2ss+12^{s_s} \le s_{\mathrm{amp}} < 2^{s_s+1}. If A=0A = 0, set hgeom(z,y)=yh_{\mathrm{geom}}(z,y) = y. If A≥1A \ge1 and y=0y = 0, set hgeom(z,y)=0h_{\mathrm{geom}}(z,y) = 0. For A,y≥1A,y \ge1, let ℓy=∣bin⁡(y)∣\ell_y = |\operatorname{bin}(y)|. If Ass≥ℓy+1A s_s \ge\ell_y + 1, then sampA>ys_{\mathrm{amp}}^A > y, so set hgeom(z,y)=0h_{\mathrm{geom}}(z,y) = 0. Otherwise A≤ℓyA \le\ell_y, and exponentiation by squaring computes the divisor, giving hgeom(z,y)=⌊y/sampA⌋h_{\mathrm{geom}}(z,y) = \left\lfloor y/s_{\mathrm{amp}}^A \right\rfloor. All intermediate integers have at most A(ss+1)≤2ℓyA(s_s + 1) \le2\ell_y bits. Computing the divisor and quotient is therefore polynomial in ∣bin⁡(n)∣+ℓy|\operatorname{bin}(n)| + \ell_y, without iterating nn in unary. This proves that hgeomh_{\mathrm{geom}} is a total polynomial-time map.

For z=bin⁡(n)z = \operatorname{bin}(n) with n≥1n \ge1, the geometric floor identity established above gives

hgeom(z,GT⋆(rgeom(z)))=aprod(n)=Gprod(z).h_{\mathrm{geom}}(z,G_{T^\star}(r_{\mathrm{geom}}(z))) = a_{\mathrm{prod}}(n) = G_{\mathrm{prod}}(z).

On every other zz, both sides are zero. Hence (rgeom,hgeom)(r_{\mathrm{geom}}, h_{\mathrm{geom}}) is a one-query metric reduction.

The postprocessor satisfies hgeom(z,y)≤yh_{\mathrm{geom}}(z,y) \le y. To make the composition explicit, combine the reduction (rmet,h⋆)(r_{\mathrm{met}}, h_\star) of Theorem 8.1 with the geometric reduction by setting

r(x)=rgeom(rmet(x)),h(x,y)=h⋆(x,hgeom(rmet(x),y)).r(x) = r_{\mathrm{geom}}(r_{\mathrm{met}}(x)), \qquad h(x,y) = h_\star(x,h_{\mathrm{geom}}(r_{\mathrm{met}}(x),y)).

Because the intermediate value hgeom(rmet(x),y)h_{\mathrm{geom}}(r_{\mathrm{met}}(x),y) has no more bits than yy, the composed postprocessor runs in time polynomial in ∣x∣+∣bin⁡(y)∣|x| + |\operatorname{bin}(y)|. Hence CUC_U metric-reduces to GT⋆G_{T^\star}. Since CUC_U is parsimoniously #EXP\#\mathrm{EXP}-complete, GT⋆G_{T^\star} is #EXP\#\mathrm{EXP}-hard under polynomial-time metric reductions. Together with membership, it is complete.

This completes the proof.

Conclusion and Discussion

We prove that counting translation-only tilings of an n×nn \times n square by a fixed finite family of connected polyominoes is #EXP-complete under polynomial-time metric reductions. Together with the efficient tileability criterion for fixed polyomino families [14], this establishes a sharp separation between feasibility and exact counting when the entire input is a binary side length. The proof shows that a binary side length can select an accepting-path count within a fixed Wang system and that this numerical information survives an ordinary geometric realization as an exact count, extending classical computation-to-tiling encodings to the fixed-square setting. The decisive step is a global counting guarantee obtained by combining a perimeter bound for open Wang rectangles with a seam bound for nontrivial rectangular dissections. Their combination places the total normalized contribution of all noncanonical configurations below one, so integer division recovers the intended count exactly. A companion Lean 4 formalization of the completeness result is available [11].

Future directions include simplifying the fixed polyomino family and extending numerical isolation to other succinct counting problems. More broadly, combining geometric rigidity with global counting bounds may provide a reusable approach to proving counting hardness under fixed local constraints.

AI Methodology

OpenAI’s ChatGPT was used to improve the language and clarity of the manuscript. A GPT-based multi-agent system assisted in reviewing the mathematical proofs and organizing the arguments into a Lean 4 formalization, particularly for the constructions and correctness proofs in § 3–§ 9.

References

  1. [1]Dorit Aharonov and Sandy Irani. Translationally invariant constraint optimization problems. In 38th Computational Complexity Conference (CCC 2023), LIPIcs 264, article 23, 2023. https://doi.org/10.4230/LIPIcs.CCC.2023.23.
  2. [4]Robert Berger. The Undecidability of the Domino Problem. Memoirs of the American Mathematical Society, No. 66, 1966. https://doi.org/10.1090/memo/0066.
  3. [5]Erik D. Demaine and Martin L. Demaine. Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs and Combinatorics, 23(Suppl.):195–208, 2007. https://erikdemaine.org/papers/Jigsaw_GC/.DOI
  4. [6]Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Theory of Computing, 9(2):31–116, 2013. https://doi.org/10.4086/toc.2013.v009a002.
  5. [8][Kas61] P. W. Kasteleyn. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 27(12):1209–1225, 1961. https://doi.org/10.1016/0031-8914(61)90063-5.
  6. [10][Kre88] Mark W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490–509, 1988. https://doi.org/10.1016/0022-0000(88)90039-6.
  7. [11][Che26] Qiyu Chen. Pak’s fixed-polyomino square-counting theorem: Lean 4 formalization. Source repository, 2026. https://github.com/canghaimeng/PakFixedPolyomino.
  8. [12][MR01] Christopher Moore and John Michael Robson. Hard tiling problems with simple tiles. Discrete & Computational Geometry, 26(4):573–590, 2001. https://doi.org/10.1007/s00454-001-0047-6.
  9. [13][Oll09] Nicolas Ollinger. Tiling the plane with a fixed number of polyominoes. In Language and Automata Theory and Applications (LATA 2009), pages 638–647, 2009. https://doi.org/10.1007/978-3-642-00982-2_54.
  10. [14][Pak18] Igor Pak. Complexity problems in enumerative combinatorics. In Proceedings of the International Congress of Mathematicians (ICM 2018), volume 3, pages 3139–3166, 2018. https://arxiv.org/abs/1803.06636.
  11. [15][Pak20] Igor Pak. Counting with tiles. Lecture slides, Journée-séminaire de combinatoire, Paris Nord, June 2, 2020. https://lipn.fr/~cb/Seminaires/Slides/pak2020.pdf.
  12. [16][PY13] Igor Pak and Jed Yang. Tiling simply connected regions with rectangles. Journal of Combinatorial Theory, Series A, 120(7):1804–1816, 2013. https://doi.org/10.1016/j.jcta.2013.06.008.
  13. [17][Rob71] Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12:177–209, 1971.DOI
  14. [20][Wan61] Hao Wang. Proving theorems by pattern recognition—II. Bell System Technical Journal, 40(1):1–41, 1961. https://doi.org/10.1002/j.1538-7305.1961.tb03975.x.

Paper details

vlnc:W_6kunr5p3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents