MHB Understanding the Equivalence in Diophantine Relations

  • Thread starter Thread starter mathmari
  • Start date Start date
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I am reading the following part of the paper of Denef (http://www.ams.org/journals/tran/1978-242-00/S0002-9947-1978-0491583-7/S0002-9947-1978-0491583-7.pdf):

Let $R$ be a commutative ring with unity and let $D(x_1,\dots , x_n)$ be a relation in $R$. We say that $D (x_1,\dots , x_n)$ is diophantine over $R$ if there exists a polynomial $P(x_1,\dots , x_n,y_1,\dots ,y_m)$ over $R$ such that for all $x_1,\dots , x_n$ in $R$ : $$D(x_1, \dots , x_n) \leftrightarrow \exists y_1, \dots , y_m \in R : P(x_1, \dots , x_n, y_1, \dots , y_m)=0$$

Let $R'$ be a subring of $R$ and suppose $P$ can be chosen such that its coefficients lay in $R'$, then we say that $D (x_1,\dots , x_n)$ is diophantine over $R$ with coefficients in $R'$.

Proposition 1.
Let $R$ be an integral domain of characteristic zero. Suppose there exists a subset $S$ of $R$ which contains $\mathbb{Z}$ and which is diophantine over $R[T]$; then $\mathbb{Z}$ is diophantine over $R[T]$.
In particular, this is true when $R$ contains $\mathbb{Q}$. A relation is diophantine over $\mathbb{Z}[T]$ if and only if it is recursively enumerable. Corollary (M. Boffa).
Every subset $D$ of $\mathbb{N}$ is diophantine over $R[T]$. Proof.
Let $r$ be the real number $r = \sum_{n=0}^{\infty}\frac{a_n}{10^{n+1}}$, where $a_n = 0$ for $n \in D$ and $a_n = 1$ for $n \notin D$.
Then we have
$$n \in D \leftrightarrow n \in N \land \exists p, m \in N: \left (m = 10^n \land 0 \leq mr - p < \frac{1}{10}\right )$$
But $\mathbb{Z}$ is diophantine over $R[T]$ by Proposition $1$, and every recursively enumerable relation in $\mathbb{Z}$ is diophantine over $\mathbb{Z}$. Thus, using elementary algebra, we see that $D$ is diophantine over $R[T]$.
I haven't understood the equivalence: $n \in D \leftrightarrow n \in N \land \exists p, m \in N: \left (m = 10^n \land 0 \leq mr - p < \frac{1}{10}\right )$

When $n \in D$ we have that $a_n=0$.

$r=\sum_{i=0}^{\infty}\frac{a_i}{10^{i+1}} \geq 0$ since the numeratoe is always $0$ or $1$.

We take $m=10^n$ so $mr=\sum_{i=0}^{\infty}\frac{a_i}{10^{i+1-n}}$.

Since $a_n=0$ we don't get the term $\frac{1}{10}$ at the sum.

But how do we know that there is a $p\in \mathbb{N}$ such that $mr - p < \frac{1}{10}$ ?
 
Physics news on Phys.org
I can't say I fully understand all the business about rings and so on, but with respect to the number $r$, I think it might be helpful to write it out. So we suppose $n\in D$, which means that $a_n=0$. Further, we have
$$r=0.a_1a_2a_3a_4a_5\dots a_{n-1}0a_{n+1}\dots$$
Then we have $m=10^n$. And here, I think, is the problem. If you want to guarantee $mr-p<\frac{1}{10}$, then I think it should be $m=10^{n-1}$. Because when we multiply $r$ by $m$, I get
$$mr=a_1a_2a_3\dots a_{n-1}0.a_{n+1}\dots$$
Now $p\in \mathbb{N}$, so the best you can hope for is to knock off the integer part of $mr$. On the other hand, if you had multiplied by $10^{n-1}$, you'd have gotten
$$mr=a_1a_2a_3\dots a_{n-1}.0a_{n+1}\dots,$$
and now, you see, if you subtract off $p=a_1a_2a_3\dots a_{n-1},$ you get something smaller than $1/10$.

Alternatively, if the authors meant to have $mr-p<1$, that would also be possible. But unless the authors can also control $a_{n+1}$, I'm not sure I see how they can do that.

Does this help?
 
Back
Top