A Recursive Construction Improving the Lower Bound on the Shannon Capacity of $C_7$

Yu Gao

REVIEW 1 major objections 5 minor 1 cited by

A Recursive Construction Improving the Lower Bound on the Shannon Capacity of $C_7$

T0 review · 1 major / 5 minor · reviewed 2026-07-31 · deepseek-v4-flash

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

Pith's one-line read This paper constructs an explicit independent set in C7^200 and proves the Shannon capacity of C7 is at least 3.2587891539.

desk verdict A genuine but tiny improvement to the Shannon capacity lower bound of C7, built on a clean recursive product lemma; the only real fragility is the machine-checked base gadget, which is a reasonable but checkable dependency. read the letter →

arxiv 2607.27869 v1 pith:3S5H3OGY submitted 2026-07-30 math.CO cs.ITmath.IT

Yu Gao This is my paper

classification math.COcs.ITmath.IT MSC 05C6905C7694A24

keywords ShannoncapacityC7oddcycleindependentsetstrongproductgadgetlowerboundexactcomputation

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

This paper improves the known lower bound on the Shannon capacity of the seven-cycle, one of the simplest graphs whose capacity is still not exactly known. It repackages the known 367-point independent set in the fifth strong power of C7 into a reusable structural object—a gadget—and proves a product lemma that combines gadgets of different dimensions while preserving independence. Iterating that lemma along a carefully chosen split tree yields an explicit independent set in the 200th strong power with size a specific 103-digit integer, giving the root lower bound 3.2587891539. An accompanying program checks the finite base assertions and performs the exact integer recursion.

What carries the argument

The engine is the gadget and its product lemma. A gadget packages an independent set I, t private pairs (r_i,q_i) with disjoint endpoints, two independent complementary transversals P_H and P_V, and an auxiliary independent set X satisfying X ∩ N(P_H) ∩ N(P_V) = ∅. Lemma 4 combines two gadgets into a larger gadget, propagating the six parameters (a,t,s,o,h,v) through formulas (6)–(11). Iterating this product lemma over a split tree of five-dimensional blocks produces the 200-dimensional independent set.

What would settle it

Independently recompute the five finite assertions for the base gadget in C7^5: check that I0 and X have size 367 and are independent, that N({q_j})∩I0={r_j} for all eight j, that P_H and P_V are independent, and that exactly 321, 26, and 20 points of X are confusable with neither, only one, or only the other transversal. If any count differs, or if any two points in the recursively generated C7^200 set are adjacent, the lower bound collapses.

Watch

Extended reading notes

Core claim

The central discovery is that the known 367-point independent set in C7^5 can be seen as a gadget: an independent code set equipped with eight private pairs, two independent complementary transversals, and an auxiliary set whose points are confusable with at most one transversal. The product lemma shows that two such gadgets, possibly of different dimensions, combine into a new gadget whose independent set has size (a1−t1)(a2−t2)+t1s2+s1t2 and whose other six parameters update by explicit polynomial formulas. Applying this lemma along the split tree 1+1=2, 1+2=3, 2+3=5, 5+5=10, 10+10=20, 20+20=40 yields an explicitly specified independent set in C7^200 of size M40, so Θ(C7) ≥ M40^(1/200) = 3

Load-bearing premise

The entire bound rests on the finite counts of one five-dimensional base gadget—that the listed 367-point code, its eight private pairs, the two transversals, and the 367-point auxiliary set behave exactly as the verification program reports.

Editorial extensions

If this is right

The lower bound for the Shannon capacity of C7 becomes 3.2587891539…, a strict improvement over the previous 3.2580207 from the ten-dimensional construction.
The 200-dimensional independent set is explicit and generated by a short recursion, not merely proved to exist.
The product lemma handles gadgets of different dimensions, so the construction does not require identical factors.
The exact integer computation verifies that the displayed split tree is optimal at every node up to forty blocks: no other split gives a larger M_k in the recurrence.
Repeatedly combining identical copies—either from the base gadget or from the 200-dimensional gadget—converges to a smaller root bound, so the optimized split tree is essential to the gain.
The balanced-product limit is 3.2586163…, below the theorem's bound, confirming that the 40-block split tree matters.

Reading between the lines

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

