betaFeedback

WorksComputer Science

How Unbalanced Must a Latin Rectangle Be?

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.

Introduction

In an agricultural field trial, the treatments occupy a grid of plots. When some pairs of treatments are systematically planted closer together than others, spatial correlation in the soil can bias their comparison [14]. Latin designs remove the row and column effects, but not this one. Spatially balanced Latin squares ask, in addition, that every pair of treatments be equally far apart on average [5, 9]. Díaz et al. [3] posed the same question for k×nk \times n rectangles, observed that perfect balance is then usually impossible, and asked instead for rectangles of minimum imbalance. Later work on the problem uses SAT encodings that prove optimal with checkable proof certificates [11] and mixed-integer programming [10]. It also uses streamliners written by large language models [16] and LLM agents that reformulate models [15]. Closest to our work, Xia et al. [17] use simulated annealing for spatially balanced Latin squares and reach the optimum for n=10n = 10 and n=13n = 13 in under a second. They also prove an Ω(n2)\Omega(n^2) lower bound on the imbalance of squares with n≡1(mod3)n \equiv1 \pmod{3}, by a parity argument. The starting point of this paper is the reference table of Voboril et al. [16], which collects the best values that the methods above obtained for rectangles. To our knowledge, this table is still current. The later work [15] reports aggregate model comparisons but no per-instance values, and Xia et al. [17] treat only squares.

Here is the point of view of this paper. Record, for each symbol uu, the columns c1(u),…,ck(u)c_1(u), \ldots, c_k(u) that it occupies in the kk rows. This gives a point xu∈[n]kx_u \in[n]^k. The distance between two symbols that the literature uses is exactly the ℓ1\ell_1 distance ∥xu−xv∥1\lVert x_u - x_v \rVert_1. A balanced rectangle is therefore a set of nn points in a kk-dimensional grid that are pairwise equidistant in the taxicab metric. When kk is small compared with nn, the grid is too crowded for equidistance, and § 8 makes this quantitative. When k=nk = n there is room, consistent with the existence of balanced squares for infinitely many nn. The point picture also suggests a search that moves individual points, rather than one that rearranges a rigid algebraic pattern.

Contributions

  1. New upper bounds (§ 4 and § 5). The search keeps each row a permutation and turns the column condition into a penalty with an adaptive weight. A move swaps two symbols within a row, and the search evaluates its effect exactly in O(n)O(n) time. Against the reference table of Voboril et al. [16], the search improves 33 of 51 instances and matches the other 18.

  1. A new optimum (§ 6). A branch and bound that places one symbol at a time proves that the known value 56 is optimal for 3×93 \times9, which was open. It also independently reproduces the known optima for 2×n2 \times n with n≤11n \le11 and for 3×83 \times8 and 4×84 \times8. A second, independent implementation with a sharper bound confirms the 3×93 \times9, 3×83 \times8 and 4×84 \times8 results and the 2×102 \times10 and 2×112 \times11 optima.

  1. A certificate of non-group structure (§ 7). The permutation group generated by the ratios of the rows does not change under column operations. For rectangles taken from group tables, its order divides nn. For 32 of our 33 improved rectangles it is the full alternating or symmetric group, and for the last one it has order 46080. So local search that only permutes the columns of a cyclic rectangle [3] cannot reach any of them. The invariant does not separate our rectangles from the published SAT and streamliner rectangles, most of which are also far from group tables.

  1. Cubic growth (§ 8). For every fixed kk, the minimum imbalance is Θ(n3)\Theta(n^3). The lower constant ck=max⁡m≥3km−k(13−1m)c_k = \max_{m \ge3} k m^{-k}\left(\frac{1}{3} - \frac{1}{m}\right) is of order k4−kk4^{-k}, while random rectangles give an upper constant Dk≤k/(62)D_k \le\sqrt{k}/(6\sqrt{2}). The right order in kk is open. Perfect balance also requires n≤e(ℓ1k)=O(klog⁡k)n \le e(\ell_1^k) = O(k \log k), by a classical bound on equilateral sets.

  1. The case k=2k = 2 (§ 9). On the open instances 14≤n≤2014 \le n \le20, we compare a single-seed two-minute annealing run with the six-hour upper bounds of Mirka et al. [10]. The run improves the bound for 15≤n≤1915 \le n \le19, ties at n=14n = 14 and is worse at n=20n = 20. The limit of min⁡I/n3\min I/n^3 exists and is the minimum of a continuous functional on permutations. We bracket it between 4/3754/375 and 0.1196, and we compute the upper value exactly for the permution of one 2×642 \times64 rectangle.

6. A Lean formalisation (§ 10). Lean’s kernel certifies all 62 rectangles behind our upper bounds by evaluation. The check uses no native_decide and no Mathlib, only Lean’s core library, so it trusts only the kernel and a short specification. We prove the identity (1) and Theorem 5 in Lean with Mathlib. Each formalised statement names the Lean theorem that proves it.

None of the algorithmic ingredients is new by itself. Simulated annealing [7] is established, including for the square version of this problem [17]. So are row-preserving swaps with temporarily violated column constraints [18, 19] and adaptive penalties, also known as strategic oscillation [4]. What we add is their combination for rectangles, the resulting records, and the exact and asymptotic results.

Preliminaries

A k×nk \times n Latin rectangle (k≤nk \le n) is an array with entries in [n]={1,…,n}[n] = \{1,\ldots,n\} in which no symbol repeats in a row or in a column. Let ci(u)c_i(u) denote the column of symbol uu in row ii and xu=(c1(u),…,ck(u))∈[n]kx_u = (c_1(u),\ldots,c_k(u)) \in[n]^k. Following Díaz et al. [3] and Peruvemba Ramaswamy and Szeider [11],

d(u,v)=∑i=1k∣ci(u)−ci(v)∣=∥xu−xv∥1,I(L)=∑1≤u<v≤n∣d(u,v)−t∣,t=k(n+1)3.d(u,v) = \sum_{i=1}^{k} |c_i(u) - c_i(v)| = \lVert x_u - x_v \rVert_1,\qquad I(L) = \sum_{1 \le u < v \le n} |d(u,v) - t|,\qquad t = \frac{k(n+1)}{3}.

Each row contributes ∑u<v∣ci(u)−ci(v)∣=(n+13)\sum_{u<v}|c_i(u)-c_i(v)| = \binom{n+1}{3} to the total distance, so tt is the average distance over all (n2)\binom{n}{2} pairs. In particular the deviations d(u,v)−td(u,v)-t sum to zero, and

I(L)=2∑u<v(t−d(u,v))+=2∑u<v(d(u,v)−t)+.(1)I(L) = 2 \sum_{u<v}(t-d(u,v))^+ = 2 \sum_{u<v}(d(u,v)-t)^+. \tag*{(1)}

The pairs that are too close and the pairs that are too far therefore contribute equally to the imbalance. This identity drives both the pruning bound of § 6 and the lower bound of § 8. (In Lean, the average is LatinRect.sum_dist and the identity is LatinRect.imbalance_eq_two_mul_sum_pos.) The quantity 3I3I is an integer. As in the literature, we write imbalances as x.0x.0, x.3x.3 and x.6x.6 for xx, x+13x+\frac{1}{3} and x+23x+\frac{2}{3}.

