2
$\begingroup$

Let's say that a discretely ordered ring has rank 1 if it has elements greater than any integer, and for any two such elements $x<y$ there is an integer $n$ such that $x^n>y$.

Question: Let $f(\bar{x})$ be a polynomial in any number of variables with integer coefficients that has a zero in at least one discretely ordered ring. Must $f$ have a zero in a discretely ordered ring of rank 1?

$\endgroup$
6
  • $\begingroup$ Can you tell us what can go wrong in the subring generated by the root? $\endgroup$ Apr 23, 2013 at 16:01
  • $\begingroup$ @Joel: I'm not sure what you mean by "the root". $\bar{x}$ is a tuple of variables. I'll add that. $\endgroup$ Apr 23, 2013 at 16:10
  • $\begingroup$ Thanks, of course. The different parts of a solution $\bar x$ may be very distant from each other in that ring. $\endgroup$ Apr 23, 2013 at 16:22
  • $\begingroup$ Please humor my additional naive questions. By the usual MRDP analysis, there is a polynomial $f(x,y)$ whose "integer" solutions in any nonstandard model of PA satisfy $y=x^x$ and $x$ is the code of a proof of a contradiction (or some other thing to ensure it is infinite). So inside such a discretely ordered ring, there will be no subring of rank 1 with a solution for this polynomial. Is there any reason to think that a similar fact must be true more generally in other nonstandard discretely ordered rings? $\endgroup$ Apr 23, 2013 at 16:37
  • $\begingroup$ @Joel: The MRDP theorem is only known to be provable in $I\Delta_0+\mathit{EXP}$, not in $\mathit{PA}^-$ (i.e., in general discretely ordered rings), but I believe your suggestion is sound in principle: it’s very likely one can extract from the proof of the MRDP theorem something that is guaranteed to have superpolynomial growth in arbitrary DOR. $\endgroup$ Apr 23, 2013 at 17:20

1 Answer 1

2
$\begingroup$

The answer is no. The argument below is essentially due to Kaye [1] (Lemmas 2.1 and 5.8). Put $$p(a,x,y)=x^2-2axy+y^2-1.$$

Lemma 1: In any discretely ordered ring (DOR), if $p(a,x,y)=0$, $0< x\le y$, and $a>0$, then $y\le 2ax\le x+y$ and $p(a,2ax-y,x)=0$.

Proof: Straightforward computation.

Lemma 2: Let $n\in\mathbb N$. In any DOR, if $p(a,x,y)=0$, $0\le x\le y$, $n\le b\le a-2$, $x\equiv b\pmod{a-1}$, and $y\equiv b+1\pmod{a-1}$, then $y\ge a^n$.

Proof: By induction on $n$. For $n=1$, $y< a$ together with the congruences implies $x=b$ and $y=b+1$, whence $-p(a,x,y)=2b^2(a-1)+2ab+1>0$. Assume the statement holds for $n$, we prove it for $n+1$. The assumption $p(a,x,y)=0$ together with Lemma 1 gives $p(a,2ax-y,x)=0$, where $0\le2ax-y\le x$ and $2ax-y\equiv b-1\pmod{a-1}$. By the induction hypothesis, $x\ge a^n$, hence by Lemma 1, $y\ge(2a-1)a^n\ge a^{n+1}$.

Now, let $q(\vec w)$ be an integer polynomial that has no roots in $\mathbb Z$, but has roots in some model of, say, PA (or rather the ring obtained from a model of PA by adding a negative part). Then the polynomial $r(a,\vec w)=\bigl(a-\sum_iw_i^2\bigr)^2+q^2(\vec w)$ is also solvable in a model $M$ of PA, but any its root in a DOR must have $a$ larger than every integer. Put \begin{multline}f(a,\vec w,u_0,u_1,u_2,u_3,v_0,v_1,v_2,v_3)=\\\\ \textstyle r^2(a,\vec w)+p^2\bigl(a,(1+\sum_iu_i^2)(a-1)-1,(1+\sum_iu_i^2+\sum_iv_i^2)(a-1)\bigr).\end{multline} If we take a root of $f$ in a DOR $R$, then $a>n$ for every $n\in\mathbb N$. Putting $b=a-2$, $x=(1+\sum_iu_i^2)(a-1)-1$, $y=(1+\sum_iu_i^2+\sum_iv_i^2)(a-1)$, Lemma 2 implies that $y\ge a^n$ for every $n\in\mathbb N$, hence $R$ does not have rank 1.

On the other hand, PA (or even much weaker theories, see Lemma 2.2, 2.3 in [1]) proves that for every $a\ge b+2$ there are $x,y$ satisfying the properties in Lemma 2, and it also proves Lagrange’s four-square theorem, hence $f$ has a root in $M$.

Reference:

[1] Richard Kaye, Diophantine induction, Annals of Pure and Applied Logic 46 (1990), no. 1, pp. 1–40.

$\endgroup$
8
  • $\begingroup$ @Emil: I just found your response. Thank you very much! I'll need some time to digest this... $\endgroup$ May 6, 2013 at 9:28
  • $\begingroup$ @Emil: You "take a root of $f$ in a DOR $R$..." Why is it obvious that if $p(a,x,y):=x^2+2axy+y^2-1$ then the equation $p(a,(1+\sum_iu_i^2)(a-1)-1,(1+\sum_iu_i^2+\sum_iv_i^2)(a-1))=0$ has a solution in some DOR? $\endgroup$ May 6, 2013 at 15:45
  • $\begingroup$ I’m not sure I understand your question. We have to show that (1) $f$ has a root in some DOR, and (2) if $R$ is any DOR where $f$ has a root, then $R$ has rank more than 1. The sentence you quote comes from the proof of (2), hence you give me a DOR with the root, and I have to show that the DOR has some property. If, on the other hand, you are asking why (1) holds, this is shown in the last paragraph. If, on the third hand, you are asking why having a zero of $f$ implies having a zero of $p(a,etc.)$, every ordered domain satisfies $x^2+y^0=0\to x=0$. $\endgroup$ May 6, 2013 at 16:31
  • $\begingroup$ That should have been $x^2+y^2$, sorry for the typo. $\endgroup$ May 6, 2013 at 16:32
  • $\begingroup$ @Emil: To make your proof work, I need some DOR in which $f$ has a zero. To make this happen I must satisfy in some DOR the three equations (1) $p(a, (1+\sum_iu_i^2)(a-1)+1, (1+\sum_iu_i^2+\sum_iv_i^2)(a-1))=0$, (2) $a=\sum_iw_i^2$, and (3) $q(w)=0$. I have no problem with (2) and (3), but given solutions to (2) and (3) in some DOR, how do I know that there are $u$'s and $v$'s that will satisfy (1)? $\endgroup$ May 6, 2013 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.