cs.DMNov 4, 2026

How Unbalanced Must a Latin Rectangle Be?

Authors: Zhengyu Li, Vijay Ganesh

Organizations: Georgia Institute of Technology.

Abstract

We view a k×nk\times n Latin rectangle as nn points in the grid [n]k[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 ℓ1\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≤n≤138\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×93\times 9 rectangle is 5656. Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity I=2∑(d−t)+I=2\sum(d-t)^+, reduces the search tree by a factor of 2.42.4 to 3.33.3 on the instances with k≥3k\ge3 that we solve. Asymptotically, the minimum imbalance is Θ(n3)Θ(n^3) for every fixed kk. A pigeonhole argument gives a lower constant of order k 4−kk\,4^{-k}, and random rectangles give an upper constant of order k\sqrt k. For k=2k=2, the limit of min⁡I/n3\min I/n^3 exists, a permuton attains it, and it lies between 4/3754/375 and 0.11960.1196. Perfect balance is an ℓ1\ell_1-equilateral problem, so it forces k=Ω(n/log⁡n)k=Ω(n/\log n) rows. For 2×n2\times n rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for 14≤n≤2014\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.

Figures & tables

Explore similar work

CardsList
  1. RadonBench: A Benchmark of Classical and Learning-Guided Search Techniques for Problems in Combinatorial Geometry

    Oct 23, 2026Xiaoan Xu, Jesus A. De Loera, Ethan X. Fang +2Combinatorial OptimizationBenchmark Design

  2. Mapping the Solution-Set Structure of Grokking on Latin Squares

    Oct 26, 2026Zihan Gu, Lulu Zhao, Tianyi Ma +4GrokkingNeural Network Generalization

  3. LRAT-Catcher: Importing SAT Solver Certificates into Lean4 by Reflection

    Jul 1, 2026Stefan SzeiderLean Theorem ProvingConstraint Satisfaction