Erdős Problem #724

Erdős Problem 724 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/724.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Fix an integer $n\ge 2$.

A Latin square of order $n$ is an $n\times n$ array $L=(L(i,j))_{i,j\in[n]}$ with symbols in $[n]:=\{0,1,\dots,n-1\}$ such that each row and each column is a permutation of $[n]$.

Two Latin squares $L,M$ of order $n$ are orthogonal if the multiset \[ \{(L(i,j),M(i,j)) : i,j\in[n]\} \] contains each ordered pair in $[n]\times[n]$ exactly once.

Let $f(n)$ be the maximum size of a set of pairwise orthogonal Latin squares of order $n$.

Question (interpreting $f(n)\gg n^{1/2}$): Does there exist an absolute constant $c>0$ and $N_0$ such that for all $n\ge N_0$, \[ f(n) \ge c\, n^{1/2}? \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records:

- Euler conjectured $f(n)=1$ for $n\equiv 2\pmod 4$, disproved by Bose--Parker--Shrikhande who proved $f(n)\ge 2$ for $n\ge 7$. - Lower bounds of the form $f(n)\gg n^\alpha$ are known with exponents $\alpha=1/91,1/17,1/14.8$ (Chowla--Erdős--Straus; Wilson; Beth).

I do not rely on any other external results.

3) ATTACK PLAN

Proof track ideas: - Combine constructions across coprime factors of $n$ to get a uniform lower bound (e.g. via a direct-product construction). - Improve exponent towards $1/2$ by pushing sieve/number-theoretic constructions.

Disproof track ideas: - Exhibit an infinite family of $n$ where $f(n)$ is provably $o(n^{1/2})$ (none is known from the statement).

I can rigorously prove basic structural bounds and explicit constructions for certain $n$; the main asymptotic question remains open.

4) WORK

FAST REALITY CHECK.

By explicit construction and verification (short scripts), I found:

- $f(2)=1$ (upper bound $n-1=1$; any single Latin square works). - $f(3)=2$ via the standard linear construction modulo $3$. - $f(4)=3$ via a linear construction on $\mathbb F_2^2$ (explicit squares included below). - $f(5)=4$ via the standard linear construction modulo $5$.

In each case, the constructed family achieves the general upper bound $n-1$ (proved next), hence is optimal for $n\in\{2,3,4,5\}$.

Lemma 1 (general upper bound). For every integer $n\ge 2$, \[ f(n) \le n-1. \]

Proof. Suppose $L_1,\dots,L_m$ are pairwise orthogonal Latin squares of order $n$ on symbol set $[n]$. Let the point set be the set of cells \[ P := [n]\times[n],\qquad |P|=n^2. \] Define the following subsets of $P$ (which we call lines for this argument):

- For each row index $i\in[n]$, the row line \[R_i := \{(i,j): j\in[n]\}.\] - For each column index $j\in[n]$, the column line \[C_j := \{(i,j): i\in[n]\}.\] - For each square $t\in\{1,\dots,m\}$ and each symbol $s\in[n]$, the symbol line \[S_{t,s} := \{(i,j)\in P: L_t(i,j)=s\}.\]

Each of these lines has size exactly $n$: - $|R_i|=|C_j|=n$ by definition. - For $S_{t,s}$: in a Latin square each symbol appears exactly once in each row, hence exactly $n$ times total.

Let $\mathcal L$ be the collection of all these lines. Then \[ |\mathcal L| = n \ \text{(rows)}\ +\ n\ \text{(columns)}\ +\ mn\ \text{(symbol lines)}\ = (m+2)n. \]

Claim. Any two distinct points of $P$ lie together in at most one line in $\mathcal L$.

Proof of claim. Take two distinct points $x=(i,j)$ and $y=(i',j')$.

- If $i=i'$ (same row), then $x,y\in R_i$. They cannot lie in any column line because $j\ne j'$. They also cannot lie together in any symbol line $S_{t,s}$ because in a fixed row of a Latin square each symbol occurs at most once.

