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

Oct 23, 2026

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

Classical optimization and learning-guided search offer complementary approaches to open problems in discrete mathematics, but their outputs are difficult to compare when search spaces, validity checks, and stopping rules differ. We present RadonBench, a benchmark for constructing maximum-cardinality Radon-free lattice configurations: finite subsets of Zd\mathbb{Z}^d admitting no integral Radon partition. It remains open whether Radon-free configurations with 1111 points in Z3\mathbb{Z}^3 or 2121 points in Z4\mathbb{Z}^4 are possible. If they exist, they would improve the corresponding lower bounds on the integer Radon numbers. We compare exhaustive extension, greedy local search, PatternBoost, AlphaZero, and AlphaEvolve. All outputs use one success predicate: a convex target-sized configuration succeeds exactly when its number of integral Radon points is zero. PatternBoost and AlphaZero construct verified Radon-free configurations of sizes 1010 and 2020, one point short of the respective targets; AlphaZero's best convex target terminals have two integral Radon points in both dimensions. Exhaustive extension over fixed seeds and declared finite search boxes likewise reaches a minimum of two integral Radon points. Greedy local search and AlphaEvolve each produce target-sized near misses with one integral Radon point. No audited run reaches zero. These results establish reproducible near-miss baselines over explicitly scoped search domains.
Oct 26, 2026

Mapping the Solution-Set Structure of Grokking on Latin Squares

Grokking is a delayed transition from memorisation to generalisation. A network first fits observed examples while remaining near chance on held-out inputs, then generalises abruptly. Prior work has focused mainly on this delay, finding that the network's main loss becomes weight decay after the fitting phase. We name the solution to this optimization problem as the minimum-norm endpoint, and study which tasks make all minimum-norm endpoints generalise from partial observations. Specifically, we model pairwise input tasks as edge colourings of Kq,qK_{q,q}, with Latin colourings as our structured family, and classify each observed instance as all-good, mixed, or no-good by its endpoint set. Furthermore, we prove two contrasting results: (1) Finite-abelian-group families are asymptotically all-good from partial observations; (2) Under a uniform random Latin square, all-good tasks become asymptotically rare for observation-based learners, leaving mixed or no-good behaviour. Moreover, experiments show that relabellings of addition generalise despite their dense polynomial representations. Finally, on tasks of composite order, finite-training results suggest that predictors learn a coarse part of the output before the full label.
Jul 1, 2026

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

SAT solvers settle combinatorial problems beyond the reach of interactive theorem provers and produce LRAT certificates for independent verification. We present LRAT-Catcher, a standalone, general-purpose tool that imports a DIMACS formula together with an LRAT certificate into Lean 4 as a theorem. LRAT-Catcher runs the formally verified LRAT checker from Lean core as compiled native code via reflection. This scales to instances where Mathlib's explicit proof-term import exhausts memory. LRAT-Catcher also composes cube-and-conquer solving runs entirely inside Lean. Per-cube refutations are combined with a cover-completeness certificate, itself an LRAT proof, into a single unsatisfiability theorem. Verified encodings connect CNF-level results to the original combinatorial problems. We evaluate the tool against Mathlib's proof-term import and the external checker cake_lpr on establishing the Schur number S(4) = 44 and the Ramsey number R(4,4) = 18 as Lean theorems.