Bounds on the Number of Small Latin Subsquares
Let ζ(n,m) be the largest number of
order m subsquares achieved by any Latin square of order n.
We show that ζ(n,m)=Θ(n^3) if m in {2,3,5}
and ζ(n,m)=Θ(n^4) if m in {4,6,9,10}.
In particular,
n^3/8+O(n^2)≤ζ(n,2)≤n^3/4+O(n^2)
and
n^3/27+O(n5/2)≤ζ(n,3)≤n^3/18+O(n2)
for all n.
We find an explicit bound on ζ(n,2^d)
of the form Θ(nd+2) and which is achieved only by
the elementary abelian 2-groups.
For a fixed Latin square L let ζ*(n,L) be the largest number of
subsquares isotopic to L achieved by any Latin square of order n.
When L is a cyclic Latin square we show that
ζ*(n,L)=Θ(n^3). For a large class of Latin squares L we
show that ζ*(n,L)=O(n^3). For any Latin square L we give an
ε in the interval (0,1) such that
ζ*(n,L)≥Ω(n2+ε). We believe that this
bound is achieved for certain squares L.