TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 00, Number 0, Pages 000–000 S 0002-9947(XX)0000-0

ZERO SETS OF UNIVARIATE POLYNOMIALS

ROBERT S. LUBARSKY AND FRED RICHMAN

Abstract. Let L be the zero set of a nonconstant monic polynomial with complex coefficients. In the context of constructive mathematics without countable choice, it may not be possible to construct an element of L. In this paper we introduce a notion of distance from a point to a subset, more general than the usual one, that allows us to measure distances to subsets like L. To verify the correctness of this notion, we show that the zero set of a polynomial cannot be empty—a weak fundamental theorem of algebra. We also show that the zero sets of two polynomials are a positive distance from each other if and only if the polynomials are comaximal. Finally, the zero set of a polynomial is used to construct a separable Riesz space, in which every element is normable, that has no Riesz homomorphism into the real numbers.

1. Quasidistance

Let T be a set of real numbers. A lower bound for T is a real number b such that b ≤ t for all t in T. By the infimum of T we mean, as usual, a lower bound inf T for T such that if inf T < r, then there exists t ∈ T such that t < r. The number sup T is defined dually. By the greatest lower bound of T we mean the largest element, glb T, of the set B of lower bounds of T. As the distinction between inf T and glb T in constructive mathematics is central to this section, we pause to illustrate this difference.

Example 1.1. Let P be an arbitrary proposition and let

L = {0 : P or ¬P } ∪ {1} .

Then the set B of lower bounds of L is (−∞, 0]. Thus glb L = 0, but if inf L exists, then P or ¬P.

Proof. Elements of (−∞, 0] are certainly lower bounds of L. Conversely, if b > 0, then b cannot be a lower bound of L, because if 0 were not in L, then P would have to be false, so ¬P would be true, so 0 would be in L. So elements of B cannot be (strictly) positive, whence they are in (−∞, 0].

Finally, if m = inf L, then m ≤ 0 so 1 > m whence there exists r < 1 in L. From this P or ¬P follows. □

So the notions of infimum and greatest lower bound are the same only in the presence of the law of excluded middle. The relations that hold between the two notions are stated in the following theorem.

\begin{matrix}c \\ ◯ \end{matrix}XXXX American Mathematical Society

2000 Mathematics Subject Classification. Primary 03F65, 13A99.

Theorem 1.2. Let T be a set of real numbers that is bounded below, and B the set of lower bounds for T. If sup B exists, then glb T = sup B. If inf T exists, then glb T = inf T.

Proof. Suppose sup B exists. We must show that it is in B, that is, that t ≥ sup B for all t in T. But t ≥ b for each b in B, so t ≥ sup B. (If t < sup B, then there would be b ∈ B such that t < b.)

Suppose inf T exists. We must show that it is the maximum element of B. It is in B by definition. If b ∈ B and b > inf T, then there exists t in T such that t < b, a contradiction, so b ≤ inf T. □

The usual informal description of a located subset L of a metric space M is that we can compute the distance from any point in M to L. This is slightly misleading because the rules for computing the distance are not explicitly stated. It is not enough to be able to compute the distance from x to L, we must compute the infimum

inf_{y∈L} d (x, y)

Thus there are some implied constructions of elements of L hidden in that statement about computing distances. That is not the case for the greatest lower bound

glb_{y∈L} d (x, y)

which is also a candidate for the distance from x to L.

To illustrate this distinction, let M be the real line and L the subset of Example 1.1. The subset L contains an element, is closed, and glb_{y∈L} d (−1, y) = 1+glb L = 1. However, inf_{y∈L} d (−1, y) = 1 + inf L, but L does not have an infimum.

If L is a subset of a metric space M, and x is a point in M, then the distance from x to L is

d (x, L) = inf_{y∈L} d (x, y)

We define the quasidistance from x to L to be

δ (x, L) = glb_{y∈L} d (x, y)

We say that L is located if d (x, L) exists for each x in M, and that L is quasilocated if δ (x, L) exists for each x in M. It follows from Theorem 1.2 that a located set L is quasilocated with δ (x, L) = d (x, L) for all x. Note that a quasilocated set cannot be empty.

Theorem 1.3. If L is a quasilocated subset of a metric space M, then δ (x, L) ≤ δ (y, L) + d (x, y) for all x and y in M. It follows that |δ (x, L) − δ (y, L)| ≤ d (x, y) so δ (x, L) is a uniformly continuous function of x.

Proof. It suffices to show that δ (x, L) − d (x, y) ≤ d (y, t) for all t ∈ L. But d (x, t) ≤ d (x, y) + d (y, t), and δ (x, L) ≤ d (x, t). □

If we think of δ (x, L) as a lowercut (a supremum of a bounded set of real numbers), see [4], then the inequality δ (x, L) ≤ δ (y, L) + d (x, y) holds for an arbitrary subset L of M.

The quasidistance can be thought of as dual to the distance. That’s because we can express the distance from x to L as

d (x, L) = inf {d (x, t) : t ∈ L} = inf {r : d (x, t) ≤ r for some t in L}

while the quasidistance is

δ (x, L) = sup {r : d (x, t) ≥ r for all t in L}

Throughout, we will use B_{r} (x) to denote the open ball of radius r centered at x.

Lemma 1.4. Let L be a subset of a metric space M and x ∈ M. Then r is a lower bound for {d (x, y) : y ∈ L} if and only if B_{r} (x) ∩ L = ∅.

