An improved lower bound for the Shannon capacity of $C_{11}$

Determine the Shannon capacity of the eleven-cycle $C_{11}$ , or improve its best explicit lower bound. The preceding BPZ construction, updated on 10 August 2026, gives an independent set of cardinality $N_0$ in dimension 207 and the lower bound $\Theta(C_{11}) \ge N_0^{1/207} = 5.29549231578462014255\ldots$ . The exact capacity remains open.

Result: Proved(see note)
Status: Partial result
AI contribution: AI co-developed
Method: Construction
Field: Zero-error information theory; graph capacity; combinatorics
Posed by: Claude Shannon (1956), underlying capacity problem; Buys, Polak and Zuiddam (2026), preceding C11 record
Year posed: 1956
Years open: 70y
Solved: 2026-09-08
Model: Astra 6 Pro; Codex GPT-6 Astra Extra-High
Vendor: OpenAI
Collaborators: Matthew Protti
Verification: Lean-checked, statement unaudited
Publication: Announced
Significance: 14 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

A sequence of explicitly constructed independent sets in strong powers of $C_{11}$ , with successive root improvements certified by exact integer comparisons, using cross-powers when dimensions differ. The current bound is $\Theta(C_{11}) \ge 5.295526013632343$ , from an independent set in $C_{11}^{\boxtimes 213}$ (R10, 9 September 2026), improving the R3 result of $5.295492477500681$ in dimension 207 that this entry was first listed for, and the Buys-Polak-Zuiddam baseline of $5.295492315784620$ . The intermediate steps R5 and R6 and the superseded R9 are recorded on the frontier. The exact capacity remains open, and no upper bound is claimed. The R5, R6, R9 and R10 builds carry disclosed native-evaluation dependencies rather than being kernel-only.

What the AI did

AI co-developed with OpenAI's Astra 6 Pro and Codex GPT-6 Astra Extra-High. Matthew Protti directed the research, evaluated proposals, required exact checks, set the scope and approved disclosure. The ChatGPT research collaboration supplied the R5 reassembly, R6 typed refinements and R9/R10 terminal certificates and written arguments. Codex replayed the finite certificates, wrote and compiled the Lean formalizations of actual independent sets, exact cardinalities and capacity bounds, inspected statement types and axiom dependencies, ran mathematical negative controls and prepared the releases. R9 and R10 import the checked R6 typed base and every child construction unchanged; only their terminal codes change. The underlying framework, base constructions and generic product machinery are due to Pjotr Buys, Sven Polak and Jeroen Zuiddam. These are author-side checks, not independent expert review.

Verification

The current R10 result is checked in v0.5.0 with Lean 4.32.2, BPZ commit aa21eeb12b75b0413d3fa9fb4208b5d0bf2c4d65 and Mathlib commit 905b95818eb32af7874a58b427f50c1711a5e96c. ShannonBounds.C11R10D213 proves an actual finite independent set in the 213th strong power of Mathlib's cycleGraph 11, its exact cardinality N, the capacity lower bound 5.295526013632343 and strict root comparisons with R6 and R9. A development build and separate fresh replay passed. Across the whole v0.5.0 consolidation, each run audited 184 numerical theorems and 261 symbolic declarations, with 246 distinct native Boolean-check axioms in the numerical audit, and rejected nine mathematical negative controls. Those counts are consolidation-wide, not R10-only. Numerical theorems retain inherited and new native-evaluation dependencies. Symbolic CellRetyping uses only propext, Classical.choice and Quot.sound; that does not remove numerical native trust. Both routes trust the pinned compiler/kernel, runtime and dependency binaries. Independent statement review, expert endorsement and exhaustive novelty clearance remain pending. Earlier R3 evidence is retained as history.

Sources

FrontierStep on Shannon capacity of C₁₁ · 5.295526013632343 · current best

Submitted by Matthew Protti on 08 Sep 2026

An improved lower bound for the Shannon capacity of C11C_{11}C11​

What was actually shown

What the AI did

Verification

Sources

Discussion

An improved lower bound for the Shannon capacity of $C_{11}$