PaperlayerView exact revision on arXiv

Source-linked AI summary

Strengthening Recursive Constructions for Zero-Error Shannon Capacity

Ravi Tandon

arXiv:2608.30273v1cs.ITcs.LGmath.CO

TL;DR

The paper addresses the unknown Shannon capacity of odd cycles beyond C5, focusing on improving lower bounds for C7 through larger independent sets in strong powers. It develops heterogeneous refinements of Gao’s and BPZ’s recursive constructions, using auxiliary structure according to downstream role. The resulting framework illustrates that intermediate constructions with equal dimension and current code size can differ in later recursive value.

  • Problem

    The exact Shannon capacity of C7 remains unknown, so the problem is to construct increasingly large independent sets in strong powers of C7.

  • Method

    The paper introduces heterogeneous refinements of Gao’s binary product and the BPZ multi-gadget recursion, allowing auxiliary structures and recursive roles to use different intermediate constructions.

  • Results

    The paper reports an improved lower bound for C7 from its refined recursive constructions.

  • Takeaways & Limitations

    Intermediate constructions with the same dimension and current code size can have different downstream value depending on their recursive use.

  • Takeaways & Limitations

    The explored space of heterogeneous codebooks, orientations, and recursive product trees remains sparse, and a two-sided extension requires additional compatibility conditions.

Abstract

from arXiv · show

The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle $C_5$, making odd cycles a central open problem in zero-error information theory. Improving the known lower bounds requires constructing large independent sets in strong powers of these graphs. Recent AI-assisted work has produced a rapid sequence of improvements: building on the construction of Itty et al., Gao developed a recursive product construction for combining structured independent sets, and Buys, Polak, and Zuiddam (BPZ) subsequently strengthened this through a richer recursion framework. We continue this line of AI-assisted exploration and introduce a heterogeneous refinement of these constructions. The central observation is that the usefulness of an intermediate construction depends not only on the size of its current main independent set, but also on the auxiliary structure it carries into subsequent recursion. Consequently, different parts of that auxiliary structure need not use the same independent set, and different occurrences in a recursion need not use the same intermediate representation. We formalize this for Gao's binary product and derive explicit propagation rules showing how heterogeneous choices strengthen the resulting gadget while leaving its current code size unchanged, then extend the principle to the more general BPZ framework, tailoring constructions to the distinct roles they play within the recursion. Applying these refinements to the seven-cycle $C_7$, we obtain an independent set in $C_7^{\boxtimes 500}$ yielding $Θ(C_7)\ge 3.25883262\ldots$, improving the best known lower bound. Beyond the numerical gain, the results illustrate a general principle for recursive zero-error constructions: intermediate structures with the same dimension and current code size can have different downstream value depending on where and how they are used in the recursion.

1 Introduction

Zero-error Shannon capacity asks which communication rates remain possible when decoding confusion is forbidden, represented through independent sets in strong powers of confusability graphs. The introduction focuses on C7 as the first unresolved odd cycle and presents heterogeneous recursive constructions for improving its lower bounds.

  • Zero-error communication: Zero-error communication requires codes whose messages cannot be confused, and blocklength-d codes correspond to independent sets in G⊠d.An independent set of size M yields the lower bound Θ(G) ≥ M^(1/d).
  • The seven-cycle C7: C7 is the smallest odd cycle with unknown Shannon capacity, motivating larger independent sets in its strong powers.The Lovász upper bound is Θ(C7) ≤ 3.31766720….
  • Recent progress: Lower-bound progress moved from finite-dimensional constructions to AI-assisted recursive mechanisms developed by Itty et al., Gao, and BPZ.The progression includes Itty et al.’s dimension-10 construction, Gao’s binary recursion, and BPZ’s stronger structure and richer recursion.
  • Contribution: The paper formalizes heterogeneous choices in recursive gadgets, arguing that an intermediate construction’s auxiliary structure matters alongside its current independent-set size.Different auxiliary components may use different independent sets when the required separation conditions permit.
  • Contribution: The paper extends this principle to the BPZ framework and supports the constructions with explicit propagation rules, finite certificates, and exact arithmetic.The stated goal is reproducibility and independent verification of the constructions and resulting bounds.

2 Problem Statement and Background

Zero-error Shannon capacity reduces to finding large independent sets in strong graph powers, with C7 remaining unresolved despite progressively stronger constructions. Recent structured and recursive products improve normalized lower bounds by preserving auxiliary gadget structure for further recursion.

  • Zero-error communication: Zero-error codes of blocklength d correspond to independent sets in G⊠d, yielding the lower bound Θ(G) ≥ |I|^1/d.The normalized size, rather than raw code size, enables comparisons across blocklengths.
  • The seven-cycle C7: 10 = 3.1622776601… is optimal for C7⊠2, but higher-dimensional joint constructions produce larger normalized bounds than two-use coding.The two-use code improves on independent repetition, while C7 remains unsettled at larger blocklengths.
  • The seven-cycle C7: C7 has unknown Shannon capacity, with Lovász’s theta function giving the upper bound Θ(C7) ≤ 3.317667207394095….The unresolved gap motivates larger independent sets in higher strong powers.
  • Recent constructions: 343^1/5 ≈ 3.21410, 367^1/5 ≈ 3.257866, and 134753^1/10 > 3.258020 mark successive improvements in C7 lower bounds.The 134753-word construction modifies a Cartesian product using a 359-word core and two routed families of size 8 · 367.
  • Recursive constructions: Gao converted Itty et al.’s structured ten-dimensional construction into a recursive product by preserving gadget profiles and auxiliary sets under combination.The product reproduces the 134753-word construction while producing another gadget, enabling iteration.
  • Recursive constructions: Buys, Polak, and Zuiddam improved Gao’s bound to Θ(C7) ≥ 3.258805369885…, with recursive calculations and base gadgets fully formalized in Lean.This progression demonstrates that structured intermediate representations can support stronger recursive constructions than one-time Cartesian products.

3 Heterogeneous Refinement of Recursive Gadgets

The heterogeneous refinement allows different auxiliary classes to use different independent sets, preserving the current Gao product code while improving the structure propagated to later recursion. This flexibility supports new intermediate gadgets and recursion trees whose benefit depends on auxiliary profiles, yielding an improved C7 lower bound.

  • Motivation: Gao’s gadget value depends on its current code size and on auxiliary structure propagated into later products.The profile records the main independent-set size, private-pair structure, and auxiliary classes that behave differently in subsequent constructions.
  • Heterogeneous construction: Heterogeneity lets different parts of the auxiliary set use different left-hand independent sets when the required separation conditions hold.The three choices J0, JH, and JV replace Gao’s uniform choice while preserving separation through distinct right-hand classes and within-class independence.
  • Propagation rules: The heterogeneous construction preserves Gao’s product code, propagated private pairs, transversals, and current code size while changing the auxiliary structure.The resulting auxiliary set is verified to be independent and to satisfy the required avoidance condition, so it forms a valid Gao gadget.
  • Application to C7: The fifteen-dimensional heterogeneous gadget has main-set size a15 = 49495055, equal to the corresponding ordinary Gao product, but carries more useful auxiliary structure.Its downstream value comes from how the profile distributes information among neutral, H-side, and V-side classes rather than from an immediate code-size increase.
  • Application to C7: The same fifteen-dimensional gadget is reused in two branches with different roles, producing 25-, 40-, and 30-dimensional states before later combination.This reorganized recursion tree treats the heterogeneous profile as a resource whose usefulness depends on where the gadget appears.
  • Application to C7: 3.2588236744275819433344360437765093813959865800495343... improves Gao’s bound and the first BPZ refinement, while remaining below the stronger BPZ multi-gadget bound.The construction uses the same five-dimensional base gadget as the first BPZ refinement; its improvement comes from new intermediate gadgets and recursion reorganization.

4 Heterogeneity in the BPZ Multi-Gadget Recursion

The BPZ framework preserves seven labeled constituent families and their separation relations while combining representations through admissible rules. The paper introduces heterogeneous choices within this framework and obtains an improved C7 lower bound.

  • Heterogeneous refinement: Heterogeneous refinements allow different intermediate representations and auxiliary structures to be selected for distinct roles in the recursion.The paper derives this refinement by converting Gao gadgets into BPZ seven-family representations and tracking their cardinality vectors and orientations.
  • Framework relation: Gao’s binary product is one particular rule within BPZ’s more general multi-gadget framework.BPZ retains more internal structure than Gao’s fixed binary product, enabling more flexible combinations.
  • BPZ representation: BPZ represents each gadget with seven independent families linked by prescribed separation relations.The labels are B, N, A, D, O, H, and V.
  • Admissible combining: An admissible combining rule specifies Cartesian products of input families whose unions preserve independence and required separations.Condition (i) handles independence within output families, while Condition (ii) preserves separation between distinct output families.
  • C7 construction: 4 · 25 = 100 base blocks produce an independent set in C7^⊠500 when terminal code K4a combines four representations with cardinality vector n25.The BPZ construction uses S2a, S3a, and S3b before applying K4a.
  • Numerical improvement: 4.634433259274595060086 × 10^-6 is the gain in the normalized lower bound over BPZ’s previous value.The new bound is Θ(C7) ≥ 3.258832620353266309121539051810475..., compared with BPZ’s 3.258827985920007034526478965794221....

5 Concluding Remarks and Open Problems

The paper concludes that recursive zero-error constructions should evaluate intermediate structures by their downstream utility, not only by immediate code size. It identifies broader search, two-sided heterogeneity, and applications to other unresolved capacities as open directions.

  • Conclusions: Intermediate structures with equal dimension and current main-code size can have different downstream value because they carry different auxiliary structure.This motivates treating recursive construction as structured, multi-objective optimization rather than successive local optimization.
  • Open problems: A systematic search should retain multiple intermediate profiles and evaluate them according to their possible downstream roles.The paper notes that heterogeneous codebooks, orientations, and recursive product trees have so far been explored only sparsely.
  • Open problems: A genuinely two-sided extension of Theorem 1 would vary both coordinates but requires additional compatibility conditions for separation.The stated condition is that every pair of product blocks be separated in at least one coordinate.
  • Open problems: The same principles could be investigated for other odd cycles and graphs whose Shannon capacities remain unknown.The paper also suggests jointly optimizing heterogeneous constructions, BPZ combining rules, and terminal codes.
  • Broader significance: The results reinforce zero-error Shannon capacity as a benchmark for AI-assisted mathematical discovery because targets are precise and constructions independently checkable.The conclusion emphasizes ideas, search methods, and verification tools in addition to numerical gains.

Code and Reproducibility

The paper provides code and machine-readable certificates for reproducing its constructions and numerical bounds.

  • Reproducibility: The accompanying repository contains neighborhood checks, recursive propagation routines, and exact-arithmetic computations supporting the reported bounds.Certificate data and final arithmetic for Theorem 2 are recorded in Appendix B.

Disclosure of AI Use

The author used large language models throughout mathematical exploration, proof development, computational verification, and manuscript refinement, while attributing support for the claims to proofs and finite computations.

  • AI use: Large language models were used to explore ideas, develop and check proofs, implement searches and verification scripts, and refine the manuscript.The author states responsibility for the results and their presentation.

Appendix A: BPZ Combining Rules and Terminal Codes

Appendix A records the BPZ combining rules and terminal codes as finite rule data, with ordered input conventions and Lean-verified admissibility and separation.

  • Rule representation: The appendix defines combining rules through output labels and ordered input words.For a rule S_m^α, T^(mα)_λ denotes the component associated with output label λ.
  • Formalization: The finite rule library is transcribed from the BPZ Lean repository files.The listed sources include ShannonBounds/Substitutions.lean and ShannonBounds/TerminalCodes.lean.
  • Rule inventory: The library covers binary and ternary combining rules together with terminal codes K3a, K4a, and K4b.The passages enumerate S2a, S2b, S3a through S3h, and the terminal-code family.
  • Verification: Admissibility of combining rules and pairwise separation of terminal codes are verified in the cited Lean source.This supplies a formal verification basis for the rule data used by the framework.

A.1.1 The rule S2a (20 words)

This section lists the ordered input words assigned to output labels for the BPZ combining rules and records the finite construction data used by the framework.

  • S2a: The rule tables assign ordered input words to output labels such as B, N, A, D, O, H, and V.For example, S2a specifies separate word lists for outputs B and N, while ternary rules provide lists for multiple labels.
  • Ternary rules: The ternary rule tables enumerate distinct input-word families for outputs B, N, A, D, O, H, and V.The supplied entries cover rules including S3a, S3b, S3c, S3d, S3e, S3f, S3g, and S3h.
  • Alternative assignments: Rules S3b through S3h provide alternative finite word assignments for the same output-label vocabulary.Their tables differ in the ordered triples assigned to each output, including the H and V rows.
  • Encoding: The appendix uses base-7 encodings and an explicit transformation T on five coordinates modulo 7.The displayed map sends (w0, w1, w2, w3, w4) to (2 − w1, w3, w0, 2 − w2, w4) modulo 7.
  • Heterogeneous exchange: Eight simultaneous exchanges preserve independence and cardinality while changing the auxiliary-set neighborhood relation.Each inserted word has one confusable neighbor matching the removed word, inserted words are pairwise nonconfusable, and removed words lie in the relevant closed neighborhood while inserted words do not.