Proof. Consider the statement P that there exists y ∈ L such that d (x, y) < r. Then ¬P says d (x, y) ≥ r for all y ∈ L, that is, that r is a lower bound for {d (x, y) : y ∈ L}. On the other hand, ¬P says that B_{r} (x) ∩ L = ∅. □

Theorem 1.5. If δ (x, L) exists, then δ (x, L) ≤ r if and only if B_{s} (x) ∩ L cannot be empty for any s > r.

Proof. Suppose δ (x, L) = glb_{y∈L} d (x, y) ≤ r. If B_{s} (x) ∩ L were empty for s > r, then s would be a lower bound for {d (x, y) : y ∈ L}, a contradiction. Conversely, suppose B_{s} (x) ∩ L cannot be empty for any s > r. If δ (x, L) > r, then B_{s} (x) ∩ L is empty for s = (δ (x, L) + r) /2, a contradiction. □

We really aren’t particularly interested in Example 1.1. What motivated these ideas was the study, in a choiceless environment, of the set L of roots of a monic polynomial p with complex coefficients. If the coefficients of p are complex numbers over the Cauchy reals, then we can write p (X) = (X − r_{1}) ⋯ (X − r_{n}), see [5], and L is the closure of the set {r_{1}, …, r_{n}}, so L is easily seen to be located. However, if the coefficients are arbitrary complex numbers, then we need not be able to construct a root of p, see [3], even if p is of the form X^{2} − a, so we can’t show that L is located. However, L is always quasilocated, as we will see (Corollary 4.6).

In the presence of choice, at least in complete spaces M where balls are totally bounded (such as Euclidean spaces), quasilocated zero sets are located. To see that some hypothesis on M is necessary to get this conclusion, take L as in Example 1.1, and M = {−1} ∪ L. Then L is the zero set of the function x (x − 1) on M.

Theorem 1.6. Let M be a complete space in which balls are totally bounded. Assuming the axiom of dependent choices, quasilocated zero sets of uniformly continuous functions on M are located.

Proof. Suppose L is a quasilocated subset of M and x ∈ M. We will show that if δ (x, L) < r, and ε > 0, then there exists t ∈ L such that d (x, t) ≤ r + ε. The proof is reminiscent of the proof of the Baire category theorem. First we construct an element y_{1} ∈ B_{r} (x) such that δ (y_{1}, L) < ε/2. This is possible because the function δ (z, L) is uniformly continuous, so has an infimum m as z ranges over B_{r} (x). Either m > 0 or m < ε/2. But if m > 0, then δ (x, L) ≥ r, so m < ε/2.

Similarly we construct an element y_{2} ∈ B_{ε/2} (y_{1}) such that δ (y_{2}, L) < ε/4. Then an element y_{3} ∈ B_{ε/4} (y_{2}) such that δ (y_{3}, L) < ε/8. In general, we construct y_{n+1} ∈ B_{ε/2^{n}} (y_{n}) such that δ (y_{n+1}, L) < ε/2^{n+1}. Dependent choice allows us to form a sequence y_{1}, y_{2}, … with those properties.

Because y_{n+1} ∈ B_{ε/2^{n}} (y_{n}), the sequence of y’s is a Cauchy sequence, hence converges to a point t in M. As δ (y_{n}, L) converges to zero, δ (t, L) = 0. As L is a zero set of a uniformly continuous function, t ∈ L. Finally d (x, y_{n}) < r + ε for all n, so d (x, t) ≤ r + ε. □

With a little work, the proof of this theorem can be modified to apply to any locally compact space M.

In Example 1.1, the quasidistance from the point 0 to the closed set L is equal to zero but 0 need not be in L. That can’t happen if L is the zero set of a continuous function. We write this as a lemma for later use.

Lemma 1.7. Let f be a continuous function that vanishes on L. If δ (x, L) = 0, then f (x) = 0.

Proof. It’s enough to show that f (x) cannot be different from 0. Suppose |f (x)| = ε > 0. As f is continuous at x, there is θ > 0 such that f is nonzero in B_{θ} (x). Lemma 1.4 then tells us that δ (x, L) ≥ θ, a contradiction. □

2. Quasifinite sets

Even with choice, the zero set of a monic polynomial need not be finite or even finitely enumerable. For example, let a and b are two real numbers and consider the polynomial p (X) = (X − a) (X − b). In addition to the roots a and b, the numbers a ∨ b and a ∧ b are roots, and the ability to equate a ∨ b with either a or b is a form of LLPO. What we can say is that the zero set of p (X) is the closure of the set {a, b}. So what we are thinking of here, in the presence of choice, are closures of finitely enumerable sets.

What are we thinking of in the absence of choice? The example to keep in mind is the zero set L of the polynomial X^{2} − a where a is a small complex number, possibly zero. Unless there is a sequence of Gaussian numbers converging to a, see [5], we cannot necessarily construct an element of L, see [3]. But L is quasilocated, as we shall see. First a little terminology.

An ε-quasiapproximation to a subset L of a metric space M is a sequence x_{1}, …, x_{n} in M such that B_{ε} (x_{i}) ∩ L cannot be empty for i = 1, …, n, and L ⊂ B_{ε} (x_{1}) ∪ ⋯ ∪ B_{ε} (x_{n}). We say that L is quasi-totally-bounded if for each ε > 0 we can find an ε-quasiapproximation to L. Unlike the notion of totally bounded, this depends on the ambient space M because we cannot assume that the ε-quasi-approximation lies in L. The subset L in Example 1.1 is quasi-totally-bounded but we can’t find an internal 1-quasiapproximation to it.

