6
$\begingroup$

Working in the language of ordered rings, which we take to have type $(+ - \times < 0\, 1)$, can anyone give an example of a discrete ordering on the polynomial ring in two variables $\mathbb{Z}[x,y]$ such that the resulting ordered ring does not satisfy the universal theory of the integers?

It is not difficult to show that as a ring, i.e. forgetting the less-than symbol, the ring $\mathbb{Z}[x,y]$ does in fact satisfy the universal theory of the ring of integers. The problem is to find a discrete ordering on $\mathbb{Z}[x,y]$ such that some system of inequalities is solvable in $\mathbb{Z}[x,y]$ but not in the integers, or, on the contrary, to prove that there is no such ordering.

$\endgroup$
5
  • 1
    $\begingroup$ Since I misread the question at first, let me point out two key provisions. "Universal": The sentence should be of the form $\forall x_1 x_2 x_3 \cdots : \phi(x_1, \ldots, x_n)$ where $\phi$ is a list of inequalities. If we don't have this, order $\mathbb{Z}[x]$ by leading term and consider the sentence "For all $0 < a < b$, there are $p$ and $q>0$ with $a q^2 < p^2 < b q^2$." "Discrete": If you don't have this, consider the sentence $\forall f: f^2 \geq f$ and order $\mathbb{Z}[x]$ by evaluation at $\alpha$ for some irrational $\alpha \in (0,1)$. $\endgroup$ Sep 20, 2012 at 14:55
  • $\begingroup$ @David: Yes, discreteness and universality are the key assumptions. More intuitively, the problem is whether the ring structure on Z[x,y] together with discreteness is enough to determine which systems of inequalities are and are not solvable. The axioms for discretely ordered rings are very weak, insofar as what they can prove about number theory, so it seems that the answer is likely to be "no", but I don't see any obvious examples to prove this. $\endgroup$ Sep 20, 2012 at 15:24
  • $\begingroup$ For clarification, can someone explain why some version of lexicographic order might (or might not) work? I am thinking such an order might be where any polynomial that has a monomial containing y is greater than any polynomial that has no y whatsoever. (If on the other hand, all such orders have to respect the order on Z, then I think it unlikely such an order will be found.) Gerhard "Ask Me About System Design" Paseman, 2012.09.20 $\endgroup$ Sep 20, 2012 at 16:23
  • $\begingroup$ @Gerhard: There is a unique ordering on Z[x,y] in which the element x is greater than any integer, and the element y is greater than any element of Z[x]. The resulting ordered ring is indeed discrete, but unfortunately it satisfies the universal theory of the integers, since, e.g., the ring in question can be embedded in any ultrapower of the integers. $\endgroup$ Sep 20, 2012 at 16:47
  • $\begingroup$ If all the axioms of an ordered ring are to be satisfied, then I think there are few choices, as (if I understand correctly) the basic orders that are discrete are determined by the order of x,y and the integers. So I suggest no such order exists that will not satisfy the universal theory. Gerhard "Ask Me About System Design" Paseman, 2012.09.20 $\endgroup$ Sep 20, 2012 at 19:03

1 Answer 1

4
$\begingroup$

Here is an example of a discrete ordering on $ \mathbb{Z}[x,y]$ which does not satisfy the universal theory of the ordered ring $ \mathbb{Z}$.

Let $\alpha$ be a real algebraic number of degree at least 3 over $\mathbb{Q}$. Let $e$ be any irrational between 1 and 2. Let $A$ be the ring $\mathbb{Z}[x,\alpha x+x^{-e}]$. For $f,g\in A$ define $f<g$ to mean that, regarding $f$ and $g$ as functions on the positive reals, $f(r)<g(r)$ for all sufficiently positive $r$. This makes $A$ into an ordered ring. I claim that

  1. $A$ is ring-isomorphic to $\mathbb{Z}[x,y]$.

  2. $A$ fails to satisfy the universal theory of the integers.

  3. $A$ is discretely ordered.

Proof of 1. We show that if $p(x,y)\in \mathbb{Z}[x,y]$ and $p(x,\alpha x+x^{-e})=0$, then $p$ is the zero-polynomial.