Two dictionaries. We can read a rectangle through its rows or through its points. Through its rows it is a kk-tuple (r1,…,rk)(r_1,\ldots,r_k) of bijections ri:[n]→[n]r_i:[n]\to[n] from columns to symbols, with ri(j)≠ri′(j)r_i(j) \ne r_{i'}(j) for i≠i′i \ne i'. Through its points it is a set {xu}\{x_u\} in [n]k[n]^k whose coordinate projections are bijections. The column condition says exactly that every point has distinct coordinates. The imbalance is invariant under relabelling symbols, permuting rows and reversing the order of the columns, j↦n+1−jj \mapsto n+1-j, which preserves every distance. It is not invariant under general column permutations. After relabelling the symbols, we may assume r1=idr_1 = \mathrm{id}.

Search: rows as permutations, columns as a penalty

The state of the search is a kk-tuple of permutations with r1=idr_1 = \mathrm{id}. It need not be Latin. A move picks a row i≥2i \ge2 and two columns j1≠j2j_1 \ne j_2, and swaps the symbols a=ri(j1)a=r_i(j_1) and b=ri(j2)b=r_i(j_2). In the point picture, the move exchanges the ii-th coordinates of the two points xax_a and xbx_b, and nothing else moves.

Lemma 1 (Incremental evaluation). After the move, only the 2(n−2)2(n-2) distances d(a,w)d(a,w) and d(b,w)d(b,w) with w∉{a,b}w\notin\{a,b\} change, and with p=ci(w)p=c_i(w),

d′(a,w)=d(a,w)−∣j1−p∣+∣j2−p∣,d′(b,w)=d(b,w)−∣j2−p∣+∣j1−p∣.d'(a,w)=d(a,w)-|j_1-p|+|j_2-p|,\qquad d'(b,w)=d(b,w)-|j_2-p|+|j_1-p|.

Hence the exact change of 3I3I is computable in O(n)O(n) integer operations.

Proof. The move only exchanges the ii-th coordinates of xax_a and xbx_b. So d(a,b)d(a,b) does not change, and no pair without aa or bb is affected.

Penalty. Let VV be the number of excess occurrences of symbols in columns. Per-column counters maintain VV in O(1)O(1) time per move. The search minimises 3I+W⋅V3I+W\cdot V and records only states with V=0V=0. The weight starts at W=kW=k and stays in [1,4n2][1,4n^2]. Every 2162^{16} proposals, the search multiplies WW by 1.02 if the current state has conflicts and by 0.99 otherwise. The search can therefore leave the Latin rectangles, pass through non-Latin states and return. By contrast, moves that permute whole columns never leave the Latin rectangles, and as § 7 shows, they never change the row group.

Schedule. The search starts from the cyclic rectangle ri(j)=i+j(modn)r_i(j)=i+j\pmod n. It accepts a move of change Δ\Delta with probability min⁡(1,e−Δ/T)\min(1,e^{-\Delta/T}). The temperature starts at T0=2kT_0=2k (in units of 3I3I) and is multiplied by 0.9999995 per proposal. It never drops below 0.05, which it reaches after about 10710^7 proposals. Most of a run is therefore a low-temperature walk on plateaus. If the best Latin rectangle found so far does not improve for 4⋅1074\cdot10^7 proposals, the search resets the temperature to T0T_0. The search discards a proposal with j1=j2j_1=j_2 but still counts it, and does not cool for it. Runs are single-threaded, and the search re-evaluates the reported rectangle from scratch.

An independent checker, written from the definition with exact rational arithmetic, verifies every reported rectangle. It also reproduces the imbalances reported for all fourteen rectangles printed in [11, 16]. Lean’s kernel also certifies every reported rectangle (§ 10).

Improved upper bounds

We take the 51 non-square instances 8≤n≤138 \le n \le13, 2≤k≤n−12 \le k \le n-1 of Table 1 of [16], which also collects the earlier records. All runs used an Apple M3 laptop, one core per run. Each instance received independent runs of 1 and 5 CPU minutes. The larger instances (k≥4k \ge4, n≥9n \ge9) also received a 10-minute run, so each instance used at most 16 CPU minutes. Table 1 reports the best of these runs. Of the 33 new values, 10 came first from the 1-minute run, 8 from the 5-minute run and 15 from the 10-minute run. The search improves 33 values, matches 18 and is worse on none. The mean improvement is 18.5% and the largest is 39.4% (12 × 13: 274.0 → 166.0). The search matches every record with n=8n = 8 or k=2k = 2, every record with k=3k = 3 except 3 × 12, and the records for 4 × 10, 5 × 10 and 6 × 12. Several of these are proven optimal [10, 11], so matching is the best possible there.

n\kn \backslash k23456789101112
840.036.032.030.024.028.0
965.356.053.3 ~~56.0~~48.6 ~~52.6~~40.0 ~~48.0~~43.3 ~~51.3~~42.6 ~~53.3~~
1092.080.078.666.660.0 ~~70.0~~58.0 ~~72.0~~58.6 ~~70.0~~64.0 ~~70.0~~
11124.0114.0104.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~~
12168.0152.0 ~~154.0~~149.3 ~~154.6~~140.0 ~~145.3~~120.0121.3 ~~164.0~~116.6 ~~148.0~~106.0 ~~154.0~~124.0 ~~174.6~~136.6 ~~147.3~~
13218.6198.0201.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~~

Table 1. Table 1. Minimum known imbalance of k×nk \times n Latin rectangles. Bold: new value from this work (best of the 1-, 5- and 10-minute runs), with the previous best value struck through below it. Previous values are those collected in Table 1 of Voboril et al. [16], which includes results of [3, 10, 11], of 4-hour Gurobi runs and of LLM-generated streamliners. Plain: a record that our search matches. Every bold or plain value is attained by a rectangle certified in Lean (Certificates.exists_k*_n*, § 10). The struck-through values are taken from the literature and are not certified.

Variability. Single runs are noisy. In 9 of the 33 improved cells, a longer run ended with a worse value than a shorter one. Across the three budgets, the final values of a cell differ by a median of 5% and at most 32.5%. The values in Table 1 are therefore upper bounds from a few runs, not estimates of typical performance.

Prior effort. Most previous values come from Voboril et al. [16]. They add LLM-generated streamlining constraints to a MiniZinc model and solve it with Gurobi. They run the streamliners either incrementally, warm-starting each round from the best solution so far, or with an evolutionary search. Their runs take 4 hours or more on dual 10-core Xeon nodes. The other previous values come from 4-hour Gurobi runs and earlier literature [3, 10, 11].

These runs used different hardware, different time limits and a general-purpose solver, so we compare values, not methods. Several previous values are attested by printed rectangles. For instance, the value 274.0 for 12 × 13 is the rectangle in Fig. 6h of [16], and our checker and Lean reproduce it. The amount of search behind each previous value also varies between cells. So the size of an improvement need not reflect the difficulty of an instance.

Speed. We reran the search with 5 fresh seeds on every improved instance, stopping when it beat the record (Figure 2b). All 165 runs succeeded. The median time to beat the previous record (not to reach our final value) was 0.12 CPU seconds and the maximum 143 seconds. For the reasons above we make no runtime comparison with earlier work. We measured these times on the Apple M3 laptop and did not archive their logs. An independent rerun of the same 165 runs used the original source on Linux x86-64 with GCC. It beat every record (pooled median 0.21 CPU seconds, maximum 280) and ended at the same values as the original runs. Its logs are in the validation/ directory of the repository.

Figure 2. The 33 improved instances. (a) Previous record (open circle) and new value (filled). (b) CPU time until the search first beats the record: median (dot) and range (bar) over 5 seeds, log scale.

Exact search and a new optimum

To complement the upper bounds, we wrote a branch and bound that decides whether a rectangle with 3I<β3I < \beta exists for a given bound β\beta.

Branching. With r1=idr_1 = \mathrm{id} fixed, the search places the symbols in the order 1,2,…,n1, 2, \ldots, n. Placing a symbol means choosing its column in each row 2,…,k2, \ldots, k, subject to the Latin conditions. The search places symbol 1 in increasing columns of rows 2,…,k2, \ldots, k. This loses nothing. Relabelling the symbols makes r1=idr_1 = \mathrm{id}, and permuting rows 2,…,k2, \ldots, k keeps r1=idr_1 = \mathrm{id}. Symbol 1 occupies distinct columns in those rows, so exactly one such permutation makes its columns increase with the row index. Both operations preserve II. A node is one choice of a column for a symbol in one row that passes the Latin check. When symbol uu is complete, the deviations ∣3d(u,v)−3t∣|3d(u,v)-3t| for all v<uv<u are final, and the search adds them to the cost. We do not yet exploit the choice of the row that is fixed to the identity, or the column reversal of § 3. Together they offer up to another factor 2k2^k of symmetry.

Bounds. Every unplaced row adds at least 1 to any distance, because the two symbols occupy different columns, and at most n−1n-1. So, while the search places a symbol, each pair (u,v)(u,v) with v<uv<u has a known overshoot ouv=(3dpart+3ρ−3t)+o_{uv}=(3d_{\mathrm{part}}+3\rho-3t)^+ and a known shortfall suv=(3t−3dpart−3ρ(n−1))+s_{uv}=(3t-3d_{\mathrm{part}}-3\rho(n-1))^+. Here dpartd_{\mathrm{part}} is the distance over the rows placed so far, and ρ\rho is the number of rows still to place. Let PP and NN be the sums of the positive and negative parts of the final deviations 3d−3t3d-3t, so that the cost so far is P+NP+N. By (1), 3I=2∑(3d−3t)+=2∑(3d−3t)−3I=2\sum(3d-3t)^+=2\sum(3d-3t)^-, so each of

P+N+∑ouv+∑suv,2(P+∑ouv),2(N+∑suv)P+N+\sum o_{uv}+\sum s_{uv},\qquad2\left(P+\sum o_{uv}\right),\qquad2\left(N+\sum s_{uv}\right)

is a lower bound on 3I3I. The search prunes the node when their maximum reaches β\beta. The first version of our program used only P+N+∑ouvP+N+\sum o_{uv}. The other two terms cost a few additions per node. When a symbol is complete, the first program also adds m0=min⁡(3t mod 3,3−3t mod 3)m_0=\min(3t\bmod3,3-3t\bmod3) for every pair that is not yet final. This is valid only for the first of the three bounds, because a pair’s deviation can lie on either side of tt. For 3×n3\times n and 4×84\times8 we have m0=0m_0=0. A run with β\beta equal to three times the value of our rectangle either finds a better rectangle or proves that none exists.

Theorem 2 (computer-assisted). The minimum imbalance of a 3×93\times9 Latin rectangle is 56. The upper bound is the rectangle of Figure 1, certified in Lean as Paper.three_by_nine. The lower bound is not formalised (§ 10). With the first bound, the branch and bound explores 5.5⋅1095.5\cdot10^9 nodes in 140 CPU seconds and finds no rectangle with I<56I<56. As a sanity check, a run with β=169\beta=169 finds a rectangle of value 56. Díaz et al. [3] had already found the value 56 itself. To our knowledge, its optimality was not known. That paper does not prove it, and Table 1 of [16] lists it as unproven.

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

A second implementation. To reduce the dependence on a single program, we re-derived the result with a second implementation. It was written independently from the description above and uses the sharper bound. Restricted to the first bound, it explores the same number of nodes as the first program to the precision we recorded (7.77⋅1077.77\cdot10^7 against 7.8⋅1077.8\cdot10^7 for 3×83\times8, 5.48⋅1095.48\cdot10^9 against 5.5⋅1095.5\cdot10^9 for 3×93\times9). With the sharper bound, it confirms the three results with k≥3k\ge3 using 2.4 to 3.3 times fewer nodes. It confirms the 2×102\times10 and 2×112\times11 optima with about 1.5 times fewer nodes (Table 2). Both programs share the branching scheme, so this guards against coding errors but not against an error in the scheme itself.

instanceoptimum IInodes, first boundCPU timenodes, sharperbefore this work
2×n2 \times n, n≤11n \le11as known≤3.8⋅107\le3.8 \cdot10^7≤1.1\le1.1 s≤2.6⋅107\le2.6 \cdot10^7 (n≥10n \ge10)proven [3, 10]
3×83 \times836.036.07.8⋅1077.8 \cdot10^71.91.9 s3.2⋅1073.2 \cdot10^7proven [3, 11]
4×84 \times832.032.01.9⋅10101.9 \cdot10^{10}477477 s5.7⋅1095.7 \cdot10^9proven [16]
3×93 \times956.056.05.5⋅1095.5 \cdot10^9140140 s2.1⋅1092.1 \cdot10^9open
5,6,7×85,6,7 \times8; 44–8×98 \times9——>1800>1800 s—open (undecided)

Table 2. Exact branch and bound, single core. Each run proves that no rectangle beats our upper bound. The sharper-bound node counts are from the second implementation. We omit its CPU times because they were measured on a shared machine. On all small instances with n≤7n \le7 and k≤4k \le4 the first program also reproduces the values reported in [3].

Table 2 summarises the runs. The method is deliberately plain: no symmetry beyond row order and symbol relabelling, and no learned bounds. With a 30-minute cap per instance and the first bound, the remaining open instances with n∈{8,9}n\in\{8,9\} stay undecided. Unlike the DRAT proofs of [11], our search does not emit a checkable certificate. Theorem 2 therefore rests on the correctness of two short programs. The first, which we publish, reproduces all the known optima listed above. The second, which is not yet in the repository, reproduces those for 2×102\times10, 2×112\times11, 3×83\times8 and 4×84\times8. A certificate in the style of [11] is the natural next step, and the overshoot and shortfall bounds may be worth encoding there as redundant constraints.

A certificate that the new rectangles are not group-based

Díaz et al. [3] start their local search from kk random rows of the cyclic Latin square. They repeatedly swap two random columns, keep a swap only when it lowers the imbalance, and restart with fresh rows. They note that the method “never leaves its isotopic class”. Two rectangles are isotopic if permuting rows, columns and symbols turns one into the other. So permuting columns preserves the isotopy class by definition. The question is how to see that a given rectangle lies outside every such class. We give an invariant that is cheap to compute and detects whether a rectangle can come from a group table. It is not a complete isotopy invariant, and it does not by itself explain why one search outperforms another.

Definition 3. The row group of a Latin rectangle with rows r1,…,rkr_1,\ldots,r_k is the permutation group on symbols

H(L)=⟨ri∘rj−1:1≤i,j≤k⟩≤Sn.\mathrm{H}(L)=\langle r_i\circ r_j^{-1}:1\le i,j\le k\rangle\le S_n.

The element ri∘rj−1r_i\circ r_j^{-1} sends the symbol in column cc of row jj to the symbol in column cc of row ii. Since rirj−1=(rir1−1)(rjr1−1)−1r_i r_j^{-1}=(r_i r_1^{-1})(r_j r_1^{-1})^{-1}, the group is already generated by the k−1k-1 ratios rir1−1r_i r_1^{-1}. In particular, for k=2k=2 the row group is the cyclic group generated by r2r1−1r_2r_1^{-1}, so it carries no information beyond the cycle type of one permutation.

Proposition 4.

(i) Permuting columns does not change H(L)\mathrm{H}(L). Permuting rows permutes its generators. Relabelling symbols by σ\sigma replaces it by σH(L)σ−1\sigma\mathrm{H}(L)\sigma^{-1}. So the conjugacy class of H(L)\mathrm{H}(L) is an isotopy invariant.

(ii) If LL is isotopic to kk rows of the Cayley table of a group GG of order nn, then H(L)\mathrm{H}(L) is conjugate to a subgroup of the left-regular representation of GG. In particular it acts semiregularly (only the identity fixes a symbol) and ∣H(L)∣|\mathrm{H}(L)| divides nn.

(iii) For i≠1i\ne1, a swap in row ii left-multiplies rir1−1r_i r_1^{-1} by a transposition and fixes the other generators. A single swap can therefore enlarge the row group.

Proof. (i) Replacing every row by ri∘πr_i\circ\pi gives (riπ)(rjπ)−1=rirj−1(r_i\pi)(r_j\pi)^{-1}=r_i r_j^{-1}. The other two statements are immediate. (ii) Up to isotopy, ri(c)=σ(aibc)r_i(c)=\sigma(a_i b_c) with ai∈Ga_i\in G and c↦bcc\mapsto b_c a bijection onto GG. Then rirj−1r_i r_j^{-1} maps σ(ajb)\sigma(a_jb) to σ(aib)\sigma(a_i b), so it is σλaiaj−1σ−1\sigma\lambda_{a_i a_j^{-1}}\sigma^{-1}, where λg\lambda_g is left multiplication by gg. (iii) Swapping two symbols in row ii replaces rir_i by τri\tau r_i for a transposition τ\tau. □\square

So any search whose moves permute columns, starting from rows of a cyclic Latin square, stays among rectangles whose row group is cyclic of order dividing nn. Figure 3 shows the row groups of the best rectangles we found. Of the 33 improved rectangles, 29 have row group SnS_n and 3 have AnA_n (5 × 9, 8 × 9 and 3 × 12). The remaining one, 5 × 12, has a row group of order 46080 = 26⋅6!2^6 \cdot6!, which does not divide 12. By Theorem 4(ii), none of the 33 rectangles is isotopic to rows of a group table. In particular, the column-swapping search of [3] cannot reach any of them. The row group of the 5 × 12 rectangle is the full centraliser S2≀S6S_2 \wr S_6 of the pairing u↔13−uu \leftrightarrow13 - u of symbols. This mirror symmetry also appears in the published 4 × 12 and 5 × 12 records.

Figure 3. Row groups of our best rectangles in the benchmark range. Shading shows the improvement over the previous best value, and grey cells are matched records. Each label gives the row group: SnS_n or AnA_n, otherwise its order. For k=2k = 2 the row group is cyclic, generated by one permutation. It still certifies non-group structure when its order does not divide nn.

What this does and does not show. The row group certifies that column-based local search cannot reach our rectangles. It does not explain why annealing finds better upper bounds than those reported by the exact solvers and streamliners, which supply most of the records we improve. Ten of the fourteen published SAT and streamliner rectangles also have row group SnS_n. The SAT encodings aim at optimality proofs, while the streamliner approach searches a general-purpose model with a MIP solver under LLM-proposed restrictions. We have not isolated which ingredient of our search accounts for the better upper bounds.

Cubic growth for a fixed number of rows

Why does imbalance grow so quickly with nn (Table 1), and why can squares be perfectly balanced? The point picture gives a short answer. For fixed kk, there is not enough room in [n][n] for nn points that are pairwise far apart.

Theorem 5 (Lean: cubic_lower_bound_ceil). Let LL be a k×nk \times n Latin rectangle and s≥1s \ge1

an integer, and put M=⌈n/s⌉M=\lceil n/s\rceil. Then

I(L)≥n(nMk−1)(k(n+1)3−k(s−1))I(L) \ge n\left(\frac{n}{M^k}-1\right)\left(\frac{k(n+1)}{3}-k(s-1)\right)

whenever k(s−1)≤tk(s-1)\le t, that is, 3(s−1)≤n+13(s-1)\le n+1. Consequently, for every fixed kk,

ck≤lim inf⁡n→∞min⁡In3≤lim sup⁡n→∞min⁡In3≤k3,ck=max⁡m≥3kmk(13−1m)>0.c_k\le\liminf_{n\to\infty}\frac{\min I}{n^3}\le\limsup_{n\to\infty}\frac{\min I}{n^3}\le\frac{k}{3},\qquad c_k=\max_{m\ge3}\frac{k}{m^k}\left(\frac{1}{3}-\frac{1}{m}\right)>0.

Proof. Cut each axis of [n]k[n]^k into MM intervals of at most ss consecutive values. This cuts the grid into MkM^k boxes. Two points in the same box differ by at most s−1s-1 in every coordinate, so their distance is at most k(s−1)≤tk(s-1)\le t. If box bb holds mbm_b of the nn points, convexity gives

∑b(mb2)≥Mk(n/Mk2)=n2(nMk−1).\sum_b \binom{m_b}{2}\ge M^k\binom{n/M^k}{2}=\frac{n}{2}\left(\frac{n}{M^k}-1\right).

pairs that share a box. Each of them has t−d≥t−k(s−1)≥0t-d\ge t-k(s-1)\ge0. Inserting this into (1) proves the first claim. For the second, take s=⌈n/m⌉s=\lceil n/m\rceil for a fixed m≥3m\ge3. Then M≤mM\le m and s−1≤(n−1)/ms-1\le(n-1)/m, and the bound becomes I≥k(13−1m)(n3mk−n2)I\ge k\left(\frac{1}{3}-\frac{1}{m}\right)\left(\frac{n^3}{m^k}-n^2\right) (lower_bound_explicit), which is km−k(13−1m)n3−O(n2)k m^{-k}\left(\frac{1}{3}-\frac{1}{m}\right)n^3-O(n^2) (eventually_lower_bound). For the upper bound (imbalance_le), k≤d≤k(n−1)k\le d\le k(n-1) gives ∣d−t∣≤2k(n−2)3|d-t|\le\frac{2k(n-2)}{3}, and (n2)⋅2kn3≤kn33\binom{n}{2}\cdot\frac{2kn}{3}\le\frac{kn^3}{3}. □\square

The Lean proof (§ 10) follows these lines and does the convexity step with the Cauchy–Schwarz inequality (∑bmb)2≤Mk∑bmb2(\sum_b m_b)^2\le M^k\sum_b m_b^2.

The upper constant k/3k/3 is crude. Random rectangles do much better, though we have not formalised this.

Proposition 6. Let U1,U1′,…,Uk,Uk′U_1,U'_1,\ldots,U_k,U'_k be independent and uniform on [0,1][0,1], put Zk=∑i=1k∣Ui−Ui′∣Z_k=\sum_{i=1}^k|U_i-U'_i| and Dk=12E∣Zk−k3∣D_k=\frac{1}{2}\mathbb{E}|Z_k-\frac{k}{3}|. Then for every fixed kk, min⁡I(k×n)≤Dkn3+O(n2)\min I(k\times n)\le D_k n^3+O(n^2), and

Dk≤12Var⁡Zk=k62.D_k\le\frac{1}{2}\sqrt{\operatorname{Var}Z_k}=\frac{\sqrt{k}}{6\sqrt{2}}.

In particular lim sup⁡nmin⁡I/n3≤Dk\limsup_{n}\min I/n^3\le D_k in Theorem 5.

Proof. Choose r1,…,rkr_1,\ldots,r_k independently and uniformly from SnS_n, ignoring the column condition. For a fixed pair u≠vu\ne v the pairs (ci(u),ci(v))(c_i(u),c_i(v)) are independent across ii and uniform over ordered pairs of distinct columns. Realise them as ⌈nUi⌉\lceil nU_i\rceil and ⌈nUi′⌉\lceil nU'_i\rceil conditioned on being distinct, an event of probability 1−1/n1-1/n. Rounding changes each coordinate difference by less than 1. Conditioning on the kk events changes the joint law by O(k/n)O(k/n) in total variation, while ∣d−t∣=O(kn)|d-t|=O(kn). Together with t−k3=k3t-\frac{k}{3}=\frac{k}{3}, this gives E∣d(u,v)−t∣=nE∣Zk−k3∣+O(k2)\mathbb{E}|d(u,v)-t|=n\mathbb{E}|Z_k-\frac{k}{3}|+O(k^2). Summing over the (n2)\binom{n}{2} pairs, EI=Dkn3+O(n2)\mathbb{E}I=D_kn^3+O(n^2). The number QQ of clashes, that is, of triples (i,i′,j)(i,i',j) with i<i′i<i' and the same symbol in column jj of rows ii and i′i', has EQ=∑i<i′Efix⁡(ri−1ri′)=(k2)\mathbb{E}Q=\sum_{i<i'}\mathbb{E}\operatorname{fix}(r_i^{-1}r_{i'})=\binom{k}{2}. Choose an outcome with I+4knQ≤E[I+4knQ]=Dkn3+O(n2)I+4knQ\le\mathbb{E}[I+4knQ]=D_kn^3+O(n^2).

