Does there exist a Latin square of order 9 for which its 9 broken diagonals and 9 broken antidiagonals are transversals?

Question

A Latin square of order $n$ has $n$ broken diagonals and $n$ broken antidiagonals. When $n \equiv \pm 1 \pmod 6$, we have diagonally cyclic Latin squares in which those $2n$ diagonals are transversals (i.e., every symbol occurs exactly once). For example

$$ \begin{bmatrix} 4 & \color{red} 3 & 2 & 1 & \color{blue} 0 \\ 1 & 0 & \color{red} 4 & \color{blue} 3 & 2 \\ 3 & 2 & \color{blue} 1 & \color{red} 0 & 4 \\ 0 & \color{blue} 4 & 3 & 2 & \color{red} 1 \\ \color{purple} 2 & 1 & 0 & 4 & 3 \\ \end{bmatrix} $$ I highlight a broken diagonal in red and a broken antidiagonal in blue (which overlap in the purple entry).

We see that symbols in rows differ by $1$, symbols in columns differ by $2$, symbols along broken diagonals differ by $1$ and symbols along broken antidiagonals differ by $3$. Since these are all generators of $\mathbb{Z}_5$, we have a Latin square with transversals along its $5$ broken diagonals and $5$ broken antidiagonals. The same thing works whenever $1,2,3$ are all generators $\mathbb{Z}_n$ which is when $n \equiv \pm 1 \pmod 6$.

A Latin square satisfying this condition is orthogonal to circulant and back-circulant Latin squares of its order (and, in fact, this is an equivalent condition), such as $$ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 \\ 4 & 0 & 1 & 2 & 3 \\ 3 & 4 & 0 & 1 & 2 \\ 2 & 3 & 4 & 0 & 1 \\ 1 & 2 & 3 & 4 & 0 \\ \end{bmatrix} \qquad \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} $$ for order $5$. For even orders, Euler showed circulant (and back-circulant) Latin squares don't have transversals (let alone orthogonal mates), thus the desired Latin square is impossible when $n$ is even.

This leaves the $n \equiv 3 \pmod 6$ cases unresolved. It's impossible when $n=3$ (proof by hand), so the next case is $n=9$. Modifying the diagonally cyclic Latin square construction by replacing the first row with any other row doesn't work (assuming my GAP code is correct). However, there may be other ways to construct these.

Question: Does there exist a Latin square of order 9 for which its 9 broken diagonals and 9 broken antidiagonals are transversals?

My brute-force GAP code is too slow for this problem, and it's probably not worth writing more efficient code without checking if the problem has already been resolved.

Answer 1

I've verified with ILP that such Latin squares do not exist for $n\in\{9,15,21,27\}$.

The ILP formulation is based on binary indicator variables $p_{c,i,j}$ telling whether Latin square has character $c$ at position $(i,j)$, with constraints $$\begin{cases} \sum_i p_{c,i,j} = 1, \\ \sum_j p_{c,i,j} = 1, \\ \sum_i p_{c,i,i+j} = 1, \\ \sum_i p_{c,i,j-i} = 1, \\ \sum_c p_{c,i,j} = 1, \end{cases}$$ which ensure that each row/column/diagonal/antidiagonal contains each character, and that each position is occupied by a single character.

Answer 2

Oh, I just realized how to prove non-existence for all $n \equiv 3 \pmod 6$.

We take the circulant and back-circulant Latin squares, defined as $L_{ij} = i+j \pmod n$ and $M_{ij} = i-j \pmod n$. Suppose there is a third Latin square $X$ which is orthogonal to both of these Latin squares. Choose a symbol, say $0$, and let $\{(r_i,c_i)\}_{i=0}^{n-1}$ be the cells of $X$ containing $0$.

Then we know:

• $\{r_i\}_{i=0}^{n-1} = \mathbb{Z}_n$,
• $\{c_i\}_{i=0}^{n-1} = \mathbb{Z}_n$,
• $\{r_i+c_i\}_{i=0}^{n-1} = \mathbb{Z}_n$ (because $X$ is orthogonal to $L$), and
• $\{r_i-c_i\}_{i=0}^{n-1} = \mathbb{Z}_n$ (because $X$ is orthogonal to $M$).

Now define the permutation $\sigma: \mathbb{Z}_n \rightarrow \mathbb{Z}_n$ such that $\sigma(c_i)=r_i$. Then $\sigma$ is an example of a strong complete mapping of $\mathbb{Z}_n$, i.e., it's a permutation in which $i \mapsto \sigma(i)-i$ is a permutation, and $i \mapsto \sigma(i)+i$ is a permutation.

Next we hit the problem with this:

Theorem 15. A finite abelian group admits strong complete mappings if and only if neither its Sylow 2-subgroup nor its Sylow 3-subgroup is nontrivial and cyclic.
_{Anthony B. Evans, The existence of strong complete mappings, Electron. J. Combin (pdf).}

When $n \equiv 3 \pmod 6$, the Sylow 3-subgroup of $\mathbb{Z}_n$ is nontrivial ($n$ is divisible by $3$) and cyclic (subgroups of cyclic groups are cyclic), so $\sigma$ does not exist.

Answer 3

Yup, pandiagonal Latin squares fail to exist unless the order lacks factors of $2$ or $3$. But odd multiples of $3$ do allow one of the two diagonal directions to be cyclic, along with the rows and columns.

3×3:

$\begin{matrix} A&B&C\\B&C&A\\C&A&B\\\end{matrix}$

9×9:

$\begin{matrix} A&B&C&D&E&F&G&H&I\\ E&F&G&H&I&A&B&C&D\\ I&A&B&C&D&E&F&G&H\\ D&E&F&G&H&I&A&B&C\\ H&I&A&B&C&D&E&F&G\\ C&D&E&F&G&H&I&A&B\\ G&H&I&A&B&C&D&E&F\\ B&C&D&E&F&G&H&I&A\\ F&G&H&I&A&B&C&D&E\\ \end{matrix}$