Editorial extension: because the product lemma's formulas are polynomial in the base gadget's parameters, any future improvement to the five-dimensional base counts would immediately propagate to higher-dimensional bounds through the same recursion.
Editorial extension: the paper's own comparison with balanced products suggests that the auxiliary-set overlap counts (o,h,v) are as important as the code size a; searching for base gadgets with larger o relative to s could slow the growth of the private-pair count t.
Editorial extension: the split tree stops at forty blocks, but the dynamic-programming recurrence (15) could be run much deeper with exact arithmetic to see whether the root bound continues to climb.
Editorial extension: the gadget/product-lemma pattern is not specific to C7; analogous private-pair structures for other odd cycles could yield new lower bounds if suitable base gadgets are found.

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

Colleague — quick read for you. The headline result is real: a new lower bound 3.258789... on Θ(C7), improving the previous 3.2580207. The improvement is numerically tiny, and still far from Lovász's upper bound, but the recursive product lemma (Lemma 4) is the actual contribution. It lets you combine gadgets of different dimensions while preserving a six-parameter invariant, and that is a method the subfield can reuse. The paper is also honest: it reproduces the Itty–Rosin–Carstensen–Reichman 134753-set (Remark 6) before extending it, and it reports negative results about balanced products not beating the main bound.

The math skeleton I checked is sound. The algebra of the invariant (δ12 = δ1δ2), the t-recurrence, and the exact integer DP for M40 all check out. The 200-dimensional set is explicitly constructed from 40 five-dimensional blocks; no fitted parameters, no circularity. The verification program is pinned to a commit, reads the base set from a file, and does exact integer arithmetic. That is creditable.

The soft spot is exactly where the reader's conditional verdict points: Proposition 5. The five finite facts about the base gadget — independence of I0 and X, the eight private-pair equations, the transversals, and the counts (321,26,20) — are not proven in the text; the proof is 'each assertion is a finite check,' delegated to the Python program. Everything else, including the recursion and the root bound, is an algebraic consequence of those counts. If the program has a bug in the adjacency predicate or the parse of R367.txt, or if R367.txt transcribes the Polak–Schrijver set incorrectly, Theorem 1 falls. That is a real but standard risk in computer-assisted combinatorics; the base set is external and published, and the program is pinned, so independent execution is feasible. I would call this a moderate caveat, not a deficiency: the paper tells you exactly what to check and provides the code.

Who this is for: people working on Shannon capacity of odd cycles, and anyone interested in recursive product constructions for independent sets in strong powers. It deserves a serious referee — the method is new, the claims are precise, and the computational part is reproducible. I'd send it out, asking a referee to run the verification independently.

Referee Report

1 major / 5 minor

Summary. The paper presents a recursive construction of independent sets in strong powers of C7. It defines a 'gadget' as an independent set (code) equipped with private pairs, two complementary independent transversals, and an auxiliary independent set with no point confusable with both transversals. A product lemma (Lemma 4) combines two gadgets into a new gadget, with explicit formulas for the size, private-pair count, and the auxiliary-set parameters (Eqs. (6)-(11)). Starting from the Polak-Schrijver 367-vertex independent set in C7^5 with eight private pairs, the author builds a chain of gadgets corresponding to the split tree 1+1=2, 1+2=3, 2+3=5, 5+5=10, 10+10=20, 20+20=40, and obtains an independent set of cardinality M40 in C7^200. This yields the lower bound Theta(C7) >= M40^{1/200} = 3.2587891539086910161967650155..., improving the previous bound 3.2580207 of Itty et al. The paper also analyzes two balanced-product strategies and argues that they do not improve the main bound.

Significance. If the theorem is correct, this is a genuine improvement of a long-studied lower bound for the Shannon capacity of C7. The method is conceptually clean: the product lemma isolates an invariant that makes the recursion close, and the final result is an exact integer computation with no fitted parameters. The paper reproduces the previous 134753-set as a special case, which lends credibility to the framework. The main strength is the explicit, checkable nature of the construction: the formulas (6)-(11) and (14)-(15) are derived symbolically, and the finite computational part is clearly separated. The principal weakness is that the base finite assertions (Proposition 5) are delegated to an external program and input file, rather than being proved or fully documented in the manuscript.

major comments (1)

