shannon — lower bounds on the Shannon capacity of odd cycles

Θ(C₇) = sup_d α(C₇^⊠d)^(1/d) is unknown. This repository is the working record of an attempt on the lower bound, starting — as every stage here does — from a verifier that can fail, and from a literature check that can contradict the plan.

Stage 0 built the instruments and found the plan out of date. Stage 1 did the search. Stage 2W writes the result up: note/note.tex, six pages, with every number in it reconciled by script against the stored computation.

• an exact verifier for independence in C_n^⊠d (scripts/verify.c, C, no dependencies);
• three published constructions rebuilt from their papers and verified;
• an exact reproduction of the current record recursion, including a 103-digit integer;
• a search stack calibrated on two known optima — α(C₇^⊠3) = 33 proved exactly, α(C₇^⊠4) ≥ 108 found;
• and the answer to the question Stage 1 was set: there is no ninth private pair.

Everything in RESULTS.md is generated by scripts/make_results.py. Every external number is backed by a verbatim quotation in SOURCES.md, and scripts/check_sources.py re-checks all 171 of them against the dumped LaTeX sources.

The Stage 1 result

The current record for Θ(C₇) rests on a gadget in C₇^⊠5 with eight private pairs — vertices just outside the 367-word Polak–Schrijver code that see exactly one of its members. Every improvement since July 2026 has come from that gadget's parameters. Stage 1 asked whether a ninth pair exists.

It does not, and that is a theorem. Exactly eight vertices of the whole of Z₇⁵ have a single neighbour in the code, and they are precisely the eight in use. The count is fragile rather than lucky: our own reproduction of the same construction, differing in two words, admits only six, and across all eight codes the Polak–Schrijver pipeline can produce the counts run 5, 6, 6, 6, 7, 7, 7, 8 — the printed one being the unique best. A sweep of 8.26·10⁹ images under Aut(C₇^⊠5) shows that no image of any of those codes is even admissible as the gadget's auxiliary set, which is why the published construction has to replace one vector; repairing them exactly lands on o = 322, the Buys–Polak–Zuiddam value, and no further.

So the lever Stage 0 identified is already at its stop. What is left needs a 367-word code from outside that construction, or a base gadget in a different dimension.

The headline

The task this repository was set named α(C₇^⊠10) ≥ 134753 (arXiv:2607.21517, July 2026) as the state of the art, and asked whether anything newer existed. It did. Three times over:

	Θ(C₇) ≥	reproduced here
Polak–Schrijver 2019	3.2578659667835159…	yes — rebuilt from the circular graph C₍₁₀₈,₃₈₂₎, not copied
Itty–Rosin–Carstensen–Reichman, Jul 2026	3.2580207372932453…	yes — 134753 vertices rebuilt and verified
Gao, Jul 2026	3.2587891539086910161967650155206769…	yes — exactly, including M₄₀ digit for digit
Buys–Polak–Zuiddam, Jul 2026	3.2588053698854655725829750306…	yes — exactly
Tandon, Aug 2026 — the record	3.2588326203532663091215390518…	no (framework not reimplemented)
upper bound, Lovász 1979	ϑ(C₇) = 3.3176672073940953927332082980…	yes — 50-digit recomputation

And the fact that reshapes Stage 1: the dimension is not the lever. Gao proves the recursion saturates; running the dynamic programme to 160 five-dimensional blocks confirms the maximum is attained at exactly 40 blocks, dimension 200. All three gains since July 2026 came from the structure of a gadget living in C₇^⊠5 — 16807 vertices, a few kilobytes — not from searching a graph with 7²⁰⁰ vertices.

The verifier

Two distinct vertices of C_n^⊠d are adjacent iff their circular distance is at most 1 in every coordinate. For n ≥ 4 that happens exactly when the boxes ∏ᵢ{xᵢ, xᵢ+1} intersect, so

a set is independent ⟺ its |I|·2^d box cells are pairwise distinct.

The quadratic pair test becomes one linear sweep into an occupancy bitmap over Z_n^d — integer arithmetic only, no floating point, no heuristic, and exact. On this host it clears 1.3 million vertices in C₇^⊠12 (5.5·10⁹ cells) in 11 s on one CPU core and 0.5 s on an RTX 4070 Ti, in under 1 GiB, and the two agree on every set.

$ scripts/verify sets/C7_d10_134753_itty_et_al.txt --maximal
file       : sets/C7_d10_134753_itty_et_al.txt
sha256     : 947cc24241a3adc8a38fae258fb2b5bd59ff35bc56b603c3ad7235fe77afefd3
graph      : C_7^10   (universe 282475249 vertices)
size       : 134753
box test   : INDEPENDENT  (137987072 cells, 1 pass(es), 0.438 s, 3.15e+08 cells/s)
maximality : MAXIMAL (no vertex can be added)
result     : PASS

(One run; the sweep is timed three times over in results/json/bench.json, where it comes out at about 10⁹ cells/s warm; throughput varies ~10% between runs.)

A verifier that answered INDEPENDENT unconditionally would pass every reproduction in this repository, so scripts/calibrate.py puts it through the cases where it can fail: 1177 single-vertex corruptions with independently computed ground truth, including 18 that leave the set independent and must be reported as such; exhaustive maximality over all 7^d vertices; agreement with the plain quadratic test at d = 2, 3, 4 on independent and dependent inputs; agreement between the single-pass and the 34-pass low-memory path; random and planted negative controls; and α(C_n^⊠2) recomputed from scratch for n = 5, 7, 9, 11, 13 against ⌊(n²−n)/4⌋.

Finally, the tests are shown to have teeth: a deliberately defective build of the same verifier (verify_mutant, which sees only repeated vertices) is run through them and is rejected.

What did not work

One thing in Stage 0 failed and is reported as failing: the exact solver, given an hour on the 343-vertex graph C₇^⊠3, reached an independent set of size 32 and proved no optimum, against the known α(C₇^⊠3) = 33. So that value stays a citation. The same solver proves the optimum for C₅^⊠2, C₇^⊠2, C₉^⊠2, C₁₁^⊠2 and C₁₃^⊠2 in at most 1.3 s, which is what it is used for.

What is in here

RESULTS.md	generated — the report for all three stages, never edited by hand
note/	the write-up: note.tex, refs.bib, and the compiled note.pdf (6 pages)
SOURCES.md	Rule 0: 171 verbatim quotations, machine-checked against sources/
METHODS.md	S0.3 — the seven families of method, what each costs, where each stops
PREREGISTRATION_S1.md	Stage 1, sealed 2026-09-25 before any search run
sets/	the reproduced independent sets, one vertex per line, with SHA-256
scripts/	the verifier, the exact MIS solver, the reproductions, the benchmarks
sources/	the dumped arXiv e-prints the quotations are taken from
results/json/	every number the report is built from

Stage 2W — the note

note/note.tex states the theorem, its proof, and the exhaustive computations around it in six pages, with the two search-based observations labelled as evidence rather than proof. Three scripts hold it in place:

• scripts/w_gate.py — before writing, the question of whether anyone has already claimed maximality: every sentence of every dumped paper that mentions private pairs, transversals or colourings together with a word of maximality or uniqueness is listed (22 of them) and read. None does, and nothing on C₇ has appeared since arXiv:2608.30273.
• scripts/w_theorem.py — recomputes what the proof displays (the neighbour histogram over all of Z₇⁵, the eight candidates, the three conflict edges, the single offending word of T(I)) and cross-checks it against the Stage 1 results.
• scripts/w_checknums.py — a ledger of 66 entries, each checked against results/json and against the note; then the note is swept backwards, and any number in it that no computation backs fails the build. Six entries are lists rather than numbers, so a reordered list fails too.

The venue's own rules are treated the same way: scripts/fetch_venue.sh dumps the publisher pages and scripts/w_venue.py re-checks each quotation against the dump, with what could not be fetched from this host marked unverified rather than recalled from memory.

Reproducing

scripts/run_all.sh      # ~10 minutes, plus a one-hour ceiling on the exact alpha(C_7^3) attempt

