How Unbalanced Must a Latin Rectangle Be?

Zhengyu Li, Vijay GanesharXiv 2026 · arXiv

TL;DR

Researchers from Georgia Tech have significantly advanced the study of spatially balanced Latin rectangles, improving 33 out of 51 established benchmarks by up to 39.4%. By combining simulated annealing with a new group-theoretic invariant and formal verification in Lean 4, they proved the optimality of specific configurations and established that minimum imbalance grows cubically with the number of columns.

What Problem Does This Paper Address?

In experimental design, such as agricultural field trials, researchers use Latin squares to ensure that treatments are distributed evenly across rows and columns. However, standard Latin squares don't account for spatial correlation—the tendency for plots close to each other to share similar soil characteristics.

A "spatially balanced" design requires that every pair of treatments be, on average, equally far apart. In the language of geometry, we want the symbols in a $k \times n$ rectangle to be pairwise equidistant in the $\ell_1$ (taxicab) metric. For most dimensions, perfect balance is mathematically impossible. This paper tackles the challenge of finding rectangles with the minimum imbalance—the smallest possible deviation from that ideal equidistance.

Figure 1. A 3 × 9 rectangle of imbalance 56, which Theorem 2 proves optimal. (a) The rectangle, one colour per symbol. (b) The deviation d(u, v) −t of every pair from the average distance t = 10. Blue pairs are too far apart and red pairs too close. (c) Histogram of the 36 deviations. They sum to zero, and I = P|d −t| = 56.

Methods

The authors approached the problem from three angles:

  1. Constructive Search: They employed simulated annealing using a "point picture" perspective. Instead of rearranging rigid algebraic patterns, they viewed symbols as points in a $k$-dimensional grid. Their search allowed temporary violations of column constraints (penalized by an adaptive weight) while keeping rows as permutations, enabling the algorithm to traverse non-Latin states to find better global optima.
  2. Exact Proofs: They developed a branch-and-bound algorithm to prove optimality for small instances. They introduced a sharper pruning bound derived from the identity $I = 2\sum(d - t)^+$, which significantly reduced the search space.
  3. Theoretical Analysis: They used permutons (limit objects for sequences of permutations) to analyze the asymptotic behavior of $2 \times n$ rectangles and established a lower bound for imbalance using a pigeonhole argument.
  4. Formal Verification: To ensure the validity of their computational results, they used the Lean 4 proof assistant. The Lean kernel verified every new rectangle reported in the paper against a rigorous 74-line specification.

Datasets

The primary benchmark used for evaluation was the reference table by Voboril et al. (2025), which compiles the best-known values achieved by SAT solvers, mixed-integer programming (MIP), and LLM-generated streamliners. For $2 \times n$ cases, they compared their results against the six-hour MIP upper bounds established by Mirka et al. (2023).

Key Insights and Ideas

  • The Row Group Invariant: The authors introduced the "row group"—the permutation group generated by the ratios of the rows. They discovered that previous local search methods were stuck in specific "isotopic classes" (mostly group-based rectangles). Their new search method breaks these symmetries, reaching configurations that were previously inaccessible.
  • Cubic Growth: The paper proves that for a fixed number of rows $k$, the minimum imbalance grows as $\Theta(n^3)$. This explains why finding balanced rectangles becomes exponentially harder as the number of columns increases.
  • Equilateral Sets Connection: They linked the problem to the study of $\ell_1$-equilateral sets in geometry. This connection provides a theoretical limit: perfect balance is only possible if the number of rows $k$ is large relative to $n$ ($k = \Omega(n/\log n)$).
Figure 3. Row groups of the best rectangles found. Shading shows improvement over previous best values. Most improved rectangles have the full symmetric (Sn) or alternating (An) group as their row group, proving they are not group-based.

Key Results

  • Benchmark Improvements: The simulated annealing approach improved 33 of the 51 non-square benchmark instances for $8 \le n \le 13$. The most significant improvement was a 39.4% reduction in imbalance for the $12 \times 13$ rectangle.
  • New Optimum: The authors proved that the minimum imbalance for a $3 \times 9$ rectangle is exactly 56, resolving a previously open question regarding its optimality.
  • Efficiency: For $2 \times n$ rectangles, a single two-minute annealing run outperformed six-hour MIP bounds in five out of seven instances.
  • Verified Correctness: All 62 rectangles reported (including new records and matched records) are certified by the Lean 4 kernel, providing a "gold standard" of correctness for these combinatorial objects.

Limitations and Future Work

  • Search Variability: The authors note that single runs of their annealing algorithm are "noisy," with final values varying by up to a third. The reported values are the best of a few runs rather than typical performance estimates.
  • Formalization Gaps: While the upper bounds (the rectangles themselves) are verified in Lean, the optimality proof (the lower bound) for the $3 \times 9$ case relies on unverified C code. Formalizing this branch-and-bound proof in Lean remains a goal for future work.
  • The $k$ vs. $n$ Gap: A major open question remains: how does the minimum imbalance transition from $O(n^3)$ growth at fixed $k$ to the much smaller $O(n^2)$ growth observed when $k=n$ (Latin squares)?

Summary updated

Abstract

We view a $k\times n$ Latin rectangle as $n$ points in the grid $[n]^k$. Each symbol gives one point, whose coordinates are the columns it occupies. The rectangle is balanced when these points are pairwise equidistant in the $\ell_1$ metric. Its imbalance measures the distance from this ideal. We study the minimum imbalance from three sides. Constructively, we use a simulated annealing that moves symbols within rows and only penalises column clashes. Against the reference table of Voboril et al. (2025), it improves 33 of the 51 non-square values for $8\le n\le 13$, by up to 39.4%, and matches the rest. A cheap invariant, the row group, certifies that none of the 33 new rectangles is isotopic to rows of a group table, so the earlier column-swapping local search cannot reach any of them. Exactly, a computer-assisted branch and bound proves that the minimum imbalance of a $3\times 9$ rectangle is $56$. Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity $I=2\sum(d-t)^+$, reduces the search tree by a factor of $2.4$ to $3.3$ on the instances with $k\ge3$ that we solve. Asymptotically, the minimum imbalance is $Θ(n^3)$ for every fixed $k$. A pigeonhole argument gives a lower constant of order $k\,4^{-k}$, and random rectangles give an upper constant of order $\sqrt k$. For $k=2$, the limit of $\min I/n^3$ exists, a permuton attains it, and it lies between $4/375$ and $0.1196$. Perfect balance is an $\ell_1$-equilateral problem, so it forces $k=Ω(n/\log n)$ rows. For $2\times n$ rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for $14\le n\le 20$. Finally, the Lean 4 kernel checks every rectangle reported in this paper against a 74-line specification that imports only Lean's core library. We also prove the pigeonhole lower bound in Lean with Mathlib.
BibTeX
@misc{li2026how,
  author = {Zhengyu Li and Vijay Ganesh},
  title = {{How Unbalanced Must a Latin Rectangle Be?}},
  year = {2026},
  eprint = {2611.06003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06003},
}
Figure