Lean-verified lower bounds for the Shannon capacity of odd cycles

Jeroen Zuiddam; Pjotr Buys; Sven Polak

REVIEW 3 major objections 4 minor 14 references

Lean-verified lower bounds for the Shannon capacity of odd cycles

T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes new lower bounds for the Shannon capacity of the odd cycles C7, C11, C13, C15, C19, C21, and C23, each obtained by composing small 'valid tuple' profiles under a star product and each certified in the Lean proof assis

desk verdict Seven new Shannon-capacity lower bounds that hinge on an unpinned Lean repo — credible but not independently verifiable from the text. read the letter →

arxiv 2607.29681 v1 pith:TJPUHTZO submitted 2026-07-31 math.CO cs.ITmath.IT

Pjotr Buys , Sven Polak , Jeroen Zuiddam This is my paper · ORCID

classification math.COcs.ITmath.IT MSC 05C6994A24

keywords ShannoncapacityoddcycleslowerboundsindependentsetsstrongpowersvalidtuplesprofilestarproductLeanformalisation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish concrete lower bounds for the Shannon capacity of seven odd cycles. Its method starts from a small 'valid tuple'—an independent set with extra structure—in a fixed power of each cycle, records only a four-number profile, and repeatedly composes profiles under a star product supplied by Theorem 1. The final profile's first coordinate is an independent set in a much larger strong power, and its d-th root is the stated capacity bound. Each bound improves the previously known value, and every step of the construction is claimed to be machine-checked in Lean. A sympathetic reader would care because these are among the few explicit numerical handles on capacities that have been open for decades.

What carries the argument

The load-bearing object is the 'valid tuple' $\tau=(I,S,f_0,f_1,X)$ plus its profile $\Pi(\tau) = (|I|, |S|, |X|, |X \setminus (N[f_0(S)] \cup N[f_1(S)])|)$, together with the star product on four-tuples. The paper imports Theorem 1, which says that star-multiplying profiles of valid tuples for $G$ and $H$ yields a valid tuple for $G \boxtimes H$; the first profile coordinate is an independent-set size. The computational work is then just a few lines of profile arithmetic per cycle—a base profile followed by explicit star-squares—which transforms a small finite search into an exponentially larger independent set.

What would settle it

Run the Lean checker on the repository as provided: if all seven base tuple files compile with proofs of validity, and the profile-star definitions agree with Theorem 1, then the printed bounds are established; any missing proof, altered definition, or invalid tuple means the corresponding bound has not been shown. A direct spot-check is to extract the first coordinate of the $C_7$ chain's final profile and confirm that its $200$th root is at least $3.258805369885$.

Watch

Extended reading notes

Core claim

The central discovery is that the star-product of valid-tuple profiles, defined by an explicit four-coordinate formula, can be iterated to produce independent sets in high strong powers of odd cycles whose size grows faster than the $d$-th power of the base bound. For example, from a base tuple in $C_7^5$ with profile (367,8,367,322), repeated star-squaring reaches a profile in $C_7^{200}$ whose first coordinate has $200$-th root $3.258805369885\ldots$; analogous chains assert bounds for $C_{11}$ through $C_{23}$. These are not asymptotic estimates but explicit existence claims: each printed root is the $d$-th root of an actual independence number in a specific strong power, and the witnessing tuples are encoded as expl

Load-bearing premise

The entire chain rests on the seven base valid tuples being genuinely valid and on the star-product theorem being correctly formalised, but the paper lists only their four-number profiles and points to an unpinned Lean repository for the actual sets, maps, and proof certificate.

Editorial extensions

If this is right

For each cycle, the stated decimal is a genuine lower bound on Shannon capacity, not an approximation: an independent set of exactly that size exists in the specified strong power.
The seven bounds improve on the best previously known values, with gains ranging from about 1.6×10^-5 for C7 to 4.7×10^-3 for C11.
Because the Lovász theta upper bound is strictly larger in each case, the true capacities remain bracketed but unresolved, so the gap between these new lower bounds and the theta bound is now the remaining target.
The recipe is reusable: any valid tuple, combined with Theorem 1, immediately yields an explicit lower-bound chain for the host graph's Shannon capacity.
If the Lean formalisation is sound, these bounds do not rest on untrusted search code or sampling; they are backed by machine-checked certificates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the Lean certificate is reproducible, this sets a template for making computer-assisted capacity bounds machine-checkable, potentially eliminating the usual trust gap in large combinatorial searches.
The printed bounds are truncated decimals; recovering the exact first coordinates of the final profiles would yield slightly stronger explicit lower bounds than the digits shown.
The same profile-product induction likely applies beyond odd cycles: any finite graph admitting a valid tuple gets an explicit capacity lower bound, so the construction is a general-purpose gadget rather than a cycle-specific trick.
The gap between the new bounds and the Lovász theta function suggests the method has not yet reached its ceiling; optimizing the four profile coordinates of the base tuples could push the bounds closer to the theta values.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the seven numbers are credible, but this paper is a trailer — the actual certificates live in an unpinned GitHub repo, so you cannot verify the central claim from the text alone.

