THE UNIV E R S I T Y OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note ON THE CLASSIFICATION OF BOOLEAN FUNCTIONS BY THE GENERAL LINEAR AND AFFINE GROUPS Michael A. Hari son @IRA P-roject' 0.879 under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF 55(657) -7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR September 1962

SUMMARY The general linear group and the affine group of transformations are defined over the field of two elements and are applied as transformation groups to Boolean functions. Algorithms for counting the number of classes under both groups are derived. The concept of equivalence is extended by allowing complementation of the range of the functions and the number of such classes is also obtained. The number of classes of invertible Boolean functions is calculated when these groups are considered. Some other problems are stated and solved.

1. INTRODUCTION Let J n denote the free Boolean algebra on n generators consisting of the 22 functions from (O,l)n into (0,1); also let Z2 = (0,1) be the field of two elements which must be of characteristic two. By GLn(Z2), we denote the group of all non-singular transformations from an n dimensional vector space over Z2 into itself. Since the underlying field is finite, the order of GLn(Z2) is also finite. It is well known (cf. Artin1) that the order of GL(Z2) is,T (2n - 2i) 2 2 H (2 - 1) i=0 i=l For our purposes, it is convenient to think of GLn(Z2) as a group of n x n nonsingular matrices whose elements are zeroes and ones. Let A = (aij) be such a matrix and let f(xl,...,xn) E 4 n- We define the product Af as n n Af(xl,.,.,Xn) = f( i aklxk,', aknxk) k=i k=l where i denotes addition modulo two. This may be abbreviated if we let x denote the vector (xl,..,xn). Then we may write Af(x) = f(xA) We shall call two functions f and g equivalent if and only if there exists a matrix A e GLn(Z2) such that f(x) = g(XA) for all x. This clearly defines an equivalence relation on din which decomposes n into disjoint transitivity 1

classes. The first problem to be posed is the determination of the number of classes. 2. THE NUMBER OF CLASSES UNDER GLn(Z2) Using the celebrated theorem of Polya15 to count the number of classes, it is sufficient to construct the cycle index polynomial of GLn(Z2) where we take a representation of this group of degree 2n. That is, it suffices to know the behavior of the group on the atoms of In' The cycle index is discussed in detail in references 15,2,7,8,9, and 10 to which the reader is referred. We shall confine ourselves to a presentation of the algorithm. All of the available information necessary to calculate the cycle index is available in the literature. Dickson4 (page 235) calculates the coefficients of the cycle index which are essentially the number of elements in a conjugacy class. Elspas5 derives and Slepianl8 uses the cycle structure for each class. Slepianl8 has solved related problems in counting the number of classes of codes under GLn(Z2). Our algorithm involves a certain amount of notation. Consider the irreducible polynomials of Z2[x]. For every positive integer m, there are at most a finite number of irreducible polynomials of degree m. We shall imagine the irreducible polynomials sorted by degree and ennumerated. The polyniuillal p(x) = x will be excluded from all our considerations. We let,di denote the degree of the i th irreducible polynomial and let ei be the least integer such that polynomial pi(x) divides xei - 1. Church3 has listed irreducible polynomials for the first four prime moduli. Table I indicates the first 22 poly2

nomials along with values of di and ei for Z2TABLE I TABLE OF IRREDUCIBLE POLYNOMIALS OVER Z2 i x6 x5 x4 x3 x2 x xO di ei 1 1 1 1 1 2 1 1 1 2 3 3 1 0 1 1 3 7 4 1 1 0 1 3 7 5 1 0 0 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 51 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 0 1 0 0 1 6 9 16 1 0 1 0 1 1 1 6 21 17 1 0 1 1 01 1 1 6 63 18 1 1 0 0 0 0 1 6 63 19 1 1 0 0 1 1 1 6 63 20 1 1 0 1 1 0 1 6 63 21 1 1 o 0 1 1 6 63 22 1 1 1 0 1 0 1 6 21 Since the irreducible factors of x2 - x are exactly the irreducible polynomials (mod 2) of all degrees which divide n, let I(m) be the number of irredicible polynomials in Z2[x] of degree m. By equating degrees we get m I(m) 2n mIn By the MSbius inversion formula. 3

I (n) =1 2d ) n d n where pd ) is the Mobius function. Because we are ignoring the polynomial p(x) = x, we must subtract one from I(n) in our calculations. Let tn be the number of irreducible polynomials in Z2[x] of degree n or less not counting p(x) = x. Table II shows the first few values of I(n) and tn. Of course n tn = I(m) - 1 n n= TABLE II VALUES OF In AND tn n tI(n) tn 1 2 1 2 1 2 3 2 4 4 3 7 5 6 13 6 9 22 The first step in our algorithm is to give a notation for describing the classes of GLn(Z2). One finds all possible non-negative integer solutions ai of the equation t Z ai di = n i=l The solutions may be written as set of tn - tuples (al,z*..atn), Take every element ai and write all possible partitions of ai where the partitions must 4