Now repair the clashes one at a time. Suppose symbol aa sits in column jj of row ii and also of another row. Swap it with the symbol bb in a column j′j' of row ii with 1≤∣j−j′∣≤2k1\le|j-j'|\le2k, chosen so that, in the other rows, aa does not occur in column j′j' and bb does not occur in column jj. At most 2k−22k-2 columns are excluded, so such a j′j' exists once n≥4kn\ge4k. The swap removes the clash of aa, creates none, and changes at most 2(n−2)2(n-2) distances by at most 2k2k each, so it changes II by at most 4kn4kn. After at most QQ swaps the rectangle is Latin, with I≤Dkn3+O(n2)I \le D_k n^3 + O(n^2). Finally, EZk=k3\mathbb{E}Z_k = \frac{k}{3} and Var⁡∣U−U′∣=16−19=118\operatorname{Var}|U-U'| = \frac{1}{6} - \frac{1}{9} = \frac{1}{18}, so the Cauchy–Schwarz inequality gives E∣Zk−k3∣≤k/18\mathbb{E}\left|Z_k - \frac{k}{3}\right| \le\sqrt{k/18}. □

The proof of Theorem 5 is a pigeonhole argument, and Figure 4a shows it at work. Clustered points are expensive, and in a low-dimensional grid clustering is unavoidable. Three remarks put the theorem in context.