Theorem 2.1. Each quasi-totally-bounded subset of a metric space M is quasilocated.

Proof. Let L be a quasi-totally-bounded subset of M. For any ε > 0, let x_{1}, …, x_{n} be an ε-quasiapproximation to L. First we show, for each z in M, that r = d (z, {x_{1}, …, x_{n}}) − ε is a lower bound for T = {d (z, y) : y ∈ L}. Given y in L there is i such that d (x_{i}, y) < ε, so d (z, x_{i}) ≤ d (z, y) + d (y, x_{i}) < d (z, y) + ε. Thus

r + ε ≤ d (z, x_{i}) < d (z, y) + ε

so r < d (z, y). Next we show that r + 3ε is not a lower bound for T. We know that d (z, x_{i}) < r + 2ε for some i, so B_{ε} (x_{i}) ⊂ B_{r+3ε} (z). We also know that B_{ε} (x_{i}) ∩ L cannot be empty, so B_{r+3ε} (z) ∩ L cannot be empty, whence r + 3ε is not a lower bound for T. Thus we can approximate δ (z, L) within 3ε/2. □

We say that L is a quasi-n-set if for each ε > 0 there is an ε-quasiapproximation to L of length n. Note that a singleton is a quasi-n-set for every positive n, so n is just an upper bound on the size of L rather than its size. We say that L is quasifinite if it is a quasi-n-set for some n. Clearly a quasifinite set is quasitotally-bounded.

The meaning of δ (x, L) < t, when δ (x, L) does not necessarily exist, follows from the general theory of lowercuts. It is the second condition in the following lemma.

Lemma 2.2. If δ (x, L) exists, then δ (x, L) < t if and only if B_{r} (x) ∩ L cannot be empty for some r < t.

Proof. We know that r ≤ δ (x, L) if and only if B_{r} (x)∩L is empty (Lemma 1.4), so if δ (x, L) < t, then B_{r} (x)∩L cannot be empty for r = (δ (x, L) + t) /2. Conversely, if B_{r} (x) ∩ L cannot be empty for some r < t, then r ≤ δ (x, L) is impossible, so δ (x, L) < t. □

We will show, in Corollary 4.6, that the zero set of a monic polynomial is quasifinite.

3. The spectrum of a polynomial

Let f be a monic polynomial of degree n ≥ 1 with complex coefficients. We can approximate f arbitrarily closely with polynomials of the form

(X − q_{1}) (X − q_{2}) ⋯ (X − q_{n})

where the q_{i} are Gaussian numbers. The spectrum of f, written spec f, is an element of the completion of the set of n-multisets of Gaussian numbers in an appropriate metric, see [3]. Classically, spec f can be identified with the multiset of roots of f. Constructively, with choice, spec f can be identified with an equivalence class of multisets r_{1}, …, r_{n} where two multisets are equivalent if ∏_{i=1}^{n} (X − r_{i}) = ∏_{i=1}^{n} (X − r′_{i}).

The choiceless fundamental theorem of algebra says that the function spec is a homeomorphism from the space of monic polynomials of degree n, with the natural metric, to the completion of the set of n-multisets of Gaussian numbers.

The distance, d (z, spec f), from a complex number z to spec f is approximated by the distance from z to the approximating multisets {q_{1}, q_{2}, …, q_{n}}. Note that d (z, spec f) is independent of multiplicities. It is not hard to show that d (z, spec f) = 0 if and only if f (z) = 0. That is the connection between spec f and the zero set of f.

The diameter of spec f is the limit of the the diameters of its approximating n-multisets. Caution: this need not be a limit of a sequence of approximating nmultisets—we are operating in the absence of countable choice. The diameter can be characterized in terms of d (z, spec f) as

inf_{ε>0} sup {|z − z′| : d (z, spec f) < ε and d (z′, spec f) < ε}

The (set-)distance between spec f and spec g is defined to be the infimum over all z of

d (z, spec f) + d (z, spec g) .

It is not hard to see that this infimum exists, and is equal to the limit of the distance between the approximations to spec f and spec g. This is like the distance between two sets of complex numbers. It is not a metric and should not be confused with the metric distance between the spectra of two monic polynomials of the same degree that comes from their both being in the completion of the set of n-multisets of Gaussian numbers.

We will need this lemma.

Lemma 3.1. Let f be a monic polynomial of degree n ≥ 1 with complex coefficients. If the diameter of spec f is positive, then f = gh for nonconstant polynomials g and h. Moreover, the distance between spec g and spec h is positive.

Proof. Let d be the diameter of spec f and let r be a rational number such that d ≥ r > 0. Let q_{1}, …, q_{n} be Gaussian numbers that approximate the spectrum of f to within r/ (8n). The transitive closure of the relation |x − y| ≤ r/ (2n) partitions the q_{i} into at least two equivalence classes (thought of as multisets). Let G_{0} be one of them and H_{0} the union of all the rest. The minimum distance ε between a point in G_{0} and a point in H_{0} is greater than r/ (2n).

Let m be the number of elements of G_{0}, including multiplicities. Any multiset of Gaussian numbers that approximates the spectrum of f to within r/ (8n) is uniquely the union of an m-multiset G and an (m − n)-multiset H, where G is within r/ (4n) of G_{0}, as m-multisets, and H is within r/ (4n)of H_{0}. So the distance between any point in G and any point in H is at least ε − r/ (2n). Let g and h be the monic polynomials whose spectra are the limits of the multisets G and H respectively. That is, g is the limit of the polynomials Π_{s∈G} (X − s). The distance between spec g and spec h is at least ε − r/ (2n). □

Any easy induction gives us the theorem.

Theorem 3.2. Let f be a monic polynomial of degree n ≥ 1 with complex coefficients. For each ε > 0 we can write f = g_{1}g_{2} ⋯ g_{k} where the diameter of each spec g_{i} is less than ε and the spec g_{i} are a positive distance from each other.

Proof. If the diameter d of spec f is less than ε, then let k = 1 and g_{1} = f. Otherwise d > 0 and from Lemma 3.1 we can write f = gh for nonconstant polynomials g and h. By induction on degree we can write g and h in the desired form. Clearly the spectrum of any factor of g is a positive distance from the spectrum of any factor of h. □

4. Weak fundamental theorem of algebra

We want to show that the zero set L of a monic polynomial p is quasilocated. We know that the quasidistance from z to L has to be r = d (z, spec p). But to prove that, we must show that it is impossible for B_{r+ε} (z) ∩ L to be empty for ε > 0 (Lemma 1.4). In particular, we must show that it is impossible for the zero set of a monic polynomial of degree at least 1 over the complex numbers to be empty—the weak fundemental theorem of algebra.

Suppose we have two polynomials

a = a_{m}X^{m} + a_{m−1}X^{m−1} + ⋯ + a_{1}X + a_{0}
b = b_{n}X^{n} + b_{n−1}X^{n−1} + ⋯ + b_{1}X + b_{0}

with coefficients in a commutative ring R. The so-called pseudodivision algorithm, which is proved in essentially the same way as the division algorithm for monic polynomials, says that if 0 < m ≤ n, then we can find canonical q and r, with deg r < m, such that

a_{m}^{n−m+1}b = qa + r

We will denote the remainder r by ρ (b, a) and we say that ρ (b, a) is the result of remaindering b by a.

The coefficients of q and r can be written as polynomials in the coefficients of a and b. The computation really takes place in the polynomial ring

Z [α_{m}, …, α_{0}, β_{n}, …, β_{0}] [X]

where the α’s and β’s are indeterminates, so we might as well assume that R is discrete. Note that ρ (b, a) is defined only when 0 ≤ deg a < deg b.

Let R be a discrete commutative ring. If a is any nonzero polynomial in R [X], then γ (a) is defined to be the result of deleting the leading term of a. We say that γ (a) is the chop of a. Set γ (0) = 0.

If A and B are subsets of R [X], then rem (A, B) is defined to be

{p ∈ R [X] : p = ρ (a, b) or p = ρ (b, a) for some (a, b) ∈ A × B}

and chop (A) is defined to be {γ (a) : a ∈ A}. We say that A is closed under chopping and remaindering if rem (A, A) ⊂ A and chop (A) ⊂ A.

Lemma 4.1. Given a finite set S of polynomials over a discrete commutative ring, there is a finite set of polynomials containing S that is closed under chopping and remaindering.

Proof. Define S_{0} to be S. Let n be a bound on the degrees of the polynomials in S_{0}. For i > 0, define

S_{i} = S_{i−1} ∪ chop (S_{i−1}) ∪ rem (S_{i−1}, S_{i−1})

We will show that, for i ≥ 1, the elements of S_{i} \ S_{i−1} have degree at most n − i. That’s clearly true for i = 1, and if i > 1, and p ∈ S_{i} \ S_{i−1}, then

p ∈ chop (S_{i−1} \ S_{i−2}) ∪ rem (S_{i−1}, S_{i−1} \ S_{i−2})

whence, by induction on i, we have deg p < n−(i − 1) so deg p ≤ n−i. In particular, the elements of S_{n} \ S_{n−1} have degree at most 0, so S_{n} is closed under chopping and remaindering. □

Apply Lemma 4.1 to the set S of two polynomials

α_{m}X^{m} + α_{m−1}X^{m−1} + ⋯ + α_{1}X + α_{0}
β_{n}X^{n} + β_{n−1}X^{n−1} + ⋯ + β_{1}X + β_{0}

over the ring Z [α_{m}, …, α_{0}, β_{n}, …, β_{0}], where the α’s and β’s are indeterminates. Let L be the set of leading coefficients of polynomials in S′. The elements of L are in Z [α_{m}, …, α_{0}, β_{n}, …, β_{0}]. If we are then given two polynomials

a = a_{m}X^{m} + a_{m−1}X^{m−1} + ⋯ + a_{1}X + a_{0}
b = b_{n}X^{n} + b_{n−1}X^{n−1} + ⋯ + b_{1}X + b_{0}

with coefficients in an arbitrary commutative ring R, we can form the subset L (a, b) of R obtained by plugging a_{i} and b_{j} for α_{i} and β_{j} in the elements of L. We are now ready to prove a general Bezout’s equation for polynomials over an arbitrary commutative ring.

Theorem 4.2. Let

a = a_{m}X^{m} + a_{m−1}X^{m−1} + ⋯ + a_{1}X + a_{0}
b = b_{n}X^{n} + b_{n−1}X^{n−1} + ⋯ + b_{1}X + b_{0}

be polynomials over a commutative ring R. If each of the elements of L (a, b) is either 0 or invertible, then there exist s and t in R [X] such that sa + tb divides both a and b and is either monic or 0.

Proof. We attempt to execute the Euclidean algorithm on a and b. This will succeed if, each time we create a new remainder, we can write it as a polynomial with an invertible leading coefficient. But that is exactly what the hypothesis of the theorem allows us to do. The elements of L (a, b) include all the coefficients of a and b and anything we might get by repeatedly applying the division algorithm. Unless a = b = 0, the last nonzero remainder from the algorithm is of the form sa + tb and divides both a and b. We can divide by its leading coefficient to make it monic. □