What's new: the authors take Gao's valid-tuple product construction, feed it with new base tuples found by LLM search, and iterate to get improved lower bounds for Θ(C7), Θ(C11), Θ(C13), Θ(C15), Θ(C19), Θ(C21), Θ(C23). The improvements over previous records are tiny — 1.6e-5 to 4.7e-3 — but they are real, and Table 1 is honest about that. The product theorem is imported from Gao without proof, which is acceptable if that paper holds up. The arithmetic in §3 is checkable; I spot-checked the exponent bookkeeping for C11 and C13, and the stated d-th roots are consistent with the profiles.

The soft spot is the evidential base. For each cycle, the paper prints only a four-coordinate profile, not the actual sets and maps that define the valid tuple. All data and proofs are said to be in the Lean formalisation at a URL, but no commit hash, no Lean/mathlib version, and no excerpt appear in the paper. So the claim 'fully formalised in Lean' is unpinned. If any base tuple is invalid, or if the formalised version of Theorem 1 misrepresents Gao's product rule, the bounds collapse while all printed arithmetic stays consistent. That is a verifiability gap, not an identified error, but it is load-bearing.

A second, minor issue: the paper says the tuples were found with ChatGPT and Claude, but gives no details on the search procedure. That doesn't undercut the result, but it does mean the discovery process isn't reproducible.

Who should read this: anyone working on Shannon capacities of odd cycles, and anyone interested in the combination of LLM search and formal proof. The paper is short and readable, and it doesn't oversell. It deserves a serious referee: the numbers are the best known, and the Lean claim is strong enough to check. I'd recommend sending it out, with the instruction that the referee should clone the repository, pin the commit, and run the build. If that passes, accept with minor copyedits; if not, the result stands unverified.

Referee Report

3 major / 4 minor

Summary. The paper gives new lower bounds on the Shannon capacity of seven small odd cycles, C7, C11, C13, C15, C19, C21, and C23, using an iterative product construction due to Gao [Gao26]. For each cycle, the authors exhibit a four-coordinate profile of a valid tuple in a small power, then repeatedly apply the star-product operation to obtain a profile in a large strong power; the d-th root of the first coordinate is a lower bound on the Shannon capacity. The bounds improve previously known values and are claimed to be fully formalised in Lean. The paper states that the base valid tuples, beyond their profiles, are recorded and verified in an accompanying Lean repository.

Significance. If the bounds and their formalisation are correct, this is a meaningful advance in a long-standing open problem: Shannon capacity of odd cycles has been open for all odd cycles length at least 7 since Lovász's determination of C5. The bounds are close to the Lovász theta upper bounds and improve on several prior constructions. The use of machine-checked proof assistants is a positive development for this area, and the paper's explicit disclosure that the tuples were found by LLM-guided search, with verification separated from search, is methodologically sound. The significance is tempered by the fact that the central certificate is not independently inspectable from the manuscript itself.

major comments (3)

[§3 and §4] The seven base valid tuples are not included in the manuscript; only their four-coordinate profiles are listed (e.g., π1=(367,8,367,322) for C7, π1=(62530,1014,62530,60502) for C13). The text says the tuples are 'recorded in the accompanying Lean formalisation', but the paper gives no commit hash, no Lean/mathlib version, and no code excerpts. Every one of the seven bounds reduces to the existence of these base tuples, so a reader cannot verify the central claim from the paper alone. Please pin the repository (commit hash, version) and provide the base tuple data as an appendix or ancillary file, or in the Lean files themselves with enough context to be checked.
[§2, Theorem 1] The star-product theorem is imported from [Gao26] without proof, and the manuscript does not state how this theorem is represented in the Lean formalisation. The iterative chains in §3 depend entirely on this theorem. If the formalisation imports Theorem 1 as an axiom rather than as a proved theorem, the certificate would not establish the bounds. Please clarify whether Theorem 1 is proved in the formalisation or imported from an existing formal proof, and give the corresponding Lean statement and its status.
[Abstract and Table 1] The numerical bounds are asserted as decimal truncations, e.g. 3.258805369885..., but the paper does not state the exact integer N and power d for each bound in a way that lets the reader reproduce the decimal digits. For example, the C7 bound comes from the first coordinate of π40 in C7^⊠200; the corresponding inequality is Θ(C7) ≥ N^(1/200). Please state explicitly, for each cycle, the exact integer N (or the exact profile) and the exponent d, and describe how the decimal truncations were computed and, if claimed, certified in Lean.

minor comments (4)

