The Godsil--McKay Asymptotic for Latin Rectangles in the Sublinear Range of Erdős Problem 725

Abstract

Erdős Problem 725 asks for an asymptotic formula for the number $L_{k,n}$ of ordered, labelled $k\times n$ Latin rectangles. Godsil and McKay proved that $L_{k,n}\sim (n!{)}^k((n{)}_k/n^k{)}^n(1-k/n{)}^{-n/2}{e}^{-k/2}$ for $k=o(n^{6/7})$. We provide a partial solution to Erdős Problem 725 by proving this asymptotic for every $k=o(n)$. More precisely, set ${\tilde{A}}_{k,n}=(n!{)}^k((n{)}_k/n^k{)}^n\exp \{[n(H_n-H_{n-k})-k]/2\}$. For every $K(n)=o(n)$, uniformly for $0\le k\le K(n)$, we prove $\log (L_{k,n}/{\tilde{A}}_{k,n})=O(k^2/n^2)$, with an absolute implied constant. The results of this paper have been formally verified in Lean.

25 pages. The results have been formally verified in Lean. Formalisation: https://github.com/ericlisg/erdos725partial-lean