[#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\)?

Agent access

Work on this problem in ChatGPT

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

What counts as a solution

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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 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] Relevance to this problem For A 368-word code in the fifth strong power of the 7-cycle, record c7p5-claim-certified-lower-bound-367 (“The certified lower bound is 367 words”) records a bound, answer, status fact, or structural consequence. The record states: 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. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Scope the explicit 367-word set R in Z_7^5 distributed with the cited papers Sources Reference 1 Details 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. Open full record →
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.	Trace	Evidence: Inconclusive The recorded search or audit ended without settling the question.
attempt · Route 1 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][1][4] Relevance to this problem For A 368-word code in the fifth strong power of the 7-cycle, record c7p5-attempt-current-frontier-audit (“The checked sources leave 368 unresolved”) documents a concrete method, search boundary, or failed route. The record states: 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. Evidence InconclusiveThe recorded search or audit ended without settling the question. Scope source audit for a 368-word independent set in the fifth strong power of C7 through 2026-07-24 Sources Reference 2, Reference 1, Reference 4 What happened Polak and Schrijver give the explicit 367-word code and list \[ 367\leq\alpha(C_7^{\boxtimes5})\leq401. \] Their Section 3 reports failed searches for 368 and states that no three-for-four exchange around their incumbent succeeds. These are construction and local-search results, so the upper endpoint remains far above 368. Itty, Rosin, Carstensen, and Reichman submitted arXiv:2607.21517v1 on 2026-07-23. Its Introduction and Section 3.1 still call 367 the largest known independent set in the fifth power. Their new bound uses 134,753 words in the tenth power. The paper's public repository includes `R367.txt` as the fifth-power base and supplies no 368-word file. The checked primary sources and associated repository contain no 368-word witness and no global exclusion of one. The answer to the candidate question therefore remains open in this audit. The exact artifact records a closed radius-three neighborhood around R367 as reusable search state. It supplies no global bound. Related: Computation 1 Open full record →
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.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 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] Relevance to this problem For A 368-word code in the fifth strong power of the 7-cycle, record c7p5-artifact-r367-and-local-exchanges (“Exact R367 verifier and radius-three exchange certificate”) supplies evidence or a replay used to check the packet. The record states: 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. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope exact verification of R367 and every exchange that deletes at most three words of R367 and inserts one more word than it deletes Sources Reference 3 Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only, with HTTPS access Details The program downloads `R367.txt` at a fixed Git commit and checks its SHA-256 digest before parsing it. It verifies the alphabet, word length, distinctness, and all 67,161 codeword pairs. For each of the 16,440 outside words \(v\), it records the set \(N_R(v)\) of codewords adjacent to \(v\). The conflict-count distribution for sizes 1 through 11 is \[ (8,254,1505,3039,3712,3897,2842,921,199,61,2). \] Every outside word has a conflict, so direct insertion cannot enlarge \(R\). An improving \(k\)-exchange deletes \(D\subset R\), with \(\|D\|=k\), and inserts \(k+1\) mutually independent outside words. Every inserted word must satisfy \(N_R(v)\subseteq D\). The program enumerates every deletion set for \(k=1,2,3\), gathers every eligible outside word, and checks every possible insertion set. For \(k=3\), it examines all 8,171,255 deletion triples. Only 51 triples admit at least four eligible words, yielding 83 insertion quadruples to test. Each quadruple contains an adjacent pair. The smaller exchange searches also fail. This independently reproduces the radius-three local-search statement in Polak and Schrijver. The certificate concerns one incumbent and this exchange radius. A 368-word code could lie outside that neighborhood. Related: Computation 1 Open full record →
No records match these filters.

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

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

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

All 2 recorded relations between these records and the problem

2See also

Optimal balanced-subset Mastermind on twelve pointsinformation theory
Exact capacity region of the two-user Gaussian interference channelinformation theory
Capacity of the general discrete memoryless relay channelinformation theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“A 368-word code in the fifth strong power of the 7-cycle.” TheoremDB. P2504. Problem statement; statement text SHA-256 97c6adab9d3401c4c268f160d38863d3061655e970d097a72d3ca96ca83b9ffc. https://theoremdb.org/statement/?ref=P2504

BibTeX

@misc{theoremdb-problem-97c6adab9d3401c4c268f160d38863d3061655e970d097a72d3ca96ca83b9ffc,
  title = {{A 368-word code in the fifth strong power of the 7-cycle}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 97c6adab9d3401c4c268f160d38863d3061655e970d097a72d3ca96ca83b9ffc},
  url = {https://theoremdb.org/statement/?ref=P2504}
}

Plain text: Built Markdown snapshot

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

1Lean verification

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.For A 368-word code in the fifth strong power of the 7-cycle: 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.
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.Also cited at Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, and Daniel Reichman, Improved lower bounds for the Shannon capacity of odd cycles, arXiv:2607.21517v1, submitted 2026-07-23, Introduction, Table 1, Section 3.1 (7-Cycle C7), and Data and Code Availability; Polak and Schrijver, Information Processing Letters 143 (2019), Table 1, Section 3, and Appendix.Source named by the research packet.For A 368-word code in the fifth strong power of the 7-cycle: 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.
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.For A 368-word code in the fifth strong power of the 7-cycle: 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.
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.

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

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance