All articles

Local Moves, Global Clusters

Local particle moves, a global energy, and a geometric question: when does ascent bring all the particles together?

Go to the experiment · View the code

Local moves, one global cluster?

An integer number of particles is placed on a periodic grid. A particle can move to one of its four neighbours, and its move is accepted if it increases the total interaction energy. On screen, the height above a site is its integer occupation count. The question is the one addressed in the manuscript: must a sequence of moves that all improve the energy eventually produce a single cluster?

The answer depends on the kernel, the graph and the interaction parameter. On the discrete torus, for a sufficiently small parameter, the concentration theorem gives an affirmative answer for every initial configuration. Outside this sufficient range, the experiment may show concentration or several separated clusters that have become stationary. Both behaviours can be examined within the same model.

The model

The sites are the elements of \(X=(\mathbb Z/N\mathbb Z)^2\). The right edge of the grid joins the left edge, and the top edge joins the bottom edge. If \(c(x)\) is the occupation of site \(x\), the total number of particles is \(n=\sum_xc(x)\). The solver stores the normalised mass \(\rho(x)=c(x)/n\); the figure converts it to the count \(c(x)\), so the vertical axis can be read directly in particles.

The visible lattice locates the graph vertices. Every occupied vertex has a bright pink marker of the same screen size, independently of its occupation count. Height and the blue-to-gold colour scale carry the count information. The vertical axis follows the maximum of the current configuration; its tick values therefore change during the experiment. The triangular surface and its level curves interpolate the displayed heights between vertices and do not introduce continuous mass or additional particles.

The kernel is exactly the exponential torus kernel studied in the notes, normalised to have unit diagonal:

\[ K_\beta(x,y)=\exp\!\left[\beta\left(\cos\frac{2\pi(x_1-y_1)}N+\cos\frac{2\pi(x_2-y_2)}N-2\right)\right],\qquad \beta>0. \]

Subtracting \(2\) in the exponent multiplies the original kernel by a positive constant. It changes neither the accepted moves nor their ranking. Interactions involve every pair of sites; only the allowed moves are restricted to neighbours. The three-dimensional plot visualises occupations. The spherical embedding associated with the kernel lies in \(\mathbb R^4\).

Each move is decided by its exact gain

The potential and energy are \(V_c=K_\beta c\) and \(E(c)=c^\top K_\beta c\). To move one particle from an occupied site \(p\) to its neighbour \(q\), we compute

\[ \Delta_{p,q}E=2\bigl[V_c(q)-V_c(p)+1-K_\beta(p,q)\bigr]. \]

The term \(1-K_\beta(p,q)\) is the correction arising from moving an entire particle. Omitting it would change the algorithm. At each iteration, the program compares all admissible moves and chooses the one with the largest gain: this is global steepest ascent. A move is accepted only if its gain is strictly positive, up to the numerical tolerance. Particles move one at a time, and the potential is updated after each move.

The evolution slider therefore counts accepted moves. It represents neither the time of a differential equation nor an Euler step. Playback runs through saved configurations; moving the slider allows an earlier step to be revisited. Every saved state has integer occupations. Any visual transition between two states would not constitute an additional state of the algorithm.

What do the settings change?

\(N\) sets the number of sites in each direction: the grid has \(N^2\) sites. \(n\) is the number of particles. These parameters have different roles; increasing \(N\) does not create additional particles. \(\beta\) controls the decay of similarity between sites. The iteration budget bounds the number of computed moves. The calculation can stop earlier if no admissible move improves the energy.

A new experiment draws a random positive profile, then distributes the \(n\) particles according to a multinomial sample from that profile. The generator seed is stored in the results: the Python code reproduces the same trajectory with the same parameters and seed. Changing the seed renews the initial configuration without changing the kernel or the acceptance rule.

With this normalisation, \(E(c)/n^2\le1\), and equality characterises single-cluster configurations. The displayed energy should increase, and the mass should remain one. The number of occupied sites indicates whether particles are concentrating. It may behave less regularly than the energy: the rule does not require it to decrease at every move.

