9
$\begingroup$

This is a follow up on another MO question.

Question. For $n\geq2$, the following is always an integer. Is it not? $$\frac{(2^n-2)(2^{n-1}-2)\cdots(2^3-2)(2^2-2)}{n!}.$$

$\endgroup$

2 Answers 2

17
$\begingroup$

As $S_n$ also embeds in $GL_{n-1}({\mathbb F}_2)$, you only need to check that $n!$ is not divisible by $2^n$.

$\endgroup$
7
  • $\begingroup$ But it never is. $\endgroup$ Mar 24, 2017 at 23:10
  • $\begingroup$ (1) It is possible for $2^{n-1}$ to divide $n!$. (2) $\mathfrak{S}_n$ embeds in $GL_n(\mathbb{F}_2)$ as permutation matrices, but how does it embed in $GL_{n-1}(\mathbb{F}_2)$? (3) At any rate, although I like to approach again, however this answer need more details. I wish it works. $\endgroup$ Mar 24, 2017 at 23:17
  • 7
    $\begingroup$ If $V={\mathbb F}_2^n$ with the permutation action of $S_n$ and $W$ is the subspace of $V$ spanned by $(1,1,\ldots,1)$, then $W$ is $S_n$-invariant and thus $S_n$ acts on $V/W$. The almost simplicity of $S_n$ guarantees that this action is faithful for all $n>4$, and you can check the smaller cases. $\endgroup$ Mar 24, 2017 at 23:26
  • $\begingroup$ Incidentally, there's a subspace $X$ of $V$ consisting of all vectors whose entries sum to zero that is also invariant under $S_{n}$. If $n$ is even, then $X$ contains $W$ and this gives an embedding of $S_{n}$ into $GL_{n-2}(\mathbb{F}_{2})$ (provided $n > 4$) and as a corollary, one gets that $\frac{(2^{n} - 4)(2^{n-1}-4) \cdots (2^{3}-4)}{n!}$ is an integer for $n$ even and $n \geq 4$. $\endgroup$ Mar 25, 2017 at 0:34
  • 1
    $\begingroup$ Just to explain the last part of John's answer: the group-theoretic argument shows that the quotient $Q=(2^n-2) \cdots (2^2-2)/n!$ is an odd integer times $2^m$ for some $m \in \mathbb{Z}$. Since $n!$ is not divisible by $2^n$, we have $v_2(n!) \leq n-1$ so that $v_2(Q) \geq 0$. $\endgroup$ Mar 25, 2017 at 12:30
11
$\begingroup$

Here is a direct number theoretic proof. First of all note that $$(2^n-2)(2^{n-1}-2)\cdots(2^2-2)=2^{n-1}(2^{n-1}-1)(2^{n-2}-1)\cdots(2^1-1).$$ Now for any prime $p$ we have, by Legendre's formula and by Fermat's little theorem, $$v_p(n!)\leq\left\lfloor\frac{n-1}{p-1}\right\rfloor\leq v_p\bigl(2^{n-1}(2^{n-1}-1)(2^{n-2}-1)\cdots(2^1-1)\bigr),$$ where for the second inequality we argue separately for $p=2$ and for $p\geq 3$. The result follows.

P.S. The above proof was inspired by Cherng-tiao Perng's deleted response (which was not entirely correct).

$\endgroup$
1
  • 2
    $\begingroup$ Indeed. I should have seen this and mentioned to Cherng-tiao how to fix it. Gerhard "Tenders His Most Sincere Apologies" Paseman, 2017.03.24. $\endgroup$ Mar 25, 2017 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.