previous sub-section
3— Multiplicative Systems in Several Variables I, II, III: With C.J. Everett (LA-683, June 7, 1948) (LA-690, June 11, 1948) (LA-707, October 28, 1948)
next chapter

III

Abstract

The set FJ of all possible genealogies or graphs z of a multiplicative system produced from one particle of type i is here introduced as a fundamental concept in the theory of such systems (see I, II). This set possesses a natural intrinsic distance function d(z, z') under which it is a complete zero-dimensional metric space satisfying the second axiom of countability.

Simple axioms on (A) intervals and (B) measure of intervals are given for an abstract set from which the classical theory of completely additive measure is derived.

Intervals in the set J1 are defined intrinsically and shown to satisfy the axioms A. If now a particular multiplicative system with given generating transformation G(x) is given, the transition probabilities Pl (i;ji,.. ,jt) serve to define a measure for the intervals of 1; satisfying the axioms B. Proof of the latter is non-trivial due to non-local-compactness of the space 17.

With this mathematical structure at hand it becomes possible to state in a simple way some of the striking properties of multiplicative systems.

If x° = G(x° ) is the death-fix-point of G(x), then the set of graphs of Fi which terminate in death has measure xi .

If v = (vl,...,v 1) is the characteristic vector corresponding to the maximal positive characteristic root r > 1 of supercritical system, then the set of all graphs of 1 whose k-th generation population approaches the ratios v:v2:... :vi has measure I - A°. Thus, almost all graphs (genealogies) either terminate in death or approach the mode v as limit. These results are trivial for subcritical systems, in which by definition, 3z = 1.


86

I—
A Remark On Measure Theory

1. It is convenient for our purposes to have a simple set of axioms on which measure theory may be shown to rest. To this end, let r = {z} be a set of points z, and I = {i} a class of special subsets i of F called intervals. We demand that the entire set F and the empty set X be intervals. Denote by J the class of all subsets S = Ei of F which are set sums of a finite or countable number of intervals. (All set sums hereafter are understood to operate on finitely or countably many summands. The notation La is used to indicate that the summands are mutually disjoint.)

We suppose that intervals satisfy the following axioms: I 1. Every set S = Zi of J can be represented as a sum Ej of disjoint intervals. I 2. The complement i' = -i of an interval i in J. I 3. The set product ij of two intervals i and j is an interval k.

Moreover, we assume m 1. To every interval i is assigned a non-negative real number m(i)>0 called its measure. m 2. M(F) = 1, m(0) = 0. m 3. If i = Ej, where the i and j are intervals, then m(i) = mr(j).

An additive class C of subsets of F is one such that C 1. All intervals belong to C. C 2. A is in C whenever all sets A are in C. C 3. If A is in C, so is A'.

The Borel sets are those common to all additive classes, hence, themselves form an additive class.

We shall define a property of subsets U of F called measurability, and prove that the class of measurable sets is additive. Simultaneously we define a measure m(M) for every measurable set M and prove

M 1. 0 <m(M)< 1 for M measurable. M 2. m ( M) =Em(M) for M measurable. M 3. If M is an interval, the measure assigned to M as a measurable set coincides with its intitially given measure.


87

2. In stating the above axioms, we have attempted to focus attention on the fundamental assumptions. It remains to show that the essential theorems follow from our axioms. This we do in the remainder of this chapter, for the sake of completeness, following the classical arguments for the real line1 . We note first the following properties of intervals: I 4. E S is in J whenever all the summands S are in J. For E S is an at most countable sum of at most countable sums of intervals. N

I 5. I1 i, then S' is in J whenever all N factors are in J. It suffices to see this for N = 2. Hence let S1 = Zim, S2 = j. Then S1S2= i,mjn = E (imjn). By I 3, imjn is an interval, so S1S2 is in J, the range (m, n) being at most countable. 6. If S = i, then S' is in J. N For S' = i', each i' is in J by I 2, and thus S' is in J by I 5. 1

3. We now assign a measure to every set S of J. Note first that if i D Si in, then i = Zin±+i(in) . By I 6 and I 5, the latter set is in J, so by I 1, we may write i= in i-n+ Ejm, and by m 3, and m 1, m(i = E (in) + E T(j) > E m (in).

Hence, if in is any sum of disjoint intervals, we have for every N, F D i in and hence 1 > Z m (in). Thus E m (in) exists, less than or equal to 1, for every such disjoint sum.

Now suppose -i,n = Zjn. Then im = im(Zjn)= E (imjn) ,nkmn, kmn being the intervalim, jn. (See 1 3.) Hence by m 3, m (im) = En m (k,,) and m(im) = m En m(kmn). Similarly Em(j,) = En Em m(kmrl). Now the double sum mn, m (kmn) converges to a limit < 1 by the preceding paragraph since the kmn are disjoint. Hence the iterated sums are both equal to this limit and hence to each other. Thus E m(im)= - m (jn).

It is therefore clear that, if S is any set of J we can write S = Zi and define m(S) = rm(i) unambiguously. Clearly 0 <m(S), and if S is an interval i, m(S) coincides with the initially given measure m(i).


88

4. We establish in this section some properties of the measure m(S) for sets S of J. First, m 4. m(S) =m(S). For, write Sm =i,,mn. Then m(ZS) m( n imn)En,m (im,) = Zm n m (in,) = m (S,) . Next m 5. If S and T are in J and S c T, then m(S)<m(T).

For, let S = E im and define Sn =m. Then T = S +TS', the summands being disjoint and in J. Hence, by m 4, m(T) = m (S) + m(TS')> rn(Sn) =m(i,,). Hence m(S) = m(i) < m(T). Thus follows m 6. For all S in J, 0 <m(S)< 1.

Next we prove m 7. For arbitrary sets S of J, disjoint or not, m(Z£S)<Zm(S), where the latter sum may of course be infinite.

Write S = E imn. Then ZSm = m,i,,, = ip = il4i1i 2+ili2" 3i . , the latter summands being disjoint and in J. Hence, by m 4, m 5, m(Sm,) = m(il) +(i'i2) + ... <(il)+m(i 2) + ...= r m(ip) = m,, 7n(imr,) = nErE m (imn) = Emm(S), the latter possibly being infinite.

Finally we have m 8. If S and T are in J, then m(S + T) + m(ST) = m(S) + m(T). First suppose S and T are each finite sums of intervals. Write S + T = S- (T- ST) ST- (T - ST) = T

where S and ST are in J, and, ST being a finite sum of intervals, also T - ST = T(ST)' is in J. Thus by m 4, m(S + T) = m(S) + m(T - ST) m(ST) + m(T - ST) = m(T), and addition yields the equation of the theorem.


89

Now let S = Zim, T = ij,, where we make either sum terminate in 0 in case it happens to be finite. Define Sn and Tn as the corresponding partial sums through the first n terms. Then by the first part of the proof we have for every n, n (Sn + Tn)+m(SnTn) = m(Sn)+mr(Tn). But limm(Sn) = limTli, = mnS), and limm(T,) = m(T). (Recall that m(0) = O).) Also, S + T = im + j, = E (im +jm) S, = S1-+SS2i   Thus m(S + T) = m (S1) + m (S2) +...= lim, (m (SI)m(S9S2)+...+ m(S   S S)) =limnm(Si+SS2 +-... + S ... n) = limn (1 + ...+Sn) =limn m (Sn+ T) . Finally ST = n im , = ,jimj n =mmnn = kj = mn = k +k k2 +.. where the intervals kmn = kp are listed in sequential order by upper squares: (1,1), (1,2), (2,1), (2,2); .... Then m(ST)= rn(kl) + m (klk2) + .. . limn2 (m (kl)+... + mn (ki ... k2_lkn2)) = lim,n mk+... ... (kl + +k k _)lk 2) = lim m (k + m (SnTn).

Hence we obtain m 8 in general by taking limits of both sides of the finite relation.

5. Let U be an arbitrary subset of F and define the outer measure O(U) = glb(m(S); U c S c J), and the inner measure I(U) = I - O(U'). From m 6 we have for all subsets U, m 9. O <O(U)< 1, and O <I(U)< 1.

Moreover, if U1 c U2 , every S of J which contains U2 also contains U1, so the numbers m(S) defining O(U 2) form a subset of those defining O(U1), and hence m 10. If Ui c U2 , then O(U1) O0(U2 ) and I(UI) < I (U2).

For every Si D U, S 2 D U', SI, S 2, in J, we have S1+S 2 D U+U' = F and M (F) = 1 = m (S + S2) <m (S)+m(S2 ). Fix S1 U. Then 1 - rn (S) < m (S2 ) for all S2 D U', so 1 - m(S)<O()1 U') U')< m(SI) for all S, DU, and 1 - O(U')<O(U). Thus follows m 11. For every subset U, I(U)<O(U).

