8
$\begingroup$

Recall that a Type III code of rank $r$ is a linear subspace $C \subset \mathbb F_3^r$ which is self-dual for the standard inner product. (These occur only when $r$ is divisible by $4$.) Elements of $C$ are called code words. The Hamming weight of a code word is its number of non-zero entries. I will call a code word maximal if its Hamming weight is $r$. (Maximal codewords clearly only occur when $r$ is divisible by $12$.)

The set of maximal codewords can be partitioned into two subsets as follows: two maximal words $w_1,w_2$ are in the same subset if $w_1-w_2$ has even Hamming weight, and are in opposite subsets if $w_1-w_2$ has odd Hamming weight. Call these subsets $M_+$ and $M_-$.

I suggest the following definition:

Definition: The index of $C$ is $|M_+| - |M_-|$. Of course, this is only defined up to sign. I could take its absolute value if I cared. The name is because this is related to the "supersymmetric index" of a certain supersymmetric field theory.

The discussion in the comments of this question implies the following when $r$ is divisible by $24$:

Proposition: The index of any Type III code of rank $r=24k$ is divisible by $24$.

Conjecture: This is true also when $r \equiv 12 \mod 24$. (It is trivially true for $r \equiv \pm 4 \mod 12$, as then $M_\pm$ are empty.)

Moreover, I suspect that both $|M_+|$ and $|M_-|$ are necessarily divisible by $24$.

Example: The Ternary Golay code, with rank $12$ has index $24$. It is the unique rank-$12$ code with non-zero index.

Example: The complete classification of Type III codes of rank $24$ is known. Assuming I read it correctly, there are precisely five codes of rank $24$ and index $24$.

Question: In higher rank, do there exist Type III codes with index exactly $24$? For example, what about rank $36$?

At best, there would be some general algorithm that produces a code with index $24$ for each rank $r = 12k$.

By the way, I know how to prove:

Proposition: If the code $C$ contains words of Hamming weight $3$, then its index vanishes.

So if you are looking for such a code, you know not to look at such codes.

It's pretty easy to show:

Lemma: The index multiplies when you take the direct sum of codes.

Since $24^2$ is pretty big, you probably will want to work with indecomposable codes.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Index $24$ isn't hard for length $36$. For example, the Type III code with generator matrix

+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 + - + 0 - - + 0 + + - + + - 0 -
0 + 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 - + - - 0 0 - 0 0 0 0 - + - - -
0 0 + 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 - + 0 + - - - + + - + 0 - 0 - +
0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 + 0 + - + 0 0 + 0 + 0 - - + -
0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 0 0 - + 0 0 - 0 - + 0 + 0 - - 0 + 0 + -
0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 0 + - 0 - - 0 + + 0 + 0 + 0 - 0 - + 0
0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 - + 0 0 - + 0 - - 0 0 - + - 0 0 - +
0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 + + - - - - - + 0 + - - - 0 + - 0
0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 + + - - + + 0 + - 0 + 0 0 + + + + -
0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 - + + + 0 0 - + + - + - - 0 + 0 - -
0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 + + 0 0 0 - + + + + + 0 - 0 - 0 0 +
0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 + 0 0 0 - - + 0 0 - 0 + - - + 0 - +
0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 + 0 - 0 0 - + - - 0 - + + - 0 0 +
0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 + 0 - + - - - - 0 0 - 0 - - - - - -
0 0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 - 0 - - - 0 + + 0 + - 0 - 0 - + 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 + - - + 0 0 - 0 - + - + - - - + + 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 - 0 + - 0 - 0 + 0 - - 0 + 0 0 - - -
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + 0 + + + + - + 0 - - 0 + 0 + - - - +

has index $24$. (The total number of maximal codewords is $520$; of $70$ "random" Type III codes I tried, $26$ had index $24$ -- which indeed was the most common index -- and all had index divisible by $24$, while the number of maximal codewords was always a multiple of $8$ but not necessarily $24$.)

Improve this answer
$\endgroup$
7
  • $\begingroup$ Awesome. By the way, how does one find "random" Type iii codes? $\endgroup$
    – Theo Johnson-Freyd
    Commented Mar 23, 2018 at 18:57
  • 1
    $\begingroup$ Thanks! One way to choose a code uniformly at random is to randomly choose a nonzero word of weight $0 \bmod 3$, then randomly choose another in its orthogonal complement, etc. At each step at least $1/3$ of words in the subspace satisfy the mod-3 condition, so if at first you don't succeed, try, try again. Meanwhile I generated a few hundred more examples of length $36$, and it's still true that plenty of them have index $24$ (and none violates the mod-$24$ conjecture). The same seems to happen for length $48$, though here the calculation for each code is much slower. $\endgroup$
    – Noam D. Elkies
    Commented Mar 23, 2018 at 19:17
  • $\begingroup$ You are either more patient than I am or you have a faster way to find the list of all maximal codewords than I do. I can generate self dual codes of length 36, but I can't seem to calculate their indexes in a reasonable amount of time, and certainly not fast enough to repeat your trial-and-error search. $\endgroup$
    – Theo Johnson-Freyd
    Commented Apr 4, 2018 at 19:15
  • $\begingroup$ (I want to repeat your calculations because I'm looking for codes with certain symmetries...) $\endgroup$
    – Theo Johnson-Freyd
    Commented Apr 4, 2018 at 19:17
  • 1
    $\begingroup$ Once the code is in the form $(I_{r/2} | A)$, all you need is to list the vectors $x$ such that both $x$ and $Ax$ have maximal weight. All I did was try all $2^{r/2}$ possible $x$. Actually only half of them, since we can assume the first coordinate is $+1$. For $r=36$, that's $131072$ candidates, which takes a few seconds in gp (and probably a fraction of a second in C). So, little patience is required. I needed to be a bit more patient for $r=48$ when the time per code was measured in minutes. I can e-mail you my gp code if it would be of use. $\endgroup$
    – Noam D. Elkies
    Commented Apr 4, 2018 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .