Skip to content

Erdős Problem #725

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: combinatorics.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Count labelled ordered k×n Latin rectangles on n symbols: each row a permutation, and entries within a column all distinct. Erdős asks for a general asymptotic formula as n grows, particularly when k increases with n; the maintained page remains OPEN. A catalogue comment correctly warns that OEIS A001009 records a reduced/normalized count, not this fully labelled \(L_{k,n}\).

A small example

For k=1 there are n! rectangles. For k=2, after choosing the first row in n! ways, the second row must be a derangement relative to it, giving \(L_{2,n}=n!\,D_n\). At n=3 the number is 6×2=12, whereas (3!)²=36 would ignore column collisions. This is an exact combinatorial count.

What is known

Erdős–Kaplansky 1946 found \(L_{k,n}\sim e^{-\binom{k}{2}}(n!)^k\) when k is much smaller than (log n)^(3/2). Yamamoto widened the range. PRIMARY publisher Godsil–McKay, 'Asymptotic enumeration of Latin rectangles', Journal of Combinatorial Theory B 48 (1990) 19–44, DOI 10.1016/0095-8956(90)90128-M, proved the asymptotic

\[ L_{k,n}\sim(n!)^k((n)_k/n^k)^n(1-k/n)^{-n/2}e^{-k/2}. \]

The theorem applies in the range \(k=o(n^{6/7})\). NEW external preprint by Eric Li, 'The Godsil–McKay Asymptotic for Latin Rectangles in the Sublinear Range of Erdős Problem 725', arXiv:2608.01671 (August 2026), claims an extension to the range

\[ k=o(n) \]

with a corrected exponential factor

\[ \exp\{[n(H_n-H_{n-k})-k]/2\} \]

and log-relative error \(O(k^2/n^2)\), reported formalized in Lean. This later result is primary author abstract evidence, not a GCL-replayed kernel certificate or a proof for k comparable to n.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition PARTIAL. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: Li's claimed k=o(n) Latin-rectangle asymptotic extension and Lean report remain external; distinguish labeled/reduced counts and prior k=o(n^(6/7)).

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

Reconcile Godsil–McKay's 1990 formula with Li's August 2026 sublinear extension and the exact \(L_{2,n}=n!\,D_n\) finite count; check reduction to fixed k and all asymptotic uniformity ranges. Source-lock original papers and external Lean axioms before formal accreditation; do not mark the full k≈n problem solved.

Sources and claim boundaries

Maintained Erdős #725; GCL source report. Original historical theorem pages and full formal proof chain not independently inspected; no newly certified theorem proof, public MathJax QA or V2 admission.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1996 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction