# A question on factorials

$P(x) = n!$ where $P(x) \in \mathbb Z[x]$ has finitely many $(x,n) \in \mathbb Z^{2}$ assuming $abc$ conjecture.

Consider the following variant: Given $c,d,r,s,k \in \mathbb Z$ and $P(x) = n!$ where $P(x) \in \mathbb Z[x]$ with coefficients of $P(x)$ ~ $O(k^{c})$ and degree($P(x)$) ~ $O(\log^{d} {k})$, is there $(x,n) \in \mathbb Z^{2} :x$ ~ $O(\log^{r} {k})$ and $n$ ~ $O(k^{s})$?

What fraction $\epsilon$ of $n \in \mathbb Z$ would have nice relations like that? Is it something harder than what the $abc$ conjecture (whose proof is not known) could give?

It seems if $\epsilon > 0$ is fixed, then one might be able compute the factorial for most $n'$ quickly as it guarantees an $n$ close enough to $n'$ whose factorial can be found using the diophantine relation (provided one is able to find an appropriate $P(x)$ and its solution quickly) and another constant number of multiplies should suffice to get $n'!$ since $\epsilon > 0$ is fixed.

• This question looks like a question about an algorithm. I do not understand why you removed the [ds.algorithms] tag which Suresh had added. Nov 7, 2010 at 6:27
• No, I don't think so. It only asks for whether $\epsilon > 0$ and is independent of $k$. If not such nice relationships don't exist. My guess is $\epsilon$ will depend on $k$ and will converge to $0$ as $k$ increases. Or else even though $P(x)$ and $x$ are unknown, it would suggest the existence of a quick but unknown way to compute $n!$ for almost all $n \in \mathbb Z$. Nov 7, 2010 at 6:33
• I felt the last paragraph made my intent clear. I just felt $n!$ could be calculated quickly using a polynomial evaluation. Typically computing $n!$ is hard. Am I correct? Nov 7, 2010 at 7:04
• Computing n! is not known to be easy in the following sense: it is not known, given n and i in binary, whether the i-th bit (counting from the least significant bit) of n! is polynomial-time computable. See also cstheory.stackexchange.com/questions/2204/…. Nov 7, 2010 at 7:14
• That is why I felt an answer to the value of $\epsilon$ might be interesting. Nov 7, 2010 at 7:16