As an immediate corollary we get

Corollary 4.3. Let R be a ring in which any noninvertible element is zero. If a and b are two polynomials in R [X] then we can construct propositions P_{1}, …, P_{k} such that if the conjunction

(P_{1} ∨ ¬P_{1}) ∧ (P_{2} ∨ ¬P_{2}) ∧ ⋯ ∧ (P_{k} ∨ ¬P_{k})

of instances of the law of excluded middle holds, then there exist s and t in R [X] such that sa + tb divides both a and b and is either monic or 0.

The complex numbers are such a ring, as is any Heyting field. Why do we want Corollary 4.3? The relevant intuitionistic tautology is that the negation of

(P_{1} ∨ ¬P_{1}) ∧ (P_{2} ∨ ¬P_{2}) ∧ ⋯ ∧ (P_{k} ∨ ¬P_{k}) ∧ A

implies ¬A. That is easy to see by induction from the case k = 1. For k = 1, suppose A and ¬ ((P_{1} ∨ ¬P_{1}) ∧ A). If P_{1} is true, then we get a contradiction, so P_{1} is false, and we get a contradiction. So if we want to prove ¬A, we are allowed to assume any finite number of instances of the law of excluded middle. The proposition A that we are interested in refuting is that a given monic polynomial with complex coefficients has no root. That refutation is the weak fundamental theorem of algebra.

First we prove the fundamental theorem of algebra for strongly separable polynomials.

Theorem 4.4. Let f be a monic polynomial with complex coefficients. Suppose that there exist polynomials s and t such that sf+tf′ = 1. Then f = (X − r_{1}) ⋯ (X − r_{n}) where the r_{i} are distinct complex numbers.

Proof. From [3] we can find algebraic numbers q_{1}, …, q_{n} that approximate the spectrum of f arbitrarily closely. That means that

g = (X − q_{1}) ⋯ (X − q_{n})

is arbitrarily close to f, and that given another close approximation q′_{1}, …, q′_{n} to the spectrum of f, we can reindex it so that q′_{i} is close to q_{i} for each i. In particular, the numbers f (q_{i}) can be made arbitrarily small so the numbers f′ (q_{i}) are bounded away from 0 because of the equation sf + tf′ = 1. Differentiation of polynomials is continuous, so f′ (q_{1}) is close to

g′ (q_{1}) = (q_{1} − q_{2}) (q_{1} − q_{3}) ⋯ (q_{1} − q_{n}) .

Hence q_{1} is bounded away from q_{2}, …, q_{n}, and similarly for the rest of the q’s. Thus we can find n discs, D_{1}, …, D_{n}, bounded away from each other, so that any sufficiently close approximation to the spectrum of f has one point in each of the discs. The points in D_{i}, as we range over approximations to the spectrum, form a coherent system of approximations, hence determine a unique complex number r_{i} because the complex numbers are complete in this choiceless sense. Clearly f vanishes on each r_{i}, so f can be written as desired. □

Now we can prove the weak fundamental theorem of algebra for arbitrary monic polynomials.

Theorem 4.5 (Weak fundamental theorem of algebra). Let f be a nonconstant monic polynomial with complex coefficients. Then the assumption that f has no roots leads to a contradiction.

Proof. We apply Corollary 4.3 to the polynomial f and its derivative f′. Assume f has no roots. We will derive a contradiction from that and the existence of polynomials s and t in C [X] such that d = sf + tf′ is a monic polynomial that divides both f and f′. As f′ is a nonzero polynomial of degree less than f, the polynomial d is either 1 or a monic nonconstant proper divisor of f. In the latter case, we can replace f by d and we are done by induction on the degree as d cannot have roots (if deg f = 1, then f has a root). So we may assume that

sf + tf′ = 1.

But then Theorem 4.4 says that f has a root. □

The following corollary is the point of this whole exercise.

Corollary 4.6. Let f be a nonconstant monic polynomial with complex coefficients, Z the zero set of f, and z a complex number. If d (z, spec f) = r, and ε > 0, then the assumption that f has no roots in the disc of radius r + ε around z leads to a contradiction. Thus d (z, spec f) = δ (z, Z) so Z is quasilocated. In fact, Z is quasifinite.

Proof. Write f = g_{1}g_{2} ⋯ g_{k} where the diameter of each spec g_{i} is less than ε. As r = inf_{i} d (z, spec g_{i}), there is i such that the diameter of g_{i} plus d (z, spec g_{i}) is less than r + ε. That requires that g_{i} has no roots (anywhere), which leads to a contradiction by Theorem 4.5.

To show that Z is quasifinite, we have to find, for each ε > 0, an ε-quasi-approximation to Z of length n. An ε-quasi-approximation to Z is given by the root set r_{1}, …, r_{n} of a polynomial over the Gaussian numbers that is close to f. To show that it is an ε-quasi-approximation, we need to show that B_{ε} (r_{i}) ∩ Z cannot be empty for i = 1, …, n, and Z ⊂ B_{ε} (r_{1})∪⋯∪B_{ε} (r_{n}). The first condition means that δ (r_{i}, Z) < ε. But δ (r_{i}, Z) = d (r_{i}, spec f) which we can make arbitrarily small. For the second condition, if z ∈ Z, so f (z) = 0, then z is close to one of the r_{i} because if the polynomial f is close to (X − r_{1}) ⋯ (X − r_{n}), and f (z) = 0, then z is close to one of the r_{i}. □

