Some problems in coding theory which interest me, and which I would
like to collaborate on
This page is under construction... I am gradually expanding it. Please
please let me know if you are interested in working with me on any of these
problems.
I study binary linear codes. More specifically,
I work on the following two problems. First, given a triple [n,k,d], I
try to determine if there exists a code with those parameters. (Read
this!) Second, for
putatively optimal parameters [n,k,d], I try to classify
and/or describe the codes with those parameters.
If you back up to my home page, you will find a huge amount of information
on these questions. For example, I have classified the optimal codes of
length <= 30 (building on other people's work of course). So in the sense
of the previous paragraph, everything is known for length <= 30, right?
Wrong! Good descriptions of many of these optimal codes have yet to be
found. Of course, they may not exist, but it is a good guess that there are
many good descriptions yet to be found.
Beyond length 30 is a wilderness. There are many interesting special cases
which warrant attention. For example, it is not known if there exists a
[165,10,80] code, but if it does exist, it has weight enumerator
1 + 858t80 + 165t96. Similarly, it is not known if
there exists a [69,9,32] code, but if it does exist, it has weight
enumerator 1 + 351t32 + 156t40 + 4t48.
Yet another example: [39,10,16], enumerator 1 + 367t16 +
414t20 + 240t24 + 2t28.
Here is another example, of a somewhat different character. It is not
known if there exists a [57,8,26] code. If if does exist, it is even
and has no codeword of weight larger than 42. On the other hand, there are over
150,000 nonisomorphic [58,8,26] codes, and there are also lots of
[56,7,26] codes.
If you go to the main
Split
document, you will find hundreds of new
nonexistence results for codes with specific parameters. Underlying
these results there are two main methods: linear programming (based on a
split or joint weight enumerator), and the explicit enumeration of all
codes having certain properties. Can you find other techniques for proving
the nonexistence of codes?
I have also compiled a large library of low-dimensional examples,
and am currently trying to "identify" them. This problem turns out to be
much harder than I had thought.
Suppose a finite group G acts on a finite-dimensional vector space V over
F2. Oftentimes one can successfully construct good codes C in the
following way. Choose a G-stable subset S of V, and form a matrix M whose
columns are the coordinate vectors of the elements of S, with respect to some
basis for V. (The latter choice is not important.) Then let C = RowSpace(M).
The rub is -- how do you pick S? I have been picking it more or less
randomly. But perhaps one can (by looking at the successful examples)
reverse the process to uncover a coherent philosophy behind picking S.
A number of people have suggested that the
Split program be extended to
codes over fields (or rings) other than F2. I keep hoping that a
coding theorist who loves to program will offer to get involved in this big
project.
It is my intention to write a better linear programming "engine" for use with
Split
(or for totally unrelated use). At present, Split relies on the
commercial program CPLEX, and on my own tentative implementation of the
simplex method. Again, I would love to have a collaborator for this
big project.