Better Latin Rectangles Reveal the Limits of Perfect Balance

Latin rectangles impose a simple rule: each row contains every symbol once, and no column repeats a symbol. Making those arrangements spatially balanced is harder. Every pair of symbols should have the same total separation, measured by adding their column distances across all rows.

In the November 4, 2026 preprint How Unbalanced Must a Latin Rectangle Be?, Zhengyu Li and Vijay Ganesh report better constructions, a computer-assisted optimality result and mathematical limits on balance. These are distinct kinds of evidence: finding a good rectangle does not establish that no better one exists.

Turning arrangements into points

For a rectangle with k rows and n columns, the authors represent each symbol as a point with k coordinates: the columns where it appears in the respective rows. The distance between two points is the sum of their coordinate differences in absolute value, also called taxicab distance.

Perfect balance means every pair has the same distance. The average pairwise distance is fixed at k(n + 1)/3, regardless of the arrangement. Imbalance is the sum, over all symbol pairs, of absolute deviations from that target. Lower is better; zero means perfect balance.

Agricultural experimental design motivates the problem because unequal treatment spacing can complicate comparisons when soil conditions are spatially correlated. This paper studies the mathematical designs, not their performance in field trials.

A search allowed to break one rule temporarily

The search uses simulated annealing, which sometimes accepts a worse move rather than always demanding immediate improvement. Each move swaps two symbols within a row, preserving that row’s permutation. Column repetitions are temporarily allowed but penalised with an adaptive weight. Only valid Latin rectangles are recorded as solutions.

These ingredients are established techniques. The authors’ contribution is their combination for this problem, the resulting constructions and the accompanying mathematical results—not the invention of simulated annealing.

Against a published reference table covering 51 non-square cases with 8–13 columns, the search improved 33 imbalance values and matched the other 18. The largest reported reduction was 39.4%, from 274 to 166 for a 12-row, 13-column rectangle.

These are improved upper bounds: explicit arrangements showing what is achievable, not necessarily the best possible values. Results were selected from independent one- and five-minute runs, plus ten-minute runs for larger cases, using at most 16 CPU minutes per instance on one Apple M3 core.

The comparison does not establish a runtime advantage over earlier methods. Hardware, search budgets and objectives differed. Results also varied: nine improved cases had a longer run finish worse than a shorter one.

What the exact search establishes

For a three-row, nine-column rectangle, an arrangement with imbalance 56 was already known. The new contribution is a branch-and-bound search concluding that nothing better exists.

Two implementations support that conclusion. A sharper pruning bound reduced the search tree by factors of 2.4–3.3 on the solved cases with at least three rows. However, both implementations share the same branching scheme, so agreement does not exclude an error in that common reasoning.

The authors also analyse a structural invariant called the row group. It certifies that none of the 33 improved rectangles can be obtained from rows of a group multiplication table through row, column and symbol permutations. Consequently, an earlier search restricted to swapping whole columns from cyclic starting designs cannot reach these constructions. This does not explain the improvements over other solver-based methods, which need not share that restriction.

Why imbalance cannot disappear

For every fixed positive number of rows, the minimum imbalance grows on the order of n cubed as the number of columns increases. A pigeonhole argument supplies the lower bound: dividing the coordinate grid into boxes forces many symbol pairs close together, creating unavoidable deviations below the target distance. A random-construction argument supplies an upper bound of the same cubic order.

This result holds with the row count fixed. It does not rule out perfectly balanced squares, where rows and columns grow together.

For two rows, the authors additionally prove that minimum imbalance divided by n cubed converges. The limiting value lies between 4/375, about 0.0107, and 0.1196. Its exact value remains unknown. A continuous representation of permutations, called a permuton, provides the limiting optimisation problem.

Verification has a defined boundary

Lean 4 checks all 62 reported rectangles for validity and their stated imbalance using kernel evaluation against a short specification. The authors also formalise the pigeonhole lower bound with Mathlib.

Those checks certify achievable values, not their optimality. In particular, the claim that 56 is minimal for the three-by-nine case still depends on uncertified search programs. The paper therefore advances both construction and understanding while leaving substantial gaps between known lower bounds, achievable values and fully certified optimality.