- #1

mathmari

Gold Member

MHB

- 5,049

- 7

**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?