B.2 Certificate ledger

The certificate ledger organizes the finite counts and reference sets needed to verify the construction, while distinguishing auxiliary decompositions used in different certificates.

  • Reference sets: The ledger defines the main independent set and neutral auxiliary components used in the certificate calculations.The notation tracks main codes, auxiliary sets, and their neutral references across dimensions 15 and 30.
  • Certificate chain: The final dependency chain uses four nontrivial finite certificates, each evaluated against a neutral reference.Table 4 presents these certificates as the finite data supporting the final construction.
  • Reference distinction: The warmup uses a reference set differing from the X0,15 reference used in certificate C2.The passage identifies this distinction as the neutral part of the heterogeneous gadget’s auxiliary set.

B.3 Component verification of q++

The q++ certificate is verified by decomposing a 30-dimensional independent set into seven Gao-product components and computing each contribution from joint neighborhood frequencies.

  • Component decomposition: The 30-dimensional main independent set is the disjoint union of seven Gao-product components.Table 5 lists the components used in the certificate construction.
  • Transformed contributions: Each component’s contribution is evaluated after applying T ×6 to the corresponding product construction.The resulting contributions feed the construction of J++30 outside the neutral reference neighborhood.
  • Input decomposition: The calculation separates neutral and nonneutral auxiliary parts of the two ordered inputs defining the left reference gadget.The inputs are represented by U0, V0 and their respective nonneutral parts U1, V1.
  • Neighborhood calculation: Product neighborhood membership is computed using union distribution and N(A × B) = N(A) × N(B).This reduces membership in the product neighborhood to corresponding conditions on the factor sets.
  • Exact verification: Joint frequencies of neighborhood indicators ensure overlaps between the two conditions are counted correctly.Exact products and sums of these frequencies yield each product component’s contribution.

B.4 Exact final arithmetic

The final BPZ computation applies the terminal code K4a to the constructed inputs, producing an independent set in C⊠500. The preceding arithmetic records the coordinate vectors and the ternary-rule calculation used in this construction.

  • Final BPZ inputs: The final BPZ inputs are recorded as three identical seven-family cardinality vectors in the order (B, N, A, D, O, H, V).Each vector has the same listed cardinalities.
  • Ternary combination: Applying ternary rule S3b to the ordered split 25 = 6 + 11 + 8 produces the displayed three-coordinate output.The output is recorded across three consecutive arithmetic lines.
  • Consistency check: The zero O-coordinate agrees with the condition T (3b), O = ∅.This consistency check is stated immediately before terminalization.
  • Terminal construction: Applying terminal code K4a to four copies of the ternary output produces an independent set in C⊠500.The resulting cardinality data continue across the displayed arithmetic lines.

B.5 Input parameters for the heterogeneous products

Table 6 collects the input parameters for nine applications of Theorem 1 in the heterogeneous products. It records ordered gadget inputs, codebook decompositions, one-sided parameters, and neighborhood-count certificates, with a fifteen-dimensional warmup in its first row.

  • J0 parameters: For each ordered pair (GL, GR), (j0, o0, h0, v0) describes J0's decomposition relative to GL's transversals.The corresponding qH count is evaluated against the neutral auxiliary part of the same left gadget.
  • Neighborhood counts: Independence implies X ∩ N(S) = S for an independent set X and subset S ⊆ X, so a one-sided codebook equal to XL has q-value sL − oL.Two such counts are used in the table's calculations.
  • Certificates: The remaining q-values are the certificates C1, C2, C3, and C4 from Table 4.These certificates supply the other neighborhood-count inputs.
  • Table scope: Table 6 lists complete input parameters for the heterogeneous products in Section 4.2, with all decompositions and neighborhood counts relative to the indicated left gadget.The table has separate parts for ordered gadget inputs and one-sided codebooks.
  • Reproducibility: The BPZ base data, combining rules, terminal codes, certificates, and verification scripts are anchored to specified repository files and commits.Machine-readable certificate files and exact-arithmetic verification scripts are available in the cited repository.
Loading 2608.30273v1…