I've asked this question on math.stackexchange before, but it has not been solved.

The following statement appears to be true:

The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is equivalent to a cyclic code if and only if if $q-1$ and $r$ are coprime.

See for example this answer on math.stackexchange.

The $\Leftarrow$-direction is not too hard to show (see for example the last paragraph of this answer), but I could not find a proof for the other direction anywhere. I've checked various sources like web search, search on mathoverflow and math.stackexchange, as well as standard books on coding theory like MacWilliams-Sloane, van Lint or Huffman-Pless.

So my question is how to show $\Rightarrow$. Preferably by means available in a typical lecture on algebraic coding theory.

  • $\begingroup$ The direction that you can already prove is proved in an answer to this earlier MO question, mathoverflow.net/questions/145345/cyclic-hamming-code $\endgroup$ – Gerry Myerson Oct 8 at 8:54
  • $\begingroup$ @GerryMyerson thank you. In fact, I came across of that answer when searching MO. I've already linked that answer above. But as all sources that I've checked, the "interesting" direction is not there. $\endgroup$ – azimut Oct 8 at 9:01
  • 1
    $\begingroup$ Sorry, I saw the links to m.se and missed the link to MO. $\endgroup$ – Gerry Myerson Oct 8 at 9:05
  • $\begingroup$ @GerryMyerson I'm happy when people care for my question. Also interesting that this statement has been touched both on MO and math.SE in the past, but the missing direction has always been dodged. It's the same situation as in the literature that I've checked, for example the book of Huffman and Pless. $\endgroup$ – azimut Oct 8 at 9:17
  • 1
    $\begingroup$ @SteveHuntsman thank you. I just checked that source: It shows that for a primitive element $\alpha$ of $\mathbb{F}_{q^r}$, the cyclic code with check polynomial given by $\alpha^{q-1}$ is a Hamming code if and only if q-1 and r are coprime. But I don't see how this is a full proof of the direction ⇒, because we don't know yet that the cyclic description of a Hamming code is necessarily of the form studied in Th. 5.5.1. For example, the check polynomial might not be irreducible. $\endgroup$ – azimut Oct 8 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.