9
$\begingroup$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$).

Theorem 1.

Assume that the characteristic of $F$ is zero. Then the existential theory of $F[t, t^{-1}]$ in the language $\{+, \cdot , 0, 1, t\}$ is unecidable.

Theorem 2.

Assume that $F$ has characteristic $p>2$. Then the existential theory of $F[t, t^{-1}]$ is undecidable.

We have that even the positive existential theory of $F[t, t^{-1}]$ is undecidable.

Now we give a Lemma that, together with the preceding results, allows us to conclude the undecidability of the positive existential theory of $F[t]$ in the language $\{+, \cdot , 0, 1, t\}$.

Lemma.

If the characteristic of $F$ is other than $2$, then the solutions of $$X^2-(t^2-1)Y^2=1$$ with $X$ and $Y$ in $F[t]$ are given by $$(X, Y)=(\pm x_n, y_n)$$ where $$x_n+\sqrt{t^2-1}y_n=(t+\sqrt{t^2-1})^n$$ fr $n$ in $\mathbb{Z}$.

Theorem 3.

If the characteristic of $F$ is other than $2$, then $F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$.

Proof.

Write $u=t+\sqrt{t^2-1}$.

Then $u^{-1}=t-\sqrt{t^2-1}$ and $F[u, u^{-1}]=F[t, \sqrt{t^2-1}]$.

We interpret the positive existential theory of $F[u, u^{-1}]$ in $F[t]$ in the following way:

an element $x$ of $F[u, u^{-1}]$ is represented as a pair $x=(a, b)$ with $a, b$ in $F[t]$ being the components of $x$ with repsect to the base $\{u, u^{-1}\}$ considering $F[u, u^{-1}]$ as a module over $F[t]$; addition and multiplication of elements of $F[u, u^{-1}]$ is defined accordingly.

So, we see that the positive existential theory of $F[u, u^{-1}]$ is interpretable in $F[t]$ with only one problem: we do not have constants for $u$ and $u^{-1}$ but only for $\frac{u+u^{-1}}{2}=t$.

So, the positive existential theory of $F[t]$ is undecidable provided that the theory of $F[u, u^{-1}]$ is undecidable in the language $\{0, 1, u+u^{-1}/2, +, \cdot\}$.

It is only a matter of routine checking to see that our undecidability result for $F[u, u^{-1}]$ holds true in this language as well: simply substitute $v=u-t$, write all equations involved in the form $fv=g$, where $f$ and $g$ have coefficients in $F[t]$ (the quantity $v^2$, wherever it appears, is replaced by $t^2-1$ which is in $F[t]$) and substitute the equations of this last form by the corresponding equations $f^2(t^2-1)=g^2$.

Of course, it is necessary to check that the new solutions that come onto the scene through the squaring do not do any harm to the stated equivalences.

Hence, the theorem follows.


$$$$

How do we use the Lemma at the proof of Theorem $3$ ? How is it useful?

$$$$

EDIT:

That's how I understood the whole proof of Theorem $3$ :

We know that the existential theory of $F[u, u^{-1}]$ in the language $\{+, \cdot , 0, 1, u\}$ is undecidable.

We want to reduce the positive existential theory of $F[u, u^{-1}]$ in the language $\{+, \cdot , 0, 1, u\}$ to the positive existential theory of $F[t]$ in the language $\{+, \cdot , 0, 1, t\}$ to show that this theory is also undecidable.

To do that we do the following:

We suppose that the positive existential theory of $F[t]$ in the language $\{+, \cdot , 0, 1, t\}$ is decidable.

We set $u=t+\sqrt{t^2-1}$. So, we have that $u^{-1}=t-\sqrt{t^2-1}$.

So, we have $F[u, u^{-1}]=F[t, \sqrt{t^2-1}]$. So, $F[u, u^{-1}]$ is an extension of $F[t]$.

Each element $x$ of $F[u, u^{-1}]$ can be written as followed: $x=a+b\sqrt{t^2-1}$, where $a,b \in F[t]$.

