Si una potencia de 2 divide un número, ¿en qué condiciones divide un coeficiente binomial que involucra al número que divide?

Question

Hemos tenido muchas preguntas aquí sobre la divisibilidad de $\binom{n}{k}$, muchas de ellas tratan sobre la divisibilidad por potencias de primos, o expresiones que involucran el $\textrm{gcd}(n,k)$ (originalmente di varios ejemplos más pero tomé el consejo de TheSimpliFire para acortar la lista, y muchos otros ejemplos todavía se pueden encontrar mirando el historial de ediciones de esta pregunta):

• ¿Cómo podemos probar que un coeficiente binomial (n elige k) es divisible por la razón de n y el gcd(n,m)?
• Demostrando que el número primo $p$ divide a $\binom{p}{k}$ para $k\in\{1,\ldots,p-1\}$

El tema también ha llevado a algunos artículos de investigación interesantes recientemente:

• En 2014: Algunas propiedades de divisibilidad de coeficientes binomiales y $q$-binomiales.
• En 2017: Divisibilidad de coeficientes binomiales y generación de grupos alternantes.
• En 2019: Sobre la divisibilidad de coeficientes binomiales.

También hay muchos teoremas asociados:

• El teorema de Kummer
• El teorema de Lucas
• El teorema de Granville
• El teorema de Désarménien

Sin embargo, me encontré con un problema relacionado que está expresado completamente en el título, y sorprendentemente no está cubierto por el extenso cuerpo de literatura anterior. En MathJax, si $s>0$ es un entero (también hagámoslo el mayor para el cual $2^s$ divide a $n$), ¿bajo qué condiciones de $k$ tenemos lo siguiente:

$$ 2^s \mid n \implies 2^s \left\vert \binom{n}{k} \right. . \tag{1} $$

Dado que $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$ y $2^s \mid n$ nos queda determinar cuándo $\frac{q}{k} \binom{n-1}{k-1}$ es un entero ($q$ siendo el resultado cuando se divide $n$ por $2^s$).

La implicación funciona para un número notable de casos, pero no siempre (por ejemplo si $\binom{n}{k}$ es impar).

Answer 1

Este es un comentario, pero un comentario un poco largo.

Recuerde la definición de la valuación $2-$ádica de $n,$ $\nu _2(n),$ que significa el mayor exponente de $2$ que divide a $n.$

Su problema, entonces, se puede expresar como $s\leq \nu _2(n)$ implica $s\leq \nu _2 \left( \binom{n}{k}\right ).$ A partir del teorema de Legendre (es decir, $\nu _2(n!)=n-S_2(n)$ donde $S_2(n)$ es la suma de los $1$'s en la expansión $2-$ádica de $n$), no es difícil demostrar que $$\nu _2 \left( \binom{n}{k}\right )=n-S_2(n)-(k-S_2(k))-(n-k-S_2(n-k))=S_2(n-k)+S_2(k)-S_2(n).$$ y $$\nu _2(n)=\nu_2(n!)-\nu _2((n-1)!)=1+S_2(n-1)-S_2(n).$$ Así que su proposición se convierte en

$s-1\leq S_2(n-1)-S_2(n)$ implica $s\leq S_2(n-k)+S_2(k)-S_2(n).$

esto puede, al menos, cumplirse si $S_2(n-1)+1\leq S_2(n-k)+S_2(k).$ Esto es trivial si $k=1.$ Por ejemplo, si $n$ es impar, esto es equivalente a $S_2(n)\leq S_2(n-k)+S_2(k)$ lo cual siempre es el caso, por ejemplo, si la expansión de $k$ tiene $1'$s donde hay un $1$ en la expansión de $n.$

Answer 2

Con la ayuda muy útil del consejo del usuario BillyJoe, podemos decir que para cualquier primo $p$,

$$\tag{1} \binom{n}{k} \equiv \left\langle {n_{s-1}\cdots n_0 \atop k_{s-1}\cdots k_0} \right\rangle \prod_{j=1}^{r-s+1}\left\langle {n_{j+s-1}\cdots n_j \atop k_{j+s-1}\cdots k_j} \right\rangle\left\langle {n_{j+s-2}\cdots n_j \atop k_{j+s-2}\cdots _j} \right\rangle^{-1} \left( \textrm{mod} ~ p^s \right), $$

donde los índices 0 y $r$ representan los términos correspondientes a las potencias más bajas y más altas (respectivamente) en las expansiones p-ádicas de $n$ y $k$, y los corchetes angulares corresponden a una ligera modificación (descrita con más detalle aquí) de los símbolos ordinarios del coeficiente binomial.

Entonces tenemos que:

$$ \left\langle {n_{s-1}\cdots n_0 \atop k_{s-1}\cdots k_0} \right\rangle \prod_{j=1}^{r-s+1}\left\langle {n_{j+s-1}\cdots n_j \atop k_{j+s-1}\cdots k_j} \right\rangle\left\langle {n_{j+s-2}\cdots n_j \atop k_{j+s-2}\cdots _j} \right\rangle^{-1} \equiv 0 \left( \textrm{mod} ~ p^s \right),\tag{2} $$

si y solo si $p^s \mid \binom{n}{k}$.

Por lo tanto, tenemos una condición general para cuando $p^s$ divide a $\binom{n}{k}$, ya sea que $p^s \mid n$.

Para el caso especial donde $p=2$ y $2^s \mid n$, que fue la premisa de la pregunta original, tal vez podamos obtener una expresión más limpia que la que tengo arriba en la Ecuación 2.