The Polak–Schrijver code has exactly eight private pairs (with the shannon repository, Stages 0–2W)

The lower bound on the Shannon capacity Θ(C7) improved four times between July and August 2026, and every improvement is built on one five-dimensional gadget: the 367-word independent set of Polak and Schrijver (IPL 143 (2019) 37–40) together with eight private pairs — vertices outside the code with a single neighbour in it. The private-pair count is the parameter those recursions are most sensitive to: a ninth pair would be worth 1.736·10−4 over the current record, about seven times the spread between the published recursions. Theorem (proved). In the whole of Z75 exactly eight vertices have a single neighbour in the Polak–Schrijver code, and they are precisely the eight in use. Their confusability graph is a matching with three edges, hence bipartite, so all eight are simultaneously usable and t* = 8. There is no ninth private pair for this code, and the route to a better bound that consists of adding one is closed. The proof is a non-mixing lemma plus two finite checks over 16807 vertices; it does not depend on the code in this repository. Exhaustive computations around the theorem. All eight 367-word codes the Polak–Schrijver construction can produce, with private-pair counts 5, 6, 6, 6, 7, 7, 7, 8 — the printed one is the unique best; the arithmetic that closes smaller codes (366 words would need 13 pairs, 365 would need 16); and a sweep of 8,260,976,640 (code, colouring, automorphism) triples under Aut(C7⊠5), in which the forbidden intersection is never empty — which is why the published construction has to replace one auxiliary vector, and the single offender is exactly the word (2,4,6,3,5) that Itty et al. replace. Exact repair reaches o = 322, the Buys–Polak–Zuiddam value, and no further. Stated as weaker than the theorem, because it is. Of the sixteen proper 2-colourings of the eight pairs, a 367-word admissible auxiliary set was found for exactly one — the one the literature uses, which no paper remarks on. For the other fifteen this is 1500 s of search finding nothing, not a proof, and the note says so. Method. An exact verifier in C with no dependencies, calibrated on the cases where it can fail (1177 corruptions, maximality sweeps, a deliberately defective build that has to be rejected); preregistration sealed before the first search run; RESULTS.md generated from stored results and never edited by hand; 171 verbatim quotations in SOURCES.md machine-checked against the dumped arXiv sources; and every number printed in the note reconciled by script against the computation behind it, an unsourced number counting as a failed build. Files. The note (PDF) and the repository archive at tag v1.0.0: the verifier, the reproductions, the sets with their SHA-256, the scripts behind every number, the note's LaTeX source and the literature checks. Code under Apache-2.0; texts, tables and data under CC BY 4.0. Third-party papers and publisher pages are not redistributed: the dumped arXiv e-prints that Rule 0 checks quotations against are omitted from the archive and are re-fetched by scripts/fetch_arxiv.sh (see sources/README.md); SOURCES.md carries only short verbatim quotations with precise references.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-26
DOI
https://doi.org/10.5281/zenodo.22972847
Primary Topic
Coding theory and cryptography
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

The Polak–Schrijver code has exactly eight private pairs (with the shannon repository, Stages 0–2W)

Artem Oktiabrev
Zenodo (CERN European Organization for Nuclear Research)
Coding theory and cryptography
preprint

The Polak–Schrijver code has exactly eight private pairs (with the shannon repository, Stages 0–2W)

Artem Oktiabrev
preprint en

Abstract

The lower bound on the Shannon capacity Θ(C7) improved four times between July and August 2026, and every improvement is built on one five-dimensional gadget: the 367-word independent set of Polak and Schrijver (IPL 143 (2019) 37–40) together with eight private pairs — vertices outside the code with a single neighbour in it. The private-pair count is the parameter those recursions are most sensitive to: a ninth pair would be worth 1.736·10−4 over the current record, about seven times the spread between the published recursions. Theorem (proved). In the whole of Z75 exactly eight vertices have a single neighbour in the Polak–Schrijver code, and they are precisely the eight in use. Their confusability graph is a matching with three edges, hence bipartite, so all eight are simultaneously usable and t* = 8. There is no ninth private pair for this code, and the route to a better bound that consists of adding one is closed. The proof is a non-mixing lemma plus two finite checks over 16807 vertices; it does not depend on the code in this repository. Exhaustive computations around the theorem. All eight 367-word codes the Polak–Schrijver construction can produce, with private-pair counts 5, 6, 6, 6, 7, 7, 7, 8 — the printed one is the unique best; the arithmetic that closes smaller codes (366 words would need 13 pairs, 365 would need 16); and a sweep of 8,260,976,640 (code, colouring, automorphism) triples under Aut(C7⊠5), in which the forbidden intersection is never empty — which is why the published construction has to replace one auxiliary vector, and the single offender is exactly the word (2,4,6,3,5) that Itty et al. replace. Exact repair reaches o = 322, the Buys–Polak–Zuiddam value, and no further. Stated as weaker than the theorem, because it is. Of the sixteen proper 2-colourings of the eight pairs, a 367-word admissible auxiliary set was found for exactly one — the one the literature uses, which no paper remarks on. For the other fifteen this is 1500 s of search finding nothing, not a proof, and the note says so. Method. An exact verifier in C with no dependencies, calibrated on the cases where it can fail (1177 corruptions, maximality sweeps, a deliberately defective build that has to be rejected); preregistration sealed before the first search run; RESULTS.md generated from stored results and never edited by hand; 171 verbatim quotations in SOURCES.md machine-checked against the dumped arXiv sources; and every number printed in the note reconciled by script against the computation behind it, an unsourced number counting as a failed build. Files. The note (PDF) and the repository archive at tag v1.0.0: the verifier, the reproductions, the sets with their SHA-256, the scripts behind every number, the note's LaTeX source and the literature checks. Code under Apache-2.0; texts, tables and data under CC BY 4.0. Third-party papers and publisher pages are not redistributed: the dumped arXiv e-prints that Rule 0 checks quotations against are omitted from the archive and are re-fetched by scripts/fetch_arxiv.sh (see sources/README.md); SOURCES.md carries only short verbatim quotations with precise references.

Zenodo (CERN European Organization for Nuclear Research)
Peace, Justice and strong institutions
Coding theory and cryptography
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.