14
$\begingroup$

Question. The following is always an integer. Is it not? $$\frac{(2^n-1)(2^n-2)(2^n-4)(2^n-8)\cdots(2^n-2^{n-1})}{n!}.$$

John Shareshian has supplied a cute proof. I'm encouraged to ask:

Question. Can you give alternative proofs, even if they are not particularly as short?

$\endgroup$
4
  • 6
    $\begingroup$ The first solution can be found by entering a few values into OEIS; see: A053601. $\endgroup$ Mar 24, 2017 at 17:56
  • 1
    $\begingroup$ Where is the combinatorics in this question? $\endgroup$
    – GH from MO
    Mar 25, 2017 at 0:04
  • 2
    $\begingroup$ Some of your questions are very interesting, while others like this one seem obvious and not so carefully thought out. It would be helpful if you could indicate some context for questions like this. The question currently has two votes to close; and I find it a bit unpleasant to close questions by established users like yourself. $\endgroup$
    – Lucia
    Mar 25, 2017 at 21:56
  • 1
    $\begingroup$ @Lucia: Thank you for your useful comment and astute suggestions. I shall try to give some background whenever applicable. $\endgroup$ Mar 25, 2017 at 22:43

2 Answers 2

47
$\begingroup$

It is, because $S_n$ embeds in $GL_n({\mathbb F}_2)$.

$\endgroup$
1
  • 2
    $\begingroup$ So does $S_{n+1}$ once $n \geq 2$, and even $S_{n+2}$ when $n$ is even and at least $6$ (acting on the quotient of the sum-zero binary vectors of length $n+2$ by the constant vectors; for $n=4$ there's still a homomorphism, but with nontrivial kernel!). So the denominator $n!$ can be replaced by $(n+1)!$ or $(n+2)!$ respectively for such $n$. $\endgroup$ Apr 9, 2017 at 20:52
6
$\begingroup$

Essentially the same argument: the ratio is a number of bases of the vector space $\mathbb{F}_2^n$.

A proof working also for composite values of $a=2$:

Let $p$ be a prime dividing $n!$. If $p$ divides $a$, then the product $\prod (a^n-a^k)$ is divisible by $p^{n-1}$, while $n!$ is not divisible by $p^n$. If $a$ and $p$ are coprime, it suffices to check that for any exponent $s$ the set $\{a^n-a^k\}$ contains at least as many numbers divisible by $p^s$ as the set $\{1,\dots,n\}$. It follows from the fact that a period of powers of a sequence $\{1,a,a^2,\dots\}$ modulo $p^s$ is less than $p^s$.

$\endgroup$
0

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.