<p>Let $P(x) \in \mathbb Z[x]$ of degree $\ge 2$ and $S = \{(x,n) \in \mathbb Z^{2}:P(x)=n!\}$. It is known:</p>

<p>$(a)$ $|S| &lt; \infty$ under the $abc$ conjecture.</p>

<p>$(b)$ Density of $S$ in $\mathbb Z$ is $0$ unconditionally.</p>

<p>Fix $k \in  \mathbb Z$. Let:</p>

<p>$(1)$ $P[k] = \{P(x) = \displaystyle \sum_{i=0}^{t}p_{i}x^{i} \in \mathbb Z[x]$: $p_{i}$ ~ $O(k^{c})$ $\forall i$, $t$ ~ $O(\log^{d} {k})$ for some $c,d \in  \mathbb Z\}$ (Set of all polynomials of controlled degree and coefficient size w.r.t $k$)</p>

<p>$(2)$ $R[k] = \{(x,n) \in \mathbb Z^{2}: x$ ~ $O(\log^{r} {k}), n$ ~ $O(k^{s})$ for some $r,s \in  \mathbb Z\}$ (Set of all pairs of integer points of prescribed size w.r.t $k$)</p>

<p>$(3)$ $S(k,P(x)) = \{(x,n) \in R[k] : P(x) = n!\}$ (Set of pairs of points of controlled size w.r.t $k$ satisfying a given equation)</p>

<p>$(4)$ $S(k) = \{S(k,P(x)):P(x) \in P[k]\}$ (set of pairs of points of controlled size w.r.t $k$ satisfying $P(x)=n!$ where $P(x)$ is of controlled size w.r.t $k$)</p>

<p>$(5)$ $S = \{S(k):k \in \mathbb Z\}$. (Set of $S(k)$)</p>

<p>$(6)$ $N = \{n \in \mathbb Z: \exists (x,n) \in S\}$. (Set of all integers which has a pair point $x$ so that $(x,n)$ form a controlled size pair solution to $P(x)=n!$ where $P(x)$ is of controlled size for some value of $k$) </p>

<p>$(7)$ $\epsilon$ = density of $N$ in $\mathbb Z$.</p>

<p><strong>Conjecture:</strong> $\epsilon = 0$.</p>

<p>$\epsilon > 0$ implies for most $m \in \mathbb Z$, $\exists n$ close to $m$ such that $n!$ can be efficiently found since a reasonable size $k$ and $P(x)$ exists to compute $n!$. So $m!$ can be found using a constant number of multiplies given $n!$. </p>

<p>Though $\epsilon > 0$ implies $m!$ has an efficient algorithm for most $m \in \mathbb Z$ since $\exists n \in N$ close to the given $m$, it does not mean the algorithm is known since none of $n$, $k$, $P(x)$ and $x$ are explicit.</p>

<p>Are my arguments correct?</p>

