32
$\begingroup$

For all natural numbers $k$ the ratio $$ \frac{(2k)!}{(k!)^2}=\binom{2k}k $$ is an integer. From staring at the Pascal triangle long and hard, we know that these ratios grow rather quickly as $k$ increases. It is therefore natural to think that may be some factors from the numerator can be dropped in such a way that the ratio would still be an integer. More specifically, can we, for some carefully chosen $k$, leave out a chosen number of largest factors. In other words, given an integer $t>0$ does there exist a natural number $k$ such that $$\frac{(2k-t)!}{(k!)^2}\in\Bbb{Z}?$$


My curiosity about this comes from a question we had in May. The asker there had found the smallest $k$ that works for each of $t=1,2,\ldots,8$. In that question it was settled that with $t=9$ the smallest $k$ that works is $k=252970$.


It is natural to think about such divisibility questions one prime factor $p$ at a time. It is well known that if we write a natural number $m$ in base $p$, $$m=\sum_{i=0}^\ell m_ip^i$$ with the digits $m_i\in\{0,1,\ldots,p-1\}$, then the highest power of $p$ that divides $m!$ is equal to $$ \nu_p(m!)=\frac1{p-1}\left(m-\sigma_p(m)\right), $$ where $$\sigma_p(m)=\sum_{i=0}^\ell m_i$$ is the sum of "digits" of $m$ in base $p$. Written in this way, my question asks for a given $t$, whether there exists a $k$ such that the inequality $$ (2k-t)-\sigma_p(2k-t)\ge 2k-2\sigma_p(k) $$ holds for all primes $p\le k$.


As we have that slack one might expect this to be possible. But I'm not sure. One obstruction comes from primes just below $k$. If $k-(t/2)<p<k$, then $p^2$ is a factor in the denominator, but $2p$ is too large to appear as factor in the numerator, so $p^2\nmid (2k-t)!$. Occasionally a small prime is also problematic. It is not clear to me how to approach this. A construction may exist. The only thing this reminds me of is the elementary exercise $(k!)^{k+1}\mid (k^2)!$, but that doesn't seem to apply here.


In a comment under the answer to the linked question user metamorphy reports having confirmed this up to $t\le14$.


Edit/Note: The available evidence (see also Sil's comment under this question) suggests that, at least when looking for the smallest $k$ that works for a given $t$, whenever a chosen $k$ works for an odd number $t$, that same $k$ also works for $t+1$. If the main question proves to be too difficult to crack, steps towards explaining this phenomenon are also interesting.

$\endgroup$
  • 3
    $\begingroup$ In your second to last paragraph, "primes just below $k$" can be accounted for by simply choosing a large prime gap and setting $k$ at the end of it... $\endgroup$ – abiessu Jul 9 at 13:02
  • 3
    $\begingroup$ @RossMillikan The other question doesn't show the existence of a valid $k$ for all $t$, only a faster way of computing the minimal valid $k$. $\endgroup$ – Varun Vejalla Jul 10 at 14:10
  • 2
    $\begingroup$ This question was created to get more material for the Pearl Dive. $\endgroup$ – Jyrki Lahtonen Jul 11 at 12:56
  • 3
    $\begingroup$ @JoshuaP.Swanson I also had association with Catalan numbers. However the main difference is that each Catalan number is integer, but here we need to show that there exists $k$ such that $\binom{2k}{k}$ is divisible by $(2k)\cdot(2k - 1)\cdots(2k - t + 1)$ $\endgroup$ – Smylic Jul 14 at 11:17
  • 3
    $\begingroup$ As for the further verification, $k=159329615$ works for $t \leq 16$ and $k=2935782898$ works for $t \leq 18$. Next $k$ must be greater than $15980000001$ per my calculations. Though this does not help much in revealing generic pattern, except that all these $k$ have very few and distinct prime divisors (i guess there is some probabilistic reason for that). $\endgroup$ – Sil Jul 16 at 11:32
1
$\begingroup$

Note: this is not a complete solution, rather it is an approach that may provide insight or be workable into a solution.

Using the terms in the question, let $t\ge 1$ be given and consider $\frac{(2k-t)!}{(k!)^2}$. If we take $q=(t+1)\#+1+t$ then each of the numbers $q-t+1,q-t+2,\dots, q$ has a factor in common with $q-t-1$. If $2k\equiv q+\{0,1\}\mod (t+1)\#$ and $2k\ge q$ then there will be no primes $p\in [2k-t+1, 2k]$ and therefore if $p\mid k!$ then $p^2\mid (2k-t)!$. (Note that odd $q$ means $2k\equiv q+1\mod (t+1)\#$ and $(q+1, (t+1)\#)\gt 2$.) Moving forward, assume that $2k\equiv_{(t+1)\#}t+1+(t\mod 2)$.

Next consider a factor $p^r\mid k!$ such that $p^{2r}\nmid (2k-t)!$, which means that $p^u\mid x,x\in[2k-t+1,2k]$. Begin with $u=2$. If $p^2\ge t$ then we must move $p^2$ into the given arrangement also, which can be accomplished by $p^2\equiv 2k-q-[1,t]\mod (t+1)\#$. This same process can be applied for each $p^u > t$. More specifically, let $u_p=\lfloor\log_p t\rfloor +1$, then $p^{u_p} > t$ for each given $p$ and the specified modulus would be along the lines $$q=t+1+\prod_{p\le t}p^{\lfloor\log_p t\rfloor+1}$$ with $2k\ge q+\{0,1\}$. This value can probably be simplified as $2k\ge t!+t+\{1,2\}$.

In order to use this further it might be provable that each prime increases its total factor count of $\binom{2n}n$ as $n$ increases, or as $n$ increases in some patterned manner, so that a bound can be determined. Specifically, it is clear in the patterns that for $p=2$ the quantity $\binom{2^n-2}{2^{n-1}-1}$ has $n-1$ factors of $2$, while for $p>2$ the quantity $\binom{p^n+1}{\frac{p^n+1}2}$ has $n-1$ factors of $p$. There are specific repeating patterns of each prime up to each of these particular boundaries, but I have not been able to tame them as yet. However, the patterns appear to present a form of "modular arithmetic" which seems to have potential for leveraging into a value for $2k$ for a given value of $t$, e.g., every $3$rd $n$ in $\binom{2n}n$ or every $5$th, etc.

| cite | improve this answer | |
$\endgroup$

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.