# Algorithm to answer existential questions - Reduction

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



How exactly do we conclude from the lemmas to the following? I haven't really understood it... Could you explain it to me?

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



EDIT1 :

The language is $\{+,\cdot , 0,1,t\}$.

I read again the proof and I undetstood the following:

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:

One part of the "translation" of the reduction is the mapping $t^n\mapsto n$.

So, the set "powers of t" corresponds to "integers".

So, we have to be able to "filter out" the powers of $t$ from all the other elements of $F[t, t^{-1}]$ in an existential way, according to Lemma $1$, permitted by the language.

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?



EDIT2:

I am reading again the proof and I got stuck at the following point:

We say that by Lemma $2$, $\mathbb{Z}$ has the structure of divisibility.

Do we conclude to that because this lemma can be written as an existential formula which is true in $F[t,t^{-1}]$ ?

But the language does not consist of the divisibility. How is this existential formula?



EDIT3:

Why doesn't the theorem stand also for $p=2$ ?

• If you are asking about a published paper, it would be helpful to have a citation to it. It seems that you have quoted a bunch of "results", only to ask how those lead to some conclusion about "existential questions in $\mathbb{Z}$." – hardmath Aug 1 '15 at 1:31
• I agree with hardmath: please give the citation if you are quoting from a published paper. In any case, to answer your question we need to know what language you are using to talk about $F[t, t^{-1}]$. If you have quoted Lemma 1 correctly, it looks to me as if $t$ is intended to be represented by a constant in the language. – Rob Arthan Aug 1 '15 at 16:00
• I edited my initial post... Could you take a look at it? It is from this paper: jstor.org/stable/2275396?seq=1#page_scan_tab_contents – Mary Star Aug 1 '15 at 17:04
• Shall I upload a picture of the paper of the part that is related to the above? – Mary Star Aug 1 '15 at 17:24
• You do not know from Lemma 1 that each element is a power of $t$. What you do know from Lemma 1 is that you can characterize the subset of those element in an existential way. And, this is sufficient. – quid Aug 5 '15 at 20:54

• Annoyingly, Pheidas doesn't number the theorems. The theorem you've quoted is the one stated after lemma 5, Its proof uses lemma 5 which requires $p > 2$ so Pheidas has only given the proof for $p > 2$. The remark following the theorem says that the theorem also holds for $p = 2$ but the proof needs a modification to lemma 5. – Rob Arthan Sep 12 '15 at 16:30