- #1
mathmari
Gold Member
MHB
- 4,984
- 7
Hey! 
Lemma 1.
For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and $t-1$ divides $x-1$ (the divisibilities are meant, of course, in $F[t, t^{-1}]$).
Lemma 2.
$t^n-1$ divides $t^m-1$ in $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$) if and only if $n$ divides $m$ in $\mathbb{Z}$.
Lemma 3.
Assume that the characteristic of $F$ is $p$ and $p>2$.
Then $(t^m-1)/(t^n-1)$ is a square in $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$) if and only if $(\exists s \in \mathbb{Z}) m=np^s$.
THEOREM.
Assume that $F$ has characteristic $p>2$. Then the existential theory of $F[t, t^{-1}]$ in the language is $\{+,\cdot , 0,1,t\}$ is undecidable.
PROOF.
We think of the powers of $t$ as representing the integers; thus, $t^n$ represents the integer $n$. By Lemma $1$, the set of powers of $t$ is existentially definable.
Addition of integers $m+n$ corresponds to multiplication of the corresponding powers of $t$, $t^mt^n$.
By Lemma $2$, the relation "$n$ divides $m$" (where $n$ and $m$ are given through their corresponding powers $t^n$ and $t^m$) is existentially definable.
Moreover, the relation $(\exists s \in \mathbb{Z})m=p^sn$, by Lemma $3$, is also existentially definable.
Therefore, if we had an algorithm to answer existential questions over $F[t, t^{-1}]$, we could convert it to an algorithm to answer existential questions in $\mathbb{Z}$ with the structure of addition, divisibility, and the relation $(\exists s \in \mathbb{Z})m=p^sn$.
In an other paper it is shown that the last structure has undecidable positive existential theory (more accurately, one can define multiplication in a positive existential way in it, and therefore, the complexity of its positive existential theory is the same as the complexity of the positive existential theory of $\mathbb{Z}$ with addition and multiplication).
It follows that the existential theory of $F[t, t^{-1}]$ is undecidable.
That's how I understand the proof:
We suppose that the existential theory of $F[t,t^{-1}]$ is decidable, that means that there is an algorithm that answers existential questions over $F[t,t^{-1}]$.
We want to reduce it to the existential theory of $\mathbb{Z}$ with the structure of addition, divisibility, and the relation $(\exists s\in\mathbb{Z})m=p^sn$, which is undecidable.
To do so, we do the following:
we know from Lemma $1$ that each element $x$ of $F[t,t^{-1}]$ is a power of $t$, $x=t^n$.
One part of the "translation" of the reduction is the mapping $t^n\mapsto n$.
We have that $t^mt^n=t^{m+n}\mapsto m+n$ so $\mathbb{Z}$ has the structure of addition.
By Lemma $2$ , $\mathbb{Z}$ has the structure of divisibility.
And by Lemma $3$, $\mathbb{Z}$ has the structure of the relation $(\exists s\in \mathbb{Z})m=np^s$.
Is that the idea of reduction? Have I understood it correctly?
Lemma 1.
For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and $t-1$ divides $x-1$ (the divisibilities are meant, of course, in $F[t, t^{-1}]$).
Lemma 2.
$t^n-1$ divides $t^m-1$ in $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$) if and only if $n$ divides $m$ in $\mathbb{Z}$.
Lemma 3.
Assume that the characteristic of $F$ is $p$ and $p>2$.
Then $(t^m-1)/(t^n-1)$ is a square in $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$) if and only if $(\exists s \in \mathbb{Z}) m=np^s$.
THEOREM.
Assume that $F$ has characteristic $p>2$. Then the existential theory of $F[t, t^{-1}]$ in the language is $\{+,\cdot , 0,1,t\}$ is undecidable.
PROOF.
We think of the powers of $t$ as representing the integers; thus, $t^n$ represents the integer $n$. By Lemma $1$, the set of powers of $t$ is existentially definable.
Addition of integers $m+n$ corresponds to multiplication of the corresponding powers of $t$, $t^mt^n$.
By Lemma $2$, the relation "$n$ divides $m$" (where $n$ and $m$ are given through their corresponding powers $t^n$ and $t^m$) is existentially definable.
Moreover, the relation $(\exists s \in \mathbb{Z})m=p^sn$, by Lemma $3$, is also existentially definable.
Therefore, if we had an algorithm to answer existential questions over $F[t, t^{-1}]$, we could convert it to an algorithm to answer existential questions in $\mathbb{Z}$ with the structure of addition, divisibility, and the relation $(\exists s \in \mathbb{Z})m=p^sn$.
In an other paper it is shown that the last structure has undecidable positive existential theory (more accurately, one can define multiplication in a positive existential way in it, and therefore, the complexity of its positive existential theory is the same as the complexity of the positive existential theory of $\mathbb{Z}$ with addition and multiplication).
It follows that the existential theory of $F[t, t^{-1}]$ is undecidable.
That's how I understand the proof:
We suppose that the existential theory of $F[t,t^{-1}]$ is decidable, that means that there is an algorithm that answers existential questions over $F[t,t^{-1}]$.
We want to reduce it to the existential theory of $\mathbb{Z}$ with the structure of addition, divisibility, and the relation $(\exists s\in\mathbb{Z})m=p^sn$, which is undecidable.
To do so, we do the following:
we know from Lemma $1$ that each element $x$ of $F[t,t^{-1}]$ is a power of $t$, $x=t^n$.
One part of the "translation" of the reduction is the mapping $t^n\mapsto n$.
We have that $t^mt^n=t^{m+n}\mapsto m+n$ so $\mathbb{Z}$ has the structure of addition.
By Lemma $2$ , $\mathbb{Z}$ has the structure of divisibility.
And by Lemma $3$, $\mathbb{Z}$ has the structure of the relation $(\exists s\in \mathbb{Z})m=np^s$.
Is that the idea of reduction? Have I understood it correctly?