CC BY-SA 2.5
2010-11-09T04:56:52.957Z
Um... Can you write that again in English, please?
Jeffε
CC BY-SA 2.5
2010-11-09T05:11:45.360Z
Funny comment Dr. Jeff. I will do it so:)
Turbo
CC BY-SA 2.5
2010-11-10T16:19:16.943Z
Now crossposted to MathOverflow: http://mathoverflow.net/questions/45523/a-question-on-factorials.  Please add links in both directions when you crosspost.  See http://meta.cstheory.stackexchange.com/questions/65/repeat-a-question-from-math-overflow/618#618 for details.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-10T16:45:13.577Z
Do you want me to take the other one down?
Turbo
CC BY-SA 2.5
2010-11-10T19:37:45.793Z
I think one of the comments in the earlier version was if I could get any opinion before posting this on the other site. So far I did not get any. That is why I posted.
Turbo
CC BY-SA 2.5
2010-11-10T22:40:53.240Z
I had already stated my opinion on crossposting in the link I provided in the previous comment, so please read it.  Just to be perfectly clear, here are my points: (1) You should always provide links in both directions when crossposting a question.  (2) You should wait for a reasonable amount of time before crossposting a question, and I think this reasonable amount of time is one week.  As for (2), I can imagine that some people probably think that 3 days is enough, so (2) is not my main point here.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-07T20:38:45.470Z
Why did you delete the [older question](http://cstheory.stackexchange.com/questions/2757/a-question-on-factorials) and post a similar question instead of editing the older one?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-07T20:39:37.930Z
It was an accident.
Turbo
CC BY-SA 2.5
2010-11-07T21:35:34.567Z
@Arul: You can undelete the deleted one if you want to.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-07T21:56:39.753Z
@Tsuyoshi: I may be wrong but I think the system does not show the deleted questions to their owners. You need high reputation to be able to see them.
Kaveh
CC BY-SA 2.5
2010-11-07T22:05:12.180Z
If I can see it, then I am ok with it. Anyone can copy the question and title from here and paste it there.
Turbo
CC BY-SA 2.5
2010-11-07T22:18:30.920Z
I assumed that a deleted question is visible to the owner (at least if the question is deleted by the owner).  If it is not the case and you want the older question to be undeleted, ask for undeletion here and I will vote to undelete it.  Alternatively you can flag this question for moderator attention and explain what you want moderators to do.  (But I am not sure if you want to undelete the older one.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-08T00:39:20.477Z
It seems to be too much of a hassle. Lets leave it as it is.
Turbo
<nt.number-theory>
Possible connection between complexity of Factorials and the density of solution of a set of Diophantine equations
Turbo
# Possible connection between complexity of Factorials and the density of solution of a set of Diophantine equations

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

Let $P(x) \in \mathbb Z[x]$ of degree $\ge 2$ and $S = \{(x,n) \in \mathbb Z^{2}:P(x)=n!\}$. It is known:

$(a)$ $|S| < \infty$ under the $abc$ conjecture.

$(b)$ Density of $S$ in $\mathbb Z$ is $0$ unconditionally.

Fix $k \in \mathbb Z$. Let:

$(1)$ $P[k] = \{P(x) = \displaystyle \sum\_{i=0}^{t}p\_{i}x^{i} \in \mathbb Z[x]$: $p\_{i}$ ~ $O(k^{c})$ $\forall i$, $t$ ~ $O(\log^{d} {k})$ for some $c,d \in \mathbb Z\}$ (Set of all polynomials of controlled degree and coefficient size w.r.t $k$)

$(2)$ $R[k] = \{(x,n) \in \mathbb Z^{2}: x$ ~ $O(\log^{r} {k}), n$ ~ $O(k^{s})$ for some $r,s \in \mathbb Z\}$ (Set of all pairs of integer points of prescribed size w.r.t $k$)

$(3)$ $S(k,P(x)) = \{(x,n) \in R[k] : P(x) = n!\}$ (Set of pairs of points of controlled size w.r.t $k$ satisfying a given equation)

$(4)$ $S(k) = \{S(k,P(x)):P(x) \in P[k]\}$ (set of pairs of points of controlled size w.r.t $k$ satisfying $P(x)=n!$ where $P(x)$ is of controlled size w.r.t $k$)

$(5)$ $S = \{S(k):k \in \mathbb Z\}$. (Set of $S(k)$)

$(6)$ $N = \{n \in \mathbb Z: \exists (x,n) \in S\}$. (Set of all integers which has a pair point $x$ so that $(x,n)$ form a controlled size pair solution to $P(x)=n!$ where $P(x)$ is of controlled size for some value of $k$)

$(7)$ $\epsilon$ = density of $N$ in $\mathbb Z$.

**Conjecture:** $\epsilon = 0$.

$\epsilon > 0$ implies for most $m \in \mathbb Z$, $\exists n$ close to $m$ such that $n!$ can be efficiently found since a reasonable size $k$ and $P(x)$ exists to compute $n!$. So $m!$ can be found using a constant number of multiplies given $n!$.

Though $\epsilon > 0$ implies $m!$ has an efficient algorithm for most $m \in \mathbb Z$ since $\exists n \in N$ close to the given $m$, it does not mean the algorithm is known since none of $n$, $k$, $P(x)$ and $x$ are explicit.

Are my arguments correct?

**Tags:** nt.number-theory

> **Comments:**
> **username_2**: Why did you delete the [older question](http://cstheory.stackexchange.com/questions/2757/a-question-on-factorials) and post a similar question instead of editing the older one?  
> **username_0**: It was an accident.  
> **username_2**: @Arul: You can undelete the deleted one if you want to.  
> **username_3**: @Tsuyoshi: I may be wrong but I think the system does not show the deleted questions to their owners. You need high reputation to be able to see them.  
> **username_0**: If I can see it, then I am ok with it. Anyone can copy the question and title from here and paste it there.  
> **username_2**: I assumed that a deleted question is visible to the owner (at least if the question is deleted by the owner).  If it is not the case and you want the older question to be undeleted, ask for undeletion here and I will vote to undelete it.  Alternatively you can flag this question for moderator attention and explain what you want moderators to do.  (But I am not sure if you want to undelete the older one.)  
> **username_0**: It seems to be too much of a hassle. Lets leave it as it is.  
> **username_1**: Um... Can you write that again in English, please?  
> **username_0**: Funny comment Dr. Jeff. I will do it so:)  
> **username_2**: Now crossposted to MathOverflow: http://mathoverflow.net/questions/45523/a-question-on-factorials.  Please add links in both directions when you crosspost.  See http://meta.cstheory.stackexchange.com/questions/65/repeat-a-question-from-math-overflow/618#618 for details.  
> **username_0**: Do you want me to take the other one down?  
> **username_0**: I think one of the comments in the earlier version was if I could get any opinion before posting this on the other site. So far I did not get any. That is why I posted.  
> **username_2**: I had already stated my opinion on crossposting in the link I provided in the previous comment, so please read it.  Just to be perfectly clear, here are my points: (1) You should always provide links in both directions when crossposting a question.  (2) You should wait for a reasonable amount of time before crossposting a question, and I think this reasonable amount of time is one week.  As for (2), I can imagine that some people probably think that 3 days is enough, so (2) is not my main point here.  

---

## 0 answers

