fully diagonalized latin k-cubes ii

One way of defining a fully diagonalized latin $k$-cube is by giving a function $A : \{0, \ldots, n-1\}^k \to \{0, \ldots, n-1\}$¹¹ Or any $n$-element set. such that the function restricted to any diagonal is an injection. A diagonal, here, involves choosing for each of the $k$ coordinates to either run it forwards from $0$ to $n-1$, to run it backwards from $n-1$ to $0$, or to fix it at some value in $\{0, \ldots, n-1\}$²² Note that if you swap every moving coordinate between running forwards / backwards, you end up with the same diagonal that you had originally. If this is a particular issue, you can normalize so that the first moving coordinate is in the +1 direction, but it’s really easier to just double count. You don’t really introduce any additional complexities if you phrase your definitions to require that both the top-left → down-right and the down-right → top-left diagonals include all n colors.. This produces a notion of the dimensionality of a diagonal: a diagonal of dimension $d$ has $d$ of its coordinates run forwards or backwards, and $n-d$ of its coordinates fixed.

In a $3$-cube, the rows, columns, and aisles are $1$-dimensional diagonals, the face diagonals are $2$-dimensional, and the space diagonals are $3$-dimensional. Each cell in the cube is a $0$-dimensional diagonal, where every coordinate is fixed. Only the $0$-dimensional diagonal maps are merely injective — the rest are necessarily bijective, for the diagonal contains $n$ cells. We will call those diagonals trivial.

The $\sum_i 2^i x_i \bmod n$ for $n$ with no nontrivial³³ Equivalently, prime. factors below $2^k$ construction from the first post is a special case of a more general construction:

Note that such a $\lambda$ exists regardless of our choice of $G$: by the fundamental theorem of finite abelian groups, $G$ is isomorphic to a direct product of cyclic groups⁴⁴ Of prime power order, but we don’t need that part. $\mathbb{Z}/q_1\mathbb{Z} \times \cdots \times \mathbb{Z}/q_m\mathbb{Z}$. Write $x \in \{0, \ldots, n-1\}$ in mixed-radix digits:

We can then set $\lambda(x) = (x_1, \ldots, x_m)$, and we’ll have $\lambda(n-1-x) = (q_1-1, \ldots, q_m-1) - \lambda(x)$: because $(n-1)_j = q_j-1$, $(n-1-x)_j$ is just $(q_j-1 - x_j)$ (that is, there’s no carrying when you do the mixed-radix subtraction), so subtracting $x$ works the same whether you do it in the mixed-radix digits or in the group.

As an aside: there’s a slightly more general class of group-affine constructions which allow the addition of a group element $c$ to give $A(x) = c + \sum \varphi_i(\lambda(x_i))$. Some of the quasigroup literature would consider these to be linear. The distinction is irrelevant in this context, because adding $c$ is an automorphism of $G$ and thus a bijection, so it maintains FDLness. So you can take $c = 0$ without losing anything.

In the mod $n$ construction, we have:

• $G = \mathbb{Z}/n\mathbb{Z}$

• $\lambda(x) = x \bmod n$.

• $\lambda(n-1-x) = (n-1-x) \bmod n = (-x + n-1) \bmod n$, so $u = (n-1) \bmod n = -1 \bmod n$

• $\varphi_i(x) = 2^i x$

• The construction works when $n$ has no nontrivial factors less than $2^k$ because those are precisely the cases where no nontrivial signed sum of powers $2^i$ for $i \in \{0, \ldots, k\}$ gives a number which shares a nontrivial factor with $n$. If some such sum existed, it would correspond to a $\sum_i e_i \varphi_i$ which failed to be a bijection.

We’ll now give a general proof, which you can use the $\mathbb{Z}/n\mathbb{Z}$ case as a concrete example for. Then we’ll give other constructions from this class as examples.

One of the main purposes of this construction is that it gives us cubes of order $2^k$ in any dimension:

Let $G = \mathrm{GF}(2^m) = \mathbb{F}_2[\alpha]/p(\alpha)$ for some irreducible polynomial $p$ and pick any $\lambda$ (such that $\lambda(n-1-x) = u - \lambda(x)$). Set $\varphi_i(x) = \alpha^i x$. So we have:

This gives a $k$-cube of size $2^k$ for any $k$. For example, consider the $4 \times 4$:

The $8 \times 8 \times 8$ from back in the day is isomorphic to $8 \times 8 \times 8$s of this form. This is also the construction from Taylor 1972.

You can also make a $25 \times 25 \times 25$ using a similar method over the field of order $25$. If we write $\mathrm{GF}(25) = \mathbb{F}_5[\alpha]/(\alpha^2 + \alpha + 2)$ and then take

then this gives a FDL $25 \times 25 \times 25$:

But I’m not really used to working in finite fields, so I don’t understand the full details of choosing coefficients beyond “powers of $\alpha$ work fine in $\mathrm{GF}(2^k)$”. There’s some fiddly details here.

We can do something more general than just multiplying by elements of the finite field: if we’re working in $G = \mathrm{GF}(p^n)$, then we can regard this as a vector space over $\mathbb{F}_p$ and take the $\varphi_i$ to be $n \times n$ matrices over $\mathbb{F}_p$. So you can, for example, make a $9 \times 9$ square just using matrices and $\mathbb{F}_3^2$ even though there’s no way to get $\mathbb{Z}/9\mathbb{Z}$ to work.

There’s more to say about when exactly this construction works, but it’s getting late and I should get off my laptop soon. Go check out the FDL $k$-cube library if you want.