Exponential Diophantine representation of the factorial How can I use the identity $$\sum_{n=0}^\infty \frac{\tau^n}{n!} = \lim_{y \to \infty} \left( 1 + \frac{\tau}{y} \right)^y$$ to find an exponential Diophantine representation of the factorial?
I was hoping to use a very large value of $y$ (so that the RHS is within an integer of the actual number) and expand with binomial theorem then extract the $\tau^k$ term to get at $k!$ but since we have $\frac{1}{k!}$ this is impossible.
I am really stuck! Any clues on how to do this? Thank you.
 A: Matiyasevich exercise III.5, hey ? I know this topic is 6 years old but I was actually stuck on the same problem and it led me here. So after one week of struggle (Matiyasevich had been very laconic in his hints, purposely I guess), I came out with a solution, and thought it was worth leaving it here for future researchers (or for you if you're still interested). So here it goes. Let
$$\alpha=x^me^{1/x}=\underbrace{x^m+x^{m-1}+\frac{x^{m-2}}{2!}+\dots+\frac{x}{(m-1)!}+\frac{1}{m!}}_{P_m(x)}+R_m(x)$$
for some integers $m,x>0$. Notice that
$$xP_{m-1}(x)=P_m(x)-\frac{1}{m!}\ ,$$
so that what we need is an exponential Diophantine representation of $P_m(x)$. By the theory of continued fractions, we know that if
$$\left|\alpha-\frac{u}{v}\right|<\frac{1}{2v^2}$$
for some integers $u,v$ with $v\neq 0$, then $u/v$ is a convergent of $\alpha$. Since $0<\alpha-P_m(x)=R_m(x)<1/x$ for $x>1$, as can be easily shown, and since $P_m(x)=u/m!$ for some integer $u$, with $m!\leq m^m$ for $m>0$, it follows that $P_m(x)$ is some convergent of $\alpha$ for $x>2\cdot m^{2m}$ (which we will assume from now on). Let this convergent be the $n-$th one, so that $P_m(x)=p_n/q_n$ with $p_n,q_n$ coprime and $q_n\mid m!~$.
Next we show that no other convergent with denominator $\leq m^m$ can approach $\alpha$ within the $1/x$ margin. Since the proof is rather notation-intensive I'll post the details upon request, but the spirit is : $(i)$ find a minoration of the error $|\varepsilon_{n-1}|=|\alpha-p_{n-1}/q_{n-1}|$ that shows that it cannot be $<1/x$, and hence every convergent with rank $<n$ is not precise enough ; $(ii)$ using the fact that
$$\frac{2}{x}>|\varepsilon_n|+|\varepsilon_{n+1}|=\frac{1}{q_nq_{n+1}}\quad,$$
show that $q_{n+1}>m^m$ so that convergents with rank $>n$ have too big a denominator.
Hence, $P_m(x)$ is the only rational with a denominator $\le m^m$ such that $|\alpha-P_m(x)|<1/x$. But that's not enough, since $\alpha$ is transcendental. We need another way to approximate it, but it takes some care. First, notice that $P_m(x)$ is actually in $]\alpha-\eta/x;\alpha[$ where $\eta$ can be chosen strictly lesser than $1$, for instance $\eta=4/5$ will do (actually, any rational between $e-2$ and $1$ would do). Then, it can be shown that if
$$0<\alpha-\tilde\alpha<\frac{1-\eta}{x}\quad,$$
then for any $\mu\in\mathbb Q$ with denominator $\leq m^m$, one has $\mu=P_m(x)$ if and only if $|\tilde\alpha-\mu|<\frac{\eta}{x}$.
So all that's left to do is find a rational approximation $\tilde\alpha_n$ that lies in $]\alpha-(1-\eta)/x,\alpha[$. With a little effort, it can be shown that
$$0<\underbrace{x^me^{1/x}}_{\alpha}-\underbrace{x^m\left(1+\frac{1}{xn}\right)^n}_{\tilde\alpha_n}<\frac{3x^m}{n}$$
for all $x,n>1$ (hence in particular for $x>2m^{2m}$), so that $\tilde\alpha_n$ does the trick for a sufficiently large $n$ (with my choice of $\eta$, I found $n>15x^{m+1}$, which is indeed an exponential Diophantine condition).
Puting this all together, it is then straightforward to show that
$$\mathcal R(u,v,m,x)\iff (m>0)\wedge(x>2m^{2m})\wedge(v\leq m^m)\wedge(u=vP_m(x))$$
is exponential Diophantine, and then to use the relation between $P_m(x)$ and $P_{m-1}(x)$ to show that $(m>1)\wedge(a=m!)$, and hence $a=m!$, are exponential Diophantine.
