45
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Wadim, why did you omit L'vovich? $\endgroup$ May 29, 2010 at 7:52
  • $\begingroup$ Victor, we are so democratic nowadays... BTW, my son is Victor Wadimovich. :) $\endgroup$ May 29, 2010 at 8:03
  • 1
    $\begingroup$ 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\right)/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$. $\endgroup$ May 31, 2010 at 18:07
  • $\begingroup$ 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). $\endgroup$ May 31, 2010 at 21:53
  • 1
    $\begingroup$ Here is a more recent paper of Soundararajan addressing integer factorial ratios: arxiv.org/abs/1906.06413 $\endgroup$
    – yoyo
    Sep 19, 2020 at 16:21

5 Answers 5

16
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jul 29, 2010 at 8:17
  • $\begingroup$ 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? $\endgroup$ Jul 29, 2010 at 13:18
  • $\begingroup$ 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! $\endgroup$ Jul 29, 2010 at 14:19
  • $\begingroup$ 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? $\endgroup$ Jul 29, 2010 at 16:49
  • $\begingroup$ 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). $\endgroup$ Jul 29, 2010 at 23:51
14
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 30, 2010 at 6:24
  • $\begingroup$ 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. $\endgroup$ Jul 30, 2010 at 17:22
  • $\begingroup$ 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. $\endgroup$ Jul 30, 2010 at 23:38
  • 1
    $\begingroup$ Incidentally, $(2m)!\,(2n)!/m!\,n!\,(m+n)!$ is the constant term in $(1+x)^m(1+1/x)^m(1-x)^n(1-1/x)^n$. $\endgroup$
    – Ira Gessel
    Oct 15, 2021 at 22:31
  • $\begingroup$ So the $-1^n$ times the coefficient of $m^{m+n}$ in both $(x+1)^{2m}(x-1)^{2n}$ and $(1-4x)^{n-1/2}$. $\endgroup$ Oct 17, 2021 at 2:49
6
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$ May 30, 2010 at 5:07
  • $\begingroup$ +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. :( $\endgroup$ May 30, 2010 at 5:44
  • $\begingroup$ 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". $\endgroup$ May 30, 2010 at 11:33
  • 1
    $\begingroup$ 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. $\endgroup$ May 31, 2010 at 0:03
  • $\begingroup$ 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. $\endgroup$ May 31, 2010 at 0:12
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ May 29, 2010 at 10:12
  • 10
    $\begingroup$ 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) $\endgroup$ May 29, 2010 at 21:42
  • $\begingroup$ good point. and semidirect products? anyway, that was just a hint, (I'm not a group theorist) $\endgroup$ May 30, 2010 at 0:30
  • 8
    $\begingroup$ 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$. $\endgroup$ Jul 29, 2010 at 11:11
  • $\begingroup$ Pietro, this was nevertheless a very "olympic" approach. Are there other "combinatorial" interpretations of the binomials rather than the order of symmetric group? As for your "Wait! Is yours an elementary question/homework? then this is not the right place; try one of these instead (links follow)", there was recently a discussion on Meta of similar flavour, but it went nowhere... $\endgroup$ Jul 29, 2010 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.