- If $j=j'$ (same column), similarly they lie in $C_j$ and in no other line.

- If $i\ne i'$ and $j\ne j'$, then they are in no row or column line together. They could lie together in a symbol line $S_{t,s}$ if and only if $L_t(i,j)=L_t(i',j')=s$. If they lie together in symbol lines for two different squares, say $S_{t,s}$ and $S_{u,s'}$ with $t\ne u$, then the ordered pair \[(L_t(i,j),L_u(i,j))=(s,s')\] would occur at both $x$ and $y$, contradicting orthogonality of $L_t$ and $L_u$. Thus they can lie together in symbol lines for at most one square. This proves the claim. $\square$

Now count unordered pairs of points in two ways. Each line has size $n$, hence contains $\binom{n}{2}$ unordered pairs of points. By the claim, no unordered pair of points is counted more than once when summing over all lines. Therefore, \[ |\mathcal L|\binom{n}{2} \le \binom{n^2}{2}. \] Substitute $|\mathcal L|=(m+2)n$ and simplify: \[ (m+2)n\cdot \frac{n(n-1)}{2} \le \frac{n^2(n^2-1)}{2}. \] Cancel $n^2/2$ (valid since $n\ge 2$): \[ (m+2)(n-1) \le (n^2-1) = (n-1)(n+1). \] Cancel $n-1$ to get $m+2\le n+1$, i.e. $m\le n-1$. Since $m$ was arbitrary, $f(n)\le n-1$. $\square$

Lemma 2 (explicit construction for primes). If $p$ is prime, then $f(p)=p-1$.

Proof. By Lemma 1 we have $f(p)\le p-1$, so it suffices to construct $p-1$ mutually orthogonal Latin squares of order $p$.

Index rows and columns by $\mathbb Z/p\mathbb Z$. For each $a\in\{1,2,\dots,p-1\}$ define a square $L_a$ by \[ L_a(i,j) \equiv ai + j \pmod p. \]

Latin property. Fix $i$. As $j$ varies, $ai+j$ runs over all residues mod $p$ exactly once, so row $i$ is a permutation. Fix $j$. Since $a\not\equiv 0\pmod p$, the map $i\mapsto ai+j$ is a bijection mod $p$, so column $j$ is a permutation. Thus $L_a$ is a Latin square.

Orthogonality. Take distinct $a,b\in\{1,\dots,p-1\}$. Consider the map \[ \phi: (\mathbb Z/p\mathbb Z)^2 \to (\mathbb Z/p\mathbb Z)^2,\qquad \phi(i,j)=(L_a(i,j),L_b(i,j))=(ai+j,\ bi+j). \] Given a target pair $(x,y)$, subtract to get \[ x-y \equiv (a-b)i \pmod p. \] Since $a\not\equiv b\pmod p$, the nonzero residue $a-b$ has a multiplicative inverse, so there is a unique solution \[ i \equiv (x-y)(a-b)^{-1} \pmod p. \] Then $j\equiv x-ai\pmod p$ is uniquely determined. Hence $\phi$ is bijective, which means each ordered pair $(x,y)$ occurs exactly once in the superposition of $L_a$ and $L_b$. So $L_a$ and $L_b$ are orthogonal.

Therefore $\{L_a:1\le a\le p-1\}$ is a set of $p-1$ mutually orthogonal Latin squares, proving $f(p)\ge p-1$. Combined with $f(p)\le p-1$, we get $f(p)=p-1$. $\square$

