1
$\begingroup$

In this question about perfect 2 error correcting codes on the Open Problem Garden, it is stated that:

Recent research activity has discovered a large number of previously unknown perfect 1-error correcting codes which are not isomorphic to the Hamming codes.

In terms of context, the following is well known for $t-$error correcting codes over finite alphabets:

No perfect $t-$error correcting codes other than the repetition codes (any $t\geq 1,$ any alphabet, odd length), the Hamming codes (binary alphabet, $t=1$) and the two Golay codes (binary with length $n=23$ and $t=3$ and ternary with length $n=11,$ and $t=2$) exist in the Hamming metric when the alphabet size $q$ is a prime power.

Question: Does anyone here know what these (recently found circa 2010) codes are?

The below is the stated open question for $t=2,$ but to be a conjecture it must actually say there are or there aren't such codes:

Conjecture: Does there exist a nontrivial perfect 2-error-correcting code over any finite alphabet, other than the ternary Golay code?

$\endgroup$

2 Answers 2

2
$\begingroup$

Back in 1986, Phelps provides many examples which is clear from the title of his paper Every finite group is the automorphism group of some perfect code, J. Combin. Theory Ser. A43(1986), no.1, 45–51.

$\endgroup$
1
  • $\begingroup$ I am specifically interested in the alphabet sizes $q,$ e.g., $q=6,$ where it is open whether a perfect code exists. It is not clear to me from the paper if it applies to nonbinary codes and how. $\endgroup$
    – kodlu
    Commented Aug 12, 2023 at 4:25
2
$\begingroup$

You can find a lot of information in the recent book: "Perfect Codes and Related Structures," by T. Etzion. The notes to Chapter 5 contain a long list of references. In particular, if you're interested in codes over general alphabets, the best (to my knowledge) necessary condition appears in: O. Heden and C. Roos, "The non-existence of some perfect codes over non-prime power alphabets," Discrete Mathematics, vol. 311, no. 14, pp. 1344-1348, 2011.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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