[§4, Proposition 5; §7] The theorem's numerical conclusion rests entirely on the five finite assertions in Proposition 5: independence of I0 and X, the eight private-pair equations N({q_j})∩I0={r_j}, independence of PH and PV, and the counts (o,h,v)=(321,26,20) for the auxiliary set X. These are not proved in the text; the proof says 'Each assertion is a finite check', and the checker is an external Python program reading inputs/R367.txt from a GitHub commit. Thus the paper as submitted is not self-contained: a reader cannot verify the base gadget without downloading and trusting an external repository. Because this is the load-bearing step, please include the verification program and R367.txt as supplementary material (or an appendix), and describe in the paper the adjacency predicate, the automorphism T, and the one-point swap so the check can be independently re-implemented. The algebraic skeleton (Lemma 4,

minor comments (5)

[§2, Definition 2] The definition of 'confusable' appears at the start of §2, but Definition 2 uses it before the formal definition; please reorder or add a forward reference.
[§4, table] The table of the eight pairs (r_j,q_j) is poorly formatted in the submitted PDF. Please ensure the columns align so the correspondence j ↦ (r_j,q_j) is unambiguous.
[§5, Proposition 8] The induction statement in Proposition 8 refers only to the parameters s, o, and t, but Lemma 4 carries the full six-tuple (a,t,s,o,h,v). The proof is valid because the omitted h and v are produced by the lemma, but the statement should say explicitly that the gadget is full (with some h,v) so that the induction is transparent.
[§6, Eqs. (16)-(18)] The claims about balanced products not improving the bound rely on numerical evaluations such as \tilde eU0 = 1.058302615128940076... and \tilde\rho_1 = 3.258770378400339734..., which are asserted from 'exact integer arithmetic' without showing the exact integers or a rigorous interval bound. Please provide exact integer inequalities or verification details for these auxiliary claims.
[§7] For reproducibility, please include a cryptographic hash of inputs/R367.txt and of the verification program, and list any non-standard Python dependencies. This will make the fixed commit b13031ba76e3 easier to audit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the recursive lower bound is derived by exact algebra from an externally published base gadget, with all finite checks and integer recurrences explicitly stated and verified.

full rationale

The claimed lower bound is not equivalent to its inputs by construction. The base gadget is the published Polak-Schrijver independent set of size 367 in C_7^5; the eight private pairs, transversals, the automorphism T, and the one-point swap in Section 4 are explicitly listed and then verified in Proposition 5 by finite checks. Those parameters are not fitted to the final integer M40: the recurrence (15) and formulas (7)-(11), (14) are algebraic consequences of the gadget definition, and M40 is computed by exact integer dynamic programming over all splits. The reproduction of Itty et al.'s 134753-set (Remark 6) is used only as a consistency benchmark of Lemma 4, not as the new result. The only load-bearing dependency is the correctness of the verification program and the input file R367.txt; that is a computational-reproducibility risk, not circularity, because the target conclusion is not assumed as an input. No self-citation carries a mathematical assumption: references [1] and [2] are external, and the author's own code citation [4] is a reproducibility artifact rather than an unverified theorem. Section 6 also checks by exact arithmetic that balanced products do not improve Theorem 1, rather than assuming it. Thus the derivation is self-contained modulo an explicit, externally based finite verification.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

One external datum (the Polak–Schrijver 367-point set), one hand-chosen point swap in the auxiliary set, and then exact integer propagation; no fitting to a target value and no invented structures. The private pairs and the J0/J1 transversal split are construction data inherited from [1], not fresh fits. The dominant epistemic load is carried by the machine checks: the exhaustive base-gadget verification and the DP optimality scan, both inside the same program that I did not execute for this review.

free parameters (1)

one-point swap in auxiliary set X_0 = remove (2,4,6,3,5); add (1,5,6,3,5)
Section 4: X = T(I0) minus one point plus one point. The gadget profile (o,h,v) = (321,26,20) — hence the propagation base s1=367 and δ1 = 2·321−367 = 275 — depends on this hand-chosen edit. All recursive counts s_k, o_k, t_k and M40 derive from these values.

assumptions (4)

