THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Interim Engineering Report COMBINATORIAL PROBLEMS IN BOOLEAN ALGEBRAS AND APPLICATIONS TO THE THEORY OF SWITCHING Michael A. Harrison ORA Project 04879 under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT: NO. AF 33(657) -7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR June 1963

This report was also a dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in The University of Michigan, 1963.

TABLE OF CONTENTS Page LIST OF TABLES............................ iv LIST OF ILLUSTRATIONS..........................vii LIST OF APPENDICES........................... viii ABSTRACT................................ ix CHAPTER I. INTRODUCTION AND HISTORY...........1 1 II. MATHEMATICAL BACKGROUND.................... 4 III. SWITCHING FUNCTIONS AND PERMUTATION GROUPS...........30 IV. EXTENTIONS OF EQUIVALENCE OF BOOLEAN FUNCTIONS.......... 73 V. APPLICATIONS................ o...108 VI. UNSOLVED PROBLEMS................... 127 APPENDICES............................... 129 BIBLIOGRAPHY.......................... o o 139 iii

LIST OF TABLES Table Page I. Operations on Permutation Groups.............. 29 II. The Number of Classes of Functions with k Atoms Under n. 40 III. The Total Number of Classes Under f............ 49 IV. The Number of Classes of Functions with k Atoms Under n. 49 V. The Total Number of Classes Under n............ 59 VI. The Number of Classes of Functions with k Atoms Under 59 VII. Table of Irreducible Polynomials Over Z.......... 62 VIII. Values of I and t.................... n n IX. The Total Number of Classes Under GL (Z)..........66 n2 X. The Number of Classes of Functions with k Atoms Under GL (Z )......................... 66 XI. The Total Number of Classes Under Ln (Z2)......... 71 XII. The Number of Classes of Functions with k Atoms Under 17n(Z2)................ 71 XIII. Number of Classes Under Groups Containing Negation..... 76 XIV. Number of Classes of Self-complementary Functions...... 78 XV. The Number of Classes of Networks Under n......85 XVI. The Number of Classes of Networks Under 8.........85 XVII. The Number of Classes of Networks Under On.....86 n XVIII. The Number of Classes of Networks Under GLn(Z2).......86 XIX. The Number of Classes of Networks Under ln(Z2)..... 87 XX. The Number of Classes of Networks with non the Inputs and \k on the Outputs.........88 XXI. The Number of Networks with n on the Inputs and fk on the Outputs..88 iv

