The 1/4-phenomenon of placement probabilities of tilings in the Aztec diamond

Technical Summary: The 1/4-Phenomenon of Placement Probabilities of Tilings in the Aztec Diamond

Problem Statement
This paper investigates the placement probabilities of domino tilings within the Aztec diamond of size $n$. Specifically, it seeks to determine the exact probability $\mathbb{P}(l, m; n)$ of observing a horizontal domino tile at a specific coordinate $(l, m)$ in a uniformly random tiling. While previous work by Cohn, Elkies, and Propp (2002) established asymptotic behaviors and explicit formulas involving products of Kravchuk polynomials, these expressions are complex and cumbersome for applications requiring exact values at fixed positions. The paper aims to uncover a simpler structural form for these probabilities and apply this structure to enumerate tilings of Aztec diamonds containing $2 \times 2$ square holes.

Methodology
The author employs the Domino Shuffling algorithm (Elkies, Kuperberg, Larsen, and Propp, 1992) as the primary tool for generating random tilings and analyzing their properties. The methodology proceeds through several key analytical steps:

1. Creation Rates: The paper utilizes the "creation rate" $Cr(l, m; n)$, defined as $2(\mathbb{P}(l, m; n) - \mathbb{P}(l, m-1; n-1))$. This quantity, which arises naturally from the Domino Shuffling algorithm, is known to be expressible via products of Kravchuk polynomials.
2. Growth Theorem for Kravchuk Polynomials: A central technical contribution is the proof of a growth theorem for Kravchuk polynomials. The author demonstrates that for specific parameter shifts related to the size of the diamond ($n = 4p + \alpha$), these polynomials grow in a manner that factors out a universal term involving binomial coefficients, leaving a rational function. This is proven by reducing the general case to a finite set of base cases using symmetry relations and three-term recurrence formulas.
3. Recursive Reduction: The proof of the main result is structured by reducing the problem from arbitrary positions $(l, m)$ to the horizontal axis ($m=0$), and subsequently to the origin $(0,0)$. This reduction relies on the symmetry of the Aztec diamond and the relationship between placement probabilities and creation rates.
4. Kuo Condensation: To establish the exact formulas for the placement probabilities at the origin (specifically for sizes $4p+1$ and $4p+3$), the paper applies Kuo condensation (a combinatorial identity for perfect matchings on planar graphs). This allows the author to relate the number of tilings of a region with a hole to the number of tilings of the full region and sub-regions with specific edges removed.

Key Contributions and Results

• The 1/4-Phenomenon (Theorem 1.1): The primary result establishes that the placement probability $\mathbb{P}(l, m; 4p+\alpha)$ for a horizontal domino with a black left square is always of the form:
  $$\mathbb{P}(l, m; 4p+\alpha) = \frac{1}{4} + 2^{-4p-\alpha} \binom{2p-1}{p}^2 f_{l,m,\alpha}(p)$$
  where $f_{l,m,\alpha}(p)$ is a rational function in $p$. The term $1/4$ represents an almost symmetric baseline, while the second term captures the deviation based on the specific location and the size of the diamond. If $l+m \not\equiv \alpha+1 \pmod 2$, the probability is zero.
• Rational Function Structure (Theorem 1.2): The paper provides bounds on the degrees of the numerator and denominator polynomials of the rational function $f_{l,m,\alpha}(p)$. It suggests that these degrees are bounded linearly by the distance of the position $(l, m)$ from the origin, facilitating the computation of these functions via polynomial interpolation.
• Explicit Formulas for Holey Aztec Diamonds (Section 6): As a direct application of the main theorem, the author derives explicit counting formulas for the number of domino tilings of an Aztec diamond with a $2 \times 2$ square hole at an arbitrary position $(l, m)$. This complements previous results by Mihai Ciucu, which covered holes in diamonds of size $4p+2$ and $4p+3$, by providing formulas for sizes $4p$ and $4p+1$.
• Asymptotic Behavior (Section 5): The paper confirms that for any fixed position $(l, m)$, the placement probability converges to $1/4$ as the size of the diamond tends to infinity, consistent with the "arctic circle" phenomenon where the interior of the diamond exhibits uniform randomness.

Significance and Claims
The paper claims that the derived structural result leads to "significantly more compact explicit counting formulas" compared to previous findings involving Kravchuk polynomials. By isolating the rational function component, the author provides a more tractable framework for calculating exact probabilities and enumeration numbers. The work serves as a complement to existing literature on dimer models and perfect matchings, offering a unified structural perspective on the placement probabilities in Aztec diamonds. The author notes that while the rational functions become increasingly complex with distance from the origin, the existence of a closed-form structure (a constant plus a scaled rational function) is the fundamental insight. The results are presented as rigorous proofs derived from established combinatorial algorithms and identities, without proposing new experimental applications or future research directions beyond the immediate scope of the derived formulas.