Computability of the Shannon Capacity of Finite Graphs

Computability of the Shannon Capacity of Finite Graphs

Definitions and mathematical statement

For a nonempty finite simple graph $G$, let $\alpha(G)$ be its largest independent-set size. In the strong product $G\boxtimes H$, distinct pairs $(g,h),(g',h')$ are adjacent when each coordinate is either equal or adjacent in its factor. Define \[ \Theta(G)=\sup_{m\ge1}\alpha(G^{\boxtimes m})^{1/m}. \] The computability question asks for one algorithm which, given the exact adjacency matrix of $G$ and integer $t\ge1$, halts and returns a rational $a$ with $|a-\Theta(G)|\le2^{-t}$. No running-time bound is required. Enumerating strong powers gives lower approximations, but without an effective two-sided error bound it does not automatically supply this algorithm. The capacity is not replaced by the logarithm of capacity or an efficiently computable upper relaxation.

Formulation and concept references: [S1].

Short English statement

Can the Shannon capacity of every finite graph be approximated algorithmically to any requested certified accuracy, with no restriction on running time?

Research attempt

Scope, process, and first gap.

This GPT-6 Astra Ultra attempt was prepared on 27 September 2026. The input is the exact finite adjacency matrix, and the output must have a certified additive error for $\Theta(G)$ itself. The work proves lower approximability, gives complete computations for several graph classes, and constructs an abstract computability countertest to the proposed limiting argument. These are established mechanisms, not a solution of the general computability problem.

The source [S1] explicitly distinguishes computability for a graph from computability for a channel specified through real transition probabilities. Determining whether such a probability is exactly zero can obstruct constructing the confusability graph. That obstruction disappears when the graph is already supplied exactly, and [S1] does not claim to resolve this finite-graph question. The first gap here is an effective stopping rule for the lower approximations, or a converging computable upper approximation with which to compare them.

What exhaustive finite search really computes.

Write $a_m=\alpha(G^{\boxtimes m})$ and $N=|V(G)|\ge1$. For any fixed $m$, one can construct the graph on $N^m$ tuples and inspect all vertex subsets to compute $a_m$ exactly. This terminates, although its time is enormous. The strong-product convention makes a Cartesian product of independent sets independent, so \[ a_{m+n}\ge a_ma_n,\qquad 1\le a_m\le N^m. \tag{408.1} \] These inequalities also prove existence of the root limit. Fix $k$ and write $m=qk+r$, with $0\le r<k$. Taking $a_0=1$, repeated use of $408.1$ gives $a_m\ge a_k^q$. Thus \[ \liminf_{m\to\infty}a_m^{1/m}\ge a_k^{1/k}. \] Taking the supremum over $k$, and using the defining upper bound by that supremum, proves \[ \lim_{m\to\infty}a_m^{1/m}=\Theta(G). \] This proof supplies convergence but no effective rate.

Define $L_M=\max_{1\le m\le M}a_m^{1/m}$. The numbers $L_M$ increase to $\Theta(G)$. Roots of integers have computable rational lower and upper enclosures: compare rational $r^m$ with the integer $a_m$. Therefore we can output an increasing rational sequence converging from below. For any rational $r$, the strict inequality $\Theta(G)>r$ is semidecidable by searching for an $m$ with $a_m>r^m$. If equality holds, this search need never halt.

An exact class from matching upper and lower bounds.

Suppose the vertices admit a partition into $r$ cliques. Partition each strong power by the $m$-tuple of clique labels. Each of the $r^m$ resulting cells is a clique, because two distinct tuples in a cell have each coordinate equal or adjacent. Hence \[ \alpha(G^{\boxtimes m})\le r^m,\qquad \Theta(G)\le r. \] If $G$ also has an independent set of size $r$, its Cartesian powers give the opposite inequality, so $\Theta(G)=r$.

This certifies, for example, complete graphs with $r=1$, edgeless graphs with $r=N$, and disjoint unions of $r$ nonempty complete graphs. For the last case, choose one vertex from each component for the independent set. These are finite verifiable certificates. An arbitrary clique partition gives an upper bound but need not match capacity, so its existence alone does not provide arbitrary-accuracy approximation.

A nonintegral example: the pentagon.

Label $C_5$ by $\mathbb Z/5\mathbb Z$, with differences $\pm1$ adjacent. In its strong square, the five tuples \[ (i,2i),\qquad i\in\mathbb Z/5\mathbb Z, \] are independent. For two different labels, either the first-coordinate difference is $\pm2$, or it is $\pm1$ and the second-coordinate difference is $\pm2$. In either event one coordinate is nonadjacent. Hence $\Theta(C_5)\ge\sqrt5$.

