TheoremDB
All problems

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

Work on this problem in ChatGPT
A neutral state and word schematic for A 368-word code in the fifth strong power of the 7-cycle.A code-rendered placeholder showing only the mathematical setup.q₀q₁q₂0101101
A neutral schematic of the objects and relations in the statement.

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

3 records

Notes and companion materialContext, examples, and computations

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 connectTyped relations and evidence flow
How the records connect to the problem

ProblemA 368-word code in the fifth strong power of the 7-cycle

2See also

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-368

This problem includes 3 records joined by 2 typed links, sourced from arxiv.org[2], current as of July 24, 2026.

1References

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Flag this problem

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.