Write $p$ in the form $$\sum_n q_n(x)x^{-en},$$ where the $q_n$ are polynomials in $\mathbb{Q}(\alpha)[x]$. It follows from the irrationality of $e$ that no monomial in $q_n(x)x^{-en}$ can appear in $q_m(x)x^{-em}$ if $n\ne m$. Therefore all of the $q_n$ must be zero-polynomials, whence p=0.

Proof of 2. Fix positive integers $a$ and $b$ such that $1<a/b<\epsilon$. Roth's theorem on diophantine approximation (here) implies that there is a natural number $N$ such that the following holds for all integers $x$ and $y$: $$x>N\implies|\alpha x-y|^bx^a>1.$$

Using quantifier elimination for real closed fields and the assumption that $\alpha$ is algebraic, it is possible to construct a quantifier-free formula, call it $\phi(x,y)$, that is equivalent in any real closed field to the above inequality. (In an arbitrary real closed field $\alpha$ has the meaning of an element satisfying a certain polynomial and lying in a certain interval with rational endpoints.)

Then $$\mathbb{Z}\models \forall x,y\,\phi(x,y).$$ On the other hand, in the real closure of the ring $A$, with $u=x$ and $v=\alpha x+x^{-e}$, it is easily verified (using $1<a/b<\epsilon$) that $$u>N\textrm{ and }|\alpha u-v|^bu^a<1.$$ Since $\phi$ is is quantifier-free, it follows that $$A\models \neg\phi(u,v).$$ Therefore $A$ fails to satisfy the universal theory of $\mathbb{Z}$.

Proof of 3. We will show that A has no finite elements other than the integers. It is enough to show that if $H\in \mathbb{Z}[x,y]$ is non-constant then $H(x,\alpha x+x^{-e})$ has at least one monomial of positive degree. We shall do this first for homogeneous $H$ and then for sums of non-constant homogeneous polynomials of different degrees. Assume now that $H(x,y)$ is homogeneous of degree $n>0$. Let $$h(y)=H(1,\alpha+y).$$ Writing out the Taylor expansion for $h$ about $y=0$, $$h(y)=\sum_{k=0}^{n}\dfrac{h^{(k)}(\alpha)}{k!}y^k,$$ where $h^{(k)}$ is the $k$-th derivative of $h$. Substituting $x^{-1-e}$ for $y$, and multiplying both sides by $x^n$, we obtain \begin{equation}\tag{$*$} H(x,\alpha x+x^{-e})=\sum_{k=0}^{n}\dfrac{h^{(k)}(\alpha)}{k!}x^{n-k(1+e)}.\end{equation} The exponent $n-k(1+e)$ is positive precisely when $k=0,1,\ldots,\lfloor n/(1+e)\rfloor$. By way of contradiction, suppose that $h^{(k)}(\alpha)$ vanishes for all of these values of $k$. Let $f$ be the irreducible polynomial of $\alpha$ over $\mathbb{Q}$, and let $m$ be the degree of $f$. Then $f^{1+\lfloor n/(1+e)\rfloor{}}$ must divide $h$. Since $h$ has degree at most $n$, we find that $$\tag{$**$}m(1+\lfloor n/(1+e)\rfloor)\le n.$$ But $$n/(1+e)<1+\lfloor n/(1+e)\rfloor,$$ hence $$\tag{$***$}mn/(1+e)<m(1+\lfloor n/(1+e)\rfloor).$$ Combining the inequalities $(**)$ and $(***)$, we have $$mn/(1+e)<n,$$ hence $m<1+e$. But by assumption $e<2$. Therefore $m<3$. This contradicts the definition of $\alpha$, which is assumed to have degree $m\ge3$. This concludes the homogeneous case.

Now suppose $H\in \mathbb{Z}[x,y]$ has the form $\sum_k H_k$, where $H_k$ is homogeneous of degree $k>0$. It follows from equation ($*$) that the powers of $x$ in $H_k(x,\alpha x+x^{-e})$ all have the form $a+be$, with $a+b=k$. Since $e$ is irrational, no power of $x$ in $H_k(x,\alpha x+x^{-e})$ can appear in $H_m(x,\alpha x+x^{-e})$ if $k\ne m$. But we have shown that some positive power of $x$ appears in $H_k(x,\alpha x+x^{-e})$ for every $k>0$. This completes the proof.

$\endgroup$

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.