There Are No Nontrivial Perfect Codes in the Johnson Scheme
math.CO
Submitted: 2026-09-19
Updated: 2026-11-19
License: http://creativecommons.org/licenses/by/4.0/
The gist: In his seminal work from 1973, Delsarte conjectured that the Johnson schemes admit no nontrivial perfect codes.
Terminology
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.
Sources
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality