1

Define a set of $n - 1$ mutually orthogonal squares $A_1, \ldots, A_{n-1}$, where n is a prime number. If we set the element $(i, j)$ in square $A_h$ as $i + hj$ then the squares in the set are mutually orthogonal squares.

(1) each square is a Latin square

for fixed $j$, $i + hj$ takes the value of each of the $n$ integers $\pmod n$ as $i$ runs through $\{1,\ldots,n\}$.

similarly for fixed $i$, $hj$ takes all $n$ values for fixed $h$ and $j$ running through $\{1,\ldots,n\}$, because $h$ and $j$ are nonzero elements of the integers modulo $n$, and $n$ is prime.

(2) the squares are mutually orthogonal

let $a_{pq} = a_{rs}$ in $A_k$. then $p + kq = r + ks$.

in $A_m$,

$a_{pq} = p + mq$, $a_{rs} = r + ms$, so

$(p + kq) - (r + ks) = (p - r) + k(q - s) = ny$, where $y$ is an integer

suppose $a_{pq} = a_{rs}$ in $A_m$ also.

$(p - r) + m(q - s) = nz$, where z is an integer

then $ny - nz = (k - m)(q - s) = nw$, where $w$ is an integer

But $k, m < n$ and $q, s \le n$.

So $k - m < n$ and $q - s < n$ (because $q$ and $s$ are distinct), and the prime $n$ can divide neither.

Hence, $a_{pq}$ and $a_{rs}$ must be distinct in $A_m$.

Community
  • 1
user81055
  • 599
  • You said "define a set of mutually orthogonal Latin squares," meaning no proof that it's a set of mutually orthogonal latin squares is necessary. First off, if $(i,j)=(n-1,n-1), h=n-1,$ then $i+hj=n-1+(n-1)^2.$ No constraint on the values is shown. In step 1, $h$ must not be congruent to 0. Why $1-n$ instead of $n-1$? – Loki Clock Jun 17 '13 at 03:18
  • It would be helpful if you mentioned why the last statement implies (2). – Loki Clock Jun 17 '13 at 03:41
  • Did you mean to let the index to $A_k$ run from $0$ to $n-1$? Because it says there are $n-1$ of $A_k$. And nevermind about h not being congruent to 0, I see it's between 1 and $n-1$. However, $hj$ doesn't take all $n$ values, because it never takes $0$ if $|A_k|<n^2 \implies j<n$. It also takes the same value twice if $|A_k|\neq n^2$ – Loki Clock Jun 17 '13 at 03:46
  • So, $i, j$ must run from $0$ to $(n-1) % n$ or $(1-n) % n$, or otherwise pass a number congruent to $n$, or the order of the square is smaller than $n^2$. – Loki Clock Jun 17 '13 at 03:56

1 Answers1

1

Essentially, your construction either skips some residues or it visits the same residue at the same $(i,j)$ for all $A_h$.

Suppose column $(i,-)$ of $A_h$ does not contain a residue $g:0\leq g<n$ mod $n$, but does contain $g+1$ at entry $(i,J)$. Then $(i-1,J)=i-1+hJ=g+1-1$ implies column $(i-1,-)$ does not contain the same set as column $(i,-)$, implies $A_h$ is not a Latin square. Likewise, $g-1$ being at $(i,J)$ implies $g$ is at $(i+1,J)$. Therefore $i+hj$ must visit every congruence class for $A_h$ to be a Latin square, therefore $j$ must visit every congruence class.

Likewise, if $j$ visits the same congruence class twice, so does $i+hJ=i+hL$ for two distinct $J, L$ and every column $(i,-)$, so that again $A_h$ is not a Latin square. Therefore $j$ must visit every residue mod $n$, for every $A_h$. Therefore $(i,J)_h=i+hJ \equiv_n i$ for some J in the index of $j$, and since the index of $j, i$ is independent of $h$, $(i,J)_h=(i,J)_k$ for all $A_h, A_k$. Therefore $A_h, A_k$ cannot be mutually orthogonal.

Loki Clock
  • 2,193

  • Suppose column i of Ah does not contain

    do you mean row i? if so, I can see that from the assumption row i doesn't have g, but row i - 1 does.

     – user81055 Jun 18 '13 at 00:34
  • also, can you explain the logic of the first part? I see that it's reductio ad absurdum, but why is considering the two cases where row i contains either g + 1 or g - 1 sufficient? what if row g contains neither? – user81055 Jun 18 '13 at 00:39

  • two distinct J,L and every row i,

    why is it "every row", not just the one row where (i, J) = (i, L)?

     – user81055 Jun 18 '13 at 00:49
  • I meant every column $i$, i.e. $(i,-)$, in both cases. – Loki Clock Jun 18 '13 at 08:19
  • $g$ can be any residue. Therefore it can be the smallest residue such that $(i,-)$ does not contain $g$ but contains $g-1$, or the largest such that $(i,-)$ does not contain $g$ but contains $g+1$. – Loki Clock Jun 18 '13 at 08:25
  • There's the extra cases of when $i+1$ or $i-1$ is over the bounds, but for those indices you can substitute their residue modulo the bound. And likewise, it would be the residue of $g+1$ that $(i,J)$ takes when $(i,-)$ doesn't take $g$. – Loki Clock Jun 18 '13 at 08:31