So, the mapping of the reduction is $x \mapsto (a,b)$.

$+ \ \ : \ \ $ $$x_1+x_2=a_1+b_1\sqrt{t^2-1}+a_2+b_2\sqrt{t^2-1}=(a_1+a_2)+(b_1+b_2)\sqrt{t^2-1} \mapsto (a_1+a_2, b_1+b_2)$$ $\cdot \ \ : \ \ $ $$x_1\cdot x_2=(a_1+b_1\sqrt{t^2-1})(a_2+b_2\sqrt{t^2-1})=a_1 \cdot a_2+a_1 \cdot b_2 \sqrt{t^2-1}+a_2 \cdot b_1\sqrt{t^2-1}+b_1 \cdot b_2 (t^2-1)=(a_1 \cdot a_2+b_1 \cdot b_2 (t^2-1))+(a_1 \cdot b_2+a_2 \cdot b_1)\sqrt{t^2-1} \mapsto (a_1 \cdot a_2+b_1 \cdot b_2 (t^2-1), a_1 \cdot b_2+a_2 \cdot b_1)$$ $0 \ \ : \ \ $ $$0=0+0 \sqrt{t^2-1} \mapsto (0,0)$$ $1 \ \ : \ \ $ $$1=1+0 \sqrt{t^2-1} \mapsto (1,0)$$
$u \ \ : \ \ $ $u \mapsto u-t=:v$. We write all the equations in the form $fv=g$ where $f,g \in F[t]$ and squaring these equations we get $f^2v^2=g^2 \Rightarrow f^2(t^2-1)=g^2$, so all these equations are in $F[t]$, where $t=(u+u^{-1})/2$.

So we can convert the algorithm that answers to positive existential questions of $F[t]$ to an algorithm that answers to existential questions of $F[u, u^{-1}]$.

Since the second theory is undecidable, we get aa contradiction. So the positive existential theory of $F[t]$ is undecidable.

$$$$

Is this correct?

$\endgroup$
7
+200
$\begingroup$

