/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 725

References:

    erdosproblems.com/725

    [Er81] Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25-42. PDF

    [ErKa46] Erdős, P. and Kaplansky, I., The asymptotic number of Latin rectangles. Amer. J. Math. 68 (1946), 230-236. PDF

    [Ya51] Yamamoto, K., On the asymptotic number of Latin rectangles. Jpn. J. Math. 21 (1951), 113-119.

@[expose] public sectionopen Filter Asymptoticsnamespace Erdos725

M is a $k\times n$ Latin rectangle: M i j is the entry in row i and column j, the entries are in Fin n (standing for ${1,\dots,n}$), every row is a permutation of the entries, and no entry is repeated in a column.

abbrev IsLatinRectangle {k n : ℕ} (M : Fin k → Fin n → Fin n) : Prop := (∀ i, Function.Injective (M i)) ∧ ∀ j, Function.Injective fun i ↦ M i j

$L(k,n)$ is the number of $k\times n$ Latin rectangles. Rows, columns and entries are labelled and the rows are ordered. It is $0$ for $k>n\geq 1$ and $1$ for $k=0$.

noncomputable def L (k n : ℕ) : ℕ := Nat.card {M : Fin k → Fin n → Fin n // IsLatinRectangle M}

There are $n!$ Latin rectangles with one row.

All goals completed! 🐙def erdos_725.answer : ℕ → ℕ → ℝ := sorry

Give an asymptotic formula for the number of $k\times n$ Latin rectangles.

The formula $F(k,n)$ must satisfy $L(k,n)\sim F(k,n)$ as $n\to\infty$ for every choice of $k=k(n)\leq n$, so it also covers Latin squares ($k=n$).

@[category research open, question value, AMS 5] theorem erdos_725 (k : ℕ → ℕ) (hk : ∀ n, k n ≤ n) : (fun n ↦ (L (k n) n : ℝ)) ~[atTop] fun n ↦ erdos_725.answer (k n) n := k:ℕ → ℕhk:∀ (n : ℕ), k n ≤ n⊢ (fun n ↦ ↑(L (k n) n)) ~[atTop] fun n ↦ erdos_725.answer (k n) n All goals completed! 🐙

Erdős and Kaplansky [ErKa46] proved the count is $$\sim e^{-\binom{k}{2}}(n!)^k$$ when $k=o((\log n)^{3/2-\epsilon})$.

Here $\epsilon>0$ is fixed.

@[category research solved, AMS 5] theorem erdos_725.variants.erdos_kaplansky (ε : ℝ) (hε : 0 < ε) (k : ℕ → ℕ) (hk : (fun n ↦ (k n : ℝ)) =o[atTop] fun n ↦ Real.log n ^ (3 / 2 - ε)) : (fun n ↦ (L (k n) n : ℝ)) ~[atTop] fun n ↦ Real.exp (-((k n).choose 2 : ℝ)) * (n.factorial : ℝ) ^ k n := ε:ℝhε:0 < εk:ℕ → ℕhk:(fun n ↦ ↑(k n)) =o[atTop] fun n ↦ Real.log ↑n ^ (3 / 2 - ε)⊢ (fun n ↦ ↑(L (k n) n)) ~[atTop] fun n ↦ Real.exp (-↑((k n).choose 2)) * ↑n.factorial ^ k n All goals completed! 🐙

Yamamoto [Ya51] extended this to $k\leq n^{1/3-o(1)}$.

As in [Ya51, p. 113], we assume $k<n^{1/3-\delta}$ with $n^{-\delta}\to 0$, where $\delta$ may be a positive constant or a function of $n$.

@[category research solved, AMS 5] theorem erdos_725.variants.yamamoto (δ : ℕ → ℝ) (hδ : Tendsto (fun n : ℕ ↦ (n : ℝ) ^ (-δ n)) atTop (nhds 0)) (k : ℕ → ℕ) (hk : ∀ᶠ n in atTop, (k n : ℝ) < (n : ℝ) ^ (1 / 3 - δ n)) : (fun n ↦ (L (k n) n : ℝ)) ~[atTop] fun n ↦ Real.exp (-((k n).choose 2 : ℝ)) * (n.factorial : ℝ) ^ k n := δ:ℕ → ℝhδ:Tendsto (fun n ↦ ↑n ^ (-δ n)) atTop (nhds 0)k:ℕ → ℕhk:∀ᶠ (n : ℕ) in atTop, ↑(k n) < ↑n ^ (1 / 3 - δ n)⊢ (fun n ↦ ↑(L (k n) n)) ~[atTop] fun n ↦ Real.exp (-↑((k n).choose 2)) * ↑n.factorial ^ k n All goals completed! 🐙end Erdos725