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$
  • 6
    $\begingroup$ The first solution can be found by entering a few values into OEIS; see: A053601. $\endgroup$ – Benjamin Dickman Mar 24 '17 at 17:56
  • 1
    $\begingroup$ Where is the combinatorics in this question? $\endgroup$ – GH from MO Mar 25 '17 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 '17 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$ – T. Amdeberhan Mar 25 '17 at 22:43
47
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 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$ – Noam D. Elkies Apr 9 '17 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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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