18
$\begingroup$

Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$?

I've been thinking on this problem with a friend and all we concluded is that primes aren't "binomiables".

CLAIM 1. Primes aren't "binomiables".

Proof. Let $p$ a prime and suppose $p = \binom{n}{k}$.

  • If $n$ is prime, then $n$ must be equals $p$, because $n\mid \binom{n}{k}$. But, in this case, $n\mid\mid \binom{n}{k}$, so $k=1$. (This would work to prime powers too.)

  • If $n$ is composed, note that $\binom{n}{k} = p$ implies, a fortiori, that $p\mid \binom{n}{k}$ and consequently $p\leqslant n$. But under our conditions, $\binom{n}{k} > n$, contradiction. $\square$

Also, I've already saw in Proofs from THE BOOK the problem "Binomial coefficients are (almost) never powers", and although it is highly related, it doesn't provide much insight towards this problem (at least as far as I understood).


EDIT: Prime powers aren't binomiables too!

Let's state three results first:

  1. Lemma. Let $p$ a prime. If $p\mid n$ and $0<k<p$, then $p\mid \binom{n}{k}$.

    Proof. Let $n= pm$ and assume $0<k<p$. Consider the Vandermonde's identity:

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

    It follows that $\binom{pm}{k}\equiv \binom{p(m-1)}{k} \mod{p}$ (the term $j=0$ in the sum). Repeating it $m$ times, we conclude $\binom{pm}{k}\equiv \binom{p}{k} \mod{p}$, and from $p\mid \binom{p}{k}$ follows our statement. $\square$

  2. Bertrand's postulate. If $n\geqslant 2k$, then the binomial $\binom{n}{k}$ has a prime factor $q > k$.

  3. Theorem. [Erdös] The binomial $\binom{n}{k}$ is never a perfect power for $4\leqslant k\leqslant n-4$.

    (This is the paragraph I mentioned in Proofs from THE BOOK.)

So there is only two cases to analyse, $k=2$ and $k=3$. In both cases we can assume $n \geqslant 6$.

CLAIM 2. Prime powers aren't "binomiables".

Proof. Let $p$ a prime, $m>1$, and suppose $p^m = \binom{n}{k}$.

  • If $k=2$, then $p^m = \frac{n(n-1)}{2}$. By Bertrand's postulate, $p\neq 2$. Now observe that $\gcd(n, n-1) = 1$, so $$ p^m \mid n\quad \text{xor}\quad p^m\mid n-1. $$ Then: $$2 =\frac{n(n-1)}{p^m} \geqslant n-1 \implies n \leqslant 3,$$ that contradicts $n\geqslant 6$.

  • If $k=3$, then $p^m = \frac{n(n-1)(n-2)}{6}$. Bertrand's postulate allows us to take $p\neq 2,3$. Hence, similarly to the previous case, we can deduce: $$p^m \mid n \quad \text{xor}\quad p^m\mid n-1 \quad \text{xor} \quad p^m\mid n-2.$$ But then: $$ 6 = \frac{n(n-1)(n-2)}{p^m} \geqslant (n-1)(n-2) \implies n \leqslant 4,$$ a contradiction. $\square$


EDIT 2: I've just realized that I didn't use the Lemma at all. Anyway, I think I'll let it here, it may be useful someday hahaha

$\endgroup$
  • 1
    $\begingroup$ Perhaps you could draw up a Pascal's triangle, see what numbers do and don't appear, and see if you find a pattern? $\endgroup$ – Akiva Weinberger Jul 13 '15 at 16:17
  • 4
    $\begingroup$ A list of these numbers is at oeis.org/A006987 - there doesn't seem to be much there. In particular, if there were a nice criterion I'd expect it to be listed there. But it's a fun problem - keep playing around with it! $\endgroup$ – Michael Lugo Jul 13 '15 at 16:29
  • 2
    $\begingroup$ Perhaps a clearer condition would be $\binom nk>n$. $\endgroup$ – ajotatxe Jul 13 '15 at 16:46