[§3, C11 chain] The exponent bookkeeping for C11 works out (3→6→9→12→21→24→42→45→87→174), but it would be clearer to display the exponents at each step as is done for C13.
[§2, Example 1] The example for C5 is helpful, but it would be even more useful to show explicitly how the profile formula (a1−b1)(a2−b2)+c1b2+b1c2 evaluates for π⋆π.
[Table 1] The 'new bound' column rounds to 8 decimal places while the abstract and body give more digits; a note that the table entries are truncated to 8 decimals would avoid apparent inconsistency.
[References] The reference [dBBZ26] is dated 2026 but the arXiv identifier is 2404.16763; if this is a revised or republished version, please clarify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bounds are derived from externally stated product theorem and independently checked base tuples; the only self-citation is contextual.

full rationale

The claimed bounds are derived by starting with base valid tuples for fixed powers of odd cycles, applying Gao's star-product theorem to obtain profiles for larger strong powers, and taking roots of the first coordinate. The first coordinate is |I| for a valid tuple, so each bound is a logical consequence of tuple existence and the product theorem. The base tuples are not defined in terms of the target bound; they are combinatorial witnesses whose validity is (claimed to be) verified in Lean. The product theorem is imported from [Gao26], an external work by different authors; no uniqueness theorem or ansatz is smuggled in from self-citations. The only self-citation, [dBBZ26], is contextual (a previous C15 bound) and is not load-bearing for the new results. LLM-based search is disclosed as search-then-verify, not as a fitted parameter, and the verification is independent of the bound being optimized. The absence of a commit hash or Lean/mathlib version is a reproducibility/verifiability gap, not circularity. Therefore no specific reduction of a prediction to its inputs by construction was found.

Assumptions & free parameters 7 free parameters · 2 assumptions · 0 invented entities

The ledger is small because the central claim is a finite computation. The seven base profiles are listed as free parameters: they are search-discovered inputs that set the strength of each bound, though their validity is machine-checked (per §4). The iteration lengths are also search choices but do not affect validity. The load-bearing axioms are Theorem 1 from [Gao26], imported without proof, and trust in the Lean kernel/mathlib, which is not version-pinned. No invented entities.

free parameters (7)

Base profile π1 for C7 (in C7^⊠5) = (367, 8, 367, 322)
Search-found valid tuple; the C7 bound is derived from it by ⋆-iteration; validity claimed checked in Lean.
Base profile π1 for C11 (in C11^⊠3) = (148, 3, 148, 142)
Search-found valid tuple; the C11 bound is derived from it by ⋆-iteration; the size-148 independent set is classical [BMR+71].
Base profile π1 for C13 (in C13^⊠6) = (62530, 1014, 62530, 60502)
Search-found valid tuple; the C13 bound is derived from it by ⋆-iteration; validity claimed checked in Lean.
Base profile π1 for C15 (in C15^⊠4) = (2842, 3, 2842, 2833)
Search-found valid tuple; the C15 bound is derived from it by ⋆-iteration; the ⁴√2842 bound appeared in [dBBZ26].
Base profile π1 for C19 (in C19^⊠4) = (7666, 2, 7666, 7661)
Search-found valid tuple; the C19 bound is derived from it by ⋆-iteration; validity claimed checked in Lean.
Base profile π1 for C21 (in C21^⊠4) = (11441, 10, 11441, 11398)
Search-found valid tuple; the C21 bound is derived from it by ⋆-iteration; validity claimed checked in Lean.
Base profile π1 for C23 (in C23^⊠4) = (16466, 30, 16466, 16323)
Search-found valid tuple; the C23 bound is derived from it by ⋆-iteration; validity claimed checked in Lean.

assumptions (2)

domain assumption Theorem 1 (Gao's product theorem): valid tuples for G and H compose to a valid tuple for G ⊠ H with Π(τ⋆τ') = Π(τ)⋆Π(τ')
Stated in §2 and attributed to [Gao26] without proof; every bound in §3 cascades from it. If the composition rule or the profile formula is incorrect, all seven bounds fail.
standard math Soundness of the Lean kernel and mathlib tactics used in §4
The 'fully formalised in Lean' claim presumes the proof assistant is sound and that the formalized statements match the prose recipes; no Lean/mathlib version or commit hash is pinned.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Lean-verified lower bounds for the Shannon capacity of odd cycles." pith.science (2026). https://pith.science/paper/TJPUHTZO

@misc{pith2026260729681,
  author       = {Pith},
  title        = {Pith review of: Lean-verified lower bounds for the Shannon capacity of odd cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TJPUHTZO}},
  note         = {Machine review of arXiv:2607.29681}
}

abstract