LIST OF TABLES (CONT'D) Table Page XXII. The Number of Networks with 0, on the Inputs and k on the Outputs.......... 89 XXIII. The Number of Networks with GL (Z ) on the Inputs and 4k on the Outputs............ 89 XXIV. The Number of Networks with on(Z2) on the Inputs and on the Outputs................... 90 XXV. The Number of Networks with n on the Inputs and t2 on the Outputs.................92 XXVI. The Number of Networks with n on the Inputs and k2 on the Outputs...........92 XXVII. The Number of Networks with n on the Inputs and. on the Outputs.....................93 XXVIII. The Number of Networks with GL (Z2) on the Inputs and [2 on the Outputs.................. 93 r, on the Outputs.. n 94 XXX. The Number of Networks with) on the Inputs and Ok on the Outputs.................. 95 XXXI. The Number of Networks with C2 on the Inputs and 0k on the Outputs. 95 XXXII. The Number of Networks with Jn on the Inputs and 0k on the Outputs... n.......... 96 XXXIII. The Number of Networks with GL (Z ) on the Inputs and (k on the Outputs........... 96 XXXIV. The Number of Networks with GL (Z2) on the Inputs and (k on the Outputs........ 97 XXXV. The Number of Networks with -n on the Inputs and GLk(Z2) on the Outputs.......... 98 XXXVI. The Number of Networks with (Z on the Inputs and XXXVII. The Number of Networks with 2 on the Inputs and GLk(Z2) on the Outputs......... 99 GT,(Z ) on the Outpu ts....... -9- -

LIST OF TABLES (CONT'D) Table Page XXXVIII. The Number of Networks with GL (Z2) on the Inputs and GLk(Z2) on the Outputs................99 XXXIX. The Number of Networks with 0 (Z2) on the Inputs and GLk(Z2) on the Outputs............. 100 2100 XL. The Number of Networks with on the Inputs and Otk(Z2) on the Outputs.............. 100 XLI. The Number of Networks with 2 on the Inputs and tk (Z2) on the Outputs.............101 XLII. The Number of Networks with 0n on the Inputs and Ik (Z2) on the Outputs. v...... 101 XLIII. The Number of Networks with GL(Z 2) on the Inputs and lk (Z2) on the Outputs........................ 102 XLIV. The Number of Networks with G (Z ) on the Inputs and -k(Z2) on the Outputs.... 102 XLV. The Number of Invertible Functions. 105 XLVI. The Number of Classes of Invertible Functions with the Same Group on Both the Domain and Range...... 105 XLVII. The Number of Classes of Invertible Functions with Different Groups on the Domain and Range....... 106 XLVIII. The Number of Classes of Post Functions Under the Symmetric Group.............. 119 XLVIX. The Properties of................. 136 vi

LIST OF ILLUSTRATIONS Figure Page I. Two networks which are equivalent under...... 5 II. Two networks which are equivalent under 3......... 41 III. The lattice of interesting subgroups of ~n(Z2).......72 IV. A generic (n,k) network................... 81 V. The effect of a = (2,3) on a (3,4) network.........82 VI. The absolutely minimal network for Xx2x3 + x2x3......109 vii

LIST OF APPENDICES Appendix Page I. CYCLE INDEX POLYNOMIALS FOR.............. 129 II. CYCLE:INDEX POLYNOMIALS FOR n''' 130 III. CYCLE INDEX POLYNOMIALS FOR GL (Z2)............ 131 IV. CYCLE INDEX POLYNOMIALS FOR 3n (Z2)''... 15 V. HARARY'S DEFINITION OF THE EXPONENTIATION GROUP... 135 VI. DERIVATION OF THEOREM 2.24................ 137 viii

ABSTRACT In recent years, the techniques of enumerative combinatorial analysis have been applied to Boolean algebras. It was Polya who first showed that a natural group classifies Boolean functions into symmetry types. Thereafter, Shannon described how these symmetry types can be used in the theory of switching. In this thesis, some new permutation groups on Boolean functions will be considered. The reasons for selecting these groups come from the motivations of switching theory. In each case, the cycle index, a multi-variate generating function for the cycle structure of the group is derived. An approach to combinatorial analysis which is capable of generalization is adopted in the presentation. In particular, it is the representation of a group as a permutation group (not as an abstract group) which determines the combinatorial properties of the group. The need for a structural theory of permutation groups is demonstrated and some results obtained. It is necessary for the purposes of combinatorial analysis to be able to decompose a group into suitable constituents and to construct the cycle index of the group in terms of the cycle indices of the component groups. The cycle indices derived for the new groups provide new classification results for Boolean functions. The recent theorems of DeBruijn are applied to obtain refined results and to enumerate various new objects such as invertible Boolean functions, networks, and self-complementary classes of functions. Finally, generalizations to Post algebras and other systems of interest are indicated in the paper. ix

CHAPTER I INTRODUCTION AND HISTORY 1-1 Preliminaries One of the basic characteristics of many areas of communication sciences is the finiteness of the objects under consideration. While finiteness of the object set sometimes results in easily derived decision procedures, many of the solutions to the problems of communication sciences arise as algorithms which are not "efficiently" computable. Even though the domain of the objects of interest may be finite, further structure and classification theorems need to be developed to facilitate computations in a practical sense. This thesis represents an approach to the solution of some of these problems. The motivation for studying these problems came from switching theory, and the presentation is made in a general way so that applications to other areas of interest may be made. 1-2 History [20o] Felix Klein characterized the fundamental problem of mathematics as that of finding the classification of systems under appropriate groups. This approach to group theory is now somewhat obscured by the abstract approach to mathematics, but the idea is that a group acting on a set of objects is, in some sense, a measure of the symmetry of the objects. The structure of the set may also be studied by examining the group. It is interesting to note that Klein's program has been carried out for certain kinds of geometries and also for logic[2. A further account of Klein's program may be found in reference 1

2 In 1937, Polya published a paper in which a fundamental theorem on enumeration was proved[3.. If there is any single paper of outstanding importance in combinatorial analysis, it is Polya's 100-page document. Some generalizations of Polya's work were given in 1959 by DeBruijn[7]. The results of both authors, suitably modified for Boolean functions, will be used in this paper. In 1941, Polya published a paper on the applications of his enumeration theorem to propositional functions While Polya could not solve the general problem, he was able to count the number of symmetry types for 1 < n < 4. In 1949, Shannon[37 indicated the practical importance of Polya's ideas. Shannon showed that functions possessing non-trivial group invariance could be realized with fewer components than most functions. Later, the staff of the Harvard Computation Laboratory classified the 65,536 functions of four variables into the 402 symmetry classes and listed a representative from each [17] class. A variety of writers have compiled a table of minimal networks for the representatives of the classes. This table is extensively [19] used in synthesis procedures [4o0] In 1955, Slepian constructed an ingenious calculus in order to solve the general problem posed by Polya. Since that time, a number of papers have appeared containing reformulations of the problem (or the solution). In addition to this thesis, Robert Lechner1], of Harvard University, is writing a thesis which is also concerned with many of the problems mentioned in the present work. Although Lechner and I have compared results, it should be explicitly stated that our methods and problems are different, and that both theses are independent works.

1-5 The Plan of the Thesis In chapter two of this thesis, the mathematical background for the later sections is constructed. In addition to developing the fundamental enumeration theorems, several products of permutation groups are defined. The principal mathematical result of the thesis is given in chapter two, namely an algorithm for finding the cycle index of a new product of two permutation groups in terms of the cycle indices of the constituent groups. Chapter three contains the construction of the cycle indices of the five most important groups in switching theory. In addition, the number of equivalence classes of Boolean functions is computed. Chapter four contains extensions of the ideas of chapter three. The idea of equivalence is refined and the results extended to networks and to invertible functions. Chapter five gives applications to problems of error correcting codes, graphs, sequential machines, and a generalization to Post algebras. Chapter six concludes with some unsolved problems.

II. MATHEMATICAL BACKGROUND 2-1. Introduction In this section the fundamental theorems of enumerative combinatorial analysis will be derived. The discussion follows the papers of Golomb [1], Polya5[30, and DeBruijn 7. Consider a finite set S consisting of s elements and a transformation group O( acting on S. Consider two elements s1 and s2 to be equivalent under q if and only if there exists an ae C such that S1 = a(s2) This relation will be denoted by s s2(A) which is read "sl is equivalent to s2 under f." Lemma 1. ( ) is an equivalence relation on S. Proof. sl = l(sl) where 1 is the identity map of 1 so that the relation is reflexive. If sl s2( i ) then s1 = a(s2) for some ac. Since Cdis a group, s2 = al(sl) and the relation is symmetric. If s1 = a(s2) and s2 = P(s3), then s = Co(s3) which shows that the relation is transitive and completes the proof. The equivalence relation ~ decomposes the set S into equivalence classes, that is disjoint classes whose union is S. It is very natural to inquire into the number of classes. It is somewhat surprising that this question is so hard to answer in an efficient way. It is clear that in principle the problem is trivial since the group and the set are both finite. In fact, enumeration is not possible in many interesting cases (even with the use of high speed computers). 4

5 The first answer to this question came from a theorem due originally to Burnside (cf., p. 191). Many people still use this approach because of its simplicity but it has computational shortcomings which will be pointed out. The result is obtained below. Lemma 2. For any s e S, = a|(s) = s is a subgroup. Lemma 3. The number of elements in the equivalence class containing s is [: e], the index of O in i s Proof. By the above lemma, is a subgroup of. Form it, the left coset of 4/ containing t. We consider the mapping s: t > $tt E S which maps elements of S into left cosets. Equivalent elements map into the same coset since Tp: t -- t csp: (t)- > s(t)= aaa(t)laeO = st As a runs through, so does aoc (not necessarily in the same order) and we get the last equality above. Thus, cp maps equivalent elements onto cosets since given any coset - st t maps onto it. If we can show that cp is one-to-one, the result will be proven. Assuming that St = -u is equivalent to a(t) = p(u)

6 or t = p(u) which shows that t - u. Theorem 4. (Burnside) [3 1 = - I(ac) where I(oa) is the [s)CS g aL number of elements of S left invariant under a, where the left-hand summation is over all equivalence classes s of S and g is the order of (1 if a(s) = s Proof. Let 56( = 0s^ lo otherwise Then (a) = a(),s We will compute the right-hand side of the theorem and prove that it is equal to the number of equivalence classes. 1 J I(a) -1 = 1 L 6 g seS a g seS a(s)=s where h is the order of 4. 1 h = h = 11 g s~S g [|C.S sE Lgs 6 sE Csg Thesnlh The lemma was needed in the last line of this proof. The lemma was needed in the last line of this proof.

7 The disadvantage of the above approach is that it requires one to compute I(a) for every oa J. Many of the groups to be considered have large orders and this requires considerable calculation. An even more serious restriction is that the calculation of I(c) is time consuming for a set of large cardinality. There is one simplification that can be noted immediately which reduces the enumeration of all elements of L4 to the enumeration of one element from each conjugate class of. Theorem 5. If ca and f are conjugates in A, then I() I(o)) -l Proof. It is clearly sufficient to show that if a = y py, then a(s) = s iff P(s) = s. Assuming c = 7- Py and that c(s) = s, then sa(s) = s = y1 7y(s) y(s) = P7(s) 7 yl(s) = P(s) = s This set of relations shows that I(a) < I(P) and by the symmetry of a and P, I(P) < I(a) which completes the proof. As a corollary, note that Burnside's formula now reduces to the following: Corollary 6. ZII 1 = I n I(c) where n is the cardinality of g L c conjugate class c; I(c) is the number of elements of S invariant under any one element of c. The sum is over all classes.

[4o] [41] This formula is the one employed by Slepian in references [6] and by Davis. The technique to be used in the present work is due originally to / Polya. The development of this theorem rests ultimately on Burnside's / theorem, but the Polya formulation is quite general. Since the applications will eventually be to Boolean functions, the statement of the theorem is formulated in terms of arbitrary functions from a finite domain to a finite range. This formulation will make it possible to [ 71 relate some generalizations of DeBruijn[] to the present discussion. Let F be the class of all functions from a finite set D to a finite set R. Suppose D has s elements and that 6~ is a permutation group of degree s and order g acting on D. Two functions fl, f2 c F are called equivalent if and only if there exists a permutation aCe such that fl(d) = f2(a(d)) for all deD. Consider R(R=q) to be represented as the r union of r disjoint subsets, i.e., R = RI Ri and Ri n R. = 0 if ifj. Let kl,...,k be a partition of s. Polya's theorem tells us the number of equivalence classes of functions from D to R such that for k. values of deD, the image f(d) e R. for i=l,...,r. The numbers that are to be derived cannot in general be given by a closed form expression. An alternative is to express the numbers as the coefficients of an infinite series. For instance, a convenient closed form expression for the number of partitions of n is not known, but it is known that this number p(n) is the coefficient of x in the series given by

9 0 o00 p(n)x = T (1 - xi ) n=O i=l / Polya's theorem is given in terms of generating functions. By a generating function is meant a polynomial in several indeterminates whose coefficients are the numbers of interest. Since the indeterminates are to be thought of as simply symbols rather than variables ranging over the complex numbers, no questions of existence or convergence ever arise. To every set Ri, an indeterminate x. is attached and Vi is the number of elements in R. for i=l,...,r. The figure counting series is der fined as (x1,...,xr) = i Usually the convention is adopted of taking x =l. Let P(xl,...,xr) be the multi-variate generating function of these desired numbers, that is, k k the coefficient of x1...x is the number of classes of functions 1 r with the property that for k. values of deD, f(d) e R. where i=l,...,r. P(x,...,xr) is often called the configuration counting series. / Before stating Polya's theorem, we must develop the concept of the cycle index polynomial of i (Zyklenzeiger), denoted by Z. Let fl,...,f be s indeterminates, and let g. be the number of 1'' s J -i^ J p.? * gl' 2''s permutations of ( having ii cycles of length i for i=l,2,...,s, so that iji = s (1) i=l

10 Then we define g (j) 11 f2 s where the sum is taken over all partitions of s which satisfy (1). / Now Polya's theorem can finally be stated; this theorem reduces the problem of determining the number of equivalence classes to the determination of the figure counting series and the cycle index polynomial. Theorem 7. (Polya). The configuration counting series is obtained by substituting the figure counting series into the cycle index polynomial of 0. 2 2 s s P(X*l,...Xr) = Z (4(Xl..,Xr) (xl,...,Xr),...Y(xl,...lxr)) Pxr) Z (rl(x., xr)" l(x...x. x.r r Proof. Let kl,... k be a partition of s and let ye. Ik.. (Y) denotesthe number of functions invariant under y such that for k. values 1 of deD, f(d)eR. for i=l,...,r. Let Pk, denote the number of equivalence classes with this property and note that pk is the k k coefficient of x1...x r in P(xl,...,Xr). By Burnside's result, Pkl,...,k g... I k ()r 1 **r g The problem is now to find k(1.,x) A E. Lk k z. (,. =.., Ik (Y) X1 r k^ "-r 1 r

11 Consider a function f such that a cycle (dl,...,d ) where d.eD for i=l,...,Q of length A leaves f invariant. All the di(i=l,...,Q) must map into the same R. since (dl,...,dn) f=f. The figure counting series for functions invariant under cycles of length R is r'i (X... ):= Z Yi x i=l Let ye 1 have j. cycles of length i for i=l,...,s. Because the cycles are disjoint, y(Xl''...~xr> = Y (YX''..xr> ^T (Xl, X....x.....Xr..., s1Xr ^ *-^ X Z *...Ik k (Y) 1 TT i 1 rr Now Combining the results k- k P(xl'",.x ) = "'. l.1. r, 1 rk k g- r- g i-k kl....k 1 r k! 1(' ~' r k^ K^ ^e^k kr I.. () r k r. r 1 rr 1= ^ Z V..x rx g y7e' 1,i ( x l,' * 8 7eM 1=' 1'~ r %

12 There is one part of the definition of the cycle index of Owhich is somewhat arbitrary. The polynomial has been defined as a sum over all partitions of s. The crucial point is only that the polynomial must be summed over all elements in (4A. Sometimes it will be convenient to sum over conjugate classes and sometimes over partitions of s. In special cases, these two sets can be the same, but generally they are different. One should note that the sum of the products of the exponents and subscripts in each term is s, since this sum is just the partitions over which the cycle index is generally summed. Also it is a convenient check to take f.=l for i=l,...,s. The value of the cycle index should then be unity. The cycle index polynomial contains all the information about the structure of as a permutation group. Since this structure is essential to all calculations involving the number of classes induced by, one might suspect that the cycle index will be the foundation of all the arguments. This suspicion will prove to be correct. The problems to be investigated in the program will require an extended definition of equivalence. In addition to acting on D, let a group of degree q act on R. Then one defines f - f iff (a) 1l 2 _ P) f1(e(d)) = Pf2(d) for every deD. Now the determination of the classes poses an even more complicated problem than before. A new formula for counting the number of classes will be derived. This theorem is a special case of both DeBruijn's[' theorems 1 and 2. The proof given here is original.

13 115 Lemma 8. 1 = - I(a,P) where I(a,P) is the num[f]& gF h i ber of functions with the property that f(a(d)) = Pf(d). Proof. This lemma is reduced to Burnside's theorem by taking S to be the set of functions F and the group to be the direct product 6 X It is important to note (for later purposes) that domain and range transformations commute. [771 Now the appropriate theorem of DeBruijn[7]may be stated. Theorem 9. I 1 Z (2.,. ) Z (hl,...,h ) where s/t ht = exp (_ tzkt) for t=l,...,q k=l Proof. The problem is to evaluate I(a,3). Assume a has b. cycles of length i for i=l,...,s; suppose that a has c. cycles of length i for i=l,...,q. Attention will now be focussed on one cycle for each permutation, say a cycle al of length m for a and a cycle [1 of length n for P. Consider a function f such that f(al(d)) = P1 f(d). For this f, f(d) must be in one and the same block C of R for every deB, for if this were not the case, then f would not be invariant. It will be shown that n m To show this, assume that m = nq + r where 0 < r < n. Since f( l(d)) = P=f(d)

14 it must be that f(a m(d)) mf(d). This last fact is trivial to prove by induction on m. Then f(al(d)) f(d) =q+r f(d) = f(d) which implies that P1 = 1. This contradicts the definition of n as the order (or length) of P1 unless r=O. Thus, as d runs through any block B of length m in D, then f(d) runs through a block C of R of length n exactly m times. All the n invarient functions are obtained as follows. For every block B of D, associate all blocks C of R whose lengths divide the length of B. There is still the possibility of assigning an arbitrary element of C to some fixed element of B. Once this has been done, the images of all other elements of B are fixed by the requirement. f(d) = r f(ad) = r Finally I(cP) is computed s bp I(aol1) _= TT i ci i<q That is for every block B of D, sum the number of elements in every block C of R whose length divides the length of B. Note that s vb 3bl? bs sb < 1 ( ci) =. b1 T b e ix c-(L i<q i<q

15 evaluated at z = =...= z =0. This is easily proven by taking partial derivatives. Now the results can be combined 21' =~Z I(c1),_1 - -^ I ^P [IJQF QagoJ PE4d b b s g1 a~~ 1b1 ~~'32bS hexp Z ZP i C.) iU T Z1 )z bs i =1 i / 51s i<q s - (Z s exp z i C zl zs h ^ 1 fj Note that /*s \q- S/i exp C exp 4 i C. zs/ i p =1 il i=l k=l i<q q. s/i = exp i zi i=l k=l 1l = z (-.A 9i 5exp Z i C [f CF 1 a z J1 i<4 sI s/i where h = exp (t kt) for =... and the function is evaluated kl i=1 k=l s/-t~~~~

16 at =... = z 0. QED Many times, one is interested in special classes of functions rather than an entire family. One class of functions of particular interest is the one-to-one onto functions or invertible functions. A new derivation of a theorem of DeBruijn[71 for calculating the number of equivalence classes of functions from D onto D will now be presented. Theorem 10. The number of classes of invertible functions from D onto D with a group ~ on the domain and a group j on the range is given by' ) Z4 ( + z1i.,1 l+ szS) Proof. Again, Burnside's theorem may be used. It is necessary to evaluate I'(a,) for ae and Pe A remembering to count only those orbits which contain one-to-one functions. Consider the mapping f -> f1 which also sends (f- ) - (f )-l=f. This map is one-to-one and indicates to us that the number of classes with O on the domain and A on the range is the same as with ~ on the domain and f on the range. Consider a cycle of a of length m and a cycle of P of length n. By the previous proof of DeBruijn's theorem, n m.

17 By the symmetry noted above, m | n and so m=n. Thus b. = c. for i=l,...,s and the determination of I'(o,P) is now trivial because this expression is now simply the number of permutations having bi [42 1 cycles of length i(i=l,...,s). This number is well known to be b. I'(a,) = TTc- i i=l Note that this is also s b S b s b. b1 b s c. TT c i 1 b b (1+ j C I I v I (l jzi=l Oz 1 z1 s j=l evaluated at z-.... z = O0. Now 1 s Z 1 = - 2 1 I'T (cP) [f]cF g e C f 1-1 b b. 1 a1 7 T~ 1n bi g h" E ~ i-=1 - ] ( + g b1 b - h C. 1 7 1 s = G Z Z S-' P (lz l s) Zl s ~ (; i'.e.'X zs) Zf (1 + Z1,.l + sz) evaluated at z =... z =0. 1 s

18 2-2. Structure Theory For Permutation Groups A major portion of research in mathematics is concerned with finding the structure of abstract systems. This usually means finding a well-defined class of subsystems and constructing larger systems from these simple ones by appropriate operations. This type of theory is well developed for abstract groups, but our applications require some knowledge of a similar theory for permutation groups. Unfortunately, a well developed theory of this type does not exist as yet. The concept of equivalence between groups which we shall need is known as permutational equivalence. Permutation groups 6t and By on disjoint object sets X and Y are called permutationally equivalent if and only if a and Y are isomorphic as abstract groups and there is a one-to-one correspondence h: X e- Y such that if cp is the abstract isomorphism between 6~ and $, then for every x e X, a c O, we have h(a x) = (cpa)h(x). Thus, two groups may be isomorphic as abstract groups but not permutationably equivalent. Note that the degree is one invariant of permutationally equivalent groups. We shall now give some of the operations on permutation groups. In each case, it would be desirable to be able to find the cycle index of the new group in terms of the cycle indices of the two given groups. Consider two groups (t and S on disjoint object sets X and Y such that the order of C0 is m and the order of.9- is h; the degree of at is a and the degree of Cy is b. The direct sum of Oi and -written O + 4- has XxY as its object set. The group is obtained as C| Oae ~, O e s }. Thus we

19 (take a(z) if z e X take ap(z) = I (z) if z E Y. It is clear that the order of O +$Y is mn and the degree is a + b. Polya[30] has shown that Z CL +, = Zt Z where we mean the Cauchy product of polynomials by this notation. The direct product of two groups written 6iY X 9 is defined on the object set X x Y in the following way (a,P)(x,y) = (c(x), P(y)). Thus, the order of S X;9 is mn and the degree is ab. The groups aL -d and (L + 3- are isomorphic as abstract groups but are not permutationally equivalent since they have different degrees. We shall now establish the connection between the cycle indices of Ot and'9 and the cycle index of Ot X -. Let 1 vj ja Z = m gl' ga and let - n( k kb ZS = n d h k hb The following theorem was stated by Harary[- ]. Theorem 1. Z = Z <Z where the cross operation for polynomials is >dfined as follows polynomials is defined as follows

20 a. b x - mn C(j) (k) ( P p ( q=l q where the cross operation on indeterminates is defined as a a b k (X gP)X(7 X hI) hq=l a b pkg(p,q) = - T1v Tifp=l q=l <p, q> where <p,q> denotes the least common multiple of p and q while (p,q) means the greatest common divisor of p and q. The statement of this theorem involves a certain amount of notation. For this reason, a simple example is presented. Let 2 and zA = (h1 + 3h1h2+ 2h3) be the cycle indices for the symmetric group on two and three letters respectively. We compute

21 2 1 2 2 2 x_ z (g _ X h3) + 3(g X hh2) + 2(gX h) 23 + (g2 X h3) + 3(g2 X hh2) + 2(g2 X h3) 1 (f6 + 3(g X h)(g2 X h) f +2f2 + f + 3(g2 x h1)(g2 h2) + 2f6) 1 (f6 + 3f6 2 + 2f3 + 4f3 + 2f6) 1 fl 1 2 + 2f6) Before leaving this example, it is interesting to note that this example solves a nontrivial problem of graph theory. If one substitutes 1 + x for f. in Z K then the coefficient of xq is the number of chromatically nonisomorphic spanning subgraphs of the [161 complete graph K23 having q lines cf. Harary [] Proof. It is easily verified that the cross operation on indeterminites is associative, commutative, and distributive over addition. It will be sufficient to examine the cycle structure of (oap) where a is a cycle of length p, say (al,...,a ) and P is a cycle of length q say (bl,...,b ). The case p=q is trivial so we assume p<q. Examining an element (al,bl) E XxY we see that (alb1) goes successively into (a 2b2),(a3,b3),...,(apbp),(al,bp+l),...; we return to (al,b1) after * Roughly speaking, a graph is colored if its vertices are painted so that no two adjacent vertices have the same color. Two graphs are chromatically isomorphic iff the uncolored graphs are isomorphic and the colored of the graphs can be made to correspond via a permutation which is consistent with respect to the isomorphism. The precise definition of these concepts occurs in Chapter 5.

22 <p,q> steps and the pq symbols are permuted in (p,q) steps of length <p,q>. Recall that pq = <p,q(p,q). The argument is completed by noting that the choice of a1 and b1 is arbitrary; any pair of elements one in a and one in f would have given the same result. Another operation of importance is the wreath product or Kranzgruppen of Polya [0], denoted by ~9? Ot in the modern notation (cf. Hall[4]). This group has as its object set X X Y; a convenient formulation is to consider the object set to be a matrix (x..) with a rows and b columns. The operations are defined by first permuting the rows by an operation of Ot and then permuting the column indices in each of the a rows separately by an element of allowing repetitions. The order of this group is seen to be mn since there are m choices for the element of (7 and n choices for each of the a elements of S9. Some observations about this group will prove useful. Note that O1 a is a subgroup of 9-2 0L obtained by always choosing the n elements of B- to all be the identity. We also note that.X.. X Y is another subgroup obtained by taking the identity operation in O. This last subgroup is seen to be normal in i OL, so that Now we turn our attention to getting the pertinent result about the cycle index of S6 O. Let Z ni _1 c() g l gJa and

23 k kb Z 1 d h... h S- b () 1 b Theorem 2. (Polya) Z = Z- lZ 1 j ja C(j) Z.. z m (j) ) a where 1 k ~ kl z = d.\ h.. h for p=l,...,a. P n d(k) pl' pb Proof. The result is fairly clear from the construction but the details are to be found in Polya Example. The cycle index of r2? 3 is now computed. 12( 1 + + 222 z tr2 t 3 = (((f+ + 2+ 35(Kf2 + f4) + 21(f3 + f6) T7 1f + 23f f2 + 3ff+ 6(ff2+ f1f4 2 ~ ~ 8 ff2 f6, + f3 + f2f4) + 8f + 8f6 (f6 + 5f4f2 + 9f2 + 9f3 + 6f6f 6ff + 8f2 + 8f) It is no accident that the result is the cycle index of the symmetry group of the three-dimensional octehedron. Another operation of importance for our application is that of exponentiation of permutation groups. Harary originally constructed

24 this operation in order to systematize the calculations which Slepian[40] had made in his work on Boolean functions. For this purpose, Harary's definition is unfortunate. At this time a more appropriate definition of exponentiation is presented; a new type of product will be discussed later which will characterize exactly what Slepian did. Harary's definition and its consequences are given in appendix V. The exponentiation of (L and is written and has as its object set Y, the class of all functions from X into Y. An ele67ment in 6y, say Pa, operates on these functions in the following way Paf(d) = Pf(a(d)). It is clear that any a and P commute so that ffi a the order of S3 is mn and the degree is b. It should be noted that this situation is exactly the same as the one we analysed in proving the DeBruijn theorems. It will not be necessary to consider the construction of Z o0 since we already have these results concerning the number of classes. Harary has investigated some of the inter-relations between the family of permutation groups and these operations on them. We restate his theorem now. Theorem 3. a. The family of all permutation groups is closed under the operations previously defined. b. If we let Q_ be the group of degree 0 and order 1; 31 be the group of degree and order 1, then for any permutation group J )

25 t + $o = X t X 0 = itoL = O = O 1,I1 XL c. For any permutation groups 0o and X1 + S = A+Ot 0^ x j = jjx M. d. For any permutation groups AJ, 4>, and. Y +(s- + I.)= (.K.).. iX(S X r) = (blX )>. X 2 (St M) = (?^ )1 Y e. The only distributive law which can hold between these groups under the operations of wreath product, sum, and product is tilt>. ) = (C~t) +(Eu) A new group product will be formulated which will characterize Slepian's result and will find applications in a variety of situations. Let h be a group of order g acting on object set X. The degree of His assumed to be b. Let QJ be a group of order m

26 acting on a copies of X; thus, the degree of Lt is b. A new group X l ~ will now be defined. It is convenient to think of a-tuples of Xa listed. If the array is thought of as a matrix of a columns and b rows, then the operations of O1t 0 are constructed by first selecting ace 0 which causes a permutation of the rows of the matrix. Selecting elements l'',..., from ~ (not necessarily distinct), the i column is to be permuted by fi for i=l,...,a. Thus, ~ e y is easily seen to be a group isomorphic to S (O but not permutationally equivalent to it. The abstract structure of Q~f is the semidirect product of 01 by Ja where da denotes.X... X. Now we turn to the problem of computing Zt in terms of Ot e^ Zot and Z i. The following exhaustive (and exhausting) procedure will work for computing Zt Xg> when enumeration is possible. Write out all possible permutations of 0~ and all possible permutations of a a. Compose the permutations and write down the cycle structures. This procedure suffers from some of the defects of the Burnside approach to enumeration. In general, the problem of finding Z in terms ot a bSe of Z and Z. is still unsolved. An algorithm is now given when t is the symmetric group on the n columns and hence a group n is induced as a permutation group on the rows. In the case described where Ot is the symmetric group, Cn X 9 has the abstract structure of the complete monomial group of degree n of S. The theory of such groups has been worked out [28] by Ore[] and reference to several of his theorems will be made. For the purposes of this thesis, it will be sufficient to derive the cycle index of En gQ where g-has a restricted type of cycle

27 structure. The condition on ~ can be expressed by requiring that Z is of the form 1 k b gI fb(k) k Although the restrictions imposed on 3 are severe, it is surprising that the results obtained have wide applicability. The formula is now presented. Since the result is complicated, the reader will wish to read chapter three before examining the proof of theorem 4. For the reason the proof is given in appendix VI. Theorem 4. Let n be the group induced by the symmetric group of degree n and let it be a group of degree m and order g whose cycle index has terms whose structure is of the form f. kp< 1 n! where the sum over the same set as the product in the formula for zrn (j~n (k) d ik d where e.(d) can be computed recursively from the following relation where the sum is over the same set as the product in the formula for

28 Proof. The theorem is proven in appendix VI. We shall conclude the section by remarking that surprisingly many groups satisfy the hypothesis on 9. Example. Let be the cyclic group of degree and order 3. 13 Z 1 = (f1 + 2f3) -1 Z r^ 2 (3(f3 + 2f)X2 + (flf3 + 2f3f6) t (f9 + 8f3 + 3f3f + 6f3f6) The group operations are shown in Table I along with the important parameters.

29 OPERATIONS ON PERMUTATION GROUPS Group 6O W 0+ rx ~ il Object Set X Y X ULY X X y X Y YX a Degree a b a+b ab ab b a Order m n mn Cfin mn mn Group Ia 9 OY SY Object Set Xa X Xa Xa Degree ba b b ba, a a Order m n a. n mn TABLE I

CHAPTER III SWITCHING FUNCTIONS AND PERMUTATION GROUPS 3-1. Introduction We shall call functions from {o,1n into f0,1l switching or 2n Boolean functions. The class of all such 2 functions forms a free Boolean algebra on n generators having 2n atoms and denoted by F. The reader is referred to reference [38] for the theory of n Boolean algebras. We shall be interested in solving certain combinatorial problems in classifying these functions. Whenever possible, the results will be given in the most general possible form even though our applications will be only to F. 3-2. Groups on Functions There are certain types of permutation groups which can be defined on Boolean functions. For instance, one might define the full 2n permutation groups on all 2 functions. This group on all the 2n functions has order 2:. No useful applications have yet been found for this group because the group is too large and does not preserve interesting relations between functions. It also seems natural to define permutation groups on the domain of Boolean functions. Examination of permutations on the domain indicates an important fact, namely these permutations are exactly the automorphisms of F. To review the terminology briefly, a mapping h from a Boolean algebra A into a Boolean algebra B is said to be a homomorphism iff 50

51 h(a + b) = h(a) + h(b) h(ab) = h(a) h(b) and h(a) = h(a) An isomorphism is a one-to-one and onto homomorphism. An endomorphism of a Boolean algebra is a homomorphism from an algebra into itself while an automorphism is an isomorphism of Boolean algebra with itself. It is well known that the class of automorphisms of a Boolean algebra forms a group. Theorem 1. Let A be a Boolean algebra having k atoms and 2 elements. The automorphism group of A is exactly the group of all k! permutations of the atoms and is isomorphic to the symmetric group on k letters. Proof. Clearly every automorphism preserves the partial order of A and hence maps minimal elements into minimal elements. Since the automorphism is one-to-one and onto, it is a permutation of the atoms. Let a be a permutation of the atoms of A. Using the normal form expansion, we see that a induces a mapping from A into A, i.e. a: f = a. - af = X aa(i) iel i (i To show the onto property, note that if we are given f = a. ieI

32 then the function ) = 211 a-l(ai) maps onto f under a. Now we show that a preserves the structure. Let f = a. and ieaI g = a,, then jeJ o(f + g) = a( a +I a ) = a( a ak) icO 1 keIvJ ~ / a f(k) ai a(i)+ A AT() = (f) + a(g) Similarly, o(fg) =- (f) a(g) Lastly, we compute a(f) a ) = a a (i) (A) Lastly, we show that a is one-to-one. Suppose of = ag This happens iff -1 -1 a af =f = ag = g Corollary 2. The automorphism group of F is the symmetric group on the 2n atoms, denoted by f2n. It is interesting to note that the endomorphisms of a Boolean algebra can be constructed in an analogous way. It is possible to

55 show the endomorphisms of a Boolean algebra are exactly the mappings from the atoms into the atoms. Thus, the Boolean algebra F has n n2 2 endomorphisms. There is one last place that one can define a permutation group. Suppose that one defines transformations on the variables xl,...,x of F. These transformations induce permutations of the atoms and hence automorphisms of F. The applications of Boolean functions to switching theory generally suggest natural groups to apply to the variables. 3-3. A More Precise Characterization of our Problems The first class of problems to be investigated involves a single group on the domain. For this class of problems one need only apply Polya's theorem. Since the range of our functions is {0,1 =-R, take R1 = {0} and R2 = { 1. With R1, associate the indeterminate 1, and with R2 associate the indeterminate x. Thus, the range enumerating series for switching functions is T(x) = 1 +x Thus, our enumeration results for Boolean functions can be obtained by constructing the cycle index of the group under consideration. It is important to note that this group must be of degree 2, i.e. defined over the domain, not the set of variables. Before proceeding to the actual constructions, a trivial case is given as an example.

34 Let n be the identity group on the n variables. n is of order one and induces a group on the domain of degree 2. The cycle index of the induced group is given by n Z = f 2n Then by Polya's theorem P(x) = (1 + x)2 (2n) Xi i=0 which says that the number of switching functions of weight k, that is, having k ones in their graph or k atoms in their normal form /2n expansion isk. Note by taking 2n 2n 22n P(l) z 2 (2) = ( 2 ~ n i=O that we get the total number of functions. If one is merely interested in the total number of classes, take f. = 1 + li = 2 in Z (fl,...,f ) for i=l,...,s and compute Z (2,...,2). 3-4. The Group 2 The first mathematical investigations of switching theory concerned the analysis of relay contact networks. In such networks, the cost of a normally closed contact is the same as the cost of a normally open contact. This suggests calling the following two networks equivalent.

35 x2 x3 ~~~~X1 D x2 X3 x2 x 12 x3 Fig. I. Two Networks Which are Equivalent Under 32 Definition 1. The group j2 = <0,1l, $, 0 > is defined with the operation of addition modulo 2. Definition 2. The symbol 2p denotes.2 X... X J2' i.e. the abstract direct product of n copies of 2. Thus, elements of 2n are n-tuples of zeroes and ones; the operation of the group is digit-wise modulo two addition. Of course, the identity element is (0,...,0). Now this group is defined on Boolean functions in the same way [2] that Ashenhurst ]did. Definition 3. Let ie 2 and let f(xl,...,xn) be a Boolean function of n variables. Define if i i n) if = (il...,in) f(x1...,xn) = f(x1 ^..,xn 1)

36 {x. if i. - 0 0 i. J where x. i = for j=l,...,n J x. if i.= 1 Rather than compute the cycle index of in the way that Ashenhurst did, we shall derive it from the structure of 2 as a permutation group and indicate some of the power of a structural theory of permutation groups. Theorem 4. As a permutation group, X 2 = 2 X... X T 2' Proof. Consider j2 defined as a permutation group on the set consisting of zero and one. Using the definition of the product of permutation groups, it is evident that n = X... X 2 - + 2 X'' 2 1 2n _ 2n-l Theorem 5. Z = (f + (2 - f2 2n2 2 Proof. By theorem 2-2.1, n =2 1 2 + r2 n X 2 (f + ) X2 i1l 2 i=l It is claimed that i ( 2) (fl + (22- 1 (f2 n 1 y ind n, we nd ony To show this by induction, we need only compute

37 1 2n-l n-2 1 2 2- (f + (2n-l 1) f2 ) < (f + f2) _1 2n ( n -1 2 1 n-1 + (n -1 2n1 - (ff + (2 - 1) 2 + (2 -1) 2n 1 2 n n-l n (f2 + (2 - ) 2 ) 2 1 2 Before applying this result to Boolean functions, it is interesting to note that a still stronger version of the theorem can be shown to be true, namely the following: Theorem 6. Let j be the regular representator of the (abelian) k group of order p and type (1,...,1) then Z = - (f + k-1 k P (p - 1) fP ) for any prime p and k > 1. p Proof. Clearly has degree and order p. Let cp be any nonidentity element of. cp: a - ax'x All the images of c must be in a single cycle of length p, for if they did not, there might for example be two shorter cycles, any one of length k and one of length -. The argument to be presented follows for any number of cycles. Since (k +4) = p, we must have (k,q) = 1 or p since any common factor of k and divides p. Assume (k,A) + p since then we would be done. Thus, we have that the order px is p = < k,l> = ( = k which is a contradiction unless one of k or p is p. Thus, the cycle index of 4 is given by

38 k k-1 Z = 1 (p + (pk 1) fP ) Ri p Now we return to Boolean functions and begin to collect our results. Theorem 7. The number of equivalence classes of functions having k atoms in their (unique) normal form expansion under X is (2n\ if k 1 mod 2 2n \k/ and in 2)+ (2 - l) ( ) if k 0 mod 2 2 / \k /k/2 / Proof. By Polya's theorem, 2 r~ (l i x).kM ((l~~x)2 ~ + " ~i,2n n 11+ 2l (1 +x) (1 + x)2 + (2n - 1)(1+ x2)- ) _n 2( If k 1 mod 2, the coefficient of (2n If k = 1 mod 2, the coefficient of x is k \ 2 If k 0= mod 2, the coefficient of x is (( +(2 1) (2n)) 2- \k + (n-)k\k/2/

39 Theorem 8. The total number of equivalence classes of Boolean functions under 2 is 2on 2n-1 \ n 2 + (2n - 1) 2 ) 2n / i Proof. By Polya's theorem, take f. = 1 + 1 = 2 in Z n 2 Some typical calculations for this group have been made and the results are tabulated in Table I. We use T for the total number of n equivalence classes and Nk for the number of classes of functions having k atoms in their normal form expansions. Note that N = N k i n n which is a consequence of the law of duality for Boolean functions.

40 THE NUMBER OF CLASSES OF FUNCTIONS WITH k ATOMS UNDER 2 n Nk n k 1 2 3 4 5 0 1 1 1 1 1 1 1 1 1 1 1 2 1 3 7 15 31 3 1 7 35 155 4 1 14 140 1,240 5 7 273 6,293 6 7 553 28,861 7 1 715 105,183 8 1! 870 330, 46o 9 715 876,525 10 553 2,020,239 11 273 4,032,015 12 140 7,063,784 15 35 10,o855,425 14 15 14,743,445 15 1 17,678,835 16 1 18,796,230 n__ 3 7 46 4,336 134,281,216 TABLE II

41 As an example of the classification of functions induced on F2 by Q2,' the equivalence classes are listed below [x + y, x +, x+ y, x + y] [xy xy, xy, xy] x e y, x y 3-5. The Symmetric Group Tn The sort of equivalence induced on functions by has practical significance because the intended applications were to contact networks where the cost of the relay contacts corresponding to x. and x. was the same. In networks consisting of electronic components, the cost of these two forms is different. It is certainly true that the cost of any network is independent of the labels on the inputs. For instance, the networks shown below cost the same in any type of technology. X1 AND x2 X~1_2 1 OR -XX 2 + x34 x4 -- AND ^ -X3-1 x2 AND x4 g I AND W Fig. II. Two Networks Which Are Equivalent Under 3

42 on is used to denote the symmetric group on n letters; this group has order n' and degree n. n is now defined as an operator group on Boolean functions as suggested by the previous discussion. Definition 1. For any aE n and any feFn, define af(x,...,x) = f(xy(1),...,(n ) The symmetric group on the variables has been studied by Heller[18] man - who was able to obtain the number of classes for 1 < n < 5 by using Burnside's formula. Hellerman, however, did not have an algorithm for the solution of the general problem. This group has been mentioned implicitly in reference[9] but no explicit discussion is given. It is believed that the results which follow have not been obtained before. Thus, every ae n induces a permutation of the atoms of F as n n shown in the following example where a = (12) and we consider F3 ( 0,0,0):-> (0,0,0) (o,,O1) - (oo,1) (0,1,0) -> (1,0,0) (0,1,1) -e (1,0,1) (1, O.) -) (0,1,0) (1,0.1) -- (0,1,1) (1,1,0) -- (1,1,0) (1,1,1) -> (1,1,1) Using the conventional decimal notation for atoms (cf. [4]) and writing the permutation of the atoms induced by a be written in cyclic notation, it is deduced that

43 a induces h = (0)(l)(6)(7)(2,4)(3,5) Thus, the permutation a of the variables induces a permutation h of the domain. a Theorem 2. The mapping a -4 h for ae j is a one-to-one homomorphism from into Proof. Clearly the mapping a -> h is a map from C into. To show that the map is a homomorphism, suppose that a - h T-~h aT -~ h aT Clearly h = h h as may be seen from computing the effect of ha on any typical domain element. To show that the mapping is one-to-one, assume that h = h a T for all domain elements, but this can only happen if a = T. Thus, the connection between C on the variables and the symmetric group on the domain can be summed up by saying that there is an injection from into n. The cycle structure of as a permutation group on n letters is known, but the present problem requires a representation of the group of degree 2 Theorem 5. Permutations of the same cycle structure in t correspond to permutations of the same cycle structure under the injection.

44 Proof. Let h be the homomorphism from n into 2n. Since all pern 2n mutations of the same cycle structure are conjugates, it is sufficient to show that conjugates of a in ( correspond to conjugates of h(a) in a. This is trivial since h(pl p) = h(p )h(a)h(p) (h(p))h(a)h(p) because h is a homomorphism. An algorithm must be constructed to pass from the symmetric group on n letters to a representation of the group on 2 letters. To accomplish this, the effect of a cycle of length k on the atoms of the Boolean algebra is calculated. A cycle of length k only affects 2 domain elements and furthermore, the non-zero elements of the domain can be considered to be in one-to-one correspondence with the integers modulo (2k - 1). Lemma 4. If q is any integer such that 0 < q < 2 -1, then the least positive d such that 2 q = q mod (2 -1) must divide k. Conversely, every d which divides k must satisfy the k congruence for some 0 < q < 2 -1. Proof. First we will show the converse. If dik, then (2 -1)| (2 -1) then 2k- = q(2 -1) or 2q - q mod (2k-l)

45 Thus, this argument tells us that for given d, the q to be chosen is the integer 2k-l 2 dl To prove the first half, assume d is the least integer such that 2d 2 k k k 2 q mod (2 -1). Then since 2 1 mod (2 -1) 2 q c qmod (2-l) Assume for the sake of contradiction that k = dp + r where 0 < r < d. Then dp 2rq q mod (2 -1) i.e. (2i)p q2r q mod (2 - 1) We shall use the fact that 2 q mod (2 -l) exactly p times until the previous congruence is reduced to 2r = q mod (2k -1) This is a contradiction unless r=O, i.e. d |k. Lemma 5. A cycle of length k in n induces permutations on the domain whose lengths are divisors of k and moreover every divisor of k is the length of some cycle.

46 Proof. Write the numbers from 0 to 2 - 1 in binary notation and in natural order. The effect of a permutation of length k can be obtained by removing the left-hand column and writing it as the right-hand column This has the effect of doubling each number modulo 2 - 1. Thus a number q (0 < K < 2 - 1) goes successively into d k 24q o,2dq - q2cj mod (2 - ) The length of the cycle containing q is the least positive integer d such that 2dq = q mod (2 - 1) By the use of lemma 4, the result is obtained. Theorem 6. A cycle of length k in the symmetric group on the letters induces a permutation on the domain whose cycle structure is given by c fe(d) Thk d d| k,there the f are the indeterminates of the cycle index and e(m) 2 Z') ~.h.e:re f1() i'the M': 3bLu:i. functiono \ Proof. Lenma 5 shows that the cycle lengths are exactly the divisors of k, but their iultiplicity remains to be determined. Since the degree of the desired representation is 2, it is necessary that 2 de(d) - 2 d. k

47 By the M'obius inversion formula, 1 dk d k e(k) = - 2 () where p(k) is the Mobius function. It is interesting to note that e(k) is precisely the number of irreducible polynomials of degree k over GF(2). Theorem 7. The cycle index for n as a permutation group on the domain of the Boolean algebra of functions is rn ni, _A _ d where the sum is over all partitions of n such that i iji = n i=l & i < 2 1n i,- 2 n' and \y =y X y... X y where y = y y... X y. i=l Proof. The coefficient in the sum is the number of permutations of the n letters with j. cycles of length i(i=l,...,n). To see this, choose any permutation with the required cycle structure. If all n! permutations are applied to the letters in the cycles, then the resulting permutations are not distinct for just two reasons, (1) the relative position of the cycles is irrelevant and (2) all cycles with the same elements in the same order are the same. The number of

48 duplications for the first reason is j i2.j..' Jn The number of duplications for the second reason is 1 2... n so that the desired number is n! n n j i=l Turning now to the cycle structure, note that each cycle of length 2k k affects 2 elements of the domain and fixes all other domain elements. So the disjoint cycles act as if they were defined on disjoint sets. Cycles of length i go into cycles of length 2 and finally that ii ij. - 2 1_ - TV ij i j i n ij i 2 2 2 This accounts for the presence of the cross operation even though the group structure is not that of a direct product. Using this theorem, the cycle index has been constructed for ~ for 1 < n < 6 and these polynomials are to be found in appendix Io Now replace each indeterminate in C by two to obtain the total number of classes which are given below in Table III. T denotes the number of classes.

49 T n n 1 4 2 12 3 80 4 3,984 5 37,333,248 6 25,626,412,338,274,308 TABLE III THE TOTAL NcTMBER OF CLASSES UNDER R n ~~n N~1i n k 1 2 3 4 5 0 1 1 1 1 1 2 3 4 5 6 2 1 4 9 17 28 3 3 16 52 134 4 1 20 136 625 5 16 284 2,674 6 9 477 10,195 7 4 655 34,230 6 1 730 100,577 9 655 258,092 10 477 579,208 11 284 1,140,090 12 136 1,974,438 15 52 3,016,994 14 17 4,077,077 15 5 4,881,092 16 1 5,182,326 T 4 12 80 3,984 37,333,248 TABLE IV TQHE NUBBER OF CLASSES OF FUNCTIONS WITH k ATOMS UNDER n

50 Now we can apply Polya's theorem to count the number of classes of functions with k atoms in their normal form expansion. N denotes this n number; we remark in passing that N = N k. It is also true that n n 0 1 N= 1 and N = n + 1 for all n > 1 Cf. Table IVn n Before concluding this description of the construction of cycle index of n, an example is given. Let n=3 so that the partitions of 3 are 1) il = 2 =0, j5 = 0 2) j, = 1, J3 =0 1, J = 0 2) i 0 ) J = 0, J2 = 0, j = 1 Thus z 5 = )X + 3(f ) x (f2f ) + 2f2f 1,8 42 4 22 (f + 3f42 + 2f2f) l 1f2 15 It is very interesting to note that one can carry the analysis one step further and write a completely closed form for Z An Theorem 8. n.. nf 1 n n n(j) nJii j1 in < i. i i=l where g (i ) = i L 2 d (i-) for k=l,...,n a k k d| ik and the sum is over all partitions of n.

51 Proof. The result follows directly from theorem 7 and the properties of the cross operation. 3-6. An the Group of Complementations and Permutations of Variables It seems very natural to consider the concept of equivalence when one can complement and permute variables. This situation was the first case considered in the development of combinatorial results on Boolean functions. The first systematic paper on this topic is by Polya who quotes some partial results of Jevons and Clifford which date back to the nineteenth century. In our discussion of this group, to be called n, there are two alternative approaches. We can simply define 6n and note that Jn and n are subgroups possessing certain structure. A preferable alternative is to try to construct n from 2and. We choose this alternative because a similar process will be followed later on for two different groups. First we shall consider symbols of the form (i,a) where ie.2 and ac.n' We shall define such a symbol as operating on Boolean functions in the following way. i 1 i (ia)f(xl,...,x) = f(xa(l),..,x (n)) Clearly, the objects (i,o) permute the domain as we would like, but our tacit comment that A is a group must be verified.

52 Theorem 1. ni = 5(ie)| i2 is s a group under the following operation (i,):(j:,T) = (i + C(j), orT) where c(j) denotes a(j) = a(j,'...Jn) = ja(l)'*''jo(n)) Proof. We first verify that the operation is associative. ((i,o) (j,)) (k,p) = ((i + a(j)), at) (k,p) (i + a(j) + aT(k), aTp) Now we compute (i,) ((j,Tr)(k,p)) = (i,a) (j + r(k), Tp) =.(i + C((j) + aT(k), CTp) The rest of the verification of the group exioms is routine. In the next two lemmas we note some facts about the abstract structure of the group. Lemma 2.a. (iy)- (l (i),l)(Oa 1) (a(i),C) = (0,a)(i,l) (0,a)(i,d1) = (a(i),1) Lemma 35 For aE and ie 2 the application p: i - ac(i) is an automorphism of 2.

55 Proof. Clearly cp is a map from 2n into 2. The map is onto since given any je t,2 then a (j) maps onto j under pa. The map is oneto-one since a(i) = r(j) implies i = C-a (i) = a c(j) = j. If i -, o(i), j -4 a(j), and i ~ j -> c(i ~ j), then we have o(i C j) = a(il ~ jl'...in jn) = (i(1) ja(l)'**"a(n) c J(n)) = (i) + d(j) and cp is an automorphism. In group theory, this process of combining In and to form En is a special case of forming the semi-direct product of X 2by n. The following theorem is a special case of theorem 6.5.2 of Hall Theorem 4. is the semi-direct product of n by. The elements of the type (0,c) form a subgroup isomorphic to n while the elements of the type (i,l) form a normal subgroup isomorphic to 2. Furthermore, n = (0,1) and 2U = L n The order of 2 n 2 nProof. The result follows from Hall's definition and construction. All the stated properties are obvious except perhaps the normality of J: 2 This follows directly from lemma 2, part c. This result corrects an error of C. E. Shannon who thought that the structure of _ was the direct product of t and I. This is obviously false since ((001),(123)) 010X(132l)) = ((001) } (100), 1) = ((101),1)) when ((010),(132 )X(001),( 123)) = ((010) @ (100). 1) = ((110), 1).

54 We may remark that this group operation of forming the semidirect product is the abstract analog of the wreath product. Before proceeding to the construction of Z, certain interpretations of An should be pointed out. It is well known that the Boolean functions of n variables can be represented on the n-cube in the following way. Each of the 2 -variables can be n labeled with exactly one of the integers 0,1,...,2 -1. If the label is written in its binary representation, there is a one-toone correspondence between the domain elements of the Boolean functions and the vertices. Thus every subset of vertices corresponds to a Boolean function and conversely. The number of equivalence classes of Boolean functions under n is thus the same as the number of distinct ways that one can paint the vertices of the n-cube with two different colors. Two paintings of the n-cube are distinct, iff one can not be transformed into the other under the symmetry group of the cube. It is interesting to note that n is abstractly isomorphic to the hyper-octahedred group of Polya, but not permutationally equivalent to it. The group must be isomorphic because the n-cube and the hyperoctahedron are dual figures and hence have isomorphic symmetry groups. The groups can be seen to be permutationally non-isomorphic since the degree of M is 2 and the degree of the hyperoctahedred group is 2n. Now the construction of Z, is carried out. Certain facts will be used about the abstract structure of C. The coefficients of Z j will be just the coefficients of Z ~. It is the cycle structure which changes. Every conjugate class in n has a cycle

55 in so-called normal form (cf. Ore, theorem 7). It is sufficient to consider a term of the form ((0,...,0,1),(,2,...,k)) by Ore's result. If the cycle structure induced by this term can be deduced, then we are done. Lemma 5. The cycle lengths d induced by((O,...,0,1),(1,2,...,k)) have the property that d[ 2k but d k and conversely. Proof. The order of the permutation induced by a = ((0,...,0,1), (l,...,k)) is 2k (theorem 4 of Ore). Thus, any cycle length d must divide 2k. If d k, then a k(q) = q for a domain element q in the cycle of length d. However, Co =((l,...l),l) which maps q into 2 - 1 - q c q. This contradiction shows that dok. Conversely, suppose that d 2k, but dkk. We shall construct a formula for an integer q which lies in a cycle of length d; the formula will be given in terms of d and k. First, note that any d which divides 2k but does not divide k must be even. It is easily verified that a domain element of length k having the following form is invarient under ad where a =((0,...,0,c1)(1,2,...,k)). d d d d d \ 12 02 12 02 12 d d/2 2 ell — The notation 1d means 1, 1,..., 1. The domain element will begin and end with 12 because if the number of terms 2 where Pe IO,1. were even, say, then we would have (2)?= k or ()d = k or that d would divide k, which would be a contradiction. To compute the

56 formula for this domain element we must simply compute the following sum d 1 i k d. 2~-1 k 1 q. == l + 2+...++22 + 2 +...+ 2 +...+ 2 +.i.+2 2k - d (2 2 1) 2id 2 2 -1 i=O = 22 + 1 For instance, if k=6, d=4, then q=51. It is easily checked that the cycle containing 51 is (12,25,38,51). Lemma 6. The cycle structure induced by a cycle (l,...,k) is given by i1T fe(d) +T f(d)) 2 alk d a j2k d dk where e(k) = 2 d k k d. k and g(2k) Z 22 k 2k di 2k d dtk where [i is the Mbbius function.

57 Proof. A cycle of length k in the symmetric group induces a permutation of the type given in theorem 6, section 5 when premultiplied by a complementation having an even number of ones. The previous lemma computes the cycle lengths of the other case. We must require that Z dg(d) = 2k dtk whence d g(2k) -1 2 2 2 -kd| 2k d dtk by a slight generalization of the Mobius inversion formula. To prove the generalization, it is sufficient to prove that 1 if k = 2p Z () f di2k I(2k dj 2k d'k 0 otherwise This is trivial since =(t) (l(t) =1 if k/2 = 1 CIL (- tI k tj k d t|t oddi 2k {0 otherwise di`rk t odd 2llk Theorem 7. The cycle index of O is given by i=l n X n'on (j) 5 0 —(n!2 e(d) ji, ( d) X-`i wher tT where the sum i over all golutions of i1 ij = n. i=~l i

58 Proof. The result follows directly from the lemmas by the same reasoning as in theorem 7, section 5. As an example, Q2 is computed 2 f The classes are shown below y ixy, xy, xy, xyh [x, y, x, yj ix y,: x - yj:x+y, x+y, x+y, x+yJ tl Table V indicates the number of classes for 1 < n < 1 while Table VI shows the numbers N'. n

59 T n n 5 6 22 402 1,228,158 400,507,806,843,728 TABLE V THE TOTAL NUMBER OF CLASSES UNDER n \ n N k \ 1 2 3 n 4 5 0 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 3 1 3 6 10 4 1 6 19 47 5 3 27 131 6 3 50 472 7 1 56 1,526 8 1 74 3,779 9 56 9,013 10 50 19,963 11 27 38,073 12 19 65,664 13 6 98,804 14 4 13355,576 15 1 158,658 16 1 169,112 T 3 6 22 402 1,228,158 TABLE VI THE NUMBER OF CLASSES OF FUNCTIONS WITH k ATOMS UNDER ~n

6o 3-7. The Lihear Group Let Z = {0,3 be the field of two elements which must be of characteristic two. By GLn(Z2), denote the group of all nonsingular transformations from an n dimensional vector space over Z into itself. Since the underlying field is finite, the order of GL (Z ) is also finite. It is well known (cf. Artin[ ) that the n2 order of GL (Z2) is n-l l)n n(n-1) n I(2n 2) = 2 2 \ (2 -1) i=O i=l For our purposes, it is convenient to think of GLn(Z2) as a group of n x n non-singular matrices whose elements are zeroes and ones. Let A = (ai.) be such a matrix and let f(xl,...,xn) E F. We define the product Af as n n \ Af(xl...x) = fk aklxk,... aknxk -k=L k=l where e denotes addition modulo two. This may be abbreviated if x denotes the row vector (x1,...,x ). Then we may write Af(4) = (xA) The first problem to be posed is the determination of the number of classes, so we turn to the problem of finding ZGL (Z2). All of the available information necessary to calculate the cycle [8] index is available in the literature. Dickson (page 255) calculates the coefficients of the cycle index which are essentially the number of elements in a conjugacy class. Elspas[ 0] derives and Slepian[']

61 [40] uses the cycle structure for each class. Slepian has solved related problems in counting the number of classes of codes under GL (Z). n The algorithm to be presented involves a certain amount of notation. Consider the irreducible polynomials of Z2[x3. For every positive integer m, there are at most a finite number of irreducible polynomials of degree m. Imagine the irreducible polynomials sorted by degree and enumerated. The polynomial p(x) = x will be excluded from all our considerations. Let d. denote the degree of the ith irreducible polynomial and let e. be the least integer such that 1 polynomial Pi(x) divides x - 1. Church[5] has listed irreducible polynomials for the first four prime moduli. Table VII indicates the first 22 polynomials along with values of d. and e. for Z2. On Since the irreducible factors of x - x are exactly the irreducible polynomials (mod 2) of all degrees which divide n, let I(m) be the number of irreducible polynomials in Z2[x] of degree m. By equating degrees we get 2I m I(m) = 2n mnln BY the M5bius inversion formula, one gets I(n) 2d ( ) where ( is the Mbius function where,(n) is the 96bius function,

62 TABLE VII TABLE OF IRREDUCIBLE POLYNOMIALS OVER Z2 6 5 4 3 2 o i x x x x x x d. e.,.,001141 1 1 1 1 1 1 2 1 1 1 2 3 3 1 0 1 3 7 4 1 1 0 1 3 7 5 1 o o 1 1 4 15 6 1 1 0 0 1 4 15 7 1 1 1 1 1 4 5 8 1 0 0 1 0 1 5 31 9 1 0 1 0 0 1 5 31 10 1 0 1 1 1 1 5 31 11 1 1 0 1 1 1 5 31 12 1 1 1 0 1 1 5 31 13 1 1 1 1 0 1 5 31 14 1 0 0 0 0 1 1 6 63 15 1 0 1 o o 1 6 9 16 1 o 1 o 1 1 6 21 17 1 0 1 1 0 1 1 6 63 18 1 1 0 0 0 0 16 63 19 1 1 0 0 1 1 6 6 3 20 1 1 0 1 6 21 1 1 1 0 0 1 1 6 65 22 1 1 1 0 1 0 1 6 21

63 Because the polynomial p(x) = x is ignored, we must subtract one from I(n) in our calculations. Let t be the number of irreducible polynomials in Z2 x of degree n or less not counting p(x) = x. Table VIII shows the first few values of I(n) and t. Of course ~~n tn I(m)- m=l TABLE VIII VALUES OF I AND t n n n I(n) t n 1 2 1 2 1 2 5 2 4 4 3 7 5 6 13 6 9 22 The first step in the algorithm is to give a notation for describing the classes of GL (Z2). One finds all possible nonnegative integer solutions a. of the equation t n > a. d. = n 1 1 i=1l The solutions may be written as set of t -tuples (a,...,at ) Take every element a. and write all possible partitions of a. where the partitions must be written in the form

64 a. ai jaij (1) j=l Thus the ai. are elements in the partition for the integer ai. The classes of the group may be given by t -tuples each of whose n elements iis a partition of a solution of equation (1). The notation is just unusual enough that an example is in order. Example: n=2. There are only 2 solutions of a1 + 2a2 = 2, namely a, = 2, a2 = 0 and al = 0, a2 = 1. Thus there are 3 classes (0l = 2, o) 11' ) (ac = 1, o) (0, c21 = 1) Before writing down the cycle index, two final definitions are b. introduced. Let qij = e.2 where b. = — log2j]. [xi is the LJ 1 2 largest integer < x. Also let d.(j-l) d 2 l (2 1 1) he 2'..(. ) ij qi. J At long last it is possible to write down a closed form for the cycle index. Theorem 1. The cycle index for GL (Z2) as a permutation group on the 2n elements of {0,ln i

65 n(n-1) n tn ai X COlij 2 2 -/(2'-l X X fi hi 1 i=1 i=L j=1 k= 1k ZGLn()n( n-) n - t a 2 (k-) aj 1 aj a. (ajp-l)ajp a. naJj-U2 c(j J'ka j (dp-)O 2 2 j-k -f ( 2 Jk' 2J 2 (2 - dj-1) i=1 j=1 k=i k=i l=k+i p=/ q=1 Proof. The complicated coefficient is merely the number of elements Y8] in the class as given by Dickson-. The products of f's denote the cycle structure as derived by Elspas Using the algorithm, the cycle index polynomials have been constructed for 1 < n < 6. The number of classes is obtained by substituting 2 for each indeterminate. The results are given in Table IX. Further results are collected in Table X where Nk denotes this numn ber while T denotes the total number of classes. n Tt is easily seen that Nn = 2 for all n. This is because the n zero vector is in a class by itself and all the other atoms are equivalent. If n > 1, then N2 = 2. One class consists of the functions having the zero vector and another non-zero vector. The second class consists of functions involving two different non-zero vectors. The reason that any pair of such functions are equivalent is that there exists a nonsingular transformation which takes any basis onto any other basis. Likewise n > 3 implies N3 = 3, and n > 4 implies N = 5 n - n

66 n Number of Classes 1 4 2 8 3 20 4 92 5 2,744 6 950,998,216 TABLE IX THE TOTAL NUMBER OF CLASSES UNDER GL (Z2) n Nk n k 1 2 3 4 5 0 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 3 2 3 3 3,4 1 4 5 5 5 3 7 8 6 2 9 14 7 2 11 23 8 1 12 35 9 11 55 10 9 84 11 7 117 12 5 158 13 3 204 14 2 242 15 2 274 16 1 290 T 4 5 20 92 2744 n TABLE X THE NUMBER OF CLASSES OF FUNCTIONS WITH k ATOMS UNDER GL (Z2)

67 It is desirable to examine the structure of the equivalence classes themselves. The following considerations facilitate calculations. Every matrix in GL (Z2) may be written in row echelon form. This says that GL (Z2) is generated by the scalar matrices, the nl permutation matrices Pi.. which interchange columns i and j, and the matrices D.. th th which add the j column to the i column mod 2. An easy calculation shows that P.. = D.. D.. D.. 1ij ij Ji 1i 2 Thus the group is generated by the n - n matrices D... This means that to find functions equivalent to f(xl,..,xi....,xn), one examines f(xl,...,xi x...,xn) for jfl.* As an example, we list the eight classes for n=2. [0) W XY [xy, xY, xy [x + y + y, x +, + y] [x, y, x 0 yJ [x, y, x y] 3-8. The Affine Group Let us consider now the affine group as a transformation group on Boolean functions. An affine transformation is of the form y = A bA where AeGL (Z ) and b is a vector whose components biZ2 for i=l,...,n. n 2..i2 Q denotes componentwise addition modulo 2. We denote the affine group *This argument also shows that the class L of all 2n linear Boolean functions of n variables is mapped into itself under GLn(Z2). There are four classes of linear functions under GL (Z2) for all n.

68 by 01(Z2). The effect of the affine group is the complementation of those variables of the Boolean function for which b. = 1. The order of 1 (n(Z2) is n(n+l) n 2 2 T (2i -1) i=l In an obvious way, the action of An(Z2) decomposes the functions into equivalence classes. The problem of counting the number of classes [25] has been solved by Nechiporuk -5- but his proof has not been published. The subgroup of the affine group consisting of translations only is the group r. This group of order 2n is the group of all complementations of variables of Boolean functions. The algorithm to be derived makes use of the fact that the structure of ( (Z2) as a permutation group is GLn(Z2) )2 where the operation is the product of permutation groups previously discussed in section 2.2. We may note that one can form the semi-direct product of 2 and GLn(Z2) in exactly the same way that was done for n. In this case, the product operation is (bl,A1) (b2A2) = ((bl O (b2Al) A1A2) Since forming b2A effects an automorphism of 2' the formation of the semi-direct product requires no additional verification. As mentioned in chapter two, a general algorithm for the construction of Z is not yet known. The problem can be solved in the present case because we know Z and Z has only transpositions CL(Z2) 2

69 as its non-identity cycle structure. If we let vi. denote the cycle structure for a term in Z GL ( ) then we must inquire after the cycle n 2 structure of v.. when pre-multiplied by (say) (0,1)...(2 -2, 2 -). These results have been worked out by Elspqs[l] and are summarized below. Lemma 2. The cycle structure of Oln(Z2) is given by J h 2Tkf 2/ j+1 1 -1 P - k ]2j-1 f f k + 2 f-1 k=l j+l 2ij | f ik if i > 1 k=l 1 qik Proof. Examine the v.. pre-multiplied by the non-identity permutations of 2n Theorem 3. The cycle index for i (Z2) is given by n(n+l) n, t XUij 2 22 (2iXl) uij i= i =1 j=1 zo (z2) = (n+) n L tn a/ a2 (k+l)aj-1 j a. d (a jp-) ajE, n(n+i) 2 k 2 i f 22kC2 C r 2d(2 ) =1 jri k=1l9( I l j- i Pel 1=1 j= \k= z k=i =k+i p=1 q=1 where the sum is over all classes.

70 Using the polynomials constructed by this formula, the numerical results of Table XI were obtained. For 3 < n < 5, the results agree with those of Nechiporuk[PS51. Again Nk denotes the number of classes of n functions with k atoms in their normal form expansion while T denotes the total number of classes. The following results are suggested by Table XII. 0.1 2 4 N = N = N = 1. If n > 1 then N = 1, and if n > 2, then N =2. n n n n n If n > 3, then N5 = 2. The first equation is trivial to verify. Suppose n > 3 and consider the classes for k=3; any set of three vectors may be translated into a basis for a three dimensional space and hence all sets of triples are equivalent. The case k=3, n=2 is trivial since N = N 1. Similar proofs may be furnished in the other cases. 2 2 We note that the class L of linear Boolean functions is preserved n under 0n(Z2) and that there are 3 classes of linear functions for all n. cxy, xy, xy, xy lx + y, x + y, x + y, x + yj x, x, y, y, x y, x y 0] [1]

71 TABLE XI THE TOTAL NUMBER OF CLASSES UNDER'tn(Z2) n T n 1 3 2 5 3 10 4 32 5 382 6 15,768,919 TABLE XII THE NUMBER OF CLASSES OF FUNCTIONS WITH k ATOMS UNDER c (Z2) Nk n \ 1 2 3 4 0 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 5 1 1 11 4 1 2 2 2 5 1 2 2 6 1 3 4 7 1 3 5 8 1 4 8 9 3 9 10 3 15 11 2 16 12 2 23 13 1 24 14 1 30 15 1 30 16 1 38 T 3 10 32 382 n

72 3-9. Summary In this chapter, we have defined five groups on switching functions and calculated their cycle indices using for the most part, structural properties of the permutation groups. The lattice structure of these subgroups is shown below in Figure III. 2'~, - n 2 Fig. III. The Lattice of Interesting Subgroups of (n(Z2) For each of these groups, we have counted the number of classes. In the next chapter the definition of equivalence will be extended and some general theorems about enumerations of Boolean functions will be proven.

CHAPTER IV EXTENSIONS OF EQUIVALENCE OF BOOLEAN FUNCTIONS 4-1. Introduction In this chapter the results about the classification of Boolean functions will be extended in several directions. First, we shall allow operations on the domain and range simultaneously. Then networks of switching elements with different groups acting simultaneously on inputs and outputs will be considered. Finally networks composed entirely of one-to-one functions will be studied. 4-2. Negation on the Range Let us extend the previous results about equivalence of functions by allowing negation of the functions also. It is convenient to obtain the negation of a Boolean function by the action of a negation group to be denoted by j9. Y has order two; one element is the identity mapping and the other element, denoted by Br, has the property: Tr: f — f for any Boolean function f. The situation is now as follows; we have a group 0 defined on the domain of the Boolean functions and a group 7 on the range. The pertinent group on the functions is the exponentiation group O. To count the number of such classes, we may apply the DeBruijn theorem once we have calculated Z M. The action of L on j0,1 is to permute 0 and 1 so that U is actually the symmetric group of degree and order two. 73

74 Thus z = 2 fl + f2) The following lemma facilitates the calculations in using DeBruijn's theorem. Lemma 1. A term h... h in Z gives rise to z ( tjttl tjt) ti itls (h Jr). Proof. We compute'.(h h ) This yields r C ^ (h1.. hr) = T exp(tt ) r 0O -y exp( tjt Zkt) t=l k=l r 00 r = (exp =1 t tj kt is te k=l elta kfunctio, =l where 6i kt is the Kronecker delta function, i.e. 1 kt 1 if i=kt i kt = 0 O otherwise

75 Taking every zi equal to zero gives D (h1... h =t t i Theorem 2. Let J be any permutation group on the domain of Boolean functions. The number of classes of functions under i (transformations of n on the domain and complementation of the range) is given by I (Z (2,2,...,2) + Z (0,2,0,2,...,0,2)) This theorem is applied to obtain the appropriate numbers for the five groups. Theorem 3. The number of classes of functions with tn on the domain and X on the range is 1 2n n 2n-l n+ (2 + (2 1)22 +1 Proof. The result follows from the closed form for Z Theorem 4. The number of classes of functions with rn on the domain and Y on the range is exactly one half the number of classes with just ~r~ on the domain. n - -- --

76 Proof. Since the domain elements corresponding to (0) and to (2 -1) are symmetric, then every term of the cycle index contains a term fl for k > 2. Theorem 5. The number of classes of functions with GL (Z ) on the n 2 domain and R on the range is exactly one half the number of classes with just GL (Z2) on the domain. Proof. Every linear transformation leaves the origin invariant so every term of the cycle index contains a factor fk for k > 1. The calculated numerical results follow. nn nn 1 2 2 2 2 5 6 4 3 30 40 14 4- 2,288 1,992 222 5 67,172,352 18,666,624 616,126 6 144,115,192,505,714,504 12,813,206,169,137,152 200,255,952,527,184 n GLn(Z2) 2Ln(Z2) 1 2 2 2 4 3 3 10 6 4 46 18 5 1,372 206 6 475,499,108 7,888,299 TABLE XIII NUMBER OF CLASSES UNDER GROUPS CONTAINING NEGATION

77 It is interesting to note the ease with which these results were obtained and to compare these methods with those of Elspas - and [261 Ninomiya ] Both these men computed the same results but with considerable effort and only for the group n 4-3. Self-Complementary Classes The results of the previous section are used to obtain some results concerning groups without negation on the range. Suppose is a group on the domain and the number of classes of 1 closed under complementation of the functions is desired. Clearly only classes of neutral functions can have this property. Neutral functions are those functions with as many ones as zeroes in their graphs, i.e. functions of weight 2n-. Theorem 1. The number of classes of functions under M which are equivalent to their complements, i.e. self-complementary, is Z (0,2,0,2,...,0,2). Proof. Let T be the number of classes of functions under 4 alone, note that ZG(2,...,2) = T. Let Nc be the number of self-complementary Gj" n sc classes. Then 1 (Z (2,...,22) + Z (0,2,..,0,2) (T - N) + N 2 n sc sc which implies Nsc Z= (0,2,...,0,2)

78 Theorem 2. The number of self-complementary classes under 2 is n-l (2n _- 1) 22 - n Proof. See the proof of theorem 3 in the previous section. Theorem 3. There exists no self-complementary classes under tn. Proof. See theorem 4, section 4-2. Theorem 4. There exist no self-complementary classes under GL (Z2). Proof. See theorem 5, section 4-2. Now we show the results of the calculations. n 2-G n I(n.. I n GLn(Z2) 11 0 1 0 1 2 3 0 2 0 1 3 14 0 6 0 2 4 240 0 42 0 4 5 63,488 0 4,094 0 30 6 4,227,858,432 0 98,210,640 0 7,679 TABLE XIV NUMBER OF CLASSES OF SELF-COMPTLEMENTARY FUNCTIONS Elspas made an interesting conjecture in relation to his solution of this problem. He suggested that the ratio of the number of selfcomplementary classes to the number of neutral classes went to zero for increasing n. This implies that the phenomenon of the self-complementary class is rather rare. Although Elspas made his conjecture for the group (n we shall now derive it for n(Z2) Then the result will be seen to hold for all groups whose orders satisfy an absolute inequality.

79 In order to obtain an answer we need a lower bound on the number of neutral classes and an upper bound on the number of self-complementary classes. These bounds are obtained in the following lemma. Lemma 5. The number of neutral classes under n (Z2) is greater than or equal to 2n 1 n-l n(n+l) n 2 -2 2 (2i -1) i=l The number of self-complementary functions is less than or equal to 2n-1 2' [22] Proof. The first part is obtained by using the well known - lower bound -, where s is the number of objects on which a permutation group g6~~~~~~~ ^~~~~n \ of order g acts. The result follows upon noting that there are n1) neutral Boolean functions. The second part of the theorem follows 2n-1 from noting that the largest term in Z (0,2,...,0,2) is.... An upper bound is certainly 1 2n-l n-l 1 L 22 - 22 g 2-1 The desired ratio can now be computed, but it is convenient to have an estimate for the binomial coefficient. Using Stirling's formula, one can show that

80 2n n 2n > 2n_ n \2n-1 4 The ratio of self-complementary classes to neutral class under n (Z2) is less than or equal to n-l n(n+l) n n(n+2) n 22 2 2 TT (2-1) 2 n) 2 2 23 i=l T i=l 2n: 2_ o(l) (2ln\ - ~ 2 2n-1 < 2 n-l0(1) 2 22l 22 2n- 1 This shows that the ratio approaches zero for large n and therefore that self-complementary classes are rather rare. Thus, this result is also true for any group whose order is less than that of Jn(Z2). One can show the following stronger result. Theorem 6. Let be any group defined on the domain of F. If the order of does not exceed r2r 2 n-1 n 22 2 e log2n for any positive c, then the number of self-complementary classes of functions tends to zero with the number of classes of neutral functions. Proof. Compute the ratio for the upper bound.

81 4-4. Networks of Switching Functions In this section, attention will be focused on networks of switching functions. The problem to be considered here is exactly the same as counting the number of classes of sequences of k Boolean functions of n variables. That is, the problem is that of classifying sequences of k Boolean functions of n variables under some transformation groups on n variables. One may think of the functions in these sequences as the transmission functions of a switching circuit having k outputs. See Fig. IV for a diagram of the generic network which will be called an (n,k) network. Our (n,k) networks realize the (k,n) sequences of [-53 ] Povarov 5' x x -- fl(Xl'' *' Xn) f (xl'' "'Xn)..X,...Xk o n | tx^fk(X,...,xkn) Fig. IV. A Generic (n,k) Network One may take either of two points of view in this investigation. Networks can be characterized by (1) their structure, i.e. the placement of certain components in arbitrary arrays or (2) by their behavior, i.e. the terminal relations. The former problem has been handled very neatly by Ninomiya for the group of complementations and permutations.

82 Some related results of a special nature have been obtained by Sagalovitch3 ] who obtained the number of one input k output networks whose transmission functions are non-trivial Boolean functions of n variables. In this discussion, the "behavioral" aspect of the problem is completely solved. Before proceeding to the theoretical results, an example of two networks to be considered equivalent under Q3 is given. Let a = (2,5) cE 3 be applied to the inputs of the top network of Fig. V to give the bottom network of the figure. x1f l- - ( xl xx2 x3 ) = X1X2X3 X2 f2(xl,,x) = x +x3 xt -- --— f3(xlx2x3) = x +x ___:,___ - f4(x1,x2,x3) = 1 X. ----— fl( Xl X2'X3 ) = X1X2X3 ---- f2(Xl'X2'X3) = X1+X2 1 _ --- f 1(x1,x2x5) = x x+x X____ f3 (xl',x2,x5) = + x3 L __ fi _f4_f (xx2x3) = 1x2 Fig. V. The Effec of a = (2,) on a ( ) Network The problem is now to count the number of classes of (n,k) networks under any group 0J acting on the domain of the functions, O0,1n. The k2 2n1 total number of such networks is 2k2 since here are 2 choices for each one of the k outputs.

83 In order to modify Polya's formula for counting the number of classes of networks, note that no change has been made in the way that acts on o, n. The only change is in the range. Mappings from 0Oljn into 0,1fk are now of interest so that a new figure counting series is needed. Obviously 2k t (xV....x ) x 2 i=l Usually x, is chosen to be one, but this is of no consequence. Theorem 1. The number of equivalence classes of (n,k) networks (sequences of k Boolean functions of n variables) under a group is given by Z (2k,.2k) Proof. To count the total number of classes, one takes x.=l for 2k [ 1i = 2k for il,. j=l Corollary 2. The total number of classes of (n,k) networks under is 1 k2n (2 n-l 1 (2n + (2n- 1)2n ) 2n

84 Proof. This follows from the fact that _ 2n n 2n-1 Z = 1 (fl2 + (2 - )f2 ) ^2 "2 It is interesting to note that the class of all mappings from {0,13 into {0,1k forms a Boolean algebra of 2 functions in the kO,14 into ~ly forms a Boolean algebra of 2 functions in the natural way. It appears that the generalization of many problems in switching theory to the multiple output case can be handled naturally from this point of view. The calculations have been carried out for the five groups under discussion and the results are given below in Tables XV through XIX. Certain facts may be deduced from the tables. For example, the number of classes under Z1 and GL1(Z2) is 4k since these groups consist of the identity alone.

85 TABLE XV THE NUMBER OF CLASSES OF NETWORKS UNDER 2 n k=l k=2 k=3 k=4 1 3 10 36 136 2 7 76 1,072 16,576 3 46 8,416 2,100,736 536,928,256 4 4,336 268,496,896 17,592,201,773,056 1,152,921,508,63355,378,816 TABLE XVI THE NUMBER OF CLASSES OF NETWORKS UNDER I> / n n k=l k=2 k=3 k=4 1 4 16 64 256 2 12 160 2,304 34,816 3 80 13,056 2,928,640 724,238,336 4 3,984 1,833,052,160 11,745,443,774,464 768,684,844,023,545,856

86 TABLE XVII THE NUMBER OF CLASSES OF NETWORKS UNDER n n k=l k=2 k=3 k=4 1 3 10 36 136 2 6 55 666 9,316 3 22 1,996 384,112 91,604,416 4 402 11,756,666 735,192,450,952 48,047,227,408,513,056 TABLE XVIII THE NUMBER OF CLASSES OF NETWORKS UNDER GL (Z2) n k=l k=2 k=3 k=4 1 4 16 64 256 2 8 80 960 13,056 3 20 1,056 135,040 27,700,736 4 92 320,416 14,333,211,520 916,495,047,958,016

87 TABLE XIX THE NUMBER OF CLASSES OF NETWORKS UNDER tn(Z2) n k=l k=2 k=3 k=4 1 3 10 36 136 2 5 35 330 35876 3 32 271 22,060 3,741,616 4 382 29,821 920,737,780 57,374,820,122,576 While the results of the previous paragraph are of some interest, certain networks are considered non-equivalent which differ only in the order of the outputs. It is desirable to enlarge our definition of equivalence of networks by allowing permutations in the range. More precisely, let the symmetric group on k letters, k, act on the range, and consider two networks equivalent if and only if there is an ate 4 and a permutation a k such that (f (d),...,fk(d)) = (g (1) (d),...,g (k)(ad)) for every deKO,ln. This instance is a special case of the DeBruijn theorem. The calculations have been carried out and are given in Tables XX through XXIV. The number of classes with (say) T2 on the domain and on the range is denoted by T (, f) 2~~~~~~

88 TABLE XX THE NUMBER OF CLASSES OF NETWORKS WITH:. ON THE INPUTS AND ON THE OUTPUTS n k=l k=2 k=3 k=4 1 3 7 13 22 2 7 46 237 1,056 3 46 4,336 356,026 22,921,696 4 4,336 134,281,216 2,932,175,712,336 48,042,795,872,587,776 TABLE XXI THE NUMBER OF NETWORKS WITH e ON THE INPUTS AND k/ON THE OUTPUTS n k=l k=2 k=3 k=4 1 4 10 20 35 2 12 88 484 2,180 3 80 6,616 497,760 31,017,356 4 3,984 916,539,904 1,957,701,217,235 32,031,538,353,966,080

89 TABLE XXII THE NUMBER OF NETWORKS WITH ON THE INPUTS AND O ON THE OUTPUTS n k=l k=2 k=3 k=4 1 3 7 13 22 2 6 34 158 652 3 22 1,056 66,336 3,945,992 4 402 5,884,954 122,543,247,874 2,002,161,498,159,934 TABLE XXIII THE NUMBER OF NETWORKS WITH GL (Z2) ON THE INPUTS AND/ joON THE OUTPUTS n k=l k=2 k=3 k=4 1 4 10 20 35 2 8 46 220 897 3 20 556 23,932 1,214,454 4 92 160,932 2,390,063,996 38,192,408,400,654

90 TABLE XXIV THE NUMBER OF NETWORKS WITH'Zn(Z2) ON THE'INPUTS AND ON THE OUTPUTS n k=l k=2 k=3 k=4 1 3 7 13 22 2 5 22 87 314 5 10 153 4,148 169,495 4 32 15,209 153,668,757 2,391,065,770,697 If complementation of the k outputs of the networks is allowed, then two networks are equivalent if there is an ae and an k i = (il,...,ik) e 2 such that (fl(d),...,fk(d)) 1 \ik: i = (fl (c(d))'','fk (fC(d)) for all de jO,n. The notation f. J(d) is defined as f.(d) if i. = O a a i. fj J(d) = for j=l,...,k f (d) if i = 1 J J The number of such classes can again be determined from DeBruijn's theorem.

91 Theorem 3. The number of classes of (n,k) networks with a group on the domain and the complementing group on the range is 1 (Z (2..,2k) + (2 )Z (0,2k,...,0,2k)) The closed form of theorem 3 arises from the closed form Z. Note Xn that the case when k=l is exactly the case considered in section 4-2. The calculations are shown below in Tables XXV through XXIX.

92 TABLE XXV THE NUMBER OF NETWORKS WITH ^2 ON THE INPUTS AND U2 ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 4 8 16 2 5 22 176 1,216 5 30 2,128 265,728 33,611,776 4 2,288 67,127,296 2,199,025,221,832 72,057,598,064,459,776 TABLE XXVI THE NUMBER OF NETWORKS WITH tn ON THE INPUTS AND k ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 4 8 16 2 6 40 288 2,176 3 40 3,264 366,080 45,264,896 4 1,992 458,263,040 1,468,180,471,808 48,042,802,751,471,616

93 TABLE XXVII THE NUMBER OF NETWORKS WITH n ON THE INPUTS AND k ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 4 8 16 2 4 19 106 676 3 14 556 49,008 5,742,016 4 222 2,945,738 91,901,007,752 2,877,952,247,834,656 TABLE XXVIII THE NUMBER OF NETWORKS WITH GL (Z2) ON THE INPUTS AND g2 ON THE OUTPUTS n2 n k=l k=2 k=3 k=4 1 2 4 8 16 2 4 20 120 816 3 10 264 16,68o 1,731,296 4 46 80,104 1,791,651,440 51,030,940,434,876

94 TABLE XXIX THE NUMBER OF NETWORKS WITHA n(Z ) ON IHE INPUTS AND 2 ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 4 8 16 2 3 11 50 276 3 6 79 2,908 236,176 4 18 7,621 115,125,476 3,585,934,560,176 It is somewhat artificial to consider complementation of the outputs only. One would prefer to consider both symmetries and complementations on the range. This suggests considering the least group containing k and 2 i.e. we shall define c on the range. Without more ado, the calculations are presented in Tables XXX-XXXIV.

95 TABLE XXX ON THE -,. PUTS AND THE NUMBER OF NETWORKS WITH ON THE INPUTS AND ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 3 4 5 2 5 18 51 122 3 30 1,200 45,777 1,476,032 4 2,288 33,601,536 366,543,984,720 3,002,400,587,673,600 TABLE XXXI THE NUMBER OF NETWORKS WITH ON THE INPUTS AND ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 3 4 5 2 6 24 98 194 3 40 1,676 63,440 1,992,430 4 1,992 235,384,592 244,644,311,176 2,002,158,848,764,301

96 TABLE XXXII THE NUMBER OF NETWORKS WITH Cn ON THE INPUTS AND 7/ ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 3 4 5 2 4 13 34 640 3 14 308 8,906 257,658 4 222 1,476,218 15,320,103,918 125,147,156,711,032 TABLE XXXIII TIE NUMBER OF NETWORKS WITH GL (Z2) ON'THE INPUTS AND ek ON THE OUTPUTS n k=l k=2 k=3 kk4 1 2 3 4 5 2 4 13 36 95 3 10 146 3,178 80,o36 4 46 40,422 298,842,656 2,387,346,322,704

97 TABLE XXXIV THE NUMBER OF NETWORKS WITH O (Z2) ON THE INPUTS AND M k ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 3 4 5 2 3 8 19 41 3 6 49 632 11,917 4 18 3,963 19,245,637 149,471,180,139 DeBruijn's theorem allows us to consider any groupc/f on the domain and any group on the range. The analysis of all remaining cases is completed by allowing GLn(Z2) and a n(Z2) on the range. The results are given in Tables XXXV through XLIV.

98 TABLE XXXV THE NUMBER OF NETWORKS WITH 2 ON THE INPUTS AND GL(Z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 3 4 4 4 2 7 21 27 28 3 46 1,531 14,056 39,839 4 4,336 44,782,251 104,751,025,086 57,280,291,273,345 TABLE XXXVI THE NUMBER OF NETWORKS WITHYk- ON THE; INPUTS AND GLk(Z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 4 5 5 5 2 12 35 46 47 3 80 2,266 19,930 55,767 4 3,984 305,552,546 69,945,183,326 38,191,772,055,973

99 TABLE XXXVII THE NUMBER OF NETWORKS WITH n ON THE INPUTS AND GLk(Z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 3 4 4 4 2 6 16 21 22 3 22 392 2,920 7,923 4 402 1,966,074 4,579,140,552 2,587,516,975,717 TABLE XXXVIII THE NUMBER OF NETWORKS WITH GL (Z ) ON THE INPUTS AND GLk(Z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 4 5 5 2 8 20 27 28 3 20 206 1,204 3,071 4 92 54,155 85,552,416 45,568,388,658

100 TABLE XXXIX THE NUMBER OF NETWORKS WITH n(Z2) ON THE INPUTS AND GLk(Z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 3 4 4 4 2 5 11 15 16 3 10 64 276 653 4 32 5,276 5,534,421 178,471,391 TABLE XL THE NUMBER OF NETWORKS WITH n ON THE INPUTS AND Ok(z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 2 2 2 2 5 9 10 10 3 30 443 2,104 3,763 4 2,288 11,211,435 13,098,898,366 3,585,768,962,689

101 TABLE XLI THE NUMBER OF NETWORKS WITH a ON THE INPUTS AND (tk(Z2) ON THE OUTPUTS n.k 2 n k=l k=-2 k=3 k=4 1 2 2 2 2 2 6 11 12 12 3 40 590 2,828 5,066 4 1,992 76,384,114 8,747,130,342 2,390,901,609,645 TABLE XLII THE NUMBER OF NETWORKS WITH C ON THE INPUTS AND k(Z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 2 2 2 2 4 7 8 8 3 14 124 504 880 4 222 494,298 547,849,868 539,100,216

102 TABLE XLIII THE NUMBER OF NETWORKS WITH GL (Z2) ON THE INPUTS AINDI.,k(Z2) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 2 2 2 2 4 7 8 8 3 10 60 214 368 4 46 13,733 10,724,116 2,854,852,38 3 TABLE XLIV THE NUMBER OF NETWORKS WITH:n (2 ) ON THE I NPUTS AND'(Z ) ON THE OUTPUTS n k=l k=2 k=3 k=4 1 2 2 2 2 2 3 5 6 6 3 6 24 70 116 4 18 1,430 700,173 179,125,249

103 4-5. Invertible Boolean Functions There is another interesting question to ask about the (n,k) networks. This problem is to determine the number of classes of invertible functions on networks. C. S. Lorens has studied this problem, and his [22 ] results will be derived and generalized Since Boolean functions are also ordinary functions, a function f is invertible (i.e. has an inverse) if and only if f is one-to-one and onto. That is, consider the one-to-one onto mappings of {0,1} into J0,1. These are just the 2 n permutations of 0, Theorem 10 of section 2-1 was proved in this thesis for this application. We shall now derive a lemma which will facilitate the calculations. Lemma 1. A term of the form..i. Zi b(l+klzk ).. (l+ksZk sI ~~~ ~1 = z =.2 = z l=l s b p k Pm. if ip = kl,...,i = k yields 0 otherwise.

104 Proof. Notice that unless the cycle structure of the term involving the differential operator is the same as the term involving the variables, the result will be zero. If i1 = k,...,i k then ables,1 1 s s m = jl...,m = s and the result follows from the rules of differentiation. First apply this lemma to the case where acts on both the domain and the range. Theorem 2. The number of classes with 2 acting on both the range and the domain is given by ( 2n, + (2n 1)22n-1)22 1) On' Before proceeding to the calculations, the reader is reminded of a remark made in the proof of theorem 2-1-10. We noted at that time that the mapping f -> f - is one-to-one. From this fact, it was remarked that the number of classes with a group X on the domain and a group - on the range is the same as the number of classes when acts on the domain and 6 on the range. The calculations for the other cases have been carried out and are summarized in Tables XLVI and XLVII. Table XLV shows the number of invertible functions. It would require a computer to evaluate the results for n=5 and most computers would require at least triple precision arithmetic to accomplish this.

105 TABLE XLV THE NUMBER OF INVERTIBLE FUNCTIONS n 1 2 2 24 3 40,320 4 20,922,789,888,000 TABLE XLVI THE NUMBER OF CLASSES OF INVERTIBLE FUNCTIONS WITH THE SAME GROUP ON BOTH THE DOMAIN AND THE RANGE 1 n 1n 2 1 GLn(Z2) n(Z2) 1 1 2 1 2 1 2 6 7 2 2 1 3 924 1,172 52 10 4 4 81,738,720,000 36,325,278,240 142,090,700 52,246 302

106 TABLE XLVII THE NUMBER OF CLASSES OF INVERTIBLE FUNCTIONS WITH DIFFERENT GROUPS ON THE DOMAIN AND RANGE n on Domain n on Domain on Domain Range on Range non Range 1 1 1 1 2 3 3 2 3 840 196 154 4 454,486,432,000 3,406,687,200 2,270,394,624 n n^ on domain on domain on domain GL (Z2) on range GL (Z2) on range GL (Z2) on range 1 1 2 1 2 1 3 1 3 30 56 10 4 64,864,800 43,265,728 2,705,820 n on domain on domain on domain GLn(Z2) on domain (n n r e (Z) on r) range (2) on ange 2 on range on ane 1 1 1 1 2 1 1 1 3 16 10 8 4 4 4,073,400 2,705,820 172,194 3374

107 One might be interested in comparing the results of the previous section with these results on invertible functions. In both cases n-input, n-output networks with groups on the domain and the range were studied but now the functions are required to have inverses. Comparing the results of this section against T( (, ) for (n,n) networks, one finds that the ratio of the number of classes of invertible functions to T( O, A) approaches zero for large n. Thus, the invertible classes are comparatively rare.

CHAPTER V APPLICATIONS 5-1. Switching Theory Chapter I presents a brief history of the development of combinatorial methods in switching theory. In this section, the principal applications of n1 to synthesis problems in the theory of switching are presented. Since we shall have occasion to discuss the group invariance problem for switching functions in some detail, the problem is stated precisely. The problem is to find a complete set of invariants ly,..YGk of a group~ defined on switching functions such that for any two functions f and g, f and g are equivalent iff ei(f) = g) for i=l,...,k The background for the use of n in synthesizing switching functions of four variables is as follows. Polya ] first showed that the 65,536 Boolean functions of four variables are resolved into 402 symmetry classes by On' The Harvard Computation Laboratory[ 7] computed [12] a representative function from each class. Golomb[ found a complete set of invariants for In and gave a canonical form for switching functions. In unpublished works, Moore, Gould, and others have compiled absolutely minimal networks for the 402 representative functions of four variables. An early version of the table is reprinted in Higgonet and Grea[19]. 108

109 Example: Given the function f(xl,x2,x3)) = xx2x3 + XX2X3 + xlx2x3, construct a minimal network for realizing f. f can be seen to be equivalent to the function x2x3 + xlx2x under the transformation ((010), (12)(3)). The latter function is known to have the absolutely minimal network shown in Fig. VI. (See [351 Seshu and Reed[3 Fig. VI. The Absolutely Minimal Network for xlx2x3 + x2x3 It would seem desirable to extend this general procedure for the group ( (Z2). This group is so large that the enumeration of classes could be carried out for n=5 if we could solve the group invariance problem for (n(Z2). All the practical applications of our ideas to switching theory require the solution of this problem, and it is strictly a non-trivial problem. At the present time, the group invariance problem has been solved for Q by Golomb. Since the solution of the problem for the unimodular [42] group in a related case is given by Weyl, and because the unimodular group is identical to GL (Z2) over the field of two elements, a partial solution to the invariance problem for GL (Z2) is known. The finding of solutions for these group invariance problems is a

110 difficult, but an important task. The extension of this synthesis approach sketched above is important in switching theory. The solution of the invariance problem would also provide a canonical form for codes, but this latter problem will be considered next. 5-2. Error Correcting Codes A problem of considerable importance in the theory of error correcting codes is the problem of enumerating equivalent codes. [4i ] Slepian has solved this problem for (n,k) codes under the general linear group. In this section, the connection between our results and those of Slepian will be indicated. In particular, Slepian's work is extended by giving the number of (n,k) codes under Ck(Z2). For the purposes of the development, it is assumed that the reader is familiar with the theory of group codes which was developed, to a large extent, by Slepian; this material is reported in an easily readable form in reference[ 9. The notation used in this section is compatible with the literature of coding theory, but unfortunately, differs somewhat from the rest of the thesis. Consider the vector space of n-tuples over Z2; a sub-space of dimension k is called an (n,k) code. Such a code contains 2k vectors. A more compact description is obtained by considering the code to be given as the basis of the subspace. If the basis vectors are written in a k x n matrix G, then G is called the generator matrix of the (n,k) code and G is of rank k. Two generator matrices of (n,k) codes _(1 and %-, are said to be equivalent iff there exists an AeGLk(Z2) and there is an n x n permutation matrix P such that -f1 = A -OP.

111 The quantities which are desired are the following: Tnk The number of equivalence classes of k x n matrices with no columns of zeroes. Tnk: The number of equivalence classes of k x n matrices with no repeated rows and no columns of zeroes. Snk: The number of equivalence classes of (n,k) codes with no columns of zeroes. Snk: The number of equivalence classes of (n,k) codes with no repeated columns and no columns of zeroes. Wnk: The number of equivalence classes of (n,k) codes allowing zero columns and repetitions. Nnk: The total number of distinct (n,k) codes. First, Slepian's results for GLk(Z2) are derived and then extended to 6k(Z2). In his first paper, Slepian showed that k-l IT (2 -2i) N _ IrPi=O nk k -1 n T (2k-2i) i=O A simple calculation shows that n Wnk =~ S ik i=l and also that the S's are related to the T's by Snk = Tnk - T nk nk nk-1

112 _ = Tk - T. nk = nk n,k-1 Thus, all the problems can be solved by computing Tnk and T. Theorem 1. T is given as the coefficient of x in n,k- —. 2n y 22 YGL () (1+x, l+x,...1+x ) where YGLk(Z2) (' 2n) = ZGLk(Z2) (f2l'' n Proof. The transition from switching functions having n minterms and k variables to a k x n matrix occurs by writing the minterms as row vectors of a n x k matrix and transposing the matrix. Exclusion of the zero-columns of a matrix is the same as excluding the minterm 1... x. This is accomplished by dividing out by fl in the cycle index of GLk(Z2). Theorem 2. T is given as the coefficient of x in 1 1 YGLz (-' 1 1-x Proof. The store enumerating series is 1 + x + x2 +... 1 1-x Noteries for this is the first timwethat we have had to endure an infinite series for the store generating function.

113 Sample Calculation: Suppose k=2. Then from appendix III, 1 4 2 + 2f ZGL2 (Z2) (f 1 3fl2 +2f 3) yGL (z) = (f+ 3flf2 + 2f3) YGL (Z l+xl+x2 l+x3) = 1 + x + x2 + Thus Ti = 1 for i=0,...,3 i2 T' = 0 for i > 4 i2 yLx2 1x x 3 l 1 2(+ 3 + Xi + 2 ) 1- -x 2 3 2 1-x 1-x 2_ j=0 The coefficient of x is n2 + 6n+ 12 2 1^2 if n - 0 mod 6 12 (n+5)(n+l) (+(l12 if n - 1, 5 mod 6 (n+4) (n+2) if n - 2, 4 mod 6 12 (n+3)2 12 if n - 3 mod 6 Now the case of the affine group is considered. Equivalence under (L k(Z2) is also a natural concept. Since the columns of zero no longer play a special role, then one need only compute the following quantities,

114 Tnk and Tnk where we now use these symbols in their previous meanings except for dropping the condition on zero columns. n Theorem 3. T is the coefficient of x in n,k - n Zk (Z ) (l+x,...,l+x ) Theorem 4. Tn is the coefficient of x in nk Z () (1 1 ) Z (Z2) l ex v nl 2n Otk l-x Now, a sample calculation. 1 2 k=l Zf (Z-) (f2 + f (l+x,l+x) = + x + x2 Ol(Z2 2 i.e. T = 1 for i=0,1,2 00 T Xn 1 1 1+ nD n2' (l-x) 1-x n+2 if n - 0 mod 2 T - nl n+l if n 1 mod 2

115 Suppose n=4, then S T 35 41 41 3 The 16 matrices are partitioned into 3 equivalence classes as shown below: (oooo0), (1111) (0001), (0010), (0100), (1000), (1110), (1101), (1011), (o011)] (0), (0101), (0110), (), (1010), (1001), (1100)] The calculations for the parameters which Slepian used are not included because of the complexity of the computation. Special computer programs are required to handle this problem. 5-3. Graph Theory It is perhaps superfluous to mention the connection between this work on Boolean functions and graph theory. Polya's original paper[30] of over one hundred pages, developed the fundamental theorem and used it to solve many enumeration problems in graph theory. In this section, the connection between the product defined in chapter two and k-colored graphs is shown. A graph is an ordered pair < G,R > where G is a set (of vertices) and R is a relation on G. aRb holds for a,b cG iff there is an edge connecting a and b. A k-colored graph is a triple < G,Rf > where G and R are defined as before and f is a function from G onto Zk =1l,2,...,k7 such that aRb = f(a) $ f(b) Two graphs < G1,Rl,fl > and < G2,R2,f2 > are said to be chromatically isomorphic iff there exists an isomorphism S of the (uncolored) graphs

116 and a permutation c of Zk such that c(f1(a)) = 2(f(a)) When the term "the number of k-colored graphs" is used, it is to be understood that we mean the number of chromatically non-isomorphic graphs. We now specialize to k=2 for bi-colored graphs. Harary has shown that it is sufficient to compute the cycle index of the line group of the complete graphs on mn points with myn; symbolically K mn This group has been shown to be X ( where ) denotes the Cartesian product of permutation groups. Turning now to the case where m=n, the line group is larger than En X En because one can interchange the colors in accordance with the definition of chromatic isomorphism. Harary proved that the line group of K is what he called the exponentiation of 2 and, but nn n what is actually the product defined in chapter two so that the algorithm (theorem 2.2.4) solves some special cases of enumerating bicolored graphs. Harary has presented an algorithm for the solution of this problem. 5-4. Post Algebras It seems natural to extend the results which wre developed for Boolean algebras to Post algebras. Most of the background can be [32] found in reference[32]. Post functions are defined as mappings from n -> Zm where, as usual, Z =,,...,m-l. Thus, there are m Post functions. First, define An on the variables just as for Boolean functions

117 v.i.z. for ac. cf(x1,..,xn) = f(xa(,))..x (n)) These permutations of the variables induce permutations of the domain which are automorphisms as before. In fact, the automorphism group of the Post algebra is isomorphic to the symmetric group on m letters. Because the mapping which associates with each permutation of the variables a permutation of the domain is a homomorphism, the coefficients of the cycle index are the same as in section 3.5. Clearly, the cycle structure associated with each class is changed. We now calculate the effect of a cycle of length k. A cycle of k length k affects m domain elements. Consider these elements to be in a one-to-one correspondence with the integers O,1,...,m -1. Lemma 1. If q is any integer such that 0 < q < m -l, then the least integer d such that d k m q =q mod (m -1) must divide k and conversely. k Proof. For the converse, choose q = d Now let d be the least m -1 d k k k integer such that m q - q mod (m -1). Then, since m - 1 mod (m -1) k k m q q mod (m -1) Assume k = dp + r where O < r < d

118 dp r k md mq q mod (m -1) /d p r- k q(md)p m - q mod (m -1) d k Repeated use of the congruence m q - q mod (m -1) yields r k q m q mod (m -1) which is a contradiction unless r=O. Theorem 2. A cycle of length k in induces permutations on the domain whose lengths are divisors of k and moreover every divisor of k is the length of some cycle. k Proof. One writes the numbers from 0 to m -1 in radix m notation and in order. The effect of a permutation of length k can be obtained by removing the left-hand column and writing it as the right-hand column. This has the effect of multiplying each number by m. Thus, a number 2 d. k q goes successively into mq, m q,...,m q q mod (m -1). Thus, the length of the cycle is the least positive integer d such that d. _ - k m q = q mod (m -1) Theorem 35 A cycle of length k in induces a permutation on the domain whose cycle structure is given by T fdh(d) dl k where the f are the indeterminates of the cycle index and h(p) mdP where (P-) is the Mobius function.~

119 Proof. The previous theorem gives the cycle lengths and their multiplicities are given by the requirement E d h(d) m dlk By the Mo6bius inversion theorem h(k) = L m4(d) k dk d Theorem 4. The cycle index of n as a group on the domain of the Post functions is n_ n n ( r Z -- U —-- X i=l )J where the notation y means y y y. The number of classes where the notation y means y X y K... X. The number of classes is calculated for a few small values of m and n; this is shown in Table I. It is interesting to note that there are always n+m-l1 m-1 m transitivity classes consisting of just one function. These are the symmetric Post functions. TABLE XLVIII THE NUMBER OF CLASSES OF POST FUNCTIONS UNDER THE SYMMETRIC GROUP \ n m 1 2 3 4 2 4 12 80 3,984 3 27 10,206 1,271,126,683,458 * 4 256 2,148,007,936 * *

120 Turning now to the complementations of the variables there are two different types of complementation used in Post algebras. The first type is shown below. P -P 0 1 1 2 2 5 m-2 m-l m-1 0 Thus, a cyclic permutation is the first analog of complementation. For the complementation of a single variable, the appropriate group is the cyclic group of order m generated by (O,1,...,m-l). The cycle index of this group, Am, was given by Polya as m y dd ^~m ~m where c(a) is the Euler p function, i.e. the number of integers not exceeding a and relatively prime to a. The cycle index of the group of complementations for n variables, I, is now derived. Theorem 5. The cycle index of n is given by m z = t- ) n m dim td Im Proof. Clearly the structure of the complementation group on the n variables is 2i X... >< L Thus, it is sufficient to evaluate

121 n n m X m S p(d) fd i=m dim But this is n m E'X (d,n) fd m dim since the cross operation applied to the indeterminants along with the property of LCM's that if dim and tim, then < d,t >(m gives simply the divisors of m as the cycle lengths. It still remains for us to determine what the coefficient' (d,n) is. It is clear that X(d,n) mn dim since the sum of the coefficients must be the order of the group. By the f6bius formula'X (dn) = Z tnl ()( t d It is interesting to note that if m=p, a prime, then this formula reduces to n n-l (fP + (p -1) f P n 1 which is theorem 3-4.7. The case p=2, is theorem 3-4.6. Now the second type of complementation which is used in Post algebras is considered. This function is defined by its graph

122 P -1P O m-1 1 m-2 2 m-3 m-2 1 m-1 0 For: m 0 mod 2, the associated group has cycle index m 1 2 f22 zy = 2(fl+ f22) If m 1 mod 2, then the cycle index is m-1 z = ft1 (f + fl2 ) L"~ 2 1 12 Now we generalize to the case of n variables. Theorem 6. The cycle index of the complementing group 7Z is n m 1 m n_ 2 (f + (2n-1) f2 ) if m 0 mod 2 2n m 2 n-k k n n-k m (m -1) n k2U f f if m 1 mod 2 Proof. First we derive the formula if m is even. In that case one can arrive at the result by induction on n. The computation of the induction step is included.

123 n-l n- n-1 n n-1 m m y -; - 2 1 1) 2 ) X 2 + f n n m m 1 m a-l n 2 n-1 2 - (fl + (2 1 -1) fn + f( + (2 -11) f2 n 1 (fm + (2n -1) 2 ) To handle the case where m is odd involves an interesting calculation. Since the cycle indices form a commutative ring under the ordinary addition and the "cross" multiplication, the binomial theorem holds. Thus, when m - 1 mod 2, 1 xn k Xk =n Kl ) I 2 f 2 1 ( ) f f 2 M-1 n n -kl n-k k 1 n n-km (m -1) -1 n fM. f2 2n O n 1 2 Q.E.D. It is now possible to combine the results obtained and form the semidirect product of these groups and compute the cycle index of this group, but the details are straightforward.

124 5-5. Sequential Machines There are many aspects of automata theory to which the present methods apply. Only one application will be discussed, the state assignment problem. Let q = < S, cP1,P2 a > be a sequential machine where S denotes the set of internal states, aeS is the initial state and 1p and c2 are the direct transition functions. Let S = r. Definition 1. A state assignment cp is defined as a one-to-one function cp: S t-kO,13k where k >- - log2rJ Certainly two state assignments are equivalent if their images are equivalent under n since permutations and complementations of the range do not change the cost of the assignment. Consider the problem of counting the number of state assignments. Theorem 2. Let < = < S, cp1,2 a > where S = r. The number of state assignments involving k (k > - {-log2r~ ) bi-stable memory elements (1-1 mappings from S into 0,1k ) is given by d- Z (l+z,1,...,1) dr dzr k evaluated at z=O Proof. This is a special case of theorem 10, section 2-1. where Z = f. Note that this result may be written ^ 1

125 X, z (ilb (a) 2 k' ae k where bl(a) is the number of cycles of length one in the permutation a. Corollary 3. Let O = < s, (1,2, a > where S = r. The number of state assignments involving k states where k = - -log2r is (2k-1) (2k-r) k! Proof. In this case only the identity term in 4k can contribute to the sum so that the result is k kk kri 2kk 2 rk = 2k r 2 2 k; r j 2k k' r: (2k_r) (2k-1) (2k -r) k; This result was derived in the paper by McCluskey and Unger, reference [24]. Theorem 2 provides a complete solution to the unrestricted counting problem for state assignment. However, the result also counts degenerate state assignments when some state variable is constant over the entire assignment. Also, if k > - [-log2rJ one wishes to divide out by the symmetric group on S. Theorem 2-1.10 may be used in that case to divide out the symmetries on S, but the degeneracy must be handled by special

126 considerations. Rather than derive the formula, the result which has been obtained by Gilbert is included. Theorem 4 (Gilbert). The number of non-degenerate state assignments for r states and k bi-stable memory elements is k k S(k+l, j+l) 2 - (2) j=l where S(n,k) are Stirling's numbers of the first kind.

CHAPTER VI UNSOLVED PROBLEMS There are a great many problems still to be solved. First, a complete theory of permutation groups involving new "products" which are sufficient to decompose groups which occur in interesting problems needs to be constructed. One also needs necessary and sufficient conditions for the decomposability of such groups along with algorithms for combining the cycle indices of constituent groups to obtain the cycle index of the composite group. For the practical implementation of our results in switching theory, the group invariance problem must be solved for the following groups n <2 a n(Z2)' Although some partial results are known, complete sets of invariants for these groups on Boolean functions are not yet known. The solution of this problem is facilitated by some recent work of Lechner[2-] in preparing a vector space representation of switching functions. A number of basic enumeration problems are unsolved in automata theory. The number of strongly connected machines is unknown along with the number of equivalence classes of behaviorially equivalent machines. The investigation of the automorphism groups of machines has 127

128, just begun, but there is surely a close connection between the structure of the automaton and the structure of its automorphism group. Many of the enumeration problems for automata may be reformulated as problems involving the enumeration of certain types of labelled graphs. This reformulation involved mapping one unsolved problem onto another, as there are still many unsolved problems of this type in graph theory. It is unknown how many transitive relations of a set of m elements there are. Closely related to this problem is the problem of counting the number of equivalence classes of Boolean connection matrices.

APPENDIX I CYCLE INDEX POLYNOMIALS FOR 1 f2 + f2 14 f2 f 4 1 2 2 3 6 +3f 4 f28 + 26f f3 +6 24 2 1 3 -2l 1 1 2 1 6 2 6 1 8 4 120 1 1 f2 +1 2 1 3 f2 + fl (f2 + 1 6 f8 + 15 8 20 + 8 0 f84 f2 f6 + 30 f4 f2 f6 + 24 f2 f6 6 __ff64 + 15 f32 f16 + 45 f16 f24 + 4 fl6 f16 + 15 f8 28 720\1 2 2+ i1 2 1 3 1 2 + 120 f8 f4 f8 f+ go f f4 f + 40 f f0 + f f6 f 4 12 2 269\ + 144f f + 120 f2 f f f 1 5 1 2 3 12 129

APPENDIX II CYCLE INDEX POLYNOMIALS FOR n n~l n 7n n=l 1 2 + f 1/=2 2 \ n=2 4 +3 2 + 23 f 2 + 2 ff) i/~8 42 2 2 4 n=3 f +1 f4 + 8 f2 f2 + 8 f2 f6 + 6 f4 f2 + 12 f ) 18 2 + 1 f2 6 3 rn=4 1 16{ + f51 f8 + 48 f21 f2 f4 + 48 f28 + 12 f8 f4 + 84 f44 1 2 1 6 4 8 88 4 4 6 4 4 22 + 12 fl f2 + 32 f4 f3 + 96 f22 f ) n=5 (812 + 231 f + 20 f6 f + 520 f4 + 80 fl f3 + 720 f f6 4 2 4 4 2 f + 480 f3 + 160 f f2 f f + 20 f2 f2 + 24 f f2 f + 48 f 1 2 3 6 4f12 1 2 f4 8 + 240 f + f f + 60 2 + 84 f f + 384 f2 f+ 3 n=6 1+ 1053 + 4920 f + 10 f16 f24 46o8oz2 1 24 1 2 6 16 8 8 8 28 8 4 8 1 + 160 f6 f36 + 5280 f28 f8 + 120 f8 f28 + 960 f f f4 1 3 2 6 1 2 1 2 3 6 + 3840 f f4 + 720 fl 4 f f2 + 5760 f8 + 2160 f f2 4 20 2' ~o 4 6 12 4 12 + 640 f4 f20 + 1920 f2 f60 + 1440 f4 f2 f12 + 2304 f4 f12 13 26 1 24 2 + 6912 f2 fl + 3840 fl f + 840 130

APPENDIX III CYCLE INDEX POLYNOMIALS FOR GL (Z2) n GLn(Z2) 1 f2 2 2 4 + 3 f2 f + 2 f f5) 3 (f1 +21 f f 2+ 42 f1 f + 56 f 3 + 48 ff f) 1 if16 8 42f [4 1 1 f(f6 + 105 f8 f + 210 fl f + 1260 f22 f4+ 2520 f2 f 2101 2 124 4 2 224 + 112 f f5 + 1680 f f f2 + 1120 f f + 36 f2 f f2 1 3126 1 3 12 3 6 + 5760 fl f2 + 1344 f f5 + 2688 f fL5 1 (f32 16 8 8 4 44 2 6 5 9,999560 1(f32 + 465 fl6 f2 + 26,040 f8 f2 f + 31248 f f2 f6 2 f13 8 12 4f6f4 + 624,960 f2 f2 f4 f6 + 6510 f f2 78,120 f f f 1 21 4 2 2 f 2 4 + 19,840 f8 f3 + 416,64o f4 f2 f4 f + 855,280 f2 f3 f f f2 1 3 2 2 3 6 160 4 461 + 55,552 f2 f + 855,280 f f2 f + 476,160 f f 1 3 153 16 17 2 26 1 2 2 f 95220 fl f3 f7 f21 + 666,624 f2 f + 1,428,480 f f f f + 1,555,248 f2 f5 + 1,955,560 fl f31) 131

132 Z 1 G Z 1953 f 2 f16 + 468 720 f16 f8 f GL6(Z2) 20,158,709,760 f + 195 1 + 4820 4 8G4 = I 2 6 8 + 26,248,320 f 24 + 314,979,840 f4 f2 f f4 + 26,248,520 f f2 4 1 2 4 f8 2 5 6 z6716 24 8 12 8 + 629,959,680 f2 f2 f4 f8 + 136,710 f 6 f24 + 9,843,120 f8 f12 f8 + 629,959,68o0 2 4 % 1 2 1 2 4 4 6 12 8 28 16 16 + 91,869,120 f f2 f24 + 234,360 f8 f2 + 333,312 f1 f 6 ~ 9770 2 41 2 21 3 2 + 34,997,760 f8 f2 f3 + 419,973,120 f4 f f4 f f2 f + 839,946,240 f f2 f2 f3 f6 f 6 + 69,995,520 f f2 f f6 1 f8, 4 2 4 2 34,283,520 f8 i 2 7 i4 + 34,283,520 f 8 f8 + 719,953,920 f4 f2 f4 f2 2 72 4 f12 +, 1,439,907,840 f2 f2 f4 f7 f4 f28 + 223,985,664 f fl5 + 671,956,992 f f2 f f6 f + 447,971,328 fl f5 1 2 5 10 9 1 15 * 1,43,913984 f0 2 f f5 f2 + 3,901,685,760 f2 f2 1 2 15 30 + 1 31 + 447,971,328 fl f5 f f5 + 895,942,656 fl f3 f5 + 422,830,080 fl f + 1,919,877,120 f2 f2 f f2 + 18,665,472 f4 f20 + 279,982,080 fl f f8 + 839,946,240 f2 f 2 f69 + 111,104 fl f 2 + 34,997,760 f f5 f8 123 1 153 6 + 419,973,120 fl f3 f6 f2 + 719,953,920 fl f7 f4 1,919,877,120 fl f6 + 319,979,520 f f7 + 639,959,040 fl f 2 + 55,996,416 f2 f f3 f) 12 Soi

APPENDIX IV CYCLE INDEX POLYNOMIALS FOR t (Z2) n ztn(Z2) 1 2 1 1 + f 2 21 4 + 6 f + 6 f4 + 8 fl f fl 31 3 2 2 3 1 f8 + 49 f4 + 42 f4 f2 + 252 f24 + 168 f 2 + 168 fA f2 f + 584 fl f + 24 + 224 f + 224 f f 17 15 26 4 2256 f16 + 645 f28 + 210 f! f4 + 1,344 f44+ 840 fl f2 + 322,560 1 2 1 2 4 1 2 + 5,040 f4 f2 f2 + 5,040 f2 + 20160 f2 f2 f + 20160 f 1 2 4 "2 4 1 2 4 8 + 1792 f f + 26,880 f f f + 26,880 f 2 f f2 153 153 6 12 53 6 + 4480 f4 f + 13,44 f2 f2 + 46,080 fr f2 + 46,080 f f4 1-3 2 f14 + 4,oo008 fl f15 + 21,504 f, f9 5 319 979,520 f2 + 32,81 + 950 f f + 2,455,200 f 844 8 426 + 104,160 f8 f f + 312,480 f2 f4 + 2,499,840 f4 f f6 + 28442 2 2 + 3,888,640 f4 f4 + 14,999,040 f8 + 9,999,360 f2 f2 f f8 812 284 8 2 + 26,040 f f+2 + 624,960 f4 f f + 79,360 f8 f8 4242 2 2 + 3333,120 f4 f2 3 f6 + 19,998,720 f2 f2 2 2 2 2 10 + 1 2,4 80 fl f3 f12 + 888,832 f f + 14,221,512f f5 + + 13,332,480 fl ff 135

13 51 2 22855,680 2 f2 f7 + 22,855,680 f4 f 5 + 11,427,840 f2 f + 22,85568 f f f 22,855,68 f + 30,474,240 fl f f f + 66598 f2 + 10,665,984 fl f 2 23 11118 7 21 1 52 21,331,968 fl f1 + 21'331968 f2 f3 + 61,931,520 f f + E2,499,8410 1f f1) + 2,499,84o f2f)

APPENDIX V HARARY'S DEFINITION OF THE EXPONENTIATION GROUP In this appendix, we shall review Harary's definition of the exponentiation of two groups. It will be shown that this group product does not occur as the structure of (n as Harary has sugJn gested. Let X = {xl...,x. and let ( be a permutation group of degree a and order m acting on X. Let ~jbe a group of order n and degree b acting on object sety Y. Then consider YX, the class of all functions O-L from X to Y. The group S is constructed* by first permuting a domain object by aCe Ot and then permuting the images in Y for each domain element by elements of i. More precisely, if ye M, then for feX, /f = if(ax) i=l,...,a. this is Harary's definition. Table XLVIX summarizes the pertinent parameters of Harary's group. The symbol denotes the grou constructedere and is Harary *The symbol __ denotes the group constructed here and is Harary's original notation. In chapter II, the same notation is used for a different group. No confusion will result because the use of Harary's group is confined to this appendix. 155

136 Object set X Y X Degree a b ba a Order m n mon TABLE XLVIX THE PROPERTIES OF Now we shall show that Harary's claim that an is permutationally n Tnn equivalent to n must be false. We have noted in the past that /w ~~~~n n must be of degree 2, i.e. it is a permutation group on the domain only. Thus, Harary must want to take the degree of to be n and the degree of 72 to be 2. The n objects which permutes are, of course, the integers l,...,n. But this means that the object set of n is the class of all mappings of l,...,n into O0,1., but these objects are not the Boolean functions of n variables, nor are they the domain of the Boolean functions. The only other possible interpretation of Harary's statement is that he wants the degree of ~2 to be 2 and the degree of to be 2 n i.e. n defined on the domain. Now this is reasonable, but it points n rn out the fundamental error since, in this case, the order of would be n' 2 which is not the order of on. Explicitly then, Harary's mistake was to define the B. as mappings on the range when, in fact, they are mappings on the n individual sets t0,1} which comprise the domain.

APPENDIX VI DERIVATION OF THEOREM 2.2.4 The derivation of Z n provides some of the background for the present proof. We shall use the fact that n'' is isomorphic to the complete monomial group of degree n of I (cf. Ore[28] It was previously shown(in the derivation of Z C ) that it is sufficient to jn consider a cycle of the form m = (0,...,0,) (l,...,k) where, = 1 (Cf. Ore [8], theorem 7.) We shall now derive the cycle structure induced by this term. In the process of the derivation, Ore's theorems 4 and 5 will be strengthened slightly. Clearly the canonical term has order kp. The cycle lengths must divide kp and their LCM must be kp. Suppose dlkq for q < p, then Pk(pl) (d) = d = (ap, a1) (d). The assumption that the terms in Z have no fixed points insures that every digit of the radix m k(p-l) expansion of d is changed, so d is not invariant under k(p-1) The argument for the converse is given similarly to the derivation of the cycle structure of Z. Thus, the cycle structure corresponding to =a (1,2,..o,k) is _ ^r ek,(a) 1 X b f k g p dlkp d q<p The exponents may be calculated recursively as Slepian did or by by deriving a generalized version of the Mobius formula. The latter approach yields 137

(D I 1- | T=~

BIBLIOGRAPHY 1. Artin, E., Geometric Algebra, Interscience Publishers, Inc., New York (1957) 2. Ashenhurst, R. L., "The application of counting techniques," Proceedings of the Association of Computing Machinery, Pittsburgh Meeting (1952), pp. 295-505. 5. Burnside, Theory of Groups of Finite Order, Cambridge University Press, 2nd edition (19-l). 4. Caldwell, S. H., Switching Circuits and Logical Design, John Wiley and Sons, Inc., New York (1958T). 5. Church, R., "Tables of irreducible polynomials for the first four prime moduli," Annals of Mathematics, Vol. 56, No. 1, January (1955), pp. 198-209. 6. Davis, R. L., "The number of structures of finite relations," Proceedings of the American Mathematical Society, Vol. 4 (1955) pp. 486-495. 7. DeBruijn, N. G., "Generalization of Polya's fundamental theorem in enumerative combinatorial analysis," Koninklijke Nederlandse Akademie Van Wetenschappen, Series A, Vol. LXII, No. 2 (1959), pp. 59-69. 8. Dickson, L. E., Linear Groups with an Exposition of the Galois Field Theory, Dover Publications, New York (1958)7 9. Dunham, B., Middleton, D., North, J., Sleter, J., and Weltzien, J., "The multi-purpose bias device. Part II. The efficiency of logical elements," IBM Journal of Research and Development, Vol. 5, No. 1 (1950), pp. 4-53. 10. Elspas, B., "Autonomous linear sequential networks," IRE Transactions, CT-6 March (1959), pp. 45-60. 11. Elspas, B., "Self-complementary symmetry types of Boolean functions," IRE Transactions of Electronic Computers, Vol. EC-9, No. 2 (1960), pp. 264-266. 12. Golomb, S., "On the classification of Boolean functions," IRE Transactions on Information Theory, Vol. IT-5 (1959), pp. 176-186. 15. Golomb, S. W., "A mathematical theory of discrete classification," Information Theory, Butterworth (1961), pp. 404-425. 159

140 14. Hall, M., Theory of Groups, The Macmillan Co., New York, 1959. 15. Harary, F., "Exponentiation of permutation groups," American Mathematical Monthly, Vol. 66, No. 7, August-September (1959). 16. Harary, F., "On the number of bi-colored graphs," Pacific Journal of Mathematics, Vol. 8, No. 4 (1958), pp. 743-755. 17. Harvard Computation Laboratory, Synthesis of Electronic Computing and Control Circuits, Harvard University Press, Cambridge- Massachusetts (1951). 18. Hellerman, L., Equivalence Classes of Logical Functions, IBM Technical Publication TR00.819, November (1961). 19. Higgonet, and Grea, Logical Design of Electrical Circuits, McGraw Hill Book Company, New York T958). 20. Klein, F., Vergleichende Betrachtungen Uber nuere geometriche Forschungen, Erlangen (1872). 21. Lechner, R., Affine Equivalence of Switching Functions, Thesis Abstract, Harvard University (1965). 22. Lorens, C. S., Invertible Boolean Functions, Space General Corporation Report, July 1 (1962). 23. Mautner, F. I., "An extension of Klein's Erlanger program; Logic as invariant theory," American Journal of Mathematics, Vol. 68 (1946), pp. 345-384. 24. McClusky, and Unger, "A note on the number of internal variable assignments for sequential switching circuits," IRE Transactions, Vol. EC-8, No. 4, December (1958). 25. Nechiporuk, E. I., "On the synthesis of networks using linear transformations of variables," Doklady Akad. Nauk 123: 610-12, No. 4, December (1958). Available in English in Automation Express, April (1959), pp. 12-13. 26. Ninomiya, I., "On the number of genera of Boolean functions of n variables," Memoirs of the Faculty of Engineering of Nagoya University, Vol. 11, No. 1-2, pp. 57-58. 27. Ninomiya, I., "On the number of types of symmetric Boolean output matrices," Memoirs of the Faculty of Engineering of Nagoya University, Vol. 7, November 7T955), pp. 115-124. 28. Ore, 0O, "Theory of monomial groups," Transactions of the American Mathematical Society, Vol. 51 (1942), pp. 15-6 4.

141 29. Peterson, W. W., Error Correcting Codes, John Wiley and Sons, New York (1961). 30. Polya, G., "Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen, und chemische Verbindungen," Acta Mathematica, Vol. 68 (1937), PP. 145-253. 31. Polya, G., "Sur les types des propositions composees," Journal of Symbolic Logic, Vol. 5 (1940), pp. 98-103. 32. Post, E. L., "A general theory of elementary propositions," American Journal of Mathematics, Vol. 43, pp. 163-185. 33. Povarov, G. N., "A mathematical theory for the synthesis of contact networks with one input and k outputs," Proceedings of an International Symposium on the Theory of Switching, Part II, Harvard University Press, Cambridge, Massachusetts (1959), pp. 74-94. 54. Sagalovich, I. U., "On the number of types of symmetry for contact (l,k)-pole networks," Doklady Akad. Nauk. 130: 72-73, No. 1, January (1960); available in English in Automation Express, March (1960), pp. 39-40. 35. Seshu, and Reed, Graph Theory and Electrical Networks, Addison Wesley Company, Inc., Reading, Massachusetts (1961). 36. Shannon, C. E., "A symbolic analysis of relay and switching circuits," AIEE Transactions, Vol. 57, pp. 713-723 (1938). 37. Shannon, Co E., "The synthesis of two-terminal switching circuits," The Bell System Technical Journal, Vol. 28 (1949), pp. 59-98. 38. Sikorski, R., Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Neue Folge, Heft 25, Springer-Verlag, Berlin (1960). 39. Singer, T., "The theory of counting techniques," Proceedings of the Association for Computing Machinery, Pittsburgh Meeting (1952), pp. 287-291. 40. Slepian, D., "'On the number of symmetry types of Boolean functions of n variables," Canadian Journal of Mathematics, Vol. 5 (1953), pp. 185-193. 41. Slepian, D., "Some further theory of group codes," The Bell System Technical Journal, Vol. XXXIX, No. 5, September (19X7, pp. 12191252. 42. Weyl, H., Classical Groups, Princeton University Press, Princeton, New Jersey (1946).