Visiting Scholars‘ Lectures—1987

MATHEMATICS SERIES NO. 15

FORWARD
Since 1980, the Ex—Students Association of Texas Tech University has gen—erously provided funds to the Mathematics Department for the purpose ofbringing visiting mathematicians to the campus. During 1986 and 1987, anumber of visitors came for brief periods, during which they presented lec—tures and consulted with the faculty and graduate students. This volumecontains the papers expanding upon the lectures they presented.
|
The Department of Mathematics gratefully acknowledges the supportof the Ex—Students Association.
John T. White
William H. Gustafson
Texas Tech University

CONTENTS£40.

§ t. %)A\—

Dennis Burke, Miami University
The normal Moore space problem . ................................ }. 1
Robert Guralnick, University of Southern California
Matrices and representations over rings of analytic functions andother one—dimensional rIng$ . .......................}s seee ses keel} ls 15
William H. Gustafson, Texas Tech University and Klaus W. Roggenkamp,
Universitat Stuttgart
Automorphisms and Picard groups for hereditary orders............ 37
Peter Henrici‘®, University of North Carolina and Mathematical Sciences
Research InstituteProduct theorems for formal hypergeometric series ................. 53
Paul R. Halmos, Santa Clara University
Fifty years of linear algebra: a personal reminisence................ TI
Onésimo Hernandez—Lerma, Centro de Investigacion del I.P.N.
Controlled Markov processes: recent results on approximation andadaptive CONAtTOL.....................leele seee eee ee ee e ee ee ee e e e e ees 91
Richard S. Varga, Kent State University
Scientific computation on some mathematical conjectures ......... 119
Michael S. Waterman, University of Southern California
Mathematical results for mapping DNA ........................... 137

Texas Tech University, Mathematics Series
Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

The Normal Moore Space Problem
Dennis Burke
Miami University
Oxford, Ohio 45056
1

Introduction.

For fifty years, the Normal Moore Space Problem has been directly or in—directly responsible for much of the research or the direction of researchin set—theoretic topology. Besides results aimed toward the solution of themain question itself, the Normal Moore Space Problem has motivated re—search on a number of related questions concerning topics from metrization
theory, normality and collectionwise normality, generalized metric spaces
and set theory.
This note is a short survey of several major steps in the history of theNormal Moore Space Problem, starting with the statement of the problem
by F. B. Jones in 1937, through the "Provisional Solution" of the problem
by P. Nyikos in 1978 and to the theorem by W. Fleissner showing thedependence of the problem on large cardinals. While we cannot begin tocover all of the important results directed toward this question, we will
discuss several of the high points, including many proofs. The proofs andterminology may not be historically accurate in that techniques or ideas
may be used that were not common at the time of the original proofs. All
topological or set—theoretic notions that are used, but not defined here, canbe found in standard references such as [E] or [K].
The term "space" refers to a topological space and all regular or normal
spaces are assumed to be T;. The sets of real numbers and natural numbers
will be denoted by R and N respectively. The cardinality of a set X isdenoted by |X|. The ordinals w, w, are used to denote the first two infinite
cardinals.
|
A Moore space is a regular space with a development. A development
for a space X is a sequence {G,}$° of open covers of X such that for anyz € X if z € G, € G,, for each n € N, then {G, : n € N} is a local base atz. Equivalently, if st(z,0,) = U{G : z € G € G,,} then {st(z,8,) : n € N}
is a local base at z. A Moore space satisfies Axiom 0 and parts 1, 2, and 3,of Axiom 1in [Mo]. The classic example of a separable Moore space which
is not metrizable is given below. We will refer to this space as the Moore
Plane.

Example 1.1 A separable, nonmectrizable, Moore space.
Let T‘ = R x [0, 00). Describe a topology on I‘ by letting points above
the x—axis have their usual neighborhoods and points on the x—axis haveneighborhoods which contain the point and the interior of an open disk

above and tangent to the x—axis at the point. To be more specific, let us
define a local base {U(p,n) : m E N} for each p E T. If d is the usual
Euclidean metric and p = (p;, p;), with p, > 0, n € N, letU(p,n) = {a € R x (0,00) : d(p, 2) < 1/n}.
If P2 = 0 let

U(p,n)= {p} U {z ET : d((pi,1/n), z) < 1/n}..
K G,, = {U(p,n) : p E T} the reader may verify that {G,, }?° is a development
for the regular space I‘. It is clear that T is separable since the set of points
in I‘ with rational coordinates is dense in I. The set S = R x {0} isan uncountable closed discrete subset of T‘, indicating that T‘ cannot be
metrizable since separable metric spaces are always hereditarily separable.

We will see later that the presence of such a set S is expected in any
separable nonmetrizable Moore space.

2

Statement of the problem.

While the problem was apparently known earlier, the first appearance inprint was in a paper by F. B. Jones in 1937.
Question 2.1 [J;]. Is every normal Moore space metrizable?
In this same paper, Jones provides a partial answer to this question for the

separable case assuming 2" < 2".

Theorem 2.2 [J;]. If 2" < 2, then every separable normal Moore space:s metrizable.
At the time (1937), of course, it was not known that the condition
2" < 2" was independent of the usual axioms (ZFC) of set theory. The
Continuum Hypothesis clearly implies that 2" < 2", so consistency of thiscondition was established by Godel [G], but independence was not proved
until methods of Cohen [C] in 1963.
The key ingredient in Jones‘ proof of Theorem 2.2 was a variation ofwhat is now known as "Jones‘ Lemma", a result appearing in most standard
general topology textbooks.
Lemma 2.3 [Ji]. If a space X contains a dense set D and a closed discrete
subset S with 212! < 2!°"\ then X is not normal.
2

