q-RSK Sampling of Domino Tilings of the Aztec Diamond domino-tilings

Leonid Petrov

Simulation Info

q-RSK Sampling of Domino Tilings of the Aztec Diamond domino-tilings

Leonid Petrov

About the Simulation

q-RSK Sampling generates random domino tilings of the Aztec diamond using the q-deformed Robinson-Schensted-Knuth correspondence. At q=0, this gives uniform tilings; as q approaches 1, tilings concentrate near "frozen" configurations.

Parameters:

n: Size of the Aztec diamond
q: q-Whittaker parameter (0 ≤ q < 1). q=0 gives Schur measure; q>0 gives q-Whittaker measure
x, y: Schur process specialization. Uniform (all 1s) gives standard measure; other weights create non-uniform sampling
High precision: Uses 50-digit arithmetic (slower but stable for q close to 1)

The simulation outputs interlacing partitions that encode the domino tiling.

Visualization Modes:

Dominoes: Standard flat tiling view with four colors for domino types.
Dimer: Displays the underlying matching on the dual graph as edges.
Double Dimer: Superimposes two independent samples to form loops. Includes a Min Loop Size filter.
Fluctuations: Visualizes height difference between two samples, approximating the Gaussian Free Field.
3D: Renders the tiling as a stepped surface in 3D space. Supports rotation, perspective/orthographic toggle, and multiple visual presets.

View Options:

Rotate 45°: Rotate the canvas view for alternative perspective.
Particles: Show lattice points forming the Schur/q-Whittaker process.
Color Palettes: Multiple palettes plus custom color pickers.
Canvas/SVG: Toggle between renderers.

Export: PNG and PDF export with adjustable quality.

References:

arXiv:1504.00666 — K. Matveev, L. Petrov, q-randomized Robinson-Schensted-Knuth correspondences and random polymers
arXiv:1407.3764 — D. Betea et al., Perfect sampling algorithms for Schur processes

Skip to simulation canvas

n = q = High precision

$x_i=y_i=r^i$: r = Syntax: 1^4 = 1,1,1,1

Q: 85

View: Dominoes Dimer Loops≥

Rotate 45° Particles Border: 1 Frozen curves: q→1 triangle finite-q arc [?]

Frozen-curve formulas (black = q→1 triangle, red = finite-q arc)

Coordinates. In the rotated unit-square chart $(u,v) = \left(\frac{hx+hy+R}{2R}, \frac{hx-hy+R}{2R}\right)$ of the Aztec diamond $|hx|+|hy|\le R$, with $R = N + \tfrac12$, set $\kappa = \mathbf m$ and $c = -\mathbf x$. The finite-q arc is plotted after the $x = y$ reflection $(\kappa, c)\mapsto (\kappa, 1-c)$ (equivalently $hx\leftrightarrow hy$) so that it hugs the south (yellow) frozen lobe; the q→1 triangle is drawn after the antipodal flip $(\kappa, c)\mapsto (1-\kappa, 1-c)$ so it lands on the same half as the visible frozen lobe.

q→1 triangle (eq. (x9) of Aztec_sym_Vadim.tex): in the $t\to 1$ limit, particles at section $\kappa$ fill the interval $$ c \in \bigl[\,p(1-\kappa),\; p(1-\kappa) + \kappa\,\bigr], \qquad p = \frac{\alpha\beta}{1+\alpha\beta}. $$ Two edges $u_L(\kappa) = p(1-\kappa)$ and $u_R(\kappa) = p(1-\kappa)+\kappa$ sweep the triangle.

Finite-q arc (q-Whittaker arctic curve, double saddle of the exponent in section 5 of Aztec_sym_Vadim.tex, specialised to $a_i=\alpha$, $b_j=\beta$): $$f(w) = \kappa \log (w/\alpha;\,q)_\infty + (1-\kappa)\log(1+w\beta) - c\log w.$$ Solving $f'(w)=f''(w)=0$ for $(\kappa, c)$: $$\kappa(w) = \frac{\alpha\beta}{\alpha\beta + \bigl(S_1 + \tfrac{w}{\alpha}\,S_2\bigr)(1+w\beta)^2},\qquad c(w) = (1-\kappa)\,\frac{w\beta}{1+w\beta} - \kappa\,\frac{w}{\alpha}\, S_1,$$ $$S_1 = \sum_{k\ge 0} \frac{q^k}{1 - (w/\alpha) q^k},\qquad S_2 = \sum_{k\ge 0} \frac{q^{2k}}{\bigl(1 - (w/\alpha) q^k\bigr)^2}.$$ The curve is traced by sweeping $w$ over the real line; poles of $S_1, S_2$ at $w = \alpha\, q^{-k}$ partition the sweep into branches, and the parametrization singularity at $w = -1/\beta$ pins the curve to $\kappa=1$. At $\alpha=\beta=1$, $q=0$ this degenerates to the standard inscribed arctic circle $(\kappa - \tfrac12)^2 + (c-\tfrac12)^2 = \tfrac14$.

Speed: Seed: Ready to start

Bernoulli Trial at Cell (i, j)

Position: not started

Probability: p = x_i · y_j / (1 + x_i · y_j)

Random U ~ Uniform[0,1]: —

Result bit: —

q-Whittaker VH Bijection Probabilities

Islands (consecutive indices where μ_i - κ_i = 1): —

f_k = (1 - q^Δλ) / (1 - q^Δν): —

g_s values: —

Stopping decision: —

Growth Diagram Cells (Precomputed Bernoulli Bits)

Staircase cells: ■ bit=1 | □ bit=0 | current

Island Processing Details

Shows islands, f_k stopping probability, g_s sequential sampling

Domino Shuffling / VH Bijection (arXiv:1407.3764 Fig. 10)

Phases: 0: Initial partitions | 1: Form dimers (λ-κ blue, κ-μ orange) | 2: Identify blocks (B markers) | 3: Slide dimers → AFTER | 4: Final result with Δ indicators

Current Aztec Diamond

After completing each anti-diagonal, the corresponding Aztec diamond is shown

Classical Domino Shuffling Algorithm (EKLP 1992)

Setup: The Aztec diamond $\mathcal{A}_n$ of order $n$ consists of all unit squares $[i, i+1] \times [j, j+1]$ with $|i| + |j| < n$. It contains $2n(n+1)$ unit squares and is tiled by $n(n+1)$ dominoes.

Domino Types: Each domino is classified by orientation and parity:

North (N): vertical domino with black square on top
South (S): vertical domino with white square on top
East (E): horizontal domino with black square on right
West (W): horizontal domino with white square on right

The Shuffling Map $\mathcal{A}_n \to \mathcal{A}_{n+1}$:

Deletion: Find all $2 \times 2$ blocks containing exactly two dominoes that form either:
- Two horizontal dominoes stacked (one N, one S), or
- Two vertical dominoes side-by-side (one E, one W)
These are called bad blocks. Delete all dominoes in bad blocks.
Sliding: Each remaining domino slides outward by one unit in its natural direction: $$\begin{aligned} \text{N dominoes} &\to \text{slide up (} +y \text{)} \\ \text{S dominoes} &\to \text{slide down (} -y \text{)} \\ \text{E dominoes} &\to \text{slide right (} +x \text{)} \\ \text{W dominoes} &\to \text{slide left (} -x \text{)} \end{aligned}$$
Creation: After sliding, empty $2 \times 2$ blocks appear. Each block is filled with exactly one of two choices:
- Two horizontal dominoes (N on top, S on bottom), or
- Two vertical dominoes (W on left, E on right)
For uniform random tilings, each choice is made independently with probability $\tfrac{1}{2}$.

Key Properties:

The map is a $2^{n+1}$-to-1 correspondence from tilings of $\mathcal{A}_{n+1}$ to tilings of $\mathcal{A}_n$
Uniform measure on $\mathcal{A}_n$ lifts to uniform measure on $\mathcal{A}_{n+1}$
Starting from the unique tiling of $\mathcal{A}_0$ and shuffling $n$ times samples uniformly from $\mathcal{A}_n$

Reference: arXiv:math/9201305 (opens in new tab) — Elkies, Kuperberg, Larsen, Propp, "Alternating-Sign Matrices and Domino Tilings" (1992).

q-Whittaker Deformation (q > 0)

Key Insight: The q-deformation modifies only Step 3 (Creation). Steps 1 and 2 remain unchanged.

In the classical case, block-filling is deterministic: geometric constraints force a unique cascade. In the q-Whittaker case, particles have probabilistic "stickiness"—even when a particle could move, it might stay with probability depending on $q$.

Step 3': q-Weighted Creation

Empty 2×2 blocks form islands—consecutive positions where new dominoes must be placed. For each island $[k, m]$:

Sample Bernoulli bit: $B \sim \text{Bernoulli}\left(\dfrac{x_i y_j}{1 + x_i y_j}\right)$
Special case: If $B = 1$ and $k = 0$, all particles jump (fill all blocks with same orientation).
Otherwise, sample stopping position:
- Compute $f_k = \dfrac{1 - q^{\lambda_k - \bar\nu_k + 1}}{1 - q^{\bar\nu_{k-1} - \bar\nu_k + 1}}$
- Sample $U \sim \text{Uniform}[0,1]$. If $U < f_k$: stop at $k$
- Else, for $s = k+1, \ldots, m$:
  - Compute $g_s = 1 - q^{\lambda_s - \mu_s + 1}$
  - Sample $U \sim \text{Uniform}[0,1]$. If $U < g_s$: stop at $s$
- If no stop occurs: all particles jump
Fill blocks based on stopping position $s$:
- Blocks at positions $k, \ldots, s-1$: orientation A (e.g., vertical EW pair)
- Block at position $s$: orientation B (opposite, e.g., horizontal NS pair)
- Blocks at positions $s+1, \ldots, m$: orientation A

Domino Orientation Mapping: The stopped particle creates a domain wall:

        Block:   k    k+1   ...   s-1    s     s+1   ...   m

        Fill:    [A]   [A]   ...   [A]   [B]   [A]   ...   [A]

References:

arXiv:1407.3764 (opens in new tab) — Betea, Bouttier, Nejjar, Vuletić, "The free boundary Schur process and applications I"
arXiv:1504.00666 (opens in new tab) — Matveev, Petrov, "q-randomized Robinson-Schensted-Knuth correspondences and random polymers"

Partitions forming the Schur/q-Whittaker process

code

(note: parameters in the code might differ from the ones in simulation results below)

Link to code (This simulation is interactive, written in JavaScript)
Link to code (C++ source code (compiled to WebAssembly))

Dear colleagues:

Feel free to use code (unless otherwise specified next to the corresponding link), data, and visualizations to illustrate your research in talks and papers, with attribution (CC BY-SA 4.0). Some images are available in very high resolution upon request. I can also produce other simulations upon request - email me at lenia.petrov@gmail.com

q-RSK Sampling of Domino Tilings of the Aztec Diamond domino-tilings