Return to Answer

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

Namely, for any 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 $n'=0\wedge\exists x\ tx'=nx$. The original assertion will be true in arithmetic just in case the translation is true in your exponential polynomial ring.

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

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

Namely, for any 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 $n'=0\wedge\exists x\ tx'=nx$. The original assertion will be true in arithmetic just in case the translation is true in your exponential polynomial ring.

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

Namely, for any 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 $n'=0\wedge\exists x\ tx'=nx$. The original assertion will be true in arithmetic just in case the translation is true in your exponential polynomial ring.

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.

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

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

Namely, for any 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 $n'=0\wedge\exists x\ tx'=nx$. The original assertion will be true in arithmetic just in case the translation is true in your exponential polynomial ring.

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

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

Namely, for any 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 $n'=0\wedge\exists x\ tx'=nx$. The original assertion will be true in arithmetic just in case the translation is true in your exponential polynomial ring.