Now let {Un } be a sequence of arbitrary subsets Un of F. Fix e > 0. For every 7n there exists an Sn in J such that Sn D Un and n (S,) < O(U) +e/2n. Hence Sn D EU,, Sn is in J, and m(r Sn)<Em(Sn) <ZO(Un)+e. Thus O(EUn )<m(Sn,) < EO(Un) +e for every e > 0 and we have


90

m 12. For arbitrary subsets U, O(0 U)<0(U). Suppose U 1, U 2 are disjoint. For every S1DUl, S2 D U2, S1,S2 in J, we have Sl + S2 D U{+ U2 = (U1U2)' = 0 = so m (S + S2 )= 1. Also, (Ul +U2)' = UlU C S1 S2 is in J, hence O (U +U 2)'< gib (m(S1S2)). Then I (Ul + U2) - I (Ul)- I (U2) = 1 - O (U1 + U2)'- I - (U)- 1O(U2) = O(U{) + O(U2) -0(Ul + U2)' - 1 > glb m (S1) + glb m (S2)gib m (S1S2) -1 gib (m(S1) + m(S2) -m (SiS2 )) - = gib m (S1 + S2) - 1= 1 - 1 = 0. We therefore obtain m 13. UIU2 =0 implies I (Ul) + I(U2) < I (Ul + U2 ).

Generalizing this, we have I(ZU)> I(U1)+ I(E2 U) >I(U1)+ I (U) + (I Z 3U)> ... >I() +...+(UN) +I( EN+) > 1 I(U) for all N, and m 14. (I(U)<I(L U), for disjoint summands.

6. We say a set M is measurable in case I(M) = O(M) and denote by K the class of all measurable sets M. For a measurable set M we define a measure m(M) = I(M) = O(M). From m 9 follows m 15. For a measurable set M, 0 <m(M)< 1.

Let i be an interval. Since i is in J and contains itself, we have O(i)<m(i) since O(i) is a lower bound. Now suppose i c S E J. Then m(i)<m(S) and m(i)<O(i) since O(i) is a greatest lower bound. Hence rn(i) = O(i). Since i' is in J, we may write F = i+ jn, so m(F) = 1 = m(i) + m(i'). Now 1(i) = 1-O(i') = 1 - O(Ejn) > 1-E (O(j,)) 1 - Em(jn) 1 - m(i') = m(i) = O(i)>I(i), so we have established m 16. Every interval is measurable with O(i) = I(i) = m(i), its initially given measure.

Also, we see m 17. If Mn are disjoint measurable sets, then E M, is measurable and m(ZMn) = Emr(M,). For, Em(M.) = I (M,)<I( Mn) <O(M,) < 0O(M,)= Em (M,), and I(EMn,) = O(EM) = E (Mn).


91

As a corollary we get m 18. Every set S = i of J is measurable and its measure as such coincides with that previously defined. If M is measurable, I(M') = 1-O(M) = 1-I(M) = 1-(1-O(M')) O(M'), and so m 19. The complement of a measurable set is measurable and m(M) + m(M') = 1.

Finally , we have to prove m 20. A sum of measurable sets, disjoint or not, is measurable. Let M1, M 2 be measurable, and hence also M,, M2. Fix e > 0. Then there exist sets S1,S2, T1 ,T2 in J such that S1 DMl,S2 D M2 , T1D MI, T 2 D M2 and m(Si) < O(MI)+e; m(Ti) < 0(Ml)+e m (S2) < O(M2) + e; m (T2) < 0 (M2) + e.

Now S1 + TI D M1+ M' and S2+T 2 D M 2+ M2 so S1 +T = F = S2 + T2 . But 1 + m(SlTl) = m(Si + T1)+ mT m(iTi) = i(S 1) + m(Ti) < O(M1 ) + e + 0(Ml) + e =m(Mi) + m(M{) + 2e = 1 + 2e. Thus m(SiTl) < 2e and similarly m(S2T2) < 2e.

But M1 + M 2C S1 + S2 and (M1 + M2)' = Ml,M c TiT2, so F (M1 + M2) + (Mi + M2 )' c S1+ S2 + TiT2 . Moreover, from the first two inclusions, 0(M1+M 2) < m(S1 +S2 ) and I(M1+M 2) = 1-O(M +M2)' > 1-m(TiT2). So, 0(M1+ M2)-I(Mi + M 2)<m(Sl + S2)+m(TiT2)-1 = m(S1+S2+TlT2)+m( (S1 + S2)TiT2)-1 = m (F)+m( (S + S2) TT2)-1 = m(S1TiT2+ S2TIT2)<mi(STl + S2T2)<m(SiTi) + m(S2T2) <4e. Thus O(M1+M2) <I(M1+M2) and M1+M2 is measurable. Accordingly, so is every sum of a finite number of measurable sets.

But we see now that a sum of a countable number of measurable sets E M, = M1 +MM2-+ (Ml+ M2)'M3- ... is measurable by m 17 and the fact that each of the latter summands (M1+ . + Mn_l)'Mn (Ml+ ... +M,-i + M,)' is measurable by m 19 and the preliminary results for finite sums.


92

II—
The Set of Graphs

1. Consider t types of particles, such that a particle of type i may produce, upon transformation, an arbitrary number jl + .... + t > 0 of such particles, of which js are of type s, s = 1,...,t. We suppose that transformation times are the same for each type, and hence that generations may be counted unambiguously. We agree to consider zerogeneration as consisting of one particle of a fixed type i, and then consider the set Fi of all conceivable genealogies or histories proceeding from it, that is, the infinite record of the transformations of this particle and of all its progeny through all generations k = 0, 1, 2,...

2. We may represent such a genealogy in the plane by a graph or lattice if we agree on the following conventions: (a) A particle of type i in the k-th generation is represented by a number i in the k-th row.

(b) If a particle of type i in generation k is transformed into no particle, that is, if it dies in generation k + 1, this is so indicated by a sequence of zeros proceeding from it to the (k + 1)st and thence successively to all lower rows, thus: (i) row k I (0) row k + 1 (0) row k + 2 I * • * • * • (c) If a particle of type i in generation k is transformed into jl + .. jt > 0 particles, j, of type s, in the (k + 1)st generation, this is indicated by a branching from the corresponding number i in the k-th row into a group of jl + ... + jt numbers in row k + 1,js being the quantity of numbers s, identical numbers being grouped consecutively, and different numbers ranging from left to right in increasing order.


93

Thus (1) /\ (1) (1) (2) indicates that a particle of type I was transformed into two particles of type 1 and one particle of type 2. Note that the two 1's represent different particles, so that the events (1) and (1) (1) (1) (2) (1) (1) (2) I I I I I (0) (2) (0) (2) (0) (0) are counted as different.

Consideration shows that the set Fi of all genealogies is uniquely represented by the set of all such graphs z in the plane, and we speak hereafter of the set Fr of all graphs z. We will not change the type of the zero-generation ancestor during the subsequent discussion.

3. The set ri has at least the power of the continuum. For to every sequence of O's and l's {an}, we may make correspond a particular graph (there are many) which contains a total of one particle in generation n if a, is 0 and a total of two particles in generation n if an is 1. This correspondence is one-one on the set of all sequences {a(,} which has the power of the continuum to a subset of the set Fi. That the set ri has power less than or equal to that of the continuum may be seen directly or from a topological result which we wish to establish anyway in the next section. It will thus appear that Fi has power of the continuum.

4. If z is a graph, Zn denotes its upper segment from generation O through n, both inclusive. Thus, if z = z', then Zn = zn for all n, whereas, if z 5 z', there exists a first integer k = k(z,z') such that Zk / Zk. Since z0 = (i) for all graphs z of ri, the integer k(z, z') > 1.


94

5. Suppose z,z',z" are all different, where m = k(z,z')>n= k(z', z"). Then Z,n- =z'_l = Z_, and k(z, z") >n. Hence we have the

Lemma. If z, z', z" are three different graphs, then k(z, z")> min (k(z, z'), k(z, z")).

6. A graph z is said to terminate in case it contains no particles (only O's) in some generation. We can write the set T of all terminating graphs in the form of a disjoint sum T = ToT 1T 2 +...

where Tn is the set of all graphs yn which contain at least one particle in all generations through the n-th and die completely in generation n + 1. The set of To consists of the single graph (i) I (0) I (0)

We prove the Lemma. The sets T, T2 ,... are all countable and thus so is T.

Proof. Induct on n of T,. First, T, is countable, since it is in oneone correspondence with the countable set of all integer-component vectors (jl,...-,t), js> 0, Ejs > 0. Suppose Tn is countable. Every graph of Tn+ 1 is the continuation to one more "live" generation of the section yn of some yn of Tn. This serves to split Tn+1 into a countable (since Tn is) number of subsets S, all y"+l in a fixed S being continuations of the same yn of Tn to one more live generation n +1, followed by death. Now the n-th generation of yn contains only a finite number of particles each of which can branch into the (n + 1)st generation in only a countable number of ways. Hence each subset S is countable and so is Tn+l.


95

7. We developed in I an abstract theory of measure, which we are eventually to apply to the set Fi of graphs z. To this end we define intervals in Fi as follows. By an interval of order n(n = 0,1,...) is meant the set i(yn ) of all graphs z such that z, = yn, where yn is some terminating graph of Tn. Note that the interval of order 0 is Fi itself. By an interval we mean an interval of order n, or a single graph z, terminating or not, or the null set 0. Define J as the class of all sets S = i which are the sums of an at most countable number of intervals, just as in I. We now have to verify the axioms I 1, 2, 3.

8. We have in the present case the simple and unusual situation that, if i and j are intervals then they are either disjoint or one is contained in the other, hence ij = 0 or i or j and I 3 follows. For suppose ij 5 0 so that some z is in both. If i or j is a single graph it must be z itself and hence lies in the other interval.

Suppose then i = i(ym), j = i(qn), with m < n. Then y =- Zm = y. Let z' be in i(pn). Then z = Y m =Ym and z' is in i(ym). Thus i(ym) D i(yn). Moreover, we see that if m =n,i(ym) = i(yn).

9. Suppose S= E i(yn) + E z + E 0 is any sum of intervals where the i(yn ) are summed according to increasing n. Without altering the sum S we may successively (a) delete the 0 summands, (b) delete duplicate z's, (c) delete duplicate i(yy)'s, (d) delete z's contained in the remaining i(yn)'s, (e) delete every i(yn) which intersects a preceding i(ym) with m < n, since then the former is contained in the latter. The resulting summands are now disjoint with sum S, and we have I 1. Moreover, and unusually, the final summands are a subclass of those originally given.

10. We have to show now (I 2) that the complement of an interval is in J. (a) If i = 0, i' = ri = i(y). (b) If i = i(y ° ) = Fi, i' = 0, an interval by definition.


96

(c) If i = i(yn), where ny is in Tn and n > 1, we may write the disjoint countable sum n-1 ri= E yk + S i(yn) k=OykeTkyneTn

since every graph z either terminates at some generation less than or equal to n, or lives through generation n and is thus in some i(yn ) with y, in Tn. The complement of i(yn) is manifestly in J.

(d) If i = y-l, where n - 1 > 0, the above decomposition of ri shows that i' is in J.

(e) If i is a non-terminating graph z, define y" in Tn so yn = Zn, n = 0, 1,.... We claim that z = H1i("n). Clearly z is in every i(y"). Moreover if z' is in i(yn) for all n, then zn= yn = Zn and z' = z. It follows that z' = - (i(yn ))', the summands being in J by b,c. Hence z' is in J.

11. We saw in I that if S = ii + . + in then S' is in J. This may be false in our case for countable sums. For example, if T = E yn is the set of all terminating graphs, then T' is the set of all non-terminating graphs. The latter cannot be a sum of a countable or finite number of intervals, for if T' = i i(yn) + z, we have T' with power of the continuum, the z summands are at most countable, hence at least one i(yn) must occur in the T' sum. But then yn is in T', a contracdiction.

12. For use in IV we include the

Lemma. An interval of finite order cannot be expressed as a finite sum of two or more disjoint non-null intervals.

For suppose i("n) =i(ym) 4- z is such a finite sum. Let T be the set of all terminating yn+1 such that n+l = ". Of these there are countably many, all in i(fn). Since the z's above are finite in number, an infinite subset T of T must be in the i(ym); if such a yn+1 is in i(ym) we must have n + I > m since yn+l = ym and ym is alive in generation m. But since y"m is in i($n), we have also m >n. Moreover if m = n, i(yn) = i(ym) and we should have only one summand above. Hence m = n + 1 and yn+l = ym. So to each yn+l of the infinite set T


97

corresponds a summand i(y"). The correspondence being one-one a contradiction arises.

Corollary. If El in D j, where i,j are intervals then j is in some in.

If j is 0 or a single graph, this is trivial. Let j be an interval of finite order. Then j = j(Zin) = EN(jin), where jin is an interval. By the preceding result, all jin = 0 except one, so (say) j = jil c il.

13. Let i(yn ) be written as the disjoint sum i(gn) = yn+ .i(yn+l) where yn+l ranges over the set T of the preceding paragraph. Then if j is an interval properly contained in i(ny), it must be contained in one of the summands. We need only consider the case j = i(ym). Since ym is in i(yn),ym must be a continuation of yn, and since ym : yn,ym must be a continuation of some yn+1 of T. Thus ym is in some i(-n+1) and so is j.

14. If we are given an arbitrary finite class N of disjoint intervals i (ym) and yP, there exists a disjoint decomposition of Fi into such intervals among which appear all those of the given class N. First write ri = yo+i(y') (1) y'ET1

We leave unaltered all i(y') which occur in the class N. All others we decompose further thus: i(y') = y' Ei(y2 ) where y2 ranges over all graphs of T2 which are continuations of y', and substitute the results into (1). Again we retain all i(y2 ) occurring in N and decompose all other i(y 2 ) one more step as indicated. This procedure eventually obtains a disjoint sum of the desired sort including all i (ym) of N as summands. The yP of N, being disjoint from the given i (ym) must occur in one of the other intervals of the sum before us. Each such interval may be decomposed until the contained yP's are expressed as summands.


98

15. If Z i(yn ) D i(ym), then the latter is contained in one of the summands. For ym is some i(yn ) and hence, so is i(ym).

III—
The Space of Graphs

1. On ri we define a metric or distance function as follows: If z = z', d(z,z') = 0, whereas, if z - z', d(z,z') = l/k(z,z') where k(z,z') is the first integer k(> 1) for which zk # zk. It is clear that d satisfies the axioms for a metric:

(A) d(z,z')> 0, for if z = z', d = 0, while if z 5 z', d > 0. Hence also d(z, z') = 0 if and only if z = z'.

(B) d(z, z') =d(z', z) since k(z, z') is symmetrically defined.

(C) d(z, z")< max (d(z, z'), d(z', z"). If any two of the three graphs involved are equal, this inequality is trivial. If all three graphs are different, C follows from the lemma of II 5. This is indeed stronger than the customary triangle inequality: d(z, z") <d(z, z') + d(z', z").

2. If z and z' are graphs, the following are equivalent (a) d(z, z') < e. (b) z = z' or z - z' and k(z, z') > 1/e. (c) z = z' or z fz' and k(z, z')> [1/e] + 1,

where the notation [1/e] indicates the greatest integer in 1/e. (d) Zn = z' where n = [l/e].

To each graph z and real positive number e > 0 we assign the e-neighborhood Ne(z) of z, namely the set of all z' such that d(z, z') < 0. Thus Ne(z) consists of all graphs z' such that z4 = Zn where n = [l/e]. It is clear that if z' is in Ne(z) then Ne(z') = Ne(z).

3. A sequence of graphs {z() } converges to limit z in case d(z(n), z) 0, that is, for every e > 0 there exists an N such that for all n >N, z() coincides with z through generation [l/e].


99

4. The space Fi is complete in the sense that every sequence (z(n) such that d(z(n), z()) O 0 has a sequential limit z. For the given condition implies that for every n = 1, 2,... there is an N(n) increasing with n such that Zn = z,, m >N(n). From this one sees that the subsequence zN(n), = 1,2,... has the property zn() = z(n+P) and hence defines a graph z such that Zn,- zn which is the limit of the subsequence and hence of the original sequence.

5. Every Ne(z) is a closed set. For let z' = limz() where z() Ne(z). Then for n sufficiently large, z() coincides with z' through generation [1/e]. But z() is in Ne(z), hence coincides also with z through generation [l/e]. Thus z' coincides with z through [1/e] and is in Ne(z). Hence the space Fi is zero-dimensional, every neighborhood being both open and closed.4

6. The space ri is not compact. For example, the sequence consisting of an arbitary sequential ordering of the countable set of graphs y' or T 1 can have no convergent subsequence, since no two y' have the same section y'. For the same reason, no neighborhood Ne(z) of a graph z which is alive in generation [l/e] is compact, and therefore the space Fi is not even locally compact.

7. A space is said to satisfy the second axiom of countability in case there exists an at most countable set C of neighborhoods of the original system such that for every z and N,(z) there is a neighborhood N of the system C such that z e N C Ne(z). Our space Fi satisfies this axiom in the trivial sense that the whole set of original neighborhoods is itself countable. Consider an arbitrary Ne(z). If [1/e] = 0, then Ne(z) = Fi, and there is only one such neighborhood. If [1/e] = n> 1, clearly Ne(z) = N (z). In this case define a terminating graph x so that xn = Zn and x has only 0's in generation n + 1. Then N,(z) =N,(x), where x is in T. Since T is countable, so is the entire neighborhood system.

Note that it is not implied in the above that x is in Tn. If z is dead in generation n., x = z will be in some Tm with m <n, and Ne(z) will consist of z alone.

8. It is well known5 that a space satisfying the second axiom of countability has at most the power of the continuum. The argument


100

rests on assigning to every z the class of all neighborhoods in C which contain z. This is one-one (by the separation axiom) on Fi to some subsets of a countable set. The class of all subsets of a countable set has power of the continuum so the power of ri cannot exceed this. Combining with the opposite inequality obtained earlier, we see that ri has the power of the continuum.

9. A word may be said about the relation of intervals to neighborhoods. Every neighborhood is either an interval of finite order or a terminating graph, hence an interval. Every interval of order n is either ri = N (y°) (when n = 0) or a NL (yn) (when n> 1) hence a neighborhood. Every terminating graph is a neighborhood, e.g., yn = N i (y), but a non-terminating graph cannot be realized as a neighborhood, and of course, neither can the null-set.

IV—
Measure in the Space of Graphs

1. Whereas the notions of the set Fi, its intervals, and its topology are intrinsic in character, depending only on the number t of types of particles considered, we may establish a measure for intervals, and hence for the class of measurable sets in various ways. We are concerned at present only with the following procedure. As in I 3, we consider a fixed generating transformation G(x) of the unit cube It of t-space: gi(2x1. rXt) = Pl(i;jl,. i -.,jt)xjl ...xJ i= 1,...,t,

defining the probabilities of transmutation pl(i;j) of a particle of type i into jl+ ... + jt> 0 particles, js of type s,s = 1,..., ,t. Then every finite upper section Zn of a graph z of ri has an associated probability P(zn) that the event defined by Zn should occur.

For example, if G(x) is g 1(xI,X 2) =I + Ix1+1XlX2 4 4 1 100 92(Xl,X2) = 2 + 4X2 + iXlX2,


101

and zo = (1); zl =(l); 2 =(1) I / \ (2) (1) (2) l l (0) (2) we have p(zo) = 1,p(z1) = 0, and p(z2) = 1/4(1/2 1/4) = 1/32.

2. We assign a G-measure to intervals of Fi thus: (a) m(0)= 0, (b) m(z)= limp(zn), (c) m(i(y(n)) =p(yn).

Note that m(z) may be non-zero, for example for a terminating yn~, m(yr) = p(y±+i), and m(i(yn)) may be zero. Clearly ml, m2 of I are satisfied and it remains to prove m 3. This is non-classical because of the non-local compactness of the space ri and we divide the proof into a number of steps. Since m(0) = O, we have only to consider the case i(yn) = Zi(yn) + Z of a countable number of summands (see II 12).

3. First suppose i D jl + ...-j, the j's being disjoint and nonnull. Then m(i)> Em(j). Proof is by induction on s. If s = 1, we have the case i D j. If j has finite order, so does i and we write i(ym) D i(yn) where necessarily n >m. Then m(i(yn)) = p(yn) <p(yn) = p(ym) = m(i(ym)). If j is a graph z, the only case to consider is i = i(yT.) D z. Then m(z) = limp(zn)<p(Zm) = p(ym) = m(i(y"7)). Now suppose the theorem true for <s- 1 summands and consider i(yn) :DJi + ...+ is with s> 2. Write i(yn) = yn + Ei(yn+l), where m(i(y")) = m(yn) + m(i(yn+l1 )). Then since s > 2, each j is properly contained in i(yn) and is therefore in one of its summands. If not all j are in the same summand, we invoke the induction assumption and obtain the result. If all j are in the same summand i(yn+l ) we decompose it and repeat the argument. Eventually the j's must be split between two summands, since the intersection of a nest i(yn) D i(yn+l) D i(yn+2 ) D ... is a single point. Hence eventually we obtain


102

the result from the induction hypothesis and the fact that m(i(yn))>m(i(ynP)) = m (yn+P) + E m(i(yn+P+l)).

4. Hence we see that i = = j implies m(i) >m(j). The opposite inequality remains to be proved. Because of non-local compactness we need the lemma of the next section.

5. Lemma. For every e > 0 there exists a set Y of disjoint intervals i(y") such that (a) Em(i(yn)) < e, (b) Ce (i(y")) is closed and compact.

Denote by s, an arbitrary finite graph from generation 0 through n. Since 1 = Ep(sl) where si ranges over all finite graphs of order 1, we have Ep(si) < e/2 for all but a finite number N 1 of si. The intervals or order 1 corresponding to the former sl we throw into y.

Consider for each of the N 1 remaining sl all of its continuations s12. Then p(Sl) = -P(S12) and we have Ep(s12) < e/2 2 Ni for all but some finite number of s12. Collecting the former s12 for all s1 of the finite set, we have E p(S12) < e/22 . The corresponding intervals of order 2 we throw into y, and retain the remaining finite number of s12. We proceed in this way to obtain the set y with E m(i(y")) < e/2 + e/22 + ... = e, at each stage retaining a finite set of finite graphs s12...,. We see now the Ce is compact, since an infinite set of graphs z in Ce may be thrown into a finite number of disjoint classes according to the agreement of their segments z1 with the retained sl. At least one class must be infinite. The latter class is further subdivided into a finite number of subclasses according to z2, and so on. The process defines a graph z with segments sl, 12,S123, which is clearly a limit point of the given infinite set of z's. Thus Ce is compact. It is manifestly closed since it is a complement of an open set. (Recall that every interval of finite order is a neighborhood, hence an open set, and the sum of open sets is open).

6. We saw in 4 that if = Ej then rn(i)>]m(j). We have now to prove the opposite inequality. We do this first for the case where i = ri, that is, we suppose Fi = j, explicitly


103

ri = Ei(YT) + P Z(V)_j

the z",v = 1,2,... being non-terminating. Fix e > 0. Since m(z()) limn p(z,() ) and the latter sequence is monotone non-increasing in n, we can fix N(v) such that p(z(,)^)) < m(z(v)) +e/2". Define yN(v) so that it is in 7Tv() and N(v) = Z() Then m(i(yN(v))) = (N(V)) =p(z ) < YN(u) N (v)' rn(z(V)) + e/2" and z() is in i(yN(v)). For the given e > 0 we define the set Ce as in 5, and we have ce c ri c c Zi(ym) + -yP+ E i(yN(v)).

Now we saw in III 9, that every interval i(ym) of order m is a neighborhood of our space namely N1/mr(y"'), and every terminating graph yP is a neighborhood, namely N1/(p+l)(yP). Hence we have the closed compact set Ce covered by a countable class of open sets. A well known topological theorem tells us that Ce is covered by a finite sub-class of the original open sets, i.e., ce CEi(yi) + EYP + Ei(YN(v))

the primed sigmas indicating summation over a sub-class of the original summands. Moreover we know that every sum of intervals can be expressed as a disjoint suml of a subclass of the original intervals so that we have C, C cli(y) + Z'_yp+ti(yN(')). The latter sum we call S.

Since there are only a finite number of intervals in S, consisting exclusively of either intervals of finite order or terminating graphs, we may decompose Fr into a disjoint sum of such intervals, among which will be those of S (see II 14.): ri = S+E y-P+i(y-) and such that 1 = E) y m(i(+Ym))+ E m(yP)+Z r(i(yN(' )))+ Cl(yP)+m (i( yP)) .


104

Taking complements in the preceding inclusion we obtain Ce D S' that is, E i(y) D Pi(m) y

Now each summand on the right is contained in one on the left (II 15) and thus using the results of (5) and (4) e> m( i(y"))> E m(y) + m(i(m)) y = 1-(EZm(i(ym)) + m(yP) + E m(i(yN()))> 1-(Em((i(y )) + ETm(y P) + Em(i(yN('))))> 1-(,m(i(ym)) + E± m(yP)+ ± m(zV) + e) = 1-m ~ m(j)-e.

So, rm(j)> 1 - 2e for every e > 0 and m(j)> 1, as was to be proved. From (4) we therefore see that ri = 7 j implies 1 = m(j).

7. Finally, suppose i(y n ) = Ej. Then we may decompose Fi into a sum of disjoint intervals (see II 14) in two ways: Fi = i(yn) + k =>j+k. By (6) we know that 1 = m(i(yn)) + Zm(k) and also 1 = Em(j) + rm(k), so that m(i(yn)) = m(j). This completes the proof of property m 3 of I.

8. Hence we see that every generating transformation G defines a G-measure for intervals of Fi, and thus a measure for the additive class of measurable sets as indicated in I.


105

V—
m(T) = x[superscript(0)subscript(i)]

1. Let T be the set of all terminating graphs y. It is trivial that T is measurable since it may be regarded as the sum of its countably many points each of which is an interval. Now pk(i; 0) is the probability of death in the k-th generation and as such represents the sum of the measures of all graphs in the set To +... + Tk_l. It follows that m(T) = Yk=0yCETkrm(y) = limk Fy-Tk m(y) = limkpk(i;0) = I°. Thus we have

Theorem. The G-measure of the set T of all terminating graphs of Fi is x°, the i-th component of the death-fixed-point x° of G. Hence, in a subcritical system (x° = 1), almost all graphs terminate.

VI—
A Strong Ratio Theorem for Supercritical Systems

1. Let G be the generating transformation: gi(x) = Epi(i;j)xj for a supercritical system with first moment matrix M = [mij]. We recall that mij = (Ogi/Oxj)1 and the maximal positive characteristic root r of M is greater than unity, possessing a unique left characteristic vector v with positive components vi, and having norm llvll = 1.

By the e-cone Ce of the system (e > 0) is meant the vector j = 0 together with all vectors jsuch thatlij/a-vll < efor some positive a.

We proved in I 3, a weak ratio theorem to the effect that, for every e > 0, f > 0, there exists a K such that, for every k>K, E Pk(i;j) < f

2. We prove in this section a much stronger result. Consider the set of all graphs z of li. Let T be the set of all terminating graphs y of Fi. For an arbitrary graph z denote by j(zk) the vector j = (i,..,jt) whose component js equals the number of particles of type s in the k-th generation of z. Let L be the set of all non-terminating graphs z such that limk ray j(Zk) = ray v. Precisely, L consists of all nonterminating z such that, for every e > 0, there exists K such that, for all k>K, j(zk) is in Ce. Define N = Fr - (T + L). We thus have Fi=T+L+N


106

where N consists of all non-terminating z for which e > 0 exists so that for all K, there exists a k>K for which j(zk) is outside Ce. We may now state the

Strong Ratio Theorem (SRT). For a super-critical system, the set N of non-terminating graphs of Fr which do not approach the ray v is measurable and m(N) = 0. Hence L is measurable and m(L) = 1- x°.

The proof is difficult and we may proceed by means of lemmas 1-20.

Lemma 1. The set N may be decomposed into subsets: N = N1 + N2 + ... where Nn is the set of all non-terminating graphs such that for every K, there is a k>K such that j(Zk) is outside C 1/n.

Clearly every Nn is a subset of N. Moreover if z is in N, where, for every K there exists a k > K for which j(Zk) is outside Ce, then, defining n so that 1/n < ez, and noting that C/,, is in Cz, we see that z is in N.n

Lemma 2. To prove the SRT, it suffices to show that if Ne is the set of all non-terminating graphs such that for every K, a k>K exists for which i(zk) is outside Ce, then outer measure O(Ne) = 0.

For then O(N,) = 0 for every Nn of the decomposition of Lemma 1, and so O(N)< O(N,) = 0, whence N is measurable and m(N) = 0.

We must now adopt some notations: Let gf(x) = EpK(i;j)x' ... xj. Then g ) = K(g,..,g = P(i; j)g gt _ pK(; j)EPj (Jl) x' .. xt and so on. Generally, (X)EPK(i; j)Epj(j) ... Pj-1 (jS)xj ...Xt jjljs

Lemma 3. Let Ne be given as in Lemma 2. To prove O(Ne) = 0, it suffices to show that, for every f > 0 there exists a K such that E PK(i;j) + Pk(i; j) pj(jl) + iJCe iOo j i iC a C, pK(i;j) pj(jl))Pj (j 2 ) + ...< f j3oj30oj 2 Ce JECe jlec,


107

For, let Ne be fixed, and fix f > 0. Then, assuming such a K exists, we have for this K that every z in Ne has z(jk) not in Ce for some first k >K. Define yk in Tk so yk = Zk. Then z e i(yk). But the above sum is the sum of all m(i(yk)) for all yk so defined. Hence O(N0) <f for every f > 0, and so O(Ne) = 0.

It is the condition of Lemma 3 which makes clear the relation of the SRT with the weaker form.

Lemma 4. To prove m(Ne) = 0, it suffices to show that, for every f there is a K such that for all s> 1, SK,, pK(i;j) +YpK(i;j) E Pj(jl)+ ...+ jffCejoj1 jCe PK(i; j) E pj(jl) * ~ pjs_~ (js)<fj3ojl ?OjsCc iECe jlECe

Now, setting x = 1 in the form obtained for gK+s(), we see that 1 =pK(i; O) + E P(i;j) + E PK(i;j)>= gi (C), we s e e that pK(i; O)+ pK(i;j)+ E K(i;j) E p(jl)+ jce .-(J j C) E K(i;j) E P(jl) >... >pK(i;O)+ SK,s+ j3ojl1o j7Ce jl Ce pK(i;j) E Pj(jl)... E pj-l(jS) jio j I o js o jECe j eC-e jsECe

The latter expression we denote by IK,S.

Lemma 5. To prove O(Ne) = 0, it suffices to show that, for every f > 0 there exists a K such that, for all s> 1, IK,s > 1 -pK(i; 0) - f

For then Sk,s<1-pK(i;O)-IK,S< 1-pK(i;0)-(1-p K(i; )--f) = f.

We must now consider more closely than we have done hitherto the transformations T(n) = nM/s(nM) and S(n) = nM/((nMII, each of


108

which we regard as operating on the set of non-null vectors with nonnegative components. One sees easily that the k-th iterates are given by Tk(n) = nMk/s(nMk) and Sk(n) = nMk/lInMkll. We have already denoted by v the characteristic vector of norm 1, for which vM = rv, and for our present purposes we let v = v/s(v) so that s(v) = 1, and v)M = rv. Clearly Tk(v) = v and Sk(v) = v. The transformation T(n) is a mapping onto the plane s(x) = 1,S(n) is onto the sphere llxll = 1. Clearly Sk(n)/s(Sk(n)) = Tk(n) while Tk(n)/IITk(n)lI = Sk(n). We first note some trivial relations.

Lemma 6. If j has non-negative components, then llll <s(j) For ljl2 =jEj (EJ)2S 2 j)

Lemma 7. If j is an arbitrary vector, then lljll >ls(j)l/t>s(j)t. For lljll = ( j2)2 > l l, m = 1,...t, and tlljll > E IJm I > I I Is(j)l > s(j).

Lemma 8. If x and y are arbitrary vectors, ( xiyi)2 < 11xll2 I11y2 . This is the well-known Schwarz inequality.2

Lemma 9. If x is an arbitrary vector, then llxMjl<IxlIl(Eij mi .)2 --X IIXi M. 2 2 For, [ [xMII2 = Ej(Eiximij)2 < EjEiXi iT Ij- II22 We have used the Schwarz inequality here.

Lemma 10. If n is a vector with non-negative components, then \lnMll> llnll( min Ej m'2.) 2 -= \nlla.l For IInM2 = Ej (Einimij)2 >Er_jEii = Ein E,m >Ei min Ej m = lin 112. .

We have now the means of establishing the existence of a Lipschitz constant for the transformation S(n).


109

Lemma 11. There exists a constant L > 1 such that IlS(n) - S(n')ll<Llln-n'll for all vectors n, n' which are non-null and have non-negative components, lln'll being unity.

For IIS(n) - S(n')ll = \lnM/lInMil - n'M/Iln'MIIll<nM/InMI\nM - nM/II II llnMIIn'Mlll + IMnMIIIn'M -n'M/ln'M = 1l/l1nMIl - 1/lln'Mlll · IlnMII + lInM - n'Mil/lln'Mi = \llnMIJ - lln'MI\I/ln'MII + IlnM - n'Mll/lln'MII<2))(n - n')MIll/ln'MIJ< 2arlln - n'll/lln'llai, by Lemmas 9, 10. Now Iln'll = 1. Hence L - 2a/a1 serves.

Lemma 12. If n and n' are non-null, non-negative component vectors and lin'll = 1, then llSk(n)-Sk(n')l<LIln - n'll, k = 1,2,.... For JlS2 (n)-S2 (n')ll < LIIS(n)-S(n')l<L2l\n-n'll, and so on. Note that IISk(n')ll = 1.

The transformation T(n) has topological and algebraic advantages since its denominator is a linear functional (see I 3). However S(n) has simplicity from the point of view of norm inequalities. We work with whichever seems more adaptable to the current purpose. The following two lemmas give inequalities connecting the two operators.

Lemma 13. Let j and k be vectors with non-negative components and having s(j) = 1= s(k). Define j' = j/lljll and k' = k/llkll as their projections on the unit sphere. Then lil' - k'Il <2tllj - kJl.

For l--k'll - llJ/lIJi - lk/\\jll\\<J/llJIl -J/llkllll+lJ/llkll - k/llki\i = il/llJll - I/llkli) llJ ll + llJ - kl\/lIkll = llJlll- llkll/llkll + 11i - k\ll/kl < 21]j - kll/llkll <2tllj - kll/s(k) = 2tllj - kll. Here we have used Lemma 7.

Lemma 14. Let j' and k' be vectors with non-negative components and 1li'll = 1 = 1lk'1l. Define j = j'/s(j'), k = k'/s(k'), their projections on the unit plane s(x) = 1. Then llj - kll<(t + 1)flj' - k'll.

For llj-kll = lj'/s(j') - k'/s(k')|<\\j'/s(j') - j'/s(k')ll + llj'/s(k')- k'/s(k')\\ = Il/s(j') - 1/s(k')l I '11/1 + lli'11 + Ii'-k'll/s(k') = Is(j') - s(k') /s(j')s(k') + iJ' - k'll/s(k') = s(j'-k') /s(j')s(k') + llj' - k'll/s(k') But s(k')> Ilk'll = 1, s(j')> Ill'll = 1 by Lemma 6, and Is(j' - k')<tllj' - k'll, by Lemma 7.


110

Lemma 15. For every e > 0 there exists a K such that for all k>K and all non-null, non-negative component vectors n, lSk(n)-v- < .

We saw in 1 3, that for e/2t > 0 there exists a K such that for all k > K and all non-null non-negative component vectors n, IITk(n)-—vI < e/2t. Referring to Lemma 13, we see that Tk(n) and v are on the plane s(x) = 1, and are vectors with non-negative components. Moreover Sk(n) = Tk(n)/llTk(n)ll and v = v/ivill. Hence I{Sk(n)- vil<2tllTk(n)vl < e.

Thus the sequence of the transformations Sk(n) is uniformly convergent to v.

We saw in Lemma 11 that IIS(n) - S(n')\\ <Llin - n'll where L > 1. Examples show that S(n) need not be a contraction in the sense that the above relation holds for some L < 1. We can however show that there exists an iterate Sq(n) which is a contraction toward v. It seems simpler first to establish the analogous result for T(n).

We recall that the simplex {, . .., t} means the set of all vectors n = nij6 i , ni > 0, nrii = 1, that is, all vectors n = (nl,...,nt) with non-negative components and s(n) = 1. By the boundary of the simplex we mean all of its points having at least one component zero. Since vM = rv, s(v) = 1, and M has all elements positive, v can have no component zero and is therefore not a boundary point. One sees therefore that there is a minimum distance D > 0 from v to the boundary of the simplex {1, ..., t }.

Lemma 16. For every f > 0 there exists a Q such that for all q >Q, \\Tq(n) -v\< flln-vll for all vectors n with non-negative components and having s(n) = 1.

Proof. Let V = maxvi/minvii > 1. Let D = min {Ilb-vl} > 0 where b ranges over the boundary of the simplex {6, .. ., f}.Iff be given, we know that for the positive constant fD/Vt there exists a Q such that for all q > Q, TTq(n) - vI < fD/Vt for all non-zero n with non-negative components.


111

Now let n v be an arbitrary such vector with s(n) = 1. The halfray v + a(n - ), a > 0, cuts the boundary of the simplex {, . .., t} in a unique point b, and n may thus be written n= hv+kb,h>O, k>0, h+k=l1.

Thus for q>Q, \\Tq(n)- vIl - \\nMq/s(nMq ) - v1 = IlhivM + kbMq/hs(vMq) + ks(bMq) - v = hrqv+ kb hr + ks(bMq) - I = k IbMq - s(bMq)v I/hrq + ks(bMq ) = ks(bMq) I Tq(b) - v\l/hrq + ks(bMq ) <ks(bMq)fj[b - v\l/Vt(hrq + ks(bMq)) = fllkb - kOvl/Vt(hrq/s(bMq ) + k).

Now (lkb-kIvI = Ilkb-(l-h)vl( = (hv +kb-vll = Iln-vll. Also, note that min i )i miq < Ei viimq = rqvj< rq maxv, and hence Ei (mq)2 < (Ei mi)2 < r2qV2 and (E (r.j)2 ) < rqV. Thus s(bM) = j i bimt < E Ilbll(i (mEij)1) ) Ej (Ei (m )2) 2 <trqV.

Hence hrq/s(bMq)+k>h/tV+k = 1-k+ktV/tV = l+k(tV-l)/tV>l/tV. Thus we see that [[Tq(n) - v\I<flln - vIl.

Lemma 17. For every e > 0, there exists a Q such that for all q>Q, \ISq(n')-v\l<elln' -vll, for all n having non-negative components and lin'll = 1.

Fix e > 0. Define f = e/2t(t + 1). Then by Lemma 16, Q exists so that for all q>Q, ITq(n) - vll<elln - vl\/2t(t + 1) for all n with non-negative components and s(n) = 1.

For arbitrary n' with Iln'll = 1 and non-negative components, define n = n'/s(n'). Then we have \Sq(n')-v\\<2tllTq(n')-vl<2t\lTq(n)-vl<2telln-v\ll/2t(t+1) <e(t+l)lln'-vll/t+1 = elln'-vll. We have used Lemmas 13, 14, and the fact that Tq(n') = n'Mq/s(n'Mq) = nMq/s(nMq) = Tq(n).

Just as the possible failure of S(n) to contract all vectors toward v forced us to prove Lemma 17, so does the possible failure of the


112

transformation nM to increase the norm of n cause difficulties for which we must provide in the next two lemmas.

Lemma 18. There exists a constant e > 0 such that for all vectors n satisfying Iln-vll < e, one has lInMII > lln11(l+r)/2 = mllnll, 1 < m < r.

For the function R(x) _ IlxMll/llxl( is continuous at x = v and R(v) = r > 1. Thus for m = (1 + r)/2 < r there exists an e > 0 such that ln - vll < e implies R(x)>m.

Lemma 19. There exists a K such that for all k > K, UnMkI> lnll for all n, with non-negative components.

Note that if w is the right characteristic root of M, with s(w) = 1, Mkw = rkw, we have max w >j mk > _jmk.wj = rkwi > rk minw so Ej mrj > rkW where W =minw/max w. Now |nMk l > s(nMk)/t= Eij nimk/t= Eini Ejm /t > rkWs(n)/t > rkWlInIlt. Take K so rKW/t > 1.

By virtue of Lemma 5, it now remains to prove the final lemma for which we have prepared all the essential tools.

Lemma 20. Let e > 0, f > 0 be fixed. Then there is a K such that, for all s > 1, E pK(i;j), P,(jl) E Pj- (jS)> 1 -pK(i;O) - f. jio jlio js»oji-Cejl Ce jS Ce

Our proof is based upon a complicated construction of K which was, of course, obtained by looking from the other end. In spite of its glaring artificiality we give the direct route:

1. By Lemma 18, we fix e so that 0 < e < e and lln - vll < e implies }lnMl >mrllnll where m = (1 + r)/2 > 1.

2. By Lemma 17, there exists a q such that $qSq(n')-vll < ln'-v11/4 for all non-negative n' with Iln'll = 1. We determine an e satisfying the following conditions: a. 0 < 5 < e < e, and e < 1. b. 5 Lq- l < e/2, that is e < e/2Lq- 1 where L is the Lipschitz constant of Lemma 11, and q is the constant just defined.


113

3. Fix E > 0 so that a. E(1+LL2 +...+ Lq- 1)</2, b. m(1 - E) > 1, that is E < (m - 1)/m < 1. Note that we now have automatically, for all s<q, E(1 + L + L2 + ...+ Ls-2) + e Ls-'<E(1 + L + L2 +... + Lq-2) + 5 Lq-1 < e/2 + e/2 < e/2 + e/2 = .

4. Fix k so that a. $Sk((n)- vI < e /2 for all non-negative n / 0 (see Lemma 15). b. [InMkfl> Ilnll, for all non-negative n. (see Lemma 19).

5. We define dk = Ej( Ei (dik) ) , dI being the dispersion of gk with respect to xj, and define rnk = (minEj (mi)2)½ .

We now fix A > 0 so a. 4dk/ 2emjA < f/4. b. dl/E2 m2(1- e )A < 1. c. dim(l - E)/E2 m2(1 - e )A(m(1 - E) - 1) < f/2.

6. Fix r so that pr(i; n) < f/4, see I 3. O<llnll<A

7. Fix K = r + k. We contend that this K satisfies the condition of the lemma. First note that gK(x) = EpK(i;j)x1 ... = gr (Gk(x)) = pr(i; n) Pk,n(j)xl .. .xt, where (gk) 1 ... (gtk)l = E Pk,n(j)xl ...xt by definition. Setting x = 1, we may write 1 = pr(i; 0) + pr(i;n) Pk,n(j) + O<llnll<A j pr(i; n) E Pk,n(j) + pr(i; n) E Pk,n(j) Ilnl>A llj/llnMklJJ-vIl<


114

Now just as in I 3, we see that, for arbitrary R > 0, Z Pk, (j)R2 < Pk,n(j)j -nMk11 = Znidj|j-NMk|>R ij lln ( (d4) ) 2 = -nlldk. J 2 Thus, Pk,(j)< llnlldk/R2 . Ilj-nMkl|>R Setting R = (InMkIe /2, we have 5 Pk,n(j)<411nldk/ e2 (lnMkl12 < 4(1nldk/ ( 11nl2m2k = Uj/ll|nMkIl-JSk(n)l> e /2 4dk/ 2m -lllnl, where mk = min ( n (m) )) (see Lemma 10).

However, if 11j/llnMkll - v||> then j is on the preceding range, for if not, \\j/llnMkl| - Sk(n) | < /2 and \Sk (n) -v | < 5 /2 by choice of k, whence 1ij/lJnMkJ1 - v|l< e, a contraction. Hence 5 Pk,n(j)< 4dk/2 mllInll. |ljlln/fMllk-vll> e Thus E pr(i;n)Pk,n(j) < pr(i; n) 4dk/ e 2m2A < Iln\l>A Ij/1\nMkll-v\I>e nll>A (f/4) E pr(i;n)<f/4. IlnII>A But by choice of r E pr(i; n)Pk,n(j)= p(i;n)<f/4. O<llnHJ<A j O<llnll<A

And, as always, pr(i; 0)< pr+k(i; 0). Thus we obtain from the original equation that Pr,(i; n).Pk,n(j) >1-pr+k(i;0) - f. nl>Aj/nMk-v< e


115

Every vector j involved on the range above has the property that ji/a - vii < 5 for some a > A, for lInMklI> llnll > A by choice of k. Thus Z pK(i;j)>1-PK(i; 0)-f lIj/a-v\l< e a>A Since 1lv l = 1 > e by choice of e, j = 0 is not on this range.

Note the two trivial remarks:

A. If llaj' - vii < e, a > 0, i'll = 1, then lij' - vll < 2e. For e > llaj' - vii > laj'll - ilvll l = a - 11, and lij' - vll = lij' - Jai' + Ilaj' - vii = I1 - al llj'll + e < 2e.

B. Corollary. If lij/a - vll < e and j' = j/lljll then (lj' - vll < 2e. Consider now the product pK(i; j) Pi(jl)  Pjl(j) { \\j/a-v\\< e \\j1\\jMj-Sll(j)\<E\\jj/\\jjMjl-S(j,)\\<E a>A E p_j (jq-l) pE _Pq- (j) *- (*) \3jq-1lj~jq-2M\\-S(jq-2) ||<E || j"/\j"-1M\\-S(j"-) ||<E

Since e < 1, E < 1, and Ilvli =1 = Sll(j)ll[ , we see that no j or ji is ever zero on these ranges. Applying Lemma 12 we find that lljq/lljMq-IM_-S(jq-l) I< E, S(jq)-S2 (j -) I< LE, 11(jq-)S3 (jq-3) < L E ... Ilsq-2 (j2)_- sq-l (j)l) 11 < Lq-2E \Sq-l(jl) Sq(j)\\ < Lq-'E, and hence ljq/lljq-lMI - _Sq(j)ll <E(1 + L + ... + Lq- l)


116

But since IISq(j/(ljl)- vl < /jlJljl - vIl/4 < 2 /4 <-/2 (see remark B and definition of q) we have|jq/lljq-MII- v|l< E(1 + L + .. + Lq- l) + /2 < /2 + /2 = 5. (see definition of E). Similarly we shall find, working from 2q to q, that llj2q/llj2q-lM -vl\ < 5 and so on for all multiples of q. Note also, for s<q, Ijs-/lljS-2Mi - S(jS-2) II < E S(js- -) - S2(j-3 ) l < EL... SS-2(jl) - Ss-l(j)I < ELS-2 \S`-l(j) -v\ <eL-1 , so lljs-1 lIj~-2MI - v\\ < E(1 + L + ... + L-2 ) + t LS-l <

(see definition of E). Similarly all jnq+r on the non-q-multiple postions are in Ce. It is clear now that the ranges for j, j,.. .are all in Ce c Ce and exclude zero. Hence the product of Lemma 20 is greater than or equal to that of (*) carried to the corresponding place.

Now note the elementary result that if l j/a-k 1 < eo where IlkI = 1, we have a - lljll = Ilakll -lljll<1ljlll - Ilak]ll<llj - akll < aeo and hence ll > a(1 - eo).

We have seen that, on the ranges involved in the (*) product, all j and js are in Ce, indeed \lj/a - vll < 5 < e, and jI/lljs-1 Mll - vll < e, all s. By choice of e, ll(j/a)MIl> mllj/all and II(js/lljS-Mll)MII>ml (js/lljs-lMll) 11. But then lljMll >mlljll and \ljsM\\> m\jsll. Thus we see that

lij/a - vll < 5 implies 11jll > a(1 -e ) > A)(1 - ). llj/(jMll - S(j)| < E implies jllj> lljMll(l - E)>m(1 - E)jllj > m(l - E)A(1 - 5), 1j2 /llj1 Mll - S(j)11 < E implies fij2 >jMll (1 - E)>m(l - E)[ jl | > m2 (1 - E)2 A(1 - ),..., js/ij-l'MIJl-S(j'-)1l < E implies ljs >m"(1 - E)8 A( - ).

Letting C = A(1 - ) and R =m(1 - E) > 1 by choice of E, we have on the (*) ranges, llill > C, ljjll > CR, lij21 > CR2 ... ljs-l > CRs-.


117

Now regard the distribution defined by g .g.. t=Pj-l, (j")xxl . .. . We see as before, for arbitrary n > 0, E P,_l(js) N2 < P(jjs)I-2 -J- E j-ldl < JJjs-js-1MJ(>VNIv Jj-1. dl, and hence 1 Pj-_(js) 1- IIs-1lld1/ .N2 lljl-j»-lMl)<N

Setting N = Ijj -1MII E for all s>1 EPP- (is) > 1 - lj-ll dl/E2lljs-lMj2 > 1- Ij1-dl 1/E2 Iij-11 2 . m l = 1 - di/E2 m llj~l I. Beginning at the last (s)-th term, we have S Pjs- (js)> 1 - di/E2 m2CR-1 > 0 Pj.s-2(jS- 1) > 1 - di/E2 m2CR-2 > 0 1IjS-1 /1jS- 2MII- (js-2) II<E 5 P (j')> 1-d/E2 mC > . 11|/11j11jM-S(j)11<E

Note that d1/E2 m\2CRi < d1/E2 m2C =di/E2 m2(1- 5)A< 1 by choice of A. Hence the (*) product through s factors is greater than or equal to (1-pK(i; 0)-f/2) (1-di/E2 m2C) (1-di/E2 m2CR) ... (1-di/E2 m2CRS-1).

It is trivially proved by induction that if all pi and 1 -pi are positive, then (1-pl)(l-p2) ... (1-pn)>1 -p-p2 -.-Pn,. Hence the preceding product is greater than or equal to


118

- pK(i; 0) - f/2 - (di/E2 m2C) (1 + 1/R + /R2 + . .. + 1/R-1 ) > 1 - pK(i; 0) - f/2 - di/E2 mC(1 - 1/R) = 1 - pK(i; O) -f/2 - diR/E2m2C(R - 1) -pK(i; 0) - f/2- m( - )/ - - E/ )A(m(1 - E)- 1) > 1 - pK(i; 0) - f/2 - f/2 = 1 - pk(i; 0)- f, by choice of A.Q.E.D.

VII—
Remarks On Systems below Critical

1. For a subcritical system (x° = 1), we have seen in V that m(T) = x = 1 so that m(T') = 0, and since N c T', O(N)<O(T') = m(T') = 0. Thus, in such a system, it is trivial that m(N) = 0. Similarly L C T' and m(L) = 0 = 1- x°. Therefore the SRT is self-evident for subcritical systems.

References

I

1. P. Alexandroff, H. Hopf, Topologie, Berlin, 1935 2. G. Birkhoff, Lattice Theory, Am. Math. Soc. Colloq. Publ. XXV, New York, 1940. 3. D. Hawkins, S. Ulam, Theory of Multiplicative Processes, see Chapter 1. 4. H. Margenau, G. M. Murphy, Mathematics of Physics and Chemistry, Van Nostrand, 1943.

II

1. C. J. Everett, S. Ulam, Multiplicative Systems in Several Variables, I, (LA 693) see Part I. 2. D. Hawkins, S. Ulam, Theory of Multiplicative Processes, see Chapter 1.


119

III

1. H. Cramer, Mathematical Methods of Statistics, Princeton University Press, 1946.

2. C. J. Everett and J. R. Ryser, The Gram Matrix and Hadamard Theorem, Am. Math. Monthly, LIII, 1946.

3. C. J. Everett, S. Ulam, Multiplicative Systems in Several Variables, I and II.

4. W. Hurewicz and H. Wallman, Dimension Theory, Princeton University Press, 1941.

5. W. Sierpinski, Introduction to General Topology, University of Toronto Press, 1934.


121

previous sub-section
3— Multiplicative Systems in Several Variables I, II, III: With C.J. Everett (LA-683, June 7, 1948) (LA-690, June 11, 1948) (LA-707, October 28, 1948)
next chapter