We give new lower bounds for the Shannon capacities of small odd cycles: $\Theta(C_7)\geq3.258805369885\ldots$, $\Theta(C_{11})\geq5.294502522149\ldots$, $\Theta(C_{13})\geq6.302455083464\ldots$, $\Theta(C_{15})\geq7.301600534487\ldots$, $\Theta(C_{19})\geq9.357192705918\ldots$, $\Theta(C_{21})\geq10.342455853338\ldots$, and $\Theta(C_{23})\geq11.328224257774\ldots$. The bounds are obtained by an iterative procedure due to Gao (2026) which is based on a method by Itty, Rosin, Carstensen and Reichman (2026). The bounds are fully formalised in Lean.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 1 linked inside Pith

[1]

Lov\'. On the. IEEE Trans. Inform. Theory , FJOURNAL =. 1979 , NUMBER =

1979
[2]

, TITLE =

Shannon, Claude E. , TITLE =. Institute of Radio Engineers Transactions on Information Theory , FJOURNAL =. 1956 , NUMBER =

1956
[3]

and Schrijver, Alexander , TITLE =

Polak, Sven C. and Schrijver, Alexander , TITLE =. Inform. Process. Lett. , FJOURNAL =. 2019 , PAGES =

2019
[4]

Improved lower bound on the

Vesel, Aleksander and. Improved lower bound on the. Inform. Process. Lett. , FJOURNAL =. 2002 , NUMBER =

2002
[5]

Ashik and \"

Mathew, K. Ashik and \". New lower bounds for the. Des. Codes Cryptogr. , FJOURNAL =. 2017 , NUMBER =

2017
[6]

Baumert, L. D. and McEliece, R. J. and Rodemich, Eugene and Rumsey, Jr., Howard C. and Stanley, Richard and Taylor, Herbert , TITLE =. Computers in algebra and number theory (. 1971 , MRCLASS =

1971
[7]

Electron

Bohman, Tom and Holzman, Ron and Natarajan, Venkatesh , TITLE =. Electron. J. Combin. , FJOURNAL =. 2013 , NUMBER =

2013
[8]

The asymptotic spectrum distance, graph limits, and the

David de Boer and Pjotr Buys and Jeroen Zuiddam , year=. The asymptotic spectrum distance, graph limits, and the. 2404.16763 , archivePrefix=

arXiv

Show all 14 references

[9]

2026 , eprint=

Improved lower bounds for the Shannon capacity of odd cycles , author=. 2026 , eprint=

2026
[10]

A Recursive Construction Improving the Lower Bound on the

Yu Gao , year=. A Recursive Construction Improving the Lower Bound on the. 2607.27869 , archivePrefix=

arXiv
[11]

The Lean 4 Theorem Prover and Programming Language , booktitle =

Leonardo de Moura and Sebastian Ullrich , editor =. The Lean 4 Theorem Prover and Programming Language , booktitle =. 2021 , doi =

2021
[12]

2019 , eprint=

The Lean mathematical library , author=. 2019 , eprint=

2019
[13]

Mathematical discoveries from program search with large language models , journal =

Bernardino Romera. Mathematical discoveries from program search with large language models , journal =. 2024 , doi =

2024
[14]

Ars Combin

Codenotti, Bruno and Gerace, Ivan and Resta, Giovanni , TITLE =. Ars Combin. , FJOURNAL =. 2003 , PAGES =

2003

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Lov\'. On the. IEEE Trans. Inform. Theory , FJOURNAL =. 1979 , NUMBER =

1979

[2] [2]

, TITLE =

Shannon, Claude E. , TITLE =. Institute of Radio Engineers Transactions on Information Theory , FJOURNAL =. 1956 , NUMBER =

1956

[3] [3]

and Schrijver, Alexander , TITLE =

Polak, Sven C. and Schrijver, Alexander , TITLE =. Inform. Process. Lett. , FJOURNAL =. 2019 , PAGES =

2019

[4] [4]

Improved lower bound on the

Vesel, Aleksander and. Improved lower bound on the. Inform. Process. Lett. , FJOURNAL =. 2002 , NUMBER =

2002

[5] [5]

Ashik and \"

Mathew, K. Ashik and \". New lower bounds for the. Des. Codes Cryptogr. , FJOURNAL =. 2017 , NUMBER =

2017

[6] [6]

Baumert, L. D. and McEliece, R. J. and Rodemich, Eugene and Rumsey, Jr., Howard C. and Stanley, Richard and Taylor, Herbert , TITLE =. Computers in algebra and number theory (. 1971 , MRCLASS =

1971

[7] [7]

Electron

Bohman, Tom and Holzman, Ron and Natarajan, Venkatesh , TITLE =. Electron. J. Combin. , FJOURNAL =. 2013 , NUMBER =

2013

[8] [8]

The asymptotic spectrum distance, graph limits, and the

David de Boer and Pjotr Buys and Jeroen Zuiddam , year=. The asymptotic spectrum distance, graph limits, and the. 2404.16763 , archivePrefix=

arXiv