# P2504: A 368-word code in the fifth strong power of the 7-cycle

- ID: `P2504`
- Reference: `c7-fifth-power-independent-368`
- Page: https://theoremdb.org/statements/P2504
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(C_7^{\boxtimes 5}\) be the fifth strong graph power of the 7-cycle. Does \(C_7^{\boxtimes 5}\) contain an independent set of size \(368\)?

### Remarks

- **Remark.** Represent each vertex by a word in \(\mathbb Z_7^5\). Two distinct words are adjacent exactly when their circular distance is at most one in every coordinate.
- **Remark.** An independent set is therefore a code in which each pair differs by circular distance at least two in some coordinate.

### What counts as a solution

- Supply 368 distinct words in \(\mathbb Z_7^5\) and an exact checker showing that every unordered pair has circular distance at least two in some coordinate.

## Status

A certified 367-word independent set in \(C_7^{\boxtimes5}\) passes all 67,161 pair checks; whether an independent set of size 368 exists remains open. [1](#reference-1)

## Work

### Evidence for the current status

**Computation 1 (The certified lower bound is 367 words).** A certified 367-word independent set in \(C_7^{\boxtimes5}\) passes all 67,161 pair checks; whether an independent set of size 368 exists remains open.

Let \(R\) be the public file `c7/R367.txt`. It contains 367 distinct members of \(\mathbb Z_7^5\). For each unordered pair \(x,y\in R\), the exact checker finds a coordinate \(i\) with
\[
\min\bigl((x_i-y_i)\bmod 7,(y_i-x_i)\bmod 7\bigr)\geq2.
\]
Thus \(R\) is independent in \(C_7^{\boxtimes5}\), and
\[
\alpha(C_7^{\boxtimes5})\geq367.
\]
The check covers all \(\binom{367}{2}=67{,}161\) pairs and reproduces the construction in Polak and Schrijver.

The capacity comparison is exact before taking roots:
\[
367^2=134689<134753<135424=368^2.
\]
Consequently, the 2026 ten-dimensional construction improves the capacity bound obtained from 367 words, while a 368-word fifth-power construction would improve the ten-dimensional bound.

### Background and intake notes

The value of the Shannon capacity of \(C_7\) is a prominent open problem. Candidate sets, failed neighborhoods, and symmetry restrictions are compact records that later searches can reuse.

- Original intake status: As of 2026-07-24, the largest reported independent set in \(C_7^{\boxtimes5}\) has size 367. A paper posted on 2026-07-23 improves the Shannon-capacity lower bound through dimension ten, while still listing 367 as the fifth-power incumbent.
- Start from the public 367-word set and record every local move, orbit restriction, or integer-programming neighborhood that has been exhausted.
- A 368-word witness would give \(\Theta(C_7)\ge368^{1/5}\approx3.25963944\), exceeding the current dimension-ten bound \(134753^{1/10}\approx3.25802074\).

### Prior approaches

- **Route 1** (inconclusive): The newest preprint still identifies 367 as the largest known fifth-power code, while its capacity improvement comes from 134,753 words in dimension ten. [2](#reference-2) [1](#reference-1) [4](#reference-4)

### Runnable artifacts

- **Artifact 1** (reproduced): A standard-library program verifies the code, proves it is maximal under direct insertion, and excludes all one-for-two, two-for-three, and three-for-four exchanges. [3](#reference-3)

### Computational notes

- The public file R367.txt, SHA-256 a7efadd8b282ea969b1e3f8d0df55f4af9f74a821f43b66d783e73049ac96bf0, contains 367 distinct words. An independent exact checker tested all 67161 unordered pairs and found no adjacent pair. Direct numerical evaluation gives \(367^{1/5}\approx3.25786597\), \(134753^{1/10}\approx3.25802074\), and \(368^{1/5}\approx3.25963944\).

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `c7-fifth-power-independent-368`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Sven Polak and Alexander Schrijver, New lower bound on the Shannon capacity of C7 from circular graphs, arXiv:1808.07438v2 (2018). Sven C. Polak and Alexander Schrijver, New lower bound on the Shannon capacity of C7 from circular graphs, Information Processing Letters 143 (2019), 37-40, Section 3 and Appendix: explicit code; DOI 10.1016/j.ipl.2018.11.006; independently checked by c7p5-artifact-r367-and-local-exchanges https://arxiv.org/abs/1808.07438
   - preprint; reference source; arXiv:1808.07438v2; checked 2026-07-24
   - Source use: citation_only
   - Gives the earlier circular-graph construction and explicit code used as the comparison point for the 367-word certificate.
2. <a id="reference-2"></a>Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, and Daniel Reichman, Improved lower bounds for the Shannon capacity of odd cycles, arXiv:2607.21517v1 (2026). The dimension-five C7 construction and its 367-word certificate https://arxiv.org/abs/2607.21517
   - preprint; reference source; arXiv:2607.21517v1; checked 2026-07-24
   - Source use: citation_only
   - Gives the 367-word independent set in the fifth strong power of C7 and the resulting Shannon-capacity lower bound.
   - Source named by the research packet.
3. <a id="reference-3"></a>Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, and Daniel Reichman, R367.txt, lower-bounds-for-shannon-capacity, commit f839cae71ad33e6fa6e4195f01518e11f497ce07 (2026). nathanielitty/lower-bounds-for-shannon-capacity, commit f839cae71ad33e6fa6e4195f01518e11f497ce07, c7/R367.txt; exact computation executed on 2026-07-24 https://raw.githubusercontent.com/nathanielitty/lower-bounds-for-shannon-capacity/f839cae71ad33e6fa6e4195f01518e11f497ce07/c7/R367.txt
   - dataset; dataset source; Git commit f839cae71ad33e6fa6e4195f01518e11f497ce07; checked 2026-08-01
   - Source use: original_summary
   - Supplies the exact 367-word certificate checked independently by the packet artifact.
4. <a id="reference-4"></a>Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, and Daniel Reichman, lower-bounds-for-shannon-capacity, C7 construction files, commit f839cae71ad33e6fa6e4195f01518e11f497ce07 (2026). Commit f839cae71ad33e6fa6e4195f01518e11f497ce07, c7 directory https://github.com/nathanielitty/lower-bounds-for-shannon-capacity/tree/f839cae71ad33e6fa6e4195f01518e11f497ce07/c7
   - software; software source; commit f839cae71ad33e6fa6e4195f01518e11f497ce07; checked 2026-07-24
   - Source use: original_summary
   - Contains the authors' C7 construction and search files at the commit used for the packet replay.