9
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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}$." $\endgroup$ – hardmath Aug 1 '15 at 1:31
  • 2
    $\begingroup$ 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. $\endgroup$ – Rob Arthan Aug 1 '15 at 16:00
  • 1
    $\begingroup$ 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 $\endgroup$ – Mary Star Aug 1 '15 at 17:04
  • $\begingroup$ Shall I upload a picture of the paper of the part that is related to the above? $\endgroup$ – Mary Star Aug 1 '15 at 17:24
  • $\begingroup$ 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. $\endgroup$ – quid Aug 5 '15 at 20:54
8
+200
$\begingroup$

I have had a chance to look at the paper now. Your description of the reduction and your understanding of the argument is perfectly correct. Your restatement of Lemma 1 is not quite right as explained by quid in acomment above.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. $\endgroup$ – Michael Galuza Aug 5 '15 at 15:41
  • 7
    $\begingroup$ The only question being asked in the OP's posting is whether her understanding is correct. I have answered that question.My answer is not a critique or a request for clarification. $\endgroup$ – Rob Arthan Aug 5 '15 at 18:08
  • 1
    $\begingroup$ @MichaelGaluza So that you know, there is currently a discussion on the meta about this review. $\endgroup$ – Peter Woolfitt Aug 5 '15 at 19:43
  • $\begingroup$ @RobArthan much ado about nothing $\endgroup$ – Michael Galuza Aug 6 '15 at 5:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Rob Arthan Sep 12 '15 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.