MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Can you tell us what can go wrong in the subring generated by the root? – Joel David Hamkins Apr 23 '13 at 16:01
@Joel: I'm not sure what you mean by "the root". $\bar{x}$ is a tuple of variables. I'll add that. – SJR Apr 23 '13 at 16:10
Thanks, of course. The different parts of a solution $\bar x$ may be very distant from each other in that ring. – Joel David Hamkins Apr 23 '13 at 16:22
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? – Joel David Hamkins Apr 23 '13 at 16:37
@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. – Emil Jeřábek Apr 23 '13 at 17:20
up vote 2 down vote accepted

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


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

share|cite|improve this answer
@Emil: I just found your response. Thank you very much! I'll need some time to digest this... – SJR May 6 '13 at 9:28
@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? – SJR May 6 '13 at 15:45
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$. – Emil Jeřábek May 6 '13 at 16:31
That should have been $x^2+y^2$, sorry for the typo. – Emil Jeřábek May 6 '13 at 16:32
@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)? – SJR May 6 '13 at 17:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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