Requirements: gcc, python3 with no packages at all, curl. nvcc is optional and only affects the GPU column of S0.4. Nothing is installed; nothing is carried over from other projects.

The search stack

engine	what it is	proves?
E1 s1_alpha3	exact cyclic layer search; pins C₇^⊠3 onto the 980 maximum 2-dimensional packings	yes
E2 s1_ils	local search, then fixed-cardinality tabu search	no
E3 s1_sym	prescribed symmetry on the orbit graph of an explicitly checked group	no
E4 s1_lns	large-neighbourhood search with exact repair inside a window	inside the window

Calibrated before use, as the brief required. E1 settles α(C₇^⊠3) = 33 in 42 s — Stage 0's generic solver spent an hour and returned 32 with no proof — and a deliberately broken build of it claims 35, so the test has teeth. The ladder to α(C₇^⊠4) ≥ 108 records four changes of method: 102 (E2) → 105 (E3) → 106 (E2 tabu) → 107 (E2+E4) → 108. Every rung was checked by scripts/verify, which knows nothing about how the set was found.

The rewritten history, and what is authoritative

On 2026-09-26 the public history of this repository was rewritten (git filter-repo --invert-paths) to remove the dumped arXiv e-prints from every commit, not only from the current tree. The reason is in sources/LICENCES.md: two of the six papers the quotations are checked against — Mathew–Östergård and, of all papers, Polak–Schrijver itself — are under arXiv's perpetual non-exclusive licence, which grants no right to redistribute them. Quoting them in SOURCES.md is quotation; shipping their PDFs in a public repository was redistribution.

Every commit hash therefore changed. The correspondence is in COMMIT-MAP.txt (old hash, new hash, one pair per line), and the two tags now read:

tag	commit	Zenodo record	archive in the record	md5 of that archive
v1.0.0	61776ec	10.5281/zenodo.22972847	shannon-1.0.0.tar.gz	17db1bc3d4cdcd9f295b1dfee0550f51
v1.1.0	2be4cd7	10.5281/zenodo.22979509	shannon-1.1.0.tar.gz	7fdfc7e3f542f9381d40c895e77cf095

For the archived versions the tarball in the record is authoritative, not a commit hash. The v1.0.0 archive was built from a commit that no longer exists in the public history, so a reader comparing the two should compare contents: scripts/w_archive.py downloads each record's tarball, unpacks it beside git archive <tag> and reports every difference. Its result is in results/json/w_archive.json, and today it is: v1.0.0 — the tarball holds 107 files, the tag 113, and the six extra files in the tag are the sources/<id>/SHA256 checksums that the v1.0.0 archive's pruning removed by mistake (stated and fixed in v1.1.0); no file differs in content. v1.1.0 — 124 files on both sides, identical.

Licences

• Code (scripts/) — Apache-2.0, see LICENSE.
• Texts, data and the note (README.md, RESULTS.md, SOURCES.md, METHODS.md, PREREGISTRATION_S1.md, note/, sets/, results/) — CC BY 4.0, see LICENSE-docs.
• Quotations from third-party works in SOURCES.md remain under their holders' copyright. The e-prints the quotations are checked against are not in this repository: sources/ keeps only each dump's SHA-256, and scripts/fetch_arxiv.sh re-fetches the papers themselves — two of the six are under arXiv's non-exclusive licence, which grants no redistribution right (sources/LICENCES.md). The publisher pages behind scripts/fetch_venue.sh are not redistributed either.

How to cite

The archive of this repository and the note: doi:10.5281/zenodo.22972846 (concept DOI, always the latest version; version 1.1.0 is doi:10.5281/zenodo.22979509). CITATION.cff carries the machine-readable form.

@misc{oktiabrev2026eightpairs,
  author    = {Oktiabrev, Artem},
  title     = {The Polak--Schrijver code has exactly eight private pairs
               (with the shannon repository, Stages 0--2W)},
  year      = {2026},
  doi       = {10.5281/zenodo.22972846},
  publisher = {Zenodo}
}