Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 42 min ago
PreprintCC BY 4.0arXiv

There Are No Nontrivial Perfect Codes in the Johnson Scheme

  • Tuvi Etzion
  • Xiande Zhang
  • Wenjie Zhong
Open at sourcePDFDOICite

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.

Related

  1. The Last Seven Open Radii for Perfect Codes in the Johnson Scheme
    Xiande Zhang, Wenjie Zhong
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. There are no nontrivial chordal square-complementary graphs
    Pierre Aboulker, Martin Milanič, Peter Muršič +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. There are no nontrivial uniquely C_9-saturated graphs
    Fayzan Khan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Subgroup Perfect Codes in Bi-Cayley Graphs
    Masoumeh Koohestani, Nasrin Soltankhah, Mohsen Ghasemi
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Quaternary Preparata codes are quasi-perfect covering codes in the Hamming metric
    Tamal Maharaj
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{etzion2026there,
  title = {{There Are No Nontrivial Perfect Codes in the Johnson Scheme}},
  author = {Tuvi Etzion and Xiande Zhang and Wenjie Zhong},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.23128},
  eprint = {2609.23128},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23128},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - There Are No Nontrivial Perfect Codes in the Johnson Scheme
AU  - Tuvi Etzion
AU  - Xiande Zhang
AU  - Wenjie Zhong
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.23128
UR  - https://arxiv.org/abs/2609.23128
AB  - 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.
ER  -