Here is the standard orthogonal-representation upper argument of Lovász [E1], specialized and verified directly. Put \[ u_j=\left(\sqrt{1-\frac1{\sqrt5}}\cos\frac{2\pi j}5, \sqrt{1-\frac1{\sqrt5}}\sin\frac{2\pi j}5, 5^{-1/4}\right). \] Each $u_j$ is a unit vector. When $j-k=\pm2$, the inner product is zero, using $\cos(4\pi/5)=-(1+\sqrt5)/4$. For the unit vector $c=(0,0,1)$, \[ |\langle c,u_j\rangle|^2=\frac1{\sqrt5}. \] Assign the tensor product $u_{j_1}\otimes\cdots\otimes u_{j_m}$ to a vertex of the strong power. Distinct independent vertices have a nonadjacent coordinate, so their assigned unit vectors are orthogonal. Bessel's inequality applied to $c^{\otimes m}$ yields \[ \alpha(C_5^{\boxtimes m})\,5^{-m/2}\le1. \] Thus $\Theta(C_5)\le\sqrt5$, proving equality. Rational enclosures of $\sqrt5$ now give any requested certified error without searching larger powers.

This illustrates what a stopping certificate can look like: a finite lower construction and a compatible upper argument agree. It does not show that every graph admits such a pair at a computably bounded search stage.

Why supermultiplicativity does not make limits effective.

Consider a program $e$ on blank input. Define an integer sequence, computably from $e,m$, by \[ b_m(e)= \begin{cases} 2^m,&\text{if }e\text{ halts within }m\text{ steps},\\ 1,&\text{otherwise}. \end{cases} \] It satisfies $1\le b_m\le2^m$ and $b_{m+n}\ge b_mb_n$. If neither shorter simulation sees a halt, the product is one; if either does, the length-$m+n$ simulation sees it and its value is $2^{m+n}$, at least the product.

Nevertheless \[ \sup_m b_m(e)^{1/m} =\begin{cases}1,&e\text{ never halts},\\2,&e\text{ eventually halts}.\end{cases} \] A uniform procedure approximating this supremum within $1/4$ would decide halting, by comparing the answer with $3/2$. Therefore computable terms, exponential boundedness, supermultiplicativity, and existence of a root limit together do not imply uniform computability of that limit.

This is not a graph construction. No claim is made that these sequences equal $\alpha(G^{\boxtimes m})$ for effectively constructed finite graphs. The example refutes a general-purpose convergence argument; proving noncomputability of graph capacity would require a genuine reduction respecting the graph-product constraints.

A sufficient upper-approximation criterion.

Suppose one could compute rational $U_j(G)\ge\Theta(G)$ with $U_j(G)\to\Theta(G)$ for every graph. Combine them with rational lower approximations $l_j(G)\uparrow\Theta(G)$, refining root enclosures as needed. Search until \[ U_j(G)-l_j(G)\le2^{1-t}. \] The midpoint then has error at most $2^{-t}$, and convergence guarantees termination. Replacing $U_j$ by the running minimum makes it decreasing if necessary.

The bound $U_j=N$ is valid but usually does not converge to capacity. An efficiently computable relaxation is likewise insufficient unless one proves that a computable hierarchy of such relaxations converges to $\Theta$ on every finite graph. The accuracy request cannot be discharged by reporting a small difference between consecutive lower bounds: a long plateau can precede a later improvement, as the halting example makes explicit.

Verification and outcome.

The finite checks verify independence of the five pentagon-square tuples and the orthogonality identities numerically at high precision, while the exact trigonometric calculation supplies the proof. Small disjoint-clique products are counted exactly. Tests of delayed-halting sequences check supermultiplicativity for representative finite ranges, independently of the general proof.

UNRESOLVED. Lower semicomputability and the stated exact capacity subcases are established. No computable upper sequence converging to the capacity of every graph, no universal stopping modulus, and no graph-based noncomputability reduction is obtained.

Sources

• S1 Holger Boche and Christian Deppe, Computability of the Zero-Error Capacity of Noisy Channels, arXiv:2010.06873v3 (19 May 2024). https://arxiv.org/html/2010.06873v3. Formulation source.
• E1 L. Lovász, On the Shannon Capacity of a Graph, IEEE Transactions on Information Theory 25 $1979$, 1--7. https://www.sfu.ca/~mdevos/notes/semidef/lovasz-theta.pdf. Original orthogonal-representation method and pentagon capacity; consulted 27 September 2026.