Bounds on the number of autotopisms and subsquares of a Latin square (Q2448962): Difference between revisions

In this paper the authors consider two extremal questions about a Latin square \(L\) of order \(n\): (1) What is the maximum value of \(I_k(L)\) (the number of \(k\times k\) subsquares of \(L\)), and (2) what is the maximum cardinality of the group of autotopisms of L (denoted \(\text{Atp}(L)\))? Regarding the first question, the authors show that \(I_k(L)\leq n^{\Theta (\log k)}\), which is a substantial improvement on the bound \(I_k(L)\leq n^{\Theta (\sqrt{k})}\) given by \textit{J. M. Browning} et al. [Commentat. Math. Univ. Carol. 51, No. 2, 175--184 (2010; Zbl 1224.05061)]. For the second question, the authors show that \(| \text{Atp}(L)| \leq n^2 \prod_{t=1}^{\lfloor \log _2 n\rfloor}(n-2^{t-1})\). Proof techniques for this theorem bear similarity to those used by \textit{G. L. Miller} [in: Proceedings of the 10th annual ACM symposium on theory of computing, STOC '78, San Diego, CA, USA, May 1--3, 1978. New York, NY: Association for Computing Machinery. 51--58 (1978; Zbl 1282.68192)]. This result leads to asymptotic formulas concerning prime power divisors of \(R_n\), the number of reduced Latin squares of order \(n\). For example, if \(p\) is prime and \(\omega _p (n)\) denotes the largest integer such that \(p^{\omega _p (n)}\) divides \(R_n\), then \(\omega _p (n)\geq \frac{n}{p-1}-O(\log ^2 n)\).