7
$\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.

$\endgroup$
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$.)

$\endgroup$
  • $\begingroup$ Awesome. By the way, how does one find "random" Type iii codes? $\endgroup$ – Theo Johnson-Freyd Mar 23 '18 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 Mar 23 '18 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 Apr 4 '18 at 19:15
  • $\begingroup$ (I want to repeat your calculations because I'm looking for codes with certain symmetries...) $\endgroup$ – Theo Johnson-Freyd Apr 4 '18 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 Apr 4 '18 at 19:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.