Category Archives: math

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.

Some favorite quotes on math, science, learning

Posted on by

Here is a collection of some favorite quotes from scientists and writers. For more, see this post.

There are some things which cannot be learned quickly,
and time, which is all we have,
must be paid heavily for their acquiring.
They are the very simplest things,
and because it takes a man’s life to know them
the little new that each man gets from life
is very costly and the only heritage he has to leave.
Ernest Hemingway
(From A. E. Hotchner, Papa Hemingway, Random House, NY, 1966)

I believe that a scientist looking at nonscientific problems is just as dumb as the next guy.
Richard Feynman

The best thing for being sad is to learn something. That is the only thing that never fails. You may grow old and trembling in your anatomies, you may lie awake at night listening to the disorder of your veins, you may miss your only love, you may see the world about you devastated by evil lunatics, or know your honor trampled in the sewers of baser minds. There is only one thing for it then to learn. Learn why the world wags and what wags it. That is the only thing which the mind can never exhaust, never alienate, never be tortured by, never fear or distrust, and never dream of regretting.
T. H. White in The Once and Future King

Truth, like gold, is to be obtained not by its growth, but by washing away from it all that is not gold. Leo Tolstoy

Education is what survives when what has been learnt has been forgotten.
B. F. Skinner

The advantage is that mathematics is a field in which one’s blunders tend to show very clearly and can be corrected or erased with a stroke of the pencil. It is a field which has often been compared with chess, but differs from the latter in that it is only one’s best moments that count and not one’s worst. A single inattention may lose a chess game, whereas a single successful approach to a problem, among many which have been relegated to the wastebasket, will make a mathematician’s reputation.
Norbert Wiener, in Ex-Prodigy: My Childhood and Youth

Science is a differential equation. Religion is a boundary condition.
Alan Turing

Everything is vague to a degree you do not realize till you have tried to make it precise.
Bertrand Russell

For every complicated problem there is a solution that is simple, direct, understandable, and wrong.
H. L. Mencken

If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is.
John Louis von Neumann

To be what we are, and to become what we are capable of becoming, is the only end in life.
Baruch Spinoza

Math blogs, SAGE, and latex

Posted on by

I only created this wordpress site thinking that I could not type LaTeX on my blogspot page (wdjoyner.blogspot.com). Since I figured out how, following http://wolverinex02.googlepages.com/emoticonsforblogger2, maybe this blog will stay dormant for now.

A latex test:

\frac{\pi}{4}=\int_0^1 \frac{dx}{1+x^2} is smallest

\frac{\pi}{4}=\int_0^1 \frac{dx}{1+x^2}

\frac{\pi}{4}=\int_0^1 \frac{dx}{1+x^2}

\frac{\pi}{4}=\int_0^1 \frac{dx}{1+x^2}

\frac{\pi}{4}=\int_0^1 \frac{dx}{1+x^2}

\frac{\pi}{4}=\int_0^1 \frac{dx}{1+x^2} is biggest

Here is a SAGE plot of the integrand:

integrand

Here is a SAGE session:


sage: x = var("x")
sage: integral(1/(1+x^2),x,0,1)
pi/4
sage: plot(1/(1+x^2),x,0,1)

Actually, I like this much better than blogspot, so I might switch after all!