5. Comaximal polynomials and resultants

We would like to prove that, for monic polynomials a and b over C, that the distance between spec a and spec b is positive if and only if there are polynomials s and t such that sa + tb = 1. To do this, we will show that if the distance from spec a to spec b is positive, then the resultant of a and b is different from zero. Then we will apply a theorem valid for arbitrary commutative rings (Theorem 5.1) that will construct the polynomials s and t.

The resultant of a and b (not necessarily monic) is the determinant of their Sylvester matrix. Here is the Sylvester matrix for a = a_{3}X^{3} + a_{2}X^{2} + a_{1}X + a_{0} and b = b_{5}X^{5} + ⋯ + b_{1}X + b_{0}

S = ( \begin{matrix}a_{3} & a_{2} & a_{1} & a_{0} & 0 & 0 & 0 & 0 \\ 0 & a_{3} & a_{2} & a_{1} & a_{0} & 0 & 0 & 0 \\ 0 & 0 & a_{3} & a_{2} & a_{1} & a_{0} & 0 & 0 \\ 0 & 0 & 0 & a_{3} & a_{2} & a_{1} & a_{0} & 0 \\ 0 & 0 & 0 & 0 & a_{3} & a_{2} & a_{1} & a_{0} \\ b_{5} & b_{4} & b_{3} & b_{2} & b_{1} & b_{0} & 0 & 0 \\ 0 & b_{5} & b_{4} & b_{3} & b_{2} & b_{1} & b_{0} & 0 \\ 0 & 0 & b_{5} & b_{4} & b_{3} & b_{2} & b_{1} & b_{0} \end{matrix} )

If a = ∏_{i=1}^{m} (X − q_{i}) and b = ∏_{j=1}^{n} (X − r_{j}), then the determinant of S is ∏_{i,j} (q_{i} − r_{j}). That fact is a simply a polynomial identity in the indeterminants q_{i} and r_{j}.

We say that two elements a and b a ring are comaximal if there exist s and t in the ring such that sa + tb = 1.

Theorem 5.1. Let a = a_{m}X^{m}+a_{m−1}X^{m−1}+⋯+a_{0} and b = b_{n}X^{n}+b_{n−1}X^{n−1}+ ⋯ + a_{0} be polynomials in R [X] with m, n ≥ 1. Then the following two conditions are equivalent:

(1) The polynomials a and b are comaximal in R [X] and the (formal) leading coefficients a_{m} and b_{n} are comaximal in R,

(2) The resultant of a and b is a unit in R.

Proof. If S is the Sylvester matrix of a and b, and S^{∗} is the adjugate of S, then S^{∗}S = (det S) I, where I is the identity matrix and det S is the resultant of a and b. So the last row of S^{∗} gives the coefficients of polynomials s and t such that sa + tb is the resultant of a and b. Thus if condition 2 holds, then the polynomials a and b are comaximal in R [X]. It remains to show that a_{m} and b_{n} are comaximal in R. But that follows by expanding the determinant of S by minors using the first column.

Now suppose condition 1 holds, so there exist polynomials s and t such that sa + tb = 1. We will first prove 2 under the assumption that a_{m} (or b_{n}) is a unit. Now if g is any polynomial of degree less than m + n, then we can certainly find polynomials s and t such that sa + tb = g. As a_{m} is unit, we can write t = qa + r where deg r < m. So

(s + qb) a + rb = g

which means we may assume that deg t < m, so deg tb < m + n. This forces deg s < n because if s_{k} is the (formal) leading coefficient of s, and k ≥ n, then the equation sa + tb = g requires s_{k} = 0 as deg tb < m + n. Because deg s < n and deg t < m, we can put the coefficients of s and t together to form a row vector v of length m + n so that vS = (g_{m+n−1}, g_{m+n−2}, …, g_{1}, g_{0}) where S is the Sylvester matrix. Since we can do this for arbitrary g of degree less than m + n, this shows that the matrix S is invertible, whence det S, which is the resultant of a and b, is a unit in R.

To finish the proof, we pass to the rings R [1/a_{m}] and R [1/b_{n}]. The kernel of the natural map R → R [1/a_{m}] is the set of elements of R that annihilate some power of a_{m}. In particular, R [1/a_{m}] is trivial exactly when a_{m} is nilpotent. Now since the theorem is true when either a_{m} or b_{n} is a unit, it follows that det S is a unit in R [1/a_{m}] and in R [1/b_{n}]. We want to show that det S is a unit in R. That follows from the fact that a_{m} and b_{n} are comaximal. Specifically, we have (det S) r/a_{m}^{k} = 1 in R [1/a_{m}] for some r ∈ R and positive integer k, so (det S) ra_{m}^{i} = a_{m}^{k+i} in R for some positive integer i. Thus det S divides a power of a_{m} in R. Similarly, det S divides a power of b_{n}. That makes det S a unit because any power of a_{m} is comaximal with any power of b_{n}. □

It’s not enough in Theorem 5.1 just to require that a and b be comaximal. A trivial example is a = b = 0X + 1 where m = n = 1.

Over a discrete field, Theorem 5.1 is often stated as the resultant of a and b is zero if and only if a and b have a nontrivial common factor, it being assumed that nobody is so silly as to have the formal leading coefficient of a and b equal to zero. The theorem in this form, even for monic a and b, does not generalize well to arbitrary commutative rings.

