Números "binomables"

Question

¿Existe un buen criterio para determinar si un determinado $m$ puede escribirse como un número binomial $\binom{n}{k}$ con $1 < k < n-1$ ?

He estado pensando en este problema con un amigo y lo único que concluimos es que los primos no son "binomiables".

RECLAMACIÓN 1. Los primos no son "binomiables".

Prueba. Dejemos que $p$ un primo y supongamos $p = \binom{n}{k}$ .

• Si $n$ es primo, entonces $n$ debe ser igual a $p$ porque $n\mid \binom{n}{k}$ . Pero, en este caso, $n\mid\mid \binom{n}{k}$ Así que $k=1$ . (Esto también serviría para las potencias primarias).

• Si $n$ se compone, tenga en cuenta que $\binom{n}{k} = p$ implica, a fortiori que $p\mid \binom{n}{k}$ y en consecuencia $p\leqslant n$ . Pero en nuestras condiciones, $\binom{n}{k} > n$ contradicción. $\square$

Además, ya he visto en Pruebas de EL LIBRO el problema "Los coeficientes binomiales no son (casi) nunca potencias", y aunque está muy relacionado, no aporta mucho a este problema (al menos hasta donde yo entendí).

---

EDITAR: ¡Los primeros poderes no son binomiables también!

Enunciemos primero tres resultados:

1. Lema. Dejemos que $p$ un primo. Si $p\mid n$ y $0<k<p$ entonces $p\mid \binom{n}{k}$ .

   Prueba. Dejemos que $n= pm$ y asumir $0<k<p$ . Considera la identidad de los Vandermonde:

   $$\binom{pm}{k} = \sum_{j=0}^k \binom{p}{j}\binom{p(m-1)}{k-j}.$$

   De ello se desprende que $\binom{pm}{k}\equiv \binom{p(m-1)}{k} \mod{p}$ (el término $j=0$ en la suma). Repitiéndolo $m$ veces, concluimos $\binom{pm}{k}\equiv \binom{p}{k} \mod{p}$ y de $p\mid \binom{p}{k}$ sigue nuestra declaración. $\square$

2. El postulado de Bertrand. Si $n\geqslant 2k$ entonces el binomio $\binom{n}{k}$ tiene un factor primo $q > k$ .

3. Teorema. [Erdös] El binomio $\binom{n}{k}$ nunca es un poder perfecto para $4\leqslant k\leqslant n-4$ .

   (Este es el párrafo que mencioné en Pruebas de EL LIBRO .)

Por lo tanto, sólo hay que analizar dos casos, $k=2$ y $k=3$ . En ambos casos podemos suponer $n \geqslant 6$ .

RECLAMO 2. Los primeros poderes no son "binomiables".

Prueba. Dejemos que $p$ un primo, $m>1$ y supongamos que $p^m = \binom{n}{k}$ .

• Si $k=2$ entonces $p^m = \frac{n(n-1)}{2}$ . Por el postulado de Bertrand, $p\neq 2$ . Ahora observe que $\gcd(n, n-1) = 1$ Así que $$ p^m \mid n\quad \text{xor}\quad p^m\mid n-1. $$ Entonces: $$2 =\frac{n(n-1)}{p^m} \geqslant n-1 \implies n \leqslant 3,$$ que contradice $n\geqslant 6$ .

• Si $k=3$ entonces $p^m = \frac{n(n-1)(n-2)}{6}$ . El postulado de Bertrand nos permite tomar $p\neq 2,3$ . Por lo tanto, de forma similar al caso anterior, podemos deducir: $$p^m \mid n \quad \text{xor}\quad p^m\mid n-1 \quad \text{xor} \quad p^m\mid n-2.$$ Pero entonces: $$ 6 = \frac{n(n-1)(n-2)}{p^m} \geqslant (n-1)(n-2) \implies n \leqslant 4,$$ una contradicción. $\square$

---

EDITAR 2: Acabo de darme cuenta de que no he utilizado el Lemma en absoluto. De todas formas, creo que lo dejaré aquí, puede ser útil algún día jajaja

Answer 1

He aquí una respuesta parcial para un caso especial: si $\sqrt{8n+1}$ es un entero impar, entonces $n$ es un coeficiente binomial de la forma $n \choose 2$ . Esta fórmula es posible porque $n \choose 2$ es cuadrática en $n$ y, por tanto, tiene una solución sencilla.

Answer 2

No creo que haya un criterio simple, pero se podría construir un algoritmo para determinarlo con una complejidad de tiempo de $O((\ln c)^2)$ coeficientes binomiales o $O((\ln c)^3)$ multiplicaitones. Además, puede ser desconocido o difícil de determinar con total certeza si el número es realmente primo o no.

Lo que podemos utilizar es estimar los coeficientes:

$$\binom{n}{k} = {\prod_0^k (n-j)\over\prod_0^k j} = {\prod_0^k (n-(k/2)+k/2-j)\over\prod_0^k j} \\ = \begin{cases} {(n-k/2)\prod_0^{(k-1)/2} (n-(k/2)-k/2+j)(n-(k/2)+k/2-j)\over\prod_0^k j} = {(n-k/2)\prod_0^{(k-1)/2} (n-(k/2))^2-(k/2+j)^2\over\prod_0^k j} & \text{ if } k \text{ is odd } \\ {\prod_0^{k/2} (n-(k/2))^2-(k/2+j)^2\over\prod_0^k j} & \text{ if } k \text{ is even } \\ \end{cases} \\ \le {(n-k/2)^k\over k!}$$

También podemos estimarlo desde abajo:

$${(n-k)^k\over k!} \le \binom{n}{k} \le {(n-k/2)^k\over k!}$$

Así que dado $k$ tenemos una estimación para $n$

$$(k!c)^{1/k} \le n \le (k!c)^{1/k} + k/2$$

Además, como sólo tenemos que considerar $2k<n$ podemos utilizar la estimación:

$$\binom{n}{k} \ge \binom{2k}{k} = {(2k)!\over k!k!}$$

Así que no tenemos que considerar $k$ con $(2k)!/(k!)^2 > c$ y como es creciente podemos terminar el algoritmo una vez que sucede.

---

Tomemos como ejemplo las cifras $8008$ y $8009$ (la última es la primera)

Tenemos los rangos de $n$ en función de $k$ como:

$$\begin{matrix} k & n_{min} & n_{max} & \binom{2k}{k} \\ \hline 2 & 127 & 127 & 6\\ 3 & 37 & 37 & 20 \\ 4 & 21 & 22 & 70 \\ 5 & 16 & 18 & 252 \\ 6 & 14 & 16 & 924 \\ 7 & 13 & 15 & 3432 \\ 8 & & & 12870 \end{matrix}$$

Es decir, sólo tenemos que considerar $\binom{127}{2}$ , $\binom{37}{3}$ , $\binom{21}{4}$ , $\binom{22}{4}$ , $\binom{16}{5}$ , $\binom{17}{5}$ , $\binom{18}{5}$ , $\binom{14}{6}$ , $\binom{15}{6}$ , $\binom{16}{6}$ , $\binom{13}{7}$ , $\binom{14}{7}$ y $\binom{15}{7}$ . El cálculo de los mismos revela que $8008 = \binom{16}{6}$ y $8009$ no es ninguno de ellos.

La complejidad temporal se debe a la fórmula de stirlings para la condición de terminación:

$$\ln{(2k)!\over (k!)^2} = (2k \ln (2k) - 2k + O(\ln 2k))-2(k\ln k - k+O(\ln k)) \\ = 2k(\ln 2+\ln k) - 2k - 2k\ln k + 2k + O(\ln k) = 2k\ln 2 + O(ln k) < \ln(c)$$

Así que tenemos que considerar $O(\ln(c))$ valores de $k$ y para cada uno de ellos $k/2$ valores de $n$ haciéndolo $O((\ln(c))^2)$ coeficientes binomiales.

Answer 3

Sólo algunos comentarios hasta ahora:

---

Primer caso: buscamos casos en los que ${ a_j \choose 2 }=b_j^m$

Por fuerza bruta encontré el siguiente patrón muy probable, por el cual las secuencias $a_j$ y $b_j^2$ puede generarse directamente. En todos los casos $m=2$ No tenía ningún caso con $m \gt 2$ hasta ahora, excepto, por supuesto, cuando $b_1 = 1$ - aquí el exponente $m$ puede tomar cualquier valor.

• La secuencia de $a_j$ es
  $$ a_j = \{2,9,50,289,...\}_{j=1,2,3,...} $$ y tiene la fórmula de iteración $$a_{j}\underset{j\ge3}=6a_{j-1}-a_{j-2}-2$$ La cuestión de si $a_j$ puede ser primo tiene al menos para cada segundo $a_j$ una respuesta sencilla mediante esta fórmula: si $a_{j-2}$ es par, entonces también $a_j$ . Y como $a_1=2$ es par, todo $a_j$ con impar $j$ son compuestos. También parece que todos los $a_j$ en el índice par $j$ son cuadrados, sin embargo no he intentado derivar una conclusión análoga para esto desde la fórmula de recursión hasta ahora. Al menos, bajo el supuesto de que la secuencia parcial $c_{j}=a_{2j}=\{9,289,577,...\}$ tiene efectivamente sólo plazas $c_j^2$ entonces tenemos una recursión $ c_j = 6c_{j-1} - c_{j-2} $ y esto también excluiría $a_{2j}$ siendo primordial.
• La secuencia $b_j$ es $$\begin{array}{} b_j^2 = \{1,36,1225,41616,...\} \\ b_j = \{1, 6, 35, 204,...\} & \text{with iteration formula} \qquad b_{j}\underset{j\ge3}=6b_{j-1}-b_{j-2} \\ \end{array}$$

---

segundo caso: buscamos casos en los que ${ a_j \choose 3 }=b_j^m$ donde $m\ge2$

Primeros ejemplos por fuerza bruta ( $a_j \le 20,000,000$ ): $$ \begin{array} {r|r|rrrll} j & a_j & {a_j \choose 3}=b_j^m & & b_j &\text{^}m \\ \hline 1 & 3 & 1 &=& 1 &\text{^}0 \ldots \infty \\ 2 & 4 & 4 &=& 2 &\text{^}2 \\ 3 &50 & 19600 &=& 140&\text{^}2 \\ \end{array} $$

Curiosamente, W|A no encontró las soluciones excepto la trivial donde $b_j=0$

Answer 4

Sé que son compuestos.

Para demostrar esto, supongamos que no, es decir, $\binom mn=p$ un primo. Entonces $m\ge p$ . Ya que estamos excluyendo los casos triviales, $m\ge p+1$ y luego

$$\binom mn\ge\binom{p+1}2=p\cdot\frac{p+1}2\ge\frac32p>p$$

una contradicción.

Pero no todo número compuesto es un coeficiente binomial no trivial. Por ejemplo, $9$ no lo es.