A perfect code is an error-correcting code whose error-correction balls partition the space of words. Let 
be an error-correcting
code consisting of 
codewords, in which each codeword
consists of 
letters taken from an alphabet 
of length 
, and every two distinct codewords
differ in at least 
places. Then 
is said to be perfect if for every possible word 
of length 
with letters in 
, there is a unique code word 
in 
in which at most 
letters of 
differ from the corresponding letters of 
.
It is straightforward to show that 
is perfect if
 |
If 
is a binary linear code, then 
and 
, where 
is the number of generators of 
, in which case 
is perfect if
 |
Among nontrivial linear codes over finite fields, the perfect codes are the Hamming codes and Golay codes (MacWilliams and Sloane 1977).
In the Johnson graph metric, a nontrivial perfect code would instead partition the constant-weight words into equal-radius balls. Zhang
and Zhong (2026) proved that no nontrivial 
-perfect codes exist in the Johnson scheme for 
, 2, 4, 9, 10, 12, or 16. Together with the previously settled
radii, this proves the conjecture that the Johnson scheme has no nontrivial perfect
codes.
The same partition principle applies to the graph distance in a graph. A perfect 1-code in this setting is an efficient dominating set, whose closed neighborhoods partition the vertex set (Biggs 1973).