Consider the polynomials (X − 2) (X − 6) = X^{2} + 4 and X (X − 4) over Z_{8}. It is easily checked that their resultant is zero. However, they have no nontrivial common factors. It’s easy to see that they have no nontrivial monic common factors. What constitutes a trivial common factor? It seems clear that these are exactly the unit polynomials, the polynomials with inverses. Over a decent ring, the units in R [X] are just the units of R, but in a ring with nilpotent elements, like Z_{8}, there are units of arbitrarily high degree, like 4X^{n} + 1.

We will show that over Z_{8}, or any primary ring, the factors of a monic polynomial are all products of a unit polynomial and a monic polynomial. Thus if a monic polynomial has a nontrivial factor, then it has a nontrivial monic factor.

First we note that in any ring, the factorization of a polynomial as a monic polynomial times a unit polynomial, if possible, is unique. Indeed, if mu = m′u′, then m = m′u′u^{−1} so deg m′ ≤ deg m, hence, by symmetry deg m′ = deg m. As both m and m′ monic, we must have u′u^{−1} = 1.

We can characterize the polynomials that can be factored in this way.

Theorem 5.2. Let p = ∑ a_{i}X^{i} be a polynomial over a commutative ring R. Suppose a_{m} is a unit in R and that a_{i} is nilpotent for i > m. Then p can be written as a unit polynomial times a monic polynomial.

Proof. Let I be a fixed nilpotent ideal of R such that a_{i} ∈ I for all i > m. We will multiply p by a sequence of unit polynomials until it becomes monic.

Suppose j > m and d ≥ 1 are such that

a_{i} ∈ I^{d} for m < i ≤ j
a_{i} ∈ I^{d+1} for i > j

Multiply p by the unit polynomial

1 − \frac{a_{j}}{a_{m}} X^{j−m}

In the resulting polynomial p′ we have

a′_{m} ∈ a_{m} + I^{d} is a unit
a′_{j} = 0 ∈ I^{d+1}
a′_{i} ∈ I^{d} + I^{d} = I^{d} for m < i ≤ j
a′_{i} ∈ I^{d+1} + I^{d+d} = I^{d+1} for i > j

When j = m + 1, we get a′_{i} ∈ I^{d+1} for all i > m. At that point we set d equal d + 1 and continue until I^{d} = 0. At that point the polynomial has a unit a_{m} as its formal leading coefficient. □

The converse of Theorem 5.2 is also true because the units in the ring R [X] are exactly those polynomials whose constant term is a unit in R and whose other coefficients are nilpotent.

We end this section by applying Theorem 5.1 to polynomials over the complex numbers and their spectra.

Theorem 5.3. If a and b are nonconstant monic polynomials over C, then the distance between spec a and spec b is positive if and only if a and b are comaximal.

Proof. We will apply Theorem 5.1. As a and b are monic, their leading coefficients are certainly comaximal. So a and b are comaximal if and only if their resultant is a unit, that is, if and only if the resultant is different from zero. It thus suffices to show that the resultant is different from zero if and only if the distance between spec a and spec b is positive.

The resultant, as a function of the coefficients of a and b, is clearly uniformly continuous on bounded subsets. So if ∏_{i=1}^{m} (X − q_{i}) and ∏_{j=1}^{n} (X − r_{j}) are close to a and b respectively, then ∏_{i,j} (q_{i} − r_{j}) is close to the resultant of a and b. Thus the resultant of a and b is the limit of ∏_{i,j} (q_{i} − r_{j}). On the other hand, the distance between spec a and spec b is the limit of min |q_{i} − r_{j}|. Clearly ∏_{i,j} (q_{i} − r_{j}) is eventually bounded away from zero if and only if min |q_{i} − r_{j}| is. □

6. Examples of Riesz spaces

The question is raised in [2] as to whether you can construct the points of the spectrum of a separable Riesz space, all of whose elements are normable, in the absence of countable choice. The authors, referring to [3], suggested basing a counterexample on the zero set of X^{2} − a. However it appeared that the resulting Riesz space was not separable. Here we elaborate on that construction and give a separable counterexample.

A Riesz space is a lattice ordered vector space V over the rational numbers with an element 1 such that for each v in V, there exists a positive integer n such that v ≤ n·1. The canonical example is the space of uniformly continuous functions on a compact metric space, where 1 is the constant function whose value is 1. We say that V is normable, or normed, if for each v ∈ V, the set {q ∈ Q : v ≤ q · 1} has an infimum in R. We call this greatest lower bound the least upper bound of v. The norm of f is defined to be the least upper bound of |v| = v ∨ 0 − v ∧ 0. Note that classically every Riesz space is normed.

Let S be a quasilocated subset of the complex plane that is contained in a closed disc D. Let C (D) be the Riesz space of uniformly continuous real valued functions on D. Let K be the functions in C (D) that vanish on S. The set K is a subspace of C (D) that is closed under the lattice operations. Our counterexample is the space C (D) /K. It is separable because C (D) is. Note that this is not exactly the space of uniformly continuous functions on S, it is the space of those uniformly continuous functions on S that extend to uniformly continuous functions on D.

If f ∈ C (D), then f vanishes on S if and only if f and −f are nonnegative on S. Note that if f is nonnegative on S, and g vanishes on S, then f + g is nonnegative on S, so this defines a notion of nonnegativity on C (D) /K. You get another notion of nonnegativity on C (D) /K by considering those functions that come from nonnegative functions in C (D). However, if f is nonnegative on S, then f is equal to f ∨ 0 on S, so these two notions are the same.

