Partitioning of square lattice into equivalence classes under congruence relation

95 Views Asked by At

Let $m,n$ be positive integers. Consider the set $S^{\small(m)}_n=([1,n]\cap\mathbb N)^m$ having $n^m$ points in the Euclidean space $\mathbb R^m$ arranged in a square (cubic, etc) lattice.

Two subsets of $S^{\small(m)}_n$ are congruent if one can be transformed into the other by a combination of rigid motions: translations, rotations, and reflections. We can see that the congruence is an equivalence relation. Partition the powerset $\mathcal P(S^{\small(m)}_n)$ into equivalence classes under this relation. Let $a^{\small(m)}_n$ be the number of resulting equivalence classes.

We can see that for the linear case $a^{\small(1)}_n=2^{n-1}+1.$

Can we find similar formulae for $a^{\small(2)}_n$ or $a^{\small(3)}_n$, or even a general case $a^{\small(m)}_n$? Or can we at least find a few initial terms of these sequences?

1

There are 1 best solutions below

0
On

The case $a_n^{(2)}$ is given by sequence A054247 in the OEIS, which starts $1, 2, 6, 102, 8548,\ldots$.

I believe that $a_2^{(3)}=22$. As a subset of the $27$ vertices of a $3\times 3\times 3$ cube can be taken to at most $48$ subsets via symmetries of the cube, $a_3^{(3)}$ is at least $\left\lceil\frac{2^{27}}{48}\right\rceil=2796203$. If my calculation for $a_2^{(3)}$ is correct, then the sequence $a_n^{(3)}$ is not in the OEIS, as it contains no increasing sequences which start with $1,2,22$ and continue to a sufficiently large third term.

In general, the lower bound $2^{n^m}/(2^m\cdot m!)$ will, for fixed $m$, be asymptotically tight as $n$ grows large. This is because a randomly-chosen subset of a large $m$-dimensional cube will typically have no symmetries, and so will have an orbit of full size. One can see this in the $m=2$ case: the lower bound of $2^{n^2}/8$ is already at $99.99\%$ of the true value when $n=6$.