domain assumption The input file R367.txt faithfully encodes a genuine 367-point independent set in C7^5 (the Polak–Schrijver set).
Section 4/7: I0 is read from inputs/R367.txt; the whole recursion is anchored to this 367-point code, whose coordinates are not printed in the text.
domain assumption The shipped Python checker correctly and exhaustively verifies Proposition 5's five finite assertions.
Section 7: the program checks independence of I0 and X, the eight private-neighbor conditions, transversality, and the (o,h,v) counts; its correctness is assumed and was not independently executed for this review.
domain assumption The dynamic program that enumerates every split k = i+(k−i) for 2 ≤ k ≤ 40 implements exact integer arithmetic correctly, and the displayed split tree attains the maximum at each node.
Section 5: M40's optimality in (15) rests on this enumeration; a bug would change M40 (though any valid split still yields a correct, possibly non-maximal, independent set).
standard math Standard strong-product facts: coordinatewise adjacency (2), associativity of the strong product permitting the 5-block grouping into 200 dimensions, and basic counting of Cartesian products.
Sections 1–3: used throughout Lemma 4 and in counting |AH| = t1s2, |AV| = s1t2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Recursive Construction Improving the Lower Bound on the Shannon Capacity of $C_7$." pith.science (2026). https://pith.science/paper/3S5H3OGY

@misc{pith2026260727869,
  author       = {Pith},
  title        = {Pith review of: A Recursive Construction Improving the Lower Bound on the Shannon Capacity of $C_7$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3S5H3OGY}},
  note         = {Machine review of arXiv:2607.27869}
}

abstract

We give a recursive reformulation and extension of the independent set of size $134753$ in $C_7^{10}$ constructed by N. Itty, C. D. Rosin, C. Carstensen, and D. Reichman (arXiv:2607.21517v1). We prove a product lemma that combines gadgets of different dimensions while preserving the required independence conditions. Starting from the size-$367$ independent set in $C_7^5$ of S. C. Polak and A. Schrijver (Information Processing Letters 143 (2019), 37-40), the construction gives an explicitly specified independent set in $C_7^{200}$. Consequently, \[ \Theta(C_7)\geq 3.2587891539086910161967650155\ldots . \] An accompanying program verifies the finite assertions about the five-dimensional base gadget and performs the exact integer computations used in the recursion.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Lean-verified lower bounds for the Shannon capacity of odd cycles
math.CO 2026-07 conditional novelty 5.0 of 10

The paper gives new, marginally stronger lower bounds for the Shannon capacity of odd cycles C7–C23, with the computation claimed fully verified in Lean.

Reference graph

Works this paper leans on

5 extracted references · 1 linked inside Pith · cited by 1 Pith paper

[1]

N. Itty, C. D. Rosin, C. Carstensen, and D. Reichman, Improved lower bounds for the Shannon capacity of odd cycles,arXiv preprint arXiv:2607.21517v1, 2026. https://arxiv.org/abs/ 2607.21517

arXiv 2026
[2]

S. C. Polak and A. Schrijver, New lower bound on the Shannon capacity of C7 from circular graphs,Information Processing Letters143 (2019), 37–40. https://doi.org/10.1016/j.ipl. 2018.11.006

doi:10.1016/j.ipl 2019
[3]

C. E. Shannon, The zero error capacity of a noisy channel,IRE Transactions on Information Theory2(3) (1956), 8–19

1956
[4]

Verification code for the recursive C7 construction, GitHub repository, commit b13031ba76e3,
[2026]

https://github.com/xyz2606/recursive_construction_of_the_Shannon_capacity_ of_C_7/tree/b13031ba76e373fdff4bd0152ae79d1c26969900. 8

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.

[1] [1]

N. Itty, C. D. Rosin, C. Carstensen, and D. Reichman, Improved lower bounds for the Shannon capacity of odd cycles,arXiv preprint arXiv:2607.21517v1, 2026. https://arxiv.org/abs/ 2607.21517

arXiv 2026

[2] [2]

S. C. Polak and A. Schrijver, New lower bound on the Shannon capacity of C7 from circular graphs,Information Processing Letters143 (2019), 37–40. https://doi.org/10.1016/j.ipl. 2018.11.006

doi:10.1016/j.ipl 2019

[3] [3]

C. E. Shannon, The zero error capacity of a noisy channel,IRE Transactions on Information Theory2(3) (1956), 8–19

1956

[4] [4]

Verification code for the recursive C7 construction, GitHub repository, commit b13031ba76e3,

[5] [2026]

https://github.com/xyz2606/recursive_construction_of_the_Shannon_capacity_ of_C_7/tree/b13031ba76e373fdff4bd0152ae79d1c26969900. 8