April 23: A bit on the Golay [24,12,8] code; the 2576 "umbral" dodecads and M_12.2 inside M_24 As we started with linear algebra, we end with it. I mentioned a bit of this already in outlining the topics; I'll say just a little more, because several people are doing this in much more detail for their final project and I don't want to step on their toes... Let k be the 2-element field Z/2Z, and D=(X,B) the Steiner (5,8,24) design. Let V be the 24-dimensional space of functions X --> k. This can be identified naturally with the set of subsets of X: v is identified with {x: v_x = 1}, and in the other direction a subset is identified with its characteristic function. The _weight_ of a vector v is its number of 1's (= the size of the subset of X corresponding to v). Vector addition corresponds to the symmetric difference, and the standard bilinear pairing = sum_x u_x u'_x takes the characteristic functions of sets S,S' to the parity of the size of their intersection. The _extended binary Golay code_ G is a subspace of V generated by (the characteristic functions of) blocks. We'll show: i) = 0 for all v,w in G. ii) G contains the all-1's vector. iii) Every vector in G has a _doubly_ even weight. ["n is doubly even" means 4|n.] iv) G has dimension 12. v) G has no vectors of weight 4 (and thus none of weight 20). vi) G has 1, 759, 2576, 759, 1 vectors of weight 0, 8, 12, 16, 24 respectively. (Check: these counts sum to 4096 = 2^12.) [The 2576 size-twelve subsets of X are often known as the "dodecads" or "umbral dodecads" of the design, as the blocks themselves are known as "octads"; likewise one sees "hexads" for the (5,6,12) blocks.] vii) Given a 12-element subset S corresponding to a vector in G, there are 132 blocks B whose intersection with B has size 6. These intersections are distinct and constitute a (5,6,12) design. viii) M_24 = Aut(G). This group acts transitively on weight-twelve vectors of G. The subgroup of M_24 that fixes such a vector S acts as M_12 on S, and -- via an outer automorphism of M_24 -- on its complement S'. Proof: (i) [given already] By bilinearity it is enough to check this on generators. We already know that any two blocks meet in 8, 4, 2, or 0 points. Each of these numbers is even, QED. (ii) Choose any block B, and recall that the complement contains 30 blocks forming the design of affine hyperplanes in k^4. Taking any two complementary hyperplanes B' and B" gives us three generators of V whose sum is the all-1's vector. (iii) [not using (ii)] We use the following variant of inclusion-exclusion that counts symmetric differences. If {A_i : i in I} is a finite collection of subsets of some set, for each nonempty subset J of I we denote by A_J the intersection of the sets A_j with j in J. Then the size of the symmetric difference Delta of the A_i is the sum over J of (-2)^(|J|-1) #(A_J). [Recall that using -1 instead of -2 would give ordinary inclusion-exclusion.] Proof: a point that appears in exactly k of the sets is counted (1 - (1+(-2))^k)/2 times, and that's 1 or 0 according as k is odd or even. In particular, if each #(A_i) is 0 mod 4, and any two A_i and A_j intersect in a set of even size, then |Delta| is a multiple of 4. This hypothesis is satisfied whenever the A_i are blocks of D, QED. (iv) For now we show that G has dimension at most 12. Proof: by (iii) G is contained in its annihilator w.r.t. the pairing <.,.>. But this pairing is nondegenerate, so dim(G) <= dim(V) - dim(G) whence dim(G) <= dim(V) / 2 = 12. (v) M_24 acts on D and thus on G. Since M_24 acts transitively on X, if G contained one word of weight 4 it would contain them all. But that's absurd (it contradicts all of (i), (ii), and the part of (iv) we've already proved). Since G contains the all-1's word, it thus cannot contain a word of length 24 either. (vi) So far we know that G contains at most 2^12 = 4096 words in total, and at least 1 + 759 + 759 + 1 = 1520 of weight 0, 8, 16, or 24 respectively. Hence it contains at most 2576 words of weight 12. At any rate it contains at least one, because we can certainly find blocks B, B' whose intersection has size 2, and form their symmetric difference. (vii) By (ii), G also contains the complement S'. By (i), any block B intersects S in a set of even size. We claim this size is one of 2, 4, or 6. Indeed if it were 8 then B would be contained in S and the symmetric difference B+S would have weight 4, contradicting (v). Likewise if it were 0 then B+S' would have weight 4. Moreover, (*) if B intersects S in a set of size 6 then no other B' block intersects S in the same set (else B+B' would be a nonzero vector of weight at most 4, again contradicting (v)). We can now prove that the six-element subsets of S that arise as intersections with a block constitute a (5,6,12) Steiner system. Indeed let Y be any 5-element subset of S. Since D is a (5,8,24) Steiner system, there exists a unique block B containing Y. Then B intersects S in at least 5 points, hence exactly 6, as desired. (viii) By (vii) there are 132 such choices of B. Each intersects S' in a set of size 2. If two blocks B1,B2 meet S' in the same pair then B1+B2 is supported on S, so it is either 0 or S itself, and the latter occurs iff the intersections of B1 and B2 with S are complementary blocks of the (5,6,12) design. This gives us an injection from (5,6,12) block-pairs to pairs in S'. But there are only Bin(12,2) = 66 pairs available, so the map is a bijection. We claim that, after possibly permuting S', this is the same bijection we obtained earlier in the week using Hadamard matrices. Indeed two distinct pairs in S' intersect iff the corresponding blocks in S have odd intersection (and thus necessarily intersection of size 3). So we have an isomorphism from the triangle graph T(12) of pairs of S', and the odd-intersection graph of block pairs in S -- and we already know (using maximal cliques, since 12>4) any such isomorphism is induced from a permutation of the underlying 12-element set. We could now also complete the proofs of (iv) and (vi) in various ways; for instance we could compute dim(G) using the map from G to the 12-dimensional space of functions on S' (by forgetting the S coordinates), and checking that its image has dimension 11 (it contains all vectors of weight 2) and its kernel is the 1-dimensional space {0,S}. Perhaps the most amusing way to finish off all that remains of (iv), (vi), and (viii) is as follows. Let H be the stabilizer in Aut(G) of S. Then H acts on the (5,6,12) design, so maps to M_12; and the map is injective because if an element of M_24 acts trivially on S then it acts trivially on T(12) and thus also on S'. Thus the orbit of H has size at least |M_24| / |M_12|. But that's (24*23*22*21*20*48) / (12*11*10*9*8) = 2^4 7 23 = 2576. Yet we saw in (vi) that G has _at most_ 2576 such vectors, and that's only if dim(G)=12, there are no vectors of weight 8 and 16 other than blocks and block complements, Aut(G) is no larger than M_24, and all of M_12 acts on G (so is in M_24). Hence all that must happen. In particular there are elements of M_24 that take S to S', so the group that stabilizes the partition X = S + S' contains M_12 with index 2. Since we've seen that the block-pair / S'-pair structure of the Hadamard matrix reappears here, the actions of M_12 on S and S' must be related by the same outer automorphism. QED! Final(?) remark: the 759 blocks consist of 132 blocks meeting S in 6 points and S' in 2 points, and 132 blocks meeting S in 2 points and S' in 6 points, and thus 495 blocks meeting S in 4 points and S' in 4 points because 759 - (132+132) = 495. But there are Bin(12,4)=495 quadruples in either S or S', and none arises twice (why?). Hence each arises, and we get a bijection between the quadruples in S and S'. It will not surprise you (and perhaps you can convince yourself) that this bijection is the same one we constructed last time using the Hadamard matrix.