fully diagonalized latin k-cubes i

Back in 2018 or so, my friend Matthew Bolan and I investigated the theory of a particular type of Latin square — I think with some help from others, i.e. Xero running an SAT solver. Most people will be familiar with Latin squares from Sudoku: a $9 \times 9$ Latin square requires that each of the digits $1$ through $9$ be present in every row and every column. This makes up two thirds of the Sudoku ruleset, not requiring the boxes condition — thus making it possible to ask about Latin squares of any order, not only of order $n^2$.

Doubly Diagonalized Latin Squares

In particular, we were interested in doubly diagonalized Latin squares:

A doubly diagonalized Latin square of order $n$ is an $n \times n$ array with entries drawn from an $n$-element set¹¹ In Sudoku this is the numbers $\{1, \ldots, 9\}$. It could also be zero-indexed, or a set of colors. The “Latin square” terminology originated because Euler used the set $\{A, B, \ldots\}$. such that each row, column, and the two diagonals all contain each element precisely once.

One occasionally sees this requirement in variant Sudoku problems:

In fact, the carré magique diabolique, an 1895 predecessor to Sudoku published in La France by M. B. Meyniel²² I wasn’t able to find any information on M. B. Meyniel beyond a 2006 The Times article by and Jack Malvern which describes him as “unknown”. requires that each row, column, and broken diagonal sums to the same number:

where a glance at the given numbers will make it clear that the number to be summed to is in fact $45$, well-known by variant Sudoku solvers to be the sum of the numbers one through nine. The inclusion of the broken diagonals makes this pandiagonal, a stronger condition than double diagonalization.

For which $n$ do $n \times n$ doubly diagonalized Latin squares exist?

It is easy to see that doubly diagonalized Latin squares exist of order $0$:

and of order $1$:

It is reasonably easy to exhaustively enumerate Latin squares of order $2$ and $3$ and conclude that none of them are doubly diagonalized. You can WLOG³³ This is just a choice of labelling convention. For any Latin square, you can choose to rewrite the symbol in the top left corner as $1$, the second symbol in the top row as $2$, and so on. For the purposes of establishing existence, it mostly suffices to consider Latin squares modulo permutation of the symbols, though when discussing symmetries of particular squares one might wish to consider permutations distinct. fix the top row to be $1, \ldots, n$, and quickly conclude that the only $2 \times 2$ Latin square is of the form:

which is not diagonalized. You can get a singly diagonalized $3 \times 3$, and of course (because you can reflect it) this can be either diagonal:

These are the only possible $3 \times 3$ Latin squares: once you fix the middle left entry to be either $2$ or $3$, every other cell is forced.

However, I would like to present a more abstract argument which rules out the order 2 and 3 cases. Consider the four corners of a square:

Any two corners you pick will share a corner, a column, or a diagonal. Thus the corners must be pairwise distinct. Since no two corners can have the same number, all four corners must be distinct. Thus, the order of the doubly diagonalized Latin square must be at least as large as the number of corners of the square, which is four for squares of order $2$ or larger⁴⁴ One must be careful to phrase this statement in a way that permits the $0 \times 0$ and $1 \times 1$ squares to exist. These are possible because $0 \times 0$ and $1 \times 1$ squares do not have four distinct corners..

So the smallest possible nontrivial square is $4 \times 4$. It turns out that such a square exists, and that it’s unique modulo obvious symmetries:

A classic puzzle studied by magicians asks for an arrangement of the jacks, queens, kings, and aces from a deck of card such that both the suits and the ranks form doubly diagonalized $4 \times 4$ Latin squares.

It turns out that doubly diagonalized Latin squares of every order except $2$ and $3$ exist. Our 2018 argument relied on a few different methods for constructing squares:

Squares of order coprime with six

Consider the square:

where $A_{i,j} = (i + 2j) \bmod n$⁵⁵ Where “mod $n$” is of course postfix notation for the quotient map $\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$. If you were wondering.. That is, moving one cell rightwards adds $1$ to your number, wrapping back around once you run out, and moving one cell downwards adds $2$, again wrapping back around. This means that moving down-right adds $3$, and moving down-left adds $1$. This pattern also includes moves that wrap around the square.

This construction produces pandiagonal Latin squares of any order $n$ such that neither $2$ nor $3$ are factors of $n$: any diagonal consists of a list of $n$ cells generated by adding $1$, $2$, or $3$ repeatedly in $\mathbb{Z}/n\mathbb{Z}$, and repeatedly adding a number $m$ traverses⁶⁶ Or reaches every element of $n$. $\mathbb{Z}/n\mathbb{Z}$ precisely when $n$ is coprime with that number⁷⁷ For nonzero $n$., as the order of $m$ in $\mathbb{Z}/n\mathbb{Z}$ is given by $n/\gcd(n, m)$.

Multiplying Latin squares

Suppose we have squares of order $n$ and $m$ with entries from sets $[n]$ and $[m]$:

We can take a product to produce an $n \times m$ square with entries in $[n] \times [m]$:

