5
$\begingroup$

Do you know if I can find the proof that the existential theory of $\mathbb{Z}$ with the structure of addition , divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable, besides the one of the paper of J. Denef "The diophantine problem for polynomial rings of positive characteristic" ?

In the paper of Denef, the corollary is stated as followed:

Let $p$ be a fixed prime number, $p>1$.

Define the relation $|^p$ by $$x |^p y \leftrightarrow \exists f \in \mathbb{N} : y= \pm x p^f$$

Then the positive existential theory of $(\mathbb{Z}; +, | , |^p)$ is undecidable.

Improve this question
$\endgroup$
5
  • $\begingroup$ Could you clarify the relation? Do you mean a binary relation, where $p$ is a fixed prime? Or do you mean a trinary relation, or what? $\endgroup$
    – Joel David Hamkins
    Commented Sep 2, 2015 at 20:52
  • $\begingroup$ I found the relation $(\exists s \in \mathbb{Z})m=np^s$ in the paper jstor.org/stable/2275396?seq=1#page_scan_tab_contents . I added how it is formulated in the paper of Denef. @JoelDavidHamkins $\endgroup$
    – Mary Star
    Commented Sep 2, 2015 at 21:08
  • $\begingroup$ Based on mathoverflow.net/questions/216251/… , my guess is it is a binary relation (as p is fixed), and that this question will not have a concise and suitable answer. Gerhard "Unsure And Undecided About Suitability" Paseman, 2015.09.02 $\endgroup$
    – Gerhard Paseman
    Commented Sep 2, 2015 at 21:43
  • $\begingroup$ I think I do not understand your question. The statement $\exists s \in \mathbb{Z} (m=np^s)$ is decidable easily: just check all $s$ up to the values of $m$. $\endgroup$
    – Dávid Natingga
    Commented Sep 3, 2015 at 12:37
  • $\begingroup$ I am looking for the proof that the existential theory of $\mathbb{Z}$ with the structure of addition, divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable. I have found one proof at the paper of Denef and I was wondering if I can find the proof also somewhere else... Do you maybe where I can find it? @DávidTóth $\endgroup$
    – Mary Star
    Commented Sep 3, 2015 at 14:35

1 Answer 1

Reset to default
3
$\begingroup$

This is Theorem 1, p. 530 in paper [1] by Pheidas.

Reference

[1] Thanases Pheidas, "An undecidability result for power series rings of positive characteristics. II." Proceedings of the American Mathematical Society 100, 526–530 (1987), MR891158, Zbl 0664.03008.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .