Non-cyclic Codes

Question

We are now studying all about cyclic codes. We determine when does a code C cyclic. My teacher give an easy example which is the Hamming Code. Then, he gave this question if there a non-cyclic hamming code. I've been reading for 2 hours now and no example or discussion about non-cyclic hamming codes, if it exists or not. If yes, how can we describe and construct it?

Answer 1

Indeed the following result holds:

Theorem: A Hamming-Code ${\mathrm Ham} [n,n-\ell]_q$ is equivalent to a cyclic code if and only if $gcd(\ell,q-1)=1$.

For $n=4$, $q=3$ and $\ell=2$ we obtain, for example, that the ternary Hamming code ${\mathrm Ham} [4,2]_3$ is not equivalent to a cyclic code, since $gcd(2,2)=2\neq 1$.

Answer 2

The smallest counterexample is the Hamming code of codimension $2$ over $\mathbb{F}_3$, as written in the answer of Dietrich Burde. This code has the parameters $[4,2,3]_3$.

To see that this Hamming code cannot be brought into cyclic form, we check the ternary cyclic $[4,2]_3$-codes, which are the candidates. From the factorization $X^4 - 1 = (X-1)(X+1)(X^2 + 1)$ into monic irreducible factors over $\mathbb{F}_3$, we see that there are two cyclic $[4,2]_3$ codes, given by the generator polynomials $(X^2 + 1)$ and $(X-1)(X+1) = X^2 - 1$. However, both generator polynomials have the Hamming weight $2$, so the generated codes cannot have minimum distance $3$.