Perfect Codes in the Johnson Scheme Hardly Exist

Abstract

In his pioneer work from 1973, Delsarte conjectured that there are no nontrivial perfect codes in the Johnson scheme J$(n,w)$. While in most other important schemes the existence problem for perfect codes was settled, the problem is still open in the Johnson scheme. In this work we considerably reduce the possible existence of such codes. We prove that there are no $e$-perfect codes in the Johnson scheme when $e\notin \{1,2,4,9,10,12,16\}$. These seven cases will be considered and solved in a follow up paper.