Category Archives: sage

Relates to the SAGE program www.sagemath.org

Steiner systems and codes

Posted on by

A t-(v,k,λ)-design D=(P,B) is a pair consisting of a set P of points and a collection B of k-element subsets of P, called blocks, such that the number r of blocks that contain any point p in P is independent of p, and the number λ of blocks that contain any given t-element subset T of P is independent of the choice of T. The numbers v (the number of elements of P), b (the number of blocks), k, r, λ, and t are the parameters of the design. The parameters must satisfy several combinatorial identities, for example:

\lambda _i = \lambda \left(\begin{array}{c} v-i\\ t-i\end{array}\right)/\left(\begin{array}{c} k-i\\ t-i\end{array}\right)

where \lambda _i is the number of blocks that contain any i-element set of points.

A Steiner system S(t,k,v) is a t-(v,k,λ) design with λ=1. There are no Steiner systems known with t>5. The ones known (to me anyway) for t=5 are as follows:

S(5,6,12), S(5,6,24), S(5,8,24), S(5,7,28), S(5,6,48), S(5,6,72), S(5,6,84),
S(5,6,108), S(5,6,132), S(5,6,168), and S(5,6,244).

Question: Are there others with t=5? ANy with $t>5$?

A couple of these are well-known to arise as the support of codewords of a constant weight in a linear code C (as in the Assmus-Mattson theorem, discussed in another post) in the case when C is a Golay code (S(5,6,12) and S(5,8,24)). See also the wikipedia entry for Steiner system.

Question: Do any of these others arise “naturally from coding theory” like these two do? I.e., do they all arise as the support of codewords of a constant weight in a linear code C via Assmus-Mattson?

Here is a Sage example to illustrate the case of S(5,8,24):

sage: C = ExtendedBinaryGolayCode()
sage: C.assmus_mattson_designs(5)
[‘weights from C: ‘,
[8, 12, 16, 24],
‘designs from C: ‘,
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]],
‘weights from C*: ‘,
[8, 12, 16],
‘designs from C*: ‘,
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]]
sage: C.assmus_mattson_designs(6)
0
sage: blocks = [c.support() for c in C if hamming_weight(c)==8]; len(blocks)
759

The Assmus-Mattson Theorem, Golay codes, and Mathieu groups

Posted on by

A block design is a pair (X,B), where X is a non-empty finite set of v>0 elements called points, and B is a non-empty finite multiset of size b whose elements are called blocks, such that each block is a non-empty finite multiset of k points. A design without repeated blocks is called a simple block design. If every subset of points of size t is contained in exactly \lambda blocks the the block design is called a t—(v,k,\lambda) design (or simply a t-design when the parameters are not specfied). When \lambda = 1 then the block design is called a S(t,k,v) Steiner system.

Let C be an [n,k,d] code and let C_i = \{ c \in C\ |\ wt(c) = i\} denote the weight i subset of codewords of weight i. For each codeword c\in C, let supp(c)=\{i\ |\ c_i\not= 0\} denote the support of the codeword.

The first example below means that the binary [24,12,8]-code C has the property that the (support of the) codewords of weight 8 (resp, 12, 16) form a 5-design.

Example: Let $C$ denote the extended binary Golay code of length 24. This is a self-dual [24,12,8]-code. The set X_8 = \{supp(c)\ |\ c \in C_8\} is a 5-(24, 8, 1) design; X_{12} = \{supp(c)\ |\ c \in C_{12}\} is a 5-(24, 12, 48) design;and, X_{16} = \{supp(c)\ |\ c \in C_{16}\} is a 5-(24, 16, 78) design.

This is a consequence of the following theorem of Assmus and Mattson.

Assmus and Mattson Theorem (section 8.4, page 303 of [HP]):

Let A_0, A_1, ..., A_n be the weight distribution of the codewords in a binary linear [n , k, d] code C, and let A_0^\perp, A_1^\perp, ..., A_n^\perp be the weight distribution of the codewords in its dual [n,n-k, d^\perp] code C^\perp. Fix a t, 0<t<d, and let s = |\{ i\ |\ A_i^\perp \not= 0, 0<i\leq n-t\, \}|.
Assume s\leq d-t.

  • If A_i\not= 0 and d\leq i\leq n then C_i = \{ c \in C\ |\ wt(c) = i\} holds a simple t-design.
  • If A_i^\perp\not= 0 and d^\perp\leq i\leq n-t then C_i^\perp = \{ c \in C^\perp \ |\ wt(c) = i\} holds a simple t–design.
  • If A_i^\perp\not= 0 and d^\perp\leq i\leq n-t then C_i^\perp = \{ c \in C^\perp \ |\ wt(c) = i\} holds a simple t–design.

In the Assmus and Mattson Theorem, X is the set \{1,2,...,n\} of coordinate locations and B = \{supp(c)\ |\ c \in C_i\} is the set of supports of the codewords of C of weight i. Therefore, the parameters of the t-design for C_i are

  • t = given,
  • v = n,
  • k = i, (this k is not to be confused with dim(C)!),
  • b = A_i,
  • \lambda = b*binomial(k,t)/binomial(v,t)

(by Theorem 8.1.6, p. 294, in \cite{HP}). Here is a SAGE example.


sage: C = ExtendedBinaryGolayCode()
sage: C.assmus_mattson_designs(5)
['weights from C: ',
[8, 12, 16, 24],
'designs from C: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]],
'weights from C*: ',
[8, 12, 16],
'designs from C*: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]]
sage: C.assmus_mattson_designs(6)
0

The automorphism group of the extended binary Golay code is the Mathieu group M_{24}. Moreover, the code is spanned by the codewords of weight 8.

References:
[HP] W. C. Huffman, V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003.
[CvL] P. Cameron, J. van Lint, Graphs, codes and designs, Cambridge Univ. Press, 1980.