Perfect codes ruled out for seven key radii in Johnson scheme
The Last Seven Open Radii for Perfect Codes in the Johnson Scheme
Information Theory
Summary
The Johnson scheme is a mathematical framework used in error correction, where 'perfect codes' can help detect and fix errors efficiently. A long-standing question was whether certain perfect codes exist for all parameter values. The authors prove that for seven specific error radii, no nontrivial perfect codes exist, closing a major open question completely. This confirms a 50-year-old conjecture and helps clarify the limits of perfect error correction in this setting.
What this means in practice
- •For coding theory engineers: Avoid attempting to design perfect error-correcting codes in the Johnson scheme for these seven radii, saving research and development effort.
- •For cryptography teams: Exclude certain perfect code structures from consideration when building secure combinatorial designs, reducing complexity of system design.
A theory result. No direct application yet.
Authors
Xiande Zhang, Wenjie Zhong
Abstract
Delsarte (1973) conjectured that there are no nontrivial perfect codes in the Johnson scheme. In this paper, we prove that there are no nontrivial $e$-perfect codes in the Johnson scheme for $e\in\{1,2,4,9,10,12,16\}$. This paper complements "Perfect Codes in the Johnson Scheme Hardly Exist", thus proving Delsarte's conjecture completely.