[#P2504] A 368-word code in the fifth strong power of the 7-cycle
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\)?
1Remarks
Remark 1. 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 2. An independent set is therefore a code in which each pair differs by circular distance at least two in some coordinate.
2What 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.
1Status
Current status (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.[1]
1Records
Notes and companion material
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\).
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\).
How the 3 records connect
ProblemA 368-word code in the fifth strong power of the 7-cycle
2See also
- Capacity of the general discrete memoryless relay channelinformation theory
- Exact capacity region of the two-user Gaussian interference channelinformation theory
- Optimal balanced-subset Mastermind on twelve pointsinformation theory
How to cite
TheoremDB contributors, “A 368-word code in the fifth strong power of the 7-cycle,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/c7-fifth-power-independent-368This page as plain text: c7-fifth-power-independent-368.md
This problem includes 3 records joined by 2 typed links, sourced from arxiv.org[2], current as of July 24, 2026.
1References
- 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. ↗preprint · reference source · arXiv:1808.07438v2 · checked 2026-07-24Source use: citation only.Gives the earlier circular-graph construction and explicit code used as the comparison point for the 367-word certificate.
- Packet source. 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. ↗preprint · reference source · arXiv:2607.21517v1 · checked 2026-07-24Source 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.
- 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. ↗dataset · dataset source · Git commit f839cae71ad33e6fa6e4195f01518e11f497ce07 · checked 2026-08-01Source use: original summary.Supplies the exact 367-word certificate checked independently by the packet artifact.
- 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. ↗software · software source · commit f839cae71ad33e6fa6e4195f01518e11f497ce07 · checked 2026-07-24Source use: original summary.Contains the authors' C7 construction and search files at the commit used for the packet replay.
Explicit finite code-construction target derived from the published incumbents.