This paper introduces row-major natural ordering labeling (hereafter referred to as the “Natural Square”) to the domino tiling space of the \(4\times4\) square grid and elucidates the structural correspondence between geometric group actions and algebraic invariants. First, based on the 36 complete tilings derived from Kasteleyn theory, these tilings are classified into 9 equivalence classes (hereafter, families) under the action of the dihedral group \(D_4\). Next, phenomena observed through exhaustive computational experiments are analyzed, and it is shown that the sum of the block-product sums for any tiling and its 90-degree rotation is invariably 1,428 (90-Degree Rotation Complement Theorem for Block-Product Sums). Furthermore, algebraic complementary pairs that satisfy power-sum equalities (Prouhet–Tarry–Escott type) across multiple degrees are identified, and the structure of higher-moment preservation phenomena that transcend geometric constraints is discussed.
The domino tiling problem is a classical theme in combinatorics [6]. Since Kasteleyn (1961) [3] presented an exact solution using Pfaffians, extensive research has accumulated from the perspectives of statistical physics and graph theory concerning the enumeration of dimer configurations (perfect matchings) on lattices.
Previous studies have actively investigated geometric and group-theoretic invariants of tiling sets (tile invariants) [4] and topological analysis of tiling spaces based on flip operations [5]. However, most of these invariants depend on tile placement relations or boundary conditions, and to the best of the author’s knowledge, the perspective focusing on algebraic properties when specific numerical labels are assigned to each cell has not been a central theme in existing research. Moreover, no systematic investigation appears to have been conducted on the interaction between numerical labeling and complementary involution operations in domino tilings. In this paper, a complementary involution refers to a mapping obtained by composing a numerical complement map that sends each value \(x\) on the grid to \(17-x\) with a geometric symmetry operation of order 2, such as 180-degree rotation or reflection.
For the \(4 \times 4\) grid, it is a well-known consequence of Kasteleyn’s theory that the total number of tilings is 36. In this work, we introduce a labeling called the “Natural Square”, in which the cells are assigned values from 1 to 16 in row-major order, as weights to this known configuration space. By performing exhaustive computational verification on the finite configuration space (36 tilings) and theoretically formalizing the observed regularities, following the experimental mathematics framework [1], we demonstrate that the Natural Square labeling generates specific algebraic identities (invariants) with respect to rotation and complement operations on domino configurations.
The novelty of this study lies in the discovery of algebraic conserved quantities that emerge when the number-theoretic structure of the Natural Square labeling is imposed on the known configuration space of 36 tilings. While the enumeration of tilings on the \(4 \times 4\) grid and their geometric classification under the dihedral group \(D_4\) are classical results, the label-dependent complementary identities presented here—including the 90-degree rotational invariance of block-product sums, higher-degree complementary invariance of power sums, and the multigrade chain structure— appear to be new findings without precedent in prior literature, to the author’s knowledge. Details of these results are summarized in Section 3.
Definition 2.1(Coordinate system and labeling of the 4th-order Natural Square).Each cell of the square grid \(G\) is represented by coordinates in the set \(V = \{(i,j) \mid 1 \le i,j \le 4\}\), where \(i\) denotes the row and \(j\) the column. The labeling function \(L: V \to \{1,2,\dots,16\}\) for the 4th-order Natural Square is defined as \[L(i,j) = 4(i-1) + j.\]
This yields the following matrix arrangement: \[\begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{pmatrix}.\]
Definition 2.2(Set of domino tilings).A domino \(d\) is defined as a set of two adjacent coordinates \(\{v_1, v_2\} \subset V\). A domino tiling \(P = \{d_1, \dots, d_8\}\) of the 4th-order Natural Square is a perfect matching of \(V\), and the set of all 36 tilings is denoted by \(\mathcal{P}\).
In what follows, a general element of \(\mathcal{P}\) is denoted by \(P\), and specifically enumerated tilings are written as \(P_1, P_2, \dots, P_{36}\) in a fixed order.
Definition 2.3(Rotation map \(\rho\) and \(P^{90}\)).The coordinate permutation \(\rho: V \to V\) is defined by \(\rho(i,j) = (j, 5-i)\). The 90-degree rotation of a tiling \(P \in \mathcal{P}\) is given by \[P^{90} = \{ \{\rho(v_1), \rho(v_2)\} \mid \{v_1, v_2\} \in P \}.\] In algebraic evaluation, the labels \(L(i,j)\) remain fixed; \(P^{90}\) refers to evaluating the rotated tile configuration on the fixed labeling. Specifically, if a domino \(d = \{v_1, v_2\}\) in tiling \(P\) covers labels \(L(v_1), L(v_2)\), then the corresponding domino \(d' = \{\rho(v_1), \rho(v_2)\}\) in \(P^{90}\) covers \(L(\rho(v_1)), L(\rho(v_2))\).
Proposition 2.4(Bijectivity and cycle structure of the rotation map).The map \(f: \mathcal{P} \to \mathcal{P}\) (\(P \mapsto P^{90}\)) is bijective. Moreover, \(\mathcal{P}\) decomposes under the orbits (cycle decomposition) induced by \(f\) into the following structure:
1. 1-cycles (fixed points): 2 (\(|Fix(f)|=2\)),
2. 2-cycles: 3 (\(|Fix(f^2)|=8\), of which 2 are common with \(Fix(f)\), and the remaining 6 form three 2-cycles),
3. 4-cycles: 7 (the remaining 28 tilings form seven orbits of four each).
The total number of elements in the set of all tilings is \(2(1) + 3(2) + 7(4) = 36\), covering the entire set.
Proof. \(\rho\) is a permutation of the set \(V\) of order 4 (\(\rho^4 = \mathrm{id}_V\)). The map \(f\) is the permutation of \(\mathcal{P}\) induced by \(\rho\), so the inverse \(f^3\) exists and thus \(f\) is bijective. Regarding the cycle structure, exhaustive computation confirms that \(|Fix(f)|=2\) and \(|Fix(f^2)|=8\). Since the orbit lengths of a permutation of order 4 on a finite set are limited to the divisors of the order (1, 2, 4), the above decomposition is uniquely determined. ◻
The complete set of \(36\) domino tiling patterns of the \(4\times4\) square grid is presented in three parts. Figure 1 shows the patterns \(P_1\)–\(P_{12}\), Figure 2 shows the patterns \(P_{13}\)–\(P_{24}\), and Figure 3 shows the patterns \(P_{25}\)–\(P_{36}\).
Remark 2.5(Independence of domino identification symbols). The total number of tilings, 36, depends solely on the geometric configuration. The symbols \(A, B, \dots, H\) in the figures are merely convenient labels for visually distinguishing the adjacency relations between cells (i.e., the regions covered by each domino) and are independent of the numerical labeling of the cells. Therefore, interchanging these symbols or omitting them altogether has no effect on the counting of tilings or their essential properties.
The enumeration of all 36 tilings presented in this paper, as well as the verification of algebraic identities in the proofs of each theorem, is based on exhaustive computation using custom programs. In order to ensure the validity and reproducibility of computer-assisted proofs, the following verification procedure was defined and carried out.
1. Data standardization (Canonical Representation): Each tiling is encoded as a \(4 \times 4\) integer matrix. To avoid duplicate counting of geometrically identical configurations, a “canonical labeling function” was implemented that reassigns identifiers \(0, \dots, 7\) to the dominos in the order of their first appearance in a top-left to bottom-right raster scan. This allows unique management of all 36 configurations without the cost of isomorphism checking.
2. Verification of population completeness: It is
mathematically guaranteed by Kasteleyn’s theory that the total number of
tilings on a \(4 \times 4\) grid is 36.
In this study, it was confirmed that the results of our independently
implemented enumeration algorithm match this theoretical value.
Furthermore, using the program
calculator0_symmetry_check.py, exhaustive search confirmed
that the set \(\mathcal{P}\) of 36
tilings is closed under the action of the dihedral group \(D_4\). The number of orbits derived from
Burnside’s lemma was verified to match the known 9 families, thereby
doubly ensuring the exhaustiveness of the population.
3. Computation of invariants and exhaustive search: The
numerical labels \(L(i,j)\) of the
cells constituting each domino are directly referenced from the
definition of the Natural Square. For identifying the “algebraic
complementary pairs” discussed in Section 3 and beyond, the program
Calculator4.py was used to perform an exhaustive
brute-force inspection of all \(\binom{36}{2}
= 630\) possible pairs formed from the 36 patterns, uniquely
extracting those pairs that satisfy the identities.
4. Publication for reproducibility: All source code used for verification, together with the tiling data library, is publicly available in the following repository. It has been confirmed that all results are reproducible in a specific Python environment (Version 3.10+, NumPy 1.23+).
Repository: https://github.com/soaisu-ken/DominoTilingSymmetries4x4
Stable Release: https://github.com/soaisu-ken/DominoTilingSymmetries4x4/releases/tag/v1.3.0
Commit ID: b269847
For the set of 36 tilings \(\mathcal{P} = \{P_1, \dots, P_{36}\}\) (Figures 1–3) obtained by the enumeration algorithm described in the previous subsection, classification is performed based on the action of the dihedral group \(D_4\). In this paper, the elements of \(D_4\) are denoted \(\{e, r_{90}, r_{180}, r_{270}, s_h, s_v, s_{d_1}, s_{d_2}\}\), where \(r_{90}\) corresponds to the map \(f\) defined earlier.
Proposition 2.6(Classification by Burnside’s lemma). Under the action of the dihedral group \(D_4\), the 36 tilings are classified into 9 essentially distinct equivalence classes (hereafter, families).
Proof. By Burnside’s lemma, the number of families is given by \[|\text{Families}| = \frac{1}{|D_4|} \sum\limits_{g \in D_4} |\text{Fix}(g)|.\]
The fixed-point counts \(|\text{Fix}(g)|\) for each transformation \(g\) are derived as follows. These values have been fully confirmed to match the results of exhaustive computation by the program (Calculator 0).
Tilings invariant under \(r_{90}\) are limited to only two patterns, P15 and P26, due to the property that the grid is partitioned into four congruent orbits (each consisting of four cells). Those invariant under \(r_{180}\) include these two plus six centrally symmetric configurations (P1, P8, P11, P21, P24, P36), for a total of 8 patterns.
Horizontal reflection \(s_h\) and vertical reflection \(s_v\) require domino configurations symmetric with respect to the axis. On the other hand, diagonal reflections \(s_{d_1}\) and \(s_{d_2}\) map horizontal dominos to vertical ones, leading to contradictions in cell coverage along the diagonal when attempting to construct self-symmetric configurations. Exhaustive verification confirmed that no fixed points exist under diagonal reflections.
Substituting the above fixed-point counts yields \[|\text{Families}| = \frac{1}{8}(36 + 2 \times 2 + 8 + 12 \times 2 + 0 \times 2) = \frac{72}{8} = 9.\]
The specific invariant pattern IDs for each transformation are as shown in Table 1. ◻
| Transformation \(g\) | \(|\text{Fix}(g)|\) | Invariant pattern IDs |
|---|---|---|
| \(e\) | 36 | \(P_1\)–\(P_{36}\) |
| \(r_{90},\, r_{270}\) | 2 | \(P_{15}, P_{26}\) |
| \(r_{180}\) | 8 | \(P_1, P_8, P_{11}, P_{15}, P_{21}, P_{24}, P_{26}, P_{36}\) |
| \(s_h\) | 12 | \(P_1, P_6, P_8, P_9, P_{11}, P_{13}, P_{18}, P_{21}, P_{24}, P_{28}, P_{31}, P_{36}\) |
| \(s_v\) | 12 | \(P_1, P_3, P_5, P_8, P_{11}, P_{19}, P_{21}, P_{23}, P_{24}, P_{32}, P_{34}, P_{36}\) |
| \(s_{d_1},\, s_{d_2}\) | 0 | none |
Remark 2.7(Numerical verification program Calculator 0) .The values of \(|\text{Fix}(g)|\) in Proposition 2.6 were confirmed not only by combinatorial derivation but also by independent numerical verification using a program. The Calculator 0 referred to in this section processes data according to the following algorithm.
1. Input the set of 36 tilings \(\mathcal{P} = \{P_1, \dots, P_{36}\}\) as \(4\times4\) matrices.
2. For each tiling \(P\), apply all 8 transformations of \(D_4\) (rotations and reflections).
3. Apply the standardization (reassignment of identifiers) described in Section 2.1 to each transformed configuration to obtain a unique representation.
4. Determine whether the standardized configuration matches the original, and count the number of fixed configurations \(|\text{Fix}(g)|\) for each transformation \(g\).
5. Substitute the computed \(|\text{Fix}(g)|\) into Burnside’s lemma to calculate the number of equivalence classes (families): \[|\text{Families}| = \frac{1}{|D_4|} \sum\limits_{g \in D_4} |\text{Fix}(g)|.\]
This program is publicly available on GitHub at https://github.com/soaisu-ken/DominoTilingSymmetries4x4/releases/tag/v1.3.0 and fully reproduces all \(|\text{Fix}(g)|\) values and the family count of 9 as stated in this paper. Note that the program serves as auxiliary numerical verification of the theoretical discussion, and the proof of Proposition 2.6 itself is based on the combinatorial argument given above.
Figure 4 shows representatives of the nine orbits obtained under the \(D_4\) action in this section. Each family corresponds to an equivalence class (orbit) of tilings that are mapped to one another under the action of the dihedral group \(D_4\).
The size (cardinality) of each orbit depends on the degree of symmetry of the tiling \(P\). By the orbit-stabilizer theorem, \[|\mathrm{Orb}(P)| = \frac{|D_4|}{|\mathrm{Stab}(P)|} = \frac{8}{|\mathrm{Stab}(P)|},\] where \[\mathrm{Stab}(P) = \{ g \in D_4 \mid g(P) = P \}.\] is the subgroup of \(D_4\) that leaves \(P\) invariant.
Highly rotationally symmetric type: For tilings invariant under \(r_{90}\), \(|\mathrm{Stab}(P)| = 4\), so the orbit size is 2. For those invariant only under \(r_{180}\), \(|\mathrm{Stab}(P)| = 2\), so the orbit size is 4.
Mirror-symmetric type: When only reflection symmetry is present, the stabilizer has order 2, and the orbit size is 4.
Fully asymmetric type: When no symmetry exists except the identity transformation, the stabilizer is the trivial group (order 1), and the orbit size is 8.
The sum of the sizes of these nine orbits is \[2 \times 4 + 4 \times 3 + 8 \times 2 = 36,\] which shows that the entire space of 36 tilings is partitioned without excess or deficiency according to symmetry.
We first define the terminology and concepts used in this paper. A domino is the basic unit covering two adjacent cells. When emphasizing its numerical properties as a pair of integers, we also refer to it as a “2-block”. Furthermore, this paper distinguishes two types of complementarity:
Rotational Complementarity: the geometric relation between a tiling \(P\) and its 90-degree rotation \(P^{90}\). Such a pair is called a rotational complementary pair.
Algebraic Complementarity: the structural relation between two tilings \((P_i, P_j)\) that satisfy power-sum identities (PTE type), independent of geometric orientation. Such a pair is called an algebraic complementary pair.
The principal contribution of this paper is the discovery of novel algebraic symmetries that emerge when the number-theoretic structure called the “Natural Square” is imposed on the configuration space of \(4\times4\) domino tilings. The main results are as follows.
Discovery of the 90-Degree Rotation Complement Theorem for Block-Product Sums: It is proved that for any tiling \(P_i\) and its geometric 90-degree rotation tiling \(P_i^{90}\) (a rotational complementary pair), the sum of their block-product sums \(S_{\mathrm{prod}}\) is invariably equal to the constant \(C_{\mathrm{prod}} = 1{,}428\), independent of the tiling configuration. This algebraic symmetry is formalized as the 90-Degree Rotation Complement Theorem for Block-Product Sums: \[S_{\mathrm{prod}}(P_i) + S_{\mathrm{prod}}(P_i^{90}) = 1{,}428.\]
Establishment of higher-degree complementary identities for block-sum power sums: All 36 patterns of the \(4\times4\) Natural Square are completely classified into 18 algebraic complementary pairs \((P_i, P_j)\) based on the values of the block-sum power sums \(S_{\mathrm{sum}}^k(P)\), beyond the constraints imposed by \(D_4\) transformations. This pairing is positioned as a PTE-type phenomenon appearing under geometric constraints, analogous to degree-3 structures in the Prouhet–Tarry–Escott (PTE) problem [7] dealing with multigraded equality. The present study shows that these pairings satisfy the following identities up to degree \(k=3\) for the block-sum power sums \(S_{\mathrm{sum}}^k(P)\): \[S_{\mathrm{sum}}^k(P_i) + S_{\mathrm{sum}}^k(P_j) = C_k \quad (k=1, 2, 3),\] where \(C_1 = 272\), \(C_2 = 5{,}848\), \(C_3 = 141{,}032\). Although the identity breaks down at \(k=4\), it realizes a nontrivial multigrade phenomenon in the moments of sums.
Identification of algebraic centroid patterns: The first power sum of block sums \(S_{\mathrm{sum}}^1(P)\) is identically equal to the mean value \(\mu_{S^1} = 136\) across all 36 patterns. Furthermore, numerical analysis over all 36 patterns reveals a remarkable phenomenon: in four highly symmetric patterns (\(P_{11}, P_{15}, P_{21}, P_{26}\)), the higher moments \(S_{\mathrm{sum}}^k(P)\) exactly coincide with the overall mean for both \(k=2\) and \(k=3\). That is, the following relation holds: \[S_{\mathrm{sum}}^k(P) = \mu_{S^k} \quad \text{for } k=1, 2, 3 \quad (P \in \{P_{11}, P_{15}, P_{21}, P_{26}\}),\] where \(\mu_{S^2} = 2{,}924\) and \(\mu_{S^3} = 70{,}516\). These four patterns represent singular configurations that embody the average balance of the entire set in the space of higher moments. Focusing on this property—the coincidence of geometric symmetry and algebraic mean—we define these four patterns as the algebraic centroid of the entire set. This coincidence provides a concrete observation that highly symmetric configurations align with the affine mean of the whole set in moment vector space.
Elucidation of the structure of algebraic perfect complementary partitions: It is shown that the partition into the above algebraic complementary pairs is not unique, and the complete structure of this non-uniqueness is clarified. Among all \(\binom{36}{2} = 630\) possible pairs, only 26 valid pairs satisfy all four conditions. The graph formed by these valid pairs decomposes into the disjoint union of one complete graph \(K_4\) on \(\{P_{11}, P_{15}, P_{21}, P_{26}\}\) and two complete bipartite graphs \(K_{2,2}\). From this structure, it is proved that the total number of algebraic perfect complementary partitions is exactly \[3 \times 2 \times 2 = 12.\]
Algebraic equivalence of complementary conditions: Among the four complementary identity conditions defined, it is algebraically proved that the essential independent constraints are only the two conditions on \(S_{\mathrm{sum}}^2\) and \(S_{\mathrm{sum}}^3\). The condition on \(S_{\mathrm{sum}}^1\) holds automatically for any pair, and the condition on \(S_{\mathrm{prod}}\) is equivalent to the condition on \(S_{\mathrm{sum}}^2\). Specifically, \[S_{\mathrm{prod}}(P) = \frac{S_{\mathrm{sum}}^2(P) – \Sigma_2}{2}, \quad \Sigma_2 = \sum\limits_{n=1}^{16} n^2 = 1{,}496.\]
This equivalence provides an algebraic explanation for the surprising coincidence that a geometric operation (90-degree rotation) and an algebraic operation (power-sum complementarity) generate the same invariant \(C_{\mathrm{prod}} = 1{,}428\).
Definition 4.1(Block-product sum).For a tiling \(P\) on the 4th-order Natural Square, the block-product sum \(S_{\mathrm{prod}}(P)\) is defined as the sum of the products of the two numbers covered by each 2-block.
Application of the \(4\times4\) Natural Square labeling, with values from \(1\) to \(16\), to the tiling patterns \(P_1\) and \(P_{36}\) is shown in Figure 5.
Example 4.2. For pattern 1: \[\begin{aligned} S_{\mathrm{prod}}(P_1) &= 1 \times 2 + 3 \times 4 + 5 \times 6 + 7 \times 8 + 9 \times 10 + 11 \times 12 + 13 \times 14 + 15 \times 16 \\ &= 744. \end{aligned}\]
Example 4.3. For pattern 36: \[\begin{aligned} S_{\mathrm{prod}}(P_{36}) &= 1 \times 5 + 2 \times 6 + 3 \times 7 + 4 \times 8 + 9 \times 13 + 10 \times 14 + 11 \times 15 + 12 \times 16 \\ &= 5 + 12 + 21 + 32 + 117 + 140 + 165 + 192 \\ &= 684. \end{aligned}\]
Theorem 4.4(90-Degree Rotation Complement Theorem for Block-Product Sums).Let \(P\) be an arbitrary domino tiling on the \(4 \times 4\) Natural Square and let \(P^{90}\) be its 90-degree clockwise rotation. Then the sum of the block-product sums \(S_{\mathrm{prod}}(P)\) and \(S_{\mathrm{prod}}(P^{90})\) is invariant: \[S_{\mathrm{prod}}(P) + S_{\mathrm{prod}}(P^{90}) = 1{,}428.\]
| \(P_i\) | \(S_{\mathrm{prod}}(P_i)\) | Rotation pair (\(P_j = P_i^{90}\)) | \(S_{\mathrm{prod}}(P_j)\) | Sum | Match |
|---|---|---|---|---|---|
| \(P_1\) | 744 | \(P_{36}\) | 684 | 1,428 | \(\checkmark\) |
| \(P_2\) | 729 | \(P_{33}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_3\) | 729 | \(P_{18}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_4\) | 729 | \(P_{16}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_5\) | 714 | \(P_{13}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_6\) | 729 | \(P_{34}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_7\) | 714 | \(P_{14}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_8\) | 729 | \(P_{24}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_9\) | 729 | \(P_{23}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_{10}\) | 714 | \(P_{20}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{11}\) | 714 | \(P_{21}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{12}\) | 729 | \(P_{35}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_{13}\) | 714 | \(P_{32}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{14}\) | 714 | \(P_{17}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{15}\) | 714 | \(P_{15}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{16}\) | 699 | \(P_{12}\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{17}\) | 714 | \(P_{22}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{18}\) | 699 | \(P_{19}\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{19}\) | 729 | \(P_{31}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_{20}\) | 714 | \(P_{30}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{21}\) | 714 | \(P_{11}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{22}\) | 714 | \(P_7\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{23}\) | 699 | \(P_6\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{24}\) | 699 | \(P_8\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{25}\) | 729 | \(P_{29}\) | 699 | 1,428 | \(\checkmark\) |
| \(P_{26}\) | 714 | \(P_{26}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{27}\) | 714 | \(P_{10}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{28}\) | 714 | \(P_5\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{29}\) | 699 | \(P_2\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{30}\) | 714 | \(P_{27}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{31}\) | 699 | \(P_3\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{32}\) | 714 | \(P_{28}\) | 714 | 1,428 | \(\checkmark\) |
| \(P_{33}\) | 699 | \(P_{25}\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{34}\) | 699 | \(P_9\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{35}\) | 699 | \(P_4\) | 729 | 1,428 | \(\checkmark\) |
| \(P_{36}\) | 684 | \(P_1\) | 744 | 1,428 | \(\checkmark\) |
| Note: The identity \(S_{\mathrm{prod}}(P_i) + S_{\mathrm{prod}}(P_i^{90}) = 1{,}428\) holds for all \(i=1,\dots,36\). | |||||
Proof. Since the \(4 \times 4\) domino tiling problem admits only a finite number of solutions (\(N=36\)), the proof of this theorem is established by exhaustive computer verification. It was confirmed that the identity \(S_{\mathrm{prod}}(P) + S_{\mathrm{prod}}(P^{90}) = 1{,}428\) holds for every \(P_i\) from \(P_1\) to \(P_{36}\). Detailed verification results, including the corresponding rotation pair \(P_j = P_i^{90}\) for each \(P_i\), are presented in Table 2. ◻
Remark 4.5(\(270^\circ\) rotation and the trivial relation).In the \(4 \times 4\) Natural Square, the \(270^\circ\) clockwise rotation \(P^{270}\) is geometrically equivalent to the \(90^\circ\) counterclockwise rotation \(P^{-90}\), and moreover satisfies \((P^{270})^{90} = P\). Therefore, the fact that the present theorem holds for all \(i=1,\dots,36\) trivially implies that the identity also holds under \(270^\circ\) rotation: \[S_{\mathrm{prod}}(P) + S_{\mathrm{prod}}(P^{270}) = 1{,}428.\]
Remark 4.6(Numerical verification program) .The numerical verification program (Python) used for the proof of this theorem is publicly available in the GitHub repository at https://github.com/soaisu-ken/DominoTilingSymmetries4x4/releases/tag/v1.3.0 and can be consulted there.
Observation 4.7(Empirical discrete structure of the block-product sum \(S_{\mathrm{prod}}(P)\)).Exhaustive enumeration of all 36 domino tilings on the 4th-order Natural Square reveals that the block-product sum \(S_{\mathrm{prod}}(P)\) does not take continuous values but forms an arithmetic sequence consisting of the following five values:
1. Set of observed values: \(\mathcal{V} = \{684, 699, 714, 729, 744\}\),
2. Common difference: \(d = 15\),
3. Median (arithmetic mean): \(714\).
This numerical regularity is consistent with Theorem 4.4 (the 90-degree rotation identity). Indeed, each element of \(\mathcal{V}\) can be expressed as \(714 \pm 15k\) (\(k \in \{0,1,2\}\)), and the theorem guarantees \[S_{\mathrm{prod}}(P) + S_{\mathrm{prod}}(P^{90}) = 1{,}428.\]
The proof of Theorem 4.4 itself is based on the exhaustive verification presented in the previous subsection. The discussion in this subsection provides supplementary explanation concerning the structural background of the numerical value 1,428.
In particular, assuming the quadratic invariance of block sums shown in the subsequent Section 5, \[S_{\mathrm{sum}}^2(P) + S_{\mathrm{sum}}^2(P^{90}) = C_2,\] we demonstrate that the value 1,428 naturally arises from an algebraic identity. Accordingly, the present discussion does not constitute a proof of the theorem but explains the consistency of its numerical outcome.
Consider a domino tiling \(P\) as a perfect matching \(M\) of the grid graph. If a domino covers cells with values \(x,y\), the product \(xy\) can be expressed by the following identity: \[xy = \frac{1}{2}\bigl[(x+y)^2 – (x^2+y^2)\bigr].\]
Summing over all eight dominos in the tiling \(P\) yields the block-product sum: \[S_{\mathrm{prod}}(P) = \frac{1}{2} \sum\limits_{e\in M}(x_e+y_e)^2 – \frac{1}{2} \sum\limits_{j=1}^{16} n_j^2.\]
The second term on the right-hand side is the sum of squares of all cell values and is independent of the configuration; its value is \(1{,}496\).
Based on this relation, the sum of block-product sums over a rotation pair \((P, P^{90})\) becomes \[\begin{aligned} S_{\mathrm{prod}}(P) + S_{\mathrm{prod}}(P^{90}) &= \frac{1}{2} \left[ S_{\mathrm{sum}}^2(P) + S_{\mathrm{sum}}^2(P^{90}) \right] – 1{,}496. \end{aligned}\]
Referring to the constant \(C_2 = 5{,}848\) from Theorem 5.1 (the quadratic invariance of block sums), which was obtained by exhaustive verification, the expression simplifies to \[\frac{5{,}848}{2} – 1{,}496 = 2{,}924 – 1{,}496 = 1{,}428.\]
Thus, the algebraic computation in this subsection is in excellent agreement with the numerical verification results of Theorem 4.4.
This section examines the \(k\)-th power sum \(S_{\mathrm{sum}}^k(P)\) of the sums within each 2-block for a domino tiling \(P\) on the 4th-order Natural Square: \[S_{\mathrm{sum}}^k(P) = \sum\limits_{i=1}^{8} (x_i + y_i)^k,\] where \((x_i, y_i)\) denotes the pair of natural numbers covered by the \(i\)-th 2-block in the tiling \(P\).
We construct a complementary involution \[\sigma : \mathcal{P} \to \mathcal{P},\] that endows the set \(\mathcal{P}\) of 36 tilings with algebraic complementarity. Specifically, \(\sigma\) is defined by associating to each of the 36 patterns a partner such that the power sums for \(k=1,2,3\) satisfy the complementary condition. By this construction, \[\sigma^2 = \mathrm{id},\] and for each \(P \in \mathcal{P}\), the pair \((P, \sigma(P))\) forms an algebraic complementary pair. This involution is independent of rotational complementarity.
Under this involution, \(\mathcal{P}\) decomposes into 18 algebraic complementary pairs \((P, \sigma(P))\). For these pairs, the following complementary identities hold.
Theorem 5.1(Complementary identities for block sums up to the third power). For the complete set \(\mathcal{P}\) of domino tilings on the 4th-order Natural Square, the following holds for every \(k \in \{1,2,3\}\) and every \(P \in \mathcal{P}\): \[S_{\mathrm{sum}}^k(P) + S_{\mathrm{sum}}^k(\sigma(P)) = C_k,\] where \[C_1 = 272,\quad C_2 = 5{,}848,\quad C_3 = 141{,}032.\]
[Computational Verification] This theorem has been computationally confirmed by exhaustive enumeration of all 36 tiling patterns on the 4th-order Natural Square: the equality holds strictly for every pair.
In this section, the complementary identities for block sums up to the third power established in Theorem 5.1 are explicitly situated within the framework of Multigrade Chains [2], an extended form of the Prouhet–Tarry–Escott (PTE) problem in number theory.
First, we introduce the definitions necessary to describe the results of this study.
Definition 6.1(PTE problem).Given two distinct integer multisets \(A = \{a_1, \dots, a_n\}\) and \(B = \{b_1, \dots, b_n\}\) and a set of exponents \(\{k_1, k_2, \dots, k_s\}\), if \[\sum\limits_{i=1}^{n} a_i^k = \sum\limits_{i=1}^{n} b_i^k \qquad (k \in \{k_1, k_2, \dots, k_s\}), \tag{1}\] holds, then this is called a solution to the Prouhet–Tarry–Escott (PTE) problem. When consecutive exponents \(k = 1, 2, \dots, s\) are used, it is referred to as the standard PTE problem, and \(s\) is called its degree.
While the PTE problem typically concerns equalities between two multisets, its multiset generalization—where multiple multisets simultaneously share identical power sums—is studied under the name Multigrade Chains. Chen [2] comprehensively organizes various extensions and generalizations of the PTE problem.
Definition 6.2(Multigrade Chains).According to [2, p. 24], given a set of exponents \(\{k_1, k_2, \dots, k_s\}\), a collection of \(j\) integer multisets \(S_1, S_2, \dots, S_j\) satisfying \[^k = [S_2]^k = \cdots = [S_j]^k \qquad (k \in \{k_1, k_2, \dots, k_s\}), \tag{2}\] is called a Multigrade Chain. Here \([S]^k\) denotes the \(k\)-th power sum of the elements in multiset \(S\). The value \(j\) is called the length of the chain. The PTE problem corresponds to the special case where the length \(j = 2\).
We now formalize the objects treated in this study to fit the definition of Multigrade Chains.
Definition 6.3(Multiset of 2-block sums).For a tiling \(P \in \mathcal{P}\), the 8-element multiset whose elements are the sums of the values in each cell pair covered by the eight dominos is defined as \[X(P) = \{\, x_i + y_i \mid i = 1, \dots, 8 \,\}, \tag{3}\] where \((x_i, y_i)\) is the pair of values in the cells covered by the \(i\)-th domino.
| Pair | \(X(P_i)\) and \(X(P_j)\) | \(M(P_i, P_j)\) |
| (\(P_1, P_{36}\)) | \(X(P_1) = \{3,7,11,15,19,23,27,31\}\) | \(\{3,6,7,8,10,11,12,15,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{36}) = \{6,8,10,12,22,24,26,28\}\) | ||
| (\(P_2, P_{35}\)) | \(X(P_2) = \{3,7,11,15,19,26,27,28\}\) | \(\{3,6,7,8,10,11,12,15,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{35}) = \{6,8,10,12,22,23,24,31\}\) | ||
| (\(P_3, P_{34}\)) | \(X(P_3) = \{3,7,11,15,21,22,28,29\}\) | \(\{3,6,7,8,10,11,12,15,21^2,22^2,28^2,29^2\}\) |
| \(X(P_{34}) = \{6,8,10,12,21,22,28,29\}\) | ||
| (\(P_4, P_{33}\)) | \(X(P_4) = \{3,7,11,15,22,23,24,31\}\) | \(\{3,6,7,8,10,11,12,15,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{33}) = \{6,8,10,12,19,26,27,28\}\) | ||
| (\(P_5, P_{32}\)) | \(X(P_5) = \{3,7,11,15,22,24,26,28\}\) | \(\{3,6,7,8,10,11,12,15,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{32}) = \{6,8,10,12,19,23,27,31\}\) | ||
| (\(P_6, P_{31}\)) | \(X(P_6) = \{3,7,11,18,19,20,27,31\}\) | \(\{3,6,7^2,8,11,18^2,19,20^2,22,24,27,31^2\}\) |
| \(X(P_{31}) = \{6,7,8,18,20,22,24,31\}\) | ||
| (\(P_7, P_{17}\)) | \(X(P_7) = \{3,7,11,18,20,22,24,31\}\) | \(\{3^2,7,10,11,12,14,16,18,20,22,23,24,27,31^2\}\) |
| \(X(P_{17}) = \{3,10,12,14,16,23,27,31\}\) | ||
| (\(P_8, P_{24}\)) | \(X(P_8) = \{3,7,13,14,20,21,27,31\}\) | \(\{3,5,6,7,12,13,14,16,18,20,21,22,27,28,29,31\}\) |
| \(X(P_{24}) = \{5,6,12,16,18,22,28,29\}\) | ||
| (\(P_9, P_{18}\)) | \(X(P_9) = \{3,7,14,15,16,23,27,31\}\) | \(\{3^2,7,10,12,14^2,15,16^2,23,26,27^2,28,31\}\) |
| \(X(P_{18}) = \{3,10,12,14,16,26,27,28\}\) | ||
| (\(P_{10}, P_{30})\) | \(X(P_{10}) = \{3,7,14,15,16,26,27,28\}\) | \(\{3,6,7^2,8,14,15,16,18,19,20,26,27^2,28,31\}\) |
| \(X(P_{30}) = \{6,7,8,18,19,20,27,31\}\) | ||
| (\(P_{11}, P_{15}\)) | \(X(P_{11}) = \{3,7,14,16,18,20,27,31\}\) | \(\{3^2,7,10,11,12,14,16,18,20,22,23,24,27,31^2\}\) |
| \(X(P_{15}) = \{3,10,11,12,22,23,24,31\}\) | ||
| (\(P_{12}, P_{29}\)) | \(X(P_{12}) = \{3,10,11,12,19,23,27,31\}\) | \(\{3,6,7,8,10,11,12,15,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{29}) = \{6,7,8,15,22,24,26,28\}\) | ||
| (\(P_{13}, P_{28}\)) | \(X(P_{13}) = \{3,10,11,12,19,26,27,28\}\) | \(\{3,6,7,8,10,11,12,15,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{28}) = \{6,7,8,15,22,23,24,31\}\) | ||
| (\(P_{14}, P_{22}\)) | \(X(P_{14}) = \{3,10,11,12,21,22,28,29\}\) | \(\{3,5,6,10,11,12^2,13,21,22^2,23,24,28,29,31\}\) |
| \(X(P_{22}) = \{5,6,12,13,22,23,24,31\}\) | ||
| (\(P_{16}, P_{25}\)) | \(X(P_{16}) = \{3,10,11,12,22,24,26,28\}\) | \(\{3,6,7,8,10,11,12,15,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{25}) = \{6,7,8,15,19,23,27,31\}\) | ||
| (\(P_{19}, P_{23}\)) | \(X(P_{19}) = \{5,6,12,13,19,23,27,31\}\) | \(\{5^2,6^2,12^2,13^2,19,22,23,24,26,27,28,31\}\) |
| \(X(P_{23}) = \{5,6,12,13,22,24,26,28\}\) | ||
| (\(P_{20}, P_{27}\)) | \(X(P_{20}) = \{5,6,12,13,19,26,27,28\}\) | \(\{5,6^2,7,8,12,13,15,19,21,22,26,27,28^2,29\}\) |
| \(X(P_{27}) = \{6,7,8,15,21,22,28,29\}\) | ||
| (\(P_{21}, P_{26}\)) | \(X(P_{21}) = \{5,6,12,13,21,22,28,29\}\) | \(\{5,6^2,7,8,12,13,15,19,21,22,26,27,28^2,29\}\) |
| \(X(P_{26}) = \{6,7,8,15,19,26,27,28\}\) | ||
| Note: \(n^2\) indicates that element \(n\) has multiplicity 2. | ||
Definition 6.4(Sum-complementary multiset).When a pair \((P_i, P_j)\) satisfies \[S_{\mathrm{sum}}^k(P_i) + S_{\mathrm{sum}}^k(P_j) = C_k \quad (k = 1, 2, 3), \] the union \[M(P_i, P_j) = X(P_i) \cup X(P_j), \tag{4}\] of the two 8-element multisets generated by these tilings is called a sum-complementary multiset. This is a multiset with 16 elements. Note that the partition of pairs satisfying only the complementary conditions for \(S_{\mathrm{sum}}^k\) (\(k=1,2,3\)) into 18 groups is not unique in general. Concrete examples are shown in Table 3.
In each row, \(X(P_i)\) and \(X(P_j)\) are listed separately, and their union \(M(P_i, P_j)\) is written in multiset notation (\(n^2\) indicates that element \(n\) has multiplicity 2).
Close inspection of the 18 multisets in Table 3 reveals the following structural properties.
Observation 6.5(Number of distinct multisets). The 16-element multisets generated by the 18 pairs can be classified into 10 distinct multisets when compared as multisets (see Table 4).
| Group | Shared pairs | Characteristic of multiset |
| \(\alpha\) (7 pairs) | (\(P_1, P_{36}\)), (\(P_2, P_{35}\)), (\(P_4, P_{33}\)), | No repetitions (ordinary set) |
| (\(P_5, P_{32}\)), (\(P_{12}, P_{29}\)), (\(P_{13}, P_{28}\)), (\(P_{16}, P_{25}\)) | ||
| \(\beta\) (2 pairs) | (\(P_7, P_{17}\)), (\(P_{11}, P_{15}\)) | Repetitions of \(3^2\), \(31^2\) |
| \(\gamma\) (2 pairs) | (\(P_{20}, P_{27}\)), (\(P_{21}, P_{26}\)) | Repetitions of \(6^2\), \(28^2\) |
| Unique (7 pairs) | (\(P_3, P_{34}\)), (\(P_6, P_{31}\)), (\(P_8, P_{24}\)), | Each pair has a distinct multiset |
| (\(P_9, P_{18}\)), (\(P_{10}, P_{30}\)), (\(P_{14}, P_{22}\)), (\(P_{19}, P_{23}\)) |
Remark 6.6(Number-theoretic significance of identical multisets). The fact that different pairs generate the same 16-element multiset demonstrates that the distribution of 2-block sums can coincide even when the geometric configurations of the tilings differ. From the viewpoint of Multigrade Chains, this means that some of the 18 chain elements are equivalent as multisets; however, the complementary relations generating each pair are algebraically independent, and the distinction as tiling structures is preserved.
With the above preparations, the main result of this study is formalized as a theorem in the language of Multigrade Chains.
Theorem 6.7(Length-18 Multigrade Chain).The family of 16-element multisets \[\mathcal{M} = \bigl\{ M_s = M(P_{i_s}, P_{j_s}) \mid s = 1, \dots, 18 \bigr\},\] generated from the 18 sum-complementary pairs shown in Table 3 constitutes a Multigrade Chain of length \(j = 18\) and degree \(3\) with respect to the exponent set \(\{1, 2, 3\}\). That is, for every \(s \in \{1, \dots, 18\}\), \[\sum\limits_{z \in M_s} z^k = C_k \qquad (k = 1, 2, 3), \tag{5}\] holds, where the constants are \(C_1 = 272\), \(C_2 = 5{,}848\), \(C_3 = 141{,}032\). For \(k = 4\), the 18 multisets take 8 distinct values (see Table 5), so the equality does not hold. Thus, the chain is complete at degree 3 and breaks at degree 4.
| No. | Pair | \(\sum z^1\) | \(\sum z^2\) | \(\sum z^3\) | \(\sum z^4\) |
|---|---|---|---|---|---|
| 1 | (\(P_1, P_{36}\)) | 272 | 5,848 | 141,032 | 3,606,664 |
| 2 | (\(P_2, P_{35}\)) | 272 | 5,848 | 141,032 | 3,606,664 |
| 3 | (\(P_3, P_{34}\)) | 272 | 5,848 | 141,032 | 3,605,224 |
| 4 | (\(P_4, P_{33}\)) | 272 | 5,848 | 141,032 | 3,606,664 |
| 5 | (\(P_5, P_{32}\)) | 272 | 5,848 | 141,032 | 3,606,664 |
| 6 | (\(P_6, P_{31}\)) | 272 | 5,848 | 141,032 | 3,629,704 |
| 7 | (\(P_7, P_{17}\)) | 272 | 5,848 | 141,032 | 3,641,224 |
| 8 | (\(P_8, P_{24}\)) | 272 | 5,848 | 141,032 | 3,628,264 |
| 9 | (\(P_9, P_{18}\)) | 272 | 5,848 | 141,032 | 3,629,704 |
| 10 | (\(P_{10}, P_{30}\)) | 272 | 5,848 | 141,032 | 3,618,184 |
| 11 | (\(P_{11}, P_{15}\)) | 272 | 5,848 | 141,032 | 3,641,224 |
| 12 | (\(P_{12}, P_{29}\)) | 272 | 5,848 | 141,032 | 3,606,664 |
| 13 | (\(P_{13}, P_{28}\)) | 272 | 5,848 | 141,032 | 3,606,664 |
| 14 | (\(P_{14}, P_{22}\)) | 272 | 5,848 | 141,032 | 3,616,744 |
| 15 | (\(P_{16}, P_{25}\)) | 272 | 5,848 | 141,032 | 3,606,664 |
| 16 | (\(P_{19}, P_{23}\)) | 272 | 5,848 | 141,032 | 3,605,224 |
| 17 | (\(P_{20}, P_{27}\)) | 272 | 5,848 | 141,032 | 3,593,704 |
| 18 | (\(P_{21}, P_{26}\)) | 272 | 5,848 | 141,032 | 3,593,704 |
| Equality check | ✓ | ✓ | ✓ | \(\times\) (8 distinct values) |
Proof. This theorem is established by exhaustively computing the power sums for \(k = 1, 2, 3, 4\) over the elements of each of the 18 multisets \(M_s\) (\(s = 1, \dots, 18\)) explicitly given in Table 3. By definition, \[\sum\limits_{z \in M(P_i, P_j)} z^k = S_{\mathrm{sum}}^k(P_i) + S_{\mathrm{sum}}^k(P_j),\] holds, so the right-hand side was computed directly for each pair. For all 18 pairs, the equalities \(S_{\mathrm{sum}}^k(P_i) + S_{\mathrm{sum}}^k(P_j) = C_k\) hold strictly at \(k=1,2,3\), while at \(k=4\) eight distinct values are obtained (Table 5). The program used for verification is publicly available in reproducible form in the repository cited in Section 2.1. ◻
Remark 6.8(Interpretation as a PTE solution).Usually the PTE problem focuses on comparing two sets, but the novelty of this study lies in the fact that, starting from a specific geometric structure (patterns of domino tilings), a “chain” naturally emerges in which as many as 18 multisets are mutually PTE-equivalent.
Up to the previous section, two patterns of partitioning the entire set of 36 domino tilings into 18 algebraic complementary pairs were confirmed. In this section, we newly introduce the concept of an algebraic perfect complementary partition.
Definition 7.1(Algebraic Perfect Complementary Partition).Consider partitioning the set \(\mathcal{P}\) of all 36 domino tilings into 18 pairwise disjoint pairs \(\{(P_{i_s}, P_{j_s})\}_{s=1}^{18}\). If every pair simultaneously satisfies the following four complementary identities, then such a partition is called an algebraic perfect complementary partition:
1. \(S_{\mathrm{sum}}^1(P_{i_s}) + S_{\mathrm{sum}}^1(P_{j_s}) = 272\)
2. \(S_{\mathrm{sum}}^2(P_{i_s}) + S_{\mathrm{sum}}^2(P_{j_s}) = 5{,}848\)
3. \(S_{\mathrm{sum}}^3(P_{i_s}) + S_{\mathrm{sum}}^3(P_{j_s}) = 141{,}032\)
4. \(S_{\mathrm{prod}}(P_{i_s}) + S_{\mathrm{prod}}(P_{j_s}) = 1{,}428\)
Exhaustive verification using the program Calculator 4 revealed the following important fact.
Proposition 7.2(Non-uniqueness of the partition).In the set \(\mathcal{P}\) of domino tilings on the 4th-order Natural Square, the algebraic perfect complementary partition is not unique. Specifically, the “Partition 1⃝” presented in this paper (Table 6) and “Partition 2⃝” (Table 3) both fully satisfy all four complementary identities across their 18 pairs, even though some of the paired members differ.
| Pair \(P_i, \sigma(P_i))\) | \(C_1\) \((k=1)\) | \(C_2\) \((k=2)\) | \(C_3\) \((k=3)\) | \(S_\mathrm{sum}^4\) pair sum | \(S_\mathrm{sum}^4\) Group |
| \(P_3\)-\(P_{34}, P_{19}\)-\(P_{23}, P_{14}\)-\(P_{27}, P_{20}\)-\(P_{22}\) | 272 | 5,848 | 141,032 | 3,605,224 | A |
| \(P_1\)-\(P_{36}, P_{15}\)-\(P_{26}, P_5\)-\(P_{32}, P_{13}\)-\(P_{28},\) | 272 | 5,848 | 141,032 | 3,606,664 | B |
| \(P_2\)-\(P_{35}, P_4\)-\(P_{33}, P_{12}\)-\(P_{29}, P_{16}\)-\(P_{25}\) | |||||
| \(P_8\)-\(P_{24}, P_{11}\)-\(P_{21}\) | 272 | 5,848 | 141,032 | 3,628,264 | C |
| \(P_9\)-\(P_{18}, P_6\)-\(P_{31}, P_7\)-\(P_{30}, P_{10}\)-\(P_{17}\) | 272 | 5,848 | 141,032 | 3,629,704 | D |
This numerical result demonstrates, as shown in Table 7 below, that even when specific patterns are paired with different partners, their sums converge to the same invariants.
| Target pattern | Pair in partition ① | Pair in partition ② |
|---|---|---|
| \(P_7\) | \((P_7, P_{30})\) | \((P_7, P_{17})\) |
| \(P_{10}\) | \((P_{10}, P_{17})\) | \((P_{10}, P_{30})\) |
| \(P_{14}\) | \((P_{14}, P_{27})\) | \((P_{14}, P_{22})\) |
| \(P_{20}\) | \((P_{20}, P_{22})\) | \((P_{20}, P_{27})\) |
While the previous subsection demonstrated the non-uniqueness of the partition, the next natural question is: how many such partitions exist in total? This subsection provides a complete answer to that question.
The total number of perfect matchings among the 36 patterns is \(35!! \approx 2.2 \times 10^{20}\), making full brute-force enumeration computationally infeasible. However, the problem can be drastically reduced using the following two-stage approach:
1. Preliminary enumeration of valid pairs: Inspect all \(\binom{36}{2} = 630\) possible pairs against the four conditions and extract only those valid pairs that satisfy them all. This step completes in \(O(630)\) time.
2. Enumeration of perfect matchings on the valid-pair graph: Construct a graph whose edges are the valid pairs, and recursively enumerate all perfect matchings in that graph. Since the number of valid pairs is small, the search space remains extremely manageable.
Exhaustive inspection shows that only 26 pairs out of the \(\binom{36}{2} = 630\) possible pairs satisfy all four conditions. Analysis of the number of partners per pattern reveals that 24 patterns have exactly one partner each, meaning their mates are fixed in every partition (fixed pairs). The remaining 12 patterns have multiple possible partners, giving rise to the degrees of freedom in the partition.
Observation 7.3(Subgraph structure of the valid-pair graph).The 12 patterns with freedom form the following three disjoint subgraphs:
1. \(\{P_{11}, P_{15}, P_{21}, P_{26}\}\): All \(\binom{4}{2} = 6\) possible pairs among the four vertices are valid, forming a complete graph \(K_4\). The number of perfect matchings in \(K_4\) is 3.
2. \(\{P_7, P_{10}, P_{17}, P_{30}\}\): This forms a complete bipartite graph \(K_{2,2}\) with bipartition \(\{P_7, P_{10}\}\) and \(\{P_{17}, P_{30}\}\) (valid pairs: \((P_7,P_{17})\), \((P_7,P_{30})\), \((P_{10},P_{17})\), \((P_{10},P_{30})\)). The number of perfect matchings in \(K_{2,2}\) is 2.
3. \(\{P_{14}, P_{20}, P_{22}, P_{27}\}\): This forms another complete bipartite graph \(K_{2,2}\) with bipartition \(\{P_{14}, P_{20}\}\) and \(\{P_{22}, P_{27}\}\) (valid pairs: \((P_{14},P_{22})\), \((P_{14},P_{27})\), \((P_{20},P_{22})\), \((P_{20},P_{27})\)). The number of perfect matchings is 2.
These three subgraphs are pairwise disjoint (no common vertices), so choices within each are independent.
Theorem 7.4(Total number of algebraic perfect complementary partitions). The total number of algebraic perfect complementary partitions of the set \(\mathcal{P}\) of domino tilings on the 4th-order Natural Square is exactly 12.
\[\text{Total number of partitions} = 3 \times 2 \times 2 = 12. \tag{6}\]
Each factor corresponds to the number of perfect matchings in one of the three subgraphs identified in Observation 7.3.
Proof. The proof proceeds in two steps.
(Upper bound) From the subgraph structure of the valid-pair graph (Observation 7.3), the three subgraphs with freedom each admit 3, 2, and 2 perfect matchings, respectively, and these choices are independent. The 12 fixed pairs are common to every partition. Hence the total number of partitions is at most \(3 \times 2 \times 2 = 12\).
(Lower bound and complete enumeration) Recursive exhaustive
search for perfect matchings on the valid-pair graph, implemented in the
program enumerate_all_partitions.py, confirms that exactly
12 such partitions exist. Each partition was individually verified to
satisfy all four conditions. The results are presented in Table 8. ◻
| Partition No. | Free pairs (6 pairs) | Note |
| 1 | \((P_7,P_{17}),\,(P_{10},P_{30}),\,(P_{11},P_{15}),\,(P_{14},P_{22}),\,(P_{20},P_{27}),\,(P_{21},P_{26})\) | |
| 2 | \((P_7,P_{17}),\,(P_{10},P_{30}),\,(P_{11},P_{15}),\,(P_{14},P_{27}),\,(P_{20},P_{22}),\,(P_{21},P_{26})\) | |
| 3 | \((P_7,P_{17}),\,(P_{10},P_{30}),\,(P_{11},P_{21}),\,(P_{14},P_{22}),\,(P_{15},P_{26}),\,(P_{20},P_{27})\) | \(=\) Partition ② |
| 4 | \((P_7,P_{17}),\,(P_{10},P_{30}),\,(P_{11},P_{21}),\,(P_{14},P_{27}),\,(P_{15},P_{26}),\,(P_{20},P_{22})\) | |
| 5 | \((P_7,P_{17}),\,(P_{10},P_{30}),\,(P_{11},P_{26}),\,(P_{14},P_{22}),\,(P_{15},P_{21}),\,(P_{20},P_{27})\) | |
| 6 | \((P_7,P_{17}),\,(P_{10},P_{30}),\,(P_{11},P_{26}),\,(P_{14},P_{27}),\,(P_{15},P_{21}),\,(P_{20},P_{22})\) | |
| 7 | \((P_7,P_{30}),\,(P_{10},P_{17}),\,(P_{11},P_{15}),\,(P_{14},P_{22}),\,(P_{20},P_{27}),\,(P_{21},P_{26})\) | |
| 8 | \((P_7,P_{30}),\,(P_{10},P_{17}),\,(P_{11},P_{15}),\,(P_{14},P_{27}),\,(P_{20},P_{22}),\,(P_{21},P_{26})\) | |
| 9 | \((P_7,P_{30}),\,(P_{10},P_{17}),\,(P_{11},P_{21}),\,(P_{14},P_{22}),\,(P_{15},P_{26}),\,(P_{20},P_{27})\) | |
| 10 | \((P_7,P_{30}),\,(P_{10},P_{17}),\,(P_{11},P_{21}),\,(P_{14},P_{27}),\,(P_{15},P_{26}),\,(P_{20},P_{22})\) | |
| 11 | \((P_7,P_{30}),\,(P_{10},P_{17}),\,(P_{11},P_{26}),\,(P_{14},P_{22}),\,(P_{15},P_{21}),\,(P_{20},P_{27})\) | \(=\) Partition ① |
| 12 | \((P_7,P_{30}),\,(P_{10},P_{17}),\,(P_{11},P_{26}),\,(P_{14},P_{27}),\,(P_{15},P_{21}),\,(P_{20},P_{22})\) | |
| Fixed pairs (common to all partitions): \((P_1,P_{36}),\,(P_2,P_{35}),\,(P_3,P_{34}),\,(P_4,P_{33}),\,(P_5,P_{32}),\,(P_6,P_{31}),\) | ||
| \((P_8,P_{24}),\,(P_9,P_{18}),\,(P_{12},P_{29}),\,(P_{13},P_{28}),\,(P_{16},P_{25}),\,(P_{19},P_{23})\) | ||
Remark 7.5. Theorem 7.4 not only shows that the partition is non-unique, but also fully reveals the structure of this non-uniqueness. Specifically, the degrees of freedom are localized exclusively to three particular subgraphs (one \(K_4\) and two \(K_{2,2}\)), while the pairings of the remaining 28 patterns remain unchanged across all partitions.
Remark 7.6(Relation to the algebraic centroid \(\{P_{11}, P_{15}, P_{21}, P_{26}\}\)). Remarkably, the four patterns \(\{P_{11}, P_{15}, P_{21}, P_{26}\}\) that form the \(K_4\) exactly coincide with the “algebraic centroid” described in Section 3—the four patterns whose moments for \(k=1,2,3\) all match the overall set means. These four patterns form algebraic perfect complementary pairs that are freely interchangeable with one another. Theoretical clarification of this correspondence remains a future task.
In the preceding discussion, Definition 7.1 enumerated four complementary identities independently. This subsection scrutinizes the algebraic independence of these four conditions and shows that there are in fact only two essential independent constraints.
Proposition 7.7(Universal constancy of \(S_{\mathrm{sum}}^1\).For every domino tiling \(P \in \mathcal{P}\), \(S_{\mathrm{sum}}^1(P) = 136\) holds. Therefore, Condition 1 (the complementary identity for \(S_{\mathrm{sum}}^1\)) holds automatically for any pair \((P_i, P_j)\) and does not act as a constraint.
Proof.Since \(S_{\mathrm{sum}}^1(P) = \sum\limits_{d \in P} (x_d + y_d)\) and the tiling \(P\) is a perfect cover of \(V = \{1, 2, \dots, 16\}\), each cell value appears exactly once. Thus \(S_{\mathrm{sum}}^1(P) = \sum\limits_{n=1}^{16} n = 136\), which is constant regardless of the choice of tiling \(P\). ◻
Proposition 7.8(Dependence of \(S_{\mathrm{prod}}\) on \(S_{\mathrm{sum}}^2\)). For every domino tiling \(P \in \mathcal{P}\), the following identity holds: \[S_{\mathrm{prod}}(P) = \frac{S_{\mathrm{sum}}^2(P) – \Sigma_2}{2}, \label{eq:prod-from-s2} \tag{7}\] where \(\Sigma_2 = \sum\limits_{n=1}^{16} n^2 = 1{,}496\) is the sum of squares of all cell values in the Natural Square (a configuration-independent constant).
Proof. For any domino covering cells with values \(x, y\), the elementary identity \[xy = \frac{(x+y)^2 – (x^2 + y^2)}{2},\] holds. Summing over all eight dominos in tiling \(P\) gives \[S_{\mathrm{prod}}(P) = \frac{1}{2}\sum\limits_{d \in P}(x_d+y_d)^2 – \frac{1}{2}\sum\limits_{d \in P}(x_d^2+y_d^2).\]
The first term on the right is \(\frac{1}{2}S_{\mathrm{sum}}^2(P)\), and the second term equals \(\sum\limits_{n=1}^{16} n^2 = \Sigma_2 = 1{,}496\) for the same reason as in Proposition 7.7. Thus Eq. (7) holds. ◻
Corollary 7.9(Derivation of the \(S_{\mathrm{prod}}\) complementary condition from the \(S_{\mathrm{sum}}^2\) condition).If a pair \((P_i, P_j)\) satisfies the complementary condition for \(S_{\mathrm{sum}}^2\), namely \(S_{\mathrm{sum}}^2(P_i) + S_{\mathrm{sum}}^2(P_j) = C_2 = 5{,}848\), then the complementary condition for \(S_{\mathrm{prod}}\), \(S_{\mathrm{prod}}(P_i) + S_{\mathrm{prod}}(P_j) = C_{\mathrm{prod}} = 1{,}428\), holds automatically. The converse also holds. Thus the two conditions are equivalent.
Proof. From Proposition 7.8, \[\begin{aligned} S_{\mathrm{prod}}(P_i) + S_{\mathrm{prod}}(P_j) &= \frac{S_{\mathrm{sum}}^2(P_i) + S_{\mathrm{sum}}^2(P_j) – 2\Sigma_2}{2} = \frac{C_2 – 2 \times 1{,}496}{2} = \frac{5{,}848 – 2{,}992}{2}\\ &= 1{,}428 = C_{\mathrm{prod}}. \end{aligned}\]
In the reverse direction, rearranging Eq. (7) gives \(S_{\mathrm{sum}}^2(P) = 2\,S_{\mathrm{prod}}(P) + \Sigma_2\), so \[S_{\mathrm{sum}}^2(P_i) + S_{\mathrm{sum}}^2(P_j) = 2\bigl(S_{\mathrm{prod}}(P_i)+S_{\mathrm{prod}}(P_j)\bigr) + 2\Sigma_2 = 2 \times 1{,}428 + 2 \times 1{,}496 = 5{,}848 = C_2.\] ◻
Theorem 7.10(Essential independence and equivalence of the four conditions).Among the four conditions in Definition 7.1, the essential independent constraints are only Conditions 2 (\(S_{\mathrm{sum}}^2\)) and 3 (\(S_{\mathrm{sum}}^3\)); specifically:
1. Condition 1 (\(S_{\mathrm{sum}}^1\)) holds automatically for any pair and does not function as a constraint (Proposition 7.7).
2. Condition 4 (\(S_{\mathrm{prod}}\)) is equivalent to Condition 2 (\(S_{\mathrm{sum}}^2\)) and is not an independent constraint (Corollary 7.9).
3. The number of valid pairs satisfying Conditions 2 and 3 simultaneously is 26, which exactly matches the number obtained when all four conditions are imposed.
Consequently, the notions of “algebraic complementary partition” (Conditions 2 and 3 only) and “algebraic perfect complementary partition” (Conditions 1–4) are completely identical, and both have exactly 12 partitions in total.
Proof. Claims 1 and 2 are already proved algebraically in
Proposition 7.7 and
Corollary 7.9,
respectively. For Claim 3, exhaustive inspection of all \(\binom{36}{2} = 630\) pairs (using the
program enumerate_all_partitions.py) confirms that exactly
26 pairs satisfy the two conditions \(S_{\mathrm{sum}}^2 + S_{\mathrm{sum}}^3\),
which coincides perfectly with the count under all four
conditions. ◻
Remark 7.11(Significance of explicitly including \(S_{\mathrm{prod}}\) in the definition).Although Theorem 7.10 shows that the \(S_{\mathrm{prod}}\) condition is derivable from the \(S_{\mathrm{sum}}^2\) condition, it is explicitly stated in the definition of this paper. The reason is that the fact \(S_{\mathrm{prod}}\) generates the same invariant \(C_{\mathrm{prod}} = 1{,}428\) as the geometric 90-degree rotation complement theorem (Theorem 4.4) carries independent number-theoretic significance and highlights the surprising coincidence between geometric and algebraic operations.
Remark 7.12(On partitions other than the 12).Combining Theorems 7.10 and 7.4, among all ways to partition the 36 patterns into 18 pairs, only 12 satisfy the complementary conditions for \(S_{\mathrm{sum}}^2\) and \(S_{\mathrm{sum}}^3\) across every pair. All other partitions (of which there are vastly many) fail the \(S_{\mathrm{sum}}^2\) condition (and hence also the \(S_{\mathrm{prod}}\) condition) in at least one pair. Thus no intermediate category exists in which \(S_{\mathrm{sum}}^k\) (\(k=1,2,3\)) holds but \(S_{\mathrm{prod}}\) does not.
The following three points are proposed as future challenges.
The results of this study were obtained for the \(4\times4\) grid (\(n=4\)). It is of great importance to verify whether this algebraic symmetry holds universally also in higher-order \(n\times n\) Natural Squares.
1. Verification of a generalized rotation complement theorem: Examine whether the block-product sum identity \(S_{\mathrm{prod}}(P) + S_{\mathrm{prod}}(P^{\theta}) = C_{\mathrm{prod}}(n)\) (where \(\theta\) is a 90-degree or 180-degree rotation) holds for even-order grids such as \(n=6, 8, \dots\). Investigate whether the constant \(C_{\mathrm{prod}}(n)\) can be described as a polynomial in \(n\).
2. Investigation of the limiting degree for which identities hold: Describe how the maximum degree \(k_{\max}\) up to which the power-sum identities \(S_{\mathrm{sum}}^k(P)\) are preserved changes as the grid size \(n\) increases (for example, while \(k=3\) was the limit for \(n=4\), how far does it extend for \(n=6\)?).
3. Multiplicity of algebraic perfect complementary partitions: Clarify whether the “algebraic perfect complementary partition” defined in this study exists for grids with \(n \ge 6\), and how its multiplicity (the non-unique structure such as 12 ways) changes.
The main conclusions of this study (the block-product sum complement theorem and the algebraic complementary identities) were derived through exhaustive numerical verification over all 36 patterns. Providing rigorous proofs of these results via number-theoretic or group-theoretic approaches that do not depend on the special case of the \(4\times4\) grid is the highest-priority task. In particular, deepening the connection with the PTE problem is desired in order to elucidate the mechanism by which geometric constraints of tilings enforce the preservation of power sums.
By focusing on tiling units other than dominos and on higher-order moments, we aim to approach the essence of the algebraic symmetry.
1. Application to tromino tilings and the like: Explore the conditions under which analogous algebraic identities are induced when using blocks of different shapes, such as \(1\times3\) blocks (trominoes) for lattice coverings.
2. Geometric interpretation of higher-order moments: Visualize and describe what kind of “bias” in the geometric structure of the tiling is being canceled by the preservation of third-order, fourth-order, and higher moments.
Through this research, it is expected that the domino tiling problem will serve not merely as a problem in combinatorics, but as an important model case for elucidating the solution structure of multigraded equality problems under geometric constraints.
The Python programs developed to verify all theorems and numerical results presented in this paper are publicly available in the following GitHub repository. To ensure reproducibility and transparency of the research, the following six programs (Program 0 to Program 5) are provided.
1. Program 0 (calculator0_symmetry_check.py): Computes the number of fixed points \(|Fix(g)|\) under the action of the dihedral group \(D_4\) for all 36 patterns of 4th-order Natural Square domino tilings. Verifies, based on Burnside’s lemma, that the tiling space is classified into 9 families (equivalence classes).
2. Program 1 (Domino Tiling Calculator1.py): Verifies the invariance of the block-product sum in rotational complementary pairs (always equal to 1,428).
3. Program 2 (Domino Tiling Calculator2.py): Verifies that the pair sums of block-sum power sums (\(S_{\mathrm{sum}}^k\), \(k=1,2,3\)) for algebraic complementary pairs take constant values independent of tiling shape.
4. Program 3 (Domino Tiling Calculator3.py): Computes properties of the squared block-product sums and higher-order moment aggregations for algebraic complementary pairs. Note: The analyses conducted by this program are not directly referenced in the main results of the present paper, but are retained in the repository as supplementary reference material for potential future investigations (see Section 8).
5. Program 4 (Domino Tiling Calculator4.py): Integratively verifies the configuration that partitions all 36 patterns into 18 algebraic perfect complementary pairs based on extended higher-degree complementary identities.
6. Program 5 (enumerate_all_partitions.py): Complete enumeration algorithm for algebraic perfect complementary partitions. Performs a graph-theoretic search (decomposition into one complete graph \(K_4\) and two complete bipartite graphs \(K_{2,2}\)) of perfect matchings among the 36 patterns, demonstrating that the total number of partitions is exactly 12.
GitHub Repository URL: https://github.com/soaisu-ken/DominoTilingSymmetries4x4/releases/tag/v1.3.0.
Readers can reproduce all theorems and numerical verification results presented in this paper by executing the provided source code.
This research was conducted entirely at the author’s own expense and with personal funds as an independent researcher. No funding was received from any external organization, public institution, or commercial entity for the conduct of the research, analysis, or preparation of this paper.
The author of this research has no financial or non-financial conflicts of interest to disclose. There are no commercial, personal, or other relationships that could potentially influence the interpretation of results or the writing of this paper.
During the preparation of this paper, Google’s generative AI model Gemini (free version) was utilized.
The specific purposes for which AI was used are as follows:
1. Translation of the paper content into English and polishing of English expressions.
2. Creation of initial drafts of Python code for data verification and analysis (Programs 1–4).
3. Adjustment of document formatting for components of the paper (e.g., LaTeX code, README files).
AI was not used for constructing the core mathematical theory of this research, designing algorithms, performing numerical analysis, or interpreting results. All text and code generated by AI were verified for accuracy and consistency by the author and underwent substantial revision and addition.