Connecting the experiment to the theorem

In dimension two, set \(\delta_N=1-\cos(2\pi/N)\) and \(A=\max_{x,y}\bigl(2-\cos(2\pi(x_1-y_1)/N)-\cos(2\pi(x_2-y_2)/N)\bigr)\). For \(n\ge2\), the sufficient regime in the theorem is

\[ 0<\beta\le\frac{\delta_N}{(n-1)A^2}. \]

The program computes this bound for the chosen grid. It can be very small and decreases as the number of particles or the grid resolution increases. It is sufficient: observing a single cluster at a larger \(\beta\) does not contradict it. Conversely, separated clusters for a large parameter illustrate the distinction between a global energy maximum and a stationary configuration under the allowed moves.

The code uses numpy and caches the potential. To avoid loss of precision for small \(\beta\), it works with \(B=(K_\beta-\mathbf1\mathbf1^\top)/\beta\), computed using expm1. This transformation preserves the sign and ranking of the gains; the displayed energy is then restored to its original normalisation. The cache is recomputed periodically to limit accumulated roundoff. The tolerance appears in the metadata, and reaching the move budget is distinguished from reaching a stationary state.

The file below is the one executed by the experiment. It can also be run in a Python environment with NumPy. These calculations check particular trajectories in floating-point arithmetic; the universal scope of the result comes from the proofs in the Mathematics section.

Local moves, global concentration

Loading the experiment…

Drag · rotate
Scroll · zoom
LowHighOccupied vertex
t = 0

Discrete index k · saved configurations from the actual algorithm.

Height is the integer number of particles at a vertex. The vertical scale follows the current maximum. Every occupied site has one pink marker of the same size, regardless of its number of occupants. The surface joins values on the lattice; it does not add particles between sites.

Parameters and computation details

Experiment code

This is the Python file executed by the experiment. It can also be run locally. The window contains the complete source.

particles.pyDownload
"""Strict energy ascent on a two-dimensional discrete torus.

The kernel and one-particle increment are those of Local Moves, Global
Clusters, equations (2.4), (3.4), and (5.2).  Time means accepted moves.
Run: python particles.py --N 12 --particles 64 --beta 0.0001 --output run.json
"""
from __future__ import annotations

import argparse
import json
import math
from pathlib import Path

import numpy as np


def torus_kernel(N: int, beta: float):
    yy, xx = np.mgrid[:N, :N]
    sites = np.column_stack((xx.ravel(), yy.ravel()))
    delta = sites[:, None, :] - sites[None, :, :]
    a = 2.0 - np.cos(2.0 * np.pi * delta / N).sum(axis=2)
    # Subtracting a constant kernel and dividing by beta preserve every
    # move ranking. expm1 keeps the gains accurate when beta is small.
    B = np.expm1(-beta * a) / beta
    neighbors = []
    for x, y in sites:
        neighbors.append([
            y * N + (x + 1) % N, y * N + (x - 1) % N,
            ((y + 1) % N) * N + x, ((y - 1) % N) * N + x,
        ])
    return B, np.asarray(neighbors, dtype=np.int32), float(a.max())


