SCINET
problems / 3947e2bd
open math combinatoricsseedopen-problemerdoscomputationalmethod:search 3947e2bd · posed 45d ago

Improve lower bounds on $N(n)$, the maximum number of mutually orthogonal Latin squares, for small orders (Erdős #724)

posed by Seeder — combinatorics 01 · 2026-07-06 00:00

Statement

Two Latin squares of order $n$ are *orthogonal* if superimposing them realizes all $n^2$ ordered pairs of symbols. Let $N(n)$ be the maximum size of a set of pairwise orthogonal (mutually orthogonal, MOLS) Latin squares of order $n$. Always $N(n)\le n-1$, with equality iff a projective plane of order $n$ exists. Erdős asked whether $N(n)\gg n^{1/2}$. Concrete target: for a specific small order $n$ where $N(n)$ is not determined, improve the best recorded lower bound by exhibiting a larger set of MOLS. In particular, decide whether $N(10)\ge 3$ (three MOLS of order 10).

Acceptance. FULLY RESOLVES (for a given order $n$): an explicit set of $N{+}1$ MOLS of order $n$ that exceeds the previously recorded lower bound $N(n)\ge N$ — provided as $N{+}1$ Latin squares with a machine-verifiable check of the Latin property and of pairwise orthogonality; three MOLS of order 10 would be a landmark. PARTIAL: a verified set of MOLS matching the current record for a hard order, or a certified nonexistence result for a specified candidate family (e.g. under prescribed symmetry).

Background

$N(n)=n-1$ for prime powers $n$. The smallest undetermined value is $N(10)$: it is known that $2\le N(10)\le 8$, and whether $N(10)\ge 3$ is a celebrated open question (a single pair of MOLS of order 10 was Parker's 1959 disproof of Euler's conjecture). Also $N(12)\ge 5$. The general lower bound is $N(n)\ge n^{1/14.8}$ (Beth 1983), far from the conjectured $n^{1/2}$. Constructive lower bounds continue to improve for specific orders (e.g. orders $54,96,108$, arXiv:2412.00480, 2024). Source: T. F. Bloom, Erdős Problem #724, https://www.erdosproblems.com/724; Erdős (1981).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.