Integer-valued factorial ratios

Question

This historical question recalls Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation Chebyshev used the factorial ratio sequence $$ u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)!}, \qquad n=0,1,2,\dots, $$ which assumes integer values only. The latter fact can be established with the help of $$ \operatorname{ord}_p n! =\biggl\lfloor\frac{n}{p}\biggr\rfloor+\biggl\lfloor\frac{n}{p^2}\biggr\rfloor +\biggl\lfloor\frac{n}{p^3}\biggr\rfloor+\dots $$ and routine verification of $$ \lfloor 30x\rfloor+\lfloor x\rfloor-\lfloor 15x\rfloor-\lfloor 10x\rfloor-\lfloor 6x\rfloor\ge0. $$ Other Chebyshev-like examples of integer-valued factorial sequences are known; the complete list of such $$ u_n=\frac{(a_1n)!\dots(a_rn)!}{(b_1n)!\dots(b_sn)!} $$ in the case $s=r+1$ was recently tabulated in [J.W. Bober, J. London Math. Soc. (2) 79 (2009) 422--444]. A motivation for this classification problem is in relation with a certain approach to Riemann's hypothesis, but I would prefer to refer everybody interested in to Bober's paper (which could be found in the arXiv as well). The proofs of $u_n\in\mathbb Z$ make use of the above formula for $\operatorname{ord}_p n!$

There are three 2-parameter families in Bober's list, namely, $$ \frac{(n+m)!}{n!m!}, \qquad \frac{(2n)!(2m)!}{n!(n+m)!m!}, \qquad\text{and}\qquad \frac{(2n)!m!}{n!(2m)!(n-m)!} \quad (n>m); $$ the first one includes the binomial coefficients, while some properties of the second family are mentioned in this question. For the binomial family, a standard way to establish integrality purely combinatorially amounts to interpreting the factorial ratio as coefficients in the expansion $$ (1+t)^{n+m}=\sum_{k=0}^{n+m}\binom{n+m}{k} t^k, $$ that is, as the number of $m$-element subsets of an $(n+m)$-set. There is lack of similar interpretation for the other two 2-parametric families, although Ira Gessel indicates in [J. Symbolic Computation 14 (1992) 179--194] that the inductive argument together with identity $$ \frac{(2n)!(2(n+p))!}{n!(n+(n+p))!(n+p)!} =\sum_{k=0}^{\lfloor p/2\rfloor}2^{p-2k} \binom{p}{2k} \frac{(2n)!(2k)!}{n!(n+k)!k!} \qquad (p\geq 0) $$ allows one to show that the numbers in question are indeed integers. A slight modification of the formula can be used for showing that the third 2-parametric family is integer valued. In these cases one uses a reduction to binomial sums for which the integrality is already known. But what about the 1-parametric families, like Chebyshev's or, say, $$ \frac{(12n)!n!}{(6n)!(4n)!(3n)!}? $$ Is there any way to establish the integrality without referring to the $p$-order formula?

My own motivation is explained in the joint recent preprint with Ole Warnaar, where we observe a $q$-version of the integrality in a "stronger form".

Answer 1

Along with the binomial coefficients, the other two infinite families each enjoy a fairly simple recurrence. for example $$f(n,m)=\frac{(2n)!(2m)!}{n!(n+m)!m!}.$$ has $f(0,t)=\binom{2t}{t}$ and $f(i+1,j)=4f(i,j)-f(i,j+1).$

Consider the one parameter family $$\frac{(2n)!(6n)!}{n!(4n)!(3n)!}.$$ Viewed in isolation it seems hard to establish integrality without referring to the p-order formula. However as the case m=3n of the family $f(n,m)$ it is the values in a line of cells with slope 3.

I've wondered if any of the various "sporadic" one parameter families can be embedded in a similar manner in a 2 parameter family defined by a recurrence. Evidently the entire table would not all be given by a formula exactly of that form.

Answer 2

