Asymptotics of A000613

Question

The general linear group $GL_n(\mathbb{F}_2)$ acts on the powerset $2^{{\mathbb{F}_2}^n \setminus \{0\}}$ by multiplication: $A \cdot S := \{Ax \in {\mathbb{F}_2}^n : \, x \in S\}$, for an invertible matrix $A \in GL_n({\mathbb{F}}_2)$ and a subset $S \subseteq {\mathbb{F}_2}^n$ not containing the zero vector. Let $$a(n) := |2^{{\mathbb{F}_2}^n \setminus \{0\}}/GL_n(\mathbb{F}_2)|$$ be the number of distinct orbits of this group action.

For example, when $n = 1$, the orbit space $2^{{\mathbb{F}_2}^1 \setminus\{0\}}/GL_1(\mathbb{F}_2) = 2^{\mathbb{F}_2 \setminus \{0\}}/\{[1]\} \cong 2^{\mathbb{F}_2 \setminus \{0\}}$, so $a(1) = 2^{|\mathbb{F}_2 \setminus \{0\}|}| = 2^1 = 2$.

When $n = 2$, the orbits are $O_1 =\{\emptyset\}$, $O_2=\{\{i\}, \{j\}, \{i + j\}\}$, $O_3 = \{\{i, j\}, \{i, i + j\}, \{j, i + j\}\}$, and $O_4 = \{\{i, j, i + j\}\}$. Here $i = \binom{1}{0}$, $j = \binom{0}{1}$ is the standard basis. So $a(2) = 4$.

In fact $(a(n))_{n \ge 1} = (2, 4, 10, 46, 1372, 475499108, \dots)$ is A000613 from the Online Encyclopaedia of Integer Sequences.

What are the asymptotics of $a(n)$ as $n \to \infty$? An obvious upper bound is $$a(n) \le |2^{{\mathbb{F}_2}^n \setminus \{0\}}| = 2^{2^n - 1} < 2^{2^n}.$$ If $S, S' \subseteq {\mathbb{F}_2}^n \setminus \{0\}$ have different cardinality, then their orbits $GL_n(\mathbb{F}_2) \cdot S$ and $GL_n(\mathbb{F}_2) \cdot S'$ are necessarily distinct. In other words, the $GL_n(\mathbb{F}_2)$-action restricts to an action on $\binom{{\mathbb{F}_2}^n \setminus \{0\}}{k}$ for each $k = 0, 1, \dots, 2^n - 1$. Thus an obvious lower bound is $$a(n) = \sum_{k = 0}^{2^n - 1} \left|\binom{{\mathbb{F}_2}^n \setminus \{0\}}{k}/GL_n(\mathbb{F}_2)\right|\ge \sum_{k = 0}^{2^n - 1} 1 = 2^n.$$ In summary, $$2^n \le a(n) < 2^{2^n}.$$ Is $a(n)$ asymptotically closer to $2^n$ or $2^{2^n}$?

Answer 1

Using Burnside's lemma it's not too hard to see that $a(n)$ is asymptotic to $2^{2^n}/|GL_n(\mathbb F_2)|$, since every non-identity element of $GL_n(\mathbb F_2)$ contributes at most $2^{ (3/4) 2^{n}}$ to $\sum_{g\in GL_n(\mathbb F_2)} |X^g|$ and these terms are swamped by the $2^{2^n}$ contribution from the identity. As Dave Benson points out, this is much closer to $2^{2^n}$ in growth rate.

Answer 2

Since the order of $GL(n,2)$ is less than $2^{n^2}$, $a(n)$ is at least $2^{2^n−1−n^2}$. I think it's closer to that than to $2^{2^n}$. In particular, this shows that $$\lim_{n\to\infty}\frac{\log_2\log_2 a(n)}{n}=1.$$