F[t] has undecidable positive existential theory in the language {+,⋅,0,1,t}

Watch
mathmari
Badges: 1
Rep:
?
#1
Report Thread starter 5 years ago
#1
Hello!!

I am reading the following part of a paper but I got stuck at some points...

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

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


The trick in the last theorem was to interpret the theory of an algebraic extension of a ring into the theory of the base ring.
Suppose that A is an integral domain and B is an extension ring of A so that the quotient field of B is algebraic over the quotient field of A and B is a finite dimensional free module over A with base, say \{b_1, \dots , b_n\}.
Suppse that C is a set of constants each of which represents an individual element of A and define L=\{+, \cdot , 0, 1\}\cup C.
For each i=1, \dots n, let f_i be an irreducible polynomial over the quotient field of A, with coefficents in A, which has b_i as a zero in B.
Let D=\{d_1, \dots , d_r\} be the set of coefficients of all the f_i's, and define L_A=L \cup D and L_B=L_A\cup \{b_1, \dots , b_n\} \cup \{T\}, where T is a predicate for the relation "x is an element of A". Let A_0 be the subring of A which is generated by the elements of A which are representable by constants in L_A (so each element of A_0 is representable in A as a polynomial in the constants in L_A with coefficients in \mathbb{Z}), and let B_0 be the subring of which is generated by the elements of B that are representable by constants in L_B (so each element of B_0 can be represented as a polynomial in the constants of L_B with coefficents in \mathbb{Z}).

Techical Lemma.
Assume that there is an effective procedure to write each element of the subring B_0 in the form a_1b_1+\dots +a_nb_n with a_1, \dots , a_n in A (it is easy to see that there is always such a representation of elements of B_0 but its effective nature has to be assumed).
Then the existential theory of B in the language L_B is decidable if and only if the existential theory of A in L_A is decidable.








I have some questions about the proof of the theorem 3.

At the beginning of the proof we take u=t+\sqrt{t^2-1}.
Which is the reason that we take this u ?


"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"

We have that each element of F[u, u^{-1}] can be represented as an element of F[t], besides u and u^{-1}, because the language does not consist of a square root. Is this correct?
0
reply
driftawaay
Badges: 3
Rep:
?
#2
Report 5 years ago
#2
I have no idea but let me just say that this is scariest thing I have ever seen in my life
0
reply
PrimeLime
Badges: 12
Rep:
?
#3
Report 5 years ago
#3
(Original post by driftawaay)
I have no idea but let me just say that this is scariest thing I have ever seen in my life
Amen to that. And I'm applying to Cambridge Maths in a couple of months...
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Should there be a new university admissions system that ditches predicted grades?

No, I think predicted grades should still be used to make offers (563)
34.12%
Yes, I like the idea of applying to uni after I received my grades (PQA) (680)
41.21%
Yes, I like the idea of receiving offers only after I receive my grades (PQO) (332)
20.12%
I think there is a better option than the ones suggested (let us know in the thread!) (75)
4.55%

Watched Threads

View All