Example (explicit $3$ MOLS of order $4$, sanity check). Label symbols by $\{0,1,2,3\}$. The following three squares (verified by script) are Latin and pairwise orthogonal: \[ \begin{array}{c} \begin{array}{|cccc|}\hline 0&3&1&2\\ 1&2&0&3\\ 2&1&3&0\\ 3&0&2&1\\\hline \end{array} \qquad \begin{array}{|cccc|}\hline 0&1&2&3\\ 1&0&3&2\\ 2&3&0&1\\ 3&2&1&0\\\hline \end{array} \qquad \begin{array}{|cccc|}\hline 0&2&3&1\\ 1&3&2&0\\ 2&0&1&3\\ 3&1&0&2\\\hline \end{array} \end{array} \]

5) VERIFICATION

- Lemma 1 uses only the Latin property and pairwise orthogonality and a direct double count of unordered pairs of cells. - Lemma 2 is fully explicit and checks bijectivity of the superposition map. - Small $n$ checks: the constructed families for $n=2,3,4,5$ meet the upper bound $n-1$, hence are optimal for these $n$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: For all $n\ge 2$, $f(n)\le n-1$ (Lemma 1), and for every prime $p$, $f(p)=p-1$ via an explicit construction (Lemma 2). Small cases $n\in\{2,3,4,5\}$ were explicitly constructed and verified to achieve $f(n)=n-1$.

(ii) First gap (crisp): Prove or disprove: there exists $c>0$ such that $f(n)\ge c\,n^{1/2}$ for all sufficiently large integers $n$.

(iii) Top 3 next moves: 1. Prove a direct-product lower bound (construct MOLS of order $mn$ from MOLS of orders $m$ and $n$) and quantify what it gives for general $n$ from prime factorizations. 2. Improve the known general lower exponents (from the statement) by refining the sieve/construction methods. 3. Compute $f(n)$ for moderately large composite $n$ (especially $n\equiv 2\pmod 4$) to detect obstruction patterns and potential extremal families.

(iv) Minimal counterexample structure: If the conjectured bound is false, a minimal counterexample would be a sequence $n\to\infty$ (likely highly composite and/or with constrained congruence class such as $n\equiv 2\pmod 4$) for which every set of MOLS has size $o(n^{1/2})$.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT

Fix an integer $n\ge 2$.

A Latin square of order $n$ is an $n\times n$ array $L=(L(i,j))_{i,j\in[n]}$ with symbols in $[n]:=\{0,1,\dots,n-1\}$ such that each row and each column is a permutation of $[n]$.

Two Latin squares $L,M$ of order $n$ are orthogonal if the multiset \[ \{(L(i,j),M(i,j)) : i,j\in[n]\} \] contains each ordered pair in $[n]\times[n]$ exactly once.

Let $f(n)$ be the maximum size of a set of pairwise orthogonal Latin squares of order $n$.

Question (interpreting $f(n)\gg n^{1/2}$): Does there exist an absolute constant $c>0$ and $N_0$ such that for all $n\ge N_0$, \[ f(n) \ge c\, n^{1/2}? \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records:

- Euler conjectured $f(n)=1$ for $n\equiv 2\pmod 4$, disproved by Bose--Parker--Shrikhande who proved $f(n)\ge 2$ for $n\ge 7$. - Lower bounds of the form $f(n)\gg n^\alpha$ are known with exponents $\alpha=1/91,1/17,1/14.8$ (Chowla--Erdős--Straus; Wilson; Beth).

I do not rely on any other external results.

3) ATTACK PLAN

Proof track ideas: - Combine constructions across coprime factors of $n$ to get a uniform lower bound (e.g. via a direct-product construction). - Improve exponent towards $1/2$ by pushing sieve/number-theoretic constructions.

Disproof track ideas: - Exhibit an infinite family of $n$ where $f(n)$ is provably $o(n^{1/2})$ (none is known from the statement).

I can rigorously prove basic structural bounds and explicit constructions for certain $n$; the main asymptotic question remains open.

4) WORK

FAST REALITY CHECK.

By explicit construction and verification (short scripts), I found:

- $f(2)=1$ (upper bound $n-1=1$; any single Latin square works). - $f(3)=2$ via the standard linear construction modulo $3$. - $f(4)=3$ via a linear construction on $\mathbb F_2^2$ (explicit squares included below). - $f(5)=4$ via the standard linear construction modulo $5$.

In each case, the constructed family achieves the general upper bound $n-1$ (proved next), hence is optimal for $n\in\{2,3,4,5\}$.

Lemma 1 (general upper bound). For every integer $n\ge 2$, \[ f(n) \le n-1. \]

Proof. Suppose $L_1,\dots,L_m$ are pairwise orthogonal Latin squares of order $n$ on symbol set $[n]$. Let the point set be the set of cells \[ P := [n]\times[n],\qquad |P|=n^2. \] Define the following subsets of $P$ (which we call lines for this argument):

- For each row index $i\in[n]$, the row line \[R_i := \{(i,j): j\in[n]\}.\] - For each column index $j\in[n]$, the column line \[C_j := \{(i,j): i\in[n]\}.\] - For each square $t\in\{1,\dots,m\}$ and each symbol $s\in[n]$, the symbol line \[S_{t,s} := \{(i,j)\in P: L_t(i,j)=s\}.\]

Each of these lines has size exactly $n$: - $|R_i|=|C_j|=n$ by definition. - For $S_{t,s}$: in a Latin square each symbol appears exactly once in each row, hence exactly $n$ times total.

Let $\mathcal L$ be the collection of all these lines. Then \[ |\mathcal L| = n \ \text{(rows)}\ +\ n\ \text{(columns)}\ +\ mn\ \text{(symbol lines)}\ = (m+2)n. \]

Claim. Any two distinct points of $P$ lie together in at most one line in $\mathcal L$.

Proof of claim. Take two distinct points $x=(i,j)$ and $y=(i',j')$.

- If $i=i'$ (same row), then $x,y\in R_i$. They cannot lie in any column line because $j\ne j'$. They also cannot lie together in any symbol line $S_{t,s}$ because in a fixed row of a Latin square each symbol occurs at most once.

- If $j=j'$ (same column), similarly they lie in $C_j$ and in no other line.

- If $i\ne i'$ and $j\ne j'$, then they are in no row or column line together. They could lie together in a symbol line $S_{t,s}$ if and only if $L_t(i,j)=L_t(i',j')=s$. If they lie together in symbol lines for two different squares, say $S_{t,s}$ and $S_{u,s'}$ with $t\ne u$, then the ordered pair \[(L_t(i,j),L_u(i,j))=(s,s')\] would occur at both $x$ and $y$, contradicting orthogonality of $L_t$ and $L_u$. Thus they can lie together in symbol lines for at most one square. This proves the claim. $\square$

Now count unordered pairs of points in two ways. Each line has size $n$, hence contains $\binom{n}{2}$ unordered pairs of points. By the claim, no unordered pair of points is counted more than once when summing over all lines. Therefore, \[ |\mathcal L|\binom{n}{2} \le \binom{n^2}{2}. \] Substitute $|\mathcal L|=(m+2)n$ and simplify: \[ (m+2)n\cdot \frac{n(n-1)}{2} \le \frac{n^2(n^2-1)}{2}. \] Cancel $n^2/2$ (valid since $n\ge 2$): \[ (m+2)(n-1) \le (n^2-1) = (n-1)(n+1). \] Cancel $n-1$ to get $m+2\le n+1$, i.e. $m\le n-1$. Since $m$ was arbitrary, $f(n)\le n-1$. $\square$

Lemma 2 (explicit construction for primes). If $p$ is prime, then $f(p)=p-1$.

Proof. By Lemma 1 we have $f(p)\le p-1$, so it suffices to construct $p-1$ mutually orthogonal Latin squares of order $p$.

Index rows and columns by $\mathbb Z/p\mathbb Z$. For each $a\in\{1,2,\dots,p-1\}$ define a square $L_a$ by \[ L_a(i,j) \equiv ai + j \pmod p. \]

