gpt pro 5.2 attempt on Math-917

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})$.