Strengthening Recursive Constructions for Zero-Error Shannon Capacity

Ravi Tandon

cs.ITAug 31, 2026

Strengthening Recursive Constructions for Zero-Error Shannon Capacity

Authors: Ravi Tandon

Organizations: School of Electrical, Computing and Software Engineering, University of Arizona, Tucson, AZ 85721, USA.

Abstract

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.

Explore similar work

Jul 23, 2026cs.IT

Improved lower bounds for the Shannon capacity of odd cycles

The Shannon capacity

Θ(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

α(G^d)^{1/d}

for any

d

, where

α(G^d)

is the independence number of the

d

-th strong product of

G

. We construct independent sets of size

134753

C_7^{10}

21909

C_{11}^{6}

62530

C_{13}^{6}

, and

8076974

C_{15}^{8}

, improving the best known lower bounds for the Shannon capacity of these graphs to

Θ(C_7)\geq 134753^{1/10}>3.258020

Θ(C_{11})\geq 21909^{1/6}>5.289773

Θ(C_{13})\geq 62530^{1/6}>6.300109

, and

Θ(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.

Nathaniel Itty, Christopher D. Rosin, Chase Carstensen +1

Maximum Independent Set Lower Bounds Combinations

Ask PDF

May 2, 2026cs.LG

Linear-Readout Floors and Threshold Recovery in Computation in Superposition

Two recent approaches to computation in superposition reach different recursive capacity regimes: Hänni et al. certify

\tilde{O}(d^{3/2})

computable features in width

d

via an approximate-linear recursive template, while Adler and Shavit reach near-quadratic capacity (up to logarithmic factors) using thresholded Boolean recovery. The main contribution of this paper is conceptual: we argue these results are not contradictory because they maintain different interface invariants, and we formalize the distinction. As a tool, we record a rank-trace Welch-type lower bound for biorthogonal linear readouts: for

F \gg d

, the worst-case off-diagonal cross-talk of any unit-diagonal linear readout is

Ω(d^{-1/2})

, and the bound is tight on average for unit-norm tight frames. At quadratic feature load

F=d^2

, random-support threshold recovery succeeds for sparsities

s=O(d/\log d)

, while linear readouts still incur

Ω(s/d)

average per-coordinate squared error on Bernoulli sparse states. Matching the Welch floor against the published tolerance of the Hänni correction layer explains the

d^{3/2}

scale as a compatibility threshold for that template, not a universal upper bound. Robust nonlinear reset beyond the Hänni template is left open.

Hector Borobia, Elies Seguí-Mas, Guillermina Tormo-Carbó

Superposition Readout Decision Thresholds Sparse Observations Ceiling

Ask PDF

Apr 16, 2026quant-ph

Learning to Concatenate Quantum Codes

Concatenating quantum error correction codes scales error correction capability by driving logical error rates down double-exponentially across levels. However, the noise structure shifts under concatenation, making it hard to choose an optimal code sequence. We automate this choice by estimating the effective noise channel after each level and selecting the next code accordingly. In particular, we use learning-based methods to tailor small, non-additive encoders when the noise exhibits sufficient structure, then switch to standard codes once the noise is nearly uniform. In simulations, this level-wise adaptation achieves a target logical error rate with far fewer qubits than concatenating stabilizer codes alone--reducing qubit counts by up to two orders of magnitude for strongly structured noise. Therefore, this hybrid, learning-based strategy offers a promising tool for early fault-tolerant quantum computing.

Nico Meyer, Christopher Mutschler, Dominik Seuß +2

Quantum Error Correction Error Correction

Ask PDF