ERDŐS/DAILY ▸

← back to the ledger

ERDőS #725 · PARTIAL

Erdős problem #725: live gate, current asymptotics, a uniform reduction, and exact small cases

Access/search date: 2026-07-28 UTC.

Result in one paragraph

The live page is open and has no claimed proof or current worker, so the collision gate did not fire. The page is materially behind its own only comment: Godsil and McKay proved in 1990 a relative asymptotic formula for the unrestricted count \(L(k,n)\) throughout \(k=o(n^{6/7})\). I verified the formula and range in the authors' primary scan. I did not find a later published theorem with a wider range; 2017 and 2025 conference abstracts announce joint work by Leckey, Liebenau, and Wormald but give no theorem statement or public manuscript. The new work in this report is not a solution. It consists of (i) a clean exact reduction \(L=B\exp\theta\), together with a uniform explicit interval for \(\theta\) and a fixed-density logarithmic asymptotic, and (ii) a from-scratch exact enumeration. The latter independently reproduces the entire reduced triangle through \(n=6\), computes \(R(4,7)=1{,}293{,}216\), and proves computationally that a normalized \(3\times7\) rectangle has exactly 144 or 148 possible fourth rows, with weighted multiplicities \(932{,}640\) and \(141{,}120\). The literal problem contains \(k=n\), hence relative asymptotic enumeration of Latin squares; the permanent sandwich loses \(\exp(O(n\log ^2n))\) there. The missing ingredient is an average-permanent/point-probability estimate with cumulative logarithmic error \(o(1)\), not another finite enumeration.

Claims are labelled as requested:

claims;

0. Mandatory live-page gate

I fetched the live problem page, its LaTeX view, and the only discussion thread through the Bright Data cloud-browser path. Ordinary datacenter retrieval was not used for this gate.

The rendered live status was OPEN. It displayed:

Therefore none of the mandatory stop conditions applies.

Verbatim current statement

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

Results and references displayed on the page

The live LaTeX page states that Erdős--Kaplansky proved

\[ L(k,n)\sim e^{-\binom{k}{2}}(n!)^k \]

when \(k=o((\log n)^{3/2-\epsilon})\), and that Yamamoto extended this to \(k\le n^{1/3-o(1)}\). It links A001009 and gives exactly these references:

American Journal of Mathematics (1946), 230--236;

Japanese Journal of Mathematics (1951), 113--119.

The page also gives its standard warning that OPEN reflects the site owner's belief and may omit relevant literature.

Everything material in the sole comment

The comment is by AronBhalla, posted 12:51 on 24 April 2026. It says the page should include Godsil--McKay (1990), defines \(L_{k,n}\) as the unrestricted count, and states

\[ L_{k,n}\sim (n!)^k \left(\frac{(n)_k}{n^k}\right)^n \left(1-\frac{k}{n}\right)^{-n/2}e^{-k/2} \quad\text{for }k=o(n^{6/7}). \]

It also warns that OEIS A001009 records reduced/normalised counts, not unrestricted \(L_{k,n}\). The site explicitly labels comments as unverified. Both points are checked independently below. [A: faithful live-page transcription, not an endorsement of comment correctness.]

1. Conventions and the normalization issue

A \(k\times n\) Latin rectangle here has symbols \([n]\), every row is a permutation of \([n]\), and no column repeats a symbol. Define:

\((1,2,\ldots,k)^\mathsf T\).

Then

\[ L(k,n)=n!K(k,n) =n!\frac{(n-1)!}{(n-k)!}R(k,n). \tag{1} \]

Indeed, a unique column permutation normalizes the first row. Among normalized rectangles there are

\[ (n-1)_{k-1}=\frac{(n-1)!}{(n-k)!} \]

possible ordered first columns, and simultaneous symbol/column relabelling bijects the classes belonging to any two such columns. [A]

The current OEIS A001009 page calls its entries “normalized” but gives the triangle

\[ \begin{array}{c} 1\\ 1\quad1\\ 1\quad1\quad1\\ 1\quad3\quad4\quad4\\ 1\quad11\quad46\quad56\quad56\\ \cdots, \end{array} \]

which is \(R(k,n)\) under the explicit convention above. For example, \(K(2,4)\) is the derangement number \(9\), whereas the OEIS entry is \(R(2,4)=9/3=3\). Thus the comment's substantive normalization warning is correct. Formula (1), not terminology, removes the ambiguity. [A]