Proof. If A C S, notice that A and S — A are disjoint closed subsets
of X so if X was normal there would be an open set U(A) in X withA C U(A) and U(A) M (S — A) = 0. We obtain a contradiction to thecondition that 212! < 2!"! by showing that if A, B are distinct subsets of
S then U(A) N D, U(B) N D are distinct subsets of D. Without loss ofgenerality, assume B — A x (; then the open set U(B) — U(A) # 0 so
(UV(B) — U(A)) ND # 0. Hence U(B)ND contains elements not in U(A)ND
and the proof is complete.
A typical application of Lemma 2.3 shows that the Moore Plane (Ex—ample 1.1) is not normal. To see this let D be any countable dense set in
T and S= R x {0}.
|If X is a separable Moore space then X is metrizable if and only if X
is Lindelof, (a fact easily shown using the definition of a Moore space andstandard results about metric spaces). The proof of Theorem 2.2 is thenfinished if it can be shown that any non—Lindelof Moore space contains
a closed discrete subset S of cardinality > w;. This fact can be proved
directly, but also follows with the use of a covering property satisfied by all
Moore spaces. This notion will also be used in the next two sections.

A space X is said to be subpaeracompact if every open cover of X has ao—discrete closed refinement.
Theorem 2.4 [Bil. Every Moore space X is subparacompact.
Proof. Let {G.}? be a development for X where each G,41 refines G,,

and suppose U = {U,, : a € A} is an open cover of X with A well ordered.
For any n € N, « € A define
Ia= { +:: ev. — (V va) and «(69 cv.}
Bia

Let 7, = {Taa : « € A}. It is easy to see that T = UM.,n=1 7T, is a cover of
X refining {/. To see that each 7, is discrete let z E X and find y E A
and m > n such that z E T,,,. Now if y E st(z,9,) MN T., we would havey E st(z,9,,) C U, and z E st(y,9..) C Ua. A contradiction arises in caseeither y < a or a <7; hence st(z, 9) NIna # 0 only if a = y. To see thateach T,,, is closed, pick z E T,,. For z C G C G,, there is some y E G )T,
so G C st(y,9,) C U,; this establishes that st(z,G,) C U,. Certainlyz ¢ Us for B < a since UsMNTn, = I0 for B < a. This says z E T., so
Tna = Taa. T is the desired a—discrete closed refinement and the theorem

is proved.
Let us now review the steps for the proof of Theorem 2.2. Suppose X isa separable Moore space with countable dense set D. If X is not metrizable
then X is not Lindelof and there is an open cover U of X with no countablesubcover. If 7 = UZ, 7, is a a—discrete closed refinement of U{ with eachT,, discrete there must be some k where 7; is uncountable. An appropriatechoice of elements from elements of 7; yields a closed discrete set S with
[S| > wi. The assumption 2" < 2" implies that 2!P! < 2"! and Jones‘
Lemma (2.3) says that X could not be normal, a contradiction. Hence X
must be metrizable.

3

Collectionwise normal spaces

In 1951, R. H. Bing published a paper [Bi] containing several results per—tinent to the study of Moore spaces. One of the results is now regarded asa standard metrization theorem similar to a metrization theorem given by
Nagata [Na) and Smirnov [Sm] at about the same time.
Theorem 3.1 [Bi]. A regular space X is metrizable if and only if X has
a a —discrete open base.
Bing noticed that imposing a "stronger" normality condition in a Moore
space would give metrizability. He defines a space X to be collectionwise
normal if for any closed discrete collection D in X there exists a pairwise
disjoint open collection G such that for each D E D there is G(D) E G sothat D C G(D) and G(D) # G(D‘) if D, D‘ E D, D # D‘. An easy exercise
shows that the collection G, as given above, can actually be made to bediscrete.
Theorem 3.2 [Bi]. If a Moore space X 1s collectionwise normal, then X
is metrizable.
Proof. Let {G,,}? be a development for the collectionwise normal Moore
space X. By Theorem 2.4 each open cover G,, has a a—discrete closed refine—ment F,, say 71 = ULZ1 /ng where each F,, is discrete. Using collection—

wise normality one can find, for each n, k E N, a discrete open collection
Hn, such that if F E F,,; there exists H(F) E H,,, and G(F) C G,, withFPC H(F) C G(F).
It is easy to show that UXL, UfZ; H4 is a a—discrete open base for X. Apply
Bing‘s Metrization Theorem (8.1) and the proof is complete.
To show that the collectionwise normal property is strictly stronger thannormality, Bing gave an example (Example G in [B;]) of a normal space
which was not collectionwise normal. Variations of this example are models
for other noncollectionwise normal spaces having some strengthening of
normality.

Example 3.3 [B;]. There is a space F which is normal but not collection—
wise normal.

Proof. Let P be an uncountable set, Q = P(P) (the power set of P) andF = xp{0,1}. For each p E P let f, € F where f,(Q) = 1 if and only if
p E Q. Let E = {f, : p e P}. The topology on F is that induced by having
all elements of P — E isolated and neighborhoods of elements of F inheritedfrom the product topology on ®g{0,1}. For C a finite subcollection of Q
and f, € E let
U(F,,C) = {g EF : f,(C) = g(C), for all C EC}.
These sets form the basic neighborhoods for f, in F.
It is easily verified that 5 is a closed discrete subset of F and to show
F is normal, it suffices to show that for any D C E, D and E — D can beseparated. To this end let Q = {p: f, 6 D}; then the setsv = U{U(F.{Q}) : p e Q}

and|

W = |{U(F. {Q}) : pe P — Q}

will give the desired separation.
Now consider the closed discrete collection {{f,} : p E P}. If F wascollectionwise normal, this collection could be separated so there would ex—

ist, for each p E P, a finite C, C Q such that U(f,,C,)NMNUU(F,,C,) = 0 ifp £ q. Using the "A—system lemma" for uncountable families of finite sets

[K] there exists some uncountable S C Pand fixed B such that C, NC, = B

for all distinct p,q € S. There are only finitely many functions from B
onto {0,1} so there must exist distinct p,q € S where f,|s = f,|s. These

conditions on C, and C, imply that U(f,,C,)NU(U(F,,C,) # 0, a contradic—

tion. Hence, the collection {{f,} : p E P} cannot be separated and F is
not collectionwise normal.
It should be mentioned that the space F above was shown to be notcollectionwise normal by showing it was not collectionwise Hausdorff. A
space X is collectionwise Hausdorff if for any closed discrete subset S of
X there exists a collection {U(x) : zx € S} of open subsets of X separating

S; ie., z € U(z) for each z € S and U(z)N\U(y) = 0 if z £4. It iseasy to show that a separable Moore space is metrizable i and only if it iscollectionwise Hausdorff [B].

Another property of F worthy of note is the character of F. Since[P| > w, and |Q| > 2" the minimum cardinality of a local base at eachJ, € E is 2. The other points of the space are isolated so F has character> 2".

Later results will show that 2" is the smallest character that anormal noncollectionwise Hausdorff space could have.

4

CQ—sets and the separable case.

An uncountable subset E of the real numbers R is a Q—set if every subset
A of E is Gs—set in E (relative to the topology inherited from R). Without
5

knowing whether the existence of a Q—set was consistent with ZFC, R.

H. Bing (1951, [B,]) and R. W. Heath (1964, [He]) gave results showingthat the existence of a separable normal nonmetrizable Moore space was
equivalent to the existence of a Q—set.

Example 4.1 [Bi]. If there exists a Q—set then there exists a separable
normal Moore space which is not metrizable.
Proof. The example is actually a subspace of the Moore Plane I‘ given
in Example 1.1. Given a Q—set E in R let

Z = (R x (0, c0)) UJ(B x {0})with the relative topology inherited from I‘. We continue to use the notation
given in 1.1. Now, Z is clearly a separable Moore space and is not metrizablesince E x {0} is an uncountable discrete subset of Z. To see that Z is normal
we first notice (argument left to the reader) it is enough to show that if
A C E x {0} and B = (E x {0}) — A then A and B can be separated.
Since E is a Q—set there exist decreasing sequences {S,}?° and {T,}? of
Euclidean open sets in R* such that

A=(f) S.)((2 x {0}
n=1

and
—

B= ((| T. YE x {0}).
n=lFor each n E N let B, = B — S,, and A, = A — T,. Next we show that

B,, and A can be separated. For each a = (a1,0) € A find a positive real
number e(A) such that
(a1 — e(a), a1 + ea)) x {0} C S..
Notice that there exists k(a) € N, depending on e(a), such that
U (a, k(a)) \U(b, 1) = 0
for all b € B,. (A simple sketch illustrating the relationship between Eu—
clidean distance and the elements of G,, will help here.) This says that if
V, = Y{U(b,1) : b € B,,} then V,, is an open set in Z with B, C V, and
Ya NA = 0. Similarly, if W, = U{U(a,1) : a € A,} then A, C W,, andW. B = 0. Letv = [J (x — U w.
n=l

kin

and
W =

U

n=l

(w. —

yr.) »kin

It is easily checked that V and W are disjoint opensets with B C V andA C W. That completes verification of the example.
Theorem 4.2 [Hel. If there exists a separable nonmetrizable normal Moore
space then there exists a Q—set.
Proof. Suppose X is a separable normal Moore space which is not
metrizable. Let D = {d; : + € N} be a countable dense subset of X whered; £ d;, if i # j, and let {9.}F be a development for X where each Gn41 is
a refinement of G,,.

As in the remarks following the proof of Theorem 2.4 there must be an
uncountable closed discrete subset Z of X, where we may assume Z contains
no isolated points of X. For each t € Z pick a sequence s(t) = {s(t, n)}22,
of distinct elements of N such thatds(t,n) E st(t, On).

Let Y = {s(t) : t € Z}, considering Y to be a subspace of x22, N (irrational
numbers) with the product topology. To show Y is a Q—set, let A C Y and

let A‘ = {t e Z : s(t) € A}. Using normality of X find disjoint open sets
V, W in X such that A‘ C V and Z — A‘ C W. Now Z — A‘ =UR, B/,

where

B/ = {t€ Z :st(t,G8,) C W}.
To each B}, there corresponds B, C Y — A given by B, = {s(t) :t 6 B/}.
For each z € A‘ there exists k(z) € N such thatst(z, Ir(2)) C V.

For m € N let j{m, z) = max{m,k(z)}. For n € N let

T (s(z),n)= {s(t) EY : s(t,i) = s(z,i), 1 <i <n}.
This is just a standard neighborhood of s(z) in Y inherited from the producttopology. Define|

Ha =U{T(s(2).i(m,2)) : 2 € ‘}.

Each H,, is an open set in Y with A C H,,. We claim H,, |B, = 0, fromwhich it would follow that NZ., H,, = A, showing that A is a G@s5—set as
desired. Otherwise suppose there is some s(t) E H., B,,. Then t e Bi,, sods(i,) E st(t,9;) C W, all i > m. Also s(t) E H,, implies there exists z € A‘

where s(t) E T (s(z), j{(m, z)) so that s(t, :) = s(z,1) for all i < j{(m, z). For

notational convenience, let r = ;j(m, z). We have the following:ds(t.r) E st(¢, G,) C W,

s(t, r) = s(z,r), .
andds(z,r) E st(z,9,) C st(z, Gr») C V.

This is impossible since W {)V = 0. That completes the proof.
When Bing published Example 4.1 it was not known whether the ex—istence of a Q—set was consistent with ZFC. Lemma 2.3 shows that the
Q—set E used in 4.1 could not have cardinality c (cardinality of the contin—uum). This can also be seen directly from a simple cardinality argument.
If E C R with |E = c then E has 2° subsets but there can only be c
Gs—subsets of R. Hence some subset of E cannot be a relative (@5—set in E

and E is not a Q—set. This shows the existence of a Q—set can be consistent
only with —CH.
Q—sets were actually studied prior to [B;], at least by Rothberger [Ro](where the term "Q—set" is used) in 1948 and by Sierpiniski [Si] in 1938. In
his paper, Sierpinski shows that a positive answer to a question of Hausdorff([H], 1933) is equivalent to the existence of a Q—set. Hausdorff had asked
the following question: Given a set E with |E] = w; does there exist asequence { A;, A;, +>} of subsets of E such that for any X C E, X can be
expressed as
X = () U Ap(n)n=l k>nfor some sequence {p(n)}? in N? All together, Sierpinski and Rothberger
give several conditions equivalent to the existence of a Q—set. The Hausdorffquestion is mentioned so the reader can see how the early idea expressed inthis question is used in the proof of the existence of a Q—set (Theorem 4.4).
The reader should also refer to Tall [Ti] for a discussion of several equiva—
lences to the Q—set problem and a more complete history of events leading
up to its solution under MA (Martin‘s Axiom) plus not CH. To give a proofof the existence of a Q—set we rely on a lemma due to Solovay [MS], theproof of which can be found in [K].

Lemma 4.3 (Assume MA) Suppose B C P(w) where w < |B| < 2" andfor any a,b, E B, if a £ b then |af)bl| < w. If A C B there exists d C w

such that |a {}d| = w for all a € A and |b{Yd| < w for all be B — A.

The theorem showing consistency of the existence of Q—sets is apparently
due to J. Silver who, after hearing of the question by F. Tall, used resultsof Solovay to finish the problem. The proof below was given in [Rul.
Theorem 4.4 (Assume MA) If E C R with w < |E] <c then E is a
C —set.

Proof. There exists an open base W = {W; : : € w} for R such that forany distinct z, y € R, z and y appear in the same set W;, for finitely many :.

For z € E, let s(z) = {i € w : z € W,}. Clearly |s(z#)Ns(y)| < w if z #4.

Let B= {s(z) : z € E}. Given X C E, let A = {s(z) : z € X}. By

Lemma 4.3 there exists d C w such that |s(z) d| = w, for all z € X and[s(z) {d| < w, for all z e E— X. If d= {p(1), p(2), +++}, where p(i) # p(j),if i # j, then X = (NZ: Uk>n Woos) ((E. This says that X is a relative
Gs—set in E, completing the proof.
_|
This finishes the normal Moore space problem for the separable case,that is, it shows that the existence of a separable normal nonmetrizable
Moore space is independent of ZFC.
Before leaving the notion of a Q—set there is another interesting example
that should be described. This example is the basis for the result by R. W.
Heath in [He] that if every metacompact normal Moore space is metrizable
then every separable normal Moore space is metrizable. In other words,
the existence of a Q—set implies the existence a metacompact normal non—metrizable Moore space. This was especially interesting at the time because
Heath showed that the metacompact Moore spaces were exactly the regularspaces with a uniform base [A] and the "Russian school of topology" wasinterested in the normal uniform base analogue of the normal Moore space
problem. Recall that a space X is metacompact if every open cover of X
has a point finite open refinement.
Example 4.5 Assuming the existence of a Q—set there exists a metacom—
pact normal Moore space which is not metrizable.

Proof. If E is a Q—set let X = (R ® (0,c0))U(E x {0}). Describe a

topology on X by isolating all elements (p1,p;) E X for p, > 0 and for
P= (71,0) € E x {0}, n € N, letV(prn)={(2,y) :y = Iz — pil. y <1/n}be a basic neighborhood of p. X is clearly a Moore space. Normality
would follow from an argument similar to that used in Example 4.1 andmetacompactness follows by noticing that any canonical cover of X bybasic open sets has point order < 2. If X was metrizable, it would becollectionwise Hausdorff. So for each p E Ex {0} (a closed discrete set) there
would be n, € N such that V(p,n,)MNYV(q, n,) = 0 whenever p,q € E x {0},p # q. Since E x {0} is uncountable there would be some k 6 N and
uncountable B C E x {0} where n, = k for all p e B. This would imply\pi — q4i| > 2/k for all (1,0), (q1,0) E B, pi # qi, which is impossible.
Hence X is not metrizable.
Notice that an example with properties as in 4.5 could not be con—structed so as to be separable. This follows since separable metacompact
spaces are Lindelof.

5The "Provisional Solution" and dependence on large
cardinals.

After consideration of the separable case, attention to the general problem
of metrizability of normal Moore spaces suggests several questions. Is therea real example of a normal nonmetrizable Moore space (i.e., one using noaxioms other than ZFC)? Is there a consistent axiom which would imply
that every normal Moore space is metrizable? What are the relationships
between the properties of normal, collectionwise normal, and collectionwise
Hausdorff? The reader is referred to the article [T;] by F. Tall for a com—prehensive study of results on the last question, many of which are deeply
embedded in set theory.
One important result which seemed to be relevant to all three questions
was given by W. G. Fleissner in [Fi]. Using the "Axiom of Constructibility"(V=L) Fleissner shows that any normal space of character < c (hence any
normal first countable space or any normal Moore space) is collectionwise
Hausdorff.

Theorem 5.1 [F,]. (Assume V=L) If X is a normal space with character< c then X is collectionwise Hausdorff.
Besides the direct force of this result, showing that some normal spaces
can be expected to have collectionwise separation properties, this theo—
rem shows that any example of a normal nonmetrizable Moore space, con—structed in an axiom system consistent with (V=L), would have to becollectionwise Hausdorff. Such examples could not be as simple as Exam—ple 4.1 which was not metrizable simply because it was not collectionwise
Hausdorff.
To illustrate that normal collectionwise Hausdorff spaces need not becollectionwise normal, Fleissner provided the following example:
Example 5.2 [F3]. A normal collectionwise Hausdorff not collectionwise
normal space.

At this time, set theory, through the use of consistent axioms, has beenheavily involved with various aspects of the Normal Moore Space Problem.
In 1977, however, P. Nyikos discovered that an axiom dependent upon large
cardinals would give a "provisional solution." Nyikos [N;] used the ProductMeasure Extension Axiom (PMEA) to prove that all normal Moore spaces
are metrizable. Nyikos used the term "provisional solution" because PMEA
implies the existence of a measurable cardinal so it will be impossible toprove the consistency of this axiom within ZFC. It is known that consistencyof PMEAwould follow from the existence of a strongly compact cardinal.
See [Fs] for a discussion of the status of PMEA and other applications of
this measure extension axiom.
10The Product Measure Extension Aziom says that for any set A the usual
product measure on 24 (= xuea{0,1}) can be extended to a c—additive
measure 4 defined on all subsets of 24. That is, u would be a measuredefined for all subsets of 24 such that(i) u(U) = 27" whenever U is a basic product neighborhood in 24
restricted at k coordinates;(ii) whenever { B, : a E k} is a disjoint collection of subsets of 24 and|| < C then B(WUaer Ba.) —— Zlo«<rx (B.).

Theorem 5.3 [N,]. (Assume PMEA) Any normal first countable space X
is collectionwise normal; hence any normal Moore space is metrizable.
Proof. Let C= {C, : a € A } be a closed discrete collection of subsetsof the normal first countable space X. Assume C, # C; if «a # B. Eachf e 2" divides [JC into two disjoint closed subsets by letting

A; = {C. : f(e) =0}
and

B; =|U{C.: f(c)=1}.

By normality, find disjoint open sets U;, V; in X so that A;, C U; andB; C V;. Each p E X has a decreasing open local base {B(p,n) : m C
N}. For p E JC find m(p, f) E N where either B(p,m(p, f)) C U; orB (p, m{(p, f)) C V;. For k € N letE(p, k) ={ f e2 : m(p,f) < k}and notice that U2, E(p, k) = 2". If p is the measure on 2* guaranteedby PMEA there is k(p) € N where u(E(p,k(p)) > 7/8. Thus for all p,q,
p € Ca, q € Cp, « £ B,

u (E (p. k(p) \E(g. k(q))) > 3/4.
Consider the set Dy; = {f c 2" : f(a) = 0, f(B) = 1 } a basic neighbor—hood in 2", restricted at coordinates a and #. Since u(Dag) = 1/4, there

must exist some g E DagME (p, k(p)MNE(g, k(q)). Now, g(a) = 0 andg E E (p, k(p)) implies B(p, k(p)) C U,. Also, g(B) = 1 and g € E(p, k(p))

implies B (q, k(q)) C V, so we have B (p, k(p))MNB (q, k(q)) = 0. For a € A
let|

Wa =U {B(p. k(p)) : pe C.}.
The argument above shows that W. | Ws = 0, if a # #, so {W, : a € A }is the desired collection of open sets separating {C, : « € A }.
11

The above theorem by Nyikos left open the possibility that a positive
answer to the Normal Moore Space Problem might be obtained througha consistent axiom such as V=L. This was not to be, however, since W.
Fleissner has shown [Fs] that a large cardinal assumption cannot be avoided.
Related to this discovery and interesting in its own right was the construc—tion, by Fleissner, of a normal nonmetrizable Moore space assuming thecontinuum hypothesis.
Example 5.4 [F,]. Assuming CH there is a normal nonmetrizable Moore
space.
This should be contrasted with the situation for separable normal Moore
spaces. Under CH, separable normal Moore spaces are metrizable and ex—_ amples of separable normal nonmetrizable Moore spaces were found assum—ing MA + —CH.
After the construction of Example 5.4, Fleissner showed the example
could be constructed using an axiom weaker than CH, an axiom following
from the assumption that no inner model of set theory contains a measur—
able cardinal. The contrapositive of this implication yields the following
theorem.
Theorem 5.5 [Fs]. If all normal Moore spaces are metrizable, then there
is a model of set theory containing a measurable cardinal.
References[A]

P. S. Aleksandrov, Some results in the theory of topological spaces,
obtained within the last twenty—five years, Russian Math. Surveys
15(1960), 23—83.

[Bi]

R. H. Bing, Metrization of topological spaces, Canad. J. Math.
8(1951), 653—663.

[B;]

R. H. Bing, A translation of the normal Moore space conjecture, Proc.
Amer. Math. Soc. 16(1965), 612—619.

[Bu] D. K. Burke, PMEA and first countable, countably paracompact
spaces, Proc. Amer. Math. Soc. 92(1984), 455—460.
[C])

P. J. Cohen, The independence of the continuum hypothesis I, II,
Proc. Nat. Acad. Sci. U.S.A. 50(1963), 1143—1148; 51(1964), 105—
110.

[E])

R. Engelking, General Topology, Polish Scientific Publishers, Warsaw,
Poland, 1977.

12

[Fi]

W. G. Fleissner, Normal Moore spaces in the constructible universe,
Proc. Amer. Math. Soc. 46(1974), 294—298.

[F2] W. G. Fleissner, When is Jones‘ space normal?, Proc. Amer. Math.
Soc. 50(1975), 375—378.
[Fs]

W. G. Fleissner, A normal collectionwise Hausdorff not collectionwise

normal space, General Topology and Appl. 6(1976), 57—64.

[Fa] W. G. Fleissner, Normal nonmetrizable Moore space from continuum
hypothesis or nonexistence of inner models with measurable cardinals,
Proc. Nat. Acad. Sci. U.S.A. T79(1982), 1371—1372.

[Fs]

W. G. Fleissner, If all normal Moore spaces are metrizable, then there

is an inner model with a measurable cardinal, Trans. Amer. Math.

Soc. 273(1982), 365—373.

[Fe]

W. G. Fleissner, The Normal Moore Space Conjecture and large car—dinals, Handbook of Set—theoretic Topology, ed. by K. Kunen and J.
Vaughan, North Holland, Amsterdam, 1984.

[G]

K. Godel, The consistency of the continuum hypothesis, Annals of
Mathematics Studies, no. 3, Princeton University Press, Princeton,
1940.

[H]

F. Hausdorff, Probléme 58, Fund. Math. 20(1933), 286.

[He]

R. W. Heath, Screenability, pointwise paracompactness, and metriza—tion of Moore spaces, Canad. J. Math. 16(1964), 763—770.

[J1]

F. B. Jones, Concerning normal andcompletely normal spaces, Bull.
Amer. Math. Soc. 43(1937), 671—677.

[J2]

[K]

F. B. Jones, Remarks on the normal Moore space metrization problem, Annals of Mathematics Studies 60(1966), 115—120.

K. Kunen, Set Theory:An Introduction to Independence Proofs,
North—Holland Publishing Co., Amsterdam, 1980.

[MS] D. A. Martin and R. M. Solovay, Internal Cohen extensions, Ann.
Math. Logic 2(1970), 143—178.

[Mo] R. L. Moore, Foundations of point set theory, Amer. Math. Soc. Col—log. Publ. Vol. 13, 1962.

[Na] J. Nagata, On a necessary and sufficient condition of metrizability,
J. Inst. Polytech. Osaka City Univ. 1(1950), 93—100.

[N1] P. Nyikos, The normal Moore space problem, Topology Proc. 3(1978),473—493.

|13

[N;] P. Nyikos, A provisional solution to the normal Moore space problem,
Proc. Amer. Math. Soc. 7T8(1980), 429—435.
[RZ] G. M. Reed and P. Zenor, Metrization of Moore spaces and general—ized manifolds, Fund. Math. 91(1976), 203—210.
[Ro] F. Rothberger, On some problems of Hausdorff and of Sierpinski,

Fund. Math. 35 (1984), 29—46.

[Ru] M. E. Rudin, Lectures on set theoretic topology, CBMS Regional Conf.
Series in Math. no. 23, 1975.

[RuS]) M. E. Rudin and M. Starbird, Some examples of normal Moore
spaces. Canad. J. Math. 29(1977), 84—92.
[Si]

W. Sierpinski, Sur un probléme de M. Hausdorff, Fund. Math.

30(1938), 1—7.

[Sm] Y. M. Smirnov, A necessary and sufficient condition for metrizabilityof a topological space, Dokl. Akad Nauk (N. S.) T7(1951), 197—200(Russian).

[T;]

F. p. Tall, Set—theoretic consistency results and topological theorems
concerning the normal Moore space conjecture and related problems,
Ph.D. Thesis, University of Wisconsin, Madison, 1969.

[T;]

F. D. Tall, Normality vs. collectionwise normality, Handbook of Set—
theoretic Topology, ed. by K. Kunen and J. Vaughan, North Holland,
Amsterdam, 1984.

14

Texas Tech University, Mathematics Series
Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

Matrices and Representations

over Rings of Analytic Functions
and other one dimensional Rings
Robert M. Guralnick*This article is based on some lectures given by the author during a visit
to Texas Tech University in April 1986. I would like to thank Texas Tech
University for its invitation and for its warm hospitality during my visit.

1

Introduction

Suppose © is a noncompact Riemann surface (e.g. a domain in thecomplex plane). Let R denote the ring of holomorphic functions on 2. If A
and B are n x n matrices over R, they are said to be pointwise similar on
if A(z) and B(z) are similar for each z in 2. It is easy to construct pointwise
similar matrices which are not similar. However, it does imply that A and
B are similar on some smaller surface ‘, and under certain circumstances,

one can prescribe that a fixed point z is in ¢‘ (see [(Wal,[OS],[G1]).

We wish to consider a stronger condition—local similarity. Say A and B
are locally similar if for each z € , there exists a neighborhood " of z suchthat A and B are similar over the ring of holomorphic functions on ‘. Thisis equivalent to asserting that A and B are similar over localization of R
at P,; = { f | f(z) = 0} for each z € N (this is not obvious). We shall show
(Theorem 4.1) that this is equivalent to A and B being globally similar. In
Section 5, we apply this to obtain results about pointwise similarity.
In order to solve this problem, one needs to consider representations offinitely generated R—algebras. We show (Section 3) that R satisfies somevery nice algebraic properties. In particular, R is Bézout, has one in thestable range, and its quotient field has trivial Brauer group. We study the
problem in an algebraic setting.
|
The problem can be generalized to the case of a commutative ring R.
One replaces 2 by a subset of Spec R. In Section 4, we establish suffi—
cient conditions for a local—global principle to hold (which includes ringsof analytic functions). In Section 6, for a certain class of rings (includingorders over Dedekind domains), we describe a method for determining by*Supported in part by NSF grant DMS 8401008

15

how much the local—global principle fails. These results have applications
to various cancellation problems.
These types of problems can all be viewed as studying representations
which become equivalent under certain extension of scalars. This pointof view is discussed in Section 7. In particular, we give a proof of the
Noether—Deuring Theorem.

2

Some Preliminary Results

In this section, we state and prove some results which will be usefullater. Let R be commutative ring with 1. Then Spec R is the set of prime
ideals of R. If A is an R—algebra and M and N are A—modules, write
M, = M ®r R,,where R, is the localization of R and P for some P in
Spec R. So M, is a A,—module. The Krull dimension of R is the maximum

length of a chain of prime ideals in R. We say that one is in the stable
range of a ring S if az + b = 1 implies a + by is a unit for some y in S.
This definition is left—right symmetric (this is not obvious). We first record
some properties of zero dimensional rings (i.e., maximal ideals are minimal
primes). See [GW] for proofs. In particular, the result applies to local
rings.
Lemma 2.1 Let J be the Jacobson radical of R, and assume that R/J has
Krull dimension zero. Let A be a module finite R—algebra. Let M be a
finitely generated A—module.
(a) One is in the stable range of E = End,(M).
(b) If N and X are finitely generated A—modules, then MOX = NOX
implies M Z N.
(c) Let tM denote t copies of M. Then tM Z tN implies M % N.
(d) If M and N are finitely presented, then Mp > Np for all P in
Spec R implies M % N.
Lemma 2.2 Let A be a finitely generated R—algebra.
A—modules which are finitely generated as R—modules.

Let M and N be(a) E = Enda(M) is a direct limit of module finite R—algebras.
(b) If R is noetherian, then Homa(M, N) is a finitely generated R—
module.
(c) If R is a Priifer domain (i.e. finitely generated ideals are pro—jective) and M and N are R—projective, then Hom,(M, N) is+ finitely
generated as an R—module.

16

Proof: (a) follows from the observation that E is the homomorphic
image of a subalgebra of M,,(R), the ring of n x mn matrices over R. (b)is obvious. Let A1, — ++, A, be generators for A over R. Consider the exact
sequence|
0 — Hom,(M, N) — Homa(M, N) —> @ Homr(M, N),
i=1

where T(0) = (0A1 — A10, * ,0A, — A,0). Since M and N are finitely gen—erated projective modules, so is Homp(M, N). Since R is Priifer, the imageof r is projective, and so Homa(M, N) is an R—summand of Homg(M, N).
In certain situations, one only wants to work with a subsetof Spec R(e.g., if R is a ring of functions on Q). The next result says this is sufficientunder suitable conditions.

Lemma 2.3 Assume R is a Priifer domain. Let A be a finitely gener—
ated R—algebra. Let M and N be A—modules which are finitely generated
projective R—modules. Suppose Q is a subset of Spec R such that if I isa finitely generated ideal of R, then I is contained in some element of N..
Then Mp S Np for all P in Q implies Mp Z Np for all P in Spec R.
Proof: First assume that M and N are free.

Since Mp Z Np for

P in 9, this implies M & N as R—modules. Thus one can define thedeterminant of an element in Homp(M, N). By Lemma 2.2, there exists
Ci,...,0, a set of R—generators for Homr(M, N). Define f(x, <>,z,) =det(z101+<++z,0,). Since Mp Z Np for P in , f takes on values outsideof P. Hence by hypothesis, the coefficients of f generate R as an ideal. Let
P be in Spec R. If R/P is infinite, then clearly f represents an element not

in P, and so Mp 3 Np. If R/P is finite, pass to a faithfully flat extension

S in which f does represent a unit (e.g. take S to be R[z], localized at
the set of polynomials whose coefficients are not contained in any maximal
ideal). Then M ®2 S Z N ®r S and so by the Noether—Deuring Theorem(see Section 7), Mp 2 Np for all P.
If M and N are not free, choose projective R—modules M‘ and N‘ suchthat M @ M‘ and N © N‘ are free R—modules of the same finite rank. We
can assume that A is a free R—algebra. Extend the action of A to M‘ and N/‘
by letting the generators act trivially on them. By the previous paragraph,
M & M‘ is locally isomorphic to N © N‘. Clearly M‘ and N‘ are locally R—
isomorphic (and hence locally A—isomorphic). By local cancellation (Lemma
2.1(b)), this implies M and N are locally isomorphic.
Lemma 2.4 Let A be an R—algebra and M a finitely presented A—module.

(a) If R‘ is a flat commutative estension of R, then Homy(M‘, N‘) >Homa(M, N) ®r R‘, where A‘ = A Qr, R‘.

17

(b) The map 0: N > Homa(M, N) is an additive bijection from thecategory of A—modules which are summands of tM for some t to
the category of finitely generated projective E = End,(M)— mod—ules. Moreover, 0 also induces a bijection between the genus of M,

G(M) = {N | Np 2 Mp for all P} and G(E).

Proof: This is well known. Note that M®zgHom,(M, N) Z N (via m@0 «—o(m)). See also [G2].
We remark that if R is a domain (or more generally reduced with only
finitely many minimal primes) and M and N are finitely generated torsion

free R—modules, then (a) and (b) also hold (cf. [W2, 3.5]).

If A is a ring, we say that mn is in the stable range of A if aX + <+a,A + BA = A implies there exist A1, ++, A, € A with A = X(a;+ BA;)A.
If this holds, write sr(A) < n. The next proof is based on [G, 4.4].
Lemma 2.5 Suppose A is a subring of T and I is a common two sided
ideal of A and T‘. Then sr(A) < maz{sr(IP), sr(A/I)} =n.

Proof: Assume arA +++++ a,A + BA = A. Since sr(A/I) < n, there
exist a} = a; + Pa; with «jA +++ a‘, A +I = A. So we can assume a,; = a}.
Thus
1 = (LZa;b;) + d

for some b; € A and d E I. Also, there exist c, c; € A with
1 = Sa;c;+ Ac.

Thus d= Za;c;d + Ped, whence

1 = Hab; + Hasce:id + Bed = Fai(b; + cid) + Bed
So by replacing # by Acd, we can assume B E I. Set e; = b; + c;d. Then
ZDa;e; + B = 1. Squaring this expression yields Za;A + 3*A = A. Sincesr(I‘) < n, this implies that XZ(a; + A°f;)P = T for some f; 6 T. Theng; = Bf; € I C A. Set J = S(a; + Ag;)A. Then JT = T, and J 35 JI =JIT = JTI = I. Since J + I = A, this implies J = A, as desired.
We shall need the next well known result for reference (cf. [W2]).
Lemma 2.6 Assume st(A) = 1. If P is a finitely generated projective
A—module, then st(End, (P)) = 1. In particular, st(M,,(A)) = 1.
One can ask about the stable range of other overrings. It is apparently
still open as the whether integral extensions of commutative rings R withsr(R) = 1 also have this property. One case that is trivial to verify is thefollowing:18

Lemma 2.7 Let R be Bézout domain (i.e. finitely generated ideals are
principal) with quotient field K. If S is an overring of R contained in K,then sr(S) < sr(R). Also S is a Bézout domain.

We give an example to show that some hypothesis is necessary.
Example 2.8 Let T = k[u,v] be the polynomial ring in two variables
over a field k. Let R be the ring of polynomials T[z] localized at theset of primitive polynomials (i.e. polynomials f(x) = X a;xz‘ such thatT = y a;T). It is easy to verify that sr(R) =1 (c.., [VK]). Let R‘ = R[w_~‘],
where w = u* +v. We claim that sr(R‘) £ 1. Note that uR‘ + vR‘ = R‘,
Suppose that u + vt is a unit for some t € R‘. By multiplying by some unitof R‘, this yields
guw"u + vs = w* f,where m,n > 0, f and g are primitive polynomials in T[z] and s E T[z].
By substituting in v = 0, we obtain
Jou

Inr+1 _ ,,2m
— U fo,where fo, go are obtained from f, g by evaluation at v = 0. Thus either fo
or go is a multiple of u. However this implies that f or g is in the ideal ofT[xz] generated by u and v. This contradicts the primitivity.
Lemma 2.9 Let S be a ring with T a two sided ideal. If T :s semiprime
and artinian as a left S—module, then T is generated by a central idempotent.
Proof: Let I be a minimal left S—ideal of T.

Since T is semiprime,

TI #0, so TI = 1‘ = I. Also if I‘ is a nonzero left ideal of T contained inI, then TI is S—invariant, so as TF # 0, I‘ = I. Thus as T is artinian as
an S—module and every minimal submodule of T is a summand, it follows
that T7 is artinian semisimple. In particular, T = eT = Te, where e is theidentity of T. If s € S, then es = ese = se, and the result follows.

Proposition 2.10 Let R be a Priifer domain such that (R/I)/rad(R/I)
is von Neumann regular whenever I £0. Let T be the R—torsion ideal of amodule finite R—algebra A. Let J be the Jacobson radical of A. If JNT = 0,then A = T & Ap (as rings), where Ap is the annthilator of T.
Proof: Since R is Priufer, T is an R—summand of A, whence finitely

generated. So fT = 0 for some nonzero f in R. Let K/fR be the radicalof R/fR. Thus KT = 0 and R/K is von Neumann regular. If P is a
maximal ideal of R, then Tp is finite dimensional over R/P. Moreover, Tp
is semiprime. Thus the result holds locally by Lemma 2.9, whence globally.

19

3

Properties of Rings of Holomorphic Functions

Throughout this section Q will denote a noncompact Riemann surface
R = H(M), the ring of holomorphic functions on , and K = M(), thefield of meromorphic functions on 2. If z C Q, let P, ={ f € R| f(2) = 0}.
Let R, denote the localization of R at P,. This is somewhat smaller thanR;, the ring of germs of analytic functions at z, which is contained in thecompletion of R,. Note that this completion is the ring of formal power
series. We record some properties of AR.

Lemma 3.1 ([F, Theorem 25.5]) Given a discrete subset X of 2 and non—negative integers mn,;, x E X, there exists f E R such that the multiplicity
of f at z is ny,.
Lemma 3.2 R, is a local principal ideal domain.
Lemma 3.3 (Strong Approximation) Let X be a discrete subset of Q.
Then given positive integers n,, x E X and functions f, holomorphic about
x, there exists f C R such that f = f, mod (P,)"*. Moreover, if f,(x) £ 0
for each xz E X, we can choose f to be a unit of R.
Proof: Choose h E6 R such that X is exactly the set of zeroes of hand that the order of the zero is n,. Let U, = (2 — X) U {z}. Then
{U,} is an open cover of Q. Define a meromorphic function g, = f, /h on
U,. If z £ y, then g,; — g, is holomorphic on U, NU, C 1 — X. Henceby [F, Theorem 26.3], there exists a meromorphic function g on 2 with
4 — 9; holomorphic on U, for all z E6 X. Set f = gh. Then on U;,
J = gh = (g — gz)h + gsh = (g — g:)h + f.. Since g — g, is holomorphic on
U,, so is f. Thus f € R. Since h E (P,)"**,f = f, mod (P,)"*.
Moreover, if f,(x) # 0 for each z E X then f, = e* mod (P,)"* forsome analytic d,. Hence by the previous paragraph, there exists d E R
with d = d, mod (P,)"* for each z, and so f = e* = f, mod (P,)"**, with fa unit.

Recall that a ring is Bézout if every finitely generated ideal is principal.

Lemma 3.4 (a) If f,g E R with no common zero, then f + gh is a unit of
R for some h e R. (b) R is Bézout.
Proof: For part (a), let X be the set of zeroes of g. This is discrete (ifg £0). Since f does not vanish on X, by the previous result, there exists
a unit u € R such that u = f mod (P,)"*, where n, is the multiplicity ofthe zero of g at z. Hence h = (u— f)/g E R, and u = f + gh, as desired.
For part (b), let f, g 6 R. Let X be the set of common zeroes of f
and g. Choose h such that Ah vanishes only on X, and the order of thezero is the minimum of the orders for f and g. Then f/h and g/h C R
and have no common zeroes. So by (a), 1 = a(f/h) + b(g/h) in R. Hence20

fR + gR = hR. We wish to apply these results to certain extensions of R
by means of the following:
Proposition 3.5 Let K‘ be a finite dimensional field extension of K. Then
there exists a finite branched covering ¥ of 1 such that K‘ is the field of
meromorphic functions of Q‘. If R‘ is the ring of holomorphic functions on
Q‘, then R‘ is the integral closure of R in K‘.
Proof: The first statement is [F, Theorem 8.12]. The fact that R‘ is theintegral closure of R follows from [F, Theorems 8.2 and 8.3].

Corollary 3.6 Let R be the integral closure of R in the algebraic closureof K. Then(a) R is Bézout,(b) st(R) = 1, and(c) R satisfies the primitive criterion (i.e. given f(x) = Ca;z‘ € Riz]with R= y a;R, then f represents a unit in R).
Proof: (a) and (b) follow from the two previous results. Now (c) follows

from (a) and (b) by [G3, Lemma 5.2] .

Note that R itself does not in general satisfy the primitive criterion (see[EG, Example 5.51.)
The next result shows that no division rings arise over K. The following
proof is based on a letter of M. Artin. By an R—order in a K—algebra A, wemean an integral subalgebra A such that KA = A.
Proposition 3.7 Let A be a simple finite dimensional K—algebra. If T ismazimal R—order of A, then T Z M,(R‘) (and A > M.,(K‘)), where K‘ isthe center of A and R‘ is the integral closure of R in K‘. In particular, K
has trivial Brauer group.
Proof: By Lemma 3.5, we can assume K = K‘. Since R, is a discrete

valuation ring with algebraically closed residue field and the group of units
is divisible, it follows that the Brauer group of its quotient field K, is trivial(this also completes the proof if Q is simply connected—use Lemma 3.1
instead of the fact that R, is a local pid.)
Suppose dim A = »‘. Then T‘; = T ®z2 R, is a maximal order in A, Z

M,,(K,). Since R, is a pid, T‘, > M,(R,). Thus there exists an open cover
O of Q such that for U E O, $y : Ty — M,,(Ry) is an isomorphism,
where Ry is the ring of holomorphic functions on U. If U,V e O withU NV nonempty, then $y and gy are two representations of T‘uny = T ®r
Runy onto Mi(Runy). Since Ruyny is Bézout, any two representations areequivalent. Hence «(U, V)py = gya(U, V) for some a(U, V) € GL,,(Ruyny).
Moreover a is uniquely determined up to a scalar. It is straightforward21

to verify that a 6 H‘(M,PGL,), where PGL, is the (nonabelian) sheaf
associated to PGL, (R).
Consider the sequences of sheaves|exp

1 — Z — ¥ — H* — 1, and1 — Y* — GL, — PGL, — 1,
where H is the sheaf of germs of analytic functions and H* is the sheaf
on nonvanishing germs of analytic functions. Since H*(Q, U) = 0 (c.., [H,

p. 178]) and H°(Q, Z) = 0 (by dimension), it follows that H°(M, M*) = 0.

Since H‘(X, GL,) = 0 (c.., [F, Corollary 30.5]), we have H‘(X, PGL, ) = 0.

Hence «(U, V) = B(U)B(V)~‘ for some A 6 H°(X,PGL,). Now replace$v by B(U)~‘ ¢;B(U) (this is independent of the lift of (U) to GL, (Rpy)).

Then $y = gy on U NV. Thus ¢ defines a global map from I into M, (R).
Since ¢ is locally an isomorphism, it is globally, and the result follows.
In the case 2 is a compact Riemann surface, the triviality of the Brauergroup is a classical result of Tsen. In fact Tsen proves that the field satisfies
certain stronger properties. We do not know if this is still true in thenoncompact case. One can derive results about quadratic forms and the
Witt ring of K from Proposition 3.7. For example, it follows that any
quadratic form in two variables is universal (i.e. az* + by" =c always has asolution for ab # 0 in K), and so any quadratic form is a sum of hyperbolic
planes and either a one or two dimensional space.
We need to record some other properties of R. Recall that the Krull
dimension of a commutative ring is the maximum length of a chain of prime
ideals.
|
Proposition 3.8 If I is a nonzero ideal of R, then S; = (R/I)/rad(R/I)
is von Neumann regular.
Proof: Choose 0 £ f E I. By Lemma 3.3,
R/fR=Z|| R/(P,;)"**,zseZ(f)where Z(f) are the zeroes of f and n, is the multiplicity of the zero of fat z. Hence S; is a direct product of fields, and the result follows.
Proposition 3.9 Let K‘ be a finite dimensional field estension of K, and
let R‘ denote the integral closure of R in K. Suppose R C S C R‘ and S
has quotient field K‘.
(a) There exists 0 £6 C R‘ with 6R‘ C S.
(b) R‘ is a finitely generated R—module.

22

Proof: (a) follows just from the fact that K" is separable. Just choose

a in S with K" = K[al, and take 6 € R to be the discriminant of a.

For (b), observe that for each z, R, is pid so there exist A,,; E R‘, 1 <i < [K‘: K), with R‘ = § RA;,;. Choose A; € R‘ so that A; approximatesAz,; as closely as possible at each x in the zeros of 6. Let T = ) RA,; + Ra].

If z is not a zero of 6, then T, = R,[a]} = R; while if z is a zero of 6 thenT, = 3 R,A; = Rl (by Nakayama‘s lemma). From this, it is easy to deducethat T= R‘ is finitely generated.

4

One—Dimensional Rings Satisfying a Local—Global
Principle

In this section R will denote an integrally closed integral domain withquotient field K satisfying the following conditions for any finite dimen—
sional extension K‘ of K:(4.1a) The integral closure R‘ of R in K"‘ is Bézout.

(4.1b) sr(R) = 1.

|

(4.1¢c) Br(K‘) = 0.
(4.1d) If I is a nonzero ideal of R, then (R/1I)/ rad(R/I) is von Neu—mann regular.
(4.1e) If S is an R—subalgebra of R‘ with quotient field K‘, then 6R‘ C
S for some nonzero 6 E R.
Examples of such rings include the ring of all algebraic integers, the ringof holomorphic functions on a noncompact Riemann surface (see the pre—vious section), and semilocal domains whose quotient field is algebraicallyclosed, and the ring of all algebraic integers. The crucial conditions for our
purposes are (a) and (b). It may be possible to eliminate (c), and this ispossible when considering the problem of matrix similarity. One can avoid(e) by working in characteristic zero or in orders in separable K—algebras.
Fix a subset Q of Spec R such that if r E R is not a unit, then r E P
for some P in Q (e.g., if R is the ring of holomorphic functions onthen
Q suffices). The main result of this section is a local—global principle formodules over R—algebras.
Theorem 4.1 Let A be a finitely generated R—algebra (where R satisfies(4.1a—e)). Let M and N be A—modules which are finitely generated free
R—modules. The following are equivalent:(1) M, 3 Np for all P e 91.

(ii) M,, > Np for all P E Spec R
23

(iii) M > N.
Proof: Clearly (iii) implies (i). Since R is Bézout, (i) implies (ii) byLemma 2.3.
So assume (ii) holds. By Lemmas 2.2 and 2.4, we can assume M = A
and N is a projective A—module. Let A = A ®r K. Since A is a free
R—module, A embeds in A. Let J be the Jacobson radical of A, and set

I = AM J. Since I is nilpotent, A/I % N/IN if and only if A & N.

Moreover, since A/I is R—torsionfree, it is in fact R—free. So we can assume
A is a semisimple K—algebra. By (4.1c), A = © M(n;, K;), where K; is a
finite dimensional field extension of K. Let R,; be the integral closure of R
in K;, and set T = QR,. Then TA is a module finite T—algebra. So by(4.1a), TA = T & QM(n;, R;). Since T is finitely generated over T and
A = KA, there exists 0 £ d € R with dP C RA. Let Z = A NT. Let
Z, be the projection of Z onto R;. Since KZ = T, Z; and R,; have thesame quotient field. Thus 0 # fR; C Z, for some 0 # f E R. Let e; bethe central idempotent in R;. Then ge; € A for some 0 # g E R. HencegZ,; C gZe; C A. Thus gfdP C gfTA C A. Set c= gdf.
Let R, be the ring obtained from R by inverting all elements of R
relatively prime to c. Thus every maximal ideal of R, contains c, and so
R,, modulo its Jacobson radical is zero dimensional. Thus by Lemma 2.1,

A @r R., = A, Z N,. Since each R,; is Bézout, PN Z TA = TP, and so we
can assume that N C PN =T. Since A, Z N,,, it follows that N, = A,.a forsome & € A. Since T‘, = T.,N, = T.a, this implies a is a unit in I,. Without

loss of generality,. we can also assume that a E I‘. Hence ‘= aP + cl. By —(4.1b) and Lemma 2.6, sr(I) = 1, and so a + cy is a unit in |. Now
set L = A(a + cy). Note that if c ¢ P, then Lp = Tp = Ap = Np (ascP C A). Also J = (a+ cy)a~‘ z= 1 mod cl,. Hence # is a unit in A,.

Thus L, = A,« = N,. Thus N = L = A(a« + cy) Z A, as desired.
Corollary 4.2 Assume the hypotheses of the theorem,,(1) If tM Z +N, then M & N.

(ii) If M GX % N @ X for X a finitely generated A—module, thenM3 N.
Proof: The results hold locally (cf., [GW]), whence globally by thetheorem.

One other observation will be useful later.

Proposition 4.3 If A is a module finite R—algebra, then sr(A) = 1.
Proof: Since A is module finite, it is a homomorphic image of a subal—
gebra of M,, (R). So we can assume A C M,,(R). Moreover, we can assume
that the nilradical of A = 0. Hence A is an order in a semisimple K—algebra24

A. Let T be a maximal R—order in A. Then 1 = QM(n;, R;) where R; isthe integral closure of R in a finite dimensional field extension. As in the
proof of the theorem, 0 # cP C A, for some 0 # c € R. Since A/cT is a
module finite R/c algebra, and R satisfies (4.1d), it follows from [GW] thatsr(A/cl‘) = 1. By Lemma 2.6, sr(I‘) = 1. Hence by Lemma 2.5, sr(A) = 1.
One can give another proof using the theorem and results in [G3].
There is a cohomological interpretation of Theorem 4.1 which we state
without proof.
Corollary 4.4 Let R be the ring of analytic functions on a noncompact
Riemann surface. Let A be a module finite free R—algebrao. Let G be thesheaf associated to the group of units of A. Then H(M,G) = 0.
It is also worthwhile to note that when R is the ring of analytic func—
tions on a noncompact Riemann surface, there are several notions of local
isomorphism. One can consider the localization, the ring of germs at apoint, or the ring of formal power series. Since the latter two are faithfully
flat extensions of the first, it follows by Section 7 that all of these notions
are the same.
We close this section by observing that the result hold for modules aswell as lattices.
Corollary 4.5 Let R satisfy the hypotheses of (4.1). If A is a module
finite R—algebra and M and N are finitely presented A—modules such that
M, Z N, for all mazimal ideals P of R (or a sufficiently large subset), thenM 3 N.
Proof: By Lemma 2.4, we can assume M and N are projective. Let T be
the R—torsion ideal of R and J the Jacobson radical of A. So M & N if andonly if M/JM > N/JN. Hence we can assume J = 0. By Proposition 2.10,
A = Ao ©@T. Thus we can consider the two cases separately. If A = Ap,
Theorem 4.1 applies. If A =T, the result follows by [GW] or Lemma 2.1.

5

Pointwise Equivalence of Representations
In this section, we consider a weaker condition than local equivalenceof modules (or representations). Let R be a commutative ring with 1,
and fix a subset Q of Spec R. If a E R, let a(P) denote its image in
R/P (and similarly for polynomials, matrices, etc.) Let K(P) denote thequotient field of R/P. If A is an R—algebra and M is a A—module, set
M(P) = M @r K(P). So M(P) is a A(P) = A ®r K(P) module. If M and
N are A—modules such that M(P) Z N(P) as A(P)—modules for all P E 2,
we say M and N are pointwise isomorphic on Q. This is equivalent to sayingthat M ®_r S Z N ®gr S as A ®r S—modules, where S is the direct productof the K(P), P in Q. Since K(P) = Rp/PRp, Mp & Np as Ap—modules
20obviously implies M(P) & N(P). It is easy to see that M(P) = N(P)does not imply Mp & Np (e.g., take M = R and N = R/P). In fact, evenassuming M(P) > N(P) for all P 6
does not imply Mq Z No for all
Q e . Choose a maximal ideal P of R with z e P — P". Consider the
representations of R[xz] given be the two matrices,
0

z

o o

°°"

a

(°

#

\o o

J

The corresponding modules M and N satisfy Mo 3 No for all Q withz not in Q, M(P) > N(P), but Mp is not isomorphic to Np. Anotherexample is obtained by considering
A =

0
0
0

1
O
0

0
z
0

and A‘ .

Theorem 5.1 Let R be an integral domain with quotient field K. Assume
A is a module finite R—algebra and M and N are finitely presented A—
modules. Then the following are equivalent:(i) M(P) 3 N(P) for a dense subset Q of Spec R (i.e., |P = 0, P E(i) M @r K 2 N ®r K as A ®r K—modules.
(iii) M(P) 3 N(P) for a dense open subset of Spec R.
Proof: Assume (i) holds and set S= [[I K(P), P € 2. Since 2 is dense,
K embeds in K ®rm S8 =T. Thus M @x T 2 N ®_x T as A ® T—modules

where A = A®gK is finite dimensional K—algebra. By the Noether—Deuring
theorem (see Section 7), this implies M ®@pg K 3 N ®r K as A—modules. So(ii) holds.

If M ®r K & N ®r K as A ®r K—modules, then we can assume theisomorphism is given by a ® 1 for some a E Homa(M, N). L = kero andN/a(M) are both torsion modules. Since N is finitely presented, there
exists 0 # d e R with dN C o(M). Set R‘ = R[1/d]. Then a induces asurjection from M ®2 R‘ onto N ®@rg R‘. Since N ®@r R‘ is finitely presented,
L ®r R‘ must be finitely generated (as an R‘—module). Thus there exists
some nonzero multiple f of d with fL = 0. Thus a(P) induces an isomor—

phism form M(P) to N(P) for any P e % = {Q € Spec R | f ¢ Q}. Thisis the desired dense (and open) subset of R.
See [G1] or [OS] for some what different proof in the matrix case. One
can generalize this to rings other than domains.
In [Wal, [OS], and [G1], various conditions in the matrix case werediscussed which forced pointwise equivalence at P to imply local equivalenceon some neighborhood of P (which is the same as equivalence over Rp).

These can be extended.

26

Let A be a finitely generated R—algebra. If M and N are A—modules
which are finitely generated as R—modules, define vp(M, N) to be the small—
est nonnegative integer v such thatp: Homa, (Mp, Np) — Homa,(M(P), N(P))
and¢,: Homa, (Mp/P*"*‘*‘Mp, Np/P*"" Np) —> Homa,(M(P), N(P))

have the same image. If no such integer exists, set vp(M,N) = oo. It
follows from the Artin—Rees Lemma (cf., [G1]) that if Rp is noetherian,then vp(M, N) is finite. The following generalizes results in [Wal, [OS],and [G1].
Lemma 5.2 If vp(M,N)= 0 and Mp Z Np as Rp—modules, then M(P) =N(P) implies Mp Z Np as Ap—modules.

Proof: Let a be an isomorphism form M(P) to N(P). Since vp(M, N) =0, there exists a Ap—homomorphism 3 from Mp to Np such that the fol—lowing diagram commutes:

Mp
l

—>

Np
l

M(P) —> N(P).
Since a is surjective, it follows from Nakayama‘s lemma that 3 is surjective.
Since Mp Z Np as Rp—modules, this implies B3 is injective. Hence Mp Z
Np.
|
More generally, the proof of Lemma 5.2 shows that if vp(M, N) = v
and Mp 2 Np as R—modules, then Mp/P"*t‘Mp & Np/P"+‘Np implies
Mp Z Np (cf., [G1, Theorem 3.2].) Examples where vp = 0 include thecase where M is projective or A = RG, G a finite group, and M and N are
permutation modules.
In the case Rp is a principal ideal domain, one can explicitly computevp(M, N). We do this only in the torsion free case. So assume R is alocal principal ideal domain with quotient field K, A is a finitely generated
R—algebra M and N are A—lattices (i.e., A—modules which are finitely gen—erated R torsion free modules). Let H = Homp(M,N). Let z1,..., z; begenerators for A over R. Then there is an exact sequence
0 — Hom,(M, N) 4 tH
where T(a) = (0z1 — z10,...,0z; — z;0). So T is a linear transforma—tion between two free R—modules. Hence T has a matrix representation as
Diag (p",...,p*%,0,...,0) with e; < e; < ++ < e,, where P = pR is the27

maximal ideal of R. By tensoring this sequence with R/P!, it is easy to
see that vp(M, N) =e, and that s = rank T.
|
If N‘ is another A—lattice we get a corresponding map T". If N‘®r K =N ®r K and N‘/P"!N‘ % N/P""N, where v = vp(M, N), then T andT‘ are equivalent over K and also over R/P"*‘. Hence they are equivalentover R. Then vp(M,N) = vp(M, N‘). Combining this observation with
Lemma 5.2 yields:

Proposition 5.3 Let R be an integral domain with quotient field K. Sup—
pose A is a finitely generated R—algebra, M and N are A—modules, andP E Spec R such that Rp is a principal ideal domain and Mp and Np are

Rp—free modules of finite rank. Set v= vp(M,N). Then Mp Z Np if andonly if Mp/P"*‘ Mp = Np/P"*‘*Np and M(O) = N(O).

Proposition 5.3 shows that v depends only on M not on N. This is nottrue if Rp is not a principal ideal domain (see [G1]). However, one special
case does apply.

Proposition 5.4 Let R be an integral domain with quotient field K. Let
A be a finitely generated R—algebra. Assume M and N are A—modules suchthat Mp and Np are free Rp—modules. If vp(M, N) = 0, then M(O) 3 N(O)and M(P) 3 N(P) implies Mp & Np.
|
Proof: This is proved in the same manner as the previous result. Insteadof using the invariant factors, quote [G1, Theorem 3.1].
If A is an n x n matrix over R, then A determines an R[xz]—module M
isomorphic as an R—module to nR, where xz acts on M via multiplication
by A. Two matrices determine isomorphic modules if and only if they are
similar. Thus, one can define vp(A, B) for a pair of square matrices. Thereis a canonical form for matrices with vp(A, A) = 0.
Proposition 5.5 (G1, Theorem 5.2) Let A be an mn xn matriz over R.
Then vp(A, A) = 0 if and only if A is similar over Rp to

Ci

0

0

C:

where C; is the companion matriz of f;(x) in Rp[z] and f; f;41.
We can obtain global versions of the preceding results by using Section 4.
Let us say a commutative ring R is a weak L G—ring if whenever M and N are
A—lattices, then Mp 2 Np for all P E Spec R implies M Z N. In particular,
this includes the rings in Section 4, but also includes other classes of rings.
In particular, semilocal rings, or more generally rings R with R/ rad R von
Neumann regular satisfy this. See [EG] for other examples.
28

Theorem 5.6 Let R be a weak LG Priifer domain with quotient field K.
Suppose A is a finitely generated R—algebrao and M and N are A—lattices

with M ®r K % N ®rK as A ®r K—modules. Set Q‘ = {P C Spec R |vp(M, M) =:0 and M(P) 3 N(P) }. Then there exists a in R such that a is
not in P for any P in QX" with M@prpR[a‘] 2 N ®gR[a~‘]. In particular, M
and N are isomorphic an a dense open subset Q2" of Spec R with Q" 5 QV‘.
If " = Spec R, then M & N.

Proof: Let R‘ be the ring obtained from R by inverting all elements t
in R such that t is not in any element of ‘. It is an easy exercise to provethat R‘ is also a weak LG—ring. By Proposition 5.4, Mp & Np for all P in
Q‘. Observe that if 1 € R‘ is not a unit, then t € PR‘ for some P E ¥‘.
Since R (and so R‘) is Bézout (by the weak LG property), Lemma 2.3
implies that M ® Rp 2 N ®2 Rp as A ®r Rp—modules for all P in Spec R‘.
Hence M ®grg R‘ 2 N ®r R‘. Suppose ¢ is an isomorphism. Without loss ofgenerality, ¢ E Hom»,(M, N). Since M and N are R—free of the same rank,a = det ¢ is defined. Since ¢ is an isomorphism on R‘, a is a unit in R‘,
i.e., a is not in P for any P in Q‘. Let Q" = {P in Spec R | a is not in P }.
The last statement follows for if Q‘ = Spec R, then R = R‘.
In particular, we can obtain global versions of the matrix results ofWasow, Ostrowski, Friedland, Ohm and Schneider and the author. We
state these only for rings of analytic functions. There are obvious versions
for a larger class of rings as well as for sets of matrices.
Theorem 5.7 Let Q be a noncompact Riemann surface with R its ringof analytic functions. Let A and B be two n x mn matrices over R. Let
Q = {z € Q |v,(A, B) = 0 and A(z) and B(z) are similar}, and assume
Q‘ nonempty.
(a) (Generalization of Wasow) There exists an open codiscrete sub—manifold Qo D X‘ of 91 such that A and B are similar over Ro, thering of analytic functions on Ro.
(b) If X = 92, then A and B are similar over R.
(c) (Generalization of Ostrowski) Let Q; = { z | v,(A, A) = 0}. Then
A is similar to C, the rational canonical form on Q, (i.e., over the
ring R,; of analytic functions on Q,). Moreover, ; is an open codis—
crete submanifold of l.
(d) A is similar to C over R if and only if v,(A, A) = 0 for all z.
Proof: (a) is just a restatement of Theorem 5.6 in a special case. Now(b) follows from (a).
By [G1, Theorem 5.2], v,(A, A) = 0 if and only if A is similar over R,
to C. Then (c) follows from (a). In particular, if 1; = , the this implies
A is similar to C. Conversely, by [G1, Theorem 5.2], v,(C, C) = 0. So if A
is similar to C, then v,(A, A) = 0 also.
29

The earlier results mentioned above merely asserted the existence of aneighborhood of a point z € !‘ ( or 1) satisfying the conclusion.

6

The Genus Class Group and Cancellation

Let A be a module finite R—algebra. If M is a finitely presented A—
module (or R is reduced with only finitely many minimal primes and M
is a A—module which is a finitely generated torsion free R—module), define
the genus of M, G(M ) to be the collection of finitely presented A—modules
N with Mp & Np for all P in Spec R. By Lemma 2.4, this is in one to
one correspondence with G(E), where E = Enda (M). One can put a groupstructure on finitely generated projective E—modules (via Kp,(F)) which via
the bijection of Lemma 2.4 imposes one on

Div M = { N | N is a A—summand of sM for some s > 0} > G(M).
We wish to give a more explicit description of this group structure ina special case. The next result is essentially [W1, Theorem 3.2], (see also[G2]). Write MIN to indicate M is isomorphic to a summand of N.
Lemma 6.1 Let R be a commutative ring of Krull dimension one with only
a finite number of minimal primes. Let A be a module finite R—algebra. As—
sume that A, B, and C are finitely generated A—modules such that either
they are finitely presented or A is reduced and A, B, and C are R torsion—
free. If Cp|Ap and Cp|Bp for each minimal prime P and Cp|Ap or Cp|Bp

for each mazimal prime P, then C|A & B.

Corollary 6.2 Let R, A and A be as in 6.1. If Bi, B, € G(A), there exist
Ci, C; € G(A) with B; @ B, % A QC; and B,; @ C, % A @ A.
Now assume R and A are as above and M satisfies the conditions ofLemma 6.1. If N E G(M), let[N] = {N‘ e G(M) | N‘ & kM = N © kM for some k} —(in fact k = 1 suffices). Now define [Ni,] + [N;] = [N3], where N3; @ M >N;, @ N,. This makes G(M) = {[N] | N ¢ G(M) } into an abelian group.

We wish to describe G(M) and obtain some consequences. If A C T are

two R—algebras with a common ideal I, we can compare G(A) and G(T)via a result of Milnor (see [B, p. 482]). In fact, in the case of interest forus, we can derive this fairly easily. The following will unify certain classicalresults for orders over Dedekind domains (c.f., [CR] and [G2]), ring orders(see [L], [WW]), and the results of Section 4. Let U(A) denote the groupof units of A.
So for the rest of this section, assume that A C T are rings such that:30

(1) 1 = ©Endz,(P;), where R,; is a one—dimensional Priifer domain
and P; is a finitely generated projective R—module,(2) T is integral over Z, the center of A.
(3) There exists an ideal I of Z such that I contains a regular element
and IR C A.

We wish to study certain A—modules. Let Lat A denote the categoryof finitely generated A—modules which are Z torsionfree (an alternativedescription is as follows: let K,; denote the quotient field of R;, and set= Q K,;; M is in Lat A if M embeds in KM = K ®@z M). Let PM ={X ¥mMm | ¥m ET, m e M} C KM. So TPM is a D—lattice. Since the genus
of PM is well understood (in terms of the Picard group of the R;), we focus
our attention on the kernel of G(M) — G(TM). We show that G(M) andG(M) coincide in the case under discussion.

Let D(M) = {N e G(M) | PN % TM }. We wish to describe D(M).
Set E = End,(M) C F = Endr(TM) C Enda(KM) = B, where A =K®zA. Note IF C E. If N E D(M), then we may assume N C PN = PM.
Let Z; denote the localization of Z at the set of regular elements which are
relatively prime to I. Then Z; is zero dimensional modulo its radical. Henceby [GW], N, 2 M; = (Z1 ®z M). Thus there exists a € B with N; = Mra.
Since PN = TM, this implies a € U(F;). Conversely given a E U(F;),
define N, = Mra NPM. Note if P E Spec Z, then (N,)p = Mp if P does

not contain I, while if P D5 I, then (N,)p = (Mp)a. Hence N, € G(M).

Also PN, = TM. Thus N, € D(M). It is straightforward to compute thatN., 3 N; & U(E;)aU(F) = U(E;)BU(F). Note that if a = B mod IF;,then N, = N5. Thus we obtain:
Proposition 6.3 There is bijection between D(M) and the set of double

cosets U(E/I)\U(F/I)/U*(F/I), where U*(F/I) is the image of U(F) inU(F/1T).

Since F > Endp(PM) 2 ©Endp,(P;) where P; is a finitely generated
projective R—module, we can define the determinant v: P — T = QR; —T/IT. Since F/IF is a direct sum of matrix rings over zero dimensionalrings, every element of determinant 1 is a product of elementary matrices
and hence is in U*(F/I). Combining this with Proposition 6.3 and applyingv yields:
Corollary 6.4 D(M) is in one to one correspondence with
U(T/I)/U*(T/I)A(M ), where A(M) is the subgroup of U(I) equal tov(U(E/T)).

Note that if T/I is finite, this implies D(M) is finite. Corollary 6.4
induces a group structure on D(M). To see that it is the same as theearlier one, we note that N, © N; £ Ny; ® M (set L = M & M, note both

N,@Ns and Nyg@M are in D(L), and compute v(Ny©N;3) = v(NagO@M).)
31

Theorem 6.5 Suppose M; and M; are faithful A—lattices. Then

A(M, © M;) = A(Mi )A(M2).
Proof: Let a = ( a 5 ) c U(E/IE), where E = Enda(M; © M;). If
«~! =

1

I

a h

, then dd‘ + eb‘ = 1 in E,/IE;, where Eq = End,(M;).

Since E; is integral over Z/I which is zero dimensional, it follows thatsr(E,/I) = 1. Hence u = d+ cb‘e is a unit of Ea/IF, for some e. Thus
a b

c d

1 be

0

1

1

0

0 ut"

1

0

—e 1

_

J

a* b*

0

1

J"

Hence v ( a ° ) = v(u)u(a*) € A(M;, )A(M3).
Corollary 6.6 If MOX % N@X where X is a summand of kM for somek, then M 3 N.

Proof: Without loss of generality X = kM and M is faithful. Thenby local cancellation, N € G(M). Since T‘ is Morita equivalent to T, wealso have PN Z PM. So N € D(M). Thus N Z N,, for some a. Set L =(k+1)M. Observe that N, @kM = L; where 8 = diag(a,1,...,1). Hence
Lg 3 L implies v(@) e A(L)U*(T/I) = A(M)U*(T/1), and so N, 2 M.

In particular, this implies G(M) = G(M).

Corollary 6.7 If MOX Z NOX, for some lattice X then MOP & N GT.
Proof: First assume M is faithful. As in the previous proof, N Z N.,

for some a. Thus v(a) € U(T/I) = A(M ©@T) = A(M)A(T‘). In the generalcase, we can replace M by M @I, and then apply Corollary 6.6.
There are many similar results that can be derived by these techniques.
We state some without proof. Most of these can be found in [G2] for orders
over Dedekind domains. The proofs are essentially unchanged except that
we use the fact that T/I is zero dimensional instead of the fact that in [G2],T/I is artinian.
|

Theorem 6.8(a) If Mp is isomorphic to a summand of Np for all
P E Spec Z, then N % M‘ @ N‘ for some M‘ € G(M).
(b) If L € G(M & N), then L % M‘ & N‘ for some M‘ E G(M) andN‘ e G(N).

(c) If L € G(tM), then L = (t — 1)M & M‘.

32

Theorem 6.9 If Mp is isomorphic to a summand of Np for all P in
Spec Z and the multiplicity of each A—composition factor in KN is strictly
larger than KM, then M is isomorphic to a summand of N. In particular,

if Mp is isomorphic to a summand of Np for all P and F is a faithful
A—lattice, then M is a summand of N © F.
Note that the results of Section 4 follow from Corollary 6.4. For ifsr(T) = 1, then U*(T/I) = U(T/I) and so |D(M)| = 1. So if N € G(M),then 7 Bézout implies PN Z TM, whence N E D(M), and so N & M.

Corollary 6.10 If M and X are faithful lattices, then the following se—quence is exact:

0 — D(M, X) — G(M) * G(M & x) — 0
where p(N) = N & X. Moreover,D(M, X) = A(X)/A(X)nU*(T/I)\(M).
In particular, if A = R, we obtain the results of [WW] on stable isomor—
phism classes.
Corollary 6.11 If M is a faithful R—lattice, then M & R Z N @ R if andonly if N 3 N.,, where v(a) E U*(T/I)A(M)A(R). If M has constant rankt, then M © RZ N G R implies tM 31tN .

|Note that if M has rank t, then A(M) 5 A(R)‘.

7T

The Noether—Deuring Theorem

As we observed earlier, most of the problems discussed here can bephrased in terms of ring extensions.
We fix some notation for this section. Let R be a commutative ring andA a module finite R—algebra. If R‘ is a commutative extension of R, letA‘ = R‘ ®r A. If M is a A—module, then M‘ = R‘ ®2 A is a A‘—module. The
question addressed here is: does M‘ > N‘ imply M % N ? The answer ingeneral is no. However, there is a positive answer when R is a field. Thiswas proved be Noether and Deuring. There have been manyextensions by
Reiner and Zassenhaus, Roggenkamp, Grothendieck, and others.
Theorem 7.1 (Grothendieck) If R is a local ring with mazimal ideal P,R‘ :s faithfully flat, and M and N are finitely presented A—modules, thenM‘Z N‘ implies M 3 N.

33

Proof: Let R = R/P, A = A/PA, M = M/PM, N = N/PN. Now
M‘ % N‘ clearly implies dim M = dim N. Since M and N are finitely
preseented, the isomorphism between M‘ and N‘ is given by 3° s;@®@0;, where
0; E Hom,(M,N) and s; 6 R‘. Define f(x1,...,z1) = det({ s;i0;) E
R[z;,..., z;], where 0; maps M into N. By hypothesis f(4;,—...,31) # 0.
Hence f £ 0. If R is infinite, this implies f(f1,...,7h) # 0 for somer; € R. Thus a = §©r;0; is surjection from M to N. Similarly, there exists
a surjection r from N to M. Hence To is a surjection from M to itself.
Thus T0 is an automorphism and so M 2 N.

If R is finite, pass to afree rank t finitely generated extension R" so that the residue field of R" issufficiently large that f represents a nonzero element in the residue field ofR" (take R" = R[xz]/g(x)), where g(x) is irreducible of large degree). Thenthe argument above shows M" Z N", and so tM = tN as A—modules. Then
M 3 N by [GW].
If the assumption that R is local is dropped, the result is no longer true.
The obstruction to this is exactly G(M). Also, note the same proof showsthat M"‘ N‘ implies M |N.
Corollary 7.2 If R‘ is a faithfully flat commutative extension and M and
N are finitely presented A—modules, then M‘ % N‘ implies N c G(M).
Conversely, if N E G(M), there exists a faithfully flat estension R‘ withM‘3 N‘.
Proof: The first statement is an immediate consequence of the theorem.
For the second one, take R‘ to be the direct product ofo the localization of
R (other extensions will suffice).
If faithfully flat is replaced by faithful finitely generated projective, thenby a result of Bass it follows that M‘ Z N‘ implies tM Z tN for some t.
It is apparently still open as to whether the converse is true. It is when R

is Dedekind [G2] and when A = M = R [BG]. If only finite generation isassumed then by an example of S. Wiegand, the corollary is false even for
R semilocal.
One can also derive similar results for modules as in Section 4. See [G2].

References[B]

H. Bass, Algebraic K—Theory, W.A. Benjamin, New York, 1968.

[BG] H. Bass and R. Guralnick, Torsion in the Picard group and extensionof scalars, J. Pure and Applied Algebra, to appear.
[CR] C. Curtis and I. Reiner, Methods of Representation Theory with Ap—
plications to Finite Groups and Orders, Vol. I, John Wiley and Sons,
New York, 1981.
34

[EG] D. Estes and R. Guralnick, Module Equivalences: local to global when
primitive polynomials represent units, J. Algebra 7T7(1982), 138—157.

[F]
[G]

O. Forster, Lectures on Riemann Surfaces, Springer—Verlag, New

York, 1981.

K.R. Goodearl, Power cancellation of groups and modules, Pacific J.

Math. 64(1976), 387—411.

[(GW)] K.R. Goodearl and R.B. Warfield, Jr., Algebras over zero dimen—

sional rings, Math. Ann. 223(1976), 157—168.

[G1] R. Guralnick, Similarity of matrices over local rings, Linear Alg. Appl.
41(1981), 161—174.

[G2] R. Guralnick, The Genus of a module II: Roiter‘s theorem, Power
Cancellation, and extension of scalars, J. Number Theory 26(1987),
149—165.

[G3] R. Guralnick, Power cancellation of modules, Pacific J. Math.
124(1986), 131—144.

[H]

L. Hormander, An Introduction to Complex Analysis in Several Vari—ables, Van Nostrand, Princeton, 1966.

[L]

L. Levy, Modules over Dedekind—like rings, J. Algebra 93(1985), 1—
116.
|[OS] J. Ohm and H. Schneider, Matrices similar on a Zariski open set,
Math. Z. 85(1964), 373—381.

VK] W. Van der Kallen, The Kof rings with many units, Ann. Sci. Ecole
Norm. Sup. 4(1977), 473—515.

[W1] R.B. Warfield, Jr., Epimorphisms to finitely generated modules,
preprint.

[W2] R.B. Warfield, Jr., Cancellation of modules and groups and stable
range of endomorphism rings, Pacific J. Math 91(1980), 457—485.

(Wa) W. Wasow, On holomorphically similar matrices, J. Math. Anal.
Appl. 4(1962), 202—206.

[WW] R. Wiegand and S. Wiegand, Stable isomorphism of modules over
one dimensional rings, J. Algebra 107(1987), 425—435.

35

Texas Tech University, Mathematics Series
Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

Automorphisms and Picard groups for
Hereditary Orders
William H. Gustafson

Klaus W. Roggenkamp*

Texas Tech University

1

Universitat Stuttgart

Introduction

In this paper we shall describe the Picard groups of hereditary orders anddetermine those bimodules that give rise to automorphisms. Let R be thering of algebraic integers in an algebraic number field K. Let A be anhereditary order in a semisimple K—algebra A. A A—A—bimodule M is said
to be invertible if there is another A—A—bimodule N such that M ®), N & A
and N ®, M Z A as bimodules. For an R—subalgebra T of the center Z(A),the isomorphism classes of invertible bimodules such that tm = mt for allt E T,. m e M form a group Picr(A), the Picard group of A, relative to T.
The elements of Picr(A) correspond to the T—linear self—equivalences of thecategory of left A—modules (cf., [1, Chapter 2, §5]). Our main interest is in
the two extreme cases: Picr(A) and the central Picard group Picent(A) =Picz(a(A). In this paper, we compute Picent(A) and the group Outc(A)of automorphisms of A that are trivial on C = Z(A), modulo the innerautomorphisms. Our basic tools are three exact sequences of Frohlich [5].

In these sequences, A, is the p—adic completion of A, CI(Z(A)) is the classgroup of the center of A, and (p is a mapping whose definition will be givenin §3. The exact sequences are:

0 — CI(Z(A)) — Picent(A) —»|||Picent(Ap) — 1,

(1.1)

J|]

(1.2)

pemax(R)0 — Clh(Z(A)) — Oute(A) &pemax(R)Oute(Ap),

where Cl, (Z(A)) = {(J) € CI(Z(A)) : JA is principal } and

0 — Picent(A) — Picg(A) <> Outr(Z(A)).

(1.3)

Our interest in these matters arose from the study of automorphismgroups of integral group rings [18]. It turns out that the group rings are*This paper was prepared while this author was an ESA Visiting Mathematician
at Texas Tech University.
He was also supported by a grant from the Deutsche
Forschungsgemeinschaft .

37sometimes fibre products, with one factor hereditary. In order to apply
the Mayer—Vietoris sequences we have associated to these fibre products,
we must compute Picard and outer automorphism groups of hereditaryorders.

Natural questions that arise in connection with these sequences are:

1. When is (1.1) split exact?
2. When is ro in (1.2) surjective?
3. If T, is surjective, when is (1.2) split?
4. When is (r in (1.3) surjective?
One of the main results of [17] (see also [16]) is that when A is the in—tegral group ring of a p—group P, (1.1) and (1.2) are split and Im(r) =Im(r,) = Outg(P), the group of automorphisms of P stabilizing the con—jugacy classes, modulo inner automorphisms.

2

Bimodules, automorphisms and class groups

Let R CT C Z(A) be an R—subalgebra of the center Z(A), where A is an R—
order in a semisimple K—algebra A. If a and 3 are T—linear automorphismsof A, we can form a bimodule ,A; which is A as R—module, and where theaction of A is twisted by a on the left and by 3 on the right. Thus,

Acc A= (ASQ)cz(AZ), A;, z € A.
Then, ,Ap is an invertible bimodule, and the elements of T act the same

way on both sides. We write 1 for the identity automorphism of A. An
inner automorphism of A is one given by A > uAu~‘, for a unit u of A.
The inner automorphisms form a normal subgroup Inn(A) 4 Autr;(A), andwe put Outr(A) = Autr(A)/ Inn(A). We now recall from [12, (37.14)]
Theorem 2.1 The map f;: Autr(A) — Picr(A) given by f() = (aA1)
is a group homomorphism whose kernel is Inn(A). Hence, 9 induces amonomorphism
n: Outp(A) — Picp(A).
In particular, ,Ai :s isomorphic to A as bimodule if and only if a is an
inner automorphism.
Let B be a simple K—algebra with center L, and let S be the ring of algebraic
integers in L. We say that B is a totally definite quaternion algebra if it
is ramified at every infinite prime of L. Thus, all infinite primes of L
are real, and the completion of B along each of them is the algebra ofHamiltonian quaternions. It follows that the L—dimension of B must be
four. A semisimple algebra A is said to satisfy Eichler‘s condition if no38

simple component of it is a totally definite quaternion algebra. If M is afull R—lattice in A, i.e., KM = A, we can form the R—orders
A,(M){a E A : aM C M} andA,(M) =

{ae A: Ma C M}.

If these are maximal orders, we say that M is a normal ideal. We say that
M is principal if M = A,(M )a, for some unit a of A. Let Nrd4/;, be thereduced norm function from A to L. We define the reduced norm of M by
Nrda,/z(M) = S—ideal generated by {Nrda/z(m) : m € M }.
For a central simple L—algebra A, let 6 be the set of infinite primes of
L at which A is ramified.
Definition 2.2

U(A) ={keEL* : ky > 0 at all pe G},

Pa(S) = {Sk :k eU(A)},
I(S) =

multiplicative group of S—ideals in L,

Cl4(S) = I(S)/Pa(S), the ray class group of S relative to 6.
There is a natural surjective homomorphism Cl4(S) — CI(S), whose kernel
is an elementary abelian 2—group [12, p.309].
The importance of Eichler‘s condition stems from Eichler‘s Norm The—
orem [4], (12, (34.9)]:
Theorem 2.3 Let A be a central simple L algebra that satisfies Eichler‘s
condition, and let M be a normal ideal in A. Then M is principal if andonly if Nrda/r is a principal fractional S—ideal of the form Sk, with k €U(A).
As a consequence of (2.3), one obtains (see Eichler [4] or [12, (35.6)])
Theorem 2.4 Let 1 be a mazimal order in a simple algebra A for which
Eichler‘s condition holds. If M and M‘ are left T—ideals, thenM = M‘ & v(M)= v(M‘),
where v{(M ) is the image of Nrda,z(M) in Cl4(S).
Another important consequence of Eichler‘s condition is (see [9, Theorem

4.1] or [14, VII, §5])

Jacobinski‘s Cancellation Theorem 2.5 Let A be an R—order in a semi—
simple algebra A, and M a A—lattice such that Enda(KM) satisfies Eichler‘s
condition. Let X and N be A—lattices such that X is locally a direct factorof the direct sum of n» > 0 copies of M. Then
X & M 3 X @ N implies M & N.
39.

We shall say that two projective left A—ideals J; and J; arestably isomorphic
if there is a nonnegative integer r such that
7, 0 AU & J;, O AC.

Note that if A satisfies Eichler‘s condition, then by (2.5), J; and J; arestably isomorphic if and only if they are isomorphic.
For an R—order A in the semisimple algebra A, we define the class group
CI(A) as the set of stable isomorphism classes of A—ideals, with addition
given by (J;) + (J;) = (I3) if there is an isomorphism J; © J;, Z A ® Js.
If A satisfies Eichler‘s condition, Cl(A) consists of the true isomorphismclasses of left A—ideals.
Combining the above results gives the following theorem of Swan [20],[12, (35.14)]:

Theorem 2.6 Let A be a central simple L—algebra that satisfies Eichler‘s
condition, and let T be a mazimal S—order in A. The reduced norm induces
an isomorphism of abelian groups

v: CI(P) — Cla($).
We assume henceforth that all algebras under discus—
sion satisfy Eichler‘s condition. We will not always ex—
plicitly repeat this assumption.
Let A be an R—order in the semisimple algebra A. LFCI(A) is the subgroupof CI(A) consisting of those projective left A—ideals JI that are locally free,i.e., for each p E max(R), R, ®2J is a free left Ap—ideal, where A, = R, ®A.

Here, R, denotes the p—adic completion of R. in other words, the locally
free ideals are just the left A—lattices in the same genus as A. From Roiter‘stheory of genera [19], (14, VII, §3], we obtain
Theorem 2.7 Let A C A‘ be R—orders in A. Assume that A‘ is projective
as left A—lattsce. Then the mapping

T:LFCI(A) — LFCI(A‘)(J) — (A‘®, 3) = (AJ)
is an isomorphism.
Since this is only implicitly in the literature, we sketch the
Proof: If I is locally free as left A—lattice, then A‘ ®) J is a locally free as
left A‘—lattice. It is clear that if J and J‘ are stably free over A, then A‘ ®, J
and A‘ ®, J‘ are stably isomorphic over A‘, and so T is well defined. If J‘
is a locally free left A‘—ideal, we can write _J‘ = An (()

pemax(R)40

Apap),

with ap a unit in A, = Kp ®x 4 and ap, = 1 almost everywhere, i.e., for all
but finitely many p. Then,

J= aAan({|pemax(R)Apap)

is a locally free A—ideal with T((I)) = (J‘). Hence, T is surjective.
Up to this point, we have not used the fact that A‘ is A—projective. This
fact is cPucial for proving that T is injective. Let J be a locally free left
A—ideal such that A‘ ®», J is free. We can find an exact sequence
0 — J — A —, — 0,

where T is a torsion A—module with anng(T) relatively prime to the Higman
ideal H(A). Since A‘ is A—projective, we get an exact sequence
0 — A‘ ®, J — A‘ — A‘ ®, T — 0.
Since (annr(T), H(A)) = 1, we have A‘ ®) T 2 T as A—modules.
Schanuel‘s Lemma, we obtain a A—isomorphism

ByA‘ ®, JOA % JOG A‘.
By assumption, A‘ ®, J Z A‘ as A—modules. Hence,

A 0 A‘ ~ J G A‘.
We have A‘ & Q > A, for some projective A—lattice Q and integer s > 0.
Thus,

Aoi® = 30 AC,

whence J Z A, by Jacobinski‘s Cancellation Theorem. Hence, T is injective.

Let us conclude by showing that A‘ ®, J can be identified with A‘J
computed inside A. Following [3, Exercise 23.7], we note that the exact
sequence
0 — A‘ — A — A/A‘ — 0

gives rise to the exact sequence

Tor(A/A‘, J) — A‘ Qa J —> A ®, J.
Since J is A—projective, we have Torf(A/A‘,7) = 0. On the other hand,A ®, J Z K ®@r A ®, J % K ®prp J 3 A, and one easily sees that the imageof y) corresponds to A‘J. The proof is now complete.

Clearly, (2.7) can be applied in the case where A is hereditary. The
following proposition allows a broader range of applications.
Proposition 2.8 Let A = (D).y,, where D is a division algebra. Let A bean R—order in A and suppose that A contains a primitive idempotent e ofA such that A = eAe is a maximal order in eAe 3 D. Then A is containedin a mazimal order 91 of A such that 91 is projective as left A—module.
41

Proof: Ae is a right A—lattice, and hence is also a left lattice over the
maximal order © = Enda(Ae). Since A is simple, Aeandare in thesame genus as Q—lattices, and hence also as A—lattices. It follows that Q is
A—projective.
Following Plesken [11], we say that an R—order A in a semisimple algebra
A is graduated if A contains a full set {e1,..., e, } of primitive orthogonal
idempotents of A, and each e;Ae; is a maximal order. We omit Plesken‘s
assumption that R is local.
Corollary 2.9 If A is a graduated order in a semisimple algebra A, then
LFCI(A) 2 LFCI(®Q) for some mazimal order 9 in A containing A.
Proof: A graduated order is a direct sum of orders of the type in the
proposition.

One of the main methods for computing the locally free class group of
an order A is to find a maximal order I‘ containing A and to examine thenatural mapping f: LFCI(A) — LFCI(T‘). From the proof of (2.7), we seethat f is surjective. Since LFCI(T) is known by (2.6), one can concentratecomputing the kernel D(A) of f. It is known (cf., [13, (3.4)]) that D(A)is independent of the choice of the maximal order I‘. Unfortunately, thismethod has no direct analogue for Picard groups. Nonetheless, in the next
section, we will establish a homomorphism Picent(A) — Picent(I‘), where
T is a uniquely determined hereditary order containing A. Unlike the caseof class groups, this mapping need not be onto. Our computations [18] fordihedral and quaternion 2—groups suggest that when A is the integral groupring of a p—group, the cokernel of the mapping is also a p—group.

3

Exact sequences for Picard groups

Let A be an order in the semisimple K—algebra A. For an R—subalgebra

T of the center Z(A), we consider the group Picr(A), as defined in the

introduction. Let M be a bimodule representing an element of Picp(A).
Since Homa—i(M, M) = Z(A) by both left and right multiplication, it caneasily be shown (cf., [12, (37.18)]) that there is a T—automorphism (y ofZ(A) such that zm = m{y(2z), for all m e M. From this observation, we
obtain a homomorphism(p: Picr(A)——»Autp(Z(A))(M) — (uwith kernel Picent(A) = Picz(ay(A). Hence, we have an exact sequence
0 — Picent(A) — Picr(A) — Autr(Z(A)).
As for class groups, we write

LFPicr(A) = {(M) E Picr(A) : M is locally free on the left },
42

(3.1)

and we have the corresponding exact sequence
0 — LFPicent(A) — LFPicr(A) — Autr(Z(A)).

(3.2)

We now proceed to connect LFPicent(A) with LFPicent(T‘), where I is auniquely determined hereditary over—order of A.
Definition 3.3 Let

rad A = An ( {) rad A,).
p[H(A)For all p|H(A), we have Rp ®rrad A= rad Ap. Put
M(A) = {a € a: a(rad A)+ (rad A)a C rad A}.

We definevo( YGaqy ftL|O

We shall call M‘*(A) the ith ring of multipliers of rad A. It is well known
that M(A) properly contains A if and only if A is not hereditary. There isa smallest integer io for which M" = T(A) is hereditary; ‘(A) is uniquelydetermined by A.
Theorem 3.4 For 1 < : < :o, there are group homomorphisms®;(A): LFPicent(A) — LFPicent(M*(A)),
given by estending the action of A on a bimodule to an action of M‘(A).
Remark 3.5 This says, in particular, that every central automorphism of
A extends to an automorphism of M‘(A).
To prepare for the proof of (3.4), we recall the exact sequences ofFrohlich [5]:Theorem 3.6 There are exact sequences

1 — CI(Z(A)) > Picent(A) —>[J|

Picent(Ap) — 1,

(3.7)

LFPicent(A,) —1,(3.8)

O8tz@,2(Ap),(3.9)

pemax(R)1 — CI(Z(A)) <*> LFPicent(A) —>||pEemax(R)and1 — Ch(Z(A)) ~> Outzin(A) +.

|Tpemax(R)where Cla (Z(A)) = { (7) € Cl(Z(A)): JA is principal }.
43Remarks 3.10
1. Since Ap is separable for almost all p, we have
Picent(A,p = 1 for almost all p. Indeed, this equation can fail to hold
only when p|H(A).
2. The maps are defined as follows: T, Trp and 7, are just localizing maps.

For a projective ideal J of Z(A), we put a((I)) = JA. Since Z(A) is

commutative, J is locally free, whence so is JA. Hence, a and ap are
well defined. In order to understand ap, we recall [12, (37.34)], [13,(9.15)]:
Theorem 3.11 If A satisfies Eichler‘s condition, there is an exact se—quence|1 — Outz(ay(A) —> LFPicent(A) *% LFCI(A),where n is the map described in (2.1) and Oc((M )) is the class of M as left
A—module. (Note that 4A1 Z i1Ay—1 is left L—free.)Now, it is clear that ap carries Cl, (Z(A)) into the kernel Outz(m(A) of 9¢,
so we can define ao = orla,(z(ay. We note further that (3.11) tells us that

LFPicent(A,) > Outz(A,)(Ap)(3.12)We are now ready to prove (3.4). Let X be a central invertible bimodulethat is locally free. Thus, we haveX» = Apa(p), a(p) E Ap a unit,
where we can take a(p) = 1 almost everywhere anda(P)Apa(p)* = Ap.
In particular, a(p) is a unit in Ap, for all p not dividing H(A), since A, isseparable for those p. Since M(A) = A N (Mypjn(a) M(Ap,)), X extends toM(A) if and only if Xp extends to M(A,) for all p, but this has been shownin [15, Lemma 4]. This completes the proof of (3.4).
In [18], we compute Picent(Z@G), where G is a dihedral 2—group. The
result shows that$;: LFPicent(A) — LFPicent(M‘(A))
need not be surjective, even at the level of the p—adic completion. —As we shall see, the nature of the image of the map 7, depends heavily
on the arithmetic of A, even when A is hereditary. We can, however, discuss
the image of the map (: Picr(A) — Autr(Z(A)) (cf., (3.1)). When Eichler‘s
condition holds, we have in analogy to (3.11) (see also (2.1)) the exact
sequences

0 — Outr(A) — Picr(A) —> LFCI(A)44(3.13)

and0 — Outz(ay(A) — Picent(A) %> LFCI(A).

(3.14)

Now, Outcent(A) = Outc(A) is a normal subgroup of Picent(A), so Im #0
is a subgroup of Im #. Thus we have
Lemma 3.15 A coset M Outcent(A) contains an automorphism if andonly if Im Ulm outcem(a)y = Im Vo. In perticular, if a coset M Outcent(A)does not contain an automorphism, then
Im |M Outcent(A) N Im ¥#¢ = 0.

4

The structure of hereditary orders

Let A be an hereditary order in a semisimple K—algebra A = Mii (DP;)n;,
where the D; are skewflelds over K and (D;),, denotes the ring of n; x n;
matrices over D;. We have A = [[, A;, where A; is an hereditary order in(D;),,. Further, we have Z(A) =I—, R;, where R,; is the ring of algebraic

integers in the center of D;. We have the exact sequence

1 — Picent(A) — Picr(A) — Autr(Z(A)), —for any R—subalgebra T of Z(A). There may be automorphisms of A =I1}; A; that permute the direct factors, and these may arise from some
automorphism of Z(A) permuting the R;. Since there is no control overwhich automorphisms permuting the R, lift to automorphisms of A, we
restrict our attention to those bimodules M such that for all m Ee M,
me; = em for each primitive central idempotent e;. Then, we are justlooking at [T, Picr(A;), and so, we may as well assume that A is a simple
algebra.

|I

Z(D), the center of DII

= skewfleld over K
the ring of algebrare integers in L=

i/[D : L], the Schur indez of DI

p 3

m tb U

Notation 4.1(D),, a simple algebra(D(P))v(p = Kp ®x D, the p—adic completion of D(p)

Y[D(p) : Ly], the p—local indez.

We retain this notation throughout the rest of the paper.
Let P1,...,p, be the maximal ideals in S such that Ap is not separable,i.e., {P; }icic», is the set of prime divisors of the Higman ideal H(A). It is

well understood that|

A = AN ({apEemax(S)

45

Ap),

y

(4.2)

and the structure of A, is also well understood (see [2], [6], [7], [10], [14]):
Lemma 4.3 If p # p;, for 1 < i < h, then Ap is conjugate in L, ®1 A to
(R(P))nu(p, where (p) is the unique masimal S,—order in D(p). If p is
one of the divisors p; of H(A), then Ap is isomorphic to(\(R(P;))r x rq

(ML.Q2(P;))n: xna\—(R(P;))r x ng***

(2(P;))n, xnr(p;)(Q(P;))n» x n2***

(R(P;))n2 Xnrr(Pi)(HLQP:))ne(pqxm (WQ(Pi))ne(poxne *** (R(Pi))n—(po)xnr(ri)where II;Q(p;) is the radical of (p;).

)

We note that I; can be chosen so that (M;Q(p;))"("" = p;Q(p;). We also
have

CB
Y n;

i=1

——

(rad A,,y°(P)nu(p;), and

M;Ap,.

Following [12, p.360], we call r(p;) the type of Ap, and (ni,...,;rr(p;)) theinvariants of Ap.. We have a left Ap,—isomorphism
L

r(Pi)

Ap, == O p(),i=1where the P; are indecomposable projective A,,—modules obtained from thecolumns of the matrix form of Ap, in the usual way.
Let 0; be the r(p;)—cycle (r(p;),r(P;) — 1, ..., 2,1). It acts on the inde—composable projective Ap,—lattices by(P;)ei = Pj,, & rad P;,

1< j < r(P;),

and the action extends in an obvious fashion to all the A—lattices, since they
are direct sums of copies of the P;. Let ;j(p;) be the smallest integer suchthat(rad A,, ) (2) E Ap,.
46

Example 4.4

1. If r(p;) = nu(p;) or if n», = nu(p;), then j(p;) = 1.

2. One can easily construct examples where j(p;) takes as value any
divisor of r(p;). For, the Grothendieck group K®(A,,) can be iden—tified with ZC(P)) by making pir) O ——— &© Plo®o) correspond to(mi;—+—;Mr(p;)). Multiplication by rad Ap, is given by the permuta—tion a,; above, which corresponds under this identification to a cyclic
permutation of coordinates in Z). The integer j(p;) is just thelength of the orbit of (mi, ..., n(p;) under this cycle.

5

Picard groups of local hereditary orders

This section is expository in nature. It contains only the following lemma,
the first part of which is essentially [12, Exercise 39.6]. We denote by C,, acyclic group of order n.
Lemma 5.1 Let A = Ap;, as described in the previous section. Then(i) Picent(A) = Cr(ppu(pq»> with generator (rad A).
(ii) Oute(A) = Cripyu(poyji(pq» with generator (rad AY(®).
Proof: (1) We first show that every central invertible A—bimodule M is of
the form (rad A), for some s with 0 < s < r(p; Ju(p;). We may assume
that M C A is a twosided invertible ideal. Since rad A is nilpotent modulo

P;:A, there is an integer s with (rad A)‘ 2 M, but (rad A)‘ 3 M. Then
N = M + (rad A) is a A—bimodule with (rad A)‘ J N D (rad A).
Since A is hereditary, N is A—projective on both sides, and hence is in—vertible. However, rad A is surely an invertible bimodule, and so N;, =N(rad A)~**" is an invertible bimodule with A D Ni D rad A. If N, #rad A, then Ni / rad A is a central invertible bimodule for the semisimple
algebra A/rad A. Then, we have N;/rad A > A/rad A, whence N;, = A.
It follows that N is either (rad A)*~‘ or (rad A)*. In the first case, we ob—tain (rad A)*~‘= M + (rad A), whence M = (rad A)‘~‘, by Nakayama‘s

Lemma. The second case cannot occur, for it implies that M C (rad A),
contrary to the way s was chosen. It remains to determine the order ofrad Ap, in Picent(Ap,). Wehave
However, conjugation by m i s a genuinee automorphism. By the structure
theory of maximal orders in complete skewflelds [8], [12, Chapter 3], wehave A#A,, = p:Ap,, which is isomorphic to Ap, as a bimodule. Hence,
Picent(Ap;) has order r(p;)u(p;) and is generated by (rad A,,). This com—pletes the proof of (1).
|(ii) According to (3.14), a central invertible bimodule M gives rise to acentral automorphism if and only if M is left A—free. Hence, we must
determine the smallest integer jp such that (rad Ay° is free. Clearly, Jo =J(P;), by the definition of the latter quantity, and (14) follows.
47

6

Picard groups of global hereditaryordersLet A be a hereditary R—order in the simple K—algebra A. Denote by
I = Z(A) the center of A, and let S be the ring of algebraic integers in L.

We retain the notation of the previous two sections.
According to (3.6), we have the exact sequences
1 — C(S) —> Picent(A) ——1 —CI(S) <*> LFPicent(A) —>JJ Picent(Ap,) — 1,
pEemax(S)

(6.1)

||

(6.2)

LFPicent(Ap)—1,

peEemax(S)and

1 — Ch (S) ~> Outs(A) —>JJ

L

Outs (Ap).

(6.3)

pemax(S)

According to (5.1), Picent(Ap,) is cyclic of order r(p;)u(p;) with generator(rad Ay,), if p; is adivisor of the S—Higman ideal of A. LFPicent(A,,) isgenerated by (rad A,,)"(P", and is cyclic of order r(p;)u(P;)/j(P;).
Lemma 6.4 The exact sequence (6.1) splits if and only if for each i with
1 <i < h, there is an ideal U; of S such that qirlpo)e(Pi) p. is principal. In

particular, (p;) must be an (r(p;)u(p;))" power in CI(S).

Proof: For 1 <i < h, let J(p;) = AN (rad A,,). Then (J(p;)) in Picent(A)maps to rad Ap, in Picent(A,,) and to 1 in Picent(Ap, ), for j #1. The fibresof r over the rad Ap, are the sets {UJ(p;) : U € CIS) }. Moreover, sinceJ(p;) and J(p;) commute (as one sees by checking locally), we conclude
that r splits if and only if each of these fibres contains an element suchthat (¥3(p;))"(P9_(P) = A as bimodules. Such an isomorphism is given bymultiplication by a central unit of A. On the other hand,(4JZ(pqyribdein) == qpipdelrdg(p,yr(po)u(ri)qprip)e(Pd)p; A,

as one sees by localizing and recalling the proof of (5.1). Now, ¥" (P)#(P)p;A
lies in the image of a. Thus, W(PI*(P)p;A 2 A if and only if W"(P)#®(P)p; ig
principal, as claimed.
Remark 6.5 Using (6.4), it is easy to construct hereditary orders for which
T is split, and others for which it is not.
Quite analogously, one can prove
Lemma 6.6 The ezact sequence (6.2) splits if and only if for 1 < i < h,there exists an ideal M; of S such that qr (Pode(ri)/i(2i) p . is principal.
48

Remark 6.7 It is again easy to construct cases where (6.2) does or does
not split. (6.4) and (6.6) show that if (6.1) splits, then so does (6.2), but
the converse statement need not hold.
It should be noted that in (6.4) and (6.6), the requirement was that someideal be principal, i.e., that it represent the neutral element in CI(S). In
the next two lemmata, an ideal must represent the neutral class in Cl4 (S).
Lemma 6.8 Cl,(S) = {¥ e C(S) : (M") e Pa(S)}. Thus, (H) E
Cla(S) if and only if %*" = Sa, for some a € L* that is positive at each
infinite prime ramified in A.
|

Proof: Recall that Cl:(S) = {(¥) e CI(S) : MA is principal }. We canuse (2.7) to conclude that HA is principal if and only if IT is principal,
where T is a maximal order containing A. Since A satisfies the Eichler
condition, Eichler‘s theorm (2.3) says that UT is principal if and only if
Nrd4/z (UP) = %"" is in Pa(S®). We now turn to the question of when Tp
is surjective.

Lemma 6.9 The map r, in (6.3) is surjective if and only if for every
1 <i < h, there is an ideal M; of S such that gpm rm/a(Pi) lies in Pa(S).
Proof: Recall that LFPicent(A,) > Outs, (Ap) Hence, in the fibre15‘ ((rad A,y() = {43(pY: ¥ e C(S) },we must find an element that maps to the identity of LFCI(A) in the exact
sequence (3.11). Again, let I‘ be a maximal order containing A. Using (2.7)
and (2.2), we see that 7, is surjective if and only if there exists an ideal
U; of S such that Nrda/z(¥4;3(p;)®T) lies in P4(S), for 1 <i < h. Let

II;Q(p;) = rad (p;), as in (4.3). ThenJp)‘ Typ, —— H;P‘p,,and.

is a maximal two—sided ideal with Nrd4/z(F3;) = p?"""®:)" Hence, the map
To in the sequence (6.3) is surjective if and only if for 1 < : < /A, there is an
ideal Y; of S so that U?" pinm/pu(p;) lies in Ba(S). Note that HB;T is aproper product of normal ideals, so that the reduced norm is multiplicative.

This completes the proof.

Remark 6.10 Again, it is easy to constuct examples where 7, is surjective
and others where it is not.
Lemma 6.11 The sequence (6.3) is split if and only if Ty is surjective(cf., (6.9)) and for 1 < i < h, there is an ideal B; with both B?" and(B., )ripo)ul(po)/i(P)p, in ‘Ba(S), where U; is as in (6.9).

49

Proof: The fibre of 1, over (rad A,,)‘is {BM; J(p;)®: (B)"? e Ba(S)}(cf., (6.8). This fibre must contain an element of order r(p;)u(p;), whence
the result easily follows.

Again, examples are easily constructed where (6.3) splits, and others

where it does not.
We conclude with a remark about Picr(A). In general, the right—hand
map in the sequence
0 — Picent(A) — Picr(A) ~ Autr(S)need not be surjective. Indeed, let S/R be Galois, and let there be an
R—automorphism y of S and a maximal ideal p of S such that y[(p) # p.
Then

5

g

a= ($ $)
has no invertible bimodule whose class maps to y. For, it is easily seenthat an element y € Autr(S) comes from Picr(A) if and only if it extends

locally, i.e., for each p E max( S), y induces an cutomorphism

7 Ap —* Arp)
arising from the extension of y to a maximal order.
References[1] H. Bass, "Algebraic K—Theory", Benjamin, New York, 1967.
[2] A. Brumer, Structure of hereditary orders, Bull. Amer. Math. Soc. 69(1963), 721—724; addendum, ibid. 70 (1964), p.185.
[3] C. Curtis and I. Reiner, "Methods of representation theory with appli—
cations to finite groups and orders", vol. I, John Wiley & Sons, New
York, 1981.

[4] M. Eichler, Uber die Idealklassenzahl total definiter Quaternionalge—bren, Math. Z. 43 (1938), 102—109.
[5] A. Frohlich, The Picard group of non—commutative rings, in particularof orders, Trans. Amer. Math. Soc. 180 (1973), 1—46.
[6] W. Gustafson, On hereditary orders, Comm. in Algebra 15 (1987),
219—226.

[7] M. Harada, Hereditary orders, Trans. Amer. Math. Soc. 107 (1963),
273—290.

[8] H. Hasse, Uber p—adische Schiefkorper und ihre Bedeutung fir die
Arithmetik hyperkomlezer Zahlsysteme, Math. Ann. 104 (1931), 495—
534.
50

[9] H. Jacobinski, Genera and decompositions of lattices over orders, Acta
Math. 121 (1968), 1—29.
[10] H. Jacobinski, Two remarks about hereditary orders, Proc. Amer.

Math. Soc. 28 (1971), 1—8.

[11] W. Plesken, "Group rings of finite groups over p—adic integers",
Springer Lecture Notes in Mathematics, vol. 1026, Springer—Verlag,
Berlin, 1983.

[12] I. Reiner, "Maximal orders", Academic Press, London, 1975.
[13] I. Reiner, "Class groups and Picard groups of group rings and orders",
American Mathematical Society, Providence, Rhode Island, 1976.
[14] K. Roggenkamp, "Lattices over orders II", Springer Lecture Notes inMathematics, vol. 142, Springer—Verlag, Berlin, 1970.
[15] K. Roggenkamp, Automorphisms and isomorphisms of integral grouprings of finite groups, Springer Lecture Notes in Mathematics, vol.
1098, 118—135.
[16] K. Roggenkamp, Picard groups, automorphisms and Frolich‘s localiza—tion sequence, to appear in the Proceedings of the American Mathe—
matical Society Summer Research Institute, Humboldt State Univer—sity, Arcata, California, 1986.
[17] K. Roggenkamp and L. Scott, Isomorphisms of p—adic group rings,
Ann. of Math. 126 (1987), 593—647.
[18] K. Roggenkamp and W. Gustafson, A Mayer—Vietoris sequence for
Picard groups, with applications to integral group rings of dihedral andquaternion groups, to appear in Illinois J. Math.
[19] A. Roiter, Integer valued representations belonging to one genus, Izv.

Akad. Nauk SSSR 30 (1966), 1315—1324.

[20] R. Swan, Projective modules over group rings and mazimal orders,Ann. of Math. T6 (1962), 55—61.

51

Texas Tech University, Mathematics Series
Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

Product Theorems for Formal

Hypergeometric SeriesPeter Henrici*
University of North Carolina
Chapel Hill, North Carolina 27514
Mathematical Sciences Research InstituteBerkeley, California 94720

Abstract

A formal hypergeometric series (fhs) is a formal power series withcoefficients that satisfy a two—term rational recurrence differential
equation satisfied by fhs. In an important special case, it is possible
to eliminate the "irreducible terms" by means of the Cayley—Hamilton
theorem, and the method then always works. Examples are given.

1

Formal Hypergeometric Series

A formal hypergeometric series (fhs) is a formal power series over C ,COF= Years*,

(1)

k=0o

where co = 1, and where the remaining coefficients satisfy a rational recur—
rence relation which we write in the forma(k)er:1 = p(Kk)er;(2)

here p and q are monic polynomials, g # 0. We do not assume that theseries (1) has a positive radius of convergence; the degrees of p and q are
therefore arbitrary. However, we do want (2) to hold not only for non—negative integers k, but also for k = —1.
requires

Since co = 1, c—1 = 0, thisa(—1) = 0,(3)which we shall assume henceforth. To make (2) uniquely solvable for c:},for all k = 0, we also requireq(k) #0,

k=0,1,2,....

*Professor Henrici died on March 13, 1987.

53

(4)

If the zeros of p and q are denoted by —q1, ..., —a, and —1, —b1, ..., —b4,
respectively, then (2) is

L 1 (a +B (a +4 _(5)""~ (1 +k)(h +k) (b, +k) *Defining the forward factorial or Pockhammer symbol by

1,

k = 0,(a)={ ala +1)(a +2) <+ (a+ k —1), k= 1,2,...,
the relation (5) is immediately solved to yieldCk_ (ai): (ap)k‘(bi)x > + (b])x"

k = 0,1,2,..., and we therefore have__ c(a) *** (4p)F= [aar Hth); ~~~ (by."Traditionally one writes (see Bailey [1])®=»8, |

G41,..:,0p;biyil., by

IZ

|.

(6)

Examples of such formal hypergeometric series (fhs) abound in classicalanalysis; for instance,oPo[z]) = &,1Fole; z](7)(1 —z)~*,(8)and the classical hypergeometric series of Gauss of course is 4Fi. Divergent
series of the form (6) (where p > q + 1) often occur in connection withasymptotic expansions of higher transcendental functions.
2

Product Theorems®

A product theorem for fhs is a formula which represents a product of twoor several fhs as a single fhs. Instances of such product theorems are nothard to find; for instance, the two simple series mentioned above obviously
satisfy the product theorems
oFo[az] oFo[bz]oFo[(a + b)z}, |1Fo[a + b; x]

1Fo[a; x] 1Fo[b; T)

for any a, b e C .
54

(9)
(10)

In this paper, we systematically explore a method for obtaining suchproduct theorems in more complicated cases. There are two reasons why
one should be interested in such product theorems.
(i) Naturally, product theorems are of interest in their own right. For
instance, de Branges‘ celebrated proof of the Bieberbach conjecture ([4],see also [5]) is ultimately based on a classical product theorem of type(2F)‘ = 3F, due to Clausen [3].

(ii) Product theorems are a source of binomial identities, i.e., of formulas

expressing a sum of products of binomial coefficients (or, what amounts tothe same, of Pochhammer symbols) by a single such product. This comes
about because the coefficients of the Cauchy product of a finite numberof fhs evidently are such sums of products of Pochhammer symbols. For
instance, the coefficient of z" in the Cauchy product of the two series on
the left of (9) isn*fa yk br—*
k! —
(n KV

In view of the identity (9) this equals(a + b)"n!

Multiplying by n!, we have obtainedS) B )a"b"~"*yokpn—k = (a + b)",
n
YC
fz k
|

(11)

that is, we have proved the binomial theorem. In a similar way we obtainfrom (10)Since

3 aBex, — @48s4)r(O)n—k———(b) (—1)*b n—k— _ABR__A__,a + b)»,ni(—1!(—1)*— k I = ———,

the sum on the left is(b)2 «—__(a)(—n)

(O)n

) —;

nl 24 Pi(— bort," n! * m [®
—b—n +1

1|—

Letting c := —b—n + 1, we thus have proved the formula

im | b mL | — @)n(c —C(C)a ‘

(12)

known as Vendermonde‘s theorem. In Vandermonde‘s theorem, the bino—
mial sum is expressed as a terminating hypergeometric series (terminating,because one of the numerator parameters is a negative integer). This is55

typical also of more complicated binomial sums: They usually can be ex—pressed as a terminating hypergeometric series, often of type ,;1 F,, of some
simple argument such as £+1,2, or 1/2.
Binomial identities are standard fare in (classical) combinatorics, where
they occur in all sorts of disguises. More recently, such identities have beenstudied in computer science, especially in connection with the analysis ofalgorithms; see [6] for an abundance of examples.

3

Methods of Proving Product Theorems

Traditionally, product theorems are often proved by reversing the approachtaken in section 2. That is, the binomial sum formula is proved first, usuallyin the form of a formula for a terminating ,4;1 F,. Then the sum formula isused to establish the product theorem. This method is used, for instance, in[1], [2]. One advantage of the method is that one and the same sum formula
can often be used to derive several essentially different product theorems.
For instance, Vandermonde‘s formula may be used to prove not only (10),but also a product theorem of the form oFi oF = 1Fr. On the other hand,

the method fails for products of more than two fhs, because hardly any sum
formulas appropriate for such cases are known. Also, because there is no
systematic way to discover or to prove binomial sum formulas, the method
even when successful has the appearance of being ad hoc.
In this paper we discuss a systematic way to establish product theorems
via the differential equation satisfied by the product in question.

4

The Differential Equation Satisfied by a fhs

This differential equation is best expressed in terms of the operator 0 definedclassically by 0 := z d/dz, and for a formal power (or Laurent) series by

OP := Y" keea*.

(13)

We call OP the derivate of P. It can be verified—and it is easy to do so—that with this definition the usual rules of calculus for D = d/dz remain
valid for 0; for instance, 0 is a linear operator; there holds the product rule,0(PQ) = 0P — Q +P —0Q;

(14)

and there holds the analog of the Leibniz formula,0"(PQ) = Y( L )0°P :0"*Q.
k=0

If P = z", then (13) means
0x" = nz".

56

(15)

Thus the powers z" are the eigenelements of 0 (with corresponding eigen—values n), much as the exponential functions e~* are eigenfunctions of theordinary differential operator d/dz. It follows that if p is any polynomial,
thenp(0)z" = p(n)z",(16)p(O)P = y" p(k)erz*.

(17)

and if P = S cmz* is a formal power series,
Let now

O1, ..., 8p; Z

be a fhs, and let the polynomials p and q be defined bype) = (@a +01) (2+ a,),alz) = (@ +1)(e +M) (e + B,),(19)

so that the coefficients c»; satisfy the recurrence relation (2) for k > —1. By(17) and (2),p(0)PY P(k)eaa®
k=0

Y a(k)eeqic*.

k=0

Thus

zp(O)P =Y°q(k)eec*"‘
k=0=

Y q(k ——— 1)c;z*
k=1=

y g(k — 1)c4xz* (since g(—1) = 0)

= a(@— DP.

It follows that P satisfies the differential equation
q(0 — 1)P — zp(0)P = 0
or, written out in full,[0(0 + A — 1) (0 + B, — 1) —z(0 + a;) —> (0 + a,)]P = 0.

(20)

Conversely, let P = LR, c&z* be any formal solution of (20) such thatco £ 0, and let the polynomials p and q be defined by (19). We then haveg(0—1]P = Y‘q(k—1l)cas*,k=0

zp(0)P

Y_ p(k)erz**.
k=O

57

The differential equation being satisfied requires
q(k)eri = p(k)esx, k> —1.

(21)

For k = —1 this requires g(—1) = 0, which condition is taken care of by
the special form of the differential equation (20). For the remaining valuesof k, assuming that q(k) # 0 for k > 0, (21) implies that P is a constantmultiple of (18). Calling the solution of a differential equation standardized
if its zeroth coefficient co = 1, we thus see that under the conditions stated(21) is the only standardized solution of (20).
The solution series (18) terminates, with the term in z* being the last
nonzero term, if p(O) # 0, p(1) # 0, ..., p(k — 1) # 0, p(k) = 0. H
this condition holds for some nonnegative integer & then it is possible for q
to vanish at some integer I > k without violating the condition (21). The
coefficient c;4, then is not determined by the differential equation, and may
be chosen arbitrarily. If g(r) # 0 for r > I, or at any rate between I and thenext integer zero of p, the differential equation has the additional linearly
independent solution|
P ==,F,a + l+ 1, ..., »HH|

Ah 4+ltl1, cs A+1l+1(22)

The situation thus described may occur repeatedly. We thus have:
Theorem 4.1 Let a1,...,4p,; Ai,..., B, 6 C , and let the polynomials p(z)and q(z) be defined by (19). If p(k) = 0 for j > O distinct non—negative
integers k, let these integers be denoted by 0 < ki < k, < ... < k;; in any
case, let k;4, := co. If qg(k) = 0 for some integer k such that 0 < k < ki,the differential equation (20) has no standardized solution. If q(k) # 0 for
0 < k < ki, the equation has the only standardized solution
P, =
I

._.F

arunont |R | amg

93()

In addition, the equation has a linearly independent, non—standardized so—lution for every i > 1 such that g(l — 1) = 0 for some integer l satisfying
ki—1 < l < k;. If l; is the largest such integer, i.e., if g(l) #0 for l; < l < k;,then this solution isoR | a tiemar t@[0(0 + Bi — s) = (0 + B, — s) — az"(0 + on »» (0 + ap)]P = 0,(25),@, + l;: a
P;= ah,. py ObT ;y...
jhe eCst® |Our applications also require the consideration of differential equations

where a € C, a # 0, and where s is a positive integer. In this case, letal2) = (@ + s)(z + MA) (2 + B,),p(z) = (2+ ai) * (2 + ap).
58

(26)

(27)

If P = y c;z* solves (25), thenSla(k — s)orz* — ap(k)eaz**"] = 0

k=0o

OT

©0

Y [a(k)er+s — ap(k)er)a*** = 0.

. k= —s

In view of g(—s) = 0, no condition results for co, which may be chosen
arbitrarily. If g(k) # 0 for k = 0,s,2s,..., the differential equation issatisfied if c; = c4 = ...= c,;—1 = 0, and— abo,

p=

Ck+s = "i(h * k = 0, s,2s, ....

By choosing co = 1 there resultsc,, _ L P(O»(s): — p(ks — s)ko
g(0)g(1) —— +q4(ks — s)"which may be expressed by Pochhammer symbols, as follows:o ukpores k(Gklsh(Ca/s)k :—> (Cp)3)k(A.]9.‘ * _ 0, 1,2, ....

Chs =We thus see that (25) has the solutionera

oi/s,..., ap/s; as‘ z® |

(28)

9

and that this is the only standardized solution of the equation.

For each integer B; such that 0 < B; < s, q(A; — s) = 0, qg(A; + ks) #0, k= 0,1,2,..., the equation has the additional non—standard solutionss, e+ +} (0p + B;)/ s;
P;.=
= pPj
A pF | 1+ (B;/s),.(an(BM ++B;)/B;)/s,— (B, + B;)/8

where the term

as?‘ z*|(29)

B; + B;sis to be omitted from the sequence of denominator parameters
Bi + B;8969

nA,; + B;
8

Thus in summary there holds:
Theorem 4.2 Let the polynomials p(z) and q(z) be given by (26), (27),let a € C , a # 0, and let s be a positive integer. If g(ks) £ 0 for k =0, 1,2, ..., then the differential equation (25) has the series (28) as its only
standardized solution. In addition, it has the non—standardized solutions(29) for every integral B;, 0 < B; < s, such that g(B;—s) = 0, qg(B; + ks) #0, k = 0,1,2,....

59

As a consequence of Theorem 4.2, the series

PSA | amore" |&1,..., O,; 4%"

where a E C , a # 0 and s is a positive integer, is the only standard solutionof the equation[0(0 + sBi—s) > (0+sB,—s)—as‘""*~"2*(0+sa;,) ——— (0 +sa,)]P = 0. (30)There will be no need to discuss the exceptional case where the polynomial
p vanishes for certain positive integers.

If expressed in terms of the customary differential operator D = d/dz,
both p(0) and g(0) become polynomials in zD. The equation (25) then
may be put in the formmax(g+1,p)3°(aa + bez°)z*D"*P = 0.

(31)

k=0

If we call 1 — k the level of a term z*D*P, then the equation (31) has theproperty that only two levels occur. Apart from certain exceptional valuesof the parameters, every such equation thus can be solved in terms of fhs.

5

A Linear Space of Products of Derivatives

Suppose we wish to find a differential equation satisfied by the product

Z = UiUVUq + —U;,

(32)

where the U; are formal power series. According to the general Leibniz
formula, the derivates of Z have the formp0‘ 7, =

Y 4;.m II 0""U;,

(m|=;

(33)

i=1

j = 1,2,..., where m = (mi, m2,..., m,) is a vector of non—negative inte—
gers, |m| = m;+m2+++++m,, and where the @;m are certain non—negative

integers. Writing

Pm —— II 0""U;,

(34)

i=1

we have& Z ——

Y

4;mPm—

(35)

{m|=;

Suppose now the series U; all are of the form ,F, (same p and q for all ?)where p < q. Using the differential equation (30) satisfied by the ,F,, each
derivate 0**‘*U,; can be expressed as a linear combination of U;, U;, . . . , JU;60with polynomial coefficients. Consequently, if m = (m, ..., m,) is an index
vector with |m| =q + 1 such that m; = q+ 1 and all other m; = 0, thenPm = Y BmnPa,
In|<q

(36)

where the Amn are polynomials. Considering (33) for j = q+ 1 and using(36) whenever required, we find that there holds a representation

04 Z = Y "anPn
\n|<q

|

(37)

where the y», are polynomials.
Our stated purpose is to obtain a differential equation satisfied by Z.
Our method simply consists in applying the operator 0 to (37) and elimi—
nating the P, from the resulting equations.
To show that the method will always be successful, let P be the vector
space of products Pm where max m,; < q, with polynomial coefficients. It
is clear that the dimension of P is finite. We select a basis in P, as follows.
Let Z, 0Z, ..., 0‘Z be among the basis elements. If these derivates arelinearly dependent, we have found a differential equation for Z, and we arefinished. If they are not, let Q1,Q2, ..., Q; be the additional basis elements.
(It is not required that each Q; equals some Pm.) These Q; will be called
the irreducible terms; they are basis elements that cannot be reduced toderivates of Z.
|
Expressing the P in terms of the basis elements, (37) reads

a

|

ko

0* Z = Y" 0,0‘ Z + Y Bo;Q3,
i=1

j=1

(38)

with polynomials ap,, and Ao,;.

Lemma 5.1 If Q E P, then OQ E P.
Proof.

By definition, Q is a linear combination of products Pm where

max m; < g. It follows that GQ is a linear combination of products Pm

where max m,; < q + 1, and at most one m,; = g + 1. If there is such anm;, express the corresponding derivate 0"*‘U; as a linear combination ofderivates of lower order with polynomial coefficients. An expression of the
form
0C =

Y "m 4m|m|<qwill result, proving the assertion.
It follows from the Lemma that for each basis element Q, there exist
polynomials (»,; and y,,; such that9,k

OQ, = >_ Cni6Z + Y v,;Q,

j=1

61

(39)

h — 1,2,..., k. Thus by applying 0 to (88) repeatedly, there follows theexistence of polynomials a;,; and A,,; such thata.

k

0H*Z = Y ei,0‘ Z+ Y B;Q;, 1 = 0,1, ....
t=0

j=1

(40)

We consider these relations for I = 0, 1, ..., k and try to find a linear com—bination in which the Q; no longer occur. This amounts to finding polyno—
mials To, T1, ..., 7s such thatks
Y Bizm = 0, j = 1,2,..., k.

(41)

lt=0o

This system of k equations for the k + 1 unknowns to,... , rt», always has anontrivial solution which may be assumed to consist of polynomials. Therefollowskq

k

Y 10f}+4Z —— X( moi;)0‘ Z —— 0,

(42)

=0
i=0 i=0
which is a differential equation for Z with polynomial coefficients. If (42)turns out to be of the form (30), it can be solved in terms of fhs. Matching
initial coefficients, that solution is readily identified with Z, and a product. theorem has been discovered.

6

An Example: A Proof of Clausen‘s Formula

In this example the method discussed in section 5 works although the hy—
pothesis p < q is not satisfied. Let= tn =v =m | ©5 *,so thator[0(0 +737 — 1) — z(0 + a)(0 + B)JU = 0(43)(1 — 2)0°U = (1 — y)0U + z(00 + z)U,

(44)

where a = a + B, t= af. We wish to study the conditions under which
Z = U"
is a fhs. We haveand

07 = 2UOU
0° Z = 2(O0U) 4+ 2U0°U.

Here AU can be eliminated by means of (44), and we get(1 — 2)0‘Z = 2(1 — z)(@U) + 2U[(1 — 7 + az)0U + #zU),62

that is (noting that 2U0U and U are reducible elements)(1 —2)0°Z — (1—3y + 08)0Z — 21zZ = 2(1 — z)Q.

(45)

Q = (0U)

(46)

Here

is the irreducible element that cannot be expressed in terms of derivates of
2. In view of

0Q = 20U0°U

we find, again using (44) to express (1—z)0°U in terms of derivates of lower
order,(1 — z)0Q = 20U[(1 — 43 + az)0U + tzU]or

(1 — z)0Q = (2 — 27 + 20z)Q + 1202,(47)

which in the present case is the sole relation of type (39). An applicationof 0 to (45) thus yields|(1—2)0°Z—[1—y+(0+1)2]0‘Z—(0 +47m)02—2122Z = [4—47+(40—2)]Q.

(48)

We wish to eliminate Q from (45) and (48). This is easily possible bymultiplying (45) by 4—47y+ (4a —2)z and (48) by 2(1—z) and subtracting.
However, the resulting equation will be hypergeometric only if the resulting
coefficients of the derivates 0‘Z are polynomials that involve terms of two
fixed degrees only. This will be the case only if the multipliers can be taken
as constants, and this in turn will be so only if the polynomial 4—47+ (40 —2)xz is proportional to 1 — z. This requires 4y — 4 = 40 — 2 or y = a + i.
In this case the expression on the right of (48) is 2(1 — 20)(1 — z), and therequired multipliers are 1 — 20 and 1. We find
0[0° + (30 — 20 + 2(0 — 5912 — 2[0° + 300° + (20° + 41)0 + 4ro]Z = 0,
which equation has__

2«,20,a + B;

2 = B ead a igs Az|

as its only standardized solution. We thus have proved Clausen‘s formula[3]p«B; z]‘ _ p* ‘| e«e+B+}

2a, 28, « + B; a

_ 32[|2e+28,«a +B +4

63

|"

7

Application of the Cayley—Hamilton Theorem

The relations (39) are based on eliminating unwanted high—order derivatives
by means of the differential equation satisfied by ,F,. Since that differential
equation depends on z, it cannot happen that all polynomials £ and 7 are
independent of z. Here we consider the next simple case. We assume thatall polynomials y,,; are constants, and that there exists a positive integer s
such that all €,,,; are of the form constant * x*. It is permitted to multiply

the Q; by suitable powers of z to satisfy these conditions. Introducing thevector

an
Q2

q=

—

aP
where the multiplications just mentioned are supposed to have taken place)and the matrix

M= (4,5)(h, j = 1,2,..., k), the relations (39) may then be written
0q = Mq + z*t(0)Z.

(49)

Here t(0) is a vector the components of which are polynomials in 0, withcoefficients that are independent of z. M is called the reduction matriz ofthe basis q with regard to the product Z. We also assume that in relation(38), the ap,; and the Bo,; are constants. Letting4&po(O) = gat! — Y a0,0,i=O

c* — (Bo,1, oo Pok)

(38) may then be written

po(0)Z = c‘q.

(50)

Under the above hypotheses the elimination of q can be performed
analytically. From (50) there follows, using (49),Opo(0)Z = c‘0q
= e‘[Mq+ zs‘t(0O)Z],0‘poe(0)Z = c[M(Mq+z‘t(0)Z) + z*(s + 0)t(0)2Z]= e‘ {M‘q +s*[M + (s + 0)I]t(0)Z}and generally, as may be seen by induction,0‘po(0)Z = e {M‘q+z2*[M‘~‘+(0+s)M‘~"+———+(0+s}—‘IJt(0)Z}, (51)64j = 0,1,2,.... To eliminate q from these relations, we use the Cayley—

Hamilton theorem stating that a matrix satisfies its own characteristic
equation. Thus, letpi(A) = det(AI — M) = Sax).

(52)

We multiply, for j; = 0,1,..., k, the ;*" equation (51) by #; and add. On
the left, this yields pi(@)po(@). On the right, the factor of q iskc‘ Y" pigM‘ = e‘pi(M),j=0which vanishes by the Cayley—Hamilton theorem. There remainspi(¥)po(O)Z = a*c"N(O)t(0)2,

(53)

where

N(O) = y> x;[M‘~‘ + (0 + s)M‘ + ... (0 + sy‘)

j=1

k
k
.
= Y) m;(0+s]°I + Y) x;(0 + sY ‘M + ... + m; M*"~‘.
j=1

j=2

Since cN(O)t(0) evidently is a scalar polynomial, the equation (53) clearly
is of the form (25), and Z can be expressed by fhs.

8

Ramanujan‘s Product Theorem

The method outlined in section 7 offers a transparent proof of Ramanujan‘stheorem concerning the product Z = UV, wherev =—.m

|

9

ill

v =n

|

®

~!

(see [2], [8]). By (20),(9(@ +4 — 1) — 2(0 + «)JU = 0,[0(0 +43 — 1) + z(0 + a)}V = 0,

hence

0°U

aezU + (1 — 47+ z)0U,@V =—azV +(1—y—z)GV.

(54)

The linear space P here is spanned by the products UV, UOV, VU, OUOGYV .
The reducible basis elements are

2 = UV,0Z = UOV + VOU;65

as irreducible basis elements we choose

Q = gUov,
R = as(VOV — VOU).
(The factor z is inserted here in order to obtain a constant reduction matrixM.) Using (54), we calculate

OQ = QUOV + OV&AU
OU [—azV + (1 —43y — z)0V]}+ OV [azU + (1 —73 + z2)0U]OR(2 — 27)Q + «R,

R+ z(UVOV — VO*U)R+ zU[—azV + (1—743—z)0OV] — zV [azU + (1 —737 + z#)GU]= (2—y)R—2az*Z — z‘0Z.

The reduction relations (49) thus here take the explicit form(af) = (*2" *,) (%) += ( a2—a)#(55)

The characteristic polynomial of the reduction matrix is(A+2y—2)(A+3—2) =A‘ +(3y—4)A + (27 —2)(y—2).

(56)

Relation (38) here becomes

0Z = UO‘V 4+20UOV + VOU= 2Q + U[—azV + (1—y—z)0V]+V [azU + (1 — 43 + z)GU]= 2Q + (1—7y)0Z — R,

that is, (50) is0(0 +1y—1}Z = 2Q — R,

(57)

and we see that all the hypotheses of the method of section 7 are satis—
fied. We thus are assured without further computation that there exists a
product theorem for Z = UV.
|
To obtain the product formula, the construction of section 7 has to be
carried through explicitly. Applying 0 to (56) and using (55) yields

0‘(0 +3y—1)Z = (2 —27)Q + (2a +37—1)}R+z2"*(O0Z +22)

(58)

and by one more application of 0 we get

0°(0 +71 —1)2 = (2—27)‘Q + |a(2 — 27) + (2 — 7)(2a +7 —2)]R (59)+2"{0Z + (4 — 7y)0Z + 2a(4 — 2a — y)2}.
66

We multiply (57), (58), (60) by the coefficients of the characteristic poly—

nomial (56) and add. This yields— 0(0 + Y — 1)[0" + (37 — 410 + (27 — 1)(7y — 1)]Z
= &°[0 + 270 + 2a(27 — 2@)}Zor in completely factored form|

0(0 +31 —1)(0 +27 —2)(0 +7 —2)Z = z*(0 + 2a)(0 +27 — 2«)Z. (60)This equation by Theorem 4.2 has the only solution
a,x —a; z* 2 /4 |Po = F:.

002 :| im iv + $v

Thus there follows Ramanujan‘s product theorem
F

a; I

a|f

F

a;

J| $

—I

= F:

a,} —a; C 2 *| Blwihhd

.

61

(64

All known product theorems (see Bailey‘s survey [2]) can be proved byessentially the same method. It seems likely that many similar producttheorems for higher order series remain as yet to be discovered, the only
obstacle to their discovery being the algebra involved for obtaining the
reduction formula (49) and the subsequent manipulations involving thematrix M.

9

Triple Product Theorems

Unlike the conventional method of proving product theorems from bino—
mial coefficient identities such as Vandermonde‘s or Dixon‘s formulas, themethod of section 7 extends to products of more than two hypergeometricseries.
It is easy to give examples of such product theorems. Take
£ = exp ——n

for some positive integer n. In view of the formulas(1 —z)(1 — ws). (1 —w"~‘z) = 1 — s",
1 + w 4+ w* ++ —~+w"~‘ = 0,
we clearly have the product theorems

TL om{*z = 1,

(62)

U iFoje;w*z] = iFola; 2".

(63)

k=0

Here is another example:

67

Theorem 9.1 Let a € C , a # —1,—2,..., and let w = exp(21ti/3). Then
there holds
oFi [1 + a; z] oFi[1l + a; wa} oFi[l + a; wz]
= 4F7

a

& q 1 a + 3.
2

a

a

4} 2

.

4°

§+p§$+$§$+1,ja+3.fa+ $, 5a +1,a+ 1(4)°2°\g

64)

G Q t im "y ‘4

The proof is a straightforward application of the techniques outlined in
section 7. Denoting the three factors on the left of (64) by U, V, W, wechoose as our irreducible basis elements= UOVOW + VOWOU + WOUOVOUOV OWV WOU + wWUOV + w@UVOW= UOVOW + wy OWOU + w" WOUOV= VWOU + w‘WUOV + w‘UVOWUOVOW + w: VOWOU + w*WOU OVThe vector

F
P
xA
zB

z°C
z" D
then satisfies

0q = Mq + z°t(0)Z

where

_

M =

—2a
0

3
—83a

0
0
0

0
0
0

0

0

1
0

1—a
0
0
0

0
1

0
0

0
0

1 — 2a
0
0

2
2 —a
0

0
—1
2 — 2a

—1

0

0

0
0
0
0

t(0) =

3—0Q

Since M and t(0) are independent of z, q can be eliminated by the Cayley
Hamilton theorem, and the result (64) follows by straightforward (if labo—

rious) computation. For details we refer to [7].
68References[1] W.N. Bailey, Generalized hypergeometric series, Cambridge Tract No.
32, Cambridge University Press, 1935.
[2] W.N. Bailey, Products of generalized hypergeometric series, Proc. Lon—
don Math. Soc. (2)28(1928), 242—254.
[3] Th. Clausen, Uber die Falle wenn eine Reihe der Form... , J. Reine

Angew. Math. 3(1828), 89—91.

[4] L. de Branges, A proof of the Bieberbach conjecture, Acta Math.
154(1985), 137—152.
[5] C.H. Fitzgerald and Ch. Pommerenke, The de Branges theorem on uni—valent functions, Trans. Amer. Math. Soc. 290(1985), 683—690.
[6] D.H. Greene and Donald E. Knuth, Mathematics for the Analysis of
Algorithms. Birkhauser, Basel 1981.
[7] P. Henrici, A triple product theorem for hypergeometric series, submit—
ted for publication.
[8] C.T. Preece, The product of two generalized hypergeometric functions,

Proc. London Math. Soc. (2)22(1923), 370—380.

69

Texas Tech University, Mathematics Series
Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

FIFTY YEARS OF LINEAR
ALGEBRA:A PERSONAL REMINISCENCE
P. R. Halmos
Department of Mathematics
Santa Clara University
Santa Clara, California 95053

1

FOUR QUESTIONS(1) Does every matrix have a square root? That is: if A is a squarematrix with complex entries (the real field is too small—it leads to unin—teresting difficulties that conceal the algebraic heart of the matter), does
there necessarily exist a matrix B such that B‘ = A?
(2) Does everyone remember what a normal matrix is? Let me remind
you: according to the geometrically useful definition a matrix is normalif it
is unitarily diagonalizable, or in other words, if the linear transformation it
induces corresponds, after a suitable rotation of the underlying orthonormal
basis, to a diagonal matrix. It is a pleasant algebraic miracle (called thespectral theorem in the finite—dimensional case) that a matrix A is normal
in this sense if and only if it commutes with A* (its adjoint, or conjugatetranspose). Normal matrices are the good ones: most of what is called
unitary geometry is the study of normal matrices, and most of the rest tries
to reduce the study of non—normal ones to that of normal ones. Question:
can every matrix be enlarged (the technical word is "dilated" ) to a normal
one? That is: if A is a square matrix, do there necessarily exist matrices
B, C, and D of, say, the same size, such that
A
| C

B
D

is normal?

(3) A real number is positive if and only if it is a square (a = b°), and,similarly, a complex number is positive if and only if it is the square of an
absolute value (a = bb); by analogy it is reasonable to define a matrix A
to be positive if and only if there exists a matrix B such that A = B*B.
(Frequently used term: "positive definite", or, more pedantically, "non—negative semi—definite.") According to an equivalent classical definition a
T1

matrix is positive if and only if the associated quadratic form is positive,
so that, for instance,

1 1
1 1

|

|‘

with quadratic form zz + yz + zy + yy, is positive, but

A=|8 a}0 1

with quadratic form yz, is not. If a complex number is positive, then it is,in particular, real; similarly if a matrix is positive, then it is, in particular,
Hermitian symmetric; the example A above is not even that.
Question: how nearly can we approximate A by a positive matrix?
That is: as P varies over all 2 x 2 positive matrices, what is the infimumof all possible values of || A — P ||, and at which, if any, positive matrices P
is that infimum attained? Here the "norm" || ———|| denotes the geometricor operator norm—the maximum stretching factor. In other words, for amatrix X, the norm || X|| is the supremum of all the values of ||Xf|| as fvaries over all unit vectors. Equivalently, for the benefit of those of you who

feel more at home with eigenvalues, ||X|| is the square root of the largest
eigenvalue of X*X.
Let us look at the question of positive approximation a little longer.
Given a complex number a, how do we find the nearest real number? Obvi—
ous answer: write a in terms of its real and imaginary parts, a = b+ :c, andpoint to the real one. Next question: given a complex number a, how do
we find the nearest positive (i.e., non—negative) number? Answer: find thereal part of a, and keep it if it‘s positive—if it‘s negative, throw it away andreplace it by 0. More concisely expressed: the answer is the "positive part"b+ of b. Final question along these lines: given a complex—valued functiona (to avoid irrelevant pathology, restrict attention to bounded functions),
how do we find the nearest positive function? ("Nearest" here refers to thesupremum norm—uniform approximation.) Easy answer: write a in termsof its real and imaginary parts, a = b+ ic, and form the positive part b* of
the real part. That‘s it—that‘s the best positive approximant.
Do these considerations shed any light on the problem of positive ap—
proximation for matrices? If

efi
0 1

it‘s easy enough to write A in terms of its real (Hermitian) and imaginary(skew—Hermitian) parts, A = B+ #C; in fact

1 [0 10 1
B= Jb i| ana C= g; | _| o |:72For a Hermitian matrix it makes sense to speak of its positive part (in thespecial case of diagonal matrices that means keep the positive entries andreplace the negative ones by 0). The positive part B+ of B turns out to be1

1

1

4|1 1|
The calculation of the norm || A—B+|| is easy but not especially interesting;the answer to two significant figures is .825. Question: is that really thebest that can be done? Is the conjecture based on the behavior of complex
numbers and complex functions really true? Or could there exist a positive
matrix P with, say, |A — PI < .7257
A curious modification of the problem of positive approximation is the

problem of positive contraction approximation. Question (and this is theone I have really been driving at): how well can a given matrix be approx—
imated by positive contractions—that is by matrices that are positive and,at the same time, have norm not greater than 17? What about the special

case of the matrix‘

6g‘—li a2— how well can it be approximated by positive contractions?
(4) Last question (for now): is the diagonal matrix

1/8
a product of three involutions? That is: do there exist three other 4 x 4matrices R, S and T, say, such that R‘ = S52 = T* = 1 (the identity matrix)
and such that D = RST?

2STATUS OF THE QUESTIONS

That‘s four questions, and I hope you understand in a general way what
they mean, and I hope you believe me when I assure you that none of themis trivial. By the last statement I do not mean that they are profoundresearch questions that I would urge the mathematical world to get towork on—nothing of the sort. I do, however mean that even the experts
in this part of mathematics are not likely to have the answers at theirfingertips, especially not for the infinite—dimensional versions. Aye—there‘s
the rub—for me "linear algebra" includes a part of functional analysis,
the part usually called operator theory on Hilbert space, and although I
asked my introductory questions about finite matrices, they all make sensein the infinite case, and, often, that‘s where the meat of the matter lies.

13

(Warning: when I ask a question about infinite matrices, I mean for them
to be bounded, or, equivalently, continuous linear transformations on thesequence space I°.) I propose to put on record here the extent to which thequestions are non—trivial; I shall report their present standing as far as theknowledge of their solutions is concerned.
(1) Does every matrix have a square root? Every complex number has
a square root: that‘s a yes answer to the question for dimension 1. For
dimension 2 the answer is no; an easy example is

A= | 0e1 | .
Reason: the square of A is 0, so its square root would have to be nilpotent
of index 4, but the characteristic polynomial of a 2 x 2 matrix must havedegree not greater than 2. Nevertheless, it is true that if you avoid 0
trouble, all is well: every invertible matrix has a square root. The proof is
not difficult, but it needs something non—trivial such as the Jordan form.
(2) Does every matrix have a normal dilation? Answer: yes. It is atrivial exercise in high school geometry to prove that every point between—1 and +1 on the real line can be obtained by rotating +1 through asuitable angle in the real plane and then perpendicularly projecting theresult back onto the line. Expressed in terms of analytic geometry the
result says that every number between —1 and +1 can be the top left entry
of a 2 x 2 orthogonal matrix. Mild generalization: every complex number z
with |z|<1 can be the top left corner of a 2x 2 unitary matrix. The pertinent
higher—dimensional generalization (whose proof is a not completely trivial
exercise in a second course on linear algebra) is this: if A is an n x n matrix

with || A||<1, then there exist matrices B, C, and D such thatr—[6 $]

is unitary and a fortiori normal; extension to the case where it is not truethat |[AJ|S1 is just an easy matter of scaling.

(3) The question of positive approximation is a typical one in what has
been called "non—commutative analysis". Unlike other parts of the subject,however, it has an effectively worked out answer. The first test question(can the particular 2 x 2 matrix
A =

0 1

be approximated by positive ones closer than .7257) is an easy special caseof the known theory. I won‘t inflict the derivation of the theory on you, but
I feel honor bound to tell you the answer to the question I have left dangling.
I reported that the positive part of the real part of A is within .825 of A,
74

and I asked whether that could be improved—whether, for instance, there

could exist a positive matrix P such that || A — PI| < .725. The general

theory (1972) shows that the positive part of the real part is not always
a good positive approximation; the non—commutative theory is strikingly
different from the commutative one. The positive part of the real part is
1
4

1 1
1 1

|}

but the unique best positive approximant turns out to beifi
1],
2 1 1 |‘

its distance from A is

2 = .1707 < .725 .

The problem of approximation by positive contractions is, of course, apart of non—commutative analysis also, and it is more typically recalcitrant
than the problem of just positive approximation. The matrix J in partic—
ular, the one whose positive contraction approximation I asked about, hasbeen making me angry for several years. The answer is that I haven‘t the
faintest idea what the answer is, and I would like very much to know—not
so much for J, which, to be sure, is not known, but the answer to thegeneral question of positive contraction approximation.
(4) The problemof writing matrices as products of involutions has re—ceived some attention. Although our knowledge of the solution has someannoying small gaps in it, for most questions the known theory provides
answers. That is true, in particular, for the 4 x 4 matrix D described in
the statement of the problem; the answer there is that it can be written as
the product of three involutions. That answer requires a bit of a proof; it
is not the sort of thing that you look at and immediately nod your headsagely.
In what follows I propose to tell you something about other questions
that I have encountered and what I learned about their answers. I was
involved, alone or in collaboration with friends, in formulating some ofthe questions and finding some of the answers, but many of them are not
my discoveries. I wish they had been—they are all of the kind I love.
Incidentally, they were all discovered during my time, during the last fifty
years. I‘ll tell you about as many of them as I can fit into the time allottedto me, but not necessarily in the order in which they were born. History is
not as systematic as I‘d like to be, and I propose to fix that up.
In the generalized meaning that I am here attributing to the phrase"linear algebra" the subject consists of three parts, and so that we may talkabout them without getting confused I tried to make up descriptive names
to refer to them by. The names I propose to use are finite, superfinite,75

and infinite. Before giving any non—trivial concrete examples, ‘d like todescribe how I propose to use these words.
I shall say that a problem in operator theory is finite (or properly or nat—urally finite) if it makes sense in both the finite and the infinite—dimensional
cases, and if the solution in the finite—dimensional case contains the coreof the idea—the proof in the infinite case is either the same or a merely
technical epsilontic elaboration of the one that works in the finite case.
A problem is superfinite if, just like a naturally finite one, it makes sense
in both the finite and the infinite cases, if its solution in the finite caseis non—trivial at least in the sense that it doesn‘t follow directly from thedefinitions but needs a respectable classical theorem or two to dispose of it,
and if, finally—this is the crucial condition—in the infinite case both thetechnique needed to get the answer and the answer itself are different fromthe finite ones. The infinite part of linear algebra consists of the statementsthat might have been suggested by a finite—dimensional fact, but are vis—ible in the finite situation in a degenerate form only. They are, in otherwords, the statements whose finite versions either do not exist, or, at best,

appear as artificial truncations—the statements that make good sense in

the infinite case only.
Having put some concrete special questions and some vague generaldefinitions before you, I am now ready to go to work.

3

SOME FINITE PROBLEMS

Positive approximation turns out to be a natural example of a naturally
finite problem. The small concrete special case of the matrix

Bois the kind that mathematicians dream about finding: one that contains
within itself all the concepts and difficulties of the general case, and all thesteps needed to understand and to overcome them.
Another good example is the so—called von Neumann inequality. Its
statement is simple:|T]|S1 > lIp(T)II<llplleo,

where T is an operator, p is a polynomial, and ||p||,, is the supremum normof p on the perimeter of the unit circle. This should remind you of anotherstatement:|z21S1 > lp(z)]Sllplleo

which is the classical maximum modulus principle for polynomials on theunit disk. The original proof of von Neumann‘s inequality (1951) is quite
heavy function theory. Since then it has become a simple application of adilation theorem, which itself has a one—word proof (write down a matrix

76and say "behold!"). The proof is naturally finite—it dips a toe into theinfinite ocean, but it works the same way in both the finite and the infinite
cases.
The von Neumann inequality is, moreover, naturally finite, in that its
limits of applicability turned out to be non—trivial problems about finite
matrices, solved in 1973 by Davie, Crabb, and Varopoulos. The problem
was to generalize the result to polynomials in n variables (in which case||pl|« is the polydisk norm, and the operators that enter must be assumed
to commute). Ando proved that that could be done for n = 2; for n > 2 thestatement is false for an interesting and non—trivial reason. Davie, Crabb,
and Varopoulos were able to exhibit three commutative contractions—here
they are, look at them —
0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

| 0 1//3 —1//3 —1//3 0
[0

0

0

0

0

0

0

0

0

0

1

0

(0

0

0

0

0

(0

0

0

|

| 0 —1//3 1/3 —1//3 0|
[ 0

_

0
0

1

0

0

0

0 ~

0

0

0

0

0

0

0

0

— 0

0

0

0

| 0 —1//3 —1//3 1//3 0 |and a polynomial p in three variables—here it is, look at it—
P(A 22, 23) = 27 + 24 + 23 — (zz + az: + 2122)

so that the 3—variable von Neumann inequality turns out to be false. (Inci—dentally, if you like to know such things, the matrices are even partial isome—tries.) As far as the norms go it turns out that the norm of p(Ti, 72,73)
is 3/3 = 5.196 ..., whereas the supremum norm of the polynomial p on
the unit circle, as a bit of elementary geometry shows, is less than 9/2.
(Reason:1|p(21, 22, 23)| < 3 (la — 2] + |z2 — zs3l* + |z3 — a|*),and for [zi], |zl, |z3| S1 the dominant is greatest when z, z;, z3 are thevertices of an equilateral triangle inscribed in the unit circle. In that casethe dominant has the value 9/2.)
T7

It is perhaps worthy of note that the number of variables is 3, which is, inview of the result of Ando, best possible, and the degree of the polynomial
is 2, which must surely be best possible. The dimension of the space is 5,

which is not best possible; Dixon (of Cambridge) showed me an example indimension 4. In dimension 2 the von Neumann inequality holds (Drury); I
don‘t know the facts in dimension 3.
Many of the developments of linear algebra, even old ones and evennaturally finite ones, still have unanswered questions. The von Neumanninequality is a prime example of what is still largely undeveloped territory—

non—commutative analysis—and I‘ll just mention one of the important prob—
lems of that subject in a teasingly vague form: develop a more extensive
non—commutative analytic function theory. Let me add a theological re—mark: questions in which the source of interest is non—commutativity (inthe sense that they become degenerate or obvious in the commutative case)are likely to be naturally finite. In other words, finite—dimensional linear
algebra is already as non—commutative as anything can get. That is not to
say that non—commutative analysis is of no interest outside of finite matrix
theory—just the opposite is true. Non—commutative analysis is an algebraic

subject, in the sense that the techniques and results depend heavily on thealgebras (von Neumann algebras and C* algebras of variously complicatedstructures) in which the questions are asked.
Mild generalizations of the von Neumann inequality are still being proved,sometimes by people who proudly announce that they have devised a proof

that "avoids dilation theory". Since the dilation theorem is, as I have said,
a no—word consequence of elementary linear algebra, to me that sounds likesaying "this is a book about arithmetic that avoids multiplication".

In

effect that means either using awkward methods, or else repeatedly using
the definition of multiplication as repeated addition. Or maybe a better

analogy is to speak proudly of a book that avoids the use of the letter k.
Why bother?
A non—trivial finite problem arose first in the work of Lax and Wendroff
on hyperbolic partial differential equations (1962). They needed to consider
the so—called numerical radius w(A) of an operator A on a Hilbert space.
Definition:—|w(4) = sup{|(4f, £1 : IfIl = 1}.

The result they needed was that if w(A)Z1, then A is "power bounded" inthe sense that the norms || A" || form a bounded set. They proved the result
for spaces of finite dimension only; the bound that they obtained depended
on the dimension and grew very rapidly as the dimension became infinite.
In an attempt to simplify the proof, improve the bound, and extend theresult to infinite—dimensional spaces, I stuck my neck out and conjectured
the "power inequality"

w(A")S(w(A))".
78

I pointed out that if that were true, then it would follow that|4*]]S2w(4*)S2(w(4))"<2
whenever w(A)ZS1. That would then surely be a maximally simple proof,
with best possible bound, under completely general assumptions. (Theinequality || A||S2w(A) is elementary.) Many people worked on the problem,
but at first only small pieces of it seemed to be accessible. Pearcy and I
proved it for n = 2 and all dimensions, and (Arlen) Brown proved it for
dimension 2 and all n, but the general case remained open till Berger‘s
ingeniously complicated proof in the spring of 1965 settled everything.

4

SOME SUPERFINITE PROBLEMS

Motivated by the finite—dimensional facts, Kaplansky conjectured that in—vertible operators always have square roots. Should the use of the Jordan
form in the proof of the finite—dimensional case have been a hint of trouble?
Maybe so. In any event, the answer is different in the infinite case: invert—
ibility is not enough for the possession of a square root. The first exampleof this phenomenon was noted by Lumer, Schaffer, and myself (1953); ourexamples are "analytic position operators" over bounded domains. Suchan operator has a square root if and only if the square root of the domain

found& | b) [mt& [— bo mt

pes

is disconnected, or equivalently, if and only if 0 belongs to the unbounded
component of the complement of the domain.
These considerations do not close the subject, however. It‘s all very
well to be able to say that certain classes of matrices always do have squareroots and other ones don‘t, but, given a particular matrix, how do we cometo a conclusion about it? Consider for an attractive example the Cesaro
matrixwhich converts a sequence numbers into the sequence of their averages.
Does it have a square root? I don‘t know why it is so, but I report asa sociological observation that most mathematicians like the question andare eager to pick up pencil and paper and start looking for an answer assoon as they hear it. The search is likely to be successful; all you have to do
is to guess that the answer is yes and, moreover, that a triangular matrix
can be found that does the trick, and then start a recursive calculation.

The trouble with that technique is that there is no guarantee that theresulting square root matrix is a bounded one, and, as I said before, inthis context boundedness is always a healthy assumption to insist on. The
healthy question has an affirmative answer too, but the proof takes more

T9

intellectual effort than mere calculation; it depends on some surprisingly

recent work of Conway in collaboration with Morrel on one occasion andOlin on another.
There are many more superfinite problems of interest than naturally
finite ones; they (the superfinite ones) are usually harder. My next ex—
ample, about commutators, is one that exerted a strong fascination on
many mathematicians in its day. Consideration of commutators, that isof operators of the form AB — BA, is algebraically natural and physicallyinevitable. The celebrated Heisenberg uncertainty principle says that thecommutator of the position operator (xf(x)) and the momentum operator,(f(x)) is a non—zero multiple of the identity. That turns out, however, tobe very infinite—dimensional fact, and, what‘s worse, the operators in ques—tion aren‘t even bounded. Wintner (1947) and Wielandt (1949), working

independently, proved that 1 is not a commutator in the bounded case, andhence, in particular, never in the finite case.
It is natural to ask: which operators are commutators? In the finite
dimensional case it is trivial to see that a necessary condition is trace 0;

sufficiency takes a little more work. The infinite—dimensional case was elu—
sive for a long time, and some conjectures arose that ultimately turned
out to be false. (That‘s not uncommon in the superfinite part of linear
algebra.) Wintner, for instance, conjectured that if C is a commutator,
then the inner products (Cf, £), with || f {| = 1, must get arbitrarily near to

0. My small success in the subject settled that conjecture (negatively): I
proved the existence of a commutator C such that the real part of (Cf, f)

is equal to 1 for every unit vector f. There were other partial results thatwere surprising: for example, every operator is the sum of two commuta—

tors (1954). The ultimate victory was won by (Arlen) Brown and Pearcy(1965): if A #0 and the operator K is compact (a concept I shall discusspresently), then A + K is not a commutator; everything else is.
Another good example of a superfinite theorem about operators is theone about dilations. The existence of unitary dilations of finite matrices isa geometrically useful fact, but one whose algebraic applicability is severely

limited by possible multiplicative misbehavior. The trouble is illustrated
by the fact that even if T is a dilation of A, it may not be true thatT° is a dilation of A". What saves the day is the powerful and widely
applicable power dilation theorem of Nagy (1953): it asserts that, in theinfinite—dimensional case, T can be constructed so that"18 $]n_4" B.

for suitable operators B,,, C,,, D,,.
I‘ll conclude this part of the discussion with a brief report on the involu—tion problem. The elements of order two are of algebraic and frequently ofgeometric interest in every group; one natural question is to ask about the80

subgroup they generate. If you are lucky they generate the entire group: inmany familiar groups every element is a product of involutions. (I remind
the geometers that every rotation is the product of two reflections.) The
version of the question that is pertinent to linear algebra is this: in thefull linear group, that is the group of all invertible matrices, which ones

are finite products of involutions? A few seconds‘ meditation will show youthat in the finite case a necessary condition is that the determinant of thegiven matrix be +1. Sampson proved in 1974 that under that condition
every (finite) square matrix over the field of real numbers is the product ofa finite number of involutions, and a couple of years later (1976) (W.H.)
Gustafson, Radjavi, and I proved that every (finite) square matrix of de—terminant +1 over any field is the product of four involutions. (The easiest
part of the subject is to see that fewer than four will not always do.)
The main idea in the proof is to consider the so—called companion ma—
trices, such as, for example,
0
1

0
0

O0
0

—1
z

0

O0

1

z

0 1 O0y.

and observe that by permuting their columns we make some algebraic profit.
To be more explicit: if we make the last column first, the result turns out
to be an involution. Otherwise said: the given companion matrix is the
product of an involution with a permutation matrix, and permutation ma—
trices are always products of two involutions. Conclusion: every companion
matrix with —1 in the northeast corner is a product of three involutions; if

the —1 becomes +1 the number of factors might have to be raised to four.
These comments constitute the largest step in the proof; by stitching them
together properly we obtain the desired factorization every time. So muchfor the finite part of this superfinite subject.

The infinite question is hard even to begin to ask: what can possibly

take the place of the determinant condition? The only thing that‘s obvious
is that a product of involutions is invertible.

Could it possibly be thatevery (bounded) invertible matrix is a product of (bounded) involutions?
Somewhat miraculously the answer turns out to be yes, and Radjavi proved
that, in fact, every bounded operator on Hilbert space is the product of not
more than seven involutions. The remaining question along these lines is
how good the number seven is. It turns out that four is no longer goodenough, and the example to prove that negative statement is pleasantly
simple — the matrix 2 (that is twice the identity matrix) does the job.
Whether the exact truth that fits the class of bounded matrices is 5, or 6, or
7 is something that nobody on this planet knows. It‘s a frivolous question,
surely not important, but, as with many other mathematical problems, it
is regarded as a challenge simply because the answer is not known. That‘s
81exasperating—I‘d like to know, so that I could then in good conscience
forget about it.

5

SOME INFINITE PROBLEMS

A curious example of a properly infinite concept is that of a compact opera—
tor. An operator is called compact if it is the limit in a sufficiently powerfuluniform sense of finite—dimensional ones (or, more precisely speaking, of op—
erators of finite rank). An easy example is given by the infinite diagonal
1#> [m=GJ [bekb [—matrixEvery finite—dimensional operator is compact—the concept makes no finite—

dimensional distinctions, and in that sense it becomes "degenerate" in thefinite case.

Every matrix of finite rank has eigenvalues and eigenvectors. For oper—
ators on infinite—dimensional spaces that‘s false, even in the limiting caseof compact operators. That falsity is the first obstacle that the search forinvariant subspaces has to face. The existence of non—trivial invariant sub—spaces for arbitrary operators on Hilbert space is still not known; for a longtime even the compact subcase was an open problem. The first solution was
published by Aronszajn and Smith (1954), but it took till 1966 before theproblem was solved for square roots of compact operators (A. Robinson and

A. Bernstein), and till 1973 before the existence of simultaneous invariant
subspaces for two commuting compact operators become tractable. (Re—call the facts about the simultaneous triangularizability of two commuting
finite matrices.) The latter was a difficult challenge, and operator theorists
worked on it quite hard—the sudden and spectacularly elementary solution
by Lomonosov came as a highly applauded surprise.

The Bernstein—Robinson proof used non—standard models of higher order
predicate languages. When Robinson sent me a copy of their preprint, I
really had to sweat to pinpoint and translate its mathematical insight. Yes,
I sweated, but, yes, it was a mathematical insight and it could be translated.

The paper did not convince me that non—standard models should forthwith
be put into every mathematician‘s toolkit. It showed only that Berstein
and Robinson were clever mathematicians who solved a difficult problem

using a language that they spoke fluently. If they had done it in Telegu
instead, I would have found their paper even more difficult to decode, but
the extra difficulty would have been one of degree, not of kind.
Some people believe that the invariant subspace problem for Hilbert
space has an affirmative solution, but they cannot even suggest a promising82

beginning of a proof; others believe that the solution is negative, but theycannot even come up with a reasonable candidate for a counterexample. I
belong to the negative team, and I am no better off than anyone else about
offering a good candidate. Nevertheless, I should like to offer you a small
bunch of possibilities. The matrices I would like to know about are the ones
that have zero entries everywhere except in the two diagonals next to theprincipal one, and there have the following structure: the diagonal below
the principal one consists of all 1‘s, and the diagonal above is "nasty".
What might "nasty" mean? It could perhaps mean alternating sequencesof 1‘s and 2‘s (0‘s are no good — they quickly lead to invariant subspaces)with lengths increasing rapidly to infinity. Another possibility: the diagonal
above the main one is a sequence of complex numbers dense in the unit disk.
Examples similar to these have been studied (by Constantine Apostol for
instance), and what is known so far is not encouraging, but where else canwe look?
|
One place used to be in the theory of the so—called subnormal operators(they will be mentioned again a little later), but that direction was closedby (Scott) Brown‘s inspired originality (1978) proving that they all do have
non—trivial invariant subspaces.

A classically important and essentially infinite concept is the alreadymentioned Ceséaro matrix. It can be truncated and then studied in a finite—
dimensional context, but most of its importance and flavor are lost whenthat‘s done.
Toeplitz matrices (the ones with constant diagonals) are another essen—tially infinite example; they are a classical subject, but relatively recently(1984) they became a major industry with important new breakthroughs.
They too can be truncated, and, in fact, their finite versions have been

extensively studied and constitute a very respectable and difficult part ofclassical analysis.
|
There are still challenging unsolved problems in the theory of Toeplitz
matrices, and many of them can be formulated algebraically. The productof two Toeplitz matrices is not necessarily a Toeplitz matrix, and, therefore,
the right thing to look at is the so—called Toeplitz algebra, the algebra
generated by all Toeplitz matrices. That is: form all finite sums of finite
products of Toeplitz matrices, thus getting an algebra, and, as a precaution,
be suitably courteous to the infinity of the situation by closing that algebrain the appropriate metric topology. The first open question I should like tomention about that algebra concerns the Cesaro matrix. The question is:
how Toeplitz—like is C? That C is not a Toeplitz matrix is obvious. Is it
perhaps the product of two Toeplitz matrices, or of three or four or someother number—or could it be that C is a sum of such products, or, in theextreme case, that C is a limit of such sums of products? The answer is
not known: it is not known whether C belongs to the Toeplitz algebra, andI no longer even dare to make a guess about the answer.
83

Another curious and algebraically important question concerns zero di—visors in the Toeplitz algebra. It is obvious that a Toeplitz matrix can be 0
only if all the coefficients that define it are 0. Hartman and Wintner knew

long ago (1950) that the product of two Toeplitz matrices can be 0 only
if one of the factors is 0—in that sense there are no zero divisors. Barria
and I proved considerably later (1983) that the same conclusion holds for
products of three Toeplitz matrices. The question for four is outstanding.

Isn‘t that strange?
The most illuminating and most important essentially infinite concept
is the unilateral shift—the operator that acts on the sequence space I° by
mapping < £0, 61, &2,+++~ > onto < 0,60, 61, 62, ~~ >—it is, in fact, fair tosay that everything essentially infinite has to do with the unilateral shift.
(The Cesiro matrix and Toeplitz matrices are no exceptions.) Its modern
study was initiated by Beurling (1949), who determined all its invariant
subspaces—a subtle piece of work that opened a new field of mathematicalresearch.

The shift is essentially infinite because its very definition shows its con—nection with Dedekind‘s definition of infinity (the existence of a one—to—one
correspondence of a set with a proper subset). Another perhaps more ob—vious way of producing incontrovertibly infinite phenomena is to throw
everything finite away. In the algebra of all operators the ones of finite
rank, and even their uniform limits, the compact operators, are the ones

that are, despite being essentially infinite, very "finite—like". To "throw
them away" means the same thing as it means to throw away sets of mea—
sure zero in measure theory—it means to identify them with zero. In moredignified technical language, the set of compact operators forms an ideal,
and to throw them away means to reduce modulo that ideal, to identify
two operators in case they differ by a compact operator only. The quo—tient obtained by reducing the algebra of all operators modulo the ideal ofcompact operators is called the Calkin algebra.
To see how consideration of the essentially infinite Calkin algebra canyield interesting results, consider the algebraic formulation of the invariant
subspace problem. If A is an operator on a Hilbert space H, then the in—variance of a subspace M of H under A (AM C M) can be expressed interms of the orthogonal projection P with range M as follows. Since forevery f in H, the vector Pf is in M, it follows from the invariance of M
that AP f is in M also, and that, therefore, APf is invariant under P. That

is: PAPf = AP f for all f, so that PAP = AP. This algebraic condition
makes sense in many algebras other than the algebra of all operators on H,
and, in particular, it makes sense in the Calkin algebra. Whenever projec—
tions make sense in an algebra, we can ask, for each element a, whether or
not there exists a non—trivial projection p (that is, p # 0, p # 1) such that
pap = ap; if the answer is always yes, then in that algebra a good analogueof an invariant subspace theorem is true. In the purely finite case of the84

full operator algebra over a space of dimension n, with 1 < n < 00, that isthe case, and, perhaps, surprisingly, it is the case also in the purely infinite
Calkin algebra (a result obtained in 1972 by (Arlen) Brown and Pearcy
and, independently, by Fillmore—Stampfli—Williams). The unsolved invari—
ant subspace problem concerns the full operator algebra over an infinite
dimensional Hilbert space.
The Calkin type of invariant subspace theorem is an essentially infi—
nite result, but not the deepest of that kind. A much deeper one is thecelebrated theorem of Larry Brown, Douglas, and Fillmore (1973) about
unitary equivalence. It is not possible to describe that result in four or fivelines in an understandable manner (four or five pages can do it easily), but
I can tell you what sort of thing it does without telling you how it does it.
The classical result about unitary equivalence is the principal axis theorem:
two normal matrices are unitarily equivalent if and only if they have thesame diagonal form, or, equivalently, the same eigenvalues with the same
multiplicities. The BDF theorem is a similar necessary and sufficient con—dition for the unitary equivalence of two elements of the Calkin algebra; thecondition is expressed in terms of the spectra of the given elements and interms of the behavior of a certain integer—valued function, called the index,
defined on the complements of the spectra.
|

6 STILL MORE LINEAR ALGEBRAThere is much more linear algebra than any one article such as this one
can mention, let alone discuss, and I have had to restrict the discussion to
those subjects that I was personally involved in. I could have mentioned
some others (such as reflexive and transitive algebras and lattices, partial
isometries, capacity in Banach algebras, and semi—continuity properties ofinvariant subspace lattices) that I am proud to have been at least marginallyassociated with, but too much is too much. And, besides, there are, in
addition to thesubjects I have just now not mentioned, three others that
I love dearly and that no modern discussion of operator theory can afford
to omit completely. They are (1) non—commutative approximation theory,(2) quasitriangular operators, and (3) subnormal operators.
(1) A typical question in non—commutative approximation theory, a su—
perfinite question, is whether almost commutative matrices are nearly com—mutative. Stated that way the question might sound like a feeble attempt

at humor, but it means something serious. The question can be expressedin sequential terms or, alternatively, in terms of the familiar e—6 languageof analysis. For sequences it becomes this: if

A, B., — B,,A, — 0,
does it follow that there exist sequences A‘, and B/, such thatAB‘, = B‘A‘,
85

and

A, — A,, — 0 and B,, — B/, — 0 ?

Analytically: is it true for matrices of size k that for every e > 0 there is a6 = 6(e, k) such that if A and B are matrices of size k with [| A|S1, || B\|S1,
and || AB — BA\l < 8, then there exists a commutative pair of matrices A‘
and B‘ of size k such that|| A — A‘) <e and ||B — B‘ <e ?
The two formulations are equivalent to each other, and in the finite casean easy compactness argument yields the affirmative answer. The infinite
case has been an open problem for quite a long time; it was recently solved,
negatively, by Choi (1986). He exhibits, for each positive integer n, twon x n matrices A and B such that ||A||<S1, ||BJ|S1,|4B — BAJE2/n,
but at the same time,|A — 4‘|| + ||B — B‘||Z1 —1/n .
whenever A‘ and B‘ are commutative n x n matrices. Several other impor—tant problems of the same kind are still unsolved; notable among them isthe same "almost—nearly" problem for Hermitian matrices. Much valuable

work has been done by Ken Davidson and Dan Voiculescu, but the ultimate

truth is still elusive.
(2) Diagonal matrices are the easiest to work with and triangular ma—
trices are the next easiest. The superfinite concepts suggested by and anal—© ogous to these essentially finite ones are called quasidiagonality and quasi—
triangularity. A simple approach is this: a typical quasitriangular matrix
is one that is a compact perturbation of a triangular one—that is the sumof a triangular matrix and a compact one. (Example: the shift, with theentry in position n* on the subdiagonal changed from 1 to 1/n‘.) That‘s

not the original definition (1968), but it‘s equivalent to it and is easier tocommunicate in a lecture such as this. The concept suggested itself when
I was trying to understand what made the Aronszajn—Smith proof of theexistence of invariant subspaces for compact matrices work—the abstrac—
tion behind it seemed to be quasitriangularity. Because of that connection
I conjectured that at least quasitriangular matrices always have non—trivial
invariant subspaces—and I turned out to be spectacularly and interestingly
wrong. It‘s not that they don‘t—at the present state of knowledge nothing
like that could conceivably be said —but what turned out, as a result of thebrilliant and deep work of the Romanian mafia (Apostol, Foias, Voiculescu)
is that the matrices that are not quasitriangular can be proved to have non—trivial invariant subspaces (1973), and that, therefore, the general invariant
subspace problem reduces to the quasitriangular case. Quasitriangularity
86continues to be at the center of much work in operator theory, and I thinkit can be described as a typically superfinite concept.
(3) An operator on a Hilbert space is called subnormalif it has a normal
extension to a larger Hilbert space. The theory of subnormal operators
is difficult and important and is usually thought of as belonging to thetypically infinite part of the theory. Recently, however, I ran across abunch of questions that are in the finite part and that are sufficiently closely
connected with subnormality to seem to demote that infinite subject to asuperfinite one. I would like to tell you about a couple of those finite
questions.
For an absolutely typical example, consider a rectangular matrix, 6 x 3
say—that‘s what I shall mean here by the word "submatrix"—and call it
subnormal in case it can be completed to a square matrix (6 x 6 of course)that is normal. In the usual vague terms that mathematicians use when
they begin the study of a new concept, the principal research problem about
subnormal submatrices is just to characterize them—how can you tell when
you are looking at one?
Look, for example, at the 6 x 3 submatrix
GOG—
GO G G ®
&

®

— G
O & G

L

C

O&O & m ® —=—Is it subnormal? The answer turns out to be no. The proof, which it
might be fun to look at, makes use of an easily usable characterization of
normality: a necessary and sufficient condition that a matrix be normal isthat the unitary geometry of its rows be the same as it is for its columns.
That means, in particular, that the length (norm) of each row is the same as
the length of the corresponding column, and that two rows are orthogonal
to each other if and only if the corresponding columns have that property.
Now then: if the matrix could be enlarged to a normal one, then, because
its third column has norm 1, the missing entries of the third row would haveto be zeros. But that then would imply that the third row is orthogonal
to all other rows, and hence that the third column has to be orthogonal toall other columns. That, in turn, implies that the norm of the first row has
to be 1, and, therefore, that the norm of the first column has to be 1 also.
Since, however, the norm of the first column is /2, we have crashed into acontradiction, and we must conclude that the submatrix is not subnormal.
This elegant example is due to Nordgren.
|
There is a definite topological question more specific than the slightly
vague one of characterization. One of the major theorems of the theoryof subnormal operators is due to Bishop (1957); it says that in a suitable87

topology they form a closed set. The subnormal submatrices do not forma closed set. The reason is that the 6 x 6 matrix[0 0 10

1

0

0

1

0

0

0

0
0

0

s
0

€

0
—1/s

0

e

0

0

_—1

0

0 1 0
1 0 0

| 0 0 s —1/s

0

0

]

__

(discovered by Barria) is normal for every non—zero value of the parametere.

The proof of that assertion is brutal computation: multiply by the

conjugate transpose in both orders and look. It follows that the first threecolumns of the matrix constitute a subnormal submatrix for every non—zero e; since, however, the limit of those submatrices as e tends to 0 is

the Nordgren counterexample, it follows that subnormal submatrices canconverge to non—subnormal ones.
What is the closure of the set of all subnormal submatrices? I have put
in some effort to try to find out, but so far fruitlessly.

7T

CONCLUSION

With that I must stop. I have given you a large handful of examples oflinear algebra that I have seen grow in my time, some of each of the threekinds (finite, superfinite, and infinite) into which it may be convenient toclassify them—but, believe me, that‘s nowhere near all there was. I had toleave out at least as many topics as I could include. The subject is alive,
important problems still remain to be solved, and connections with andapplications to other parts of mathematics continue to be discovered.
Has the subject changed as well as grown"? Is there a trend visible? Are
new methods coming to the fore? It‘s dangerous to raise questions such asthat and to try to answer them, but I‘ll stick my neck out and hazard aguess. I am inclined to think that the subject is now more analytic and lesscombinatorial than it used to be, and that therefore it is perhaps harderbut not necessarily deeper. I predict that before long the pendulum might
have to swing back. Let me explain what I mean by this unorthodox useof language.
I am inclined to believe that at the root of all deep mathematics there

is a combinatorial insight. I think, for instance, to mention an example
from linear algebra, that the Jordan form theorem is a combinatorial the—orem, and that all its proofs involve, in one form or another, a deep lookat the geometric structure of the parts of a linear transformation—the sortof deep look that the von Neumann inequality does not need. The von
Neumann inequality may be technically difficult, but it isn‘t all that deep.

88The determination of the counterexamples to the many—variable von Neu—mann inequality, on the other hand, isn‘t all that hard, but I think it tooka deeper combinatorial insight.
I am not defining what I mean by combinatorial versus analytic—I amjust illustrating my use of the words. Let me try it again. The spec—
tral theorem (finite or infinite) involves counting (measure) and addition(integration)—that‘s the deep combinatorial heart of a statement that iswell within the reach of students—where as some of the facts about Toeplitz
operators are accessible via some quite difficult complex analysis only, but
I don‘t think they are as seminal.
That then is the sense in which I think linear algebra is currently more
analytic than it once was. I think that in this subject (in every subject?)the really original, really deep insights are always combinatorial, and I think
for the new discoveries that we need the pendulum needs to swing back,and will swing back in the combinatorial direction.
That‘s the end, and while I can not know what you, listeners and read—ers, thought of it, I enjoyed it very much. I hope that fifty years from now
you‘ll invite me again, so that I maytell you about my personal reminis—
cences of a hundred years of linear algebra.

89Texas Tech University, Mathematics Series

Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

Controlled Markov Processes: Recent
Results on Approximation and Adaptive
ControlOnésimo Hernandez—Lerma*
Departamento de Matematicas
Centro de Investigacion del L.P.N.

Apartado Postal 14—740, México, D.F. 07000. MEXICO

Abstract

Recent results on the approximation and adaptive control of discrete—time, infinite horizon, controlled Markov processes with discounted re—ward criterion are surveyed, including parametric and non—parametricproblems.

1

Intro duction

This is a survey of some recent contributions to the approximation andadaptive control of Markov processes. The paper is self—contained, in thesense that no previous knowledge of stochastic control theory is assumed
and—except for proofs readily available in the literature—all the resultspresented are proved here.
We restrict ourselves to discrete—time stochastic control systems withcomplete state information and discounted reward criterion, but extensions
to other cases (e.g., semi—Markov processes, partially observable systems,
and problems with average reward criterion) are briefly indicated.

1.1

Organization of the Paper

In Section 2 we present a detailed description of the stochastic control
systems we will be dealing with; these are the so—called Controlled Markov
Processes (CMP‘s), also known as "Markov decision processes" or "dynamic
programs". An example of an inventory/production system is included toillustrate the main concepts.
*Some of the research summarized in this paper has been partially supported in the last
few years (1984—present) by the Consejo Nacional de Ciencia y Tecnologia (CONACyT).

91

Section 3 contains some basic, well—known results on discounted—reward

CMP‘s, such as the dynamic programming equation (3.1) and the conver—gence of the value—iteration functions v, in (3.5). It also contains someresults on "asymptotic discount optimality", a notion introduced by Schal[38] to study certain adaptive control systems, i.e., systems depending on
unknown parameters.
In Section 4 we present the Nonstationary Value—Iteration (NVT) schemes
to approximate control models. The NVI schemes were originally intro—
duced by Federgruen and Schweitzer [10] for Markov decision processes
with finite state and action spaces and they have proved to be very useful toobtain different types of approximations and adaptive policies for stochas—tic control problems. Some of these results are developed in Section 5 foradaptive CMP‘s; namely, the NVI results are used to obtain asymptoti—cally optimal "adaptive" policies, i.e., policies combining "estimation andcontrol".
|
Section 6 is on non—paerametric adaptive control systems, that is tosay, systems in which the transition law itself—and not only some of its
parameters—is unknown. The approximation and optimality results inthis section require a more restrictive setting than that of the parametriccase.
We conclude in Section 7 with some general remarks and comments on

possible extensions.

1.2

Terminology and notation

A topological (respectively, product) space, say X, is always endowed with

the Borel (respectively, product) sigma—algebra B(X). The cartesian prod—
uct of sets X and Y is denoted by XY. Throughout the following X and Y
denote Borel spaces. (Recall that a Borel space is a Borel subset of a com—plete separable metric space.) B(X) and C(X) denote, respectively, thespace of real—valued bounded measurable functions on X, and the space ofbounded continuous functions. A stochastic kernel (or conditional proba—
bility measure) on X given Y is a function g(dz|y) such that for each y E Y,q( — |y) is a probability measure on X, and for each Borel set B c B(X),q(B|—) is a Borel—measurable function on Y. For a function v in B(X),[|v|| denotes the sup norm, and for a finite signed measure 4 on B(X), |{p]|denotes the total variation norm [36]. Recall that for any such v and 4,|[ +«»| s Iolllell

_

(13)

The indicator function Ip of a set B is defined by Ip(z) := if a e B, andIs(x) := 0 otherwise.

92

2

Controlled Markov Processes

An optimal control problem requires three components: a control (or de—cision) model, a set of admissible policies (or control strategies), and an
objective function (or performance criterion). These components are de—scribed in this section for the case of controlled Markov processes.

2.1

Control models

These are determined by five objects (X, A, D,q,r), where:(i) X is the state space, which is assumed to be a Borel space.
(ii) A is the control set (or action space) and is assumed to be a Borel
space.
(iii) D is a set—valued function which assigns to each state z E X anonempty Borel subset D(z) of A, which denotes the set of admissible
controls in state z. We assume that the set of admissible state—action

pairs

K := {(z,a)|z € X and a € D(z)}(2.1)

is a measurable subset of the product space XA. The pairs (x, a) in
K will be denoted sometimes by k.
(iv) q(dz|k), the so—called transition law (or law of motion), is a stochastic
kernel on X given K.
(v) r: K — R is a measurable function denoting the one—step reward (orreturn or income) function.
A control model is interpreted as representing a system which is ob—
served at times + = 0,1,...; the state and control at time t are denotedby z; and a;, respectively. If the system is in state x; = z at time t and
we take the control action a; = a € D(z), then we receive a reward r(x, a)and the system moves to a new state z;4, = z‘ according to the probability

distribution g( — |x, a) on X. Once the transition into z‘ has occurred, a newcontrol a € D(z‘) is chosen and the process is repeated.
In many control problems, instead of the transition law above, we are
given an explicit system equation
ZLty+1 — F(x;, a;, 61),i = 0, 1, « + +g

(2.2)

where the disturbance or driving process {&;} is a sequence of independent
identically distributed (i.i.d.) random elements, with values in some Borel
space S, and independent of the initial state zo. If u denotes the common
distribution of the &;, then the transition law q, that is,q(Blz,a)= Prob {z}4i € B | zi =z, a; =a}93can be written asa(Biz,a)= [ I» [F(z, a, s)] u(ds).
In adaptive control problems, q and r are allowed to depend measurablyon unknown parameters 0, in which case the control model is written as(X, A, D, 4(0), r(0)).

A vector h; := (Zo, 4o,——.,Zt—1,4—1, Z;), where (x;, a;) € K for all : =0,1,..., is called a history of the control system up to time t. For eacht = 0,1,..., h; is a vector in the space of histories H,, where Hy := X andH, := KH,;_i for t > 1

2.2

Policies

A policy is a sequence 6 = {6,} of (possibly "randomized" [28]) measurable
functions 6, : H,; — A such thatdi(hi) E D(zx;)

for all h} E H, and t = 0, 1, ee

These "history—dependent" (or non—anticipative) policies are particularly
important in adaptive control problems: to compute estimates of the un—
known parameters it is sometimes necessary to use the full history /A; of theprocess at each time t. In standard control problems, however, it is usually
sufficient to consider policies which, at each decision time, depend only on
the present state.

Thus we define a Markov (or feedback) policy as a sequence 6 = {f,}of functions f; E F, where F is the collection of all decision functions(or selectors), that is, measurable functions f:X — A such that f(x) E
D(x) for all zx € X. Moreover, a Markov policy {f,} such that f; = f isindependent of t is called stationary; to specify such a policy we will simply
write f C F. (Some authors denote a stationary policy f C F by f*.)Given any initial state z, = z, together with the transition law q, a pol—icy 6 defines a probability measure P? on the product space Q := X AXA ...
endowed with the product sigma—algebra, say J, and thus a random pro—
cess (Zo, 40, £1, 41, ...), and the state and control variables x; and a, denoteprojections from 2 into X and A, respectively. (For details, see, e.g. Hin—derer [28], p.80). The process (Q, F, P3, {z}) thus constructed is called acontrolled Markov process (CMP).
Remark. From the construction [28] of P? it can be obtained that if 56 ={f,} is a Markov policy, then the state process {x,} is a non—homogeneous
Markov chain with transition kernelPi(z1 € Biz}) =q4(Bizi, fi(x;)),where B E B(X), t =0,1,....

For a stationary policy f E F, the process {z,} is a homogeneous Markov
chain.
94

Expectations with respect to P? are denoted by ES.
For adaptive control models (X, A, D, q4(0), r(0)), the probability PJ will
be written (in Sections 5 and 6) as PS", and the expectation EF as EF.

2.3

Objective function

This is a function V(6, z) that "measures" the system‘s performance when
the policy 6 is used, given that the initial state is z. We are concerned herewith the expected total discounted reward defined asV(6,2) := E} {£ B‘r(z;, «)}(2.3)

with discount factor 3 E (0,1). In the following sections we will assume
that r is a bounded function, so that V(6, z) is finite for all 6 and z.
Remark. There are, of course, other performance criteria. In particular,
results on approximations and adaptive policies for the long—run average
expected reward per unit timen—1

V‘(6,z) := liminf n~‘ E2 Y r(ar, aq)

(2.4)

=0

are given in [1,10,12,13,18,31,32,33,34].

2.4

Optimal control problems (OCP‘s)

Once we have a control model, the set A of admissible policies and an
objective function, we define the OCP as follows: Find a policy 6* E Asuch that||
V(8*,z) = v*(z)for all z € X,
(2.5)
where

v*(z) := sup V (6,2),
SEA

z € X,|(2.6)

is the optimal reward (or optimal value) function. Any policy 6* satisfying(2.5) is said to be (discount—)optimal.
In adaptive control problems, however, in general it is not possible toobtain optimal policies. Namely, if the expectation E? and the one—stepreward r in (2.3) depend on an unknown parameter 0 which has to be es—
timated at each time t = 0,1, ..., one cannot expect to obtain an equality
such as (2.5). (Notice that, in contrast, for the average reward criterion(2.4) it is indeed possible to obtain optimal adaptive policies, because, un—der appropriate assumptions, the estimation errors introduced in (2.4) are"cancelled out" in the limit.) Thus for adaptive problems with discounted
reward criterion, it is necessary to consider a weaker notion of optimality.

95

Definition 2.1 [38] A policy 6 is said to be asymptotically discount opti—
mal (AD0) if, as n — 00,|V.(6.2) — Biv*(zn)| — 0
wherefor all zx € X,

(2.7)

oo

V.(6, 2) := Ef > B‘~"r(a;, a)}ti=n

is the expected total reward from stage n onwards discounted at stage n.
The fact that a policy 6 is ADO if it is optimal follows from Bellman‘s
principle of optimality [28, p. 109]: 6 is optimal iff E$v*(x,) = V.(6, z) for
all n» > 0 and xz € X, in which case the left side of (2.7) is zero for all n and€.
In the following section we will review some useful criteria for optimality.
But first, we present an example.

2.5

An example: control of inventory/production
systems

Consider a finite capacity (C < coo) inventory/production system [2,4,9].

The state variable z; is the stock level at the beginning of period t; a; isthe quantity ordered: or produced in that period, and &; is the demand.
Denoting by y; := min(€;, z; + a;) the amount sold during period t, thesystem equation becomes
Zi41 = Zi + 4 — ¥e = (i+ a — 6);

Zp given,(2.8)

where vt := max(0,v).

Clearly, the state space and the control set are X = A = [0, C], whereas
the set of admissible controls in state z is D(z) = [0,C — z]. To computethe transition q, let us assume that {€,} is a sequence of i.i.d. randomvariables with common distribution p, which is absolutely continuous withdensity g:u(5) = few ds

for all Borel sets S in R.

Thus for any admissible pair k = (xz, a) and any Borel subset B of X,q(Blz, a)[ Iel(@ +a — s)] u(ds)= f In(e+a—s)]9(s)4s,
where Ip(—) is the indicator function of set B.
The (expected) one—stage reward r(x, a) may have different forms, de—pending on the specific situation we have in mind. For instance, if we are96

given the unit sale price (p), the unit production cost (c), and a unit holding
cost (h), then the net revenue in stage t is
T; — PY: —— CU; — h(xi + ti),and r(x, a) becomesr(c,a) = E(r;|x;=z,a,= a)= [ pmin(s, a + a) — ca — h(x + a)] g(s) ds.
This completes the specification of the control model (X, A, D, q, r) and theset of admissible policies.
The optimal control problem for both types of performance criteria (2.3)
and (2.4) has been studied in the literature [2,4,9], and also the adaptive
control problem in which the demand density g depends on unknown pa—
rameters [13], or when the distribution L itself is unknown [24].
There are many other interesting examples of stochastic control systems
in, say, queueing theory, maintenance and quality control, or population

systems such as fisheries and epidemics; see the references at the end. And
one thing we want to emphasize is that the random "noise" process {&,} inmodels such as (2.2) or (2.8) can in fact be "observed", and "measured" inmany cases. This is not an idle remark—even though it seems to contradict
the usual notion of "noise"—, because in adaptive control problems it issometimes necessary to have sample values of the disturbance process inorder to calculate estimates of the unknown parameters. This is illustrated
in the example above: to estimate parameters of the demand distribution—or the distribution itself—we need realizations of the demand process.

3

Optimality Conditions

In this section we consider the control model (X, A, D, q, r) and the problemof maximizing the discounted reward V(6, xz) in (2.3). We give first a result(Theorem 3.1) characterizing the optimal reward function v* in (2.6), andthen we obtain uniform approximations to v*.
|
The assumptions below are supposed to hold throughout the following.
Assumptions 3.1 (@a) For each state z, the set D(xz) of admissible con—trols is a compact subset of A.

(b) There is a constant R such thet |r(x,a)| < R for all (x,a) E K, andr(x, a) is a continuous function of a € D(z) for each z in X.

(c) fy v(y)q(dy|z, a) is a continuous function of a € D(z) for each a € X
and each v € B(X), where B(X) is the space of bounded measurable

functions on X endowed with the supremum norm, ||vull := sup, |v(az)].

The following is a well—known result [4,9,12,27,28].
97

Theorem 3.2 (a) v* is the unique solution in B(X) of the dynamic pro—gramming equation (DPF)
v*(x) = Pa, {r(c a) + a [ v*(y) a(dylz; a)} , a € X.

(3.1)(b) A stationary policy f* E F is optimal iff f*(x) maximizes the rightside of (3.1) for all zx € X, that is,v*(a) =r(e, f*(a)) + A | v*(y) a(dule, £*(c))

for all z e X.

(3.2)

Remark 3.3 The proof of Theorem 3.2 uses the fact that the right sideof the DPE (3.1) defines a contraction operator T on B(X) as follows: Foreach v in B(X),

Tv(x) := Pa {re. a) + 8 | v(y) a(dyle; a)}for all zx Ee X.

(3.3)(That T is a contraction operator with contraction ratio 3, i.e., ||[Tu—TvI| <Bl|u — v|| for all u and v in B(X) follows easily from (3.7) below.) The
proof of Theorem 3.2 also uses the following Measurable Selection Theorem[9,12,27,37]; Let X and A be Borel spaces, let D be a set—valued function
from X to A such that D(xz) is a compact subset of A for each z in X
and such that K := {(z,a)|z € X and a € D(z)} is a Borel subset of
X A; finally, let u: K — R be a measurable function such that u(z, a) is
continuous (or upper semi—continuous) in a E D(z) for each z in X. Then
there exists a measurable function f: X — A such that f(x) € D(z) for allz E X andu (z, f(x)) = max ule, a)
for all z € X.
Moreover, the function v defined by v(#) := max,en(;) u(x, a) is measurable.
3.1

Value—iteration

Thus by the Fixed Point Theorem for Contraction Operators, Theorem 3.2(a)can also be stated as: v* is the unique fixed point of T,.that is to say, v*
is the unique function in B(X) satisfying the equation Tv = v. And in
addition, we can obtain v* as the limit of the iterates of T:||va — v*]| < B" ||vo — v*] — 0

as n — 00,(3.4)

where the so—called value—iteration functions v,, are defined by v, := Tv,—1 =T"v, for n = 1,2, ... and any initial function v, in B(X). Indeed, writingvi(x) = Pa {r(c, a) + 8 | vi—1(v) q(dy|z, a)} ,98

z E X,(3.5)

and comparing with (3.1), we obtainla®)—v@1 < mas #]/ bri(®) —»‘) aldvles a)<

Bllva—1 — v*||

(3.6)

for all n > 1 and z in X. This implies |[v, — v*] < Aliv.—1 — v*I| and (8.4)
follows.
Remark 3.4 To obtain the first inequality in (3.6) we used the following
fact. If u and v are real—valued bounded functions on an arbitrary space Z,
then| sup u(z) — sup (z)] < sup |u(z) — v(2)].

(3.7)

For a proof, see e.g. Hinderer [28], p.17.

3.2

Asymptotic discount optimality

So we now know how to approximate v*, and motivated by the definition ofv, and part (b) of Theorem 3.1 we ask ourselves if we can "approximate"an optimal stationary policy by the maximizers of (3.5). An affirmative
answer can be provided in the sense of asymptotic discount optimality(Definition 2.1) as follows.
Theorem 3.5 For each n > 0, let f, EF be a decision function such thatfa(x) mazimizes the right side of (83.5) for all z in X, i.e.,va(c) =r (c, fa(c)) + B J ¥a—1(4) a(dy|z, f.(2)) for all z EX and n > 1;
take fo E F arbitrary. Then the (Markov) policy 6 = {f,,} which chooses
action f.(x,) at time n (n = 0,1,...) is ADO.
Before proving this theorem it is convenient to characterize asymptotic

discount optimality in terms of the function ¢ : K — R defined by

6(z,a):=r(a,a) +B [ v‘lu)a(dylz.a)—v(c)(€.0) EK. (38)

Notice that ¢ < 0; this follows from the DPE (3.1) which can be rewritten
as:
JPoX, ¢(z,a) = 0, z e X.
Similarly, part (b) in Theorem 3.2 can be stated in terms of $: A stationary
policy f E F is optimal iff¢(z, f(x)) =0

for all z € X.
99

Other obvious properties of ¢ are that (under Assumption 3.1) ¢ is abounded measurablefunction, and ¢(z,a) is continuous in a E D(z#) forall z € X.
Now, to relate ¢ to the concept of asymptotic discount optimality, let
us first note that¢(z;, a;) = E? {r(i, a) + Bv*(@H1) — v*(z;) | h, a;}for any policy 6 and t > 0. Next, multiply by B‘~", take expectation ES,
and sum over t > », to obtain$6" E5¢(2,, a,) = V.(6, 8) — E$v*(x,).
t=nComparing this equation with (2.7) we see that 6 is ADO iff
Y B‘"Ei¢(z;, a;) — 0

as n —>» 00,

t=nwhich is clearly equivalent toE@p(z;, a,) — 0

as t — 00.

Finally, since ¢ is bounded, we can use the Dominated Convergence Theo—rem to conclude the following.
Lemma 3.6 6 is ADO iff p(xz;,a;) — 0 in probability—P?} for all zx € X.

We now go back to Theorem 3.5. To prove it, it suffices to show thatsup |¢(xz, f{(#))]| —0

se X

as n — 00;(3.9)

the desired result is then concluded by Lemma 3.6. To prove (3.9), we use(3.8) and the definition of f,, to obtain
AC AC)

AC AC) — v. (c) + v,(@)—B | Iva1(w) — v*(v)) aldule, fale) + vale) — v*(2),so that, by (3.4),

10 (¢, fale))] <_ Bllva—a — v*Il + Ilva — v*]<

2B" || vo —— v*ll.

This implies (3.9), and therefore, Theorem 3.5.
The results in this section play an important role in all that follows. In
fact, the basic idea to obtain approximations to v* and adaptive policies
for the parametric control model (X, A4,D,q(0),r(0)) is to take suitableversions of the functions v, in (3.5), together with the decision functions£, in Theorem 3.5. Since the result (3.4) on the approximation of v* by v,
is called the value—iteration (or successive approximations) method, we callthe new version the Nonstationary Value—Iteration (NV1) approach and it
was originally inspired by the results of Federgruen and Schweitzer [10] forfinite state and control spaces. We explain these ideas in the next section
and they are applied to adaptive control problems in Sections 5 and 6.
100

4

Nonstationary Value—Iteration (NVI)

Let (X, A4,D,q;,r;), where t = 0,1,..., be a sequence of control models
each of which satisfies Assumption 3.1, and such that they "converge" tothe control model (X, A, D, q, r) in the following sense:

Assumption 4.1 p(t) — 0 and t(t) — 0 as t — oo, wherep(t) := sup |r;(k) — r(k)]keK

r(t) := sup |Ig.(—|k) — 4(+|k)]| .
keKRecall that K is the set defined by (2.1), whereas in the definition ofx(t), || || denotes the total variation norm for finite signed measures.
Remark 4.2 Assumption 4.1 is equivalent to: as t — 00,
p(t) := sup p(n) — 0
not

and

T(t) := sup r(n) — 0.
not

Note also that both sequences p(t) and T(t) are non—increasing.
Now, for each control model (X, A, D, q;, r;) we define the dynamic pro—gramming operator T, on B(X) as (cf., (3.3)):

To(a):= mas {rik.a) + 6 [ vu) aldvle. a)},v €B(X), z ex

(4.1)
T, is a contraction operator with contraction ratio A for all t > 0. We now
use 7, to define two sequences of functions and corresponding policies.

4.1

NVI schemes

NVI—1. For each t > 0, let vf 6 B(X) be the unique fixed point of T}, i.e.,vi(c) = Tvfi (c)for all z € X,

(4.2)

and let 6* = {f*} be a sequence of decision functions f/ E F such thatf(x) maximizes the right side of (4.2) for all z € X; that is,vile) =r (e. file)) + 6 | of(v) ac (aule, fre)
for all z € X and t > 0.

NVI—2. Define a sequence of functions vf € B(X) recursively:
vi(z) := Tiwvi_i(x)for all z € X and t= 0,1,...,
101

(4.3)

where v‘; = 0, and let 6‘ = {f/} be a sequence of decision functions suchthat f/(x) maximizes the right side of (4.3) for all z € X, that is,vile) = ri (e, file)) + A | vi_.(v) a(dule, File))
for all z E X and t > 0.

The existence of the decision functions (or selectors) f;# and f? above isinsured by the Measurable Selection Theorem in Remark 3.3.
In the following approximation theorem we use the constants

co := R/(1 — 8),c; := (1+ Beo)/(1 — £),c2:= C1 +2¢Co,(4.4)

where R is the constant in Assumption 3.1(b). Observe that c, is an upperbound for the optimal reward function v* in (2.6), that is, |[v*l| < co, andit also bounds vf and vf for all t, sinceletll < R+ Alleill

andtwlll <REXA <c
i=0

Theorem 4.3 For all t= 0,1,...,(a) ||v?f —v*I\ < aa — max {p(t), r(t)} .

(b) |Iv; — v*I| < ca max { a([t/2]), #((¢/2]), 94/2 },where [c] denotes the largest integer < c. Moreover, if the sequences p(t)and x(t) in Assumption 4.1 are non—increasing, then in the right side of (b)we can substitute p and t for p and #, respectively.
In other words, the NVI schemes (4.2) and (4.3) can be used to obtain
uniform approximations to the optimal reward function v* of the limiting
control model (X, A, D,q,r), so that Theorem 4.3 is the NVI—analogue of(3.4). The corresponding analogue of Theorem 3.5 is the following.
Theorem 4.4 Both policies 6* and 6‘ are ADO (Markov) policies for thecontrol model (X, A, D, q,r).
Proof of Theorem 4.3. (a) From (4.2), the DPE (3.1) and inequality(3.7), we obtain that, for all z € X and t > 0,|vi(c) — v*(z)| <max n(a. a) — r(x, a) + B fr q:(dy|x, a) — 8 |v*Cv) q(dy|x, a)).

aeED(zx)

Inside the absolute value on the right side, add and subtract the term

B J vil(y) g(dy|z, a),102and then using the triangle inequality and the definitions of p(t) and t(t),we see thatlv? (c) — v*(c)| < p(t) + Allvflliz(t) + Allu? — v*ll,
where we have used inequality (1.1). Finally, since ||vf|| < co, taking supover all z € X, we get(1 — 8)llv? — v*Il < p(t) + Beor(t)< (1+ Beo) max {p(t), r(t)} ,which completes the proof of (a).
The proof of part (b) is the same as the proof of Theorem 3.1(a) in [10];see also Theorem 1 in [16].
Proof of Theorem 4.4. The argument is the same as in (3.9); namely, if
6 = {g;} denotes any of the two policies 6* or 8‘, it suffices to show thatsup |P(x,gi(x))| — 0«€

as t — 00,(4.5)

and then we apply Lemma 3.6. For instance, if g; = f#, then from (4.2)
and the definition (3.8) of ¢, we obtain (writing a = f#(x) to simplify thenotation)b[(z,a) = ¢(s,a)—vt(zc)+v{(z)r(x, a) + 8 [ v*(y) a(dylz; a) m AOE—ri(z,a)— 8 | f(y) acldyle, a) + vi(2)and a straightforward calculation yields|d(z, a)] < o() + Allv*]x(t) + 2llvt — *I + llof —v*If.
The latter inequality, together with Theorem 4.3(a) and Assumption 4.1,
implies (4.5) when g; = f#.
When 6 = 6‘, that is, g; = f{, a similar argument yields|\¢(c, a)| < p(t) + 8lly*\|z(¢) + 8llvi_1 — v*Il + llve — v*
with a = f{/(x#).
Remark 4.5 (a) The NVI functions vf and vf in (4.2) and (4.3) are, ofcourse, interrelated, since they are defined in terms of the same operators
T;. They are also related to the value—iteration functions v; := Tv,; in(3.5); for instance, from (3.4) and Theorem 4.3 we see that, as t — 00,
both|v? — vill — 0,

and
103

||vfi — vel|l — 0.

But it is also important to notice the difference between the two NVI
schemes. Namely, to obtain the policy 6* in NVI—1, at each stage t wehave to solve equation (4.2), which in general is not a trivial matter. In
contrast, the policy 6‘ in NVI—2 has the advantage that the functions vf in(4.3) are defined recursively, and therefore, this second approach seems to
be of more direct applicability.
(b) It is possible to obtain other NVI—like policies by suitable modifica—
tions of NVI—1 and NVI—2. For instance, Gordienko [14] (see also [24,25])
considers any sequence of functions w, in B(X) such that |[w, — vf — 0,
so that, by Theorem 4.3(a),|| w, —v*] —0

as t — 00.

(4.6)

Next, one defines a policy 6g = {f;} as a sequence of measurable functions
from X to A such that, for all z in X,n (e fi@)) + 6 | wily) a(dle, he)) > Twa) — c
where {e;} is a sequence of positive numbers converging to zero; in otherwords, f,(x) is an e,—maximizer of T;w,(z). And again, as in the proof of

Theorem 4.2, one can use (4.5) and (4.6) to show that 6g is ADO. The

reader is referred to [24,25] for details.

Remark 4.6 The NVI scheme (4.3) can be modified to obtain finite—state
approximations for (denumerable) state control models [6], [17], including
adaptive control problems [7], [8].
There is another useful application of the NVI results: The approxi—
mating control models (X, A, D,q;, r;) can be interpreted as describing thetransient behavior of the limiting control model (X, A, D, q, r). For further
discussion on this interpretation and the extension to CMP‘s with averagereward criterion, see [10,18,34].

5

Adaptive Control Models

A control model (CM), say (X, A, D, q(0), r(0)), depending on an unknown
parameter 0 is called an adaptive CM. (Some authors, e.g. Hinderer [28], in—clude in this category the class of CM‘s with incomplete state information.)
In such a case, the controller or decision—maker has to estimate the unknown
parameter 0 while seeking the optimal policy. Thus at each decision epoch,he/she has to estimate the parameter and "adapt" the control actions to
the estimated value. Policies combining these two functions—parameter
estimation and the control action itself—are called adaptive policies.
Our main objective in this section is to use the NVI schemes in Section 4
to derive adaptive policies. We begin by re—writing some of the results in
104

Section 3 in terms of the 0—CM (X, A, D,q(0), r(0)). For each (fixed) valueof 8, everything remains the same, except for changes in notation:q( — |k), r(k), V(6,z), v*(x), E2, etc.,
are changed respectively, intoq(—|k, 0), r(k, 0), V(6,z,0), v*(x, 0), E$, etc.
We then translate the NVI schemes and results into appropriate parameter—
adaptive versions.
5.1

Preliminaries

Let 0 be a Borel space, and for each 0 E O, let (X, A, D,q(0),r(0)) be a
. CM satisfying the 0—analogue of Assumption 3.1:

Assumption 5.1(a) Same as Assumption 3.1(a).

(b) r(z,a, 0) is a bounded measurable function on KO such that |r(z, a, 0)|< R for all (z, a,0) in KO, and r(x, a 6 is continuous in a E D(z)for all zx E X and 0 c O.
(c) ‘fx v(y,0)4(dy|z,a,0) is a continuous function of a E D(z) for eachxz E X, 0 € O, and v e B(XO).
Under these assumptions all the results in Section 3 hold foreach 0 in —O. For instance, introducing
V (6,z,0) := EBS Y A‘r(zi;, a;, 0),i=0v*(xz,0) := sup V(6, 2,0),6etc., we can re—state Theorem 3.2 and Lemma 3.6 combined as follows:

Theorem 5.2(@) For each 0 E O, v*(+,0) is the unique solution in

B(X) of the DPEv*(x,0) = Pa {r(c. a, 0) + 8 | v(v,0) q(dy|z, a, 6} ,or equivalently,z € X,(5.1)

JPaX, p(x, a,0) = 0,

where¢(x, a, 0) *= r(c, a, 0)+8 fvvv.9 q(dy|zx, a, 0)—v*(x,0), (x, a) E K.

105

(b) A stationary policy f*(:,0) EF is (0—)optimal iff¢(z, f*(x,0),0) = 0

for all zx € X.

(c) A policy 6 is 0—ADO iff, as t — 00,¢(x;, a;, 0) — 0

in P$ —probability for all z E X ,where (cf. Definition 2.1) 0—ADO means that, as n — 00,

V.(6, 2,0) — ESv*(z,,0)|\ —0

for all z € X.

Sometimes we write v*(z,0) as vj(x).
Remark 5.3 Since X, A, and O are assumed to be Borel spaces, theirproduct is again a Borel space [9,28]. Thus the joint measurability of thefunctions v*(z, 0), f(x, 0) and so on, in both variables z and 0 follows from
the Measurable Selection Theorem in Remark 3.3. This also applies toother functions and policies introduced below.

5.2

NVI approach

If 0 E6 O is the true (but unknown) parameter value we can approximate vj
and obtain A—ADO policies using the NVI schemes in Section 4. The idea
is simply to consider approximating CM‘s (X, A, D, q;, r;) withri(k) := r(k,0;)anda( — |k) := g( |k, G),

k C K,(5.2)

where {0;} is any sequence in O converging to 0. Thus Assumption 4.1 isnow translated into the obvious form:
Assumption 5.4 For any 0 and any sequence {0,} in O such that 0; — 0,
we have that p(t,0) — O0 and t(t,0) — 0, wherep(t, 0) — Sup [r( k, 0;) ~ r(k, 0)

keK

and

T(t, 0) := sup lle( — 1, 4) — a( +14. 0)]1 .
€This assumption is a condition of continuity in the parameter 0, uni—
formly in k = (z,a) E K, and one would expect that it implies continuityof v*(xz,0) in 0. This is indeed the case and the continuity is uniform on
X. That is, for any 0 and 0; as in Assumption 5.4,

I|v*( —, 4) — v*( :, 0)I| < a « max {p(t, 0), 1(t,0)} ,
106

(5.3)

where c; is the constant in (4.4). Observe that this continuity result isexactly the same as Theorem 4.3(a) under the "translation" (5.2) and so it
illustrates how one goes from the NVI results in Section 4 to the parametricCM‘s in the present section.
To complete the exposition let us define, for each 0 in O, the (dynamic
programming, contraction) operator 7, on B(X):
Tov(z) := $M {r(c, a, 0) + 8 | vu) q(dy|x, a, 0} .

(5.4)

The fixed point vfj( —) = v*( — , 0) of Ty is the optimal reward function of the
0—CM, and the DPE (5.1) can also be written as
v*(z,0) = Tov‘*(z,0)

for all z c X.

|

(5.5)

Finally, given a sequence {0,;} in O, we define the operators 7, := 7p, on
B(X). Under the translation (5.2), these operators T}, are the same as thosedefined by (4.1). Thus the parametric version of the NVI schemes becomes:
NVI—1. For each t = 0, 1,..., let vft( —) = v*(—,0,) € B(X) be the uniquefunction satisfying the equationv*(xz,0;) = T;w*(z,0,;)for all z E X,

(5.6)

and let 6§ = {f#*} be a sequence of maximizers f#( —) = f*(—,0,) E F of

(5.6).

NVI—2. Let vi(—) = vf(:, 9) c B(X) be the functions defined recursively by
vi := Tiwvi_;; that is,vilz, 0) = Tivi_i(z, 91)

for all z € X and t = 0,1,...,(5.7)

where v‘, = 0, and let 8, = {f/} be a sequence of maximizers f/( —) =fi(:,0,) in F of the right side of (5.7). (Notice that both vf and f/ dependon all the values 0), ... ,0;, and not only on 0,; however, we shall keep theshorter notation vi(z,0,;) and f{/(z, 0;) introduced above.)
Then as a consequence of Theorems 4.3 and 4.4 we obtain:
Corollary 5.5 If 0; — 0, then both sequences v*(xz,0,) and vi(z,0,;) con—verge to v*(x,0) uniformly in xz; the inequalities in Theorem 4.3(a) and (b)also hold in the present case (see, e.g., (5.8)) with p(t) and t(t) replaced byp(t, 0) and t(t, 0), respectively. Moreover, the policies 6§ and 6) are 0— ADO.
The latter part of the corollary is proved exactly as (4.5), to obtainsup |¢ (c, £*(x, 6,), 0)| — 0
and similarly,(5.8)

sup |¢ (x, fi(x, 0), 0)| — 0.

On the other hand, Gordienko‘s policy dg in Remark 4.5(b) can also be
extended to the adaptive case [24,25].

107

5.3

Adaptive policies

We have now all the ingredients to define adaptive policies, except for one
thing: we have not said yet how to estimate the unknown parameters. Well,
it turns out that it does not matter how one gets the estimates (using, e.g.,
maximum likelihood, minimum contrast, the method of moments, etc.),
provided that they are sufficiently "good" in the sense of the following
definition.
Definition 5.6 Let {0;} be a sequence of measurable functions 0,; H, — O,

where H, is the space of histories up to time t (Section 2). It is sard that{d,} is a sequence of strongly consistent (SC) estimators of 0 E O if, ast — 00, 0, = O;(h;) converges to 0 PS" —almost surely (a.s.) for any z E X
and 6 E A.
a
Examples of SC estimators for controlled Markov (or semi—Markov) pro—
cesses are given in [8,13,21,30,32,33,38]. It can also be seen in some of thesereferences (e.g. [30,38]) that "strong consistency" in the sense of "almost
sure" convergence as in Definition 5.6 can be replaced by other types of
convergence, e.g., in probability or in mean square, in which case the opti—
mality results are changed accordingly.
We will now use the NVI policies 65 = {f*(:,0,;)} and 6) = {f{(+,0;)}
introduced above and a sequence {0,} of estimators to define adaptive poli—cies. We also use the abbreviation PEC for "Principle of Estimation andControl"
Definition 5.7(@) The policy 6* = {6¢} defined by

6; (h;) a — f* (xe, A(M))

for all h; E H; and t —> 0,

is called a PEC—adaptive policy.
(b) The policy 6‘ = {8{} defined by

6i(h) := fi (ci, 8(M))

for all h, € H, and t> 0,

is called an NVI—adaptive policy.
The PEC adaptive policy is also found in the literature on stochastic
adaptive control under various names: "self—optimizing controls", "naive
feedback controller", and "certainty—equivalence controller", among others.
Mand] [33] called it the "method of substituting the estimates into optimal
stationary controls", which describes the underlying idea: first, we deter—mine an optimal stationary policy £*(:,0) E F for each admissible valueof 0 (cf. Theorem 5.2(b)); next, if at time t the computed estimate of theunknown parameter is 0,, we then apply the control action f*(x;, 6;), so we
simply replace the unknown parameter value by its estimate.
108

_ Suppose now that we want to prove that (e.g.) the PEC policy 6* is
0—ADO. Then by Theorem 5.2(c) it suffices to verify that, as t — 00,|6 (21 f*(z;, 0), 0)| — 0

PS—a.s. for all z € X,

(5.9)

where we have written 0, for 0,(h,). But on the other hand, we alreadyknow that (5.8) holds of any sequence 0; converging to 0, which implies(5.9) if {d,} is a sequence of SC estimators of 0. A similar argument applies
to verify the O—asymptotic optimality of the NVI policy 6‘, and therefore,
we conclude:
Corollary 5.8 If {d,} is a sequence of SC estimators of 0, then each of
the adaptive policies 6* and 6‘ in Definition 5.7 is 0—ADO.
We have thus shown how to derive ADO adaptive policies using the

NVI schemes introduced in Section 4. Variants of this approach can beused to study also adaptive control problems for semi—Markov processes[15] and systems with partial state information [23] with discounted andaverage reward criterion [1,18,34]. As another application, we consider inthe following section the case of control systems of the form (2.2) withunknown disturbance distribution.

6

Nonparametric Adaptive Control

We shall study now a controlled Markov process whose evolution is de—scribed by the system equation
Zi41 = F(xi,a;, &i),t= 0,1,...; zo given,(6.1)

where the disturbance process {&,} is a sequence of i.i.d. random elementswith values in a Borel space S, and common distribution 0. We assume
that {&,} and the initial state z, are independent, and that 0 is an elementof O, a measurable subset of the set P(S) of probability measures on S.
Since S is a Borel space, P(S) is also a Borel space [9]; © represents theset of "admissible" disturbance distributions.
In this section, we first reduce the process above to a "parametric"model (X, A, D,q(0),r(0)) and show that the setting in Section 5 is not
the appropriate one (unless 0 is a discrete distribution); we then describe
how things should be changed in order to obtain asymptotically discount
optimal (ADO) adaptive policies.

6.1

Reduction to the parametric case

Let X, A and D be as in Section 2, and assume the disturbance distribution

0 is given. Then the transition law q( < |x, a, 0) is determined by the function
F in (6.1):
q(B|zx, a,0) = [» [F(z, a, s)] 0(ds)
109

(6.2)

for all B in B(X) and k = (z,a) in K. The one—step expected reward isgiven byr(x, a, 0) := frc a, s) 0(ds),for all (z,a) E K,

(6.3)

where F is a bounded measurable function on KS; that is, r(z,a,0) is
the expected value of r(x;, a;, £,) given that z; = z, a; = a and 0 is the
distribution of the &;. (This means that we allow r to depend on the"disturbances", as in the inventory/production example in Section 2.)
We have thus an adaptive CM (X, A, D, q(0), r(0)) as in Section 5, andsuppose that conditions on F(z,a,s) and r(z,a,s) are imposed so that
Assumption 5.1 holds. In such a case, the results in Corollaries 5.5 and 5.8
also hold if Assumption5.4 is satisfied. To obtain the latter, we see that,from (6.3) and inequality (1.1),|70k ») {6i(ds) — Ads)}
IA

In(k, 6) — r(k0)1

R\|O; ~ 0|1,

where R is a upper bound of |[rl], and |[0; — 0|| is the variation norm of thefinite signed measure 0, — 0. Thus|p(t, 0) < RI\Q; — 0]|

and the first part of Assumption 5.4 holds if|G; — 0|| — 0.

(6.4)

Similarly, from (6.2) it can be obtained that1(t,0) < 119. — 01]
Thus Assumption 5.4 holds if the probability distributions 0, are "esti—mates" of 0 which satisfy (6.4).
And this is precisely the difficulty with the "non—parametric‘" case: (6.4)
is a very strong requirement. Namely, except for special cases (e.g., when 0
is discrete), non—parametric estimation methods give "consistent" estimates

but in forms weaker than in variation norm (6.4).
thus to give a more complete solution to the non—parametric adaptive
control problem we will use a slightly different approach, following Gordi—
enko [14]; see also [24,25].

6.2

New setting

Let di, dg and d3 denote respectively the metrics on X, A, and S, and let dbe the metric on K defined by := max{d;, d;}. We suppose the following:
Assumptions 6.1 There esist constants R, Lo, L1 and Ly such that110

(a) |F(k,s)| < R and |F(k, s) — F(k‘, s)] < Lo d(k, k‘) for all k and k‘ in K
and all s € S.

(b) D(z) is a compact subset of A for each state z, and H (D(z), D(x‘)) <Li di(xz,z‘) for all z and x‘ in X where H is the Hausdorff metric.
(e) lal: |k,9) — a( |K‘, 0)\| < L1 d(k, k‘) for k and k‘ in K and all 0 in O.
(d) The function F(k,s) in (6.1) is continuous in k E K, measurable
in s C S, and moreover, the family of functions {F(k, —), k E K} isequicontinuous at each point s in S; that is, for each s in S and e > 0,
there exists 1 > 0 such thatds(s, s‘) < 73 implies di [F(k, s), F(k,s‘)) <e

for all k in K.

Comments on these assumptions are given at the end of this section.
Right now what it needs to be remarked is that they are introduced because,in the new setting, we need the optimal reward function vj(xz) = v*(xz,0)to be continuous in x for each value of 0. Therefore, we consider again the
dynamic programming operator 7; in (5.4), but now we define it on thespace C(X) of bounded continuous functions on X:
Tov(x) := max, {r( a, 0) + a [ vy) q(dy|z, a, 0} ,

aED

(6.5)

where v € C(X) and z € X. We then have the following.
Proposition 6.2 For each 0 € O,.
(a) vj is the unique solution in C(X) of the DPE|v(x) = Tovi(c),z € X.

(b) |vj(z) —vf(x‘)|l < L*di(zx, x‘) for all x and a‘ in X, where
L* := (Lo + BL2co) max{1, L1}
and co is the constant in (4.4), an upper bound for ||v§\|.
(c) The family of functions
V* := {vj [F(k,»:)], k E K}
is uniformly bounded and equicontinuous at each point s in S.
Proof. Part (a) is the same as Theorem 3.2(a), with B(X) replaced byC(X).
To prove (b) we use the following obvious fact, valid under the present
assumptions.
111Lemma 6.3 If J(k) = J(x,a) is a Lipschitz function on K, thenJ(a) := max, J(c, a)
is Lipschitz on X. More precisely, if L is a constant satisfying|J(k) — J(k‘)| < Ld(k, k‘)

for all k and k‘ in K,

thenlj («) — ;j(x‘)] < L3di (#, 2‘),

where L; := L < max{1, 4}.

From this lemma and (6.5) we deduce that Tyv is a Lipschitz function
with constant

Ls = (Lo + Allv|LZ2) » max{1, L1},and then part (b) is concluded from the DPE in (a).

Finally, part (c) follows from (a), (b) and Assumption 6.1(d).

Let us now go back to the problem of estimating the unknown distribu—
tion 0 of the disturbance process.

6.3

The empirical distribution process

Let {0,} be the empirical distribution of the disturbance process {&;}; thatis, for any Borel subset B of S,.
t—10,(B) := t* Y" Ip(6;),

t= 1,2,...,

i=O

and assume 0, € O for all t. For each Borel set B in S, the random variables
Ip(&;) are i.i.d. with mean 0(B), and therefore, by the law of large numbers,
0,(B) — 0(B) a.s. as t — 00.
Moreover, if 0 is discrete, Scheffe‘s Theorem [5] implies that (6.4) holds,
but this is not true for general 0. What we do know [11, p. 211] is that 0,
converges weakly to 0 a.s., that is,

J h dd, —> J hdd

a.s. for all h € C(S).

(6.6)

This, however, is still not good enough for the adaptive control results wewant (Theorem 6.5). Thus let us recall some concepts.

Remark 6.4 Let 0 be a probability measure on a Borel space, say S, and
let G = {h;, : € I} be a family of real—valued measurable functions on S,
where I is an arbitrary set of indices. It is said that G is a O—uniformity
class if for any sequence {0,} of probability measures on S which converges
weakly to 0,
sup161

f naee— [ n ap| — 0

as £ — 00.

Furthermore [5, p. 17], G is a O—uniformity class if G is uniformly boundedand equicontinuous at each s in S.

112

Thus, if instead of G we take the family of functions V* in Proposi—tion 6.2(c), we conclude that, from (6.6) and the previous remark,n(t, 0) — 0 a.s.

as 1 — 00,

(6.7)

where

n(+0) := sup |f v5(0) aldvles a 6) — [ v3(u) a(dvies a, o
= sup |/ v5 [F(E, s)] #:(ds) — / v[F(E, s)] 0(ds)==sup© Su; [FCE&)) — / v3 [FCE»)] 6(ds)i=0Similarly, if in addition to Assumption 6.1(a), the family of functions{r(k,:), k E K} is equicontinuous at each s E S,

(6.8)

then as t —» 00,»(t0) = sup[r(t.5)0(4s)— [ s(k,5)0(ds)] — 0 as.

(6.9)

Conditions (6.7) and (6.9) are what we need for the approximation andoptimality results in the non—parametric case. Namely, the conclusions ofCorollary 5.5 (or Theorems 4.3 and 4.4) also hold in the present case if wechange 1(t, 0) by 7»(t,0) and the constants c; and c; in (4.4) are replaced _respectively byc; := (1+B)/(1—$B)andc}) := c} +2c

Therefore, the result now reads as follows.
Theorem 6.5 Suppose that Assumption 6.1 holds and let v*(—,0,;) andvi(+,0;) be the functions on C(X) defined by (5.6) and (5.7), when Ty

is defined on C(X). Then(a) ||v*(:,0) — v*(:,0)]| < ci — max {p(t, 0), n(¢,0)}—(b) |Ivi( ,d) — v*(, 0) < c), — max {»(/2, 0) , 7 ([1/2], 0) , ge/a}, where|p(t,0) := supp(?,0) and 7(t,0) := supn(t,0).
i>ti>t

If in addition (6.8) holds, then the policies 6§ and 6, are 0—ADO.
Remarks on the assumptions. Assumption 6.1(b) trivially holds if
D(z) = A is compact and independent of z. If D(z) = [0,C — z], asin the inventory/production system in Section 2, thenH(D(z),D(ax‘)) = |z —a‘
113

for all z and z‘ in X.

Assumption 6.1(c) holds, for instance, if for every k € K and 0 E O, theprobability g( — |k, 0) has a density p(z|k,0) with respect to a measure 4 on
X such that|p(z|k, 0) — p(«|k‘, 0)| < L(x) dik, k‘)

for all k and k‘ E K, z 6 X and 0 E O, where L(z) is a pu—integrable
function. This follows from the fact that [36]: if P, and P;, are probability
measures with densities p; and p» with respect to a measure 4, then

IA — Plt = / Ip — pil de.
Finally, Assumption 6.1(d) holds in the additive—noise case, sayF(z, a,s) = b(z, a) + c(z#)sif b and c are continuous functions and c is bounded.
Additional comments on Assumption 6.1 are given in [24] and [25]. inthe latter reference the results in this section are extended to partiallyobservable systems.

7T

Concluding Remarks

We have presented a unified exposition to some recent results on the adap—
tive control of stochastic systems, the unifying theme being the Nonsta—
tionary Value—Iteration (NVI) approach in Section 4. Perhaps the most re—strictive assumption in this presentation is the boundedness of the one—stepreward function r. This can be weakened but at the expense of considerablycomplicating the presentation [2,6,7,38], and of course, the results would
be weaker: in general, the approximations to the optimal reward function
v* would be pointwise, instead of uniform as above.
Another key fact is the contraction property of the dynamic program—ming operator, which results from the discount factor # being less than 1.
If we let B3 be > 1, we can still get a contraction operator on the space
B(X) but with respect to the span pseudo—norm|

sp(v) := sup v(a) — inf v(@), —and provided that an appropriate ergodicity assumption is imposed on thetransition law q( — |x, a); see e.g., [18,20,29].

Other approaches to the adaptive control of Markov processes can beseen in [31,35,39].
Approximation procedures for the adaptive policies in Sections 5 and 6
are presented in [26]; these approximations are related to results in [3] and

[7].

114

References[1] R. Acosta Abreu and O. Hernandez—Lerma, Iterative adaptive control
of denumerable state average—cost Markov systems, Control and Cyber.

14(1985), 313—322.

[2] A. Bensoussan, Stochastic control in discrete time and applications to
the theory of production, Math. Programm. Study 181982), 43—60.

[3] D.P. Bertsekas, convergence of discretization procedures in dynamic
programming, IEEE Trans. Autom. Control 20(1975), 415—419.

[4] D.P. Bertsekas, Dynamic Programming and Stochastic Control, Aca—
demic Press, New York, 1976.

[5] P. Billingsley, Convergence of Probability Measures, Wiley, New York,
1968.

[6] R. Cavazos—Cadena, Finite—state approximations for denumerable state
discounted Markov decision processes, Appl. Math. Optim. 14(1986),
1—26.

[7] R. Cavazos—Cadena, Finite—state approximations and adaptive con—trol of discounted Markov decision processes with unbounded rewards,
Control and Cyber. 16(1987), 31—58.

[8] R. Cavazos—Cadena and O. Hernandez—Lerma, Adaptive policies forpriority assignment in discrete time queues—discounted reward crite—

rion. Submitted for publication.

[9] E.B. Dynkin and A.A. Yushkevich, Controlled Markov Processes,
Springer—Verlag, New York, 1979.

[10] A. Federgruen and P.J. Schweitzer, Nonstationary Markov deci—sion problems with converging parameters, J. Optim. Theory Appl.
34(1981), 207—241.

[11] P. Gaenssler and W. Stute, Empirical processes: a survey for i.i.d.
random variables, Ann. Probab. 7(1979), 193—243.

[12] J.P. Georgin, Controle de chaines de Markov sur des espaces arbi—
traires, Ann. Inst. H. Poincaré, Sect. B., 14(1978), 255—277.

[13] J.P. Georgin, Estimation et controle des chaines de Markov sur desespaces arbitraires, Lecture Notes Math. 636(1978), 71—113.

[14] E.I. Gordienko, Adaptive strategies for certain classes of controlled
Markov processes, Theory Probab. Appl. 29(1985), 504—518.

115

[15] O0. Hernandez—Lerma, Nonstationary value—iteration and adaptive con—trol of discounted semi—Markov processes, J. Math. Anal. Appl.

112(1985), 435—445.

[16] O. Herngndez—Lerma, Approximation and adaptive policies in dis—counted dynamic programming, Bol. Soc. Mat. Mexicana 30(1985),
25—35.
[17] O. Hernandez—Lerma, Finite—state approximations for denumer—
able multi—dimensional state discounted Markov decision processes,

J. Math. Anal. Appl. 113(1986), 382—389.

[18] O. Hernandez—Lerma, Approximation and adaptive control of Markov
processes: average reward criterion, Kybernetika (Prague), 23(1987),
265—288.
[19] O. Hernandez—Lerma and R. Cavazos—Cadena, Continuous dependenceof stochastic control models on the noise distribution, Appl. Math.
Optim. 15(1987), to appear.
[20] O. Hernandez—Lerma and J.B. Lasserre, A forecast horizon and a stop—
ping rule for general Markov decision processes. J. Math. Anal. Appl.

132(1988), to appear.

[21] O. Herngndez—Lerma and S.. Marcus, Optimal adaptive control ofpriority assignment in queueing systems, Syst. Control Lett. 4(1984),
65—72.
[22] O. Hernandez—Lerma and S.I. Marcus, Adaptive control of discounted
Markov decision chains, J. Optim. Theory Appl. 46(1985), 227—235.
[23] O. Herngndez—Lerma and S.I. Marcus, Adaptive control of Markov
processes with incomplete state information and unknown parameters,
J. Optim. Theory Appl. 52(1987), 227—241.
[24] O. Herngndez—Lerma and S.I. Marcus, Adaptive control for discrete—time stochastic control systems with unknown disturbance distribu—
tion, Syst. Control Lett. T(1987), to appear.
[25] O. Hernandez—Lerma and S.I. Marcus, Nonparametric adaptive control
of discrete—time partially observable stochastic systems, J. Math. Anal.
Appl. (1988), to appear.
[26] O. Hernandez—Lerma and S.I. Marcus, Discretization procedures foradaptive Markov control processes, J. Math. Anal. Appl. (1988), toappear.

116

[27] C.J. Himmelberg, T. Parthasarathy and F.S. Van Vleck, Optimal plansfor dynamic programming problems, Math. Oper. Res. 1(1976), 390—394.
[28] K. Hinderer, Foundations of Non—stationary Dynamic Programmingwith Discrete Time Parameter, Lecture Notes in Oper. Res. 33,
Springer—Verlag, New York, 1970.
[29] G. Hibner, On the fixed points of the optimal reward operator instochastic dynamic programming with discount factor greater thanone, Zeit. Angew. Math. Mech. 57(1977), 477—480.
[30] M. Kolonko, Strongly consistent estimation in a controlled Markov
renewal model, J. Appl. Probab. 19(1982), 532—545.
[31] P.R. Kumar, A survey of some results in stochastic adaptive control,
SIAM J. Control Optim. 23(1985), 329—380.
[32] M. Kurano, Discrete—time markovian decision processes with an un—
known parameter—average return criterion, J. Oper. Res. Soc. Japan

15(1972), 67—76.

[33] P. Mandl, Estimation and control in Markov chains, Adv. Appl. Prob.

6(1974), 40—60.

[34] P. Mand] and G. Hubner, Transient phenomena and self—optimizing
control of Markov chains, Acta Universitatis Carolinae—Math. et Phys. >26(1985), 35—51.
[35] U. Rieder, Bayesian dynamic programming, Adv. Appl. Probab.

T(1975), 330—348.

[36] H.L. Royden, Real Analysis, 2nd ed., Macmillan, New York, 1968.
[37] M. Schal, Conditions for optimality in dynamic programming and forthe limit of mn—stage optimal policies to be optimal, Z. Wahrs. verw.

Geb. 32(1975), 179—196.

[38] M. Schal, Estimation and control in discounted stochastic dynamic
programming, Preprint No. 428, Institute for Applied Math., University of Bonn, Bonn, 1981.
[39] K.M. Van Hee, Bayesian control of Markov Chains, Mathematical Cen—tre Tract 95, Mathematisch, Centrum, Amsterdam, 1978.

[40] W. Whitt, Approximation of dynamic programs, I, II, Math. Oper.
Res. 3(1978), 231—243; 4(1979), 179—185.

117

Texas Tech University, Mathematics Series
Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

Scientific Computation on Some
Mathematical Conjectures
Richard S. Varga*
Institute for Computational Mathematics

Kent State University
Kent, Ohio 44242

This talk will survey recent results on four mathematical conjectures:the Bernstein Conjecture in polynomial approximation theory, the Polya
Conjecture (related to Riemann Hypothesis) in function theory, the "1/9"
Conjecture in rational approximation theory, and the Ruscheweyh—Varga
Conjecture in polynomial function theory. The emphasis here will be on theinteraction between high—precision scientific computation and mathematicalanalysis, and their application to unsolved mathematical conjectures.

1

The Bernstein Conjecture

Scientific computations on an old open conjecture of S. Bernstein inapproximation theory, turned out to be both mathematically and compu—
tationally interesting, as well as esthetically pleasing. Like other famous
unsolved conjectures (such as the Goldbach conjecture in number theory),
the Bernstein conjecture is very easy to state.
For notation, given any real continuous function f(x) with domain[—1,+1], letEalf) := inf {IIf — gllzsst—141] : 9 € Ta}(1.1)

denote the error of best uniform approximation of f(x) on [—1, +1] bypolynomials in t,. (Here, t, denotes the set of all real polynomials ofdegree at most n (n = 0,1,...).) For the specific function |x|, a well—known
result of Jackson (cf. Meinardus [1.7, p. 56]) gives that
En (|x|) < 6/n(n = 1, 2,...),

|

(1.2)

and, because |x| is an even function on [—1, +1], it is easily seen (cf. Rivlin[1.9, p. 43]) that||

Ern (|x|) = Pon (|z])(n = 0,1,...).

*Research supported by the Air Force Office of Scientific Research.

119

|

(1.3)

Thus, it is sufficient to consider only the manner in which the sequence{E2 (|z|)}72., decreases to zero. From (1.2), there follows
2nE, (|x|) < 6(n = 1,2,...).

(1.4)

In his fundamental paper [1.2] from 1914, Bernstein significantly im—
proved (1.4). Specifically, he showed that there ezists a constant, which wecall 3 (3 for "Bernstein" ), such thatlim 2nE2,(|z|) = #.

(1.5)

In addition, Bernstein, using crude calculations based on extremely inge—
nious methods, deduced in [1.2] the following rigorous upper and lower
bounds for 3:
0.278 < B < 0.286.
(1.6)
Moreover, Bernstein noted [1.2, p. 56], as a "curious coincidence" that theconstant

1——
0.282 47917 2..
37z = 0.28209

1.7
(1.7)

also satisfies the bounds of (1.6) and is very nearly the average of thesebounds. This observation has, over the years, become known as the.
.
Bernstein Conjecture:

r 1
B= w

(1.8)

In the 70 years since Bernstein‘s work [1.2] appeared in 1914, his con—jecture remained unsolved, though there was considerable interest in thisconjecture (cf., Bell and Shah [1.1], Bojanic and Elkins [1.3], and Salvati[1.10}]). Recently, we showed in 1985 in [1.11] that Bernstein‘s Conjecture isfalse. It is important to add that the proof of this depended on numerically
implementing some extremely ingenious ideas already devised by Bernsteinin 1914!
The high—precision calculations we performed in [1.11] consisted of threebasic parts:(i) Determination of {2nE;, (|z])}?22.,;n=1)(ii) Determination of the upper bounds (Brim)m=
m=0 for A;(iii) Determination of the lower bounds {l,}27., for 3.

The determination in [1.11] of the best approximation errors Ez, (|z|) (cf.,(1.1)) used an essentially standard mathematical implementation of the(second) Remez algorithm (cf. [1.7, p. 105]) on a VAX 11/780, with R.P.
Brent‘s MP package [1.4] to handle the multiple—precision computations.
Taking into account guard digits and the possibility of some small rounding

errors, we believe that the numbers {E, (|x|)};, we determined are accu—
rate to at least 95 decimal digits. A subset of the numbers {2nEs, (|z|)}?2
n=1>)
120

truncated to ten decimal digits, is given in Table 1.1 below to show theslow convergence of these numbers. (For a complete listing of the numbers{2nrnEs.(|z|)}?*, in greater precision, see [1.11].)n

2nEsn(|z|)

1
10
20
30
40
50

0.25000 00000
0.27973 24337
0.28005 97447
0.28012 06787
0.28014 20296
0.28015 19162
Table 1.1

The computation of the upper bounds {24,, }i08, for B is based on thefollowing ingenious observation of Bernstein [1.2]. Define the function F(t)on [0, +00) by
—i "
~* du
t) := t==F(t) := [%= s2 . cosh(a/ad —

1.

(1.9)

Other representations of F(t) include
F(t) =

Qt
2t + 13 1(1 1: +g)3)t1(1.10)

where F(a, b; c; z) denotes the classical hypergeometric function (cf. Henrici[1.6, p. 27]), andro—}{v (f]) —¥(¢e3)} «20 aan

where ¥(z), the psi (digamma) function, is defined from the gamma func—tion ‘(z) byV(z):= I"(2) .

(1.12)

The connection between F(t) of (1.9) and the Bernstein constant 2 of
(1.5) is the following. For each positive integer m, set
Hm :=

.

sie |_ (‘Cinf

and for m = 0, set

C

&p

)
(t 22 cee 0c/ )| Il on..,(1.13)

cos(rt |r t) — (« +Ho := infI| eos(mt)[F(t) — @olllnss{0,400) *121(1.13‘)Note that the poles of the sum in (1.13) are cancelled by zeros of cos(tt).
Because of this, standard arguments show that real constants {@;(m)} fp
exist such thatm =cos(1t) |e — Co + y a — oreopp)

Lso[O0,+00)

1Moreover, it is evident from (1.13) that the numbers {u,, }X—, are nonin—creasing:
Lo 2 H1 2 ~* 2 Hm 2099.
(1.15)
Now, Bernstein [1.2, p. 55] proved that # of (1.5) and the constants u,, of(1.13) are connected throughB = 2 YM Am.

(1.16)

Clearly, we see from (1.15) and (1.16) that240 2 241 2 ~>* > 2unm > B(m = 0,1,...),(1.17)

so that the calculation of the constants 24, provides increasingly sharper
upper bounds for 3. We mention that the upper bound 0.286 for B of
(1.16), determined by Bernstein in 1914, corresponds to an approximationof the upper bound of 243.
What is mathematically and computationally interesting is that thesolution of the approximation problem in (1.13) has an oscillation character
which permits (cf. [1.11]) the use of a modified form of the (second) Remezalgorithm. We mention that Bernstein‘s work [1.2] of 1914 predates the1934 appearance of Remez‘s algorithm [1.8].

In Table 1.2 below, we give a subset of the numbers {24,,.}}02,, eachtruncated to 10 decimal digits. (For details on the application of this mod—ified Remez algorithm, and on the accuracies in the associated calculations,
we refer to [1.11].

m
5
20
40
60
80
100

2m
0.28177 99926
0.28026 79181
0.28019 38951
0.28018 03067
0.28017 55680
0.28017 33791
Table 1.2

We remark that already from the case m = 5 of Table 1.2, we have (cf.

(1.7)),——— > 2u5 = 0.28177 <<>> A,
2/1
122

so that the Bernstein Conjecture (1.8) is necessarily false.
The final third part of the calculations for the Bernstein Conjecture from
[1.11] involved the calculation of lower bounds I,, for 3. This, as Bernstein[1.2] also showed, is related to a complicated nonlinear optimization involv—

ing the function F(t) of (1.9). This was by far the most time—consuming of

all calculations performed in [1.11]; for details of this and for a discussionof the accuracy of these calculations, we refer the reader to [1.11]. Theselower bounds {I,, }X., can be shown to satisfy
4 < l4 § <<< l,, < B, with lim lL, = 3,

(1.18)

so that the calculation of the constants I,, provides increasingly sharper
lower bounds for 3. We mention that the lower bound 0.278 for 3 of (1.6),
determined by Bernstein in 1914, corresponds to an approximation of thelower bound l;. Table 1.3 below gives a subset of the numbers {L, }20~;,
each truncated to 10 decimal digits.
m

Im

1
5
10
15
20

0.27198 23590
0.28009 77913
0.28016 13794
0.28016 71898
0.28016 85460
Table 1.3

From (1.17) and (1.18), we have thatlzo < B < 21100.

(1.19)

Thus, from the appropriate entries of Tables 1.2 and 1.3, this implies that
0.280168 < J < 0.280174.

(1.20)

Hence, these upper and lower bound calculations give us thatB = 0.280171 + 6,

where |6]| < 3 x 10~S.

(1.21)

It turned out that the use of Richardson extrapolation (cf. Brezinski[1.5, p. 7] with z, = 1/n"*), applied to the high precision calculationsof {2nE2.(|z|)}]2,, produced unexpectedly beautiful results! This use of
Richardson extrapolation in [1.11] suggests thatB = 0.28016 94990 23869 13303 64364 91230 67200 00424 $2139 81236...
(1.22)

to 50 decimal places. And, to leave intact the number of unsolved con—jectures in this area, it is conjectured in [1.11] that 2nE;, (|x|) admits thefollowing asymptotic expansion:

K;

K,

K

InEm (Iel) = A— —7 + 4 — 4 +(n — 00),(1.23)

where the constants K, (independent of n) are all positive. (For numericalestimates of {K;}}°,,, see also [1.11].) |Finally, because the Bernstein constant 3 is intimately associated withthe function F(t) of (1.10), it is not implausible that 3, as well as theconstants K, in (1.23), may admit a closed—form expression in terms ofclassical hypergeometric functions and/or known mathematical constants!
References[1.1]

R.A. Bell and S.M. Shah, Oscillating polynomials and approxima—
tions to |z|, Publ. of the Ramanujan Inst. 1(1969), 167—177.

[1.2]

S. Bernstein, Sur la meillure approximation de |x| par des polynomesde degrés donnés, Acta Math. 37(1914), 1—57.

[1.3]

R. Bojanic and J.M. Elkins, Bernstein‘s constant and best approx—
imation on [0, +00), Publ. de l‘Inst. Math. (Nouvelle série) 18(32)(1975), 19—30.

[1.4]

R.P. Brent, A FORTRAN multiple—precision arithmetic package, As—
soc. Comput. Mach. Trans. Math. Software 4(1978), 57—70.

[1.5]_C. Brezinski, Algorithmes d‘Accélération de la Convergence, Paris:
Editions Technip, 1978.

[1.6]

P. Henrici, Applied and computational Complezs Analysis, vol.1, New
York: John Wiley and Sons, 1974.

[1.7]

G. Meinardus, Approzimation of Functions: Theory and Numerical
Methods, New York: Springer—Verlag, 1967.

[1.8]

E.Ya. Remez, Sur le calcul effectiv des polynomes d‘approximationde Tchebichef, C.R. Acad. Sci. Paris 199(1934), 337—340.

[1.9]

T.J. Rivlin, An Introduction to the Approzimation of Functions,
Waltham, Mass.: Blaisdell Publishing Co., 1969.

[1.10] D.A. Salvati, Numerical Computation of Polynomials of Best Uni—
form Approzimation to the Function |x|, Master‘s Thesis, Ohio State
University, Columbus, Ohio, 1980, 39pp.

124

[1.11] R.S. Varga and A.J. Carpenter, On the Bernstein Conjecture in ap—
proximation theory, Constr. Approx. 1(1975), 33—348. (This has also
appeared as a Russian translation in Math. Sbornik 129(1986), 535—
548.)

2

The Polya ConjectureThis section is devoted to an old conjecture from 1927 of G. Polya(related to the famous Riemann Hypothesis). To begin, let Riemann‘s &—function (cf. Titchmarsh [2.9, p. 16]) be defined by«in=}(e— Deine) o().

Cnwhere ( denotes the Riemann (—function. It is known that & is an entire
function of order one which admits (cf. Polya [2.8, p. 11]) the integral
representation

1

3° (3) = [
where

co

$(t) cos(zt) dt,

(2.2)

bo —

®(t) := Y "(2r‘n‘e"* — 31n"‘e") exp(—tn"‘e*"*).

(2.3)

n=l

Now, expanding cos(zt) and integrating termwise in (2.2) show that £ canbe written in Taylor series form as

1.

(z» (—1)" 5,22" |s* (3) = 2
where

|

5o

bm. := [ t"®®(t)dt

(2m)!

_

(2.4)

(m= 0,1,...).

— (25)oOn setting z =—z" in (2.4), the function F(z) is then defined by

FO) = Y coy

(2.6)

m=0

so that F is an entire function of order 1/2 which is real for real z. From
(2.4) and (2.6), it follows thatat (§) =F")—

(en

Concerning the Riemann (—function, it is known that {—2m}®_, are thereal zeros of (, and the Riemann Hypothesis asserts that all remaining zerosof the function ((z) lie on the line Re z = 1/2. It is known (cf. Titchmarsh[2.9]) that all the nonreal zeros of ((x) lie in the strip 0 < Re z < 1, andthat infinitely many zeros lie on Re z = 1/2. To add to this, the Riemann125Hypothesis has been attacked numerically over the years, and it is now
known (cf. van de Lune et al. [2.10}]) that the first 1,500,000,001 nonreal

zeros of ((x) closest to the real axis do lie exactly on Rez = 1/2!
In a different direction, as a consequence of (2.1) and (2.7), one obtains

the well—known result (cf., [2.4, p. 16]) that the Riemann Hypothesis isequivalent to the statement that all zeros of F(z) of (2.6) are real andnegative. Now, it is known (cf. Boas [2.1, p. 24]) that a necessary condition
that F(z) satisfy the weaker hypothesis that all its zeros be real is that its
Taylor coefficients satisfybirm (Bes)

*

b

bm 1

_> (m + ‘c,.~ (2m T ay

(m = 1,2,.. ),(2.8)

or equivalently that

.

Im

—1N\s

o

Dn := (bay — Ca () bn—i6m41>0(m= 1,2...)(29)

In 1927, Polya [2.8], while studying some fragmentary unpublished notesof J.L.W.V. Jensen dealing with the Riemann Hypothesis, raised the ques—tion of directly establishing the inequalities (2.9), without proving the Rie—mann Hypothesis. The interest in the inequalities in (2.9) is very natural:
the truth of the Riemann Hypothesis obviously implies that all the in—equalities of (2.9) are. valid, so that if one of the inequalities of (2.9) were
to fail for some m > 1, then the Riemann Hypothesis would necessarily befalse! For historical reasons, we call the inequalities of (2.8) and (2. 9) the
Polya— Turdn inequalities.
|
The history concerning Polya‘s problem of 1927 is interesting. For
nearly 40 years, this problemwas apparently untouched in the literature.
Then in 1966, Grosswald [2.4,2.5] generalized a formula of Hayman [2.6] on
admissable functions, and, as an application of this generalization, Gross—wald proved thatD., = tok {1 +0 (cz)}log m(m —» 00).

(2.10)As the moments {b,,}%—, are well—known to be all positive (cf Thm. A
of [2.3]), then Grosswald‘s result (2.10) proves that (2.9) is valid for all m
sufficiently large, say m > mo, but the exact value of my was not determinedin Grosswald‘s analysis. To our knowledge, this gap in Grosswald‘s solutionof Polya‘s problem was not filled subsequently in the literature.
Intrigued by Polya‘s problem, in part because of its interesting numer—
ical overtones in the determination of the moments {b,, }2_,, we embarked
on a dual program of high—precision computations of the moments {bm £reo
and the numbers {D,, }}02; , as well as an attempt of a mathematically rig—orous analysis of the Polya problem. Our mathematical result (cf. Csordas,
Norfolk, and Varga [2.3]) is that the Polya Conjecture is true:
126

Theorem 2.1 The Polya—Turdn inequalities (2.9) are valid for all m =
1,2, ....
Our proof of this Theorem, using a technique which is different from
Grosswald‘s approach, has two main steps which we now sketch. Setting

K(t) := [ 8(Va)du(t> 0),(2.11)

where ® is defined in (2.3), our first main step was to establish that log K(?)
is strictly concave on (0, +00). Next, on setting
1

Ag ::= »®crD .

® ,u‘K(u) du(¢ > —1),(2.12)

the second main step of our analysis was to establish that log A, is also
strictly concave on (0, +00), from which it follows that
A172 _> Am—3/2Am+1/2(m — 1, 2, & % .).

(2.13)

Now, integration by parts and the change of variable u =t" in (2.12) yield
1

Ap == rts /

°

22+3

422+ $(t) dt(x _> —1).

(2.14)

Thus, on choosing z = m — 1/2, the above reduces from (2.5) toAm—1/2 = bm41/T(m +3/2)(m= 1,2,...).

(2.15)

Substituting (2.15) in (2.12) then gives(bim+1 ) _ (2m + 1\, ;tem 3) bmodmer(m= 1,2,.. .),|(2.16)

which directly establishes (2.9) for all m = 2,3,.... (The remaining casem = 1 of (2.9) was established numerically by computing the moments
bo, bi, and b;, each to a precision of 50 significant digits.) We mention thathigh—precision estimates of {b,,}2%, and {D,, }!?—,, can be found in [2.3].

To add to our excitement, a review of a 1982 paper by Matiyasevich[2.7] appeared in the Mathematical Reviews (MR 85g:11079), after we hadsubmitted our manuscript [2.3]. Using an approach different from ours or
Grosswald‘s, Matiyasevich also attacked the Polya problem. Specifically,
Matiyasevich first established that the number D,, of (2.9) possesses theinteresting triple—integral representation _1 ~D», —— nin )"* (® om,..2m
nemy * du dv,$(u)$(v)(u 2 — V » ) [ [*_w(t)VU[(2.17)
where

w(t) := (t0(t))‘ O‘(t) —tP@"(t)0(t)127(t> 0).

(2.18)

As P(t) is well—known to be positive on [0, +00) (cf. Wintner [2.11] orThm. A of [2.3]), it is evident from (2.17) that establishingw(t) > 0,

for t > 0,(2.19)

would directly give the positivity of D,, for all m = 1,2,..., and thiswould affirmatively solve Pdlya‘s problem! Apparently by sampling valuesof w(t) and using an interval arithmetic computer package, Matiyasevich[2.7] asserts that (2.19) is valid, and that his interval computations "are as
powerful as a proof". Of course, a proof that the numbers {D,, }&., areall positive is given in [2.3]. Whether or not Matiyasevich‘s use of intervalarithmetic computations to establish (2.19) will be accepted as a rigorous
mathematical solution of Pélya‘s problem, his representation (2.17) willcertainly be very useful in further similar investigations associated with
the Riemann Hypothesis.
Concerning further possible research in this area, we mention an inter—esting open problem. In analogy with (2.2) and (2.6), consider the entire
function F\(z) defined by

Fi(—22) := [_ O(t)e*" cos(zt) dt,
o(2.20)

for any A > 0. Then, as in (2.4) and (2.5), we can write_ & b. (A)z"

ACQ= b —a.
where

.

o

bm (A) := [ £?"8(t)e"dto(2.21)(m =0,1,...).

(2.22)

It is known (cf. de Bruin [2.2]) that F(z) has only real zeros for all A > 1/2.
Moreover, it can be shown that if F)(z) has only real zeros, then Fy,(z) has
only real zeros for any A‘ > A. Now as the choice A = 0 in (2.20) gives thefunction F(z) of (2.6), then the truth of the Riemann Hypothesis would
necessarily imply that Fh(z) has only real zeros for each A > 0, from which
it would follow that the numbersa2
2m — 1\ ;aDm(A) := (bu(A))"— (G7)
bn—1(AJbmir(A)(m= 1,2,...) (2.23)

would satisfy the associated Polya— Turdén inequalities:
D.,(A) > 0(m = 1,2,...; all A > 0).

(2.24)

We conjecture that, in fact, that (2.24) is valid for all real A, and this iscurrently being investigated by us.** (Added in proof: This conjecture is now known to be true, and will appear in thejournal Constructive Approximation in 1988.)

128

References[2.1]

R.B. Boas, Entire Functions, New York: Academic Press, 1954

[2.2]

N.G. de Bruijn, The roots of trigonometric integrals, Duke Math. J.
17(1950), 197—226.

[2.3]

G. Csordas, T.S. Norfolk, and R.S. Varga, The Riemann Hypothesis
and the Turan inequalities, Trans. Amer. Math. Soc. 296(1986), 521—
541.

[2.4]

E. Grosswald, Generalization of a formula of Hayman, and its ap—
plications to the study of Riemann‘s zeta function, Illinois J. Math.

10(1966), 9—23.

[2.5]

E. Grosswald, Corrections and completion of the paper "Generaliza—tion of a formula of Hayman", Illinois J. Math. 13(1969), 276—280.

[2.6]

W.K. Hayman, A generalization of Stirling‘s formula, J. Reine[2.7]

Yu. V. Matiyasevich, Yet another machine experiment in support of[2.8]

G. Polya, Uber die algebraisch—funktionentheoretischen Unter—suchungen von J.LW.V. Jensen, Kgl. Danske Vid. Sel. Math.—Fys.
Medd. 7(1927), 3—33.

[2.9]

E.C. Titchmarsh, The Theory of the Riemann Zeta Function, Ox—
ford: The Clarendon Press, 1951.

Angew. Math. 196(1956), 67—95.

Riemann‘s Conjecture, Kibernetika 6(1982), 10—22 (MR 85g:11079).

[2.10] J. van de Lune, H.J.J. Rielte te, and D.T. Winter, On the zeros of the
Riemann zeta function in the critical strip IV, Math. of Computation
46(1986), 667—681.
[2.11] A. Wintner, A note on the Riemann (@—function. J. London Math.
Soc. 10(1935), 82—83.

3

The "1/9" Conjecture

The object of this section is to review the more recent results concerningthe "1/9" conjecture in approximation theory, and to mention some exciting
new developments related to it.
|
Because rational approximations of e~" occur naturally in the numeri—cal solution of heat—conduction problems (cf., [3.8, Chapter 8]), there has
been considerable theoretical interest in the best uniform rational approx—
imations to e~"* on [0, +00). Specifically, if T,,,, denotes the set of rational129

functions p,,(z)/q,(z), where p,,(x) and q,(x) are real polynomials of re—spective degrees m and n, then set

Amn := min { ||e_* — Tm.n(Z)llLso[0,+00) ! Tmn € Tmn }and setAi := lim AVZ;

A; := lim AZ(m <n)

(3.1)

(3.2)

It was first shown in 1969 by Cody, Meinardus, and Varga [3.2], using
elementary means, that

Tim A< pps.

(3.3)

Since it is obvious from (3.1) that

Aon 2 Atm 22 Ana(n= 0,1,...),(3.4)

then (3.3) gives that

0 < A1 € Ar S pong.

(3.5)

Thus, the error in best uniform rational approximation to e~" on [0, +00)
by rational functions in T,,, exhibits geometric convergence, and this phe—nomenon stimulated much subsequent related research. For further histor—
ical remarks and related references, see [3.1] and [3.9].
Now, the paper of Cody, Meinardus, and Varga [3.2] also contained

numerical estimates for {A,,, }iLi,. These numbers, which indicated thatthe upper bound in (3.3) was certainly crude, led Saff and Varga [3.5] toconjecture that

A; 3 Az,as well as thatq

AQ + 5

(3.6)
(3.7)

It was recently shown in 1985 by Opitz and Scherer [3.4] that the conjecturein (3.7) is false. More precisely, Opitz and Scherer, using an interesting
steepest descent approach and numerical optimizations, established that1

< ———;

A2 < 9.037

.

(3.8)

In other words, the geometric convergence rate of {A,,, }$p, is actually
better than 1/9! To round out our discussion here, the currently best lower
bound for A; was established in 1982 by Schonhage [3.6], and is1< Ai.
13.928130(3.9)

To describe connections with the Carathéodory—Fejér rational approxi—
mation method, letCOexp [(a —1)/(a +1)] = 3"caTé(@)(# € [—1, +1])

k=0

(3.10)

denote the Chebyshev expansion of exp [(x — 1)/(x + 1)] on [—1, +1], where+1—1

Ck := * / exp [(a — 1)/(a + 1)] Ti(#) dae /V1 — 2|(k = 0,1,...),(3.10)

and where the prime on the summation in (3.10) means that co/2 is usedin place of co, defined in (3.10). On forming the infinite Hankel matrix
H := [¢;4;—1]i§., from the coefficients of (3.10), set¢,, := nth singular value of H (where 0, > 04 > <>).

(3.11)In 1983, Trefethen and Gutknecht [3.7] conjectured that
Aun ~ On(n — 00),(3.12)

and, on the basis of numerical estimates of a, from [3.7], they further
conjectured that
1A2 = 3.38903(3.13)

Subsequently in 1984, Carpenter, Ruttan and Varga [3.1] calculated (by theRemez algorithm) the numbers {A,,, }2%, with very high precision (about

200 decimal digits), and with Richardson extrapolation techniques, theyconjectured thatA+1

_ 9.28902 54919 2081 °(3.14)

Note that this latter conjecture, on rounding, confirms (to the number ofdigits claimed) the conjecture of Trefethen and Gutknecht in (3.13), which
was based on totally different computations and analyses.
In a surprising new development, A.P. Magnus [3.3] has estimated thesingular values a,, of (3.11), and he is convinced that

A, & e—rk‘/K,(3.15)

where K and K‘ are complete elliptic integrals of the first kind (usual
notation), evaluated at the point where K = 2EF, E being the complete
elliptic integral of the second kind. Even more astounding is the fact thatthe number e~"*‘/* , which can be calculated to arbitrary precision, is givenby1—1rK‘/K_
C

1

4

9.28902 54919 20818 91875 54494 35952...‘(3.16)

131

which agrees with all 15 digits of (3.14), again based on totally different
computations and analyses! It is very likely that Magnus‘ conjecture (3.15)
is correct, but there is no complete proof of this as yet.
We conclude this section by stating that it would seem that a sequence of
esplicit and constructive rational approximations {r,, (z)}7.., of e~" could
be found (perhaps based on the notions of inner polynomials introduced by
Opitz and Scherer [3.4], and on Laguerre polynomials) which would directly
settle all these interesting conjectures in this area, without the necessity of
indirect use of the Carathéodory—Fejér method.
References[3.1] A.J. Carpenter, A. Ruttan, and R.S. Varga, Extended numerical com—putations on the "1/9" conjecture in rational approximation theory, in
Rational Approzimation and Interpolation (P.R. Graves—Morris, E.B.
Saff, and R.S. Varga, eds.), Lecture Notes in Mathematics 1105, 383—
411, Heidelberg: Springer—Verlag, 1984.
[3.2] W.J. Cody, G. Meinardus, and R.S. Varga, Chebyshev rational ap—
proximation to e~* in [0, +00) and applications to heat—conduction
problems, J. Approximation Theory 2(1969), 50—65.
[3.3] A.P. Magnus (1985), C F G T determination of Varga‘s constant"1/9" , personal communication.
[3.4] H.—U. Opitz and K. Scherer, On the rational approximation of e~* on[0, +00), Constr. Approx. 1(1985), 195—216.
[3.5] E.B. Saff and R.S. Varga, Some open questions concerning polynomi—
als and rational functions, in Padé and Rational Approzimation (E.B.
Saff and R.S. Varga, eds.). pp.483—488, New York: Academic Press,
Inc., 1977.
|
2.
ed
relat
and
e~"
ation to[3.6] A. Schonhage, Rational approxim

problems, SIAM J. Numer. Anal. 19(1982), 1067—1082.

[3.7] L.N. Trefethen and M.H. Gutknecht, The Carathéodory—Fejér method
for real rational approximation, SIAM J. Numer. Anal. 20(19830, 420—436.
[3.8] R.S. Varga, Matriz Iterative Analysis, Englewood Cliffs, New Jersey:
Prentice—Hall, Inc., 1962.
[3.9] R.S. Varga, Topics in Polynomial and Rational Interpolation and Ap—
prozimation, Montreal: University of Montreal Press, 1982.

132

4

The Ruscheweyh—Varga Conjecture andthe Volcano Function

There has been a continuing research interest in global descent meth—ods for finding zeros of a given polynomial. (For recent contributions on~ this and for related literature, see Henrici [4.1] and Ruscheweyh [4.3].) To
crudely describe such methods, let p,(z) be a given complex polynomial,and suppose that z,, our initial starting point of a procedure for finding azero of p.(z), is such that p.(zo) £ 0. Without loss of generality, assume
zo = 0, and further normalize p,,(2) so thatpa(z2) = 1+ Y} a;z‘,

where Y" |a;| # 0.

j=1

(4.1)

j=1

By a well—known result of Cauchy (cf., Marden [4.2, p. 126]), if R (called
the Cauchy radius of p,(z)) is defined as the unique positive real root of

1 — Y] |aj|R‘ =0,
j=1

(4.2)

then each zero 2 of p,,(z) necessarily satisfies [#] > R. On further normal—
izing R to unity, i.e., on assumingn

3 |aj| = 1,

j=1

(4.3)

then any polynomial p,(z) in (4.1) which satisfies (4.3) evidently has nozeros in [z] < 1. (It may well have zeros on [z] = 1, as the example 1 + z"
shows.)
Next, let z1 be any point on |z| = 1 for which|pa(z1)] = min|pa(e*)|.

(4.4)(In actual numerical applications, [p,, (21 )| need only be an approzimation of
the minimum of |p, (e)}, obtained from sampling [p,(2)]| in a finite numberof points on |z| = 1.) Note that since p,(z) from (4.1) is not identicallyconstant, then by the minimum principle,|pal21)l < l|pr(zo)] —(4.5)

In this fashion, one obtains (with appropriate normalizations at each step)a sequence of points {z,;}%, which, because of (4.5), is known to converge

to a zero of p, (z).

Our interest in the problem was in the following question. While (4.5)

shows that the point z; is in some sense an improvement over zo in esti—

mating a zero of p,(z), it could be that the reduction in [p, (z))], in finding/133

|P.(z1)], might be small. This led to the question of how large min |p.(e")|
can be for all polynomials p,(2z) satisfying (4.1), and (4.3). Thus, we were
led to the problem of investigating the behavior ofnI,, := sup { min |pa(2)] : pa(2) = 1+ Y} a;z‘ with Y" |a;| = 1 } ,
j=1

j=1

(4.6)

for each n > 1.

1 —

3 | ——In Ruscheweyh and Varga [4.4], it was shown that

<I, < 1—i4¢<1—,n2m(r>3).

(4.7)

Analogously, if we set

F, := sup| min lpa(2)] : paCe) = 1 + $ a;#‘j=1

with p() =2, 4 >0 (1 <; <n) },(48)42then each polynomial considered in (4.8) evidently satisfies the hypothesesfor (4.6), so that

.

(4.9)

n < In.

1 —

3 | —

It was further shown in [4.4] that—
3
3
1
SF</_—
ap"~a+*(G)(n — co). (4.10)

Next, we conjectured in [4.4] thatT.<sFPF,(rn>1),(4.11)and that there exists a positive constant y (independent of n) such that

mo f

1
(2)
2Y £o(2)T, #1 ——(nc) .

4.12(412)

Indeed, extended precision calculations given in [4.4] led us to further con—jecture in [4.4] thaty 2 0.86718 9051... .

(4.13)

In subsequent research, Ruscheweyh and I [4.5] have focused on thefollowing different, but related, problem. Let P,, denoting the set of allcomplex polynomials of degree at most n (mn > 1). Then for each complex
number p, consider the following subset of P,, of polynomials with twoprescribed values, defined byP.(p) a {pn(2) E P,, : p. (0) = 1 and Pr(1) — } *134(4.14)

What then can be said about the nonnegative numbers

Sa(u) := sup { min |pr(z)| : pa € Pile) } ©)(4.15)

as a function of n and u?
One of the surprising results of [4.5] is that
S,(2) =I, = 1— y—{arccosh(2)}" + o (2)(n — 00),(4.16)

so that the quantity y of (4.12) is exactly given by

y = {arccosh(2)}*/2 = 0.86718 90511 36318... .

(4.17)

Thus, our conjecture of (4.13) (as to the number of digits given in (4.13))
is correct. The conjecture of (4.11), however, remains open.
We quote from [4.5, Corollary 1] the following result which, for the
special case u = 2, gives the result of (4.16).
Theorem 4.1 Let u > 0. Then there holds
L,
0,
0,

Sa(u) ={

if 0 < u < 1
if 1 < u < 2";
if 2" < u.

(4.18)

Here, 0 is the uniquely determined solution in (0,1) of the equation
L4 = 0Thqi (a—V(+)) 3(4.19)

where Taqi(z) denotes the Chebyshev polynomial (of the first kind) of degree
n +1. For n tending to infinity, the solution a of (4.19) can be expressedas1
0 = 1 — {arecosh(u)}*/2n + o (2)(n — 00).
(4.20)In addition, for u E (1, 2") and for a defined in (4.19), define the polynomial
Qn,o(z) by means ofd

1 + w"

2\__
Qnc(w*):=minT3» 2n+3 Jo {» —(nrn+1) T4 |e —1/(nrn+1) (p" )]}(4.21)
Then, Qne(2) is an element of P,(u), and is the unique extremal polyno—
mial for S.(u), i.e.,
Sa(u) = min |Qne(#)| .

(4.22)

Moreover, Qn,«(z), when expanded in powers of z, has positive coefficients.
Finally, we can associate to each complex number w in the complex
plane the nonnegative quantity S,,[(1) of (4.15), thereby generating a three—dimensional surface. This surface, as it turns out, has the interesting shapeof a volcano. There are different types of volcanoes (active, dormant, ex—tinct), and the present author hopes that this volcano will help convey theactive interplay between scientific computing and mathematical analysis!
135

References[4.1] P. Henrici, Methods of descent for polynomial equations, in Compu—
tational Aspects of Complez Analysis (H. Werner, L. Wuytack, E. Ng,
H.J. Biinger, eds.), pp.133—147. Boston: D. Reidel Publishing, 1983.
[4.2] M. Marden, Geometry of Polynomials, Providence, Rhode Island:
American Math. Soc. (Mathematical Surveys, No. 3), 1966.
[4.3] S. Ruscheweyh, On a global descent method for polynomials, Numer.
Math. 45(1984), 227—240.
[4.4] S. Ruscheweyh and R.S. Varga, On the minimum moduli of normal—
ized polynomials, in Rational Approzimation and Interpolation (PR.
Graves, E.B. Saff, and R.S. Varga, eds.), Lecture Notes in Mathemat—
ics 1105(1984), 150—159, Heidelberg: Springer—Verlag.
[4.5] S. Ruscheweyh and R.S. Varga, On the minimum moduli of normal—
ized polynomials with two prescribed values, Constructive Approxi—
mation 2(1986), 349—368.

136

Texas Tech University, Mathematics Series

Visiting Scholars Lectures, 1986—1987, vol. 15 (1988)

Mathematical Results for Mapping DNA
Michael S. Waterman
Departments of Mathematics and Molecular Biology
University of Southern California
Los Angeles, CA 90089—1113
1

Introduction

When people discover new territory, such as a continent or even a galaxy,
one of the first goals is to make at least a rough map of the territory. A map
lets us organize the unknown into manageable units, so that we can find
our way around and locate more and more features of interest. When Lewis
and Clark set off on their famous journey, they already knew a great deal
more about the continent than did Columbus. By the time they reachedthe Pacific, they had established much information of great value, such as
the existence and approximate location of rivers, mountains, and deserts.
At the present time, the physical geography of North America is known tofine precision due to increased familiarity and the application of satellite
technology.
A major scientific revolution is occurring in the biological sciences [11]that can be viewed in the above context. After Mendel it was known that
inheritance of genetic information occurred, but there was no idea as towhat the units of inheritance might be. Eventually light microscopes wereable to locate objects called chromosomes which, it was correctly reasoned,
contained the units of inherited genetic information. In 1953, Crick andWatson determined that DNA, in a linear sequence of adenine (A), cytosine(C), guanine (G), and thymine (T), was the form of genetic information. At
that time, the state of knowledge about a genome (all the genetic informa—tion of an organism) corresponded approximately to that which Columbus
possessed about North America after he discovered it. During the mid tolate 1970s, biological scientists learned to read the linear sequence of small
regions of DNA. Think of their knowledge as corresponding to that of thefirst North America settlers exploring the fringes of the continent. Now only
a decade later, we are seriously working at mapping the human genome of
3 x 10° letters (nucleotides) of DNA. The bacterium E. coli. of 4.7x 10°
nucleotides has just been physically mapped [9], the first organism of thatsize to be mapped. We are at just about the planning stage of a Lewis and
Clark expedition getting ready to set off to make a rough but very usable
137map of a continent.
Just what does mathematics have to contribute to these exciting explo—
rations? In classical genetics mathematical contributions are well known.
Molecular biology has "re—defined" allele and some geneticists and math—ematical biologists are hard at work to update those concepts to produce
genetic maps [1]. However, here we will concentrate on physical mapping,
and we will find some mathematics hiding among the nucleic acids andenzymes of biology.

The discussion will be divided into two parts, thefirst treating the physical mapping of small DNA molecules and the second
physical mapping of genomes.

2

Mapping Small Regions of DNA

DNA is taken here to be a finite, linear word over the four letter alphabet{A,C,G,T}. While DNA can be circular, we will only discuss the linear
case. Site—specific restrictions enzymes were discovered in 1970 [12]; these
enzymes cut the DNA at a short pattern (frequently of 4, 6, or 8 letters)
specific to that enzyme. For example, the restriction enzyme Hhal cuts at

GCGC. It is experimentally possible to apply these enzymes singly or in
combination, and to estimate the lengths of the fragments of DNA that
result. The problem is to construct the map of location of the enzyme
sites along the DNA from this fragment length data. The results are fromGoldstein and Waterman [8].

2.1Simulated Annealing

Here we consider the simplest problem of interest involving linear DNA,two restriction enzymes, and no measurement error. We will refer to thisproblem as the double digest problem or problem DDP. A restriction en—
zyme cuts a piece of DNA of length L at all occurrences of a short specificpattern and the lengths of the resulting fragments are recorded. In the
double digest problem we have as data the list of fragment lengths wheneach enzyme is used singly, say,A ={a :l <i<gn}from the first digest

B ={b;:1<i<m}from the second digest,

as well as a list of double digest fragment lengths when the restriction en—
zymes are used in combination and the DNA cut at all occurrences specificto both patterns, say
C = {ail §€i4 < mr}.
Only length information is retained; order is unknown. In general A, B
and C will be multisets; that is, there may be values of fragment lengths
138

that occur more than once. We adopt the convention that the sets A, B,

and C are ordered by length, that is, a; < a,; for : < ;, and likewise for thesets B and C. Of course
Y)

a; =

1<i<n

3°

b; =

1<i<m

Y

c; = L,

1<i<ni,2

since we are assuming that fragment lengths are measured in number ofletters with no errors.
Given the above data the problem is to find orderings for the sets A
and B such that the double digest implied by these orderings is, in a sense
made precise below, C. This is a mathematical statement of a problem
considered by Pearson [14], who solved it by exhaustive search.
We may express the double digest problem moreprecisely as follows.
For permutations a E S,, u € S,, call (,p) a configuration. By ordering
A and B according to a and u, respectively, we obtain the set of locationsof cut sites$= {s:is= Y az(;) Of $ = Y" but) a 0<rsn, 0<t<m}.

1<j<r

1<j<t

Since we want to record only the location of cut sites, the set S is notallowed repetitions, that is, S is not a multiset. Now label the elements ofS such that

S$ = {s; :1 <j Sma},

with s; < s; for i < j.

The double digest implied by the configuration (a, 4) can be defined byC(o,u)= {ci(0,u): ci(lao,u)= s; — s;—1, for some a < j < ma},where we assume as usual that the set is ordered in the index :. The
problem then is to find a configuration (a,4) such that C = C(a,p). As
discussed in Section 2.3, this problem lies in the class of NP complete
problems conjecturedto have no polynomial time solution.
In order to implement a simulated annealing algorithm, an energy func—tion and a neighborhood structure are required. We take as our energyfunction the chi—squared—like criterion
Can —

Y

i1<i<ni,2(ci(c, p) ~ c;)" /enote that if all measurements are error free then f attains its global mini—
mum value of zero for at least one choice (a, p).
Following Lutton and Bonomi [2], we define the set of neighbors of aconfiguration (a, 1) by139

N(o,u) = {(r, u):r e N(a)}U{(0,v): ve N(p)},where N(p) are the neighbors used in the discussion of the travelling sales—
man problem [2].
With these ingredients, the algorithm was tested on exact, known datafrom the bacteriophage lambda with restriction enzymes BamHI and EcoRI,
yielding a problem size of |A|! B|! = 6! 6! = 518,400. See Daniels et al. [4]for the complete sequence and map information about lambda. Tempera—ture was not lowered at the rate c/log(n) as suggested by the theorem inGeman and Geman [7], but the reasons of practicality was instead lowered
exponentially. On three separate trials using various annealing schedules
the solution was located after 29,702, 6895, and 3670 iterations from ran—
dom initial configurations.

2.2

Multiplicity of Solutions

In many instances, the solution to the double digest problem is not unique.
Consider for example

andA{1,3,3,12},

B{1,2,3,3, 4,6},

C = {1,1,1,1,2,2,2,3,6}.

This problem of size 4!6!/2!2! = 4320 admits 208 distinct solutions. We
now demonstrate that this phenomenon is far from isolated.
Below, we use the Kingman subadditive ergodic theorem to prove thatthe number of solutions to the double digest problem increases exponen—tially as a function of length under the probability model stated below.
For reference, we state a version of the subadditive ergodic theorem [10]here. For s,t non—negative integers with 0 < s < t let X,,, be a collectionof random variables which satisfy(i) whenever s < t < u, X;4 < Xsi + Xiu,
(ii) the joint distribution of {X,,} is the same as that of {X.4141},(iii) The expectation g; = E[Xo,,] exists and satisfies g,; > —Kt, for someconstant K and all t > 1.
Then the finite lim;Xo,4/t = A exists with probability one and in themean.
For our probability model, sites labeled 1,2,3, ..., are cut by two re—striction enzymes independently with probability p;, p;, respectively with
P; € (0, 1).

140

Let a coincidence be defined to be the event that asite is cut by both
restriction enzymes; such an event occurs at each site independently withprobability pip; > 0, and at site 0 by definition. On the sites 1,2,3, ...,
there will be an infinite number of such events. For s,u = 0,1,2,... and0 < s < u we may consider the double digest problem for only that segment
located between the sth and uth coincidence. Let Y,,, denote the numberof solutions to the double digest problem for this segment.
It is clear that wherever s < t < u, given a solution for the segment
between the sth and tth coincidence and a solution for the segment between
the tth and uth coincidence one has a solution for the segment between the
sth and uth coincidence. HenceYs,u _ \D ®

We note that the inequality may be strict as Y,, counts solutions given
by orderings where fragments initially between, say, the sth and tth coin—cidence now appear in the solution between the tth and uth coincidence.
Letting
Ast —— *~ log Ys:

we have that s < t < u implies X,,4 < Xs; + Xiu.
|
Additional technical details can be established to show there is a con—stant A > 0 such that|lim 128COe
_ );,
A

t—00

2.3

Computational Complexity

We demonstrate below that the double digest problem is NP—complete.
See [6] for definitions. It is clear that the double digest problem DDP as
described above is in the class NP, as a nondeterministic algorithm need
only guess a configuration (a,) and check in polynomial time if C(a, p) =C. The number of steps to check this is in fact linear. To show that DDP
is NP—complete we transform the partition problem to DDP.
In the partition problem, known to be NP—complete [6], we are given a
finite set A, say |A = n, and a positive integer s(a) for each a E A andwish to determine whether there exists a subset A‘ C A such that
Y s(a) =ace A‘

Y s(a).
a€6A—A‘If Y.e4 s(a) = J is not divisible by two, there can be no such subset A‘;
else, consider as input to problem DDP the data A = {s(a;): 1 < k <n},B = {J/2, J/2}, and set C = A. It is clear that any solution to problem
DDP with this data yields a solution to the partition problem through theorder of the implied digest C. Therefore DDP is NP—complete.
141

3

Genomic Mapping of DNA by Fingerprinting

The problem of this section is to make a map of a full genome of DNA. As
seen in the last section, simply digesting even 10° nucleotides of DNA withenzymes that cut on the average of every 4° nucleotides would not give us amap. Instead the biologist constructs a library (sample space) of randomly
selected pieces of DNA called clones. The clones might be, for example,
15 x 10° nucleotides of sequence. He hopes that if he randomly samples
enough clones he will have overlapped the clones into islands. In this way
he can organize a genome of DNA into overlapping clones that span the
genome.
To assist the experimental scientist we wish to give some estimates about
the number of clones necessary to map a large percentage of the genome.
The only additional concept we need is that of the fingerprint of a clone.
Various experimentalists have developed different strategies, but the idea
is that each clone is digested with one or more enzymes and the data used
to detect overlap [3,9,13]. Obviously a small amount of overlap between
two clones cannot be detected. We parameterize this by 0, the fraction of
overlap necessary for overlap to be detected.

3.1

Estimates with Constant Overlap Detection

First we set some notation:

G = haploid genome length in nucleotides;
L = length of clone insert in nucleotides;
N = number of clones;a = N/G = probability of starting a new clone;
O = amount of overlap in nucleotides necessary to detect;

0 = O/L;c = redundancy of coverage = LN/G.
Proposition 3.1 Let 0 be the fraction of overlap between two clones re—quired to detect the overlap. Let a = 1 — 0.
(1) The expected number of apparent islands is Ne.
(2) The expected number of apparent islands consisting of j clones (j > 1)
18
Ne" (1 — e7°" y— .

142

(2‘) The expected number of apparent islands consisting of at least twoclones 1s
Ne~* — Ne".
(3) The expected number of clones in an apparent island is e.
(4) The expected length in nucleotides of an apparent island is

L [((e" —1)/c)+(1—0)].
(5) The expected length in nucleotides of an unmapped gap (ocean) be—
tween true islands is 1/a.
For results in the case of actual islands that would result if all overlaps
could be detected, use the above formulas with a = 1.
Proof. Imagine that we move from nucleotide to nucleotide through the
genome, starting at one end. The probability that we encounter the begin—ning of a cloned insert at any nucleotide is a. An island begins when we
encounter a cloned insert and continues while we detect overlapping clones.
The probability that we begin a cloned insert and fail to detect an overlap—
ping clone is «(1 — a)"" = a(1 — N/G)(C/N)" x ae". Since the number ofislands is equal to the number of times we exit a clone without detecting
overlap, the expected number of islands is Gae~" = Ne~C and we haveshown (1).
The above reasoning shows that the number of clones, ;, in an island fol—lows a geometric distribution, with stopping probability e~"" , and has prob—
ability (1—e~")}~*e~". Multiplying this last probability by the expected
number of islands gives (2), while the mean of the distribution required by(3) is e".

|

To prove (4), consider an islandconsisting of J clones, where J has
the geometric distribution noted in the last paragraph. The length X; (innucleotides) of the coverage of the ith clone, 1 < i+ < J — 1 has n truncatedgeometric distribution:
P(X,; = m) = «(l — ay"~* / [1 — (1 — a)" ,1 < m < Lo. The expected length of an apparent island inE(Ficis x;) + (1 —a),since the last clone contributes a full insert length, L, the full island length.
The above expression is, by Wald‘s identity [5], F(X)(EF(J)) + (1 — a)L.
Some summation of series gives equation (4).
One apparent feature of the model is its linearity. To see how this follown
from the results derived above, first assume the genome is hroken up into
EKlarge segments. One can think of these segments as chromosomes, ‘Phen\143

YLic<<r C; = G, where G; is the size of the ith segment. We allocate a total
number of clones N by N = aG = Cicicpy 4G; = TCiciep N;. Consider, forexample, the number of islands. Equation (2) gives theexpected number ofislands to be N exp (—c(1 — 0)), in the case that the genome is unsegmented.
Notice that|
Nexp(—co)= Y" N;exp(—c0o)
1Ci<K
and the expected number of islands for the K segments add to equal the

expected number of islands for the "unbroken" genome.

The preceding analysis is relevant to discussions about whether it isworthwhile to separate chromosomes and map individual chromosomes or
to just map the complete genome. An important assumption is concealedin the analysis: 0 is constant for various numbers of clones. In reality
it becomes harder and harder to detect overlap as the number of clones
increases. To see this recall that to find overlap relationships in N clones
requires (4 ) = N(N — 1)/2 pairwise comparisons. Therefore with fixed 0,
the number of false overlaps detected goes up proportionally to N*.

3.2

Variable Overlap Detection

In this section we relax some of the simplifying assumptions made in Sec—tion 3.1, namely that L and 0 are constant. Now we take the clone size
L to be chosen according to some probability distribution with mean L.
The overlap between two clones necessary to detect overlap will be OL
nucleotides, where 0 is chosen according to some probability distribution.

This last distribution is meant to model the differences between signaturesfrom clone to clone. The same number of nucleotides can have a widelydiffering number of ECORI sites, for example. Next we present formulas
for the case of L and 0 non—constant which correspond to the formulas ofSection 2.
We define the redundancy by c= LN/G; G, N, and a remain defined
as before. It will become evident that a = L/L — 0 is the correct formulafor a. The probability that overlap is not detected in a clone of length L
is (1 — a)*~" x e—°/4+—9) = e~*. The probability density function of a isf(g). The average stopping probability is then f e~—* f(a) do, and replacinge~" by this integrated form gives the new versions of (1), (2), and (3):(1*) The expected number of apparent islands is
N [e* f(a) do.
(2*) The expected number of apparent islands consisting of j clones (j > 1)
1s
144

N {/ e—f(a) do} {1 — [&flo) do} .
(3*) The expected number of clones in an apparent island is{/ e—f(0) do}

To justify the generalization of (4), we need to assume that X;, thecoverage of the ith clone in nucleotides, define statistically independent
random variables. This was easily the case when L and 0 were constant,
and we will later show that it is a reasonable assumption here. Under thatassumption, we have(4*) The expected length in nucleotides of an apparent islund is{[&flo) do}—1[1/« — [/ Loe" / (1 — e~**> f(L, a) dL. do +J L(1 — o)f(L, 0) dL do,where f(L, 0) is used to indicate the random nature of both L and a.
Some mathematical results are available for the offects of nllowing vari—ation in L and a. In particular Jensen‘s inequality tells un that n convex
function of the average of a random variable is less than or equal to theaverage of that convex function evaluated at the random variable., Sincee_ is a convex function, (1*) gives the result that
Average # of islands > N e~®@) .. y&—v—=H(#))|
and (3*) becomes
Average # clones in an island < e*") — £"C‘~M(#),
where E(G) is the average value of 0. This tells us that using nvornge
values underestimates the number of islands and overestimates the numberof clones in an island. Recall though that wo nro counting Isolnted clonen
as islands; unfortunately equation (2) cumnot he nualyzed with Jennen‘sinequality to obtain either an upper or a lower hound for the number ofislands with two or more clones.
Another approach to evaluating the effects of non constant L nud 0 is
to expand the exponential functions into a Taylor neries, We will let Var(a)denote the variance of a. Expanding out to second order terma given un
Average # islands ~ Ne~* ") {1 + e* Var(a)/ 2} .
——145

whiley —1
Average # clones per island z {es© {1 + c* Var(a)/2}} .
Using this approach, an approximate value can be found for (2‘):

Average # islands with at least 2 clones 2(Ne—*BC) __ Ne~2*°E(@)) +Nc‘e~*®C) {Var(0)/2} {1 — 2Ne°®) — Nee—*BC) Var(c)/2} .
Therefore, while the average number of islands increases under variation,
the average number of non—isolated islands can either decrease(small c) or
increase(large c). What is the size of these changes? Each effect involves
Var(g). From the definition of a, we find that
Var(a) = Var(L)/(LYy‘ + Var(0),which is not likely to be very large. The first term is unlikely to contributesignificantly, while Var(0) might be as large as 0.01. Still, multiplying by
Nc" increases the effect.
Acknowledgements. Section 2 describes a joint paper with Larry Gold—stein [8] and Section 3 reports work in progress with Eric Lander.
References[1]

B. J. Backmann, Linkage map of Escherichia coli K—12, Edition 7,
Microbiol. Rev. 47(1983), 180—230.

[2]

E. Bonomi and J. L. Lutton, The N—city travelling salesman prob
lem: Statistical mechanics and the Metropolis algorithm, SIAM Rev.
26(1984), 551—568.

[3]

A. Coulson, J. Sulston, S. Brenner, and J. Karn, Toward a physicalmap of the genome of the nematode, Caenorhabditis elegans, Proc.
Natl. Acad. Sci. USA 83(1986), 7821—7825.

[4]

D. Daniels, J. Schroeder, W. Szybalski, F. Sanger, A. Coulson,
G. Hong, D. Hill, G. Peterson, and F. Blattner, Complete annotatedlambda sequence, in Lambda II, (R. W. Hedrix, J. W. Roberts, and F.

W. Weisberg, eds.), Cold Spring Harbor Laboratory, 1983.

[5]

W. Feller, An Introduction to Probability Theory and its Application,
Vol. I, John Wiley & Sons, New York, 1968.

[6]

M. R. Garey and D. S. Johnson, Computers and Intractability: A
Guide to the Theory of NP—Completeness, Freeman, San Francisco,
1979.
146

[7]

S. Geman and D. Geman, Stochastic relaxation, Gibbs distribution,and the Bayesian restoration of images, IEEE Trans Pattern Anal.
Mach. Intell. 6(1984), 721—741.

[8]

L. Goldstein and M. S. Waterman, Mapping DNA by stochastic relax—
ation, Adv. Appl. Math. 8(1987), 194—207.

[9]

K. Isono, Y. Kohara, and K. Akiyama, The physical map of the whole
E. coli. chromosome: application of a new strategy for rapid analysis
and sorting of a large genomic library, Cell 50(1987), 495—508.

[10] J. F. C. Kingman, Subadditive ergodic theory, Ann. Probab. 1(1973),
883—909.
||[11] B. Lewin, Genes III, third edition, John Wiley & Sons, New York,1987.
[12] D. Nathans and H. O. Smith, Restriction endonucleases in the analysis
and restructuring of DNA molecules, Ann. Rev. Biochem. 44(1975),
273—293.
|[13] M. V. Olson, J. E. Dutchik, M. Y. Graham, G. M. Brodeur, C. Helms,
M. Frank, M. MacCollin, R. Scheinman, and T. Frand, Random—clone
strategy for genomic restriction mapping in yeast, Proc. Nat. Acad.
Sci. USA 83(1986), 7826—7830.
[14] W. Pearson, Automatic construction of restriction site maps, Nucleic
Acids Res. 10(1982), 217—227.

147