# Integer-valued factorial ratios

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".

-
Wadim, why did you omit L'vovich? – Victor Protsak May 29 '10 at 7:52
Victor, we are so democratic nowadays... BTW, my son is Victor Wadimovich. :) – Wadim Zudilin May 29 '10 at 8:03
Just to add some more on the list: artofproblemsolving.com/Forum/viewtopic.php?t=160695 (scroll down to posts #3 and #4) and $\frac{\left(na_1\right)!\left(na_2\right)!...\left(na_n\right)!}{a_1!a_2!...a_n‌​!\cdot\left(a_1+a_2\right)^{\left(n-1\right)/2}\left(a_2+a_3\right)^{\left(n-1\ri‌​ght)/2}...\left(a_n+a_1\right)^{\left(n-1\right)/2}}\in\mathbb Z$ for any $n\in\mathbb N$ and $a_1,a_2,...,a_n\in\mathbb N$. – darij grinberg May 31 '10 at 18:07
Very nice, Darji, thanks! I just checked that the first one (from the forum) is perfectly treatable by the arithmetic argument ($p$-order of factorials). – Wadim Zudilin May 31 '10 at 21:53
So is the second. The interesting question is how to solve those without. – darij grinberg Jun 1 '10 at 10:57

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.

-
MO welcoming +1, Aaron! Yes, the 2-parametric families possess (many!) recurrences, and this is why they are "easy". There are arithmetic-algebraic obstacles for the 1-parametric families to extend to 2-parametric ones of the the same "factorial ratio" form (this can be rigorously shown!). My intuition says that the desired 2-parametric families $f(n,m)$, say, have the form $\sum_kg(n,m,k)$ of a hypergeometric sum, so that $f(n,n)$ (or some other specializations to 1 variable) has a closed "factorial ratio" form. I simply have no idea on how to construct such $f$; I've never seen them around. – Wadim Zudilin Jul 29 '10 at 8:17
I agree that 2-parametric families of that "factorial ratio" form are unlikely to be sitting around undiscovered (as noted in my closing sentence). But what about embedding in a 2-parameter family possessing a recurrence like g(i+1,j+1)=ug(i,j+1)+vg(i,j)+wg(i+1,j). Still seems like a long shot. In the example g(n)=f(n,3n) I gave, how would one start from g(n) and somehow deduce a 2-parameter recurrence? Are there other ones in which it nicely embeds? – Aaron Meyerowitz Jul 29 '10 at 13:18
You wish me answer the questions I ask myself! :-) Unless one finds at least one nontrivial example of lifting from 1- to 2-parametric families, we can only try to guess the structure. The recurrence relation you write strongly resembles the WZ-pair relation, at least some "brain food" for me. Thanks! – Wadim Zudilin Jul 29 '10 at 14:19
Right. We do know that example with a lift to a family given by a recurrence. Can we "discover" the recurrence? I was curious about the "many!" recurrences you mention. I can find that one and a similar one for the other family, but only those. What form do you mean? – Aaron Meyerowitz Jul 29 '10 at 16:49
Many (in fact, three) recurrences, which are sufficient for proving the integrality of $(2n)!(2m)!/n!(n+m)!m!$, are given in Gessel's paper (see the free weblink in the question). – Wadim Zudilin Jul 29 '10 at 23:51

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

http://mathforum.org/kb/message.jspa?messageID=5435773

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):

http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0310&L=nmbrthry&T=0&F=&S=&P=1513

-
Thanks, Timothy, for the references which I'll follow. I am definitely not interested in combinatorial interpretations (yes, this is too much to ask!), and as I indicate in my question the 2-parametric families can be shown to be integer valued (so that there is a hope to get something for 1-parametric families as well). – Wadim Zudilin May 30 '10 at 5:07
+1 for the references and convincing me on the fact that the problem is on the market for quite a period. Dick's Problem 6514 most probably can be solved by Ira Gessel's approach (I mention in the question), although the ratio $(3m+3n)!(3n)!(2m)!(2n)!/(2m+3n)!(m+2n)!(m+n)!m!n!n!$ is better split into two integer-valued ratios (I have to think more about this). Jam's response is not close enough to the problem. I'll check Fibonacci Q. I am aware of other work on this problem but not of other methods of showing the desired integrality. :( – Wadim Zudilin May 30 '10 at 5:44
Timothy, I read your Dec 2006 question carefully once again, and even I understand your motivation quite well, it is a different question! First, you don't have the factorial ratios I mention in mind (except for the one from Dick's problem). Secondly, you wish to have an expression by means of "obviously integers", like binomials. This does not work even for the non-binomial 2-parametric families, an extra induction is required. Final remark: the $p$-order argument is originally due to Chebyshev(!), not Gregg Patruno, and is given in Polya-Szego's "Problems and theorems in analysis". – Wadim Zudilin May 30 '10 at 11:33
Wadim, you're right; as I said, I asked a "similar" question and not "the same" question, but I thought the pointers might be of use to you anyway. And certainly I did not mean to attribute the $p$-order argument to Gregg Patruno; indeed, Patruno complained that the method was absolutely ancient and that the Monthly should stop posing problems of this sort. It was just the first place I happened to encounter it. – Timothy Chow May 31 '10 at 0:03
Timothy, once again: Thank you very much for your response! I think that it's veryhelpful for my (and maybe somebody else) understanding of what is going on here. – Wadim Zudilin May 31 '10 at 0:12

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

-
Welcome again, Aaron! That's a very good point, to interpret these factorial ratios as CTs... To my best knowledge there are no such things known for the 1-parametric families, but I might be wrong. +1 again and many thanks. – Wadim Zudilin Jul 30 '10 at 6:24
I also don't know of any, and CT identities are not my area of expertise. On the other hand there are now known to be 3 2-parameter families and a 29 sporadic one parameter families (an! bn!)/(cn! dn! en!) there are a handful more sporadic families with 3 on the top 4 on the bottom and maybe 4 on top 5 on the bottom. SO it would not be totally amazing if root systems came in somehow. – Aaron Meyerowitz Jul 30 '10 at 17:22
With your very explicit idea in mind, I should ask Doron directly (he appeared on MO only once). I am not an expert on CT evaluations, although I know a huge database of some work in this direction, related to Calabi-Yau differential equations. – Wadim Zudilin Jul 30 '10 at 23:38

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.

-
Hmmm, this is hardly an answer but probably expression of interest. I am curious enough whether an injective homomorphism $S_n\times S_m\times S_{n+m}\to S_{2n}\times S_{2m}$ is known... I doubt. – Wadim Zudilin May 29 '10 at 10:12
Pietro: This is impossible even for $n=1$: Assume such $\phi$ exists. The image of a 5-cycle from $S_6$ is either a 5-cycle or a product of two disjoint 5-cycles in $S_{12}.$ In the latter case, its centralizer doesn't contain elements of order 3. In the former case, the centralizer is $S_7\times C_5,$ which contains a unique $S_3\times S_4$ subgroup modulo conjugation. But its centralizer in $S_{12}$ is $S_5$ , which cannot contain $\phi_(S_6)$. (There may be an even easier proof, but using a 3-cycle, a 4-cycle, and a 6-cycle doesn't seem to immediately lead to a contradiction) – Victor Protsak May 29 '10 at 21:42
good point. and semidirect products? anyway, that was just a hint, (I'm not a group theorist) – Pietro Majer May 30 '10 at 0:30
Semidirect products don't help. For $n \neq 6$, every automorphism of $S_n$ is inner. So every semidirect product $G \ltimes S_n$ is isomorphic to $G \times S_n$. – David Speyer Jul 29 '10 at 11:11
wow, thank you, very good! – Pietro Majer Jul 29 '10 at 11:57