# Show that the positive existential theory is undecidable

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?

• Interesting question. Your notation $x(1)=1$ suggests that you allow to evaluate the polynomial expressions in your ring, but this is not actually mentioned in the language. Could you clarify whether this is allowed or not? Nov 20, 2015 at 0:36
• I think you mean $t-1$ rather than $z-1$. You are saying that polynomial/exponential expression $x(t)$ has $x(1)=1$ just in case it is a multiple of the term $(t-1)$. Nov 20, 2015 at 2:08
• But that doesn't seem true to me. For example, take $x=\frac 1ee^t$, which has $x(1)=1$. But unless I am mistaken, I don't think we have that $t-1$ divides $x-1$. (It would be true in the polynomial ring, but not in this exponential-polynomial ring.) Nov 20, 2015 at 2:57
• I don't really understand the close votes, since I think the question is interesting. Can you define $\mathbb{Z}$ in the structure $\mathbb{C}[t,e^{\lambda t}]_{\lambda\in \mathbb{C}}$ by an existential formula in the language of rings with differentiation and a constant for the polynomial $t$? Nov 20, 2015 at 12:02
• I posted an answer. The issue of $x(1)=1$ seems unnecessary to me now. Nov 21, 2015 at 14:08

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.

• I realized that one must add $x\neq 0$ to the definition in the lemma in order to avoid unwanted solutions, but now this is not "positive". So we get undecidability of the existential theory, but not (yet) for the positive existential theory. Perhaps one can get rid of this irritation somehow. Nov 21, 2015 at 15:05
• The original condition $x(1)=1$ would eliminate the unwanted solution. Nov 21, 2015 at 15:07
• Yes, I agree with that. But I don't see how to express that in the language at hand. We can't seem to evaluate the exponential/polynomial expressions at a given complex number, using only the allowed language. Nov 21, 2015 at 15:11
• Why not (as suggested in a comment) $(t-1) | (x-1)$? It is true for $\lambda t^n$ only when $\lambda=1$. More formally, $\exists y \; (x-1)=y\cdot(t-1)$. Nov 21, 2015 at 15:16
• Ah, yes, this works with polynomials, and so it is fine here. My earlier objection was that this does not define $x(1)=1$ in the full ring, since $x=\frac 1ee^t$ is a counterexample, but it is fine once you know that $x$ is a polynomial. I'll edit. Nov 21, 2015 at 15:19