That is, $(A \otimes B)_{i,j} = (A_{i//m,\ j//m}, B_{i\%m,\ j\%m})$⁸⁸ Where $//$ is floor division and $\%$ is mod.. This is sort of like a matrix Kronecker product, except where the scalar multiplication of the entries is replaced with just taking an ordered pair of the two entries. It might be sort of like a tensor product. You could reasonably call it a quasigroup direct product⁹⁹ There’s a bijection between Latin squares and quasigroups on sets $\{1, \ldots n\}$, where a Latin square corresponds to the Cayley table for a quasigroup. (Cayley table is basically just a fancy name for multiplication table)..

One can check that this product is doubly diagonal if both of the input squares are¹⁰¹⁰ It’s furthermore pandiagonal if both of the input squares are.. Consider two entries in column $i$, $(A \otimes B)_{i,j}$ and $(A \otimes B)_{i,k}$. If $j \ne k$, we must have either $j//m \ne k//m$ or $j\%m \ne k\%m$. In the former case, we have $A_{i//m,\ j//m} \ne A_{i//m,\ k//m}$ because those both occur in the $(i//m)^{\text{th}}$ column of $A$, and thus must be distinct for $A$ to be a Latin square. In the latter case, we have $B_{i\%m,\ j\%m} \ne B_{i\%m,\ k\%m}$ because both occur in the $(i\%m)^{\text{th}}$ column of $B$, and thus must be distinct. A similar argument works for the rows and diagonals, though it gets annoying to chase the indices.

An example of a $16 \times 16$ produced with this method might make it more clear how this works:

These two methods, along with explicit examples of squares of order $4$, $6$, $8$, $9$, $12$, $18$, and $27$ allow you to construct squares of any order except those of the form $2n$ or $3n$, where $n$ is coprime with $6$: the $4$ and $8$ can be combined to get $2^a$ for $a > 3$, and the $9$ and $27$ can be combined to get $3^b$ for $b > 3$. You can get the factors that are coprime with $n$ easily, leaving you with some number of the form $2^a 3^b$ you need to add in. Then you can just throw in the relevant powers of $2$ and $3$ if $a, b > 1$, or you can use $6$, $12$, or $18$ to cover the $2^1 3^1$, $2^2 3^1$, and $2^1 3^2$ cases.

This leaves only the $2^1 3^0$ and $2^0 3^1$ cases that require another construction.

Doubling and tripling

The proof program that I had always had in my head was to then come up with doubling and tripling constructions. I had thought we’d had a doubling construction, but I’m not actually sure we did. I haven’t been able to turn up any actual evidence of a tripling at all, so I think we probably didn’t have that one.

Doubling and tripling constructions do exist, according to what Claude has been able to figure out anyways, but I do not understand them well enough to report on them at this time.

What we had back years ago was more like… well, look at this particular $8 \times 8$:

If you stare at this enough, you will come to the belief that this is sort of like a doubled version of the $4 \times 4$. I believe in you. You can do it.

One thing you’ll notice about this is that, if you split the rows down the middle, it always nicely places $0$-$3$ on one side and $4$-$7$ on the other. This is the sort of thing that happens when you take a $2n \times 2n$ square and try to double it. I definitely remember staring at things like this a lot trying to get them to work out. But all the doubling constructions that seem to exist when you start with an odd sided square are somewhat less nice. There isn’t a $10 \times 10$ that looks as neat and tidy as this $8 \times 8$, as far as I know.

Fully Diagonalized Latin $k$-cubes

Much of the above generalizes to higher dimensions. The corners argument makes orders strictly between $1$ and $2^k$ impossible. Orders with no prime factors less than $2^k$ are all straightforward: $A_{i_1, \ldots, i_k} = i_1 + 2i_2 + 4i_3 + \ldots + 2^{k-1} i_k \bmod n$, which works by much the same argument. You want to use specifically powers of two for the coefficients because they’re the smallest numbers such that you can add or subtract them from each other in any combination and you’ll definitely never hit zero. It’s probably not too tricky to state that formally but I’m kind of tired tonight. The multiplication construction works great. It should probably just be like, $(A \otimes B)_{i_1, \ldots, i_k} = (A_{i_1//m, \ldots, i_k//m}, B_{i_1\%m, \ldots, i_k\%m})$, right? That seems right to me.

We managed to find an $8 \times 8 \times 8$, back in 2021 or so:

There’s a general construction that produces a cube equivalent to this one in the $k = 3$ case, and which works for producing a $k$-cube of order $2^k$ in any dimension. We had a general idea of parts of the construction, and I think I attempted to slowly construct the order 16 tesseract at some point, but we didn’t have a particularly nice formulation of it.

Upon looking through the literature, I found that a very nice formulation of the construction was published in 1972! We’ll go through that next time we cover this topic, as well as (perhaps) a few other constructions that can be found in the literature.

Taylor 1972 ends by posing three problems:

1. Does a doubly diagonalized Latin square of order $12$ exist?

2. Does a fully diagonalized Latin cube of order $9$ exist?

3. Is the set of fully diagonalized Latin $k$-cubes cofinite for each $k$? Do they exist of all orders $\ge 2^k$?

I currently believe the answer to all of these is “yes”. The only one I¹¹¹¹ Well, okay, this particular square is from Claude and is probably either directly based on ideas present in the literature or at least precedented by them. have actually proven so far is the first:

There are several obstructions to any straightforward algorithm for constructing a $9 \times 9 \times 9$, but little reason to doubt that one exists — there are more than enough chances for one to exist! But they probably don’t have much simple structure, and they make up a very small portion of the $9 \times 9 \times 9$ cubes which are merely Latin. A failure of cofiniteness would be incredibly shocking, though perhaps some (non-Fermat) order $2^{k+1}$ $k$-cube fails or something. It seems unlikely to me, but I don’t currently have any great idea of how one would actually disprove it rather than making (perhaps very strong) heuristic arguments.

I would very much like to see a $9 \times 9 \times 9$ someday, though, even if it probably won’t have very much elegant structure! I’ll see if I can piece one together. But in the mean time, there is more theory to understand well enough that I can write it down in a blog post. This whole daily blogging thing is ridiculous, they should let me spend a month putting together a monstrous fifteen thousand word post that covers every single aspect of a topic in a single fell swoop.