The conjectured consistency probability formula for cycles

The conjectured formula is false for every cycle length $n\ge3$. Its exact corrected version is

$$\boxed{ q(C_n) = s^n+t^n-\frac1{4^n}-\frac1{2\cdot8^n}, \qquad s=\frac{17+\sqrt{97}}{32}, \quad t=\frac{17-\sqrt{97}}{32}. }$$

The published final term $-8^{1-n}$ is incorrect, and the discrepancy is

$$q(C_n)-q_{\mathrm{conjectured}}(C_n) = \frac{15}{2\cdot8^n}>0.$$

In particular, although the source reports agreement for $n=3,\ldots,7$, exhaustive exact enumeration at $n=3$ gives

$$q(C_3)=\frac{2397}{4096},$$

whereas the stated conjecture gives $2337/4096$.

Here is a finite-state proof of the corrected formula for every $n$. Each uniformly random Boolean equation on an edge determines a uniformly random binary relation $R\subseteq\{0,1\}^2$. There are 16 equally likely relations, viewed as $2\times2$ Boolean matrices. Their composition is

$$(R\circ S)_{ij} = \bigvee_{a=0}^{1}(R_{ia}\wedge S_{aj}).$$

An assignment around the cycle exists if and only if the product $R_1\circ\cdots\circ R_n$ has a nonzero diagonal entry.

Discard the absorbing zero relation. The other relations have six classes under independent row and column permutations: one entry, one full row, one full column, a permutation matrix, three entries, and four entries. Their respective class sizes are

$$d=(4,2,2,2,4,1),$$

and the proportions having a nonzero diagonal entry are

$$g=\left(\frac12,1,1,\frac12,1,1\right)^{\mathsf T}.$$

Counting right multiplication by each of the 16 relations gives the exact class-transition matrix

$$L= \begin{pmatrix} 8&4&0&0&0&0\\ 6&9&0&0&0&0\\ 0&0&8&0&0&4\\ 4&2&2&2&4&1\\ 2&1&4&0&4&4\\ 0&0&6&0&0&9 \end{pmatrix}.$$

Thus the number of consistent edge systems is

$$A_n=dL^{n-1}g.$$

For

$$P(X) = (X-2)(X-4)(X^2-17X+48),$$

direct integer multiplication gives

$$P(L)(2g)=0.$$

Consequently

$$A_{n+4} = 23A_{n+3}-158A_{n+2} +424A_{n+1}-384A_n.$$

The initial values are

$$A_1=12,\quad A_2=175,\quad A_3=2397,\quad A_4=32377.$$

Writing $\lambda_\pm=(17\pm\sqrt{97})/2$, these initial values and the recurrence give

$$A_n = \lambda_+^n+\lambda_-^n-4^n-2^{n-1} \qquad(n\ge1).$$

Division by $16^n$ proves the corrected probability formula for every simple cycle $n\ge3$.

Source: P. Horak and I. Semaev, “Inconsistency Probability of Sparse Equations over $\mathbb F_2$,” arXiv:2603.24890, Conjecture 20.