Definition and basic properties of k-stage Euclidean domains

Let R be an integral domain and let N : R \rightarrow \mathbb{N} be a bounded divisibility norm. (That is, N(ab) = N(a)N(b), N(0) = 0 and N(1) = 1.) We say that R is 2-stage Euclidean with respect to N if for all a,b \in R with b \neq 0, there exist q_1,q_2,r_1,r_2 \in R such that a = q_1b + r_1, b = q_2r_1 + r_2, and either r_2 = 0 or N(r_2) < N(b).

Generalize this definition to “k-stage Euclidean domains” and prove the following.

  1. For all a,b in a k-stage Euclidean domain with b \neq 0, then a and b have a greatest common divisor which is a linear combination of a and b. Conclude that every finitely generated ideal of R is principal.
  2. Prove that if R is a k-stage Euclidean domain in which every nonzero nonunit is a finite product of irreducibles, then R is a unique factorization domain.

We begin with a definition.

Let R be an integral domain. Let \mathcal{A}(R) = \{ (\lambda,\theta) \ |\ \lambda,\theta : \mathbb{N} \rightarrow R, \lambda_k = \theta_k \lambda_{k+1} + \lambda_{k+2}\ \mathrm{for\ all}\ k \}. We will call elements of \mathcal{A}(R) division sequences in R. A division sequence (\lambda,\theta) is said to terminate if \lambda_k = 0 for some k. Next we prove some basic properties of division sequences.

Lemma: Let R be an integral domain and let (\lambda,\theta) \in \mathcal{A}(R).

  1. \lambda_{k+2} \in (\lambda_k, \lambda_{k+1}) for all k.
  2. (\lambda_{k+1},\lambda_{k+2}) \subseteq (\lambda_k,\lambda_{k+1}) for all k.
  3. \lambda_k \in (\lambda_0,\lambda_1) for all k.
  4. If q|\lambda_{k+1} and q|\lambda_{k+2}, then q|\lambda_k for all k.
  5. If \lambda_{k+2} = 0, then \lambda_{k+1}|\lambda_k for all k.
  6. If (\lambda,\theta) terminates, then \lambda_0 and \lambda_1 have a greatest common divisor, which is contained in (\lambda_0,\lambda_1).

Proof:

  1. We have \lambda_{k+2} = \lambda_k - \theta_k\lambda_{k+1}.
  2. (\lambda_{k+1},\lambda_{k+2}) \subseteq (\lambda_{k+1}, \lambda_k, \lambda_{k+1}) = (\lambda_k,\lambda_{k+1}).
  3. Certainly \lambda_0,\lambda_1 \in (\lambda_0,\lambda_1). Then \lambda_{k+2} \in (\lambda_k,\lambda_{k+1}) \subseteq (\lambda_0,\lambda_1).
  4. Follows since \lambda_k = \theta_k\lambda_{k+1} + \lambda_{k+2}.
  5. Follows since \lambda_k = \theta_k\lambda_{k+1}.
  6. Let t be minimal such that \lambda_{t+1} = 0. If t = 0, then \lambda_1 = 0 so that \lambda_0 is a greatest common divisor of \lambda_0 and \lambda_1, and certainly \lambda_0 \in (\lambda_0,\lambda_1). If t \geq 1, then \lambda_t|\lambda_{t-1} by (5). Since \lambda_t|\lambda_t, using (4) and induction, \lambda_t|\lambda_k for all 0 \leq k \leq t. In particular, \lambda_t|\lambda_0 and \lambda_t|\lambda_1. By (3), (\lambda_t) = (\lambda_0,\lambda_1). If q|\lambda_0 and q|\lambda_1, then (\lambda_t) = (\lambda_0,\lambda_1) \subseteq (q), so that q|\lambda_t. So \lambda_t is a greatest common divisor of \lambda_0 and \lambda_1.

Evidently, then, if a,b \in R with b \neq 0 and there exists a terminating division sequence (\lambda,\theta) such that \lambda_0 = a and \lambda_1 = b, then (a,b) is principal; that is, a and b have a greatest common divisor which is a linear combination of a and b. We are now in a position to define k-stage Euiclidean domains.

Let R be an integral domain and let N : R \rightarrow \mathbb{N} be a divisibility norm. We say that R is k-stage Euclidean with respect to N if for all a,b \in R such that b \neq 0, there exists a division sequence (\lambda,\theta) \in \mathcal{A}(R) such that \lambda_0 = a, \lambda_1 = b, and either \lambda_{k+1} = 0 or N(\lambda_{k+1}) < N(b).

The significance of the k-stage condition is that it allows us to patch together a terminating division sequence for all pairs of elements, and moreover to give an upper bound on its length.

