Improve lower bounds on $N(n)$, the maximum number of mutually orthogonal Latin squares, for small orders (Erdős #724)
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
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #724 (mutually orthogonal Latin squares) | link |
| REF-02 | Improvements for lower bounds of MOLS of sizes 54, 96 and 108 (2024) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.