Record Lower Bounds for the Shannon Capacity of Odd Cycles

Determine the Shannon capacities of odd cycles beyond $C_5$ , or improve the best explicit bounds. Lovasz's theta function settled $C_5$ in 1979 and every longer odd cycle has stayed open since. The current records, all obtained with model assistance and formally verified, are $\Theta(C_7) \ge 3.258805369885$ , $\Theta(C_{11}) \ge 5.294502522149$ , $\Theta(C_{13}) \ge 6.302455083464$ , $\Theta(C_{15}) \ge 7.301600534487$ , $\Theta(C_{19}) \ge 9.357192705918$ , $\Theta(C_{21}) \ge 10.342455853338$ and $\Theta(C_{23}) \ge 11.328224257774$ .

Result: Proved(see note)
Status: Partial result
AI contribution: AI-discovered
Method: Construction
Field: Zero-error information theory
Posed by: Claude Shannon
Year posed: 1956
Years open: 70y
Solved: 2026-07-31
Model: ChatGPT 5.6 Sol Pro, ChatGPT 5.6 Sol, Claude Opus 5
Vendor: OpenAI / Anthropic
Collaborators: Pjotr Buys, Sven Polak, Jeroen Zuiddam, Yu Gao, Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman
Verification: Lean-verified
Publication: Preprint
Significance: 35 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

record lower bounds for seven odd cycles; the exact capacities remain open for every odd cycle beyond C5

What the AI did

Three model-assisted papers in eleven days, each beating the last. Itty, Rosin, Carstensen and Reichman had ChatGPT-5.6 Sol Pro generate and run search programs across repeated prompts, returning explicit independent sets in strong graph powers that the authors checked. Gao then improved $C_7$ with a recursive construction and states that ChatGPT 5.6 Sol implemented all the code and expanded the proofs. Buys, Polak and Zuiddam followed both methods using ChatGPT 5.6 Sol Pro and Claude Opus 5, beat every previous bound, added three more cycles, and formalised the lot in Lean.

Verification

The current records are formalised in Lean 4 at the linked repository, one base tuple per bound, so the seven stated inequalities are machine-checked rather than author-checked. We have not compiled it. Gao's intermediate record ships exact-integer verification code pinned to a fixed commit, and the earlier Itty-Rosin-Carstensen-Reichman constructions came with public data, prompts and checking code. All three are arXiv preprints; none is peer-reviewed.

Sources

FrontierStep on Shannon capacity of C₁₁ · 5.294502522149 · a step on the frontier, since improved

Record Lower Bounds for the Shannon Capacity of Odd Cycles

What was actually shown

What the AI did

Verification

Sources

Discussion