Let $l$ be a prime power and $r$ a positive integer with $r<l$.
There are known ways to construct a set of $r$ mutually orthogonal Latin squares (MOLS) of order $l$; the size of each Latin square's grid will be $l \times l$. One nice way to do this is the following:
- Step 1: Let the symbols be the elements of the field $\mathbb{F}_l=\{0,1,\dots,l-1\}$.
- Step 2: For each nonzero element in $\mathbb{F}_l$, construct a Latin square such that $L_\alpha(i,j) = \alpha i+j$ (mod) $l$, where $L_\alpha(i,j)$ denotes the symbol at position $(i,j)$ of the corresponding Latin square $L_\alpha$.
For the sake of this question, we want to pick a set of symbols for each Latin square; let those sets be $S_1,\dots,S_{r}$ where $S_i$ contains the symbols we have picked for Latin square $L_i$ and obviously $\forall i$, $S_i \subseteq \{0,1,\dots,l-1\}$. Assume that we can pick $k$ symbols in total, i.e., $|S_1|+\cdots+|S_{r}| = k$ (note that $0 < k \leq rl$ since we pick symbols independently for each Latin square).
Next, for each symbol $s$ in $S_1$ we observe which positions $(i,j)$ in the grid of $L_1$ have $L_1(i,j)=s$. We repeat this process for the remaining symbol sets $S_2,S_3,\dots,S_{r}$ and the corresponding Latin squares $L_2,L_3,\dots,L_{r}$.
I am interested in counting how many times we can hit each position $(i,j)$ in total at the end of the above process. Specifically, given that one can pick exactly $k$ symbols in total, my question is:
How can one choose the symbols in $S_1,\dots,S_{r}$ s.t. the number of distinct positions $(i,j)$ hit at least $a$ times is maximized.
Example
Let $l=5$, $r=3$, then the set of $3$ MOLS $L_1=i+j$ (mod $5$), $L_2=2i+j$ (mod $5$), $L_3=3i+j$ (mod $5$) will be
$L_1= \begin{bmatrix} 0&1&2&3&4\\ 1&2&3&4&0\\ 2&3&4&0&1\\ 3&4&0&1&2\\ 4&0&1&2&3 \end{bmatrix} $ $L_2= \begin{bmatrix} 0&1&2&3&4\\ 2&3&4&0&1\\ 4&0&1&2&3\\ 1&2&3&4&0\\ 3&4&0&1&2 \end{bmatrix} $ $L_3= \begin{bmatrix} 0&1&2&3&4\\ 3&4&0&1&2\\ 1&2&3&4&0\\ 4&0&1&2&3\\ 2&3&4&0&1 \end{bmatrix} $
Now suppose that $k=3$ and $a=2$.
If I pick $S_1=\{0,1\}$, $S_2=\{0\}$, $S_3=\emptyset$ then the positions of the grid I hit are:
- $(1,1)$ hit $2$ times.
- $(5,3)$ hit $2$ times.
- each of $(1,2),(2,1),(2,5),(3,4),(3,5),(4,3),(4,4),(5,2),(2,4),(3,2),(4,5)$ hit $1$ time.
So only two points $(1,1),(5,3)$ are hit at least $a=2$ times.
But if I pick $S_1=\{0\}$, $S_2=\{0\}$, $S_3=\{1\}$ then the positions of the grid I hit are:
- $(1,1)$ hit $2$ times.
- $(2,4)$ hit $2$ times.
- $(4,3)$ hit $2$ times.
- $12$ points hit $1$ time
which is better since we hit 3 points $a=2$ times each.
To put this into perspective, my problem is how one can characterize the maximum number of distinct positions in a set of MOLS grids hit at least $a$ times if we are only allowed to pick $k$ to hit on the Latin squares (with the above method).
Could you suggest any related literature results already known?