must be written in the form a. ai ) j iji (1) j=l Thus the aij are elements in the partition for the integer ai. The classes of the group may be given by tn - tuples each of whose elements is 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 al + 2a2 = 2, namely al = 2, a2 = 0 and al = O, a2 = 1. Thus there are 3 classes (a,1 = 2, 0) (o12 = 1, 0) o(, O21 = 1) Before writing down the cycle index, we introduce two final definitions. Let qij = ei2 J where bj = -[-log2j]. [x] is the largest integer < x. Also let di(j-1) (2di 1 h =2(2 - ) f qij At long last it is possible to write down a closed form for the cycle index. Theorem 1. The cycle index for GLn(Z2) as a permutation group on the 2n elements of {O,]nn is n(n-l) n tn ai (X Xij 22'fT(2'-) X X( f 1____i=l _ _ i=l j=c \k= k ZGLn(Z2) =n tn/a a2 (k-l) na 1a 2ka. aJ (jp-l)~Jp'jp 22 = f (2^1) =r(i 2 2jk nT T 2 J= 3)r 2d 2' -pY(2q d,-1) i=1 j=l k=\ k= =k+i/ p= q= 1 5

where the cross operation is defined as follows (it ap X( bqq = XT(apiP X b j() P= i / = 1 P ( where i 1 i (P, ) ap X b = f P q p,q> and <p,q> is the least common multiple of p and q; (p,q) is the greatest common divisor of p and q. X is an associative and commutative operation. The sum is over all classes.* Proof. The complicated coefficient is merely the number of elements in the class as given by Dickson. The products of f's denote the cycle structure as derived by the Elspas.5 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, cf. 8. The results are given in Table III. TABLE III n Number of Classes 1 4 2 8 3. 20 4 92 5 2,744 6 950,998,216 k k *Since the symbol fk is ambiguous and might mean'f...f or f.... xf, we write fXk in the latter case. 6

If we replace each indeterminate fi by 1 + xi and collect all the terms into a polynomial in x, then Polya's theorem insures us that the coefficient of xk is the number of functions with k atoms in their normal form expansion. The results are collected in Table IV where Nk denotes this number while Tn denotes the total number of classes. TABLE IV 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 Tn 4 8 20 92 2744 It is easily seen that N = 2 for all n. This is because the zero vector is in a class by itself and all the other atoms are equivalent. If n > 1, then 2 Nn = 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 7

that there exists a nonsingular transformation which takes any basis onto any other basis. Likewise n > 3 implies N3 = 3 and n > 4 implies N4 5 n n It is desirable to examine the structure of the equivalence classes themselves. We now mention a few considerations which facilitate calculations. Every matrix in GLn(Z2) may be written in row echelon form. This says that GLn(Z2) is generated by the scalar matrices, the n! permutation matrices Pij which interchange columns i and j, and the matrices Dij which add the jth col umn to the ith column mod 2. An easy calculation shows that Pij = Dij ji Dij Thus the group is generated by the n2 - n matrices Dij. This means that to find functions equivalent to f(xl,...,xi,...,xn), one examines f(xl,...,xi ~ xj,...,xn) for j ~ i.* As an example, we list the eight classes for n = 2. [01 ] [1] [ y] [ y, x y, xy] [x + y] [x + y, x + y, x + y] [x, y, x ~y] [x, y, x'- y] 3. THE NUMBER OF CLASSES UNDER 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 = x A @ b -*This argument also shows that the class; nf of all 2n+l 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. 8

where A e GLn(Z2) and b is a vector whose components bi C Z2 for i = 1,...,n. e denotes componentwise addition modulo 2. We denote the affine group by XOn(Z2)o The effect of the affine group is the complementation of those variables of the Boolean functionfor which bi = 1. The order of Oin(Z2) is n(n+l) n 22 2 (2 _ 1) i=1 In an obvious way, the action ofd(n(Z2) decomposes the functions into equivalence classes. We shall now count the number of classes. The problem has been solved by Neckiporukl but his proof has not been published. The subgroup of the affine group consisting of translations only is the well known group JL of 2 and 8. This group of order 2n is the group of all complementations of variables of Boolean functions. The algorithm to be derived makes GLn(Z2) use of the fact that the structure of On(Z2) as a permutation group is 2 where the operation is the exponentation of permutation groups. The exponention of permutation groups has been defined and studied by Harary.6 The general definition is briefly reviewed. Let O and^be permutation groups of degrees a and b operating on object sets X and Y; let the orders of Ot and Z be m and n respectively. The exponention P has YX, the class of all functions from X to Y as its object set. The elements of 6 tare constructed by permuting the domain X using a permutation in'( and then permuting the image objects for every object in the domain by elements of T. The properties of the group are summarized below, in Table V. It is interesting to note that the exponentiation of permutation groups has occurred in two combinatorial problems prior to this study. The first oc9

TABLE V Group 0 7 Object Set X Y yX Degree a b ba Order m n mna currence was in Slepian's original study of the number of classes of Boolean functions.18 The next occurrence was in Harary's study of bi-colored graphs.7 It is interesting to note that Slepian computed 2 while Harary worked with I/ 22 n ~ In reference 8, Slepian's original method was reformulated using the properties of the exponentiation of the two groups. GLn (Z2) It is immediately verified that t n(Z2) = 2 The equation f(x A b) = f((x b A-1) A) (A-' exists since A e GLn(Z2)) shows that the group of translations gn is a 2 normal subgroup of n(Z2). Thus n n = % (GLh(Z2)).* Many algebraic identities may be derived about the relation of elements in %2 and in GLn(Z2) but we shall not do so here. We know from references 2 and 8 that the cycle index of )m is given by Z n = (f2 + (2n - 1) f2 ) 2 *By the product'tZ A-6 of two groups d- and A which are subgroups of a larger group< we mean the group whose domain is (abla c o, be A>}. This group is defined when one of 6i or 5v is normal in L. In our case 2 is normal in n( Z2) and cln(Z2) is the least group containing ~2 and GL(Z2). 10

The importance of this result is that there are only two types of cycle structure induced by elements of 2. The first corresponds to the identity. When this permutation is composed with elements of GLn(Z2), we obtain just the elements of GLn(Z2). We must now determine the effect of multiplying a non-identity permutation in, with the permutations having cycle structure J ik vij 4 fl fqik k=i The answer is given in the following lemma. Lemma 2. The cycle structure of Otn(Z2) is given by 2J-1 f f hk + 2-1l f 23/1 k= 1,qzk qzj+l u.j =, k=l ~ui~j~j i hik 2 iJ f1 f if i > 1 k=i n Proof. Examine the vij premultiplied by the non-identity permutations of J.2 Theorem 3. The cycle index for rX n(Z2) is given by n(n+l) n tn a X aij 2 (2i_1) uij 1 \ i= i=1 j=1 Z:(n(Z2) = n(n+l) n tn a (k+l)aj-1 a a (ajp-l)ajp ajp 22 Tt (-1) ( T 2 t jk jT a T 2k-j T (2k- 1) i=1 j=1 ik=i k=i =k+i / p= q=1 where the sum is over all classes. 11

Using the polynomials constructed by this formula, the following numerical results were obtained. For 3 < n < 5, the results agree with those of Nechiporuk.l4 Again N denotes the number of classes of functions with k atoms in their normal form expansion while Tn denotes the total number of classes. TABLE VI n Tn 1 3 2 5 3 10 4 32 5 582 6 15,768,919 TABLE VII Nn A 1 2 3 4 5 0 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 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 Tn 3 5 10 32 382 12

0 1 2 The- following results are suggested by Table VII. Nn = Nn = Nn = 1. If 3 4 5 n > 1 then Nn = 1 and if n > 2, then Nn = 2. If n > 3, then Nn =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 N3 = N2 = 1. Similar proofs may be furnished in the other cases. We note that the class fn of linear Boolean functions is preserved under n(Z2) and that there are 3 classes of linear functions for all n. [y3, Sy, xy, xy] [x + y, x + y, x + 3, x + y] [x, x, y, 7y x 7'y, x = y] [0] [I] 4. THE NUMBER OF CLASSES WHEN THE RANGE IS COMPLEMENTED The definition of equivalence of Boolean functions is often enlarged by also allowing complementation of the range of the functions. This subject was investigated in reference 9 and the following theorem was proved. Theorem 4. Let o~-be any permutation group on the domain of Boolean functions. The number of classes of functions under x (transformations of on the domain and complementation of the range) is given by $(Z (2,2),6G,2) + Z (0,2,0,2,...,0,2)) We shall apply this theorem to GLn(Z2) and Hn(Za). Theorem 5. The number of classes under 1 x GLn(Z2) is one half the number of classes under GLn(Z2). 13

Proof. Since every linear transformation in GLn(Z2) leaves the origin invariant, every term of the cycle index has a factor f where k > 1. The calculations for both groups are given below in Table VIII. TABLE VIII THE NUMBER OF CLASSES UNDER THE ENLARGED GROUPS n R x GLn(Z2) Yx x1In(Z2) 1 2 2 2 4 3 3 10 6 4 46 18 5 1,372 206 6 475,499,108 7,888,299 It was also shown in reference 9 that the number of self complementary classes (classes closed under complementation) under a group is Z (0,2,0,2,...,,2). The number of such classes is given in Table IX below TABLE IX THE NUMBER OF SELF-COMPLEMENTARY CLASSES n GLn(Z2) _ (tn(Z2) 1 0 1 2 0 1 3 0 2 4 0 4 5 0 30 6 0 7,679 One might inquire whether most of the classes of neutral functions (those with 2n-z atoms in their normal form expansion) are self complementary or not 14

under 6 n(2)o In order to obtain the 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 6. The number of neutral classes under a7n(Z2) is greater than or equal to \n n-1 n(n+l) n v2 2 2i (2 -l) i=l The number of self complementary functions is less than or equal to 2n-1 2. 12 s Proof. The first part is obtained by using the well known2 lower bound g, where s is the number of objects on which a permutation group of order g acts. I2n The result follows upon noting that there are (2n-. neutral Boolean functions. The second part of the theorem follows from noting that the largest term in n-l. Z (C,2,, o,0,2) is g An upper bound is certainly 1 v 2n-1 2n-1 g L 2 - 2 The ratio we desire can now be computed, but it is convenient to have an estimate for the binomial coefficient. Using Stirling's formula, we get ( n 22n2 n / A The ratio of self-complementary classes to neutral class under O<n(Z2) is less than or equal to 15

n(n+l) n n(n+2) n (2i 2 2 2 il< 22- = o(l) 2n I 2 2n-1 2 2n-l 2nThis shows that the ratio approaches zero for large n and therefore that self complementary classes are rather rare. 5. INVERTIBLE BOOLEAN FUNCTIONS C. S. Lorensl2 has studied the invertible Boolean functions and has counted the number of classes of such functions with the same group acting on both the domain and range of the functions. This writer10 has extended Lorens' results by allowing different groups on the domain and range. We now apply the techniques of reference 10 to counting the number of classes of invertible functions when GLn(Z2) and 0-n(Z2) are considered. The notation for the other groups to be studied are as follows. denotes the group of all 2n complementations of variables; the cycle index of this group was first computed by Ashenhurst.2 dn denotes the symmetric group of degree n on the variables. This group was studied by Hellerman11 and the cycle index was first computed in reference 8. n is the least group containing Tn and n*' n The cycle index was first computed by P6lyal for 1 <n < 4. Slepianl7 first gave an algorithm for counting the number of classes under O/n for all n although he did not explicitly construct the cycle index. A closed form for the cycle index is given in reference 8, 16

Theorem 7. The number of classes of invertible functions with a group acting on the domain and a group acting on the range is Z ^,,. On, a )Z (l + zi, 1 + 2z2,., 1 + SZs) evaluated at zl = z2 =.. = zs = 0 where Z denotes the cycle index of Table X gives the number of classes with the same group on both the domain and range. Table XI gives the results with different groups on the domain and range. It is trivial to show that the number of classes of invertible functions with 7n on the domain and GLn(Z2) on the range is (2n 1)J n(n-i) n 2 I 1 (21 1) i=l TABLE X NUMBER OF CLASSES OF INVERTIBLE FUNCTIONS WITH THE SAME GROUP ON BOTH THE DOMAIN AND THE RANGE 61, G n * GLn(Z2) 2n(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 *These numbers are quoted. from reference 10. 17

TABLE XI 2on d on domain en on domain GLn(Z2) on range GLn(Z2) on range GLn(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 nn on domain doain on doma n omin GL (Z2) on domain 2 nn on n n 0-(n(Z2) on range (n(Z2) on range <(n(Z2) on range orn(Z2) on range 1 1 1 1 1 2 1 1 1 1 3 16 10 8 4 4 4,073,400 2,705,820 172,194 3374 6. ENGINEERING IMPLICATIONS The orders of GLn(Z2) and 6n(Z2) are much larger than the other groups which have been studied previously in switching theory. Because the orders are so large, we find a smaller number of classes. This opens up the possibility of using ennumeration techniques for n = 5 or perhaps n =,6 if a computer is used. There are still several problems to be solved before the practical design methods may be developed. These problems are mentioned in detail in the next section. The small number of classes gives some justification for the linear approach to switching circuits. It appears that the number of @ operations which are required to realize the transformation which maps one function into an equivalent function is very small. A more precise conjecture is made in the next section. 18

The development of cheap and fast components for realizing the ~ operation also makes this approach look more promising. Recently tunnel diode circuits for realizing the e operation have been reported by Menger13 and others.; these circuits require only one tunnel diode for realizing x1 ~ x2 ~ x3. 7. MISCELLANEOUS COMMENTS AND PROBLEMS The initial investigation into equivalence of Boolean functions under linear groups has been very promising, but a great many problems remain open. The most serious unsolved problem is to find an algorithm for determining when two functions are equivalent under the groups. Nechiporuk14 and Slepianl8 list partial results but the general problem has not been solved. A canonical form for functions under GLn(Z2) would have applications in coding theory also. It is a general principle that if and ~ are two groups such that c 14, then the set of invariants of ~ contains the set of invariants of. One would like to have the invariants of Yn(Z2) and all its subgroups. & n(Z2) contains all the other groups which have been studied as transformation groups on Boolean functions as subgroups. The lattice structure of these subgroups is shown below Otn(Z2) /1^~ 9^^ —~GLn(Z2) 19

It appears that the transformation which maps one equivalent function into another requires very few eioperations in its hardware realization. One may also observe that the representatives of the equivalence classes are very simple for the first few values of n. It was even thought that there might be a linearly separable function in each class, but this can be shown to be false by a cardinality argument. Both of these observations about the small number of @ operations and the simplicity of the representatives cannot be true for all n because of complexity considerations. This writer conjectures that the former observation is correct. More precisely that the number of'Ooperations required to realize the transformation from f(x) to f(x A), A E GLn(Z2) is linear in n. The techniques given for counting the number of classes under 04n(Z2) may be immediately applied to counting the number of equivalence classes of (n,k) codes under the affine group. 8. ACKNOWLEDGMENT I wish to thank B. Elspas who first suggested these problems and who was able to verify the results for 1 < n < 3 under GLn(Z2), I am indebted to C. S. Lorens for pointing out the work of Nechiporuk. Robert Lechner is also working on these and related problems and has also constructed algorithms for counting the number of classes under GLn(Z2) and 6Yn(Z2). I am indebted to him for verifying my results for 1 < n < 6 under both groups. 20

REFERENCES 1. Artin, E., Geometric Algebra, Interscience Publishers, Inc., New York (1957)o 2, Ashenhurst, R. L, "The application of counting techniques," Proceedings of the Association of Computing Machinery, Pittsburgh Meeting (1952), pp. 293-305. 35 Church, Ro, "Tables of irreducible polynomials for the first four prime moduli," Annals of Mathematics, Vo. 36, No. 1, January (1935), pp. 198-209. 4o Dickson, L. E., Linear Groups with an Exposition of the Galois Field Theory, Dover Publications, New York (1958). 5. Elspas, B., "Autonomous linear sequential networks," I.R.E. Transactions, C-6, March (1959), pp. 45-60, 6. Harary, F., "Exponentiation of permutation groups," American Mathematical Monthly, Vol. 66, No. 7, August-September, (1959). 7. Harary, Fo, "On the number of bi-colored graphs," Pacific Journal of Mathematics, Volo 8, No. 4, (1958), pp. 743-755. 8. Harrison, MO A., The Number of Transitivity Sets of Boolean Functions, The University of Michigan Technical Note 04879-3-T, June (1962). 9. Harrison, M. Ao, The Number of Equivalence Classes of Boolean Functions under Groups Containing Negation, The University of Michigan Technical Note 04879-4-T, June (1962), 10. Harrison, M. A., The Number of Classes of Invertible Boolean Functions, The University of Michigan Technical Note 04879-5-T, July (1962). 11. Hellerman, L., Equivalence Classes of Logical Functions, IBM Technical Publication TROO. 819, November (1961). 12. Lorens, C. So, Invertible Boolean Functions, Space General Corporation Report, July 1, (1962), 13. Menger, aK. S., "A modulo two adder for three inputs using a single tunnel diode,' IoR.E. Transaction, Vol. 10, No. 3, September (1961), pp. 530-531. 14. Nechiporuk, Eo I., "On the synthesis of networks using linear transformations of variables," Doklady Akad. Nauk 1235: 610-12, No. 4, December (1958), Available in English in Automation Express, April (1959), pp. 12-135 21

REFERENCES (Concluded) 15. Polya, G., "Kombinatorische Anzahlbestimmungen fir Gruppen, Graphen, und chemische Verbindungen," Acta Mathematica, Vol. 68 (1937), pp. 145-253. 16. Polya, G., "Sur les types des propositions composees," Journal of Symbolic Logic, Vol. 5 (1940), pp. 98-103. 17. Slepian, D., "On the number of symmetry types of Boolean functions of n variables," Canadian Journal of Mathematics, Vol. 5 (1953), PP. 185-193. 18. Slepian, D., "Some further theory of group codes," The Bell System Technical Journal, Vol. XXXIX, No. 5, September (1960), pp. 1219-1252. 22

UNIVERSITY OF MICHIGAN 3 9015 03026 8307II III111 3 9015 03026 8307