MAS400: Solutions 1

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

1. For the following pairs of elements f, g ∈ F [x] find the g.c.d. (h say) of f and g and also find elements a, b ∈ F [x] such that af + bg = h. (You should normalise h so that its leading coefficient is 1.)

(a) f = x^{2} − 2x + 1 and g = x^{3} + 3x^{2} − 7x + 3.

(b) f = x^{3} + 1 and g = x^{4} + 5x^{3} + 3x^{2} − 2x − 1.

(c) f = x^{3} − 2 and g = 2x^{2} + 3x − 1.

(d) f = x^{2} + 5x + 4 and g = 3x^{2} − 2x + 1.

[You may assume that F has characteristic 0, say F = ℚ. It is also interesting to see what divergence we get from the general case when we set F = 𝔽_{p} for p a prime.]

The g.c.d. algorithm works with a particular field, not an arbitrary field. First, we will carry out the algorithm when F = ℚ (the workings will be identical over any field of characteristic 0). The answers are as follows.

(a) h = x − 1, a = (−x − 5)/2, b = 1/2. Valid for all fields not of characteristic 2.

(b) h = x + 1, a = (x^{2} + 6x + 8)/9, b = (−x − 1)/9. Valid for all fields not of characteristic 3.

(c) h = 1, a = (−2x − 5)/11, b = (x^{2} + x − 1)/11. Valid for all fields not of characteristic 11.

(d) h = 1, a = (−51x + 67)/342, b = (17x + 74)/342. Valid for all fields not of characteristics 2, 3, 19.

2. Show that the ideal of I = ⟨x, y⟩ of F [x, y] cannot be generated by a single element.

The ideal I consists of all polynomials with zero constant term. We let J = ⟨x^{2}, xy, y^{2}⟩. Thus J consists of those polynomials that have zero coefficients for the monomials 1 = x^{0}y^{0}, x = x^{1}y^{0} and y = x^{0}y^{1}. Observe that whenever q = q(x, y) ∈ I we have xq, yq ∈ J. Suppose that there is a g ∈ F [x] such that I = ⟨g⟩. Then g ∈ I, so that g = αx + βy + j where α, β ∈ F and j ∈ J. Take p ∈ F [x]. Then p = γ + q where γ ∈ F and q ∈ I. So gp = αγx + βγy + h where h = αxq + βyq + jp ∈ J. Since x, y ∈ I there exist p_{1}, p_{2} ∈ R such that gp_{1} = x and gp_{2} = y. We can choose notation such that for i = 1, 2 we have γ_{i} ∈ F and p_{i} − γ_{i} ∈ I, giving gp_{i} = αγ_{i}x + βγ_{i}y + h_{i} for some h_{i} ∈ J. But then (αγ_{1}, βγ_{1}) = (1, 0) and (αγ_{2}, βγ_{2}) = (0, 1). The former equation gives α ≠ 0, β = 0, while the latter gives α = 0, β ≠ 0, a contradiction. Thus I cannot be singly generated.

3. For n ⩾ 2 show that the ideal of I = ⟨x_{1}, x_{2}, …, x_{n}⟩ of F [x_{1}, x_{2}, …, x_{n}] cannot be generated by a single element. What is the minimum number of elements required to generate I? Justify your answer.

We require a minimum of n generators, for example x_{1}, x_{2}, …, x_{n}; n−1 elements cannot generate I. The ideal I consists of all polynomials with zero constant term. We let J = ⟨ x_{i}^{2}, x_{i}x_{j} : 1 ⩽ i, j ⩽ n ⟩. (In fact J = I^{2} = II.) Thus J consists of those polynomials that have zero coefficients for the monomials 1, x_{1}, x_{2}, …, x_{n}.

Now the typical element of I has the form f = λ_{1}x_{1}+⋯+λ_{n}x_{n}+g where g ∈ J and λ_{i} ∈ F for all i, and the typical element of F [x_{1}, x_{2}, …, x_{n}] is p = κ + q where q ∈ I and κ ∈ F. We have qf ∈ J, and thus pf = κ(λ_{1}x_{1} + ⋯ + λ_{n}x_{n}) + h where h = qf + κg ∈ J. Let f_{i} = λ_{i1}x_{1} + ⋯ + λ_{in}x_{n} + g_{i} where g_{i} ∈ J and λ_{ij} ∈ F for all i and j. If p_{i} ∈ F [x_{1}, x_{2}, …, x_{n}] we shall define κ_{i} and q_{i} by p_{i} = κ_{i} + q_{i} where κ_{i} ∈ F and q_{i} ∈ I.

If we identify f = λ_{1}x_{1}+⋯+λ_{n}x_{n}+g with the vector v = (λ_{1}, …, λ_{n}) ∈ F^{n} then this forces f_{i} to be identified with v_{i} = (λ_{i1}, …, λ_{in}). (The mapping from I to F^{n} is well-defined since f ∈ I has a unique expression in the form f = λ_{1}x_{1} + ⋯ + λ_{n}x_{n} + g where g ∈ J and λ_{i} ∈ F.) Anyway, the p_{1}f_{1} + ⋯ + p_{m}f_{m} gets mapped to κ_{1}v_{1} + ⋯ κ_{m}v_{m} ∈ F^{n}. The v_{i} are constant vectors (depending on f_{i}) in F^{n}, and since all spanning sets of F^{n} require at least n vectors it follows that I also requires at least n generators.

4. Let n, m ∈ ℕ, with n ⩾ 1. How many n-tuples (a_{1}, …, a_{n}) ∈ ℕ^{n} are there such that ∑_{i=1}^{n} a_{i} = m?

This is a standard combinatorial trick. We make a one-to-one correspondence between such n-tuples and certain ways of placing n + 1 crosses into a line m + n + 1 boxes, with just one cross per box and the rest of the boxes being left blank. The crosses are labelled as the 0th cross up to the nth cross, with the 0th cross being placed in the leftmost box, the nth cross being placed in the rightmost box, and the ith cross being placed in a box strictly to the left of the jth cross whenever i < j. The placement corresponding to the n-tuple (a_{1}, …, a_{n}) has a_{i} blank boxes between the ith cross and the (i + 1)th cross. Of course, it is also possible to determine the n-tuple (a_{1}, …, a_{n}) from the valid placement of n + 1 crosses into a line of m + n + 1 boxes. So we have a 1-to-1 correspondence between n-tuples and valid placements.

Now the first and last boxes contain crosses, but any distribution of the remaiming n − 1 crosses among the remaining m + n − 1 boxes is possible. There are \binom{m+n−1}{n−1} = \binom{m+n−1}{m} such distributions, and therefore \binom{m+n−1}{n−1} = \binom{m+n−1}{m} such n-tuples.