There Are No Nontrivial Perfect Codes in the Johnson Scheme

Abstract

In his seminal work from 1973, Delsarte conjectured that the Johnson schemes admit no nontrivial perfect codes. We prove this fundamental conjecture which is central in combinatorial coding theory. Our arguments combine lower bounds on the design strength of a perfect code with divisibility conditions for the size of a metric ball. We show that the ball size divides the greatest common divisor of specified binomial coefficients. An exact formula for this gcd implies squarefreeness and localizes a power of each prime divisor of the ball size to a short interval. Lloyd polynomials, explicit prime estimates, and bounds for linear forms in logarithms then exclude all sufficiently large radii. Additional arithmetic arguments handle the remaining radii.