2. Primary-source literature check

Erdős--Kaplansky and Yamamoto

The primary Erdős--Kaplansky scan exists and its Theorem 2 gives the displayed classical formula in the \((\log n)^{3/2-\epsilon}\) range. The paper itself says the motivation is to approach Latin squares and conjectures a break around \(n^{1/3}\). [B, primary-source transcription.]

The primary Yamamoto paper exists. Its introduction states the condition

\[ k<n^{1/3-\delta}, \]

where \(\delta>0\) may tend to zero provided \(n^{-\delta}\to0\). This is the page's \(n^{1/3-o(1)}\) formulation with a diverging subpower gap. [B, primary-source transcription.]

Godsil--McKay: the verified later theorem

Godsil and McKay's paper exists as

C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, Journal of Combinatorial Theory, Series B 48 (1990), 19--44, DOI 10.1016/0095-8956(90)90128-M90128-M).

I inspected the author-hosted scan with corrections. Theorem 1.1 is exactly

\[ L(k,n)\sim G(k,n):= (n!)^k \left(\frac{(n)_k}{n^k}\right)^n \left(1-\frac{k}{n}\right)^{-n/2}e^{-k/2}, \qquad k=o(n^{6/7}). \tag{2} \]

Here \((n)_k=n(n-1)\cdots(n-k+1)\), and \(L\) is explicitly the unrestricted count. The paper's Theorem 6.5 is a sharper expansion from which (2) follows. The sentence after Theorem 1.1 conjectures (2) for \(k=O(n^{1-\delta})\), \(\delta>0\); it does not prove that range. [B for (2); C for the conjectured extension.]

Expansion of the logarithm in (2) explains how the older answer fits inside it. Uniformly when \(k=o(n)\),

\[ \log\frac{G(k,n)}{(n!)^ke^{-\binom{k}{2}}} =-\frac{k^3}{6n} +O\!\left(\frac{k^2}{n}+\frac{k^4}{n^2}\right). \tag{3} \]

To check (3), use

\[ \begin{split} \log\frac{G}{(n!)^ke^{-\binom{k}{2}}} ={}&n\sum_{j=0}^{k-1}\log(1-j/n) -\frac n2\log(1-k/n)-\frac k2+\binom{k}{2}; \end{split} \]

the linear terms cancel, and the quadratic logarithm terms equal

\[ \frac{-2k^3+6k^2-k}{12n}. \]

The remaining power series is \(O(k^4/n^2)\) for \(k=o(n)\). Hence the old formula has relative error \(o(1)\) for \(k=o(n^{1/3})\), while at \(k\sim c n^{1/3}\) the first new factor tends to \(e^{-c^3/6}\). [A]

Search for anything later

Targeted searches used the exact title and problem phrase; the author publication lists; arXiv title/full-text and author searches for Godsil, McKay, Leckey, Liebenau, and Wormald; DOI/Crossref-style searches; and papers citing the 1990 result.

The relevant later items I could verify are:

rectangles](https://doi.org/10.1006/eujc.1998.0221), European Journal of Combinatorics* 19 (1998), 617--620, obtains bounds from permanent inequalities. In particular, the lower product used in Section 3 is known; I make no novelty claim for it.

asymptotic estimates for the number of Latin rectangles and Latin squares*](https://doi.org/10.4213/dm264), 2002, proves a uniform permanent formula in a near-complete matrix regime and then states conjectural consequences for Latin rectangles/squares. Its abstract does not claim a wider unconditional relative formula for \(L(k,n)\).

calls Godsil--McKay the current best Latin-rectangle range and gives another proof of a smaller range.

abstract](https://www.math.cmu.edu/rsa2017/abs/Wormald.pdf) by Wormald says joint work with Kevin Leckey and Anita Liebenau obtains a further improvement, but supplies neither the range nor a proof.

seminar](https://www.unsw.edu.au/science/our-schools/maths/engage-with-us/seminars/2025/Asymptotic-enumeration-of-Latin-Rectangles) and a December 2025 AustMS plenary abstract describe “recent joint work”/work in progress on asymptotics, again without a theorem statement. As of the access date, Liebenau's current UNSW publication/preprint list and the arXiv author query contain no corresponding manuscript.

Thus (2) is the latest theorem whose exact statement and proof I could verify. The conference announcements are evidence that stronger unpublished work may exist, not a citable result and not a basis for claiming the problem solved. This is an honest search result, not a proof of bibliographic completeness. [C]

3. Exact extension reduction and uniform bounds

Let a \(j\times n\) rectangle \(Q\) be fixed. Its next row is a perfect matching in the \(n\times n\) availability matrix \(A_Q\), whose rows and columns all have sum

\[ r=n-j. \]

Consequently the number of extensions is \(\operatorname{per}A_Q\). Averaging over all \(j\times n\) rectangles gives the exact identity

\[ \frac{L(j+1,n)}{L(j,n)} =\mathbb E_{Q\in\mathcal L(j,n)}\operatorname{per}A_Q. \tag{4} \]

This is the precise place where the distribution of earlier rows enters. [A]

The Egorychev--Falikman theorem (van der Waerden's permanent conjecture) and the Bregman--Minc inequality give, for every such \(A_Q\),

\[ n!\left(\frac rn\right)^n \le \operatorname{per}A_Q \le (r!)^{n/r}. \tag{5} \]

Multiplying (5) through the \(k\) row additions yields

\[ \boxed{ B(k,n):=(n!)^k\left(\frac{(n)_k}{n^k}\right)^n \le L(k,n) \le U(k,n):=\prod_{r=n-k+1}^{n}(r!)^{n/r}. } \tag{6} \]

[B: modulo Egorychev--Falikman and Bregman.]

There is a useful completely explicit bound on the width. For \(r\ge1\), integral comparison gives

\[ \log r!\le r\log r-r+1+\log r,\qquad \log n!\ge n\log n-n. \]

Thus the logarithm of the ratio of the \(r\)-th upper and lower factors in (5) is at most

\[ \frac nr\log r!-\log n!-n\log(r/n) \le \frac n r(1+\log r). \]

It follows that, for every \(1\le k\le n\),

\[ L(k,n)=B(k,n)e^{\theta_{k,n}}, \tag{7} \]

where

\[ 0\le\theta_{k,n} \le n\sum_{r=n-k+1}^{n}\frac{1+\log r}{r} \le n(1+\log n)^2. \tag{8} \]

For \(k\le(1-\eta)n\), the same calculation gives the sharper

\[ \theta_{k,n} \le \frac{nk(1+\log n)}{n-k+1} =O_\eta(n\log n). \tag{9} \]

The manipulations after the two permanent theorems are elementary. [B]

The base in (7) has the exact logarithm

\[ \log B(k,n) =k\log(n!) +n\{\log(n!)-\log((n-k)!)-k\log n\}. \tag{10} \]

For fixed \(0\le\alpha<1\) and \(k=\alpha n+O(1)\), Stirling's formula, (9), and (10) imply

\[ \boxed{ \log L(k,n) =\alpha n^2\log n -2\alpha n^2 -(1-\alpha)n^2\log(1-\alpha) +O_\alpha(n\log n). } \tag{11} \]

At \(\alpha=1\), (8) instead gives

\[ \log L(n,n)=n^2\log n-2n^2+O(n\log^2 n). \tag{12} \]

These are logarithmic asymptotics only: an uncertainty \(\exp(O(n\log n))\) or \(\exp(O(n\log^2n))\) is nowhere near the relative \(1+o(1)\) demanded by (2). [B]

In the language of (7), Godsil--McKay determines

\[ \theta_{k,n} =-\frac n2\log(1-k/n)-\frac k2+o(1) \qquad(k=o(n^{6/7})). \tag{13} \]

This isolates the open analytic task: estimate the sum of the logarithms of the average permanents in (4) to absolute error \(o(1)\) in a wider regime. A uniform per-layer log error \(o(1/n)\) would suffice, although a proof may instead exploit cancellation in the sum. Near \(k=n\), the available degree \(r\) becomes small and the permanent depends strongly on the accumulated rectangle; no structure-free refinement of (5) can simply be multiplied to produce (13). [A for the reduction; C for this proposed sufficient route.]

4. Exact small cases from scratch

The standalone checker is erdos725_wavew011_reverify.py. It uses only the Python standard library and no downloaded sequence/table.

4.1 Union-state dynamic program

Fix the first row to the identity. After \(j\) rows, encode a rectangle by

\[ S=(S_1,\ldots,S_n), \]

where \(S_c\) is the bit mask of symbols already used in column \(c\). Store the number of ordered row sequences producing each \(S\). Every next row is a perfect matching using only bits outside \(S_c\). Aggregating equal union states gives an exact recurrence. [A for the recurrence; D for its executed implementation.]

The complete reduced table independently recomputed through \(n=6\), plus the computed \(n=7\) prefix, is:

| \(n\) | \(R(1,n)\) | \(R(2,n)\) | \(R(3,n)\) | \(R(4,n)\) | \(R(5,n)\) | \(R(6,n)\) | |---:|---:|---:|---:|---:|---:|---:| | 1 | 1 | | | | | | | 2 | 1 | 1 | | | | | | 3 | 1 | 1 | 1 | | | | | 4 | 1 | 3 | 4 | 4 | | | | 5 | 1 | 11 | 46 | 56 | 56 | | | 6 | 1 | 53 | 1,064 | 6,552 | 9,408 | 9,408 | | 7 | 1 | 309 | 35,792 | 1,293,216 | not run | not run |

The raw normalized counts \(K(k,n)\) through \(n=6\) are:

| \(n\) | \((K(1,n),\ldots,K(n,n))\) | |---:|---| | 1 | \(1\) | | 2 | \(1,1\) | | 3 | \(1,2,2\) | | 4 | \(1,9,24,24\) | | 5 | \(1,44,552,1344,1344\) | | 6 | \(1,265,21280,393120,1128960,1128960\) |

All normalization divisions in (1) and both exact-power versions of (6) are asserted by the checker. [D]

4.2 An independent exact formula for three rows

There is an independent cross-check that never uses the union-state dynamic program. With the first row fixed, let the second row be a derangement \(\pi\) of cycle type \(\lambda=(\lambda_1,\ldots,\lambda_s)\), all \(\lambda_i\ge2\). The two forbidden cells in each row/column form disjoint cycles \(C_{2\lambda_i}\). The matching polynomial for \(C_{2\ell}\) is

\[ q_\ell(x)= \sum_{t=0}^{\ell} \frac{2\ell}{2\ell-t}\binom{2\ell-t}{t}x^t. \tag{14} \]

If

\[ \prod_iq_{\lambda_i}(x)=\sum_{t=0}^n r_t(\lambda)x^t, \]

rook inclusion--exclusion says that the possible third rows number

\[ P_\lambda=\sum_{t=0}^n(-1)^tr_t(\lambda)(n-t)!. \]

There are \(n!/z_\lambda\) permutations of type \(\lambda\), where

\[ z_\lambda=\prod_{\ell\ge2}\ell^{m_\ell}m_\ell!. \]

Therefore

\[ \boxed{ K(3,n)= \sum_{\substack{\lambda\vdash n\\1\notin\lambda}} \frac{n!}{z_\lambda} \sum_{t=0}^n(-1)^tr_t(\lambda)(n-t)!. } \tag{15} \]

This proves the exact finite formula from first principles; it is not offered as a new fixed-\(k\) result. [A]

The checker evaluates (15) through \(n=15\) and agrees with the unrelated union-state computation everywhere they overlap:

| \(n\) | \(K(3,n)\) | \(R(3,n)=K(3,n)/((n-1)(n-2))\) | |---:|---:|---:| | 3 | 2 | 1 | | 4 | 24 | 4 | | 5 | 552 | 46 | | 6 | 21,280 | 1,064 | | 7 | 1,073,760 | 35,792 | | 8 | 70,299,264 | 1,673,792 | | 9 | 5,792,853,248 | 103,443,808 | | 10 | 587,159,944,704 | 8,154,999,232 | | 11 | 71,822,743,499,520 | 798,030,483,328 | | 12 | 10,435,273,503,677,440 | 94,866,122,760,704 | | 13 | 1,776,780,700,509,416,448 | 13,460,459,852,344,064 | | 14 | 350,461,958,856,515,690,496 | 2,246,551,018,310,998,016 | | 15 | 79,284,041,282,622,163,140,608 | 435,626,600,453,967,929,344 |

[D]

4.3 Exact \(3\times7\) extension distribution

At depth three for \(n=7\), the dynamic program has 357,435 distinct labelled union states representing 1,073,760 normalized rectangles. Instead of materializing all fourth-row transitions, the checker computes the permanent of each complementary \(4\)-regular board by a second memoized matching recurrence. The complete distribution is:

| fourth-row extensions | labelled union states | weighted normalized \(3\times7\) rectangles | contribution to \(K(4,7)\) | |---:|---:|---:|---:| | 144 | 315,855 | 932,640 | 134,300,160 | | 148 | 41,580 | 141,120 | 20,885,760 | | total | 357,435 | 1,073,760 | 155,185,920 |

Thus

\[ K(4,7)=155{,}185{,}920,\qquad R(4,7)=\frac{K(4,7)}{120}=1{,}293{,}216, \]

and

\[ L(4,7)=7!K(4,7)=782{,}137{,}036{,}800. \]

[D]

The two possible extension counts also have tiny explicit witnesses. The following normalized rectangles have respectively 144 and 148 next rows:

\[ \begin{pmatrix} 1&2&3&4&5&6&7\\ 2&1&4&3&6&7&5\\ 3&4&1&2&7&5&6 \end{pmatrix}, \qquad \begin{pmatrix} 1&2&3&4&5&6&7\\ 2&1&4&3&6&7&5\\ 3&4&1&5&7&2&6 \end{pmatrix}. \]

The checker verifies these certificates separately by trying all \(7!\) candidate fourth rows. [D]

4.4 Reproduction command and core code

Run:

python runs/erdos725_wavew011_reverify.py

The recorded full run ended with:

extensions=144: states=315855, normalized 3x7 rectangles=932640
extensions=148: states=41580, normalized 3x7 rectangles=141120
K(4,7)=155185920; R(4,7)=1293216; L(4,7)=782137036800
explicit 144/148 extension certificates: PASS
ALL CHECKS PASSED in 4.916 seconds

The essential state transition in the standalone source is:

for state, weight in states.items():
    allowed = tuple(full ^ mask for mask in state)
    for row in generate_perfect_matchings(allowed):
        new_state = tuple(mask | bit for mask, bit in zip(state, row))
        following[new_state] += weight

The independent permanent recursion is:

@lru_cache(maxsize=None)
def permanent_by_matching_recurrence(sorted_rows):
    if not sorted_rows:
        return 1
    pivot = min(range(len(sorted_rows)),
                key=lambda index: sorted_rows[index].bit_count())
    choices = sorted_rows[pivot]
    remaining = sorted_rows[:pivot] + sorted_rows[pivot + 1:]
    total = 0
    while choices:
        bit = choices & -choices
        choices -= bit
        child = tuple(sorted(mask & ~bit for mask in remaining))
        if not child or child[0] != 0:
            total += permanent_by_matching_recurrence(child)
    return total

The complete 392-line auditable implementation, including the independent cycle-type formula, explicit certificates, expected-value assertions, and exact-integer bound checks, is in the linked .py. Its SHA-256 is a34cad5d2f5bace8c2efb2f06da411d529006a451e58a6861b13b81db20c270c.

5. What remains, precisely

Nothing here closes the problem.

  1. Equation (2) is already a strong verified answer for

\(k=o(n^{6/7})\), omitted from the main live text but present in its unverified comment.

  1. Equations (7)--(10) reduce every remaining regime to the correction

\(\theta_{k,n}\), i.e. to accumulated average permanents, not worst-case permanents.

  1. Godsil--McKay identify \(\theta\) to \(o(1)\) only in their range. The

elementary general interval has width \(O_\eta(n\log n)\) away from the square boundary and \(O(n\log^2n)\) uniformly. Relative asymptotics require reducing that additive logarithmic uncertainty all the way to \(o(1)\).

  1. At \(k=n\), \(L(n,n)\) is the number of Latin squares. Formula (12) is the

familiar logarithmic scale, but no relative \(1+o(1)\) asymptotic is known. Hence any interpretation of the page asking uniformly through \(k=n\) contains this major unresolved subproblem.

  1. A sufficient missing lemma would give the average extension factor in (4)

at every layer with cumulative log error \(o(1)\), or equivalently evaluate the normalized-count point probability advertised in the recent Liebenau--Wormald talks. No public theorem statement currently permits that step. More exact small cases cannot supply the required uniformity.

This is a sharp wall rather than a conjectural closure. [A for items 2--4 as logical implications; C for the suggested route in item 5.]

PARTIAL: verified Godsil--McKay through \(k=o(n^{6/7})\), proved a uniform permanent reduction/logarithmic bound, and independently computed exact reduced counts through \(n=6\) plus \(R(4,7)=1{,}293{,}216\); the unresolved relative-asymptotic wall includes Latin squares at \(k=n\).

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger