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

  • $\begingroup$ This question looks like a question about an algorithm. I do not understand why you removed the [ds.algorithms] tag which Suresh had added. $\endgroup$ Nov 7, 2010 at 6:27
  • $\begingroup$ 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$. $\endgroup$
    – Turbo
    Nov 7, 2010 at 6:33
  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Nov 7, 2010 at 7:04
  • $\begingroup$ 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/…. $\endgroup$ Nov 7, 2010 at 7:14
  • $\begingroup$ That is why I felt an answer to the value of $\epsilon$ might be interesting. $\endgroup$
    – Turbo
    Nov 7, 2010 at 7:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.