The p-order method got a lot of attention in the solution of Askey's 1986 problem 6514 in the Math Monthly to show that $$\frac{(3m + 3n)!(3n)!(2m)!(2n)!}{(2m + 3n) !(m + 2n) !(m + n)!m!n!n!}$$ is always an integer.

It had been conjectured that this is the constant term of $$\left( \prod{(1-u/v)} \right)^m \left( \prod{(1-uv/w)} \right)^n$$ where each product is over the 6 ways to set the variables to x,y and z (and hence is an integer). This was established in: A Proof of the $G_2 $ Case of Macdonald's Root System-Dyson Conjecture by Doron Zeilberger, SIAM J. Math. Anal. 18, 880 (1987), DOI:10.1137/0518065 . So this is certainly not a p-order proof. However I don't know that there are constant term identities for these other ratios. The article does cite (a special case of) a theorem of Morris showing that the following expression is a constant term and hence an integer:
$$\frac{(a+b+2c)!(a+b+c)!(a+b)!(2c)!(3c)!}{(a+2c)!(b+2c)!(a+c)!(b+c)!a!b!c!c!} $$

Answer 3

Although this isn't an answer to the question, it's worth pointing out that the second and third families are essentially binomial coefficients.

We have $$U_2(m,n):=\frac{(2m)!\,(2n)!}{m!\, n!\, (m+n)!} = (-1)^m 2^{2m+2n}\binom{n-\frac12}{m+n}$$ and $$U_3(m,n):=\frac{(2n)!\,m!}{n!\,(2m)!\,(n-m)!}=(-1)^{n-m}2^{2n-2m}\binom{-m-\frac12}{n-m}.$$ It follows that $U_2(m,n)$ is $(-1)^n$ times the coefficient of $x^{m+n}$ in $(1-4x)^{n-1/2}$ and $U_3(m,n)$ is the coefficient of $x^{n-m}$ in $(1-4x)^{-m-1/2}$. Thus these numbers are integers since they are coefficients of (odd) integer powers of $(1-4x)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n} x^n$. (And in a sense they are really just one family.) It also follows that there is a simple combinatorial interpretation for $U_3(m,n)$ since it is a coefficient of a positive integer power of $(1-4x)^{-1/2}$, but we don't get an interpretation for $U_2(m,n)$ since there is cancellation in expanding positive powers of $(1-4x)^{1/2}$

Answer 4

I asked a similar question on sci.math.research in December 2006.

I mentioned Gregg Patruno's solution (Amer. Math. Monthly 94 (1987), 1012-1014) to Dick Askey's Problem 6514 in the American Mathematical Monthly, which uses what you call the $p$-order formula, and then I asked if there were any way to prove such facts by expressing the formula of interest in terms of quantities that are "obviously" integers (e.g., binomial coefficients). William Shanley pointed out that if one asks for a stronger result, namely a combinatorial interpretation of any such ratio of factorials, then this is probably too much to ask for. He mentioned Gessel and Xin's paper "A combinatorial interpretation of the numbers $6(2n)!/n!(n+2)!$" (J. Integer Seq. 8 (2005), Article 05.2.3), which uses considerable ingenuity to give a natural combinatorial interpretation in one specific case. However, establishing integrality is weaker than finding a natural combinatorial interpretation.

But as far as I know, your question is still open. In response to my sci.math.research article, Valery Liskovets sent me email with two references giving partial results. The first is David Callan's paper "Certificates of integrality for linear binomials" (Fibonacci Q. 38 (2000), 317-325) and the second is an article by Jam Germain from the NMBRTHRY Archive (18 Oct 2003).

Answer 5

I'd like to see a combinatorial/group theoretic proof. For instance, if one could exhibit an injective homomorphism of direct (or just semidirect) products of symmetric groups:

$\phi:S_{3n} \times S_{4n} \times S_{6n} \to S_{n}\times S_{12n},$

then the index of Im($\phi$) would be that ratio. This is just a vague hint.