You are, I believe, asking about a proof in the paper Extensions of Hilbert's Tenth Problem by Thanases Phaedas. You've asked three questions about this. The background is that Phaedas has proved that the existential theory of $F[u, u^{-1}]$ is undecidable (he actually wrote $t$ rather than $u$ when he proved, but he has now switched to $u$). He is trying to get stronger result by reducing decidability in the polynomial ring $F[t]$ to decidability in the ring of Laurent polynomials $F[u, u^{-1}]$. The approach is to extend $F[t]$ to $F[t, s\mathrel{|} s^2 = t^2 - 1]$ (but Phaedas doesn't quite put it like that). Then one observes that $F[t, s]$ is isomorphic to $F[u, u^{-1}]$ under an isomorphism that associates $t$ with $(u + u^{-1})/2$ and $s$ with $(u - u^{-1})/2$.

Your first question is:

an element $x$ of $F[u, u^{-1}]$ is represented as a pair $x=(a, b)$ with $a, b$ in $F[t]$ being the components of $x$ with repsect to the base $\{u, u^{-1}\}$ considering $F[u, u^{-1}]$ as a module over $F[t]$

Does this mean that we write any element $x$ of $F[u, u^{-1}]$ in the form $x=au+bu^{-1}$ ?

It means that every $x \in F[u, u^{-1}]$ can be written uniquely as $x = au+bu^{-1}$ for $a, b \in F[t]$. However, I believe this is false. $F[t, s]$ is a free module of rank $2$ over $F[t]$, a suitable base being $\{1, s\}$ (which Pheidas would write as $\{1, \sqrt{t^2 - 1}\}$). What this means is that every element $x \in F[u, u^{-1}]$ can be written uniquely in the form $a + bs$ with $a, b \in $F[t]$. I believe this is just a (very significant) typo.

Your second question is:

We have that each element of $F[u, u^{-1}]$ can be represented as an element of $F[t]$, besides $u$ and $u^{-1}$, becasuse the language does not consist of a square root. Is this correct?

What we have is that each element of $F[u, u^{-1}]$ can be represented uniquely as a pair of elements $a, b$ of $F[t]$ with $(a, b)$ representing $a + bs$ (following my correction to Pheidas's statement about the basis above).

Your final question is:

$\ldots$ simply substitute $v=u-t$, write all equations involved in the form $fv=g$, where $f$ and $g$ have coefficients in $F[t]$ (the quantity $v^2$, wherever it appears, is replaced by $t^2-1$ which is in $F[t]$) $\ldots$

Why can we write all the equations in the form $fv=g$, where $f$ and $g$ have coefficients in $F[t]$ ?

$F[u, u^{-1}]$ is generated over $F$ as a ring by $t$ and $v$, hence any equation in $F[u, u^{-1}]$ can be written as $p(t, v) = 0$ where $p$ is a polynomial with coefficients in $F$, but $v^2 = t^2-1$, so we can arrange for $p$ to have the form $vf(t) - g(t)$ for $f, g \in F[t]$. and then $p(r, t) = 0$ is equivalent to $fv = g$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You say that the approach of the reduction is to extend $F[t]$ to $F[t,s\mid s^2=t^2-1]$ and at the beginning of the proof we take $u=t+\sqrt{t^2-1}$. Why do we take this extension? Which the reason that we take this $u$ ? $$$$ What does it mean that "$F[t,s]$ is a free module of rank $2$ over $F[t]$" ? $\endgroup$ – Mary Star Aug 17 '15 at 1:36
  • $\begingroup$ I have tried to expand my answer a bit to help with these comments. To say a bit more out the motivation: if you play around with the elements $t = (u + u^(-1})/2$ and $s = (u + u^{-1})/2$ in the ring of Laurent polynomial $F[u, u^{-1}]$, you find they have the pleasant property that $s^2 = t^2 -1$ and that they generate $F[u, u^{-1}]$ in a very simple way (as a free $F[t]$ module of rank 2). This makes it natural to see if everything one needed to express in the language of $F[u, u^{-1}]$ in the first undecidability result can be recast in the language of $F[t]$. $\endgroup$ – Rob Arthan Aug 18 '15 at 16:17
  • $\begingroup$ Why do the elements $t$ and $s$ generate $F[u, u^{-1}]$ ? $$$$ At which point of the proof do we use the Lemma? $$$$ I still don't understand the part: "So, we see that the positive existential theory of $F[u, u^{-1}]$ is interpretable in $F[t]$ with only one problem: we do not have constants for $u$ and $u^{-1}$ but only for $\frac{u+u^{-1}}{2}=t$. So, the positive existential theory of $F[t]$ is undecidable provided that the theory of $F[u, u^{-1}]$ is undecidable in the language $\{0, 1, u+u^{-1}/2, +, \cdot\}$." Could you explain it to me? $\endgroup$ – Mary Star Aug 20 '15 at 11:19
  • $\begingroup$ We want to map the elements of $F[u, u^{-1}]$ into the elements of $F[t]$, right? There is no mapping of the elements $u=t+\sqrt{t^2-1}$ and $u^{-1}=t-\sqrt{t^2-1}$ into an element of $F[t]$, because the square root is not contained at the language so $t+\sqrt{t^2-1}$ and $t-\sqrt{t^2-1}$ are not elements of $F[t]$. Have I understood it correct so far? Why do we have to look then at the language $\{0, 1, u+u^{-1}/2, +, \cdot\}$ and not at the original language $\{+, \cdot , 0, 1, t\}$ ? Could you explain it to me? $\endgroup$ – Mary Star Aug 20 '15 at 17:38
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Module_(mathematics) for the definition of a module over a ring (or, and much better, read an introductory book on ring theory or attend a course). Whenever $R$ is a subring of a ring $S$, $S$ automatically becomes a module over $R$ in a standard way. Here $F[t]$ is a subring of $F[u, u^{-1}]$. $\endgroup$ – Rob Arthan Aug 29 '15 at 14:48

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.