Let R be a k-stage Euclidean domain with respect to N and let a,b \in R with b \neq 0. We claim that there is a terminating division sequence whose first two terms are a and b; we proceed by induction on N(b). Let b \in R be nonzero and of minimal norm. By the k-stage condition, there is a division sequence (\lambda,\theta) such that \lambda_0 = a, \lambda_1 = b, and \lambda_{k+1} = 0 or N(\lambda_{k+1}) < N(b). Since b has minimal norm, \lambda_{k+1} = 0, and thus (\lambda,\theta) terminates. Suppose that for some k \in \mathbb{N}, for all a and b such that b \neq 0 and N(b) \leq k, there is a terminating division sequence whose first two terms are a and b. Let b be nonzero and of minimal norm greater than k. We have (\lambda,\theta) such that \lambda_0 = a, \lambda_1 = b, and either \lambda_{k+1} = 0 or N(\lambda_{k+1}) < N(b). If \lambda_{k+1} = 0, then (\lambda,\theta) terminates. If N(\lambda_{k+1}) < N(b), then by the induction hypothesis there is a terminating division sequence (\lambda^\prime,\theta^\prime) such that \lambda^\prime_0 = \lambda_k and \lambda^\prime_1 = \lambda_{k+1}. Then (\lambda^{\prime\prime},\theta^{\prime\prime}) defined by \lambda^{\prime\prime}_i = \lambda_i if i < k and \lambda^\prime_{i-k} otherwise and \theta^{\prime\prime}_i = \theta_i if i < k and \theta^\prime_{i-k} otherwise is a terminating division sequence whose first two terms are a and b.

Thus every pair of elements in a k-stage Euclidean domain are the first two terms of a terminating division sequence, and thus have a greatest common divisor which is contained in (a,b). By an easy induction argument, every finitely generated ideal is principal.

Suppose now that R is k-stage Euclidean with respect to N and that every nonzero nonunit in R is a finite product of irreducibles.

First we will show that every irreducible in R is prime. To that end, let x \in R be irreducible and suppose x|ab. Consider the ideal (a,x); by the previous discussion, (a,x) = (d) is principal, and so x = du for some u. Since x is irreducible, either u is a unit, so that (a,x) = (x) and x|a, or d is a unit and (a,x) = (1). Then as + xt = 1 for some s,t \in R. Multiplying by b, we have abs + bxt = b; since x|ab, we have x|b. Thus x is prime.

Now we show that if a \in R is a nonzero nonunit, then any to factorizations of a have the same length and are unique up to units. We proceed by induction on the length of the shortest factorization. For the base case, suppose a = x = \prod_{i=1}^n y_i, where x and the y_i are irreducible. Since x is prime, then (reordering if necessary) we have x|y_1; since y_1 is irreducible, y_1 = ux for some unit u. Then x = xu\prod_{i=2}^n y_i. Since R is a domain, u\prod_{i=2}^n y_i = 1. In particular, y_i is a unit for each 2 \leq i \leq n, a contradiction, so that in fact n = 1. Thus a = y_1u^{-1} = x; so if a has an irreducible factorization of length 1, then all factorizations have length 1 and are unique up to units. For the inductive step, suppose that for some k, every nonzero nonunit which has an irreducible factorization of length k has an essentially unique factorization. Let a be a nonzero nonunit with a factorization of length k+1, say a = \prod_{i=1}^{k+1}x_i. Suppose a = \prod_{i=1}^n y_i is another irreducible factorization, with n \geq k+1. Since x_1 is prime, then without loss of generality x_1 divides y_1. Since y_1 is irreducible, x_1u = y_1 for some unit u. From \prod_{i=1}^{k+1} x_i = \prod_{i=1}^n y_i = x_1u\prod_{i=1}^n y_i, we have \prod_{i=2}^{k+1} x_i = u\prod_{i=2}^n y_i. By the induction hypothesis, n = k+1 and the x_i and y_i are pairwise associates. Thus all factorizations of a have length k+1 and (up to a reordering) the irreducible factors are associates.

Thus if every nonzero nonunit has a factorization into irreducibles, then every element has an essentially unique factorization. Thus R is a unique factorization domain.

As a side note, the significance of the k-stage Euclidean condition is that it guarantees the existence of a terminating division sequence and gives an upper bound on its length. We could weaken this condition as follows: say an integral domain R with divisibility norm N is finite stage Euclidean if for all a,b \in R with b \neq 0, there exists an integer k and a division sequence (\lambda,\theta) such that \lambda_0 = a, \lambda_1 = b, and \lambda_{k+1} = 0 or N(\lambda_{k+1}) < N(b). (That is, for all pairs, some finite number of divisions yields a remainder of smaller norm than b. We still have that a terminating sequence exists for all a,b, but now there is no upper bound on how long such a sequence might be.

About these ads
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 207 other followers

%d bloggers like this: