REVIEW 3 major objections 4 minor 1 cited by
Improved lower bounds for the Shannon capacity of odd cycles
T0 review · 3 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read Explicit constructions improve lower bounds on Shannon capacity for four odd cycles.
desk verdict Genuine, explicit improvements to the known lower bounds for C7, C11, C13, C15 — most notably C13 — but the paper should ship a verifier and the external base sets before the tiny C7/C15 margins are credible. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key object is an independent set in the d-th strong product C_n^d: a collection of d-vectors over Z_n such that any two distinct vectors differ by more than 1, in the circular metric, in at least one coordinate. The ratio α(C_n^d)^(1/d) lower-bounds Shannon capacity. The constructions work by taking a known dense independent set in a smaller product and inflating it into a larger product—using cross products, glued blocks, linear lifts, and substitution rules—so that the added vectors stay non-adjacent to the core and to each other. The named ingredients are the explicit sets B, X, PH, PV, S, R, T_i, and the W0/W1 substitution tables; these encode the local repair choices that make the l
What would settle it
Run a direct check on the 134,753 ten-vectors for C7: if any two distinct vectors differ by at most 1, circularly, in all ten coordinates, the C7 bound collapses. Similarly, rerun the C15 construction using the stated base set and the W0/W1 rules, then check all 8,076,974 eight-vectors; a single violating pair would falsify that bound.
Extended reading notes
Core claim
The central claim is Theorem 1: the Shannon capacity lower bounds for C7, C11, C13, and C15 improve to the values above. The proof is the existence of explicit independent sets in the stated strong products. The paper describes how each set is built from a known base set: for C7, a 367-vector set in C7^5 is turned into a 134,753-vector set in C7^10 via a cross product plus glued blocks; for C11, a 148-vector set in C11^3 is extended to a 21,909-vector set in C11^6; for C13, a 370-vector independent set in an auxiliary graph over Z13^4 is lifted by a linear map to 62,530 vectors in C13^6; and for C15, a 2,842-vector set in C15^4 is expanded with case-by-case substitutions into 8,076,974 vecto
Load-bearing premise
The load-bearing premise is that the listed vectors really are independent sets in the strong products—especially that the C15 W0/W1 substitution rules are implemented exactly as intended on the base set taken from another publication.
Editorial extensions
If this is right
- If the sets are correct, the new lower bounds Θ(C7) ≥ 134753^(1/10) > 3.258020, Θ(C11) ≥ 21909^(1/6) > 5.289773, Θ(C13) ≥ 62530^(1/6) > 6.300109, and Θ(C15) ≥ 8076974^(1/8) > 7.301399 each become the best known for these graphs.
- The improved independence numbers for intermediate products, such as α(C11^4) ≥ 766, α(C7^6) ≥ 1120, and α(C15^3) ≥ 383, can be composed with other sets to push capacity bounds still higher.
- Because the constructions are fully explicit, the lower bounds are checkable without any search: a direct pairwise-adjacency test on the listed vectors is enough to certify them.
- The pattern of augmenting a strong base set with carefully chosen replacement vectors may transfer to other odd cycles, potentially improving their Shannon capacity bounds as well.
- The paper's reported use of a large language model to discover these sets suggests that explicit combinatorial search can be guided by a model that reasons about existing constructions, not just by brute-force local search.
Reading between the lines
- A natural extension is to apply the same augmentation template to C9, C17, or to the next product dimension for these four cycles; the paper's 'small repair' pattern seems likely to generalize, though no claim of that kind is made in the paper.
- Because the C7 and C15 constructions depend on base sets reproduced in earlier publications, an independent verifier must first locate those base sets; reproducing the W0/W1 substitution procedure on them would settle whether the 8,076,974-vector set is exactly as described.
- The authors report that their own search heuristics, including simulated annealing, did not reach these sets, while the language-model interaction did. If this replicates, it shifts the practical bottleneck in this area from generating candidates to verifying them.
- The independence-number improvements for C11^4, C13^4, C7^6, and C15^3 are not yet tied to capacity records; combining them with each other or with new sets could yield further capacity gains even if no individual new product is dense enough on its own.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims improved lower bounds on the Shannon capacity of C7, C11, C13, and C15 by explicitly constructing independent sets in strong products: 134753 vectors in C7^10, 21909 in C11^6, 62530 in C13^6, and 8076974 in C15^8. The corresponding bounds are Θ(C7)>3.258020, Θ(C11)>5.289773, Θ(C13)>6.300109, and Θ(C15)>7.301399. The constructions are described in Section 3, partly through explicit formulas and partly relative to previously published base sets from [12] and [6]. The paper also reports improved independence numbers for several other products in Appendix B. The authors state that the constructions were verified computationally, but no verifier code, certificate, or exhaustive check log is included in the manuscript; a GitHub repository is cited instead. The mathematical claim is a finite existence claim, and the reported lower bounds follow immediately from the existence of the listed sets. The main weakness is that the central claim is not independently checkable from the text alone.
Significance. If the constructions are correct, the paper provides the best known lower bounds for the Shannon capacity of these four odd cycles, with the C13 improvement being the most substantial. The C13 construction is particularly elegant: it uses a linear map from Z_13^6 to Z_13^4 and a 370-vertex independent set in an auxiliary graph, giving a clean conceptual reduction. The reported bounds are modest but genuine, and the method of using an LLM to discover explicit combinatorial constructions is noteworthy, though it does not substitute for mathematical verification. The paper uses no fitted parameters for the lower bounds and compares against independent published bounds, so there is no circularity in the numerical claims. The central limitation is reproducibility: the existence of the independent sets is asserted on the basis of an unreported computational check.
major comments (3)
- [§3.1–§3.4, Theorem 1] The central claim is the existence of the four independent sets, but the only evidence is the sentence 'We verified that the vertices ... constitute an independent set.' No verifier program, certificate, or exhaustive-check log is provided. The GitHub link is not a substitute in the submitted manuscript. For a finite existential claim of this kind, a journal proof should supply a machine-checkable certificate or exact verification code. Without it, a reader cannot distinguish a correct construction from one with a single hidden adjacency. This is load-bearing because each capacity bound follows only from the existence of the exact finite set.
- [§3.1, §3.2, §3.4 (cardinality arithmetic)] The reported sizes assume that the unioned parts are disjoint and duplicate-free. In §3.1, |I| is computed as 359^2 + 16·367 = 134753, but this counts (B×B) ∪ {(h_j(x),x)} ∪ {(x,v_j(x))} correctly only if the three parts are pairwise disjoint and the augmented vectors are all distinct. In §3.4, the count 8054244 + 2·11365 = 8076974 similarly assumes that the W0 and W1 additions are disjoint from B×B and from each other. In §3.2, the count assumes that F_A, F_B, F_C are disjoint subsets of X and that G_A, G_B, G_C are disjoint subsets of Y with the stated sizes. No proof or certificate of distinctness is supplied. The authors should provide a short argument or a machine-verifiable certificate that the final sets have exactly the claimed cardinalities.
- [§3.1 and §3.4 (external base sets)] The constructions for C7 and C15 are not self-contained. In §3.1, R is 'the explicit size-367 set of 5-vectors as given in the Appendix of [12]'; in §3.4, R0 is 'the explicit size-2842 set of 4-vectors as given in Appendix B of [6]'. Neither set is reproduced. All subsequent operations (B, X0, X, T_i, the W0/W1 rules, and the final verification) are defined relative to these external data. Consequently, a reader cannot regenerate the claimed independent sets from the text alone. The authors should reproduce the base sets in an appendix or supply a verifier that reads them from a permanent repository and confirms the final sets' independence and cardinalities.
minor comments (4)
- [Table 1] The improvement for C15 is extremely small: 8076974^{1/8} > 7.301399 versus the previous 2842^{1/4} > 7.301397. This is not a defect, but the authors may wish to explicitly state the margin so readers are not surprised by the tiny gain.
- [§3.1, §3.2] The symbol R is used for different base sets in the C7 and C11 constructions, and again in the C15 discussion. This is confusing; a different name for each would improve readability.
- [Data and Code Availability] The GitHub repository link should include a versioned commit or a checksum for the constructed sets, so that the exact files used for the claims can be identified in the future.
- [Appendix B, Table 5] The additional independence-number improvements are stated without the same level of construction detail or verification. If these claims are part of the contribution, they should be backed by the same kind of explicit listing or verifier as the main constructions.
Circularity Check
No significant circularity: the claimed lower bounds are direct consequences of explicitly constructed independent sets, with no parameter fitted to the target values and no load-bearing self-citation.
full rationale
Each lower bound in Theorem 1 follows immediately from an asserted independent set of a stated cardinality: e.g., for C7, 134753 = 359*359 + 8*367 + 8*367, and the paper claims the resulting 10-vectors are independent in C7^10. The target bound is not used as an input to the construction; it is a consequence of the claimed set size. The constructions use prior independent sets ([12], [2], [6]) as base objects, but these are external benchmarks, not hidden restatements of the target lower bounds. The only self-citation, [14] by co-author Rosin, is used as a comparison of search heuristics and is not load-bearing for Theorem 1. The paper's main weakness is that the independence verification is asserted rather than fully reproducible from the manuscript, but that is a verifiability or correctness issue, not circularity. No equation or construction step reduces to the quantity being predicted, so the circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Base independent set R of size 367 in C7^5 exists (from [12]).
- domain assumption Base independent set R0 of size 2842 in C15^4 exists (from [6]).
- ad hoc to paper The authors' computational verification of the constructed sets is exhaustive and correct.
Cite this review
Pith. "Pith review of Improved lower bounds for the Shannon capacity of odd cycles." pith.science (2026). https://pith.science/paper/5PBE3VCG
@misc{pith2026260721517,
author = {Pith},
title = {Pith review of: Improved lower bounds for the Shannon capacity of odd cycles},
year = {2026},
howpublished = {\url{https://pith.science/paper/5PBE3VCG}},
note = {Machine review of arXiv:2607.21517}
}
abstract
The Shannon capacity $\Theta(G)$ of a graph $G$ quantifies the maximum rate at which information can be transmitted with zero error over a noisy channel. It is lower bounded by $\alpha(G^d)^{1/d}$ for any $d$, where $\alpha(G^d)$ is the independence number of the $d$-th strong product of $G$. We construct independent sets of size $134753$ in $C_7^{10}$, $21909$ in $C_{11}^{6}$, $62530$ in $C_{13}^{6}$, and $8076974$ in $C_{15}^{8}$, improving the best known lower bounds for the Shannon capacity of these graphs to $\Theta(C_7)\geq 134753^{1/10}>3.258020$, $\Theta(C_{11})\geq 21909^{1/6}>5.289773$, $\Theta(C_{13})\geq 62530^{1/6}>6.300109$, and $\Theta(C_{15})\geq 8076974^{1/8}>7.301399$. We also improve the best known lower bounds on the independence numbers of several individual strong products of odd cycles that do not improve the Shannon capacity lower bound. The constructions were discovered through iterative interactions with a Large Language Model (LLM), illustrating the potential of LLMs for finding explicit combinatorial constructions.
Forward citations
Cited by 1 Pith paper
-
A Recursive Construction Improving the Lower Bound on the Shannon Capacity of $C_7$
The Shannon capacity of C7 is at least 3.2587891539, via an explicit independent set of size M40 in C7^200 built by a recursively optimized gadget product.
Reference graph
Works this paper leans on
-
[14]
Christopher D Rosin. Using reasoning models to generate search heuristics that solve open instances of combinatorial design problems.arXiv preprint arXiv:2505.23881, 2025
arXiv 2025
-
[12]
New lower bound on the Shannon capacity of C7 from circular graphs.Information Processing Letters, 143:37– 40, 2019
Sven C Polak and Alexander Schrijver. New lower bound on the Shannon capacity of C7 from circular graphs.Information Processing Letters, 143:37– 40, 2019
2019
-
[6]
David de Boer, Pjotr Buys, and Jeroen Zuiddam. The asymptotic spec- trum distance, graph limits, and the Shannon capacity.arXiv preprint arXiv:2404.16763, 2024
arXiv 2024
-
[1]
The Shannon capacity of a graph and the independence numbers of its powers.IEEE Transactions on Information Theory, 52(5):2172–2176, 2006
Noga Alon and Eyal Lubetzky. The Shannon capacity of a graph and the independence numbers of its powers.IEEE Transactions on Information Theory, 52(5):2172–2176, 2006
2006
-
[2]
A combinatorial packing problem
Leonard D Baumert, Robert J McEliece, Eugene Rodemich, H Rumsey, Richard Stanley, and Herbert Taylor. A combinatorial packing problem. Computers in algebra and number theory, 4:97–108, 1971
1971
-
[3]
A limit theorem for the Shannon capacities of odd cycles I.Proceedings of the American Mathematical Society, 131(11):3559–3569, 2003
Tom Bohman. A limit theorem for the Shannon capacities of odd cycles I.Proceedings of the American Mathematical Society, 131(11):3559–3569, 2003
2003
-
[4]
On the inde- pendence numbers of the cubes of odd cycles.The Electronic Journal of Combinatorics, page P10, 2013
Tom Bohman, Ron Holzman, and Venkatesh Natarajan. On the inde- pendence numbers of the cubes of odd cycles.The Electronic Journal of Combinatorics, page P10, 2013
2013
-
[5]
Some remarks on the Shannon capacity of odd cycles.Ars Combinatoria, 66:243–258, 2003
Bruno Codenotti, Ivan Gerace, Giovanni Resta, et al. Some remarks on the Shannon capacity of odd cycles.Ars Combinatoria, 66:243–258, 2003
2003
Show all 17 references
-
[7]
Linear Shannon capacity of Cayley graphs
Venkatesan Guruswami and Andrii Riazanov. Linear Shannon capacity of Cayley graphs. In2021 IEEE International Symposium on Information Theory (ISIT), pages 988–992. IEEE, 2021
2021
-
[8]
Cliqueishardtoapproximatewithin n1−ε.Acta Mathematica, 182(1):105–142, 1999
JohanHåstad. Cliqueishardtoapproximatewithin n1−ε.Acta Mathematica, 182(1):105–142, 1999
1999
-
[9]
Advances in the Shannon capacity of graphs
Nitay Lavi and Igal Sason. Advances in the Shannon capacity of graphs. arXiv preprint arXiv:2509.24600, 2025
2025
-
[10]
On the Shannon capacity of a graph.IEEE Transactions on Information theory, 25(1):1–7, 1979
László Lovász. On the Shannon capacity of a graph.IEEE Transactions on Information theory, 25(1):1–7, 1979
1979
-
[11]
New lower bounds for the Shannon capacity of odd cycles.Designs, Codes and Cryptography, 84(1):13– 22, 2017
K Ashik Mathew and Patric RJ Östergård. New lower bounds for the Shannon capacity of odd cycles.Designs, Codes and Cryptography, 84(1):13– 22, 2017. 9
2017
-
[13]
Mathemati- cal discoveries from program search with large language models.Nature, 625(7995):468–475, 2024
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathemati- cal discoveries from program search with large language models.Nature, 625(799...
2024
-
[15]
The zero error capacity of a noisy channel.IRE Transac- tions on Information Theory, 2(3):8–19, 1956
Claude Shannon. The zero error capacity of a noisy channel.IRE Transac- tions on Information Theory, 2(3):8–19, 1956
1956
-
[16]
Improved lower bound on the Shannon capacity of C7.Information processing letters, 81(5):277–282, 2002
Aleksander Vesel and Janez Žerovnik. Improved lower bound on the Shannon capacity of C7.Information processing letters, 81(5):277–282, 2002
2002
-
[17]
Cycle Code
Yi Zhai, Zhiqiang Wei, Ruohan Li, Keyu Pan, Shuo Liu, Lu Zhang, Jian- min Ji, Wuyang Zhang, Yu Zhang, and Yanyong Zhang. X-Evolve: So- lution space evolution powered by large language models.arXiv preprint arXiv:2508.07932, 2025. 10 A ChatGPT Interactions Each search centered ...
2025 arXiv
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.