MAS400: Solutions 2

Throughout this sheet F will denote an arbitrary field unless otherwise stated.

1. Show that ℤ[x] has ideals that are not generated by a single element. Thus ℤ[x] is not a principal ideal domain, even though it is a unique factorisation domain.

An example of a non-principal ideal of ℤ[x] is I = ⟨2, x⟩. More generally, the ideal ⟨n, x⟩ is non-principal for all n ∈ ℤ \ {−1, 0, 1}. The ideal I consists of all polynomials 2p(x)+xq(x), where p, q ∈ ℤ[x]. The polynomial 2p(x) has all of its coefficients being even integers, while xq(x) has zero constant term. Therefore the typical element of I is a polynomial f(x) = ∑_{i=1}^{n} a_{i}x^{i} where a_{i} ∈ ℤ for all i and a_{0} is even. Suppose that I is principal, that is I = ⟨g⟩ for some polynomial g. Then the typical member of I is gh for some h ∈ ℤ[x]. If g = 0 then I = {0}, a contradiction. If deg g ⩾ 1 then gh = 0 (when h = 0) or deg(gh) ⩾ deg g ⩾ 1, so that gh ≠ 2, also a contradiction. Therefore deg g = 0 and g = m ∈ ℤ \ {0} is a non-zero constant, and so all coefficients of gh are integers divisible by m. Since x ∈ I, we need m | 1 (in ℤ), forcing m = 1 or −1. But 1, −1 ∉ I, a contradiction that (finally) shows that I is non-principal. The non-principality of ⟨n, x⟩ for n ∉ {−1, 0, 1} is proved similarly.

2. Write, using pseudo-code, the univariate division algorithm (that is the algorithm that given f, g ∈ F [x] with g ≠ 0 will return q, r ∈ F [x] such that f = qg + r and deg r < deg g).

See separate sheet of algorithms. Version II of UnivariateDivision is effectively a specialisation of MultivariateDivision, while Version I (probably ‘better’) is somewhat closer to one’s idea of what long division does.

3. Rewrite the Euclidean Algorithm so that only a bounded number of variables is used. (These variables should be elements of F [x], and not such things as an arbitrarily long sequence of elements of F [x].)

See separate sheet of algorithms. Version I is essentially as given in lectures. The crucial observation is that it is unnecessary to store p_{0}, p_{1}, …, p_{p−1} once we know p_{j} and p_{j+1}. Therefore we only need p_{0}, p_{1},p_{2}, and we overwrite unneeded variables as appropriate. Similarly for the a_{j} and b_{j}. The q_{j} do not depend on their predecessors, and these can simply be replaced by q. See Version II of the algorithm.

4. Show that the only monomial order on ℕ is x^{0} < x^{1} < x^{2} < ⋯ < x^{i} < x^{i+1} < · · ·.

Note the monomial x^{i} corresponds to i ∈ ℕ and (i) ∈ ℕ^{1}. In lectures we showed that 0 < a for all non-zero a ∈ ℕ^{n} whenever < is a monomial order. So let < be a monomial order on ℕ. We certainly have 0 < 1, and thus also m < m + 1 for all m ∈ ℕ. So we have 0 < 1, 1 < 2, 2 < 3, 3 < 4, and so on. The transitivity of < then ensures that < is the usual order on ℕ.

5. Show that a totally ordered set is well ordered if and only if it has no infinite descending chains.

Let S be a totally ordered set. If S contains an infinite (strictly) descending chain, say

s_{0} > s_{1} > ⋯ > s_{i} > s_{i+1} > ⋯

then {s_{0}, s_{1}, s_{2}, …} has no minimal element, and so S is not wellordered. Conversely, suppose that S has no infinite descending chain. Let T be a subset of S with no minimal element, so that for all t ∈ T there exists u ∈ T such that t > u (recall that S is totally ordered). But then we can form an infinite descending chain t_{0} > t_{1} > t_{2} > ⋯ where for all i we have t_{i} ∈ T and t_{i+1} ∈ T is chosen to be strictly less than t_{i}. This contradiction establishes the result.

6. Any exercises that may be embedded in my lecture notes.

Exercise for the reader. This also applies to (most) future exercises I may set in this way.