3
$\begingroup$

Here is a partial answer for a special case: if $\sqrt{8n+1}$ is an odd integer, then $n$ is a binomial coefficient of the form $n \choose 2$. Such a formula is possible because $n \choose 2$ is quadratic in $n$ and therefore has a straightforward solution.

$\endgroup$
2
$\begingroup$

I don't think theres a single simple criterion, but one could construct an algorithm for determining it with time complexity of $O((\ln c)^2)$ binomial coefficients or $O((\ln c)^3)$ multiplicaitons. Besides it may be unknown or hard to determine totally certainly whether the number is actually prime or not.

What we can use is to estimate the coefficients:

$$\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!}$$

We also can estimate it from below:

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

So given $k$ we have an estimate for $n$

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

Also since we only have to consider $2k<n$ we can use the estimate:

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

So we don't have to consider $k$ with $(2k)!/(k!)^2 > c$ and since it's increasing we can terminate the algorithm once it happens.


Take for example the numbers $8008$ and $8009$ (the later being prime)

We have the ranges of $n$ depending on $k$ as:

$$\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}$$

That is we only have to consider $\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}$ and $\binom{15}{7}$. Calculating these reveals that $8008 = \binom{16}{6}$ and $8009$ is none of them.

The time complexity is due to stirlings formula for the termination condition:

$$\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)$$

So we have to consider $O(\ln(c))$ values of $k$ and for each of those $k/2$ values of $n$ making it $O((\ln(c))^2)$ binomial coefficients.

$\endgroup$
  • $\begingroup$ That's a really nice answer! I particularly liked how this algorithm sheds light over the structure of possible binomial representations. Thank you for your careful considerations :) $\endgroup$ – Alufat Jun 29 '17 at 13:04
1
$\begingroup$

Just some comment so far:


First case: we search cases where ${ a_j \choose 2 }=b_j^m$

By brute force I found the following very likely pattern, by which the sequences $a_j$ and $b_j^2$ can directly be generated. In all cases $m=2$, I had no case with $m \gt 2$ so far, except of course where $b_1 = 1$ - here the exponent $m$ can take any value.

  • The sequence of $a_j$ is
    $$ a_j = \{2,9,50,289,...\}_{j=1,2,3,...} $$ and has the iteration formula $$a_{j}\underset{j\ge3}=6a_{j-1}-a_{j-2}-2$$ The question of whether $a_j$ can be prime has at least for each second $a_j$ a simple answer by this formula: if $a_{j-2}$ is even, then also $a_j$. And since $a_1=2$ is even, all $a_j$ with odd $j$ are composite. It seems also that all $a_j$ at even index $j$ are squares, however I didn't try to derive an analogue conclusion for this from the recursion-formula so far. At least, under the assumption, that the partial sequence $c_{j}=a_{2j}=\{9,289,577,...\}$ has indeed only squares $c_j^2$ then we have a recursion $ c_j = 6c_{j-1} - c_{j-2} $ and this would also exclude $a_{2j}$ being prime.
  • The sequence $b_j$ is $$\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}$$


second case: we search cases where ${ a_j \choose 3 }=b_j^m$ where $m\ge2$

First examples by brute force ($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} $$

Interestingly, W|A didn't find the solutions except the trivial one where $b_j=0$

$\endgroup$
-1
$\begingroup$

I know they are composite.

To show this, suppose not, that is, $\binom mn=p$, a prime. Then $m\ge p$. Since we are excluding the trivial cases, $m\ge p+1$ and then

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

a contradiction.

But not every composite number is a non-trivial binomial coefficient. For example, $9$ is not.

$\endgroup$
  • 6
    $\begingroup$ I already remarked that primes aren't binomiables in the body of the question (in the big yellow box!). $\endgroup$ – Alufat Jul 14 '15 at 3:53

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.