Latin property. Fix $i$. As $j$ varies, $ai+j$ runs over all residues mod $p$ exactly once, so row $i$ is a permutation. Fix $j$. Since $a\not\equiv 0\pmod p$, the map $i\mapsto ai+j$ is a bijection mod $p$, so column $j$ is a permutation. Thus $L_a$ is a Latin square.

Orthogonality. Take distinct $a,b\in\{1,\dots,p-1\}$. Consider the map \[ \phi: (\mathbb Z/p\mathbb Z)^2 \to (\mathbb Z/p\mathbb Z)^2,\qquad \phi(i,j)=(L_a(i,j),L_b(i,j))=(ai+j,\ bi+j). \] Given a target pair $(x,y)$, subtract to get \[ x-y \equiv (a-b)i \pmod p. \] Since $a\not\equiv b\pmod p$, the nonzero residue $a-b$ has a multiplicative inverse, so there is a unique solution \[ i \equiv (x-y)(a-b)^{-1} \pmod p. \] Then $j\equiv x-ai\pmod p$ is uniquely determined. Hence $\phi$ is bijective, which means each ordered pair $(x,y)$ occurs exactly once in the superposition of $L_a$ and $L_b$. So $L_a$ and $L_b$ are orthogonal.

Therefore $\{L_a:1\le a\le p-1\}$ is a set of $p-1$ mutually orthogonal Latin squares, proving $f(p)\ge p-1$. Combined with $f(p)\le p-1$, we get $f(p)=p-1$. $\square$

Example (explicit $3$ MOLS of order $4$, sanity check). Label symbols by $\{0,1,2,3\}$. The following three squares (verified by script) are Latin and pairwise orthogonal: \[ \begin{array}{c} \begin{array}{|cccc|}\hline 0&3&1&2\\ 1&2&0&3\\ 2&1&3&0\\ 3&0&2&1\\\hline \end{array} \qquad \begin{array}{|cccc|}\hline 0&1&2&3\\ 1&0&3&2\\ 2&3&0&1\\ 3&2&1&0\\\hline \end{array} \qquad \begin{array}{|cccc|}\hline 0&2&3&1\\ 1&3&2&0\\ 2&0&1&3\\ 3&1&0&2\\\hline \end{array} \end{array} \]

5) VERIFICATION

- Lemma 1 uses only the Latin property and pairwise orthogonality and a direct double count of unordered pairs of cells. - Lemma 2 is fully explicit and checks bijectivity of the superposition map. - Small $n$ checks: the constructed families for $n=2,3,4,5$ meet the upper bound $n-1$, hence are optimal for these $n$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: For all $n\ge 2$, $f(n)\le n-1$ (Lemma 1), and for every prime $p$, $f(p)=p-1$ via an explicit construction (Lemma 2). Small cases $n\in\{2,3,4,5\}$ were explicitly constructed and verified to achieve $f(n)=n-1$.

(ii) First gap (crisp): Prove or disprove: there exists $c>0$ such that $f(n)\ge c\,n^{1/2}$ for all sufficiently large integers $n$.

(iii) Top 3 next moves: 1. Prove a direct-product lower bound (construct MOLS of order $mn$ from MOLS of orders $m$ and $n$) and quantify what it gives for general $n$ from prime factorizations. 2. Improve the known general lower exponents (from the statement) by refining the sieve/construction methods. 3. Compute $f(n)$ for moderately large composite $n$ (especially $n\equiv 2\pmod 4$) to detect obstruction patterns and potential extremal families.

(iv) Minimal counterexample structure: If the conjectured bound is false, a minimal counterexample would be a sequence $n\to\infty$ (likely highly composite and/or with constrained congruence class such as $n\equiv 2\pmod 4$) for which every set of MOLS has size $o(n^{1/2})$.