No simple duplication formula for factorials?

Question

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) 2^2z-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!

Answer 1

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

Answer 2

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?

Answer 3

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.