Abstract
We study the configuration spaces $C(n;p,q)$ of $n$ labeled hard squares in a $p$ by $q$ rectangle, a generalization of the well-known 15 Puzzle. Our main interest is in the topology of these spaces. Our first result is to describe a cubical cell complex and prove that is homotopy equivalent to the configuration space. We then focus on determining for which $n, j, p,$ and $q$ the homology group $H_j [ C(n;p,q) ]$ is nontrivial. We prove three homology-vanishing theorems, based on discrete Morse theory on the cell complex. Then we describe several explicit families of nontrivial cycles, and a method for interpolating between parameters to fill in most of the picture for large-scale nontrivial homology.
Introduction
The "15 Puzzle" is a classic $4 \times 4$ grid with 15 sliding tiles. While typically viewed as a discrete graph of permutations, allowing the squares to slide continuously within a rectangle transforms the problem into a study of configuration spaces. These spaces are high-dimensional and difficult to visualize, yet their topology—specifically their homology groups—reveals fundamental constraints on how physical objects can rearrange themselves. This research bridges the gap between discrete puzzles and the statistical mechanics of hard-sphere systems.
Topological Modeling and Methods
To analyze these continuous spaces, the authors demonstrate that the configuration space is homotopy equivalent to a simpler, finite cubical cell complex. This discrete representation allows for the application of advanced topological tools:
- Discrete Morse Theory: By defining a discrete gradient vector field based on the "apex" (upper-right corner) of squares, the authors "collapse" the complex to its essential features. This facilitates the proof of vanishing theorems, identifying regions where no homology can exist.
- Cycle Construction: To prove the existence of "holes" (nontrivial homology), the authors describe specific configurations where squares orbit one another. These local interactions form the basis for nontrivial cycles.
The Homological Landscape
The research categorizes the configuration space into three physical regimes:
- Solid: High density prevents interesting movement, leading to vanishing homology.
- Gas: Low density allows squares to behave like points, with well-understood topology.
- Liquid: An intermediate zone where crowding leads to complex, high-dimensional homology.
A central result is the mapping of "homological density." By plotting the density $x = n/pq$ against the dimension ratio $y = j/pq$, the authors visualize the regions where nontrivial homology persists.
The authors proved that for any rational point within the blue region (roughly bounded by $y = x - (8/9)x^2$), there exists a configuration with nontrivial homology.
Conclusion and Future Directions
This work provides a large-scale map of the topology of hard squares. However, the precise boundaries between the solid, liquid, and gas regimes remain a subject of conjecture. Future research will focus on more efficient computational algorithms to explore systems with more than six squares and to further investigate the transition between the homological "liquid" and "gas" states.
Summary updated