Figure 4. 2×n2 \times n rectangles as point sets. (a) The proof of Theorem 5 for a 2×162 \times16 rectangle with I=422I = 422: a 4×44 \times4 grid of boxes, and in red the pairs that share a box. Each such pair is closer than the average t=34/3t = 34/3 and costs imbalance. (b) The best rectangles found by annealing for larger nn (one 2-minute run each), rescaled to the unit square. Most points lie on a few long parallel diagonal runs, with scattered extra points.

Remark 7 (Constants). For k=2k = 2, the maximum that defines c2c_2 is attained at m=5m = 5, which gives c2=4/375≈0.0107c_2 = 4/375 \approx0.0107 (lowerConst_two_five, lowerConst_two_le). Also D2=496/3645≈0.1361D_2 = 496/3645 \approx0.1361, the value for a uniformly random derangement. For k≥3k \ge3, ck=k/(12⋅4k)c_k = k/(12 \cdot4^k), attained at m=4m = 4 (lowerConst_four, lowerConst_le_four). Numerically, Dk≈0.094kD_k \approx0.094\sqrt{k} for large kk, for example D3≈0.165D_3 \approx0.165 and D12≈0.327D_{12} \approx0.327. So the lower constant is of order k4−kk4^{-k}, and the upper one grows like k\sqrt{k}. We do not know the right order in kk.

