Dear All,

I am considering maximal subgroups of odd index in Alternating and Symmetric groups, and this leeds me to some questions on binomial coefficients that I presently do not know and that I need some hints and suggestions :

  1. Assume that $ab=2^t$ with $a>1, b>1,t\geq 3$. Which values of $a$ and $b$ such that $$\frac{(2^t)!}{(a!)^b.b!}$$ is odd and smallest.

  2. Let $n\geq 9$ be an odd integer (not prime) and $p$ the largest prime less than $n$. Is there always an integer $r\geq 1$ such that $\binom{n}{r}$ is odd and divisible by $p$. Note that this is not true for the case $n=9$. Is it also true for $n$ even?

Thanks you very much in advance for comments and advice.

  • $\begingroup$ Use Lucas's theorem: http://en.wikipedia.org/wiki/Lucas'_theorem $\endgroup$ – Chris Godsil Jun 23 '12 at 15:23
  • $\begingroup$ For (1), the quotients are all odd, and I think the smallest occur when $b=2$. I think this can be proved with Stirling's formula, but perhaps there is a nice inductive argument. $\endgroup$ – Douglas Zare Jun 23 '12 at 17:12
  • $\begingroup$ @Chris Godsil : Thanks for your indicating me to use Lucas's theorem that I did not know before. @Douglas Zare : Thanks. I also think that the smallest occurs when $b=2$ but I am still on the way to prove that. $\endgroup$ – Ben Jun 25 '12 at 7:24

Hi! I have a proposed answer for 2).

You can construct an infinite series of counter examples. Erdos proved that there are primes between $n$ and $2n$. Now consider $2n=2^k$ for some $k>2$.

We can observe that the binomial number $\binom{2n+1}{r}, 1< r < n+1$ is always even. The upper product have powers of 2 as the following sequence: $\lbrace k,1,2,1,3,\dots,s \rbrace$
while the bottom product have powers of 2 of the form: $\lbrace 1,2,1,3,\dots,s,k-1\rbrace$.
This can be reflected for cases $\binom {2n+1}{r}, n < r < 2n$.

The difference of the sum of these 2 sequences is at least 1. As a result, the binomial number may be divisible by $p$ but it will not be even.

(Edit) Exception: When the binomial number is $\binom{2n+1}{1}$ or $\binom{2n+1}{2n}$ you have either no powers of 2 or same powers of 2. But in this case it will not be divisible by $p$.

  • $\begingroup$ More generally, using Lucas' Theorem, take q to be the smallest prime greater than 2^t with q not a Mersenne prime, then any number m between 2^t and q should serve: When n is large enough for m choose n to be divisible by the preceding prime p, the binary expansion of n will start with 1 in a place where m's expansion has a 0. One can also do this starting with b times 2^t for small odd numbers b, providing b2^t+1 is not prime. Gerhard "Ask Me About Systtem Design" Paseman, 2012.06.23 $\endgroup$ – Gerhard Paseman Jun 23 '12 at 18:26
  • $\begingroup$ Oops. For b=3 it will not work. This may lead to characterizing which m ha e the desired property. Gerhard "Ask Me About System Design" Paseman, 2012.06.23 $\endgroup$ – Gerhard Paseman Jun 23 '12 at 20:06
  • $\begingroup$ Thanks for your answer and comments. In fact, Nagura proved that for $n\geq 25$, there exists a prime between $n$ and $\frac{6}{5}n$. And if we take any $n$ in the interval $[2^t+[2^t/6]+1,2^{t+1}-1]$ and $r=n-2^t$ then $\binom{n}{r}$ should do the job. $\endgroup$ – Ben Jun 26 '12 at 20:27
  • 1
    $\begingroup$ Chebyshev was the first who proved this, not Erdos:) $\endgroup$ – Fedor Petrov Sep 8 '16 at 7:33

About the question (1), I quoted here the result from this paper of Attila Maróti

First, We may assume that $a\geq b$ since if $b>a$ then $$b!^{a-1}=a!^{a-1}(a+1)^{a-1}\cdots b^{a-1}>a!^{a-1}a^{(b-a)(a-1)}$$ In addition, we have that $a^{a-1}>1.2.\cdots.a=a!$ and so $$b!^{a-1}>a!^{a-1}a!^{b-a}=a!^{b-1}$$ which implies that $$b!^a.a!>a!^b.b!\Rightarrow \frac{m!}{a!^b.b!} > \frac{m!}{b!^a.a!}$$

Assume now that $m=a_1b_1=a_2b_2$ with $b_1\leq a_1, b_2\leq a_2$. If $b_1\leq b_2$ and $a_1\geq a_2$ then

$$a_1!^{b_1}.b_1! \geq a_2!^{b_1}(a_2+1)^{b_1}\cdots a_1^{b_1}b_1! \geq a_2!^{b_1}a_2^{(a_1-a_2)b_1}b_1! \quad (\rm{since ~ a_1\geq a_2})$$

$$ = a_2!^{b_1}b_1! (a_2^{a_2})^{\frac{b_1}{a_2}(a_1-a_2)} = a_2!^{b_1}b_1! (a_2^{a_2-1}a_2)^{\frac{b_1}{a_2}(a_1-a_2)} $$

$$\geq a_2!^{b_1}b_1! (a_2!b_2)^{\frac{b_1}{a_2}(a_1-a_2)} = a_2!^{b_1}b_1! (a_2!b_2)^{b_2-b_1} \quad (\rm{since ~ a_2\geq b_2 ~ and ~ a_1b_1=a_2b_2})$$

$$ \geq a_2!^{b_2}b_1!(b_1+1)\cdots b_2 = a_2!^{b_2}b_2! \quad (\rm{since ~ b_2\geq b_1})$$ and hence $$\frac{m!}{a_1!^{b_1}.b_1!}\leq \frac{m!}{a_2!^{b_2}.b_2!}$$


Your first problem has a simple solution. Suppose $p$ is a prime and $(n!)_p$ is the $p$-part of $n!$. Dirichlet proved $(n!)_p=p^k$ where $k = (n-s_p(n))/(p-1)$ and $s_p(n)$ is the sum of the base-$p$ digits of $n$. Let $a=2^\alpha$ and $b=2^\beta$. Then $(a!)_2 = 2^{a-1}$, $(b!)_2 = 2^{b-1}$ and $((ab)!)_2 = 2^{ab-1}$. The index of the imprimitive group $S_a\wr S_b$ in $S_{ab}$ is $(ab)!/((a!)^b\,b!)$ and this odd for all $\alpha,\beta\geqslant0$.

Proof: $((a!)^b\,b!)_2 = (2^{a-1})^b\,2^{b-1}=2^{ab-1}=((ab)!)_2$. Thus a Sylow 2-subgroup of $S_a\wr S_b$ has order $2^{ab-1}$ as does a Sylow 2-subgroup of $S_{ab}$, and so $(ab)!/((a!)^b\,b!)$ is odd. QED


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.