MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Many special functions including the gamma function have a duplication formula of some sorts. In the case of the gamma function it reads:

Gamma(2z) = Gamma(z) Gamma(z+1/2) 22z-1/Gamma(1/2)

On the other hand, there is no algebraic relation between Gamma(2z) and Gamma(z) by themselves, meaning that is there is no nonzero polynomial f(x,y) such that f(Gamma(2z),Gamma(z))=0 for all complex z. I can prove this by chasing poles and their order.

However, I'd be interested in a (simple) argument which shows that the following similar statement is true (which I believe it is):

There is no (nonzero) polynomial f(x,y) such that f((2n)!, n!)=0 for all integers n≥0.

Any ideas? Thank you!

share|cite|improve this question
up vote 10 down vote accepted

It's equivalent to show that there is no polynomial relationship f({2n choose n}, n!) = 0. On the other hand, we know that {2n choose n} ~ 4^n/sqrt{n} asymptotically and n! grows much faster.

Terence Tao once remarked that if a sufficiently simple duplication formula were known for the factorial then Wilson's theorem would give an efficient primality test. (Edit: see the other answer. I may be misremembering the stronger remarks that Dick Lipton made.)

share|cite|improve this answer
I don't think that was me; this is the first I've heard of that observation (though it is neat...) – Terry Tao Nov 4 '09 at 6:07
Very nifty! Thanks! – Armin Straub Nov 4 '09 at 17:06


Let me try to solve your original problem differently. First write the wanted polynomial in the form $f(x,y)=\sum_kx^kA_k(y)$ where the leading polynomial $A_0(y)$ is not identically zero (otherwise we can always replace $f(x,y)$ by $f(x,y)/x^\ell$ for a suitable $\ell$). Denote by $N$ the degree of the polynomial $A_0(y)$. For any prime $p>N!$ the numbers $0$ and $(-1)^kk!$, where $k=0,\dots,N-1$, are distinct residues modulo $p$, so that $p!\equiv 0\pmod p$ and $(p-k)!=(p-1)!/\prod_{j=1}^{k-1}(p-j)\equiv(-1)^k(k-1)!^{-1}\pmod p$ are pairwise noncongruent modulo $p$ as well. Substituting $x=(2p-2k)!\equiv0\pmod p$ and $y=(p-k)!$ for each $k=0,1,\dots,N$ into $f(x,y)=0$ and reducing modulo $p$, we obtain $N+1$ different solutions of the polynomial equation $A_0(x)\equiv0\pmod p$, so that all coefficients of $A_0(x)$ are divisible by $p$. Since this is true for any prime $p>N!$, the polynomial $A_0(x)$ is identically zero, which contradicts our assumption.

Is it elementary enough?

share|cite|improve this answer
Not just elementary but slick and elegant. Thank you, Wadim! – Armin Straub Jul 4 '11 at 21:00

I don't know how to answer your question, but here is something related that you will find interesting. Dick Lipton has a post about how a duplication formula that directly related Γ(2z) with Γ(z) would lead to an efficient classical algorithm for factoring. If I remember correctly, he also speculates about potential approaches to showing that such formulae can't exist.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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