def simulate(params: dict | None = None) -> dict:
    params = params or {}
    N = int(params.get("N", 12))
    n = int(params.get("particles", 64))
    beta = float(params.get("beta", 0.0001))
    steps = int(params.get("steps", 2500))
    snapshots = int(params.get("snapshots", 121))
    seed = int(params.get("seed", 173))
    if not 3 <= N <= 32 or not 1 <= n <= 4096:
        raise ValueError("Choose 3 <= N <= 32 and 1 <= particles <= 4096.")
    if not math.isfinite(beta) or not 1e-8 <= beta <= 30:
        raise ValueError("beta must lie between 1e-8 and 30.")
    if not 1 <= steps <= 20000 or not 2 <= snapshots <= 400:
        raise ValueError("Invalid move budget or number of snapshots.")

    rng = np.random.default_rng(seed)
    B, neighbors, A = torus_kernel(N, beta)
    # A new random mass profile, followed by an integer particle sample.
    weights = rng.gamma(shape=0.8, scale=1.0, size=N * N)
    weights /= weights.sum()
    c = rng.multinomial(n, weights).astype(np.int64)
    potential = B @ c
    rows = np.arange(N * N)[:, None]
    edge_correction = -B[rows, neighbors]
    history = [c.astype(np.uint16).copy()]
    energies = [1.0 + beta * float(c @ potential) / n**2]
    accepted_gains = []
    tolerance = 128.0 * np.finfo(float).eps * max(1, n) * max(1.0, A)
    stationary = False

    for _ in range(steps):
        gain = 2.0 * (potential[neighbors] - potential[:, None] + edge_correction)
        gain[c == 0, :] = -np.inf
        p, direction = np.unravel_index(int(np.argmax(gain)), gain.shape)
        best = float(gain[p, direction])
        if best <= tolerance:
            stationary = True
            break
        q = int(neighbors[p, direction])
        c[p] -= 1
        c[q] += 1
        potential += B[:, q] - B[:, p]
        # Refresh the cached potential occasionally; this limits long-run drift.
        if len(history) % 128 == 0:
            potential = B @ c
        accepted_gains.append(beta * best)
        history.append(c.astype(np.uint16).copy())
        energies.append(1.0 + beta * float(c @ potential) / n**2)

    total_moves = len(history) - 1
    chosen = np.unique(np.rint(np.linspace(0, total_moves, min(snapshots, total_moves + 1))).astype(int))
    selected = [history[k].astype(float) / n for k in chosen]
    edge_a = 1.0 - math.cos(2.0 * math.pi / N)
    threshold = edge_a / ((n - 1) * A**2) if n > 1 else None
    if np.count_nonzero(c) == 1:
        stationary = True
    return {
        "x": list(range(N)),
        "y": list(range(N)),
        "frames": [state.tolist() for state in selected],
        "times": [int(k) for k in chosen],
        "diagnostics": {
            "energy": [float(energies[k]) for k in chosen],
            "occupied": [int(np.count_nonzero(history[k])) for k in chosen],
            "max_density": [float(history[k].max() / n) for k in chosen],
            "mass": [float(history[k].sum() / n) for k in chosen],
        },
        "meta": {
            "model": "Global steepest one-particle ascent on (Z/NZ)^2",
            "kernel": "exp(beta*(cos(2*pi*dx/N)+cos(2*pi*dy/N)-2))",
            "time_label": "Accepted moves",
            "density_label": "c(x) / n",
            "N": N, "particles": n, "beta": beta, "seed": seed,
            "accepted_moves": total_moves,
            "stationary": stationary,
            "termination": "stationary_to_tolerance" if stationary else "move_budget_reached",
            "occupied_final": int(np.count_nonzero(c)),
            "sufficient_beta_threshold": threshold,
            "inside_proved_regime": bool(n == 1 or beta <= threshold),
            "scaled_gain_tolerance": float(tolerance),
            "minimum_accepted_gain": float(min(accepted_gains)) if accepted_gains else None,
            "mass_error": float(abs(c.sum() - n)),
            "energy_normalization": "E_K(c) / n^2",
        },
    }


def _main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("--N", type=int, default=12)
    parser.add_argument("--particles", type=int, default=64)
    parser.add_argument("--beta", type=float, default=0.0001)
    parser.add_argument("--steps", type=int, default=2500)
    parser.add_argument("--seed", type=int, default=173)
    parser.add_argument("--snapshots", type=int, default=121)
    parser.add_argument("--output", default="particles-run.json")
    args = vars(parser.parse_args())
    output = args.pop("output")
    result = simulate(args)
    Path(output).write_text(json.dumps(result, ensure_ascii=False), encoding="utf-8")
    print(json.dumps(result["meta"], ensure_ascii=False, indent=2))


if __name__ == "__main__":
    _main()
Back to top