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?

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

2 Answers 2

Reset to default
47
$\begingroup$

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

Improve this answer
$\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$
    – Noam D. Elkies
    Commented 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$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .