# Given a positive integer $t$ does there always exist a natural number $k$ such that $(k!)^2$ is a factor of $(2k-t)!$?

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), 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.

• 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... Jul 9, 2020 at 13:02
• @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$. Jul 10, 2020 at 14:10
• This question was created to get more material for the Pearl Dive. Jul 11, 2020 at 12:56
• @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)$ Jul 14, 2020 at 11:17
• 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).
– Sil
Jul 16, 2020 at 11:32

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.