To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $$n \in \mathbb{N} \leftrightarrow \exists x \left (n \in \mathbb{C} \land tx'=nx \land x(1)=1\right )$$ 


So do we have to do the following? 


We suppose that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0, 1, t\}$ is decidable, i.e., there is an algorithm that answers to positive existential questions over $(\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}];+, \cdot , ' , 0, 1, t)$. 


We want to reduce the positive existential theory $\mathbb{N}$ in the language $\{+, \cdot , 0, 1\}$ into the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0, 1, t\}$. 


Is this correct? 


But which is the mapping of the reduction? 



Show that the positive existential theory is undecidable
I like this question very much. Before answering, let me try to
explain the question in my words.


You are considering the structure $\mathbb{C}[t,e^{\lambda t}]\_{\lambda\in\mathbb{C}}$,
which is the ring of all polynomial expressions over $\mathbb{C}$ in the
indeterminate variable $t$ and $e^{\lambda t}$, for any $\lambda\in\mathbb{C}$.
So this ring has objects like this: $$t\qquad\qquad (t^2+5)e^{3t}+te^{\pi
t}\qquad\qquad t^2e^{\pi i t}+5t^{10}.$$ We consider this structure in the
language of rings, using addition, multiplication, 0, 1, augmented
with the differentiation operation $f'$ and a constant symbol for
the polynomial $t$. So we may freely make terms like $t^2x''+tx$
and so on, where $x$ is a variable ranging over the ring. The
exponential polynomials are simply points in the structure. The question is whether the positive existential theory of this structure is undecidable.


In order to show that the existential theory of this structure is
undecidable, it suffices to show that we may define the natural
numbers in it by an existential property, for then we would be
able to reduce any existential question in the language of
arithmetic, that is, in the structure
$\langle\mathbb{N},+,\cdot,0,1\rangle$, to an existential question
in your structure. Since the existential theory of arithmetic is
undecidable, it will follow that the existential theory of your
structure will be undecidable.


Notice that we can define the constant polynomials, that is, the
elements of $\mathbb{C}$ in your ring, since these are precisely
the $x$ that satisfy $x'=0$.


Let us view $\mathbb{N}$ as a subset of $\mathbb{C}$, which is a
subset of your ring $\mathbb{C}[t,e^{\lambda t}]\_{\lambda\in\mathbb{C}}$. Using the idea
you suggested, we can define $\mathbb{N}$ in your ring by an
existential formula as follows:


**Lemma.** $n\in\mathbb{N}$ if and only if
$\mathbb{C}[t,e^{\lambda t}]\_{\lambda\in\mathbb{C}}\models n'=0\wedge \exists x\
tx'=nx\wedge x\neq 0$.


**Proof.** If $n$ is a natural number, then it is constant and so
the derivative $n'$ is $0$. But furthermore, if $x=t^n$, then
$x'=nt^{n-1}$, and so $tx'=nx$. So $n$ satisfies the definition.


Conversely, suppose that $n\in\mathbb{C}$ and there is some nonzero $x$ in
your ring with $tx'=nx$. I claim that the only solutions of this
differential equation are of the form $\lambda t^n$, for
$\lambda\in\mathbb{C}$. Certainly any expression of this form is a
solution. And if $x$ and $y$ are both solutions of the
differential equation, then $(\frac
xy)'=\frac{x'y-y'x}{y^2}=\frac{\frac{nx}ty-\frac{ny}tx}{y^2}=0$.
So every solution is a constant multiple of $t^n$. Since this
occurs only for $n\in\mathbb{N}$ in your ring, it follows that $n$
is a natural number. **QED**


So we have defined $\mathbb{N}$ by an existential formula in your
structure, and therefore the existential theory of your structure
is undecidable. Any existential assertion in arithmetic, such as
the halting problem, can be transformed to an existential theory
in your structure.


The existential assertion in the lemma is not positive, however, because of the $x\neq 0$ part. But we can replace $x\neq 0$ there with the assertion that $(t-1)$ divides $x-1$, since once we know that $x$ is a solution of $tx'=nx$, we know that $x$ must have the form $x=\lambda t^n$, and the only way that $t-1$ can divide $\lambda t^n-1$ is if $\lambda=1$. Thus, we have:


$$n\in\mathbb{N}\iff \mathbb{C}[t,e^{\lambda t}]\_{\lambda\in\mathbb{C}}\models n'=0\wedge \exists x\
tx'=nx\wedge \exists y\ (t-1)y=x-1.$$


So the natural numbers are defined by a positive existential assertion in your exponential polynomial ring.


Therefore, for any positive existential assertion $\exists n\_0,n\_1,\ldots,n\_k\ \varphi(\vec n)$ in the language of arithmetic, where $\varphi$ is quantifier free, we may translate this to $\exists n\_0,\ldots,n\_k( n\_0\in\mathbb{N}\wedge\cdots\wedge n\_k\in\mathbb{N}\wedge\varphi(\vec n)$ in the language of your ring, where $n\in\mathbb{N}$ is an abbreviation for the formula displayed above. The original assertion will be true in arithmetic just in case the translation is true in your exponential polynomial ring.