In the benchmark range, the finite-nn lower bound is weak. For 2×132 \times13 it gives 7.77.7, against the true optimum 218.6218.6, and for k=3k = 3 it becomes positive only at n=28n = 28. Its message is asymptotic. For fixed kk, the average deviation per pair, I/(n2)I/\binom{n}{2}, grows linearly in nn, the same order as the target tt itself. So rectangles are imperfect on average at the scale of tt.

Remark 8 (Squares). The bound is useless when kk grows with nn, and it must be. Spatially balanced Latin squares exist, for instance whenever 2n+12n + 1 is prime, by a construction that streamlined search itself discovered [9]. In [n]k[n]^k there is room for nn equidistant points. For squares with n≡1(mod3)n \equiv1 \pmod{3}, where perfect balance is impossible, Xia et al. [17] prove I≥4n(n−1)/9I \ge4n(n-1)/9, an order n2n^2 rather than n3n^3. The bound is attained for n≡1(mod3)n \equiv1 \pmod{3} up to n=52n = 52 [17]. It is not known whether the minimum for squares is of order at most n2n^2 for every nn. The point picture raises a natural question, which we leave open: how does the minimum imbalance pass from order n3n^3 at fixed kk to these much smaller values at k=nk = n?

Remark 9 (Equilateral sets). A perfectly balanced rectangle needs 3∣k(n+1)3 \mid k(n+1), so that tt is an integer. It is also a set of nn points in Rk\mathbb{R}^k that are pairwise equidistant in ℓ1\ell_1, that is, an equilateral set of ℓ1k\ell_1^k. Hence n≤e(ℓ1k)n \le e(\ell_1^k), the largest size of such a set. Kusner conjectured e(ℓ1k)=2ke(\ell_1^k) = 2k. The conjecture is known for k≤4k \le4, where the case k=4k = 4 is due to Koolen et al. [8]. In general, Alon and Pudlák [1] proved e(ℓ1k)=O(klog⁡k)e(\ell_1^k) = O(k \log k). The survey of Swanepoel [12] covers these results. So a perfectly balanced k×nk \times n rectangle needs k=Ω(n/log⁡n)k = \Omega(n/\log n) rows. For k≤4k \le4 this gives n≤2kn \le2k, which recovers part of the case analysis of Díaz et al. [3]. Their arguments are sharper for k≤3k \le3. Their bound k≥6−18/(n+1)k \ge6 - 18/(n+1) coincides with ours at k=4k = 4 and is vacuous for k≥6k \ge6. The point sets of rectangles are far more special than general equilateral sets, because their coordinate projections are bijections onto [n][n]. So we do not expect these bounds to be tight. We did not find this connection in the literature on balanced designs.

Two rows

For k=2k = 2 a rectangle is a derangement π=r2\pi= r_2, and the points xu=(u,π−1(u))x_u = (u,\pi^{-1}(u)) form its permutation diagram. Mirka et al. [10] solved n≤13n \le13 to optimality with a clique-based MIP and reported bounds up to n=20n = 20 after six hours. Table 3 adds our two-minute annealing runs. They improve the upper bound for 15≤n≤1915 \le n \le19, tie at n=14n = 14 and lose at n=20n = 20. At n=20n = 20, the best bound of [10] came from eight parallel six-hour runs. Our runs are single runs with one seed, and the improvements are small (0.2–2%). The MIP also spends its time on lower bounds. So the comparison shows only that annealing is a strong source of incumbents. The lower bounds remain far away, and we did not try to improve them.

nn14151617181920
lower bound [10]201.57252.6273.82252.0402.6465.3155.0
upper bound [10]268.0345.3427.3508.0617.3732.0816.0
annealing (this work)268.0344.6422.0498.0610.6722.6832.0

Table 3. 2×n2 \times n rectangles beyond the proven range. The lower and upper bounds are the best over all methods and configurations in Tables 1, 2 and 4–7 of [10], from 6-hour runs. Annealing: one 2-minute single-core run. Bold: better than the previous upper bound. The lower bounds are those reached when the 6-hour limit expired, which is why they are not monotone in nn. The values 201.57 and 273.82 come from one instance with 32 threads in their Table 6 and are decimals as reported there. All other values use the x.3x.3, x.6x.6 convention.

The shape of good permutations. Figure 4b shows the best permutations that annealing finds for n∈{24,32,48,64}n \in\{24, 32, 48, 64\}. They are not known to be optimal, but they are far from random. Most points lie on a few long parallel segments of slope 1, cyclically shifted against one another, with a minority of scattered points.

A limit object. A permuton is a probability measure on [0,1]2[0, 1]^2 with uniform marginals. Every permutation σ\sigma of [n][n] defines one, μσ\mu_\sigma, uniform on the squares [i−1n,in]×[σ(i)−1n,σ(i)n]\left[\frac{i-1}{n}, \frac{i}{n}\right] \times\left[\frac{\sigma(i)-1}{n}, \frac{\sigma(i)}{n}\right]. Put

C(μ)=12E[∥X−X′∥+∥Y−Y′∥−23],C(\mu) = \frac{1}{2}\mathbb{E}\left[\lVert X-X'\rVert+ \lVert Y-Y'\rVert- \frac{2}{3}\right],

where (X,Y)(X,Y) and (X′,Y′)(X',Y') are independent samples of μ\mu.

Proposition 10. For k=2k = 2, min⁡I/n3\min I/n^3 converges as n→∞n \to\infty to min⁡μC(μ)\min_\mu C(\mu), where the minimum over permutons is attained.

Proof. Let f(x,y,x′,y′)=∥x−x′∥+∥y−y′∥−23f(x, y, x', y') = \lVert x-x'\rVert+ \lVert y-y'\rVert- \frac{2}{3}, which is bounded and 1-Lipschitz for the ℓ1\ell_1 norm on [0,1]4[0, 1]^4. If μn→μ\mu_n \to\mu weakly then μn⊗μn→μ⊗μ\mu_n \otimes\mu_n \to\mu\otimes\mu weakly, so CC is continuous. Permutons form a weakly closed subset of the compact space of probability measures on [0,1]2[0,1]^2, so CC attains its minimum.

Fix a derangement σ\sigma of [n][n] and take the 2×n2 \times n rectangle with π=σ−1\pi=\sigma^{-1}, whose points xu=(u,σ(u))x_u=(u,\sigma(u)) are the cells of μσ\mu_\sigma. Write

I(σ)n3=12n2∑u≠v∣d(u,v)n−23∣.\frac{I(\sigma)}{n^3}=\frac{1}{2n^2}\sum_{u\ne v}\left|\frac{d(u,v)}{n}-\frac{2}{3}\right|.

Each ordered pair u≠vu\ne v corresponds to a pair of cells of μσ⊗μσ\mu_\sigma\otimes\mu_\sigma of weight 1/n21/n^2. Within these cells, ff differs from ∣d(u,v)/n−2/3∣\left|d(u,v)/n-2/3\right| by at most 2/n2/n, and ∣t/n−2/3∣\left|t/n-2/3\right| by at most 2/(3n)2/(3n). The nn diagonal cell pairs carry total weight 1/n1/n and are absent from II. Hence ∣I(σ)/n3−C(μσ)∣≤A/n\left|I(\sigma)/n^3-C(\mu_\sigma)\right|\le A/n for an absolute constant AA, uniformly in σ\sigma. This gives min⁡I/n3≥min⁡μC(μ)−A/n\min I/n^3\ge\min_\mu C(\mu)-A/n.

