Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers 3

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|improve this answer
2  
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
add comment

Armin,

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|improve this answer
    
Not just elementary but slick and elegant. Thank you, Wadim! –  Armin Straub Jul 4 '11 at 21:00
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.