Theorem 6.1. Let S be a quasilocated subset of the complex plane that is contained in a closed disc D. Let C (D) be the Riesz space of uniformly continuous real valued functions on D and let K be the functions in C (D) that vanish on S. Then every element of C (D) /K is normable, and each Riesz-space homomorphism C (D) /K → R that takes 1 to 1 is given by evaluation at a point z_{0} ∈ D such that δ (z_{0}, S) = 0. Conversely, if δ (z_{0}, S) = 0, and f ∈ K, then f (z_{0}) = 0, so evaluation at z_{0} gives a Riesz-space homomorphism C (D) /K → R that takes 1 to 1.

Proof. We want to approximate the least upper bound of f on S to within ε. Choose θ > 0 so that if d (x, y) ≤ θ, then |f (x) − f (y)| < ε/2. Take a finite θ/4approximation F to D and partition F into two subsets, one, S′, where δ (x, S) < θ and one where δ (x, S) > θ/2. Let μ be the supremum of f on S′. We want to show that f ≤ μ + ε on S and that it is not the case that f ≤ μ − ε on S.

To show that f ≤ μ + ε on S, let s ∈ S. There is s′ ∈ S′ such that d (s, s′) < θ for otherwise d (s, s′) > θ/2 for every s′ ∈ S′. But d (s, t) < θ/2 for some t ∈ F, and this t must be in S′. Thus |f (s) − f (s′)| < ε/2. As f (s′) ≤ μ, we conclude that f (s) ≤ μ + ε/2.

Now suppose f ≤ μ − ε on S. We know that there is s′ ∈ S′ such that f (s′) is arbitrarily close to μ. Note that B_{θ} (s′) ∩ S cannot be empty because δ (s′, S) < θ. Yet if s ∈ B_{θ} (s′)∩S, then |f (s) − f (s′)| < ε/2, so f (s′) ≤ μ−ε/2, a contradiction.

For the second claim, let ρ be a Riesz-space homomorphism C (D) /K → R taking 1 to 1. This induces a homomorphism ρ : C (D) → R taking 1 to 1 and K to zero. To see that ρ is given by evaluation at a point in D, let W be the vector sublattice of C (D) generated by 1 and the two coordinate projections, π_{1} and π_{2}. Then W is dense in C (D) by the Stone-Weierstrass approximation theorem (see below). Let z_{0} = ρ (π_{1}) + iρ (π_{2}). It’s easy to see that ρ is evaluation at z_{0} on W, hence is evaluation at z_{0} on C (D).

We want to show that δ (z_{0}, S) = 0. The function f (x) = δ (x, S) is in C (D) and vanishes on S. So ρ (f) = 0. But ρ is evaluation at z_{0}, so δ (z_{0}, S) = 0. Conversely, suppose δ (z_{0}, S) = 0 and f ∈ K. Then Lemma 1.7 tells us that f (z_{0}) = 0. □

Corollary 6.2. Let S be the root set of a nonconstant monic polynomial p and let V = C (D) /K be the Riesz space associated with S as in the theorem. Then V is normed and separable, and each Riesz-space homomorphism from V onto R gives a root of p.

Proof. The space V is separable because the space C (D) is separable. As p is in K, if δ (z_{0}, S) = 0, then z_{0} is a root of p. □

The point of the corollary is that, in the absence of choice, we need not be able to construct a root of the polynomial p (X) = X^{2} − a, see [3], so we need not be able to construct a Riesz-space homomorphism from a normed, separable, Riesz space onto R.

We include a short choice-free proof of the Stone-Weierstrass theorem for the square, which was appealed to in the proof of Theorem 6.1. We want to approximate nonegative functions on the square by finite suprema of finite infima of functions of the form ax + by + c, that is, functions whose graphs are planes. Suppose we have a little square S_{i} in a grid and a nonnegative constant c_{i}. Let φ_{i} be the infimum of the constant c_{i} and one affine function for each side L of S_{i} whose value is c_{i} on L and 0 on the opposite side of the other little square in the grid with side L. The graph of φ_{i} is a pyramid with its top cut off. Let ψ = sup_{i} φ_{i}. Let J be the indexes of the block of nine little squares centered at S_{i}. If x ∈ S_{i}, then

inf_{j∈J} c_{j} ≤ ψ (x) ≤ sup_{j∈J} c_{j}

Given a uniformly continuous function f on the square, choose a grid so that f does not vary by more than ε on any block of nine little squares in the grid. Choose c_{i} to be the value of f in the center of the little square S_{i} and let ψ be as above. Then ψ approximates f within ε.

References

[1] Bishop, Errett, Foundations of constructive analysis, McGraw-Hill 1967

[2] Coquand, Thierry and Bas Spitters, Formal topology and constructive mathematics: the Gelfand and Stone-Yoshida representation theorems, Journal of Universal Computer Science, 11 (2005) 1932–1944

[3] Richman, Fred, The fundamental theorem of algebra: a constructive development without choice, Pacific Journal of Mathematics, 196 (2000), 213-230. MR 2001k:03141 [4] , Generalized real numbers in constructive mathematics, Indagationes Math-

ematicae, 9 (1998), 595-606. MR 2000e:03172

[5] Ruitenburg, Wim B. G., Constructing roots of polynomials over the complex numbers. Computational aspects of Lie group representations and related topics (Amsterdam, 1990), 107– 128, CWI Tract, 84, Math. Centrum, Centrum Wisk. Inform., Amsterdam, 1991.

Florida Atlantic University

E-mail address: Robert.Lubarsky@comcast.net

Florida Atlantic University

E-mail address: richman@fau.edu