# What odd-length binary codes have Hamming weights restricted to be multiples of eight?

Let $G$ be a $k$ by $n$ binary matrix with row vectors $\lbrace \vec{x}_j {\rbrace} _{j=1}^k$. We can interpret $G$ as a generator matrix of a linear $[n,k]$ code $\cal{C}$ whose codewords consist of all linear combinations of these vectors (with arithmetic defined for GF(2)).

Let $H$ be a $(n-k)$ by $n$ binary matrix with row vectors $\lbrace \vec{y}_j {\rbrace} _{j=1}^{n-k}$ where $\vec{x}_a \cdot \vec{y}_b = 0~\forall a, b$. We can interpret $H$ as a parity check matrix for code $\cal{C}$. Alternatively, we can treat $H$ as the generator for the dual $[n,n-k]$ code $\cal{C}^\perp$.

If we require both that $n$ be odd and that all codewords of $\cal{C}$ (not just the rows of $G$) have a Hamming weight $w_j \equiv 0$ (mod 8), what minimum distances are possible for $\cal{C}^\perp$? What families of codes satisfy these properties?

So far, I have identified the following examples:

distance 2: $\cal{C}$ = [8,1,8] repetition code, $\cal{C}^\perp$ = [8,7,2]

distance 3: $\cal{C}$ = [15,4,8] Reed-Muller code, $\cal{C}^\perp$ = [15,11,3] Hamming code

My previous example (based on the Golay code) for distance 4 was incorrect. It was only distance 3, and in fact I have repeatedly failed to find a good candidate with distance larger than 3.

Here is a link to the MacWilliams identity (which I am having problems putting into a comment).

-
Do you look at the MacWilliams transform of $\mathcal{C}$? It does provide a lot of conditions on $\mathcal{C}^\perp$. – Dima Pasechnik Jul 5 '12 at 4:12
Thanks. It's been a long while since I've played around with the MacWilliams identity, and that does look very informative for finding the minimum distance of $\cal{C}^\perp$, namely by finding the first nonzero term for $x$ in the expansion of the weight enumerator $W(\cal{C};y−x,y+x)$. I suppose the better question then may be how to first identify/construct a candidate code $\cal{C}$. – Jim Harrington Jul 5 '12 at 5:08
Some trace codes will surely have this property. A theorem of Ax has been used in the past to give precise information about divisibility of weights by a power of two. IIRC Oscar Moreno & P.V. Kumar have published something about this. I would begin by searching for applications of Ax's theorem to this. Trace codes have typically a relatively low rate. Therefore the dual are correspondingly very large and have relatively small minimum Hamming weights. – Jyrki Lahtonen Jul 5 '12 at 13:25

In Weight Divisibility of Cyclic Codes, Highly nonlinear functions on $F_{2^m}$, and crosscorrelation of maximum length sequences, Canteaut, Charpin, and Dobbertin (Siam J. Discrete Math. 13(1):105-138) this problem was considered for Cyclic codes.
The classical McEliece's theorem states that a binary cyclic code $C$ is exactly $2^{\ell}$ divisible if and only if $\ell$ is the minimum integer such that $\ell+1$ nonzeros of $C$, i.e., roots of the parity check polynomial, have product 1 with repetition allowed.