8
$\begingroup$

Cross posting from MSE, where this question received no answers.

The following Latin square

$$\begin{bmatrix} 1&2&3&4&5&6&7&8\\ 2&1&4&5&6&7&8&3\\ 3&4&1&6&2&8&5&7\\ 4&3&2&8&7&1&6&5\\ 5&6&7&1&8&4&3&2\\ 6&5&8&7&3&2&4&1\\ 7&8&5&2&4&3&1&6\\ 8&7&6&3&1&5&2&4 \end{bmatrix}$$

has the property that for all pairs of two different rows $a$ and $b$, the permutations $ab^{-1}$ have the same cycle type (one 2-cycle and one 6-cycle).

What is known about Latin squares with the property that all $ab^{-1}$ have the same cycle type (where $a$ and $b$ are different rows)? For example, do they have a particular structure, for which cycle types do they exist, are there any infinite families known, do they have a name, etc?

The only example of an infinite family I'm aware of are powers of a single cyclic permutation when $n$ is prime, for example: $$\begin{bmatrix} 1&2&3&4&5\\ 2&3&4&5&1\\ 3&4&5&1&2\\ 4&5&1&2&3\\ 5&1&2&3&4 \end{bmatrix}$$

$\endgroup$
5
  • 1
    $\begingroup$ I think for every $n$, there's a square of order $2^n$, with every permutation a product of $2$-cycles. $\pmatrix{1&2\cr2&1\cr}$, $\pmatrix{1&2&3&4\cr2&1&4&3\cr3&4&1&2\cr4&3&2&1\cr}$, $\pmatrix{1&2&3&4&5&6&7&8\cr2&1&4&3&6&5&8&7\cr3&4&1&2&7&8&5&6\cr4&3&2&1&8&7&6&5\cr5&6&7&8&1&2&3&4\cr6&5&8&7&2&1&4&3\cr7&8&5&6&3&4&1&2\cr8&7&6&5&4&3&2&1\cr}$, etc. $\endgroup$ Feb 7, 2022 at 5:50
  • 4
    $\begingroup$ @GerryMyerson Your example generalizes to the multiplication table of any elementary abelian group. $\endgroup$ Feb 7, 2022 at 6:29
  • 1
    $\begingroup$ The example given in the comments above generalize further to the multiplication tables of $p$-groups where every non-identity element has order $p$. $\endgroup$ Feb 7, 2022 at 6:43
  • $\begingroup$ @Gerry that's a bit of a comment flex... :-) $\endgroup$
    – David Roberts
    Feb 7, 2022 at 8:10
  • 1
    $\begingroup$ As noted by Joseph, there are, for example, nonabelian groups of exponent 3, for which every pair of rows will break into cycles of length 3. There are also some non-group based examples where all row cycles have length 3. See Kinyon and Wanless, Loops with exponent three in all isotopes, Internat. J. Algebra Comput., 25 (2015), 1159-1177. $\endgroup$ Feb 7, 2022 at 10:37

3 Answers 3

6
$\begingroup$

One way to achieve the required property is to construct a Latin square whose autotopism group acts transitively on unordered pairs of rows. This can be achieved for orders that are a prime power congruent to 3 mod 4, by means of the quadratic orthomorphism method, described in this paper. The focus of that paper is the atomic squares I mentioned in other comments, but the construction will always achieve the property that each pair of rows produces the same cycle structure. For prime powers that are 1 mod 4, quadratic orthomorphisms will build Latin squares with at most two types of cycle structures formed by pairs of rows.

$\endgroup$
7
$\begingroup$

There are also "pan-Hamiltonian" Latin squares, see Perfect Factorisations of Bipartite Graphs and Latin Squares Without Proper Subrectangles by I. M. Wanless, Electronic J. Combin. 6 (1999), R9.

$\endgroup$
2
  • 1
    $\begingroup$ Some time after writing the "pan-Hamiltonian" paper referenced by Brendan McKay we came to prefer the name "row-Hamiltonian" for the case when, for all pairs of two different rows a and b, the permutations $ab^{-1}$ is a single cycle. There are several infinite families of row-Hamiltonian Latin squares known. Most are for prime orders only, but one family is known for order $p^2$, where $p$ is prime. There are also sporadic cases known for orders that are not prime powers. $\endgroup$ Feb 7, 2022 at 6:49
  • 1
    $\begingroup$ A stronger property than row-hamiltonian is to also require the analogous property to hold for the permutations that define columns, and also for the permutations that dictate the positions of symbols. When all these properties hold simultaneously, the Latin square is called "atomic". Cayley tables of cyclic groups of prime order are one such class, but there are others known. These include infinite families of atomic squares of prime order, and some sporadic examples of composite order. It is an open question whether the atomic property can be achieved for orders that are not prime powers. $\endgroup$ Feb 7, 2022 at 6:56