Conversely, let μ∗\mu^* attain the minimum. Sampling nn independent points from μ∗\mu^* and taking the induced permutation gives permutations σn\sigma_n with μσn→μ∗\mu_{\sigma_n}\to\mu^* almost surely [6]. Remove the fixed points of σn\sigma_n one at a time: if σ(j)=j\sigma(j)=j, exchange the values at jj and j′j', where j′=j+1j'=j+1 for j<nj<n and j′=n−1j'=n-1 for j=nj=n. Then σ(j)\sigma(j) becomes σ(j′)≠j\sigma(j')\ne j and σ(j′)\sigma(j') becomes j≠j′j\ne j', so no new fixed point is created. Each exchange moves two points by one cell, so it changes II by at most 4n4n, and there are at most nn of them. The resulting derangements τn\tau_n satisfy I(τn)/n3≤C(μσn)+O(1/n)→C(μ∗)I(\tau_n)/n^3\le C(\mu_{\sigma_n})+O(1/n)\to C(\mu^*).

The uniform permuton gives C=496/3645≈0.1361C=496/3645\approx0.1361, the limit for a random derangement, and the diagonal (the cyclic rectangle) gives 16/81≈0.19816/81\approx0.198. Optimising numerically over permutons made of mm increasing or decreasing segments gives 0.1480.148, 0.1330.133 and 0.1240.124 for m=3,4,5m=3,4,5. The permuton of our 2×642\times64 rectangle does better. On a pair of distinct cells, ∣X−X′∣+∣Y−Y′∣|X-X'|+|Y-Y'| is a constant plus a sum of four independent uniform variables. So C(μσ)C(\mu_\sigma) is a finite sum of explicit polynomial integrals, and exact rational arithmetic gives C(μσ)=228509453/1911029760≈0.119574C(\mu_\sigma)=228509453/1911029760\approx0.119574. This is our best upper bound for the limit. The rectangle itself has I=29988I=29988, so I/n3=0.11440I/n^3=0.11440. The diagonal cells account for almost all of the difference 0.005180.00518. They contribute 13n−13n2=0.00513\frac{1}{3n}-\frac{1}{3n^2}=0.00513 to C(μσ)C(\mu_\sigma), and the remaining 0.00005 comes from the within-cell smoothing and from t/n≠23t/n \ne\frac{2}{3}. The finite values I/n3≈0.11I/n^3 \approx0.11 in Figure 5 therefore lie below the limit estimate by about 1/(3n)1/(3n).

Figure 5. Normalised imbalance I/n3I/n^3 for k=2k=2. Black: proven optima. Grey: interval between the best lower and upper bounds of [10]. Blue dots: our annealing values. Blue dashes: C(μσ)C(\mu_\sigma) for our 2×642 \times64 rectangle, an upper bound for the limit (Theorem 10). Red: Theorem 5 at each nn (solid) and its limit c2c_2 (dashed). A uniformly random derangement has I/n3→0.1361I/n^3 \to0.1361 (dotted).

Question. What is lim⁡nmin⁡I(2×n)/n3=min⁡μC(μ)\lim_{n}\min I(2 \times n)/n^3 = \min_{\mu} C(\mu)? We know only that it lies between 4/375≈0.0114/375 \approx0.011 and 0.1196. Is the minimiser unique, and is it a finite union of segments?

Formal verification in Lean 4

Most computational results on balanced rectangles rest on unverified programs. The DRAT proofs of Peruvemba Ramaswamy and Szeider [11] are an exception, and for squares Xia et al. [17] verified their lower bound in Lean 4. We formalised the parts of this paper where formalisation is cheap and useful, in Lean 4 [2] with Mathlib [13]. The development has about 700 hand-written lines plus generated certificates. It is in the lean/ directory of the repository, and Table 4 maps the statements of the paper to Lean names.

statement in the paperLean nameuses
all rectangles (Table 1 and Table 3, Figure 1)Certificates.exists_k*_n*core
I=imb3⁡/3I = \operatorname{imb3}/3; tt is the mean distanceimbalance_eq_imb3, sum_distMathlib
identity (1)imbalance_eq_two_mul_sum_posMathlib
Theorem 5, pigeonhole boundcubic_lower_bound_ceilMathlib
Theorem 5, lim inf⁡≥ck\liminf\ge c_keventually_lower_boundMathlib
Theorem 5, lim sup⁡≤k/3\limsup\le k/3imbalance_leMathlib
c2=4/375c_2 = 4/375lowerConst_two_five, lowerConst_two_leMathlib
ck=k/(12⋅4k)c_k = k/(12 \cdot4^k), k≥3k \ge3lowerConst_four, lowerConst_le_fourMathlib
rectangles of [11, 16]Certificates.exists_pub_*core
spec = Latin arrays; non-vacuousarrayEquiv, nonempty_of_leMathlib
optimality in Theorem 2not formalised
Theorems 4, 6 and 10not formalised

Table 4. Table 4. Formalised statements. Names are relative to the namespace BalancedLatin; theorems about a rectangle are in its sub-namespace LatinRect. “Core”: the proof uses only Lean’s core library and the 74-line specification Defs.lean; “Mathlib”: it also uses Mathlib. The certificates use only the axiom propext; the theorems use the three standard axioms propext, Classical.choice and Quot.sound. No statement uses sorry or native_decide.

Specification. The file Defs.lean contains the whole specification that the certificates rely on. It imports only Lean’s core library, not Mathlib. It uses the point picture of § 3: a rectangle is the function (i,u)↦ci(u)(i,u) \mapsto c_i(u), with indices starting at 0.

structure LatinRect (k n : Nat) where
  col : Fin k → Fin n → Fin n             -- col i u = column of symbol u in row i
  row_inj : ∀ i u v, col i u = col i v → u = v
  col_inj : ∀ u i j, col i u = col j u → i = j

def dist (L : LatinRect k n) (u v : Fin n) : Nat :=      -- d(u, v) = ∑ᵢ |cᵢ(u) − cᵢ(v)|
  fsum fun i => absDiff (L.col i u).val (L.col i v).val

def imb3 (L : LatinRect k n) : Nat :=                    -- 3I = ∑ᵤ₍ᵥ |3d(u, v) − k(n + 1)|
  fsum fun u => fsum fun v =>
    if u < v then ((3 * L.dist u v : Int) - k * (n + 1)).natAbs else 0

Here fsum f is the sum of the list [f 0, ..., f (n-1)], and absDiff a b is (a−˙b)+(b−˙a)=∣a−b∣(a \mathbin{\dot-} b)+(b\mathbin{\dot-} a) = |a-b|, with truncated subtraction −˙\mathbin{\dot-} on N. We certify the integer 3I3I, so that the kernel never handles fractions. In Cubic.lean, we define the imbalance II over Q\mathbb{Q} exactly as in § 3, and imbalance_eq_imb3 proves I=imb3⁡/3I = \operatorname{imb3}/3.

Certificates by kernel evaluation. A script copies each rectangle from its data file into Lean, after cross-checking the claimed value with the independent Python checker. For Figure 1 it produces

def rows_k3_n9 : List (List Nat) :=
  [[1, 2, 3, 4, 5, 6, 7, 8, 9], [8, 3, 1, 6, 7, 4, 5, 9, 2], [4, 5, 8, 1, 9, 3, 2, 6, 7]]

def rect_k3_n9 : LatinRect 3 9 where
  col := colOfRows rows_k3_n9
  row_inj := by decide +kernel
  col_inj := by decide +kernel

theorem imb3_k3_n9 : rect_k3_n9.imb3 = 168 := by decide +kernel
theorem exists_k3_n9 : ∃ L : LatinRect 3 9, L.imb3 = 168 := ⟨rect_k3_n9, imb3_k3_n9⟩

The tactic decide +kernel is proof by reflection. The proposition has a decision procedure, written in Lean, and the kernel itself reduces that procedure to true while type-checking the proof term. The alternative, native_decide, runs compiled code. It adds the axiom Lean.ofReduceBool, so it trusts the compiler and every implemented_by annotation. Our certificates avoid it, and #print axioms reports only propext.

The soundness of a statement such as exists_k3_n9 does not depend on the script or on how colOfRows reads the data. For any function passed as col, the kernel checks that it is a Latin rectangle with the stated value of 3I3I. To tie each certificate to its data file, a further theorem faithful_k3_n9 checks that the entry of row ii in column col i u is the symbol u+1u+1 of the file. Lean certifies all 62 rectangles: the 51 of Table 1 and the eleven 2×n2 \times n rectangles with 14≤n≤6414 \le n \le64 used in Table 3 and Figure 4 and Figure 5. The largest are 12×1312 \times13 and 2×642 \times64, which has 2016 pairs. Elaborating all of them takes about 50 s of CPU time on an Apple M3 laptop. As a negative test, changing the claimed value by one, placing a symbol twice in a column, or repeating a symbol in a row each makes the check fail.

Cubic growth. Cubic.lean (480 lines, 14 s) proves Theorem 5. The main statements read

theorem cubic_lower_bound (L : LatinRect k n) (s M : ℕ) (hs : 0 < s) (hM : n ≤ M * s)
    (ht : (k : ℚ) * (s - 1) ≤ target k n) :
    (n : ℚ) * (n / (M : ℚ) ^ k - 1) * (target k n - k * (s - 1)) ≤ L.imbalance

theorem eventually_lower_bound (k m : ℕ) (hm : 3 ≤ m) {ε : ℚ} (hε : 0 < ε) :
    ∀ n in Filter.atTop, ∀ L : LatinRect k n,
      (lowerConst k m - ε) * (n : ℚ) ^ 3 ≤ L.imbalance

where target k n is t=k(n+1)/3t = k(n+1)/3 and lowerConst k m is km−k(1/3−1/m)k m^{-k}(1/3 - 1/m). The first is slightly more general than Theorem 5: it allows any MM intervals per axis with n≤Msn \le Ms. Its instance M=⌈n/s⌉M = \lceil n/s \rceil, cubic_lower_bound_ceil, is Theorem 5 word for word. The second states the liminf bound in the eventually form, for each mm, so we do not have to define min⁡I\min I as a function of nn. The proof follows the paper. It reindexes along the row permutations (Fintype.sum_bijective) to show that tt is the average distance. It then symmetrises the sum over u<vu < v to one over ordered pairs, and uses Mathlib’s sq_sum_le_card_mul_sum_sq for Cauchy–Schwarz.

Is the specification the right one? A formal proof is only as good as its statement. A definition that differs subtly from the intended one would make every certificate meaningless. We guard against this in four ways. (i) Agreement with the literature. Lean certifies the 14 rectangles printed in [11, 16], of sizes 3×43 \times4 to 12×1312 \times13, with the imbalances that those papers report (Certificates.exists_pub_*). This tests the definitions of dd and II against independent data, not against our own Python checker. (ii) Agreement with the textbook definition. arrayEquiv is a bijection between LatinRect k n and arrays AA (row ii, column jj) whose rows are permutations and whose columns have no repeats. ofArray_col shows that col i u is the column of symbol uu in row ii, that is, ci(u)c_i(u). (iii) Non-vacuity. nonempty_of_le shows that LatinRect k n is inhabited for every k≤nk \le n, so the universally quantified theorems are not vacuous. (iv) Agreement with the paper. A test parses Table 1 and Table 3 and the values quoted in the text for 3×93 \times9, 2×162 \times16 and 12×1312 \times13, and compares them with the Lean statements. It also compares every rectangle printed in Section A, entry by entry, with the rows of its certificate. Changing one of these printed values makes it fail.

What is not formalised. The optimality half of Theorem 2 is the main gap. The branch and bound visits 5.5⋅1095.5 \cdot10^9 nodes, far more than kernel evaluation can handle. A certificate would need one of two routes. The first is a branch and bound written and proved correct in Lean and then run with native_decide, which moves the trust from our C program to Lean’s compiler. The second is a SAT encoding with an LRAT proof that a verified checker accepts. Either route also has to prove the symmetry reduction of § 6. Theorem 10 needs permutons and the sampling theorem of Hoppen et al. [6], which Mathlib does not have. Theorem 6 needs an asymptotic estimate of ∣EZk−k3∣|\mathbb{E}Z_k - \frac{k}{3}| for discretised uniform variables. Theorem 9 rests on the theorem of Alon and Pudlák [1]. Theorem 4 is elementary, but we computed the row groups in Figure 3 with SymPy’s Schreier–Sims implementation, and they are not certified.

Discussion

The point picture says that balance is a packing problem in ℓ1\ell_1, so moving points is the natural search move. It also gives the right scale. For a fixed number of rows, imbalance is not a small defect that clever search will remove. It is a quantity of order n3n^3, and its leading constant is the real object of study. The row group adds a cheap check that a rectangle is not built from a group table.

Limitations. The new upper bounds are best-of-runs from at most three runs per instance, and single runs vary by up to a third (§ 5). We did not isolate the effect of the adaptive penalty or rerun earlier local search head-to-head. We also make no runtime comparison with earlier work. The optimality of 3×93 \times9 rests on two uncertified programs that share a branching scheme. In contrast, Lean checks every upper bound and the pigeonhole theorem. Our lower-bound constant is far from the observed values for k=2k = 2 and is negligible in the benchmark range.

Open problems

  1. Certify Theorem 2, for instance with a DRAT-producing SAT encoding as in [11] or with a branch and bound verified in Lean (§ 10). Also settle 5×85 \times8 to 7×87 \times8. The sharper bound and the unused column-reversal and row symmetries of § 6 are natural first steps. Our new upper bounds are natural starting incumbents for certified solvers. The mirror pairing u↔n+1−uu \leftrightarrow n + 1 - u seen in several records is a candidate streamliner in the sense of [16].

  1. Close the gap between c2=0.0107c_2 = 0.0107 and 0.11960.1196. A sharper lower bound might weight each close pair by its shortfall t−dt - d instead of the worst case inside a box. The limit problem is a quadratic minimisation over permutons. One route to a certified lower bound is to discretise it to doubly stochastic matrices and apply a semidefinite relaxation.

  1. Determine the minimising permuton for k=2k = 2.

  1. Find the order in kk of the constants in Theorem 5, between k4−kk4^{-k} and k\sqrt{k}. Also find how the minimum passes to order n2n^2 for squares.

  1. Show directly that a perfectly balanced k×nk \times n rectangle needs k≥n/2k \ge n/2, using that its coordinate projections are bijections. This would follow from Kusner’s conjecture for ℓ1\ell_1, a long-standing problem in geometry, but it may be easier for these special point sets.

Data and code. Rectangles, the annealing code, the branch and bound, the exact checker, the Lean development and the scripts for every figure are at https://github.com/BrianLi009/Balanced-Latin-Rectangles. The new rectangles are listed in Section A, and all 62 are in the ancillary file anc/rectangles.txt.

The new rectangles

This appendix lists the 33 rectangles that improve Table 1 and the seven 2×n2 \times n rectangles of Table 3. Rows are listed from top to bottom, entry jj of a row is the symbol in column jj, and the first row is always the identity. Each heading gives the new imbalance in bold and, in grey, the previous best value of [16] and the relative improvement. As in Figure 1, each symbol has its own colour, so every row shows all nn colours and no colour repeats within a column. Each rectangle is a file of the repository named by its size: the 4×94 \times9 rectangle, for example, is results/rectangles/k4_n9.txt (the 2×n2 \times n ones are in results/k2_large/). Lean certifies it as Certificates.exists_k4_n9, and Certificates.faithful_k4_n9 ties the certificate to the file (§ 10). A test in the repository checks this list against the certificates entry by entry. All 62 rectangles of the paper, including the matched records and the 2×n2 \times n rectangles with n≥24n \ge24, are in the ancillary file anc/rectangles.txt.

n=9n = 9

123456789
517392648
278543916
385629174

Table 5. 4×94 \times9: 53.3 (56.0, −4.8%)

123456789
945271836
269184573
714693258
482739615

Table 6. 5×95 \times9: 48.6 (52.6, −7.6%)

123456789
384172956
745931268
491865372
936247815
617398524

Table 7. 6×96 \times9: 40.0 (48.0, −16.7%)

123456789
619348527
294865371
935712468
851927634
382679145
748193256

Table 8. 7×97 \times9: 43.3 (51.3, −15.6%)

123456789
842973516
456297138
937514862
764381295
691845327
578162943
385629471

Table 9. 8×98 \times9: 42.6 (53.3, −20.0%)

n=10n = 10

12345678910
83692754101
37105189264
58439102176
95163410782
74918361025

Table 10. 6×106 \times10: 60.0 (70.0, −14.3%)

12345678910
64791210385
31041789562
81963541027
57139106248
93278456101
49510218736

Table 11. 7×107 \times10: 58.0 (72.0, −19.4%)

12345678910
86429110357
71106834925
27694103581
10825376419
39876512104
65911082743
54781291036

Table 12. 8×108 \times10: 58.6 (82.6, −29.0%)

12345678910
71109348562
96271531048
68151039724
10362784159
45710692381
39468712105
21098415673
87539210416

Table 9 × 10. 9 × 10: 64.0 (70.0, −8.6%)

n=11n = 11

1234567891011
4310116851297
9642111107835
8459110211376

Table 4 × 11. 4 × 11: 104.0 (112.0, −7.1%)

1234567891011
8321174610159
3107511186294
7189210354116
1084163911725

Table 5 × 11. 5 × 11: 94.0 (116.0, −19.0%)

1234567891011
1146178103259
8311195641072
3679111210485
4798231156110
7511310419826

Table 6 × 11. 6 × 11: 88.0 (108.0, −18.5%)

1234567891011
3510111467298
6114398151027
9176103548112
5692117310184
8361021119745
1042965811173

Table 7 × 11. 7 × 11: 84.0 (118.0, −28.8%)

1234567891011
2811567410193
8476395211110
6921071835114
1075328911461
3116712104859
7519114261038
5610183119742

Table 8 × 11. 8 × 11: 78.0 (114.0, −31.6%)

1234567891011
7361081954112
6825791110341
3117298411065
8451131062197
5710111284639
1161947538210
9583111106274
4109625311718

Table 9 × 11. 9 × 11: 84.0 (120.0, −30.0%)

1234567891011
5712101194368
3851011246791
8171193526410
7611321019584
6108145117239
1154961310827
1049738251116
2965871011413
4112819631075

Table 10 × 11. 10 × 11: 100.0 (110.0, −9.1%)

n=12n = 12

123456789101112
510982111126347
691071212115438

Table 3 × 12. 3 × 12: 152.0 (154.0, −1.3%)

123456789101112
491116587212310
635912104181127
511621012147398

Table 4 × 12. 4 × 12: 149.3 (154.6, −3.4%)

123456789101112
118631941210752
965123112101874
371154121982610
831229764111105

Table 5 × 12. 5 × 12: 140.0 (145.3, −3.7%)

7×127 \times12: 121.3 (164.0, −26.0%)

123456789101112
311782491061215
819271235104611
931058111627124
296111275318410
107169312481152
754911110212386

Table 13.

8×128 \times12: 116.6 (148.0, −21.2%)

123456789101112
739111126542108
351061229711481
101697541228311
861234912101157
945810311161272
611472103981125
412710318115629

Table 14.

9×129 \times12: 106.0 (154.0, −31.2%)

123456789101112
941251781032611
212101756118943
792831256114101
111738410125629
810524119171236
107469211312158
681910312421175
539101112768124

Table 15.

10×1210 \times12: 124.0 (174.6, −29.0%)

123456789101112
121682109115374
481239151011267
867935102121141
511916712348102
974210118611235
645101292731811
105871411122693
712251183469110
310116712418529

Table 16.

11×1211 \times12: 136.6 (147.3, −7.2%)

123456789101112
374109121651128
241211695103817
111051486712392
812103154112769
931157481262101
711121210938456
592810712416311
619128113275410
125763210111984
106871132941125

Table 17.

n=13n = 13

4×134 \times13: 201.3 (211.3, −4.7%)

12345678910111213
74115911213328106
31110178561312429
51027131239111648

Table 18.

5×135 \times13: 191.3 (210.6, −9.2%)

12345678910111213
29111812376513410
61175122113103498
73691311101241285
12496712101385113

Table 19.

6×136 \times13: 166.0 (204.0, −18.6%)

12345678910111213
11176101224138539
81019211512374136
10365121913728411
26911131045137812
75102313811611294

Table 20.

7×137 \times13: 164.0 (203.3, −19.3%)

12345678910111213
38610112119213457
71116139341058212
13682114101712593
51011382911371246
11458313171221069
89411256131132710

Table 21.

8×138 \times13: 160.0 (220.6, −27.5%)

12345678910111213
13151064391187212
10411672121315893
91011225867413311
11582103134129671
49751113210311286
26139811415123107
51261139102137148

Table 22.

9×139 \times13: 152.0 (214.0, −29.0%)

12345678910111213
36111384971122510
81357122311461091
91812311251061374
51113710491312826
13310295847111261
10871631221113954
27961113110583412
11428101131265937

Table 23.

10 × 13: 154.6 (240.6, −35.7%)
12345678910111213
73129810111256134
81151337141021296
41221175968131310
12185496131131027
67481312321115109
25131210389674111
10862111127134953
91317281054123611
51076121131139248

Table 24.

11 × 13: 168.0 (224.0, −25.0%)
12345678910111213
12510672131311948
31112581024197136
10643131182127159
41297231161011385
11961315312482107
13378911051112462
68293121375410111
87111641213235910
54132117910861213
21311210849653711

Table 25.

12 × 13: 166.0 (274.0, −39.4%)
12345678910111213
12872101613394511
41210313211586179
91127124531316810
21398651012473111
39113812471011562
87135113210141296
11112621384539107
51041981211613723
13461071119258312
76512391311121048
63811410927121315

Table 26.

k=2k = 2, 14≤n≤2014 \le n \le20

2 × 14: 268.0
1234567891011121314
7821111213456143910

Table 27.

2 × 15: 344.6
123456789101112131415
212108651541431311197

Table 28.

2 × 16: 422.0
12345678910111213141516
91112231551667810141134

Table 29.

2 × 17: 498.0
1234567891011121314151617
1315417278910111211431656

Table 30.

2 × 18: 610.6
123456789101112131415161718
641621411211109871851731513

Table 31.

2 × 19: 722.6
12345678910111213141516171819
65171621131211910871918431514

Table 32.

2 × 20: 832.0
1234567891011121314151617181920
4316114191211109872051817215613

Table 33.

References

  1. [1]Noga Alon and Pavel Pudlák. Equilateral sets in lⁿₚ. Geometric and Functional Analysis, 13(3):467–482, 2003. doi: 10.1007/S00039-003-0418-7.
  2. [2]Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction – CADE 28, volume 12699 of Lecture Notes in Computer Science, pages 625–635. Springer, 2021. doi: 10.1007/978-3-030-79876-5_37.
  3. [3]Mateo Díaz, Ronan Le Bras, and Carla P. Gomes. In search of balance: The challenge of generating balanced Latin rectangles. In Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2017), volume 10335 of Lecture Notes in Computer Science, pages 68–76. Springer, 2017. doi: 10.1007/978-3-319-59776-8_6.DOI
  4. [4]Fred Glover and Jin-Kao Hao. The case for strategic oscillation. Annals of Operations Research, 183(1):163–173, 2011. doi: 10.1007/s10479-009-0597-1.
  5. [5]Carla P. Gomes and Meinolf Sellmann. Streamlined constraint reasoning. In Principles and Practice of Constraint Programming (CP 2004), volume 3258 of Lecture Notes in Computer Science, pages 274–289. Springer, 2004. doi: 10.1007/978-3-540-30201-8_22.DOI
  6. [6]Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio. Limits of permutation sequences. Journal of Combinatorial Theory, Series B, 103(1):93–113, 2013. doi: 10.1016/j.jctb.2012.09.003.DOI
  7. [7]Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983. doi: 10.1126/science.220.4598.671.DOI
  8. [8]Jack Koolen, Monique Laurent, and Alexander Schrijver. Equilateral dimension of the rectilinear space. Designs, Codes and Cryptography, 21:149–164, 2000. doi: 10.1023/A:1008391712305.DOI
  9. [9]Ronan Le Bras, Carla P. Gomes, and Bart Selman. From streamlined combinatorial search to efficient constructive procedures. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pages 499–506, 2012. doi: 10.1609/aaai.v26i1.8147.
  10. [10]Renee Mirka, Laura Greenstreet, Marc Grimson, and Carla P. Gomes. A new approach to finding 2 × n partially spatially balanced Latin rectangles (short paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), volume 280 of LIPIcs, pages 47:1–47:11. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPIcs.CP.2023.47.DOI
  11. [11]Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider. Proven optimally-balanced Latin rectangles with SAT (short paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), volume 280 of LIPIcs, pages 48:1–48:10. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPIcs.CP.2023.48.DOI
  12. [12]Konrad J. Swanepoel. Equilateral sets in finite-dimensional normed spaces, 2004. arXiv:math/0406264.DOI
  13. [13]The mathlib Community. The Lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), pages 367–381. ACM, 2020. doi: 10.1145/3372885.3373824.DOI
  14. [14]H. M. van Es and C. L. van Es. Spatial nature of randomization and its effect on the outcome of field experiments. Agronomy Journal, 85(2):420–428, 1993. doi: 10.2134/agronj1993.00021962008500020046x.DOI
  15. [15]Florentina Voboril and Stefan Szeider. Improving constraint models with LLM agents, 2026. arXiv:2608.08127.arxiv.org/abs/2608.08127
  16. [16]Florentina Voboril, Vaidyanathan Peruvemba Ramaswamy, and Stefan Szeider. Balancing Latin rectangles with LLM-generated streamliners. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), volume 340 of LIPIcs, pages 36:1–36:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.CP.2025.36.DOI
  17. [17]Hai Xia, Carla P. Gomes, Bart Selman, and Stefan Szeider. Agentic neurosymbolic collaboration for mathematical discovery: A case study in combinatorial design, 2026. arXiv:2603.08322.arxiv.org/abs/2603.08322
  18. [18]Zhenxuan Xie, Zhipeng Lü, Zhouxing Su, Chu-Min Li, Junwen Ding, and Yuxuan Wang. A swap relaxation-based local search for the Latin square completion problem. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24), pages 7047–7055, 2024. doi: 10.24963/ijcai.2024/779.DOI
  19. [19]Cheng Zhang and Jianpeng Ma. Counting solutions for the N-queens and Latin square problems by efficient Monte Carlo simulations, 2008. arXiv:0808.4003.DOI

Paper details

vlnc:W_kv7dyuc5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents