# No simple duplication formula for factorials?

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!

-

## 3 Answers

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

-
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

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?

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9347054362297058, "perplexity": 279.0924293826586}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-32/segments/1438042989126.22/warc/CC-MAIN-20150728002309-00221-ip-10-236-191-2.ec2.internal.warc.gz"}