3
$\begingroup$

Since the quasigroups are the algebraic structures that correspond to Latin squares, one of the first things that I would do is try to investigate if these Latin squares satisfy any special identities or if they can be characterized as the algebras that satisfy a collection of identities. It turns out that when we add the condition that all cycles in the permutations $x\mapsto a*(b\setminus x)$ are of length $p$ whenever $a\neq b$, then such quasigroups can easily be axiomatized using identities.

If $(X,*,/,\backslash)$ is a quasigroup, then define mappings $L_{a},R_{a}:X\rightarrow X$ by letting $L_{a}(x)=a*x,R_{a}(x)=x*a$.

Observation: Let $p$ be a prime. Let $(X,*,/,\backslash)$ be a quasigroup. The following are equivalent:

  1. if $a\neq b$, then all the cycles in the permutation $x\mapsto a\backslash(b*x)$ are finite of length $p$,

  2. $(X,*,/,\backslash)$ satisfies the identity $(L_{x}L_{y}^{-1})^{p}(z)=z$.

The general case

The quasigroups associated with the Latin squares with one cycle type can be endowed with 5-ary algebraic operations that satisfy non-trivial identities.

Let $X$ be a finite set, and let $F_{X}$ denote the free group generated by $X$. Then we say than an element $h\in F_{X}$ is Brunnian if whenever $\phi:F_{X}\rightarrow G$ is a group homomorphism such that $\phi(x)=e$ for some $x\in X$, then $\phi(h)=e$. For example, if $[x,y]=xyx^{-1}y^{-1}$, and $X=\{x_{1},\dots,x_{n}\},|X|=n$, then the iterated commutator $[x_{1},[x_{2},[\dots[x_{n-1},x_{n}]\dots]]]$ is always Brunnian.

Suppose that $(X,*,/,\setminus)$ is a finite quasigroup such that if $a\neq b,c\neq d$, then the mappings $x\mapsto a\setminus(b*x),x\mapsto c\setminus(d*x)$ have the same cycle type. Let $s,t:X^{5}\rightarrow X$ be 5-ary operations such that $s(a,b,c,d,t(a,b,c,d,x))=t(a,b,c,d,s(a,b,c,d,x))=x$ whenever $a,b,c,d,x\in X$ and where if $a\neq b,c\neq d$, then $c\setminus(d*x)=s(a,b,c,d,a\setminus (b*t(a,b,c,d,x))).$

If $a\in X$, then define permutations $L_{a},R_{a}:X\rightarrow X$ by letting $L_{a}(x)=a*x,R_{a}(x)=x*a$.

Suppose now that $a,b,c,d\in X$. Then define a permutation $h_{a,b,c,d}$ $X$ by letting $h_{a,b,c,d}(x)=t(a,b,c,d,x).$

Let $w\in F=F_{l_{1},l_{2},l_{3},l_{4},r_{1},r_{2},r_{3},r_{4},q}$ be an element such that

i. if $\phi:F\rightarrow G$ is a group homomorphism with $\phi(l_{3}^{-1}l_{4})=\phi(q^{-1}l_{1}^{-1}l_{2}q)$, then $\phi(w)=e$,

ii. if $\phi:F\rightarrow G$ is a group homomorphism with $\phi(l_{1})=\phi(l_{2}),\phi(r_{1})=\phi(r_{2})$, then $\phi(w)=e$, and

iii. if $\phi:F\rightarrow G$ is a group homomorphism with $\phi(l_{3})=\phi(l_{4}),\phi(r_{3})=\phi(r_{4})$, then $\phi(w)=e$.

For example, every Brunnian element in $F$ satisfies the conditions i-iii.

Define a homomorphism $\psi_{a_{1},a_{2},a_{3},a_{4}}:F\rightarrow\text{Sym}(X)$ by letting $\psi(q)=h_{a_{1},a_{2},a_{3},a_{4}}$ and $\psi(l_{k})=L_{a_{k}},\psi(r_{k})=R_{a_{k}}$ whenever $1\leq k\leq 4$. Then the algebraic structure $(X,*,/,\backslash,s,t)$ satisfies the identity $\psi_{a_{1},a_{2},a_{3},a_{4}}(w)(x)=x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.