How Unbalanced Must a Latin Rectangle Be?
Organizations: Georgia Institute of Technology.
Abstract
We view a Latin rectangle as points in the grid . Each symbol gives one point, whose coordinates are the columns it occupies. The rectangle is balanced when these points are pairwise equidistant in the 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 , 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 rectangle is . Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity , reduces the search tree by a factor of to on the instances with that we solve. Asymptotically, the minimum imbalance is for every fixed . A pigeonhole argument gives a lower constant of order , and random rectangles give an upper constant of order . For , the limit of exists, a permuton attains it, and it lies between and . Perfect balance is an -equilateral problem, so it forces rows. For rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for . 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 8 | 40.0 | 36.0 | 32.0 | 30.0 | 24.0 | 28.0 | |||||
| 9 | 65.3 | 56.0 | 53.3 56.0 | 48.6 52.6 | 40.0 48.0 | 43.3 51.3 | 42.6 53.3 | ||||
| 10 | 92.0 | 80.0 | 78.6 | 66.6 | 60.0 70.0 | 58.0 72.0 | 58.6 82.6 | 64.0 70.0 | |||
| 11 | 124.0 | 114.0 | 104.0 112.0 | 94.0 116.0 | 88.0 108.0 | 84.0 118.0 | 78.0 114.0 | 84.0 120.0 | 100.0 110.0 | ||
| 12 | 168.0 | 152.0 154.0 | 149.3 154.6 | 140.0 145.3 | 120.0 | 121.3 164.0 | 116.6 148.0 | 106.0 154.0 | 124.0 174.6 | 136.6 147.3 | |
| 13 | 218.6 | 198.0 | 201.3 211.3 | 191.3 210.6 | 166.0 204.0 | 164.0 203.3 | 160.0 220.6 | 152.0 214.0 | 154.6 240.6 | 168.0 224.0 | 166.0 274.0 |
| instance | optimum | nodes, first bound | CPU time | nodes, sharper | before this work |
|---|---|---|---|---|---|
| , | as known | s | ( ) | proven [ 3 , 10 ] | |
| 36.0 | 1.9 s | proven [ 3 , 11 ] | |||
| 32.0 | 477 s | proven [ 16 ] | |||
| 56.0 | 140 s | open | |||
| ; – | — | — | s | — | open (undecided) |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
|---|---|---|---|---|---|---|---|
| lower bound [ 10 ] | 201.57 | 252.6 | 273.82 | 252.0 | 402.6 | 465.3 | 155.0 |
| upper bound [ 10 ] | 268.0 | 345.3 | 427.3 | 508.0 | 617.3 | 732.0 | 816.0 |
| annealing (this work) | 268.0 | 344.6 | 422.0 | 498.0 | 610.6 | 722.6 | 832.0 |
| statement in the paper | Lean name | uses |
|---|---|---|
| all rectangles ( Tables 1 and 3 , Figure 1 ) | Certificates.exists_k_n | core |
| ; is the mean distance | imbalance_eq_imb3 , sum_dist | Mathlib |
| identity ( 1 ) | imbalance_eq_two_mul_sum_pos | Mathlib |
| Theorem 5 , pigeonhole bound | cubic_lower_bound_ceil | Mathlib |
| Theorem 5 , | eventually_lower_bound | Mathlib |
| Theorem 5 , | imbalance_le | Mathlib |
Combinatorial Optimization
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
See all 413 papers