Algorithm to answer existential questions - Reduction

In summary, the theorem says that the existential theory of $F[t,t^{-1}]$ is undecidable. However, for $p=2$, the theory is decidable.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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?
 
Physics news on Phys.org
  • #2
Why doesn't the theorem hold also for $p=2$ ?
 

Related to Algorithm to answer existential questions - Reduction

1. What is an algorithm for answering existential questions?

An algorithm for answering existential questions is a set of step-by-step instructions or procedures designed to help a computer or human find a logical and systematic solution to a question about existence. It involves breaking down complex questions into smaller, more manageable sub-questions and using logic and reasoning to arrive at a conclusion.

2. How does the algorithm work?

The algorithm works by first identifying and defining the key terms and concepts in the question. Then, it breaks down the question into smaller sub-questions and applies logical principles, such as deduction and induction, to analyze and evaluate each sub-question. The algorithm then uses this information to arrive at a conclusion or answer to the original question.

3. What are some common reduction techniques used in this algorithm?

Some common reduction techniques used in this algorithm include abstraction, generalization, and simplification. These techniques help to break down complex questions into more manageable parts and eliminate irrelevant information, allowing for a more focused and systematic approach to finding an answer.

4. Can this algorithm be applied to all existential questions?

While this algorithm can be applied to many existential questions, it may not be suitable for all of them. Some questions may be too abstract or subjective to be answered using a purely logical approach. Additionally, the accuracy and reliability of the algorithm's answer may also depend on the quality and specificity of the original question.

5. How can this algorithm benefit society?

This algorithm can benefit society by providing a structured and logical approach to answering complex existential questions. It can help individuals and organizations make informed decisions and solve problems related to existence, such as ethical dilemmas and philosophical debates. It can also contribute to advancements in various fields, such as artificial intelligence and cognitive science.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
432
Replies
4
Views
535
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
546
  • Calculus and Beyond Homework Help
Replies
8
Views
160
  • Set Theory, Logic, Probability, Statistics
Replies
27
Views
3K
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top