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

<p>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})$?</p>

<p>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?</p>

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

CC BY-SA 2.5
2010-11-07T06:27:45.057Z
This question looks like a question about an algorithm. I do not understand why you removed the [ds.algorithms] tag which Suresh had added.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-07T06:33:49.573Z
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$.
Turbo
CC BY-SA 2.5
2010-11-07T07:04:45.713Z
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?
Turbo
CC BY-SA 2.5
2010-11-07T07:14:59.040Z
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 http://cstheory.stackexchange.com/questions/2204/efficiently-getting-bits-of-n.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-07T07:16:19.537Z
That is why I felt an answer to the value of $\epsilon$ might be interesting.
Turbo
CC BY-SA 2.5
2010-11-07T07:17:26.853Z
I wanted to get a feedback on complexity theory people before posting on mathoverflow.
Turbo
<nt.number-theory>
A question on factorials
Turbo
# A question on factorials

(Asked by: username_0 on 2010-11-07)

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

**Tags:** nt.number-theory

> **Comments:**
> **username_1**: This question looks like a question about an algorithm. I do not understand why you removed the [ds.algorithms] tag which Suresh had added.  
> **username_0**: 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$.  
> **username_0**: 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?  
> **username_1**: 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 http://cstheory.stackexchange.com/questions/2204/efficiently-getting-bits-of-n.  
> **username_0**: That is why I felt an answer to the value of $\epsilon$ might be interesting.  
> **username_0**: I wanted to get a feedback on complexity theory people before posting on mathoverflow.  

---

## 0 answers

