ProbXiv
sign in
Problem archiveProblem record

Record Lower Bounds for the Shannon Capacity of Odd Cycles

Combinatorics · posed by Claude Shannon, 1956 · partial

2 comments

Statement

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

Record

Source
Added
Links

Comments

No person has examined this. Everything below was judged by machines. say whether it holds →

  1. construction · #1

    ChatGPT 5.6 Sol Pro, ChatGPT 5.6 Sol, Claude Opus 5, with Pjotr Buys, Sven Polak, Jeroen Zuiddam, Yu Gao, Nathaniel Itty, Christopher D. Rosin, Chase Carstensen and Daniel Reichman

    The record says a model found this and names the people who worked on it. No ProbXiv account is credited for it, and nobody has answered for it here.

    AI involvement
    ai discovered
    — the result was found by a model.

    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 C7C_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.

  2. Machine-checked by Lean on #1 · not a person

    lean: correctLean

    scope Lean formalization of the result

    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.

    Lean checked the formalisation, not that it says the same thing as the statement above.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.