Is there a way to estimate the number of Latin squares with a given autotopism?

Question

An autotopism of a Latin square $L$ of order $n$ is a triple of permutations $(\alpha,\beta,\gamma)$ for which $L$ is stabilized after permuting the rows by $\alpha$, the columns by $\beta$, and the symbols by $\gamma$.

Question: Is there a way to estimate the number of Latin squares with a given autotopism?

Basically I want an algorithm for the following problem:

• Input: order $n$, and permutations $\alpha$, $\beta$, $\gamma$ of $\{1,2,\ldots,n\}$.

• Output: Estimate for the number Latin squares of order $n$ for which $(\alpha,\beta,\gamma)$ is an autotopism.

Estimates for the number of Latin squares have been computed in:

• McKay and Rogoyski, 1995: full text.

• Kuznetsov, 2009: DOI.

• Zhang and Ma, 2009: arXiv; full text.

I compare these estimates in my survey paper, Figure 2. These papers therefore answer the $\theta=(\mathrm{id},\mathrm{id},\mathrm{id})$ case.

I plan to use this number for analysing a cryptographic application (as described in A Latin square autotopism secret sharing scheme, 2016). Informally, I want to say "the number is really big, around [this big] according to estimates, therefore successful attacks are highly improbable".

Answer 1

This is a dumb answer, and will not yield information quickly. I give it in hopes that it inspires smarter answers.

I use the triple form of representation for a Latin square, which is a collection of $n^2$ triples (a,b,c) whose properties you can guess or read about on Wikipedia. I am using symbols 1 through n, thus every Latin square in this post has a triple of the form (1,1,c) for c being one of the $n$ symbols.

The algorithm essentially builds partial transversals until "it feels good" about estimating the remaining number resulting from information gathered so far. I use a, b and c to represent both the permutations above (so I don't keep typing $\alpha,\beta,\gamma$) and the result when applying it to a triple. So for each of the triples (1,1,c), I apply the permutation to get (a,b,c'), another triple. I repeat this operation (so apply the permutation to (a,b,c') to get (a',b',c''), and iterate) until I get a clash (I produce something like (1,1,c'') for c'' different from c ) or I return to the triple I started with, namely (1,1,c).

If I got a clash, then I toss out (1,1,c), otherwise I have an orbit size, which is a number $m$ depending on $c$ which shows how the input permutation when iterated acted on (1,1,c). I now start with a triple distinct from all of the allowed orbits computed thus far, (if there is one) and compute its orbit size if it has one, say $m'$.

If the orbit sizes are large (approaching some fraction of $n^2$), then there will be few if any Latin squares preserved under the permutation. If the orbit sizes are small (say less than n), then there will be many. Since an estimate is wanted for output, I would stop after computing a few orbits and use a look-up table or some other heuristic for producing an estimate.

This is a dumb answer partly because for permutations close to the identity or well synchronized, the orbits will be small and the estimate is likely to be very poor or take a very long time. For a random triple, it is conceivable the orbits will be large and that the estimate will show very few Latin squares are preserved. Thus one might be able to tell after $n^3$ operations what situation you are in, and then run a more expensive and discriminating algorithm once this simple minded test has been applied.

Gerhard "Tis Giftly To Be Simple" Paseman, 2017.04.18.