VibeMathedMath problems solved with AI
Sign in

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

Determine the Shannon capacity of the eleven-cycle C11C_{11}, or improve its best explicit lower bound. The preceding BPZ construction, updated on 10 August 2026, gives an independent set of cardinality N0N_0 in dimension 207 and the lower bound Θ(C11)≥N01/207=5.29549231578462014255…\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

An explicitly defined independent set of exactly N1N_1 words in C11⊠207C_{11}^{\boxtimes 207} gives Θ(C11)≥N11/207≥5.295492477500681\Theta(C_{11}) \ge N_1^{1/207} \ge 5.295492477500681. The full 150-digit integers N0N_0 and N1N_1 are frozen in CANDIDATE.json, and N1>N0N_1>N_0 is checked, so the new root strictly exceeds the complete BPZ baseline at the same dimension. The gain in the constructed root is approximately 1.617160609865×10−71.617160609865\times10^{-7}. At BPZ node x27, the replacement uses the N and A rows of T3d and all other rows of T3c, with the same ordered children h7, p11, h9. The base construction, remaining schedule, and terminal code are retained. This is a specific numerical improvement within BPZ's framework. It does not determine the exact capacity, prove optimality, or establish a new general two-sided heterogeneous extension. A public-source search on 8 September 2026 located no equal or stronger public C11 bound; worldwide priority is qualified by that search scope.

What the AI did

AI co-developed with OpenAI's Astra 6 Pro and Codex GPT-6 Astra Extra-High. Matthew Protti selected and directed the research, evaluated the proposed construction, required exact checks, set the claim's scope, and approved disclosure. The ChatGPT research collaboration developed the frozen auxiliary-row construction and Lean integration source. Codex ran the pinned Lean compiler, repaired audit-output compatibility in the harness, completed a fresh build and semantic negative controls, and prepared the preserved verification evidence and public release. The mathematical Lean construction supplied for compilation was unchanged. The work builds substantially on BPZ's existing framework, tables, base data, and terminal code.

Verification

The frozen construction passed a fresh BPZ and candidate build with Lean 4.32.2, BPZ commit aa21eeb12b75b0413d3fa9fb4208b5d0bf2c4d65, and Mathlib commit 905b95818eb32af7874a58b427f50c1711a5e96c. Scope aliases check an actual finite set in the 207th strong power of Mathlib's cycleGraph 11 with cardinality exactly N1, the capacity inequality derived from that set, and strict comparison with the full N0 root. Thirteen declarations were audited; all 193 distinct compiler-generated native dependencies across them were inspected as closed Boolean-equality axioms. Standard Lean axioms and native_decide/compiler-runtime trust are disclosed; this is not kernel-only arithmetic replay. False-cardinality and false-separation controls were rejected for the expected mathematical reasons. A clean public clone also passed the 272-file integrity and recorded-evidence check; that script does not rerun Lean. Independent statement anchoring, independent expert review, and exhaustive novelty clearance remain pending.

Sources

Submitted by Matthew Protti on

Changelog2 changes

Discussion