How Unbalanced Must a Latin Rectangle Be?
Abstract
We view a k× 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 ℓ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≤ 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× 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∑(d−t)+, reduces the search tree by a factor of $2.4$ to $3.3$ on the instances with k≥3 that we solve. Asymptotically, the minimum imbalance is Θ(n3) 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 √k. For k=2, the limit of min I/n3 exists, a permuton attains it, and it lies between 4/375 and $0.1196$. Perfect balance is an ℓ1-equilateral problem, so it forces k=Ω(n/log n) rows. For 2× n rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for 14≤ n≤ 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.
Related
- The five vertex model on a rectangle
- Rationality and Quasipolynomiality of Restricted Rectangle Partitions
- Voltage and current density in a rectangle with point in- and ejection via Green's functions and q-analysis
- A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound
- A closed form for the block-statistic generating function of the 2× n rectangle: the two-row case of Kahane's conjecture
BibTeX
@misc{li2026unbalanced,
title = {{How Unbalanced Must a Latin Rectangle Be?}},
author = {Zhengyu Li and Vijay Ganesh},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06003},
eprint = {2611.06003},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06003},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - How Unbalanced Must a Latin Rectangle Be?
AU - Zhengyu Li
AU - Vijay Ganesh
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06003
UR - https://arxiv.org/abs/2611.06003
AB - We view a k× 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 ℓ_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≤ 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× 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∑(d−t)^+, reduces the search tree by a factor of $2.4$ to $3.3$ on the instances with k≥3 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 √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 ℓ_1-equilateral problem, so it forces k=Ω(n/log n) rows. For 2× n rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for 14≤ n≤ 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.
ER -