# P2594: Hard-core coefficient log-concavity on the first ten thousand four-cycle strips

- ID: `P2594`
- Reference: `hard-core-c4-strip-log-concavity`
- Page: https://theoremdb.org/statements/P2594
- Record maturity: Reviewed problem with recorded work

## Problem

For \(1\le n\le10000\), let \(G_n=C_4\mathbin{\square}P_n\) and \(I_n(z)=\sum_k i_{n,k}z^k\) be its independence polynomial. Is the coefficient sequence \((i_{n,k})_k\) log-concave for every such \(n\)?

### Problem setup

- **Remark.** i_{n,k} is the number of k-vertex independent sets in G_n.
- **Definition.** C_4 square P_n denotes the Cartesian product C_4 with the n-vertex path.

### What counts as a solution

- Give an exact transfer sweep through n=10000 with checksums, or report the first n and coefficient index where log-concavity fails.

## Status

Exact transfer verifies log-concavity for every \(C_4\mathbin{\square}P_n\) with \(1\le n\le3000\); the cases \(3001\le n\le10000\) remain unchecked. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (Every four-cycle strip through length 3000 has a log-concave independence sequence).** Exact transfer verifies log-concavity for every \(C_4\mathbin{\square}P_n\) with \(1\le n\le3000\); the cases \(3001\le n\le10000\) remain unchecked.

Let
\[
I_n(z)=\sum_{k=0}^{2n}i_{n,k}z^k
\]
be the independence polynomial of \(C_4\mathbin{\square}P_n\). Exact integer computation gives
\[
i_{n,k}^2\geq i_{n,k-1}i_{n,k+1}
\]
for every \(1\leq n\leq3000\) and \(1\leq k\leq2n-1\). The sweep checks exactly
\[
\sum_{n=1}^{3000}(2n-1)=9{,}000{,}000
\]
inequalities. All are strict.

The independent masks in one four-cycle column are
\[
0,1,2,4,5,8,10.
\]
Cycle symmetry reduces their terminal polynomials to \(a_n\) for the empty mask, \(b_n\) for each singleton, and \(c_n\) for each opposite pair. Starting with
\[
(a_1,b_1,c_1)=(1,z,z^2),
\]
the exact transfer is
\[
\begin{aligned}
a_{n+1}&=a_n+4b_n+2c_n,\\
b_{n+1}&=z(a_n+3b_n+c_n),\\
c_{n+1}&=z^2(a_n+2b_n+c_n),
\end{aligned}
\qquad I_n=a_n+4b_n+2c_n.
\]
The program checks this reduction against the full seven-state transfer through \(n=20\).

At \(n=1\), the least margin is 14 at \(k=1\). For every \(2\leq n\leq3000\), the least margin occurs at \(k=2n-1\), where the adjacent triple is
\[
\bigl(4(n^2+n-2),4n,2\bigr)
\]
and the margin is \(8n^2-8n+16\). The requested lengths \(3001\) through \(10000\) remain unchecked.

### Background and intake notes

This is a finite transfer-matrix sweep with reusable progress by terminal n. Exact work has reached n=40.

- Original intake status: Status unknown. Independence-polynomial unimodality for grid strips may be known.
- The seven independent row masks of C_4 give an exact polynomial transfer matrix. Store coefficient hashes and the least log-concavity slack at each n.
- Real-rootedness fails already at n=2, so a sweep should test the coefficient inequalities directly rather than use roots as a proxy.

- Recorded example: I_2(z)=1+8z+16z^2+8z^3+2z^4, which is log-concave and has nonreal roots.

### Prior approaches

- **Route 1** (supported): The located primary sources support the transfer construction and the claw-free real-rootedness boundary; none reports this cylindrical width-four log-concavity sweep. [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python regenerates every coefficient with integers, tests every adjacent triple, and hashes eight checkpoint rows. [2](#reference-2)

### Computational notes

- Exact integer transfer matrices computed every I_n through n=40 and found no log-concavity violation. Numerical root calculation at n=2 found imaginary parts as large as approximately 1.71319, confirming that real-rootedness cannot prove this case.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `hard-core-c4-strip-log-concavity`, 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>Maria Chudnovsky and Paul Seymour, “The roots of the independence polynomial of a clawfree graph”. Journal of Combinatorial Theory, Series B 97(3) (2007), 350-357. DOI 10.1016/j.jctb.2006.06.001. Journal of Combinatorial Theory, Series B 97(3) (2007), 350-357 https://doi.org/10.1016/j.jctb.2006.06.001
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Hard-core coefficient log-concavity on the first ten thousand four-cycle strips: The grid-transfer literature gives the method, while this coefficient question appears unsettled. The located primary sources support the transfer construction and the claw-free real-rootedness boundary; none reports this cylindrical width-four log-concavity sweep.
2. <a id="reference-2"></a>Neil J. Calkin and Herbert S. Wilf, “The Number of Independent Sets in a Grid Graph”. SIAM Journal on Discrete Mathematics 11(1) (1998), 54-60. DOI 10.1137/S089548019528993X. Neil J. Calkin and Herbert S. Wilf, The Number of Independent Sets in a Grid Graph, SIAM Journal on Discrete Mathematics 11(1) (1998), 54-60, Section 1; Maria Chudnovsky and Paul Seymour, The Roots of the Independence Polynomial of a Clawfree Graph, Journal of Combinatorial Theory, Series B 97(3) (2007), 350-357, DOI 10.1016/j.jctb.2006.06.001 https://doi.org/10.1137/S089548019528993X
   - Also cited at SIAM Journal on Discrete Mathematics 11(1) (1998), 54-60, Section 1
   - Also cited at Exact transfer and replay certificate in hcc4-artifact-exact-transfer-sweep
   - Also cited at Inline Python 3 exact computation executed on 2026-07-25
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Hard-core coefficient log-concavity on the first ten thousand four-cycle strips: The located primary sources support the transfer construction and the claw-free real-rootedness boundary; none reports this cylindrical width-four log-concavity sweep.
   - Source named by the research packet.